發(fā)布時間：2017-12-26 08:40

  本文關鍵詞：POMDP近似算法的研究與設計　出處：《中國科學技術大學》2017年碩士論文　論文類型：學位論文

  更多相關文章： POMDP 基于點的值迭代 啟發(fā)式搜索值迭代 可達空間

【摘要】：部分可觀測馬爾科夫決策過程(Partially Observable Markov Decision Process,POMDP)是處理不確定條件下決策問題的一個通用框架,它在機器人控制,口語系統(tǒng),醫(yī)療診斷等領域都有很大的應用前景。但是由于POMDP問題的歷史災難和緯度災難性質(zhì),精確求解算法是NP難問題,這就大大限制了其在實際中的應用。近年來,近似算法,特別是基于點的近似算法在POMDP策略求解上取得了很大的進步�；邳c的算法只考慮初始信念點的可達空間,在可達空間的采樣點上進行值迭代,不同算法之間的區(qū)別主要在于采樣方法和迭代策略。其代表性的算法有基于點的值迭代(PBVI),前向搜索值迭代(FSVI)和啟發(fā)式搜索值迭代(HSVI),它們通常能夠得到最優(yōu)或近似最優(yōu)的策略。另一類重要的近似算法是基于迭代函數(shù)的近似,如基于MDP的近似(QMDP),快速告知邊界法(FIB),它們得到的是精確值函數(shù)的上下界。這類算法通常簡單快速,能夠處理規(guī)模較大的問題,但是對產(chǎn)生策略的質(zhì)量沒有保證。為了在較短的時間內(nèi)得到一個良好的下界,本文提出了相關狀態(tài)提升法(RSU),它的主要思想是用對信念點相關狀態(tài)的提升去近似對信念點的提升,同時借助內(nèi)在的MDP探索最優(yōu)策略下的可達狀態(tài)空間,然后在得到的狀態(tài)空間中利用近似值迭代和狀態(tài)轉(zhuǎn)移樹的拓撲結(jié)構來加速迭代的進程。利用得到的上下界,本文給出了一個改進的基于點的算法--多路啟發(fā)式搜索值迭代(MHSVI),依據(jù)可能的最優(yōu)值函數(shù)產(chǎn)生信念點路徑,對路徑可能達到的值進行評估,并依據(jù)評估值對路徑進行剪枝,使得值函數(shù)能夠快速地收斂。本文在幾個代表性問題上對提出的算法和已有算法進行了實驗,實驗結(jié)果證明了 RSU和MHSVI的有效性。
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP301.6;O225

【相似文獻】

相關期刊論文 前10條

1 馮定謨;在物理教學中培養(yǎng)學生運用近似算法的一些體會[J];物理通報;1957年02期

2 魏麒;蔣義偉;;一類兩階段雜交流水作業(yè)的近似算法(英文)[J];軟件學報;2012年05期

3 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學的實踐與認識;1983年03期

4 馬紹漢;一類限制樹問題的復雜性及其近似算法[J];山東大學學報(自然科學版);1984年01期

5 楊延齡,戚文發(fā);關于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學學報;1989年01期

6 杜林古;;帶風向投遞員問題的一個多項式1—近似算法[J];山東紡織工學院學報;1992年01期

7 蘇純潔;帶服務器的三臺平行機排序問題的復雜性和近似算法[J];應用數(shù)學學報;2003年03期

8 劉光聰;朱大銘;姜海濤;;有向基因組反轉(zhuǎn)和轉(zhuǎn)位排序最小權重問題的1.5k近似算法[J];小型微型計算機系統(tǒng);2010年07期

9 何勇;帶核集分劃問題的一個線性(1/7)-近似算法[J];高校應用數(shù)學學報A輯(中文版);1997年04期

10 季敏,何勇;帶核集分劃問題的一個改進近似算法[J];系統(tǒng)工程理論與實踐;2003年12期

相關會議論文 前9條

1 劉聲田;朱大銘;;基因序列翻轉(zhuǎn)排序的一種近似算法[A];山東省計算機學會2005年信息技術與信息化研討會論文集（一）[C];2005年

2 梅生偉;洪奕光;秦化淑;翁紹鵬;;非線性H_∞控制的粘性解及其近似算法[A];1996年中國控制會議論文集[C];1996年

3 田世俊;李建;朱洪;;多需求目標的UFL問題及其近似算法[A];2005年全國理論計算機科學學術年會論文集[C];2005年

4 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學者大會論文集[C];2012年

5 保利勇;趙東風;丁洪偉;;雙服務器異步控制策略輪詢系統(tǒng)性能的近似算法分析[A];2009年中國高校通信類院系學術研討會論文集[C];2009年

6 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運籌學學術交流大會論文集[C];2005年

7 李灝;張春路;丁國良;;對多層墻體反應系數(shù)的一種近似算法的討論[A];上海市制冷學會一九九七年學術年會論文集[C];1997年

8 李灝;張春路;丁國良;;對多層墻體反應系數(shù)的一種近似算法的討論[A];全國暖通空調(diào)制冷1998年學術年會論文集（2）[C];1998年

9 周露;吳瑤華;黃文虎;聞新;;一種推廣卡爾曼濾波的近似算法[A];1995中國控制與決策學術年會論文集[C];1995年

相關重要報紙文章 前1條

1 PALADIN;近似算法[N];電腦報;2003年

相關博士學位論文 前5條

1 楊朝霞;超圖嵌入圈問題的近似算法[D];山東大學;2010年

2 潘銳;設施選址與K-中間點問題的復雜性與近似算法[D];山東大學;2007年

3 陳仕平;若干組合優(yōu)化問題的近似算法設計與分析[D];浙江大學;2002年

4 柳楠;基因組片段填充問題的算法研究[D];山東大學;2013年

5 姜海濤;基因組比較算法研究[D];山東大學;2011年

相關碩士學位論文 前10條

1 陳崇琛;多色點集直線劃分的復雜性及其近似算法[D];復旦大學;2014年

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

3 張亞平;最小賦權連通k-子圖覆蓋問題的近似算法[D];新疆大學;2015年

4 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學;2015年

5 朱婷婷;具有不同釋放時間的單機重新排序問題的近似算法[D];蘭州大學;2016年

6 王克紅;均勻限制NP-完備間題及其近似算法設計[D];云南大學;2016年

7 肖文英;限制版本瓶頸斯坦納樹問題算法研究[D];中南民族大學;2015年

8 申子慧;廣義多乘積規(guī)劃問題的近似算法[D];河南師范大學;2016年

9 黃小曼;差異分批模式下供應鏈調(diào)度的近似算法設計與分析[D];合肥工業(yè)大學;2017年

10 劉冰冰;POMDP近似算法的研究與設計[D];中國科學技術大學;2017年

，

本文編號：1336595