约束分类视角下多智能体路径规划算法性能分析及其在机器人运动规划中的应用

《IEEE Transactions on Robotics》：An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms

本研究针对多智能体路径规划(MAPF)和多机器人运动规划(MRMP)算法设计中约束选择的关键问题，系统比较了保守型(运动约束)和激进型(优先级约束)两类约束策略。研究人员通过混合网格-路线图表征体系，深入分析了冲突搜索算法(CBS)和带优先级冲突搜索算法(CBSw/P)在不同场景下的性能表现。研究发现：激进约束在高智能体密度或高分辨率场景中求解效率更优，而保守约束在成功求解时能提供更优路径质量。该研究创新性地提出了基于拓扑特征、问题规模、分辨率等多维度决策流程图，为复杂场景下路径规划算法的约束策略选择提供了重要理论依据和实践指导。

　　

在自动化仓储、智能交通和机器人集群协同等前沿领域，多智能体路径规划(Multi-Agent Pathfinding, MAPF)技术扮演着至关重要的角色。随着应用场景的日益复杂，传统的路径规划方法在面对成百上千个智能体协同作业时，往往显得力不从心。特别是在多机器人运动规划(Multi-Robot Motion Planning, MRMP)场景中，机器人本体的几何形状、运动学约束以及环境的高维表征，使得路径规划问题变得更加棘手。

目前，约束类搜索算法已成为解决MAPF问题的主流方法之一，其中冲突搜索算法(Conflict-Based Search, CBS)及其变体因其良好的完备性和最优性保证而备受关注。然而，一个长期困扰研究人员的核心问题是：在面对不同的环境拓扑、智能体规模和表征分辨率时，应该如何选择合适的约束策略？保守的运动约束与激进的优先级约束各自具有怎样的适用边界？这一决策难题严重制约了MAPF算法在真实场景中的应用效果。

为了破解这一难题，来自伊利诺伊大学厄巴纳-香槟分校的研究团队在《IEEE Transactions on Robotics》上发表了重要研究成果。该研究首次从约束分类的视角系统分析了CBS和带优先级冲突搜索算法(Conflict-Based Search with Priorities, CBSw/P)的性能特征，并创新性地提出了基于环境拓扑、问题规模、表征分辨率等多维度因素的决策流程图，为约束策略的选择提供了科学依据。

研究团队采用了一种巧妙的混合网格-路线图表征方法，通过调节分辨率参数(1、2、4)来模拟从传统MAPF网格到复杂MRMP路线图的连续过渡。这种方法既保留了网格表征的结构化特性，又能够捕捉路线图表征中边长时间不等、碰撞检测复杂等关键特征。如图3所示，随着分辨率的提高，路径中的状态数量相应增加，这与MRMP中边离散化增加的效果相似。

在技术方法层面，研究团队重点考察了以下关键环节：首先，他们明确定义了保守约束与激进约束的概念内涵——保守约束(以CBS的运动约束为代表)通过在特定时间步限制智能体访问特定顶点或边来局部化解决问题；而激进约束(以CBSw/P的优先级约束为代表)则要求低优先级智能体在整个路径规划过程中完全避让高优先级智能体。其次，研究引入了介数中心性(Betweenness Centrality)这一图论工具来量化表征拓扑特征，有效识别瓶颈区域和狭窄通道。第三，团队在27个具有不同拓扑特征的地图上进行了系统性实验，涵盖了空旷地图、随机地图、狭窄地图、真实城市地图和视频游戏地图五大类别，每个地图在三种分辨率下各运行25个场景，从而确保研究结论的普适性和可靠性。

环境拓扑特征的影响分析

研究发现，环境表征的拓扑特征是约束策略选择的首要考量因素。在拥有大型开放空间的场景中(如empty系列地图)，激进约束表现出明显优势。如图8所示，CBSw/P在不同问题规模和分辨率下都实现了更高的成功率和相当或更快的运行时间，且解决方案质量的最大次优性仅比最优解高出约1.015倍。这种优势源于激进约束能够快速探索搜索空间，而不会被大量冲突所拖累。

相反，在包含狭窄通道或瓶颈的复杂环境中(如room和maze系列地图)，保守约束则展现出独特价值。如图9所示，当智能体数量较少且表征分辨率较低时，保守约束能够保证智能体间更加协调的行为，且运行时间和成功率与激进约束相当。这是因为保守约束能够精确地定位冲突并施加针对性限制，避免了对整个路径的不必要干扰。

对于具有混合拓扑特征的环境(如城市和游戏地图)，保守约束的整体表现更为出色。如图11和12所示，保守约束在不同问题规模和分辨率下都提供了略高的成功率且规划时间更短，这得益于其能够根据不同区域的特点实施精准的冲突解决策略。

问题规模与表征分辨率的交互影响

研究表明，问题规模(智能体数量)和表征分辨率之间存在显著的交互效应。当智能体数量较多或表征分辨率较高时，激进约束因其更好的可扩展性和计算效率而成为更优选择。这主要是因为激进约束通过施加更少的约束来快速识别有效路径，尽管这是以牺牲完备性为代价的。

特别值得注意的是，随着分辨率的提高，激进约束的优势变得更加明显。在分辨率2的网格路线图表征中，CBSw/P展现出比分辨率1更好的可扩展性，这是因为增加表征中的状态数量使得智能体能够进行更精细的运动，这在智能体密度较高的场景中尤为有益。

决策流程图的构建与应用

基于上述发现，研究团队构建了一个直观实用的决策流程图(图1)，该流程图通过不同颜色区分了环境表征拓扑(棕褐色)、问题规模(粉红色)、表征分辨率(紫色)和期望规划时间(蓝色)四个维度的决策因素。这一工具使得实践者能够根据具体问题特征系统化地选择最合适的约束策略，从而在求解效率和解质量之间达到最佳平衡。

研究的创新性还体现在对表征拓扑与环境拓扑的明确区分上。团队发现，对于MAPF算法而言，影响性能的关键因素是表征拓扑而非环境拓扑本身。如图2所示，同一环境可能产生多个强调不同拓扑特征的表征，这解释了为什么传统基于环境拓扑的分析方法在复杂MRMP场景中往往失效。

研究结论与意义

这项研究的重要意义在于首次系统揭示了约束策略选择对MAPF和MRMP算法性能的影响规律，并提供了实用的决策支持工具。研究明确指出了一个关键发现：协调需求水平是约束选择的核心决定因素。当表征要求高度协调时，保守约束因其能够系统解决冲突并保持完备性而更受青睐；而在协调需求较低的场景中，激进约束则通过快速消除冲突和减少规划开销来提供更高效的解决方案。

此外，研究还强调了表征拓扑分析在算法设计中的重要性，特别是对于高自由度系统的MRMP问题，其中构型空间拓扑可能与物理环境拓扑几乎没有直接关联。团队提出的介数中心性分析方法为表征拓扑的量化评估提供了有效手段，填补了该领域的技术空白。

尽管本研究聚焦于基础版本的CBS和CBSw/P算法，并采用最佳优先搜索作为固定高层搜索策略，但其研究框架和结论为更广泛的约束类算法设计提供了重要启示。未来工作可以在此基础上进一步探索约束表述与搜索策略的分离效应，整合最先进的算法变体，并拓展拓扑表征方法 beyond 介数中心性和网格-路线图抽象。

总之，这项研究为多智能体路径规划领域的算法选择和性能优化提供了重要理论依据和实践指导，对推动自动驾驶、智能仓储、机器人集群等领域的实际应用具有深远影响。通过将约束明确分类为保守型与激进型，开发人员能够做出更加明智的设计选择，从而最终拓宽MAPF算法的有效性和应用范围。