Abstract
Multi-Agent Path Finding (MAPF) is the problem of moving multiple agents from starts to goals without collisions. Lifelong MAPF (LMAPF) extends MAPF by continuously assigning new goals to agents. We present our winning approach to the 2023 League of Robot Runners LMAPF competition, which leads us to several interesting research challenges and future directions. In this paper, we outline three main research challenges. The first challenge is to search for high-quality LMAPF solutions within a limited planning time (e.g., 1s per step) for a large number of agents (e.g., 10,000) or extremely high agent density (e.g., 97.7%). We present future directions such as developing more competitive rule-based and anytime MAPF algorithms and parallelizing state-of-the-art MAPF algorithms. The second challenge is to alleviate congestion and the effect of myopic behaviors in LMAPF algorithms. We present future directions, such as developing moving guidance and traffic rules to reduce congestion, incorporating future prediction and real-time search, and determining the optimal agent number. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications. We present future directions, such as dealing with more realistic kinodynamic models, execution uncertainty, and evolving systems.
Abstract (translated)
多智能体路径寻径（MAPF）是解决在有限规划时间内将多个智能体从起点移动到目标而避免碰撞的问题。终身MAPF（LMAPF）在MAPF的基础上，通过持续为智能体分配新目标来扩展。我们向2023年机器人跑者联赛MAPF比赛呈现我们的获胜方法，该方法导致我们面临多个有趣的研究挑战和未来方向。在本文中，我们概述了三个主要的研究挑战。第一个挑战是在有限规划时间内（例如每步1s）搜索高质量LMAPF解决方案，对大量智能体（例如10,000个）或极高 agent density（例如97.7%）进行规划。我们提出了未来的研究方向，例如开发更具竞争力的基于规则的MAPF算法和并行化最先进的MAPF算法。第二个挑战是减轻LMAPF算法中的拥塞和视野行为的影响。我们提出了未来的研究方向，例如开发移动引导和交通规则以减少拥塞，包括未来的预测和实时搜索，以及确定最优的智能体数量。第三个挑战是桥接文献中使用的LMAPF模型与现实应用之间的差距。我们提出了未来的研究方向，例如处理更真实的动力学模型、执行不确定性以及不断演变的系统。
URL
https://arxiv.org/abs/2404.16162
