张瑞鹏，冯彦翔，杨宜康

西安交通大学 自动化科学与工程学院，西安 710049

无人机系统具有隐身性能好、自主能力强、可重复回收利用的特点，在目标侦察、目标打击、毁伤评估等军用领域和环境监测、灾害救援、区域物流等民用领域均发挥着重要的作用[1]。在实际应用中为了解决单一无人机执行复杂任务时的不足，更多的采用多无人机协同方案，把单一无人机作为独立任务处理单元，在执行任务时多个无人机利用设备或功能进行信息整合，实现高效统一的执行步骤，并利用相关设备完成不同的任务[2]。因此多无人机协同控制成为了一项重要的研究内容，而多无人机协同任务分配问题(Multi-UAV Task Allocation Problem, MTAP)，已成为无人集群协同自主导航领域需要解决的关键问题[3]。

多无人机任务分配是指在一定的决策时间内，分配异构无人机对给定的目标执行多个任务，形成协调配合，使系统综合成本最小化，以达到最优效率[4]。在进行多无人机任务分配时，受多种约束条件的影响，如任务能力约束、任务时序约束、路径安全性约束和规划实时约束等。需要综合协调任务优先级、时间约束、可飞行轨迹等，因此多无人机任务分配问题本质上是一个非确定性多项式(Non-deterministic Polynomial-hard, NP-hard)问题[5]。与此同时，待求解问题的规模(如：无人机数目、目标和任务的数量)也会影响求解过程的复杂性。目前，一些学者提出了多种计算可行的多无人机协同任务分配算法。文献[6]通过丰富合同类型的改进合同网拍卖模型实现多无人机多任务拍卖，利用条件合同机制实现多无人机间的协调。文献[7]提出了改进后的差分进化算法，进行尺度因子和交叉率动态调整。文献[8]改进了和声搜索算法，引入了一种调整音高的算子，将和声搜索的解映射到聚类方法中。文献[9]提出了基于分工机制的蚁群算法，利用基于任务能力评估的问题解构造策略和基于任务代价的状态转移规则，改进蚁群算法。文献[10]提出了一种混合蚁群优化算法，将禁忌搜索算法与最大最小蚁群系统集合。文献[11]基于不确定理论建立以信度函数为目标的最小风险模型,任务分配时规避不确定变量标准差较大的目标点。文献[12]将分布式合同网拍卖算法与模拟退火算法结合协调任务执行次序。文献[13]利用整数线性规划模型，对遗传算法进行改进，使用的编码方案有效减低了算法的复杂度。此外，当任务之间存在时序关系或者多个任务需要同时执行时，有可能出现“死锁”[14]。死锁是由一系列需要顺序执行的任务形成“循环等待”的关系引起的，文献[14]描述了死锁定义和死锁产生的必要条件。文献[15]针对任务时序约束导致的死锁问题，提出了一种基于图论和矩阵转置的死锁检测修复方法。文献[16]在文献[15]的基础上，提出了一种基于自由边翻转的死锁修复方法。任务执行过程中，由于新目标发现等实时事件的发生，导致原任务分配方案失效，需要进行任务重分配。文献[17]针对任务重分配场景，提出了一种匹配策略。文献[18]使用匹配策略设计了重组和非重组两种重调度方法。文献[19]考虑了任务时序对重调度的影响。

同其他启发式算法、智能优化算法相比，粒子群算法具有计算简单、鲁棒性好、搜索能力强且收敛速度快的特点，在求解多飞行器协同任务分配问题时，具有较大优势[20-25]。文献[20]基于启发信息和冲突消解策略改进标准粒子群算法(Particle Swarm Optimization, PSO)，提高算法收敛性和全局搜索能力。文献[21]利用混沌机制和变异算子增强量子粒子群算法的寻优能力。文献[22]在粒子矩阵编码中引入任务时序约束和多机协同约束。但因自身结构原因，粒子群算法不可避免的会出现粒子早熟和停滞倾向，容易陷入“局部收敛”，无法得到全局最优解。目前解决这个问题有2种方法，一是改进粒子群算法参数，扩大局部搜索范围，文献[23]设计最优粒子更新算法的控制参数。文献[24]结合进化博弈理论动态调整粒子群算法3个主要控制参数，但是这样的方法效果有限，没有结合其它算法的混合算法性能好。另一种方法是利用其它智能优化算法的局部搜索能力，帮助粒子群算法跳出局部收敛，文献[25]将模拟退火算法与粒子群算法相结合组成混合算法，提高算法寻优精度。但是这种方法每次迭代时都需要执行跳出局部收敛策略，大幅度增加计算开销。

多飞行器协同攻击地面目标场景中的任务分配问题，属于典型的MTAP问题。部分目标需要多架无人机同时打击，可能会出现死锁。任务具有软时间窗约束，即允许任务开始执行时间违背时间窗约束，但会产生相应的偏差代价。基于MTAP问题的数学模型，提出一种综合考虑任务收益和代价的混合粒子群任务分配算法。主要创新点包括：

1) 针对同时打击任务引起的死锁问题，提出一种基于多打击任务有向图的死锁检测和修正算法。

2) 根据变邻域算法强大的解空间搜索能力，提出一种能够有效跳出局部收敛的策略，并将这种策略嵌入到粒子群算法中。

3) 设计了一种局部搜索的概率启动准则，综合考虑了跳出局部收敛与计算开销之间的平衡关系。

4) 设计不同规模的仿真实验，结果表明同其它智能分配算法相比，混合粒子群任务分配算法的性能更好、适应性更强。

1 MTAP模型

假设共有Nu架无人机U={U1,U2,…,UNu}和Nt个地面目标T={T1,T2, …,TNt}，无人机数量远小于目标数。需要对每个目标Tj执行一次攻击任务Mj，因此有Nt个任务M={M1,M2,…,MNt}。每个打击任务需要一架或多架无人机来执行。令任务Mj需要Γ(j)≥1架无人机来执行。故M分为单打击任务集合Md={Mj∈M|Γ(j)=1}和多打击任务集合Mk={Mj∈M|Γ(j)>1}。每个单打击任务只需要一架无人机攻击相应目标；多打击任务Mj∈Mk需要Γ(j)架无人机同时攻击相应的目标。无人机完成任务会获得的综合收益由摧毁目标的价值、目标打击时间窗口、无人机飞行航程等因素决定。每架无人机武器载荷有限，只能完成有限个数的任务，即攻击有限个数的目标。

(1)

(2)

∀c∈{2,3,…,mi}

(3)

式中：vi为无人机Ui的飞行速度;TN(·)表示执行对应任务所需时间。

同时，无人机Ui执行Δi中的单打击任务时，无需等待，其到达时间等于任务执行时间。但当Ui执行的任务Mci是多打击任务时，则需要等待其它执行Mci的无人机都到达同一目标点，共同执行Mci。令Θ(Mj)={Us∈U|Mj∈Δs}表示需要执行任务Mj的无人机集合，则

∀c∈{2,…,mi}

(4)

(5)

式中：b1和b2分别是机会损失系数和延误惩罚系数。

MTAP问题数学模型如下：

(6)

(7)

(8)

(9)

xij∈{0,1} ∀Ui∈U,∀Mj∈M

(10)

2 混合粒子群任务分配算法

提出一种用于多无人机协同攻击地面目标的混合粒子群任务分配算法，设计粒子的编码、解码与修正过程。针对粒子群算法容易陷入局部收敛的缺点，提出一种基于变邻域搜索的跳出局部收敛的策略，提高算法的性能和适应性。

2.1 标准粒子群算法

在PSO[26]中，每个粒子对应一个潜在解，多个粒子组成一个种群。在粒子种群进化过程中，粒子需要追踪2个极值：个体极值pbest和群体极值gbest。前者是某个粒子搜索到的历史最优解，后者是整个种群当前的最优解。所有粒子根据适应度函数更新自身的位置向量和速度向量，尽可能的向最优解靠拢。

令粒子k时刻t的位置向量和速度向量分别是和。算法迭代演化过程中，每个粒子的速度和位置根据如下公式更新：

(11)

(12)

式中：r1和r2都是分布在[0, 1]之间的随机数；c1=c2=2分别是个体加速常数与群体加速常数；pbestk,t是粒子k当前时刻的个体极值，gbestt是当前时刻粒子种群群体极值。ω称为惯性因子，受文献[27]启发，ω由下式计算：

(13)

其中：ωmax和ωmin分别为惯性权重的最大和最小参考值；Iter和Imaxter分别为当前迭代次数和最大迭代次数；Fold为过去10次迭代最优粒子适应度平均值，F(gbest)为当前迭代最优粒子适应度。这样设置的ω能在搜索过程中自适应调整大小，特别当算法陷入局部收敛时，ω将逐步变大，提高局部探索能力。

2.2 编码、解码与修正

PSO算法中粒子的位置和速度是连续性变量，对应的解空间也是连续性的。而MTAP问题的任务分配解是离散的，因此需要先对粒子的位置和速度进行“离散化”编码，进而解码出MTAP的一个潜在解。

2.2.1 编 码

已知Nt是任务数量，Nu是无人机数量，故粒子维数其中Γ(j)是执行打击任务Mj需要的无人机数量。采用实数编码方式，令粒子k的位置Pk和速度Yk都是维实数向量，每个位置元素Pk[j]限制在1跟Nu+1之间但不等于Nu+1，即Pk[j]∈[1,Nu+1)。同时，为了保证粒子的位置尽可能在[1,Nu+ 1)之间，限定粒子的速度Yk的每个元素Yk[j]∈[-Nu,Nu]。

2.2.2 解码与修正

令In(n)为实数n的整数部分，De(n)表示n的小数部分，例如In(4.7)=4，De(4.7)=0.7。可用粒子k的位置元素Pk[j]表示一个任务分配解。例如对于In(Pk[j])=s，表示将任务Mj分配给了无人机Us。本文限定：对于具有相同整数部分的位置元素(将它们分给同一无人机)，其小数部分的大小顺序对应该无人机执行这些任务的顺序。因此从Pk可解码出无人机Ui的一组任务序列Δi。

算例1将任务M1～M9分配给无人机U1～U3，即Nt=9且Nu=3，其中M2、M4和M6是多打击任务，且Γ(2)=Γ(4)=Γ(6)=2，其余任务是单打击任务。因此，=12，相应PSO算法的解空间是12维。每个粒子的位置元素限定在[1, 4)之间，速度元素限定在[-3, 3]之间。表1给出一个粒子的位置、速度以及对应位置元素的整数部分和小数部分。从中可以看出M1、M4、M6、M7和M8分配给无人机U1。同时，因为De(Pk[10])。同理可得Δ2=，Δ3= 。很显然，对于Δ3，M2两次分配给U3，不满足约束式(8)。令而超过了无人机U1的任务上限，不满足约束式(9)。

表1 一个粒子的速度、位置和对应位置分量的整数部分和小数部分

算法1 约束修正1.for(1≤t≤Nu)2. while Δt中存在重复多打击任务Mj∈Mk3. 随机删除Δt中一个Mj;4. 选择r∈[1, Nu], s.t. r ≠ t且Δr中无Mj5. 将Mj随机插入Δr中;6. end7.end8.令Φ=⌀,Π=⌀,s=1;9.for(s≤Nt)10. if (Δs>Qmaxs)11. Φ=Φ∪{s};12. elseif(Δs

在算法1中，第1～7行对分配同一无人机的中多打击任务进行修正，以满足约束式(8)；第8～16行计算Φ和Π，Φ表示分配任务数超过其上限的无人机序号集合，Π表示对应任务序列还能插入任务的无人机序号集合；第17～28行是一个while循环，每次迭代中从Φ中选择一个无人机序号i，随机删除任务序列Δi中的一个任务Me，并将Me随机插入到任务集合Δj中，Δj中其余任务相应移位，其中j为随机从Π抽取得到无人机序号，与此同时更新集合Φ和Π。最终得到的新任务序列Δ′i(i∈{1, 2, …,Nu})，满足约束式(9)。

经算法1修正得到的任务分配解满足约束式(8)和式(9)，但可能出现“死锁”，即不同无人机执行多打击任务时，出现循环等待的现象，导致任务无法继续执行。比如，算例中任务分配解Δ经算法1修正后变成Δ′={Δ′1,Δ′2,Δ′3}，其中Δ′1=，Δ′2=，Δ′3=，Δ′可用图1描述，灰色圆形表示单打击任务，白色圆形表示多打击任务。很明显，无人机U1需等待U2到达T6后，才能执行多打击任务M6；但U2需要先打击目标T4(即执行任务M4)，才能到达T6；而执行任务M4又需要无人机U1先到达目标T4，这与U1的执行任务序列相矛盾。即U1和U2陷入无限循环等待，出现了死锁[14]。

图1 任务分配解示意图

本文中的死锁只与多打击任务有关，因此采用有向图G=来表征死锁，其中V={j|Mj∈Mk}表示多打击任务节点，E中的弧线(i,j)表示存在一架无人机先执行Mi再执行Mj。根据文献[15]，G中的强连通分量(即回路)表示死锁。比如上述修正解Δ′的有向图G如图2(a)表示，其中顶点4和6组成回路，因此任务M4与M6组成了死锁，这与上述分析结果相同。可用DFS算法(深度优先搜索)检测G的回路[28]。

根据文献[16]，本文针对多打击任务的死锁问题，提出了一种基于多打击任务有向图的死锁检测和修复方法，如算法2所示。输入为满足约束式(8)和式(9)的任务分配解Δ′={Δ′k|k∈{1, 2, …,Nu}}，输出为无死锁可行解Δ″={Δ″k|k∈{1, 2, …,Nu}}。

图2 多打击任务有向图

算法2 死锁修正1.构建Δ'对应的有向图G=;2.利用DFS算法检测是否存回路,回路信息存入列表RΔ';3.while(RΔ'≠⌀)4. 对RΔ'中各弧线根据出现次数排序;5. 轮盘赌法选取换位弧线(i, j);6. fork∈{1, 2, …, Nu}7. if 根据Δk, Uk先执行Mi再执行Mj8. 交换Δk中Mi和Mj的位置;9. end10. end11. 更新Δ'对应的有向图G = ;12. DFS算法检测回路,更新列表RΔ';13. end14. 输出无死锁可行解{Δ″kk∈{1, 2, …, Nu}}

在算法2中，第1～2行构建有向图，将DFS算法检测到的回路信息保存在RΔ′中；第3～13行修正死锁，根据RΔ′中出现的次数使用轮盘赌法选取弧线(i,j)，进行换位操作，交换一些任务序列Δ′k中多打击任务Mi和Mj的位置。类似于文献[16]中的分析，算法2在有限运算后输出一个无死锁的任务分配解。因为算法2仅调整任务序列Δ′k中一些多打击任务的位置，不会在Δ′k中增加或者删除任务，因此得到的无死锁解仍然满足式(8)和式(9)。

利用算法2对算例中的Δ′进行死锁检测和修复，可知RΔ′={(6, 4), (4, 6)}。选择弧线(6, 4)，交换Δ′1中M6和M4的位置，得到新的有向图G′，如图2(b)所示。相应的新的无死锁解是Δ″1= ，Δ″2= ，Δ″3= 。

2.2.3 适应度值计算

对于粒子k，首先将其位置向量解码为1组任务分配解Δ，然后利用算法1和算法2确保Δ满足约束条件且无死锁。相应的适应度值F(k)由式(1)确定，即

(14)

式中，F(k)越小，从粒子k解码出的任务分配解的质量越好。

2.3 变邻域搜索跳出局部收敛策略

为了提高PSO算法的性能，防止算法陷入局部收敛，本文提出一种基于变邻域搜索(Variable Neighborhood Search, VNS)算法的局部搜索策略，使算法具备跳出局部收敛的能力。

2.3.1 邻域结构

VNS算法的基本思想是在搜索过程中改变邻域结构集，从而拓展搜索范围，获得最优解[29]。

令Pk表示粒子k的位置向量，根据解码和算法1可从Pk得到1组任务分配解，即Pk决定k对应解的质量。因此，本文采用以下3种邻域结构，修改位置向量Pk寻找更好的邻域解：

2) 第2邻域结构(插入邻域)：在Pk中随机选择2个位置i和j且i

算法3利用第1邻域结构(交换邻域)搜寻局部最优解。首先令i= rand(1,Nt)和j= rand(1,Nt)都为区间[1,Nt]的任一整数，并设当前邻域搜索次数N为0。Nmax表示最大搜寻次数。算法的主要组成部分是while循环(第2～14行)，在每次迭代中N

算法3 第1邻域结构1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0//初始化2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. P'k=(Pk, i, j) ∥将Pk[i]和Pk[j]互换,得新的位置P'k8. P'k与粒子k的速度结合得新的粒子k';9. end10. if(F(k) > F(k'))11. 将粒子k替换为k'; ∥粒子k性能差,替换为k'12. end 13. N++14. end15. 输出粒子k';

算法4 第2邻域结构1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0;2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k =(Pk, i, j) ∥将Pk[j]插入位置i处得新位置P'k9. else10. P'k=(Pk, j, i)11. end12. P'k与粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 将粒子k替换为k'; ∥粒子k性能差,替换为k'16. end17. N++;18. end19. 输出粒子k';

算法4利用第2邻域结构(插入邻域)搜寻局部最优解，其算法步骤与算法3相似，主要区别在于算法4需要判断随机选择的位置序号i和j的大小，将较大位置序号的元素插入较小位置序号(见第6～12行)，形成新的位置向量P′k。

算法5使用第3邻域结构(逆转邻域)搜索局部最优解，将随机选择的序号i和j之间的片段逆转重排(第6～12行)，直至搜索到局部最优解。

算法5 第3邻域结构1.令 i = rand(1, Nt), j = rand(1, Nt), N = 0;2. while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k=(Pk, i, j) ∥Pk中位置i、j之间元素逆转重排9. else10. P'k = (Pk, j, i)11. end12. P'k与粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 将粒子k替换为k'; ∥粒子k性能差,替换为k'16. end17. N++;18. end

2.3.2 局部搜索启动概率准则

为了综合平衡算法跳出局部收敛能力与整体计算开销，以概率rk启动对粒子k的变邻域局部搜索，rk由下式计算

(15)

启动概率rk由当前粒子k的适应度值F(k)和全局最优值F(gbest)决定。当F(k)≤F(gbest)时，由式(15)可知rk=1，此时算法很有可能已陷入了局部收敛，因此必须要启动变邻域搜索过程，跳出局部收敛；当F(k)>F(gbest)时，粒子k的性能较差，距离全局最优解较远，此时是否会启动局部搜索由概率rk=S决定；分析可知k性能越差，越不可能陷入到局部收敛中，相应的启动概率rk越小，同时将最小启动概率设置为0.01。

通过此概率启动准则，一方面对陷入局部最优的粒子进行变邻域搜索，跳出局部收敛；另一方面，对距离全局最优解较远的粒子，降低启动局部搜索的概率，实现跳出局部最优与计算开销的合理平衡。

2.3.3 跳出局部收敛的变邻域搜索算法

利用上述3种变邻域结构，提出一种VNS局部搜索算法，实现跳出PSO算法可能陷入的局部收敛。如算法6所示，输入为粒子k的位置Pk，输出为局部最优解对应的粒子k′。

在算法6中Nmax表示某一邻域结构内最大搜索次数，本文采用了3级邻域结构，因此最高邻域等级Klevel_max=3。令r= rand(0,1)为0～1之间的随机数，启动概率rk由式(11)确定。若r≥rk，则不启动变邻域搜索，直接输出原粒子k。VNS搜索过程如第3～23行所示，当邻域搜索次数N≤Nmax时，进行第K变邻域结构局部搜索(第6～21行)。在此过程中，若新粒子k′优于原粒子k，用k′替换k，跳出当前循环过程，并初始化N和K(第15～21行)；若搜索Nmax次后仍未找到更优粒子，则需要提升邻域等级(第22行)；若当前邻域等级大于Klevel_max时仍未发现更优粒子，直接输出原粒子k。

算法6 VNS局部搜索算法1.Let Nmax= n,Klevel_max= 32.if (r = rand(0, 1) < rk)3. K = 1;4. while (K≤Klevel_max)5. N=1; ∥初始化当前邻域搜索次数6. while (N≤Nmax)7. switchK:8. case 1: ∥启动第一邻域搜索9. 执行算法3,输出粒子k'10. case 2: ∥启动第二邻域搜索11. 执行算法4,输出粒子k'12. case 3: ∥启动第三邻域搜索13. 执行算法5,输出粒子k'14. end15. if (F(k') < F(k)) ∥找到局部最优解16. 将粒子k替换为k';17. K = 0; ∥复位邻域等级18. break; ∥跳出当前while循环19. end20. N = N + 1 ∥完成一次邻域搜索21. end22. K = K + 1; ∥增加相应邻域等级23. end24. end25. 输出粒子k;

2.4 混合粒子群任务分配算法设计

本文提出了一种结合标准PSO算法与VNS搜索跳出局部收敛策略的协同任务分配混合粒子群算法，算法流程图如图3所示。具体步骤如下所示：

步骤1初始化种群，设置最大迭代次数Tmax，经过解码和修正过程，计算当前种群的全局极值和每个粒子的个体极值。

步骤2根据式(15)计算每个粒子k的局部搜索启动概率rk，利用算法6进行VNS搜索，用生成的更优粒子替代原粒子。

步骤3计算每个粒子k的适应度值F(k)，更新k的个体极值与全局极值。

图3 协同任务分配混合粒子群算法流程图

步骤4根据式(11)和式(12)更新每个粒子的位置和速度。

步骤5判断当前迭代次数是否大于Tmax，若否，则返回步骤2。

步骤6输出全局极值和相应的任务分配解。

2.5 基于匹配策略的局部任务重分配方法

针对新目标发现等实时事件导致的初始分配计划失效问题，结合2.4节中的协同任务分配混合粒子群算法，提出了一种基于匹配策略的局部任务重分配方法。匹配策略思想首先定义重分配范围(以时间窗的形式)，然后重新调度在重分配范围内的任务，最后将得到的局部调度计划集成到初始任务分配方案中，这样能保证初始任务分配计划的稳定性，还减小了计算开销，缩短了重分配用时[18]。

考虑发现新目标场景下的任务重分配。令Tn={T1n,T2n,…,TNn}表示ts时刻新发现的Nn个目标，对应的打击任务集合是Mn={M1n,M2n,…,MNn}。新任务Mjn需要Γ(jn)架无人机执行，对应的时间窗口[S(Mjn),C(Mjn)]。根据文献[19]，定义重分配范围[tstart,tend]，其中tstart=ts，tend=max{C(Mjn)|Mjn∈Mn}。需要将Mn中的新任务在时间窗[tstart,tend]内分配给各个无人机，但这样会影响初始计划中[tstart,tend]内的任务Mo(不包括tstart,tend点正在执行的任务)。因此，重分配的任务集合MR=Mo∪Mn。

图4(a)表示一个任务分配方案的甘特图，可知Δ1= ,Δ2= ,Δ3= , 假设在ts= 12发现新目标Ts，对应任务Ms的时间窗是[15, 28]，故相应的重分配范围是[12, 28]。注意在tend时刻，M4正在执行。按照初始计划，此时段内任务Mo= {M5,M6,M7}，因此需要重分配的任务集合是MR= {M5,M6,M7,Ms}。根据tstart之前的任务分配计划，更新各个无人机的起始时间和地点，将MR中的任务分配给无人机，并将所得结果与原计划tend后的方案结合起来，共同组成重分配结果。这样的简化调度问题减少了待分配任务数量，缩短重分配用时，保留部分原分配计划。

图4 任务分配甘特图

现证明重分配任务方案Δ*是无死锁的。假设对应的多打击任务有向图G*具有回路。因为MR和∪i∈{1,2,…,Nu}Δvi对应的多打击任务有向图都是无回路的(这由混合粒子群的死锁修复算法决定)，则V′中肯定同时包含了MR和∪i∈{1,2,…,Nu}Δvi中的多打击任务，且存在任务Mr∈MR∩V′以及Mv∈∪i∈{1,2,…,Nu}Δvi∩V′，使得弧线(Mv,Mr)∈E′，即有一架无人机先执行Mv再执行Mr。然而根据时间轴关系，这是不可能的。因此G*无回路，重构结果Δ*无死锁。

3 算法实例与分析

分别用遗传算法(Genetic Algorithm, GA)[30]、模拟退火算法(Simulated Annealing, SA)[31]、粒子群算法(PSO)[26]、粒子群与模拟退火结合的混合算法(PSO+SA)[25]和本文提出的混合PSO算法求解多无人机协同任务分配问题，并对比分析实验结果。验证平台为具有Intel Core i9-9900K处理器、32 GB内存的PC机，所有算法在MATLAB R2021a平台编译运行。

实验1考虑5架无人机协同攻击20个地面目标的任务分配场景。无人机和攻击目标的参数如表2和表3所示。为了简化实验场景，假设无人机起飞后均匀速飞行。每个目标具有不同打击时间窗口和打击用时。

设定上述5种算法的最大迭代次数均为800次，均衡考虑各受益和代价的影响，令目各项增益系数a1=a2=a3。同时设2种时间偏差的代价相同，即b1=b2=1。5种算法的任务分配结果如表4所示，括号中的数据为各无人机执行相应任务的无量纲时间，比如12(7.78)表示无人机于7.78时刻执行任务12。从表4可看出，使用本文死锁检测和修复算法，多架无人机在同一时刻执行同一多打击任务，不会引发死锁。与其他4种算法相比，提出的混合PSO适应度值最小，性能最好。

表2 无人机参数

表3 任务目标参数

图5为5种算法适应度变化折线图，可以看出GA算法具有较差的局部搜索能力和进化能力，所得结果与其他4种算法相比有明显差距；SA算法在一开始优化速度较快，但很快陷入了局部收敛；PSO算法在起始阶段具有较快的优化速度，但在中期陷入了局部收敛；PSO+SA算法虽具有一定的跳出局部收敛的能力，但收敛速度较慢，仍然会陷入局部收敛，所得适应度值也非最佳；本文提出的混合粒子群算法采用了局部搜索启动概率准则，不仅在起始阶段具有并不低于PSO算法的优化速度，还能不断的跳出局部收敛，所得的结果也是最优的。

表4 任务分配结果[25,30,31]

图5 5种算法适应度对比

实验2为了验证提出的概率启动准则具有平衡跳出局部收敛与计算开销的能力，本文对于实验1的场景，设置3种情形：不执行跳出局部收敛策略、每次迭代执行跳出局部收敛、采用本文提出的概率启动准则。共进行5次实验，计算平均适应度值和平均算法运行时间。

实验结果如表5所示，从中可知：与不执行跳出局部收敛策略的情形相比，本文的概率启动准则跳出局部收敛策略使得解的性能提升324% (≈(182.82-43.08)/43.08)；与每次都执行跳出局部收敛策略相比，概率启动准则在节约84% (≈(4642-732)/4642)时间的前提下，解的性能仅下降4%(≈(43.08-41.43)/41.43)。因此，本文提出的概率启动准则实现了计算开销与跳出局部收敛的平衡。

表5 不同跳出最优策略实验统计结果

实验3为了综合验证本文提出的混合PSO算法求解MTAP问题的能力，本文将上述5种算法用于不同规模的MTAP实验，所得结果如图6所示。其中，MTAP0305表示3架无人机协同打击5个目标的任务场景。5种算法均进行5次实验，并分别统计所得解目标值的3项指标：最小值、平均值和方差。从图6可以看出，对于小规模问题(比如MTAP0305)，由于解空间较小，5种算法求解性能相似，均能得到最优解；随着问题规模的增大，不同算法的表现差异也显著增大，但本文提出的混合PSO任务分配算法在不同规模的MTAP问题中都取得了最好的解，适应性最好。

图6 不同规模MTAP实验对比

实验4针对发现新目标导致初始任务分配方案失效问题，验证本文提出的基于匹配策略的局部任务重分配算法的有效性。设初始任务分配方案Δ的甘特图如图7(a)所示，将10个任务M1～M10分配给了3架无人机，其中M2、M5和M8是多打击任务。假设在ts=15时刻，发现新目标Tn={T11,T12}，新增加任务Mn={M11,M12}，它们的参数如表6所示，可知只有M12是多打击任务。根据3.5节中的任务重分配方法，因max{C(Mjn)|Mjn∈Mn}=40，故重分配范围为[15, 40]，相应的重分配任务集MR={M1,M4,M5,M11,M12}。注意tend时刻任务M6未完成，因此M6不属于MR。初始任务分配方案在tend之后序列Δv1= ，Δv2= ，Δv3= 。

图7 任务重分配实验甘特图

表6 新任务参数

4 结 论

针对多无人机协同任务分配问题，建立了综合考虑飞行航程、任务收益、任务完成时间窗口的混合粒子群任务分配算法。首先设计了满足多打击任务约束条件的粒子编码与解码过程，针对可能存在的死锁问题，设计了一种基于多打击任务有向图的快速死锁检测修复算法，实现了粒子群算法解的离散化。然后对于标准粒子群算法容易陷入局部收敛的问题，设计了一种基于变邻域搜索算法的跳出局部收敛策略，同时提出局部搜索概率启动准则，实现了跳出局部收敛和计算开销的平衡。最后，将所提出的跳出局部收敛策略与粒子群算法相结合，得到适用于MTAP问题的混合粒子群算法。对于新目标发现导致的初始计划失效问题，本文也设计了一种基于匹配策略的局部任务重分配方法。

通过设计仿真实验，与现有其他4种智能任务分配算法相比较，本文提出的混合粒子群算法在保证优化速度的同时，还具有不断跳出局部收敛的能力，因此会获得较好的任务分配结果，性能表现显著优于其他算法。