Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem
Proceedings of the International Conference on Automated Planning and Scheduling · 30.05.2024 · 34 · 484-488
DOI: 10.1609/icaps.v34i1.31508 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 30.05.2024. Verfasst von Jingyao Ren und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
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 lambda2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller lambda2 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 lambda2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with lambda2 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.
Zitieren
APA
Ren, J., Ewing, E., Kumar, T. K. S., Koenig, S., & Ayanian, N. (2024). Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem. Proceedings of the International Conference on Automated Planning and Scheduling, 34, 484-488. https://doi.org/10.1609/icaps.v34i1.31508
Vancouver
Ren J, Ewing E, Kumar TKS, Koenig S, Ayanian N. Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem. Proceedings of the International Conference on Automated Planning and Scheduling. 2024;34:484-488. doi:10.1609/icaps.v34i1.31508
BibTeX
@article{Ren2024,
author = {Ren, Jingyao and Ewing, Eric and Kumar, T. K. Satish and Koenig, Sven and Ayanian, Nora},
title = {Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2024},
volume = {34},
pages = {484--488},
doi = {10.1609/icaps.v34i1.31508}
}
EUVIMED