Definition 9 (Trivial Ordering Relation) Let (O,I,G) be a planning problem, and let A, B E G be two atomic goals. An ordering relation B ≤ f A or B ≤ r A is called trivial iff there is no state s(A,-B).

In this paper, we will usually consider forced and reasonable goal orderings as non-trivial orderings and make the distinction explicit only if we have to do so.

Definitions 7 and 8 seem to deliver promising candidates for an achievement order.

Unfortunately, both are very hard to test: it turns out that their corresponding decision problems are PSPACE hard.

Theorem 1 Let F_ORDER denote the following problem:
Given two atomic facts A and B i as well as an action set O and an initial state Z i does B ≤ ƒ A hold ?

Deciding FORDER is PSPACE-hard.

Proof: The proof proceeds by polynomially reducing PLANSAT (Bylander, 1994)—the decision problem of whether there exists a solution plan for a given arbitrary STRIPS
planning instance—to the problem of deciding F_ORDER.

Let I, G, and O denote the initial state, the goal state, and the action set in an arbitrary STRIPS instance. Let A, B, and C be new atomic facts not contained in the instance so far. We build a new action set and initial state for our F_ORDER instance by setting

$${\mathcal{O}}^{\prime}:={\mathcal{O}}\cup\left\{\begin{array}{l l l}{o_{I_{1}}}&{=\{C\}}&{\longrightarrow\mathrm{\ADD\}\{A\}\mathrm{\DEL\}\{C\},}\\ {o_{I_{2}}}&{=\{A\}}&{\longrightarrow\mathrm{\ADD\}{\mathcal{I}}\mathrm{\ DEL\}\{A\},}\\ {o_{G}}&{={\mathcal{G}}}&{\longrightarrow\mathrm{\ADD\}{\mathcal{B}}\mathrm{\ DEL\}\emptyset}\end{array}\right\}$$

and

$$T\,:=\{C\}$$

With these definitions, reaching B from A is equivalent to solving the original problem. The other way round, unreachability of B from A —forced ordering B ≤ t A —is equivalent to the unsolvability of the original problem. In order to prove this, we consider the following:
The only way of achieving A is by applying oj, to I'. Consequently, the only state s(A,-B)
is {A}, cf. Definition 5. Thus starting with the assumption that B </A is valid, we apply the following equivalences:
B ≤ f A

$\Leftrightarrow\quad\forall\;s_{(A,\;\neg B)}:\;\neg\exists\;\mathcal{P}^{\mathcal{O}^\vee}:B\;\in Result(s_{(A,\;\neg B)},\mathcal{P}^{\mathcal{O}}\;)$ . 
$\text{cf.Definition7}$ . 
 \#

$$\neg\exists\;{\mathcal{P}}^{\mathcal{O}}\;\colon\;B\,\in\,R e s u l t(\{A\},{\mathcal{P}}^{\mathcal{O}^{\dagger}})$$
$\{A\}$ is the only reachable state $s_{(A,\neg B)}$ with the definition of $\mathcal{C}^{\prime}$.  

$$\mathrm{w}\,\mathrm{i}\,\mathrm{t}\mathrm{l}$$

with the definition of O'
¬¬
f no solution plan exists for I, G and given O
f