第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 ·