（计算机应用技术专业论文）图规划框架下创建删除对象规划的研究及实现.pdf

摘要 经典规划对规划问题做如下三条假设：( 1 ) 规划问题的目标是世界状态的逻辑描述； ( 2 ) 规划器所采取的动作是改变世界状态的唯一来源；( 3 ) 动作由前提条件与效果来 描述。前提是动作能够应用的条件，是一个命题集合；效果也是一个命题集合，这些命 题只能描述对象的性质与状态，不能表示对象的创建与删除，并且动作执行的效果是确 定的。g r a p h p l a n 是上世纪9 0 年代最为著名最为经典的规划器之一，至今仍有许多学者 在i 虱规划的框架下进行研究。g r a p h p l a n 的一个主要的局限是它只能应用于s t r i p s 领 域，特别是动作不能删除对象，动作也不能创建对象，而这类问题在现实中大量存在。 本文对创建删除对象的规划问题进行了初步研究。首先从新对象的性质是否可预 知，把创建删除对象的规划问题分为两类：新对象的性质可预知与新对象的性质不可 预知；提出了对象命题化的概念，通过对象命题化，可以把对象作为命题来处理，成功 的把对象间的互斥关系转换为命题间的互斥关系；提出了一种图规划框架下的创建删 除对象的规划算法( c d o g p ) ，用c + + 进行了实现，对实验结果进行了较为详细的分析， 并与g r a p h p l a n 进行了比较，结果表明本文的规划算法保留了g r a p h p l a n 的快速、高效 的特点，并且在求解新对象不相互干扰的规划问题方面有着较好的性能。 由于创建删除对象规划问题的广泛存在，因此该领域的研究对于丰富智能规划理 论，扩大智能规划的应用领域有着重要学术价值，而且对于竞赛机器人，游戏角色设计， 自然语言理解，工农业生产等许多领域的研究，也有一定的价值。 关键词：创建删除对象；对象命题化；图规划；可预知 a b s t r a c t a a s s i c a lp l a 疵n gp m b l e m si n a k ea s s u m p t i o n sa b o u tt h ew o d da sf o l l ，s ：( 1 ) m eg o a l s o ft h ep l a n n e ra r eal o g i c a ld e s c r i p t i o no fw o r l ds t a t e s ，( 2 ) t h ea c t i o n st a k e nb yt h e p l a n n e ra r e t 1 1 eo n l ys o u r c e so fc h a n g ei nm ew o r l d ，a n d ( 3 ) e a c ha c t i o nc a i lb ed e s c r i b e db yl h e c o n d i t i o n su n d e rw h i c hi tc a nb e 印p l i e da i l di t se f f c c t s0 nm ew o n d 孔e s ee f f e c t s 盯e d e s c r i b e db yas c to ff a c t sw h i c h 甜ee i m e rt 0b ea d d e dt oo rd e l e t e d 丘o mt 1 1 ew o r l ds t a t ei n w l l i c ht h ea c t i o ni sa p p l i e d n e s ef a c t sd e s 积b et h ec h a r a c t e r so fo b j e c ta n ds t a t e ，c a nn o t e x p r e s st h ec r e a t i n go rd e s t m y i l l go b j e c t g r a p h p l a i so n eo ft h em o s tp o p u l a rp l 卸n e r si i lt h e 9 0 so f2 0c e n t u r y ，a l l dl o t so fs c h o l a r ss t i l ld e v o t et h e m s e l v e st or e s e a r c hu n d e ri t sf r a m e w o r k t h em a i nl i m i to fg r a p h p l a ni s 出a ti to i l l ya p p i i e st os 1 r m sp r o b l e m s ，e s p e d a l l yc a i ln o t h a n d l et h ep l a n n i n gp r o b l e mw i t hc r e a t i i l go rd e s t r o y i n go b j e c t s ，b u t 山i s “n do fp m b l e mi s f a m i l i a ri nr e a lw o r l d n i sp a p e rm a k e st h ee l e m e n t 盯ys t u d yo ft h ec r e a t i i l go rd e s t r o y i n go b j e c t sp 1 蛐n i n g a c c o r d i n gt ow h e t l l e rt h ep r o p e r t yo ft h en e wo b j e c ti sp r e d i c t a b l eo r o t ，m i sk i n do f p r o b l e mw a sf i r s td i v i d e di n t ot w ot y p e s ：p i 锄n i i l gw i t hp r e d i c t a b l eo b j e c t sp r o p e n ya n d p l a n n i n gw i t hu n p r e d i c t a b l co b j e c t sp m p e r t y 。t h i sp a p e rb r i n g sf o r w a r dm ei d e ao f t r a n s f o 衄i 1 1 9o b j e c t si n t op r o p o s i t i o n s ，b a s e do nw h i c l lw et r a n s f o m lm u t e xb e t w e e no b j e c t s i n t om u t e xb e 柳e e np r o p o s i t i o n s ha d d i t i o n ，t h i sp 印e ro 廊r sa i la l g o r i t l l i nc a l l e dc r e a t i n go r d e s 扛d y i n g0 b j e c t si n 也eg r a p h p l a nf r a m e w o r k ( c d o g p ) a n di m p l e m e n t si tu s i i l gc + + w e a l l a l y z et h ee x p e r i m e n t a lr e s u l t s ，啪p 盯e dw i t l lg r a p h p l a i lt h en e wa 1 9 0 r i t h mn o to n l y p r e s e i n gt t l eh i 曲l ye f f i c i e n c yo fg r 印h p i a i l ，b u ta l s oc a i lh a n d l ec f e a t i n go rd e s t r o y i n g o b j e c t sp l a i l n i n gp r o b l e m sm a tn e wo b j e c t sd on o ti n t e e r e 谢t he a c ho m e l t h e r ea r eal a f g en u m b e ro fc r e a t i n go rd e s t r o ) d n g0 b j e c t sp l a n n i n gp r o b l e m si nt 量l er e a l w o r l d ，s ot h er e s e a r c hi n t h i sp a p e rw i l le n l a 玛et h et t l e o r e t i c a l f o u n d a t i o no fi n t e m g e n t p l a 皿i n ga n dt l l ea p p l i c a t i o d o m a i n s ，i ti si l n p o r t a i l tf o rt h es t u d y0 fr o b o tc o n t m i ，i n t e l l i g c n t g a m e ，t h ec o m p r e h e n s i o n o fn a t u r a l l a n g i l a g e ，a i l di n d u s 时p m “c ee t c 1 1 k e y w o r d s ：c r e a t i n go rd e s t r o y i n go b j e c t s ；o b j e c t _ p r o p o s i t i o n ；g m p h p l a n ；p r e d i c t a b l e i l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：蓬擅垂日期：z ! ! 聱复旦? 6 臼 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：蕴! 滔整 指导教师签名： 日 期：丝! ：! ! 乡日 期： 学位论文作者毕业后去向 工作单位： 通讯地址： 电话： 邮编： 引言 在人工智能的研究中规划是较早的研究领域之一，近年来，逐渐成为人工智能领域 的一个研究热点，aaa l 和u c a i 中有大约1 ，4 规划方面的文章。从9 8 年开始，u c a i 每两年举行一届智能规划与调度竞赛。在应用方面，规划技术广泛应用于工厂的作业调 度( j o bs h o ps 曲e d u l i n g ) 、宇宙航行、车辆调度等领域。特别是1 9 9 8 年底，美国的 n a s a 发射的d e e ps p a c eo n e 宇宙飞船的燃料自动控制系统使用了基于s a t 的规划方 法，表明智能规划的研究已经走出实验室应用于实际，在人工智能领域形成了智能规划 这一当前研究热点。 规划就是设计一个动作序列，使a g e n t 从初始状态出发，执行该动作序列就能达到 目标状态。对规划的理论研究始于对经典规划的研究，经典规划满足以下的假设经典规 划对规划问题做如下三条假设：( 1 ) 规划问题的目标是世界状态的逻辑描述( 2 ) 规划 器所采取的动作是改变世界状态的唯一来源；( 3 ) 动作由前提条件与效果描述，前提是 动作能够应用的条件，效果是一个命题集合，这些命题只能描述对象的性质与状态，并 不能表示对象的创建与删除，并且动作执行的效果是确定的。a l b l u m 教授与m l f u r s t 教授于1 9 9 5 年开发出经典规划器g r a p h p l a n ，提出的新颖的规划图结构给规划领域带来 了突破性的进展。同时也指出g r a p h p l a n 的一个主要的局限是它只能应用于s t r i p s 领 域，特别是动作不能删除对象，动作也不能创建对象。 创建删除对象的规划问题在现实世界中广泛存在，因此该领域的研究对于丰富智 能规划理论，扩大智能规划的应用领域有重要的学术价值。由于智能规划技术本身的独 立性，该研究在竞赛机器人，游戏角色设计，自然语言理解，工农业生产等许多领域， 也有广泛的应用前景。 本文研究的创建删除对象的规划，从对象的是否变化的角度来考察规划，是最为 复杂的规划之一，它突破了经典规划的第三条假设，特别是在规划操作的表达能力上， 超出了所有现有规划系统所能处理的操作类型。本篇论文的结构如下：第一章主要是对 智能规划进行了概述；第二章主要介绍了图规划方法和图规划框架下的主要研究成果； 第三章概述了创建删除对象的规划问题并对其进行了分类；第四章提出了基于规划图 的创建删除对象的规划算法( c d o g p ) ；第五章给出了c d o g p 规划器的实现与实验结果。 第一章智能规划概述 1 1 智能规划的基本概念 智能规划是一个多领域交叉的研究领域，它涉及知识表达、知识推理、非单调逻辑、 情景演算、人机交互和知识挖掘等各个方面。在人工智能领域，规划目前还没有一个统 一的定义，m c d e r m o t t 和j 鲫e sh e n d e l e r 认为“规划就是设计某个( 组) 实体( e n t i t y ) 的动作序列，其结果被称之为规划解( p l _ a n ) ”。智能规划系统实际上是一个应用软 件，当给定初始状态和目标状态及可用的相关操作后，该软件就可以给出从初始状态到 达目标状态的规划解，也就是自动给出一个动作序列，使得系统在初始状态下通过执行 这个动作序列，就可以到达目标状态。 一个规划问题( p l a n n i n gp r o b l e m ) 涉及以下四个集合”1 ： 个操作( o p e r a t o r s ) 的集合i 个对象( o b j e c t s ) 的集合； 一个初始条件( i n i t i a lc o n d i t i o n s ) 的集合，其中每个元素都是一个命题； 一个目标( g o a l s ) 的集合，其中每个元素都是一个命题，而且要求规划结束时 这些命题必须是真命题。 规划要解决的问题是：在初始条件下，对对象实施怎样一些操作，才能使问题目标 得以实现。 一般地，我们在做规划之前，大多做以下的假设： 1 规划是动作的序列； 2 动作的执行前件是确定的； 3 动作的执行后件( 效果) 是确定的。 通常，我们把满足以上假设的规划称之为“经典的规划”( c l a s s i c a lp l a n n i n g ) ， 例如地图着色问题、积木世界问题等都是经典的规划问题。现在，许多研究者还在采纳 此假定，但是由于现实世界的复杂性，实际问题往往并不能满足上述条件，因此也有一 部分人正在研究不满足上面假定的规划问题，不满足此假定的规划问题称之为“非经典 的规划”。 1 2 智能规划的发展 智能规划是人工智能领域的一个经典问题，对其研究始于2 0 世纪6 0 年代，并主要 依据两个已得到深入开发的技术：搜索和定理证明。可以说最早的规划系统是g p s ( 通 用问题求解) 。原则上g p s 可以解决任何搜索问题，但是它需要设计操作符一差别表记 载各操作符能消除的状态差别，这是耗时和冗繁的。与g p s 同期开发的规划系统是g r e e n 系统，该系统将规划问题的解决归约到定理证明：引入状态演算来演绎动作序列，但其 2 使用的推理链导致了难以解决的搜索问题且效率极低。“3 斯坦福研究所于1 9 7 1 年开始设 计著名的机器人动作规划系统s t r i p s ，它是早期自动规划领域中具有重要影响的一个系 统。该系统本质上是g p s 的特殊应用，但它采用g r e e n 系统中状态演算方法，解决了框 架公理问题，对推动规划技术的研究具有划时代意义。此后到1 9 7 7 年先后出现了 h a c k e r 、w a r p l a n 、i n t e r p l a n 、a b s t r i p s 、n o a h 、n o n l i n 等规戈0 系统。这期间人4 研究 智能规划的兴致比较高，普遍认为规划问题必须用定理证明的理论来解决，直到c h a d m a n 设计的规划系统t w e a k 出现。由于c h a p m a n 的分析，人们认识到简单地利用定理证明的 方法来解决规划问题是很难的，因此这以后到1 9 9 0 年问，在人们发现新的求解方法之 前，对智能规划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a k 和p r o d i g y 等智能规划 器出现。 9 0 年代，规划系统的研究达到高潮。这时主要采用三种方法来产生规划算法。第一 种方法是1 9 9 2 年k a u t z s e l m n 提出的规划可满足性方法s a t ( s a t i s f i a b i l i t y ) “1 ，该 方法将规划翻译成命题可满足性加以解决。第二种方法是1 9 9 5 年b l u l i l f u r s t 提出的 g r a p h p l a n 方法”“。该方法利用规划图结构来求解规划问题，为规划问题开辟了新的 解决途径。在该方法中采用n o o p 动作来传播未经动作改变的命题，解决了框架问题， 并且提出命题互斥和动作互斥的概念，利用互斥关系，大大加速了规划图后向搜索过程， 因此该方法比以前的方法求解速度要快得多。由于图规划算法的高效性，后来很多研究 者都致力于扩展g r a p h p l a n 来解决更多的问题，如i p p ，c g p ，s g p ，t g p 以及p g p 等规 划器都是在其基础上发展而来的。第三种方法是1 9 9 8 年b o n e t & g e f f e r 提出的启发式搜 索规划删。启发式函数产生规划实例的说明，用来指导在状态空间中的搜索。 h s p ( h e u r i s t i cs e a r c h i n gp l a n n i n g ) ”1 和f f ( f a s tf o r w a r d ) ”3 都是启发式规划器，它 们都使用放松的规划任务。放松任务的规划图中不包含任何互斥关系。目前采用的启发 式多为距离估计，如将当前状态与所要到达的目标状态的距离作为启发式估计。h s p 和 f f 均采用此种方法，但二者具体实现不同。h s p 假定命题可以独立的实现，忽略了动作 之间可能的交互作用。f f 则采用并行动作估计，f f 的启发式通常要比h s p 估计要低， 因为它考虑了命题之间积极的交互作用。目前将各种方法混合使用，规划的效果较好。 如b 1 a c k b o x 伽将命题满足性和规划图结合运用，取得第一届规划器比赛的冠军；f f 将规 划图结构和启发式搜索统一使用，获得第二届规划器比赛的冠军，并且在此次比赛中， 规划图算法和启发式知识相结合的技术也被发现可以得到更好的规划解。 综上所述，规划问题求解从最初的定理证明方法到s t r i p s 方法是问题求解方法上 的转变，然后又发展了非线性规划器，采用目标导向的方式来生成规划：一方面使得规 划的生成速度大大提高；另一方面，由于是目标导向的生成方式，因此生成规划的质量 比较好。现在人们又在此基础上加入了启发式信息，进一步提高规划求解的效率和质量。 1 3 规划问题描述语言 规划问题的定义是规划问题求解的前提，如果一个规划问题不能通过规划语言来表 3 示，则任何一个规划器都不能对它进行求解，所以说规划语言的发展是智能规划发展的 关键。1 9 7 1 年f i k e 和n i l s o n 的s t r i p s “”系统在智能规划中具有划时代的意义，因为 它使得规划可以非常容易地进行描述和操作。但随着规划技术的应用，人们发觉s t r i p s 的表达能力非常有限，它不能满足一些实际问题的模型化要求。设计一种能够刻画、模 型化一个实际问题的规划问题定义语言成为了规划技术应用的关键，1 9 9 6 年 e p e d n a u l t “”提出了动作描述语言 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 w m c d e r m o t t “等提出了规划领域定义语言( p d d l ) ，它逐渐地成为公认的国际智能规划 比赛的标准。p d d l 语言不仅给出了规划问题定义的语法，也从语义的角度给出了规划的 定义。p d d l 语言的表达能力非常强，能够刻画规划问题的时间和数值方面的属性，超过 了现有的规划器所能处理的表达能力，给规划器的发展提出了挑战，指明了发展的方向。 规划语言也是规划领域的种交流和沟通的标准，对于不同的规划器我们可以通过 它们对同一规划问题的处理来进行比较。 1 3 1s t r i p s 表示 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 ep r o b l e ms o l v e r ) 是斯坦福研究院在1 9 7 1 年开发的一个机器人行为规划系统，用来控制不稳定的可动机器人。为了描述s t r i p s 中的操作和世界模型( w o r l dm o d e l s ) ，开发了s t r i p s 语言。“”实际上，这种语言不仅 仅应用于s t r i p s 系统，还应用于其它规划系统中，g r a p h p l a n 就是其中之一。 规划问题的一种简单的形式化方法是定义三个输入： ( 1 ) 用某种形式语言对该领域的初始状态的描述； ( 2 ) 用某种形式语言对目标的描述： ( 3 ) 可能被执行动作的描述( 也用某种形式语言) ，这个描述通常被称为域理论。 s t r i p s 表示定义了“经典”的规划问题，它用一系列完整的基本字来描述域的初始 状态，并且将目标定义为一个合取命题，所有满足目标形式的域状态将被同等地考虑。 在s t r i p s 表示中，每个动作用一个合取前提和合取效果来描述，它们定义了从域到域 的过渡函数。 1 3 2 动作描述语言a d l 采用s t r i p s 式语言描述的经典规划问题具有一定的限制条件，即动作的前提是命 题的合取，动作的效果也是命题的合取，时间被离散地表示，动作既不能创建新的对象， 也不能删除对象。并且，动作一旦执行，其执行的效果是确定的。这种规划描述语言对 有些问题不能全面描述、甚至对有些问题根本就无法描述，不能满足一些实际问题的模 型化需求，所以要解决此类现实问题必须重新设计新的领域描述语言。 1 9 9 6 年e p e d n a u l t 1 提出了动作描述语言一一a d l ( a c t i o nd e s c r i p t i o n 4 l a n g u a g e ) 。a d l 所描述的操作对s t r i p s 进行了扩展，a d l 语言对s t r i p s 进行了扩展， 除了具有s t r i p s 的表达能力外，还能表达条件效果、量化效果等语言特征。条件效果 是动作描述中与上下文相依赖的效果，一般用w h e n 子句来表示。w h e n 子句由两部分构 成：前提和结论，动作执行后，只有w h e n 子句的前提也同时满足，才生成结论中的效 果；量化效果是允许在动作的效果描述中具有存在量词和全称量词。a d l 的扩展使得规 划语言所能描述的问题更多，解决了很多以前无法求解的问题类型。 1 3 3 规划领域定义语言p d d l 智能规划的研究逐渐地从理论研究走向实际应用，将规划技术运用到实际问题领域 就涉及到一个不可避免的问题：如何对一个实际问题领域进行模型化并进行推理。1 9 9 8 年，d r e wm c d e 瑚o t t “”提出了规划领域定义语言p d d l 。 p d d l 是一种以动作为中心的语言，它的实质是表达使用前件和后件来描述动作的可 使用性和效果的动作的语法标准。一个规划问题由一个域描述和一个问题描述组成。动 作的前件和后件表达成由谓词、项和逻辑连接词组成的逻辑命题。 1 p d d l l 2 p d d l l 2 是1 9 9 8 年第一届国际智能规划比赛使用的规划语言，它只是简单地给出了 如何定义规划问题的领域及规划问题的语法标准，并没有给出规划的语义。p d d l l 2 包 含了s t r i p s 域和a d l 域，使用s t r i p s 和a d l 能够表达的问题，p d d l l 2 也能够表达。 2 p d d l 2 1 m a r i af o x d e r e kl o n g 在2 0 0 2 年的第三届规划器比赛中提出了p d d l 2 1 “， p d d l 2 1 与p d d l 前面的版本兼容，它去掉了p d d l l 2 中不常使用的部分，增加了数值表 达、规划尺度和持续动作等新的表达能力。 p d d l + “4 3 是对p d d l 2 1 的第5 层的描述，它引入了两个附加的模型化部件：过程和 事件 3 p d d l 2 2 p d d l 2 2 “”保留了p d d l 2 1 的前三层的表达能力，新增了导出谓词和初始化时间命 题这两种表达能力。 导出谓词( d e r i v e dp r e d i c a t e s ) ：导出谓词提供了一种简洁和方便的方法来表达 对关系的传递闭包的更新。这种更新出现在那些包含一些结构的域中。 时间化初始文字( t i m e di n i t i a ll i t e r a l s ) ：时间化初始文字是一种很简单地表 示某种限定形式的外部事件的方法：规划器事先已知将在某个时间点变为真或假的事 实，与规划器动作的执行无关。 总之，规划语言是智能规划发展的关键，对于规划理论的发展有着重要的意义。一 些规划语言所能表达的规划问题，当前的规划器还不能够完全处理，所以说规划语言的 发展为规划的发展指出了方向。从s t r i p s 域到a d l 语言再到p d d l 语言，我们可以看出， 规划语言的表达能力越来越强，而且规划语言逐渐从实际应用的模型化角度来增强表达 能力。 1 4 规划的复杂度 人们对规划问题的研究已经五十多年了，到目前也已经提出了各种各样的解决方 案，但是由于规划问题是一个非常难解决的问题，所以现在能够解决的规划问题仍然是 很有限的，关于现实世界中的一些大而复杂的规划问题仍然不能很好地解决。对于规划 问题从理论上分析其计算复杂性的研究的主要结论如下： 1 9 8 5 年j o h nc a n n y 证明了形式化的s t r i p s 规划问题是一个p s p a c e 完全问题“。 g u p t aa n dn a u 于1 9 9 1 年证明：不论采取什么样的形式化系统，积木世界问题总 是n p 难题( n p h a r d ) “”。 领域相关的规划问题至少是n p 完全的( c h e n o w e t h1 9 9 1 “”；g u p t a a n dn a u1 9 9 2 “9 1 ) 。 领域无关的规划问题是p s p a c e 完全问题或更难( c h a p m a n1 9 8 7 。”； b y l a n d e r 1 9 9 1 1 ) 。 b e r n h a r dn e b e l 于1 9 9 4 年证明了规划问题是n p 难题o ”。 s e l m a n 于1 9 9 4 年进一步指出：类似于规划的问题是n p 完全的或更难的o “。 现在所能解决的规划问题还有很大的局限性，距离在社会中的广泛应用更有很大的 距离。也正因如此，规划问题的研究才具有很大的挑战性和价值，使得一些人工智能方 面的研究者乐此不疲。 6 2 1 基本的概念 第二章规划图 1 规划问题 一个规划问题( p l a n l l i n g p r o b l e m ) 涉及以下四个集合叫： ( 1 ) 个操作( 0 p e m t o r s ) 的集合； ( 习一个对象( 0 b j e c t s ) 的集合； ( 3 ) 一个初始条件( i i l i t i a lc o n d i t i o n s ) 的集合，其中每个元素都是一个命题； ( 4 ) 一个目标( g o a l s ) 的集合，其中每个元素都是一个命题，而且要求规划结束时这 些命题必须是真命题。 表2 - 1 火箭问题的操作 例如，火箭( r o c l 【e t ) 问题 操作的集合( 表2 1 ) ：m o v e ，u n l o a d ，l o a d ； 对象的集合：火箭r ，货物a ，货物b ； 初始条件的集合：a t a la t b la t r k f u e l r ； 问题目标的集合：a t ap a t b p 。 2 动作 一个完全实例化的操作叫做动作。如m o v e 操作中当? f r o m - l ，? t o = p ，则实例化成 动作皿o v e ( l ，p ) 。规划的任务就是在给定规划问题的初始条件之后，对对象实旋一系 列动作，使问题目标得以实现。 7 3 规划图 ( 1 ) 规划图的基本概念 规划图是由两种节点，三种边组成的分层有向图。两种节点分别是命题节点和动作 节点；三种边分别是前提条件边，添加效果边和删除效果边。 ( 2 ) 规划图中节点的互斥关系 在规划图中提出了动作互斥和命题互斥的概念。 两个动作节点a 与b 互斥 设a 与b 是在一个规划图中同一个动作层的两个动作，如果不存在一个有效规划能 同时包含两者，就说动作a 与b 是互斥的。 动作互斥判别方法包括动作相互冲突和动作的竞争需要。 动作相互冲突：设a ，b 是规划图中同一个动作层的两个动作，若动作a 删除了动作 b 的前提条件或者删除动作b 的添加效果，则动作a ，b 相互冲突，反之亦然。 动作竞争需要：同一个动作层的两个动作a ，b ，若它们的前提条件存在互斥，则动 作a ，b 具有竞争需要，也就是存在动作互斥，不可以在一个时间步同时执行。 两个命题节点p 与q 互斥 设p 与q 是在一个规划图中某一命题层上的两个命题，如果不存在一个有效规划能 同时包含两者，就说命题p 与q 是互斥的。 命题互斥判别方法：设p ，q 是规划图中同一个命题层的两个命题节点，若产生命题 p 的所有动作和产生命题q 的所有动作( 包括n 0 _ 叩动作) 都是互斥的，则命题节点p 和q 互斥。 ( 3 ) n 0 - o p 动作 一种对命题不作任何改变的动作称为空动作，即n o - 0 p 动作。n o o p 动作是一个特 殊的动作，任何一个真命题都可以成为它的全部前提条件，它被执行后，没有删除效果， 唯一的添加效果仍旧就是这个真命题。其作用是把本命题层的命题与互斥关系传递到下 一层。 ( 4 ) 规划图的“稳定”( 1 e v e lo f f ) 在规划图扩张阶段，存在一个最小整数n ，如果对于任何正整数m n ，时间步m 的 命题集合与时间步n 的命题集合总相同，时间步m 与时间步n 的动作集合也相同，而且 互斥关系相同。在这种情况下，我们就说规划图从第n 时间步起已经稳定。文献 2 ，3 已证明任何规划图都能达到稳定状态。 4 有效规划( v a l j dp l a ) 设有一个动作的集合，其中的每个动作都被指明其被执行的时间步；在同一个时间 步中被执行的任何两个动作都是不互斥的，所有的问题目标在最后的时间步均为真，那 么，我们就称这个动作集合为一个有效规划( v a l i dp l a n ) 。 8 2 2 图规划方法的基本思想 由初始条件对应的命题节点构成初始命题列。从初始命题列开始扩展规划图，在扩 展的过程中，考察同层命题节点的“互斥”关系与同层动作节点的“互斥”关系，通过 对互斥的考察有效的控制了规划图的增长速度，当所有目标命题都出现时，进行有效规 划的提取。如果有效规划提取成功，则输出有效规划，算法结束；否则继续扩展规划图， 直到找到有效规划( 成功) 或规划图进入稳定状态( 该规划问题无解) 。 2 2 1 图扩展 算法如f ： 1 时间步1 的命题列的生成 把初始条件中的所有命题作为时间步1 的命题列，一个命题一个节点。 2 时间步1 的动作列的生成 对操作集合中的每一个操作进行考察，把能够实例化的都进行实例化( 只要一个操 作的前提都在当前命题列中，并且两两不互斥，该操作就可以被实例化) ，每实例化一 个操作，就得到一个动作节点。这样就可以生成时间步1 的动作列。 将动作节点与作为其前提条件的命题节点用前提条件边连接。 3 假定时间步i 的命题列与动作列均已生成，时间步l + 1 的命题列的生成 时间步i 的所有动作( 包括o o p 动作) 的添加效果构成时间步i + 1 的命题列。将 时间步i 的动作列的每个动作节点与作为其添加效果的命题节点用添加效果边相连接， 与作为其删除效果的命题节点用删除效果边相连接。 如果命题p 是动作a 的一个添加效果，就说动作a 支持命题p 。如果支持命题p 的 任意一个动作都与支持命题q 的所有动作相冲突，则说命题p 与q 互斥。 考察动作问的冲突关系，对于每个动作标出与之互斥的动作列表。考察命题间的互 斥关系，标出相应的互斥的命题。 4 在当前的命题列中搜索问题目标 如果目标集中的所有命题均在此命题列中出现，并且任意两个命题都不互斥，则规 划图扩张结束，转为搜索有效规划：如果规划图进入“稳定”状态则该问题无解，结束； 如果目标集中还存在未在此命题列中出现的命题，则生成时间步i + 1 的动作列。 5 时间步i + 1 的动作列的生成 对操作集合中的每个操作，只要它的所有前提都出现在时间步i + 1 的命题列中，并 且任意两个命题都不互斥，便可以实例化该操作，并得到一个动作节点，把所有可能实 例化的操作都进行实例化，这样便得到时间步i + l 的动作列。将时间步i + 1 的每个动作 节点与作为其前提条件的命题节点用前提条件边相连接，转步骤3 。 9 2 2 2 有效规划的搜索 从时间步2 开始，每当一个时间步的命题列生成完毕后，就在此命题列中搜索目标 集。如果在时间步t 问题目标集合中还有未出现在命题列中的命题，则继续扩张规划图。 如果在时间步t 问题目标中的所有命题均出现在命题列中，并且任意两个都不相冲突， 则进行有效规划搜索，算法如下： 在规划图的最后一列( 必是第t 个时间步的命题列) ，任意取定一个目标集中的命题 ( 可以是命题列中上数第一个属于目标集的命题) ，考察在时间步t 1 中以这个命题为添 加效果的所有的动作( 叫做支持该命题的动作) ，从中取定一个动作，如动作1 。再从余 下的问题目标集中取定一个命题，考察时间步t 1 中支持它的动作，从中取定动作2 ， 要求动作2 与动作1 不相冲突。如果动作2 与动作1 相冲突，就换一个与动作1 不相冲 突的动作来取代动作2 。依此类推，继续这一工作。最后，假定从时间步卜1 中取定动 作n ，它支持目标集中最后一个命题，并且它与已经取定的动作1 ，动作2 ，动作 n 1 不相冲突。 把动作1 的所有前提，动作2 的所有前提，动作n 的所有前提都放到一起构 成一个新的命题集，叫做次目标集。如果这个次日标集能用t 1 步实现，则原目标集就 能用t 步实现。创建次目标集的过程叫做目标集合创建步( g o a is e t c r e a t i o ns t e p ) 。 对次目标集在时问步t _ l 继续这一过程。 如果到某一步次目标集恰好是初始条件中命题集的子集，则有效规划就被找到。 如果到某一步排在前面的一个目标支持它的任意一个动作都与已经选定的动作相 冲突，则我们需要立即回溯。注意，此时并不意味着没有有效规划，因为支持动作还可 以有不同的选法。 2 3 图规划的局限性及其扩展 图规划算法可以很快地找到一个最短的有效规划，或者返回规划问题无解。尽管图 规划算法具有如此良好的性能，但是规划图仍然具有很强的限制，最明显的就是图规划 算法采用s t i p s 语言进行描述。s t r 碍s 语言要求动作执行的效果是确定的，这种强 制性使得图规划算法只能处理一些规模较小的规划问题。 1 g r a p h p l a n 的一个主要的局限是它只能应用于s t r i p s 领域，特别是动作不能删 除对象，动作也不能创建对象。对对象实施某一动作的效果必须是能被静态确定的人或 物。 现实中许多规划问题不满足这些条件。 例如，如果一个动作允许挖任意深的一个洞，则可能有无穷多的对象被创建出来”3 。 又如，假定有这样一个动作“把屋里的所有的东西都涂红”。这一动作的添加效果 不能被静态地确定：一个对象被涂红取决于碰巧它当时在这个屋子里，所以被涂红的对 1 0 象的集合是不能被静态地确定的“1 。 2 g r a p h p l a n 需要互斥关系作为问题的重要约束，或很强的执行并行动作的能力以 减少图的深度，存在这两点都不满足的规划问题，能否找到更强有力的其它限制把它加 于g r a p h p l a i l 以使这一问题得到解决。 3 不确定规划 由于图规划算法采用s t r i p s 语言进行描述，而s 1 限i p s 语言要求动作执行的效果 是确定的，因此对于涉及到不确定成分的规划问题图规划算法不能解决。有许多学者在 此方面对规划问题展开研究，取得了成果较为丰硕的成果。比较典型的有： ( 1 ) 一致图规划g p ( c o n f o r i n a i l tg r a p h p l 蛆) 。” 非确定规划主要有两个不确定源：初始条件的不确定性和动作的不确定性。c g p 的处理对象是初始状态带有不确定性或带有不确定性动作的规划问题。对于初始状态的 不确定性，c g p 通过给出多个可能的初始状态来模拟初始状态的不确定性，每一个可能 的初始状态叫一个世界。c g p 的基本思想是根据初始条件和动作的不确定划分多个可能 世界，然后再用经典的图规划扩张过程并行的为每一个可能世界生成一个独立的规划 图，规划图生成后在各个规划图中搜索一个可以在各个世界中都能达到目标的规划。 ( 2 ) 感知图规划s g p ( s e n s o r yg f 印h p l a n ) ”“ 感知图规划s g p 算法可以处理具有如下特征的规划问题： 动作具有条件效果 初始状态带有不确定性 感知动作 在s g p 中，动作可以分为两种：感知动作和因果动作。所谓感知动作即带有感知 效果的动作，一个感知效果用一个s e n s ew 霞子句来表示，其中s e n s e 为一个关键字， 表示这是一个感知效果；w 伍是一个逻辑命题表达式即这个感知动作要观测的命题的逻 辑表达式。如果在执行感知动作时w f f 的值为真，则感知动作的返回效果是t ，如果在 执行感知动作时w 丘的值为假，则返回f 。感知动作的实质是一个检测动作，它检测w 丘 在某一时刻的值，它不改变任何命题的值，这一点与其它动作不同。在规划问题中引入 感知动作后我们就可以产生具有分支的规划了，我们可以根据感知动作的效果来分别执 行某些不同的动作。由于感知动作的返回值只是简单的二元值t 和f ，不便于规划器利 用，所以在s g p 中把感知动作的效果转化为知识命题。动作改变某个命题的值的效果 叫做动作的因果效果，具有因果效果的动作是因果动作。 知识命题表示规划器对世界的区分能力，如果规划器能够区分世界wu 和世界w v ，则可以用两个知识命题来表示规划器的这个能力，其表示方法如下：k 1u ：v 和k 1 v ：u 。在s g p 中我们可以根据感知动作在不同世界中的返回效果来区分不同的世界，即 可以把感知动作的效果转化为知识命题。如果某个感知动作在wu 和wv 中返回的效 果不同，那么我们就可以得到如下的知识命题：k 1u ：v 和k 1v ：u 。 s g p 表示出所有可能的世界并为每一个世界生成一个规划图。在规划图扩张过程中 的每一步，s g p 先不考虑感知动作，依次把每个世界的规划图向前扩张一步，其扩张方 1 1 法与经典图规划方法一样。把所有的世界都扩张完了步之后，再把跨越各个世界的感 知动作添加到规划图中。 s g p 算法的优点是它能够使用感知动作来感知当前所有的世界，这样可以大大地减 小搜索的空间，从而提高效率，但不足之处是算法比较复杂。 ( 3 ) 概率图规划( p g p p r o b a b i l i s t i cg r a p h p l a n 】“1 p g r 印h p l 姐算法是利用g r a p h p l a n 算法中的规划圈结构进行概率规划问题的求解， 它的处理对象是具有动作效果不确定性的规划问题，即动作执行后有若干个可能效果， 并且每个效果附有相关概率值。它采用一个概率分布来描述动作效果的不确定性，动作 执行后有若干个可能效果，每个效果附有相关概率值。p g r 印h p l a n 算法主要分为两个阶 段：第一个阶段是扩展一个给定时间步的规划图；第二个阶段是对己创建的规划图进行 前向搜索，得到成功概率最高的有效规划。 ( 4 ) 灵活图规划f ( m ( f l c x j b l eg r a p h p l 翘) 灵活图规划在2 0 0 0 年由e a nm i g i l e l 在欧洲第十四次人工智能会议上第一次提出o ”， 在2 0 0 1 年又在它的基础上加入了h d c s p 等算法在人工智能工程应用上得以发表o ，到