POMDP近似算法的研究與設計.pdf

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

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

3、的質(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)生信念點路徑，對路徑可能達到