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

Authors

  • Ariel Felner Ben-Gurion University
  • Jiaoyang Li University of Southern California
  • Eli Boyarski Ben-Gurion University
  • Hang Ma University of Southern California
  • Liron Cohen University of Southern California
  • T. K. Satish Kumar University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/icaps.v28i1.13883

Keywords:

Conflict Based Search, Heuristics, Multi-agent path finding

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.

Downloads

Published

2018-06-15

How to Cite

Felner, A., Li, J., Boyarski, E., Ma, H., Cohen, L., Kumar, T. K. S., & Koenig, S. (2018). Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 83-87. https://doi.org/10.1609/icaps.v28i1.13883

Issue

Vol. 28 (2018): Twenty-Eighth International Conference on Automated Planning and Scheduling

Section

Main Track