基于改进粒子群优化的多无人机协同航迹规划

杜 云, 彭 瑜, 邵士凯, 刘 冰

(河北科技大学电气工程学院, 石家庄 050018)

近年来无人机在科学研究领域和市场应用中,都得到了越来越多的关注[1]。随着技术的快速发展,无人机自身性能不断增强,极大地加速和扩展了无人机在军事和民事领域的应用。作为无人机应用的重要方向之一,多无人机协同飞行备受关注。

在多无人机协同飞行过程中,航迹规划系统为无人机飞行提供航迹指引,是实现无人机协同作战的关键技术之一。协同航迹规划可得到满足无人机性能约束、机群空间和时间协同关系的最优航迹,是无人机实现自主飞行的重要保障。

当前,有不少学者对多无人机协同航迹规划算法进行了研究。文献[2]提出一种基于“追踪”思想的改进A*算法对航迹求解并通过仿真实验验证算法有效性；文献[3]提出一种改进模拟退火算法,将人工蜂群与模拟退火相结合在二维空间内取得较好结果；文献[4]提出使用人工势场算法描述最优控制问题中的约束条件,以降低求解难度,并引入起飞时间为优化变量完成多无人机系统的协同,通过仿真验证得到可行方案；文献[5]采用合作型协同多种群粒子群优化算法规划出满足可飞行要求的路径,时间协同方面是采用五次PH路径法调整路径的距离以达到近似相等来保证同时达到,虽可实现时间协同要求,但破坏了路径最优性；协同航迹规划存在约束条件多、复杂程度高、计算量大、实时性要求高等特点,上述文献虽可实现协同航迹规划,但在规划实时性、寻优成功率等方面仍有较大提升空间。

针对现有航迹规划算法过早收敛和易陷入局部最优的缺点,以及改进算法复杂度高、运算时间较长的不足,提出一种改进粒子群算法,利用参数调整策略加强粒子搜索能力；设置最大速度兼顾搜索的全面性和精度；引入混沌映射改善粒子质量；设计最优位置取代机制加快收敛速度。最后,将综合改进算法应用于多无人机协同航迹规划仿真实验中,验证了改进算法的优越性。

1 航迹规划数学模型

1.1 航迹表示

航迹规划的目的是在三维空间内寻找一条满足各种约束条件的最优路径。在整个解空间内使用三维坐标系(x,y,z)来表示搜索到的航迹点位置,航迹点满足以下条件：

{(x,y,z)|xmin≤x≤xmax,ymin≤y≤ymax,

zmin≤z≤zmax}

(1)

式(1)中：xmin、xmax、ymin、ymax、zmin、zmax表示解空间的边界值。搜索到的航迹点序列通过平滑的曲线连接起来形成航迹。

1.2 协同航迹规划约束描述

1.2.1 最大航程约束

最大航程约束是根据无人机携带的燃料总量决定的,最大航程记作Lmax,若整条航迹由n个航迹点组成,则第i段航程可表示为li,总航程L满足：

(2)

1.2.2 最大转弯角/俯仰角约束

最大转弯角约束即最小转弯半径约束是在水平方向上由于无人机自身机动性能的限制,设任意一架无人机第i段航迹的水平投影为ai=(xi-xi-1,yi-yi-1),最大转弯角为θmax,转弯角[6]可表示为

(3)

最大俯仰角是在竖直方向上对当前航迹点到下一个航迹点做俯仰运动时的角度限制,设最大俯仰角为φmax,两个相邻航迹点竖直高度差为|zi-zi-1|,则俯仰角约束[7]可表示为

(4)

1.2.3 飞行高度约束

为保证无人机飞行安全,飞行高度不宜过低或过高。设hi表示第i段航迹的飞行高度,hmin表示最低飞行高度,hmax表示最大飞行高度,该约束表示为

hmin≤hi≤hmax,i=1,2,…,n

(5)

1.2.4 空间协同约束

空间协同约束是对多无人机协同飞行时空间位置关系的限制,要求无人机集群之间的距离应大于最小安全距离,即空间协同约束可表示为

s>smin

(6)

式(6)中：s为无人机之间距离；smin为最小安全距离。

1.2.5 时间协同约束

时间协同约束是对无人机集群到达目标时间的限制。可分为以下两种情况：①强协同。设Li为一条航迹的长度,无人机速度范围为[vmin,vmax],则可解出每架无人机到达目标点的时间范围ti=[Li/vmax,Li/vmin],若sj=t1∩t2…∩tn为非空集,则取集合sj中最小值作为达到时间。②弱协同。因无人机性能原因导致无法在同一时刻达到,则取一个可接受的最小时间间隔[tmin,tmax]作为达到时间。

1.3 威胁约束模型

建立飞行环境模型是完成协同航迹规划的前提,研究考虑的威胁包括雷达探测威胁和山峰威胁。

1.3.1 雷达威胁

雷达是无人机主要威胁之一,其探测能力与周围复杂环境有关。当航迹点在雷达最大探测距离内,则表示无人机在雷达威胁范围内。雷达威胁数学模型可表示为

Ldanger=(xk,yk,zk,rk)

(7)

式(7)中：xk、yk、zk表示雷达威胁源的中心位置；rk表示雷达探测半径。

1.3.2 山峰威胁

无人机在执行任务时难免遇到一些不可穿越的山峰障碍,规划的航迹需避免与山峰碰撞。单个山峰威胁可表示[8]为

(8)

式(8)中：xm、ym、zm表示山峰威胁的三维坐标；a、b表示山峰的起始位置；c表示山峰的高度系数；d为高度调节参数；i表示山峰的跨度范围。调整上述参数可改变山峰的位置、跨度和高度。

1.4 适应度函数模型

无人机飞行代价包括飞行能量消耗(由航程决定)、山峰碰撞代价、雷达威胁、飞行高度、转弯角、俯仰角、无人机间距等指标。定义适应度函数[9]为

F=w1f1+w2f2+w3f3+w4f4+w5f5+w6f6

(9)

式(9)中：F为总代价；f1为航程代价；f2为威胁代价,包括雷达威胁和山峰威胁；f3为飞行高度代价；f4为转弯角代价,f5为俯仰角代价,f6为机间距代价；w表示各项指标所占的权重,且满足：

w1+w2+w3+w4+w5+w6=1

(10)

2 基本粒子群算法及其改进

2.1 基本粒子群算法简介

粒子群算法是模拟鸟群搜索食物的方法,假设在一个D维的目标搜索空间中,有m个代表问题潜在解的粒子组成一个种群x=[x1,x2,…,xm],第i个粒子的信息可以表示为xi=[xi1,xi2,…,xiD]T,速度为vi=[vi1,vi2,…,viD]T。算法先进行初始化,然后通过迭代找到最优解。每一次迭代中,粒子通过跟踪个体极值和群体极值进行信息交流,再根据式(11)和式(12)更新自己的速度vi和位置xi。

(11)

(12)

式中：w为惯性权重；c1和c2为两个学习因子；r表示(0,1)的随机数。

2.2 改进粒子群算法

基本粒子群算法规则简单、易于仿真。但在多维度优化问题求解上存在收敛速度慢、易陷入局部最优等缺点。针对这些不足提出改进粒子群算法。

2.2.1 参数调整

惯性权重w和学习因子c1和c2在很大程度上影响着粒子速度的更新。已有文献证明惯性权重较大时有助于全局搜索,较小时有助于加快收敛[10],常采用如下所示线性递减方式：

wt=wmax-(wmax-wmin)(t/T)

(13)

式(13)中：t表示当前迭代次数；wmax和wmin分别表示惯性权重的最大值和最小值；T表示最大迭代次数。分析可知,学习因子c1和c2也起到影响粒子搜索方向的作用。为加快粒子群体在迭代学习过程中向最优解靠近,与此同时避免种群陷入局部最优,对学习因子c1和c2进行自适应调幅设计,具体规律为

c1=cmin+(cmax-cmin)(t/T)

(14)

c2=cmax-(cmax-cmin)(t/T)

(15)

迭代初期c2较大可引导粒子从当前位置向全局最优解的方向搜索,有助于提升收敛速度,后期c1较大则是为了强化粒子个体的搜索能力,防止种群堆积在群体最优解附近进行重复搜索导致搜索停滞,避免算法陷入局部最优。

2.2.2 混沌初始化

粒子群算法的收敛速度和解的好坏受初始粒子分布的影响。考虑到Logistic混沌[11]有较好的均匀分布性,设计采用Logistic混沌进行粒子群位置初始化,基本公式为

xn+1=μxn(1-xn)

(16)

式(16)中：xn表示第n个混沌变量；μ为预先设定常数。当xn∈(0,1)且μ∈[0,4]时,映射系统处于混沌状态。当μ=4时,系统在[0,1]处于混沌状态。

为说明Logistic混沌映射初始化的优越性,做出Logistic混沌映射与rand命令在[0,1]范围的对比图。由图1可看出混沌映射的取值分布更均匀。混沌映射能提高初始粒子的质量,增加粒子种群的多样化、有效防止种群过早收敛,增强算法的合理性。

图1 混沌映射与随机数对比图

2.2.3 取代策略

遗传算法中的交叉行为和变异行为可有效提升种群多样性,增强全局搜索能力。借鉴遗传算法,提出一种最优位置取代策略,具体设计过程如下：种群中所有粒子完成某一迭代循环后,计算每个粒子的适应度值,并根据适应度大小进行排序。适应度值较差的粒子说明其位置距离最优解较远或进入威胁区域,参考价值不高,对这些粒子进行剔除,用性能较好的粒子位置取代性能较差的粒子。若完全进行取代,则会出现重复搜索,会增加陷入局部最优和搜索停滞的可能性。故综合考虑,设计在取代的位置和速度小范围内进行偏移,从而提升效率,并增加搜索多样性。具体取代公式为

xbad=xgood+2ρ1(rand-0.5)

(17)

vbad=vbad+2ρ2(rand-0.5)

(18)

式中：xbad为适应度较差的粒子位置;xgood为适应度较好的粒子位置；ρ1为位置偏移半径；vbad为被取代的粒子速度；ρ2为速度偏移半径。

2.2.4 调速机制

传统粒子群算法的最大速度vmax为定值,难以同时兼顾收敛速度和搜索精度两项指标。因此提出一种调速机制改进策略,具体过程如下。

将基本粒子群中的最大速度由定值改为“阶梯式”。前期最大速度较大,虽搜索粗糙,但可扩大粒子的搜索范围,增强多样性；中期最大速度适当调小,兼顾收敛速度和精度；后期再次减小,使粒子进行更细致的搜索。调速机制公式为

(19)

式(19)中：v1>v2>v3。调速机制能兼顾不同迭代阶段的全面搜索和精确搜索的要求,前期侧重全局搜索能力,后期侧重搜索精度,中期作为过渡期平衡两种性能。调速机制可灵活调整参数,加强算法的通用性。

2.3 改进算法步骤

基于上述改进策略,提出了无人机协同航迹规划算法,记为RPSO算法。具体步骤如下。

(1)设置无人机的起点和终点,设定山峰和雷达的位置、作用半径与无人机最小安全距离。

(2)设置种群总数N、求解维度D、最大迭代次数T,根据式(13)～式(15)对惯性权重和学习因子初始化,根据式(19)对最大速度进行设定,对个体最优值和种群最优值初始化。使用Logistic混沌映射,对粒子的位置和速度进行初始化。

(3)进行迭代搜索,计算每个粒子航迹点的代价,与个体最优值和种群最优值做比较。若小于个体最优值,则更新个体最优值；若小于种群最优值,则更新种群最优值。

(4)完成速度位置的更新。若计算出的速度大于设定的最大速度vmax,则取值为最大速度。

(5)根据步骤(4),对计算出的航迹代价进行排序,并完成粒子位置和速度的取代更新。

(6)根据当前迭代次数,调整最大速度。判断是否到达最大迭代次数,若未达到,转到步骤(3),否则向下执行。

(7)搜索完成,输出最优解。

3 仿真实验与结果分析

针对提出的算法进行仿真实验,并对结果进行分析。具体仿真环境：CPU为intel Corei5处理器,主频2.6 GHz,操作系统为windows7 64位,内存为4 GB,在MATLAB R2016a环境下实现。

3.1 仿真条件

设定无人机速度范围为[0,10 m/s],相邻两个航迹点之间最大转弯角与最大俯仰角均为45°；设置地形环境,具体参数如表1所示。无人机数量8架,每架无人机的起点位置和终点位置参数如表2所示。

表1 地形威胁参数

表2 无人机起点和终点位置

基本粒子群算法参数设定：种群数N=500,最大迭代次数T=120,求解维度D=40,惯性权重w=0.8,学习因子c1=c2=2,最大速度vmax=1。RPSO的惯性权重从2.2递减至1.5,c1从0.2递增至2.2,c2从2.2递减至0.2。V1取(ymax-ymin)/1 000,V2取0.75V1,V3取0.5V1。无人机飞行过程中的最小安全距离设置为20 m。

3.2 仿真结果与分析

分别使用PSO算法、Elhoseny[12]提出的MGA(modified genetic algorithm)和Tian等[13]提出的MPSO(modified particle swarm optimization)以及RPSO算法,进行100次仿真实验。

由实验得出几种算法在两种不同的规划算法下的平均运行时间,基本PSO算法用时17.48 s,RPSO算法用时17.5 s,表明改进方案对算法求解的运行时间没有产生明显影响,且优于MGA算法的32.4 s和MPSO算法的21.66 s,表明改进算法在快速性方面的优势。图2和图3所示分别为立体航迹对比和代价收敛对比,可见设计的RPSO算法收敛速度最快、飞行代价最低、航线平滑性最佳。

图2 立体航迹对比

图3 迭代收敛对比

图4所示为4种算法的平均代价折线,从图4中可明显看出，PSO算法与MGA算法平均代价波动性较大,且最小值偏高,由此可知算法搜索的航线路程较远或未成功规避威胁与障碍。MPSO算法与RPSO算法的代价折线较小且稳定,因RPSO算法的代价折线整体在MPSO算法的折线图下,说明RPSO算法性能优于MPSO算法,且RPSO算法在实验中均没有出现撞山、进入雷达探测区域。

图4 代价折线

4种算法的性能对比如表3所示,表3中代价为100次仿真实验中航迹代价的平均值；成功率为仿真结果中代价不高于1.3的航迹线所占100次实验的比重；表中次数为所有航线代价达到收敛所需次数的平均值,若规划结果碰到障碍物或航线代价高于1.3,则该次规划的收敛次数取最大迭代次数T。结果表明基本粒子群算法的平均代价为1.401,成功率仅为41%,达到收敛平均需要迭代116次,而改进后的RPSO算法规划出航线的平均代价为1.078,成功率为100%,达到收敛平均需要43次。

表3 性能对比

表3说明RPSO算法较PSO算法在代价性能上提升23.05%,在收敛所需次数上提升62.93%,成功率提升59%,为4种算法中性能最佳的算法。

规划出航迹后可计算出总航程,根据设定的速度范围可得机群满足强协同要求,预计到达时间ET=229.6 s,每架无人机的速度为

(20)

由RPSO算法规划出的结果在20个航迹点处的转弯角和俯仰角均满足要求,如图5所示。此外无人机之间距离均大于设定的最小安全距离,如图6所示，满足空间协同要求。

图5 转弯角与俯仰角

图6 机间距

4 结论

(1)惯性权重和学习因子的调整,实现粒子在保持惯性和向最优粒子学习两种行为上达到较好平衡。

(2)混沌映射的引入改善了粒子初始位置的分布；设计取代策略加快了算法收敛速度。

(3)调速机制的提出兼顾了粒子群算法的全局搜索能力和局部搜索能力。

(4)通过多无人机协同航迹规划仿真实验,说明RPSO算法能有效规划出高质量协同飞行路径。