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.
Cite
Text
Tan and Grastien. "Inapproximability of Optimal Multi-Agent Pathfinding Problems." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I25.34873Markdown
[Tan and Grastien. "Inapproximability of Optimal Multi-Agent Pathfinding Problems." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/tan2025aaai-inapproximability/) doi:10.1609/AAAI.V39I25.34873BibTeX
@inproceedings{tan2025aaai-inapproximability,
title = {{Inapproximability of Optimal Multi-Agent Pathfinding Problems}},
author = {Tan, Xing and Grastien, Alban},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
pages = {26707-26715},
doi = {10.1609/AAAI.V39I25.34873},
url = {https://mlanthology.org/aaai/2025/tan2025aaai-inapproximability/}
}