Tech Report CS-94-20

Acting Optimally in Partially Observable Stochastic Domains

Anthony R. Cassandra, Leslie Pack Kaelbling and Michael L. Littman

April 1994

Abstract:

In this paper, we describe the partially observable Markov decision process ({\sc pomdp}) approach to finding optimal or near-optimal control strategies for partially observable stochastic environments, given a complete model of the environment. The {\sc pomdp} approach was originally developed in the operations research community and provides a formal basis for planning problems that have been of interest to the AI community. We found the existing algorithms for computing optimal control strategies to be highly computationally inefficient and have developed a new algorithm that is empirically more efficient. We sketch this algorithm and present preliminary results on several small problems that illustrate important properties of the {\sc pomdp} approach.

(complete text in pdf or gzipped postscript)