部分可观察的马氏决策过程(partially observable Markov decision process,简称POMDP)为主体在部分可观察的随机环境中的序列决策问题提供了一个通用的数学模型。POMDP模型可以被广泛地用来建模机器人导航、物体抓取、目标跟踪、人机对话等规划和学习任务。一般而言,在合理时间内精确地求解POMDP规划问题是不可能的。近十年来,出现了很多POMDP模型的近似规划算法。它们可以大致分为离线规划算法和在线规划算法。基于点的值迭代算法是这些离线规划算法中最耀眼的一类,它在近十年里取得了很大的成功。它的出现和发展使得POMDP规划问题求解器从只能求解几十个状态的小规模POMDP问题发展到可以求解数十万个状态的大规模POMDP问题。对可达信念空间的δ-覆盖数(简称：覆盖数)这个概念的认识的不断深入对基于点的值迭代算法的发展起到了重要的推动作用。可达信念空间指的是从初始信念状态通过采取随机行动可以到达的信念状态构成的集合。覆盖数指的是用给定半径δ>0的小球完全覆盖可达信念空间所需要的球的最少个数。已有的文献表明：我们可以在覆盖数的多项式时间内计算出POMDP规划问题的近似最优解。在本文中,我们将给出三种估算覆盖数的方法,并分析它们各自的优缺点。我们将看到在一组小规模的POMDP基准问题上,覆盖数是比其它的复杂性度量,如：状态数等,更好得多的表征POMDP规划问题和学习问题难易程度的度量。进一步地,我们将把覆盖数与POMDP规划问题间的理论关系推广到POMDP学习问题领域。我们将从覆盖数的角度来分析POMDP学习问题比规划问题更难的原因,并提出一个在覆盖数的指数时间内收敛的POMDP学习算法。我们希望覆盖数的概念及它的估算方法能够为将来设计出更高效的POMDP学习算法提供洞察和指导。基于对覆盖数的研究,我们发现：现有的一些基于点的值迭代算法在保证能在有限时间内找到近似最优解的同时,忽略了一些重要的启发式信息,这造成了这些算法的性能并不足够高效。我们提出了一个基于贪心策略的值迭代算法框架,它的主要思想是：利用这些被忽略的启发式信息来构造一个贪心子算法,并把它插入到之前的值迭代算法中。我们构造了一个有一定的数学理论支持的、被称为第二好策略导向的贪心子算法来检验该算法框架的有效性。我们的实验结果表明：在求解很多POMDP基准问题时,三个结合了第二好策略导向的贪心子算法的值迭代算法较之前的算法有至少一个数量级的时间性能的改进。与离线规划算法不同的是,在线规划算法采取的是“按需”做决策而不是预先对整个状态空间做决策的方式,因此能够在较短规划时间内高效地处理较大规模的POMDP问题。在本文中,我们将利用POMDP问题中状态表示的结构和杂合启发法来加速现有的启发式在线规划算法。我们将提出两个新的在线规划算法,它们分别被用来检验一种最近提出的因子化状态表示方法和一种新颖的杂合启发法在加速POMDP规划算法中的重要性。我们的实验结果表明：从可扩展性和解的质量两个方面来看,使用了因子化状态表示和杂合启发法的新的在线规划算法的实验性能都比当前的其它启发式搜索在线算法的实验性能要好得多。