Experimental Evaluation of Classical Multi Agent Path Finding Algorithms

Authors

  • Omri Kaduri Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel
  • Eli Boyarski Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel
  • Roni Stern Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel Palo Alto Research Center (PARC), ISL, Palo Alto, USA

Keywords:

Portfolios Of Search Algorithms, Analysis Of Search Algorithms

Abstract

Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.

Downloads

Published

2021-07-21