EUVIMEDEUVIMED entdecken
Crossref

Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees

Tiannan Zhang, Rishi Veerapaneni, Shao-Hung Chan, Jiaoyang Li, Maxim Likhachev

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (35) · 29911-29920

DOI: 10.1609/aaai.v40i35.40238 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Tiannan Zhang und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a team of agents. Although several MAPF methods that solve full-horizon MAPF have completeness guarantees, very few MAPF methods that plan partial paths have completeness guarantees. Recent work introduced the Windowed Complete MAPF (WinC-MAPF) framework, which shows how windowed optimal MAPF solvers (e.g., SS-CBS) can use heuristic updates and disjoint agent groups to maintain completeness even when planning partial paths. A core limitation of WinC-MAPF is that it requires optimal MAPF solvers. Our main contribution is to extend WinC-MAPF by showing how we can use a bounded suboptimal solver while maintaining completeness. In particular, we design Dynamic Agent Grouping ECBS (DAG-ECBS) which dynamically creates and plans agent groups while maintaining that each agent group solution is bounded suboptimal. We prove how DAG-ECBS can maintain completeness in the WinC-MAPF framework and can improve scalability compared to windowed ECBS which does not have completeness guarantees. More broadly, our work serves as a blueprint for designing more MAPF methods that can use the WinC-MAPF framework

Zitieren

APA

Zhang, T., Veerapaneni, R., Chan, S., Li, J., & Likhachev, M. (2026). Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees. Proceedings of the AAAI Conference on Artificial Intelligence, 40(35), 29911-29920. https://doi.org/10.1609/aaai.v40i35.40238

Vancouver

Zhang T, Veerapaneni R, Chan S, Li J, Likhachev M. Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(35):29911-29920. doi:10.1609/aaai.v40i35.40238

BibTeX
@article{Zhang2026,
  author = {Zhang, Tiannan and Veerapaneni, Rishi and Chan, Shao-Hung and Li, Jiaoyang and Likhachev, Maxim},
  title = {Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {35},
  pages = {29911--29920},
  doi = {10.1609/aaai.v40i35.40238}
}
Kostenlos starten →