# Intractability of Optimal Multi-Robot Path Planning on Planar Graphs

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2015.

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

- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds](https://mlsanity.com/paper/2104.08759/) (2021)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [Distributing Collaborative Multi-Robot Planning with Gaussian Belief Propagation](https://mlsanity.com/paper/2203.11618/) (2022)
- [Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology](https://mlsanity.com/paper/2312.09646/) (2023)
- [Leveraging Experience in Lifelong Multi-Agent Pathfinding](https://mlsanity.com/paper/2202.04382/) (2022)
- [A Competitive Analysis of Online Multi-Agent Path Finding](https://mlsanity.com/paper/2106.11454/) (2021)
- [DiRecT: Safe Diffusion-Based Planning via Receding-Horizon Denoising](https://mlsanity.com/paper/2606.15359/) (2026)
- [The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True](https://mlsanity.com/paper/2210.04590/) (2022)
- [Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids](https://mlsanity.com/paper/2305.16303/) (2023)
- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)
- [Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning](https://mlsanity.com/paper/2501.10781/) (2025)
- [Multi-Agent Path Finding For Large Agents Is Intractable](https://mlsanity.com/paper/2505.10387/) (2025)
- [MAPF-World: Action World Model for Multi-Agent Path Finding](https://mlsanity.com/paper/2508.12087/) (2025)

## Abstract (arXiv)

We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.