（计算机软件与理论专业论文）基于延迟部分推理的快速前向规划系统.pdf

摘要 智能规划是人工智能的重要研究领域之一。用启发式搜索技术求解智能规划问题成 为近年来的研究热点。 “快速前向规划系统”( f f ) 是启发式搜索技术应用于规划领域的一个成功范例。f f 通过忽略动作的删除效果，使用放松图规划( r e l a x e dg r a p h p l a n ) 提供的启发信息引导 加强爬山算法( e n f o r c e dh i l l c l i m b i n g ) ，在s t r i p s 规划域中显示出优异的性能。在 a d l 域，f f 使用i p p 方法处理带有条件效果的动作。这样的处理方法导致放松图规划引 导的加强爬山算法在a d l 域求解时经常失败。本文指出，此问题的原因在于放松图规划 无法处理组件之间存在的诱导关系从而不能提供足够的有用动作。我们设计了 d p r n c e p g f f 智能规划系统，以解决发现的问题。d p r n c e p g f f 采用一个我们称之为在 朴素的条件效果规划图上进行延迟部分推理( d p r n c e p g ) 的方法提取启发信息。在此方 法中，我们虽然考虑所有动作的删除效果，但是只计算动作的组件之间限定范围内的诱 导组件互斥关系。初步的实验结果显示，在a d l 域，加强爬山算法在d p r n c e p g 的引导 下，求解的质量和求解的速度都明显提高。 目前的启发函数设计思想大都基于完全忽略动作的删除效果。本文的工作指出，即 使考虑动作的一部分删除效果，也可以有助于提高启发函数对于搜索的引导效率。本文 的工作有助于提高依赖于剪枝技术的启发式状态空间搜索规划器在a d l 域问题上的求解 能力。 关键词：智能规划；启发式搜索；朴素条件效果规划图；延迟部分推理 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 ! 学位论文作者签名；蕊础 日期：趔。堕疆 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即：东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：慈煎赵 指导教师签名： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 引言 近年来，智能规划成为人工智能的一个研究热点。研究者所关注的规划问题从逻辑 表示的、确定的、离散时间步的、具有严格约束的问题逐渐扩展到逻辑和数值共同表示 的、不确定的、时序的、具有非严格约束的问题。解决不同类型规划问题的方法也相继 出现。由于具有快速求解的特性，启发式搜索方法被应用在各种类型的规划系统中，成 为智能规划研究的重要方向。 在十几年的时间里，很多规划方法被相继提出。其中最重要的方法之一是b l u m 和 f u r s t 在1 9 9 5 年提出的基于规划图分析的快速规划系统。其他研究者也提出了不同的 方法：k a u t z 等人将规划图转化为可满足问题( s a t ) ，设计了b 1 a c k b o x 规划系统，通 过使用快速的s a t 求解器解决s t r i p s 规划问题”“”“1 ；其他一些研究者尝试将规划问题 转化为约束可满足问题( c s p ) 并利用已有的c s p 求解技术，扩展了规划器的求解能力 和速度。1 ”3 ；e d e l k a m p 等人将模型检测方法应用于规划，进行了获取较优的规划解的探 索”1 。1 ；b o n e t 等人使用启发式搜索方法求解规划并设计了领域无关的启发函数，在求 解非最优规划方面表现出极大的优势。“。 随着规划问题的扩展，能够处理这些扩展的规划器也随之出现：处理不确定性问题 的概率规划器1 n 4 1 、感知规划器1 、一致规划器呲m ；处理时序和资源 约束的时序规划器。”“；处理非严格约束的灵活规划器”。 启发式状态空间搜索技术可以应用于多种类型规划问题的求解。但是，不同的搜索 算法和启发函数的结合在不同类型的规划问题中的效果存在很大差别。启发式搜索算法 在人工智能的搜索领域已经有大量研究。“。在搜索领域，启发函数都是问题相关的；然 而，对于领域无关的规划器，最需要的是领域无关的启发函数。因此，许多研究者提出 了领域无关的启发函数设计方法。例如h s p 方法。1 ，f f 方法“，模式数据库，因果图 嘲等。 相对于1 9 9 5 年以前的智能规划求解系统，现代规划系统无论在规划求解规模上还 是在规划求解效率上都有数量级的提高。基于启发式搜索的快速前向规划求解系统 f a s t f o r w a r d ( f f ) 是其中表现最为优异的智能规划系统之一，获得了2 0 0 0 年的国际 智能规划竞赛的冠军，在2 0 0 2 年国际智能规划竞赛中f f 在s t r i p s 规划域和n u m e r i c 规划域的表现同样最为优异o 。f f 系统的核心技术是利用放松图规划( r e l a x e d g r a p h p l a n ，r g p ) 模块提供有用动作和状态的启发值来引导加强爬山算法( e n h a n c e d h i l 卜c l i m b i n g ) 。虽然根据放松图规划获取的启发式信息和有用动作不能保证规划求解 的完备性，但是在几乎所有的s t i r i p s 规划问题中，放松图规划提供的有用信息足以引 导加强爬山算法取得成功，其原因由h o f f m a n n 在文 2 6 ， 2 7 ， 2 8 中进行了详尽的 1 种能够刻画、模型化一个实际问题的规划问题定义语言成为了规划技术应用的关键。 1 9 9 6 年e p e d n a u l t ”。提出了动作描述语言a d l ( a c t i o nd e s c r i p t i o nl a n g u a g e ) 。 a d l 除了具有s t r i p s 的表达能力外，还能表达条件效果、量化效果等语言特征。1 9 9 8 年d r e wm c d e 瑚o t t ”提出了规划领域定义语言( p 叩l ) 。p d d l 逐渐地成为国际智能规 划比赛( i n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n ，i p c ) 的公认标准。p d d l 语言不仅给出 了规划问题定义的语法，也从语义的角度给出了规划的定义。p d d l 语言是不断发展的， 目前，它的表达能力已经非常强，能够刻画规划问题的时间和数值方面的属性，能够表 达用户对于规划的衡量标准。并且，从规划研究的历史上可以看出，1 殳时间内，规划 语言的表达能力超出了当时的规划器所能处理的表达能力，因此，p d d l 给规划器的发 展提出了挑战，指明了规划研究的发展方向。规划语言也是规划领域的一种交流和沟通 的标准：对于不同的规划器，我们可以通过它们对同一规划问题的处理能力和速度来进 行比较。为了后文的需要，这里我们简要介绍一下s t r i p s 语言和a d l 语言。 1 z 1s i i p s s t r i p s 本来是一个非常著名的规划器，它代表“斯坦福研究委员会问题求解器”。 s t r i p s 系统在智能规划发展中具有划时代的意义，因为它使得规划可以非常容易地进 行描述和操作。规划问题的一种简单的形式化方法是定义三个输入：( 1 ) 用某种形式语 言描述的初始状态；( 2 ) 用某种形式语言描述的目标；( 3 ) 用某种形式语言描述允许执行 的动作，这个描述通常被称为域理论( d o m a i nt h e o r y ) 。 s t r i p s 语言的是基于数理逻辑的表示方法。它的表达能力弱于一阶逻辑，因为在 s t r i p s 语言中不包含全称量词、存在量词和函数符号。它用一系列基文字来描述域的 初始状态，并且将目标定义为一个合取命题公式，所有满足目标的状态将被同等地考虑。 在s t r i p s 表示中，每个动作用一个合取前提和合取结果来描述，它们定义了从一个状 态到另一个状态的转移函数。动作可以在满足前提公式的任何状态s 中执行：执行的结 果是状态s 加上动作的结果；在合并过程中，矛盾的基文字被删除。 1 2 2a d l 采用s t r i p s 式语言描述的经典规划问题具有一定的限制条件，即动作的前提是命 题的合取，动作的结果也是命题的合取，时间被离散地表示，动作既不能创建新的客观 对象，也不能消灭已有的客观对象。并且，动作一旦执行，其执行的结果是确定的。这 种规划描述语言对多数现实世界问题不能全面描述，甚至对有些闯题根本无法描述，不 能满足一些实际问题的模型化需求。所以，要解决此类现实问题必须设计新的领域描述 语言。 1 9 9 6 年，e p e d n a u l t 提出了动作描述语言一一a d l ( a c t i o nd e s c r i p t i o n l a n g u a g e ) 。a d l 对s t r i p s 进行了扩展，除了具有s t r i p s 的表达能力外，还能表达 条件效果、量化效果等语言特征。条件效果是动作描述中上下文相关 ( c o n t e x t d e p e n d e n t ) 的效果，一般用w h e n 子句来表示。w h e n 子句由两部分构成： d 前提和结论，动作执行后，当w h e n 子句的前提也同时被满足时，才生成结论中的结果； 量化效果是允许在动作的效果描述中出现存在量词和全称量词。a d l 的扩展使得规划语 言所能描述的问题更多，解决了很多以前无法求解的问题。但是，a d l 仍然存在不能完 全表达客观世界的不足。p d d l 语言在继承它的基础上继续发展，不断增加可以刻画资 源约束、时序约束等存在于现实世界规划问题中的属性。 1 3 规划器 规划器是一个问题求解器，它以给定的规划问题为输入，输出解决这个给定问题的 一个或多个( 可能0 个) 规划解。规划器大致包括三个模块：输入处理模块，问题求解 模块和结果输出模块。输入处理模块组合了词法分析和语法分析的功能以及将问题描述 转化为规划器的内部数据表示的功能。因为给定的问题都是使用规划定义语言描述的， 所以输入处理模块的分析能力限制着规划器求解问题的范围。比如，只能处理s t r i p s 语言的规划器就不能求解由a d l 语言描述的问题。问题求解模块是规划器的核心模块， 它的设计取决于使用哪种方法求解规划，可以是基于状态空间的启发式搜索也可以是基 于规划空间的启发式搜索，或者是基于c s p 模型求解方法。有的规划器还使用不只一个 问题求解方法。结果输出模块负责输出规划解和其他相关信息。 步k 1 实现了子目标集，则时间步k 的目标集也就可以实现了；如果时间步 k - 1 的子目标集没能实现，g r a p h p l a n 再次为时间步k 的目标集合寻找其他的动 作集合，直到该子目标集被实现或证明k 命题层的初始目标集不能被实现。总 体来说，g r a p h p l a n 试图从长度为k 的规划图中搜索规划解，当搜索失败时规 划图从第k 层扩展到第k + 1 层。规划图可以编码为a d c s p ( a c t i v i t y b a s e d d v a m i cc o n s t r a 砬s a t i s f a d i o np r o b l e m ) 问题【”，互斥关系传播对应于约束满足 问题中的有向的部分一元一致约束传播和部分有向的二元致性约束传播【”。 一个规划图的a d c s p 编码可以利用任何适用于d c s p 问题的求解方法来解决 ( g r a p h p l 如的回溯搜索就是一个例子) 也可以通过将a d c s p 问题转化为c s p 问题进行求解。 g r a p h p l a n 解的晟优性：g r a p h p l a i l 算法可以保证搜索到从时间步的数量来说是 最佳的规划解( 即时间步最少) 。因为图规划的求解方法类似于i d a 算法。但 是，如果从规划所包含的动作数来考虑最佳性的话，则需要从串行规划图来考 虑。 串行规划图( s e r i a l p l 唧i 1 1 9g r a p h ) 是指在规划图中同一层上的任意一对非n 0 0 p 动作之间都是互斥的规划图。 规划图稳定( 1 e v e io f f ) ：如果一个规划图的相邻两层完全相同，即两个相邻层 的动作列、命题列以及互斥关系完全相同，则称该规划图达到稳定状态。 规划图的性质： ( 1 ) 实现一对命题所需的动作数不少于规划图中两个命题以非互斥关系出现的 最小命题列的索引； ( 2 ) 任意一对静态互斥的命题不可能同时出现在从初始状态出发可以到达的状 态； ( 3 ) 规划图达到稳定时的所有动作的集合包含了所有适用于从初始状态出发可 到达状态的动作； 2 ) 放松图规划( r e l a 【e dg 翔p h p i a ) 放松的规划图是对应于放松的规划问题建立的。在放松的规划图中，因为忽略了动 作的删除效果，任何一对命题节点之间不存在互斥关系，任何一对动作节点之间也不存 在互斥关系。放松规划问题和放松规划图具有如下性质： 命题1 ：设p 7 = 徊，j ，g ) 是一个放松的s t r r p s 任务，根据p 建立的规划图 将不包含任何命题互斥或者动作互斥。( 在原g r a p h p u n 中互斥的定义：两个命题互 斥的条件是这两个命题的所有支持动作都互斥动作互斥的条件是：互相删除对方的添 加效果或前提，两个动作的前提互斥) 命题2 ： 设p = ( d 。， j ，g ) 是一个放松的s t r 口s 任务，g r a p h p u 州根据p 进行解搜索的过程中不必回溯。 定理l ：设p = ( d7 ，j ，g ) 是一个放松的s t r i p s 任务，其中任何动作的最长 1 0 添加列表的长度是l ，则g i u p 阳p u 小可以在以l ，i d ll ，l 为参数的多项式时间 内找到一个解。 图规划算法在放松规划图上进行求解就得到一个放松规划： ，其 中o i 是在时间步i 选择的并行动作集合，m 是第一次所有目标均出现的时间步。 1 ) 状态s 的启发值 在f f 的放松图规划启发式方法中，状态5 的启发值定义为：从s 出发到达目标状 态的规划解的串行长度： 0 ) - 瑚，。一ld f i 。 2 2 6 模式数据库法( p a t t e r nd a t a b a s e s ，p d b s ) 模式数据库方法来源于模型检测领域，在刚被提出时，它是曼哈顿距离启发式的一 种推广形式，对应于把每个格子移到其目标位罱这样的子问题的解。p d b s 被表示为一 个查找表( l o o k u pt a b l e ) ，查找表的每一项存储着一个格子在板上的某一位置到达目 标位置的距离估计。因为假设子问题之间是相互独立的，这样，把每个格子到对应的目 标位置的最小距离估计相加得到的和作为整个状态到达目标的距离估计仍然是一个可 纳的估计。后来的p d b s 同时考虑一些格子：它们同时到达目标的距离估计也被存储在 一个查找表中，这些距离估计是在假设所有其他的格子都不存在的情况下进行计算的。 通常，p d b s 的计算由抽象目标开始，使用系统的后向搜索方法进行。若一个抽象状态 在回退搜索的路径上，就可以计算出这个抽象状态到达抽象目标的距离。 下面我们简要介绍一下抽象( a b s t r a c t i o n ) “。a b s t r a c t i o n 改变一个给定的搜索 空间s 的描述，产生一个简化的搜索空间s 。若一个搜索空间s 满足：a ) 对于每个s 中的状态都存在一个s7 中的对应状态；b ) 在搜索空间s 中，任何两个状态之间的距离 大于或者等于它们在s 中的对应状态之间的距离，则称空间s 为空间s 的一个抽象。这 样，在状态空间s 中的两个状态s 。和s 。的距离就可以通过它们在s 中的对应状态s 。和 s ：7 之间的精确距离进行估计。 我们可以把从s 到s7 的抽象表示为一个映射：s s7 ，用妒g ) 表示s 中的状态s 在s 中的对应状态，用如( 庐( s ) ，庐( g ) ) 表示在抽象空间s 中妒( s ) 到妒( g ) 的精确距离。这 样一个模式数据库可以表示为对应于砂的对偶集合： p d b ( 妒) = ( s ，6 壬( 妒( s ) ，( g ) ) ) ls s 。 e d e l k a m p ”1 使用了模式数据库的思想解决规划问题。这种思想相当于通过对动作的前提 和效果进行同时的放松来获取启发信息。近来的研究工作扩展到考虑同时使用多个模式 数据库，以及在模式数据库的存储空间代价和搜索的时间代价之间如何进行权衡“。 2 2 7 因果图法( c a s u a ig r a p h c g ) 在大多数规划系统的状态模型中，状态变量一般是布尔型的。例如，以第一章提到 的积木世界问题为例，变量“积木a 在地板上( o n t a b l e ( a ) ) ”可以取真和假两个值。 但是，因果图法采用了一个状态变量具有多个可能值的表示方法。h e l m e r t 在文渊中将 儿 因果图启发式应用于状态空间搜索。他首先把一个s t r i p s 语言描述的规划任务转化为 一个s a s “1 规划任务，然后基于s a s + 规划任务建立每个状态变量的域转移图( d o m a i n t r a n s i t i o ng r a p h ，d t g ) 和表达所有状态变量之间相互关系的因果图( c a s u a lg r a d h ) ， 最终在域转移图和放松的因果图上进行推理以获取启发式估计。在s a s + 规划任务中，状 态变量“积木a 的位置”可以有多个取值。变量的域转移图是一个有向图，图的顶点表 示变量的可能取值，两个顶点之间用多条有向边表示此变量可以从一个取值转变为取另 一个值，每条有向边用可以进行这种取值转变的条件( 条件根据某个可以引起这个转变 的s a s + 操作得到) 进行标记。例如，因为表示“积木a 的位置”的变量可以有三个取值： “在地板上”，“在积木b 上”，“被机器手臂抓着”。这样，对应于变量“积木a 的位置” 的域转移图中包括三个顶点，对应于“被机器手臂抓着”的顶点到对应另外两个值的顶 点分别有一条有向边，但是，对应于“在地板上”的顶点和对应“在积木b 上”的顶点 不存在有向边，因为这两个顶点之间的转变不能由任何一个s a s + 操作单独完成。关于所 有变量的因果图也是一个有向图。其中的顶点对应状态变量，两个顶点之间有一个有向 边表示它们之间存在相互关系。因果图是根据s a s + 操作建立的。根据因果图的定义方法， 其中存在环路。环路增加了处理的复杂性。可以通过忽略s a s + 动作的前提来去除环路。”。 实际上，在文 2 5 中，因果图启发式是根据无环因果图计算的，需要比较低的计算代价， 为搜索算法快速地扩展节点提供了基础。 3 1f f 规划系统概述 第三章f f 规划系统 倒1f f 的基本系统结构 f f 的基本系统结构见图1 。它采用加强爬山算法( e n f o r c e dh i l 卜c l i m b i n g ) 作为主要的搜索算法，使用放松图规划作为主要的启发式信息产生模块。f f 的输入 是p 叻l 语言描述的域模型和问题实例。加强爬山算法不断产生状态，并将这些状态 发送给放松图规划模块以获取启发信息。放松图规划模块以加强爬山模块提供的状 态s 为初始状态求解一个到目标状态的放松规划，并把求得的放松规划的长度作为 状态s 到目标状态的距离估计反馈给加强爬山模块，同时反馈的还有对于状态s 到 达目标状态有帮助的动作。值得指出的是，f f 在求解问题之前首先对目标进行排序 “：把目标分解为多个目标子集，计算这些子集实现的先后顺序。在求解过程中， 排在前面的目标子集被完成之后才考虑完成排在后面的目标子集。 3 2 启发函数的定义 如前所述，一个状态j 的启发值定义为由放松图规划求得的从状态s 到目标状 态的放松规划所包含的动作数目。放松图规划的规划提取过程见图2 。 3 3 加强爬山算法( e n f o r c e dh i l l 一c l i m b i n g ) 加强爬山算法是爬山算法的一种变形，它的提出是基于对爬山算法搜索空间的 简单结构的考虑。使用启发式前向状态空间搜索求解规划时，搜索空间由所有由初 始状态可达的状态和这些状态的启发式估计组成。正如h o f f m a n n 在文“”中指出：使 用爬山算法时，搜索空间具有简单的结构，局部最小和高原的面积一般很小。对于 任一状态，它的具有严格的较好启发式估计的后继状态通常是在几步之内可以被找 到。 1 3 f o r f ：= 1 ，md o g i ：= g gil a y e 卜m e m b e r s h i p 穗) = l e d f b r f o r l ：= m ，1d o f o r a l l g g i ，g n d t m a r k e da s t r u e a t t i m e f d o s c l e c t 卸a c t i o ndw i mg a d d ( d ) ，l a y e rm e m b e r s h i pf - 1 蛐dm i n i m a ld i f f i c u l t y f o ra 1 1 ，p r e c ( o ) ，l a ”r - m e m b e r s h i p 善0 ，n o tm a r k e dt r u ea td m ej - ld o g j 肾眦i | l b c b h 蝴：= g l a y c m b c 袖晰) u ， e n d f b r f o ra l l ，a d d ( d ) d o m a r k ，a s t r u e a t t i m e s fa n da t t i m e s 1 e n d f b r e d f o r e n d f b r 图2 放松图规划的规划搜索算法 i n i t i a l i z et 1 1 ec u r r e n tp l a nt ot h ee m p t yp l a l l s ：= j w 砸i l e 御0 d o s t a n i n g f o ms ，p e r f o mb r e a d mf i r s t a r c hf o fas t a t c w i t h 囟0 御， a v o i d i n g 陀p e a t e ds t a t e su s i n gah a s ht a b l e ， d 0n o te x p e n d i n gs t a t e s s “w h e r c b 一。 i f n os u c hs t a t ec a nb ef b u n d t l i e n f a i l e n d i f a d d t h ea c t i o n s o t h e p a t l l t 0s a t t l l ee n d o f t l l ec u r r e n tp l a n s ：= e n d w h i l e o u t p u tc u r r e c tp l a n ，s u c c e e d 图3 加强爬山算法 加强爬山算法的描述见图3 。和爬山算法相同，加强爬山算法也从初始状态开 始搜索。在面对一个中间状态s 时，算法通过从状态s 开始进行宽度优先搜索寻找 它的最近的较好后继，如果采用这个策略但无法找到s 的较好后继，则整个算法失 败， 3 4 剪枝策略 状态空间搜索面临的普遍问题是搜索空间的指数级别增长，因此f f 系统采用了 多种剪枝策略。下面简略予以介绍。 3 4 1 选择最有希望的节点进行扩展 加强爬山算法的效率不仅得自于放松图规划提供的距离估计，而且得益于放松 图规划提供的有用动作( h e l p f u l ea c t i o n s ) 。状态s 的有用动作定义为：h 0 ) 一( 口 ip r e ( 口) s ，a d d ( 口) ng 0 ) ，o ) 。其中g 。( s ) 表示在放松图规划模块根据状 态s 进行规划求解时在放松规划图的第一命题列所生成的子目标。有用动作就是那 些可以添假g ，( s ) 中某个命题并且在状态s 中可以应用的动作。加强爬山算法在以宽 度优先方式为状态s 寻找较好后继的过程中，任一状态的后继状态都由这个状态对 应的有用动作进行扩展。容易看出，状态s 的有用动作是适用于状态s 的动作的子 a c 伽s ： n a m e ( p r e ，a d d ，d e l ) o p a t = ( a ， a ， b ) o p a 2 = ( p ，t a ，g ) o p p a = ( o ， p a ha ) o p b l = ( o ， b ， a ) o p b 2 = ( ( p b ，f b ，o ) o p p b = ( g ， p b ) o ) ，：( b ) ，g ：( a ，b b ) c 图4 采用有用动作策略导致搜索失败 集，因此，有用动作的使用起到减少分枝因子( b r a n c hf a c t o r ) 的作用。实践表明， f f 使用有用动作策略在s t r i p s 规划域非常有效，但是，我们的工作指出，在a d l 规划域，由于f f 处理a d l 动作的方法导致了有用动作的剪枝过度，从而导致加强爬 山算法搜索经常失败。 采用有用动作策略进行搜索时，加强爬山搜索不能保证完整性，即，加强爬山 搜索算法有可能无法求解某些可解问题。这样的例子可以参见图4 。例如，在状态 ( b ) 时选取有用动作o p a ，转移到状态 a ) ，在状态 a 时选取有用动作o p b ，转移 到状态 b ) ，规划器发现 b ) 已经被估价过，从搜索空间中排除此状态，之后发现搜 索空间为空，搜索失败。 3 4 2 删除过早添加的目标 多个目标之间存在完成的先后顺序。即，在一个目标集合中有的目标应该在其 他一些目标之前完成。删除过早添加的目标的思想是，如果目标g 已经完成，但其 后的目标在完成的过程中必须暂时删除g ，则认为g 应该被推迟完成。 f f 采用如下的判断方法识别应该被推迟完成的目标：对于垤日，如果 g r a p h p l a n 为s 搜索得到的放松规划p 中包含一个删除g 的动作，那么将5 从搜索 第四章基于部分延迟推理的快速前向规划系统 4 1 背景 f f 系统的核心技术是利用放松图规划( r e l a x e dg r a p h p l a n ，r g p ) 模块提供有用动 作和状态的启发值来引导加强爬山算法( e n h a n c e dh i l l c l i m b i n g ) 。虽然根据放松图规 划获取的启发式信息和有用动作不能保证规划求解的完备性，但是在几乎所有的 s t i r i p s 规划问题中，放松图规划提供的有用信息足以引导加强爬山算法取得成功，其 原因由h o f f m 叽n 在文 2 6 ， 2 7 ， 2 8 中进行了详尽的理论和实践分析。然而，在a d l 规划问题中f f 的表现并不突出；放松图规划提供的有用动作往往使得加强爬山算法无 法搜索到存在解的空间，在有些规划域中，例如“b r i e f c a s ew o r l d ”域，加强爬山搜 索算法几乎在所有的问题上都会失败。 该问题的发生并非是域相关的，f f 在加强爬山搜索阶段失败的原因主要在于f f 系 统在提高处理a d l 动作的效率的同时也提高了处理过程的复杂性。目前处理a d l 动作的 三种方法有全扩展法( f u l le x p a n s i o n ) 啪1 ，i p p 方法1 和分枝扩展法( f a c t o r e d e x p a n s i o n ) 。”。第一种方法适合于在系统运行时( r u n t i m e ) 使用，后两种方法由于节省 空间适合在系统运行前使用。f f 采用了i p p 方法。但是，i p p 方法和分枝扩展法同样需 要比全扩展法更复杂的处理过程，因为这两种方法处理a d l 动作的结果内部存在新的相 互关系诱导关系。在f f 系统中，放松图规划完全忽略了这种诱导关系，从而无法 给出引导加强爬山算法扩展到解空间的有用动作，最终导致f f 系统的效率低下。 在f f 系统的基础上，我们设计了d p r n c e p g f f 智能规划系统。在d p r n c e p g f f 中， 我们使用朴素条件效果规划图( n a i v ec o n d i t i o n a 卜e f f e c t sp l a n n i n gg r a p h ，n c e p g ) 来替代放松规划图，并在n c e p g 上采取我们称之为延迟部分推理( d e l a y e dp a r t l y r e a s o n i n g ) 的方法为加强爬山搜索提供有用动作和有效的启发式信息，进而求解a d l 域 中的规划问题。实验结果表明，在“b r i e f c a s ew o r l d ”域问题中，我们的方法不仅可 以完全避免加强爬山失败，而且在效率上比之f f 也有成倍的提高，事实上，在大多数 a d l 规划问题中，我们的算法较之f f 都有显著的改善。 4 2f f 规划系统的局限性 在图1 所示的f f 规划系统的主要结构中，放松图规划模块是f f 系统的核心模块之 一，它一方面为系统提供当前状态到目标状态的估计值，一方面为加强爬山搜索提供有 用动作以裁减未搜索的状态空间。f f 通过使用目标排序方法降低问题求解难度，使用 放松图规划模块提供的信息引导搜索，并利用不完备的加强爬山搜索快速求解规划，只 t a l ( e o u t 和d u t i n ，分别表示移动公文包，取出包内物品，向包内放置物品。其中m o v e 动作是条件效果动作：当包内有物品时，该物品会随着包的移动而移动。 在“b r i e f c a s ew o r l d ”类问题中，f f 的加强爬山搜索即使在最简单的问题上也会失败。 例如，某个规划问题的初始状态为物品。在公文包内( i o ) ，公文包在l 地( i s a tl ) ，问 题的目标状态为物品。在l 地( a t ol ) ，公文包在l 1 地( i s a tl 1 ) 。在求解该问题时，f f 首先通过放松图规划模块获取初始状态的启发值和有用动作。图8 给出了该问题的放松 规划图的基本结构，其中虚线表示n 0 0 p 动作。当放松规划图扩展到第一命题层时，所 有的目标命题已经出现，图扩展过程结束。放松图规划模块根据n o o p 优先的原则以及 具有最小难度的动作优先原则【1 0 】，得到一条放松规划( m o v ell 1 ) ，并反馈给加强爬山 模块如下信息：当前状态到达目标状态的距离是1 ，有用动作是( m o v e ll 1 ) 。加强爬山 模块应用动作( i n o v ell 1 ) ，转移到状态：公文包和物品。在k 地。由于该状态不是目 标状态，系统再次调用放松图规划模块。放松图规划模块再次反馈给加强爬山模块如下 信息：当前状态到达目标状态的距离仍然是1 ，有用动作是( m o v el 1l ) 。加强爬山模块 发现经由动作( m o v el 】l ) 转移到的状态不比当前状态好，因此进行宽度优先搜索寻找估 计值小于1 的状态，结果发现经过有用动作可达的搜索空间中没有估计值更好的状态， 报告加强爬山搜索失败。 事实上，从初始状态出发，只要使用动作( t a k e 0 u to ) 取出物品。再使用动作( m o v el l 1 ) ，就可以到达目标状态。放松图规划只能发现有用动作( 妇o v ell 1 ) 的原因是它只考 察了组件( m o v e oll 1 ) 的一个效果( i s a tl 1 ) 而没有发现执行组件i7 1 ( m o v e oll 1 ) 会触发组 件( m o v e lll 1 ) 的执行，从而产生效果( a tol 1 ) 。如果它能够发现( a tol 1 ) 和目标( a tol ) 相冲突，在执行动作( m o v ell 1 ) 之前把物品。从公文包中取出，就可以正确地引导加强 爬山算法。然而，忽略动作的全部删除效果使得这种推理变得不可能。 4 3 朴素条件效果规划图上的延迟部分推理 4 3 1 处理具有条件效果的规划动作 和s t r i p s 语言相比，a d l 语言具有更强的知识表达能力，可以描述更为复杂的世 界模型。其特点在于允许在逻辑表达式中使用全称量词和条件效果。目前处理条件效果 的主要方法主要有三种，其一为全扩展方法ue x p a s i o n ) ，其二为f f 采用的口p 扩展 方法，其三为w e l d 等人介绍的分枝扩展( f a c t ( r 唧a i l s i o n ) 方法。全扩展法的不足在于扩 展之后的动作数目随着问题中涉及的对象数目呈指数级增长，后两者从本质上是相同 的，生成的动作数模目相对于涉及的对象数目线性增长。在本文，我们采用的是第三种 方法，即基于分枝扩展的处理方法。分枝扩展的主要思想是将动作所有的效果条件化， 每个效果产生一个动作组件( c o m p o n e n t ) ，一个组件由两部分构成：前提( a n t e c e d e n t ) 和结 果( c 叫s e q u c n t ) 。组件的前提是它所来自( 属于) 的动作的前提和条件效果的前提的合取， 组件的结果就是对应的条件化效果。例如，在图9 a 中的这个简单规划问题中，一个m o v e 动作被分枝扩展法处理为如图9 b 所示的三个组件。我们称组件( m o v e o1 01 1 ) 来自( 属于) 动作( m o v el o1 1 ) 。 2 0 ( d c n n e ( p f o b l e mb d e f c a - e x a 加p l e ) ( ：d o m a i nb 打e 6 s c w o r i d ) ( ：o b j c c t sk1 1 一l o c a t i o n o l p o n a b l c ) ( ：i n i i ( a to o u ( 醅a 1 ) ) ( ：g l ( a n d ( a to 。1 1 ) ( i s - a t l 0 ) ) ) ) n a m e ：( m o v e 01 01 1 ) p t c ：( i s a l 蛐 一( i s - a t1 1 ) a d d ：o s - a t l l ) ，( i s a tk ) n a m e ：( m o v 0 11 01 1 ) p r c a s a t u 一( i s a i l l ) o n0 0 ) a d d ：( i s a t l l ) 一( i s - a t l o ) ( a t0 0 1 1 ) ，( a t0 0 1 0 ) n a m e ：( m o v 0 2bl t ) p m ：( i s - a t1 0 ) ，( i s - a l1 1 ) g n0 1 ) a d d ：( i s _ a t l l ) ，( i s a t l 0 ) ( a t o l l l ) ，( a t 0 1 u 图9 a 一个公文包问题 图9 b 动作( m o v e1 01 1 ) 的三个组件 虽然i p p 方法和分技扩展方法可以显著地减少动作规模，但同时也会带来规划图扩 展和搜索的复杂性，其主要原因是诱导关系的存在【l “。第一，在图的扩展过程中我们在 动作的每个组件上进行推理，而不是在动作上推理；但求得的规划解是由动作构成，而 不是由组件构成。这使得在规划图建立的过程中，需要使用更复杂的规则来定义组件间 的互斥关系。第二，在规划求解过程中，我们必须通过否定某个组件的前提以抵制多个 组件之间由于相互诱导而出现的消极作用。 4 3 2 朴素条件效果规划图 在d p r n c e p g f f 系统中，我们利用在朴素条件效果规划图上进行延迟部分推理 p r n c e p g ) 来获取启发式信息。我们知道，在设计启发式函数时有两个最为重要的 因素需要考虑。其一为启发式函数的可纳性。与放松图规划相似，d p r n a j p g 所提供 的启发式函数是不可纳的。但是由于考虑到了组件之间的相互关系，我们的启发式函数 具有更多信息，因此d p r - n c e p g f f 求得的规划解更接近最优解。其二为计算启发式 函数的花费。花费越长的时间来计算启发式信息，获得的启发式信息可能越多，极端情 况下是直接求解该问题，将该问题的解作为启发式信息。显然这种做法是不可取的。实 验表明，我们的d p r n c e p g 方法可以快速地计算状态的启发值，而且提供较多的启发 信息。 标准的条件效果规划图扩展方法和规划图扩展方法相同，只是在动作层中，我们添 加的是组件而不是动作。对于组件c i ，当它的所有前提都在当前命题列出现并且不存在 两两互斥时，c i 就被加入到下一组件列。c ；被添加后，它的结果被加入下一命题列。 两个组件c n 和c 。互斥1 1 5 】的定义如下： a ) 干扰，不一致效果：c i l 和c 0 来自两个不同的动作，并且组件c l i 的结果删除了组 件c 。的前提或者结果( 反之也成立) ； b ) 竞争需要：g i 的某个前提和c 。的某个前提在i 1 命题列互斥； c ) 诱导组件：存在第三个组件q ，吼由c n 在第i 列诱导，且c k 和c 。互斥。 组件g 诱导组件c k 【7 l 的定义如下： a ) c i i 和c k 来自同一个动作，并且 b ) g l 和c k 不互斥，并且 4 4 2s c h e d u l e 域 s c h e d u i e 域是一个公认难处理的域【2 5 l 【5 1 】。我们以它为基础来比较f f 和 d p r n c e p g f f 的规划求解效率和规划求解质量。图1 2 和图1 3 是我们从a i p s - 0 0 的 s c h e d i l l e 域的一部分测试问题上的对比测试结果。我们在全部的1 5 0 个测试问题上进行 了对比试验。实验结果表明，无论在r g p 的引导下还是在d p r n c e p g 的引导下，加 强爬山搜索在几乎所有的问题上都能够成功。但是如图所示，在大多数问题中，加强爬 山算法在d p r n c e p g 引导下，可以获得更好的规划解，并且耗费较少的时间。 l35791 1 1 31 5 1 7 1 92 12 3 2 52 72 93 13 3 p m b l e ms i 2 e 图1 2r g p 和d p r n c e p g 对规划解长度的影响 1 0 00 0 1 0 0 二：一镰l一d p r n 旺p g 秆 ：i 7 、 c 譬尹j 蠢f j u 13 7 量一0 1 3 1 51 7 1 92 12 32 5 ”2 93 13 1 3 誊列”1 5 ”2 1 2 3 2 5 ”2 ”1 3 、y 一 图1 3r g p 和d p r n c e p g 对求解时问的影响( 时间以对数坐标显示) 4 4 3e i e v a t o r 域 在e l e v a t o r 域，我们使用a i p s o o 的测试问题集。加强爬山算法在r g p 的引导下也 在这个域的一些问题上求解失败。我们的试验结果表明d p r n c e p g 和r g p 对加强爬 山算法的影响不同，见图1 4 。图中标有“e h c ”的列表示加强爬山算法是否搜索成功，“r 代表搜索成功，“f ”代表搜索失败。从结果可以看出，在一些问题中( 例如问题n 2 1 和 f 1 4 加强爬山算法在r g p 引导下遭遇失败，在d p r n i c e p g 引导下取得成功；当加 【s口88-o卜 第五章总结 在过去的十多年中，智能规划研究发展迅速。在求解速度不断提升的同时，规划器 所面对的问题日趋复杂化、现实化。启发式搜索方法作为人工智能研究中的主要方向之 一，已经成功地应用于处理目前的规划问题，并且有希望在以后的规划器设计中取得进 一步的成功。 本文回顾了在智能规划领域获取启发函数的一些主要方法，包括h s p 、h s p r 、放 松图规划、因果图、模式数据库。这些方法对于在规划领域的启发式搜索应用研究都进 行了成功的尝试。在这些方法中，放松图规划具有比较明显的优势，因为它既提供启发 式估计又提供裁减状态空间的建议。 放松图规划在s t r i p s 域的性能比较好，当它被扩展到a d l 域时由于a d l 定义问题 的复杂性，放松图规划方法在a d l 域上经常失败。本文分析了导致这一失败的原因并提 出了处理方法，得到一个新的启发函数获取方法。我们在l i n u x 平台