基于改进人工蜂群算法的无人机实时航迹规划

张洛兵, 徐流沙, 吴梅

(1.中国航空工业集团公司 防务工程部, 北京 100022;2.西北工业大学 自动化学院, 陕西 西安 710072)

基于改进人工蜂群算法的无人机实时航迹规划

张洛兵1, 徐流沙2, 吴梅2

(1.中国航空工业集团公司 防务工程部, 北京 100022;
2.西北工业大学 自动化学院, 陕西 西安 710072)

为了适应现代战争战场环境的复杂性,针对所建立的突发威胁模型,提出了一种基于改进人工蜂群算法的无人机航迹规划方法,对无人机进行动态航迹寻优,并通过MATLAB进行了仿真验证。仿真结果表明,所设计的方法能够根据实时出现的威胁状况进行动态航迹规划、评价和选优,同时满足实时性要求。

人工蜂群算法; 航迹规划; 无人机

0 引言

航迹规划是根据地形、天气和威胁等信息,寻找飞行器从起始点到目标点之间最优运行轨迹的新一代低空突防技术[1]。因此无人飞行器飞行前,一般会根据其飞行性能、任务和已获得的威胁信息,设计多条离线飞行航迹。一般情况下,在没有遇到突发威胁或改变执行任务的情况下,无人机会按照规划好的离线航迹飞行。然而随着现代战争复杂性的增强,传统的航迹规划算法已不能满足高复杂度战场环境的需求,动态航迹规划已成为提高飞行器环境适应性和生存能力的重要方法。该方法应尽可能地依靠机载计算机,实时、高效地在线规划出较优的航迹,以规避突发的威胁状况,从而使其具备对突发威胁的自主决策能力。因此,研究面向突发威胁的实时航迹规划,对提高无人飞行器的战场生存能力具有非常重要的价值。

人工蜂群(Artificial Bee Colony,ABC)算法是一种基于群体智能理论[2]的全局优化算法,已经在函数优化组合优化和工程领域得到了大量的应用。人工蜂群是在2005年由Karaboga[2]基于蜂群的智能采蜜行为及自治、分工和自组织模型提出的。在人工蜂群算法中,人工蜂群由三部分组成:采蜜蜂、侦察蜂和跟随蜂。蜜源的位置代表优化问题的可行解,蜜源质量对应于该解的优劣,通常用一个适应度函数来评价。目前ABC算法作为一种新的随机优化算法,在接近全局最优解时,仍存在搜索速度变慢、过早收敛、个体多样性减少,甚至陷入局部最优解等难题。

本文提出了一种改进人工蜂群算法,并应用于无人机实时航迹规划中,同时提出了航迹点“势能”概念,使得各个航迹点的“搜索优先级”存在差异。基于这种差异,改进ABC算法中采蜜蜂采蜜的方式,从而在无人机实时航迹规划过程中,在不增加搜索时间的基础上,规划出全局较优的航迹。最后,通过仿真试验验证了改进算法的有效性。

1 威胁模型

航迹规划需要回避一些禁飞区域和威胁区域,而各种威胁模型简化为具有一定形状的几何体组合,可以降低规划的复杂度。然后以适当的地形覆盖威胁或障碍的作用区域,则可把威胁障碍模型等效为相应的地形模型。在实际应用中,可以建立一个表来单独记录这些不确定因素,以便当环境发生改变时,及时更新规划环境,以满足实时性要求。

1.1 禁飞区

禁飞区(No-fly Zone)指某地上空禁止任何未经特别申请许可的航空器(包括飞机、直升机、热气球等)飞入或飞越的空域。将禁飞区建为圆柱体或长方体地形,并赋予一个较大高程值,表示若无人机从该区域通过,将要付出很高的“高度代价”。将圆形禁飞区表示为(x,y,R),矩形禁飞区表示为(a,b,c,d),其三维模型如图1所示。

图1 禁飞区三维图Fig.1 3D no-fly zone

1.2 地形因素

本文引入地形作为威胁。在无人机飞行过程中,地形因素对无人机造成的影响主要有两方面:一方面对无人机的飞行安全带来严重威胁,增大碰撞概率;另一方面,回避地形的同时,也可实现地形遮蔽,减小被敌方防空武器发现的概率。对飞行区域中某些陡峭的山峰单独处理,用二维高斯分布来对孤立山峰进行模拟,数学表达式为:

(1)

式中:(x,y)为水平投影面的坐标;hmi(x,y)为该点的地形高度;Hi为山峰最高点的高度;pi,qi分别为山峰沿x轴和y轴方向与坡度相关的量,控制山峰的范围,其值越小山峰越陡峭,其值越大山峰越平坦;(x0i,y0i)为山峰中心位置。

当有多个山峰时,则山峰地形表示为:

(2)

式中:i为山峰的个数。图2为山峰的三维模拟。

图2 山峰三维模拟Fig.2 3D simulation of mountain

1.3 雷达威胁

在航迹规划时面临的主要威胁是雷达[3],分为预警雷达和火控雷达。预警雷达通过防空系统将探测到的目标数据传送给火控雷达,然后火控雷达根据这些数据跟踪和锁定目标,之后火力系统才能打击目标。因此,避开敌方的雷达探测区域是无人机航迹规划中的重要因素之一。

设雷达的最大作用范围为Rm,且雷达位置(xr,yr,hr)固定,则无人机在某一位置(x,y,h)时受雷达的威胁可量化为:

(3)

其中:

式中:KR为威胁系数。而无人机在安全曲面上飞行,即有h=hs(x,y),所以式(3)只与(x,y)有关。考虑到无人机从进入雷达区域到距雷达很近这段过程,不被发现的概率很小,且突防中也需要与雷达探测区域保持一段安全距离,因此可采用如下等效高程:

(4)

式中:a<1,如取为0.5;b>1,如取为1.1;HR为一很大常值。三维等效高程如图3所示。

图3 雷达等效高程Fig.3 Radar equivalent elevation

2 基于改进人工蜂群算法的航迹规划

2.1 算法改进

2．1．1 初始蜜源生成

为了加快实时航迹规划的收敛速度,加入离线规划出的最优蜜源,即无人机的参考航迹。由于离线规划的最终蜜源群仍含有丰富的模式,因此可以直接引用为初始蜜源。

初始蜜源的生成采取小区间生成法:先将第j(j=1,2,…,D)个参数的取值范围分成蜜源总数NP个等值小区间,分别记作I1j,I2j,…,INPj,再生成一个NP×D矩阵E={eij},其中E的每列为1,2,…,NP的随机排列,则第i个蜜源的各个参数分别在小区间Iiei1,Iiei2,…,IieiD中随机生成,如这样生成的初始个体将会均匀地分布在整个解空间上,保证了初始群体含有较丰富的模式,增强了搜索收敛于全局最优点的可能。

2．1．2 选择机制

ABC算法中,跟随蜂是以轮盘赌的机制选择蜜源,这是一种基于贪婪策略的选择方式,会使种群多样性降低,从而引起过早收敛和提前停滞的现象。

对于一处蜜源(航迹),采蜜蜂负责局部搜索,采蜜时随机生成要改变的蜜源分量(航迹点),根据上文所述的思想,可以对每一个分量(航迹点)赋一个权值,采蜜蜂依据这些权值来决定要改变的蜜源分量,就像跟随蜂选择要开采的蜜源一样。为此,引入人工势场的思想,设想威胁源中心为一斥力源,航迹点离威胁源越近,所受斥力就越大,航迹点“势能”也就越大,因此越容易被“改变”。设航迹点Pk+i(i=1,2,…,D-k)到威胁源中心的距离为Ri,则“势能”为:

(5)

按轮盘赌原则,被改变的概率为:

(6)

之后,采蜜蜂按概率选择要改变的分量。

2．1．3 侦察蜂寻找新的蜜源

引入差分进化法的变异和交叉操作寻找新的蜜源,差分进化(Differential Evolution,DE)算法是一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法。DE的原理简单、受控参数少,实施随机、并行、直接的全局搜索,易于理解和实现。算法的基本思想是:对当前种群进行变异和交叉操作,产生另一个新种群;然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择,从而产生最终的新一代种群。

(1)变异操作

为加速收敛,在变异操作中,选择全局最优蜜源Xbest作为父代基向量,即

(7)

式中:Vi=(vi1,vi2,…,viD),i=1,2,…,NP,D为优化参数;Xbest为当前全局最佳蜜源;F为缩放比因子;(Xr2-Xr3)为父代差分向量;参数r1,r2,r3∈{1,2,…,NP}互异且不等于i[4]。

(2)交叉操作

将Xi与Vi交叉产生子代个体Ui=(ui1,ui2,…,uiD)。为保证第i个蜜源的演化,首先通过随机选择使得Ui至少有一位由Vi贡献,而对其他位,可利用一个交叉概率因子CR∈[0,1]决定Ui中哪些位由Xi贡献,哪些位由Vi贡献。如果rand

(8)

式中,rand(j)为[0,1]之间的均匀分布随机数;rnbr(i)为(i=1,2,…,D)之间的随机量。

最后,将Ui替代Xi成为第i个蜜源进入下一次循环,并更新相应蜜源质量信息。

2.2 航迹规划的约束条件

由于无人机有自身特殊的物理限制和使用要求,所以其航迹规划不同于路面机器人的路径规划,还需要满足一定的航迹基本约束条件。无人机受到的约束条件很多,包括飞行环境、自身的物理性能及战术要求等。在构造航迹规划地图时引入安全曲面的概念,利用无人机的纵向约束(最大爬升/俯冲角、法向过载和最小离地飞行高度)构造安全曲面,水平方向要考虑的约束[5]主要有:最大航程、最小转弯半径。

2．2．1 最大航程

(9)

2．2．2 最小转弯半径

要实现规划的航迹可飞,必须满足最小转弯半径。半径越小,转弯曲率越大,将导致过载过大。转弯半径如图4所示。

图4 转弯半径Fig.4 Turning radius

规划航迹由航迹点组成,采用不过点的航迹点转换控制飞行方式,当无人机距Pk的距离为Lc时,开始匀速水平转弯。则有:

(10)

式中：φk为Pk处的转弯角。因此,只需控制Lc和φk的大小,则可满足最小转弯半径条件,即与最小水平航迹段长度和最大转弯角有关。转换控制应依据飞行控制系统控制律计算结果确定,由导航计算机给出。

2.3 目标函数

2.3.1 威胁代价

无人机在空间中的点x处受第j个威胁的影响指数主要与无人机和威胁间的距离dxj有关,具体计算可采用如下公式:

(11)

式中:Kj为反映第j个威胁的强度参数,默认为1;a>1;b>1。将规划空间相对于威胁j划分成三个区域:危险区、次安全区和安全区。

要计算第i段航迹的威胁指数需沿第i段进行积分。为了减少计算量,只计算该段航迹若干个点威胁指数的平均值,再乘以该航迹段的长度。则:

式中:Nthr为已知威胁源的个数;li/6为第i段航迹的1/6处,如图5所示。

图5 航迹威胁示意图Fig.5 Route threat

2.3.2 油耗代价

假设无人机飞行速度为常值,则油耗可简单地认为与航迹长度成正比。

2.3.3 转弯代价

为限制转弯角过大,需要在代价函数中加入对转弯角的惩罚项,航迹点Pi处的转弯角为:

(12)

当φi大于水平转弯角φ时,做出惩罚。只考虑转弯代价的情况下,有：

(13)

式中:k3为惩罚因子,设为10。因此转弯角代价为:

(14)

综合以上,目标函数为:

(15)

航迹规划问题的数学描述即为:

当无人机的机载雷达在参考航迹周围探测到威胁和障碍,就需要不断地更新地图信息并重新规划一条航迹。在线航迹规划需要充分利用离线航迹规划的结果,应用局部再规划将新终点后的离线航迹引用过来,与规划出来的局部航迹相组合,作为无人机的当前航迹,因此实时规划时间更少,能够满足实时性要求。

3 仿真算例及结果分析

采用Global Mapping软件截取秦岭一块90 km×

90 km的规划区域,设置横向与纵向采样间隔为100 m×100 m,保存为.tif格式,通过MATLAB读取并显示。为方便计算,将该数字高程模型(Digital Elevation Model,DEM)减去最低采样高度,基准海拔为0。原始数字高程如图6所示。

图6 原始数字高程Fig.6 3D original elevation

依据航迹规划参数,对无人机设定了飞行约束条件和威胁源,并基于ABC算法完成离线航迹优化,优化轨迹如图7所示。

图7 离线航迹优化Fig.7 Route optimization off-line

(1)起始点

起点S:(0, 0, 1.7) km;

目标点G:(90,90,0.6) km。

(2)无人机约束条件

最小水平航迹段长度3 km;最大转弯角60°;最大爬升俯冲角30°;最小离地距离100 m;最大航迹长度250 km。

(3)威胁参数

①禁飞区

矩形1:(20, 10, 40, 20) km,等效高度5 km;

矩形2:(70, 65, 85, 75) km,等效高度5 km;

圆形1:中心(20, 20) km,半径8 km。

②等效山峰

山峰1:中心(30, 50) km,a1=b1=5 km,H1=6 km;山峰2:中心(60, 15) km,a2=b2=4 km,H2=6 km。

③雷达

a=0.5,b=1.1,HR=5 km,Rm=100 m;

雷达1:中心(60, 50) km;

雷达2:中心(40, 75) km。

(4)ABC算法参数

控制参数为SN=30,Limit=30,MCN=2 500,由于航迹代价都为正值,则可令适应度值为:

fit(X)=1/J(X)

(16)

DE参数F=0.5,CR=0.8。

当无人机遇到突发威胁时,应用改进的ABC算法进行实时航迹再规划。迭代100次,运行时间在5.5 s左右。仿真结果如图8、图9所示。

图9 收敛趋势Fig.9 Convergent tendency

从图8可以看出,在线航迹规划在充分利用离线航迹规划计算结果的基础上,可以对实时出现的威胁快速计算出新的航迹。图中，虚线为修正航迹,在参考航迹基础上,除了在突发威胁附近外,还在其他区域都有些小修正,计算时间短,规划的航迹有效地避开了新出现的威胁,验证了算法的有效性。

4 结束语

本文提出了航迹点“势能”概念,使得各个航迹点的“搜索优先级”存在差异,基于这种差异,改进了ABC算法中采蜜蜂采蜜的方式。改进后的ABC算法搜索效率大大提高,与局部重规划相比,在不增加搜索时间的基础上,能规划出全局较优的航迹。

[1] 杜萍,杨春.飞行器航迹规划算法综述[J].飞行力学,2005,23(2):10-14.

[2] Karaboga D.An idea based on honey bee swarm for numerical optimization [R].Kayseri:Computer Engineering Department,Engineering Faculty Erciyes University,

2005.

[3] 郝震,张健,朱凡,等.雷达威胁环境下的无人机三维航迹规划 [J].飞行力学,2010,28 (1):47-52.

[4] 谢晓锋,张文俊,张国瑞,等.差异演化的实验研究 [J].控制与决策,2004,19(1):49-52.

[5] Szczerba R J,Galkowski P,Glicktein I,et al.Robust algorithm for real-time route planning [J].Aerospace and Electronic Systems,IEEE Transactions on,2000,36(3):869-878.

(编辑：李怡)

Real-time route planning of UAV based on improved ABC algorithm

ZHANG Luo-bing1, XU Liu-sha2, WU Mei2

(1.Department of Defense Engineering, AVIC, Beijing 100022;2.School of Automation, NWPU, Xi’an 710072, China)

In order to adapt to the complex nature of modern warfare battlefield environment, for the unexpected threat model established, a UAV flight route planning method based on improved artificial bee colony(ABC)algorithm was put forward for optimization of dynamic trajectory of UAV. The method was simulated with MALTAB. Simulation results show that this method can be used to dynamically perform dynamic flight route planning, evaluation and optimization of the emerging threats based on real-time status, and it can meet the real-time requirements.

artificial bee colony algorithm; route planning; unmanned aerial vehicle

2014-05-19;

2014-11-10;

时间:2014-11-18 16:57

张洛兵(1967-)，男，山西高平人，工程师，硕士，主要从事工程管理研究。

V279; V249.1

A

1002-0853(2015)01-0038-05