
## 2. Basic Formalism And Causal Graphs

In this paper we consider only propositional planning problems, using the **propositional**
strips with negative goals **formalism (Bylander, 1994), in which both positive and negative**
preconditions are allowed. Following B¨ackstr¨om and Klein (1991b), we distinguish between preconditions and prevail conditions. In the former case the variable involved changes its value after the operator is executed, while in the latter case the value does not change. The post-condition of an operator expresses which state variables it changes and what values these variables will have after executing the operator. The **pre-condition specifies which** values these changed variables must have before the operator is executed. The prevail condition specifies which of the unchanged variables must have some specific value before execution of the operator and what these values are. Hence, prevail conditions, such as having a visa, are needed in order to apply an operator, such as Enter-USA, but their values do not change after the operator is applied. Finally, **we assume that an operator is** applicable if and only if both its pre- and prevail conditions are satisfied.

Formally, we assume that a problem instance is given by a quadruple Π = hV,Λ**, Init, Goal**i, where:

- V = {v1, . . . , vn} is a set of propositional state variables**, each one with an associated**
binary domain D(vi). The domain D(vi) of the variable viinduces an **extended domain**
D+(vi) = D(vi) ∪ {u}, where u denotes the unspecified **value.**
- Init is an initial, fully specified state, i.e. Init ∈ D(v1) × . . . × D(vn).

- Goal **is a set of possible goal states. We assume that such a set is specified by a partial**
assignment on V, thus Goal ∈ D+(v1) × . . . × D+(vn).

- Λ = {A1, . . . , AN } is a finite set of operators **of the form** hpre, post, prvi**, where**
pre, post, prv ⊆ D+(v1) × . . . × D+(vn**) denote the pre-, post-, and prevail condition,**
respectively. In what follows, by pre(A), post(A**), and** prv(A) we denote the corresponding conditions of an operator A**, and by** pre(A)[i], post(A)[i**], and** prv(A)[i**] the**
corresponding values of the variable vi.
For every vi ∈ V**, we must have either** pre(A)[i] = u or prv(A)[i] = u**. Further,**
post(A)[i] 6= u **if and only if** pre(A)[i] 6= u**, in which case** post(A)[i] 6= pre(A)[i].

In this paper we analyse only planning problems with unary **operators. Therefore, in**
what follows, we assume that, for each operator A ∈ **Λ, we have that:**
1. there exists a variable vi ∈ V**, such that** pre(A)[i] 6= u**, and**

2. for each other variable vj **∈ V − {**vi}, pre(A)[j] = u.
Note that specifying both pre- and postconditions in case of **only propositional variables**
is redundant, and we use it only to simplify the presentation. Likewise, our assumption that post(A) 6= u **implies** pre(A) 6= u is different from the usual strips **formalism, and requires**
an exponential time translation in general. However, in our **case of only unary operators,** this translation takes only linear time.