

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

## 3.1 The Axiomatic Planning Framework

The axiomatic framework makes only a minimum of assumptions about the underlying formalism. It may be instantiated to any planning formalism that defines some concept of a planning problem a domain of entities called actions and a validity test. The planning problem is assumed to consist of planning problem instances (PPIs), 3 with no further assumptions about the inner structure of these. The validity test is a truth-valued function taking a PPI and a sequence of actions as arguments. If the validity test is true for a PPI Π
and an action sequence 1 n then the action sequence   1 n is said to solve I. While the inner structure of the PPIs and the exact definition of the validity test are crucial for any specific planning formalism, many results in this article can be proven without making any such further assumptions. Results on the computational complexity of certain problems will make an assumption about the complexity of the validity test, though. Based on these concepts, the notion of plans can be defined in the usual way.

Definition 3.1 A total-order plan (t.o. plan) is a sequence of actions, l l n which can alternatively be denoted by the tuple where for 1 l n
. Given a PPI II,
 is said to be Π-valid iff the validity test is true for Π
i k and