POMDP近似算法的研究与设计

发布时间：2017-12-26 08:40

  本文关键词：POMDP近似算法的研究与设计　出处：《中国科学技术大学》2017年硕士论文　论文类型：学位论文

  更多相关文章： POMDP 基于点的值迭代 启发式搜索值迭代 可达空间

【摘要】：部分可观测马尔科夫决策过程(Partially Observable Markov Decision Process,POMDP)是处理不确定条件下决策问题的一个通用框架,它在机器人控制,口语系统,医疗诊断等领域都有很大的应用前景。但是由于POMDP问题的历史灾难和纬度灾难性质,精确求解算法是NP难问题,这就大大限制了其在实际中的应用。近年来,近似算法,特别是基于点的近似算法在POMDP策略求解上取得了很大的进步。基于点的算法只考虑初始信念点的可达空间,在可达空间的采样点上进行值迭代,不同算法之间的区别主要在于采样方法和迭代策略。其代表性的算法有基于点的值迭代(PBVI),前向搜索值迭代(FSVI)和启发式搜索值迭代(HSVI),它们通常能够得到最优或近似最优的策略。另一类重要的近似算法是基于迭代函数的近似,如基于MDP的近似(QMDP),快速告知边界法(FIB),它们得到的是精确值函数的上下界。这类算法通常简单快速,能够处理规模较大的问题,但是对产生策略的质量没有保证。为了在较短的时间内得到一个良好的下界,本文提出了相关状态提升法(RSU),它的主要思想是用对信念点相关状态的提升去近似对信念点的提升,同时借助内在的MDP探索最优策略下的可达状态空间,然后在得到的状态空间中利用近似值迭代和状态转移树的拓扑结构来加速迭代的进程。利用得到的上下界,本文给出了一个改进的基于点的算法--多路启发式搜索值迭代(MHSVI),依据可能的最优值函数产生信念点路径,对路径可能达到的值进行评估,并依据评估值对路径进行剪枝,使得值函数能够快速地收敛。本文在几个代表性问题上对提出的算法和已有算法进行了实验,实验结果证明了 RSU和MHSVI的有效性。
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6;O225

【相似文献】

相关期刊论文 前10条

1 冯定谟;在物理教学中培养学生运用近似算法的一些体会[J];物理通报;1957年02期

2 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

3 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

4 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

5 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

6 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

7 苏纯洁;带服务器的三台平行机排序问题的复杂性和近似算法[J];应用数学学报;2003年03期

8 刘光聪;朱大铭;姜海涛;;有向基因组反转和转位排序最小权重问题的1.5k近似算法[J];小型微型计算机系统;2010年07期

9 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

10 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

相关会议论文 前9条

1 刘声田;朱大铭;;基因序列翻转排序的一种近似算法[A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一）[C];2005年

2 梅生伟;洪奕光;秦化淑;翁绍鹏;;非线性H_∞控制的粘性解及其近似算法[A];1996年中国控制会议论文集[C];1996年

3 田世俊;李建;朱洪;;多需求目标的UFL问题及其近似算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

5 保利勇;赵东风;丁洪伟;;双服务器异步控制策略轮询系统性能的近似算法分析[A];2009年中国高校通信类院系学术研讨会论文集[C];2009年

6 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

7 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];上海市制冷学会一九九七年学术年会论文集[C];1997年

8 李灏;张春路;丁国良;;对多层墙体反应系数的一种近似算法的讨论[A];全国暖通空调制冷1998年学术年会论文集（2）[C];1998年

9 周露;吴瑶华;黄文虎;闻新;;一种推广卡尔曼滤波的近似算法[A];1995中国控制与决策学术年会论文集[C];1995年

相关重要报纸文章 前1条

1 PALADIN;近似算法[N];电脑报;2003年

相关博士学位论文 前5条

1 杨朝霞;超图嵌入圈问题的近似算法[D];山东大学;2010年

2 潘锐;设施选址与K-中间点问题的复杂性与近似算法[D];山东大学;2007年

3 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

4 柳楠;基因组片段填充问题的算法研究[D];山东大学;2013年

5 姜海涛;基因组比较算法研究[D];山东大学;2011年

相关硕士学位论文 前10条

1 陈崇琛;多色点集直线划分的复杂性及其近似算法[D];复旦大学;2014年

2 王敏;基于图特征的介度中心近似算法研究[D];曲阜师范大学;2015年

3 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

4 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

5 朱婷婷;具有不同释放时间的单机重新排序问题的近似算法[D];兰州大学;2016年

6 王克红;均匀限制NP-完备间题及其近似算法设计[D];云南大学;2016年

7 肖文英;限制版本瓶颈斯坦纳树问题算法研究[D];中南民族大学;2015年

8 申子慧;广义多乘积规划问题的近似算法[D];河南师范大学;2016年

9 黄小曼;差异分批模式下供应链调度的近似算法设计与分析[D];合肥工业大学;2017年

10 刘冰冰;POMDP近似算法的研究与设计[D];中国科学技术大学;2017年

，

本文编号：1336595