# On The Compilability And Expressive Power Of Propositional Planning Formalisms

Bernhard Nebel NEBEL@INFORMATIK.UNI-FREIBURG.DE
Institut fur Informatik, Albert-Ludwigs-Universit ¨ at, Georges-K ¨ *ohler-Allee, D-79110 Freiburg, Germany* ¨

## Abstract

The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of "expressive power" is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of "compilation schemes" between planning formalisms. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the "compilability" framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved linearly. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.

## 1. Introduction

GRAPHPLAN (Blum & Furst, 1997) and SATPLAN (Kautz & Selman, 1996) are among the most efficient planning systems nowadays. However, it is generally felt that the planning formalism supported by these systems, namely, propositional basic STRIPS (Fikes & Nilsson, 1971), is not expressive enough. For this reason, much research effort (Anderson, Smith, & Weld, 1998; Gazen
& Knoblock, 1997; Kambhampati, Parker, & Lambrecht, 1997; Koehler, Nebel, Hoffmann, & Dimopoulos, 1997) has been devoted in extending GRAPHPLAN in order to handle more powerful planning formalisms such as ADL (Pednault, 1989).

There appears to be a consensus on how much *expressive power* is added by a particular language feature. For example, everybody seems to agree that adding negative preconditions does not add very much to the expressive power of basic STRIPS, whereas conditional effects are considered as a significant increase in expressive power (Anderson et al., 1998; Gazen & Knoblock, 1997; Kambhampati et al., 1997; Koehler et al., 1997). However, it is unclear how to measure the expressive power in a more formal way. Related to this problem is the question of whether "compilation" approaches to extend the expressiveness of a planning formalism are optimal. For example, Gazen and Knoblock (1997) propose a particular method of compiling operators with conditional effects into basic STRIPS operators. This method, however, results in exponentially larger operator sets.

While most people (Anderson et al., 1998; Kambhampati et al., 1997; Koehler et al., 1997) agree that we cannot do better than that, nobody has proven yet that a more space-efficient method is impossible.