Iterative-Deepening Conflict-Based Search
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.
Cite
Text
Boyarski et al. "Iterative-Deepening Conflict-Based Search." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/565Markdown
[Boyarski et al. "Iterative-Deepening Conflict-Based Search." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/boyarski2020ijcai-iterative/) doi:10.24963/IJCAI.2020/565BibTeX
@inproceedings{boyarski2020ijcai-iterative,
title = {{Iterative-Deepening Conflict-Based Search}},
author = {Boyarski, Eli and Felner, Ariel and Harabor, Daniel and Stuckey, Peter J. and Cohen, Liron and Li, Jiaoyang and Koenig, Sven},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {4084-4090},
doi = {10.24963/IJCAI.2020/565},
url = {https://mlanthology.org/ijcai/2020/boyarski2020ijcai-iterative/}
}