学位论文 > 优秀研究生学位论文题录展示

基于可能性决策图的可能性规划

作　者: 王乐
导　师: 谷文祥；殷明浩
学　校: 东北师范大学
专　业: 计算机应用技术
关键词: 二元决策图可能性理论可能性决策图 PPUPDDs算法
分类号: TP391.41
类　型: 硕士论文
年　份: 2011年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

早期智能规划研究一直集中在“封闭世界”假设之下的经典规划领域,然而,很多实际问题并不满足这样的假设条件,因此,一些学者将目光投向了不确定性规划的研究,其中概率规划的研究取得了一定的成绩,由于人工智能研究中的不确定性通常是顺序的、定性的,动作效果的概率在实际中往往很难获得,一些研究认为,可能性理论更适合解决那些概率模型无法解决或者概率信息很难获得的问题,提出可能性规划的概念,在可能性规划中,规划的初始世界状态是部分已知的,规划动作的效果按照对最终目标的完成效用被分成各个等级。然而,求解可能性规划的可能性价值迭代算法往往只能高效地求解较小的问题,尤其,伴随着域特征数目的增加状态空间的规模往往呈指数级增长,会陷入Bellman的维度灾难。同时,智能规划的求解方法由最初的用归结定理证明的方法求解规划,扩展为用STRIPS方法求解规划问题,及将规划问题转化为可满足问题来求解和采用模型检测的方法来求解规划问题。其中利用模型检测的方法求解规划取得了很好的成绩,在2000年规划大赛上,基于模型检测的MIPS(The Model Checking Integrated Planning System)规划系统,采用二元决策图(Binary Decision Diagrams)来压缩地表示规划状态,使得规划解的搜索空间得到有效的扩展。本文基于可能性理论和决策图理论提出一种新的决策图:可能性决策图,用于对不确定环境下的不精确的和模糊的信息进行编码,并用定理证明所提出的可能性决策图能规范地表示可能性命题公式,而且定义了可能性决策图上可应用的运算:取MAX运算、取MIN运算和取N运算。并将可能性决策图应用于求解可能性规划问题,提出了新的算法PPUPDDs,来创建最优可能性策略:利用可能性决策图来压缩地表示可能性价值函数和可能性策略,通过可能性决策图表示来捕捉动作和效用函数中的一些规则,去实现可能性价值迭代算法,这使得算法PPUPDDs节省了大量的空间和计算时间。我们在Factory、Moat-Castle、Block三个可能性规划问题域上测试了PPUPDDs算法,都有优异的表现。

全文目录

摘要  4-5
Abstract  5-9
引言  9-12
第一章可能性决策图  12-18
  1.1 决策图简介  12-15
    1.1.1 二元决策图  13-14
    1.1.2 有序二元决策图  14
    1.1.3 二元决策图的应用  14-15
  1.2 可能性理论  15
  1.3 可能性决策图提出的意义  15
  1.4 可能性决策图  15-18
    1.4.1 可能性决策图定义  15-16
    1.4.2 简化的可能性决策图  16-17
    1.4.3 可能性决策图上的操作  17-18
第二章可能性规划介绍  18-25
  2.1 可能性规划  18
  2.2 马尔可夫决策过程  18-19
  2.3 基于可能性理论的定性决策理论  19-22
    2.3.1 隶属函数  19
    2.3.2 可能性测度  19-22
  2.4 可能性规划介绍  22-24
  2.5 可能性马尔可夫决策过程  24-25
第三章基于可能性决策图的可能性规划  25-36
  3.1 可能性规划例子  25-26
  3.2 用可能性决策图表示可能性规划问题  26-27
  3.3 用可能性决策图表示可能性值迭代  27-32
  3.4 算法的优化  32-33
  3.5 数据和结果  33-36
结论  36-37
总结与展望  37-38
参考文献  38-42
致谢  42-43
在学期间公开发表论文及著作情况  43

相似论文

基于时间自动机的模型验证技术,TP301.1
具有交易费用和多种投资限制的模糊投资组合模型的研究,F830.59
摩擦市场下基于可能性理论的投资组合模型研究,F830.59
模糊决策模型在供应链库存管理中的应用,F274
基于BDD的多阶段任务系统可靠性建模分析,TB114.3
求解极小碰集的ROBDD算法的研究与分析,TP181
期待可能性理论在劳动争议中的适用,D912.5
基于BDD的碰集与配置求解,TP311.12
符号化模型检测算法的研究,TP311.52
论期待可能性理论的基础与地位,D924
一种基于基数的领域特征模型检验方法,TP301
基于模块化思想的动态故障树分析方法研究,TP18
多阶段任务系统BDD排序方法研究,TB114.3
二元决策图的排序优化及故障树转化方法的研究,TP311.5
论刑法中的期待可能性,D924.1
论期待可能性之引入,D924
基于Windows Mobile5.0平台的故障树分析软件设计与开发,TP311.52
期待可能性理论解读,D917
基于可能性理论与ANP模型的BOT项目投资机会评价研究,F224
论期待可能性及其立法借鉴,D914