# Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version

arXiv: https://arxiv.org/abs/2203.14852 · HTML: https://mlsanity.com/paper/2203.14852/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 28 Mar 2022.

## Builds on (most cited first, 16 of 16)

- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [What Can Learned Intrinsic Rewards Capture?](https://mlsanity.com/paper/1912.05500/) (2019)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning](https://mlsanity.com/paper/2007.06702/) (2020)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Transfer of Deep Reactive Policies for MDP Planning](https://mlsanity.com/paper/1810.11488/) (2018)
- [Generalized Planning With Procedural Domain Control Knowledge](https://mlsanity.com/paper/1910.04999/) (2019)
- [Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version](https://mlsanity.com/paper/2105.04250/) (2021)
- [The Role of Macros in Tractable Planning](https://mlsanity.com/paper/1401.3486/) (2014)

## Built on by (most cited first, 12 of 12)

- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [What Planning Problems Can A Relational Neural Network Solve?](https://mlsanity.com/paper/2312.03682/) (2023)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Learning General Policies with Policy Gradient Methods](https://mlsanity.com/paper/2512.19366/) (2025)
- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains](https://mlsanity.com/paper/2404.02499/) (2024)
- [Language-Based Causal Representation Learning](https://mlsanity.com/paper/2207.05259/) (2022)
- [Property-Guided LLM Program Synthesis for Planning](https://mlsanity.com/paper/2605.16142/) (2026)

## Abstract (arXiv)

Recently, sketches have been introduced as a general language for representing the subgoal structure of instances drawn from the same domain. Sketches are collections of rules of the form C -> E over a given set of features where C expresses Boolean conditions and E expresses qualitative changes. Each sketch rule defines a subproblem: going from a state that satisfies C to a state that achieves the change expressed by E or a goal state. Sketches can encode simple goal serializations, general policies, or decompositions of bounded width that can be solved greedily, in polynomial time, by the SIW_R variant of the SIW algorithm. Previous work has shown the computational value of sketches over benchmark domains that, while tractable, are challenging for domain-independent planners. In this work, we address the problem of learning sketches automatically given a planning domain, some instances of the target class of problems, and the desired bound on the sketch width. We present a logical formulation of the problem, an implementation using the ASP solver Clingo, and experimental results. The sketch learner and the SIW_R planner yield a domain-independent planner that learns and exploits domain structure in a crisp and explicit form.