论文标题
大规模仓库中的终身多试路径查找
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
论文作者
论文摘要
多代理路径查找（MAPF）是将一组代理团队转移到其目标位置而不会发生冲突的问题。在本文中，我们研究了MAPF的终生变体，在该变体中，代理商不断与新的目标位置（例如大型自动仓库中）互动。我们通过将问题分解为一系列窗口的MAPF实例，提出了一个新的框架滚动滚动碰撞分辨率（RHCR），以解决终身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.
