基于NSGA-Ⅲ算法的多无人机协同航迹规划

袁梦顺陈 谋吴庆宪

(南京航空航天大学 自动化学院,南京 210016)

0 引 言

在复杂的战场环境中,通常需要多架无人机协同作战,以完成复杂任务[1]。协同航迹规划能显著提升多无人机协同作战效能,已经得到越来越多研究人员的重视。协同航迹规划通常需要多无人机同时从起始位置起飞,在飞行过程中保持安全距离且规避障碍物和威胁区域,最终同时到达目标位置,执行打击任务。

在协同航迹规划问题求解中,陈志旺等[2]应用定向A*算法,有效完成了多无人机同时集结的任务;赵明等[3]采用空间模糊文化算法,能在三维环境中快速规划出多条可行航迹;韩庆田[4]利用Dubins曲线,提出了粒子群改进算法,具有全局寻优性;徐瑞莲等[5]改进了差分进化算法,较好地处理了协同航迹规划中的约束条件。

在上述的航迹规划算法中,通常将多项优化目标直接加权为单个目标进行优化,未考虑多项目标之间的制约关系,不能较好地处理某些目标。非支配排序遗传算法(NSGA:Non-dominated Sorting Genetic Algorithm)是一种多目标进化算法,能同时优化多个目标。周德云等[6]应用NSGA-Ⅱ算法,设置航迹距离和航迹安全两个目标,并且考虑时空约束,能为多无人机规划出协同航迹。但时空约束未加入非支配排序过程中,需要进行额外的排序,不能完全体现出非支配解的优越性。同时NSGA-Ⅱ算法在选择下一代种群的过程中,拥挤距离排序运算量较大,不适合处理高维目标优化问题。Deb等[7]提出了NSGA-Ⅲ算法,算法总体框架与NSGA-Ⅱ算法大致相同,主要改进为用参考点法替换了拥挤距离排序,使算法运算量减小且能保持种群个体的多样性,因此能解决高维优化问题。

基于以上研究,为使算法能给多架无人机规划出安全、平滑且代价较小的航迹,且保持多个目标独立优化,笔者提出一种NSGA-Ⅲ算法与势场蚁群算法结合的多目标进化算法。算法将威胁区域设置为禁飞区,其处理方式与障碍物相同。笔者算法改进如下:势场蚁群算法首先对地图进行势场构建,使距离障碍物较近的节点不易被选择,并且引导搜索方向,加快算法收敛速度。随后利用改进NSGA-Ⅲ算法进行迭代搜索,其中设计了临界层选择方法和进化算法等。由于势场具有引导性且参考点法运算量较小,笔者算法收敛速度较快,能在二维和三维栅格地图中进行协同航迹规划。仿真实验表明,规划出的协同航迹能满足期望需求,且3个目标函数值均较优。

1 问题描述

在协同航迹规划中,多架无人机由起始位置起飞,前往目标位置并执行任务。对航迹规划中的约束条件,首先需要考虑无人机自身性能约束、地形和威胁区域[8]。其次需要考虑空间协同约束,即各无人机在飞行时,需保持适当的安全距离。同时还需要考虑时间协同约束,即多无人机在执行任务时,需同时到达目标位置,以提升任务成功率。在航迹规划中,规划空间为栅格地图,每个栅格都是一个搜索节点[9]。因此,协同航迹规划问题可以描述为,在满足约束条件的前提下,从栅格地图节点集合中为各无人机选择连续的航迹节点,使各无人机沿航迹节点飞行时能同时到达目标位置,且代价较小。多无人机从相同起始位置起飞,并且到达相同目标位置的协同航迹如图1所示。

图1 协同航迹规划示意图Fig.1 Diagram of cooperative path planning

多无人机协同航迹规划可以视为多目标优化问题,且各目标往往是互相制约的,某目标函数值的减小可能会导致其他目标函数值的增大,多个目标不能一起达到最优[10]。笔者的目标函数设计为函数值越小时,目标越优,理想最优值为零。若将多个目标直接加权为一个目标,求得的解表现较差,所以需要对多个目标进行独立优化。在多目标优化问题中,不存在使所有目标函数最优的解,而是非支配解[11]。非支配解的定义为:在求解多目标优化问题时,对n个目标函数fi(x),i=1,…,n,任意两个可行解Xa和Xb,如果1)∀i=1,…,n,都有fi(Xa)≤fi(Xb)成立;2)∃i=1,…,n,使fi(Xa)

对一个可行解,若不存在其他解能支配它,则该解被视为非支配解(非支配个体)。多目标进化算法得到的解为非支配解集,需根据具体情况选择满意的解。

1.1 多约束模型

在多目标优化问题中,需要将约束转换为数学模型,便于进行优化。建立时空约束模型以两架无人机为例,多架无人机时累加即可。下面详细给出航迹代价、空间协同约束和时间协同约束的数学模型。

1)航迹代价模型。在航迹规划中,航迹代价有多种计算公式。受无人机油耗限制,航迹代价需综合考虑长度、爬升高度和转弯行为,因此采用的计算公式[12]如下

其中n为航迹段的总数,li为第i段航迹的长度,此项计算长度代价;hi为第i段航迹的爬升高度值,此项计算爬升高度代价;gi为进入第i段航迹的转弯角度变化值,此项计算转弯行为代价;k1、k2和k3分别为长度代价、爬升高度代价和转弯行为代价的权重值,各项权重的选择与具体飞行任务有关。

2)空间协同约束模型。多无人机在飞往目标位置的过程中,相同时刻需保持适当的安全距离[13]。设在时刻t,第i架无人机所处的坐标点为Xi(t),第j架无人机所处的坐标点为Xj(t),则两无人机坐标需满足以下关系

其中‖Xi(t)-Xj(t)‖为两无人机之间的欧氏距离,dsafe为安全距离,N*为大于0的正整数。在起始位置和目标位置附近,各无人机可能不可避免地距离较近,所以重设起始位置和目标位置附近的安全距离。以起始和目标位置中心为圆心,作半径为R的圆,只要Xi(t)和Xj(t)有一个在圆内,dsafe取d1,否则dsafe取d2,d1,d2根据实际情况设定。

空间协同函数值在航迹点的计算公式如下

整条航迹的空间协同代价fspace(x)计算公式如下

其中p,q分别为两条航迹各自的航迹段数量。

3)时间协同约束模型。在协同航迹规划中,多无人机往往需要同时到达目标位置,完成协同任务。参照文献[6]中的时间协同约束模型,设第i架无人机的速度范围为vi=[vimin,vimax],航迹长度为Li,第j架无人机的速度范围为vj=[vjmin,vjmax],航迹长度为Lj,则两无人机飞行用时的范围区间分别为

同时到达需要两无人机满足下列条件

其中max函数取两者中的较大值,min函数取较小值。两无人机的飞行时间区间只要有交集,通过调整速度,即可同时到达目标位置。整条航迹的时间协同代价ftime(x)计算公式如下

1.2 目标优化问题模型

建立上述约束模型后,设置航迹代价、空间协同代价和时间协同代价为3个目标,多目标进化算法数学模型如下

各个目标的函数值越小时,算法搜索结果越优。

2 基于NSGA-Ⅲ算法的协同航迹规划

对协同航迹规划,需要将航迹代价、空间协同约束和时间协同约束设置到航迹搜索过程中。针对这些约束,笔者以NSGA-Ⅲ算法为基础,将上述需要考虑的约束转换为多个目标,其中进化算法选用势场蚁群算法,得到改进NSGA-Ⅲ算法。算法首先对地图进行势场构建,使距离障碍物较近的节点不易被选择,并且引导搜索方向。然后对航迹代价、空间协同约束和时间协同约束进行数学建模,转换为目标函数,设置为NSGA-Ⅲ算法的多个目标。最后对NSGA-Ⅲ算法进行具体设计,其中包括临界层选择方法和进化算法等,完成了基于NSGA-Ⅲ算法的协同航迹规划算法的设计。

将各无人机的航迹规划视为子问题,算法根据无人机数量产生多个种群,各种群为各无人机搜索航迹。各个种群独立进化,个体在进行空间和时间协同代价计算时,需依靠其他种群的代表个体。在算法迭代过程中,为了保证各无人机之间不发生碰撞,选取各种群中非支配且空间协同代价最小的个体作为代表个体。迭代结束时,算法选取各种群的代表个体作为各无人机的最终航迹。

2.1 临界层选择方法设计

NSGA-Ⅲ算法通过非支配排序,得到种群的非支配排序集。在选择下一代种群时,首先从第1层非支配集合中选择,然后从第2层非支配集合中选择,依此类推,直至得到下一代进化种群。当某非支配层的个体不需全部选取时,将此层标记为临界层,并采用临界层选择方法选取部分个体,添加入下一代种群。笔者采用参考点法进行临界层选择。首先进行参考点设置,生成内层与外层两个参考点平面,内层参考点密集,较优解往往分布在内层,外层参考点稀疏,以此减少参考点的数量,并保证参考点的广泛分布。参考点分布图如图2所示。

图2 参考点分布图Fig.2 Distribution of reference points

然后,将种群个体转换为与目标函数相关的向量,并且将其进行归一化处理,方便后续计算。随后,将参考点与个体关联起来,参考点和个体之间的关系可能是一对一,一对多或无对应关系。最后,需要依据关联关系,从临界层中选择出较优的个体进入下一代种群。此方法减小了算法的运算量,且能保持种群个体的多样性。

2.2 进化算法设计

其中ρ(0<ρ<1)为挥发系数,τa(t)为t时刻节点a的信息素浓度,w为本次航迹产生信息素的权重,Csum为本次航迹的综合代价,Csum的计算方式如下

2.3 算法流程

NSGA-Ⅲ算法中的进化算法一般为遗传算法,由于遗传算法在解决三维航迹规划问题时表现一般[14],笔者采用势场蚁群算法进行种群个体的航迹规划。势场蚁群算法首先对障碍物添加斥力场,使航迹远离障碍物。其次对目标位置添加引力场,对航迹搜索方向进行引导,加快算法收敛速度。然后,在蚂蚁进行邻节点搜索时,添加无人机约束条件限制,选择非障碍物节点,使航迹能实际可飞。最后,笔者将航迹代价、空间协同代价和时间协同代价添加到信息素更新规则中,计算公式如下协同航迹规划算法主程序以NSGA-Ⅲ算法为基础,其中进化算法选用势场蚁群算法,算法主程序步骤如下:

1)初始化无人机数量M,子种群内个体数量N;

2)利用势场蚁群算法产生第1代各种群,从各种群中随机选出初次代表个体,此时t=1;

3)通过势场蚁群算法产生子代种群,合并父代和子代构成混合种群;

4)对种群中的个体进行非支配排序,构成非支配排序集;

5)从中选取N个优秀个体,构成下一代种群;

6)从下一代种群中选出不受其他解支配且空间协同代价最小的个体作为该种群的代表个体;

7)如果符合终止条件,则执行下一步骤;否则t=t+1,返回至步骤3);

8)输出各无人机航迹,进行可视化展示。

流程图如图3所示。

图3 改进NSGA-Ⅲ算法流程图Fig.3 Flow chart of improved NSGA-Ⅲalgorithm

3 仿真结果与分析

为验证算法的有效性,以Windows 10为平台,Python3.6语言为编程环境进行仿真实验。实验的硬件平台为:Intel Core i5 4210M处理器,主频2.6 GHz,内存8 GByte。笔者算法能解决多种情况下的协同航迹规划问题。多无人机由相同起始位置起飞,并且同时到达相同目标位置,为最难求解的情况,所以在此情况下对笔者算法进行仿真验证。仿真实验在相同硬件平台的条件下,用二维和三维地图,对笔者的协同航迹规划算法进行了验证。

3.1 二维地图

在二维栅格地图中,设置最小栅格的长度和宽度均为100 m。在规格为30×30的栅格地图1中,设置3架无人机,使用NSGA-Ⅲ算法进行航迹搜索。在地图中,方块区域表示障碍物,圆形区域表示威胁。设定无人机的起始位置为圆域,圆心为(0.55 km,0.55 km),半径为0.3 km;目标位置同样为圆域,圆心为(2.55 km,2.55 km),半径为0.3 km。种群的代表个体在迭代过程中的综合代价变化曲线如图4所示。

由图4分析可知,在初始迭代过程中,代表个体的综合代价下降较快,说明此时已能得到较优航迹。在后续迭代过程中,综合代价变化较小,最终达到比较稳定的值。选取各种群的代表个体作为各无人机的最终航迹,协同航迹可视化结果如图5所示。

图4 二维地图综合代价变化曲线Fig.4 The change curve of comprehensive cost for two dimensional map

图5 二维地图协同规划航迹Fig.5 Cooperative planning path of two dimensional map

由图5可看出,3架无人机航迹始终保持安全距离,且航迹符合无人机自身约束条件。各无人机最终航迹的各项指标如表1所示。

由表1数据可知,3架无人机的航迹代价均比较小,空间协同代价和时间协同代价为0,说明3架无人机能在飞行过程中保持安全距离,且同时到达目标点。二维地图实验中,NSGA-Ⅲ算法可以规划出符合要求的协同航迹,能解决多无人机在二维地图中的协同航迹规划问题。

3.2 三维地图

在三维栅格地图中,设置最小栅格的长度、宽度和高度均为100 m。在规格为30×30×30的栅格地图2中,设置3架无人机,使用NSGA-Ⅲ算法进行航迹搜索。在地图中,锥形区域表示障碍物,球体和圆柱体区域表示威胁。设定无人机的起始位置为球体区域,圆心为(0.55 km,0.55 km,0.15 km),半径为0.3 km;目标位置同样为球体区域,圆心为(2.55 km,2.55 km,0.75 km),半径为0.3 km。种群的代表个体在迭代过程中的综合代价变化曲线如图6所示。

由图6分析可知,在初始迭代过程中,代表个体的综合代价下降较快,已能得到较优航迹。在后续迭代过程中,综合代价变化较小,最终达到稳定的值。选取各种群的代表个体作为各无人机的最终航迹,不同视角的协同航迹可视化结果如图7所示。

图7 三维地图协同规划航迹Fig.7 Cooperative planning path of three dimensional map

对图7进行分析可知,3架无人机航迹始终保持安全距离,且航迹符合无人机自身性能约束。NSGA-Ⅲ算法在三维地图中,规划出各无人机航迹的各项指标如表2所示。

表2 三维地图协同航迹数据Tab.2 Cooperative path data of three dimensional map

由表2数据可知,3架无人机的航迹代价均比较小,空间协同代价和时间协同代价为0,说明3架无人机能在飞行过程中保持安全距离,且同时到达目标位置。三维地图实验中,NSGA-Ⅲ算法能规划出期望的协同航迹,有效解决了多无人机在三维地图中的协同航迹规划问题。

通过二维和三维地图中的仿真可知,算法在起始搜索阶段所得航迹综合代价较高,因为起始阶段可利用经验较少。在迭代一段时间后,随着信息素浓度的提高,各种群逐渐集中在较优解附近搜索,算法所得航迹综合代价可达到比较稳定的较优值。由仿真实验结果可知,算法最终为各无人机规划出的航迹安全,能够同时到达目标位置且代价较小,符合预期要求,验证了算法的有效性。

4 结 语

笔者提出了一种NSGA-Ⅲ算法与势场蚁群算法结合的协同航迹规划算法。在势场蚁群算法中,通过障碍物斥力场使无人机与障碍物保持安全距离,通过目标位置引力场加快算法的收敛速度。在NSGA-Ⅲ算法中,将协同航迹规划中的航迹代价、空间协同约束和时间协同约束设置为多目标函数,各目标函数相对独立优化,最终都能达到较优值。在构成下一代种群时应用了优化的临界层选择方法,保持了种群的多样性。将改进后的算法应用到栅格地图上,利用各种群为各无人机搜索航迹,最终规划出满意的协同航迹。在二维和三维地图的仿真实验中,改进NSGA-Ⅲ算法规划出的协同航迹安全且代价较小,能有效解决多无人机的协同航迹规划问题。