图规划框架下的决策概率规划的研究与实现

摘要

智能规划是人工智能研究领域近年来发展起来的一个热门分支,由于其广泛的实用性,受到研究者的高度重视.尤其是具有不完全信息和不确定信息的规划问题已经成为智能规划中的研究重点.在各种研究方法中,由于概率方法能较准确地对不确定信息定量描述,因此研究动作具有概率输出的概率规划方法体现了较强的优越性,这个方法得到了研究者的肯定,并在此基础上产生了大量的算法.又由于这种概率规划的研究方法和马尔可夫决策过程(Markov decision processes,MDPs)的研究方法相似,所以很多研究人员在两者之间的结合上做了大量的工作.在今年举行的IPC-4(2004 International Planning Competition),第一次把概率域列入了竞赛的项目,再一次表明了概率规划在智能规划研究领域中的重要地位.该文首先从表示方法、规划类型、复杂度、规划语言等几方面分析了概率规划的研究现状,概括了研究概率规划的相关理论和相关技术,揭示了概率规划和MDPs之间的关系,并把决策理论应用到概率规划中,定义了效用模型下的概率规划,提出了相应的算法DPG(Decision Probabilistic Graphplan).DPG算法建立在具有迅速传播能力的概率规划图(Probabilistic Graphplan)上,结合动态编程(Dynamic Programming),用前向搜索的方法来求最优规划解.我们用C语言实现了这个算法,并证明出,在有限时间步内,这是一个多项式级复杂度的算法.通过实验结果,我们阐明了效用模型下,各因素对最优规划解及DPG算法复杂度的影响.最后指明了该算法是对概率规划的有效扩张及对MDPs的成功应用.

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

引言

第一章概率规划概述

1.1概率规划

1.1.1状态表示

1.1.2初始世界

1.1.3动作表示

1.1.4概率规划的定义

1.1.5概率规划的类型

1.2概率规划(Probabilistic planning)和不确定规划(planning under uncertainty)

1.3概率规划复杂度

1.3.1复杂类的介绍

1.3.2各类概率规划的复杂度

1.4概率规划语言

1.4.1概率化的PDDL(PPDDL)

1.4.2其它语言

1.5IPC-4中关于概率规划的一些问题

第二章马尔可夫决策过程(MDP)

2.1问题定义

2.2观察(observation)

2.3奖励和值

2.4界限和成功标准

2.5概率规划和马尔可夫决策问题

第三章DPG算法

3.1算法背景

3.2定义与表示

3.2.1命题、状态和目标集

3.2.2动作和动作序列

3.3算法描述

3.3.1规划图的扩张

3.3.2规划解的生成

3.3.3效用值的计算

3.4算法复杂度

3.5例子和实验结果

3.5.1概率积木世界

3.5.2护城河和城堡问题

3.5.3实验结果总结

第四章总结及后续工作

附录A 第一届规划调度系统比赛

附录B 第二届规划调度系统比赛

附录C 第三届规划调度系统比赛

附录D 主要概率规划器一览表

参考文献

致谢