（计算机应用技术专业论文）以目标为导向的时序图规划算法的研究.pdf

摘要 智能规划是当前人工智能领域中极为活跃的一个研究热点，它已广泛应用于自主机 器人、航空航天、自然语言理解、知识推理、人机交互、数据挖掘等许多高技术领域。 虽然它的一些理论问题与应用问题是世界上公认的难题，但多年来国内外优秀学者一直 致力于这一方向的研究，特别是美国卡耐基梅隆大学的a l b l u m 教授和m l f u r s t 教 授利用规划图分析提出的图规划方法，第一次采用图的方式来解决规划问题，在智能规 划领域中取得了革命性进展。近年来，智能规划研究发展飞速。2 0 0 2 年，第三届国际规 划竞赛召开，值得注意的是，这次大赛集中考察了规划系统对时序和数值问题的解决情 况。时序规划问题是一类较难的规划问题，但它更接近现实世界的实际问题，因此引起 了众多规划研究者的关注，纷纷投入到时序规划的研究中。目前已经有几个基于图规划 算法的规划器可以成功地解决时序规划问题，如t g p ，t p s y ，l p g p 。 基于图规划的时序规划算法虽然具有很多优点，但也存在一些局限。比如，它的搜 索是从初始状态出发，搜索可能为真的所有命题，这样当初始状态中包括很多与目标不 相关的命题，或初始状态可应用的动作数量过多而导致规划图过宽时，图规划算法的性 能就会急剧下降。为了克服图规划的这一缺点，作者在对时序图规划深入研究的基础上， 提出了以目标为导向的时序图规划算法。 本文针对规划领域中比较复杂的一类问题时序规划问题展开研究，对以下内容 进行了创新性研究： 本文系统地回顾了智能规划的研究历史，深入地介绍了在图规划框架下智能规划的 研究工作，同时，全面地展示了智能规划技术的研究现状及未来的发展方向。 提出了一种从目标集扩张时序规划图的新算法。该算法与现有算法不同，采用逆向 扩张、正向搜索的策略；由于扩张保留了关于目标的信息，实现了动作方案的完全量化。 因此在搜索阶段，只搜索相关可用动作的交叉点，减少了搜索代价，极大地提高搜索效 率。这种算法使处理的规划问题从理想向现实迈进了一步，因此在解决实际问题中，具 有其独特的优势。 由于智能规划技术本身的独立性，开展对智能规划算法的研究，对于竞赛机器人、 游戏角色设计、智能用户接口的设计、自然语言理解以及多a g e n t 系统等许多领域的研 究也有广泛的应用前景。 关键词：人工智能；智能规划；图规划；时序规划：目标导向 a b s t r a c t n o w a d a y s ，i n t e l l i g e n tp l a n n i n gi sav e r yh o tb r a n c hi na ib e c a u s eo fi t sw i d ea p p l i c a t i o n i n h i g h t e c h n o l o g yf i e l d s s u c ha sa u t o n o m o u s r o b o t s ，s p a c e c r a f t ，n a t u r a ll a n g u a g e u n d e r s t a n d i n g , k n o w l e d g ei n f e r e n c e ，h u m a n - m a c h i n ei n t e r a c t i o n ，d a t am i n i n ge t c s o m e p r o b l e m si nt h e o r ya n d i np r a c t i c ea r ei n t e r n a t i o n a lp u z z l e s ，b u tal o to ff a m o u ss c h o l a r sh o m e a n da b r o a ds t i l ld e v o t et h e m s e l v e st ot h er e s e a r c h s p e c i a l l y , p r o f e s s o ra l b l u ma n d p r o f e s s o rm l f u r s tp r o v i d e dt h eg r a p h p l a na l g o r i t h m ，w h i c hc a u s e dr e v o l u t i o n a r yp r o g r e s s i nt h ei n t e l l i g e n tp l a n n i n g r e c e n t l y ，t h er e s e a r c h i n go fi n t e l l i g e n tp l a n n i n gd e v e l o p sa tv e r y f a s ts p e e d t h et h i r di c a p sc o n v e n e di n2 0 0 2 ，t e m p o r a la n dn u m e r i c a lp l a n n i n gp r o b l e m sa r e m a i n l yc o n s i d e r e di nt h ec o n f e r e n c e t e m p o r a lp l a n n i n gp r o b l e m sa r ed i f f i c u l ti np l a n n i n g d o m a i n s ，b u tt h e ya p p r o a c ht h er e a lw o r l dp r o b l e m s ，s om o r ea n dm o r er e s e a r c h e r sg i v e a t t e n t i o nt ot h e m s o m ep l a n n e r sf o rt e m p o r a lp l a n n i n gp r o b l e m sa r ed e v e l o p e d ，w h i c ha r e b a s e do ng r a p h p l a n , s u c ha st g p , t p s ya n dl p g e t h et e m p o r a lp l a n n i n ga l g o r i t h m sb a s e do ng r a p h p l a nh a v es o m ea d v a n t a g e s ，a n dt h e y a l s oh a v es o m er e s t r i c t i o n f o re x a m p l e ，t h es e a r c h i n ga l g o r i t h m sb e g i na tt h ei n i t i a ls t a t e ， a n ds e a r c ha l lp r o p o s i t i o n sw h i c ha r el i k e l yt ob et r u e i nt h e s es i t u a t i o n s 。i ft h e r ea r e i r r e l e v a n tp r o p o s i t i o n st og o a l si ni n i t i a ls t a t eo rt h ep l a n n i n gg r a p hi so v e r s i z eb e c a u s eo ft h e o v e r a b u n d a n c ea c t i o n sf o ri n i t i a ls t a t e ，t h ep e r f o r m a n c eo ft h ea l g o r i t h mw i l ld e s c e n dr a p i d l y t os o l v et h i sp r o b l e m ，w ep r o p o s ean e wa l g o r i t h mf o rt e m p o r a lp l a n n i n gp r o b l e m s t h i sp a p e rm a k e sr e s e a r c ho nak i n do fc o m p l e xp l a n n i n gp m b l e m s _ 一t e m p o r a l p l a n n i n gp r o b l e m s t h ef o l l o w i n go r i g i n a lr e s e a r c h e sa r ec a r r i e do u t ： t h ep a p e rs y s t e m a t i c a l l yr e v i e w st h eh i s t o r yo fi n t e l l i g e n tp l a n n i n g ，t h o r o u g h l ys t a t e s r e s e a r c hi nt h eg r a p h p l a nf r a m e w o r k ，o b j e c t i v e l ys h o w st h ec u r r e n ts t a t ea n ds u g g e s t sa r e a s f o rf u t u r er e s e a r c h t h ep a p e ra p p l i e san o v e li n t e l l i g e n tp l a n n i n ga l g o r i t h m i nc o n t r a s tt ot h ee x i s t i n g m e t h o d s ，t h ea l g o r i t h me x p a n d st h et e m p o r a lp l a n n i n gg r a p hb a c k w a r d sf r o mt h eg o a ls e ta n d s e a r c h e sav a l i dp l a nf o r w a r d s ，p e r f e c t st h ea p p r o a c ho fb a c k w a r df l e x i b l em u t e xi n f e r e n c e ， t h em e t h o dm a k e st h es o l u t i o np l a nm o r eq u i c k l yf o rt h es e a r c h ，a n dh a n d l e st h ep l a n n i n g p r o b l e m sm u c hc l o s e rt o t h er e a lw o r l d t h e r e f o r e ，t h em e t h o dh a si t sa d v a n t a g eo v e r p r e v i o u so n e si na p p l i c a t i o n b e c a u s eo ft h ed e p e n d e n c yo fi n t e l l i g e n tp l a n n i n g , o u rr e s e a r c hh a sw i d ea p p l i c a t i o n o u t l o o ko nr o b o t o l o g y , i n t e l l i g e n tu s e ri n t e r f a c ed e s i g n ，n a t u r a ll a n g u a g eu n d e r s t a n d i n g , m u l t i - a g e n ts y s t e m se t c k e yw o r d s ：a i ；i n t e l l i g e n tp l a n n i n g ；g r a p h p l a n ；t e m p o r a lg r a p h ，l a n ；g o a l d i r e c t e d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：犀苁物日期：2 垃挚土! 蕴 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：签题 指导教师签名： 日 期：i 血么皇日 期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 引言 智能规划是一个涵盖知识表达、知识推理、非单调逻辑、情景演算、知识挖掘、人 机交互和认知科学等多领域的交叉性学科，其发展不仅对于人工智能领域具有重要的意 义，甚至会从根本上改变人类使用计算机的传统方式。规划的研究始于2 0 世纪6 0 年代， 在9 0 年代达到高潮。n a s a 于1 9 9 9 年在航天器“d e e ps p a c eo n e ”中运用规划技术，使 得规划研究从实验室向实际应用迈出了重要的一步，标志规划的研究步入了实用阶段， 智能规划已成为当前人工智能领域的研究热点。 多年来，国内外许多优秀学者一直致力于智能规划这一方向的研究，特别是美国卡 耐基梅隆大学的a l b l u m 教授和m l f u r s t 教授利用规划图分析提出的图规划方法， 第一次采用图的方式来解决规划问题，在智能规划领域中取得了革命性进展。用这种方 式解决规划问题，能使一些动作并行执行，大大提高了执行效率。图规划为智能规划技 术提供了一种快速优雅的求解方式，它拥有许多重要属性，包括健壮、稳定、合理、高 效、且建立规划图的计算复杂度是多项式时间和多项式空间等，后来很多算法都采用了 图规划的方法，比较著名的规划器b l a c k b o x 、f f 、l g p 、s g p l a n 这四届规划大赛的世界 冠军都或多或少地采用了图规划的技巧。近年来，智能规划的研究更是发展飞速。2 0 0 2 年，第三届国际规划竞赛召开，值得注意的是，这次大赛集中考察了规划系统对时序和 数值问题的解决。目前已经有几个基于图规划算法的规划器可以成功地解决时序规划问 题，如t g p ，t p s y ，l p g p 。时序图规划( t g p ) 是由美国国家航空局埃姆斯研究中心的 d a v i de s m i t h 和华盛顿大学的d a n i e ls w e l d 提出的，该方法可以看作对人工智能 规划领域问题求解综合能力的提升和对原有的规划定义的扩展。虽然它的一些理论问题 与应用问题是世界上公认的难题，但由于它在实际应用中有着良好的前景，因此吸引了 众多研究者，使其成为目前智能规划中的一个研究热点。 本文在时序图规划框架下，对以下内容进行了创新性研究： 系统地回顾了智能规划的研究历史，深入地介绍了在图规划框架下智能规划的研究 工作，同时，全面地展示了智能规划技术的研究现状及未来的发展方向。 现有的时序规划算法各有千秋，但有其共同点：先从初始状态出发向目标状态扩张 规划图，再逆向搜索有效规划。本文提出了一个全新的算法：从目标状态向初始状态扩 张规划图，之后进行正向搜索，这种方法称为以目标为导向的时序图规划算法( g d t g p ) 。 该算法完善了逆向互斥推理的策略，大大地提高了搜索效率，这种算法使处理的规划问 题从理想向现实迈进了一步，因此在解决实际问题中，具有其独特的优势。 本文首先对智能规划进行了概括地介绍，分析了目前智能规划的研究现状和发展情 况，然后深入地研究了时序图规划理论。在对智能规划和时序图规划深入研究的基础上， 提出了以目标为导向的时序图规划算法。 1 1 智能规划发展历史 第一章智能规划 智能规划是人工智能中研究较早的一个领域，它的研究最早可以追溯到2 0 世纪5 0 年代后期，当时人们利用程序来模拟人类的问题求解能力。作为此目的的第一个系统是 由n e w e l l 和s i m o n 设计的逻辑理论家程序，随后他们又设计了通用问题求解器( g p s ) “1 ，这个系统把领域知识与一般的搜索控制信息相分离，采用分析当前状态和目标状态 间差别的启发式方法来执行状态空间搜索，它在人工智能领域中具有非常重要的地位。 在2 0 世纪6 0 年代末，g r e e n 提出使用定理证明的方法来构造规划，并基于此理论 设计了q a 3 系统0 1 ，因为它是第一个面向现实规划问题提出的规划系统，所以被大多数 智能规划研究人员认为是第一个真正的规划器。然而，由于当时定理证明技术的不成熟， 这种方法不久就被舍弃了。 2 0 世纪7 0 年代出现了非线性规划( 部分序、因果链接) 方法，它在域独立规划中 占有主导地位，该方法直到2 0 世纪9 0 年代中期仍深受欢迎。“”。基于此方法，1 9 7 1 年f i k e s 和n i i s s o n 设计了s t r i p s ”1 规划系统，它是历史上最具影响力的规划系统之一。 在s t r i p s 域中，状态是公式的集合，状态描述的改变由操作从集合中添加和删除公式 来实现，搜索使用类似于g p s 系统的启发式方法。这一系统采用的与文字相关的术语直 到今天仍在使用，引入的s t r i p s 操作符使得规划可以非常容易地进行描述和操作，原 来很神秘的规划问题求解从此变得明朗清晰起来。此后至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 等规划系统。 2 0 世纪8 0 年代，对智能规划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a k 0 1 和 p r o d i g y 吲等智能规划系统出现。人们通过使用模态逻辑和动态逻辑从理论上对演绎规划 进行了调整，但这些工作对于规划算法的发展所起到的作用微乎其微。1 9 8 7 年， c h a p m a n 在此基础上详细全面地分析了利用定理证明理论解决规划问题中的关键问题： 模型与规划解的对应关系，提出了著名的模态真值标准理论，并设计了规划系统 t w e a k “。后来随着经典命题逻辑可满足问题的发展，规划问题的演绎方法和基于逻辑 的方法在2 0 世纪9 0 年代末再次得到广泛应用。 2 0 世纪9 0 年代，规划系统的效率得到了明显提高，这种提高主要来源于规划领域 的三种新方法。第一种方法是1 9 9 2 年k a u t z 等把规划问题求解转化为可满足( s a t ) 问 题“”“”，这种方法使得命题推理系统中的新技术可以直接应用于规划系统，从而有效 地推动了规划研究：第二种方法是1 9 9 5 年由b l u m 和f u r s t 提出的图规划“4 ，这种方 法第一次采用图的方式来解决规划问题，开辟了规划求解的新途径，使智能规划领域取 得了革命性进展“；第三种方法是1 9 9 8 年由b o n e r 和g e f f n e r 提出的启发式“ ，这种 2 方法利用启发式函数来指导状态空间搜索，实践证明采用启发式的规划器比没有采用启 发式的规划器表现出了更强的问题求解能力，比较典型的规划器如f f “”，h s p “”，g r t “”， a l t a l t 1 ，m i p s 。“2 2 和s t a n 。”都采用了启发式搜索的思想。另外，需要关注的是，在1 9 9 8 年两年一次的国际规划竞赛首次召开，再一次掀起了规划研究的热潮，大赛为规划器的 优劣提供了测试平台，对智能规划的理论研究起到了巨大的推动作用。 进入2 1 世纪以来，到目前为止国际规划竞赛又成功地召开了三届，不断涌现出杰 出的规划器，在理论上也取得了很多重大突破。目前，规划系统对时序和数值问题的求 解能力已引起人们的普遍关注，最新的规划系统大都考虑了对资源约束的处理。由于智 能规划研究的难度大、应用广，未来此领域无疑将继续成为一个富有挑战性的国际研究 热点和人工智能领域中最活跃的分支之一。 1 2 规划表示语言 一个问题求解系统通常由三部分组成：知识表示、存储知识的数据结构和知识推理。 知识表示是知识推理的前提。一个规划器可以看成是一个问题求解系统，自然地也由相 应的三个部分组成：规划问题的定义、存储规划的数据结构( 如规划图、状态空间图等) 及规划的搜索。规划问题的定义是规划问题求解的前提，如果一个规划问题不能通过规 划语言来表示，则任何一个规划器都不能对它进行求解，所以说规划语言的发展是智能 规划发展的关键。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 操作符使得规划 可以非常容易地进行描述和操作。但随着规划技术的应用，人们发觉s t r i p s 表示的表 达能力有很大的局限性，它不能满足一些实际问题的模型化要求。设计一种表达力更强 的规划表示语言成为规划技术应用的关键，1 9 9 6 年e p e d n a u l t 提出了动作描述语言 ( a d l ) 嘲1 ，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 ) “1 ，它逐渐地成为国际 智能规划比赛( i p c ) 的标准。p d d l 语言不仅给出了规划问题定义的语法，还从语义的角 度给出了规划的定义，能够刻画、模型化一个实际问题。p d d l 语言的表达能力非常强， 能够刻画规划问题的时间和数值方面的属性，超过了现有的规划器所能处理的表达能 力，为规划器的发展提出了挑战，指明了发展方向。 规划语言也是规划领域的一种交流和沟通的标准，通过它我们可以比较不同的规划 器在对同一规划问题处理时表现出的性能。 1 2 1s t r i p s 表示 s t r i p s 是一个非常著名的规划器，全称为“斯坦福研究委员会问题求解器”，产生 于2 0 世纪7 0 年代，用来控制不稳定的可动机器人。 一种简单的规划问题的形式化方法是定义三个输入：( 1 ) 用某种形式语言对初始状 态的描述；( 2 ) 用某种形式语言对目标的描述；( 3 ) 用某种形式语言对可能被执行动作 3 的描述，这个描述通常被称为域理论 s t r i p s 表示可以定义经典规划问题，它用一系列基本文字来描述域的初始状态，将 目标定义为命题的合取，并且考虑所有满足目标形式的状态。在s t r i p 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 提出了动作描述语 言 d l 。 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 的出现使得规划语言所能描述的问题类型增加。 i 2 3p d d l 语言 ( 1 ) p d d l 语言的提出及其背景 规划的研究逐渐地从理论研究走向实际应用，将规划技术运用到现实世界领域就涉 及到一个无法回避的问题：如何对一个实际问题模型化并进行推理。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 的核心是s t r i p s 表示，扩展的表达能力包括表达问题域中对象的类型结构， 动作和谓词中的参数类型，具有否定命题和条件效果的动作，以及在前件和后件的表达 中使用量词。 p d d l 包含了问题域对表达能力层次要求的语法描述，它通过使用r e q u i r e m e n t s 标 志来表达特定问题域描述所要求的表达能力的层次水平。这样可以使一个规划系统优雅 地拒绝那些具有它所不能处理的语言特征的问题域( 即该问题域所要求的表达能力超过 了规划系统所能处理的表达能力) 。 4 ( 2 ) p d d l 语言各个版本简介 p d d l i 2 p d d l i 2 z s l 是1 9 9 8 年第一届国际智能规划比赛使用的规划语言，它只是简单地给出 了如何定义规划问题的域及规划问题的语法标准，并没有给出规划的语义。p d d l i 2 包 含了s t r i p s 表示和a d l ，即使用s t r i p s 表示和a d l 能够表达的问题，p d d l i 2 也能表 达。 ( 至) p d d l 2 1 1 9 9 8 年后，规划技术开始逐渐走向实际应用，一个规划系统能够解决以前命题化较 难的问题域( 如积木世界、火箭问题等) 已经不再能够证明它的实用性。现代的规划器 应该能够处理时序和数值，所以需要一种能够表达时序和数值的规划语言。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 啪1 ，它去掉了p d d l i 2 中 不常使用的部分，增加了数值表达、规划尺度和持续动作等新的表达能力。p d d l 2 1 的 表达能力可以分为5 个层次，第一层是p d d l 2 1 的s t r i p s 部分；第二层是数值表达部 分；第三层是离散的持续动作；第四层是连续的持续动作；第5 层是p d d l 2 1 的所有扩 展及能够支持自发事件和物理过程模型化的附加组件。p d d l 2 1 与p d d l 前面的版本兼 容，下面具体地介绍p d d l 2 1 中几个新扩展： p d d l 2 1 中的数值表达是通过函数来实现的，原始数值表达通过领域中的函数与对 象组合而成，数值表达式是由原始数值表达和算术操作符组成的表达式。数值条件通常 是一对数值表达式的比较，可以用一个三元组 来表示，其中e x p 和 e x p 都是数值表达式，而r e l 是关系操作符( ，= ， = ) 。数值效果利用赋值操作 来更新原始数值表达，其中包括直接赋值和相对赋值。 p d d l 2 1 中引入规划尺度是为了能够更好地根据问题域的特点来评价规划的质量， 例如对于运输之类消耗资源的问题域，一个好的规划应该是尽可能的减少所消耗的能源 ( 如汽油等) ，但对于一些比较看重时间资源的问题域，总的执行时间越少则该规划的 质量越高。不同的问题域对规划质量的评价尺度是不一样的，所以引入了规划尺度，为 特殊的问题域定义相应的规划尺度来评价规划的质量。在给定的不同规划尺度下，相同 的初始状态和目标状态可能产生完全不同的最优规划。当然，一个规划器可能不选择利 用规划尺度来指导求解过程，而只是利用规划尺度来评价规划解。 规划尺度在问题描述中定义，定义过程如下： ( a ) 为了从明确的具体量( 数量) 上定义一个规划尺度，必须首先在问题域描述中 引入那个数值量：( b ) 在问题描述中加入该规划尺度；( c ) 在初始状态中将该规划尺度 的值进行初始化；( d ) 在对影响该规划尺度的动作中添加相应的数值效果。 p d d l 2 1 定义了两种形式的持续动作：离散持续动作和连续持续动作。通常认为逻 辑变化是瞬时的，因此一个连续动作的连续方面是指数值如何在动作持续时间里变化。 离散持续动作中时序关系的模型化是通过在前提和效果中添加时间注释实现的。持 续动作中的所有条件和效果必须都加上时间注释。对条件的注释明确了一个相应的命题 是否必须在间隔的起始点( 动作执行的时间点) 成立，或在间隔的结束点( 动作的所有 5 效果成立的时间点) 成立，或在起始点和结束点之间一直成立：对效果的注释明确了效 果是否是瞬时的( 即在间隔的起始点发生) ，或效果是延迟的( 即它发生在间隔的结束 点) 。在离散持续动作中，除了这几个时问点外，不能获取、访问其它的时间，所以离 散的活动发生在动作的起始点或结束点；一个持续动作中的不变前提( 条件) 要求在间 隔期间都成立，这个间隔是开区间( 不包括动作的起始点和结束点) 。离散持续动作和 连续持续动作的区别主要体现在动作效果发生的时间上。离散持续动作抽象出某些变量 连续的变化，使变化发生在执行过程的结束点上，即a ( t ) 中的t 是常量，这样做可以简 化动作模型，使动作容易处理。有些值具有连续变化的特点，如某些数值变量随时间的 变化增加或减少，如果规划器为了到达目标，能够在任意一时问点上访问这些变量的值， 动作效果就不能发生在执行过程的结束点上，这时候t 是一个连续变量，而e ( t ) 随着t 变化而变化，具有这样动作效果的持续动作称为连续持续动作。 p d d l + p d d l + 0 7 1 是对p d d l 2 1 第5 层的描述。在p d d l 2 1 的第3 层采用了一种离散的方法 模型化时间和数值变量，即在动作说明中添加一个值来表示该动作的持续时间。从某种 角度来说，这是一种比较吸引人的模型化变化事件的方法一变化的连续方面已被抽象 掉，剩下一个包含变化事件完成的关键点的模型。然而，这种方法有一些缺点：( a ) 在 一个持续动作的执行过程中不可获取一个数值变量的值信息，这意味着引用同一变量的 几个动作不能并行执行，即只是访问该变量，而不改变它的值；( b ) 如果一个动作具有 持续时间，则在没有规划器的干预下动作将在持续时间的结束点产生其效果。这阻碍了 对作为一个过程的起始动作的效果的模型化，且该动作必须明确结束。所以p d d l + 弓j 入 了两个附加的模型化部件：过程和事件。过程和事件的引入意味着那些用持续动作来模 型化的领域在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 + 中，动作具有瞬时的效 果，它将改变问题域中的逻辑状态，动作可以开始一个过程；而一个过程在随着时间修 改状态的数值部分时将保持该状态的逻辑部分。动作与过程的区别：动作导致状态转移， 而过程则不会导致状态转移：动作与事件的区别：问题域设计者把动作标识为事件来阻 止规划器在提取一个规划时选择它们；过程和事件的区别：事件的数值后件中不能有与 时间相关的效果，而过程的数值后件通常是与时间相关的效果。一个过程可以由一个动 作或由出现在世界中的某个事件来结束。 p d d l 2 2 p d d l 2 2 保留了p d d l 2 1 中前三层的表达能力，新增了导出谓词和初始化时间命 题这两种表达能力。 导出谓词在以前的一些规划系统中已经实现，如u c p o p 。导出谓词是受那些不适用 于规划器的动作所影响的谓词。然而，谓词的真值来自一些形如：i f 巾( x ) t h e np ( x ) 规 则的集合。导出谓词提供了一种简洁、方便的方法来表达对关系传递闭包的更新，这种 更新出现在那些包含一些结构的域中。 6 时间化初始文字是一种表示某种限定形式的外部事件的简单方法：规划器事先已知 将在某个时间点变为真或假的事实，与规划器动作的执行无关。时间化文字表示的是确 定性的无条件的外部事件。时间化文字跟实际应用是密切相关的：在真实的世界中，确 定性的无条件的外部事件是很常见的，具有代表性的是时间窗口的形式( 商店开门的时 间、人们上班的时间，研究会议室占用的时间等) 。 概率规划问题定义语言( p p d d l l o ) p p d d l l 0 对p d d l 进行了扩展，允许对马尔可夫决策过程( m d p s ) 的说明，如对概率 效果的支持，对马尔可夫决策过程中的奖励值的模型化等。 m d p 是决策理论研究的一个重要方面，长期应用于决策分析、运算研究中，由于决 策理论评估动作强弱程度的能力很强，而不确定规划又主要涉及动作的选择，所以决策 理论是一种处理不确定规划的有效方法。目前，绝大部分关于不确定规划的研究都集中 在马尔可夫决策过程框架下，马尔可夫决策过程模型是一个线性决策生成问题，由将一 个状态转换成一个或几个可能的后继状态的动作组成，而且转换每一个可能状态时都带 有一个概率值。在这一框架下的智能规划具有如下几个特点：( a ) 动作有一组可能的输 出；( b ) 目标和效用值相连( 经典规划下目标只能为真或假) ；( c ) 动作的每一种输出 都有一个概率值，且一个动作所有输出的概率值之和为1 。 p p d d l i 0 可以对一个具有概率效果的动作进行定义，概率效果的语法是： ( p r o b a b 订i s t i cp le i p ke 。) ，这意味着效果e 。出现的概率是p 。，要求p i 0 且。 巾严1 。一个概率效果声明是带有概率权值效果的穷举集合。 在基于马尔可夫的不确定规划中，一个状态的转移伴随着一个奖励值。在p p d d l i 0 中预留了数值变量r e w a r d 来表示从初始状态开始奖励值的累积之和，r e w a r d 的初始值 为0 ，在规划执行过程中可以访问它的值。r e w a r d 通过动作效果中的更新效果伴随着状 态转移。在p p d d l i 0 中，动作通过一个数值效果对r e w a r d 流进行更新：( ( r e w a r df l u e n t ) ，其中 是i n c r e a s e ( 增加) 或d e c r e a s e ( 减 小) ， 是一个不涉及r e w a r d 的数值表达式；在动作前提和条件效果的前项中不 涉及r e w a r d 流。 p p d d l i 0 中引入了新的要求标识：r e w a r d s 来表示对奖励值的支持。对于同时要求 概率效果( ：p r o b a b i l i s t i c e f f e c t s ) 和奖励值( ：r e w a r d s ) 的问题域可以声明为：m d p ，这 个要求标识蕴含着：p r o b a b i l i s t i c - e f f e c t s 和：r e w a r d s 。 如果在规划问题定义中没有明确定义一个规划尺度，则概率规划问题的目标描述 ( ：g o a l 由) 可以表明规划目标是实现由的概率最大。对于一个具有：r e w a r d s 要求标识 的规划问题，默认的规划目标是使期望的奖励值最大。一般来说，一个规划问题定义中 的规划尺度( ：m e t r i cm a x i m i z ef ) 意味着应该最大化或最小化规划尺度变量的期望值。 p p d d l i 0 定义了一个特殊的规划尺度g o a l p r o b a b i l i t y ，它可指定规划目标是最大化 ( 或最小化) 实现目标的概率。 7 1 2 4 规划语言的发展 规划语言是智能规划发展的关键。当前的规划器还不能完全处理规划语言的一些表 达能力，所以说规划语言的发展为规划的发展指明了方向。从s t r i p s 表示到a d l 语言 以及从a d l 语言到p d d l 语言，可以看出，规划语言的表达能力越来越强，它逐渐向实 际应用的模型化发展来增强表达能力。 1 3 现状与展望 近年来，随着应用的需要以及客观条件的改善，智能规划领域获得长足发展。在欧 美等发达国家掀起了智能规划理论研究、应用开发的热潮，有关这一理论的研究成果不 断涌现。比较成熟的模型和相应算法种类繁多，各种修正和演变的模型、算法更是层出 不穷，这些卓有成效的方法使得规划系统的效率得到了显著提高，并在现实世界中得到 广泛应用。在智能规划自身强大优势的感召下，许多学者对该方向产生了极大兴趣，关 于此领域的学术活动越来越多，异常活跃，学者们致力于使规划系统解决的问题更多、 求解的速度更快、求出的规划解更优。此领域的研究呈现出一派生机勃勃的景象，进入 了一个崭新的突飞猛进的时代。值得注意的是，目前我国人工智能和其它相关学科领域 的专家、学者、工程技术人员在智能规划理论和应用研究方面，也做出了许多可喜的成 绩。但由于规划问题的复杂性，现今仍有很多国际难题尚未解决，有着巨大的研究空间， 因此，未来此领域的研究无疑将继续作为一个富有挑战性的国际研究热点，成为深刻影 响人类的伟大工程。 以下给出几个难度很大，研究价值很高的未解决问题和未来的发展方向。 1 应对规划 长久以来，研究者主要关心的是单个智能规划系统在一个和它的能力目标相适应的 封闭环境中的反应、计划、推理和学习。然而随着网络技术和通讯技术的发展，对于一 个在开放性的复杂环境中活动的规划系统，必然会和其它系统包括其它规划系统同时产 生作用。这时，不考虑其它系统或过程的影响是不可想象的，而这种影响对于我方规划 系统可能是帮助的、中立的、甚至敌意的。 例如2 0 0 3 年1 月，美国总统布什下令制定了网络战略，以便在必要的情况下对敌 方的计算机系统发动袭击，这里对系统的攻击性动作对于防范网络攻击系统中的规划系 统便是敌意的；而基于规划机制的协作型机器人之间由于存在着共同的规划目标，相互 的动作则是互为友好的。 从本质上来讲，无论对方规划系统对于我方规划系统是友好的还是敌意的，处理的 基本方法应该只限于一种情况：根据对方的动作，做出相应的对策，最终达到自己的规 划目标。针对应对对方具有敌意动作的这类智能规划( 应对规划) 将是未来智能规划发 展的一个重要方面。 由于系统间的相互作用是不可避免的，因此对应对规划的研究不仅对于计算机系统 8 安全甚至国家安全具有重要意义，而且在系统分析和设计方法学上也具有重要的学术价 值。 目前对应对规划的模型、算法、实现的研究尚处于非常初级的阶段。 2 对象集合动态可变的图规划 十年来，人们在图规划框架下做了许多研究工作，取得很多突破，发表了一系列研 究成果。但是，到目前为止，所有这些研究都不允许动作消灭现有对象，也不允许动作 创建新的对象，即规划的对象集合是静态不变的。然而许多实际规划问题都不满足这一 条件，这就极大地限制了图规划技术的应用。打破这一限制，针对对象集合动态可变的 规划问题进行研究，将会给图规划的理论与应用带来重大影响，使其获得更加广阔的发 展空间。 3 关于资源约束的规划问题是智能规划领域中一类较难的问题，仍有很多国际难题 尚未解决，有着巨大的研究空问，目前对于此类问题的解决都基于某些较强的假设，放 宽、取消这些假设，或者开创新方法解决此类问题是目前以及未来一段时间智能规划学 者们研究的热点问题。 4 未来规划的发展除了增强规划知识表达能力外，与人的交互将是一个重要的方 向，在规划过程中允许人的干预，以指导规划器的规划过程，将具有广阔的前景和强大 的生命力。 5 新一代的智能规划器应该是基于知识的。利用各种知识来提高规划的生成、执行 和修复效率，以及规划选择的正确率；利用规划系统本身以往的规划知识，使规划系统 具备学习的功能；利用知识，开发规划的启发式函数，用于控制搜索。充分利用知识， 并且有效地挖掘蕴涵的隐含知识，开发基于知识的规划系统。 6 未来的智能规划系统应该具有学习的功能。通过学习删除或完善规划领域理论： 当一个a g e n t 的动作怎样影响其所处世界的模型不可知时，可以通过学习改进它的领域 理论，使领域理论与实际环境更一致；通过学习加速规划：避免搜索无用空间，朝着可 能导致解决方案出现的方向搜索；通过学习提高规划质量：学习用户对规划的偏好，使 规划器带有某种要求属性或衡量价值。规划系统具有学习的功能将使得规划的效率和质 量有一个大的飞跃。 9 第二章图规划 图规划方法的提出引起了整个智能规划界的关注，受到许多学者的强烈推崇。这种 方法把按照s t r i p s 规则形成的规划问题翻译成了能用路径发现方法求解的规划图结构， 第一次采用图的方式来解决规划问题，在智能规划领域中取得了革命性进展。用这种方 式解决规划问题，能使一些动作并行执行，大大提高了求解效率，它拥有许多重要属性， 包括健壮、稳定、合理、高效且建立规划图的计算复杂度是多项式时间和多项式空间等， 后来很多算法都采用了图规划的方法，比较著名的规划器如b l a c k b o x 乜9 j 、f f f ”1 、l p g c ”1