基于改进狼群算法的无人直升机航迹规划

王黎文, 邵书义, 吴庆宪, 韩增亮

(南京航空航天大学自动化学院, 江苏 南京 211106)

0 引 言

由于无人直升机(unmanned autonomous helicopter,UAH)具有垂直起降、空中悬停、可朝任意方向飞行、起飞着陆场地小、体积小且操作灵活等诸多优势,在侦查、打击、追踪、目标截获、大气监测、电力监控等军用、民用领域得到了广泛应用[1]。UAH航迹规划,是指在复杂地理环境的地形起伏和障碍物威胁严重影响UAH执行侦查任务的效率以及飞行安全问题的情况下,综合考虑飞行器飞行距离、高度、油耗及区域威胁等因素,结合自身性能约束,为UAH规划一条从初始位置到任务目标点位置的最满意的航路[2]。

UAH三维离线航迹规划问题,本质上是一个多约束多峰高维的最优化问题求解,因此在求解UAH航迹规划的过程中,群智能算法得到了广泛应用[3]。针对航迹规划问题,大量文献对多种群智能算法进行了深入研究,有传统的遗传(genetic algorithm,GA)算法[4-5]、粒子群优化(particle swarm optimization,PSO)算法[6-7]、蚁群算法[8-9]等,还有近些年提出的人工蜂群算法[10-11]、灰狼算法[12]、蝙蝠算法[13]等,这些算法各有优势和不足。利用传统群智能算法搜索UAH最优路径,最突出的缺点是复杂地理环境下的航迹规划问题,算法本身易陷入局部最优解,收敛过早,导致算法全局寻优能力不足,使得最后规划出的航迹达不到最优解的情况[14-16]。很多文献也针对上述问题提出了相应的改进方法,文献[17]引入模拟退火算法结合传统遗传算法,同时采用非线性自适应调节交叉算子和遗传算子的概率,避免传统遗传算法搜索过程易陷入局部最优解的问题,提高了传统遗传算法的全局寻优能力;文献[18]通过在传统粒子群算法的初始阶段、算法处理过程中以及迭代选取的最大值附近分别引入混沌序列、正弦函数和混沌算法,避免了算法陷入局部最优解的情况,提高了算法的整体寻优能力;文献[19]在新的启发函数中引入方向性因子,同时设计具有自适应调整的信息素挥发因子和改进的信息素更新规则,提高了传统蚁群算法的精度,不仅可以提高算法全局寻优能力,而且加快了算法后期的运行效率。上述改进能够在一定程度上提高算法的全局搜索能力和规划效率,但也受限于传统算法本身的特性。

狼群算法(wolf pack algorithm, WPA)[20-21]源于对狼群生态和狼群群体行为的研究,受狼群捕猎行为及猎物分配方式启发,模拟出游走、召唤和围攻3种智能行为,及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制,以完成在复杂空间中的寻优,具有较好的全局规划能力,在航迹规划方向有着广阔的前景。本文在利用WPA求解UAH航迹规划问题的基础上,主要完成的工作包括以下几点:①首先针对传统WPA中3种智能行为中移动步长固定及游走方向数人为确定不变导致的算法收敛速度慢、收敛精度不高的缺点,提出自适应步长的动态调整方法,使得每只狼的移动步长可以依靠当前狼与头狼位置之间的距离动态调整移动步长;②其次,针对游走行为,提出了基于莱维飞行与变方向自适应游走相结合的搜索策略,改善算法易陷入局部最优的问题,保证了狼群搜索的覆盖性,提高了算法收敛速度和全局寻优能力;③最后,将改进WPA用于求解UAH三维航迹规划问题,在三维模拟环境下验证了改进WPA在UAH航迹规划方面的有效性和优越性。

1 UAH三维航迹规划模型

1.1 环境建模

UAH航迹规划需要从环境模型中获取相关信息,良好的地形环境建模能够有效提高航迹规划的效率。本文航路规划任务环境建模包括基准地形建模、障碍区域建模及雷达威胁区域建模。

任务空间建模设置飞行区域为100 km×100 km×10 km的直角坐标区域,基准地形采用山峰函数模型[22]模拟建模,山峰函数模型的数学描述为

(1)

式中:(xk,yk)是第k个山峰的中心坐标;hk表示第k个山峰的高度;xok和yok分别表示山峰沿x轴和y轴的衰减量,主要控制山峰的坡度。

障碍区域一般是指任务环境中禁飞区、恶劣天气区域等UAH无法穿越的区域,障碍区域建模可以通过圆柱体模型[23]模拟,圆柱体模型的数学描述为

(2)

式中:Li(x,y,z)表示第i个障碍区域;(xi,yi)表示第i个障碍区域的中心坐标;RLi、hi分别表示第i个障碍区域的半径和高度。

威胁区域一般是指电磁干扰区域、敌方火力打击区域和敌方雷达探测区域等,威胁区域建模可以通过半球体模型[23]模拟建模,本文选用敌方雷达探测区域作为威胁区域,半球体的数学描述为

(3)

式中:Wi(x,y,z)表示第i个雷达威胁区域;(xi,yi,zi)表示第i个雷达区域的中心坐标;RWi表示第i个雷达探测范围半径。

综上所述,建模效果图如图1所示。其中DEM (digi-tal elevation model)表示数字高程模型,DEM.z表示DEM中对应(x,y)处的地面地形高度。

图1 空间环境建模Fig.1 Space environment model

1.2 航路约束条件建模

提出航路约束条件的目的是为UAH规划出可飞路径,基于UAH自身性能限制以及地形环境约束,UAH的航路规划需要满足一系列的约束条件,本文主要考虑以下约束条件:最小离地高度约束、最大转弯角约束、最大爬升角度约束、最短航迹段约束和边界约束。

(1)最小离地高度约束。UAH在执行任务时,为了避免与基准地形发生碰撞,UAH的飞行高度应该始终高于地形高度,同时应该与基准地形预留足够的安全距离,即

Hmin≥DEM.zi(xi,yi)+hmin

(4)

式中:Hmin表示UAH离地最小高度;DEM.zi(xi,yi)表示位置(xi,yi)处的基础地形高度;hmin表示UAH与基础地形预留的安全距离。

(2)最大转弯角约束。考虑此约束条件是为了避免UAH在飞行速度较快时,为避开障碍或威胁区域而需要大角度转弯时造成UAH不稳定甚至与障碍发生碰撞,故需要对UAH在水平范围内的最大转弯角度做出限制,即

(5)

(3)最大爬升角度约束。由于UAH具有可垂直起降的特性,对于UAH的航路规划,在起飞与着陆阶段不必考虑爬升或下降的角度约束,而在飞行过程中考虑这一约束,旨在使选取的相邻航迹点相对高度适中,从而使规划出来的航迹相对平滑,提高航迹的适航性。即

(6)

式中:|zi-zi-1|表示第i段航迹的高度差;ai表示第i段航迹的水平投影长度,i=1,2,…,n;θmax表示UAH规定的最大爬升角度。

(4)最短航迹段约束。最短航迹段定义为UAH在飞行过程中保持当前飞行姿态飞行的最短距离,为了避免因频繁改变飞行姿态而造成UAH不稳定甚至失控,UAH的航路需满足最短航迹段约束,即

li≥lmin

(7)

式中:li表示第i段航迹的长度;lmin表示最短航迹段距离。

(5)边界约束。为了提高UAH航路规划效率,同时降低航路代价,规定UAH需要在指定区域内工作,即

(8)

式中:i=1,2,…,n;(xi,yi,zi)表示第i个航迹点在三维空间中的坐标位置;(xmax,ymax,zmax)表示指定区域的边界位置;hmin(DEM.z)表示基准地形的最低高度。

1.3 适应度函数建模

在UAH航路规划过程中,可以通过适应度函数计算航路代价,用于比较选取的航迹点的优劣。对于可选择的航迹点,本文综合考虑了UAH航程、障碍区域以及雷达威胁这3项因素,适应度函数可表示为

F=ω1fL+ω2fT+ω3fC

(9)

式中:F表示UAH航迹总代价;fL表示UAH航程成本;fT表示障碍区域碰撞成本;fC表示雷达区域威胁成本;ω1、ω2和ω3为常数,表示不同成本权重值,各项权重的取值与UAH执行的具体飞行任务有关。

1.3.1 航程成本

航程成本决定于UAH从起点到终点的飞行距离,航程成本是评价航迹质量的最重要的指标之一。考虑到UAH自身携带的燃料有限以及侦查任务需求,UAH需要尽快到达目标点,航迹越短,UAH的耗时及耗能越少。假设总航迹由N个航迹点组成,那么航程成本可以表示为

(10)

式中:(xi,yi,zi)和(xi+1,yi+1,zi+1)分别表示第i个航迹点与相邻下一节点的三维坐标。

1.3.2 障碍区域碰撞成本

障碍区域碰撞成本。主要考虑UAH在执行任务过程中的山峰威胁、禁飞区及恶劣天气区域等UAH无法直接穿越的区域。为使规划出的航迹满足需求,规划的航迹节点需要与障碍区域保持一定距离,障碍区域碰撞成本可以表示为

(11)

(12)

(13)

式中:N和T分别表示航迹节点数和障碍区域数;TDi表示第i个航迹节点的碰撞成本;Di,j和RLj分别表示第i个航迹节点到第j个障碍中心的距离和障碍区域半径;lmin表示航迹节点距离障碍区域的最小安全距离;(xi,yi,zi)和DEM.zi分别表示第i个航迹节点的三维坐标和对应第i个航迹点的基础地形山峰高度;(xj,z,yj,z,zi)表示位于障碍区域中轴线上的与第i个航迹点同等高度的障碍中心坐标;MT表示足够大的常数。

1.3.3 雷达区域威胁成本

雷达区域威胁成本。UAH在执行任务时,若进入雷达探测范围,易被敌方发现,甚至遭受敌方火力打击,故UAH需要与雷达探测区域保持一定距离,威胁成本可以表示为

(14)

(15)

(16)

式中:N和R分别表示航迹节点数和雷达区域数;Tci表示第i个航迹节点的威胁成本;Ci,l和RWl分别表示第i个航迹节点到第l个雷达中心的距离和雷达探测半径;lmin表示航迹节点距离雷达探测区域的最小安全距离;(xi,yi,zi)分别表示第i个航迹节点的三维坐标;Nc表示足够大的常数。

2 基于改进WPA的UAH航迹规划

2.1 基本WPA

根据不同职能分工,狼群可分为头狼、探狼和猛狼3种。对于“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制[20]不作具体阐述,本文主要针对狼群捕猎过程中的3种智能行为展开介绍。

假设狼群的捕猎空间为一个N×D的可行解空间,其中N表示狼群数量,D表示待寻优的维数。某一匹狼的位置定义为Xi=(xi1,xi2,…,xiD),其中xiD为第i匹狼在待寻优的第d(d=1,2,…,D)维变量空间中所处的位置,相应的目标适应度函数值记为Yi;头狼的位置定义为Xlead=(xlead1,xlead2,…,xleadD),目标适应度函数值记为Ylead。则3种智能行为描述如下:

(17)

同时,探狼i朝着目标适应度值大于当前位置的方向前进一步,并对探狼i的状态Xi进行更新。重复以上游走行为,直到探狼的目标适应度值Yi大于Ylead或达到最大游走次数,结束当前游走行为。

(18)

奔袭途中,若猛狼j感知到的目标适应度值Yi>Ylead,则Ylead=Yi,此时猛狼j代替头狼发起召唤行为;若Yi

(19)

式中:ω表示距离判定因子;Md、md分别表示待寻优的第d维变量空间的最大值和最小值。

(20)

式中:λ表示[-1,1]间均匀分布的随机数。

(21)

式中:C表示步长因子,代表狼群在解空间中搜索的精细程度。

2.2 改进WPA

本文采用自适应步长为

step=rand×‖xi-Xlead‖2

(22)

式中:rand表示[0,1]之间的随机数。自适应步长依靠当前狼和头狼的位置信息作出自适应调整,当狼远离头狼位置时,以较大步长快速逼近头狼;当狼靠近头狼位置时,以较小步长缓慢逼近头狼,提高了算法的收敛速度。

2.2.1 基于莱维飞行和变方向的自适应游走行为

莱维飞行[25-26]是服从莱维分布的一种随机搜索方法,是一种短距离和长距离相间混合的搜索方式,具有较好的全局搜索能力。莱维飞行的位置更新公式为

(23)

(24)

式中:μ和v服从正态分布,定义如下:

(25)

式中:Γ表示伽马函数;γ通常取值为1.5。

对莱维飞行策略进行仿真实验,起始位置位于(0,0),仿真步长为1 000,仿真结果如图2所示。从图2可以看出,莱维飞行策略本身的特殊位置更新方式,使得其具有搜索的随机性和更广的搜索范围,这在一定程度上提高了算法的全局寻优能力和避免了算法陷入局部最优的情况。

图2 莱维飞行策略仿真图Fig.2 Simulation diagram of Levy flight strategy

只采用莱维飞行策略虽然有助于提高算法的搜索范围,以改善算法陷入局部最优的问题,但是其短距离和偶尔长距离相间的位置更新方式会造成算法整体收敛速度较慢,影响航迹规划的效率。由此将变方向的自适应游走行为与莱维飞行相结合,以帮助莱维飞行策略在提高全局搜索能力的同时,提高算法的收敛速度。具体变方向游走策略如图3所示。

图3 变方向游走策略示意图Fig.3 Schematic diagram of changing direction migration strategy

依据上述策略,规定当游走次数为奇数次时,探狼i向第p(p=1,2,…,h)个方向前进后,探狼i的位置表示为

(26)

当游走次数为偶数次时,探狼i向第p(p=1,2,…,h,h+1)个方向前进后,探狼i的位置表示为

(27)

依据上述游走行为位置更新公式,探狼按照游走次数的奇偶,搜索方向在h和h+1之间变动,丰富了算法搜索范围,莱维飞行策略和变游走方向的结合使得算法具有出色的全局搜索能力。同时,自适应步长使得当前狼的前进步长依靠其与头狼的距离动态调整,弥补了莱维飞行策略收敛速度慢的缺陷。

2.2.2 自适应召唤行为

传统WPA中头狼召集距离头狼最近的M_num匹猛狼向头狼位置奔袭,经过多次迭代之后,头狼的位置不断更替,如果只召集头狼位置附近的猛狼,易使算法陷入局部最优。针对上述缺点,本文在自适应召唤行为中随机选取除头狼的M_num匹狼作为猛狼,通过头狼召唤以自适应步长向头狼所在位置奔袭。则猛狼j经历第k+1次迭代时在第d维空间所处的位置为

(28)

2.2.3 自适应围攻行为

(29)

2.3 算法描述

UAH的航迹可以定义为一系列三维空间位置点的集合P={Pstart,P1,P2,…,Pn,Pgoal},Pstart和Pgoal分别表示UAH的起始点和目标点,Pi=(xi,yi,zi)(i=1,2,…,n)为中间航迹点。将UAH航路上的航迹点Pi作为人工狼在d维空间上的位置信息,则基于改进WPA的UAH航迹规划具体步骤为:

步骤 1根据第1.1节内容创建三维环境,并设置UAH的起点和目标点。

步骤 2参数初始化。初始化狼群中狼的位置xi及种群数目N,最大迭代次数Kmax,探狼的比例因子α,最大游走次数Tmax,距离判定因子ω,种群更新比例因子β(参数具体描述详见文献[20,28])。

步骤 3计算初始化种群个体的目标函数适应度值,选取其中目标函数值最优的作为初始头狼,位置记为Xlead,目标适应度值记为Ylead。选取除头狼的目标适应度值最优的S_num匹狼作为探狼,并按照式(22)、式(23)执行游走行为,直到某匹探狼的适应度值优于当前头狼的适应度值,或者达到最大游走次数Tmax,转至步骤4。

步骤 4随机选取除头狼的M_num匹狼作为猛狼,并按照式(24)向猎物位置奔袭(即头狼位置)。奔袭途中,如果猛狼感知到的目标函数值Yi大于头狼感知到的目标函数值Ylead,则Ylead=Yi,当前猛狼替代头狼重新发起召唤行为,并重新选取猛狼;如果猛狼感知到的目标函数值Yi小于头狼感知到的目标函数值Ylead,则继续奔袭行为,直到猛狼与头狼的距离小于dnear时,转至步骤5。

步骤 5猛狼联合探狼对猎物所在位置(即头狼位置)进行围攻行为,并按照式(25)对参加围攻行为的狼的位置进行更新。

步骤 6按照“胜者为王”的头狼更新规则更新头狼位置;按照“强者生存”的狼群更新机制对狼群进行更新[13]。

步骤 7判断是否达到最大迭代次数Kmax,如果满足,输出头狼位置,即最优航迹点位置,否则转至步骤2。

综上所述,可得基于改进WPA的UAH航迹规划流程图如图4所示。

图4 基于改进WPA的航迹规划流程图Fig.4 Flow chart of UAH path planning based on improved WPA

3 仿真实验及结果分析

3.1 仿真环境和实验数据准备

为验证本文所提的改进WPA在UAH航迹规划中的有效性,将传统WPA算法和改进WPA算法在相同条件下进行离线三维航迹规划仿真。仿真实验环境为Win10 64位操作系统,Intel Core i5-7300 HQ处理器,8GB RAM配置下的计算机,仿真软件为Matlab R2019B。

航迹规划任务空间为100 km×100 km×10 km,其中包括基准地形山峰、一个障碍区域、两个雷达区域。相关参数设置如下:基准地形山峰相关参数设置为(xk,yk)=[(50,80),(60,20)],hk=[10,5],xok=[15,10],yok=[15,10];起点坐标为Pstart=[3,3,1];目标点坐标为Pgoal=[90,90,2];障碍区域参数为:(xj,yj,zj)=[75,50,0],RLj=10,hj=6;雷达区域参数为:(xl,yl,zl)=[(20,50,0),(35,20,0)],RWl=[10,8],WPA参数设置如表1所示。同时,为进一步说明改进WPA用于三维航迹规划的有效性和优越性,本文增加了改进WPA与传统PSO算法[29]和传统GA算法[30]用于三维航迹规划的对比。传统PSO基本参数选择如下:粒子个数为50,惯性因子ω=0.79,两个学习因子c1=c2=2,ωmax=0.9,ωmin=0.4,Vmax=2;传统GA参数选择如下:种群规模为50,染色体长度为5,选择概率为0.5,交叉概率为0.8,变异概率为0.2。

表1 WPA参数设置Table 1 WPA parameter setting

3.2 平缓地形下的仿真结果与分析

从表2和图5可以看出,由于WPA自身算法特性的限制,在3种智能行为的每一次迭代中都需要计算并判断当前狼与头狼的适应度值,因此WPA相比PSO和GA,运行时间更长。但是改进的WPA与其他3种算法相比,在第3代就逐渐收敛到122.9,全局寻优能力更强,同时在快速收敛的同时,改进WPA在后期也有这样优越的搜索精度,改进WPA规划出的航迹长度更短,质量更优。同时,与传统的GA相比,改进的WPA能够有效改善群智能算法在寻优过程中易陷入局部最优的问题。由此能够得出以下结论:改进WPA的收敛速度更快,航迹代价更小,改进WPA能够有效改善传统WPA中由固化步长所导致的前期收敛速度慢的问题以及易陷入局部最优的情况,并且改进WPA的全局寻优能力更强。

表2 平缓地形下算法的对比结果Table 2 Comparison results of algorithms in gentle terrain

图5 平缓地形下适应度值变化曲线Fig.5 Change curve of fitness value in gentle terrain

从图6和图7可以看出,改进WPA算法和其余3种算法规划出的航迹均能躲避障碍区域和雷达探测区域,使UAH能够顺利到达目标点。但是,与其他3种算法规划出的航迹相比,改进WPA规划出的航迹长度相对较短,航迹高度变化小,航迹冗余少,从而使得航迹质量更佳。

图6 平缓地形下三维航迹正视图Fig.6 Front view of 3D track in gentle terrain

图7 平缓地形下三维航迹俯视图Fig.7 Top view of 3D track in gentle terrain

3.3 复杂地形下的仿真结果与分析

为进一步说明改进WPA在三维航迹规划中的性能,在第3.2节仿真的基础上将地形复杂化,模拟更为复杂的三维环境。4种算法的基本参数不变,起点与终点相同,三维环境相关参数设置如下:基准地形山峰相关参数设置为(xk,yk)=[(20,20),(30,80),(50,20),(60,50),(60,80)],hk=[8,10,5,8,8],xok=[5,10,10,10,8],yok=[5,10,10,10,8];障碍区域参数为:(xj,yj,zj)=[(80,30,0),(40,55,0)],RLj=[6,6],hj=[6,6];雷达区域参数为:(xl,yl,zl)=[(20,50,0),(80,60,0)],RWl=[10,8]。仿真结果如表3、图8～图10所示。

表3 复杂地形下算法的对比结果Table 3 Comparison results of two algorithms in complex terrain

图8 复杂地形下适应度值变化曲线Fig.8 Change curve of fitness value in complex terrain

图9 复杂地形下三维航迹正视图Fig.9 Front view of 3D track in complex terrain

图10 复杂地形下三维航迹俯视图Fig.10 Top view of 3D track in complex terrain

从表3和图8可知,改进WPA在复杂地形中仍然能够快速寻找到最满意的航迹,虽然因自身算法性能的限制,其在算法运行时间上稍逊于传统PSO及GA,但是相比传统WPA已有较大的改善。从图8可知,改进WPA在第10次迭代后逐渐收敛到最优值附近,相比其他3种算法,收敛速度快,寻优能力更强,规划出的航迹更短。同时,与传统GA相比,其传统群智能算法易陷入局部最优的问题也有着较大的改善。从图9～图10可以看出,改进WPA规划出的航迹冗余少,没有频繁的高度变化,航迹质量更优。

综合第3.2节和第3.3节的仿真结果,可以得出以下结论:本文所提出的改进WPA在用于UAH三维航迹规划时有着令人满意的收敛速度和全局寻优能力,能够快速搜索到最优航迹,且规划出的航迹质量更优,能够避开威胁区域,进而保证UAH安全、快速地到达指定目标区域乙执行任务。

4 结 论

本文针对UAH航迹规划问题,提出了一种改进WPA算法。利用自适应步长代替传统WPA算法中的游走步长、奔袭步长和围攻步长,通过依靠当前狼的位置与头狼位置之间的距离动态调整步长,克服了传统WPA算法前期收敛速度慢的缺点。同时,针对探狼游走行为,将莱维飞行策略和变方向的自适应游走相结合,进一步拓展了搜索空间,使改进WPA算法具有较好的全局寻优能力和较快的收敛速度。仿真结果表明,与传统WPA算法相比,改进WPA算法能够更快搜索到最优航迹,且规划出的航迹能够有效躲避障碍物和雷达,航迹规划所需代价更小,航迹质量更优,实验证明了改进WPA算法用于解决UAH航迹规划问题的有效性和优越性。