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

摘要

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

目录

声明

摘要

引言

第一章 可能性决策图

1．1 决策图简介

1．1．1 二元决策图

1．1．2 有序二元决策图

1．1．3 二元决策图的应用

1．2 可能性理论

1．3 可能性决策图提出的意义

1．4 可能性决策图

1．4．1 可能性决策图定义

1．4．2 简化的可能性决策图

1．4．3 可能性决策图上的操作

第二章 可能性规划介绍

2．1 可能性规划

2．2 马尔可夫决策过程

2．3 基于可能性理论的定性决策理论

2．3．1 隶属函数

2．3．2 可能性测度

2．4 可能性规划介绍

2．5 可能性马尔可夫决策过程

第三章 基于可能性决策图的可能性规划

3．1 可能性规划例子

3．2 用可能性决策图表示可能性规划问题

3．3 用可能性决策图表示可能性值迭代

3．4 算法的优化

3．5 数据和结果

结论

总结与展望

参考文献

致谢

在学期间公开发表论文及著作情况