部分可观测马尔科夫决策过程(Partially Observable Markov Decision Process,POMDP)是处理不确定条件下决策问题的一个通用框架,它在机器人控制,口语系统,医疗诊断等领域都有很大的应用前景。但是由于POMDP问题的历史灾难和纬度灾难性质,精确求解算法是NP难问题,这就大大限制了其在实际中的应用。近年来,近似算法,特别是基于点的近似算法在POMDP策略求解上取得了很大的进步。基于点的算法只考虑初始信念点的可达空间,在可达空间的采样点上进行值迭代,不同算法之间的区别主要在于采样方法和迭代策略。其代表性的算法有基于点的值迭代(PBVI),前向搜索值迭代(FSVI)和启发式搜索值迭代(HSVI),它们通常能够得到最优或近似最优的策略。另一类重要的近似算法是基于迭代函数的近似,如基于MDP的近似(QMDP),快速告知边界法(FIB),它们得到的是精确值函数的上下界。这类算法通常简单快速,能够处理规模较大的问题,但是对产生策略的质量没有保证。为了在较短的时间内得到一个良好的下界,本文提出了相关状态提升法(RSU),它的主要思想是用对信念点相关状态的提升去近似对信念点的提升,同时借助内在的MDP探索最优策略下的可达状态空间,然后在得到的状态空间中利用近似值迭代和状态转移树的拓扑结构来加速迭代的进程。利用得到的上下界,本文给出了一个改进的基于点的算法--多路启发式搜索值迭代(MHSVI),依据可能的最优值函数产生信念点路径,对路径可能达到的值进行评估,并依据评估值对路径进行剪枝,使得值函数能够快速地收敛。本文在几个代表性问题上对提出的算法和已有算法进行了实验,实验结果证明了 RSU和MHSVI的有效性。