基于CMPSO算法的无人机复杂三维路径规划

甯 洋, 郑 波,2, 龙足腾, 罗金超

(1.中国民用航空飞行学院航空电子电气学院,四川 广汉 618000; 2.核工业西南物理研究院,成都 610000)

0 引言

无人机(UAV)路径规划是无人机领域的研究热点之一,它是指在不违背自身物理特性及约束条件的前提下,形成一条从出发点到末端点的最优路径。20世纪80年代之前,无人机的路径规划主要靠人工来完成,但是战场环境复杂多变,人工规划的路径不足以面对复杂多变的现代战场,随着科技的快速发展,无人机的通讯、交互、控制、探测、导航技术都得到了增强,对地面人工的操控要求就逐渐变低,无人机路径规划逐渐趋于智能化。

目前,国内外学者提出了大量用于无人机路径规划的方法,其中比较经典的有基于图搜索的算法包括Dijstra算法[1]、A*算法[2]、D*算法[3]等;基于采样的算法包括随机路标[4]和随机搜索树[5]等;一些局部规划算法,例如人工势场法[6]和动态窗口法[7]等。随着群智能算法的发展,众多学者也将群仿生智能算法应用于无人机路径规划,其中,比较常见的群智能算法有粒子群优化(PSO)算法、蚁群算法、遗传算法、人工势场法等。文献[8]提出了一种改进蚁群优化(ACO)算法,使用栅格法来将三维空间平分,虽然改进算法能够有效避免陷入局部最优,但是约束条件较少且模拟的三维空间较简单,栅格法规划的路径对航路起点和终点的位置比较敏感,且规划的路径不平滑;文献[9]利用了人工势场法进行规划,但是涉及的模型过于理想;文献[10]利用ACO算法进行规划,但是所涉及的算法仅仅在二维空间可行,无法应用于三维空间。

PSO算法是一种启发式智能算法,相比于其他算法,PSO算法具有鲁棒性较好、对种群个体数量敏感性低[11]、涉及的参数和公式较少、收敛速度快等优点,但缺点是后期收敛速度慢,且收敛精度低导致早熟现象。针对其缺点,众多学者进行了研究。文献[12]将PSO算法与细菌觅食算法、遗传算法混合,各算法间取长补短,在速度、收敛值、跳出局部最优方面均有改善;文献[13]利用Logistic混沌映射处理粒子群,提升粒子种群的初始化质量,提高种群的多样性,能够有效提高PSO算法的全局寻优能力;文献[14]提出了一种结合天牛须算法的粒子群算法,利用天牛须算法帮助粒子群算法跳出局部最优;文献[15]将鸡群算法的分组优化策略应用于粒子群算法,并在更新时采取模拟退火操作,有效避免了陷入局部最优。

本文综合考虑航程代价等约束条件,设计了代价函数,考虑了城市和山区两种复杂环境,将CMPSO(Compression and Mutation PSO)、CPSO与PSO算法分别进行仿真实验,结果表明,CMPSO算法具有较高的寻优精度,在两种环境下都能得到高质量的路径。

1 粒子群算法

1.1 传统粒子群算法

假设粒子群的种群规模为N,在d维空间中搜索,粒子i的当前速度和位置分别为vi与xi(i=1,2,…,N),所经历过的最优位置为pi,群体经历过的最优位置为pg,上述参数分别表示为

(1)

PSO算法靠更新粒子的速度和位置来迭代,直到满足停止规则,速度和位置更新规则为

(2)

式中:w为惯性权重,表示对当前粒子速度的信任程度;c1、c2为粒子的学习因子,调节粒子移动的最大步长;r1、r2为0～1间的随机数,增加粒子搜索的随机性。

1.2 融合压缩策略与变异策略的粒子群(CMPSO)算法

传统的PSO算法的所有参数都是固定的,因此算法易理解易操作,但是在解决实际复杂工程问题时,会出现搜索不到全局最优解,或者搜索到全局最优解需要消耗大量时间成本的情况,固定的参数往往都不能很好地解决问题,导致结果不理想。本文提出融合压缩策略与变异策略的思想,在压缩策略中,取消了惯性权重w,加入了压缩因子,避免因选取错误的权重而导致寻优结果与预期差别较大,再通过变异策略来增加粒子的多样性,以此提高算法的全局搜索能力。

1.2.1 惯性权重的影响

惯性权重w影响粒子的飞行速度,表示对当前粒子速度的信任程度,w的取值对PSO算法的性能有明显影响,较大的惯性权重有利于全局搜索,但是容易导致粒子错过最优解,较小的惯性权重有利于局部搜索,但是容易陷入局部最优。采用了错误的惯性权重,则可能造成收敛精度低或者无法收敛,在无人机路径规划方面则会导致找不到合适的路径。所以粒子在前期能够有较快的搜索速度,后期有较慢的搜索速度,以达到平衡粒子全局搜索能力与局部搜索能力的目的,文献[16]提出了线性递减惯性权重的粒子群(Linear Decreasing Inertia Weight PSO,LDIWPSO)算法,文献[17]提出了一种余弦式递减惯性权重粒子群(Cosine Decreasing Inertia Weight PSO,CDIWPSO)算法,这两种权重的算式分别为

(3)

(4)

式中:w1为线性递减惯性权重;w2为余弦式递减惯性权重;wmax为权重最大值,可取0.9;wmin为权重最小值,可取0.4;Imax为最大迭代次数;k为当前迭代次数。两种递减惯性权重的变化趋势如图1所示。

图1 两种递减惯性权重变化趋势对比

拥有两种递减惯性权重的PSO算法在低维问题中能够有效地避免早熟,但是对于高维复杂问题,算法的寻优效果并不是很理想,当粒子在迭代过程中,某粒子当前代的适应度值相比于上一代变差,如果此时惯性权重变小的话,不利于该粒子进行全局搜索,导致该粒子不能遍历全局从而陷入局部最优。

1.2.2 压缩策略

无论是线性递减惯性权重还是余弦式递减惯性权重都实现不了真正意义上的自我调节,为了减少w对粒子状态的影响,避免采用错误的惯性权重,同时又能平衡前期的全局搜索与后期局部搜索,需要所有粒子都能根据自身情况自适应调节,本文采用带压缩因子的粒子群(CPSO)算法[18],其粒子速度更新算式为

(5)

式中,δ为压缩因子,其算式为

(6)

相比于传统PSO,CPSO算法相当于拥有递减惯性权重的粒子群算法。为了平衡算法的全局搜索能力与局部搜索能力,CPSO算法删除了惯性权重w,取而代之的是压缩因子δ,这样粒子群算法的速度就仅靠c1、c2两个学习因子来调节,c1、c2的取值为

(7)

(8)

其中:cmax的取值为2.5;cmin的取值为1.5[18];f(xi)为粒子i的适应度大小;favg为种群的平均适应度。当粒子i的适应度f(xi)小于种群的平均适应度favg时,粒子xi进行局部搜索,c1、c2的取值按照式(7)进行;当粒子i的适应度f(xi)大于种群的平均适应度favg时,粒子i进行全局搜索,c1、c2的取值按照式(8)进行。

1.2.3 变异策略

PSO算法在每次迭代后都会形成新的粒子,新粒子相比旧粒子会有新的速度和位置,因其受到全局最优解的影响,新粒子会向全局最优粒子的方向移动,但是如果此时全局最优粒子的位置不是真正的全局最优解,则粒子就会陷入局部最优。所以本文对粒子进行提前变异,增加粒子的多样性和活跃性,增加因不断迭代而慢慢缩小的活动空间,增强粒子跳出局部最优的能力,粒子变异算式为

(9)

式中,β为与xid同维,且每一项都是[0,1]间随机数的D维向量,这样做的目的是使xid中的部分元素被pgd中相应位置的元素替代,还能增加粒子的搜索范围,不仅增加了粒子多样性还能增加粒子的后期开发能力。

CMPSO算法的具体步骤如下:

1) 设置种群规模N,最大迭代次数Imax,最小学习因子cmin,最大学习因子cmax,变异率γ等参数,并初始化各粒子的速度vi和位置xi;

2) 计算各粒子的适应度,并计算个体最优位置与群体最优位置,计算个体最优适应度与群体最优适应度;

3) 根据压缩策略更新各粒子的速度;

4) 判断0～1间的随机数R是否大于变异率γ,如果是,则按照式(2)更新位置,否则按照式(9)更新位置;

5) 判断是否满足终止条件,未满足则重复步骤2)～4),满足则结束循环,本文设置的结束条件为达到最大迭代次数。

2 算法性能测试

为了验证改进算法的可行性,本文对CEC2017测试函数中的部分基准函数进行仿真测试,这些函数都具有复杂、多模态等特点。本次测试函数的算法分别为粒子群算法(PSO)、采用线性递减惯性权重的算法(w1-PSO)、采用余弦式递减惯性权重的粒子群算法(w2-PSO)、仅采用压缩策略的粒子群算法(CPSO)、仅采用变异策略的粒子群算法(MPSO),以及同时采用压缩策略与变异策略的粒子群算法(CMPSO),算法参数如表1所示。共有的参数取相同的值。

表1 算法参数

10种测试函数的函数特征如表2所示。

表2 测试函数及特征

其中既包含单峰测试函数也包括多峰测试函数,为了测试所有算法在低维和高维的寻优能力,其中函数f1、f2仅在2维测试,函数f3～f10都在50维测试。函数f1、f2、f3、f4、f6、f10为多峰测试函数,它们虽然只有一个全局极小值点,但是都存在大量局部极小值影响算法的寻优结果,函数f5、f7、f8、f9都为单峰测试函数。

每个算法独立运行100次,取其适应度均值(mean)、方差(StD)和平均消耗时间(MET)来衡量寻优性能。测试函数运行结果如表3所示。

表3 测试函数运行结果

由表3可以看出,PSO、CPSO、MPSO与CMPSO算法对测试函数的测试过程等同于一种消融实验,PSO、CPSO与MPSO算法的寻优结果明显优于PSO算法,而CMPSO算法的寻优结果又明显优于CPSO算法与MPSO算法,且也优于w1-PSO与w2-PSO算法,总体来看,CMPSO算法测试结果的均值和方差都明显优于其他算法,结果更接近最优值,说明CMPSO算法的收敛效果更好,且更加稳定,收敛时间也处于较理想的水平。综合比较下,CMPSO算法的收敛性和计算复杂度都比较理想,证明了压缩策略与变异策略的有效性。这是因为压缩策略能够使粒子根据自身状态进行正确的自适应调节,加强了局部寻优能力,而变异策略又能增加粒子的多样性,提高粒子的开发能力,加强了全局寻优能力,从而使CMPSO算法的寻优能力要远远优于其他算法,表明CMPSO算法能为路径规划提供强有力的技术支撑。

3 环境建模及约束条件

3.1 环境建模

3.1.1 城市环境建模

环境建模就是将环境中的各种物理信息转换为计算机算法能处理的数字模型,这是规划无人机路径的前提和基础[19]。为了验证CMPSO算法的有效性,本文主要模拟城市和山区两种环境下的路径规划,在城市环境中,所有不同形状的建筑物都可以等同于圆柱形障碍物,当无人机飞过这些障碍物,需要与这些障碍物有一定的距离来保证自身的安全。障碍物示意图见图2。

图2 障碍物示意图

图2中,R1为障碍物的半径,S为无人机的尺寸,T为危险飞行区域,要求无人机离障碍物中心点垂直线的距离R2大于R1+S才能满足要求。

本文的城市环境建模设计了26个圆柱形障碍物,半径从小到大分别为3 km、4 km、5 km,城市环境仿真如图3所示。

图3 城市环境仿真

3.1.2 山区环境建模

山区环境仿真地图可建模为

(10)

式中:z0为地基高度,取值为0.02 km;M为山峰的个数,取值为15;hm、xm、ym、xsm、ysm都为M维的系数向量,hm为山峰的高度,(xam,yam)为山峰中心轴在地面的坐标值;xsm,ysm为山峰分别在x方向和y方向的坡度,表示山峰的陡峭程度。山区环境仿真如图4所示。

图4 山区环境仿真

3.2 约束条件

固定翼无人机在飞行过程中,并不能像旋转翼无人机一样自由升降、前进、后退、以及空中停滞。因此,固定翼无人机的飞行要求相比于旋转翼无人机更严格。本文综合考虑航程代价、飞行约束代价(包含高度约束代价、最小惯性距离约束代价、俯仰角约束代价)和环境威胁代价,以此使本文研究内容更贴近现实,更有应用价值。

1) 航程代价。

由于自身航油携带量、自身油耗、总油量等因素的影响,无人机的飞行距离都是有限的。设最终航迹有D个航路点,每个航路点i和i+1之间的距离为li,则航程代价为

(11)

式中,Lmax为最大航程。

2) 高度约束代价。

无人机在飞行过程中,如果飞行高度太低容易受到建筑物或者山谷地貌的影响,飞行高度太高则容易受到大气和自身性能的影响,因此需要在一个合适高度范围内飞行,无人机在城市或者山谷低空侦察飞行时,由于自身有一定的体积,还面临着电杆、树木等障碍物的威胁,因此飞行时需要与环境保持一定的安全距离,设电杆和树木的高度为hz,无人机不能贴着这些障碍物飞行,因此还要设置一定的安全距离hsafe,为了达到较好的侦察效果,无人机飞行时的高度并不能太高,设某航迹点下方的地面高度为ht,距离地面的最大高度为hd,则无人机飞行高度Zi为

(12)

则高度约束代价为

(13)

式中,C0为代价常数,可自行设置。

3) 最小惯性距离约束代价。

无人机在飞行时,由于自身的惯性原因及动力原因,急转弯是不被允许的,因此要设置最小惯性距离Lmin防止飞机突然进行转弯,此约束可表示为

li≥Lmini∈[1,D-1]

(14)

则最小惯性距离约束代价为

(15)

4) 俯仰角约束代价。

由于自身性能的限制,无人机在升高或者俯冲时,角度需要有一定的限制,设置最大俯仰角θmax,只有当俯仰角小于θmax时才能安全飞行,否则有可能对飞机机体造成损坏。设前后相邻的两航路点坐标分别为(xi-1,yi-1,zi-1)、(xi,yi,zi),如果zi≠zi-1,则说明飞机在进行升高或者俯冲动作,则飞机的最大俯仰角θmax应满足

(16)

则俯仰角约束代价为

(17)

式中,θ为无人机的俯仰角。综合考虑无人机的飞行高度约束、最小惯性距离约束、俯仰角约束,则飞行约束代价为

Trestrain=T1+T2+T3。

(18)

5) 环境威胁代价。

本文的环境威胁主要为两种:1) 山区障碍物的威胁;2) 城市建筑障碍物的威胁。无人机在飞行过程中,如果距离这些障碍物越远,则表明无人机越安全,设航路点与障碍物中心轴的水平距离为

(19)

式中:(xd,yd)为航路点在水平面投影的坐标;(xm,ym)为障碍物中心轴在水平面投影的坐标。则环境威胁代价为

(20)

适应度函数包含了优化目标,以及约束条件,是定量评价解优劣的标准[20],综合上述分析,无人机的总代价函数为

f=ω1Tvoyage+ω2Trestrain+ω3Tthreat

(21)

式中,ω1、ω2、ω3为权重系数,表示这些代价的重要程度,且满足ω1+ω2+ω3=1。

4 仿真实验分析

为了验证CMPSO算法的有效性,本文将CMPSO、CPSO与PSO算法应用于无人机路径规划,对比分析算法的寻优结果。山区和城市两种环境都是在100 km×100 km×2 km的空间中仿真。

为了验证算法在不同末端航线规划的性能,假设将起点视为坐标原点,对于起点在不同象限的区域各设置一个侦察点,在山区环境中,设置起点为(50 km,50 km,0.13 km),设置4个象限的侦察点分别为(5 km,90 km,0.06 km)、(95 km,90 km,0.06 km)、(20 km,5 km,0.06 km)、(97 km,10 km,0.06 km),形成航线为L1～L4。在城市环境中,设置起点为(50 km,50 km,0.07 km),4个侦察点分别为(5 km,90 km,0.3 km)、(59 km,90 km,0.3 km)、(5 km,5 km,0.3 km)、(90 km,7 km,0.3 km)。PSO算法种群数N为300,每条航路的航路点个数为30,最大迭代次数为150,学习因子c1、c2都设置为1.5,惯性权重w为0.9。CPSO算法的cmax、cmin分别取0.9、0.4,设置无人机的约束条件为:Lmax=100 km,hz=0.005 km,hsafe=0.15 km,hd=2 km,Lmin=1 km,C0=500;θmax根据式(16)确定。

图5为3种算法在山区环境中的路径规划仿真图。

图5 山区环境路径规划图

图6为3种算法在城市环境中的路径规划仿真图。

图6 城市环境路径规划图

如图5～6所示,CMPSO算法规划的航迹路线无论是平滑度还是偏转次数,都比PSO和CPSO算法规划的航迹要好,有利于无人机的飞行安全。

表4、表5为山区和城市两种环境中的3种算法的航路规划性能比较。

表4 山区环境寻优数据对比

表5 城市环境寻优数据对比

每条航路各自独立仿真20次,计算20次仿真的平均消耗时间,20次航程的最小值(min)、平均值(mean)、标准差(StD),以及违反约束代价(Constraint Violations,CV)的次数,CV为1×5的矩阵,反映20次仿真过程中算法未满足3.2节中约束代价的次数,例如,CV=[5,0,6,0,0],表示这20次实验中,5次违反航程约束条件,6次违反最小惯性距离约束条件。由表4、表5可以看出,在L1～L4这4种不同末端航线的规划中,相比于其他算法,CMPSO算法规划航路所消耗的时间最少,航路的距离最短,性能最稳定,违反约束条件的次数最少。充分证明了CMPSO算法面对实际工程问题时优秀的寻优能力。

图7为山区和城市两种环境中航线L1的目标函数迭代图。

图7 目标函数迭代图

由图7可以看出,随着迭代次数的增加,3种算法的目标函数值都在减小,不过CMPSO算法的最终目标函数值和规划快速性均优于CPSO、PSO算法,且PSO算法的寻优结果明显差于其余两种算法,这说明CPSO和PSO算法都可能陷入局部最优,而改进后的CMPSO 算法,通过压缩策略增加了粒子的自调节能力,通过变异策略增加了粒子的多样性,从而增加了算法跳出局部最优的能力,证明了CMPSO算法面对路径规划问题时的有效性。

5 结束语

本文提出了CMPSO算法,利用压缩策略使粒子实现自适应调节,利用变异策略增加了粒子的活跃性与多样性,并用10种经典测试函数对CMPSO算法的寻优性能进行了验证,结果表明,CMPSO算法具有优秀的寻优能力和避免陷入局部最优的能力。综合考虑航程代价、飞行约束代价和环境威胁代价设计了目标函数,通过仿真测试,相比于PSO与CPSO算法,CMPSO算法无论在山区环境中还是在城市环境中,规划出来的路径更加合理,航程更短,性能更稳定且耗时更短。