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

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

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 常見(jiàn)的應(yīng)用 領(lǐng)域, 并進(jìn)行了總結(jié)和展望。1馬爾可夫決策過(guò)程Agent 每一個(gè)時(shí)刻都要做一些決策, 做決策時(shí)不僅要考慮 甚至是其它 Agents (Markov decision process , MDP 的最優(yōu)解, MDP 可以用一個(gè)

3、四元組 < , >來(lái)描述 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 決策過(guò)程中, 要同時(shí)考慮世界模型的不確定性 和目標(biāo)的長(zhǎng)遠(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由于下式可以知道, 值迭代算法所求出來(lái)的策略將是最 優(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è)六元組 < , , >來(lái)描述, 其中、 與 MDP 一樣。 , : ×£ºA gent 它可計(jì)算出采 用動(dòng)作:Agent 使用來(lái)描述 Agent 處在用以下的形式來(lái)進(jìn)行描述 4,5 : × ;、 行 為得到, 具體的過(guò)程根據(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)來(lái)解決 POMDP 問(wèn)題時(shí), 由于必須知道歷史動(dòng) 作才能決定當(dāng)前的動(dòng)作, 這種解決方案是非馬爾可夫鏈, 然而 當(dāng)引入信念狀態(tài)空間后, POMDP 問(wèn)題就可以轉(zhuǎn)化為基于信念 狀態(tài)空間的馬爾可夫鏈來(lái)求解。通過(guò)信念狀態(tài)空間的引入, POMDP 問(wèn)題可以看成 Belief MDP 問(wèn)題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 -策略樹(shù) (如圖 5所示 和值函數(shù), 通過(guò)求解值函數(shù)來(lái)進(jìn)行最優(yōu)策略的選取。令 -策略樹(shù), - 策略樹(shù)的集合, 為策略樹(shù)的節(jié)點(diǎn), 則值函數(shù)的構(gòu)造如下 = + , , =(14為了簡(jiǎn)化表達(dá), 令 =< , =µÄ×îÓÅÖµ£¬Í¼6 描述了在不同區(qū)域的最優(yōu)值= max(15 對(duì)于以上策略樹(shù), 其

8、最大的節(jié)點(diǎn)數(shù)為 ( |-1 , 其中 |1(16策略樹(shù)的時(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)問(wèn)

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

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

11、, Witness 算法、 Incremental Pruning 算法和基于點(diǎn) 的值迭代算法都是將整個(gè)問(wèn)題進(jìn)行分解,構(gòu)造, |, |。4POMDP 應(yīng)用領(lǐng)域20世紀(jì)末,由于看到 POMDP 模型可以更加真實(shí)的反應(yīng) 客觀世界模型, 人們開(kāi)始對(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ī)器人來(lái)進(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è) 管 理,美 國(guó) 高 速 公 路 就 是 一 個(gè) 成 功 案 例, Woodward-Clycde 公司開(kāi)發(fā)了一個(gè)基于馬氏決策過(guò)程的公路 管理系統(tǒng), 使用有限的資金來(lái)維護(hù)公路, 這個(gè)系統(tǒng) 4年內(nèi)就節(jié) 省了 1億多美元。在養(yǎng)魚(yú)行業(yè)中,也需要在短期目標(biāo)和長(zhǎng)期 目標(biāo)之間作平衡, 使用 POMDP 模型決策可以達(dá)到這一目的。 在商業(yè)應(yīng)用領(lǐng)域, 例如網(wǎng)絡(luò)故障查找和排除, 假如電網(wǎng)出現(xiàn)故 障, 需要快速地找到故障處并排除它。 在市場(chǎng)管理領(lǐng)域, 人們 可以開(kāi)發(fā)基于 POMDP 的軟件來(lái)解決庫(kù)存

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

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ǔ)上, 以全國(guó)高校儀器設(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)信息。通過(guò)該系統(tǒng), 各高校之間可以通 過(guò) I

16、nternet 便捷的共享貴重儀器設(shè)備資源, 提高貴重儀器的使 用率, 實(shí)現(xiàn)高校之間優(yōu)勢(shì)資源互補(bǔ), 提高國(guó)內(nèi)高校綜合實(shí)力和 競(jìng)爭(zhēng)能力。4結(jié)束語(yǔ)基于 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)性的問(wèn)題, 保證了系 統(tǒng)的魯棒性、 通用性和可擴(kuò)展性, 為貴重儀器設(shè)備的遠(yuǎn)程操作 和共享奠定了基礎(chǔ)。系統(tǒng)采用基于角色的訪問(wèn)控制技術(shù), 實(shí) 現(xiàn)了 “用戶 -角色 -權(quán)限” 管理模式, 保證了數(shù)據(jù)和系統(tǒng)的安全 性, 降低了管理難度, 而且可以滿足用戶多樣

17、化需求; 采用屏 幕共享技術(shù)開(kāi)發(fā)了第三方共享軟件, 實(shí)現(xiàn)了通過(guò) Internet 對(duì)貴 重儀器設(shè)備的遠(yuǎn)程操作和共享, 保證了軟件的通用性。系統(tǒng) 可以避免貴重儀器設(shè)備的重復(fù)購(gòu)置, 提高現(xiàn)有資源的使用率, 為最終建立全國(guó)范圍內(nèi)共性的和跨地區(qū)、 跨高校的網(wǎng)上儀器 設(shè)備資源共享應(yīng)用服務(wù)平臺(tái)提供良好的基礎(chǔ)。參考文獻(xiàn) :1范莉婭 , 王愛(ài)民 , 肖田元 , 等 . 基于 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)峰 , 劉乃安 , 錢(qiá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 . 中國(guó)制造業(yè)信息化 , 2004,33(9 :86-88.7David Booth, Hugo Haas, Fran

19、cis McCabe,et al. Web Services Architecture DB/OL. /TR/ws-arch/,2004. 8毛科杰 , 范莉婭 , 王愛(ài)民 , 等 . 基于 ASP 的軟件資源共享通用平 臺(tái)研究及實(shí)現(xiàn) J . 航空制造技術(shù) , 2005,48(10 :50-55.(上接第 2119頁(yè) 目前 POMDP 面臨兩大問(wèn)題, 其一是 “維數(shù)災(zāi)” 問(wèn)題, 涉及 的是時(shí)間復(fù)雜度; 另一種是 “應(yīng)用建模難” 問(wèn)題。對(duì)于 “維數(shù) 災(zāi)” 問(wèn)題, 除了使用動(dòng)態(tài)規(guī)劃和線性規(guī)劃思想外, 還需探討其 它解決方案, 同時(shí)加入學(xué)習(xí)算法, 特別是增強(qiáng)學(xué)習(xí)、 分

20、層學(xué)習(xí)。 對(duì)于 “應(yīng)用建模難” 問(wèn)題, 在許多應(yīng)用領(lǐng)域中, 看起來(lái)很簡(jiǎn)單的 問(wèn)題, 但是卻需要很大的狀態(tài)空間, 因此需要一些新的算法來(lái) 高效地解決這個(gè)問(wèn)題。 以上兩種問(wèn)題的解決, 是 POMDP 的未 來(lái)研究的主要方向。參考文獻(xiàn) :1Stephen M Majercik, Michael L Littman. Contingent planning under uncertainty via stochastic satisfiability J . Artificial Intel-ligence, 2003,147(1-2 :119-162.2劉克 . 實(shí)用馬爾可夫決策過(guò)程 M . 北京

21、:清華大學(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 Artificial Intelligence Conference C . Seattle:The MIT Press, 2004. 531-539.4Poupart P . Exploiting structure to e

22、ffciently solve large scale partially observable Markov decision processes D . Toronto: University of Toronto, 2005.5SébastienPaquet, Ludovic Tobin, Brahim Chaibdraa. An onlinePOMDP algorithm for complex multi-Agent environment A . The Proceedings of The fourth International Joint Conference on

23、 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:A