Black Box and Generalized Algorithms for Planning in Uncertain Domains
We propose to investigate planning algorithms applicable to diverse real-world problems. Many such problems can be formalized as Markov Decision Processes (MDPs), which can represent domains where actions have stochastic outcomes. We consider extensions to the MDP framework that model other types of uncertainty, including uncertainty about the costs of actions, uncertainty due to other agents in the world, and partial observability. We also address some of these problems in an online setting.
This work makes extensive use of two tools: first, the reduction of more complex planning problems (larger domains, more types of uncertainty) to simpler problems where fast existing algorithms can be applied. This approach uses the existing algorithms in a purely ``black box'' fashion. Our second approach is to take algorithms for simpler problems and generalize them (and hopefully their performance advantages) to harder planning domains. As an example of the first approach, we show how to use fast algorithms for standard MDPs to solve a more general class of problems where there is uncertainty about the costs of actions. As an example of the second approach, we generalize Dijkstra's algorithm and Gaussian Elimination to solve MDPs. We then discuss several other areas where we hope similar techniques will yield efficient new algorithms.
full text of the proposal [ps]
slides [powerpoint slideshow]
The HTML version seems to only work on IE, and then not very well. Not recommended. slides [html]