（计算机应用技术专业论文）带有回溯和有用动作排序的ff规划算法研究.pdf

摘要 智能规划是人工智能的一个重要领域。近年来，有关智能规划的研究在问题 描述和问题求解两方面得到了新的突破，使得智能规划已成为个热门的人工智能 研究领域。对智能规划算法的研究主要集中在规划算法性能的提高和规划算法求解 问题的范围的扩展。基于规划图原理和启发式状态空间搜索的智能规划算法在众多 的智能规划算法中表现十分突出。f f 规划器将规划图和启发式状态空间搜索原理进 行了很好的结合，在两届i p c ( 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 j o n ) 中取得了 优异的成绩。但是f f 规划算法所采用的搜索方法和规划图的使用上都存在很大不 足，使得f f 规划算法在某些规划问题域中，特别是含有死点状态的问题域中表现 不够理想。 本文通过对规划图原理、启发式状态空间搜索原理和f f 规划算法的研究，提 出了一种更适合f f 规划器使用的搜索方法一带有回溯的加强爬山搜索算法，同 时在规划图的使用中加入了有用动作排序并且探索了多种排序标准。带有回溯的加 强爬山算法在加强爬山算法失败时，通过回溯使规划器可以利用前一步的搜索结果 来继续进行加强爬山搜索。有用动作排序使规划图和状态空间搜索更好地结合在一 起。以上两种方法可以有效地解决死点问题。基于以上两点，本文提出了一种新的 规划算法，即带有回溯和有用动作排序的f f 规划算法。 本文将回溯应用在规划解的提取过程中，同时将规划图理论和状态空间理论有 机地结合在一起，很好地解决了死点状态问题。基于新算法的b t f f 规划器相对于 f f 规划器极大地提高了求解的效率和解决问题的范围。因此本文具有很重要的学术 意义和研究价值。 关键词：智能规划；规划图；f f ：启发式状态空间搜索 a b s t r a c t n o wa n i f i d a li n t e l l i g e n c ep l a n n i n gi sav e r yh o tb r a 】1 c hi 1 1a j b e c a u s eo fi t sw i d e a p p l i c a t i o n ，r e s e a r c h e r sp a ym u c ha t t e n t i o n t op l a n l l i n gt e c h n 0 1 0 9 y t h et o p i c so f a n i f ! i c i a l i n t e l l i g e n c ep l a i l l g f o c u s e do nt h es p e e do fp m b l e m s o l v j n ga n d t h e c o m p l e xm o d e l l i n go fd o m a i n st h a th l t e l l i g e n tp l a 蚰 n gs y s t e m s o rp l a n n e r sc a nd e a l w i t h m o s ta n i f i c i a li n t e l l i g e tp l a n n i n ga l g o r i t h m sa r eb a s e do np l a n n i l l g 鲈a p h0 rs t a t e s p a c e s e a r c h f fb a s e do nb o t h p l a n n i n gg r a p h a n dh e u r i s t i cs t a t e s p a c e s e a r c h i n g ，p e r f b 册a n e ds t a i l d o u ti i lt h e2 n da i l d3 r di m e m a t i o n a lp 1 a n n i n gc o m p e t i t i o n b e c a u s eo ft h es e a r c h i n gl 玎e t h o da n dt h eu s i n go fp l a n n i n gg r a p h ，f fd o e s n o t p e r f o r n l a n e di d e a l l yi l ls o m ep r d b l e md o m a i n ss u c ha sg r i p p e l i nt h i sp a p e r an e ws e a r c b i n gm e t h o de n f o r c e dh i l l _ d i m b i i l gw i t hb a c k t r a c k si su s e d ， a n dan e wm e t h o do fh e l p f l l la c t i o no r d e r i n ga r ep r e s e n t e d e n f o r c e dh i l l c l i m b i n gw i t h b a c k t r a c k sc a nu s et h el a s ts e a r c h i n gr e s u n sw h e ne n f o r c e dh 罅d i m b i n gf a i l s ，s oi ti s m o r ef i tf o rf f h e l p f i l la c t i o no r d e r i n gc a ns a v et h et i m eu s e db ye n f o r c eh i l l c l i m b i n g t h r o u 曲o r d e t i i l gt h eh e l p f u la c t i o n s w ep u t f o 州a r dan e wi n t d l i g e mp l a n n i n g a l 譬o r i t h mb t f fw i t ht h ee n f o r c e dh i 一d i m b i n ga 1 1 dh e l p f i l la c t i o no r d e r i g i n t h i sp a p e rw e 讪e s t i g a t eh o wt oi m p r o v et h ee n f o r c eh i l l d i m b i n ga n d h e l p f u l a c t i o no r d e r i n gi 1 1a n i f i c i a l1 1 1 t e l l i g e n tp l a l l i l i n g n i s r e s e a r c hi s i m p o r t a n tb o m t h e o r e t i c a l l ya dp r a c t i c a l ly k e y w o r d s ：a m f i d a li n t e l l i g e c ep 1 a n n i n g ；p l 咖j 1 1 9g r a p h ；f a s t f h w a r d ；h e u r i s t i c s e 盯c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：茎盔缸日期：碑日型宣 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：j l ：i l 生缸指导教师签名： 同 期：盈! i 丕i j 苗叠日 期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 引言 在人工智能研究中，智能规划( a ip 1 a n n i n g ) 实际上就是一种问题求解 技术，即从某个特定问题的初始状态出发，发现一系列行为或构造一系列操作 ( 也有称之为算子的) 步骤，达到解决该问题的目标状态。智能规划是人工智 能领域被较早研究的方向之一，它的研究起初源于问题求解，由于其广泛的实 用性，受到研究者的高度重视。人们对于它的研究可以追溯到6 0 年代：1 9 5 7 年n e w e l l 和s i m o n 的通用问题求解程序( g p s ) ，1 9 6 9 年g r e e n 的q a 3 系统“3 。 1 9 7 1 年f i k e 和n i l s s o n 的s t r i p s “1 系统在智能规划领域中具有划时代的意义， 它使得规划可以非常容易地进行描述和操作，但由于受到当时客观条件的制约， 该领域一直处于较为保守的状态；近几年来，随着客观条件的改善，多个国家 特别是一些发达国家在此领域取得了长足的进展，规划技术在国防和空间技术 领域中得以应用，取得了巨大的经济和社会效益。n a s a 于1 9 9 9 年在航天器“d e e p s p a c eo n e ”中运用规划技术，使得规划研究从实验室向实际应用迈出了重要的 一步，标志着规划的研究步入了实用阶段，在人工智能领域形成了智能规划这 一当前研究的热点，但是在我国关于规划理论和应用的研究现在还处于初级阶 段。 在智能规划的发展史上出现过两个里程碑式的方法：规划图“”和启发式状 态空间搜索”1 。这两个理论现在仍然是智能规划研究中占主导地位的方法“3 。基 于这两个原理的智能规划算法f f 在第2 届和第3 届世界规划器比赛中都取得了 令人瞩目的成绩“。 本文首先对智能规划进行了概括地介绍，分析了目前智能规划的研究现状 和应用情况，着重介绍了规划图理论和启发式状态空间搜索原理。然后深入的 研究f f 规划算法，对该算法的缺点进行了分析，着重分析了它对死点处理的不 合理性。在对f f 规划算法深入理解的基础上，针对其缺点提出了改进方法。本 篇文章的结构如下：第一章主要是对智能规划进行了概述；第二章主要介绍了 图规划方法；第三章主要介绍了f f 规划算法并对其做了分析；在第四章提出了 新的规划算法并将它与阡规划算法进行了比较。第五章给出了我们的新算法与 f f 在相同的问题域中进行比较的实验数据。 第一章智能规划概述 1 1 智能规划的基本概念 规划过程是种问题求解方法，一个规划系统我们可以认为就是一个问题 求解系统，若用它求解比较复杂的问题，即可求得一个动作序列( 串行、并行 或串并行混合) ，依次执行此动作序列可以完成某一特定的具体任务，最终达到 一个特定目标。在人工智能的研究中规划是其较早的研究领域之一。它的研究 可以追朔到6 0 年代：1 9 5 7 年n e w e l l 和s i 0 n 的问题求解程序( g p s ) 、g r e e n 的q a 3 系统( 1 9 6 9 ) “1 。1 9 7 1 年f i k e 和n i l s s o n 的s t r i p s 系统“1 在智能规划 领域中具有划时代的意义，这使得规划可以非常容易地进行描述和操作，但由 于受到当时客观条件的制约，该领域一直处于较为保守的状态。但是由于其广 泛的实用性，受到研究者的高度重视，特别是近几年来，随着客观条件的改善， 世界上特别是一些发达国家在此领域获得了长足的发展，已经开发出来了获取 和使用特定领域控制信息的有效方法，并且有了些实用的规划器( p l a n n e r ) ， 它们能够在数分钟内合成包括上百条动作的规划，并且在国防和空间技术领域 中得以成功地应用，取得了巨大的经济和社会效益，n a s a 于1 9 9 9 年在航天器 “d e e ps p a c eo n e ”中运用规划技术，使得规划研究从实验室向实际应用迈出 了重要的一步，标志着规划的研究步入了实用阶段，智能规划已经成为人工智 能领域研究的热点。 一方面，智能规划是一个多领域交叉的研究领域，它涉及知识表达、知识 推理、非单调逻辑、情景演算、人机交互和知识挖掘等各个方面。在人工智能 领域，规划目前还没有一个统一的定义，m c d e 珈o t t 和j 鲫e sh e n d e l e r 。3 认为 “规划就是设计某个( 组) 实体( e n t i t y ) 的动作序列，其结果被称之为规划 解( p l a n ) ”。一个规划解实质上就是一个动作序列，此序列能够实现某一日标， 智能规划就是设计这个动作序列的过程，也就是说它主要解决怎么样做，而不 解决为什么。 一般地，我们在做规划之前，大多做以下的假设： 1 规划是动作的序列。 2 2 动作的执行前件是确定的。 3 动作的执行后件( 效果) 是确定的。 通常，我们把满足以上假设的规划称之为“经典的规划”( c l a s s i c a l p l a n n i n g ) ，例如地图着色问题、积木世界问题等都是经典的规划问题。现在， 大多数研究者还在采纳此假定，但是由于现实世界的复杂性，实际闯题往往并 不能满足上述条件，因此也有一部分人正在研究放宽此假定，研究在环境不断 变化情况下的规划问题，不满足此假定的规划问题称之为“非经典的规划” ( n o n c l a s s i c a 卜p l a n n i n g ) 。 由上面的讨论我们可以看到，规划问题由于其自身的特点，它至少包括三 个部分：初始状态、目标状态和动作。初始状态和目标状态是规划问题的起点 和终点，动作是可能由初始状态到达目标状态的一系列可以执行的动作。初始 状态和目标状态属于状态的描述，一般用一阶逻辑或命题逻辑来表示。动作( 也 有叫操作的) 主要包括三部分：动作名称、动作前件和动作后件。 q i a n gy a n g “1 把s t r i p s 规划问题定义为一个三元组： ， 其中，i n i t 是初始状态文字的集合，即初始世界模型：g o a l 是目标状态文字， 即目标状态模型；o 是规划操作( 动作) 的集合，也有的称之为域理论。 1 2 智能规划的发展 人们对智能规划的研究已经有半个世纪了，最早可以追朔到1 9 5 6 年 n e w e l l 、s h a w 和s i m o n 设计的逻辑理论家( l o g i ct h e o r i s t ) 程序，这个系统 采用了启发式信息和反向搜索技术，随后他们设计的g p s 系统把领域知识与一 般的搜索控制信息相分离，上述两个系统特别是g p s 在人工智能领域中具有非 常重要的地位，但它们还不是真正面向规划问题研制的智能规划系统。 1 9 6 9 年g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统“1 ，这一系统被大多数的智能规划研究人员认为是第一个规划器，原因就 在于他是第一个面向现实规划问题提出的规划系统；1 9 7 1 年f i k e s 和n i l s s o n 设计的s t r i p s 系统0 1 在智能规划的研究中具有重大的意义和价值，他的突出贡 献是引入了s t r i p s 操作符的概念，使得原来很神秘的规划问题求解变得明朗清 晰起来；此后到1 9 7 7 年先后出现了 i 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 渊l i n 等规划系统。这个十年时间人们研究智能规划的兴致比较高，普 遍认为规划问题必须用定理证明的理论来解决，直到c h a p m a n 设计的规划系统 t w e a k 出现。由于c h a p i i l a n 的分析，使人们认识到简单地利用定理证明的方法 来解决规划问题是很难的，因此这以后到1 9 9 0 年间，在人们发现新的求解方法 3 之前，对智能规划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a k 和p r o d i g y 等较少的智能规划器出现。 1 9 9 2 年k a u t z 等把规划问题求解转化为可满足( s a t ) 问题。“，一反定理 证明式求解方法，利用在约束可满足问题算法上的突破，有效地解决了部分规 划问题。后来，基于此理论的b l a c k b o x 规划器。“在第一届智能规划器的比赛( 参 见附录a ) 中表现了非凡的解决问题能力，一举夺魁，开辟了解决规划问题的 又一新途径。1 9 9 5 年a v r i mb 1 u m 等设计的图规划系统g r a p h p l a n 测第一次采用 图的方式来解决规划问题，并且提出了用于规划的规划图的概念。后来很多规 划系统都借鉴了图规划系统的方法，参加第一届智能规划比赛的规划器除委内 瑞拉的h s p 外，其它四个规划器s g p 、b l a c k b o x 、i p p 和s t a n 都或多或少地采 用了图规划的某种( 些) 技巧，并且对图规划做了相应的扩充：s g p 加入了用 户互操作界面；b 1 a c k b o x 则综合了基于规划图的快速规划扩展和基于s a t 的快 速规划验证的优点；i p p 扩充了图规划的问题描述语言，支持a d l 规划描述语 言，它能够处理条件效果等，这样它的表达能力比图规划器要强大；s t a n 在减 少搜索和构造规划图的费用上做了扩充。这些规划算法都是部分序或非线性的 通用规划器，此次比赛表明部分序方法在规划求解中具有举足轻重的地位。两 年以后，在第二届规划比赛( 参见附录b ) 上，部分序规划的思想得到了进一 步验证，并且在规划过程中规划知识被人们广泛关注。在参加比赛的十六种规 划器中采用启发式知识的有十一个，并且采用启发式知识的规划器比没有采用 启发式知识的规划器得到的规划解效果好：例如比赛评委评选出的最佳规划器 t a l p l a n n e r 和f f ，以及排名其次的s t a n 、h s p 2 、m i p s 和s y s t e mr 都是采用启 发式知识的规划器，在此次比赛中采用启发式知识的规划器表现出很强的问题 求解能力，而第一届比赛的冠军b l a c k b o x ( g r a p h p l a n + s a t ) 则由于没有采用启 发式知识在此次比赛中表现不如人意。“”1 。 综上所述，规划问题求解从最初的定理证明方法到s t r i p s 方法是问题求解 方法上的转变，然后又发展了非线性规划器，采用目标导向的方式来生成规划： 一方面使得规划的生成速度大大提高；另一方面，由于是目标导向的生成方式， 因此生成规划的质量比较好。现在人们又在此基础上加入了启发式信息，进一 步提高规划求解的效率和质量。 1 3 规划问题描述语言 规划问题的定义是规划问题求解的前提，如果一个规划问题不能通过规划 语言来表示，则任何一个规划器都不能对它进行求解，所以说规划语言的发展 4 是智能规划发展的关键。1 9 7 1 年f i k e 和n i l s o n 的s t r i p s 。3 系统在智能规划中 具有划时代的意义，因为它使得规划可以非常容易地进行描述和操作。但随着 规划技术的应用，人们发觉s t r i p s 表示的表达能力非常地有限，它不能满足一 些实际问题的模型化要求。设计一种能够刻划、模型化一个实际问题的规划问 题定义语言成为了规划技术应用的关键，1 9 9 6 年e p e d n a u l t 9 3 提出了动作描述 语言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 r m o t t “” 提出了规划领域定义语言( 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 p e t i t i o n ，i p c ) 的标准。p d d l 语言不仅给出了 规划问题定义的语法，也从语义的角度给出了规划的定义。p d o l 语言的表达能 力非常强，能够刻画规划问题的时间和数值方面的属性，超过了现有的规划器 所能处理的表达能力，给规划器的发展提出了挑战，指明了发展的方向。 规划语言也是规划领域的一种交流和沟通的标准，对于不同的规划器我们 可以通过它们对同一规划问题的处理来进行比较。 1 3 1s t r i p s 表示 s t r i p s 。1 是一个非常著名的规划器，它代表“斯坦福研究委员会问题求解 器”，造于2 0 世纪7 0 年代，用来控制不稳定的可动机器人。s t r i p s 系统在智 能规划中具有划时代的意义，因为它使得规划可以非常容易地进行描述和操作。 规划问题的一种简单的形式化方法是定义三个输入： ( 1 ) 用某种形式语言对该领域的初始状态的描述； ( 2 ) 用某种形式语言对目标的描述； ( 3 ) 可能被执行动作的描述( 也用某种形式语言) ，这个描述通常被称为域 理论。 s t r i p s 表示定义了“经典”的规划问题，它用一系列完整的基本字来描述 域的初始状态，并且将目标定义为一个合取命题，所有满足目标形式的域状态 将被同等地考虑。在s t r i p s 表示中，每个动作用一个合取前提和合取结果来描 述，它们定义了从域到域的过渡函数。动作能在满足前提公式的任何域w 中执 行，执行的结果通过描述域w 状态，为动作结果的合取依次地添加描述动作效 果的实字，除去过程中的矛盾实字。 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 提出了动作描述语言 d l ( a c t i o nd e s c r i d 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 的表达 能力外，还能表达条件效果、量化效果等语言特征。条件效果是动作描述中与 上下文相依赖的效果，一般用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 r m o t t 提出了规划领域定义语言p d d l 。 p d d l 是一种以动作为中心的语言，它的实质是表达使用前件和后件来描述 动作的可使用性和效果的动作的语法标准。一个规划问题由一个域描述和一个 问题描述组成。同一个问题域可以许多不同的问题描述一起组成同一问题域的 不同规划问题。动作的前件和后件表达成由谓词、项和逻辑连接词组成的逻辑 命题。 p d d l l 2 “”是1 9 9 8 年第一届国际智能规划比赛使用的规划语言，它只是简 单地给出了如何定义规划问题的域及规划问题的语法标准，并没有给出规划的 语义。p 叻l 1 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 也能表达该问题。 艟a r i af 0 xa n dd e r e kl o n ”于z 0 0 2 年的第三届规划器比赛中提出了 p d d l 2 1 ，它去掉了p d d l l 2 中不常使用的部分，增加了数值表达、规划尺度和 持续动作等新的表达能力。p d d l 2 1 的表达能力可以分为5 个层次，第一层是 p d d l 2 1 的s t r i p s 部分；第二层是数值表达部分；第三层是离散的持续动作； 第四层是连续的持续动作；第5 层是p 叻l 2 1 的所有扩展及能够支持自发事件 6 和物理过程模型化的附加组件。它的表达能力超出了目前规划器所能处理的表 达能力，给规划研究者们提出了新的挑战。p d d l 2 1 与p d d l 前面的版本兼容。 p 叩l + “”是对p 叻l 2 1 的第5 层的描述，它引入了两个附加的模型化部件： 过程和事件。过程和事件的引入意味着那些用于持续动作来模型化的领域特点 在l e v e l 5 可以使用由起始点、过程和结束点三部分组成的结构来进行模型化， 在起始点和结束点可以运用动作或事件，也可以是活跃过程的效果导致一个数 值到达关键阈值的点，这称为s t a r t p r o c e s s s t o p 模型。在p d d l + 的第5 层， 动作具有瞬时的效果，它将改变问题域中的逻辑状态，动作可以开始一个过程； 而一个过程在随着时间修改状态的数值部分时将保持一个状态的逻辑部分。动 作与过程的区别：动作导致状态转移，而过程则不会导致状念转移：动作与事 件的区别：问题域设计者在把它们标识为事件来阻止规划器在提取一个规划时 选择它们；过程和事件的区别：事件的数值后件中不能有与时间相关的效果， 而过程的数值后件通常是与时间相关的效果。一个过程可以由一个动作或由出 现在世界中的某一事件来结束。 p d d l 2 2 “”保留了p d d l 2 1 的前三层的表达能力，新增了导出谓词和初始化 时间命题两种表达能力。 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 aa n dn a u 1 9 9 2n 7 1 ) 。 领域无关的规划问题是p s p a c e 完全问题或更难( c h a p m a n 1 9 8 7 “： b y l a n d e r1 9 9 1m 3 ) 。 b e r n h a r dn e b e l 于1 9 9 4 年证明了规划问题是n p 难题“。 s e l m a n 于1 9 9 4 年进一步指出：类似于规划的问题是n p 完全的或更难的“。 7 现在所能解决的规划问题还有很大的局限性，也正因如此，规划问题的研 究才具有很大的挑战性，使得一些人工智能方面的研究者乐此不疲。 1 ，5 规划研究项目和有关的会议情况 与规划相关的主要项目( 计划) 情况： 1 ) 美国国防部高级研究计划局d a r p a ( d e f e n s ea d v a n c e dr e s e a r c h p r o j e c t sa g e n c y ) 和r o m e 实验室的d a r p a r o m ep 1 a n n i n gi n i t i a t i v e ( a p r i ) 计划删 在1 9 9 1 年2 月该计划正式启动，主要针对军事中空军规划问题进行研究， 现在已进行到第六阶段，目前为止总投资额已经超过7 千万美元，同时该项计 划也产生了巨大的社会经济效益，据1 9 9 4 年美国政府的一份商业报告称：仅后 勤支援计划d a r t ( a r p i 的部分) 这一子项目在沙漠风暴行动中的应用价值就 足以抵上政府在a i k b s 研究中过去3 0 年所投资的总额m 1 。美国一流的科研机 构和著名的公司都参加了该计划，主要有：布朗大学、卡乃基一梅隆大学、 i s x 公司、k e s t r e l 学院、西北大学、洛氏国际( r o c k w e l l ) 、s r i 国际、斯 坦福大学、夏威夷大学、马里兰大学、俄勒冈大学和华盛顿大学等。 2 ) 欧洲p l a n e t 计划“” 此项计划开始于1 9 9 8 年1 0 月1 号，是由e s p r n 基金资助的，目前已经有 1 4 个国家共5 8 个高校、科研所和企业参加了这一计划，在欧洲这是一个非常 庞大的计划，投入了巨大的人力、物力和财力，目前参加的国家包括：比利时、 塞浦路斯、法国、德国、希腊、匈牙利、意大利、荷兰、挪威、葡萄牙、西班 牙、瑞典、瑞士和大不列颠联合王国。这些国家著名的高等学府、科研机构大 都参加了这一计划。 3 ) 美国国家航空和宇宙航行局也投入了大量的人力、物力，开展关于规划 理论及其应用的研究，并且将之应用于宇宙飞船等航空器上“。 4 ) 英国的国家航空和宇宙航行局也赞助了e u m e t s a t 项目“”。 这些项目有力地推动了规划理论和应用的研究，世界上关于智能规划的专 题会议等活动也渐渐地增多起来，目前比较重要的会议有：两年一届的a i p s 会 议、e c p 欧洲规划会议、美国国家航空和宇宙航行局举办的n a s a p s 、i j c a i 中 也有专门针对规划问题的专题讨论等等。 8 第二章规划图 2 1 图规划( g r a p h p ia n ) 方法 1 9 9 5 年b 1 u m 和f u r s t 。“提出了种基于规划图的快速规划方法一一图规 划，其代表有美国卡乃基一梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的图规 划嚣g r 即h p l a n ( b l u m 和f u 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 等) 。 先来介绍几个概念： 有效( v a l i d ) 规划解：规划问题的一个有效规划解是一个动作的集合和对 每一个动作发生时间的指定。 规划图( p l a n n i n gg r a p h ) ：是一个具有两类节点和三类边的有向、分层图。 规划图各层是命题层( 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 ) 交替出 现的，命题层包含命题节点( 标识为一些命题) ，动作层包含动作节点( 标识为 动作) 。三类边是前提条件边( p r e c o n d i t i o ne d g e ) ，添加效果边( a d de d g e ) 和删除效果边( d e l e t ee d g e ) 。规划图的第一层是命题层，包括规划问题初始 条件下的所有命题。 图规划在两个阶段( p h a s e s ) 交替进行：图扩展( g r a p he x p a n s i o n ) 阶段和 解提取( s 0 1 u t i o ne x t r a c t i o n ) 阶段。图扩展阶段正向扩展规划图直到目标状态 的所有命题都出现为止。解提取阶段反向搜索规划图以求出规划解。如图2 一l 所示：黑圆点代表命题节点，空白方框代表动作节点。 ， 、- 图2 一l 这里以s t r i p s 规划问题型( 动作的前件和后件都是确定的文字的合取) 为 例，结合图例大致介绍这一方法，为了简化规划图的规模，b l u m 和f u r s t 定义 了规划图中节点的两元互斥关系，如图2 2 所示： 9 第i 层两个动作实例( a c t i o ni n s t a n c e ) 满足以下三者中的任意一个时， 我们称之为具有互斥关系： 后件( 效果) 不一致( i n c o n s i s t e n t ) ：一个动作的后件是另个动作后件 的否定。 冲突 i n t e r f e r e n c e ) ；一个动作删除另一个动作的前件。 竞争所需( c o m p e t i n gn e e d s ) ：两个动作具有i l 层互斥关系的前件。 第i 层的两个命题( p r o p o s i t i o n s ) 具有互斥关系，当： 一个命题是另一个的否定或： 不一致支持( i n c o n s i s t e n ts u p p o r t ) ：获得此命题的所有动作( 方法) 都 具有互斥关系。 显然上述关系不具备传递性。 雾毒鞫菸毳鸯 1 n c o n s i s t e n te 虢c t s l n 鼬r e n c 。 c 0 m p e t i n gn e e d s i n s i s t e n ts u p p o n 图2 2 考虑以下问题：给睡眠中的爱人准备一个惊喜，要求把垃圾( g a r b a g e ) 带 出去，做好正餐( d i n n e r ) ，准备好一份礼物( p r e s e n t ) 。 初始条件：( a n d ( g a r b a g e ) ( c l e a n h a n d s ) ( q u i e t ) ) 目标：( a n d ( d i n n e r ) ( p r e s e n t ) ( n o t ( g a r b a g e ) ) ) 动作： c o o k：前件( c l e a n h a n d s )c a r r y：前件 ：后件( d i n n e r )：后件 w r a p ：前件 ( q u i e t ) ：后件( p r e s e n t ) d 0 1 l y ：前件 ：后件 1 0 () ( a n d ( n o t ( g a r b a g e ) ) ( n o t ( c l e a n h a n d s ) ) ) () ( a n d ( n o t ( g a r b a g e ) ) ( n o t ( q u i e t ) ) ) o g a r b d e a 九 a u l e t 2 u 狂嵴 瓣碚f j 翮 幽2 _ 一3 图2 3 是上述问题的部分规划图，我们注意到：动作c a r r y 与保持g a r b a g e 的动作具有互斥关系，因为他们的后件不一致；d 0 1 l y 与w r a p 由于冲突而具有 互斥关系；在第二层即命题层1q u i e t 与p r e s e n t 具有互斥关系。由于在第二 层已经获得了所有的子目标，并且它们之间没有互斥关系，因此下面可以进入 图规划的第二阶段：即解提取阶段。依次考虑目标的各个子目标，对第i 层的 每一个子目标，图规划选择第i 一1 层的获得此子目标的动作a ，此处选择是一 个回溯点：如果存在多于一个的动作能够获得此目标，那么图规划为了保证其 完整性必须考虑所有的动作，如果一个动作a 与其他的已经选择的动作是一致 ( c o n s i s t e n t ) 的，那么图规划就继续进行其他的子目标，否则如果没有这样的 选择存在，图规划就回溯到前一个选择。当图规划找到所有的实现第i 层目标 的动作后，它再把选择的动作的前件作为目标，依次进行，直到第零层，即初 始条件为止，否则返回第一阶段继续进行图扩展阶段。 在上面的例子中，在第二层有三个子目标：_ 1g a r b a g e 可有动作c a r r y 或 d 0 1 l y 来获得；d i n n e r 可有c o o k 来实现：p r e s e n t 可有w r a p 来包扎好。因此 图规划至少必须考虑两个动作的集合： c a r r y ，c o o k ，w r a p ) 和 d o l l y ，c o o k ，w r a p ) ，但是这两个集合都不一致，因为c a r r y 和c 0 0 k 、d 0 1 1 y 和 w r a p 是互斥的，因此解提取失败，图规划扩展规划图到第四层如图2 4 所示， 然后经过解提取阶段获得解规划如图2 5 所示。 玎 o q a r b 口u i e i o 234 诺到峄：。 x c a r r 蜘 uf瓣1 9 8 。j ：i d 0 i i k 飞 f l ：j 溯 恼虱一“、”c 心爨 2 3 例! 竺：瓤：ji 辩! 竺9 心 c晒( x do i i 缸、 “飞甜= 谱 f1 y 删2 ii 一婪 图2 5 已经证明图规划算法是多项式时间的。 2 2 规划图的互斥延迟算法 d 0 芝：) 我们利用相互独立集改进了建立规划图的算法，改进的基本思想是：在建 立完一动作列后，查看该动作列中是否存在互斥关系，并将没有互斥关系的动 作归入一个集合中( 称这样的一个集合叫相互独立集，即集合内的每个动作间 没有相互排斥关系) 如果该动作列的相互独立集个数大于l ，则说明独立集间 的动作有相互排斥关系。为了将这一组不可能在同一时间步内执行的动作拆分 成多个时问步内完成，我们引入了延续时间步。延续时间步的主要作用是延续 1 2 0 甜州 叭懒 懈 暮| - | 飞曲 鹏 动作的执行效果( 包括添加效果和删除效果) ，因为相互独立集间动作不能在同 一时间步同时执行，所以必须延续几个时间步以便将多个独立集拆分开。我们 把非延续时间步称为扩张时间步，为了区分这两种时间步，我们可以利用一个 动态一维数组，每添加一个时间步就增加一个元素，扩张时间步用“1 ”表示， 延续时间步用“o ”表示。这样，通过相互独立集的个数n ，我们可以知道有几 组动作相互排斥，那么通过使用n o p 动作，将接下来的命题列延续n 一1 个时间 步，在延续时间步内不考虑可能新增加的动作( 即形成动作的前提在上一命题列 中存在，且该动作在上一动作列中不存在) ，这样做的目的仅是为了将所有相互 排斥的动作组分开，放在多个不同的时间步内完成。 改进后的规划图扩张算法如下： 时间步1 的命题列的生成：将所有的初始条件作为时间步l 的命题列。 时间步l 的动作列的生成：对操作集合中的每一操作把能够实例化的都 实例化( 即只要一操作的前提条件存在于时间步1 的命题列的，该操作就可以 实例化。) 每实例化一个操作，就可以添加一个动作结点( a c t i o nn o d e ) ，这样 便得到时间步l 的动作列。同时将所有动作与其对应的前提条件用前提条件边 ( p r e c o n d i t i o ne d g e ) 连接起来。时间步的动作列确定以后，查看该动作列中 动作间的相互排斥关系，例如我们可以用一个二维矩阵来表示，称其为相互排 斥矩阵。通过该矩阵我们就可以找出各相互独立集，再根据相互独立集的个数， 若大于1 ，则接下来便是延续时间步，反之，则接下来的就是扩张时间步。 延续时间步：延续时间步内保留上一时间步的所有非n o p 动作，并添加 所有的n o p 动作( 命题列中的每个命题都可以通过n o p 动作延续到下一时间步) ， 自然接下来生成的命题列与上一命题列完全相同，这便达到了延续作用，但需 注意的是，这并不属于后面所说的规划图稳定状态。 扩张时间步：如果此扩张时间步是紧接在延续时间步之后的，那么该扩 张时间步内则不考虑上一延续时间步内所有非n o p 动作，只须添加新增加的动 作及n o p 动作。如果此扩张时间步是接在扩张时间步之后则按时间步1 动作列 生成方式一样生成动作列。扩张时间步的命题生成之后，查看其间是否包含所 有目标命题，若是，则表示规划图扩张完成；否则，查看该命题列是否与上一 命题列相同，若是，则表示规划图稳定，目标命题不能实现，规划图扩张结束； 若不是，则继续进行下去，查看相互独立集，确定下一时间步是延续时间步还 是扩张时间步，直到目标实现或规划图稳定。 在改进后的规划图扩展的算法中，对扩张时间步和延续时间步进行了区别 对待，这也用于搜索有效规划的算法中。在从后往前的搜索过程中，当遇到延 续时间步时，则可直接选取该时间步的一个相互独立集中的动作，这样会提高 搜索有效规划的效果。 2 3 图规划下的条件效果 条件效果。”是动作描述中与上下文相依赖的效果，一般用一个w h e n 子旬来 表示条件效果。w h e n 子句有两部分：前提( a n t e c e d e n t ) 和结论( c o n s e q u e n t ) 。 w h e n 子句的执行就像动作的执行一样，只有当在执行前，它的前提满足时才能 被执行，并产生结论中的效果，如果把动作的前提看成是主前提的话，那么w h e n 子旬的前提则是次要前提( s e c o n d a r yp r e c o n d i t i o n ) 。例如搬公事包 ( m o v e b r i e f c a s e ) 这个动作： m o v e b r i e f c a s e