交互策略改进MOFA进化的多UAV协同航迹规划

来 磊, 邹 鲲, 吴德伟, 李保中

(空军工程大学信息与导航学院, 陕西 西安 710077)

0 引 言

无人机(unmanned aerial vehicle, UAV)航迹规划是指在自身物理条件约束下,综合考虑航行中所受地形威胁、防空威胁、燃料损耗等外界因素,为UAV计算出利于任务执行的最优航迹。通常,所规划航迹的优劣在一定程度上影响着UAV任务的成败,因此作为UAV关键技术之一的航迹规划一直是国内外学者的研究热点。

若按规划中UAV的数量区分,航迹规划分为单UAV航迹规划和多UAV协同航迹规划。单UAV航迹规划因研究起步较早、模型限制因素较少等原因,目前的研究成果相对较为成熟。近年,随着人工智能技术发展和现代战争模式向智能化转变,各军事发达国家纷纷制定多个UAV集群研究项目;随之发展,需要高效、实时的多UAV协同航迹规划成为亟待提升的关键技术之一。相比于单UAV航迹规划,多UAV协同航迹规划还需考虑与众多相邻UAV的位置约束,因此其优化复杂度相对较高。常规的多UAV协同航迹规划方法主要有人工势场法、贝塞尔曲线法、Voronoi图、Djikstra算法等[1-2]。另外,智能优化算法在解决非确定性多项式问题时所表现出的优异性能,使其成为解决协同航迹问题中最常见的方法,文献[3]对蚁群算法进行改进并将其应用到UAV的协同三维航迹规划中;文献[4]提出一种基于空间模糊表示和差分进化相结合的文化算法,并应用于协同航迹搜索中;文献[5]将鸽群优化算法应用到UAV协同航迹规划中;文献[6]提出一种协同进化的遗传算法,并将其应用到UAV协同航迹规划中;文献[7]将粒子群算法用于协同航迹规划中。随后,鉴于单目标航迹优化中各航迹评价函数间通常存在相互冲突、制约的不足,研究人员将航迹规划作为多目标优化问题,提出了多目标优化的UAV航迹规划方法,文献[8]应用非支配排序遗传算法,提出一种针对多无人机的协同航迹规划方法;文献[9-11]利用改进的粒子群算法求解多目标协同航迹;文献[12]提出了一种基于增强型遗传算法的多目标UAV协同航迹规划方法;文献[13]将萤火虫算法(firefly algorithm, FA)用于多目标的航迹规划中。对于多目标的航迹规划方法,算法会以不同航迹评价目标为侧重点,生成多条优化航迹,这与多目标优化问题中Pareto最优解集相对应。但采用这种多目标航迹优化策略的不足之处在于:航迹评价目标数量较多时,非支配解数量将会增多,算法对种群的选择能力变差,相应算法的性能衰减严重;此外,最优非支配解数量增多意味着备选的最优航迹数量增多,如何从众多航迹中选取符合任务特点的最终航迹也成为新的问题。

通过对众多UAV航迹规划的目标分析可以看出,UAV在不同任务背景下的航迹侧重点是不一样的。如在UAV突防任务中,最优航迹具体表现为能够避开对方防空系统打击、顺利到达目标点进行侦查打击;而实际中躲避对方侦查最有效的方式就是贴地飞行,即极限降低飞行高度以躲避对方侦查。因此,在多目标萤火虫算法(multi-objective firefly algorithm, MOFA)基础上，本文根据不同任务、不同航迹侧重点的现实需要,提出了一种交互策略改进MOFA(improved MOFA, IMOFA)的多UAV协同航迹规划方法,该方法将UAV协同航迹规划转化为多目标优化问题,并以多种策略交互改进的FA作为航迹寻优算法;同时,加入任务偏好信息,根据所设置的偏好参考点选择最优航迹,从而提高最优航迹的搜索效率。本文所提方法特点表现为:① 采用变量分解策略将协同航迹规划中FA的大规模变量分解为多个变量,以降低算法搜索复杂度;② 采用Tent混沌初始化策略以提高FA的全局收敛性，以及算法收敛速度;③ 提出多种群循环分裂合并策略以整体平衡FA的搜索全局性和局部性;④ 采用双极偏好占优机制以突出不同任务航迹的需要,同时提高航迹有限数量下的多样性;⑤ 设计协同度指标以在多样性选取不同UAV航迹时提高航迹间的协同性。通过以上策略在算法不同阶段的有机结合,提高多目标UAV协同航迹规划的整体效能。

1 IMOFA

1.1 MOFA

FA来源于模拟自然界中萤火虫的群体行为[14-18],其特点在于算法简单、调整参数较少、更易于实现。该算法假设每个萤火虫所在位置代表可行解,萤火虫的发光亮度代表解的优越性;发光亮度高的萤火虫具有较高的吸引度,会吸引发光亮度低的萤火虫向自身运动,从而更新自身的位置,获得新的可行解;萤火虫通过以上亮度吸引机制,在解空间中不断搜索寻找最优解。

假设萤火虫i比j的亮度更高,则萤火虫i对j的吸引力为

(1)

式中:rij为萤火虫i到j的距离;β0为最大吸引力;γ为光吸收系数。

相应萤火虫j位置更新公式为

xj=xj+βij(xi-xj)+αε

(2)

式中:α为常系数;ε为随机数向量。

在多目标优化的MOFA中,最优解的搜索策略与上述策略相同,不同处主要是萤火虫亮度评价方法和外部档案维护更新。

单目标FA中可以用目标函数值大小表示萤火虫的亮度,但多目标函数中各个函数可能存在相互制约的情况,无法采用其中某一个目标函数值来代表亮度。因此,必须应用Pareto支配表示解的优劣关系[19-22],既萤火虫iPareto支配萤火虫j,则表示萤火虫i的亮度高于萤火虫j。

另外,MOFA的最优解是一组Pareto支配解所组成的集合,算法在每次迭代后都会产生新的Pareto支配解,因此需要对迭代前后的解集进行合并更新,既建立外部档案;随着迭代次数的增加,外部档案的规模将相应增大,MOFA采用自适应网格法对解的密度进行计算[19],将网格密度大的解随机剔除以实现对外部档案的多样性维护。

1.2 变量分解策略

在采用进化算法对航迹进行优化时,种群个体中变量的个数代表了航迹点的个数;航迹点个数越多,相应航迹规划的精准度越高;因此,通常希望变量个数越多越好,但大规模变量意味算法复杂度增加。另外,多UAV航迹规划使种群个体中变量的数量更加庞大。本文采用合作框架下的大规模变量分解策略将变量进行分解,将D维优化变量分解成s个Di维的子变量,每个子变量代表一个UAV的航迹点组合,相应的每个子变量由一个子种群进行迭代进化。在UAV协同航迹规划中,单个UAV航迹的变化有时会引起其他UAV理想航迹的变动,因此各子种群在航迹优化时会以航迹基本约束条件和协同约束条件共同关联整体变量与子变量间的关系。

1.3 Tent混沌初始化策略

在智能优化算法中,群体位置的初始化效果对于搜索全局最优值以及算法的收敛速度都有一定的影响,通常初始位置分布越均匀,算法越易于快速收敛。混沌映射在众多研究成果中已被证明是目前智能优化算法中最有效的初始化策略,常用的混沌映射有Tent映射和Logistic映射[23],但Tent映射的遍历性相对较好,因此本文选择Tent映射对萤火虫位置初始化进行改进,Tent映射可表示为

(3)

式中:yt为混沌变量。

1.4 多种群循环分裂合并策略

对FA中位置更新公式进行分析可以看出,位置更新主要受到吸引力β和参数α的影响;α取值较大时算法的全局探索能力较强,取值较小则局部搜索能力强;对于吸引力β,其主要受到距离r的影响,随着算法迭代次数的递增,β逐渐趋于最大,则算法的全局探索能力逐步减低;综合分析,算法在前期注重全局探索,但在迭代后期则偏于局部寻优,难于在整体上平衡全局与局部寻优的关系。

应对此不足,采用多种群分裂合并策略进行改进,具体策略为:原FA基础上,在每次算法迭代过程中,当萤火虫根据式(2)进行位置更新后,根据亮度对萤火虫进行排序,并将萤火虫分裂成m个种群、每个种群有l个萤火虫;种群分裂原则为:亮度第1萤火虫分配到种群1,亮度第2萤火虫分配到种群2,亮度第m萤火虫分配到种群m,亮度第m+1萤火虫分配到种群1,以此类推直至分配完所有萤火虫,如图1所示。

图1 种群分裂示意图

分裂后的子种群在各自种群内根据位置更新式(2)进行kp次迭代寻优。同时,为了改善各子种群亮度最差个体的亮度值,将总群体中亮度最高的精英个体作为参考点,使最差个体始终向精英个体运动,即

xworst=xworst+β(xbest-xworst)+αε

(4)

另外,为了使算法在迭代后期不陷入局部最优,子种群在每次迭代过程中,在亮度最优萤火虫随机运动中加入Levy飞行随机扰动[24-25],即

xbest i=xbest i⊕Levy

(5)

式中:i表示子种群的编号;⊕表示点乘;Levy表示Levy飞行生成的随机向量。

当子种群完成迭代后,各子种群进行合并同时进行位置更新,对种群分裂、合并反复进行,直到达到算法终止条件。

1.5 确定偏好下多样性维护策略

在众多确定偏好的多目标进化算法中,基于参考点设定的方法因其简单有效从而得以广泛应用[26-29]。偏好下的航迹规划是指UAV根据任务需要侧重于不同目标函数,如侧重隐蔽偏好实际上是UAV在突防飞行过程中在平衡威胁和距离代价基础上,尽量贴地飞行降低飞行高度代价以保持隐蔽性。因此,在众多Pareto非支配解中可根据经验设定侧重飞行高度代价的参考点,同时以双极偏好占优方法[30]选取偏重隐蔽性的最优航迹,其基本策略首先计算解的标志值:

(6)

式中:g为参考点;w为目标空间中任意点;p为目标数。

根据flag值对种群进行分层非支配排序,同时计算每一层解的相对贴近度,计算方法为

c=d-/(d++d-)

(7)

式中:d-为到负参考点的欧式距离;d+为到正参考点的欧式距离。

最后通过不同解间相对贴近度差值与所设定阈值的比较对非支配解进行裁剪,以保持解的多样性。

另外,对于多UAV的协同航迹规划,各UAV航迹间的协同性也是衡量航迹优劣的重要方面,因此为了能从众多非支配解中选出最优航迹,本文提出了协同度排序以便选出最优协同航迹,协同度分别由时间协同度和空间协同度组成,其中时间协同度表示为

(8)

式中:ti为UAVi到达目的地的时间;tmin为到达目的地的最小时间;tmax为到达目的地的最大时间。

距离协同度为

(9)

式中:n为除各UAV自身外其他UAV航迹的数量;li为与第i个航迹间的安全距离标志,如与第i个航迹间满足最小安全距离,则li=1，反之li=0。

则总的协同度为

cd=cdt+cds

(10)

在选择协同性较好航迹时,可对协同度进行排序,并选取靠前航迹作为最优航迹。

2 航迹模型建立

2.1 航迹评价模型

(1)航迹距离评价

航迹距离是指UAV从飞行起点到终点所经过的空间距离,UAV在飞行过程中受到自身动力能源和任务完成时间的限制,通常希望飞行距离越短越好;同时,飞行距离短、留空时间少,相应也提高了UAV的安全性。因此,将航迹距离评价函数定义为

(11)

式中:lst为起点到终点的直线距离;ltotal为实际飞行的总长度。

(2)航迹威胁评价

对于航迹威胁主要指被防空系统所探测照射到的威胁,飞行航迹远离或穿越防空探测区域越少,则航迹威胁越小;反之,航迹威胁越大。航迹威胁评价函数可定义为

(12)

式中:lrd为航迹中穿越防空探测区域的总长度;dri为第i个防空探测区域的直径长度;nr为防空探测区域的数量。

(3)航迹隐蔽评价

对于UAV突防等任务,提高其隐蔽性最有效的方法是保持低空或超低空飞行,因此航迹高度在一定程度上可以说明其飞行隐蔽性,将航迹隐蔽评价函数定义为

fh=(have-hmin)/(hmax-hmin)

(13)

式中:have为整体航迹的平均高度;hmin为UAV飞行最低高度;hmax为UAV飞行最高高度。

2.2 航迹约束模型

由于UAV自身的物理限制和性能约束,在飞行过程中其航迹必须满足一些基本的约束条件,包括:最大航行距离约束、最大飞行角度约束、飞行高度约束,对以上约束条件的函数表达式本文不再详述,详见文献[31]。

另外,除了基本约束条件外,对于多UAV协同航迹规划问题,不同UAV航迹之间必须满足空间约束和时间约束。

(1)空间约束

空间约束实际上是指UAV间的无碰撞条件,即UAV在飞行过程中,UAV间在任意时刻必须保持一定的安全距离,以避免发生碰撞。假设UAVi和j在时刻t的位置表示为pi(t)和pj(t),则此时UAV间的间隔距离必须满足:

‖pi(t)-pj(t)‖≥dsafe,i≠j

(14)

式中:dsafe为航迹间的最小安全距离。

(2)时间约束

时间约束是指UAV为最大化满足任务的执行效率,通常要求各UAV能够同时到达目标任务区域。假设UAV沿既定航迹匀速飞行,飞行速度范围为v∈[vmin,vmax],UAVi的飞行航迹距离为ltotal i,则UAVi的飞行时间范围为

ti∈[tmin i,tmax i]=[ltotal i/vmin,ltotal i/vmax]

(15)

时间约束条件则要求

(16)

式中:nUAV为UAV的数量。该式表示各UAV到达时间有交集才能同时到达。

另外,本文对于解决带有约束条件的优化问题所采用方法是将约束条件转化为惩罚函数,从而通过惩罚值使目标函数逼近最优解。

2.3 多目标协同航迹规划模型

本文针对传统航迹规划中将各评价函数进行简单的加权求和处理的不足,建立以航迹距离评价、航迹威胁评价和航迹隐蔽评价为指标的多目标优化模型,所建立的优化模型为

(17)

式中:x为可行航迹点;s.t.1指最大航行距离、最大飞行角度和飞行高度基本约束条件;s.t.2指式(14)中空间约束和式(16)中时间约束的协同约束条件。

相对于单目标优化,多目标优化的解不再是单个最优解,而是一组Pareto最优解集。假设x1、x2为两个可行解,若

(18)

则解x1Pareto支配解x2;如果不存在支配x1的解,则x1为Pareto最优解;而所有Pareto最优解组成的集合称为Pareto最优解集。多目标航迹规划实际上求解的Pareto最优解集就是满足航迹要求的可行航迹点解集。

3 IMOFA协同航迹规划

协同航迹规划实质是在满足基本约束条件基础上,同时满足各UAV间协同约束条件,并达到航迹评价函数最优的航迹点组合。航迹只有首先满足基本约束条件,才能在此基础上满足协同约束条件。因此,本文将IMOFA协同航迹进化算法流程划分为两个阶段:第1阶段由各UAV所属子种群在仅考虑基本约束条件下进行单独进化,寻找最优航迹;第2阶段由各子种群在第1阶段进化基础上,通过合作进化同时考虑基本约束条件和协同约束条件搜索最优协同航迹。算法具体流程如图2所示。

图2 算法流程图

第1阶段:

步骤 1对算法各参数进行初始化设置;

步骤 2采用变量分解策略将大规模变量分解成多个子变量,每个子变量对应一个UAV航迹点组合;

步骤 3采用Tent混沌初始化策略式(3)对各个子种群位置进行初始化;

步骤 4采用多种群循环分裂策略式(2)～式(5)对各子种群中萤火虫位置进行更新计算,此时只考虑航迹基本约束模型并应用式(17)对萤火虫位置进行寻优;

步骤 5采用确定偏好下的多样性维护策略式(7)对各子种群进行外部档案更新与维护;

步骤 6判断算法是否满足第1阶段最大迭代次数,如满足进入下一步;否则转至步骤4。

第2阶段:

步骤 7分别从各子种群中选取部分最优非支配解,形成新的初始子种群;

步骤 8同时在考虑基本约束和协同约束条件下,采用多种群循环分裂策略式(2)～式(5)对各子种群中萤火虫位置进行更新计算;

步骤 9采用确定偏好下多样性维护策略式(7)和协同度指标式(10)进行外部档案更新与维护;

步骤 10判断算法是否满足迭代终止条件,满足则结束;不满足则转至步骤8。

4 实验验证

为验证本文所提方法的有效性,仿真验证实验分为多目标测试函数验证实验和多目标航迹规划测试实验两部分。所用实验平台配置参数为:Intel Core i5-6200U CPU @ 2.3 GHz,内存8.0 GB,编程环境为Matlab 2019b。

4.1 多目标测试函数实验

实验中将两目标函数ZDT1、ZDT3和三目标函数DTLZ2作为测试函数,以验证本文所提方法对标准测试函数的有效性。分别采用MOFA和本文所提IMOFA对测试函数进行优化,并与真实的Pareto前沿进行对比。两种算法种群大小均设为100,变量维数为30,算法最大迭代次数为1 000。

图3为IMOFA和MOFA在3种测试函数上的对比效果图,其中IMOFA在ZDT1函数中正负参考点设为(0.3,0.6)和(0.2,0.4),ZDT3函数中正负参考点设为(0.1,0.2)和(0.5,0.2),在DTLZ2函数中正负参考点设为(0.5,0.5,0.7)和(0.2,0.3,0.3)。

图3 测试函数优化性能对比

通过图3中对比效果可以看出,本文IMOFA相对于MOFA所优化的结果更逼近于Pareto真实前沿;另外,本文所提IMOFA通过设置偏好参考点,可以使算法最后得到的优化结果趋于所设置的参考点,从而有针对性的筛选出满足需求的最优结果,在一定程度上提高算法的运行效率。

4.2 多目标航迹规划实验

实验中选择100 km×100 km三维山地空间范围对UAV协同航迹规划进行仿真,并在坐标点(13,59)km、(36,52)km、(71,61)km、(51,42)km处设置对空威胁区域。UAV数量设定为3架,起始坐标为(1,1)km,目标点为(100,100)km。IMOFA中种群大小为100,变量维数即航迹点数设为50。对于航迹选择,以隐蔽性、贴地飞行为侧重点,在众多航迹解中选择飞行高度代价相对较低的非支配解作为最终航迹。图4为各UAV所生成的一组最优航迹解,其中图4(a)、图4(b)分别为三维效果图和二维效果图。

图4 多组航迹效果图

图4中3种不同颜色曲线代表不同UAV优化轨迹,每个UAV从非支配解中选取5组最优航迹。从图4(a)三维效果图中可以看出,各优化航迹均以隐蔽性为侧重点沿较低地形起伏进行规划,同时兼顾航迹路径最短和对空威胁度最小原则。从图4(b)二维航迹中可以看出,各UAV航迹基本沿起始点至目标点间的直线进行规划,使路径达到最短;另外,各优化航迹基本躲避了对空威胁的探测区域。

图5为5组优化航迹中的一组。

图5 最优航迹组合

从图5效果图中可以看出,各UAV航迹在满足隐蔽性、最短路径和威胁度最小的约束条件下,不同UAV航迹间还满足航迹的协同性,即最小安全距离和时间协同性。

5 结 论

在UAV的实际应用中,航迹规划通常属于不同目标相互冲突、相互制约的多目标优化问题,同时在不同任务情景下对不同目标的侧重度是不一样的。根据上述特征,本文提出了一种交互策略IMOFA的多UAV协同航迹规划方法,该方法采用变量分解策略、Tent混沌初始化策略、多种群循环分裂合并策略提高FA算法的最优解搜索能力;采用双极偏好占优机制突出不同任务背景对不同优化目标的侧重点;并设计协同度指标提高不同UAV间的航迹协同性;通过以上策略在算法不同阶段的有机结合,提高多目标UAV协同航迹规划的整体效能。

实验中以UAV飞行隐蔽性为优化目标侧重点对算法进行验证,实验结果表明本文所提方法可以根据航迹侧重偏好生成多组协同航迹,所生成航迹均可平衡优化目标间的冲突,且侧重于偏好目标;另外,不同UAV航迹间满足协同性的要求。