We call the resulted graph the *ordering graph* of the problem, since it denotes the order in which the subgoals have to be achieved. Figure 5 shows the *ordering graph* for the problem of Figure 3. Lines with arcs denote ordering constraints. Double-lines without arcs denote that the two facts are ordered together.

Proposition 8. The ordering graph is an acyclic graph.

Proof sketch: The proof can be based on the way in which the facts are achieved in the PreProcessing Algorithm (Section 2.4). Actually, facts are achieved in a specific time order (in case where a fact has been re-achieved with smaller cost, we consider the last time it has been achieved). We define the ordering relation < between facts, denoting that a fact has been achieved before another in the Pre-Processing Algorithm. Similarly we define the ≤ relation.

Ordering relations between the subgoals originate in two ways. Firstly, subgoals of type (II) of the same XOR-constraint are ordered explicitly to each other, according to the time they have been achieved (in Figure 5 these ordering relations are denoted with non-dashed lines with arcs). Secondly, each subgoal of type (I) is ordered before than or at least at the same time with the previous one of its corresponding type (II) subgoal (in Figure 5 these ordering relations are denoted with dashed lines with arcs). Using the above equivalences, we can transform the ordering graph to an equivalent time-ordering graph. Since a time-ordering relation cannot include cycles, the same happens for the ordering graph. 

The ordering graph makes it possible to construct intermediate, possibly incomplete, states, which have to be achieved sequentially. Starting from the initial state, GRT attempts to insert one subgoal from each XOR-constraint in each intermediate state. This fact must have the following properties:

 It has not been inserted in a previous intermediate state, it is not ordered after some other fact of the same XOR-constraint that has not yet been inserted in a previous intermediate state, and finally it is not ordered together with a fact of another XOR-constraint that cannot be inserted in the current intermediate state.
In case where there are more than one facts with the above properties for a single XORconstraint, the selection among them is done arbitrarily. Finally, in case where no fact with the above properties exists for an XOR-constraint, the intermediate state is left incomplete.

Corollary 4. It is always possible to construct the intermediate states. 

Corollary 4 follows from Proposition 8. Since the ordering graph is a directed acyclic graph, it is always possible to find at least one subgoal to be included in the next intermediate state. The number of subgoals is an upper bound for the number of the intermediate states that will be constructed. 

From the ordering graph of Figure 5, the following intermediate states can be extracted:
Intermediate state 1: ( (*at R1 n3_0) (at R2 n3_3*) (*in K1 R1) (in K2 R2*) ) Intermediate state 2: ( (*at R1 n1_1*) (*at R2 n1_3) (at K1 n1_1*) (*at K2 n1_3*) )
Intermediate state 3: ( (*at R1 n0_0*) (*at R2 n0_3*) (*at K1n1_1*) (*at K2 n1_3*) )
where the last state is the goal state. 

After the construction of the intermediate states, the planner has to solve three sub-problems, which are easier than the original one; thus, the overall time to solve them is shorter than the time 