第2卷第2期 智能系统学报 Vol.2 Na 2 2007年4月 CAAI Transactions on Intelligent Systems Apr.2007 智能规划研究综述 个面向应用的视角 宋泾舸，查建中，陆一平 (北京交通大学机械与电子控制工程学院，北京100044) 摘要：智能规划是智能系统研究的重要领域.在分析了智能规划中典型问题类型特征的基础上，从应用的视角对 智能规划研究的前沿问题以及近年来的主要理论与方法进行了评述.结合若干工业领域的应用实例，讨论了工程应 用中的规划问题特征及研究现状，并在此基础上结合智能工程理论对智能规划的应用研究方向进行了展望. 关键词：智能规划：问题类型：应用研究：工业领域；智能工程 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)02-001808 Survey on AI planning research-an application-oriented perspective SON GJing ge,CHA Jian-zhong,LU Yi-ping (School of Mechanical,Electronic and Control Engineering,Beijing Jiaotong University,Beijing 100044,China) Abstract:Intelligent planning is an important area in AI research.Based on characteristics of typical AI planning problems,some areas of applicationoriented planning theories and techniques are surveyed.Sig- nificant industrial planning problems are enumerated and their characteristics are discussed.Combining AI planning with Intelligence Engineering principles,potential directions for future research are explored. Key words:AI planning;types of planning;application research;industrial area;intelligence engineering 智能规划(AI planning)是用人工智能理论与 本文从智能规划的基本问题类型入手，分析了 技术自动或半自动地生成一组动作序列（或称一个 它们的描述机制和适用领域.然后从问题规模、领域 “计划”plan),用以实现期望的目标.智能规划是智 建模、不确定性、知识工程等4个方面对现代智能规 能系统理论与应用研究的重要分支，与基于遗传算 划理论和技术进行了综述.进而对几个工程领域的 法等智能方法的线性、非线性规划问题(program- 规划问题特征进行了分析，在此基础上结合智能工 ming)不同，动作排序是智能规划的主要任务 程的若干原则对智能规划的应用研究方向进行了展 近年来，随着信息技术的广泛应用以及海量信 望。 息的产生，自动、高效地处理大规模的事务成为新的 应用需求.同时，一些高效算法的提出也大大推动了 1规划问题的基本类型 智能规划的研究从经典问题向实际应用问题的转 按照不同的视角，规划问题有多种分类方法.从 移.一些集成的规划系统也在应用中发挥了一定作 应用角度看，不同领域对规划问题特征的需求有所 用.但是笔者注意到，目前的综述主要集中于理论方 不同，问题的描述也存在差异.因此按应用类型的不 面，而从应用角度的总结和分析较少.应用是理 同，规划问题的描述形式可归纳为3大类：STRIPS 论研究的动力和归宿，从应用的视角对当前智能规 规划、HTN规划和基于约束的规划. 划理论、方法与问题特征进行分析和总结是十分必 1.1 STRIPS规划 要的，这不仅有利于理论联系实际，也便于发现当前 STRIPSI5)规划起源于机器人研究领域，目的是 理论研究中的不足并推动其发展 对机器人的基本动作进行组合，以形成能够完成特 定目标任务的动作序列.STRIPS问题可描述为一 收稿日期：20060901. 基金项目：国家自然科学基金资助项目(50335040) 个三元组形式D=,其中I表示初始状 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
第 2 卷第 2 期 智 能 系 统 学 报 Vol. 2 №. 2 2007 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2007 智能规划研究综述 ———一个面向应用的视角 宋泾舸 ,查建中 ,陆一平 (北京交通大学 机械与电子控制工程学院 ,北京 100044) 摘 要 :智能规划是智能系统研究的重要领域. 在分析了智能规划中典型问题类型特征的基础上 ,从应用的视角对 智能规划研究的前沿问题以及近年来的主要理论与方法进行了评述. 结合若干工业领域的应用实例 ,讨论了工程应 用中的规划问题特征及研究现状 ,并在此基础上结合智能工程理论对智能规划的应用研究方向进行了展望. 关键词 :智能规划 ; 问题类型 ; 应用研究 ; 工业领域 ; 智能工程 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0220018208 Survey on AI planning research —an application2oriented perspective SON G Jing2ge , CHA Jian2zhong , L U Yi2ping (School of Mechanical , Electronic and Control Engineering , Beijing Jiaotong University , Beijing 100044 , China) Abstract :Intelligent planning is an important area in AI research. Based on characteristics of typical A I planning problems , some areas of application2oriented planning t heories and techniques are surveyed. Sig2 nificant industrial planning problems are enumerated and t heir characteristics are discussed. Combining A I planning with Intelligence Engineering principles , potential directions for f ut ure research are explored. Keywords :A I planning ; types of planning ; application research ; industrial area ; intelligence engineering 收稿日期 :2006209201. 基金项目 :国家自然科学基金资助项目(50335040) . 智能规划 (AI planning) 是用人工智能理论与 技术自动或半自动地生成一组动作序列 (或称一个 “计划”,plan) ,用以实现期望的目标. 智能规划是智 能系统理论与应用研究的重要分支 ,与基于遗传算 法等智能方法的线性、非线性规划问题 (program2 ming) 不同 ,动作排序是智能规划的主要任务. 近年来 ,随着信息技术的广泛应用以及海量信 息的产生 ,自动、高效地处理大规模的事务成为新的 应用需求. 同时 ,一些高效算法的提出也大大推动了 智能规划的研究从经典问题向实际应用问题的转 移. 一些集成的规划系统也在应用中发挥了一定作 用. 但是笔者注意到 ,目前的综述主要集中于理论方 面[1 - 4 ] ,而从应用角度的总结和分析较少. 应用是理 论研究的动力和归宿 ,从应用的视角对当前智能规 划理论、方法与问题特征进行分析和总结是十分必 要的 ,这不仅有利于理论联系实际 ,也便于发现当前 理论研究中的不足并推动其发展. 本文从智能规划的基本问题类型入手 ,分析了 它们的描述机制和适用领域. 然后从问题规模、领域 建模、不确定性、知识工程等 4 个方面对现代智能规 划理论和技术进行了综述. 进而对几个工程领域的 规划问题特征进行了分析 ,在此基础上结合智能工 程的若干原则对智能规划的应用研究方向进行了展 望. 1 规划问题的基本类型 按照不同的视角 ,规划问题有多种分类方法. 从 应用角度看 ,不同领域对规划问题特征的需求有所 不同 ,问题的描述也存在差异. 因此按应用类型的不 同 ,规划问题的描述形式可归纳为 3 大类 :STRIPS 规划、H TN 规划和基于约束的规划. 111 STRIPS 规划 STRIPS [ 5 ]规划起源于机器人研究领域 ,目的是 对机器人的基本动作进行组合 ,以形成能够完成特 定目标任务的动作序列. STRIPS 问题可描述为一 个三元组形式 D = , 其中 I 表示初始状
第2期 宋泾舸，等：智能规划研究综述—一个面向应用的视角 ·19· 态集合，A表示动作的集合，G表示目标状态集合 Dermott!1基于谓词逻辑提出的PDDL语言对领域 这类问题要求分别明确给出初始状态、动作特征以 对象、谓词、初始状态、目标、动作等规划元素进行了 及目标状态的描述，动作在这里被描述为一种改变 形式化，形成一种通用的描述机制.FoxM等人在 系统状态的行为，动作序列形成了系统状态的演变， PDDL2.1)中增加了对领域类型、数值描述、持续 如图1(a)所示 性动作、时间、目标函数(metric)等元素的支持，形 成了定性与定量相结合的机制，又在PDDL+版本 动作I动作2 初始状态 目标状态 中引入了对事件(event)和过程(process)的描述，将 动作3 领域描述从有限状态(finite state)的离散事件动态 (a)STRIPS规划 系统(DEDS)扩展到混杂系统(hybrid system),丰 富了STRIPS规划的适用领域.下面是PDDL2.1 初始状态 目标任务 对简单规划问题的一些主要定义 定义1简单规划问题实例可描述成一个二元 子任务引 子任务2 组D=(Dom,Prob),其中Dom是领域描述，Prob 是问题描述.领域可用四元组描述Dom=(Fs,Rs, 子任务3子任务4子任务一仔任务6 As,arity),其中Fs是函数符号的集合，Rs是关系 符号的集合，As是动作符号的集合，arity是函数涉 (b)HTN规划 及的变量的集合.问题描述为Prob=(Os,Init,G), 初始状态事件1·… 事件n 且标状态 其中Os是对象的集合，Init是初始状态，G是目标 状态 约束条件， 定义2原始数值表达式(PNEs)是由函数符 号与项(terms)形成的谓词结构.函数符号的作用对 (c)基于约束的规划 象是Os中的元素 图13类规划问题的描述 定义3原子(atms)是由关系符号与项形成的 Fig 1 The diagram of three types of Al planning problem 谓词结构.关系符号的作用对象是Os中的元素 最初的STRIPS描述对领域进行了多项假设， 定义4初始状态Init包括Initog和Initnumeric 形成了所谓的“经典问题”这些假设包括： 2部分，其中Initg是由Atms构成的符号命题的 1)静态性假设即除动作外的其他因素对环 集合，Initmumerie是由PNEs构成的数值命题的集合」 境状态不产生影响，动作是唯一改变世界状态的因 定义5动作符号表示为a=(Pre,Eff),a∈ 素； As.其中Pre是动作执行的前提条件，Eff是动作执 2)信息完全性假设求解所需的环境信息是 行的效应 完全的，即由这些信息可以完全了解环境的变化情 STRIPS类问题具有较坚实的理论基础，适用 况. 于目标状态能够明确描述且求解直接涉及基本的动 3)确定性假设—当动作执行的条件给定时， 作特征描述的问题.这样的问题通常规模较小或只 动作执行产生的效应是完全确定的； 涉及局部应用领域，目标状态容易准确观察和较方 4)动作独立性假设不同的动作间彼此独 便地描述，如机器人运动、无人驾驶运载工具 立，没有前后顺序上的依赖关系，只是通过上下文 (UAV)调度、货物仓储等问题 (context)形成了间接的联系 1.2HTN规划 5)间原子性假设不考虑动作执行的延时对 许多大规模、复杂应用领域，往往很难直接、快 执行效果的影响，即动作的效果不能按延时再细分 速地给出目标状态描述，于是一些学者提出了层次 解。 任务网(HTN)规划，HTN规划将目标状态用抽象 近年来，为了提高STRIPS类规划的应用范围， 的目标任务(task)替代，任务按照不同的抽象程度 些学者提出了改进的问题描述机制.例如，Mc 形成分层结构，原始动作处在HTN的最底层（图1 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
态集合 ,A 表示动作的集合 , G 表示目标状态集合. 这类问题要求分别明确给出初始状态、动作特征以 及目标状态的描述 ,动作在这里被描述为一种改变 系统状态的行为 ,动作序列形成了系统状态的演变 , 如图 1 (a) 所示. (a) STRIPS 规划 (b) H TN 规划 (c)基于约束的规划 图 1 3 类规划问题的描述 Fig11 The diagram of three types of AI planning problem 最初的 STRIPS 描述对领域进行了多项假设 , 形成了所谓的“经典问题”. 这些假设包括 : 1) 静态性假设 ———即除动作外的其他因素对环 境状态不产生影响 ,动作是唯一改变世界状态的因 素 ; 2) 信息完全性假设 ———求解所需的环境信息是 完全的 ,即由这些信息可以完全了解环境的变化情 况. 3) 确定性假设 ———当动作执行的条件给定时 , 动作执行产生的效应是完全确定的 ; 4) 动作独立性假设 ———不同的动作间彼此独 立 ,没有前后顺序上的依赖关系 ,只是通过上下文 (context) 形成了间接的联系. 5) 间原子性假设 ———不考虑动作执行的延时对 执行效果的影响 ,即动作的效果不能按延时再细分 解. 近年来 ,为了提高 STRIPS 类规划的应用范围 , 一些学者提出了改进的问题描述机制. 例如 , Mc2 Dermott [6 ]基于谓词逻辑提出的 PDDL 语言对领域 对象、谓词、初始状态、目标、动作等规划元素进行了 形式化 ,形成一种通用的描述机制. Fox M 等人在 PDDL211 [7 ]中增加了对领域类型、数值描述、持续 性动作、时间、目标函数 (metric) 等元素的支持 ,形 成了定性与定量相结合的机制 ,又在 PDDL + 版本 中引入了对事件(event) 和过程(process) 的描述 ,将 领域描述从有限状态(finite state ) 的离散事件动态 系统(DEDS) 扩展到混杂系统 ( hybrid system) ,丰 富了 STRIPS 规划的适用领域. 下面是 PDDL211 对简单规划问题的一些主要定义. 定义 1 简单规划问题实例可描述成一个二元 组 D = (Dom , Prob) ,其中 Dom 是领域描述 ,Prob 是问题描述. 领域可用四元组描述 Dom = (Fs , Rs , As , arity) , 其中 Fs 是函数符号的集合 ,Rs 是关系 符号的集合 ,As 是动作符号的集合 ,arity 是函数涉 及的变量的集合. 问题描述为 Prob = (Os ,Init , G) , 其中 Os 是对象的集合 ,Init 是初始状态 , G 是目标 状态. 定义 2 原始数值表达式 (PN Es) 是由函数符 号与项(terms) 形成的谓词结构. 函数符号的作用对 象是 Os 中的元素. 定义 3 原子(atms) 是由关系符号与项形成的 谓词结构. 关系符号的作用对象是 Os 中的元素. 定义 4 初始状态 Init 包括 Initlogical和 Init numeric 2 部分 ,其中 Initlogical是由 Atms 构成的符号命题的 集合 ,Init numeric是由 PN Es 构成的数值命题的集合. 定义 5 动作符号表示为 a = (Pre , Eff) , a ∈ As. 其中 Pre 是动作执行的前提条件 ,Eff 是动作执 行的效应. STRIPS 类问题具有较坚实的理论基础 ,适用 于目标状态能够明确描述且求解直接涉及基本的动 作特征描述的问题. 这样的问题通常规模较小或只 涉及局部应用领域 ,目标状态容易准确观察和较方 便地 描 述 , 如 机 器 人 运 动、无 人 驾 驶 运 载 工 具 (UAV) 调度、货物仓储等问题. 112 H TN 规划 许多大规模、复杂应用领域 ,往往很难直接、快 速地给出目标状态描述 ,于是一些学者提出了层次 任务网( H TN) 规划. H TN 规划将目标状态用抽象 的目标任务(task) 替代 ,任务按照不同的抽象程度 形成分层结构 ,原始动作处在 H TN 的最底层 (图 1 第 2 期 宋泾舸 ,等 :智能规划研究综述 ———一个面向应用的视角 ·19 ·
·20· 智能系统学报 第2卷 (b).这种机制不仅可以方便地描述领域中的众多 Erol等人的形式化定义.SHOP用通用的HTN语 抽象任务，而且可以描述任务、动作间的层次依赖关 法结构描述不同领域的对象、状态、任务分解策略， 系，适用于具有层次任务结构的规划领域.HTN规 形成了一种通用的HTN描述机制，成为不同领域 划可描述为一个三元组形式D=,其 专用知识的建模基础.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 表示任务分解策略的集合. 由于许多应用领域 的任务通常按层次结构组织和管理 , 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 卷
第2期 宋泾舸，等：智能规划研究综述—一个面向应用的视角 ·21· 检验的一种技术，在许多工程领域得到应用，如电 采用了有环谓词-变迁Petri网和有环着色Petri 路、通信协议、数字控制器的检验等.近年来，模型检 网.Kristensen!30]在军事运筹规划中用Petri网描述 验作为一种求解策略引起智能规划研究者的关注。 了“任务”，使领域描述支持了层次任务结构 基于二元判定图(BDD)的模型检验是采用较多的策 2.3不确定性问题 略.该方法用BDD模型表达系统状态和动作，降低 通过对经典问题假设的适当放宽形成了非经典 了表达的冗余度改善了求解效率.采用这类方法的 问题.不确定性规划是其中重要的分支，主要研究系 规划器主要有MBp2、UMOP2]MIPS23]等 统初始状态不确定和动作效果不确定对求解的影 虽然STRIPS类问题的求解效率和成功率得到 响.相容性(conformant)规划是研究初始状态信息 了大幅提高，但仍然不能胜任大规模问题.为了解决 不完整的不确定性规划问题3 更大规模的STRIPS规划问题，一些学者采用了元 对于动作的执行效果的不确定性，决策理论的 (meta)求解策略.FoxM等人在STAN424]中采用 应用是一种自然的选择.采用马尔可夫决策过程 了领域分析的策略，从领域描述中提取与求解相关 (MDPs)是一种主要的表达和求解]方法 的信息，忽略不相关的信息，将目标问题分解成子问 2.4知识的获取与运用问题 题，使状态空间缩小，然后采用适合的求解算法分别 引入领域知识被认为是提高系统实用性的必然 进行求解，最后对子问题解进行合成.WahB2s]等 选择).但是这也同时带来另外一些问题，例如，规 人在SGPlan中运用了基于扩展鞍点理论的子目标 模较大领域中知识获取比较困难；难于有效集成多 分割策略，大大提高了多目标STRIPS类问题的求 种类型的知识：过量的知识将增加计算量：知识的领 解效率和成功率 域相关降低了系统的通用性等 2.2领域建模问题 HTN规划虽然引入了领域知识，提高了问题 尽管人们己经对领域建模进行了大量研究，但 求解效率，但其领域知识的主要表现形式是任务的 从描述准确性和描述效率看，仍有许多领域问题不 能很好描述.一些学者认为，领域建模是影响规划系 分解策略.事实上，知识工程可以应用于规划系统的 不同层面，例如领域对象描述、任务和目标结构描 统应用性的十分重要的因素 目前的建模机制以命题式描述为主（如PD 述、搜索策略控制、计划质量评估、知识获取、知识管 理等.因此知识工程方法与智能规划的结合是近年 DL),其形式简单、通用性强.但命题描述更适合于 简单知识和浅层知识的描述，即领域知识必须明确 来的一个应用研究热点 给出，因此有时无法有效地描述复杂的和深层知识 本体论(ontology)是面向知识表达、共享、协同 例如对象具有空间关系的货物仓储问题，命题描述 的知识工程方法，在领域建模、知识集成与管理、协 必须明确指出货物间的摆放位置关系，货物量较大 同求解等方面为复杂领域的知识建模提供有力的支 时将使描述量变得很大.解决命题描述的“规模瓶 持.因而成为知识工程应用于智能规划的一个新方 颈”的一种途径是基于模型的描述.模型是描述领域 向！.机器学习是知识获取的重要方法之一，因而 对象及其关系的数据结构，通常以图结构的形式表 成为知识工程应用的另一个方向.近年来一些学者 现.模型描述将知识、约束隐含在模型中，使描述更 在这方面进行了探索，例如，Veloso1等人在prod 自然、有效 igy规划器中引入了学习机制，Yang Q34等人则用 自动机(automata)是一种应用广泛的工业系统 学习方法进行动作模式的获取 过程建模机制.一些学者26.21采用基于该模型的模 3工程中的规划问题 型检验方法进行规划问题求解，满足目标命题的模 型检验路径就是规划求解生成的计划.由于自动机 为了使智能规划研究更好地服务于实践，近年 模型中状态的改变以事件形式表现，在设计并行和 来一些学者提出将规划研究的案例重点从理想化、 不确定行为时描述能力受到限制.Petri网是另一种 小规模的“玩具”问题(toy problem)转向大规模、复 模型，对并行和异步行为有更强的表达能力.这方面 杂的现实世界问题(real-world problem),并提出了 目前仍在起步阶段，如Murata21和Mieller21分别 不同领域中的一些典型问题实例 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
检验的一种技术 ,在许多工程领域得到应用 ,如电 路、通信协议、数字控制器的检验等. 近年来 ,模型检 验作为一种求解策略引起智能规划研究者的关注. 基于二元判定图(BDD) 的模型检验是采用较多的策 略. 该方法用 BDD 模型表达系统状态和动作 ,降低 了表达的冗余度 ,改善了求解效率. 采用这类方法的 规划器主要有 MBP [21 ] 、UMOP [ 22 ] 、MIPS [23 ]等. 虽然 STRIPS 类问题的求解效率和成功率得到 了大幅提高 ,但仍然不能胜任大规模问题. 为了解决 更大规模的 STRIPS 规划问题 ,一些学者采用了元 (meta) 求解策略. Fox M 等人在 STAN4 [ 24 ] 中采用 了领域分析的策略 ,从领域描述中提取与求解相关 的信息 ,忽略不相关的信息 ,将目标问题分解成子问 题 ,使状态空间缩小 ,然后采用适合的求解算法分别 进行求解 ,最后对子问题解进行合成. Wah B [25 ] 等 人在 SGPlan 中运用了基于扩展鞍点理论的子目标 分割策略 ,大大提高了多目标 STRIPS 类问题的求 解效率和成功率. 212 领域建模问题 尽管人们已经对领域建模进行了大量研究 ,但 从描述准确性和描述效率看 ,仍有许多领域问题不 能很好描述. 一些学者认为 ,领域建模是影响规划系 统应用性的十分重要的因素. 目前的建模机制以命题式描述为主 (如 PD2 DL) ,其形式简单、通用性强. 但命题描述更适合于 简单知识和浅层知识的描述 ,即领域知识必须明确 给出 ,因此有时无法有效地描述复杂的和深层知识. 例如对象具有空间关系的货物仓储问题 ,命题描述 必须明确指出货物间的摆放位置关系 ,货物量较大 时将使描述量变得很大. 解决命题描述的“规模瓶 颈”的一种途径是基于模型的描述. 模型是描述领域 对象及其关系的数据结构 ,通常以图结构的形式表 现. 模型描述将知识、约束隐含在模型中 ,使描述更 自然、有效. 自动机(automata) 是一种应用广泛的工业系统 过程建模机制. 一些学者[26 - 27 ]采用基于该模型的模 型检验方法进行规划问题求解 ,满足目标命题的模 型检验路径就是规划求解生成的计划. 由于自动机 模型中状态的改变以事件形式表现 ,在设计并行和 不确定行为时描述能力受到限制. Petri 网是另一种 模型 ,对并行和异步行为有更强的表达能力. 这方面 目前仍在起步阶段 ,如 Murata [28 ] 和 Mieller [29 ] 分别 采用了有环谓词 - 变迁 Petri 网和有环着色 Petri 网. Kristensen [ 30 ]在军事运筹规划中用 Petri 网描述 了“任务”,使领域描述支持了层次任务结构. 213 不确定性问题 通过对经典问题假设的适当放宽形成了非经典 问题. 不确定性规划是其中重要的分支 ,主要研究系 统初始状态不确定和动作效果不确定对求解的影 响. 相容性 (conformant) 规划是研究初始状态信息 不完整的不确定性规划问题[31 ] . 对于动作的执行效果的不确定性 ,决策理论的 应用是一种自然的选择. 采用马尔可夫决策过程 (MDPs) 是一种主要的表达和求解[3 ]方法. 214 知识的获取与运用问题 引入领域知识被认为是提高系统实用性的必然 选择[2 ] . 但是这也同时带来另外一些问题 ,例如 ,规 模较大领域中知识获取比较困难 ;难于有效集成多 种类型的知识 ;过量的知识将增加计算量 ;知识的领 域相关降低了系统的通用性等. H TN 规划虽然引入了领域知识 ,提高了问题 求解效率 ,但其领域知识的主要表现形式是任务的 分解策略. 事实上 ,知识工程可以应用于规划系统的 不同层面 ,例如领域对象描述、任务和目标结构描 述、搜索策略控制、计划质量评估、知识获取、知识管 理等. 因此知识工程方法与智能规划的结合是近年 来的一个应用研究热点. 本体论(ontology) 是面向知识表达、共享、协同 的知识工程方法 ,在领域建模、知识集成与管理、协 同求解等方面为复杂领域的知识建模提供有力的支 持. 因而成为知识工程应用于智能规划的一个新方 向[32 ] . 机器学习是知识获取的重要方法之一 ,因而 成为知识工程应用的另一个方向. 近年来一些学者 在这方面进行了探索 ,例如 ,Veloso [33 ] 等人在 prod2 igy 规划器中引入了学习机制 , Yang Q [34 ] 等人则用 学习方法进行动作模式的获取. 3 工程中的规划问题 为了使智能规划研究更好地服务于实践 ,近年 来一些学者提出将规划研究的案例重点从理想化、 小规模的“玩具”问题 (toy problem) 转向大规模、复 杂的现实世界问题 (real2world p roblem) ,并提出了 不同领域中的一些典型问题实例. 第 2 期 宋泾舸 ,等 :智能规划研究综述 ———一个面向应用的视角 ·21 ·
·22 智能系统学报 第2卷 3.1供电故障恢复问题(PSR) 任何时间都必须充满管道.流体被视为不可压缩，即 供电故障恢复问题(power supply restoration, 任意时段内管道中输入的流体体积与流出的流体体 PSR)是由Thiebaux S3s)等人引入到智能规划领域 积要基本相等，不同种类的流体有接合面，但不能大 的一个工程问题.图2(a)所示的简化供电网络包括 量掺混.每一个区域对不同的流体的储存能力有一 电力线路和2类设备：断路器（大方块）、开关（小方 定限制.流体输送到指定区域有一定的时间限制，操 块).设备最多只能连接2条线路并且只有2种状 作行为的描述必须与相应作用管段的内部状态保持 态：“拉开”和“闭合”.断路器被视为电源，当它闭合 一致.这需要复杂的操作行为描述方法。 时，处于供电状态的线路一直延伸到处于拉开状态 Miliditú38]等人采用FF算法对该问题进行求 的开关设备.在预先设定的设备状态下，不同的断路 解，但规模只限于数量为4~5个区域和管道的问 器为不同的区域供电.图中黑色和灰色的线路分别 题.Hoffman则用MIPs进行了实验，对于具有存储 表示“供电”与“未供电”状态.“拉开”与“合上”是仅 能力和时间限制的某些问题尚不能很好地解决」 有的操作行为.当某段线路发生故障时，相关区域停 x供电线路 电，规划的任务是如何使停电区域尽可能恢复正常 工作 PSR问题的特点是当某线路或设备状态发生 变化时，相关的区域的线路通断状态将随之发生变 打开关闭 化.由于系统中的设备和线路数量通常很多，网络运 断路器 行状态多变，倒闸操作行为对系统状态的改变很难 用行为的效果状态直接准确描述，因此该问题存在 多种不确定性，如系统信息只能部分可观察（不完 (a)PSR 全)、系统信息获取的不确定性、动作执行效果的不 确定性等 A2 Bertoli!2I在MBP中采用通用规划方法进行求 S12 34 解，能够成功地对一些典型案例生成满足特定目标 B8 的 的应急恢复方案.Bonet!361在GPT中将规划目标转 B9B10 为故障代价的最小化问题，将优化方法引入了不确 定性规划.Jesen R3则用智能体(Agent)代替动作 S43 B7 (action),并加入了环境Agent用来描述规划过程 中环境状态的不确定性，从并行、对立(adversarial) 的角度丰富了PSR问题的描述和求解框架 (b)pipeworld 3.2管道输送问题(pipesworld) 该问题源于石油管道输送领域，反映了工程系 统中管网输送流体的规划问题.pipeworld问题通常 转炉#1 吊车#1 Q加工议备#传送带加工设备1加工没备#3 包括区域（如配送中心、港口、提炼厂等）和输送管 等 道.图2(b)是一个包含4个区域5条输送管道的管 Q工设备料传送带#2加T设备#5 0 转炉#2 吊车#2 网系统.管道中可能依次输送多种不同批量的流体， 物○ 如柴油、汽油、煤油等.“压入”(push)与“抽出” 停 铸造设备 (pop)是该问题的2个操作行为.规划的目标是制 0 定合理的流体输送操作计划，以满足应用、安全、经 (c)SIDMAR 济等方面的需求 图2工程中的规划问题 与传统运输问题不同，pipeworld问题的运输工 Fig 2 Planning problems in engineering 具（管道）是静止的，而货物是运动的.流体在运输的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
311 供电故障恢复问题(PSR) 供电故障恢复问题(power supply restoration , PSR) 是由 Thiébaux S [35 ]等人引入到智能规划领域 的一个工程问题. 图 2 (a) 所示的简化供电网络包括 电力线路和 2 类设备 :断路器 (大方块) 、开关 (小方 块) . 设备最多只能连接 2 条线路并且只有 2 种状 态“: 拉开”和“闭合”. 断路器被视为电源 ,当它闭合 时 ,处于供电状态的线路一直延伸到处于拉开状态 的开关设备. 在预先设定的设备状态下 ,不同的断路 器为不同的区域供电. 图中黑色和灰色的线路分别 表示“供电”与“未供电”状态.“拉开”与“合上”是仅 有的操作行为. 当某段线路发生故障时 ,相关区域停 电 ,规划的任务是如何使停电区域尽可能恢复正常 工作. PSR 问题的特点是当某线路或设备状态发生 变化时 ,相关的区域的线路通断状态将随之发生变 化. 由于系统中的设备和线路数量通常很多 ,网络运 行状态多变 ,倒闸操作行为对系统状态的改变很难 用行为的效果状态直接准确描述. 因此该问题存在 多种不确定性 ,如系统信息只能部分可观察 (不完 全) 、系统信息获取的不确定性、动作执行效果的不 确定性等. Bertoli [21 ]在 MBP 中采用通用规划方法进行求 解 ,能够成功地对一些典型案例生成满足特定目标 的应急恢复方案. Bonet [36 ]在 GPT 中将规划目标转 为故障代价的最小化问题 ,将优化方法引入了不确 定性规划.J esen R [37 ]则用智能体 (Agent) 代替动作 (action) ,并加入了环境 Agent 用来描述规划过程 中环境状态的不确定性 ,从并行、对立 (adversarial) 的角度丰富了 PSR 问题的描述和求解框架. 312 管道输送问题 (pipesworld) 该问题源于石油管道输送领域 ,反映了工程系 统中管网输送流体的规划问题. pipeworld 问题通常 包括区域 (如配送中心、港口、提炼厂等) 和输送管 道. 图 2 (b) 是一个包含 4 个区域、5 条输送管道的管 网系统. 管道中可能依次输送多种不同批量的流体 , 如柴油、汽油、煤油等.“压入”( p ush) 与“抽出” (pop) 是该问题的 2 个操作行为. 规划的目标是制 定合理的流体输送操作计划 ,以满足应用、安全、经 济等方面的需求. 与传统运输问题不同 ,pipeworld 问题的运输工 具(管道) 是静止的 ,而货物是运动的. 流体在运输的 任何时间都必须充满管道. 流体被视为不可压缩 ,即 任意时段内管道中输入的流体体积与流出的流体体 积要基本相等. 不同种类的流体有接合面 ,但不能大 量掺混. 每一个区域对不同的流体的储存能力有一 定限制. 流体输送到指定区域有一定的时间限制. 操 作行为的描述必须与相应作用管段的内部状态保持 一致. 这需要复杂的操作行为描述方法. Milidiú[38 ] 等人采用 FF 算法对该问题进行求 解 ,但规模只限于数量为 4～5 个区域和管道的问 题. Hoffman 则用 MIPS 进行了实验 ,对于具有存储 能力和时间限制的某些问题尚不能很好地解决. (a) PSR (b) pipeworld (c) SIDMAR 图 2 工程中的规划问题 Fig12 Planning problems in engineering ·22 · 智 能 系 统 学 报 第 2 卷
第2期 宋泾舸，等：智能规划研究综述—一个面向应用的视角 ·23· 3.3钢调度问题(SIDMAR) 能对机器的闲置作不确定地等待、操作没有固定的 该问题来自扁钢生产领域.领域对象包括转炉、 持续时间」 加工机器、吊车、传送带等如图2（©）所示，炼钢厂 目前该问题的研究成果较少，Fehnkerl2采用 包括2个转炉2个吊车5个加工设备、2条传送带 赋时自动机(timed automata)模型检验方法进行了 和1个铸造设备以及一些停放物料的位置.生铁从 初步的约束求解研究，能容易地添加拓扑和计时约 转炉进入加工生产线，经过多道工序后由铸造设备 束而无需改变底层算法但无法直接确定最小生产 送出.调度的任务是按要求的工序完成钢材的加工 时间。 领域中的操作动作包括物料的处理、吊起、移动、放 除上述用于研究的实例外，一些欧美国家在外 下等.规划的目标是制定满足要求的调度方案 层空间探索和军事信息化建设中研制出一些具有代 SIDMAR问题的特点是由于系统拓扑结构的 表性的集成规划系统，并在不同领域中发挥了一定 关系，某台机器上的某一操作往往使另一些机器上 的作用.表I对O-Plan、SIPE2和ASPEN系统进 的某些操作无法执行，而且存在资源的移动、任务不 行了初步归纳和对比。 表1应用型规划系统的应用模式与应用领域 Table 1 Application mode and domain of application planning system 规划系统 说明 应用模式 应用领域 集指挥、规划、控制于一体应急规划、自主规空战规划、盟军与多国部队的指挥与控制、协同搜 O-Plan4,391 的智能系统（英国） 划、资源调度. 救行动、无人驾驶载运工具的指挥与控制， SIPE-2U15,401 计划生成与执行结合的智应急规划、资源调空战规划、军事运筹规划、油井井喷事故应急规 能系统（美国SRD 度、过程规划 划、生产线调度规划、建筑规划 模块化、可配置、多领域的 资源调度、自主规 航天飞机的指令生成规划、星球探测器任务规划、 ASPENI16,411 规划系统（美因JPL) 划 地面站自动化、无人驾驶战机控制 4)结构化原则结构化的表达比命题式的表 4 研究展望 达更能反映系统的深层知识，更适合大规模人工系 从应用的视角看，同许多其他的计算技术相似， 统中应用问题的描述 目前的智能规划在通用性与高效性方面存在着冲 基于智能工程的指导思想和原则，笔者认为智 突，如何进行有效的协调是智能规划系统走向实用 能规划应该在如下几方面作进一步研究」 的关键 1)知识类型的分析和整理 智能工程是以人工智能的理论和技术为依托发 目前的规划系统根据不同的规划问题类型建立 展起来的计算机应用学科，是研究知识的自动处理 了多种知识描述.这些知识描述通用性强，但对一些 及应用理论和方法以及面对复杂问题建立集成化智 专门的领域则缺少更深入的形式化描述，使领域工 能软件系统的技术.近年的一些研究2242.指出 程师难以更好地介入知识建模过程.因此应结合不 了应用型智能系统的研究应遵循的若干原则，包括 同领域的特征，研究更深化、更有针对性和更易于领 领域相关原则、多机制原则、层次化原则、结构化原 域专家理解的知识分类与表达 则等 2)基于多模型的领域描述机制 1)领域相关原则领域无关方法不能很好地 近年来，不同的领域建模研究产生了多种建模 适应特定领域的实际问题； 方法，但目前的智能规划研究主要基于单一的建模 2)多机制原则一没有单一的方法能够解决现 机制，尚缺少对这些建模方法的全面、有效的利用 实世界中的应用问题： 因此应结合领域知识的特征对现有建模机制进行全 3)层次化原则—层次化的系统结构是处理大 面的对比研究并进行组织，建立多模型结合的建模 规模复杂问题的有效途径： 方法.虽然不同领域有其各自的特点，但许多人工系 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
313 钢厂调度问题 (SIDMAR) 该问题来自扁钢生产领域. 领域对象包括转炉、 加工机器、吊车、传送带等. 如图 2 (c) 所示 ,炼钢厂 包括 2 个转炉、2 个吊车、5 个加工设备、2 条传送带 和 1 个铸造设备以及一些停放物料的位置. 生铁从 转炉进入加工生产线 ,经过多道工序后由铸造设备 送出. 调度的任务是按要求的工序完成钢材的加工. 领域中的操作动作包括物料的处理、吊起、移动、放 下等. 规划的目标是制定满足要求的调度方案. SIDMAR 问题的特点是由于系统拓扑结构的 关系 ,某台机器上的某一操作往往使另一些机器上 的某些操作无法执行 ,而且存在资源的移动、任务不 能对机器的闲置作不确定地等待、操作没有固定的 持续时间. 目前该问题的研究成果较少 ,Fehnker [ 27 ] 采用 赋时自动机(timed automata) 模型检验方法进行了 初步的约束求解研究 ,能容易地添加拓扑和计时约 束而无需改变底层算法. 但无法直接确定最小生产 时间. 除上述用于研究的实例外 ,一些欧美国家在外 层空间探索和军事信息化建设中研制出一些具有代 表性的集成规划系统 ,并在不同领域中发挥了一定 的作用. 表 1 对 O2Plan、SIPE22 和 ASPEN 系统进 行了初步归纳和对比. 表 1 应用型规划系统的应用模式与应用领域 Table 1 Application mode and domain of application planning system 规划系统 说明 应用模式 应用领域 O2Plan [14 ,39 ] 集指挥、规划、控制于一体 的智能系统(英国) 应急 规 划、自 主 规 划、资源调度. 空战规划、盟军与多国部队的指挥与控制、协同搜 救行动、无人驾驶载运工具的指挥与控制. SIPE22 [15 ,40 ] 计划生成与执行结合的智 能系统(美国 SRI) 应急 规 划、资 源 调 度、过程规划. 空战规划、军事运筹规划、油井井喷事故应急规 划、生产线调度规划、建筑规划. ASPEN [16 ,41 ] 模块化、可配置、多领域的 规划系统(美国 J PL) 资源 调 度、自 主 规 划. 航天飞机的指令生成规划、星球探测器任务规划、 地面站自动化、无人驾驶战机控制. 4 研究展望 从应用的视角看 ,同许多其他的计算技术相似 , 目前的智能规划在通用性与高效性方面存在着冲 突 ,如何进行有效的协调是智能规划系统走向实用 的关键. 智能工程是以人工智能的理论和技术为依托发 展起来的计算机应用学科 ,是研究知识的自动处理 及应用理论和方法以及面对复杂问题建立集成化智 能软件系统的技术. 近年的一些研究[ 2 ,24 ,42 - 44 ] 指出 了应用型智能系统的研究应遵循的若干原则 ,包括 领域相关原则、多机制原则、层次化原则、结构化原 则等. 1) 领域相关原则 ———领域无关方法不能很好地 适应特定领域的实际问题 ; 2) 多机制原则 ———没有单一的方法能够解决现 实世界中的应用问题 ; 3) 层次化原则 ———层次化的系统结构是处理大 规模复杂问题的有效途径 ; 4) 结构化原则 ———结构化的表达比命题式的表 达更能反映系统的深层知识 ,更适合大规模人工系 统中应用问题的描述. 基于智能工程的指导思想和原则 ,笔者认为智 能规划应该在如下几方面作进一步研究 : 1) 知识类型的分析和整理 目前的规划系统根据不同的规划问题类型建立 了多种知识描述. 这些知识描述通用性强 ,但对一些 专门的领域则缺少更深入的形式化描述 ,使领域工 程师难以更好地介入知识建模过程. 因此应结合不 同领域的特征 ,研究更深化、更有针对性和更易于领 域专家理解的知识分类与表达. 2) 基于多模型的领域描述机制 近年来 ,不同的领域建模研究产生了多种建模 方法 ,但目前的智能规划研究主要基于单一的建模 机制 ,尚缺少对这些建模方法的全面、有效的利用. 因此应结合领域知识的特征对现有建模机制进行全 面的对比研究并进行组织 ,建立多模型结合的建模 方法. 虽然不同领域有其各自的特点 ,但许多人工系 第 2 期 宋泾舸 ,等 :智能规划研究综述 ———一个面向应用的视角 ·23 ·
·24· 智能系统学报 第2卷 统在对象、关系、状态、过程、行为等方面存在相似 [8]TA TE A.Generating project networks [A].In Proceed- 性，这将成为更全面、更深入的领域描述机制建立的 ings of UCAI-77[C].Boston,Mass,USA,1977 基础 [9]SACERDOTI E.A Structure for Plans and Behavior 3)从元层次研究协同的求解策略 M].New York:Elsevier,1977. [10]EROL K,HENDL ER J,NAU D.Semantics for hier- 多策略的协同求解是应用智能系统的重要求解 archical task-network planning[R].CS TR-3239,UMI 策略.从元层次进行策略的协同应成为一个重要的 ACS TR-94-31,ISR TR-95-9,University of 研究方向.虽然元层次的求解已经在规划研究中得 Maryland,1994. 到应用，但仍然在起步阶段，目前尚无比较系统的研 [11]EROL K,HENDL ER J,NAU D.HTN planning: 究，尤其是利用元知识进行协同求解的研究.基于元 complexity and expressivity [A ]In Proceedings of 知识的求解策略研究将为多求解策略的建立、维护、 AAAF94 [C].Seattle,USA,1994. 扩展提供顶层的方法和指导 [12]NAU D,AU T,IL GHAMI O,et al.SHOP2:an 5结束语 HTN planning system[J ]JAIR,2003,20:379-404. [13 ]SIMPSON R,MCCLUSKEY T,LIU D,et al.Knowl- 综上所述，智能规划是兼具理论和应用价值的 edge representation in planning:a PDDL to OCLh trans- 研究领域，经过多年的发展，其研究与应用已经涉及 lation [A].ISMIS2000 [C].Charlotte,USA,2000. 到众多的领域，形成了多种理论体系并在实践中得 [14]TATE A,DRABBLE B,DAL TON J.O-plan:a 到体现.但在大规模、复杂领域中，目前的理论和方 knowledge-based planner and its application to logistics [A].Advanced Planning Technology[C].Morgan Kauf- 法还远远不够.面向实际应用问题是充分应用现有 mann,1996. 理论、技术并提出新的理论问题的重要途径.应用研 [15]WIL KINS D.Using the SIPE2 planning system:a 究应该结合应用领域的问题特征进行，并将知识在 manual for version 6.0[M].SRI International Artificial 多角度、多层面的运用作为提高系统实用性的关键 Intelligence Center.Menlo Pork.California.1999. 技术进行全面、深入的研究，并应注重多种知识的集 [16]CHIEN S,RABIDEAU G.ASPEN-automated planning 成与协同 and scheduling for space mission operations [A ] SpaceOps2000 [C].Toulouse,France,2000. 参考文献： [17]CESTA A,ODDI A.A representation language for do- [1]WELD D.Recent advances in AI planning[J ]AI Maga- main knowledge in planning architectures [A].In Pro- ine,1999,20(2):93-123. ceedings of KAW-96 [C].Alberta,Canada,1996. [2]WIL KINS D,DESJARDINS M.A call for knowledge- [18]BLUM A,FURST M.Fast planning through planning based planning [J ]AI Magazine,2001,22(1):99. graph analysis [A].In Proceedings of DCAF95 [C]. 115. Quebec,Canada,1995. [3]BL YTHEJ.An overview of planning under uncertainty [19]HOFFMANNJ.FF:the fast-forward planning system [J].A1 Magazine,1999,20(2):37-54. [U].AI Magazine,2001,22(3):57-62. [4]ZIMMERMAN T,KAMB HAMPA TI S.Learningas- [20]KAUTZ H,SEL MAN B.Pushing the envelope:plan sisted automated planning [J ]AI Magazine,2003,24 ning,propositional logic,and stochastic search [A ]In (2):73-96. Proceedings of AAAF96 [C].Portland,USA,1996. [5 ]FIKES R,NILSSON N.Strips:a new approach to the [21]BERTOLI P,CIMATTIA,SLANEYJ,et al.Solving application of theorem proving to problem solving [J]. power supply restoration problems with planning via Artificial Intelligence,1971,2(3,4):189-208. symbolic model checking [A].In Proceedings of ECA102 [6]MCDERMOTT D.PDDL-the planning domain definition [C].Lyon,France,2002. language EB/OL ]www.cs.yale.edu./homes/dvm, [22 ]J ENSEN R,VELOSO M.OBDD-based deterministic 1998-05.10. planning using the UMOP planning framework [A ]In [7]FOX M,LONGD.PDDL2.1:an extension to PDDL for Proceedings of AIPS-00 Workshop on Model-Theoretic expressing temporal planning domains [J ]Journal of AI Approaches to Planning [C].Breckenridge,USA, Research,2003,20:61-124 2000. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
统在对象、关系、状态、过程、行为等方面存在相似 性 ,这将成为更全面、更深入的领域描述机制建立的 基础. 3) 从元层次研究协同的求解策略 多策略的协同求解是应用智能系统的重要求解 策略. 从元层次进行策略的协同应成为一个重要的 研究方向. 虽然元层次的求解已经在规划研究中得 到应用 ,但仍然在起步阶段 ,目前尚无比较系统的研 究 ,尤其是利用元知识进行协同求解的研究. 基于元 知识的求解策略研究将为多求解策略的建立、维护、 扩展提供顶层的方法和指导. 5 结束语 综上所述 ,智能规划是兼具理论和应用价值的 研究领域 ,经过多年的发展 ,其研究与应用已经涉及 到众多的领域 ,形成了多种理论体系并在实践中得 到体现. 但在大规模、复杂领域中 ,目前的理论和方 法还远远不够. 面向实际应用问题是充分应用现有 理论、技术并提出新的理论问题的重要途径. 应用研 究应该结合应用领域的问题特征进行 ,并将知识在 多角度、多层面的运用作为提高系统实用性的关键 技术进行全面、深入的研究 ,并应注重多种知识的集 成与协同. 参考文献 : [1 ]WELD D. Recent advances in AI planning[J ]. AI Maga2 zine , 1999 ,20 (2) : 93 - 123. [2 ]WIL KINS D , DESJ ARDINS M. A call for knowledge2 based planning [J ]. AI Magazine , 2001 , 22 ( 1) : 99 - 115. [3 ]BL YTHE J. An overview of planning under uncertainty [J ]. AI Magazine , 1999 ,20 (2) : 37 - 54. [4 ] ZIMMERMAN T , KAMB HAMPA TI S. Learning2as2 sisted automated planning [J ]. AI Magazine , 2003 , 24 (2) : 73 - 96. [5 ] FIKES R , NILSSON N. Strips: a new approach to the application of theorem proving to problem solving [J ]. Artificial Intelligence , 1971 , 2 (3 ,4) : 189 - 208. [6 ]MCDERMO TT D. PDDL2the planning domain definition language [ EB/ OL ]. www. cs. yale. edu. / homes/ dvm , 1998 - 05 - 10. [ 7 ]FOX M , LON G D. PDDL2. 1 : an extension to PDDL for expressing temporal planning domains [J ]. Journal of AI Research , 2003 , 20 : 61 - 124. [8 ] TA TE A. Generating project networks [A ]. In Proceed2 ings of IJCAI - 77[C]. Boston , Mass , USA , 1977 [9 ] SACERDO TI E. A Structure for Plans and Behavior [ M ]. New York : Elsevier , 1977. [10 ] EROL K , HENDL ER J , NAU D. Semantics for hier2 archical task2network planning[ R]. CS TR23239 , UMI2 ACS TR - 94 - 31 , ISR - TR - 95 - 9 , University of Maryland , 1994. [11 ] EROL K , HENDL ER J , NAU D. H TN planning : complexity and expressivity [ A ]. In Proceedings of AAAI294 [C]. Seattle , USA , 1994. [ 12 ] NAU D , AU T , IL GHAMI O , et al. SHOP2 : an H TN planning system[J ]. J AIR , 2003 ,20 :379 - 404. [ 13 ]SIMPSON R , MCCLUSKEY T , L IU D , et al. Knowl2 edge representation in planning : a PDDL to OCLh trans2 lation [A ]. ISMIS’2000 [C]. Charlotte , USA , 2000. [14 ] TA TE A , DRABBL E B , DAL TON J. O2plan : a knowledge 2based planner and its application to logistics [ A ]. Advanced Planning Technology[C]. Morgan Kauf2 mann , 1996. [15 ]WIL KINS D. Using the SIPE22 planning system : a manual for version 6. 0 [ M ]. SRI International Artificial Intelligence Center. Menlo Pork. California. 1999. [16 ]CHIEN S , RABIDEAU G. ASPEN2automated planning and scheduling for space mission operations [ A ]. SpaceOps2000 [C]. Toulouse , France , 2000. [17 ]CESTA A , ODDI A. A representation language for do2 main knowledge in planning architectures [ A ]. In Pro2 ceedings of KAW296 [C]. Alberta , Canada , 1996. [18 ]BLUM A , FURST M. Fast planning through planning graph analysis [ A ]. In Proceedings of IJCAI295 [ C ]. Quebec , Canada , 1995. [19 ] HOFFMANNJ. FF : the fast2forward planning system [J ]. AI Magazine , 2001 ,22 (3) : 57 - 62. [20 ] KAU TZ H , SELMAN B. Pushing the envelope : plan2 ning , propositional logic , and stochastic search [ A ]. In Proceedings of AAAI296 [C]. Portland , USA , 1996. [21 ]BERTOL I P , CIMA TTI A , SLAN EYJ , et al. Solving power supply restoration problems with planning via symbolic model checking [ A ]. In Proceedings of ECAI02 [C]. Lyon , France , 2002. [22 ]J ENSEN R , V ELOSO M. OBDD2based deterministic planning using the UMOP planning framework [ A ]. In Proceedings of AIPS200 Workshop on Model2Theoretic Approaches to Planning [ C ]. Breckenridge , USA , 2000. ·24 · 智 能 系 统 学 报 第 2 卷
第2期 宋泾舸，等：智能规划研究综述—一个面向应用的视角 ·25 [23]EDEL KAMP S,HELMERT M.Mips-model checking model-based diagnosis and repair planning [A].In Pro- integrated planning system [J ]AI Magazine,2001,22 ceedings of UAI [C].Portland,USA,1996. (3):67-72. [36]BONET B,THIEBAUX S.GPT meets PSR [A].In [24]FOX M,LONG D.STAN4:A hybrid planning strate- Proceedings of ICAPS-03 [C].Trento,Italy,2003. gy based on subproblem abstraction[J].AI Magazine, [37]J ENSEN R.Efficient BDD-based planning for nomrde- 2001,22(3):81-84. terministic,fault-tolerant,and adversarial domains[D]. [25]WAH B,CHEN YX.Partitioning of temporal planning Pittsburgh:Carnegie Mellon University,2003 problems in mixed space using the theory of extended [38]MILIDIA R,LIPORACE F,LUCENA C.Pipesworld: saddle points [A].In Proceedings of ICTA12003 [C]. pipeline transportation of petroleum derivatives [A ]In Sacramento,USA,2003. Proceedings of ICAPS-03 Workshop on the Competition [26]HUNE T,LARSEN K,PETTEERSSON P.Guided [C].Trento,Italy,2003. synthesis of control programs using UPPAAL for VHS [39]AIAI.www.aiai.ed.ac.uk/~oplan/documents/index. case study 5[R].VHS deliverable in workpackage CS. html.2007-01-15. 1999-01.01. [40 ]SRI.http:/www.ai.sri.com/~sipe/.2000-05-24. [27]FEN HNKER A.Scheduling a steel plant with timed [41]J PL.www-aig.jpl.nasa.gov/public/planning/aspen/. automata [A].In Proceedings of the Sixth International 2006.06-22. Conference on Real-Time Computing Systems and Appli- [42]VITTORINI V,IACONO M,MAZZOCCA N,et al. cations [C].Hong Kong,China,1999. The OsMoSys approach to multrformalism modeling of [28]MURATA T,NEL SON P.A predicate-transition net systems [J].Software and System Modeling,2004,3 model for multiple agent planning [J ]Information Sci- (1):68-81. ences,1991(57.58):361-384. [43]查建中.智能工程[M].北京：机械工业出版社，1992. [29]MIELL ER Y,FABIANI P.Planning with petri nets [44]周济，查建中，肖人彬.智能设计[M].北京：高等教 [A].In Proceedings of RJCIA-2000 [C].Lyon,France, 有出版社，1998. 2000. 作者简介： [30]KRISTENSEN L,MITCHELL B,ZHAN GL,et al. Modeling and initial analysis of operational planning 宋泾舸，男，1969年生，讲师，博士 processes using coloured petri nets [A].In Proceedings 研究生，主要研究方向为智能规划、工 of Formal Methods in Software Engineering and Defence 业系统建模智能工程等。 Systems [C].Adelaide,Australia,2002. Email jgsong @bjtu.edu.cn. [31 ]BRAFMAN R,HOFFMANN J.Conformant planning via heuristic forward search:a new approach [A ]In 查建中，男，1947生，教授，博士生 Proceedings of ICAPS-04 [C].Whistler,Canada,2004. 导师，主要研究方向为智能制造与设 [32]MCCLUSKEY T,CRESSWELL S.Importing ontology 计、智能工程.联合国教科文组织产学 information into planning domain models [A].In Pro- 合作教席首席教授，机械工程学会理 ceedings of ICAPS-05 Workshop on the Role of Ontology 事，机械设计学会常务理事，承担国家 in Planning and Scheduling[C].Monterey,USA,2005. 科学基金和攻关项目20多项，获奖3 [33]VELOSO M,CARBON ELL J,PEREZ A,et al.In 项.发表学术文章200多篇，出版专著 tegrating planning and learning:the PRODIGY architec- 2部. ture [J ]Journal of Theoretical and Experimental AI, E mail jzcha @center.njtu.edu.cn. 1995,7(1):81-120. [34]YANG Q,WU K,JIANG Y.Learning action models 陆一平，男，1965生，副教授，博 from plan examples with incomplete knowledge [A].In 士，主要研究方向优化设计、智能工程、 Proceedings of ICAPS-2005 [C].Monterey,USA, CAD/CAM等，发表论文30余篇 2005. Email:yplu @bjtu.edu.cn. [35]THIEBAUX S,CORDIER M,et al.Supply restoration in power distribution systems a case study in integrating 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
[23 ] EDEL KAMP S , HELMERT M. Mips 2 model checking integrated planning system[J ]. AI Magazine , 2001 , 22 (3) : 67 - 72. [24 ] FOX M , LON G D. STAN4 : A hybrid planning strate2 gy based on subproblem abstraction [J ]. AI Magazine , 2001 , 22 (3) : 81 - 84. [25 ]WA H B , CHEN YX. Partitioning of temporal planning problems in mixed space using the theory of extended saddle points [ A ]. In Proceedings of ICTAI2003 [ C ]. Sacramento , USA , 2003. [26 ] HUN E T , LARSEN K , PETTEERSSON P. Guided synthesis of control programs using U PPAAL for V HS case study 5 [ R]. V HS deliverable in workpackage CS. 1999 - 01 - 01. [27 ] FEN HN KER A. Scheduling a steel plant with timed automata [ A ]. In Proceedings of the Sixth International Conference on Real2Time Computing Systems and Appli2 cations [C]. Hong Kong , China , 1999. [28 ] MURA TA T , N ELSON P. A predicate2transition net model for multiple agent planning [J ]. Information Sci2 ences , 1991 (57 - 58) :361 - 384. [29 ] MIELL ER Y , FABIANI P. Planning with petri nets [A ]. In Proceedings of RJCIA22000 [C]. Lyon , France , 2000. [30 ] KRISTENSEN L , MITCHELL B , ZHAN G L , et al. . Modeling and initial analysis of operational planning processes using coloured petri nets [ A ]. In Proceedings of Formal Methods in Software Engineering and Defence Systems [C]. Adelaide , Australia , 2002. [31 ]BRAFMAN R , HOFFMANN J. Conformant planning via heuristic forward search : a new approach [ A ]. In Proceedings of ICAPS204 [C]. Whistler , Canada , 2004. [ 32 ]MCCL USKEY T , CRESSWELL S. Importing ontology information into planning domain models [ A ]. In Pro2 ceedings of ICAPS205 Workshop on the Role of Ontology in Planning and Scheduling[C]. Monterey , USA , 2005. [33 ]V ELOSO M , CARBONELL J , PEREZ A , et al. In2 tegrating planning and learning : the PRODIGY architec2 ture [J ]. Journal of Theoretical and Experimental AI , 1995 , 7 (1) : 81 - 120. [34 ] YAN G Q , WU K , J IAN G Y. Learning action models from plan examples with incomplete knowledge [ A ]. In Proceedings of ICAPS22005 [ C ]. Monterey , USA , 2005. [35 ] THIEBAUX S , CORDIER M , et al. Supply restoration in power distribution systems2a case study in integrating model2based diagnosis and repair planning [ A ]. In Pro2 ceedings of UAI [C]. Portland , USA , 1996. [36 ]BON ET B , THIEBAUX S. GPT meets PSR [ A ]. In Proceedings of ICAPS203 [C]. Trento , Italy , 2003. [37 ]J ENSEN R. Efficient BDD2based planning for non2de2 terministic , fault2tolerant , and adversarial domains[D ]. Pittsburgh :Carnegie Mellon University ,2003. [ 38 ]MIL IDI! R , L IPORACE F , LUCENA C. Pipesworld : pipeline transportation of petroleum derivatives [ A ]. In Proceedings of ICAPS203 Workshop on the Competition [C]. Trento , Italy , 2003. [39 ]AIAI. www. aiai. ed. ac. uk/ ～oplan/ documents/ index. html. 2007 - 01 - 15. [40 ]SRI. http :/ / www. ai. sri. com/ ～sipe/ . 2000 - 05 - 24. [41 ]J PL . www2aig. jpl. nasa. gov/ public/ planning/ aspen/ . 2006 - 06 - 22. [42 ]VITTORINI V , IACONO M , MAZZOCCA N , et al. The OsMoSys approach to multi2formalism modeling of systems [J ]. Software and System Modeling , 2004 , 3 (1) : 68 - 81. [43 ]查建中. 智能工程[ M]. 北京 :机械工业出版社 , 1992. [44 ]周 济 ,查建中 ,肖人彬. 智能设计[ M ]. 北京 :高等教 育出版社 , 1998. 作者简介 : 宋泾舸 ,男 ,1969 年生 ,讲师 ,博士 研究生 ,主要研究方向为智能规划、工 业系统建模、智能工程等. E2mail : jgsong @bjtu. edu. cn. 查建中 ,男 ,1947 生 ,教授 ,博士生 导师 , 主要研究方向为智能制造与设 计、智能工程. 联合国教科文组织产学 合作教席首席教授 ,机械工程学会理 事 ,机械设计学会常务理事 ,承担国家 科学基金和攻关项目 20 多项 , 获奖 3 项. 发表学术文章 200 多篇 ,出版专著 2 部. E2mail : jzcha @center. njtu. edu. cn. 陆一平 ,男 , 1965 生 , 副教授 ,博 士 ,主要研究方向优化设计、智能工程、 CAD/ CAM 等 , 发表论文 30 余篇. E2mail : yplu @bjtu. edu. cn. 第 2 期 宋泾舸 ,等 :智能规划研究综述 ———一个面向应用的视角 ·25 ·
