不确定环境下无人机三维路径规划研究

无人机（UAV）正被整合到生活的各个领域，广泛应用于室内外环境的民用、商业和军事领域。实现无人机交通管理系统（UTM）与空中交通管理（ATM）的集成，无人机机载智能是至关重要的要求。在GPS使用受到严格限制、需要更复杂的定位技术且交通管理系统支持较少的室内应用中，对无人机机载智能的要求更为迫切。

要使无人机被考虑用于特定任务，其使用效益必须明显优于其他成熟的传统系统。无人机的一个关键特性是能够执行自主的、机载实时路径规划。路径规划定义为：在考虑静态和动态环境及模型约束与不确定性的情况下，自动生成通往预定目标点的可行且最优路径的过程。此功能使得无人机在定义其工作环境和目标后，仅需最少的人工干预。因此，自主且鲁棒的路径规划是无人机被考虑用于工业、商业、军事和家庭室内应用的基础。

对自主路径规划的需求始于几十年前机器人技术引入工业重复应用之时。自那时起，路径规划从二维扩展到三维，走出工厂车间，在静态和动态环境中运行，并应对各种约束和不确定性。自主载具的路径规划算法可大致分为三类：基于图（Graph-based）或基于网格（Grid-based）的算法；基于采样（Sampling-based）的算法和插值（Interpolation）算法。

尽管无人机的使用有所增加，但其潜力远未完全发挥。这主要归因于许多尚未完全解决的挑战，阻碍了小型无人机在室内环境中的使用。本研究将重点关注在室内、障碍物密集且无UTM支持（仅提供目标点定义）环境下的路径规划挑战。在此类场景中，预计无人机仅使用机载设施进行操作。在这方面，确定了三个挑战，可总结如下：

在存在静态和动态障碍物以及不确定性的情况下，仅使用无人机机载资源，实时构建从无人机当前位置到目标位置的无碰撞路径。

为实现无人机在室内环境中的路径规划算法，制定了以下研究目标以应对这三个挑战：

评估最先进的路径规划原理在无人机于存在不确定性的三维实时动态室内环境中运行的性能，并根据应用确定定制的配置。

为应对此研究目标，提出了五个研究问题：

研究问题1：无人机三维路径规划领域的最新技术水平是什么？这些算法如何比较？

为探究不同路径规划算法的潜力，考虑了工程各领域的当前技术水平。文献综述表明，基于图的方法和基于采样的方法是三维无人机路径规划的潜在候选方案。对每类中最常用的算法，即A*算法和快速探索随机树（RRT）算法及其变体（即无步长约束的RRT和多快速探索随机树（MRRT）），在不同复杂度的三维场景中进行了测试。还开发了一种路径平滑插值算法，以优化非最优路径（尤其是基于采样的方法产生的路径）。

对每种路径规划变体使用相同的参数实施相同的路径平滑算法，以进行公平比较。这些算法使用同一台计算机在同一组不同复杂度的三维场景上进行测试。为进行比较，将路径长度和计算时间作为性能衡量指标。

实施了具有一系列分辨率的A算法、具有不同步长约束的标准RRT算法、无步长约束的RRT算法以及具有不同种子的多快速探索随机树（MRRT）算法，并比较了它们的性能指标。对于A算法，测试显示在所有场景中，路径长度随分辨率变化存在固有波动。这是由于A*算法基于网格的特性造成的，该特性会导致这样的情况：分辨率的微小增加（理论上应略微缩短路径长度）实际上可能生成长度更长或更短的路径。通过在所有三个维度上将环境随机平移一个介于零到相邻图节点之间距离一半的距离，可以减轻这种波动。

结果证实，在所有考虑的 resolutions、步长和种子的所有场景中，所有算法都能生成路径。相比之下，A算法相对于RRT算法能在更短时间内生成更短的路径，尽管A算法仅探索路径构建所需的区域，而RRT算法均匀地探索环境。结果表明，在存在静态障碍物的离线情况下，A*算法在路径长度和路径生成时间方面均优于RRT算法，在所有考虑的场景中两者成功率均为100%。

A*允许根据场景不同部分的不同需求对环境进行不同的离散化，从而最优地利用资源。相反，RRT及其变体适用于在均匀分布和聚焦的三维区域探索应用中高效生成路径。基于所得结果及其对无人机路径规划的意义，应对第二个研究问题。

研究问题2：所选路径规划算法能否使用小型无人机机载计算资源在实时静态环境中应用？

此研究问题假设所有路径规划计算、感知和环境建模以及执行器控制都必须在机载实时完成。另一个含义是，路径规划器只能可视化由机载传感系统确定的传感距离内的环境，因此只能（如果可能）构建一条通往中间目标点的路径。

在此研究问题范围内，考虑一个等于无人机传感范围的球体，假设传感系统在所有三个维度上具有360度视场角（FOV）。进一步假设传感范围内的静态障碍物是确切已知的，而其他障碍物是未知的，仅当无人机向其方向移动时才变得可见。为模拟实时路径规划，计算时间必须小于或等于无人机从当前位置移动到新位置所需的时间。使用用于应对研究问题1的相同测试环境和相同的性能衡量指标。

结果表明，在所有考虑的场景中，A算法在路径长度和计算时间上再次优于RRT算法，且差异随场景复杂性增加而增大。只要前瞻距离（look-ahead distance）至少是每次迭代移动距离的两倍，A算法在所有考虑场景的所有测试中成功率达到90%或更高。总体而言，由于构建中间路径所需的计算时间比A算法长，RRT算法的成功率低于A算法。

无人机速度、传感器范围和计算能力是基于分析多种无人机机载这些参数的不同研究[1-3]来定义的。基于这些无人机参数的路径规划结果表明，仅使用无人机机载系统即可实现三维实时路径规划。结果给出了不同参数的最佳经验值。这些参数的设置将配置三维实时路径规划平台，针对每个特定的室内应用优化其性能。

研究问题2仅考虑了静态障碍物，但在实际的无人机应用中，障碍物可以移动和旋转，因此需要考虑动态环境以评估所开发的三维实时无人机路径规划算法的可用性。此要求在下一个研究问题中进行探讨：

研究问题3：如果用动态障碍物替换静态障碍物，对路径规划性能有何影响？

动态环境的纳入是路径规划算法外部因素，但它会影响无人机将遍历的路径。室内环境中的动态障碍物可以用对称形状表示。在本工作范围内，构建了四个不同复杂度的场景。这些场景包含旋转和非旋转的立方体、旋转的V形障碍物以及带窗户的静态二维平面。

在动态环境建模中考虑了障碍物的移动和方向。假设随机障碍物移动速度小于或等于无人机的速度，否则避障将不可能实现。

有限范围的实时环境会产生中间目标点不可用的情况。为此，制定了两种不同的基本原理来缓解这种情况。在“等待”策略中，无人机在其当前位置等待，直到定义的中间目标位置变得可用。在“移动”策略中，中间目标位置被移动到更靠近无人机当前位置的地方，从而增加无人机更接近最终目标位置的机会。这两种策略都集成到A*和RRT路径规划算法中，并在所有具有动态障碍物的场景中进行了测试。

结果表明，对于A和RRT算法，与“等待”选项相比，“移动”选项在路径长度、计算时间和成功率方面产生更好的整体结果。在相对简单的场景中，A和RRT产生相似的结果，但RRT在路径长度、计算时间和成功率方面记录到更好的结果。对于复杂场景，如果时间不受限，RRT更优；而A算法受时间约束的影响较小。此外，在复杂场景中，随着速度增加，由于A和RRT都缺乏路径规划时间，成功率会下降。

结果表明，所开发的包含A*和RRT算法的三维实时路径规划平台有潜力用于低障碍物密度的动态障碍物场景。“等待”变体适用于安全性至高无上的情况。在家庭环境中，通常就是这种情况，因为无人机不能与障碍物碰撞，尤其是当障碍物是人时。“移动”变体在目标达成比安全更重要的情境下是理想的，例如搜索和救援。

到目前为止，假设无人机系统内不存在不确定性。在实际场景中，存在一系列不确定性。在下一个研究问题中，研究了在室内环境中运行的无人机的不确定性。

研究问题4：不确定性是否影响无人机的三维路径规划？如果是，如何对这些不确定性进行建模？

此研究问题探究不确定性是否影响无人机在室内环境中的路径规划。这需要进行彻底的文献调研，进而识别并建模可能影响路径规划性能的不确定性源。

在本工作范围内，仅考虑无人机模型内部的不确定性和环境不确定性（通过无人机机载传感系统感知）。其他不确定性，例如与用户的通信，不在本次分析范围内，故不予考虑。

文献指出需要在实时三维无人机路径规划中考虑不确定性，因为如果忽略不确定性，可能对路径规划性能产生负面影响。不确定性可预测的保真度对于确定所提出路径规划算法的可用性至关重要。此外，文献将边界形状和概率分布方法描述为无人机应用中不确定性建模的关键候选方法。在考虑两种方法的特性后，使用围绕当前无人机位置和障碍物体积的边界形状对不确定性进行建模。

一旦不确定性源被识别、估计和建模，便在存在动态障碍物和不确定性的情况下评估所开发的三维实时路径规划算法。

研究问题5：在存在动态障碍物的情况下，能否减轻不确定性以确保无人机实时进行无碰撞三维路径规划？

使用相同的实时三维无人机路径规划平台，考虑为评估研究问题3而构建的相同测试环境。使用A*和RRT路径规划算法及“移动”方法进行测试。基于文献对不确定性边界进行量化，无人机位置和障碍物的不确定性在2%到20%之间变化。通过向实际相应参数添加偏移量来引入不确定性。将独立地并与动态障碍物共同分析每个不确定性源的影响，以确定实时路径规划算法如何安全运行。

结果表明，对于所有考虑的场景，两种不确定性源（无人机位置和障碍物）都降低了A和RRT算法的路径规划性能，其中RRT表现出更大的影响。同时包含两种不确定性源进一步恶化了路径规划性能。在相对简单的场景中，RRT产生最快和最短的路径，成功率与A大致相同；而在相对复杂的情况下，A表现更好。此外，RRT的碰撞风险高于A，因为RRT比A*更频繁地接近障碍物。

从结果可以确认，必须考虑不确定性，因为它对路径规划性能有影响。不确定性建模的准确性会影响所考虑的两种路径规划原理的性能。

在本论文中，每个研究问题都建立在前一个的基础上，以这种方式达成最终研究目标并应对研究挑战。在评估每种算法的路径规划性能（研究目标的第一部分）过程中，可以独立分析每种方法对每个额外复杂因素的响应。这些知识可用于指导未来的无人机设计者根据其应用选择最佳配置，从而达到研究目标的第二部分。

将所开发的三维实时路径规划算法应用于配置真实无人机，使其在室内、障碍物密集的环境中实现自主三维导航，是最终的未来目标，可推动该系统在家庭应用中商业化。此外，该实时三维无人机路径规划系统可被提议集成到室外无人机中。最后，本论文的最终目标是致力于缩小将无人机集成到家庭环境中仍存在的差距，旨在改进当前和未来依赖无人机的服务，最终目标是提升人们的日常生活质量。