论文部分内容阅读
智能规划(AI planning)是传统人工智能最重要的研究领域之一。随着问题规模不断增大,复杂程度不断提高,如何在大规模不确定环境下设计出高效智能的决策算法是当前智能规划非常重要的研究课题。由于POMDP能够很好地对环境、动作及观察的不确定性进行建模,因而在不确定性环境下基于POMDP模型来进行规划是目前自动规划研究的重要内容。而在无限视野下精确求解POMDP问题是NP难问题,在过去的十多年里,基于点的POMDP问题启发式求解成为了大规模POMDP问题求解的研究热点。但是在离线求解POMDP问题的研究中,大多数基于点的近似求解方法都是基于单一的启发式标准,难以适用于不同的问题场景；在在线求解POMDP问题的研究中,且近几年的启发式方法都是只以最优上界作为探索标准,降低了收敛效率。本文围绕如何设计高效的启发式POMDP求解算法来展开研究。本文的研究内容主要有三个方面,首先,研究了目前主流的基于点的POMDP近似求解启发式标准,杂合密度分布的标准和值函数的标准设计HHVI算法来提高探索信念点集的质量；其次,研究了基于聚类构造可达信念点集最小覆盖的方法,并设计了基于点的策略迭代算法来求解POMDP司题；最后改进了最优可达信念空间的探索标准,设计了基于概率的最优可达空间近似方法,从而改进了POMDP在线求解的效率。具体来说,论文的主要内容和创新点如下：1. 目前基于点的POMDP离线近似求解启发式标准主要是基于密度分布的标准、基于值函数的标准和基于MDP的标准。但是基于MDP的近似解法没有考虑部分可观察性,会退化为随机策略；单一基于密度标准的算法无法控制探索点集的规模难以保证收敛质量；单一基于值函数的算法复杂度较高难以保证收敛效率。本文提出了杂合的启发式值迭代算法来离线求解POMDP问题,该算法基于值函数启发式标准评价已探索点集内信念点的被扩价值,结合信念点分布和值函数选择合理的后继点,通过杂合值函数和密度的标准避免了单一标准的局限性,增强了对不同POMDP问题的适应性。2.最近的研究说明δ-覆盖数是刻画基于点的POMDP问题求解的有效度量,但精确计算可达信念空间的δ-覆盖数是一个NP-难的问题。本文分析了可达信念空间的聚类特性,基于可达信念空间的分布特征来高效地构造其δ-覆盖,由此获得分散分布于可达信念空间的探索信念点集,通过策略迭代来离线求解POMDP问题。3. 当前的启发式在线算法大多基于最高上界的行动分支搜索探索信念点,从理论上保证算法最终能找到信念点上的最优行动,但上界的收敛较慢,且下界能够保证策略的质量,在线规划算法在执行时以最优下界对应的行动作为决策行动。本文提出了选择最优动作的新标准,以所有动作的函数值在其上界和下界之间的概率分布为基础,计算每个动作的值函数取值最大的概率,再选择概率值最大的动作。算法更准确地探索到最优可达信念空间附近的区域,从而提高在线求解的迭代效率。