It has been observed that many classical planning domains with atomic goals can be solved by means of a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width, which in these cases is bounded and small. Yet, while the notion of width has become part of state-of-the-art planning algorithms such as BFWS, there is no good explanation for why so many benchmark domains have bounded width when atomic goals are considered. In this work, we address this question by relating bounded width with the existence of general optimal policies that in each planning instance are represented by tuples of atoms of bounded size. We also define the notions of (explicit) serializations and serialized width that have a broader scope as many domains have a bounded serialized width but no bounded width. Such problems are solved non-optimally in polynomial time by a suitable variant of the Serialized IW algorithm. Finally, the language of general policies and the semantics of serializations are combined to yield a simple, meaningful, and expressive language for specifying serializations in compact form in the form of sketches, which can be used for encoding domain control knowledge by hand or for learning it from small examples. Sketches express general problem decompositions in terms of subgoals, and sketches of bounded width express problem decompositions that can be solved in polynomial time.

许多具有原子目标的经典规划领域可以通过一个简单的多项式探索过程（称为IW）解决，该过程在问题宽度的指数时间内运行，而在这些情况下问题宽度是有界且较小的。本文通过将有界宽度与每个规划实例中表示为有界大小的原子元组的一般最优策略的存在相关联，解答了为什么在考虑原子目标时许多基准领域具有有界宽度的问题。此外，我们还定义了（显式）串行化和序列化宽度的概念，这些概念具有更广泛的范围，因为许多领域具有有界序列化宽度但没有有界宽度。这些问题可以通过序列化IW算法的适当变体在多项式时间内非最优地解决。最后，一般策略的语言和串行化的语义结合起来，以便以简洁的形式用草图指定串行化，这些草图可以通过手工编码领域控制知识或从小例子中进行学习。有界宽度的草图以多项式时间解决问题的分解表达一般问题分解。

一般政策、子目标结构和规划宽度