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

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

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

-n當初始狀態為s，系統有n步決策時，V?(s)便是最優策略π?下的最優值函數。這個動態規劃的計算過程便是值迭代過程。對公式-9進一n???,??(??)=??(??,??)+??∑??(??,??, ???(??)=??????

-n在公式-10中，V?,a(s)表示在狀態sagent執行動作a，余下nnn-1步執行對應狀態??′下的最優決策。稱V?,a(s)為Q函數。由此，可以得到最優策略π?=(d?,d? ,…,d?)，其中d?(s)=argmaxV?,a(s)。n

對于無限步決策的COMDP模型，用類似于有限步模型求解過程的方???(??)=??????[??(??,??)+??∑??(??,??,-通過最優值函數，得到最優策略???(??)=????????????[??(??,??)+??∑??(??,??,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1=

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

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

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

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

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

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

=??????∑???

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

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

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

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

,

∈

?a,z|?a,z|=

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

???,??-|?a|=|?a,z||Z|?a,z?a 中，故在動作a下最優值函數可表示為???,??(??)=????????? ??∈????n對于動作集A中的每一個動作a，生成其對應的?a，并做如下操n??

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

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

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

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

≥

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

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

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

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

},

∈

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

,

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

ωnn

+γφ(b,a,ba

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

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

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

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

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

???,??) -n公式-45的計算復雜度是隨|Z|的大小成指數增長對于多狀態的?a,zn????=

???,??)

??????????(???,??))=??????????(⊕??∈??-可以對交叉和運算中的每兩組向量集合再進行裁剪運算????=

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

-結合以上兩式，得到信念狀態b時，動作a下的最優函數????(??)={????(??)|????(??)=????+∑???????????????

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

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

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

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

，則誤差

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

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

)?

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

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