部分可觀察馬爾可夫決策過程研究進(jìn)展

1、0引 言部分可觀察馬爾可夫決策過程 (partially observable Markov decision processes , POMDP 描述的是當(dāng)前世界模型部分可知的 情況下,智能體 Agent Agent 的 例如, 足球運(yùn)動(dòng)員在球場(chǎng)上踢 足球, 每個(gè)球員并不完全清楚他周圍的所有狀態(tài), 當(dāng)他向前 帶球的過程中, 他可能知道在他前面人的位置和狀態(tài), 但是 可能不知道在他后面的其他隊(duì)友的位置和狀態(tài), 此時(shí)他觀察 到的信息是不完整的, 但是一個(gè)優(yōu)秀的足球運(yùn)動(dòng)員往往靠著 一種感覺傳給他身后的最有利的隊(duì)員, 使其進(jìn)行最有利的進(jìn) 攻,過程就是部分可觀察馬爾可夫決策過程。在部分可感知模 型中,

2、 不僅要考慮到狀態(tài)的不確定性, 同時(shí)還要考慮到動(dòng)作 的不確定性,這種世界模型更加能夠客觀的描述真實(shí)世界, 因此應(yīng)用十分廣泛。本文綜述了目前在 POMDP 領(lǐng)域的研究情況, 介紹了 MDP 的數(shù)學(xué)理論基礎(chǔ)和決策模型, 以及一種典型的 POMDP 決策算 法-值迭代算法, 介紹了目前現(xiàn)有的幾種經(jīng)典的決策算法, 并 分析它們之間的優(yōu)點(diǎn)和不足, 列舉了一些 POMDP 常見的應(yīng)用 領(lǐng)域, 并進(jìn)行了總結(jié)和展望。1馬爾可夫決策過程Agent 每一個(gè)時(shí)刻都要做一些決策, 做決策時(shí)不僅要考慮 甚至是其它 Agents (Markov decision process , MDP 的最優(yōu)解, MDP 可以用一個(gè)

3、四元組 < , >來描述 1 :Agent 的行為集;, : ×:當(dāng) Agent 在狀態(tài) , 可能轉(zhuǎn)移到狀態(tài) 的概率, 使用 |: 情況下 采用動(dòng)作-2116-2117 -, Agent 使 Agent 選擇的動(dòng)作能夠獲得在 MDP 模型中, Agent 在為折扣因子, 其目標(biāo)是讓期望值有界(1由于 MDP 決策過程中, 要同時(shí)考慮世界模型的不確定性 和目標(biāo)的長遠(yuǎn)性, 需要在策略時(shí)刻, 狀態(tài)的情況下, 值函數(shù)構(gòu)造如下 = , = ,*,也就是 Agent 每個(gè)時(shí)刻都能做到的最優(yōu)決策, 根據(jù) Bellman 最優(yōu)策略公式可以得到。根據(jù)貪婪策略 *=arg max ,*1(4

4、 = max,*(5最優(yōu)策略的通常使用值迭代算法 2, 具體的算法步驟如下 步驟 1初始化 V 1(s =0, 假定一個(gè)任意小的數(shù)值= max,1得到 V t (S ; 步驟 3判斷下式, 如果結(jié)果為真, 則進(jìn)入步驟 4; 否則返回步驟 2; 1 <步驟 4對(duì)于每個(gè) s S , 取 =arg max,1由于下式可以知道, 值迭代算法所求出來的策略將是最 優(yōu)策略 max *(62POMDPs在 POMDP 模型中, Agent 必須利用隨機(jī)環(huán)境中部分觀察 在每個(gè)時(shí)間點(diǎn)上, Agent 都可能是眾多可 能狀態(tài)中的某一狀態(tài), 它必須利用現(xiàn)有的部分信 息、 1,3。 一般情況下, POMDP 可

5、以用一個(gè)六元組 < , , >來描述, 其中、 與 MDP 一樣。 , : ×£ºA gent 它可計(jì)算出采 用動(dòng)作:Agent 使用來描述 Agent 處在用以下的形式來進(jìn)行描述 4,5 : × ;、 行 為得到, 具體的過程根據(jù)貝葉斯計(jì)算如下 , , , , ,Pr, = Pr, Pr , ,策略 Agent 世界模型 s a圖 2MDP 決策t 時(shí)刻狀態(tài) S t t+1時(shí)刻狀態(tài) S t+1T 函數(shù)R選取 動(dòng)作 報(bào)酬 值選取 動(dòng)作 報(bào)酬 值圖 3 POMDP 模型狀態(tài)評(píng)估 (SE 圖 4決策行動(dòng)信念觀察狀態(tài)abosa'b'

6、o's' R (s, a O (s', a, o T (s, a, s' b (s -2118 -Pr , =Pr , , =Pr , Pr , = , , = , , = , ,(8以前的觀點(diǎn)來解決 POMDP 問題時(shí), 由于必須知道歷史動(dòng) 作才能決定當(dāng)前的動(dòng)作, 這種解決方案是非馬爾可夫鏈, 然而 當(dāng)引入信念狀態(tài)空間后, POMDP 問題就可以轉(zhuǎn)化為基于信念 狀態(tài)空間的馬爾可夫鏈來求解。通過信念狀態(tài)空間的引入, POMDP 問題可以看成 Belief MDP 問題3。尋求一種最優(yōu)策略將當(dāng)前的信念狀態(tài)映射到Agent 的行動(dòng)上, 根據(jù)當(dāng)前的信念狀態(tài)和行為就可以

7、決定下一 個(gè)周期的信念狀態(tài)和行為, 具體描述如下 ,=Pr(b' a,b =a,b,o(b,a :信念狀態(tài)報(bào)酬函數(shù), 其定義如下 *=arg max * *= max*1 -策略樹 (如圖 5所示 和值函數(shù), 通過求解值函數(shù)來進(jìn)行最優(yōu)策略的選取。令 -策略樹, - 策略樹的集合, 為策略樹的節(jié)點(diǎn), 則值函數(shù)的構(gòu)造如下 = + , , =(14為了簡化表達(dá), 令 =< , =µÄ×îÓÅÖµ£¬Í¼6 描述了在不同區(qū)域的最優(yōu)值= max(15 對(duì)于以上策略樹, 其

8、最大的節(jié)點(diǎn)數(shù)為 ( |-1 , 其中 |1(16策略樹的時(shí)間復(fù)雜度是一個(gè)指數(shù)函數(shù),隨著,然后將所有節(jié)點(diǎn)的策略集合求或, 得到值函數(shù)4,5。 由于 |、 |1|的時(shí)間復(fù)雜度是多項(xiàng)式的, 因此1(18 (19W i t n e s s算法不去關(guān)注所有時(shí)間的所有動(dòng)作, 它將每個(gè)節(jié)點(diǎn)進(jìn)行分解, 取獲取每個(gè)節(jié)點(diǎn)的最優(yōu)動(dòng)作, 然后在將所有的最 優(yōu)動(dòng)作轉(zhuǎn)換為最終的值函數(shù)。 這種算法在某些情況下可以降 低計(jì)算的復(fù)雜度, 但對(duì)世界模型的建模不夠完整, 難以保證所求得的解一定是有效的, 算法如圖 7所示。3.2Incremental Pruning 算法Witness 算法對(duì)于小規(guī)模的計(jì)算時(shí)效果比較好, 但是當(dāng)問

9、題規(guī)模變大后,使用 Witness 算法就很難求得近似最優(yōu)解。 Zhang and Liu (1996 提出一種 Incremental Pruning 算法 (如圖 8所示 可以較好的解決較大規(guī)模問題。該算法的基本思想是 使用動(dòng)態(tài)規(guī)劃方法根據(jù)給定的值函數(shù) ,t =t +1;whi l e ( 1 <12 O-2119- 數(shù) =max +(20 =max =(22 表示成向量集合 表示成向量集合 , 將 =max 表示成向量集合 =max 表示成向量集合(24 1 2(25 = , , , Pr ,3.3基于點(diǎn)的值迭代算法以上兩種算法都是通過降低信念狀態(tài)空間的維數(shù)來降低求解的規(guī)模, 但是

10、在實(shí)際的求解過程中歷史觀察-動(dòng)作集合 也是一個(gè)指數(shù)函數(shù), 如何降低歷史觀察-動(dòng)作函數(shù)的求解復(fù) 雜度也是衡量一種算法優(yōu)劣的重要尺度。 基于點(diǎn)的值迭代算 法 Jolle Pineau,Geoff Gordon and Sebastian Thrun,2003主要是通 過降低歷史觀察-動(dòng)作值函數(shù)的求解規(guī)模來近似求解 POMDP 問題 7。 基于值迭代的算法都是 PWLC 的, 可以表示為可以看成 Backup 操作, 每個(gè)動(dòng)作都對(duì)應(yīng)一個(gè) +, , ,=, 實(shí)現(xiàn)精確更新, 首先引入中間變量, * =,0 =, , 1 =|O| , 也就是所謂的 “維數(shù)災(zāi)” 問題, 使得問題無法求解。 為了解決這個(gè)問題

11、, Witness 算法、 Incremental Pruning 算法和基于點(diǎn) 的值迭代算法都是將整個(gè)問題進(jìn)行分解,構(gòu)造, |, |。4POMDP 應(yīng)用領(lǐng)域20世紀(jì)末,由于看到 POMDP 模型可以更加真實(shí)的反應(yīng) 客觀世界模型, 人們開始對(duì) POMDP 進(jìn)行大量的研究和應(yīng)用 9。 在科學(xué)應(yīng)用領(lǐng)域, 科學(xué)家主要將其應(yīng)用到自主機(jī)器人控制上。 例如:在太空中的漫步機(jī)器人; 機(jī)器人導(dǎo)航; 炸彈拆除; 放射性 廢物回收; 深海探礦; 管道網(wǎng)絡(luò)的檢修和維護(hù)等, 在這些領(lǐng)域中, 人們不可能直接操作, 只能依靠機(jī)器人來進(jìn)行, 同時(shí)這些 領(lǐng)域的環(huán)境條件非常符合 POMDP 模型。在工業(yè)應(yīng)用領(lǐng)域, 例如機(jī)器生產(chǎn)

12、和維護(hù), 人們可以建立一 個(gè) POMDP 模型, 使得最小化機(jī)器使用費(fèi)用, 最大化生產(chǎn)能力。 例 如 道 路 檢 測(cè) 管 理,美 國 高 速 公 路 就 是 一 個(gè) 成 功 案 例, Woodward-Clycde 公司開發(fā)了一個(gè)基于馬氏決策過程的公路 管理系統(tǒng), 使用有限的資金來維護(hù)公路, 這個(gè)系統(tǒng) 4年內(nèi)就節(jié) 省了 1億多美元。在養(yǎng)魚行業(yè)中,也需要在短期目標(biāo)和長期 目標(biāo)之間作平衡, 使用 POMDP 模型決策可以達(dá)到這一目的。 在商業(yè)應(yīng)用領(lǐng)域, 例如網(wǎng)絡(luò)故障查找和排除, 假如電網(wǎng)出現(xiàn)故 障, 需要快速地找到故障處并排除它。 在市場(chǎng)管理領(lǐng)域, 人們 可以開發(fā)基于 POMDP 的軟件來解決庫存

13、問題, 使得利潤最大 化。 POMDP 還可以應(yīng)用到醫(yī)療診斷問題上, 盡早查處病因。 在軍事領(lǐng)域, POMDP 的應(yīng)用也很廣泛, 例如:移動(dòng)目標(biāo)的查找、 跟蹤和拯救; 目標(biāo)的辨認(rèn); 武器的使用分配等。5結(jié)束語解決 POMDP 問題的算法有很多種, 但是從本質(zhì)上都是基于動(dòng)態(tài)規(guī)劃和線性規(guī)劃思想, 對(duì)所求問題進(jìn)行分解, 降低 “維 數(shù)災(zāi)” 問題, 然后采用值迭代算法進(jìn)行求解。 本文重點(diǎn)介紹和 分析了 Witness 算法、 Incremental Pruning 算法和基于點(diǎn)的值迭 代算法, 這 3種算法雖然表達(dá)方式不同, 但是一個(gè)本質(zhì)思想就 是降低所求問題的規(guī)模, 求出近似解。(下轉(zhuǎn)第 2126頁

14、 DP-Update (S For each a in A and o in O;S o a =Filter ( , S t-1 ;S a =IncPrune ( , ; =return S' IncPrune ( , W=RR (2; for (i=3;i<=k;i+ W=RR( W, ; retrun W; RR (A, B F=A;W=W w ; F=Fw ; while (F +1=(a 1+1+1+|<|+;W=W w ; F=Fw ; retrun W;圖 8Incremental Pruning 算法表 13種算法分析比較算法指標(biāo)最壞 最好 Witness 算

15、法 O (ZMQ 2 O (ZMQ 2 Incremental Pruning 算法O (ZMQ 2 O (ZQ 2 基于點(diǎn)的值迭代算法O (Z 2M 2Q O (ZMQ 3系統(tǒng)實(shí)現(xiàn)在上述研究和分析的基礎(chǔ)上, 以全國高校儀器設(shè)備和優(yōu) 質(zhì)資源共享項(xiàng)目為契機(jī), 設(shè)計(jì)實(shí)現(xiàn)了基于 Web 貴重儀器設(shè)備 共享系統(tǒng)。 系統(tǒng)采用 J2EE 技術(shù), 設(shè)計(jì)為典型的 B/S結(jié)構(gòu):表示 層是瀏覽器, 顯示用戶界面; 應(yīng)用層為服務(wù)器和應(yīng)用程序, 應(yīng) 用程序由 JSP 、 Servlet 、 Javabean 、 Applet 和 EJB 構(gòu)成; 數(shù)據(jù)層存 儲(chǔ)了儀器設(shè)備的相關(guān)信息。通過該系統(tǒng), 各高校之間可以通 過 I

16、nternet 便捷的共享貴重儀器設(shè)備資源, 提高貴重儀器的使 用率, 實(shí)現(xiàn)高校之間優(yōu)勢(shì)資源互補(bǔ), 提高國內(nèi)高校綜合實(shí)力和 競爭能力。4結(jié)束語基于 Web 貴重儀器設(shè)備共享系統(tǒng)充分體現(xiàn)了貴重儀器設(shè) 備遠(yuǎn)程操作和共享的特點(diǎn)。 系統(tǒng)采用基于 Web 的工作機(jī)制和 混合式共享模式有利于信息的動(dòng)態(tài)更新和統(tǒng)一管理, 有利于 解決地理位置分布性和軟硬件平臺(tái)異構(gòu)性的問題, 保證了系 統(tǒng)的魯棒性、 通用性和可擴(kuò)展性, 為貴重儀器設(shè)備的遠(yuǎn)程操作 和共享奠定了基礎(chǔ)。系統(tǒng)采用基于角色的訪問控制技術(shù), 實(shí) 現(xiàn)了 “用戶 -角色 -權(quán)限” 管理模式, 保證了數(shù)據(jù)和系統(tǒng)的安全 性, 降低了管理難度, 而且可以滿足用戶多樣

17、化需求; 采用屏 幕共享技術(shù)開發(fā)了第三方共享軟件, 實(shí)現(xiàn)了通過 Internet 對(duì)貴 重儀器設(shè)備的遠(yuǎn)程操作和共享, 保證了軟件的通用性。系統(tǒng) 可以避免貴重儀器設(shè)備的重復(fù)購置, 提高現(xiàn)有資源的使用率, 為最終建立全國范圍內(nèi)共性的和跨地區(qū)、 跨高校的網(wǎng)上儀器 設(shè)備資源共享應(yīng)用服務(wù)平臺(tái)提供良好的基礎(chǔ)。參考文獻(xiàn) :1范莉婭 , 王愛民 , 肖田元 , 等 . 基于 Web 的全生命周期項(xiàng)目管理 系統(tǒng)研究 J . 機(jī)械科學(xué)與技術(shù) , 2005,24(5 :529-532.2楊志寶 , 羅亞波 , 肖田元 . 面向中小企業(yè)的 ASP 方案研究 J . 計(jì) 算機(jī)工程與應(yīng)用 , 2003,39(22 :19

18、8-201.3孫笑慶 , 劉寶旭 , 姜力東 , 等 .FreeNet 中的密鑰和索引機(jī)制綜述 J . 計(jì)算機(jī)工程與應(yīng)用 , 2003,39(11 :138-141.4張聯(lián)峰 , 劉乃安 , 錢秀檳 , 等 . 綜述 :對(duì)等網(wǎng) (P2P 技術(shù) J . 計(jì)算機(jī)工 程與應(yīng)用 , 2003,39(12 :142-145.5毛科杰 . 網(wǎng)絡(luò)化制造平臺(tái)公共服務(wù)技術(shù)研究 D . 北京 :清華大 學(xué) , 2005.6侯永濤 , 顧寄南 . 網(wǎng)絡(luò)化制造環(huán)境下的軟件工具共享技術(shù)的研 究綜述 J . 中國制造業(yè)信息化 , 2004,33(9 :86-88.(上接第 2119頁 目前 POMDP 面臨兩大問題, 其

19、一是 “維數(shù)災(zāi)” 問題, 涉及 的是時(shí)間復(fù)雜度; 另一種是 “應(yīng)用建模難” 問題。對(duì)于 “維數(shù) 災(zāi)” 問題, 除了使用動(dòng)態(tài)規(guī)劃和線性規(guī)劃思想外, 還需探討其 它解決方案, 同時(shí)加入學(xué)習(xí)算法, 特別是增強(qiáng)學(xué)習(xí)、 分層學(xué)習(xí)。 對(duì)于 “應(yīng)用建模難” 問題, 在許多應(yīng)用領(lǐng)域中, 看起來很簡單的 問題, 但是卻需要很大的狀態(tài)空間, 因此需要一些新的算法來 高效地解決這個(gè)問題。 以上兩種問題的解決, 是 POMDP 的未 來研究的主要方向。參考文獻(xiàn) :1Stephen M Majercik, Michael L Littman. Contingent planning under uncertainty

20、via stochastic satisfiability J . Artificial Intel-ligence, 2003,147(1-2 :119-162.2劉克 . 實(shí)用馬爾可夫決策過程 M . 北京 :清華大學(xué)出版社 , 2004. 20-52.3Alexander L Strehl, Michael L Littman. An empirical evaluation of interval estimation for Markov decision processes A . The 16th IEEE International on Tools with Artifici

21、al Intelligence Conference C . Seattle:The MIT Press, 2004. 531-539.4Poupart P . Exploiting structure to effciently solve large scale partially observable Markov decision processes D . Toronto: University of Toronto, 2005.5SébastienPaquet, Ludovic Tobin, Brahim Chaibdraa. An onlinePOMDP algorit

22、hm for complex multi-Agent environment A . The Proceedings of The fourth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-05 C . Netherlands:Utrecht University,2005. 970-977.6Haakan L S Younes, Michael L Littman, David Weissman, et al. The first probabilistic track of the international planning compe-tition J . Journal of Artificial Intelligence Research, 2005, 24: 851-887.7Pineau J, Gordon G, Thrun S. Point-based value iteration:An anytime algorithm