
$$R\,e s u l t\left(s,o\right):=\left\{\begin{array}{l l}{{\left(s\cup a d d(o)\right)\setminus d e l(o)}}&{{\mathrm{if~}p r e(o)\subseteq s}}\\ {{s}}&{{\mathrm{~}o t h\,e r w i s\,e}}\end{array}\right.$$

If pre(o) C s holds, the action is said to be applicable in s. The result of applying a sequence of more than one action to a state is recursively defined as Result(s, (01, . . . , 0n)) := Result(Result(s, (01, . . . , 0n-1)), 0n).

Definition 3 (Planning Problem) A planning problem (O, I, G) is a triple where O is the set of actions, and I (the initial state) and G (the goals) are sets of ground atoms.  A
plan P  is an ordered sequence of actions.  If all actions in a plan are taken out of a certain action set O, we denote this by writing PO.

Note that we define a plan to be a sequence of actions, not a sequence of parallel steps, as it is done for GRAPHPLAN (Blum & Furst, 1997), for example. This makes the subsequent theoretical investigation more readable. The results directly carry over to parallel plans.

Given two atomic goals A and B, various ways to define an ordering relation over them can be imagined. First, one can distinguish between domain-specific and domainindependent goal ordering relations. But although domain-specific orderings can be very effective, they need to be redeveloped for each single domain. Therefore, one is in particular interested in domain-independent ordering relations having a broader range of applicability. Secondly, following Hüllem et al. (1999), one can distinguish the goal selection and the goal achievement order. The first ordering determines in which order a planner works on the various atomic goals, while the second one determines the order, in which the solution plan achieves the goals. In this paper, we compute an ordering of the latter type. In the agenda-driven planning approach that we propose later in the paper, both orderings coincide anyway. The goals that are achieved first in the plan are those that the planner works on first.

The following scenario motivates how an achievement order for goals can be possibly defined. Given two atomic goals A and B , for which a solution plan exists, let us assume the planner has just achieved the goal A, i.e., it has arrived at a state s(A,-B); in which A
holds, but B does not hold yet. Now, if there exists a plan that is executable in s(A,-B)
and aieves B without ever deleting A, a solution has been found. If no such plan can be found, then two possible reasons exist:
1. The problem is unsolvable—achieving A first leads the planner into a deadlock situation. Thus, the planner is forced to achieve B before or simultaneously with A .

2. The only existing solution plans have to destroy A temporarily in order to achieve B .

But then, A should not be achieved first. Instead, it seems to be reasonable to achieve B before or simultaneously with A for the sake of shorter solution plans.
In the first situation, the ordering " B before or simultaneously with A " is forced by inherent properties of the planning domain. In the second situation, the ordering "B before or simultaneously with A" appears to be reasonable in order to avoid non-optimal plans. Conssequently, we will define two goal orderings, called the forced and the reasonable ordering. For the sake of clarity, we first give some more basic definitions.