论文标题
基于旁路的细节扩展的多代理路径查找
Multi-Agent Path Finding Based on Subdimensional Expansion with Bypass
论文作者
论文摘要
多代理路径查找（MAPF）是人工智能中的一个活跃领域，它具有许多真实的应用程序，例如仓库管理，交通控制，机器人技术等。最近，M*及其变体大大提高了解决MAPF问题的能力。尽管这些方法中使用的优异扩展大大降低了关节搜索空间的维度并降低了分支因子，但它们并不能充分利用每个代理的最佳路径的可能性非唯一性。结果，碰撞集的更新可能会带来大量的冗余计算。在本文中，旁路的想法被引入细分扩展中，以减少冗余计算。具体而言，我们提出了BPM*算法，该算法是M*中旁路的细分扩展的实现。在实验中，我们表明BPM*在解决了几个MAPF基准问题方面的最先进。
Multi-agent path finding (MAPF) is an active area in artificial intelligence, which has many real-world applications such as warehouse management, traffic control, robotics, etc. Recently, M* and its variants have greatly improved the ability to solve the MAPF problem. Although subdimensional expansion used in those approaches significantly decreases the dimensionality of the joint search space and reduces the branching factor, they do not make full use of the possible non-uniqueness of the optimal path of each agent. As a result, the updating of the collision sets may bring a large number of redundant computation. In this paper, the idea of bypass is introduced into subdimensional expansion to reduce the redundant computation. Specifically, we propose the BPM* algorithm, which is an implementation of subdimensional expansion with bypass in M*. In the experiments, we show that BPM* outperforms the state-of-the-art in solving several MAPF benchmark problems.
