# Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds](https://mlsanity.com/paper/2104.08759/) (2021)
- [Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch](https://mlsanity.com/paper/1801.01689/) (2018)
- [Refined Hardness of Distance-Optimal Multi-Agent Path Finding](https://mlsanity.com/paper/2203.07416/) (2022)
- [Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity](https://mlsanity.com/paper/2303.00745/) (2023)
- [On Two-Handed Planar Assembly Partitioning with Connectivity Constraints](https://mlsanity.com/paper/2009.12369/) (2020)

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

- [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)

Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem arising in multi-agent systems with a wide range of applications. The problem's intractability has led to extensive research on improving the scalability of solvers for it. Since optimal solvers can struggle to scale, a major challenge that arises is understanding what makes MAPF hard. We tackle this challenge through a fine-grained complexity analysis of time-optimal MAPF on 2D grids, thereby closing two gaps and identifying a new tractability frontier. First, we show that 2-colored MAPF, i.e., where the agents are divided into two teams, each with its own set of targets, remains NP-hard. Second, for the flowtime objective (also called sum-of-costs), we show that it remains NP-hard to find a solution in which agents have an individually optimal cost, which we call an individually optimal solution. The previously tightest results for these MAPF variants are for (non-grid) planar graphs. We use a single hardness construction that replaces, strengthens, and unifies previous proofs. We believe that it is also simpler than previous proofs for the planar case as it employs minimal gadgets that enable its full visualization in one figure. Finally, for the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in. Namely, we complement our hardness result, which holds for three directions, with an efficient algorithm for finding an individually optimal solution if only two directions are allowed. This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem.