AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 28 > Book One

Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding

Authors

Ariel Felner,Jiaoyang Li,Eli Boyarski,Hang Ma,Liron Cohen,T. K. Satish Kumar,Sven Koenig

Ben-Gurion University,University of Southern California,Ben-Gurion University,University of Southern California,University of Southern California,University of Southern California,University of Southern California


Proceedings:

Book One

Volume

Issue:

Proceedings of the International Conference on Automated Planning and Scheduling, 28

Track:

Main Track

Downloads:

Download PDF

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.

DOI:

10.1609/icaps.v28i1.13883


ICAPS

Proceedings of the International Conference on Automated Planning and Scheduling, 28