General Policies, Serializations, and Planning Width
  It has been observed that in many of the benchmark planning domains, atomic
goals can be reached with a simple polynomial exploration procedure, called IW,
that runs in time exponential in the problem width. Such problems have indeed a
bounded width: a width that does not grow with the number of problem variables
and is often no greater than two. Yet, while the notion of width has become
part of the state-of-the-art planning algorithms like BFWS, there is still no
good explanation for why so many benchmark domains have bounded width. In this
work, we address this question by relating bounded width and serialized width
to ideas of generalized planning, where general policies aim to solve multiple
instances of a planning problem all at once. We show that bounded width is a
property of planning domains that admit optimal general policies in terms of
features that are explicitly or implicitly represented in the domain encoding.
The results are extended to much larger class of domains with bounded
serialized width where the general policies do not have to be optimal. The
study leads also to a new simple, meaningful, and expressive language for
specifying domain serializations in the form of policy sketches which can be
used for encoding domain control knowledge by hand or for learning it from
traces. The use of sketches and the meaning of the theoretical results are all
illustrated through a number of examples.
