Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF where agents are constantly engaged with new goal locations, such as in large-scale warehouses. We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a finite time horizon and ignores collisions beyond it. Our framework is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. Theoretically, we analyze the advantages and disadvantages of our framework. Empirically, we evaluate our framework with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents, significantly outperforming existing methods.

本文研究了在大型自动化仓库等场景下，智能体不断需要寻找新的目标点的长期多智能体路径规划问题。我们提出了一种新的解决方案，Rolling-Horizon Collision Resolution框架，通过将问题分解成一系列窗口MAPF实例来解决，其中窗口MAPF解决器仅在有限时间范围内解决智能体路径的冲突，并忽略其外的冲突。我们通过模拟仓库实例，经验性地评估了RHCR，并与各种MAPF解算器进行了比较，在多达1000个智能体的情况下（=地图上38.9％的空单元格），RHCR可以产生高质量的解决方案，显着优于现有工作。

大规模仓库中的终身多智能体路径规划