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:
- Reward Decomposition: The global reward function is split into independent components (e.g., processing different parts in a factory).
- Approximate Abstraction: For each component, only relevant variables are identified, creating smaller "abstract MDPs" that are computationally inexpensive to solve.
- 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.
- 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).
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.
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