部分可觀察馬爾可夫決策過程研究進展_百度文庫

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

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

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

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

5、以用一個六元組 < , , >來描述, 其中、 與 MDP 一樣。 , : ×£ºA gent 它可計算出采 用動作:Agent 使用來描述 Agent 處在用以下的形式來進行描述 4,5 : × ;、 行 為得到, 具體的過程根據(jù)貝葉斯計算如下 , , , , ,Pr, = Pr, Pr , ,策略 Agent 世界模型 s a圖 2MDP 決策t 時刻狀態(tài) S t t+1時刻狀態(tài) S t+1T 函數(shù)R選取 動作 報酬 值選取 動作 報酬 值圖 3 POMDP 模型狀態(tài)評估 (SE 圖 4決策行動信念觀察狀態(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以前的觀點來解決 POMDP 問題時, 由于必須知道歷史動 作才能決定當前的動作, 這種解決方案是非馬爾可夫鏈, 然而 當引入信念狀態(tài)空間后, POMDP 問題就可以轉(zhuǎn)化為基于信念 狀態(tài)空間的馬爾可夫鏈來求解。通過信念狀態(tài)空間的引入, POMDP 問題可以看成 Belief MDP 問題3。尋求一種最優(yōu)策略將當前的信念狀態(tài)映射到Agent 的行動上, 根據(jù)當前的信念狀態(tài)和行為就可以

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

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

9、題規(guī)模變大后,使用 Witness 算法就很難求得近似最優(yōu)解。 Zhang and Liu (1996 提出一種 Incremental Pruning 算法 (如圖 8所示 可以較好的解決較大規(guī)模問題。該算法的基本思想是 使用動態(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基于點的值迭代算法以上兩種算法都是通過降低信念狀態(tài)空間的維數(shù)來降低求解的規(guī)模, 但是

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

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

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

13、問題, 使得利潤最大 化。 POMDP 還可以應用到醫(yī)療診斷問題上, 盡早查處病因。 在軍事領(lǐng)域, POMDP 的應用也很廣泛, 例如:移動目標的查找、 跟蹤和拯救; 目標的辨認; 武器的使用分配等。5結(jié)束語解決 POMDP 問題的算法有很多種, 但是從本質(zhì)上都是基于動態(tài)規(guī)劃和線性規(guī)劃思想, 對所求問題進行分解, 降低 “維 數(shù)災” 問題, 然后采用值迭代算法進行求解。 本文重點介紹和 分析了 Witness 算法、 Incremental Pruning 算法和基于點的值迭 代算法, 這 3種算法雖然表達方式不同, 但是一個本質(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種算法分析比較算法指標最壞 最好 Witness 算

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

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

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

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

19、一是 “維數(shù)災” 問題, 涉及 的是時間復雜度; 另一種是 “應用建模難” 問題。對于 “維數(shù) 災” 問題, 除了使用動態(tài)規(guī)劃和線性規(guī)劃思想外, 還需探討其 它解決方案, 同時加入學習算法, 特別是增強學習、 分層學習。 對于 “應用建模難” 問題, 在許多應用領(lǐng)域中, 看起來很簡單的 問題, 但是卻需要很大的狀態(tài)空間, 因此需要一些新的算法來 高效地解決這個問題。 以上兩種問題的解決, 是 POMDP 的未 來研究的主要方向。參考文獻 :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劉克 . 實用馬爾可夫決策過程 M . 北京 :清華大學出版社 , 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