一種基于最優(yōu)策略概率分布的POMDP值迭代算法

劉　峰,王崇駿,駱　斌

(1.南京大學軟件學院,江蘇南京 210093;2.南京大學計算機科學與技術(shù)系,江蘇南京 210093;3.南京大學軟件新技術(shù)國家重點實驗室,江蘇南京 210093)

?

一種基于最優(yōu)策略概率分布的POMDP值迭代算法

劉峰1,3,王崇駿2,3,駱斌1,3

(1.南京大學軟件學院,江蘇南京 210093;2.南京大學計算機科學與技術(shù)系,江蘇南京 210093;3.南京大學軟件新技術(shù)國家重點實驗室,江蘇南京 210093)

隨著應(yīng)用中POMDP問題的規(guī)模不斷擴大,基于最優(yōu)策略可達區(qū)域的啟發(fā)式方法成為了目前的研究熱點.然而目前已有的算法雖然保證了全局最優(yōu),但選擇最優(yōu)動作還不夠精確,影響了算法的效率.本文提出一種基于最優(yōu)策略概率的值迭代方法PBVIOP.該方法在深度優(yōu)先的啟發(fā)式探索中,根據(jù)各個動作值函數(shù)在其上界和下界之間的分布,用蒙特卡羅法計算動作最優(yōu)的概率,選擇概率最大的動作作為最優(yōu)探索策略.在4個基準問題上的實驗結(jié)果表明PBVIOP算法能夠收斂到全局最優(yōu)解,并明顯提高了收斂效率.

部分可觀測馬爾科夫決策過程;基于最優(yōu)策略概率的值迭代算法;蒙特卡羅法

1　引言

規(guī)劃問題,即“設(shè)計合理的行動計劃以達到個體目標”[1],是人工智能研究里的重要領(lǐng)域.序列決策問題(Sequential Decision Making)是規(guī)劃問題的一個重要子領(lǐng)域.而動態(tài)不確定性環(huán)境下的行動規(guī)劃是其中的熱點,其動態(tài)性和不確定性是在這種環(huán)境下進行行動規(guī)劃的主要難點.

部分可觀察馬氏決策過程(Partially Observable Markov Decision Process,POMDP)是一個強大的數(shù)學框架,可以用來描述并解決很多實際的不確定環(huán)境中序列決策問題,例如機器人探索任務(wù)[2]、口語對話管理[3]、服務(wù)漂移[4]、傳感器調(diào)度[5]等.

精確求解POMDP問題計算復(fù)雜度過高,難以應(yīng)用于實際問題,因此出現(xiàn)了各種近似算法如FIB[6]、MA-Q-learning[7]等等.其中基于點的值迭代方法在可達信念點集上進行迭代,通過增加迭代次數(shù)提升了整體效率,使得POMDP可以應(yīng)用到較大規(guī)模的問題并在實際應(yīng)用中取得了良好的效果.自從基于點的值迭代方法PBVI[8]提出之后,對探索信念點集的啟發(fā)式探索方法成為了研究熱點.PEMA[9]算法選取誤差最大的后繼點,使點迭代盡可能近似精確迭代;HSVI[10]、SARSOP[11]、GapMin[12]、PGVI[13]等算法根據(jù)最優(yōu)值函數(shù)上界來選擇最優(yōu)動作探索最優(yōu)可達信念點集,保證收斂到全局最優(yōu);AEMS[14]、HHOP[15]等算法構(gòu)造啟發(fā)式函數(shù)選擇最優(yōu)動作探索最優(yōu)可達信念點集,提高了收斂效率.

為了解決較大規(guī)模的POMDP問題,近年來基于點的算法通過探索最優(yōu)可達信念空間來提高算法的效率.為了保證值函數(shù)能夠收斂到全局最優(yōu)解,HSVI等算法在探索最優(yōu)可達信念空間時,根據(jù)IE-MAX[16]原則選取值函數(shù)上界最大的動作.但值函數(shù)的上界通過線性規(guī)劃等方法來計算,其收斂效率很低,而值函數(shù)下界基于貝爾曼方程進行迭代收斂效率較高.HSVI等算法雖然可以在理論上保證收斂,但在選擇最優(yōu)動作時僅以值函數(shù)上界為參照而完全不考慮值函數(shù)下界的取值情況,降低了值函數(shù)下界的迭代收斂效率,從而影響了算法的整體收斂效率.為保證高效地探索到全局最優(yōu)解,HHOP算法設(shè)計了有前景的策略再結(jié)合最優(yōu)值函數(shù)上界構(gòu)造了兩個獨立的啟發(fā)式搜索函數(shù)進行雜合以探索最優(yōu)可達信念空間.本文提出基于最優(yōu)策略概率的值迭代算法(Probability-based Value Iteration on Optimal Policy,PBVIOP)來提高全局最優(yōu)解的收斂效率.在探索最優(yōu)可達信念空間時,PBVIOP算法和HHOP算法一樣都考慮了值函數(shù)的上界和下界,不同之處在于HHOP算法在每次探索時是把有前景的策略和值函數(shù)上界分隔開來各自考慮后再雜合;而PBVIOP算法在每次探索時先結(jié)合動作值函數(shù)的上界和下界來探索最優(yōu)策略,再貪婪探索其不確定性最大的后繼信念點,相比之下HHOP算法更為細致復(fù)雜.PBVIOP算法在探索最優(yōu)可達信念空間方面有如下特點:首先,在尋找最優(yōu)策略的過程中同時參考動作值函數(shù)的上界和下界,保證算法的收斂質(zhì)量和效率;其次,把選擇最優(yōu)動作建模成基于各個動作值函數(shù)的分布求最大值函數(shù)的問題,以各個動作值函數(shù)最大的概率作為選擇最優(yōu)動作的標準,保證了算法的可靠性和穩(wěn)定性;最后,引入蒙特卡羅方法來近似計算動作最優(yōu)的概率,使得算法合理且高效.算法在選擇最優(yōu)動作時避免了局部化的干擾,可以穩(wěn)定達到全局最優(yōu).試驗結(jié)果表明PBVIOP算法優(yōu)于HSVI和GapMin算法的性能,且隨著POMDP問題規(guī)模的擴大其優(yōu)勢愈加顯著.

2　背景和相關(guān)工作

2.1POMDP模型

POMDP模型可以表示為一個八元組(S,A,Z,b0,T,O,R,γ)[8].其中S是一個隱含狀態(tài)的有限集合,表示了系統(tǒng)所有可能處于的狀態(tài);A是一個動作的有限集合,包括Agent能夠采取的所有動作;Z是一個觀察的有限集合,表示Agent所有可能的輸入;b0是初始的狀態(tài)分布,表示在初始時刻t0系統(tǒng)在狀態(tài)集合S上的概率分布;T(s,a,s′)是狀態(tài)到狀態(tài)的轉(zhuǎn)移概率,描述Agent在狀態(tài)s采取動作a后到達狀態(tài)s′的概率,表明了動作的隨機效應(yīng);O(a,s′,z)是Agent采取動作a到達狀態(tài)s′后且觀察到z的概率,模擬了Agent部分可觀測的特性;R(s,a)是在狀態(tài)s時采取動作a所獲得的回報值;γ∈(0,1)γ∈(0,1)是折扣因子.

在POMDP中,Agent不能直接獲取自己的狀態(tài)而只能從環(huán)境中獲得觀察信息作為狀態(tài)的參照,所以它必須根據(jù)動作和觀測的歷史序列{a0,z1,a1,z2,a2,z3,…,at-1,zt}來決策下一個動作at.因此POMDP引入維持歷史信息的充分統(tǒng)計量b來代替歷史序列以計算其長遠回報[17].b是一個代表狀態(tài)上概率分布的向量:

bt(s)=P(st=s|zt,at-1,…,a0)

在POMDP中t時刻的信念點bt可以根據(jù)貝葉斯規(guī)則來更新,只涉及前一步的信念狀態(tài)bt-1,最近采取的動作at-1和得到的觀測zt,因而b的更新具有Markov性.

bt(s′)=τ(bt-1,at-1,zt)

2.2POMDP求解

POMDP中的策略是一個由信念到動作的映射:π(b)→a.Agent在策略π下的長遠回報為:

POMDP的求解是指POMDP模型完全已知(狀態(tài)集合、動作集合、轉(zhuǎn)移函數(shù)、回報函數(shù)等)的情況下計算最優(yōu)策略π*,它能夠最大化長遠回報的期望.最優(yōu)策略可以由貝爾曼方程迭代獲得.Q值函數(shù)Qt+1(b,a)是t步視野內(nèi)在當前信念點b處執(zhí)行動作a的回報值:

其對應(yīng)的最優(yōu)策略可以表示為:

再將這些集合與一步回報集合笛卡爾和相加得到某一動作a所對應(yīng)的向量:

其中笛卡爾和⊕定義為:

最后得到所有動作向量集合:

反復(fù)update至Гn收斂即可精確求解POMDP問題.每次update的計算復(fù)雜度近似為O(|S|2|A||Гt||Z|)[17],因而精確求解存在著歷史災(zāi)和維度災(zāi)的問題.雖然Witness算法和增量裁剪算法等對精確算法有所改進,但在極端情況下計算復(fù)雜度還是不能降低.

2.3基于點的POMDP近似求解

對于大部分的POMDP問題,Agent所能到達的信念點集合B往往只是信念空間的一小部分,因此可以用基于點的算法來求得其誤差在一定范圍之內(nèi)的近似解,避免精確求解中計算笛卡爾和的巨大計算量,通過增加迭代次數(shù)保證算法效果.

基于點進行backup和精確算法的update的比較如圖1所示.精確求解算法在整個信念空間上進行,所以無法先行確定動作a之后各個觀察下的最優(yōu)向量,只能選取所有可能的向量作笛卡爾和,因而計算量很大.基于點的方法中,執(zhí)行動作a之后的每個觀察下的最優(yōu)向量都可以先行確定,從而可以根據(jù)|Z|個觀察所對應(yīng)的最優(yōu)向量計算出執(zhí)行動作a的回報值,再比較得出回報值最高的最優(yōu)動作,最后通過backup操作得到b在一次更新后的最優(yōu)向量.

在點集B上由Гt構(gòu)建Гt+1過程如下:

在點集B上進行一次backup的計算復(fù)雜度近似為O(|S|2|A||Z‖B|2).基于點的方法在達到終止條件之前反復(fù)執(zhí)行兩個步驟:探索新的信念點來擴張信念點集合B;在B上更新值函數(shù)Γ.各種基于點的值迭代方法的主要差別在于不同的信念點集探索方法[18].

2.4最優(yōu)策略下的可達區(qū)域

基于點的算法的核心思想是可到達區(qū)域的概念.可到達區(qū)域R(b0)是從初始信念點b0經(jīng)過任意動作和觀察序列能夠到達的信念點集合[8].但第t步時R(b0)中增加信念點的數(shù)量級為(|A‖Z|)t,隨著步數(shù)t的增加R(b0)的規(guī)模也較為可觀.R*(b0)是從b0開始按照最優(yōu)策略所到達信念點的集合[19],第t步時R*(b0)中增加信念點的數(shù)量級為|Z|t.如圖2所示,R*(b0)的規(guī)模遠小于R(b0),因而在較大規(guī)模的問題中基于R*(b0)采樣更加高效.

盡管R*(b0)規(guī)模相對較小,但足以用于計算出b0處的最優(yōu)策略[19].然而最優(yōu)策略無法預(yù)知,所以一般通過啟發(fā)式的方法來對R*(b0)進行近似.

已有的基于點的近似算法在探索R*(b0)時嘗試了不同的選擇最優(yōu)動作的標準.如圖3所示,信念點b處有3個可供選擇的動作a1、a2、a3,其動作值函數(shù)Q(b,ai)分別在各自的下界和上界之間取值.在此例中PEMA等算法根據(jù)動作值函數(shù)下界的最大值會選取動作a1作為最優(yōu)策略;HSVI等算法根據(jù)動作值函數(shù)上界選擇動作a2作為最優(yōu)策略.

3　PBVIOP算法

3.1算法思想

目前已有的R*(b0)近似算法仍有改進的空間.PEMA算法僅根據(jù)值函數(shù)下界選取最優(yōu)動作,則值函數(shù)下界取值較高的信念點更可能會被探索到,然后在該點上的backup操作又只會使得該點附近區(qū)域的值函數(shù)下界會有所提升而其他信念區(qū)域的值函數(shù)下界幾乎沒有提升,從而在下一次的探索中該點附近區(qū)域的信念點又會被優(yōu)先探索到,因此算法不能保證值函數(shù)收斂到全局最優(yōu)解.HSVI等算法根據(jù)IE-MAX原則只根據(jù)值函數(shù)上界值最大來選擇動作,上界在更新中不斷降低,因而即使在某次迭代中只是找到了次優(yōu)動作也不會影響值函數(shù)最終能夠收斂到全局最優(yōu).但值函數(shù)的上界通過線性規(guī)劃或sawtooth算法[10]來近似計算,其收斂速度非常緩慢,HSVI等算法雖然在理論上保證收斂,但在選擇最優(yōu)動作時完全不考慮迭代收斂效率較高的值函數(shù)下界,影響了整個算法的收斂效率,不利其應(yīng)用于大規(guī)模的POMDP問題.

事實上動作值函數(shù)在上界和下界之間取值,單單以上界或下界的值來評估動作值函數(shù)都是片面的.在圖3的示例中,以Q(b,ai)的上界和下界為端點的整個線段反映了Q(b,ai)的取值情況,僅僅以線段的上端點或下端點來評價Q(b,ai)顯然不夠全面.事實上就整個線段比較而言,在圖3的示例中可能選擇a3作為最優(yōu)動作更為合理,盡管Q(b,a3)的上界和下界都不是最大值,但是Q(b,a3)值最大的概率可能最大.

本文提出了選擇最優(yōu)動作的新標準:以所有動作的函數(shù)值在其上界和下界之間的概率分布為基礎(chǔ),計算每個動作的值函數(shù)取值最大的概率,再選擇概率值最大的動作.基于新標準選擇動作更加合理,可以更準確地探索到R*(b0)附近的區(qū)域,從而提高迭代效率.

3.2基于蒙特卡羅的概率計算

p(y)=p(x1,x2,…,xn)

其中y是一個n維向量:y=(x1,x2,…,xn)滿足∮Ωp(x1,x2,…,xn)dx1dx2…dxn=1.其中

則動作ai的值函數(shù)的取值xi最大的概率為:

F*(ai)=P(xi>xj,?j≠i)

=∮Ωip(x1,…,xn)dx1…dxn

Ωi=Ω∩{(x1,x2,…,xn)|xi>xj,?j≠i}

由于Ωi是n維空間的一個封閉區(qū)域,F*(ai)的計算涉及高維積分.隨著維數(shù)n的增加,計算難度和復(fù)雜度將大大增加,本文通過蒙特卡羅法來求其近似值.

證明:構(gòu)造兩個函數(shù)Qi(y)和Fi(y):

則:F*(ai)=∮ΩQi(y)dy=∮ΩFi(y)p(y)dy

由此F*(ai)即隨機變量Fi(y)的數(shù)學期望值,由于y1,y2,…,ym為Ω上按概率密度p(y)選取的隨機樣點,可求Fi(y)的數(shù)學期望近似值.

本文參照AEMS1算法[14]假定動作的最優(yōu)值函數(shù)在上下界之間均勻分布,對動作值函數(shù)進行取樣,并由此計算動作最優(yōu)的概率.

3.3PBVIOP算法

PBVIOP算法(算法1)初始化值函數(shù)的上下界之后,反復(fù)調(diào)用子函數(shù)PBVIOPExplore從b0出發(fā)進行深度探索并更新值函數(shù)的上界和下界,直至b0處取值收斂為止.

PBVIOP算法在選擇最優(yōu)動作時同時考慮了最優(yōu)動作值函數(shù)的上界和下界.在迭代過程中下界持續(xù)上升而上界會持續(xù)下降,隨著值函數(shù)上下界之差逐漸縮小,對各個動作最優(yōu)概率的估算會更加精確,因而保證了值函數(shù)的收斂.因為算法同時更新值函數(shù)的上界和下界,并以值函數(shù)在上界和下界之間的分布來計算動作最優(yōu)的概率,所以在信念點上更新值函數(shù)的上界和下界不會增加該點以后被探索到的可能性,故而算法會收斂到全局最優(yōu)解.

4　實驗

4.1實驗設(shè)置

本文實驗對比了PBVIOP算法、HSVI算法和GapMin算法運算情況,因為PBVIOP算法和HSVI算法的主要差別在于最優(yōu)動作的選擇,而GapMin算法是目前最高效的POMDP規(guī)劃算法之一.本文在常見4個數(shù)據(jù)集上進行實驗,其中Tiger、Hallway是早期的經(jīng)典迷宮問題;RockSample模擬了Agent采樣礦石的科學考察任務(wù),是一個可擴展的問題[10].實驗所用數(shù)據(jù)集的狀態(tài)、動作和觀察規(guī)模如下表:

表1　POMDP標準數(shù)據(jù)集的規(guī)模

本文實驗中復(fù)用了GuyShani教授提供的POMDPSolver部分代碼.對每個問題設(shè)定折扣因子為0.95,分別用PBVIOP算法、HSVI算法和GapMin算法各做10次運算,再對10次運算的結(jié)果取平均值,選取運算時間和平均折扣回報值(AverageDiscountedReward,ADR)作為評價指標.平均折扣回報值表示了生成策略的質(zhì)量,由生成的策略模擬運行100步計算得出折扣回報值,通過反復(fù)500次的模擬來計算平均折扣回報值.

4.2實驗結(jié)果分析

實驗結(jié)果如表2所示,可見大多數(shù)情況下PBVIOP算法有較好的收斂效果.

圖4是HSVI、GapMin和PBVIOP在四個問題上實驗結(jié)果的詳細對比,表示了生成策略的平均折扣回報值的演變情況.圖中橫坐標為算法運行時間(s),縱坐標為ADR值;實線表示HSVI算法對應(yīng)的結(jié)果,短劃線表示GapMin算法對應(yīng)的結(jié)果,圓點線表示PBVIOP算法對應(yīng)的結(jié)果.

表2　實驗結(jié)果數(shù)據(jù)

在求解Hallway和Tiger-grid問題的實驗中,因為問題規(guī)模較小,PBVIOP算法和HSVI算法收斂到相同的ADR,GapMin算法的ADR略高一點.而PBVIOP算法的收斂效率明顯較高,在Hallway問題求解中比HSVI算法快3.15倍,比GapMin算法快4.51倍;在Tiger-grid問題求解中比HSVI算法快1.36倍,比GapMin算法快4.96倍.

在求解RockSample(5,5)問題的實驗中,PBVIOP算法收斂到的ADR比HSVI算法高出較多,收斂效率比HSVI算法快5.86倍.PBVIOP算法收斂到的ADR略低于GapMin算法,但其收斂效率比GapMin算法快157.06倍.

在求解RockSample(7,8)問題的實驗中,PBVIOP算法和GapMin算法收斂到的ADR都比HSVI算法高出較多,且PBVIOP算法收斂到的ADR比GapMin算法略高.PBVIOP算法收斂效率比HSVI算法快1.54倍,比GapMin算法快1.66倍.

雖然GapMin算法和HSVI算法一樣選擇值函數(shù)上界最優(yōu)的動作,但GapMin算法在每輪迭代中會探索所有Gap大于當前閾值的信念點,因而GapMin算法可以更加有效地降低上界值,在狀態(tài)規(guī)模不太大的POMDP問題上找到全局最優(yōu)解.但隨著POMDP問題中狀態(tài)數(shù)的增加,上界的下降效果變差,GapMin算法也難以有效地求解POMDP問題.另外由于GapMin算法多探索了許多信念點,其收斂效率受到較大影響.

實驗結(jié)果表明PBVIOP算法比HSVI和GapMin算法有更高的收斂效率,并且隨著POMDP問題規(guī)模的增加,其收斂到的ADR也會明顯地優(yōu)于HSVI算法,和GapMin算法相當.隨著狀態(tài)數(shù)目的增加,上界的下降速度會顯著降低,因而HSVI和GapMin算法的收斂效率直接受到了影響.另一方面,隨著動作數(shù)量的增加,PBVIOP算法探索的R*(b0)和HSVI算法探索的R*(b0)會有更大的差異,因而PBVIOP算法的效果會更優(yōu)于HSVI算法.這說明與單純利用上界相比而言,同時利用上下界能夠更快更優(yōu)地探索到R*(b0)附近的區(qū)域,對于算法性能和收斂質(zhì)量的提升有很大的幫助.

5　結(jié)束語

本文提出了一種基于概率的最優(yōu)策略值迭代方法PBVIOP,解決了啟發(fā)式探索最優(yōu)策略可達區(qū)域R*(b0)時需要保障值函數(shù)上下界收斂效率的問題.PBVIOP算法與現(xiàn)有基于點的值迭代算法不同之處在于使用一種有效的新方法來探索最優(yōu)策略可達區(qū)域R*(b0).PBVIOP算法同時維持值函數(shù)的上界和下界,在啟發(fā)式的深度探索中,用蒙特卡羅法估算各個動作值函數(shù)最優(yōu)的概率,選擇概率最大的動作為最優(yōu)策略,再貪婪探索不確定性最大的后繼信念點.實驗結(jié)果表明,與HSVI和GapMin算法相比,PBVIOP算法在基準數(shù)據(jù)集上有更高的收斂效率并能夠獲得較優(yōu)的策略.未來的工作一方面是在APPL平臺上實現(xiàn)本算法,完善實驗配置,嘗試和HHOP等算法進行比較分析以完善本算法;另一方面是進一步優(yōu)化值函數(shù)的概率分布模型和后繼信念點的選擇標準,并嘗試每步探索多個有效的信念點來近似最優(yōu)策略可達區(qū)域,從而進一步提高一次深度探索的效率.

[1]S Russell,PNorvig.Artificial Intelligence:A Modern Approach[M].Prentice-Hall,1995.

[2]T Smith.Probabilistic planning for robotic exploration[D].Massachusetts Institute of Technology,2007.

[3]J D Williams,S Young.Partially observable Markov decision processes for spoken dialog systems[J].Computer Speech & Language,Elsevier,2007,21(2):393-422.

[4]趙二虎,陽小龍,等.CPSM:一種增強IP網(wǎng)絡(luò)生存性的客戶端主動服務(wù)漂移模型[J].電子學報,2010,38(9):2134-2139.

Zhao Er-hu,Yang Xiao-long,et al.CPSM:Client-side proactive service migration model for enhancing IP network survivability[J].Acta Electronica Sinica,2010,38(9):2134-2139.(in Chinese)

[5]張子寧,單甘霖,段修生.基于部分可觀馬氏決策過程的多平臺主被動傳感器調(diào)度[J].電子學報,2014,42 (10):2104-2109.

Zhang Zi-ning,Shan Gan-lin,Duan Xiu-sheng.POMDP-based scheduling of active/passive sensors in multi-platform[J].Acta Electronica Sinica,2014,42(10):2104-2109.(in Chinese)

[6]M Hauskrecht.Value-function approximations for partially observable Markov decision processes[J].Journal of Artificial Intelligence Research,2000,13(1):33-94.

[7]劉海濤,洪炳熔,等.不確定性環(huán)境下基于進化算法的強化學習[J].電子學報,2006,34 (7):1356-1360.

Liu Hai-tao,Hong Bing-rong,et al.Evolutionary algorithm based reinforcement learning in the uncertain environments[J].Acta Electronica Sinica,2006,34(7):1356-1360.(in Chinese)

[8]Pineau J,Gordon G,Thrun S.Point-based value iteration:An anytime algorithm for POMDPs[A].International Joint Conference on Artificial Intelligence[C].Acapulco,Mexico:Morgan Kaufmann,2003.1025-1032.

[9]J Pineau,G Gordon.POMDP planning for robust robot control[A].International Symposium on Robotics Research[C].San Francisco,USA:Springer,2005,69-82.

[10]T Smith,R G Simmons.Point-based POMDP algorithms:Improved analysis and implementation[A].Conference on Uncertainty in Artificial Intelligence[C].Edinburgh,United kingdom:AUAI Press,2005,542-547.

[11]H Kurniawati,D Hsu,W S Lee.SARSOP:Efficient point-based POMDP planning by approximating optimally reachable belief spaces[A].Robotics:Science and Systems[C].Zurich,Switzerland:MIT Press,2008,65-72.

[12]P Poupart,K E Kim,D Kim.Closing the gap:Improved bounds on optimal POMDP solutions[A].International Conference on Planning and Scheduling[C].Freiburg,Germany:AAAI Press,2011.194-201.

[13]Z Zhang,D Hsu,W S Lee.Covering Number for Efficient Heuristic-based POMDP Planning[A].International Conference on Machine Learning[C].Beijing,China:International Machine Learning Society,2014.48-60.

[14]S Ross,B Chaib-Draa.AEMS:An anytime online search algorithm for approximate policy refinement in large POMDPs[A].International Joint Conference on Artificial Intelligence[C].Hyderabad,India:Morgan Kaufmann,2007.2592-2598.

[15]章宗長,陳小平.雜合啟發(fā)式在線POMDP規(guī)劃[J].軟件學報,2013,24(7):1589-1600.

Zhang Zong-zhang,Chen Xiao-ping.Hybrid heuristic online planning for POMDPs[J].Journal of Software,2013,24(7):1589-1600.(in Chinese)

[16]L P Kaelbling.Learning in Embedded Systems[M].MIT Press,1993.

[17]R D Smallwood,E J Sondik.The optimal control of partially observable markov processes over a finite horizon[J].Operations Research,1973,21(5):1071-1088.

[18]G Shani,J Pineau,R Kaplow.A survey of point-based POMDP solvers[J].Autonomous Agents and Multi-Agent Systems,2013,27(1):1-51.

[19]D Hsu,W S Lee,N Rong.What makes some POMDP problems easy to approximate?[A].Advances in Neural Information Processing Systems[C].Vancouver,BC,Canada:Curran Associates Inc,2007.689-696.

劉峰男,1976年生于江蘇泰州.南京大學軟件學院講師.研究方向為強化學習、智能規(guī)劃.

E-mail:ufeng-nju@163.com

王崇駿男,1975年生于江蘇盱眙,南京大學計算機科學與技術(shù)系教授,中國計算機學會高級會員.研究方向為Agent及多Agent系統(tǒng)、 復(fù)雜網(wǎng)絡(luò)分析及智能應(yīng)用系統(tǒng).

駱斌男,1967年生,南京大學軟件學院教授,博士生導(dǎo)師,中國計算機學會杰出會員.研究方向為軟件工程、人工智能.

A Probability-Based Value Iteration on Optimal Policy Algorithm for POMDP

LIU Feng1,3,WANG Chong-jun2,3,LUO Bin1,3

(1.SoftwareInstitute,NanjingUniversity,Nanjing,Jiangsu210093,China;2.DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing,Jiangsu210093,China;3.NationalKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,Nanjing,Jiangsu210093,China)

With the enlargement of the scale of POMDP problems in applications,the research of heuristic methods for reachable area based on the optimal policy becomes current hotspot.However,the standard of existing algorithms about choosing the best action is not perfect enough thus the efficiency of the algorithms is affected.This paper proposes a new value iteration method PBVIOP (Probability-based Value Iteration on Optimal Policy).In depth-first heuristic exploration,this method uses the Monte Carlo algorithm to calculate the probability of each optimal action according to the distribution of each action′s Q function value between its upper and lower bounds,and chooses the maximum probability action.Experiment results of four benchmarks show that PBVIOP algorithm can obtain global optimal solution and significantly improve the convergence efficiency.

partially observable Markov decision process (POMDP);probability-based value iteration on optimal policy(PBVIOP);Monte Carlo method

2014-09-15;

2015-03-19；責任編輯：藍紅杰

國家自然科學基金(No.61375069);江蘇省自然科學基金(No.BK20131277)

TP319

A

0372-2112 (2016)05-1078-07

電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.010