# Cooperative Path Planning with Asynchronous Multiagent Reinforcement Learning

arXiv: https://arxiv.org/abs/2409.00754 · HTML: https://mlsanity.com/paper/2409.00754/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 70 references that are in the map.
- First posted on arXiv 1 Sep 2024.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks](https://mlsanity.com/paper/2006.07869/) (2020)
- [Multiagent Cooperation and Competition with Deep Reinforcement Learning](https://mlsanity.com/paper/1511.08779/) (2015)
- [A Closer Look at Invalid Action Masking in Policy Gradient Algorithms](https://mlsanity.com/paper/2006.14171/) (2020)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1906.04737/) (2019)
- [Asynchronous Multi-Agent Reinforcement Learning for Efficient Real-Time Multi-Robot Cooperative Exploration](https://mlsanity.com/paper/2301.03398/) (2023)
- [Survey of Recent Multi-Agent Reinforcement Learning Algorithms Utilizing Centralized Training](https://mlsanity.com/paper/2107.14316/) (2021)
- [Multi-Agent Reinforcement Learning for Markov Routing Games: A New Modeling Paradigm For Dynamic Traffic Assignment](https://mlsanity.com/paper/2011.10915/) (2020)
- [GDDR: GNN-based Data-Driven Routing](https://mlsanity.com/paper/2104.09919/) (2021)
- [Deep Reinforcement Learning Based Dynamic Route Planning for Minimizing Travel Time](https://mlsanity.com/paper/2011.01771/) (2020)
- [Packet Routing with Graph Attention Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2107.13181/) (2021)
- [Reducing Bus Bunching with Asynchronous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2105.00376/) (2021)
- [Road Planning for Slums via Deep Reinforcement Learning](https://mlsanity.com/paper/2305.13060/) (2023)
- [A Multiclass Simulation-Based Dynamic Traffic Assignment Model for Mixed Traffic Flow of Connected and Autonomous Vehicles and Human-Driven Vehicles](https://mlsanity.com/paper/2301.11083/) (2023)
- [Hierarchical Dynamic Routing in Complex Networks via Topologically-decoupled and Cooperative Reinforcement Learning Agents](https://mlsanity.com/paper/2207.00763/) (2022)

## Abstract (arXiv)

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.