EUVIMEDEUVIMED entdecken
Crossref

Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem

Jingyao Ren, Eric Ewing, T. K. Satish Kumar, Sven Koenig, Nora Ayanian

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →