（计算机软件与理论专业论文）一种基于图规划思想的规划器的实现.pdf

中山大学硕士论文一种基于图规划思想的规划器的实现 论文题目：一种基于图规划思想的规划器的实现 专业：计算机软件与理论 硕士生：欧阳亚雄 指导教师：姜云飞教授 摘要 智能规划( a ip l a n n i n g ) 是人工智能领域的一个重要分支，它的主要思想是：对周围 环境进行认知与分析，根据指定的目标，对若干可供选择的动作及资源限制实行推理， 综合制定出实现目标的规划( p l a n ) 。近十几年来，智能规划的理论研究取得了巨大的进 步，出现了一些优秀的规划方法，其中图规划( 6 r a p h p l a n ) 由于其简单、高效而成为 一个非常有吸引力的规划方法。许多研究者对图规划方法作了大量的研究和改进，并基 于此方法实现了优秀的规划系统。本文深入研究了图规划方法之后提出了一些优化方 法，并基于该方法实现了规划n z s o p 。本文给出了图规划的基本算法和优化技巧的的实 现思路，并提出t z s u p 未来仍需改进的方面。 【关键词】人工智能，智能规划， 图规划，规划器 中山大学硕士论文 一种基于图规划思想的规划器的实现 t i t l e ：a ni m p l e m e n t a t i o no fp l a n n e rb a s e do ng r a p h p l a n m a j o r ：c o m p u t e rs c i e n c e n a m e ：y a x i o n go u y a n g s u p e r v i s o r ：p r o f y u n f e ij i a n g a b s t r a c t a ip l a n n i n gi sa ni m p o r t a n tb r a n c hi na if i e l d t h em a i ni d e ao fa ip l a n n i n g i st os y n t h e s i z eap l a nt oa c h i e v ed e s i r e dg o a l sb yr e c o g n i z i n ge n v i r o n m e n t s a n de h o o si n ga v a il a b l ea c ti o n su n d e rr e s o u r c ec o n s t r a i n t s i nr e c e n td e c a d e o fy e a r s ，t h e r eh a v eb e e nd r a m a t i ca d v a n c e si n p l a n n i n ga l g o r i t h m s s o m e e x c e l l e n ta l g o r i t h m sa p p e a r e di n c l u d eg r a p h p l a n 。g r a p h p l a ni sa s i m p l e ， e l e g a n ta l g o r i t h mt h a ty i e l d se x t r e m e l ys p e e d yp l a n n e r a f t e rs t u d i e d g r a p h p l a n ，w eg i v es o m eo p t i m i z a t i o n sa n di m p l e m e n tap l a n n e rz s u pb a s e do n i t a l s ow es u g g e s tf u t u r ew o r ka b o u tz s u p 【k e y w o r d s ：a i ，p l a n n i n g ，g r a p h p l a n ，p l a n n e r 中山大学硕士论文一种基于图规划思想的规划器的实现 引言 智能规划是人工智能研究中应用性很强的一个研究领域，例如工厂作业调度( j o b s h o ps c h e d u i n g ) 。车辆调度( v e h i c l es c h e d u l i n gp r o b l e m ) 等等。智能规划技术应用 在这些领域往往能为公司或者工厂带来可观的经济效益。正因为智能规划有如此广泛的 应用，所以人工智能专家m c d e r m o t t 指出“智能规划调度问题大量地出现在工业领域， 规划质量的改进，哪怕是一点小小的改进，都会节约大量的时间，带来上百万美元的效 益” 1 。 图规划方法作为智能规划技术当中一种优秀的规划方法，能够产生具有很强规划 能力的规划系统，国外许多优秀的规划系统都是采用或者结合图规划方法而实现，研究 如何实现并优化基于图规划方法的规划器具有重要的意义。本文详细的介绍了图规划方 法的理论，并提出了一些优化方法，并介绍了基于该方法的规划器z s u p 的设计思路。 最后本文给出了z s u p 与g r a p h p l a n 比较的实验结果，以及z s u p 未来需要完善的地方。 中山大学硕士论文一种基于图规杰! 思想的规划嚣的实现 1 1 概述 第一章智能规划简介 智能规划( a ip l a n n i n g ) 的研究从二十世纪5 0 年代开始，它与人工智能的研究 几乎一样早，但最初阶段由于理论和应用的限制，智能规划的发展比较缓慢。近4 0 年来由于应用需要的推动，吸引了众多的研究者加入了这个研究领域，使得智能规划 的发展越来越快，成为了人工智能研究的热点 1 。 智能规划本质上属于人工智能的一种问题求解方法，1 9 5 7 年n e w e l l 和s i m o n 的问题求解程序( g p s ) 其实就是最早的智能规划系统，因此智能规划系统可以被看 作是一个问题求解系统。 采用智能规划系统求解复杂的问题，得到的结果是个动作序列，依次执行此 动作序列能完成指定的具体任务，从而达到指定的目标。顾名思义，规划，就是给 定一个待解决的实际问题，在执行一系列动作之前，事先制定出动作的计划，即先 对闯题做出规划，然后执行规划。 最初研究者对智能规划系统的研究起源于问题求解，但随着规划研究的发展， 使得规划比常规的问题求解更加注重于解决具体的实际问题，而并非抽象的数学模 型【6 】。 智能规划也不并仅限于给出动作的执行顺序，还要求能够监视动作序列的执行 过程，如果动作执行的结果出现意外并且影响后续的动作执行，则要求规划系统能 够进行适当的干预并重新作出合理的规划。 在现实世界中，当人类面对复杂的实际问题时，首先是对问题进行周密的考虑， 制定一个可行的规划，然后按照这个规划执行，在执行的过程中如果出现问题或意 外情况，还会对未执行的计划进行修正甚至重新规划，直到达到目标为止。智能规 划实际上就是模拟了人类处理复杂的实际问题的这样一个过程。 中山大学硕士论文 种基于圈规划思想的规划器的实现 1 2 主要思想 智能规划的主要思想：对周围环境进行认知与分析，根据需要实现的目标及当前的 状态，对若干可供选择的动作及所提供的资源限制施行推理，综合制定出实现目标的 规划( p l a n ) 1 智能规划研究的主要目的是建立高效实用的智能规划系统( p l a n n e r ) 。该系统的主 要功能可以描述为： 给定问题的形式化描述： 1 初始状态的形式化描述 2 目标状态的形式化描述 3 对可实施的动作的形式化描述( 通常也称为领域知识) 3 智能规划系统能够根据该问题的形式化描述给出从初始状态转换到目标状态的一 个动作序列( p l a n ) ，即规划解。 问题的形式化描述通常采用命题逻辑或者一阶谓词逻辑的形式化语言，例如：积木世 界问题的形式化描述如下： ( p r e c o n d s ( o n - t a b l eb l o c k a ) ( o n t a b l eb l o c k b ) ( o nb l o c k cb l o e k a ) ( c l e a rb l o c k s ) f d e a l b l o c k c ) ( a m - e r u p t y ) ) ( e f f e c t s ( o nb l o c k a b l o c k b ) ( 0 nb l o c k bb l o c k c ) ) 广初始状态， p 目标状态 ( o p e r a t o rp 动作( 算子) ， p i c k - u p 0 a l a m s ( o b l o b j e c t ) ) ( p r e e o n d s ( c l e a r ) ( o n - t a b l e ) ( a r m - e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) ( o p e r a t o r p u p d o w n ( p a r a m s ( o s j e c r ) ) 中山大学硕士论文一种基于图规划思想的规划器的实现 r e c o n d s ( h o l d i n g d ( e f f e c t s ( c l e a r ( o b ) ( a r m - e m p t y ) ( o n - t a b l e o b ) ) ) 智能规划系统的复杂性和系统所处的环境以及a g e n t 的功能有关，为了简化规划问 题，经典的规划做出如下假设 1 3 。 1 环境的状态的改变完全由a g e n t 的动作的效果造成的，排除外界的影响和干 扰。 2 a g e n t 的动作的效果是完全确定的。 3 ，a g e n t 能够感知环境和动作的效果。 具有上述假设的规划问题叫做经典规划问题。 通常，我们把满足以上假设的规划称之为“经典的规划”( c l a s s i c a lp l a n n i n g ) ， 例如地图着色问题、积木世界问题等都是经典的规划问题。现在大多数研究者仍然采 纳此假定。由于现实世界的复杂性，实际问题往往并不能满足上述条件，许多研究者 也正在研究不限制于此假定的规划，例如在环境不断变化情况下的规划问题。不满足 此假定的规划问题称之为“非经典的规划”( n o n c l a s s i c a lp l a n n i n g ) 6 。本文设 计的规划系统针对的是经典的规划问题。 1 3 智能规划方法 1 3 1 基于定理证明的规划方法 基于定理证明的规划系统本质上是基于消解原理( r e f u t a t i o nr e s o l u t i o n ) 6 ， 它采用定理证明的方法，把规划求解的过程看成是一个证明过程，该证明过程试图证明 由初始状态和动作序列等构成的命题表达式能够推导出目标状态为真，其证明的过程就 是规划解。基于定理证明的规划方法以命题逻辑、一阶谓词逻辑等规范逻辑和各种菲规 范逻辑如缺省推理( d e f a u l ti n f e r e n c e ) 、或然推理( p l a u s i b l ei n f e r e n c e ) 、时序逻 辑( t e m p o r a ll o g i c ) 、内涵逻辑( i n t e n t i o n a ll o g i c ) 、非单调逻辑( n o n - m o n o t o n el o g i c ) 4 中山大学硕士论文 种基于酉规划思想的规划嚣的实现 和模糊逻辑( f u z z yl o g i c ) 等为其理论基础。较为典型的系统是g 1 r e r n s t 和a n e w e l l 设计的通用问题求解系统( g p s ，g e n e r a lp r o b l e ms o l v e r ) 和g r e e n 的q a 3 系统。 基于定理证明的规划方法在求解规划问题方面有固有的先天性不足，它会产生一 些异常模型( a n o m a l o u sm o d e l s ) ：即存在这样的模型，它们满足定理，但却找不到和 模型相对应的有效的规划解 1 。c h a p m a n 深入地研究了模型和规划解的对应关系，给 出了模型对应规划解的充分条件，并且给出了证明过程。 因此研究者普遍认为：规划问题必须采用特定目的的定理证明器来解决，通用的定 理证明器不能有效的求解规划问题，而且通用的定理证明器无法增加领域( 启发式) 知 识或者在加入一些推理的策略。 1 3 2 基于搜索的规划方法( p l a n n i n ga ss e a r c h ) 基于搜索的规划方法通常是在问题的状态空间上进行搜索，例如：n i l s s o n 和他的 斯坦福研究院人工智能研究组设计的s t r i p s 系统( s t a n f o r dr e s e a r c hi n s t i t u t e p r o b l e ms o l v e r ) 就是典型的基于搜索的规划方法 3 。尤其值得一提的是，s t r i p s 系 统提出的s t r i p s 算子对动作的表达能力非常适用，后来的很多规划系统都采用了 s t r i p s 风格的表达方式。 在s t r i p s 系统中，动作算子可以改变问题空间的状态，而对规划的求解就是利用 算子改变状态空间，并搜索状态空间直到搜索到目标的状态空间。搜索的方式通常有前 向搜索( f o r w a r ds e a r c h ) ，反向搜索( b a c k w a r ds e a r c h ) 或者两种方式结合在一起。 1 3 3 半序规划方法( p a r t i a l - o r d e rp l a n n i n g ) 半序规划方法是对操作序列加上一组半序约束，满足这些约束的动作序列叫 做候选规划。它是一个全序的操作序列，但是在半序上与约束的要求完全一致，在 数据结构课程中，也把这个过程叫做拓扑排序 1 。 规划的过程可以看成是“排除”和“分裂”的过程。“排除”的过程就是增加 约束，排除掉那些不能成为解的候选规划。“分裂”的过程就是在规划中插入新的操 作，搜索那些满足条件的解。 中山大学硕士论文一种基于图规划思想的规划器的实现 按约束要求给出操作序列的过程也叫做线性化，安全的线性化不但要满足对 操作的半序约束，而且要满足辅助约束。半序规划实际上代表了一组动作序列，任 何与上述半序规划的序相符合的全序动作序列都是strips 系统的规划。 半序规划的求精策略 可以把半序规划的求精看成是一个过程，也可以看成一个映射r ，它把一个规 划约束集合p 映成为另一个规划约束集合p ，使得p 的候选规划集是p 的候选规划 集的子集。如果p 包含了p 的所有的解，则r 称作是完各的( c o m p l e t e ) 。如果p 的候选规划集是p 的候选规划集的真子集， 则r 称作是前进的( p r o g r e s s i v e ) 1 。 如果没有操作序列属于具有p 的一个以上约束的候选规划集，则称r 具有系统性 ( s y s t e m a t i c ) 。完备性保证我们在求精的过程中不会丢失解，前进性保证我们在求 精的过程中会有效地剪掉不是解的候选规划，系统性保证我们在求精的过程中只能对 同一个候选解考虑一次。 求精策略可分为正向和反向两种。正向策略从初始状态出发，不断增加约束，一 直到目标状态得到满足为止。反向策略则从目标出发增加约束，知道动作的前提条件 都被问题的初始条件包含为止。因为反向策略产生的分支数比较少，因而在规划系统 中使用的比较多。 最小承诺策略 最小承诺就是在规划的求精过程中，对规划个体所加的约束尽可能的少，以免 过多的约束造成规划步骤闻的不相容，从面导致不必要的回溯。例如，如果在规划 的求精过程中有两个可供选择的操作，一个需要间隔保持约束，而另一个不需要，则 我们应该选择后一种求精过程。在比如，如果两个供选择的操作中，一个是抽象的 动作( 由若干具体简单动作抽象得来) ，而另一个是具体的动作，则我们应该选择抽 象的操作。 最小承诺与问题领域有很强的依赖性，一般说来，承诺相当于增加了约束，这 样容易识别半序规划是否包含解，但是增加了回溯的次数。因此对于问题的解比较少 的问题领域，晟小承诺比较有效，而对于解比较多的问题领域，效果差一些。 中山大学硕士论文 一种基于图规划思想的规划器的实现 1 3 4 图规划( g r a p h p l a n ) 方法 b l u m 和f u r s t 的图规划方法是最近几年智能规划最具吸引力的一种方法。因为图 规划方法作为一个简单、高效的方法能够产生非常快速的规划器，而且在图规划方法中 采用的知识表达方式也成为基于s a t ( 约束可满足) 规划的知识编码的基础。本文设计 的规划系统就是基于图规划方法。第二章将会详细介绍图规划方法。 1 3 5 基于约束可满足的方法( s a t ) 基于约束可满足规划是h e n r yk a u t z 和b a r ts e l m a n 深入地分析了传统的基于定理 证明的规划以后提出来的完全不同于以往演绎技术的一种特殊的规划方法，它克服了传 统规划器的异常( 每一个模型不一定对应一个有效的规划解) 情况，使得每一个正确模 型都有一个有效的规划解与其相对应 3 。 图2 _ 6 s a t 规划的体系结构如图2 6 所示，编译器( c o m p i l e r ) 的输入是规划问题( 包 括初始状态、目标状态和动作集合) ，它首先猜测规划解的长度，产生一个逻辑命题公 式，如果逻辑命题公式是可满足的，它蕴涵着规划解是存在的：符号表( s y m b o lt a b l e ) 记录了命题变量和规划实例之间的对应：简化器( s i m p l i f i e r ) 运用较快( 通常为线性 时间) 的技术( 如单元子句法，纯文字消去法等) 等来降低c n f 公式的规模；求解器 ( s o l v e r ) 运用系统或统计的方法来找到一个满足的赋值；解码器( d e c o d e r ) 用符号 表把赋值转换成一个规划解。如果求解器发现公式是不可满足的，那么编译器就会产生 新的编码( 代表更长的规划解) 。 由基于s a t 的规划的体系结构可以看到，这种规划方法关键在于两个环节，一个是 编码方式，另一个是求解方式。有关第一个问题的研究取得了一系列的进展，由于基于 7 中山大学硕士论文一种基于圈规划思想的规划器的实现 s a t 的规划算法是基于s a t 算法来实现的，所以第二个问题其实就是选择好的s a t 算法， 而可满足性( s a t ) 问题是人工智能研究领域中的一个基本理论问题，最近几年来，每 年都有新的s a t 算法问世，人们设计各种各样的技术来提高解决s a t 问题的效率，这几 年来主要有g s a t 算法和w a l k s a t 算法，但是这两个算法都不是完备的，一个比较经典 的完备s a t 算法是d p 算法。 总结g r a p h p l a n 和s a t p i a n 的相同点和异同点： 共同点：s a t p i a n 和g r a p h p l a n 都分两阶段进行： ( 1 ) 建立一个命题结构( ap r o p o s i t i o n a ls t r u c t u r e ) ：在图规划中是规划图， 在s a t 规划中是c n fw f f 。 ( 2 )在第一步所建立的结构中搜索规划解。 异同点： 图规划( g r p h p l a n ) 用的实例化命题结构算法较好。 s a t 规划( s a t p l a n ) 的搜索算法更加强大。 结合以上两种算法的优点，k a u t z 和s e l m a n 于1 9 9 8 年在a i p s 上提出了b l a c k b o x 规划算法，此系统分三个步骤进行工作： 1 把一个规划问题( 以标准的s t r i p s 形式描述的) 转化为一个规划图。 2 把第一步中生成的规划图转化成一个c n fw f f 。 3 运用最快的s a t 引擎解决w f f 。 1 3 6 其它规划方法 除了上述的规划方法外，还有基于事例( c a s e - b a s e d ) 的规划方法、基于约束 ( c o n s t r a i n t - b a s e d ) 的规划方法、互操作( r e a c t i v ea p p r o a c h e s ) 规划方法、分 布式规划( d i s t r i b u t e dp l a n n i n g ) 、骨架式规划( s k e l e t a lp l a n n i n g ) 、概率( 机遇) 式规划( o p p o r t u n i s t i cp l a n n i n g ) 、线形规划( l i n e a rp l a n ) 、层次规划( h i e r a r c h y p l a n n i n g ) 、非线形规划( n o n l i n e a r p l a n ) 、启发式规划( h e u r i s t i cp l a n n i n g ) 等等 6 ， 这里就不一一赘述了。 8 中山大学硕士论文一种基于圈规划思想的规划器的实现 1 4 目前的研究背景 1 在最近的7 - 8 年，许多智能规划系统的规划能力有了非常大的提高。过去的 智能规划系统只能产生出5 _ 6 个动作的规划，且需花费几分钟的时间：而现在 同样的时间内却能够产生超过1 0 0 个动作的规划。 2 智能规划的理论研究有了太幅度的进展。例如：把智能规划问题和约束可满足 问题联系起来进行研究，取消了智能规划和调度问题的区别，利用领域知识进 行规划的方法等等【1 5 ，6 1 。 3 智能规划系统能力的提高，使智能规划在实际应用领域得到了广泛的应用。 例如：在工业、交通、信息、机器人、航空航天等领域。 4 在国外，近年来成立了许多专门从事智能规划方面研究的协会和联盟，如欧 洲智能规划网p l a n e t ( e u r o p e a nn e t w o r ko fe x c e l l e n c ei na ip l a n n i n g ) ，英 国诺丁汉大学a s a p 研究组( a u t o m a t e ds c h e d u l i n g , o p t i m i s a t i o na n d p l a n n i n g ) 以及美国亚利桑那州立大学砌1 a l l 研究组1 1 】 5 一些国际知名期刊发表的关于智能规划方面的论文呈逐年增长的趋势。如 a r t i f i c i a li n t e l l i g e n c e 近年来发表了许多篇智能规划方面的文章，在1 9 9 5 , 2 0 0 3 都出版了关于智能规划的专刊。 6 在一些大学里，不仅有越来越多的研究人员从事智能规划方面的研究工作，还 在大学生和研究生中开设了智能规划方面的课程。 7 近十几年来，智能规划方面的学术会议也越来越多，u c a i ( i n t e r n a t i o n a lj o i n t c o n f e r e n c eo n a r t i f i c i a li n t e l l i g e n c e ) p 0 0 1 年召开智能规划与机器人”( h a r m i n g a n dr o b o t i c s ) 专题的研讨会：国际智能规划与调度研讨会a i p s ( a r t i f i c i a l i n t e l l i g e n c ep l a n n i n g s c h e d u l i n g ) 已经举办到1 2 届：欧洲智能规划研讨会 e c p ( e u r o p e a nc o n f e r e n c eo np l a n n i n g ) 已经举办到第5 届；其中在2 0 0 3 年 a i p s 和e c p 合并为属于i e e e 下的国际智能规划与调度研讨会i c a p s ( i n t e r n a t i o n a lc o n f e r e n c e0 1 1 a u t o m a t e dp l a n n i n g s c h e d u l i n g ) 【1 】。 中山大学硕士论文 种基于田规划思想的规划器的实现 2 1 图规划简介 第二章图规划方法 图规划( g r a p h p l a n ) 方法是近十年来智能规划研究中发展非常快的一种方法， 它最初是由a v r i ml b u m 和m e r r i c kl f u r s t 4 提出来，而后，很多研究者在这 个基础上提出了许多改进和优化。目前主要基于图规划方法的规划系统有美国卡乃 基一梅隆大学( c a r n e g i e m e l l o n u n i v e r s i t y ) 的图规划器g r a p h p l a n ( b l u m l f n r s t ) 、 德国的i p p 、英国的s t a n 、美国华盛顿大学( u n i v e r s i t yo fw a s h i n g t o n ) 的 s g p ( d a n i e ls w e l d 等) 3 。 2 2 基本概念和定义 2 2 1s 嘲p s 算子 1 9 7 1 年，f i k e s n i t s s o n 7 在他们开发的智能规划系统s t r i p s 当中提出了一 种算子，由于该算子在表达动作方面具有很好的适用性，后来的许多规划系统大多采用 类s t r i p s 风格的算子。 一个s t r i p s 算子由三部分组成： 1 ) 集合p c ，称为算予的前提条件( p r e c o n d i t i o n s ) 的基本文字。即当p c 中的所 有文字都在当前状态描述中时，动作才能被执行。 2 ) 集合d ，称为删除列表( d e l e t e1 i s t ) 的基本文字。 3 ) 集合a ，称为加入列表( a d dl i s t ) 的基本文字。 为了生成动作后的状态描述，删除动作前状态出现在d 集合中的所有文字，加入a 中的所有文字，在d 中没有提到的文字延续至动作后状态描述中，这种延续是为了解决 框架问题的种方法。 例如： 中山大擘硕士论文一种基于萄授划思想韵觏捌器的实现 m o v e ( x ，y ，z ) p c ：o n ( x ，y ) a n dc l e a r ( x ) a n dc l e a r ( z ) d ：c l e a r ( z ) o n ( x ，y ) a ：o n ( x ，z ) ，c l e a r ( y ) ，c l e a r ( f 1 ) 在图规划系统中采用了两种算子表达方式：( 1 ) p r o d i g y ( 2 ) n o n p r o d i g y 。 p r o d i g y 的表达方式将增加效应和删除效应的命题合并在一起，给删除效应命题加 上特殊的前缀，例如”d e l “，使得系统能够分辨出增加效应和删除效应。 n o n - p r o d i g y 的表达方式没有给出删除效应，删除效应由前提条件和增加效应的集 合差表达，即前提条件没有显式出现在效果的命题里被默认为属于删除的命题。这种表 达方式简洁有效，适合大多数常用的领域。本文所研究的动作实例化方法是基于这种表 达类型的算子。 例如： ( o p e r a t o r p i e k - u p ( p a r a m s ( o b j e c t ) ) ( p r e c o n d s ( c l e a r ) ( o n - t a b l e ) ( a r l l l e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) 算子本质上是一种动作模式( a c t i o ns c h e m a t a ) 3 ，它是为了简化对规划问题 的动作的表达。在规划问题里存在若干个对象，如果采用具体的动作表达方式，将 使得规划系统变得很庞大，它需要为每个可能的对象生成具体的动作，这使得规划 问题的表达变得很繁琐。因此，将大量的具体的动作抽象成若干种动作模式就能简 化规划动作的表达。算子包含自由变量，而不是实际的对象。若存在替换 ( s u b s t i t u t i o n ) 使得算子的自由变量替换成实际的对象，那么该算子变成一个具体 的动作，这称为动作实例化。 例如下面给出了一个积木世界算子实例化为具体动作的例子。 当前状态为： ( o n - t a b l eb l o c k a ) 1 1 中山大学硕士论文 一种基于图规划思想的规划嚣的实现 ( o n - t a b l eb l o c k b ) ( o nb l o c k cb l o c k a ) r c l e a tb l o c k b ) ( e l e a tb l o c k c ) ( a r m e m p t y ) 对于算予p i c k - u p ( o p e r a t o r p i c k - u p ( p a r a m s ( o b j e c t ) ) ( p r e t e n d s ( c l e a r ) ( o n t a b l e ) ( a t m - e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) 可以实例化为动作：p i c k - u pb l o c k b p r e c o n d s ：( c l e a rb l o c k b ) ( o n - t a b l eb l o e k b ) ( a r m e m p t y ) e f f e c t s ：( h o l d i n gb l o c k b ) 2 2 2 有效规划解( v a l i dp l a n ) 通常来讲一个有效的规划解是一个动作序列，它包括一个动作的集合，且指定每个动 作执行的顺序。其中有些动作可以并发的执行，有些动作则不行。在线性规划里，可以 并发执行的动作可以采用任意的顺序执行【4 】。 2 2 3 规划图( p l a n n i n gg r a p h ) 图规划方法提出了规划图这样一种数据结构，它将规划问题编码为规划图，利用规 划图来搜索规划解 3 。 规划图( p l a n n i n gg r a p h ) 是一个具有两类节点和三类边的有向分层图 1 ，2 。规划 图各层依次由命题层( p r o p o s i t i o nl e v e l s ) 和动作层( a c t i o nl e v e l s ) 交替出现，命 中山大学硕士论文 一种基于图规划思想的规划器的实现 题层包含命题节点( 一些命题为标记) ，动作层包含动作节点( 一些动作为标记) 。 如图2 ，黑色圆圈表示命题节点，方框节点表示动作节点。动作结点与上一层的命 题结点的线段表示这些命题是该动作的前提条件：动作结点与下一层的命题层结点的线 段表示这些命题是该动作的效果( 包括增加效果和删除效果) 。上一层命题层结点与下 层命题结点直接相连的线段表示没有任何动作实施使得状态延续，这能够解决框架公理 ( f r a m ea x i o m ) 问题。 0i 1ii + 1 - 图2 - i 2 2 4 规划图的互斥关系 图规划方法的最重要的特征就是发现和记录动作结点或者命题结点间的互斥关 系，通过互斥关系，可以显著减少搜索的开销【4 】。 互斥关系的定义：给定某一动作层的两个动作，如果不存在一个有效的规划解包含 这两个动作，那么这两个动作互斥；给定某一命题层的两个命题，如果不存在一个有效 的规划解使得这两个命题同时为真，那么这两个命题互斥【4 】。 图规划方法通过一些简单的规则来发现和延续这些互斥关系，以下给出了这些简 单的规则： 两个动作在第i 层互斥当且满足以下规则： ( 1 )效果不相容( i n c o n s i s t e n te f f e c t s ) = 一个动作的效果是另外一个动作的效果 的反命题，或者说一个动作增加的效果恰恰是另外一个动作删除的效果。 ( 2 ) 冲突国t e r f e r e n c e ) ：一个动作的效果删除了另外一个动作的前提 中山大学硬士论文一种基于图规划思想舯规划嚣的实现 ( 3 ) 竞争所需( c o m p e t i n gn e e d s ) ：两个动作的前提的命题在i - 1 层互斥 两个命题在第i 层互斥当满足以下规则： ( 1 ) 一个命题是另外一个命题的取反 ( 2 ) 获得一个命题的所有动作解与获得另外一个命题的所有动作解两两互斥。 在解提取过程中，可以充分利用规划图构造的动作结点和命题结点的互斥关系，减 少解的搜索过程，例如在解的反向搜索过程中，当某一个子目标与另外一个子目标互斥， 则不需要再对这个子目标继续搜索。或者当为某个子目标选取动作解时，如果该动作 与已经选择的动作解互斥，则不需要选择该动作，而继续搜索其他的动作或者回溯。 2 2 5 规划图的定理 ( 1 )如果存在一个小于或者等于t 步的有效规划解，那么这个规划解一定是规划图 的子图。 ( 2 ) 假设一个具有n 个物体，初始命题具有p 个文字、1 1 1 个s t r i p s 算子的规划问 题，假设l 等于最长的算子a d d l i s t 的长度，那么创建t 层的规划图的时间是n , m ，p ，1 ，t 的多项式。 证明： 假设k 是最长的算子参数的长度，由于算子不能创建对象，因此能够被一 个算子增加的命题数量为o ( 1 n 。) ，因此规划图的任意命题层的结点数不超过 0 0 + m 1 i 国，由于每个算子最多能被实例化为o ( n b + ，因此规划图的任意动作层的结 点数不超过o ( mn k ) 。因此规划图的大小是n , m ，p ，l ，t 的多项式( k 通常是个常量) 。 2 3 图规划过程 规划图的第一层( 初始层) 是命题层，该层包含规划问题的初始条件下的所有命题。 图规划在两个阶段( p h a s e s ) 交替进行：图扩展( g r a p he x p a n s i o n ) 和解提取( s o l u t i o n e x t r a c t i o n ) 。 ( 1 ) 开始时构造只有第一层命题层的规划图，这第一层命题层包含初始状态的命题 1 4 中山大学硕士论文一种基于圈规划思想的规划嚣的实现 ( 2 ) 然后递归的扩展规划图，假设在第i 步 ( 3 ) g r a p h p l a n 把第i - 1 步的规划图作为输入 ( 4 ) 把该规划图扩展一个动作层和一个命题层 ( 5 ) 然后在扩展后的规划图提取长度为i 的规划解 ( 6 ) g r a p h p l a n 或者搜索到一个长度为i 的规划解或者无解。 ( 7 ) 如果无解，则i i i + 1 ，继续( 3 ) ( 8 ) 结束 2 3 1 图扩展 图扩展阶段分为两个步骤： ( 1 ) 假设当前层为第i 层，对于每一个算子，选取所有可能的对象将算子实例 化为动作，如果当前命题层满足该动作的前提条件且前提条件不互斥，那么将 动作插入规划图的第i + l 层即动作层，同时插入无动作结点( n o 0 1 3 ) ，该结点表 示持续效果，即命题没有施加任何动作，状态持续不变。然后插入前提条件的 边：检查每个动作结点，根据2 2 4 提到的规划图的互斥关系规则，为每个动作 创建一个互斥链表，该链表记录所有与该动作互斥的动作。这个步骤完成了第 i + l 层的规划图的创建，包括结点和边。 ( 2 ) 检查第i + 1 层的动作结点的增加效果( 包括无动作结点) ，把这些增加效 粟命题插入到第i + 2 层的命题层( 无动作结点的增加效果就是前提条件) ，然后 插入增加效果或者删除效果的边，如果所有到达第i + 2 层的两个命题的动作解 两两互斥，则标记这两个命题互斥。 2 3 2 解提取 给定一个规划图，g r a p h 采用反向链接( b a c k w a r d - c h a i n i n g ) 策略从规划图中提取 出规鲻解，这个过程就是解提取过程。解提取过程反向搜索是逐层迸行，这是为了能充 分利用每一层的互斥关系c 4 。 给定一个第t 步的目标集合，解提取尝试在t - 1 步发现一个动作的集合( 包括无动 作) ，使得这些动作的增加效果就是该目标集合。而这些动作的前提条件又形成第t - 1 中山大学硕士论文一种基于圈规划思想的规生! 器的实现 步的子目标。如果这些t 一1 步的子目标不存在有效的规划解，那么解提取尝试在t 一1 步发现另外的一个动作集合，持续直到成功地获得规划解或者证明无解。这个过程是一 个递归的过程。 为了实现上述策略，g r a p h p l a n 采用如下递归的搜索方法： ( 1 )依次选择第t 步的每个目标，选择第t - 1 步的动作能达到这个目标，且该 动作不与已经选择的动作互斥。持续递归的选择第t 步的下一个目标；如 果该目标已经存在于已经选择的动作的增加效果，则不需要加入这个动作 jo ( 2 ) 如果选择动作失败，就尝试另外的动作以达到当前的目标。如果所有的动 作都尝试过但仍然互斥，则返回失败。 ( 3 ) 如果第t 步的目标都能够达到，那么所选动作的前提作为新的子目标集合， 即t - 1 步的目标。 g r a p h p l a n 在解提取过程中提到了一个重要的优化过程：m e m o r i z a t i o n ：当解提 取过程时，如果发现在t 步时间里发现某目标子集无解，则先将该目标子集存入哈 希表中，如果下次搜索到第t 步的目标子集，首先寻找哈希表中是否存在该目标子 集，如果存在则无需再搜索。 2 3 3 无解的判定 如果不存在规划解，规划图将会无限制的扩展，为了解决这个问题，m 印h p l 纽 给出了无解的判定条件： 假设一个问题无解，那么在不断的扩展规划图中，一定存在一个命题层p 使得p 以后的命题层和p 一样，具有同样的命题结点和同样的命题互斥关系。我们称之为l e v e l o f f , 可以理解为规划圈扩展的饱和状态。如图2 - 1 ： 审山大学磺士论文一种基于圈规划思想的规划器的实现 个 数 时间 图2 1 个数 关系个数 证明： 规划图存在无动作结点，即上一层的命题层结点持续到下一层命题结点，由于 基于s t r i p s 风格的算子所增加的命题集合是有限的，因此一定存在命题层o ，o 以后 的命题层与q 具有同样多的命题结点。由于存在无动作结点，如果某一层命题p 和q 不互斥，那么p , q 延续到下一层一定也不互斥，即互斥关系在q 之后定是单调非递增。 因此，一定存在命题层p 在q 以后，所有的命题具有同样的互斥关系。 l e v e lo f f ，即饱和状态是无解的必要条件。 在解提取过程中，g r a p h p l a n 记住哪些被确定为无规划解的目标子集。假定s ! 表示 经过第t 步，第i 层的被判定为无解的目标子集的集合( t i ) 。换句话说，在第t 层的 规划图进行反向提取时，在第i 层确定无解的目标子集。g r a p h p l a n 此时能够判定两个 事实 ( 1 ) 如果存在t 步或者更少的规划解，那么该规划解至少能够使得g 中的一个子 集为真。 ( 2 ) s j 的任一个子集在第i 步时是无解的。 假设规划图在第n 步达到l e v e l o f f * t 态，如果经过t 步( 1 n ) ，满足i 4 i = i s ：l ， 那么该规划问题无解。这是无解的充分条件。 中山大学硕士论文 种基于圈规龙! 思想的魏射嚣的实现 2 4 图规划的优化 解的提取过程的优化：f o r w a r dc h e c k i n g ，m e m o r i z a t i o n ， e x p l a n a t i o n b a s e d l e a r n i n g 图扩展过程的优化：h a n d l i n g t h ec l o s e d w o r l da s s u m p t i o n ，c o m p i l a t i o no fa c t i o n s c h e m a t a t y p ea n a l y s i s ， s i m p l i f i c a t i o n ， r e g r e s s i o nf o c u s i n g ，a n di n p l a c e g r a p he x p a n s i o n 。 以上提到的图规划的优化都能够或多或少的提高规划系统的效率，限于篇幅，本文 这里介绍几个主要的优化方法，详细的资料可以查看参考文献 3 ( 1 ) m e m o r i z a t i o n ： 在反向搜索解的过程中，如果在时问t 的子目标被确定为无解，则 g r a p h p l a n 将该子目标记录下来。如果在下一次时间t 创建了子目标，首先检 查该子目标是否已被记录为无解，如果是，则直接回溯而无需继续搜索。 ( 2 ) f o r w a r dc h e c k i n g ： f o r w a r dc h e c k i n g 优化技巧来源于c s p ( 约束可满足问题) ：当给一个变量 赋值时，c s p 解答系统只是简单的保证该值与已赋值是一致的。而f o r w a r d c h e c k i n g 作为更好的一种技巧则首先检查未赋值的变量，删除掉那些与已赋值不一 致的值，如果未分配的变量的值域为空( 说明不存在与已赋值一致的值