【作者】 韩冰；

【导师】 李宣东； 刘峰；

【作者基本信息】 南京大学 ， 软件工程（专业学位）， 2014， 硕士

【摘要】 如何在不完全确定的状态信息下制定一系列的决策一直都是人工智能领域研究的一个重要主题。部分可观察的马尔科夫决策过程(POMDP)能够帮助智能体从环境中获取不完全确定的状态信息并制定收益较高的决策,因而具有很高的实用价值。但由于POMDP问题采用精确求解是NP难问题,因此精确求解的方案在实际的应用中受到了极大的限制。现在人们主要采用近似求解的方法,这样的方法比精确求解具备更好的性能,应用范围更加广泛。本文先介绍了马尔科夫决策过程(MDP)以及它的拓展——部分可观察的马尔科夫决策过程(POMDP)相关概念和数学模型。通过对精确计算的算法描述和探讨引出现在较为实用的近似算法并对其中具有代表性的PBVI、Perseus和PBPI等方法进行分析。对于这些方法,本文主要介绍各个算法在点集选取和值函数迭代上处理的不同,并分析了这些算法的优点和缺点。本文提出在基于点的策略迭代基本思想上结合聚类的求解算法PCFBPI (Point Clustering Feature Based Policy Iteration)。本文重点关注了可达点在信念空间上的分布特点。并根据该特点制定考察点的选取策略和拓展方法。本文根据提出的算法介绍了代码实现,并在具有代表性的几个数据集上进行与已有算法PBPI的对比实验。通过实验对比可以看出：本文提出的算法利用了大量可达点的聚类信息,其性能相比PBPI在整体上有所提高,但在规模较小的问题模型上性能优势并不明显。更多还原

【Abstract】 How to make a series of decisions in the state information which is not completely determined has always been an important topic in the field of artificial intelligence. Partially observable Markov decision processes (POMDP) can help the agent to obtain status information which is not completely observed from the environment and to develop high reward decision, thus it has high practical value. But because solving the POMDP problems in precise ways is non-polynomial hard problem. So the solution with precise computing is extremely limited in practical application. Now people mainly use the approximation methods. These method have better performance than the exact ones and have a wider range of applications.This paper firstly introduces concepts and mathematical models of the Markov decision process (MDP) and the extended part of it:partially observed Markov decision process (POMDP). Based on the description and discussion of the methods with precise calculation, this paper introdeces some practical approximation algorithms and compares some representative ones:PBVI, Perseus and PBPI methods, etc. For these methods, this paper mainly compares and analyses the differences of point set selection and value function iteration in each algorithm.According to the algorithms and the research results that already exist, this paper puts foward PCFBPI(Point Clustering Feature Based Policy Iteration) algorithm which is based on clustering method and point based policy iteration. This paper focuses on the study of the distribution of reachable points in the belief space. And It discusses the strategies of the point set’s selection and expansion by making the use of characteristics of the reachable points’distribution in the belief space. According to the algorithm proposed in this paper, the implementation code is introduced. After the introduction there is an experiment comparing PCFBPI (Point Clustering Feature Based Policy Iteration) with PBPI on several representative POMDP models.Experimental results show the proposed algorithm in this paper compared with PBPI is improved in the use of clustering reachable points. But in the problem whose model is small, PCFBPI’ advantage is not obvious.更多还原