复杂环境下无人飞行器航路规划技术研究*

王明明　夏学知

(武汉数字工程研究所　武汉　430205)



复杂环境下无人飞行器航路规划技术研究*

王明明夏学知

(武汉数字工程研究所武汉430205)

摘要为解决常用航迹规划算法在复杂环境下飞行时收敛速度慢、容易陷入局部最优的问题，论文提出了一种基于模拟退火的复合粒子群优化算法。通过对复杂环境进行建模，生成融合了地形、地物及威胁信息的等效数字地形图，并在该地图上使用该改进算法进行航迹规划。实验结果表明，基于模拟退火的融合粒子群优化算法具有较好的可行性和实时性，能够有效解决复杂环境下无人飞行器航迹规划的空间复杂度、搜索效率等，加快全局收敛速度，保持标准粒子群算法较强的鲁棒性，并能够实时避开障碍和规划出最优或次优的路径。

关键词无人飞行器; 航迹规划; 粒子群算法; 威胁建模与回避

Class NumberV279

1引言

无人飞行器(Unmanned Aerial Vehicles，UAV)航迹规划[1]就是指在综合无人飞行器自身机动性能和飞行空间环境信息的基础上，为其提供一条从起始点到目标点安全性较高、航迹代价较小的飞行航迹。无人飞行器航迹规划系统作为UAV任务规划系统中的关键组成部分，为实现无人飞行器自主控制、智能飞行[2]提供了最有力的技术保障。航迹规划一般分为全局航迹静态规划和局部航迹动态规划[3]：全局航迹规划一般是起飞前在地面完成的，并以代码形式输入到机载无人机自动驾驶仪中，作为UAV飞行的参考航迹;局部航迹规划是指无人飞行器在任务飞行过程中遇到新威胁时对参考航迹所做的局部重规划。由目前研究的情况可知：虽然无人飞行器航迹规划研究起步较早，可供选择的算法[4]也很多，但是算法要么具有不错的鲁棒性却不够快速，要么基本上能满足实时性要求却不够稳定;并且很少将算法扩展到三维航迹实时重规划这个问题上。针对上述问题，本文首先采用数字地图融合的思想，在地面上预先把飞行区域内已知的地形、地物及威胁信息融合成一种综合的地形信息，从而使得航迹优化过程中信息扫描的时间变短，同时将威胁回避转化为地形回避来处理，简化了航迹优化算法，满足了实时性的要求。然后吸收作为群体智能算法典型代表粒子群算法的核心思想，对离散域搜索问题在速度进化方程中考虑惯性权重因子，同时在粒子群优化(Particle Swarm Optimization，PSO)算法参数确定过程中引入模拟退火操作，形成一种改进的粒子群优化算法，从而弥补常规PSO算法参数取值过程全凭经验和极易陷入局部最优(即早熟现象)的不足，改善其全局寻优能力，然后用来解决UAV的复杂航路规划问题[5～6]。

2复杂环境下无人机航迹规划

无人机航迹规划是为无人机规划出一条满意的航迹，而航迹是由许多航迹点描述的，因此真正规划的是这些航迹点。无人机飞行的任务环境简单时，常用的航迹规划方法通常可以得到一条满意的航迹，但是当环境复杂时(文中的复杂环境指的是地形复杂或威胁数量与种类众多)，将很难获得一条满意航迹。

以复杂地形为例，当需要引导无人机在图1所示的地形下飞行时，由于无人机的飞行高度需要保持在一定的范围内，因此需要规划出较多的航迹点才能实现类似于地形跟踪的安全飞行航迹。图中地形有三次起伏，通过七个航迹点(图中实线连接点)可以较好的满足高度约束，而若只采取五个航迹点(图中虚线连接点)，将难以实现在避撞的同时满足最大飞行高度的约束。复杂地形下的起伏将很多，此时将需要大量的航迹点来描述。另外，环境中威胁很多时，为了回避威胁也将需要大量的航迹特征点来描述航迹。

图1　航迹规划示意图

近年来，以随机搜索为特征的遗传算法[7～8]，由于其全局搜索能力很强，因此在无人机航迹规划中得到极大应用。但随着航迹点数越多、规划维度越高，遗传算法的计算量随优化问题的维度将呈指数增加，算法的收敛时间显著增加。而粒子群算法[9]相比遗传算法，其通过粒子间的信息交互，能够快速收敛于解空间中的某一点，收敛速度很快，但是后期会出现早熟现象而陷入局部最优，全局搜索能力很差;尤其是粒子群算法中控制参数的设定，往往是根据实际的问题，通过大量的试验，凭借研究经验做出选择，操作起来十分困难。针对粒子群算法存在的上述缺点，本文提出一种基于模拟退火思想的复合粒子群改进方法，在PSO中引入模拟退火的思想，在优化过程中自动优选控制参数，以此构建一种复合粒子群算法。

3航迹规划建模

3.1建立数字地图

本文在进行环境建模时，包括了原始地形的建模、障碍区域的建模和威胁区域的建模[10]。

在进行原始地形建模时，飞行区域设为100×100的直角坐标区域，分别将飞行区域中每个点所对应的z(x,y)的值设为5×rand，即原始地形点z轴的值是在0～5之间的随机数。

(1)

(2)

(3)

将上述地形等效融合成飞行区域的数字地形图，融合算法如式(4)。

z(x,y)=max[z1(x,y),z2(x,y),z3(x,y)]

(4)

式(4)中，(x,y)代表地形中每个点投影到平面上的点坐标，z1(x,y)、z2(x,y)和z3(x,y)则表示地形中每个点的相应地形高度;n代表山峰总数，hi表示第i座山峰的高度，(xi,yi)为第i座山峰的地理中心坐标，ki表示第i座山峰在x轴和y轴方向的坡度向量;(x0,y0,z0)为球心坐标，r代表球体半径，r0是距离气象威胁中心的距离。

在根据式(4)得到各个点的数据后，如果直接进行绘图得到的图形还不能满足要求，图形棱角比较明显，需要进行插值来平滑图形。现在常用的样条函数称为Cubic Spline，即三阶样条函数。本文在建模时采用了规格的样条函数，用interp2命令进行样条函数插值，根据表1～表3中给出的参数设置地形和威胁源，最后得到如图2所示的等效数字地图。其中，坐标系水平方向以100m为单位。山体地形的最大高程为110.68m，任务区域的范围为10km×10km。

表1　山峰地图参数

表2　雷达探测模型参数

表3　气象威胁模型参数

图2　等效数字地图

3.2无人机建模

假设飞行器控制系统理想工作，并忽略它的旋转惯性和旋转角速度对力矩的影响，在求解飞行器轨迹时，由于并不关心它的具体结构，可以把飞行器当作质点考虑。飞行器的质点动力学模型如下：

(5)

其中，x、y、z为飞行器在地面坐标系中的位置坐标;nx、ny、nz分别为地面坐标系中飞行器的切向过载和法向过载;θ、ψ分别为航迹倾角和航迹偏角。

3.3航迹评价函数

复杂环境下无人机航迹规划的评价函数Fmain(xi)包括地形威胁代价Fterrain(xi)、自身性能限制代价Fself_performance(xi)和最短航程代价Fmin_path(xi)，如式(6)所示。

Fmain(xi)=ω1Fterrain(xi)+ω2Fself_performance(xi)

+ω3Fmin_path(xi)

(6)

其中，地形威胁代价Fterrain(xi)又包括山峰地形威胁代价fterrain(xi)、雷达探测威胁代价fradar(xi)和气象因素威胁代价fdemage(xi)，如式(7)所示。

(7)

而自身性能限制代价Fself_performance(xi)包括最大转弯角度限制代价fturn_angle(xi)、最小步长限制代价fmin_step(xi)、最小飞行高度限制代价fmin_height(xi)、最大爬升角度限制代价fvertical_angle(xi)和最大飞行距离限制代价fmax_distance(xi)，如式(8)所示。

Fself_perform(xi)=β1fturn_angle(xi)+β2fmin_step(xi)

+β3fmin_height(xi)+β4fvertical_angle(xi)

+β5fmax_distance(xi)

(8)

(9)

其中，Rt表示无人机到山体的距离，Rm表示等高线上的山体半径。由式(9)可知，无人机与山体间的安全距离为10m，最小距离为4m。当无人机与山体间距离大于最大安全距离时，代价为0，而当与山体距离小于最小安全距离时，代价为1。

(10)

其中，dRmax为雷达实际探测的最大水平作用半径，d为飞行器与雷达的水平距离。

3) 气象因素威胁代价

(11)

其中，Qi(j)表示无人机在第i条航迹下受第j种气象因素影响时损毁的概率，Rjmax表示第j种气象因素的作用范围，R表示无人机距某气象因素作用中心的距离，kj为损毁概率。

4) 最短航程代价

(12)

其中，l表示起点和终点之间的直线距离，di表示航迹中每个航段的长度。

5) 最大转弯角度限制代价

(13)

其中，ψ表示无人机在相邻航段之间的转弯角度。

6) 最小步长限制代价

(14)

其中，i为当前航迹节点i到上一个航迹节点i-1的距离。

7) 最小飞行高度限制代价

(15)

其中，ΔH是根据环境分析以及任务需要所得出的最优的飞行高度。hi为无人机距地面高度。正数kh为约束值。

8) 最大爬升角度限制代价

(16)

其中，γ为当前航段中无人机的爬升和俯冲角度。

9) 最大飞行距离限制代价

(17)

其中，dmax为无人机的最大飞行距离，d为无人机的航程。

3.4最小威胁曲面

在建立数字地图时，将各种威胁等效成地形威胁叠加到数字地图[11]上，这样得到的数字地图不仅包含地形的信息，也考虑了威胁的信息，其中威胁的作用相当于抬高了当地的地形。考虑了威胁信息对数字地图的抬高作用后，定义一个由所有距离地表高度为h的点所构成的曲面，当无人机飞行在这个曲面上时具有最小的危险性，则飞行器的最小危险飞行航迹一定位于这个曲面上。设合成后的数字地图高程为z(x,y)，则最小威胁曲面为

z(x,y)=T(x,y)+z(x,y)

(18)

4航迹规划算法

4.1标准粒子群算法

粒子群优化算法是由Kennedy博士和Eberhart于1995年提出的一种新的群体智能优化算法。在粒子群优化算法中，每个粒子都有自己的位置和速度，还有一个由被优化函数决定的适应度值，而且知道自己当前发现的最好位置pBest和现在的位置xi，粒子的位置代表被优化问题在搜索空间中的潜在解，粒子群追随当前的最优粒子在解空间中搜索。PSO算法初始化为一群随机粒子(即随机解)，然后通过迭代寻找最优解，在每一次迭代中，粒子通过跟踪两个极值来更新自己的位置和速度。对于前面所说的两个极值，一个是粒子本身所找到的最优解，称为个体极值pBest;另一个极值是整个粒子群目前找到的最优解，称为全局极值gBest。设第i个粒子(i=1,2,…,N)的D维位置矢量为xi=(xi1,xi2,…,xid,…,xiD)，第i个粒子的飞行速度为vi=(vi1,vi2,…,vid,…,viD)，该种群中第i个粒子迄今为止搜索到的最优位置记为pid;当前种群中适应度值最大的粒子位置为pgd。标准粒子群算法位置和速度的更新公式为

(19)

(20)

其中i=1,2,…,N；d=1,2,…,D;c1和c2为学习因子，通常C1=C2=2；r1和r2是之间的随机数;k为迭代次数。粒子在不断根据速度调整自己位置的时候，为防止粒子由于速度过大而远离搜索空间，还要受到最大速度Vmax的限制。当Vi超过Vmax时，将被限定为Vmax;粒子位置xid的取值范围为xmin～xmax。

4.2粒子群算法改进

(21)

针对粒子群算法容易陷入局部最优，全局搜索能力差，以及控制参数设定困难的问题，本文将模拟退火的思想融入到粒子群算法中，使算法可以以一定概率接受使评价函数适应度“变差”的解，避免陷入局部最优，从而增强算法全局搜索的能力;同时在PSO算法参数确定过程中引入模拟退火操作，如此一来，可省去选取参数的麻烦，而且在优化过程中，参数能够自适应的根据算法进行改变。

5基于改进粒子群算法的无人机航迹规划

本文利用基于模拟退火的复合粒子群优化算法进行单个无人机的三维航迹规划，每个粒子代表一个潜在的可行路径。该复合算法把粒子群算法作为主要的算法，其参数惯性权重ω、学习因子c1和c2的设定作为一个小的优化问题，由模拟退火在一定范围内进行优化。在每一次的优化过程中，粒子群算法中的最优适应度函数既是粒子群的适应度，同时也是模拟退火对参数优化过程中的评价值。由于模拟退火思想可以以一定概率接受“恶化”解，因此，可以帮助粒子跳出局部的极值，从而找到全局最优极值。算法具体实现步骤如下所示。

Step1：粒子群的初始化。

2)根据式(6)计算每个粒子的航迹评价函数f(xi)，相应地初始化个体极值pBest和群体极值gBest。

Step2：模拟退火的初始化。

1)设置初始温度T=10000，温度衰减因子decayScale=0.7，生成初始解S(ω,c1,c2);

2)求评价函数C(s)：按照式(19)和式(20)更新速度vi和位置xi，并计算出航迹评价函数f(xi)，根据航迹评价函数值相应的更新pBest和gBest，取C(s)=gBest。

Step4：按照式(19)和式(20)更新速度vi和位置xi，其中ω、c1和c2按照S′取值。

Step5：计算航迹评价函数f(xi)。

Step6：求得C(s′)=min[f(xi),i=1,2，…,m]，ΔC=C(s′)-C(s);如果ΔC<0，则C(s)=C(s′)，S=S′，并接受由S′所更新的速度和位置;如果ΔC>0且exp(-ΔC/T)>rand(0,1)，则C(s)=C(s′),S=S′,T=decayScale*T，仍然接受由S′所更新的速度和位置;如果ΔC>0且exp(-ΔC/T)

Step7：根据航迹评价函数值更新pBest和gBest。

Step8：判断是否达到内层循环迭代次数或是否满足内层循环约束条件;若满足，转Step9;否则，转Step3。

Step9：判断是否达到外层循环迭代次数或是否满足外层循环约束条件;若满足，则输出最优值;否则，转Step2。

6仿真及分析

将图2所示的数字地形图作为无人机航迹规划的任务环境;为了测试本文算法在无人机航迹规划方面的性能，分别按标准粒子群优化算法(SPSO) (ω=0.7)、线性递减惯性权重粒子群优化算法(LDPSO)和本文提出的基于模拟退火算法的复合粒子群优化算法(SAPSO)进行航路规划实验。设置起始点为(10，50，50)，目标点为(95，50，50)，种群规模N=40，迭代次数为100，其中D=9，则每个粒子代表的航迹中包含9个航迹控制节点。惯性权重ω取值为0.9到0.4成线性递减，学习因子c1=c2=[1.8,2.2]，初始温度T=10000，衰减因子为0.7。适应度函数如式(6)。在这里无人机完成任务时采取的策略是速度与安全性并重的策略。当迭代次数达到最大或连续五代种群最优值标准差小于0.0001时，算法停止。有关适应度函数的加权设置如表4所示。

表4　权重参数取值

根据表4中的参数取值，然后求解适应度函数。使用Matlab2013a对静态航迹规划进行仿真。三种算法各运行50次，实验结果见表5。

表5　三种算法实验结果表

从实验结果可以看出，标准粒子群优化算法(SPSO)极易陷入局部最优;而在速度进化方程中考虑随进化代数线性递减的惯性因子后，能明显增强算法的收敛能力，一定程度地改善早熟现象;当在粒子群优化算法参数确定过程中引入模拟退火操作后，早熟现象得以充分改观，收敛速度显著加快(平均80代以内即找到最优解);但搜索时间略有增加。

综合改进的粒子群优化算法在数字地图中规划出的可行的航迹示意图分别如图3和图4所示。为使规划出的航迹更贴近无人机实际飞行时的路线，本文还使用了点间拟合的方法将两两航迹控制点依次拟合起来。

图3　全局航迹规划三维立体图

图4　全局航迹规划等高线图

由于本文算法在航迹规划的精度和速度上都有较好的效果，不仅适用于全局静态航迹规划，也可进行局部动态航迹规划，为了检验算法在复杂环境下在线动态规划的能力，本文在上面得到的全局航迹规划的路线中增加突发威胁，如图5所示，当传感器探测到前方有突发威胁时，无人机会以当前航迹控制节点为起点，出现突发威胁路段的下一个航迹控制节点为目标点进行局部动态航迹规划。如图6所示，无人机可以在该算法的引导下及时避开突发威胁。

图5　突发威胁示意图

图6　局部动态航迹三维立体图

7结语

在对UAV飞行复杂环境建立的等效数字地图基础上，采用本文提出的一种改进的PSO算法，即在速度进化方程中考虑惯性权重因子，同时在粒子群优化算法参数确定过程中引入模拟退火操作，然后进行航迹规划。仿真实验结果表明，本文提出的改进PSO算法弥补常规PSO算法参数取值过程全凭经验和极易陷入局部最优(即早熟现象)的不足，改善其全局寻优能力，然后用来解决UAV的复杂航路规划问题。

参 考 文 献

[1] Chao Zhang， Ziyang Zhen， Daobo Wang， Meng Li. UAV Path Planning Method Based on Ant ColonyOptimization[C]//ControI and Decision Conference(CCSC)，2010 China，2010:3790-3792.

[2] Shao P C， Chang Y H， Chen H J. Analysis of an aircraft accident model in Taiwan[J]. Journal of Air Transport Management， 2013， 27: 34-38.

[3] Amin Jayesh N，Boskovic Jovan D，et.al. A fast and efficient approach to path planning for unmanned vehicles [C]// United states: Guidance， Navigation， and Control Conference， 2006:871-879

[4] Pehlivanoglu YV.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology， 2012，16(1):47-55.

[5] Koyuncu E， Garcia E， Inalhan G. Flight deck automation support with dynamic 4D trajectory management for ACAS: AUTOFLY-Aid[C]// Integrated Communications， Navigation and Surveillance Conference (ICNS)， 2012. IEEE， 2012: C4-1-C4-9.

[6] Nikolos I K，Valavanis K P，Tsourveloudis N C.Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE Transaction on Systems， Man， and Cybernetics-PartB，2003，33(6):898-912.

[7] Pehlivanoglu YV.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology， 2012，16(1):47-55.

[8] Fu S Y， Han L W， Tian Y， et al. Path planning for unmanned aerial vehicle based on genetic algorithm. Cognitive Informatics & Cognitive Computing (ICCI* CC)[C]//2012 IEEE 11th International Conference on. IEEE， 2012: 140-144.

[9] Yong Bao， Xiaowei Fu， Xiaoguang Gao. Path Planning for Reconnaissance UAV Based on Particle Swarm Optimization [C]//2010 Second International Conference on Computational Intelligence and Natural Computing (CINC):28-32.

[10] Zhou S， Zhu G， Li H， et al. Real-time route planning for UAV based on weather threat[C]// Remote Sensing， Environment and Transportation Engineering (RSETE)， 2011 International Conference on. IEEE， 2011: 2342-2345.

[11] Ge Y， Yuan L， Zhang W. Path planning based on graphical search ant colony algorithm for unmanned aerial vehicle[C]//Oxide Materials for Electronic Engineering (OMEE)， 2012 IEEE International Conference on. IEEE， 2012: 697-701.

收稿日期：2016年1月10日,修回日期：2016年2月25日

作者简介：王明明，男，硕士研究生，研究方向：指控系统，航迹规划。夏学知，男，研究员，博士生导师，研究方向：指控系统技术。

中图分类号V279

DOI：10.3969/j.issn.1672-9730.2016.07.008

UAV Path Planning Technology in Complex Environment

WANG MingmingXIA Xuezhi

(Wuhan Digital Engineering Institute, Wuhan430205)

AbstractIn order to solve the commonly-used route-planning algorithm’s problem of slow convergence and easy to fall into local optimum in a complex flight environment, a composite particle swarm optimization algorithm is presented based on simulated annealing. By modeling complex environment, equivalent digital topographic map combining topography, surface features and threat information is generated. Then route planning on the map can be done with the improved algorithm. Experimental results show that, the optimization particle swarm fusion algorithm based on simulated annealing has better feasibility and real-time, can effectively solve the problem of spatial complexity and the search efficiency in complex environment of UAV route planning, and accelerate global convergence speed, keeping PSO robust, and avoid obstacles in real time and plan an optimal or suboptimal path.

Key Wordsunmanned aerial vehicle, route-planning, particle swarm algorithm, modeling and avoidance of threat