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

对象集合动态可变的概率规划算法的研究与实现

作　者: 吴爽
导　师: 谷文祥
学　校: 东北师范大学
专　业: 计算机软件与理论
关键词: CDOPGP 动态规划图的分支分支概率 CDOPGP的规划解
分类号: TP18
类　型: 硕士论文
年　份: 2008年
下　载: 23次
引　用: 0次
阅　读: 论文下载

内容摘要

智能规划已经成为人工智能研究的热点,尤其是基于概率方法的不确定规划算法和对可创建删除对象规划算法的研究。概率方法定量的刻画了现实世界中的不确定性,更适合于求解现实世界中的规划问题,从而得到很多学者的关注。基于Graphplan算法的PGraphplan是概率规划中较优秀的一个规划器。PGraphplan在图规划框架下利用动态规划算法找到随机规划解。但规划解是在“每个时间步只允许执行一个非空动作”的假设下求得的,这使得它并没有Graphplan那样的高效。在规划中,对象的增减是大量存在的,因此,可创建删除对象规划的研究更加符合现实世界的环境与状态,更适合于求解现实世界的问题。2005年问世的规划器CDOGP,是一个较好的基于Graphplan的规划器,它提出了对象命题化的思想,使对象统一成命题来看待,使对象集合动态可变的规划更容易求解了。但是,在现实世界中,一般操作尚有动作效果的不确定性,更别说具有创建删除对象效果的操作了。CDO操作的复杂程度在算法中并没有被表现出来。本文针对以上两个算法存在的问题,提出了新的规划算法CDOPGP,即对象集合动态可变的概率规划算法。我们引入了动态规划图的分支以及分支概率的概念,基于这些概念通过对搜索中出现目标命题的分支的排列组合,实现了对象集合动态可变的概率规划问题中动作的并行执行;并且重新定义了命题、动作以及对象间互斥的概念,使其在本算法中发挥了应有的作用,提高了算法的效率;另外,本文把CDOP操作引入到概率规划中来,成功地用概率来表示了创建删除对象操作的复杂性,使概率规划算法能成功地处理一部分的可创建删除规划问题。最后,本文在给出算法的基础上,利用C语言对该算法进行了实现,设计了可以处理并行动作的对象集合动态可变的概率规划系统CDOPGP。实验证明该系统可以达到理论预期的效果,实现了动作的并行执行,可以找到概率最大的规划解,提高了概率规划器的效率,使得概率规划更适合于处理现实世界问题。新的算法更适合于解决现实世界中的规划问题,具有较高的理论研究价值。同时,CDOPGP规划器的开发,进一步拓宽了概率规划的应用领域,推动了概率规划在实际应用方面的发展。

全文目录

摘要  4-5
Abstract  5-8
第一章引言  8-11
  1.1 课题研究背景  8-9
  1.2 本文主要工作及意义  9-10
  1.3 本文结构  10-11
第二章智能规划  11-19
  2.1 智能规划的基本概念  11-12
  2.2 智能规划的发展  12-13
  2.3 规划问题的描述  13-15
    2.3.1 STRIPS 表示  14
    2.3.2 动作描述语言ADL  14-15
    2.3.3 规划域定义语言 PDDL  15
  2.4 图规划（GRAPHPLAN）  15-19
    2.4.1 基本概念  15-17
    2.4.2 规划图扩张算法  17-18
    2.4.3 有效规划提取算法  18-19
第三章概率规划  19-31
  3.1 不确定规划  19-20
  3.2 概率规划  20-23
    3.2.1 概率规划器  20
    3.2.2 概率规划的定义  20-21
    3.2.3 概率规划的类型  21-22
    3.2.4 概率规划表示  22-23
  3.3 概率规划语言  23-25
    3.3.1 概率化的结果  23-24
    3.3.2 奖励和目标  24-25
  3.4 PGRAPHPLAN 算法  25-31
    3.4.1 马尔可夫决策问题（MDP）  26
    3.4.2 概率规划在图规划框架下的表示  26-27
    3.4.3 规划图扩张及有效规划提取算法  27-28
    3.4.4 概率规划的一个实例  28-31
第四章可创建删除对象规划  31-36
  4.1 创建/删除对象规划问题的提出  31-32
  4.2 创建/删除对象规划问题  32-36
    4.2.1 基本概念  32-34
    4.2.2 创建/删除规划问题描述  34
    4.2.3 CDOGP 的规划图生成算法  34-35
    4.2.4 CDOGP 的有效规划的搜索算法  35-36
第五章 CDOPGP 算法及规划器的设计与实现  36-45
  5.1 算法研究背景  36
  5.2 基本定义与符号  36-39
    5.2.1 规划与规划问题  36-37
    5.2.2 动作与no-op 动作  37-38
    5.2.3 对象命题化  38
    5.2.4 互斥的定义  38-39
    5.2.5 算法的其它相关定义  39
  5.3 对象集合动态可变的概率规划（CDOPGP）算法  39-41
    5.3.1 问题描述  39
    5.3.2 CDOPGP 算法  39-41
  5.4 概率规划器的设计与实现  41-45
    5.4.1 系统功能设计  41
    5.4.2 系统工作流程  41-42
    5.4.3 实验用例及结果  42-45
结论  45-46
参考文献  46-49
致谢  49-50
在校期间公开发表论文及著作情况  50
参加项目情况  50

对象集合动态可变的概率规划算法的研究与实现

内容摘要

全文目录

相似论文