Partially observable Markov decision process (POMDP) is a formal model for planning in stochastic domains. In a POMDP, the state of world is not known with certainty and the effects of actions are nondeterministic. It can potentially be employed in a wide range of applications, including medical decision making and robot planning. However computational difficulties have limited its actual use....[ Read more ]

Partially observable Markov decision process (POMDP) is a formal model for planning in stochastic domains. In a POMDP, the state of world is not known with certainty and the effects of actions are nondeterministic. It can potentially be employed in a wide range of applications, including medical decision making and robot planning. However computational difficulties have limited its actual use.

At the present time, the most efficient exact algorithm for finding optimal policies for POMDP is incremental pruning. In this thesis, two methods are proposed to speed up incremental pruning. The first method is called quality retaining approximation, which employs approximation technique in the exact solution algorithm. For each iteration, the error is bounded by a pre-determined value. The second method is point-based improvement. The underlying idea is similar to that behind modified policy iteration for fully observable Markov decision processes (MDPs). We find that the techniques can make solving POMDPs several orders of magnitude faster. We will explain how to integrate these concepts with incremental pruning and their benefits. For each approach, the effectiveness will be demonstrated with experiments.