一种改进多目标灰狼优化算法的多无人机任务分配*

王 昭，华 翔,2

(1.西安工业大学 兵器科学与技术学院，西安 710021；2.西安工业大学 电子信息工程学院，西安 710021)

无人机编队在城镇、森林、山地等复杂环境中，通过多个无人机智能感知和协同合作，可以执行探测、巡逻、跟踪等多项任务。无人机编队的应用，促进了自主协同任务分配和规划方法的发展[1]。多无人机任务分配是一个组合优化问题，很多学者引入旅行商模型[2]、合同网模型[3]、整数规划模型[4]等经典模型，这些方法考虑到团队合作的协同性，能够有效解决简单任务的分配问题；一些新的研究将蝗虫弹跳行为[5]、细菌觅食行为[6]、蚁群释放信息素行为[7]、狼群等级制度[8]等生物行为映射到任务分配中，通过模拟生物在不同阶段的形态特点和行为方式，定义无人机的任务功能和飞行状态，有利于对复杂动态任务的实时分配。任务分配涉及到任务协调、时间约束等协同决策问题，考虑到这些因素，文献[9]提出了协同多任务分配模型(Cooperative Multiple Task Assignment Problem，CMTAP)，在无人机任务分配领域受到广泛关注。随着编队中无人机数量的增加，执行任务的复杂性增加，任务分配的协同性需求也随之提高，因此有必要进一步研究CMTAP模型在多无人机任务分配中的应用。

CMTAP主要解决多个无人机对多个目标协同执行多个任务的分配问题，自提出以来根据具体问题不断得到改进和优化。文献[9]在网络流优化模型的基础上提出了CMTAP模型，采用树结构描述分配问题的解空间，结合任务时序约束、执行时间约束、飞行轨迹约束等因素，以最小化飞行距离或最小化任务完成时间作为优化目标进行求解，该模型考虑到任务的优先级、协调性以及飞行轨迹的需要，能够提供良好可行的解决方案。文献[10]为解决无人机对地面已知目标分类和评估的问题，在CMTAP模型的基础上增加了有限资源约束，采用镜像方式以存储任务分配过程中的剩余资源并将其对应的无人机作为备用集合，从而使无人机的资源信息实现实时存储和更新。文献[11]对CMTAP模型进行了扩展，考虑无人机的机载资源和执行任务的异构性，将航迹规划总长度和任务执行时间作为代价函数，该方法适用于任务数量较多的场景，能够避免“单点失效”问题。CMTAP是一个组合优化问题，运行时间会随着搜索空间的增加而呈指数级增长。启发式随机搜索算法能够降低计算量，快速找到问题的最优解，所以学者们通常采用遗传算法、蚁群算法、粒子群算法等启发式算法对CMTAP模型求解。文献[12]设计染色体结构中的多基因编码策略，对无人机的异构特征、任务的多种类型进行描述，该方法在大规模任务场景中具有良好的鲁棒性。文献[13]考虑任务完成时间、燃料消耗、无人机数量等因素，采用改进的遗传算子对约束满足问题模型中的多个目标函数进行优化，该方法能够快速解决无人机数量增加时的目标分配问题。文献[14]采用改进粒子群算法、蚁群算法和遗传算法分别对无人机任务分配模型进行求解，结果表明遗传算法求解精度更优，而改进粒子群算法和蚁群算法求解速度更快。灰狼优化(Grey Wolf Optimization，GWO)算法[15]作为新兴的启发式随机搜索算法，因其操作简单、收敛速度快等优点，自提出以来被一些学者应用于任务分配领域。文献[16]将GWO和多机器人协同搜索相结合，形成混合随机搜索，在多个机器人之间实时分配搜索任务。文献[17]将分布式拍卖机制引入GWO算法中，通过竞标的方式选择价值高的无人机执行任务，避免优化算法陷入局部最优。文献[18]将自适应调整策略引入GWO中，解决了原本算法的早熟问题，提高了动态任务分配问题的求解速度。在CMTAP问题上采用GWO算法，能够快速搜索解空间，解决任务分配中由于搜索空间增大带来的运行时间倍增的问题。

针对多无人机对空中移动目标的任务分配问题，对CMTAP模型进行改进，考虑到无人机的编队性能和任务完成时间两个因素，构建了执行代价和时间代价两个目标函数。再对GWO进行改进，使其能够快速求解所提模型。在对多目标函数优化的传统算法中，研究人员通常选择一个目标函数作为主要函数，将约束条件和其他目标函数作为罚函数添加到该主函数中，以形成单一函数。在多无人机任务分配问题中，约束条件的权值无法统一界定，更为准确的处理方法是采用多目标优化算法。在对CMTAP模型求解时，随着无人机数量的增加，算法的计算量会增加。因此，本文将基于并行机制的多目标灰狼优化算法(Parallel Mechanism with Multi-Objective Grey Wolf Optimization Algorithm，PMOGWO)应用于多无人机CMTAP问题中，设计分层编码和档案室共享策略，将无人机编队的复杂任务简化到每个无人机上，以解决传统方法和一些启发式算法带来的计算量增加的问题。最后，通过实验仿真验证模型和算法的合理性。

1 多无人机CMTAP模型

1.1 问题描述

无人机i对目标j执行任务k的示意图如图1所示。无人机1首先对目标1探测，然后对目标3分类。无人机2对目标1分类，对目标2探测。无人机3依次对目标1和目标3执行评估任务。无人机4对目标2进行评估。无人机5首先对目标3进行探测，其次对目标2进行分类。

图1 无人机i对目标j执行任务k的示意图Fig.1 The diagram of UAV i performing the task k to the target j

1.2 评价指标

针对空中移动目标的任务分配，考虑目标的飞行情况以及无人机与目标之间的相对状态，以CMTAP的通用模型为基础，引入无人机空中态势模型，建立双目标函数，以描述多个无人机执行任务时产生的相关代价函数。根据文献[19]建立无人机空中态势模型，如图2所示。Vi和Vj分别表示无人机i和目标j机体轴线所在方向的速度，θi表示i的离轴角，θj表示j的离轴角，其绝对值不大于180°。

图2 无人机空中态势模型示意图Fig.2 Schematic diagram of UAV aerial situation model

文中构建执行代价函数Jcarry和时间代价函数Jtime，作为多无人机CMTAP模型的目标函数。其中，执行代价是无人机对目标执行任务时编队的性能损耗；时间代价是无人机完成所有任务耗费的时间。

1) 执行代价

(1)

2) 时间代价

对无人机i而言，任务完成时间是无人机和其对应目标的相对距离与它们相对速度的比值,计算公式为

(2)

其中，ΔVi，j是无人机i与目标j的相对速度，用ΔVi，j=|Vicosθi+Vjcosθj|表示。

以最晚完成任务的无人机执行任务的时间作为整个编队的时间代价：

(3)

3) 评价指标

要进行合理有效地任务分配，不仅需要单个无人机顺利完成任务，还要保证整个编队实现协同分配。文中将最小化执行代价和最小化时间代价作为目标函数，并考虑任务数量约束、多机协同约束和任务时序约束等三个约束条件，得到最优任务分配方案A应满足的评价指标公式为

minJ(A)=(Jcarry,Jtime)，

(4)

(5)

(6)

(7)

(8)

式(5)表示任务数量约束，所有目标上的任务应被完全执行。式(6)与式(7)表示多机协同约束，无人机在一个目标上只能执行一种任务，而一个目标上的多个任务可以被不同无人机执行。式(8)表示任务时序约束，对于一个目标来说，探测任务在分类任务之前执行，评估任务在分类任务之后执行。

2 PMOGWO算法

对多无人机CMTAP模型的求解可抽象成双目标函数及多个约束的优化问题，为减少CMTAP在求解优化过程中产生的计算量，本节将并行机制引入多目标灰狼优化算法中，提出了PMOGWO算法，以搜寻CMTAP模型的解空间。每个无人机被视为一个独立的灰狼子群，通过分层编码和种群优化寻求各自的最优分配序列；多个子群对公共档案室的帕累托解集进行共享，以获得最终的任务分配结果。

2.1 分层编码

在并行机制中，一个无人机对应一个灰狼子群，子群中的所有个体反映该无人机的分配情况。每个个体的编码位可由一个三元组(U,T,A)表示，其中U表示对应无人机的初始状态，包括无人机的位置、角度、速度和价值；T表示所有目标的初始状态，包括目标的位置、角度、速度和优势概率；A表示该无人机的分配决策变量。由于传统的二进制编码方式无法准确描述无人机的决策变量，采用实数进行编码，整数部分表示分配的目标序号，小数部分划分为三个区间，在[0.1,0.3]内表示执行探测任务，在[0.4,0.6]内表示执行分类任务，在[0.7,0.9]内表示执行评估任务。多无人机分层编码方案如图3所示。

图3 分层编码方案示例Fig.3 Example of layered encoding scheme

2.2 种群优化

多目标灰狼优化(Multi-Objective Grey Wolf Optimization，MOGWO)算法[20]是在GWO的基础上提出的算法，以解决多个目标函数的快速寻优问题。相较于传统的启发式随机搜索算法，MOGWO所需参数更少、收敛速度更快，适用于对高维优化问题的求解。该算法将灰狼分为四个等级，优先级呈金字塔状，自上而下分别是Alpha、Beta、Delta和Omega，分别对应目标函数的最优解、次优解、第三优解和候选解。同时建立档案室，存储前三个灰狼的位置即初始非支配解。在迭代过程中， Alpha、Beta、Delta首先预测猎物的大致位置，其他候选狼在这些领导者的指引下不断更新位置，最终找到猎物即最优解。灰狼种群更新后，根据帕累托支配策略筛选非支配解，将其与原档案室中的解比较，选择更优解替代劣解存入档案室中。迭代结束后，档案室存储的所有个体即为优化问题的最优解集。

2.3 档案室共享策略

每个灰狼子群都是独立的群体，在并行迭代时能够自主包围猎物，而不受到其他群体的干扰，其档案室策略可能会被重复运行。为了充分进行群体间的信息交流，并且减少计算量，设计档案室共享策略。所有子群共享一个公共档案室，实现存储或删除非支配解等操作。每个子群的第一个个体产生的初始非支配解作为当前最优解集，存储在公共档案室的每一层中。将下一个个体获得的非支配解与档案室中保留的非支配解进行比较，根据帕累托支配策略判断是否将当前非支配解添加到档案室中。当所有子群都完成了优化搜索后，存储在档案室所有层的非支配解集就是所求目标函数的帕累托解集。

2.4 PMOGWO算法

基于多无人机CMTAP模型，本文将并行策略引入多目标灰狼优化算法中，提出了PMOGWO算法。首先建立NU个灰狼子群，对应NU个无人机，各子群为其对应的无人机构造初始任务分配序列；其次通过子群内个体间的信息共享得到所有个体的目标函数值，选择最小函数值对应的子序列构成一个集合，作为本次迭代中对应子群的分配序列，存储在公共档案室中；迭代结束后，根据约束条件，在档案室中找到一组合适的分配序列作为最终结果。该算法的流程如下所示。

输入：优化算法的控制参数，无人机集合，目标集合。

输出：任务分配序列。

Step 1：初始化灰狼种群和公共档案室种群，将灰狼种群划分为NU个子群，初始化相关控制参数，设置最大迭代次数。

Step 2：每个灰狼子群按照分层编码方案，根据每个灰狼的当前位置构造初始可行序列。

Step 3：根据式(1)～式(3)，计算每个灰狼个体所得任务序列的目标函数值，根据轮盘赌法选择每个子群的最优个体，存入档案室中。

Step 4：根据领导者围捕策略，更新灰狼个体的位置以及对应的目标函数值，并选择函数值最小的序列作为候选解集。

Step 5：将候选解集与档案室相应层存储的解集进行比较，选择非支配解集作为当前迭代的最优分配序列存储在档案室中。

Step 6：判断算法是否满足终止条件，若是，则根据约束条件式(5)～式(8)，输出档案室中的最优任务分配序列；否则转Step 2。

3 仿真验证

本文对实验场景作如下想定：无人机编队与目标编队均由一组能够自主飞行和智能决策的无人机构成，在任务分配过程中不考虑能源消耗和通信约束。为了方便分析，将无人机和目标均视为具有速度、角度、价值、概率等属性的质点。仿真环境的区域设置为5 km×5 km的平面。

为了验证算法的性能，本文设计了3种不同的场景，分别为：5个无人机对3个目标，10个无人机对4个目标，15个无人机对5个目标。无人机对每个目标需要依次执行探测、分类和评估三种任务。采用PMOGWO算法、MOGWO算法和多目标粒子群优化(Multi-Objective Particle Swarm Optimization，MOPSO) 算法分别求解多无人机CMTAP模型，从代价函数统计值和收敛曲线两个方面对比其稳定性和收敛性，以验证本文算法在任务分配上的可行性。

3.1 分配结果分析

场景1设定为5个无人机对3个空中目标，无人机和目标的参数设置见表1～表2，目标对无人机的优势概率见表3。根据参数设置，无人机和目标初始分布情况如图4所示。采用PMOGWO进行快速寻优，设置子群规模为5，每个子群中包含10个个体，迭代次数为50，分配结果见表4，其结果分布如图5所示。

表1 无人机参数设置Tab.1 Parameters of UAVs

表2 目标参数设置Tab.2 Parameters of targets

表3 目标对无人机的优势概率Tab.3 Advantage probability of the targets to UAVs

图4 初始分布图Fig.4 Initial distribution

从表4和图5可看出，每个无人机都分配到了相应的任务。由于飞行路径的限制，首先无人机5对目标1执行探测任务，其次无人机1对目标1执行分类任务。无人机2首先对目标2进行探测，其次对目标3进行评估。无人机3对目标3探测，对目标2分类，最后对目标1进行评估。无人机4对目标3执行分类任务，随后对目标2评估。至此，所有目标上的三种任务均已分配完毕。因此，在该仿真场景下，多无人机任务分配的结果是可行的。

表4 任务分配结果Tab.4 Assignment results

图5 分配结果分布图Fig.5 Distribution of assignment results

3.2 稳定性分析

为了验证算法的稳定性，采用PMOGWO、MOGWO和MOPSO分别求解3种场景下的多无人机CMTAP模型。每种算法分别独立运行10次，最大迭代次数设置为50，子群规模的设置与无人机的数量相匹配，其执行代价和时间代价的统计结果见表5～表6。

从表5和表6可以看出，随着场景变化，3种算法的代价值在逐步增长，这是由于目标数量增加，无人机在任务分配过程中可执行的任务序列也会增加，其编队性能损耗和时间损耗会相应提高。然而在3种场景下，无论是执行代价还是时间代价，PMOGWO的最小值、最大值、平均值和标准偏差值均小于其他算法。以平均值为例，PMOGWO的执行代价均值至少比MOGWO的均值降低了4.5%，比MOPSO的均值降低了4.8%；其时间代价均值至少比MOGWO降低了3.1%，比MOPSO降低了3.4%。该结果表明，本文算法能够以更少的代价在合理的迭代次数内产生可行解，具有更好的优化能力，其稳定性优于其他算法。

表5 各算法在不同场景下执行代价函数值比较Tab.5 Comparison of the three algorithms’ carry cost in different scenarios

表6 各算法在不同场景下时间代价函数值比较Tab.6 Comparison of the three algorithms’ time cost in different scenarios

3.3 收敛性分析

为验证算法的收敛性能，3种算法在相同的仿真环境中分别迭代100次，其收敛曲线如图6所示。

图6 不同场景下PMOGWO、MOGWO和MOPSO的收敛曲线Fig.6 The convergence curves of PMOGWO,MOGWO and MOPSO in different scenarios

从总体上看，每种算法产生的执行代价和时间代价最终都能趋近于一个稳定值，而PMOGWO算法的收敛值均小于其他两种算法。此外，随着目标数量的增加，执行代价和时间代价也在相应增加。在无人机数量超过目标数量的前提下，无人机更有机会选择更多的目标执行任务，这将可能增大编队性能的损失；而无人机执行任务越多，由于路程增加带来的时间损耗也将越多，从而增加时间代价。

从图6(a)看出，在目标数量较少的场景下，相比其他两种算法，随着迭代次数增加，PMOGWO能够找到代价值更小的可行解。在图6(b)和(c)中，当目标数量扩展时，在迭代初期3种算法的代价值上下波动，这是因为任务数量增加导致CMTAP模型的搜索空间扩增，优化算法的搜索操作呈现不稳定状态；而在迭代后期寻找到探索与开发的平衡，执行代价和时间代价逐渐收敛于稳定值。通过对3种场景下不同算法的双代价收敛值进行统计平均，PMOGWO相较于MOGWO，收敛值降低了约15.5%；相较于MOPSO，降低了约6.2%。这是由于本文算法的固有优势，通过并行机制，无人机可以根据自身情况，不受外界干扰，独立智能地选择合适的目标执行任务，同时采用的分层编码和档案室共享策略能够提高算法的求解速度，避免其过早陷入局部最优。因此，与MOGWO和MOPSO相比，PMOGWO具有良好的收敛性能。

4 结 论

1) 针对多无人机对空中移动目标的协同任务分配问题，文中提出了一种基于并行机制的多目标灰狼优化算法。根据无人机的多任务需求，考虑目标特点和环境约束，构造了多无人机CMTAP模型，建立了执行代价和时间代价双目标函数以及多个约束。

2) 为了快速求解该模型，在多目标灰狼优化算法中引入并行机制，提出了PMOGWO算法，增强其跳出局部最优的能力，提高算法的寻优速度。与MOGWO和MOPSO相比，PMOGWO的代价函数平均值分别降低了大约3.8%和4.1%，收敛值分别降低了大约15.5%和6.2%。所以，本文提出的方法能够快速求解多任务分配问题，具有更好的稳定性和收敛性。

3) 随着无人机技术的发展，协同执行任务的无人机数量逐渐扩增，本文将进一步研究无人机集群的协同多任务分配问题。