f-Aware Conflict Prioritization & 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

Keywords:

Applications

Abstract

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). The main step of CBS is to expand nodes by resolving conflicts (where two agents collide). Choosing the ‘right’ conflict to resolve can greatly speed up the search. CBS first resolves conflicts where the costs (g-values) of the resulting child nodes are larger than the cost of the node to be split. However, the recent addition of high-level heuristics to CBS and expanding nodes according to f=g+h reduces the relevance of this conflict prioritization method. Therefore, we introduce an expanded categorization of conflicts, which first resolves conflicts where the f-values of the child nodes are larger than the f-value of the node to be split, and present a method for identifying such conflicts. We also enhance all known heuristics for CBS by using information about the cost of resolving certain conflicts, and with only a small computational overhead. Finally, we experimentally demonstrate that both the expanded categorization of conflicts and the improved heuristics contribute to making CBS even more efficient.

Downloads

Published

2021-05-18

How to Cite

Boyarski, E., Felner, A., Le Bodic, P., Harabor, D. D., Stuckey, P. J., & Koenig, S. (2021). f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12241-12248. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17453

Issue

Section

AAAI Technical Track on Search and Optimization