Efficient planning in stochastic domains through exploiting problem characteristics
Nevin Lianwen Zhang · 1995
Partially observable Markov decision process (POMDP) can be used as a model for planning in stochastic domains. However, general POMDPs are computationally expensive to solve. This paper investigates how might problem characteristics be exploited to cut down computation. We consider planning problems where observations are informative of the world state and there are not much uncertainties in effects of actions. We describe a way of making use of such characteristics to improve previous algorithms for solving POMDPs. Complexity analysis shows that the more informative the observations and the more predictable the effects of the actions, the more improvements can be achieved. Keywords: planning under uncertainty, partially observable Markov decision processes, problem characteristics, policy trees, parsimonious covering 1 Introduction There is a growing interest in using Markov decision processes (MDP) as a model for planning in stochastic domains (Dean and Wellman 1991, Provan and C...