
## 3.4  An Extension Of Goal Orderings To Adl Actions

The orderings, which have been introduced so far, can be easily extended to deal with ground ADL actions having conditional effects and using negation instead of delete lists.

Such actions have the following syntactic structure:

$$\begin{array}{r l}{{o:}}&{{\phi_{0}(o)=p r\,e_{0}(o)\longrightarrow e\!f_{0}^{+}(o),\,e\!f_{0}^{-}\left(o\right)}}\\ {{}}&{{\phi_{1}(o)=p r\,e_{1}(o)\longrightarrow e\!f_{1}^{+}(o),\,e\!f\!f_{1}^{-}\left(o\right)}}\\ {{}}&{{\vdots}}\\ {{}}&{{\phi_{n}(o)=p r\,e_{n}(o)\longrightarrow e\!f_{n}^{+}(o),\,e\!f\!f_{n}^{-}\left(o\right)}}\end{array}$$

All unconditional elements of the action are summarized in φ 0 ( σ ): The precondition of the action is denoted with preo (o), and its unconditional positive and negative effects with eff ( σ ) and eff ( σ ), respectively.  Each conditional effect φ i ( σ ) consists of an effect condition (antecedent) prei (o), and the positive and negative effects eff, (o) and eff, (o).

Additionally, we denote with Φ(o) the set of all unconditional and conditional effects, i.e., Φ(o) = {φρ(o), φι(o), . . , φπ(o)}.

The computation of < e immediately carries over to ADL actions when an extension of planning graphs is used, which can handle conditional effects, e.g., IPP (Koehler, Nebel, Hoffmann, & Dimopoulos, 1997) or SGP (Anderson & Weld, 1998). One simply takes the set of exclusive facts that is returned by these systems to determine the set FAp. The test from Definition 10, which decides whether there is an ordering B < e A of two atomic goals A and B, is extended to ADL as follows.

Definition 17 (Ordering < e for ADL) Let ( O, I, G = {A, B}) be a planning problem.

Let FAp  be the False set for A.  The ordering B ≤ e A holds if and only if
∀ o ∈ O, φ i ( o ) ∈ Φ ( o ) : B ∈ effi + ( o ) ∧ A ∈ D i ( o ) ⇒ ( pr e i ( o ) U pr e 0 ( o )) ∩ F ∈ P  ≠ ∅
Here, D i ( o ) denotes all negative effects that are implied by the conditions of φ i ( o ).

$$D_{i}\left(o\right):=\left\{\begin{array}{l l}{{e\!f\!\overline{{{_0}}}\left(o\right)\cup\bigcup_{p r e_{j}\left(o\right)}\subseteq p r e_{i\left(o\right)}\,e\!f\!\overline{{{_j}}}\left(o\right)}}&{{i\neq0}}\\ {{e\!f\!\overline{{{_0}}}\left(o\right)}}&{{i=0}}\end{array}\right.$$

Thus, B is ordered before A if all (unconditional or conditional) effects that add B either imply an effect that deletes A , or need conditions that cannot be made TRUE together with A. Note that an effect φ i requires all the conditions in pre i ( o ) Upre o ( o ) to be satisfied, which is impossible in any state where A holds because of the non-empty intersection with FA
The computation of <h requires a little more adaptation effort. In order to obtain the set FA : we now need to investigate the conditional effects as well. For each action that has A as a conditional or unconditional effect, we determine which atoms are negated by it, no matter which effect is used to achieve A. We obtain these atoms by intersecting the appropriate sets Di (o).

$$D\left(o\right):=\bigcap_{A\in{\mathrm{\,eff}}_{i}^{+}\left(o\right)}D_{i}\left(o\right)$$
