\documentclass{article}
\usepackage{graphicx}
\usepackage{times}
\usepackage{aaai}
%\setlength{\textheight}{9in}
%\setlength{\textwidth}{6.5in}
%\setlength{\oddsidemargin}{0in}
%\setlength{\evensidemargin}{0in}
%\setlength{\topmargin}{0in}

\title{Analyzing Plans with Conditional Effects}
\author{Elly Winner \and Manuela Veloso\\
  Computer Science Department\\
  Carnegie Mellon University\\
  5000 Forbes Avenue\\
  Pittsburgh, PA 15213\\
  \{elly,veloso\}@cs.cmu.edu\\
  fax: (412) 268-4801}

\begin{document}
%\bibliographystyle{plain}

\date{}
\maketitle

%%%%%%%%%%%%   ABSTRACT   %%%%%%%%%%%%
\begin{abstract}
  Several tasks, such as plan reuse and agent modelling, need to
  interpret a given or observed valid plan to generate the underlying
  plan rationale. Although there are several successful previous
  contributions to this rationale-extraction problem, we realize that
  they do not apply to complex plans, in particular to plans with
  actions that have conditional effects. In this paper, we introduce
  \textsc{Sprawl}, an algorithm to find a minimal annotated partially
  ordered structure in an observed totally ordered plan with
  conditional effects. The algorithm proceeds in a two-phased
  approach, first preprocessing the given plan using a novel
  \textit{needs analysis} technique that builds a \textit{needs tree}
  to identify the dependencies that link all the literals, including
  the conditional effects, in the totally ordered plan. The needs tree
  is then processed to construct a partial ordering that captures the
  complete rationale of the given plan.  We introduce the concept and
  details of needs analysis, present the complete algorithm, and
  provide illustrative example. We discuss the challenges we faced in
  handling the rationale and conditional effects.
\end{abstract}

%%%%%%%%%%%%   INTRODUCTION   %%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

Much of the work on plan reuse, plan recognition and agent modelling
has been founded on the analysis of example plans and executions. One
of the most common approaches to plan analysis has been to create an
\textit{annotated ordering} of the example
plan~\cite{nilsson72learnex,regnierfade91,rao92valstruct,rao94ebgpo,veloso94analogy},
in which the plan is supplemented with a rationale for (some of) the
ordering constraints. Annotated orderings allow systems not only to
more flexibly reuse portions of the plans they have observed, but also
to reuse the reasoning that created those plans in order to solve new
problems.

In recent years, the focus of the planning and agent modelling
community has shifted from the simple STRIPS domain-specification
language~\cite{fikes71strips} towards richer languages like
ADL~\cite{pednault86formulating}. Despite the success of the annotated
ordering approach, it has not been applied to domains with conditional
effects. In this paper, we introduce the \textsc{Sprawl} algorithm for
finding \textit{minimal annotated consistent partial orderings} of
observed totally ordered plans.

We assume that we are given or observe a plan that is valid, i.e., the
steps in the plan are {\it needed} in the sense that they have a
reason to be part of the plan. We aim at linking the steps of the plan
through the literals or terms that they support. Partial orderings are
capable of representing these dependencies.\footnote{A partial order
is a precedence relation $\preceq$ with the following three properties
1) reflexivity: $a \preceq a$; 2) non-symmetric (no cycles): if $a
\preceq b$ then not $b \preceq a$, unless $a=b$; and 3) transitivity:
if $a \preceq b$ and $b \preceq c$, then $a \preceq c$. The relation
is a ``partial'' order because there may be uncomparable elements:
i.e., elements $a,b$ such that neither $a \preceq b$ nor $b \preceq
a$. Note that a DAG is a partial order if we define $a \preceq b$ as a
path from $a$ to $b$.} In addition, partial orderings can isolate
independent subplans that can be reused or recognized separately, and
they also identify potential parallelism.

We assume that observed example plans are totally ordered as plans of
single executors. The annotations on the ordering constraints should
\textit{explain} the rationale behind the plans and allow portions of
them to be easily matched, removed, and used independently.

Conditional effects difficult the task of annotating a plan because
they cause the effects of a given step to change depending on what
steps come before it, thus making the effects of a step difficult to
predict. In fact, an ordering must treat each conditional effect in
the plan in one of three ways:

\begin{itemize}
\item {\bf Use:} make sure the effect occurs;
\item {\bf Prevent:} make sure the effect does not occur;
\item {\bf Ignore:} don't care whether the effect occurs or not.
\end{itemize}

Figure~\ref{fig:upi} shows totally ordered plans that demonstrate
these three cases. The preconditions (pre) are listed and the effects
are all represented as conditional effects $\{a\}
\rightarrow b$, i.e., if $a$ then add $b$. A ``regular'' effect for
adding a literal $b$ is then represented as $\{\} \rightarrow b$.
Delete effects are represented as negated terms.

\begin{figure}[hbt]
  \begin{center}
    \includegraphics[width=8cm]{upismall.eps}
    \caption{
      %
      Three totally ordered plans that illustrate the three possible
      ways of treating a conditional effect in an ordering: using it
      to achieve a goal, preventing it in order to achieve a goal, or
      ignoring its effect. 
      %
      }
    \label{fig:upi}
  \end{center}
\end{figure}

In the first plan, the conditional effect of {\sf op1} is used to
generate the goal term {\sf c}. In the second plan, it is prevented
from generating the term {\sf c}, and in the third plan, the effect is
irrelevant to the plan. Figures~\ref{fig:usepo} and~\ref{fig:ignorepo}
show the partial orders representing the \textit{use} and
\textit{ignore} cases, respectively. Although the totally ordered
plans for these two cases are composed of the same steps in the same
order, the partial orderings are very different. Treating any
conditional effect in a different way will result in a different
partial ordering. One way to deal with this is to insist that exactly
the same conditional effects must be active in the partial ordering as
are active in the totally ordered plan, but this will result in an
overly restrictive partial ordering in which some ordering constraints
may not contribute to goal achievement. Instead, we perform
\textit{needs analysis} on the totally ordered plan to discover which
conditional effects are \textit{relevant}.  Needs analysis allows us
to ignore \textit{incidental} conditional effects in the totally
ordered plan.

Instead of looking for the optimal (according to some metric)
partially ordered plan to solve a problem, we chose to focus on
finding partial orderings \textit{consistent} with the given totally
ordered plan, or those in which all relevant effects were also active
in the total ordering. There are two reasons for this. The first is
that the totally ordered plan contains a wealth of valuable information about
how to solve the problem, including which operators to use and which
conditional effects are relevant. The second is that for many
applications, including plan modification and reuse and agent
modelling, it is important to be able to analyze an observed or
previously generated plan (for example, to find characteristic
patterns of behavior or to identify unnecessary steps).

There are cases in which a different total ordering of the same plan
steps would produce a different partial ordering, but these are cases
in which the relevant effects differ. Consider the two totally ordered
plans shown in Figures~\ref{fig:reordering1}
and~\ref{fig:reordering2}. Although they consist of the same
operators, in the first totally ordered plan, the sequence of relevant
effects that produces the goal term {\sf z} is different than the sequence that produces {\sf z} in the second totally ordered plan.
We consider these two plans to be non-equivalent, though they solve
the same problem. \textsc{Sprawl} would never produce the same partial
ordering for both of them; the partial orderings would each preserve
the same relevant effects as are active in the respective totally
ordered plans.


\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=1.0\columnwidth]{usesmallpo.eps}
    \caption{
      %
      The annotated partially ordered plan which uses the conditional
      effect of {\sf op1} to achieve a goal.
      %
      }
    \label{fig:usepo}
  \end{center}
\end{figure}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.75\linewidth]{ignoresmallpo.eps}
    \caption{
      %
      The annotated partially ordered plan which ignores the
      conditional effect of {\sf op1}.
      %
      }
    \label{fig:ignorepo}
  \end{center}
\end{figure}



\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.8\linewidth]{reordering1.eps}
    \caption{
      %
      One possible totally ordered plan. In this plan, the goal
      {\sf z} is achieved via the first conditional effect of each
      operator.
      %
      }
    \label{fig:reordering1}
  \end{center}
\end{figure*}
\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.8\linewidth]{reordering2.eps}
    \caption{
      %
      Another possible totally ordered plan achieving the same goals.
      In this plan, the goal {\sf z} is achieved via the second
      conditional effect of each operator.
      %
      }
    \label{fig:reordering2}
  \end{center}
\end{figure*}

However, since our purpose is to reveal underlying structure, we do
have some requirements on the form of the resulting partial ordering; we
allow only ordering constraints which affect the fulfillment of the
goal terms---those which provide for or prevent relevant effects.

The remainder of this paper is organized as follows. We first discuss
related work in plan analysis. Then we introduce the needs analysis
technique, illustrate its behavior and discuss its complexity. Next,
we explain how the \textsc{Sprawl} algorithm uses needs analysis to
find a partial ordering and discuss the complexity of the entire
algorithm. We then discuss the limitations and capabilities of the
algorithm, present formal definitions for the concepts we use and
introduce, and finally present our conclusions.


%%%%%%%%%%%%   RELATED WORK   %%%%%%%%%%%%
\section{Related Work}
\label{sec:relwork}

Triangle tables:
~\cite{nilsson72learnex,regnierfade91}
FOR REUSE/MACRO LEARNING: store generalized plans in a table that shows which add-effects of
each op remain after each subsequent op, \& therefore which ops provide
precs to subsequent ops--helps to know how to use subplans--can
identify which ops are irrelevant for partial reuse (how?) mention the
need to be able to ``identify the role of each operator in the overall
plan: what its important effedcts are (as opposed to side effects) and
why these effects are needed in the plan.''

FOR PARALLELISM: reg \& fade use triangle table to build po from a to. remove
``artificial'' (vs.  ``genuine'') ordering constraints. find
``complete set of actions which can be executed in parallel''. change
computation of triangle tables, slightly. no ce handling.

Validation structures:
~\cite{rao92valstruct,rao94ebgpo}
FOR REUSE/MOD: given a p.o., constructs list of validations: 4-tuple (provided
effect, providing op, relying condition, relying op). no ces. no
validations for threats, but some computation over validations finds
threats for you. validation structure acts as proof of
correctness. modification = fixing inconsistencies in proof

Annotated ``decision-making'' rationale:
~\cite{veloso94analogy}
FOR REUSE/MOD: analogical reasoning---stores cases supplemented with
``decision-making rationale'' in order to be able to reuse rationale,
not just old plan.

Operator graphs \& their various-\&-sundry uses:
~\cite{smith93postponing,smith96recursion}
capture interaction between ops by chaining back from goal in very
needs-analysis-y sort of way. one node for each operator. used for
threat analysis, threat postponing, analyze/identify/avoid
``recursions'' (a, a-1, a, a-1...).

Goal agendas:
~\cite{koehler00reasonable}
use various methods (including planning graphs) to find ``goal
agendas''---an ordering for in which order to attack goals. still
exponential time, since it doesn't remember the plans, but less
exponential, since fewer threat difficulties.

previous partial ordering work:
~\cite{veloso90nonlin} found a po from a non-ce to; no annotations
~\cite{backstrom93harder} found that it's np-complete to find a best
po, given a to.
~\cite{rao96disjunctive} delay threat resolution by using disjunctive
orderings---we use disjunctions, too! is this too tenuous a link??

various po-ish planning methods:
~\cite{ucpop}
given problem, finds PO. can handle CEs, but does not annotate.

One of the most popular and efficient partial-order planners,
Graphplan~\cite{graphplan}, produces overconstrainted partial orderings,
which does not suit our purpose. Consider the plan in which the steps
$op\_a\_1 \ldots op\_a\_n$ may run in parallel with the steps
$op\_b\_1 \ldots op\_b\_m$. Graphplan would find the partial ordering
shown in Figure~\ref{fig:badpo}, which forces $op p$ to be one of the
first two steps of the plan. The ordering constraint between $op p$
and $op 2$ does not help achieve the goal, so it would not have been
included in a partial ordering created by \textsc{Sprawl}.
\textsc{Sprawl} would find the partial ordering shown in
Figure~\ref{fig:goodpo}, which allows $op p$ to run in parallel with
any of the other steps.
POINT OUT IRRELEVANT LINKS IN GRAPHPLAN VERSION. NO POSSIBLE REASON
FOR THEM.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=1.00\columnwidth]{badpo.eps}
    \caption{
      %
      The partial ordering found by Graphplan.
      %
      }
    \label{fig:badpo}
  \end{center}
\end{figure}
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=1.00\columnwidth]{goodpo.eps}
    \caption{
      %
      The partial ordering found by \textsc{Sprawl}.
      %
      }
    \label{fig:goodpo}
  \end{center}
\end{figure}


%%%%%%%%%%%%   NEEDS ANALYSIS   %%%%%%%%%%%%
\section{Needs Analysis}
\label{sec:needs}

Our first step in finding a partial ordering is to do needs analysis on
the totally ordered plan. Needs analysis begins by creating a goal step called
{\sf FINISH}, as in~\cite{smith93postponing}, with the
terms of the goal state as preconditions. Then it calculates
which terms need to be true before the last step in the plan
in order for the preconditions of {\sf FINISH} to be true
afterwards, and then which need to be true before the second-to-last
plan step in order for \textit{those} terms to be true. We continue
this calculation all the way backwards to the initial state, building up a
tree of ``needs.'' This needs tree allows us to identify easily the
relevant effects of a given step and most of the dependencies in the
plan. However, threats not active in the totally ordered plan are not
identified by needs analysis, and must be found afterwards.

\subsection{Needs Tree Structure}
\label{sub:treestruct}
In this section, we will discuss the needs that compose the
needs tree as well as the structure of the tree.

There are three kinds of needs in the needs tree:
\begin{enumerate}
\item{{\sf Precondition Needs}} the preconditions of a step are
  called \textit{precondition needs} of the step---they must be true
  for the step to be executable;
\item{{\sf Creation Needs}} terms which must be true before step
  $n$ in order for step $n$ to create a particular term (or maintain a
  previously existing term) are called \textit{creation needs} of the
  term;
\item{{\sf Protection Needs}} terms which must be true before step
  $n$ in order for step $n$ not to delete a particular term are called
  \textit{protection needs} of the term.
\end{enumerate}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.70\columnwidth]{sprinkle.eps}
    \caption{
      %
      The step {\sf sprinkle front-yard}.
      %
      }
    \label{fig:sprinkle}
  \end{center}
\end{figure}

We will use the plan step shown in Figure~\ref{fig:sprinkle} to
illustrate the three kinds of needs.  The term {\sf on sprinkler}
is a \textit{precondition need} of the step {\sf sprinkle
  front-yard}. To illustrate \textit{creation needs}, let us assume
that, after executing the step {\sf sprinkle front-yard},
{\sf wet shoe} must be true. This could be accomplished by ensuring
that {\sf at shoe front-yard} was true before {\sf sprinkle
  front-yard} executed or by ensuring that {\sf wet shoe} was
already true before {\sf sprinkle front-yard} executed, as shown in
Figure~\ref{fig:createlogop}. These two terms are called
\textit{creation needs} of {\sf wet shoe} at the step
{\sf sprinkle front-yard}, since they provide ways for the term
{\sf wet shoe} to be true after the step {\sf sprinkle
  front-yard}. To illustrate \textit{protection needs}, assume that,
after executing the step {\sf sprinkle front-yard}, the term
{\sf NOT wet shoe} must be true. In order to protect the term
{\sf NOT wet shoe}, we must ensure that {\sf NOT at shoe
  front-yard} is true before {\sf sprinkle front-yard} executes.
This is called a \textit{protection need} because it protects the term
from being deleted.

\begin{figure}
  \begin{center}
    \includegraphics[width=.85\columnwidth]{logop.eps}
    \caption{
                                %
      Expanding the need {\sf wet shoe} in the step
      {\sf sprinkle front-yard}. The term {\sf wet shoe} may be
      satisfied in either of two ways; this is represented by an
      {\sf OR} operator.
                                %
      }
    \label{fig:createlogop}
  \end{center}
\end{figure}

We must also make a distinction between \textit{maintain} creation
needs and \textit{add} creation needs~\footnote{Precondition needs and
  protection needs are always \textit{add} needs.}. As mentioned
above, there are two ways to ensure that {\sf wet shoe} is true
after the execution of the step {\sf sprinkle front-yard}, both
illustrated in Figure~\ref{fig:createlogop}. One way is for
{\sf wet shoe} to have been true previously. We call this a
\textit{maintain} creation need since the step does not generate the
term, but simply maintains a term that was previously true. However,
the step {\sf sprinkle front-yard} could generate the term
{\sf wet shoe} if {\sf at shoe front-yard} were true before the
step executed. We call this an \textit{add} creation need, since we
have introduced a new need in order to satisfy another.

It is not always necessary to generate new needs to satisfy a need
term; it may also be satisfied if a non-conditional effect of the step
satisfies it, as illustrated in Figure~\ref{fig:accomplish}. We call
such needs \textit{accomplished}.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.85\columnwidth]{accomplish.eps}
    \caption{
                                %
      A term may be true after a particular step if a non-conditional
      effect of the previous step accomplishes it. We indicate this
      with a double circle around the term.
                                %
      }
    \label{fig:accomplish}
  \end{center}
\end{figure}

The description of needs must include logical operators.  In the
example shown in Figure~\ref{fig:createlogop},the needs of {\sf wet
  shoe} are {\sf wet shoe OR at shoe front-yard}. Only one of the
two needs to be true to satisfy {\sf wet shoe}. {\sf AND}s and
{\sf NOT}s are also necessary.


%%%%%%%%%%%%   NEEDS ANALYSIS ALGORITHM   %%%%%%%%%%%%
\subsection{Needs Analysis Algorithm}
\label{sub:needsalg}

The needs analysis algorithm is shown in Table~\ref{alg:needsanal},
and Figure~\ref{fig:spandstheterm} illustrates in detail how it
generates the needs of an individual term. The complexity of needs
analysis is $O(mP(EC)^n)$, where $m$ is the number of steps without
conditional effects, $n$ is the number of steps with conditional
effects, $P$ is the bound on the number of preconditions, $E$ is the
bound on the number of conditional effects in each step, and $C$ is
the bound on the number of conditions per conditional effect. Note
that the complexity of needs analysis on a plan with no conditional
effects is linear: $O(mP)$.

\begin{table}[htb]
\hrule
{\small
%\begin{tabular}{|c|c|}
%\hline
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: A totally ordered plan $\cal T$ $=$ $S_1,S_2,\ldots,S_n$,\\ 
     \>the START operator $S_0$ with add effects set to the\\
     \>initial state, and the FINISH operator $S_n+1$ with\\
     \>preconditions set to the goal state.\\
{\bf Output}: A needs tree $N$.\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
{\bf procedure} Needs\_Analysis($\cal T$, $S_0$, $S_n+1$):\\
1. \>{\bf for} $c \leftarrow$ \bf{n+1} down-to $1$ {\bf do}\\
2. \> \>{\bf for} each precond of $S_c$ {\bf do}\\
3. \> \> \>Expand\_Term(c, precond)\\
\\
{\bf procedure} Expand\_Term(c, term):\\
4. \>Find\_Creation(c, term)\\
5. \>Find\_Prevention(c, term)\\
\\
{\bf procedure} Find\_Creation(c, term):\\
6. \>{\bf for} each conditional effect of $S_c$ {\bf do}\\
7. \> \>{\bf if} effect adds term {\bf then}\\
8. \> \> \>term.accomplished $\leftarrow$ {\bf true}\\
9. \> \>{\bf otherwise}\\
10. \> \> \>Add\_Conditions\_To\_Creation\_Needs(effect, term)\\
11. \> \> \>{\bf for} each condition of effect {\bf do}\\
12. \> \> \> \>Expand\_Term(c-1, condition)\\
\\
{\bf procedure} Find\_Prevention(c, term):\\
13. \>{\bf for} each conditional effect of $S_c$ {\bf do}\\
14. \> \>{\bf if} effect deletes term {\bf then}\\
15. \> \> \>term.impossible $\leftarrow$ {\bf true}\\
16. \> \> \>return\\
17. \> \>{\bf otherwise}\\
18. \> \> \>Add\_Conditions\_To\_Prevention\_Needs(effect, term)\\
19. \> \> \>{\bf for} each condition of effect {\bf do}\\
20. \> \> \> \>Expand\_Term(c-1, condition)\\
\end{tabbing}
\hrule
}}
\caption{Needs Analysis algorithm.}
\label{alg:needsanal}
%\end{tabular}
\end{table}

\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.90\linewidth]{expand_term.eps}
    \caption{
      %
      The creation needs of a need at a particular step are calculated
      by finding all possible ways it can be generated in the previous
      step and ensuring that at least one of these occurs. The
      protection needs are calculated by finding all possible ways it
      can be deleted in the previous step and ensuring that none of
      these occurs.
      %
      }
    \label{fig:spandstheterm}
  \end{center}
\end{figure*}
\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.750\linewidth]{fullcompleteneeds.eps}
    \caption{
      %
      A totally ordered plan in the sprinkler domain and its complete
      needs tree.
      %
      }
    \label{fig:completeneeds}
  \end{center}
\end{figure*}

We will use the totally ordered plan from the sprinkler domain shown in
Figure~\ref{fig:completeneeds} to illustrate the behavior of the needs
analysis algorithm.  First, the algorithm will create the
{\sf FINISH} step that has, as its precondition needs, the goal
terms. Then it will move to the last plan step ({\sf sprinkle
  front-yard}), which has one precondition need, to determine how to
satisfy the needs of the subsequent step ({\sf FINISH}). As
previously discussed, there are two ways for the step {\sf sprinkle
  front-yard} to satisfy {\sf wet shoe}: either {\sf wet shoe}
could be true before this step executes, or {\sf at shoe
  front-yard} must be true before this step executes. So the needs of
the term {\sf wet shoe} are {\sf \textit{maintain} wet shoe OR
  \textit{add} at shoe front-yard}. As for {\sf \textit{add} wet
  front-yard}, the other precondition need of the {\sf FINISH}
step, it is accomplished by the step {\sf sprinkle front-yard}
since it is a non-conditional effect of the step.

Next, the algorithm moves back to the previous plan step, {\sf move
  shoe back-yard front-yard}, which has one precondition need. The
needs carried over from previous steps are {\sf \textit{maintain}
  wet shoe OR \textit{add} at shoe front-yard}, the creation need of
{\sf wet shoe} from the {\sf FINISH} step, and {\sf on
  sprinkler}, the precondition need of the step {\sf sprinkle
  front-yard}.  The term {\sf at shoe front-yard} is a
non-conditional effect of this step, so it is accomplished.  The term {\sf wet shoe} cannot be prevented or
created by this step, so it is satisfied by a maintain creation need:
{\sf \textit{maintain} wet shoe}.  The term {\sf on sprinkler}
also cannot be prevented or created by this step, so it, too, is
satisfied by a maintain creation need: {\sf \textit{maintain} on
  sprinkler}.

Finally, the algorithm reaches the initial state, or {\sf START}
step, and it is able to determine which branches of the needs tree can
be accomplished and which can not. The remaining branches of the tree
are {\sf \textit{add} at shoe back-yard}, {\sf \textit{maintain}
  on sprinkler}, and {\sf \textit{maintain} wet shoe}. Two of the
needs, {\sf \textit{add} at shoe back-yard} and
{\sf {\sf maintain} on sprinkler} are true in the initial state
(accomplished by the {\sf START} step). However,
{\sf \textit{maintain} wet shoe} is cannot be accomplished by the
{\sf START} step, so we call its branch of the tree
\textit{unsatisfiable}.
 

%%%%%%%%%%%%   BUILDING A PARTIAL ORDER   %%%%%%%%%%%%
\section{The \textsc{Sprawl} Algorithm}
\label{sec:poing}

Table~\ref{alg:po} shows the \textsc{Sprawl} partial ordering
algorithm. \textsc{Sprawl} performs needs analysis, then walks
backwards along the needs tree and adds causal links in the partial
ordering between steps that need terms and the steps that generate
them.  The complexity of the \textsc{Sprawl} algorithm is $O(mP(EC)^n
+ A * (m+n+2)^3)$, where $m$ is the number of steps without
conditional effects, $n$ is the number of steps with conditional
effects, $P$ is the bound on the number of preconditions, $E$ is the
bound on the number of conditional effects in each step, and $C$ is
the bound on the number of conditions per conditional effect.

\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: A totally ordered plan $\cal T$ $=$ $S_1,S_2,\ldots,S_n$,\\ 
     \>the START operator $S_0$ with add effects set to the\\
     \>initial state, and the FINISH operator $S_n+1$ with\\
     \>preconditions set to the goal state.\\
{\bf Output}: A partially ordered plan shown as a directed graph $\cal
P$.\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
{\bf procedure} Find\_Partial\_Order($\cal T$, $S_0$, $S_n+1$):\\
1. \>tree $\leftarrow$ Needs\_Analysis($\cal T$, $S_0$, $S_n+1$)\\
2. \>tree $\leftarrow$ Trim\_Unaccomplished\_Need\_Tree\_Branches(tree)\\
3. \>{\bf for} $c \leftarrow$ {\bf n+1} down-to $1$ {\bf do}\\
4. \> \>{\bf for} each precondition of $S_c$ {\bf do}\\
5. \> \> \>Recurse\_Need(c, precondition, $\cal P$)\\
6. \>Handle\_Threats(tree, $\cal P$)\\
7. \>Remove\_Transitive\_Edges($\cal P$)\\
\\
{\bf procedure} Recurse\_Need(c, term, $\cal P$):\\
8. \>Add\_Causal\_Link(choose one way to create term, $S_c$, $\cal P$)\\
9. \>Recurse\_Need(c-1, term.create, $\cal P$)\\
10. \>Recurse\_Need(c-1, term.protect, $\cal P$)\\\
\\
{\bf procedure} Handle\_Threats(tree, $\cal P$):\\  
11. \>{\bf for} each causal link $S_i \rightarrow S_j$ {\bf do}\\
12. \> \>{\bf for} $c \leftarrow 1$ up-to $i-1$ {\bf do}\\
13. \> \> \>{\bf if} Threatens($S_c$, $S_i \rightarrow S_j$) {\bf
  then}\\
14. \> \> \> \>{\bf DEMOTE:} Add\_Causal\_Link($S_c$, $S_i$, $\cal P$)\\
15. \> \>{\bf for} $c \leftarrow j+1$ up-to $n$ {\do}\\
16. \> \> \>{\bf if} Threatens($S_c$, $S_i \rightarrow S_j$) {\bf then}\\
17. \> \> \> \>{\bf PROMOTE:} Add\_Causal\_Link($S_j$, $S_c$, $\cal P$)\\
\end{tabbing}
\hrule
}}
\caption{The \textsc{Sprawl} algorithm.}
\label{alg:po}
\end{table}

%%%%%%%%%%%%   RESOLVING THREATS  %%%%%%%%%%%%
\subsection{Resolving Threats}
\label{sub:resolvethreats}
We rely heavily on the totally ordered plan to help us resolve threats.  There
are three ways to resolve threats in a plan with conditional effects,
as described in~\cite{ucpop}:
\begin{enumerate}
\item{{\sf Promotion}} moves the threatened operators
  before the threatening operator;
\item{{\sf Demotion}} moves the threatened operator after
  the threatening operator;
\item{{\sf Confrontation}} may take place when the threatening
  effect is conditional. It adds preconditions to the threatening
  operator to prevent the effect causing the threat from occurring.
\end{enumerate}
To find all possible partial orderings, all these possibilities should be
explored. However, since we are provided the totally ordered plan, we do not
need to search at all to find a feasible way to resolve the threat; we
can simply resolve it in the same way it was resolved in the totally
ordered plan. In fact, if threats are resolved in a different way, then the
resulting partial ordering would not be consistent with the totally
ordered plan.

If, in the totally ordered plan, the threatening operator occurs
before the threatened operators, then promotion should be used to
resolve the threat in the partial ordering. Similarly, if it occurs
after the threatened operators, demotion should be used to resolve the
threat in the partial ordering. If the threatening operator occurs
between the threatened operators in the totally ordered plan, then we
know that confrontation must have been used in the totally ordered
plan to prevent the threatening conditional effect from occurring.
Needs analysis takes care of confrontation with \textit{protection
  needs}, shown in Figure~\ref{fig:spandstheterm} which ensure that
steps that occur between a needed term's creation and use in the
totally ordered plan do not delete the term.


%%%%%%%%%%%%   DISCUSSION   %%%%%%%%%%%%
\section{Discussion}
\label{sec:discussion}

The \textsc{Sprawl} algorithm does not create a partially ordered plan
from scratch; its purpose is to partially order the steps of a given
totally ordered plan to aid in our understanding of the structure of the plan.
Because of this, \textsc{Sprawl} is restricted to partial orderings
consistent with the totally ordered plan.

However, frequently there are many partial orderings consistent with the
totally ordered plan. Here, we discuss the space of possibilities explored by
\textsc{Sprawl} as we have described it, and how that space can be
extended to include all possible partial orderings consistent with the
totally ordered plan.

%%%%%%%%%%%%   CEs CHANGE BTW TOTAL ORDER & PARTIAL ORDER   %%%%%%%%%%%%
\subsection{Active Conditional Effects May Differ from Those in
  Totally Ordered Plan}
\label{sub:activeces}

Though \textsc{Sprawl} is restricted to partial orderings consistent
with the totally ordered plan it is given, this does not mean that all
conditional effects active in the totally ordered plan must be active
in the partial ordering, or vice versa. There are sometimes irrelevant
conditional effects in the totally ordered plan or in the partial
ordering, and \textsc{Sprawl} does not seek to maintain or prevent
these irrelevant effects. The ignore case shown as a totally ordered
plan in Figure~\ref{fig:upi} demonstrates this. In this problem, one
of the active effects in the totally ordered plan is {\sf wet
  shoe}.  However, this effect does not affect the fulfillment of the
goal state, and so is not a relevant effect. In fact, as is shown in
Figure~\ref{fig:ignorepo}, \textsc{Sprawl} would enforce no ordering
constraints between the two steps in its partial ordering. Though the
different orderings produce different final states, the goal terms are
true in each of these final states, so it doesn't matter which occurs.

%%%%%%%%%%%%   R.E.s FEWER IN PO THAN TO   %%%%%%%%%%%%
\subsection{Partial Ordering May Not Include All Relevant Effects in
  Total Ordering}
\label{sub:releffs}

Although, as we discussed, \textsc{Sprawl} is restricted to partial
orderings with no relevant effects not active in the given totally
ordered plan, this does not mean that all relevant effects in the
totally ordered plan must be relevant effects in the partial ordering.
Sometimes, there are several relevant effects in the totally ordered
plan which achieve the same aim. B{\"a}ckstr{\"o}m presented an
example that neatly illustrates this. The totally ordered plan is
shown with its needs tree in Figure~\ref{fig:fullneeds}. In this plan,
two different relevant effects provide the term {\sf q} to step
{\sf c}---both step {\sf a} and step {\sf b} generate
{\sf q}. Choosing a different relevant effect to generate
{\sf q} creates a different partial order. The two partial orders
representing each of the two relevant effect choices are shown in
Figures~\ref{fig:totalpartial} and~\ref{fig:betterpartial}.

\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.80\linewidth]{fullneeds.eps}
    \caption{
      %
      B{\"a}ckstr{\"o}m's example plan, and the needs tree created if
      the algorithm does not terminate branches when they are
      accomplished. Note that the term {\sf q} is accomplished by
      two different steps: {\sf a} and {\sf b}. This means that
      two partial orderings are possible: one in which step {\sf a}
      provides {\sf q} to step {\sf c}, and one in which
      {\sf b} does. If branches are terminated as they are
      accomplished, the accomplished need marked {\sf q*}, which
      represents step {\sf a} providing {\sf q} to step
      {\sf c}, would not be found.
      %
      }
    \label{fig:fullneeds}
  \end{center}
\end{figure*}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.50\columnwidth]{totalpartial.eps}
    \caption{
                                %
      The only partial ordering of B{\"a}ckstr{\"o}m's example plan
      permitted by the presented version of the needs analysis
      algorithm
                                %
      }
    \label{fig:totalpartial}
  \end{center}
\end{figure}
\begin{figure}
  \begin{center}
    \includegraphics[width=.28\columnwidth]{betterpartial.eps}
    \caption{
                                %
      Another partial ordering of B{\"a}ckstr{\"o}m's example plan. If
      we make the discussed modifications to the needs analysis
      algorithm, both this partial ordering and the one shown in
      Figure~\ref{fig:totalpartial} would be represented in the needs
      tree, as shown in Figure~\ref{fig:fullneeds}.
                                %
      }
    \label{fig:betterpartial}
  \end{center}
\end{figure}


%%%%%%%%%%%%   MULTIPLE POs   %%%%%%%%%%%%
\subsection{Finding Multiple Partial Orderings}
\label{sub:multpos}

In the interest of speed, \textsc{Sprawl} finds exactly one partial
ordering and does not search through different partial orderings to
find a ``better'' one according to any measure.  The needs analysis
algorithm shown in Table~\ref{alg:needsanal} produces a needs tree
that encompasses all possible partial orderinsg consistent with the
totally ordered plan, but the version of \textsc{Sprawl} shown in
Table~\ref{alg:po} arbitrarily chooses one possible partial ordering
from those represented by the needs tree. \textsc{Sprawl} can be
modified to search through more possible partial orderings, however,
finding the best partial ordering according to any measure is
NP-complete~\cite{backstrom93harder}.

When an {\sf OR} logical operator is encountered in the needs tree,
\textsc{Sprawl} arbitrarily chooses which of its branches to follow
and ignores the others (Table~\ref{alg:po}, step 8). Instead, we could
search through the possibilities to find the branch that contributes
to the best partial ordering.

If we modify the needs analysis algorithm as discussed above, there is
sometimes more than one way to accomplish a need, as with the need
{\sf q} in Figure~\ref{fig:fullneeds}. \textsc{Sprawl} arbitrarily
chooses one of these ways to be the need's creator in the partial
ordering (Table~\ref{alg:po}, step 8). Again, we could search through all
possibilities instead, and choose the one that contributes to the best
partial ordering.

\textsc{Sprawl} resolves threats in the same way they were resolved in
the totally ordered plan. It is possible instead to search over all
three ways (promotion, demotion and confrontation) to resolve each.
However, the partial ordering will only be consistent with the totally
ordered plan if threats are resolved in the same way.

%%%%%%%%%%%%   DEFINITIONS   %%%%%%%%%%%%
\section{Definitions}
\label{sec:defs}

\paragraph{Totally ordered plan $\cal T$} \textit{consists
  of an initial state, $\cal I$, which is a list of terms that are
  true before the plan begins; a goal state, $\cal G$, which is a list
  of terms that must be accomplished by the plan; and a list of steps,
  $S_1 \ldots S_n$.  Each step has a list of preconditions, or terms
  that must be true before the step is executable; and a list of
  conditional effects, which describe the effects of the step. Each
  conditional effect has a list of conditions and a list of effects,
  which become true after the plan step executes if the conditions of
  the effect were satisfied before the plan step executed. The
  preconditions of the first step in the plan, $S_1$, must be true in
  the initial state $\cal I$; the preconditions of each subsequent
  step $S_i$ must be true after steps $S_1 \ldots S_{i-1}$ execute in
  order; and the terms of the goal state $\cal G$ must be true after
  steps $S_1 \ldots S_n$ execute in order.}

\paragraph{Partial ordering $\cal P$} \textit{A partial
  ordering $\cal P$ of the totally ordered plan $\cal T$ also includes
  a list of {\sf ordering constraints}. Each ordering constraint
  specifies that a given step $S_i$ must come before another step
  $S_j$. The preconditions of the first step in the plan, $S_1$, must
  still be true in the initial state $\cal I$. However, we now demand
  that the preconditions of each subsequent step $S_i$ must be true
  after any possible ordering of the plan steps that ends at $S_i$
  that is consistent with the ordering constraints; and that the terms
  of the goal state $\cal G$ must be true after steps $S_1 \ldots S_n$
  execute in any order consistent with the ordering constraints.}

\paragraph{Annotated Ordering} \textit{an ordering of
  plan steps supplemented with a rationale for (some of) the ordering
  constraints.}
  
\paragraph{Relevant Effect} \textit{an effect which
  affects the fulfillment of a goal term. MORE RIGOROUS DEFINITION IS
  COMING}

\paragraph{Incidental Effect} \textit{an
  effect which does not affect the fulfillment of a goal term. MORE
  RIGOROUS DEFINITION IS COMING}
  
\paragraph{Consistent} \textit{a partial ordering
  $\cal P$ is consistent with the totally ordered plan $\cal T$ if all
  relevant effects active in $\cal P$ are also active in $\cal T$.}

\paragraph{Minimal Annotated Consistent Partial Ordering} \textit{a
  partial ordering consistent with the totally ordered plan in which
  each ordering constraint either provides a term which a relevant
  effect depends upon or prevents a threat to such a term, and in
  which each ordering constraint is annotated with which term it
  provides or protects.}

%%%%%%%%%%%%   CONCLUSIONS   %%%%%%%%%%%%
\section{Conclusions}
\label{sec:concl}

THIS WAS GARBAGE AND NEEDS TO BE REWRITTEN. BASIC MESSAGE, WE HAVE
PRESENTED, YAP YAP YAP, AND WE HOPE IT OPENS THE FIELD FOR PLAN
REUSE/ADAPTATION/RECOGNITION AND AGENT MODELLING TO RICHER DOMAIN
LANGUAGES WITH CEs.

%%%%%%%%%%%%   ACKNOWLEDGEMENTS   %%%%%%%%%%%%
%\section*{Acknowledgements}
%what grant numbers are paying for this? should also mention the NSF.

\bibliographystyle{aaai}
\bibliography{big}

\end{document}