Abstract
Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. Typically, the agents' moves are limited to a pre-defined graph of possible locations and allowed transitions between them, e.g. a 4-neighborhood grid. We explore how to solve MAPF problems when each agent can move between any pair of possible locations as long as traversing the line segment connecting them does not lead to the collision with the obstacles. This is known as any-angle pathfinding. We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP). The straightforward combination of those, however, scales poorly since any-angle path finding induces search trees with a very large branching factor. To mitigate this, we adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints. Experimental results on different combinations of these techniques show they enable solving over 30% more problems than the vanilla combination of CCBS and TO-AA-SIPP. In addition, we present a bounded-suboptimal variant of our algorithm, that enables trading runtime for solution cost in a controlled manner.
Abstract (translated)
多智能体路径搜索（MAPF）是找到一组智能体的一组无冲突路径的问题。通常，智能体的移动范围受到预定义的图的约束，例如一个4邻域网格。我们研究了当每个智能体可以在任意两个可能的位置之间移动时如何解决MAPF问题，只要穿过连接它们的线段不导致障碍物碰撞。这被称为任意角路径搜索。我们提出了第一个最优任意角多智能体路径搜索算法。我们的规划基于连续冲突基于搜索（CCBS）算法和最优任意角安全间隔路径规划（TO-AA-SIPP）的优化变体。然而，这种直接的组合表现不佳，因为任意角路径搜索导致具有非常大分支因子的搜索树。为了减轻这种影响，我们将两个经典MAPF技术适应到任意角设置，即离散分裂和多约束。在不同的技术组合的实验结果表明，它们能够解决超过CCBS和TO-AA-SIPP的30%多的问题。此外，我们还提出了一个有界最优的算法变体，它能够以可控的方式 trading 运行时间与解决方案成本。
URL
https://arxiv.org/abs/2404.16379
