无人机群对多目标执行多任务的协同规划方法

卫钊丞，刘卫东，张小明，樊宇韬

(火箭军工程大学，陕西 西安 710025)

0 引言

当待执行任务分布广泛且工作量较大时，单个无人机难以满足要求，而无人机群通过相互协同和配合可以更好地完成此类工作。无人机协同任务规划是提高无人机群工作效率和生存能力的重要手段[1]。

无人机群对多目标执行多项任务的协同规划问题，是当前研究的热点问题，解决思路是建立多无人机协同任务规划的数学模型，使用群智能算法搜索模型最优解。文献[2]提出了自适应烟花算法解决多无人机的多约束多任务规划问题，此方法能快速收敛于全局最优；文献[3]提出了带队-跟随编队方法，用于设计无人机协同跟踪地面目标的制导律；文献[4]提出了基于离散粒子群算法的多无人机多任务协同分配方法，给出了满足约束条件的任务分配方法；文献[5]针对多架异构无人机在未知环境下执行搜索打击任务，提出了并行带精英策略非支配排序的遗传算法求解模型，此方法实时性很强。

目前的研究成果很少考虑任务执行的时间序列问题，本文考虑了任务规划和时序规划，提出了保留潜力蜜源人工蜂群算法(retain potential source artificial bee colony algorithm,RPSABC)的无人机群多目标多任务规划问题，旨在提高无人机群任务规划的速度、精度和鲁棒性。

1 问题描述与建模

1.1 无人机群协同任务规划问题描述

将无人机群任务协同考虑在战场环境下，多架无人机对不同基地的目标执行多项任务，在执行任务时要规避威胁区域和禁飞区域。

将问题具体化，无人机考虑为集侦查、打击、评估能力于一体的无人机，给定任务环境中n架无人机出发点和m个攻击目标位置。使用n架无人机对m个目标点执行侦查、打击和评估任务，3种任务依次记为C任务、A任务和E任务。某架无人机在某目标位置执行1次任务后会被标记，若此无人机在此区域再次执行任务存在被打击的风险，因此规定同一架无人机在同一目标位置最多执行1次任务。

本文设定无人机在定值高度层飞行，雷达、防空导弹和防空火炮等威胁简化为圆模型，如图1所示。圆模型参数包括威胁中心、威胁半径和威胁等级3个参数。在此需要强调的是，威胁半径为雷达、导弹的威胁半径与无人机外接圆半径之和，故可以将无人机简化为一个质心。无人机群协同任务规划和执行情况如图1所示，图1中Ui为无人机编号，Ti为目标编号。

图1 无人机群协同任务规划示意

1.2 协同任务规划约束条件

对于同一目标点，3类任务的执行顺序是侦查、打击和评估，执行顺序不允许颠倒，且一个任务执行完毕后才执行下一任务。同一无人机对同一目标点最多执行1次任务，同一目标点必须完成这3类任务。以上约束条件用公式表达为

(1)

x为无人机的编码；当第i个无人机在第j个目标点执行任务时xi,j=1，否则xij=0；k用于区分执行任务类型，k=1,2,3分别代表执行侦查、打击和评估任务；t1j,k、t2j,k、t3j,k分别表示无人机对第j个目标点执行第k类任务的开始时间、结束时间和等待时间；tj,k为对第j个目标点执行第k类任务所需时间。本文假设对同一目标点执行3类任务的时间相同。

1.3 目标函数建立

设定无人机飞行速度不变，记为v。无人机群的最后一项任务执行完毕后，整个无人机群的任务才算执行完毕，因此执行任务耗时最长的无人机代表了此无人机群的耗时。基于以上考虑，将目标函数设置为

(2)

S=(S1,S2,…,Sn)，Si代表无人机Ui执行所有任务的总航程。

由于目标函数中提到了航程问题，点与点之间的航迹规划问题必须交代清楚，本文使用文献[6]中给出的航迹规划方法。

2 优化模型求解

2.1 保留潜力蜜源人工蜂群算法

人工蜂群算法原理已经成熟，可以参考文献[7-8]，这里不再赘述。针对算法自身缺陷和无人机对多目标执行多样任务优化问题，做以下说明和改进：

a.蜜源编码方式。由于每个目标点需要执行3项任务，则对于m个目标点需设置3m维的蜜源编码，从编码第1位开始，每3位代表1个目标点任务，也就是说第1、2、3位分别表示对第1个目标点执行侦查、打击和评估任务，第4、5、6位表示对第2个目标点执行任务，以此类推。记1个任务分配序列为(x1,x2,…,x3m)，则表示相应位置的任务由编码为xj的无人机执行。

b.改进蜜源初始化。蜜源初始化是生成1个NB×3m的矩阵，由于编码只能取整数，则传统人工算法的初始化方法不再适用。为了解决这一问题，改进蜜源初始化方法为

xj=rand(0,n)

(3)

rand(0,n)表示0～n的随机整数。蜜源初始化时，要求同一无人编号在同一目标3个任务中最多出现1次。

c.改进观察蜂对雇佣蜂的选择概率。在传统算法中，观察蜂依据雇佣蜂蜜源适应度值确定跟随概率，该方法利于算法收敛，但是却容易陷入局部最优。可认为连续被优化的蜜源附近更具有搜索潜力，更具有搜索价值，基于这一考虑，设置变量D1(i)、D2(i)用于记录蜜源连续更新次数。当蜜源i更新时，令D1(i)=0，D2(i)=D2(i)+1；当蜜源i保持不变时，令D2(i)=0，D1(i)=D1(i)+1。D1(i)、D2(i)最大值均设定为Limit，Limit表示局部搜索最大次数。

经过多次搜索未更新的蜜源，说明其邻域搜索意义不大，已经陷入了局部最优。而多次更新的蜜源邻域搜索活力较大，对算法寻优指导意义更大，因此应将观察蜂更大概率地分配到此区域。记G(i)为蜜源i的评估分值，每个蜜源基础分为50，各蜜源得分计算方法为

G(i)=

(4)

fit(i)表示第i只蜜蜂的适应度值，本文中f(i)=Fi表示第i只蜜蜂的目标函数，且有

(5)

依据各蜜源得分，确定观察蜂的动态选择概率为

(6)

d.改进蜜源评价方法。传统算法中，依据蜜源适应度值大小决定是否接受蜜源，这种选择方式过早地将有潜力的蜜源淘汰掉，使算法前期收敛较快，算法后期收敛较慢。为了解决这一问题，本文提出了蜜源选择的Metropolis准则[9]，蜜蜂由当前蜜源转向新蜜源的转移概率为

(7)

P(o→n)为由当前蜜源o向新蜜源n转移的概率，下降函数T(t)=T(t-1)·σ，σ为退火系数，取σ=0.8。

分析式(7)可知，当新蜜源适应度小于原蜜源时，仍有一定的转移概率，有利于保留具有潜力的蜜源；在算法初期，退火温度T(t)较高，适应度差的蜜源转移概率较大，保留有潜力蜜源的概率也大，有利于算法跳出局部最优；算法后期退火温度逐渐减小，算法更加“关注”优质蜜源，更多蜜蜂在优质蜜源邻域内细致搜索，提高寻优精度。

2.2 保留潜力蜜源人工蜂群算法流程

根据上节对人工蜂群算法机理的改进，使用保留潜力蜜源人工蜂群算法寻优的步骤为：

a.初始化算法参数。种群规模NB、局部搜索最大次数Limit、最大迭代次数MaxCycle、概率值P1，设置trial(i)=0,iter=0。

b.进行种群初始化，依据适应度值将蜜蜂分为雇佣蜂和观察蜂。

c.雇佣蜂进行邻域搜索，依据Metropolis准则判断是否接受新蜜源，使用摇摆舞将蜜源信息传递给观察蜂。

d.观察蜂根据动态选择概率选择雇佣蜂，而后与雇佣蜂一起进行邻域搜索，依据Metropolis准则判断是否接受新蜜源，若蜜源更新则trial(i)=0，若不更新则trial(i)=trial(i)+1。

e.判断trial(i)>Limit是否成立，若成立则第i只蜜蜂转化为侦查蜂进行随机搜索，若不成立则转至下一步。

f.输出全局最优蜜源，iter=iter+1，判断iter>MaxCycle是否成立，若成立则算法结束，否则转至步骤c。

2.3 时序规划方法

使用改进人工蜂群算法寻优得到目标函数意义下的最优解，其解的形式为3m维的行向量，以此为基础进行时序规划。提取每个无人机经过的目标点，由于每个无人机执行任务的目标点是有限的，因此使用排列法就可以将所有顺序穷尽地列举出来，然后计算每种顺序的目标函数，目标函数最小时对应的任务顺序即为任务的执行时序。所有无人机在同一时刻开始，由出发点逐个飞向目标点，直至所有任务执行完毕。

3 仿真验证

为了验证保留潜力蜜源人工蜂群算法在无人机群协同任务规划中的可行性和有效性，使用MATLAD R2014a软件进行仿真验证。目标点分布在1 000 km×1 000 km环境范围内，共设置10个目标点，分别记为T1～T10，位置坐标分别为(50,300)(310,300)(210,700)(620,610)(250,500)(620,350)(450,470)(600,150)(820,350)(420,750)。任务执行范围内存在8个威胁，威胁参数设置如表1所示。使用5架无人机组成的无人机群执行任务，无人机参数如表2所示。

表1 各威胁参数

表2 各无人机参数

保留潜力蜜源人工蜂群算法的参数设置为：种群规模NB=60、局部搜索最大次数Limit=10、最大迭代次数MaxCycle=300。

为了形成对比，分别使用本文保留潜力蜜源人工蜂群算法、逆向算子人工蜂群算法(improved artificial bee colony algorithm based on reverse operator,ROABC)[10]、基本人工蜂群算法(artificial bee colony algorithm,ABC)进行无人机群协同任务规划，各算法进行20次仿真。算法迭代过程中，目标函数最优值变化曲线如图2所示。

图2 不同算法的目标函数最优值变化曲线

由图2可以看出:在算法迭代前20次，3种算法收敛速度相差不大，而后ABC算法收敛速度缓慢，算法陷入局部极值，寻优结果较差；在算法迭代至80次时，ROABC算法收敛速度变缓，RPSABC算法继续快速收敛；从收敛结果看，RPSABC搜索结果最优，其次为ROABC算法、ABC算法。

记所有无人机起飞时刻为0时刻，使用改进人工蜂群算法规划的任务最优分配时刻表如图3所示。

图3 各无人机任务执行时刻表

以无人机U5为例，按时序执行任务的航迹如图4所示。

图4 U5执行任务航迹

由图3可知:每个目标点都执行了3类任务，意味着任务完成；且同一目标点不同任务在时间上分散，满足同一目标点不能同时执行不同任务的约束；同一无人机在同一目标点最多执行了1次任务，保证了无人机的安全。由图4可知，时序安排非常合理，没有出现“南辕北辙”的现象。

为了进一步比较RPSABC算法、ROABC算法和ABC算法在无人机群协同任务规划中的性能，统计20次仿真的平均收敛迭代次数、目标函数收敛值均值和目标函数收敛值标准差，结果如表3所示。

表3 不同算法寻优参数

结合表3与图2可知：RPSABC算法在迭代158次时收敛，目标函数值不再下降，比ROABC算法的收敛速度提高了31.9%，比ABC算法的收敛速度提高了40.4%；RPSABC算法任务规划的目标函数值最优，比ROABC算法减小了5.2%，比ABC算法减小了19.0%；而且RPSABC算法的收敛值标准差最小，说明此算法的稳定性和鲁棒性最好。这是因为在改进人工蜂群算法中，观察蜂选择雇佣蜂的动态选择策略既考虑了适应度高的蜜源，也考虑了具有搜索潜力的蜜源，利于算法寻优；将Metropolis准则应用于蜜源评价，算法前期搜索优质蜜源和潜力蜜源，算法后期更加关注优质蜜源，保证了算法前期跳出局部最优，后期细致搜索，最终使改进算法收敛速度快，收敛精度高。

4 结束语

本文研究了无人机群对多基地多目标执行多项任务的规划问题，建立了无人机群协调任务规划的环境模型和数学模型，使用动态选择规则、优质蜜源引导、Metropolis准则等改进了人工蜂群算法，将改进人工蜂群算法应用于多无人机协同任务规划问题。仿真结果表明，改进算法在收敛速度和收敛精度上均优于逆向算子人工蜂群算法、基本人工蜂群算法。