Publication

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 λ₂) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller λ₂ 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 λ₂ ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with λ₂ 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.

Download the paper in pdf.