部分可觀察馬氏決策過(guò)程的復(fù)雜性理論及規(guī)劃算法研究.pdf

1、部分可觀察的馬氏決策過(guò)程(partiallyobservableMarkovdecisionprocess，簡(jiǎn)稱(chēng)POMDP)為主體在部分可觀察的隨機(jī)環(huán)境中的序列決策問(wèn)題提供了一個(gè)通用的數(shù)學(xué)模型。POMDP模型可以被廣泛地用來(lái)建模機(jī)器人導(dǎo)航、物體抓取、目標(biāo)跟蹤、人機(jī)對(duì)話(huà)等規(guī)劃和學(xué)習(xí)任務(wù)。一般而言，在合理時(shí)間內(nèi)精確地求解POMDP規(guī)劃問(wèn)題是不可能的。近十年來(lái)，出現(xiàn)了很多POMDP模型的近似規(guī)劃算法。它們可以大致分為離線規(guī)劃算法和在線規(guī)劃算法

2、。
　　 基于點(diǎn)的值迭代算法是這些離線規(guī)劃算法中最耀眼的一類(lèi)，它在近十年里取得了很大的成功。它的出現(xiàn)和發(fā)展使得POMDP規(guī)劃問(wèn)題求解器從只能求解幾十個(gè)狀態(tài)的小規(guī)模POMDP問(wèn)題發(fā)展到可以求解數(shù)十萬(wàn)個(gè)狀態(tài)的大規(guī)模POMDP問(wèn)題。對(duì)可達(dá)信念空間的δ-覆蓋數(shù)（簡(jiǎn)稱(chēng):覆蓋數(shù)）這個(gè)概念的認(rèn)識(shí)的不斷深入對(duì)基于點(diǎn)的值迭代算法的發(fā)展起到了重要的推動(dòng)作用?？蛇_(dá)信念空間指的是從初始信念狀態(tài)通過(guò)采取隨機(jī)行動(dòng)可以到達(dá)的信念狀態(tài)構(gòu)成的集合。覆蓋數(shù)指的是用

3、給定半徑δ＞0的小球完全覆蓋可達(dá)信念空間所需要的球的最少個(gè)數(shù)。已有的文獻(xiàn)表明:我們可以在覆蓋數(shù)的多項(xiàng)式時(shí)間內(nèi)計(jì)算出POMDP規(guī)劃問(wèn)題的近似最優(yōu)解。在本文中，我們將給出三種估算覆蓋數(shù)的方法，并分析它們各自的優(yōu)缺點(diǎn)。我們將看到在一組小規(guī)模的POMDP基準(zhǔn)問(wèn)題上，覆蓋數(shù)是比其它的復(fù)雜性度量，如:狀態(tài)數(shù)等，更好得多的表征POMDP規(guī)劃問(wèn)題和學(xué)習(xí)問(wèn)題難易程度的度量。進(jìn)一步地，我們將把覆蓋數(shù)與POMDP規(guī)劃問(wèn)題間的理論關(guān)系推廣到POMDP學(xué)習(xí)問(wèn)題領(lǐng)

4、域。我們將從覆蓋數(shù)的角度來(lái)分析POMDP學(xué)習(xí)問(wèn)題比規(guī)劃問(wèn)題更難的原因，并提出一個(gè)在覆蓋數(shù)的指數(shù)時(shí)間內(nèi)收斂的POMDP學(xué)習(xí)算法。我們希望覆蓋數(shù)的概念及它的估算方法能夠?yàn)閷?lái)設(shè)計(jì)出更高效的POMDP學(xué)習(xí)算法提供洞察和指導(dǎo)。
　　 基于對(duì)覆蓋數(shù)的研究，我們發(fā)現(xiàn):現(xiàn)有的一些基于點(diǎn)的值迭代算法在保證能在有限時(shí)間內(nèi)找到近似最優(yōu)解的同時(shí)，忽略了一些重要的啟發(fā)式信息，這造成了這些算法的性能并不足夠高效。我們提出了一個(gè)基于貪心策略的值迭代算法框架

5、，它的主要思想是:利用這些被忽略的啟發(fā)式信息來(lái)構(gòu)造一個(gè)貪心子算法，并把它插入到之前的值迭代算法中。我們構(gòu)造了一個(gè)有一定的數(shù)學(xué)理論支持的、被稱(chēng)為第二好策略導(dǎo)向的貪心子算法來(lái)檢驗(yàn)該算法框架的有效性。我們的實(shí)驗(yàn)結(jié)果表明:在求解很多POMDP基準(zhǔn)問(wèn)題時(shí)，三個(gè)結(jié)合了第二好策略導(dǎo)向的貪心子算法的值迭代算法較之前的算法有至少一個(gè)數(shù)量級(jí)的時(shí)間性能的改進(jìn)。
　　 與離線規(guī)劃算法不同的是，在線規(guī)劃算法采取的是“按需”做決策而不是預(yù)先對(duì)整個(gè)狀態(tài)空間做

6、決策的方式，因此能夠在較短規(guī)劃時(shí)間內(nèi)高效地處理較大規(guī)模的POMDP問(wèn)題。在本文中，我們將利用POMDP問(wèn)題中狀態(tài)表示的結(jié)構(gòu)和雜合啟發(fā)法來(lái)加速現(xiàn)有的啟發(fā)式在線規(guī)劃算法。我們將提出兩個(gè)新的在線規(guī)劃算法，它們分別被用來(lái)檢驗(yàn)一種最近提出的因子化狀態(tài)表示方法和一種新穎的雜合啟發(fā)法在加速POMDP規(guī)劃算法中的重要性。我們的實(shí)驗(yàn)結(jié)果表明:從可擴(kuò)展性和解的質(zhì)量?jī)蓚€(gè)方面來(lái)看，使用了因子化狀態(tài)表示和雜合啟發(fā)法的新的在線規(guī)劃算法的實(shí)驗(yàn)性能都比當(dāng)前的其它啟發(fā)式