多智能体路径规划（MAPF）是一个在机器人、交通控制和自动化仓库等领域具有广泛应用的重要问题。MAPF的核心目标是为一组智能体找到一组无冲突的路径，使它们能够从起点移动到目标位置。传统的MAPF问题通常限制智能体只能在预定义的图上移动，这种限制在实际应用中可能不够灵活。
任意角度路径规划（Any-Angle Pathfinding）是一种更为灵活的方法，允许智能体在不碰撞障碍物的情况下在任意位置之间移动。这种方法在提高路径规划效率和适应复杂环境方面具有显著优势。然而任意角度路径规划也带来了新的挑战，特别是在多智能体环境中，如何确保路径的无冲突性和最优性成为一个关键问题。
被IROS 2024会议接收论文《Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding》提出了第一个针对任意角度多智能体路径规划的最优算法，并介绍了其有界次优变体。这些算法在解决复杂路径规划问题时表现出色，具有重要的理论和实际意义。通过引入连续冲突搜索（CCBS）和安全区间路径规划（TO-AA-SIPP），以及多约束（MC）和分离拆分（DS）技术，论文的算法显著提高了路径规划的效率和效果。
研究团队由Konstantin Yakovlev、Anton Andreychuk和Roni Stern组成，他们分别隶属于多个知名研究机构。Konstantin Yakovlev隶属于FRC CSC RAS（俄罗斯科学院计算机科学与控制研究中心）、AIRI（人工智能研究所）、HSE University（高等经济学院）和MIPT（莫斯科物理技术学院）。Anton Andreychuk隶属于AIRI（人工智能研究所）。Roni Stern隶属于Ben-Gurion University of the Negev（内盖夫本-古里安大学）。他们在多智能体路径规划领域具有丰富的研究经验和深厚的学术背景，为论文的研究提供了坚实的基础。
研究背景
多智能体路径规划（MAPF）是一个在机器人、交通控制和自动化仓库等领域具有广泛应用的重要问题。MAPF的核心目标是为一组智能体找到一组无冲突的路径，使它们能够从起点移动到目标位置。传统的MAPF问题通常限制智能体只能在预定义的图上移动，这种限制在实际应用中可能不够灵活。
近年来，研究人员开始探索放宽这些经典假设的方法。Yakovlev和Andreychuk提出了一种基于优先级规划的任意角度MAPF算法，这种算法允许智能体在不碰撞障碍物的情况下在任意位置之间移动。这一方法在提高路径规划效率和适应复杂环境方面具有显著优势。然而任意角度路径规划也带来了新的挑战，特别是在多智能体环境中，如何确保路径的无冲突性和最优性成为一个关键问题。
其他研究也提出了支持运动学约束的技术。例如，Yan和Li提出了一种基于优先级搜索的三阶段求解器，能够处理加速和减速动作。这些研究虽然在一定程度上解决了MAPF中的一些问题，但它们大多不是最优的。
在最优MAPF求解器方面，许多研究是对冲突基搜索（CBS）的改进。例如，Solis等人提出了为每个机器人构建路线图并使用CBS进行规划的方法，并结合轨迹优化方法为异构智能体团队（如四旋翼机）构建无碰撞路径。Kinodynamic变体的CBS也被提出，用于处理具有不同运动学特性的智能体。
尽管这些研究在一定程度上解决了MAPF中的一些问题，但它们大多集中在经典MAPF假设的基础上。论文的研究旨在进一步放宽这些假设，提出一种新的任意角度多智能体路径规划算法（AA-CCBS），并通过引入多约束（MC）和分离拆分（DS）技术来提高算法的效率和效果。
问题陈述
在多智能体路径规划（MAPF）中，目标是为一组智能体找到一组无冲突的路径，使它们能够从起点移动到目标位置。传统的MAPF问题通常限制智能体只能在预定义的图上移动，这种限制在实际应用中可能不够灵活。论文研究的任意角度多智能体路径规划问题（AA-MAPF）则放宽了这一限制，允许智能体在不碰撞障碍物的情况下在任意位置之间移动。
图1：同一MAPF实例的两个最优解：由基数组成的一个只移动（左），而具有任何角度的一个移动（右）。后者的成本降低了22%。
具体来说，AA-MAPF问题的目标是找到一组将智能体从起点传送到目标位置的无冲突路径，并且这些路径的总成本最小。每个智能体可以在任意角度上移动，只要它们的路径不与障碍物相交。这种任意角度的移动方式使得路径规划更加灵活和高效，但也带来了新的挑战，特别是在多智能体环境中，如何确保路径的无冲突性和最优性成为一个关键问题。
图2：vanilla AA-CCBS多约束的示例。
论文提出的AA-CCBS算法结合了连续冲突搜索（CCBS）和安全区间路径规划（TO-AA-SIPP），旨在解决这些挑战。CCBS算法通过在连续时间间隔上进行搜索，避免了时间离散化的问题，而TO-AA-SIPP算法则能够处理动态障碍物环境中的任意角度路径规划。通过结合这两种方法，AA-CCBS算法能够在保证路径最优性的同时，提高路径规划的效率。
此外，为了进一步提高算法的性能，论文引入了多约束（MC）和分离拆分（DS）技术。多约束技术通过添加多个约束来减少高层搜索迭代次数，而分离拆分技术则通过在冲突解决时添加正负约束来减少搜索工作量。这些技术的结合使得AA-CCBS算法在处理复杂路径规划问题时表现出色。
算法介绍
研究团队提出了一种新的任意角度多智能体路径规划算法，称为AA-CCBS（Any-Angle Continuous Conflict-Based Search）。该算法结合了连续冲突搜索（CCBS）和安全区间路径规划（TO-AA-SIPP），并通过引入多约束（MC）和分离拆分（DS）技术来提高算法的效率和效果。
连续冲突搜索（CCBS）
CCBS是冲突基搜索（CBS）的变体，适用于非离散时间线。它通过在连续时间间隔上进行搜索，避免了时间离散化的问题。CCBS的工作原理是为每个智能体单独找到路径，检测这些路径之间的冲突，并通过对个别智能体重新规划来解决冲突。CCBS通过高层搜索选择要约束的智能体，并通过低层搜索找到满足约束的路径。
安全区间路径规划（TO-AA-SIPP）
TO-AA-SIPP是SIPP（Safe Interval Path Planning）的变体，旨在为在动态障碍物环境中导航的智能体找到最优的任意角度路径。TO-AA-SIPP的搜索节点由一个元组（顶点，安全时间间隔）标识，表示智能体可以在该时间间隔内安全地驻留在该顶点。与SIPP不同，TO-AA-SIPP不会通过扩展搜索节点来迭代构建搜索树，而是预先生成所有搜索节点，并迭代尝试识别节点之间的正确父子关系，以获得最优解。
多约束（MC）
多约束技术通过添加多个约束来减少高层搜索迭代次数。论文提出了三种MC方法。
MC1：识别出所有源顶点相同的动作子集，并为每个智能体添加相应的多约束。尽管MC1方法有效，但在AA-MAPF中，互相冲突的动作数量可能很大，导致不安全区间过短，从而削弱约束效果。
MC2：为解决上述问题，MC2方法通过仅考虑有限的动作集和过滤掉导致原始不安全区间缩短的动作来增强约束效果。MC2方法在约束效果上更强。
MC3：进一步扩展MC2，包含不同源顶点但相同目标顶点的动作。这些动作可能导致相同智能体在几乎相同位置发生碰撞，因此自然地包含在同一多约束中。
图3：包含多约束的不同版本的动作。请注意，MC2和MC3中动作的时间间隔明显大于MC1。因此，预计MC2和MC3将表现出更大的修剪能力。
分离拆分（DS）
分离拆分技术通过在冲突解决时添加正负约束来减少搜索工作量。一个CCBS子节点对智能体i添加负约束，另一个子节点对智能体i添加正约束并对智能体j添加负约束。论文提出了两种实现方式：
直接使用DS：这种方式较为直接，通过在冲突解决时添加正负约束来减少搜索工作量。
结合MC使用DS：这种方式需要处理多个起点位置的连续搜索，较为复杂。为了简化DS和MC的集成，论文建议避免将多约束作为地标，而是使用常规的负多约束。
通过结合这些技术，AA-CCBS算法能够在保证路径最优性的同时，提高路径规划的效率和效果。实验结果表明，这些改进显著提高了算法的性能，使其在处理复杂路径规划问题时表现出色。
实验结果
为了评估AA-CCBS算法的性能，研究团队在MovingAI基准测试中进行了广泛的实验。实验使用了多个不同类型的地图，包括空地图、随机地图、迷宫地图和仓库地图。每个地图提供了25个场景，每个场景包含一组起点和目标位置。实验通过逐步增加智能体数量，直到算法在300秒的时间限制内无法找到解决方案为止。
实验结果显示，AA-CCBS算法的多种变体在不同场景下表现出色。具体来说，MC3、DS和DS+MC3变体显著优于其他变体。MC3在快速解决简单实例方面表现尤为突出，而DS和DS+MC3在处理复杂实例时表现更佳。
在评估有界次优AA-CCBS时，研究团队使用了不同的次优性界限（w = 1.01, 1.1, 1.25）进行实验。结果表明，MC3在寻找有界次优解时显著提高了AA-CCBS的性能，而DS变体未能超越原始AA-CCBS。这可能是因为DS的正约束在次优搜索中效果较差，不能立即消除冲突，而MC3通过对更多动作施加约束，在贪婪搜索中更有效地消除冲突。
具体实验结果如下：
图4:AA-CCBS不同变体的评估。左侧窗格显示了AA-CCBS每个版本在5分钟时间限制内完全解决的实例数量。中间窗格显示了找到解决方案所需的时间（Y轴以对数刻度表示）。
每个数据点告诉算法在一定时间内（Y轴）能够解决多少个实例（X轴）。右侧面板展示了解决不同MAPF问题实例所需的高级迭代次数。X轴显示实例id。每个数据点告诉算法（Y轴）对特定问题实例（X轴）进行了多少次高级迭代。
实验结果表明，AA-CCBS算法及其增强版本在处理任意角度多智能体路径规划问题时表现出色。MC3在快速解决简单实例和寻找有界次优解方面表现尤为突出，而DS和DS+MC3在处理复杂实例时表现更佳。这些结果验证了多约束和分离拆分技术在提高算法性能方面的有效性。
有界次优AA-CCBS
在实际应用中，找到最优解往往需要耗费大量时间和计算资源。为了在保证解的质量的同时提高算法的效率，论文提出了有界次优（Bounded Suboptimal, BS）AA-CCBS算法。该算法通过允许解的成本在最优解成本的某个倍数范围内，从而在一定程度上放宽了最优性的要求，以换取更快的求解速度。
图5:AA-CCBS的评估结果及其在不同次优因素下的修改。
实现方法
有界次优AA-CCBS的实现基于在高层搜索中引入焦点搜索（Focal Search）。具体来说，在每次高层迭代中，算法会创建一个名为FOCAL的节点列表。FOCAL包含所有生成的节点，这些节点的成本不超过 ( w \cdot f_{\text{min}} )，其中 ( w ) 是次优性界限， ( f_{\text{min}} ) 是常规AA-CCBS将扩展的节点的成本。
在FOCAL中，算法选择冲突最少的节点进行扩展，并在节点数量相同时优先选择约束更多的节点。这种方法迫使搜索更贪婪地解决冲突，同时保持所需的次优性界限。
实验结果
研究团队对BS AA-CCBS进行了广泛的实验，评估了不同次优性界限（ ( w = 1.01, 1.1, 1.25 ) ）下的算法性能。实验结果显示：
结论与未来工作
论文提出了第一个针对任意角度多智能体路径规划（AA-MAPF）的最优算法AA-CCBS，并通过引入多约束（MC）和分离拆分（DS）技术显著提升了算法的性能。实验结果表明，这些改进在处理复杂路径规划问题时表现出色，能够有效地解决冲突并找到最优解。
具体来说，MC3在快速解决简单实例和寻找有界次优解方面表现尤为突出，而DS和DS+MC3在处理复杂实例时表现更佳。这些结果验证了多约束和分离拆分技术在提高算法性能方面的有效性。
未来工作可以从以下几个方面进一步探索和改进。
多约束形成过程：探索更复杂和高效的多约束形成过程，以进一步提高算法的剪枝能力和搜索效率。
增量搜索技术：在任意角度低层搜索中适应增量搜索技术，以减少重复计算和提高求解速度。
实际应用场景：将AA-CCBS算法应用于更多实际场景，如自动驾驶、无人机编队和智能交通系统，验证其在真实环境中的性能和鲁棒性。
算法优化：进一步优化算法的实现，减少计算资源的消耗，提高算法的可扩展性和适用性。
总之，研究团队为任意角度多智能体路径规划提供了一种高效且实用的解决方案，具有重要的理论和实际意义。通过进一步的研究和改进，AA-CCBS算法有望在更多领域中得到广泛应用，为复杂路径规划问题提供更优的解决方案。（END）
参考资料：
本文转载自，作者：