# Expected 1.x-Makespan-Optimal MAPF on Grids in Low-Poly Time

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2024.

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

- [Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning](https://mlsanity.com/paper/2501.10781/) (2025)
- [Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time](https://mlsanity.com/paper/2512.22171/) (2025)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is NP-hard to solve optimally, even on graphs, suggesting no polynomial-time algorithms can compute exact optimal solutions for them. This raises a natural question: How optimal can polynomial-time algorithms reach? Whereas algorithms for computing constant-factor optimal solutions have been developed, the constant factor is generally very large, limiting their application potential. In this work, among other breakthroughs, we propose the first low-polynomial-time MAPF algorithms delivering 1-1.5 (resp., 1-1.67) asymptotic makespan optimality guarantees for 2D (resp., 3D) grids for random instances at a very high 1/3 agent density, with high probability. Moreover, when regularly distributed obstacles are introduced, our methods experience no performance degradation. These methods generalize to support 100% agent density. Regardless of the dimensionality and density, our high-quality methods are enabled by a unique hierarchical integration of two key building blocks. At the higher level, we apply the labeled Grid Rearrangement Algorithm (RTA), capable of performing efficient reconfiguration on grids through row/column shuffles. At the lower level, we devise novel methods that efficiently simulate row/column shuffles returned by RTA. Our implementations of RTA-based algorithms are highly effective in extensive numerical evaluations, demonstrating excellent scalability compared to other SOTA methods. For example, in 3D settings, rta-based algorithms readily scale to grids with over 370,000 vertices and over 120,000 agents and consistently achieve conservative makespan optimality approaching 1.5, as predicted by our theoretical analysis.