Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
复制标题
多智能体路径查找搜索的成对对称推理
DOI：
10.1016/j.artint.2021.103574
复制
发表时间：
2021
影响因子：
14.4
通讯作者：
Koenig, S.
中科院分区：
文献类型：
--
作者：
Li, J.;Harabor, D.;Stuckey, P.;Ma, H.;Gange, G.;Koenig, S.
多智能体路径寻找（MAPF）是一个具有挑战性的组合问题，要求我们规划一个团队的合作代理的无碰撞路径。在这项工作中，我们证明了MAPF如此难以解决的原因之一是由于一种称为成对对称的现象，这种现象发生在两个代理有许多不同的路径到达其目标位置时，所有这些都看起来很有希望，但它们的每一个组合都会导致碰撞。我们确定了几个类的成对对称性，并表明，每一个通常出现在实践中，可以产生一个指数爆炸的空间中可能的冲突解决方案，导致不可接受的运行时间为当前国家的最先进的（有界子）最佳MAPF算法。我们提出了各种推理技术，有效地检测对称性，因为它们出现和解决它们，通过使用专门的约束条件，以消除所有的排列成对碰撞路径在一个分支的步骤。我们在领先的最佳MAPF算法CBS的背景下实现了这些想法，并表明对称推理技术的添加可以对其性能产生显着的积极影响-我们报告节点扩展数量减少了多达四个数量级，并且可扩展性增加了多达三十倍。这些收益使我们能够最优地解决各种具有挑战性的MAPF实例，这些实例以前被认为是CBS无法达到的。
Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints to eliminate all permutations of pairwise colliding paths in a single branching step. We implement these ideas in the context of a leading optimal MAPF algorithm CBS and show that the addition of the symmetry reasoning techniques can have a dramatic positive effect on its performance — we report a reduction in the number of node expansions by up to four orders of magnitude and an increase in scalability by up to thirty times. These gains allow us to solve to optimality a variety of challenging MAPF instances previously considered out of reach for CBS.
登录
查看更多内容
DOI：
10.24963/ijcai.2019/179
发表时间：
2019-08
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Edward Lam;P. L. Bodic;Daniel Damir Harabor;Peter James Stuckey
通讯作者：
Edward Lam;P. L. Bodic;Daniel Damir Harabor;Peter James Stuckey
影响因子：
1.6
作者：
D. Cohen;P. Jeavons;Christopher Jefferson;K. Petrie;Barbara M. Smith
通讯作者：
Barbara M. Smith
鲁棒的多代理路径查找
DOI：
--
发表时间：
2018
期刊：
Symposium on Combinatorial Search
影响因子：
--
作者：
Dor Atzmon;Roni Stern;Ariel Felner;Glenn Wagner;R. Barták;Neng
通讯作者：
Neng
用于宽松可达性分析的基于对称的任务缩减
DOI：
--
发表时间：
2018
期刊：
International Conference on Automated Planning and Scheduling
影响因子：
--
作者：
Gabriele Röger;Silvan Sievers;Michael Katz
通讯作者：
Michael Katz
使用互斥传播的多代理路径查找
DOI：
--
发表时间：
2020
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
--
作者：
Zhang, H.;Li, J.;Surynek, P;Koenig, S.;Kumar, S.
通讯作者：
Kumar, S.