Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
复制标题
DOI：
10.1609/socs.v10i1.18510
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Roni Stern;Nathan R Sturtevant;Ariel Felner;Sven Koenig;Hang Ma;Thayne T. Walker;Jiaoyang Li;Dor Atzmon;L. Cohen;T. K. S. Kumar;Eli Boyarski;R. Barták
中科院分区：
文献类型：
--
作者：
Roni Stern;Nathan R Sturtevant;Ariel Felner;Sven Koenig;Hang Ma;Thayne T. Walker;Jiaoyang Li;Dor Atzmon;L. Cohen;T. K. S. Kumar;Eli Boyarski;R. Barták
多智能体寻路问题（MAPF）是为多个智能体规划路径的基本问题，其中的关键约束是智能体能够并发地遵循这些路径而不相互冲突。MAPF的应用包括自动化仓库、自动驾驶汽车和机器人。近几年来，MAPF的研究得到了蓬勃发展。不同的MAPF研究论文假设不同的假设，例如，智能体是否可以在同一时间穿越同一条道路，并具有不同的目标函数，例如，最小化完工时间或代理人的行动成本之和。这些假设和目标有时是隐含的假设或非正式的描述。这使得难以在研究论文中建立适当的比较基线，也使得从业人员难以找到与其具体应用相关的论文。本文旨在填补这一空白，并通过提供一个统一的术语来描述常见的MAPF假设和目标，以促进未来的研究和实践。此外，我们还提供了两个MAPF基准的指针。特别是，我们引入了一个新的基于网格的基准MAPF，并通过实验证明，它构成了当代MAPF算法的挑战。
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.