马 硕，马亚平

（1.国防大学，北京 100091；2.解放军92232 部队，北京 100161）

0 引言

在复杂的战争条件下，作战单元面对的将是开放、动态、不确定的环境，这对发展智能化任务规划系统提出了更高的要求。特别是对于无人系统，如何在复杂的战场环境中降低对人员操作的依赖性，是亟待解决的重要问题。为此，智能无人系统的任务规划技术也从预编程生成任务关联动作，向在未知环境中自主完成作战任务的方向发展。

根据思维方式的不同，现代作战筹划方法一般分为逆向作战筹划方法和正向作战筹划方法两大类［1］。分层任务网络方法HTN 是一种层次化的规划框架，规划的目的是完成某一任务集合，规划的过程是递归将非原子任务分解，直到出现可以直接执行规划动作就能完成的原子任务为止［2］。HTN 对任务进行逐层分解细化的处理方法，体现了“自上而下”、“由粗到精”的正向作战筹划思维模式，已在作战任务规划领域得到了应用［3-5］，但HTN 不能根据任务目标进行决策推理生成作战决策方案，没有提供逆向推理规划机制，因此，也限制了HTN 在军事领域的应用范围。此外，HTN 方法要求建立问题领域完备的知识模型，处理方法需要覆盖任务执行过程中各种可能出现的状况，否则将导致任务规划失败，这对HTN 使用人员开展问题领域建模工作，特别是在动态、不确定的任务执行环境条件下建模，提出了很高的要求。

在HTN 基础上，提出一种新的智能规划方法—分层目标任务网络HGTN，给出了HGTN 的形式化定义和求解算法。HGTN 在保持HTN 的分层任务分解能力的同时，还具备基于目标的任务推理规划机制，并在一定程度上改进了HTN 方法的适应性。

1 分层目标任务网络HGTN

1.1 HGTN 形式化定义

定义1：HGTN 任务网络是形如tn=（T，C）的二元组，其中T 为有限任务节点集合，C 为任务节点的约束关系集合。每个节点t∈T 表示一个任务，可以是原子任务、目标任务或组合任务（compound task）。关于操作（operation）和原子任务（atom task）的定义与HTN 定义相同。

定义2：HGTN 目标任务（goal-based task）是一个二元组，t=（head（t），goal（t）），表示一项需要完成的非原子任务活动，通过描述任务所要达成的目标（goal）实现对任务的定义。式中，head（t）语法形式为nt（x1，…，xk），nt 是唯一的方法标识符，（x1，…，xk）是所有在goal（t）中任意地方出现的变量符号。goal（t）表示任务t 的目标，通过基文字集（ground literals set）的DNF（析取范式）公式表示。

定义3：HGTN 组合任务（compound task）是由多个原子任务或目标任务组合而成的任务。

定义4：HGTN 方法（method）是一个四元组，m=（head（m），task（m），precond（m），subtasknet（m）），描述了对非原子任务的分解方法。式中，head（m）语法形式为nm（x1，…，xk），nm 是唯一的方法标识符，（x1，…，xk）是所有在方法m 中任意地方出现的变量符号；task（m）为组合任务或目标任务；文字集合precond（m）是方法的前提条件；subtasknet（m）是通过方法m 分解后的子任务网络，子任务中可以包括原子任务、目标任务或组合任务。

定义5：设m 为一个方法实例，t 为一个组合任务，如果task（m）=head（t），则m 与t 相关（relevant）。

定义6：设m 为一个方法实例，t 为一个目标任务，goal（subtasknet（m））为子任务列表中目标任务的目标集合，如果goal（subtasknet（m））∩goal（t）≠Ø，则m 与t 相关。

定义7：HGTN 规划域（planning domain）是形如D=（D'，M）的二元组，其中，D' 是经典规划领域模型［6］，M 是HGTN 方法集合。

定义8：HGTN 规划问题（planning problem）是一个三元组triple P=（D，S0，tn），其中，D 是规划域，S0是初始状态，tn=（T，C）是一个HGTN 任务网络。

定义9：令规划π 为规划问题P 的一个解，则规划解π 满足以下情况：

情况1：任务网络tn 为空，此时如果规划解π为空，则π 是P 的解。

情况2：存在t 为T 的一个无前驱（no predecessors）原子任务节点，如果操作a 在状态S0下可作用于t，设π'为HGTN 规划问题（D，γ（S0，a），（T '，C'））的解，则＜a，π'＞是规划问题P 的解（符号＜＞表示序列）。式中，T'=T-{t}，C'是C 中关于T'的约束关系。

情况3：存在t 为T 的一个无前驱组合任务节点，设方法实例m 在状态S0下可作用于t，且与t 相关，将节点t 从T 中删除，在t 的位置上插入subtasknet（m）（先前作用于节点t 的约束条件作用于subtasknet（m）中的每个节点），形成的新任务网络为tn'，如果π 为规划问题（D，S0，tn'）的解，则π 是P 的解。

1.2 HGTN 规划算法GTDP

根据HGTN 的相关定义，设计规划算法GTDP（Goal-Task Decomposition Planner）伪代码如图1 所示。

图1 HGTN 规划算法GTDP的流程描述

基本流程如下：

如果tn 为空集，则表示所有任务已完成，因此，GTDP 返回当前规划π。否则，GTDP 选择一个无前驱任务节点t∈tn；如果t 是一个原子任务，在当前状态下可用的操作集合中（如果集合为空，则任务无法完成，规划失败），任取一个操作实例（instance），将其加入当前计划π 动作序列后递归调用GTDP。如果t 不是原子任务，则在当前状态下可用的方法集合中取一个方法实例，任务子网络替换任务t 后递归调用GTDP。

定理1（GTDP 正确性soundness）：设P=（D，S0，tn）是一个HGTN 规划问题，则任何由算法GTDP（D，S0，＜tn>，＜>）所返回的规划π 都是规划问题P的解。

证明：根据HGTN 定义，采用归纳法证明。设GTDP 生成的规划解π 的长度为n，即π=＜a1，a2，…，an＞。

当n=0 时，π=Ø。当tn=Ø，或当找不到与任务相关的操作或方法时GTDP 返回failure。

假设规划＜a1，a2，…，ak，πk>（k＜n）是问题P 的解，πk是问题P'=（D，Sk，tnk）的解（其中，Sk=γ（γ（γ（S0，a1），a2），…，ak）=γ（S0，＜a1，a2，…，ak＞）；tnk为GTDP 在生成ak操作解时，所生成的任务网络）。则算法GTDP（D，Sk，tnk，＜a1，a2，…，ak＞）在执行过程中，当tnk中存在无前驱的原子任务节点，且存在ak+1是与t 相关的、当前状态下可用的操作集合中的一个操作实例，根据定义8，＜ak+1，πk+1＞为问题P'=（D，Sk，tnk）的解，因此，＜a1，a2，…，ak，ak+1，πk+1＞为问题P 的解；当tnk中存在无前驱的组合任务节点，且存在m是与t 相关的、在状态S 下可用的方法实例，子任务网络插入后形成新的任务网络tnk'，根据定义8，问题P"=（D，Sk，tnk'）的解πk"即为问题P'的解，因此，＜a1，a2，…，ak，πk"＞是问题P 的解。由于GTDP 计算过程是递归迭代的，因此，GTDP（D，S0，＜tn>，＜>）所返回的规划π 是规划问题P 的解。

定理2（GTDP 完备性completeness）：设P=（D，S0，tn）是一个HGTN 规划问题，Π 是P 的所有解的集合，对于每个π∈Π，GTDP 至少有一条执行路径对应π。

证明：采用归纳法证明，设π=＜a1，a2，…，an＞是规划问题P 的解。

当n=0 时，π=Ø。在GTDP 算法中，当tn=Ø，或当找不到与任务相关的操作或方法时返回failure。

假设GTDP 生成规划解π'的前k 项与π 的前k 项＜a1，a2，…，ak>相同（k＜n），且对应的任务网络tnk也相同。由于π 是P 的解，因此，任务网络tnk，或通过相关方法集合分解后的任务网络中应包含与操作ak+1相关的原子任务。则根据算法1，GTDP（D，Sk，tnk，＜a1，a2，…，ak＞）在执行过程中（其中，Sk=γ（γ（γ（S0，a1），a2），…ak）=γ（S0，＜a1，a2，…，ak＞）），当tnk包含与操作ak+1相关的原子任务时，GTDP 返回的解为＜a1，a2，…，ak，ak+1＞；否则，由于存在相关的方法集合mk 可以分解得到与操作ak+1相关的原子任务，因此，存在一条GTDP 的执行路径，使得GTDP 选择的任务相关方法集合与mk 相同，并返回解＜a1，a2，…，ak，ak+1＞。由于GTDP 计算过程是递归迭代的，因此，对于每个π∈Π，GTDP 至少存在一条执行路径对应π。

1.3 GTDP 算法扩展

1.3.1 启发式搜索算法HGTDP

传统HTN 规划方法处理待分解的任务，采用的是按照指定的任务类型进行替代的方式，无法引入搜索信息，只能采用盲目搜索方法，如SHOP2 等［7］。当任务网络中的任务均为原子任务和目标任务时，原子任务的正效果effect+相当于任务的目标，因此，原子任务本身也可以作为一个目标任务，从系统当前状态S 到目标G，可以通过设计合理的启发函数h（u），进一步提高GTDP 算法的求解速度。HGTDP（Heuristic Goal-Task Decomposition Planner）算法伪代码如图2 所示。

算法2 与算法1 的主要区别，在于引入启发函数h（u）后，将算法1 中行8、行11 中非确定性的选择方式，转换为根据启发函数所计算的启发值大小进行排序，优先执行启发值大的操作或方法。因此，算法2 性能优劣很大程度上取决于启发函数的设计，可根据具体领域问题特点设计专有的启发函数，也可以使用领域无关的启发函数（如快速前向规划器FF-planner［8］所使用的放松图启发函数）。

1.3.2 目标推理规划算法GTIDP

当目标任务无对应的相关方法时，设当前规划问题P=（D，S0，tn），以状态S0为初始状态，D 为规划域，任务t 的目标goal（t）为规划目标g，形成一个经典规划问题P'=（D，S0，g），此时可以采用经典规划中的快速规划方法（如FF-planner 等）求解。

GTIDP（Goal-Task Inferring and Decomposition Planner）伪代码如图3 所示。

图3 GTIDP 的流程描述

2 基于HGTN 的作战任务规划方法

无人水下航行器（Unmanned Underwater Vehicle，UUV）在水雷战等海上作战领域得到了日益广泛的应用［9］。以UUV 执行水下布雷任务为例［10］，说明基于HGTN 的作战任务规划基本流程。示例语法格式参照HTN 以及PDDL［11］的相关定义。

2.1 建立规划域D

根据定义，HGTN 的规划域D 包括操作O 和方法M。操作描述作战行动执行的约束以及效果，是可由作战单元直接执行的动作，方法则描述了作战任务分解的规则。接到布雷作战命令后，通常需要开展布雷战术计算（包括数量和位置计算等）、运输、布放、投送、回收等一系列子任务，因此，“布雷任务”可以作为一项组合任务，根据领域专家的经验知识或相关条例规定，使用相应的方法进行任务细化分解，见图4 所示。

图4 布雷任务方法示例

方法seamine_laying 对应“布雷任务”，包括3个全序子任务：辅助战术计算任务tactical_aids（可通过调用外部函数实现）、水雷布放任务mine_at（把水雷?mn 布放到指定位置点）以及回收UUV 任务uuv_at（UUV?uv 返回至回收点?recoverypoint）。前提条件是：水雷布放点?endpoint 在雷区?mf 内，回收点?Recoverypoint 在布雷方控制区?cf 内，且水雷?mn 和UUV?un 处于可用状态。

水雷布放任务mine_at 可以作为组合任务，按HTN 的方式对其进一步分解为一系列子任务。也可以作为HGTN 目标任务，见图5 所示。

水雷布放任务方法（将水雷?mn 从区域?cf 中的贮存点?storagepoint，经由UUV 入水点?startpoint 投送到雷区?mf 中的终点?endpoint）

图5 水雷布放任务方法

方法lay_mine 将目标任务（mine_at?mn?endpoint）分解为两个子目标任务，实际的含义是：若要将水雷从贮存位置?storagepoint 投到指定的布雷点?endpoint，应先将水雷?mn 运输至UUV 的入水点?startpoint，再由UUV 投送至布雷点?endpoint。任务目标（mine_at ?mn ?endpoint）与方法lay_mine 的子目标任务（mine_at ?mn ?endpoint）相匹配，因此，根据HGTN 定义6，lay_mine 是与目标任务（mine_at?mn?endpoint）相关的方法之一。

图4、图5 分别对应HGTN 组合任务方法（和HTN 方法一致）和目标任务方法。

2.2 建立规划问题P

根据定义，规划问题P 包括初始状态定义和任务网络。初始任务为seamine_laying。

2.3 问题求解

根据问题领域要求，使用合理的求解算法。

如果规划域中的部分方法建模考虑不完备（例如没有图5 任务对应的方法），对于传统HTN 规划方法，任务无法分解导致无解，而使用HGTN 的GTIDP 算法，以（mine_at?mn?endpoint）目标进行规划，可以得到相应的规划解。

如果增加多种布雷投送方式，如无人机或无人艇等［12］，可以引入考虑任务成本（如时间成本）的启发函数［13］，以成本最小为目标使用GTIDP 算法求解，而传统HTN 规划方法无法使用搜索信息。

表1 几种规划方法对比

3 结论

HTN 逐层分解任务的规划方法体现了问题领域专家解决具体问题的知识经验，而本文提出的HGTN 规划方法进一步扩展了HTN 概念，增加了目标任务和相关处理方法，引入了基于目标的推理规划机制，对问题领域建模的表达上更为灵活，提高了规划方法的适用性。目前对HTN 规划方法的主要研究方向是扩展时间、资源［14-15］、动态任务规划［16］等规划能力，对HGTN 规划方法扩展上述功能，是后续需要开展的主要工作。