Title: Cooperative Path Planning with Asynchronous Multiagent Reinforcement Learning Show Chinese title

Title: 基于异步多智能体强化学习的协同路径规划

Abstract: In this paper, we study the shortest path problem (SPP) with multiple source-destination pairs (MSD), namely MSD-SPP, to minimize average travel time of all shortest paths. The inherent traffic capacity limits within a road network contributes to the competition among vehicles. Multi-agent reinforcement learning (MARL) model cannot offer effective and efficient path planning cooperation due to the asynchronous decision making setting in MSD-SPP, where vehicles (a.k.a agents) cannot simultaneously complete routing actions in the previous time step. To tackle the efficiency issue, we propose to divide an entire road network into multiple sub-graphs and subsequently execute a two-stage process of inter-region and intra-region route planning. To address the asynchronous issue, in the proposed asyn-MARL framework, we first design a global state, which exploits a low-dimensional vector to implicitly represent the joint observations and actions of multi-agents. Then we develop a novel trajectory collection mechanism to decrease the redundancy in training trajectories. Additionally, we design a novel actor network to facilitate the cooperation among vehicles towards the same or close destinations and a reachability graph aimed at preventing infinite loops in routing paths. On both synthetic and real road networks, our evaluation result demonstrates that our approach outperforms state-of-the-art planning approaches. Show Chinese abstract

Abstract: 本文研究了具有多个源-目标对（MSD）的最短路径问题（SPP），即MSD-SPP，旨在最小化所有最短路径的平均旅行时间。 道路网络中的固有交通容量限制导致车辆之间的竞争。 由于MSD-SPP中异步决策设置的存在，多智能体强化学习（MARL）模型无法提供有效的路径规划协作，其中车辆（即代理）不能在同一时间步内同时完成路由操作。 为了解决效率问题，我们提出将整个路网划分为多个子图，并随后执行区域间和区域内路径规划的两阶段过程。 为了解决异步问题，在所提出的asyn-MARL框架中，我们首先设计了一个全局状态，该状态利用一个低维向量隐式表示多智能体的联合观测和动作。 然后，我们开发了一种新颖的轨迹收集机制以减少训练轨迹中的冗余。 此外，我们设计了一种新颖的演员网络，以促进朝向相同或接近目的地的车辆之间的合作，以及一种可达性图，旨在防止路由路径中的无限循环。 在合成和真实路网上，我们的评估结果显示，我们的方法优于最先进的规划方法。