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

\def\und#1{\vspace*{0.1in}\noindent{\bf #1}}
\def\mvp{}
\def\Ignore#1{}
\newcommand{\fromrao}[1]{}
\def\altalt{{\sl AltAlt}}
\def\altaltp{{\sl AltAlt$^p$}}
\def\ap{\altaltp}
\def\ps{{\sl Pushup}}

\jairheading{19}{2003}{631-657}{10/02}{12/03}

\ShortHeadings{Online Parallelization of Plans with Heuristic
State Search}{Sanchez \& Kambhampati}

\firstpageno{631}

\begin{document}
\title{\ap: Online Parallelization of Plans with \\ Heuristic State
  Search}

\date{ASU CSE TR02-002}

%\begin{centering}
\author{\name Romeo Sanchez Nigenda \email rsanchez@asu.edu\\
\name Subbarao Kambhampati \email rao@asu.edu\\
\emph{Department of Computer Science and Engineering,}\\
\emph{Arizona State University, Tempe AZ 85287-5406}\\
}
\maketitle

\begin{abstract}
Despite their near dominance, heuristic state search planners still
lag behind disjunctive planners in the generation of parallel plans in
classical planning. The reason is that directly searching for parallel
solutions in state space planners would require the planners to branch
on all possible subsets of parallel actions, thus increasing the
branching factor exponentially. We present a variant of our heuristic state
search planner \altalt\, called \altaltp\ which generates parallel
plans by using greedy online parallelization of partial plans. The
greedy approach is significantly informed by the use of novel distance
heuristics that \altaltp\ derives from a graphplan-style planning
graph for the problem. While this approach is not guaranteed to
provide optimal parallel plans, empirical results show that \altaltp\
is capable of generating good quality parallel plans at a fraction of
the cost incurred by the disjunctive planners.
\end{abstract}

\section{Introduction}
\label{sec-intro}

Heuristic state space search planning has proved to be one of the
most efficient planning frameworks for solving large deterministic
planning problems~\cite{bonet97,bonet99,aips-00}. Despite its near
dominance, its one achilles heel remains generation of ``parallel
plans'' ~\cite{haslum00}.  Parallel plans allow concurrent
execution of multiple actions in each time step. Such concurrency
is likely to be more important as we progress to temporal domains.
While disjunctive planners such as Graphplan~\cite{blum97}
SATPLAN~\cite{satplan} and GP-CSP \cite{gp-csp} seem to have no
trouble generating such parallel plans, planners that search in
the space of states are overwhelmed by this task. The main reason
is that straightforward methods for generation of parallel plans
would involve progression or regression over sets of actions. This
increases the branching factor of the search space exponentially.
Given $n$ actions, the branching factor of a simple progression or
regression search is bounded by $n$, while that of progression or
regression search for parallel plans will be bounded by $2^n$.

The inability of state search planners in producing parallel plans
has been noted in the literature previously.  Past attempts to
overcome this limitation have not been very successful.  Indeed,
~\citeA{haslum00} consider the problem of generating parallel
plans using a regression search in the space of states. They note
that the resulting planner, HSP*p, scales significantly worse than
Graphplan. They present TP4 in~\cite{haslum01}, which in addition
to being aimed at actions with durations, also improves the
branching scheme of HSP*p, by making it incremental along the
lines of Graphplan. Empirical studies reported by
\citeA{haslum01}, however indicate that even this new approach,
unfortunately, scales quite poorly compared to Graphplan variants.
Informally, this achilles heel of heuristic state search planners
has been interpreted as a sort of last stand of the disjunctive
planners -- {\em only they are capable of generating parallel
plans efficiently}.

Given that the only way of efficiently generating optimal parallel
plans involves using disjunctive planners, we might want to
consider ways of generating near-optimal parallel plans using state
search planners. One obvious approach is to post-process the
sequential plans generated by the state search planners to make them
parallel. While this can easily be done - using approaches such as
those explored by~\citeA{backstrom98}, one drawback is that
such approaches are limited to transforming the sequential plan given
as input. Parallelization of sequential plans often results in plans
that are not close to optimal parallel plans.\footnote{We will
  empirically demonstrate this  later; curious readers may refer to
  the plots in  Figure~\ref{postprocessinglog-fig}.}

An alternative, that we explore in this paper, involves incremental
online parallelization. Specifically, our planner \altaltp, which is a
variant of the \altalt\ planner~\cite{altalt-kbcs,long-aaai2}, starts
its search in the space of regression over single actions. Once the
most promising single action to regress is selected, \altaltp\ then
attempts to parallelize (``fatten'') the selected search branch with
other independent actions. This parallelization is done in a greedy
incremental fashion - actions are considered for addition to the
current search branch based on the heuristic cost of the subgoals they
promise to achieve. The parallelization continues to the next step
only if the state resulting from the addition of the new action has a
better heuristic cost. The sub-optimality introduced by the greedy
nature of the parallelization is offset to some extent by a
plan-compression procedure called \ps\ that tries to rearrange
the evolving parallel plans by pushing up actions to higher levels in
the search branch (i.e. later stages of execution) in the plan.

Despite the seeming simplicity of our approach, it has proven to be
quite robust in practice. In fact, our experimental comparison with
five competing planners - STAN \cite{fox-graph}, LPG \cite{lpg02},
Blackbox \cite{satplan}, SAPA \cite{sapa} and TP4 \cite{haslum01} -
shows that \altaltp\ is a viable and
scalable alternative for generating parallel plans in several
domains. For many problems, \altaltp\ is able to generate parallel
plans that are close to optimal in makespan. \fromrao{We can't say
we are the only scalable one - since LPG also seems to scale..} It
also seems to retain the efficiency advantages of heuristic state
search over disjunctive planners, producing plans in a fraction of the
time taken by the disjunctive planners in many cases. \altaltp\ has
also been found to be superior to post-processing
approaches. Specifically, we compared \altaltp\ to an approach that
involves post-processing the sequential plans generated by \altalt\
using the techniques from~\citeA{backstrom98}. We found that
\altaltp\ is able to generate shorter parallel plans in many
cases. Finally, we show that \altaltp\ incurs very little additional
overhead compared to \altalt.

In the rest of this paper, we discuss the implementation and
evaluation of our  approach to generate parallel plans with
\altaltp. Section~\ref{sec-background} starts by providing a review
of the \altalt\ planning system, on which \altaltp\ is based.  Section~\ref{sec-algorithm} describes the
generation of parallel plans in \altaltp. Section~\ref{sec-eval} presents
extensive empirical evaluation of \ap. The evaluation includes both
comparison and ablation studies.  Finally,
Section~\ref{sec-rel} discusses some related work in classical as well
as metric temporal planning.
Section~\ref{sec-conc} summarizes our contributions.

\section{\altalt\ Background  Architecture and Heuristics}
\label{sec-background}

The \altalt\ planning system is based on a combination of
Graphplan~\cite{blum97,fox-graph,blackbox} and heuristic state
space search~\cite{bonet97,bonet99,mcd99} technology. \altalt\
extracts powerful heuristics from a planning graph data structure
to guide a regression search in the space of states. The high
level architecture of \altalt\ is shown in
Figure~\ref{altalt-fig}. The problem specification and the action
template description are first fed to a Graphplan-style
planner~\cite<in our case, STAN from>{fox-graph}, which constructs
a planning graph for that problem in polynomial time~\cite<we
assume the reader is familiar with the Graphplan algorithm
of>{blum97}. This planning graph structure is then fed to a
heuristic extractor module that is capable of extracting a variety
of effective heuristics ~\cite{long-aaai,long-aaai2}. These
heuristics, along with the problem specification, and the set of
ground actions in the final action level of the planning graph
structure are fed to a regression state-search planner.

\begin{figure}
\centerline{\epsfxsize=3.3in \epsfbox{altalt-arch.eps}}
\mvp
\caption{Architecture of \altalt}
\mvp
\label{altalt-fig}
\end{figure}

To explain the operation of \altalt\ at a more detailed level, we need
to provide some further background on its various components.  We
shall start with the regression search module. Regression search is a
process of searching in the space of potential plan suffixes. The
suffixes are generated by starting with the goal state and regressing
it over the set of relevant action instances from the domain. The
resulting states are then (non-deterministically) regressed again over
relevant action instances, and this process is repeated until we reach
a state (set of subgoals) which is satisfied by the initial state.  A
state $S$ in our framework is a set of (conjunction of) literals that
can be seen as ``subgoals'' that need to be made true on the way to
achieving the top level goals. An action instance $a$ is considered relevant to
a state $S$ if the effects of $a$ give at least one element of $S$ and
do not delete {\em any element} of $S$. The result of regressing $S$
over $a$ is then $(S \backslash eff(a)) \cup prec(a)$ - which is
essentially the set of goals that still need to be achieved before the
application of $a$, such that everything in $S$ would have been
achieved once $a$ is applied. For each relevant action $a$, a separate
search branch is generated, with the result of regressing $S$ over
that action as the new fringe in that branch. Search terminates with
success at a node if every literal in the state corresponding to that
node is present in the initial state of the problem.

The crux of controlling the regression search involves providing a
heuristic function that can estimate the relative goodness of the
states on the fringe of the current search tree and guide the search
in the most promising directions. The heuristic function
needs to evaluate the cost of achieving the set $S$ of subgoals (comprising a
regressed state) from the initial state. In other words, the heuristic computes the length of
the plan needed to achieve the subgoals from the initial state. We now discuss
how such a heuristic can be computed from the planning graph, which,
provides optimistic reachability estimates.

Normally, the planning graph data structure supports ``parallel''
plans - i.e., plans where at each step more than one action may be
executed simultaneously. Since we want the planning graph to provide
heuristics to the regression search module of \altalt, which generates sequential
solutions, we first make a modification to the algorithm so that it
generates a ``serial planning graph.''  A {\em serial planning graph} is
a planning graph in which, in addition to the normal mutex relations,
every pair of non-noop actions at the same level are marked
mutex. These additional action mutexes propagate to give additional propositional
mutexes. Finally, a planning graph is said to {\bf level off} when there
is no change in the action, proposition and mutex lists between two
consecutive levels.

We will assume for now that given a problem, the Graphplan module
of \altalt\ is used to generate and expand a serial planning graph
until it levels off. As discussed by~\citeA{altalt-kbcs}, we can
relax the requirement of growing the planning graph to level-off,
if we can tolerate a graded loss of informedness of heuristics
derived from the planning graph. We will start with the notion of
level of a set of propositions:

\newtheorem{level}{Definition}
\begin{level}[Level]
Given a set $S$ of propositions,  $lev(S)$ is the index of the
first level in the {\sl leveled serial} planning graph in which all
propositions in $S$ appear and are non-mutex with one another. If
$S$ is a singleton, then $lev(S)$ is just the index of the first level
where the singleton element occurs. If no such level exists, then
$lev(S) = \infty$ if the planning graph has been grown to level-off.
\end{level}

The intuition behind this definition is that the level of a literal
$p$ in the serial planning graph provides a lower bound on the length
of the plan (which, for a serial planning graph, is equal to the
number of actions in the plan) to achieve $p$ from the initial state.
Using this insight, a simple way of estimating the cost of a set of
subgoals will be to sum their levels.

\newtheorem{sum_heu}{Heuristic}
\begin{sum_heu}[Sum heuristic]
$h_{sum}(S) := \sum_{p \in S} lev(\{p\}) $
\end{sum_heu}

The sum heuristic is very similar to the greedy regression
heuristic used in UNPOP~\cite{mcd99} and the heuristic used in the
HSP planner~\cite{bonet97}. Its main limitation is that the
heuristic makes the implicit assumption that all the subgoals
(elements of $S$) are independent.  The $h_{sum}$ heuristic is
neither admissible nor particularly informed as it ignores the
interactions between the subgoals. To develop more effective
heuristics, we need to consider both positive and negative
interactions among subgoals in a limited fashion.

In \cite{long-aaai2}, we discuss a variety of ways of using the
planning graph to incorporate negative and positive interactions
into the heuristic estimate, and discuss their relative tradeoffs.
One of the best heuristics according to that analysis was a
heuristic called $h_{AdjSum2M}$. We adopted this heuristic as the
default heuristic in \altalt. The basic idea of $h_{AdjSum2M}$ is
to adjust the sum heuristic to take positive and negative
interactions into account. This heuristic approximates the cost of
achieving the subgoals in some set $S$ as the sum of the  cost of
achieving $S$, while considering positive interactions and
ignoring negative interactions, plus a penalty for ignoring the
negative interactions. The first component $RP(S)$ can be computed
as the length of a ``relaxed plan'' for supporting $S$, which is
extracted by  {\em ignoring all the mutex relations}. To
approximate the penalty induced by the negative interactions
alone, we proceed with the following argument. Consider any pair
of subgoals $p,q \in S$. If there are no negative interactions
between $p$ and $q$, then $lev(\{p,q\})$,  the level at which $p$
and $q$ are present together, is exactly the maximum of $lev(p)$
and $lev(q)$. The degree of negative interaction between $p$ and
$q$ can thus be quantified by:
\[
\delta(p,q) = lev(\{p,q\}) - max \left ( lev(p) , lev(q) \right )
\]
We now want to use the $\delta$ - values to characterize the amount of
negative interactions present among the subgoals of a given set
$S$. If all subgoals in $S$ are pair-wise independent, clearly, all
$\delta$ values will be zero, otherwise each pair of subgoals in $S$
will have a different value. The largest such $\delta$ value among any
pair of subgoals in $S$ is used  as a measure of the negative
interactions present in $S$ in the heuristic $h_{AdjSum2M}$. In
summary, we have

\newtheorem{adj}[sum_heu]{Heuristic}
\begin{adj}[Adjusted 2M]
$h_{AdjSum2M}(S):=length(RP(S))+max_{p,q \in S}\delta(p,q)$
\end{adj}

The analysis by \citeA{long-aaai2} shows that this is one of the
more robust heuristics in terms of both solution time and quality.
This is thus the default heuristic used in \altalt\ (as well as
\altaltp; see below).

\begin{figure}
\centerline{\epsfxsize=3.3in \epsfbox{altaltp-arch.eps}}
\mvp
\caption{Architecture of \altaltp}
\mvp
\label{altaltparch-fig}
\end{figure}

\begin{figure}
\centerline{\epsfxsize=4.0in \epsfbox{altpnotation.eps}} \mvp
\caption{\ap\ Notation} \mvp \label{overview-fig}
\end{figure}

\section{Generation of Parallel Plans Using \altaltp}
\label{sec-algorithm}

The obvious way to make \altalt\ produce parallel plans would involve
regressing over subsets of (non interfering) actions. Unfortunately,
this increases the branching factor exponentially and is infeasible
in practice. Instead,  \altaltp\ uses a greedy depth-first approach
that makes use of its heuristics to regress single actions, and
incrementally parallelizes the partial plan at each step, rearranging
the partial plan later if necessary.

The high level architecture of \altaltp\ is shown in Figure~\ref{altaltparch-fig}.
Notice that the heuristic extraction phase of \altaltp\ is very similar to
that of \altalt, but with one important modification. In
contrast to \altalt\ which uses a ``serial'' planning graph as the
basis for its heuristic (see Section~\ref{sec-background}), \altaltp\
uses the standard ``parallel'' planning graph.  This makes sense given
that \altaltp\ is interested in parallel plans while \altalt\ was
aimed at generating sequential plans. The regression state-search engine
for \altaltp\ is also different from the search module in \altalt. \altaltp\
augments the search engine of \altalt\ with 1) a fattening
step and 2) a plan compression procedure (\ps). The details of these
procedures are discussed below.

The general idea in \altaltp\ is to select a fringe action $a_p$
from among those actions $A$ used to regress a particular state
$S$ during any stage of the search (see
Figure~\ref{overview-fig}). Then, the pivot branch given by the
action $a_p$ is ``fattened'' by adding more actions from $A$,
generating a new state that is a consequence of regression over
multiple parallel actions. The candidate actions used for
fattening the pivot branch must (a) come from the sibling branches
of the pivot branch and (b)  be pairwise independent with all the
other actions currently in the pivot branch. We use the standard
definition of action independence: two actions $a_{1}$ and $a_{2}$
are considered independent  if the state $S'$ resulting after
regressing  both actions simultaneously is the same as that
obtained by applying $a_{1}$ and $a_{2}$ sequentially with any of
their possible linearizations. A sufficient condition for this is
that the preconditions and effects of the actions do not
interfere:

\[((|prec(a_{1})| \cup |eff(a_{1})|) \cap (|prec(a_{2})| \cup |eff(a_{2})|))=
\emptyset\] where \textbar L\textbar~refers to the non-negated
versions of the literals in the set L. We now discuss the details
of  how the pivot branch is selected in the first place, and how
the branch is incrementally fattened.

\begin{figure*}[t]
\centerline{
\begin{minipage} [b] {11.5cm}
\textbf{parexpand}(S) \\
\hspace*{0.5cm} A $\leftarrow$ \emph{get set of applicable actions for current state S} \\
\hspace*{0.5cm} \textbf{forall} $a_{i} \in A$ \\
\hspace*{1cm}   $S_{i} \leftarrow$ \emph{Regress($S$,$a_i$)} \\
\hspace*{1cm}   CHILDREN(S) $\leftarrow$ CHILDREN(S) + $S_{i}$ \\
\hspace*{0.5cm} $S_{p} \leftarrow$ \emph{The state among $Children(S)$
  with  minimum \\
\hspace*{0.5cm} $h_{\emph adjsum2M}$ value}\\
\hspace*{0.5cm} $a_{p} \leftarrow$ \emph{the action that regresses to $S_{p}$ from $S$}\\
\hspace*{3.5cm} /**Fattening process \\
\hspace*{0.5cm} $O \leftarrow$ \{ $a_{p}$ \} \\
\hspace*{0.5cm} \textbf{forall} $g \in S$ ranked in the decreasing order of $level(g)$  \\
\hspace*{1.5cm} Find an action $a_g \in A$ supporting $g$ such that $a_{g} \not\in O$ and \\
\hspace*{1.5cm} $a_{i}$ is pairwise independent with  each action in $O$. \\
\hspace*{1.5cm} If there are multiple such actions, pick the one which has \\
\hspace*{1.5cm} minimum $h_{adjsum}(Regress(S , O+a_{g}))$ among all $a_g \in A$ \\
\hspace*{1.5cm} If $h_{adjsum2M}(S,O+ a_i )  < h_{\emph adjsum2M}(S,O)$ \\
\hspace*{2cm}   $O \leftarrow O$ + $a_g$ \\
\hspace*{0.5cm} $S_{par} \leftarrow Regress(S, O)$ \\
\hspace*{0.5cm}   CHILDREN(S) $\leftarrow$ CHILDREN(S) + $S_{par}$ \\
\hspace*{0.5cm} \textbf{return} CHILDREN \\
\textbf{END};
\end{minipage}
}
\caption{Node Expansion Procedure}
\label{nodeExpansion-fig}
\end{figure*}

\begin{figure}
\centerline{\epsfxsize=4.0in \epsfbox{example1.eps}} \mvp
\caption{After the regression of a state, we can identify the
$Pivot$
  and the related set of pairwise independent actions.}
\mvp
\label{example1-fig}
\end{figure}

\paragraph{Selecting the Pivot Branch:}
Figure~\ref{nodeExpansion-fig} shows the procedure used to select
and parallelize the pivot branch.  The procedure first identifies
the set of regressable actions $A$ for the current node $S$, and
regresses each of them, computing the new children states. Next,
the action leading to the child state with the lowest heuristic
cost among the new children is selected as the pivot action
$a_{p}$, and the corresponding branch becomes the pivot branch.

The heuristic cost of the states is computed with the $h_{adjsum2M}$
heuristic from \altalt, based on a ``parallel'' planning graph.
Specifically, in the
context of the discussion of the $h_{adjsum2M}$ heuristic at the end of
Section~\ref{sec-background}, we compute the $\delta(p,q)$ values,
which in turn depend on the $level(p),level(q)$ and $level(p,q)$ in
terms of the levels in the parallel planning graph rather than the
serial planning graph. It is easy to show that the level of a set of
conditions on the parallel planning graph will be less than or equal
to the level on the serial planning graph. The length of the relaxed
plan is still computed in terms of number of actions. We show later
(see Figure~\ref{parallelserial-fig}(a)) that this change does improve
the quality of the parallel plans produced by \altaltp.

The search algorithm used in \ap\ is similar to that used in HSPr
\cite{bonet99} - it is a hybrid between greedy depth first and a
weighted A* search.  It goes depth-first as long as the heuristic
cost of any of the children states is lower than that of the
current state. Otherwise, the algorithm resorts to a weighted A*
search to select the next node to expand. In this latter case, the
evaluation function used to rank the nodes is  $f(S) =
g(S)+w*h(S)$ where $g(S)$ is the length of the current partial
plan in terms of number of steps, $h(S)$ is our estimated cost
given by the heuristic function (e.g. $h_{AdjSum2M}$), and $w$ is
the weight given to the heuristic function. $w$ is set to 5 based
on our empirical experience.\footnote{For the role of $w$ in
Best-First search see \cite{rkorf}.}

\noindent{\em Breaking Ties:} In case of a tie in selecting the
pivot branch, i.e., more than one branch leads to a state with the
lowest heuristic cost, we break the tie by choosing the action
that supports subgoals that are harder to achieve. Here, the
hardness of a literal $l$ is measured in terms of the level in the
planning graph at  which $l$ first appears. The standard rationale
for this decision \cite<c.f.>{rao-sanchez} is that we want to fail
faster by considering the most difficult subgoals first. We have
an additional justification in our case, we also know that a
subgoal with a higher level value requires more steps and actions
for its achievement because it appeared later into the planning
graph. So, by supporting it first, we may be able to achieve other
easier subgoals along the way and thereby reduce  the number of
parallel steps in our partial plan.

\paragraph{Fattening the Pivot Branch:}
Next the procedure needs to decide which subset $O \subseteq A$ of
the sibling actions of the pivot action $a_p$ will be used to
fatten the pivot branch. The obvious first idea would be to fatten
the pivot branch maximally by adding all pairwise independent
actions found during that search stage. The problem with this idea
is that it may add redundant and heuristically inferior actions to
the branch, and satisfying their preconditions may lead to an
increase of the number of parallel steps.

So, in order to avoid fattening the pivot branch with such
irrelevant actions, before adding any action $a$ to $O$, we {\em
require} that the heuristic cost of the state $S'$ that results
from regressing $S$ over $O + a$ be strictly lower than that of
$S$. This is in addition to the requirement that $a$ be pairwise
independent with the current set of actions in $O$. This simple
check also ensures that we do not add more than one action for
supporting the same set of subgoals in $S$.

The overall procedure for fattening the pivot branch thus involves
picking the next hardest subgoal $g$ in $S$ (with hardness
measured in terms of the level of the subgoal in the planning
graph), and finding the action $a_g \in A$ achieving $g$, which is
pair-wise independent of all actions in $O$ and which, when added
to $O$ and used to regress $S$, leads to a state $S'$ with the
lowest heuristic cost, which in consequence should be lower than
the cost of $S$. Once found, $a_g$ is then added to $O$, and the
procedure is repeated. If there is more than one action that can
be $a_{g}$, then we break ties by considering the degree of
overlap between the preconditions of action $a_g$ and the set of
actions currently in $O$. The degree of precondition overlap
between $a$ and $O$ is defined as $| prec(a) \cap \{ \cup_{o \in
O} prec(o)\}|$. The action $a$ with higher degree of overlap is
preferred as this will reduce the amount of additional work we
will need to do to establish its preconditions. Notice that
because of the fattening process, a search node may have multiple
actions leading to it from its parent, and multiple actions
leading from it to each of its children.

\und{Example:}
Figure~\ref{example1-fig} illustrates the use of this node expansion procedure
for a problem from the logistics domain~\cite{aips-00}.
In this example we have four packages {\tt
  pack1, pack2, pack3} and {\tt pack4}. Our goal is to place the first
three of them at {\tt ASU} and the remaining one at {\tt home}. There
are two planes {\tt airp1} and {\tt airp2} to carry out the
plans. The figure shows the first level of the search after $S$ has
been regressed. It also shows the pivot action $a_{p}$ given by {\tt
  unload(pack1,airp1,ASU)}, and a candidate set of pairwise
independent actions with respect to $a_{p}$. Finally, we can see
in Figure~\ref{example2-fig} the generation of the parallel
branch. Notice that each node can be seen as a partial regressed
plan. As described in the paragraphs above, only actions
regressing to lower heuristic estimates are considered in
$a_{par}$ to fatten the pivot branch. Notice that the action {\tt
unload(pack4,airp2,Home)} has been discarded because it leads to a
state with higher cost, even though it is not inconsistent with
the rest of the actions chosen to fatten the pivot branch.
Furthermore, we can also see that we have preferred actions using
the plane {\tt airp1}, since they overlap more with the pivot
action $a_p$.

\begin{figure}
\centerline{\epsfxsize=4.0in \epsfbox{example2.eps}} \mvp
\caption{$S_{par}$ is the result of incrementally fattening the
  $Pivot$ branch with the pairwise independent actions in $O$}
\mvp
\label{example2-fig}
\end{figure}

\begin{figure}[t]
{\small{
\centerline{
\begin{minipage} [b] {10.5cm}
\textbf{pushUP}(S) \\
\hspace*{0.5cm} $A_{s}$ $\leftarrow$ \emph{get actions leading to S}\\
\hspace*{0.5cm} \textbf{forall} $a \in A_{s}$ \\
\hspace*{1cm} $x$ $\leftarrow$ $0$ \\
\hspace*{1cm} $S_{x}$ $\leftarrow$ \emph{get parent node of S} \\
\hspace*{2cm} /** Getting highest ancestor for each action \\
\hspace*{1cm} \textbf{Loop} \\
\hspace*{1.5cm} $A_x$ $\leftarrow$ \emph{get actions leading to $S_x$}\\
\hspace*{1.5cm} \textbf{If} $(parallel(a,A_x))$ \\
\hspace*{2cm} $x$ $\leftarrow$ $x + 1$ \\
\hspace*{2cm} $S_x$ $\leftarrow$ \emph{get parent node of $S_{x-1}$} \\
\hspace*{1.5cm} \textbf{Else} \\
\hspace*{2cm} $a_j \leftarrow$ \emph{get action conflicting with $a$ from $A_x$} \\
\hspace*{2cm} \textbf{If} \emph{(Secondary Optimizations)}\\
\hspace*{2.5cm} \emph{Remove $a$ and $a_j$ from branch} \\
\hspace*{2.5cm} \emph{Include $a_{new}$ if necessary} \\
\hspace*{2cm} \textbf{Else} \\
\hspace*{2.5cm} $A_{x-1}$ $\leftarrow$ $A_{x-1} + a$ \\
\hspace*{2cm} $A_s$ $\leftarrow$ $A_s - a$ \\
\hspace*{1.5cm} \emph{break} \\
\hspace*{1cm} \textbf{End Loop} \\
\hspace*{2cm} /**Adjusting the partial plan \\
\hspace*{0.5cm} $S_x$ $\leftarrow$ \emph{get highest ancestor x in
  history}\\
\hspace*{0.5cm} $createNewBranchFrom(S_x)$ \\
\hspace*{0.5cm} \textbf{while} $x > 0$ \\
\hspace*{1cm} $S_{new}$ $\leftarrow$ \emph{regress $S_x$ with
  $A_{x-1}$} \\
\hspace*{1cm} $S_x$ $\leftarrow$ $S_{new}$ \\
\hspace*{1cm} $x$ $\leftarrow$ $x - 1$ \\
\textbf{END};
\end{minipage}}
}}
\caption{\ps\ Procedure}
\label{pushUp-fig}
\end{figure}


\begin{figure*}[!htp]
\centerline{
\begin{tabular}{c}
\subfigure[Finding the highest ancestor node to which an action
can be pushed up.]{ \epsfxsize=3.9in \epsfbox{example3.eps} } \\
\subfigure[The \ps\ procedure generates a new search branch.]{
\epsfxsize=3.9in \epsfbox{example4.eps} }
\end{tabular}}
\mvp \caption{Rearranging of the Partial Plan}
\label{example34-fig} \mvp
\end{figure*}

\paragraph{Offsetting the Greediness of Fattening:} The fattening
procedure is greedy, since it insists that the state resulting
after fattening have a strictly better heuristic value. While
useful in avoiding the addition of irrelevant actions to the plan,
this procedure can also sometimes preclude actions that are
ultimately relevant but were discarded because the heuristic is
not perfect. These actions may then become part of the plan at
later stages during search (i.e., earlier parts of the execution
of the eventual solution plan; since we are searching in the space
of plan suffixes). When this happens, the length of the parallel
plan is likely to be greater, since more steps that may be needed
to support the preconditions of such actions would be forced to
come at even later stages of search (earlier parts of the plan).
Had the action been allowed into the partial plan earlier in the
search (i.e., closer to the end of the eventual solution plan),
its preconditions could probably have been achieved in parallel to
the other subgoals in the plan, thus improving the number of
steps.

In order to offset this negative effect of greediness, \altaltp\
re-arranges the partial plan to promote such actions higher up the
search branch (i.e., later parts of the execution of the eventual
solution plan).  Specifically, before expanding a given node $S$,
\altaltp\ checks to see if any of the actions in $A_{s}$ leading
to $S$ from its parent node (i.e., Figure~\ref{example2-fig} shows
that $A_{par}$ leads to $S_{par}$) can be pushed up to higher
levels in the search branch. This online re-arrangement of the
plan is done by the \ps\ procedure, which is shown in
Figure~\ref{pushUp-fig}. The \ps\ procedure is called each time
before a node gets expanded, and it will try to compress the
partial plan. For each of the actions $a \in A_s$ we find the
highest ancestor node $S_{x}$ of $S$ in the search branch to which
the action can be applied (i.e., it gives some literal in $S_x$
without deleting any other literals in $S_x$, and it is pairwise
independent of all the actions $A_{x}$ currently leading out of
$S_{x}$, in other words the condition $parallel(a,A_x)$ is
satisfied). Once $S_x$ is found, $a$ is then removed from the set
of actions $A_s$ leading to $S$ and introduced into the set of
actions leading out of $S_x$ (to its child in the current search
branch). Next, the states in the search branch below $S_x$ are
adjusted to reflect this change. The adjustment involves
recomputing the regressions of all the search nodes below $S_x$.
At first glance, this might seem like a transformation of
questionable utility since the preconditions of $a$ (and their
regressions) just become part of the descendants of $S_x$, and
this does not necessarily reduce the length of the plan.  We
however expect a length reduction because actions supporting the
preconditions of $a$ will get ``pushed up'' eventually during
later expansions.

Rather than doctor the existing branch, in the current implementation,
we just add a new branch below $S_x$ that reflects the changes made by
the \ps\ procedure.\footnote{Because of the way our data structures are
set up, adding the new branch turns out to be a more robust option
than manipulating the existing search branch.}  The new branch then
becomes the active search branch, and its leaf node is expanded next.

\paragraph{Aggressive Variation of \ps:}
The \ps\ procedure, as described above, is not expensive as it only
affects the current search branch, and the only operations involved
are recomputing the regressions in the branch.  Of course, it is
possible to be more aggressive in manipulating the search branch. For
example, after applying an action $a$ to its ancestor $S_x$ the set of
literals in the child state, say $S_{new}$ changes, and thus additional actions
may become relevant for expanding $S_{new}$. In
principle, we could re-expand $S_{new}$ in light of the new
information. We decided not to go with the re-expansion option, as it
typically does not seem to be worth the cost.  In
Section~\ref{sec-scenarios}, we do compare our default version of \ps\
procedure with a variant that re-expands all nodes in the search
branch, and the results of those studies support our decision to avoid
re-expansion.  Finally, although we introduced the \ps\ procedure as
an add-on to the fattening step, it can also be used independent of
the latter, in which case the net effect would be an incremental
parallelization of a sequential plan.

\paragraph{Example:} In Figure~\ref{example34-fig}(a), we have two actions
  leading to the
  node $S_{par}$ (at depth two), these two actions are {\tt
  Unload(pack4,airp2,Home)} and {\tt fly(airp1,LocX,ASU)}. So, before
  expanding $S_{par}$ we check if any of the two
  actions leading to it can be pushed up. While the second action is
  not pushable since it interacts with the actions in its ancestor
  node, the first one is. We find the highest ancestor in the partial
  plan that interacts with our pushable action. In our example the
  root node is such an ancestor. So, we insert our pushable action {\tt
  Unload(pack4,airp2,Home)} directly below the root node.  We then
  re-adjust the state $S_{par}$ to $S_{new}$ at depth 1, as shown in
  Figure~\ref{example34-fig}(b), adding a new branch, and reflecting the
  changes in the states below. Notice that the action {\tt
  Unload(pack4,airp2,Home)} was initially discarded by the
  greediness of the fattening procedure (see Figure~\ref{example2-fig}), but we
  have offset this negative effect with our plan compression
  algorithm. We can see also that we have not re-expanded the
  state $S_{new}$ at depth 1, we have only made the adjustments to the
  partial plan using the actions already presented in the search
  trace.\footnote{Instead, the aggressive \ps\ modification would
  expand $S_{new}$ at depth 1, generating similar states to
  those generated by the expansion of $S_{par}$ at the same depth.}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{ \epsfxsize=3.0in \epsfbox{grippersteps.eps} } &
\subfigure[]{ \epsfxsize=3.0in \epsfbox{elevatorsteps.eps} }
\end{tabular}}
\mvp \caption{Performance on the Gripper (AIPS-98) and the
Elevator (AIPS-00) Domains.} \label{gripelevt-fig} \mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{ \epsfxsize=3.0in \epsfbox{schedulesteps.eps} } &
\subfigure[]{ \epsfxsize=3.0in \epsfbox{scheduletime.eps} }
\end{tabular}}
\mvp \caption{Performance on the Schedule domain (AIPS-00)}
\label{schedule-fig} \mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{logisticssteps.eps}
} & \subfigure[]{
  \epsfxsize=3.0in \epsfbox{logisticstime.eps}
}
\end{tabular}}
\mvp \caption{Performance on the Logistics domain(AIPS-00)}
\label{logistics-fig} \mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{driverlogsteps.eps}
} & \subfigure[]{
  \epsfxsize=3.0in \epsfbox{driverlogtime.eps}
}
\end{tabular}}
\mvp \caption{Performance on the DriverLog domain(AIPS-02)}
\label{driverlog-fig} \mvp
\end{figure*}

\section{Evaluating the Performance of \ap}
\label{sec-eval}
We implemented \altaltp\ on top of \altalt.
We have tested our implementation on a suite of  problems that
were used in the 2000 and 2002 AIPS
competition~\cite{aips-00,aips-02}, as well as other benchmark
problems~\cite{aips-98}. Our experiments are broadly divided into
three sets, each aimed at comparing the performance of
\altaltp\ under different scenarios:

\begin{enumerate}
\item Comparing the performance of \altaltp\ to other planning systems
  capable of producing parallel plans.
\item Comparing our incremental parallelization technique to \altalt\
  + Post-Processing.
\item Ablation studies to analyze the effect of the different
  parts of the \altaltp\ approach on its overall performance.
\end{enumerate}

Our experiments were all done on a Sun Blade-100 workstation,
running SunOS 5.8 with 1GB RAM. Unless noted otherwise, \altaltp\
was run with the $h_{adjsum2M}$ heuristic described in
section~\ref{sec-background} of this paper, and with a parallel
planning graph grown until the first level where the top-level
goals are present without being mutex. All times are in seconds.

\subsection{Comparing \ap\ with Competing Approaches}
\label{sec-optimal}
In the first set of experiments we have compared the performance of
our planner with the results obtained by running
STAN~\cite{fox-graph}, Blackbox~\cite{blackbox}, TP4~\cite{haslum01},
LPG~\cite{lpg02} and SAPA~\cite{sapa}. Unless noted otherwise, every
planner has been run with its default settings.  Some of the planners
could not be run in some domains due to parsing problems or memory
allocation errors. In such cases, we just omit that planner from
consideration for those particular domains.

%HERE
\subsubsection{Planners Used in the Comparison Studies}

STAN is a disjunctive planner, which is an optimized version of
the Graphplan algorithm that reasons with invariants and
symmetries to reduce the size of the search space. Blackbox is
also  based on the Graphplan algorithm but it works by converting
planning problems specified in STRIPS~\cite{strips} notation into
boolean satisfiability problems and solving it using a SAT solver
(the version we used defaults to SATZ).\footnote{We have not
chosen IPP~\cite{ipp}, which is also an optimized Graphplan
planning system because results reported by~\citeA{haslum01} show
that it is already less efficient than STAN.} LPG~\cite{lpg02} was
judged the best performing planner at the 3rd International
Planning Competition~\cite{aips-02}, and it is a planner based on
planning graphs and local search inspired by the Walksat approach.
LPG was run with its default heuristics and
  settings. Since LPG employs an iterative improvement algorithm, the
quality of the plans produced by it can be improved by running it for
multiple iterations (thus increasing the running time). To make the
comparisons meaningful, we decided to run LPG for  two iterations
(n=2), since beyond that, the running time of LPG was generally worse
than that of \altaltp.
Finally, we have
also chosen two metric temporal planners, which are able to represent
parallel plans because of their representation of
time and durative actions. TP4~\cite{haslum01} is a temporal planner
based on HSP*p~\cite{haslum00}, which is an optimal parallel state space
planner with an IDA* search algorithm.
The last planner in our list is SAPA~\cite{sapa}. SAPA is a
powerful domain-independent heuristic forward chaining planner for metric temporal
domains that
employs distance-based heuristics~\cite{rao-sanchez} to control its
search.

\subsubsection{Comparison Results in Different Domains}

We have run the planners in the Gripper domain from the
International Planning and Scheduling competition from
1998~\cite{aips-98}, as well as three different domains
(Logistics, Scheduling, and Elevator-miconic-strips) from
2000~\cite{aips-00}, and three more from the 2002
competition~\cite{aips-02} - DriverLog, ZenoTravel, and Satellite.
In cases where there were multiple versions of a domain, we used
the ``STRIPS Untyped'' versions.\footnote{Since SAPA does not read
the STRIPS file format, we have run the SAPA planner on equivalent
problems with unit-duration actions from \citeA{aips-02}.}. We
discuss the results of each of the domains  below.

\und{Gripper:} In Figure~\ref{gripelevt-fig}(a), we compare the
performance of \altaltp\ on the Gripper
domain~\cite{aips-98} to the rest of the planners excluding
SAPA. The plot shows the results in terms of
number of (parallel) steps. We can see that for even this simplistic domain, \altaltp\
and LPG are the only planners capable of scaling up and generating
parallel plans. None of the other approaches is able to solve more
than four problems.\footnote{Although STAN is supposed to be
able to generate optimal step-length plans, in a handful of cases it
seems to have produced nonoptimal solutions for the Gripper Domain. We
have no explanation for this behavior, but have
informed the authors of the code.} \altaltp\ is able to
scale up without any difficulty to problems involving 30
balls. Furthermore, \altaltp\ returns better plans than LPG.

\und{Elevator:} In Figure~\ref{gripelevt-fig}(b), we compare \altaltp\ to
STAN, Blackbox and LPG in the Elevator domain (Miconic
Strips)~\cite{aips-00}.\footnote{we did not include  the traces from
  TP4  because the pre-processor of the planner was not able to read
  the domain.} \altaltp\ approached the quality of the solutions
produced by the optimal approaches (e.g. Blackbox and
STAN). Notice that Blackbox can only solve around half of the problems
solved by \altaltp\ in this domain.

\und{Scheduling:} Results from the Scheduling domain are shown in
Figure~\ref{schedule-fig}. Only Blackbox and STAN are considered
for comparison.\footnote{The TP4 pre-processor cannot read this
domain, LPG runs out of memory, and SAPA has parsing problems.}
\altaltp\ seems to reasonably approximate the optimal parallel
plans for many problems (around 50 of them), but does produce
significantly suboptimal plans for some.  However, it is again
able to solve more problems than the other two approaches and in a
fraction of the time.

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{zenotravelsteps.eps}
} &
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{zenotraveltime.eps}
}
\end{tabular}}
\mvp \caption{Performance on the ZenoTravel domain (AIPS-02)}
\label{zenotravel-fig} \mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{satellitesteps.eps}
} &
\subfigure[]{
  \epsfxsize=3.0in \epsfbox{satellitetime.eps}
}
\end{tabular}}
\mvp \caption{Performance on the Satellite domain(AIPS-02)}
\label{satellite-fig} \mvp
\end{figure*}

\und{Logistics:} The plots corresponding to the Logistics domain
from~\citeA{aips-00} are shown in
Figure~\ref{logistics-fig}.\footnote{Only SAPA is excluded due to
parsing problems.}  For some of the most difficult problems
\altaltp\ outputs lower quality solutions than the optimal
approaches. However, only \altaltp\ and LPG are able to scale up
to more complex problems, and we can easily see that \altaltp\
provides better quality solutions than LPG. \altaltp\ also seems
to be more efficient than any of the other approaches. The LPG
solutions for problems 49 to 61 are obtained doing only one
iteration, since LPG was not able to complete the second iteration
in a reasonable amount of time. This explains the low time taken
for LPG, and the lower quality of its solutions.

\und{DriverLog:}  We see in Figure~\ref{driverlog-fig}(a) that
\altaltp\ does reasonably well in terms of quality with respect to the
other approaches in the DriverLog domain. Every planner is considered
this time. \altaltp\  is one of the
two planners able to scale up. Figure~\ref{driverlog-fig}(b) shows
also that \altaltp\ is more efficient than any of the other planners.

\und{Zeno-Travel:}  Only \altaltp, SAPA, and LPG are able to solve most of the problems
in this domain.\footnote{Blackbox and TP4 are not able to parse this domain.}
\altaltp\ solves them very efficiently (Figure~\ref{zenotravel-fig}(b))
providing very good solution quality (Figure~\ref{zenotravel-fig}(a)) compared
to the temporal metric planners.

\und{Satellite:}  The results from the Satellite domain are shown in
Figure~\ref{satellite-fig}. Although every planner is considered, only \altaltp,
SAPA, and LPG can solve most of the problems. SAPA solves all problems but
produces lower quality solutions for many of them. \altaltp\ produces better
solution quality than SAPA, and is also more efficient. However, \altaltp\ produces
lower quality solutions than LPG in four problems. LPG cannot solve one of
the problems and produces lower quality solutions in 5 of them.


\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{ \epsfxsize=3.0in \epsfbox{stepslogisticspost.eps} }
& \subfigure[]{ \epsfxsize=3.0in \epsfbox{timelogisticspost.eps} }
\end{tabular}}
\mvp \caption{\altalt\ and Post-Processing {\em vs.} \ap\
(Logistics domain)} \label{postprocessinglog-fig} \mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[]{ \epsfxsize=3.0in \epsfbox{stepszenopost.eps} } &
\subfigure[]{ \epsfxsize=3.0in \epsfbox{timezenopost.eps} }
\end{tabular}}
\mvp
\caption{\altalt\ and Post-Processing {\em vs.}  \ap\ (Zenotravel domain)}
\label{postprocessingzeno-fig}
\mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{cc}
\subfigure[\ap\ Solution]{ \epsfxsize=2.80in
\epsfbox{altaltpsol.eps} } & \subfigure[\ap\ plus
Post-processing]{ \epsfxsize=3.0in \epsfbox{altaltpsolpost.eps} }
\end{tabular}}
\mvp
\caption{Plots showing that \altaltp\ solutions cannot be
  improved anymore by Post-processing.}
\label{altaltpsols-fig}
\mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l@{}l@{}l}
\subfigure[]{ \epsfxsize=3.0in \epsfbox{stepslogisticspushagr.eps}
} & \subfigure[]{ \epsfxsize=2.9in
\epsfbox{timelogisticspushagr.eps}
} & \\
\subfigure[]{ \epsfxsize=3.0in \epsfbox{stepssatellitepushagr.eps}
} & \subfigure[]{ \epsfxsize=2.9in
\epsfbox{timesatellitepushagr.eps} }
\end{tabular}}
\mvp
\caption{Analyzing the effect of the \ps\ procedure}
\label{pushscenarios-fig}
\mvp
\end{figure*}

\begin{figure*}[t]
\centerline{
\begin{tabular}{@{}l@{}l}
\subfigure[Utility of using Parallel Planning Graphs]{
\epsfxsize=3.0in \epsfbox{stepsparallelserial.eps} } &
\subfigure[Solving a Serial domain]{ \epsfxsize=3.0in
\epsfbox{blockstime.eps} }
\end{tabular}}
\mvp
\caption{Plots showing the utility of using parallel planning graphs in
  computing the heuristics, and characterizing the overhead incurred
  by \altaltp\ in serial domains.}
\label{parallelserial-fig}
\mvp
\end{figure*}

\und{Summary:} In summary, we note that \altaltp\ is significantly
superior in the elevator and gripper domains. It also performs
very well in the DriverLog, ZenoTravel, and Satellite domains from
the 2002 competition~\cite{aips-02}. The performance of all
planners is similar in the Schedule domain.  In the Logistics
domain, the quality of \altaltp\ plans are second only to those of
Blackbox for the problems that this optimal planner can solve.
However, it scales up along with LPG to bigger size problems,
returning very good step-length quality plans. TP4, the only other
heuristic state search regression planner capable of producing
parallel plans is not able to scale up in most of the domains.
SAPA, a heuristic search progression planner, while competitive,
is still outperformed by \altaltp\ in planning time and solution
quality.

\subsection{Comparison to  Post-Processing Approaches}
\label{sec-postprocessing}

As we mentioned earlier (see Section~\ref{sec-intro}), one way of
producing parallel plans that has been studied previously in the
literature is to post-process sequential plans \cite{backstrom98}.  To compare
online parallelization to post-processing, we
have implemented~\citeA{backstrom98}'s ``Minimal De-ordering Algorithm'',
and used it to post-process the sequential
plans produced by \altalt\ (running with its default heuristic
$h_{AdjSum2M}$ using a serial planning graph). In this section we will
compare our online parallelization procedure to this offline method.

The first set of experiments is on the Logistics
domain~\cite{aips-00}. The results are shown in
Figure~\ref{postprocessinglog-fig}. As expected, the original \altalt\
has the longest plans since it allows only one action per time
step. The plot shows that post-processing techniques do help in
reducing the makespan of the plans generated by \altalt. However, we
also notice that \altaltp\ outputs plans with better makespan than
either \altalt\ or \altalt\ followed by post-processing.  This shows
that online parallelization is a better approach than post-processing
sequential plans.  Moreover, the plot in
Figure~\ref{postprocessinglog-fig}(b) shows that the time taken by
\altaltp\ is largely comparable to that taken by the other two
approaches.  In fact, there is not much additional cost overhead in
our procedure.

Figure~\ref{postprocessingzeno-fig} repeats these  experiments  in the
ZenoTravel domain~\cite{aips-02}. Once again, we  see that \altaltp\ produces better
makespan than post-processing the sequential plans of \altalt. Notice
that this time, \altalt\ plus post-processing is clearly less
efficient than either of the other two approaches.
 In summary, the results of this section demonstrate that
\altaltp\ is superior to \altalt\ plus post-processing.

One might wonder if the plans generated by \altaltp\ can also
benefit from the post-processing phase. We have investigated this
issue and found that the specific post-processing routines that we
used do not produce any further improvements. The main reason for
this behavior is that the \ps\ procedure already tries to exploit
any opportunity for shortening the plan length by promoting
actions up in the partial plan. As an illustrative example, we
show, in Figure~\ref{altaltpsols-fig}, the parallel plan output by
\ap\ for a problem from the logistics domain \cite<{\tt
logistics-4-1} from>{aips-00}, and the result of post-processing
this solution. Although the two solutions differ in terms of step
contents, we notice that they have the same step length. The
difference in step contents can be explained by the fact that the
de-ordering algorithm relaxes the ordering relations in the plan,
allowing for some actions to come earlier, while \ps\ always moves
actions towards the end of the plan. We have run more
comprehensive studies in three different domains (Logistics,
Satellite and Zenotravel), and found that in no case is the step
length of a plan produced by \ap\ improved by the post-processing
routine (we omit the comparison plots since they essentially show
the curves corresponding to \ap\ and \ap\ with post-processing
{\em coincident}).\footnote{We also verified this
  with at least one problem in all the other domains.}

\subsection{Ablation Studies}
\label{sec-scenarios}

This section attempts to analyze the impact of the different parts of
\altaltp\ on its performance.

\paragraph{Utility of the \ps\ Procedure:}
Figure~\ref{pushscenarios-fig} shows the effects of running
\altaltp\ with and without the \ps\ procedure (but with the
fattening procedure), as well as running it with a more aggressive
version of \ps, which as described in Section~\ref{sec-algorithm},
re-expands all the nodes in the search branch, after an action has
been pushed up.  We can see that running \altaltp\ with the \ps\
and fattening procedures is better than just the latter.
Comparison of results in Figure~\ref{postprocessinglog-fig}(a) and
Figure~\ref{pushscenarios-fig}(a) shows that even just the
fattening procedure performs better than the original \altalt. In
Figure~\ref{pushscenarios-fig}(b) we can see that although the
\ps\ procedure does not add much overhead, the aggressive version
of \ps\ does get quite expensive. We also notice that  only around
20 problems are solved within time limits with aggressive \ps. The
plots in Figure~\ref{pushscenarios-fig}(c) and
Figure~\ref{pushscenarios-fig}(d) show the results of the same
experiments in the Satellite domain. We see that the situation is
quite similar in this domain. We can  conclude then that the \ps\
procedure, used to offset the greediness of the algorithm,
achieves its purpose.

\paragraph{Utility of basing heuristics on Parallel Planning Graphs:}
We can see in Figure~\ref{parallelserial-fig}(a) that using parallel
planning graph as the basis for deriving heuristic estimates in
\altaltp\ is a winning idea. The serial planning graph overestimates
the heuristic values in terms of steps, producing somewhat longer
parallel solutions. The fact that the version using serial planning
graph runs out of time in many problems also demonstrates that the
running times are also improved by the use of parallel planning
graphs.

\paragraph{Comparison to \altalt:}
One final concern would be how much of an  extra computational hit
is taken by the \altaltp\ algorithm  in serial domains~\cite<e.g.
Blocks-World from>{aips-00}. We expect it to be negligible and to
confirm our intuitions, we ran \altaltp\ on a set of problems from
the sequential Blocks-World domain. We see from the
plot~\ref{parallelserial-fig}(b) that the time performance between
\altalt\ and \altaltp\ are equivalent for almost all of the
problems.

\section{Related work}
\label{sec-rel}

The idea of partial exploration of parallelizable sets of actions is not new
~\cite{kabanza97,godefroid91,sapa}.  It has been studied in the area of concurrent
and reactive planning, where one of the main goals is to approximate
optimal parallelism. However, most of the research there has been focused on
forward chaining planners~\cite{kabanza97}, where the state of the world is
completely known. It has been implied that backward-search methods are
not suitable for this kind of analysis ~\cite{godefroid91} because the
search nodes correspond to partial states. We have shown that
backward-search methods can also be used to approximate parallel plans
in the context of classical planning.

Optimization of plans according to different criteria (e.g.
execution time, quality, etc) has also been done as a
post-processing step. The post-processing computation of a given
plan to maximize its parallelism has been discussed
by~\citeA{backstrom98}. Reordering and de-ordering techniques are
used to maximize the parallelism of the plan. In de-ordering
techniques ordering relations can only be removed, not added. In
reordering, arbitrary modifications to the plan are allowed. In
the general case this problem is NP-Hard and it is difficult to
approximate~\cite{backstrom98}. Furthermore, as discussed in
Section~\ref{sec-intro} and ~\ref{sec-eval}, post-processing
techniques are just concerned with modifying the order between the
existing actions of a given plan. Our approach not only considers
modifying such orderings but also inserting new actions online
which can minimize the possible number of parallel steps of the
overall problem.

We have already discussed Graphplan based
planners~\cite{fox-graph,blackbox}, which return optimal plans based
on the number of time steps. Graphplan uses IDA* to include the
greatest number of parallel actions at each time step of the
search. However, this iterative procedure is very time consuming and
it does not provide any guarantee on the number of actions in its
final plans. There have been a few attempts to minimize the number of
actions in these planners~\cite{cheng99} by using some domain control
knowledge based on the generation of rules for each specific planning
domain. The Graphplan algorithm tries to maximize its
parallelism by satisfying  most of the subgoals at each
time step, if the search fails then it backtracks and reduces the set
of parallel actions being considered one level before. \altaltp\ does
the opposite, it tries to guess initial parallel nodes given the
heuristics, and iteratively adds more actions to these nodes as
possible with the \ps\ procedure later during search.

More recently, there has been some work on generalizing forward
state search to handle action concurrency in metric temporal
domains. Of particular relevance to this work are the Temporal
TLPlan~\cite{fbac01} and SAPA \cite{sapa}.  Both these planners
are designed specifically for handling metric temporal domains,
and use similar search strategies. The main difference between
them being that Temporal TLPlan depends on hand-coded search
control knowledge to guide its search, while SAPA (like \altaltp)
uses heuristics derived from (temporal) planning graphs. As such,
both  these planners can be co-opted to produce parallel plans in
classical domains. Both these planners do a forward chaining
search, and like \altaltp, both of them achieve concurrency
incrementally, without projecting sets of actions, in the
following way. Normal forward search planners start with the
initial state $S_0$, corresponding to time $t_0$, consider all
actions that apply to $S_0$, and choose one, say $a_1$ apply it to
$S_0$, getting $S_1$. They simultaneously progress the ``system
clock'' from $t_0$ to $t_1$. In order to allow for concurrency,
the planners by \citeA{fbac01}, and \citeA{sapa} essentially
decouple the ``action application'' and ``clock progression.'' At
every point in the search, there is a non-deterministic choice -
between progressing the clock, or applying (additional) actions at
the current time point.  From the point of view of these planners,
\altaltp\ can be seen as providing heuristic guidance for this
non-deterministic choice (modulo the difference that \altaltp\
does regression search). The results of empirical comparisons
between \altaltp\ and SAPA, which show that \altaltp\ outperforms
SAPA, suggest that the heuristic strategies employed in \altaltp\,
including the incremental fattening, and the pushup procedure, can
be gainfully adapted to these planners to increase the concurrency
in the solution plans. Finally, HSP*, and TP4, its extension to
temporal domains, are both heuristic state search planners using
regression that are capable of producing parallel plans
\cite{haslum00}. TP4 can be seen as the regression version of the
approach used in SAPA and temporal TLPlan. Our experiments however
demonstrate that neither of these planners scales well in
comparison to \altaltp.

The \ps\ procedure can be seen as a plan compression procedure. As
such, it is similar to other plan compression procedures such as
``double-back optimization'' \cite{double-back}. One difference is
that double-back is used in the context of a local search, while
\ps\ is used in the context of a systematic search. Double-back
could be also applied to any finished plan or schedule, but as any
other post-processing approach its outcome would depend highly on
the plan given as input.

\section{Concluding Remarks}
\label{sec-conc}

Motivated by the acknowledged inability of heuristic search
planners to generate parallel plans, we have developed and
presented an approach to generate parallel plans in the context of
\altalt, a heuristic state space planner. This is a challenging
problem because of the exponential branching factor incurred by
naive methods. Our approach tries to avoid the branching factor
blow up by greedy and online parallelization of the evolving
partial plans. A plan compression procedure called \ps\ is used to
offset the ill effects of the greedy search.  Our empirical
results show that in comparison to other planners capable of
producing parallel plans, \altaltp\ is able to provide reasonable
quality parallel plans in a fraction of the time of competing
approaches. Our approach also seems to provide better quality
plans than can be achieved by post-processing sequential plans.
Our results show that \altaltp\ provides an attractive  tradeoff
between quality and efficiency in the generation of parallel
plans. In the future, we plan to adapt the  \altaltp\ approach to
metric temporal domains, where the need for concurrency is more
pressing. One idea is to adapt some of the sources of strength in
\altaltp\ to SAPA, a metric temporal planner being developed in
our group \cite{sapa}.

\acks{We thank Minh B. Do and XuanLong Nguyen for helpful
discussions and feedback. We also thank David Smith and the JAIR
reviewers for many constructive comments. This research is
supported in part by the NASA grants NAG2-1461 and NCC-1225, and
the  NSF grant IRI-9801676.}

\bibliography{rao-latest}
\bibliographystyle{theapa}
\end{document}
