Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915668055556096 |
|---|---|
| author | Ren, Jingyao Ewing, Eric Kumar, T. K. Satish Koenig, Sven Ayanian, Nora |
| author_facet | Ren, Jingyao Ewing, Eric Kumar, T. K. Satish Koenig, Sven Ayanian, Nora |
| contents | Multi-agent pathfinding (MAPF) is the problem of finding collision-free paths for a team of agents on a map. Although MAPF is NP-hard, 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 best-performing 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10078 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities Ren, Jingyao Ewing, Eric Kumar, T. K. Satish Koenig, Sven Ayanian, Nora Multiagent Systems Multi-agent pathfinding (MAPF) is the problem of finding collision-free paths for a team of agents on a map. Although MAPF is NP-hard, 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 best-performing 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. |
| title | Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2512.10078 |