这篇文档属于类型a，即报告了一项原创性研究。以下是针对该研究的学术报告：
多机器人路径规划的新框架：子维度扩展（Subdimensional Expansion）与M*算法
一、作者、机构及发表信息
本研究由Glenn Wagner和Howie Choset（来自卡内基梅隆大学机器人研究所）合作完成，发表于《Artificial Intelligence》期刊2015年第219卷。论文标题为《Subdimensional expansion for multirobot path planning》，提出了一种名为子维度扩展（Subdimensional Expansion）的新框架，并基于此开发了M*算法，用于高效解决多机器人路径规划问题。
二、学术背景
研究领域与动机
多机器人系统在监控、搜救、仓储自动化等领域具有广泛应用潜力，但其路径规划问题面临计算复杂度高的挑战。传统方法分为两类：
1. 耦合方法（Coupled Approaches）：在高维联合配置空间（joint configuration space）中搜索最优路径，但计算成本随机器人数量指数增长（NP难问题）。
2. 解耦方法（Decoupled Approaches）：独立规划单个机器人路径后协调碰撞，计算效率高但无法保证解的存在性或最优性。
本研究旨在提出一种兼顾计算效率与路径质量的混合方法，通过动态调整搜索空间维度，仅在必要时协调机器人运动。
关键背景知识
- 联合配置空间：多机器人系统的状态空间，维度为各机器人自由度之和。
- A*算法：经典启发式搜索算法，用于单机器人最优路径规划。
- 冲突集（Collision Set）：记录需协调的机器人子集，动态调整搜索空间。
三、研究流程与方法
1. 子维度扩展框架
- 步骤1：独立路径规划
为每个机器人计算个体策略（Individual Policy），即忽略其他机器人时的最优路径（通过反向A*实现）。
- 步骤2：一维搜索空间构建
初始时，所有机器人遵循个体策略，形成联合策略路径（Joint Policy Path），搜索空间为一维。
- 步骤3：动态维度扩展
当检测到机器人碰撞时，局部增加搜索空间维度，仅允许冲突集中的机器人脱离个体策略，其他机器人仍受约束。
2. M*算法实现
- 核心改进：将A*算法与子维度扩展结合，动态生成搜索图（Search Graph）。
- 冲突集更新：通过回溯集（Backpropagation Set）传播碰撞信息，更新需协调的机器人集合。
- 有限邻居（Limited Neighbors）：仅扩展冲突集内机器人的可能动作，降低计算负担。
- 递归优化（RM*）：将冲突集拆分为独立子集，分别规划，进一步减少搜索空间维度。
3. 实验验证
- 环境设置：32×32四连通网格地图，障碍物概率20%，机器人数量10–200个。
- 对比算法：A*、Operator Decomposition（OD）、Enhanced Partial Expansion A*（EPEA*）等。
- 性能指标：成功率、中位求解时间、最大冲突集规模。
四、主要结果
计算效率提升
- M*在20机器人问题中成功率显著高于A*和OD（图12），且递归版本（RM*、ODRM*）可处理25机器人问题。
- 冲突集规模：非递归方法最多处理15个机器人的冲突集，递归方法可扩展至25个（表4）。
最优性保证
- 理论证明：M*在有限时间内返回全局最优路径（若存在），且搜索空间维度远低于联合配置空间。
- 实例分析：图10展示M*通过局部协调避免无效搜索，而OD需遍历所有机器人路径。
策略优化效果
- 结合Meta-Agent Conflict-Based Search（MA-CBS）框架后，ODRM*在1000合并阈值下表现最佳（图13），成功解决高密度交互问题。
五、结论与价值
科学价值
- 理论创新：子维度扩展首次将动态维度调整引入多机器人规划，平衡了解耦与耦合方法的优势。
- 算法贡献：M*及其变体（如RM*、ODRM*）为大规模多机器人系统提供了可证明最优且高效的解决方案。
应用价值
- 工业场景：适用于仓储物流、自动化工厂等需高密度机器人协作的场景。
- 开源潜力：算法框架可扩展至其他搜索算法（如RRT*），推动多机器人规划领域发展。
六、研究亮点
- 动态维度调整：通过冲突集局部扩展搜索空间，显著降低计算复杂度。
- 递归冲突分解：RM*将冲突集拆分为独立子集，进一步优化性能。
- 混合框架优势：MA-CBS+ODRM*结合了策略优化与局部协调，达到当前最优性能。
七、其他发现
- 启发式函数影响： inflated heuristic（膨胀启发式）可加速搜索，但牺牲路径最优性（ε-最优）。
- 局限性：在极端密集环境中（如所有机器人需通过单一瓶颈），M*仍需依赖全局耦合规划。
以上报告全面涵盖了该研究的背景、方法、结果与价值，可作为学术交流的参考材料。