Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
复制标题
DOI：
10.1609/aaai.v35i13.17344
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Jiaoyang Li;Andrew Tinka;Scott Kiesel;Joseph W. Durham;T. K. S. Kumar;Sven Koenig
中科院分区：
文献类型：
--
作者：
Jiaoyang Li;Andrew Tinka;Scott Kiesel;Joseph W. Durham;T. K. S. Kumar;Sven Koenig
多智能体路径查找（MAPF）是移动一组代理到他们的目标位置没有冲突的问题。在本文中，我们研究了MAPF的终身变体，其中代理人不断与新的目标位置，如在大型自动化仓库。我们提出了一个新的框架滚动地平线冲突解决（RHCR）解决终身MAPF分解成一系列的窗口MAPF实例，其中一个窗口MAPF求解器解决的路径之间的冲突，只有在一个有限的时间范围内的代理，并忽略碰撞超出它，RHCR是特别适合于生成柔韧的计划，适应不断到达新的目标位置。我们用各种MAPF求解器对RHCR进行了经验评估，并表明它可以为模拟仓库实例的多达1,000个代理（=地图上38.9%的空单元格）生成高质量的解决方案，显著优于现有的工作。
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 automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) 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 bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents (= 38.9% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.