（计算机软件与理论专业论文）图规划框架下的决策概率规划的研究与实现.pdf

摘要 智能规划是人工智能研究领域近年来发展起来的一个热门分支 由 于其广泛的实用性 受到研究者的高度重视 尤其是具有不完全信息和 不确定信息的规划问题已经成为智能规划中的研究重点 在各种研究方 法中 由于概率方法能较准确地对不确定信息定量描述 因此研究动作 具有概率输出的概率规划方法体现了较强的优越性 这个方法得到了研 究者的肯定 并在此基础上产生了大量的算法 又由于这种概率规划的 研究方法和马尔可夫决策过程 m a r k o vd e c i s i o np r o c e s s e s m d p s 的研 究方法相似 所以很多研究人员在两者之间的结合上做了大量的工作 在今年举行的口c 4 2 0 0 4i n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n 第一次把 概率域列入了竞赛的项目 再一次表明了概率规划在智能规划研究领域 中的重要地位 本文首先从表示方法 规划类型 复杂度 规划语言等 几方面分析了概率规划的研究现状 概括了研究概率规划的相关理论和 相关技术 揭示了概率规划和m d p s 之间的关系 并把决策理论应用到 概率规划中 定义了效用模型下的概率规划 提出了相应的算法d p g d e c i s i o np r o b a b i l i s t i cg r a p h p l a n d p g 算法建立在具有迅速传播能力 的概率规划图 p r o b a b i l i s t i cg r 印h p l a n 上 结合动态编程 d y n a m i c p r o g r a m m i n g 用前向搜索的方法来求最优规划解 我们用c 语言实现 了这个算法 并证明出 在有限时间步内 这是一个多项式级复杂度的 算法 通过实验结果 我们阐明了效用模型下 各因素对最优规划解及 d p g 算法复杂度的影响 最后指明了本算法是对概率规划的有效扩张及 对m d p s 的成功应用 关键词 人工智能智能规划概率规划动态编程马尔可夫决策 过程 a b s t r a c t n o w 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 i b e c a u s eofi 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 ha t t e n t i o nt 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 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 s b e c o m et h ef o c a l p o i n t s t u d i e d i nv a r i o u sk i n d so 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 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 et h eu n c e r t a i n i 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 os t u d yt h ep r o h 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 g s n p e r i o r i t yi nm 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 d a n dh a sp r o d u c e dal a r g ea 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 b e c a u s er e s e a r c ha p p r o a c h e so ft h ep r o b a b i l i s t i cp l a n n i n ga n dm a r k o v d e c i s i o np r o c e s s e sa r cv e r ys i m i l a ra g a i n s oal o to fr e s e a r c h e r sh a v e d o n eal a r g ea m o u n to fw o r ki nt h ec o m b i n a t i o nb e t w e e nt h et w o i n t h e2 0 0 4i n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o nt h a th o l dt h i sy e a r l i s t t h ep r o b a b i l i t yd o m a i ni nt h ep r o j e c to ft h ec o n t e s tf o rt h ef i r s tt i m e t h i si n d i c a t e sa g a i nt h a tp r o b a b i l i s t i cp l a n n i n gi st h ei m p o r t a n ts t a t u s o ft h er e s e a r c hf i e l di n i n t e l l i g e n tp l a n n i n g t h i s t e x t a n a l y s e s p r o b a b i l i s t i cp l a n n i n g r e s e a r c hc u r r e n ts i t u a t i o nf 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 gt y p e s a l g o r i t h mc o m p l e x i t y p l a n n i n gl a n g u a g e s u mu pv a r i o u sk i n d so ft h e o r i e sa n dt e c h n o l o g yr e l e v a n tt ot h es t u d y m e t h o do f p r o b a b i l i s t i cp l a n n i n g a n n o u n c e t h er e l a t i o nb e t w e e n p r o b a b i l i s t i cp l a n n i n ga n d m a r k o vd e c i s i o np r o c e s s e s a l s oa p p l yt h e d e c i s i o n t h e o r y t o p r o b a b i l i s t i cp l a n n i n g d e f i n e t h e p r o b a b i l i s t i c u n d e ru t i l i t ym o d e l p u tf o r w a r dt h ec o r r e s p o n d i n ga l g o r i t h md p gw e s e t su pt h ed p g a l g o r i t h ms t r u c t u r ea b o v e t h ep r o b a b i l i s t i cp l a n g r a p h w h i c hh a v et h e r a p i d l yp r o p a g a t i n ga b i l i t y c o m b i n g t h e d y n a m i c p r o g r a m m i n g w i t hf o r w a r d s e a r c hm e t h o d g e tao p t i m a lp l a n n i n g s o l u t i o ni nf i n i t et i m es t e p w eh a v er e a l i z e dt h i sa l g o r i t h mi n c l a n g u a g e a n d i m p r o v e d t h e c o m p l e x i t y o ft h e a l g o r i t h m i si n p o l y n o m i a li nf i n i t et i m es t e p b yt h ee x p e r i m e n t a lr e s u l t w ec l a r i f y e v e r yf a c t o ru n d e ru t i l i t ym o d e li m p a c to no p t i m u m p l a n n i n gs o l u t i o n a n dd p g a l g o r i t h mc o m p l e x i t y a tl a s t w ep o i n t e d o u tt h em e r i to ft h e a l g o r i t h m t h i si s t h ee x t e n s i o nt ot h ep r o b a b i l i s t i cp l a n n i n ga n dt h e s u c c e s s f u la p p l i c a t i o no ft h em d p s k e y w o r d s a i i n t e l l i g e n tp l a n n i n g p r o b a b i l i s t i cp l a n n i n g d y n a m i c p r o g r a m m i n g m a r k o vd e c i s i o np r o c e s s e s m d p 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果 据我所知 除了文中特别加以标注和致谢的 地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不 包含为获得东北师范大学或其他教育机构的学位或证书而使用过的 材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意 学位论文作者签名 5 蕴鱼j 立日期 塑旦生 塞2 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留 使用学位论 文的规定 即 东北师范大学有权保留并向国家有关部门或机构送 交学位论文的复印件和磁盘 允许论文被查阅和借阅 本人授权东 北师范大学可以将学位论文的全部或部分内容编入有关数据库进行 检索 可以采用影印 缩印或其它复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 盘五f 指导教师签名 同 期 逊毡 5 j 7 日 期 学位论文作者毕业后去向 工作单位 通讯地址 电话 邮编 引言 规划 p l a n n i n g 一词在我们的日常理解中是指在行动之前拟订 行动步骤 j 在人工智能的研究范围中 智能规划 a i p l a n n i n g 实际上 就是一种问题求解技术 即从某个特定问题的初始状态出发 发现一系 列行为或构造一系列操作 也有称之为算子的 步骤 达到解决该问题 的目标状态 规划系统的研究起初源于问题的求解 但是后来规划研究 比起 般的问题求解更注重于解决具体的实际问题 而不单单是抽象的 数学模型 因此近几年来智能规划成为人工智能研究领域一个新的热点 智能规划 a ip l a n n i n g 是人工智能领域的一个经典问题 它的产生 几乎与人工智能同步 由于其广泛的实用性 受到研究者的高度重视 近年来 国际上对规划的研究越来越热 a a a i 和i j c a i 中有大约1 4 规 划方面的文章 从9 8 年开始 i j c a i 每两年举行一届智能规划与调度竞 赛 在应用方面 规划技术广泛应用于工厂的作业调度 j o bs h o p s c h e d u l i n g 宇宙航行 车辆调度等领域 1 9 9 8 年底 美国的n a s a 发 射的d e e ps p a c e o n e 宇宙飞船的燃料自动控制系统使用了基于s a t 的规 划方法 m u r p y 等人1 9 9 6 年为美国联邦太平洋铁路建立了基于规划的 自动调度系统 3 k n o b l o c k 等人用规划方法解决q u e r yp l a n n i n g 问题 是 规划技术在i n t e m e t 上的成功应用 4 这些表明智能规划的研究已经走 出实验室应用于实际 在人工智能领域形成了智能规划这一当前研究的 热点 但是在我国关于规划理论和应用的研究现在还处于初级阶段 由于实际应用的需要 具有不完全信息和不确定信息的规划问题已经 成为近几年智能规划的研究重点 由于概率方法能较合理地对不确定信 息定量描述 因此成为众多研究者的首选方法 又因为概率规划和马尔 可夫决策问题模型的相似 很多研究者把两个问题的研究方法相结合 促进了两方面问题的共同发展 使这两方的研究问题越来载趋于一致 i p c 4 的一个重点目标促使这两个研究内容相似的机构结合在一起创造 出更可比较的方法和工具 本文本着与i p c 4 相同的目地 结合概率规 划和马尔可夫决策问题 在具有迅速传播能力的规划图上 建立高效的 规划算法 实验结果是令人满意的 增强了规划算法处理问题的能力 表明了在有限时间步内 这是一个多项式级复杂度的算法 并进一步揭 示了如何在决策中运用规划来解决问题 最后指明了在这种方法下应继 续做工作 1 1 概率规划 第一章概率规划概述 规划问题是a i 研究中最古老 研究最多的问题之一 它一般定义 为 在某些初始条件下 求得一个动作序列 串行 并行或串并行混合 依次执行此动作序列可以完成某一特定的具体任务 最终达到一个特定 目标 由于它具有很强的现实意义和应用价值 很多研究者都致力于它 的理论研究工作 寻找表示方法和算法来高效地解决一些重要的问题并 通过经验来评估表示方法和算法的有效范围和实用性 但是我们看到 隐藏在这个模型下的假设约束是很强的 初始状态 己知 动作的效果已知 不存在我们不知道的能改变状态的外部事件 e x o g e n o u se v e n t s 也就是说世界是全知的 o m n i s c i e n t 对于人类 和机器来说 这个模型几乎是不可能存在的 因为几乎不可能完全了解 世界并完全控制世界状态 比如说 一个机器人拿钥匙上楼去丌门并不 能保证机器人能把门打开 可能是因为楼梯台阶设计过高 机器人上不 去 也可能是机器人中途把钥匙弄丢了 或许还有一些我们无法了解的 因素 都使我们对机器人是否能开门无法有一个明确地况明 为了能更 加真实地描述这个世界状态 产生了经典规划的各种代替模型 其中一 种模型就是用概率的方法描述不确定信息 用概率的方法进行不确定推 理是人工智能中非常重要的方法 研究者把它运用到规划中也体现了这 种方法的优越性 研究者提出了许多有效的概率规划器 b u r i d a n 5 1 是在部分可观察条 件下的第一个概率规划器 c b u r i d a n 扩展了b u r i d a n 产生相应 c o n t i n g e n t 规划m 1 规划器m a x p l a n l l 2 1 把规划问题编译成一个 e m a j s a t 问题并被用来解决相应规划 p g r a p h p l a n 口l j 是一个基于规划 图 2 0 的概率规划 它第一次把规划图引入了概率规划中 产生了一个基 于前向搜索的最优的相应规划 在概率规划的很多算法都结合了马尔可 夫决策理论 m d p 的知识 这个在本文的后面我们会介绍到 综合各 种概率规划器的特点 我们简要地介绍一下概率规划及相关知识 1 1 1 状态表示 概率规划中关于状态的表示方法有两种 一种是单调域 f l a t d o m a i n 另一种是命题域 p r o p o s i t i o n a ld o m a i n 单调域指状态是一个 单一的整体 它明确地列举状态 如机器人拿着钥匙在楼下这个状态我 们可以指定为s l 命题域是认为状态是布尔状态变量或命题的集合 上 面的例子我们就可以用p 1 表示机器人拿着钥匙 p 2 表示机器人在楼下 一般情况下 命题域表示方法会用少量的变量或命题表示较大的问题 例 如果有m 个命题 每个命题的值有两个 真或假 0 或1 就可以 表示2 个状态 在单调表示法中 转换函数t 可用一个i s l l s l 的矩阵表示 在命题 表示方法中 这种i sj i s l 的方法将会形成一个很大的矩阵 所以转换函 数必须用其它方法表示 在概率规划中 命题规划域的两种常用表示方 法是 概率状态算子 p s o s 5 1 和两层时序贝叶斯网 2 t b n s 2 2 1 尽 管这些表示方法和其它规划域表示方法有些不同 但从计算复杂性上是 等价的 即用一种方法表示的规划域可在多项式时间内转换为有另一种 方法表示的相同的规划域 至多增长多项式级表示空间 2 3 1 1 1 2 初始世界 一般来说 初始世界就是初始状态 上面我们已经提到状态的两种 表示方法 初始世界的表示方法就是状态的表示方法 但我们研究的是 不确定世界中的规划 初始世界也可能是不确定的 所以初始世界也分 确定和不确定两种 确定的初始世界和经典规划中的定义没有区别 对 于不确定的初始世界 在概率规划中 我们还可以用概率的方法定义世 界的初始状态 如b u r i d a n 5 中 可能存在多个初始状态 其中初始状态 是这些可能的世界中的一个 即用概率值表示初始状态存在的可能性 这样我们对不确定的初始状态就会有一个量化的评估 进而来评估整个 d 规划 1 1 3 动作表示 在概率规划中 动作具有多个可能输出 每一个输出都伴随一个概 率值表示产生这种输出的可能性 用这种方法定义动作的好处是 1 对于我们知道的可能存在的输出 我们可以准确地把动作模型化 并且根据经验对于每一个输出给定一个符合实际的概率值 另外 还有 用条件效果 c o n d i t i o n a le f f e c t 的方法来定义动作模型 如上例中 我 们可以用这种条件语义来表示 如果动作的前提条件中存在楼梯台阶设 计过高这个条件 那么动作的结果就是机器人上不了楼 如果没有这个 条件那么机器人就能上去 但是用这种方法有时也不能准确地描述动作 的结果 比如说 如果台阶设计过高 机器人可能上去也可能不上去 这时候用条件效果的方法就不能准确地定义了 而我们用概率表示动作 输出的方法就可以较清晰地说明了 2 对于我们不知道的可能输出 我们假设动作没有产生结果 即动作 没有改变世界状态 也赋给这个输出一个概率值 这种方法虽然并不十 分准确 但是它占有一个动作的输出的可能性 所以也能在生成规划中 起到作用 如图1 所示 机器人能上楼的可能性是0 6 还有0 4 的可能性不能 到楼上 不能到楼上可能的原因是楼梯台阶设计过高 也可能是其它原 因 但我们不必完全说明 图1 具有概率输出的动作g o u p s t a i r s 1 1 4 概率规划的定义 对于概率规划 文 5 给出了最早的定义 并且后来的很多算法旧2 1 2 3 1 3 8 1 也都是根据这个定义来决定算法的执行结果的 在这个定义下 一个概率规划包含以下几部分 1 状态集合 2 具有概率分布的初始状态 3 目标集 4 能影响随机状态转换的算子集合 5 表示概率规划成功的合理的闽值t 寻找规划就是寻找一个动作序列使主体能在最小概率值为t 的状态 下到达目标状态 寻找最优规划就是寻找到达目标概率值为最大的规划 我们可以用六元组定义上面的概率规划域m 其中s 表示 1 s o s 表示 2 a 表示 4 若s s s t 是概率转换函数 t s a s 表示s 通过a 到达s 的概率 g 表示 3 t 表示 5 对于上面给出的这个概率规划的定义 很多人从m d p 的角度给出了 多种算法 但是对于决策来说它是不严格的定义 因为在这种假设下 没有考虑动作的代价以及规划中某些动作的结果会对整个规划有促进作 用丽生成的奖励 也就是说只是衡量了规划到达目标的可能性 没有考 虑到使用动作所涉及的资源及其它数字要求 这种状况只是一种理想状 态 它的实际应用能力也是很有限的 因此扩展上述定义 丰富动作和 状态的表达能力是目标概率规划中很重要的任务 考虑到上面的提到的 问题 一个概率规划域包含的内容应该是 f 1 状态集合 2 初始状态上的概率分布 3 带有奖励值的目标集 带有代价能影响随机状态转换的算子集合 5 表示规划成功的合理的阈值t 寻找规划就是寻找一个动作序列使这个动作序列的在达到所有目标 的情况下 效用值达到阈值 在这早我们还需要定义一个效用函数 对于效用函数的定义我们会在下文提到 因此m 中的a 应该是一个函数 a e a s s a s 表示在s 下执行动作a 的代价 g g 和一个实数相对应 g 专r 表 示奖励值 概率规划的这两个定义看起来很类似第一个定义中计算的阈值是规 划到达目标的可能性 而第二个定义中的阈值表示到达目标的期望效用 值 这是这两种规划的根本区别 严格来说上面的方法仅是对经典规划的扩展 目前还有一方面的工 作是在用上述方法表述动作和初始状态的情况下 完全放弃了经典规划 模型研究控制模型 特别是运用m d p 程作为一种代替方法来考虑规划语 义 这种方法和上述概率规划定义最大的区别是 它不是寻找一组确定 的目标 求得达到这个目标集的概率 而是把目标定义为一个效用值 即寻找一个规划达到这个效用值 在这种情况下 只要规划的效用值足 够大 已知的目标集可以是部分满足的 本文在第三章提到的规划类似 于这种 情况 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 i c c o n d i t i o n a l p l a n 它产生的规划包括条件规划的 全序规划 第三类是相对于全序规划的部分有序规划 p a r t i a lo r d e r e d p l a n 它和全序规划不同的是它的动作序列不必是一个精确的序列 动 作的序列是一个相对的序列 最后一类是有环规j f 1 0 0 pp l a n 它产生具 有重复规划步的非循环规划 这类的规划也被称为规划图或策略图l 概率规划算法中最成功的是在完全可观察 f u l lo b s e r v a t i o n 的假 设下的算法 在这种方法中 尽管不确定性阻碍了主体在时间步之前预 测运行时间状态 主体还能掌握运行时间完全 准确的信息 另外 研 究人员也采用了部分可观察 p a r t i a lo b s e r v a t i o n 的模型处理a i 规划问 题 但是它的复杂性显然受这种工作的应用程序所限制 但这些困难并 没有阻止人们对部分可观察问题的热衷 这是由于部分可观察的这个假 设使规划更具有现实意义 是使规划问题走出实验室的一个很重要的方 面 因此它已经成为规划界研究的热点问题 但是由于加入决策理论已 经使规划图变得比较复杂 如果再进一步考虑部分可观察问题会使问题 变得复杂而不可解 所以本文没有涉及到部分可观察 而一个完全可观 察的算法 在未来的工作中 希望能把工作扩展到部分可观察情况下 1 2 概率规划 p r o b a b i l i s t i cp l a n n i n g 和不确定规划 p l a n n i n gu n d e ru n c e r t a i n t y 本文主要介绍概率规划算法 但是概率规划和不确定规划的关系还 是值得我们去研究一下的 这对于理解概率规划的重要性以及概率规划 在不确定规划中所起的作用是很重要的 由于在实际世界中 我们缺少对知识描述的完整性 精确性 问题 领域存在很多不确定的因素 所以实现经典规划的适用范围有限 真正 能用于应用的是不确定规划 在不确定规划中我们一般用动作和状态表 示世界知识的不确定性 一般情况下 动作分为概率化动作和非概率化动作 对于概率化动 作 我们上面已经提到过 一个状态上动作的输出是一个到达下一状态 的概率分布 一个非概率化动作根据动作一般是条件化的 c o n d i t i o n a l 的 前提条件的不同可能有多个可能输出 这时 给定执行时的动作的 前提条件 动作的结果是确定的 但是主体可能不知道动作执行时的前 提条件 因此也不知道动作的结果 这样 不确定就表示为一个可能状 态输入 输出的列表对 而不是到下一输出的概率分布 我们用一个简单的例子来区分概率化动作和非概率化动作 积木世 界中的概率动作m o v e a b c 即从积木b 上移动积木a 放到积木c 上 成功的概率为0 8 5 放到桌子上的概率为o 1 0 什么也没发生的概率为 0 0 5 一个非概率化的相同的动作可能会这样定义 如果机器人的手臂 是空的且是干的 动作就会成功 如果手臂是空的却沾到水了 积木就 会掉到桌予上 如果手臂不起作用 什么都不会发生 概率规划从某种意义上讲是主体关于域的知识的函数 一个动作可 能输出的概率分布在菜种意义上是对域知识比较好的替代晶 在积木世 界中 当机器人手臂上沾有水时 主体可能不知道m o v e 动作失败 但 经验允许主体估计那个动作输出的概率分布 或者 更深一步讲 主体 知道什么时候机器人手臂上会沾到水 动作通常会失败 但也有o 0 5 的 可能性会成功 如果主体不知道为什么有时动作会成功 主体仍会在动 作执行时加上一个概率分布 并且规划也用到这个概率分布 由此状态表示也有概率化和非概率化之分 这一般和动作相对应 如果动作是概率化的 通常状态的表示也是概率化 否则不是 特别是 初始状态我们有两种表示方法 一种是根据经验估计初始状态的概率口 寻找规划时这种表示可能性的概率值加入到规划的值计算中 另一种是 所有可能状态并存 寻找一种规划满足所有可能的初始状态 7 不确定规划中 我们经常区分条件规划 c o n d i t i o n a lp l a n n i n g 和相 应规划 c o n t i n g e n tp l a n n i n g 在条件规划中 动作的执行 e x e c u t i o n 和结果 e f f e c t s 并不是根据先前一步的动作而定 动作集是条件动作集 在相应规划中 动作的结果和执行都由先前执行的动作决定 这样 在 相应规划中 主体可能会进行观察 并且根据这些观察建立规划分支 如果不具备观察动作相应的环境和条件 主体可能仅能执行一个直线规 划 一个简单的非相应的动作序列 这样一个规划也可被称为 丌放 循环 o p e n l o o p 和根据运行时间的观察选择条件动作的 封闭循环 c l o s e d l o o p 的规划相对应 这两个区别 条件规划v 相应规划和非概率规划v s 非概率规划 可以使不确定规划器进行下面的分类 1 具有非概率化动作的条件规划 这种类型的规划器出现在一致 规划 c o n f o r m a n tp l a n n i n g 中 即产生一个直线规划并保证无论遇见什 么情况规划都能成功 如 c o n f o r m a n t g r a p h p l a n 1 2 具有非概率化动作的相应规划 感知允许这类规划器产生一个 相应规划 但缺少概率动作意味着规划器必须寻找一个在所有环境下都 成功的规划 如c n l p 9 1 s e n s o r yg r a p h p l a n i s c a s s a n d r a u o l 3 带有概率动作的条件规划 和第一种情况一样 这类规划器也 出现在一致规划中 但是动作输出附加的概率允许规划器说明直线规划 具有成功的最高概率 即使是这个概率值小于1 0 如b u r i d a n i u d t p o p 1 1 j m a x p l a n 4 带有概率动作的相应规划 和第二种情况一样 感知允许这类 规划器产生相应规划 也像第三种情况那样 概率动作允许规划器说明 规划具有成功的最高概率值 如 c b u r i d a n j d t p o p m a h 肿m 1 5 和s p u d d 1 6 l 我们第三单讲的规划器也是属于这种类型 的规划器 我们注意到 第二和第三种情况包含第一种情况 第四种情况包含 其它所有的情况 这样表述第四种事例的规划器能用在所有的情况中 而我们所谓的概率规划是第三和第四神规划 因此 概率规划是不确定 规划的 部分 而且是主要的那部分 原因是 1 状态和动作概率分 布是根据经验的估计值 具有可信任性 2 这种方法使问题的描述更 加直接 3 而且这种方法中 成功的概率并非唯一所要考虑的问题 另外规划长度最短 效用值 如果效用函数给目标状态都赋予以一个数 字值 就可以提供对某一方面的衡量 等也是所要考虑的问题 1 3 概率规划复杂度 关于概率规划的复杂度问题已经有很多人研究 特别是 1n 对概率规 划进行了系统而完整的研究 本文中对概率规划的复杂度的分析主要是 来自这篇文章的观点 概率规划的复杂度分析实际上包含两部分的内容 规划评估 p l a ne v a l u a t i o n 和规划存在 p l a n e x i s t e n c e 规划评估是指 规划的效用值是否能超过给定的阈值 即假设一个域m 规划p 的大4 为吲 m 阈值为e 规划的值是否大于0 即是否 p r 锕r e a c h e sag o a ls t a t eu n d e rp e 而规划存在指在给定的界限内 是否存在规划并且这个规划的效用 值大于给定阈值 即设一个域m 闽值为0 大小的界限是z m 是否 存在一个规划 它的大小z 的值大于0 但是有些算法中 规划存在的 计算存在于规划评估中 但这仅是一种特殊情况 一般来说 这种情况 规划的复杂度等于规划评估的复杂度 1 3 1 复杂类的介绍 在复杂类中 p 类问题是指多项式时间可判定的语言类 n p 是指多 项目式时间可验证的语言类 3 在复杂度发展的过程中 由于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 n p c o n p 类问题和n p 类问题是相对应的 n p 是指多项式时间可验证 为正确的语言类 而c o n p 是指多项式时间可验证为错误的语言类 p s p a c e 类是指空间复杂度中和p 类相对应的类 是指多项式空间可 判定的类 显然p c p s p a c e 因为运行的快的机器不可能消耗大量的空 间 更精确地说 对于t n n 任何在时间t n 内运行的机器最多能 消耗t e 1 的空间 因为机器在每个计算步上最多能访问一个新单元 类 似地 n p 至p s p a c e e x p 类问题是指指数时间或指数空间可解的问题 事实上 它基本 等于不可解问题 很多这类中的问题都是加上某些限定 使之转化成多 项式级的问题才能有效求解 l 类是对数时间可判定的语言类 p l p r o b a b i l i s t l cl o g s p a c e 概率对数空间 是指对于集合a 类 存在 个非确定对数有限空间自动 机n 当且仅当n 关于x 可接受的路径大于拒决的路径时 x a 在p l 的原始定义中 没有关于复杂度的时间限制 文 1 8 证明了p l e p 1 9 证明了任意一个概率对数空间可解的问题在p l 机具有同步多项式时间 界限的概率对数空间也是可解的 和p 完全问题明显不同的是 p i 中的 集合用于判定并行计算的复杂度 概率多项式时间 p p 的定义和上面 类似 m a j s a t 就是一个p p 完全问题 对于复杂类c 和c 类c 由类c 图灵可归约到c 的集合组成 即 c 中所限定的资源接受的集合 用c 中的某些问题作为带有即时输出的 予程序 如果c e p s p a c e 那么n p p s p a c e 因此n p p s p a c e n 旷 7 1 是指在带有指数级查询 每一个查询在查询列表下多项式时 间可计算 的多项式时间析取可归约下的p p 的闭包 简单来说n p p p 是概 率多项式时间可验证的问题 总之 问题是所涉及的复杂类的关系是这样的 l p l 量 n p p p 互n p p p p p 至p s p a c e e c o n p c o n p x p 1 3 2 各类概率规划的复杂度 由于状态的表示方法不同 算法的复杂度计算方法也不同 所以规 划域中的算法对于单调域 f l a td 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 由于无限制的 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 这两种 类型的规划评估存在于判定规划存在中 所以它的值为空 对于部分有序规划 我们根据值函数 把这种规划分成三类 最优 o p t i m i s t i c 表示值函数最大的 最差 p e s s i m i s t i c 表示值函数最小的 2 平均的 a v e r a g e 表示取值函数的平均值 这三种情况f 求解规划的方 式并不相同 所以在复杂度计算时我们把它们看成是三类问题 从表中我们看到单调域和复杂度要比命题域的复杂度级别要低 这 和我们前面所提到的 用命题方式会简化问题相矛盾 事实上是用命题 表示方法可以用少量的命题表达多个状态 这样针对同一个问题 他们 处理的问题的规模不同 因此针对具体问题来说 命题的表示方法还是 要简单一些 但也不完全 由表中我们也可以得知 在平均值解释下的 部分有序规划的复杂度在两种域下都是一样的 但最优值和最差值的部 分有序规划命题表示方法都比单调表示方法的复杂度要高 表1 单调表示方法的复杂度 p l a n t y p e p l a ne v a l u a t i o np l a ne x i s t e n c e u o r e s t r i c t e d 1 p c o m p l e t e p o l y n o m i a l d e p t h p c o m p l e t e l o o p i n gp l c o m p l e t e n p c o m p l e t e a c y c l i cp l c o m p l e t e n p c o m p l e t e t o t a l l yo r d e r e dp l c o m p l e t e n p c o m p l e t e p a r t i a l l yo r d e r e d o p t i m i s t i c n p c o m p l e t en p c o m p l e t e p a r t i a l l yo r d e r e d a v e r a g ep p c o m p l e t e n p c o m p l e t e p a r t i a l l yo r d e r e d p e s s i m i s t i cc o n p c o m p l e t e n p c o m p l e t e 表2 命题表示方法的复杂度 p l a nt y p ep l a ne v a l u a t i o n p l a ne x i s t e n c e u n l e s t r i c t e d e x p c o m p l e t e p o l y n o m i a l d e p t h p s p a c e c o m p l e t e l o o p i n g p s p a c e c o m p l e t ep s p a c e c o m p l e t e a c y c l i c p p c o m p l e r en p 9 p c o m p l e t e t o t a l l yo r d e r e d p l c o m p l e t en p p 9 c o m p l e t e p a r t i a l l yo r d e r e d o p t i m i s t i c p p c o m p l e t en p p p c o m p l e t e p a r t i a l l yo r d e r e d a v e r a g en p p v c o m p l e t e n p 9 9 c o m p l e t e p a r t i a l l yo r d e r e d p e s s i m i s t i c c o n p 9 9 c o m p l e t en p p p c o m p l e t e 1 4 概率规划语言 规划语言作用是对规划域的描述 定义规划的输入输出格式 另外 规划语言提供了规划的表达标准 使域模型能够共享 促进了规划域向 现实应用的发展 规划语言主要有p d d l t h ep l a n n i n g d o m a i nd e f i n i t i o n l a n g u a g e 2 53 9 4 0 1 a d l i 3 矾 r p l r e a e t i v ep 1 a nl a n g u a g e d d l 因为p d d l 强大的表达能力和适用范围 从第一届智能规划与调度竞赛 p d d l 就作为竞赛用语言 p d d l 已逐渐成为规划域的标准语言 概率规划语言是对规划语言的进一步扩充 服务于概率规划的语言 因为语言往往是对具体问题来定义的 一般不具有共性 这里我们介绍 共性较强的概率规划语言 1 4 1 概率化的p d d l p p d d l 概率规划语言有很多种 扩展p d d l 2 1 2 5 1 为p p d d l 2 6 1 使之能适 用于m d p 域模型下的概率规划 是比较正式的一种 也是主要研究机构 承认的一种 也是i p c 一4 中采用的概率规划语言 4 7 1 1 4 1 1 概率化结果 因为m d p 域模型中动作具有概率化结果 我们采用一个随机的动作模 型 它是对要素概率s t r i p s 算子的改变 一个随机动作a 有一个前提 条件中和一个结果集c c 1 i c 每一个结果c i 有一个触发条件中i 和 一个结果列表s p e 鼻 p e 其中e 是一个文字集并且 p 1 o 1 是和第j 个结果集相连的概率 且蒜 p 1 和触发条件一 致的互斥结果具有可交换的结果 随机动作的前提条件就是要素 f a c t o r 触发条件 因此如果动作的 前提条件不存在 那么这个动作也就没有执行效果 我们扩展p d d l 语法来定义随机动作并且其动作结果有概率值 图2 给出了概率结果的扩展 标志 p r o b a b i l i s t i c e f f e c t s 用来支持 1 4 动作的概率效果 根据上面的介绍 语法和动作的表示是相一致的 一个动作效果列 表定义如下 p r o b a b i l i s t i c p e p e 如果触发条件研 护 p 很重要 效果就表示为条件效果 表示方法如下 w h e n 西f p r o b a b i l i s t i c e p e e f f e c t c a n d c o n d i t i o n a l e f f e c t g f o r a l l c o n d i t i o n a l e f f e c t s w h e n d e f f e c t p r o b a b i l i s t i c e f f e c t s c p r o b a b i l i s 七i c d e f f e c t 2 f a n d d e f f e c t n o t d e f f e c t f l u e n t s f e x p a n yr a t i o n a l n u m b e ri nt h e i n t e r v a l 0 j1 图2p d d l 对概率结果的扩展 我们举例说明一个动作效果列表 描述如下 p r o b a b i l i s t i c0 9 a n d c l e a r x 0 1 a n d 5 概率值相加为1 a n d 表示空效果状态 数字结果可以和概率结果相结合 这样可能导致无限状态空间的上 随机过程 补救的办法是引入一个界限整型量 i n t e g e r l o wh i g h 除标 准的p d d l 类型 数字值要用函数表示 这用一种非常直接的方式保证了 有限状态空间 如 f u n c t i o n s p o w e