自主无人机路径规划技术综述

吴浩炜，张川

（1.中国电子科技南湖研究院，浙江 嘉兴 314001；2.中国科学技术大学先进技术研究院，安徽 合肥 230000）

0 引言

无人驾驶飞机（Unmanned Aerial Vehicle，UAV）简称“无人机”，因其价格低、维护成本小、高机动性等优点，已广泛应用于军事和民用领域[1]。无人机避障技术和路径规划是无人机自主飞行、保障无人机安全和完成任务的关键技术。提高无人机的路径规划能力对无人机智能化、自主化是不可或缺的。

无人机的路径规划任务是综合考虑无人机自身的动力学约束和环境约束，结合飞行路径长度、最优性、安全性、飞行能耗、飞行时长等因素，规划出一条从出发点到目的地的最优路径。飞行路径的求解是一个NP-Hard（非确定性多项式时间）问题，并且往往是非凸问题，因此最优路径求解的计算量极大。而对无人机系统这类时变非线性动态系统而言，高计算效率的路径规划能力至关重要。

总体而言，无人机的路径规划应满足以下四点原则：（1）路径规划应能得到从起始节点到目标节点的路径；（2）无人机在飞行路径上不会与障碍物碰撞；（3）生成的路径需要满足无人机自身的机动约束；（4）生成的路径应该尽可能优化。为了更全面细致地了解无人机的各种路径规划技术，本文将对现有文献进行全面综述，如图1所示为无人机路径规划技术图示。

图1 无人机路径规划技术Figure 1 UAV path planning technology

1 基于采样的路径规划

在基于采样的路径规划方法中，无人机的路径规划问题转化为一个连续的状态空间中从有限的候选路径中选择一条可行的路径。在进行路径规划前，需要预先定义三维空间环境的空间配置信息，将整体的状态空间离散成有限的点集，然后使用路径规划方法将节点映射到空间配置上，在有限点集中通过数值方法搜索最优路径。基于采样的路径规划具有以下优点：（1）能够在较短的时间内寻找到一条可行的飞行路径，能很好地满足实时性要求，且可以理论推导出路径具备的概率完备性；（2）能够适用于不同的动态环境；（3）不需要显式地枚举约束条件，可以进行路径轨迹检查。基于采样的路径规划方法有风险地图、单元分解、路线图、势场法等。

考虑到无人机飞行时的静态和动态威胁，Mujumdar和Padhi[2]提出将无人机路径规划分成全局路径规划和局部路径规划两阶段。Primatesta等[3]提出了风险地图这一概念。风险地图是一种基于位置风险的动态地图，地图中的每一个位置点都与无人机飞过该点的风险相关，风险成本量化了无人机飞过该点的风险。他们提出了在基于风险地图的基础上，对无人机进行全局离线路径规划和局部在线路径规划两个阶段。全局离线路径规划在给定风险地图、起始节点和目标节点的情况下，避开静态障碍物和禁飞区，在计算最小风险成本的情况下搜索一条最优飞行路径，全局离线路径规划是在无人机开始执行任务前计算的。局部在线路径规划是根据不断变化的动态风险地图，对已经生成的全局离线规划路径进行调整。当预先生成的路径中出现未预料到的障碍物和其他风险因素时，风险地图会发生变化，局部在线路径规划会根据变化的风险地图重新进行路径规划，确保无人机不会与障碍物发生碰撞。Primatesta等[3]首先在静态风险地图上使用改进A*算法的risk A*算法计算全局路径，然后在动态风险地图上提出了一种Borderland算法。该算法基于应用于网格图的Bug算法，在在线路径规划中检查不断变化的动态风险图并对规划的路径进行实时调整。实验结果表明，Borderland算法能够在短时间、多种场景下调整路径，最大程度地降低风险成本，且Borderland算法并不从头开始计算新路径，而是仅在必要情况下对现有路径进行调整。尤其在高维地图中，该方法具有明显优势。

在单元分解法中，首先将构形空间C-space（configuration space）划分为不同的单元或者区域的集合，然后计算出同一单元或相邻单元的安全路径。当计算出C-space的单元分解后，按顺序连接单元后即可得到飞行路径[4]。

路线图方法通过定义三维空间环境中的曲线来计算自由C-space的连通性。当路线图构建完成后，在搜索阶段，根据给定的初始节点和目标节点通过拼接曲线来搜索飞行路径。路线图方法常适用于静态环境，路径规划的时间较短，通常可以完成实时求解。目前使用最广泛的路线图方法有A*算法、快速扩展随机树（Rapidly-Exploring Random Tree，RRT）等。

RRT算法由于其对动态环境良好的适应性，已被广泛应用于无人机路径规划中，如图2所示为RRT算法示意图。Zhang等[5]提出了一种RRT Connect方法，该方法将RRT与人工势场法相结合，对无人机飞行路径进行规划，仿真结果表明RRT Connect相比RRT得到了更短的飞行路径长度。Lin和Saripalli[6]提出了一种基于闭环RRT的路径规划生成树，并在该方法的基础上提出了三种改进模型：（1）简化节点连接策略，用以减少路径规划的时间；（2）利用中间节点，通过无碰撞轨迹的中间节点以提高路径规划过程的效率；（3）可达集的碰撞预测，通过利用可达集节点对障碍物的运动进行预测，提出了候选轨迹法，使得无人机网络对意外障碍物具有更强的健壮性。同时他们在理论上推导出了算法具有概率完备性，若存在解，则在足够的采样点上寻找到解的概率收敛于1。实验结果表明，该路径规划算法能够让无人机避开不同数量、不同飞行方向的移动障碍物，并且能够在不同的无人机平台上工作。Yang等[7]提出了一种基于环境势场的RRT算法以解决无人机路径规划问题，实验结果表明，该算法具有较高的收敛效率。

图2 快速扩展随机树（RRT）Figure 2 Rapidly expanding random tree

人工势场法（Artificial Potential Field，APF）最早是由Khatib[8]提出的，该算法简单有效，计算量小且路径平滑，但存在局部极小现象。如图3所示为人工势场法中目标产生的引力场和障碍物产生的斥力场。毛晨悦等[9]提出了一种基于APF的无人机路径规划避障算法，在给定出发点和目标点的情况下预先生成一条路径，以提高路径连贯性，将安全性、平滑性和飞行能耗作为调节因子来计算代价函数，最终在候选路径中选取代价最小的飞行路径。丁家如等[10]提出了改进APF的无人机路径规划算法，该算法在路径规划前对全局地图信息进行了威胁建模和连通性分析，缩小了搜索范围，同时通过曲率检查对轨迹平滑化，提高了算法的效率和适应性。Dai等[11]提出了一种分层PFM（Potential Field Method）来解决无人机飞行中目的节点不可达的问题，Bai等[12]向PFM中加入了纵向因素以解决无人机之间的局部极小陷阱。Chen等[13]在PFM中加入了协调力以解决无人机飞行过程中的局部极小问题。仿真结果表明，该方法避免碰撞的概率为98%，可以得到一条安全无碰撞的最优路径。

图3 人工势场法中目标产生的引力场和障碍物产生的斥力场Figure 3 The gravitational field generated by the target and the repulsive field generated by the obstacle in the artificial potential field method a）gravitational field b）repulsive field

2 基于数学模型的路径规划

基于数学模型的路径规划方法将无人机的路径规划问题转化为数值优化问题，旨在解析意义上得到一条最优路径。该类方法主要包括线性规划（Linear Programming，LP）、混 合 整 数 线 性 规 划（Mixed Integer Linear Programming，MILP）、非线性规划（Nonlinear Programming，NP）、动态规划（Dynamic Programming，DP）、贝塞尔曲线、Dubins曲线等。这类算法的时间复杂度通常是用多项式方程来描述的，计算时长很长，故大多数基于数学模型的算法通常被用于无人机的离线路径规划中。将LP应用于无人机的路径规划时，可以将非线性复杂问题转化为线性规划模型。MILP已经在数学建模中得到了广泛的使用，被认为是能够提出最优解和接近最优解的强大数学工具，因此De Waen等[14]利用MILP计算得到了无人机飞行路径。DP可以将问题分解为多个相关的子问题。在无人机的路径规划问题中，DP的目标是计算图中所有节点到目的节点的距离，子问题是计算到相邻点的距离。在这些解中，DP首先考虑最小子问题的解，然后向高一级的问题推进，最终以迭代的方式找到最优解。Liu等[15]提出了一种基于椭圆切线模型的路径规划方法，该方法可以在不构建周围环境地图的情况下快速进行路径规划，实验结果表明，该方法可以有效地完成无人机实时目标跟踪任务。贝塞尔曲线通常用于对生成轨迹进行平滑处理。B样条曲线（B-spline Curves）是贝塞尔曲线的一种一般化，在继承了贝塞尔曲线的几何不变性、保凸性的同时，B样条曲线在点无论增加多少的情况下，多项式的次数都不会增加。因此，B样条曲线在无人机的路径规划中对生成的路径轨迹进行平滑处理时特别有效。Primatesta等[4]对路径轨迹使用了Dubins曲线进行平滑处理，Qu等[16]使用B样条曲线对路径轨迹进行平滑处理，结果表明它们都很好地满足了无人机飞行时的动力学约束。

3 基于启发式搜索的路径规划

在实际规划无人机路径时，可以采用启发式搜索算法将问题的时间复杂性降低到多项式时间问题的水平。启发式搜索算法是受自然启发所创造出的一套算法，它起源于模仿生物的交互行为或物理现象。在实际问题中，用传统的方法无法解决的高复杂度优化问题，可以考虑使用启发式搜索算法进行解决[17]。启发式搜索方法用于解决无人机的路径规划时，即是在无人机的自身动力学、周围环境和实时性等条件的约束下，将路径规划问题转变为复杂优化问题。

Mirjalili等[18]提出了一种灰狼优化算法（Grey Wolf Optimizer，GWO），将无人机路径求解模拟成狼群捕食，该算法具有良好的灵活性和实时性。Radmanesh等[19]提出了一种基于灰狼优化算法的无人机感知避障和路径规划算法，用以解决在未知环境下的多无人机路径规划问题。Qu等[16]认为灰狼优化算法存在两个缺陷：一是在搜索过程中，所有的狼都执行相同的行为，而不考虑个体的特征，对整个群体进行统一的开发行为；二是当所需要优化的问题维度增加时，算法的性能下降明显。无人机的路径规划问题在复杂的三维环境中通常具有很高的维度，因此当灰狼优化算法应用于无人机路径规划时算法性能会显著下降。因此他们提出了一种新的基于强化学习的灰狼优化算法来离线计算无人机的最优飞行路径，并进行几何调整和优化调整，确保了飞行路径的可行性、平滑性和局部最优性。

Wu等[20]提出了一种避障天牛须搜索（Obstacle Avoidance Beetle Antennae Search，OABAS）算法，该算法考虑了更短的飞行路径长度，并结合无人机自身最大转弯角的动力学约束和实时避障的要求与最小威胁面（Minimum Threat Surface，MTS）对飞行路径进行规划，仿真结果表明了该算法的有效性。Tian等[21]提出了一种改进人工蜂群算法，改进后的算法需要的参数少、收敛速度快、计算时间短，适用于多无人机在实时环境下的避障。Cheng等[22]将遗传算法和模拟退火算法相结合，提出了一种新的算法，该算法具有收敛速度快、成本最小等优点。Yang和Yoo[23]将遗传算法和蚁群算法相结合，根据传感、能耗、时间和风险选择无人机最优路径。

通常来说，启发式搜索算法由于计算耗时较长，难以应对动态实时的路径规划场景，因此常被用于无人机全局离线路径规划中。

4 基于深度学习的路径规划

近年来，随着深度学习（Deep Learning，DL）技术的发展，已有越来越多的学者提出将深度学习技术应用于无人机上，引入了深度学习-无人机（DLUAVs）的概念。深度学习技术用于智能化自主机器人是未来机器人发展的一个趋势。近年来，越来越多的研究人员提出了各种不同的神经网络模型和目标检测算法，给无人机的路径规划提供了新的解决方案。Loquercio等[24]提出了一个基于卷积神经网络的DroNet框架模型，该模型通过学习城市街道上正常行驶的汽车和自行车来学习导航；实验结果表明，无人机基于该模型可以对未预料的事件和障碍物迅速做出反应，具备在城市中安全飞行的能力。Palossi等[25]实际制作出了DroNet纳米无人机，实现了纳米无人机的自主导航，结果表明无人机可以以4m/s的速度安全飞行。Wang等[26]利用基于深度学习的目标检测算法和深度摄像机，得到了无人机最优避障策略和最短飞行路径的路径规划方法；实验结果表明，该方法能够显著地提高无人机对环境的感知能力、避障能力和自主飞行能力。如图4所示为用于无人机的一个卷积神经网络模型示例。

图4 用于无人机的一个卷积神经网络模型示例Figure 4 An example of a convolutional neural network model for drones

强化学习的本质如图5所示，是智能体通过与环境交互来得到最优策略，以期能得到最大化的长期回报。目前，无模型强化学习已成为无人机路径规划领域的流行方法之一。Q-Learning算法即是一种强化学习下的路径规划算法。QLearning可以视为一种用随机近似方法求解Bellman方程的方法，它将所有的状态-动作都存储在一张Q-Table中，且由于迭代学习不断产生的状态-动作Q值需要维护和更新，因此在处理高维状态时存在局限性。为了解决这个问题，Mnihet等[27]提出了深度Q网络（Deep Q Network，DQN），将原始图像的高维状态作为深度Q网络的输入。深度强化学习是深度学习和强化学习的结合，对自主智能体问题研究有很强的适用性。Singla等[28]设计了一个基于记忆的DQN网络，用以在未知环境中实现无人机的有效避障，通过在长观测序列中保留关键信息，解决了无人机避障中的部分可观察性问题，实验结果表明该方法的有效性相比DQN有着显著的提升。Yan等[29]提出了一种深度强化学习方法，用于动态威胁环境下的无人机路径规划，实验结果表明该方法在静态和动态的导航任务中具有良好的泛化能力和实时性。Wang等[30]开发了深度强化学习框架用于无人机在复杂环境下的路径规划和自主导航。在该框架下，无人机的路径规划问题转化为部分可观察马尔可夫决策过程（Partially Observable Markov Decision Process，POMDP），他们提出了通用的深度强化学习算法来解决问题。该方法在没有重建地图和路径规划的情况下，能够使无人机在复杂环境中从初始位置飞行到目的地，并且可以推广到更大规模、更为复杂的三维环境中，且方法的性能下降很小。

图5 强化学习的结构Figure 5 Structure of reinforcement learning

5 结语

无人机的智能化和自主化是无人机在军事和民用领域上发展的关键技术。无人机系统平台限制了无人机的尺寸、重量、有效载荷和飞行时长等因素，这些因素又主要受限于当前的传感器和电池技术。此外，机载处理也是无人机研究的重点，尤其是当通信能力会极大影响无人机性能时，如在有限的带宽下传输大量数据。对于多无人机协同飞行，如何防御可能的网络攻击是一个挑战。为了保证多无人机协同飞行时的安全，需要考虑网络干扰、数据协同传输等。Challita等[31]总结了主要的无线网络和安全问题，并介绍了不同的基于人工智能的方法和通过深度学习方法来对安全事件和警报进行分类。Xin等[32]介绍了基于机器学习和深度学习方法对入侵检测进行网络分析的方法。Xiao等[33]提出了一种基于循环神经网络的深度学习-无人机系统网络安全异常行为检测方案。Al-Emadi等[34]提出的算法利用无人机独特的声纹进行安全检测和识别。

如表1所示为无人机路径规划方法的总结。当无人机在现实环境中飞行时，路径规划通常涉及高维连续状态，以目前的方法还无法有效解决无人机的路径规划问题，进而限制了无人机平台应用程序的开发。在元启发式算法中，Wolpert和Macerday提出了没有免费的午餐（No Free Lunch，NFL）定理，他们认为不存在独立于具体应用之外的普遍适用的优化算法。如何有效解决无人机的路径规划问题还是一个未知的挑战。深度学习技术应用到无人机上可以很好地满足高度自主化无人机的操作需求，然而将深度学习技术和无人机技术结合起来仍然存在着很多挑战，如深度学习技术自身的理论问题、训练数据集的选取问题等。

表1 无人机路径规划方法简述Table 1 Brief introduction of UAV planning method

由于深度学习方法的本质是从训练过程使用的数据中提取更复杂抽象的高层表示属性或类别特征，因此使用的数据集的数量和质量对深度学习方法的泛化能力和效力有较大影响，多数深度学习模型的不足也在于学习过程中所使用的数据数量和质量问题。对于监督学习方法，在不同的现实环境中生成具有泛化能力的模型需要大量的数据；自监督学习方法采用了自动化收集数据和标记数据过程，以生成大量的数据集，然而这些数据集也受到标记数据生成策略的限制。现实环境和虚拟环境之间的差距限制了仿真方法在现实世界的适用性，如何开发更具有现实特性的虚拟数据集仍是一个问题。同时，强化学习的试错特性也会引发安全问题，在现实环境中可能遭受崩溃[35]。深度学习-无人机系统分层架构的较低层系统，如特征提取系统，需要大量的计算资源。这些资源需要强大的通信能力和机外处理能力，因此难以在无人机平台上集成。如何进一步开发深度学习-无人机系统架构和提升嵌入式硬件技术是极其重要的挑战。