基于滚动时域冲突解决的高质量高效四旋翼无人机集群轨迹重规划方法

《Drones》：A High-Quality and Efficient Trajectory Replanning Method for Quadrotor Swarms Based on Rolling-Horizon Collision Resolution

　　

研究人员提出一种面向无人机（UAV）集群的高质量且计算高效的轨迹重规划方法，称为RHCR-Opt，该方法旨在密集障碍环境中持续高效地生成多条无碰撞轨迹。RHCR-Opt由三层组成。前两层是基于冲突搜索（Conflict-Based Search, CBS）的滚动时域冲突解决（Rolling-Horizon Collision Resolution, RHCR）算法，第三层专注于使用最小控制（Minimum Control, MINCO）轨迹进行轨迹生成与优化。在两层RHCR框架内，研究人员提出了一种融入时空约束的改进型终身规划A*（Lifelong Planning A*, LPA*）算法，并将其作为CBS的低层求解器，以满足在变化时空约束下频繁搜索可行路径的需求，从而显著提升计算效率。此外，在高层CBS框架中采用了滚动时域冲突解决概念，仅考虑有限时间窗口内的无碰撞路径发现，这大幅降低了时间窗口之外轨迹生成与优化的计算负担。在第三层，研究人员设计了一种基于MINCO的轨迹生成方案，并提出了一种有限时间窗的集群轨迹联合优化框架，以生成动态可行且无碰撞的轨迹。同时，针对需要同时到达的集群任务，研究人员开发了一种两阶段时间协调优化方法。大量仿真实验表明，与所提基准上的最先进（State-Of-The-Art, SOTA）算法相比，RHCR-Opt在轨迹质量和计算效率上均有显著提升。特别地，当集群规模较大时，计算效率提升至少23.7%。

在无人机集群自主导航中，运动规划是核心组成部分，但传统方法常将集群运动规划视为一次性任务。实际应用中（如农药喷洒、搜索救援、监视巡检），集群需实时适应动态变化的目标区域，轨迹重规划需求更为迫切。现有方法中，集中式方法在联合状态空间中生成轨迹，计算效率受集群规模严重制约；分布式方法（如基于速度障碍法、分布式模型预测控制、分布式轨迹优化）虽灵活鲁棒，但缺乏集中协调，在密集场景下易出现轨迹质量下降或规划失败，且对称场景中可能发生死锁。基于冲突搜索（CBS）的方法结合了分布式规划与集中式冲突解决，有效平衡了轨迹质量与计算效率，但现有方案的前端往往采用CBS的次优变体（如增强冲突搜索ECBS、优先级搜索PBS），虽提升计算效率却牺牲了路径质量；后端轨迹优化在处理复杂时空约束时仍负担较重。为此，研究人员提出一种基于滚动时域冲突解决的高质量高效四旋翼无人机集群轨迹重规划方法RHCR-Opt，旨在不牺牲路径或轨迹质量的前提下提升计算效率。

研究人员开展了以下研究：提出三层框架RHCR-Opt，前两层为基于CBS的滚动时域冲突解决（RHCR）算法，第三层为基于最小控制（MINCO）轨迹的生成与优化。在RHCR框架中，采用融入时空约束的改进终身规划A*（LPA*）作为CBS低层求解器，利用增量搜索能力减少重复计算；在CBS高层引入滚动时域冲突解决概念，仅考虑有限时间窗口内的冲突，避免窗口外路径生成与轨迹优化。在第三层，设计基于MINCO的轨迹生成方案（包括航点选择和局部目标点选择策略），提出有限时间窗的集群轨迹联合优化框架，将动态约束、避障约束和集群碰撞避免约束作为惩罚项纳入无约束优化问题。针对同时到达任务，提出两阶段时间协调优化方法：第一阶段基于时间负载均衡的任务分配（混合整数二次规划MIQP），第二阶段为软约束时间优化。论文发表在《Drones》。通过大量仿真实验验证，与最先进算法（RBP、EDG-TEAM）相比，RHCR-Opt在轨迹质量和计算效率上显著提升，集群规模大时计算效率提升超23.7%。

主要关键的技术方法包括：1）基于改进LPA*的低层搜索（利用增量搜索能力，避免重复节点扩展）；2）滚动时域冲突解决（RHCR）概念（仅在有限时间窗口内解决冲突，降低计算负担）；3）基于MINCO的轨迹生成与联合优化框架（包括航点选择和局部目标点选择策略，将动态可行性、避障、集群碰撞避免作为惩罚项，并设计有限时间窗的惩罚公式）；4）两阶段时间协调优化方法（第一阶段为基于时间负载均衡的MIQP任务分配，第二阶段为软约束时间优化）。样本队列来源：仿真实验在随机生成的地图和障碍物环境中进行，具体地图尺寸、障碍物数量、集群规模等参数均明确设定。

研究结果如下：
**5.1 改进LPA*对CBS性能提升**：通过对比CBS（A*）和CBS（LPA*）在相同测试实例中的表现，研究人员发现LPA*在初始规划后节点扩展数保持在个位数，而A*持续扩展数百个节点；计算时间上LPA*仅在初始规划阶段较长，后续重规划显著低于A*。CBS（LPA*）相比CBS（A*）迭代次数减少73.3%，计算时间减少82.2%。结论：改进LPA*通过动态维护搜索图并灵活适应时空约束，显著提升了CBS在复杂环境下的计算效率。
**5.2 RHCR-Opt性能分析**：通过设计四种算法配置（CBS(A*)-Opt、CBS(LPA*)-Opt、CBS(LPA*)-Opt-R、RHCR(LPA*)-Opt）进行对比，研究人员发现CBS(LPA*)-Opt相比CBS(A*)-Opt在路径成本相同的情况下，CBS计算时间减少90.4%；RHCR(LPA*)-Opt相比CBS(LPA*)-Opt-R，在重规划迭代中CBS高层迭代次数、CBS计算时间、MINCO轨迹优化时间均显著降低，整体计算时间减少约37.5%。结论：RHCR-Opt通过滚动时域冲突解决和后端联合优化，在保持高轨迹质量的同时大幅提升计算效率。
**5.3 特殊场景集群飞行**：在穿墙遍历和对称交换场景中，研究人员将RHCR-Opt与最先进的分布式规划算法Ego-Swarm-v2对比。在穿墙场景中，Ego-Swarm-v2未能成功穿过墙洞，部分无人机选择绕飞；在对称交换场景中，Ego-Swarm-v2频繁出现悬停、轨迹扭曲和回溯现象。而RHCR-Opt通过前端集中式冲突解决和后端联合优化，生成更平滑、直观的飞行轨迹。结论：RHCR-Opt在密集或对称场景中避免了分布式方法的死锁和轨迹质量下降问题。
**5.4 与基线算法比较**：在全局规划任务中，研究人员将RHCR-Opt与RBP（使用ECBS前端和Bernstein多项式轨迹后端）对比。RHCR-Opt与RBP在前端路径成本相近，但RHCR-Opt后端轨迹优化时间保持在4ms-34ms，比RBP减少一到两个数量级；所有集群规模下成功率均有提升，整体计算时间随规模增大接近一个数量级降低。在重规划任务中，与EDG-TEAM（使用ECBS前端和MINCO后端）对比，当集群规模为8或16时，RHCR-Opt前端计算时间略高，但规模增至32或64时，前端及后端计算时间均显著降低，总计算时间减少超过23.7%。结论：RHCR-Opt在中等及大规模集群中计算效率优势明显，且轨迹长度、飞行时间、控制代价均优于基线。
**5.5 两阶段时间协调优化效果**：研究人员设计三种方案（无任务分配和软约束、仅软约束、两阶段完整方法），执行同时到达任务。结果表明，两阶段方法使飞行时间范围从0.941s降至0.386s，飞行时间方差从0.164降至0.027。结论：所提出的两阶段时间协调优化方法显著改善了集群同时到达性能。

总结讨论部分，论文指出：在无人机集群轨迹重规划中平衡轨迹质量与计算效率是根本挑战。RHCR-Opt通过滚动时域冲突解决，在不牺牲路径或轨迹质量的前提下提升计算效率，仿真验证了其在SOTA算法上的优势。研究结论翻译如下：本文提出了RHCR-Opt，一种基于CBS的集群轨迹重规划框架，通过滚动时域冲突解决来应对轨迹质量与计算效率的平衡挑战。RHCR-Opt框架由三层组成：前两层为基于CBS的RHCR框架，第三层执行基于MINCO的轨迹生成与优化。在RHCR框架内，研究人员提出了一种显式考虑时空约束的基于LPA*的低层规划器，并将其集成到CBS中；在CBS高层，采用滚动时域冲突解决概念。在RHCR生成多条无冲突路径后，采用基于MINCO的轨迹生成方案，并开发了基于时间窗的集群轨迹联合优化框架。此外，为满足集群任务中的同时到达需求，研究人员提出了一种两阶段时间协调优化方法。所有提出的贡献均经过全面的实验验证和定量分析。仿真结果表明，在所提出的基准上，RHCR-Opt相比最先进方法实现了更优的轨迹质量和更高的计算效率。特别地，当集群规模较大时，计算效率提升超过23.7%。RHCR-Opt也存在若干实际局限性：尽管轨迹执行是分布式的，但冲突解决由指定规划无人机执行，因此框架依赖可靠且低延迟的通信以及该规划器的可用性；当集群规模、冲突密度或环境变化率导致规划时间接近重规划间隔时，其实时优势可能减弱；此外，当前验证假设静态环境和准确状态信息，未建立对通信丢失、感知误差、动态障碍物或模型失配的鲁棒性。这些条件界定了RHCR-Opt当前的适用性，并激励了未来在混合分布式协调和不确定性感知重规划方面的工作。