（计算机软件与理论专业论文）智能规划中观测约简及互斥检测的进一步研究.pdf

智能规划中观测约简及互斥检测的进步研究 摘要 本文在前人已有的工作基础上对智能规划领域的观测约简和互斥检测问题 做进一步的研究。智能规划的研究领域在近年来得到了不少的扩展，比如不确定 规划( n d p ) 放松了确定性系统的假设、过度规划( o s p ) 放松了严格目标的假设等 等。这些扩展带来了不少新的问题，比如不确定规划中的观测个数约简问题，还 有过度规划中互斥目标的检测问题及经典规划器的改造等问题。这些新问题包括 了很多有待进一步研究的子问题，比如观测约简中观测个数最小化、启发式的互 斥检测、改造优秀的经典规划器以利用互斥检测中的知识等。本文提出了解决上 述三个有待进一步研究的子问题的方法。 本文从三方面改进观测约简：一是如何找最小观测集合( m o s ) ，二是如何在 观测代价不均等时找最优观测集合( o o s ) ，三是如何找到容错的o o s 。通过m o s 问题和图论中的最小覆盖集问题( m s c ) 的类似性，可证m o s 是n p 难的问题， 还可参考m s c 算法得出时间复杂性为0 ( 2 朋m 2 ) 及q ( 2 肿1 ) 的算法，其中脚是观 测的个数。通过使用整数规划( i p ) 技术，可找到o o s 以及容错的o o s 。可以证 明，上述算法能够保证找到解，并且能够保证解的最优性。 互斥检测本身是n p 完全的，本文提出两种用较小的代价给重构目标子集提 供启发信息的方法。第一种方法将实现子目标的规划视为宏动作，通过识别这些 宏动作之间的关系推测目标之间的关系。第二种方法基于动作之间的因果链提出 因果链图( c l g ) 来检测动作之间的竞争性前提，从而识别目标之间的冲突。其中 对第一种方法实现了一个名为c o m b i n a t o r 的目标关系检测工具。f f p s 是本文实 现的增量规划结合外部信息求解简单过度规划的规划器。为了利用互斥检测的附 加结论，f f p 8 改造了经典的f f 规划器以接受外部信息，比如目标序；为了处理 o s p 问题，f f p s 支持软目标处理。实验证明，f f p 3 结合c o m b i n a t o r 所给出的目标 关系检测信息可以高效地处理过度规划问题。 关键字：人工智能，智能规划，观测约简，互斥检测 簧戆篾翅巾凌浏约蓥及互殍检测的遴一多磷究 a b s t r a c t b a s e do np r e v i o u sw o r k s ，t h i sp a p e rf o c u s e so nd o i n gf u l t h e rr e s e a r c ho n o b s e r v a t i o nr e d u c t i o na n dm u t e xd e t e c t i o ni na ip l a n n i n g r e s e a r c ha r e a so fa i p l a n n i n gh a v eb e e ne x t e n d e di nv a r i o u sd i r e c t i o n s 。f o re x a m p l e ，n o n - d e t e r m i n i s t i c p l a n n i n g ( n d p ) p r o b l e m sr e l a xt h ea s s u m p t i o no fd e t e r m i n i s t i cs y s t e m s ，a n d o v e r - s u b s c r i p t i o np l a n n i n g ( o s p ) p r o b l e m sr e l a xt h ea s s u m p t i o no fs t r i c tg o a l s t h e s e e x t e n t i o n sb r i n gu pal o to fn e wp r o b l e m s , e g 。，o b s e r v a t i o nr e d u c t i o ni nn d p , m u t e x d e t e c t i o na n dc l a s s i cp l a n n e r sr e v i s i o ni no s et h e s ep r o b l e m si n c l u d e v a r i o u s s u b - p r o b l e m sw h i c he x p e c tf u l t h e rr e s e a r c ke g ，m i n i m a lo b s e r v a t i o nr e d u c t i o l i ， h e u r i s t i cm u t e xd e t e c t i o nm e t h o d s ，n e wp l a n n e r sw h i c ht a k ea d v a n t a g eo fm u t e x i n f o r m a t i o n t h i sp a p e ra d d r e s s e st h ea b o v et h r e es u b - p r o b l e m s t h i sp a p e ri m p r o v e so b s e r v a t i o nr e d u c t i o ni nt h r e ea s p e c t s ：t h ef i r s ti st of i n da m i n i m a lo b s e r v a t i o ns e t ( m o s ) ；t h es e c o n di st of r e da l lo p t i m a lo b s e r v a t i o ns e t ( o o s ) i fo b s e r v a t i o n sh a v ed i f f e r e n tc o s t s ；t h et h i r di st of i n daf a u l t - t o l e r a n to o s a m o s p r o b l e mi ss i m i l a rt oam i n i m a ls e tc o v e r ( m s c ) p r o b l e m ，s oi tc a nb ep r o v e d t h a tf i n d i n gm o si sn p - h a r d 。i n s p i r e db ym s cm e t h o d s ，a l lo ( 2 攒枣掇2 ) b u tn ( 2 - ) a l g o r i t h mf o rm o si sp r e s e n t e d , w h e r e ， i st h en u m b e ro fo b s e r v a t i o n s b yu s i n g i n t e g e rp r o g r a m m i n g ( i p ) t e c h n o l o g i e s ，o o so rf a u l tt o l e r a n to o s c a nb ef o u n do u t p r o o f sa r ep r o v i d e dt os h o wt h a tt h e s ea l g o r i t h m sc a l lg u a r a n t e ef i n d i n go p t i m a l s o l u t i o n s m u t e xd e t e c t i o ni sn p - e o m p l e t ei ne s s e n t i a l t h i sp a p e rp r e s e n t st w os i m p l e m e t h o d sw h i c hc a r lp r o v i d eh e u r i s t i ci n f o r m a t i o nf o rs u b g o a ls e tr e c o n s t r u n c t i o n 、析t l lm i n o re f f o r t s t h ef i r s tm e t h o dr e g a r d sa no p t i m a lp l a nl e a d i n gt oas u b g o a la sa m a c r oa c t i o na n dt h e ni n f e r sa b o u ti n t e r a c t i o n sb e t w e e ng o a l sf r o mt h e s em a c r o a c t i o n s 。t h es e c o n dm e t h o db u i l d sc a s u a l l i n kg r a p h s ( e l g ) a n dd e t e c t sc o m p e t i t i v e p r e c o n d i t i o n si nc l g ；a n dh e n c ea c h i e v e sm u t e xa n a l y s i s ag o a li n t e r a c t i o nd e t e c t i o n t o o l ，n a m e l yc o m b i n a t o r , i si m p l e m e n t e db a s e do nt h ef i r s tm e t h o d 。f f p si sa no s p p l a n n e r 髑i n gi n c r e m e n t a lp l a n n i n ga n de x t e r n a li n f o r m a t i o n t ou s ei n f o r m a t i o nf r o m 骜笺娩巅孛鬟嚣终楚及鬣蓐裣溅豹进一步辑究 m u t e xd e t e c t i o n , f f 筘r e v i s e st h ec l a s s i cf fp l a n n e rt o c o o p e r a t ew i t he x t e r n a l i n f o r m a t i o n , e g ，g i v e ng o a lo r d e r s 。t oh a n d l eo s pp r o b l e m s ，龄萨s u p p o r t ss o f tg o a l s e x p e r i m e n t ss h o wt h a tf f 鼍w o r k i n gw i t hc o m b i n a t o r , c a l ls o l v es i m p l eo s p p r o b l e m se f f e c t i v e l y k e y w o r d ：a r t i f i c i a li n t e l l i g e n c e ，a u t o m a t e dp l a n n i n g ，o b s e r v a t i o nr e d u c t i o n , m u t e x d e t e c t i o n m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进彳予研究 工作所取得的成果。除文中已经注明弓| 用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以嘎确方式标明。本入完全意识刘本声明的法律结果由本人承担。 学位论文作者签名： 饶末宇 日期：加哩年弓茂沁e t 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向冒家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：饶挝 日期：御年了月日 导师签名：和 、， 日期： 州羚 智藐麓菇巾麓测费篱及要臻捡溅懿遂一步磷究 第1 章引言 智能规划是人工智能的一个重要分支。智能规划从某个特定问题的初始状态 出发，寻找达到解决该问题的目标状态的动作序列。在日常生活中，人们作规划 的过程冀实就是一种动作推理的过程。在这个过程中，人们需要蓄先预麓各种动 作的效果，然后制定一个可以满足某个规划目标的动作执行策略。智能规划就是 人工智能里专门研究如何利用计算理论和计算机技术实现自动规划的领域。早期 的规划闯题很鸯然缝使用逻辑推理来进行求解，僵由于推理方法存在着效率低以 及存在异常模型等缺点，人们转向使用各种搜索技术来求解智能规划问题，例如 启发式搜索、半序规划、图规划及可满足规划等等。这些搜索技术极大地提高了 规划闻题的求解效率，也壶此带来了规划求解领域的扩展。 n o p f n o n d e t e r m i n i s t i cp l a n n i n g ) 和o s p ( o v e r - s u b s c r i p t i o np l a n n i n g ) 是近年来 比较重要的两类规划扩展。其中n d p 放松了确定性系统的假设，即系统的初始 状态和动作效果具有不确定性；o s p 放松了严格目标的假设，即不是所有的目标 都要求实现。由于实际问题的复杂性，n d p 和o s p 的发展其实是规划向应用发 展的必经之路。n d p 是目前规划研究中的热点之一，近几次的国际顶级会议 i n t e r n a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ( u c a i ) 及n a t i o r m a l c o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ( a a a i ) 均设立了专门的n d ps e s s i o n 。而自 2 0 0 4 年o s p 被提出后，每年的i j c a i ，a a a i ，i n t e r n a t i o n a lc o n f e r e n c eo n 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 ( i c a p s ) 上都有成果面世，2 0 0 7 年的丸讼i 会议上有专门的t u t o r i a l 介绍o s p ，2 0 0 8 年的i c a p s 还设立了专门的w o r k s h o p 。 观测约简是n d p 中的一个新闻题。在n d p 巾由于动作效采是不确定的，往 往需要进行观测，以区分多种可能的状态。但是，在现实中观测信息的获取往往 需要各种各样的代价，比如传感器的能耗以及通信代价等等。同时很多时候观测 变量一般都是可选的，甚至在规划执行的过程中用不到。因此要找到一个对规划 的执行两言最小的观测集，或者种最好的观测组合方案。进一步，考虑到观测 ( 例如传感器) 也有可能出错，有时需要一个能容错的观测组合方案。在观测约简 这个问题上，本文将就如何找最小鼹测集合( m i n i m a lo b s e r v a t i o ns e t ，简称m o s ) ， 如何在观测代价不均等时找最优观测集( o p t i m a lo b s e r v a t i o ns e t ，简称o o s ) ，如 智熊规剜巾溪测约籀及互薅捡溅魏迸一步研究 何找到客错的o o s 三个方蕊进行研究。 互斥检测是o s p 的固有问题。最初s m i t h 研究o s p 闯题时就发现了o s p 问 题具有天然的量层结构，高层选择目标子集而低层进行规划。处理o s p 问题的 很多规划器都采取这样的方法。为保证尽标子集可行，需要进行目标之闻的互斥 分析和不可达暌标的删除，其中前者更有研究价值。但宪备或者完全的互斥分析 是n p 完全的，所以一般需要使用启发式方法。因此本文提出两种简单的互斥检 测方法：将实现予露标的规划视为宏动作，逶过识别这些宏动作之阆的关系推断 鼹标之间的关系；基于动作之间的因果链提出因果链图( c a u s u ll i n kg r a p h ，简称 c l g ) 来检测动作之间的竞争性前提，从而识别目标之间的冲突。 o s p 规划器需要考虑o s p 问题的特性。比如考虑到互斥分析的计算复杂性， 如何剩用这个过程中褥到信息就成了一个有吸引力的阅题。再比如o s p 闯题中 的日标都是软目标，而经典规划器都是严格目标，如何改造f f 等经典规划器以 处理软警标就成了一个有趣的阔题。因此本文提出并实现了释泌，它改造了经典 的f f 规划器以接受辨部信息，比如可能的嗣标序，还支持软目标处理。另一方 面f f v s 也为验证本文提出的互斥检测方法提供了工具。 本文后面的内容组织如下：第二章介绍规划研究的技术、应用和发展；第三 章针对观测约篱最小化问题给出相关靛背景知识和解决方法；第四章针对嚣斥检 测问题给出相关的背景知识和启发式算法，其中最后一节介绍f f p 8 ，即用增量规 划结合外部信息酌规划器，并逶过实验验证本文提出的互斥检测瘟发式算法及 f 的效果；最艨一章是全文的总结及对来来王俸的展望。 2 智能规划中观测约简及互斥检测的进一步研究 第2 章规划综述 智能规划领域的研究起源于更早期的关于动作和变化的推理【l 】，规划问题描 述语言和计算理论也是来自于各种动作描述语言和动作理论。本章主要有三方面 内容：首先会介绍智能规划的起源、发展和历史以及基本定义，然后是不确定规 划的综述和基本定义，最后会给出过度规划的综述以及基本定义。 2 1 规划的发展历史 智能规划是人工智能的一个分支，从1 9 7 1 年至今已经发展了近4 0 年。智能 规划的发展历史可以从以下五个方面来阐述： 智能规划研究社区的发展 智能规划求解技术的发展 一智能规划目标领域的发展 规划定义语言的发展 智能规划系统和国际规划竞赛的发展 本文将本节中涉及到的智能规划历史整理为编年史，作为附录。 2 1 1 智能规划研究社区的发展 1 9 7 1 年，f 慨s 【2 】研制s t r i p s 通用问题求解程序时，正式使用 规戈l j ( p l a n n i n g ) 这个术语，从此诞生了智能规划这个研究领域。此后，研究智能规划的组织陆续 成立，出现了专门的国际会议，智能规划的研究成果也在整个人工智能领域得到 了认可。其中主要的智能规划组织包括： 1 9 8 4 年成立的英国智能规划和调度特别兴趣小组p l a n s i g ( u k p l a n n i n ga n ds c h e d u l i n gs p e c i a li n t e r e s tg r o u p ) i 州： 1 9 9 5 年成立的由s u b b a r a ok a m b h a m p a t i 领导的美国亚利桑那州立大学 y o c h a n l 4 】研究组： 警巍艇翻巾溪涮魏楚及互蓐捻溺的避一步研究 1 9 9 8 年成立的欧洲智能规划网p l a n e t 5 】； 1 9 9 9 成立的英国诺丁汉大学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 dp l a n n i n g ) 【6 l 。 为了推进智能规划的研究，规划社区还专门举行了很多次星际会议，其中比 较著名的有： 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 ) ：首届e c p 会议于1 9 9 1 年举行， 其后每两年次，直到2 0 0 3 年； a i p s ( i n t e r n a t i o n a l c o n f e r e n c eo na 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 ga n d s c h e d u l i n gs y s t e m s ) ：首届a i p s 会议于1 9 9 2 年举行，其后每两年一次， 直到2 0 0 3 年； i c a p s ( i n t e m a t i o n a lc o n f e r e n c eo na 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 ) i a i p s 和e c p 在2 0 0 3 年合并而来，每年一届。 规捌社区的研究成果也得到了人工智能领域的认可，在1 9 9 5 、2 0 0 3 、2 0 0 9 年期刊( a r t i f i c i a li n t e l l i g e n c e ) 出了三次智能规划方面的专刊。 以上三个方预的发展体现了整个智能规划研究社区的发展。 2 。王2 智能规划求解方法的发展 在近四十年的发展过程中，智能规划的技术理论以及研究的新领域不断丰 富，这一过程可以大致分为四个阶段。第一个阶段是规划被定义之前的研究，它 们源自其他的人王智能分支。第二个阶段是在1 9 7 1 年规划这一术语被正式使用 后，直到二十世纪九十年代初，举行了专门的规划会议和成立了规划研究组织。 第三阶段就是从二十世纪九十年代初到1 9 9 8 年开始的国际规划竞赛和规划问题 描述语言( p d d l ) 的诞生。第四阶段则是在1 9 9 8 年之蜃，壹到现在。 ( 1 ) 第一阶段：1 9 7 1 年之前 规划作为人工智能的一个分支，其早期技术也源白其他的人工智能研究领 域。其中被规划技术广泛采用的包括： 启发式信息和反向搜索技术：在1 9 5 6 年的逻辑理论家( l o g i ct h e o r i s t ) 阴程序被首次芷式采用； 4 智能霾潮巾观测约楚及互蓐检测的逶一多研究 联合子目标：在1 9 5 9 年的定理证明机【8 】中首次被处理； 情景演算：1 9 6 0 年著名入王智能大薅泊妇m c c a r t h y 建议使用谓词演算 去指导智能行为中的推理，并由此提出了情景演算法( s i t u a t i o nc a l c u l u s ) 。 后来在1 9 6 9 年，情景演算问题描述法【9 l 被正式提出，并且g i 优n 【1 0 1 还提 出用它来逶过定理证明进行阀题求解； 梦领域知识与一般的搜索控制信息相分离：在1 9 6 9 年的g p s 系统l l l 】中首 次被使用。 ( 2 ) 第二阶段：1 9 7 1 年到1 9 9 0 年 1 9 7 1 年，规划这一术语被正式使用，规划社区开始发展自己的技术、理论以 及对新领域的探索。这一阶段提出的主要技术包括： s t r i p s 撬翔方法：1 9 7 1 年r i c h a r df i k e s 和n i l sj n i l s s o n 提出了s t r i p s 规划方法 2 1 。s t r i p s 规划在规划问题表示上引入了过程化表示和语义， 用算法化思想使规划方法突破了纯逻辑方法的不足，极大的提高了规划 系统的能力，成为智能觏划研究的一个里程碑。s t r i p s 搜索过程使用目 标分解回溯进行问题求解，可以使用启发知识提高搜索效率； 框架规划：1 9 7 4 年在w a r p l a n 规划器【1 2 】中被提出并使用； 分层规划愚想：1 9 7 4 年s a c e r d o t i 在【穆】提避。它透过分析闷题的空闻划分 为若干个不同的抽象层次，在最一般的抽象空间中作最高层的规划，在 具体问题空间中作最低层的规划。利用高层的规划限制下层的规划搜索 空闯，可以提高总体效率。但是，部分序计划的逐步求精过程仍然是n p 困难的，而且在规划状态空间中，构造启发策略更加网难1 4 1 ； 因标退化技术：在1 9 7 5 年的w a l d i n g e r sp l a n n e r 1 5 1 申酋次被使用； 非线性规划：由n o a h 系统i 键在1 9 7 5 年引入； 给层次规划引入了层控制：1 9 8 1 年在m o l g e n 系统【1 7 】【1 8 】中提出并使用； 再规划：在1 9 8 3 年的s i p e 1 9 】中首次被提擞； 约束传递方法：1 9 8 7 年在t w e a k 系统渊中被提出并采用。 a d l 语言：p e d n a u l t 在1 9 8 9 年【2 i 】提出a d l 语言，它也是后来p d d l 语 言的前身之一； 在这一阶段，c 脚m a n 阎还在1 9 8 7 年提磁了著名的模态真值标准( m o d a l 5 彗辘烧麓巾襞溅约麓殷嚣蓐棱溅豹迸步研究 t r u t hc r i t e r i o n ) 理论，并发现：筒单地利用定理证明的方法来解决规划闯题是很 难的。 在新的领域的探索方面，这阶段无论是不确定规划还是时态规划都还处在 萌芽期。其中对羼来的研究比较有影响的包括： 不确定规划的早期尝试：1 9 7 6 年【2 2 】最早在基于规划空间的规划方法上作 定的扩展，尝试解决含不确定性的规划问题； 用黠态逻辑进行过程推理：1 9 8 2 年幽粥1 提出； 使用时态世界模型：在f 2 4 l 中提出，包括动作与时间的推理理论和使用时 态世界模型的规划方法； 支持在连续时阅内靓划：1 9 8 3 年d e v i s e r 2 5 】第一个支持在连续时闻内 规划，放松了离线规划的假设； 这一阶段的很多重要成果都被总结到a l l e n 等人的文献【2 研中。 ( 3 ) 第三酚段：1 9 9 1 年到1 9 9 8 年 二十世纪九十年代初，隧着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 ) 、 a i 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 1a r t i f i c i a li n t e l l i g e n c ep l a n n i n ga n ds c h e d u l i n g s y s t e m s ) 等会议的举行和y o c h a n 研究组、欧洲智能规划潮p l a n n e t 麴成立， 智能援划研究进入了一个蓬勃发展的时期。这一阶段提懑豁很多技术和理论都对 规划技术的发展有着重大的影响。其中比较重要的技术包括： 部分序巍划：1 9 9 2 年被提掰来溯：部分序规划也称为规划空阆中的规划 ( p l a n n i n gi np l a ns p a c e ) 。相对予状态空闻中酶兢划，部分序规划在( 部 分) 规划空问中寻求从初始的空规划到完整解规划的条路径； 基于s a t 技术的规划方法：1 9 9 2 年被k a u t z 帮s e l m a n f 2 3 1 提出。一反定 理证明式求解方法，捌溺在约束可满足闯题算法上的突破，有效地解决 了部分规划问题； 基于m a r k o v 决策过程的规划方法：19 9 4 年被c a s s a n d r a 等人溯提激； 图规划方法：1 9 9 5 年蠢b l u m 和f 硪妒蠲提出。第一次采用图的方式来解 决规划问题，并且提出了用于规划的规划图的概念。后来很多规划系统 都借鉴了豳规划系统的方法； 改进部分序规划中的扇发策略：1 9 9 6 年融g e r e v i n i t 3 1 】提出； 6 智能规划中观测约简及互斥检测的进一步研究 基于模型检测的规划方法：1 9 9 7 年被c i m a t t i 等人【3 2 】提出； 将图规划扩展到不确定规划：在1 9 9 8 年被s m i t h 和w e l d 3 3 】提出。 这阶段比较重要的理论方法和结果包括： 放松了序列规划的假设：1 9 9 2 年m i l a n i 提出并行规划中冲突的处理方 法刚，放松了序列规划的假设； 最小承诺规划( 1 e a s tc o m m i t m e n tp l a n n i n g ) ：1 9 9 4 年被w e l d l 3 5 1 提出； 不确定性( 概率) 规划的算法：1 9 9 5 年被k u s h m e f i c k 3 6 1 提出； 在m d p 的框架下表示时序逻辑目标：1 9 9 6 年由b a c c h u s 3 7 1 提出： 基于m d p s 的规划方法基本算法( 策略迭代和值迭代) 的复杂性：在1 9 9 7 年和1 9 9 8 年由l i t t m a n t 3 8 】【3 9 】给出； 资源约束下的规划：1 9 9 8 年被k o e m e r 【4 0 1 提出； 不确定规划中强规划解的概念：1 9 9 8 年被c i m a t t i 等人【4 1 】提出； 不确定规划中强循环解的概念：1 9 9 8 年被c i m a t t i 等人【4 2 】提出； 放松了隐式的时间假设：1 9 9 1 年出现了可以处理时间和资源的规划器 o - p l a n t 4 3 1 ，放松了隐式的时间假设。 这一阶段的很多重要成果概括在w ，e l d 的文献畔】中。 ( 4 ) 第四阶段：1 9 9 8 年之后 1 9 9 8 年诞生的规划问题描述语言p d d l 和国际规划竞赛i p c 推动了规划研 究的发展，在这一阶段产生了大量的规划系统和求解技术，规划目标的形式也不 断扩展。其中比较有影响的成果包括： 1 9 9 8 年正式出现了被规划社区认可的规划问题描述标准- p d d l 语言 【4 5 】 o 将执行上下文的因素也考虑到规划解( 即动作选择策略) 中：b o u t i l i e r 4 6 1 提出解策略的执行过程可以为一有限状态序列，并在此基础上将执行上 下文的因素也考虑到规划解中； 实时值迭代算法：2 0 0 0 年b o n e t 和g e f f n e r l 4 7 】提出用于缓解状态空间爆 炸所带来的问题的实时值迭代算法； 基于符号模型检测技术的规划方法：2 0 0 0 年被j e n s e n 和v e l o s o 4 8 l 采用； 基于s a t 技术的规划方法扩展到不确定规划领域：在2 0 0 0 年被f e r r a r i s 7 智巍规划中瘸测约篱及麓器检溅豹进一多耩究 和g i u n c h i g l i a 4 9 】提出； 放松了完全可观测的假设：2 0 0 0 年b o n e t 和g e f f n e r 研究了p o n d p ( 部 分可观测的不确定规划) f 4 7 】，放松了完全可观测的假设； 弱规划解，强规划解和强循环规划解的描述框架被扩展：2 0 0 1 年b e r t o l i 以及p i s t o r e 等人瑟翻刚扩展了它们用于解决含部分可观察性的规划阎题； 启发式方法：h s p 系统f 5 2 l 以及f f 规划器网进一步发展了启发式方法； 弱规划解、强规划解和强循环规划解的全面分析和比较：2 0 0 3 年 c i m a t t i 等人【嗣进行了全菰的分析和比较； 基于b d d 数据结构的启发式的规划方法：2 0 0 3 + 年j e n s e n 等人 5 5 l 提出； 过度规划问题：2 0 0 4 年被s m i t h l 5 6 提出； 基亏二p e t r i 嬲展开的规划方法：2 0 0 7 被h i c k m o t t l 5 7 提出。 上述四个阶段大致体现了智能规划求解技术的发展，包括已有技术的发展和 新技术的涌现。一方面很多已有技术在不断发展，比如启发式技术，从第一阶段 的逻辑理论家囝，到第二阶段被应用在s t r i p s 框架隧中，奔到第三阶段用到了 部份序规划【3 ，最后在第四阶段被应用到f f 规划器【5 3 1 中；另一方面新的求解手 段不断涌现，比如第一阶段的情景演算 9 1 ，第二阶段的s t r i p s 方法【2 1 、分层规 划翻和约束传递方法 2 0 1 ，第三阶段的部份序规划朗、图规划瑟o l 和基于s a t 技术 的规划【2 引，第四阶段的基于模型检测技术的规划【4 8 i 、基于b d d 的启发式规划【5 5 1 以及基于p e t r i 网展开的规划【5 7 】方法等。 2 1 3 智能规划目标领域的发展 智能规划研究的发展也体现在智能规划图标领域和智能规划定义语言的发 展上，其中目标领域的发展又集中体现在八个经典规划中假设的放松上。 ( 1 ) 八个经典假设的逐步放松 在经典规划中有八个假设，这八个假设在规划的研究和发展中被逐步的放 松。这八个假设是： 有限状态：规划问题的状态数是有限的； 完全可观测：规划问题的状态是完全可观测的； 3 智能筑捌巾或铡约篱及互露检测的迸一步研究 确定性的系统：规划问题的初始状态、动作效果都是确定的； 静态的系统：在规划过程，不存在外部事件的干扰； 严格目标：整个目标集是可达的； 序列的规划：规划解是由顺序的动作所构成的； 隐式的时闻：动作都是瞬阆完成的； 离线规划：规划问题的求解和规划解的执行是分开的。 在规划的发展过程中，确定性系统、离线规划、隐式时间、序列规划、完全 可观测以及严格冒标这六个假设被逐一放松了： 1 9 7 6 年w a r r e n 在基于规划空间的规划方法上作一定的扩展【2 2 1 ，尝试解 决含不确定性的规划问题，放松了确定性的系统假设； 1 9 8 3 年d e v i s e r t 2 题第一个支持在连续时闻内规划，放松了离线规划的 假设； 1 9 9 1 年出现了可以处理时间和资源的规划器o p l a n l 4 3 l ，放松了隐式的时 闻假设； 1 9 9 2 年m i l a n i 提出并行规划中冲突的处理方法【川，放松了序列规划的 假设： 2 0 0 0 年b o n e r 和g e f f n e r 研究了p o n d p ( 部分可观测的不确定规划) 4 7 1 ， 放松了完全可观测的假设； 2 0 0 2 年i p c 使用的p d d l 2 。l 中【5 引，增加了持续的动作和对任意实际时 闻、复杂的度量领域的表示，部分地放松了有限状态的假设； 2 0 0 4 年s m i t h 提出了过度规划问题【5 6 1 ，放松了严格圈标的假设。 实际上，在以p d d l 和i p c 为标准的规划领域中，已经确认了系统的不确定 性、系统不一定完全可观测、连续状态空间、存在软磊标、需要考虑动作执行时 间以及需要在线规划等实际因素的影响。随着八个经典假设的放松，规划研究的 范围越来越广，面对的问题也越来越复杂，越来越接近现实应用。本文将会在第 三章进一步介绍这些假设( 特别是硬目标假设) 的放松。 2 1 。4 规划定义语言的发展 9 智能撬剜中观测约簿及嚣蓐检测斡进一步研究 规划定义语言的发展也能够体现规划求解范围的拓展和求解能力的增强。下 面按照历史发展的顺序对基于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 o v e r ) 和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 ) 的规划领域定义语言( p d d l ) 进行介绍。 而对予不确定规划语言方面的介绍将会和不确定规划的介绍一起被放在第二章。 ( 薹) 斯坦福研究院问题求解系统s t r i p s 1 9 7 1 年，r i c h a r df i k e s 和n i l sj n i l s s o n 提出了s t r i p s 规划方法 2 1 。s t r i p s 规划在逻辑的规划问题表示上引入了过程化表示和语义，用算法化思想使规划方 法突破了纯逻辑方法的不足，极大的提高了规划系统的麓力，成为智能规划研究 的一个里程碑。自此之后，智能规划的问题表示都是s t r i p s 规划或者s t r i p s 规划的扩充。s t r i p s 的动作模式用三个集合表示，即前提文字集、增加文字集 和删除文字集，可以省略框架公理。s t r i p s 描述方法发震戒了经典栽划中最主 要的描述语言。s t r i p s 是智能规划历史上具有重要意义的研究成果，它的规划 能力比以前所有规划系统的规划能力都强，其知识表示方法及推理方法对它以后 的规划系统具有深刻的影响。 ( 2 ) 动作描述语言a d l e p e d n a u l t 在1 9 8 9 年1 2 1 】提出了动作描述语言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 ) 。该描述语言是在s t r i p s 基础上进行了扩充，它允许使用全称量词 c o n i v e r s a lq u a n t i f i e r ) 、存在量词( e x i s t e n t i a lq u a n t i f i e r ) 和条件效果( c o n d i t i o n a l e f f e c 0 等。 ( 3 ) 规划领域定义语言p d d l1 7 p d d l 作为智能规划问题设计的标准语言，最早版本是由m c d e r m o t t 定义1 4 5 】， 用在1 9 9 8 年规划大赛上。p d d l 描述语言? l a n n i n gd o m a i nd e f i n i t i o nl a n g u a g e ) ， 其表达能力包括s t r i p s 和a d l 。 ( 4 ) 规划领域定义语言p d d l2 1 在2 0 0 2 年规划大赛上，l o n g 和f o x 对p d d l 进行较大的扩展 5 8 l ，称为 p d d l 2 1 。p d d l 2 1 是一种基于时序规划和度量规划的语言，它的描述能力采 取了a d l 一部分内容，比s t r i p s 的描述能力更强，更接近实际应用问题上的 描述，缩小了理论研究跟实际应用之闻的代沟。p d d l 2 1 扩充增加时序逻辑的内 容，即对动作延续时间的描述和时间流逝对动作的影响，以及条件效果。它包括 1 0 智能规划中观测约简及互斥检测的进一步研究 五个层次： 第一层：相应于m c d e r r n o t t 定义的p d d l l 7 中的命题和a d l 层相容，这是 为了保证p d d l 向下兼容性，没有进行新的添加和修改。 第二层：在第一层的基础上增加了数值变量，并且能够对这些数值变量的值 进行即时的测试和更新，并对m c d e r m o t t 的提议稍微作了修订。 第三、第四层：在第二层的基础上增加了持续的动作。持续的动作定义为： 在动作开始执行后要经过一段时间才能得到动作的效果。第三层和第四层的区别 在于：在第三层描述的动作没有持续的影响，而在第四层描述的动作就可以有持 续的影响。因为持续动作被限定在它影响的变量上，故第四层简化了在实际时间 领域的模型。 第五层：是第四层的一个自然扩展，增加了表示任意实际时间、复杂的度量 领域，目的是为以后研究者们设计规划问题、描述语言p d d l 指明了方向。 ( 5 ) 规划领域定义语言p d d l 2 2 p d d l 2 2 语言【5 9 1 是2 0 0 4 年国际规划竞赛i p c 4 所采用的规划问题描述语言， 它在原来的p d d l 2 1 【5 8 】的基础上，增加了两个新的特性：派生谓词( d e r i v e d p r e d i c a t e ) 和时间初始谓词( t u n ei n i t i a ll i t e r a l ) 。派生谓词用来描述动作的非直 接效果，而时间初始谓词用来预先设置谓词的时间窗口。 ( 6 ) 规划领域定义语言p d d l3 0 2 0 0 5 年，为2 0 0 6 年的i p c 5 准备的p d d l 3 0 中引入了偏好和轨迹。其中 偏好是从过度规划问题演化而来的，但本身不涉及资源问题。而轨迹就提出了对 中间目标和解路径的要求。 实际上在2 0 0 8 年的i p c 6 上提出了p d d l 3 1 的名称但( 到目前为止) 没有给 出正式的定义。考虑到i p c 6 是基于这个未定义的语言的，因此在本文中将不涉 及p d d l 3 1 以及i p c 6 上出现的规划器。 上述不同版本的规划定义语言反映了规划研究领域在经典规划求解问题的 表示能力方面的发展。规划研究领域对不确定规划的研究不断深入也带来了对不 确定规划的表示能力的尝试，比如2 0 0 0 年【4 8 】提出n a d l + ，2 0 0 3 年【6 1 】被b e r t o l i 等人提出n - p d d l ，2 0 0 4 年的规划大赛上使用的p p d d l l 0 【6 2 1 。但是对整个不确 定规划领域还没有标准的规划定义语言。 智戆绒糍中琨溅约簿及置斥检溅熬避一多研究 2 1 5 智能规划系统和国际规划竞赛的发展 规划系统是规划研究的主要成果之一，规划系统的发展体现了规划求解能力 的提高。