Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding

多智能体路径规划（MAPF）是指为一组智能体找到一组无冲突路径的问题。通常，智能体的移动被限制在预定义的可能位置和允许它们之间转换的图形上，例如4邻域网格。我们探讨了如何解决MAPF问题，当每个智能体可以在任何可能的位置之间移动，只要穿越连接它们的线段不会导致与障碍物的碰撞。这被称为任意角度路径规划。我们提出了第一个最优任意角度多智能体路径规划算法。我们的规划器基于连续冲突搜索（CCBS）算法和安全间隔路径规划（TO-AA-SIPP）的最优任意角度变体。然而，这些算法的直接组合效果较差，因为任意角度路径规划会产生具有非常大分支因子的搜索树。为了缓解这个问题，我们将经典MAPF中的两种技术适应到任意角度设置中，即不相交分割和多约束。对这些技术的不同组合的实验结果表明，它们可以解决比CCBS和TO-AA-SIPP的基本组合多30%的问题。此外，我们还提出了我们算法的有界次优变体，它可以以可控的方式在运行时间和解决方案成本之间进行交换。

解决问题：本论文旨在解决多智能体路径规划（MAPF）中的任意角度路径规划问题，即在智能体间存在障碍物的情况下，找到一组无冲突路径。

关键思路：本文提出了第一个最优的任意角度多智能体路径规划算法，该算法基于连续冲突搜索（CCBS）算法和安全区间路径规划（TO-AA-SIPP）算法的任意角度最优变体。为了缓解任意角度路径规划的搜索树分支因子大的问题，本文还采用了两种技术，即不相交分割和多约束。

其他亮点：本文实验结果表明，采用不相交分割和多约束技术的组合能够解决超过30％的问题，比使用CCBS和TO-AA-SIPP的基本组合要好。此外，本文还提出了一个有界次优化变体的算法，可以在控制的范围内以运行时间为代价换取解决方案的成本。

相关研究：最近在该领域的相关研究包括《Multi-Agent Pathfinding with Continuous-Time Flows》、《Optimal Multi-Agent Pathfinding with Flow-based Heuristics》等。