size of the plan in the source formalism, or a size bounded polynomially by the original planning instance and the original plan.

Although the compilability framework appears to be a straightforward and intuitive tool for measuring the expressiveness of planning formalisms, it is possible to come up with alternative measures. B¨ackstr¨om (1995), for instance, proposed to use *ESP-reductions*, which are polynomial many-one reductions on planning problems that preserve the plan size exactly. However, requiring that the transformation should be polynomial-time computable seems to be overly restrictive. In particular, if we want to prove that one formalism is not as expressive as another one, we had better proven that there exists no compilation scheme regardless of how much computational resources the compilation process may need. Furthermore, there appear to be severe technical problems to using B¨ackstr¨om's (1995) framework for proving negative results. On the other hand, all of the positive results reported by B¨ackstr¨om are achievable in the compilation framework because the transformations he used are in fact compilation schemes. Taking all this together, it appears to be the case that the compilation framework is superior from an intuitive and technical point of view.

Another approach to judging the expressiveness of planning formalisms has been proposed by Erol and colleagues (1994, 1996). They measure the expressiveness of planning formalisms according to the set of plans a planning instance can have. While this approach contrasts hierarchical task network planning nicely with STRIPS-planning, it does not help us in making distinctions between the formalisms in the S-family.

The compilability framework is mainly a theoretical tool to measure how concisely domain structures and plans can be expressed. However, it also appears to be a good measure of how difficult planning becomes when a new language feature is added. *Polynomial-time* compilation schemes that preserve the plan size linearly indicate that it is easy to integrate the feature that is compiled away. One can either use the compilation scheme as is or mimic the compilation scheme by extending the planning algorithm. If only a polynomial-time compilation scheme leading to a polynomial growth of the plan is possible, then this is an indication that adding the new feature requires most probably a significant extension of the planning algorithm. If even a compilation scheme preserving plan size polynomially can be ruled out, then there is most probably a serious problem integrating the new feature.

Using this framework, we analyzed a large family of planning formalisms ranging from basic STRIPS to formalisms with conditional effects, boolean formulae, and incomplete state specifications. The most surprising result of this analysis is that we are able to come up with a complete classification. For each pair of formalisms, we were either able to construct a polynomial-time compilation scheme with the required size bound on the resulting plans or we could prove that compilation schemes are impossible—even if the computational resources for the compilation process are unbounded. In particular, we showed for the formalisms considered in this paper:
 incomplete state specifications and literals in preconditions can be compiled to basic STRIPS
preserving plan size exactly, incomplete state specifications and literals in preconditions and effect conditions can be compiled away preserving plan size exactly, if we have already conditional effects,