Inapproximability of Optimal Multi-Agent Pathfinding Problems
Abstract
Multi-agent pathfinding MAPF is a problem where multiple autonomous agents must find paths to their respective destinations without colliding. Decisional MAPF on undirected graphs can be solved in polynomial time; Several optimization MAPF variants however are NP-complete. The directed graph variant (diMAPF) is more complex, with its decisional version already being NP-complete. This paper examines the computational approximability of optimal MAPF problems (i.e., minimizing makespan for agent travel distance and maximizing the total number of agents reaching their goals), providing a first set of several inapproximability results for these problems. The results reveal an inherent limitation in approximating optimal solutions for MAPFs, provide a deeper understanding regarding their computational intractability, thus offer foundational references for future research.
BibTeX
@article{Tan_Grastien_2025, title={Inapproximability of Optimal Multi-Agent Pathfinding Problems}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34873}, DOI={10.1609/aaai.v39i25.34873}, abstractNote={Multi-agent pathfinding MAPF is a problem where multiple autonomous agents must find paths to their respective destinations without colliding. Decisional MAPF on undirected graphs can be solved in polynomial time; Several optimization MAPF variants however are NP-complete. The directed graph variant (diMAPF) is more complex, with its decisional version already being NP-complete. This paper examines the computational approximability of optimal MAPF problems (i.e., minimizing makespan for agent travel distance and maximizing the total number of agents reaching their goals), providing a first set of several inapproximability results for these problems. The results reveal an inherent limitation in approximating optimal solutions for MAPFs, provide a deeper understanding regarding their computational intractability, thus offer foundational references for future research.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Tan, Xing and Grastien, Alban}, year={2025}, month={Apr.}, pages={26707-26715} }