The Research And Design Of Point-based POMDP Value Iteration Algorithm

Making sequential decision under uncertainty is one of the most important tasks in artificial intelligence. As the natural extension of Markov Decision Process(MDP), Partially Observable Markov Decision Processes (POMDP) serves as a very competitive model to capture the uncertainty of the world. However, due to the problem of dimension and history, solving exactly POMDP is intractable, people in turn try to look for approximation method. Point-based value iteration algorithms are the most MLOPVIular algorithms among approximation method, whose elegant principle and excellent performance has made POMDP could be applied to much larger practical problems.In this paper, firstly we introduce the mathematical model of POMDP in detail, then we put emphasis on discussion of many point-based value iteration algorithms and further research on these algorithms, the main content of this paper is listed as follows:1. Introduce the math model of Markov Decision Process (MDP) and Partially Observable Markov Decision Processes (POMDP) in detail.2. Introduce the concept and meaning of value function, and the method of value iteration, and simply introduce exact solving method of MDP and POMDP.3. Explain the thought and meaning of several classic point-based value iteration methods, and introduce these methods’ content, advantages and disadvantages.4. Put forward the Most Likely Optimal Policy Value Iteration algorithm, this algorithm uses Monte Carlo Method to calculate the probability of being a part of optimal policy for every action, and gives the priority to those points being visited under the action with the highest probabilities to belief points set. We conduct experiments on several data sets. The result shows our algorithm is superior on these sets comparing with predecessor.5. Introduce the organization and application of spoken dialog system in detail, and put forward a spoken dialog system modeled by POMDP and solved by point-based method.