基于层次任务网络的作战任务-系统功能映射方法

易 侃, 张杰勇, 焦志强, 王 哲

(1. 中国电子科技集团公司第二十八研究所信息系统工程重点实验室, 江苏 南京 210007; 2. 空军工程大学信息与导航学院, 陕西 西安 710077; 3. 中国人民解放军第95910部队,甘肃 酒泉 735018; 4. 国防科技大学信息通信学院, 陕西 西安 710106)

0 引 言

军事信息系统作为作战要素的黏合剂,在信息化战场上发挥着十分重要的作用。随着军事技术的不断发展,武器装备的性能在不断提高。同时,战场环境也日趋复杂,作战任务的多样性和不确定性给军事信息系统带来了巨大的挑战。因此,如何面向任务构建军事信息系统受到了众多学者和研究机构的广泛关注[1-2]。

从问题本质上看,面向任务构建军事信息系统就是要实现任务需求到系统资源的映射,而系统能力/功能即是连接任务和资源的纽带。一方面,系统能力/功能为任务的执行提供直接支撑;另一方面,系统能力/功能是通过系统资源实现的。因此,实现任务到系统功能的映射是面向任务构建军事信息系统的关键。

目前,在工程上一般采用模板匹配的方法处理作战任务-系统功能映射问题,即先根据专家及作战人员的经验设计好所有可能的作战任务-系统功能映射模板(需要从任务直接映射到原子级系统功能)并形成模板库,在使用时根据需求在模板库中进行匹配查找[3-4]。显然,这种方法前期投入的人力和时间成本很大,且后期仍需投入较大的成本对模板库进行维护,不利于军事信息系统面向任务的快速生成与敏捷演化。

针对上述情况,部分学者开始研究自动映射方法。从映射方式来看,目前的研究可分为两类:集中式[5]与分布式[6]。集中式的映射要在给定抽象功能流程的基础上,确定各节点选取的功能实例。因此,主要包含了检索[7-8]和选择[9-10]两个步骤,即先根据给定的抽象需求对功能进行检索,然后在被检索到的多个功能中选择当前最优的功能实例。而分布式的映射则从抽象流程构建的角度出发,以功能间的依赖关系为基础,针对任务需求、通过规划方法得到映射方案。由于分布式的映射不需要直接提供抽象流程,因而其具有更高的自动化程度。针对分布式的映射问题,一般可以采用智能规划方法[11-12]进行求解。文献[11]通过对状态的预先排序,提出了基于有序爬山法的前向启发式搜索规划方法,提高了前向规划器的规划效率。文献[12]则基于宏操作的概念,提出了一种具有学习策略的规划方案,有效增强了规划器在特定规划领域的规划效果。

然而,当功能实例数量过多或规划链路过长时,前向规划的时间将会迅速增加,不利于快速得到规划方案。层次任务网络(hierarchical task network, HTN)方法[13-15]是一种作用在领域空间内的智能规划方法,通过领域内定义的方法将任务进行分解,直至达到不可分解的原子操作,从而得到规划解,在规划时间上具有独特优势。由于在作战任务-系统功能映射问题中,任务和功能都具备可分解的特性,本文考虑利用HTN规划方法实现作战任务到系统功能的高效映射。通过设计基于递归思想的任务分解算法以及基于邻接矩阵的多方案整合算法,使得HTN方法能够适应多属性输入的情况,从而得到了满足任务需求的系统功能映射方案。

1 问题描述

系统能力是系统为了完成任务所必需具备的一些属性,系统能力可以根据任务和系统状态进行分解。在分解得到的子能力中,不可再分解或者可以由系统直接实现的能力被称作功能。作战任务-系统功能映射过程关注完成某项作战任务时系统所需具备的能力/功能,是生成军事信息系统构建方案的基础。下面对作战任务和系统功能作如下定义。

作战任务可以表示为一个五元组Task=,其中TNum表示任务的编号;TN为任务的名字;TD={d1,d2,…,dN}表示任务属性集合,di为对任务的第i项属性的描述集合;TS=(Sin,Sfin)表示任务的信息状态需求,Sin为任务开始时需要具备的信息状态集合,Sfin为任务完成时需要具备的信息状态集合;TOP是扩充字段,可根据需要添加内容。

系统功能可以表示为一个五元组Capbility=,其中CNum表示功能的编号;CN为功能的名字;CD为功能的详细描述;CI=(Pre,Del,Add)表示功能的信息属性,Pre是功能开始执行时必须满足的前提条件集,Del和Add表示操作对状态的影响(即执行该操作后,Del中的状态应该被删除,Add中的状态应该被增加);COP是扩充字段,可根据需要添加内容。为了更加详细地对系统功能中涉及的各类信息进行描述,这里将功能中的信息INFO分为态势信息sInfo和指控信息cInfo,即INFO=sInfo∪cInfo。一条态势信息S∈sInfo,可以定义为一个七元组S=。其中,sname表示态势信息的名称;sid表示态势信息的编号;stime表示态势信息生产的时间;sloction表示态势信息的地理位置;starget表示态势信息的目标;stype表示态势信息的类型,包括文字、图像、音频、视频等;sstate表示目标的具体状态,其数据类型由stype决定。

同样,一条指控信息C∈cInfo,可以定义为一个七元组C=。其中,cname表示指控信息的名称;cid表示指控信息的编号;ctime表示指控信息生产的时间;chigh表示指控信息的制定发送方;csub表示指控信息的接受执行方;ctarget表示指控信息的作用目标;cdir表示具体的指控命令。基于上述定义,信息属性CI中的Pre、Del和Add即可用谓词+INFO的形式进行描述。

状态集合State包含了系统在运行过程中所有可能出现的状态,描述了双方作战单元的情况和战场环境的情况。这里采用一阶语言来描述状态,假设一条状态p(name1,name2,…,namen)∈State,p表示谓词,namei(i=1,2,…,n)为变量。在上述定义中,TS中的Sin与Sfin,CI中的Pre、Del和Add本质上都是状态集合State的子集。

综上定义,作战任务-系统功能映射就是以任务Task为输入,找到一组功能集合{Capbility1,Capbility2,…,Capbilityn},使得初始状态能够演化到满足任务需求的最终状态。考虑到作战任务-系统功能映射的过程与HTN规划中将初始任务不断分解为原子任务十分类似。因此,本文在HTN规划的基础上提出了作战任务-系统功能映射方法。

2 基于HTN的作战任务-系统功能映射方法

2.1 HTN规划与SHOP2规划器

HTN规划是基于分层抽象和知识推理的智能规划技术,能够表示和处理领域知识,在任务规划[16]、云制造管理[17]、机器人自动化[18]等领域中得到了广泛应用。

HTN的规划领域D是一个四元组(S,Op,Me,γ),其中S为状态集合,Op表示操作,Me表示方法,γ:S×Op→S为状态转移函数。HTN规划问题P是一个三元组(s0,d,D),其中s0为初始状态,d为初始任务网络,D为规划领域。在给定规划问题P的情况下,HTN规划器利用Me中的方法将初始任务网络中的非原子任务进行分解,直至得到最终的原子任务。由于原子任务可以通过Op中的操作直接实现,因此可以根据当前的状态执行对应的操作。操作执行后,状态也会随之发生改变。不断执行上述过程,直至任务网络中只存在原子任务,如图1所示。

图1 HTN规划原理图Fig.1 HTN planning schematic diagram

SHOP2[19]是一种经典的HTN规划器,其实现原理类似于深度优先搜索方法。与其他 HTN 规划器相比,SHOP2具有更强大的预处理估计能力,因为其采用前向的规划方法,即按照执行顺序进行任务的分解。SHOP2的输入为规划领域文件和规划问题文件。规划领域文件主要包括以下领域知识。

(1) Me指出如何将复合分解为原子任务

(:method,head,Pre1,ability1/function1,Pre2,ability2/function2,…,Prei,abilityi/functioni)。其中,:method为关键字;head包括方法的名称和所需参数;Prei为前置条件,abilityi/functioni为分解后的能力或功能列表。只有当前置条件Prei被满足时,其对应abilityi/functioni才能被确定为该方法的分解结果。

(2) Op定义了原子任务如何被执行

(:operator,head,Pre,Del,Add [c])。其中,operator为关键字;head包括操作的名称和所需参数;Pre为前置条件。只有当前置条件Pre被满足,操作才能被执行;Del和Add表示操作对状态的影响(即执行该操作后,Del中的状态应该被删除,Add中的状态应该被增加);[c]为可选参数,能够表示执行该操作的代价。

SHOP2中的规划问题可定义为以下格式:(defproblem,problem-name,domain-name,([s11,s12,…,s1n1])T1,…,([sm1,sm2,…,smnm])Tm)。其中,defproblem为关键字;problem-name表示问题的名称;domain-name表示规划领域的名称;([s11,s12,…,s1n1])为可选参数,用来表示任务的初始状态;Ti为系统需要完成的任务。

2.2 基于HTN的作战任务-系统功能映射方法

首先,阐述HTN中各个概念在作战任务-系统功能映射过程中的具体含义如下。

(1) State与原SHOP2规划器中的定义类似,表示外界环境的情况以及特定数据、信息的获取情况。此外,State还包含了任务属性的具体描述信息。

(2) Me指明了完成某项任务需要具备的能力以及实现某种能力需要具备的子能力或功能。

(3) Op对应着系统内的一类服务资源,指明了功能的实现方式,并反映了任务执行后对State的影响。

(4) Policy为系统完成某项任务必须具备的功能序列。例如,针对一个高空目标防御任务,系统的功能序列为((!htracking,targethigh,targetstste),(!achieve,weatherinfo,ourstate),(!fusion,comprehensivesituation),(!report,reportup),(!makingdecision,plan))。

(5) Problem为系统需要处理的作战任务,根据上级作战需求确定。

由于State中包含了任务属性的具体描述信息,经典的SHOP2算法无法直接对该类问题进行处理,因此需要在使用SHOP2规划算法前对问题进行处理。首先,分析一下SHOP2算法失效的原因。在SHOP2算法中,Me中的前提条件是按照顺序进行验证的。图2为一个方法实例,在前提条件验证时,算法会从上到下按照顺序进行验证。若防空任务仅有防御中高空目标的需求状态,则规划器会选择branch1,执行中高空目标的跟踪服务;若防空任务仅有防御低空目标的需求状态,则规划器会选择branch2,执行低空目标的跟踪服务。但是,若上层作战需求要求系统能够同时具备中高空目标和低空目标的防御能力,该规划器将会在选择branch1后直接结束对该方法的处理,即低空目标的防御需求将被忽略。

图2 方法案例Fig.2 Method case

为了将SHOP2规划器用于作战任务-系统功能映射方法,本文考虑根据作战的属性对作战任务进行预处理,将其分解为多个SHOP2算法可规划的简单任务,利用SHOP2算法分别对上述简单任务进行规划,再将所有规划结果整合为完整的系统能力需求。

图3 基于HTN规划的作战任务-系统功能映射方法框架Fig.3 Framework of combat mission-system function mapping method based on HTN planning

图3中的规划知识可以由领域专家提供,即由专家给出能力的分解方法和功能的实现方法,领域知识库可以随着能力和功能的增加而不断扩充。规划器则选取SHOP2的JAVA版本JSHOP2。

2.2.1 作战任务分解

作战任务分解的实质就是找到所有可能的属性组合,可以利用递归算法直接遍历N类属性的所有组合,从而得到Np个JSHOP2规划器可直接处理的简单任务,即每个任务满足|di|=1(i=1,2,…,N)。鉴于上述思路,对作战任务进行分解,具体步骤如算法1所示。

算法 1 基于递归思想的任务分解算法输入 初始作战任务Task输出 分解后的作战任务集合RTS={Task'1,Task'2,…,Task'N}步骤 1 提取Task的任务属性集合TD={d1,d2,…,dN}步骤 2 res←reduction(TD,N)步骤 3 RTS←⌀,i←1步骤 4 for tdi∈res,Task'i←Task,Task'i.TD←tdi,RTS←RTS∪Task'i,i←i+1步骤 5 if i≤∏Ni=1|di|,to 步骤4;else,输出RTS。其中,reduction(TD,N)为属性递归分解算法,其定义如下:reduction(TD,N)if N=1 return res=td1,endelse,temp←reduction(TD,N-1)res←temp×tdN(×为笛卡尔积)return resreduction(Stater,N) end

2.2.2 映射方案整合

为了将多个能力匹配方案进行整合,首先对能力匹配方案进行描述。考虑到SHOP2规划器得到的能力匹配方案Policyi是一个顺序流程,可以用有向图的形式描述Policy中各功能之间的关系,如图4所示。

图4 能力匹配方案案例Fig.4 Capability matching scheme case

图4中,S和E分别表示开始和结束,小写字母表示不同的功能。图4的邻接矩阵为

在矩阵A中,前两行分别表示开始和结束,从第3行起依次表示Policyi中的各功能。若Ai,j=1,表示j为i的后继节点;Ai,j=0,则表示i和j没有直接关系,可以假设方案集合为POL={Policyi}(i=1,2,…,M)。在上述方案描述的基础上,本文提出了一种能力方案整合算法,如算法2所示,将多个Policy整合到一个方法中。

算法 2 基于邻接矩阵的方案整合算法输入 方案集合POL输出 整合后的最终方案Policyf步骤 1 随机选择POL中的一个方案Policyr,根据其能力间的相互关系得到邻接矩阵Ar,POL←POL{Policyr};

3 仿真实验

考虑一个联合作战场景下的作战任务-系统功能匹配问题,根据作战需求,明确系统需要支持空海联合作战行动,利用空基平台和海基平台完成对对方空中与海面目标的打击任务。任务的具体属性如表1所示。从表1中可以看到,该任务的执行需要系统为空基平台和海基平台提供导航、对对方空中目标和海上目标进行跟踪,并完成对海空导弹与空面导弹的导引。表2为功能列表,为提高针对性,这里只显示了与上述任务相关的功能。表3为方法列表,反映了任务到子任务、任务到功能的映射关系。表2和表3基于规划领域定义语言(planning domain definition language, PDDL)[20]可以直接构成规划领域文件,而表1由于包含了多个选项的任务属性,需要先利用算法1对任务进行分解,才能够使用JSHOP2规划器进行求解。在算法1下,ASJO任务可以分解如表4所示。

表1 空海联合作战任务描述Table 1 Air-sea joint operations mission description

表2 相关系统功能列表Table 2 List of related system functions

续表2Continued Table 2

表3 相关规划方法列表Table 3 List of related planning methods

表4 分解后的任务列表Table 4 List of post-decomposition tasks

利用JSHOP2规划器可得上述问题的规划解,如表5所示。为了整合规划解,这里将表5中的能力匹配方案作为算法2的输入,可得到合并后的邻接矩阵,如图5所示。从图5可以看到,经过合并后,d8和d9的后继节点只有一个,而c4、d1、d2、d4和d5的后继节点都有两个。根据上述邻接矩阵,可以得到最终的任务-能力匹配方案,如图6所示。

表5 规划解集Table 5 Planning solution set

续表5Continued Table 5

图5 合并后的邻接矩阵Fig.5 Merged adjacency matrix

图6 最终任务-能力映射方案Fig.6 Final mission-capability mapping scheme

由图6可以看到,最终得到的匹配方案包含了对空基平台和海基平台的引导能力、对空中和海上目标的跟踪能力以及对空空导弹和海空导弹的制导能力,满足任务的实际需求。而对陆基平台的引导、陆上目标的跟踪以及空面导弹的制导等与任务需求无关的能力并没有被列入到匹配方案中,有效避免了系统能力的冗余。

4 结 论

为了解决作战任务-系统功能的自动映射问题,本文首先对作战任务与系统能力/功能进行建模,然后基于任务和能力可以分解的特点,将作战任务-系统功能的自动映射问题转化为智能规划问题,并基于HTN对问题进行求解。考虑到JSHOP2规划器在求解问题时无法处理多属性输入的问题,基于递归算法将待求解问题分解为JSHOP2规划器能够求解的规划问题,并利用邻接矩阵将多个规划解进行整合,得到了最终的作战任务-系统功能映射方案,为系统面向任务的自动生成提供了基础支撑。