Abstract
J. Ren, E. Ewing, S. Kumar, S. Koenig and N. Ayanian. Map Connectivity and Empirical Hardness of Grid-Based Multi-Agent Pathfinding Problem. In International Conference on Automated Planning and Scheduling (ICAPS), pages (in print), 2024.Abstract: We present an empirical study of the relationship between map connectivity and the empirical hardness of the multi-agent pathfinding (MAPF) problem. By analyzing the second smallest eigenvalue (commonly known as λ2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller λ2 tend to create more challenging instances when agents are generated uniformly randomly. Additionally, we introduce a map generator based on Quality Diversity (QD) that is capable of producing maps with specified λ2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with λ2 and the empirical hardness of MAPF, this study serves as a valuable initial investigation for gaining a deeper understanding of what makes a MAPF instance hard to solve.
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.