课程资源人工智能AI有时也称机器定义为

第一章绪引(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的值函数进行合并的算法，参见公式̂â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 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]γ基于点的策