The role of representation and abstraction in stochastic planning

Markov decision process (MDP), originally studied in the Operations Research (OR) community, provides a natural framework to model a wide variety of sequential decision making problems. Because of its powerful expressiveness, the AI community has adopted the MDP framework to model complex stochastic planning problems. However, this expressiveness in modeling comes with a hefty price when it comes to solving the MDP model and obtaining an optimal plan. Scaling up solution algorithms for MDPs is thus a critical research topic in AI that has received a lot of attentions. In this thesis I study the role of representation and abstraction in scaling up solution methods for various MDP models. Three variants of MDP models are studied in this thesis: A discrete state, fully observable model; a continuous state, fully observable model; and a discrete state, partially observable model. One contribution of this thesis is the development of new algorithms for these models that use various representations to exploit natural state abstractions. These new algorithms significantly increase the range of problems that can be solved in practice. A second contribution is the formulation of a new type of belief-space structure in partially observable MDPs. Using a region-based representation, new algorithms are able to reduce the computational time exponentially while still maintaining the optimality of the solution. This presents a breakthrough in scalability studies for this model. The results open up a range of opportunities to gain better understanding of the model and its complexity, and to develop better computational solutions