AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Further Improved Heuristics For Conflict-Based Search

Authors

Eli Boyarski,Ariel Felner,Pierre Le Bodic,Daniel D. Harabor,Peter J. Stuckey,Sven Koenig

Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Monash University,Monash University,Monash University,University of Southern California


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Student Papers

Downloads:

Download PDF

Abstract:

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). At its high level, CBS expands nodes by resolving conflicts. In recent years, admissible heuristics were added to the high level of CBS. We enhance all known heuristic functions for CBS by using information about the cost of resolving certain conflicts, with only a small computational overhead. We experimentally demonstrate that the improved heuristics contribute to making CBS even more efficient.

DOI:

10.1609/socs.v12i1.18587


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search