基于改进DPSO的故障下多无人机协同任务规划

邵士凯,李厚振,赵渊洁

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

0 引言

伴随着高新技术的发展,无人机在各个行业均受到了普遍的重视。尤其在多变的战场环境下,多无人机协同执行任务是无人机技术的发展趋势,多无人机协同执行侦查攻击任务是无人机执行复杂多样化、智能化任务的研究热门[1-3]。

目前,针对无人机任务分配问题,国内外很多学者均进行了广泛的研究。文献[4-5]提出了一种故障无人机编队容错控制策略,给出了编队控制与协调的基本定义和分类,针对故障检测的容错协同控制技术进行了综述。文献[6]提出离散粒子群算法进行无人机的任务分配,通过仿真实验验证其算法的有效性。文献[7]根据无人机群的在线任务分配问题,设计了粒子二维0-1编码方法和针对不规范粒子的修正方法,实验验证该方法解决带实时要求的任务分配问题。根据当前发展成果,无人机任务分配的控制方式包括了集中式、分布式与分层次控制,文献[8]使用混合整数线性规划(MILP)进行了多无人机的任务规划,该方法提高了障碍物数量及起点和目标点间距离的可扩展性。但是其计算复杂程度也将会随着任务数量的增多使运算时间变长,不适合大机群协同任务分配。文献[9]提出了一种DE-DPSO-GT-SA算法的协同多任务分配,并进行了多种算法的对比,仿真实验证明该方法具有较好的收敛特性。文献[10-11]考虑实际环境下无人机任务分配的协同能力,加入了复杂的地形约束。文献[12]提出了一个由嵌入式硬件和高级别通信协议相结合的系统,作为识别、分发和分配任务的基础,进而用简单分散的方式供多无人机使用。文献[13]提出了一种动态离散鸽群的优化算法,进行处理多无人机协同搜索攻击任务规划,集成了任务分配和路径生成方面。

此外,针对当前无人机航线规划的研究方法,国内外学者进行了深入的探索研究。运用图论的方法进行一些路径规划是当前研究的一种思路,具体如A*算法[14]、匈牙利算法[15]、随机树算法[16]、Voronoi图形算法[17]等。这类方法由于均是基于代价图进行规划的,需要进行离线存储好代价图,从而导致该方法较费时。随着人工智能技术的发展,仿生物群体捕食技术的算法被广泛应用于航线规划中,应用较广泛的算法如蜂群算法(bee colony algorithm )[18]、狼群算法(wolf swarm algorithm)[19]、遗传算法(genetic Algorithm)[20]以及粒子群算法(particle swarm optimization)[21]等。其中粒子群算法因搜索能力强、易仿真操作等优势被广泛应用,文献[22]提出了将粒子群算法进行航线预规划,并结合高斯伪谱法进行拟合进行航线规划的方法,该方法有效提高了收敛速度,航线平滑性更好。文献[23]提出了一种对变量进行控制优化的粒子群算法,将无人机与水下机器人进行协同路径规划,所得解可以追踪理论极值。

综上所述,当前无人机任务规划研究大都只考虑任务分配或者航迹规划方面内容,没有考虑现实状况下二者耦合情况; 同时,在无人机集群协同作战过程中,当无人机出现故障后,对各机的协同性和任务的有效性考虑不够充分。基于此,本论文主要研究以下内容:首先,运用匈牙利算法对故障后无人机机群进行快速队形重构;其次,介绍和分析了离散粒子群算法的2种改进,即基于柯西算子、非线性时变的变异更新策略,并与传统离散粒子群算法和遗传算法相比,有效提高收敛速度和最优解。最后,改进的离散粒子群优化算法成功地实现了地形、雷达等威胁约束下的任务规划。

1 问题描述

假设无人机集群在执行作战任务的过程中,因有无人机发生故障而无法继续执行任务进而退出战队序列,剩余无人机需调整状态,快速变换队形,替代故障机完成原定任务分配。为满足发生故障后,无人机群整体任务规划最优,需在合理规划的约束下将敌方目标按照最小成本代价分配给各型无人机。

由于任务分配是采用离线分配的模式,因此,任务分配完成后,各无人机根据设定的航迹点进行航迹规划,最终到达分配的目标处。

1.1 约束条件

多无人机协同任务规划是一种在多种约束条件下进行优化的问题,为便于算法建模求解,设定任务时序、时间协同、侦查次数、飞行高度、弹药量等约束条件。

1.1.1任务时序约束

针对同一敌方目标的打击任务必须在侦查任务完成后才能执行。假定对目标i执行侦查,打击任务的时刻依次设为tScout(i)、tAttack(i),二者需满足:

tScout(i)

(1)

其对应的优化约束指标函数为:

(2)

1.1.2时间协同约束

任务分配过程中,需要各类型无人机在规定的有限时间内完成对目标点的侦查和打击任务,超过该时间窗,任务可能会失败。假设,对此目标i的侦查或打击任务在tbegin(i)时刻开始执行,Δtmin表示其他无人机开始执行相同任务的最短时长,Δtmax表示其他无人机开始执行相同任务的最长时长,则对此目标任务执行完毕的时间窗tfinish(i)约束为:

tbegin(i)+Δtmin≤tfinish(i)≤tbegin(i)+Δtmax

(3)

其对应的优化约束指标函数为:

(4)

1.1.3侦查次数约束

侦查次数约束是指每架侦查无人机对敌方目标均需进行一次侦查,设xi, j∈{0,1}为决策变量,当分配无人机i执行侦查任务j时,xi, j的值为1,否则,其值为0。因此,侦查机群协同约束可表述为:

(5)

其对应的优化约束指标函数设置为:

(6)

1.1.4飞行高度约束

在无人机飞行过程中,需规避敌方侦测雷达信号以及山区地形威胁,设定hi表示第i段航线的航行高度,hmin表示最低飞行高度,hmax表示最高飞行高度,n表示维数,则航行高度可表示为:

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

(7)

其对应的优化约束指标函数为:

(8)

1.1.5弹药量约束

打击无人机所携带的弹药是有限的,故设定打击机对敌方目标执行攻击任务的次数约束。假设无人机执行任务分配时,对目标i执行打击的次数表示为MAttack(i),目标点集合表示为T,则打击次数可表示为:

(9)

其对应的优化约束指标函数为:

(10)

1.1.6雷达威胁约束

多无人机在执行任务飞行时需避免被敌方目标设置的雷达监测到,假设雷达探测范围表示为半球形,且不会被周边地形遮盖,则多无人机在执行任务的航线规划过程中,其雷达威胁模型设置为:

Lradar=(xk,yk,zk,rk)

(11)

式(11)中:xk、yk、zk表示雷达所在的中心位置;rk表示其监测半径。设定约束形式为:

(12)

其优化约束的指标函数为:

(13)

1.1.7山峰威胁约束

在实际自然环境中,多无人机协同执行任务分配时,还需要规避飞行区域内的山峰。因此,编队机群应与山体威胁保持一定航距。则山峰威胁约束的建模形式为:

(14)

其优化约束的指标函数为:

(15)

1.2 评价指标

多无人机协同任务规划必须满足以上各约束条件,使得各机协同优化性能达到最优,将无人机飞行总航程最短、航线有效规避威胁等纳入评价协同任务规划性能的指标中。

在实际作战空间中,无人机执行任务的航程越长,其被敌方目标反打击的概率也越大,因此,要求多无人机执行任务分配的飞行总航程最短。

考虑到无人机飞行过程中的航线规划,假设S1表示为无人机从起始点到敌方目标点需要付出的航程代价,为保证总体目标函数中权重占比差距不大,将航程代价进行归一化,设置为规划的飞行航线总里程与无人机起点到终点的直线里程的比值。具体表示为:

(16)

其中

li=sqrt[(xk+1-xk)2+(yk+1-yk)2+(zk+1-zk)2]

(17)

式(16)和式(17)中:η为航线维数;k为某一航迹点;x、y为该航线点在水平面上的坐标;z为航迹点的垂直高度;lstr为无人机起点到终点的直线里程。航线规划的最终结果是在三维空间内搜索出一系列的航线点,每个航线点与相邻的航线点相连,构成飞行航线。

综上,总体指标函数表示为:

S=S1+f1+f2+f3+f4+f5+fR+fM

(18)

式(18)中:S为总代价值;S1为航程代价;f1为时序约束惩罚值;f2为时间协同约束惩罚值;f3为侦查次数约束惩罚值;f4为飞行高度约束惩罚值;f5为弹药量约束惩罚值;fR为雷达威胁惩罚值;fM为山峰威胁惩罚值。

2 求解策略

2.1 匈牙利算法

故障下多无人机编队重分配是一种带有目标代价的指派问题,利用匈牙利算法能够将指派问题转换到算法的求解过程中,有效化解为数学问题进行解决。假设飞行过程中侦查机、打击机各出现一架无人机故障,剩余无人机需迅速调整队形,重新进行任务分配。

设无人机发生故障时位置集合为C={c1,c2,…,cp},重分配后无人机位置集合为N={n1,n2,…,nq},xij表示无人机从故障位置Ci到编队重分配后位置Nj的航程。航程集合X={xij|i=1,2,…,q}。给定q架侦查无人机和打击无人机,从Ci出发沿一条路径分配至Nj,即求解q条路径,使得此q架无人机的飞行总航程D最短,其表示为:

(19)

2.2 改进离散粒子群算法

2.2.1基本离散粒子群算法

根据基本粒子群算法,在离散空间中设计了交叉和变异策略,重新定义了粒子位置和速度的更新规则,表达式为:

Xi(t+1)=c2⊗F3(c1⊗F2(ω⊗F1(Xi(t),Pi(t)),Pg(t)))

(20)

式(20)中:Xi(t)=(xi1,xi2,…,xiz)表示粒子i在第t次迭代中的位置坐标;Pi(t)=(Pi1,Pi2,…,Piz)表示粒子i在第t次迭代中的个体极值;Pg(t)=(Pg1,Pg2,…,Pgz)表示全局极值。

2.2.2改进离散粒子群算法策略

1) 柯西变异策略。

针对DPSO易陷入局部最优的特点,引入柯西算子,能够有效提升算法的全局搜索能力,增强搜索空间。由于柯西分布函数在中点的步长较小,在两端的步长较大,从而对粒子个体产生较大扰动,使得粒子能够及时调整位置,避免陷入局部最优。同时,柯西分布峰值下降的坡率较缓且峰值较小,从而使得粒子经过变异后用于搜索的时间花费较少,进而能够把更多的时间用于全局寻优上,因此提高了改进算法的收敛速度。

经过离散化的算法采用如下改进的柯西变异公式,进行更新当前个体的最优位置,提高全局寻优能力。

(21)

2) 非线性时变策略。

DPSO借鉴遗传算法的思想,离散化基本粒子群算法的粒子位置和速度,更新为交叉和变异策略,变异策略使得粒子在迭代后期可以跳出局部最优,加强全局搜索,从而提升寻优能力。然而DPSO的变异策略较为简单,随着迭代的进行与时间的推移,不能及时地根据位置的变化做出相应的调整,从而导致寻优效果变差,为解决该问题,引入非线性时变的变异策略,有:

(22)

根据式(22),将变异策略分为3个阶段,其中T表示最大迭代次数,t表示当前阶段的迭代次数,由于变异策略处于算法的后期阶段,此时解的寻优性较差,然而利用非线性时变变异因子的前2个阶段能够加强粒子的变异能力,从而及时摆脱局部搜索,提高解的寻优能力,随着迭代的进行,适应值趋于最优,变异因子随之进入第3阶段的线性环节,从而加快算法的收敛速度。

此外,交叉因子ω、c1也会影响粒子的更新速度与寻优能力,为进一步提高算法的收敛速度与全局寻优能力,对交叉因子进行如下改进:

ω=0.25+0.8×(t/T)

(23)

c1=0.75-0.8×(t/T)

(24)

式(23)～(24)中:t为当前迭代次数;T为最大迭代次数;交叉因子ω随着迭代的进行而增加;c1随迭代次数的累加而减小。这使得算法在迭代开始阶段积极进行全局搜索,进而提升收敛速度,当随着迭代接近尾声,个体学习能力的加强使得种群不易陷入局部最优,同时,ω与c1的累加和为1,保证了粒子的寻优能力和收敛速度能力之和保持恒定,从而兼顾了算法收敛速度和寻优性的统一。

2.3 流程设计

依据改进离散粒子群算法与匈牙利算法相结合的方法,进行故障下多无人机编队重分配任务规划,多约束下的任务规划流程步骤如下。

步骤1:设定基本参数。给定无人机、目标点位置,设定环境障碍参数,包括雷达威胁的个数及监测中心坐标与半径,山峰威胁的个数及相关参数。

步骤2:初始化种群数量,设置粒子个体极值和全局极值的初值,以及最大迭代次数。

步骤3:开始进行迭代寻优,编译适应值函数并输入多约束条件,给定相应惩罚值,计算每次的代价值,并画出代价值函数曲线。

步骤4:根据每次迭代的代价值,判断粒子当前迭代值与个体极值的大小情况,如若连续10次迭代值相等,执行柯西变异策略,帮助跳出局部最优;如若不然,则不执行此策略,直接进入下一步骤。

步骤5:执行改进离散粒子群算法的交叉策略,并依据改进算法依次执行式(25)的的非线性时变的变异策略,并将当前迭代次数与最大迭代次数进行比较,直至执行完设定的最大迭代次数。

步骤6:依据任务分配得到的最终代价值、分配结果进行航线规划。

具体仿真流程设计如图1所示。

图1 故障下多无人机协同任务规划流程Fig.1 Flow chart of multi UAV cooperative mission planning under fault

3 仿真与分析

3.1 仿真参数设定

根据流程设计,在计算机硬件配置为Intel 5,1.19 GHz,运用软件Matlab 2020b进行仿真。设定迭代次数T=200,种群数N=400,飞行高度hmax=33、hmin=15;航迹维度η=20;打击机速度设定为3v0km/min、侦查机速度设定为4v0km/min,其中v0=10 km/min;时间协同过程的最短执行时间Δtmin=1 min、最长执行时间Δtmax=2 min。

设定三维地形环境为250 km×250 km×70 km的任务区域,包括5个雷达监测区域和2个山峰威胁区域,雷达区域在仿真环境中以半球进行绘制,山峰则用高低起伏不同的曲面进行绘制。其参数设置如表1所示。

表1 威胁参数Table 1 Threat parameters

3.2 仿真结果分析

将无人机拟化为质点,并忽略相关的动力学模型。假设15架无人机中有2架无人机因发生故障退出编队协同,则对剩余13架无人机执行编队重分配任务,分配为打击队形和侦查队形。故障下多无人机编队重分配参数如表2所示。

表2 故障下多无人机编队重分配参数Table 2 Multiple UAV formation fault allocation

根据匈牙利算法多无人机重编队的总分配航程最短的指标,得到剩余的多无人机重编队的前后位置信息(见表2)。故障下多无人机编队重分配结果如图2所示,五角形表示故障前15架无人机的队形排列,其中蓝色五角形为故障无人机,六角形表示故障后2个打击队形排列,四角形表示故障后的1个侦查队形排列。

图2 故障下多无人机编队重分配结果Fig.2 Reassignment results of multiple UAV formation under fault

基于改进离散粒子群算法的多无人机任务分配以8架打击型无人机和5架侦查型无人机执行对5个敌方目标的侦查、打击任务为背景进行仿真实验,无人机的起点为故障下多无人机编队重分配后的13架无人机坐标位置,5个敌方目标点位置的具体信息如表3所示。

表3 目标点区域范围参数Table 3 Parameters of target point area

为验证改进离散粒子群算法(IDPSO)的有效性,分别将改进算法与基本离散粒子群算法(DPSO)和遗传算法(GA)进行了对比仿真,并同时进行了30次、50次、100次蒙特卡罗仿真,求其平均值后得到如图3所示的算法对比图。

图3 改进算法对比结果Fig.3 Comparison results of improved algorithms

根据图3改进算法对比结果可以看出,经过30次、50次、100次蒙特卡罗仿真求平均值的多次仿真对比,改进离散粒子群算法(IDPSO)在历次迭代寻优性能上均优于基本离散粒子群算法(DPSO)和遗传算法(GA),寻优有效性较好。

为进一步验证改进算法在无人机任务规划中具有应用有效性,分别对改进离散粒子群算法(IDPSO)、基本离散粒子群算法(DPSO)、遗传算法(GA)进行三维空间中的建模仿真,如图4—图6所示。

图4 IDPSO打击任务分配结果Fig.4 IDPSO attack task allocation results

由于篇幅问题,仅针对故障后无人机的打击任务分配场景进行详细分析。无人机的航线规划均采用10个航迹点,通过图4—图6的三维仿真航迹可以看出,基于改进离散粒子群算法(IDPSO)的任务规划结果可以成功躲避威胁障碍,平滑性优于DPSO和GA,说明IDPSO任务分配的寻优有效性能够保证粒子群航线规划的成功;其次,在考虑其他相同约束的条件下,算法优化的目标主要集中在总航程最短,由仿真图4(c)与图5(c)对比可以看出,与传统离散粒子群算法相比,IDPSO所求结果中,各无人机选择距离本机位置更近的目标点进行打击,说明了IDPSO具有更佳的求解特性;由图4和图6的对比得知,改进离散粒子群算法(IDPSO)的任务分配结果满足打击机的弹药量约束,而遗传算法(GA)的分配未对2、5号目标点进行打击,导致任务分配的失败,由此规划出的航线也未能避开设置的障碍威胁。这些仿真结果验证了改进算法在求解复杂优化问题时能够得到优于其他算法的解。

图5 DPSO打击任务分配结果Fig.5 DPSO attack task allocation results

图6 GA打击任务分配结果Fig.6 GA attack task allocation results

针对故障后多无人机任务重分配问题,基于改进离散粒子群算法(IDPSO)对侦查、打击全场景的分配结果进行仿真实验,图7中红实线表示侦查机任务规划,蓝实线为打击机任务规划。根据图7信息可知,各无人机均在一定高度上飞行且有效避障,满足飞行高度约束条件;由图8(a)侦查分配结果得知,侦查机对每个目标均进行了一次侦查任务,即满足侦查次数约束条件。根据图9(a)打击分配结果可以看出,打击机对不同标号的目标进行了不同架次的打击任务,满足弹药量约束条件。此外,由图8(b)和图9(b)的协同飞行时间比较可知,侦查机群在12～19 min内可以完成侦查任务;打击机群随后在22～38 min内完成打击任务,满足先侦查再打击的时序约束条件;且各侦查机和各打击机在执行任务时,均具有1～2 min共同的时间窗,即满足时间协同约束。

图7 故障后多无人机任务重分配结果Fig.7 Task reassignment results of multiple UAVs under fault

图8 故障后侦查机群任务重分配结果Fig.8 Task reassignment results of scout UAVs under fault

图9 故障后打击机群任务重分配结果Fig.9 Task reassignment results of attack UAVs under fault

综上可知,采用13架无人机进行仿真具有较好的一般性,能够实现侦查过程的一对一场景和打击过程的多对一场景,仿真结果也说明了本文所提算法的有效性。

4 结论

针对故障下多无人机执行多目标任务规划的问题,本文提出了利用匈牙利算法与改进离散粒子群算法进行结合的求解方法。首先利用匈牙利算法进行故障下无人机群编队重规划,然后基于柯西变异策略、非线性时变策略改进的离散粒子群算法,将剩余无人机进行任务重分配,为了得到公正且信服的评估,将各无人机在多种约束条件下进行了多组蒙特卡罗模拟仿真,并与传统离散粒子群算法和遗传算法进行了充分比较,说明了本文所提出的改进DPSO的有效性。主要研究结果总结如下:

1) 改进DPSO可以比传统DPSO和GA获得更好的最优解。

2) 改进DPSO的收敛速度比DPSO和GA更快。

3) 改进DPSO可以优化得到更佳的分配方案,从而降低任务规划成本,具有一定现实意义。

本研究仅考虑了故障无人机无法继续执行任务的场景,下一步将在轻度故障可继续执行相应任务的策略方法上进行探索跟进。