Prioritized Goal Decomposition of Markov Decision Processes: Toward a Synthesis of Classical and Decision Theoretic Planning

Craig Boutilier, Ronen I. Brafman and Christopher Geib
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: cebly,brafman,

We describe an approach to goal decomposition for a certain class of Markov decision processes (MDPs). An abstraction mechanism is used to generate abstract MDPs associated with different objectives, and several methods for merging the policies for these different objectives are considered. In one technique, causal (least-commitment) structures are generated for abstract policies and plan merging techniques, exploiting the relaxation of policy commitments reflected in this structure, are used to piece the results into a single policy. Abstract value functions provide guidance if plan repair is needed. This work makes some first steps toward the synthesis of classical and decision theoretic planning methods.

To appear, IJCAI-97, Nagoya, Japan

Return to List of Papers