基于遗传模拟退火算法的无人机航迹规划

邱福生，杨建平，邵绪威

(沈阳航空航天大学 航空航天工程学部(院)，沈阳 110136)

基于遗传模拟退火算法的无人机航迹规划

邱福生，杨建平，邵绪威

(沈阳航空航天大学 航空航天工程学部(院)，沈阳 110136)

航迹规划技术是无人机任务规划系统中重要的核心技术之一，无人机飞行空间广阔，需要一种快速搜索最佳路径的方法。首先在飞行区域中建立数字地图模型和防空威胁区模型，在满足无人机飞行约束条件的情况下，为无人机航迹规划提供一种遗传模拟退火算法，充分利用模拟退化算法的概率突跳特性和遗传算法强大的快速搜索能力。仿真结果表明，使用该算法无人机能够自动避开模拟数字地图的威胁区，搜索出一条安全有效航迹，并保证航线的完整性和最优性。

无人机；航迹规划；遗传模拟退火算法；威胁区

无人机航迹规划就是在根据无人机自身性、战场环境和任务要求，为其选择一条安全有效的飞行路线，在现代日新月异的高科技空战中，航迹规划是确保飞行器对敌区进行远程侦察和精确打击必要途径之一。航迹规划技术主要是研究在航迹规划中的算法，程国采研究的最优控制方法由于在航迹规划中执行时间较慢，此算法在地形复杂、新增威胁较多的战场环境下规划出的航线不是很理想[1]。2000年Robert J Szcaerba提出的A*算法经常应用在机器人二维路径规划中，在三维的航迹规划中常常出现组合爆炸的问题[2]。Kenneny J.Eberhart研究的粒子群优化算法(Particle Swarm Optimization，PSO)在约束优化过程中，罚函数的设计过于复杂，不利于求解，若约束处理的不好，其优化的结果往往会出现不能够收敛和结果是空集的状况[3]。遗传算法是一种全局最优搜索算法，但容易得到局部最优极值[4]。本文采用的遗传模拟退火算法利用基本遗传算法的编码技术和概率搜索技术，在交叉和变异过程中结合模拟退火算法常用的Metropolis接受准则对遗传算法求解过程进行扰动[5]，跳出局部最优解，从而得到目标函数的全局最优解，在航迹规划中使用模拟退火遗传算法能够减少迭代次数和求解时间，并且能够得到最优航迹，因此在求解要求越来越高的航迹规划领域，遗传模拟退火算法在求解过程中得到了广泛的应用。

1 飞行区域

1.1 地形的构建

无人机航迹规划的首要条件就是建立数字地图模型，其它航迹规划元素模型的建立都是在建好的数字地图模型上展开，地图模型的复杂程度直接影响着航线的优越性。随着计算机仿真技术的越来越成熟，数字地图的仿真模拟方法也越来越多。为了使数字地图模型在仿真过程中趋于真实，本文根据文献[6]给出了一种函数模拟方法加以改进，在文献[6]提出的模型中的横纵坐标前添加一个调节系数，改进后的数字地图模型如下：

(1)

其中，x，y表示水平投影面上的点坐标，Z1表示对应水平面坐标点的地形高度。a，b，c，d，e，f，g，ξ是常系数，可以通过调节a，b，c，d，e，f，g，ξ的大小来模拟各种数字地形。为了能模拟出高度、宽度和坡度各不相同的山峰，采用高斯造型法通过公式(2)来对山峰进行构造模拟：

(2)

其中，x，y表示水平投影面上的点坐标，Z2表示对应水平面坐标点的地形高度。h(i)和xi(i)，yi(i)是山峰的轮廓参数，i表示第i座山峰的山体，通过公式(3)：

Z(x,y)=max(Z1(x,y),Z2(x,y))

(3)

可以将山峰和起伏的地貌通过取两者较大高程值的方法叠加融合到一起，形成一个完整的地形[7]，如图1所示。

1.2 防空武器威胁区模型

雷达是军事上低空突防时具有较大威胁的探测设备，其探测能力易受周边环境的影响，如果考虑各种影响因素，精确的描述雷达的探测能力非常复杂，一般用雷达的探测空域来考察其威胁性能，雷达主要依靠短电磁波沿直线传播，电磁波传播的距离越远，电磁波的能量越弱，则威胁代价也越小。地空导弹是防空火力最重要的火力部分，一般配置在主要目标附近，对射程内的无人机有较高的杀伤概率，在无人机进行航迹规划时应当避免飞入导弹的威胁区域。在导弹威胁区域内，无人机距离导弹位置越远，威胁代价越小[8]。雷达和地空导弹的威胁代价都是随着无人机距离雷达和地空导弹越远而越小，将雷达和地空导弹的威胁空域映射到定高的二维平面上组成防空武器威胁区域，防空武器威胁模型合并为如下数学模型：

图1 模拟地形图

(4)

其中，fLDi表示第i段航迹被雷达和导弹威胁的代价，β为参数，表示无人机在第i段航迹距离雷达和导弹中心最近点受雷达和导弹的威胁的强度，它与威胁概率和威胁密度有关，di表示第雷达和导弹威胁中心点第i段航迹的距离，R表示雷达和导弹的威胁半径。

图2 威胁区模拟图

2 含约束条件的最优航迹规划问题

2.1 航迹约束条件

在对无人机航迹规划时要充分考虑其性能限制，一般要考虑以下5个方面的约束条件：

(1)航迹最小步长:无人机在飞行过程中，在改变飞行姿态机动前和机动后，无人机应保持一段距离的直飞状态，这个距离称为最小步长。多次改变飞行姿势容易增大导航误差，设li表示第i段航迹长度，lmin表示最小航迹段长度，该约束表示为：

li≥lmin(i=1，2，3…，n)

(5)

(2)最大转弯角：无人机的机动性能受到转弯角α的限制，该限制取决于飞行器的过载能力和飞行任务。新生成的航迹段只能在最大转弯角的范围内转弯。

图3 最大转弯角约束

(6)

(7)

(4)最小离地高度：无人机在飞行过程中，为了不被雷达或地空导弹威胁，应尽量贴地飞行，但如果离地面高度太小易发生撞地事件，因此要设定一个合适的最小离地高度[9]。设第i个航迹点[xi,yi,h(xi,yi)]，h(xi,yi)为第i个航迹点的飞行高度，Z(xi,yi)为地理模型的海拔高度，hmin为离地最小飞行高度，所以该约束可以表示为:

h(xi,yi)-Z(xi,yi)≥hmin

(8)

(5)航迹总长约束：无人机在飞行过程中受到耗油率和载油量的限制，必须要求飞行的总航程越小越好[10]，设dmax为最大航迹长度，等于1.5倍出发点到目标点的直线距离，所以航迹总长约束可以表示为：

(9)

(6)机动点数量:机动点的数量直接影响着航迹规划的精度，当精度要求较高时，可以增加机动点的数量，反之可以减少机动点的数量。机动点的数量增加较多时，会导致导航误差增大和计算时间延长。所以，需要根据具体的飞行任务要求来决定机动点的数量。

2.2 威胁代价函数

当无人机进行三维航迹规划时，实质上是一个多约束优化问题，本文对航迹规划威胁代价函数采用线性加权的指标方法[11]。

(10)

其中li表示第i段航迹的长度，hi表示第i段航迹的海拔高度，fLDi表示第i段航迹被雷达和导弹威胁代价，w1，w2，w3为权系数，w1+w2+w3=1，由w2/w1的大小来选择飞机是从上方飞越还是从障碍侧边绕过，w3/w1的大小决定让飞机直接穿越雷达威胁区还是绕过威胁区。

3 遗传模拟退火算法求解流程

遗传算法在航迹规划中得到了广泛的应用，遗传算法的选择、交叉和变异算子在搜索最佳的航迹路线时，能够以随机的方式得到寻求最优解，新一代的子群体主要是通过上一代父群体之间进行交叉重组产生的，容易得到全局最优解附近的局部最优解，所以，单纯的使用遗传算法容易导致早熟和陷入局部最优解，而模拟退火算法能够对遗传算法寻优过程进行扰动，具有摆脱局部最优解的能力，在交叉和变异过程中用Metropolis准则判断新解是否可以被接受，使用两者结合的遗传模拟退火算法能够有效的解决陷入局部最优解问题，从而得到全局最优解[4]。

设定种群规模M,最大遗传操作代数N，交叉概率pc，变异概率pm，初始温度T=T0,温度更新次数j=0，设定退火温度变化规律为Tj+1=0.9Tj，终止温度为Te。遗传模拟退火算法流程如图4所示：

4 仿真实验

为了验证模拟遗传退火算法的可靠性，对算法进行仿真实验，结合模拟地形图和威胁区模拟图，取最小步长lmin=2 km，最大转弯角α=450，最大俯仰角θ=300，最小离地高度hmin=0.05 km，取各权重系数w1=0.4，w2=0.4，w3=0.2，种群规模M=20，最大迭代操作代数N=80，交叉概率pc=0.4，变异概率pm=0.1，初始温度T=T0=100，终止温度Te=60，航线起始点坐标为(0，20)，目标点坐标(200，200)，仿真结果如图5-图7所示。

图4 遗传模拟退火算法流程图

图5 适应度曲线

迭代次数为51次，航迹总长3.372 6×105m，通过图6和图7可以看出，通过本文提出的遗传模拟退火算法，无人机能够有效的避开山体障碍和威胁区，并根据地形和适应度函数有效的选择最佳路径，最后能够得到满足无人机约束性能的航迹。

图6 航迹规划三维示意图

图7 航迹规划等高示意图

5 结论

本文首先建立数字地形和防空武器威胁区模型，给出代价函数，并对无人机飞行性能进行约束，本文提出的遗传模拟退火算法是将模拟退火算法中常用的Metropolis接受准则引入到遗传算法的交叉和变异过程中，这使得算法可以避免基本遗传算法陷入局部最优解，通过扰动跳出局部最优解，从而得到全局最优解，减少迭代次数并保证了算法的收敛性,在三维航迹规划快速搜索最佳路径领域有较好的应用前景。本文使用的算法在山峰和防空威胁区数量较少的情况下较适用，对于战场地形环境特别复杂和实时规避动态防空威胁区域的问题还需要进一步的研究。

[1]杨军，朱学平，朱苏朋，等.飞行器最优控制[M].北京：国防工业出版社，2011.

[2]Robert J Szcaerba J.Robust algorithm for real-time router planning[J].IEEE Transactions 0n Aerospace and Electronic System,2000，36(3):869-875.

[3]Kenneny J,Eberhart R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks,Perth,Western Australia,1995.

[4]巩敦卫，郝国生，周勇,等.交互式遗传算法原理及其应用[M].北京：国防工业出版社，2007.

[5]Krikpatrick S,Gelett C,Veechi M.Optimization by simulated annealing[J].Science,1983,200(8):671-680.

[6]Ioannis K Nikolos,Kimon P.Valavanis,Nikos C.Sourveloudis.Evolutionary algorithm based offline/online path panner for UAV nvigation[J].EE Transactions on Systems Man and Cybernetics,2003,33(6):898-912.

[7]刘娟.小型无人机地面站电子地图子系统研究与设计[D].呼和浩特：内蒙古工业大学，2009.

[8]张延松.基于遗传算法的无人机航迹规划研究[D].长沙：中南大学，2010.

[9]巴海涛.无人机航迹规划方法研究[D].西安：西北工业大学，2006.

[10]柳长安.无人机航路规划方法研究[D].西安：西北工业大学，2003.

[11]郑昌文，严平，丁明跃,等.飞行器航迹规划[M].北京：国防工业出版社,2008.

(责任编辑：宋丽萍 英文审校：刘敬钰)

UAVrouteplanningbasedonthegeneticsimulatedannealingalgorithm

QIU Fu-sheng，YANG Jian-ping，SHAO Xu-wei

Faculty of Aerospace Engineering，Shenyang Aerospace University，Shenyang 110136)

Path planning technology is one of the core technologies of UAV mission planning system.UAV flight space is large,which needs a method to quickly find out the best path.This paper sets up a digital map model and a model for air defense threat area in the airfield domain.Under the condition of meeting the UAV flight constraints,the paper provides a genetic simulated annealing algorithm for UAV track planning,and makes full use of the probability kick features of simulation degradation algorithm and powerful ability of fast searching genetic algorithm.Simulation results show that with this algorithm,UAV can automatically avoid the threatened field of simulated digital map area,search out a safe and effective path,and ensure the integrity and optimality of their routes.

UAV;route planning;genetic simulated annealing algorithm;threatened area

2013-11-05

邱福生(1977-)，男，江西于都人，副教授，主要研究方向：飞机系统设计与试验技术、飞行器设计与制造一体化(CAX集成技术/DFX)，E-mail:shenhangsau2011@sina.com。

2095-1248(2014)01-0016-04

V249.12

A

10.3969/j.issn.2095-1248.2014.01.004