基于部分可观察马尔科夫决策过程的序列规划问题的研究

发布时间：2017-10-07 17:37

  本文关键词：基于部分可观察马尔科夫决策过程的序列规划问题的研究

  更多相关文章： 部分可观测马尔科夫决策过程 基于点的值迭代 策略迭代 启发式在线算法 蒙特卡罗法

【摘要】：智能规划(AI planning)是传统人工智能最重要的研究领域之一。随着问题规模不断增大,复杂程度不断提高,如何在大规模不确定环境下设计出高效智能的决策算法是当前智能规划非常重要的研究课题。由于POMDP能够很好地对环境、动作及观察的不确定性进行建模,因而在不确定性环境下基于POMDP模型来进行规划是目前自动规划研究的重要内容。而在无限视野下精确求解POMDP问题是NP难问题,在过去的十多年里,基于点的POMDP问题启发式求解成为了大规模POMDP问题求解的研究热点。但是在离线求解POMDP问题的研究中,大多数基于点的近似求解方法都是基于单一的启发式标准,难以适用于不同的问题场景；在在线求解POMDP问题的研究中,且近几年的启发式方法都是只以最优上界作为探索标准,降低了收敛效率。本文围绕如何设计高效的启发式POMDP求解算法来展开研究。本文的研究内容主要有三个方面,首先,研究了目前主流的基于点的POMDP近似求解启发式标准,杂合密度分布的标准和值函数的标准设计HHVI算法来提高探索信念点集的质量；其次,研究了基于聚类构造可达信念点集最小覆盖的方法,并设计了基于点的策略迭代算法来求解POMDP司题；最后改进了最优可达信念空间的探索标准,设计了基于概率的最优可达空间近似方法,从而改进了POMDP在线求解的效率。具体来说,论文的主要内容和创新点如下：1. 目前基于点的POMDP离线近似求解启发式标准主要是基于密度分布的标准、基于值函数的标准和基于MDP的标准。但是基于MDP的近似解法没有考虑部分可观察性,会退化为随机策略；单一基于密度标准的算法无法控制探索点集的规模难以保证收敛质量；单一基于值函数的算法复杂度较高难以保证收敛效率。本文提出了杂合的启发式值迭代算法来离线求解POMDP问题,该算法基于值函数启发式标准评价已探索点集内信念点的被扩价值,结合信念点分布和值函数选择合理的后继点,通过杂合值函数和密度的标准避免了单一标准的局限性,增强了对不同POMDP问题的适应性。2.最近的研究说明δ-覆盖数是刻画基于点的POMDP问题求解的有效度量,但精确计算可达信念空间的δ-覆盖数是一个NP-难的问题。本文分析了可达信念空间的聚类特性,基于可达信念空间的分布特征来高效地构造其δ-覆盖,由此获得分散分布于可达信念空间的探索信念点集,通过策略迭代来离线求解POMDP问题。3. 当前的启发式在线算法大多基于最高上界的行动分支搜索探索信念点,从理论上保证算法最终能找到信念点上的最优行动,但上界的收敛较慢,且下界能够保证策略的质量,在线规划算法在执行时以最优下界对应的行动作为决策行动。本文提出了选择最优动作的新标准,以所有动作的函数值在其上界和下界之间的概率分布为基础,计算每个动作的值函数取值最大的概率,再选择概率值最大的动作。算法更准确地探索到最优可达信念空间附近的区域,从而提高在线求解的迭代效率。
【关键词】：部分可观测马尔科夫决策过程 基于点的值迭代 策略迭代 启发式在线算法 蒙特卡罗法
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O225
【目录】：

• 摘要4-6
• abstract6-15
• 第一章 绪论15-21
• 1.1 引言15-16
• 1.2 POMDP问题求解研究现状16-18
• 1.3 目前POMDP求解中存在的问题18-19
• 1.4 本文的主要工作和论文结构19-21
• 第二章 研究背景21-36
• 2.1 规划问题研究的发展21-25
• 2.1.1 经典规划21-24
• 2.1.2 不确定环境中的规划24-25
• 2.2 MDP模型及其求解25-30
• 2.2.1 模型定义26-27
• 2.2.2 策略27-28
• 2.2.3 值函数和值迭代28-30
• 2.3 POMDP模型及其求解30-35
• 2.3.1 模型定义31
• 2.3.2 决策和信念31-32
• 2.3.3 值向量和精确值迭代32-34
• 2.3.4 向量裁剪34-35
• 2.4 本章小结35-36
• 第三章 一种基于杂合标准的POMDP值迭代求解方法36-61
• 3.1 引言36-37
• 3.2 基于点的值迭代方法37-38
• 3.3 主流基于点的信念空间探索方法38-47
• 3.3.1 PBVI算法(基于点的值迭代算法)38-39
• 3.3.2 PEMA算法(基于点的最小误差算法)39-40
• 3.3.3 类MDP的近似解法40-42
• 3.3.4 FSVI算法42
• 3.3.5 HSVI算法42-43
• 3.3.6 SARSOP算法(最优策略可达空间的连续近似法)43-45
• 3.3.7 GapMin算法45-46
• 3.3.8 基于点的值迭代算法的分析46-47
• 3.4 HHVI算法47-51
• 3.4.1 算法思想47-48
• 3.4.2 算法描述48-50
• 3.4.3 算法分析50-51
• 3.5 实验和分析51-59
• 3.5.1 基准问题51-57
• 3.5.2 实验57-59
• 3.6 本章小结59-61
• 第四章 一种基于聚类的POMDP策略迭代求解方法61-78
• 4.1 引言61-62
• 4.2 基于点的策略迭代62-66
• 4.2.1 POMDP的策略迭代求解62-64
• 4.2.2 基于点的策略迭代算法PBPI64-66
• 4.3 可达信念空间聚类特性的分析66-72
• 4.3.1 可达信念空间获取方法66-68
• 4.3.2 可达信念空间聚类分析68-70
• 4.3.3 基于密度的信念点聚类算法70-72
• 4.4 CBPI算法72-75
• 4.4.1 算法思想72-73
• 4.4.2 算法描述73-75
• 4.5 实验和分析75-77
• 4.6 本章小结77-78
• 第五章 一种基于概率最优可达空间迭代的POMDP在线求解方法78-93
• 5.1 引言78-80
• 5.2 在线规划算法概述80-83
• 5.3 最优可达信念空间的求解方法83-85
• 5.3.1 最优可达信念空间83-84
• 5.3.2 基于概率的最优可达空间近似方法84-85
• 5.4 PBORSI算法85-88
• 5.4.1 算法思想85-86
• 5.4.2 算法描述86-88
• 5.5 实验和分析88-92
• 5.6 本章小结92-93
• 第六章 总结与展望93-95
• 6.1 论文总结93-94
• 6.2 下一步的工作94-95
• 致谢95-96
• 参考文献96-104
• 附录104-105

【参考文献】

中国期刊全文数据库 前2条

1 周傲英,周水庚,曹晶,范晔,胡运发;Approaches for Scaling DBSCAN Algorithm to Large Spatial Databases[J];Journal of Computer Science and Technology;2000年06期

2 章宗长;陈小平;;杂合启发式在线POMDP规划[J];软件学报;2013年07期

，

本文编号：989185