Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search
Conference Paper, Proceedings of 28th International Joint Conference on Artificial Intelligence (IJCAI '19), pp. 442 - 449, August, 2019
Abstract
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Path Finding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependencies between agents. Empirically, CBS with either new heuristic significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50.
BibTeX
@conference{Li-2019-131426,author = {Jiaoyang Li and Ariel Felner and Eli Boyarski and Hang Ma and Sven Koenig},
title = {Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search},
booktitle = {Proceedings of 28th International Joint Conference on Artificial Intelligence (IJCAI '19)},
year = {2019},
month = {August},
pages = {442 - 449},
}
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.