Abstract
J. Ren, E. Ewing, S. Kumar, S. Koenig and N. Ayanian. Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities [Blue Sky Ideas Track]. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages (in print), 2025.Abstract: Multi-agent pathfinding (MAPF) is the problem of finding collisionfree paths for a team of agents on a map. Although MAPF is NPhard, the hardness of solving individual instances varies significantly, revealing a gap between theoretical complexity and actual hardness. This paper outlines three key research challenges in MAPF empirical hardness to understand such phenomena. The first challenge, known as algorithm selection, is determining the bestperforming algorithms for a given instance. The second challenge is understanding the key instance features that affect MAPF empirical hardness, such as structural properties like phase transition and backbone/backdoor. The third challenge is how to leverage our knowledge of MAPF empirical hardness to effectively generate hard MAPF instances or diverse benchmark datasets. This work establishes a foundation for future empirical hardness research and encourages deeper investigation into these promising and underexplored areas.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.