POMDP近似算法的研究與設(shè)計(jì).pdf

1、部分可觀測(cè)馬爾科夫決策過程(Partially Observable Markov Decision Process，POMDP)是處理不確定條件下決策問題的一個(gè)通用框架，它在機(jī)器人控制，口語(yǔ)系統(tǒng)，醫(yī)療診斷等領(lǐng)域都有很大的應(yīng)用前景。但是由于POMDP問題的歷史災(zāi)難和緯度災(zāi)難性質(zhì)，精確求解算法是NP難問題，這就大大限制了其在實(shí)際中的應(yīng)用。近年來(lái)，近似算法，特別是基于點(diǎn)的近似算法在POMDP策略求解上取得了很大的進(jìn)步。
　　基于點(diǎn)的算

2、法只考慮初始信念點(diǎn)的可達(dá)空間，在可達(dá)空間的采樣點(diǎn)上進(jìn)行值迭代，不同算法之間的區(qū)別主要在于采樣方法和迭代策略。其代表性的算法有基于點(diǎn)的值迭代(PBVI)，前向搜索值迭代(FSVI)和啟發(fā)式搜索值迭代(HSVI)，它們通常能夠得到最優(yōu)或近似最優(yōu)的策略。另一類重要的近似算法是基于迭代函數(shù)的近似，如基于MDP的近似(QMDP)，快速告知邊界法(FIB)，它們得到的是精確值函數(shù)的上下界。這類算法通常簡(jiǎn)單快速，能夠處理規(guī)模較大的問題，但是對(duì)產(chǎn)生策略

3、的質(zhì)量沒有保證。
　　為了在較短的時(shí)間內(nèi)得到一個(gè)良好的下界，本文提出了相關(guān)狀態(tài)提升法(RSU)，它的主要思想是用對(duì)信念點(diǎn)相關(guān)狀態(tài)的提升去近似對(duì)信念點(diǎn)的提升，同時(shí)借助內(nèi)在的MDP探索最優(yōu)策略下的可達(dá)狀態(tài)空間，然后在得到的狀態(tài)空間中利用近似值迭代和狀態(tài)轉(zhuǎn)移樹的拓?fù)浣Y(jié)構(gòu)來(lái)加速迭代的進(jìn)程。
　　利用得到的上下界，本文給出了一個(gè)改進(jìn)的基于點(diǎn)的算法——多路啟發(fā)式搜索值迭代(MHSVI)，依據(jù)可能的最優(yōu)值函數(shù)產(chǎn)生信念點(diǎn)路徑，對(duì)路徑可能達(dá)到