Iterative-Deepening Conflict-Based Search

Iterative-Deepening Conflict-Based Search

Eli Boyarski, Ariel Felner, Daniel Harabor, Peter J. Stuckey, Liron Cohen, Jiaoyang Li, Sven Koenig

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4084-4090. https://doi.org/10.24963/ijcai.2020/565

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF). CBS variants typically compute MAPF solutions using some form of A* search. However, they often do so under strict time limits so as to avoid exhausting the available memory. In this paper, we present IDCBS, an iterative-deepening variant of CBS which can be executed without exhausting the memory and without strict time limits. IDCBS can be substantially faster than CBS due to incremental methods that it uses when processing CBS nodes.
Keywords:
Planning and Scheduling: Planning and Scheduling
Agent-based and Multi-agent Systems: Multi-agent Planning
Heuristic Search and Game Playing: Heuristic Search