（计算机软件与理论专业论文）增量式动态概率规划的研究.pdf

摘要 无论是因为对人工智能理论研究的贡献，还是因为实际的应用前景，作为人工智能 的一个重要分支，智能规划的研究价值不可小觑，近年来研究成果颇多，成绩斐然。为 了让智能规划能处理更为实际及复杂的问题，当前很多研究人员热衷于不确定规划的研 究，比如说概率规划。 其中，很多概率规划系统研究最短路径问题，然而当环境发生变化时，原来的规划 结果将不再适用或不是足够好，许多系统不得不重新进行规划。当然，环境的变化通常 是渐变的，重新规划时处理的往往是相似的规划问题，所以多次的重规划中，存在大量 的重复规划和搜索过程，如果完全重新独立规划，规划系统的效率是低下的，在某些领 域甚至是不可容忍的。如何记住已经进行过的可以复用的规划成果，在时间和空间寻求 一个均衡点，就是增量式规划的任务。尽管目前对增量式规划已经有了若干研究，但并 不广泛。 本文将随机概率规划问题转为马尔可夫决策过程( m d p ) 模型来研究，同时结合了 启发式搜索的算法，用启发值的迭代计算来解决最短路径规划问题，在这基础上，研究 其中规划过程的特点和规律，当环境不断变化时，我们用增量式规划的方法来重规划， 重复利用了前面规划的成果，减小了再次状态空间扩展时的规模，更加快速的进行启发 值的迭代计算，提高整个规划过程的效率。 本文主要的工作有：提出了增量式动态概率规划的模型和定义，设计了增量式动态 概率规划的状态空间生成算法、增量式动态概率规划启发值的迭代算法及增量式动态概 率规划的算法。 同时，本文用c + + 语言编写代码，在l i i l u x 系统环境下开发了赛车问题域的增量式 动态概率规划系统，实现了该算法。用大量实例进行测试，结果验证了算法的有效性， 特别是进行重规划时，大大减小了状态空间的再扩展规模和启发值迭代计算的次数，从 而节省了规划时间，提高重规划的效率。 关键词：智能规划；概率规划；增量式；最短路径；启发式搜索 a b s t r a c t t h er e s e a r c hi n t o 硫e l l i g e n tp l a 加m g ，t l l a n k st oi t sc o 曲j b u t i o nt 0a i t i f i c i a li n t e l l i g e n c e t l l e o 巧a i l db r o a d 印p l i e df o r e g r o u i l d ，i s 诵d e l yc o n s i d e r e dt 0b eo fe s s e n t i mi i n p o n a i l c e r e c e n t l y ，r e m a r k a b l ea c h i e v e m e n th a sb e e n 晰协e s s e d m e a i l w m l e ，t 0s o l v em o r ef a c t u a la n d c o m p l e xp r o b l e m s ，r e s e a r c h e r sc o m m i tt 1 1 e m s e l v e st ot l l es m d yo fu n c e r t a i n t ) ，p l a i 】1 1 i n g ，i n w 1 1 i c ho n e p r o p e ri 1 1 s t 姐c es h o u l db em e n t i o n e d ，t h ep r o b a b i l i s t i cp l 蛐g r e s e a r c h e r sh a v ei n v e s t i g a t e dm 锄yp r o b a b i l i s t i cp l 觚m n gs y s t e m st h a ta 1 1 0 wo n et o s o l v es h o r t e s t - p a t l lp 1 砌n gp r o b l e m s h o w e v e r ，w h j l et l l ee n v i r o i l i i l e n tc h a i l g e s ，t h eo r i g i n a l p l a n sm i g h tn ol o n g e ra p p l y0 rm i g h ti l o tb eg o o de n o u 曲a 1 1 y m o r e ，t l l e r e f o r e ，c o r r e s p o n d i n g s y s t e m ss h o u l db er e p l a n e d i ti s 仃u et h a tt h ec h a l l g e so ft h ee n v i r 0 i m l e n ta r eu s u a l l y 黟a d u a l a i l dt 1 1 e r e f o r es m a l l ，s ot l l ep l a l 】j 1 i n gp r o b l e m sa r em o r eo rl e s ss i m i l 跹1 1 1t h o s e 伊a d u a l c k m g e s ，t h e r ea r em a n yr e p e a t e dp l a n sa 1 1 ds e a r c l l i n gp r o c e s s e s ，a n dac o m p l e t ec o m p u t a t i o n o ft l l eb e s tp l a nc a i lb ei n e f ! f i c i e n ts i n c es o m eo ft h ep 代v i o l l ss e a r c hr e s u l t sc a nb er e u s e d ， w 1 1 i c hc o m db eu i l b e a r a b l ei i ls o m ed o m a i l l s h o wt 0r e m e m b e rn l er e s u l t so fm ep l a n sa 1 1 dt o s e e kab a l a n c ep o i mb e t w e e nn l et i i i l ea n dt l l es p a c ei sj l l s tw h a ti n c r e m e n t 村s e a r c hm e t h o d s 仃yt 0s o l v e a l t h o u g h 也e r ea r cs o m er e s e a r c h e so n l es t u d yo fi i l c r e m e n t 甜p l 锄i n g ，i ti s s t i l ln o tb r o a de n o u 曲 i i l 廿：i et l l e s i s ，w et r a i l s f o m st 1 1 e 砌【l d o mp r o b a b i l i s t i cp l 锄l i n gp r o b l e mm ot 1 1 em d p p r o b l e ma i l dc o m b i n e sah e 嘶s t i cs e a r c hm e m o dt os o l v et l l es h o r t e s t - p a ：c hp r o b l e m ，a i l d i n v e s t i g a t e st h ec h a r a c t e r i s t i c sa n dd i s c i p l i i 埘a i l so ft h em e t h o d ：w h e nm ee n v i r o m n e n t c h a n g e s ，t 1 1 es y s t e mc o u l db er 印l a i l e db yi i l c r e m e n t a lp l 觚m n g t h r o u g h 也i s ，、v ec o u l d r e d u c et h en m n b e ro fs t a t e sa 1 1 dc o m p u t en l eh e 血s t i cv a l u e 谢t 1 1s p e e da i l de 街c i e n c y n l et 1 1 e s i sa i m sa t b r i l l g i n g f o n v a r dm em o d e la 1 1 dd e f i l l i t i o no f 恤i n c r e m e 删 d y n 锄i cp r o b a b i l i s t i cp l a l l i l i n ga i l dd e s i g i 】【i 1 1 9r e l e v 觚ta l g o r i t h m sa b o mt l l ep l a i ls y s t e m m o r e o v e r ，a 1 1c o d e sf o rn l ea l g o r i m ma r e 、撕讹ni i lc + + ，a 1 1 dap l a i ls y s t e ma b o u tt h e r a c i n gc a rd o m a i np r o b l e mu n d e rl i m s y s t e mi s a l s o d e s i g n e d t h er e s u l t so ft h e e x p 砸m e n t a t i o i l sp r o v et h e 、谢i d 埘o f t h ea l g o r i t h m a b o v ea l l ，t h ei i l c r e m e m a lp l a l lm i i l i s h e s t l l es t a l es p a c e 肌dr e d u c e st 1 1 e 雠q u e n c yo fc o n l p u t i n gh e 嘶s t i cv a l l u e ，t h e r e f i o r es a v em e t i m ea n de i l l l a n c et h ec o n t i n u e dp l a n s e 街c i e n c y k e yw o r d s ：i n t e l l i g e n tp l 锄n i i l g ；p r o b a b i l i s t i cp l a i l i l i n g ；i n c r e m e n 诅l ；s h o 毗s t p a t l l ； h e u r i s t i cs e a r c h 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者毕业后去向： 指导教师签名： 日 期： 忆蚴i ， 臁厶 l ， 一 电话： 邮编： 东北师范大学硕士学位论文 引言 智能规划是人工智能一个重要的领域，其研究起源于6 0 年代。近年来，有关智能 规划的研究在问题的描述和问题求解两方面得到了新的突破，使得智能规划已成为一个 热门的人工智能研究领域，由于智能规划的研究对象和研究方法的转变，极大地扩展了 智能规划的应用领域，使近年来智能规划的理论和应用研究有了长足的进展。为了促进 智能规划的发展，两年一届的国际智能规划大赛妒c ( i n t e m a t i o n a lp l a l l j i l gc o m p e t i t i o n ) 是这个研究领域最顶级的学术会议和规划系统竞赛。在国外，近年来成立了许多专门从 事智能规划方面研究的协会和联盟，如欧洲智能规划网p i ，a n e t ( e u r o p e a i ln e 铆o r ko f e x c e l l e n c ei i la ip 1 a 1 1 i l i n g ) ，英国诺丁汉大学a s a p 研究组( a m o m a t e ds c h e d u l i n g o 两觚s a l i o na n dp l a i l i l i n g ) 以及美国亚利桑那州立大学y 0 c h a i l 研究组等i 。 经典的规划是基于强约束条件之上的，在大多数实际环境中，智能体几乎从来无法 了解关于其环境的全部事实，经典规划的强约束条件是得不到保证的，智能体必须在不 确定的环境下行动。因此不确定规划就得到研究者的重视并得到迅速发展，尤其是用概 率方法来定量描述问题不确定性的概率规划问题。近年来涌现了许多概率规划器，比如 比较经典的基于g r a p h p l a i l 【2 】的p g a _ p h p l a n 【3 】等。通过引入信念状态空间将非马尔可夫链 问题转化为马尔可夫链问题来求解，其描述真实世界的特性使它成为研究随机决策过程 的重要分支，所以本文将概率规划问题转化为马尔可夫决策问题来解决。 规划的搜索算法有两类，盲目搜索和启发式搜索，盲目的搜索算法搜索空间巨大， 效率极低，种种实践结果表明启发式搜索减小了搜索的空间，极大的提高了规划搜索的 效率。 实际的环境都处于动态变化当中，原有的规划结果可能将不再可用，许多规划系统 不得不调整规划方法或重新规划以应对。幸运的是，在一个规划域内，当连续规划时， 往往环境的改变量是比较小的，存在众多的重复搜索过程。在这种情况下，如果完全重 新规划，效率是很低的，在一些特殊的领域里，如军事规划系统等，这将是无法忍受的， 遗忘历史的算法注定要重复历史。如何记住已经进行过的可以复用的搜索结果，在时间 和空间寻求一个均衡点，就是增量式规划( i i l c r e m e mp l a n ) 的任务。 本文将随机概率规划问题转为马尔可夫决策过程( m d p ) 模型来研究，用搜索启发 值的迭代计算来解决最短路径规划问题。同时在分析了随机最优概率规划的特点和规律 的基础之上，发现在环境变换时，不需要再对问题进行重新独立的规划，可以利用众多 前面规划所得到的大量的信息进行增量式重规划，提高规划效率。本文算法具有较高的 理论价值，同时在实际应用中，比如在军事领域等需要快速反应的问题上具有重要的应 用价值。 本文主要的工作有：提出了增量式动态概率规划的模型和定义，设计了增量式动态 东北师范大学硕士学位论文 概率规划的状态空间生成算法、增量式动态概率规划启发值的迭代算法及增量式动态概 率规划的算法。 同时，本文用c + + 语言编写代码，在l i n u ) 【系统环境下开发了赛车问题域的增量式 动态概率规划系统，实现了该算法。用大量实例进行测试，结果验证了算法的有效性， 特别是进行重规划时，大大减小了状态空间的再扩展规模和启发值迭代计算的次数，从 而节省了规划时间，提高重规划的效率。 本文主要结构是：第一章对智能规划进行了概述；第二章介绍了本文的背景知识， 即概率规划和马尔可夫决策过程；第三章是本文的主体部分，详细介绍了增量式动态概 率规划的相关算法；第四章是算法的实现和实验结果验证分析，最后对算法进行总结。 2 东北师范大学硕士学位论文 第一章智能规划 智能规划是人工智能中的一个重要的研究领域，其主要思想是：对周围环境进行认 识与分析，根据自己要实现的目标，对若干可供选择的动作及所提供的资源限制施行推 理，综合制定出实现目标的规划。近年来，有关智能规划的研究在问题的描述和问题求 解两方面得到了新的突破，使得智能规划已成为一个热门的人工智能研究领域。 1 1 智能规划概念 智能规划研究的主要目的是建立起高效实用的智能规划系统。该系统的主要功能可 以描述为：给定问题的状态描述、对状态描述进行变换的一组操作、初始状态和目标状 态。智能规划系统能够给出从初始状态变到目标状态的一个操作序列，其复杂性和所处 的环境以及a g e n t 的功能有关。求解a g e n t 从初始状态执行怎样的规划才能到达目标状 态的过程叫做求规划解，求得的规划叫做规划解。直观的说，一个规划解实质上就是一 个动作序列，此动作序列能实现某一种目标。智能规划就是设计这个动作序列的过程， 即主要解决怎么做，而不解决为什么这样做。 传统的规划一般都作出如下假设：( 1 ) 环境的状态的改变完全是由a g e n t 的动作的 效果造成的，排除了其他可能的影响和干扰；( 2 ) a g e n t 的动作的效果是完全确定的； ( 3 ) a g e n t 能够感知环境和它的动作的效果。人们把具有上述假设的规划问题叫做经典 规划问题。例如地图着色问题、积木世界问题等都是经典的规划问题。现在，大多数研 究者还在采纳此假设。 但是由于现实世界的复杂性，实际问题往往并不能满足上述条件，限制了智能规划 的求解规模和领域，因此目前研究热点致力于放宽这一假设，研究在环境不断变化情况 下的规划问题。相应地，我们把不满足该假设的规划问题称为“非经典规划”问题。 求规划解的系统称为规划器。它是一种应用软件，当给定初始状态、目标状态以及 相关操作等信息后，这个应用软件就可以给出从初始状态到达目标状态的规划解，即自 动给出动作序列，使得在初始状态下通过执行这个动作序列就可以到达目标状态。规划 器要在尽可能短的时间里，给出质量尽可能高，甚至最优的规划解。为了促进智能规划 的发展，两年一届的国际智能规划大赛口c ( i n t e m a t i o n a lp l a m n gc o m p e t i t i o n ) 是这个研究 领域最顶级的学术会议和规划系统竞赛。 1 2 智能规划的发展历史 人们对智能规划的研究已经有半个世纪了，最早可以追朔到6 0 年代n e 、e l l 、s h a w 和s i m o n 设计的逻辑理论家( l o g i cn l e o r i s t ) 程序，这个系统采用了启发式信息和反 3 东北师范大学硕士学位论文 向搜索技术。随后他们又设计了g p s 系统，把领域知识与一般的搜索控制信息相分离。 上述两个系统，特别是g p s 在人工智能领域中具有非常重要的地位，但它们还不是真 正面向规划问题研制的智能规划系统。 1 9 6 9 年陆e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统1 4 1 ， 这一系统被大多数的智能规划研究人员认为是第一个规划器，原因就在于他是第一个面 向现实规划问题提出的规划系统；1 9 7 1 年f i k e s 和n i l s s o n 设计的s ，丌u p s 系统【5 】在 智能规划的研究中具有重大的意义和价值，他的突出贡献是引入了s t i 心s 操作符的概 念，使得原来很神秘的规划问题求解变得明朗清晰起来；此后到1 9 7 7 年先后出现了 h a c k e r 、w 甜冲l a n 、i n t e r p l a n 、a b s t 耐p s 、n o a h 、n o n l i n 等规划系统。 在这十年里，人们研究智能规划的兴致比较高，普遍认为规划问题必须用定理证明的理 论来解决，直到c h 印m a l l 设计的规划系统t w e a k 【6 】的出现。由于c h a p m a l l 的分析使 人们认识到简单地利用定理证明的方法来解决规划问题是很困难的，因此从这以后到 1 9 9 0 年间，在人们发现新的求解方法之前，对智能规划的研究陷入了低谷，这期间仅 有s i p e 、a b t w e 出和p r o d i g y 等较少的智能规划器出现。 1 9 9 2 年k a l l t z 等把规划问题求解转化为约束可满足( s a t ) 问题【7 - 9 】，一反定理证 明式求解方法，利用在约束可满足问题算法上的突破，有效地解决了部分规划问题。后 来，基于此理论的b 1 a c k b o x 规划器【lo 】在第一届智能规划器的比赛中表现出了非凡的解 决问题的能力，一举夺魁，开辟了解决规划问题的又一新途径。1 9 9 5 年a v r i mb l 啪等 设计的图规划系统q a p h p l a i l 第一次采用图的方式来解决规划问题，并且提出了用于规 划的规划图的概念。后来很多规划系统都借鉴了图规划的方法，参加第一届智能规划比 赛的规划器除委内瑞拉的h s p 外，其它四个规划器s g p 、b l a c k b o x 、i p p 和s n 都 或多或少地采用了图规划的某些技巧，并且对图规划做了相应的扩充：s g p 加入了用 户交互操作界面；b l a c k b o x 综合了基于规划图的快速规划扩展和基于s a t 的快速规 划验证的优点；p p 扩充了图规划的问题描述语言，支持a d l 规划描述语言，能够处 理条件效果等，因此其表达能力比图规划器要强大；s 口n 在减少搜索和构造规划图的 费用上做了改进。这些规划算法都是偏序或非线性的通用规划器，此次比赛表明偏序方 法在规划求解中具有举足轻重的地位。两年以后，在第二届规划比赛上，偏序规划的思 想得到了进一步验证，并且在规划过程中启发式信息被人们广泛关注。在参加比赛的十 六种规划器中有十一个采用启发式信息，并且采用启发式信息的规划器比没有采用启发 式信息的规划器得到的规划解效果更好，比如最终选出的最佳规划器聊p l 黜l e r 和 f f ，以及排名其次的s t f 蝌、h s p 2 、m i p s 和s y s t e mr 都采用了启发式信息。在此次 比赛中，采用启发式信息的规划器表现出很强的问题求解能力，而第一届比赛的冠军 b l a c k b o x ( 渤p h p l a i l + s a t ) 则由于没有采用启发式信息而表现得不尽人意。 4 东北师范大学硕士学位论文 1 3 智能规划的应用 在问题描述和问题求解两方面的研究得到了新的突破，使智能规划成为一个热门的 人工智能研究领域。由于智能规划的研究对象和研究方法的转变，极大地扩展了智能规 划的应用领域，使近年来智能规划的理论和应用研究有了长足的进展。目前智能规划在 自动系统中的应用使得自动化系统的灵活性、健壮性和适应性得到显著提高。智能规划 的主要应用领域有机器人、智能企业和商业软件。 在i j c 越0 1 的智能规划讨论会上，会议主题是“资源约束规划”，目标是为实际应用 上的规划研究学者提供一个交流的平台。会议上的规划系统都是在计算机实际应用系统 中得到广泛使用的规划系统，例如：美国宇航局的a s p e n 规划系统【1 1 】、马里兰大学的 c 瓜c a 、美国宇航局的e u r o p a 、华盛顿大学的l p s a t 规划系统和爱丁堡大学的o p l a l l 规划系统等等。这次会议主要讨论内容有：混合规划系统、整合规划系统、资源约束上 的推理技术、时序规划、智能规划和调度、优化目标规划和有关规划的模型、问题领域 和实验结果。 规划在机器人领域中的应用主要有环境、机器人能力和目标三者的模型化描述以及 实时的输入响应。不同于其它规划研究领域，机器人领域的规划研究主要在于当处于有 噪音的环境模型中，机器人通过感应器和交流信道得到的信息都存在噪音，这样它就需 要将感应和执行整合来进行直接规划。智能规划在机器人学中具体的应用方向有环境模 型的描述、控制知识的表示、路径规划、任务规划、非结构环境下的规划、含有不确定 性的规划、协调操作( 运动) 规划、装配规划、基于传感信息的规划、任务协商与调度和 制造( 加工) 系统中机器人的调度等。 智能规划也可用在智能工厂中【1 2 】，例如在工厂作业调度规划问题中( j o bs h o p s c h e d u l i n g ) ，就是要考虑在加工资源( 车床，刨床，钻床) 有限的情况下根据已知的工件 的加工顺序要求对整个车间的生产做出安排，使得加工完所有工件所需的时间尽可能的 少，每台机床的等待时间尽可能的短，以使工厂在同样设备条件下，由于作业调度规划 合理而增加了生产能力，从而给工厂带来了可观的经济效益，主要采用资源约束的方法 进行对规划求解1 1 3 1 。 智能规划在商业中的应用更加广泛，对原有的经典规划作了更大的扩充，其目标状 态可以只是满足某个条件，而不是明确的命题。目前主要研究领域有网络信息集成、运 输规划等。 1 4 智能规划的方法 智能规划可分为传统智能规划和现代智能规划。 东北师范大学硕士学位论文 1 4 1 传统智能规划方法 半序规划：自1 9 7 1 年产生以来，s t i 珊s 系统在规划系统中一直占据统治地位。此 后的研究工作，大都在s t r j p s 的基础上加以改进，这其中最重要的一种方法就是半序 规划。这种规划借用了s t i 冲s 的描述，但是不要求产生一个完整的操作序列，而是先 在操作之间生成半序描述，然后逐步加细求精，最后在操作的半序描述中抽出全序的规 划。 逻辑规划系统是基于r - o b i i l s o n 的消解原理( r e 缸a t i o nr e s o l u t i o n ) 的，它采用定理 证明的方法，把求解规划的过程形式化为证明由初始状态和动作序列可以证明目标状态 的过程，其证明过程的解释就是一个规划解，也有人称这种方法为基于变化 ( c h a n g e b a s e d ) 的规划，以命题逻辑、一阶谓词逻辑等规范逻辑和各种非规范逻辑如 默认推理( d e 矗柚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 l l o 西c ) 、内涵逻辑( i n t e n s i o n a ll o g i c ) 、非单调逻辑和模糊逻辑等为其理论基础。 几乎所有的规划问题都固有一种层次结构，即递归的目标与子目标之间的组成体 系，上层与下层目标之间的关系实际上都相应于某个操作与其先决条件之间的关系。但 是就规划问题的表示意义来说，却可以把目标分成抽象与具体，或者重要与次要程度不 同的层次，也可以对所有子目标一视同仁，即在表示意义上只认为是一个层次，前者称 为层次规划方法，后者称为非层次规划方法。 1 4 2 现代智能规划方法 从1 9 9 5 年b 1 u m 和f u r s t 提出图规划算法以来，与领域无关的智能规划算法的效率 得到了较大的提高。现代智能规划系统基本可以划分为五大类。第一类是基于图规划的 规划系统，它们的代表规划系统有：研a p h p l a n 、b l a c k b o x 、i p p 【1 4 】和l g p 【1 5 】；第二类是 基于启发式搜索的规划系统它们的代表规划系统有：h s p 【阚、f f 【1 7 】【1 8 】和m i p s 【1 9 】【2 0 】；第 三类是基于逐步细化的分层规划系统它们的代表规划系统有：s h o p 2 【2 l 】；第四类是将规 划问题转化为约束可满足问题来求解的规划方法，代表规划系统有b l a c k b o x ；第五类是 将规划问题转化为模型检测问题来求解的规划方法，代表规划系统有m i p s 。 另外将经典规划的约束放开，根据放开约束条件的不同，非经典规划还可分为动作 或效果不确定的概率规划、初始状态或动作不确定的一致性规划、初始不确定或感知动 作的感知规划等，这些规划称为不确定规划。不确定规划是当前研究的热点。 1 5 规划域定义语言p d d l 规划问题的形式化描述是规划问题求解的前提。如果一个规划问题不能通过规划语 言来表示，则任何一个规划器都不能对它进行求解。所以说规划语言的发展是智能规划 发展的关键。1 9 7 1 年f i k e 和n i l s o n 的s 删p s 系统在智能规划中具有划时代的意义， 6 东北师范大学硕士学位论文 因为它使得规划可以非常容易地进行描述和操作。但随着规划技术的应用，人们发觉 s 喇p s 表示的表达能力非常有限，它不能满足一些实际问题的模型化要求。设计一种 能够刻画和模型化一个实际问题的规划问题定义语言成为了规划技术应用的前提。1 9 8 6 年e p e d i l a u l t 提出了动作描述语言：a d l ( a c t i o nd e s c r i p t i o nl 锄g u a g e ) 【2 2 1 。a d l 除了具 有s t 对p s 的表达能力外，还能表达条件效果和量化效果等语言特征。1 9 9 8 年d r e w m c d e 彻o t t 提出了规划领域定义语言( p d d l ) 【2 3 1 ，它逐渐地成为公认的国际智能规划 比赛( n e m a t i o n a lp l a i l n i l l gc o m p e t i t i o n ，i p c ) 的标准语言。p d d l 语言不仅给出了规划问 题定义的语法，也从语义的角度给出了规划的定义。p d d l 语言的表达能力非常强，能 够刻画规划问题的时间和数值方面的属性，超过了现有的规划器所能处理的表达能力， 给规划器的发展指明了方向。规划语言是规划领域交流和沟通的标准，对于不同的规划 器我们可以通过它们对同一种语言表示的规划问题的处理来进行性能比较。 智能规划的研究逐渐地从理论研究走向实际应用，而将规划技术运用到实际问题领 域就不可避免地涉及到一个问题：如何模型化一个实际问题领域并进行推理。1 9 9 8 年， d r e wm c d e m o t t 提出了规划领域定义语言p d d l ，同时指出一种语言的主要任务是表达 世界的物理属性，而不是建议规划器如何搜索相应的解空间。 p d d l 是一种以动作为中心的语言，它的实质是一种动作的语法标准，表达使用前 件和后件来描述动作的可使用性和效果。动作的前件和后件被表达成由谓词、项和逻辑 连接词组成的逻辑命题。 p d d l 的核心是s t p s 表示，扩展的表达能力包括表达问题域中对象的类型结构、 动作和谓词中的参数类型、具有否定命题和条件效果的动作以及在前件和后件的表达中 使用量词。 p d d l 包含了问题域对表达能力层次要求的语法描述，它通过使用r e q u i r e m e n t s 标 志来表达特定问题域描述所要求表达能力的层次水平，这样可以使一个规划系统优雅的 拒绝那些具有它所不能处理的语言特征的问题域。 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 m p s 表示和a d l ，即如果某个问题可以由s 1 r i 洄s 和a d l 表示，那么该问 题也能够通过p d d l l 2 表示。 2 p d d l 2 1 1 9 9 8 年后，规划技术开始逐渐走向实际应用，现代规划器需要处理时序和数值问题， 所以就需要一种能够表达时序和数值特征的规划语言。因此，m 撕af o x 和d e r e kl o n g 【2 4 】 于2 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 p s 部分； 第二层是数值表达部分；第三层是离散的持续动作；第四层是连续的持续动作；第五层 是p d d l 2 1 的所有扩展及能够支持自发事件和物理过程模型化的附加组件。它的表达 7 东北师范大学硕士学位论文 能力超出了目前规划器所能处理的范围，给规划研究者们提出了新的挑战。p d d l 2 1 与 p d d l 前面的版本兼容。 3 p d d l + p d d l + 【2 5 】是对p d d l 2 1 的第5 层描述，它引入了两个附加的模型化部件：过程 和事件。过程和事件的引入意味着那些用持续动作来模型化的领域特点在第5 层可以使 用由起始点、过程和结束点三部分组成的结构来进行模型化，在起始点和结束点可以运 用动作或事件，也可以是活跃过程的效果导致一个数值到达关键阈值的点，这称为 s t a n - p r o c e s s s t o p 模型。在p d d l + 的第5 层，动作可以开始一个过程，它具有瞬时的 效果，可以改变问题域中的逻辑状态；而一个过程在随着时间修改状态的数值部分时将 保持一个状态的逻辑部分。动作与过程的区别在于动作导致状态转移，而过程则不会； 过程和事件的区别在于：事件的数值后件中不能有与时间相关的效果，而过程的数值后 件通常是与时间相关的效果。一个过程可以由一个动作或由出现在世界中的某一事件来 结束。 4 p d d l 2 2 p d d l 2 2 【2 6 】保留了p d d l 2 1 的前三层的表达能力，新增了导出谓词和初始化时间 命题两种表达能力。 8 东北师范大学硕士学位论文 第二章概率规划与m d p 智能体在了解到关于环境足够多的事实之后，并且在不变的环境中，一般总能够得 到保证可行的规划。这种确定的规划具有一定的现实意义和应用价值，很长一段时间内， 研究者致力于它的研究工作，寻求通用的描述方法和高效、节省空间的算法来解决一些 问题。 然而不幸的是，在大多数实际环境中，智能体几乎从来无法了解关于其环境的全部 事实，经典规划的强约束条件是得不到保证的，智能体必须在不确定的环境下行动。比 如，某人开车去上班，尽管到办公室只有十五分钟的车程，即使提前半个小时出门也不 能保证及时到达办公室，这里有许多不确定因素，可能交通拥堵，可能汽车抛锚等，但 提前半个小时仍是一个不错的选择，它有很大的可能性保证上班不迟到，又避免过早的 出门，关于这种可能性的知识是可以被利用的，研究者将它运用在规划中，描述规划问 题中的不确定信息，这就是概率规划的方法。这种方法更加真实地描述这个世界状态， 研究者开发了很多概率规划器，从而解决了很多实际问题，推动了智能规划的发展，拓 展了规划研究问题的规模和领域。 2 1 概率规划 2 1 1 概率规划的表示 1 状态表示 概率规划中关于状态的表示方法有两种，一种是单调域( f l a td o m a i n ) ，另一种是 命题域( p r o p o s i t i o n a ld o m a i l l ) 。单调域是指状态是一个单一的整体，它明确地列举状 态，如某人开车在上班的路上这个状态我们可以指定为s 1 。而命题域认为状态是布尔 状态变量或命题的集合，上面的例子我们就可以用p l 表示某人在开车，p 2 表示某人在 路上。一般情况下，命题域表示方法会用少量的变量或命题表示较大的问题，例：如果 有m 个命题，每个命题的值有两个( 真或假、0 或1 ) ，就可以表示2 m 个状态。 在单调表示法中，转换函数t 可用一个l s l i s l 的矩阵表示，而在命题表示方法中， 这种i s l l sj 的方法将会形成一个很大的矩阵，所以转换函数必须用其它方法表示。在概 率规划中，命题规划域的两种常用表示方法是：概率状态算子( p s o s ) 和两层时序贝叶 斯网( 2 t b n s ) 1 27 。尽管这些表示方法和其它规划域表示方法有些不同，但从计算复杂性 上是等价的，即用一种方法表示的规划域可在多项式时间内转换为由另一种方法表示的 相同的规划域，至多增长多项式级表示空剐2 8 1 。 2 初始世界表示 一般来说，初始世界就是初始状态，上面我们已经提到状态的两种表示方法，初始 0 东北师范大学硕士学位论文 世界的表示方法就是状态的表示方法。由于我们研究的是不确定世界中的规划，初始世 界也可能是不确定的，所以初始世界也分确定和不确定两种，确定的初始世界和经典规 划中的定义没有区别。对于不确定的初始世界，在概率规划中，我们可以用概率的方法 定义世界的初始状态，即用概率值表示初始状态存在的可能性。这样我们对不确定的初 始状态就会有一个量化的评估，进而来评估整个规划。 3 动作表示 在概率规划中，动作具有多个可能输出，每一个输出都伴随一个表示产生这种输出 的可能性的概率值。用这种方法定义动作的好处是： ( 1 ) 对于我们知道的可能存在的输出，我们可以准确地把动作模型化，并且根据 经验对于每一个输出给定一个符合实际的概率值。另外，还有用条件效果( c o n d i t i o n a l e 虢c t ) 的方法来定义动作模型，如上例中，我们可以用这种条件语义来表示：如果动 作的前提条件中存在交通比较拥堵，那么动作的结果就是某人上班会迟到，如果没有这 个条件那么某人就能按时上班。但是用这种方法有时也不能准确地描述动作的结果，比 如说，交通拥堵，可能迟到也可能按时上班，这时候用条件效果的方法就不能准确地定 义了，而我们用概率表示动作输出的方法就可以较清晰地说明了。 ( 2 ) 对于我们不知道的可能输出，也为其赋一个概率值。这种方法虽然并不十分 准确，但是它占有一个动作输出的可能性，所以也能在生成规划中起到作用。 2 1 2 概率规划的定义 对于概率规划，很多算法都是根据以下定义来决定算法的执行结果的。在这个定义 下，一个概率规划包含以下几部分： 1 状态集合。 2 具有概率分布的初始状态。 3 目标集。 4 能影响随机状态转换的算子集合。 5 表示概率规划成功的合理的阈值t 。 寻找规划就是寻找一个动作序列使主体能在最小概率值为t 的状态下到达目标状 态。寻找最优规划就是寻找到达目标概率值最大的规划。 我们可以用六元组定义上面的概率规划域m = s ，s o ，a ，t ，g ，p ，其中s 表示 状态集合；s o s 表示具有概率分布的初始状态；a 表示能影响随机状态转换的算子集 合；若s ，s s ，t 是概率转换函数，t ( s ，a ，s ) 表示s 通过a 到达s 的概率；g 表 示目标集合；t 表示概率规划成功的合理阈值。 对于上面给出的这个概率规划的定义，很多人从马尔可夫决策过程( m d p ) 的角度 给出了多种算法。但是对于决策来说它并不是严格的定义，因为在这种假设下，没有考 虑动作的代价以及规划中某些动作的结果会对整个规划有促进作用而生成的奖励。也就 是说只是衡量了规划到达目标的可能性，没有考虑到使用动作所涉及的资源及其它数值 东北师范大学硕士学位论文 要求。这种状况只是一种理想状态，它的实际应用能力也是很有限的。因此扩展上述定 义，丰富动作和状态的表达能力是目标概率规划中很重要的任务。考虑到这些问题，一 个概率规划域包含的内容应该是： 1 状态集合。 2 初始状态上的概率分布。 3 带有奖励值的目标集。 4 带有能影响随机状态转换的代价的算子集合。 5 表示规划成功的合理的阈值t 。 寻找规划就是寻找一个动作序列使这个动作序列在达到所有目标的情况下，效用值 达到阈值t 。 因此m = s ，s o ，a ，t ，g ，伊中的a 应该是一个函数，a a ，s s ，a ( s ) 表示在s 下执行动作a 的代价。g g ，和一个实数gr 相对应，gr 表示奖励值。 概率规划的这两个定义看起来很相似，但是第一个定义中计算的阈值是规划到达目 标的可能性，而第二个定义中的阈值表示到达目标的期望效用值，这是二者的根本区别。 严格来说上面的方法仅是对经典规划的扩展，目前还有一方面的工作是在用上述方 法表述动作和初始状态的情况下，完全放弃了经典规划模型，特别是运用m d p 过程作 为一种代替方法来考虑规划语义。这种方法和上述概率规划定义最大的区别是：它不是 寻找一组确定的目标，求得达到这个目标集的概率，而是把目标定义为一个效用值，即 寻找一个规划达到这个效用值。在这种情况下，只要规划的效用值足够大，己知的目标 集可以是部分满足的。 2 1 3 概率规划的类型 概率规划域有四种类型。第一类是全序规划( t o t a l l vo r d e n 觅p l a l l ) ，它是最基本的 类型，其规划中的动作序列是严格有序的，在这类规划中每个时间步只能有一个动作被 执行；第二类是无环规划( a na c y c l i c ( c o n d i t i o n a l ) p l a l l ) ，它产生的是包括条件规划的 全序规划；第三类是相对于全序规划的部分有序规划( p 枷a lo r d e dp l a n ) ，它和全序 规划不同的是它的动作序列不必是一个精确的序列，而是一个相对有序的序列；最后一 类是有环规划( l o o pp l a n ) ，它产生具有重复规划步的非循环规划，这类规划也被称为规 划图或策略副2 9 】。 概率规划中最成功的是在完全可观察( f u l lo b s e n ，a t i o n ) 的假设下的算法，在这种 算法中，尽管不确定性阻碍了主体在时间步之前预测运行时间状态，但主体还是能够掌 握有关运行时间的完全、准确的信息。另外，研究人员也采用了部分可观察( p a r t i a l o b s e r v a t i o n ) 的模型处理甜规划问题，但是它的复杂性显然受这种工作的应用程序的 限制。但这些困难并没有减少人们对部分可观察问题的热衷程度，这是由于部分可观察 的这个假设使规划更具有现实意义，是使规划问题走出实验室的一个很重要的方面，因 此它