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


\jairheading{20}{2003}{239--290}{11/02}{12/03}
\ShortHeadings{Planning through Stochastic Local Search and Action 
Graphs in LPG}
{Gerevini, Saetti \& Serina}
\firstpageno{239}



\def\newplaintheorem#1#2{
\newtheorem{#1plain}{#2}
\newenvironment{#1}{\begin{#1plain}\rm }{\end{#1plain}}}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}


\newcommand{\G}{$\cal G$}
\newcommand{\Act}{{\cal A}}
\newcommand{\C}{ C}

\newcommand{\assign}{\leftarrow}
\newcommand{\vuoto}{o\hspace{-1.7mm}/}


\renewcommand{\textfraction}{0.0}
\def\stackdown#1#2{\mathrel{\mathop{#1}\limits_{#2}}}
\newcommand{\R}{I\hspace{-1mm}R}

\date{}
\begin{document}


\title{Planning through Stochastic Local Search and\\ 
Temporal Action Graphs in LPG}


\author{\name Alfonso Gerevini  \email gerevini@ing.unibs.it \\
\name Alessandro Saetti \email saetti@ing.unibs.it \\ 
\name Ivan Serina       \email serina@ing.unibs.it \\
\addr{Dipartimento di Elettronica per l'Automazione, 
Universit\`{a} degli Studi di Brescia \\
Via Branze 38, I-25123 Brescia, Italy} 
}


\maketitle


\begin{abstract}


We present some techniques for planning in domains specified with the
recent standard language {\sc pddl\small 2.1}, supporting ``durative
actions'' and numerical quantities. These techniques are implemented
in {\sc lpg}, a domain-independent planner that took part in the 3rd
International Planning Competition (IPC).
{\sc lpg} is an incremental, any time system producing
multi-criteria quality plans. The core of the system is based 
on a stochastic local search method and on a graph-based
representation called ``Temporal Action Graphs'' (TA-graphs).  
This paper focuses on temporal planning, introducing TA-graphs and
proposing some techniques to guide the search in {\sc lpg} using this
representation. 
The experimental results of the 3rd IPC, as well as further results
presented in this paper, show that our techniques can be very
effective. Often {\sc lpg} outperforms all other fully-automated
planners of the 3rd IPC in terms of speed to derive a solution, or
quality of the solutions that can be produced.
\end{abstract}
%


\section{Introduction}

Modeling temporal and numerical information in automated planning is
important for representing real-world domains, where actions take
time, and consume resources, and the quality of the solutions should
take these aspects into account. In the '80s and early '90s some
expressive, but inefficient, planning systems handling time were
developed \cite<e.g.,>{Vere83,Tsang86,Allen91:rap,PenWel94}.  More
recently, a number of alternative interesting approaches to temporal
planning has been proposed 
\cite<e.g.,>{Weld-IJCAI99-tgp,Kambha-ECP01-sapa,Geffner-ECP01-tp,DimGer02}.  
Some of these planners can compute plans with optimal makespan, but in
practice most of them scale up poorly.

Local search is emerging as a powerful method to address
fully-automated planning, though in principle this approach does not
guarantee generation of optimal plans. In particular, two planners that
successfully participated in the recent 3rd International Planning
Competition (IPC) are based on local search: {\sc ff}
\cite{HofNeb-JAIR01} and {\sc lpg}.

In earlier work on {\sc lpg} \cite{GerSer99,GerSerAIPS02} we proposed
a first version of our system using several techniques for local
search in the space of {\it action graphs} (A-graphs), particular
subgraphs of the planning graph representation \cite{BluFur95}. This
version of the planner handled only {\sc strips} domains, possibly
extended with simple costs associated with the actions.  In this
paper, which is a revised and extended version of a recent work
\cite{Ger-et-al:ICAPS03}, we present some major improvements that were
used in the 3rd IPC to handle domains specified in the recent {\sc
pddl\small 2.1} language supporting ``durative actions'' and numerical
quantities \cite{FoxLon03:JAIR}.

The general search scheme of our planner is {\small \sf Walk-plan}, a
stochastic local search procedure similar to the well-known {\small
\sf Walk-sat} \cite{SelKauCoh94}. Two of the most important extensions
on which we focus in this paper concern the use of {\em temporal
action graphs} (TA-graphs), instead of simple A-graphs, and some new
techniques to guide the local search process.  In a TA-graph, action
nodes are marked with temporal values estimating the earliest time
when the corresponding action terminates, while fact nodes are
marked with temporal values estimating the earliest time when the
corresponding fact becomes true.  A set of ordering constraints is
maintained during search to handle mutually exclusive actions, and to
represent the temporal constraints implicit in the ``causal'' relations 
between actions in the current plan.

The new heuristics exploit some reachability information to weigh the
elements (TA-graphs) in the search neighborhood that resolve an
inconsistency selected from the current TA-graph.  The evaluation of
these TA-graphs is based on the estimated number of search steps
required to reach a solution (a valid plan), its estimated makespan,
and its estimated execution cost.
{\sc lpg} is an incremental planner, in the sense that it produces a
sequence of valid plans each of which improves the quality of the
previous ones. Plan quality is modeled by execution and temporal 
costs in a flexible way (the user can determine the relative importance 
of the plan quality criteria).

In the 3rd IPC, our planner demonstrated excellent performance on a large
set of test problems in terms of both speed to compute the first
solution and quality of the best solution computed by the incremental
process.  {\sc lpg} was the fully-automated planner that solved the
greatest number of problems, and the one with the highest success ratio
between attempted problems and solved problems.

The paper is organized as follows. Section 2 presents the action and
plan representation used in the competition version of {\sc lpg}.
Section 3 describes {\sc lpg}'s local search neighborhood, some new
heuristics for temporal action graphs, and the techniques for
computing the reachability and temporal information used in these
heuristics. Moreover, in this section we describe how {\sc lpg}
handles numerical variables and the incremental process to produce
good quality plans.
Section 4 presents the results of an experimental analysis
using the test problems of the 3rd IPC, and illustrating the
efficiency of our approach especially for temporal planning. Section 5
gives conclusions, and mentions current and future work. Finally, 
a collection of appendices describes {\sc lpg}'s algorithm for computing 
the mutual exclusion relations used during search, and gives details 
about some of the experimental results presented in Section 4.

\section{Action and Plan Representation}

In this section we introduce our graph-based representations for 
{\sc strips} and temporal plans, which can be seen as an elaboration 
of planning graphs \cite{BluFur95}.  


\subsection{Planning Graphs and Actions Graphs}

A planning graph is a directed acyclic levelled graph with two kinds
of nodes and three kinds of edges.  The levels alternate between a
fact level, containing fact nodes, and an action level containing
action nodes.  An action node at a level $t$ represents an action
(instantiated operator) that can be planned at time step $t$.  A fact
node at a level $t$ represents a proposition corresponding to a
precondition of one or more actions at time step $t$, or to an effect
of one or more actions at time step $t-1$.  The fact nodes of level
$1$ represent the positive facts of the initial state of the planning
problem (every fact that is not mentioned in the initial state is
considered false).

In the following, we indicate with [$u$] the proposition (action) 
represented by the fact node (action node) $u$.
The edges in a planning graph connect action nodes and fact nodes. In
particular, an action node $a$ at a level $i$ is connected by:
{\it precondition edges} from the fact nodes of level $i$
representing the preconditions of [$a$];
{\it add-edges} to the fact nodes  of level $i+1$
representing the positive effects of [$a$];
{\it delete-edges} to the fact nodes of level $i+1$
representing the negative effects of [$a$].
Each fact node $f$ at a level $l$ is associated with a {\em no-op}
action node at the same level, which represents a dummy action having
$[f]$ as its only precondition and effect. 

Two action nodes $a$ and $b$ are marked as mutually exclusive in the
graph when one of the actions deletes a precondition of the other
({\em interference}) or an add-effect of the other ({\em inconsistent
effects}), or when a precondition node of $a$ and a precondition node
of $b$ are marked as mutually exclusive ({\em competing needs}).

Two proposition nodes $p$ and $q$ in a proposition level are marked as
exclusive if all ways of making proposition [$p$] true are exclusive
with all ways of making [$q$] true (each action node $a$ having an
add-edge to $p$ is marked as exclusive with each action node $b$ having
an add-edge to $q$).  When two fact or action nodes are marked as mutually
exclusive, we say that there is a {\em mutex} relation (or simply a mutex) 
between them.

Given a planning problem $\Pi$, the corresponding planning graph $\cal
G$ can be incrementally constructed level by level starting from level
1 using a polynomial algorithm \cite{BluFur95}. The graph construction 
should reach a propositional level where the goal nodes are present, 
and there is no mutex relation between them.\footnote{
   In some cases, when the problem is not solvable, the algorithm 
   identifies that there is no level satisfying these conditions, 
  and hence it detects that the problem is unsolvable.}
The {\em fixed-point level} of the graph is the level from which 
the nodes and mutex relations at every subsequent level remain the same.
Blum and Furst refer to this level as the level where the
graph has ``leveled off''.  The mutex relations in the planning graph
monotonically decrease with the increase of the levels: a mutex
relation holding at a certain level may not hold at the next levels,
but it is guaranteed that it holds at all previous levels containing
the fact/action nodes involved in the relation. The mutex relations at
the fixed-point level of the graph are called {\em persistent mutex}
relations \cite{FoxLon00}, because they hold at every level of the
graph.

Without loss of generality, we can assume that the goal nodes
of the last level represent the preconditions of the special action 
$[a_{end}]$, which is the last action in any valid plan, while
the fact nodes of the first level represent the effects of the special
action $[a_{start}]$, which is the first action in any valid plan.

Our approach to planning uses particular subgraphs of  $\cal G$,
called {\em action graphs}, which represent partial plans.

\vspace{-0.3cm}
\begin{definition}
An {\bf action graph} (A-graph) for $\cal G$ is a subgraph $\cal A$ of
$\cal G$ containing $a_{start}$ and $a_{end}$, and such that, if $a$
is an action node of $\cal G$ in $\cal A$, then also the fact nodes of
$\cal G$ corresponding to the preconditions and positive effects of
[$a$] are in $\cal A$, together with the edges connecting them to $a$.
\end{definition}

Notice that an action graph can represent an invalid plan for the
problem under consideration, since it may contain some {\em inconsistencies}, 
i.e., an action with precondition nodes that are not {\em supported}, 
or a pair of action nodes involved in a mutex relation.  
In general, a precondition node $q$ at a level $i$ is supported in an action
graph ${\cal A}$ of ${\cal G}$ if either (i) in ${\cal A}$ there
is an action node at level $i-1$ representing an action with
(positive) effect [$q$], or (ii) $i=1$ (i.e., [$q$] is a proposition
of the initial state). 
An action graph without inconsistencies represents a valid 
plan and is called a {\em solution graph}.

\begin{definition}
A {\bf solution graph} for $\cal G$ is an action graph ${\cal A}_s$ of
$\cal G$ such that all precondition nodes of the actions in ${\cal A}_s$ 
are supported, and there is no mutex relation between action nodes
of ${\cal A}_s$.
\end{definition}

For large planning problems the construction of the planning graph can
be computationally very expensive, especially because of the high
number of mutex relations. For this reason our planner considers only
pairs of actions that are persistently mutex, derived using a dedicated 
algorithm given in Appendix A.
An experimental comparison with {\sc ipp}'s implementation of the
planning graph construction \cite{Koe-et-al97-TechRep} showed that in practice
our method for deriving mutex relations is considerably more efficient
than the ``traditional'' method for deriving the mutex relations in
the fixed-point level of the graph. Moreover, for the problems that we tested,
our method derived all the persistent mutex relations found by the traditional 
method. 
%

The definition of action graphs and the notion of supported facts can
be made stronger by observing that the effects of an action node can
be automatically propagated to the next levels of the graph through
the corresponding no-ops, until there is an interfering action {\em
blocking} the propagation (if any), or the last level of the graph has
been reached. The use of the no-op propagation, that we presented in
previous work \cite{GerSerAIPS02}, leads to a smaller search space and
can be incorporated into the definition of action graph.

\begin{definition}
An {\bf action graph with propagation} is an action graph $\cal A$
such that if $a$ is an action node of $\cal A$ at a level $l$, then, for
any positive effect $[e]$ of $[a]$ and any level $l' > l$ of $\cal A$,
the no-op of $e$ at level $l'$ is in $\cal A$, unless there is another
action node at a level $l''$ ($l \leq l'' < l'$) which is mutex
with the no-op.
\end{definition}

Since in the rest of this paper we consider only action graphs with 
propagation, we will abbreviate their name simply to action 
graphs (leaving implicit that they include the no-op propagation).

In most of the existing planners based on planning graphs,
when the search for a solution graph fails, $\cal G$ is iteratively
expanded by adding an extra level and performing a new search using
the resulting graph. In systematic planners like {\sc graphplan}
\cite{BluFur95}, {\sc stan} \cite{FoxLon98b} and {\sc ipp} 
\cite{Koe-et-al97-TechRep} 
the search fails when there exists no solution graph, while in
planners that use local search like {\sc blackbox} \cite{KauSel99b} or 
{\sc gpg} \cite{GerSer99} the search fails when a certain search limit is
exceeded. As we will show, in {\sc lpg} there is no need to explicitly
treat this kind of search failure, since the size of the graph is
incrementally increased during search (i.e., the graph extension can be
part of a local search step).

\subsection{Linear and Temporal Action Graphs}
\label{sec:TA-graphs}
The first version of {\sc lpg} \cite{GerSerAIPS02} was based on action
graphs where each level may contain an arbitrary number of action
nodes, as in the usual definition of planning graph. The
version of the system that participated in the 3rd IPC uses a
restricted class of action graphs, called {\em linear action graphs},
combined with some additional data structures supporting a more 
expressive action and plan representation. 
In particular, the new system can handle actions
having temporal durations and preconditions/effects involving numerical
quantities, as specified in {\sc pddl\small 2.1} \cite{FoxLon03:JAIR}.
In this paper we focus mainly on planning for temporal domains, 
where {\sc lpg} showed particularly good performance with respect 
to the other (fully-automated) participants of the 3rd IPC. 


In order to keep the presentation simple, we describe our techniques
considering mainly preconditions of type ``{\tt over\,all}'' (i.e.,
preconditions that must hold during the whole action execution) and
effects of type ``{\tt at\,end}'' (i.e., effects that hold at the 
end of the action execution).%
\footnote{ 
  {\sc lpg} supports all types of preconditions and effects that can be 
  expressed in {\sc pddl2.1} (levels 1--3).}
In Section \ref{sec:ordering-time} we discuss how we handle the other 
types of preconditions and effects in the test domains of the 3rd IPC.

\begin{definition}
A {\bf linear action graph} \it (LA-graph) of $\cal G$ is an A-graph
of $\cal G$ in which each level of actions contains at most one action 
node representing a domain action and any number of no-ops.
\end{definition}


It is important to note that having only one action in each level of 
an LA-graph does not prevent the generation of parallel (partially
ordered) plans. 
In fact, from any LA-graph we can easily extract a partially ordered
plan where the ordering constraints are (1) those between mutex
actions and (2) those implicit in the causal structure of the
represented plan. Regarding the first constraints, if $a$ and $b$ are
mutex and the level of $a$ precedes the level of $b$, then $[a]$ is
ordered before $[b]$; regarding the second constraints, if $a$ has an
effect node that is used (possibly through the no-ops) to support a
precondition node of $b$, then $[a]$ is ordered before $[b]$.
These causal relations between actions producing an
effect and actions consuming it are similar to the causal links in
partial-order planning \cite<e.g.,>{McAllester91,PenWel92,Kambha-ijcai01}.  
{\sc lpg} keeps track of these relationships during search and uses
them to derive some heuristic information useful for guiding the
search (more details on this in the next section), as well as to
extract parallel plans from the solution graph. 

For temporal domains where actions have durations and plan
quality mainly depends on the makespan, rather than on the number of 
actions or graph levels, the distinction between one action or more 
actions per level is scarcely relevant. The order of the graph levels 
should not imply any ordering of the actions (e.g., an action 
at a certain level could terminate before the end of an action at the next 
level).


Since in LA-graphs there is at most one action node for each level, and
every inconsistency is an unsupported precondition, the use of this
representation has some advantages over general A-graphs:
\begin{itemize}

\item LA-graphs can be represented by simpler data structures, which
allow one to manage the no-op propagation, the inconsistency
identification and selection, and the numerical effect propagation
more efficiently.

\item LA-graphs better support the computation of the heuristic and
reachability information used by the local search algorithm presented
in the next section. As we will see, for these techniques it is
important to derive a consistent and possibly complete description of the
state where any action in the current plan is applied. In an LA-graph,
we can efficiently derive these state descriptions by using the levels
of the graph as a total order of the actions in the current plan.

\item In numerical domains, if mutex actions can belong to the same
  level of the current action graph, it could be impossible
  to determine whether a numerical precondition of an action
  at a following level is satisfied.\footnote{
  For instance, suppose we have an A-graph with two mutex actions at 
  a level such that one action sets the value of the numerical 
  variable $x$ to 10, while the other sets it to 20. Unless we order these 
  actions, it is impossible to determine whether   
  $x > 15$ holds when the action at the next level is applied.
}
In an LA-graph (persistent) mutex actions belong to different levels
and are ordered, making this easy to determine.
\end{itemize}

Also note that the fact of having only one action per level allows us to 
define a larger search neighborhood. 
In general, a disadvantage of LA-graphs with respect to A-graphs is
the size of the representation, since the number of levels in an
LA-graph can be significantly larger than the number of levels in the
corresponding A-graph. However, in all planning problems that we
tested, the size of LA-graphs was never a problem for our planner.\footnote{
  {\sc lpg}'s implementation of LA-graphs uses an extended version of
  Hoffmann's ``connectivity graph'', a compact representation of the
  action and fact nodes in a planning graph \cite{HofNeb-JAIR01}.
  The extensions are needed to represent persistent mutex relations, 
  durative actions and numerical preconditions/effects.  
}

For {\sc pddl\small 2.1} domains involving
durative actions, our planner represents temporal information by an
assignment of real values to the action and fact nodes of the
LA-graph, and by a set $\Omega$ of {\em ordering constraints} between
action nodes. The value associated with a fact node $f$ ($Time(f)$)
represents the earliest time when $[f]$ becomes true, given the
actions in the represented plan and the constraints in $\Omega$; the
value associated with an action node $a$ ($Time(a)$) represents the
earliest time when the execution of $[a]$ can terminate. These
temporal values are derived from the duration of the actions in the
LA-graph and the ordering constraints between them that are stated in
$\Omega$.

\begin{definition}
A {\bf temporal action graph} (TA-graph) of $\cal G$ is a triple 
$\langle {\cal A},{\cal T},{\Omega}\rangle$ where
\vspace{-0.1cm} 
\begin{itemize}
\item ${\cal A}$ is a linear action graph;
\vspace{-0.1cm} 
\item ${\cal T}$ is an assignment of real values to the fact and action nodes
      of ${\cal A}$;
\vspace{-0.1cm} 
\item ${\Omega}$ is a set of ordering constraints between action nodes of 
      ${\cal A}$.
\end{itemize}
\end{definition}

\begin{figure}[t]
%
\begin{center}
\psfrag{INIT}{\Large $INIT$}
\psfrag{a1}{\huge $a_1$}
\psfrag{a2}{\huge $a_2$}
\psfrag{a3}{\huge $a_3$}
\psfrag{a4}{\huge $a_4$}
\psfrag{f1}{\huge $f_1$}
\psfrag{f2}{\huge $f_2$}
\psfrag{f3}{\huge $f_3$}
\psfrag{f4}{\huge $f_4$}
\psfrag{f5}{\huge $f_5$}
\psfrag{f6}{\huge $f_6$}
\psfrag{f7}{\huge $f_7$}
\psfrag{f8}{\huge $f_8$}
\psfrag{f9}{\huge $f_9$}
\psfrag{f10}{\huge $f_{10}$}
\psfrag{f11}{\huge $f_{11}$}
\psfrag{f12}{\huge $f_{12}$}
\psfrag{f13}{\huge $f_{13}$}
\includegraphics[angle=0,width=.85\textwidth]{./examples-jair/lin-temp-pg-o.eps}
\vspace{-5mm}
\[{\Omega}=\{ a_1\prec_C a_4 ; \; a_2\prec_C a_3;       %% CAUSAL CONSTRAINTS
           \; a_1\prec_E a_2 ; a_2\prec_E a_3 ; a_2 \prec_E a_4 \}\]  %% MUTEX CONSTRAINTS
\end{center}   
\caption{\label{fig:TA-graph}
%
An example of TA-graph. Dashed edges form chains of no-ops that are
blocked by mutex actions. Round brackets contain temporal values
assigned by ${\cal T}$ to the fact nodes (circles) and the action nodes
(squares). The numbers in square brackets represent the durations of the
actions. ``(--)'' indicates that the corresponding fact node is not supported.
%
}
\end{figure}

The ordering constraints in a TA-graph are of two types: constraints
between actions that are implicitly ordered by the causal structure of
the plan ({\em $\prec_C$-constraints}), and constraints that are
imposed by the planner to deal with mutually exclusive actions 
({\em $\prec_E$-constraints}).  $a \prec_C b$ belongs to $\Omega$ if 
and only if $a$ is used to achieve a precondition node of $b$ in $\cal A$,  
while $a \prec_E b$ (or $b \prec_E a$)  belongs to $\Omega$ only if $a$ and $b$
are mutually exclusive in $\cal A$  ($a \prec_E b$, if the level of $a$
precedes the level of $b$, $b \prec_E a$ otherwise).  In Section
\ref{sec:ordering-time} we will discuss how ordering constraints are
introduced by {\sc lpg} during the search.  Given our assumption on the
types of action preconditions and effects in temporal domains, an
ordering constraint $a \prec b$ (where ``$\prec$'' stands for
$\prec_C$ or $\prec_E$) states that the end of $[a]$ is before the
start of $[b]$.
The temporal value assigned by $\cal T$ to a node $x$, denoted
by $Time(x)$, is derived as follows. If a fact node $f$ of the
action graph is unsupported, then $Time(f)$ is undefined, otherwise it
is the minimum value over the temporal values assigned to the actions
supporting it.  If the temporal value of every precondition node of
an action node $a$ is undefined, and there is no action node with a
temporal value that must precede $a$ according to $\Omega$, then
$Time(a)$ is set to the duration of $a$; otherwise
$Time(a)$ is the sum of the duration of $a$ and the maximum value over the 
temporal values of its precondition nodes and the temporal values of 
the action nodes that must precede $a$.   

Figure \ref{fig:TA-graph} gives an example of a TA-graph containing four
action nodes ($a_{1...4}$) and several fact nodes representing thirteen
facts. Since $a_1$ supports a precondition node of $a_4$, $a_1 \prec_C a_4$ 
belongs to $\Omega$ (similarly for $a_2 \prec_C a_3$). 
$a_1 \prec_E a_2$ also belongs to $\Omega$ because $a_1$ and $a_2$ are 
persistently mutex (similarly for $a_2 \prec_E a_3$ and $a_2 \prec_E a_4$).
The temporal value assigned to the facts $f_{1...5}$ at the first level 
is zero, because they belong to the initial state. $a_1$ has all its 
preconditions supported at time zero, and hence $Time(a_1)$ is the 
duration of $a_1$.
Since $a_1 \prec a_2 \in \Omega$, $Time(a_2)$ is given by the sum of 
the duration of $a_2$ and the maximum value over the temporal values of its 
precondition nodes (zero) and $Time(a_1)$.
Since $f_9$ at level 3 is supported only by $a_2$, and this is the
only supported precondition node of $a_3$, $Time(a_3)$ is the sum of
$Time(a_2) = Time(f_9)$ and the duration of $a_3$. Since $a_2$ must
precede $a_4$ (but there is no ordering constraint between $a_3$ and
$a_4$), $Time(a_4)$ is the maximum value over $Time(a_2)$ and the temporal
values of its supported precondition nodes ($f_6$), plus the duration
of $a_4$.  Finally, note that $f_{12}$ at the last level is supported
both by $a_4$ and $a_3$.  Since $Time(a_3) > Time(a_4)$, we have that
$Time(f_{12})$ at this level is equal to $Time(a_4)$.

\begin{definition}
A {\bf temporal solution graph} for $\cal G$ is a TA-graph $\langle
{\cal A},{\cal T},{\Omega}\rangle$ such that ${\cal A}$ is a
solution LA-graph of $\cal G$, ${\cal T}$ is consistent with
${\Omega}$ and the duration of the actions in ${\cal A}$, ${\Omega}$
is consistent, and for each pair $\langle a,b \rangle$ of mutex
actions in ${\cal A}$, either ${\Omega} \models a \prec b$ or
${\Omega} \models b \prec a$.
\end{definition}

While obviously the levels in a TA-graph do not correspond to real
time values, they represent a topological order for the
$\prec_C$-constraints in the TA-graph (i.e., the actions of the TA-graph
that are ordered according to their relative levels form a linear plan 
satisfying all $\prec_C$-constraints). 
This topological sort can be a valid total order for the 
$\prec_E$-constraints of the TA-graph as well, provided that these 
constraints are appropriately stated during search, i.e., that if $a$ 
and $b$ are exclusive, the planner appropriately imposes either 
$a \prec_E b$ or $b \prec_E a$.  {\sc lpg} chooses $a \prec_E b$ 
if the level of $a$ precedes the level of $b$,  $b \prec_E a$ otherwise.
Under this assumption on the ``direction'' in which $\prec_E$-constraints
are imposed, it is easy to see that the levels of a TA-graph correspond 
to a topological order of the actions in the represented plan satisfying 
every ordering constraint in $\Omega$.

For planning domains that require minimizing the plan makespan 
(like the ``Time'', ``SimpleTime'', ``Complex'', and some of the 
``Numeric'' and ``HardNumeric'' domain sets of the 3rd IPC) each element 
of {\sc lpg}'s search space is a TA-graph. For domains where time
is irrelevant (like the ``Strips'' and ``Numeric'' domain sets of the 
3rd IPC) the search space is formed by LA-graphs.\footnote{
  An experimental analysis showed that in {\sc strips} domains the 
  techniques for LA-graphs are more powerful than the techniques for 
  A-graphs that we proposed in previous work \cite{GerSerAIPS02}.
}



\subsection{Action Durations and Costs}

In this section we comment on the representation of action durations
and action costs in {\sc lpg}.  In accordance with {\sc pddl\small
2.1}, our planner handles both static durations and dynamic durations,
i.e., durations depending on the state in which the action is
applied. Static durations are either explicitly given as numbers
specified in the field ``{\tt :duration}'' of the operator
description, or they are implicitly specified by an expression
involving some static quantities specified in the initial state of the
planning problem. An example of implicit static duration is the
duration of the {\tt Drive} actions in the {\tt Depots-Time} domain of
the 3rd IPC: the {\tt Drive} operator defines the duration as the
distance between the source and the destination of travel (two
operator parameters instantiated by values specified in the initial
state), divided by the speed of the vehicle that is driven (another
operator parameter).

Typically, dynamic durations depend on some numeric quantities that
may vary from one state to another state reached by the actions 
in the plan. An example is the energy of a rover in the domain 
{\tt Rovers-Time} of the 3rd IPC, where the duration specified in 
the {\tt recharge} operator is 

 {\tt (/ (- 80 (energy ?x)) (recharge-rate ?x)))}.


\noindent
This expression depends on the current value of {\tt energy} for 
the rover {\tt ?x} and on its static recharging rate 
({\tt recharge-rate}) specified in the initial state.
Our planner handles the dynamic duration of an action by computing 
and maintaining during search an estimate of the value of the numerical 
quantities in the state where the action is applied.  
%
In Section \ref{sec:numerical-vars} we will briefly describe how
the version of {\sc lpg} that took part in the 3rd IPC handles
numerical state variables, and numerical preconditions and effects
involving them. 
However, in this paper we will not describe their treatment in detail,
and in the next section we will assume that action durations are
static.

Each action of a plan can be associated with a cost that
may affect the plan quality. Like action durations, in general these
costs could be either static or dynamic, though the current version of
{\sc lpg} handles only static ones. {\sc lpg} precomputes the action
costs using the plan metric specified in the
problem description using the {\sc pddl\small 2.1} field 
``{\tt :metric}''.\footnote{
  As in the domains of the competitions, we assume that the plan metric
  expression is linear.
  For simple {\sc strips} domains, where there is no metric
  expression to minimize, the cost of each action is set to one,
  and {\sc lpg} minimizes the number of actions in the plan.}
For instance, the plan metric used for a problem in the 
{\tt ZenoTravel-Numeric} domain of the 3rd IPC is

%
{\tt (:metric minimize (+ (* 4 (total-time)) (* 5 (total-fuel-used))))},
%

\noindent
i.e., it is the sum of four times the plan makespan and five times the
total amount of the fuel used by the actions in the plan.  
%
The cost of an action $a$ is derived by evaluating how the value of
the plan metric expression is changed by the effects of $a$. {\sc lpg}
computes an initial value $m_0$ for the expression by using the values 
specified in the initial state as values of the involved numerical variables.
 From $m_0$ {\sc lpg} derives a new value $m_1$
by applying the effects of $a$ that increase/decrease the value of one 
or more variables in the expression. The cost of $a$ is defined as 
$m_1 - m_0$. If this difference is zero, in order to prefer plans
containing a lower number of actions, the cost of $a$ is set to a
small positive quantity.
%
Notice also that in these evaluations of the metric expression the temporal
value {\tt total-time} is not considered (it is set to zero, if
present), because the temporal aspect of the plan quality is already
taken into account by the durations of the actions. In the previous example,
the metric subexpression used to derive the action costs is {\tt (* 5
(total-fuel-used)))}. Thus, for instance, the cost of the {\tt
ZenoTravel} action {\tt (fly plane1 city0 city1)} in the problem {\tt
pfile1} of the 3rd IPC is 13560 because the effects of this action
increase {\tt total-fuel-used} by the following quantity

%
{\tt (* (distance city0 city1) (slow-burn plane1)))} = 678 * 4 = 2712,
%

\noindent
which increases the metric value of the plan by 5 * 2712 = 13560.


\section{Local Search in the Space of Temporal Action Graphs}
\label{sec:search}

In this section we present some search techniques used in {\sc lpg}.
We start with a description of the general local search scheme in the
space of action graphs.  Then we concentrate on temporal action graphs
giving a detailed description of {\sc lpg}'s heuristics and of its
methods for computing and using reachability information, for
maintaining the TA-graph representation during search, and for
deriving good quality plans incrementally.  In order to simplify the
notation, instead of using $a$ and $[a]$ to indicate an action node
and the action represented by this node respectively, we will use $a$
to indicate both of them (the appropriate interpretation will be clear
from the context).

\subsection{Basic Search Procedure: Walkplan}
\label{sec:walkplan}
Given a planning graph $\cal G$, the local search process of {\sc lpg} 
starts from an initial A-graph of $\cal G$ (i.e., a partial plan), and
transforms it into a solution graph (i.e., a valid plan) through the
iterative application of graph modifications improving the
current partial plan. The two basic modifications consist of an
extension of the A-graph to include a new action node, or a reduction
of the A-graph to remove an action node (and the relevant
edges).\footnote{
  Another possible modification that is analyzed by Gerevini and
  Serina \citeyear{GerSerAIPS02}, 
  but that will not be considered in this paper, is action ordering, i.e.,  
  moving forward or backward one of two exclusive action nodes.}
At any step of the search process, which produces a new A-graph, the
set of actions that can be added or removed is determined by the 
inconsistencies that are present in the current A-graph.

The general scheme for searching for a solution graph (a final state of
the search) consists of two main steps. The first step is an
initialization of the search in which we construct an initial
A-graph. The second step is a local search process in the space of all
A-graphs, starting from the initial A-graph.  We can generate an
initial A-graph in several ways. Four possibilities that can be
performed in polynomial time, and that we have implemented are: an
empty A-graph (i.e., containing only the no-ops of the facts in the
initial state, and the special action nodes $a_{start}$ and
$a_{end}$); a randomly generated A-graph; an A-graph where all
precondition facts are supported, but in which there may be some
violated mutex relations; and an A-graph obtained from an existing
plan given as input to the process.
The last option is particularly useful in the plan optimization
phase, as well as for solving plan adaptation problems 
\cite{GerSer-aips00}. %
In the current version of {\sc lpg}, the default initialization 
strategy is the empty action graph with the fixed-point level as the
last level of the graph.
Further details on the initialization step can be found in earlier
papers on planning through local search and action graphs
\cite{GerSer99,GerSer-aips00}.

%
Once we have computed an initial A-graph, each basic search step
selects an inconsistency in the current A-graph.
If this is an unsupported fact node, then in order to resolve
(eliminate) it, we can either add an action node that supports it, or
we can remove an action node that is connected to that fact node by a
precondition edge.  If the chosen inconsistency is a mutex
relation, then we can remove one of the action nodes of the mutex
relation.  Note that the elimination of an action node can remove
several inconsistencies (e.g., all those corresponding to the
unsupported preconditions of the action removed).
On the other hand, obviously the addition of an action node can 
introduce several new inconsistencies.
The strategy for selecting the next inconsistency to handle
may have a significant impact on the overall performance 
\cite<this has
been extensively studied in the context of causal-link partial-order
planning, e.g.,>{PolJosPao97,GerSch96a}. Our planner includes
several strategies that we are currently testing. The default strategy
that we used in the 3rd IPC and in all experiments presented in 
Section \ref{sec:experiments}, prefers inconsistencies appearing at the
earliest level of the graph.

Given an action graph $\cal A$ and an inconsistency $\sigma$ in $\cal A$,
the {\it neighborhood} $N(\sigma,{\cal A})$ of $\sigma$ in $\cal A$ is 
the set of A-graphs obtained from $\cal A$ by applying a graph
modification that resolves $\sigma$.
At each step of the local search scheme, the elements of the
neighborhood are evaluated according to a function estimating their
quality, and an element with the best quality is then chosen as the
next possible A-graph (search state).
The quality of an A-graph depends on a number of factors, such as the
number of inconsistencies and the estimated number of search steps
required to resolve them, the overall cost of the
actions in the represented plan and its makespan.\footnote{ 
  For simple {\sc strips} domains the execution cost of the plan is 
  measured in terms of the number of actions (i.e., each action has 
  cost 1), while plan makespan is ignored. Alternatively it can be 
  modeled as the number of parallel time steps \cite{GerSerAIPS02}.}

\begin{figure}[t]
{\sf Walkplan}$(\Pi,max\_steps,max\_restarts,p)$
\begin{description}
\vspace*{-.2cm}
\item 
\emph{Input}: A planning problem $\Pi$, the maximum number of search steps
$max\_steps$,

\vspace{-0.15cm}
\hspace{0.35cm} the maximum number of search restarts $max\_restarts$, 
a noise factor $p$ ($0 \leq p \leq 1$).
\vspace*{-.75cm}
\item 
\emph{Output}: A solution graph representing a plan solving $\Pi$ 
or {\tt fail}. 
\end{description}
%

\begin{tabbing}
1.~ \textbf{for} \= $i\assign1$ { $to$} $max\_restarts$ \textbf{do} \\
2.    \> $\Act \assign$ an initial A-graph derived from the planning graph 
          of $\Pi$;\\
3. \>  \textbf{for} \= $j\assign1$ \textbf{to} $max\_steps$ \textbf{do} \\
4. \>    \>  \textbf{if} \= $\Act$ is a solution graph \textbf{then} \\
5. \>    \>   \>         \textbf{return} $\Act$   \\
6. \>    \> $\sigma \assign$ an inconsistency in $\Act$;\\
7. \>    \> $N(\sigma, \Act ) \assign$ neighborhood of $\Act$ for $\sigma$;\\
8. \>    \>  \textbf{if} \= $\exists\, {\cal A'}  \in N(\sigma, \Act )$ such 
               that the quality of ${\cal A'}$ is not worse than the 
               quality of ${\cal A}$ \\
9. \>  \>  \>  \textbf{then} $\Act \assign {\cal A'}$
                 (if there is more than one ${\cal A'}$-graph, 
                 choose randomly one)\\
10.\>  \>   \textbf{else} \=  \textbf{if}  {\tt random} $<$ $p$ \textbf{then}  \\
11. \>    \> \>   $\Act \assign$ an element of $N(\sigma, \Act )$ randomly chosen\\
12. \> \> \>  \textbf{else}  $ \Act \assign$ best element in $N(\sigma, \Act )$; \\

13. \textbf{return} {\tt fail}.
\end{tabbing}
\caption{\label{fig:walkplan}
General scheme of {\sf Walkplan} with restarts. {\tt random} is a randomly 
chosen value between 0 and 1. The quality of an action graph in the 
neighborhood is measured using an evaluation function estimating
the cost of the graph modification used to generate it from the current
action graph.}
\end{figure}

Gerevini and Serina \citeyear{GerSer99} proposed three general
strategies for guiding the local search: {\sf Walkplan}, {\sf
Tabuplan} and {\sf T-Walkplan}.  In this paper we focus on {\sf
Walkplan}, which is the strategy used by {\sc lpg} in the 3rd IPC, as
well as in the experimental tests presented in Section
\ref{sec:experiments}.  {\sf Walkplan} is similar to {\sf Walksat}, a
stochastic local search method for solving propositional
satisfiability problems \cite{SelKauCoh94,KauSel96}.  In {\sf
Walkplan} the best element in the neighborhood is the A-graph which
has the {\em lowest decrease of quality} with respect to the current
A-graph, i.e., it does not consider possible improvements.  Like {\sf
Walksat}, our strategy uses a {\it noise parameter} $p$. Given an
A-graph $\cal A$ and an inconsistency $\sigma$, if there is a
modification for $\sigma$ that does not decrease the quality of $\cal
A$, then this modification is performed, and the resulting A-graph is
chosen as the next A-graph; otherwise, with probability $p$ one of the
graphs in $N(\sigma, \cal A)$ is chosen randomly, and with probability
$1-p$ the next A-graph is chosen according to the minimum value of the
evaluation function.  If a solution graph is not reached after a
certain number of search steps ({\em max\_steps}), the current A-graph
and {\em max\_steps} are reinitialized, and the search is repeated up
to a user-defined maximum number of times ({\em
max\_restarts}). Figure \ref{fig:walkplan} gives a formal description
of {\sf Walkplan} with restarts.

Gerevini and Serina \citeyear{GerSerAIPS02} proposed some heuristic
functions for evaluating the search neighborhood of A-graphs with
action costs. In the next section we present additional, more powerful
heuristic functions for LA-graphs and TA-graphs. These techniques are
implemented in the latest version of our planner and were used in the
3rd IPC.


\subsection{Neighborhood and Heuristics for Temporal Action Graphs}
\label{sec:neighborhood}

%%

The search neighborhood for an inconsistency $\sigma$ in an LA-graph
${\cal A}$ is the set of LA-graphs that can be derived from ${\cal A}$
by adding an action node supporting $\sigma$, or removing the action
with precondition $\sigma$ (in linear graphs the only
type of inconsistencies are unsupported preconditions).  An action
$a$ supporting $\sigma$ can be added to $\Act$ at any level $l$ preceding 
the level of $\sigma$, and such that the desired effect of $a$ is not
blocked before or at the level of $\sigma$ (assuming that the
underlying planning graph contains $a$ at level $l$).
The neighborhood for $\sigma$ contains a linear action graph for each of 
these possibilities.

%
Since at any level of an LA-graph there can be at most one action node
(plus any number of no-ops), when we remove an action node from $\cal A$, 
the corresponding action level becomes ``empty'' (i.e., it contains only no-ops).%
\footnote{Note that the empty levels are ignored during the extraction 
  of the plan from the (temporal) solution graph.}
If the LA-graph contains adjacent empty levels, and in order to resolve 
the selected inconsistency a certain action node can be added at any of 
these levels, then the corresponding neighborhood contains only one of 
the resulting graphs.

%
When we add an action node to a level $l$ that is not empty, the
LA-graph is extended by one level, all action nodes from $l$ are
shifted forward by one level, and the new action is inserted at level
$l$ (Figure \ref{fig:TA-graph-rev} in Section \ref{sec:ordering-time}
gives an example).
Moreover, when we remove an action node $a$ from the current LA-graph,
we can also remove each action node $b$ supporting only the
preconditions of $a$. Similarly, we can remove the actions
supporting only the preconditions of $b$, and so on.
While this induced pruning is not necessary, an experimental analysis 
showed that it tends to produce better quality plans more quickly.

The elements of the neighborhood are evaluated according to an {\em
action evaluation function} $E$ estimating the cost of adding 
($E(a)^i$) or removing an action node $a$ ($E(a)^r$). 
In general, $E$ consists of three weighed terms evaluating three 
aspects of the quality of the current plan that are affected by the 
addition/removal of $a$:

\[ E(a)= 
\left\{\begin{array}{ll}
E(a)^i =
\alpha \cdot Execution\_cost(a)^i + 
\beta \cdot Temporal\_cost(a)^i + \gamma \cdot Search\_cost(a)^i
\\
\\
E(a)^r =
\alpha \cdot Execution\_cost(a)^r + 
\beta  \cdot Temporal\_cost(a)^r  + \gamma \cdot Search\_cost(a)^r 
\end{array}
\right.
\]   

The first term of $E$ estimates the increase of the plan execution cost
($Execution\_cost$), the second estimates the end time of $a$ 
($Temporal\_cost$), and the third estimates the increase of the number 
of search steps needed to reach a solution graph ($Search\_cost$).
The coefficients of these terms are used to normalize them, and
to weigh their relative importance (more on this in Section 
\ref{sec:incremental-quality}).

In the computation of the terms of $E$ there is an important tradeoff
to consider. On one hand, an accurate evaluation of them could lead to
valid plans of good quality within few search steps. On the other
hand, the computation of $E$ should be fast ``enough'', because the
neighborhood could contain many elements, and an accurate evaluation
of its elements could slow down the search excessively.
%
In the design of our heuristics for evaluating the terms of $E$ 
we took this tradeoff into account trying to find an appropriate
balance between informativeness and efficiency of computation.

%
The evaluation of the terms of $E$ is based on computing 
particular relaxed plans for achieving certain action preconditions
in the context of the current TA-graph. In the next subsections, first 
we describe how these relaxed plans are derived, and then we give a
detailed description of how the terms of $E$ are defined using 
relaxed plans.

%
\subsubsection{Relaxed Plans for Action Preconditions}

%

\label{sec:Rplan}
%

Suppose we are evaluating the addition of $a$ at a level $l$ of the
current linear action graph $\Act$. The three terms of $E$ are heuristically
estimated by computing a relaxed plan $\pi_r$ containing a minimal set
of actions for achieving (1) the unsupported preconditions of $a$ and 
(2) the set $\Sigma$ of preconditions of the other actions in the LA-graph
that would become unsupported by adding $a$ (because it would block the 
no-op propagation currently used to support such preconditions). 
This plan is relaxed because during its construction we do not consider 
the possible interference between actions resulting from delete-effects. 

$\pi_r$ is computed in two stages. First we deal with the
preconditions of type (1) and then with the preconditions of type
(2). The generation of $\pi_r$ depends on the actions in the
current partial plan (the plan represented by $\Act$) in two ways:
\begin{itemize}
\item
The actions in the current plan are used to define an initial state for 
the problems of achieving the preconditions of $a$ and those in $\Sigma$.
In particular, the relaxed subplan for the preconditions of $a$ is 
computed from the state {\em INIT}$_l$ obtained by applying the actions 
in $\Act$ up to level $l-1$, ordered according to their corresponding 
levels.%
\footnote{Notice that, as we pointed out in the previous section, 
  the levels in a TA-graph correspond to a total order of the actions 
  of the represented partial-order plan that is consistent with the 
  ordering constraints in $\Omega$ (though, of course, this is not 
  necessarily the only valid total order).
}
 The relaxed subplan for achieving $\Sigma$ is computed from {\em INIT}$_l$
modified by the effects of $a$, and it can reuse the actions in the relaxed
subplan previously computed for the preconditions of $a$. 

\item
In the process of deriving a relaxed plan, when we choose
an action, we consider its potential interference with the no-ops that
support a precondition of some action in $\Act$ at a level following $l$,
and we prefer actions that do not block the propagation of such no-ops.
%
The motivation is that taking these interferences into account during
the construction of a relaxed plan can lead to a better estimate
of the cost required to support preconditions of type (1) and (2)
in the context of the search that we are conducting to transform
the current action graph into a solution graph (more details below).
\end{itemize}

We indicate with {\em Threats}$(a)$ the set of preconditions of the actions 
in $\Act$ that would become unsupported when adding $a$ (similarly for the
action preconditions that could be subverted by an action in the
relaxed plan).
%
Using the causal-link notation of partial-order planners 
\cite<e.g.,>{McAllester91,PenWel92}, {\em Threats}$(a)$ can be formally
defined in the following way

%
\begin{center}
{\em Threats}$(a) = \{ f \mid $ no-op$(f)$ and $a$ are mutex;
  $\exists \, b, c \in {\cal A}$ such that $b \stackrel{f}{\rightarrow} c\}$.
\end{center}
%

\noindent
Note that, according to our representation, $b \stackrel{f}{\rightarrow} c$
implies   $Level(b) <  Level(a) < Level(c)$, where $Level(x)$ denotes 
the level of $x$ in $\Act$. 

Figure \ref{alg:RelaxedPlan} gives a recursive algorithm for computing
our relaxed plans, {\sf RelaxedPlan}, which uses the following
additional notation.  $Duration(a)$ denotes the duration of
$a$;\footnote{
  If the duration of $a$ is dynamic (it depends on the
  value of one or more numerical variables), it is computed using the
  values of the numerical variables in {\em INIT}$_l$.
}
$Pre(a)$ denotes the precondition nodes of $a$; $Add(a)$ denotes the
(positive) effect nodes of $a$; $Supported\_facts(l)$ denotes the set
of positive facts that are true after executing the actions at levels
that precede $l$ (ordered according to their level); $Num\_acts(p,l)$
denotes an estimated minimum number of actions required to reach $p$
from $Supported\_facts(l)$ (if $p$ is not reachable, $Num\_acts(p,l)$
is a negative number).
%
The technique for computing $Num\_acts$ is described in Section 
\ref{sec:reachability}.
%


\begin{figure}[t]
%
{\sf RelaxedPlan}($G, INIT_l, A$)

\vspace{-0.2cm}
\begin{description}
\item
{\it Input}: A set of goal facts ($G$), the set of facts that are true after
executing the actions of the current TA-graph up to the level $l$ 
({\em INIT}$_l$), a possibly empty set of actions ($A$);

\vspace{-0.2cm}
\item
{\it Output}: A set of actions and a real number, estimating a minimal set 
of actions required to achieve $G$ and the earliest time when all facts 
in $G$ can be achieved, respectively.
\end{description}

%
\begin{tabbing}
1. ~~~\= $t \assign \stackdown{MAX}{g \in G \cap INIT_l} Time(g)$;
\\ 
2. \> $ G \assign G -INIT_l$; $ACTS \assign A$; 
\\
3. \>  $F \assign \bigcup_{a \in ACTS} Add(a)$; 
\\
4. \> $t \assign MAX \left\{t, \stackdown{MAX}{g \in G \cap F} 
            T(g) \right\}$; \\ 
%
5. \> {\bf while} $G - F \neq \emptyset$ 
\\
6. \> ~~~~\= $g \assign$ a fact in $G - F$; 
\\
7. \>\> $bestact \assign Bestaction(g)$;
\\
%
8. \>\> $Rplan \assign$ {\sf RelaxedPlan}($ Pre(bestact),INIT_l,ACTS$); \\
9. \>\> {\bf forall} $f \in Add(bestact) - F$\\
10. \>\> ~~~~~~~$T(f) \assign End\_time(Rplan)+Duration(bestact)$;\\
11. \>\> $ACTS \assign Aset(Rplan) \cup \{ bestact \}$;\\
12. \>\> $F \assign \bigcup_{a \in ACTS} Add(a)$; \\
13. \>\> \( t \assign MAX\{t,  End\_time(Rplan)+Duration(bestact)\}\);\\
14. \> {\bf return } $\langle ACTS, t \rangle$.
\end{tabbing}

%
\caption{\label{alg:RelaxedPlan}
Algorithm for computing a relaxed plan achieving a set of action 
preconditions from the state {\em INIT}$_l$. $Rplan$ is a pair
of values $\langle Aset(Rplan)$, $End\_time(Rplan) \rangle$, where
the first value is a set of actions and the second is a temporal quantity. 
$Bestaction(g)$ is the action that is heuristically chosen to support $g$ 
as described in the text.  
%
}
%
\end{figure}

Given a set $G$ of goal facts, an initial state {\em INIT}$_l$, and a
possibly empty set of actions $A$, {\sf RelaxedPlan} computes a pair
{\em Rplan} = $\langle ACTS, t \rangle$ where: $ACTS$ is a set of actions 
including $A$ and forming a relaxed plan achieving $G$ from {\em
INIT}$_l$; $t$ is a temporal value estimating the earliest time when all
facts in $G$ are achieved. The first element of {\em Rplan} is
indicated with $Aset(Rplan)$, the second with $End\_time(Rplan)$.

As mentioned above and described in detail in Section \ref{sec:E-terms},
when we evaluate the addition of an action $a$, {\sf RelaxedPlan} is
run twice: first to compute a relaxed plan for the preconditions of
$a$, and then to extend this plan for achieving the preconditions that
would be subverted by $a$ (i.e., {\em Threats}$(a)$).  The input set
$A$ is the set of actions currently in the relaxed plan that
can be ``reused'' to achieve an action precondition or goal of the
relaxed (sub)problem.
$A$ is not empty whenever {\sf RelaxedPlan} is recursively executed, 
and when it is run to achieve {\em Threats}$(a)$.


{\sf RelaxedPlan} constructs $Rplan$ through a backward process where
$Bestaction(g)$ is the action $a'$ chosen to achieve a (sub)goal $g$,
and such that: (i) $g$ is an effect of $a'$; (ii) all preconditions of
$a'$ are reachable from {\em INIT}$_l$; (iii) the reachability of the
preconditions of $a'$ requires a minimum number of actions, estimated
as the maximum of the heuristic minimum number of actions required to
support each precondition $p$ of $a'$ from {\em INIT}$_l$ (i.e., the
maximum of $Num\_acts(p,l)$ over each precondition $p$ of $a'$); (iv)
$a'$ subverts a minimum number of supported precondition nodes in
$\Act$ (i.e., the size of the set {\em Threats}$(a')$ is minimal).  More
formally,

\vspace{-0.2cm}
\[ Bestaction(g) = \,
\stackdown{ARGMIN}{\{a' \in A_{g}\}} 
       \left\{\stackdown{MAX}{p \in Pre(a') - F} Num\_acts(p,l) + |Threats(a')|
       \right\},
\]

\noindent
%
where $F$ is the set of positive effects of the actions currently in {\em
ACTS}, and $A_g$ is the set of actions with the effect $g$ and with reachable 
preconditions, i.e.,

\begin{center}
$A_g= \{ a \in {\cal O} \, | \,g\in Add(a)$, ${\cal O}$ is the
%
set of all actions, $\forall p \in Pre(a)$ $Num\_acts(p)\ge 0 \}$.% 
\footnote{
  \label{fn:mutex-preconds}
  In principle $A_g$ can be empty because $g$ might not be reachable
  from {\em INIT}$_l$ (i.e., $Bestaction(g) = \emptyset$). 
  {\sf RelaxedPlan} treats this special case by forcing its termination 
  and returning a set of actions including a special action with a very 
  high cost, leading $E$ to consider the element of the neighborhood 
  under evaluation a bad possible next search state. 
  For clarity we omit these details from the formal description of the 
  algorithm.}
\end{center}

%
\noindent
Notice that the set of actions ${\cal O}$ in the definition of $A_g$ 
does not contain operator instances with mutually exclusive preconditions.
The reason why $Bestaction(g)$ considers the cost of the preconditions in
$Pre(a') - F$, instead of in $Pre(a')$, is that the preconditions of
$a'$ that are in $F$ are already supported by other actions currently 
in the relaxed plan under construction.

Requirements (i) and (ii) for the definition of $Bestaction$ are
obvious. Regarding (iii) and (iv), we considered alternative versions
that are implemented in {\sc lpg}, but that are not used as default
strategies because we experimentally found that on average they lead
to a worse performance. In particular, instead of using the maximum of
the heuristic minimum number of actions required to support each
precondition $a'$, we tested the use of the {\em sum} of such numbers,
which can give an overestimation of the actual search cost.
We have also tested a version of $Bestaction$ which does not consider
(iv), i.e., without the term $|Threats(a')|$. While this simplified
version is faster to compute, overall the performance of the planner
was on average worse both in terms of CPU-time and quality of the
plans produced (detailed results of this experiment are
available from the web page of {\sc lpg}).

%
Steps 1, 4 and 13 of {\sf RelaxedPlan} estimate the earliest time
required to achieve all goals in $G$. This is recursively defined as
the maximum of 
\begin{itemize}
\item[(a)] the times assigned to the facts in $G$ that are already
  true in the state {\em INIT}$_l$ (step 1);
\item[(b)] the estimated
  earliest time $T(g)$ required to achieve every fact $g$ in $G$ that is
  an effect of an action currently in {\em ACTS} (step 4); 
\item[(c)] the estimated earliest time required to complete the execution 
  of the actions chosen by $Bestaction$ to achieve 
  each of the remaining facts in $G$ (step 13).
\end{itemize}

The $T$-times of (b) are computed by steps 9--10 from the relaxed
subplan derived to achieve them. Clearly the algorithm terminates,
because either every (sub)goal $p$ is reachable from {\em INIT}$_l$
(i.e., $Num\_acts(p,l) \geq 0$), or at some point $bestact =
\emptyset$ holds, forcing immediate termination (see footnote
\ref{fn:mutex-preconds}).  Moreover, it can be proved that the
complexity of the algorithm is polynomial in the number of actions and
facts in the planning problem/domain.


\subsubsection{An Example Illustrating {\sf RelaxedPlan}}

\label{sec:example-relaxedplan}


Suppose we are evaluating the addition of $a$ to the current TA-graph
$\Act$ illustrated in Figure \ref{fig:RelaxedPlan}. For each fact that is
used in the example, the tables of Figure \ref{fig:RelaxedPlan} give the
relative $Num\_acts$-value or the temporal value ($Num\_acts$ for the
unsupported facts, $Time$ for the other nodes). The $Num\_acts$-value
for a fact belonging to {\em INIT}$_l$ is zero.  The duration of the
actions used in the example are indicated in the corresponding table
of Figure \ref{fig:RelaxedPlan}.  
Solid circle and square nodes represent precondition and action nodes
in $\Act \cup \{a\}$; dotted circle and square nodes represent the
precondition and action nodes that are considered during the
evaluation process; finally, the gray circle and square nodes
represent the precondition and action nodes that are selected by 
{\sf RelaxedPlan}.

First we describe the derivation of the sets of actions in the relaxed plan
for $Pre(a)$ and {\em Threats}$(a)$, i.e., 

$S_1 = Aset({\sf RelaxedPlan}(Pre(a),INIT_l,\emptyset))$ and 

$S_2 = Aset({\sf RelaxedPlan}(Threats(a),INIT_l, S_1))$


\noindent
respectively.  Then we describe the derivation of the estimation of
the earliest time when all preconditions in $Pre(a)$ can be achieved,
i.e., 
$End\_time({\sf RelaxedPlan}(Pre(a),INIT_l,\emptyset))$.

\vspace{0.3cm}
\noindent
{\em Actions for $Pre(a)$ in the Relaxed Plan}
\vspace{0.1cm}

\noindent
$Pre(a)$ is $\{p_1,p_2,p_3\}$ but, since $p_2 \in$ {\em INIT}$_l$, in
the first execution of {\sf RelaxedPlan} step 2 removes $p_2$ from
$G$. So, only $p_1 $ and $p_3$ are the goals of the relaxed
problem. Suppose that in order to achieve $p_1$ we can use $a_1$,
$a_2$ or $a_3$ (forming the set $A_g$ examined by $Bestaction(p_1)$ 
in step 7). Each of these actions is evaluated, and $a_1$ is chosen.
In the recursive call of {\sf RelaxedPlan} applied to the preconditions 
of $a_1$, $p_5$ is not considered because it already belongs to {\em
INIT}$_l$. Regarding the other precondition of $a_1$ ($p_4$), suppose
that $a_4$ is the only action achieving it.  Then this action is
chosen to achieve $p_4$, and since its preconditions belong to {\em
INIT}$_l$, they are not evaluated (the new recursive call of {\sf
RelaxedPlan} returns an empty action set).


Regarding the precondition $p_3$ of $a$, assume that it can be
achieved only by $a_5$ and $a_6$. These actions have a common
precondition ($p_{12}$) that is an effect of $a_4$, an action
belonging to {\em ACTS} (because it was already selected by {\sf
RelaxedPlan}$(Pre(a_1),INIT_l,\emptyset)$).  The other preconditions
of these actions belong to {\em INIT}$_l$. Since $|Threats(a_5)| = 0$
and $|Threats(a_6)|= 1$, $Bestaction(p_3)$ is $a_5$.  Consequently,
$Aset({\sf RelaxedPlan}(Pre(a),INIT_l,\emptyset))$ is
$\{a_1,a_4,a_5\}$.

\begin{figure}[t]
\hspace{40mm}
\psfrag{INIT_l}{\Large {\em INIT$_l$}}
\psfrag{a}{\huge $a$}
\psfrag{b}{\huge $b$}
\psfrag{c}{\huge $c$}
\psfrag{a1}{\huge $a_1$}
\psfrag{a2}{\huge $a_2$}
\psfrag{a3}{\huge $a_3$}
\psfrag{a4}{\huge $a_4$}
\psfrag{a5}{\huge $a_5$}
\psfrag{a6}{\huge $a_6$}
\psfrag{a7}{\huge $a_7$}
\psfrag{a8}{\huge $a_8$}
\psfrag{p}{\Large $p$}
\psfrag{q}{\Large $q$}
\psfrag{q1}{\Large $r$}    
\psfrag{p1}{\Large $p_1$}
\psfrag{p2}{\Large $p_2$}
\psfrag{p3}{\Large $p_3$}
\psfrag{p4}{\Large $p_4$}
\psfrag{p5}{\Large $p_5$}
\psfrag{p6}{\Large $p_6$}
\psfrag{p7}{\Large $p_7$}
\psfrag{p8}{\Large $p_8$}
\psfrag{p9}{\Large $p_9$}
\psfrag{p10}{\Large $p_{10}$}
\psfrag{p11}{\Large $p_{11}$}
\psfrag{p12}{\Large $p_{12}$}
\psfrag{p13}{\Large $p_{13}$}
\psfrag{p14}{\Large $p_{14}$}
\psfrag{p15}{\Large $p_{15}$}
\psfrag{p16}{\Large $p_{16}$}
\psfrag{Level}{\Large Level $l+1$}
\includegraphics[angle=0,width=0.7\textwidth]{./examples-jair/es_relaxed_plan-A.eps}

\vspace{-98mm}
\footnotesize
\begin{tabular}{| c | c |}
\hline
Fact            & $ Num\_acts$ \\
\hline
$p_1$           & 2    \\
$p_3$           & 2    \\
$p_4$           & 1    \\
$p_6$           & 6    \\        
$p_8$           & 2    \\
$p_{12}$        & 1    \\
$p_{14}$        & 2    \\
$p_{15}$        & 2    \\
$p_{16}$        & 9    \\
\hline
\hline 
Fact            & $Time$ \\
\hline
$p_2$           & 220    \\
$p_5$           & 170    \\
$p_7$           & 300    \\
$p_9$           & 50    \\ 
$p_{10}$        & 30    \\
$p_{11}$        & 170    \\
$p_{13}$        & 30    \\
\hline
\hline
Action            & $Duration$ \\
\hline
$a$             & 30    \\
$a_1$           & 70    \\
$a_4$           & 100   \\
$a_5$           & 30    \\ 
$a_{7}$         & 90    \\
\hline 
\end{tabular}
\vspace{7mm}
\normalsize
\caption{ 
\label{fig:RelaxedPlan}
An example illustrating {\sf RelaxedPlan}.  Square nodes represent
action nodes, while the other nodes represent fact nodes; solid nodes
correspond to nodes in $\Act \cup \{a\}$; dotted nodes correspond to
the precondition and action nodes that are considered during the
evaluation process; the gray nodes are those selected by {\sf
RelaxedPlan}. }
\end{figure}

\vspace{0.3cm}
\noindent
{\em Actions for Threats$(a)$ in the Relaxed Plan }
\vspace{0.1cm}

\noindent
Concerning the execution of {\sf RelaxedPlan} for {\em Threats}$(a)$,
i.e., {\sf RelaxedPlan}$(\{q\},INIT_l,\{a_1,a_4,$ $a_5\})$,
suppose that the only actions for
achieving $q$ are $a_7$ and $a_8$. Since the precondition $p_{14}$ of
$a_7$ is an effect of $a_5$, which is an action in the input set $A$
(it belongs to the relaxed subplan computed for the preconditions of
$a$), and {\em Threats}$(a_7)$ is empty, the best action chosen by {\sf
RelaxedPlan} to support $q$ is $a_7$.  It follows that the set of
actions returned by {\sf RelaxedPlan} is $\{a_1,a_4,a_5,a_7\}$.

\vspace{0.3cm}
\noindent
{\em Temporal Value for $Pre(a)$}
\vspace{0.1cm}

We now consider the evaluation of the temporal value returned by {\sf
RelaxedPlan}$(Pre(a), \,$ {\em INIT}$_l,\emptyset)$.  According to the
temporal values specified in the table of Figure
\ref{fig:RelaxedPlan}, the value of $t$ at step 1 is $Time(p_2)=220$.
As illustrated above, {\sf RelaxedPlan} for $Pre(a)$ is recursively
executed to evaluate the preconditions of $a_1$ (the action chosen to
achieve $p_1$) and then of $a_4$ (the action chosen to achieve
$p_4$). In the evaluation of the preconditions of $a_4$, at step 1 of
{\sf RelaxedPlan}$(Pre(a_4), \,${\em INIT}$_l,\emptyset)$) $t$ is set
to 50, i.e., the maximum value between $Time(p_9)$ and $Time(p_{10})$ and
the algorithm returns $\langle \emptyset, 50 \rangle$.

In the evaluation of the preconditions of $a_1$, at step 1 of {\sf
RelaxedPlan}$(Pre(a_1),\,${\em INIT}$_l,\emptyset)$) $t$ is set to
$Time(p_5) = 170$, at step 8 {\sf RelaxedPlan}$(Pre(a_4), \,${\em
INIT}$_l,\emptyset)$) returns $\langle \emptyset, 50 \rangle$, while
steps 9--10 set $T(p_{12})$ to $50 + 100$ (the duration of $a_4$), and
at step 13 $t$ is set to $MAX\{170, 50+100\}$. Hence, the recursive
execution of {\sf RelaxedPlan} applied to the preconditions of $a_1$
returns $\langle \{a_4\}, 170 \rangle$, and at step 13 of {\sf
RelaxedPlan}$(Pre(a),INIT_l,\emptyset)$ $t$ is set to $MAX\{220,
170+70\}=240$.

As we have seen in the first part of the example, the action chosen
to support $p_3$ is $a_5$. The recursive execution of {\sf
RelaxedPlan}$(Pre(a_5), ${\em INIT}$_l,\{a_1, a_4\})$ applied to
the preconditions of $a_5$ returns $\langle \{a_1,a_4\}, 170 \rangle$.
In fact, the only precondition of $a_5$ that is not in {\em INIT}$_l$
($p_{12}$) is achieved by an action already in {\em ACTS} ($a_4$).
Moreover, since $T(p_{12}) = 150$ and $Time(p_{11}) = 170$, the
estimated end time of $a_5$ is $170+30 = 200$.  At step 13 of {\sf
RelaxedPlan}$(Pre(a), INIT_l, \emptyset)$ $t$ is then set to
$MAX\{240, 200\}$ and the output of {\sf RelaxedPlan} is $\langle
\{a_1, a_4, a_5\}, 240\rangle$.

\subsubsection{Estimating the terms of $E$}
\label{sec:E-terms}

As noted before, the terms of the action evaluation function $E$ are
computed by using the relaxed (sub)plan $\pi_r$ for a set of
preconditions.  The number of actions in $\pi_r$ and the threats 
of these actions are used to define a heuristic estimate of the
additional search cost that would be introduced by adding an action
$a$ to the current TA-graph, or removing it (i.e., the {\em
Search\_cost} terms of $E$).
Note that in general this is not an admissible heuristic, because
it can overestimate the minimum number of search steps needed to 
cope with the inconsistency under consideration.

The $Temporal\_cost$ term of $E(a)^i$ is an estimation of
the earliest time when the new action $a$ would terminate, given the
actions in $\pi_r$ and the earliest time when $\pi_r$ can be applied
in the context of the current action graph.\footnote{
 The makespan of $\pi_r$ is not a lower bound for
 $Temporal\_cost(a)$ because the possible parallelization of $\pi_r$
 with the actions already in $\Act$ is not considered.  
}
The $Temporal\_cost$ term of $E(a)^r$ is an estimation of the earliest
time when all preconditions that would become unsupported by removing
$a$ from the current action graph could be supported again.
 
The $Execution\_cost$ term of $E(a)^i$ is an estimation of the additional
execution cost that would be required to satisfy the preconditions of
$a$, and is derived by summing the cost of each action $a'$ in $\pi_r$ 
($Cost(a')$). The $Execution\_cost$ term of $E(a)^r$ is estimated similarly
by considering the preconditions of the actions that would become 
unsupported when removing $a$ from the current action graph.
More formally, $E$ is defined as follows:

\[
 E(a)^i
\left\{\begin{array}{l}
\vspace{0.2cm}
Execution\_cost(a)^i = \sum_{a' \in ~Aset({\sf EvalAdd}(a)) } Cost(a') \\
\vspace*{0.2cm}
 Temporal\_cost(a)^i = End\_time( {\sf EvalAdd}(a) )  \\
 Search\_cost(a)^i = | Aset({\sf EvalAdd}(a)) | + \sum_{a' \in Aset({\sf EvalAdd}(a))}   | Threats(a') |
 \end{array}
\right.
\]
\[
E(a)^r
\left\{\begin{array}{l}
\vspace*{0.2cm}
Execution\_cost(a)^r = \sum_{a' \in ~ Aset({\sf EvalDel}(a)) } Cost(a')  -Cost(a) \\
\vspace*{0.2cm}
Temporal\_cost(a)^r = End\_time( {\sf EvalDel}(a) ) \\
 Search\_cost(a)^r = | Aset({\sf EvalDel}(a)) | +  \sum_{a' \in Aset({\sf EvalDel}(a))}   | Threats(a') |
 \end{array}
\right.
\vspace*{0.2cm}
\]


\begin{figure}[t]
%
{\sf EvalAdd}($a$) %
\begin{description}
\vspace*{-.2cm}
\item
\emph{Input}: 
An action node $a$ that does not belong to the current TA-graph.
\vspace*{-.3cm}
\item 
{\it Output}: A pair formed by a set of actions and a temporal value $t$.
\end{description}
%

\begin{tabbing}
1. ~~~ \= $INIT_l \assign Supported\_facts(Level(a))$; \\
2. \> $Rplan \assign  {\sf RelaxedPlan}(Pre(a),  INIT_l, \emptyset)$; \\
3. \> $t_1 \assign MAX\{0,MAX \{ Time(a') \mid  {\Omega} \models a' \prec a\}\}$;\\
4. \> $t_2 \assign MAX\{t_1, End\_time(Rplan) \}$;\\
5. \> $A \assign Aset(Rplan) \cup \{ a \}$;\\
6. \> $Rplan \assign {\sf  RelaxedPlan}( Threats(a), INIT_l-Threats(a), A)$; \\
7. \>  {\bf return} $\langle Aset(Rplan), t_2+ Duration(a)\rangle$.\\
\end{tabbing}

\vspace{-0.2cm}

{\sf EvalDel}($a$)
\begin{description}
\vspace*{-.2cm}
\item
\emph{Input}: An action node $a$ that belongs to the current TA-graph.
\vspace*{-.3cm}
\item 
{\it Output}: A pair formed by a set of actions and a temporal value $t$.
\end{description}
%

\begin{tabbing}
1.  ~~~ \= $INIT_l \assign Supported\_facts(Level(a))$; \\
2. \> $Rplan \assign$ {\sf RelaxedPlan}($Unsup\_facts(a), INIT_l, \emptyset$). \\
3. \>  {\bf return} $Rplan$.
\end{tabbing}

\caption{\label{alg:EvalAddDel} Algorithms for estimating the search,
execution and temporal costs for the insertion (${\sf EvalAdd}$) and removal 
({\sf EvalDel}) of an action node $a$. $Rplan$ is a pair of values,
identified by $Aset(Rplan)$ and $End\_time(Rplan)$, where the first is
a set of actions and the second a temporal value. $Num\_acts$, 
$Supported\_facts$, $Duration$ and $Threats$ have been defined in 
Section \ref{sec:Rplan}. $Unsup\_facts(a)$ denotes the set of 
precondition nodes that become unsupported by removing $a$ from $\Act$.
}
\end{figure}

\noindent
where {\sf EvalAdd($a$)} and {\sf EvalDel($a$)} are the functions 
defined in Figure \ref{alg:EvalAddDel}. {\sf EvalAdd($a$)} returns
two values: the set of actions in $\pi_r$ ($Aset$) and an
estimation of the earliest time when the new action $a$ would
terminate ($End\_time$).  Similarly for {\sf EvalDel($a$)}, which
returns the set of actions in the relaxed plan achieving the 
preconditions that would become unsupported if $a$ were removed from 
$\Act$, together with an estimation of the earliest time when all
these preconditions would become supported. The relaxed subplans used
in {\sf EvalAdd($a$)} and {\sf EvalDel($a$)} are computed by {\sf
RelaxedPlan}, as described in Section \ref{sec:Rplan}.

After having computed the state {\em INIT}$_l$ using
$Supported\_facts(l)$, in step 2 {\sf EvalAdd} uses {\sf RelaxedPlan}
to compute a relaxed subplan ($Rplan$) for achieving the preconditions
of the new action $a$ from {\em INIT}$_l$. Steps 3--4 compute an
estimation of the earliest time when $a$ can be executed as the
maximum value over the end times of all the actions preceding $a$ in $\Act$
($t_1$) and $End\_time(Rplan)$ ($t_2$). Steps 5--6 compute a relaxed
plan for {\em Threats}$(a)$ taking account of $a$ and the actions in the
first relaxed subplan.

{\sf EvalDel} is simpler than {\sf EvalAdd}, because the only new
inconsistencies that can be generated by removing $a$ are the
precondition nodes supported by $a$ (possibly through the no-op
propagation of its effects) that would become unsupported. 
$Unsup\_facts(a)$ denotes the set of these nodes.

Of course, an action elimination from $\Act$ to cope with an
inconsistency could remove some additional inconsistencies (the
unsupported preconditions of the eliminated action).  Similarly, an
action that is added to $\Act$ to support a certain precondition could
support additional preconditions as well. However note that, as
described in Section \ref{sec:walkplan}, {\sf Walkplan}, like {\sf
Walksat}, does not consider possible improvements during the
evaluation of the search neighborhood.  Hence, {\sf EvalDel} and {\sf
EvalAdd} do not take account of additional inconsistencies that 
are removed from $\Act$ as positive ``side-effects'' of coping 
with the inconsistency under consideration.

In order to illustrate the steps of {\sf EvalAdd}, consider again the
example of Figure \ref{fig:RelaxedPlan}. As shown in Section
\ref{sec:example-relaxedplan},
the pair assigned to $Rplan$ by step 2 of {\sf EvalAdd(a)} is $\langle
\{a_1, a_4, a_5 \}, 240 \rangle$ (which is the pair of values returned
by {\sf RelaxedPlan}$(Pre(a),INIT_l,\emptyset)$).  At step 3 of {\sf
EvalAdd(a)} suppose that $t_1$ is set to 230 (i.e., that the highest
temporal value assigned to the actions in the TA-graph that must
precede $a$ is 230).  Step 4 sets $t_2$ to $MAX\{230, 240\}$, and the
execution of {\sf RelaxedPlan}$(\{q\}, \,${\em INIT}$_l-\{q\},\{a_1,
a_4, a_5, a\})$ at step 6 returns $\langle \{a_1, a_4, a_5, a, a_7 \},$
$t_q \rangle$, where $t_q$ is a temporal value that is ignored in the
rest of the algorithm, because it does not affect the estimated end
time of $a$.
Thus, since the duration of $a$ is 30, the output of {\sf EvalAdd(a)} 
is $\langle \{a_1, a_4, a_5, a, a_7 \}, 240+30 \rangle$.         
 
\subsection{Computing Reachability and Temporal Information}
\label{sec:reachability}

The techniques described in the previous subsection for computing the
action evaluation function use heuristic reachability information about 
the minimum number of actions required to achieve a fact $f$ from
{\em INIT}$_l$ ($Num\_acts(f,l)$), and the earliest times for actions and 
preconditions.
{\sc lpg} precomputes $Num\_acts(f,l)$ for $l = 1$ and any fact $f$,
i.e., it estimates the minimum number of actions required to achieve 
$f$ from the initial state $I$ of the planning problem before starting 
the search. 
For $l > 1$, $Num\_acts(f,l)$ can be computed only during search
because it depends on which actions nodes are in the current 
TA-graph (at levels preceding $l$).  Since during search many action 
nodes can be added and removed, it is important that the 
computation of $Num\_acts(f,l)$ is fast.

\begin{figure}
%
{\sf ComputeReachabilityInformation}($I,{\cal O}$)
\vspace{-0.2cm}
\begin{description}
\item
{\it Input}: The initial state of the planning problem under consideration ($I$) 
and all ground instances of the operators (${\cal O}$);
\vspace{-0.2cm}
\item
{\it Output}: An estimate of the number of actions ($Num\_acts$)
and of the earliest time ($Time\_fact$) required to achieve each
fact from $I$.
\end{description}
\vspace{-0.4cm}
\begin{tabbing}
1. ~~~ \=  {\bf forall }\= facts $f$  ~~{\small /* the set of all facts is
precomputed by the operator instantiation phase */}\\
2. \>\> {\bf if} $f \in I $ {\bf then}\\
3. \>\>~~~~$Num\_acts(f,1) \assign 0$; $Time\_fact(f,1) \assign 0$; $Action(f,1) \assign a_{start}$;\\
4. \>\> {\bf else} $Num\_acts(f,1) \assign -1$;\\
5. \> $F \assign {I}$; $F_{new}\assign {I}$; \( A \assign {\cal O}\); \\
6. \>{\bf  while } $F_{new} \not = \emptyset $ \\
7. \>\>  $F\assign F \cup F_{new}$; $F_{new} \assign \emptyset$\\
8. \>\>{\bf  while } \( A' = \{ a \in A \mid  Pre(a) \subseteq F\}\) is not empty \\
9. \>\>~~~~\= $a \assign $ an action in $A'$;\\
10. \>\>\> $ ra \assign$ {\sf RequiredActions}(${I}, Pre(a)$);\\
11. \>\>\> $t \assign  \stackdown{MAX}{f \in Pre(a)}{ Time\_fact(f,1)}$;\\
12. \>\>\> {\bf  forall  }\=  $f\in Add( a )$ \\
13.\>\>\>\>
{\bf if}  $f \not\in F \cup F_{new}$ or $Time\_fact(f,1) > (t + Duration(a))$ {\bf then}
\\
14.\>\>\>\> ~~~~~~~\= $Time\_fact(f,1) \assign t + Duration(a)$;\\
15.\>\>\>\>  
{\bf if}  $ f \not\in F\cup F_{new}$ or  $Num\_acts(f,1) > (ra+1)$  {\bf then}
\\
16.\>\>\>\>\>$Num\_acts(f,1) \assign ra + 1$;
\\
17.\>\>\>\>\>$Action(f,1) \assign a $;
\\
18. \>\>\> $F_{new} \assign F_{new} \cup Add(a) - F$; 
\\
19. \>\>\> $A \assign A - \{a\}$; 
\\
\end{tabbing}

{\sf RequiredActions}($I,G$)
\vspace{-0.2cm}
\begin{description}
\item
{\it Input}: A set of facts $I$ and a set of action preconditions $G$;
\vspace{-0.2cm}
\item
{\it Output}: An estimate of the minimum number of actions
required to achieve all facts in $G$ from $I$ ({\em ACTS}).
\end{description}
\vspace{-0.4cm}
\begin{tabbing}
1. ~~~ \= $ACTS \assign \emptyset$; \\
2. \> $G \assign G - I$; \\
3. \> {\bf while } $G\not = \emptyset $ \\ 
4. \> ~~~\= $g \assign$ an element of $G$; \\
5. \> \> $ a \assign Action(g,1)$;\\
6. \> \> $ACTS \assign  ACTS \cup \{ a \} $;\\
7. \> \>  \( G \assign G ~ \cup ~ Pre(a) - I - \bigcup_{b\in ACTS} Add(b) \); \\
8. \> {\bf  return}(\(| ACTS |\)).
\end{tabbing}
\caption{\label{alg:reachability}
Algorithms for computing heuristic information about the reachability of each
fact.
}
\end{figure}

Figure \ref{alg:reachability} gives {\sf ComputeReachabilityInformation}, 
the algorithm used by {\sc lpg} for computing $Num\_acts(f,1)$ trying to
take account of the tradeoff between quality of the estimation and 
computational effort to derive it. The same algorithm could be used for 
(re)computing $Num\_acts(f,l)$ after an action insertion/removal for 
any $l > 1$ (when $l >1$, instead of $I$, in input the algorithm has 
$Supported\_facts(l)$).\footnote{
  In order to obtain better performance, for $l > 1$ {\sc lpg} uses 
  an incremental version of {\sf ComputeReachabilityInformation} 
  updating $Num\_acts(f,l)$ after each action insertion/removal.
  We omit the details of this version of the algorithm.}
In addition to $Num\_acts(f,1)$, {\sf ComputeReachabilityInformation}
derives heuristic information about the possible earliest time
of every fact $f$ reachable from $I$ ($Time\_fact(f,1)$). 
{\sc lpg} can use $Time\_fact(f,1)$ to assign an initial temporal
value ($Time(f)$) to any unsupported fact node representing $f$,
instead of leaving $Time(f)$ undefined as we indicated in Section
\ref{sec:TA-graphs}.  This can give a more accurate estimation of the
earliest start time of an action with unsupported preconditions, which
is defined as the maximum value over the times assigned to its preconditions.
Note that $Time\_fact(f,1)$ is not updated when actions are added to
(or removed from) the current TA-graph.
%

Before illustrating in detail the algorithm for computing reachability
information that we used for the competition version of {\sc lpg}, we
should also note that preconditions involving numerical quantities are
ignored by this technique. A new version taking numerical preconditions
into account is under development.


\subsubsection{Computation of $Num\_acts$ and $Time\_facts$}
\label{sec:numacts-timefacts}

For clarity we first describe only the steps of {\sf
ComputeReachabilityInformation} used to derive $Num\_acts$, and
then we comment on the computation of $Time\_fact$.
In steps 1--4, the algorithm initializes $Num\_acts(f,1)$ to 0, if 
$f \in I$, and to -1 otherwise (indicating that $f$ is not reachable).
Then in steps 5--19 it iteratively constructs the set $F$ of facts that are
reachable from $I$, starting with $F = I$, and terminating when $F$
cannot be further extended. In this forward process each action is
applied at most once, when its preconditions are contained 
in the current $F$. The set $A$ of the available actions is 
initialized to the set of all possible actions (step 5), and it is 
reduced after each action application (step 19).
The internal while-loop (steps 8--19) applies the actions in $A$ to the
current $F$, possibly deriving a new set of facts $F_{new}$ in step
18. If $F_{new}$ is not empty, $F$ is extended with $F_{new}$ and the
internal loop is repeated. Since $F$ monotonically increases and the
number of facts is finite, termination is guaranteed. 
When an action $a$ in $A'$ (the subset of actions currently in $A$ 
that are applicable to $F$) is applied, the reachability information 
for its effects are revised as follows.
First we estimate the minimum number $ra$ of actions required to 
achieve $Pre(a)$ from $I$ using the subroutine {\sf RequiredActions} 
(step 10). Then we use $ra$ to possibly update $Num\_acts(f,1)$
for any effect $f$ of $a$ (steps 12, 15--16). If the application of $a$ leads 
to a lower estimation for $f$, i.e., if $ra + 1$ is less than the current 
value of $Num\_acts(f,1)$, then $Num\_acts(f,1)$ is set to $ra+1$. 
In addition, a data structure indicating the current best action to 
achieve $f$ from $I$ ($Action(f,1)$) is set to $a$ (step 17).\footnote{
  In the actual algorithm implemented in {\sc lpg}, when we set $Action(f,1)$,
  we consider also the case in which $Num\_acts(f,1)$ is equal to 
  $ra+1$; if the execution cost of $a$ is lower than that cost of
  the current $Action(f,1)$, or they have the same cost but the
  $a$ supports $f$ earlier, then $Action(f,1)$ is revised to $a$.
  For clarity these details are omitted from the formal description
  of the algorithm.} 

For any fact $f$ in the initial state, the value of $Action(f,1)$ is
$a_{start}$ (step 3).  {\sf RequiredActions} uses $Action$ to derive
$ra$ through a backward process starting from the input set of action
preconditions ($G$), and ending when $G \subseteq I$.  The subroutine
incrementally constructs a set of actions ({\em ACTS}) achieving the
facts in $G$ and the preconditions of the actions already selected
(using $Action$). At each iteration the set $G$ is revised 
by adding the preconditions of the last action selected, and removing
the facts belonging to $I$ or to the effects of actions already 
selected (step 7). Termination of {\sf RequiredActions} is
guaranteed because every element of $G$ is reachable from~$I$.

$Time\_fact(f,1)$ is computed in a way similar to $Num\_acts(f,1)$.
Step 3 of {\sf ComputeReachabilityInformation} initializes it to 0,
for any fact $f$ in the initial state. Then, at every application of
an action $a$ in the forward process described above, we estimate the
earliest possible time $t$ for applying $a$ as the maximum value over
the times currently assigned to its preconditions (step 11). For any
effect $f$ of $a$ that has not been considered yet (i.e., that is not
in $F$), or that has a temporal value higher than $t$ plus the
duration of $a$, steps 13--14 set $Time\_fact(f,1)$ to this lower
value (because we have found a shorter relaxed plan to achieve $f$
from $I$).

The complexity of {\sf ComputeReachabilityInformation} is polynomial
in the number of facts and actions in the problem/domain under
consideration. Step 10, the most expensive step of the algorithm, is
executed $O(|{\cal O}|)$ times, where $\cal O$ is the set of all
actions, and $|{\cal O}|$ is the size of this set.
It is easy to see that the worst-case time complexity of
{\sf RequiredActions} is $O(|{\cal O}|)$.  It follows that the time
complexity of {\sf ComputeReachabilityInformation} is $O(|{\cal
O}|^2)$. However, we have experimentally observed that very often {\sf
RequiredActions} terminates returning numbers much smaller than $|\cal
O|$ (i.e, that the number of iterations that the algorithm performs is
well below $|\cal O|$).  Finally, we observe that the order in which
actions are examined for their application in the forward process can
affect the output results.  In our current implementation we use a
random order. 

\begin{figure}[t]
\hspace{72mm}
\psfrag{a1}{\huge $a_1$}
\psfrag{a2}{\huge $a_2$}
\psfrag{a3}{\huge $a_3$}
\psfrag{a4}{\huge $a_4$}
\psfrag{a5}{\huge $a_5$}
\psfrag{a6}{\huge $a_6$}
\psfrag{a7}{\huge $a_7$}
\psfrag{f1}{\Large $f_1$}
\psfrag{f2}{\Large $f_2$}
\psfrag{f3}{\Large $f_3$}
\psfrag{f4}{\Large $f_4$}
\psfrag{f5}{\Large $f_5$}
\psfrag{f6}{\Large $f_6$}
\psfrag{f7}{\Large $f_7$}
\psfrag{f8}{\Large $f_8$}
\psfrag{f9}{\Large $f_9$}
\psfrag{f10}{\Large $f_{10}$}
\psfrag{f11}{\Large $f_{11}$}
\psfrag{f12}{\Large $f_{12}$}
\psfrag{f13}{\Large $f_{13}$}
\psfrag{f14}{\Large $f_{14}$}
\psfrag{f15}{\Large $f_{15}$}
\psfrag{f16}{\Large $f_{16}$}
\psfrag{f17}{\Large $f_{17}$}
\includegraphics[angle=0,width=0.5\textwidth]{./examples-jair/ComputeReachabilityInformation.eps} 

\vspace{-85mm}
\small
\begin{tabular}{| c | c | c |}
\hline
Actions            & $ra$ & Duration \\
\hline
$a_1$           & 0 &  10  \\
$a_2$           & 0 &  30 \\
$a_3$           & 0 &  50 \\
$a_4$           & 2 &  50 \\     
$a_5$           & 2 &  70 \\
$a_6$           & 1 &  30 \\
$a_7$           & 5 &  20 \\
\hline
\hline
Facts            & $Num\_acts$ & $Time\_fact$ \\
\hline
$f_9$           & 1 & 10 \\
$f_{10}$        & 1 & 30 \\
$f_{11}$        & 1 & 30 \\
$f_{12}$        & 1 & 50 \\
$f_{13}$        & 3 & 80 \\
$f_{14}$        & 3 & 120\\
$f_{15}$        & 2 & 80\\
$f_{16}$        & 2 & 80\\
$f_{17}$        & 7 & 140 \\
\hline
\end{tabular}
\vspace{10mm}
\caption{ \label{fig:ComputeRI}
%
An example illustrating {\sf ComputeReachabilityInformation}. The numbers
in parenthesis are $Num\_acts$ values. ${\cal O} = \{ a_1,a_2,...,a_7\}$.
The subscript of each action corresponds to the order in which it is 
applied.
%
}
\end{figure}

%
Figure \ref{fig:ComputeRI} illustrates the algorithm with an example.
Suppose that the facts in the initial state $I$ are $f_{1...8}$, and
that the actions in $\cal O$ are $a_{1...7}$, where the subscript of
the actions correspond to the order in which they are applied by the
algorithm.  The first actions that are applied are $a_1$, $a_2$ and
$a_3$, because their preconditions are in $F$ which is initially set
to $I$.  The $Num\_acts$ value of these preconditions is set to zero,
because {\sf RequiredActions} applied to them returns zero.  In the
internal for-loop of the algorithm we update the reachability
information for each effect of these actions.  In particular, consider
the effects $f_1$ and $f_9$ of $a_1$. Since $f_1$ is not a new fact
(it belongs to $I$) and its $Num\_acts$ and $Time\_fact$ values are
set to the minimum (initial) values, steps 14 and 16 do not revise
them.  Since $f_9$ is a new fact, step 14 sets $Time\_fact(f_9)$ to 10
(i.e., the duration of $a_1$), and step 16 sets $Num\_acts(f_9)$ to 1
($ra$ is zero). Moreover, $Action(f_9,1)$ is set to $a_1$ by step 17.  
The effects of $a_2$ and $a_3$ are handled similarly.

At this point, since there is no other action that is applicable in
$F$, the internal while-loop terminates, $F$ is set to $F \cup
\{f_9,f_{10},f_{11},f_{12}\}$, and $F_{new}$ is set to $\emptyset$.
The set $A'$ of the actions in $A$ that are applicable is
$\{a_4,a_5,a_6\}$. Consider the application of $a_4$.  We have that
$ra$ at step 10 is set to 2, because {\sf
RequiredActions}$(I,Pre(a_4))$ sets {\em ACTS} to $\{a_1,a_2\}$ (note
that $f_1 \in I$, $Action(f_9,1)=a_1$, $Action(f_{10},1)=a_2$, and all
preconditions of these actions are in $I$). Thus, $Time\_fact(f_{13})$
is set to 80 (i.e., the maximum temporal value assigned to a
precondition of $a_4$, 30, plus the duration of $a_4$), and
$Num\_acts(f_{13})$ to 3. The effects of the actions $a_5$ and $a_6$
are handled in a similar way. However, it is worth noting that
$Num\_acts(f_{15})$ is first set to 3, when we examine $a_5$, and then
revised to 2, when we examine $a_6$.  Analogously,
$Time\_fact(f_{15})$ is first set to 120, and then revised to 80,
while $Action(f_{15},1)$ is first set to $a_5$ and then to $a_6$.

Consider now the preconditions of the last applicable action $a_7$.
{\sf RequiredActions} applied to $Pre(a_7)$ by step 10 returns 6, 
because the set {\em ACTS} of actions selected by the subroutine is
$\{a_4, a_1, a_2, a_5, a_3, a_6\}$.  Steps 11 of the {\sf
ComputeReachabilityInformation} sets $t$ to $Time\_fact(f_{14})=120$,
and hence the $Time\_fact$-value for the new effect $f_{17}$
is set to 120+20, while its $Num\_acts$-value is set to 6+1.

 
\subsubsection{Related work on reachability information}
%
Other techniques for estimating the cost of reaching a fact (or a set
of facts) from a certain state have been proposed and used in some
planners, e.g., {\sc hsp} \cite{Geffner-AI01}, {\sc ff}
\cite{HofNeb-JAIR01} and {\sc sapa} \cite{DoKam:aips-02}.  When
comparing {\sf ComputeReachabilityInformation} with these techniques,
we should note that in {\sc lpg} the $Num\_acts$-values are used to
select the actions forming relaxed plans achieving sets of action
preconditions or goals (computed by {\sf RelaxedPlan}). These relaxed
plans are then used by the action evaluation function $E$ guiding
the search.  In general, this approach is similar to {\sc ff}'s and
{\sc sapa}'s methods, but with some significant differences that we
comment on below.

Bonet \& Geffner proposed two basic heuristics for {\sc hsp}, $h_{max}$ and
$h_{add}$. In $h_{add}$ the (search) cost of a set of facts is the sum
of the costs of each individual fact, while in $h_{max}$ it is the
maximum cost over all individual costs. As noted by Haslum and Geffner
\citeyear{HasGef:aips00}, 
$h_{max}$ and $h_{add}$ are approximation of the optimal cost function
of a relaxed problem where delete effects are ignored.  $h_{add}$
ignores positive interactions among subgoals that could make one goal
simpler after a second one has been achieved (this makes $h_{add}$
non-admissible).  $h_{max}$ is admissible, but it is less informative 
and effective for Bonet \& Geffner's {\sc hsp} planner.

A difference between the forward process of our algorithm for
computing $Num\_acts$ and Bonet \& Geffner's forward propagation for
computing $h_{add}$ is that in our propagation every action is applied
at most once, while in their propagation it can be considered more
than once (for computing $h_{max}$ it suffices to apply each action
once with an appropriate order).  This restriction, that we introduced
for efficiency reasons, can clearly lead to overestimation of
reachability costs. By adding a new step between steps 17 and 18 of
{\sf ComputeReachabilityInformation} that adds to $A$ every action
with $f$ as precondition, we can obtain a more accurate cost
propagation like in $h_{add}$. However, this could slow down the
planning process, given that reachability information may be
(re)computed many times during search.

Another important difference concerns the use of the subroutine {\sf
RequiredActions} at step 10 for estimating the cost of reaching a set
of preconditions $G$. Instead of considering the maximum value over the
costs of the preconditions or the sum of their costs, like in $h_{max}$
and $h_{add}$, respectively, we compute a relaxed plan for $G$, and we
count the number of actions forming it. This can be seen as an
intermediate approach between the $h_{max}$ and $h_{add}$ methods, 
aimed at taking account of positive interactions among subgoals.\footnote{
  Note that if we replaced step 10 with $ra$
  $\leftarrow$ ``sum of $Num\_acts(f,1)$ for each $f$ in $Pre(a)$'', then 
  the resulting algorithm would be quite similar to $h_{add}$ (using
  the additional step for reconsidering actions already applied that we 
  mentioned above). }

Finally, another difference concerns the initial set of
actions used in the forward process. While our set (${\cal O}$) does
not contain actions with preconditions that are mutex, Bonet \&
Geffner's forward processes for computing $h_{max}$ and $h_{add}$
contain them. The use of our restricted set of actions would make
the approximation of $h_{max}$ and $h_{add}$ more accurate.

As observed by Hoffmann \citeyear{Hoffman-01}, {\sc ff}'s reachability
technique is similar to $h_{max}$, and so the previous observations
about $h_{max}$ compared to our reachability information hold also for
{\sc ff}'s technique. Another difference with respect to {\sc ff}
concerns the choice of actions forming the relaxed plans. While {\sf
RelaxedPlan} and {\sf EvalAdd} take threats into account, {\sc ff}'s
relaxed plans do not consider them. Moreover, {\sc ff} can generate
relaxed plans including actions with mutex preconditions, while we
exclude such actions.

Most of the differences with respect to {\sc hsp}'s and {\sc ff}'s
reachability information that we have outlined appear to also hold 
when comparing {\sf ComputeReachabilityInformation} and {\sc sapa}'s
reachability techniques (in particular, the use
of {\sf RequiredActions} for estimating the search cost of a {\em set}
of preconditions, the application of an action at most once in the
forward process, and the use of a more restrictive set of actions
${\cal O}$).
Another significant difference is that, while {\sc sapa}'s reachability
information concerns execution and temporal costs, our information
concerns mainly search costs. As a consequence, the action choices in
{\sf RelaxedPlan} depend mainly on the search costs (as we pointed
out, when there is more than one action with the lowest search cost,
$Bestaction$ chooses the one with lower execution cost). In {\sc lpg}
the execution and temporal costs of the relaxed plans are subsequently
taken into account by the action evaluation function $E$, using the
actions in the computed relaxed plans.  A major motivation for giving
primary importance to search costs was that we designed our planner as
an any time planning system, that can compute a first solution
quickly, and then derive additional solutions with incrementally
better quality, but requiring more CPU-time (this incremental process
is described in Section \ref{sec:incremental-quality}).


\subsection{Updating Ordering Constraints and Temporal Values}
\label{sec:ordering-time}

In this subsection we describe the generation during search of action
ordering constraints in the current TA-graph $\Act$, and the update at
each search step of the temporal values associated with the fact and
action nodes of $\Act$.  If during search the planner adds an action
node $a$ to $\Act$ for supporting a precondition of another action
node $b$, then $a \prec_C b$ is added to $\Omega$.  Moreover, for each
action $c$ in $\Act$ that is mutex with $a$, if $Level(a) < Level(c)$,
then $a \prec_E c$ is added to $\Omega$, otherwise ($Level(c) <
Level(a)$) $c \prec_E a$ is added to $\Omega$.  If the planner removes
$a$ from $\Act$, then any ordering constraint involving $a$ is removed
from $\Omega$.

The addition/removal of an action node $a$ also determines a possible
revision of $Time(x)$, the temporal value assigned to any fact and
action $x$ that is (directly or indirectly) connected to $a$ through
the ordering constraints in $\Omega$.  Essentially, the algorithm for
revising the temporal values assigned to the nodes of $\Act$ performs
a simple forward propagation starting from the effects of $a$, and
updating level by level the times of the actions (together with the
relative precondition and effect nodes) that are constrained by
$\Omega$ to start after the end of $a$.  If every precondition is of
type {\tt overall} and every effect is of type {\tt at\,end}, when an
action node $a'$ is considered for possible temporal revision,
$Time(a')$ becomes the maximum value over the temporal values assigned to
(a) its preconditions and (b) the actions preceding $a'$ according to
$\Omega$, plus the duration of $a'$. The times assigned to the
effect nodes of $a'$ are revised accordingly. If $a'$ is the only
action node supporting a precondition node $f$, or its temporal value is
lower than the value assigned to the other action nodes supporting $f$,
then $Time(f)$ is set to $Time(a')$.
%
For instance, suppose that, in order to support the precondition node
$f_7$ of $a_4$ in the TA-graph in Figure \ref{fig:TA-graph}, we insert
the action node $a_5$ at level 4 (see Figure \ref{fig:TA-graph-rev}).
$a_5$ has duration 110 and precondition node $f_8$.  Since $Time(f_8)$
= 120, $Time(f_7)$ becomes 230, which is propagated to $a_4$ and its
effects. $Time(a_4)$ becomes 270, $Time(f_{12})$ is revised to 220
($Time(a_3)$), $Time(f_{13})$ is revised to 270 ($Time(a_4)$), while
$Time(f_8)$ remains 120 ($Time(a_2)$).


\begin{figure}[t]
%
\begin{center}
\psfrag{INIT}{\Large $INIT$}
\psfrag{a1}{\huge $a_1$}
\psfrag{a2}{\huge $a_2$}
\psfrag{a3}{\huge $a_3$}
\psfrag{a4}{\huge $a_4$}
\psfrag{a5}{\huge $a_5$}
\psfrag{f1}{\huge $f_1$}
\psfrag{f2}{\huge $f_2$}
\psfrag{f3}{\huge $f_3$}
\psfrag{f4}{\huge $f_4$}
\psfrag{f5}{\huge $f_5$}
\psfrag{f6}{\huge $f_6$}
\psfrag{f7}{\huge $f_7$}
\psfrag{f8}{\huge $f_8$}
\psfrag{f9}{\huge $f_9$}
\psfrag{f10}{\huge $f_{10}$}
\psfrag{f11}{\huge $f_{11}$}
\psfrag{f12}{\huge $f_{12}$}
\psfrag{f13}{\huge $f_{13}$}
\includegraphics[angle=0,width=.95\textwidth]{./examples-jair/lin-temp-pg-o2.eps}
\[{\Omega}=\{ a_1\prec_C a_4 ; \; a_2\prec_C a_3;       %% CAUSAL CONSTRAINTS
              a_2\prec_C a_5; a_5 \prec_C a_4;          %% CAUSAL CONSTRAINTS
           \; a_1\prec_E a_2 ; a_2\prec_E a_3 \; a_2 \prec_E a_4 \}\]  %% MUTEX CONSTRAINTS
%
\end{center}
\caption{\label{fig:TA-graph-rev}         
%
Update of the TA-graph of Figure \ref{fig:TA-graph} after the addition
of action node $a_5$ at level 4 to support the precondition node $f_7$ 
of $a_4$. Dashed edges form chains of no-ops that are
blocked by mutex actions. Round brackets contain temporal values
assigned by ${\cal T}$ to the fact nodes (circles) and the action nodes
(squares). The numbers in square brackets represent action durations.
``(--)'' indicates that the corresponding fact node is not supported.
%
}
\end{figure}

%
Some operators in the domains used for the 3rd IPC contain
(pre)conditions of type ``{\tt at\,end}'' or ``{\tt at\,start}'', and
effects of type ``{\tt at\,start}'' \cite{FoxLon03:JAIR}, i.e.,
preconditions that must hold at the end or at the beginning of the
action, and effects that are true at the beginning of the action.  In
the following we revise the definition of $Time$ that we have given in
Section \ref{sec:TA-graphs} to consider actions involving these types
of preconditions/effects. When an action node $a$ has a precondition
node $p$ of type {\tt at\,end}, in the definition of $Time(a)$, we use
$Time(p)$ $-$ $Duration(a)$ instead of $Time(p)$.\footnote{ In the
special cases in which a precondition of $a$ is of type either {\tt
at\,end} or {\tt overall}, and it is also an effect node of type {\tt
at\,start} of $a$, $Time(p)$ is not considered in the definition of
$Time(a)$ because the action itself makes $p$ true (unless $p$ is also
a precondition node of $a$ of type {\tt at\,start}).  
}  
While in the definition of $Time(a)$ precondition nodes of type 
{\tt at\,start} are treated as precondition nodes of type {\tt overall}.

If an action node $a$ has an effect node $e$ of type {\tt at\,start},
when we estimate $Time(e)$, instead of using $Time(a)$, we use the
minimum value over (1) $Time(a')$, for any action node $a'$ supporting $e$
by an effect of type {\tt at\,end}, (2) $Time(a'')$ $-$
$Duration(a'')$, for any action node $a''$ supporting $e$ by an effect
of type {\tt at\,start}, and (3) $Time(a)$ $-$ $Duration(a)$ (because
$e$ is supported at the start time of $a$).
 
When preconditions of type different from {\tt over\,all} and effects
of type different from {\tt at\,end} are present in the domain
specification, in some cases two mutex actions can partially
overlap.\footnote{
  For example, if $f$ is a precondition {\tt at\,start} of $a$ and 
  $\neg f$ is an effect {\tt at\,end} of $b$, although $a$ and $b$ 
  are mutex, $a$ can overlap $b$ (e.g., $a$ can start after the 
  start time of $b$ and terminate before the end time of $b$).
  If $a$ is at a level preceding the level of $b$, the only 
  ordering constraint that should be imposed is that {\em the start
  of $a$ is before the end of $b$}. Otherwise, the imposed ordering
  constraint is that the end of $b$ is before the start of $a$, and 
  so the two actions do not overlap.
} 
The version of {\sc lpg} that took part in the 3rd IPC did not
handle these possible overlaps, and any pair of mutex actions was
treated by always imposing an ordering constraint between the 
end of an action and the start of the other one. 
%
While this is always a sound way of ordering mutex actions, it might
over-constrain the actions, introducing unnecessary delays in the
plan.  However, in the test problems of the 3rd IPC the possibility of
overlapping mutex actions is rare, and when it is possible it does not
affect the temporal quality of the plans significantly. Recently, we
have extended the treatment of mutex actions in {\sc lpg},
distinguishing various types of interferences and competing needs.
These are handled by ordering constraints between different endpoints
of the involved actions, allowing overlapping mutex actions.
Experimental results using the SimpleTime variant of the {\tt
Satellite} domain show that the new version of {\sc lpg} generates
plans which are about 10\% better (in terms of makespan) than those
computed by the competition version. Moreover, the overhead introduced
by the more sophisticated management of the temporal information is on
average negligible. A detailed description of how temporal
information is managed in the new version of {\sc lpg} is given
in another recent paper \cite{GerSaeSer03:AIIA}.

\subsection{Numerical State Variables}
\label{sec:numerical-vars}
In this subsection we briefly describe how {\sc lpg} deals with
preconditions and effects involving numerical quantities. We start
with a brief description of numerical preconditions and effects
in {\sc pddl\small 2.1}, and then we show how the plan representation,
search neighborhood and heuristics that we presented in the previous
sections have been extended to handle them.

%
In {\sc pddl\small 2.1} a state $s$ for a planning domain involving
numerical variables is a pair $\langle p(s), v(s)\rangle$ where $p(s)$
is a set of ground atoms (positive facts), and $v(s) = \langle r_1,
\ldots, r_n \rangle$ is a tuple of real numbers representing the
values of the $n$ numerical variables $v^1$, $v^2$, ..., $v^n$.  A
numerical expression is an arithmetic expression over the set $V$ of
these variables and the real numbers. A numerical precondition is a
triple $\langle exp, rel, exp' \rangle$, where $exp$ and $exp'$ are
numerical expressions, and $rel\in\{<,\leq, =, \geq, >\}$ is a
relational operator.  A numerical effect is a triple $\langle v^i,
ass, exp \rangle$, where $v^i\in V$ is a variable, $ass\in\{:=,
+\hspace{-1.2mm}=, -\hspace{-1.2mm}=, *\hspace{-1.2mm}=, /
\hspace{-1.2mm}=\}$ is an assignment operator (using a C-like notation),
and {\em exp} is a numerical expression.
%

In order to handle numerical domains, we have extended the notion of
TA-graph with {\em numerical fact nodes} representing values of
numerical variables. For each level $l$ in the current action graph
$\Act$ and each numerical variable $v^i\in V$, there is a numerical
fact node representing the value for $v^i$ at level $l$. The resulting
tuple of real values at level $l$ is denoted by $Num\_values(l)$.
These values are derived by applying all actions in $\Act$ at the
levels preceding $l$, starting from the initial level and following
the order of the corresponding levels.\footnote{  
 This way of ordering actions at levels before $l$ is consistent
 with the action ordering constraints in $\Act$  (if any).
 Furthermore, note that if an action $a$ at level $l$ has a numerical
 precondition involving a numerical variable $v^j$, then 
 any action $b$ with an effect affecting the value of $v^j$ is mutex
 with $a$. So, if $\Act$ is a TA-graph, then $b \prec_E a \in \Omega$.
 Otherwise ($\Act$ is a simple LA-graph without temporal information),
 $b \prec a$ is implied by the levels of $a$ and $b$.
}
The values of the numerical fact nodes at the initial level,
$Num\_values(0)$, are the real numbers assigned to the corresponding
numerical variables in the initial state of the planning problem under
consideration. Similarly, we can associate with each level $l$ a set
of facts that are true ($Supported\_facts(l)$), given the actions in 
$\Act$ at levels preceding $l$. In this way we can define a
numerical state $s_l$ = $\langle Supported\_facts(l),Num\_values(l)
\rangle$ for each level $l$ of $\Act$.

A numerical precondition $\langle exp, rel, exp'\rangle$ of an action
at a level $l$ is supported if and only if the values of $exp$ and
$exp'$ evaluated in $s_l$ satisfy the relation $rel$.

Every time an action is added/removed to/from a level of $\Act$ we
apply/retract the numerical effects of the action, which can modify
the values associated with some numerical fact nodes at the next
level.  These changes are propagated to the following levels of the
graph. During this propagation, we identify the numerical preconditions 
that become supported or unsupported. Moreover, if the value of a
numerical fact node affecting the duration of an action is changed, 
then we update the duration of this action.

The local search neighborhood associated with an unsupported numerical
precondition $p = \langle exp, rel,exp' \rangle$ of an action $a$ is
defined as the set of linear action graphs obtained by either removing
$a$, or adding a new action that {\em decreases} the ``gap'' between
the values of $exp$ and $exp'$ according to $rel$ (possibly supporting 
$p$).\footnote{
  %
  Note that it can be necessary to add more
  than one action to support a numerical precondition. 
  These actions are added to different levels by different search steps.
  For instance, suppose that $p = \langle x,>,100\rangle$ is a numerical
  precondition, and that $a$ is the only action with a numerical effect $e$
  increasing the value of $x$. If $e$ increases $x$ by 20 and the current 
  value of $x$ is 30, then we need four actions to support $p$.
}
In the competition version of {\sc lpg}, we considered adding an
action only to the level immediately before the level of $p$ (while
for a boolean unsupported precondition $q$ an action supporting it can
be added to {\em any} preceding level).  We are currently studying an
extension of the neighborhood in which supporting actions can be added
to any preceding level also in the case of numerical preconditions.

We now briefly describe how {\sc lpg} computes the relaxed plans used
by {\sf EvalAdd} and {\sf EvalDel} for numerical domains. This is done
by an extended version of {\sf RelaxedPlan} handling numerical
preconditions in a very simple way. Since the current version of {\sf
ComputeReachabilityInformation} ignores numerical preconditions, there
is no $Num\_acts$-value associated with them. Hence, when {\sf
RelaxedPlan} chooses the (heuristic) best action to support a subgoal
$g$, for each numerical precondition $p$ involved in the definition of
$Bestaction(g)$ (see Section \ref{sec:Rplan}), $Num\_acts(p,l)$ is
replaced by 1, i.e., the estimated minimum cost to satisfy any
numerical precondition is always 1. (Of course, this is quite a strong
assumption giving weak information; we are currently working on a
new version of the planner using more informative heuristics for
constructing relaxed plans involving numerical preconditions.)
%
Another difference in the definition of $Bestaction(g)$ is that, if
$g$ is a numerical precondition, instead of considering only the
actions supporting $g$, we consider every action that decreases the
gap between the values of the expressions forming $g$.

The relaxation of the plans computed by the extended version of {\sf
RelaxedPlan} concerns both the negative effects, which are ignored for
plan validity (but considered to count possible threats), and a form
of {\em monotonic} change of the minimum and maximum possible values
for the numerical quantities. We start from the numerical initial
state {\em INIT}$_l = \langle Supported\_facts(l),Num\_values(l)
\rangle$ and, for each numerical variable involved in an action in the
relaxed plan constructed from {\em INIT}$_l$, we consider only the
minimum/maximum values that the variable can assume given the actions
already in the relaxed plan. These values are monotonically
decreased/increased whenever an action is added to the relaxed plan.
Specifically, we define two tuples of numerical values, $v_{max}$ and
$v_{min}$, that are both initialized using $Num\_values(l)$.  If an
effect of an action in the relaxed plan increases the value of a
variable $v^i$ by a quantity $\delta$, then we increase $v^i_{max}$ by
$\delta$; while, if it decreases the value of $v^i$ by $\delta$, then
we decrease $v^i_{min}$ by $\delta$.  During the construction of a
relaxed plan, when we check whether a numerical precondition $p =
\langle v^x, >, v^y \rangle$ is supported, we evaluate $v^x > v^y$
considering $v^x_{max}$ as the value assigned to $v^x$, and
$v^y_{min}$ as the value assigned to $v^y$. If an expression involves
more than one numerical variable (e.g., $p = \langle v^x - v^y, >, v^z
\rangle$), we consider the combination of the maximum/minimum values
that is most favorable to satisfy the condition (the value of $v_x$ is
$v_{max}$, the value of $v^y$ is $v^y_{min}$, and the value of $v^z$
is $v^z_{min}$).  Similarly if the expression involves another
relational operator.


\subsection{Multi-Criteria Incremental Plan Quality}
\label{sec:incremental-quality}

As we have seen, our approach can model different plan quality criteria 
determined by action execution costs and action durations. 
%
The coefficients $\alpha$, $\beta$ and $\gamma$ of the action
evaluation function $E$ specified in Section \ref{sec:neighborhood}
are used to weigh the relative importance of the execution and
temporal costs of $E$, as well as to normalize them with respect to
the search cost.  Specifically, {\sc lpg} uses the following function
for evaluating the insertion of an action node $a$ (the evaluation
function $E(a)^r$ for removing an action node is analogous):

%
\[ E(a)^i =
 \frac{\mu_E}{max_{ET}} \cdot Execution\_cost(a)^i +
 \frac{\mu_T}{max_{ET}} \cdot Temporal\_cost(a)^i  +
 \frac{1}{max_S} \cdot Search\_cost(a)^i,
\]
%

\noindent
where $\mu_E$ and $\mu_T$ are non-negative coefficients that weigh
the relative importance of the execution and temporal costs,
respectively. Their values can be set by the user, or they can be
automatically derived from the expression defining the plan metrics in
the formalization of the problem. The factors $1/max_{ET}$ and
$1/max_S$ are used to normalize the terms of $E$ to a value less than
or equal to $1$.  The value of $max_{ET}$ is defined as $\mu_E \cdot
max_E + \mu_T \cdot max_T$, where $max_E$ ($max_T$) is the maximum
value of the first (second) term of $E$ over all TA-graphs in the
neighborhood, multiplied by the number $\kappa$ of inconsistencies in
the current action graph; $max_S$ is defined as the maximum value of
$Search\_cost$ over all possible action insertions/removals that
eliminate the inconsistency under consideration.  The role of $\kappa$
is to decrease the importance of the first two optimization terms when
the current plan contains many inconsistencies, and to increase it
when the search approaches a valid plan.  I.e., $E(a)^i$ can be
rewritten as

\[\begin{array}{ll}
E(a)^i =
 \frac{1}{\kappa \cdot (\mu_E \cdot max_E + \mu_T \cdot max_T)} \cdot 
 \left(\mu_E \cdot Execution\_cost(a)^i + \mu_T \cdot Temporal\_cost(a)^i
 \right) \ +
\\
\vspace{-0.3cm}
\\
~~~~~~~~~~~~~~~~~~~~~~~~~\,\, + \ \frac{1}{max_S} \cdot Search\_cost(a)^i.
\end{array}
\]

Without this normalization the first two terms of $E$ could be much
higher than the value of the third term. This would guide the search
towards good quality plans without paying sufficient attention to
their validity. Instead, we would like to have the search give
more importance to reducing the search cost, rather than optimizing
the quality of a plan, especially when the current partial
plan contains many inconsistencies,

Our planner can produce a succession of valid plans where each plan is
an improvement of the previous ones in terms of quality.  The
first plan generated is used to initialize a new search for a second
plan with better quality, and so on. This is a process that
incrementally improves the quality of the plans, and the search can be
stopped at any time to give the best plan computed so far (each plan
can be written in a file as soon as it is derived).
When {\sc lpg} starts a new search, some inconsistencies are forced in 
the TA-graph representing the previous plan, and the resulting TA-graph 
is used to initialize the search.
Similarly, during search some random inconsistencies are forced in the
current TA-graph when a valid plan that does not improve the plan of
the previous search is reached.  This is done by choosing a small set
$R$ of action nodes that are removed from the action graph together
with (1) the action nodes supporting their preconditions and (2) the
action nodes with a precondition supported by an action in $R$.  The
elements of $R$ are chosen by taking account of the values of $\mu_E$
and $\mu_T$. If $\mu_E > \mu_T$, we randomly remove action nodes giving
higher probability to those representing actions with higher execution 
costs, otherwise preference is given to the action nodes having a higher
impact on the plan makespan.\footnote{
  In the version of {\sc lpg} that took part in the 3rd IPC this 
  second preference was based on a simple estimation of the 
  temporal impact of each action node. We are currently testing 
  a newer version that selects such actions more accurately by
  using the {\em critical path} in the graph of the ordering
  constraints in the TA-graph.}

In the 3rd IPC, for each test problem attempted, we considered only
the first and the last solutions generated by {\sc lpg} within five
CPU-minutes. The first solution was used to test how fast our planner
can be; the last solution to test how good a solution can be.  Often
the first solution has low quality compared to the last one, while the
last solution requires much more CPU-time than the first.  The other
fully-automated planners in the competition did not exhibit any-time
behavior like {\sc lpg}. So, when we compare our two solutions with
the single solution derived by the other planners, we should consider
that {\sc lpg} very often derives additional solutions of intermediate
quality, and requiring intermediate CPU-time.  In particular, as 
will be shown in the next section, it can be the case that, when (1)
the first solution found by {\sc lpg} requires less CPU-time than any
other planner, but has quality worse than the best solution found by
the other planners, and (2) the last solution of {\sc lpg} has superior
quality to all other planners but requires more CPU-time, {\sc lpg} finds
an intermediate solution which is still better than the solutions
found by all other planners {\em and} is derived in less CPU-time.

\section{Experimental Results}
\label{sec:experiments}

All our techniques are implemented in {\sc lpg}. The system is 
written in C and is available from {\tt http://prometeo.ing.unibs.it/lpg}.
%
In this section we present some experimental results illustrating the
efficiency of {\sc lpg} using the test problems of the 3rd IPC.  These
problems belong to several domains, 
%
most of which have some variants containing different features of 
{\sc pddl\small 2.1}. The variants are named ``Strips'', ``SimpleTime'',
``Time'', ``Complex'', ``Numeric'' and ``HardNumeric'', and are all
handled by our planner.  For a description of the domains and of the
relative variants, the reader can visit the official web site of the 3rd
IPC ({\tt www.dur.ac.uk/d.p.long/competition.html}). 
%


\begin{table}[t]
\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
%
%
\textbf{Planner}  & \textbf{Solved}   & \textbf{Attempted} & \textbf{
Success ratio}      \\
\hline
 LPG            & 442           & 468           & 94\%          \\
 FF             & 237           & 284           & 83\%          \\
 Simplanner     & 91            & 122           & 75\%          \\
 Sapa           & 80            & 122           & 66\%          \\
 MIPS           & 331           & 508           & 65\%          \\
 VHPOP          & 122           & 224           & 54\%          \\
 Stella         & 50            & 102           & 49\%          \\
 TP4            & 26            & 204           & 13\%          \\
 TPSYS          & 14            & 120           & 12\%          \\
 SemSyn         & 11            & 144           & 8\%           \\
\hline 
\end{tabular}
\caption{ \label{tab:coverage}
Number of problems attempted and solved by the planners that took part
in the 3rd IPC ordered by their success ratio.  The data from the
planners compared with {\sc lpg} are from the official web site of the
3rd IPC. The data for {\sc lpg} do not consider the 20 problems in 
{\tt Satellite} HardNumeric, which are all solved by the current version
of the planner, slightly improving the success ratio. 
}
\end{center}
\end{table}


All tests were conducted on the official machine of the competition,
an AMD Athlon$^{tm}$ MP 1800+ (1500MHz) with 1 Gbyte of RAM. 
The results for {\sc lpg} correspond to median values over five runs 
for each problem considered. The CPU-time limit for each run was
5 minutes, after which termination was forced.\footnote{
 When the CPU-time limit was exceeded in one or two runs, the 
 median values are derived by considering these runs as those
 producing the worst results. When the CPU-time limit was exceeded
 in three or four runs, instead of the median values, we considered
 the worst results of the remaining successful runs. This happened in 
 16 of the 442 problems solved.
}
Notice that the results that we present here are not exactly the same
as the official results of the competition, where for lack of time we
were not able to run our system a sufficient number of times to obtain
meaningful statistical data. However, in general the new results are
very similar to those of the competition,  with some considerable
improvement in {\tt Satellite} Complex and in the {\tt Rovers}
domains, where many problems could not be solved due to a minor bug in the
parser of our planner that was easily fixed right after the competition.

Overall, the number of problems attempted in the new tests by our
planner was 468 (over a total of 508 problems), and the success ratio
was 94.4\% (the problems attempted by {\sc lpg} in the competition
were 428 and the success ratio 87\%). Figure \ref{tab:coverage} gives
these data for every fully-automated planner that took part in the
competition. The success ratio of {\sc lpg} is the highest one
over all competing domain-independent planners.

The version of {\sc lpg} that we used in the competition is integrated
with an alternative search method that can be activated when the local
search is not effective. This method is based on the same best-first search
technique implemented in {\sc ff} \cite{HofNeb-JAIR01}. The only domain 
were we used best-first search instead of local search is {\tt FreeCells}.
The 40 problems that were not attempted by our planner are
the 20 problems in {\tt Settlers} Numeric and the 20 problems
in {\tt Satellite} HardNumeric. The first domain contains
operators with universally quantified effects, which are not handled
in the current version of {\sc lpg}. 
%
The plan metrics of the problems in the second domain require
maximizing the value of a certain numerical variable representing
acquired data ({\tt data-stored}), which is another feature of {\sc
pddl\small 2.1} that the competition version of {\sc lpg} did not
handle properly. Many of these problems were solved by the other
fully-automated planners by the empty plan or by plans with zero
quality. While such plans could have been derived also by {\sc lpg},
we did not consider these interesting solutions.\footnote{
  Very recently we have extended {\sc lpg} to handle maximization 
  of plan metric expressions. 
%
  This new version of {\sc lpg} solves all the 20 test 
  problems of {\tt Satellite} HardNumeric, generating plans with quality
  higher than zero.  The only fully-automated planner of the competition
  that derived solutions with {\tt data-}${\tt stored} > 0$ is {\sc mips}.
  An experimental comparison of {\sc mips} and {\sc lpg} considering only 
  these solutions shows that the plans  generated by 
  {\sc lpg} have quality much higher than those computed by {\sc mips}, 
  and that our planner is significantly faster (detailed results of this
  experiment are available from the web page of {\sc lpg}).
}

%
We ran {\sc lpg} with the same default settings for every problem
attempted (maximum numbers of search steps and restarts for each run,
inconsistency selection strategy, and noise factor), 
that can be modified by the user.
%
  The default initial value of the noise $p$ is 0.1. Note that 
  this is a dynamic value that is automatically increased/decreased by 
  the planner during search, depending on the variance of the number of 
  inconsistencies in the last $n$ search steps. In all our tests 
  $p$ was automatically increased if the variance did not change 
  significantly in the last 50 search steps. It was set to the initial
  default value otherwise.
%
The parameters $\mu_E$ and $\mu_T$ of the action evaluation function
were automatically set using the (linear) plan metric specified
in the problem formalization.
In particular, $\mu_E$ was set to 1, while $\mu_T$ was set to the
coefficient weighing the {\tt total-time} variable in the expression
specifying the plan metric.
%
  For instance, in the example of plan metric given at the end of 
  Section 2, the coefficient weighing {\tt total-time} is 4, and 
  so for that problem $\mu_T$ was set to 4.
%
If no plan metric was specified, then $\mu_E$ was set to 0.5 and 
$\mu_T$ to 0. 

%

\begin{figure}[t]
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/DriverLog-Strips-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/ZenoTravel-SimpleTime-speed.ps}   \\
\end{tabular}

\begin{tabular}{cc}
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/Satellite-Complex-speed.ps} & 
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/Rovers-Numeric-speed.ps} 
\end{tabular}
\caption{ \label{fig:LPG-vs-competitors-speed}
CPU-time and number of problems solved by the fully-automated planners
of the 3rd IPC for the domains {\tt DriverLog} Strips, {\tt
ZenoTravel} SimpleTime, {\tt Satellite} Complex and
{\tt Rovers} Numeric.  }
\end{figure}

The performance of {\sc lpg} was tested in terms of both CPU-time
required to find a solution ({\sc lpg}-speed) and quality of the best
plan computed ({\sc lpg}-quality) using at most five CPU-minutes.  
In the plots of Figures \ref{fig:LPG-vs-competitors-speed},
\ref{fig:LPG-vs-competitors-quality},
\ref{fig:LPG-vs-SuperPlanner-Sat-Strips-SimpleTime-Time} and
\ref{fig:LPG-vs-SuperPlanner-Sat-Complex-Numeric}, on the x-axis we
have the problem names (simplified with numbers); on the y-axis, in
the plots for CPU-time we have milliseconds (logarithmic scale),
while in the plots for plan quality we have the quality of the
plans generated, measured using the plan metric expression in the
corresponding problem specification. Note that the lower the plan
quality values, the better the corresponding plans are.


\begin{figure}[t]
\begin{tabular}{cc}
\hspace{-9mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/DriverLog-Strips-length.ps} & 
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/ZenoTravel-SimpleTime-quality-gp.ps} \\
\end{tabular}

%
\begin{tabular}{cc}
\hspace{-9mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/Satellite-Complex-quality-gp.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/Rovers-Numeric-quality-gp.ps} 
\end{tabular}
\caption{ \label{fig:LPG-vs-competitors-quality}
Quality of plans computed by the fully-automated planners
of the 3rd IPC for the domains {\tt DriverLog} Strips, {\tt
ZenoTravel} SimpleTime, {\tt Satellite} Complex, {\tt Depots} Time and
{\tt Rovers} Numeric. In order to improve readability, the plot for
{\tt DriverLog-Strips} is given in logarithmic scale.}
\end{figure}

Figure \ref{fig:LPG-vs-competitors-speed} shows the performance of
{\sc lpg}-speed compared to the other competitors in some variants of
four domains.\footnote{Complete results for all other domains and variants are
available from {\tt http://prometeo.ing.unibs.it/ lpg/test-results}.}  
In {\tt DriverLog} Strips, {\sc ff} is on average the fastest planner,
but {\sc lpg} solves more problems, and it scales up somewhat better.
In {\tt ZenoTravel} SimpleTime, {\sc lpg} outperforms the other
competitors in terms of both number of problems solved and CPU-time
(our planner is about one order of magnitude faster).  In {\tt
Satellite} Complex the excellent performance of {\sc lpg} is even more
evident especially for the largest problems.
Finally, in {\tt Rovers} Numeric, {\sc ff} and {\sc lpg} perform
similarly, but our planner solves a larger number of problems.  The
plots concerning the performance of {\sc lpg}-quality for these four
domain variants are given in Figure \ref{fig:LPG-vs-competitors-quality}.
These results show that the solution computed by our
planner was always similar to or better than the solution derived by
any of the other planners. The most interesting differences are in {\tt
Satellite} Complex, where {\sc lpg}-quality produced solutions of
higher quality for almost every problem.

In order to derive some general results about the performance of our
approach with respect to all other fully-automated planners of the
competition, we compared {\sc lpg} with the best result over {\em all}
these planners.  We will indicate these results as if they were
produced by a hypothetical ``SuperPlanner'' (which does not
exist). Clearly, if {\sc lpg} performs generally better than the
SuperPlanner in a certain domain, then in that domain it performs
better than {\em any} other real planner that we considered. On the
other hand, if it performs worse, this does not necessarily imply that
there is a single real planner that generally performs better than
{\sc lpg}.

The plots of Figures
\ref{fig:LPG-vs-SuperPlanner-Sat-Strips-SimpleTime-Time} and
\ref{fig:LPG-vs-SuperPlanner-Sat-Complex-Numeric} give complete
results for {\tt Satellite}, one of the domains where our planner
performed particularly well in the temporal and Complex variants.  
The plots on the left show CPU-times for {\sc lpg}-speed, {\sc
lpg}-quality, and the two corresponding versions of the SuperPlanner:
a version in which, for each problem, we consider the fastest planner
over all the other fully-automated planners, and a version
in which we consider the planner that produced the best quality plan (of
course it can be the case that the fastest planner for a problem is
different from the planner that produces the best quality solution for
that problem). The plots on the right show plan quality for the
two versions of {\sc lpg} and the SuperPlanner.

\begin{figure}
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-Strips-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-Strips-length.ps} \\
\end{tabular}

\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-SimpleTime-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-SimpleTime-quality-gp.ps} \\
\end{tabular}

\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-Time-quality-gp.ps} \\
\end{tabular}

\caption{ \label{fig:LPG-vs-SuperPlanner-Sat-Strips-SimpleTime-Time}
Performance of {\sc lpg}-speed (left plots) and {\sc lpg}-quality (right
plots) compared with the SuperPlanner (speed and quality versions)  in 
{\tt Satellite} Strips, SimpleTime and Time.
}
\end{figure}

\begin{figure}[t]
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-Complex-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-Complex-quality-gp.ps} \\
\end{tabular}

\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-Numeric-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-Numeric-quality-gp.ps} 
\end{tabular}
\caption{ \label{fig:LPG-vs-SuperPlanner-Sat-Complex-Numeric}
Performance of {\sc lpg}-speed (left plots) and {\sc lpg}-quality (right
plots) compared with the SuperPlanner (speed and quality versions) 
in {\tt Satellite} Complex and Numeric.}
\end{figure}
  
The results in these and in the following plots are mostly self
explanatory. In the temporal and complex variants {\sc lpg}-speed is
often one or more orders of magnitude faster than the SuperPlanner. 
In the Strips variant the SuperPlanner is faster for the smallest problems,
but it is generally slower for the largest ones.
In the Numeric variant the SuperPlanner is faster, but our planner
produces solutions of better quality.  Regarding {\sc
lpg}-quality, in all variants except {\tt Satellite} Strips our
planner performs much better than the SuperPlanner.  In the
Strips variant, the quality of the plans produced by {\sc lpg}-quality 
is approximately the same as the quality of the plans generated
by the SuperPlanner.

%
\begin{figure}[t]
\begin{tabular}{cc}
%
\hspace{-7mm}
\includegraphics[angle=-90,width=0.52\textwidth]{Graphs-journal2-new/qualita-tempo/Satellite-SimpleTime-pfile15.ps} & 
\hspace{-7mm}
\includegraphics[angle=-90,width=0.52\textwidth]{Graphs-journal2-new/qualita-tempo/Satellite-Time-pfile6.ps} \\
\end{tabular}

\begin{tabular}{cc}
%
\hspace{-7mm}
\includegraphics[angle=-90,width=0.52\textwidth]{Graphs-journal2-new/qualita-tempo/Satellite-Strips-pfile9.ps} &
\hspace{-7mm}
\includegraphics[angle=-90,width=0.52\textwidth]{Graphs-journal2-new/qualita-tempo/Satellite-Numeric-pfile3.ps}   \\

\end{tabular}
\caption{ 
\label{fig:LPG-incremental-sols}
Plan quality and the corresponding CPU-milliseconds (logarithmic scale)
for the solutions found by {\sc lpg} (five runs) and the SuperPlanner
for four problems in {\tt Satellite} Strips, SimpleTime, Time and
Numeric.  }
\end{figure}

%
Concerning the quality of the solutions computed by {\sc lpg}-speed
and the CPU-time required by {\sc lpg}-quality, as we have described
in Section \ref{sec:incremental-quality}, it is important to note that
{\sc lpg} produces additional intermediate solutions, that for clarity
are not shown in these plots. It is not surprising that very often
plan quality for {\sc lpg}-speed is poor with respect to plan quality
for {\sc lpg}-quality, and that the CPU-time required by {\sc
lpg}-quality is much higher that the CPU-time required by {\sc
lpg}-speed.  Things become less clear if we compare plan quality for
{\sc lpg}-speed (or CPU-time for {\sc lpg}-quality) and plan quality for
the speed version of the SuperPlanner (or CPU-time for the quality version
of the SuperPlanner). 

Given the any time nature of {\sc lpg}, obviously there is a tradeoff
between plan quality and speed. The more CPU-time the planner is
allowed to run, the better the last solution generated. If we want
to study this tradeoff experimentally, we need to consider not only
the first and last solutions that {\sc lpg} found in the competition
tests, but also the intermediate solutions.  In fact, we observed that
in several cases {\sc lpg} generates an intermediate solution that has
quality better than or similar to the quality of the best plan
generated by the SuperPlanner, {\em and} that requires less or no more
CPU-time than the SuperPlanner. In Figure
\ref{fig:LPG-incremental-sols} we give some support to our claim (a
detailed analysis of all intermediate solutions generated by our
planner is beyond the scope of this paper).
%
The plots in this figure show CPU-time and quality of all plans
generated by {\sc lpg} (five runs) and by the SuperPlanner for some
problems in the {\tt Satellite} domain.  In {\tt
Satellite-SimpleTime-pfile15} and {\tt Satellite-Time-pfile6} (first
two plots of Figure \ref{fig:LPG-incremental-sols}) {\sc lpg}'s first
solutions ({\sc lpg}-speed) require less CPU-time than the first
solution found by the SuperPlanner. On the other hand, the quality 
of {\sc lpg}-speed's solutions are worse than the quality of the 
solution found by the speed version of the SuperPlanner (see also the
corresponding plots of Figure
\ref{fig:LPG-vs-SuperPlanner-Sat-Strips-SimpleTime-Time}, keeping in
mind that they are derived from median values over five
runs). However, Figure \ref{fig:LPG-incremental-sols} shows that for 
these two problems {\sc lpg}-speed generates additional intermediate solutions
that have quality better than the solutions found by the SuperPlanner,
and that still require less CPU-time.  
%
Moreover, the third and fourth plots of Figure
\ref{fig:LPG-incremental-sols} show that in {\tt
Satellite-Strips-pfile9} and {\tt Satellite-Numeric-pfile3} the
SuperPlanner is faster than {\sc lpg}-speed, but {\sc lpg} finds
intermediate solutions of quality better than the best solution of the
SuperPlanner using less CPU-time than the SuperPlanner and {\sc
lpg}-quality.

%
Since our main focus in this paper is temporal planning, it is
interesting to compare {\sc lpg} and the SuperPlanner in the Time
variant of all competition domains. The detailed results of this
comparison are given in Appendix B. As shown by the plots in this
appendix, {\sc lpg}-speed is usually faster than the SuperPlanner, 
and it always solves a larger number of problems, except in {\tt
ZenoTravel}, where our planner solves one problem less than the
SuperPlanner. This problem was solved by {\sc mips}, another 
planner of the 3rd IPC that performed well in the temporal 
domains \cite{Edelkamp-WSAIPS02}.
The percentage of the problems solved by {\sc lpg}-speed is 95.1\%,
while those solved by the SuperPlanner is 77.5\%.  The percentage of
the problems in which our planner is faster is 81.4\%, the percentage
in which it is slower is 13.7\%.

Regarding {\sc lpg}-quality, generally in these domains the quality
of the best plans produced by our planner is similar to the quality of
the plans generated by the SuperPlanner, with some significant
differences in {\tt ZenoTravel}, where in a few problems the
SuperPlanner performs better, and in {\tt Satellite}, where our
planner always performs better. Overall, in the Time variant of all
the domains the percentages of the problems in which our planner
produces a solution of better/worse quality are the same as the
percentages of the problems in which {\sc lpg}-speed is faster/slower.

We have also analyzed the performance of {\sc lpg} with respect to the
SuperPlanner for all other domains and problems attempted.
Appendices C and D give summary results.\footnote{
  The paper in this issue by Long and Fox \citeyear{LonFox:JAIR03} presents 
  a detailed statistical analysis of all official results of the 3rd IPC.}
As for the Time-problems, in the SimpleTime problems {\sc lpg} solves
more problems than the SuperPlanner, and the percentages of problems
in which {\sc lpg}-speed and {\sc lpg}-quality perform better than
SuperPlanner are even higher than the corresponding percentages for
the Time variants.  In the Numeric and Strips problems, on average
{\sc lpg}-speed is less efficient than the SuperPlanner. This is
mainly due to the generally good performance of {\sc ff} in these
domains.  However, note that {\sc lpg}-quality on average is better
than the SuperPlanner in every domain except the Strips version of
{\tt ZenoTravel}.
%

Overall, considering all problems attempted, {\sc lpg}-speed
performs better/worse than the SuperPlanner in 55.8/38.1\% 
of the problems, while {\sc lpg}-quality performs better/worse
in 71/11.6\% of the problems.

Finally, we ran our planner on some of the large problems that were
used to test the hand-coded planners in the 3rd IPC. In this
experiment {\sc lpg} was tested using a PC Pentium III, 500 MHz, with
1 Gbyte of RAM, which is more than two times slower than the machine
used for testing the hand-coded planners.  Of course, we did not
expect to solve these problems more efficiently than the hand-coded
planners. This experiment was aimed at testing how far we are from
planners exploiting domain knowledge.

\begin{figure}[t]
\begin{tabular}{cc}
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/Rovers-SimpleTime-HandCoded-speed.ps}
\hspace{-7mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/Rovers-SimpleTime-HandCoded-quality-gp.ps} &
\end{tabular}
%
\begin{tabular}{cc}
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/speed/Rovers-Time-HandCoded-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/mediana_alladv/quality/Rovers-Time-HandCoded-quality-gp.ps}
\end{tabular}
\caption{\label{fig:lpg-hand-coded}
Performance of {\sc lpg} in two temporal domains designed
for hand-coded planners competing at the 3rd IPC.
{\sc lpg} was tested on a machine that is more than two times
slower than the machine used to test the other planners.
}
\end{figure}
Figure \ref{fig:lpg-hand-coded} shows plots comparing the
performance of {\sc lpg} and the competing hand-coded planners for the
two temporal variants of {\tt Rovers}. {\sc lpg} solved 38 of the 40
problems attempted. 
In terms of plan quality, very often {\sc lpg}-quality generates plans
that are nearly as good as those computed by the hand-coded planners,
especially in {\tt Rovers-SimpleTime-} {\tt HandCoded}.
Interestingly, given that the machine used to test {\sc lpg} was slower,
in this domain {\sc lpg}-speed appears to perform slightly
better than {\sc shop\small 2} \cite{Nau-et-al03}.
%
In {\tt Rovers-Time-HandCoded} {\sc lpg}-speed can solve most of the
problems, but it does not perform as well. It remains an open question
whether further research can reduce this gap significantly, but we
are optimistic about this.

\section{Conclusions and Future Work}
%
We have presented some new techniques for planning in {\sc pddl\small
2.1} domains that are implemented in {\sc lpg}, an incremental
(any time) planner producing multi-criteria quality plans.
%
{\sc lpg} was given an award for ``distinguished
performance of the first order'' at the 3rd International Planning
Competition, and additional experimental results presented in this
paper give further evidence of the high performance of our system.

Other related techniques that are implemented in {\sc lpg}, but 
not described here, concern: the restriction of the
search neighborhood when it contains many elements, and their
evaluation can slow down the search excessively; different strategies
to choose the inconsistency to handle at each search step; 
the use of Lagrange multipliers in the action evaluation function
\cite{GerSerAIPS02,GerSer:constraints-03}.

We have already mentioned some directions that we are pursuing
to improve our system. These include, in particular, an extension of 
our algorithm for computing reachability information taking account 
of numerical preconditions and goals (a recent related method has 
been proposed by Hoffmann \citeyear{Hof03}).
In addition, we intend to test other local search strategies for
action graphs based on the use of a ``tabu list'' \cite{GerSer99},
and further types of graph modifications, some of which were
implemented in the previous version of {\sc lpg} \cite{GerSerAIPS02}.
This might be especially important for improving the incremental
plan-quality process.  Another possible improvement of this process
that is worth investigating is the use of dynamic coefficients to
weigh the terms of the action evaluation function. When we start a
new search for a plan of better quality, the weights of the terms
representing the execution and temporal costs could be increased with
respect to the term representing the search cost.
%
This could guide the search towards plans better than those already
derived, which is the purpose of the incremental process. 

Finally, other directions for improving temporal planning in {\sc lpg}
concern the treatment of a richer temporal representation to handle
upper and lower bounds on the possible action durations, as well as
the integration of temporal reasoning techniques to deal with temporal
constraints between actions similar to those that can be stated using
Allen's Interval Algebra \cite{Allen83} or STP-constraints
\cite{Dechter91}.

%
\section*{Acknowledgments}
\vspace{-0.15cm}

The development of {\sc lpg} has been carried out with the valuable
support of several undergraduate students. Their help in the
implementation and testing of {\sc lpg}, before and during the
competition in Toulouse, was very important.  We would like to thank
especially Marco Lazzaroni and Sergio Spinoni. Thanks also to Fabrizio
Morbini, Valerio Lorini, and Stefano Orlandi for their support during
the competition, and to all students of the AI class at the University
of Brescia who made a contribution to this project.  Finally,
thanks to Maria Fox and Derek Long for their hard work in the
organization of the 3rd IPC, to J\"org Hoffmann who made the source
code of {\sc ff} available (the parser and some data structures in
{\sc lpg} are based on extensions of J\"org's code), and to David
Smith and the anonymous reviewers for their helpful comments.

\newpage
\section*{Appendix A: Mutex Relations in LPG and Related Work}

\begin{figure} %

{\sf  ComputeMutexFacts}($I, {\cal O}$) 
\begin{description}
\vspace*{-.2cm}
\item
\emph{Input}: An initial state ($I$) and all ground operator instances 
(${\cal O}$); 
\vspace*{-.35cm}
\item 
\emph{Output}: A set of persistent mutex relations between facts  ($M$).
\end{description}
%
 
\begin{tabbing}
1 ~ $F^* \, \gets I$;    $F    \, \gets  \emptyset $;           \\
2.~ $M \, \gets \emptyset; \;  M^* \, \gets \emptyset $; $ A\, \gets  \emptyset $; \\ 
3.~ \textbf{while} $F^* \, \neq F \vee M^* \neq M$ \\
4.  ~~~~~\= $F \gets F^*$;  $M \gets M^*$; \\
5.      \> \textbf{forall} $a \in$ ${\cal O}$ such that $Pre(a) \subseteq F^*$ 
           and $\neg ( \exists \, p,\, q \in Pre(a) \wedge (p,\,q) \in M^*)$  \\
6.  \> ~~~~~~\= $ New(a) \gets Add(a) - F^*$;\\
7.  \>\> \textbf{forall} $f \in New(a)$  \\
8.  \>\> ~~~~~\= \textbf{forall} $h \in Del(a)$ \\
9. \>\>\>~~~~~\= $M^* \gets M^* \cup \{(f,\,h),(h,\,f)\}$; ~~~~/* Potential mutex relation */ \\ 
10. \>\>\> \textbf{forall} $(p,\,q) \in M^*$ such that  $ p \in Pre(a)$ 
                           and $q \not \in Del(a)$ \\
11. \>\>\>\>  $ M^* \gets M^* \cup  \{(f,\,q),(q,\,f)\}$; ~~~~/* Potential mutex relation */ \\
12. \>\> \textbf{if} $a \not \in A$ \textbf{then}\\ 
13. \>\>\>  \textbf{forall} $ p,\,q \in Add(a)$ such that $(p,\,q) \in M^*$  \\
14. \>\>\>\>  $ M^* \gets M^* - \{(p,\,q),(q,\,p)\}$; ~~~~/* Invalid mutex relation */\\ 
15. \>\> $ L \gets Add(a) - New(a)$;\\
16. \>\> \textbf{forall} $(i,\,q) \in M^*$ such that $i \in L$ \\
17. \>\>\> \textbf{if}  $q \notin Del(a) \wedge \neg ( \exists \, p \in Pre(a) \wedge (p,\,q) \in M^*$)  \textbf{then} \\
18. \>\>\>\> $ M^* \gets M^* - \{(i,\,q),(q,\,i)\}$; ~~~~/* Invalid mutex relation */ \\
19. \>\> $F^* \gets F^* \cup  New(a)$; \\
20. \>\>  $ A\, \gets A \cup \{a\}$;\\
21. \textbf{return} $M$.
\end{tabbing}
%


\vspace{0.4cm}
{\sf ComputeMutexActions}($M, {\cal O}$) 
\begin{description}
\item
\vspace*{-.2cm}
\emph{Input}: 
A set of mutex relations between facts ($M$) and all ground operator
instances (${\cal O}$);
%
%
\item 
\vspace*{-.35cm}
\emph{Output}: 
A set of persistent mutex relations between actions  ($N$). 
\end{description}
%
\begin{tabbing}
1.~ $N \, \gets \emptyset$; ${\cal O}^*$ $\assign$ ${\cal O}$ extended 
with the no-op of every fact; \\
2.~ \textbf{forall} $(p,\,q) \in M$ \\
3.~ ~~~~\= \textbf{forall} $a \in$ ${\cal O}^*$  such that $p \in Pre(a)$\\
4.~ \>~~~~\= \textbf{forall} $b \in$  ${\cal O}^*$ such that $q \in Pre(b)$\\
5.~ \>\>~~~~\= $N \gets N \cup \{(a,\,b),(b,\,a)\}$; ~~~~ /* Competing needs */ \\
6.~ \textbf{forall}  $ a \in$ ${\cal O}^* $ \\
7.~ \> \textbf{forall} $p \in Pre(a)$\\
8.~ \>\> \textbf{forall} $b \in$ ${\cal O}$  such that $p \in Del(b)$\\
9.~ \>\>\> $N \gets N \cup \{(a,\,b),(b,\,a)\}$;  ~~~~ /* Interference */\\
10.~ \> \textbf{forall} $p \in Add(a)$\\
11.~ \>\> \textbf{forall} $b \in$  ${\cal O}$ such that $p \in Del(b)$\\
12.~ \>\>\> $N \gets N \cup \{(a,\,b),(b,\,a)\}$;  ~~~~ /* Inconsistent
effects */ \\
%
13.~ \textbf{return} $N$.
\end{tabbing}

\caption{\label{fig:mutex}
{\sc lpg}'s algorithms for computing the mutex relations. 
} 
\end{figure} 


{\sc lpg} precomputes a set of mutex relations for the input planning
problem using the two algorithms given in Figure \ref{fig:mutex},
where $Add(a)$ denotes the set of the positive effects of $a$,
$Del(a)$ the set of its negative effects, and $Pre(a)$ the set of its
preconditions.  {\sf ComputeMutexFacts} derives a set of mutex
relations between facts, that are used by {\sf ComputeMutexActions} to
compute a set of relations between actions.  The correctness of this
second algorithm is obvious since it just applies the original
definition of mutex relation \cite{BluFur95}.

{\sf ComputeMutexFacts} iteratively constructs a set $M$ of {\em
potential} mutex relations and the set $F$ of all possible facts for
the planning problem under consideration. At each iteration we
consider every possible action $a$ (step 5) to possibly
generate a set of new potential mutex relations (steps 7--11), and to
possibly invalidate other potential mutex relations that have already 
been formulated (steps 12--18). The algorithm terminates when all
possible facts have been considered ($F^* = F$), and no new potential
mutex relations can be generated ($M^* = M$).  When the algorithm 
terminates, $M$ contains a set of persistent mutex relations between facts. 
A mutex relation $m$ in $M$ is {\em persistent} if there is no state that 
can be reached from the initial state of the problem, using the operators 
of the domain under consideration, in which the facts of $m$ are both
true. All mutex relations in the fixed-point level of a traditional 
planning graph are persistent.

Given an action $a$, two facts $f_1$ and $f_2$ form a potential mutex
relation $m$ if (1) one of them is a positive effect of $a$ and the
other is a negative effect (steps 7--9), or (2) one of them is a
positive effect of $a$ and the other is (potentially) mutually
exclusive with a precondition of $a$ (steps 7, 10 and 11). (1) is a
natural way of hypothesizing mutex relations that is used also by
Gerevini and Schubert \citeyear{GerSch98}. (2) is based on the
observation that, if $f_1$ is an effect of $a$, $p \in Pre(a)$, $f_2
\not \in Add(a)$, and $f_2$ is mutually exclusive with $p$, then in
any state resulting from the application of $a$ to a reachable state,
$f_2$ and $f_1$ cannot be both true.
%

A potential mutex relation $m \in M$ between $f_1$ and $f_2$ becomes
invalid if (1) there exists an action containing the two facts of $m$
among its positive effects (steps 13--14), or $f_1$ ($f_2$) is an
add-effect of an action $a$, $f_2$ ($f_1$) is not deleted by $a$, and
$f_2$ ($f_1$) is (potentially) mutually exclusive with no precondition
of $a$ (steps 15--18). The first case if obvious, while the second can
be explained as follows.  If $f_1$ is a positive effect of $a$, and we
cannot exclude that $f_2$ is true in a state where $a$ can be applied,
then $f_2$ could persist from this state to the state produced by $a$
(similarly if $f_2$ is a positive effect of $a$).

Note that {\sc lpg} handles negative preconditions as proposed by
Koehler {\em et al.} \citeyear{Koe-et-al97-TechRep}, i.e., no
explicit atomic negation is available in {\sc lpg}'s language. Instead
we model atomic negation by introducing an additional predicate {\em
not-}$p(x)$ if $\neg p(x)$ is needed and by formulating add and delete
effects correspondingly (this guarantees than {\em not-}$p(x)$ and
$p(x)$ are mutex).

The next theorem states the correctness of our algorithms.

\vspace{0.2cm}

\noindent
%
{\bf Theorem} {\em 
{\sf ComputeMutexFacts} and {\sf ComputeMutexActions} correctly
compute a set of persistent mutex relations between facts and 
actions respectively.}
%

\vspace{0.2cm}

\noindent
{\bf Proof}. Correctness of {\sf ComputeMutexActions} is obvious,
since it is a direct consequence of the definition of persistent mutex
relation between actions. Correctness of {\sf ComputeMutexFacts} follows from
the two conditions under which a potential mutex relation is made
invalid by the algorithm, and it can be proved by an inductive
argument on the number $k$ of actions applied to reach a state $S$
from the initial state.

\noindent
{\em Induction base ($k = 0$)}. It is easy to see that each element $m$
in the output set $M$ is a valid mutex relation for the initial state
($S = I$), because the algorithm cannot formulate mutex relations
involving two facts that are both true in the initial state.

\noindent
{\em Induction hypothesis ($k = n$)}. Suppose that any element $m$
in the output set $M$ is a valid mutex relation in any state reached 
by the application of $n$ actions ($n \geq 1$).

\noindent
{\em Induction step ($k = n+1$)}. Assume that there exists an element
$m$ in the output set $M$ that is not a valid mutex relation in a
state $S$ reachable by applying a sequence of $n+1$ actions (because
the two facts $f_1$ and $f_2$ of $m$ are both true in $S$), and let
$a_{n+1}$ be the last action in this sequence. 
By the inductive assumption this can happen only if (i) $f_1$ and
$f_2$ are both positive effects of $a_{n+1}$, or (ii) $f_1$ ($f_2$) is
an add-effect of $a_{n+1}$, $f_2$ ($f_1$) is not deleted by $a_{n+1}$,
and $f_2$ ($f_1$) is true in the state $S'$ where $a_{n+1}$ is applied.  
Case (i) is ruled out by steps 13--14 of {\sf ComputeMutexActions}.
Regarding case (ii), since we are assuming that $S'$ is a reachable
(consistent) state where $f_2$ ($f_1$) is true and $a_{n+1}$ can be
applied, there must exist no precondition $p$ of $a_{n+1}$ that is mutex 
with $f_2$ ($f_1$). Moreover, by the inductive assumption $(p,f_2)$
($(p,f_1)$) cannot belong to the output $M$-set -- if some iteration of
the algorithm adds the potential mutex relation between $p$ and $f_2$
($f_1$) to $M$, then it must be the case that it is then removed from
$M$.  It follows that, if some iteration adds $(f_1,f_2)$ to $M$,
steps 16--18 will then remove it from $M$,
contrary to our assumption that $m$ belongs to the output $M$-set.

Termination of the two algorithms is guaranteed because there is always 
a finite maximum number of different facts, actions and potential mutex 
relations. $\Box$

%

\vspace{0.3cm} 

Smith and Weld proposed the notion of ``eternal mutex'' ({\em emutex})
as a mutex relation that persists for all time \cite{Weld-IJCAI99-tgp}.  
According to their definition of emutex, our persistent mutex
relations between facts and between actions subsume theirs. Concerning
emutex relations between an action and a fact, Smith and Weld consider
an action $a$ with effect $p$ emutex with a fact $p$, while we do not
consider $a$ and {\em no-op($p$)} persistently mutex.

Bonet and Geffner \citeyear{Geffner-AI01} proposed a method for
deriving a set of mutex relations between facts that has some
similarities with ours. Both methods are based on hypothesizing a set
of pairs of mutex facts that are then possibly eliminated from the set
according to certain conditions on the preconditions and effects of the
actions. However, there are also some significant differences. While
Bonet and Geffner compute an initial large set $M_0$ of candidate
mutex pairs, and then prune it, {\sf ComputeMutexFacts} incrementally 
constructs and verifies the set $M$ through a forward process. 
The conditions under which a pair of facts is in $M_0$ are different 
 from the conditions used by {\sf ComputeMutexFacts} to create $M$
(especially the condition in step 10).  Moreover, our algorithm
generates and tests the pairs of $M$ considering only applicable
actions (i.e., actions with all preconditions in $F^*$ and with
non-mutex preconditions), while Bonet and Geffner derive $M_0$ using
every operator instance.  Finally, their paper does not contain
algorithmic details about the identification of ``bad pairs'' in $M_0$,
and there is no formal proof of correctness.

For problems involving a very high number of actions, precomputing
mutex relations could be computationally very expensive. In order to
cope with these cases, the user of {\sc lpg} can set an option of the
planner ({\tt lowmemory}) for computing the mutex relations between
actions at search time (while those between facts and between actions
and no-ops are still precomputed).  Preprocessing with {\tt lowmemory} 
on becomes faster and requires much less memory, but each
search step becomes slower.  For this reason in the current version of
{\sc lpg} this option is recommended only when the precomputation of
mutex relations between actions is prohibitive. This was never the
case for the test problems of the 3rd IPC designed for the fully-automated
planners, but for some of the problems designed for the hand-coded planners,
like those of the domain {\tt Satellite} Hand-Coded, the use of this
option is necessary. 
Currently we are studying an alternative method for computing
(persistent) mutex relations during search based on the use of state
invariants automatically derived by existing domain analysis tools,
such as {\sc Discoplan} \cite{GerSch98} or {\sc Tim} \cite{FoxLon98}.
A similar method has been proposed by Fox and Long \citeyear{FoxLon00}.

Finally, for domains involving numerical preconditions and effects, 
the set of mutex relations between actions computed by the algorithms 
of Figure \ref{fig:mutex} is extended using the definition of mutex 
relations for numeric domains given by Fox and Long \citeyear{FoxLon03:JAIR}.

%
\newpage
\section*{Appendix B: LPG and the SuperPlanner in the Time 
variant of the competition domains}

%

\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Depots-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Depots-Time-quality-gp.ps} \\
\end{tabular}

\vspace{-0.2cm}
\hspace{-7mm}
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/DriverLog-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/DriverLog-Time-quality-gp.ps} \\
\end{tabular}
%


\vspace{-0.2cm}
\hspace{-7mm}
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Rovers-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Rovers-Time-quality-gp.ps} \\
\end{tabular}

\newpage
\hspace{-7mm}
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/ZenoTravel-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/ZenoTravel-Time-quality-gp.ps} \\
\end{tabular}

\vspace{-0.2cm}
\hspace{-7mm}
\begin{tabular}{cc}
%
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/speed/Satellite-Time-speed.ps} &
\hspace{-10mm}
\includegraphics[angle=-90,width=0.54\textwidth]{Graphs-journal2-new/superspeed+superquality/quality/Satellite-Time-quality-gp.ps} \\
\end{tabular}

\newpage
\section*{Appendix C: Comparison of LPG-speed and the SuperPlanner}

The following table shows the performance of {\sc lpg}-speed and the
SuperPlanner in every variant of every domain tested using our local
search techniques. The two systems are compared in terms of: number of
problems solved (2nd and 3rd columns); number of problems in which
{\sc lpg}-speed is faster/slower than the SuperPlanner (4th/6th
columns); number of problems in which {\sc lpg}-speed is much
faster/slower than the SuperPlanner (5th/7th columns).  A system was
considered much faster than the other one when the CPU-time required
by the first was at least one order of magnitude lower than the
second. When a planner was not able to find a solution, the required
CPU-time was considered infinite.



\begin{center}
\small
\scriptsize
\vspace{1cm}
\begin{tabular}{| l | l | l | l | l | l | l |} \hline
{ }         & {Problems}   & {Problems}        & {LPG}    & {LPG much}       & {LPG }   & {LPG much}\\
{Domain }   & {solved}     & {solved by}       & {better then}   & {better then}      & {worse than}   & {worse than}\\
{ }         & {by }         & {the Super-}           & {the Super-}       & {the Super-}          & {the Super-}      & {the Super-}  \\
{ }         & {LPG}        & {Planner}         & {Planner}     & {Planner }       & {Planner}    & {Planner}  \\
\hline
\hline
{\bf{Strips}} & & & & & & \\
%
%
{\tt Depots}     & 22 (100\%)  & 22 (100\%) & 6 (27.3\%)  & 0 (0\%)     & 16 (72.7\%) & 5 (22.7\%) \\
{\tt DriverLog}  & 20 (100\%)  & 15 (75\%)  & 7 (35\%)   & 5 (25\%)    & 12 (60\%)   & 1 (5\%) \\
{\tt Rovers}     & 20 (100\%)  & 20 (100\%) & 4 (20\%)   & 0 (0\%)     & 14 (70\%)   & 3 (15\%) \\
{\tt Satellite}  & 20 (100\%)  & 20 (100\%) & 6 (30\%)   & 1 (5\%)     & 14 (70\%)   & 2 (10\%) \\
{\tt ZenoTravel} & 19 (95\%)   & 20 (100\%) & 0 (0\%)    & 0 (0\%)     & 20 (100\%)  & 12 (60\%) \\
\hline
{\tt Total}   &  99\%    &  95.1\%   & 22.5\%    &  5.9\%    &  74.5\%   & 22.5\% \\
\hline
\hline
{\bf{Simple-time}} & & & & & & \\
{\tt Depots}      & 21 (95.5\%)  & 11 (50\%)  & 18 (81.8\%) & 14 (63.6\%)  & 3 (13.6\%)   & 0 (0\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)  & 15 (75\%)   & 6 (30\%)     & 3 (15\%)     & 2 (10\%) \\
{\tt Rovers}      & 20 (100\%)   & 10 (50\%)  & 17 (85\%)   & 12 (60\%)    & 1 (5\%)      & 1 (5\%) \\
{\tt Satellite}   & 20 (100\%)   & 19 (95\%)  & 18 (90\%)   & 12 (60\%)    & 1 (5\%)      & 1 (5\%) \\
{\tt ZenoTravel}  & 19 (95\%)    & 16 (80\%)  & 18 (90\%)   & 9 (45\%)     & 1 (5\%)      & 0 (0\%) \\
\hline
{\tt Total}   & 96\%    &  70.6\%   & 83.4\%   & 51.9\%    & 8.8\%   & 3.9\%  \\
\hline
\hline
{\bf{Time}} & & & & & & \\
%
{\tt Depots}      & 20 (90.9\%)  & 11 (50\%)  & 14 (63.6\%) & 12 (54.5\%)   & 6 (27.3\%)   & 2 (9.1\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)  & 17 (85\%)   & 6 (30\%)      & 0 (0\%)      & 0 (0\%) \\
{\tt Rovers}      & 20 (100\%)   & 12 (60\%)  & 18 (90\%)   & 13 (65\%)     & 2 (10\%)     & 1 (5\%) \\
{\tt Satellite}   & 20 (100\%)   & 20 (100\%) & 19 (95\%)   & 12 (60\%)     & 1 (5\%)      & 0 (0\%) \\
{\tt ZenoTravel}  & 19 (95\%) & 20 (100\%) & 15 (75\%)    & 0 (0\%)      & 5 (25\%)     & 1 (5\%) \\
\hline
{\tt Total}   &  95.1\%    & 77.5\%    & 81.4\%  & 42.1\%   & 13.7\%  & 3.9\% \\
\hline
\hline
{\bf{Numeric}} & & & & & & \\
%
{\tt Depots}      & 21 (95.5\%)  & 20 (90.9\%) & 8 (36.4\%)& 2 (9.1\%)    & 12 (54.5\%) & 2 (9.1\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)   & 7 (35\%)  & 3 (15\%)     & 10 (50\%)   & 3 (15\%) \\
{\tt Rovers}      & 17 (85\%)    & 9 (45\%)    & 10 (50\%) & 8 (40\%)     & 7 (35\%)    & 3 (15\%) \\
{\tt Satellite}   & 12 (60\%)    & 14 (70\%)   & 2 (10\%)  & 2 (10\%)     & 14 (70\%)   & 5 (25\%) \\
{\tt ZenoTravel}  & 20 (100\%)   & 20 (100\%)  & 0 (0\%)   & 0 (0\%)      & 20 (100\%)  & 5 (25\%) \\
\hline
{\tt Total}   & 83.6\%    &  77.4\%  & 26.4\%  &  14.7\%  & 61.8\%  & 17.6\% \\
\hline
\hline
{\bf{Complex}} & & & & & & \\
%
{\tt Satellite}     & 20 (100\%)  & 17 (85\%) & 19 (95\%)  & 14 (70\%)    & 1 (5\%)      & 1 (5\%) \\
\hline
\hline
{\bf{Hard-numeric}} & & & & & & \\
%
{\tt DriverLog} & 20 (100\%) & 16 (80\%)  & 12 (60\%) & 5 (25\%)& 8 (40\%) & 2 (10\%) \\
\hline
\hline
{\tt Total}   &  94.6\%    &  80.3\%   & 55.8\%   & 30.3\%    & 38.1\%   & 11.6\%  \\
\hline
\end{tabular}
%
\end{center}
%

\newpage
\section*{Appendix D: Comparison of LPG-quality and the SuperPlanner}

The following table shows the performance of {\sc lpg}-quality and the
SuperPlanner in every variant of every domain tested using our local
search techniques. The two systems are compared in terms of: number of
problems solved (2nd and 3rd columns); number of problems in which the quality
of the solution computed by {\sc lpg} is better/worse than the
solution computed by the SuperPlanner (4th/6th columns); number of problems in
which the solution of {\sc lpg}-quality is much better/worse than the
solution of the SuperPlanner (5th/7th columns).  A solution $\pi$
derived by a system is considered much better than the solution $\pi'$
for the same problem derived by the other system if the quality of
$\pi$ is at least twice as good as the quality of $\pi'$, or if 
$\pi$ exists and $\pi'$ does not exist (because the system could 
not solve the corresponding problem).
%
 The quality of a plan is measured using the plan metric indicated in
 the problem specification, except for the Strips problems, where plan
 quality is defined as the number of actions. In all problems considered, 
 the lower the value of the metric expression, the better the plan is.
%

%
\begin{center}
\scriptsize
%
%
\begin{tabular}{| l | l | l | l | l | l | l |} 
\hline
{ }         & {Problems}   & {Problems}        & {LPG }    & {LPG much}       & {LPG }   & {LPG much}\\
{Domain }   & {solved}     & {solved by}       & {better than}   & {better than}      & {worse than}   & {worse than}\\
{ }         & {by}         & {the Super-}           & {the Super-}       & {the Super-}          & {the Super-}      & {the Super-}  \\
{ }         & {LPG}        & {Planner}         & {Planner}     & {Planner }       & {Planner}    & {Planner}  \\
\hline
\hline
{\bf{STRIPS}} & & & & & & \\
%
%
{\tt Depots}     & 22 (100\%)  & 22 (100\%)  & 12 (54.5\%)& 0 (0\%)      & 4 (18.2\%)   & 0 (0\%) \\
{\tt DriverLog}  & 20 (100\%)  & 15 (75\%)   & 14 (70\%)  & 5 (25\%)     & 0 (0\%)     & 0 (0\%) \\
{\tt Rovers}     & 20 (100\%)  & 20 (100\%)  & 9 (45\%)   & 0 (0\%)      & 1 (5\%)     & 0 (0\%) \\
{\tt Satellite}  & 20 (100\%)  & 20 (100\%)  & 13 (65\%)  & 0 (0\%)      & 0 (0\%)    & 0 (0\%) \\
{\tt ZenoTravel} & 19 (95\%)   & 20 (100\%)  & 3 (15\%)   & 0 (0\%)      & 9 (45\%)    & 1 (5\%) \\
\hline
{\tt Total}   &   99\%  & 95.1\%     & 50\%  & 4.9\%   & 13.7\%  & 0.9\% \\
\hline
\hline
{\bf{Simple-time}} & & & & & & \\
%
{\tt Depots}      & 21 (95.5\%)  & 11 (50\%)  & 19 (86.4\%) & 11 (50\%)    & 1 (4.5\%)   & 0 (0\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)  & 17 (85\%)   & 3 (15\%)     & 1 (5\%)     & 0 (0\%) \\
{\tt Rovers}      & 20 (100\%)   & 10 (50\%)  & 20 (100\%)  & 10 (50\%)    & 0 (0\%)     & 0 (0\%) \\
{\tt Satellite}   & 20 (100\%)   & 19 (95\%)  & 20 (100\%)  & 7 (35\%)     & 0 (0\%)     & 0 (0\%) \\
{\tt ZenoTravel}  & 19 (95\%)    & 16 (80\%)  & 17 (85\%)   & 3 (15\%)     & 2 (10\%)    & 0 (0\%) \\
\hline
{\tt Total}   &  96\%    &  70.6\%   & 91.2\%   & 33.3\%    & 3.9\%   & 0\%  \\
\hline
\hline
{\bf{Time}} & & & & & & \\
%
{\tt Depots}      & 20 (90.9\%)  & 11 (50\%)  & 17 (77.3\%)  & 9 (40.9\%)   & 2 (9.1\%)    & 0 (0\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)  & 17 (85\%)    & 4 (20\%)     & 1 (5\%)      & 0 (0\%) \\
{\tt Rovers}      & 20 (100\%)   & 12 (60\%)  & 18 (90\%)    & 8 (40\%)     & 2 (10\%)     & 0 (0\%) \\
{\tt Satellite}   & 20 (100\%)   & 20 (100\%) & 20 (100\%)   & 5 (25\%)     & 0 (0\%)      & 0 (0\%) \\
{\tt ZenoTravel}  & 19 (95\%)    & 20 (100\%) & 11 (55\%)    & 0 (0\%)      & 9 (45\%)     & 3 (15\%) \\
\hline
{\tt Total}   &  95.1\%    &  77.4\%   & 81.4\%   & 25.5\%    & 13.7\%   & 2.9\%  \\
\hline
\hline
{\bf{Numeric}} & & & & & & \\
%
{\tt Depots}      & 21 (95.5\%)  & 20 (90.9\%) & 10 (45.5\%) & 1 (4.5\%)     & 8 (36.4\%) & 1 (4.5\%) \\
{\tt DriverLog}   & 18 (90\%)    & 16 (80\%)   & 15 (75\%)   & 2 (10\%)      & 0 (0\%)    & 0 (0\%) \\
{\tt Rovers}      & 17 (85\%)    & 9 (45\%)    & 8 (40\%)   & 8 (40\%)       & 0 (0\%)   & 0 (0\%) \\
{\tt Satellite}   & 12 (60\%)    & 14 (70\%)   & 12 (60\%)   & 7 (35\%)      & 4 (20\%)   & 4 (20\%) \\
{\tt ZenoTravel}  & 20 (100\%)   & 20 (100\%)  & 9 (45\%)    & 1 (5\%)       & 6 (30\%)   & 3 (15\%) \\
\hline
{\tt Total}   & 86.3\%    & 77.4\%   & 52.9\%  &  18.6\%  & 17.6\%  & 7.8\% \\
\hline
\hline
{\bf{Complex}} & & & & & & \\
%
{\tt Satellite}     & 20 (100\%)  & 17 (85\%)   & 19 (95\%) & 9 (45\%)     & 1 (5\%)    & 0 (0\%) \\
\hline
\hline
{\bf{Hard-numeric}} & & & & & & \\
%
{\tt DriverLog} & 20 (100\%) & 16 (80\%) & 18 (90\%) & 5 (25\%) & 1 (5\%) & 0 (0\%) \\
\hline
%\hline
\hline
{\tt Total}   & 94.6\%    &  80.3\%  & 71\%  & 21.9\%   & 11.6\%  & 2.7\% \\
\hline
\end{tabular}
%
\end{center}
%

\newpage
\bibliography{./biblio6}
\bibliographystyle{theapa}

%
\end{document}

