第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,A,G>,其中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 ,A , G > , 其中 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=<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 卷
第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 卷