Definition 4 (Reachable State) Let (O, I, G) be a planning problem and let P be the set of ground atoms that occur in the problem. We say that a state s ⊆ P is reachable, iff there exists a sequence (01, . . ,0n) out of actions in O for which s = Result(I, (01, . . ,0n))
hold s.

Definition 5 (Generic State s [ A,-B ]) Let ( O, I, G ) be a planning problem.  By s ( A,-B )
we denote any reachable state in which A has just been achieved, but B is FALSE,
i.e., B & s(A,-B) and there is a sequence of actions (01,..,on) such that s(A,-B) =
Result(I, (01, . . , 0n )), with A E add(0n).

One can imagine s{A,-B} as a state about which we only have incomplete information.

All the states s it represents satisfy s = A, ¬ B, but the other atoms p ∈ P with p ̸ = A, B can adopt arbitrary truth values.

Definition 6 (Reduced Action Set OA ) Let (O, I, G) be a planning problem, and let A E G be an atomic goal. By OA we denote the set of all actions that do not delete A,
i.e., OA = {o E O | A & del(o)}.

We are now prepared to define what we exactly mean by forced and reasonable goal orderings.

Definition 7 (Forced Ordering ≤ f ) Let ( O, I, G ) be a planning problem, and let A, B E
G be two atomic goals. We say that there is a forced ordering between B and A, written B ≤ f A, if and only if V S(A,-B) :  ¬¬ P° :  B E Result(s(A,-B); P°)
If Definition 7 is satisfied, then each plan achieving A and B must achieve B before or simultaneously with A, because otherwise it will encounter a deadlock, rendering the problem unsolvable. Definition 8 (Reasonable Ordering ≤ r) Let (O, I, G) be a planning problem, and let A, B E G be two atomic goals. We say that there is a reasonable ordering between B and A, written B ≤ r A, if and only if
∀ s(A,¬B) :  ¬∃ P°A ;  B E Result(s(A,¬B), P°A )
Definition 8 gives B ≤ r A the meaning that if, after the goal A has been achieved, there is no plan anymore that achieves B without—at least temporarily—destroying A, then B
is a goal prior to A.

We remark that obviously B < f A implies B < r A, but not vice versa. We also make a slightly less obvious observation at this point: The formulae in Definitions 7 and 8 use a universal quantification over states s(A,-B). If in a planning problem there is no such state at all, the formulae are satisfied and the goals A and B get ordered, i.e., B < f A and B <, A follow, respectively. In this case, however, there is not much information gained by a goal ordering between A and B , because any sequence of actions will achieve B prior or simultaneously with A —A cannot be achieved with B still being FALSE . Thus in this case, the ordering relations B < t A and B < r A are trivial in the sense that no reasonable planner would invest much effort in considering the goals A and B ordered the other way round anyway.