基于着色Petri网的无人机侦察战术规划

张源原, 高 阳, 朱 鹏, 刘锦涛, 谷树山

(1. 海军航空大学第一飞行训练基地教练机模拟训练中心, 辽宁 葫芦岛 125000; 2. 陆军工程大学指挥控制工程学院, 江苏 南京 210042)

0 引 言

无人机任务规划分系统主要完成路径规划、有效载荷规划、方案评估及选择等功能。这些功能按照规划的对象及任务背景的侧重点可以分为三层:行动规划、战术规划以及航迹规划。行动规划主要完成多机的任务分配及其协同规划,具体需要结合任务要求、所处态势及有效资源,给出最优任务分配及对应的行动方案;战术规划主要对单机作战中的战术动作进行规划,具体需要结合任务要求、约束条件、所处态势以及载机及武器系统的使用限制等,确定机载传感器(如雷达)的使用等动作的参数及各种动作在空间及时间上的关系;航迹规划即根据无人机的飞行性能模型、任务要求规划出最优航迹。

在上述三层规划中,行动规划及轨迹规划研究较为充分,人工势场法、A*算法以及诸如模拟退火算法、禁忌搜索算法、遗传算法、粒子群算法、蚁群算法等智能算法都在这些规划领域得到了应用,但是与任务执行最紧密的战术规划领域,相关研究较少。战术规划一方面要满足载机及机载设备的物理特性要求;另一方面又要满足任务要求及指挥员的意图。所以,在设计无人机战术规划的功能中,需要设计一种易于战术知识表达的结构,强化系统设计者与战术制定者之间的沟通及交流。同时,该结构应能够有效的将任务按照计划、目标的顺序进行有序分解,最终得到无人机的动作序列,例如平飞、跃升、俯冲、开机、投弹等,并按照序列固化、参数可调的原则将其转化为一个离散动态系统。而且,不同的计划与计划、目标与目标之间不是孤立的,不仅受到可利用资源的影响,而且互相也存在影响。所以,战术规划的重点是对任务的有序分解及其目标的推理。

在美国飞行员助手项目中,采用了计划-目标图(plan-goal graph,PGG)作为计划-目标层次分解的工具。PGG是具有一定抽象及聚合特点的图表,以不同形状的节点表示计划及目标,计划和目标之间通过具有约束值的线段交替连接。PGG中,最顶层节点代表系统最抽象的目标节点(用),与之连接的是高度聚合的计划节点,由一系列抽象行为组成。随着PGG的逐层向下,节点代表的内容越来越具体,最底层节点代表飞行员或者agent可以执行的动作。PGG的引入不仅给飞行员及设计人员提供了结构,用于战术知识的分析,而且该结构可用于飞行员信息需求的解释、预测以及确定飞行员助手系统中各个模块之间功能的交互。虽然PGG具有如上优势,但是由于缺乏数学定义,无法有效对结构进行分析,而且PGG图不具备扩展能力以及动态特性,无法实现动态分析。本文以无人机战术规划问题中的资源分配及目标推理为研究对象,采用着色Petri网,在对总体任务按照计划——目标顺序分解为子任务后,分别设计了消耗类资源规划、正效应规划及负效应规划建模方法,实现对各子任务的建模,最后利用该方法对无人机侦察任务进行建模,验证了方法的有效性。

1 着色Petri网

Petri网的建模元素包括库所、变迁、有向弧以及托肯,为了增强Petri网的建模能力,众多学者尝试对上述建模元素进行扩展,分层、时延、随机Petri网都是针对库所及变迁进行的扩展,这些扩展Petri网极大丰富了其可描述对象。但是依然存在一个问题,即没有数据概念。为了解决这一问题,着色Petri网主要对托肯及有向弧进行扩展,使其能够将数据纳入到网结构的描述中,具体扩展内容如下。

(1) 每个标记附加一个颜色数据值。

(2) 对各条有向弧定义标记类型和通过条件。

(3) 对变迁定义变迁表达式函数,对触发条件进行约束。

以下给出着色Petri网形式化定义。

多元组CPN=(∑,,,,,,,,)为着色Petri网,其中:

(1) ∑是类型的非空有限集,也称为颜色集;

(2)是有限库所集合;

(3)是有限变迁集合;

(4)是有向弧集合;

(5)是节点函数,:→×∪×;

(6)是颜色函数,:→∑;

(7)是变迁表达式函数,也可以称为守护函数,:→Expression,满足:∀∈:[Type(())]=∧Type(Var(()))⊆∑。其中,Type()表示变量的类型;Var(expr)表示表达式Expr的变量集;

(8)是弧表达式函数,:→Expression,满足:∀∈:[Type(())=()∧Type(Var(()))⊆∑],其中,为()中的库所,()表示居于()上的所有多重集的集合;

(9)是初始化函数,:→CloseExpression,满足:∀∈:[Type(())=()]。

2 计划-目标层次分解

基于Petri网的计划-目标层次分解通过一个树结构,利用Petri网中的库所及变迁描述目标、计划以及行动。计划由子目标以及一组有序的行动序列构成,行动序列从库所起始,通过变迁连接到其他库所,这些变迁代表了可以执行的行动。目标同样用库所起始,通过变迁连接到其他计划。

树结构由库所及变迁组成,其中计划节点可以包含多个子目标节点,这些子目标必须全部完成,该计划才能实现。目标/子目标节点可以包含多个计划节点,实现多个计划中的任何一个都能完成该目标节点。子目标节点和计划节点的结构图如图1和2所示。

图1 子目标节点结构图Fig.1 Subgoal node structure

图2 计划节点结构图Fig.2 Plan node structure

在图1的子目标节点中,顶部库所的容量限制为1,当变迁、中任一变迁触发,中的托肯被移除,防止另一组计划激活。在图2的计划节点中,虽然的容量依然为1,但是当变迁触发,和子目标节点都获得一个托肯,从而允许一个计划下的多个子目标可以同时进行。在图1的子目标节点结构图底部,还需要对所有计划支路分别设置独立的变迁,并将这些支路汇合。当所选计划支路实现之后,设置的变迁触发,从而将托肯置于“完成”库所中,以表示子目标完成。而对于图2所示的计划节点结构图,需要在底部对所有支路设置一个单独的变迁,只有当所有支路的“完成”库所都获得托肯之后,变迁才能触发,从而实现顶部计划库所。

3 消耗类资源规划建模方法

资源可以分为两类:消耗类资源以及再生类资源。例如,通信信道属于再生类资源,而时间或是燃油属于消耗类资源。在使用Petri网技术对任务按照计划、目标顺序进行层次分解的基础上,使用着色技术,将每一计划及其行动序列所消耗的资源纳入模型当中,并将这些资源信息从结构图底部自下而上的传递,最终得到资源信息总览。利用资源信息总览,首先可以基于可利用资源判断某个目标是否可以安全完成,或者在执行某个目标的计划过程中,判断是否有足够资源完成其他目标,其次可以用于在目标的多个计划中选择消耗资源最少的计划。由于再生类资源对目标、计划的影响较小,本文不作分析。

图3给出了消耗类资源模型,图中库所、变迁、变迁表达式、弧及弧表达式含义如表1所示。图3中,库所关联了一个着色托肯,从而可以描述数据,代表着某消耗类资源,当前余量为100。对库所关联两个变迁,变迁检查该资源余量,判断当前余量是否大于消耗量,当变迁表达式≥时,变迁触发。变迁代表某行动对该资源的消耗为,当变迁表达式-≥0时,变迁触发。需要注意的是,弧是双向的,代表变迁并不改变库所的资源量。

表1 消耗类资源模型各元素含义

图3 消耗类资源模型Fig.3 Consumable resources model

图3仅对单一消耗类资源进行建模,当存在多种消耗类资源时,需要将这些资源的消耗量汇总到资源信息总览。如果某类资源较为稀缺或者在任务执行过程中需要大量使用,则可以在汇总过程中,对该类资源附加更高权值。

资源信息总览包含两类数值,第一类是每一类资源的消耗量,第二类是资源消耗总量。第一类数值用于判断某个目标是否能够安全完成,如果可以且目标被选择,则预留出消耗量资源,第二类数值用于判断资源消耗总量情况,从而选择最优计划支路。对于每一个目标及计划,需要关联两个资源信息总览数值分别描述最优计划(best plan, BP)消耗量以及最次(worst plan,WP)计划消耗量。

图4给出了如何将资源信息总览作为库所加入到计划-目标层次分解结构图中,从而实现子目标最优计划分支的推理。图4中库所及变迁的含义如表2所示。当库所(子目标1)获得托肯,首先对、及库所(计划1、2、3)的资源信息总览(、及库所)进行比较,假设没有其他因素限制计划的选择,那么与最优计划相关联的变迁将会触发。

图4 最优计划推理结构Fig.4 The most optimal plan reasoning structure

表2 最优计划推理结构图中库所含义

当各计划、子目标的资源信息总览自底向上汇总至顶部目标,任务主体可以根据这些信息判断是否采取行动去完成该目标,以及判断正在进行的目标是否还能顺利完成。图5给出了当目标序列加入新目标到新目标完成之后,资源信息总览更新的过程,图中各元素含义如表3所示，其中更新资源用表示，原资源用表示。

图5 基于资源信息总览的任务目标推理Fig.5 Mission goal reasoning based on resources information summary

表3 基于资源信息总览的任务目标推理图中各元素含义

其中,变迁的变迁表达式为=,并传递新目标所需要的资源,变迁的变迁表达式为=-。

任务管理层模型保存着主体选择完成的全部目标的资源信息总览,存储在库所中,所以在执行一个新目标的行动序列之前,首先要通过变迁更新资源信息总览,并根据资源余量判断是否能够将新目标安全的加入到目标序列中,如果有充足的资源余量,则加入新目标并执行。当新目标完成之后,再一次更新资源信息总览,同时利用图4所示模型更新资源余量。

4 正效应规划建模方法

正效应是指在执行任务过程中,任务主体可能同时执行多个目标,这些目标的触发条件可能相同,对应的计划及产生的效果也可能相同,所以,仅仅执行其中一个计划即可以同时完成两个目标的要求。当正效应出现在计划——目标层次模型的顶部时,经过有效推理,可以避免大量的重复工作以及资源的消耗。

正效应的判断首先可以通过计划产生的效果来判断。当两个计划实现相同效果时,只需要执行其中一个。但是,存在一种情况,即两个计划的触发条件不能同时满足,此时必须待第二个计划的触发条件再次满足才能实现正效应。

图6给出了基于Petri网的正效应推理模型,各元素含义如表4所示。当推理网中及库所获得托肯,代表子目标准备执行,执行之前需要判断该目标所要到达的效果(变量网中库所的着色托肯值)是否已经达成,即变迁触发,开始进行正效应推理。当库所的着色托肯值不符合目标所达效果,库所获得托肯,代表该子目标未实现,变迁触发,库所获得托肯,开始执行相应的计划。当计划执行完毕之后,变迁触发,通过弧获取库所托肯值,然后通过弧将库所托肯值设置为目标效果值。

图6 正效应推理模型Fig.6 Positive effect reasoning model

表4 正效应推理模型各元素含义

总体目标网中库所存储着待完成目标效果托肯值,托肯数等于待完成目标数,变迁检查各变量网中的变量托肯值,在子目标实现之后,库所托肯值设置为目标效果值,变迁触发,将库所中满足条件的托肯移入库所中,当中的全部托肯移入时,触发,库所获得托肯,代表总体目标完成。

需要说明的是,变量网中库所存储的着色托肯值允许其他计划关联的变迁进行修改。

5 负效应规划建模方法

负效应存在于3个以上的目标之间,其中两个或多个目标同属于相同计划。假设计划包含两个子目标,和,而且、之间存在因果关系,即目标产生的结果是目标触发的前提条件,此时目标正在执行。同时,存在另一个正在进行的计划,其对应目标为,而且目标产生的结果与目标相反。那么,目标的实现就会阻碍目标的触发,导致计划无法完成,浪费了用于目标的资源。负效应可以通过将目标的执行安排在、目标之前或者之后来避免。

图7给出了基于Petri网的负效应推理模型,各元素含义如表5所示。图7中，库所与库所表示的子目标与同属于一个计划,且触发条件是的结果,为了避免其他计划对的影响,对变迁添加变迁表达式,使与结果相关的变量库所中增加一个保护托肯,如图7变量网中的红色托肯,当其他可能更改库所值的目标执行前,需要检查库所中是否包含保护托肯。当与相关的计划及其行动执行完毕,触发改变相关变量库所托肯值的同时,将库所中的保护托肯移除,从而允许其他影响库所的目标可以开始执行。

图7 负效应推理模型Fig.7 Negative effect reasoning model

表5 负效应推理模型各元素含义

6 无人机侦察战术规划

为了综合验证本文提出方法的有效性,以无人机侦察任务为背景,首先使用计划——目标层次分解方法将任务进行逐层分解,然后将正效应规划、最优计划选择,变量管理图(包含负效应规划)、总体目标管理图(包含基于消耗类资源规划)用于层次分解图中,最终实现无人机侦察任务的战术规划。

任务背景:一架无人机需要前往A地执行侦察地形任务,前往B地执行侦察敌情任务,在获得侦察结果之后,需要将情报通过数据链传送至基地,但是当存在干扰或者其他原因导致传输系统无法正常工作时,需要无人机立即返回基地上传数据。

上述任务的关键库所及变迁含义如表6所示,总体目标管理图、变量管理图、层次分解结构图分别如图8～图10所示。

表6 部分元素含义

图8 侦察任务总体目标管理图Fig.8 General goals management graph of reconnaissance mission

图9 侦察任务变量管理图Fig.9 Variables management graph of reconnaissance mission

图10 侦察任务层次分解结构图Fig.10 Hierarchical decomposition graph of reconnaissance mission

在任务执行过程中,燃油、数据链分别属于消耗类资源和再生类资源,本文只将燃油消耗类资源纳入模型中。为了阐述负效应规划的应用,将位置信息归为特殊资源,无人机需要根据任务要求更新位置信息,同时对其进行保护。例如,在前往A地过程中,禁止执行前往B地目标。侦察任务的目标总共包括:前往A地、前往B地、侦察A地、侦察B地、传输A地情报、传输B地情报。

无人机在领受任务之后,层次分解结构图中的托肯历经(,,,)到达各子目标库所中(,,,,,),并针对各子目标下的计划执行正效应规划,托肯进入正效应规划起始库所(,),由于所有子目标均没有被实现,即不存在正效应,所以各子目标均处于待命状态,等待条件满足使对应变迁触发执行对应计划。在各子目标库所获取托肯同时,总体目标管理网中变迁的触发使库所获得6个托肯,代表所有待完成子目标。

此时,变迁及具有发生权,假设无人机首先选择前往A地,在前往A地之前需要判断燃油是否足够启动该计划,对应的过程如下:变迁获取前往A地计划消耗的燃油信息(存储在库所中),总体目标管理网中变迁更新资源信息总览,并与变量管理网中的剩余燃油库所进行比较,判断剩余燃油是否足够。假设剩余燃油满足飞往A地要求,变迁触发,同时通过变迁对变量管理网中的位置库所添加保护托肯,飞往B地目标在执行之前首先要检查位置库所是否包含保护托肯,此时由于含有保护托肯,所以变迁无法触发。

在到达A地之后,变迁触发代表该子目标完成,对应总体目标管理图中触发,将到达A地子目标托肯移入,同时更新资源信息总览,变量管理图中触发,对剩余燃油量进行修改。随后,无人机开始执行侦察任务区域A子目标,在该子目标完成时,即变迁触发,对应变量管理图中变迁触发,移除位置库所中的保护托肯,从而允许飞往B地子目标可以开始执行。

在飞往B地过程中,传输A区域信息中的变迁,同时也满足触发条件,由于位置库所被飞往B地子目标的执行重新添加保护托肯,需要返回基地的计划支路不可能执行,而且,即使无人机没有执行飞往B地计划,也会由于该计划会消耗燃油,使传输A区域信息子目标优先执行通过数据链传输计划,只有在数据链无法使用情况下,返回基地的计划支路才可能执行。

随着各子目标的全部完成,总体目标管理图中的获取6个托肯之后,变迁触发,使库所得到托肯。同时,层次分解结构图中的获得托肯,代表侦察任务的全部完成。

7 结束语

战术规划的重点是对任务的有序分解及其目标的推理。本文首先利用Petri网实现了任务的计划-目标层次分解,所得结构图有助于战术知识的表达。其次,在讨论了战术规划中消耗类资源规划及目标间的正效应、负效应规划问题的基础上,利用着色Petri网中的着色托肯能够描述数据的特点,对计划-目标层次分解结构图进行改进并引入正效应规划,设计总体目标管理图配合层次分解结构图实现了消耗类资源规划、设计了变量管理图实现了负效应规划。最后,以无人机侦察任务为例,采用本文提出的方法对其建模,验证了本方法的有效性,即不仅能够实现任务的计划-目标层次描述,而且能够实现目标、计划的在线推理,允许任务主体根据外部态势自动选择合适的目标,避免冲突以及资源的浪费,最终实现战术的规划。

从侦察任务层次分解结构图可以看出,针对一个简单无人机侦察战术规划任务,由于需要考虑诸多因素,导致网结构复杂,而且不能表达任务执行的时间因素,在今后的研究中,可以将分层及时延概念引入结构图中,简化网络并能模拟时间带来的影响。