1 引言
无人机族群任务规划是指在复杂的作战地域内，将各种任务类型的多个无人机族进行统一的协同规划，使每个无人机按时序、时隙要求到达指定任务区域执行作战任务。任务规划需要对所有任务类型的无人机进行整体规划，根据任务要求，将相应的任务分配给各类型无人机族，保证所有无人机高效完成任务[1]。当前，国内外针对大规模无人机任务规划问题的解决方法主要有2种：
第1种是分布式规划方法，使用同构无人机集群，完成分配给无人机的相似任务。例如，使用多个侦察无人机执行特定区域的侦察任务，文献[2]就是这种规划方法，可以很好地解决单一任务的规划要求，但是不同任务之间缺乏协同，很难满足实际作战中多类型任务间的协同需求。
第2种是集中式规划方法，使用异构无人机集群，完成侦察、攻击等特定协同任务的规划方法。例如，执行攻击前的侦察任务。文献[3]就是这种规划结构，考虑了不同类型任务的协同规划，可以有效解决小规模协同任务规划问题，但是对于较大规模的异构协同任务，规划效率低下。考虑到上述2种结构的优缺点，文献[4]提出了一种层级结构。这种结构根据无人机资源的数量和类型以及不同无人机之间的关系，将无人机群划分为多个子群，使大规模的任务规划问题转变为多个相关的小规模问题，该结构能有效解决目标数量较大时任务规划问题。层次结构是整理和简化复杂问题的有效手段[5]。
近年来，越来越多的学者使用多Agent理论来解决无人机任务规划问题[6]。因为多Agent理论是利用个体之间的交互作用来实现的，整个系统解决问题的能力大于各分系统解决问题能力的简单相加[7]。此外，多Agent理论具有协同性、健壮性、可扩展性和分布性等特点[8]，在解决无人机任务规划问题方面有很大优势。
针对以上问题，为更加接近实际作战，提出了一种无人机分层族群任务规划方法。族群任务规划是指在复杂战场环境中，多个任务同时进行或者时序进行时，将相同或相似任务功能及配置地域的多个无人机，以“族”的形式统一进行任务规划与控制，多个不同的“族”所组成的无人机群称为“族群”[9]。首先，根据分层结构理论及多Agent理论，将无人机族群任务规划分为4个规划层级，以实现将各类任务实时、有序的分配给各无人机族，且同时满足任务成本小、实用性强的要求；然后，将规划过程分为3步(任务预处理、任务分配和任务规划)实施；最后，对上述规划方法进行仿真验证，结果表明，该方法可以有效解决作战范围内复杂环境下多类型无人机任务规划问题。
2 任务规划模型
2.1 问题描述
在陆战场使用无人机作战中，作战范围内有多个任务区域需要多种类型无人机执行作战任务。在各个任务区域内目标因属性和作战要求不同，需要各类无人机族协同执行作战任务。
作战任务是对族群需要完成任务的描述，由指定任务步骤的多个相互关联的独立任务组成。用MS={M,D}表示，其中M={m1,m2,…,mk}表示作战任务中独立任务组成的集合，D是不同任务之间的依赖关系。其D={mi,mj}表示mj必须等mi完成后才能开始。如果将每个任务看作一个节点，把2个任务之间的关系看作有向边，则所有任务就可以用有向图表示其关系。
在执行任务过程中，任何给定的时间t都有与其相对应的状态。任务的状态可以用MSt={C,P,W}三元组表示，其中C表示已完成，P表示正在执行，W表示等待执行。当P=W={}和C=M时，表示任务已经完成。
无人机族群由不同任务功能的无人机族组成，用S表示。则S={v1,v2,…,vn}表示n个不同任务功能或配置地域的无人机族，n表示族群中族的数量。无人机族具有以下属性：
1) 一个无人机族执行单一类型任务，如侦察、攻击或者中继等；
2) 单个无人机族应位于相同的配置地域；
3) 单个无人机族执行任务的能力有限，这意味着每个族内的无人机有限。
在执行任务时，对于任意时刻t，所有无人机族都有一个t时刻的状态定义为vi(t)，其包含以下内容：
1) 执行任务的情况，即族内有多少数量的无人机正在执行任务；
2) 剩余容量，即族内还有多少数量的无人机未被分配任务；
3) 分配给此无人机族的任务列表。
族群的任务状态包括所有任务族无人机状态的集合和族群上调度的所有任务的状态集合等2个方面。
2.2 目标函数
基于上述定义，考虑以下问题：给定无人机族群S和作战任务MS，使用无人机族群以最小代价完成作战任务。
任务规划过程首先需要规划独立任务集合到无人机族集合的映射Map。该映射表示为无人机族分配相应的任务。例如，Map={m1,v2}表示将任务1分配给无人机族2。
任务代价是指完成所有任务时，无人机族群需要付出代价的总和。对于不同类型的独立任务，任务的代价是不同的。一般说来，独立任务的代价是指族内任务无人机从配置地域到任务地点的路径代价和执行特定任务需要的不同代价，在族群任务规划过程中，目标函数为执行完所有任务的代价和最小。即：
f=min(f1+f2+…+fn)
(1)
式(1)中： f为目标函数表示完成任务的总代价和； fi表示第i个任务族完成任务的代价。
3 层级结构
针对复杂战场大规模无人机作战任务规划问题，提出了一种基于多Agent的分层任务规划方法。分层结构是将复杂问题整理简化的一种有效方法，按照解决复杂问题的流程，将具有相同功能或相似时间节点的问题处理模块放在相同层级，不同模块放到不同层级，层级之间相互区分又互相联通，这样有利于高效有序地解决如多无人机任务规划等复杂的工程实际问题。族群任务规划框架如图1所示。
按照无人机族群任务规划要求，如图1所示，规划方法分为4个层，包括输入层、族群任务规划层、族任务规划层和执行任务层。
图1 族群任务规划框架示意图
Fig.1 Framework of clustered group’s mission planning
3.1 输入层
输入层是无人机族群任务规划方法的第1层，主要实现对任务信息和资源信息的管理及预处理，作为下一层的数据输入。
输入层包括2种类型的Agent，分别是任务信息管理Agent和资源信息管理Agent。任务信息管理Agent负责实时接受信息部门分配的或者下级部门反馈的需要完成的任务，并将其处理为任务规划系统可读的标准任务形式。资源信息管理Agent负责管理族群内各类无人机的所有资源信息，为族群规划层提供所属无人机资源信息和剩余能力数据。资源信息管理Agent从族任务规划层中得到反馈信息，并随时更新各类无人机的资源信息。
3.2 族群任务规划层
族群任务规划层是族群任务规划的核心层，实时从输入层接收任务及资源信息，根据各类任务和无人机资源的对应关系，形成任务分配方案，将方案发送给族任务规划层，同时接收族任务规划层反馈的规划结果。
该层主要由族群任务规划Agent组成，族群任务规划Agent从任务信息管理Agent和资源信息管理Agent中得到任务信息和资源信息，根据任务所需资源来确定无人机资源和独立任务的映射关系，将所有任务适时地分配给对应的族任务规划Agent。
族群任务规划层具有整个任务的全局视野，在该方法中起着协调作用，其协调作用是将作战任务根据类型和时序要求分配到族任务规划层。
3.3 族任务规划层
第3层为族任务规划层，从上一层得到任务分配方案，各无人机族根据任务分配方案，结合所属无人机资源进行族任务规划，将规划结果发送给执行任务层，并反馈到输入层。
族任务规划层包含各类无人机族任务规划Agent，包括不同配置地域的侦察族，攻击族和中继族。
该层中，每个无人机族规划部门作为不同的Agent，接收从族群任务规划Agent分配的独立任务，完成族内任务分配和路径规划，并将规划方案发送给所属无人机，同时反馈到输入层。
3.4 执行任务层
第4层为执行任务层，各类无人机接收族任务规划层的规划方案，并按方案执行作战任务。将任务进程实时反馈给族任务规划层，以便出现特殊情况时，族任务规划层可以及时进行重规划。
执行任务层主要包含各种类型的任务无人机，由上层的族任务规划Agent管理和控制，各个任务无人机将自身的状态信息实时反馈给族任务规划Agent，从族任务规划Agent中接收任务规划方案，并根据各自接受的方案执行作战任务。
4 规划流程
无人机族群任务规划流程反映了各类无人机执行作战任务时的协同机制。规划流程包括3个步骤，分别为任务预处理、任务分配和任务规划。以无人机对目标进行攻击、侦察和中继等3种典型任务为例，建立如图2所示的规划流程。对目标先侦察再攻击以及对远距离目标侦察这2种任务模式，作为触发族群任务规划协同机制的输入。
图2 任务规划流程框图
Fig.2 Mission planning flow chart
4.1 任务预处理
各指挥决策机构以随机形式不断地下达作战任务到任务队列，任务信息管理Agent对任务进行预处理，并确定每个任务需要多少种类型的任务无人机，是否需要中继无人机。然后将处理后的结果发送到族群任务规划Agent，等待分配。
4.2 任务分配
族群任务规划Agent实时地与族任务规划Agent交换信息，并利用任务规划算法将各个独立任务按要求时序分配到各个族任务规划Agent。
在进行族群任务分配时需要考虑2个方面因素：第1是任务类型的区分，第2是各类任务间的关系。不同的任务类型很容易被分配到相应的任务族中，但是由于协同任务中的任务之间存在依赖关系，需要同时或者时序的被分配，因此族群任务规划Agent需要确定哪些任务已经准备好被分配，哪些任务已完成。当一个任务完成或者正在进行时，其他依赖于该任务的任务需要准备好被执行。族群任务规划Agent通过接受任务信息Agent以及各个族反馈来完成任务的信息，实时更新所有任务的状态，并适时时将任务分配给相应的任务族。
对于所有需要马上执行的任务，族群任务规划Agent通过2个阶段将任务最优地分配到相应的任务族Agent。
第1阶段，任务预处理阶段，主要是对族任务规划Agent和各个独立任务进行初始匹配，匹配操作为独立任务选择相应类型的族任务规划Agent。如果一个族任务规划Agent的任务类型符合任务要求，则认为该任务族可以与该任务匹配。
第2阶段，预处理完成后，使用以下方法将各独立任务按要求分配给对应的族任务规划Agent。
1) 计算每个任务族完成任务的代价。族群任务规划Agent根据各个无人机族的最新状态，使用改进的人工蜂群算法来计算完成当前任务的最小代价，改进人蜂群算法的流程如图3所示。
图3 算法流程框图
Fig.3 Flow chart algorithm
其具体步骤为：
步骤1：种群初始化。设置初始化参数，对初始蜜源编码，生成初始种群;
步骤2：改进雇佣蜂阶段。使用带概率的逆向算子、交叉算子操作对每个雇佣蜂进行邻域搜索，使用贪婪选择保留更好的解;
步骤3：选择产生跟随蜂。按轮盘赌方式选择较优种群作为跟随蜂种群;
步骤4：改进跟随蜂阶段。同雇佣蜂一样，使用带概率的逆向算子、交叉算子操作对每个跟随蜂进行邻域搜索，使用贪婪选择保留更好的解；
步骤5：判断是否产生侦察蜂。如果产生，对当前最佳蜜源实施变异算子操作进行全局搜索；
步骤6：判断是否满足终止条件。若满足则输出最优解，否则转至步骤2。
2) 将所需代价与任务族的剩余容量进行比较。如果剩余容量可以胜任完成任务所需，则将此任务族作为独立任务的候选族。
3) 将所有候选族的任务代价进行排序，选择代价最小的任务族作为执行任务的无人机族。
4.3 任务规划
族任务规划Agent从族群任务规划Agent接受任务后，根据所属无人机资源剩余情况，对所分配任务进行规划，得到各个无人机的执行任务方案。而后，族任务规划Agent将规划方案反馈给族群任务规划Agent，族群任务规划Agent对规划方案进行评估，并确定是否采用此方案，如果不采用，族任务规划Agent重新确定方案；如果采用，将告知各个族任务规划Agent，族任务规划Agent接到消息后将规划方案发送给任务无人机使其按方案执行作战任务。族群任务规划方法具有以下优点：首先，不同任务族的协同是通过族群任务规划Agent集中协调实现的；其次，各族任务规划Agent也可以直接接收相应独立任务；最后，各个族任务规划Agent之间也可以通过对话，增加抗扰性能。
5 仿真验证
仿真实验平台为Inter Core i5-7300HQ /8GB /64位Win10操作系统的惠普笔记本。编程工具为Matlab R2017b(64位)。
5.1 仿真参数设置
假设作战范围内有4个任务区域如图4所示，其中3个未知信息区域和1个已知信息区域，未知信息区域需要无人机进行覆盖侦察，如果其中存在需要攻击的目标，则使用攻击无人机进行攻击；已知信息区域已经侦察完毕，确定有数个目标需要攻击无人机进行目标攻击。对于远距离目标，由于目标和测控站距离超过了无人机的通信距离，需要中继无人机协同完成作战任务，则需要所有的任务机在执行任务过程中均通过中继机与测控站进行通信。
图4 任务区域示意图
Fig.4 Task area map
作战范围内不同位置预先配置了2个侦察无人机族、2个攻击无人机族以及1个中继无人机族，各个无人机族的相关信息如表1所示，其中蓝色多边形表示任务区域、红色点表示无人机对目标的攻击位置，使用所提族群综合任务规划方法对所有任务进行规划仿真。
表1 任务族无人机的配置信息
Table 1 configuration of mission cluster UAV
任务族类型位置容量备注(单架任务机)v1侦察(1 000,7 000)8有效覆盖面积7 km2v2侦察(8 000,1 000)8有效覆盖面积7 km2v3攻击(8 000,3 000)8载弹量:6枚v4攻击(1 000,6 000)8载弹量:6枚v5中继(6 000,2 000)8有效通信距离3 km
5.2 仿真内容及结果分析
在任务规划的预处理阶段，对同一时间所下达的任务进行分析整理可得，任务分为3种类型和2个时间段，分别是第1阶段对4个任务区域的中继无人机部署、对3个未知区域的覆盖侦察以及1个已知区域内目标的攻击；第2个阶段为对3个未知区域的中继无人机部署以及对第1阶段侦察到目标的攻击。
在任务规划的任务分配阶段，首先计算各族对所需执行攻击或侦察任务的任务成本，可以得出使用无人机族v1执行左边2个未知区域的覆盖侦察任务、无人机族v2执行右边1个区域的未知区域成本较小，使用无人机族v3执行已知区域的攻击任务成本较小，中继任务分配给无人机族v5。
在任务规划阶段，根据以上无人机任务族所收到的任务，各无人机族对侦察和攻击无人机进行任务分配、路径规划以及对中继无人机进行位置部署。
任务规划结果如下：
在第1阶段，中继无人机族v5部署中继无人机，使所有任务区域中无人机的待执行任务位置均在中继无人机的通信范围之内，每个中继无人机均可以直接或者通过其余中继无人机与测控站进行通信，保证所有任务机在执行任务过程中均可以通过中继无人机与测控站进行通信。无人机部署位置如图5所示，其中红色的点表示无人机的攻击位置、黑色星表示测控站位置、蓝色小圈表示中继无人机部署位置、绿色大圈表示中继无人机通信范围。同时，使用侦察无人机族v1、v2对信息未知的3个区域进行覆盖侦察，使用攻击无人机族v3对信息已知的一个区域内的所有目标进行攻击，规划结果如图6所示，其中红色的细线表示无人机的飞行路径、黑色星字表示无人机族v1、v2、v3的地面站位置，区域内部蓝色粗线表示侦察无人机的区域分界线。
图5 中继无人机部署位置示意图
Fig.5 Relay UAV deployment location
图6 侦察族和攻击族无人机的任务路径示意图
Fig.6 Mission paths of reconnaissance and attack UAVs
在第2阶段，上一阶段任务完成以后，首先调整中继无人机族v5中无人机位置，对第1阶段侦察得到详细信息的3个区域进行中继通信全覆盖，使得攻击无人机族在执行攻击任务时，均在中继无人机通信范围内，能实时有效地通过中继无人机与测控站进行通信，调整后位置如图7所示，其中蓝色小圆表示中继无人机部署位置、绿色大圆表示每个中继无人机的通信范围。同时，攻击无人机族v3、v4对3个待攻击区域的所有目标进行攻击，其任务分配及路径规划结果如图8所示。
图7 中继无人机调整后位置示意图
Fig.7 Adjusted position of relay UAV
图8 攻击无人机攻击路径示意图
Fig.8 Attack UAV attack path
仿真结果分析如下：
1) 务分配方法将各类型的任务准确的分配给了各个无人机族，使各无人机族按正确的阶段去执行相应类型的任务，说明了族群分配方法的有效性。
2) 人机族根据现有算法，对所需执行任务进行任务规划，规划相应的任务路径，说明了各个任务族规划方法的有效性。
3) 划方法将实时下达的任务按照各类型任务之间的依赖关系，有序分配给相应的任务族，而后由各任务族规划任务执行方案，可以有效解决较大规模无人机实时任务规划问题，说明了族群综合任务规划方法的有效性。
6 结论
1) 根据战场任务需要，将各类型配置地域相同的任务无人机作为无人机族统一规划调度，既满足了各种复杂任务之间的协同需要，又减少了现有规划方法的复杂度。
2) 采用分层结构和多Agent形式进行任务规划，每个Agent各司其职且相互联通，各层级之间有序协调，使任务规划方案达到既并行又串行的效果，节省了规划时间又满足了协同需要。
3) 为大规模陆战场无人作战任务规划提出了研究方向。
[1] Ruiz J J，Martinez-De-Dios J R，Cobano J A， et al.A multi-payload simulator for cooperative UAS missions[C]//Proc.of the 2016 International Conference on Unmanned Aircraft Systems (ICUAS),2016:1192-1199.
[2] Kim D Y,Lee J W.Joint mission assignment and topology management in the mission-critical FANET[J].IEEE Internet of Things Journal,2020,7(03):2368-2385.
[3] Nuri O,Ayan U,Oztop E.Cooperative multi-task assignment for heterogonous UAVs[C]//Proc.of the international conference on advanced robotics,2015:599-604.
[4] Fu X W,Feng P,Li B,et al.A two-layer task assignment algorithm for UAV swarm based on feature weight clustering[J].International Journal of Aerospace Engineering,2019(5):1-12.
[5] Baham C,Calderon A,Hirschheim R.Applying a layered framework to disaster recovery[J].Communications of the Association for Information Systems,2017,40(01)277-293.
[6] Maza L,McMillan C.Adaptive multi-agent path planning for distributed UAV systems[R].CS229 Autumn 2017 Final Project Category:Theory & Reinforcement Learning.2017.
[7] Miloradovic B，Ürüklü B，Ekstrm M，et al.A genetic algorithm approach to multi-agent mission planning problems[C]//Proc.of the International Conference on Operations Research and Enterprise Systems,2019:109-134.
[8] Dorri A,Kanhere S S,Jurdak R.Multi-agent systems:A survey[J].IEEE Access 2018,6:28573-28593.
[9] Rastgoftar H,Atkins E M.Safe multi-cluster UAV continuum deformation coordination[J].Aerospace Science and Technology,2019,91:640-655.