AAAI

Association for the Advancement of Artificial Intelligence

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

Experimental Evaluation of Classical Multi Agent Path Finding Algorithms

Authors

Omri Kaduri,Eli Boyarski,Roni Stern

Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel,Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel,Ben Gurion University of the Negev, SISE Dept., Be'er Sheva, Israel Palo Alto Research Center (PARC), ISL, Palo Alto, USA


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

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

Track:

Short Papers

Downloads:

Download PDF

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.

DOI:

10.1609/socs.v12i1.18560


SOCS

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