（计算机应用技术专业论文）基于效用理论的并行概率规划算法的研究与实现.pdf

摘要 智能规划是人工智能研究领域近年来发震起来的一个热门分支，由于其广泛的实用 性，受到研究者的高度重视。尤其是具有不完全信息和不确定信息的规划问题已经成为 智能规划研究中的重点。在各种研究方法中，由于概率方法能较准确地对不确定信息进 行定量描述，因此研究动作具有概率输出的概率规划方法体现了较强的优越性，这个方 法得到了研究者的肯定，并在此基础上产生了大量的算法。 基于研a p h p l a l l 算法的p g r a p h p l a n 是概率规划中较优秀的款规划器。p 研印h p l a l l 在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许 执行一个非空动作 的假设下求得的，这个假设的存在使得在规划图中无法使用互斥信 息，找到的规划解相对冗长，浪费求解时间。并且算法只考虑概率信息，没有涉及状态 的效用值信息，不便于处理现实世界的问题。 本文针对概率规划中存在的这两点不足之处，提出了新的概率规划算法 u c p g f a 两p l 勰。首先，我们通过添加结果结点，对经典规划圈进行了扩展，并定义了 并行有效轨迹及各种结点的互斥关系，尽可能多的包含所有的有效轨迹，使其在同一时 间步实现了并行，打破了原有概率规划算法中“每个时间步只允许执行一个非空动作 的限制，弥补了原有算法的不足，提高了靓划器的运行速度和性能。其次，在并行概率 规划中运用了效用理论，使所有目标都能以最大的期望效用值去实现，从而提高了规划 器的求解质量。该算法更适合于求解现实世界中的概率规划问题。 本文在给出算法的基础上，利用c 语言对该算法进行了实现，设计了可以处理带 有最大期望效用值的并行概率规划系统u c p 翟坤l 娩。实验证翡该系统可以达到理论 预期的效果，实现了概率规划算法中动作的并行执行，可以找到成功概率较大且具有最 大期望效用值的规划解。提高了概率规划器的求解质量，使得概率规划器更适合于处理 现实世界闯题。 关键词；智能规划；p 错a p h p l a n ；并行有效轨迹 a b s t r a c t n o wi n t e u i g e n t p 1 a n n i n gi s av e r yh o tb r a n c hi na i b e c a u s eofi t sw i d e a p p l i c a t i o nr e s e a r c h e r sp a ym u c ha t t e n t i o nt op l a n n i n gt e c h n ol o g y e s p e c i a l l y ， p l a n n i n gu n d e ru n c e r t a i n t ya n di n c o m p l e t eh a sb e c o m et h ef o c a lp o i n ts t u d i e d i n v a r i o u sk i n d so fr e s e a r c ha p p r o a c h e s ，b e c a u s et h ep r o b a b i l i t ym e t h o dc a nd e s c r i b e t h eu n c e r t a i ni n f o r m a t i o nr a t i o n r e l a t i v e l ya c c u r a t e l y ， s o s t u d yt h ep r o b a b i l i s t i c p l a n n i n gt h a tt h eo p e r a t o rh a sp r o b a b i l i s t i co u t c o m er e l a t i v e l ys t r o n gs u p e r i o r i t yi n m e t h o d m a n yr e s e a r c h e r sa r ei nf a v o ro ft h i sm e t h o da n dh a sp r o d u c e da1 a r g e a m o u n to fa l g o r i t h m so nt h eb a s i so ft h i s p g r 印h p l a ni sas o u n dp l a n n e r b a s e do ng r a p h p l a n 衙p r o b a b i l i s t i cp l a n n i l l gp r o b l e m s a n di t p r o d u c e sac o n t i n g e n tp l a nb e g m i i l gw i t ht o p d o w nd y i l a m i cp r o 铲a m i i l g b u ti t p 柏册su n d e rt h er e s t r i c t i o no fa l l o w i l l go n l yo n en o n - n o o pa c t i o np e rt i m es t 印t 1 1 i s r e s t r i c t i o nm a k e st h ea k o r i t l m lg a i l ll e n 垂h yp l a n n i n ga n dc o s tm o r et 硫ea i l ds p a c e t h e e x t e n s i o no fp g r a p h p l a nc a nn o tb r e a c ht h i sc o n s t r a m p g r a p h p l a na l g o r i t h mo n l yc o n s i d e r p r o b a b i i i t yi n 旬m a t i o n ，a 1 1 dd o e sn o ti i l v o l v ea i l ys t a t eo f t h eu t i l i t yv a l u eo f 访南r m a t i o n ni s n o te a s yt od e a lw “ht h er e a lw o r l dp r o b l 锄 f o rt h e s ep r o b l e m s ，w ep r o p o s e du c p g r a p h p l a ni i lt h i sp a p e r f i r s t ，w ee x p a i l s i o nt h e c l a s s i c a lp l a n sb ya d d i l l gr e s u nn o d e sa i l dp r o p o s ean e wc o n c 印to fp a r a l l e lv a l i dt r a j e c t o r i e s a n dm u t e xi n 南r n l a t i o n 血u c - p g r a p h p l a nt o i m p r o v ep l a n n e r sp e r 向r m a n c e a sm a n y c o n t a i na 1 1t h ev a l i dt r 旬e c t o r i e st oa c h i e v ea tt h es 锄et i n l es t 印u c p g r a p h p l a nb r e a c h e st h e r e s t r i c t i o n “a 1 1 0 w so n l yo n en o n n o o pa c t i o np e rt i m es t e p ”，a 1 1 di tc a nf i n dt h eo p t i i i l a lp l a n s e c o n d ，w eu s et h eu t i l i t yt h e o 巧i i lt h eu c p g r a p h p l 矾t h a ta 1 1o b j e c t i v e sc a nb e a c c o i n p l i s h e dw i t ht h eg r e a t e s tv a l u eo fe x p e c t e du t i l i t yt h u s ，i tc a i le n h a n c et h eq u a l i t yo f p l a n n i i l g 南rt h es o l u t i o n t h ea l g o r i t l l mi sn l o r cs u i t e dt os o l v er e a l - w o r l dp r o b l e m si i lt h e p l a r m i i l g b a s e do nt h ea l g o r i t h m p r o p o s e da b o v e ， w eh a v ed e v e l o p e dan e wp l a n e r ：u c - p g r 印h p l a n ，w h i c hr e a l i z e sh a n d l i i 玛p a r a l l e lv a l i dt r 句e c t o 订e s i i l p r o b a b i l i s t i cp l a l l l l i n g p r o b l e m s d u et oi t c a l l6 n dt h eo p t i i i l a lp l 矾s ou c p g r a p h p l a ni sm o r el l s e 旬l 南ra c t u a l p r o b l e i n sa n d 肌l a r g et h ea p p l i c a t i o nd o i m i i l so f t h ep r o b a b i l i s t i cp l 幽g k e yw o r d s ： i n t e l l i g e n tp l 乏i i l i l i i l g ；p g r a p h p l a i l ；p a r a l l e lv a l i dt r 旬e c t o r i e s i i 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别热以标注和致谢的地方外，论文中不包含其他入已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 确的说明。本声明的法律结果由本人承担。 学位论文作者签名：j 查4 l 日期：2 五琏i 螋 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 、汇编本学位论文。同意将本学位论文收录到巾匿优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光艋版) 电子杂志社) 、中豳学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：簿 圜 期：趁呈：吐：乏方 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 东北师范大学硕士学位论文 课题研究背景 第一章引言 智能规划是当前人工智能领域中极为活跃的一个研究热点，近十年来，有关智能规 划的研究在润题攒述和阍题求解两方面得到了新的突破。相对于早期的智能规划系统， 现代规巅系统无论在规划求解效率上还是在规划求解规模上都有很大的提高。然而，经 典智能规划要求知识的完整性，即假设a g e n t 对于规划世界的知识是完全的，规划过程 中动作的效果是确定的，但在现实世界中，我们得到的信息往往是不完全、不确定的， 这就使规划理论的应焉范萋受到极大的限制。因此不确定规划就缛到研究者的重视并得 到迅速发展，尤其是用概率方法来定量描述问题不确定性的概率规划问题。2 0 0 4 年， 由国际人工智能规划与调度会议委员会主办的第网届国际规划竞赛特别增加了概率规 划部分的比赛，可见概率规划已经弓| 起了人们的足够重视。 解决概率规划的方法很多，也涌现出很多高效的概率规划器。a l b l u m 教授与 m l f w s t 教授于1 9 9 5 年开发出经飙规划器g r a p h p l a n ，提出的新颖的规划图结构给规 划领域带来了突破性的进展。g r a p h p l a n 算法的高效性，使得基于该算法的概率规划器 脱颖丽出强一3 ，成为薪的磺究热点，其中p 觚曲p k 疆3 算法就是图规划框架下的一款较 好的概率规划器。 p g r a p h p l a n 算法在图规划框架下利用动态规划算法找到一个随机规划解。但该规划 解是在“每个时闻步只允许执行一个非空动作 的限制下求褥的，由于这个限制的存 在，使得规划器无法并行执行动作。丽且，算法只考虑概率信息，没有涉及命题及目标 的效用值信息，导致找到的规划解相对冗长，浪费求解时问。p g r a p h p l a n 算法的后续发 展的算法也都存在这些不足，使得概率规划算法无法高效的处理现实世界中的不确定规 划闯题。 针对概率规划中存在的这些问题，本文提出了一种新的概率规划算法 u c p g r a p h p l a n 。首先，我们在规划图中添加了结果结点，对其进行了扩展。其次，定 义了并行有效轨迹及各种结点间的互斥关系，使得u c p g r a p h p l 嬲算法打破了传统概率 规划方法中“每个时间步只允许执行一个非空动作 的限制，弥补了p g r a p h p l a n 算法 的不足。最后，在规划中引用了效用理论，使得u c 。p g r 印h p l a n 算法可以找到成功概率 最大且具有最大期望效用值的最优规划解。新的算法更适合于解决实际问题，进一步拓 宽了概率靓划的应用领域。 东北师范大学硕士学位论文 1 2 本文主要工作及意义 本文针对以往概率规划算法中的“每个时间步只允许执行一个非空动作”和“没有 考虑状态的效用值信息”的两点不足之处，提出了新的概率规划算法u c p g r a p h p l 孤。 本文的主要工作表现在以下几个方面： 1 添加了结果结点，对经典规划图进行了扩展，并定义了并行有效轨迹的概念， 给出并行有效轨迹的生成原则。 2 重新定义了命题互斥、动作结点互斥及结果结点互斥的概念，从而在概率规划 算法中可以使用互斥信息，提高了规划器的求解速度。 3 在概率规划问题中引入了效用理论，使规划算法可以找到成功概率较大且具有 最大期望效用值的规划解。 4 利用c + + 语言开发了u c p g r a p h p l a n 概率规划器，达到了理论预期的效果，实 现了概率规划中动作的并行执行，并且所有目标都能以最大的期望效用值去实现，从而 提高了规划器的求解质量。 新的算法更适合于解决实际问题，具有较高的理论研究价值。同时，u c p g r 印h p l 肌 规划器的开发，促进了概率规划在实际应用方面的发展。 2 东北师范大学硕士学位论文 第二章智能规划 智能规划是人工智能中的一个重要的研究领域，其主要思想是：对周围环境进行认 识与分析，根据自己要实现的目标，对若干可供选择的操作及所提供的资源限制施行推 理，综合制定出实现目标的规划西3 。智能规划是一个交叉研究领域，它涉及知识表达、 知识推理、非单调逻辑、情景演算、人机交互和知识挖掘等多个方面。本章我们将介绍 智能规划的一些相关概念。 2 1 智能规划的概念 智能规划是一种问题求解技术，它从规划问题的初始状态出发，构造一个能够到达 问题目标状态的动作或操作序列。 智能规划研究起源于问题的求解，是人工智能研究中较早出现的研究领域之一。它 的研究可以追溯到6 0 年代的n e w e l l 和s i m o n 的g p s ( 通过问题求解系统) 以及 g r e e i l 的q a 3 系统( 1 9 6 9 ) 哺1 。1 9 7 1 年，f i l ( e 和n i l s s o n 提出的s t p s 口1 系统在智 能规划领域中具有划时代的意义。 智能规划虽然是人工智能中较早的研究领域之一，通常我们可以这样定义，如果一 个实体在初始状态下经过一个动作序列，最后到达目标状态，我们就称这个动作序列为 一个规划。给定初始状态和目标状态，求解实体从初始状态执行怎样的规划才能到达目 标状态的过程叫做求规划解，求得的规划叫做规划解。直观的说，一个规划解实质上就 是一个动作序列，此动作序列能实现某一种目标。智能规划就是设计这个动作序列的过 程，即主要解决怎么做，而不解决为什么这样做。 一般地，我们在做规划之前，大多做以下的假设： 1 环境状态的改变完全是由智能体的动作效果造成的，排除了其他可能的影响和 干扰。 2 智能体的动作的效果是完全确定的。 3 智能体能够感知环境和它的动作的效果。 通常，我们把满足以上假设的规划称之为“经典规划 阿1 ，例如地图着色问题、积 木世界问题等都是经典的规划问题。现在，大多数研究者还在采纳此假设。但是由于现 实世界的复杂性，实际问题往往并不能满足上述条件，因此一部分学者正在致力于放宽 这一假设，研究在环境不断变化情况下的规划问题。相应地，我们把不满足该假设的规 划问题称为“非经典规划”问题。 东北师范大学硕士学位论文 求规划解的系统称为规划器，它是一种应用软件。当给定初始状态、目标状态以及 相关操作等信息后，这个应用软件就可以给出从初始状态到达目标状态的规划解，即自 动给出动作序列，使得在初始状态下通过执行这个动作序列就可以到达目标状态。规划 器要在尽可能短的时间里，给出质量尽可能高，甚至最优的规划解。在这里规划算法无 疑成为规划器的核心，目前对于规划算法的研究已经越来越热，使得规划问题的理论研 究迈向了新的台阶。 2 2 智能规划的发展及应用 1 智能规划的发展 智能规划阳3 是人工智能领域的一个经典问题，对其研究始于2 0 世纪6 0 年代，并主 要依据两个已得到深入丌发的技术：搜索和定理证明。可以说最早的规划系统是g p s 。 原则上g p s 可以解决任何搜索问题，但是它需要设计操作符差别表来记载各操作符能 消除的状态差别，这是耗时和冗繁的。与g p s 同期开发的规划系统是g r e e l l 系统。该 系统将规划问题的解决归约到定理证明：引入状态演算来演绎动作序列。但其使用的推 理链导致了难以解决的搜索问题且效率极低。由于各自缺点，二者都只能用于解决简单 的规划问题。斯坦福研究所于1 9 7 1 年开始设计著名的机器人动作规划系统s t p s ，它 是早期自动规划领域中具有重要影响的一个系统。该系统本质上是g p s 的特殊应用， 但它采用g r e e n 系统中状态演算方法，解决了框架公理问题，对推动规划技术的研究具 有划时代意义。此后到1 9 7 7 年先后出现了h a c 三r 、w a 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 a p m a n 设计的规划系统 t w e a k 出现。由于c h a p m 肌的分析，人们认识到简单地利用定理证明的方法来解决 规划问题是很难的，因此这以后到1 9 9 0 年间，在人们发现新的求解方法之前，对智能 规划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a l 【和p r o d 远y 等智能规划器出现。 9 0 年代，规划系统的研究达到高潮，这时主要采用三种方法来产生规划算法。第 一种方法是1 9 9 2 年k a u t z & s e l m a n 提出的规划可满足性方法s a t ( s a t i s f i a b i l i t y ) ，该方法 将规划翻译成命题可满足问题加以解决。第二种方法是1 9 9 5 年b l u m & 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 l l 来解决更多的问题，如l 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 虢r 提出的启发 式搜索规划。h s p ( h e u r i s t i cs e a r c h 访gp 1 锄i n g ) n 们和f f ( 缸t 南删a r d ) n 都是启发式规划器， 它们都使用放松的规划任务，而放松任务的规划图中不包含任何互斥关系。目前采用的 启发式多为距离估计，如将当前状态与所要到达的目标状态的距离作为启发式估计。 4 东北师范大学硕士学位论文 h s p 和f f 均采用此种方法，但二者具体实现不同。h s p 假定命题可以独立的实现，忽 略了动作之间可能的交互作用。f f 则采用并行动作估计，f f 的启发式通常要比h s p 估计要低，因为它考虑了命题之间积极的交互作用。目前将各种方法混合使用，规的 效果较好。如b l a c k b o x h l 将命题满足性和规图结合运用，取得第一届规器比赛的冠 军；f f 将规图结构和启发式搜索统一使用，获得第二届规器比赛的冠军，并且在 此次比赛中，规图算法和启发式知识相结合的技术也被发现可以得到更好的规解。 综上所述，规问题求解首先实现了从最初的定理证明方法到s t p s 方法的问题 求解方法上的转变，然后又发展了非线性规器，并且采用以目标为导向的方式来生成 规，一方面使得规的生成速度大大提高，另一方面，由于是目标导向的生成方式， 因此生成规的质量比较好。现在人们又在此基础上加入了启发式信息，进一步提高规 求解的效率和质量。 2 智能规在各领域的应用 目前智能规在自动系统中的应用使得自动化系统的灵活性、健壮性和适应性得到 显著提高。智能规的主要应用领域有机器人、智能企业和商业软件。 智能规的一个重要应用领域是航天航空，在该领域的应用中取得最好效果的是美 国宇航局的a s p e n ( a u t o m a t e ds c h e d u l i i l ga n dp l 籼i 1 1 9e n v 拍m e n t ) h 副规 系统。 a s p e n 获得了1 9 9 9 年美国宇航局的软件比赛优秀奖并且广泛用在进行外太空任务的宇 航器上。 规在机器人领域中的应用主要有环境、机器人能力和目标三者的模型化描述以及 实时的输入响应。不同于其它规研究领域，机器人领域的规研究主要在于当处于有 噪音的环境模型中，机器人通过感应器和交流信道得到的信息都存在噪音，这样它就需 要将感应和执行整合来进行直接规 。 智能规在机器人学中具体的应用方向有环境模型的描述、控制知识的表示、路径 规、任务规、非结构环境下的规、含有不确定性的规、协调操作( 运动) 规 、 装配规、基于传感信息的规、任务协商与调度和制造( 加工) 系统中机器人的调度等。 智能规是人工智能研究中应用性很强的一个研究领域，例如在工厂作业调度规 问题中( j o bs h o ps c h e d u l m g ) ，就是要考虑在加工资源( 车床，刨床，钻床) 有限的情况 下根据己知的工件的加工顺序要求对整个车间的生产做出安排，使得加工完所有工件所 需的时间尽可能的少，每台机床的等待时间尽可能的短，以使工厂在同样设备条件下， 由于作业调度规合理而增加了生产能力，从而给工厂带来了可观的经济效益。 智能规在商业中的应用更加广泛，对原有的经典规作了更大的扩充，其目标状 态可以只是满足某个条件，而不是明确的命题。目前主要研究领域有：网络信息集成和 运输规 。 5 东北师范大学硕士学位论文 2 3 智能规划的语言 规划过程就是一个问题求解过程，利用它来求解比较复杂的问题。规划问题的定义 是规划问题求解的前提，如果一个规划问题不能通过规划语言来表示，则任何一个规划 器都不能对它进行求解，所以说规划语言的发展是智能规划发展的关键。1 9 7 1 年f i k e 和n i l s o n 的s t 刚p s 系统在智能规划中具有划时代的意义，因为它使得规划可以非常容 易地进行描述和操作。但随着规划技术的应用，人们发觉s t 对p s 表示的表达能力非常 有限，它不能满足一些实际问题的模型化要求。设计一种能够刻画和模型化一个实际问 题的规划问题定义语言成为了规划技术应用的前提。1 9 8 6 年e p e d n a u l t 提出了动作描述 语言a d l ( a c t i o nd e s c 啷t i o nl a n g u a g e ) n 3 1 。a d l 除了具有s t 对p s 的表达能力外， 还能表达条件效果和量化效果等语言特征。1 9 9 8 年d r e wm c d e n n o t t 提出了规划领域 定义语言( p d d l ) n4 1 ，它逐渐地成为公认的国际智能规划比赛( 缸e r n a t i o n a lp l a n n i n g c o m p e t i t i o n ，i p c ) 的标准语言。p d d l 语言不仅给出了规划问题定义的语法，也从语义的 角度给出了规划的定义。p d d l 语言的表达能力非常强，能够刻画规划问题的时间和数 值方面的属性，超过了现有的规划器所能处理的表达能力，给规划器的发展提出了挑战， 指明了方向。规划语言是规划领域交流和沟通的标准，对于不同的规划器我们可以通过 它们对同一种语言表示的规划问题的处理来进行性能比较u 引。 2 3 1s t r i p s s t p s ( s t a n 如r dr e s e a r c hi n s t i t u t ep r o b l e ms 0 1 v e r ) 是斯坦福研究院在1 9 7 1 年开发 的一个机器人行为规划系统，解决了框架问题，对规划问题的研究起着划时代的意义。 为了描述s t p s 中的操作和世界模型( w o r l dm o d e l s ) ，开发了s t p s 语言。实际上， 这种语言不仅仅应用于s t 砒p s 系统，还应用于其它规划系统中，g r a p l l p l a n 就是其中 之一。 在s t p s 语言中，操作和世界模型都是采用具有良好形式( w e l l 旬m e d 南m m l a ) 的一阶谓词演算公式来描述的，即所有的变量在使用之前都有辖域限制。如v x p ( y ) 就不 具有良好的形式，因为变量y 没有受到辖域的限制。 世界模型是一阶谓词演算公式的集合。s t 砌p s 语言用一系列完整的基本文字来描 述问题的初始状态，并且将目标定义为命题的合取，所有满足目标形式的状态都将被考 虑。 操作由合取的前提条件和合取的效果两部分组成，它们定义了从状态到状态的过渡 函数。其中前提条件说明了该操作在何种情况下可以应用；效果则说明应用该操作以后 会添加哪些新命题，删除哪些原有命题。 6 东北师范大学硕士学位论文 一般一个规划问题可以形式化地定义成以下三个输入： 1 用某种形式语言对该领域的初始状态的描述。 2 用某种形式语言对目标的描述。 3 可能被执行的操作的描述，这个描述通常被称为域理论。 2 3 2a d l 采用s t p s 语言描述的经典规划问题具有一定的限制条件，其中最重要的一个是 s t p s 要求文字是无函数的，另外它还要求动作的前提和效果都是命题的合取，时间 被离散的表示，动作既不能创建新的对象，也不能消灭原有对象，并且动作一旦执行， 其执行的结果是确定的。这种规划描述语言不能满足一些实际问题的模型化需求，对某 些问题不能全面描述，甚至根本就无法描述，所以要解决这一类现实问题就必须重新设 计新的问题描述语言。1 9 8 6 年e p e d n a u l 提出了动作描述语言一一a d l ( a c t i o n d e s c r i p t i o nl a n g u a g e ) 。 a d l 对s t p s 语言进行了扩展，放松了其中的一些限制，除了具有s t 融p s 的表 达能力外，还能表达条件效果和量化效果等语言特征。条件效果是动作描述中与上下文 相依赖的效果，一般用、h e n 子句来表示。、e i l 子句由前提和结论两部分构成。动作 执行后，只有w h e n 子句的前提也同时满足，才生成结论中的结果；量化效果是允许在 动作的效果描述中具有存在量词和全称量词。a d l 的扩展使得规划方法能够对更多的 实际问题进行编码。u c p o p 是采用a d l 表达的第一个规划器。 s t 砌p s 语言和a d l 语言的主要区别如下： 1 s t p s 在状态表示中只有正文字，而a d l 在状态中既有正文字又有负文字。 2 s t 对p s 采用了封闭世界假设，认为未被提及的文字均为假，而a d l 则采用开 放世界假设，认为未被提及的文字是未知的。 3 s t 融p s 中效果p 八一q 意味着增加p ，删除q ；而在a d l 中表达式p 1 q 则意 味着增加p 和1 ( 2 并删除一p 和q 。 4 s t p s 的目标中只包含基本文字，而a d l 的目标中则包含有量化变量，这样 更有利于表达。 5 s t 刚p s 的效果要求用合取表达式，而a d l 中则允许包含条件效果。 6 s t p s 中不支持等式，a d l 中包含等式谓词。 7 s t p s 中不支持类型定义，a d l 中变量可以具有类型。 2 3 3p d d l 智能规划的研究逐渐地从理论研究走向实际应用，而将规划技术运用到实际问题领 域就不可避免地涉及到一个问题：如何模型化一个实际问题领域并进行推理。1 9 9 8 年， 7 东北师范大学硕士学位论文 d r e wm c d e 彻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 讹n l e n t s 标 志来表达特定问题域描述所要求表达能力的层次水平，这样可以使一个规划系统优雅的 拒绝那些具有它所不能处理的语言特征的问题域。 1 p d d l l 2 p d d l l 2 n 们是1 9 9 8 年第一届国际智能规划比赛使用的规划语言，它只是简单地给 出了如何定义规划问题域以及规划问题的语法标准，并没有给出规划的语义。p d d l l 2 包含了s t p s 表示和a d l ，即如果某个问题可以由s t 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 n 利， p d d l 2 1 与p d d l 前面的版本兼容，它去掉了p d d l l 2 中不常使用的部分，增加了数 值表达、规划尺度和持续动作等新的表达能力，下面具体地介绍几个p d d l 2 1 新的扩 展： p d d l 2 1 中的数值表达是通过函数来实现的，原始数值表达通过领域中的函数与 领域中的对象相组合而成，数值表达是由原始数值表达和算术操作符组成的表达式。数 值条件通常是一对数值表达的比较，可以用一个三元组 来表示，其中 e x p 和e x p 都是一个数值表达，而r c l 是关系操作符( ，= ， = ) 。数值效果利用赋 值操作来更新原始数值表达。 p d d l 2 1 中规划尺度( p l a nm e t r i c ) 的引入是为了能够更好地根据问题域的特点来评 价规划的质量。在给定的不同的规划尺度下，同样的初始状态和目标状态可能产生完全 不同的最优规划。 规划尺度是在问题描述中定义的，定义过程如下：( 1 ) 为了从明确的具体量( 数量) 上定义一个规划尺度，则必须先在问题域描述中引入那个数值量；( 2 ) 在问题描述中加 入该规划尺度；( 3 ) 在初始状态中将该规划尺度的值进行初始化；( 4 ) 在对影响该规划尺 度的动作中添加相应的数值效果。 p d d l 2 1 定义了两种形式的持续动作：离散持续动作和连续持续动作。离散持续 动作中时序关系的模型化是通过对前提和效果添加一个时间注释实现的。持续动作中的 所有条件和效果都必须加上时间注释。离散持续动作和连续持续动作的区别主要在于动 r 东北师范大学硕士学位论文 作效果发生的时间。离散持续动作抽象出某些变量连续的变化，使变化发生在执行期的 结束点上；但是如某些数值变量是随时间的连续变化的且规划器需要在任意一时间点上 知道这些变量的值，就不能把动作效果发生在执行的结束点上，这时候t 是一个连续变 量，而e ( t ) 随着t 变化而变化，具有这样动作效果的持续动作称为连续持续动作。 图2 1j u g - p o u r i n g 域中部分p d d l 编码 图2 1 的例子定义了一个j u g p o u r 吨域，其中函数a m o u n t 和c a p a c i t y 分别为各自 的对象进行了水量和容量的数值赋值，而赋值操作i l l 咪嬲e 则更新了? l j u 9 2 对象的水量。 3 p d d l + p d d l + 阳是对p d d l 2 1 的第5 层描述，它引入了两个附加的模型化部件：过程 和事件。过程和事件的引入意味着那些用持续动作来模型化的领域特点在第5 层可以使 用由起始点、过程和结束点三部分组成的结构来进行模型化，在起始点和结束点可以运 用动作或事件，也可以是活跃过程的效果导致一个数值到达关键阈值的点，这称为 s t a n p 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 n 鲫保留了p d d l 2 1 的前三层的表达能力，新增了导出谓词和初始化时间 命题这两种表达能力。 9 东北师范大学硕士学位论文 导出谓词( d 喇v e dp r e d i c a t e s ) ：导出谓词在以前的一些规划系统中已经实现，例如 u c p o p 。它们是那些不被规划器的任何动作所影响的谓词。然而，谓词的真值来自一 些形如：i f q ( x ) t h e l lp ( x ) 规则的集合。导出谓词提供了一种简洁和方便的方法来表达对 关系的传递闭包的更新，这种更新出现在那些包含一些结构的域中。 时间化初始文字( t 硫e di 1 1 i t i a l l i t e r a l s ) ：时间化初始文字是一种很简单地表示某种 限定形式的外部事件的方法。规划器事先已知将在某个时间点变为真或假的事实，与规 划器动作的执行无关。时间化文字表示的是确定性的无条件的外部事件，跟实际应用是 很相关的。 1 0 东北师范大学硕士学位论文 第三章概率规划 规划过程是一种问题求解方法，一个规划系统可以认为就是一个问题求解系统，若 用它求解比较复杂的问题，即可求得一个动作集合序列，依次执行此动作集合序列就可 以完成某一特定的具体任务，最终从初始状态达到一个特定的目标状态。 经典的s t p s 域满足三点假设，这种强制性使得规划器只能求解对世界信息完全 可知的、问题规模较小的模型规划问题，因此具有不完全信息和不确定信息的规划问题 已经成为近几年智能规划的研究热点。 描述不确定信息的一种模型就是概率方法。用概率的方法进行不确定推理是人工智 能中非常重要的方法，研究者把它运用到规划中也体现了这种方法的优越性。s t p s 语言要求的动作执行效果确定，概率规划器将动作结果放宽到动作结果具有概率输出， 用概率分布来描述不确定性。即动作执行后有若干种可能的输出结果，每种可能的输出 结果都附有相关的概率值。同时概率规划器也允许状态信息的不确定性，即状态也可以 用一定的概率值表示。 3 1 概率规划器的发展 目前已经有许多有效的概率规划器，其中b u r i d a n 乜们是第一个部分可观察条件下的 概率规划器。c b u r i d a n 乜门扩展了b u 耐a n 产生随机规划，避免了求解规划的盲目性。 规划器m a x p l a i l 乜2 1 把规划问题编译成一个e m a j s a t 问题并被用来产生随机规划。 p g r 印h p l a l l 是一个基于图规划算法的概率规划器，它第一次把规划图引入了概率规划 中，产生一个基于前向搜索的最优的随机规划。最优是指在给定的时间步内使规划成功 的概率最大。p g r a p h p l a n 规划器采用与图规划相反的搜索过程，利用动态规划算法， 每一步都选取最优动作，从而找到成功概率最大的规划解。但在p g r a p h p l a n 算法中限 定每个时间步只许一个非空动作，这样g r 印h p l a n 中提出的互斥关系就没有意义了。 为了能够有效利用规划图中的互斥信息，b l u m 和l 肌g 旬r d 等人又提出了t g r a p h p l a n 算法。t g r a p h p l a n 采用与图规划相同的规划扩张算法，只是动作互斥和命题互斥的定 义略有不同。同样采用后向链进行搜索，并找到从初始状态到目标状态的最优轨迹。所 谓的轨迹是指动作和可能输出效果的序列。t g r 叩h p l a n 算法比p g r a p h p l a n 速度快，但 它只返回满足条件的第一个规划解，找到的并不是最优规划解。 东北师范大学硕士学位论文 3 2 概率规划简介 3 2 1 概率规划表示 1 概率规划领域定义语言 1 9 9 8 年，d r e wm c d e n n o t t 提出了规划领域定义语言( p 1 a nd o m a i l ld e f m i t i o n l a i l g u a g e ，p d d l ) 随后p d d l 逐渐成为规划领域模型表示和交流的通用标准，并成为 国际智能规划比赛的标准语言。2 0 0 4 年，h y 0 u n e sh 和l i t t n l a nm 提出了p p d d l l o 以处理动作带有不确定效果的概率规划问题乜引，概率部分的比赛使用的语言即是 p p d d i ，1 o 2 4 。 2 p p d d l 语法 相对于经典规划领域定义语言p d d l ，p p d d l l o 增加了新的表达能力，主要包括 两个方面，即对概率效果的支持、对马尔可夫决策过程回报值的支持。在概率规划中， 动作的效果是随机的，因此p p d d l 增加了对概率效果的支持，其语法表示为： ( p r o b a b i l i s t i cp ，p ，p te 女) 其中p ，表示动作的一个可能效果，p f 表示动作效果白出现的概率，并且鼽满足如下约束： p 却， 鼍。p = 1 。 但有时也允许某个空的概率效果出现，即 ( p r o b a b i l i s t i c p ，p j p ，e ，) 其中： 鼍乳 这种表示和下面的表示是等价的： ( p r o b a b i l i s t i cp ，p p ，p fg ( a i l d ) ) 其中： g = 1 一罨一t ， ( a n d ) 表示空效果。 例如，( p m b a b i l i s t i co 9 ( c 1 0 9 9 e d ) ) 表示命题c l o g g e d 以o 9 的概率在下一状态中变为真， 以o 1 的概率保持原有真值。 1 2 东北师范大学硕士学位论文 另一方面，p p d d l 使用关键字r e w a r d 来表示动作或规划的回报值，其基本语法 表示为： ( ) 其中， 为增加回报算子或减少回报算子， 是不包括r e w a r d 的数值 表达。动作的前提和效果不涉及变量r e w 莉。能同时支持概率效果和回报的域可声明需 求标记：m d p 。 图3 1 显示了咖啡传送域心町的p p d d l 语言表示，当b u y - c o 彘e 动作执行时，如 果使用者得到了c o 虢e ，则获得o 8 的回报。当在i s w e t 为假时，执行“b u y c o 脏e ”动作， 获得的回报则是o 2 。