The process, which decides whether an atomic goal B is heuristically ordered before another goal A (i.e., whether B <h A holds) proceeds in exactly the same way as described in Section 3.2: The False set FAA for A is reduced by the fixpoint computation, which remains unchanged, but employs the updated routines for computing O* and for deciding pA( f, O*). As a result, B is ordered before A ( B ≤ h A ) if and only if it is not possibly aievable pA(B, O*) using the action set that results from the fixpoint.

## 4. The Use Of Goal Orderings During Planning

After having determined the ordering relations that hold between pairs of atomic goals from a given goal set, the question is how to make use of them during planning. Several proposals have been made in the literature, see Section 6 for a detailed discussion. In this paper, we propose a novel approach that extracts an explicit ordering between subsets of the goal set—called the goal a genda . The planner, in our case IPP, is then run successively on the planning subproblems represented in the agenda.

## 4.1 The Goal Agenda

The first step one has to take for computing the goal agenda is to perform a so-called goal analysis.  During goal analysis, each pair A, B E G of atomic goals must be examined in order to find out whether an ordering relation A ≤ B, or B ≤ A, or both, or none holds between them. For the ordering relation <, an arbitrary definition can be used. In our experiments, the relation < was always either <e or <h.

After having determined all ordering relations that hold between atomic goals, we want to split the goal set into smaller sets based on these relations, and we want to order the smaller sets, also based on these relations. More precisely, our goal is to have a sequence of goal sets G 1 , . . . G n with and

$$\bigcup_{i=1}^{\cdots}G_{i}\,=\mathcal{G}$$
$$G_{i}\cap G_{j}=\varnothing$$

for i = j,l < i,j < n. We also want the sequence of goal sets to respect the ordering relations that have been derived between atomic goals.  To make this explicit, we first introduce a simple representation for the detected atomic orderings: the goal graph G.

G := ( V, E )
where

$$V:={\mathcal{G}}$$

and

$$E:=\left\{(A,B\,)\in{\mathcal{G}}\times{\mathcal{G}}\mid A\,\leq B\,\right\}$$

Now, the desired properties, which the sequence of goal sets should possess, can be easily stated: