%%
%%
%% main file
%%
%%



\documentstyle[jair,twoside,11pt,theapa]{article}


\input epsf %% at top of file



%%
%%
%% command defs
%%
%%



\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}}


\newenvironment{beweis}{\noindent {\bf Proof:}}%
{\hfill \rule[0.3ex]{1ex}{1ex} \par \addvspace{\bigskipamount}}
\newtheorem{theorem}{Theorem}
\newtheorem{def1}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{example}{Example}

\renewcommand{\shortcite}[1]{\citeyear{#1}}


%%
%%
%% shortcut defs
%%
%%



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


\newcommand{\snlp}{SNLP}
\newcommand{\unpop}{Unpop}
\newcommand{\propplan}{PropPlan}
\newcommand{\bddplan}{BDDPlan}
\newcommand{\mips}{Mips}
\newcommand{\systemr}{System-R}
\newcommand{\hsp}{HSP}
\newcommand{\blackbox}{BLACKBOX}
\newcommand{\graphplan}{GRAPHPLAN}
\newcommand{\hspr}{HSP-r}
\newcommand{\grt}{GRT}
\newcommand{\ipp}{IPP}
\newcommand{\stan}{STAN}
\newcommand{\ffall}{FAST-FORWARD}
\newcommand{\ff}{FF}


\newcommand{\aips}{AIPS}

\newcommand{\simple}{SIMPLE}

\newcommand{\strips}{STRIPS}
\newcommand{\adl}{ADL}
\newcommand{\pddl}{PDDL}


\newcommand{\sat}{SAT}
\newcommand{\gsat}{GSAT}

\newcommand{\plansat}{PLANSAT}
\newcommand{\pspace}{PSPACE}
\newcommand{\npspace}{NPSPACE}
\newcommand{\coNP}{co-NP}
\newcommand{\deadend}{DEADEND-FREE}


\newcommand{\ehc}{enforced hill-climbing}
\newcommand{\hc}{hill-climbing}
\newcommand{\bfs}{best-first search}


\newcommand{\true}{{\sc true}}
\newcommand{\false}{{\sc false}}


\newcommand{\Poriginal}{{\mathcal P}}
\newcommand{\Prelaxed}{{\mathcal P}'}


\newcommand{\act}{{\mathcal O}}
\newcommand{\actrelaxed}{{\mathcal O}'}
\newcommand{\G}{{\cal G}}
\newcommand{\I}{{\cal I}}


\newcommand{\pre}{\mbox{pre}}
\newcommand{\add}{\mbox{add}}
\newcommand{\del}{\mbox{del}}





%%
%%
%% title, abstract
%%
%%



%\jairheading{13}{2000}{1-1}{7/00}{10/00}
\ShortHeadings{Fast Plan Generation Through Heuristic Search}
{Hoffmann \& Nebel}
\firstpageno{1}


\begin{document}


\title{The FF Planning System: Fast Plan Generation Through Heuristic
  Search}


\author{\name J\"org Hoffmann \email
       hoffmann@informatik.uni-freiburg.de \\
       \name Bernhard Nebel \email nebel@informatik.uni-freiburg.de \\
       \addr Georges-K\"ohler-Allee, Geb. 52,\\
       79110 Freiburg, Germany}


\maketitle


\begin{abstract}
  We describe and evaluate the algorithmic techniques that are used in
  the \ff\ planning system. Like the \hsp\ system, \ff\ relies on
  forward state space search, using a heuristic that estimates goal
  distances by ignoring delete lists. Unlike \hsp's heuristic, our
  method does not assume facts to be independent. We introduce a novel
  search strategy that combines \hc\ with systematic search, and we
  show how other powerful heuristic information can be extracted and
  used to prune the search space. \ff\ was the most successful
  automatic planner at the recent \aips-2000 planning competition. We
  review the results of the competition, give data for other benchmark
  domains, and investigate the reasons for the runtime performance of
  \ff\ compared to \hsp.\footnote{This article is an extended and
    revised version of a paper \cite{hoffmann:ismis-00} that has been
    published at ISMIS-00.}
\end{abstract}



%%
%%
%% contents ...
%%
%%




\section{Introduction}
\label{introduction}

Over the last few years we have seen a significant increase of the efficiency
of planning systems. This increase is mainly due to three new approaches in
plan generation.
 
The first approach was developed by Blum and Furst
\shortcite{blum:furst:ijcai-95,blum:furst:ai-97}.  In their seminal paper on
the \graphplan{} system \cite{blum:furst:ijcai-95}, they described a new plan
generation technique based on {\em planning graphs}, which was much faster
than any other technique known at this time. Their paper started a whole
series of research efforts that refined this approach by making it even more
efficient \cite{fox:long:jair-98,kambhampati:et:al:ecp-97} and by extending
it to cope with more expressive planning languages
\cite{koehler:et:al:ecp-97,gazen:knoblock:ecp-97,anderson:et:al:aips-98,nebel:jair-00}.

The second approach is the {\em planning as satisfiability} method, which
translates planning to propositional satisfiability
\cite{kautz:selman:aaai-96}. In particular there is the hope that advances in
the state of the art of propositional reasoning systems carry directly over to
planning systems relying on this technology. In fact, Kautz and Selman
\shortcite{kautz:selman:ijcai-99} predicted that research on planning methods
will become superfluous because the state of the art in propositional
reasoning systems will advance much faster than in planning systems.

A third new approach is {\em heuristic-search planning} as proposed by
Bonet and Geffner
\shortcite{bonet:geffner:aips-ws-98,bonet:geffner:ecp-99}. In this
approach a heuristic function is derived from the specification of the
planning instance and used for guiding the search through the state
space. As demonstrated by the system \ff\footnote{\ff{} stands for
  \ffall.} at the planning competition at \aips-2000, this approach
proved to be competitive. In fact, \ff\ outperformed all the other
fully automatic systems and was nominated {\em Group A Distinguished
  Performance Planning System} at the competition.


In \hsp\ \cite{bonet:geffner:aips-ws-98}, goal distances are estimated
by approximating solution length to a relaxation of the planning task
\cite{bonet:et:al:aaai-97}. While \ff\ uses the same relaxation for
deriving its heuristics, it differs from \hsp\ in a number of
important details. Its base heuristic technique can be seen as an
application of \graphplan\ to the relaxation. This yields goal
distance estimates that, in difference to \hsp's estimates, do not
rely on an independence assumption. \ff\ uses a different search
technique than \hsp, namely an {\em enforced form} of \hc, combining
local and systematic search. Finally, it employs a powerful pruning
technique that selects a set of promising successors to each search
node, and another pruning technique that cuts out branches where it
appears that some goal has been achieved too early.  Both techniques
are obtained as a side effect of the base heuristic method.



Concerning the research strategy that \ff\ is based on, we remark the
following. A lot of classical planning approaches, like partial-order
planning \cite{mcallester:rosenblitt:aaai-91} or planning graph
analysis \cite{blum:furst:ai-97}, are generic problem solving methods,
developed following some theoretical concept, and tested on examples
from the literature afterwards. In our approach, exploring the idea of
heuristic search, there is no such clear distinction between
development and testing. The search strategy, as well as the pruning
techniques, are generic methods that have been motivated by observing
examples. Also, design decisions were made on the basis of careful
experimentation. This introduces into the system a bias towards the
examples used for testing during development. We were testing our
algorithms on a range of domains often used in the planning
literature. Throughout the paper, we will refer to domains that are
frequently used in the literature, and to tasks from such domains, as
{\em benchmarks}. In the development phase, we used benchmark examples
from the {\sl Assembly}, {\sl Blocksworld}, {\sl Grid}, {\sl Gripper},
{\sl Logistics}, {\sl Mystery}, {\sl Mprime}, and {\sl Tireworld}
domains. When describing our algorithms in the paper, we indicate the
points where those testing examples played a role for design decision
making.

Planning is known to be \pspace-complete even in its simplest form
\cite{bylander:ai-94}. Thus, in the general case, there is no
efficient algorithmic method. It is therefore worthwhile to look for
algorithms that are efficient at least on restricted subclasses. To
some extent, this idea has been pursued by posing severe syntactical
restrictions to the planning task specifications
\cite{bylander:ai-94}. Our approach is complementary to this.
Examining the existing benchmarks, one finds that they, indeed, do not
exploit the full expressivity of the underlying planning formalism.
Though they do not fulfill any obvious rigid syntactical restrictions,
almost none of them is particularly hard. In almost all of the
existing benchmark domains, a non-optimal plan can, in principle, be
generated in polynomial time. Using the benchmarks for inspiration
during development, we have been able to come up with a heuristic
method that is not provably efficient, but does work well empirically
on a large class of planning tasks. This class includes almost all of
the current planning benchmarks. Intuitively, the algorithms exploit
the simple structure underlying these tasks. Our ongoing work is
concerned with finding a formal characterization of that ``simple''
structure, and thereby formalizing the class of planning tasks that
\ff\ works well on.


%Section~\ref{architecture} gives a schematic overview over \ff's
%system architecture, and 
Section~\ref{architecture} gives a schematic view on \ff's system
architecture, and Section~\ref{notation} introduces our notational
conventions for \strips\ domains. Sections~\ref{heuristic}
to~\ref{pruning} describe the base heuristic technique, search
algorithm, and pruning methods, respectively. Section~\ref{adl} shows
how the algorithms are extended to deal with \adl\ domains.  System
performance is evaluated in Section~\ref{performance}, demonstrating
that \ff\ generates solutions extremely fast in a large range of
planning benchmark domains. In order to illustrate our intuitions on
the kind of structure that \ff\ can exploit successfully, the section
also gives examples of domains where the method is less appropriate.
Finally, to clarify the performance differences between \ff\ and \hsp,
the section describes a number of experiments we made in order to
estimate which of the new algorithmic techniques is most useful. We
show connections to related work at the points in the text where they
apply, and overview other connections in Section~\ref{related}.
Section~\ref{outlook} outlines our current avenue of research.




\section{System Architecture}
\label{architecture}

To give the reader an overview of \ff's system architecture,
Figure~\ref{xfig/ff_archi.eps} shows how \ff's most fundamental
techniques are arranged.


%figure
\scalefig{0.35}{xfig/ff_archi.eps}{\ff's base system architecture.}

The fundamental heuristic technique in \ff\ is relaxed \graphplan,
which we will describe in Section~\ref{heuristic}. The technique gets
called on every search state by {\em \ehc}, our search algorithm. This
is a forward searching engine, to be described in
Section~\ref{search}.  Given a state, relaxed \graphplan\ informs the
search with a goal distance estimate, and additionally with a set of
promising successors for the state, the {\em helpful actions}, to be
described in Section~\ref{pruning}. Upon termination, \ehc\ either
outputs a solution plan, or reports that it has failed.

On top of the base architecture shown in
Figure~\ref{xfig/ff_archi.eps}, we have integrated a few optimizations
to cope with special cases that arose during testing:

\begin{itemize}
\item If a planning task contains states from which the goal is
  unreachable (dead ends, defined in
  Section~\ref{search:completeness}), then \ehc\ can fail to find a
  solution. In that case, a complete heuristic search engine is
  invoked to solve the task from scratch.
\item In the presence of goal orderings, \ehc\ sometimes wastes
  a lot of time achieving goals that need to be cared for later on.
  Two techniques trying to avoid this are integrated:
  \begin{itemize}
  \item {\em Added goal deletion}, introduced in
    Section~\ref{pruning:orderings}, cuts out branches where some goal
    has apparently been achieved too early.
  \item The {\em goal agenda} technique, adapted from work by Jana
    Koehler \shortcite{koehler:aips-98}, feeds the goals to the
    planner in an order determined as a pre-process
    (Section~\ref{pruning:orderings:search}).
  \end{itemize}
\end{itemize}





\section{Notational Conventions}
\label{notation}

For introducing \ff's basic techniques, we consider simple \strips\ 
planning tasks, as were introduced by Fikes and Nilsson
\shortcite{fikes:nilsson:ai-71}. Our notations are as follows.

\begin{def1}[State]
  A {\em state} $S$ is a finite set of logical atoms.
\end{def1}

\noindent 
We assume that all operator schemata are grounded, \ie we only talk
about {\em actions}.

\begin{def1}[Strips Action]\label{op}
  A {\em STRIPS action} $o$ is a triple
\[
o = ( \pre(o), \add(o), \del(o) )
\]
where $\pre(o)$ are the {\em preconditions} of $o$, $\add(o)$ is the
{\em add list} of $o$ and $\del(o)$ is the {\em delete list} of the
action, each being a set of atoms. For an atom $f \in \add(o)$, we say
that $o$ {\em achieves} $f$. The result of applying a single STRIPS
action to a state is defined as follows:
\[
Result(S,\langle o\rangle) = \left \{ \begin{array}[]{ll} (S \cup
    \add(o)) \setminus
    \del(o) & \pre(o) \subseteq S\\
    \mbox{undefined} & \mbox{otherwise} \end{array} \right.
\]
In the first case, where $\pre(o) \subseteq S$, 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),\langle o_n \rangle).
\]
\end{def1}

\begin{def1}[Planning Task]\label{problem}
  A {\em planning task} $\Poriginal = (\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 atoms.
\end{def1}

\noindent
Our heuristic method is based on {\em relaxed planning tasks}, which
are defined as follows.

\begin{def1}[Relaxed Planning Task]\label{relaxedproblem}
  Given a planning task $\Poriginal = (\act,\I,\G)$. The {\em
    relaxation} $\Prelaxed$ of $\Poriginal$ is defined as $\Prelaxed =
  (\act',\I,\G)$, with
\[
\act' = \{ ( pre(o), \add(o), \emptyset ) \mid (
\pre(o), \add(o), \del(o) ) \in \act \}
\]
\end{def1}

\noindent
In words, one obtains the relaxed planning task by ignoring the delete
lists of all actions. Plans are simple sequences of actions in our
framework.

\begin{def1}[Plan]\label{plan}
  Given a planning task $\Poriginal = (\act,\I,\G)$. A {\em plan} is a
  sequence $P = \langle o_1, \dots, o_n \rangle$ of actions in $\act$
  that solves the task, \ie for which $\G \subseteq Result(\I,P)$
  holds. An action sequence is called a {\em relaxed plan} to
  $\Poriginal$, iff it solves the relaxation $\Prelaxed$ of
  $\Poriginal$.
\end{def1}





\section{\graphplan\ as a Heuristic Estimator}
\label{heuristic}

In this section, we introduce the base heuristic method used in \ff.
It is derived by applying \graphplan\ to relaxed planning tasks. The
resulting goal distance estimates do not, like \hsp's estimates, rely
on an independence assumption. We prove that the heuristic computation
is polynomial, give some notions on how distance estimates can be kept
cautious, and describe how the method can be implemented efficiently.


Consider the heuristic method that is used in \hsp\ 
\cite{bonet:geffner:aips-ws-98}. Given a planning task $\Poriginal =
(\act, \I, \G)$, \hsp\ estimates for each state $S$ that is reached in
a forward search the solution length of the task $\Prelaxed_S =
(\actrelaxed, S, \G)$, \ie the length of a relaxed plan that achieves
the goals starting out from $S$. As computing the optimal solution
length to $\Prelaxed_S$---which would make an admissible
heuristic---is {\sf NP}-hard \cite{bylander:ai-94}, the \hsp\ estimate
is a rough approximation based on computing the following weight
values.

\begin{equation}\label{hsp-weights}
weight_S(f) := \left\{ \begin{array}[]{ll}
    0 & \mbox{if } f \in S\\
    i & \mbox{if } [ min_{o \in \act, f \in \add(o)} \sum_{p \in
    \pre(o)} weight_S(p) ] = i - 1\\
    \infty & \mbox{otherwise} \end{array}
  \right.\\
\end{equation}

\hsp\ assumes facts to be achieved independently in the sense that the
weight of a set of facts---an action's preconditions---is estimated as
the {\em sum} of the individual weights. The state's heuristic
estimate is

\begin{equation}\label{hsp-heuristic}
h(S) := weight_S( \G ) = \sum_{g \in \G} weight_S( g )
\end{equation}

Assuming facts to be achieved independently, this heuristic ignores
positive interactions that can occur. Consider the following short
example planning task, where the initial state is empty, the goals are
$\{ G_1, G_2 \}$, and there are the following three actions:

\begin{center}
\begin{tabular}{lrrrr}
name         &   &  $(\pre,$     &   $\add,$     &   $\del)$
\vspace{0.15cm}\\
{\bf op$G_1$} & =  & $(\{ P \},$    & $\{ G_1 \},$  &  $\emptyset)$ \vspace{0.1cm} \\
{\bf op$G_2$} & =  & $(\{ P \},$    & $\{ G_2 \},$  &  $\emptyset)$ \vspace{0.1cm} \\
{\bf op$P$}   & =  & $(\emptyset,$  &  $\{ P \},$   &  $\emptyset)$
\vspace{0.0cm} \\
\end{tabular}
\end{center}

\hsp's weight value computation results in $P$ having weight one, and
each goal having weight two. Assuming facts to be achieved
independently, the distance of the initial state to a goal state is
therefore estimated to four. Obviously, however, the task is solvable
in only three steps, as {\bf op$G_1$} and {\bf op$G_2$} share the
precondition $P$. In order to take account of such positive
interactions, our idea is to start \graphplan\ on the tasks
$(\actrelaxed, S, \G)$, and extract an explicit solution, \ie a
relaxed plan. One can then use this plan for heuristic evaluation. We
will see in the next section that this approach is feasible:
\graphplan\ can be proven to solve relaxed tasks in polynomial time.






\subsection{Planning Graphs for Relaxed Tasks}
\label{heuristic:planning_graphs}

Let us examine how \graphplan\ behaves when it is started on a
planning task that does not contain any delete lists. We briefly
review the basic notations of the \graphplan\ algorithm
\cite{blum:furst:ai-97}.

A planning graph is a directed, layered graph that contains two kinds
of nodes: {\em fact nodes} and {\em action nodes}. The layers
alternate between fact and action layers, where one fact and action
layer together make up a {\em time step}. In the first time step,
number $0$, we have the fact layer corresponding to the initial state
and the action layer corresponding to all actions that are applicable
in the initial state. In each subsequent time step $i$, we have the
layer of all facts that can possibly be made true in $i$ time steps,
and the layer of all actions that are possibly applicable given those
facts.

One crucial thing that \graphplan\ does when building the planning
graph is the inference of {\em mutual exclusion} relations. A pair of
actions $( o, o' )$ at time step $0$ is marked mutually exclusive, if
$o$ and $o'$ {\em interfere}, \ie if one action deletes a precondition
or an add effect of the other. A pair of facts $( f, f' )$ at a time
step $i > 0$ is marked mutually exclusive, if each action at level $i
- 1$ that achieves $f$ is exclusive of each action at level $i - 1$
that achieves $f'$. A pair of actions $( o, o' )$ at a time step $i >
0$ is marked mutually exclusive, if the actions interfere, or if they
have {\em competing needs}, \ie if some precondition of $o$ is
exclusive of some precondition of $o'$.  The planning graph of a
relaxed task does not contain any exclusion relations at all.

\begin{proposition}\label{graphplan:no_exclusions}
  Let $\Prelaxed = (\actrelaxed, \I, \G)$ be a relaxed \strips\ 
  task. Started on $\Prelaxed$, \graphplan\ will not mark any pair
  of facts or actions as mutually exclusive.
\end{proposition}

\begin{beweis}
  The Proposition is easily proven by induction over the depth of the
  planning graph.

{\em Base case: time step $0$}. Only interfering actions are marked
mutual exclusive at time step $0$. As there are no delete effects, no
pair of actions interferes.

{\em Inductive case: time step $i \rightarrow $ time step $i + 1$}.
Per induction hypothesis, the facts are not exclusive as their
achievers one time step ahead are not. From this it follows that no
pair of actions has competing needs. They do not interfere either.
\end{beweis}

When started on a planning task, \graphplan\ extends the planning
graph layer by layer until a fact layer is reached that contains all
goal facts, and in which no two goal facts are marked
exclusive.\footnote{If no such fact layer can be reached, then the
  task is proven to be unsolvable \cite{blum:furst:ai-97}.} Starting
from that layer, a recursive backward search algorithm is invoked. To
find a plan for a set of facts at layer $i > 0$, initialize the set of
selected actions at layer $i - 1$ to the empty set. Then, for each
fact, consider all achieving actions at layer $i - 1$ one after the
other and select the first one that is not exclusive of any action
that has already been selected. If there exists such an action,
proceed with the next fact.  If not, backtrack to the last fact and
try to achieve it with a different action. If an achieving action has
been selected for each fact, then collect the preconditions of all
these actions to make up a new set of facts one time step earlier.
Succeed when fact layer $0$---the initial state---is reached, where no
achieving actions need to be selected. On relaxed tasks, no
backtracking occurs in \graphplan's search algorithm.


\begin{proposition}\label{graphplan:no_backtracks}
  Let $\Prelaxed = (\actrelaxed, \I, \G)$ be a relaxed \strips\ 
  task. Started on $\Prelaxed$, \graphplan\ will never backtrack.
\end{proposition}

\begin{beweis}
  Backtracking only occurs if all achievers for a fact $f$ are
  exclusive of some already selected action. With
  Proposition~\ref{graphplan:no_exclusions}, we know that no
  exclusions exist, and thus, that this does not happen. Also, if $f$
  is in graph layer $i$, then there is at least one achiever in layer
  $i-1$ supporting it.
\end{beweis}

While the above argumentation is sufficient for showing
Proposition~\ref{graphplan:no_backtracks}, it does not tell us much
about what is actually going on when one starts \graphplan\ on a
task without delete lists. What happens is this. Given the task
is solvable, the planning graph gets extended until some fact layer is
reached that contains all the goals. Then the recursive search starts
by selecting achievers for the goals at this level. The first attempt
succeeds, and new goals are set up one time step earlier. Again, the
first selection of achievers succeeds, and so forth, until the initial
state is reached. Thus, search performs only a single sweep over the
graph, starting from the top layer going down to the initial layer,
and collects a relaxed plan on its way. In particular, the procedure
takes only polynomial time in the size of the task.

\begin{theorem}\label{graphplan:polynomial}
  Let $\Prelaxed = (\actrelaxed, \I, \G)$ be a solvable relaxed \strips\ 
  task, where the length of the longest add list of any action is
  $l$. Then \graphplan\ will find a solution to $\Prelaxed$ in time
  polynomial in $l$, $|\actrelaxed|$ and $|\I|$.
\end{theorem}

\begin{beweis}
  Building the planning graph is polynomial in $l$, $|\actrelaxed|$,
  $|\I|$ and $t$, where $t$ is the number of time steps built
  \cite{blum:furst:ai-97}. Now, in our case the total number
  $|\actrelaxed|$ of actions is an upper limit to the number of time
  steps. This is just because after this number of time steps has been
  built, all actions appear at some layer in the graph. Otherwise,
  there is a layer $i$ where no new action comes in, \ie action layer
  $i - 1$ is identical to action layer $i$. As the task is
  solvable, this implies that all goals are contained in fact layer
  $i$, which would have made the process stop right away. Similarly,
  action layer $|\actrelaxed|$ would be identical to action layer
  $|\actrelaxed|-1$, implying termination. The graph building phase is
  thus polynomial in $l$, $|\actrelaxed|$ and $|\I|$.
  
  Concerning the plan extraction phase: With
  Proposition~\ref{graphplan:no_backtracks}, search traverses the
  graph from top to bottom, collecting a set of achieving actions at
  each layer. Selecting achievers for a set of facts is
  $O(l*|\actrelaxed|+|\I|)$: A set of facts has at most size
  $l*|\actrelaxed|+|\I|$, the maximal number of distinct facts in the
  graph. An achieving action can be found to each fact in constant
  time using the planning graph. As the number of layers to be looked
  at is $O(|\actrelaxed|)$, search is polynomial in the desired
  parameters.
\end{beweis}

Starting \graphplan\ on a solvable search state task $(\actrelaxed,
S, \G)$ yields---in polynomial time, with
Theorem~\ref{graphplan:polynomial}---a relaxed solution $\langle O_0,
\dots, O_{m-1} \rangle$, where each $O_i$ is the set of actions selected
in parallel at time step $i$, and $m$ is the number of the first fact
layer containing all goals. As we are interested in an estimation of
{\em sequential} solution length, we define our heuristic as follows.

\begin{equation}\label{ff-heuristic}
h(S) := \sum_{i = 0, \dots, m-1} |O_i|
\end{equation}

The estimation values obtained this way are, on our testing examples,
usually lower than \hsp's estimates (Equations~\ref{hsp-weights}
and~\ref{hsp-heuristic}), as extracting a plan takes account of
positive interactions between facts. Consider again the short example
from the beginning of this section, empty initial state, two goals $\{
G_1, G_2 \}$, and three actions:

\begin{center}
\begin{tabular}{lrrrr}
name         &   &  $(\pre,$     &   $\add,$     &   $\del)$
\vspace{0.15cm}\\
{\bf op$G_1$} & =  & $(\{ P \},$    & $\{ G_1 \},$  &  $\emptyset)$ \vspace{0.1cm} \\
{\bf op$G_2$} & =  & $(\{ P \},$    & $\{ G_2 \},$  &  $\emptyset)$ \vspace{0.1cm} \\
{\bf op$P$}   & =  & $(\emptyset,$  &  $\{ P \},$   &  $\emptyset)$
\vspace{0.0cm} \\
\end{tabular}
\end{center}

Starting \graphplan\ on the initial state, the goals are contained in
fact layer two, causing selection of {\bf op$G_1$} and {\bf op$G_2$}
in action layer one. This yields the new goal $P$ at fact layer one,
which is achieved with {\bf op$P$}. The resulting plan is $\langle \{$
{\bf op$P$} $\}, \{$ {\bf op$G_1$}, {\bf op$G_2$} $\} \rangle$, giving
us the correct goal distance estimate three, as distinct from \hsp's
estimate four.




\subsection{Solution Length Optimization}
\label{heuristic:solution_length} 


We use \graphplan's heuristic estimates, Equation~\ref{ff-heuristic},
in a greedy strategy, to be introduced in
Section~\ref{search:enforced}, that does not take its decisions back
once it has made them. From our experience with running this strategy
on our testing examples, this works best when distance estimates are
cautious, \ie as low as possible. As already said, an {\em optimal}
sequential solution can not be synthesized efficiently. What one {\em
  can} do is apply some techniques to make \graphplan\ return as short
solutions as possible. Below, we describe some ways of doing that.
The first technique is a built-in feature of \graphplan\ and ensures a
minimality criterion for the relaxed plan. The two other techniques
are heuristic optimizations.



\subsubsection{NOOPs-first}
\label{heuristic:solution_length:noops} 


The original \graphplan\ algorithm makes extensive use of so-called
{\em NOOP}s. These are dummy actions that simply propagate facts from
one fact layer to the next. For each fact $f$ that gets inserted into
some fact layer, a NOOP corresponding to that fact is inserted into
the action layer at the same time step.  This NOOP has no other effect
than adding $f$, and no other precondition than $f$.  When performing
backward search, the NOOPs are considered just like any other
achiever, \ie one way of making a fact true at time $i > 0$ is to
simply keep it true from time $i - 1$.

In \graphplan, the implementation uses as a default the {\em
  NOOPs-first} heuristic, \ie if there is a NOOP present for achieving
a fact $f$, then this NOOP is considered first, before the planner
tries selecting other ``real'' actions that achieve $f$. On relaxed
tasks, the NOOPs-first heuristic ensures a minimality criterion for
the returned plan as follows.


\begin{proposition}\label{graphplan:no_doubleops}
  Let $(\actrelaxed, \I, \G)$ be a relaxed \strips\ task, which is
  solvable. Using the NOOPs-first strategy, the plan that \graphplan\ 
  returns will contain each action at most once.
\end{proposition}

\begin{beweis}
  Let us assume the opposite, \ie one action $o$ occurs twice in the
  plan $\langle O_0, \dots, O_{m-1} \rangle$ that \graphplan\ finds.
  We have $o \in O_i$ and $o \in O_j$ for some layers $i, j$ with $i <
  j$.

  Now, the action $o$ has been selected at layer $j$ to achieve some
  fact $f$ at layer $j + 1$. As the algorithm is using the NOOPs-first
  strategy, this implies that there is no NOOP for fact $f$ contained
  in action layer $j$: otherwise, the NOOP---not action $o$---would
  have been selected for achieving $f$.

  In contradiction to this, action layer $j$ does indeed contain a
  NOOP for fact $f$. This is because action $o$ already appears in
  action layer $i < j$. As $f$ gets added by $o$, it appears in fact
  layer $i + 1 \leq j$. Therefore, a NOOP for $f$ is inserted in
  action layer $i + 1 \leq j$, and, in turn, will be inserted into
  each action layer $i' \geq i + 1$.
\end{beweis}





\subsubsection{Difficulty Heuristic}
\label{heuristic:solution_length:difficulty} 


With the above argumentation, if we can achieve a fact by using a
NOOP, we should do that. The question is, which achiever should we
choose when no NOOP is available? It is certainly a good idea to
select an achiever whose preconditions seem to be ``easy''. From the
graph building phase, we can obtain a simple measure for the
difficulty of an action's preconditions as follows.

\begin{equation}\label{difficulty}
\mbox{difficulty}(o) := \sum_{p \in \pre(o)} min\{ i \mid p \mbox{ is
  member of the fact layer at time step } i \}
\end{equation}

The difficulty of each action can be set when it is first inserted
into the graph. During plan extraction, facing a fact for which no
NOOP is available, we then simply select an achieving action with
minimal difficulty. This heuristic works well in situations where
there are several ways to achieve one fact, but some ways need less
effort than others.





\subsubsection{Action Set Linearization}
\label{heuristic:solution_length:linearization} 

Assume \graphplan\ has settled for a parallel set $O_i$ of achievers
at a time step $i$, \ie achieving actions have been selected for all
goals at time step $i+1$. As we are only interested in sequential
solution length, we still have a choice on how to linearize the
actions. Some linearizations can lead to shorter plans than others. If
an action $o \in O_i$ adds a precondition $p$ of another action $o'
\in O_i$, then we do not need to include $p$ in the new set of facts
to be achieved one time step earlier, given that we restrict ourselves
to execute $o$ before $o'$. The question now is, how do we find a
linearization of the actions that minimizes our new fact set? The
corresponding decision problem is {\sf NP}-complete.

\begin{def1}\label{optimal_linearization}
Let {\sf OPTIMAL ACTION LINEARIZATION} denote the following problem.

\medskip 
{\em Given a set $\act$ of relaxed \strips\ actions and a
  positive integer $K$. Is there a one-to-one function $f: \act
  \mapsto \{1, 2, \dots, |\act|\}$ such that the number of unsatisfied
  preconditions when executing the sequence $\langle f^{-1}(1), \dots,
  f^{-1}(|\act|) \rangle$ is at most $K$ ?}
\end{def1}

\begin{theorem}\label{optimal_linearization-theo}
Deciding {\sf OPTIMAL ACTION LINEARIZATION} is {\sf NP}-complete.
\end{theorem}

\begin{beweis}
  Membership is obvious. Hardness is proven by transformation from
  {\sf DIRECTED OPTIMAL LINEAR ARRANGEMENT}
  \cite{even:shiloach:tr-75}. Given a directed graph $G = (V,A)$ and a
  positive integer $K$, the question is, does there exists a
  one-to-one function $f: V \mapsto \{1, 2, \dots, |V|\}$ such that
  $f(u) < f(v)$ whenever $(u,v) \in A$ and such that $\sum_{(u,v) \in
    A}(f(v) - f(u)) \leq K$ ?
  
  To a given directed graph, we define a set of actions as follows.
  For each node $w$ in the graph, we define an action in our set
  $\act$. For simplicity of presentation, we identify the actions with
  their corresponding nodes. To begin with, we set $\pre(w) = \add(w)
  = \emptyset$ for all $w \in V$. Then, for each edge $(u,v) \in A$,
  we create new logical facts $P_w^{(u,v)}$ and $R_w^{(u,v)}$ for $w
  \in V$.
  
  Using these new logical facts, we now adjust all precondition and
  add lists to express the constraint that is given by the edge
  $(u,v)$. Say action $u$ is ordered before action $v$ in a
  linearization. We need to simulate the difference between the
  positions of $v$ and $u$. To do this, we define our actions in a way
  such that the bigger this difference is, the more unsatisfied
  preconditions there are when executing the linearization.  First, we
  ``punish'' all actions that are ordered before $v$, by giving them
  an unsatisfied precondition.
\[
\pre(w) := \pre(w) \cup P_w^{(u,v)} \mbox{ for } w \in V, \;
\add(v) := \add(v) \cup \{ P_w^{(u,v)} \mid w \in V \}
\]
With this definition, the actions $w$ ordered before $v$---and $v$
itself---will have the unsatisfied precondition $P_w^{(u,v)}$, while
those ordered after will get this precondition added by $v$. Thus, the
number of unsatisfied preconditions we get here is exactly $f(v)$.

Secondly, we ``give a reward'' to each action that is ordered {\em
  before $u$}. We simply do this by letting those actions add a
precondition of $u$, which would otherwise go unsatisfied.
\[
\add(w) := \add(w) \cup R_w^{(u,v)} \mbox{ for } w \in V, \;
\pre(u) := \pre(u) \cup \{ R_w^{(u,v)} \mid w \in V \}
\]
That way, we will have exactly $|V| - (f(u) - 1)$ unsatisfied
preconditions, namely the $R_w^{(u,v)}$ facts for all actions except
those that are ordered before $u$.

Summing up the number of unsatisfied preconditions we get for a
linearization $f$, we arrive at
\[
\sum_{(u,v) \in A} (f(v) + |V| - (f(u) - 1)) = \sum_{(u,v) \in A}
(f(v) - f(u)) + |A| * (|V| + 1)
\]
We thus define our new positive integer $K' := K + |A| * (|V| + 1)$.

Finally, we make sure that actions $u$ get ordered before actions $v$
for $(u,v) \in A$. We do this by inserting new logical ``safety''
facts $S_1^{(u,v)}, \dots, S_{K'+1}^{(u,v)}$ into $v$'s precondition-
and $u$'s add list.
\[
\pre(v) := \pre(v) \cup \{ S_1^{(u,v)}, \dots, S_{K'+1}^{(u,v)} \}, \;
\add(u) := \add(u) \cup \{ S_1^{(u,v)}, \dots, S_{K'+1}^{(u,v)} \}
\]
Altogether, a linearization $f$ of our actions leads to at most $K'$
unsatisfied preconditions if and only if $f$ satisfies the
requirements for a directed optimal linear arrangement. Obviously, the
action set and $K'$ can be computed in polynomial time.
\end{beweis}


Our sole purpose with linearizing an action set in a certain order is
to achieve a smaller number of unsatisfied preconditions, which, in
turn, might lead to a shorter relaxed solution.\footnote{It should be
  noted here that using optimal action linearizations at each time
  step does {\em not} guarantee the resulting relaxed solution to be
  optimal, which would give us an admissible heuristic.} Thus, we are
certainly not willing to pay the price that finding an optimal
linearization of the actions is likely to cost, according to
Theorem~\ref{optimal_linearization-theo}. There are a few methods how
one can approximate such a linearization, like introducing an ordering
constraint $o < o'$ for each action $o$ that adds a precondition of
another action $o'$, and trying to linearize the actions such that
many of these constraints are met. During our experimentations, we
found that parallel actions adding each other's preconditions occur so
rarely in our testing tasks that even approximating is not worth the
effort. We thus simply linearize all actions in the order they get
selected, causing almost no computational overhead at all.








\subsection{Efficient Implementation} 
\label{heuristic:implementation} 



We have implemented our own version of \graphplan, highly optimized
for solving relaxed planning tasks. It exploits the fact that the
planning graph of a relaxed task does not contain any exclusion
relations (Proposition~\ref{graphplan:no_exclusions}). Our
implementation is also highly optimized for repeatedly solving
planning tasks which all share the same set of actions---the tasks
$\Prelaxed_S = (\actrelaxed, S, \G)$ as described at the beginning of
this section.


Planning task specifications usually contain some operator schemata,
and a set of constants. Instantiating the schemata with the constants
yields the actions to the task. Our system instantiates all operator
schemata in a way such that all, and only, reachable actions are
built.  Reachability of an action here means that, when successively
applying operators to the initial state, all of the action's
preconditions appear eventually. We then build what we call the
connectivity graph. This graph consists of two layers, one containing
all (reachable) actions, and the other all (reachable) facts. From
each action, there are pointers to all preconditions, add effects and
delete effects.
%Other way round, from each fact there are pointers to all
%actions that add it, that delete it, or that it is precondition
%of.\footnote{Building a planning graph without exclusion relations,
%  the fix point layer would correspond directly to our connectivity
%  graph.} 
All of \ff's computations are efficiently implemented using this graph
structure. For the subsequently described implementation of relaxed
\graphplan, we only need the information about preconditions and add
effects.


As a relaxed planning graph does not contain any exclusion relations,
the only information one needs to represent it are what we call the
{\em layer memberships}, \ie for each fact or action, the number of
the first layer at which it appears in the graph. Called on an
intermediate task $\Prelaxed_S = (\actrelaxed, S, \G)$, our version of
\graphplan\ computes these layer memberships by using the following
fixpoint computation. The layer memberships of all facts and actions
are initialized to $\infty$. For each action, there is also a counter,
which is initialized to $0$. Then, fact layer $0$ is built implicitly
by setting the layer membership of all facts $f \in S$ to $0$. Each
time when a fact $f$ gets its layer membership set, all actions of
which $f$ is a precondition get their counter incremented. As soon as
the counter for an action $o$ reaches the total number of $o$'s
preconditions, $o$ is put to a list of scheduled actions for the
current layer. After a fact layer $i$ is finished, all actions
scheduled for step $i$ have their layer membership set to $i$, and
their adds, if not already present, are put to the list of scheduled
facts for the next fact layer at time step $i+1$. Having finished with
action layer $i$, all scheduled facts at step $i+1$ have their
membership set, and so on. The process continues until all goals have
a layer membership lower than $\infty$. It should be noticed here that
this view of planning graph building corresponds closely to the
computation of the weight values in \hsp. Those can be computed by
applying the actions in layers as above, updating weight values and
propagating the changes each time an action comes in, and stopping
when no changes occur in a layer. Having finished the relaxed version
of planning graph building, a similarly trivial version of
\graphplan's solution extraction mechanism is invoked. See
Figure~\ref{code:1P}.
%When the graph building phase stops without reaching the goals, then
%this implies that $\Prelaxed_S$ is unsolvable---there is no relaxed
%solution from $S$. This, in turn, implies that there is also no real
%solution from $S$. The heuristic value of $S$ is then consequently set
%to $h(S) := \infty$. In the other case, all goals having a layer
%membership lower than $\infty$, the relaxed version of \graphplan's
%solution extraction mechanism is invoked. See Figure~\ref{code:1P}.

\begin{figure}[htb]
{\small
\begin{tabbing}
{\bf for} \= $i$ := $1, \dots, m$ {\bf do}\\
\> $G_i$ := $\{ g \in \G \mid \mbox{layer-membership}(g) = i \}$\\
{\bf endfor}\\
{\bf for} $i$ := $m, \dots, 1$ {\bf do}\\
\> {\bf for} \= all $g \in G_i, \; g \; \mbox{not marked \true\ at time}
\; i$ {\bf do}\\
\> \> select an action $o$ with $g \in add(o)$ and layer membership $i - 1$, $o$'s difficulty being minimal\\
\> \> {\bf for} \= all $f \in pre(o), \; \mbox{layer-membership}(f) \neq 0, \; f
\; \mbox{not marked \true\ at time} \; i-1$ {\bf do}\\
\> \> \> $G_{\mbox{layer-membership}(f)}$ := $G_{\mbox{layer-membership}(f)} \cup \{ f \}$\\
\> \> {\bf endfor}\\
\> \> {\bf for} \= all $f \in add(o)$ {\bf do}\\
\> \> \> mark $f$ as \true\ at times $i-1$ and $i$\\
\> \> {\bf endfor}\\
\> {\bf endfor}\\
{\bf endfor}
\end{tabbing}}
\caption{\label{code:1P}Relaxed plan extraction}
\end{figure}

Instead of putting all goals into the top layer in \graphplan\ style,
and then propagating them down by using NOOPs-first, each goal $g$ is
simply put into a goal set $G_i$ located at $g$'s first layer $i$.
Then, there is a for-next loop down from the top to the initial layer.
At each layer $i$, an achieving action with layer membership $i-1$
gets selected for each fact in the corresponding goal set. If there is
more than one such achiever, a best one is picked according to the
difficulty heuristic. The preconditions are put into their
corresponding goal sets. Each time an action is selected, all of its
adds are marked true at times $i$ and $i-1$. The marker at time $i$
prevents achievers to be selected for facts that are already true
anyway. Marking at time $i-1$ assumes that actions are linearized in
the order they get selected: A precondition that was achieved by an
action ahead is not considered as a new goal.






\section{A Novel Variation of Hill-climbing}
\label{search}

In this section, we introduce \ff's base search algorithm. We discuss
the algorithm's theoretical properties regarding completeness, and
derive \ff's overall search strategy.

In the first \hsp\ version \cite{bonet:geffner:aips-ws-98}, \hsp 1 as
was used in the \aips-1998 competition, the search strategy is a
variation of \hc, always selecting one best successor to the state it
is currently facing.  Because state evaluations are costly, we also
chose to use local search, in the hope to reach goal states with as
few evaluations as possible. We settled for a different search
algorithm, an ``enforced'' form of \hc, which combines local and
systematic search.  The strategy is motivated by the simple structure
that the search spaces of our testing benchmarks tend to have.




\subsection{Enforced Hill-climbing}
\label{search:enforced}

Doing planning by heuristic forward search, the search space is the
space of all reachable states, together with their heuristic
evaluation. Now, evaluating states in our testing benchmarks with the
heuristic defined by Equation~\ref{ff-heuristic}, one often finds that
the resulting search spaces are simple in structure, specifically,
that local minima and plateaus tend to be small. For any search state,
the next state with strictly better heuristic evaluation is usually
only a few steps away (an example for this is the {\sl Logistics}
domain described in Section~\ref{performance:competition:logistics}).
Our idea is to perform exhaustive search for the better states. The
algorithm is shown in Figure~\ref{code:ehc}.

\begin{figure}[htb]
{\small
\begin{tabbing}
initialize the current plan to the empty plan $\; <>$\\
$S$ := $\I$\\
{\bf while} \= $h(S) \neq 0$ {\bf do}\\
\> perform breadth first search for a state $S'$ with $h(S') < h(S)$\\
\> {\bf if} \= no such state can be found {\bf then}\\
\> \> output "Fail", stop\\
\> {\bf endif}\\
\> add the actions on the path to $S'$ at the end of the current plan\\
\> $S$ := $S'$\\
{\bf endwhile}
\end{tabbing}}
\caption{\label{code:ehc}The \ehc\ algorithm.}
\end{figure}


Like \hc, the algorithm depicted in Figure~\ref{code:ehc} starts out
in the initial state. Then, facing an intermediate search state $S$, a
complete breadth first search starting out from $S$ is invoked. This
finds the closest better successor, \ie the nearest state $S'$ with
strictly better evaluation, or fails. In the latter case, the whole
algorithm fails, in the former case, the path from $S$ to $S'$ is
added to the current plan, and search is iterated. When a goal
state---a state with evaluation $0$---is reached, search stops.

Our implementation of breadth first search starting out from $S$ is
standard, where states are kept in a queue. One search iteration
removes the first state $S'$ from the queue, and evaluates it by
running \graphplan. If the evaluation is better than that of $S$,
search succeeds. Otherwise, the successors of $S'$ are put to the end
of the queue. Repeated states are avoided by keeping a hash table of
visited states in memory.  If no new states can be reached anymore,
breadth first search fails.





\subsection{Completeness}
\label{search:completeness}


If in one iteration breadth first search for a better state fails,
then \ehc\ stops without finding a solution. This can happen because
once \ehc\ has chosen to include an action in the plan, it never takes
this decision back. The method is therefore only complete on tasks
where no fatally wrong decisions can be made. These are the tasks that
do not contain ``dead ends.''

\begin{def1}[Dead End]\label{deadend}
  Let $(\act,\I,\G)$ be a planning task. A state $S$ is called a {\em
    dead end} iff it is reachable and no sequence of actions achieves
  the goal from it, \ie iff $\exists \; P: \; S = Result(\I,P)$ and
  $\neg \exists \; P': \; \G \subseteq Result(S,P')$.
\end{def1}

Naturally, a task is called dead-end free if it does not contain any
dead end states. We remark that being dead-end free implies solvability,
as otherwise the initial state itself would already be a dead end.

\begin{proposition}\label{ehc-completeness}
  Let $\Poriginal = (\act,\I,\G)$ be a planning task. If
  $\Poriginal$ is dead-end free, then \ehc\ will find a solution.
\end{proposition}

\begin{beweis}
  Assume \ehc\ does not reach the goal. Then we have some intermediate
  state $S = Result(\I,P)$, $P$ being the current plan, where breadth
  first search can not improve on the situation. Now, $h(S) > 0$ as
  search has not stopped yet. If there was a path from $S$ to some
  goal state $S'$, then complete breadth first search would find that
  path, obtain $h(S') = 0 < h(S)$, and terminate positively. Such a
  path can therefore not exist, showing that $S$ is a dead end state
  in contradiction to the assumption.
\end{beweis}


We remark that Proposition~\ref{ehc-completeness} holds only when $h$
is a function from states to natural numbers including $0$, where
$h(S) = 0$ iff $\G \subseteq S$. The proposition identifies a class of
planning tasks where we can safely apply \ehc.  Unfortunately, it is
\pspace-hard to decide whether a given planning task belongs to that
class.

\begin{def1}\label{deadend-prob}
Let \deadend\ denote the following problem:

\bigskip

{\em Given a planning task $\Poriginal = (\act,\I,\G)$, is
  $\Poriginal$ dead-end free?}
\end{def1}

\begin{theorem}\label{deadend-theo}
Deciding \deadend\ is \pspace-complete.
\end{theorem}

\begin{beweis}
  Hardness is proven by polynomially reducing \plansat\ 
  \cite{bylander:ai-94}---the decision problem of whether $\Poriginal$
  is solvable---to the problem of deciding \deadend. We simply add an
  operator to $\act$ that is executable in all states, and
  re-establishes the initial state.
\[
\act_1 := \act \cup \{ o_{I} := \langle \emptyset, \I, \bigcup_{o \in
  \act} \add(o) \setminus \I \rangle \}
\]
Applying $o_{I}$ to any state reachable in $\Poriginal$ leads back to
the initial state: all facts that can ever become true are removed,
and those in the initial state are added. Now, the modified problem
$\Poriginal_1 = (\act_1,\I,\G)$ is dead-end free iff $\Poriginal$ is
solvable. From left to right, if $\Poriginal_1$ is dead-end free, then
it is solvable, which implies that $\Poriginal$ is solvable, as we
have not added any new possibility of reaching the goal. From right to
left, if $\Poriginal$ is solvable, then also is $\Poriginal_1$, by the
same solution plan $P$. One can then, from all states in
$\Poriginal_1$, achieve the goal by going back to the initial state
with the new operator, and executing $P$ thereafter.

Membership in \pspace{} follows from the fact that \plansat\ and its
complement are both in \pspace. A non-deterministic algorithm that
decides the complement of \deadend{} and that needs only polynomial
space can be specified as follows. Guess a state $S$. Verify in
polynomial space that $S$ is reachable from the initial state.
Further, verify that the goal cannot be reached from $S$. If this
algorithm succeeds, it follows that the instance is not dead-end
free---since $S$ constitutes a dead end. This implies that \deadend{}
is in \npspace, and hence in \pspace.
\end{beweis}

Though we can not efficiently decide whether a given task is dead-end
free, there are easily testable sufficient criteria in the literature.
Johnsson et al. \shortcite{jonsson:et:al:ai-00} define a notion of
{\em symmetric} planning tasks, which is sufficient for dead-end
freeness, but \coNP-complete. They also give a polynomial sufficient
criterion for symmetry. This is, however, very trivial. Hardly any of
the current benchmarks fulfills it. Koehler and Hoffmann
\shortcite{koehler:hoffmann:jair-00} have defined notions of {\em
  invertible} planning tasks---sufficient for dead-end freeness, and
{\em inverse actions}---sufficient for invertibility, under certain
restrictions. The existence of inverse actions, and sufficient
criteria for the additional restrictions, can be decided in polynomial
time. Many benchmark tasks do, in fact, fulfill those criteria and can
thus efficiently be proven dead-end free.

One could adopt Koehler and Hoffmann's methodology, and use the
existence of inverse actions to recognize dead-end free tasks. If the
test fails, one could then employ a different search strategy than
\ehc. We have two reasons for {\em not} going this way:

\begin{itemize}
\item Even amongst our benchmarks, there are tasks that do not contain
  inverse actions, but are nevertheless dead-end free. An example is
  the {\sl Tireworld} domain, where \ehc\ leads to excellent results.
\item Enforced hill-climbing can often quite successfully solve tasks
  that do contain dead ends, as it does not necessarily get caught in
  one.  Examples for that are contained in the {\sl Mystery} and {\sl
    Mprime} domains, which we will look at in
  Section~\ref{performance:classical:mystery}.
\end{itemize}

\noindent
The observation that forms the basis for our way of dealing with
completeness is the following. If \ehc\ can not solve a planning task,
it usually fails very quickly. One can then simply switch to a
different search algorithm. We have experimented with randomizing
\ehc, and doing a restart when one attempt failed. This didn't lead to
convincing results. Though we tried a large variety of randomization
strategies, we did not find a planning task in our testing domains
where one randomized restart did significantly better than the
previous one, \ie all attempts suffered from the same problems. The
tasks that \ehc\ does not solve right away are apparently so full of
dead ends that one can not avoid those dead ends at random. We have
therefore arranged our overall search strategy in \ff\ as follows:

\begin{enumerate}
\item Do \ehc\ until the goal is reached or the algorithm fails.
\item If \ehc\ failed, skip everything done so far and try to solve
  the task by a complete heuristic search algorithm. In the current
  implementation, this is what Russel and Norvig
  \shortcite{russel:norvig:95} term {\em greedy best-first} search.
  This strategy simply expands all search nodes by increasing order of
  goal distance estimation.
\end{enumerate}


\noindent
To summarize, \ff\ uses \ehc\ as the base search method, and a
complete best-first algorithm to deal with those special cases where
\ehc\ has run into a dead end and failed.



\section{Pruning Techniques}
\label{pruning}

In this section, we introduce two heuristic techniques that can, in
principle, be used to prune the search space in any forward state
space search algorithm:

\begin{enumerate}
\item {\em Helpful actions} selects a set of promising successors to a
  search state. 
%It is part of \ff's base system architecture. 
  As we will demonstrate in Section~\ref{performance:hsp}, the
  heuristic is crucial for \ff's performance on many domains.
\item {\em Added goal deletion} cuts out branches where some goal has
  apparently been achieved too early. Testing the heuristic, we found
  that it can yield savings on tasks that contain goal orderings, and
  has no effect on tasks that don't.
%  The heuristic is integrated in order to optimize \ff's performance
%  in the presence of goal orderings.
\end{enumerate}

Both techniques are obtained as a side effect of using \graphplan\ as
a heuristic estimator in the manner described in
Section~\ref{heuristic}. Also, both of them do {\em not} preserve
completeness of any hypothetical forward search. In the context of our
search algorithm, we integrate them such that they prune the search
space in the single \ehc\ try---which is not complete in general
anyway---and completely turn them off during \bfs, if \ehc\ failed.




\subsection{Helpful Actions}
\label{pruning:helpful}

To a state $S$, we define a set $H(S)$ of actions that seem to be most
promising among the actions applicable in $S$. The technique is
derived by having a closer look at the relaxed plans that \graphplan\ 
extracts on search states in our testing tasks. Consider the {\sl
  Gripper} domain, as it was used in the 1998 \aips\ planning
competition. There are two rooms, A and B, and a certain number of
balls, which are all in room A initially and shall be moved into room
B. The planner controls a robot, which changes rooms via the {\bf
  move} operator, and which has two grippers to {\bf pick} or {\bf
  drop} balls. Each gripper can hold only one ball at a time. We look
at a small task where $2$ balls must be moved into room B. Say the
robot has already {\bf pick}ed up both balls, \ie in the current
search state, the robot is in room A, and each gripper holds one ball.
There are three applicable actions in this state: {\bf move} to room
B, or {\bf drop} one of the balls back into room A. The relaxed
solution that our heuristic extracts is the following.

\begin{tabbing}
$< \;$ \= $\{ \;$ \= {\bf move} A B $\}$,\\
\> $\{$ \> {\bf drop} ball1 B left,\\
\> \> {\bf drop} ball2 B right $\} \; >$
\end{tabbing}

\noindent
This is a parallel relaxed plan consisting of two time steps. The
action set selected at the first time step contains the only action
that makes sense in the state at hand, {\bf move} to room B. We
therefore pursue the idea of restricting the action choice in any
planning state to only those actions that are selected in the first
time step of the relaxed plan. We call these the actions that seem to
be helpful. In the above example state, this strategy cuts down the
branching factor from three to one.


Sometimes, restricting oneself to only the actions that are selected
by the relaxed planner can be too much. Consider the following {\sl
  Blocksworld} example. Say we use the well known representation with
four operators, {\bf stack}, {\bf unstack}, {\bf pickup} and {\bf
  putdown}.  The planner controls a single robot arm, and the
operators can be used to {\bf stack} one block on top of another one,
{\bf unstack} a block from another one, {\bf pickup} a block from the
table, or {\bf put} a block that the arm is holding {\bf down} onto
the table. Initially, the arm is holding block C, and blocks A and B
are on the table. The goal is to stack A onto B.  Started on this
state, relaxed \graphplan\ will return one out of the following three
time step optimal solutions.

\begin{tabbing}
$< \;$ \= $\{ \;$ \= {\bf putdown} C $\}$,\\
\> $\{$ \> {\bf pickup} A $\}$,\\
\> $\{$ \> {\bf stack} A B $\} \; >$
\end{tabbing}

\noindent
or

\begin{tabbing}
$< \;$ \= $\{ \;$ \= {\bf stack} C A $\}$,\\
\> $\{$ \> {\bf pickup} A $\}$,\\
\> $\{$ \> {\bf stack} A B $\} \; >$
\end{tabbing}

\noindent
or

\begin{tabbing}
$< \;$ \= $\{ \;$ \= {\bf stack} C B $\}$,\\
\> $\{$ \> {\bf pickup} A $\}$,\\
\> $\{$ \> {\bf stack} A B $\} \; >$
\end{tabbing}

\noindent
All of these are valid relaxed solutions, as in the relaxation it does
not matter that {\bf stack}ing C onto A or B deletes facts that we
still need. If C is on A, we can not {\bf pickup} A anymore, and if C
is on B, we can not {\bf stack} A onto B anymore.

The first action in each relaxed plan is only inserted to get rid of
C, \ie free the robot arm, and from the point of view of the relaxed
planner, all of the three starting actions do the job. Thus the
relaxed solution extracted might be any of the three above. If it
happens to be the second or third one, then we lose the path to an
optimal solution by restricting ourselves to the corresponding
actions, {\bf stack} C A or {\bf stack} C B. Therefore, we define the
set $H(S)$ of helpful actions to a state $S$ as follows.

\begin{equation}\label{helpful}
H(S) := \{ o \mid \pre(o) \subseteq S, add(o) \cap G_1(S) \neq
\emptyset \}
\end{equation}

Here, $G_1(S)$ denotes the set of goals that is constructed by
relaxed \graphplan\ at time step 1---one level ahead of the initial
layer---when started on the task $(\actrelaxed, S, \G)$.  In words, we
consider as helpful actions all those applicable ones, which add at
least one goal at the first time step. In the above {\sl Blocksworld}
example, freeing the robot arm is among these goals, which causes all
the three starting actions to be helpful in the initial state, \ie to
be elements of $H(\I)$. In the above {\sl Gripper} example, the
modification does not change anything.



The notion of helpful actions shares some similarities with what Drew
McDermott calls the {\em favored actions}
\cite{mcdermott:aips-96,mcdermott:ai-99}, in the context of computing
{\em greedy regression graphs} for heuristic estimation. In a
nutshell, greedy regression graphs backchain from the goals until
facts are reached that are contained in the current state. Amongst
other things, the graphs provide an estimation of which actions might
be useful in getting closer to the goal: Those applicable ones which
are members of the {\em effective subgraph}, which is the minimal cost
subgraph achieving the goals.


There is also a similarity between the helpful actions heuristic and
what is known as {\em relevance} from the literature
\cite{nebel:et:al:ecp-97}. Consider a {\sl Blocksworld} task where
hundreds of blocks are on the table initially, but the goal is only to
stack one block A on top of another block B. The set $H(\I)$ will in
this case contain only the single action {\bf pickup} A, throwing away
all those applicable actions moving around blocks that are not
mentioned in the goal, \ie throwing away all those actions that are
irrelevant. The main difference between the helpful actions heuristic
and the concept of relevance is that relevance in the usual sense
refers to what is useful for solving the whole task. Being helpful, on
the other hand, refers to something that is useful {\em in the next
  step}. This has the disadvantage that the helpful things need to be
recomputed for each search state, but the advantage that possibly far
less things are helpful than are relevant. In our specific setting, we
get the helpful actions for free anyway, as a side effect of running
relaxed \graphplan.



We conclude this subsection with an example showing that helpful
actions pruning does {\em not} preserve completeness, and a few
remarks on the current integration of the technique into our search
algorithm.


\subsubsection{Completeness}
\label{pruning:helpful:completeness}

In the following short example, the helpful actions heuristic prunes
out all solutions from the state space. Say the initial state is $\{ B
\}$, the goals are $\{ A, B \}$, and there are the following actions:


\begin{center}
\begin{tabular}{lrrrr}
name         &   &  $(\pre,$     &   $\add,$     &   $\del)$
\vspace{0.15cm}\\
{\bf op$A_1$} & =  &  $(\emptyset,$     & $\{ A \},$     & $\{ B \})$  \vspace{0.1cm} \\
{\bf op$A_2$} & =  &  $(\{ P_A \},$     &  $\{ A \},$    & $\emptyset)$  \vspace{0.1cm} \\
{\bf op$P_A$} & =  &  $(\emptyset,$     &  $\{ P_A \},$  & $\emptyset)$ \vspace{0.1cm} \\
{\bf op$B_1$} & =  &  $(\emptyset,$     &  $\{ B \},$    & $\{ A \})$  \vspace{0.1cm} \\
{\bf op$B_2$} & =  &   $(\{ P_B \},$    &   $\{ B \},$   & $\emptyset)$ \vspace{0.1cm} \\
{\bf op$P_B$} & =  &  $(\emptyset,$     &   $\{ P_B \},$ & $\emptyset)$          
\vspace{0.0cm} \\
\end{tabular}
\end{center}

\noindent
In this planning task, there are two ways of achieving the missing
goal $A$. One of these, {\bf op$A_1$}, deletes the other goal $B$. The
other one, {\bf op$A_2$}, needs the precondition $P_A$ to be achieved
first by {\bf op$P_A$}, and thus involves using {\em two} planning
actions instead of {\em one} in the first case.  Relaxed \graphplan\ 
recognizes only the first alternative, as it's the only time step
optimal one. The set of goals at the single time step created by graph
construction is
\[
G_1(\I) = \{ \; A, B \; \}
\]
This gives us two helpful actions, namely
\[
H(\I) = \{ \; \mbox{{\bf op$A_1$}}, \mbox{{\bf op$B_1$}} \; \}
\]
One of these, {\bf op$B_1$}, does not cause any state transition in
the initial state. The other one, {\bf op$A_1$}, leads to the state
where only $A$ is true. To this state, we obtain the same set of
helpful actions, containing, again, {\bf op$A_1$} and {\bf op$B_1$}.
This time, the first action causes no state transition, while the
second one leads us back to the initial state. Helpful actions thus
cuts out the solutions from the state space of this example task. We
remark that the task is dead-end free---one can always reach $A$ and
$B$ by applying {\bf op$P_A$}, {\bf op$A_2$}, {\bf op$P_B$}, and {\bf
  op$B_2$}---and that one can easily make the task invertible without
changing the behavior.



In \strips\ domains, one could theoretically overcome the
incompleteness of helpful actions pruning by considering not only the
first relaxed plan that \graphplan\ finds, but computing a kind of
union over all relaxed plans that \graphplan\ could possibly find,
when allowing non time step optimal plans. More precisely, in a search
state $S$, consider the relaxed task $(\actrelaxed, S, \G)$. Extend
the relaxed planning graph until fact level $|\actrelaxed|$ is
reached. Set a goal set $G_{|\actrelaxed|}$ at the top fact level to
$G_{|\actrelaxed|} := \G$.  Then, proceed from fact level
$|\actrelaxed| - 1$ down to fact level $1$, where, at each level $i$,
a set $G_i$ of goals is generated as the union of $G_{i+1}$ with the
preconditions of all actions in level $i$ that add at least one fact
in $G_{i+1}$. Upon termination, define as helpful all actions that add
at least one fact in $G_1$. It can be proven that, this way, the
starting actions of all optimal solutions from $S$ are considered
helpful. However, in all our \strips\ testing domains, the complete
method always selects {\em all} applicable actions as helpful.


%NOCHMAL GENAU UEBERLEGEN, ODER UNEXAKTER MACHEN
%One can overcome the incompleteness of helpful actions pruning by
%considering not only the {\em first} relaxed plan that \graphplan\ 
%finds, but computing a kind of union over {\em all} relaxed plans that
%\graphplan\ {\em could} possibly find. Precisely, facing a search
%state $S$, consider the relaxed task $(\actrelaxed, S, \G)$. Extend
%the relaxed planning graph until fact layer $max := |\actrelaxed| -
%|\{o \in \actrelaxed \mid \pre(o) \subseteq S \}| + 1$ is reached. At
%each fact layer $i$, $1 \leq i \leq max$, initialize a set of facts
%$G_i$ to the intersection of $\G$ with the facts that are present in
%fact layer $i$. Then, proceed from layer $max - 1$ down to layer $1$.
%At each layer $i$, put into $G_i$ the preconditions of all actions in
%layer $i$ that add at least one fact in $G_{i+1}$. Upon termination,
%define as helpful all actions that add at least one fact in $G_1$. It
%can be proven that, this way, any starting action of any optimal
%solution from $S$ is considered helpful. Also, the process takes only
%polynomial time, by the same argument that is used in the proof to
%Theorem~\ref{graphplan:polynomial}. However, in our experiments, we
%found that, in $14$ out of $16$ \strips\ domains we tried, the
%complete method always selects {\em all} applicable actions as
%helpful. We therefore did not integrate it into the \ff\ system.



\subsubsection{Integration into Search}
\label{pruning:helpful:search}

As has already been noted at the very beginning of this section, we
integrate helpful actions pruning into our search algorithm by only
applying it during the single \ehc\ try, leaving the complete \bfs\ 
algorithm unchanged (see Section~\ref{search}). Facing a state $S$
during breadth first search for a better state in \ehc, we look only
at those successors generated by $H(S)$. This renders our
implementation of \ehc\ incomplete even on invertible planning tasks.
However, in all our testing domains, the tasks that cannot be solved
by \ehc\ using helpful actions pruning are exactly those that cannot
be solved by \ehc\ anyway.







\subsection{Added Goal Deletion}
\label{pruning:orderings}

The second pruning technique that we introduce in this section is
motivated by the observation that in some planning domains there are
goal ordering constraints, as has been recognized by quite a number of
researchers in the past
\cite{irani:cheng:ijcai-87,drummond:currie:ijcai-89,joslin:roach:ai-89}.
In our experiments on tasks with goal ordering constraints, \ff's base
architecture sometimes wasted a lot of time achieving goals that
needed to be cared for later on. We therefore developed a heuristic to
inform search about goal orderings. 


The classical example for a planning domain with goal ordering
constraints is the well known {\sl Blocksworld}. Say we have three
blocks A, B and C on the table initially, and want to stack them such
that we have B on top of C, and A on top of B. Obviously, there is not
much point in stacking A on B first. Now, imagine a forward searching
planner confronted with a search state $S$, where some goal $G$ has
just been achieved, \ie $S$ resulted from some other state by applying
an action $o$ with $G \in \add(o)$. What one can ask in a situation
like this is, was it a good idea to achieve $G$ right now? Or should
some other goal be achieved first? Our answer is inspired by recent
work of Koehler and Hoffmann \shortcite{koehler:hoffmann:jair-00},
which argues that achieving $G$ should be postponed if the remaining
goals can not be achieved without destroying $G$ again. Of course,
finding out about this involves solving the remaining planning task.
However, we can arrive at a very simple but---in our testing
domains---surprisingly accurate approximation by using the relaxed
plan that \graphplan\ generates for the state $S$. The method we are
using is as simple as this: If the relaxed solution plan, $P$, that
\graphplan\ generates for $S$, contains an action $o$, $o \in P$, that
deletes $G$ ($G \in \del(o)$ in $o$'s non-relaxed version), then we
remove $S$ from the search space, \ie do not generate any successors
to $S$. We call this method the {\em added goal deletion} heuristic.


Let us exemplify the heuristic with the above {\sl Blocksworld}
example. Say the planner has just achieved $on($A,B$)$, but with
$on($B,C$)$ still being false, \ie we are in the situation where A is
on top of B, and B and C are standing on the table. The relaxed
solution that \graphplan\ finds to this situation is the following.

\begin{tabbing}
$< \;$ \= $\{ \;$ \= {\bf unstack} A B $\}$,\\
\> $\{$ \> {\bf pickup} B $\}$,\\
\> $\{$ \> {\bf stack} B C $\} \; >$
\end{tabbing}

\noindent
The goal $on($A,B$)$, which has just been achieved, gets deleted by
the first action {\bf unstack} A B. Consequently, we realize that {\bf
  stack}ing A onto B right now was probably a bad idea, and prune this
possibility from the search space, which results in a solution plan
that {\bf stack}s B onto C first.

Like in the preceding subsection, we conclude with an example showing
that pruning search states in the manner described above does not
preserve completeness, and with a few remarks on our current search
algorithm implementation.


\subsubsection{Completeness}
\label{pruning:orderings:completeness}

In the following small example, one of the goals {\em must} be
destroyed temporarily in order to achieve the other goal. This renders
the planning task unsolvable when one is using the added goal deletion
heuristic. Say the initial state is empty, the goals are $\{ A, B \}$,
and there are the following actions:

\begin{center}
\begin{tabular}{lrrrr}
name         &   &  $(\pre,$     &   $\add,$     &   $\del)$
\vspace{0.15cm}\\
{\bf op$A$} & =  & $(\emptyset,$    & $\{ A \},$  &  $\emptyset)$ \vspace{0.1cm} \\
{\bf op$B$}   & =  & $(\{ A \},$  &  $\{ B \},$   &  $\{ A \})$
\vspace{0.0cm} \\
\end{tabular}
\end{center}

\noindent
All solutions to this task need to apply {\bf op$A$}, use {\bf op$B$}
thereafter, and re-establish $A$. The crucial point here is that $A$
{\em must} be temporarily destroyed. The added goal deletion heuristic
is not adequate for such planning tasks. The example is dead-end free,
and one can easily make the scenario invertible without changing the
behavior of the heuristic.

Unlike for helpful actions, completeness can not be regained by
somehow enumerating all relaxed plans to a situation. In the above
example, when $A$ has been achieved but $B$ is still \false, then all
relaxed plans contain {\bf op$B$}, deleting $A$.




\subsubsection{Integration into Search}
\label{pruning:orderings:search}

We use the added goal deletion heuristic in a way similar to the
integration of the helpful actions heuristic. As indicated at the very
beginning of the section, it is integrated into the single \ehc\ try
that search does, and completely turned off during \bfs, in case \ehc\ 
didn't make it to the goal.

We also use another goal ordering technique, taken from the
literature. One of the most common approaches to dealing with goal
orderings is trying to recognize them in a preprocessing phase, and
then use them to prune fractions of the search space during planning
\cite{irani:cheng:ijcai-87,cheng:irani:ijcai-89,joslin:roach:ai-89}.
This is also the basic principle underlying the so-called ``goal
agenda'' approach \cite{koehler:aips-98}. For our system, we have
implemented a slightly simplified version of the goal agenda
algorithm, and use it to further enhance performance. A very short
summary of what happens is this. In a preprocessing phase, the planner
looks at all pairs of goals and decides heuristically whether there is
an ordering constraint between them.  Afterwards, the goal set is
split into a totally ordered series of subsets respecting these
orderings. These are then fed to \ehc\ in an incremental manner.
Precisely, if $G_1, \dots, G_n$ is the ordered series of subsets,
\ehc\ gets first started on the original initial state and $G_1$. If
that works out, search ends in some state $S$ satisfying the goals in
$G_1$. Enforced hill-climbing is then called again on the new starting
state $S$ and the larger goal set $G_1 \cup G_2$. From a state
satisfying this, search gets started for the goals $G_1 \cup G_2 \cup
G_3$, and so on.  The incremental, or {\em agenda-driven}, planning
process can be applied to any planner, in principle, and preserves
completeness only on dead-end free tasks
\cite{koehler:hoffmann:jair-00}, \ie again, we have an enhancement
that loses completeness in general. Thus, we use the goal agenda only
in \ehc, leaving the complete \bfs\ phase unchanged.

The goal agenda technique yields runtime savings in domains where
there are ordering constraints between the goals. In our testing
suite, these are the {\sl Blocksworld} and the {\em Tireworld}. In
planning tasks without ordering constraints, the series of subsets
collapses into a single entry, such that the agenda mechanism does not
change anything there. The runtime taken for the pre-process itself
was neglectible in all our experiments.





\section{Extension to \adl}
\label{adl}

So far, we have restricted ourselves to planning tasks specified in
the simple \strips\ language. We will now show how our approach can be
extended to deal with \adl\ \cite{pednault:kr-89} tasks, more
precisely, with the \adl\ subset of \pddl\ \cite{pddl-handbook} that
was used in the 2nd international planning systems competition
\cite{pddl-2000-subset}. This involves dealing with arbitrary
function-symbol free first order logic formulae, and with conditional
effects. Our extension work is divided into the following four
subareas:

\begin{enumerate}
\item Apply a preprocessing approach to the \adl\ domain and task
  description, compiling the specified task down into a
  propositional normal form.
\item Extend the heuristic evaluation of planning states to deal with
  these normal form constructs.
\item Adjust the pruning techniques.
\item Adjust the search mechanisms.
\end{enumerate}





\subsection{Preprocessing an \adl\ Planning Task}
\label{adl:preprocessing}


\ff's preprocessing phase is almost identical to the methodology that
has been developed for the \ipp\ planning system. For details, we
refer the reader to the work that's been done there
\cite{koehler:hoffmann:ecai-ws-00}, and give only the basic principles
here.

The planner starts with a planning task specification given in the
subset of \pddl\ defined for the \aips-2000 planning competition
\cite{pddl-2000-subset}. The input is a set of operator schemata, the
initial state, and a goal formula. The initial state is simply a set
of ground atoms, and the goal formula is an arbitrary first order
logical formula using the relational symbols defined for the planning
task. Any operator schema $o$ is defined by a list of parameters, a
precondition, and a list of effects.  Instantiating the parameters
yields, just like \strips\ tasks are usually specified, the actions to
the schema. The precondition is an arbitrary (first order) formula.
For an action to be applicable in a given state $S$, its instantiation
of this formula must be satisfied in $S$. Each effect $i$ in the list
has the form
\[
\forall y_0^i, \dots, y_{n^i}^i: ( \psi^i(o), \add^i(o),
\del^i(o) )
\]
Here, $y_0^i, \dots, y_{n^i}^i$ are the effect parameters, $\psi^i(o)$
is the effect condition---again, an arbitrary formula---and
$\add^i(o)$ and $\del^i(o)$ are the atomic add and delete effects,
respectively. The atomic effects are sets of uninstantiated atoms, \ie
relational symbols containing variables. The semantics are that, if an
instantiated action is executed, then, for each single effect $i$ in
the list, and for each instantiation of its parameters, the condition
$\psi^i(o)$ is evaluated. If $\psi^i(o)$ holds in the current state,
then the corresponding instantiations of the atoms in $\add^i(o)$ are
added to the state, and the instantiations of atoms in $\del^i(o)$ are
removed from the state.


In \ff's heuristic method, each single state evaluation can involve
thousands of operator applications---building the relaxed planning
graph, one needs to determine all applicable actions at each single
fact layer. We therefore invest the effort to compile the operator
descriptions down into a much simpler propositional normal form, such
that heuristic evaluation can be implemented efficiently. Our final
normal form actions $o$ have the following format.

\begin{tabbing}
Precondition: \= $\pre(o)$\\
Effects: \> $( \pre^0(o), \add^0(o), \del^0(o) ) \; \; \wedge$\\
\> $( \pre^1(o), \add^1(o), \del^1(o) ) \; \; \wedge$\\
\> .\\
\> .\\
\> .\\
\> $( \pre^m(o), \add^m(o), \del^m(o) )$
\end{tabbing}

The precondition is a set of ground atoms. Likewise, the effect
conditions $\pre^i(o)$ of the single effects are restricted to be
ground atoms. We also represent the goal state as a set of atoms.
Thus, we compile away everything except the conditional effects.
Compiling away the logical formulae involves transforming them into
DNF, which causes an exponential blow up in general. In our testing
domains, however, we found that this transformation can be done in
reasonable time. Concerning the conditional effects, those can not be
compiled away without another exponential blow up, given that we want
to preserve solution length. This was proven by Nebel
\shortcite{nebel:jair-00}. As we will see, conditional effects can
efficiently be integrated into our algorithmic framework, so there is
no need for compiling them away. The compilation process proceeds as
follows:

\begin{enumerate}
\item Determine predicates that are {\em static}, in the sense that no
  operator has an effect on them. Such predicates are a common
  phenomenon in benchmark tasks. An example are the $(\mbox{in-city}
  \; ?l \; ?c)$ facts in {\sl Logistics} tasks: Any location $?l$
  stays, of course, located within the same city $?c$ throughout the
  whole planning process. We recognize static predicates by a simple
  sweep over all operator schemata.
\item Transform all formulae into quantifier-free DNF. This is
  subdivided into three steps:
\begin{enumerate}
\item Pre-normalize all logical formulae. Following Gazen and Knoblock
  \shortcite{gazen:knoblock:ecp-97}, this process expands all
  quantifiers, and translates negations. We end up with formulae that
  are made up out of conjunctions, disjunctions, and atoms containing
  variables.
\item Instantiate all parameters. This is simply done by instantiating
  all operator and effect parameters with all type consistent
  constants one after the other. The process makes use of knowledge
  about static predicates, in the sense that the instantiated formulae
  can often be simplified \cite{koehler:hoffmann:ecai-ws-00}. For
  example, if an instantiated static predicate $(p \; \vec{a})$ occurs
  in a formula, and that instantiation is {\em not} contained in the
  initial state, then $(p \; \vec{a})$ can be replaced with \false.
\item Transform formulae into DNF. This is postponed until after
  instantiation, because it can be costly, so it should be applied to
  as small formulae as possible. In a fully instantiated formula, it
  is likely that many static or one-way predicate occurrences can be
  replaced by \true\ or \false, resulting in a much simpler formula
  structure.
\end{enumerate}
\item Finally, if the DNF of any formula contains more than one
  disjunct, then the corresponding effect, operator, or goal condition
  gets split up in the manner proposed by Gazen and Knoblock
  \shortcite{gazen:knoblock:ecp-97}.
\end{enumerate}







\subsection{Relaxed \graphplan\ with Conditional Effects} 
\label{adl:heuristic}

We now show how our specialized \graphplan\ implementation, as was
described in Section~\ref{heuristic:implementation}, is changed to
deal with \adl\ constructs. Building on our normalized task
representation, it suffices to take care of conditional effects.



\subsubsection{Relaxed Planning Graphs with Conditional Effects}
\label{adl:heuristic:graph}

Our encoding of planning graph building for relaxed tasks almost
immediately carries over to \adl\ actions in the above propositional
normal form. One simply needs to keep an additional layer membership
value for all {\em effects} of an action. The layer membership of an
effect indicates the first layer where all its effect conditions plus
the corresponding action's preconditions are present. To compute these
membership integers in an efficient manner, we keep a counter for each
effect $i$ of an action $o$, which gets incremented each time a
condition $c \in \pre^i(o)$ becomes present, {\em and} each time a
precondition $p \in \pre(o)$ of the corresponding action becomes
present. The effect gets its layer membership set as soon as its
counter reaches $|\pre^i(o)| + |\pre(o)|$. The effect's add effects
$\add^i(o)$ are then scheduled for the next layer. The process is
iterated until all goals are reached the first time.



\subsubsection{Relaxed Plan Extraction with Conditional Effects}
\label{adl:heuristic:plan}


The relaxed plan extraction mechanism for \adl\ differs from its
\strips\ counterpart in merely two little details. Instead of
selecting achieving actions, the extraction mechanism selects
achieving effects. Once an effect $i$ of action $o$ is selected, all
of its effect conditions plus $o$'s preconditions need to be put into
their corresponding goal sets. Afterwards, not only the effect's own
add effects $\add^i(o)$ are marked \true\ at the time being, but also
the added facts of all effects that are {\em implied}, \ie those
effects $j$ of $o$ with $\pre^j(o) \subseteq \pre^i(o)$ (in
particular, this will be the unconditional effects of $o$, which have
an empty effect condition).


\subsection{\adl\ Pruning Techniques}
\label{adl:pruning}

Both pruning techniques from Section~\ref{pruning} easily carry over
to actions with conditional effects.


\subsubsection{Helpful Actions}
\label{adl:pruning:helpful}

For \strips, we defined as helpful all applicable actions achieving at
least one goal at time step $1$, cf. Section~\ref{pruning:helpful}.
For our \adl\ normal form, we simply change this to {\em all
  applicable actions having an appearing effect that achieves a goal
  at time step $1$}, where an effect {\em appears} iff its effect
condition is satisfied in the current state.

\begin{equation}\label{helpful-adl}
H(S) := \{ o \mid \pre(o) \subseteq S, \exists i: \pre^i(o) \subseteq S
\wedge \add^i(o) \cap G_1(S) \neq \emptyset \}
\end{equation}




\subsubsection{Added Goal Deletion}
\label{adl:pruning:orderings}

Originally, we cut off a state $S$ if one of the {\em actions}
selected for the relaxed plan to $S$ deleted a goal $A$ that had just
been achieved, cf. Section~\ref{pruning:orderings}. We now simply take
as criterion the {\em effects} that are selected for the relaxed plan,
\ie a state is cut off if one of the effects selected for its relaxed
solution deletes a goal $A$ that has just been achieved.





\subsection{\adl\ State Transitions}
\label{adl:search}

Finally, for enabling the search algorithms to handle our
propositional \adl\ normal form, it is sufficient to redefine the {\em
  state transition function}. Forward search, no matter if it does
\hc, \bfs, or whatsoever, always faces a completely specified search
state.\footnote{This holds if the initial state is completely
  specified and all actions are deterministic, which we both assume.}
It can therefore compute exactly the effects of executing a context
dependent action. Following Koehler et
al.\shortcite{koehler:et:al:ecp-97}, we define our \adl\ state
transition function $Res$, mapping states and \adl\ normal form
actions to states, as follows.
\[
Res(S,o) = \left\{ \begin{array}[]{ll}
    \big(S \cup A(S,o)\big) \setminus D(S,o) & \mbox{if } \pre(o) \subseteq S\\
    \mbox{undefined}                              & \mbox{otherwise} \end{array} 
\right.
\]
with 
\[ 
A(S,o) = \bigcup_{\pre^i(o) \subseteq S} \add^i(o)
\hspace*{2cm} \mbox{and} \hspace*{2cm} 
D(S,o) = \bigcup_{\pre^i(o) \subseteq S} \del^i(o) \enspace .
\]






\section{Performance Evaluation}
\label{performance}

We have implemented the methodology presented in the preceding
sections in {\sf C}.\footnote{The source code is publicly available
  via the \ff\ Homepage at http://www.informatik.uni-freiburg.de/{\~\ 
    }hoffmann/ff.html.} In this section, we evaluate the performance
of the resulting planning system. 
%Empirical data is shown for our
%testing domains, and for domains not seen during development. Remember
%that our testing domains were {\sl Blocksworld}, {\sl Hanoi}, {\sl
%  Tireworld}, and all domains from the \aips-1998 competition ({\sl
%  Assembly}, {\sl Grid}, {\sl Gripper}, {\sl Logistics}, {\sl Movie},
%{\sl Mprime}, and {\sl Mystery}). 
Empirical data is divided into three subareas:

%present empirical data in
%favor of the claim that \ff, when started on solvable benchmark
%planning tasks, does usually generate plans fast, as the paper title
%suggests. We are also concerned with looking at the length of the
%plans found---in terms of number of actions---, to demonstrate that
%\ff, while not guaranteeing the plans to be optimal, still finds very
%close to optimal plans in most cases. The data is divided into three
%subareas.

\begin{enumerate}
\item The \ff\ system took part in the fully automated track of the
  2nd international planning systems competition, carried out
  alongside with \aips-2000 in Breckenridge, Colorado. We review the
  results, demonstrating \ff's good runtime and solution length
  behavior in the competition. We also give some intuitions on why
  \ff\ behaves the way it does.
\item From our own experiments, we present some of the results that we
  have obtained in domains that were not used in the \aips-2000
  competition. First, we briefly summarize our findings in some more
  domains where \ff\ works well. Then, to illustrate our intuitions on
  the reasons for \ff's performance, we give a few examples of domains
  where the approach is less appropriate.
\item We finally present a detailed comparison of \ff's performance to
  that of \hsp, in the sense that we investigate which differences
  between \ff\ and \hsp\ lead to which performance results.
\end{enumerate} 



\subsection{The \aips-2000 Planning Systems Competition}
\label{performance:competition}

From March to April 2000, the 2nd international planning systems
competition, organized by Fahiem Bacchus, was carried out in the
general setting of the \aips-2000 conference in Breckenridge,
Colorado. There were two main tracks, one for fully-automated
planners, and one for hand-tailored planners. Both tracks were divided
into five parts, each one concerned with a different planning domain.
Our \ff\ system took part in the fully automated track. In the
competition, \ff\ demonstrated runtime behavior superior to that of
the other fully automatic planners and was therefore granted ``Group A
distinguished performance Planning System'' \cite{bacchus:nau:aim-01}.
It also won the Schindler Award for the first place in the Miconic 10
Elevator domain, \adl\ track. In this section, we briefly present the
data collected in the fully automated track, and give, for each
domain, some intuitions on the reasons for \ff's behavior. The reader
should be aware that the competition made no distinction between
optimal and suboptimal planners, putting together the runtime curves
for both groups. In the text to each domain, we state which planners
found optimal solutions, and which didn't. Per planning task, all
planners were given half an hour running time on a 500 MHz Pentium III
with 1GB main memory. If no solution was found within these resource
bounds, the planner was declared to have failed on the respective
task.


\subsubsection{The {\sl Logistics} Domain}
\label{performance:competition:logistics}

The first two domains that were used in the competition were the {\sl
  Logistics} and {\sl Blocksworld} domains. We first look at the
former. This is a classical domain, involving the transportation of
packets via trucks and airplanes. Figure~\ref{eps/log_t.eps} shows the
runtime curves of those planners that were able to scale to bigger
instances in the competition.

%figure
\scalefig{1.0}{eps/log_t.eps}{Runtime curves on large {\sl Logistics}
  instances for those six planners that could scale up to them. Time
  is shown on a logarithmic scale.}

The {\sl Logistics} tasks were subdivided into two sets of instances,
the easy and the harder ones. Those planners that did well on all of
the easy instances were also run on the harder set. These planners
were \ff, \hsp 2 \cite{bonet:geffner:aips-ws-98,bonet:geffner:ecp-99},
\systemr, \grt\ \cite{refanidis:vlahavas:ecp-99}, \mips\ 
\cite{edelkamp:ecai-ws-00}, and \stan\ 
\cite{long:fox:jair-99,fox:long:ijcai-01}. Two observations can be
made:

\begin{enumerate}
\item \systemr\ does significantly worse than the other planners.
\item The better planners all behave quite similar, with \ff\ and
  \mips\ tending to be the fastest.
\end{enumerate}

Note also that times are shown on a logarithmic scale, so we are {\em
  not} looking at linear time {\sl Logistics} planners. Concerning
solution plan length, we do not show a figure here. None of the shown
planners guarantees the returned plans to be optimal. It turns out
that \stan\ finds the shortest plans on most instances. \systemr\ 
finds significantly longer plans than the others, ranging from $178\%$
to $261\%$ of \stan's plan lengths, with an average of $224\%$. The
lengths of \ff's plans are within $97\%$ to $115\%$ of \stan's plan
lengths, with an average length of $105\%$. Concerning \ff's good
runtime behavior, we think that there are mainly two reasons for that:

\begin{enumerate}
\item In all iterations of \ehc, breadth first search finds a state
  with better evaluation at very small depths (motivating our search
  algorithm, cf. Section~\ref{search:enforced}). In most cases, the
  next better successor is at depth $1$, \ie a direct one. There are
  some cases where the shallowest better successor is at depth $2$,
  and only very rarely breadth first needs to go down to depth $3$.
  These observations are independent of task size.
\item The helpful actions heuristic prunes large fractions of the
  search space. Looking at the states that \ff\ encounters during
  search, only between $40$ and $5$ percent of all of a state's
  successors were considered helpful in our experiments, with the
  tendency that the larger the task, the less helpful successors there
  are.
\end{enumerate}

There is a theoretical note to be made on the first observation. With
the common representation of {\sl Logistics} tasks, the following can
be proven. Let $d$ be the maximal distance between two locations, \ie
the number of move actions a mobile needs to take to get from one
location to another. Using a heuristic function that assigns to each
state the length of an {\em optimal} relaxed solution as the heuristic
value, the distance of each state to the next better evaluated state
is maximal $d + 1$. Thus, an algorithm that used \ehc\ with an oracle
function returning the length of an optimal relaxed solution would be
polynomial on standard {\sl Logistics} representations, given an upper
limit to $d$. In the benchmarks available, mobiles can reach any
location accessible to them in just one step, \ie the maximal distance
in those tasks is constantly $d = 1$. Also, \ff's heuristic usually
{\em does} find optimal, or close to optimal, relaxed solutions there,
such that \ehc\ almost never needs to look more than $d + 1 = 2$ steps
ahead.



\subsubsection{The {\sl Blocksworld} Domain}
\label{performance:competition:blocksworld}

The {\sl Blocksworld} is one of the best known benchmark planning
domains, where the planner needs to rearrange a bunch of blocks into a
specified goal position, using a robot arm. Just like the {\sl
  Logistics} tasks, the competition instances were divided into a set
of easier, and of harder ones. Figure~\ref{eps/blo_t.eps} shows the
runtime curves of the planners that scaled to the harder ones.

%figure
\scalefig{1.0}{eps/blo_t.eps}{Runtime curves on large {\sl
    Blocksworld} instances for those three planners that could scale
  up to them: \ff, \hsp 2, and \systemr. Time is shown an a
  logarithmic scale.}

\systemr\ scales most steadily to the {\sl Blocksworld} tasks used in
the competition. In particular, it is the only planner that can solve
{\em all} of those tasks. \hsp 2 solves some of the smaller instances,
and \ff\ solves about two thirds of the set. If \ff\ succeeds on an
instance, then it does so quite fast. For example, \ff\ solves one of
the size-$50$ tasks in $1.27$ seconds, where \systemr\ needs $892.31$
seconds. None of the three planners finds optimal plans. On the tasks
that \hsp 2 manages to solve, its plans are within $97\%$ to $177\%$
of \systemr's plan lengths, with an average of $153\%$. On the tasks
that \ff\ manages to solve, its plans are within $83\%$ to $108\%$ of
\systemr's plan lengths, average $96\%$.

By experimenting with different configurations of \ff, we found that
the behavior of \ff\ on these tasks is largely due to the goal
ordering heuristics from Section~\ref{pruning:orderings}. Goal
distance estimates are not so good---the planner grabs a whole bunch
of blocks with its single arm---and neither is the helpful actions
heuristic---when the arm holds a block, all positions where the arm
could possibly put the block are usually considered helpful. The goal
agenda (Section~\ref{pruning:orderings:search}), on the other hand,
divides the tasks into small subtasks, and added goal deletion
(Section~\ref{pruning:orderings}) prevents the planner from putting
blocks onto stacks where some block beneath still needs to be moved.
However, in some cases achieving the goals from earlier entries in the
goal agenda cuts off goals that are still ahead. Not aware of the
blocks that it will need to stack for achieving goals ahead, the
planner might put the current blocks onto stacks that need to be
disassembled later on. If that happens with too many blocks---which
depends more or less randomly on the specific task and the actions
that the planner chooses---then the planner can not find its way out
of the situation again. These are probably the instances that \ff\ 
couldn't solve in the competition.



\subsubsection{The {\sl Schedule} Domain}
\label{performance:competition:schedule}

In the {\sl Schedule} domain, the planner is facing a bunch of objects
to be worked on with a set of machines, \ie the planner is required to
create a job schedule in which the objects shall be assigned to the
machines. The competition representation makes use of a simple form of
quantified conditional effects. For example, if an object gets painted
red, then that is its new color, and for all colors that it is
currently painted in, it is not of that color anymore. Only a subset
of the planners in the competition could handle this kind of
conditional effects. Their runtime curves are shown in
Figure~\ref{eps/sch_t.eps}.

%figure
\scalefig{1.0}{eps/sch_t.eps}{Runtime curves on {\sl Schedule}
  instances for those planners that could handle conditional effects.
  Time is shown on a logarithmic scale.}

Apart from those planners already seen, we have runtime curves in
Figure~\ref{eps/sch_t.eps} for \ipp\ \cite{koehler:et:al:ecp-97},
\propplan, and \bddplan\ \cite{hoelldobler:stoerr:cl-00}. \ff\ 
outperforms the other planners by many orders of magnitude---remember
that time is shown on a logarithmic scale. Concerning solution length,
\ff's plans tend to be slightly longer than the plans returned by the
other planners on the smaller instances. Optimal plans are found by
\mips, \propplan, and \bddplan. \ff's plan lengths are within $175\%$
of the optimal lengths, with an average of $116\%$. Only \hsp\ 
sometimes finds longer plans than \ff, being in a range from $62\%$ to
$117\%$ of \ff's plan lengths, $94\%$ on average.

Responsible for the outstanding runtime behavior of \ff\ on the {\sl
  Schedule} domain is, apparently, the helpful actions heuristic.
Measuring, for some example states, the percentage of successors that
were considered helpful, we usually found it was close to $2$ percent,
\ie only two out of a hundred applicable actions were considered by
the planner. For example, all of the $637$ states that \ff\ looks at
for solving one of the size-$50$ tasks have $523030$ successors
altogether, where the sum of all {\em helpful} successors is only
$7663$. Also, the better successors, similar to the {\sl Logistics}
domain, lie at shallow depths. Breadth first search never goes deeper
than three steps on the {\sl Schedule} tasks in the competition suite.
Finally, in a few experiments we ran for testing that, the goal agenda
helped by about a factor $2$ in terms of running time.



\subsubsection{The {\sl Freecell} Domain}
\label{performance:competition:freecell}

The {\sl Freecell} domain formalizes a solitaire card game that comes
with Microsoft Windows. The largest tasks entered in the competition
(size $13$ in Figure~\ref{eps/fre_t.eps}) correspond directly to some
real-world sized tasks, while in the smaller tasks, there are less
cards to be considered. Figure~\ref{eps/fre_t.eps} shows the runtime
curves of the four best performing planners.

%figure
\scalefig{1.0}{eps/fre_t.eps}{Runtime curves on {\sl Freecell}
  tasks for those planners that scaled to bigger instances. Time is
  shown on a logarithmic scale.}

From the group of the four best-scaling planners shown in
Figure~\ref{eps/fre_t.eps}, \hsp 2 is the slowest, while \stan\ is the
fastest planner. \ff\ is generally second place, and has a lot of
variation in its running times. On the other hand, \ff\ is the only
planner that is capable of solving the real-world tasks, size $13$.
It solves four out of five such tasks.  None of the shown planners
guarantees the found plans to be optimal, and none of the shown
planners demonstrates superior performance concerning solution length.
\stan\ produces unnecessarily long plans in a few cases. Precisely, on
the tasks that both \hsp\ and \ff\ manage to solve, \hsp's plan
lengths are within a range of $74\%$ to $126\%$ of \ff's plan lengths,
average $95\%$. On tasks solved by both \mips\ and \ff, plan lengths
of \mips\ are within $69\%$ to $128\%$ of \ff's lengths, average
$101\%$. For \stan, the range is $65\%$ to $318\%$, with $112\%$ on
average.



Concerning \ff's runtime behavior, the big variation in running time
as well as its capability of solving larger tasks both seem to result
from the way the overall search algorithm is arranged. We observed the
following. Those tasks that get solved by \ehc\ are those that are
solved fast. Sometimes, however, especially on the larger tasks, \ehc\ 
runs into a dead end situation (no cards can be moved anymore). Then,
the planner starts from scratch with complete \bfs, which takes more
time, but can solve big instances quite reliably, as can be seen on
the tasks of size $13$. Helpful actions works moderately well,
selecting around $70\%$ of the available actions, and the better
successors are usually close, but sometimes lie at depths of more than
$5$ steps.





\subsubsection{The {\sl Miconic} Domain}
\label{performance:competition:miconic}

The final domain used in the competition comes from a real-world
application, where moving sequences of elevators need to be planned.
The sequences are due to all kinds of restrictions, like that the VIPs
need to be served first. To formulate all of these restrictions,
complex first order preconditions are used in the representation
\cite{koehler:schuster:aips-00}. As only a few planners could handle
the full \adl\ representation, the domain was subdivided into the
easier \strips\ and \simple\ (conditional effects) classes, the full
\adl\ class, and an even more expressive class where numerical
constraints (the number of passengers in the elevator at a time)
needed to be considered. We show the runtime curves for the
participants in the full \adl\ class in Figure~\ref{eps/mic_t.eps}. In
difference to the previous domains, the {\sl Miconic} domain was run
on site at \aips-2000, using 450 MHz Pentium III machines with 256
MByte main memory.


%figure
\scalefig{1.0}{eps/mic_t.eps}{Runtime curves on {\sl Elevator} tasks
  for those planners which handled the full \adl\ Miconic 10 domain
  representation. Time is shown on a logarithmic scale.}

\ff\ outperforms the two other full \adl\ planners in terms of
solution time. It must be noticed, however, that \ipp\ and \propplan\ 
generate provably optimal plans here, such that one needs to be
careful when directly comparing those running times. On the other
hand, \ff's plans are quite close to optimal on these instances, being
within in a range of maximally $133\%$ of the optimal solution lengths
to the instances solved by \propplan, $111\%$ on average.

The large variation of \ff's running times is apparently due to the
same phenomenon as the variation in {\sl Freecell} is: sometimes, as
we observed, \ehc\ runs into a dead end, which causes a switch to
\bfs, solving the task in more time, but reliably. The helpful actions
percentage takes very low values on average, around $15\%$, and
breadth first search rarely goes deeper than four or five steps, where
the large majority of the better successors lie at depth $1$.



%We have, for each competition domain, seen a group of planners---or a
%single planner---that scaled best. Let us remark, just to draw the
%reader's attention to this, that {\em all} of those planners are based
%on heuristic search in state space, with the single exception of
%\systemr\ on the {\sl Blocksworld}.







\subsection{Some more Examples}
\label{performance:classical}

In this section, we present some of the results that we have obtained
in domains that were not used in the \aips-2000 competition. We give
some more examples of domains where \ff\ works well, and, to
illustrate our intuitions on the reasons for \ff's behavior, also some
examples of domains where \ff\ is less appropriate. 

For evaluation, we ran \ff\ on a collection of 20 benchmark planning
domains, including all domains from the \aips-1998 and \aips-2000
competitions, and seven more domains from the literature. Precisely,
the domains in our suite were {\sl Assembly}, two {\sl Blocksworld}s
(three- and four-operator representation), {\sl Briefcaseworld}, {\sl
  Bulldozer}, {\sl Freecell}, {\sl Fridge}, {\sl Grid}, {\sl Gripper},
{\sl Hanoi}, {\sl Logistics}, {\sl Miconic}-\adl, {\sl
  Miconic}-\simple, {\sl Miconic}-\strips, {\sl Movie}, {\sl Mprime},
{\sl Mystery}, {\sl Schedule}, {\sl Tireworld}, and {\sl Tsp}.
Instances were either taken from published distributions, from the
literature, or modified to show scaling behavior.\footnote{All \pddl\ 
  files are available in an online appendix. Random instance
  generators for all domains (together with descriptions of our
  randomization strategies) are available at
  http://www.informatik.uni-freiburg.de/{\~\ 
    }hoffmann/ff-domains.html.}  Times for \ff\ were measured on a
Sparc Ultra 10 running at 350 MHz, with a main memory of 256 MBytes.
Running times that we show for other planners were taken on the same
machine, if not otherwise indicated in the text. We found that \ff\ 
shows extremely competitive performance on 16 of the 20 domains listed
above. On the two {\sl Blocksworld}s, {\sl Mprime}, and {\sl Mystery},
it still shows satisfying behavior. Some examples that have not been
used in the \aips-2000 competition are:

\begin{itemize}
\item The {\sl Assembly} Domain. \ff\ solves $25$ of the $30$ tasks in
  the \aips-1998 test suite in less than five seconds, where the five
  others are either unsolvable, or have specification errors. The only
  other planner we know of that can solve any of the {\sl Assembly}
  tasks is \ipp. The latest version \ipp 4.0 solves only four of the
  very small instances, taking up to $12$ hours running time. \ff's
  plan lengths are, in terms of the number of actions, shorter than
  \ipp's time step optimal ones, ranging from $90\%$ to $96\%$.
\item The {\sl Briefcaseworld} Domain. This is a classical domain,
  where $n$ objects need to be transported using a briefcase.
  Whenever the briefcase is moved, a conditional effect forces all
  objects inside the briefcase to move with it. From our suite, \ipp
  4.0 easily solves the tasks with $n \leq 5$ objects, but fails to
  solve any task where $n \geq 7$. \ff, on the other hand, solves even
  the $11$-objects tasks in less than a second. On the tasks that
  \ipp\ solves, plan lengths of \ff\ are within $84\%$ to $111\%$ of
  \ipp's lengths, $99\%$ on average.
% examples stehen unter hsp ff experi / re-revision / small_domains
% --> mit erklaerung zu pddl files fuer hsp / ff dazunehmen, extra 
% abgesondert
\item The {\sl Grid} Domain. The 1998 competition featured five
  instances. For these tasks, the fastest planning mechanism we know
  of from the literature is a version of \grt\ that is enhanced with a
  simple kind of domain dependent knowledge, supplied by the user. It
  solves the tasks in $1.04$, $6.63$, $21.35$, $19.92$ and $118.65$
  seconds on a 300 MHz Pentium Celeron machine with 64 MByte main
  memory \cite{refanidis:vlahavas:aips-00}. \ff\ solves the same tasks
  within $0.15$, $0.47$, $2.11$, $1.93$ and $19.54$ seconds,
  respectively. Plan lengths of \ff\ are within $89\%$ to $139\%$ of
  \grt's lengths, $112\%$ on average.
\item The {\sl Gripper} Domain, used in the 1998 competition. The
  number of states that \ff\ evaluates before returning an optimal
  sequential solution is {\em linear} in the size of the task there.
  The biggest \aips-1998 example gets solved in $0.16$ seconds.
\item The {\sl Tireworld} Domain. The original task formulated by
  Stuart Russel asks the planner to find out how to replace a flat
  tire. Koehler and Hoffmann \shortcite{koehler:hoffmann:jair-00}
  modified the task such that an arbitrary number of $n$ tires need to
  be replaced. \ipp 3.2, using the goal agenda technique, solves the
  $1$, $2$, and $3$-tire tasks in $0.08$, $0.21$, and $1.33$ seconds,
  respectively, but exhausts memory resources as soon as $n \geq 4$.
  \ff\ scales to much larger tasks, taking less than a tenth of a
  second when $n \leq 6$, still solving the $10$-tire task in $0.33$
  seconds. \ff's plan lengths are, on the tasks that \ipp\ manages to
  solve, equally long in terms of the number of actions.
\end{itemize}

\noindent
As was already said, our intuition is that the majority of the
currently available benchmark planning domains---at least those
represented by our domain collection---are ``simple'' in structure,
and that it is this simplicity which makes them solvable so easily by
a greedy algorithm such as \ff. To illustrate our intuitions, we now
give data for a few domains that have a less simple structure. They
are therefore challenging for \ff.




\subsubsection{The {\sl Mystery} and {\sl Mprime} Domains}
\label{performance:classical:mystery}

The {\sl Mystery} and {\sl Mprime} domains were used in the \aips-1998
competition. Both are variations of the {\sl Logistics} domain, where
there are additional constraints on the capacity of each vehicle, and,
in particular, on the amount of fuel that is available. Both domains
are closely related, the only difference being that in {\sl Mprime},
fuel items can be transported between two locations, if one of those
has more than one such item.  In Figure~\ref{tab:mystery}, we compare
\ff's results on both domains to that reported by Drew McDermott for
the \unpop\ system \cite{mcdermott:ai-99}.


\begin{figure}[htb]
\begin{center}
{\tiny
\begin{tabular}{|l||r|r|r|r||r|r|r|r|}\hline
\multicolumn{1}{|c||}{} &
\multicolumn{4}{|c||}{{\sl Mystery}} &
\multicolumn{4}{|c|}{{\sl Mprime}} \\
\multicolumn{1}{|c||}{} &
\multicolumn{2}{|c|}{\unpop} &
\multicolumn{2}{|c||}{FF} &
\multicolumn{2}{|c|}{\unpop} &
\multicolumn{2}{|c|}{FF} \\ \hline \hline
task & time     &     steps &   time & steps
        & time     &     steps &   time & steps
        \\ \hline
prob-01 &   0.3   &     5     &   0.04 & 5
        &   0.4   &     5     &   0.04 & 5 
        \\ \hline
prob-02 &   3.3   &     8     &   0.25 & 10
        &  13.5   &     8     &   0.27 & 10
        \\ \hline
prob-03 &   2.1   &     4     &   0.08 &  4
        &   5.9   &     4     &   0.09 &  4
        \\ \hline
prob-04 &    -    &     -     &    -   &  -
        &   3.9   &     9     &   0.04 &  10
        \\ \hline
prob-05 &    -    &     -     &    -   &  -
        &  19.2   &    17     &    -   &  - 
        \\ \hline
prob-06 &    -    &     -     &    -   &  -
        &    -    &     -     &    -   &  - 
        \\ \hline
prob-07 &    -    &     -     &    -   &  -
        &    -    &     -     &    -   &  - 
        \\ \hline
prob-08 &    -    &     -     &    -   &  -
        &  52.5   &    10     &   0.40 & 10 
        \\ \hline
prob-09 &   3.3   &     8     &    -   &  -
        &  13.5   &     8     &   0.16 & 10 
        \\ \hline
prob-10 &    -    &     -     &    -   &  -
        &  79.0   &    19     &    -   &  - 
        \\ \hline
prob-11 &   1.4   &    11     &   0.05 & 9
        &   2.9   &    11     &   0.06 & 9 
        \\ \hline
prob-12 &    -    &     -     &    -   & -
        &   8.0   &    12     &   0.20 & 10
        \\ \hline
prob-13 & 370.1   &    16     &    -   &  -
        &  89.3   &    15     &   0.16 & 10 
        \\ \hline
prob-14 & 162.1   &    18     &    -   &  -
        &   -     &     -     &    -   &  - 
        \\ \hline
prob-15 &  17.3   &     6     &   0.98 & 8
        &  14.6   &     6     &   3.39 & 8 
        \\ \hline
prob-16 &   -     &     -     &    -   & -
        &  25.2   &    13     &   0.28 & 7 
        \\ \hline
prob-17 &  13.1   &     5     &   0.70 & 4
        &   4.0   &     5     &   0.92 & 4 
        \\ \hline
prob-18 &    -    &     -     &    -   &  -
        &    -    &     -     &    -   &  - 
        \\ \hline
prob-19 &  11.8   &     6     &    -   & -
        &  24.7   &     6     &   0.99 & 9 
        \\ \hline
prob-20 &  22.5   &     7     &   0.41 & 13
        &  62.8   &    17     &   3.11 & 13
        \\ \hline
prob-21 &   -     &     -     &    -   &  - 
        &  22.1   &    11     &    -   &  -
        \\ \hline
prob-22 &    -    &     -     &    -   &  -
        & 135.7   &    16     & 643.19 & 23 
        \\ \hline
prob-23 &    -    &     -     &    -   &  -
        &  55.0   &    18     &  3.09  & 14 
        \\ \hline
prob-24 &    -    &     -     &    -   &  -
        &  24.8   &    15     &   2.7  &  9 
        \\ \hline
prob-25 &   0.4   &     4     &   0.02 & 4
        &   0.5   &     4     &   0.02 & 4 
        \\ \hline
prob-26 &   6.0   &     6     &   0.85 & 7
        &  16.4   &    14     &   0.16 & 10
        \\ \hline
prob-27 &   3.8   &     9     &   0.05 & 5
        &   2.8   &     7     &   0.78 & 5 
        \\ \hline
prob-28 &   1.4   &     9     &   0.01 & 7
        &   1.6   &    11     &   0.08 & 5 
        \\ \hline
prob-29 &   0.9   &     4     &   0.06 & 4
        &   1.5   &     4     &   0.30 & 4 
        \\ \hline
prob-30 &  20.8   &    14     &   0.23 & 11
        &  17.7   &    12     &   1.86 & 11
        \\ \hline
\end{tabular}}
\end{center}
\caption{\label{tab:mystery}Running times and solution length results
  on the \aips-1998 {\sl Mystery} and {\sl Mprime} suites.}
\end{figure}


Instances are the same for both domains in Figure~\ref{tab:mystery}.
Results for {\em \unpop} have been taken by McDermott on a 300 MHz
Pentium-II workstation \cite{mcdermott:ai-99}. A dash indicates that
the task couldn't be solved by the corresponding planner.

One needs to be careful when comparing the running times in
Figure~\ref{tab:mystery}: unlike \ff, coded in {\sf C}, \unpop\ is
written in {\sf Lisp}. Thus, the apparent runtime superiority of \ff\ 
in Figure~\ref{tab:mystery} is not significant. On the contrary,
\unpop\ seems to solve these task collections more reliably than \ff:
it finds solutions to four {\sl Mystery} and three {\sl Mprime}
instances which \ff\ does not manage to solve. None of the planners is
superior in terms of solution lengths: On {\sl Mystery}, \ff\ ranges
within $55\%$ to $185\%$ of \unpop's lengths, $103\%$ on average, on
{\sl Mprime}, \ff\ ranges within $45\%$ to $150\%$, $93\%$ on average.



We think that \ff's behavior on these two domains is due to the large
amount of dead ends in the corresponding state spaces---we tried to
randomize \ff's search strategy, running it on the {\sl Mystery} and
{\sl Mprime} suits. Regardless of the randomization strategy we tried,
on the tasks that original \ff\ couldn't solve search ended up being
stuck in a dead end. Dead ends are a frequent phenomenon in the {\sl
  Mystery} and {\sl Mprime} domains, where, for example, an important
vehicle can run out of fuel. In that sense, the tasks in these domains
have a more complex structure than those in a lot of other benchmark
domains, where the tasks are dead-end free. Depending more or less
randomly on task structure and selected actions, \ff\ can either solve
{\sl Mystery} and {\sl Mprime} tasks quite fast, or fails, \ie
encounters a dead end state with \ehc.  Trying to solve the tasks with
complete \bfs\ exhausts memory resources for larger instances.






\subsubsection{Random \sat\ Instances}
\label{performance:classical:sat}


Our last example domain is not a classical planning benchmark. To give
an example of a planning task collection where \ff\ {\em really}
encounters difficulties, we created a planning domain containing hard
random \sat\ instances. Figure~\ref{eps/sat.eps} shows runtime curves
for \ff, \ipp 4.0, and \blackbox 3.6.

%figure
\scalefig{1.0}{eps/sat.eps}{Runtime curves for \ff, \ipp, and
  \blackbox, when run on hard random \sat\ instances with an
  increasing number of variables.}

The tasks in Figure~\ref{eps/sat.eps} are solvable \sat\ instances
that were randomly generated according to the fixed clause-length
model with $4.3$ times as many clauses as variables
\cite{mitchell:et:al:aaai-92}. Random instance generation and
translation software to \pddl\ have both been provided by Jussi
Rintanen. Our figure shows running times for \sat\ instances with $5$,
$10$, $15$, $20$, $25$, and $30$ variables, five tasks of each size.
Values for tasks of the same size are displayed in turn, \ie all data
points below 10 on the x-axis show running times for 5 variable tasks,
and so on. Though the data set is small, the observation to be made is
clear: \ff\ can only solve the small instances, and two of the bigger
ones. \ipp\ and \blackbox\ scale much better, with the tendency that
\blackbox\ is fastest.

The encoding of the \sat\ instances is the following. An operator
corresponds to assigning a truth value to a variable, which makes all
clauses true that contain the respective literal. Once a variable has
been assigned, its value is fixed. The goal is having all clauses
true. It is not surprising that \blackbox\ does best. After all, this
planner uses \sat\ technology for solving the tasks.\footnote{In
  these experiments, we ran \blackbox\ with the default parameters.
  Most likely, one can boost the performance by parameter tuning.} For
\ipp\ and \ff, the search space is the space of all partial truth
assignments. Due to exclusion relations, \ipp\ can rule out quite many
such assignments early, when it finds they can't be completed. \ff, on
the other hand, does no such reasoning, and gets lost in the
exponential search space, using a heuristic that merely tells it how
many variables it will still need to assign truth values to, unaware
of the interactions that might, and most likely will,
occur.

In contrast to most of the current benchmark planning domains, finding
a non-optimal solution to the planning tasks used here is {\sf
  NP}-hard. \ff's behavior on these tasks supports our intuition that
\ff's efficiency is due to the inherent simplicity of the planning
benchmarks.














\subsection{What Makes the Difference to \hsp?}
\label{performance:hsp}

One of the questions that the authors have been asked most frequently
at the \aips-2000 planning competition is this: If \ff\ is so closely
related to \hsp, then why does it perform so much better? \ff\ uses
the same basic ideas as classical \hsp, forward search in state space,
and heuristic evaluation by ignoring delete lists
\cite{bonet:geffner:aips-ws-98}. The differences lie in the way \ff\ 
estimates goal distances, the search strategy, and \ff's pruning
techniques. To obtain a picture of which new technique yields which
performance results, we conducted a number of experiments where those
techniques could be turned on and off independently of each other.
Using all combinations of techniques, we measured runtime and solution
length performance on a large set of planning benchmark tasks. In this
section, we describe the experimental setup, and summarize our
findings. The raw data and detailed graphical representations of the
results are available in an online appendix.










\subsubsection{Experimental Setup}
\label{performance:hsp:setup}


We focused our investigation on \ff's key features, \ie we restricted
our experiments to the \ff\ base architecture, rather than taking into
account all of \ff's new techniques. Remember that \ff's base
architecture (cf.  Section~\ref{architecture}) is the \ehc\ algorithm,
using \ff's goal distances estimates, and pruning the search space
with the helpful actions heuristic. The additional techniques
integrated deal with special cases, \ie the added goal deletion
heuristic and the goal agenda are concerned with goal orderings, and
the complete \bfs\ serves as a kind of safety net when local search
has run into a dead end.
%In the 20 planning domains from our testing
%suite, \ff's goal ordering techniques are essential only in the
%four-operator {\sl Blocksworld}, and yield moderate savings in the
%three-operator {\sl Blocksworld}, {\sl Schedule}, and the {\sl
%  Tireworld}. \ehc\ sometimes runs into a dead end in the {\sl
%  Freecell}, {\sl Miconic}-\adl, {\sl Mprime}, and {\sl Mystery}
%domains. In {\sl Briefcaseworld} and {\sl Bulldozer}, helpful actions
%can cut out solution paths, leading to invocation of \bfs. 
Considering all techniques independently would give us $2^6 = 64$
different planner configurations. As each of the special case
techniques yields savings only in a small subset (between 4 and 6) of
our 20 domains, large groups of those 64 configurations would behave
exactly the same on the majority of our domains. We decided to
concentrate on \ff's more fundamental techniques. The differences
between classical \hsp\ and \ff's base architecture are the following:
%Considering all those optimizations independently would thus
%have been an unnecessary blow up of our experiments. 
%We thus did not consider them all independently, and concentrated on
%\ff's more fundamental techniques instead. The differences between
%classical \hsp\ and \ff's base architecture are the following.

\begin{enumerate}
\item Goal distance estimates: while \hsp\ approximates relaxed
  solution lengths by computing certain weight values, \ff\ extracts
  explicit relaxed solutions, cf. Section~\ref{heuristic}.
\item Search strategy: while classical \hsp\ employs a variation of
  standard \hc, \ff\ uses \ehc\ as was introduced in
  Section~\ref{search}.
\item Pruning technique: while \hsp\ expands all children of any
  search node, \ff\ expands only those children that are considered
  helpful, cf.  Section~\ref{pruning:helpful}.
\end{enumerate}

We have implemented experimental code where each of these algorithmic
differences is attached to a switch, turning the new technique on or
off. The eight different configurations of the switches yield eight
different heuristic planners. When all switches are on, the resulting
planner is exactly \ff's base architecture. With all switches off, our
intention was to imitate classical \hsp, \ie \hsp 1 as it was used in
the \aips-1998 competition. Concerning the goal distance estimates
switch and the pruning techniques switch, we implemented the original
methods. Concerning the search strategy, we used the following simple
\hc\ design:

\begin{itemize}
\item Always select one best evaluated successor randomly.
\item Keep a memory of past states to avoid cycles in the \hc\ path.
\item Count the number of consecutive times in which the child of a
  node does not improve the heuristic estimate. If that counter
  exceeds a threshold, then restart, where the threshold is $2$ times
  the initial state's goal distance estimate.
\item Keep visited nodes in memory across restart trials in order to
  avoid multiple computation of the heuristic for the same state.
\end{itemize}

In \hsp 1, some more variations of restart techniques are implemented.
In personal communication with Blai Bonet and Hector Geffner, we
decided not to imitate those variations---which affect behavior only
in a few special cases---and use the simplest possible design instead.
We compared the performance of our implementation with all switches
turned off to the performance of \hsp 1, running the planners on 12
untyped \strips\ domains (the input required for \hsp 1). Except in
four domains, the tasks solved were the same for both planners. In
{\sl Freecell} and {\sl Logistics}, our planner solved more tasks,
apparently due to implementation details: though \hsp 1 did not visit
more states than our planner on the smaller tasks, it ran out of
memory on the larger tasks. In {\sl Tireworld} and {\sl Hanoi}, the
restarting techniques seem to make a difference: In {\sl Tireworld},
\hsp 1 cannot solve tasks with more than one tire because it always
restarts before getting close to the goal (our planner solves tasks
with up to 3 tires), whereas in {\sl Hanoi} our implementation can not
cope with more than 5 discs for the same reason (\hsp 1 solves tasks
with up to 7 discs). Altogether, in most cases there is a close
correspondence between the behavior of \hsp 1 and our configuration
with all switches turned off.  In any case, our experiments provide
useful insights into the performance of \ehc\ compared to a simple
straightforward \hc\ strategy.





To obtain data, we set up a large example suite, containing a total of
939 planning tasks from our 20 benchmark domains. As said at the
beginning of Section~\ref{performance:classical}, our domains were
{\sl Assembly}, two {\sl Blocksworld}s (three- and four-operator
representation), {\sl Briefcaseworld}, {\sl Bulldozer}, {\sl
  Freecell}, {\sl Fridge}, {\sl Grid}, {\sl Gripper}, {\sl Hanoi},
{\sl Logistics}, {\sl Miconic}-\adl, {\sl Miconic}-\simple, {\sl
  Miconic}-\strips, {\sl Movie}, {\sl Mprime}, {\sl Mystery}, {\sl
  Schedule}, {\sl Tireworld}, and {\sl Tsp}. In {\sl Hanoi}, there
were $8$ tasks---3 to 10 discs to be moved---in the other domains, we
used from $30$ to $69$ different instances. As very small instances
are likely to produce noisy data, we tried to avoid those by rejecting
tasks that were solved by \ff\ in less than $0.2$ seconds.  This was
possible in all domains but {\sl Movie}, where all tasks in the
\aips-1998 suite get solved in at most $0.03$ seconds. In the two {\sl
  Blocksworld} representations, we randomly generated tasks with $7$
to $17$ blocks, using the state generator provided by John Slaney and
Sylvie Thiebaux \shortcite{slaney:thiebaux:ai-01}. In {\sl Assembly}
and {\sl Grid}, we used the \aips-1998 instances, plus a number of
randomly generated ones similar in size to the biggest examples in the
competition suites. In {\sl Gripper}, our tasks contained from 10 to
59 balls to be transported.  In the remaining 9 competition domains,
we used the larger instances of the respective competition suites. In
{\sl Briefcaseworld} and {\sl Bulldozer}, we randomly generated around
50 large tasks, with 10 to 20 objects, and 14 to 24 locations,
respectively. In {\sl Fridge}, from 1 to 14 compressors had to be
exchanged, in {\sl Tireworld}, 1 to 30 wheels needed to be replaced,
and in {\sl Tsp}, 10 to 59 locations needed to be
visited.\footnote{All \pddl\ files are available in an online
  appendix, and the source code of all instance generators we used
  (together with descriptions of the randomization strategies) is
  available at http://www.informatik.uni-freiburg.de/{\~\ 
    }hoffmann/ff-domains.html.}



For each of the eight configurations of switches, we ran the
respective planner on each of the tasks in our example suite. Those
configurations using randomized \hc\ were run five times on each task,
and the results averaged afterwards. Though five trials might sound
like a small number here---way too small if we were to compare
different \hc\ strategies for \sat\ problems, for example---the number
seemed to be reasonable to us: remember that, in the planning
framework, all \hc\ trials start from the same state. The variance
that we found between different trials was usually low in our testing
runs. To complete the experiments in a reasonable time, we restricted
memory consumption to 128 MByte, and time consumption to 150
seconds---usually, if \ff\ needs more time or memory on a planning
task of reasonable size, then it doesn't manage to solve it at all. As
said at the beginning of the section, the raw data is available in an
online appendix, accompanied by detailed graphical representations.
Here, we summarize the results, and discuss the most interesting
observations. We examined the data separately for each domain, as our
algorithmic techniques typically show similar behavior for all tasks
within a domain. In contrast, there can be essential differences in
the behavior of the same technique when it is applied to tasks from
different domains.








\subsubsection{Running Time}
\label{performance:hsp:times}


For our running time investigation, if a configuration did not find a
solution plan to a given task, we set the respective running time
value to the time limit of 150 seconds (sometimes, a configuration can
terminate faster without finding a plan, for example an \ehc\ planner
running into a dead end). In the following, we designate each switch
configuration by 3 letters: ``H'' stands for helpful actions on, ``E''
stands for \ehc\ on, ``F'' stands for \ff\ estimates on. If a switch
is turned off, the respective letter is replaced by a ``$-$'': \ff's
base architecture is configuration ``HEF'', our \hsp 1 imitation is
``$---$'', and ``H$--$'', for example, is \hc\ with \hsp\ goal
distances and helpful actions pruning. For a first impression of our
running time results, see the averaged values per domain in
Figure~\ref{tab:times_pure}.





\begin{figure}[htb]
\begin{center}
  {\small
\begin{tabular}{|l||r|r|r|r|r|r|r|r|}\hline
    & $---$ & $--$F & $-$E$-$ &  $-$EF &  H$--$ & H$-$F & HE$-$ & HEF  \\ \hline \hline

Assembly & 117.39 & 31.75 & 92.95 & 61.10 & 47.81 & 20.25 & 20.34 & 16.94 \\ \hline
Blocksworld-3ops & 4.06 & 2.53 & 8.37 & 30.11 & 1.41 & 0.83 & 0.27 & 6.11 \\ \hline
Blocksworld-4ops & 0.60 & 8.81 & 80.02 & 56.20 & 1.21 & 10.13 & 25.19 & 40.65 \\ \hline
Briefcaseworld & 16.35 & 5.84 & 66.51 & 116.24 & 150.00 & 150.00 & 150.00 & 150.00 \\ \hline
Bulldozer & 4.47 & 3.24 & 31.02 & 15.74 & 81.90 & 126.50 & 128.40 & 141.04 \\ \hline
Freecell & 65.73 & 46.05 & 54.15 & 51.27 & 57.35 & 42.68 & 43.99 & 41.44 \\ \hline
Fridge & 28.52 & 53.58 & 31.89 & 52.60 & 0.85 & 0.69 & 1.88 & 2.77 \\ \hline
Grid & 138.06 & 119.53 & 115.05 & 99.18 & 115.00 & 95.10 & 18.73 & 11.73 \\ \hline
Gripper & 2.75 & 1.21 & 15.16 & 1.00 & 1.17 & 0.48 & 0.17 & 0.11 \\ \hline
Hanoi & 93.76 & 75.05 & 6.29 & 3.91 & 150.00 & 78.82 & 4.47 & 2.70 \\ \hline
Logistics & 79.27 & 102.09 & 79.77 & 111.47 & 36.88 & 39.69 & 10.18 & 11.94 \\ \hline
Miconic-ADL & 150.00 & 150.00 & 102.54 & 54.23 & 142.51 & 128.28 & 95.45 & 59.00 \\ \hline
Miconic-SIMPLE & 2.61 & 2.01 & 2.47 & 1.93 & 1.35 & 0.86 & 0.55 & 0.56 \\ \hline
Miconic-STRIPS & 2.71 & 2.32 & 4.84 & 1.53 & 1.44 & 1.01 & 0.64 & 0.36 \\ \hline
Movie & 0.02 & 0.02 & 0.02 & 0.02 & 0.02 & 0.02 & 0.02 & 0.02 \\ \hline
Mprime & 73.09 & 69.27 & 82.89 & 81.43 & 47.09 & 58.45 & 18.56 & 26.62 \\ \hline
Mystery & 78.54 & 90.55 & 71.60 & 86.01 & 75.73 & 95.24 & 85.13 & 86.21 \\ \hline
Schedule & 135.50 & 131.12 & 143.59 & 141.42 & 77.58 & 38.23 & 12.23 & 13.77 \\ \hline
Tireworld & 135.30 & 110.38 & 119.22 & 121.34 & 121.13 & 105.67 & 97.41 & 85.64 \\ \hline
Tsp & 4.11 & 0.82 & 2.45 & 0.75 & 2.48 & 0.57 & 0.15 & 0.07 \\ \hline
\end{tabular}}
\end{center}
\caption{\label{tab:times_pure}Averaged running time per domain for
  all eight configurations of switches.}
\end{figure}


Figure~\ref{tab:times_pure} shows, for each domain and each
configuration, the averaged running time over all instances in that
domain. As the instances in each domain are not all the same size, but
typically scale from smaller to very large tasks, averaging over all
running times is, of course, a very crude approximation of runtime
behavior. The data in Figure~\ref{tab:times_pure} provides a general
impression of our runtime results per domain, and gives a few hints on
the phenomena that might be present in the data. Compare, for example,
the values on the right hand side---those planners using helpful
actions---to those on the left hand side---those planners expanding
all sons of search nodes. In {\sl Briefcaseworld} and {\sl Bulldozer},
the right hand side values are higher, but in almost all other
domains, they are considerably lower. This is especially true for the
two rightmost columns, showing values for planners using helpful
actions and \ehc. This indicates that the main sources of performance
lie in the pruning technique and the search strategy---looking at the
rightmost ``HE$-$'' and ``HEF'' columns, which only differ in the goal
distance estimate, those two configuration values are usually close to
each other, compared to the other configurations in the same domain.


To put our observations on a solid basis, we looked, for each domain,
at each pair of configurations in turn, amounting to $20 * \frac{8 *
  7}{2} = 560$ pairs of planner performances. For each such pair, we
decided whether one configuration performed significantly better than
the other one. To decide significance, we counted the number of tasks
that one configuration solved faster. We found this to be a more
reliable criterion than things like the difference between running
times for each task. As tasks grow in size, rather than being taken
from a population with finite mean size, parametric statistical
procedures, like computing confidence intervals for runtime
differences, make questionable assumptions about the distribution of
data. We thus used the following non-parametric statistical test,
known as the two-tailed sign test \cite{siegel:castellan:88}.  Assume
that both planners, A and B, perform equally on a given domain.  Then,
given a random instance from the domain, the probability that B is
faster than A should be equal to the probability that A is faster than
B. Take this as the null hypothesis. Under that hypothesis, if A and B
behave differently on an instance, then B is faster than A with
probability $\frac{1}{2}$. Thus, the tasks where B is faster are
distributed over the tasks with different behavior according to a
Binomial distribution with $p = \frac{1}{2}$. Compute the probability
of the observed outcome under the null hypothesis, \ie if there are
$n$ tasks where A and B behave differently, and $k$ tasks where B is
faster, then compute the probability that, according to a binomial
distribution with $p = \frac{1}{2}$, at least $k$ positive outcomes
are obtained in $n$ trials. If that probability is less or equal than
$.01$, then reject the null hypothesis and say that B performs
significantly better than A.  Symmetrically, decide whether A performs
significantly better than B.  We remark that in all domains except
{\sl Movie} the tasks where two configurations behaved equally were
exactly those that could not be solved by either of the
configurations. In $60\%$ of the cases where we found that one
configuration B performed significantly better than another
configuration, B was faster on {\em all} instances with different
behavior. In $71\%$, B was faster on all but one such instance.


We are particularly interested in pairs A and B of configurations
where B results from A by turning one of the switches on, leaving the
two others unchanged. Deciding about significant improvement in such
cases tells us about the effect that the respective technique has on
performance in a domain. There are 12 pairs of configurations where
one switch is turned on. Figure~\ref{tab:times_switches} shows our
findings in these cases.


\begin{figure}[htb]
\begin{center}
{\small
\begin{tabular}{|l||c|c|c|c||c|c|c|c||c|c|c|c|}\hline
\multicolumn{1}{|c||}{} &
\multicolumn{4}{|c||}{F} &
\multicolumn{4}{|c||}{E} &
\multicolumn{4}{|c|}{H} \\ 

domain & $--$ & $-$E & H$-$ & HE & $--$ & $-$F & H$-$ & HF & $--$ & $-$F & E$-$ & EF \\ \hline \hline
Assembly & $+$ & $+$ & $+$ & $+$ & $ $ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Blocksworld-3ops & $+$ & $ $ & $+$ & $-$ & $+$ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Blocksworld-4ops & $ $ & $+$ & $ $ & $ $ & $-$ & $-$ & $-$ & $ $ & $ $ & $-$ & $+$ & $+$ \\ \hline
Briefcaseworld & $+$ & $-$ & $ $ & $ $ & $-$ & $-$ & $ $ & $ $ & $-$ & $-$ & $-$ & $-$ \\ \hline
Bulldozer & $+$ & $+$ & $-$ & $ $ & $-$ & $-$ & $-$ & $ $ & $-$ & $-$ & $-$ & $-$ \\ \hline
Freecell & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Fridge & $-$ & $ $ & $ $ & $ $ & $-$ & $-$ & $-$ & $-$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Grid & $+$ & $ $ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Gripper & $+$ & $+$ & $+$ & $+$ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Hanoi & $ $ & $+$ & $ $ & $ $ & $+$ & $+$ & $+$ & $+$ & $ $ & $ $ & $ $ & $ $ \\ \hline
Logistics & $-$ & $-$ & $+$ & $ $ & $ $ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Miconic-ADL & $ $ & $+$ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ \\ \hline
Miconic-SIMPLE & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Miconic-STRIPS & $+$ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Movie & $ $ & $ $ & $ $ & $ $ & $+$ & $+$ & $+$ & $+$ & $ $ & $ $ & $ $ & $ $ \\ \hline
Mprime & $+$ & $+$ & $+$ & $ $ & $ $ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Mystery & $ $ & $ $ & $ $ & $ $ & $+$ & $ $ & $+$ & $+$ & $+$ & $ $ & $ $ & $ $ \\ \hline
Schedule & $ $ & $ $ & $+$ & $+$ & $ $ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
Tireworld & $+$ & $ $ & $+$ & $+$ & $ $ & $-$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ \\ \hline
Tsp & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ \\ \hline
\end{tabular}}
\end{center}
\caption{\label{tab:times_switches}The effect of turning on a single
  switch, keeping the others unchanged. Summarized in terms of
  significantly improved or degraded running time performance per
  domain, and per switch configuration.}
\end{figure}

Figure~\ref{tab:times_switches} is to be understood as follows. It
shows our results for the ``F'', ``E'', and ``H'' switches, which
become active in turn from left to right. For each of these switches,
there are four configurations of the two other, background, switches,
displayed by four columns in the table. In each column, the behavior
of the respective background configuration with the active switch
turned off is compared to the behavior with the active switch turned
on. If performance is improved significantly, the table shows a
``$+$'', if it is significantly degraded, the table shows a ``$-$'',
and otherwise the respective table entry is empty. For example,
consider the top left corner, where the ``F'' switch is active, and
the background configuration is ``$--$'', \ie \hc\ without helpful
actions.  Planner A is ``$---$'', using \hsp\ distances, and planner B
is ``$--$F'', using \ff\ distances. B's performance is significantly
better than A's, indicated by a ``$+$''.


The leftmost four columns in Figure~\ref{tab:times_switches} show our
results for \hsp\ distance estimates versus \ff\ distance estimates.
Clearly, the latter estimates are superior in our domains, in the
sense that, for each background configuration, the behavior gets
significantly improved in 8 to 10 domains. In contrast, there are only
5 cases altogether where performance gets worse. The significances are
quite scattered over the domains and background configurations,
indicating that a lot of the significances result from interactions
between the techniques that occur only in the context of certain
domains. For example, performance is improved in {\sl Bulldozer} when
the background configuration does not use helpful actions, but
degraded when the background configuration uses \hc\ with helpful
actions. This kind of behavior can not be observed in any other
domain. There are 4 domains where performance is improved in all but
one background configuration. Apparently in these cases some
interaction between the techniques occurs only in one specific
configuration. We remark that often running times with \ff's estimates
are only a little better than with \hsp's estimates, \ie behavior gets
improved reliably over all instances, but only by a small factor (to
get an idea of that, compare the differences between average running
times in Figure~\ref{tab:times_pure}, for configurations where only
the distance estimate changes). In 5 domains, \ff's estimates improve
performance consistently over all background configurations,
indicating a real advantage of the different distance estimates. In
{\sl Gripper} (described in Section~\ref{pruning:helpful}), for
example, we found the following. If the robot is in room A, and holds
only one ball, \ff's heuristic prefers picking up another ball over
moving to room B, \ie the picking action leads to a state with better
evaluation. Now, if there are $n$ balls left in room A, then \hsp's
heuristic estimate of picking up another ball is $4n - 2$, while the
estimate of moving to room B is $3n + 1$. Thus, if there are at least
4 balls left in room A, moving to room B gets a better evaluation.
Summing up weights, \hsp\ overestimates the usefulness of the moving
action.



Comparing \hc\ versus \ehc, \ie looking at the four columns in the
middle of Figure~\ref{tab:times_switches}, the observation is this.
The different search technique is a bit questionable when the
background configuration does not use helpful actions, but otherwise,
\ehc\ yields excellent results. Without helpful actions, performance
gets degraded almost as many times as it gets improved, whereas, with
helpful actions, \ehc\ improves performance significantly in 16 of our
20 domains, being degraded only in {\sl Fridge}. We draw two
conclusions. First, whether one or the other search strategy is
adequate depends very much on the domain.  A simple example for that
is the {\sl Hanoi} domain, where \hc\ always restarts before it can
reach the goal---on all paths to the goal, there are exponentially
many state transitions where the son has no better evaluation than the
father. Second, there is an interaction between \ehc\ and helpful
actions pruning that occurs consistently across almost all of our
planning domains. This can be explained by the effect that the pruning
technique has on the different search strategies. In \hc, helpful
actions pruning prevents the planner from looking at too many
superfluous successors on each single state that a path goes through.
This saves time proportional to the length of the path. The effects on
\ehc\ are much more drastic.  There, helpful actions prunes out
unnecessary successors of each state during a breadth first search,
\ie it cuts down the branching factor, yielding performance speedups
exponential in the depths that are encountered.



We finally compare consideration of all actions versus consideration
of only the helpful ones. Look at the rightmost four columns of
Figure~\ref{tab:times_switches}. The observation is simply that
helpful actions are really helpful---they improve performance
significantly in almost all of our planning domains. This is
especially true for those background configurations using \ehc, due to
the same interaction that we have outlined above. In some domains,
helpful actions pruning imposes a very rigid restriction on the search
space: in {\sl Schedule}, as said in
Section~\ref{performance:competition:schedule}, we found that states
can have hundreds of successors, where only about $2\%$ of those are
considered helpful. In other domains, only a few actions are pruned,
like in {\sl Hanoi}, where at most three actions are applicable in
each state, which are all considered helpful in most of the cases.
Even a small degree of restriction does usually lead to a significant
improvement in performance. In two domains, {\sl Briefcaseworld} and
{\sl Bulldozer}, helpful actions can prune out too many possibilities,
\ie they cut away solution paths. This happens because there, the
relaxed plan can ignore things that are crucial for solving the real
task.  Consider the {\sl Briefcaseworld}, briefly described in
Section~\ref{performance:classical}, where objects need to be moved
using a briefcase. Whenever the briefcase is moved, all objects inside
it are moved with it by a conditional effect. Now, the relaxed planner
never needs to take any object out of the briefcase---the delete
effects say that moving an object means the object is no longer at the
start location. Ignoring this, keeping objects inside the briefcase
never hurts.










\subsubsection{Solution Length}
\label{performance:hsp:steps}


We also investigated the effects that \ff's new techniques have on
solution length. Comparing two configurations A and B, we took as the
data set the respective solution length for those tasks that both A
and B managed to solve---obviously, there is not much point in
comparing solution length when one planner can not find a solution at
all. We then counted the number $n$ of tasks where A and B behaved
differently, and the number $k$ where B's solution was shorter, and
decided about significance like described in the last section.
Figure~\ref{tab:steps_switches} shows our results in those cases where
a single switch is turned.



\begin{figure}[htb]
\begin{center}
{\small
\begin{tabular}{|l||c|c|c|c||c|c|c|c||c|c|c|c|}\hline
\multicolumn{1}{|c||}{} &
\multicolumn{4}{|c||}{F} &
\multicolumn{4}{|c||}{E} &
\multicolumn{4}{|c|}{H} \\ 

domain & $--$ & $-$E & H$-$ & HE & $--$ & $-$F & H$-$ & HF & $--$ & $-$F & E$-$ & EF \\ \hline \hline
Assembly & $ $ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $ $ & $+$ & $+$ & $ $ & $ $ \\ \hline
Blocksworld-3ops & $ $ & $+$ & $ $ & $+$ & $ $ & $+$ & $ $ & $+$ & $ $ & $+$ & $+$ & $ $ \\ \hline
Blocksworld-4ops & $ $ & $ $ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ \\ \hline
Briefcaseworld & $ $ & $+$ & $ $ & $ $ & $+$ & $+$ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
Bulldozer & $ $ & $ $ & $ $ & $ $ & $+$ & $+$ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
Freecell & $ $ & $+$ & $ $ & $+$ & $ $ & $ $ & $ $ & $ $ & $+$ & $+$ & $ $ & $ $ \\ \hline
Fridge & $-$ & $ $ & $-$ & $ $ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ & $ $ & $ $ \\ \hline
Grid & $ $ & $ $ & $ $ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ & $ $ \\ \hline
Gripper & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ & $-$ & $ $ & $ $ & $ $ & $-$ & $ $ \\ \hline
Hanoi & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
Logistics & $ $ & $+$ & $-$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ & $+$ & $ $ \\ \hline
Miconic-ADL & $ $ & $+$ & $ $ & $+$ & $ $ & $ $ & $ $ & $+$ & $ $ & $ $ & $ $ & $+$ \\ \hline
Miconic-SIMPLE & $-$ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ & $ $ & $+$ & $+$ & $+$ \\ \hline
Miconic-STRIPS & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $+$ & $ $ & $ $ & $+$ & $+$ \\ \hline
Movie & $ $ & $ $ & $ $ & $ $ & $-$ & $-$ & $-$ & $-$ & $ $ & $ $ & $ $ & $ $ \\ \hline
Mprime & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
Mystery & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
Schedule & $ $ & $ $ & $+$ & $ $ & $ $ & $ $ & $ $ & $-$ & $+$ & $+$ & $ $ & $ $ \\ \hline
Tireworld & $ $ & $ $ & $ $ & $+$ & $ $ & $ $ & $ $ & $+$ & $ $ & $ $ & $ $ & $ $ \\ \hline
Tsp & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \\ \hline
\end{tabular}}
\end{center}
\caption{\label{tab:steps_switches}The effect of 
  turning on a single switch, keeping the others unchanged. Summarized
  in terms of significantly improved or degraded solution length
  performance per domain, and per switch configuration.}
\end{figure}



The data in Figure~\ref{tab:steps_switches} are organized in the
obvious manner analogous to Figure~\ref{tab:times_switches}. A first
glance at the table tells us that \ff's new techniques are also useful
for shortening solution length in comparison to \hsp 1, but not as
useful as they are for improving runtime behavior. Let us focus on the
leftmost four columns, \hsp\ distance estimates versus \ff\ distance
estimates. The observations are that, with \ehc\ in the background,
\ff\ estimates often result in shorter plans, and that there are two
domains where solution lengths are improved across all background
configurations. Concerning the second observation, this is due to
properties of the domain that \ff's heuristic recognizes, but \hsp's
doesn't. Recall what we observed about the {\sl Gripper} domain in the
preceding section. With the robot standing in room A, holding only one
ball, the \ff\ heuristic gives picking up the ball a better evaluation
than moving to room B. The \hsp\ heuristic doesn't do this.
Therefore, using the \hsp\ heuristic results in longer plans.
Concerning the first observation, improved solution lengths when \ehc\ 
is in the background, we do not have a good explanation for this. It
seems that the greedy way in which \ehc\ builds its plans is just
better suited when distance estimates are cautious, \ie low.



Consider the four columns in the middle of
Figure~\ref{tab:steps_switches}, \hc\ versus \ehc. There are many
cases where the different search strategy results in shorter plans.
We figure that this is due to the different plateau behavior that the
search methods exhibit, \ie their behavior in flat regions of the
search space. Enforced hill-climbing enters a plateau somewhere,
performs complete search for a state with better evaluation, and adds
the shortest path to that state to its current plan prefix. When \hc\ 
enters a plateau, it strolls around more or less randomly, until it
hits a state with better evaluation, or has enough of it and restarts.
All the actions on its journey to the better state are kept in the
final plan. In {\sl Movie}, the phenomenon is this. If a planner
chooses to reset the counter on the VCR before it chooses to rewind
the movie (initially, neither heuristic makes a distinction between
these two actions), then it has to reset the counter again. The \ehc\ 
planners always reset the counter first. The \hc\ planners, on the
other hand, randomly choose either ordering with equal probability. As
said in Section~\ref{performance:hsp:setup}, \hc\ was given five tries
on each task, and results averaged. In five tries, around half of the
solutions use the correct ordering, such that, for all tasks, the
average value is lower than the corresponding value for the \ehc\ 
planners.



Finally, we compare consideration of all actions versus consideration
of only the helpful ones, results depicted in the rightmost four
columns of Figure~\ref{tab:times_switches}. Coming a bit unexpected,
there is only one single case where solution length performance is
degraded by turning on helpful actions. This indicates that the
actions on the shortest path to the goal are, in fact, usually
considered helpful---unless {\em all} solution paths are thrown away,
as is sometimes the case only in the {\sl Briefcaseworld} and {\sl
  Bulldozer} domains. Quite the other way around than one should
think, pruning the search space with helpful actions sometimes leads
to significantly shorter solution plans, especially when the
underlying search method is \hc. Though this may sound paradoxical,
there is a simple explanation to it. Consider what we said above about
the plateau behavior of \hc, randomly adding actions to the current
plan in the search for a better state. If such a search engine is
armed with the helpful actions successors choice, focusing it into the
direction of the goals, it might well take less steps to find the way
off a plateau.





\section{Related Work}
\label{related}

The most important connections of the \ff\ approach to methodologies
reported in the literature are the following:

\begin{itemize}
\item \hsp's basic idea of forward state space search and heuristic
  evaluation by ignoring delete lists \cite{bonet:geffner:aips-ws-98}.
\item The view of our heuristic as a special case of \graphplan\ 
  \cite{blum:furst:ijcai-95}, and its connection to \hsp's heuristic
  method.
\item The similarity of the helpful actions heuristic to McDermott's
  favored actions \shortcite{mcdermott:aips-96}, and to irrelevance
  detection mechanisms \cite{nebel:et:al:ecp-97}.
\item The inspiration of the added goal deletion heuristic by work
  done by Koehler and Hoffmann \shortcite{koehler:hoffmann:jair-00},
  and the adaption of the goal agenda approach \cite{koehler:aips-98}.
\item The adaption of \ipp's \adl\ preprocessing phase
  \cite{koehler:hoffmann:ecai-ws-00}, inspired by ideas from Gazen and
  Knoblock \shortcite{gazen:knoblock:ecp-97}.
\end{itemize}

\noindent
We have discussed all of these connections in the respective sections
already. So let us focus on a connection that has not yet been
mentioned. It has been recognized after the first planning competition
at \aips-1998 that the main bottleneck in \hsp 1 is the recomputation
of the heuristic on each single search state. Two recent approaches
are based on the observation that the repeated recomputation is
necessary because \hsp 1 does forward search with a forward heuristic,
\ie the directions of search and heuristic are the same. The authors
of \hsp\ themselves stick to their heuristic, but change the search
direction, going backwards from the goal in \hspr\ 
\cite{bonet:geffner:ecp-99}. This way, they need to compute weight
values only once, estimating each fact's distance to the initial
state, and only sum the weights up for a state later during
search.\footnote{\hspr\ is integrated into \hsp 2 as an option of
  configuring the search process \cite{bonet:geffner:ai-01}.}

Refanidis and Vlahavas \shortcite{refanidis:vlahavas:ecp-99} invert
the direction of the \hsp\ heuristic instead. While \hsp\ computes
distances going from the current state towards the goal, \grt\ goes
from the goal to each fact. The function that then extracts, for each
state during forward search, the states heuristic estimate, uses the
pre computed distances as well as some information on which facts will
probably be achieved simultaneously.

Interestingly, \ff\ recomputes, like \hsp, the heuristic from scratch
on each search state, but nevertheless outperforms the other
approaches. As we have seen in Section~\ref{performance:hsp}, this is
for the most part due to \ff's search strategy and the helpful actions
pruning technique.






\section{Conclusion and Outlook}
\label{outlook}

We have presented an approach to domain independent planning that, at
the time being, outperforms all existing technology on the majority of
the currently available benchmark domains. Just like the well known
\hsp 1 system, it relies completely on forward state space search and
heuristic evaluation of states by ignoring delete lists. Unlike \hsp,
the method uses a \graphplan-style algorithm to find an explicit
relaxed solution to each search state. Those solutions give a more
careful estimation of a state's difficulty. As a second major
difference to \hsp, our system employs a novel local search strategy,
combining \hc\ with complete search. Finally, the method makes use of
powerful heuristic pruning techniques, which are based on examining
relaxed solutions.

As we have mentioned earlier, our intuition is that the reasons for
\ff's efficiency lie in structural properties that the current
planning benchmarks tend to have. As a matter of fact, the simplicity
of the benchmarks quite immediately meets the eye, once one tries to
look for it. It should be clear that the {\sl Gripper} tasks, where
some balls need to be transported from one room to another, exhibit a
totally different search space structure than, for example, hard
random \sat\ instances. Therefore, it's intuitively unsurprising that
different search methods are appropriate for the former tasks than are
traditionally used for the latter. The efficiency of \ff\ on many of
the benchmarks can be seen as putting that observation to the surface.

To make explicit the hypotheses stated above, we have investigated the
state spaces of the planning benchmarks. Following Frank et al.
\shortcite{frank:et:al:jair-97}, we have collected empirical data,
identifying characteristic parameters for different kinds of planning
tasks, like the density and size of local minima and plateaus in the
search space. This has lead us to a taxonomy for planning domains,
dividing them by the degree of complexity that the respective task's
state spaces exhibit with respect to relaxed goal distances. Most of
the current benchmark domains apparently belong to the ``simpler''
parts of that taxonomy \cite{hoffmann:ijcai-01}. We also approach our
hypotheses from a theoretical point of view, where we measure the
degree of interaction that facts in a planning task exhibit, and draw
conclusions on the search space structure from that. Our goal in that
research is to devise a method that automatically decides which part
of the taxonomy a given planning task belongs to.

In that context, there are some remarks to be made on what AI planning
research is heading for. Our point of view is that the goal in the
field should not be to develop a technology that works well on {\em
  all} kinds of tasks one can express with planning languages. This
will hardly be possible, as even simple languages as \strips\ can
express {\sf NP}-hard problems like \sat. What might be possible,
however, is to devise a technology that works well on those tasks that
{\em can} be solved efficiently. In particular, if a planning task
does not constitute much of a problem to an uninformed human solver,
then it neither should do so to our planning algorithms. With the \ff\ 
system, we already seem to have a method that accomplishes this quite
well, at least for sequential planning in \strips\ and \adl. While
\ff\ is not particularly well suited for solving random \sat\ 
instances, it easily solves intuitively simple tasks like the {\sl
  Gripper} and {\sl Logistics} ones, and is well suited for a number
of other domains where finding a non-optimal solution is not {\sf
  NP}-hard. This sheds a critical light on the predictions of Kautz
and Selman \shortcite{kautz:selman:ijcai-99}, who suspected that
planning technology will become superfluous because of the fast
advance of the state of the art in propositional reasoning systems.
The methods developed there are surely useful for solving \sat. They
might, however, not be appropriate for the typical structures of tasks
that AI planning should be interested in.



\acks{The authors wish to thank Blai Bonet and Hector Geffner for
  their help in setting up the experiments on the comparison of \ff\ 
  with \hsp. We thank Jussi Rintanen for providing us with software to
  create random \sat\ instances in the \pddl\ language, and
  acknowledge the anonymous reviewer's comments, which helped improve
  the paper.  }


%%
%%
%% bibliography
%%
%%



\vskip 0.2in
\bibliography{./abbreviations,./biblio,./crossref}
\bibliographystyle{theapa}


\end{document}
