課程資源人工智能AI有時(shí)也稱機(jī)器定義為

第一章緒引(inligentagent)的研究與設(shè)計(jì)”[Pooleetal.,1998]，是研究、開發(fā)用于機(jī)器人學(xué)當(dāng)中，并且對(duì)AI技術(shù)本身的魯棒性和可伸縮性提出了更高的要求。智能是指一個(gè)可以觀察周遭環(huán)境并做出行動(dòng)以達(dá)致目標(biāo)的系統(tǒng)（序貫決策(SequentialDecisionMaking)[Littman,1998]是規(guī)劃中的一個(gè)子領(lǐng)域。在序貫決策中，智能以下稱agent）通過不斷的與環(huán)境進(jìn)行交互，并通過一系列的決策來實(shí)現(xiàn)某個(gè)規(guī)劃目標(biāo)。當(dāng)agent面對(duì)的周遭環(huán)境決策過程(MarkovDecisionProcesses，MDPs)提供了良好的解決方案。但真作為MDPs的推廣，部分可觀測(cè)馬爾可夫過程(PartiallyObservableMarkovDecisionProcesses，POMDPs)[Astrom,1965]被用于解決不確定環(huán)境下的決策問題。但POMDPs的精確計(jì)算是一個(gè)NP-Hard問題，所以如何從性能和（效果上綜合提高POMDPs計(jì)算，是該領(lǐng)域研究的熱點(diǎn)和難點(diǎn)研究現(xiàn)AI規(guī)劃是從早期的控制理論和搜索算法中延伸出來的，具體來說是早期的機(jī)器人科學(xué)、任務(wù)計(jì)劃等領(lǐng)域?qū)χ悄芗夹g(shù)的需求[Russelletal.,2009]?；谶壿嫚顟B(tài)的規(guī)劃[Fikesetal.,1971]，到基于偏序關(guān)系[Penberthyetal.,1992]，以及規(guī)劃圖[Blumetal.,1995]、決策表[Clarkeetal.,1987]的出現(xiàn)，作為MDP的擴(kuò)展，同樣使用動(dòng)態(tài)規(guī)劃方法來求解。在最優(yōu)策略的求解中，需要考慮當(dāng)前收益和長(zhǎng)遠(yuǎn)收益的權(quán)衡，MDP是獲知自身狀態(tài)，在此基礎(chǔ)上，MDP問題可以通過Markov性質(zhì)進(jìn)行求解。但在實(shí)際應(yīng)用場(chǎng)景中，agent狀態(tài)是不確定的，而且agent本身要通過搜周圍的信息來確定當(dāng)前狀態(tài)或狀態(tài)的部分信息。于是POMDP模型被提[Astrom,1965]Sondik在他的博士中提出了POMDP的第一個(gè)精確算法One-Pass算法[Sondik,1971]。他證明了值函數(shù)在信念狀態(tài)空間上的分段線性凸(piece-wisedlinearconvex，PWLC)性質(zhì)，這個(gè)性質(zhì)是后來所有精確算法以及相關(guān)啟發(fā)式近似算法的理論基礎(chǔ)。Monohan的枚舉算One-Pass算法的基礎(chǔ)上，提出了一個(gè)最簡(jiǎn)單的解決框架[Monohan1982]。之后出現(xiàn)了對(duì)One-Pass進(jìn)行改良的線性支持算法(Linearsupportalgorithm)[Cheng1988]。Witness算法[Cassandraetal1994]和IncrementalPruning算法[Cassandraetal.,1994，Cassandraetal.,1997]分別從添加有效向量和裁剪無用向量的角于是出現(xiàn)了不同的近似算法MDP算法[Nourbakhshetal1995，Littmanetal.,1995b，Hauskrecht,2000]通過將POMDP問題MDP化，降低了計(jì)算似計(jì)算[Bonet,2002，Zhouetal.,2001，Rossetal.,2008]的思想，基于點(diǎn)的近似算法被提出[Pineauetal2003，Spaanetal2005，Pineauetal2005，Smithetal.,2004，Smithetal.,2005，Shanietal.,2007，Kurniawatietal.,這樣的方法使得實(shí)際場(chǎng)景中的POMDP問題變得可解，且具備處理大規(guī)模這些精確算法和其他相關(guān)的近似算法均是基于值函數(shù)迭代計(jì)算的，POMDP的求解的另一個(gè)思路是直接使用策略迭代的方法Sondik最早提出的策略迭代方法[Sondik1978]期望通過最優(yōu)動(dòng)作將整個(gè)信念空間進(jìn)行劃分，但終因表示的和復(fù)雜的迭代無法使用。Hansen[Hansen,1997，Hansen,1998a]提出了可用的策略迭代方案，通過FSC來表示值函數(shù)向量、動(dòng)作以隨著POMDP求解研究的不斷發(fā)運(yùn)用POMDP解決實(shí)際問題的相關(guān)POMDP本文工本文對(duì)POMDP模型和出現(xiàn)的基于值迭代的精確算法做了詳細(xì)介紹，了本人PIPBVI算法和PBHSPI算法，并進(jìn)行了實(shí)驗(yàn)對(duì)比和分析。概MDP模型和POMDP模型介紹POMDP模型中信念狀態(tài)和基于PWLC性質(zhì)的值迭代POMDP精確算法介紹POMDP基于點(diǎn)的近似算法介紹POMDP策略迭代和PBPI算法介紹提出PIPBVI算法，并通過實(shí)驗(yàn)進(jìn)行驗(yàn)證和分析提出PBHSPI算法，并通過實(shí)驗(yàn)進(jìn)行驗(yàn)證和分析文章結(jié)第一章介紹POMDP模型研究的背景和當(dāng)前國內(nèi)外的研究情況，以及第二章在介紹COMDP模型的基礎(chǔ)上，引出POMDP模型對(duì)先后出現(xiàn)第三章介紹基于點(diǎn)的近似算法PIPBVI算法，通過在第四章介紹了策略迭代算法以及將其運(yùn)PBVIPBPI算法。提出了基于點(diǎn)的啟發(fā)式策略迭代方法PBHSPI。通過在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并且對(duì)比已有的單純基于點(diǎn)的啟發(fā)式方法HSVIFSVI對(duì)算法的性能以及最后的策略質(zhì)量進(jìn)行了驗(yàn)得出該算法是在綜合效果上介于HSVIFSVI第五章對(duì)研究進(jìn)行了總結(jié)，并且提出展望和后續(xù)改進(jìn)的可能第二章POMDP介引序貫決策問題需要在系統(tǒng)的整個(gè)生命周期中作決策M(jìn)DP是解決序貫本章首先介紹MDP模型和其求解，然后過渡到POMDP模型的介紹。POMDP作為不確定環(huán)境下決策問題的解決模型，在對(duì)MDP模型擴(kuò)展的基礎(chǔ)上其求解過程也相對(duì)本章在模型定義描述的基礎(chǔ)上對(duì)POMDP問MDP模模型定理解為上文提到的aet而系統(tǒng)便是決策者決策的環(huán)境首先決策（即作決策個(gè)特殊情況序貫決策是在系統(tǒng)的整個(gè)生命周期互并作決策所以考慮及時(shí)收益和長(zhǎng)期收益，并通過一定的方法做出權(quán)衡。1994，Bertsekas,1995]，也就是說行動(dòng)的選擇有著固定的時(shí)間點(diǎn)。狀態(tài)是通常用一個(gè)五元組(S,A,τ,R,γ)來定義一個(gè)狀態(tài)(State)，S={s0s1sn}agent所有可能狀態(tài)的有限集合。在時(shí)間t，agent所處狀態(tài)記為????MDP中，狀態(tài)是agent在做決策時(shí)所需動(dòng)作Acton)A={a0,1,…,am是aet能夠執(zhí)行的所有可能動(dòng)作的轉(zhuǎn)移函數(shù)(TransitionFunction)，狀態(tài)到狀態(tài)的轉(zhuǎn)移通過執(zhí)行某個(gè)動(dòng)作來完成，將這個(gè)過程定義成轉(zhuǎn)移函數(shù)τ:SA→∏(S)，表示狀態(tài)-動(dòng)作的笛??(??,??,??′)=??(????+1=??′|????=??,????=??),???∈-其中，st時(shí)刻agent的狀態(tài)，aagentt時(shí)刻采取的行動(dòng)，??′t+1時(shí)刻的狀態(tài)，即在時(shí)刻t系統(tǒng)狀態(tài)s，執(zhí)行動(dòng)作a后，系統(tǒng)狀態(tài)轉(zhuǎn)移到??′。轉(zhuǎn)移函數(shù)定義了在當(dāng)前的狀態(tài)-動(dòng)作下，下一個(gè)狀態(tài)的概率分??(????+1=??′|????,????,?????1,?????1,…,??0,??0)=??(????+1=??′|????,=??(??2=??′|??1,所以滿足以下性質(zhì)：∑s′∈Sτ(s,a,s′)=1。收益(Reward)。模型中收益同時(shí)包含了正收益和負(fù)收益，可以理解執(zhí)行某個(gè)動(dòng)作的獎(jiǎng)賞和成本。MDP中使用直接獎(jiǎng)賞函數(shù)RSA→??，表示狀態(tài)-動(dòng)作的笛積到實(shí)數(shù)集的映射。R(s,a)是在狀態(tài)s時(shí)執(zhí)行動(dòng)作a所獲得的直接收益。而現(xiàn)實(shí)中使用RS×A×S→??，其中R′(sas′)表示當(dāng)前狀態(tài)為s，執(zhí)行動(dòng)作a且系統(tǒng)狀態(tài)轉(zhuǎn)為s′時(shí)所獲得的收益。使用后一??(??,??)=∑??(??,??,??′)??′(??,??,-折扣(Discount)，定義γ∈[0,1)作為折扣因子。決策需要優(yōu)化的標(biāo)準(zhǔn)，∑∑

R(st,at)最大。但該值可能無法收斂?？紤]到現(xiàn)實(shí)場(chǎng)景中，越早執(zhí)行動(dòng)作對(duì)整個(gè)過程越有意義所以MDP引入了折扣因子當(dāng)前時(shí)刻之后的收益進(jìn)行折扣累積，于是得到如下的收益函數(shù)（假設(shè)起始時(shí)刻為0??0=??(??0,??0)+=??(??0,??0)+??[??(??1,??1)+..∞=∑??????(????,-由此可見折扣因子的存在使得agent在決策時(shí)地關(guān)注立即收益，弱化時(shí)間偏后的決策收益。并且，γ越接近0，立即收益的影響便越大，反累積獎(jiǎng)賞，可復(fù)用公式二-3，只需將無窮符號(hào)換成時(shí)間長(zhǎng)度常數(shù)。始狀態(tài)概率分布μ0(s)=P(s0=s)，滿足∑s∈Sμ0(s)=1。，至此完整的MDP模型定義結(jié)束為區(qū)別于后面將要提到的部分可觀察馬爾可夫決策過程(POMDPs)這個(gè)模型完整定義為完全可觀察馬爾可夫決策過程(CompleyObservableMarkovDecisionProcesses，，以下介紹COMDP的求解過策由于agent無法預(yù)知將來的狀態(tài)，所以在做決策時(shí)，需要依據(jù)已有決策過程，即歷史信息?。?包含了系統(tǒng)的初始狀態(tài)，以及之后的所有狀態(tài)和動(dòng)作，?={skak|k=0,1,t1}，其中t為當(dāng)前決策時(shí)刻。對(duì)于有需要依據(jù)當(dāng)前狀態(tài)st做決策[Puterman,1994]。????來表示時(shí)刻t時(shí)的決策，它是一個(gè)狀態(tài)到動(dòng)作集合的映射，dtS→Adt(sa)=P(at=a|st=s)，其中∑a∈Adt(sa)=1,?s∈S?t∈列決策的集合，πd0,d1,…,dT?1)，其中????表示時(shí)刻tagent的決策。我們期望最優(yōu)化策略π，并且用最優(yōu)化的過程來求解COMDP問題。策略分為固定策略和不固定策略。在一個(gè)COMDP模型中，如果每個(gè)時(shí)刻t做決策的規(guī)則是固定的，即為固定策略，一般用于無限步?jīng)Q策模型COMDP模型，在任意初始狀態(tài)s0條件下，總存在一個(gè)最優(yōu)策略π?使得長(zhǎng)期回報(bào)至少好于其他策略π[Bellman1975]外根據(jù)每一步?jīng)Q策規(guī)則對(duì)執(zhí)行有了策略的定義，便能agent在系統(tǒng)中的執(zhí)行過程值函agent的目標(biāo)是最大化策略的總收益，用期望折扣收益(expectedfuturediscountedreward)來表示[Cassandra,1998]：??∑??????(????,-T是結(jié)束時(shí)刻。也有其他的總收益衡量方法[Howardetal對(duì)于無限步?jīng)Q策模型，有如下公∞??∑??????(????,-對(duì)于一個(gè)COMDP模型，最優(yōu)的總收益可能是一定的，但獲得最優(yōu)總對(duì)于一個(gè)非固定策略長(zhǎng)度為T的有限步策略π，假設(shè)時(shí)刻t狀態(tài)為s，定義剩余T-t步時(shí)策略的值函數(shù)如下????(??,??)=??(??,????(??))+??∑??(??,????(??),??′)????+1(??,-開始時(shí)刻t=0，結(jié)束時(shí)刻t=T1，并且VT(πs)=0，運(yùn)用動(dòng)態(tài)規(guī)劃(DynamicProgramming，DP)，從t=T?1到t=0遞歸進(jìn)行計(jì)算，即自????(??,??)=??(??,????(??))+??∑??(??,????(??),??′)?????1(??,在公式-7中，對(duì)于所有的狀態(tài)s，V0(πs)=0

-.1對(duì)于無限步?jīng)Q策的COMDP模型，有固定策略下的值函數(shù)與之對(duì)應(yīng)??(??,??)=??(??,??(??))+??∑??(??,??(??),??′)??(??,-值迭通過從時(shí)刻T-1到0進(jìn)行自底向上的計(jì)算，動(dòng)態(tài)規(guī)劃提供了同時(shí)計(jì)算最優(yōu)總收益和最優(yōu)策略的途徑。使用公式二-7的表達(dá)方式，介紹最優(yōu)值函數(shù)的計(jì)算方法。使用動(dòng)態(tài)規(guī)劃的思想，假設(shè)需要計(jì)算n步策略的最優(yōu)值函數(shù)，當(dāng)n-1步對(duì)于所有狀態(tài)的最優(yōu)值函數(shù)已知，那么只需選擇當(dāng)前步???(??)=??????[??(??,??)+??∑??(??,??,

-n當(dāng)初始狀態(tài)為s，系統(tǒng)有n步?jīng)Q策時(shí)，V?(s)便是最優(yōu)策略π?下的最優(yōu)值函數(shù)。這個(gè)動(dòng)態(tài)規(guī)劃的計(jì)算過程便是值迭代過程。對(duì)公式-9進(jìn)一n???,??(??)=??(??,??)+??∑??(??,??, ???(??)=??????

-n在公式-10中，V?,a(s)表示在狀態(tài)sagent執(zhí)行動(dòng)作a，余下nnn-1步執(zhí)行對(duì)應(yīng)狀態(tài)??′下的最優(yōu)決策。稱V?,a(s)為Q函數(shù)。由此，可以得到最優(yōu)策略π?=(d?,d? ,…,d?)，其中d?(s)=argmaxV?,a(s)。n

對(duì)于無限步?jīng)Q策的COMDP模型，用類似于有限步模型求解過程的方???(??)=??????[??(??,??)+??∑??(??,??,-通過最優(yōu)值函數(shù)，得到最優(yōu)策略???(??)=????????????[??(??,??)+??∑??(??,??,

由公式二-12得到最終的固定策略π?=(ddd?)POMDP模

-模型定POMDP中，沿用COMDP的五元組(??????????)，并且添加另外兩個(gè)信息量ZO，構(gòu)成七元組(??,??,??,??,??,??,??)。觀察(Observation)，Z={z0z1zL}agent從環(huán)境中所有可能獲得觀察的有限集合。在每個(gè)時(shí)刻t，agent只可能獲得一個(gè)觀察zt。在POMDP中，觀察可以是續(xù)空間，但本文只涉及有限離散空間的情況。觀察函數(shù)(ObservationFunction)，觀察函數(shù)O是一個(gè)動(dòng)作-狀態(tài)積到觀察集概率分布的映射，O:A×S→∏(Z)。??(??,??,??)=??(????+1=??|????+1=??,????=-環(huán)境中得到觀察值z(mì)的概率。由于觀察函數(shù)是觀察集概率分布在????上的充分條件概率分布滿足以下性質(zhì)：∑z∈ZO(s,a,z)=1,?s,a。策M(jìn)DP的目標(biāo)就是尋找最優(yōu)策略。COMDP的馬爾可夫性質(zhì)決定了每一步?jīng)Q策的制定只依賴于當(dāng)前agent的狀態(tài)，而PODMP中在狀態(tài)本身無法準(zhǔn)確獲得的情況下，單純依賴于當(dāng)前狀態(tài)的方法明顯不適用。所以，可以根據(jù)POMDP的特性來制定策略。最簡(jiǎn)單的方法便是使用觀察到動(dòng)作的函數(shù)映射，π:O→A，但結(jié)果很糟糕[Jaakkolaetal.,1995，Littman,1994]；另外也有相關(guān)工作使用觀察到動(dòng)作的概率分布的映射，πO→∏(A)，效果同樣不理想[Jaakkolaetal.,1995]。這些研究結(jié)果證明，POMDP中策略的制定不能單純的依賴于基于觀察或有限的觀察歷史的馬做決策[WhiteⅢetal.,1994]，但結(jié)果被證明同樣是很糟糕的。為POMDP重新定義π:?→A。其中t時(shí)刻的歷時(shí)?t{a0,1,1,z2,…,at?1,zt[m,9]。由于aet只能獲得對(duì)環(huán)境的觀察?信念狀A(yù)gent需要根據(jù)歷史?來做決策，但歷史的在實(shí)際應(yīng)用中是的。使用一個(gè)新的統(tǒng)計(jì)量來替代系統(tǒng)歷史，即信念狀態(tài)b。信念狀態(tài)是?的一個(gè)充分統(tǒng)計(jì)量[Sondik,1971，Striebel,1965]，所以可以使用b來代替?統(tǒng)初始信念狀態(tài)為b0，定義時(shí)刻t時(shí)系統(tǒng)的信念狀態(tài)bt，其中：????(??)=??(????=??|???,-是續(xù)空間，是狀態(tài)空間S上的單形體，它的維度是|S|?1。在時(shí)刻t-1時(shí)刻的信念狀態(tài)b，動(dòng)作a和觀察z，已知的前提下，通過使用????(??′)=??(??′|??,??,??(??′,??,??, ??(??,??,??(??|??′,??,??)??(??′|??,??)??(??, ??(??|??,??)??(??,??(??|??′,??)??(??′|??, ??(??|??,??(??|??′,??)∑??∈????(??′|??,??,??)??(??|??,∑=∑

??(??|??′′,??)∑??∈????(??′′|??,??,??)??(??|??,??(??|??′,??)∑??∈????(??′|??,??)∑=∑

??(??|??′′,??)∑??∈????(??′′|??,??)其中，P(s|ba)=b(s)，P(s′|sa)=τ(sas′)，P(z|sa)=O(saz)。代入上式得到[Sondik,1971]：????(??′)

??(??′,??,??)∑??∈????(??,??,∑??′′∈????(??′′,??,??)∑??∈????(??,??,-有了信念狀態(tài)b，可以重新定義POMDP的策略：π:?S→A。在COMDP中，基于狀態(tài)s選擇動(dòng)作a；在POMDP中，根據(jù)信念狀態(tài)b選擇動(dòng)作a。由此，POMDP中的信念狀態(tài)便類似于COMDP中的狀態(tài)，所以可以將POMDP模型稱為信念狀態(tài)下的MDP(BeliefMDP，MDPBeliefKaelblingetal.,1998]為簡(jiǎn)單起見，定義在信念狀態(tài)b時(shí)，執(zhí)行動(dòng)作aagent獲得觀察的概率函數(shù)??(??,??,??)=??(??|??,=∑??(??′,??,??)∑??(??,??,

-a據(jù)此，我們可以得到觀察z下的信念狀態(tài)bz。定義信念狀態(tài)轉(zhuǎn)aa數(shù)φ(b,a,bz)，表示信念狀態(tài)的轉(zhuǎn)移a??(??,??,????)=∑??(??′′,??,??)∑??(??,??,

--值函有了信念狀態(tài)之后COMDP的基礎(chǔ)上擴(kuò)展得到POMDP基于信念狀??????????????(??,??)=∑??(??)??(??,-方便起見，將POMDP值函數(shù)簡(jiǎn)寫為ω(ba)。由信念狀態(tài)空間的連續(xù)性和上界信念空間的更新，可以將POMDP視為連續(xù)狀態(tài)空間的MDP問題[Astrom,1965，Sawaragietal1970a]。所以，在POMDP中，同樣使用期望折扣收益(expectedfuturediscountedreward)來表示總的值函數(shù)：??∑??????(????,-對(duì)于無限步迭代∞??∑??????(????,-對(duì)應(yīng)于公式-7COMDP的值函數(shù)公式，得到n步策略下的值函數(shù)公式????(??)=??(??,??)+??∑??(??,??,????) --對(duì)于無限步的情況，有??(??)=??(??,??)+??∑??(??,??,????) -值迭至此，可以參照COMDP的值迭代過程POMDP的函數(shù)值迭代過程。使用動(dòng)態(tài)規(guī)劃的思想，使用n-1步下的最優(yōu)策略來計(jì)算n步最優(yōu)???(??)=??????{??(??,??)+??∑??(??,??,????)

-分別將公式-16-17代入上???(??)=??????{∑??(??)??(??, +??∑∑∑??(??)??(??′,??,??)??(??,??,??′) ??∈????′∈??

將公式-23略作分解，得到如下的計(jì)算過程???(??)=??????

- -???,??(??)=∑ -???,??,??(??)=

??(??,??)+????(??,??,

-由于使用期望折扣總收益，所-27中的1對(duì)立即收益取值，為公式2.24中計(jì)算動(dòng)作a的總收益時(shí)，對(duì)不同觀察由公式-27的分段線性凸性COMDP中，有了函數(shù)值迭代過程，可COMDP問題進(jìn)行求解，得到最優(yōu)值函數(shù)和最優(yōu)策略。POMDP中，信念狀態(tài)是對(duì)S的概率分布，是續(xù)空間，所以計(jì)算最優(yōu)值函數(shù)和最優(yōu)策略是的。函數(shù)表示一個(gè)平面；而在單形體中，線性函數(shù)表示為一個(gè)超平面。而是分段線性凸的eceweiearandcvx，PWC。Sondik證明，在有限步策略的POMDP中，最優(yōu)值函數(shù)是分段線性有限線性函數(shù)的集合在信念狀態(tài)空間上進(jìn)行表示?？梢詫步策略的最優(yōu)??(??)=??????∑??(??)??(??)=?????????

-Γ .2如圖.2分段線性凸函數(shù)示例所示，顏色標(biāo)記部分為各個(gè)向量在該區(qū)間上為最優(yōu)向量。當(dāng)agent處于信念b時(shí)，向量α2為其最優(yōu)值函假設(shè)集合Γ表示信念狀態(tài)空間中的一個(gè)值函數(shù)，對(duì)于向量α，假設(shè)于?bSbα≤maxbα，那么Γ與Γ所表示的值函數(shù)是一樣的。樣的?稱為被向量，如圖二.2分段線性凸函數(shù)示例中的α6,α7向量。相應(yīng)的，稱區(qū)間上取最大值的向量為向量，如圖二.2分段線性凸函數(shù)示例中信念點(diǎn)b上的α2向量由于被向量的存在，最優(yōu)值函數(shù)的向量集合可以有無數(shù)種示。但由于最優(yōu)值函數(shù)的PWLC性，它總可以表示成一個(gè)唯一的最小集合[Littman,1996，Littmanetal.,1995a]。稱值函數(shù)這個(gè)唯一的最小集合為吝嗇集(parsimoniousset)。每一個(gè)向量會(huì)有一個(gè)區(qū)間，表示在這個(gè)區(qū)間上，該向量是構(gòu)成了信念狀態(tài)空間?S的劃分。對(duì)于α∈Γ，其在?S上的區(qū)間記為R(αΓ)：??(??,??)={??|?????≥????,?∈???{??},??∈-基于域，進(jìn)一步得到集的性質(zhì)：對(duì)于一個(gè)具有PWLC性質(zhì)的值函數(shù)，其集表示為Γ，那么，?α∈Γ,R(α,Γ)≠?。值函數(shù)的向量迭利用值函數(shù)分段線性凸的性質(zhì)，對(duì)公式二-27進(jìn)行改寫???,??,??(??)=

??(??,??)+????(??,??,????)???????????????

1=

∑??(??)??(??,+??∑∑??(??)??(??′,??,??)??(??,??,??′)??????????????(??′)???????∈??

1=∑??(??){|??|??(??,+??∑??(??′,??,??)??(??,??,??′)??????????????(??′)?????

-定義向量????,??(??,??)=

??(??,??)+??∑??(??′,??,??)??(??,??,??′)??????????????(??′)?????

-上式可以改寫成???,??,??(??)=??? -進(jìn)而得???,??(??)=??(??,??)+??∑??(??,??,????)??????????????? =∑???

-???(??)=??????{??(??,??)+??∑??(??,??,????)???????????????????}

=??????∑???

-n由于αa,z(b)的集合是有限的，所以使用值函數(shù)的PWLC性質(zhì)，可以nPOMDP問題進(jìn)行求解為方便求解和闡述定義三個(gè)向量集合Γ?,Γ?,a, 分別對(duì)應(yīng)于公式二-25，公式二-26，公式二-27中的值函數(shù)。易得αa,z(bs)∈Γ?,a,z 精確解盡管POMDP相關(guān)的基礎(chǔ)理論以及集的表示在研究中不斷發(fā)展[Astrom,1965，Aoki,1967，Striebel,1965，Astrom,1969，Sawaragietal.,1970b]，但第一個(gè)通用的精確算法是1971年Sondik在他的博士中提出來的[Sondik,1971]。本節(jié)介紹POMDP的精確解法。POMDP的精確解法都是基于函數(shù)值代，而不同之處在于處理值迭代時(shí)，動(dòng)態(tài)規(guī)劃如何從 計(jì)算V??；?文中描述，該問題等同于如何由 集合生成Γ? 枚舉枚舉法(Enumeration)由Monahan提出[Monohan,1982]，雖然不是最早法的思想在Sondik的中已有涉及[Sondik,1971]但最終由Monahan根據(jù)One-Pass的算法而形成。公式-25-26，公式-27n步策略時(shí)，信念狀態(tài)由公式-????,??(??,??)=

??(??,??)+??∑??(??′,??,??)??(??,??,??′)??????????????(??′)?????

n在剩余n步策略，信念狀態(tài)為b，且執(zhí)行動(dòng)作a并得到觀察z的情況下，agent要做的便是從Γt?1中選擇一個(gè)向量，生成αa,z。定義向量集合：n???,??={

??(??,??)+????(??,??,

,

∈

?a,z|?a,z|=

- 由于αa= ?a z∈Z ?a,z?a，?a,z (cross-sum，⊕)運(yùn)算。即???

???,??-|?a|=|?a,z||Z|?a,z?a 中，故在動(dòng)作a下最優(yōu)值函數(shù)可表示為???,??(??)=????????? ??∈????n對(duì)于動(dòng)作集A中的每一個(gè)動(dòng)作a，生成其對(duì)應(yīng)的?a，并做如下操n??

???-至此，得到信念狀態(tài)b時(shí)的最優(yōu)值函數(shù)???(??)=?????????????????∈???nOne-Pass算nnOne-Pass是最早被POMDP精確求解算法。One-Pass算法從任αa(b)函數(shù)的PWLC性質(zhì)，αa(b)對(duì)于該區(qū)間內(nèi)b周圍的信念點(diǎn)也將是最優(yōu)nnR(αa,αa 所以，需要找到其他信念狀態(tài)空間的向量。One-Pass算法提出，如果1 當(dāng)前區(qū)間上的最優(yōu)動(dòng)作不再是其他區(qū)間上的最優(yōu)動(dòng)作2 當(dāng)前最優(yōu)動(dòng)作沒變，但下一步策略發(fā)生了變化n所以O(shè)ne-Pass算法通過三個(gè)不等式確定αa的區(qū)間由公式二-34，當(dāng)剩余n步策略時(shí)，執(zhí)行動(dòng)作a，獲得z時(shí)的最優(yōu)函數(shù)：n???(??)=??????{??(??,??)+??∑??(??,??,????)???????????????????}

對(duì)上述公式稍作改寫如下???(??)=??????{??(??,??)+??∑??(??,??,????)?????????????????

-a其中ι(b,a,z)表示Γn?1中使bz取最大值的值函數(shù)向量序號(hào)，公式中簡(jiǎn)寫為ι。假設(shè)在信念狀態(tài)b時(shí)的最優(yōu)動(dòng)作為a?，對(duì)于第一個(gè)條件，必須確保a????????≥???即??(??????????)≥0,???∈??,??∈????,???∈??,??(??)>0,∑??(??)=-對(duì)于第二個(gè)條件，必須確保??(??,???,????)????≥??(??,???,???? 即??(??,???,?????)(?????????)????≥0,0≤??≤|?????1|?1,???∈??,??∈-但僅是如此還不夠。雖然在信念狀態(tài)b上，對(duì)于動(dòng)作a?，任何其他動(dòng)作a以及其對(duì)應(yīng)的n-1步策略都不具備比a?更高的收益，但對(duì)于除b之外的其他信念狀態(tài)上，動(dòng)作a以及某個(gè)n-1步策略將可能獲得比a?以及某個(gè)n-1步策略更高的收益。所以，需要第三個(gè)不等式：

??)????,??,????

≥

??,??,????即??(??,??,

??′?????)≥0,0≤??≤ |?1,???∈??,??≠

,??∈n-41在得到αa的區(qū)間后，在其邊界處可以得到屬于其他區(qū)間的n念狀態(tài)并由此生成新的向量和其區(qū)間這種類似搜索的方法可以生成窮盡整個(gè)信念狀態(tài)空間，生成最終的最優(yōu)值函數(shù)集。而由于One-Pass算法中基于三個(gè)不等式來構(gòu)造向量的區(qū)間的方法是極為保守的，最終生成的區(qū)間可能是其真正區(qū)間的子集。所以，很有可能出現(xiàn)在非當(dāng)前區(qū)間的其他信念狀態(tài)下求得的向量已經(jīng)出現(xiàn)在最終的集中。對(duì)于這種情況，將重復(fù)向量刪除即可。One-Pass算法是第一個(gè)精確的POMDP求解算法，并且首次運(yùn)用了對(duì)每個(gè)動(dòng)作a單獨(dú)求解最優(yōu)值函數(shù)的思路。以后出現(xiàn)的其他精確算法，均是基于One-Pass算法的思想。Two-Pass算nTwo-Pass算法是Sondik另一個(gè)POMDP問題精確求解方法。n在介紹Two-Pass算法之前，首先要介紹鄰居(neighbors)的概念。????=∑????,??=∑{

??(??)+????(??,??,

},

∈

n定義αa的鄰居向量n??=∑????,??+???,??′ 其中，z′∈Z,αa,z′= (

,

-∈ ,αa,z′nαa,z′n

ωnn

+γφ(b,a,ba

n簡(jiǎn)單來說，如果一個(gè)向量ν是αa的鄰居向量，那么在生成他們的向nnαa,z中，有且僅有一對(duì)是不同的。據(jù)此，由于一共有|Z|種不同的觀察，每nn觀察可以有||Γn?1|?1|個(gè)其他向量可以選擇αa向量有n

?個(gè)鄰居向量。用集合?a來表示所有可能的αa向量，那么集合?a中所有元 的鄰居向量也在集合?a中。αa的鄰居向量的集合，我們用??(αa)來表示 前的枚舉算法我們交叉和的計(jì)算復(fù)雜度為|ΓA||ΓB|對(duì)于向量α∈ΓA， α α3 α2α2+2+αα1+

αα3+α2+圖二.3信念狀態(tài)空間中向量集ΓA,ΓB的交叉和ΓD的集生而實(shí)際上，可以通過幾何特性簡(jiǎn)化這個(gè)集的計(jì)算為方便闡述使用二維向量如圖.3所示R(α1ΓA)這個(gè)區(qū)間中，對(duì)于所有的βΓB不存在α2β或者α3β會(huì)比α1β的函數(shù)值大所以，量區(qū)間有重合的兩個(gè)相加，作為ΓD中這個(gè)重合區(qū)間的向量，并最需要判斷R(α,ΓA)∩R(β,ΓB)是否為空。由此，計(jì)算復(fù)雜度便由原來的+n由公式-36可知，在剩余n步策略時(shí)，動(dòng)作a下的值函數(shù)集合ΓanΓa,z的交叉和。故：αa= ????,?? ??∈??判斷R(αa,Γa)是否為空集，只需判斷如下的區(qū)域是否是空集 ???(????,??,????,??)=??(????,????)

-Two-Pass算法便是基于這樣一個(gè)幾何性質(zhì)在整個(gè)信念狀態(tài)空間中進(jìn)行搜索并對(duì)每一個(gè)向量計(jì)算它的空間然后找到其余的相鄰空間。使用?a來表示確定區(qū)間的向量集合，?a來表示尚未確定區(qū) n的向量集合，算法結(jié)束后，?a便是整個(gè)信念狀態(tài)空間上剩余n步策略時(shí)na的值函數(shù)向量集合。從任意信念狀態(tài)b開始，計(jì)算b對(duì)應(yīng)的動(dòng)作a下αa，αa?a?aαa， ?aαaR(αa, ??(αa)aaa 如果沒有交界，則舍棄向量αa；否則，將αa加入到集合?a中。重復(fù)的從?a nn取出向量，完成上述計(jì)算過程，直到?a向量為空，那么動(dòng)作a下信念狀態(tài)?ann在得到?a后，通過以下計(jì)算得到最后的最優(yōu)值函數(shù) ???=???? -nTwo-Pass算法不能保證得到最優(yōu)值函數(shù)的集，因?yàn)樾砸?guī)劃過程中，某些處于邊界處的向量未必在其他區(qū)域存在區(qū)間，這樣的向量?an松弛算法和線性支持算基于One-Pass算法，Cheng在他的博士[Cheng,1988]中，提出了松弛算法。通過去掉One-Pass算法中的第三個(gè)不等式這個(gè)限制條件，該算法避免了One-Pass算法中區(qū)間過于保守的弊端。但僅僅去掉這一個(gè)限制條件是不行的。SmallwoodSondik在他們文章[Smallwoodetal.,1973]對(duì)One-Pass算法的描述中，忽略了這個(gè)條件，但的一個(gè)點(diǎn)做計(jì)算得到相鄰的區(qū)間以及該區(qū)間上的向量Cheng通過使用頂點(diǎn)枚舉算法[Mattheis,1973]在區(qū)間上選擇多個(gè)頂點(diǎn)進(jìn)行計(jì)算，從而判斷在這些點(diǎn)上是否存在未被發(fā)現(xiàn)的向量。在松弛算法的基礎(chǔ)上，Cheng提出了線性支持算法。松弛算法的思想說明對(duì)于一個(gè)向量，定義比其在Γn上的實(shí)際區(qū)間更大的區(qū)間是可行的?；谶@一點(diǎn)，Cheng提出了一種新的選取最優(yōu)向量的方法。假設(shè)?n表示確定區(qū)間的向量集合，?n表示未確定區(qū)間的向量集合。對(duì)于α∈?n在以前的算法中通過計(jì)算R(α,Γn)來得到α的區(qū)間如果該區(qū)間非空則將α加進(jìn)最優(yōu)集合?n中但性支持算法中使用R(α,?n)?n?n治區(qū)間的超集。所以，如果R(α?n)非空且α?n，取該信念點(diǎn)上的最優(yōu)向?n與松弛算法一樣，為確保區(qū)間不被忽略，線性支持算法同樣需要目擊點(diǎn)算nnn目擊點(diǎn)算法[Cassandraetal.,1994]是第一個(gè)單獨(dú)求解每個(gè)動(dòng)作a上的最優(yōu)值函數(shù)?a的算法，然后對(duì)所有a的值函數(shù)進(jìn)行合并的算法，參見公式?a?annn對(duì)一個(gè)動(dòng)作a，目擊點(diǎn)算法從任一信念點(diǎn)b開始，計(jì)算它的數(shù)αa(b)，以及??(αa)。為了避免得到多個(gè)αa(b)值，對(duì)于在b處取得多 n最優(yōu)值函數(shù)向量的情況，使用字典序方法選取最優(yōu)的αa(b)[Littman,n以確保最終的?a集合是Γa的集使用?a作為待選集合將αa(b)加入?a ?a 從?a中選擇一個(gè)向量α，如果其不在?a中，計(jì)算R(α?a)。如果R為 n集則說明在?a中所有向量的已確定區(qū)間上不會(huì)更優(yōu)所以舍棄nn如果R不為空，那么返回R區(qū)間中的一個(gè)信念點(diǎn)b′，求得?a中在b′中取得?a?a?an ?a中的某個(gè)向量成上述計(jì)算過程?a為空集時(shí)計(jì)算結(jié)束 n可以確保?a是整個(gè)信念狀態(tài)空間中a動(dòng)作在剩余n步策略下值函數(shù)的n基于鄰居向量的性質(zhì)，可以證明目擊點(diǎn)算法的正確性。對(duì)于任意向αa∈Γa，假設(shè)存在b∈?S，和另一個(gè)向量αa∈Γa，若bαa>bαa，當(dāng) 僅當(dāng)存在向量α∈??(αa)滿足b?α>b?αa所以可以在一個(gè)向量 鄰居中，找到其他區(qū)間的向量?a?a)?a n因?yàn)殡m然α在當(dāng)前?a集合中已有向量的區(qū)間上不是最優(yōu)，但它有可能nnn為了使?a中區(qū)間覆蓋的更廣，可以隨機(jī)的選取多個(gè)點(diǎn)，分別計(jì)算這些?ann記錄?a中已被刪除的向量，導(dǎo)致某些無用向量被重復(fù)加入?a中。通過備 n已刪除的鄰居向量，在向?a中添加新向量時(shí)不重復(fù)添加這些向量nn一些無用的計(jì)算過程。另外在向?a中添加新向量時(shí)，可以通過簡(jiǎn)單的n規(guī)劃將一部分比向?a中已有向量差的鄰居向量剔除，縮小?a中有效向量 規(guī)模。另外還有其他的優(yōu)化方法，本文略過增量裁剪n增量裁剪算法(IncrementalPruning，IP)ZhangLiu提出[Zhang在信念空間上進(jìn)行搜索的方式不同，它直接計(jì)算每個(gè)可能的αa。n枚舉法也是直接計(jì)算所有可能的αa，進(jìn)而得到

。但不同于枚舉法 在計(jì)算αa并生成最后的Γ過程中，會(huì)對(duì)生成的中間集合不斷進(jìn)行裁剪 nn，?a?a,znn???)

???,??) -n公式-45的計(jì)算復(fù)雜度是隨|Z|的大小成指數(shù)增長(zhǎng)對(duì)于多狀態(tài)的?a,zn????=

???,??)

??????????(???,??))=??????????(⊕??∈??-可以對(duì)交叉和運(yùn)算中的每?jī)山M向量集合再進(jìn)行裁剪運(yùn)算????=

=??????????(????,0⊕????,1⊕????,2⊕…⊕ =??????????(…??????????(??????????(????,0⊕????,1)⊕????,2)⊕…⊕ -n對(duì)于公式二-47中向量集合Γa,z的裁剪順序并非是固定的，可以有其nGeealedIcemealPrig，GIP被提出[Cassanaeta.,19]該算法基本啟發(fā)是在..3節(jié)中提到的對(duì)兩個(gè)向量集合求交叉和的集的方法不過在此基礎(chǔ)上GIP有著的細(xì)節(jié)GIP使用更為高效的線性規(guī)劃方法來計(jì)算A⊕BD中的每個(gè)向量做是否為區(qū)間的判定。定義如下向量集合：??=????⊕??????????(????∈???|??)????{???|?(???基于以上集合，使用新的方法來優(yōu)化原先的PRUNE(ΓA⊕ΓB)。首先，?D?D?D?D?D?D對(duì)于計(jì)算過程中涉及到的向量集合?，有如下選擇?=?=({??}+????)∪(????+?=?=??∪(????+?=??∪({??}+GIP算根據(jù)θ選擇相應(yīng)的最小向量集合作為當(dāng)前?進(jìn)行線性規(guī)劃的精確算法復(fù)雜度分由公式-31，公式-35可以得到，在每次迭代過程中，將會(huì)生于是該階段的總時(shí)間復(fù)雜度為|S||A||Γt?1||O|由此動(dòng)態(tài)規(guī)劃的向量新過程總時(shí)間復(fù)雜度為O(|Γt?1||A||O||S|2|S||A||Γt?1||O|)N-Had高了算法的性能，但情況時(shí)，仍然無法降低POP問題的求解復(fù)雜度。所以精確算法在實(shí)際應(yīng)用中存在很大的局限性?？偙菊陆榻B了精確算法，從One-Pass算法以來，已有多個(gè)精確算法被相第三章基于點(diǎn)的近似引基于章節(jié)2.5中的討論和分析，精確算法計(jì)算中，每一次迭代過程，計(jì)算過程，直接生成區(qū)間上向量子集，或者對(duì)值函數(shù)向量集合進(jìn)行裁剪來降低其規(guī)模POMDP模型用于大規(guī)模狀態(tài)集、動(dòng)作集和觀察集在此背景下，出現(xiàn)了一些近似算基于COMDP計(jì)算的低復(fù)雜性，通過將POMDP問題轉(zhuǎn)化成COMDP問題的啟發(fā)式方法是最直觀的近似算法。這類算法包括MLS算法(MostLikelyStateNourbakhshetal.,1995]，QMDP算法[Littmanetal.,1995b]FIB算法(FastInformedBound)[Hauskrecht,2000]。通過這種類COMDP的啟發(fā)式上界V?(b)≤VFIB(b)≤VQMDP(b)≤VMLS(b)網(wǎng)格計(jì)算等方法[Bonet,2002，Zhouetal.,2001，Rossetal.,2008]也被提出，在此不作介紹。來得到廣泛關(guān)注，它能高效的解決大規(guī)POMDP求解問題，并在實(shí)際應(yīng)用中有良好的效果?；谥岛瘮?shù)的PWLC性，可以選取每個(gè)向量統(tǒng)治域中具有代表性的信念點(diǎn)，來代表這個(gè)區(qū)間。通過精細(xì)的信念點(diǎn)選擇方法，可以用這些點(diǎn)來近似整個(gè)信念空間。通過更新每個(gè)信念點(diǎn)的向量，可以推進(jìn)值迭代過程。不同于網(wǎng)格計(jì)算方法，基于點(diǎn)的算法PVI法PIPIPOPPIPVI在提高性能的同時(shí)能得到更好的值函數(shù)近似效果?；邳c(diǎn)算法的函數(shù)值更在基于點(diǎn)的計(jì)算方法中，選取一個(gè)信念點(diǎn)集合B??S，并且計(jì)算該集述對(duì)信念點(diǎn)b進(jìn)行值函數(shù)更新的過程。首先立即值的計(jì)算跟精確值迭代是一樣的ω(b,a)∑s∈Sb(s)R(sa)，進(jìn)一步表示為????={????|????=??(??,??),???∈ -接下來，基于Γn?1計(jì)算長(zhǎng)期收益????,??={????,??|????,??(??)=??∑??(??′,??,??)??(??,??,??′)??(??′),??∈

-結(jié)合以上兩式，得到信念狀態(tài)b時(shí)，動(dòng)作a下的最優(yōu)函數(shù)????(??)={????(??)|????(??)=????+∑???????????????

-對(duì)比公式-36和公式-3我們發(fā)現(xiàn)，在精確值迭代中，需要對(duì)所有觀察下的Γa,z做交叉和運(yùn)算生成Γa，而在基于點(diǎn)的值更新中對(duì)每 然后對(duì)這些最優(yōu)值做累加和。在此基礎(chǔ)上，我們得到b上的向量：????(??)=????????∈????

???-n基于點(diǎn)的值迭代過程首先對(duì)當(dāng)前信念點(diǎn)b生成每個(gè)動(dòng)作下的值函數(shù)集n????(??)={????????????(??,?????1(??)),??∈-對(duì)于基于點(diǎn)的近似算法來說，我們期望有限的點(diǎn)集B在函數(shù)值更新之后，生成的向量能夠很好的覆蓋信念空間中的可到達(dá)區(qū)間，而且這對(duì)于所有的基于點(diǎn)的近似算法，有下面的計(jì)算框架.1InitializeV0,while conditionnotmetBnew←??????????????(????,forNiterationsVn+1←????????????(????,??,n←n+endB←B∪10.end基于點(diǎn)算法概第一個(gè)基于點(diǎn)的算法是基于點(diǎn)的值迭代算法(Point-BasedValueIteration，PBVI)[Pineauetal.,2003]，之后又相繼出現(xiàn)了Perseus算法etal.,2005]發(fā)式搜索值迭代算法(HeuristicSearchValueIteration，HSVISmithetal2004，Smithetal2005]，基于點(diǎn)的最小誤差算法(Point-BasedErrorMinimizationAlgorithm，PEMA)[Pineauetal.,2005]，向前搜索值迭代算法(ForwardSearchValueIteration，F(xiàn)SVI)[Shanietal.,2007]和最優(yōu)策略下的后繼可到達(dá)近似空間算法(SuccessiveApproximationoftheees算法的信念點(diǎn)集B定程度上避免了其他算法在每步迭代中點(diǎn)集擴(kuò)張帶來的計(jì)算量的不斷增加但隨機(jī)采點(diǎn)方法對(duì)重要點(diǎn)的隨機(jī)假設(shè)會(huì)導(dǎo)致收斂較慢以及大規(guī)模領(lǐng)域下求解點(diǎn)集太大等問題。本文主要介紹PVI、HVI和VI這三個(gè)算法。PBVI算PBVI是第一個(gè)被基于點(diǎn)的POMDP近似計(jì)算方法，它第一次提出了僅在具有代表性的系統(tǒng)可到達(dá)信念狀態(tài)子集B??S上進(jìn)行函數(shù)值迭CollectionPBVI從一個(gè)初始信念點(diǎn)B={b0}開始。在每次點(diǎn)集擴(kuò)張過程中，由當(dāng)最終的信念點(diǎn)集B=B∪Bnew。所以每次點(diǎn)集擴(kuò)張后，新的點(diǎn)集規(guī)模是原來點(diǎn)集的兩倍下面是由當(dāng)前點(diǎn)集B中某個(gè)信念點(diǎn)b生成新的信念點(diǎn)b′的過程。在b上依次執(zhí)行aiA，并由得到的觀察zZ中隨機(jī)選取?i由信念狀態(tài)轉(zhuǎn)移函數(shù)φ(b,ai,bai,z?i)得到后繼信念點(diǎn)bai,z?i。重復(fù)這個(gè)過程，得到b關(guān)于每個(gè)動(dòng)作下的后繼點(diǎn)集合{ba1,z?1,ba2,z?2,…,ba|A|,z?|A|}。接下來，計(jì)算{bai,z?i}中每個(gè)信念點(diǎn)與B中每個(gè)信念的L1模式，并將具有最大L1模式的bai,z?i作為b′，加入到B中。??1模式公式如下：1||??1?1

=∑|??1(??)?-||??????,????????||=??????||??????,?????? -??′=????????????||??????,?????? -由上述公式可知，b′即為{bai,z?i}中距B中所有信念點(diǎn)最遠(yuǎn)的點(diǎn)。對(duì)于新生成的點(diǎn)集Bnew是與現(xiàn)有點(diǎn)集B在信念狀態(tài)空間上距離最遠(yuǎn)并且所BackupPBVI對(duì)信念點(diǎn)的函數(shù)值更新很簡(jiǎn)單。對(duì)于當(dāng)前信念點(diǎn)集B，使用公三-5來對(duì)它們的值函數(shù)進(jìn)行但是B中每個(gè)信念點(diǎn)進(jìn)行值更新的過程中不斷對(duì)這個(gè)下屆進(jìn)行提升，進(jìn)而近最優(yōu)值函數(shù)。這樣做的優(yōu)勢(shì)在一個(gè)較常用的下界初始化方法是最優(yōu)-情況初始化方法(best??????[????????(??,??(??)=??∈?? ,???∈1???-最優(yōu)-情況初始化方法在計(jì)算立即收益時(shí)總是選擇狀態(tài)下執(zhí)在PBVI算法執(zhí)行過程中信念點(diǎn)集的擴(kuò)展過程和信念點(diǎn)集合上的函數(shù)念點(diǎn)集合上進(jìn)行深度為N迭代計(jì)算，生成該集合上的值函數(shù)，對(duì)應(yīng)于整個(gè)PBVI定義了信念點(diǎn)集密度?B來衡量一個(gè)點(diǎn)集B在信念狀態(tài)空間?SHSVI算HSVI算法采用啟發(fā)式的采點(diǎn)方法，在最早該算法[Smithetal.,2004]的基礎(chǔ)上個(gè)改進(jìn)版本[Smithetal.,2005]本段關(guān)注改進(jìn)后的HSVIHSVI在計(jì)算最優(yōu)值函數(shù)上下界的基礎(chǔ)上，使用啟發(fā)式的方法來選擇新HSVI采用新加信念點(diǎn)先計(jì)算的反向計(jì)算方法，提高算法的收斂速度。HSVI完成與最優(yōu)函數(shù)不斷近的過程。并且在上下界函數(shù)值差小于一定閾值時(shí)結(jié)束計(jì)算。HSVI算法是綜合性能最好的點(diǎn)迭代算法，函數(shù)值收斂快，并且上下界近的方法使得在某些信念點(diǎn)上，值函數(shù)能收斂到實(shí)際最優(yōu)值。CollectionHSVI使用信念點(diǎn)對(duì)值函數(shù)收斂作用的大小的啟發(fā)式方法來選擇后繼于信念點(diǎn)集B中的每個(gè)信念點(diǎn)b，HSVI為其兩個(gè)函數(shù)值，分別是該點(diǎn)???(b)?(b)[?(b)HSVI定義了?(b)的大小用來表示b點(diǎn)上值函數(shù)上界和下界之間的(?(??))?(??)-HSVI使用信念點(diǎn)和和該點(diǎn)在值函數(shù)上界上的投影值對(duì)的形式來表示上界集合，記為Υ?={(bi?i)}，上界的更新過程即為向Υ?對(duì)中增加新的信上界?來選取[Kaelbling,1993]：???=???????????????(??,-???(??,??)=∑??(??,??)??(??)+∑??(??|??,??)?(??(??,??, -函數(shù)上界來選取動(dòng)作a。而最優(yōu)動(dòng)作a?在要么是真實(shí)最優(yōu)，要么其近似值函數(shù)上界在下一步的更新中下降。如果?只是次優(yōu)動(dòng)作，那么當(dāng)更新導(dǎo)致HSVI定義了一個(gè)excess函數(shù)來定義一個(gè)信念點(diǎn)的不確定性????????????(??,??)=?????????(?(??))?-其中?是引入的一個(gè)控制算法質(zhì)量的閾值。HSVI選擇導(dǎo)致當(dāng)前信念點(diǎn)???=????????????[??(??|??,??)????????????(??(??,??,??),??+-由此得到下一個(gè)信念點(diǎn)bnew=φ(b,a?,z?)。計(jì)算width(?(bnew))是否Backup信念點(diǎn)過程按照策略樹由淺到深的順序依次構(gòu)造了一系列的信HSVI值函數(shù)的上界和下界按照不同的方法同步進(jìn)行更新對(duì)于值函數(shù)上界的更新，每次加入一個(gè)信念點(diǎn)和其在值函數(shù)上界的投影值Υ?Υ?Q?即Γ=ΓVbackup(b)，其中backup操作見-4對(duì)于值函數(shù)上界，在最早的版本中[Smithetal.,2004]，使用COMDP函數(shù)[Littmanetal1995b]。在后來改進(jìn)版本中[Smithetal.,2005]，使用FIB方法[Hauskrecht,2000]。這兩種方法均能保證值函數(shù)上界在真實(shí)值函之上，且FIB能夠得到更為接近真實(shí)值函數(shù)的上界，加快算法收斂。對(duì)于值函數(shù)下界，在最早版本中使用固定策略，見公式三-9。在改版本中，使用該策略初始化αa，并使用如下的方程迭代得到αa向 集 (??)=??(??,??)+??∑??(??′|??,

-FSVI算VI是7年提出來的一個(gè)收斂較快的算法，且能在大規(guī)模問題下具有很好的性能。FVI使用基于OP的啟發(fā)式策略沿著策略樹索搜新操作。CollectionFSVI使用基于COMDP的最優(yōu)策略，用Q函數(shù)來表示其在POMDP中????????(??)=????????(??,-其中??(??,??)=??(??,??)+∑??(??,??,-進(jìn)而得到最優(yōu)動(dòng)作???=??????????????(??,-，F(xiàn)SVI中，使用信念狀態(tài)b來表示agent的當(dāng)前狀態(tài)，同時(shí)用一個(gè)狀態(tài)s模擬其在環(huán)境中的確切狀態(tài)這樣一個(gè)狀態(tài)-信念狀態(tài)對(duì)(s,b)于s，由公式三-18得到COMDP下的最優(yōu)動(dòng)作a?。基于狀態(tài)轉(zhuǎn)移矩陣τ(s,a,s′)隨即選取下一個(gè)狀態(tài)??′，再通過觀察函數(shù)O(s′,a?,z)得到隨機(jī)觀察值z(mì)，由此可根據(jù)信念狀態(tài)轉(zhuǎn)移函數(shù)得到下一個(gè)信念點(diǎn)bφ(baz)。然后對(duì)(s′,b′)繼續(xù)搜索得到下一個(gè)信念點(diǎn)，直到agent到達(dá)某一個(gè)目標(biāo)狀態(tài)?，Backup當(dāng)基于COMDP沿著策略樹向前搜索得到一個(gè)信念狀態(tài)b后，F(xiàn)SVIb上執(zhí)行backup操作，參見公式-4時(shí)候，按相反的順序進(jìn)行，該方法在HSVI算法也得到了使用。FSVI需要一個(gè)給定的目標(biāo)狀態(tài)?確保信念點(diǎn)能夠終止或者規(guī)定略深度，在一定迭代次數(shù)之后結(jié)HSVI能夠在一些HSVI處理性能很差的大規(guī)模問題上得到很好的執(zhí)行效果，但對(duì)于需要進(jìn)行信息的問題領(lǐng)域中，F(xiàn)SVI便無法適用。PointInterpretationPBVI(PIPBVI)算本節(jié)提出基于插點(diǎn)的PBVI改進(jìn)算法PIPBVI并且使用通用數(shù)據(jù)集進(jìn)行在PIS上分布的密度?B實(shí)驗(yàn)證明，這種方法是有效的。算法描PBVI中，信念點(diǎn)和信念點(diǎn)集合上的值函數(shù)更新是交替進(jìn)行的。個(gè)信念狀態(tài)空間上的分布滿足密度

，則誤差

≤(Rmax?Rmin)?BPIPBVI中對(duì)PBVI算法的改進(jìn)體現(xiàn)為兩個(gè)點(diǎn)集的約簡(jiǎn)和信念點(diǎn)的.2PIPBVIPIPBVI算輸入POMDP問題，折扣γ，誤差輸出最優(yōu)策略和初始化V(??0)=0最大初始化whileV′(??)?V(??)≥?1?γ B進(jìn)行約對(duì)B進(jìn)行信念點(diǎn)插入，Backup新插入信念V(??0)=V′(??0)，求得??0處值endPVI一向量區(qū)間上的情況所以使用,b)的形式來記錄一個(gè)統(tǒng)治向量以及該向量上的點(diǎn)最后這樣的向量-信念點(diǎn)對(duì)構(gòu)成當(dāng)前迭代結(jié)束后經(jīng)過約簡(jiǎn)的點(diǎn)集和整個(gè)信念狀態(tài)空間上的近似值函數(shù)。由當(dāng)前點(diǎn)集B經(jīng)過點(diǎn)過程生成Bnew，合并得到新的點(diǎn)集B=B∪Bnew。在進(jìn)行點(diǎn)集上的值函數(shù)更新過程中，我們使用向量-信念點(diǎn)對(duì)(αibj)來表示生成的向量。在整個(gè)迭代過程完成之后，對(duì)點(diǎn)集進(jìn)行約簡(jiǎn)。初始向量集合Γ′=?-信念點(diǎn)對(duì)按照各α向量進(jìn){(αi{b1b2bk})}，對(duì)于每一個(gè)(αi{b1b2bk})，記?={b1b2bk}，選取?中距離B??最遠(yuǎn)的一個(gè)信念點(diǎn)作為αi向量區(qū)間下的代表信念點(diǎn)，于是得到向量-信念點(diǎn)對(duì)集合{(αibi)}。至此，完成信念點(diǎn)集的約簡(jiǎn)，得到到的信念點(diǎn)并非backup中真正用到的點(diǎn)，只是為采點(diǎn)所做的一種啟發(fā)式搜索。所以，期望在這種啟發(fā)式策略之外，根據(jù)當(dāng)前點(diǎn)集在信念布密度降低，所以可能會(huì)找到滿足插入條件的信念空間，所以進(jìn)行程：計(jì)算點(diǎn)集B′中每對(duì)信念點(diǎn)之間的曼哈頓距離：d(bi,bj)=||bi?bj||1如果??(????,????)

2??? ，-19計(jì)算bi,bj上對(duì)應(yīng)的向量的交界，如果兩個(gè)信念點(diǎn)處于同一個(gè)向量下則不進(jìn)行任何操作否則根據(jù)[Cheng,1988]中的采點(diǎn)方法一個(gè)信念點(diǎn)b，并根據(jù)公式-4的值函數(shù)更新過程對(duì)b進(jìn)行backup操作。對(duì)，進(jìn)行backup過程之后，不再附加對(duì)向量和信念點(diǎn)集的剪裁過根據(jù)初始信念點(diǎn)的值在值函數(shù)迭代前后的取值差來定義收斂條件，即

)?

1?)≤實(shí)驗(yàn)和分PIPBVI并非能在所有的POMDP模型上帶來效果提升，因?yàn)镻IPBVI依的問題，PIPBVI中的向量裁剪和信念點(diǎn)集約簡(jiǎn)過程效果甚微，且增加了算PIPBVI可以解決更大規(guī)模的問題，通過向量的裁剪和信念點(diǎn)集的約簡(jiǎn)過程，可以在更為有效的向量和信念點(diǎn)集的基礎(chǔ)上增加迭代深度，算法進(jìn)行檢驗(yàn)，并且與PBVI算法進(jìn)行對(duì)比。各模型參數(shù)：.3數(shù)據(jù)552收斂時(shí)初始信念點(diǎn)處平均折扣收益(averagediscountreward，ADR)的大小。具體來說將每個(gè)算法在每個(gè)數(shù)據(jù)集上執(zhí)行11每次隨機(jī)選擇不同復(fù)該過程10是得到110次執(zhí)行過按照每次執(zhí)行時(shí)間排去執(zhí)行情況最好的5次和執(zhí)行情況的5次，得到其余100次執(zhí)行的平均規(guī)定參數(shù)γ=095?=000實(shí)驗(yàn)結(jié)果如錯(cuò)誤!未找到源看到PIPVI得到了更好算法性能和收益alge和agPI而言性能插入點(diǎn)計(jì)算等均需要消耗時(shí)間，而算法整體性能的改善并不明顯。.4PIPBVIPBVI算收斂時(shí)--DR取值的關(guān)系，如圖三.1所示?？吹絇IPVI在四個(gè)數(shù)據(jù)集上均加快了值函數(shù)的收斂，并且在執(zhí)行過程中的各個(gè)未收斂狀態(tài)，PIPVI函數(shù)也優(yōu)于PVI。數(shù)。而且PIPBVI在不斷的迭代和點(diǎn)集擴(kuò)張過程中，保持了一個(gè)規(guī)模較為適0123456789 0123456789 04812162024283236 0024681012141618 981224364860728496 總PIPVIPVI算法在性能上有所提升，并且得到更優(yōu)的策略。第四章基于點(diǎn)的策略迭代算引對(duì)于續(xù)空間上無限步策略的MDP問題，總存在一個(gè)最優(yōu)的固定策略[Blackwell,1965]?；谶@樣一個(gè)結(jié)論，Sondik提出了POMDP問題的策略表示和策略迭代解法[Sondik,1978]。但這個(gè)原始的策略迭代方法十Hansen提出用有限狀態(tài)機(jī)(Finitestatecontroller，F(xiàn)SC)來表示策略的方法[Hansen,1997，Hansen,1998a]，動(dòng)作的執(zhí)行和觀察導(dǎo)致FSC節(jié)點(diǎn)之間的轉(zhuǎn)移，而策略迭代過程可以通過FSC點(diǎn)的添加，修改和刪除來進(jìn)行。FSC的引入使得策略迭代變得實(shí)際可行，相比于值迭代有很好的性能優(yōu)勢(shì)，并能夠在真實(shí)環(huán)境中解決實(shí)際問題[Bagnelletal.,2003]。本章介紹Hansen的策略迭代算法和基于點(diǎn)的策略迭代近似算法。在策略迭代算法介FSC的表示和轉(zhuǎn)基于PWLC性質(zhì)，值函數(shù)可以表示成向量的集合，策略迭代也是基于這一性質(zhì)。面介紹的精確算法中，將策略表示成信念狀態(tài)空間到動(dòng)的映射：πSA，這是值迭代中策略的表示方法。接下來用FSC來直接在基于值迭代的精確算法中，Γn+1中每個(gè)向量對(duì)應(yīng)于在剩余n步策略數(shù)向量和一步策略選擇之間的對(duì)應(yīng)關(guān)系，文章[Kaelblingetal1998]提出了使用非循環(huán)FSC表示有限策略步POMDP的最優(yōu)策略FSC中，每策略迭代的進(jìn)步策略空間中的向量，可以由此進(jìn)行直接計(jì)算： (??)=??(??,??)+ ??(??,??,??′)??(??′,??,

-通過求解|S|個(gè)如上等式，可基于Γn得到Γn+1中的一個(gè)向量 nn對(duì)于剩余n步策略時(shí)的FSC，有與之對(duì)應(yīng)的向量集合Γn，每個(gè)αi∈nn對(duì)應(yīng)轉(zhuǎn)移到的后繼節(jié)點(diǎn)jl(iz)使用公式-1對(duì)此過程進(jìn)行迭可對(duì)αi進(jìn)行提升，得到 。對(duì)Γ中的每個(gè)向量執(zhí)行此一步迭代過程，得 接下來根據(jù)t+1和剩余n步策略時(shí)的SC構(gòu)造當(dāng)前的SCα∈?！?，如果存在與某個(gè)狀態(tài)控制節(jié)點(diǎn)對(duì)應(yīng)的n∈n，其中與相關(guān)的動(dòng)作和后繼與nα完全αn并更新向量為α，如果存在多個(gè)這樣的n，則合并這些狀態(tài)控制節(jié)點(diǎn)；否SC中添加一個(gè)與SC中任何沒有與n+1中的某個(gè)向量相對(duì)應(yīng)的狀態(tài)控制節(jié)點(diǎn)，這些節(jié)點(diǎn)是不可達(dá)的。當(dāng)Γn+1中的所有向量與n步策FSC中對(duì)應(yīng)的向量重復(fù)時(shí)，策略迭代收斂而當(dāng)前的FSC便是對(duì)應(yīng)的最優(yōu)策略但并不是所有的POMDP模型都能有一個(gè)收斂的FSC，很可能發(fā)生的情況是隨著迭代的進(jìn)行，F(xiàn)SC不斷的近似于一個(gè)真實(shí)最優(yōu)策略。在這樣的情況下，可以確保策略迭代與實(shí)最優(yōu)在小于?(1?γ)的誤差范圍內(nèi)收斂[Hansen,1998b]γ基于點(diǎn)的策