Planning Under Uncertainty: Structural Assumptions and Computational Leverage

Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4

Thomas Dean
Department of Computer Science
Brown University
Providence, RI 02912, U.S.A.

Steve Hanks
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195 U.S.A.

The problem of planning under uncertainty has been addressed by researchers in many different fields, adopting rather different perspectives on the problem. Unfortunately, these researchers are not always aware of the relationships among these different problem formulations, often resulting in confusion and duplicated effort. Many probabilistic planning or decision making problems can be characterized as a class of Markov decision processes that allow for significant compression in representing the underlying system dynamics. It is for this class of problems that we as experts in intensional representations are advantageously positioned to contribute efficient solution methods. This paper provides a general characterization of the representational requirements for this class of problems, and we describe how to achieve computational leverage using representations that make different types of dependency information explicit.

Unpublished Manuscript

Return to List of Papers