拓扑多样环境：约束搜索在多智能体路径规划中的作用

论文题目：An Analysis of Constraint-Based Multiagent Pathfinding Algorithms

第一作者：Hannah Lee 伊利诺伊大学厄巴纳-香槟分校博士，研究兴趣是将混合算法应用于多机器人任务和运动规划，更具体的将混合算法应用于多机器人任务和运动规划应用，如优先级约束任务分配与路径寻优，以及可重构环境中的任务与运动规划。

通讯作者：Nancy M. Amato 格兰杰工程学院西贝尔计算与数据科学学院院长，伊利诺伊大学厄巴纳-香槟分校阿贝尔·布利斯工程学教授。研究重点是探索动态多机器人系统中的任务规划与交互。曾担任CRA董事会主席、IEEE机器人与自动化学会主席、ACM理事会常任成员以及AAAS第T分会主席。

E-mail：namato@illinois.edu。

拓扑多样环境：约束搜索在多智能体路径规划中的作用

论文摘要

这篇文章聚焦多智能体路径规划（MAPF）和多机器人运动规划（MRMP）中约束搜索算法的设计。传统的分析通常以环境拓扑为核心，但在复杂运动规划中，表示方式（网格、路网、混合网格路网）的拓扑差异远比环境形状更影响算法效果。论文将约束划分为保守（运动约束） 和激进（优先级约束） 两大类，系统比较了经典冲突基搜索（CBS）与基于优先级的 CBSw/P 在混合网格路网表示下的性能。研究发现：当环境拓扑简单或问题规模大、表示分辨率高时，激进约束更容易在有限时间内找到解，但牺牲了一定的完备性；当拓扑复杂或需要高精度协调时，保守约束虽运行时间更长，但可保证解的完整性和更好的协同性。作者提出决策流程图（见图3）帮助读者根据表示拓扑、问题规模、分辨率和可接受的规划时间选择合适的约束类型。这些结论为将MAPF技术推广到高维MRMP领域提供了重要指导。

一、研究背景与问题

1.1 多智能体路径规划与多机器人运动规划

• MAPF定义与难度：MAPF 要求为多个移动体同时规划不相碰撞的路径，应用于装配、疏散、编队、定位和运输等领域。由于状态空间随智能体数量呈指数增长，MAPF 被证明是 NP 难问题。
• MRMP差异：MRMP 不仅要考虑路径，还要对机器人形状、尺寸和运动约束进行建模，因此常通过采样生成非均匀路网或隐式图来表示自由空间。这使得MRMP在表示上更复杂，冲突检测和约束生成更耗时。
• 表示方式影响：传统 MAPF 使用均匀网格，边和动作的碰撞检测简单高效；MRMP 中的非均匀路网包含不同长度的边，带来人工狭窄通道等拓扑伪像。论文提出的混合网格路网表示既保留网格的规则结构，又通过提高采样密度模拟路网的高分辨率特性，使两类算法在同一框架下比较。

关键点

• MAPF与MRMP的表示差异：网格使用均匀采样，路网用随机采样，混合表示通过增加分辨率在两者之间平滑过渡。

• 目标函数：论文使用总成本（sum‑of‑costs）衡量解的优劣，即所有机器人路径长度之和：

  。

  总成本比完工时间 （makespan）更加关注整体效率，适合群体协同场景。

1.2 冲突类型与问题模型

• 冲突定义 ：在离散图  上，机器人在时间步  位于顶点 。当两个机器人同时占用同一顶点时发生顶点冲突；当它们同时沿同一无向边 （不论方向）移动时发生边冲突。
• 混合网格路网的冲突检测 ：在分辨率1时，每条边的持续时间为一个时间步，冲突检测类似传统网格；分辨率升高时，机器人体积覆盖多个顶点，需要检查边中间点的碰撞，近似MRMP中的连续冲突检测。

关键点

• 图表示粒度影响冲突检测复杂度：分辨率越高，冲突检测考虑的配置越多，适用MRMP；分辨率低时类似传统 MAPF。
• 目标是找到无冲突路径集，使所有冲突均被规避。

二、方法框架与技术细节

2.1 保守约束与激进约束

论文将约束分为两类，并明确指出其特性：

• 保守约束（运动约束）：在经典CBS中，当检测到冲突  时，为两个机器人分别添加约束  和 ，禁止它们在该时间步访问冲突顶点或边。这类约束局部而精确，保证搜索空间完整，可得到最优解，但需要不断细分冲突，导致冲突树（CT）规模膨胀、规划时间较长。
• 激进约束（优先级约束）：在CBSw/P中，同一冲突通过约束  和  表示优先级关系。高优先级机器人路径先确定，低优先级机器人必须完全避开高优先级机器人的轨迹。这类约束影响整条路径，拓展搜索空间迅速，能够减少重复冲突，但牺牲完备性和最优性，生成的优先级树（PT）虽然分支数较少，低层搜索成本较高。

关键点

• 保守约束强调局部精细：保证搜索完整性，适用于需要高协调的情景。
• 激进约束强调快速探索：通过优先级限制减少冲突，适用于追求效率的大规模问题，但可能漏解。
• 两者独立于高层搜索策略，本文固定高层为最佳优先搜索，以突出约束形式的影响。

2.2 冲突基搜索框架

论文在保守约束与激进约束的基础上分析两种典型算法：

1. 冲突基搜索（CBS）：

• 初始化每个机器人各自的最短路径。
• 创建冲突树根节点并加入候选集合CT。
• 重复选择CT中成本最低的节点，检查冲突并按冲突为每个机器人产生保守约束，重新规划该机器人的路径并生成子节点。
• 搜索直至没有冲突，返回解或CT为空。 CBS利用保守约束保证最优性，但每个冲突会生成两个子节点，CT的大小随着冲突数线性增长。

2. 基于优先级的冲突基搜索（CBSw/P）：

• 采用与CBS类似的框架，但冲突用优先级约束处理，高优先级机器人先规划，其路径对其他机器人形成不可逾越的“障碍”。
• PT的分支数由机器人对数限制，规模通常小于CT，但由于重规划涉及所有低优先级机器人，低层搜索开销较大。

关键点

• CT vs PT的规模差异：CT因冲突数量增加而迅速扩大，PT受优先级组合限制。
• 完备性差异：CBS完备且最优，CBSw/P不保证找到所有可能解。

2.3 表示分辨率与混合网格路网

为了公平比较两类约束，作者在传统网格和MRMP路网之间引入混合网格路网表示。主要思想是在网格上按分辨率  采样， 等价于MAPF网格， 则将网格细分为更密的路网，提升自由度并模拟MRMP中高分辨率路网的边离散化。在分辨率1到4之间提升时，路径节点数量增加，类似于在MRMP路网中增加边的离散化。

下图展示了不同表示的差异：左为网格（每个栅格对应一个配置），中为网格路网（在网格单元中心抽样），右为随机路网（边长多样，采样不均）。高分辨率路网在本质上引入了人工窄通道，使冲突更加集中。

关键点

• 分辨率越高，节点越多，规划更精细，但低层搜索和冲突检测开销增加。
• 混合表示可控性强，既避免MRMP路网的随机伪影，又能调整粒度研究约束策略的适用性。

2.4 拓扑分析与中介中心性

为定量分析表示拓扑对算法的影响，论文采用中介中心性（Betweenness Centrality, BC） 评估每个节点在图中承载“交通流量”的能力。BC定义为

，

其中  是节点  到  的所有最短路径数， 是这些路径中经过节点  的数量。节点的BC越高，表示其位于更多最短路径上，是潜在的瓶颈或窄通道；BC越低则表示存在替代路径。作者利用BC可视化不同环境的拓扑特征：红色代表高BC的瓶颈区域，蓝色代表低BC的开阔区域。

关键点

• BC揭示表示拓扑：有助于判断环境是否包含窄通道、瓶颈等结构。
• 在无障碍环境中BC不具区分性，需通过中心性方差判断环境是否为空旷。
• BC结合决策流程图：帮助选择约束类型（参见图3）。

2.5 决策流程图

作者根据环境拓扑、问题规模、表示分辨率和预期运行时间四个因素设计决策流程图（图3）。流程图通过颜色编码提出了以下指导：

• 拓扑评估（棕色）：大开阔环境→选激进约束；拓扑混合或复杂→进入下一层判断。
• 问题规模与分辨率（粉色和紫色）：机器人数量或分辨率高→激进约束提高效率但可能丧失完备性；规模小或分辨率低→根据完整性和效率需求选择。
• 预期运行时间（蓝色）：若时间充裕且需完备性→选择保守约束；时间有限→选择激进约束以快速得出解。

三、实验结果与讨论

3.1 实验设计

• 数据集与分组：选取27幅地图，按BC分析分为五类：空旷、随机、狭窄、城市、游戏地图。每幅地图在分辨率1、2、4下生成25个起终对场景，从4个机器人开始，每次增加4个机器人，直到在15分钟内无法求解。
• 评价指标：对每一类地图，统计CBS和CBSw/P在不同问题规模与分辨率下的解决实例数、平均成功率和总成本比值。用平均曲线消除随机生成带来的难易差异。

3.2 结果分析

3.2.1 大开阔环境

在没有明显障碍物的空旷环境中，冲突稀少且协同要求低。实验表明，激进约束在成功率和运行时间上均优于保守约束，且仅在总成本上略有损失（最差仅高出最优值的1.5%）。随着分辨率升高，激进约束的优势更明显，尤其在分辨率2时能以较少的状态数量提供更好的伸缩性。

3.2.2 狭窄环境

狭窄环境包含大量窄通道和瓶颈，机器人密度高、协调复杂。结果显示：

• 当机器人数量少且分辨率低时，保守约束在成功率和运行时间上与激进约束相当，但生成的路径更加协调。
• 随着机器人数增加，保守约束需要在CT上不断分裂，运行时间迅速增长，而激进约束通过一次优先级限制避免重复冲突，更具伸缩性。
• 在高分辨率下，激进约束可以减少运行时间，从而在15分钟内求得解，但由于不完备可能漏掉可行解；保守约束则能保证完整性但计算开销大。

3.2.3 随机环境

随机散布障碍物的环境缺乏突出拓扑特征，协调需求低。结果显示激进约束更适合此类环境：它快速排除冲突，提高计算效率，并保持良好的成功率。保守约束仅在问题规模非常小或分辨率低时具有意义，且会显著增加搜索开销。

3.2.4 混合环境（城市与游戏地图）

城市和游戏地图同时包含宽阔区域、狭窄通道和瓶颈，拓扑多样。实验表明：

• 保守约束在成功率和运行时间上略优于激进约束，其局部冲突解决策略能在不同拓扑区域间灵活调整协调水平。
• 激进约束在复杂环境中虽然可用，但优先级限制会导致大量低层重规划，运行时间较长，且不保证找到解。

3.3 讨论与启示

综合实验结果可以得出以下原则：

• 协调需求高的环境（狭窄或拓扑混合）优先选择保守约束，以保证完整性和路径质量。
• 协调需求低或规模大的环境（空旷、随机）适合激进约束，以减少搜索时间和冲突重启次数。
• 问题规模和分辨率是重要参考：机器人密度超过10–20%时可视为“规模大”，此时激进约束更有优势。
• 运行时间 vs 完整性：如果可接受较长的规划时间并需要完备解，采用保守约束；若时间紧迫且容忍潜在遗漏，则可选择激进约束。

四、创新点与总结

4.1 论文贡献与亮点

• 约束分类框架：首次系统地将约束搜索中的约束分为保守和激进两类，并在同一框架下比较其效果，为算法设计者提供新的认知维度。
• 混合网格路网表示：通过可调分辨率的网格路网统一MAPF和MRMP的表示，为评估约束策略在不同粒度下的性能提供了实验平台。
• 拓扑分析方法：引入中介中心性评估表示拓扑，结合决策流程图为用户选取约束策略提供直观操作指南。
• 决策流程图：从拓扑、问题规模、分辨率和运行时间四个维度总结选择约束的原则，帮助快速决策并推广到MRMP。
• 全面实验：在27个地图、不同分辨率和场景下系统比较CBS与CBSw/P，给出各类环境下约束选择的具体建议。

4.2 限制与未来工作

论文固定高层搜索为最佳优先搜索，仅关注约束类型，未讨论深度优先PBS、分支限界等高层策略对结果的影响。此外，混合网格路网依然是一种抽象，无法完全替代真实MRMP的连续特性；中介中心性在空旷环境中区分度低，需要更丰富的拓扑指标。作者指出未来可以结合现代启发式算法、分层搜索及其他拓扑分析方法，进一步完善约束选择策略。

4.3 总结

本文通过系统地分析保守与激进约束在多智能体路径规划中的表现，指出环境拓扑、问题规模、表示分辨率和运行时间共同决定了约束策略的选择。激进约束以效率为先，适用于空旷或规模大问题；保守约束注重完备性和协同，适合狭窄或混合拓扑环境。混合网格路网提供了统一的实验平台，中介中心性让拓扑分析更直观。论文总结的决策流程图为实践者在设计约束搜索算法时提供了可操作的指导，有助于将MAPF技术推广到更广泛的MRMP应用中。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。