预测状态表示中状态空间划分机制及应用研究

PSR (Predictive State Representations) is an efficient technique for solving partially observable problems.The state of the art algorithms for obtaining the PSR model of a system search the entire state space for a solution, which is high computational complexity, hard to obtain and can only be applied to small scale systems. In this project, in order to apply PSR to large scale systems, the mechanism of dividing the state space is studied, the scheme of obtaining the PSR model is proposed, and the planning algorithm with the PSR model is analyzed. Firstly, a method for state space division is proposed, where the entire state space is divided into multiple sub-state spaces by using the identified landmarks as the critical points; secondly, to reduce the difficulty and computational complexity for obtaining the PSR model, based on the sub-state spaces, a mechanism of obtaining the PSR model is put forward; finally,the planning algorithm based on the obtained PSR model, which is combined by the PSR models of the sub-state spaces and is usually inaccurate, is discussed. The PSR related algorithms studied in this project will provide efficient programs for solving the widespread partially observable problems and will be applied to large scale systems.

预测状态表示（PSR）是解决局部可观测问题的有效方法，但现有研究在整个状态空间上获取系统的PSR模型，计算复杂、获取模型困难，相关算法仅能应用于较小规模系统。本项目以大规模系统为讨论对象，研究PSR中状态空间划分机制，提出PSR模型的构建方案，并分析如何将获取的PSR模型应用于规划。首先，本项目拟通过确定系统的landmark集合，并以landmark为临界点，将状态空间划分为多个子状态空间，提出状态空间的划分方法;进而，分析子空间本身特性,研究子空间PSR模型的获取方式，并通过子空间PSR模型构建整个系统的PSR模型, 提出基于状态空间划分的PSR模型的获取方案;最后，考虑到获取的模型往往不准确，结合模型本身特点，以大规模系统为应用背景，探讨基于状态空间划分PSR模型的规划算法。通过项目的开展，可望实现PSR方法在大规模系统中的应用，为解决现实世界中广泛存在的局部可观测问题提供有效方案。

动态环境中的智能体，由于受到感知能力限制，往往感知不到环境的某些重要特征，同时，采取动作后有时也会得不到预期效果。在这种局部可观测、随机的系统中如何获取智能体的最优策略，即不确定性环境下的规划问题，是人工智能领域研究的重要问题。常用的解决该问题的途径为首先对系统建模，进而根据模型对问题求解。预测状态表示（PSR）是对系统建模的重要方法，相比局部可观测马尔科夫模型（POMDP），具有易学习、不易陷入局部极小点等诸多优势，近年来，得到越来越多的关注和重视。本项目主要研究了系统预测状态表示模型的获取和应用，项目开展过程中，主要研究了以下内容：1）提出了系统状态空间划分方式，实现了子模型的获取，完成了整个PSR模型的构建，并证明了相关方法理论正确性；2）利用Monte-Carlo Tree Search在大规模空间搜索解决方案的优势，通过提出模型熵的概念，并以模型熵为引导，将系统检验核的发现问题转换为动作决策问题，实现了较大规模系统PSR模型的建立；3）谱方法（Spectral Method）是当前系统PSR模型获取的主要方法，但在构建获取系统PSR模型的Hankel矩阵时，不同检验的集合（列向量）往往导致不同的获取模型精度，通过分析模型熵与模型精度之间的关系，进而通过模型熵确定相应的检验集合，实现了利用谱方法在获取系统PSR模型时预测精度的提高；4）针对获取系统整体模型存在的困难，研究了如何仅针对感兴趣的事件预测的方案，提出了通过建立系统的MDP模型，实现对感兴趣事件的预测，并进一步根据模型熵研究了如何提高模型的精度；5）实际应用中，获取的模型很难完全准确，但现有基于模型的规划，往往假定模型完全准确，本项目研究了模型不准确的情况下，如何获取智能体的规划策略问题；6）研究了其它方法，例如alternating direction method of multipliers （ADMM），在获取系统PSR模型中的应用。通过项目的开展，实现了研究预期中较大规模系统（PocMan, 吃豆人）PSR模型的获取，探讨了基于不准确模型的智能体的决策方案，发表了多项高水平成果，为进一步的研究奠定了坚实基础。