# Refined Hardness of Distance-Optimal Multi-Agent Path Finding

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2022.

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

- [Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding](https://mlsanity.com/paper/2602.06733/) (2026)
- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [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)
- [Scalable Mechanism Design for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.17044/) (2024)
- [Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity](https://mlsanity.com/paper/2608.07734/) (2026)

## Abstract (arXiv)

We study the computational complexity of multi-agent path finding (MAPF). Given a graph G and a set of agents, each having a start and target vertex, the goal is to find collision-free paths minimizing the total distance traveled. To better understand the source of difficulty of the problem, we aim to study the simplest and least constrained graph class for which it remains hard. To this end, we restrict G to be a 2D grid, which is a ubiquitous abstraction, as it conveniently allows for modeling well-structured environments (e.g., warehouses). Previous hardness results considered highly constrained 2D grids having only one vertex unoccupied by an agent, while the most restricted hardness result that allowed multiple empty vertices was for (non-grid) planar graphs. We therefore refine previous results by simultaneously considering both 2D grids and multiple empty vertices. We show that even in this case distance-optimal MAPF remains NP-hard, which settles an open problem posed by Banfi et al. (2017). We present a reduction directly from 3-SAT using simple gadgets, making our proof arguably more informative than previous work in terms of potential progress towards positive results. Furthermore, our reduction is the first linear one for the case where G is planar, appearing nearly four decades after the first related result. This allows us to go a step further and exploit the Exponential Time Hypothesis (ETH) to obtain an exponential lower bound for the running time of the problem. Finally, as a stepping stone towards our main results, we prove the NP-hardness of the monotone case, in which agents move one by one with no intermediate stops.