# Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2014.

## Built on by (most cited first, 19 of 19)

- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [POGEMA: Partially Observable Grid Environment for Multiple Agents](https://mlsanity.com/paper/2206.10944/) (2022)
- [Environment Optimization for Multi-Agent Navigation](https://mlsanity.com/paper/2209.11279/) (2022)
- [Constrained Environment Optimization for Prioritized Multi-Agent Navigation](https://mlsanity.com/paper/2305.11260/) (2023)
- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS](https://mlsanity.com/paper/2205.11624/) (2022)
- [Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality](https://mlsanity.com/paper/2301.08451/) (2023)
- [MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2404.19518/) (2024)
- [Safe and Interpretable Multimodal Path Planning for Multi-Agent Cooperation](https://mlsanity.com/paper/2602.19304/) (2026)
- [Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints](https://mlsanity.com/paper/2108.05145/) (2021)
- [Q-Mixing Network for Multi-Agent Pathfinding in Partially Observable Grid Environments](https://mlsanity.com/paper/2108.06148/) (2021)
- [Scalable Mechanism Design for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.17044/) (2024)
- [Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots](https://mlsanity.com/paper/2402.09246/) (2024)
- [Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability](https://mlsanity.com/paper/2410.17160/) (2024)
- [Fault-Tolerant Offline Multi-Agent Path Planning](https://mlsanity.com/paper/2211.13908/) (2022)
- [Factorization of Multi-Agent Sampling-Based Motion Planning](https://mlsanity.com/paper/2304.00342/) (2023)
- [Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning](https://mlsanity.com/paper/2501.10781/) (2025)
- [PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints](https://mlsanity.com/paper/2505.08025/) (2025)
- [AVOID-JACK: Avoidance of Jackknifing for Swarms of Long Heavy Articulated Vehicles](https://mlsanity.com/paper/2511.08016/) (2025)

## Abstract (arXiv)

An important capability of autonomous multi-robot systems is to prevent collision among the individual robots. One approach to this problem is to plan conflict-free trajectories and let each of the robots follow its pre-planned trajectory. A widely used practical method for multi-robot trajectory planning is prioritized planning, which has been shown to be effective in practice, but is in general incomplete. Formal analysis of instances that are provably solvable by prioritized planning is still missing. Moreover, prioritized planning is a centralized algorithm, which may be in many situations undesirable. In this paper we a) propose a revised version of prioritized planning and characterize the class of instances that are provably solvable by the algorithm and b) propose an asynchronous decentralized variant of prioritized planning, which maintains the desirable properties of the centralized version and in the same time exploits the distributed computational power of the individual robots, which in most situations allows to find the joint trajectories faster. The experimental evaluation performed on real-world indoor maps shows that a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized algorithm provides solution faster than the previously proposed synchronized decentralized algorithm.