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

Craig Boutilier, Ronen I. Brafman, Christopher W. Geib

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 merged using classical planning techniques.

Introduction

This research represents a foundational attempt to bridge the gap between two historically distinct paradigms: Classical Planning, which excels at decomposing complex problems into subgoals, and Decision-Theoretic Planning, which utilizes Markov Decision Processes (MDPs) to handle uncertainty and competing objectives. By synthesizing these approaches, the authors aim to overcome the scalability issues inherent in large-scale MDPs.

The Scalability Challenge

Markov Decision Processes are the standard for planning under uncertainty, yet they suffer from the "curse of dimensionality." To find an optimal policy, standard algorithms typically explore every possible state. As the number of features increases, the state space grows exponentially, rendering MDPs impractical for complex real-world tasks. Classical planners mitigate this through goal decomposition—solving for individual goals separately and merging the plans—but these plans are often too rigid for stochastic environments.

Methodology: Prioritized Goal Decomposition

The authors propose a framework for Prioritized Goal Decomposition that breaks a complex MDP into manageable components:

  1. Reward Decomposition: The global reward function is split into independent components (e.g., processing different parts in a factory).
  2. Approximate Abstraction: For each component, only relevant variables are identified, creating smaller "abstract MDPs" that are computationally inexpensive to solve.
  3. Causal Link Extraction: The "Most Likely Execution Path" (MLEP) of an abstract policy is analyzed to identify the causal reasons behind actions. This transforms a rigid MDP policy into a "Least-Commitment Plan" (LCP), revealing which actions are essential and which can be reordered.
  4. Prioritized Merging: Sub-policies are merged using state-space search (guided by value functions as heuristics) or plan-based merging (using causal links to prevent goal interference).
Table 1: Action specifications for the Job Shop Domain, illustrating the stochastic nature of the environment and context-dependent effects.

Key Insights: Synthesis of Paradigms

A central contribution is the realization that MDP policies are often "over-committed." By extracting causal links, the authors reveal the "hidden flexibility" in an MDP policy, allowing for more robust merging. Furthermore, the value function of a sub-MDP serves as an admissible heuristic; since it represents the maximum possible value for a goal, any negative interaction with other goals can only decrease this value, making it a powerful guide for global search.

Figure 1: A merged plan for multiple goals (P1 and P2) utilizing causal links to manage interactions and ensure goal achievement.

Experimental Evaluation: The Job Shop Domain

The framework was evaluated using a Job Shop Domain, a robot part-processing task. Actions such as drill, press, and paint have probabilistic effects—for example, drilling may cause a bit to overheat, necessitating a cooling action. The decomposition approach successfully reduced a massive state space into several tiny sub-problems (e.g., 8 to 16 states). The merging process effectively resolved conflicts, such as reordering actions to allow a drill bit to cool, which were not apparent when considering goals in isolation.

Conclusion and Future Directions

The paper demonstrates that prioritized goal decomposition can significantly reduce the computational burden of solving large MDPs while maintaining near-optimal performance. While the current method for extracting causal links assumes a dominant "primary" effect for actions, future work will explore applications in highly volatile environments and perpetual MDPs where the agent must maintain a state indefinitely.

Summary updated

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 t echnique, causal (least-commitment) structures are generated for
BibTeX
@inproceedings{boutilier1997prioritized,
  author = {Craig Boutilier and Ronen I. Brafman and Christopher W. Geib},
  title = {{Prioritized Goal Decomposition of Markov Decision Processes: Toward a Synthesis of Classical and Decision Theoretic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure