无人机避障方法研究综述

刘玄冰，周绍磊，肖支才，祁亚辉，代飞扬

(海军航空大学，山东 烟台 264001)

1 引言

随着国防建设和无人机技术的快速发展，无人机凭借其成本低、机动性强、不会造成人员伤亡等特点正在逐渐替代有人机执行高风险的作战任务，为军事作战创造了许多有利条件，具有广阔的应用前景。目前无人机在军事方面主要应用于边境巡逻、情报侦察、定点打击、目标跟踪等作战场景，随着无人机的作战环境从中高空域逐渐拓展至低空域，遇到环境障碍的情况也大大增加。同时，现代战争的作战环境复杂多变，无人机在执行作战任务时将遇到更多的突发情况，在处理未知障碍的问题上也将面临巨大挑战。

无人机避障问题主要是指在指定的飞行环境下，设计一种能够使无人机从起始点安全抵达目标点的方法，这种方法不仅需要考虑如何能够使无人机安全地避开障碍物，而且还需要满足相应飞行航迹的要求以及无人机自身的物理约束条件。具备高效的避障能力已经成为无人机安全完成飞行任务的重要保障之一，因此，无人机在飞行过程中的避障问题逐渐引起许多专家学者的关注。

针对无人机避障问题，目前已有大量文献从不同角度提出了多种解决方案，本文将对无人机避障算法的研究进行综述，并对一些常见的避障算法进行分类介绍，重点介绍避障方法的基本原理并分析各自的优势和不足，为进一步的研究提供参考。

2 避障方法研究现状

关于无人机避障方法的研究，根据其研究成果的不同大体可分为2类：基于航路规划算法的避障方法和基于局部防碰撞算法的避障方法。根据不同任务要求来选择合适的方法。需要注意的是，无人机避障方法研究的分类并无统一界定，在应用时也可依据具体要求将这2种方法结合或与其他算法结合使用，使其能够更好地完成飞行任务。本文这里仅提供一种分类思路。

基于航路规划算法的避障方法也称全局规划避障算法，其基本思想是通过航路规划算法寻找一条使无人机从起始点出发，避开所有障碍物抵达目标点的飞行航路，再运用航路跟踪制导方法，控制无人机沿所产生的航路飞行，达到避障的目的。这类方法需要具备全局障碍信息，适用于环境已知、实时性要求高的任务，多用于静态障碍物，例如无人机在城市地形中飞行，障碍物将是建筑物、树木和其他已知静态结构。基于航路规划算法的避障方法目前主要包括A搜索算法、粒子群算法、快速扩展随机树(RRT)算法以及遗传算法。

A搜索算法是根据评估函数在静态连通图中寻找最优路径的经典搜索算法，也是最有效的直接搜索算法。文献[9]利用稀疏A算法将无人机约束条件进行简化，减小搜索空间，有效缩短了航路规划的时间；文献[10]提出了一种改进双向A算法和向量场直方图算法相结合的规划方法，相比传统A算法，缩短规划的时间和路径。

粒子群算法是一种基于种群搜索策略的自适应随机优化算法，属于启发式搜索算法，在大小一定的搜索空间中具有较高的路径搜索效率。文献[13]提出了一种变惯性权值的改进粒子群算法，提高了航迹规划的精度和稳定性；文献[14]针对无人机避障提出了一种混合粒子群算法，并通过实验证明该算法收敛速度优于传统的粒子群算法；文献[15]提出了一种基于滚动时域控制的模糊粒子群算法用于实现静态避障，具有较好的避障能力。

RRT算法是一种基于采样的单查询随机搜索算法，能够根据当前的环境信息快速有效地搜索规划航迹，可以处理无人机复杂动力学与运动学约束问题。文献[16]针对某型无人机设计了基于RRT算法的在线航路规划算法，并通过仿真验证了该方法的可行性；文献[17]在节点扩展时从已有搜索树中选择若干个距离目标点最近的节点，通过评价函数引导节点的扩展；文献[18]通过引入航迹距离约束，使搜索树沿路径最短的近似最优航迹方向进行扩展，克服了传统RRT算法随机性强的缺陷。

遗传算法是从生物进化思想得到启发而提出的优化算法，具有强大的全局搜索能力，可以很好的解决航路规划的问题。文献[20]提出了一种改进的遗传算法，相比传统遗传算法可以有效解决静态环境下多目标航路规划问题；文献[21]采用基于混沌的遗传算法求解无人机航路规划问题，缩短了路径编码长度，提高了搜索效率；文献[22]通过增加删除节点的操作避免冗余路径点的出现，并通过仿真对比证明该方法生成的路径更加平滑安全。

基于局部防碰撞算法的避障方法也称局部规划避障，是指利用无人机本地防碰撞控制器，对探测到的障碍进行实时规避。这类方法不依赖全局信息，不需要知道初始点和目标点的信息，只需要无人机传感器所探测到的实时障碍信息，多用于先验信息不足的障碍或突发障碍，例如敌方导弹、预警机等。这类方法通常依托于无人机导航控制系统，可以是控制环路的一部分，也可作为单独的内环。基于局部防碰撞算法的避障方法主要包括基于制导律的避障算法，基于速度障碍法的避障算法以及基于人工势场法的避障算法。

基于制导律的避障算法是利用局部障碍信息来计算避障所需的制导指令。文献[26]在参考点航路跟踪制导法的基础上进行改进，确定了规避制导的时机和参考点选取原则，能够使无人机在避障的同时较小偏离原定航路；文献[27]利用无人机与障碍物的信息建立模糊规则，通过模糊控制获得无人机避障所需的制导指令，适用于二维平面避障；文献[28]根据障碍物模型设计了圆弧避障路径，结合非线性制导律实现了无人机三维航路跟踪与避障。

基于速度障碍法的避障算法是利用速度空间模型，将物理空间中的障碍物范围转换到速度空间，从而求解无人机避障时的速度输出。文献[30]建立了三维动态不确定速度障碍的模型，并通过仿真验证了该方法的有效性和可行性；文献[32]对速度障碍法进行改进，相比传统速度障碍法可以实现无人机在密集场景下的避障。

基于人工势场法的避障算法是利用虚拟势场生成对无人机的引力与斥力，并将引力与斥力的合力引入底层控制，从而得到有效的局部避障航路。文献[33]对人工势场法进行改进，使其相比传统人工势场法具有更小的航迹偏差，并通过仿真进行了验证。文献[34]设计了一种基于拉普拉斯方程的人工势场，对障碍物形态具有较高的适应度，可快速计算势场内任一点的梯度。文献[35]提出了一种用于无人机三维避障航路规划的势场法，可以较好地避免局部最小性。

目前提出的无人机避障算法都能够保证无人机的基本飞行安全，区别在于不同算法之间避障准确度、计算复杂度以及适用场景各不相同。全局规划避障在无人机飞行前对航路进行规划，适用于先验信息完整的情况，局部规划避障在飞行过程中实时避障，多用于处理未知障碍或动态障碍，实际应用中按要求也可采用两者相结合的方式。本文接下来将分别介绍全局规划避障算法和局部规划避障算法中的几种典型算法，并通过理论对比分析各算法的优点和不足。

3 基于航路规划算法的避障方法

3.1 A*搜索算法

A搜索算法是一种用于静态连通图的经典搜索算法，A搜索算法用于无人机避障航路规划的基本思路如下。

首先采用栅格法将飞行空间分解为一些具有规则形状的单元，并判断这些单元是否被障碍物覆盖或与障碍物相交，如图1所示。

图1 栅格法分解飞行空间示意图

然后，找到包含起始点与目标点的单元，采用A算法寻找一系列连通的单元将起始单元与目标单元连接起来，A算法的搜索过程是根据启发函数值的大小向着代价低的方向进行，即对于所处的节点，算法利用代价函数对其周边节点进行评估，并选择估价值最小的点为下一节点，代价函数的表达式为：

()=()+()

(1)

式(1)中：()为启发函数；()表示当前节点位置到目标点的预测代价，表示出发点到当前节点的航路代价；()为估价值，由()和()相加得到。在栅格图中，启发函数()通常采用2点间距离表示。A算法的计算过程是一个探索的过程，通过逐渐对最小()的方向延伸，逐渐得到最优解，既为最优航路。

A算法的具体计算过程如下：首先建立2个数组1和2，用于存放无人机所经过的节点信息；然后将划分好的方格添加到数组1中，遍历1中的方格，找出()最小的节点，将其从数组1中移除，添加到数组2中；之后找到与相邻的最近的障碍物方格，获取该障碍物的节点信息，并将可用节点添加到数组1当中；循环以上过程直到把目标点加入到数组1中，或者1为空时，结束算法。当把目标点加入到1中时，代表已找到一条可到达的航路，反之没有找到可到达的航路，算法的流程如图2所示。

图2 A*算法流程框图

3.2 RRT算法

RRT算法是一种基于采样的单查询随机搜索算法，其基本思路是在状态空间中以随机采样的方式扩展构建可行航路集合，然后在以图结构或者树结构表达的路径集合中寻找完整可行路径。RRT算法将状态空间中的出发点作为根节点，然后通过随机采用逐渐增加叶节点的方式生成随机扩展树，生成的过程中，若新的节点与障碍区域有冲突，则舍弃该节点并重新选取。当随机树的叶节点中包含了目标点时，随机树的扩展停止，由此即可得到一条从出发点到目标点的避障航路。随机树的扩展如图3所示，下面给出RRT算法实现避障的具体过程。

图3 RRT节点扩展示意图

图3中，和分别为出发点和目标点，为状态空间中的随机采样点。的选取规则为：以概率选择目标点，并以概率1-在飞行空间内随机选取一个点。表示为在随机树的叶节点中离随机采样点最近的一个节点，然后在和的连线上以扩展步长step为单位截取一个新节点，如果在向新节点扩展的过程中没有碰到障碍物，则将新节点加入随机树中，否则舍弃该节点，并需要重新选择随机采样点。依次通过这样连续的迭代，直至随机树中的叶节点与目标点足够近的时候，结束循环。从构建的随机树中，寻找从出发点到目标点的路径，即为所求的避障航路，RRT算法的流程图如图4所示。

图4 RRT算法流程框图

3.3 遗传算法

遗传算法是在自然界生物进化利用基础上总结出来的一种随机优化搜索算法，其基本思路是首先利用栅格法对飞行空间进行划分，找到被障碍物覆盖或与障碍物冲突的区域；然后在地图中随机生成自出发点到目标的无碰撞路径，路径可以表示为:

={,,,…,-1,,+1,…,}

(2)

式(2)中：表示出发点；表示目标点；表示整条路径中的第个路径节点；(-1,)表示第段路径。路径示意图如图5所示。

图5 遗传算法随机生成路径示意图

在规划过程中，每一条从出发点到目标点的无碰撞路径表示为一个个体，每个个体中有一条染色体，因此每条无碰撞路径也可成为一条染色体。路径中的每一段(-1,)表示为一个基因。所有个体的集合，既生成的所有从出发点到目标点无碰撞路径称为种群。设计相应的适应度函数从种群中筛选出所需的个体，适应度高的个体既为精英个体，通过精英个体之间的交叉变异操作，不断筛选出更优的精英个体直到满足终止条件，最终保留的即为所需的避障航路，遗传算法的流程如图6所示。

图6 遗传算法流程框图

4 基于局部防碰撞算法的避障方法

4.1 基于制导律的方法

基于制导律的避障算法也可视为具有避障功能的无人机制导方法，利用无人机探测到的障碍信息来实时生成加速度指令躲避障碍。其基本思路是将飞行过程中传感器探测到的障碍物信息整合分析，并根据避障要求，建立障碍物覆盖圆以及覆盖圆的组合模型来代替复杂的障碍物，障碍物覆盖圆建立如图7所示。

图7 障碍圆建立示意图

图7(a)为无人机对小型障碍物进行探测生成的覆盖圆，图7(b)为无人机对大型障碍物探测生成的覆盖圆组合，为无人机最大可探测到的角度。当判断无人机靠近障碍物范围时，切换制导律，根据无人机自身的飞行状态以及与障碍物之间的几何关系，计算避障所需的加速度指令，通过加速度指令控制无人机的速度大小和方向；当无人机飞离障碍物范围后，切换为原来的制导律，继续跟踪原航路，基于制导律的避障流程图如图8所示。

图8 基于制导律的避障方法流程框图

4.2 速度障碍法

速度障碍法主要考虑的是针对运动的障碍物进行避障，其基本思路是将物理空间中的障碍物可达范围转换到速度空间，由此求得无人机在速度空间中的可行解。速度障碍的概念最早由Fiorini提出，假设物理空间中，在时刻存在空间范围，则在速度空间存在相应的集合与之对应。如果无人机从=0时刻开始，以中的某一具体速度运动，那么在时刻，无人机的位置一定处在中，这样()就是一个瞬时速度障碍，记为()。对于存在一定时间的障碍物，其速度障碍在速度空间是一个二维的图形，如果障碍物以某个速度运动，则其速度障碍是一个没有尖端的锥形，记为VOS，如图9所示。

图9 VOS示意图

此处的VOS是在障碍物具体运动路径未知情况下得到的，包含了障碍物所有可能的运动方式，比较全面地概括了障碍物的运动范围，速度障碍的计算公式为：

(3)

式(3)中：为速度障碍范围的分段表达式；为对应的物理空间障碍范围。

无人机在飞行过程中利用机载的探测系统获取障碍物的运动信息，然后通过速度障碍法预测障碍物的运动态势，从而可以计算得到避开障碍物的最优速度解，基于速度障碍法的避障流程图如图10所示。

图10 速度障碍法避障流程框图

4.3 人工势场法

人工势场法最早是由Khatib提出的一种虚拟力法，人工势场法避障的基本思路是将无人机在飞行环境中的运动设计成在一种假设的人造力场中的运动，其中目标点对无人机产生吸引力场，障碍物对无人机产生排斥力场，最终使得无人机在引力场和斥力场的叠加下沿势场下降的方向生成一条避障航路，无人机在势场中受力情况如图11所示。

图11 无人机在势场中受力示意图

势场法中引力势函数和斥力势函数的表达式为：

(4)

(5)

其中：为无人机当前位置；()为无人机距目标点的距离；()为无人机距障碍物的距离；为障碍物影响范围；和分别为引力场系数和斥力场系数。

通过对引力势函数和斥力势函数在处求负梯度，即可得到无人机在势场中受到的引力和斥力，由此可以得到无人机所受的合力为：

=()+()

(6)

无人机在飞行过程中利用局部障碍信息与目标点计算当前位置在势场中所受的合力，并根据该合力计算无人机避障所需的控制量，从而引导无人机避开障碍物，基于人工势场法的避障流程如图12所示。

图12 人工势场法避障流程框图

5 避障算法对比分析

无人机避障算法的优劣主要体现在避障成功率、路径最优性以及计算复杂度等方面，针对上述介绍的避障算法，每种算法都有其自身的优势和不足，需要根据不同的飞行任务进行选择，下面对这几种算法进行对比分析。

对于航路规划算法来说：A搜索算法可以在短时间内完成避障航路的规划，得到较优的避障航路，但仅能用于静态环境的规划；A算法的规划效果主要取决于启发函数的选取，较好的启发函数可以得到更优的避障航路，但规划所需要的时间也会相应增加。RRT算法通过对状态空间的随机采样，避免了对空间的建模，具有高效的搜索特性；基于随机规划的方法使得RRT算法能够处理无人机的复杂动力学与运动学约束，但节点的随机采样性也导致该算法得到的避障航路难以保证最优性。遗传算法通过精英个体的反复迭代筛选可以得到最优的避障路径，具有较强的适应能力和鲁棒性，但是进化速度难以控制，运算速度不快，需要较大的存储空间和运算时间。基于航路规划算法的避障方法对比如表1所示。

表1 航路规划算法对比

对于局部防碰撞算法来说：① 基于制导律的避障算法将障碍物简化为障碍圆模型，降低了计算的复杂度；通过加速度指令控制无人机避障，充分考虑了无人机机动性能的约束，具有较小的航迹偏差，但存在障碍物连续出现时需要频繁切换制导律的情况。② 速度障碍法在处理动态障碍物方面具有较好的表现，通过求解无人机面临的碰撞威胁态势，结合不同优化条件，可以得出无人机避障的速度解，可以同时处理多处障碍，但计算复杂度较高，需要一定的计算时间。③ 人工势场法在计算复杂度和路径最优性方面均具有一定优势，但传统人工势场法在复杂环境中会存在局部最优和目标不可达的问题。基于局部防碰撞的避障算法对比如表2所示。

表2 局部防碰撞算法对比

6 结论

综合目前避障算法能够实现的功能以及存在的不足，分别介绍了2种避障方法未来可能的研究方向。根据已发表的相关文献介绍，针对航路规划算法的研究相对成熟，未来的发展方向主要包括：

1) 降低算法计算杂度，减少规划时间，使其具有实现在线航路规划的可能；

2) 对复杂环境下的三维航路规划方法的研究，特别是密集障碍环境和复杂凹型障碍环境；

3) 传统航路规划算法与人工智能技术的结合，优势互补，解决传统规划算法中存在的问题。

4) 避障航路的可跟踪性，结合导航控制系统进一步考虑规划结果的可跟踪性，确保无人机能够正常跟踪。

针对局部防碰撞算法的研究存在更多的研究空间，未来的发展方向主要包括：

1) 算法设计上更多地考虑无人机的动态性能，使输出控制量满足最大转弯角速率和最大可用过载等指标；

2) 减小无人机在处理连续动态障碍时的计算时间，使算法具有更好的实时性；

3) 结合机载传感器的实际性能和工作特性设计避障算法，考虑无人机获取障碍物信息的能力；

4) 全局规划和局部规划2种避障算法相融合，使避障方法更加完备。

尽管无人机避障方法的研究已经取得了不少成果，但大多还处在理论方面，今后应该更多考虑避障工程化方面的研究，在实际环境中检验避障算法的可行性。