带有并行动作的概率规划算法的研究

论文摘要

智能规划已经成为人工智能的研究热点,尤其是基于概率方法的不确定规划算法的研究。概率方法定量的刻画了现实世界中的不确定性,更适合于求解现实世界中的规划问题,从而得到很多学者的关注。基于Graphplan算法的PGraphplan是概率规划中较优秀的一款规划器。PGraphplan在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许执行一个非空动作”的假设下求得的,这个假设的存在使得在规划图中无法使用互斥信息,找到的规划解相对冗长,并且比较浪费求解时间。PGraphplan的后续发展算法也都没有打破这个限制。本文针对概率规划中存在的这一问题,提出了新的概率规划算法PPGraphplan。我们通过定义并行动作集以及节点间互斥的概念,实现了在概率规划算法中处理并行动作,打破了原有概率规划算法中“每个时间步只允许执行一个非空动作”的限制,弥补了原有算法的不足。PPGraphplan算法在规划图扩展阶段标记节点间的互斥信息,有效利用规划图的特性,提高了规划器的求解质量;同时在有效规划提取阶段利用动态规划算法计算每个动作到达目标状态的最大成功概率,从而找到成功概率较大的最短规划解因此,该算法更适合于求解现实世界中的规划问题。本文在给出算法的基础上,利用C语言对该算法进行了实现,设计了可以处理并行动作的概率规划系统PPGraphplan。实验证明该系统可以达到理论预期的效果,实现了概率规划算法中动作的并行执行,可以找到长度最短的规划解,提高了概率规划器的求解质量,使得概率规划更适合于处理现实世界问题。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题研究背景
• 1.2 本文主要工作及意义
• 第二章 智能规划
• 2.1 智能规划概念
• 2.2 智能规划的应用
• 2.2.1 航空航天领域中的应用
• 2.2.2 机器人领域中的应用
• 2.2.3 智能工厂中的应用
• 2.2.4 商业中的应用
• 2.3 智能规划的发展
• 2.4 规划问题表示
• 2.4.1 STRIPS
• 2.4.2 ADL
• 2.4.3 PDDL
• 第三章 概率规划
• 3.1 概率规划器的发展
• 3.2 概率规划
• 3.2.1 概率规划表示
• 3.2.2 概率规划的定义
• 3.2.3 概率规划的类型
• 3.3 概率规划和不确定规划
• 3.4 概率规划语言
• 3.4.1 概率化的结果
• 3.4.2 奖励和目标
• 第四章 图规划框架下的概率规划
• 4.1 图规划
• 4.1.1 基本概念
• 4.1.2 规划图扩张算法
• 4.1.3 有效规划提取算法
• 4.2 PGRAPHPLAN 算法
• 4.2.1 马尔可夫决策问题（MDP）
• 4.2.2 概率规划在图规划框架下的表示
• 4.2.3 启发值信息
• 4.2.4 规划图扩张及有效规划提取算法
• 4.2.5 概率规划实例
• 第五章 PPGRAPHPLAN 算法及规划器的设计与实现
• 5.1 算法背景
• 5.1.1 PGraphplan 算法分析
• 5.1.2 PGraphplan 的发展
• 5.1.3 PPGraphplan 算法的提出
• 5.2 PPGRAPHPLAN 算法
• 5.2.1 基本概念
• 5.2.2 规划图扩张算法
• 5.2.3 有效规划提取算法
• 5.3 规划器的设计与实现
• 5.3.1 系统功能设计
• 5.3.2 系统工作流程
• 5.3.3 例子及实验结果
• 结论
• 参考文献
• 致谢
• 在学期间公开发表论文及著作情况