论文标题
迈向大型代理的完整多代理探索算法
Towards A Complete Multi-Agent Pathfinding Algorithm For Large Agents
论文作者
论文摘要
多代理探路（MAPF）是一个具有挑战性的问题，即使采用了简化的假设，例如平面图（通常是网格），离散的时间，移动的统一持续时间和等待动作等。另一方面，在这种限制性假设下（也称为经典MAPF）MAPF等同于所谓的非优美的多义时时间算法的所谓的粘合运动问题。最近，出现了一系列作品，研究了MAPF超出基本环境，尤其是被认为是任意大小和形状的试剂。尽管如此，据我们所知，对于此类MAPF变体而言，没有完整的算法。在这项工作中，我们试图通过考虑大型代理的MAPF来缩小差异，并建议如何将这个问题简化为（一般）图上的卵石运动。减少的症结是将代理从边缘移开的过程，这是执行当前代理的移动动作所需的。我们考虑了如何实现此过程的不同变体，并提出了包含此过程的卵石运动算法的变体。不幸的是，该算法仍然不完整，但是从经验上，我们证明，与最新的非平面图（路线图）相比，与最先进的MAPF求解器相比，大型代理可以解决更多的MAPF实例（在严格的时间限制之下）。
Multi-agent pathfinding (MAPF) is a challenging problem which is hard to solve optimally even when simplifying assumptions are adopted, e.g. planar graphs (typically -- grids), discretized time, uniform duration of move and wait actions etc. On the other hand, MAPF under such restrictive assumptions (also known as the Classical MAPF) is equivalent to the so-called pebble motion problem for which non-optimal polynomial time algorithms do exist. Recently, a body of works emerged that investigated MAPF beyond the basic setting and, in particular, considered agents of arbitrary size and shape. Still, to the best of our knowledge no complete algorithms for such MAPF variant exists. In this work we attempt to narrow this gap by considering MAPF for large agents and suggesting how this problem can be reduced to pebble motion on (general) graphs. The crux of this reduction is the procedure that moves away the agents away from the edge which is needed to perform a move action of the current agent. We consider different variants of how this procedure can be implemented and present a variant of the pebble motion algorithm which incorporates this procedure. Unfortunately, the algorithm is still incomplete, but empirically we show that it is able to solve much more MAPF instances (under the strict time limit) with large agents on arbitrary non-planar graphs (roadmaps) compared to the state-of-the-art MAPF solver -- Continous Conflict-Based Search (CCBS).
