韩 超 王 赢

(1.海军驻426厂军事代表室 大连 116005)(2.武汉数字工程研究所 武汉 430074)

一种基于改进PSO的无人机航路规划方法*

韩 超1王 赢2

(1.海军驻426厂军事代表室 大连 116005)(2.武汉数字工程研究所 武汉 430074)

针对无人机航路规划问题,提出了一种改进的粒子群的无人机航路规划方法。该方法将UAV的航路规划问题通过目标转换,形成一个考虑威胁优先,路径优化其次的单目标航路优化问题,并引入局部搜索改进粒子群算法求解该问题的收敛性。仿真结果证明了该方法对解决无人机的航路规划问题高效可行。

航路规划; 无人机; 粒子群算法; 局部搜索

ClassNumberTP391.9

1 引言

无人机(Uninhabited CombatAerial Vehicle,UAV)是当前国内外热门研究的武器装备,通常可进行自主任务控制或者由操作人员进行远程地面遥控进行使用,可执行空对空、空对地、空对海等多种作战任务。与传统的有人作战飞机相比,无人机具备多项优势,如:作战零伤亡、制空时间长、隐身性能好、战斗准备时间短、研发维护费用相对较低等。无人机的这些优势能缩短作战应用中的观察、定位、决策、行动周期,在针对敌方的高风险目标突防、防空系统能力压制、纵深目标攻击等多种作战中发挥多种独特的作用。由于无人机的这些显著优势,国内外越来越多重视其研究与发展,欧美国家都把军用UAV的发展置于优先地位,先后制定了UAV发展计划,投入了巨资开展UAV技术研究和作战应用原型验证,尤其是美国的UAV已进入作战实用阶段[1]。面对未来的多样化战争技术发展趋势,迫切需要我国发展UAV相关技术,为打赢未来信息化条件下非对称战争提供支撑。

无人机航路(航迹)规划是无人机作战使用中的重要部分。航路规划的目的是在限定的条件下,选择一条到达任务地点的最优或次优路径。无人机在进行作战使用时,首先对作战任务进行规划,确定完成任务的各个目标地点,航路规划则是通过分析各个目标地点之间的关系,寻找每两个目标地点之间的优选航路,在飞行过程中,还需要规避敌方防空火力、侦测雷达、地形等多种威胁源,以最大限度的保障飞行的可靠性。目前,已存在较多的航路规划算法,如A*算法、蚁群算法、遗传算法、粒子群算法等。特别是粒子群算法为代表的智能优化方法在应用于求解航路规划问题具备实现简单、优化效果好、运算速度快的优点,但是,运用智能优化算法求解航路规划问题也存在一些不足,如容易陷入局部最优,早熟收敛等问题。

UAV航路规划问题由于包含威胁、路径等多个目标,是一个典型的多目标优化问题。传统的粒子群算法[2]、遗传算法[3]、蚁群算法[4]等随机进化算法都是针对单目标问题而提出,无法直接应用于该类问题的求解。因此,在本文中将UAV的多目标优化问题通过目标转换,形成一个考虑威胁优先,路径优化其次的航路优化问题,采用了高效的粒子群算法对该问题进行求解,并引入混沌搜索对粒子群算法的收敛性提出改进,实现保证UAV飞行安全前提下的完成任务的可能性,以此提高UAV到达指定地点完成任务的效率。

2 UAV航路规划模型

2.1 UAV威胁模型

UAV所受到的威胁包括有防空火力、雷达、复杂的气候地形等。UAV在起飞后,通常保持一定的高度飞行。考虑到UAV的飞行高度通常较高,本文中不考虑地形和气候的影响,只考虑雷达的威胁。由于UAV反射雷达回波的强度与当前位置与雷达的距离的四次方成反比,因此,UAV的雷达威胁近似认为如式(1)所示[5]:

(1)

其中,Jthreat表示总威胁的大小,n为威胁的编号,li为航路位于第i个威胁范围内的长度,di(l)表示为航路上某一点与第i个威胁的距离。在仿真研究的过程中,通常简化为在该航段在威胁范围内划分为五段进行计算[5]。并作简化后得到式(2):

(2)

图1 UAV雷达威胁描述

在式(2)中,Li为UAV的航路位于第i个威胁区域的长度,d0.1,i、d0.3,i、d0.5,i、d0.7,i、d0.9,i分别为位于第i个威胁的UAV航路中为,位于0.1、0.3、0.5、0.7、0.9位置与第i个威胁的距离,无人机的威胁代价计算各变量描述如图1所示。ti表示第i个威胁的威胁权重。

2.2 威胁环境下的UAV航路规划模型

因为UAV的飞行速度通常在一定的较小范围内调整,UAV飞行的航路越长,UAV的燃油消耗越大,所以可以用航路的长度作为评价指标,以代替UAV的燃油消耗指标。UAV的燃油代价可描述为

Jfuel=L

(3)

由此可以得出考虑威胁环境下的UAV航迹规划模型,既要满足燃油的总消耗最小,亦要满足UAV受到的威胁最小。即:

(4)

3 粒子群算法描述

粒子群优化算法(Particle Swarm Optimization,PSO)是一种新型的进化计算技术,由Eberhart和Kennedy于1995年提出[6]。PSO算法已经被证明是一种有效的全局优化方法。在PSO算法中,粒子的位置代表被优化问题在搜索空间中的潜在解。所有的粒子都有一个被适应度函数决定的适应值,每个粒子还有一个速度决定它们飞翔的方向和距离。粒子们追随当前的最优粒子在解空间中搜索。PSO算法初始化为一群随机粒子(随机解),然后通过迭代找到最优解,在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:一个是粒子本身所找到的最优解,称为个体极值;另一个极值是整个粒子群目前找到的最优解,称为全局极值。基本思路依据如式(5)所示:

(5)

其中:i=1,2,…,m,m为粒子的个数;d=1,2,…,D,D为每个粒子的维数;xid为第i个粒子第d维的位置值;ω为非负数,称为惯性权值,其值较大有利于全局搜索最优,其值较小有利于最终结果的收敛;c1、c2为非负常数,称为加速因子,根据经验通常取c1=c2=2;rand(0,1)为介于0～1之间的随机数;Vi为第i个粒子的移动速度,Vid∈[-Vmax,Vmax],Vmax是常数,用以限制Vid的值。Vid为第i个粒子第d维的移动速度值;Vi为这一部分表示粒子有扩展搜索空间的趋势,即代表有全局搜索能力;pi为第i个粒子自身找到的最优值,它代表粒子具有记忆和认识能力。如果没有这一项c1×rand(0,1)×(pid-xid),在微粒的相互作用下,算法也有能力到达新的搜索空间,且它的收敛速度更快,但对复杂问题则容易陷入局部最优点;pg为所有粒子找到的最优值,它表示所有粒子具有信息共享的能力,如果没有这一项c2×rand(0,1)×(pgd-xid),相当于粒子个体间没有交互,一个规模为m个粒子的群体等价于运行了m个单个微粒的运行,因而得到解的几率非常小[7]。

PSO算法中粒子位置的迭代过程如图2所示。其中,xk为当前时刻某个粒子的位置(图中假设恰好位于原点);gbest为所有粒子经历的最优位置;pbest为该粒子经历的最优位置;Vk为该粒子当前时刻的速度;Vk+1为该粒子改进后的速度;xk+1为该粒子改进后的位置。可见,粒子改进后的位置更加靠近全局的最优位置。

图2 粒子位置迭代改进示意图

标准粒子群的算法流程如下:

步骤1:初始化一群粒子X={xi},i=1,2,…,m,其中m为粒子的个数,包括随机的粒子位置和速度;

步骤2:利用适应度函数计算每个粒子的适应值;

步骤3:对每个粒子,将其适应值与其经历过的最好位置pi作比较,如果较好则将其作为当前的最好位置pi;

步骤4:对每个粒子,将其适应值与全局所经历的最好位置pg作比较,如果较好,则重新设置pg的索引号;

步骤5:根据公式更新粒子的速度和位置;

步骤6:如未达到结束条件(通常为足够好的适应值或达到一个预设的最大迭代次数),则返回步骤2,得到最优粒子的位置。

4 算法实现

由于传统的粒子群算法只适用于单目标问题的求解,由于无人机航迹规划存在大量的个体比较操作,而无人机航迹规划问题同时包含了威胁和路径两种指标。通常情况下,可采用罚函数法来解决此类问题,通过惩罚因子将两种目标转换成单目标进而进行比较,但是罚函数在应用过程中需要反复试算,以确定惩罚因子,从而增加了实现的难度[9]。因此,针对无人机的航路规划问题提出一种优先考虑威胁,次考虑路径目标的比较方法,以保证无人机能够在最安全的前提条件下,以最优的路径到达目的地。

4.1 目标模型转换

本文考虑了一种威胁目标优先的模型转换方法,该方法作用于在两个或多个无人机航路规划方案中选择更优方案。该方法比较两个航路规划方案的过程描述如下:

1)若两套方案都超出了无人机的飞行最大航程限制。超出最大航程短的方案优于超出最大航程长的方案。

2)未超出最大航程的方案,优于超出最大航程约束的方案。

3)对于未超出最大航程的两个方案,威胁代价小的方案优于威胁代价大的方案;威胁代价相同的个体,总航程短的个体更优。

4.2 个体编码

由于无人机航路规划问题是一个三维路径,为简化计算采用最小威胁曲面方法,将三维规划空间映射到二维平面,在二维平面内对飞行路径点进行编码,然后根据得到二维航路曲线以最小威胁曲面对其进行相应的抬高调整,即可得到最终的三维航路规划方案[9]。因此,本文针对二维航路曲线进行编码,以求得无人机的二维航路曲线。由于二维平面内的无人机航迹规划,不考虑相应的高程信息与地形跟随,将包含N个航迹点的粒子个体X以及对应的速度V分别设计如下:

(6)

其中(xi,yi)为航迹中第i个的路径点;(x1,y1)为航迹的起点;(xN,yN)为航迹的终点;(Vxi,Vyi)表示粒子第i维的速度向量。将个体X中的各航迹点按照顺序连起来,即表示为一条带求的航路。

4.3 算法流程

针对无人机航路规划提出的粒子群算法流程如下:

步骤1:随机初始化种群、粒子群算法各参数。各粒子的历史最优解初始化为与自身相同、全局最优解初始化为当前种群中的最优解。置进化代数g=0。

步骤2:对种群进行进化。使用粒子群算法对群体空间每个粒子的速度和位置进行更新。对于个体Xi更新速度和位置的公式如式(7)所示:

(7)

步骤3:更新每个粒子的历史最优,还有种群的全局最优。

步骤4:判断是否启动局部搜索,若rand()>(1-ε),则选择当前搜索到的最优解进行局部搜索,否则转下一步。其中ε为用户定义局部搜索系数,表示进行局部搜索的概率。

步骤5:判断是否达到最大进化代数MaxGen,如果g≥MaxGen,输出当前最优解,算法结束,否则,g=g+1,转步骤2。

其中,为了增强算法的收敛效果,对粒子群算法的参数ω采用式(8)计算:

ω=(ωmax-ωmin)×e-β×Gen+ωmin

(8)

其中ωmax和ωmin是ω的初始权重和最终权重因子;Gen是当前的进化代数;β为常数,决定了ω随着进化代数的变化速度。在算法的计算初期,一个较大的ω使算法在一个大的范围内搜索,提高搜索的全局性,在算法的后期,较小的ω使算法能够在一个小范围内寻优,提高解的收敛精度。

4.4 局部搜索策略

在4.3节算法的计算流程中,为增强算法的搜索效果,提出一种局部搜索方法。该方法针对航路中的某个航迹点进行局部随机寻优。其原理如图3所示。

图3 局部搜索原理示意图

针对一个方案X的局部搜索具体过程描述如下:

步骤1:对第k维变量进行随机扰动,扰动的表达式如式(9)所示:

(9)

步骤2:评价得到的临时方案X′,其中:

(10)

步骤3:如果方案X′优于方案X,则令X=X′,局部搜索过程结束。否则,新重复循环步骤1和步骤2,若多次循环都无更优方案,也结束循环过程。

5 仿真结果与分析

为了验证提出算法的可行性与有效性,采用如下航迹规划模型进行仿真[10]:

无人机起点为(11,11),目标点位(75,75)。中间包含一系列的威胁,威胁的数据如表1所示。

表1 威胁数据

在Intel E4600 CPU、Windows XP、JAVA环境下,采用提出的算法求解该仿真应用运行结果如图4所示。

图4 算法求解航迹规划问题结果

算法求得的最短路径为96,威胁已经全部避开,算法的计算耗时为0.12s,该算法不仅能够在有效的时间范围内取得优秀解,所求得的无人机航路结果中,无人机航路还避开了全部威胁源,并找到了优化的路径。充分证明了该方法求解无人机航迹规划问题的可行性与高效性。

6 结语

本文提出了一种适用于无人机航路规划问题的改进粒子群优化算法,该方法采用了高效的粒子群算法对该问题进行求解,将UAV的航路规划问题通过目标转换,形成一个考虑威胁优先,路径优化其次的航路优化问题,并引入混沌搜索对粒子群算法的收敛性提出改进,仿真结果表明提出的方法容易实行,求解效率高,能够保证UAV的完成任务的安全性,并提高UAV的作战效率。

[1]柳煌,夏学知.无人机航路规划[J].舰船电子工程,2008,28(5):47-51.

[2]单敏瑜,刘以安,倪天权.QPSO在无人机侦察航路规划中的应用研究[J].计算机工程与设计,2009,30(20):4690-4692.

[3]马云红,周德云.基于遗传算法的无人机航路规划[J].电光与控制,2005,12(5):24-27.

[4]孟祥恒,王社伟,陶军.基于改进蚁群算法的多无人机航路规划研究[J].计算机仿真,2008,25(11):56-59.

[5]叶文,范洪达,朱爱红.无人飞行器任务规划[M].北京:国防工业出版社,2011:27-29.

[6]Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE Press,1995:1942-1948.

[7]吴钦,许晓飞,张晶炜,等.粒子群算法在巡航导弹航路规划中的应用[J].舰船电子工程,2010,30(11):18-20.

[8]Ying Wang, Jianzhong Zhou, Hui Qin, et al. Improved Chaotic Particle Swarm Optimization Algorithm for Dynamic Economic Dispatch Problem with Valve-Point Effects[J]. Energy Conversion and Management,2010,51(12):2893-2900.

[9]唐上钦,黄长强,胡杰,等.基于威胁等效和改进PSO算法的UCAV实时航路规划方法[J].系统工程与电子技术,2010,32(8):1706-1710.

[10]Chunfang Xu, Haibin Duan, Fang Liu. Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle(UAV)path planning[J]. Aerospace Science and Technology,2010(14):535-541.

PathPlanningofUAVBasedonAnImprovedPSOAlgorithm

HAN Chao1WANG Ying2

(1. Military Representative Office of Navy in No.426 Factory, Dalian 116005)

(2. Wuhan Digital Engineering Institute, Wuhan 430074)

Focus on the path planning problem of UAV, an improved particle swarm optimization algorithm is proposed in this paper. This method transforms the multi-object problem to a single one, which takes the threat-object in consideration firstly, then, the length of flying route. What’s more, a local search is imported to improve the convergence of proposed algorithm. Finally, the high efficiency and feasibility of proposed algorithm is proved by the simulation result.

path planning, UAV, particle swarm optimization algorithm, local search

2013年10月5日,

:2013年11月25日

韩超,男,工程师,研究方向:指控装备应用。王赢,男,工程师,研究方向:指控装备运用。

TP391.9DOI:10.3969/j.issn1672-9730.2014.04.015