本文關(guān)鍵詞：POMDP近似算法的研究與設(shè)計(jì)　出處：《中國科學(xué)技術(shù)大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)會議論文 前9條

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

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

3 田世俊;李建;朱洪;;多需求目標(biāo)的UFL問題及其近似算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

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

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

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

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

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

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

相關(guān)重要報紙文章 前1條

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

相關(guān)博士學(xué)位論文 前5條

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

2 潘銳;設(shè)施選址與K-中間點(diǎn)問題的復(fù)雜性與近似算法[D];山東大學(xué);2007年

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

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

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

相關(guān)碩士學(xué)位論文 前10條

1 陳崇琛;多色點(diǎn)集直線劃分的復(fù)雜性及其近似算法[D];復(fù)旦大學(xué);2014年

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

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

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

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

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

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

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

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

10 劉冰冰;POMDP近似算法的研究與設(shè)計(jì)[D];中國科學(xué)技術(shù)大學(xué);2017年

，

本文編號：1336595