New techniques for pairwise symmetry breaking in multi-agent path finding

J Li, G Gange, D Harabor, PJ Stuckey, H Ma… - Proceedings of the …, 2020 - aaai.org
Proceedings of the International Conference on Automated Planning and Scheduling, 2020aaai.org
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 …
Abstract
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.
aaai.org
以上显示的是最相近的搜索结果。 查看全部搜索结果