Expressing and Exploiting the Common Subgoal Structure of Classical
  Planning Domains Using Sketches: Extended Version
  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.
