New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding
New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding
复制标题
多智能体路径查找中成对对称性破缺的新技术
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sven Koenig
中科院分区：
文献类型：
--
作者：
Jiaoyang Li;G. Gange;Daniel Damir Harabor;Peter James Stuckey;Hang Ma;Sven Koenig
我们考虑了在多智能体路径发现(MAPF)的背景下出现的两类新的成对路径对称。第一种是走廊对称性，当两个代理人试图以相反的方向通过同一狭窄通道时，就会出现这种情况。第二种称为目标对称性，当一个代理的最短路径在第二个代理已经到达第二个代理的目标位置后穿过该目标位置时，就会出现目标对称。这些对称性可能会在可能的冲突解决方案空间中产生指数级爆炸，导致无法接受的运行时间，即使对于基于冲突的搜索(CBS)等最先进的MAPF算法也是如此。我们建议使用新的推理技术来打破这些对称性：(1)检测每一类对称，(2)通过引入专门的约束来解决它们。我们的实验表明，在某些情况下，我们的技术可以将CBS的成功率提高一倍以上，并将其运行时间提高一个数量级。
We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.
大型代理的多代理路径查找
DOI：
--
发表时间：
2019
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence (AAAI
影响因子：
--
作者：
Li, J.;Surynek, P.;Felner, A.;Ma, H.;Kumar, S.;Koenig, S.
通讯作者：
Koenig, S.