本文档属于类型a，即报告单一原创研究的学术论文。以下是针对该研究的详细学术报告：

作者及机构
本研究由Anton Andreychuk（俄罗斯人民友谊大学/RUDN University、俄罗斯科学院计算机与控制联邦研究中心）、Konstantin Yakovlev（俄罗斯科学院计算机与控制联邦研究中心、HSE University）、Eli Boyarski（本-古里安大学）和Roni Stern（本-古里安大学、帕洛阿尔托研究中心）合作完成，发表于AAAI 2021会议。

学术背景
研究领域为多智能体路径规划（Multi-Agent Path Finding, MAPF），核心问题是解决多智能体在连续时间（continuous-time）环境下的无冲突路径规划。传统MAPF算法（如Conflict-Based Search, CBS）依赖时间离散化假设，而现实场景（如机器人导航、机场调度）需处理连续时间下的非均匀动作时长和几何碰撞。已有算法如CCBS（Continuous-Time CBS）虽支持连续时间，但未整合CBS的优化技术（如冲突优先级、分离拆分），导致可扩展性受限。本研究旨在将CBS的三大改进（Prioritizing Conflicts, PC; Disjoint Splitting, DS; 高层启发式）适配至CCBS，提升其求解能力。

研究流程与方法
1. 问题建模与算法改进
- 目标：将DS、PC和启发式融入CCBS框架。
- DS适配：
- 提出“正约束”（positive constraints）和“负约束”（negative constraints）。正约束要求智能体在特定时间区间内执行动作（如移动或等待），负约束禁止动作。
- 开发广义安全区间路径规划算法（Generalized SIPP, GSIPP），支持多起点/目标搜索，确保动作地标（action landmarks）的完整覆盖。例如，在存在负约束时，GSIPP会为同一顶点生成多个安全区间（safe intervals），分别规划路径。
- PC适配：
- 定义冲突的“成本影响”（cost impact），即解决冲突导致的最小成本增量。通过显式低层搜索计算成本影响，优先处理高成本冲突。
- 启发式设计：
- 提出两种启发式：基于线性规划（h1）和贪心选择不相交冲突（h2）。h2通过排序冲突成本影响，快速估算解的下界。

1. 实验验证

   • 实验设计：
     
     • 数据集：稀疏/稠密/超稠密路网（roadmaps）及8/32连通网格（grids），基于MovingAI基准。
       
     • 对比算法：原始CCBS、CCBS+PC、CCBS+DS、CCBS+DS+PC、CCBS+DS+PC+h。
       
     • 指标：成功率、运行时、扩展的高层节点数（CT nodes）。
       
   • 实验过程：
     
     • 逐步增加智能体数量（n），记录30秒内可求解的最大n。
       
     • 对高扩展节点实例，分析启发式对节点数的削减效果。
       

2. 数据分析

   • 统计各算法在成功率、运行时和扩展节点上的差异，通过箱线图和表格展示中位数比率。
     

主要结果
1. DS的优化效果：
- 在超稠密路网中，CCBS+DS的求解能力比原始CCBS提升49.2%（实例数从3,792增至5,659），部分场景支持两倍智能体数量。
- 正约束通过限制分支因子（branching factor）显著减少冗余路径。

1. PC与启发式的协同作用：

   • 在稀疏/稠密路网中，CCBS+DS+PC+h表现最佳，扩展节点数比CCBS+DS+PC降低17.8%-26.5%。
     
   • 高连通度网格（如32-neighborhood）中PC效果减弱，因高分支因子降低了冲突成本差异。
     

2. 计算效率：

   • 改进版CCBS的运行时比原始版本快两个数量级，尤其在复杂场景（如warehouse网格）中优势显著。
     

结论与价值
1. 理论贡献：
- 首次将DS、PC和启发式整合至连续时间MAPF框架，证明了广义SIPP和成本影响度量的有效性。
- 提出正/负约束的形式化定义，为连续时间规划提供新工具。

1. 应用价值：
   
   • 提升算法在机器人协作、物流调度等实时场景的实用性，支持更高密度智能体的路径规划。
     
   • 开源实现（GitHub）为后续研究提供基准。
     

研究亮点
1. 方法创新：
- GSIPP算法通过多安全区间处理，解决连续时间下的动作地标规划问题。
- 成本影响度量（cost impact）量化冲突优先级，优于传统基数冲突分类。

1. 实验全面性：

   • 覆盖路网和网格两类场景，验证算法在不同分支因子下的鲁棒性。
     

2. 跨领域意义：

   • 成果可扩展至动态障碍物避障（dynamic obstacle avoidance）和混合系统规划（hybrid systems）。
     

其他价值
- 缓存冲突检测结果和差分启发式（differential heuristics）的优化策略，为工程实现提供参考。
- 未来方向包括动态图（dynamic graphs）和实时约束处理。