Iterative-Deepening Conflict-Based Search
Conference Paper, Proceedings of 29th International Joint Conference on Artificial Intelligence (IJCAI '20), pp. 4084 - 4090, January, 2021
Abstract
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.
BibTeX
@conference{Boyarski-2021-131414,author = {Eli Boyarski and Ariel Felner and Daniel Harabor and Peter J. Stuckey and Liron Cohen and Jiaoyang Li and Sven Koenig},
title = {Iterative-Deepening Conflict-Based Search},
booktitle = {Proceedings of 29th International Joint Conference on Artificial Intelligence (IJCAI '20)},
year = {2021},
month = {January},
pages = {4084 - 4090},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.