基于DTC和遗传算法的无人机-无人车任务规划方法

陶灿灿，韩 旭，周 锐

(1.北京航空航天大学 自动化科学与电气工程学院,北京 100191；2.中国航空工业总公司成都飞机设计研究所，四川 成都 610091)

0 引言

利用无人机/无人车等异构多机器人的功能互补性，组成跨域协作系统，实现任务协同和信息共享，能够弥补单一军种作战力量的不足，进而创造出单一领域行动无法达成的效果[1-2]。

任务规划是无人作战的顶层规划，应根据任务环境态势、任务需求、自身特性等进行综合调度。文献[3]考虑时间窗、速度及能量共享，提出一种多准则混合整数规划模型，以最小化旅行距离、旅行时间和能源消耗为目标进行多机器人任务规划；文献[4]考虑平台能力、任务特点及环境约束，提出了一种基于市场的异构空地机器人任务分配算法，目标是最小化团队执行救援任务的总时间；文献[5]针对城市环境中持续监测任务，提出了一种估计分布算法和遗传算法相结合的混合算法，用于无人机-无人车协同路径规划。

本文研究智能任务规划技术助力无人作战飞机(Uninhabited Combat Aerial Vehicle,UCAV)/无人战车(Uninhabited Combat Ground Vehicle,UCGV)进行无人作战的可能性[6]。考虑到UCAV/UCGV协同任务规划扩展性，引入任务分析和环境建模仿真(Task Analysis Environment Modeling and Simulation,TAEMS)模型语言来描述UCAV/UCGV的任务结构，基于DTC方法设计任务规划的目标函数，并利用基于精英机制的遗传算法求解UCAV/UCGV任务规划问题的解。在任务规划过程中集成了路径规划[7]，规划的结果是包含任务参数信息如位置、时间、累加收益、累加路径的动作序列。

1 任务规划模型

1.1 协同任务想定

以协同攻击任务为例，无人机/无人车执行攻击任务的目的是在作战初期派UCAV和UCGV进入敌方战区，利用异构平台作战能力的差异性和互补性，UCAV和UCGV根据战场信息分别对不同的敌方火力部署进行摧毁，从而获得更大的作战效益，并减小后期有人部队对该区域进行搜索、轰炸的危险性，提升整个战场的作战效果[8]。

图 1为UCAV/UCGV协同执行攻击任务的示意图，战场环境中存在敌方各类武器威胁，如雷达、装甲车、炮、直升机、单兵等，图中以“+”表示，周围的圆表示威胁覆盖的区域；存在不同的环境威胁区域，如电磁区、恶劣气候区等，图中以阴影区域表示；存在不同的地形威胁区域(主要针对UCGV)，根据通过的难易程度分为避免通过区和不可通过区，图中以不规则四边形区域表示，不可通过区可以是难以通过的坑洼、断崖、河流、湖泊等[9]。

图1 UCAV/UCGV协同攻击任务想定Fig.1 UCAV/UCGV collaborative attack mission scenario

1.2 任务结构模型

TAEMS是一种通用的Agent任务结构描述语言，实质上是分层的有向图[10]，以无人机/无人车协同执行攻击任务为例，其对应的基于TAEMS描述的任务结构如图 2所示。图中的任务结构包含3类节点[11-12]：任务群、任务和动作。任务群节点是TAEMS框架中最高层的任务节点，是没有父节点的任务节点；任务节点本身可以递阶地分解为更低层次的子任务，并通过品质累积函数定义各子节点的合成方式，在图中圆角矩形表示任务；动作节点是TAEMS任务树型结构的叶节点，它没有子节点，动作表示可以由Agent直接执行的，不能再分解的任务，在图中用矩形表示动作。

图2 基于TAEMS模型的UCAV/UCGV任务结构Fig.2 UCAV/UCGV mission structure based on TAEMS model

1.3 相互关系及品质累积函数

TAEMS任务结构模型定义了任务的效用信息(如收益、代价、持续时间、持续路程等)和子任务间的相互关系，在图 2中带矩形标签的有向线表示相互关系。常用到的相互关系有[13-14]：

(1)

式中，Ta,Tb表示任务或方法节点；{Task}表示任务节点集合，{Method}表示方法节点集合；使能关系enable(Ta,Tb)表示只有关系的源节点完成后，目标节点才允许被执行和生效；使不能关系disable(Ta,Tb)，表示只有在关系源节点未执行时，目标节点才可执行和生效；促进关系facilitate(Ta,Tb)表示源节点对目标节点的执行效果具有有利影响；阻碍关系hinder(Ta,Tb)表示源节点对目标节点的执行效果具有不利影响。

品质累积函数 (Quality Accumulate Function,QAF)定义了如何由各子节点的品质获取节点自身的品质。常用的QAF有[13,15]：

(2)

式中，{T1,T2,…,Tm}是子节点集合，m表示子节点的个数，q_min表示任务节点的品质为其所有子节点中最小的品质值；q_max表示节点品质等于其子节点中最大的品质值；q_sum表示父节点的品质值等于其所有子节点品质值之和；q_exactly_one表示完成父节点可以通过执行其任何一个子节点，父节点的品质值为所执行的子节点的品质值。

2 任务规划问题描述

2.1 动作

动作是UCAV/UCGV可以直接执行的原始任务，形式化描述为[1,11]：

IA=

estimate_time,certainty,val,

location,attachPara,interrelations>,

(3)

式中，id为动作的编号，label为动作的名称，Agent为动作所属的智能体，threatcost为执行该动作需要付出的威胁代价，estimate_time为完成动作的预计时间，certainty为动作存在概率，val为完成动作后获得的回报，location为完成动作所在的位置，attachPara为和具体任务相关的附加参数，其形式和内容是由具体的任务决定的，interrelations为和动作关联的关系集合，IA为InputAction缩写。

2.2 动作集合

动作集合是UCAV/UCGV任务结构分解出来的无序动作集合，即

IAS={IA1,IA2,…,IAn}，

(4)

式中，IAS为InputActionSet的缩写，IAi表示任务结构分解出来的无序动作集合中第i个具体的动作。

2.3 解动作

解动作是UCAV/UCGV任务规划求解出来的某个具体动作，形式化描述为[11,13]：

OA=

estimate_time,certainty,val,

location,attachPara,

interrelations,ac_threatcost,

ac_estimate_time,ac_val,ac_dis>，

(5)

式中，ac_threatcost为完成该动作后的累加威胁代价，ac_estimate_time为完成该动作后的累加预计时间，ac_val为完成该动作后的累加效果，ac_dis为完成该动作后的累加距离，OA为OutputAction缩写，其他参数意义和输入动作相同。

2.4 解序列

解序列是求解出来的UCAV/UCGV可以直接执行的动作序列，为解动作的有序集合，即

OAS={OA1,OA2,…,OAm}，

(6)

式中，OAS为OutputActionSequence的缩写。

2.5 约束

UCAV/UCGV进行任务规划时需要满足一定的约束条件，这些约束可以是任务规划初始时设置的，也可以是战场环境中突发的任务约束，约束形式化表示为[1，14]：

constraint=

certainty,distance,threat,…>,

(7)

式中，label为约束标识,Agent为受约束的Agent,task为约束对应的任务,time表示任务的预计时间约束,certainty表示目标存在概率的确定性约束,distance表示任务的总路程约束(即燃油约束),threat表示任务受到的威胁障碍约束。

2.6 相互关系

UCAV/UCGV任务结构中的相互关系可形式化描述为[1,15]：

interrelation=

fromOutcome,delay,effect,active>,

(8)

式中，label为关系名称,Agent为此相互关系所在的任务结构所属的Agent,type为相互关系的类型,from为关系源节点,to为关系的目标节点,fromOutcome为关系源节点的输出,delaty表示关系生效需要延迟的时间,effect为关系作用对目标节点的影响,active指示相互关系是否生效。

根据以上各元素的描述，可给出如下定义：

定义[UCAV/UCGV任务规划问题]UCAV/UCGV任务规划问题可形式化描述为一个映射：

LS(TaskTree,constraint,interrelations,IAS)→OAS,

(9)

式中,TaskTree为任务和动作节点构成的树形结构，即UCAV/UCGV的TAEMS任务结构,constraint为任务规划的约束集合,interrelations为节点间相互关系集合,IAS为UCAV/UCGV任务结构分解出来的无序动作节点集合,OAS={OA1,OA2,…,OAm}为求解出来的动作序列集合。

UCAV/UCGV任务规划问题定义为给定任务目标，如何求取实现此任务目标并满足约束条件的动作序列，同时确定各动作的相关参数。

3 规划求解方法

3.1 DTC标准设计准则

DTC方法提出重要度权重的概念，指示集合中每一个因素的相对重要程度，用百分比表示。权重概念可以表示为“收益因素重要性是代价因素的两倍，而时间不是问题”“收益和时间同等重要，代价不是问题”等需求[16]。

由权重集合可以定义用户设计准则，而怎样利用这些准则生成满足期望的结果是剩下的问题。在使用某个具体算法求解任务规划问题时，搜索的每一步都要利用基于DTC方法设计的用户目标函数去评价一个动作节点“好”的程度[17]，用权重组对动作节点进行标定。本节在考虑收益、代价、持续时间、持续路程4个属性因素的基础上，介绍两个权重组，每组权重值之和为100%。

原始效果(Raw Goodness)权重组[1]：这组权重包括收益、代价、持续时间、持续路程的权重，表示不同因素的相对重要程度。例如，将收益权重设为50%，代价权重和时间权重分别设为25%，表示收益的重要程度是代价和时间的两倍，而不考虑受燃油约束的持续路程。

求原始效果的标定分量需要先计收益、代价、持续时间、持续路程四维子分量值，步骤为：

(10)

(11)

(12)

(13)

式中，maxp、maxd、maxt、maxc和minp、mind、mint、minc分别为要标定的动作序列的收益、持续路程、持续时间和代价的最大值和最小值；this.ep、this.ed、this.et、this.ec表示动作序列的预计收益、持续路程、持续时间和代价；RG_sliderp、RG_sliderd、RG_slidert、RG_sliderc是原始效果权重组中各分量的权重值。

原始效果分量等于四维子分量之和：

componentRG=componentp+componentd+

componentt+componentc。

(14)

上下限(Thresholds/Limits)权重组[1]：此组权重包含收益超过预计下限的重要度权重，代价、持续时间和持续路程低于某个上限的重要度权重。此权重组的意义表明代价、时间和路程满足一定约束条件，收益值达到一定阀值的动作具有特殊的价值[1]。

上下限分量的求解同样需要计算四维子分量，如式(15)～(18)所示，其中Thresholdp、Limitd、Limitt和Limitc为最小收益要求、最大距离限制、最大时间限制和最大代价限制，TL_sliderp、TL_sliderd、TL_slidert和TL_sliderc是各分量的权重值。同样，上下限分量为各子分量之和。

(15)

(16)

(17)

(18)

componentTL=componentp+componentd+componentt+

componentc。

(19)

3.2 基于精英机制的遗传算法求解

遗传算法是一类常用于求解优化问题的进化算法[18]，它将优化问题的寻优过程转化为对染色体种群的进化过程，进化完成的种群中适应度最高的染色体就是优化问题的解。还可以根据具体问题制定进化的策略以及限定条件等，从而加快进化的过程，提高问题的求解速度。

以无人机/无人车协同攻击n个目标为例，种群中染色体的编码可以表示为[19]：

(20)

式中，i,j,…,k代表某个攻击目标由谁执行，0代表不被执行，1代表被无人机执行，2代表被无人车执行，n代表目标的个数。

适应度表明单个染色体或解的优劣性，以无人机/无人车协同攻击n个目标获取最大攻击收益为例，适应度函数可以定义为[19]：

(21)

式中，attaVali代表攻击第i个目标后获得的收益，n代表目标的个数。

选择操作从旧的染色体种群中以一定概率选择个体到新群体中，本文使用轮盘赌方法选择，个体被选择的概率跟适应度值有关，个体适应度值越大，被选中的概率越大，计算过程为[20]：

(22)

式中，Fi为第i个父本对应的适应度值，Pi为第i个父本被选择的概率。

交叉操作通过组合父辈个体的特性得到新一代的个体，以协同攻击n个目标为例，将父代样本两两分组，每组中的两个染色体互相交换部分基因；变异操作从群体中选择若干个体，对于选中的个体以一定的概率随机地改变染色体中基因的值[20]。

为了加快种群进化的速度，对遗传算法进行改进，引入精英策略，将父代种群中染色体适应度最高的10条染色体直接复制到下一代种群中，从而保证子代种群中的最优个体不会比父代最优的个体差。

基于DTC和遗传算法的任务规划流程如图3所示。

图3 基于DTC和遗传算法的UCAV/UCGV任务规划流程Fig.3 Flowchart of UCAV/UCGV mission planning based on DTC and genetic algorithm

4 仿真实例

4.1 问题和参数

以协同攻击任务为例，UCAV/UCGV从进入战区点开始，根据任务需求和任务约束对区域内的敌方目标实施攻击，攻击任务完成后从退出战区点返回我方基地。根据先验信息，将战场上的攻击目标分为3类：无人机优先目标、无人车优先目标、普通目标。例如目标所处环境地形不适合无人车通过，可将此目标设为无人机优先目标。战场存在雷达、武器等威胁，在任务规划之前可以结合路径规划给出相关任务参数，规定了攻击目标类型和关键的战术点，设置的任务参数如表 1所示。

表1 任务参数Tab.1 Mission parameters

4.2 仿真实验1

设定遗传算法的选择概率Ps=0.9，交叉概率Pc=0.8，变异概率Pm=0.05，精英机制保留染色体数目为10，初始种群数为100，最大进化代数为200。

根据任务参数，求解在累加任务威胁threatconstraint=200约束下获取最大的攻击收益、侦察路径尽量短，得到UCAV任务完成效果如表 2所示，UCGV任务完成效果如表 3所示，UCAV动作序列时间表如图 4所示，UCGV动作序列时间表如图5所示，UCAV/UCGV各自执行任务的路径如图6所示，适应度函数进化过程如图7所示。

表2 UCAV攻击任务完成效果数据Tab.2 UCAV data for completing attack mission

表3 UCGV攻击任务完成效果数据Tab.3 UCGV data for completing attack mission

图4 UCAV执行攻击任务的动作序列Fig.4 UCAV action schedule for attack mission

图5 UCGV执行攻击任务的动作序列Fig.5 UCGV action schedule for attack mission

图6 UCAV/UCGV执行攻击任务的路径示意图Fig.6 UCAV/UCGV route diagram for attack mission

图7 适应度进化过程(累加威胁受约束)Fig.7 Evolution process diagram of fitness (accumulated threat constrained)

从适应度曲线图可知，随着种群的迭代进化，系统整体的任务收益逐渐增大，最后获得最优值并趋于稳定；从任务完成效果数据表和各自执行任务的动作序列图看出，本文所提出的方法能够在考虑无人机和无人车能力差异性的基础上，将不同的子任务调度给不同的Agent执行，且规划调度的过程中融合了各项任务信息；从执行任务的路径示意图看出，所提方法能够在最大化系统整体任务收益的同时，兼顾路程长度因素。

4.3 仿真实验2

为了比较，求解和上述实验条件相同，但累加威胁不受约束的UCAV/UCGV协同攻击任务的动作序列，得到UCAV/UCGV各自执行任务的路径如图8所示，适应度函数进化过程如图9所示，任务完成效果表和动作序列时间表与上述实验相似，此处不再列举。

图8 UCAV/UCGV执行攻击任务的路径示意图Fig.8 UCAV/UCGV route diagram for attack mission

图9 适应度进化过程(累加威胁不受约束)Fig.9 Evolution process diagram of fitness(accumulated threat not constrained)

从适应度曲线图看出，由于本次实验相比上个实验条件约束更少，可以对雷达和导弹威胁区域内的目标进行攻击，系统整体的任务收益比上个实验有所提高；从执行任务的路径示意图看出，本文所提方法能够根据子任务的属性和周边环境因素以及对系统整体任务目标的作用，将相应子任务规划给对应的Agent执行；结合本文的两个仿真案例，验证了本文所提方法在满足不同作战任务需求、考虑无人机和无人车能力差异的基础上规划不同子任务给相应Agent执行以及融合任务多项信息方面的有效性，从而使无人机和无人车系统的整体作战效益最大。

5 结束语

采用TAEMS语言描述UCAV/UCGV任务结构，对任务的递阶分解及相互关系进行了明确表述和建模，建立的模型可扩展到更多数量的无人机/无人车协同作战问题上。

提出了一种基于标准设计准则和遗传算法相结合的任务规划方法；基于DTC方法设计基于用户目标准则的效益函数来控制优化的过程；引入具有精英机制的遗传算法来求解UCAV/UCGV任务规划问题；并在任务规划过程中集成路径规划，规划的结果是包含任务参数信息如位置、时间、累加收益、累加路径的动作序列；仿真表明本文算法具有很高的鲁棒性和自适应性，契合未来战争高复杂性的发展趋势。