《Robotics and Autonomous Systems》：Collision-free multi-UAV 3D path planning using dynamic spatial reservations of reducing air corridors
编辑推荐：
多无人机协同路径规划与动态空中走廊管理研究，提出基于胶囊形空间预留的三维动态走廊收缩机制，结合分层碰撞检测系统实现高效无冲突导航，实验验证了低密度场景下的100%成功率，高密度时需动态调整走廊以应对地形瓶颈。
安德烈·龙津（Andrey Ronzhin）|安东·萨维利耶夫（Anton Saveliev）|德米特里·阿尼金（Dmitry Anikin）|亚历山德拉·扎伊采娃（Alexandra Zaytseva）|叶卡捷琳娜·切尔斯基赫（Ekaterina Cherskikh）|亚历山德拉·菲格雷克（Aleksandra Figurek）
俄罗斯科学院圣彼得堡联邦研究中心（FSBIS St Petersburg Federal Research Center of the Russian Academy of Sciences），俄罗斯联邦圣彼得堡
摘要
本文提出了一种用于多智能体无人机（UAV）系统的集中式协调框架，旨在确保在复杂的三维环境中实现无碰撞导航。该框架的核心贡献是一种基于减少空中走廊的动态空间预留机制。这些定义好的、胶囊形状的体积被分配给每个智能体，并在它们移动时沿其纵轴收缩，从而逐步释放出空间供后续的飞行器使用。为了在协调失败或到达预定义目标点时提高安全性，智能体被封装在保护性的球形区域内。协调逻辑遵循先来先服务的顺序规划范式，智能体使用任意角度路径规划器。生成的路径受到限制，以避免静态障碍物和预留的走廊，同时遵守智能体的特定安全半径要求。在由于空间冲突导致规划失败的情况下，智能体会进入保护状态，并在可配置的延迟后重新尝试路径生成。碰撞检测子系统采用多层方法来提高效率：宽阶段过滤使用八叉树处理静态障碍物，分层哈希网格处理动态走廊，高度边界处理地形。窄阶段则利用解析几何验证，将静态障碍物建模为凸多面体，动态走廊建模为胶囊，地形建模为从高度网格派生的双线性补丁。这确保了所有碰撞检测的精确性和距离准确性。实验结果验证了该框架在各种操作场景中实现无碰撞协调的有效性。尽管计算负载和智能体等待时间会随着智能体数量的增加而增加，但该方法通过严格的验证和重试机制提供了安全性和任务完成的正式保证。因此，所提出的方法特别适用于对操作可靠性要求极高的安全关键应用。
引言
在复杂环境中（如山区或城市化地区）部署无人机（UAV）以解决大规模运输问题时，需要仔细考虑地形几何形状和空域交通密度。多旋翼无人机具有静止悬停和精确转向的能力，通过战略性地设计空中走廊，为提高空域容量提供了潜在的解决方案。
这些无人机越来越多地用于货物运输、基础设施监测和搜救行动，特别是在难以到达的地区。它们的垂直起降（VTOL）能力，加上在狭小空间内的精确定位和灵活性，使它们特别适合密集的城市和地形复杂的环境。然而，无人机应用的扩展导致空中交通强度急剧增加，数十架飞机可能同时在共享的空域内运行。因此，这些异构无人机编队的安全协调成为一个关键挑战。
多智能体路径规划是无人机交通管理系统的基础元素。其目标是确保无冲突运动、防止碰撞并高效利用空域。如果没有强大的协调算法，无人机在各个领域的安全、大规模集成将无法实现。尽管现有的协调方法多种多样，但仍存在一些问题，包括新智能体的操作集成、对导航错误和外部干扰的鲁棒性、通信失败时的可靠性，以及对现实世界障碍物几何形状和地形的精确处理。
为了解决这些挑战，本研究开发了一种基于动态空中走廊的协调系统。该方法利用沿智能体路径的自适应空间预留，由一系列胶囊形状的体积组成。一个关键创新是这些走廊会随着无人机的移动而同步收缩，从而释放出智能体后面的空域并提高整体吞吐量。集中式架构结合了连续的位置验证，使得新智能体可以随时安全地集成到空域中。路径安全性通过三阶段几何验证过程得到保证，包括空间过滤、边界体积检查和精确的解析解。所提出系统的一个显著优势在于它直接使用几何原语（如胶囊、凸多面体和插值地形表面），从而确保了高保真的碰撞检测。
本文的贡献如下：
- •
一种动态空中走廊模型，用于生成由胶囊形状段组成的分段线性无人机路径。这些走廊随着飞行器的移动而同步收缩，动态释放出已穿越的空域以提高利用率。与整个任务期间阻塞整个路径的静态预留方法不同，这种方法逐步释放出后续智能体可以使用的空域。
- •
一种增量集成算法，允许将新的无人机路径添加到操作规划系统中。新智能体规划路径时将现有走廊视为动态障碍物，从而可以在不重新规划之前计算的路径的情况下随时进行集成。
- •
在胶囊半径内的几何安全裕度，可以吸收导航错误和外部干扰，避免因小偏差而需要连续重新规划。在通信丢失时，走廊会保守地保持在其最后已知的状态，确保在通信失败期间无碰撞操作。
- •
一种高保真的路径规划框架，明确地结合了地形和静态障碍物的几何数据。这确保了在复杂环境（如密集的城市地区和山区地形）中计算出安全和可行的轨迹。该框架直接在几何原语（如胶囊、凸多面体和双线性补丁）上操作，提供了连续3D空间中的解析验证，解决了现有方法中简化的环境表示问题。
本文的结构如下：第2节回顾了现有的多智能体路径规划方法及其局限性分析。第3节描述了材料和方法，包括系统架构、规划算法和走廊管理机制。第4节展示了实验验证结果及其讨论。第5节包含结论和未来研究的方向。
相关工作
基于冲突的搜索（CBS）是多智能体规划中一个成熟的范式。基础的CBS算法[2]通过两级结构将多智能体问题分解为单智能体子问题：高级冲突树构建和低级路径搜索。CBS保证了最优性，但假设事先知道所有智能体的信息，并依赖于抽象图，无法考虑真实的几何形状和地形。后续的研究引入了几项显著的扩展：
问题表述和方法概述
我们考虑的问题是为在具有地形起伏和静态障碍物的共享三维环境中运行的多个多旋翼无人机规划无冲突路径。设
表示一组
架无人机智能体。每个智能体
必须执行一个由有序目标点序列定义的飞行任务。工作空间
是一个有界的三维区域，其中包含由数字高程模型（DEM）定义的地形表面
实验设置
在基于VTK可视化库[38]的C++中实现了一个专门的仿真环境。多智能体规划系统的核心功能被实现为一个C++库，该库集成了路径规划、碰撞检测和空中走廊管理的模块。实验在一个模拟的600米×600米×300米的环境中进行。设计了四个复杂程度逐渐增加的测试场景——低、中、高和压力场景，以评估系统性能
讨论
顺序策略导致了解决方案质量的顺序依赖性，这是优先级规划方法的已知特征[8]。中等复杂度场景定量说明了这一效应：智能体1-2的路径长度约为240米，而智能体9-10由于走廊预留的累积，分别需要672米和754米的路径。后来智能体的路径长度增加代表了无需重新规划即可保证运行时间的成本。
有几个因素可以缓解这一问题
结论
所提出的使用动态空中走廊的多智能体规划方法在智能体密度较低的情况下表现出高效性能。在低和中等复杂度场景（5-10个智能体）中，实现了100%的成功率。在高复杂度场景中，从第13个智能体开始出现重新规划尝试，表明可用空域被走廊严重饱和。山区地形通过创建多个智能体走廊汇聚的瓶颈加剧了这一问题。
缩写
本手稿中使用了以下缩写：
| UAV | 无人机 |
|---|
| VTOL | 垂直起降 |
|---|
| UTM | 无人机交通管理 |
|---|
| CBS | 基于冲突的搜索 |
|---|
| MA-CBS | 元智能体基于冲突的搜索 |
|---|
| ECBS | 增强型基于冲突的搜索 |
|---|
| CBS-CIOCA | 基于冲突的策略 - 综合最优冲突避免 |
|---|
| DRL | 深度强化学习 |
|---|
| MMACO | 改进的最大最小蚁群优化 |
|---|
| RL | 强化学习 |
|---|
| CTDE | 集中训练与分散执行 |
|---|
| MPC | 模型预测 |
|---|
CRediT作者贡献声明
安德烈·龙津（Andrey Ronzhin）：撰写——审稿与编辑、撰写——初稿、方法论、调查、概念化。安东·萨维利耶夫（Anton Saveliev）：撰写——审稿与编辑、撰写——初稿、方法论、调查。德米特里·阿尼金（Dmitry Anikin）：撰写——初稿、可视化、软件、调查。亚历山德拉·扎伊采娃（Alexandra Zaytseva）：撰写——初稿、调查。叶卡捷琳娜·切尔斯基赫（Ekaterina Cherskikh）：撰写——审稿与编辑、撰写——初稿、可视化、调查。亚历山德拉·菲格雷克（Aleksandra Figurek）：撰写——审稿
