Abstract
Multi-Robot-Arm Motion Planning (M-RAMP) is a challenging problem featuring complex single-agent planning and multi-agent coordination. Recent advancements in extending the popular Conflict-Based Search (CBS) algorithm have made large strides in solving Multi-Agent Path Finding (MAPF) problems. However, fundamental challenges remain in applying CBS to M-RAMP. A core challenge is the existing reliance of the CBS framework on conservative "complete" constraints. These constraints ensure solution guarantees but often result in slow pruning of the search space -- causing repeated expensive single-agent planning calls. Therefore, even though it is possible to leverage domain knowledge and design incomplete M-RAMP-specific CBS constraints to more efficiently prune the search, using these constraints would render the algorithm itself incomplete. This forces practitioners to choose between efficiency and completeness. In light of these challenges, we propose a novel algorithm, Generalized ECBS, aimed at removing the burden of choice between completeness and efficiency in MAPF algorithms. Our approach enables the use of arbitrary constraints in conflict-based algorithms while preserving completeness and bounding sub-optimality. This enables practitioners to capitalize on the benefits of arbitrary constraints and opens a new space for constraint design in MAPF that has not been explored. We provide a theoretical analysis of our algorithms, propose new "incomplete" constraints, and demonstrate their effectiveness through experiments in M-RAMP.
Abstract (translated)
多机器人手臂运动规划（M-RAMP）是一个具有复杂单智能体规划和多智能体协调的具有挑战性的问题。最近，扩展流行的基于冲突的搜索（CBS）算法的进展已经大大解决了 Multi-Agent Path Finding（MAPF）问题。然而，将 CBS 应用于 M-RAMP 仍然存在一些基本挑战。核心挑战是 CBS 框架现有对保守“完整”约束的依赖。这些约束确保了解决方案保证，但通常会导致搜索空间中单次规划的重复且代价昂贵的调用。因此，即使可以利用领域知识和设计不完整的 M-RAMP 特定的 CBS 约束以更有效地剪枝搜索，但使用这些约束会使算法本身不完整。这迫使实践者必须在效率和完整性之间做出选择。鉴于这些挑战，我们提出了一个名为 Generalized ECBS 的新颖算法，旨在消除在 MAPF 算法中选择完整性和效率之间的负担。我们的方法允许在基于冲突的算法中使用任意约束，同时保留完整性和约束下的逼近最优解。这使得实践者能够利用任意约束的优势，并为 MAPF 中的新约束设计打开了一个新的空间。我们对算法进行了理论分析，提出了新的“不完整”约束，并通过在 M-RAMP 上的实验验证了它们的有效性。
URL
https://arxiv.org/abs/2405.01772
