%%
%%
%% 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]
\vspace*{-3mm}
\begin{center}
  \makebox{{\def\epsfsize##1##2{#1##1}\epsfbox{#2}}}
\end{center}
\vspace*{-7mm}
\caption{\label{#2}#3}
\vspace*{-3mm}
\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{\ff}{FF}
\newcommand{\mff}{Metric-FF}
\newcommand{\mffs}{FF.speed}
\newcommand{\mffq}{FF.quality}
\newcommand{\hsp}{HSP}
\newcommand{\mipp}{Metric-IPP}
\newcommand{\ipp}{IPP}
\newcommand{\grt}{GRT}
\newcommand{\grtr}{GRT-R}
\newcommand{\stan}{STAN}
\newcommand{\repop}{RePOP}
\newcommand{\unpop}{Unpop}
\newcommand{\tpfour}{TP4}
\newcommand{\sapa}{Sapa}
\newcommand{\graphplan}{Graphplan}
\newcommand{\mips}{MIPS}
\newcommand{\mipss}{MIPS.plain}
\newcommand{\mipsq}{MIPS.quality}
\newcommand{\lpg}{LPG}
\newcommand{\lpgs}{LPG.speed}
\newcommand{\lpgq}{LPG.quality}
\newcommand{\semsyn}{SemSyn}




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

\newcommand{\ipctwo}{IPC-2}
\newcommand{\ipcthree}{IPC-3}



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

\newcommand{\poly}{P}
\newcommand{\np}{NP}
\newcommand{\pspace}{PSPACE}

\newcommand{\actions}{A}
\newcommand{\goal}{G}
\newcommand{\initial}{I}


\newcommand{\true}{``true''}
\newcommand{\false}{``false''}

\newcommand{\ehc}{enforced hill-climbing}


\newcommand{\rationale}{{\bf Q}}
\newcommand{\natuerliche}{{\bf N}_0}





\newcommand{\stripsrelaxedplansat}{RPLANSAT}
\newcommand{\restrictedrelaxedplansat}{RESTRICTED-RPLANSAT}
\newcommand{\monotonicrelaxedplansat}{STRONGLY-MONOTONIC-RPLANSAT}





\newcommand{\propos}{P}
\newcommand{\vars}{V}

\newcommand{\proposof}{p}
\newcommand{\varsof}{v}



\newcommand{\expr}{\mbox{{\em exp}}}
\newcommand{\comp}{\mbox{{\em comp}}}
\newcommand{\ass}{\mbox{{\em ass}}}



\newcommand{\con}{\mbox{{\em con}}}
\newcommand{\eff}{\mbox{{\em eff}}}
\newcommand{\pre}{\mbox{{\em pre}}}



\newcommand{\result}{result}
\newcommand{\relaxed}{+}



\newcommand{\comps}{\mbox{{\em Cons}}}
\newcommand{\effass}{\mbox{{\em Eff-ass}}}
\newcommand{\effrh}{\mbox{{\em Eff-rh}}}

\newcommand{\lexpr}{\langle linexp \rangle}



\newcommand{\asseff}{\mbox{:=}}
\newcommand{\inceff}{\mbox{+=}}
\newcommand{\deceff}{\mbox{-=}}
\newcommand{\muleff}{*\mbox{=}}
\newcommand{\diveff}{\mbox{/=}}



\newcommand{\maxneed}{\mbox{mneed}}
\newcommand{\supportval}{\mbox{supv}}
\newcommand{\mininc}{\mbox{mininc}}






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



%\jairheading{13}{2000}{1-1}{7/00}{10/00}
\ShortHeadings{Translating ``Ignoring Delete Lists'' to Numeric State Variables}
{Hoffmann}
\firstpageno{1}


\begin{document}


\title{The Metric-FF Planning System: Translating ``Ignoring Delete Lists'' to Numeric State Variables}


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


\maketitle


\begin{abstract}
  Planning with numeric state variables has been a challenge for many
  years, and was a part of the 3rd International Planning Competition
  (\ipcthree). Currently one of the most popular and successful
  algorithmic techniques in \strips\ planning is to guide search by a
  heuristic function, where the heuristic is based on relaxing the
  planning task by ignoring the delete lists of the available actions.
  
  We present a natural extension of ``ignoring delete lists'' to
  numeric state variables, preserving the relevant theoretical
  properties of the \strips\ relaxation under the condition that the
  numeric task at hand is ``monotonic''. We then identify a subset of
  the numeric \ipcthree\ competition language, ``linear tasks'', where
  monotonicity can be achieved by pre-processing. Based on that, we
  extend the algorithms used in the heuristic planning system \ff\ to
  linear tasks. The resulting system \mff\ is, according to the
  \ipcthree\ results which we discuss, one of the two currently most
  efficient numeric planners.\footnote{This article is an extended and
    revised version of a paper \cite{hoffmann:ecai-02} that has been
    published at ECAI-02.}
\end{abstract}



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



\section{Introduction}
\label{introduction}









The planning community has long been aware of the fact that purely
propositional representation languages, in particular \strips\ 
\cite{fikes:nilsson:ai-71}, are not well suited for modeling various
phenomena that are essential in real-world problems. In particular,
modeling context dependent effects, concurrent execution of actions
with different duration, and continuous resources are all awkward, or
impossible, within the \strips\ language. To overcome the first of
these limitations, Pednault \shortcite{pednault:kr-89} defined the
(nowadays widely accepted) \adl\ language, which amongst other things
allows for conditional effects (effects that only occur when their
condition holds true in the state of execution). To overcome (one or
both of) the latter two limitations, various proposals have been made,
e.g.
\cite{ghallab:laruelle:aips-94,koehler:ecai-98,smith:weld:ijcai-99}.
The most recent effort in this direction is the \pddl2.1 language
defined by Fox and Long \shortcite{fox:long:aips-02b} as the input
language for the 3rd International Planning Competition (\ipcthree).
The IPC series is a biennial challenge for the planning community,
inviting planning systems to participate in a large scale publicly
accessible evaluation. \ipcthree\ was hosted at \aips-2002, and
stressed planning beyond the \strips\ formalism, featuring tracks for
temporal and numeric planners. This article describes the approach
behind one of the planners that participated in \ipcthree, \mff. \mff\ 
is an extension of the \ff\ system (that can handle \adl) to numeric
constructs.





Currently one of the most popular and successful algorithmic
techniques in \strips\ planning is to guide search (forward or
backward, state space or plan space) by a heuristic function, where
the heuristic is based on relaxing the planning task by ignoring the
delete lists (i.e. the negative effects) of the available actions. The
heuristic value of a search state in this framework is (an estimate
of) the difficulty of extending the state to a solution using the
relaxed actions. This idea was first, independently, proposed by
McDermott \shortcite{mcdermott:aips-96} and Bonet et al
\shortcite{bonet:et:al:aaai-97}, and is now widely used in a huge
number of variations. Examples of planners that use the idea are
\unpop\ \cite{mcdermott:aips-96,mcdermott:ai-99}, \hsp\ in its various
configurations
\cite{bonet:geffner:aips-ws-98,bonet:geffner:ecp-99,bonet:geffner:ai-01},
\grt\ \cite{refanidis:vlahavas:ecp-99,refanidis:vlahavas:jair-01},
\mips\ \cite{edelkamp:helmert:aim-01}, \stan4 \cite{fox:long:aim-01},
\repop\ \cite{nguyen:kambhampati:ijcai-01}, \sapa\ 
\cite{do:kambhampati:ecp-01}, and \ff\ 
\cite{hoffmann:ismis-00,hoffmann:nebel:jair-01}.  The search paradigms
used by these planners include forward and backward state space search
as well as partial-order planning. The forward state space planner
\ff\ was especially successful at \ipctwo\ \cite{bacchus:aim-01}.  In
what follows we extend the heuristic idea for \strips, ignoring delete
lists, to numeric state variables in a way that preserves the relevant
theoretical properties of the \strips\ relaxation. We phrase these
properties {\em admissibility}, {\em basic informedness}, and {\em
  polynomiality}. While the investigation takes place in the setting
of forward state space search as used by \ff, it seems likely that the
same ideas will also work in other search schemes such as plan-space
search (some more on this in the outlook, Section~\ref{conclusion}).
The \sapa\ system also deals with numeric constructs. The heuristic
function, however, completely ignores numeric goals and thus lacks one
of the relevant theoretical properties, basic informedness (we will
return to this later). There are also numeric versions of \mips\ and
\grt. On the respective \mips\ version there is no publication
available at the time of writing but an article
\cite{edelkamp:jair-03}, which the reader is referred to, is to appear
in this same JAIR special issue. The numeric version of \grt, \grtr\ 
\cite{refanidis:vlahavas:ecai-00}, allows only for a restricted form
of numeric variables and expressions, basically a limited form of
resource allocation and consumption. The heuristic function considers
resource consumption as another form of state cost. This, like \sapa's
heuristic, lacks basic informedness, as we will see later.




In a numeric planning task, there can be numeric constraints (in
action preconditions and the goal) and numeric effects (in action
effects).  Constraints and effects can be of different types. For
example, a constraint can require that the value of a variable be
either at least as high as or at most as high as a given constant. The
numeric effects can, from a semantic perspective, either increase or
decrease the value of the affected variable. Now, the delete effects
in \strips\ decrease the logical value of the propositional variables,
so the idea we explore is to relax the numeric task by ignoring all
decreasing effects. The main difficulty with this idea is that
ignoring the decreasing effects does not necessarily simplify the
task. For example, when the goal requires that $x < 0$ and $x$ is
initially equal to $0$, the decreasing effects are needed to solve the
task, so the relaxed task is unsolvable. The relaxation is thus only
adequate (preserves the theoretical properties mentioned above) in
tasks where it is always preferable to have higher variable values.
We call such tasks {\em monotonic}.\footnote{There is a duality here
  with respect to ignoring the {\em in}creasing effects or the {\em
    de}creasing effects. If lower variable values are always
  preferable then ignoring the increasing effects is an adequate
  relaxation. Whether one chooses one or the other does not seem to
  make much difference. We choose monotonicity in the positive sense
  only because it is conceptually simpler.}
%DAVID's view of monotone
%fns, primarily?? 
We observe that tasks that belong to a subset of the numeric
\ipcthree\ competition language, {\em linear} tasks (in which the
numeric variables are only used in linear functions), can be brought
into a normal form that is monotonic. Based on that, we extend the
heuristic algorithms used in \ff, and thereby the whole system, to
linear tasks.





\ff\ \cite{hoffmann:nebel:jair-01} is a close relative of \hsp\ 
\cite{bonet:geffner:ai-01}. Search takes place forward in the state
space, \ie starting from the initial state new states are explored
until a goal state is found. The search process in \ff\ is guided by a
heuristic function that is based on solving, in each search state $s$,
the relaxed task starting from $s$. The heuristic value to $s$ is the
number of actions in the respective relaxed plan, \ie the number of
actions needed to achieve the goal from $s$ when assuming the delete
lists are all empty. States with lower heuristic value are preferred.
The main obstacle in the extension of \ff\ to numeric state variables
is to extend the machinery that solves the relaxed task in each search
state. Once this machinery is defined, the rest of the system
translates effortlessly.  We evaluate the resulting planning system
\mff\ by discussing the results of the numeric domains used in the 3rd
International Planning Competition. As it turns out, \mff\ and \lpg\ 
\cite{gerevini:et:al:jair-03} were the best performing numeric
planners in the competition.\footnote{The C source code of \mff\ is
  available for free download from the \ff\ homepage at {\tt
    http://www.informatik.uni-freiburg.de/}\~ {\tt hoffmann/ff.html}.}









The article is structured as follows. Throughout the text we refer to
related work where it is relevant. We first give the necessary
background in terms of \strips\ notation, and the techniques that the
\strips\ version of \ff\ uses. Section~\ref{numeric} introduces our
notation for numeric state variables, \ie for the numeric subset of
\pddl2.1. Section~\ref{relaxation} describes how the heuristic
principle for \strips, the relaxation, can be extended to the numeric
setting. Section~\ref{rplans} defines our algorithms for solving
relaxed numeric tasks. Section~\ref{metric-ff} then fills in the
details on how the relaxed plans are used to implement the \mff\ 
planning system, and we briefly describe how \adl\ constructs can be
handled, and how flexible optimization criteria can be taken into
account. The \ipcthree\ results are discussed in
Section~\ref{results}. Section~\ref{conclusion} concludes and outlines
future work. An appendix contains most proofs.













\section{\strips\ Techniques}
\label{strips}






In this section, we give background on the techniques that the \ff\ 
system uses in the \strips\ language. We start by examining the
relaxation that underlies \ff's heuristic function. We then proceed to
the algorithms that are used to solve relaxed tasks.  We finally
describe how the relaxed plans are used to implement the actual \ff\ 
system. The discussion is a little more detailed than would strictly
be necessary to understand the \ff\ workings. This serves to provide a
solid background for what is to come: Sections~\ref{relaxation},
\ref{rplans}, and~\ref{metric-ff} will, in turn for each of the
subtopics dealt with in this section, show how these methodologies can
be extended to the numeric setting.




Before we start, we give the notation for the \strips\ language. When
we refer to sets we mean finite sets. We consider the propositional
\strips\ language, where all constructs are based on logical
propositions. A world {\em state} $s$ is a set of (the true)
propositions. An {\em action} $a$ is given as a triple of proposition
sets, $a = (\pre(a), \eff(a)^+, \eff(a)^-)$: $a$'s {\em precondition},
{\em add list}, and {\em delete list}, respectively (we use the
somewhat unusual notation $\eff(a)^+$ and $\eff(a)^-$ as this makes
the extension to numeric variables more readable).




We first specify the semantics of world states and actions. Throughout
the article, we consider sequential planning only, where a single
action at a time is applied to a world state.\footnote{As opposed to,
  e.g., \graphplan-based approaches \cite{blum:furst:ai-97}, which
  find sets of actions to be applied in parallel.} Actions induce
state transitions as follows. Given a world state $s$ and an action
$a$, the {\em result} of executing (the action sequence consisting
solely of) $a$ in $s$, $\result(s, \langle a \rangle)$, is $\result(s,
\langle a \rangle) := s \setminus \eff(a)^- \cup \eff(a)^+$ if the
action is {\em applicable} in $s$, $\pre(a) \subseteq s$. Otherwise,
$\result(s, \langle a \rangle)$ is undefined. The result of executing
an action sequence $\langle a_1, \dots, a_m \rangle$ in a state is
recursively defined by $\result(s, \langle a_1, \dots, a_m \rangle) :=
\result(\result(s, \langle a_1, \dots, a_{m-1} \rangle), a_m)$, and
$\result( s, \langle \rangle) = s$.





A \strips\ task -- we use the word ``task'' rather than ``problem'' to
avoid confusion with the complexity theoretic notion of decision
problems -- is a tuple $(\propos, \actions, \initial, \goal)$: the set
$\propos$ of logical propositions used in the task, the set $\actions$
of actions, the {\em initial state} $\initial$ (a world state), as
well as the {\em goal} $\goal$ (a partial world state, see below). All
propositions in the actions, initial state, and goal are taken from
$\propos$.  Given a task $(\propos, \actions, \initial, \goal)$, what
one wants to find is a {\em plan}. An action sequence $\langle a_1,
\dots, a_m \rangle \in \actions^*$ is a plan for $(\propos, \actions,
\initial, \goal)$ if $\goal \subseteq \result(\initial, \langle a_1,
\dots, a_m \rangle)$. Since the $\subseteq$ relation (not equality) is
used here, there could be several {\em goal states} in which a plan
ends. If there exists at least one plan for a task, then the task is
{\em solvable}. Sometimes we refer to {\em optimal} plans. In our
sequential framework, a plan is optimal for a task if there is no plan
for the task that contains fewer actions.






















\subsection{Relaxing Strips Tasks}
\label{strips:relaxation}





We want to inform the search for a plan by a function that estimates
the goal distance of search states. The idea is to define a relaxation
(\ie a simplification) of planning tasks, then solve, in any search
state, the relaxed task, and take the length of the relaxed solution
as an estimate of how long the solution from the state at hand really
is. The relaxation that was first proposed by McDermott
\shortcite{mcdermott:aips-96} and Bonet, Loerincs, \& Geffner
\shortcite{bonet:et:al:aaai-97}, is to relax \strips\ tasks by
ignoring the delete lists of all actions.






\begin{def1}\label{def:strips-relaxation}
  Assume a \strips\ task $(\propos, \actions, \initial, \goal)$. The
  {\em relaxation} $a^{\relaxed}$ of an action $a \in \actions$, $a =
  (\pre(a), \eff(a)^+, \eff(a)^-)$, is defined as
\[
a^{\relaxed} := (\pre(a), \eff(a)^+, \emptyset).
\]
The relaxation of $(\propos, \actions, \initial, \goal)$ is $(\propos,
\actions^{\relaxed}, \initial, \goal)$, where $\actions^{\relaxed} :=
\{ a^{\relaxed} \mid a \in \actions \}$. An action sequence $\langle
a_1, \dots, a_n \rangle \in \actions^*$ is a {\em relaxed plan} for
$(\propos, \actions, \initial, \goal)$ if $\langle a_1^{\relaxed},
\dots,a _n^{\relaxed} \rangle$ is a plan for $(\propos, \actions^{\relaxed},
\initial, \goal)$.
\end{def1}



Ignoring the delete lists simplifies the task because the action
preconditions and the goal are all positive. We identify a number of
desirable properties that the relaxation has. We will later define
relaxations for numeric variables that have the same properties.


\begin{def1}\label{def:strips-relaxeddecision}
Let \stripsrelaxedplansat\ denote the following problem.

\medskip {\em Assume a \strips\ task $(\propos, \actions, \initial,
  \goal)$. Is the relaxation of $(\propos, \actions, \initial, \goal)$
  solvable?}
\end{def1}

\begin{proposition}\label{pro:stripsrelaxreasonable}
  The relaxation given in Definition~\ref{def:strips-relaxation} is
  adequate, \ie the following holds true.

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: any plan that solves the original task also
  solves the relaxed task, \ie assuming a \strips\ task $(\propos,
  \actions, \initial, \goal)$, any plan for $(\propos, \actions,
  \initial, \goal)$ is also a relaxed plan for $(\propos, \actions,
  \initial, \goal)$.
\item {\em Basic informedness}: the preconditions and goals can
  trivially be achieved in the original task if and only if the same
  holds in the relaxed task, \ie assuming a \strips\ task $(\propos,
  \actions, \initial, \goal)$, $\langle \rangle$ is a plan for
  $(\propos, \actions, \initial, \goal)$ if and only if $\langle
  \rangle$ is a relaxed plan for $(\propos, \actions, \initial,
  \goal)$, and for $a \in \actions$, $\result(\initial, \langle
  \rangle) \supseteq \pre(a)$ if and only if $\result(\initial,
  \langle \rangle) \supseteq \pre(a^{\relaxed})$.
\item {\em Polynomiality}: the relaxed task can be solved in
  polynomial time, \ie deciding \stripsrelaxedplansat\ is in \poly.
\end{enumerate}
\end{sloppypar}
\end{proposition}



The proof is trivial -- admissibility and basic informedness follow
directly from the definitions, and polynomiality has been proved
earlier by Bylander \shortcite{bylander:ai-94}. The proof can be found
in Appendix~\ref{proofs}.


If we want to use the length of relaxed plans as a heuristic function,
the properties stated by Proposition~\ref{pro:stripsrelaxreasonable}
are important for the following reasons. Admissibility tells us that
optimal relaxed plan length is an admissible heuristic, since the
optimal real plan is also a relaxed plan.\footnote{Note that using the
  term ``admissibility'' this way slightly abuses notation, as
  admissibility usually refers to a property of the heuristic
  function, not the technique (relaxation, in our case) it is based
  on.} Also, we will not mistake a solvable state for a dead end: if
there is no relaxed plan then there is no real plan either (more on
this below). The ``only if'' directions in basic informedness tell us
that the relaxation does not give us any constraints for free (for
example, the heuristic value will be zero only in goal states). If the
heuristic does not have these properties then possibly parts of the
problem must be solved in regions where there is no heuristic
information at all (like when the heuristic value is already zero but
no goal state is reached yet).\footnote{The formulation of basic
  informedness might seem unnecessarily complicated. We chose the
  general formulation at hand so that the definition can easily be
  transferred to other relaxation techniques, like the ones we
  introduce later.} Polynomiality tells us that we can compute the
heuristic function efficiently.


























\subsection{Solving Relaxed Tasks}
\label{strips:rplans}




Ideally, given a search state $s$, we would like to know how many
relaxed actions are {\em at least} needed to reach the goal, \ie we
would like to know what the length of an {\em optimal} relaxed plan is
(this would be an admissible heuristic, \cf\ above). But finding
optimal relaxed plans is still intractable \cite{bylander:ai-94}. So
instead we compute arbitrary, \ie not necessarily optimal, relaxed
plans. This is done with a \graphplan-style algorithm
\cite{blum:furst:ai-97,hoffmann:nebel:jair-01}. Given a search state
$s$ in a \strips\ task $(\propos, \actions, \initial, \goal)$, we
first build a relaxed planning graph starting from $s$, \ie for the
task $(\propos, \actions, s, \goal)$. Then we extract a relaxed plan
from that graph. The graph building algorithm is depicted in
Figure~\ref{code:RPG_building}.





\begin{figure}[htb]
{\small
\begin{tabbing}
$P_0$ := $s$\\
$t$ := $0$\\
{\bf while} $\goal \not \subseteq P_t$ {\bf do}\\
\hspace{0.3cm} \= $A_{t}$ := $\{ a \in \actions \mid \pre(a)
\subseteq P_t \}$\\
\> $P_{t+1}$ := $P_t \cup \bigcup_{a \in A_{t}} \eff(a)^+$\\
\> {\bf if} \= $P_{t+1} = P_t$ {\bf then} fail {\bf endif}\\
\> $t$ := $t + 1$\\
{\bf endwhile}\\
$finallayer$ := $t$, succeed
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:RPG_building}Building a relaxed planning graph
  for a task $(\propos, \actions, s, \goal)$.}
\vspace{-0.0cm}
\end{figure}





The planning graph in the relaxed case is simply represented as a
sequence $P_0,$ $A_0,$ $\dots,$ $A_{t-1},$ $P_t$ of proposition sets
and action sets. These are built incrementally in the obvious fashion,
starting with $P_0 = s$ as the initial layer, and iteratively
inserting the add effects of all applicable actions. The algorithm
fails if at some point before reaching the goals no new propositions
come in. This only happens when the relaxed task is unsolvable.





\begin{proposition}\label{pro:rpg_suff}
  Assume a \strips\ task $(\propos, \actions, \initial, \goal)$, and a
  state $s$. If the algorithm depicted in
  Figure~\ref{code:RPG_building} fails, then there is no relaxed plan
  for $(\propos, \actions, s, \goal)$.
\end{proposition}


The proof is in Appendix~\ref{proofs}. The main argument is that, if
two consecutive proposition layers are identical, then the same will
hold true at all later layers so the graph has reached a fixpoint.


In case the goals can be reached at layer $finallayer$, we call the
relaxed plan extraction mechanism depicted in
Figure~\ref{code:plan_extraction}. The {\em level} of each proposition
$p$ (action $a$) here is the first layer in the relaxed planning graph
at which $p$ ($a$) appears, \ie the minimum $t$ such that $p \in P_t$
($a \in A_t$).






\begin{figure}[htb]
  {\small
\begin{tabbing}
{\bf for} \= $t$ := $1, \dots, finallayer$ {\bf do}\\
\> $\goal_t$ := $\{ g \in \goal \mid level(g) = t \}$\\
{\bf endfor}\\
{\bf for} $t$ := $finallayer, \dots, 1$ {\bf do}\\
\> {\bf for} \= all $g \in \goal_t$ {\bf do}\\
\> \> select $a$, $level(a) = t - 1$, $g \in \eff(a)^+$\\
\> \> {\bf for} \= all $p \in \pre(a)$ {\bf do}\\
\> \> \> $\goal_{level(p)} \cup = \{ p \}$\\
\> \> {\bf endfor}\\
\> {\bf endfor}\\
{\bf endfor}
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:plan_extraction}Extracting a relaxed
  plan for a task $(\propos, \actions, s, \goal)$ (levels and
  $finallayer$ computed by the algorithm in
  Figure~\ref{code:RPG_building}).}  \vspace{-0.0cm}
\end{figure}





Relaxed plan extraction is based on a sequence $\goal_1, \dots,
\goal_{finallayer}$ of goal and sub-goal sets. Goals and sub-goals are
always inserted into the set at their respective level, \ie at the
position of their first appearance in the relaxed planning graph. The
goal sets are initialized by inserting the respective (top-level)
goals. A backwards loop then selects, at each layer, actions to
support the respective goal set. All goals or sub-goals $g$ are
supported, and the preconditions of the respective actions become new
sub-goals. This way, upon termination the selected actions can be used
to form a relaxed plan for the state at hand.






\begin{proposition}\label{pro:rplan_suff}
  Assume a \strips\ task $(\propos, \actions, \initial, \goal)$, and a
  state $s$ for which the algorithm depicted in
  Figure~\ref{code:RPG_building} reaches the goals. The actions
  selected by the algorithm depicted in
  Figure~\ref{code:plan_extraction} form a relaxed plan for $(\propos,
  \actions, s, \goal)$.
\end{proposition}



As all goals and sub-goals are supported, arranging the actions
selected at each layer in an arbitrary order yields a relaxed plan.
The proof is in Appendix~\ref{proofs}.


























\subsection{FF}
\label{strips:ff}






Based on the relaxed plan information, a heuristic state space planner
is easily implemented. Choices must be made on how to use the relaxed
plans, and how to arrange the search strategy. We describe the
specific methods used in \ff, which are very efficient in many
\strips\ and \adl\ benchmarks \cite{hoffmann:nebel:jair-01}. The
extended system uses straightforward adaptions of these methods. We
define a heuristic function, a search strategy, and a pruning
technique. The heuristic estimates goal distances as relaxed plan
length.







\begin{def1}\label{def:ff-heuristic}
  Assume a \strips\ task $(\propos, \actions, \initial, \goal)$, and a
  state $s$. The {\em \ff\ heuristic value} $h(s)$ for $s$ is defined
  as follows. If the algorithm depicted in
  Figure~\ref{code:RPG_building} fails, $h(s) := \infty$. Otherwise,
  $h(s) := \sum_{t=1}^{finallayer} |A_t|$ where $A_t$ is the set of
  actions selected at layer $t$ by the algorithm depicted in
  Figure~\ref{code:plan_extraction}.
\end{def1}




If there is no relaxed plan for a state, then the heuristic value is
set to $\infty$. This is justified by the first property proved in
Proposition~\ref{pro:stripsrelaxreasonable}: when there is no relaxed
plan then there can be no real plan either, \ie the state is a {\em
  dead end} in the sense that the goals can not be reached from it.
Such states can be pruned from the search. The search scheme we use is
a kind of hill-climbing procedure using a complete lookahead to find
better states. See Figure~\ref{code:ehc}.






\begin{figure}[htb]
{\small
\begin{tabbing}
initialize the current plan to the empty plan $\; <>$\\
$s$ := $\initial$\\
{\bf while} \= $h(s) \neq 0$ {\bf do}\\
\> starting from $s$, perform \= breadth first search for a state $s'$ with $h(s') <
h(s)$,\\
\> \> avoiding repeated states using a hash table,\\
\> \> not expanding states $s''$ where $h(s'') = \infty$\\
\> {\bf if} \= no such state can be found {\bf then} fail {\bf endif}\\
\> add the actions on the path to $s'$ at the end of the current plan\\
\> $s$ := $s'$\\
{\bf endwhile}\\
output current plan, succeed
\end{tabbing}}
\caption{\label{code:ehc}The \ehc\ algorithm, for a task with heuristic $h$.}
\end{figure}





Enforced hill-climbing, like (standard) hill-climbing, starts out in
the initial state and performs a number of search iterations trying to
improve on the heuristic value, until a state with zero value is
reached. While normally, iterative improvement is done by selecting
one best direct successor of the current search state, \ehc\ uses a
complete breadth first search to find a strictly better, possibly
indirect, successor. The search cuts out states that have been seen
earlier during the same iteration, and does not expand states that the
heuristic function recognizes as dead ends. This strategy works well
when the better successors are usually nearby, which is the case in
many planning benchmarks when using the \ff\ heuristic function
\cite{hoffmann:ijcai-01,hoffmann:aips-02}. When there is no better
successor below the current search node, the algorithm fails (more on
this below).






We finally define a pruning technique, selecting a set of the most
promising successors to each search state. The unpromising successors
can then be ignored. A promising successor is a state generated by an
action that is helpful in the following sense.



\begin{def1}\label{def:ff-helpful}
  Assume a \strips\ task $(\propos, \actions, \initial, \goal)$, and a
  state $s$ for which the algorithm depicted in
  Figure~\ref{code:RPG_building} reaches the goals. The set of {\em
    helpful actions} $H(s)$ to $s$ is defined as
\[
 H(s) := \{ a \in \actions \mid \eff^+(a) \cap \goal_1 \neq \emptyset
 \},
\]
where $\goal_1$ is the set of sub-goals constructed at layer $1$ by
  the algorithm depicted in Figure~\ref{code:plan_extraction}.
\end{def1}




In other words, an action is considered helpful if it achieves at
least one of the lowest level goals in the relaxed plan to the state
at hand. The helpful actions information is used as a pruning
technique. During a breadth first search iteration in \ehc, when
expanding a state $s$, only the states generated by actions in $H(s)$
are included into the search space. Note that states $s$ where the
relaxed planning graph does not reach the goals have $h(s) = \infty$
so do not get expanded anyway.






In general, neither \ehc\ nor helpful actions pruning maintain
completeness. The algorithm fails if \ehc\ gets caught in a dead end
state. This can happen because the search does not backtrack over its
decisions, and because the heuristic function can return a value below
$\infty$ for a dead end state. The algorithm also fails if helpful
actions pruning cuts out important states, which can happen because
the technique is a non-admissible approximation of usefulness. We deal
with this issue by employing a safety-net solution, \ie if \ehc\ fails
then the planner starts from scratch using a complete heuristic search
engine, without any pruning technique. The search engine used is what
Russel and Norvig \shortcite{russel:norvig:95} term {\em greedy
  best-first} search.  This is a weighted $A^*$ strategy where the
weight $w_g$ of the node cost in the equation $f(s) = w_g * g(s) + w_h
* h(s)$ is $w_g = 0$, \ie search simply expands all search nodes by
increasing order of goal distance estimation. Repeated states are
avoided in the obvious way by keeping a hash table of visited states.

























\section{Numeric State Variables}
\label{numeric}





We introduce notation for the numeric part of the \pddl2.1 language
(i.e., \pddl2.1 level 2) defined by Fox and Long
\cite{fox:long:aips-02b}, used at \ipcthree. We restrict ourselves to
\strips\ for readability reasons. Extensions to \adl\ will be
summarized in Section~\ref{metric-ff:adl}. All sets are assumed to be
finite unless stated otherwise.



In addition to the propositions $\propos$, we now have a set $\vars$
of numeric variables. Notationally, we say $\vars = \{ v^1, \dots, v^n
\}$ (throughout the article, $n$ will denote the number of numeric
variables). A {\em state} $s$ is a pair $s = (\proposof(s),
\varsof(s))$ where $\proposof(s) \subseteq \propos$ is a set of
propositions and $\varsof(s) = (\varsof^1(s), \dots, \varsof^n(s)) \in
\rationale^{n}$ is a vector of rational numbers (the obvious semantics
being that $\proposof(s)$ are the true propositions, and
$\varsof^i(s)$ is the value of $v^i$).\footnote{We ignore, for
  readability reasons, the possibility given in Fox and Long's
  original language that a variable can have an undefined value until
  it is assigned one. Our methodology can be easily extended -- and is
  in fact implemented -- to deal with this case.}



An {\em expression} is an arithmetic expression over $\vars$ and the
rational numbers, using the operators $+$, $-$, $*$, and $/$. A {\em
  numeric constraint} is a triple $(\expr, \comp, \expr')$ where
$\expr$ and $\expr'$ are expressions, and $\comp \in \{ <, \leq, =,
\geq, > \}$ is a {\em comparator}. A {\em numeric effect} is a triple
$(v^i, \ass, \expr)$ where $v^i \in \vars$ is a variable, $\ass \in \{
\asseff, \inceff, \deceff, \muleff, \diveff \}$ is an {\em assignment
  operator}, and $\expr$ is an expression (the effect right hand
side). A {\em condition} is a pair $(\proposof(\con), \varsof(\con))$
where $\proposof(\con) \subseteq \propos$ is a set of propositions and
$\varsof(\con)$ is a set of numeric constraints. An {\em effect} is a
triple $(\proposof(\eff)^+, \proposof(\eff)^-, \varsof(\eff))$ where
$\proposof(\eff)^+ \subseteq \propos$ and $\proposof(\eff)^- \subseteq
\propos$ are sets of propositions (the add- and delete-list), and
$\varsof(\eff)$ is a set of numeric effects such that $i \neq j$ for
all $(v^i, \ass, \expr), (v^j, \ass', \expr') \in
\varsof(\eff)$.\footnote{Fox and Long \shortcite{fox:long:aips-02b}
  make this assumption implicitly, by requiring that the outcome of an
  action is well-defined -- note that commutative effects on the same
  variable can be merged.} An {\em action} $a$ is a pair $(\pre(a),
\eff(a))$ where $\pre(a)$ is a condition and $\eff(a)$ is an effect.




The semantics of this language are straightforward. The {\em value}
$\expr(v)$ of an expression $\expr$ in a variable value vector $v$ (in
$s$, if $v$ is the numeric part $\varsof(s)$ of a state $s$) is the
rational number that the expression simplifies to when replacing all
variables with their respective values, or undefined if a division by
$0$ occurs. A constraint $(\expr, \comp, \expr')$ {\em holds} in a
state $s$, written $s \models (\expr, \comp, \expr')$, if the values
of $\expr$ and $\expr'$ are defined in $s$, and stand in relation
$\comp$ to each other. A condition $\con = (\proposof(\con),
\varsof(\con))$ holds in a state $s$, $s \models \con$, if
$\proposof(\con) \subseteq \proposof(s)$, and all numeric constraints
in $\varsof(\con)$ hold in $s$. The value $(v^i, \ass, \expr)(v)$ of a
numeric effect $(v^i, \ass, \expr)$ in a variable value vector $v$ (in
$s$, if $v$ is the numeric part $\varsof(s)$ of a state $s$) is the
outcome of modifying the value of $v^i$ in $s$ with the value of
$\expr$ in $s$, using the assignment operator $\ass$. A numeric effect
is {\em applicable} in $s$ if its value in $s$ is defined. An effect
$\eff = (\proposof(\eff)^+, \proposof(\eff)^-, \varsof(\eff))$ is
applicable in $s$ if all numeric effects in $\varsof(\eff)$ are
applicable in $s$. For such $\eff$ and $s$, $\eff(s)$ is the state
$s'$ where $\proposof(s') = \proposof(s) \setminus \proposof(\eff)^-
\cup \proposof(\eff)^+$, and $\varsof(s')$ is the value vector that
results from $\varsof(s)$ when replacing $\varsof^i(s)$ with $(v^i,
\ass, \expr)(s)$ for all $(v^i, \ass, \expr) \in \varsof(\eff)$.
Putting all of these definitions together, the {\em result} of
executing an action $a$ in a state $s$ is $\result(s, \langle a
\rangle) = \eff(a)(s)$ if $s \models \pre(a)$ and $\eff(a)$ is
applicable in $s$, undefined otherwise. In the first case, $a$ is said
to be applicable in $s$. For an action sequence $\langle a_1, \dots,
a_n \rangle$, $\result(s, \langle a_1, \dots, a_n \rangle)$ is as
usual defined recursively by $\result(s, \langle a_1, \dots, a_n
\rangle) = \result(\result(s, \langle a_1, \dots, a_{n-1} \rangle),
a_n)$ and $\result( s, \langle \rangle) = s$.





A {\em numeric task} is a tuple $(\vars, \propos, \actions, \initial,
\goal)$ where $\vars$ and $\propos$ are the variables and propositions
used, $\actions$ is a set of actions, $\initial$ is a state, and
$\goal$ is a condition. A sequence of actions $\langle a_1, \dots, a_n
\rangle \in \actions^*$ is a {\em plan} if the result of applying it
to $\initial$ yields a state that models $\goal$, $\result( \initial,
\langle a_1, \dots, a_n \rangle) \models \goal$.






In our algorithmic framework, we make distinctions between different
degrees of expressivity that we allow in numeric constraints and
effects, \ie between different {\em numeric languages}. A numeric
language is a tuple $(\comps, \effass, \effrh)$ where $\comps$ is a
possibly infinite set of numeric constraints, $\effass$ is a set of
assignment operators, and $\effrh$ is a possibly infinite set of
expressions. A task $(\vars, \propos, \actions, \initial, \goal)$
belongs to a language if all constraints, assignment operators, and
effect right hand sides are members of the respective sets.




The next three sections contain the technical part of this article.
They are organized as follows.

\begin{enumerate}
\item Section~\ref{relaxation} provides the theory on which \mff's
  heuristic function is based. The relaxation, ignoring delete lists
  as described in Section~\ref{strips:relaxation}, is extended to
  numeric variables. Section~\ref{relaxation:restricted} formalizes
  the key idea in a restricted numeric language, and states that the
  extended relaxation fulfills admissibility, basic informedness, and
  polynomiality.  Section~\ref{relaxation:monotonicity} abstracts from
  the restricted language, identifying generalized semantic properties
  that make the relaxation work. Section~\ref{relaxation:linear} then
  introduces the language of linear tasks, which can be brought into a
  linear normal form (LNF) that has these semantic properties. \mff's
  core planning algorithms are implemented for LNF tasks.
\item Section~\ref{rplans} introduces the algorithms implemented in
  \mff's heuristic function. The algorithms are extensions to the
  relaxed \graphplan\ methods described in
  Section~\ref{strips:rplans}. Section~\ref{rplans:restricted}
  describes the algorithms for the restricted language,
  Section~\ref{rplans:lnf} extends that to LNF tasks. We state
  formally that the algorithms are complete and correct. We also see
  that the algorithms are, in theory, less efficient than they could
  be. The number of relaxed planning graph layers built can be
  exponential in the size of the task encoding, in contrast to
  polynomiality of the relaxation as proved in
  Section~\ref{relaxation}. The reason why the implementation lags
  behind what is theoretically possible is that the implementation
  work was done before the theory was fully developed. However, from a
  practical point of view, it is at least debatable how important the
  potential exponentiality is (the number of relaxed planning graph
  layers built is bounded by the length of a shortest relaxed plan).
  Exploring this issue in depth is a topic for future work. More
  details are in Sections~\ref{relaxation:restricted}
  and~\ref{rplans:restricted}.
\item Section~\ref{metric-ff} details how the relaxed plan information
  is used to implement the \mff\ system. Section~\ref{metric-ff:basic}
  explains the extension of the basic \ff\ architecture as described
  in Section~\ref{strips:ff}. Section~\ref{metric-ff:adl} explains the
  extension to \adl, Section~\ref{metric-ff:cost} describes how
  flexible optimization criteria can be dealt with.
\end{enumerate}








\section{Relaxing Numeric State Variables}
\label{relaxation}








We show how the relaxation technique for \strips\ can naturally be
extended to the numeric context. We proceed in the three steps
outlined above.
















\subsection{A Restricted Language}
\label{relaxation:restricted}







The key idea in our relaxation becomes apparent when one considers the
context where constraints only compare variables to constants via
$\geq$ or $>$, there are only $\inceff$ and $\deceff$ effects, and the
effect right hand sides are positive constants. More formally, our
restricted language is:



\begin{tabbing}
$($ \= $\{ (v^i, \comp, c) \mid v^i \mbox{ variable}, \comp \in \{ \geq, > \}, c \in
\rationale \},$\\
\> $\{ \inceff, \deceff \},$\\
\> $\{ c \mid c \in \rationale, c > 0 \} \; )$
\end{tabbing}




In \strips, delete lists are troublesome because they falsify
propositions that we might need for preconditions or the goal. In the
restricted numeric language here, the $\deceff$ effects are
troublesome because they diminish the value of the affected variables.
The idea is therefore to ignore these effects.






\begin{def1}\label{def:restricted-relaxation}
  Assume a restricted numeric task $(\vars, \propos, \actions,
  \initial, \goal)$. The {\em relaxation} $a^{\relaxed}$ of an action
  $a \in \actions$, $a = (\pre(a), (\proposof(\eff(a))^+,
  \proposof(\eff(a))^-, \varsof(\eff(a))))$, is defined as
\[
a^{\relaxed} := (\pre(a), (\proposof(\eff(a))^+, \emptyset, \{ (v^i,
\inceff, \expr) \mid (v^i, \inceff, \expr) \in \varsof(\eff(a)) \} )).
\]
The relaxation of $(\vars, \propos, \actions, \initial, \goal)$ is
$(\vars, \propos, \actions^{\relaxed}, \initial, \goal)$, where
$\actions^{\relaxed} := \{ a^{\relaxed} \mid a \in \actions \}$. An
action sequence $\langle a_1, \dots, a_n \rangle \in \actions^*$ is a
{\em relaxed plan} for $(\vars, \propos, \actions, \initial, \goal)$
if $\langle a_1^{\relaxed}, \dots,a _n^{\relaxed} \rangle$ is a plan
for $(\vars, \propos, \actions^{\relaxed}, \initial, \goal)$.
\end{def1}




The above relaxation is adequate in the restricted language, in the
precise sense introduced in Section~\ref{strips:relaxation}.





\begin{def1}\label{def:restricted-relaxeddecision}
Let \restrictedrelaxedplansat\ denote the following problem.

\medskip {\em Assume a restricted numeric task $(\vars, \propos,
  \actions, \initial, \goal)$. Is the relaxation of $(\vars, \propos,
  \actions, \initial, \goal)$ solvable?}
\end{def1}



\begin{theorem}\label{the:restrictedrelaxreasonable}
  The relaxation given in Definition~\ref{def:restricted-relaxation}
  is adequate, \ie the following holds true.

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: assuming a restricted numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, any plan for $(\vars, \propos,
  \actions, \initial, \goal)$ is also a relaxed plan for $(\vars,
  \propos, \actions, \initial, \goal)$.
\item {\em Basic informedness}: assuming a restricted numeric task
  $(\vars, \propos, \actions, \initial, \goal)$, $\langle \rangle$ is
  a plan for $(\vars, \propos, \actions, \initial, \goal)$ if and only
  if $\langle \rangle$ is a relaxed plan for $(\vars, \propos,
  \actions, \initial, \goal)$, and for $a \in \actions$,
  $\result(\initial, \langle \rangle) \models \pre(a)$ if and only if
  $\result(\initial, \langle \rangle) \models \pre(a^{\relaxed})$.
\item {\em Polynomiality}: deciding \restrictedrelaxedplansat\ is in
  \poly.
\end{enumerate}
\end{sloppypar}
\end{theorem}


The detailed proof can be found in Appendix~\ref{proofs}. It is a
straightforward extension of the \strips\ proof, exploiting the
correspondence between pre/goal-conditions, add lists, and delete
lists on the one hand, and $x \geq [>] c$ constraints, $\inceff$
effects, and $\deceff$ effects on the other hand. The only tricky part
lies in proving polynomiality, precisely in how to handle repeated
increasing effects on the same variable. Such effects might have to be
applied an exponential number of times. Consider the tasks, for $n \in
\natuerliche$, where $v^i$ is initially $0$, $v^i \geq n$ is the goal,
and we have an action effect $(v^i, \inceff, 1)$. For task $n$, the
shortest relaxed plan comprises $n$ steps, which is exponentially long
in the size of a non-unary encoding of $n$. The trick one can use to
decide relaxed solvability in polynomial time is a simple $\infty$
handling. The polynomial decision process is a forward fixpoint
procedure similar to building a relaxed planning graph. As soon as
there appears an action $a$ that increases a variable $v^i$, one can
assume that $v^i$'s value is $\infty$, reflecting the fact that
$v^i$'s value can be made arbitrarily high by applying $a$ a
sufficient number of times. As indicated earlier, the current
implementation of \mff, which we will describe in
Section~\ref{rplans}, does {\em not} make use of such an $\infty$
handling technique, and may thus build an exponential number of
relaxed planning graph layers for a search state. More on this in
Section~\ref{rplans:restricted}.






A few words on related work are in order here. If one relaxes numeric
tasks by ignoring all the numeric constructs, then one gets
admissibility and polynomiality, but not basic informedness. The
heuristic methods used in \sapa\ \cite{do:kambhampati:ecp-01} and
\grtr\ \cite{refanidis:vlahavas:ecai-00} come quite close to this
extreme case. In fact, \sapa's heuristic constructs a relaxed plan
that completely ignores the numeric part of the task. Then the
``resource consumption'' of the resulting relaxed plan (roughly, the
sum of all decreasing effects on numeric variables) is used to
estimate the number of actions that would be needed to re-produce
these resources, and that number is added to the heuristic value of
the state at hand.  In particular, this method ignores all numeric
goals and preconditions and thus lacks basic informedness. Similarly,
the heuristic technique used in \grtr\ considers resource consumption
as another form of state cost, but does not take any numeric
precondition or goal constraints into account. The heuristic technique
does not make explicit use of relaxed plans so our definitions can not
be directly applied. However, as numeric constraints are not
considered, the heuristic value of a purely numeric action
precondition is zero even if the precondition is not true in the
current state, and the technique thus also lacks basic informedness.

































\subsection{Monotonicity, and a Dynamic Relaxation}
\label{relaxation:monotonicity}







We now have a look behind the scenes of the relaxation technique that
we used above for the restricted language. We abstract from the syntax
of the numeric constructs, and focus on their semantics instead. We
define an extension of our relaxation to the general context, and
identify a group of semantic properties that make this relaxation
adequate. We will later focus on a syntactically restricted language,
linear tasks, where it is easier to see that the relaxation is
adequate. The main intention of the abstract work in this subsection
is to provide some theoretical background on the general
characteristics for which our relaxation works.




Let us first ignore semantic issues, and simply extend the definition
of our relaxation. In general, the definition is not as easy as for
the restricted case in Definition~\ref{def:restricted-relaxation}.
While our idea is still to ignore decreasing effects, the difficulty
is that whether an effect is decreasing or not can depend on the
context it is executed in.\footnote{It is common practice to refer to
  $\inceff$ effects as ``increasing effects'', and to $\deceff$
  effects as ``decreasing effects''. In contrast to that, we
  distinguish between syntax and semantics by using $\inceff$ /
  $\deceff$ to denote syntax, and increasing / decreasing to denote
  semantics (of arbitrary numeric effects).} As a simple example, say
an action $a$ has a numeric effect $(v^i, \inceff, v^j)$. If $v^j$ has
a negative value in the state of $a$'s execution, this effect
decreases the value of $v^i$ instead of increasing it. So we can not
statically relax $a$ by ignoring parts of its specification. Instead,
our relaxation now is dynamic: we relax the state transition function.




\begin{def1}\label{def:monotonic-relaxation}
  Assume a state $s$ and an action $a = (\pre(a), \eff(a))$. The {\em
    relaxed result} of executing $a$ in $s$ is $\result^{\relaxed}(s,
  a) = s'$ such that $\proposof(s') = \proposof(s) \cup
  \proposof(\eff(a))^+$, and $\varsof(s')$ is the value vector that
  results from $\varsof(s)$ when replacing $\varsof^i(s)$ with $(v^i,
  \ass, \expr)(s)$ for all $(v^i, \ass, \expr) \in \varsof(\eff)$ such
  that $(v^i, \ass, \expr)(s) > \varsof^i(s)$.
\end{def1}



For an action sequence $\langle a_1, \dots, a_n \rangle$,
$\result^{\relaxed}(s, \langle a_1, \dots, a_n \rangle)$ is defined
recursively as with the original $\result$ function in
Section~\ref{strips}. Note that, in \strips\ and the restricted
numeric language, Definition~\ref{def:monotonic-relaxation} comes down
to exactly the relaxations we have used before.



Having generalized our relaxation, we now want to know in exactly
which situations this relaxation is adequate. Obviously, ignoring the
decreasing effects is not adequate in general. As a simple example, if
the value of a variable $v^i$ is initially $0$, there is an effect
$(v^i, \deceff, 1)$, and the goal requires that $v^i < 0$, then the
``relaxation'' renders the task unsolvable. Intuitively, the
relaxation is adequate if it is always preferable for the numeric
variables to have higher values. Formalizing this intuition turns out
to be a bit tricky. Recall our three conditions for adequacy of a
relaxation: admissibility (any real plan is also a relaxed plan),
basic informedness (the relaxation does not ignore any precondition or
goal constraints), and polynomiality (solvability of the relaxation
can be decided in polynomial time). Basic informedness is obviously
given for our relaxation here. Not so admissibility and polynomiality.
Say we want to make sure that each real plan is also a relaxed plan.
Not only must the numeric constraints prefer higher variable values,
but the effects must also. As an example, say we have $v^i = v^j = 0$
initially, the goal $v^i \geq 1$, an action effect $(v^i, \deceff,
v^j)$, and an action effect $(v^j, \deceff, 1)$. If we ignore the
decreasing effect on $v^j$, we can not solve the task because for the
effect $(v^i, \deceff, v^j)$ it is better when $v^j$ takes on lower
values. Considering polynomiality, to ensure that relaxed solvability
can be decided in polynomial time, all kinds of subtleties must be
handled. Say we want to shortcut repeated action application by an
$\infty$ trick, \ie by assuming that repeated application of
increasing effects makes the affected variable diverge (as is the case
in the restricted language above). Then we will get in trouble if
repeated (relaxed) application of an action makes the value of the
affected variable converge.\footnote{As an example, if $v^i$ is
  initially $1$ and we have an effect $(v^i, \inceff, 1 -
  \frac{v^i}{2})$ then repeated application of the effect makes the
  value of $v^i$ converge to $2$ (the value of $v^i$ after $n$
  applications is $2 - \frac{1}{2}^n$).}  Similar difficulties arise
when an expression in a constraint does not diverge with its
variables. Finally, it might be that the constraint looks correct when
inserting $\infty$, but can never be fulfilled with finite values. An
example of this is the constraint $v^i \geq v^i + 1$, which is
fulfilled when inserting $\infty$ for $v^i$.


In the following definition, we introduce a number of conditions that
are sufficient to ensure that none of the difficulties described above
appear. We will see that in ``monotonic'' tasks each real plan is also
a relaxed plan, and that in ``strictly monotonic'' tasks, given their
$\asseff$ effects are acyclic in a certain sense, relaxed plan
existence can be decided in polynomial time.

%
% REV: REMARK ON TOO STRONG, I.E. REACHABILITY OF STATES ETC. COULD BE
% TAKEN INTO ACCOUNT FOR  s AND  s' HERE... footnote??









\begin{def1}\label{def:monotonicity}
  Assume a numeric task $(\vars, \propos, \actions, \initial,
  \goal)$. The task is {\em monotonic} if, for all pairs of states $s$
  and $s'$ with $\forall v^i: \varsof^i(s) \leq \varsof^i(s')$, the
  following holds.
\begin{itemize}
\item[(1)] For all numeric constraints $(\expr, \comp, \expr')$
  occurring in the task:
\[
s \models (\expr, \comp, \expr') \Rightarrow s' \models (\expr, \comp, \expr').
\]
\item[(2)] For all numeric effects $(v^i, \ass, \expr)$ occurring in
  the task:
\[
(v^i, \ass, \expr)(s) \leq (v^i, \ass, \expr)(s'),
\]
where the $\leq$ relation holds only if both values are defined.
\end{itemize}
The task is {\em strongly monotonic} if the above and the following hold.
\begin{itemize}
\item[(3)] For all states $s$ and $s'$ as above, for all numeric
  effects $(v^i, \ass, \expr)$ occurring in the task, with $\ass \in \{
  \inceff, \deceff, \muleff, \diveff \}$: 
\[
(v^i, \ass, \expr)(s) - v^i(s) \leq (v^i, \ass, \expr)(s') - v^i(s'),
\]
where the $\leq$ relation holds only if both  values are defined.
\item[(4)] For all expressions $\expr$ occurring in the task:
\[
\forall v^i \in \varsof(\expr): \lim_{v^i \to \infty} \expr = \infty,
\]
where $\varsof(\expr)$ denotes the set of all variables contained in
$\expr$. 
\item[(5)] For all numeric constraints $(\expr, \comp, \expr')$
  occurring in the task:
\[
\exists s: s \models (\expr, \comp, \expr').
\]
\end{itemize}
\end{def1}




Some explanation of this lengthy definition is in order. Condition (1)
ensures that the numeric constraints prefer higher variable values.
Condition (2) does the same for effects, requiring that the value of
an effect can only increase with the variables. In particular, the
value does not become undefined, \ie no division by zero occurs when
the variables grow. These two conditions suffice to make each real
plan a relaxed plan, as higher variable values are always preferable.
Conditions (3) to (5) aim at making relaxed solvability easy to
decide. Condition (3) is a stronger version of condition (2). We
require that the {\em value that the effect adds to the affected
  variable} increases with the variables.  This ensures that repeated
application of the effect causes the value of the affected variable to
diverge. To illustrate this, an effect $(v^i, \inceff, -v^j + c)$
fulfills condition (2) but not condition (3). The outcome of this
effect is always $c$, which is monotonic in its (zero) variables but
affects $v^i$ more as $v^i$'s own value becomes higher.  Condition (4)
postulates that all expressions diverge in all variables, and
condition (5) postulates that to all constraints there is a finite
variable assignment that makes these constraints true.  Together with
condition (1) these requirements ensure that the constraints will
eventually be fulfilled when increasing the values of the
variables.\footnote{One could weaken conditions (1) to (3) of
  Definition~\ref{def:monotonicity} by exploiting the fact that we are
  only interested in {\em reachable} states. It does not matter if,
  e.g., a constraint is not monotonic in a region of variable values
  that will never be reached due to the semantics of the task. \mff\ 
  implements no such analysis techniques, except throwing away actions
  -- and with them, numeric constraints and effects -- whose
  preconditions can not be reached in the relaxed planning graph for
  the initial state, when ignoring all numeric constructs. Exploring
  the topic in more depth is future work.}

The $\asseff$ effects are separated out from the definition of strong
monotonicity, \ie while we do postulate condition (2) for them, we do
not postulate condition (3). Postulating condition (3) for $\asseff$
effects would also suffice. But this condition does not hold for even
the simplest form of $\asseff$ effects, namely $(v^i, \asseff, c)$,
assigning a constant to a variable. Note that this is in principle the
same effect as the example given above, $(v^i, \inceff, -v^j + c)$.
Effects of this kind are common even in the limited suits of
benchmarks that are currently available (e.g., when filling up a tank,
the fuel level is assigned the maximum level). So we identify a
different sufficient criterion that makes $\asseff$ effects tractable,
and that captures the common forms of these effects.  Computing the
maximum outcome of a set of assignment effects, in the relaxation and
under condition (2), becomes easy if the value changes on each single
variable can not be propagated into their own value.  The proof
argument is that, if, transitively, a change on $v^i$ can not
influence $v^i$'s own value then all one needs to do is to perform
value propagation steps, at each step computing the maximum assignment
available for each variable. After at most as many steps as there are
variables, the values will be fixed. We formalize the possible value
propagations with a straightforward graph definition.




\begin{def1}\label{def:cyclefree}
  Assume a numeric task $(\vars, \propos, \actions, \initial,
  \goal)$. The task has {\em acyclic $\asseff$ effects} if the graph
  $(\vars, E)$ is cycle-free, where
\[
E = \{ (v^i, v^j) \in \vars \times \vars \mid \exists a \in \actions,
(v^j, \asseff, \expr) \in \varsof(\eff(a)): v^i \in \varsof(\expr) \},
\]
with $\varsof(\expr)$ denoting the set of all variables contained in
$\expr$.  
\end{def1}



We now state in which ways our definitions imply adequacy of ignoring
decreasing effects as a relaxation. In the notation for the relaxed
plan existence decision problem, we abstract from syntactic issues,
and assume that a well-formed input task to the decision procedure is
strongly monotonic and has acyclic $\asseff$ effects.




\begin{def1}\label{def:monotonic-relaxeddecision}
Let \monotonicrelaxedplansat\ denote the following problem.

\medskip {\em Assume a numeric task $(\vars, \propos, \actions,
  \initial, \goal)$. Is there a relaxed plan for $(\vars, \propos,
  \actions, \initial, \goal)$, provided the task is strongly monotonic
  and has acyclic $\asseff$ effects?}
\end{def1}



\begin{theorem}\label{the:monotonicrelaxreasonable}
  The relaxation given in Definition~\ref{def:monotonic-relaxation} is
  adequate for strongly monotonic tasks with acyclic $\asseff$
  effects. Precisely the following holds true.

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: assuming a monotonic numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, any plan for $(\vars, \propos,
  \actions, \initial, \goal)$ is also a relaxed plan for $(\vars,
  \propos, \actions, \initial, \goal)$.
\item {\em Basic informedness}: assuming a numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, $\langle \rangle$ is a plan
  for $(\vars, \propos, \actions, \initial, \goal)$ if and only if
  $\langle \rangle$ is a relaxed plan for $(\vars, \propos, \actions,
  \initial, \goal)$, and for $a \in \actions$ $\result(\initial,
  \langle \rangle) \models \pre(a)$ if and only if
  $\result^{\relaxed}(\initial, \langle \rangle) \models \pre(a)$.
\item {\em Polynomiality}: deciding \monotonicrelaxedplansat\ is in
  \poly.
\end{enumerate}
\end{sloppypar}
\end{theorem}



The proof, given in Appendix~\ref{proofs}, is basically a
straightforward exploitation of the properties ensured by the above
definitions. Note that Theorem~\ref{the:monotonicrelaxreasonable} only
identifies sufficient criteria that make our relaxation work.
Interesting questions are, are there other, maybe weaker, criteria? As
a concrete example, there seem to be certain cases of cyclic
assignment effects that can be easily handled. What exactly are these
cases? Answering these questions is a topic for future work.




Another thing we have not dealt with is how our semantic constraints
translate to the syntax of the arithmetic expressions that are allowed
in \pddl2.1.  We do not consider the details of this but base the rest
of the article on a subset of \pddl2.1 where the required semantic
properties can easily be achieved -- the language for which the \mff\ 
system is actually implemented. Extending the system to richer
languages is an open research topic.



























\subsection{Linear Tasks, and LNF}
\label{relaxation:linear}








The \mff\ system is implemented to deal with what we call {\em linear}
tasks. This is the language of numeric tasks where there are no
$\muleff$ or $\diveff$ effects, and the numeric variables are only
used in linear expressions. More formally:





\begin{tabbing}
$($ \= $\{ (\expr, \comp, \expr') \mid \expr, \expr' \mbox{ linear
  expression}, \comp \mbox{ arbitrary} \},$\\
\> $\{ \asseff, \inceff, \deceff \},$\\
\> $\{ \expr \mid \expr \mbox{ linear expression} \} \; )$
\end{tabbing}




\mff's implementation allows for tasks that are linear after the
following pre-processing step. Assume we are given a planning task
$(\vars, \propos, \actions, \initial, \goal)$. A variable $v^i \in
\vars$ is a {\em task constant} if $v^i$ is not affected by the effect
of any action in $\actions$. An expression is a task constant if all
variables occurring in it are task constants. The pre-process replaces
all task constants with the respective rational numbers resulting from
inserting the initial variable values.\footnote{If, in a quotient
  $(\expr / \expr')$, $\expr'$ simplifies to $0$ then the expression
  is undefined and the respective constraint can never be fulfilled /
  the respective action's effects can never become applicable. In this
  case one can replace the constraint with \false / remove the
  action.}





% DAVID hier: linear fns monoton in all vars, exploit that to make them 
% monotone in same dir, by replacing negative monotone occurences
% with new, inverse, vars (in the relaxation, these vars then correspond 
% to the possible min value the org vars can take on) (reviewer
% comments?)
% oder was???
Linear tasks are, of course, not necessarily monotonic. In fact, all
of the illustrative counter examples we have given above are linear.
But linear functions are monotonic, more precisely strictly monotonic
and diverging, in all variables, either in the positive or in the
negative sense. The idea is to introduce, for a variable $v^i$ that is
used in the negative sense at some point, an {\em inverted} variable
$-v^i$ that always takes on the value $(-1) * v^i$. One can then
replace $v^i$ with $-v^i$ at the points where $v^i$ is used
negatively. When this has been done for all variables, the task is
(strictly) monotonic: all variables are only used in the positive
sense (more details below). Introducing inverted variables can be
viewed as a shortcut way of informing the heuristic function about
which places to use the variables in the positive or in the negative
sense.\footnote{David Smith, personal communication.} We will return
to this issue when considering \mff's heuristic algorithms in
Section~\ref{rplans:lnf}.




Given a linear task, \mff\ transforms the task into what we call its
{\em linear normal form} (LNF). In an LNF task, the expressions are
weighted sums of variables, where the weights are all greater than
$0$. The transformation process works as follows. First, a series of
simple steps transforms the task into the following language.



\begin{tabbing}
$($ \= $\{ (\sum_{j \in X} c^j * v^j + c, \geq [>], 0) \mid c^j, c \in
\rationale, c^j \neq 0 \},$\\
\> $\{ \asseff, \inceff \},$\\
\> $\{ \sum_{j \in X} c^j * v^j + c \mid c^j, c \in
\rationale, c^j \neq 0 \} \; )$
\end{tabbing}



To achieve this language format, one replaces all constraints $(\expr,
=, \expr')$ with $(\expr, \leq, \expr')$ and $(\expr, \geq, \expr')$,
and all effects $(v^i, \deceff, \expr)$ with $(v^i, \inceff, -\expr)$.
The rest is a matter of normalizing linear functions. The language
format differs from LNF only in that the variable weights may be
negative. This, of course, makes all the difference. Reconsider the
example where a variable $v^i$ is initially $0$, there is an action
$a$ with effect $(v^i, \deceff, 1)$, and the goal requires that $v^i <
0$. We take this as the running example in the following. In the above
language format, $a$'s effect is $(v^i, \inceff, -1)$, and the goal
requires that $(-1) * v^i > 0$. Due to the negative weighting of $v^i$
in the goal condition, ignoring decreasing effects is not viable.




The way we introduce inverted variables is an extension to the
methodology that eliminates negative preconditions in \strips\ 
planning (a technique first introduced by Gazen and Knoblock
\shortcite{gazen:knoblock:ecp-97}). The process works as follows.
Initialize the set $T$ of translated variables to $T := \emptyset$.
Iterate until there are no more negative weights, otherwise select an
(arbitrary) occurrence $c^j * v^j$, $c^j < 0$, in a weighted sum.
Introduce a new variable $-v^j$.  Set $-v^j(\initial) := (-1) *
v^j(\initial)$. For all effects $(v^j, \inceff [\asseff], \sum_{j \in
  X} c^j * v^j + c)$, introduce (into the effect set of the same
action) the effect $(-v^j, \inceff [\asseff], \sum_{j \in X} ((-1) *
c^j) * v^j + ((-1) * c))$. Set $T := T \cup \{ v^j, -v^j \}$. For all
occurrences of $c * v$ in weighted sums such that $c < 0$ and $v \in T$
(where $v$ may be one of the original variables or one of the
introduced inverse variables), replace $c * v$ with $((-1) * c) * -v$
(where $-v$ is the respective inverse counterpart to $v$). After at
most $|\vars|$ iterations, all weights are positive and the process
terminates. The task is then in the following linear normal form.




\begin{tabbing}
$($ \= $\{ (\sum_{j \in X} c^j * v^j + c, \geq [>], 0) \mid c^j, c \in
\rationale, c^j > 0 \},$\\
\> $\{ \asseff, \inceff \},$\\
\> $\{ \sum_{j \in X} c^j * v^j + c \mid c^j, c \in
\rationale, c^j > 0 \} \; )$
\end{tabbing}



For our running example, the LNF transformation is the following.
There are now two variables, $v^j$ and $-v^j$, both of which are
initially $0$. The action $a$ has two effects, namely $(v^i, \inceff,
-1)$ and $(-v^i, \inceff, 1)$. The goal condition is now expressed in
terms of the value of $-v^i$, and reads $-v^i > 0$. A single
application of the action achieves the goal, as it also does under the
relaxed transition function because the effect on $-v^i$ is
increasing.\footnote{Note that estimating the maximum value of $-v^i$
  is the same as estimating the minimum value of $v^i$. More on this
  in Section~\ref{rplans:lnf}.} In general, it is easy to see that LNF
tasks are strongly monotonic.






\begin{proposition}\label{pro:lnf_stronglymonotonic}
  Assume a linear numeric task $(\vars, \propos, \actions, \initial,
  \goal)$. If the task is in LNF, then it is strongly monotonic.
\end{proposition}

\begin{beweis}
  All conditions in Definition~\ref{def:monotonicity} are trivially
  fulfilled in LNF tasks. As examples, condition (1) is true because
  we only compare expressions that are (positively) monotonic in all
  variables to constants via $\geq$ or $>$. Condition (3) is true
  because we only have $\inceff$ effects whose right hand sides are
  (positively) monotonic in all variables.
\end{beweis}




With Proposition~\ref{pro:lnf_stronglymonotonic}, if an LNF task
$(\vars, \propos, \actions, \initial, \goal)$ has acyclic $\asseff$
effects (remember that these are separated out from
Definition~\ref{def:monotonicity} condition (3)) then the task
fulfills the prerequisites of
Theorem~\ref{the:monotonicrelaxreasonable}, so ignoring the decreasing
effects is an adequate relaxation. It is thus feasible to use
solutions to the relaxation as a means of heuristic estimation.





For the $\asseff$ effects, one can easily translate these into, e.g.,
$\inceff$ effects -- $(v^i, \asseff, \exp)$ translates to $(v^i,
\inceff, ((-1) * v^i) + \exp)$. So the reader might wonder why we
bother treating $\asseff$ effects at all. The point is that, while the
translated effects behave equivalently under the real transition
function, they behave differently in the relaxation. In our running
example suppose there is a second action $a'$ with the effect $(v^i,
\asseff, 10)$. In the LNF transformation, the translated version of
this effect is $(v^i, \inceff, -v^i + 10)$.  Say we execute, under
$\result^{\relaxed}$, first $a$ (with effects $(v^i, \inceff, -1)$ and
$(-v^i, \inceff, 1)$) then $a'$. In the original task, the resulting
value of $v^i$ is 10. In the translated task, that value is $11$
(because the decreasing effect on $v^i$ is ignored). So it does make a
difference whether we treat $\asseff$ effects separately or not. An
open question is whether, or in which situations, that difference is
important for planner performance.



We also remark that, while \mff\ implements the introduction of
inverted variables for LNF tasks only, it seems likely that similar
processes will work for richer languages, when all functions are
strictly monotonic and diverging in all variables.














\section{Solving Relaxed Tasks}
\label{rplans}








We now concentrate on the algorithms used in \ff, more generally
algorithms that can be used to obtain heuristic information in a
forward state space search. We explain how to solve relaxed numeric
tasks. We first consider the restricted language, then extend the
methods to LNF tasks. The algorithms form the basis of the \mff\ 
implementation.















\subsection{Restricted Tasks}
\label{rplans:restricted}






The implementation uses a straightforward extension of the
\graphplan-style algorithms introduced in Section~\ref{strips:rplans}.
We still use a two-step process that first builds a relaxed planning
graph then extracts a relaxed plan from that (if the graph succeeds in
reaching the goals). In parallel to the structures that keep track of
the progress in logical propositions, we now have structures that keep
track of the progress in terms of maximally possible variable values.
The graph building mechanism is outlined in
Figure~\ref{code:restricted_RPG_building}.







\begin{figure}[htb]
{\small
\begin{tabbing}
$P_0$ := $s$, {\bf for} all $v^i$ {\bf do} $max_0^i := \varsof^i(s)$ {\bf endfor}\\
$t$ := $0$\\
{\bf while} $\proposof(\goal) \not \subseteq P_t$ or $(v^i, \geq [>], c) \in
\varsof(\goal), max_t^i \not \geq [\not >] c$ {\bf do}\\[0.05cm]
\hspace{0.3cm} \= $A_{t}$ := $\{ a \in \actions \mid$ \= $\proposof(\pre(a))
\subseteq P_t,$\\[0.05cm]
\> \> $\forall (v^i, \geq [>], c) \in \varsof(pre(a)): max_t^i \geq [>] c \}$\\[0.05cm]
\> $P_{t+1}$ := $P_t \cup \bigcup_{a \in A_{t}} \proposof(\eff(a))^+$\\[0.05cm]
\> {\bf for} all $v^i$ {\bf do} $max_{t+1}^i := max_{t}^i + \sum_{a \in A_t, (v^i,
  \inceff, c) \in \varsof(\eff(a))} c$ {\bf endfor}\\
\> {\bf if} \= $P_{t+1} = P_t$ and\\
\> \> $\forall v^i: max_{t+1}^i = max_t^i$ or $max_t^i > \maxneed^i$ {\bf then}\\
\> \> {\bf fail}\\
\> {\bf endif}\\
\> $t$ := $t + 1$\\
{\bf endwhile}\\
$finallayer$ := $t$
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:restricted_RPG_building}Building a relaxed planning
  graph for a state $s$ in a restricted numeric task $(\vars,
  \propos, \actions, \initial, \goal)$.}  \vspace{-0.0cm}
\end{figure}






The parts of the algorithm concerned with the propositions work
exactly as in the \strips\ case, \cf\ Section~\ref{strips:rplans}. As
for the numeric variables, the $max$ value vector at a layer $t$
specifies the current maximum value that the variables can take on.
The vectors are updated in the obvious fashion, adding at each layer
the total sum of the increasing effects at that layer. The termination
condition now checks whether the maximum values of all variables have
either not changed, or are already higher than needed: the
$\maxneed^i$ value for each variable $v^i$ is defined as the highest
requirement on that variable, \ie
\[
\maxneed^i := \max( -\infty, \{ c \mid (v^i, \geq [>], c) \in
\varsof(\goal) \cup \bigcup_{a \in \actions} \varsof(\pre(a)) \}).
\]
Note that the algorithm fails only if there is no relaxed plan for
$(\vars, \propos, \actions, s, \goal)$: if the algorithm fails at a
layer $m$ then the termination condition will hold true at all later
layers. Also, note that there can be only a finite number of layers as
the numeric variables that do increase will eventually reach their
finite $\maxneed$ values. But, as mentioned in
Section~\ref{relaxation:restricted}, the number of layers can be
exponential in the task encoding. Reconsider the example where, for $n
\in \natuerliche$, $v^i$ is initially $0$, $v^i \geq n$ is the goal,
and we have an action effect $(v^i, \inceff, 1)$. The number of graph
layers built for this example, $n$, is exponential in a non-unary
encoding of $n$, whereas one could easily decide solvability with the
$\infty$ trick outlined in Section~\ref{relaxation:restricted}. On the
other hand, it appears unlikely that an implementation of the provably
polynomial decision procedure would be better in practice. The graph
building algorithm is polynomial in the length of its output (the
minimal length of a relaxed plan). Also, the possibly exponential
minimal length of a relaxed plan (exponential in a non-unary encoding
of the variable values) does not seem particularly relevant, at least
not in examples that are not specifically constructed to provoke this
exponentiality. It remains an open question whether an implementation
of $\infty$ handling can achieve better performance in realistic
examples.














We now focus on relaxed plan extraction. This is invoked if the
relaxed planning graph succeeds in reaching the goals. The information
that the graph provides us with are the {\em levels} of all actions,
propositions, and numeric goals. For actions and propositions the
level is the first graph layer at which they appear, \cf\ 
Section~\ref{strips:rplans}. For numeric goals $(v^i, \geq [>], c)$,
the level is the graph layer $t$ where the goal can first be achieved,
\ie where $max^i_t \geq [>] c$ holds the first time. The plan
extraction mechanism is outlined in
Figure~\ref{code:restricted_plan_extraction}.







\begin{figure}[htb]
  {\small
\begin{tabbing}
{\bf for} \= $t$ := $1, \dots, finallayer$ {\bf do}\\
\> $\proposof(\goal_t)$ := $\{ g \in \proposof(\goal) \mid level(g) = t \}$\\[0.05cm]
\> $\varsof(\goal_t)$ := $\{ (v^i, \geq [>], c) \in \varsof(\goal) \mid level(v^i, \geq [>], c) = t \}$\\
{\bf endfor}\\
{\bf for} $t$ := $finallayer, \dots, 1$ {\bf do}\\
\> {\bf for} \= all $g \in \proposof(\goal_t)$ {\bf do}\\
\> \> select $a$, $level(a) = t - 1$, $g \in \proposof(\eff(a))^+$\\[0.05cm]
\> \> {\bf for} \= all $p \in \proposof(\pre(a)), (v^i, \geq [>], c) \in \varsof(\pre(a))$ {\bf do}\\[0.05cm]
\> \> \> $\proposof(\goal_{level(p)}) \cup = \{ p \}$\\[0.05cm]
\> \> \> $\varsof(\goal_{level(v^i, \geq [>], c)}) \cup = \{ (v^i, \geq [>], c) \}$\\
\> \> {\bf endfor}\\
\> {\bf endfor}\\
\> {\bf for} \= all $(v^i, \geq [>], c) \in \varsof(\goal_t)$ {\bf do}\\[0.05cm]
\> \> {\bf while} \= $max_{t-1}^i \not \geq [\not >] c$ {\bf do}\\
\> \> \> select $a$, \= $level(a) = t - 1$, $(v^i, \inceff, c') \in
\varsof(\eff(a))$,\\
\> \> \> \> $a$ not previously selected in this while-loop\\
\> \> \> $c := c - c'$\\
\> \> \> /* introduce $a$'s preconditions as above */\\
\> \> {\bf endwhile}\\
\> \> $\varsof(\goal_{t-1}) \cup = \{ (v^i, \geq [>], c) \}$\\
\> {\bf endfor}\\
{\bf endfor}
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:restricted_plan_extraction}Extracting a relaxed
  plan for a state $s$ in a restricted numeric task $(\vars,
  \propos, \actions, \initial, \goal)$ (levels and $finallayer$
  computed by the algorithm in
  Figure~\ref{code:restricted_RPG_building}).}  \vspace{-0.0cm}
\end{figure}





Again, the logical entities are dealt with exactly as in the \strips\ 
case, \cf\ Section~\ref{strips:rplans}. In addition to the
propositional (sub-)goal set $\proposof(\goal_t)$ at each layer $t$ we
now have a set $\varsof(\goal_t)$ of numeric goals. Like in \strips,
goals and sub-goals are always inserted into the set at their first
appearance in the relaxed planning graph, and the goal sets are
initialized by inserting the respective (top-level) goals. Then there
is a backwards loop from the top to the bottom layer, selecting
actions to support the propositions and numeric variables in the
respective goal sets. The propositions are supported as before, the
only difference being that now also the numeric preconditions of the
supporting actions must be inserted into the goal sets below. When
uniting sets of numeric goals that both contain a constraint on the
same variable $v^i$, the stronger one of both constraints is taken.
For the numeric goals $(v^i, \geq [>], c) \in \varsof(\goal_t)$ it is
in general not enough to select a single action as several actions at
$t-1$ might have contributed to $v^i$'s maximum value at $t$. So
supporters are selected until the goal can be achieved one layer
earlier. Note that $max_{t}^i - \sum_{a \in A_{t-1}, (v^i, \inceff, c)
  \in \varsof(\eff(a))} c = max_{t-1}^i$, so the {\bf while} loop will
always terminate successfully. Note also that one occurrence of an
action can support different logical and numeric goals by different
effects, but can not be used to support the same numeric goal twice.



Upon termination of plan extraction, the selected actions can be used
to form a relaxed plan: with $A_t$ denoting the actions selected at
layer $t$, an arbitrary linearization of $A_0, \dots,
A_{finallayer-1}$ is a relaxed plan for the task. Note that one can
apply various simple heuristics, like selecting $\inceff$ effects with
maximum right hand side first, to make the relaxed plans as short as
possible.
































\subsection{LNF Tasks}
\label{rplans:lnf}










The algorithms for numeric tasks in linear normal form differ from
those for restricted tasks in that we need to take care of $\asseff$
effects, and of the more general expressions in numeric constraints
and in effect right hand sides. As it turns out, integrating these
extensions is not overly difficult. The only issue that becomes
slightly involved is the exact termination criterion for relaxed graph
building. In our solution to the issue we assume, as in the
theoretical analysis underlying
Theorem~\ref{the:monotonicrelaxreasonable}, that the $\asseff$ effects
are acyclic. An outline of the graph building mechanism is shown in
Figure~\ref{code:lnf_RPG_building}.









\begin{figure}[htb]
{\small
\begin{tabbing}
$P_0$ := $s$, {\bf for} all $v^i$ {\bf do} $max_0^i := \varsof^i(s)$ {\bf endfor}\\
$t$ := $0$\\
{\bf while} $\proposof(\goal) \not \subseteq P_t$ or $(\expr, \geq [>], 0) \in
\varsof(\goal), \expr(max_t) \not \geq [\not >] 0$ {\bf do}\\[0.05cm]
\hspace{0.3cm} \= $A_{t}$ := $\{ a \in \actions \mid$ \= $\proposof(\pre(a))
\subseteq P_t,$\\[0.05cm]
\> \> $\forall (\expr, \geq [>], 0) \in \varsof(pre(a)): \expr(max_t) \geq [>] 0 \}$\\[0.05cm]
\> $P_{t+1}$ := $P_t \cup \bigcup_{a \in A_{t}} \proposof(\eff(a))^+$\\[0.05cm]
\> {\bf for} all $v^i$ {\bf do} $max_{t+1}^i := max_{t}^i + \sum_{a \in A_t: (v^i,
  \inceff, \expr) \in \varsof(\eff(a)), \expr(max_t) > 0} \expr(max_t)$ {\bf endfor}\\
\> {\bf for} all $v^i$ {\bf do} $max_{t+1}^i := \max( max_{t+1}^i, \max_{a \in A_t, (v^i, \asseff, \expr) \in
\varsof(\eff(a))} \expr(max_t))$ {\bf endfor}\\
\> {\bf if} \= $P_{t+1} = P_t$ and\\
\> \> $\forall v^i: max_{t+1}^i = max_t^i$ or $max_t^i > \maxneed^i(s)$ {\bf then}\\
\> \> {\bf fail}\\
\> {\bf endif}\\
\> $t$ := $t + 1$\\
{\bf endwhile}\\
$finallayer$ := $t$
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:lnf_RPG_building}Building a relaxed planning
  graph for a state $s$ in an LNF task $(\vars, \propos, \actions,
  \initial, \goal)$.}  \vspace{-0.0cm}
\end{figure}






Compare Figure~\ref{code:lnf_RPG_building} with
Figure~\ref{code:restricted_RPG_building}. We deal with the
expressions in constraints and effect right hand sides simply by
inserting the respective $max$ values of the variables, and computing
the respective outcome (recall that $\expr(v)$ for an expression
$\expr$ and a variable value vector $v$ denotes the value of $\expr$
when inserting the values $v$). The $\inceff$ effects are taken into
account to obtain the $max_{t+1}$ values exactly as before, \ie by
adding their combined contributions to $max_t$ (except that the value
of the right hand sides must now be computed using the $max_t$
values). The $\asseff$ effects are taken into account by determining,
after all $\inceff$ effects have contributed to $max_{t+1}$, whether
there is a $\asseff$ effect in the graph whose value, when inserting
the $max_t$ values, is higher than the hitherto $max_{t+1}$ value. In
this case, $max_{t+1}$ (for the respective variable) is updated to the
maximum assignment possible.




The only part of the algorithm that becomes somewhat complicated, in
comparison to the algorithm for restricted tasks, is the termination
criterion. The difficult part is the computation of the $\maxneed$
values, \ie the values above which the variables can no longer
contribute anything to a relaxed solution.  These values can now
depend on the state $s$ we start from. To derive the values, we start
with the static (non state-dependent) notion of {\em
  solution-relevant} variables. A variable $v^i$ is solution-relevant
if it either occurs in a numeric constraint, or in the right hand side
$\expr$ of an effect $(v^j, \inceff [\asseff], \expr)$ on a
solution-relevant variable $v^j$. Note that solution-relevance thus
transfers transitively over the variables. We denote the set of
solution-relevant variables with $rV$. For the state-dependent aspects
of the relaxed task, we provide notation for the value that a variable
$v^i$ must at least take on in a state $s$ in order to raise (or
``support'') the value of a positively weighted sum $\expr = \sum_{j
  \in X} c^j * v^j + c$ above a constant $c'$.
\[
\supportval^i( s, \expr, c' ) := (c' - c - \sum_{i \neq j \in X} c^j *
v^j(s)) \; / \; c^i
\]
Of course, the support value $\supportval^i( s, \expr, c' )$ is only
defined if $v^i \in \varsof(\expr)$, \ie if $v^i$ is a part of the
weighted sum. As the reader can easily convince him/herself, if we
raise the value of $v^i$ in $s$ above $\supportval^i( s, \expr, c' )$
then we know that the value of $\expr$ is at least $c'$. We use this
concept to determine the point above which a variable $v^i$
contributes sufficiently to all constraints and effect right hand
sides that it can contribute to. For constraints $(\expr, \geq [>],
0)$ with $v^i \in \varsof(\expr)$ this point is reached with $v^i \geq
\supportval^i( s, \expr, 0 )$ (then the constraint is fulfilled). For
$\inceff$ effect right hand sides in $(v^j, \inceff, \expr)$ with $v^i
\in \varsof(\expr)$ and $v^j \in rV$ ($v^j$ may be needed) this point
is reached with $v^i \geq \supportval^i( s, \expr, 0 )$ (the effect
can then eventually increase $v^j$ to arbitrarily high values). As for
$\asseff$ effect right hand sides, in an effect $(v^j, \asseff,
\expr)$ with $v^i \in \varsof(\expr)$ and $v^j \in rV$ the value of
$v^i$ is sufficient if $v^i \geq \supportval^i( s, \expr,
\maxneed^j(s) )$: then the effect is high enough to assign $v^j$ a
sufficient value. The main complication here is that we want to use
the $\supportval$ values to define the $\maxneed$ values so our
definition for $\asseff$ effects is recursive. That does not
constitute a problem given our assumption that the $\asseff$ effects
are acyclic. In effect, the recursion is guaranteed to terminate.
Altogether, the definition is the following.  {\small
\[
\maxneed^i(s) := \max \left\{ \begin{array}[]{l}
    -\infty,\\[0.1cm]
    \{ \supportval^i( s, \expr, 0 ) \mid (\expr, \geq [>], 0) \in
    \varsof(\goal) \cup \bigcup_{a \in \actions} \varsof(\pre(a)),
    v^i \in \varsof(\expr) \},\\[0.13cm]
    \{ \supportval^i( s, \expr, 0 ) \mid (v^j, \inceff, \expr) \in
    \bigcup_{a \in \actions} \varsof(\eff(a)), v^i \in \varsof(\expr),
    v^j \in rV \},\\[0.13cm]
    \{ \supportval^i( s, \expr, \maxneed^j(s) \mid (v^j, \asseff,
    \expr) \in \bigcup_{a \in \actions} \varsof(\eff(a)), v^i \in
    \varsof(\expr), v^j \in rV \}
     \end{array} 
  \right.\\
\]
} 
Note that, with this definition, the variables with $\maxneed^i(s) =
-\infty$ are the variables that are not solution-relevant.



\begin{theorem}\label{the:lnf_rpg_suff}
  Assume a linear numeric task $(\vars, \propos, \actions, \initial,
  \goal)$ that is in LNF and has acyclic $\asseff$ effects. Assume a
  state $s$. If the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} fails, then there is no relaxed
  plan for $(\vars, \propos, \actions, s, \goal)$.
\end{theorem}



The main proof idea is, as before, this: if the algorithm fails at a
layer $m$ then the termination condition will hold true at all later
layers. The argument concerning the $\maxneed(s)$ values follows what
is outlined above. The full details are a bit lengthy. See
Appendix~\ref{proofs}.




As discussed before for the restricted language, the number of graph
layers built before termination is finite -- eventually, all variables
either do not increase or reach their finite $\maxneed$ values -- but
can be exponential in the encoding length of the task. Again, one
could implement a provably polynomial algorithm along the lines of the
method used in the proof to
Theorem~\ref{the:monotonicrelaxreasonable}, and again it is debatable
whether such an implementation would, for realistic examples, achieve
any significant performance improvements over the existing
implementation.





It is interesting to consider the role that the inverted variables --
as introduced by \mff\ during LNF pre-processing, see
Section~\ref{relaxation:linear} -- play in the relaxed planning graph
process described above. Estimating the maximum value of an inverted
variable is the same as estimating the minimum value of the respective
original variable. More precisely, in
Figure~\ref{code:lnf_RPG_building}, if $v^j$ is the inverted variable
to $v^i$ then $(-1) * max_t^j$ is, for all $t$, an optimistic
approximation of the minimum value that $v^i$ can take on after $t$
steps: the value that results when one ignores all {\em in}creasing
effects on $v^i$, and is optimistic about the {\em de}creasing
effects. In this sense, the introduction of the inverted variable
$-v^i = v^j$ can be viewed as a way of informing the relaxed planner
of where, in the numeric constraints and effects, to use the minimum
or the maximum possible value of $v^i$, when computing an optimistic
approximation of these maximum and minimum values.\footnote{This
  insight has been pointed out to the author by David Smith in a
  comment on the submitted version of this article. Optimistically
  estimating maximum and minimum variable values, or more generally
  multiple variable values, is an alternative viewpoint to the
  monotonicity paradigm we explore here. Investigating the alternative
  viewpoint in more depth is an open topic.}





We now focus on relaxed plan extraction. As justified by
Theorem~\ref{the:lnf_rpg_suff}, this is invoked only if the relaxed
planning graph succeeds in reaching the goals. Also as before, the
information that the graph provides are the levels of all actions,
propositions, and numeric goals. For actions and propositions the
definitions stay the same, for numeric goals $(\expr, \geq [>], 0)$
the level is the graph layer $t$ where the goal can first be achieved,
\ie where $\expr(max_t) \geq [>] 0$ holds the first time. An outline
of the plan extraction mechanism is shown in
Figure~\ref{code:lnf_plan_extraction}.



\begin{figure}[htb]
  {\small
\begin{tabbing}
{\bf for} \= $t$ := $1, \dots, finallayer$ {\bf do}\\
\> $\proposof(\goal_t)$ := $\{ g \in \proposof(\goal) \mid level(g) = t \}$\\[0.05cm]
\> $\varsof(\goal_t)$ := $\{ (v^i, \geq [>], max^i_t) \mid (\expr,
\geq [>] 0) \in \varsof(\goal), level(\expr, \geq [>], 0) = t, v^i \in
\varsof(\expr) \}$\\
{\bf endfor}\\
{\bf for} $t$ := $finallayer, \dots, 1$ {\bf do}\\
\> {\bf for} \= all $g \in \proposof(\goal_t)$ {\bf do}\\
\> \> select $a$, $level(a) = t - 1$, $g \in \proposof(\eff(a))^+$\\[0.05cm]
\> \> {\bf for} \= all $p \in \proposof(\pre(a)), (\expr, \geq [>], 0) \in \varsof(\pre(a))$ {\bf do}\\[0.05cm]
\> \> \> $\proposof(\goal_{level(p)}) \cup = \{ p \}$\\[0.05cm]
\> \> \> $\varsof(\goal_{level(\expr, \geq [>], 0)}) \cup = \{ (v^i,
\geq [>], max^i_{level(\expr, \geq [>], 0)}) \mid v^i \in \varsof(\expr) \}$\\
\> \> {\bf endfor}\\
\> {\bf endfor}\\
\> {\bf for} \= all $(v^i, \geq [>], c) \in \varsof(\goal_t)$ {\bf
  do}\\[0.05cm]
\> \> {\bf if} \= $\exists a$, $level(a) = t - 1$, $(v^i, \asseff, \expr) \in
\varsof(\eff(a))$, $\expr(max_{t-1}) \geq [>] c$ {\bf then}\\
\> \> \> $\varsof(\goal_{t-1}) \cup = \{ (v^j, \geq, max^j_{t-1}) \mid
v^j \in \varsof(\expr) \}$\\
\> \> \> /* introduce $a$'s preconditions as above */\\
\> \> {\bf else}\\
\> \> \> {\bf while} \= $max_{t-1}^i \not \geq [\not >] c$ {\bf do}\\
\> \> \> \> select $a$, \= $level(a) = t - 1$, $(v^i, \inceff, \expr) \in
\varsof(\eff(a))$, $\expr(max_{t-1}) > 0$\\
\> \> \> \> \> $a$ not previously selected in this while-loop\\
\> \> \> \> $c := c - \expr(max_{t-1})$\\
\> \> \> \> /* introduce max constraints for all vars in $\expr$ as
above */\\
\> \> \> \> /* introduce $a$'s preconditions as above */\\
\> \> \> {\bf endwhile}\\
\> \> \> $\varsof(\goal_{t-1}) \cup = \{ (v^i, \geq [>], c) \}$\\
\> \> {\bf endif}\\
\> {\bf endfor}\\
{\bf endfor}
\end{tabbing}}
\vspace{-0.4cm}
\caption{\label{code:lnf_plan_extraction}Extracting a relaxed
  plan for a state $s$ in an LNF task $(\vars, \propos, \actions,
  \initial, \goal)$ (levels and $finallayer$ computed by the algorithm
  in Figure~\ref{code:RPG_building}).}  \vspace{-0.0cm}
\end{figure}




Compared to the algorithm for restricted tasks, shown in
Figure~\ref{code:restricted_plan_extraction}, the novelties in
Figure~\ref{code:lnf_plan_extraction} are that complex numeric goals
get split up into goals for the individual variables, that effect
right hand sides are forced to have a sufficiently high value, and
that $\asseff$ effects are handled. The first issue, given a numeric
goal $(\expr, \geq [>], 0)$, is dealt with simply by constraining all
variables $v^i \in \varsof(\expr)$ to take on their respective $max$
value. Similarly, effect right hand sides in $(v^i, \asseff [\inceff],
\expr)$ are forced to be sufficiently high by requiring all $v^j \in
\varsof(\expr)$ to take on the respective $max$ value. The $\asseff$
effects are taken into account as an alternative way of achieving a
numeric goal $(v^i, \geq [>], c) \in \varsof(\goal_t)$. If there is an
effect $(v^i, \asseff, \expr)$ with sufficiently high value,
$\expr(max_{t-1}) \geq [>] c$, then the respective action is selected.
Otherwise a set of actions with $\inceff$ effects is selected in a
similar fashion as for restricted tasks. As in
Figure~\ref{code:restricted_plan_extraction}, when uniting sets of
numeric goals that both contain a constraint on the same variable
$v^i$, the stronger one of both constraints is taken. It is easy to
see that, upon termination, the selected actions can be used to form a
relaxed plan for the state at hand.



\begin{theorem}\label{the:lnf_rplan_suff}
  Assume a linear numeric task $(\vars, \propos, \actions, \initial,
  \goal)$ that is in LNF and has acyclic $\asseff$ effects. Assume a
  state $s$ for which the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} reaches the goals. The actions
  selected by the algorithm depicted in
  Figure~\ref{code:lnf_plan_extraction} form a relaxed plan for
  $(\vars, \propos, \actions, s, \goal)$.
\end{theorem}


The (straightforward) proof can be found in Appendix~\ref{proofs}.  We
conclude this section with two additional remarks. One thing that
might also have occurred to the reader is that one does not
necessarily need to support a goal $(\expr, \geq [>], 0)$ by requiring
all $v^i \in \varsof(\expr)$ to take on the maximum possible value.
Weaker requirements might already be sufficient. The same holds true
for effect right hand sides. One might be able to find shorter relaxed
plans by using some simple heuristics at these points. It also seems
plausible that the algorithms specified here will work for {\em any}
strictly monotonic task that uses only $\inceff$ effects and acyclic
$\asseff$ effects, assuming the $\maxneed$ value computation is
modified appropriately. Exploring this idea for richer language
classes is left open as a topic for future work. It is also left open
if and how $\muleff$ effects and $\diveff$ effects could be taken into
account.










\section{Metric-FF}
\label{metric-ff}








This section details how the theoretical and algorithmic work
described so far is used to implement the heuristic planning system
\mff. Section~\ref{metric-ff:basic} specifies how the relaxed plan
information is used to define the basic architecture of a planner that
handles \strips\ plus linear tasks with acyclic $\asseff$ effects.  We
then describe extensions that are integrated into the system:
Section~\ref{metric-ff:adl} explains how the extension to \adl\ is
handled, Section~\ref{metric-ff:cost} explains how flexible
optimization criteria can be taken into account.















\subsection{Basic Architecture}
\label{metric-ff:basic}







As in the \strips\ case, once we have the techniques for extracting
relaxed plans, a state space planner is easily implemented. The given
linear task is transformed into an LNF task using the algorithms
described in Section~\ref{relaxation:linear}. We define a heuristic
function, a search strategy, and a pruning technique analogous to that
used in the \strips\ version of \ff, \cf\ Section~\ref{strips:ff}. All
methods are straightforward adaptions of the \strips\ techniques. The
heuristic function still estimates goal distance as the number of
actions in the relaxed plan.





\begin{def1}\label{def:mff-heuristic}
  Assume a linear numeric task $(\vars, \propos, \actions, \initial,
  \goal)$ that is in LNF and has acyclic $\asseff$ effects, and a
  state $s$. The {\em \mff\ heuristic value} $h(s)$ for $s$ is defined
  as follows. If the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} fails, $h(s) := \infty$.
  Otherwise, $h(s) := \sum_{t=1}^{finallayer} |A_t|$ where $A_t$ is
  the set of actions selected at layer $t$ by the algorithm depicted
  in Figure~\ref{code:lnf_plan_extraction}.
\end{def1}




The search strategy remains exactly the same, namely \ehc\ as depicted
in Figure~\ref{code:ehc}. The only difference lies in the the way we
avoid repeated states. In the \strips\ case, this is a simple hash
table lookup procedure. The straightforward adaption would be to store
all visited states $s$, and cut out a new state $s'$ if an identical
state $s$ has been visited before. We can, however, derive a weaker
cutoff criterion that has an important performance impact in certain
situations. It might be that $s'$ differs from $s$ only in that some
solution-irrelevant numeric variables have other values. For example,
the only difference between $s$ and $s'$ might be that in $s'$ more
execution time has been spent. If we expand $s'$ then iteratively we
might end up with an infinite sequence of succeeding states that do
nothing but increase execution time (this phenomenon can be observed
in various benchmark domains). We can avoid such phenomena by cutting
out new states $s'$ that are {\em dominated} by a stored state $s$.
Given a task $(\vars, \propos, \actions, \initial, \goal)$, a state
$s'$ is dominated by a state $s$ if the propositions in $s$ and $s'$
are the same, and for all $v^i \in \vars$, either $v^i$ is not
solution-relevant, $v^i \in \vars \setminus rV$, or $v^i(s') \leq
v^i(s)$ holds.\footnote{Recall the definition of the solution-relevant
  variables $rV$, given in Section~\ref{rplans:lnf}: all variables
  that occur in a numeric constraint, or in the right hand side
  $\expr$ of an effect $(v^j, \ass, \expr)$ on a solution-relevant
  variable $v^j$.} If $s'$ is dominated by $s$, and the task at hand
is monotonic in the sense of Definition~\ref{def:monotonicity}, then
all action sequences that achieve the goal starting from $s'$ do the
same starting from $s$.



\begin{proposition}\label{pro:irrelevance-cutoff}
  Assume a numeric task $(\vars, \propos, \actions, \initial, \goal)$
  that is monotonic. Assume two states $s$ and $s'$. If $s'$ is
  dominated by $s$ then, for all action sequences $P \in \actions^*$,
  if $\result( s', P ) \models \goal$ then $\result( s, P ) \models
  \goal$. 
\end{proposition}

\begin{beweis}
  Say $P = \langle a_1, \dots, a_n \rangle$ is an action sequence such
  that $\result( s', P ) \models \goal$ holds. We show that, for all
  solution-relevant variables $v^i \in rV$ and for all $0 \leq j \leq
  n$, $v^i(\result(s', \langle a_1,$ $\dots,$ $a_j \rangle)) \leq
  v^i(\result(s, \langle a_1, \dots, a_j \rangle))$ holds. This proves
  the proposition: the variables in the goal constraints are all in
  $rV$, the goal constraints are monotonic
  (Definition~\ref{def:monotonicity} condition (1)), and the goal
  constraints are fulfilled in $\result( s', P )$. So with the claim
  above they are also fulfilled in $\result( s, P )$. We prove the
  claim on the solution-relevant variable values by induction over
  $j$. Base case $j = 0$: by prerequisite, $v^i(s') \leq v^i(s)$ holds
  for all $v^i \in rV$. Inductive case $j \rightarrow j + 1$. First,
  the preconditions of $a_{j+1}$ are fulfilled in $\result(s, \langle
  a_1, \dots, a_j \rangle)$ due to the same argument as used for the
  goal constraints above. Second, all variables that are contained in
  effect right hand sides on solution-relevant variables are
  themselves solution-relevant by definition so the induction
  hypothesis holds for them. This proves the claim with monotonicity
  of numeric effects (Definition~\ref{def:monotonicity} condition
  (2)).
\end{beweis}



LNF tasks are monotonic. So with
Proposition~\ref{pro:irrelevance-cutoff}, if there is a solution plan
from $s'$, then there is a solution plan from $s$. Thus cutting $s'$
out of a search space that already contains $s$ is solution
preserving.  Consequently, during each search iteration performed by
\ehc, our implementation keeps a hash table of states visited in that
iteration, and skips a new state if it is dominated by at least one of
the visited states.\footnote{More precisely, a new state $s'$ is
  skipped only if there is a dominant visited state $s$ {\em in the
    same hash entry}. If the value of all solution-relevant variables
  is the same in $s'$ and $s$ (like when only execution time has
  increased), then our implementation ensures that this is the case.
  Otherwise it is a matter of chance. It is an open question how the
  visited states could be indexed in order to provide a fast exact
  answer to the query whether they contain a dominant state or not.}
As indicated above, in various benchmark examples this prevents the
planner from looping when the new states do nothing but increase the
value of some solution-irrelevant variable like execution
time.\footnote{What we have here is a consequence of the
  undecidability of numeric planning \cite{helmert:aips-02}, which can
  be observed even in seemingly benign benchmarks. In a finite state
  space we of course would not run the risk of entering an infinite
  loop.}


To extend our \strips\ pruning technique, helpful actions now are all
those actions that can support either a propositional or a numeric
goal at the lowest layer of the relaxed planning graph.



\begin{def1}\label{def:mff-helpful}
  Assume a linear numeric task $(\vars, \propos, \actions, \initial,
  \goal)$ that is in LNF and has acyclic $\asseff$ effects, and a
  state $s$ for which the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} reaches the goals. The set of
  {\em helpful actions} $H(s)$ for $s$ is defined as
\begin{tabbing}
$H(s) := \{ \; a \in \actions \mid$ \= $\proposof(\eff(a))^+ \cap
\proposof(\goal_1) \neq \emptyset \; \vee$\\
\> $\exists (v^i, \geq [>] c) \in \varsof(\goal_1): \exists (v^i, 
\asseff, \expr) \in \varsof(\eff(a)): \expr(\varsof(s)) \geq [>] c \; \vee$\\
\> $\exists (v^i, \geq [>] c) \in \varsof(\goal_1): \exists (v^i, \inceff, \expr) \in
\varsof(\eff(a)): \expr(\varsof(s)) > 0 \; \},$
\end{tabbing}
where $\goal_1$ is the set of sub-goals constructed at layer $1$ by
  the algorithm depicted in Figure~\ref{code:lnf_plan_extraction}.
\end{def1}



Supporting a numeric goal here means: for $\asseff$ effects, that the
right hand side of the effect is sufficient to fulfill the goal; for
$\inceff$ effects, that the respective right hand side expression is
greater than $0$. Note that the right hand side value of an effect at
the lowest layer of the relaxed planning graph is exactly its value in
the state $s$ at hand. During a search iteration in \ehc, when
expanding a state $s$, only the states generated by the actions in
$H(s)$ are included into the search space. Note that states $s$ where
the relaxed planning graph does not reach the goals have $h(s) =
\infty$ so do not get expanded anyway.





As in \strips, the algorithm can fail if either \ehc\ gets trapped in
a dead end state or helpful actions pruning cuts out important states.
We have observed that helpful actions pruning is too severe in some
numeric domains. So, in case \ehc\ fails we try again with the pruning
technique turned off, \ie we continue the hill-climbing procedure from
the point of failure without pruning. If this fails too, then like in
\strips\ we employ a safety net solution: a complete greedy best-first
strategy trying to solve the task from scratch. This strategy expands
all search nodes by increasing order of goal distance estimation. New
states are cut out if they are dominated by an already visited state.

























\subsection{ADL}
\label{metric-ff:adl}







\adl\ \cite{pednault:kr-89} goes beyond \strips\ in that it allows, in
action preconditions and the goal, arbitrary equation-free first-order
logical formulae, and actions with conditional effects -- effects that
only occur when their effect condition holds true. The effect
condition can be an arbitrary (equation-free) first-order logical
formula. In the numeric setting, the effects can contain updates on
numeric variables. The numeric constraints can now appear at any point
in a logical formula where a logical atom is allowed.




Like the previous \ff\ version \cite{hoffmann:nebel:jair-01}, \mff\ 
compiles quantifiers and disjunctions away in a pre-processing phase.
\mff\ does not compile conditional effects away. So \mff's internal
language differs from \strips\ (with numeric constraints and effects)
only in that actions can have conditional effects, where the effect
conditions are conjunctions of propositions (and numeric constraints).
The reason why \adl\ is compiled into this language is that the
heuristic algorithms (i.e., the relaxed planning graph) can be
implemented very efficiently for this more restricted language format.
The compilation can be exponentially costly in general but is feasible
when, as one might expect in the formulation of a realistic planning
scenario, the logical formulae are not overly complex. The reason why
conditional effects are not also compiled away (which could be done in
principle) is that, as Nebel \shortcite{nebel:jair-00} proved, this
would imply another exponential blow up given we want to preserve
solution length.  Fortunately the conditional effects can easily be
dealt with so there is no need to compile them away. In the following,
we give a brief overview of the compilation process, and of the
extended heuristic function implementation. Except for the heuristic
function, the only thing that must be adapted is the state transition
function, which is conceptually trivial.




The compilation process is largely an implementation of ideas that
have been proposed by Gazen and Knoblock
\shortcite{gazen:knoblock:ecp-97}, as well as Koehler and Hoffmann
\shortcite{koehler:hoffmann:ecai-ws-00}. The extensions to handle
numeric constructs are all straightforward. The process starts with
the usual planner inputs, \ie with a set of parameterized operator
schemata, an initial state, and a goal formula. The compilation works
as follows.


\begin{enumerate}
\item Determine predicates and numeric functions that are static in
  the sense that no operator has an effect on them. Such predicates
  and functions are a common phenomenon in benchmark tasks. Examples,
  in a transportation context, would be the connections between
  locations as given by a static $(\mbox{connected} \; ?l1 \; ?l2)$
  predicate, or the distances between locations as given by a static
  $(\mbox{distance} \; ?l1 \; ?l2)$ function. Static predicates and
  functions are recognized 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
  consist of conjunctions, disjunctions, and atoms containing
  variables (where the atoms can be numeric constraints).
\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 not contained in the initial
  state, then $(p \; \vec{a})$ can be replaced with \false. As another
  example, if both sides of a numeric constraint are static then the
  constraint can be replaced with either \true\ or \false.
\item Transform formulae into DNF. This is postponed until after
  instantiation, because it can be costly, so it should be applied to
  the smallest formulae possible. In a fully instantiated formula, it
  is likely that many static predicate occurrences (constant
  constraint 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}




When all the logical constructs have been normalized, the numeric
constructs in the task are transformed into LNF in a manner analogous
to the process described in Section~\ref{relaxation:linear}.
Integrating conditional effects into the relaxed planning process is
an easy matter. The relaxed planning graph differs from its \strips\ 
counterpart only in that it now keeps track of the graph layers at
which an action's effects first become applicable. The relaxed plan
extraction process differs from its \strips\ counterpart only in that
it now selects supporting {\em effects} for the propositional and
numeric goals.

























\subsection{Optimization Criteria}
\label{metric-ff:cost}






In \pddl2.1, the user can specify an optimization criterion for a
task. The criterion consists of an arbitrary numeric expression
together with a keyword ``maximize'' or ``minimize'' saying whether
higher or lower values of the expression are preferred. The semantics
are that a solution plan is optimal iff the state it leads to is a
maximal / minimal goal state with respect to the optimization
expression. \mff\ supports, run in ``optimization mode'', a somewhat
more restrictive form of optimization. It accepts the optimization
criterion only if the criterion can be transformed, according to a
certain schema, into additive action cost minimization. The heuristic
cost of a state is then the summed up cost of the actions in the
respective relaxed plan, and search is a standard weighted $A^*$ where
the weights can be set via the command line. Note that this
methodology can not give a guarantee on the quality of the returned
solution as the heuristic function is not provably admissible. The
methodology is an obvious option given that the cost of a relaxed plan
(in an additive setting) gives us a remaining cost estimation
technique for free. It is an open question how more general
optimization criteria can be dealt with. In the following, we describe
our implemented methodology in a little more detail. We start with the
\strips\ setting, then outline the changes made in the extension to
\adl.





\mff\ rejects the optimization expression if it is not linear.
Otherwise, if the optimization keyword is ``maximize'' then the
expression is multiplied by $-1$ so minimization is required. The
expression is then brought into LNF, $\sum_{j \in X} c^j * v^j$ (the
constant part can obviously be skipped). With this notation, the
optimization criterion is accepted (only) if all action effects on
variables $v^j \in X$ increase the optimization expression value by a
constant, \ie if all effects on $v^j \in X$ are of the form $(v^j,
\inceff, c)$ where $c \in \rationale$, $c \geq 0$. For each action
$a$, the cost of the action is then defined as
\[
cost(a) := \sum_{(v^j,
  \inceff, c) \in \varsof(\eff(a)), v^j \in X} c^j * c,
\]
\ie as the sum of all increases in cost variables for the action,
multiplied by their weight in the optimization expression. The cost of
an action sequence or set is the sum of the individual costs. It is
easy to see that, in this setting, finding a goal state that minimizes
the optimization expression value is equivalent to finding a plan with
minimal cost. The search algorithm we then use is, as stated above, a
standard weighted $A^*$ algorithm implementing a best-first search on
the function $f(s) = w_g * g(s) + w_h * h(s)$ where $g(s)$ is the cost
of the search path that leads to $s$, $h(s)$ is the remaining cost
estimate (\ie the cost of the relaxed plan from $s$), and the weights
$w_g$ and $w_h$ can be given in the command line. Since the remaining
cost estimate is in general not admissible, the first plan found is
not guaranteed to be optimal. But one would expect that empirically
better plans can be found. We will see below that this is, in fact,
the case in some of the \ipcthree\ testing domains.





In \adl, the cost of an action in a state is the sum of the costs of
all effects that appear, the cost of an action sequence is the sum of
the costs of the actions in the respective states, and minimizing the
optimization expression is as before equivalent to minimizing plan
cost. Estimating the remaining cost by means of a relaxed plan becomes
somewhat less obvious, since a choice has to be made on which effect
costs are counted for the result. There are effects that have been
selected to support logical or numeric goals during relaxed plan
extraction, and there are effects that will get triggered when
actually executing the relaxed plan. We have chosen to only count the
costs of the former effects. The heuristic search algorithm remains
exactly the same as in the \strips\ case.





















\section{Competition Results}
\label{results}









We briefly examine the \ipcthree\ competition data relevant to \mff.
The competition featured domains spanning the whole range from
\strips\ to \pddl2.1 level 3, which permits a combination of logical,
numeric, and temporal constructs. \ff\ participated in the \strips\ 
domains and in the numeric domains, demonstrating very competitive
performance. We only discuss the data for the numeric domains. A
discussion of the \strips\ results can be found in the competition
overview article by Long and Fox \shortcite{long:fox:jair-03}.



There were six numeric domains used in the competition. For each of
these domains, we include a figure showing runtime curves, and discuss
relative (runtime and solution quality) performance in the text. Like
\ff, the \mips\ and \lpg\ systems could be configured to either favor
speed or quality, \ie to either find some plan as fast as possible or
to search for a good plan in the sense of the optimization criterion.
To make the graphs readable, we only show the runtime curves of those
planners that favor speed. We discuss the solution quality behavior of
these planners in terms of plan length, \ie number of steps. Note that
these planners do not take account of the optimization criterion
anyway. For the planners that favor quality, we discuss their runtime
and solution quality behavior in the text. Given that the optimization
mode in \mff\ is only a preliminary implementation, we keep the
discussions short. We also give only brief descriptions of the domain
semantics. More details on these can be found in the overview article
\cite{long:fox:jair-03}. We focus on the six domains in turn, then
give a short summary of \mff's performance.















\subsection{Depots}
\label{results:depots}






The {\sl Depots} domain is a combination of the well-known {\sl
  Logistics} and {\sl Blocksworld} domains. Objects must be
transported with trucks as in {\sl Logistics}, and must then be
arranged in stacks as in {\sl Blocksworld}. The numeric constructs
define fuel consumption for trucks and the hoists that lift the
objects (in order to stack them somewhere). Objects have weights and
the sum of the weights of the objects loaded onto a truck at any time
must be lower than or equal to that truck's capacity.
Figure~\ref{eps/dep.eps} shows the runtime data on the 22 {\sl Depots}
instances used in the competition.




%figure
\scalefig{1.0}{eps/dep.eps}{Runtime curves on {\sl Depots} instances
  for the planners favoring speed. Time is shown on a logarithmic
  scale, instance size scales from left to right.}


  
The four planners participating in the numeric version of {\sl Depots}
were \mff, \lpg, \mips, and \semsyn. At the time of writing, no paper
on the numeric version of any of these planners is published. for
\lpg\ and \mips, the reader is referred to the respective articles to
appear in this same JAIR special issue
\cite{gerevini:et:al:jair-03,edelkamp:jair-03}. As
Figure~\ref{eps/dep.eps} shows, \semsyn\ can only solve the single
smallest instance, and \mips\ solves 10 instances scattered across the
whole set. \mff\ and \lpg\ solve most of the instances and exhibit
similar behavior. \mff\ is the only planner that can solve the two
largest instances. As stated above, we only show the curves for those
configurations favoring speed. In the competition data, this version
of \mff\ is called ``\mffs'', this version of \lpg\ is called
``\lpgs'', and this version of \mips\ is called ``\mipss''.



To assess relative plan quality behavior (\ie plan length or
minimization expression value), we computed quotients as follows.
Given planners A and B, measure, for all instances solved by both
planners, A's plan quality divided by B's plan quality. Compute the
average quotient. At points where we need an absolute measure of
comparison between the participating planners in a domain, we set the
planner B to a hypothetical ``Best-of'' planner whose data is obtained
by selecting the best (\ie lowest) results of all planners. The
individual planners in the domain are then all ranked by comparing
them to Best-of.



The data obtained concerning plan length in {\sl Depots}, for the
planners shown in Figure~\ref{eps/dep.eps}, is this. \mffs's plans are
on average $1.23$ times as long as Best-of's plans, \lpgs's plans are
on average $1.25$ times as long as Best-of's plans, and \mipss's plans
are on average $1.29$ times as long as Best-of's plans. Thus plan
lengths are roughly similar here. For the single instance that
\semsyn\ solves, its plan has $5$ steps while \mffs's has $10$ steps,
and those of \lpgs\ and \mipss\ have $11$ steps.




We next comment on the algorithms used in the planner versions
favoring quality. In \mips, similar to \mff, in optimization mode the
heuristic function becomes a kind of relaxed plan cost in an $A^*$
algorithm. In contrast, the \lpg\ optimization method starts from the
first plan, and then continues search for plans that are better. \mff\ 
performs best-first search on the function $f(s) = w_g * g(s) + w_h *
h(s)$. In the competition, the weights were set to $w_g = 1$ and $w_h
= 5$. The quality version of \mips\ is simply called ``MIPS'' in the
competition data. To improve readability we call it ``\mipsq'' here,
similar to the quality-favoring versions of \mff\ and \lpg, called
``\mffq'' and ``\lpgq''.




The optimization criterion in {\sl Depots} is to minimize overall fuel
consumption. For runtime, the quality versions of \mips\ and \lpg\ 
behave only slightly worse than the speed versions. In contrast,
\mff's quality version solves only the smallest 3 instances. For
solution quality, the fuel consumption of \mffs\ on the first 3
instances is $22$, $33$, and $35$, while that of \mffq\ is $22$, $33$,
and $36$. Thus no optimization effect is observable. On the same
instances, \mipsq\ finds more costly plans ($32$, $63$, and $44$), and
\lpgq's plans are slightly better ($22$, $33$, and $29$). Across all
instances, \lpgq's plans consume, on average, $1.01$ times the fuel
that Best-of's plans consume, while that average value is $1.46$ for
\mipsq.

















\subsection{Driverlog}
\label{results:driverlog}







The {\sl Driverlog} domain is a variation of {\sl Logistics} where the
trucks need drivers, and the underlying map is an arbitrary undirected
graph (as opposed to the fully connected graphs in the standard
version of the domain). Drivers can move on different paths than
trucks. The numeric constructs specify the total time driven and
walked. Figure~\ref{eps/dri.eps} shows the runtime data for the 20
{\sl Driverlog} instances used in the competition.


%figure
\scalefig{1.0}{eps/dri.eps}{Runtime curves on {\sl Driverlog}
  instances for the planners favoring speed. Time is shown on a
  logarithmic scale, instance size scales from left to right.}




As in {\sl Depots}, the participating planners were \mff, \lpg, \mips,
and \semsyn. Again, \semsyn\ solved only the smallest instance.
\lpgs\ is the only planner that solves all instances. \mffs\ solves
one more task than \mipss\ (the respective data point is almost hidden
behind ``SemSyn'' in the top right corner), and is roughly as fast as
\lpgs\ on the tasks that it solves. As for plan length, again none of
the planners is clearly superior. The average quotients versus Best-of
are: $1.34$ for \mffs, $1.44$ for \lpgs, and $1.21$ for \mipss.
\mffs's and \lpgs's plan lengths are thus on average somewhat longer
than those of \mipss. The difference has no tendency to grow with
instance size, though. On the single instance solved by \semsyn,
\semsyn's plan has $3$ steps while those of the other planners have
$8$.


The optimization criterion in {\sl Driverlog} is to minimize some
(instance-specific) linear combination of total time, driven distance,
and walked distance. \mffq's runtime behavior is, as in {\sl Depots},
a lot worse than that of \mffs, solving only 5 of the smaller
instances. The quality of the plans is slightly better, though, $0.94$
times \mffs's values on average. \mipsq\ and \lpgq\ solve the same
instances as their speed-favoring counterparts. The average comparison
of \lpgq\ to Best-of is $1.00$ (precisely $1.000411$), that of \mipsq\ 
is $1.31$ -- on a single instance, \mipsq's plan consumes less fuel
($730$ units) than \lpgq's plan ($736$ units).



The competition also featured a version of {\sl Driverlog}
(``Hard-Numeric'') where driving a truck consumes fuel proportional to
the square of its load, and the criterion is to minimize an
instance-specific linear combination of total time and fuel
consumption. Interestingly, with this optimization criterion \mffq\ is
only slightly less efficient than \mffs, solving the same instances as
the speed-favoring version. We will come back to this phenomenon in
the outlook, when we discuss the effect of optimization expressions on
runtime performance. The overall runtime performance of all other
planners is similar to that in the domain version described above.
For the optimization expression, \mffq's values are on average $0.77$
times those of \mffs\ (so an optimization effect can be observed). The
comparison to Best-of is $1.59$ for \mffq, $1.007$ for \lpgq, and
$1.72$ for \mipsq.


















\subsection{Zenotravel}
\label{results:zenotravel}





The {\sl Zenotravel} domain, as used in the competition, is a rather
classical transportation domain, where objects must be transported via
airplanes. The planes use fuel, and can fly either slow or fast. Fast
movement consumes more fuel. In the numeric version of the domain, the
fuel level of a plane and the overall fuel usage are numeric
variables. In addition, a numeric variable counts the passengers on
board a plane, and fast movement is only allowed if the number of
passengers is below a certain threshold. A refuel operator can be used
to set the fuel level of a plane back to its maximum capacity. Without
durations, the only difference between the effects of slow and fast
flying lie in the higher fuel consumption, thus ``fast'' flying is a
useless action. Figure~\ref{eps/zen.eps} shows the runtime data on the
20 {\sl Zenotravel} instances used in the competition.



%figure
\scalefig{1.0}{eps/zen.eps}{Runtime curves on {\sl Zenotravel}
  instances for the planners favoring speed. Time is shown on a
  logarithmic scale, instance size scales from left to right.}



Again, the participating planners were \mff, \lpg, \mips, and \semsyn.
\semsyn\ solves only the smallest three instances, the other planners
solve the whole test set. \mffs\ is an order of magnitude faster than
\lpgs\ and \mipss. For plan length, \mffs\ and \mipss\ behave
similarly, while \lpgs\ finds somewhat longer plans. The quotient
values versus Best-of are $1.28$ for \mffs, $1.45$ for \lpgs, and
$1.22$ for \mips. When visualizing the data, one finds that the
difference between \lpgs's and \mffs's plans grows with instance size.
\semsyn, again, finds the best (shortest) plans for those instances
that it solves. The quotients \mffs\ versus \semsyn\ are $1.00$,
$2.72$, and $4.50$ on the three instances solved by \semsyn.




The optimization criterion in {\sl Zenotravel} is to minimize some
(instance-specific) linear combination of total time and fuel
consumption. \mffq's runtime behavior is worse than that of \mffs,
solving only the smaller half of the test set. \mipsq\ solves only the
first 16 instances, \lpgq\ solves all but the largest instance. The
optimization criterion values of \mffq\ are on average $0.82$ times
those of \mffs, so an optimization effect can be observed. The
quotient values versus Best-of are $1.51$ for \mffq, $1.39$ for \lpgq,
and $1.14$ for \mipsq.

















\subsection{Satellite}
\label{results:Satellite}






In {\sl Satellite}, a number of Satellites must make a number of
observations using their installed instruments. This involves turning
the Satellites the right direction, switching the instruments on or
off, calibrating the instruments, and taking images. In the numeric
version of the domain, turning the Satellites consumes
(non-replenishable) fuel, the images occupy data memory, and the
Satellites have only limited data memory capacity.
Figure~\ref{eps/sat.eps} shows the runtime data on the 20 problem
instances used in the competition.


%figure
\scalefig{1.0}{eps/sat.eps}{Runtime curves on {\sl Satellite}
  instances for the planners favoring speed. Time is shown on a
  logarithmic scale, instance size scales from left to right.}




In this domain, the participating planners were \mff, \lpg, \mips, and
\tpfour\ \cite{haslum:geffner:ecp-01}. \tpfour\ (which finds plans
with optimal makespan) solves 3 of the smallest instances, \mipss\ 
solves 7 of the smaller instances, \lpgs\ solves 10 instances, and
\mffs\ solves 14. Note, though, that the instances that \lpgs\ fails
to solve but \mffs\ solves are mainly the smaller ones. As for plan
length, the quotients versus Best-of are $1.11$ for \mffs, $1.04$ for
\lpgs\ and \mipss, and $1.09$ for \tpfour. So plan lengths are roughly
similar, but \lpgs\ and \mipss\ seem to have a slight advantage over
\mffs.



\begin{sloppypar}
  The optimization criterion in {\sl Satellite} is to minimize overall
  fuel consumption. \mffq's (\mipsq's) runtime behavior is a lot worse
  than that of \mffs\ (\mipss), solving only 2 (4) of the smallest
  instances. \lpgq\ solves the same instances as \lpgs. The fuel
  consumption of \mffs\ on the 2 instances that \mffq\ solves is $109$
  and $97$. That of \mffq\ is $109$ and $83$, so there is a slight
  optimization effect on one of the two instances. \lpgq\ finds the
  best plans for all instances that it solves (thus the quotient
  versus Best-of is constantly $1.00$), the comparison of \mipsq\ to
  Best-of is $2.54$.
\end{sloppypar}






The competition also featured a version of {\sl Satellite}
(``Hard-Numeric'') where there were no logical or numeric goals at
all, and the optimization criterion was to maximize the amount of
stored data (\ie the memory occupied by the taken images). This is an
example of an optimization criterion that can not be transformed into
action costs in the sense explained in Section~\ref{metric-ff:cost}.
The actions that take images have negative costs. \mff\ thus rejects
the optimization criterion and reports, for all instances, that they
are trivially solved by the empty plan.  Similarly, the plans returned
by \mipss\ are all empty.  The \mipsq\ version finds non-trivial plans
for the smaller half of the instances.  For \lpg\ there is no data in
the competition results for this domain version.


















\subsection{Rovers}
\label{results:rovers}



In {\sl Rovers}, a number of planetary rovers must analyze a number of
rock or soil samples, and take a number of images. This involves
navigating the rovers, taking or dropping samples (rovers can only
hold one sample at a time), calibrating the camera and taking images,
and communicating the data to a lander. In the numeric version of the
domain, all the activities decrease the energy available for the rover
by a certain amount, and an energy recharge operator can be applied
when the rover is located in a sunny spot.  Figure~\ref{eps/sat.eps}
shows the runtime data on the 20 {\sl Rovers} instances used in the
competition.



%figure
\scalefig{1.0}{eps/rov.eps}{Runtime curves on {\sl Rovers} instances
  for the planners favoring speed. Time is shown on a logarithmic
  scale, instance size scales from left to right.}




The participating planners in this domain were \mff, \lpg, and \mips.
None of the planners can solve the whole test set, in fact \lpg, which
scales best, is the only planner that can solve most of the larger
instances.\footnote{In the actual competition data, \lpg\ failed to
  solve 8 of the instances due to an implementation bug. We show the
  corrected data provided by Alfonso Gerevini.} The smaller instances
are solved quickly by all three participants. \mffs\ might have a
slight plan length advantage. The quotients versus Best-of are $1.02$
for \mffs, $1.26$ for \lpgs, and $1.19$ for \mipss.





The optimization criterion in {\sl Rovers} is to minimize the number
of recharge actions applied in the plan (\ie the cost of recharging is
$1$, the cost of all other actions is $0$). With this optimization
criterion, \mffq\ does not solve a single instance (we will return to
this in the outlook). \mipsq\ and \lpgq\ solve the same instances as
their speed-favoring counterparts. \lpgq's plan quality is $0$ in all
the 8 instances that \mipsq\ solves. \mipsq's plans contain $0$
recharge actions in three cases, $1$ recharge action in four cases,
and $2$ recharge actions in one case.






















\subsection{Settlers}
\label{results:settlers}








The {\sl Settlers} domain is about building up an infrastructure in an
unsettled area. The things to be built include housing, railway
tracks, sawmills, etc. There are a lot of operator schemata encoding a
complex building process. The raw materials, timber, stone, and ore,
must first be felled, broken, or mined. One can then process timber
into wood or coal, and process ore into iron. Carts, trains, or ships
can be built to transport materials. One can combine materials to
build docks, wharfs, rails, housing, etc. The encoding makes a more
intensive use of numeric variables than the other domains. While in
the other domains the numeric constructs mainly encode resource
constraints and action costs, in {\sl Settlers} the numeric variables
play an active part in achieving the goal. Indeed, many of the
operator schemata have no logical effects at all. For example, felling
timber increases the amount of timber available at the respective
location by one unit. Loading (unloading) a material unit onto (from)
a vehicle is encoded by increasing (decreasing) the respective
material availability in the vehicle while decreasing (increasing) the
material's availability at the respective location.  For building a
housing unit at least one wood and stone unit must be available,
resulting in increased housing units and decreased wood and stone
units. With the numeric variables playing such an active role in the
domain encoding, {\sl Settlers} is a very interesting benchmark for
numeric planners.  Figure~\ref{eps/sat.eps} shows the runtime data on
the 20 {\sl Settlers} instances used in the competition.


%figure
\scalefig{1.0}{eps/set.eps}{Runtime curves on {\sl Settlers} instances
  for the planners favoring speed. Time is shown on a logarithmic
  scale, instance size scales from left to right.}



Only \mff\ and \mips\ (in the versions that favor speed) were able to
solve some of the {\sl Settlers} instances. \lpg\ could not
participate in this domain because some operators make use of
universally quantified effects, which \lpg\ does not support. \mipss\ 
solves only a single instance while \mffs\ solves the 6 smallest
instances. It should be noted here that the instances in this example
suite appear to be rather large. \mffs's plans on the 6 smallest
instances contain $53$, $26$, $102$, $67$, $74$, and $81$ actions
respectively. For comparison, in all of the other domains except {\sl
  Depots} \mffs's longest plan in the first 6 instances contains $26$
steps. In {\sl Depots} the numbers are $10$, $15$, $35$, $34$, $75$,
the 6th instance isn't solved by any planner. The plan that \mipss\ 
finds for the second smallest instance contains $36$ steps (as stated
above \mffs's plan for this instance contains $26$ steps). No planner
favoring quality solved any of the {\sl Settlers} instances.




















\subsection{Performance Summary}
\label{results:performance}








In their speed-favoring configurations, \mff\ and \lpg\ perform the
best, both in terms of runtime and solution length. For runtime, in
{\sl Driverlog} and {\sl Rovers}, \lpg\ scales better (solves more
instances). In {\sl Zenotravel}, \mff\ scales better (an order of
magnitude advantage in runtime). In {\sl Settlers}, \lpg\ could not be
run, but \mff\ can solve some rather large instances. In {\sl Depots}
and {\sl Satellite}, there is a slight advantage for \mff, which
solves a few more instances. \mips\ lags behind both \mff\ and \lpg\ 
in all the domains except {\sl Zenotravel} where it scales roughly
similar to \lpg. As for solution length, this is roughly similar for
\lpg\ and \mff\ in all of the domains except {\sl Zenotravel}, where
\lpg's plans are longer. In {\sl Satellite} there might be a slight
advantage for \lpg, and in {\sl Rovers} there might be a slight
advantage for \mff. The plan lengths of \mips\ are roughly similar to
those of \mff\ across all the domains.







The results for \mff\ in optimization mode, \mffq, are less
satisfying, at least as far as runtime behavior is concerned. \mffq\ 
does not solve a single instance in {\sl Rovers} and {\sl Settlers},
and it solves only very few instances in {\sl Depots}, {\sl Driverlog}
(with the normal, i.e. not ``hard'' optimization expression), and {\sl
  Satellite}. \mffq's runtime behavior is reasonably good only in {\sl
  Zenotravel} and {\sl Driverlog} (with the ``hard'' optimization
expression). The solution quality behavior is mixed. In most cases it
can be observed that \mffq's plans are better in the sense of the
optimization criterion than \mffs's plans are. Better plan quality is
clearly observable in {\sl Driverlog} (with the ``hard'' optimization
expression) and {\sl Zenotravel}. It is also observable in {\sl
  Driverlog} (with the normal optimization expression) and {\sl
  Satellite}, although only a small number of instances were solved in
these domains. Compared to \lpgq\ and \mipsq, \mffq\ is the only
quality-favoring planner here that shows dramatically worse runtime
behavior than its speed-favoring counterpart. The reasons for that
must lie in the algorithmic differences between the systems,
concerning the way they treat optimization expressions. In the outlook
we speculate on the reasons for \mffq's poor runtime behavior, and
what might be done about it.







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








We have presented a natural extension of a popular heuristic technique
for \strips\ -- ignoring delete lists -- to numeric planning. The
straightforward implementation of \mff\ based on the technique was one
of the two best performing numeric planning systems at \ipcthree.




Let us summarize the contributions of this work in a little more
detail. The most important contribution is the ``monotonicity'' idea,
\ie a numeric framework in which the main \strips\ concepts
(pre/goal-conditions, add lists, and delete lists) translate very
naturally to the numeric concepts (monotonic constraints, increasing
effects, and decreasing effects).  The monotonicity idea might be
useful in many other contexts beside the specific heuristic planner
implementation we focus on in this article (some ideas on that are
given in the outlook below). In the heuristic context considered here,
we have:

\begin{itemize}
\item Abstracted the desirable properties (admissibility, basic
  informedness, and polynomiality) that ignoring delete lists has as a
  relaxation in \strips.
\item Defined a natural extension of this relaxation to the numeric
  case and provided sufficient criteria to identify numeric tasks
  where the relaxation preserves the desirable properties.
\item Defined a subset of \pddl2.1 level 2, linear tasks, where the
  sufficient criteria can be achieved by a pre-processing technique.
\item Defined algorithms that solve relaxed tasks in this language and
  thus provide a heuristic function.
\item Implemented a straightforward extension of \ff, and a first
  technique that takes user-specified optimization criteria into
  account. The \ff\ extension (FF.speed) shows reasonable performance
  across a number of benchmark domains. Specifically it performed
  best, together with \lpg, in the numeric track of the 3rd
  International Planning Competition, both in terms of runtime and
  solution length.\footnote{Note that one can easily imagine domains
    where relaxed plans in the way \mff\ uses them would likely yield
    no good heuristic information. As an example, consider the
    15-puzzle, with numeric variables encoding the positions of the
    tiles. In this situation, there is a large degree of interaction
    between the numeric variables, and relaxed plans will presumably
    not be able to capture this interaction.} The runtime behavior of
  the optimization technique (FF.quality) is unsatisfying, but plan
  quality improvements can be observed.
\end{itemize}





\noindent
Various research topics have been left open:

\begin{itemize}
\item The background theory given in
  Section~\ref{relaxation:monotonicity} provides only sufficient
  criteria for the numeric relaxation to be adequate. The question is,
  are there weaker sufficient criteria, and can one come up with a
  complete analysis (\ie find the exact borders beyond which ignoring
  decreasing effects is no longer adequate)? Also, how do the
  identified borderlines translate, syntactically, to the mathematical
  constructs allowed in \pddl2.1 level 2?
\item The pre-processing algorithm given in
  Section~\ref{relaxation:linear} (transforming linear tasks into LNF
  tasks) is defined for linear tasks only. Can it be extended to
  richer language classes? Similarly, the algorithms given in
  Section~\ref{rplans:lnf} only work for LNF. Is there an easy
  extension to richer language classes?
\item As mentioned in Section~\ref{relaxation:linear}, various kinds
  of numeric effects can easily be translated into each other (\eg
  $\asseff$ effects into $\inceff$ effects or vice versa), but the
  respective translations behave differently in the relaxation. Can
  one identify problem classes where one or the other formulation
  yields better heuristic performance?
\item The current optimization technique, FF.quality, is restricted to
  optimization criteria that can be transformed into action cost
  minimization according to a certain simple translation schema. How
  can more general optimization criteria be handled?
\item We have seen that the runtime performance of FF.quality is
  unsatisfying. There appears to be some interaction (as exemplified
  by the two different quality metrics in {\sl Driverlog}) between the
  form of the optimization (\ie the action cost minimization)
  expression and runtime behavior. An explanation for this might be
  the degree of ``goal-directedness'' of the minimization expression.
  Intuitively, a minimization expression is goal-directed if it is
  closely correlated with goal distance, \ie the lower the expression
  value the nearer the goal and vice versa.  The maximally
  goal-directed minimization expression is the goal distance itself
  (i.e., ``total-time'' in our sequential framework).  In contrast,
  the minimization expression in {\sl Rovers}, number of recharge
  operations, is only very loosely connected with goal distance. It
  would be worthwhile to come up with a good formal notion of
  goal-directedness, and to investigate its connection with runtime
  performance (in {\sl Driverlog} the connection is less obvious than
  in {\sl Rovers}). On the more practical side, algorithms remain to
  be found that show better performance no matter what the form of the
  optimization expression is. One option is to always integrate, to
  some extent, the current goal distance estimate (\ie the length of
  the relaxed plan in our case) into the remaining cost estimation.
  Another option is to use different search schemes. A
  branch-and-bound like approach appears possible (first find some
  plan quickly then use the cost of this plan as an upper bound during
  further exploration of the search space).
\end{itemize}




It would be exciting to explore the impact of the monotonicity idea,
\ie the correspondence that it brings between pre/goal-conditions and
monotonic constraints, add lists and increasing effects, as well as
delete lists and decreasing effects, in different contexts of planning
research.  Examples that spring to mind are other heuristic
approaches, \graphplan-based numeric planning, or goal ordering
techniques. To stimulate the imagination of the reader:

\begin{itemize}
\item It seems likely that similar methods can be used in other
  heuristic approaches that relax the task by ignoring the delete
  lists. For example, our techniques can presumably be adapted to
  heuristic estimators in the partial order framework used in \repop\ 
  \cite{nguyen:kambhampati:ijcai-01}, yielding a heuristic numeric
  partial-order planner. Also, it appears feasible to integrate our
  techniques into \sapa's \cite{do:kambhampati:ecp-01} heuristic
  function, possibly making that function more accurate in various
  numeric situations. As another possible avenue, one might be able to
  adapt the techniques presented here for use in \lpg's heuristic
  precondition cost estimation process \cite{gerevini:et:al:icaps-03},
  making it more sensitive to the numeric constructs, and thereby --
  potentially -- further improving \lpg's performance.
\item Koehler's extension of \ipp\ to a numeric context
  \cite{koehler:ecai-98} suffers from complications in the backward
  search procedure, which significantly degrade runtime performance.
  Do the same difficulties arise in the monotonic context?
\item Koehler and Hoffmann \shortcite{koehler:hoffmann:jair-00} argue
  that there is a reasonable ordering $B \leq A$ between two goals $A$
  and $B$ if, from all states where $A$ is achieved first, one must
  delete $A$ in order to achieve $B$. Under monotonicity, the
  straightforward translation of this is that two numeric goals $A$
  and $B$ are ordered $B \leq A$ if, once the values of the variables
  that participate in $A$ are sufficient to achieve $A$, their values
  must be decreased below the necessary value again in order to
  achieve $B$. It seems that Koehler and Hoffmann's techniques to
  approximate \strips\ goal orderings transfer easily to this
  situation. Similarly, it seems that under monotonicity the
  definitions and approximation techniques given for landmarks
  (subgoals that will necessarily arise during planning) by Porteous,
  Sebastia, and Hoffmann \shortcite{porteous:et:al:ecp-01} can
  directly be transferred to numeric goals.
\end{itemize}



%
% future work: diff viewpoint by David, extensions opened up by that







\acks{Metric-FF was developed and implemented while the author was
  visiting the Durham Planning Group, Durham, UK. Thanks go to Maria
  Fox and Derek Long for discussions, and for making the stay
  enjoyable. Thanks also go to Malte Helmert for some fruitful remarks
  on the relaxation theory. I thank David Smith for his insights into
  the nature of inverted variables, and for many detailed comments on
  the language. Finally I thank the anonymous reviewers for their
  comments, which helped improve the paper.}


% REV AND DAVID ACK
%


\begin{appendix}


\section{Proofs}
\label{proofs}





This appendix presents the proofs to all theorems in detail. There are
three different classes of results, which we focus on in turn:
relaxation adequacy, relaxed \graphplan\ completeness, and relaxed
\graphplan\ correctness. Within each of these classes, the results are
given for languages of increasing expressivity.














\subsection{Relaxation Adequacy}
\label{proofs:adequacy}





For \strips, the restricted numeric language, and numeric tasks in
general, we prove that the respective relaxations are adequate (in the
general case, we identify situations where the relaxation is
adequate). The proof for the \strips\ case is trivial.




\bigskip
\noindent
{\bf Proposition 1} {\em The relaxation given in
  Definition~\ref{def:strips-relaxation} is adequate, \ie the
  following holds true.

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: any plan that solves the original task also
  solves the relaxed task, \ie assuming a \strips\ task $(\propos,
  \actions, \initial, \goal)$, any plan for $(\propos, \actions,
  \initial, \goal)$ is also a relaxed plan for $(\propos, \actions,
  \initial, \goal)$.
\item {\em Basic informedness}: the preconditions and goals can
  trivially be achieved in the original task if and only if the same
  holds in the relaxed task, \ie assuming a \strips\ task $(\propos,
  \actions, \initial, \goal)$, $\langle \rangle$ is a plan for
  $(\propos, \actions, \initial, \goal)$ if and only if $\langle
  \rangle$ is a relaxed plan for $(\propos, \actions, \initial,
  \goal)$, and for $a \in \actions$, $\result(\initial, \langle
  \rangle) \supseteq \pre(a)$ if and only if $\result(\initial,
  \langle \rangle) \supseteq \pre(a^{\relaxed})$.
\item {\em Polynomiality}: the relaxed task can be solved in
  polynomial time, \ie deciding \stripsrelaxedplansat\ is in \poly.
\end{enumerate}
\end{sloppypar}
}
\medskip

\begin{beweis}
  1. After application of each action in the relaxed action sequence,
  at least the propositions are true that are true in the real
  sequence. So each action precondition, and the goal, is fulfilled.
    
  2. Holds because we are not dropping any precondition or goal
  constraints. The empty plan $\langle \rangle$ is a plan for
  $(\propos, \actions, \initial, \goal)$ if and only if $\goal
  \subseteq \initial$ holds. The same is true for $(\propos,
  \actions^{\relaxed}, \initial, \goal)$. Similarly for action
  preconditions.
    
  3. This has been proven by Bylander \shortcite{bylander:ai-94}.
\end{beweis}







The proof for the case of the restricted numeric language is a
straightforward extension to the \strips\ proof, exploiting the
correspondence between pre/goal-conditions, add lists, and delete
lists on the one hand, and $x \geq [>] c$ constraints, $\inceff$
effects, and $\deceff$ effects on the other hand.



\bigskip
\noindent
{\bf Theorem 1} {\em The relaxation given in
  Definition~\ref{def:restricted-relaxation} is adequate, \ie the
  following holds true.

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: assuming a restricted numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, any plan for $(\vars, \propos,
  \actions, \initial, \goal)$ is also a relaxed plan for $(\vars,
  \propos, \actions, \initial, \goal)$.
\item {\em Basic informedness}: assuming a restricted numeric task
  $(\vars, \propos, \actions, \initial, \goal)$, $\langle \rangle$ is
  a plan for $(\vars, \propos, \actions, \initial, \goal)$ if and only
  if $\langle \rangle$ is a relaxed plan for $(\vars, \propos,
  \actions, \initial, \goal)$, and for $a \in \actions$,
  $\result(\initial, \langle \rangle) \models \pre(a)$ if and only if
  $\result(\initial, \langle \rangle) \models \pre(a^{\relaxed})$.
\item {\em Polynomiality}: deciding \restrictedrelaxedplansat\ is in
  \poly.
\end{enumerate}
\end{sloppypar}
}
\medskip

\begin{beweis}
  1. After application of each step in the relaxed plan, at least the
  propositions are true that are true in the real plan, and the values
  of all numeric variables are at least as high as in the real plan.
  As all action preconditions and the goal only require variable
  values to be greater than or equal to a constant, all these
  constraints remain fulfilled.
    
  2. Holds because we are not dropping any precondition or goal
  constraints. The empty plan $\langle \rangle$ is a plan for $(\vars,
  \propos, \actions, \initial, \goal)$ if and only if $\initial
  \models \goal$ holds. The same is true for $(\vars, \propos,
  \actions^{\relaxed}, \initial, \goal)$. Similarly for action
  preconditions.
    
  3. The following is a polynomial time algorithm that decides
  \restrictedrelaxedplansat.

\begin{tabbing}
$M$ := $\initial$, $m$ := $\varsof(\initial)$\\
remove, from action preconditions and the goal, all propositions in $M$ and\\
all numeric constraints that are fulfilled by the $m^i$ values (i.e., $m^i \geq [>] c$)\\
{\bf while} $\goal \neq \emptyset$ {\bf do}\\
\hspace{0.3cm} \= $A$ := $\{ a \in \actions \mid \pre(a) = \emptyset \}$\\
\> $M'$ := $M \cup \bigcup_{a \in A} \proposof(\eff(a))^+$\\
\> $m'$ := $m$\\
\> {\bf for} \= $i \in \{ 1, \dots, n \}, m^i \neq \infty$ {\bf do}\\
\> \> {\bf if} \= $\exists a \in A: (v^i, \inceff, c) \in
\varsof(\eff(a))$ {\bf then} $(m')^i := \infty$ {\bf endif}\\
\> {\bf endfor}\\
\> {\bf if} \= $M' = M$ and $m' = m$ {\bf then} fail {\bf endif}\\
\> $M$ := $M'$, $m$ := $m'$\\
\> remove, from action preconditions and the goal, all propositions in $M$ and\\
\> all numeric constraints that are fulfilled by the $m^i$ values\\
{\bf endwhile}\\
succeed
\end{tabbing}

Remember that $n$ denotes the number of numeric variables. Denote by
$A_t$ the action set in iteration $t$ of this algorithm. We prove that
the algorithm succeeds if there is a relaxed plan, that there is a
relaxed plan if the algorithm succeeds, and that the algorithm takes
polynomial time in the size of the task.

If there is a relaxed plan $\langle a_1, \dots, a_k \rangle$ for
$(\vars, \propos, \actions, \initial, \goal)$, then $a_t \in A_t$
holds true for $1 \leq t \leq k$: the set $M$ (the values $m$) always
include (are always at least as high as) the true facts in the relaxed
plan (the variable values in the relaxed plan). The algorithm succeeds
after at most $k$ iterations. It does not fail earlier as this implies
a fixpoint in contradiction to reachability of the goals.

In the other direction, if the algorithm succeeds in an iteration $k$
then one can construct a relaxed plan. Simply linearize the
(relaxations of the) actions in the sets $A_1, \dots, A_k$ in an
arbitrary order. If an action at a layer $t$ has a $\inceff$ effect on
a variable $x^i$, then repeatedly execute the action until all
constraints on $x^i$ that have been removed in iteration $t$ are
fulfilled (as all the constraints are of the form $x^i \geq [>] c$,
this will eventually happen). The actions applied this way all have
their preconditions fulfilled as these were empty at the respective
iteration, and the execution sequence makes the same constraints true
as the algorithm.

As for runtime, each single iteration is polynomial. An upper bound on
the number of iterations is $|\vars| + |\propos|$. In each iteration,
to avoid failure, at least one new proposition must enter $M$ or one
new variable value must be set to $\infty$.
\end{beweis}

















Generalizing from the restricted language, ignoring the decreasing
effects is adequate if all numeric constraints are monotonic, and all
numeric effects are strongly monotonic (plus changes due to $:=$
effects can not propagate into a numeric variable's own value). The
proof generalizes, in this way, from the proof above.









\bigskip
\noindent
{\bf Theorem 2} {\em The relaxation given in
  Definition~\ref{def:monotonic-relaxation} is adequate for strongly
  monotonic tasks with acyclic $\asseff$ effects, \ie the following
  holds true.
\medskip

\begin{sloppypar}
\begin{enumerate}
\item {\em Admissibility}: assuming a monotonic numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, any plan for $(\vars, \propos,
  \actions, \initial, \goal)$ is also a relaxed plan for $(\vars,
  \propos, \actions, \initial, \goal)$.
\item {\em Basic informedness}: assuming a numeric task $(\vars,
  \propos, \actions, \initial, \goal)$, $\langle \rangle$ is a plan
  for $(\vars, \propos, \actions, \initial, \goal)$ if and only if
  $\langle \rangle$ is a relaxed plan for $(\vars, \propos, \actions,
  \initial, \goal)$, and for $a \in \actions$ $\result(\initial,
  \langle \rangle) \models \pre(a)$ if and only if
  $\result^{\relaxed}(\initial, \langle \rangle) \models \pre(a)$.
\item {\em Polynomiality}: deciding \monotonicrelaxedplansat\ is in
  \poly.
\end{enumerate}
\end{sloppypar}
}

\begin{beweis}
  1. Say $\langle a_1, \dots, a_n \rangle$ is a plan for $(\vars,
  \propos, \actions, \initial, \goal)$. Executing the sequence under
  $\result$, all precondition and goal constraints are fulfilled.
  Denote by $\varsof^i(t)$ the value of variable $i$ after execution
  of action $a_t$, and denote by $\varsof^i(t)^{\relaxed}$ the value
  of variable $i$ after execution of action $a_t$ under
  $\result^{\relaxed}$. We show that $\varsof^i(t) \leq
  \varsof^i(t)^{\relaxed}$ for all $i$ and $t$. With monotonicity of
  numeric constraints, Definition~\ref{def:monotonicity} condition
  (1), this suffices. The claim is easily shown by induction over $t$.
  With $t = 1$, $\varsof^i(1) \leq \varsof^i(1)^{\relaxed}$ holds for
  all $i$ simply because $\result^{\relaxed}$ is identical to
  $\result$ except that all effects that decrease the value of a
  variable are ignored. From $t$ to $t+1$, if $\varsof^i(t) \leq
  \varsof^i(t)^{\relaxed}$ for all $i$ then $\varsof^i(t+1) \leq
  \varsof^i(t+1)^{\relaxed}$ holds for all $i$ due to the same
  argument, plus the monotonicity of the numeric effects in the
  sense of Definition~\ref{def:monotonicity} condition (2): the higher
  the input numeric variables are, the higher the resulting value of
  the affected variable becomes.
  
  2. The empty plan $\langle \rangle$ is a plan for $(\vars, \propos,
  \actions, \initial, \goal)$ if and only if $\initial \models \goal$
  holds. The same is true for $\langle \rangle$ as a relaxed plan, as
  we are not dropping any goal constraints. Similarly for action
  preconditions.
  
  3. The following is a polynomial time algorithm that decides relaxed
  solvability of a strongly monotonic task with acyclic $\asseff$
  effects.

\begin{tabbing}
1. \hspace{0.05cm} \= $M$ := $\initial$, $m$ := $\varsof(\initial)$\\
2. \> remove, from action preconditions and the goal, all propositions in $M$ and\\
\> all numeric constraints that are fulfilled by the $m^i$ values\\
3. \> {\bf while} $\goal \neq \emptyset$ {\bf do}\\
4. \> \hspace{0.3cm} \= $A$ := $\{ a \in \actions \mid \pre(a) = \emptyset \}$\\
5. \> \> $M'$ := $M \cup \bigcup_{a \in A} \proposof(\eff(a))^+$\\
6. \> \> $m'$ := $m$\\
7. \> \> {\bf for} \= $i \in \{ 1, \dots, n \}, m^i \neq \infty$ {\bf do}\\
8. \> \> \> {\bf if} \= $\exists a \in A, (v^i, \ass, \expr) \in
\varsof(\eff(a)):$\\
9. \> \> \> \> $\ass \in \{ \inceff, \deceff, \muleff, \diveff \}, (v^i, \ass, \expr)(m) > m^i$ 
{\bf then} $(m')^i := \infty$ {\bf endif}\\
10. \> \> {\bf endfor}\\
11. \> \> {\bf for} \> $i \in \{ 1, \dots, n \}, m^i \neq \infty$ {\bf do}\\
12. \> \> \> {\bf if} \> $\exists a \in A, (v^i, \asseff, \expr) \in
\varsof(\eff(a)): (v^i, \asseff, \expr)(m) > m^i$ {\bf then}\\
13. \> \> \> \> $(m')^i$ := $\max_{a \in A, (v^i, \asseff, \expr) \in
\varsof(\eff(a)): (v^i, \asseff, \expr)(m) > m^i} (v^i, \asseff, \expr)(m)$\\
14. \> \> \> {\bf endif}\\
15. \> \> {\bf endfor}\\
16. \> \> {\bf if} $M' = M$ and $m' = m$ {\bf then} fail {\bf endif}\\
17. \> \> $M$ := $M'$, $m$ := $m'$\\
18. \> \> remove, from action preconditions and the goal, all propositions in $M$ and\\
\> \> all numeric constraints that are fulfilled by the $m^i$ values\\
19. \> {\bf endwhile}\\
20. \> succeed
\end{tabbing}




Here, as above, $\varsof(\expr)$ for an expression $\expr$ denotes the
set of all variables contained in $\expr$. The value of an expression
that contains variables set to infinity is given as the limit of the
expression in these variables. Note that by assumption the limits are
all $\infty$ (Definition~\ref{def:monotonicity} condition (4)) so they
can, in particular, be computed efficiently. We prove that the
algorithm succeeds if there is a relaxed plan, that there is a relaxed
plan if the algorithm succeeds, and that the algorithm takes
polynomial time in the size of the task.



Denote by $A_t$ the action set in iteration $t$ of the algorithm. If
there is a relaxed plan $\langle a_1, \dots, a_k \rangle$ for $(\vars,
\propos, \actions, \initial, \goal)$, then $a_t \in A_t$ holds true
for $1 \leq t \leq k$: the variable updates on $m$ performed in the
algorithm are always at least as high as those performed by the
$\result^{\relaxed}$ function. Note here that line 13 takes the
maximum over the available $\asseff$ effects. Note also that all
effects obey Definition~\ref{def:monotonicity} condition (2), so one
needs consider only the maximum input values in order to obtain the
maximum output value. In consequence, with monotonicity of numeric
constraints in the sense of Definition~\ref{def:monotonicity}
condition (1), the algorithm reaches the goals and succeeds after at
most $k$ iterations. It does not fail earlier as this implies a
fixpoint in contradiction to reachability of the goals.





If the algorithm succeeds after an iteration $k$ then one can
construct a relaxed plan as follows. Perform an upwards loop from $1$
to $k$. At each iteration $t$, repeatedly apply all actions in $A_t$
until all the constraints that have been removed in line 18, in
iteration $t$, are fulfilled. We show below that this point will
eventually be reached. Once the point is reached, one can continue
with the next higher $t$ value until the step at the succeeding
iteration $k$ has been completed. All the actions applied this way
have their preconditions fulfilled as these were all empty at the
iteration $t$ where the actions are applied, as the constructed
relaxed plan always fulfills the same constraints that were removed in
an iteration, and as by Definition~\ref{def:monotonicity} condition
(1) constraints can not become false again once they are true in a
relaxed plan. For the same reason the goals are fulfilled at the end
of iteration $k$. It remains to show that, at an iteration $t$,
repeatedly applying the actions in $A_t$ will eventually fulfill all
the constraints removed in that iteration. Denote by $I_t$ the set of
all variables that got set, in iteration $t$, to $\infty$ in line 9,
denote by $I'_t$ the set of all variables that got set to $\infty$ in
line 13, and denote by $F_t$ the set of all variables that got set to
a new value below $\infty$ in line 13. We show that:

\begin{enumerate}
\item After one application of the actions in $A_t$ the variables in
  $F_t$ have at least the values that they had at constraint removal
  in line 18.
\item With repeated application of the actions in $A_t$ the variables
  in $I_t \cup I'_t$ reach arbitrarily high values.
\end{enumerate}

This suffices for the constraints eventually being fulfilled. The
variables in $F_t$ obviously play at least as well
(Definition~\ref{def:monotonicity} condition (1)) a role as in the
decision algorithm. As for the variables in $I_t \cup I'_t$, there is
a finite assignment to these variables, higher than their previous
values, that makes the respective constraints true at this point. This
is a simple consequence of Definition~\ref{def:monotonicity} condition
(1) (the constraints prefer higher variable values), condition (4)
(the expressions diverge in the variables), condition (5) (existence
of a finite fulfilling assignment), and the fact that the constraints
were not true in the previous iteration but became true when setting
the variables in $I_t \cup I'_t$ to $\infty$.


The first claim follows from the simple fact that the actions
responsible for increasing the values of the variables in $F_t$ -- the
actions that fulfill the condition in line 12 -- are, in particular,
contained in $A_t$. Their outcome might be higher if other variables
in the respective effect right hand side have been increased first;
there are no negative interactions with other variables as we are
considering the relaxed transition function. The argument for the
second claim is as follows. As for the variables in $I_t$, $A_t$
contains the respective responsible action fulfilling the condition in
lines 8 and 9. Each application of this action increases, by
Definition~\ref{def:monotonicity} condition (3), the variable's value
by at least as much as the previous application, so repeated
application diverges. Note that, again, under relaxed state
transition, applying an action can not worsen the situation for other
variables. As for the variables in $I'_t$, $A_t$ contains the action
$a$ fulfilling the condition in line 13, with $(v^i, \asseff, \expr)
\in \varsof(\eff(a))$, $\expr$ containing at least one variable $v'
\in \varsof(\expr)$ set to $\infty$ at this point (as $(v^i, \asseff,
\expr)(m) = \infty$). Recursively, a responsible action $a'$ setting
$v'$ to $\infty$ must have been included in the previous iteration. If
the effect of $a'$ on $v'$ is a $\asseff$ effect, a responsible action
must have been included earlier, and so on. At one point, the
responsible action $a''$ for the respective ancestor variable $v''$
must have been included in line 9.  Repeated application of $a''$
causes the value of $v''$ to diverge (with the same argument as
above), and in effect transitively causes the value of $v^i$ to
diverge.




It finally remains to show that the algorithm terminates in polynomial
time. Obviously each single iteration is polynomial. The number of
iterations is bound by the number of times that $M'$ or $m'$ can be
different from $M$ respectively $m$. Changes to these values occur in
lines 5, 9, and 13. The overall number of changes in line 5 is bound
by the number of logical propositions, $|\propos|$. The overall number
of changes in line 9 is bound by the number of numeric variables,
$|\vars|$. So if there was an exponential number of iterations until
termination then there would be an exponential number of consecutive
iterations where changes occur only in line 13.  The number of such
consecutive iterations is, however, bound by $|\vars| * |\actions|$.
This can be seen as follows. Throughout the entire sequence of
iterations, only $\asseff$ effects contribute to the changes. The
$\asseff$ effects are acyclic by our assumption so their value change
can not propagate into their own value, and the only possible further
change can occur when a new action comes in. It takes at most
$|\vars|$ iterations to propagate the changes through all variables
(this is the length of the longest possible propagation path), so, if
at least one new action comes in at an iteration $t$, then another new
action comes in at iteration $t + |\vars|$ at the latest.  The obvious
bound on the number of iterations where new actions come in is
$|\actions|$, which concludes the argument.
\end{beweis}


































\subsection{Relaxed Graphplan Completeness}
\label{proofs:completeness}






For \strips\ and LNF tasks we prove that the respective relaxed
\graphplan\ mechanisms are complete, \ie that they find a relaxed plan
if there is one. The proof for the \strips\ case is trivial.






\bigskip
\noindent
{\bf Proposition 2} {\em Assume a \strips\ task $(\propos, \actions,
  \initial, \goal)$, and a state $s$. If the algorithm depicted in
  Figure~\ref{code:RPG_building} fails, then there is no relaxed plan
  for $(\propos, \actions, s, \goal)$.
}
\medskip

\begin{beweis}
  We show the contrapositive, \ie if there is a relaxed plan for
  $(\propos, \actions, s, \goal)$, then the algorithm succeeds. Say
  there is a relaxed plan $P = \langle a_1, \dots, a_m \rangle$ for
  $(\propos, \actions, s, \goal)$. The algorithm applies, at the first
  layer, all possible actions. In particular, this includes $a_1$, so
  at layer $P_1$ at least the facts are true that are true after
  executing the first step in $P$. The same argument can inductively
  be applied for all actions in $P$, implying that at each layer $t$
  we have $a_t \in A_t$, and $P_t$ contains all facts that are true
  upon execution of the first $t$ actions in $P$. This implies that
  the goals are true at some layer $m' \leq m$, $\goal \subseteq
  P_{m'}$. Moreover, the algorithm does not fail at any layer $m'' <
  m'$: if so then it follows that a fixpoint is reached, $P_{i} =
  P_{m''}$ for all $i > m''$, so $\goal \not \subseteq P_{m'}$, which
  contradicts our assumptions.
\end{beweis}









The proof for LNF tasks proceeds along the same line, but requires
some care with the details concerning the values beyond which numeric
variables can no longer contribute to a solution.






\bigskip
\noindent
{\bf Theorem 3} {\em Assume a linear numeric task $(\vars, \propos,
  \actions, \initial, \goal)$ that is in LNF and has acyclic $\asseff$
  effects. Assume a state $s$. If the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} fails, then there is no relaxed
  plan for $(\vars, \propos, \actions, s, \goal)$.  
}
\medskip

\begin{beweis}
  We show the contrapositive, \ie if there is a relaxed plan for
  $(\vars, \propos, \actions, s, \goal)$, then the algorithm succeeds.
  Say there is a relaxed plan $P = \langle a_1, \dots, a_m \rangle$
  for $(\vars, \propos, \actions, s, \goal)$. The algorithm applies,
  at the first layer, all possible actions. In particular, this
  includes $a_1$, so at layer $P_1$ at least the facts are true that
  are true after executing the first step in $P$, and the $max^i_1$
  values are at least as high as the respective variable values.
  Together with the fact that the effect right hand sides are
  positively monotonic (so inserting the $max_t$ values can only
  increase the outcome), the same argument can inductively be applied
  for all actions in $P$, implying that at each layer $t$ we have $a_t
  \in A_t$, $P_t$ contains all facts that are true upon execution of
  the first $t$ actions in $P$, and the $max^i_t$ values are at least
  as high as the respective variable values. This, with the
  monotonicity of the numeric constraints, implies that the goals will
  be reached at some layer $m' \leq m$, $\proposof(\goal) \subseteq
  P_{m'}$ and for all $(\expr, \geq [>], 0) \in \varsof(\goal):
  \expr(max_{m'}) \geq [>] 0$. Moreover, the algorithm does not fail
  at any layer $m'' < m'$. Assume it does. Then at $m''$ no new
  propositions have come in, and the $max^i$ values all either have
  not changed, or are already above their maximum needed value.
  Denote by $L$ the set of variables $v^i$ whose value is still too
  low, $max^i_{m''} \leq \maxneed^i(s)$. Note that $L \subseteq rV$
  holds since outside $rV$ the $\maxneed$ values are $-\infty$. We
  have $P_{m''+1} = P_{m''}$ and, for all $v^i \in L$, $max_{m''+1}^i
  = max_{m''}^i$. We show that $P_{m''+2} = P_{m''+1}$ and, for all
  $v^i \in L$, $max_{m''+2}^i = max_{m''+1}^i$. This proves the claim:
  by iterating the argument, the same holds true at all layers $t >
  m''+1$, and we get a contradiction to the goals being reached at
  $m'$ (note that all constraints in which a variable out of $\vars
  \setminus L$ participates are already fulfilled, so increasing these
  variables can not reach new goal constraints). The set of
  propositions could increase at layer $m'' + 2$ if a new action came
  in, \ie if there was $a \in A_{m''+1}$, $a \not \in A_{m''}$. The
  value of a variable $v^i \in L$ could increase at layer $m'' + 2$
  if: a new action came in; a $\inceff$ effect right hand side
  expression $(v^i, \inceff, \expr)$ became positive in $A_{m''+1}$ as
  a result of increasing the $\vars \setminus L$ variable values from
  $m''$ to $m'' + 1$; a $\asseff$ right hand side expression $(v^i,
  \asseff, \expr)$ in $A_{m''+1}$ became higher than $max^i_{m''+1}$
  as a result of increasing the $\vars \setminus L$ variable values
  from $m''$ to $m'' + 1$. None of these three cases can occur by
  definition of the $\maxneed$ values (that the variables in $\vars
  \setminus L$ have reached). As for the first case, $A_{m''+1}$ can
  not contain a new action because no new precondition constraints
  became true from $m''$ to $m'' + 1$ -- only the $\vars \setminus L$
  variable values have increased, and the constraints in which these
  participate are already fulfilled at $m''$. As for the second case,
  all $(v^i, \inceff, \expr)$ effect right hand sides in which $\vars
  \setminus L$ variables participate are already above $0$ with the
  values at $m''$ ($v^i \in L \subseteq rV$, so the $\maxneed$
  definition for $\inceff$ effects applies). As for the third case, if
  this occurred then there was at least one variable $v^j \in \vars
  \setminus L$ contained in the right hand side of the responsible
  effect $(v^i, \asseff, \expr)$. This variable would fulfill
  $max_{m''}^j > \maxneed^j(s)$, thus $\expr(max_{m''}) >
  \maxneed^i(s)$ would hold ($v^i \in L \subseteq rV$, so the
  $\maxneed$ definition for $\asseff$ effects applies), thus
  $max^i_{m''+1} > \maxneed^i(s)$ would hold (through application of
  $(v^i, \asseff, \expr)$ in $A_{m''}$) in contradiction to our
  assumptions. This concludes the argument.
\end{beweis}




















\subsection{Relaxed Graphplan Correctness}
\label{proofs:correctness}






For \strips\ and LNF tasks we prove that the respective relaxed
\graphplan\ mechanisms are correct, \ie that the actions they select
form a relaxed plan. The proof for the \strips\ case is trivial.








\bigskip
\noindent
{\bf Proposition 3} {\em Assume a \strips\ task $(\propos, \actions,
  \initial, \goal)$, and a state $s$ for which the algorithm depicted
  in Figure~\ref{code:RPG_building} reaches the goals. The actions
  selected by the algorithm depicted in
  Figure~\ref{code:plan_extraction} form a relaxed plan for $(\propos,
  \actions, s, \goal)$.
}
\medskip

\begin{beweis}
  First, note that at each layer $t$ and for each goal $g \in
  \goal_t$, there is at least one action $a$ such that $level(a) = t -
  1$, $g \in \eff(a)^+$, due to the way the levels are computed. Also,
  an action's preconditions always have a lower level than the action
  itself. 
  
  The algorithm selects a set $\actions_t$ at each layer $t$. We can
  arrange the actions in each of these sets in an arbitrary order to
  obtain a relaxed plan for $(\propos, \actions^{\relaxed}, s,
  \goal)$. All goals and sub-goals at a layer $t$ are achieved by the
  actions in $\actions_{t-1}$. So with delete effects being ignored,
  at least the propositions are true which are needed.
\end{beweis}






The proof for LNF tasks is a straightforward extension of the \strips\ 
proof.



\bigskip
\noindent
{\bf Theorem 4} {\em Assume a linear numeric task $(\vars, \propos,
  \actions, \initial, \goal)$ that is in LNF and has acyclic $\asseff$
  effects. Assume a state $s$ for which the algorithm depicted in
  Figure~\ref{code:lnf_RPG_building} reaches the goals. The actions
  selected by the algorithm depicted in
  Figure~\ref{code:lnf_plan_extraction} form a relaxed plan for
  $(\vars, \propos, \actions, s, \goal)$.
}
\medskip

\begin{beweis}
  First, note that at each layer $t$ and for each goal $g \in
  \goal_t$, there is at least one action $a$ such that $level(a) = t -
  1$, $g \in \eff(a)^+$, due to the way the levels are computed. For
  the numeric goals $(\expr, \geq [>], 0) \in \varsof(\goal_t)$, there
  is always a $\asseff$ effect with sufficiently high right hand side
  value, or
\[
max_{t}^i - \sum_{a \in A_t: (v^i, \inceff, \expr) \in
  \varsof(\eff(a)), \expr(max_{t-1}) > 0} \expr(max_{t-1}) =
max_{t-1}^i
\]
holds. In the first case the {\bf while} loop is not entered, in the
second case it terminates successfully. Note that one occurrence of an
action can support different logical and numeric goals by different
effects, but can not be used to support the same numeric goal twice.
  
  Denote, for a layer $t$, by $\actions_{t}$ the set of actions
  selected by the algorithm at that layer. We can arrange the actions
  in each of these sets in an arbitrary order to obtain a relaxed plan
  for $(\actions^{\relaxed}, s, \goal)$. All goals and sub-goals at a
  layer $t$, both logical and numeric, are achieved by the actions in
  $\actions_{t-1}$. The expressions in numeric goals and the effect
  right hand sides are always at least as high as required as we
  constrain all contained variables to take on their respective
  maximum values. With delete effects being ignored, at least the
  propositions are true which are needed. With decreasing effects
  being ignored and monotonicity of effect right hand sides, the
  expression values in constraints are at least as high as required.
\end{beweis}


\end{appendix}






%%
%%
%% bibliography
%%
%%



\vskip 0.2in
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Bacchus}{Bacchus}{2001}]{bacchus:aim-01}
Bacchus, F. \BBOP2001\BBCP.
\newblock \BBOQ The {AIPS}'00 planning competition\BBCQ\
\newblock {\Bem The AI Magazine}, {\Bem 22\/}(3), 47--56.

\bibitem[\protect\BCAY{Biundo\ \BBA\ Fox}{Biundo\ \BBA\ Fox}{1999}]{ecp99}
Biundo, S.\BBACOMMA\  \BBA\ Fox, M.\BEDS. \BBOP1999\BBCP.
\newblock {\Bem Recent Advances in AI Planning. 5th European Conference on
  Planning (ECP'99)}, Durham, UK. Springer-Verlag.

\bibitem[\protect\BCAY{Blum\ \BBA\ Furst}{Blum\ \BBA\
  Furst}{1997}]{blum:furst:ai-97}
Blum, A.~L.\BBACOMMA\  \BBA\ Furst, M.~L. \BBOP1997\BBCP.
\newblock \BBOQ Fast planning through planning graph analysis\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 90\/}(1-2), 279--298.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{1998}]{bonet:geffner:aips-ws-98}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP1998\BBCP.
\newblock \BBOQ {HSP}: Heuristic search planner\BBCQ\
\newblock In {\Bem {AIPS-98} {P}lanning {C}ompetition}, Pittsburgh, PA.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{1999}]{bonet:geffner:ecp-99}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP1999\BBCP.
\newblock \BBOQ Planning as heuristic search: New results\BBCQ
\newblock In Biundo\BBACOMMA\ \BBA\ Fox \cite{ecp99}, \BPGS\ 60--72.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{2001}]{bonet:geffner:ai-01}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2001\BBCP.
\newblock \BBOQ Planning as heuristic search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 129\/}(1--2), 5--33.

\bibitem[\protect\BCAY{Bonet, Loerincs,\ \BBA\ Geffner}{Bonet
  et~al.}{1997}]{bonet:et:al:aaai-97}
Bonet, B., Loerincs, G., \BBA\ Geffner, H. \BBOP1997\BBCP.
\newblock \BBOQ A robust and fast action selection mechanism for planning\BBCQ\
\newblock In {\Bem Proceedings of the 14th National Conference of the American
  Association for Artificial Intelligence (AAAI-97)}, \BPGS\ 714--719. MIT
  Press.

\bibitem[\protect\BCAY{Bylander}{Bylander}{1994}]{bylander:ai-94}
Bylander, T. \BBOP1994\BBCP.
\newblock \BBOQ The computational complexity of propositional {STRIPS}
  planning\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 69\/}(1--2), 165--204.

\bibitem[\protect\BCAY{Cesta\ \BBA\ Borrajo}{Cesta\ \BBA\
  Borrajo}{2001}]{ecp01}
Cesta, A.\BBACOMMA\  \BBA\ Borrajo, D.\BEDS. \BBOP2001\BBCP.
\newblock {\Bem Recent Advances in AI Planning. 6th European Conference on
  Planning (ECP'01)}, Toledo, Spain. Springer-Verlag.

\bibitem[\protect\BCAY{Do\ \BBA\ Kambhampati}{Do\ \BBA\
  Kambhampati}{2001}]{do:kambhampati:ecp-01}
Do, M.~B.\BBACOMMA\  \BBA\ Kambhampati, S. \BBOP2001\BBCP.
\newblock \BBOQ Sapa: A domain-independent heuristic metric temporal
  planner\BBCQ
\newblock In Cesta\BBACOMMA\ \BBA\ Borrajo \cite{ecp01}, \BPGS\ 109--120.

\bibitem[\protect\BCAY{Edelkamp}{Edelkamp}{2003}]{edelkamp:jair-03}
Edelkamp, S. \BBOP2003\BBCP.
\newblock \BBOQ Taming numbers and durations in the model checking integrated
  planning system\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}.
\newblock Special issue on the 3rd International Planning Competition, to
  appear.

\bibitem[\protect\BCAY{Edelkamp\ \BBA\ Helmert}{Edelkamp\ \BBA\
  Helmert}{2001}]{edelkamp:helmert:aim-01}
Edelkamp, S.\BBACOMMA\  \BBA\ Helmert, M. \BBOP2001\BBCP.
\newblock \BBOQ {MIPS}: The model checking integrated planning system\BBCQ\
\newblock {\Bem {AI} Magazine}, {\Bem 22\/}(3), 67--71.

\bibitem[\protect\BCAY{Fikes\ \BBA\ Nilsson}{Fikes\ \BBA\
  Nilsson}{1971}]{fikes:nilsson:ai-71}
Fikes, R.~E.\BBACOMMA\  \BBA\ Nilsson, N. \BBOP1971\BBCP.
\newblock \BBOQ {STRIPS}: A new approach to the application of theorem proving
  to problem solving\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 2}, 189--208.

\bibitem[\protect\BCAY{Fox\ \BBA\ Long}{Fox\ \BBA\
  Long}{2001}]{fox:long:aim-01}
Fox, M.\BBACOMMA\  \BBA\ Long, D. \BBOP2001\BBCP.
\newblock \BBOQ {STAN4}: A hybrid planning strategy based on subproblem
  abstraction\BBCQ\
\newblock {\Bem The AI Magazine}, {\Bem 22\/}(3), 81--84.

\bibitem[\protect\BCAY{Fox\ \BBA\ Long}{Fox\ \BBA\
  Long}{2002}]{fox:long:aips-02b}
Fox, M.\BBACOMMA\  \BBA\ Long, D. \BBOP2002\BBCP.
\newblock \BBOQ The third international planning competition: Temporal and
  metric planning\BBCQ
\newblock In Ghallab et~al. \cite{aips02}, \BPGS\ 333--335.

\bibitem[\protect\BCAY{Gazen\ \BBA\ Knoblock}{Gazen\ \BBA\
  Knoblock}{1997}]{gazen:knoblock:ecp-97}
Gazen, B.~C.\BBACOMMA\  \BBA\ Knoblock, C. \BBOP1997\BBCP.
\newblock \BBOQ Combining the expressiveness of {UCPOP} with the efficiency of
  {Graphplan}\BBCQ\
\newblock In Steel, S.\BBACOMMA\  \BBA\ Alami, R.\BEDS, {\Bem Recent Advances
  in AI Planning. 4th European Conference on Planning (ECP'97)},
  \lowercase{\BVOL}\ 1348 of {\Bem {L}ecture {N}otes in {A}rtificial
  {I}ntelligence}, \BPGS\ 221--233, Toulouse, France. Springer-Verlag.

\bibitem[\protect\BCAY{Gerevini, Saetti,\ \BBA\ Serina}{Gerevini
  et~al.}{2003a}]{gerevini:et:al:jair-03}
Gerevini, A., Saetti, A., \BBA\ Serina, I. \BBOP2003a\BBCP.
\newblock \BBOQ Planning through stochastic local search and temporal action
  graphs\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}.
\newblock Special issue on the 3rd International Planning Competition, to
  appear.

\bibitem[\protect\BCAY{Gerevini, Serina, Saetti,\ \BBA\ Spinoni}{Gerevini
  et~al.}{2003b}]{gerevini:et:al:icaps-03}
Gerevini, A., Serina, I., Saetti, A., \BBA\ Spinoni, S. \BBOP2003b\BBCP.
\newblock \BBOQ Local search techniques for temporal planning in {LPG}\BBCQ\
\newblock In {\Bem Proceedings of the 13th International Conference on
  Automated Planning and Scheduling (ICAPS-03)}, Trento, Italy. Morgan
  Kaufmann.
\newblock Accepted for publication.

\bibitem[\protect\BCAY{Ghallab, Hertzberg,\ \BBA\ Traverso}{Ghallab
  et~al.}{2002}]{aips02}
Ghallab, M., Hertzberg, J., \BBA\ Traverso, P.\BEDS., AIPS-02 \BBOP2002\BBCP.
\newblock {\Bem Proceedings of the 6th International Conference on Artificial
  Intelligence Planning and Scheduling (AIPS-02)}, Toulouse, France. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Ghallab\ \BBA\ Laruelle}{Ghallab\ \BBA\
  Laruelle}{1994}]{ghallab:laruelle:aips-94}
Ghallab, M.\BBACOMMA\  \BBA\ Laruelle, H. \BBOP1994\BBCP.
\newblock \BBOQ Representation and control in {IxTeT}, a temporal planner\BBCQ\
\newblock In {\Bem Proceedings of the 2nd International Conference on
  Artificial Intelligence Planning Systems (AIPS-94)}, \BPGS\ 61--67, Chicago,
  IL. {AAAI} Press, Menlo Park.

\bibitem[\protect\BCAY{Haslum\ \BBA\ Geffner}{Haslum\ \BBA\
  Geffner}{2001}]{haslum:geffner:ecp-01}
Haslum, P.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2001\BBCP.
\newblock \BBOQ Heuristic planning with time and resources\BBCQ
\newblock In Cesta\BBACOMMA\ \BBA\ Borrajo \cite{ecp01}, \BPGS\ 121--132.

\bibitem[\protect\BCAY{Helmert}{Helmert}{2002}]{helmert:aips-02}
Helmert, M. \BBOP2002\BBCP.
\newblock \BBOQ Decidability and undecidability results for planning with
  numerical state variables\BBCQ
\newblock In Ghallab et~al. \cite{aips02}, \BPGS\ 44--53.

\bibitem[\protect\BCAY{Hoffmann}{Hoffmann}{2000}]{hoffmann:ismis-00}
Hoffmann, J. \BBOP2000\BBCP.
\newblock \BBOQ A heuristic for domain independent planning and its use in an
  enforced hill-climbing algorithm\BBCQ\
\newblock In {\Bem Proceedings of the 12th International Symposium on
  Methodologies for Intelligent Systems (ISMIS-00)}, \BPGS\ 216--227.
  Springer-Verlag.

\bibitem[\protect\BCAY{Hoffmann}{Hoffmann}{2001}]{hoffmann:ijcai-01}
Hoffmann, J. \BBOP2001\BBCP.
\newblock \BBOQ Local search topology in planning benchmarks: An empirical
  analysis\BBCQ
\newblock In Nebel \cite{ijcai01}, \BPGS\ 453--458.

\bibitem[\protect\BCAY{Hoffmann}{Hoffmann}{2002a}]{hoffmann:ecai-02}
Hoffmann, J. \BBOP2002a\BBCP.
\newblock \BBOQ Extending {FF} to numerical state variables\BBCQ\
\newblock In {\Bem Proceedings of the 15th European Conference on Artificial
  Intelligence (ECAI-02)}, \BPGS\ 571--575, Lyon, France. Wiley.

\bibitem[\protect\BCAY{Hoffmann}{Hoffmann}{2002b}]{hoffmann:aips-02}
Hoffmann, J. \BBOP2002b\BBCP.
\newblock \BBOQ Local search topology in planning benchmarks: A theoretical
  analysis\BBCQ
\newblock In Ghallab et~al. \cite{aips02}, \BPGS\ 92--100.

\bibitem[\protect\BCAY{Hoffmann\ \BBA\ Nebel}{Hoffmann\ \BBA\
  Nebel}{2001}]{hoffmann:nebel:jair-01}
Hoffmann, J.\BBACOMMA\  \BBA\ Nebel, B. \BBOP2001\BBCP.
\newblock \BBOQ The {FF} planning system: Fast plan generation through
  heuristic search\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 14},
  253--302.

\bibitem[\protect\BCAY{Koehler}{Koehler}{1998}]{koehler:ecai-98}
Koehler, J. \BBOP1998\BBCP.
\newblock \BBOQ Planning under resource constraints\BBCQ\
\newblock In {\Bem Proceedings of the 13th European Conference on Artificial
  Intelligence (ECAI-98)}, \BPGS\ 489--493, Brighton, UK. Wiley.

\bibitem[\protect\BCAY{Koehler\ \BBA\ Hoffmann}{Koehler\ \BBA\
  Hoffmann}{2000a}]{koehler:hoffmann:jair-00}
Koehler, J.\BBACOMMA\  \BBA\ Hoffmann, J. \BBOP2000a\BBCP.
\newblock \BBOQ On reasonable and forced goal orderings and their use in an
  agenda-driven planning algorithm\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 12},
  338--386.

\bibitem[\protect\BCAY{Koehler\ \BBA\ Hoffmann}{Koehler\ \BBA\
  Hoffmann}{2000b}]{koehler:hoffmann:ecai-ws-00}
Koehler, J.\BBACOMMA\  \BBA\ Hoffmann, J. \BBOP2000b\BBCP.
\newblock \BBOQ On the instantiation of {ADL} operators involving arbitrary
  first-order formulas\BBCQ\
\newblock In {\Bem Proceedings ECAI-00 Workshop on New Results in Planning,
  Scheduling and Design}.

\bibitem[\protect\BCAY{Long\ \BBA\ Fox}{Long\ \BBA\
  Fox}{2003}]{long:fox:jair-03}
Long, D.\BBACOMMA\  \BBA\ Fox, M. \BBOP2003\BBCP.
\newblock \BBOQ The 3rd international planning competition: Results and
  analysis\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}.
\newblock Special issue on the 3rd International Planning Competition, to
  appear.

\bibitem[\protect\BCAY{McDermott}{McDermott}{1996}]{mcdermott:aips-96}
McDermott, D. \BBOP1996\BBCP.
\newblock \BBOQ A heuristic estimator for means-ends analysis in planning\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on
  Artificial Intelligence Planning Systems (AIPS-96)}, \BPGS\ 142--149. {AAAI}
  Press, Menlo Park.

\bibitem[\protect\BCAY{McDermott}{McDermott}{1999}]{mcdermott:ai-99}
McDermott, D.~V. \BBOP1999\BBCP.
\newblock \BBOQ Using regression-match graphs to control search in
  planning\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 109\/}(1-2), 111--159.

\bibitem[\protect\BCAY{Nebel}{Nebel}{2001}]{ijcai01}
Nebel, B.\BED., IJCAI-01 \BBOP2001\BBCP.
\newblock {\Bem Proceedings of the 17th International Joint Conference on
  Artificial Intelligence (IJCAI-01)}, Seattle, Washington, USA. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Nebel}{Nebel}{2000}]{nebel:jair-00}
Nebel, B. \BBOP2000\BBCP.
\newblock \BBOQ On the compilability and expressive power of propositional
  planning formalisms\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 12},
  271--315.

\bibitem[\protect\BCAY{Nguyen\ \BBA\ Kambhampati}{Nguyen\ \BBA\
  Kambhampati}{2001}]{nguyen:kambhampati:ijcai-01}
Nguyen, X.\BBACOMMA\  \BBA\ Kambhampati, S. \BBOP2001\BBCP.
\newblock \BBOQ Reviving partial order planning\BBCQ
\newblock In Nebel \cite{ijcai01}, \BPGS\ 459--464.

\bibitem[\protect\BCAY{Pednault}{Pednault}{1989}]{pednault:kr-89}
Pednault, E.~P. \BBOP1989\BBCP.
\newblock \BBOQ {ADL}: Exploring the middle ground between {STRIPS} and the
  situation calculus\BBCQ\
\newblock In Brachman, R., Levesque, H.~J., \BBA\ Reiter, R.\BEDS, {\Bem
  Principles of Knowledge Representation and Reasoning: Proceedings of the 1st
  International Conference (KR-89)}, \BPGS\ 324--331, Toronto, Ontario. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Porteous, Sebastia,\ \BBA\ Hoffmann}{Porteous
  et~al.}{2001}]{porteous:et:al:ecp-01}
Porteous, J., Sebastia, L., \BBA\ Hoffmann, J. \BBOP2001\BBCP.
\newblock \BBOQ On the extraction, ordering, and usage of landmarks in
  planning\BBCQ
\newblock In Cesta\BBACOMMA\ \BBA\ Borrajo \cite{ecp01}, \BPGS\ 37--48.

\bibitem[\protect\BCAY{Refanidis\ \BBA\ Vlahavas}{Refanidis\ \BBA\
  Vlahavas}{1999}]{refanidis:vlahavas:ecp-99}
Refanidis, I.\BBACOMMA\  \BBA\ Vlahavas, I. \BBOP1999\BBCP.
\newblock \BBOQ {GRT:} a domain independent heuristic for {STRIPS} worlds based
  on greedy regression tables\BBCQ
\newblock In Biundo\BBACOMMA\ \BBA\ Fox \cite{ecp99}, \BPGS\ 47--59.

\bibitem[\protect\BCAY{Refanidis\ \BBA\ Vlahavas}{Refanidis\ \BBA\
  Vlahavas}{2000}]{refanidis:vlahavas:ecai-00}
Refanidis, I.\BBACOMMA\  \BBA\ Vlahavas, I. \BBOP2000\BBCP.
\newblock \BBOQ Heuristic planning with resources\BBCQ\
\newblock In {\Bem Proceedings of the 14th European Conference on Artificial
  Intelligence (ECAI-00)}, \BPGS\ 521--525, Berlin, Germany. Wiley.

\bibitem[\protect\BCAY{Refanidis\ \BBA\ Vlahavas}{Refanidis\ \BBA\
  Vlahavas}{2001}]{refanidis:vlahavas:jair-01}
Refanidis, I.\BBACOMMA\  \BBA\ Vlahavas, I. \BBOP2001\BBCP.
\newblock \BBOQ The {GRT} planning system: Backward heuristic construction in
  forward state-space planning\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 15},
  115--161.

\bibitem[\protect\BCAY{Russell\ \BBA\ Norvig}{Russell\ \BBA\
  Norvig}{1995}]{russel:norvig:95}
Russell, S.\BBACOMMA\  \BBA\ Norvig, P. \BBOP1995\BBCP.
\newblock {\Bem Artificial Intelligence: A Modern Approach}.
\newblock Prentice-Hall, Englewood Cliffs, NJ.

\bibitem[\protect\BCAY{Smith\ \BBA\ Weld}{Smith\ \BBA\
  Weld}{1999}]{smith:weld:ijcai-99}
Smith, D.~E.\BBACOMMA\  \BBA\ Weld, D.~S. \BBOP1999\BBCP.
\newblock \BBOQ Temporal planning with mutual exclusion reasoning\BBCQ\
\newblock In {\Bem Proceedings of the 16th International Joint Conference on
  Artificial Intelligence (IJCAI-99)}, \BPGS\ 326--337, Stockholm, Sweden.
  Morgan Kaufmann.

\end{thebibliography}

%\bibliography{/home/hoffmann/tex/BIBLIO/abbreviations,/home/hoffmann/tex/BIBLIO/biblio,/home/hoffmann/tex/BIBLIO/crossref}
%\bibliographystyle{theapa}


\end{document}
