Further Improved Heuristics For Conflict-Based Search

Authors

  • Eli Boyarski Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Pierre Le Bodic Monash University
  • Daniel D. Harabor Monash University
  • Peter J. Stuckey Monash University
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/socs.v12i1.18587

Keywords:

Bounding And Pruning Techniques

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.
SoCS-2021 Proceedings Cover

Downloads

Published

2021-07-21

How to Cite

Boyarski, E., Felner, A., Le Bodic, P., Harabor, D. D., Stuckey, P. J., & Koenig, S. (2021). Further Improved Heuristics For Conflict-Based Search. Proceedings of the International Symposium on Combinatorial Search, 12(1), 213–215. https://doi.org/10.1609/socs.v12i1.18587

Issue

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

Section

Student Papers