Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
- Roni Stern
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Sven Koenig
- Hang Ma
- Thayne T. Walker
- Jiaoyang Li
- Dor Atzmon
- Liron Cohen
- T.K. Satish Kumar
- Roman Barták
- Eli Boyarski
The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e.g., whether agents can traverse the same road at the same time, and have different objective functions, e.g., minimize makespan or sum of agents' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult for establishing appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and facilitate future research and practitioners by providing a unifying terminology for describing the common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.
Citation
R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar, R. Barták, E. Boyarski. "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks". Symposium on Combinatorial Search, (ed: Pavel Surynek, William Yeoh), pp 151-159, July 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Stern+al:SoCS19,
author = {Roni Stern and Nathan R. Sturtevant and Ariel Felner and Sven
Koenig and Hang Ma and Thayne T. Walker and Jiaoyang Li and Dor Atzmon and
Liron Cohen and T.K. Satish Kumar and Roman Barták and Eli Boyarski},
title = {Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks},
Editor = {Pavel Surynek, William Yeoh},
Pages = {151-159},
booktitle = {Symposium on Combinatorial Search},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
