Introduction
In AI planning, a fundamental tension exists between computational efficiency and plan quality. Satisficing planners, such as FASTFORWARD, are designed for speed but often produce suboptimal, "messy" plans. Conversely, optimal planners guarantee the best possible solution but suffer from exponential complexity, often failing to solve modest-sized problems within reasonable time limits.
This paper presents a novel framework that bridges this gap by integrating Hierarchical Task Network (HTN) learning with Reinforcement Learning (RL). While HTNs are traditionally hand-coded, recent advances allow them to be learned from plan traces. However, learned models typically focus on reachability rather than quality. By incorporating RL, the authors enable a planner to learn not just how to decompose tasks, but which decompositions lead to the highest-quality (shortest) plans.
The Integrated Framework
The proposed system utilizes a three-stage pipeline to learn and refine planning knowledge:
1. Q-MAKER: Structure and Initial Estimation
Building upon the HTN-MAKER algorithm, Q-MAKER analyzes successful plan traces to "reverse engineer" HTN methods. It identifies task decomposition structures and calculates an initial Q-value for each method based on the rewards (negative plan length) observed in the training data.
2. Q-REINFORCE: Value Refinement
To overcome the limitations of potentially suboptimal training traces, the system employs a Monte Carlo RL approach. Q-REINFORCE performs off-policy exploration in a simulator, testing various task decompositions to refine the Q-values. This allows the agent to discover high-quality paths that may not have been present in the initial training examples.
3. Q-SHOP: Greedy Planning
Q-SHOP is a modified version of the SHOP planner. Instead of selecting the first applicable method, Q-SHOP acts greedily by choosing the decomposition method with the highest learned Q-value for the current task. This synergy allows the planner to maintain the speed of HTN decomposition while prioritizing plan quality.
Experimental Evaluation
The framework was evaluated on two standard benchmarks: BLOCKS-WORLD and SATELLITE. The researchers compared their approach (Phase 1 and Phase 1+2) against state-of-the-art satisficing planners like SGPLAN6 and FASTFORWARD (FF).
Results in Blocks-World
In the BLOCKS-WORLD domain, the refined Q-values (Phase 1+2) allowed Q-SHOP to find the optimal plan in 417 out of 420 test cases. As shown in the figure below, the plan quality of the proposed method remains consistently near-optimal, whereas competing satisficing planners produce significantly longer plans as problem size increases.
Results in Satellite
In the SATELLITE domain, the framework again demonstrated superior plan quality compared to SGPLAN6 and FF. While the ordered decomposition constraint of the underlying SHOP planner occasionally prevented finding the absolute shortest plan, the RL-refined methods consistently outperformed the initial learned methods and standard satisficing tools.
Conclusion
By associating Q-values with (Task, Method) pairs, the authors effectively abstracted the state space, making RL-based planning feasible and efficient. The results demonstrate that integrating HTN structure learning with RL refinement produces a planner that matches the speed of satisficing planners while approaching the quality of optimal planners. Future work will explore more complex, stochastic environments and the integration of advanced RL techniques like Temporal Difference learning.
Summary updated