不确定环境下的规划问题在研究领域和应用领域愈发重要,设计健壮而具备较强可伸缩性的算法是设计和实现不确定环境下能够独立决策的自治和半自治系统的关键。部分可观测马尔科夫模型(Partially Observable Markov Decision Processes, POMDPs)提供了不确定环境下决策问题的解决框架,但是由于POMDP问题的历史灾难和维度灾难特性,其精确求解的方法使得POMDP在实际领域的应用中受阻。虽然基于策略迭代的方法具有比值迭代更好的性能,但其应用仅局限于一定规模下的实际问题。近似算法的提出,尤其是基于点的近似算法的提出和不断改善,改变了这一情况。通过选取具有代表性的点并基于这些点来做规划,可以得到比较接近精确最优的次优策略。本文介绍了POMDP由MDp模型的演变,以及在此基础上值函数和迭代过程的变化。通过对一系列精确算法的描述,分析其计算复杂度,得到其无法实用的原因。随后介绍了策略迭代算法和基于点的近似算法,通过对几年来具有代表性的基于点的算法PBVI、HSVI和FSVI的描述,展示了点算法统一的框架和在点集选取和点集上值函数迭代在细节上的不同。本文提出了PIPBVI和PBHSPI算法,并在四个具有代表性的权威数据集上进行实验,与已有经典算法进行对比,分析和讨论了算法在不同问题上的表现。通过对信念点集和值函数向量有针对性的裁剪,然后对点集进行对值函数有提升效果的插值,PIPBVI算法取得了相比于PBVI更好的性能和策略。PBHSPI算法结合了策略迭代和启发式点算法的优点,通过交叉使用基于点集的值迭代和直接策略迭代,决策效果不降低的情况下有效加快了算法的收敛。