# Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning First-Order Symbolic Representations for Planning from the Structure of the State Space](https://mlsanity.com/paper/1909.05546/) (2019)
- [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)
- [Features, Projections, and Representation Change for Generalized Planning](https://mlsanity.com/paper/1801.10055/) (2018)
- [Unsupervised Grounding of Plannable First-Order Logic Representation from Images](https://mlsanity.com/paper/1902.08093/) (2019)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Learning General Policies from Small Examples Without Supervision](https://mlsanity.com/paper/2101.00692/) (2021)
- [HDDL -- A Language to Describe Hierarchical Planning Problems](https://mlsanity.com/paper/1911.05499/) (2019)

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

- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022)
- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Target Languages (vs. Inductive Biases) for Learning to Act and Plan](https://mlsanity.com/paper/2109.07195/) (2021)
- [Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning](https://mlsanity.com/paper/2106.04866/) (2021)
- [A Reminder of its Brittleness: Language Reward Shaping May Hinder Learning for Instruction Following Agents](https://mlsanity.com/paper/2305.16621/) (2023)
- [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)
- [Revisiting Landmarks: Learning from Previous Plans to Generalize over Problem Instances](https://mlsanity.com/paper/2508.21564/) (2025)

## Abstract (arXiv)

Width-based planning methods deal with conjunctive goals by decomposing problems into subproblems of low width. Algorithms like SIW thus fail when the goal is not easily serializable in this way or when some of the subproblems have a high width. In this work, we address these limitations by using a simple but powerful language for expressing finer problem decompositions introduced recently by Bonet and Geffner, called policy sketches. A policy sketch over a set of Boolean and numerical features is a set of sketch rules that express how the values of these features are supposed to change. Like general policies, policy sketches are domain general, but unlike policies, the changes captured by sketch rules do not need to be achieved in a single step. We show that many planning domains that cannot be solved by SIW are provably solvable in low polynomial time with the SIW_R algorithm, the version of SIW that employs user-provided policy sketches. Policy sketches are thus shown to be a powerful language for expressing domain-specific knowledge in a simple and compact way and a convenient alternative to languages such as HTNs or temporal logics. Furthermore, they make it easy to express general problem decompositions and prove key properties of them like their width and complexity.