基于互斥约束的概率规划器及其扩展算法的研究与实现

论文摘要

智能规划是人工智能研究领域近年来发展起来的一个热门分支,由于其广泛的实用性,受到研究者的高度重视。尤其是具有不完全信息和不确定信息的规划问题已经成为智能规划中的研究重点。在各种研究方法中,由于概率方法能较准确地对不确定信息进行定量描述,因此研究动作具有概率输出的概率规划方法体现了较强的优越性,这个方法得到了研究者的肯定,并在此基础上产生了大量的算法。在 2004 年举行的 IPC-4（2004 International Planning Competition）,第一次把概率域列入了竞赛的项目,再一次表明了概率规划在智能规划研究领域中的重要地位。 智能规划领域的研究者针对规划问题中的不确定性（uncertainty）问题和不完全信息（incomplete）问题,开发了一些有效的规划器,其中 Blum 与 Langford 提出了专门针对动作结果不确定的规划问题的算法 Probabilistc GraphPlan（简称 PGP）,相关的实验结果表明 PGP 优于解决同类问题的规划器 Buridan,SPI,BlackBox 等。但PGP 算法只局限于处理 STRIPS 动作的概率规划问题,对于动作带有条件效果的概率规划问题,PGP 算法就不适用了。为了扩大 PGP 规划器的处理范围,提出该研究课题。 本文首先从表示方法、规划类型、复杂度、规划语言等几方面分析了概率规划的研究现状,概括了研究概率规划的相关理论和相关技术,并分别介绍了经典规划器与概率规划器中对动作带有条件效果的规划问题的处理方法,其次介绍自己做的主要工作,包括两个部分:（一）研究与实现基于互斥约束的概率规划器,该规划器是对 PGP加以改进,改进后的算法相对于 PGP 规划器减少了规划图中的结点数目,节省了存储空间.（二）提出处理动作带有条件效果的概率规划器的算法。最后阐明了未来继续要做的工作,对第二部分提出算法进行程序实现。

论文目录

• 摘要
• Abstract
• 目录
• 引言
• 第一章 概率规划概述
• 1.1 概率规划
• 1.1.1 状态表示
• 1.1.2 初始世界
• 1.1.3 动作表示
• 1.1.4 概率规划的定义
• 1.1.5 概率规划的类型
• 1.2 概率规划和不确定规划
• 1.3 概率规划复杂度
• 1.3.1 复杂类的介绍
• 1.3.2 各类概率规划的复杂度
• 1.4 概率规划语言
• 1.4.1 概率化的PDDL（PPDDL）
• 1.4.2 其它语言
• 1.5 IPC-4 中关于概率规划的一些问题
• 第二章 图规划框架下的概率规划
• 2.1 图规划算法
• 2.1.1 基本概念
• 2.1.2 有效规划与规划图
• 2.1.3 扩张规划图（extending planning graphs）算法
• 2.1.4 搜索有效规划算法
• 2.2 PGP 算法
• 2.2.1 马尔可夫决策问题（MDP）
• 2.2.2 概率动作在规划图中的表示
• 2.2.3 启发式信息
• 2.2.4 规划图扩张与有效规划解搜索算法
• 第三章 MPGP 算法
• 3.1 算法背景
• 3.2 算法分析
• 3.3 命题互斥
• 3.4 规划图的扩张算法
• 3.5 搜索有效规划
• 3.6 例子和实验结果
• 3.6.1 概率积木世界
• 3.6.2 护城河和城堡问题
• 3.6.3 实验结果总结及后续的研究方向
• 第四章 MCPGP
• 4.1 条件效果
• 4.2 处理方法
• 4.2.1 完全扩展法
• 4.2.2 要素扩展法
• 2方法'>4.2.3 IP²方法
• 4.3 MCPGP 中的条件效果
• 4.3.1 动作模式
• 4.3.2 动作在规划图中的表示
• 4.3.3 MCPGP 中的命题互斥
• 4.3.4 MCPGP 的图扩张算法
• 4.3.5 搜索有效规划
• 4.3.6 总结及后续工作
• 总结
• 参考文献
• 附录 A 第一届规划调度系统比赛
• 附录 B 第二届规划调度系统比赛
• 附录 C 第三届规划调度系统比赛
• 附录 D 主要概率规划器一览表
• 致谢
• 在学期间公开发表论文及著作情况