\documentclass[11pt,twoside]{article}
\usepackage{jair}
\usepackage{theapa}
\usepackage{epsf}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{verbatim}


%\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file

\jairheading{12}{2000}{339--386}{12/99}{6/00}
\ShortHeadings{On Reasonable and Forced Goal Orderings}
{Koehler \& Hoffmann}
\firstpageno{339}



%\renewcommand{\textfraction}{0.05}



\newcommand{\scalefig}[3]{%%  scale, figure, caption
\begin{figure}[htb]
\begin{center}
\makebox{{\def\epsfsize##1##2{#1##1}\epsfbox{#2}}}
\end{center}
\vspace*{-7mm}
\caption{\label{#2}#3}
\end{figure}}

\newcommand{\ie}{i.e.,~}
\newcommand{\eg}{e.g.,~}



\newcommand{\False}{{\sf F}}
\newcommand{\PP}{{\cal P}}
\newcommand{\act}{{\mathcal O}}
\newcommand{\G}{{\cal G}}
\newcommand{\I}{{\cal I}}
\newcommand{\GG}{{G}}
\newcommand{\achievable}{{\cal A}}
\newcommand{\pachievable}{p{\cal A}}
\newcommand{\true}{{\sc true}}
\newcommand{\false}{{\sc false}}
\newcommand{\eff}{\mbox{{\sl eff}}}
\newcommand{\pre}{pre}
\newcommand{\add}{add}
\newcommand{\del}{del}

\newcommand{\graphplan}{{\sc graphplan}}
\newcommand{\ipp}{{\sf IPP}}

\newcommand{\forced}{{\sf F\_ORDER}}
\newcommand{\reasonable}{{\sf R\_ORDER}}
\newcommand{\effective}{{\sf E\_ORDER}}

\newcommand{\plansat}{{\sf PLANSAT}}
\newcommand{\pspace}{{\sf PSPACE}}
\newcommand{\copspace}{{\sf co-PSPACE}}



\newenvironment{beweis}{\noindent {\bf Proof:}}%
{\hfill \rule[0.3ex]{1ex}{1ex} \par \addvspace{\bigskipamount}}

\newtheorem{theorem}{Theorem}
\newtheorem{def1}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{example}{Example}


\bibliographystyle{theapa}

\begin{document}

\title{On Reasonable and Forced Goal Orderings and their Use in an
  Agenda-Driven Planning Algorithm}

\author{\name Jana Koehler \email jana\_koehler@ch.schindler.com\\
        \addr Schindler Lifts, Ltd.\\
          R \& D Technology Management\\
               6031 Ebikon, Switzerland\\
       \AND
       \name  J\"org Hoffmann \email hoffmann@informatik.uni-freiburg.de\\
       \addr Institute for Computer Science\\
Albert Ludwigs University  \\
Georges-K\"ohler-Allee, Geb. 52\\
79110 Freiburg, Germany \\
} 


\maketitle

 
\begin{abstract} The paper addresses the problem of computing goal
  orderings, which is one of the longstanding issues in AI planning.
  It makes two new contributions.  First, it formally defines and
  discusses two different goal orderings, which are called the {\em
    reasonable} and the {\em forced} ordering. Both orderings are
  defined for simple STRIPS operators as well as for more complex ADL
  operators supporting negation and conditional effects. The
  complexity of these orderings is investigated and their practical
  relevance is discussed. Secondly, two different methods to compute
  reasonable goal orderings are developed. One of them is based on
  planning graphs, while the other investigates the set of actions
  directly. Finally, it is shown how the ordering relations, which
  have been derived for a given set of goals $\G$, can be used to
  compute a so-called {\em goal agenda} that divides $\G$ into an
  ordered set of subgoals. Any planner can then, in principle, use the
  goal agenda to plan for increasing sets of subgoals.
  This can lead to an exponential complexity reduction, as the
  solution to a complex planning problem is found by solving easier
  subproblems. Since only a polynomial overhead is caused by the goal
  agenda computation, a potential exists to dramatically speed up
  planning algorithms as we demonstrate in the empirical evaluation,
  where we use this method in the \ipp\ planner.  \end{abstract}




\section{Introduction}

How to effectively plan for interdependent subgoals has been in the
focus of AI planning research for a very long time. Starting with the
early work on ABSTRIPS \cite{abstrips} or on conjunctive-goal planning
problems \cite{chapman87}, quite a number of approaches have been
presented and the complexity of the problems has been studied. But
until today, planners have made only some progress in solving bigger
planning instances and scalability of classical planning systems is
still a problem.

In this paper, we focus on the following problem: Given a set of
conjunctive goals, can we define and detect an ordering relation over
subsets from the original goal set? To arrive at such an ordering
relation over subsets, we first focus on the atomic facts contained in
the goal set. We formally define two closely related ordering
relations over such atomic goals, which we call {\em reasonable} and
{\em forced} ordering, and study their complexity. It turns out that
both are very hard to decide.

Consequently, we introduce two efficient methods that can both be used
to approximate {\em reasonable} goal orderings. The definitions are
first given for simple STRIPS domains, where the desired theoretical
properties can be easily proven. Afterwards, we extend our definitions
to ADL operators \cite{pednault89} handling conditional effects and
negative preconditions, and discuss why we do not further invest any
effort in trying to find {\em forced} orderings.

We show how a set of ordering relations between atomic goals can be
used to divide the goal set into disjunct subsets, and how these
subsets can be ordered with respect to each other. The resulting
sequence of subsets comprises the so-called {\em goal agenda}, which
can then be used to control an agenda-driven planning algorithm.

The method, called {\bf G}oal {\bf A}genda {\bf M}anager, is
implemented in the context of the \ipp\ planning system, where we show
its potential of exponentially reducing computation times on certain
planning domains.

The paper is organized as follows: Section~\ref{relation} introduces
and motivates reasonable and forced goal orderings. Starting with
simple STRIPS operators, they are formally defined, and their
complexity is investigated. In Section~\ref{method}, we present two
methods, which compute an approximation of the reasonable ordering and
discuss both orderings from a more practical point of view.  The
section concludes with an extension of our definitions to ADL
operators having conditional effects. Section~\ref{planning} shows how
a planning system can benefit from ordering information by computing a
goal agenda that guides the planner. We define how subsets of goals
can be ordered with respect to each other and discuss how a goal
agenda can affect the theoretical properties, in particular the
completeness of a planning algorithm. Section~\ref{empirical} contains
the empirical evaluation of our work, showing results that we obtained
using the goal agenda in \ipp. In Section~\ref{related} we summarize
our approach in the light of related work.  The paper concludes with
an outlook on possible future research directions in
Section~\ref{outlook}.

\section{Ordering Relations between Atomic Goals}
\label{relation}

For a start, we only investigate simple STRIPS domains just allowing
sets of atoms to describe states, the preconditions, and the add and
delete lists of operators.

\begin{def1}[State]
  The set of all ground atoms is denoted with $P$.  A {\em state} $s
  \in 2^{P}$ is a subset of ground atoms.
\end{def1}

\noindent 
Note that all states are assumed to be {\em complete}, \ie we always
know for an atom $p$ whether $p \in s$ or $p \not \in s$ holds. We
also assume that all operator schemata are ground, \ie we only talk
about {\em actions}.

\begin{def1}[Strips Action]\label{strips-op}
  A {\em STRIPS action} $o$ has the usual form
\[
\pre(o) \; \longrightarrow \mbox{ ADD } \; \add(o) \; \mbox{ DEL } \; \del(o)
\]
where $\pre(o)$ are the preconditions of $o$, $\add(o)$ is the Add list
of $o$ and $\del(o)$ is the Delete list of the action, each being a set
of ground atoms.  We also assume that $\del(o) \cap \add(o) =
\emptyset$. The result of applying a STRIPS action to a state is
defined as usual:

\[
Result(s,o) := \left \{ \begin{array}[]{ll} (s \cup \add(o)) \setminus
  \del(o) & \mbox{{\sl if} } \pre(o) \subseteq s\\
 s & \mbox{otherwise} \end{array} \right. 
\]

If $\pre(o) \subseteq s$ holds, the action is said to
be {\em applicable} in $s$. The result of applying a sequence of more
than one action to a state is recursively defined as
\[
Result(s,\langle o_1,\dots,o_n\rangle) := Result(Result(s,\langle
o_1,\dots,o_{n-1}\rangle),o_n).
\]
\end{def1}

\begin{def1}[Planning Problem]\label{strips-plan}
  A {\em planning problem} $(\act,\I,\G)$ is a triple where $\act$ is the set
  of actions, and $\I$ (the initial state) and $\G$ (the goals) are sets of
  ground atoms. A {\em plan} $\PP$ is an ordered sequence of actions. If all
  actions in a plan are taken out of a certain action set $\act$, we denote
  this by writing $\PP^{\act}$.
\end{def1}

Note that we define a plan to be a sequence of {\em actions}, not a
sequence of {\em parallel steps}, as it is done for \graphplan\
\cite{blum-aij}, 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
{\em domain-specific} and {\em domain-independent} 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\"ullem et al.\ \citeyear{huellem}, one can distinguish the
{\em goal selection} and the {\em 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$, \ie it has arrived at a state $s_{(A,\neg B)}$, in which
$A$ holds, but $B$ does not hold yet. Now, if there exists a plan that
is executable in $s_{(A,\neg B)}$ and achieves $B$ without ever
deleting $A$, a solution has been found. If no such plan can be found,
then two possible reasons exist:

\begin{enumerate}
\item The problem is unsolvable---achieving $A$ first leads the planner into a
  deadlock situation. Thus, the planner is {\em forced} to achieve $B$
  before or simultaneously with $A$.
\item 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 {\em reasonable} to achieve $B$ before or simultaneously with
  $A$ for the sake of shorter solution plans.
\end{enumerate}

In the first situation, the ordering ``$B$ before or simultaneously
with $A$'' is {\em forced} by inherent properties of the planning
domain. In the second situation, the ordering ``$B$ before or
simultaneously with $A$'' appears to be {\em reasonable} in order to
avoid non-optimal plans. Consequently, we will define two goal
orderings, called the {\em forced} and the {\em reasonable} ordering.
For the sake of clarity, we first give some more basic definitions.

\begin{def1}[Reachable State]
  Let $(\act,\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
  \subseteq P$ is {\em reachable}, iff there exists a sequence $
  \langle o_1, \dots, o_n \rangle $ out of actions in $\act$ for which
  $s = Result(\I, \langle o_1, \dots, o_n \rangle )$ holds.
\end{def1}

\begin{sloppypar}
\begin{def1}[Generic State $s_{(A,\neg B)}$]\label{sAnegB}
  Let $(\act,\I,\G)$ be a planning problem. By $s_{(A,\neg B)}$ we
  denote any reachable state in which $A$ has just been achieved, but
  $B$ is \false, \ie $B \not \in s_{(A,\neg B)}$ and there is a
  sequence  of actions $\langle o_1, \dots, o_n \rangle$ such that
  $s_{(A,\neg B)}$ $= Result(\I, \langle o_1, \dots, o_n \rangle )$,
  with $A \in \add(o_n)$.
\end{def1}
\end{sloppypar}

One can imagine $s_{(A,\neg B)}$ as a state about which we only have
incomplete information. All the states $s$ it represents satisfy $s
\models A, \neg B$, but the other atoms $p \in P$ with $p \neq A,B$
can adopt arbitrary truth values.

\begin{def1}[Reduced Action Set $\act_A$] \label{reduced-O}
  Let $(\act,\I,\G)$ be a planning problem, and let $A \in \G$ be an
  atomic goal. By $\act_A$ we denote the set of all actions that do
  not delete $A$, \ie $\act_A = \{ o \in \act \mid A \not \in \del(o)
  \}$.
\end{def1}

\noindent
We are now prepared to define what we exactly mean by {\em forced} and
{\em reasonable} goal orderings.

\begin{def1}[Forced Ordering $\leq_f$]\label{f-ord}
  Let $(\act,\I,\G)$ be a planning problem, and let $A,B \in \G$ be
  two atomic goals. We say that there is a {\em forced ordering}
  between $B$ and $A$, written $B \leq_f A$, if and only if
\[ 
\forall \; s_{(A,\neg B)}: \; \; \neg \exists \; \PP^\act: \; B \in
Result(s_{(A,\neg B)},\PP^\act)
\]

\end{def1}

If Definition~\ref{f-ord} 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.

\begin{def1}[Reasonable Ordering $\leq_r$]\label{r-ord}
  Let $(\act,\I,\G)$ be a planning problem, and let $A,B \in \G$ be
  two atomic goals. We say that there is a {\em reasonable ordering}
  between $B$ and $A$, written $B \leq_r A$, if and only if
\[ 
\forall \; s_{(A,\neg B)}: \; \; \neg \exists \; \PP^{\act_A}: \; B \in
Result(s_{(A,\neg B)},\PP^{\act_A})
\]
\end{def1}

Definition~\ref{r-ord} gives $B \leq_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 \leq_f A$ implies $B \leq_r A$, but not
vice versa. We also make a slightly less obvious observation at this
point: The formulae in Definitions~\ref{f-ord} and~\ref{r-ord} use a
universal quantification over states $s_{(A,\neg 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, \ie $B \leq_f A$ and
$B \leq_r A$ follow, respectively. In this case, however, there is not much
information gained by a goal ordering between $A$ and $B$, because
{\em 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 \leq_f A$ and $B \leq_r A$ are
{\em 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.

\begin{def1}[Trivial Ordering Relation]\label{trivial}
  Let $(\act,\I,\G)$ be a planning problem, and let $A,B \in \G$ be
  two atomic goals. An ordering relation $B \leq_f A$ or $B \leq_r A$
  is called {\em trivial} iff there is no state $s_{(A,\neg B)}$.
\end{def1}

In this paper, we will usually consider forced and reasonable goal
orderings as non-trivial orderings and make the distinction explicit
only if we have to do so.

Definitions~\ref{f-ord} and~\ref{r-ord} seem to deliver promising
candidates for an achievement order. Unfortunately, both are very hard
to test: it turns out that their corresponding decision problems are
{\sf PSPACE} hard.

\begin{theorem}\label{forced-hard}
Let \forced\ denote the following problem:

\bigskip

{\em Given two atomic facts $A$ and $B$, as well as an action set
$\act$ and an initial state $\I$, does $B \leq_f A$ hold ?}

\bigskip

Deciding \forced\ is \pspace-hard.
\end{theorem}

\begin{beweis}
  The proof proceeds by polynomially reducing \plansat\ 
  \cite{bylander-aij}---the decision problem of whether there exists a
  solution plan for a given arbitrary STRIPS planning instance---to
  the problem of deciding \forced.

\bigskip 
Let $\I$, $\G$, and $\act$ denote the initial state, the goal state,
and the action set in an arbitrary STRIPS instance.  Let $A$, $B$, and
$C$ be new atomic facts not contained in the instance so far. We build
a new action set and initial state for our \forced\ instance by
setting

\[
\act' := \act \cup \left\{ \begin{array}{lll}
 o_{I_1} & = \{ C \} \; & \longrightarrow \mbox{ ADD } \{A \} \; \mbox{ DEL
 } \{ C \}, \\
o_{I_2} & = \{ A \} \; & \longrightarrow \mbox{ ADD } \I \; \mbox{ DEL } \{ A
  \}, \\ 
o_G  & = \G \; & \longrightarrow \mbox{ ADD } \{B \} \; \mbox{ DEL } \emptyset 
\end{array}\right\}
\]
and 
\[
\I' := \{ C \}
\]
With these definitions, reaching $B$ from $A$ is equivalent to solving
the original problem. The other way round, unreachability of $B$ from
$A$---forced ordering $B \leq_f A$---is equivalent to the unsolvability of
the original problem. In order to prove this, we consider the
following: The only way of achieving $A$ is by applying $o_{I_1}$ to
$\I'$.  Consequently, the only state $s_{(A,\neg B)}$ is $\{ A \}$,
cf.  Definition~\ref{sAnegB}. Thus starting with the assumption that
$B \leq_f A$ is valid, we apply the following equivalences:

\[
\begin{array}{llr}
                & B \leq_f A  \\[2mm] 
\Leftrightarrow & 
\forall \; s_{(A,\neg B)}: \neg \exists \; \PP^{\act'}: B \in Result(s_{(A,\neg B)},\PP^{\act'}) & \mbox{\small cf.\ Definition}~\ref{f-ord}\\[2mm]
\Leftrightarrow & \neg \exists \; \PP^{\act'}: \;
B \in Result(\{ A \},\PP^{\act'}) &  \{A\} \; \mbox{\small is the only reachable
state }  s_{(A,\neg B)}\\[2mm]
 \Leftrightarrow & \neg \exists \; \PP^{\act}: \;   \G \subseteq
Result(\I,\PP^{\act}) & \mbox{\small with the definition of } \act'\\[2mm]
 \Leftrightarrow & \mbox{no solution plan exists for } \I, \G \mbox{
  and given } \act
\end{array}
\]

\noindent
Thus, the complement of \plansat\ can be polynomially reduced to
\forced. As \pspace\ = \copspace, we are done.
\end{beweis}

\begin{theorem}\label{reasonable-hard}
Let \reasonable\ denote the following problem:

\medskip
{\em Given two atomic facts $A$ and $B$, as well as an action set
  $\act$ and an initial state $\I$, does $B \leq_r A$ hold ?}

\medskip
Deciding \reasonable\ is \pspace-hard.
\end{theorem}
\begin{beweis}
  The proof proceeds by polynomially reducing \plansat\ to
  \reasonable.
  
\bigskip
Let $\I$, $\G$, and $\act$ be the initial state, the goal state, and
the action set in an arbitrary STRIPS planning instance. Let $A$, $B$,
$C$, and $D$ be new atomic facts not contained in the instance so
far. We define the new action set $\act'$ by setting
\[
\act' := \act \cup \left\{ \begin{array}{lll}
o_{I_1} & = \{ C \} \; & \longrightarrow \mbox{ ADD } \{ A, D \} \; \mbox{ DEL } \{ C \}, \\
 o_{I_2} & = \{ A, D \} \; & \longrightarrow \mbox{ ADD } \I \; \mbox{ DEL
  } \{ D \}, \\
o_G & = \G \; & \longrightarrow \mbox{ ADD } \{ B \} \; \mbox{
  DEL } \emptyset 
\end{array}\right\}
\]
and the new initial state by
\[
\I' := \{ C \}
\]
As in the proof of Theorem~\ref{forced-hard}, the intention behind
these definitions is to make solvability of the original problem
equivalent to reachability of $B$ from $A$. For reasonable orderings,
reachability is concerned with actions that do not delete $A$, which
is why we need the safety condition $D$.

Precisely, the only way to achieve $A$ is by applying $o_{I_1}$ to
$\I'$, \ie per Definition~\ref{sAnegB} the only state $s_{(A,\neg B)}$
is $\{ A, D \}$. As no action in the new operator set $\act'$ deletes
$A$, we have the following sequence of equivalences.

\[
\begin{array}{llr}
                & B \leq_r A  &\\
\Leftrightarrow & 
\forall \; s_{(A,\neg B)} \; \neg \exists \; \PP^{\act'_A}:  B
\in Result(s_{(A,\neg B)},\PP^{\act'_A}) & \mbox{\small cf.\
Definition}~\ref{r-ord}\\[2mm] 
\Leftrightarrow &  \neg \exists \; \PP^{\act'_A}: \; B 
\in Result(\{ A, D \},\PP^{\act'_A})  &
\{A,D\} \;  \mbox{\small is the only reachable state } s_{(A,\neg B)}\\[2mm] 
\Leftrightarrow  & \neg \exists \; \PP^{\act'}: \; B \in Result(\{ A,
D \},\PP^{\act'})  
& \mbox{\small no action in } \act' \mbox{\small deletes } A\\[2mm]
\Leftrightarrow & \neg \exists \; \PP^{\act} \mbox{
such that } \; \G \subseteq Result(\I,\PP^{\act})  & 
\mbox{\small with the definition of } \act'\\[2mm]
\Leftrightarrow & \mbox{ no solution plan exists for } \I, \G, \act
\end{array}
\]

\bigskip
\noindent
Thus, the complement of \plansat\ can be polynomially reduced to
\reasonable. With \pspace\ = \copspace, we are done.
\end{beweis}

 

Consequently, finding reasonable and forced ordering relations between
atomic goals is already as hard as the original planning problem and
it appears unlikely that a planner will gain any advantage from doing
that. A possible way out of the dilemma is to define new ordering
relations, which can be decided in polynomial time and which are,
ideally, sufficient for the existence of reasonable or forced goal
orderings. In the following, we introduce two such orderings.

\section{The Computation of Goal Orderings}
\label{method}


In this section, we will 

\begin{enumerate}
\item define a goal ordering $\leq_e$, which can be computed using
  \graphplan's exclusivity information about facts. We prove that this
  ordering is sufficient for $\leq_r$ and that it can be decided in polynomial
  time (the subscript ``e'' stands for ``efficient'').
\item define a goal ordering $\leq_h$, which is computed based on a
  heuristic method that is much faster than the computation based on
  \graphplan, and also delivers powerful goal ordering information
  (the subscript ``h'' stands for ``heuristic'').
\item discuss that most of the currently available benchmark planning
  domains do not contain forced orderings, \ie $\leq_f$ will fail in
  providing a problem decomposition for them.
\item show how our orderings can be extended to handle more
  expressive ADL operators.
\end{enumerate}


\subsection{Reasonable Goal Orderings based on \graphplan}
\label{reasonable:graphplan}

A goal ordering is always computed for a specific planning problem involving
an initial state $\I$, a goal set $\G \supseteq \{A,B\}$, and the set $\act$
of all ground actions. In order to develop an efficient computational method,
we proceed in two steps now:

\begin{enumerate}
\item We compute more knowledge about the generic state $s_{(A,\neg B)}$.
\item We define the relation $\leq_e$ and investigate its theoretical
  properties. In particular, we prove that $\leq_e$ implies $\leq_r$.
\end{enumerate}

The state $s_{(A,\neg B)}$ represents states that are reachable from
$\I$, and in which $A$ has been achieved, but $B$ does not hold. Given
this information about $s_{(A,\neg B)}$, one can derive additional
knowledge about it. In particular, it is possible to determine a
subset of atoms $\False$, of which one definitely knows that $\False
\cap s_{(A,\neg B)} = \emptyset$ must hold.  One method to determine
$\False$ is obtained via the computation of invariants, \ie logical
formulae that hold in all reachable states, cf.\
\cite{fox-jair}. After having determined the invariants, one assumes
that $A$ holds, but $B$ does not, and then computes the logical
implications. Another possibility is to simply use \graphplan\
\cite{blum-aij}. Starting from $\I$ with $\act$, the planning
graph is built until the graph has {\em leveled} off at some time
step. The proposition level at this time step represents a set of
states, which is a superset of all states that are reachable from $\I$
when applying actions from $\act$. All atoms, which are marked as {\em
mutually exclusive} \cite{blum-aij} of $A$ in this level can never
hold in a state satisfying $A$. Thus, they cannot hold in $s_{(A,\neg
B)}$. We denote this set with $\False^A_{GP}$---the {\sf False} set
with respect to $A$ returned by \graphplan.\footnote{We assume the
reader to be familiar with \graphplan, because this planning system is
very well known in the planning research community. Otherwise,
\cite{blum-aij} provide the necessary background.}
\begin{equation} \label{false-pg} \False^A_{GP} := \{ p \mid p \mbox{
is exclusive of } A \mbox{ when the graph has leveled off} \}
\end{equation}

\noindent
Note that the planning graph is only grown once for a given $\I$ and $\act$,
but can be used to determine the $\False^A_{GP}$ sets for all atomic goals $A
\in \G$.

\begin{lemma}\label{lemma:false-pg}
  $\False^A_{GP} \cap s_{A} = \emptyset$ holds for all states $s_{A}$
  satisfying $A \in s_A$ that are reachable from $\I$ using actions from
  $\act$.
\end{lemma}

The proof follows immediately from the definitions of ``level-off'' and ``two
  propositions being mutual exclusive'' given in \cite{blum-aij}.


We now provide a simple test which is sufficient for the existence of
a reasonable ordering $B \leq_r A$ between two atomic goals $A$ and
$B$.

\begin{def1}[Efficient Ordering $\leq_e$]\label{ord-e}
  Let $(\act,\I,\G \supseteq \{A,B\})$ be a planning problem. Let
  $\False^A_{GP}$ be the {\sf False} set for $A$. The ordering $B \leq_e A$
  holds if and only if
\[ 
\forall \; o \in \act_A: B \in \add(o) \Rightarrow \pre(o)
   \cap \False^A_{GP} \neq \emptyset
\]
\end{def1}

This means, $B$ is ordered before $A$ if the reduced action set
only contains actions, which either do not have $B$ in their add lists or if
they do, then they require a precondition which is contained in the {\sf
  False} set. Such preconditions can never hold in a state satisfying $A$ and
thus, these actions will never be applicable.

\begin{theorem}
\[ 
B \leq_e A \Rightarrow B \leq_r A
\]
\end{theorem}

\begin{beweis}
  Assume that $B \not \leq_r A$, \ie $B \in Result(s_{(A, \neg B)},
  \PP^{\act_A})$ for a reachable state $s_{(A, \neg B)}$ with $A \in
  s_{(A, \neg B)}$, $B \not \in s_{(A, \neg B)}$, and a Plan
  $\PP^{\act_A} =  \langle o_1, \dots, o_n \rangle $ where $o_i \in \act_A$ for $1 \leq
  i \leq n$.

As $A \not \in \del(o_i)$ for all $i$ (Definition~\ref{reduced-O}), we have 
\[
A \in Result(s_{(A, \neg B)},  \langle o_1, \dots, o_i \rangle ) \; \mbox{ for } \; 0
\leq i \leq 
n
\]
and, with Lemma~\ref{false-pg},
\begin{equation}\label{zwischenbeh}
   \False^A_{GP} \cap Result(s_{(A, \neg B)},  \langle o_1, \dots, o_i \rangle ) = \emptyset
\; \mbox{ for } \; 0 \leq i \leq n 
\end{equation}


Furthermore, as $B \not \in s_{(A, \neg B)}$, but $B \in Result(s_{(A,
  \neg B)},  \langle o_1, \dots, o_n \rangle )$, there must be a step which makes $B$
true, \ie
\[
\exists 1 \leq k \leq n: B \not \in Result(s_{(A, \neg B)},  \langle o_1,
\dots, o_{k-1} \rangle ) \wedge B \in Result(s_{(A, \neg B)},  \langle o_1, \dots,
o_{k} \rangle )
\]

For this step, we obviously have $B \in \add(o_k)$ and consequently, with the
definition of $B \leq_e A$, $\pre(o_k) \cap \False^A_{GP} \neq \emptyset$.
Now, as $o_k$ must be applicable in the state where it is executed (otherwise
it would not add anything to this state), the preconditions of $o_k$ must
hold, \ie $\pre(o_k) \subseteq Result(s_{(A, \neg B)},  \langle o_1, \dots, o_{k-1} \rangle )$.
This immediately leads to $\False^A_{GP} \cap Result(s_{(A, \neg B)},  \langle o_1,
\dots, o_{k-1} \rangle ) \neq \emptyset$, which is a contradiction to
Equation~(\ref{zwischenbeh}).
\end{beweis}

\noindent
Quite obviously, the ordering $\leq_e$ can be decided in polynomial
time.

\begin{theorem}
Let \effective\ denote the following problem:

\bigskip

{\em Given two atomic facts $A$ and $B$, as well as an initial state
  $\I$ and an action set $\act$, does $B \leq_e A$ hold ?}

\bigskip

\noindent
Then, \effective\ can be decided in polynomial time: \effective\ $\in$ {\sf P}.
\end{theorem}

\begin{beweis}
To begin with, we need to show that computing $\False^A_{GP}$ takes
only polynomial time. From the results in \cite{blum-aij}, it follows
directly that building a planning graph is polynomial in $|\I|$,
$|\act|$, $l$ and $t$, where $l$ is the maximal length of any
precondition, add or delete list of an action, and $t$ is the number
of time steps built. Taking $l$ as a parameter of the input size, it
remains to show that a planning graph levels off after a polynomial
number $t$ of time steps. Now, a planning graph has leveled off if
between some time steps $t$ and $t+1$ neither the set of facts nor the
number of exclusion relations change. Between two subsequent time
steps, the set of facts can only increase---facts already occuring in
the graph remain there---and the number of exclusions can only
decrease---non-exclusive facts will be non-exclusive in all subsequent
layers.  Thus, the maximal number of time steps to be built until the
graph has leveled off is dominated by the maximal number of changes
that can occur between two subsequent layers, which is dominated by
the maximal number of facts plus the maximal number of exclusion
relations. The maximal number of facts is $O(|\I| + |\act|*l)$, and
the maximal number of exclusions is $O((|\I| + |\act|*l)^2)$, the
square of the maximal number of facts.


Having computed $\False^A_{GP}$ in polynomial time, testing $B \leq_e
A$ involves looking at all actions in $\act$, and rejecting them if
they either
\begin{itemize}
\item delete $A$, which is decidable in time $O(l)$, or
\item have a precondition, which is an element of
  $\False^A_{GP}$, decidable in time $O(l * (|\I| + |\act|*l))$.
\end{itemize}

Thus we have an additional runtime for the test, which is
$O(|\act| * l * (|\I| + |\act|*l))$.
\end{beweis}

Let us consider the following example, which illustrates the computation of
$\leq_e$ using a common representational variant of the {\em blocks world} with
actions to {\bf stack}, {\bf unstack}, {\bf pickup}, and {\bf putdown} blocks:

{\sl 
\begin{tabbing}
{\bf pickup(?ob)}\\
clear(?ob) on-table(?ob) arm-empty() $\longrightarrow$ \= ADD holding(?ob)\\
\>   DEL clear(?ob) on-table(?ob) arm-empty().
\end{tabbing}
\begin{tabbing}
{\bf putdown(?ob)}\\
holding(?ob) $\longrightarrow$ \= ADD clear(?ob) arm-empty() on-table(?ob)\\
\>   DEL holding(?ob).
\end{tabbing}
\begin{tabbing}
{\bf stack(?ob,?underob)}\\
clear(?underob) holding(?ob) $\longrightarrow$ \=
          ADD arm-empty() clear(?ob) on(?ob,?underob)\\
\>     DEL  clear(?underob) holding(?ob).
\end{tabbing}
\begin{tabbing}
{\bf unstack(?ob,?underob)}\\
on(?ob,?underob) clear(?ob) arm-empty() $\longrightarrow$ \= 
ADD holding(?ob) clear(?underob) \\
 \>     DEL on(?ob,?underob) clear(?ob) arm-empty().
\end{tabbing}
}


\noindent
Given the simple task of stacking three blocks:

\begin{tabbing}
{\bf initial state:} \= on-table(a) on-table(b) on-table(c)\\
{\bf goal state:} \>  on(a,b) on(b,c)

\end{tabbing}

\noindent
is there a reasonable ordering between the two atomic goals? Intuitively, the
{\em blocks world} domain possesses a very natural goal ordering, namely that
the planner should start building each tower from the bottom to the top and
not the other way round.\footnote{Note that the goals do not specify where the
  block $c$ has to go, but leave this to the planner.}

Let us first investigate whether the relation $on(a,b) \leq_e on(b,c)$
holds.  Vividly speaking, it asks whether it is still possible to
stack the block $a$ on $b$ after $on(b,c)$ has been achieved. As a
first step, we run \graphplan\ to find out which atoms are exclusive
of $on(b,c)$ when the planning graph, which corresponds to this
problem, has leveled off. The result is 

\[\False^{on(b,c)}_{GP} = \{
\mbox{\em clear(c), on-table(b), holding(c), holding(b), on(a,c),
on(c,b), on(b,a)}\}\]

One observes immediately that these atoms can never be true in a state that
satisfies $on(b,c)$.

Secondly, we remove all ground actions which delete $on(b,c)$ (in this
case, only the action {\bf unstack(b,c)} satisfies this condition) and
obtain the reduced action set $\act_{on(b,c)}$.

Now we are ready to test if $on(a,b) \leq_e on(b,c)$ holds. The only action,
which can add $on(a,b)$ is {\bf stack(a,b)}. It has the preconditions
$holding(a)$ and $clear(b)$, neither of which is a member of
$\False^{on(b,c)}_{GP}$. The test fails and we get $on(a,b) \not \leq_e
on(b,c)$.

As a next step, we test whether $on(b,c) \leq_e on(a,b)$
holds. \graphplan\ returns the following {\sf False} set: 

\[
\False^{on(a,b)}_{GP} = \{ \mbox{\em clear(b), on-table(a),
holding(b), holding(a), on(a,c), on(c,b), on(b,a)}\} 
\]

The action {\bf unstack(a,b)} is not contained in $\act_{on(a,b)}$ because it
deletes $on(a,b)$. The only action which adds $on(b,c)$ is {\bf stack(b,c)}.
It needs the preconditions $clear(c)$ and $holding(b)$. The second
precondition $holding(b)$ is contained in the set of false facts, \ie $holding(b)
\in \False^{on(a,b)}_{GP}$ and thus, we conclude $on(b,c) \leq_e on(a,b)$.
Altogether, we have $on(a,b) \not \leq_e on(b,c)$ and $on(b,c) \leq_e
on(a,b)$, which correctly reflects the intuition that $b$ needs to be stacked
onto $c$ {\em before} $a$ can be stacked onto $b$.

Although $\leq_e$ appears to impose very strict conditions on a domain
in order to derive a reasonable goal ordering, it succeeds in finding
reasonable goal orderings in all available test domains in which such
orderings exists.  For example, in the {\em tyreworld}, in {\em
bulldozer} problems, in the {\em shopping problem} \cite{russel-aima},
the {\em fridgeworld}, the {\em glass} domain, the {\em tower of
hanoi} domain, the {\em link-world}, and the {\em woodshop}.  Its only
disadvantage are the computational resources it requires, since
building planning graphs, while being theoretically polynomial, is a
quite time- and memory-consuming thing to do.\footnote{More recent
implementations of planning graphs, which are for example developed
for STAN \cite{spike} and \ipp\ 4.0 \cite{tr-128} do not build the
graphs explicitly anymore and are orders of magnitude faster than the
original \graphplan\ implementation, but still the computation of the
planning graph takes almost all the time that is needed to determine
the $\leq_e$ relations.}

Therefore, the next section presents a fast heuristic computation of goal
orderings, which analyzes the domain actions directly and does not need to
build planning graphs anymore.

\subsection{Reasonable Goal Orderings derived by a Fast Heuristic
Method}
\label{ord-h-strips}

One can analyze the available actions directly using a method we will call
{\em Direct Analysis} (DA). It determines an initial value for $\False$ by
computing the intersection of all delete lists of all actions which contain
$A$ in their add list, as defined in the following equation.

\begin{equation}\label{false-DA}
\False^A_{DA} := \bigcap_{o \; \in \; \act, \; A \, \in \, \add(o)} \del(o)
\end{equation}

The atoms in this set are all \false\ in a state where $A$ has just been
achieved: they are deleted from the state description independently of the
action that is used to add $A$. As a short example, let us consider the two
actions

\[
\longrightarrow \mbox{ ADD } \; \{ A \} \; \; \mbox{ DEL } \; \{ C, D \}
\] 
\[
\longrightarrow \mbox{ ADD } \; \{ A, C \} \; \; \mbox{ DEL } \; \{ D \}
\] 

Only the atom $D$ is deleted by both actions, and thus $D$ is the only element
initially contained in $\False^A_{DA}$.


However, Equation~(\ref{false-DA}) only says that when $A$ is added then the
atoms from $\False^A_{DA}$ will be deleted. It does not say anything about
whether it might be possible to reestablish atoms in $\False^A_{DA}$. One can
easily imagine that actions exist, which leave $A$ true, and at the same time
add such atoms. If this is the case, there are reachable states in which $A$
and atoms from $\False^A_{DA}$ hold. 

Now, our goal is to derive an ordering relation that can be easily
computed, and that ideally, like the $\leq_e$ relation, is sufficient
for the $\leq_r$ relation. Therefore, we want to make sure that the
atoms in $\False^A_{DA}$ are really \false\ in any state after $A$ has
been achieved. We arrive at an approximation of atoms that remain
\false\ by performing a fixpoint reduction on the $\False^A_{DA}$ set,
removing those atoms that are {\em achievable} in the following sense.

\begin{def1}[Achievable Atoms]\label{def:achievable}
  An atom $p$ is {\em achievable} from a state $s$ given an action set $\act$
  (written $\achievable(s,p,\act)$) if and only if
\[
p \in s\;  \vee \;  \exists \; o \in \act: p \in \add(o) \; \wedge
\; \forall \; p' \in \pre(o): \; \achievable(s,p',\act)
\]   
\end{def1}

The definition says that an atom $p$ is achievable from a state $s$ if it
holds in $s$, or if there exists an action in the domain, which adds $p$ and
whose preconditions are all achievable from $s$. This is a necessary condition
for the existence of a plan $\PP^{\act}$ from $s$ to a state where $p$ holds.

\begin{lemma}\label{lemma:planfolgtachievable}
$\exists \; \PP^{\act}: \; p \in Result(s,\PP^{\act}) \Rightarrow
  \achievable(s,p,\act)$
\end{lemma}

\begin{beweis}
  The atom $p$ must either already be contained in the state $s$, or it has to
  be added by a step $o$ out of $\PP^{\act}$. In the second case, all
  preconditions of $o$ need to be established by $\PP^{\act}$ in the same way.
  Thus $p$ and all preconditions of the step, which adds it, are
  achievable in the sense of Definition~\ref{def:achievable}.
\end{beweis}

There are two obvious difficulties with Definition~\ref{def:achievable}:
First, $p \in s$ must be tested.  With complete knowledge about the state $s$,
this should not cause any problems. In our case, however, we only have the
{\em generic} state $s_{(A,\neg B)}$ and cannot decide whether an arbitrary
atom is contained in it or not. Secondly, we observe an infinite regression
over preconditions, which must be tested for achievability.

As for the first problem, it turns out that it is a good heuristic to simply
assume $p \not \in s$, \ie no test is performed at all. As for the second
problem, in order to avoid infinite looping of the ``achievable''-test, one
needs to terminate the regression over preconditions at a particular level.
The point in question is how far to regress? A quick approximation simply
decides ``achievable'' after the first recursive call.

\begin{def1}[Possibly Achievable Atoms]\label{def:pachievable}
  An atom $p$ is {\em possibly achievable} given an action set $\act$ (written
  $\pachievable(p,\act)$) if and only if
\[
\exists \; o \in \act: p \in \add(o) \; \wedge \; \forall \; p' \in
\pre(o): \; \exists \; o' \in \act: p' \in \add(o')
\]
holds, \ie there is an action that adds $p$ and all of its preconditions are
add effects of other actions in $\act$.
\end{def1}

\medskip

If the assumption is justified that none of the atoms $p$ is contained in the
state $s$, then being possibly achievable is a necessary condition for being
achievable.

\begin{lemma}\label{lemma:achievablefolgtpossibly}
  Let $s$ be a state for which $p \not \in s$ and also $\forall o \in \act: p
  \in \add(o) \Rightarrow \pre(o) \cap s = \emptyset$ holds. Then we have
\[
\achievable(s,p,\act) \Rightarrow \pachievable(p,\act)
\]
\end{lemma}

\begin{beweis}
  From $\achievable(s,p,\act)$ and $p \not \in s$, we know that there
  is a step $o \in \act$, $p \in \add(o)$, with $\forall \; p' \in
  \pre(o) \; \achievable(s,p',\act)$. We also know that $\pre(o) \cap s
  = \emptyset$, so for each $p' \in \pre(o)$ there must be an achiever
  $o' \in \act: p' \in \add(o')$.
\end{beweis}

\medskip

The condition that all of the facts $p$ must not be contained in the
state $s$ seems to be rather rigid. Nevertheless, the condition of
being possibly achievable delivers good results on all of the
benchmark domains and it is easy to decide. We can now use this test
to both

\begin{itemize}
\item perform a fixpoint reduction on the set $\False^A_{DA}$ and
\item decide whether an atomic goal $B$ should be ordered before $A$.
\end{itemize}

\medskip
\noindent
The fixpoint reduction, as depicted in Figure~\ref{fixpoint-algo} below,
uses the approximative test $\pachievable(f,\act^*)$ to remove facts
from $\False^A_{DA}$ that can be achieved. It finds {\em all} these
facts under certain restrictions, see below. As a side effect of the
fixpoint algorithm, we obtain the set $\act^*$ of actions that our
method assumes to be applicable after a state $s_{(A,\neg B)}$. We
then order $B$ before $A$ iff it cannot possibly be achieved using
these actions.

\newpage

\begin{figure}[htb]
\begin{center}
\begin{minipage}{10cm}
\begin{tabbing}
$\False^* := \False^A_{DA}$\\
$\act^* := \act_A \setminus \{ o \mid \False^*
                \cap \pre(o) \neq \emptyset \}$\\
$fixpoint\_reached := $ \false\\
{\bf while} \= $\neg fixpoint\_reached$\\
\>  $fixpoint\_reached := $ \true\\
\>  {\bf for} \= $f \in \False^*$\\
\>  \>  {\bf if} \= $\pachievable(f,\act^*)$ {\bf then}\\
\>  \> \>  $\False^* := \False^* \setminus \{f\}$\\
\>  \> \>  $\act^* := \act_A \setminus \{ o \mid \False^*
                \cap \pre(o) \neq \emptyset \}$\\
\> \> \>  $fixpoint\_reached := $ \false\\
\> \>  {\bf endif}\\
\>  {\bf endfor}\\
{\bf endwhile}\\
{\bf return} $\False^*$, $\act^{*}$
\end{tabbing}
\end{minipage}
\end{center}
\caption{\label{fixpoint-algo} Quick, heuristic fixpoint reduction of the set
  $\False^{A}_{DA}$.}
\end{figure}

The computation checks whether atoms of $\False^*$, which is initially
set to $\False^A_{DA}$, are possibly achievable using only those
actions, which do not delete $A$ and which do not require atoms from
$\False^*$ as a precondition.  Achievable atoms are removed from
$\False^*$, and $\act^*$ gets updated accordingly. If in one
iteration, $\False^*$ does not change, the fixpoint is reached, \ie
$\False^*$ will not further decrease and $\act^*$ will not further
increase---the final sets $\False^*$ of false facts and $\act^*$ of
applicable actions are returned.

Let us illustrate the fixpoint computation with a short example
consisting of the empty initial state, the goals $\{ A, B \}$, and the
following set of actions

\begin{center}
{\sl 
\begin{tabular}{lllll}
{\bf op1}: &         & $\longrightarrow$ & ADD \{ A \} \;  & DEL \{ C, D \}\\
{\bf op2}: &         & $\longrightarrow$ & ADD \{A, C \} \;  & DEL \{ D \} \\
{\bf op3}: & \{ C \} & $\longrightarrow$ & ADD \{ D \} & \\
{\bf op4}: & \{ D \} & $\longrightarrow$ & ADD \{ B \} &
\end{tabular}
}
\end{center}

When assuming that $A$ has been achieved, we obtain $\False^* =
\False^A_{DA}= \{ D \}$ as the initial value of the {\sf False} set,
since $D$ is the only atom that {\bf op1} and {\bf op2} delete when adding $A$.
Figure~\ref{Bilder/fix-example.eps} illustrates a hypothetical
planning process. Starting in the empty initial state and trying to
achieve $A$ first, we get two different states $s_{(A,\neg B)}$ in
which $A$ holds. The atom $D$ does not hold in any of them and thus in
both states, no action is applicable that requires $D$ as a
precondition. This excludes {\bf op4} from $\act_A$, yielding the
initial action set $\act^* = \{ {\bf op1}, {\bf op2}, {\bf op3}
\}$. Now, {\bf op4} is the only action that can add $B$. Therefore, if
we used this action set to see if $B$ can still be achieved, we would
find that this is {\em not} the case. Consequently, without performing
the fixpoint computation, we would order $B$ before $A$. But as can be
seen in Figure~\ref{Bilder/fix-example.eps}, this would not be a
reasonable ordering: there is the plan $ \langle ${\bf op3} $, ${\bf
op4}$ \rangle $ that achieves $B$ from the state $s_{(A,\neg B)} =
Result(\I,${\bf op2}$)$ without destroying $A$.



The fixpoint computation works us around this problem as follows:
There is the action {\bf op3}, which can add the precondition $D$ of
{\bf op4} without deleting $A$. When checking $\pachievable(D,\act^*)$
in the first iteration, the fixpoint procedure finds this action. It
then checks whether the preconditions of {\bf op3} are achievable in
the sense that they are added by another action. This is the case
since the only precondition $C$ is added by {\bf op2}. Thus, $D$ is
removed from $\False^*$, which becomes empty now. The action {\bf op4}
is put back into the set $\act^*$, which now becomes identical with
the action set $\act_A$. This set, in turn, is identical with the
original action set $\act$ as no action deletes $A$. The fixpoint
process terminates and $B$ will not be ordered before $A$ as it can be
achieved using the action {\bf op4}. This correctly reflects the fact
that there exists a plan from the state $s_{(A,\neg B)} = Result(\I,
\langle {\bf op2} \rangle ) = \{ C, A \}$ to a state that satisfies
$B$ without destroying $A$.

\bigskip

\scalefig{0.7}{Bilder/fix-example.eps}{An example illustrating why we need
  the fixpoint computation.}

\bigskip

As already pointed out, the intention behind the fixpoint procedure is
the following: Starting from a state $s_{(A,\neg B)}$, we want to know
which facts can become \true\ without destroying $A$, and
consequently, which actions can become applicable. In the first step,
only actions that do not use any of the facts in $\False^A_{DA}$ are
applicable, as all those facts are deleted from the state description
when $A$ is added. However, such actions may make facts in
$\False^A_{DA}$ \true, so we want to remove those facts from
$\False^A_{DA}$. If we manage to find {\em all} the facts that can be
made \true\ without destroying $A$, then the final set $\False^*$ will
contain only those facts that do not hold in a state reachable from
$s_{(A,\neg B)}$ without destroying $A$. In this case, the final
action set $\act^*$ will contain {\em all} the actions that can be
applied after $s_{(A,\neg B)}$, and we can safely use this action set
to determine whether another goal $B$ can still be achieved or not.

However, as we only use the approximative test
$\pachievable(f,\act^*)$ with $f \in \False^*$ to find out if a fact
in the current $\False^*$ set is achievable, there may be facts which are
achievable without destroying $A$, but which remain in the set
$\False^*$. This could exclude actions from the set $\act^*$ which can
be safely applied after $s_{(A,\neg B)}$. Under certain restrictions,
however, we can prove that this will not happen. In order to do so, we
need to impose a restriction on the particular state $s_{(A,\neg B)}$,
in which we achieved the goal $A$: If none of the preconditions of
actions, which add facts contained in $F^A_{DA}$, occur in the state
$s_{(A,\neg B)}$, then the fixpoint procedure will remove all facts
from $F^A_{DA}$ that are achievable without destroying $A$. We will
use this property of the fixpoint procedure later to show that our
heuristic ordering relation approximates reasonable orderings.

\begin{lemma}\label{lemma:fixpoint-algo}
  Let $(\act,\I,\G)$ be a planning problem, and let $A \in \G$ be an atomic
  goal. Let $s_{(A,\neg B)}$ be a reachable state where $A$ has just been
  achieved. Let $\PP^{\act_A} =  \langle o_1, \dots, o_n \rangle $ be
  a sequence of actions not destroying $A$. Let $\False^*$ be the set
  of facts that is returned by the fixpoint computation depicted in
  Figure~\ref{fixpoint-algo}. If we have

\begin{equation}
\forall f \in \False^A_{DA}: \forall o \in \act_A: f \in \add(o) \Rightarrow
\pre(o) \cap s_{(A,\neg B)} = \emptyset \tag{$*$}
\end{equation}

then no fact in $\False^*$ holds in the state that is reached by applying
$\PP^{\act_A}$, \ie
\[
Result(s_{(A,\neg B)},\PP^{\act_A}) \cap \False^* = \emptyset
\]
\end{lemma}

\begin{beweis} 

Let $\False^*_j$ and $\act^*_j$ denote the state of the fact and
action sets, respectively, after $j$ iterations of the algorithm
depicted in Figure~\ref{fixpoint-algo}. As $\False^*$ only decreases
during the computation, we have $\False^* \subseteq \False^*_j$ for
all $j$. Let $s_0, \dots, s_n$ denote the sequence of states that are
encountered when executing $\PP^{\act_A} = \langle o_1, \dots, o_n
\rangle $ in $s_{(A,\neg B)}$, \ie $s_0 = s_{(A, \neg B)}$ and $s_i =
Result(s_{i-1}, \langle o_i \rangle )$ for $0 \leq i \leq n$. We can
assume that each action $o_i$ is applicable in state $s_{i-1}$, \ie
$\pre(o_i) \subseteq s_{i-1}$. Otherwise, $o_i$ does not cause any
state transition, and we can skip it from $\PP^{\act_A}$. Obviously,
we have $s_n = Result(s_{(A,\neg B)},\PP^{\act_A})$, so we need to
show that $s_n \cap \False^* = \emptyset$.  The proof proceeds by
induction over the length $n$ of $\PP^{\act_A}$.


\medskip
  
\underline{$n=0$}: $\PP^{\act_A} = \langle \rangle $ and $s_n = s_0 =
s_{(A,\neg B)}$. All facts in $\False^A_{DA}$ are deleted from the
state description when $A$ is added, so we have $s_n \cap
\False^A_{DA} = \emptyset$. As $\False^A_{DA} = \False^*_0$ and
$\False^* \subseteq \False^*_0$, the proposition follows immediately.


\medskip 

\underline{$n \rightarrow n+1$}: $\PP^{\act_A} = \langle o_1,\dots,
o_n, o_{n+1} \rangle $. From the induction hypothesis, we know that $s_i \cap
\False^* = \emptyset$ for $0 \leq i \leq n$. What we need to show is
$s_{n+1} \cap \False^* = \emptyset$.

Let $j$ be the step in the fixpoint iteration where 
$\False^*_j \cap \bigcup_{i = 0, \dots, n} s_i$ becomes empty, \ie $j$
denotes the iteration in which the intersection of all the states
$s_i, i \leq n$ with $\False^*_j$ is empty for the first time. Such an
iteration exists, because all the intersections $s_i \cap \False^*$
with $i \leq n$ are empty.

Now each action $o_i, 1 \leq i \leq n+1$ is applicable in state
$s_{i-1}$, \ie $\pre(o_i) \subseteq s_{i-1}$, and thus $\pre(o_i) \cap
\False^*_j = \emptyset$ for all the actions $o_i$ in
$\PP^{\act_A}$. Therefore, all these actions are contained in
$\act^*_j$, as this set contains all the actions out of $\act_A$ whose
intersection with $\False^*_j$ is empty. Let us focus on the
facts in the state $s_{n+1}$. All these facts are achieved by executing
$\PP^{\act_A}$ in $s_{(A,\neg B)}$. In other words, there is a plan
from $s_{(A,\neg B)}$ to each of these facts. As we have just seen,
this plan consists out of actions in $\act^*_j$. Applying
Lemma~\ref{lemma:planfolgtachievable} to all the facts $p \in
s_{n+1}$ using $s_{(A,\neg B)}$ and $\PP^{\act_A}$ ($ =
\PP^{\act^*_j}$), we know that all facts $p$ are achievable using
actions from $\act^*_j$. 
\[ 
\forall p \in s_{n+1}: \achievable(s_{(A,\neg B)},p,\act^*_{j}) 
\] 
We will now show that those facts $f \in s_{n+1}$ we are interested in,
namely the \False\ facts that are added by $o_{n+1}$ and that are
still contained in $\False_j$, are also {\em possibly} achievable
using actions from $\act^*_j$. Let $f$ be a fact $f \in s_{n+1}$, $f
\in \False^*_j$. We apply Lemma~\ref{lemma:achievablefolgtpossibly}
using $s_{(A,\neg B)}$, $f$, and $\act^*_j$. We {\em can} apply
Lemma~\ref{lemma:achievablefolgtpossibly} as obviously $f \not \in
s_{(A,\neg B)}$, and as $\forall o \in \act^*_j: f \in \add(o)
\Rightarrow \pre(o) \cap s_{(A,\neg B)} = \emptyset$ by prerequisite
$(*)$. With $\achievable(s_{(A,\neg B)},p,\act^*_{j})$, we arrive at
\[
\forall f \in s_{n+1} \cap \False^*_j: \pachievable(f,\act^*_{j}) 
\] 
What remains to be proven is that all these facts $f$ will be removed
from $\False^*$ during the fixpoint computation. With the
argumentation above, it is sufficient to show that all the facts $f
\in s_{n+1} \cap \False^*_j$ will get tested for
$\pachievable(f,\act^*_{j})$ in iteration $j+1$ of the fixpoint
computation. These tests will succeed and lead to $s_{n+1} \cap
\False^*_{j+1} = \emptyset$, yielding, as desired, $s_{n+1} \cap
\False^* = \emptyset$. Remember that $\False^*_{j+1} \supseteq
\False^*$.  There are two cases, which we need to consider:

\begin{enumerate} 
  
\item $j = 0$: all intersections $s_i \cap \False^*_0$ are initially
  empty, \ie $s_i \cap \False^A_{DA} = \emptyset$ for $0 \leq i \leq
  n$. In this case, all facts $f \in s_{n+1} \cap \False^A_{DA}$ are
  tested for $\pachievable(f,\act^*_{0})$ in iteration $j+1 = 1$ of
  the fixpoint computation.

  
\item $j > 0$: in this case, at least one of the intersections $s_i
  \cap \False^*_j$ became empty in iteration $j$ by definition of $j$,
  \ie at least one fact was removed from $\False^*$ in this iteration.
  Therefore, the fixpoint has not been reached yet, and the
  computation performs at least one more iteration, namely iteration
  $j+1$. All facts in $\False^*_j$ will be tested in this iteration,
  in particular all facts $f \in s_{n+1} \cap \False^*_j$.

\end{enumerate}

With these observations, the induction is complete and the proposition is
proven. 
\end{beweis}



As has already been said, we now simply order $B$ before $A$, if it is
not possibly achievable using the action set that resulted from the
fixpoint computation. The ordering relation $\leq_h$ (where $h$ stands
for ``heuristic'') obtained in this way approximates the reasonable
goal ordering $\leq_r$.

\begin{def1}[Heuristic Ordering $\leq_h$]
  Let $(\act,\I,\G \supseteq \{A,B\})$ be a planning problem. Let
  $\act^{*}$ be the set of actions that is obtained from $\act$ by
  performing the fixpoint computation shown in
  Figure~\ref{fixpoint-algo}.

\noindent
The ordering $B \leq_h A$ holds if and only if 
\[
\neg \pachievable(B,\act^{*})
\]
\end{def1}

If $A$ has been reached in a particular state $s_{(A,\neg B)}$ where
the assumptions made by the fixpoint computation and by the test for
$\pachievable(B,\act^{*})$ are justified, then being not possibly
achievable is a sufficient condition for the non-existence of a plan
to $B$ that does not temporarily destroy $A$.

\begin{theorem}\label{leqhimplizierung}
  Let $(\act,\I,\G)$ be a planning problem, and let $A,B \in \G$ be
  two atomic goals. Let $s_{(A,\neg B)}$ be a reachable state where
  $A$ has just been achieved, but $B$ is still false, \ie $B \not \in
  s_{(A,\neg B)}$. Let $\False^*$ and $\act^{*}$ be the sets of facts
  and actions, respectively, that are derived by the fixpoint
  computation shown in Figure~\ref{fixpoint-algo}. If we have

\begin{equation}
\forall f \in \False^A_{DA} \cup \{ B \}: \forall o \in \act_A: f \in
\add(o) \Rightarrow \pre(o) \cap s_{(A,\neg B)} = \emptyset \tag{$**$}
\end{equation}

then we have
\[
\neg \pachievable(B,\act^*) \Rightarrow \neg \exists \PP^{\act_A}: \;
B \in Result(s_{(A,\neg B)},\PP^{\act_A})
\]
\end{theorem}



\begin{beweis} 
Assume that there is a plan $\PP^{\act_A} = \langle o_1, \dots, o_n
\rangle $ that does not destroy $A$, but achieves $B$, \ie $B \in
Result(s_{(A,\neg B)}, \langle o_1, \dots, o_n \rangle )$. With the
restriction of $(**)$ to the facts in $\False^A_{DA}$,
Lemma~\ref{lemma:fixpoint-algo} can be applied to each action sequence
$ \langle o_1, \dots, o_{i-1} \rangle $ yielding $Result(s_{(A,\neg
B)}, \langle o_1, \dots, o_{i-1} \rangle ) \cap \False^* =
\emptyset$. Consequently, each $o_i$ is either

\begin{itemize}
\item not applicable in $Result(s_{(A,\neg B)}, \langle o_1, \dots,
  o_{i-1} \rangle )$,
\item or its preconditions are contained in $Result(s_{(A,\neg B)},
    \langle o_1, \dots, o_{i-1} \rangle )$, yielding $\pre(o_i) \cap
    \False^* = \emptyset$.  
\end{itemize}

In the first case, we simply skip $o_i$ as it does not have any
effects. In the second case, $o_i \in O^*$ follows. Thus, we have a
plan constructed out of actions in $O^*$ that achieves $B$ from
$s_{(A,\neg B)}$.  Applying Lemma~\ref{lemma:planfolgtachievable}
leads us to $\achievable(s_{(A,\neg B)},B,O^*)$. We have $B \not \in
s_{(A,\neg B)}$. We also know, from $(**)$ with respect to $B$, as
$\act^* \subseteq \act_A$, that $\forall o \in \act^*: B \in \add(o)
\Rightarrow \pre(o) \cap s_{(A,\neg B)} = \emptyset$ holds. Therefore,
we can now apply Lemma~\ref{lemma:achievablefolgtpossibly} and arrive
at $\pachievable(B,\act^*)$, which is a contradiction.
\end{beweis}

\noindent
We return to the {\em blocks world} example and show how the computation of
$\leq_h$ proceeds. Let us first investigate whether $on(a,b) \leq_h
on(b,c)$ holds. The initial value for $\False^{on(b,c)}_{DA}$ is obtained
from the delete list of the {\bf stack(b,c)} action, which is the
only one that adds this goal.

\[ 
\False^{on(b,c)}_{DA} = \{ clear(c), holding(b) \}
\]

Intuitively, it is immediately clear that neither of these facts can
ever hold in a state where $on(b,c)$ is true: if $b$ is on $c$, then
$c$ is not clear and the gripper cannot hold $b$. It turns out that
the fixpoint computation respects this intuition and leaves the set
$\False^{on(b,c)}_{DA}$ unchanged, yielding $\False^* = \{ clear(c),
holding(b) \}$. We do not repeat the fixpoint process in detail here,
because it can be reconstructed from Figure~\ref{fixpoint-algo} and
the details are not necessary for understanding how the correct
ordering relations are derived. In short, for both facts there are
achievers in the reduced action set, but all of them need
preconditions for which no achiever is available. For example,
$holding(b)$ can be achieved by either an {\bf unstack} or a {\bf
pickup} action. Both either need $b$ to stand on another block or to
stand on the table. All actions that can achieve these facts need
$holding(b)$ to be \true\ and are thus excluded from the reduced
action set.

After finishing the fixpoint computation, the planner tests
$\pachievable(on(a,b),\act^*)$, where $\act^*$ contains all actions
except those that delete $on(b,c)$ and those that use $clear(c)$ or
$holding(b)$ as a precondition. It finds that the action {\bf
  stack(a,b)} adds $on(a,b)$. The preconditions of this action are
$holding(a)$ and $clear(b)$. These conditions are added by the actions
{\bf pickup(a)} and {\bf unstack(a,b)}, respectively, which are both
contained in $\act^*$: neither of them needs $c$ to be clear or $b$ to
be in the gripper. Thus, the test finds that in fact, $on(a,b)$ is
possibly achievable using the actions in $\act^*$, and no ordering is
derived, \ie $on(a,b) \not \leq_h on(b,c)$ follows.

Now, the other way round, $on(b,c) \leq_h on(a,b)$ is tested. The
initial value for $\False^{on(a,b)}_{DA}$ is obtained from the single
action {\bf stack(a,b)} as
\[
\False^{on(a,b)}_{DA} = \{ clear(b), holding(a) \}
\]
%\begin{sloppypar}
Again, the fixpoint computation does not cause any changes, resulting
in $\False^* = \{ clear(b),$ $holding(a) \}$. The process now tests
whether $\pachievable(on(b,c),\act^*)$ holds, where $O^*$ contains all
actions except those that delete $on(a,b)$ and those that use
$clear(b)$ or $holding(a)$ as a precondition. The only action that can
add $on(b,c)$ is {\bf stack(b,c)}. This action needs as preconditions
the facts $holding(b)$ and $clear(c)$. The process now finds that a
crucial condition for achieving the first fact is violated: Each
action that can achieve $holding(b)$ has $clear(b)$ as a precondition,
because $b$ must be clear first before the gripper can hold it. Since
$clear(b)$ is an element of $\False^*$, none of the actions achieving
$holding(b)$ is contained in $\act^*$. Consequently, the test for
$\pachievable(on(b,c),\act^*)$ fails and we obtain the ordering
$on(b,c) \leq_h on(a,b)$. This makes sense as the gripper cannot grasp
$b$ and stack it onto $c$ anymore, once $on(a,b)$ is achieved.
%\end{sloppypar}




\subsection{On Forced Goal Orderings and Invertible Planning Problems}
\label{no-forced}

So far, we have introduced two easily computable ordering relations
$\leq_h$ and $\leq_e$ that both approximate the reasonable goal
ordering $\leq_r$. One might wonder why we do not invest any effort in
trying to find {\em forced} goal orderings. There are two reasons for
that:

\begin{enumerate}
\item As we have already seen in Section~\ref{relation}, any forced
  goal ordering is also a reasonable goal ordering, \ie a method that
  approximates the latter can also be used as a crude approximation to
  the former.
\item Many benchmark planning problems are {\em invertible} in a
  certain sense. Those problems do not contain forced orderings
  anyway.
\end{enumerate}

In this section, we elaborate in detail the second argument. The
results are a bit more general than necessary at this point. We want
to make use of them later when we show that the Agenda-Driven
planning algorithm we propose is complete with respect to a certain
class of planning problems. We proceed by formally defining this class
of planning problems, show that these problems do not contain forced
orderings, and identify a sufficient criterion for the membership of a
problem in this class. Finally, we demonstrate that many benchmark
planning problems do in fact satisfy this criterion. For a start, we
introduce the notion of a {\em deadlock} in a planning problem.

\begin{def1}[Deadlock]
\label{deadlock}
Let $(\act,\I,\G)$ be a planning problem. A reachable state $s$ is called a
{\em deadlock} iff there is no sequence of actions that leads from $s$ to the
goal, \ie iff $s = Result(\I,\PP^{\act})$ and $\neg \exists \; \PP^{'\act}:
\; \G \subseteq Result(s,\PP^{'\act})$.
\end{def1}

The class of planning problems we are interested in is the class of
problems that are {\em deadlock-free}. Naturally, a problem is called
deadlock-free if none of its reachable states is a deadlock in the
sense of Definition~\ref{deadlock}.

Non-trivial forced goal orderings imply the existence of deadlocks
(remember that an ordering $B \leq_f A$ or $B \leq_r A$ is called {\em
  trivial} iff there is no state $s_{(A,\neg B)}$ at all).

\begin{lemma}
\label{forcedfolgtdeadlock}
Let $(\act,\I,\G)$ be a planning problem, and let $A,B \in \G$ be two atomic
goals. If there is a non-trivial forced ordering $B \leq_f A$ between $A$ and
$B$, then there exists a deadlock state $s$ in the problem.
\end{lemma}

\begin{beweis}
Recalling Definition~\ref{trivial} and assuming non-triviality of
$\leq_f$, we know that there is at least one state $s_{(A,\neg B)}$
where $A$ is made \true, but $B$ is still \false. From
Definition~\ref{f-ord}, we know that there is no plan in any such
state that achieves $B$. In particular, it is not possible to achieve
all {\em goals} starting out from $s_{(A,\neg B)}$. Thus, the state $s
:= s_{(A,\neg B)}$ must be a deadlock.  
\end{beweis}

We will now investigate deadlocks in more detail and discuss that most
of the commonly used benchmark problems do not contain them, \ie they
are deadlock-free. With Lemma~\ref{forcedfolgtdeadlock}, we then also
know that such domains do not contain non-trivial forced goal
orderings either---so there is not much point in trying to find them.
We do not care about trivial goal orderings. Such orderings force any
reasonable planning algorithm to consider the goals in the correct
order.

The existence of deadlocks depends on structural properties of a
planning problem: There must be action sequences, which, once
executed, lead into states from which the goals cannot be reached
anymore. These sequences must have undesired effects, which cannot be
inverted by any other sequence of actions in $\act$. Changing
perspective, one obtains a hint on how a sufficient condition for the
{\em non-existence} of deadlocks might be defined. Assume we have a
planning problem where the effects of each action sequence in the
domain can be inverted by executing a certain other sequence of
actions. In such an {\em invertible} planning problem, it is in
particular possible to get back to the {\em initial state} from each
reachable state. Therefore, if such a problem is solvable, then it
does not contain deadlocks: From any state, one can reach all goals by
going back to the initial state first, and then execute an arbitrary
solution thereafter. We will now formally define the notion of
invertible planning problems, and turn the above argumentation into a
proof.

\begin{def1}[Invertible Planning Problem]
\label{invertibleP}
Let $(\act,\I,\G)$ be a planning problem, and let $s$ denote the states that
are reachable from $\I$ with actions from $\act$. The problem is called {\em
  invertible} if and only if
\[
\forall \; s: \; \; \forall \; \PP^\act: \; \exists \; \overline{\PP}^{\act}:
\; Result(Result(s,\PP^\act),\overline{\PP}^{\act}) = s
\]
\end{def1}

\begin{theorem}\label{theorem:invertible-nodeadlocks}
Let $(\act,\I,\G)$ be an invertible planning problem, for which a
solution exists. Then $(\act,\I,\G)$  does not contain any deadlocks.
\end{theorem}

\begin{beweis}
  Let $s = Result(\I,\PP_s^{\act})$ be an arbitrary reachable state.
  As the problem is invertible, we know that there is a sequence of
  actions $\overline{\PP}_s^{\act}$ for which
  $Result(s,\overline{\PP}_s^{\act}) = \I$ holds. As the problem is
  solvable, we have a solution plan $\PP^{\act}$ starting from $\I$
  and achieving $\G \subseteq Result(\I,\PP^{\act})$. Together, we
  obtain $\G \subseteq
  Result(Result(s,\overline{\PP}_s^{\act}),\PP^{\act})$. Therefore,
  the concatenation of $\overline{\PP}_s^{\act}$ and $\PP^{\act}$ is a
  solution plan executable in $s$ and consequently, $s$ is no
  deadlock.
\end{beweis}

\noindent
We now know that invertible planning problems, if solvable, do not contain
deadlocks and consequently, they do not contain (non-trivial) forced goal
orderings. What we will see next is that, as a matter of fact, most benchmark
 planning problems {\em are} invertible. We arrive at a sufficient
condition for invertibility through the notion of {\em inverse actions}.

\begin{def1}[Inverse Action]\label{def:inverse}
  Given an action set $\act$ containing an action $o$ of the form
  $\pre(o) \longrightarrow \add(o) \;  \; \del(o)$. An action $\overline{o}
  \in \act$ is called {\em inverse} to $o$ if and only if
  $\overline{o}$ has the form $\pre(\overline{o}) \longrightarrow
  \add(\overline{o}) \;  \; \del(\overline{o})$ and satisfies the
  following conditions
\begin{enumerate}\addtolength{\itemsep}{-2mm}
\item $\pre(\overline{o}) \subseteq \pre(o) \cup \add(o) \setminus \del(o)$
\item $\add(\overline{o}) = \del(o)$
\item $\del(\overline{o}) = \add(o)$
\end{enumerate}
\end{def1}

\noindent
Under certain conditions, applying an inverse action leads back to the
state one started from.

\begin{lemma}\label{lemma:inverse}
  Let $s$ be a state and $o$ be an action, which is applicable in $s$.
  If $\del(o) \subseteq \pre(o)$ and $s \; \cap \; \add(o) =
  \emptyset$ hold, then an action $\overline{o}$ that is inverse to $o$ in
  the sense of Definition~\ref{def:inverse} is applicable in
  $Result(s, \langle o \rangle )$ and $Result(Result(s, \langle o
  \rangle ), \langle \overline{o} \rangle ) = s$ follows.
\end{lemma}

\begin{beweis}
  As $o$ is applicable in $s$, we have $\pre(o) \subseteq s$. The atoms
  in $\add(o)$ are added, and the atoms in $\del(o)$ are removed from $s$,
  so altogether we have 
\[
Result(s, \langle o \rangle ) \supseteq (\pre(o) \cup \add(o))
  \setminus \del(o) \supseteq \pre(\overline{o})
\]
Thus, $\overline{o}$ is applicable in $Result(s, \langle o \rangle )$. 


\noindent 
Furthermore, we have $Result(s, \langle o \rangle ) = s \cup
\add(o) \setminus \del(o)$ and with that
\[
\begin{array}{llr}
 & Result(Result   (s, \langle o \rangle ), \langle \overline{o}
\rangle ) & \\[2mm] 
= &  Result(s \cup \add(o) \setminus \del(o), \langle \overline{o} \rangle )  \\[2mm] 
= & (s \cup \add(o) \setminus \del(o)) \cup \add(\overline{o}) \setminus
\del(\overline{o})  \\[2mm] 
= & (s \cup \add(o) \setminus \del(o)) \cup \del(o) \setminus \add(o) 
  & \mbox{(cf. Definition~\ref{def:inverse})}\\[2mm] 
= & s \cup \add(o) \setminus \add(o)
  & (\mbox{because }\del(o) \subseteq \pre(o) \subseteq s)\\[2mm]
= & s 
  & (\mbox{because }s \cap \add(o) = \emptyset)\\
\end{array}\]\end{beweis}

\noindent 
Lemma~\ref{lemma:inverse} states two prerequisites: (1)
inclusion of the operator's delete list in its preconditions and (2)
an empty intersection of the operator's add list with the state where
it is applicable. A planning problem is called invertible if it
meets both prerequisites and if there is an
inverse to each action.

\begin{theorem}\label{theorem:inverse}
  Given a planning problem $(\act,\I,\G)$ with the set of ground
  actions $\act$ satisfying $\del(o) \subseteq \pre(o)$ and $\pre(o)
  \subseteq s \Rightarrow \add(o) \cap s = 
  \emptyset$ for all actions and reachable states $s$. If there
  is an inverse action $\overline{o} \in \act$ for each action $o \in
  \act$, then the problem is invertible.
\end{theorem}

\begin{beweis}
  Let $s$ be a reachable state, and let $\PP^{\act} =  \langle o_1,
  \dots o_n \rangle $ be a  sequence of actions. We need to show the
  existence of a sequence $\overline{\PP}^{\act}$ for which
\begin{equation}
Result(Result(s,\PP^{\act}),\overline{\PP}^{\act}) = s \tag{$***$}
\end{equation}

\noindent
holds. We define $\overline{\PP}^{\act} :=  \langle \overline{o_n}, \dots,
  \overline{o_1} \rangle $, and prove $(***)$ by induction over $n$.

\medskip
\noindent
\underline{$n=0$}: Here, we have $\PP^{\act} = \overline{\PP}^{\act} = \langle
\rangle $, and $Result(Result(s, \langle \rangle ), \langle \rangle )
= s$ is obvious.

\medskip
\noindent
\underline{$n \rightarrow n+1$}: Now $\PP^{\act} = \langle o_1, \dots, o_n,
o_{n+1} \rangle $. From the induction hypothesis we know that
$Result(Result(s, \langle o_1, \dots, o_n \rangle ), \langle
\overline{o_n}, \dots, \overline{o_1} \rangle ) = s$. To make the
following a bit more readable, let $s'$ denote $s' := Result(s,
\langle o_1, \dots, o_n \rangle )$. We have
\[
\begin{array}{llr}
& Result(Result(s, \langle o_1, \dots, o_{n+1} \rangle ), \langle
    \overline{o_{n+1}}, \dots, \overline{o_1} \rangle ) &\\[2mm]
= & Result(Result(s', \langle o_{n+1} \rangle ),  \langle
    \overline{o_{n+1}}, \dots, \overline{o_1} \rangle ) & \\[2mm] 
= & Result(Result(Result(s', \langle o_{n+1} \rangle ), \langle
    \overline{o_{n+1}} \rangle ), \langle \overline{o_n}, \dots,
    \overline{o_1} \rangle ) & \\[2mm] 
= & Result(s', \langle \overline{o_n}, \dots, \overline{o_1} \rangle ) 
  & \mbox{(cf. Lemma~\ref{lemma:inverse} on} \; s' \;
    \mbox{and} \; o_{n+1}) \\[2mm] 
= & s  & \mbox{(per induction)}\\
\end{array}
\]
\end{beweis}

Altogether, we know now that invertible problems, if solvable, do not
contain forced orderings. We also know that problems, where there is
an inverse action to each action in $\act$, are invertible following
Theorem~\ref{theorem:inverse}. Theorem~\ref{theorem:inverse} requires
$\del(o) \subseteq \pre(o)$ to hold for each action $o$, and $\pre(o)
\subseteq s \Rightarrow \add(o) \cap s = \emptyset$ to hold for all
actions and reachable states $s$.  We will see that all conditions,
(a) inclusion of the delete list in the precondition list, (b) empty
intersection of an action's add list with reachable states where it is
applicable, and (c) existence of inverse actions, hold in most
currently used benchmark domains.\footnote{In order to avoid reasoning about
  reachable states in condition (b), one could also postulate that an
  action has all of its add effects as {\em negative preconditions}, cf.\
  \cite{jonsson:haslum:backstrom:ai-00}. This is, however, not commonly used in the typical planning benchmark problems.}

Concerning the  condition (a) that actions only delete facts they
require as preconditions, one finds this phenomenon in {\em all}
domains that are commonly used by the planning community, at least in
those that are known to the authors. It is just something that seems
to hold in any reasonable logical problem formulation. Some authors
even postulate it as an assumption for their algorithms to work, cf.\
\cite{fox-jair}.

Similarly in the case of conditions (b) and (c): One usually finds
inverse actions in benchmark domains. Also, an action's preconditions
usually imply---by state invariants---that its add effects are all
\false. For example in the {\em blocks world}, {\bf stack} and {\bf
unstack} actions invert each other, and an action's add effects are
exclusive of its preconditions---the former are contained in the union
of the {\sf False} constructed for the preconditions, see
Section~\ref{reasonable:graphplan}. Similarly in domains that deal
with logistics problems, for example {\em logistics}, {\em trains},
{\em ferry}, {\em gripper} etc., one can often find inverse pairs of
actions with their preconditions always excluding the add
effects. Sometimes, two different ground instances of the same
operator schema yield an inverse pair.  For example, in {\em gripper},
the two ground instances

{\sl 
\begin{tabbing}
{\bf move(roomA, roomB)}\\
at-robby(roomA) $\longrightarrow$  ADD at-robby(roomB) DEL at-robby(roomA).
\end{tabbing}}

\noindent
and

{\sl 
\begin{tabbing}
{\bf move(roomB, roomA)}\\
at-robby(roomB) $\longrightarrow$ ADD at-robby(roomA) DEL at-robby(roomB).
\end{tabbing}}

\noindent
of the {\bf move(?from,?to)} operator schema invert each other.
Similarly, in {\em towers of hanoi}, where there is only the single
{\bf move} operator schema, an inverse instance can be found for each
ground instance of the schema, and the add effects are always \false\
when the preconditions are \true.

Only very rarely, non-invertible actions can be found in benchmark
domains. If they occur, their role in the domain is often quite
limited as for example the operators {\bf cuss} and {\bf inflate} in
Russel's Tyreworld.

{\sl 
\begin{tabbing}
{\bf cuss} \\
$\longrightarrow$ DEL annoyed().
\end{tabbing}}

{\sl 
\begin{tabbing}
{\bf inflate(?x:wheel)}\\
have(pump) not-inflated(?x) intact(?x) $\longrightarrow$ 
ADD inflated(?x) DEL not-inflated(?x).
\end{tabbing}}

Obviously, there is not much point in defining something like a {\bf
decuss} or a {\bf deflate} operator. More formally speaking, none of
the ground actions to these operators destroys a goal or a
precondition of any other action in the domain. Therefore, it does not
matter that their effects cannot be inverted. In particular, no forced
goal ordering can be derived wrt.\ these actions.~\footnote{The {\bf
cuss} operator, by the way, is the only one known to the authors that
deletes a fact it is not using as a precondition. It is also the only
one we know that could be removed from the domain description without
changing anything.}

The importance of inverse actions in real-world domains has also been
discussed by Nayak and Williams \citeyear{nayak}, who describe the
planner BURTON controlling the Cassini spacecraft. In contrast to
these domains, problems such as those for example used by Barrett et
al.\ in \citeyear{barrett94} almost never contain inverse actions.
Consequently, in these domains plenty of forced goal orderings could
be discovered and used by a planner to avoid deadlock situations. The
widespread, although perhaps unconscious use of invertible problems
for benchmarking is a current phenomenon related to STRIPS descending
planning systems. As one of the anonymous reviewers pointed out to us,
quite a number of non-invertible planning problems have also been
proposed in the planning literature, \eg the {\em register assignment}
problem \cite{nilsson-pai}, the {\em robot crossing a road} problem
\cite{sanborn}, some instances of manufacturing problems \cite{regli},
and the {\em Yale Shooting} problem \cite{ysp}. For these 
problems, \ie for problems that are not invertible, one could---in the
spirit of argument 1 at the very beginning of this section---simply
use $\leq_e$ and $\leq_h$ to approximate forced orderings if one is
interested in finding at least those. More precisely, $\leq_e$ and
$\leq_h$ are methods that might detect forced orderings---as those are
also reasonable---but that might also find more, not necessarily
forced, orderings. If one is not interested in finding {\em only} the
forced orderings, this is a possible way to go. For example, in a
simple {\em blocks world} modification where blocks cannot be
unstacked anymore once they are stacked---which {\em forces} the
planner to build the stacks bottom up---both $\leq_e$ and $\leq_h$ are
still capable of finding the correct goal orderings.



\subsection{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}{ll}
 o : & \phi_0(o)  = \pre_0(o) \longrightarrow \eff^+_0(o), \eff^-_0(o)\\
      & \phi_1(o) = \pre_1(o) \longrightarrow \eff^+_1(o), \eff^-_1(o)\\ 
      & \vdots \\
      & \phi_n(o) = \pre_n(o)  \longrightarrow \eff^+_n(o),\eff^-_n (o)
\end{array} 
\]

All unconditional elements of the action are summarized in
$\phi_0(o)$: The precondition of the action is denoted with
$\pre_0(o)$, and its unconditional positive and negative effects with
$\eff^+_0(o)$ and $\eff^-_0(o)$, respectively. Each conditional effect
$\phi_i(o)$ consists of an effect condition (antecedent) $\pre_i(o)$,
and the positive and negative effects $\eff^+_i(o)$ and $\eff^-_i(o)$.
Additionally, we denote with $\Phi(o)$ the set of all unconditional
and conditional effects, \ie $\Phi(o) = \{ \phi_0(o), \phi_1(o), \dots
,\phi_n(o) \}$.

The computation of $\leq_e$ immediately carries over to ADL actions
when an extension of planning graphs is used, which can handle
conditional effects, \eg \ipp\ \cite{jk-ecp97} or SGP \cite{sgp}. One
simply takes the set of exclusive facts that is returned by these
systems to determine the set $F^A_{GP}$. The test from
Definition~\ref{ord-e}, which decides whether there is an ordering $B
\leq_e A$ of two atomic goals $A$ and $B$, is extended to ADL as follows.

\begin{def1}[Ordering $\leq_e$ for ADL]\label{ord-e-adl}
Let $(\act,\I,\G \supseteq \{A,B\})$ be a planning problem. Let
$\False^A_{GP}$ be the {\sf False} set for $A$.  The ordering $B
\leq_e A$ holds if and only if
\[ 
\forall \; o \in \act, \; \phi_i(o) \in \Phi(o): B \in \eff_i^+(o)
\wedge A \not \in D_i(o) \; \Rightarrow (pre_i(o) \cup pre_0(o)) \cap
\False^A_{GP} \neq \emptyset
\]
Here, $D_i(o)$ denotes all negative effects that are implied by the
conditions of $\phi_i(o)$.
\[
D_i(o) := \left\{ \begin{array}[]{ll}
    \eff^-_0(o) \cup \bigcup_{\pre_j(o) \; \subseteq \; \pre_i(o)}
    \eff^-_j(o) & i \neq 0\\
    \eff^-_0(o) & i = 0 \end{array} 
  \right.
\]
\end{def1}

\noindent
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 $\phi_i$ requires all the conditions in $pre_i(o) \cup
pre_0(o)$ to be satisfied, which is impossible in any state where $A$
holds because of the non-empty intersection with $\False^A_{GP}$.


The computation of $\leq_h$ requires a little more adaptation effort.
In order to obtain the set $F^A_{DA}$, 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 $D_i(o)$.
\[
D(o) := \bigcap_{A \; \in \; \eff_i^+(o)} D_i(o)
\]
These are exactly the facts that are always deleted by $o$ when
achieving $A$, no matter which effect we use. 

The intersection of the sets $D(o)$ for all actions $o$ yields the
desired set $F^A_{DA}$.  Let us consider the following small example
to clarify the computation.
\[
\begin{array}{lll}
\phi_0(o) = \{ U \}    & \longrightarrow  & \{ W \} \; \{ \neg X \};\\
\phi_1(o) = \{ V, W \} & \longrightarrow & \{ A \} \; \{ \neg X \};\\
\phi_2(o) = \{ W \}    & \longrightarrow & \{ U \} \; \{  \neg Y \}
\end{array}
\]

We obtain $D_{1}(o) = \{ \neg X \} \cup \{ \neg Y \} = \{ \neg X, \neg
Y \}$, because the precondition of $\phi_2(o)$ is implied by the first
conditional effect $\phi_1(o)$. As $\phi_1(o)$ is the only effect that
can achieve $A$, we get $D(o) = D_1(o) = \{ \neg X, \neg Y \}$. 

We obtain a smaller set $D(o)$, if we add $A$ as an unconditional
positive effect of the action.
\[
\begin{array}{lll}
\phi_0(o) = \{ U \}     & \longrightarrow  & \{ W, A \} \; \{ \neg X \};\\
\phi_1(o) = \{ V, W \}  & \longrightarrow & \{ A \} \; \{ \neg X \};\\
\phi_2(o) = \{ W \}     & \longrightarrow & \{ U \} \; \{  \neg Y \}
\end{array}
\]

In this case, we need to intersect the sets $D_0(o) = \{ \neg X \}$
and $D_1(o) = \{ \neg X, \neg Y \}$, yielding $D(o) = \{ \neg X \}$.
This reflects the fact that, when achieving $A$ via the unconditional
effect of $o$, only $X$ gets removed from the state.

The fixpoint computation requires to adapt the computation of $\act^*$. First,
we repeat the same steps as in the case of simple STRIPS actions and
consider the unconditional negative effects and the intersection of the
preconditions with the {\sf False} set:
\[
\act^* := \act \setminus \{ o \mid A \in \eff_0^-(o) \vee \False^A_{DA}
                \cap pre_0(o) \neq \emptyset \} 
\]
Then, we additionally remove from each action the conditional effects
that either imply the deletion of $A$ or have an impossible effect
condition.
\[
\act^* := red(\act^*) = \{ red(o) | o \in \act^* \}
\]
Here, $red$ is a function $red(o): o \mapsto o'$ such that
\[
\Phi(o') = \Phi(o) \setminus \{ \phi_k(o) \mid A \in D_k(o) \vee
\pre_k(o) \cap \False^A_{DA} \neq \emptyset \}
\]

\noindent
Finally, we need to redefine Definition~\ref{def:pachievable}, which expresses
the conditions under which a fact is believed to be {\em possibly achievable}
given a certain set of operators $\act$.

\begin{def1}[Possibly Achievable Atoms for ADL]\label{def:pachievable-adl}
  An atom $p$ is possibly achievable given an action set $\act$
  (written $\pachievable(p,\act)$) if and only if
\[
\begin{array}{l}
\exists \; o \in \act, \; \phi_i \in \Phi(o): p \in \eff^+_i(o) \; \wedge\\
\hspace*{35mm} \forall \; p' \in (pre_i(o) \cup pre_0(o)): \; \exists
\; o' \in \act, \; \phi_{i'} \in \Phi(o'): p' \in \eff_{i'}^+(o')
\end{array}
\] 
holds, \ie there is a positive effect for $p$ and all of its conditions and
preconditions can be made true by other effects in the reduced action set.
\end{def1}

\noindent 
The process, which decides whether an atomic goal $B$ is heuristically
ordered before another goal $A$ (\ie whether $B \leq_h A$ holds)
proceeds in exactly the same way as described in
Section~\ref{ord-h-strips}: The {\sf False} set $\False^A_{DA}$ for
$A$ is reduced by the fixpoint computation, which remains unchanged,
but employs the updated routines for computing $\act^*$ and for
deciding $\pachievable(f,\act^*)$. As a result, $B$ is ordered before
$A$ ($B \leq_h A$) if and only if it is not possibly achievable
$\pachievable(B,\act^*)$ using the action set that results from the
fixpoint.



\section{The Use of Goal Orderings During Planning}
\label{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~\ref{related} 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 {\em goal agenda}. The planner, in our case \ipp, is then run
successively on the planning subproblems represented in the agenda.




\subsection{The Goal Agenda}

The first step one has to take for computing the goal agenda is to
perform a so-called {\em goal analysis}. During goal analysis, each pair $A, B
\in \G$ of atomic goals must be examined in order to find out whether
an ordering relation $A \leq B$, or $B \leq A$, or both, or none holds
between them. For the ordering relation $\leq$, an arbitrary
definition can be used. In our experiments, the relation $\leq$ was
always either $\leq_e$ or $\leq_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, \dots, G_n$ with
\[
\bigcup_{i=1}^{n} G_i = \G
\]
and
\[
G_i \cap G_j = \emptyset
\]
for $i \neq j, 1 \leq i,j \leq 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 
{\em goal graph} $\GG$.  
\[
\GG := (V,E)
\]
where
\[
V := \G
\]
and
\[
E := \{ (A,B) \in \G \times \G \mid A \leq B \}
\]
Now, the desired properties, which the sequence of goal sets should
possess, can be easily stated:

\begin{itemize}
\item Goals $A,B$ that lie on a cycle in $\GG$ belong to the same set, \ie
  $A,B \in G_i$.
\item If $\GG$ contains a path from a goal $A$ to a goal $B$, but not vice
  versa, then $A$ is ordered before $B$, \ie $A \in G_i$ and $B \in
G_j$ with $i <j $.   
\end{itemize}

\noindent
These are the only properties that appear to be reasonable for a
goal-set sequence respecting the atomic orderings. We will now
introduce a simple algorithmic method that does produce a sequence of
goal sets which meets these requirements.


First of all, the transitive closure of $\GG$ is computed. This can be
done in at most cubic time in the size of the goal
set~\cite{warshall62}. Then, for each node $A$ in the transitive
closure, the ingoing edges $A_{in}$ and outgoing edges $A_{out}$ are
counted. All disconnected nodes with $A_{in} = A_{out} = 0$ are moved
into a separate set of goals {\em G-sep} containing now those atomic
goals, which do not participate in a $\leq$ relation.  For all other nodes
$A$, their {\em degree} $d(A) = A_{in} - A_{out}$ is determined as the
difference between the number of ingoing edges and the number of
outgoing edges. Nodes with identical degree are merged into one set.
The sets are then ordered by increasing degree and yield our desired
sequence of goal sets. The only problem remaining is the set {\em
  G-sep}. If it is non-empty, it is not clear in which place to put
it.

Let us consider a small example of the
process. Figure~\ref{Bilder/trans-clos.eps} depicts on the left the
goal graph, which results from the goal set $\G = \{ A, B, C, D, E \}$
and the ordering relations $A \leq B, B \leq C$ and $B \leq D$, and
its transitive closure on the right.

\scalefig{0.8}{Bilder/trans-clos.eps}{On the left, the goal graph depicting
  the $\leq$ relations between the atomic subgoals.  On the right, the
  transitive closure of this graph.}


\noindent
In Figure~\ref{Bilder/degree.eps}, the number of in- and outgoing
edges of each goal, the corresponding degrees, and resulting goal-set
sequence are shown.

\scalefig{0.8}{Bilder/degree.eps}{On the left, the number of in- and outgoing
  edges for each node.  On the right, the degree of the nodes and the merged
  sets of goals having same degree. The node $E$ becomes a member of the {\em
    G-sep} set and remains unordered.}

\noindent
It is not difficult to verify that the resulting goal sequence 
respects the atomic goal orderings:

\begin{itemize}
\item Nodes occurring on a cycle in a graph have isomorphic in- and
  outgoing edges in the transitive closure of that graph. In
  particular, they have the same degree and get merged into the same
  set $G_i$.
\item Say we have a graph, where there is a path from $A$ to $B$, but not vice
  versa. Then, in the transitive closure of that graph, we will have an edge
  from $A$ to each node that $B$ has a path to, and additionally the edge from
  $A$ to $B$, \ie $A_{out} > B_{out}$ follows. Similarly, we have an ingoing
  edge to $B$ for each node that has a path to $A$, and additionally, the edge
  from $A$ to $B$, which gives us $B_{in} > A_{in}$. Altogether, $d(A) =
  A_{in} - A_{out} < B_{in} - A_{out} < B_{in} - B_{out} = d(B)$ and thus, the
  degree of $A$ is smaller than the degree of $B$ and as required, $A$
  gets ordered before $B$.
\end{itemize}

Note that nothing is said in this argumentation about the set of
unordered goals, {\em G-sep}. This set could, in principle, be
inserted anywhere in the sequence with the resulting sequence still
respecting the atomic orderings. A possible heuristic may use this
goal set as the first in the sequence, because apparently there is no
problem to reach all other goals after the goals in this set have been
achieved. Another heuristic could put this set at the end as there is
neither a problem to reach this goal set from all other goals. We have
decided to deal with the problem in a more sophisticated way by trying
to derive an ordering relation between {\em G-sep} and the other goal sets
$G_i$ that have already been derived. In order to do so, we need to
extend our definitions of goal orderings to {\em sets} of goals.


\subsection{Extension of Goal Orderings to Goal Sets}
\label{sets}

Given a set of atomic goals, it has always been a problem which of the
exponentially many subsets should be compared with each other in order to
derive a reasonable goal ordering between goal sets. A consideration of all
possible subsets is out of question, because it will result in an exponential
overhead. The partial goal agenda that we have obtained so far offers one
possible answer. It suggests taking the set {\em G-sep} and trying to order it
with respect to the goal sets emerging from the goal graph.

Given a planning problem $(\act,I,\G)$ and two subsets of atomic goals
$\{A_1,\dots,A_n\} \subseteq \G$ and $\{B_1,\dots,B_k\} \subseteq \G$,
the definition of $\leq_e$ and $\leq_h$ for sets of atomic goals is
straightforward. For the sake of simplicity, we consider only STRIPS
actions here. The definitions can be directly extended to ADL.

To define an ordering $\leq_E$, which extends $\leq_e$ to sets, 
we begin by defining a set $F^{\{A_1,\dots,A_n\}}_{GP}$ of
all atoms, which are exclusive of at least one atomic goal $A_i$ in
the planning graph generated for $(\act,I,\G)$:
\[ 
F^{\{A_1,\dots,A_n\}}_{GP} := \{ p \mid p \mbox{ is exclusive of at
least one $A_i$ when the graph has leveled off } \} 
\]

The set $\act_{\{A_1,\dots,A_n\}}$ is obtained accordingly by removing
from $\act$ all actions that delete at least one of the $A_i$, \ie
$\act_{\{A_1,\dots,A_n\}} = \{o \in \act \mid \forall \; i \in \{1,
\dots, n\}: \; A_i \not \in \del(o)\}$.

\begin{def1}[Ordering $\leq_E$ over Goal Sets]
  Let $(\act,I,\G)$ be a planning problem with $\{A_1, \dots, A_n\}
  \subseteq \G$ and $\{B_1, \dots, B_k\} \subseteq \G$. Let
  $\False^{\{A_1, \dots, A_n\}}_{GP}$ be the {\sf False} set for $
  \{A_1, \dots, A_n\}$.  The ordering $ \{B_1,\dots,B_k\} \leq_E \{A_1,
  \dots A_n\} $ holds if and only if
\[ 
\exists \; j \in \{1, \dots, k\}: \forall \; o \in \act_{\{A_1,\dots,A_n\}}:
B_j \in \add(o) \Rightarrow \pre(o) \cap \False^{\{A_1, \dots, A_n\}}_{GP} \neq
\emptyset.
\]
\end{def1}

\noindent
In a similar way, $\leq_h$ can be extended to $\leq_H$. For each $A_i$, the
sets $\False^{A_i}_{DA}$ are determined based on Equation~(\ref{false-DA}).
The set $\False^{\{A_1, \dots, A_n\}}_{DA}$ is simply the union over the
individual sets:
\begin{equation}\label{f-mengen}
  \False^{\{A_1, \dots, A_n\}}_{DA} := \bigcup_i \; \False^{A_i}_{DA}  
\end{equation}

\noindent
Then the fixpoint computation is entered with 
\begin{equation}\label{o-mengen}
\act^* := \act \setminus
\{ o \in \act \mid \exists \; i \in \{1, \dots, n\}: A_i \in \del(o) \vee \False^{\{A_1, \dots,
A_n\}}_{DA} \cap \pre(o) \neq \emptyset \}
\end{equation}

\noindent
The recomputation of $\act^*$ in each iteration of the fixpoint
algorithm from Figure~\ref{fixpoint-algo} is done accordingly.
Apart from this, the algorithm remains unchanged.


\begin{def1}[Ordering $\leq_H$]
  Let $(\act,I,\G)$ be a planning problem with $\{A_1, \dots, A_n\}
  \subseteq \G$ and $\{B_1, \dots, B_k\} \subseteq \G$. Let $\act^{*}$
  be the set of actions that is obtained by performing the fixpoint
  computation shown in Figure~\ref{fixpoint-algo}, modified to handle
  {\em sets} of facts as defined in Equations~(\ref{f-mengen})
  and~(\ref{o-mengen}). The ordering $\{B_1, \dots, B_k\} \leq_H
  \{A_1, \dots, A_n\}$ holds if and only if
\[
\exists \; j \in \{1, \dots, k\}: \neg \pachievable(B_j,\act^{*})
\]
\end{def1}

All given goal sets then undergo goal analysis, \ie each pair of sets
is checked for an ordering relation $\leq_E$ or $\leq_H$. Each derived
relation defines an edge in a graph with the subgoal sets as nodes.
The transitive closure is determined as before, and the degree of each
node is computed. If the graph contains no disconnected nodes, then a
total ordering over subsets of goals results by ordering the nodes
based on their degree. This ordering defines the goal agenda. In the
case of disconnected nodes, we default to the heuristic of adding the
corresponding goals to the last goal set in the agenda.
%the computation has failed in
%determining a goal ordering covering all atomic subgoals and the
%agenda {\em collapses} into just one entry containing the original
%unordered goal set $\G$.


\subsection{The Agenda-Driven Planning Algorithm}

Given a planning problem $(\act,\I,\G)$, let us assume that a goal
agenda $G_1, G_2, \dots, G_k$ with $k$ entries has been returned by
the analysis.  Each entry contains a subset $G_i \subseteq \G$. The
basic idea for the agenda-driven planning algorithm is now to first
feed the planner with the original initial state $\I_1 := \I$ and the
goals $\G_1 := G_1$, then execute the solution plan $\PP$ in $\I$,
yielding the new initial state $\I_2 = Result(\I_1,\PP)$. Then, a new
planning problem is initialized as $(\act,\I_2,\G_2)$. After solving
this problem, we want the goals in $G_2$ to be \true, but we also want
the goals in $\G_1$ to remain \true, so we set $\G_2 := \G_1 \cup
G_2$. The continuous merging of successive entries from the agenda
yields a sequence of incrementally growing goal sets for the planner,
namely
\[ 
\G_i := \bigcup_{j = 1}^i G_j 
\]
In a little more detail, the agenda-driven planning algorithm we
implemented for \ipp\ works as follows.  First, \ipp\ is called on the
problem $(\act,\I,\G_1)$ and returns the plan $\PP_1$, which achieves
the subgoal set $\G_1$. $\PP_1$ is a sequence of parallel sets of
actions, which is returned by \ipp\ similarly to \graphplan.  Given
this plan, the resulting state $R(\I,\PP_1) = \I_2$ is computed based
on the operational semantics of the planning actions.\footnote{See
\cite{jk-ecp97} for the exact definition of $R$, which we do not want to
repeat here.} In the case of a set of STRIPS actions, one simply adds
all ADD effects to and deletes all DEL effects from a state
description in order to obtain the resulting state, following the
 $Result$ function in Definition~\ref{strips-op}. For
STRIPS, the $Result$ function coincides directly with the $R$
function. In the case of a set of parallel ADL actions, one needs to
consider all possible linearizations of the parallel action set and
has to deal with the conditional effects separately. For each
linearization, a different resulting state can be obtained, but each
of them will satisfy the goals. To obtain the new initial state
$\I_2$, one takes the intersection of the resulting states for each
possible linearization of the actions in a parallel set. This means to
compute $n!$ linearizations for a parallel action set of $n$ actions
in each time step. Since $n$ is usually small (more than 5 or 6 ADL
actions per time step are very rare), the practical costs for this
computation are neglectible.

This way, given a solution to a subproblem $(\act,\I_i,\G_i)$, one calculates
the new initial state $\I_{i+1}$ and runs the planner on the subsequent
planning problem $(\act,\I_{i+1},\G_{i+1})$ until the planning problem
$(\act,\I_{k},\G_{k})$ is solved.

The plan solving the original planning problem $(\act,\I,\G)$ is
obtained by taking the sequence of subplans $\PP_1, \PP_2, \dots,
\PP_k$.  One could argue that planning for increasing goal sets can
lead to highly non-optimal plans.  But \ipp\ still uses the ``no-ops
first'' strategy to achieve goals, which was originally introduced in
the \graphplan\ system \cite{blum-aij}. Employing this strategy, the
\graphplan\ algorithm, in short, first tries to achieve goals by
simply keeping them \true, if possible. Since all goals $\G_1, \G_2,
\dots, \G_{i}$ are already satisfied in the initial state $\I_{i+1}$,
starting from which the planner tries to achieve $\G_{i+1}$, this
strategy ensures that these goals are only destroyed and
re-established if no solution can be found otherwise. The no-ops
first strategy is merely a \graphplan\ feature, but any reasonable
planning strategy should preserve goals that are already true in the
initial state whenever possible.

The soundness of the agenda-driven planning algorithm is obvious
because $\G_k = \G$ and we have a sequence of sound subplans yielding
a state transition from the initial state $\I$ to a state satisfying
$\G$.

The completeness of the approach is less obvious and holds only if the
planner cannot make wrong decisions before finally reaching the goals.
More precisely, the approach is complete on problems that do not
contain {\em deadlocks} as they were introduced in
Definition~\ref{deadlock}.

\begin{theorem}\label{theorem:completeness}
  Given a solvable planning problem $(\act,I,\G)$, and a goal agenda $\G_1,
  \G_2, \dots \G_k$ with $\G_i \subseteq \G_{i+1}$ and $\G_k = \G$. Running
  any complete planner in the agenda-driven manner described above will yield a
  solution if the problem is deadlock-free.
\end{theorem}

\begin{beweis}
  Let us assume the planner does not find a solution in step $i$ of
  the agenda-driven algorithm, \ie no solution is found for the
  subproblem $(\act,\I_i,\G_i)$. As the planner is assumed to be
  complete on each subproblem, this implies unsolvability of
  $(\act,\I_i,\G_i)$. If this problem is not solvable, then neither is
  the problem $(\act,\I_i,\G)$ solvable, since $\G_i \subseteq \G$
  holds. Therefore, the goals cannot be reached from $\I_i$.
  Furthermore, $\I_i$ is a reachable state---it was reached by
  executing the partial solution plans $\PP_1, \dots, \PP_{i-1}$ in
  the initial state. Consequently, $\I_i$ must be a deadlock state in
  the sense of Definition~\ref{deadlock}, which is a contradiction.
\end{beweis}

This result states the feasibility of our approach: As we have 
shown, most benchmark problems that are currently investigated do
contain inverse actions, are therefore invertible
(Theorem~\ref{theorem:inverse}), and are with that also deadlock-free
(Theorem~\ref{theorem:invertible-nodeadlocks}).  Thus, with
Theorem~\ref{theorem:completeness}, our approach preserves
completeness in these domains.

However in the general case, completeness cannot be guaranteed. The
following example illustrates a situation where the assumption
$s_{(A,\neg B)} \not \models p$ (assuming that preconditions of
achieving actions are not contained in the state where $A$ is reached,
cf.\ the derivation of the ordering $\leq_h$ in Section~\ref{method})
is wrong and yields a goal ordering under which no plan can be found
anymore although the problem is solvable.

Given the initial state $\{C,D\}$ and the goals $\{A,B\}$, the planner
has the following set of ground STRIPS actions :

\begin{description}\addtolength{\itemsep}{-3mm}
\item[{\bf op1}:] $\{C\} \longrightarrow \mbox{ ADD } \{B\} \mbox{ DEL } \{D\}$
\item[{\bf op2}:] $\{D\} \longrightarrow \mbox{ ADD } \{E\}$
\item[{\bf op3}:] $\{E\} \longrightarrow \mbox{ ADD } \{F\}$
\item[{\bf op4}:] $\{F\} \longrightarrow \mbox{ ADD } \{A\}$
\end{description}


The analysis will return an ordering $B \leq_h A$ because $B$ is only
added by {\bf op1}, but its precondition $C$ is not an effect of any
of the other actions. Thus it concludes that $C$ is not reachable from
a state in which $A$ holds. But in this example, $C$ holds in all
reachable states. The assumption $s_{(A,\neg B)} \not \models C$ as
made by the test $\pachievable(B,\act^*)$ is wrong. Thus, $B$ can be
reached after $A$. On the other hand, $A \leq_r B$ holds, we even have
a forced ordering $A \leq_f B$. But when testing for $A \leq_h B$,
this ordering remains undetected, because our method does not discover
that the precondition $F$ of {\bf op4} is not achievable from the
state in which $B$ holds: we obtain $\False^B_{DA} = \{ D \}$, which
excludes {\bf op2} from $\act^*$, but {\bf op3} and {\bf op4} remain
in the set of usable actions. Thus, {\bf op4} is considered a legal
achiever of $A$, and {\bf op3} is considered a legal achiever for its
precondition $F$. We could only detect the right ordering if we
regressed over the action chain {\bf op4}, {\bf op3}, {\bf op2} and
found out that, with $D$ being in the \False\ set of $B$, all these
actions must be excluded from $\act^*$.

Consequently, the goal agenda $\{ B \}, \{ A \}$ is fed into the
planner, which solves the first subproblem using {\bf op1}, but then
fails in achieving $A$ from the state $\{ B, C \}$ since there is no
inverse action to {\bf op1} and $D$ cannot be re-established in any
other way.

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% TeX-master: t
%%% TeX-master: t
%%% TeX-master: t
%%% TeX-master: t
%%% TeX-master: t
%%% TeX-master: t
%%% End: 




\section{Empirical Results} \label{empirical}

We implemented both methods to approximate $\leq_r$ as a so-called
Goal Agenda Manager (GAM) for the \ipp\ planning system
\cite{jk-ecp97}. GAM is activated after the set of ground actions has
been determined and either uses $\leq_e$ or $\leq_h$ to approximate
the reasonable goal ordering. Then it calls the \ipp\ planning
algorithm on each entry from the goal agenda and outputs the solution
plan as the concatenation of the solution plans that have been found
for each entry in the agenda.\footnote{The source code of GAM, which
is based on \ipp\ 3.3, and the collection of domains from which we draw
the subsequent examples can be downloaded from
http://www.informatik.uni-freiburg.de/{\~\ }koehler/ipp/gam.html. All
experiments have been performed on a SPARC 1/170.}

\newpage

The empirical evaluation that we performed uses the \ipp\ domain
collection, which contains 48 domains with more than 500 planning
problems. Out of these domains, we were able to derive goal ordering
information in 10 domains. These domains indeed pose constraints on
the ordering in which a planner has to a achieve a set of goals. In
all other domains, where no goal orderings could be derived, we found
that either only a single goal has to be achieved, for example in the
{\em manhattan}, {\em movie}, {\em molgen}, and {\em montlake} domains
or the goals can be achieved in any order, as for example in the {\em
  logistics}, {\em gripper}, and {\em ferry} domains. We found no
benchmark domain, in which a natural goal ordering existed, but our
method failed to detect it. As a matter of fact, looking at a goal
ordering that seems to be natural, one usually finds that the ordering
is reasonable in the sense of Definition~\ref{r-ord}, see for example
the {\em blocks world}, {\em woodshop}, and {\em tyreworld} domains. Our
method finds almost all of the reasonable orderings, which indicates
that both approximation techniques $\leq_e$ and $\leq_h$ are
appropriate for detecting ordering information.

\bigskip

In the following, we will first compare the $\leq_e$ and $\leq_h$
techniques in terms of runtime and number of goal agenda entries
generated. Then we take a closer look at the agendas that are
generated in selected domains and investigate how they influence the
performance of the \ipp\ planning system. The exact definition of all
domains can be downloaded from the \ipp\ webpage, we just give the
name of the domain and the name of the particular planning problem as
well as the number of (ground) actions a domain contains, because this
parameter nicely characterizes the size of a domain and with that
usually the difficulty to handle it.

\bigskip

In all examples, the times shown to compute the goal agenda contain
the effort to parse and instantiate the operators, \ie to compute the
set of actions. Times for parsing and instantiation are not listed
explicitly, because they are, on the test examples used here, usually
very close to zero and do not influence the performance of the planner
in a significant way.

\bigskip

\subsection{Comparison of $\leq_h$ and $\leq_e$}

We begin our comparison with a summary of results that we obtained in
different representational variants of the {\em blocks world}. The
{\em bw\_large\_a} to {\em bw\_large\_d} examples originate from the
SATPLAN test suite \cite{kautz96} to which we added the larger
examples {\em bw\_large\_e} to {\em bw\_large\_g}. The {\em parcplan}
example comes from \cite{parcplan} and uses multiple grippers and
limited space on the table. The {\em stack\_n} examples use the
\graphplan\ {\em blocks world} representation and simply require to
stack $n$ blocks on each other, which are all on the table in the
initial state.

\bigskip

The two methods return exactly the same ordering relations across all
{\em blocks world} problems. But as Figure~\ref{vergleich1} confirms,
the computation of $\leq_e$ based on planning graphs is much more
time-consuming. It hits the computational border when a domain
contains more than 10000 actions. The computation of $\leq_h$ is much
faster and also scales to larger action sets.

\newpage 

\begin{figure}[htb]
\begin{center}
\begin{tabular}{|l|l|r|r|r|} \hline
problem & \#actions & \#agenda entries&  CPU($\leq_e$)
& CPU($\leq_h$)\\\hline \hline
bw\_large\_a & 162   & 1   &   0.69 & 0.07 \\
bw\_large\_b & 242   & 5   &   1.45 & 0.11 \\
bw\_large\_c & 450   & 7   &   4.85 & 0.22 \\
bw\_large\_d & 722   & 11  &  14.18 & 0.35 \\
bw\_large\_e & 722   & 11  &  12.95 & 0.35 \\
bw\_large\_f & 1250  & 6   &  44.93 & 0.58 \\
bw\_large\_g & 1800  & 9   &  97.11 & 0.88 \\ \hline
parcplan     & 1960  & 4   &  25.84 & 1.47 \\\hline
stack\_20      & 800   & 19  &   6.91 & 0.36 \\
stack\_40      & 3200  & 39  & 160.00 & 1.74\\
stack\_60      & 7200  & 59  & 840.42 & 4.85 \\
stack\_80      & 12800 & 79  & -      & 11.38 \\ \hline
\end{tabular}
\end{center}
\caption{\label{vergleich1} Comparison of $\leq_e$ and $\leq_h$ on
  {\em blocks world} problems. \#actions shows the number of actions in the
  set  $\act$, from which the planner tries to construct a
  plan. \#agenda entries says how many goal subsets have been detected
  and ordered by GAM. Column 4 and~5 display the CPU time that is
  required by both methods to compute the agenda when provided with
  the set $\act$. A dash will always mean that \ipp\ ran out of memory
on a 1 Gbyte machine.}
\end{figure}


 
Figure~\ref{vergleich2} and Figure~\ref{vergleich3} show the results
for the other domains, in which our method is able to detect
reasonable orderings. Figure~\ref{vergleich2} lists the domains, in
which both methods return the same goal agendas. The {\em tyreworld},
{\em hanoi}, and {\em fridgeworld} domains originate from UCPOP
\cite{ucpop}, while the {\em link-repeat} domain can be found in
\cite{veloso94}. The performance results coincide with those shown in
Figure~\ref{vergleich1}. Figure~\ref{vergleich3} shows the same
picture in terms of runtime performance, but in these domains
different agendas are returned by $\leq_e$ and $\leq_h$.

The {\em woodshop} and {\em scheduling} domains contain actions with
conditional effects, while the other domains only use STRIPS
operators. The computation of $\leq_e$ fails to derive goal orderings
for all {\em scheduling world} problems (of which we only display the
largest problem {\em sched6}) and for the {\em wood1} problem. The
explanation for this behavior can be found in the different treatment
of conditional effects by both methods. \ipp\ does only find a very
limited form of {\em mutex} relations between conditional effects when
building the planning graph. A goal, which is achieved with a
conditional effect, will not very often be exclusive to a large number
of other facts in the graph.  Thus, the \False\ sets are very small or
sometimes even empty and consequently, only very few actions can be
excluded when performing the reachability analysis and thus, reasonable
orderings may remain undetected. Direct analysis investigates the
conditional effects in more detail and is therefore able to derive
much larger \False\ sets.


\begin{figure}[htb]
\begin{center}
\begin{tabular}{|l|l|l|r|r|r|} \hline
domain & problem & \#actions & \#agenda entries&  CPU($\leq_e$)
& CPU($\leq_h$)\\\hline\hline
tyreworld   & fixit1  &  26 & 6 &  0.05  & 0.01 \\
            & fixit2  &  59 & 6 &  0.20  & 0.03  \\
            & fixit3  & 108 & 6 &  0.45  & 0.06 \\
            & fixit4  & 173 & 6 &  0.84  & 0.10 \\
            & fixit5  & 254 & 6 &  1.56  & 0.15 \\
            & fixit10 & 899 & 6 & 16.29  & 0.64 \\ \hline
hanoi       & hanoi3  &  48 & 3 &  0.05  & 0.02 \\
            & hanoi4  &  90 & 4 &  0.10  & 0.04 \\
            & hanoi5  & 150 & 5 &  0.19  & 0.08 \\
            & hanoi6  & 231 & 6 &  0.35  & 0.12 \\
            & hanoi7  & 336 & 7 &  0.63  & 0.19 \\ \hline
fridgeworld & fridge & 779 & 2   & 0.77 & 0.55 \\\hline
link-repeat & link10  &  31 & 2   & 0.19 & 0.01\\
            & link30  &  31 & 2   & 0.21 & 0.01\\\hline
\end{tabular}
\end{center}
\caption{\label{vergleich2} Comparison of $\leq_e$ and $\leq_h$ on
  those benchmark domains, in which they return identical agendas.}
\end{figure}



\begin{figure}[htb]
\begin{center}
\begin{tabular}{|l|l|l|r|r|r|} \hline
domain & problem & \#actions & \#agenda entries&  CPU($\leq_e$)
& CPU($\leq_h$)\\\hline\hline
bulldozer   & bull    &  61 & 2/1 & 0.09 & 0.03 \\\hline
glassworld  & glass1  &  26 & 2/1   & 0.02 & 0.01\\
            & glass2  & 114 & 2/1   & 0.19 & 0.09\\
            & glass3  & 122 & 2/1   & 0.22 &0.09\\\hline
shoppingworld    & shop  &  81 &  2/1  & 0.07 & 0.02 \\  \hline
scheduling & sched6 & 104 & 1/4 & 01.0 & 0.12\\\hline
woodshop         & wood1 & 15  & 1/3 & 0.03 & 0.01\\
                 & wood2 & 15  & 6/5 & 0.03 & 0.01\\
                 & wood3 & 43  & 6/5 & 0.14 & 0.06\\ \hline
\end{tabular}
\end{center}
\caption{\label{vergleich3} Domains in which $\leq_e$ and $\leq_h$
  return different goal agendas, which we give in the form
  $n_1/n_2$. The number before the slash says how 
  many entries are contained in the agenda computed by $\leq_e$, the
  number following the slash says how many entries are contained in
the agenda computed by $\leq_h$. \#agenda entries=1 means that the 
  agenda contains only a single entry, namely the original goal set,
  and no ordering was derived.}
\end{figure}




The behavior of the $\leq_h$ method in the STRIPS domains {\em
  bulldozer}, {\em glassworld}, and {\em shopping world} is caused by
the same phenomenon. In these domains, one can derive much larger
\False\ sets using planning graphs and in turn these sets exclude more
actions.  Since direct analysis finds smaller or empty \False\ sets,
it also finds less $\leq_h$ relations.  The {\em woodshop} domain
shows that the results can differ within the same domain, but
depending on the specific planning problem. The problem {\em wood2}
varies from the problem {\em wood1} in the sense that one goal is
slightly different---an object needs to be put into a different
shape---and that two more goals are present. While there are no goal
orderings derived between pairs of the old goals from {\em wood1},
lots of $\leq_e$ relations are derived between mixed pairs of old and
new goals in {\em wood2}, yielding a detailed goal agenda. The problem
{\em wood3} contains additional objects and many more goals, which can
also be successfully ordered.


In the subsequent experiments, we decided to solely use the heuristic
ordering $\leq_h$ because the computation of $\leq_h$ is less costly
than the computation of $\leq_e$ in all cases, yielding comparable
agendas in most cases. In the three domains that we investigate more
closely, namely the {\em blocks world}, {\em tyreworld} and {\em hanoi}
domains, the agendas derived by both methods are, in fact, exactly the
same.


\subsection{Influence of Goal Orderings on the Performance of \ipp\
  and Interaction with RIFO}


In this section, we analyze the influence of the goal agenda on the
performance of \ipp\ and combine it with another domain analysis
method, called RIFO \cite{bn-ecp97}. RIFO is a family of heuristics
that enables \ipp\ to exclude irrelevant actions and initial facts
from a planning problem. It can be very effectively combined with GAM,
because if \ipp\ plans for only a subset of goals from
the original goal set, it is very likely that also only a subset of
the relevant actions is needed to find a plan. More precisely, we
obtain one subproblem for each entry in the agenda, and, for each such
subproblem, we use RIFO for preprocessing before planning with \ipp. In
this configuration, GAM reduces the search space for \ipp\ by
decreasing the number of subgoals the planner has to achieve at each
moment, while RIFO reduces the search space dramatically by selecting
only those actions that are relevant for this goal subset.

\subsubsection{The Blocks World}

Figure~\ref{Bilder/parcplan-bw.eps} illustrates the {\em parcplan}
problem \cite{parcplan} in detail.  Seven robot arms can be used to
order 10 blocks into 3 stacks on 5 possible positions on the table.


\scalefig{0.4}{Bilder/parcplan-bw.eps}{The {\em parcplan} problem with limited
space on the table, seven robot arms, and several stacks.} 

\noindent
The goal agenda derived by \ipp\ orders the blocks into horizontal
layers:

{\sl 
\begin{itemize}\addtolength{\itemsep}{-3mm}
\item[1:] on-table(21, t2) $\wedge$ on-table(11, t1)
\item[2:] on-table(31, t3) $\wedge$ on(22, 21) $\wedge$ on(12, 11)
\item[3:] on(32, 31) $\wedge$ on(13, 12) $\wedge$ on(23, 22)
\item[4:] on(14, 13) $\wedge$ on(24, 23)
\end{itemize}
}


The optimal plan of 20 actions solving the problem is found by \ipp\ 
using GAM in 14~s, where it spends one second on computing the goal
agenda, almost 13 seconds to build the planning graphs, but only 0.01
second to search for a plan. Only 70 actions have to be tried to find
the solution. Without the goal analysis, \ipp\ needs approx.\ 47~s and
searches 52893 actions in more than 26 seconds.

RIFO \cite{bn-ecp97} fails in detecting a subset of relevant actions
when the original goal set has to be considered, but it succeeds in
selecting relevant actions for the subproblems stated in the agenda.
It reduces runtime down to less than 8~s with 1~s again spent on the
goal agenda, almost 6~s spent on the removal of irrelevant actions and
initial facts, less than 1~s spent on building the planning graphs.
As previously, almost no time is spent on planning.

Figure~\ref{sat-ex} shows \ipp\ on the SATPLAN {\em blocks world}
examples from \cite{kautz96}, the {\em bw\_large.e} example taken from
\cite{yd-ecp97}, and two very large examples {\em bw\_large.f}
(containing 25 blocks and requiring to build 6 stacks in the goal
state) and {\em bw\_large.g} with 30 blocks/8 stacks.



\begin{figure}[htb]
\begin{center}
\begin{tabular}{|l|l|c|r|r|r|r|}\hline
SATPLAN & \# actions & plan length & \ipp & +G     & +G+R    &
+G+R+L\\ \hline  \hline
bw\_large.a  & 162  & 12 (12)& 0.70    & 0.74   & 0.58    & 0.34 \\
bw\_large.b  & 242  & 22 (18)&  26.71  & 0.86   &  0.55   & 0.52 \\
bw\_large.c  & 450  & 48    &  -      & 7.34   &  2.42   & 2.58\\
bw\_large.d  & 722  & 54    &  -      & 11.62  &  3.74   & 3.81\\
bw\_large.e  & 722  & 52    &  -      & 11.14  &  3.99   & 3.97\\ 
bw\_large.f  & 1250 & 90    &   -     &  -     &   -     & 16.01 \\
bw\_large.g  & 1800 & 84    &  -      & -      & 117.56 & 28.71 \\\hline
\end{tabular}
\end{center}
\caption{\label{sat-ex} Performance on the extended SATPLAN {\em
    blocks world} test suite. The second column shows the number of
  ground actions in this domain, the third column shows the plan
  length, \ie the number of actions contained in the plan, generated
  by GAM and in parentheses the plan length generated by \ipp\ without
  GAM given that \ipp\ without GAM is able to solve the corresponding
  problem.  +G means that \ipp\ is using GAM, +G+R means \ipp\ uses
  GAM and RIFO, +G+R+L means that subgoals from the same set in the
  agenda are arbitrarily linearized. All runtimes cover the whole
  planning process starting with parsing the operator and domain file,
  performing the GAM and RIFO analysis (if active), and then searching
  the graph until a plan is found.}
\end{figure}

\ipp\ 3.3 without GAM can only solve the {\em bw\_large.a} and {\em
  bw\_large.b} problems. Using a goal agenda, some plans become
slightly longer, but performance is increasing dramatically.  Plan
length is growing because blocks are accidentally put in
positions where they cut off goals that are still ahead in the agenda
and thus, additional actions need to be added to the plan to remove
these blocks from wrong positions. A further speed-up is possible when RIFO
is additionally used, because it reduces the size of planning graphs
dramatically. Finally, goals that belong to the same subset in the
agenda can be linearized based on the heuristic assumption that if the
analysis found no reasonable goal orderings, then the goals are
achievable in any order. With this option, the problems are solved
almost instantly.

The reader may wonder at this point why we use linearization of agenda
entries only as an extra option and do not investigate it further.
There are two reasons for that. First, linearization does have
negative side effects in most domains that we investigated. For
example, it yields much longer plans in the {\em logistics} domain and
all its variants. When linearizing the single entry that the agenda
for a {\em logistics} problem contains, all packages get transported
to their goal position one by one. Of course, this takes much more
planning steps than simultaneously transporting packages with
coinciding destinations.

Secondly, the effects of linearization are somewhat unpredictible,
even in domains where it usually tends to yield good results. This is
because GAM does not recognise {\em all} interactions between goals.
Consider a {\em blocks world} problem with four blocks $A$, $B$, $C$
and $D$. Say $B$ is positioned on $C$ initially, the other blocks
being each on the table, and the goal is to have $on(A,B)$ and
$on(C,D)$. The agenda for this problem will comprise a single entry
containing both goals. In fact, there is no reasonable goal ordering
here. Nevertheless, stacking $A$ onto $B$ immedeatly is a bad idea, as
the planner needs to move $C$ to achieve $on(C,D)$. Being not aware of this,
GAM might linearize the single agenda entry to have $on(A,B)$ up
front, which makes the problem harder than it actually is.  Thus, the
runtime advantages that linearization sometimes yields on the {\em
  blocks world} can be more or less seen as cases of ``good luck''.


Figure~\ref{Bilder/bw.eps} shows \ipp\ on the {\em stack\_n} problems.
\ipp\ without any domain analysis can handle up to 12 blocks in less
than 5 minutes, but for 13 blocks more than 15 minutes are needed.
Using GAM, 40 blocks can be stacked in less than 5 minutes. Using GAM
and RIFO, the 5 minutes limit is extended to 80 blocks, while {\em
  stack100} is solved in 11.5~min where 11.3~min are spent for both
analysis methods and only 0.2~min are needed for building the planning
graphs and extracting a plan.

\scalefig{0.4}{Bilder/bw.eps}{\ipp\ 3.3 on a simple, but huge stacking
problem.} 


Figure~\ref{xx} shows the sharing of the overall problem-solving time
between GAM, RIFO and the \ipp\ search algorithm on {\em blocks world}
problems. Similar results are obtained in the {\em tyreworld}. GAM
takes between 3 and 16 \%, RIFO takes between 75 and 96 \%, and the
search effort is reduced down to approx.\ 1 \%. The overall problem
solving time is clearly determined by RIFO, while the search effort
becomes a marginal factor in the determination of performance. This
indicates that a further speed-up is possible when improving the
performance of GAM and RIFO. It also indicates that even the hardest
planning problems can become easy if they are structured and
decomposed in the right way.


\begin{figure}[htb]
\begin{center}
\begin{tabular}{|l|l|l|r|l|} \hline
problem  & \# actions & GAM    & \multicolumn{1}{c|}{RIFO}  
&  \multicolumn{1}{c|}{search algorithm}\\ \hline \hline
stack\_20 &  800   & 0.31 = 16 \%    & 1.44   = 75 \% & 0.13 = 7 \%\\
stack\_40 & 3200   & 1.57 = 7 \%     & 18.77  = 90 \% & 0.51 = 2 \%\\
stack\_60 & 7200   & 4.40 = 4 \%     & 93.10  = 94 \% & 1.15 = 1 \%\\
stack\_80 & 12800  & 9.60 = 3 \%     & 283.60 = 96 \% & 2.33 = 1 \%\\
parcplan & 1960   & 0.86 = 12 \%    & 5.52   = 76 \% & 0.83 = 11 \%\\ \hline
\end{tabular}
\end{center}
\caption{\label{xx} Distribution of problem-solving time on {\em blocks world}
examples between GAM, RIFO, and the search algorithm, which 
comprises the time to build and search the planning graph. 
The remaining fraction of total problem-solving time, which is not
shown in the table,  is spent on parsing and instantiating the operators.} 
\end{figure}



%%% fuer easy100
%%ipp: spent 0.00 seconds instantiating
%%gam: spent 850.77 seconds computing goal agenda
%%gam: spent 3.15 seconds determining new initial facts
%%ifo: spent 678.39 seconds removing irrelevants

%%ipp: spent 17.57 seconds building graphs
%%ipp: spent 0.51 seconds searching for plans
%%ipp: used 1550.39 seconds total time

%%neue easy100 ergebnisse
%%ipp: spent 0.00 seconds instantiating
%%gam: spent 14.11 seconds computing goal agenda
%%gam: spent 3.97 seconds determining new initial facts
%%ifo: spent 663.98 seconds removing irrelevants
%%ipp: spent 3.35 seconds building graphs
%%ipp: spent 0.28 seconds searching for plans

%%ipp: used 685.69 seconds total time

%%% ERGEBNISTABELLE SIEHE ORDNER

\subsubsection{The Tyreworld}

The tyreworld problem, originally formulated by Stuart Russell,
asks a planner to find out how to replace a flat tire. It is
easily solved by \ipp\ within a few milliseconds. The problem
becomes much harder if the number of flat tires is increasing, cf.\ 
Figure~\ref{tyre-ex}. 

\begin{figure}[htb]
\begin{center}
\begin{tabular}{|c|l|c|c|c|r|}\hline
Tires & \# actions & \ipp     &  +G+R   & +G+R+L &  Search Space   \\ \hline \hline
1     & 26    &  0.10 (12/19) & 0.15 (14/19) & 0.16  (17/19)  & 1298/88 \\
2     & 59    & 17.47 (18/30) & 0.41 (24/32) & 0.32  (30/34)  & 1290182/210 \\
3     & 108   &      -        & 2.87 (32/44) & 0.63  (41/46)  & -/366\\
4     & 173   &      -        &      -       & 1.12  (52/60)  & -/565 \\ 
5     & 254   &      -        &      -       & 1.93  (63/73)  & -/807 \\
6     & 353   &      -        &      -       & 3.42  (73/85)  & -/1092\\
7     & 464   &      -        &      -       & 4.81  (84/98)  & -/1420 \\
8     & 593   &      -        &      -       &  8.07 (95/121) & -/1791\\
9     & 738   &      -        &      -       & 11.27 (106/124) &-/ 2205 \\ 
10    & 899   &      -        &      -       & 16.89 (118/136) & -/2662\\\hline
\end{tabular}
\end{center}
\caption{\label{tyre-ex} \ipp\ in the Tyreworld. The numbers in parentheses
show the time steps, followed by the number of actions in the
generated plan. The last column compares the search spaces. The 
number before the slash shows the ``number of actions tried''
parameter for the plain  \ipp\ planning algorithm, while the number
following the slash shows the  ``number of actions tried'' for \ipp\
using GAM, RIFO, and the linearization of entries in the agenda. A dash
means that the ``number of actions tried'' is unknown because \ipp\ failed
in solving the corresponding planning problem.}
\end{figure}

\ipp\ is only able to solve the problem for 1 and 2 tires. Using GAM
and RIFO, 3 tires can be handled. Solution length under GAM is
slightly increasing, which is caused by superfluous {\em jack-up} and
{\em jack-down} actions. In short, this is explained as follows. Each
wheel needs to be mounted on its hub, which is expressed by an {\em
  on(?r, ?h)} goal. To mount a wheel, its hub must be jacked up. After
mounting, the nuts are done up. Then, the hub needs to be jacked down
again, in order to tighten the nuts achieving a {\em tight(?n, ?h)}
goal.  Now, GAM puts all of the $on$ goals into one entry preceeding
the {\em tight} goals. Thus, solving the entry containing the $on$
goals, each hub is jacked up, the wheel is put on, and the hub is
immediatly jacked down again in order to replace the next wheel.
Afterwards, solving the {\em tight} goals, each hub must be jacked
up---and down---one more time for doing up the nuts. Solving the
problem in this manner, the planner inserts one superfluous {\em
  jack-up}, and one superfluous {\em jack-down} action for each wheel.
More precisely, superfluous actions are inserted for all but one
wheel, namely the wheel that is last mounted when solving the $on$
goals. After mounting this wheel, all {\em on} goals are achieved, and
the planner proceeds to the next agenda entry with this wheel still
being jacked up. Then, trying to achieve the {\em tight} goals, \ipp\ 
recognizes that the shortest plan (in terms of the number of parallel
steps) results when the nuts are first done up on the hub that is
already jacked up. Thus, this hub is only jacked up {\em one} time,
achieving the corresponding {\em on} goal, and jacked down again one
time, before achieving its {\em tight} goal.

\noindent
In the case of 3 tires, the following goal subsets are
identified and ordered:

%%Ipp: spent 0.00 seconds instantiating
%%gam: spent 0.55 seconds computing goal agenda
%%gam: spent 0.10 seconds determining new initial facts
%%ifo: spent 14.42 seconds removing irrelevants

%%ipp: spent 1.74 seconds building graphs
%%ipp: spent 0.08 seconds searching for plans

%%ipp: used 16.89 seconds total time


{\sl
\begin{itemize}\addtolength{\itemsep}{-3mm}
\item[1:] inflated(r3), inflated(r2), inflated(r1)
\item[2:] on(r3, hub3),  on(r1, hub1), on(r2, hub2)
\item[3:] tight(n2, hub2), tight(n3, hub3), tight(n1, hub1)
\item[4:] in(w3, boot), in(pump, boot), in(w1, boot), in(w2, boot)
\item[5:] in(jack, boot)
\item[6:] in(wrench, boot)
\item[7:] closed(boot)
\end{itemize}
}

The hardest subproblem in the agenda is to achieve the $on(r_i,hub_i)$
goals in entry 2, \ie to mount inflated spare wheels on the various
hubs. Trying to generate a maximum parallelized plan is impossible for
\ipp\ for more than 3 tires. But since the goals are completely
independent of each other, any linearization of them will perfectly
work. The resulting plans become slightly longer due to the way that
the {\em tight} goals are achieved when using the -L option. We
noticed earlier that for one wheel (the one that is last mounted when
solving the {\em on} goals) no superfluous {\em jack-up} and {\em
  jack-down} actions need to be inserted into the plan. Linearizing
the agenda entries, superfluous {\em jack-up} and {\em jack-down}
actions must most likely be inserted for {\em all} wheels, yielding
plans that are two steps longer. The reason for that is that any
$tight$ goal might be the first in the linearization. Most likely,
this is not the {\em tight} goal corresponding to the hub that is
still jacked up, so the planner needs to insert one superfluous {\em
  jack-down} action here. Later, it must jack up this hub again,
yielding another superfluous action. Using +G+R+L in the case of 10
tires, only 2662 actions need to be tried until a plan of 136 actions
is found, which takes 0.08~s. GAM requires 0.55~s, RIFO requires
14.42~s, 1.74~s are consumed to generate the planning graphs, and
0.08~s are spent to compute the initial states for all subproblems.
The remaining 0.02~s are consumed for parsing and instantiating.



\subsubsection{The Tower of Hanoi}

A surprising result is obtained in the {\em tower of hanoi} domain. In
this domain, a stack of discs has to be moved from one peg to a third
peg with an auxiliary second peg between them, but never a larger disc
can be put onto a smaller disc. In the case of three discs $d1$, $d2$,
$d3$ of increasing size, the goals are stated as {\em on(d3,peg3),
  on(d2,d3), on(d1,d2)}. GAM returns the following agenda, which
correctly reflects the ordering that the largest disc needs to be put
in its goal position first.

{\sl 
\begin{itemize}\addtolength{\itemsep}{-3mm}
\item[1:] on(d3,peg3)
\item[2:]  on(d2,d3)
\item[3:]  on(d1,d2)
\end{itemize}
}

The goal agenda leads to a partition into subproblems that corresponds
to the recursive formulation of the problem solving algorithm, \ie to
solve the problem for $n$ discs, the planner first has to solve the
problem for $n-1$ discs, etc.  For the first entry, a plan of 4
actions (time steps 0 to 3 below) is generated, which achieves the
goal {\em on(d3,peg3)}.\footnote{A {\em move} action takes as first
  argument the disc to be moved, as second the disc from which it is
  moved, and as third argument the disc or peg to which it is
  moved.} Then a plan of 2 actions (time steps 4 and 5) achieves the
goals {\em on(d3,peg3)} and {\em on(d2,d3)} with {\em on(d3,peg3)}
holding already in the initial state.  Finally, a one-step plan (time
step 6) is generated that moves the third disc with the other two
discs being already in the goal position.

\bigskip

\begin{minipage}{8cm}
\begin{verbatim}
time step 0:  move(d1,d2,peg3)
time step 1:  move(d2,d3,peg2)
time step 2:  move(d1,peg3,d2)
time step 3:  move(d3,peg1,peg3)
\end{verbatim}
\end{minipage}
\begin{minipage}{8cm}
\begin{verbatim}
time step 4:  move(d1,d2,peg1)
time step 5:  move(d2,peg2,d3)
time step 6:  move(d1,peg1,d2)
\end{verbatim}
\end{minipage}

\bigskip

Surprisingly, \ipp\ is not able to benefit from this information, but
runtime of \ipp\ using GAM is exploding dramatically for increasing
numbers of discs, see Figure~\ref{hanoi-problems}. 
\begin{figure}[htb]
\begin{center}
\begin{tabular}{|c|r|r|r|r|r|} \hline
discs &  \#actions   &  \ipp\  & \ipp\ +G & UCPOP  & UCPOP on
subproblems\\ \hline \hline
2     & 21  & 0.02   & 0.02  & 0.12 (27) & 0.06 (17) + 0.02 (6) \\
3     & 48  & 0.08   & 0.07  & 8.00 (2291) & 0.18 (48) + 0.06 (13) +
0.01 (6) \\
4     & 90  & 0.33   & 0.25  & - & -\\
5     & 150 & 1.57   & 3.10 & - & - \\
6     & 231 & 9.71   & 88.45 & - & -\\
7     & 336 & 69.44  & 2339.94 & - & -\\ \hline
\end{tabular}
\end{center}
\caption{\label{hanoi-problems} Runtimes of \ipp\ with and without
  the goal agenda on {\em hanoi} problems compared to UCPOP without
  agenda and UCPOP on the agenda subproblems using ZLIFO and the {\em ibf}
control strategy.}
\end{figure}


 We are not able to provide an explanation for this phenomenon, but
the division into subproblems causes a much larger search space for
the planner although the same solution plans result.  RIFO cannot
improve on the situation because it selects all actions as relevant.

The {\em tower of hanoi} domain is the only one we found where \ipp's
performance is deteriorated by GAM. We do currently not see a way of how
one can tell in advance whether \ipp\ will gain an advantage from
using GAM or not. The overhead caused by the goal analysis itself is
very small, but an ``inadequate'' split of the goals into subgoal sets
can lead to more search, see also Section~\ref{related}.

However in this case, the phenomenon seems to be specific to \ipp. We
simulated the information that is provided by GAM in UCPOP and
obtained a quite different picture. The fifth column in
Figure~\ref{hanoi-problems} shows the runtime of UCPOP using ZLIFO
\cite{pollack} and the {\em ibf} control strategy with the number of
explored partial plans in parentheses. UCPOP can only solve the
problem for 2 and 3 discs. In the last column of the figure, we show
the runtime and number of explored partial plans, which result when
UCPOP is run on the subproblems that result from the agenda. These are
exactly the same subproblems which \ipp\ has to solve, but the
performance of UCPOP improves significantly. Instead of taking 8~s and
exploring 2291 partial plans, UCPOP only takes 0.18+0.06+0.01=0.25~s
and explores only 48+13+6=67 plans.  Unfortunately, any problems or
subproblems with more than 3 discs remain beyond the performance of
UCPOP. The performance improvement is independent of the search
strategies used by UCPOP. For example, if {\em ibf} control is used
without ZLIFO, the number of explored partial plans is reduced from
78606 down to 2209 in the case of the problem with 3 discs. Runtime
improves from 65 seconds down to 2 seconds.  Similarly, when using
{\em bf} control without ZLIFO the number of explored partial plans
reduces from 1554 down to 873.

Knoblock \citeyear{knoblock94} also reports an improvement in performance
for the Prodigy planner \cite{prodigy} when it is using the
abstraction hierarchy generated for this domain by the {\sc alpine}
module, which provides in essence the same information as the goal
agenda.\footnote{However, to find that goal ordering information, {\sc
    alpine} requires to represent the tower of hanoi domain involving
  several operators, cf.~\cite{knoblock-phd}.}



%%hanoi7 mit gam
%%ipp: number of actions tried: 84783510
%%ipp: had 19868735 simple memoizing hits
%%ipp  had  641364 partial memoizing hits
%%ipp: had  917612 subset memoizing hits
%%ipp: spent 0.00 seconds instantiating
%%gam: spent 0.16 seconds computing goal agenda
%%gam: spent 0.03 seconds determining new initial facts

%%ipp: spent 0.67 seconds building graphs
%%ipp: spent 2339.08 seconds searching for plans

%%ipp: used 2339.94 seconds total time

\begin{comment}

 H2



Created 46 plans, but explored only 27

      CPU time:    0.1200 sec

      Branching factor:  0.000

      Working Unifies: 816 

      Bindings Added: 78  





h2a

Stats: Initial terms = 14;   Goals = 3 ;  Success (2 steps)

      Created 30 plans, but explored only 17

      CPU time:    0.0700 sec

      Branching factor:  0.000

      Working Unifies: 476 

      Bindings Added: 59  



h2b

      Created 10 plans, but explored only 6

      CPU time:    0.0200 sec

      Branching factor:  0.000

      Working Unifies: 115 

      Bindings Added: 19  





h3

    Created 3306 plans, but explored only 2291

      CPU time:    8.0000 sec





      Branching factor:  0.000

      Working Unifies: 68237

      Bindings Added: 3466



h3a

   Created 83 plans, but explored only 48

      CPU time:    0.1800 sec

      Branching factor:  0.000

      Working Unifies: 1523

      Bindings Added: 130 



h3b

  Created 23 plans, but explored only 13

      CPU time:    0.0600 sec

      Branching factor:  0.000

      Working Unifies: 500 

      Bindings Added: 46  



h3c

  Created 10 plans, but explored only 6

      CPU time:    0.0100 sec

      Branching factor:  0.000

      Working Unifies: 141 

      Bindings Added: 19  





h4a (failure)!!! Created 116156 plans, but explored only 85873

      CPU time:  390.9200 sec

      Branching factor:  0.000

      Working Unifies: 2497001

      Bindings Added: 98047



h4b



   Created 106027 plans, but explored only 84605

      CPU time:  760.3500 sec

      Branching factor:  0.000

      Working Unifies: 5403554

      Bindings Added: 115260









\subsection{Woodshop and Scheduling World}



In the {\em woodshop} and {\em scheduling world} domains\footnote{Both

domains were developed to test the UCPOP planner \cite{ucpop} and have

also been added to \ipp's domain collection.}, objects can be given

different shapes, surfaces and colors, holes can be drilled

etc. Shaping and drilling usually destroys surfaces including colors

and makes objects dusty. Drilling requires that objects be in certain

shapes, but shaping and painting require that objects obey certain

surface and temperature conditions.  Let us consider two typical

examples in more detail.



The woodshop domain contains the 8 actions {\bf sand}, {\bf vacuum},

{\bf paint}, {\bf forklift}, {\bf drill}, {\bf saw}, {\bf put-in-box},

{\bf unpack}. Drilling damages surfaces and can only be performed on

objects with non-round shapes, painting requires that objects should

be free of dust. A typical planning task comprises the following

object declarations, initial state, and goals:



\bigskip



{\sl 

\begin{tabular}{ll}

object:    &  obj1\\

color:     &  green, plain\\

shape:     &  blob, square, round\\

surface:   &  rough, smooth\\

dimension: & three-eights

\end{tabular}

}



\bigskip



{\sl 

{\bf initial:}

shape(obj1, round), painted(obj1, plain), surface(obj1, rough)}



\bigskip



{\sl 

\begin{tabbing}

{\bf goal:} \= shape(obj1, round), surface(obj1, smooth),

painted(obj1, green), \\ 

\> has-hole(obj1, three-eights), $\neg$ dusty(obj1), boxed(obj1)

\end{tabbing}

}



\bigskip



GAM determines the following goal agenda, which

reflects the natural ordering over subgoals that exists:





{\sl 

\begin{itemize}\addtolength{\itemsep}{-3mm}

\item[1:] has-hole(obj1, three-eights) 

\item[2:] surface(obj1, smooth),  shape(obj1, round) 

\item[3:] $\neg$ dusty(obj1), painted(obj1, green)

\item[4:] boxed(obj1)

\end{itemize}

}



\noindent

for which the optimal plan of 9 actions is found when incrementally

planning for the increasing goal sets from the agenda





\begin{verbatim}

time step   0: saw(obj1, blob, round)

time step   1: drill(obj1, three-eights)

time step   2: saw(obj1, round, blob)

time step   3: sand(obj1, smooth)

time step   4: vacuum(obj1)

time step   5: forklift(obj1)

time step   6: paint(green)

time step   7: forklift(obj1)

time step   8: put-in-box(obj1)

\end{verbatim}



For this tiny woodshop problem, runtime is increasing from 0.08 s to

0.12 s because of the effort invested by GAM, but for larger problems

in which more objects have to be processed, significant improvements

are obtained. In particular, problems that were previously unsolvable

because of the huge search space they create, are solved within a few

seconds. The linearization option of goal agendas greatly

improves runtime because the processing of the individual objects is

independent of each other.



The scheduling world contains more complex actions, but is similar in

the sense that a natural ordering exists in which objects have to be

processed. For the following planning problem



\bigskip



{\sl 

\begin{tabular}{ll}

object:     & A, B\\

paint:      & red, blue\\

location:   & sched, store\\

paint-cond: & nil, red, blue\\

shape-cond: & oblong, cylindrical, flat, rectangular\\

temp-cond:  & cold, hot\\

surf-cond:  & rough, smooth, polished\\

width:      & null, null-1, null-2, null-3\\

orient:     & nil, front, back, left-side, right-side

\end{tabular}

}





{\sl 

\begin{tabbing}

{\bf initial:} \= 

shape(A, rectangular), temperature(A, cold), surface-condition(A, rough),\\

\>  painted(A, blue), has-hole(A, null-2, front), has-hole(A, null-3,

left-side),\\ 

\> shape(B, flat), temperature(B, hot),  surface-condition(B, rough),\\

\> painted(B, nil), has-hole(B, null, nil), have-supply(red),  is-at(sched)

\end{tabbing}}





{\sl \begin{tabbing}

{\bf goal:} \= shape(A, oblong), painted(A, red), has-hole(A, null-1,

right-side), painted(B, red),\\ 

\> $\neg$ has-hole(A, null-2, front), $\neg$ has-hole(A, null-3, left-side),

shape(B, cylindrical), \\

\> temperature(B, cold), surface-condition(B, polished),

has-hole(B, null-2, back)

\end{tabbing}

}





an agenda with 4 entries is generated:



{\sl 

\begin{itemize}\addtolength{\itemsep}{-3mm}

\item[1:] shape(B, cylindrical)

\item[2:] $\neg$ has-hole(A, null-3, left-side)

          $\neg$ has-hole(A, null-2, front)

\item[3:] painted(B, red)

\item[4:] shape(A, oblong), has-hole(A, null-1, right-side), painted(A, red),\\

          surface-condition(B, polished), temperature(B, cold)

          has-hole(B, null-2, back)

\end{itemize}

}



Although this agenda does not completely order goals to the maximal

possible extent, because too many $\prec$ relations cause some subgoal

sets to collapse, it reduces runtime significantly and still enables

the planner to generate the optimal plan of 17 actions. As a

phenomenon, one can observe in many domains that ordering subgoals to

the maximum possible increases the danger of superfluous actions in

plans, while non-maximal agendas can still significantly improve

runtime. Interestingly, removal of irrelevants can preserve optimality

of the solution in some cases.







\begin{verbatim}

time step   0: roll(B)

time step   1: roll(A)

time step   2: make-sprayable(red)

               cool-down(B)

time step   3: spray-paint(B,red)

time step   4: move(sched,store)

time step   5: buy-paint(red)

time step   6: move(store,sched)

time step   7: make-sprayable(red)

               punch(B,null-2,back)

               cool-down(A)               

time step   8: cool-down(B)

               lathe(A)

time step   9: polish(B)

               cool-down(A)               

time step  10: spray-paint(A,red)

time step  11: punch(A,null-1,right)

\end{verbatim}





Using goal agendas plus RIFO, planning time decreases for this

schedworld problem from 3.86 s down to 1.63 s.





\section{Summary and Comparison to Related Work}
\label{related}

Many related approaches have been developed to provide a planner
with the ability to decompose a planning problem by giving it any kind
of goal ordering information. Subsequently, we discuss the most
important of them and review our own work in the light of these
approaches.


Our method introduces a preprocessing approach, which derives a total
ordering for subsets of goals by performing a static, heuristic
analysis of the planning problem at hand. The approach works for
domains described with STRIPS or ADL operators and is based on
polynomial-time algorithms. The purpose of this method is to provide a
planner with search control, \ie we opt at deriving a goal achievement
order and then successively call the planner on the totally ordered
subsets of goals.

The method preserves the soundness of the planning system, but the
completeness only in the case that the planning domain does not
contain deadlocks.  We argue that benchmark domains quite often
possess this property, which is also supported by other authors
\cite{nayak}.

The computation of $\leq_h$ and $\leq_e$ requires only polynomial
time, but both methods are incomplete in the sense that they will not
detect all reasonable goal orderings in the general case. The
complexity of deciding on the existence of {\em forced} and {\em
  reasonable} goal orderings has been proven to be {\sf PSPACE}-hard
in Section~\ref{relation} and therefore, trading completeness for
efficiency seems to be an acceptable solution. Our complexity results
relate to those found by Bylander \citeyear{bylander92a} who proves the {\sf
 PSPACE}-completeness of serial decomposability \cite{korf}. Given a set
of subgoals, {\em serial decomposability} means that  previously
satisfied subgoals do not need to be violated later in the solution
path, \ie once a subgoal has been achieved, it remains valid until the
goal is reached. The purpose of our method is to derive constraints
that make those orderings explicit under which no serial
decomposability of a set of goals can be found, \ie we consider the
complementary problem, which is also reflected in our complexity
proofs.  


In many cases, we found that the goal agenda manager can significantly
improve the performance of the \ipp\ planning system, but we found at
least one domain, namely the {\em tower of hanoi}, where a dramatic
decrease in performance can be observed although \ipp\ still generates
the optimal plan when processing the ordered goals from the agenda.
So far, the complexity results of B\"ackstr\"om and Jonsson
\citeyear{backstrom95} predicted that planning with abstraction
hierarchies can be exponentially less efficient, but because
exponentially longer plans can be generated.

The idea to analyze the effects and preconditions of operators and to
derive ordering constraints based on the interaction of operators can
also be found in a variety of approaches. While we analyze harmful
interactions of operators in our method by studying the delete
effects, the approaches described in \cite{dawsson,korf85,knoblock94}
concentrate on the positive interactions between operators. The
successful matching of effects to preconditions forms the basis to
learn {\em macro-operators}, see \cite{dawsson,korf85}.

The {\sc alpine} system  \cite{knoblock94} learns
abstraction hierarchies for the Prodigy planner \cite{prodigy}. The
approach is based on an ordering of the preconditions and the effects
of each operator, \ie all effects of an operator must be in the same
abstraction hierarchy and its preconditions must be placed at the same
or a lower level than its effects. This introduces an ordering between
the possible subgoals in a domain, which is orthogonal to the ordering
we compute: In {\sc alpine}, a subgoal $A$ is ordered before a subgoal
$B$ if $A$ {\em enables} $B$, \ie $A$ must be {\em possibly} achieved
first in order to achieve $B$. Our method orders $A$ before $B$ if $A$
cannot be achieved without {\em necessarily} destroying $B$. The
result of {\sc alpine} and GAM are a set of binary constraints. In the
case of {\sc alpine}, the constraints are computed between all atoms
in a domain, while GAM restricts the analysis to the goals only. Both
approaches represent the binary constraints in a graph structure.
{\sc alpine} merges atomic goals together if they belong to a strongly
connected component in the graph.  GAM merges sets of goals together
if they have identical degree.  Then they both compute a topological
sorting of the sets that is consistent with the constraints. The
resulting goal orderings can be quite similar as the examples by Knoblock
\citeyear{knoblock94} demonstrate, but GAM approximates reasonable goal
orderings in domains where {\sc alpine} fails in finding abstraction
hierarchies. Two further examples \cite{knoblock-phd} are the
{\em tower of hanoi} domain using only one {\em move} operator and the
{\em blocks world}. In both domains, {\sc alpine} cannot detect the
orderings because it investigates the operator schemata, not the set
of ground actions, and therefore cannot distinguish the orderings
between different instantiations of the same literal. Although {\sc
alpine} could be modified to handle ground actions, this will
significantly increase the amount of computation it requires. GAM on
the other hand, handles large sets of ground actions in an efficient
way, in particular if {\em direct analysis} is
used.\footnote{Abstraction hierarchies are more general than the goal
orderings we compute. They cannot only serve for the purpose of
providing a planner with goal ordering information, but also allow to
generate plans at different levels of refinement, see also
\cite{bacchus-yang}. Two other approaches generating abstraction
hierarchies based on numerical {\em criticality} values can be found in
\cite{abstrips,bundy96}.}

An analysis, which is quite similar to {\sc alpine}, but which is
performed in the framework of HTN planning, is described by Tsuneto et
al.\ \citeyear{tsuneto98}. The approach analyzes the {\em external}
conditions of methods, which cannot be achieved when decomposing the
method further. This means, such conditions have to be established by
the decomposition of those methods, which {\em precede} the method
using this external condition.  Two strategies to determine the
decomposition order of methods are defined and empirically compared.
Here lies the main difference to the other approaches described so
far: Instead of trying to automatically construct the decomposition
orderings, they are predefined and fixed for all domains and problems.


Harmful interactions among operators are studied by Smith and Peot
\citeyear{smith93a} and Etzioni \citeyear{etzioni93a}. A {\em threat}
of an operator $o$ to a precondition $p$ occurs if there is an
instantiation of $o$ such that its effects are inconsistent with $p$
\cite{smith93a}.  The knowledge about threats is used to control a
plan-space planner.  In contrast to a state-space planner such as
\ipp, computing an explicit ordering of goals does not prevent the
presence of threats in a partial plan because the order in which the
goals are processed does not determine the order in which actions
occur in the plan. The notion of forced and reasonable goal orderings
is not comparable to that of a threat because a threat still has the
potential of being resolved by adding binding or ordering constraints
to the plans. In contrast to this, a forced or reasonable goal
ordering persists under all bindings and enforces a specific ordering
of the subgoals.

Given a planning problem, {\sc static} \cite{etzioni93a} computes a
backchaining tree from the goals in the form of an AND/OR graph, which
it subsequently analyzes for the occurrence of goal interactions that
will {\em necessarily} occur. This analysis is much more complicated
than ours, because {\sc static} has to deal with uninstantiated
operators and axioms, which describe properties of legal states. The
result of the analysis are goal ordering rules, which order goals if
certain conditions are satisfied in a state. This is the main
difference to GAM, which generates explicit goal orderings
independently of a specific state. It does not need to extract
conditions that a specific state has to satisfy because it considers
the generic state $s_{(A,\neg B)}$ in the analysis, which represents
all states satisfying $A$, but not $B$. As GAM, {\sc static} is
incomplete in the sense that it cannot detect all existing goal
interactions. The problem for GAM is that deciding reasonable
orderings is \pspace-hard, as we have proven in this paper. The
problem for {\sc static} is that it has to compute the {\em necessary}
effects of an operator in a given state. As Etzioni
\citeyear{etzioni93a} conjectures and Nebel and B\"ackstr\"om
\citeyear{neba94} prove, this problem is computationally intractable
and therefore, any polynomial-time analysis method must be incomplete.

Last, but not least there have been quite a number of approaches in
the late Eighties, which focused directly on subgoal orderings. These
fall into two categories: The approaches described in
\cite{drummond89b,hertzberg89} focus on the detection of conflicts
caused by goal interdependencies to guide a partial-order planner
during search. We do not investigate these approaches in more detail
here because they do not extract explicit goal orderings as a
preprocess to planning as we do.  The works described in
\cite{irani87,irani89,joslin90} implement preprocessing approaches,
which perform a structural analysis of the planning task to determine
an appropriate goal ordering before planning starts. Irani and Cheng
\citeyear{irani87} compute a relation $\prec$ between pairs of goals,
which---roughly speaking---orders a goal $A$ after a goal $B$ if $B$
must be achieved before $A$ can be achieved. Their formalism is rather
complicated and the theoretical properties of the relation are not
investigated. In \cite{irani89}, the approach is extended such that
{\em sets} of goals can be ordered with respect to each other. The
exact properties of the formalism remain unclear. In \cite{joslin90},
a graph-theoretical approach is described that generates a graph with
all atoms from a given domain description as nodes and draws an arc
between a node $A$ and a node $B$ if an operator exists that takes $A$
as precondition and has $B$ as an effect. When assuming that all
operators have inverse counterparts, identifying connected components
in the graph is proposed as a means to order goals. The approach is
unlikely to scale to the size of problem spaces today's planners
consider and it is also completely outdated in terms of terminology.

Finally, one can wonder how the reasonable and forced goal orderings
relate to others defined in the literature. There is only one attempt
of which we know where an ordering relation is explicitly defined and
its properties are studied, see \cite{huellem}. In this paper, the
notion of {\em necessary} goal orderings is introduced, which must be
true in all {\em minimal solution plans} \cite{kamb95}.\footnote{A
plan is minimal if it contains no subplan that is also a solution
plan. We remark that minimality does not mean that only shortest plans
having the least number of actions are considered. In fact, minimal
plans can be highly non-optimal as long as no action is truly
superfluous.} The approach extends operator graphs \cite{smith93a} and
orders a goal based on three criteria called {\em goal subsumption},
{\em goal clobbering}, and {\em precondition violation}. Goal
subsumption $A < B$ holds if every solution plan achieving a goal $B$
in a state $s$ also achieves a goal $A$ in a state $s'$ preceding $s$,
and no plan achieving one of the goals in $\G \setminus \{A\}$ deletes
$A$. Goal clobbering holds if any solution plan for $A$ deletes $B$
and thus, $A < B$. Precondition violation holds if any solution for
$B$ results in a deadlock from which $A$ cannot be reached anymore,
\ie again $A < B$. A composite criterion is defined that tests all
three criteria simultaneously.\footnote{Here, the authors are not very
precise about what they mean with this. We argue that this means that
two goals are ordered if they satisfy at least one of the criteria.}
A goal $A$ is {\em necessarily ordered} before $B$ if it satisfies the
composite criterion.

We remark that {\em precondition violation} seems to be equivalent to
the {\em forced} orderings we introduced, while {\em goal clobbering}
appears to be similar to our {\em reasonable} orderings. It is not
possible for us to verify this conjecture as the authors of
\cite{huellem} do not give exact formal definitions. We have nothing
similar to {\em goal subsumption} and we argue that this criterion
will be rarely satisfied in natural problems: if a goal $A$ is
achieved by every solution for a goal $B$ anyway, then the goal $A$
can be removed from the goal set without changing the planning task.

The authors report that they are able to detect {\em necessary}
orderings in the artificial domains $D_iS_i$, cf. \cite{barrett94},
but fail in typical benchmark domains such as the {\em blocks world}
or the {\em tyreworld}. The reason for this seems to be that their
operator graphs do not represent all possible instantiations of
operator schemes. As the authors claim, this makes operator graph
analysis very efficient. However, the heuristic ordering $\leq_h$ that
we introduced in this paper also takes almost no computation time, and
succeeds in finding the goal orderings in these domains.

\section{Outlook}
\label{outlook}

Three promising avenues for future research are the following: 

First, one can imagine that goal ordering information is also used
{\em during} the search process, \ie by not only ordering the original
goal set, but also other goals that emerge during search. The major
challenge seems to balance the effort on computing the goal ordering
information with the savings that can result for the search
process. One can easily imagine that ordering all goal sets that are
ever generated can become a quite costly investment without yielding a
major benefit for the planner.

Secondly, the refinement of the goal agenda with additional subgoals is
another interesting future line of work. A first investigation using
so-called {\em intermediate goals} (these are facts that the planner
must make \true\ before it can achieve an original goal) has been
explored inside GAM and the results are reported in \cite{gam-report}.
Earlier work addressing the task of learning intermediate goals can be
found in \cite{ruby89}, but this problem has not been in the focus of
AI planning research since then.

A third line of work addresses the interaction of GAM with a
forward-searching planning system. We have seen that GAM preserves the
correctness of a planner, and that it preserves the completeness at
least on deadlock-free planning domains. We have also seen, however,
that solution plans using GAM can get longer, \ie GAM does {\em not}
preserve the optimality of a planner. Recently, planning systems that
do not deliver plans of guaranteed optimality have demonstrated an
impressive performance in terms of runtime and plan length, \eg {\sf
HSP}, which is first mentioned in \cite{geffner-aaai97}, {\sf GRT}
\cite{refanidis-ecp99}, and in particular {\large {\sc ff}}
\cite{hoffmann:ismis-00}. These systems are heuristic-search planners
searching forward in the state space with non-admissible, but
informative heuristics.

The {\large {\sc ff}} planning system developed by one of the authors
has been awarded ``Group A Distinguished Performance Planning System''
and has also won the Schindler Award for the best performing planning
system in the Miconic 10 Elevator domain (ADL track) at the AIPS 2000
planning competition. The integration of goal agenda techniques into
the planner is one of the factors that enabled the excellent behavior
of {\large {\sc ff}} in the competition: they were crucial for scaling
to {\em blocks world} problems of 50 blocks, helped by about a
factor~2 on {\em schedule} and {\em Miconic 10}, and never slowed down
the algorithm.

Forward state-space search is a quite natural framework to be driven
by the goal agenda: Simply let the planner solve a subproblem, and
start the next search from the state where the last search ended. Even
more appealing, heuristic forward-search planners have a deeper kind
of interaction with GAM than for example \graphplan-style planners. In
addition to the smaller problems they are facing when using the goal
agenda, their heuristics are influenced because they employ techniques
for estimating the goal distance from a state. When using the goal
agenda, different goal sets result at each stage of the planning
process and therefore, the goal-distance estimate will be different,
too. Currently a heuristic device inside the {\large {\sc ff}} search
algorithm is being developed, which knows that it is being driven by a
goal agenda, and which has access to the complete set of goals. This
information can be used to further prune unpromising branches from the
search space when it discovers that currently achieved goals will
probably have to be destroyed and reachieved later on.




\bibliography{biblio/phi,biblio/kr,biblio/related,biblio/ich,biblio/planning,biblio/crossrefs}

\end{document}























