|
『运筹OR帷幄』原创
作者：高建琦
编者按
本文节选自作者参加“OR 青年计划”的结题报告，针对天舒老师在活动时期举荐的一篇论文《Multi -Agent Routing Value Iteration Network》进行重点详述。
1 论文源自
论文源自自于天舒老师发布的 paperlist。日前我的科研课题中触及到多设备人任务分配和路径规划，这篇文案里面部分知识点能够用于我的课题，因此对该文做进一步的详述。该论文发布于 ICML 2020，代码和数据已开源： https://github.com/uber/MARVIN。
2 论文概述
这篇论文提出了一种基于图神经网络的模型（Multi-Agent Routing Value Iteration Network, MARVIN），该模型能够在交通要求动态变化的稀疏连接图中完成基于值迭代网络的多智能体路由问题。另外，该文案还运用通信模块使多个 agent 能够在线协调，更有效地适应变化。
实验方面，该论文中创建了一个模拟环境，以模拟自动驾驶汽车在未知的最小边缘覆盖和交通要求下执行的真实地图。结果表示：1）该论文模型在总成本和运行时间方面明显优于传统的求解器；2）模型拥有较好的扩展性。
3 背景
针对一群设备人制定执行任务的路线问题，一般能够运用TSP(Toth Vigo, 2002) 或VRP(TothVigo, 2002) 模型去处理。TSP 或者 VRP 问题是计算机科学中的经典的 NP-Hard 组合优化问题。尽管有非常多经典的求解器 (Applegate et al, 2006;Helsgaun,2017) 来处理这些问题，但她们一般为离线计算，没法在线调节其处理方法。另一这些求解器中不包括代理之间的在线通信。
这篇文案需要处理的是多车辆自主建图问题，详细描述为：给定一组车辆，按照交通要求找到找到最小的路径代价去完成城市街区的地图构建，其中每一个城市道路最少遍历必定的次数，并且遍历数量事先是未知的，这是由于一个区域可能因为闭塞、交通拥挤、定位错误、传感器故障、卑劣天气要求等原由需要重新收集。
4 关联工作
4.1 车辆路由问题（VRP）
现有 VRP 求解器可分为两类：传统迭代求解器和深度学习办法。传统迭代求解器一般没法在线运用，并且在这些求解器中 agent 之间不可进行任安在线通信，以纳入 agent 当地的观察结果。与传统求解器相比，因为广泛采用重视力机制 (Vinyals et al., 2015; Vaswani et al., 2017) 和图神经网络 (Kipf Welling, 2017; Khalil et al., 2017) 技术，深度学习办法已然作为求解组合问题的有效近似办法。一样，深度学习办法都不是能处理动态环境下的 VRP 问题。
4.2 值迭代网络（VIN）
基于深度学习的路径规划办法亦表示出良好的性能，重点工作包含： 值迭代网络 (Tamar et al.，2016)，它在神经网络中嵌入了来自值迭代 (Bellman, 1954) 的结构偏差;门通路径规划网络 (Lee et al.，2018)，运用通用长短期记忆 (LSTM) 改变了最大池化层(Hochreiter Schmidhuber, 1997)，明显加强了训练稳定性，有助于延长迭代次数;广义值迭代网络 (GVIN)(Niu et al.，2018)，经过用图（Graph）中的边（edge）替换过渡（transition）。然而，以上算法仅能处理简单的路径规划环境，如二维迷宫，而 Dijkstra 的最短路径算法在处理这些问题上已然非常有效。
4.3 图神经网络（GNN）
图神经网络 (Scarselli et al.，2009;Wu et al.，2019) 供给了一种学习图表征的办法，这些表征既与图中的节点数量无关，又与局部邻域中的置换不变式无关。来自节点邻域的信息能够经过图卷积 (Kipf Welling, 2017)、递归神经网络 (Li et al.，2016) 和重视机制 (Yun et al.，2019；Velickovic，2018 年) 等技术聚合得到。图重视力模块亦出此刻基于深度学习的 VRP/TSP 求解器中，如 AM (Kool et al.，2019) 和 EAN (Deudon et al.，2018)。
4.4 多智能体通信
Sukhbaatar 等人 (2016) 对 agent 之间的信息进行了简单求和。Jiang 和 Lu(2018) 利用重视机制识别 agent 之间对自己有用的信息。
5 问题定义
6 MARVIN 框架
在整体框架中重点包含两个模块：值迭代模块（图 1.B）和通信模块（图 1.C）。
6.1 值迭代模块
该模块工作流程为：针对给定的初始节点特征，咱们将其输入图神经网络，而后经过必定次数的迭代将特征解码输出给以上节点的标量值函数，最后选取拥有最大的特征值的节点做为咱们下一个目的点。
6.2 通信模块
因为本文现实问题的部分观察性质，让 agent 交流她们的预期轨迹是有益的，从而能够有更加多的协作行径。为了达到这个目的，咱们提出的模型还拥有一个基于重视力的通信模块。
7 模型训练办法
本文提出的网络框架 MARVIN 能够经过模仿学习或强化学习两种区别的办法进行端到端训练。针对模仿学习，假设有一个依赖于完全可观察的环境的神谕“oracle"，他能够处理本文说到的规划问题。然则，一般 oracle 会减慢训练过程，由于咱们会为每次滚动迭代重新生成一个训练图，oracle 都会基于新图重新进行规划计算。另一，本文还运用强化学习对网络框架进行训练，较其他办法它更难于收敛，但能够直接优化最后目的。
7.1 模仿学习
7.2 强化学习
8 实验结果
实验结果显示：1）利用强化学习办法进行训练的 MARVIN 框架在总成本 cost 和运行时间runtime 方面明显优于传统的求解器；2）MARVIN 框架拥有较好的扩展性，小样本训练的模型拓展到很强样本亦拥有比较好的性能表现。
9 可拓展工作
| 
发表于 2024-8-31 10:12:18