发帖
雷达卡
摘要：
本文针对多智能体路径规划（MAPF）中的约束机制，提出将约束划分为保守型（CBS）与激进型（CBSw/P）两类。基于混合网格-路网表示方法，系统分析了在不同分辨率和拓扑结构下，两种约束类型的搜索行为差异；并构建决策流程图以辅助最优约束策略的选择，为MAPF及多机器人运动规划（MRMP）算法的设计提供关键理论支持。
一、引言
多智能体路径规划（MAPF）是实现多智能体协同作业的核心技术之一，其目标是在复杂环境中为多个智能体生成安全、高效且无碰撞的路径序列，广泛应用于自动化装配、紧急疏散、编队控制等场景。该问题的本质挑战在于协调大量智能体的并发移动行为以避免冲突，同时由于状态空间随智能体数量呈指数级增长，已被证明属于NP难问题。
当前主流解决方案多采用基于约束的搜索框架，典型代表包括Conflict-Based Search（CBS）及其变体CBS with Priorities（CBSw/P）。这类方法通过迭代地添加约束来缩小搜索空间，逐步逼近可行解。然而，现有研究普遍忽视了环境表示的分辨率与拓扑特性对约束性能的影响，导致其结论难以有效迁移到更复杂的多机器人运动规划（MRMP）领域。相较于MAPF，MRMP需考虑机器人的几何形状、尺寸及运动学约束，依赖非均匀采样的路网进行建模，由此可能引入“虚假窄通道”或遗漏真实狭窄区域（如图2所示），显著增加路径规划的不确定性。
本研究依托伊利诺伊大学厄巴纳-香槟分校与墨西哥自治技术学院联合提出的约束分类框架——将约束划分为保守型与激进型，选取基础CBS（施加运动约束）与CBSw/P（引入优先级机制）作为分析对象。结合混合网格-路网表示模型（见图3：分辨率1对应传统MAPF网格，更高分辨率则模拟MRMP中高密度离散化路网），深入探讨不同环境配置下两类约束的搜索效率与解质量表现，并最终提出一个可指导实际应用的决策流程图（图1），为MAPF/MRMP算法设计提供系统性参考。
二、核心概念界定
2.1 MAPF 与 MRMP 的本质区别
MAPF与MRMP在环境建模方式与碰撞检测机制上存在根本性差异（如图2所示）：
- MAPF：通常将环境抽象为规则的均匀网格，忽略机器人具体几何细节。每个智能体的状态被映射至单一网格单元，碰撞检测简化为判断同一时间步内是否有多个智能体占据相同网格节点，环境表示固定且计算简便。
- MRMP：必须考虑机器人的真实形状、体积和朝向变化，依赖随机采样生成非结构化路网。边长与时序跨度差异显著，碰撞检测需精确验证机器人实体是否与其他智能体或障碍物发生几何交集。此外，稀疏采样可能导致未实际存在的“人工拓扑”出现，例如虚假的狭窄通道，而真实瓶颈却可能因采样不足被忽略。
为统一分析尺度，本文采用“混合网格-路网”（grid roadmap）作为统一表示形式：当分辨率为1时，完全退化为传统MAPF网格；当分辨率提升至2或4时，在保持网格结构的基础上增加顶点密度（如图3所示：分辨率1含4个顶点，分辨率4扩展至25个），以此逼近MRMP中高离散化的路网特征。该设定聚焦于MAPF查询算法在不同表示下的适应性表现，而非路网构建过程本身。
2.2 保守约束 vs 激进约束：约束类型的分类体系
本文依据约束作用范围与强度，将MAPF中的约束机制划分为两大类：保守型与激进型，分别以CBS和CBSw/P为代表，其核心特征对比如下：
| 约束类型 | 典型算法 | 约束形式 | 搜索行为 | 解特性 |
|---|---|---|---|---|
| 保守约束 | CBS | 运动约束：限制某智能体在特定时间步不得访问某一顶点或边（如禁止ai在t时刻位于v）；约束局部、精准 | 采用冲突树（CT）结构增量求解，每发现一次冲突即分支扩展，搜索深度随冲突数上升而增加，整体规划耗时较长 | 智能体间协同性强，路径整体优化程度高；保证算法完备性（有解必能找到）与最优性 |
| 激进约束 | CBSw/P | 优先级约束：为智能体分配全局优先级，低优先级个体必须全程避让高优先级路径；约束影响范围广、粒度粗 | 构建优先级树（PT），分支数量受限于优先级排列组合，能快速探索解空间，规划响应速度快 | 协同性较弱，部分潜在解可能因优先级设定被提前剪枝，牺牲完备性风险；解质量相对较低 |
2.3 冲突类型与评价指标
MAPF的核心目标是生成一组无冲突的团队路径。主要冲突类型包括：
- 顶点冲突：两个或多个智能体在同一时间步占据同一顶点；
- 边冲突：多个智能体在同一时间步沿同一条边移动，尤其包括方向相反的“交换冲突”。
衡量路径质量的关键指标为“成本和”（sum-of-costs），即所有智能体从起点到目标所经历的时间步总和。相比“完工时间”（makespan），该指标更能反映整体路径效率，适用于评估多智能体系统的综合性能。
三、实验方法论
3.1 表示分辨率与拓扑结构的影响分析
为探究环境表示对约束性能的作用，设置三种分辨率等级：1、2、4（参见图3）。随着分辨率提高，混合网格-路网的顶点密度相应增大，路径状态空间随之扩张，更贴近MRMP中高离散化路网的实际特征。此设置旨在考察从标准MAPF向复杂MRMP过渡过程中，保守与激进约束的表现演化规律。
拓扑特征的量化分析采用介数中心性（Betweenness Centrality, BC）方法，用于表征环境中的拓扑结构（如图 5 所示）。介数中心性反映节点在所有最短路径中出现的频率：数值较高的节点通常对应于通道狭窄或瓶颈区域，而数值较低的节点则代表空间开阔的区域。基于该指标，可将测试环境划分为五类典型场景——空环境（无任何障碍物，中心性分布均匀）、随机环境（障碍物分布杂乱，缺乏明显拓扑规律）、窄通道环境（存在多个瓶颈结构，高中心性节点呈链状分布）、混合环境（模拟城市或游戏地图，兼具开阔区域与狭窄通道）。
3.2 实验设计
实验设置如下：
- 测试环境：共使用 27 张基准地图，涵盖空地图、随机地图、窄通道地图、城市地图及典型游戏地图（如图 7），以覆盖多样化的拓扑特性；
- 对比算法：选取基础版 CBS（保守约束）与 CBSw/P（激进约束），高层搜索均采用“最佳优先”策略，确保约束类型为唯一变量，排除搜索机制带来的干扰；
- 实验流程：每张地图在 3 种不同分辨率下进行测试，每个配置运行 25 个独立场景，智能体数量从 4 开始，每次递增 4，直至系统在 15 分钟内无法完成求解；
- 评价指标：包括求解实例数（15 分钟内成功解决的场景总数）、成功率（成功场景占总场景的比例），以及解质量（通过 CBSw/P 与 CBS 的路径成本比值衡量）。
四、核心实验结果（融合关键图表）
依据决策流程图（图 1），在不同拓扑条件下，保守约束与激进约束的表现差异显著：
4.1 大开阔区环境（空地图）
如图 8 显示，在各类分辨率和智能体规模下，激进约束（CBSw/P）在求解实例数与成功率方面均接近或优于保守约束（CBS）。同时，其解成本仅略高，最大成本比为 1.015 倍。因此，在开阔区域主导的环境中，推荐优先采用激进约束，可在保证解质量的前提下显著提升求解效率。
4.2 窄通道环境（多瓶颈结构）
如图 9 所示，在窄通道密集的环境中表现如下：
- 当智能体数量较少且地图分辨率较低时，保守约束生成的路径协同性更强，规划时间与激进约束相近，建议优先使用；
- 当智能体数量增多或分辨率提高时，保守约束易导致冲突树分支爆炸，规划耗时急剧上升；此时激进约束能有效提升求解成功率，应优先选用。
4.3 随机环境（无显著拓扑特征）
如图 10 所示，随机环境中缺乏明显的空间结构特征，任务协调需求较低。在此类场景中，激进约束能够快速剪除相似冗余路径，显著缩短搜索时间，求解效率远超保守约束，且解质量损失几乎可以忽略，因此强烈推荐使用激进约束。
4.4 混合拓扑环境（城市 / 游戏地图）
如图 11 与图 12 所示，混合环境融合了开阔区域、窄通道及多种瓶颈结构。在此类复杂拓扑中，保守约束能更精确地处理局部冲突，表现出更高的求解实例数、成功率以及更短的规划时间，整体性能优于激进约束，故建议优先选择保守约束。
五、核心结论与指导建议
本研究通过系统性实验明确了保守约束与激进约束的适用边界，其核心结论可通过图 1 的决策流程图直接指导实际应用：
- 拓扑特征导向：对于大范围开阔区域或无明显拓扑结构的环境，推荐使用激进约束；而对于包含多种地形特征的混合拓扑环境，则应优先采用保守约束；窄通道环境需结合智能体规模与地图分辨率综合判断；
- 规模与分辨率影响：在智能体数量多或地图分辨率高的情况下，激进约束有助于提升求解效率；而在智能体少、分辨率低的场景中，保守约束更利于保障解的质量；
- 效率与完备性权衡：若计算资源有限或无需保证完备性，可选用激进约束；若要求确保有解或追求最优解，则保守约束更为合适。
本研究为多智能体路径规划（MAPF）及多机器人运动规划（MRMP）中的约束机制选择提供了明确的设计指南。未来工作可拓展至含噪声或不确定性的动态环境，并结合深度优先、有界次优等高阶搜索策略，进一步验证不同类型约束的鲁棒性与适应性。
京公网安备 11010802022788号
