# Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 18 Jan 2025.

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

- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Deep Multi-agent Reinforcement Learning for Highway On-Ramp Merging in Mixed Traffic](https://mlsanity.com/paper/2105.05701/) (2021)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Decentralized Cooperative Planning for Automated Vehicles with Hierarchical Monte Carlo Tree Search](https://mlsanity.com/paper/1807.09530/) (2018)
- [Multi-Robot Path Deconfliction through Prioritization by Path Prospects](https://mlsanity.com/paper/1908.02361/) (2019)
- [Cyber-Physical Mobility Lab: An Open-Source Platform for Networked and Autonomous Vehicles](https://mlsanity.com/paper/2004.10063/) (2020)
- [Expected 1.x-Makespan-Optimal MAPF on Grids in Low-Poly Time](https://mlsanity.com/paper/2408.05385/) (2024)
- [A Priority-Aware Replanning and Resequencing Framework for Coordination of Connected and Automated Vehicles](https://mlsanity.com/paper/2109.05573/) (2021)
- [Limiting Computation Levels in Prioritized Trajectory Planning with Safety Guarantees](https://mlsanity.com/paper/2409.05029/) (2024)

## Abstract (arXiv)

Multi-agent path finding (MAPF) in large networks is computationally challenging. An approach for MAPF is prioritized planning (PP), in which agents plan sequentially according to their priority. Albeit a computationally efficient approach for MAPF, the solution quality strongly depends on the prioritization. Most prioritizations rely either on heuristics, which do not generalize well, or iterate to find adequate priorities, which costs computational effort. In this work, we show how agents can compute with multiple prioritizations simultaneously. Our approach is general as it does not rely on domain-specific knowledge. The context of this work is multi-agent motion planning (MAMP) with a receding horizon subject to computation time constraints. MAMP considers the system dynamics in more detail compared to MAPF. In numerical experiments on MAMP, we demonstrate that our approach achieves near-optimal prioritization and outperforms state-of-the-art methods with only a minor increase in computation time. We show real-time capability in an experiment on a road network with ten vehicles in our Cyber-Physical Mobility Lab.