多无人机协同任务分配综述

一.协同任务规划的功能与结构

多无人机协同任务规划即是根据一组特定条件的约束，以实现某个准则函数的最优或次优为目标，将某项作战任务分解成一些子任务并分配给多无人机系统中的各个无人机分别去完成的过程。 通常多无人机任务规划可以分成两大部分：上层的任务分配(Task Assignment or Task Allocation)和下层的路径规划(Path Planning)

任务分配考虑各种约束条件，以总体任务有效达成为目标，将具体目标和行动任务分配给各机，而各机根据分配的任务再进行具体的作战路径规划。

而路径规划的功能是在满足如最大线性速度、最大转角速度、操作的安全性、时间和环境变量等自身或外部限制的前提下在一系列位置之间设计或生成路径。同时，多无人机协同任务规划系统本身又是整个多无人机协同控制系统的重要组成部分。

二.任务分配

按照无人机作战任务之间的相关联性，可归类为
1.独立任务分配
2.协同任务分配

按照无人机作战任务所处环境可分为
1.静态任务分配
2.动态任务分配

按照分配方法可分为
1.集中式任务分配
2.分布式任务分配
3.分层式分布任务分配

协同任务分配

多无人机协同任务分配的目标是在考虑各种诸如任务执行顺序、时间、无人机自身物理条件等约束条件的前提下，以总体任务效率最优或次优为目标，离线地或实时地将具体目标和行动任务分配给各机。

三.建模

以集中式控制系统为基础进行任务分配最常用的模型有
多旅行商问题（multiple traveling salesman problem,MTSP）模型[13]、
车辆路径问题(Vehicle Routing,VRP)模型[14]、
多机路径分配模型(mVRP)[19]、
混合整数线性规划问题(Mixed-Integer Linear Programming ,MILP,)模型[15]、
动态网络流优化（Dynamic Network Flow Optimization ,DNFO)模型[16]、
多处理器资源分配问题模型(Multiple Processsors Resources Allocation ,CMTMP)模型[17]
除了上述模型外，美国空军研究实验室在无人机任务分配研究中建立了
带时间窗的不同能力约束车辆路径问题(CVRPTW,Capacitated Vehicle Routing Problem with Time Windows）

四.方法

1. 集中式任务分配方法

集中式控制系统就是编队中的无人机之间的通信、信号的传输和控制均由唯一的一个控制中心来进行。
常用的模型有MTSP、VRP、MILP、DNFO、CMTAP。

1.1最优化方法

(1)穷举法，适用于离散且规模小的情况
(2)整数规划法(Mixed-Integer Linear Programming,MIP)根据既定的目的和目标，通过建立目标函数和约束条件的方法对规模较小的任务分配问题进行解决的一种最优化方法矩阵作业法、单纯型法、匈牙利法、分支定界法等是比较常用的整数规划方法。
(3)约束规划(Constaint Programming CP)方法由变量集和约束集两者组成，变量集内的所有变量都有自己对应的值域，且变量的取值也只能从其值域中选取，它是求解组合优化问题的一种通用方法。
(4)图论方法是通过图示的方法把任务和接受任务的成员特征表述出来，同时在任务和系统成员之间用图论方法建立匹配，以此设计出合理可行的任务分配方案。网络流模型和偶图匹配模型是两种经典的图论任务分配模型。

1.2启发式算法

在能够接受的时间范围内求得局部最优解或满意解。
(1)列表规划（List Scheduling，LS）方法的步骤是首先建立任务的优先权函数，求得任务的处理次序，然后按照求得的任务处理次序将任务分派给系统成员。最常见的列表规划方法有动态列表规划（Dynamic List Scheduling ，DLS）法、多维动态列表规划（Multi-Dimensional Dynamic List Scheduling,MDLS）方法、多优先级动态列表规划（Multi-Priority List Dynamic Scheduling ,MPLDS）等。
(2)智能优化算法
①进化算法EA 遗传算法GA 遗传规划Genetic Programming-GP 进化规划Evolutionary Programming-GP等
②群智能算法 PSO ACO
③人工免疫、禁忌搜索、模拟退火。

2.分布式任务分配

分布式控制系统与集中式控制系统不同的是实现信号传输的方式，前者无人机还可以在编队内进行通信，具有更好的灵活性。分布式控制系统结构相比集中式控制系统结构来说对无人机的要求更高，需要无人机具备独立计算、分析与决策等能力。

2.1合同网方法

目前，合同网（ContractNet）是应用范围最广的一种分布式任务分配方法，它的核心是为防止产生冲突，对每个问题的求解用通信的方式协商处理。[25]
合同网方法有发布者和竞标者两个角色，由“招标- 投标- 中标- 确认”4 个交互阶段组成。在合同网协作方法中，系统成员的角色不用提前规定，任何系统成员可以是管理者，也可以是工作者，区别只在于成员是发布任务通知还是应答任务通知，于是任务能够被层次地分解分派。这种方法的缺点是通信量大、作为发布者的系统成员工作强度大且任务分解分配没有有效融合等。

2.2 拍卖方法

拍卖方法是实现资源配置的一种市场机制，指的是买方在清楚了解拍卖规则的前提下，采用竞价的方式决定特定物品的价格，也就是将要拍卖的物品用公开竞价的方式转卖给应价最高（ 最低）者的一种交易方式。一个拍卖主要由参与方、拍卖品、收益函数和应价策略4 个要素组成，在无人机任务分配问题中，无人机需要执行的任务可视为拍卖品，无人机的任务分配方和任务接受方共同组成参与者，且双方都有各自对应的收益函数和出价策略。拍卖方法是一种协商协议，因其规则明确且便于操作，近年来受到越来越多学者们的关注。拍卖方法用明确的规则引导买卖双方进行交互，可操作性非常强，能在较短时间内将资源合理分配，得到问题的最优解或较优解。该方法现已广泛运用在无人机作战和传感器等资源分配问题中。

综述

文献[1] 将任务分配方法归纳为集中式任务分配、分布式任务分配、分层次分布式任务分配三类，并对方法进行了简单阐述，提出了几个任务分配的可能的未来发展趋势。

文献［6］归纳和总结了多无人机协同任务规划的国内外研究现状，重点总结了任务分配方法的常见模型和算法，对各种算法的优缺点进行了讨论，得出多智能体的市场机制类算法在空战中将有广泛的应用价值。

模型

文献［5］探索了对不同种类的目标进行侦察、打击和评估任务时异构无人机的协同任务分配问题。对于侦察与评估任务中所得到的信息量，运用信息论中熵的变化量对其进行度量，把无人机对不同类型目标的打击能力简化为对目标的毁伤概率，同时把每个任务之间的关联性考虑在内，建立了异构多无人机协同任务分配模型。

文献［7］建立了以合同网协议和多智能体系统理论为基础的有人机／ 无人机编队MAS(Multi-agent System MAS)结构和基于投标过程的无人机任务分配模型。

文献[23]提出了集群组网任务分配模型和任务分配求解算法。分析了集群组网的任务分配问题，并剖析了任务分配分层递阶结构；借助层次分析思路，建立了集群组网任务分配模型；结合群体智能优化算法的优势，提出了基于PSO-ICWPA 的集群组网任务分配算法；

同构

文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。

1.蚁群

文献［8］在无人机协同多任务分配的研究中，运用了基于分工机制的蚁群算法进行求解，并给出了基于作战任务能力评估的问题解构造策略和基于作战任务代价的状态转移规则，大幅度提升了算法的性能。

2.粒子群

文献［11］设计出一种多无人机任务分配与航迹规划相结合的整体控制架构，假设威胁和障碍区域为合理的多边形模型，使用改进的算法求出两个航迹点之间的最短路径，将此路径当成任务分配过程全局目标函数的输入，然后用粒子群优化任务分配迭代寻优。

文献［10］在基于任务依赖关系和ISO–DATA（Iterative Self-organizing Data Analysis Technique）算法相结合的基础上设计了新的任务分组方法，在保持无人机负载均衡的基础上，给出了基于资源福利的任务组级组粗粒度的无人机任务分配方法，在任务组内提出了结合粒子群算法的细粒度任务分配算法。

文献[21]通过综合考虑多无人机任务分配约束条件，以多UCAV 总飞行航程和多UCAV 总飞行时间两个关
键指标作为任务分配方案的评价标准，构建多无人机任务分配模型，采用改进的QPSO 算法进行优化求解多无人机任务分配问题。

文献[22]，综合考虑了协同多任务分配问题的任务优先级和任务协同约束、任务时间约束，同时针对无人机载弹量有限的实际情况，将无人机的载弹量约束等同于无人机执行攻击任务的最大次数限制，建立了协同多任务分配模型，在算法引入自组织惯性权重和加速系数，增强了算法的全局和局部搜索能力，优于遗传算法的协同多任务分配。

GA

文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 用整数规划法MIP和遗传算法求解。但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。

文献[24]针对战场环境的多目标、多任务以及无人机能力有限等特点，设计了一种适应于多目标、多无人机、多任务种类的无人机群协同多任务分配模型。结合该模型以及其中的任务偏序约束、协同任务约束、无人机能力约束等约束条件提出了基于任务序列的遗传算法染色体编码方法，和基于同类任务的遗传算法交叉、变异算子。该方法利用遗传算法的全局搜索优化解特点，对无人机群的协同任务分配进行优化.

动态及不确定环境下

文献[12]分析了实际战场上信息的不确定性，同时指出了在此条件下多无人机面临的任务分配问题。将收益毁伤代价指标、目标价值及航程代价指标的不确定信息作为参考依据，在此基础上建立了基于区间
信息环境下多无人机的任务分配模型，采用随机概率的多属性方案排序（Stochastic Multi-criteria Acceptability Analysis,SMAA）方法，得出不确定环境下多无人机动态任务分配求解方法。

文献[3]建立了多UCAV任务分配模型，对动态重分配策略进行研究并做出改进，将周期性重调度和事件驱动重调度进行有机结合。提出了一种改进的混合重调度策略．增加了对突发事件的处理能力，并结合粒子群算法和细菌觅食算法的优缺点。提出了混合细菌觅食算法(PBFO)解决多UCAV的动态任务分配问题。

异构

文献［9］以异构类型多目标多无人机任务分配问题为原型，设计了一种基于时间窗的多无人机联盟组任务分配方法，此算法使用冲突消解机制来防止无人机实时任务分配过程中出现多机资源死锁，其次通过无人机两阶段任务联盟构成算法，组成了任务联盟，使无人机任务分配的有效性和实时性有了很大的提高。
文献[18]以多异构无人机执行SEAD任务为背景采用图论的方法完成问题的建模,将无人机本体等效为Dubins Car模型,并对其在相应目标处执行侦查、打击、评估任务时的进入角度进行约束,通过Dubins路径完成对无人机飞行路径的等效,采用分布式遗传算法完成对问题的快速求解.

文献[4]基于文献[20]的研究成果,将模型适用范围扩展到了异构UAV,但对约束条件的假设仍然相对理想.

文献

[1]陈侠,乔艳芝.无人机任务分配综述[J].沈阳航空航天大学学报,2016,33(6):1-7. DOI:10.3969/j.issn.2095-1248.2016.06.001.
[2]李炜,张伟. 基于粒子群算法的多无人机任务分配方法[J].控制与决策，2010,25(9):1359 -1364.
[3]杨尚君,王社伟,陶军, 等.动态环境下的多UCAV协同任务分配研究[J].电光与控制,2012,19(7):32-36,79. DOI:10.3969/j.issn.1671-637X.2012.07.008.
[4]Wang J, Zhang Y F, Geng L, et al. A heuristicmission planning algorithm for heterogeneous tasks with
heterogeneous UAVs[J]. Unmanned Systems, 2015, 3(3):205-219.
[5]邸斌,周锐,丁全心. 多无人机分布式协同异构任务分配[J].控制与决策,2013,28(2):274 -278.
[6]朱毅,张涛,程农,等.多UAV协同任务规划研究[J]. 系统仿真学报,2009(20):194 -199.
[7]刘跃峰,张安.有人机/无人机编队协同任务分配方法[J]. 系统工程与电子技术,2010，32(3):584-588.
[8]苏菲,，陈岩,沈林成.基于蚁群算法的无人机协同多任务分配[J]. 航空学报,2008(29):184-191.
[9]林林,孙其博,王尚广,等.基于时间窗的多无人机联盟任务分配方法研究[J].电子与信息学报,2013,35(8):1983-1988.
[10]谭何顺,曹雷,彭辉,等. 一种多无人机层次化任务分配方法[J]. 解放军理工大学学报(自然科学版),2014,15(1):18 -24.
[11]孙小雷,齐乃明,董程,等. 无人机任务分配与航迹规划协同控制方法[J]. 火力与指挥控制,2015,37(12):2772 -2776.
[12]陈侠,唐婷.不确定环境下多无人机动态任务分配方法.火力与指挥控制[J].2013,38(1):45 -49.
[13]SECREST. Traveling salesman problem for surveillance mission using particel swarm optimization [Ｄ]. wright-PattersonAFB:Air Force Institute of Technologhy,2003.
[14]O’Rourke K P,Bailey T G,Hill R,et al. Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search[J].Military Operations Research Journal, 2001(6):5 -30.
[15]ALIGHANBARI M.Task assignment algorithms for teams of UAVs in dynamic environments[D].Cambridge:Massachusetts Institute of Technology,2004.
[16]NYGARD K E,CHANDLER P R,PACHTER M.Dynamic network flow optimization modles for air vehicle resourceallocation[C]//Proceedingsofthe 2001 American Control Conference,2001,3:1853-1858.
[17] ALVARO E G .Stability Analysis of Network-based Cooperative Resource Allocation Strategies[D].Columbus:Ohio State University,2003.
[18]吴蔚楠,关英姿,郭继峰, 等.基于SEAD任务特性约束的协同任务分配方法[J].控制与策,2017,32(9):1574-1582. DOI:10.13195/j.kzyjc.2016.0858.
[19] Arsie A, Savla K, Frazzoli E. Efficient routing algorithmsfor multiple vehicles with no explicit communications[J].IEEE Trans on Automatic Control, 2009, 54(10):2302-2317.
[20]Geng L, Zhang Y F, Wang J, et al. Cooperative missionplanning with multipleUAVs in realistic environments[J].Unmanned Systems, 2014, 2(1): 73-86.
[21]邓可,连振江,周德云, 等.基于改进量子粒子群算法的多无人机任务分配[J].指挥控制与仿真,2018,40(5):32-36. DOI:10.3969/j.issn.1673-3819.2018.05.007.
[22]梁国强,康宇航,邢志川, 等.基于离散粒子群优化的无人机协同多任务分配[J].计算机仿真,2018,35(2):22-28. DOI:10.3969/j.issn.1006-9348.2018.02.005.
[23]汪汝根,李为民,刘永兰,刘金松.无人机集群组网任务分配方法研究[J].系统仿真学报,2018,30(12):4794-4801+4807.
[24]姚敏,王绪芝,赵敏.无人机群协同作战任务分配方法研究[J].电子科技大学学报,2013,(5):723-727. DOI:10.3969/j.issn.1001-0548.2013.05.015.
[25]SM ITH R G.The Contractnet Protocol :High level Communication and Control in a Distributed problem solver [J]. IEEE Transaction and Computers