Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding
Conference Paper, Proceedings of 28th International Conference on Automated Planning and Scheduling (ICAPS '18), pp. 83 - 87, June, 2018
Abstract
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However,existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.
BibTeX
@conference{Felner-2018-131438,author = {Ariel Felner and Jiaoyang Li and Eli Boyarski and Hang Ma and Liron Cohen and T. K. Satish Kumar and Sven Koenig},
title = {Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding},
booktitle = {Proceedings of 28th International Conference on Automated Planning and Scheduling (ICAPS '18)},
year = {2018},
month = {June},
pages = {83 - 87},
}
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.