·20· 智能系统学报 第2卷 (b).这种机制不仅可以方便地描述领域中的众多 Erol等人的形式化定义.SHOP用通用的HTN语 抽象任务，而且可以描述任务、动作间的层次依赖关 法结构描述不同领域的对象、状态、任务分解策略， 系，适用于具有层次任务结构的规划领域.HTN规 形成了一种通用的HTN描述机制，成为不同领域 划可描述为一个三元组形式D=<I,T,Me>,其 专用知识的建模基础.OCLh则在领域描述中加入 中I表示初始状态集合，T表示抽象任务的集合， 了对对象分类的支持，使领域模型具有层次化结构 Me表示任务分解策略的集合.由于许多应用领域 1.3基于约束的规划 的任务通常按层次结构组织和管理，HTN规划在 基于约束的规划是另一种面向大规模应用的问 大规模应用问题中被广泛采用」 题类型.Cestal7等人提出的DDL语言是基于约束 虽然HTN规划的提出和开发与STRIPS规划 的领域描述语言，用于描述复杂的物理系统.该方法 几乎同时8)，但其理论基础的建立却较晚. 以控制理论为基础，用变量描述系统的状态，用约束 Erol1o.)等人对HTN问题进行了较系统的理论 限制变量在某一时间段内的取值.计划的表现形式 研究，给出了如下一些基于谓词逻辑的形式化定义 实际上是一组控制事件的序列（图1(c) 定义6HTN规划领域是一个二元组D= 与STRIPS类和HTN类方法不同，这种问题 (Op,Me〉，其中Op为操作算子(operator)),Me为 类型的描述中没有明确定义动作或任务，而是将动 方法(method).操作算子是一个基本的操作行为模 作以“事件”形式隐含在系统状态变化的过程中，事 式，表示为Op=(h(v),Pre,E),其中h是包含了件可以认为是使变量值发生改变的一种动作.由于 输入参数列表v的原始任务名称，Pre是操作行为 事件的动作形式简单，采用隐含方式是可行的.对于 的执行条件，EfT是操作的执行效应.方法Me是将 动作类型多样，形式比较复杂的领域，仅仅依靠约束 非原始任务分解成子任务的规则，表示为Me=(a, 是不够的 d).其中a是一个非原始任务，d是任务网络 定义7任务网络结构表示为d=(m:) 2应用研究中的前沿领域 (m:)…m:tm)中1，其中m表示网络节点名称， 2.1求解规模问题 ,表示节点对应的任务，中是网络中各种约束条件 受“状态爆炸”的影响，求解规模一直是 的布尔表达式 STRIPS类规划问题的瓶颈，因此研究更加高效的 任务网络由原始任务(primary task)、非原始任 算法成为近年来STRIPS类规划研究的热点 务(nomprimary task)组成，非原始任务又可细分为 Blums1等人提出的图规划算法(graphplan)采 目标任务(goal task)和复合任务(compound 用规划图(planning graph)作为求解的辅助工具.规 task). 划图是一种描述规划问题状态演化的分层数据结 定义8原始任务do是一个不可再分解的基 构，求解过程是规划图不断按层展开的过程和基于 本任务，形式为do[f(x1,2,x],其中f是原 规划图的搜索过程的组合.由于在图层展开的过程 始任务谓词，x:是项.原始任务只能包含一个操作 中很好地删除了冲突的动作效果状态，使搜索空间 算子Op.复合任务perform是一个由任意数量的原 迅速下降，因此求解效率得到显著提高.F℉1算法 始任务或复合任务构成的任务，形式为perform 采用了启发式前向搜索策略代替了图规划算法中的 [1(x,x2,,x],其中1是复合任务谓词，x,是 全局搜索策略，进一步提高了搜索效率，成为目前最 项 有效的STRIPS类算法之一 从以上定义可以看出，方法Me的形式虽然是 由Kautz2o]等人提出的SAT算法将状态空间 通用的，但Me的构建却需要领域知识和经验.因 的搜索问题转化为命题满意性问题，使状态描述得 此求解的成功率和效率与领域知识有很大关系. 到简化，然后采用基于命题满意性的求解算法进行 Me的表达是HTN规划中智能的重要体现形式. 求解.虽然问题表达的转化会带来一定的信息损失， HTN描述语言主要有SHOp2、OCLh引、 但求解效率的显著提高仍使该算法成为另一重要的 TF4、ACT5]、AMLI6]等.SHOP是基于“海上搜 STRIPS类算法 救"”应用发展起来的HTN规划系统，其理论基础是 模型检验(model checking)是进行模型正确性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net(b) ) . 这种机制不仅可以方便地描述领域中的众多 抽象任务 ,而且可以描述任务、动作间的层次依赖关 系 ,适用于具有层次任务结构的规划领域. H TN 规 划可描述为一个三元组形式 D = < I , T ,Me > , 其 中 I 表示初始状态集合 , T 表示抽象任务的集合 , Me 表示任务分解策略的集合. 由于许多应用领域 的任务通常按层次结构组织和管理 , H TN 规划在 大规模应用问题中被广泛采用. 虽然 H TN 规划的提出和开发与 STRIPS 规划 几乎 同 时[8 - 9 ] , 但 其 理 论 基 础 的 建 立 却 较 晚. Erol [10 - 11 ]等人对 H TN 问题进行了较系统的理论 研究 ,给出了如下一些基于谓词逻辑的形式化定义. 定义 6 H TN 规划领域是一个二元组 D = 〈Op , Me〉,其中 Op 为操作算子 (operator) ,Me 为 方法(met hod) . 操作算子是一个基本的操作行为模 式 ,表示为 Op = ( h( v) ,Pre , Eff) ,其中 h 是包含了 输入参数列表 v 的原始任务名称 ,Pre 是操作行为 的执行条件 , Eff 是操作的执行效应. 方法 Me 是将 非原始任务分解成子任务的规则 ,表示为 Me = (α, d) . 其中α是一个非原始任务 , d 是任务网络. 定义 7 任务网络结构表示为 d = [ ( n1 ∶t1 ) ( n2 ∶t2 ) …( nm ∶tm )φ] ,其中 ni 表示网络节点名称 , ti 表示节点对应的任务 ,φ是网络中各种约束条件 的布尔表达式. 任务网络由原始任务(primary task) 、非原始任 务(non2primary task) 组成 ,非原始任务又可细分为 目标 任 务 ( goal task ) 和 复 合 任 务 ( compound task) . 定义 8 原始任务 do 是一个不可再分解的基 本任务 ,形式为 do [ f ( x1 , x2 , …, xk ) ] , 其中 f 是原 始任务谓词 , xi 是项. 原始任务只能包含一个操作 算子 Op . 复合任务 perform 是一个由任意数量的原 始任务或复合任务构成的任务 , 形式为 perform [ t( x1 , x2 , …, xk ) ] , 其中 t 是复合任务谓词 , xi 是 项. 从以上定义可以看出 ,方法 Me 的形式虽然是 通用的 ,但 Me 的构建却需要领域知识和经验. 因 此 ,求解的成功率和效率与领域知识有很大关系. Me 的表达是 H TN 规划中智能的重要体现形式. H TN 描述语言主要有 SHOP [ 12 ] 、OCLh [13 ] 、 TF [ 14 ] 、ACT [15 ] 、AML [16 ]等. SHOP 是基于“海上搜 救”应用发展起来的 H TN 规划系统 ,其理论基础是 Erol 等人的形式化定义. SHOP 用通用的 H TN 语 法结构描述不同领域的对象、状态、任务分解策略 , 形成了一种通用的 H TN 描述机制 ,成为不同领域 专用知识的建模基础. OCLh 则在领域描述中加入 了对对象分类的支持 ,使领域模型具有层次化结构. 113 基于约束的规划 基于约束的规划是另一种面向大规模应用的问 题类型. Cesta [17 ]等人提出的 DDL 语言是基于约束 的领域描述语言 ,用于描述复杂的物理系统. 该方法 以控制理论为基础 ,用变量描述系统的状态 ,用约束 限制变量在某一时间段内的取值. 计划的表现形式 实际上是一组控制事件的序列(图 1 (c) ) . 与 STRIPS 类和 H TN 类方法不同 ,这种问题 类型的描述中没有明确定义动作或任务 ,而是将动 作以“事件”形式隐含在系统状态变化的过程中. 事 件可以认为是使变量值发生改变的一种动作. 由于 事件的动作形式简单 ,采用隐含方式是可行的. 对于 动作类型多样 ,形式比较复杂的领域 ,仅仅依靠约束 是不够的. 2 应用研究中的前沿领域 211 求解规模问题 受“状 态 爆 炸”的 影 响 , 求 解 规 模 一 直 是 STRIPS 类规划问题的瓶颈 ,因此研究更加高效的 算法成为近年来 STRIPS 类规划研究的热点. Blum [ 18 ]等人提出的图规划算法 (grap hplan) 采 用规划图(planning grap h) 作为求解的辅助工具. 规 划图是一种描述规划问题状态演化的分层数据结 构 ,求解过程是规划图不断按层展开的过程和基于 规划图的搜索过程的组合. 由于在图层展开的过程 中很好地删除了冲突的动作效果状态 ,使搜索空间 迅速下降 ,因此求解效率得到显著提高. FF [19 ] 算法 采用了启发式前向搜索策略代替了图规划算法中的 全局搜索策略 ,进一步提高了搜索效率 ,成为目前最 有效的 STRIPS 类算法之一. 由 Kautz [20 ] 等人提出的 SA T 算法将状态空间 的搜索问题转化为命题满意性问题 ,使状态描述得 到简化 ,然后采用基于命题满意性的求解算法进行 求解. 虽然问题表达的转化会带来一定的信息损失 , 但求解效率的显著提高仍使该算法成为另一重要的 STRIPS 类算法. 模型检验(model checking) 是进行模型正确性 ·20 · 智 能 系 统 学 报 第 2 卷