TL;DR
This paper introduces a novel approach to learning "sketch decompositions" for complex planning problems by framing it as a deep reinforcement learning (DRL) task. Instead of relying on traditional, often brittle, rule-based methods, their DRL agent learns to break down problems into manageable sub-problems, significantly improving planning efficiency and scalability.
What Problem Does This Paper Address?
Achieving goals in long-horizon planning tasks (where many actions are needed) is a significant challenge. A common strategy is to decompose these problems into smaller, more manageable sub-problems, often by identifying "subgoal structures." These structures, formalized as "sketches," allow planners to solve problems more efficiently. Existing methods for learning these sketches, however, struggle with scalability and expressivity, often requiring complex feature engineering and combinatorial solvers. This paper aims to overcome these limitations by leveraging DRL to learn these decompositions.
Methods
The core innovation is reframing the learning of sketch decompositions as a DRL problem. Specifically, they adapt an actor-critic DRL algorithm. The key modification is in how the "successor states" are defined: instead of just immediate next states, they consider states reachable within a bounded search (IW(k) search). This allows the DRL agent to learn "jumps" that represent solving sub-problems. The learned policy then implicitly defines the sketch decomposition. While the resulting decompositions are not explicit rules, the authors demonstrate they can often be interpreted.
Datasets
The authors evaluate their method on a variety of standard planning domains, including:
- Blocks (with single and multiple tower goals)
- Childsnack
- Delivery
- Grid
- Gripper
- Logistics
- Miconic
- Reward
- Spanner
- Visitall
These domains are primarily drawn from previous work on learning sketches and general policies. The evaluation uses 40 larger test instances for each domain, extending those used in prior studies.
Key Insights and Ideas
- DRL for Decomposition: The paper demonstrates that DRL can effectively learn complex problem decompositions, offering a more scalable and potentially more expressive alternative to traditional symbolic methods.
- IW(k) as "Jumps": By defining successor states as those reachable via IW(k) search, the DRL agent learns to make "jumps" that correspond to solving sub-problems, effectively learning sketch decompositions.
- Interpretable Decompositions: Despite not producing explicit rules, the learned decompositions are often interpretable, allowing researchers to understand the learned strategies.
- Width as a Guiding Principle: The concept of "width" from classical planning is central, guiding the search for sub-problems that can be solved efficiently.
Key Results
- High Coverage: The proposed method achieves nearly perfect coverage across most domains, significantly outperforming baselines in challenging domains like Logistics and Grid, especially for width-2 decompositions.
- Scalability: The DRL approach scales better than combinatorial methods, handling larger instances and avoiding the need for explicit feature pools.
- Interpretable Subgoal Structure: Analysis of generated plans reveals that the learned decompositions often align with intuitive, interpretable sketches (e.g., R1-R4 described in the paper).
- Plan Quality: While the primary focus is on decomposition and coverage, the plan lengths are competitive, often close to optimal or LAMA's performance, though sometimes longer due to the abstraction of action costs.
Limitations and Future Work
- Plan Length Optimization: The current method prioritizes finding subgoals that reduce the problem size but doesn't explicitly optimize for the cost of solving those subgoals. Future work could incorporate subproblem costs into the DRL training to reduce overall plan lengths.
- Two-Level Hierarchies: The authors suggest exploring two-level hierarchical policies to further reduce the reliance on IW(k) searches within subproblems.
- GNN Expressivity: For certain domains and widths (e.g., width-1 in Logistics and Grid), GNNs may have limitations in fully capturing the sketch decompositions, suggesting potential avenues for architectural improvements.
Summary updated