摘要,采用蚁群算法对无人机协同多任务分配问题(CMTAP)进行研究。在通用CMTAP模型的基础上,综合考虑包括动态任务时间约束和无人机任务能力的差别多类复杂约束条件,建立扩展的协同多任务分配模型。在多子群蚁群算法的基础上,提出了基于分工机制的蚁群算法对CMTAP进行求解。根据协同多任务分配的特点,设计了基于任务能力评估的问题解构造策略和基于任务代价的状态转移规则,提高了算法的性能。仿真实验结果表明该方法能有效地解决无人机协同多任务分配问题。
关键词,无人机,协同多任务分配问题,动态时间窗,分工机制,多子群蚁群算法
无人机协同多任务分配问题(CooperativeMulti-TaskAssignmentProblem,CMTAP)[1]的目标是在执行任务无人机集合性能允许的范围内,针对不同用户提出的多任务需求,确定出各无人机的任务执行序列,包括目标集合、执行任务的类型以及不同任务的执行顺序和时间等,以确保多无人机在多任务执行过程中的协同性。研究高效率协同多任务分配方法是提升无人机未来战场适应能力和作战效能的重要途径,具有较大的理论和实际意义。现阶段,国内外关于无人机任务分配问题的研究成果主要包括任务分配问题建模和任务分配求解算法两方面。
在任务分配问题建模方面,现阶段的研究成果主要包括多旅行商问题(MutipleTravelingSa-
lesmanProblem,MTSP)模型[2]、车辆路径问题(VehicleRoutingProblem,VRP)模型[3]、混合整数线性规划(MixedIntegerLinearProgramming,MILP)模型[4]等。美国空军研究实验室在无人机任务分配研究中建立了带时间窗的不同能力约束车辆路径问题(CapacitatedVehicleRoutingPro-blemwithTimeWindows,CVRPTW)模型,并将其应用于“全球鹰”无人机和“捕食者”无人机的侦察任务规划问题建模[5-7]。随着无人机能力不断增强,无人机执行任务的复杂程度也随之增强,不同任务之间存在着复杂的时序以及时间约束。对于这一类复杂的任务集合,目前大多数任务分配模型无法对其进行有效的描述。针对这一不足,文献[1]提出了一种CMTAP通用模型,该模型能对无人机执行复杂作战任务时任务间的时序约束关系进行有效建模。
在任务分配求解算法方面,目前的研究成果主要有A*算法、遗传算法(GA)和基于合同网(ContractNet)的方法[8-9]等。A*算法作为传统优化方法的典型代表,其优化目标是获取问题最优解,且具有完备性和可纳性,但A*算法作为一种确定性算法,在求解大规模组合优化问题时存在时间、空间复杂性较大的不足,随着问题规模的增大,其求解难度也急剧增加,遗传算法作为进化类算法的典型代表,近年来在无人机任务分配问题领域得到了广泛应用[1],但遗传算法由于其本质上的随机性,求解过程中存在较多劣质搜索过程,导致其在大规模组合优化问题的求解中效率和精度不高,基于合同网的方法将任务分配看做一个交易过程,将增加或降低的任务计划评估值作为无人机之间任务分配的控制变量,通过无人机的互相协商和任务竞争,在局部最优的基础上追求全局最优,但由于基于合同网方法的优化能力建立在不同无人机之间协商和竞争的基础上,当任务分配问题规模较大时,会导致无人机之间协商通信量大大增加,降低问题求解效率。
蚁群算法(AntColonyAlgorithm,ACA)于1991年由意大利学者Dorigo提出,此后该方法被应用于各类组合优化问题求解中,并取得了一系列的研究成果。蚁群算法通过对自然界中真实蚁群觅食机制的模拟,将搜索问题中的启发信息表达到蚁群的信息素释放/挥发机制中,通过在搜索过程中引入正反馈机制,大大提高了算法的收敛速度。
本文在CMTAP通用问题模型基础上,综合考虑多类复杂约束条件进行扩展,对无人机协同多任务分配问题进行描述。在多子群蚁群算法基础上,设计了基于分工机制的蚁群算法对问题进行求解,通过对蚁群算法问题解构造策略及状态转移规则的改进和设计,使得算法性能得到明显提高。
在通用CMTAP模型[1]中,约束条件主要包括任务时序约束、任务时间约束、多机协同约束。
定义2(任务时间约束) 如果某个任务必须在指定的时间范围内完成,则称该任务具有时间约束。在无人机协同多任务分配问题中,时间约束通常对具有机动能力的动态目标存在。任务时间约束可表达为
ET LT i i ≤ (3)式中, ETi和LTi分别为执行第i个任务的最早时间限制和最晚时间限制, i为该任务的执行时间。
定义3 (多机协同约束) 除非在预先的任务需求中对某个特定目标指定了多次任务或者该任务没能顺利完成,否则,任务集合中任何一个任务只能被无人机集合完成一次。设 , {0,1}j ∈ 为决策变量,当无人机i被分配执行任务 j时,,j 取值为1,否则其值取0,则多机协同约束可以表达为
在上述通用模型约束条件的基础上,结合无人机实际作战使用过程中的特点,无人机协同多任务分配问题还应考虑动态任务时间约束和无人
定义4 (动态任务时间约束) 无人机执行任务的时间约束经常是建立在任务的时序约束的基础上。设任务 i的前续任务的执行时间为(Prev( )) M ,则任务时间约束可以表达为
定义5 (无人机任务类型能力约束) 在无人机协同多任务分配问题中,单架无人机所能完成的任务类型是有限的,故特定无人机只能执行任务集合中与自身能力相符合的任务,超出自身能力范围的任务必须交由其他无人机执行。设无人机i所能执行的任务类型为MissionKind( ) ,则若无人机i能够执行任务 j必须满足如下的类型能力约束
无人机协同多任务分配问题中,任务分配计划的优劣程度可采用无人机集合完成该计划中所有任务所需的总飞行航程和计划中包含的任务数量两种指标进行评价。
设(Proj ect ) 为无人机i任务分配计划的飞行航程值, max( ) V为i的最大航程限制,则无人机集合任务分配计划的总飞行航程指标为
式中, (Project ) 为无人机i完成其任务分配计划所需的时间(由起点出发直至到达预定终点所经历的时间), i为无人机i的飞行速度,本文提出的模型中假设该值为一常量。无人机协同多任
务分配的目标是在满足2.1节中诸多约束条件的前提下制定合理的任务分配计划,且使得该分配计划的总飞行航程指标1最小化。
无人机集合任务分配计划中包含的任务数量反映了任务分配对待执行任务集合的覆盖程度,其计算方法为
在该评价指标下,无人机协同多任务分配的目标是在满足协同多任务分配问题诸多约束条件的前提下,使得完成任务数量指标2最大化。在实际指标应用中,为了与任务总飞行航程代价的最小化目标相对应,通常将该指标转化为未完成任务数量指标,以实现无人机集合未完成任务数量最小化为目标,即
综上所述,可以得到无人机集合任务分配计划的综合评价指标为总飞行航程代价指标与未完成任务数量指标之和,协同多任务分配的目标即实现该综合指标的最小化,即
基于上一节建立的问题模型,本文在多子群蚁群算法基础上,将蚁群社会中蚂蚁之间的分工合作机制引入问题求解过程中,针对协同多任务分配问题特点,对分工机制蚁群建立、 问题解构造策略、人工蚂蚁状态转移规则进行改进和设计,提出了基于分工机制的蚁群算法。
在无人机协同多任务分配问题中,不同无人机执行的任务各不相同,由此可将各无人机映射为人工蚁群中不同的蚂蚁子群,各蚂蚁子群为其对应的无人机构造任务分配计划,相互之间通过基于信息素分布的间接信息交互实现任务的协同。
基于分工机制的协同多任务分配蚁群算法中,分工机制蚁群的建立以不同无人机执行任务的不同为基础。设人工蚁群为AC {AC( 1) i =AC, , } ,其中, AC 为人工蚁群中包含的蚂蚁子群数,满足 AC V N , ,C {Ant ( 1) ik k =2, , } 为对应于无人机i的蚂蚁子群,且不同
,nti j为第i个子群中第j个人工蚂蚁,蚂蚁子群ACi中每个人工蚂蚁为无人机i构造任务分配计划,而无人机集合V的任务分配计划需要来自不同蚂蚁子群的 V个人工蚂蚁构造的任务序列构成。构造无人机集合V的一个满足各类约束的任务分配计划的 V个人工蚂蚁,称为人工蚂蚁簇AG( 1)2, ( i m ) , AGi是人工蚁群中构造无人机集合完整任务分配计划的最小蚂蚁群落,且不同的人工蚂蚁簇之间满足
综上所述,分工机制蚁群可由如图1所示的蚂蚁矩阵 , VC=[Ant ]( 1)2, , ( 1)2, ,j i N j m = , 进行描述。其中,蚂蚁子群对应于矩阵的各个行,人工蚂蚁簇对应于矩阵的各个列。如图1所示。
基于分工机制蚁群算法对协同多任务分配问题的求解过程中,构造无人机集合任务分配计划的基本群落是人工蚂蚁簇。人工蚂蚁簇AGl ( 1(2) , ) m , 在构造无人机集合V的任务分配计划的过程中, 每次选择一个人工蚂蚁, Vnt ( 1(2) , ) l i N , 进行状态转移,确定其后续执行的任务,该人工蚂蚁的选择应根据人工蚂蚁簇中所有蚂蚁个体任务能力评估的大小决定,任
务能力较大的人工蚂蚁被选中进行状态转移以选择将要执行的任务的概率较大,反之则被选中的概率较小,具体可以表达示为
相关研究表明,局部优化策略的引入能够较大程度地提升蚁群算法搜索效率。 因此,本文算法在问题解构造过程中还引入了逆转变异算子(2-opt局部优化)[10]对任务分配计划进行局部优化。逆转变异算子可由图2描述。
当人工蚂蚁簇中所有蚂蚁个体完成任务分配子计划构造之后,对所有子计划运用逆转变异算子进行局部优化,调整变异后任务分配计划中各任务的执行顺序和时间。当所得的计划满足协同多任务分配问题约束条件,且优于原计划时,以变异后的任务分配计划替换原计划。
蚁群算法中人工蚂蚁按照环境中的信息素分布和启发信息进行其状态转移,启发信息由候选的解元素的评价值决定。在求解无人机协同多任务分配问题的蚁群算法中的状态转移是指无人机执行当前任务之后向下一个任务的转移,因而人工蚂蚁可以获得启发信息为无人机由当前任务向下一任务转移所要花费的代价。 由此可以得到蚁群中各人工蚂蚁按照下式进行状态转移,
综合上述设计及基本蚁群算法的步骤,基于分工机制的无人机协同多任务分配蚁群算法如下所示,
输入, 系统参数 global local 0 , , ,qβρ ρ (其中global local ρ 为蚁群系统信息素更新的全局挥发系数和局部挥发系数),无人机集合V, 目标集合T,任务类型集合Mt。
步骤1 初始化规模为 V m 的分工蚁群AC,建立人工蚂蚁子群 VC( 1)2, ( u N ) 和人工蚂蚁簇 ( 1)2, (G v m ) 。设置任务分配蚁群算法初始迭代计数器 0← 和最大允许的迭代次数m ax 。
(16),式(20)所示的状态转移规则构造各自对应的无人机u的任务分配子计划。
(2) 当AGv中所有蚂蚁个体 ,nt ( v u =V(2) , ) 均构造完任务分配计划Projectu之后,对其中所有蚂蚁个体的任务分配子计划运用逆转变异算子进行局部优化。根据局部优化结果对AGv形成的任务分配计划Progect按照蚁群系统的局部信息素更新规则[11-12]进行局部信息素更新。
步骤3 按照蚁群系统的全局信息素更新规则[11-12]进行全局信息素更新。
步骤4 选择当前迭代中最优人工蚂蚁簇构造的任务分配计划与全局最优任务分配计划进行比较。如果优于当前的全局最优任务分配计划,则以当前迭代最优任务分配计划作为新的全局最优任务分配计划,否则继续后续步骤。
步骤5 1 c+ ,如果 max c ,则算法结束,输出当前的全局最优任务分配计划,否则转步骤2继续执行。
4(a)和图4(b)分别为各无人机的子计划飞行航程指标和总任务分配计划航程指标的收敛曲线。可以看出,各无人机的任务分配子计划的航程指标在迭代过程中存在大小变化过程,但总航程指标却迅速减小。 图4(c)和图4(d)分别为各无人机任务分配子计划的完成任务数指标和总任务分配计PG电子官方平台
