Expected $1x$-Makespan-Optimal MAPF on Grids in Low-Poly Time
<|reference_start|>Expected $1x$-Makespan-Optimal MAPF on Grids in Low-Poly Time: 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.<|reference_end|>
@article{guo2024expected,
    title={Expected $1.x$-Makespan-Optimal MAPF on Grids in Low-Poly Time},
    author={Teng Guo and Jingjin Yu},
    journal={Journal of Artificial Intelligence Research, vol. 81, pages
  443-479, 2024},
    year={2024},
    doi={10.1613/jair.1.16299},
    archivePrefix={arXiv},
    eprint={2408.05385},
    primaryClass={cs.RO}
}