（计算机软件与理论专业论文）基于互斥约束的概率规划器及其扩展算法的研究与实现.pdf

摘要 智能规划是人t智能研究领域近年来发展起来的一个热门分支， 由于其广泛的实 用性， 受到研究者的高度重视。 尤其是具有不完全信息和不确定信息的规划问题已 经 成为智能规划中的研究重点。 在各种研究方法中， 由于概率方法能较准确地对不确定 信息进行定量描述，因此研究动作具有概率输出的概率规划方法体现了 较强的优越 性，这个方法得到了研究者的肯定，并在此基础上产生了大量的算法。在 2 0 0 4 年举 行的i p c - 4 ( 2 0 0 4 i n t e r n a t i o n a l p l a n n i n g c o m p e t i t i o n ) ， 第一次把概率域列入了 竞赛的项目，再一次表明了概率规划在智能规划研究领域中的重要地位。 智能规划领域的研究者针对规划问题中的不确定性 u n c e r t a i n t y )问题和不完 全信息 ( i n c o m p l e t e ) 问 题， 开发了一些有效的规划器， 其中b l u m 与l a n g f o r d 提出 了 专门针对动作结果不确定的规划问 题的 算法p r o b a b i l i s t c g r a p h p l a n ( 简称p g p ) i 相关的实验结果表明p g p 优于解决同 类问 题的规划器b u r i d a n , s p i , b l a c k b o ， 等。 但 p g p 算法只局限于处理s t r i p s 动作的 概率规划问 题，对于动作带有条件效果的概率 规划问题， p g p 算法就不适用了。 为了 扩大p g p 规划器的处理范围， 提出该研究课题。 本文首先从表示方法、 规划类型、 复杂度、 规划语言等几方面分析了概率规划的 研究现状， 概括了 研究概率规划的相关理论和相关技术， 并分别介绍了经典规划器与 概率规划器中对动作带有条件效果的规划问 题的处理方法， 其次介绍自己做的主要工 作， 包括两个部分: ( 一) 研究与实现基于互斥约束的概率规划器， 该规划器是对p g p 加以改进，改进后的算法相对于p g p 规划器减少了规划图中的结点数目， 节省了存储 空间.( 二)提出处理动作带有条件效果的概率规划器的算法。最后阐明了未来继续 要做的工作， 对第二部分提出算法进行程序实现。 关键词:概率规划;互斥约束;条件效果 ab s t r a c t n o w i n t e l l i g e n t p l a n n i n g i s a v e r y h o t b r a n c h i n a i . b e c a u s e o f i t s w i d e a p p l i c a t i o n r e s e a r c h e r s p a y m u c h a t t e n t i o n t o p l a n n i n g t e c h n o l o g y . e s p e c i a l l y , p l a n n i n g u n d e r u n c e rt a i n t y a n d i n c o m p l e t e h a s b e c o m e t h e f o c a l p o i n t s t u d i e d . i n v a r i o u s k i n d s o f r e s e a r c h a p p r o a c h e s , b e c a u s e t h e p r o b a b i l i t y m e t h o d c a n d e s c r i b e t h e u n c e r t a i n i n f o r m a t i o n r a t i o n r e l a t i v e l y a c c u r a t e l y , s o s t u d y t h e p r o b a b i l i s t i c p l a n n i n g t h a t t h e o p e r a t o r h a s p r o b a b i l i s t i c o u t c o m e r e l a t i v e l y s t r o n g s u p e r i o r i t y i n m e t h o d . ma n y r e s e a r c h e r s a r e i n f a v o r o f t h i s m e t h o d a n d h a s p r o d u c e d a l a r g e a m o u n t o f a l g o r i t h m s o n t h e b a s i s o f t h i s . i n t h e 2 0 0 4 i n t e r n a t i o n a l p l a n n i n g c o m p e t i t i o n t h a t h o l d t h i s y e a r , l i s t t h e p r o b a b i l i t y d o ma i n i n t h e p r o j e c t o f t h e c o n t e s t f o r t h e f i r s t t i m e . t h i s i n d i c a t e s a g a i n t h a t p r o b a b i l i s t i c p l a n n i n g i s t h e i m p o r t a n t s t a t u s o f t h e r e s e a r c h fi e l d i n i n t e l l i g e n t p l a n n i n g . r e s e a r c h e r s i n i n t e l l i g e n t p l a n n i n g a r e a d e v e l o p s o m e p l a n n e r s w h i c h s o l v e u n c e rt a i n a n d i n c o m p l e t e p l a n n i n g p r o b l e m . b l u m a n d l a n g f o r d d e v e l o p p r o b a b i l i s t i c g r a p h p l a n ( p g p ) . e x p e r i m e n t a l r e s u l t i n d i c a t e s t h a t p g p o u t p e r f o r m s o t h e r p l a n n e r s w h i c h s o l v e c o n g e n e r i c p r o b l e m, s u c h a s b u r d i a n , we a v e r , ma x p l a n . b u t p g p c a n o n l y s o l v e s t r i p p l a n n i n g p r o b l e m, p l a n n i n g p r o b l e m s w i t h c o n d i t i o n a l e f f e c t a c t i o n c a n t b e s o l v e d b y p g p t h i s t e x t f i r s t l y a n a l y s e s p r o b a b i l i s t i c p l a n n i n g r e s e a r c h c u r r e n t s i t u a t i o n f r o m p r e s e n t a t i o n m e t h o d s , p l a n n i n g t y p e s 、a l g o r i t h m c o m p l e x i t y , p l a n n i n g l a n g u a g e , s u m u p v a r i o u s k i n d s o f t h e o r i e s a n d t e c h n o l o g y r e l e v a n t t o t h e s t u d y m e t h o d o f p r o b a b i l i s t i c p l a n n i n g , a n d i n t r o d u c e s t e c h n i q u e o f d e a l i n g w i t h c o n d i t i o n a l e f f e c t i n c l a s s i c a l a n d p r o b a b i l i s t i c p l a n n e r s r e s p e c t i v e l y . s e c o n d l y t h e t e x t i n t r o d u c e s m a i n w o r k s b y my s e l f w h i c h i n c l u d e t w o s e c t i o n s . t h e fi r s t i s t o r e s e a r c h a n d i m p l e m e n t p r o b a b i l i s t i c p l a n n e r b a s e d o n m u t e x c o n s t r a i n t . t h i s p l a n n e r i s i m p r o v e d f r o m p g p , d e c r e a s e s t h e a m o u n t o f n o d e s i n t h e p l a n n i n g g r a p h a n d s a v e s s t o r a g e s p a c e . t h e s e c o n d i s t o i n t r o d u c e a l g o r i t h m o f d e a l i n g w i t h p r o b a b i l i s t i c p l a n n i n g p r o b l e m w i t h c o n d i t i o n a l e f f e c t a c t i o n . f i n a l l y t h e t e x t c l a r i f i e s t h e f u t u r e w o r k : i m p l e m e n t t h e a l g o r i t h m i n t h e s e c o n d s e c t i o n . k e y w o r d s : a i ; p r o b a b i l i s t i c p l a n n i n g ; m u t e x c o n s tr a i n t ; c o n d i t i o n a l e f f e c t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。 据我所知，除了 文中特别加以标注和致 谢的地方外， 论文中不包含其他人已 经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名 史隧一.日 期 : 2 0 4 r . 上2 4 ) 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即:东北师范大学有权保留并向国家有关部门 或机 构送交学位论文的复印 件和磁盘，允许论文被查阅 和借阅。 本人 授权东北师范大学可以 将学位论文的全部或部分内 容编入有关数 据库进行检索，可以 采用影印、 缩印或其它复制手段保存、 汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 日期: 指导教师签名: 2 0 叱s ; 2 0 日期: 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话 邮编 引言 在人工智能的研究中规划是较早的研究领域之一，近年来，国际上对规划的研 究越来越热，a a a i 和 u c a i 中有大约 1 / 4规划方面的文章.从 9 8 年开始，i j c a i 每两年举行一届智能规划与调度竞赛。 在应用方面， 规划技术广泛应用于工厂的作 业调度 ( j o b s h o p s c h e d u l i n g ) 、 宇宙航行、车辆调度等领域。 m u r p y 等人1 9 9 6 年 为 美国 联邦 太平洋铁路建立了 基 于规 划的自 动 调度系 统 ll , k n o b l o c k 等人 用规划方 法 解决q u e r y p l a n n i n g 问 题，是规 划技术 在i n t e rn e t 上的成 功应用 12 1 。 1 9 9 8 年底， 美 国的n a s a发射的d e e p s p a c e o n 。 宇宙飞 船的 燃料自 动控制系统使用了 基于s a t 的 规划方法f 3 1这些表明智能规划的 研究己 经走出 实验室应用于实际， 在人工智能 领域形成了智能规划这一当前研究热点。 智能规划就是设计一个动作序列，使a g e n t 从初始状态出发， 执行该动作序列 就能达到目 标状态。对规划的理论研究始于对经典规划的研究， 经典规划满足以下 的假设( 功动作的执行前件是确定的;( 2 ) 动作的执行后件是确定的; 3 ) 规划是动 作的序列. 美国的 a .l .b l u m 教授与 m.l .f u r s t 教授于 1 9 9 5年开发出经典规划器 g r a p h p la n ，提出 的 新颖的 规划图 结 构 4 1给 规 划 领域 带 来了 突 破 性的 进展 ， 但 存 在只 适 用于确定域的局限性 由 于现实生活中 存在大量不完整， 不确定的信息， 如世界初始状态不确定或动作 执行效果( 后件) 不确定等等， 因此针对不确定规划问题展开广泛而深入的研究是有 实际意义的， 不确定规划已 成为当前智能规划研究领域中较为热门的课题。由 于概 率方法能较合理地对不确定信息进行定量描述，因此成为众多研究者的首选方法。 1 9 9 9 年a .l .b l u m教授与j . c .l a n g f o r d 教 授在规 划图 框架的 基础上 提出了 概率规 划 算法 p g r a p h p l a n ( 以下简称 p g p ) 5 1， 相比当时存在的概率规划器，如 b u r d i a n ,m a x p l a n ,w e a v e r 等等， 速度要 快， 但p g p只局限 于处理s t r i p s 动作且 动 作结果不确定的概率规划问题。 本文主要在p g p 的基础上做了两项工作， 第一个是 研究并实现了基于互斥约束的概率规划器，该规划器减少了规划图中的结点数目 ， 从而节省了 存储空间。 第二个是专门针对p g p 只能处理s t r i p s 动作这一局限性而 做的一些工作， 借鉴己开发出的一些经典规划器和不确定规划器中处理条件效果的 方法， 在p g p 算法的基础上做了一些改动， 使其能够处理动作带有条件效果的概率 规划问题。 本文最后指明了要做的一些后续工作: 对提出的算法进行程序实现， 并进行算 法评估; 扩展p g p 规划器的适用范围， 使其能处理世界初始状态及动作结果均不确 定且动作带有条件效果的规划问题。 第一章 概率规划概述 1 . 1 概率规划 规划问题是 a l 研究中最古老、研究最多的问题之一，它一般定义为:在某 些初始条件下，求得一个动作序列 ( 串 行、并行或串并行混合) ，依次执行此动作 序列可以 完成某一特定的具体任务， 最终达到一个特定目 标。由 于它具有很强的 现 实 意义和应用价值， 很多 研究者都致力于它的 理论研究工作: 寻找表示方法和算法 来高效地解决一些重要的问题并通过经验来评估表示方法和算法的有效范围和实 用性。 但是我们看到，隐藏在这个模型下的 假设约束是很强的: 初始状态已 知，动作 的 效果已 知， 不 存在我们不知 道的 能改 变 状态的外 部事件 ( e x o g e n o u s e v e n t s ) 。 也 就是说世界是全知的 ( o m n i s c i e n t ) 。 对于人类和机器来说，这个模型几乎是不可 能存在的，因为几乎不可能完全了解世界并完全控制世界状态。比如说，一个机器 人拿钥匙上楼去开门并不能保证机器人能把门打开，可能是因为楼梯台阶设计过 高， 机器人上不去;也可能是机器人中途把钥匙弄丢了，或许还有一些我们无法了 解的因素，都使我们对机器人是否能开门无法有一个明确地说明。为了能更加真实 地描述这个世界状态， 产生了 经典规划的各种代替模型。 其中一种模型就是用概率 的 方法描述不确定信息。 用概率的方法进行不确定推理是人工智能中非常重要的方 法， 研究者把它运用到规划中也体现了这种方法的优越性. 研究者 提出了 许多 有效的 概率 规 划器。 b u r id a n lb l 是 在部分可观察 条件下的 第 一 个 概率 规 划 器。 c - b u r i d a n 扩展了b u r id a n 产生 随 机( c o n t in g e n t ) 规 划 17 1 。 规 划 器 m a x p l a n is l 把规划问 题编译成一个 e - m a j s a t问 题并被用来解决相应规划。 p g r a p h p la n l5 l 是 一 个 基 于 规 划图 的 概 率 规 划， 它 第 一 次 把 规 划图 引 入了 概 率 规 划 中 ， 产生了一个基于前向搜索的最优的相应规划。 综合各种概率规划器的特点，我们简 要地介绍一下概率规划及相关知识。 1 . 1 . 1 状态表示 概率规划中关于状态的表示方法有两种， 一种是单调域 ( fl a t d o m a i n ) ， 另一种 是命 题域 p r o p o s i t i o n a l d o m a i n ) 。 单调 域指状态是一个单一的整体，它明 确地列举 状态， 如机器人拿着钥匙在楼下这个状态我们可以指定为s l ， 命题域是认为状态是 2 4尔状态变量或命题的集合。上面的例子我们就可以用 p 1 表示机器人拿着钥匙， p 2 表示机器人在楼下。 一般情况下， 命题域表示方法会用少量的变量或命题表示较 大的问 题，例:如果有 m个命题，每个命题的值有两个 ( 真或假、0或 1 ) ，就可 以 表示2 m 个状态。 在单调表示法中， 转换函数t 可用一 个is i x is i的矩阵 表示， 在命题表示方法中， 这种is i x is i 的 方法将会形成一 个很大的 矩阵， 所以 转换函 数必须用其它方法表示。 在概率 规划中 ， 命题规划域的 两种常 用表示 方 法是: 概率 状态算子 ( p s o s ) (6 1 和 两 层时 序贝 叶 斯网 ( 2 t b n s ) 9 1 。 尽管这 些表示 方法 和其它 规划域表示方法 有些不同 ， 但从计算复杂性上是等价的， 即用一种方法表示的规划域可在多项式时间内转换为 由另一 种方法表示的相同的规划域， 至多增长多项式级表示空间 1 0 1 1 . 1 . 2 初始世界 一般来说，初始世界就是初始状态，上面我们已经提到状态的两种表示方法， 初始世界的表示方法就是状态的表示方法。但我们研究的是不确定世界中的规划， 初始世界也可能是不确定的， 所以 初始世界也分确定和不确定两种， 确定的初始世 界和经典规划中的定义没有区别。 对于不确定的初始世界， 在概率规划中， 我们还 可以 用概率的方法定义世界的初始状态。 如b u ri d a n l6 l 中， 可能存在多个初始状态， 其中初始状态是这些可能的世界中的一个，即用概率值表示初始状态存在的可能 性。这样我们对不确定的初始状态就会有一个量化的评估，进而来评估整个规划。 1 . 1 . 3 动作表示 在概率规划中，动作具有多个可能输出，每一个输出都伴随一个概率值表示产 生这种输出的可能性。用这种方法定义动作的好处是: ( 1 ) 对于我们知道的可能存在的输出，我们可以 准确地把动作模型化，并且根据 经验对于每一个输出给定一个符合实际的概率值。另外，还有用条件效果 ( c o n d it i o n a l e f f e c t ) 的方法来定义动作模型， 如上例中， 我们可以 用这种条件语义 来表示; 如果动作的前提条件中存在楼梯台阶设计过高这个条件， 那么动作的结果 就是机器人上不了楼; 如果没有这个条件那么机器人就能上去。 但是用这种方法有 时也不能准确地描述动作的结果，比 如说， 如果台阶设计过高，机器人可能上去也 可能不上去，这时候用条件效果的方法就不能准确地定义了。而我们用概率表示动 作输出的方法就可以较清晰地说明了。 ( 2 ) 对于我们不知道的可能输出， 我们假设动作没有产生结果，即动作没有改变 世界状态，也赋给这个输出一个概率值。 这种方法虽然并不十分准确， 但是它占 有 一个动作的输出的可能性，所以也能在生成规划中起到作用。 如图 1 所示， 机器人能上楼的可能性是0 .6 ， 还有 0 .4 的可能性不能到楼上， 不 能到楼上可能的原因是楼梯台阶设计过高， 也可能是其它原因， 但我们不必完全说 图1 具有概率抽出的 动作 4 概率规划的定义 a.11 明l 对于概率规划， 文网 给出了 最早的定义，并且后来的很多算法(s . 5 、 。 川 也都是 根据这个定义来决定算法的执行结果的。 在这个定义下，一个概率规划包含以下几部分: ( 1 ) 状态集合， ( 2 ) 具有概率分布的初始状态， ( 3 )目 标集， ( 4 )能影响随机状态转换的算子集合， ( 5 ) 表示概率规划成功的合理的阐值t 寻找规划就是寻找一个动作序列使主体能在最小概率值为: 的状态下到达目 标状态。寻找最优规划就是寻找到达目 标概率值为最大的规划。 我们可以 用六元组定义上面的概率规划域m = ， 其中s 表示 ( 1 ); s o e s 表示 ( 2 ): a 表示 ( 4 ); 若s , s e s , t 是概率转换函数， t ( s , a , s ) 表示 5 通过a 到达 s 一 的概率;g 表示 ( 3 );t 表示 ( 5 )。 1 . 1 . 5 概率规划的类型 概率 规划域有四 种类型。 第一类是 全 序规 划( t o t a l l y o r d e r e d p l a n ) ， 它是最 基础 的类型， 它的定义是规划中的动作序列是严格按顺序执行每一个动作， 在这类规划 中 每 个时 间 步 只能 有 一 个动 作 被 执 行。 第 二 类是 无 环 规 划 ( a n a c y c l ic ( c o n d it io n a l) p l a n ) ， 它 产生的 规 划包括条件规划的 全序规划。 第三 类是相 对于 全序规 划的 部 分有 序 规 划( p a r ti a l o r d e r e d p l a n ) ， 它 和 全 序 规 划 不同 的 是 它的 动 作 序列 不 必 是 一 个 精 确的序列， 动作的 序列是一个相对的 序列。 最后一类是有环规划( l o o p p l a n ) ， 它产 生具有重复规划步的非循环规划， 这类的 规划也被称为规划图或策略图 14 1 概率规划算法中最成功的是在完全可观察( f u ll o b s e r v a t i o n ) 的假设下的算法。 在这种方法中， 尽管不确定性阻碍了 主体在时间步之前预测运行时间状态， 主体还 能掌握运行时间完全、准确的信息。 另外， 研究人员也采用了部分可观察 ( p a r t i a l o b s e r v a t i o n )的 模型处理 a i 规划问 题， 但是它的复杂性显然受这种工作的 应用程 序所限制。 但这些困难并没有阻止人们对部分可观察问题的热衷， 这是由于部分可 观察的这个假设使规划更具有现实意义， 是使规划问 题走出实验室的一个很重要的 方面，因此它己经成为规划界研究的热点问题。 但是由于加入决策理论己经使规划 图 变得比 较复杂，如果再 进一步考虑部分可观察问题会使问题变得复杂而不可解， 所以本文没有涉及到部分可观察，而一个完全可观察的算法，在未来的工作中， 希 望能把工作扩展到部分可观察情况下。 1 . 2 概率规划和不确定规划 本文主要介绍概率规划算法， 但是概率规划和不确定规划的关系还是值得我们 去研究一下的， 这对于理解概率规划的重要性以 及概率规划在不确定规划中 所起的 作用是很重要的。 由于在实际世界中，我们缺少对知识描述的完整性， 精确性，问 题领域存在很 多不确定的因素， 所以实现经典规划的适用范围有限， 真正能用于应用的是不确定 规划。在不确定规划中我们一般用动作和状态表示世界知识的不确定性。 一般情况下，动作分为概率化动作和非概率化动作。对于概率化动作，我们上 面己 经提到过， 一个状态上动作的输出是一个到达下一状态的概率分布。 一个非概 率化动作其输出一般是条件化的 ( c o n d i t i o n a l ) ,前提条件的不同可能有多个可能输 出。 这时， 给定 执行时的动作的前提条件， 动作的结果是确定的。 但是主体可能 不 知道动作执行时的前提条件，因此也不知道动作的结果。 这样，不确定就表示为一 个可能状态输入/ 输出的列表对，而不是到下一输出的概率分布。 我们用一个简单的例子来区分概率化动作和非概率化动作。积木世界中的概 率动作m o v e ( a , b , c ) ( 即从积木b 上移动积木a 放到积木c 上) 成功的 概率为0 . 8 5 , 放到桌子上的概率为。 . 1 0 ， 什么也没发生的 概率为0 . 0 5 。 一个非概率化的 相同的动 作可能会这样定义，如果机器人的手臂是空的且是干的，动作就会成功，如果手臂 是空的却沾到水了，积木就会掉到桌子上，如果手臂不起作用，什么都不会发生。 概率规划从某种意义上讲是主体关于域的知识的函数。 一个动作可能输出的概 率分布在某种意义上是对域知识比较好的替代品。 在积木世界中，当机器人手臂上 沾有水时，主体可能不知道m o v e 动作失败，但经验允许主体估计那个动作输出的 概率分布。或者， 更深一步讲，主体知道什么时候机器人手臂上会沾到水， 动作通 常会失败，但也有。 .0 5 的可能性会成功。如果主体不知道为什么有时动作会成功， 主 体仍会在动作执行时加上一个概率分布，并且规划也用到这个概率分布。 由此状态表示也有概率化和非概率化之分。 这一般和动作相对应，如果动作是 概率化的， 通常状态的表示也是概率化， 否则不是。 特别是， 初始状态我们有两种 表 示 方法: 一 种是根据经验估计 初始 状态的 概率 5 1 ， 寻找规 划时这种表 示可能性的 概率值加入到规划的值计算中:另一种是所有可能状态并存，寻找一种规划满足所 有可能的初始状态( i 2 , 1 3 1 不确定规划中，我们经常区分条件规划 c o n d i t i o n a l p l a n n i n g ) 和相应规划 ( c o n t in g e n t p l a n n i n g ) 。 在条件规划中， 动作的执行 ( e x e c u t i o n ) 和结果 ( e ff e c t s ) 并不是根据先前一步的动作而定， 动作集是条件动作集; 在相应规划中， 动作的结 果和执行都由先前执行的动作决定。这样，在相应规划中，主体可能会进行观察， 并且根据这些观察建立规划分支。 如果不具备观察动作相应的环境和条件， 主体可 能仅能执行一个线形序规划一个简单的非相应的动作序列。 这样一个规划也可 被称为“ 开 放循环 ( o p e n - l o o p ) ， 和根 据运行时间的 观察 选择条件动作的“ 封闭 循 环( c lo s e d - lo o p ) ” 的 规 划相 对 应。 这两个区别 ( 条件规划 v随机规划和非概率规划 v s . 非概率规划) 可以使不 确定规划器进行下面的分类: ( 1 )具有非概率化动作的条件规划:这种类型的规划器出现在一致规划 ( c o n f o r m a n t p l a n n i n g ) 中， 即 产生一 个线 形序规划并 保证 无论遇见 什么情况 规划都 能成功。如:c o n f o r ma n t g r a p h p l a n j 1 2 1. ( 2 ) 具有非概率化动作的随机规划: 感知动作允许这类规划器产生一个随机规 划，但缺少概率动作意味着规划器必须寻找一个在所有环境下都成功的规划。如 c n l p i . s e n s o r y g r a p h p l a n 1 t b 1 . c a s s a n d r a 1 7 1 o ( 3 ) 带有概率动作的条件规划: 和第一种情况一样， 这类规划器也出现在一致 规划中，但是动作输出附加的概率允许规划器说明线形序规划具有成功的最高概 率 ， 即 使 是 这 个 概 率 值小 于1 .0 。 如b u r id a n b 1 . u d t p o p s 1 , m a x p l a n e 1 o ( 4 ) 带有概率动作的相应规划: 和第二种情况一样， 感知允许这类规划器产生 相应规划。 也像第三种情况那样， 概率动作允许规划器说明规划具有成功的最高概 率 值。 如: c - b u r ma n 7 1 , d t p o p i i , m a h i n u r i i 9 1 ， 和s p u d d i2 o 3 。 我们第三章 讲的规划器也是属于这种类型的规划器。 我们注意到， 第二和第三种情况包含第一种情况， 第四种情况包含其它所有的 情况， 这样表述第四种事例的规划器能用在所有的情况中。 而我们所谓的概率规划 是第三和第四 种规划。 因此， 概率规划是不确定规划的一部分， 而且是主要的那部 分。原因是:( 1 )状态和动作概率分布是根据经验的估计值，具有可信任性;( 2 ) 这种方法使问题的描述更加直接;( 3 ) 而且这种方法中，成功的概率并非唯一所要 考虑的问 题，另外规划长度遥短， 效用值 ( 如果效用函数给目 标状态都赋予一个数 字值，就可以提供对某一方面的衡量)等也是所要考虑的问题。 ，3概率规划复杂度 关于概率规划的复杂度问 题已 经有很多人进行了 研究， 特别是 2 1 对概率规划 进行了 系统而完整的研究， 本文中对概率规划的复杂度的分析主要是来自 这篇文章 的观点。 概率规划的复杂度分析实际上包含两部分的内容:规划评估 ( p l a n 石 e v a lu a t i o n ) 和 规 划 存 在( p l a n e x i s t e n c e ) ， 规 划 评 估 是 指 规划的 效 用 值 是 否能 超过 给 定的阐 值， 即假设一个域m, 规划p的大小为p ( im ，阐值为0 ， 规划的 值是否 大于 0 即是否 p r ( m r e a c h e s a g o a l s t a t e u n d e r p )0 而规划存在是指在给定的界限内， 是否存在规划并且这个规划的效用值大于给 定阐值。即 设一个域 m,闽 值为0 ， 大小的界限是 z ,i m i ， 是否存在一 个规划， 它 的大小z 的值大于0 。但是有些算法中， 规划存在的计算存在于规划评估中，但这 仅是一种特殊情况。一般来说，这种情况规划的复杂度等于规划评估的复杂度。 1 . 3 . 1 复杂类的介绍 在复杂类中， p 类问题是指多项式时间可判定的语言类， n p 是指多项目 式时间 可 验证的 语言类2 2 1 。 在复杂度发展的过程中，由于p 类问 题是否等价于n p 类问题 一直是复杂性理论中的一个难题， 为了解决这类问题， 7 0 年代初， 斯蒂芬. 库克和 列奥尼德 列文发现 n p中的某些问题的复杂性与整个类的复杂性相关联。 提出了 n p 完全 ( n p - c o m p l e t e )问 题。 它的 定 义是这 样的: 语言b 称为n p 完全的，它应满足下面两个条件: ( 1 ) b 属于n p ，并且 ( 2 ) n p 中的每个a 都多项式可归约到b 后面的关于完全 c o m p l e t e ) 复杂类的定义都可以 参照上面的定义。 目 前虽然没有人能证明p 类问题是否等价于n p 类问题，但一般认为p 9 n p . c o - n p 类问 题和n p 类问 题是相对应的， n p 是指多 项式时间可验证为正确的 语 言 类，而c o - n p 是指多项式时间可验证为错误的语言类。 p s p a c e 类是指空间复杂度中 和p 类相对应的 类， 是指多项式空间可判定的 类。 显然p 9 ; p s p a c e ，因为运行得快的 机器不可能消耗大量的空间。更精确地说， 对于 t ( n ) 3 n ， 任何在时间t ( n ) 内 运行的机器最多能消耗n ) 的空间， 因为 机器在每个 计算步上最多能访问一个新单元。类似地， n p 9 p s p a c e e e x p 类问题是指指数时间或指数空间可解的问题。事实上，它基本等于不可解 问题， 很多这类中的问题都是加上某些限定， 使之转化成多项式级的问题才能有效 求解。 l 类是对数时间 可判定的 语言类， p l ( p r o b a b i l i s t i c l o g s p a c e ) 概率对数空 间，是指对于集合a 类，存在一个非确定对数有限空间自 动机n ，当且仅当n 关于 、 可接受的路径大于拒绝的路径时， x 二 a 。 在p l 的原始定义中， 没有关于复杂度的 时间限制。文【 2 3 ) 证明了p l cw p . 2 4 证明了 任意一个概率对数空间可解的问题在 p l 机具有同步多项式时间界限的概率对数空间也是可解的。 和p 完全问题明显不同 的是， p l 中的集合用于判定并行计算的复杂度。 概率多项式时间 ( 即) 的定义和上 面类似， m a j s a t 就是一个p p 完全问题25 对于复杂类c 和c , ， 类c . 由 类c 图灵可归约到c , 的集合组成。即c 中 所限定 的资源接受的集合，用 c , 中的某些问题作为带有即时输出的子程序。如果 c s p s p a c e ，那么n p 9 p s p a c e ，因此n p = p s p a c e o n p p u 5 ) 是指在带有指数级查询( 每一个查询在查询列表下多项式时间可计算) 的 多 项式时间析取可归约下的即的闭 包。 简单来说n 产是概率多项式时间可验证的问 题。 问题是所涉及的复杂类的关系是这样的 p l 三n p co - np c : p p g n p p p c p s p a c e 9 e x p c o - n p p p 1 . 3 . 2 各类概率规划的复杂度 由 于状态的表示方法不同，算法的复杂度计算方法也不同，所以规划域中的 算法对于单调域 ( f l a t d o m a i n ) 和命题域 ( p r o p o s i t i o n a l d o m a i n ) 是对区别对待的。 关于单调域和命题域中各种类型的概率规划的复杂度总结如表1 和表2 0 由 于 无限 制的 ( u n r e s t ri c t e d ) 和多项式深度 ( p o l y n o m i a l - d e p t h ) 这两种类型的 规划 评估存在于判定规划存在中，所以它的值为空。 对于部 分有序规划。 我 们根 据值函 数， 把这 种规划分成三 类: 最优( o p t im i s t i c ) 表示值函数最大的;最差 ( p e s s i m is t ic ) 表示值函数最小的;平均的 ( a v e r a g e ) 表示 取值函数的平均值。 这三种情况下求解规划的方式并不相同， 所以在复杂度计算时 我们把它们看成是三类问题。 从表中我们看到单调域的复杂度要比命题域的复杂度级别要低， 这和我们前面 所提到的: 用命题方式会简化问 题相矛盾。 事实上是用命题表示方法可以 用少量的 命 题 表 达 多 个 状 态 ， 这 样 针 对 同 一 个 问 题， 他 们 处 理 的 问 题 的 规 模 不 同 。 因 此 针 对 具体问题来说，命题的表示方法还是要简单一些， 但也不完全。由表中我们也可以 得知， 在平均值解释下的部分有序规划的复杂度在两种域下都是一样的， 但最优值 和最差值的部分有序规划命题表示方法都比单调表示方法的复杂度要高。 表 1 p l a n t y p e几 u n r e s t r i c t e d p o l y n o m i a l - d e p t h l o o p i n g a c y c l i c t o t a l l y o r d e r e d p a rt i a l l y o r d e r e d , o p t i m i s t i c 单调表示方法的复杂度 i p la n e v a lu a ti o n 一 p l a n e x i s t e n c e p l - c o m p l e t e p l - c o m p l e t e p l - c o m p l e t e n p - c o m p l e t e p c o r r 甲 l e t e p c o m p l e t e n p - c o m p l e t e n p - c o m p l e t e n p - c o m p l e t e n p - c o m p l e t e p a rt l a l y o rd e r e d ，a v e ra g e p a rt l a l l y o r d e r e d ，p e s s i m l s t i c p p 一 c o ll 甲l e te c o 一p 一 c 0 il l p l e te n p 一 o l l l p l et e n p 一 c o m p l e t e 表2命题表示方法的复杂度 p l anl ) ， e u们 r e s tr l c ted p o l yno n u a l 一 d e p th l o opi n g a c y c l l c 尸r ot a l ! y o 了 d e re d p a rt l a l y o rder e d ，o p t l mis t l c p a rt l a l l y o rd e r e d ，a v e ra g e p arti a l l y o rd e r e d ， p e s s i m i s t l c p l 田i ev a l u 3 t i o np l a nex i s t e n c e p s pac e 一 c o it lp l e te p p 一 c o m p l et e p l c o m p l e 忱 p p 一 c o n 1 p l e t e n p p p 一 c o 哪le t e c o 入p p r 一 c o m p le te e x p . c o n 口 p l e te p s p a c e 一 c o m p l e t e p s pac e o n 1 p l e t e n 尹一 。 mple te n p p p 一 。 吻p le te n 尹 。 帅le te 柳pp 一 c o 哪l e t e n p pp 一 c o 帅le t e 1 ， 4 概率规划语言 规划语言作用是对规划域的描述，定义规划的输入输出格式。另外规划语言提 供了规划的表达标准，使域模型能够共享， 促进了 规划域向 现实应用的发展。规划 语言 主 要 有p d d l( th e p lannin g d o m ai n d e finit io n l an 即 ase ) 12 6 、 2 7 2 8 、 a d l i2 9 、 r p l( r e a c t 主 v e p l a n l a n g u a g e ) 、 d d l 。 因 为p d d l强大的 表 达能 力和适用范围， 从第一届智能规划与调度竞赛p d d l就作为竞赛用语言， p d d l己 逐渐成为规划 域的标准语言。 概率规划语言 是对规划语言的进一步扩充， 服务于概率规划的语言。因为语言 往往是对具体问题来定义的，一般不具有共性， 这里我们介绍共性较强的概率规划 语言。 1 .