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

Abstract

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 makessome first steps toward the synthesis of classical and decision theoretic planning methods. 1 Introduction Markov decision processes (MDPs) have become a standard conceptual and computational model for decision theoretic planning (DTP) problems, allowing one to model uncertainty, competing goals, and process-oriented objectives. One of the key drawbacks of MDPs, vis-a-vis ...