协同任务分配的控制方式主要有3种：集中式控制、分布式控制和分层次分布式控制[5]。其中，对于集中式控制，协同多任务分配问题(Cooperative Multi-Task Assignment Problem, CMTAP)模型可以对无人机执行任务的约束进行有效建模[6-7]，受到众多研究者的关注。
很多****从不同方面对CMTAP模型进行了改进，文献[7]考虑动态任务时间和无人机任务能力约束，通过总航程最小化且完成任务数量最大求解模型，但没有考虑载机弹药数量约束；文献[8]考虑任务之间的时序耦合约束，通过最小化航程最大的无人机的航程求解模型，但没有考虑不同飞机执行任务能力的约束; 文献[9-10]考虑时间窗约束，通过收益最大化求解模型，但仅考虑了时间窗约束; 文献[11]考虑目标的时间敏感性，需要在指定的时间内执行任务，通过收益最大化求解模型，但没有考虑任务之间的时间间隔; 文献[12]考虑载机弹药等约束，通过收益最大且执行时间最小求解模型，但没有考虑飞机执行任务能力的约束; 文献[13]考虑目标毁伤价值、编队损耗代价及时间消耗，通过毁伤最大且时间及消耗最小求解模型，但没有考虑载机弹药数量约束。
在求解无人机编队的CMTAP上，已有很多算法，如离散粒子群优化(DPSO)算法[14]、差分进化(DE)算法[15]、郭涛(GT)算法[16]、离散粒子群-郭涛(DPSO-GT)算法[9]、离散粒子群-郭涛-模拟退火(DPSO-GT-SA)算法[17]。但是，DPSO算法收敛速度慢、精度低，DE算法具有较好的全局收敛性，但是收敛速度仍然较慢，DPSO-GT算法虽然收敛速度快，但是容易陷入局部极值，DPSO-GT-SA算法虽然具有较好的收敛性，但是收敛速度及全局收敛性上仍然有待提高。
作战飞机在执行任务时，已经出现了多机协同执行任务的情况，如协同探测[18]、协同攻击[19-20]，这说明有时同一个作战任务需要多架飞机协同完成。本文在前人研究基础上，对CMTAP模型考虑了时序约束、航程约束、任务能力约束、时间约束、时间间隔约束和载机弹药约束，同时考虑无人机协同执行任务的情况，增加了任务协同约束。在此基础上，将DE算法、DPSO算法、GT算法及SA算法进行融合，构造DE-DPSO-GT-SA算法来求解该模型，仿真结果表明，本文算法具有更好的收敛性和收敛速度。
1 问题模型 假设我方执行任务的飞机编队由NU架飞机构成，表示为U={U1, U2, …, UNU}；设目标总共有NC个，表示为C={c1, c2, …, cNC}；每个目标上有多种类型任务需要执行，设任务类型总共有3个，表示为M={m1, m2, m3}，m1表示探测，m2表示攻击，m3表示评估。则目标ci上的任务mj为Scimj，其数值表示需要N(Scimj)架飞机同时到达任务点共同执行任务，对于探测和攻击任务，双击协同比单机协同更具优势[18-19]。所以，本文中探测及攻击任务采取双击协同方式执行，则N(Scimj)的最大值为2，任务总数为NT=
 | (1) |
1.1 约束条件 本文考虑的约束条件如下：
1) ?时序约束。对每个目标执行任务时，首先执行探测任务；其次执行攻击任务；最后执行评估任务。表示为
 | (2) |
式中:tcimj(j=1, 2, 3)为目标ci(i=1, 2, …, NC)相应类型任务被执行时的时刻。
2) ?航程约束。对于每架无人机，其执行任务飞行的航程应小于其最大航程，表示为
 | (3) |
式中:LmaxUi为第i架无人机的最大航程；LUi为第i架飞机执行任务时所用的航程。
3) ?任务能力约束。在异构无人机组成的编队中，每架无人机所能执行的任务种类是有限的，所以，每架无人机只能执行自身能力集合内的任务，表示为
 | (4) |
式中：MissionKind(Ui)为飞机Ui能执行的任务类型集合；AssignMission(Ui)为分配给Ui飞机的任务类型集合。
4) ?时间约束。如果某任务需要在指定的时间范围内执行，则称该任务具有任务时间约束，通常对于机动目标存在这样的约束，可表示为
 | (5) |
式中：ETi为任务可以执行的最早时刻；LTi为任务可以执行的最晚时刻; ti为该任务实际开始执行的时刻。
5) ?任务间隔约束。如果某任务需要在上一个任务执行完后的一段时间范围内执行，则称该任务具有任务间隔约束，通常评估任务具有此约束，可表示为
 | (6) |
式中:Time(pre(Ti))为上一个任务Ti执行完的时刻; Δtmini为当前任务开始执行的最小间隔；Δtmaxi为当前任务开始执行的最大间隔。
6) ?载机弹药约束。无人机执行任务会消耗自身的资源，弹药就是其中一种，其执行的攻击任务需要消耗的弹药数目需小于自身可用的弹药数目，表示为
 | (7) |
式中:MissileAmount(Ui)为无人机Ui能可用的导弹数量；AssignMissile(Ui)为分配给此无人机的任务所需要用的导弹数量。
7) ?任务协同约束。某任务需要多架无人机协同完成时，这些飞机不能是同一架飞机多架次执行，而是不同架飞机同时到达任务点执行任务，表示为
 | (8) |
式中:PlaneSet(Ti)为可以协同执行任务Ti的飞机集合; AssignPlane(Ti)为分配给此协同任务的飞机集合; tuk和tuj为执行协同任务Ti的飞机开始执行此任务的时刻。
1.2 任务分配评价指标 无人机编队需要尽可能多的完成任务，并且所有任务完成的时间要尽可能小，所以构造如下任务分配评价指标：
 | (9) |
式中:N(Ui)为第i架飞机完成的任务数量；J1为整个无人机编队完成的任务总数；tUi为第i架飞机完成分配给其执行的任务的总时间；J2为无人机编队完成所有分配任务所用的时间；G为目标函数。
2 DE-DPSO-GT-SA算法 对于飞机编队的CMTAP，本文将DE算法、DPSO算法、GT算法及SA算法相结合，提出DE-DPSO-GT-SA算法。首先, 将DPSO算法与DE算法相结合，构造差分操作，通过向全局极值和局部极值的粒子学习以提高算法求解最优解的效率; 其次，将DE算法与GT算法相结合，构造变异操作，通过提高粒子的多样性以提高算法的全局搜索能力；最后，通过SA算法使粒子更容易跳出局部最优解。
2.1 粒子表示 种群总数为NP；任务总数为NT；子任务总数为NST，第i个粒子表示为
 | (10) |
式中:xji为第i个粒子的第j位置上的值，其值为整数，范围为0≤xji≤NC，值为零表示此任务未分配飞机，值为非零表示此任务分配给对应编号的飞机。
以任务总数NT为8，子任务总数NST为10，对粒子表示进行示例性描述，如图 1所示。对于双机协同探测，由于不受约束限制，所以不区分角色，而对于双机协同攻击，根据文献[18]，一般由一架飞机发射导弹，另一架飞机接力制导，并且本文考虑了载机弹药约束，所以指定任务号小的为发射，另一个为制导。
 |
| 图 1 粒子表示示例 Fig. 1 Example of coding particle |
| 图选项 |
2.2 更新策略 1) ?差分操作。根据文献[16-17]，DPSO算法的粒子更新分为速度更新和位置更新，而DE算法的变异操作与之类似，可以理解为不同数据集的差分操作。为了结合2种差分操作，本文采用式(11)~式(13)计算。
 | (11) |
 | (12) |
 | (13) |
式中:rand为0~1之间的随机数; pr1k和pr2k为任意选择的且互不相等的个体极值; prk为第r个粒子的第k次迭代的个体极值; F0为缩放因子; urk+1为DE算法更新后的粒子; d1和d2分别为个体和群体的学习因子; r1和r2为0~1之间的随机数; pgk为第k次迭代的全局极值; w为速度的惯性权重; vrk+1为DPSO算法速度更新后的速度; yrk+1为DPSO算法位置更新后的粒子；brk+1为差分操作后更新的粒子; p1为差分概率。
2) ?变异操作。根据文献[16, 19]，本文采用DE算法的交叉操作和GT算法的序列倒置操作构成变异操作，采用式(14)~式(16)计算。
 | (14) |
 | (15) |
 | (16) |
式中：CR为交叉概率; zrk+1为DE算法更新后的粒子，下标i表示对粒子的每个位置按照交叉概率进行交叉；hrk+1为GT算法序列倒置操作后的粒子；inver(·)为序列倒置操作，即将顺序从a到b位置上的值换成顺序从b到a位置上的值；a和b为1~NST之间随机选择的不相等的整数；p2为变异概率；crk+1为变异操作后更新的粒子。
3) ?模拟退火操作。根据文献[20]，采用的模拟退火操作为
 | (17) |
式中:W为温度，根据文献[20]采用动态温度衰减因子；Grk+1和Grk分别为旧粒子和新粒子的适应度值，通过式(9)计算得到；er为新旧粒子的适应度值的差；Xrk+1为退火操作后的新粒子。
2.3 算法步骤 具体流程如下：
步骤?1??初始化参数。确定种群规模NP，惯性权重w，学习因子d1和d2；差分概率p1；变异概率p2；缩放因子F0；交叉概率CR；温度W；随机生成初始种群；模拟退火迭代次数L；更新代数loop。
步骤?2??适应度值计算。计算每个粒子的适应度值Gr，根据适应度值选择出个体极值pr和全局极值pg。
步骤?3??差分操作。根据式(11)~式(13)完成差分操作。
步骤?4??变异操作。根据式(14)~式(16)完成变异操作。
步骤?5??模拟退火操作。根据式(17)完成模拟退火操作。
步骤?6??更新计算。根据适应度值选择出个体极值pr和全局极值pg。
步骤?7??模拟退火迭代判断。判断模拟退火迭代次数是否到达L，如果未到达，跳转到步骤3，如果到达，进行步骤8。
步骤?8??更新代数判断。判断循环代数是否到达loop，如果到达，终止寻优，如果未到达，跳转到步骤3继续迭代。
3 仿真验证及分析 为验证本文算法及模型的有效性和可行性，将其与DPSO算法、DE算法、DPSO-GT算法、DPSO-GT-SA算法进行仿真对比分析。
假设我方作战飞机编队由6架不同能力的飞机组成，任务目标点有10个。飞机作战能力表如表 1所示，表中：飞机所具有的能力项用勾选表示，不具有的能力未勾选。任务目标点信息如表 2所示，表中：0表示无任务；1表示单机执行的任务；2表示需要双机协同执行的任务。战场环境中我方飞机编队和任务目标点位置如图 2所示。
表 1 飞机作战能力 Table 1 Combat capabilities of aircraft
| 飞机编号 | 起始位置/m | 航程/m | 导弹数目 | 速度/(m·s-1) | 任务能力 | ||
| 探测 | 攻击 | 评估 | |||||
| 1 | (1 000, 500) | 100 000 | 4 | 200 | √ | √ | √ |
| 2 | (500, 1 000) | 100 000 | 4 | 200 | √ | √ | |
| 3 | (1 000, 1 000) | 100 000 | 2 | 300 | √ | √ | √ |
| 4 | (0, 1 000) | 100 000 | 4 | 300 | √ | √ | |
| 5 | (1 000, 0) | 100 000 | 8 | 300 | √ | √ | |
| 6 | (0, 0) | 100 000 | 4 | 200 | √ | √ | |
表选项
表 2 任务目标点信息 Table 2 Information of task target points
| 目标编号 | 目标位置/m | 执行任务所需飞机架数 | ||
| 探测 | 攻击 | 评估 | ||
| 1 | (10 000, 10 000) | 1 | 1 | 1 |
| 2 | (20 000, 20 000) | 2 | 1 | 1 |
| 3 | (14 000, 6 000) | 0 | 1 | 1 |
| 4 | (8 000, 16 000) | 0 | 1 | 1 |
| 5 | (20 000, 10 000) | 1 | 1 | 0 |
| 6 | (10 000, 20 000) | 1 | 2 | 1 |
| 7 | (15 000, 15 000) | 2 | 2 | 1 |
| 8 | (8 000, 5 000) | 0 | 1 | 0 |
| 9 | (1 000, 3 000) | 1 | 0 | 0 |
| 10 | (5 000, 8 000) | 1 | 1 | 0 |
表选项
 |
| 图 2 仿真环境初始位置 Fig. 2 Initial location of simulation environment |
| 图选项 |
假设无论单机还是双机，探测任务执行时间为20 s，攻击任务执行时间为10 s，评估任务执行时间为20 s，评估任务和攻击任务之间有间隔约束，最小间隔时间为10 s，最大间隔时间为120 s，目标编号3和目标编号8为时敏目标，有任务时刻约束，需要在指定的时刻内开始执行攻击任务，目标3最早攻击时刻为80 s，最晚攻击时刻为110 s，目标8最早攻击时刻为150 s，最晚攻击时刻为190 s。
仿真中，惯性权重w设为0.9;学习因子d1和d2设为2;缩放因子F0为0.3;交叉概率CR为0.3;差分概率p1为0.5;变异概率p2为0.5;种群规模NP为20;迭代总数loop为200;温度W为1 000;根据文献[16]设置衰减因子为0.99;模拟退火迭代次数L为4。
迭代200次后，本文算法得到的优化结果为[4, 3, 5, 4, 5, 3, 5, 1, 1, 1, 4, 2, 6, 4, 2, 1, 1, 1, 6, 2, 2, 3, 3]。图 3给出每架飞机按照时间执行的任务序列，线上的数字表示的是任务号。图 4给出每个目标点的任务按照时间被执行情况，线上的数字表示飞机号，对于协同探测和协同攻击，线上有2个数字，表示执行此协同任务的2个飞机号。
 |
| 图 3 飞机任务分配结果 Fig. 3 Task assignment results of aircraft |
| 图选项 |
 |
| 图 4 目标任务执行情况 Fig. 4 Results of target tasks being executed |
| 图选项 |
从图 3和图 4可以看出，目标编号3的攻击任务开始执行时刻为80 s，目标编号8的攻击任务开始执行时刻为150 s，满足其任务时间约束。对于目标编号为2的协同探测任务，分配了3和5两架飞机，两架飞机于95~115 s同时执行对目标2的探测任务，目标6的协同攻击任务分配了5和3两架飞机，两架飞机于230~240 s同时执行对目标6的攻击任务，目标7的协同探测分配了3和5两架飞机，两架飞机于135~155 s同时执行对目标7的探测任务，目标7的攻击任务分配了2和3两架飞机，两架飞机于165~175 s同时执行对目标7的攻击任务，满足任务协同约束。目标1、2、3、6、7的评估任务在攻击任务10 s后开始执行，目标4的评估任务在攻击任务120 s内执行，满足时间间隔约束。所有目标的任务都是先执行探测，再攻击，最后评估，满足任务时序约束。
从表 3可以看出，每架飞机所使用的导弹数目，满足载机弹药使用约束, 每架飞机飞行的航程在其航程允许范围内，满足航程约束。
表 3 导弹和航程使用情况 Table 3 Missile and distance of aircraft
| 飞机编号 | 携带的导弹数目 | 已用导弹数目 | 航程/m | 飞行距离/m |
| 1 | 4 | 3 | 100 000 | 51 628 |
| 2 | 4 | 1 | 100 000 | 46 126 |
| 3 | 2 | 1 | 100 000 | 80 654 |
| 4 | 4 | 2 | 100 000 | 61 454 |
| 5 | 8 | 1 | 100 000 | 71 654 |
| 6 | 4 | 1 | 100 000 | 38 302 |
表选项
为检验算法的收敛性，进行50次仿真试验，对所得数据进行求和取平均。5种算法的仿真结果如图 5所示，可见本文算法具有较好的收敛性。
 |
| 图 5 5种算法的最优迭代过程比较 Fig. 5 Comparison of optimal iterative process among five algorithms |
| 图选项 |
如表 4所示，从平均运行时间，适应度值的最优值、最劣值、平均值进行比较，本文算法收敛的最优值、最劣质、平均值都好于其他4种算法，说明收敛较稳定，收敛的结果较好，但是，比其他算法所用的运行时间多。
表 4 5种算法综合比较 Table 4 Comprehensive comparison of five algorithms
| 算法 | 适应度值 | 平均运行时间/s | ||
| 最优值 | 最劣值 | 平均值 | ||
| DPSO | 0.067 8 | 0.057 0 | 0.060 2 | 91.834 0 |
| DE | 0.075 3 | 0.062 9 | 0.067 2 | 99.549 4 |
| DPSO-GT | 0.078 1 | 0.062 5 | 0.068 5 | 222.813 6 |
| DPSO-GT-SA | 0.079 4 | 0.063 4 | 0.070 6 | 355.067 3 |
| DE-DPSO-GT-SA | 0.080 2 | 0.065 2 | 0.071 8 | 359.244 7 |
表选项
4 结论 1) ?考虑双机协同探测和双机协同攻击任务分配情况，对CMTAP模型引入了新的约束。
2) ?将DPSO算法、GT算法和DE算法进行融合，通过SA算法循环迭代，提出了DE-DPSO-GT-SA算法，仿真表明本文算法具有较好的收敛性能。
参考文献
| [1] | ALIGHANBARI M.Task assignment algorithms for teams of UAVs in dynamic environments[D].Cambridge: Massachusetts Institute of Technology, 2014: 25-30. |
| [2] | SHI Z, YANG B, LIU H Y.Modeling and simulation of UCAV swarm cooperative task assignment[C]//2010 Third International Conference on Information and Computing(ICIC).Piscataway: IEEE Press, 2010: 308-311. |
| [3] | 尹高扬, 周绍磊, 贺鹏程, 等. 国外多无人机协同任务分配研究现状及发展趋势[J]. 飞航导弹, 2016(5): 54-58. YIN G Y, ZHOU S L, HE P C, et al. Research status and development trend of cooperative task allocation for multiple UAVs in foreign countries[J]. Aerodynamic Missile Journal, 2016(5): 54-58. (in Chinese) |
| [4] | PACK D, YORK G, FIERRO R.Information-based cooperative control for multiple unmanned aerial vehicles[C]//Proceeding of the 2006 IEEE International Conference on Networking, Sensing and Control.Piscataway: IEEE Press, 2006: 446-450. |
| [5] | 陈侠, 乔艳芝. 无人机任务分配综述[J]. 沈阳航空航天大学学报, 2016, 33(6): 1-7. CHEN X, QIAO Y Z. Summary of unmanned aerial vehicle task allocation[J]. Journal of Shenyang Aerospace University, 2016, 33(6): 1-7. DOI:10.3969/j.issn.2095-1248.2016.06.001 (in Chinese) |
| [6] | SHIMA T, RASMUSSEN S J, SPARKS A G. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33(11): 3252-3269. |
| [7] | 苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(S1): S184-S191. SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(S1): S184-S191. (in Chinese) |
| [8] | 张耀中, 陈岚, 史国庆, 等. 时序耦合约束下的多无人机协同任务决策研究[J]. 西北工业大学学报, 2018, 36(5): 890-896. ZHANG Y Z, CHEN L, SHI G Q, et al. Collaborative task assignment for multi-UAV with sequence and time constrains[J]. Journal of Northwestern Polytechnical University, 2018, 36(5): 890-896. DOI:10.3969/j.issn.1000-2758.2018.05.011 (in Chinese) |
| [9] | 颜骥, 李相民, 刘波. 应用离散粒子群-郭涛算法分配多无人机协同任务[J]. 国防科技大学学报, 2015, 37(4): 165-171. YAN J, LI X M, LIU B. Cooperative task allocation of multi-UAVs with mixed DPSO-GT algorithm[J]. Journal of National University of Defense Technology, 2015, 37(4): 165-171. (in Chinese) |
| [10] | JIA Z, YU J, AI X, et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm[J]. Aerospace Science and Technology, 2018, 76(1): 112-125. |
| [11] | 王宇琦, 张安, 毕文. 有人/无人机编队打击时敏目标任务分配[J]. 电光与控制, 2018, 25(8): 7-10. WANG Y Q, ZHANG A, BI W. Mission planning of manned/unmanned aerial vehicle formation for time critical target attacking[J]. Electronics Optics & Control, 2018, 25(8): 7-10. DOI:10.3969/j.issn.1671-637X.2018.08.002 (in Chinese) |
| [12] | 田震, 王晓芳. 基于多基因遗传算法的异构多无人机协同任务分配[J]. 飞行力学, 2019, 37(1): 39-44. TIAN Z, WANG X F. Cooperative multiple task assignment for heterogeneous multi-UAVs with multi-chromosome genetic algorithm[J]. Flight Dynamics, 2019, 37(1): 39-44. (in Chinese) |
| [13] | DENG Q, YU J, WANG N. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algothrithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250. DOI:10.1016/j.cja.2013.07.009 |
| [14] | 李炜, 张伟. 基于粒子群算法的多无人机任务分配方法[J]. 控制与决策, 2010, 25(9): 1359-1363. LI W, ZHANG W. Method of tasks allocation of multi-UAVs based on particles swarm optimization[J]. Control and Decision, 2010, 25(9): 1359-1363. (in Chinese) |
| [15] | 宋敏, 魏瑞轩, 冯志明. 基于差分进化算法的异构多无人机任务分配[J]. 系统仿真学报, 2010, 22(7): 1705-1710. SONG M, WEI R X, FENG Z M. Cooperative task assignment for heterogeneous multi-UAVs based on differential evolution algorithm[J]. Journal of System Simulation, 2010, 22(7): 1705-1710. (in Chinese) |
| [16] | TAO G, MICHALEWICZ Z.Inver-over operator for the TSP[C]//Proceedings of the 5th International Conference on Parallel Problem Solving from Nature.Berlin: Springer, 1998: 803-812. |
| [17] | 宗群, 秦新立, 张博渊, 等. 基于DPSO-GT-SA算法的大规模UCAV协同任务分配[J]. 天津大学学报(自然科学与工程技术版), 2018, 10(51): 7-11. ZONG Q, QIN X L, ZHANG B Y, et al. Cooperative task allocation of large-scale UCAV based on DPSO-GT-SA algorithm[J]. Journal of Tianjin University(Science and Technology), 2018, 10(51): 7-11. (in Chinese) |
| [18] | 孙晓闻. 无人/有人机协同探测/作战应用研究[J]. 中国电子科学研究院学报, 2014, 9(4): 331-334. SUN X W. Application research for cooperative detection combat of unmanned/manned aerial vehicles[J]. Journal of CAEIT, 2014, 9(4): 331-334. DOI:10.3969/j.issn.1673-5692.2014.04.001 (in Chinese) |
| [19] | 付昭旺, 于雷, 周中良, 等. 双击协同攻击指令瞄准建模及精度研究[J]. 空军工程大学学报(自然科学版), 2013, 14(1): 5-10. FU Z W, YU L, ZHOU Z L, et al. Research on coordinated targeting modeling and precision for double fighter[J]. Journal of Air Force Engineering University(Natural Science Edition), 2013, 14(1): 5-10. (in Chinese) |
| [20] | 刁兴华, 方洋旺, 伍友利, 等. 双机编队空空导弹协同发射区模拟仿真分析[J]. 北京航空航天大学学报, 2014, 40(3): 370-376. DIAO X H, FANG Y W, WU Y L, et al. Simulation analysis on air-to-air missile allowable launch envelope about cooperative air combat of multi-fighter formation[J]. Journal of Beijing University of Aeronautics and Astronautics, 2014, 40(3): 370-376. (in Chinese) |
