# Graph-Based Multi-Robot Path Finding and Planning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 121 references that are in the map.
- First posted on arXiv 22 Jun 2022.

## Builds on (most cited first, 30 of 35)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [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)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning](https://mlsanity.com/paper/2011.13219/) (2020)
- [Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning](https://mlsanity.com/paper/2005.05420/) (2020)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/1812.06355/) (2018)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees](https://mlsanity.com/paper/1401.3905/) (2014)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers](https://mlsanity.com/paper/1912.00253/) (2019)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)
- [Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios](https://mlsanity.com/paper/1702.05515/) (2017)
- [Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World](https://mlsanity.com/paper/2103.16511/) (2021)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [Multi-Agent Path Finding with Deadlines](https://mlsanity.com/paper/1806.04216/) (2018)
- [Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search](https://mlsanity.com/paper/2012.06005/) (2020)
- [MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings](https://mlsanity.com/paper/2102.12461/) (2021)
- [AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)](https://mlsanity.com/paper/1710.03774/) (2017)
- [Symmetry Breaking for k-Robust Multi-Agent Path Finding](https://mlsanity.com/paper/2102.08689/) (2021)

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

- [Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.05893/) (2023)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)
- [Intelligent logistics management robot path planning algorithm integrating transformer and GCN network](https://mlsanity.com/paper/2501.02749/) (2025)
- [SkyRover: A Modular Simulator for Cross-Domain Pathfinding](https://mlsanity.com/paper/2502.08969/) (2025)
- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)
- [SPARC: Spatial-Aware Path Planning via Attentive Agent Communication](https://mlsanity.com/paper/2603.02845/) (2026)

## Abstract (arXiv)

Purpose of Review Planning collision-free paths for multiple robots is important for real-world multi-robot systems and has been studied as an optimization problem on graphs, called Multi-Agent Path Finding (MAPF). This review surveys different categories of classic and state-of-the-art MAPF algorithms and different research attempts to tackle the challenges of generalizing MAPF techniques to real-world scenarios. Recent Findings Solving MAPF problems optimally is computationally challenging. Recent advances have resulted in MAPF algorithms that can compute collision-free paths for hundreds of robots and thousands of navigation tasks in seconds of runtime. Many variants of MAPF have been formalized to adapt MAPF techniques to different real-world requirements, such as considerations of robot kinematics, online optimization for real-time systems, and the integration of task assignment and path planning. Summary Algorithmic techniques for MAPF problems have addressed important aspects of several multi-robot applications, including automated warehouse fulfillment and sortation, automated train scheduling, and navigation of non-holonomic robots and quadcopters. This showcases their potential for real-world applications of large-scale multi-robot systems.