\section{Previous Work}
\label{sec:prev}

\subsection{Analyzing Plans with Conditional Effects}
\label{sub:sprawl}


Analyzing example plans and executions is crucial for plan adaptation
and reuse, e.g.,~\cite{nilsson72learnex}, and could be useful for plan
recognition and agent modeling, e.g.,~\cite{kautz86planrecog}. One of
the most common approaches to plan analysis has been to create an
\textit{annotated ordering} of the example plan,
e.g.,~\cite{nilsson72learnex,regnierfade91,rao89thesis,rao92valstruct,veloso94analogy},
in which an ordered plan is supplemented with a rationale for the
ordering constraints. Annotated orderings allow systems not only to
reuse more flexibly 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 modeling
community has shifted from the simple STRIPS domain-specification
language~\cite{fikes71strips} toward richer languages like
ADL~\cite{pednault86formulating} that capture the conditional effects
of real-world actions. Despite the success of the annotated ordering
approach for simple domain-specification languages, it has not been
applied to plans with conditional effects.

In this paper, we introduce the \textsc{Sprawl} algorithm for finding
the rationale behind an observed totally ordered plan: the purpose for
which each step is used in the plan and the reason behind each of the
ordering constraints.  We store this information in a structure we
call a \textit{minimal annotated consistent partial ordering} (MACPO). A
consistent partial ordering $\cal P$ of a totally ordered plan $\cal
T$ is one in which all \textit{relevant} effects (those which affect
the fulfillment of the goal) active in $\cal P$ are also active in
$\cal T$. We call the partial orderings found by \textsc{Sprawl}
\textit{minimal} because they do not include extraneous ordering
constraints; each constraint either:
\begin{itemize}
\item provides a term upon which a relevant effect depends, or
\item prevents a threat to such a term.
\end{itemize}
Finally, \textsc{Sprawl} annotates each ordering constraint with the
term the constraint provides or protects. Given an evaluation function for partial order quality, \textsc{Sprawl} is capable of identifying the optimal MACPO of an
observed total order.


We assume that we are given or that we observe a plan that is valid,
i.e., all preconditions of the steps are satisfied, and, when
executed, the plan produces the goal state. \textsc{Sprawl} links 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 incomparable 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
sub-plans 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 easily to be matched, removed, and used independently.

\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.7\linewidth]{upismall}
    \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*}

Conditional effects make the task much more difficult because they
cause the effects of a given step to change depending on what steps
come before it, thus making step behavior difficult to predict. In
fact, any ordering must treat each conditional effect in the plan in
one of three ways:
\begin{itemize}
\item \textbf{Use:} make sure the effect occurs;
\item \textbf{Prevent:} make sure the effect does not occur;
\item \textbf{Ignore:} don't care whether the effect occurs or not.
\end{itemize}
Figure~\ref{fig:upi} illustrates three totally ordered plans that
demonstrate these cases. Note that all three plans have the same
initial state and the same operators. We are able to demonstrate all
three cases by changing only the goals. The preconditions (pre) are
listed, as are the effects, which are represented as conditional
effects $\{a\} \rightarrow b$, {\textit i.e.}, if $a$ then add $b$. A
non-conditional effect that adds a literal $b$ is then represented as
$\{\} \rightarrow b$.  Delete effects are represented as negated terms
({\textit e.g.}, $\{a\} \rightarrow NOT b$). In the first plan, the conditional
effect of {\sf op1} is \textit{used} to generate the goal term {\sf
  c}. In the second plan, it is \textit{prevented} from generating the
term {\sf c}, and in the third plan, the effect is irrelevant, so it
is \textit{ignored}.

Figure~\ref{fig:upipo} shows the annotated partial orderings generated
by \textsc{Sprawl} for each of these cases. The ordering constraints
are annotated with a rationale explaining why they are necessary.
Although the plans for these three cases are composed of the same
steps, \textsc{Sprawl} reveals that the partial orderings are very
different. In the ``use'' case, \textsc{Sprawl} identifies that {\sf
  op2} threatens the goal term {\sf c}, which is created by {\sf op1},
and enforces the ordering {\sf op1 $\rightarrow$ op2} to protect {\sf
  c}. In the ``prevent'' case, \textsc{Sprawl} identifies that the step
{\sf op1} must not be able to execute the conditional effect that adds
the term {\sf c}, and so ensures that the condition of this effect,
the term {\sf b}, is not true before the step executes. In this way,
\textsc{Sprawl} finds the ordering constraint \mbox{\sf op2
  $\stackrel{NOT b}{\rightarrow}$ op1}. It also finds that the {\sf
  START} step, since it adds {\sf b}, is a threat to this link, and
must therefore come before {\sf op2}. Finally, \textsc{Sprawl}
identifies that, in the ``ignore'' case, the conditional effect is
irrelevant, so {\sf op1} and {\sf op2} may run in parallel.

Treating \textit{any} conditional effect in a plan in a different way
will result in a different partial ordering, creating exponentially
(in the number of conditional effects) many partial orderings, many of
which may be invalid.~\footnote{The number of possible partial
  orderings is also exponential in the number of steps and the number
  of conditions on each step.} One way to deal with this difficulty 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 analyze the totally ordered plan to discover which
conditional effects are relevant. This allows us to ignore incidental
conditional effects in the totally ordered plan.

\begin{figure*}[ht!]
  \begin{center}
    \includegraphics[width=.5\columnwidth]{upismallpo}
    \caption{
      %
      The annotated partially orderings generated by \textsc{Sprawl}
      for the three totally ordered plans shown in
      Figure~\ref{fig:upi}.
      %
      }
    \label{fig:upipo}
  \end{center}
\end{figure*}

Instead of finding the optimal partially ordered plan to solve a given
problem, we chose to focus on finding optimal partial orderings
\textit{consistent} with 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. Using this information reduces the search
required to solve the problem. The second is that for many applications,
including plan modification and reuse and agent modeling, 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).

%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 that affect the fulfillment of the
%goal terms---those that provide for or protect relevant effects.
%\textsc{Sprawl} achieves this via a two-phased approach. It first uses
%needs analysis to identify the relevant effects of each operator and
%the needs of each operator (which terms must be true before the
%operator executes in order to ensure that the relevant effects occur).
%\textsc{Sprawl} is able to use this to find the annotated partial
%order by treating the operators like they have no conditional
%effects---using the needs as preconditions and the relevant effects as
%non-conditional effects.

\subsubsection{Needs Analysis}
\label{sec:needs}

Needs analysis, the first step of the \textsc{Sprawl} algorithm,
computes a tree of needs for the totally ordered plan. We first
create a goal step called {\sf FINISH} with the terms of the goal
state as preconditions.  Needs analysis 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 afterward. Then it
calculates which need to be true before the second-to-last plan step
in order for \textit{those} terms to be true.  This calculation is
executed for each step of the plan, starting from the last step and
finishing at the {\sf START} step, creating a tree of ``needs.'' This
needs tree allows us to identify the relevant effects of a given step
and most of the dependencies in the plan.  However, not all threats
are identified in Needs Analysis; \textsc{Sprawl} uses the needs tree
to calculate the remaining threats.

\paragraph{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. The needs tree
consists of three kinds of needs:
\begin{enumerate}
\item{\textbf{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. For example, the precondition needs
  of the {\sf FINISH} step are the goals of the plan.
\item{\textbf{Existence Needs:}} terms that must be true before a step $n$
  in order for $n$ to create a particular term or to maintain a
  previously existing term are called \textit{existence needs} of the
  term at the step $n$. In the ``use'' example in
  Figure~\ref{fig:upipo}, one existence need of the term {\sf c} at the
  step {\sf op1} is {\sf b}, since {\sf op1} will generate {\sf c} if
  {\sf b} is true before it executes.
\item{\textbf{Protection Needs:}} terms that must be true before step
  $n$ in order for $n$ not to delete a particular term are called
  \textit{protection needs} of the term at the step $n$. In the
  ``prevent'' example in Figure~\ref{fig:upipo}, one protection need
  of the term {\sf NOT c} at the step {\sf op1} is {\sf NOT b}, since
  if {\sf NOT b} is not true before step {\sf op1}, then {\sf op1}
  will add {\sf c} (thereby deleting {\sf NOT c}).
\end{enumerate}

For the sake of simplicity, instead of abstract plan steps, we will
illustrate the three kinds of needs using plan steps from a domain in
which we have a sprinkler that, if on, can wet the yard as well as any
object that may be in the yard.  Figure~\ref{fig:sprinkle} shows the
operator {\sf sprinkle front-yard}. The term {\sf on sprinkler} is a
\textit{precondition need} of the step {\sf sprinkle front-yard}.

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

To illustrate \textit{existence needs}, let us assume that, after
executing the step {\sf sprinkle front-yard}, {\sf wet shoe} must be
true. This could be accomplished in two ways:
\begin{itemize}
\item by ensuring that {\sf at shoe front-yard} was true before {\sf
    sprinkle front-yard} executed, or
\item by ensuring that {\sf wet shoe} was already true before {\sf
    sprinkle front-yard} executed, as shown in
  Figure~\ref{fig:createlogop}.~\footnote{In the remainder of the
  sprinkler examples, we abbreviate the literals {\sf sprinkler} as
  {\sf sp}, {\sf front-yard} as {\sf fy}, {\sf back-yard} as {\sf by},
  and {\sf shoe} as {\sf sh}.}
\end{itemize}
These two terms are called \textit{existence 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}.

\begin{figure*}
  \begin{center}
    \includegraphics[width=.5\columnwidth]{logop}
    \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} existence
needs and \textit{create} existence needs.~\footnote{Precondition
  needs and protection needs are always \textit{create} 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}
existence 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{create} existence need, since we have introduced a new need
in order to satisfy another.

Note that, because there may be multiple ways to ensure the existence
of a term, the description of needs must include the {\sf OR} logical
operator, as shown in Figure~\ref{fig:createlogop}. It must also
include the {\sf AND} logical operator, since we allow a conditional
effect to have multiple conditions, and in order to guarantee that the
effect occurs, we must be able to specify that all must be true.

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 (i.e., prevents {\sf
  wet shoe} from being added).

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}, and indicate this in our diagrams
with a double circle.

\begin{figure*}[htbp]
  \begin{center}
    \includegraphics[width=.5\columnwidth]{accomplish}
    \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*}

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

The needs analysis algorithm is shown in Table~\ref{alg:needsanal}. We
now describe in detail how needs analysis generates the needs of an
individual term. Each needed term {\sf t} must be created and
protected from deletion; we represent this as two branches of needs:
existence needs and protection needs. As explained previously, {\sf
  t}'s existence needs at a particular step {\sf n} are terms which
must be true before step {\sf n} to ensure that {\sf t} is true after
step {\sf n}. There are two possibilities for existence needs: either
{\sf t} may have been true before step {\sf n}, or a conditional
effect of step {\sf n} may generate {\sf t}~\footnote{Non-conditional
  effects of step {\sf n} that add {\sf t} do not add needs---nothing
  needs to be true before step {\sf n} in order for them to occur}.
The protection needs of {\sf t} at step {\sf n} are terms which must
be true before step {\sf n} to ensure that step {\sf n} does not
delete {\sf t}. Prevention needs are therefore negated conditions of
any conditional effects of step {\sf n} that delete {\sf
  t}.~\footnote{If {\sf t} is deleted by a non-conditional effect of
  step {\sf n}, then we call it \textit{unsatisfiable} and end its
  branch of the needs tree.} Figure~\ref{fig:spandstheterm} illustrates
the needs tree created to satisfy each needed term.

\begin{table*}[ht!]
\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\_Existence(c, term)\\
5. \>Find\_Protection(c, term)\\
\\
{\bf procedure} Find\_Existence(c, term):\\
6. \>{\bf for} each conditional effect of $S_c$ {\bf do}\\
7. \> \>{\bf if} effect unconditionally adds term {\bf then}\\
8. \> \> \>term.accomplished $\leftarrow$ {\bf true}\\
9. \> \>{\bf otherwise if} effect conditionally adds term {\bf then}\\
10. \> \> \>Add\_Conditions\_To\_Existence\_Needs(effect, term)\\
11. \> \> \>{\bf for} each condition of effect {\bf do}\\
12. \> \> \> \>Expand\_Term(c-1, condition)\\
\\
{\bf procedure} Find\_Protection(c, term):\\
13. \>{\bf for} each conditional effect of $S_c$ {\bf do}\\
14. \> \>{\bf if} effect unconditionally deletes term {\bf then}\\
15. \> \> \>term.impossible $\leftarrow$ {\bf true}\\
16. \> \> \>return\\
17. \> \>{\bf otherwise if} effect conditionally deletes term {\bf then}\\
18. \> \> \>Add\_Conditions\_To\_Protection\_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=1.0\linewidth]{expand_term}
    \caption{
      %
      The existence needs of a need at a particular step $n$ 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*}[ht!]
  \begin{center}
    \includegraphics[width=1.0\linewidth]{fullcompleteneeds}
    \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 analyze the last
plan step ({\sf sprinkle front-yard}), which has one precondition need
({\sf on sprinkler}), to determine how to satisfy the needs of the
subsequent step {\sf FINISH} ({\sf wet shoe} and {\sf wet
  front-yard}). 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 \textit{maintain} {\sf wet shoe OR}
\textit{create} {\sf at shoe front-yard}. As for {\sf 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. However, the algorithm continues
to look for other ways to accomplish the term. Since there are no
conditional effects of {\sf sprinkle front-yard} that either generate
or delete {\sf wet front-yard}, the algorithm just adds the maintain
existence need, \textit{maintain} {\sf wet fy}.

Next, the algorithm moves back to the previous plan step, {\sf move
  shoe back-yard front-yard}, which has the precondition need {\sf at
  shoe back-yard}. The needs carried over from previous steps are {\sf
  \textit{maintain} wet shoe OR} \textit{create} {\sf at shoe
  front-yard}, the existence needs of {\sf wet shoe} from the {\sf
  FINISH} step; {\sf \textit{maintain} wet front-yard}, the existence
need of {\sf wet front-yard} 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, but, as with {\sf wet fy}
in the previous step, the algorithm adds a maintain existence need
(\textit{maintain} {\sf at shoe front-yard}) in order to find other
ways to accomplish the term. The terms \textit{maintain} {\sf wet
  shoe}, {\sf \textit{maintain} wet front-yard}, and {\sf on
  sprinkler} cannot be prevented or created by this step, so each is
satisfied by a maintain existence need (\textit{maintain} {\sf wet
  shoe}, {\sf \textit{maintain} wet front-yard}, and \textit{maintain}
{\sf on sprinkler}).

Finally, the algorithm reaches the initial state, or {\sf START} step,
and 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 at shoe back-yard}, \textit{maintain} {\sf at shoe front-yard},
\textit{maintain} {\sf wet shoe}, \textit{maintain} {\sf wet
  front-yard}, and \textit{maintain} {\sf on sprinkler}. Two of the
needs, {\sf at shoe back-yard} and \textit{maintain} {\sf on
  sprinkler} are accomplished by the {\sf START} step. However, all of
the other remaining needs are not accomplished by the {\sf START}
step. We call these needs \textit{unsatisfiable} and indicate this in
our diagrams with a dashed circle.
 
The complexity of needs analysis is exponential in the number of
conditional effects and the bound on the number of conditions in each
effect, or $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. The
complexity of needs analysis on a plan with no conditional effects is
linear: $O(mP)$.


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

Table~\ref{alg:po} shows the \textsc{Sprawl} partial ordering
algorithm. \textsc{Sprawl} performs needs analysis, then performs a
depth-first search on the needs tree, adding 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
%blah.

%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.

%Similarly, 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.

%Finally, \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 is only consistent with the
%totally ordered plan if threats are resolved in the same way.

%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, $C$ is the
%bound on the number of conditions per conditional effect, and $A$ is
%the bound on the number of adds and deletes for each step.

\begin{table*}[ht!]
\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, the FINISH operator $S_n+1$ with\\
     \>preconditions set to the goal state, and an evaluation\\
     \>function $F$, to determine the value of partial orderings.\\
{\bf Output}: An optimal minimal annotated consistent partially\\
     \>ordered plan shown as a directed graph $\cal P$.\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
{\bf procedure} {\sc Sprawl}($\cal T$, $S_0$, $S_n+1$, $F$):\\
1. \>tree $\leftarrow$ Needs\_Analysis($\cal T$, $S_0$, $S_n+1$)\\
2. \>tree $\leftarrow$ Trim\_Unaccomplished\_Need\_Tree\_Branches(tree)\\
3. \>queue $\leftarrow$ tree.precondition\_Needs\\
4. \>$\cal P$ $\leftarrow$ Find\_MaxEval\_MACPO(tree, queue, $F$, null)\\
\\
{\bf procedure} Find\_MaxEval\_MACPO(tree, queue, $F$, $\cal P$):\\
5. \>best\_PO $\leftarrow$ $\cal P$\\
6. \>best\_val $\leftarrow$ $F($best\_PO$)$\\
7. \>{\bf if} queue.empty() {\bf then}\\
8. \> \>{\bf return} Resolve\_Threats($\cal P$)\\
9. \>{\bf else}\\
10. \> \>need $\leftarrow$ queue.top()\\
11. \> \>{\bf for} each way of satisfying need {\bf do}\\
12. \> \> \>{\bf if} this way is via a CE {\bf then}\\
13. \> \> \> \>queue.add(CE.conditions)\\
14. \> \> \>queue.add(need.Protection)\\
15. \> \> \>new\_PO $\leftarrow$ Find\_MaxEval\_MACPO(tree, queue,
$F$, $\cal P$\\
\> \> \> \>$+$ Causal\_Link(satisfying step, need.step, need))\\
16. \> \> \>new\_val $\leftarrow$ $F($best\_PO$)$\\
17. \> \> \>{\bf if} new\_val > best\_val {\bf then}\\
18. \> \> \> \>best\_PO $\leftarrow$ new\_PO\\
19. \> \>{\bf return} best\_PO\\
\\
{\bf procedure} Handle\_Threats(tree, $\cal P$):\\  
20. \>{\bf for} each causal link $S_i \rightarrow S_j$ {\bf do}\\
21. \> \>{\bf for} $c \leftarrow 1$ up-to $i-1$ {\bf do}\\
22. \> \> \>{\bf if} Threatens($S_c$, $S_i \rightarrow S_j$) {\bf
  then}\\
23. \> \> \> \>{\bf DEMOTE:} Add\_Causal\_Link($S_c$, $S_i$, $\cal P$)\\
24. \> \>{\bf for} $c \leftarrow j+1$ up-to $n$ {\do}\\
25. \> \> \>{\bf if} Threatens($S_c$, $S_i \rightarrow S_j$) {\bf then}\\
26. \> \> \> \>{\bf PROMOTE:} Add\_Causal\_Link($S_j$, $S_c$, $\cal P$)\\
\end{tabbing}
\hrule
}}
\caption{The \textsc{Sprawl} algorithm.}
\label{alg:po}
\end{table*}

%When an {\sf OR} logical operator is encountered in the needs tree,
%{\sc Sprawl} must explore each branch to find the one that contributes
%to the best MACPO according to the provided evaluation
%function. Similarly, there is sometimes more than one way to
%accomplish a need, as with the need {\sf q} in
%Figure~\ref{fig:fullneeds}. {\sc Sprawl} must search through all
%possibilities to choose the one that contributes to the best partial
%ordering.


%%%%%%%%%%%%   RESOLVING THREATS  %%%%%%%%%%%%
\paragraph{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{weld94leastcommitment}:
\begin{enumerate}
\item{\textbf{Promotion}} moves the threatened operators
  before the threatening operator;
\item{\textbf{Demotion}} moves the threatened operator after
  the threatening operator;
\item{\textbf{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   %%%%%%%%%%%%
\subsubsection{Discussion}
\label{sec:discussion}

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

However, frequently, there are many partial orderings consistent with
the totally ordered plan. \textsc{Sprawl} searches through these
possibilities to find the optimal partial ordering. Here, we discuss
the space of possibilities explored by \textsc{Sprawl} and discuss a
polynomial solution for finding a suboptimal minimal annotated
consistent partial ordering.

%%%%%%%%%%%%   SAME STEPS -> DIFF POS   %%%%%%%%%%%%
\paragraph{Different Total Orderings of the Same Steps May Produce
  Different Partial Orderings}
\label{sub:difftos}

In some cases, 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. For example, the use and prevent cases shown
in Figure~\ref{fig:upi} consist of the same initial states and the
same operators. However, the relevant effects differ. \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. The minimal annotated
consistent partial orderings found by \textsc{Sprawl} are shown in
Figure~\ref{fig:upipo}.

%%%%%%%%%%%%   CEs CHANGE BTW TOTAL ORDER & PARTIAL ORDER   %%%%%%%%%%%%
\paragraph{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 conditional effects in the totally ordered plan is the
effect \mbox{\sf b $\rightarrow$ c} from step $op1$.  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:upipo},
\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   %%%%%%%%%%%%
\paragraph{Finding Multiple Partial Orderings}
\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. Thus, there could be several possible minimal annotated
consistent partial orderings.

Sometimes, there are several relevant effects in the totally ordered
plan that achieve the same aim. B{\"a}ckstr{\"o}m presented an example
that neatly illustrates this~\cite{backstrom93harder}. 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=1.0\linewidth]{fullneeds}
    \caption{
      %
      B{\"a}ckstr{\"o}m's example plan and the needs tree created by
      needs analysis. 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.
      %
      }
    \label{fig:fullneeds}
  \end{center}
  \vspace*{-.3cm}
\end{figure*}

\begin{figure*}[t]
  \begin{minipage}[t]{0.48\linewidth}
    \begin{center}
      \includegraphics[width=.50\columnwidth]{totalpartial}
      \caption{
                                %
        One possible partial ordering of B{\"a}ckstr{\"o}m's example
        plan.
                                %
        }
      \label{fig:totalpartial}
    \end{center}
  \end{minipage} \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \begin{center}
      \includegraphics[width=.28\columnwidth]{betterpartial}
      \caption{
                                %
        Another partial ordering of B{\"a}ckstr{\"o}m's example plan,
        found by {\sc Sprawl} when the evaluation function favors
        shorter partial orderings.
                                %
        }
      \label{fig:betterpartial}
    \end{center}
  \end{minipage}
\end{figure*}


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

%In the interest of speed, \textsc{Sprawl} finds exactly one minimal
%annotated consistent partial ordering and does not search through
%different choices 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 orderings
consistent with the totally ordered plan, and \textsc{Sprawl} searches
through these orderings to identify the optimal one according to a
given measure. However, finding the optimal partial ordering ``under
reasonable optimality criteria'' has been shown to be
NP-hard~\cite{backstrom93harder}. In Table~\ref{alg:poly}, we provide
a polynomial-time algorithm for finding one (not necessarily optimal)
minimal annotated consistent partial ordering. This algorithm is a
variation on the one presented by~\cite{veloso90nonlin}, however, in
order to handle conditional effects, we must calculate the state
between each step to determine whether the conditional effects were
active in the totally-ordered plan.

\begin{table*}[h!]
\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 minimal annotated consistent partially\\
     \>ordered plan shown as a directed graph $\cal P$.\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
{\bf procedure} Find\_Any\_MACPO($\cal T$, $S_0$, $S_n+1$):\\
1. \>Calculate intermediate states $T_1 .. T_n+1$,\\
\> \> where $T_i$ is the state after step $S_{i-1}$\\
2. \>Use states $T_1 .. T_n+1$ to identify CEs active in $\cal T$\\
3. \>{\bf for} step $S_i$ $\leftarrow$ $S_n+1$ downto $S_1$ {\bf do}\\
4. \> \>{\bf for} all $P_{i_j}$ preconditions of $S_i$ {\bf do}\\
5. \> \> \>Use states $T_1 .. T_i$ to find last producer of
$P_{i_j}$\\
6. \> \> \>Add\_Causal\_Link(producer, $S_i$, $P_{i_j}$, $\cal P$)\\
7. \> \> \>{\bf if} $P_{i_j}$ was produced via a CE {\bf then}\\
8. \> \> \> \>add conditions of CE to preconditions of producer step\\
9. \>return Resolve\_Threats($\cal P$)
\end{tabbing}
\hrule
}}
\caption{A polynomial-time algorithm for finding one (not necessarily
  optimal) MACPO}
\label{alg:poly}
\end{table*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Automatically Acquiring Planning Templates from Example
  Plans}
\label{sub:template}

Planning is a powerful tool for action selection, since it offers a
guarantee that a proposed plan achieves an agent's goals. If
efficient, agents could re-plan to deal with unexpected situations.
However, general-purpose planning is too slow to use in most real-time
systems and does not scale to large problems. In order for planning to
be feasible in these situations, some knowledge about the domain being
solved must be used in the planning process, either by using a
domain-specific planner or by using domain-specific knowledge to
narrow the search.

Many researchers have focused on learning domain-specific control
knowledge for planning automatically, usually in the forms of control
rules, macro operators, and plan case libraries. There have also been
several efforts focusing on writing domain-specific planners to
quickly solve planning problems in particular domains without
resorting to generative planning. These programs are currently
handwritten, but this process is tedious and often quite difficult.

We introduce the \distill algorithm, which automatically extracts
these domain-specific planning programs (which we call
\textit{templates}) from example plans, and show how to use them to
solve planning problems. We call these domain-specific planning
programs \textit{templates}. Table~\ref{alg:gripper-small} shows a
simple example template that solves all problems in the gripper domain
that involve moving balls from one room to another.

\begin{table*}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\mywhile (\ingoal({\sf at(?1:ball ?2:room)}) \myand \\
\> \> \incur({\sf at(?1:ball ?3:room)}) \myand \\
\> \> \mynot \mysame({\sf ?2:room ?3:room}) \myand \\
\> \> \incur({\sf at-robby(?5:room)})) \mydo \\
\> \myif (\mynot \mysame({\sf ?3:room ?5:room})) \mythen \\
\> \> {\sf move(?4 ?5 ?3)}\\
\> {\sf pick(?1 ?4 ?3)}\\
\> {\sf move(?4 ?3 ?2)}\\
\> {\sf drop(?1 ?4 ?2)}
\end{tabbing}
\hrule
}}
\caption{A simple template that solves all gripper-domain
  problems involving moving balls from one room to another.}
\label{alg:gripper-small}
\end{table*}

In some domains, finding optimal solutions is NP-complete. Therefore,
templates learned automatically from a finite number of example plans
cannot be guaranteed to find optimal plans. Our goal is to extend the
\textit{solvability horizon} for planning by reducing planning times
and allowing much larger problem instances to be solved. We believe
that post-processing plans can help improve plan quality.

Our work on the \distill algorithm for learning templates focuses on
converting new example plans into templates in if-statement form and
merging them, where possible. Our results show that merging templates
produces a dramatic reduction in space usage compared to case-based or
analogical plan libraries. We also show that by constructing and
combining the if statements appropriately, we can achieve automatic
\textit{situational generalization}, which allows templates to solve
problems that have not been encountered before without resorting to
generative planning or requiring adaptation.

We first formalize the concept of templates. Next, we present our
novel \distill algorithm for learning templates from example plans and
present our results. We then discuss how to use templates to solve
planning problems.

%Planning is a very powerful tool for action selection, since it offers
%a guarantee that a proposed plan achieves an agent's goals and also
%allows agents to deal with unexpected situations without requiring the
%agent programmers to have thought of every eventuality.  However,
%general-purpose planning is too slow to use in most real-time systems
%and does not scale to large problems. In order for planning to be
%feasible in these situations, some knowledge about the domain being
%solved must be used in the planning process, either by using a
%domain-specific planner or by using domain-specific knowledge to
%narrow the search. A lot of research has focused on learning
%domain-specific control knowledge for planning automatically, usually
%in the forms of control rules, macro operators, and plan case
%libraries.

%We believe domain-specific ``programs'' exist that can quickly solve
%planning problems in many domains without resorting to generative
%planning. These programs could be written by hand, but this is tedious
%and often quite difficult. In this paper, we introduce the \distill
%algorithm, which automatically extracts these domain-specific programs
%(which we call \textit{templates}) from example plans, and show how to
%use templates to solve planning problems. Table~\ref{alg:gripper-small}
%shows a very simple example template that solves all problems in the
%gripper domain that involve moving balls from one room to another.

%\begin{table}[htb]
%\hrule
%{\small
%\noindent\begin{tabbing}
%\=~~~~~~~~~~\=\=\+\kill
%\end{tabbing}
%\vspace{-0.5cm}
%{\small
%\begin{tabbing}
%\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
%\mywhile (\ingoal({\sf at(?1:ball ?2:room)}) \myand \\
%\> \> \incur({\sf at(?1:ball ?3:room)}) \myand \\
%\> \> \mynot \mysame({\sf ?2:room ?3:room}) \myand \\
%\> \> \incur({\sf at-robby(?5:room)})) \mydo \\
%\> \myif (\mynot \mysame({\sf ?3:room ?5:room})) \mythen \\
%\> \> {\sf move(?4 ?5 ?3)}\\
%\> {\sf pick(?1 ?4 ?3)}\\
%\> {\sf move(?4 ?3 ?2)}\\
%\> {\sf drop(?1 ?4 ?2)}
%\end{tabbing}
%\hrule
%}}
%\caption{A simple template that solves all gripper-domain
%  problems involving moving balls from one room to another.}
%\label{alg:gripper-small}
%\end{table}

%In some domains, finding optimal solutions is NP-complete. Therefore,
%templates learned automatically from example plans cannot be
%guaranteed to find optimal plans. Our goal is to extend the
%\textit{solvability horizon} for planning. We believe that
%post-processing plans can help improve plan quality.

%\fixme{insert related work here. should the rest of this paragraph
%  just go if we keep the (now smaller) related work section? Our work
%  on template learning has three goals: to make planning feasible in
%  complex and real-time domains and for large problems; to reduce the
%  storage and search problem experienced by many learning algorithms
%  for planning by exploiting the fact that many plans have similar
%  subsections and storing these sections only once, and by using loops
%  to capture repeated structures in plans rather than storing the
%  entire sequence; and to couple the predictive power of planning with
%  the ability to model and reason about observed agent behavior and
%  characteristic behavior patters \fixme{gal: i especially need your
%    help HERE}.}

%Our work on the \distill algorithm for learning templates focuses on
%converting new example plans into templates in if-statement form and
%merging them, where possible. Our results show that merging templates
%produces a dramatic reduction in space usage compared to case-based or
%analogical plan libraries. We also show that by constructing and
%combining the if statements appropriately, we can achieve
%\textit{situational generalization}, which allows templates to solve
%problems that have not been encountered before.

%We first formalize the concept of templates. Next, we present our
%novel \distill algorithm for learning templates from example plans and
%present our results. We then discuss how to use templates to solve
%planning problems. Finally, we explore future work and present our
%conclusions.

%In this paper, we introduce templates, automatically-generated
%domain-specific planning programs composed of ordinary
%programming-language constructs like if statements, while loops and
%equality checks, that could generate plans without any planning
%search. Templates are able to capture and reuse the sequences and
%structures in observed plans to represent their planning knowledge
%compactly and reduce the search and storage problem that plagues much
%learning work in planning. They may also be used to generalize
%knowledge automatically via while loops and situational
%generalization. We investigate the problem of learning templates
%automatically from example plans and applying them to new planning
%problems. We allow operators with conditional effects, but assume that
%complete operator descriptions are known, since previous work has
%shown that they are learnable from example traces and
%practice~\cite{gil92thesis,wang96thesis}.


%%%%%%%%%%%%   WHAT IS A TEMPLATE   %%%%%%%%%%%%
\subsubsection{Defining Templates}
\label{sec:definition}

A template is a domain-specific planning program that, given a
planning problem (initial and goal states) as input, either returns a
plan that solves the problem or returns failure, if it cannot do so.
Templates are composed of the following programming constructs and
planning-specific operators:
\begin{itemize} \itemsep 0pt
\item \mywhile loops;
\item \myif, \mythen, \myelse statements;
\item logical structures (\myand, \myor, \mynot);
\item \ingoal, \incur, \ininit operators;
\item \mysame operator;
\item plan predicates; and
\item plan operators.
\end{itemize}

In order for templates to capture repeated sequences in while loops
and to determine that the same sequence of operators in two different
plans has the same conditions, they must update a current state as
they execute by simulating the effects of the operators they add to
the plan. Without this capability, we would be unable to use such
statements as: \mywhile (condition holds) \mydo (body).
Therefore, in order to use a template, it must be possible to simulate
the execution of the plan. However, since template learning requires
full models of the planning operators, this is not an additional
problem.

%\fixme{explain why they output t.o. plans. is this too trivial for
%  words?}

Table~\ref{alg:gripper-small} shows a template that solves all
gripper-domain~\cite{AIMag-AIPS98} problems involving moving balls
between rooms. The template is composed of one while loop: while there
is an ball that is not at its goal location, move to the ball (if
necessary), pick up the ball, move to goal location of the object, and
drop the ball.


%%%%%%%%%%%%   LEARNING TEMPLATES   %%%%%%%%%%%%
\subsubsection{Learning Templates: the \distill Algorithm}
\label{sec:learning}

The \distill algorithm, shown in Table~\ref{alg:distill}, learns
templates from sequences of example plans, incrementally adapting the
template with each new plan.  One benefit of online learning is that
it allows a learner with access to a planner to acquire templates on
the fly in the course of its regular activity.  And because templates
are learned from example plans, they reflect the \textit{style} of
those plans, thus making them suitable not only for planning, but also
for agent modeling.

\begin{table*}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: Minimal annotated consistent partial order $\cal P$,\\
\> current template $T_i$.\\
{\bf Output}: New template $T_{i+1}$, updated with $\cal P$\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myprocedure \distill($\cal P$, $T_i$):\\
\> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$,
${T_i}.variables$, $\emptyset$)\\
\> \myuntil match \myor can't match \mydo \\
\> \> \myif $\cal A = \emptyset$ \mythen \\
\> \> \> can't match \\
\> \> \myelse \\
\> \> \> $\cal N$ \myassign Make\_New\_If\_Statement(Assign($\cal P$, $\cal A$))\\
\> \> \> match \myassign Is\_A\_Match($\cal N$, $T_i$) \\
\> \> \myif \mynot can't match \myand \mynot match \mythen \\
\> \> \> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$, ${T_i}.variables$, $\cal A$) \\
\> \myif can't match \mythen \\
\> \> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$, ${T_i}.variables$, $\emptyset$) \\
\> \> $\cal N$ \myassign Make\_New\_If\_Statement(Assign($\cal P$, $\cal A$))\\
\> $T_{i+1}$ \myassign Add\_To\_Template($\cal N$, $T_i$) \\
\\
\myprocedure Make\_New\_If\_Statement($\cal P_{\cal A}$):\\
\> $N$ \myassign empty if statement\\
\> \myfor all terms $t_m$ in initial state of $\cal P_{\cal A}$ \mydo \\
\> \> \myif exists a step $s_n$ in plan body of $\cal P_{\cal A}$
\suchthat \\
\> \> \> \> $s_n$ needs $t_m$ \myor goal state of $\cal P_{\cal A}$
needs $t_m$ \mythen \\
\> \> \> Add\_To\_Conditions($N$, \incur($t_m$))\\
\> \myfor all terms $t_m$ in goal state of $\cal P_{\cal A}$ \mydo \\
\> \> \myif exists a step $s_n$ in plan body of $\cal P_{\cal A}$ \suchthat \\
\> \> \> \> $t_m$ relies on $s_n$ \mythen \\
\> \> \> Add\_To\_Conditions($N$, \ingoal($t_m$))\\
\> \myfor all steps $s_n$ in plan body of $\cal P_{\cal A}$ \mydo \\
\> \> Add\_To\_Body($N$, $s_n$)\\
\> \myreturn $N$\\
\\
\myprocedure Is\_A\_Match($\cal N$, $T_i$):\\
\> \myfor all if-statements $I_n$ in $T_i$ \mydo\\
\> \> \myif $\cal N$ matches of $I_n$ \mythen\\
\> \> \> \myreturn \mytrue\\
\\
\myprocedure Add\_To\_Template($\cal N$, $T_i$):\\
\> \myfor all if-statements $I_n$ in $T_i$ \mydo\\
\> \> \myif $\cal N$ matches $I_n$ \mythen\\
\> \> \> $I_n$ \myassign Combine($I_n$, $\cal N$)\\
\> \> \> \myreturn\\
\> \myif $\cal N$ is unmatched \mythen\\
\> \> Add\_To\_End($\cal N$, $T_i$)\\
\end{tabbing}
\hrule
}}
\caption{The \distill algorithm: updating a template with a new observed plan.}
\label{alg:distill}
\end{table*}

\distill can handle domains with conditional effects, but we assume
that it has access to a complete model of the operators and to a
minimal annotated partial ordering of the observed total order plan.
Previous work has shown that operator models are learnable through
examples and experimentation~\cite{CarGil90,Wang-aips94} and has
shown how to find minimal annotated partial orderings of
totally-ordered plans given a model of the operators~\cite{sprawl}.

The \distill algorithm converts observed plans into templates
(see ``Converting Plans into Templates'') and
merges them by finding templates with overlapping solutions and
combining them (see ``Merging Templates''). In
essence, this builds a highly compressed case library. However,
another key benefit comes from merging templates with overlapping
solutions: this allows the template to find \textit{situational
  generalizations}~\cite{sitgen} for individual sections of the plan,
thus allowing it to reuse those sections when the same situation is
encountered again, even in a completely different planning problem.
%\fixme{is this clear or just random big-word spewing?}


%%%%%%%%%%%%   GENERALIZING SITUATIONS   %%%%%%%%%%%%
\paragraph{Generalizing Situations}
\label{sub:generalizingsits}

We make several assumptions about what makes one planning
\textit{situation} different than another, and about how the observed
planner will solve problems. We assume that two objects of the same
type will be treated the same by the planner. Thus, two situations are
equivalent if they contain the same number and types of objects in the
same relationships. We assume that the planner will respond to
equivalent situations with the same plan. This allows the \distill
algorithm to identify common situations that occur in the solutions of
several planning problems, and to extract their solutions for
independent use in other problems. %\fixme{should this be a separate
%  section or a normal paragraph? is this too repetitive with the
%  previous paragraph?}


%%%%%%%%%%%%   CONVERTING PLANS INTO TEMPLATES   %%%%%%%%%%%%
\paragraph{Converting Plans into Templates}
\label{sub:conversion}

The first step of incorporating an example plan into the template is
converting it into a parameterized if statement. First, the entire
plan is parameterized. \distill chooses the first parameterization
that allows part of the solution plan to match that of a
previously-saved template. If no such parameterization exists, it
randomly assigns variable names to the objects in the
problem.~\footnote{Two discrete objects in a plan are never allowed to
  map onto the same variable.  As discussed
  in~\cite{nilsson72learnex}, this can lead to invalid plans.}

Next, the parameterized plan is converted into a template, as
formalized in the procedure Make\_New\_If\_Statement in
Table~\ref{alg:distill}. The conditions on the new if statement are
the initial- and goal-state terms that are \textit{relevant} to the
plan. Relevant initial-state terms are those which are needed for the
plan to run correctly and achieve the goals~\cite{veloso94book-thesis}.
Relevant goal-state terms are those which the plan accomplishes. We
use a minimal annotated partial ordering~\cite{sprawl} of the observed
plan to compute which initial- and goal-state terms are relevant.  The
steps of the example plan compose the body of the new if statement. We
store the minimal annotated partial ordering information for use in
merging the template into the previously-acquired knowledge base.

Figure~\ref{fig:explan} shows an example minimal annotated partially
ordered plan with conditional effects. Table~\ref{alg:explantemplate}
shows the template \distill creates to represent that plan. Note that
the conditions on the generated if statement do not include all terms
in the initial and goal states of the plan. For example, the template
does not require that {\sf e(z)} be in the initial and goal states of
the example plan. This is because the plan steps do not generate {\sf
  e(z)}, nor do they need it to achieve the goals.  Similarly, {\sf
  b(x)} and the conditional effects that could generate the term {\sf
  c(x)} or prevent its generation are also ignored, since it is not
relevant to achieving the goals.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.60\columnwidth]{exampleplan}
    \caption{
                                %
      An example plan. The preconditions (pre) are listed, as are the
      effects, which are represented as conditional effects $a
      \rightarrow b$, i.e., if $a$ then add $b$. A non-conditional
      effect that adds a literal $b$ is then represented as $\{\}
      \rightarrow b$.  Delete effects are represented as negated terms
      (e.g., $\{a\} \rightarrow NOT b$.
                                %
      }
    \label{fig:explan}
  \end{center}
\end{figure}

\begin{table*}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myif (\incur({\sf f(?0:type1)}) \myand \\
\> \> \incur({\sf g(?1:type2)}) \myand \\
\> \> \ingoal({\sf a(?0:type1)}) \myand \\
\> \> \ingoal({\sf d(?1:type2)})) \mythen \\
\> {\sf op1}\\
\> {\sf op2}
\end{tabbing}
\hrule
}}
\caption{The template \distill would create to represent the plan
  shown in Figure~\ref{fig:explan}.}
\label{alg:explantemplate}
\end{table*}


%%%%%%%%%%%%   MERGING PLANS INTO THE TEMPLATE   %%%%%%%%%%%%
\paragraph{Merging Templates}
\label{sub:merging}

The merging process is formalized in the procedure Add\_To\_Template
in Table~\ref{alg:distill}. The templates learned by the \distill
algorithm are sequences of non-nested if statements. To merge a new
template into its knowledge base, \distill searches through each of
the if statements already in the template to find one whose body (the
solution plan for that problem) matches that of the new problem. We
consider two plans to match if:
\begin{itemize}
\item one is a sub-plan of the other, or
\item they overlap: the steps that end one begin the other.
\end{itemize}
If such a match is found, the two if statements are combined. If no
match is found, the new if statement is simply added to the end of the
template.

\newcommand{\myifcase}[1]{{\it if}$_{#1}$}%
%
We will now describe how to combine two if statement templates,
\myifcase{1}$ = $ \myif $x$ \mythen $abc$ and \myifcase{2}$ = $ \myif
$y$ \mythen $b$, when the body of \myifcase{2} is a sub-plan of that
of \myifcase{1}. This process is illustrated in
Figure~\ref{fig:case3}.~\footnote{Combining two if statements with
  overlapping bodies is similar. It is illustrated in
  Figure~\ref{fig:case4}}. For any set of conditions $C$ and any step
$s$ applicable in the situation $C$, we define $C_s$ to be the set of
conditions that hold after step $s$ is executed in the situation $C$.
We also define a new function, $Relevant(C, s)$, which, for any set of
conditions $C$ and any plan step $s$, returns the conditions in $C$
that are relevant to the step $s$.

As shown in Figure~\ref{fig:case3}, merging \myifcase{1} and
\myifcase{2} will result in three new if statements. We will label
them \myifcase{3}, \myifcase{4}, and \myifcase{5}. The body of
\myifcase{3} is set to $a$ and its conditions are $Relevant(x, a)$.
The body of \myifcase{4} is $b$ and its conditions are $Relevant(x_a,
b)$ \myor $Relevant(y, b)$.~\footnote{Note that, though $Relevant(x,
  a) \subseteq x$, $Relevant(y, b) = y$.} Finally, the body of
\myifcase{5} is $c$ and its conditions are $Relevant(x_ab, c)$.
Whichever of \myifcase{1} or \myifcase{2} is already a member of the
template is removed and replaced by the three new if statements.

\begin{figure*}[t]
  \begin{minipage}[t]{0.48\linewidth}
    \begin{center}
      \includegraphics[width=.60\columnwidth]{case3}
      \caption{
                                %
      Combining two if statements when the body of one is a sub-plan
      of the body of the other.
                                %
        }
      \label{fig:case3}
    \end{center}
  \end{minipage} \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \begin{center}
      \includegraphics[width=.6\columnwidth]{case4}
      \caption{
                                %
      Combining two if statements when their bodies are
      overlapping.
                                %
        }
      \label{fig:case4}
    \end{center}
  \end{minipage}
\end{figure*}


%%%%%%%%%%%%   ILLUSTRATIVE RESULTS   %%%%%%%%%%%%
\paragraph{Illustrative Results}
\label{sub:results}

Table~\ref{alg:blocks-learned} shows a template learned by the
\distill algorithm that solves all problems in a blocks-world domain
with two blocks. There are 555 such problems~\footnote{Though the
  initial state must be fully-specified in a problem, the goal state
  need only be partially specified. There are only
  three possible fully specified states in the blocksworld domain with
  two blocks, but there are 185 valid partially specified states.},
but the template needs to store only two plan steps, and \distill is
able to learn it from only 6 example plans.

\begin{table*}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myif (\incur({\sf clear(?1:block)}) \myand \\
\> \> \incur({\sf on(?1:block ?2:block)}) \myand \\
\> \> (\ingoal({\sf on(?2:block ?1:block)}) \myor \\
\> \> \> \ingoal({\sf on-table(?1:block)}) \myor \\
\> \> \> \ingoal({\sf clear(?2:block)}) \myor \\
\> \> \> \ingoal({\sf $\neg$on(?1:block ?2:block)}) \myor \\
\> \> \> \ingoal({\sf $\neg$clear(?1:block)}) \myor \\
\> \> \> \ingoal({\sf $\neg$on-table(?2:block)})\\
\> \> )) \mythen \\
\> {\sf move-from-block-to-table(?1 ?2)}\\
\myif (\incur({\sf clear(?1:block)}) \myand \\
\> \> \incur({\sf clear(?2:block)}) \myand \\
\> \> \incur({\sf on-table(?2:block)}) \myand \\
\> \> (\ingoal({\sf on(?2:block ?1:block)}) \myor \\
\> \> \> \ingoal({\sf $\neg$clear(?1:block)}) \myor \\
\> \> \> \ingoal({\sf $\neg$on-table(?2:block)})\\
\> \> )) \mythen \\
\> {\sf move-from-table-to-block(?2 ?1)}\\
\end{tabbing}
\hrule
}}
\caption{A template learned by the \distill algorithm that solves all two-block
  blocks-world problems.}
\label{alg:blocks-learned}
\end{table*}

Table~\ref{alg:gripper-learned} shows a template learned by the
\distill algorithm to solve all gripper-domain problems with one ball,
two rooms, and one robot with one gripper arm. Although there are 1932
such problems,~\footnote{As previously mentioned, each problem consists
  of one fully-specified initial state (in this case, there are 6
  valid fully-specified initial states), and one partially-specified
  goal state (in this case, there are 322).} the \distill algorithm
is able to learn the template from only five example plans. It
successfully generalizes situations within individual plans for use in
other plans. Also note that only five plan steps (the length of the
longest plan) are stored in the template.

\begin{table*}[h!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
      \myif (\incur({\sf at(?3:ball ?2:room)}) \myand \\
      \> \> \incur({\sf at-robby(?1:room)}) \myand \\
      \> \> (\ingoal({\sf at(?3:ball ?1:room)}) \myor \\
      \> \> \> \ingoal({\sf $\neg$at(?3:ball ?2:room)}) \myor \\
      \> \> \> \ingoal({\sf holding(?3:ball)}) \myor\\
      \> \> \> \ingoal({\sf $\neg$free-arm})\\
      \> \> )) \mythen \\
      \> {\sf Move(?1 ?2)}\\
      \myif (\incur({\sf at(?3:ball ?2:room)}) \myand \\
      \> \> \incur({\sf at-robby(?2:room)}) \myand \\
      \> \> (\ingoal({\sf at(?3:ball ?1:room)}) \myor \\
      \> \> \> \ingoal({\sf $\neg$at(?3:ball ?2:room)}) \myor \\
      \> \> \> \ingoal({\sf holding(?3:ball)}) \myor\\
      \> \> \> \ingoal({\sf $\neg$free-arm})\\
      \> \> )) \mythen \\
      \> {\sf Pick(?3 ?2)}\\
      \myif (\incur({\sf holding(?3:ball)}) \myand \\
      \> \> \incur({\sf at-robby(?2:room)}) \myand \\
      \> \> (\ingoal({\sf at(?3:ball ?1:room)}) \myor \\
      \> \> \> (\ingoal({\sf $\neg$at(?3:ball ?2:room)}) \myand \\
      \> \> \> \> (\ingoal({\sf $\neg$holding(?3:ball)}) \myor\\
      \> \> \> \> \> \ingoal({\sf free-arm})))\\
      \> \> )) \mythen \\
      \> {\sf Move(?2 ?1)}\\
      \myif (\incur({\sf holding(?3:ball)}) \myand \\
      \> \> \incur({\sf at-robby(?1:room)}) \myand \\
      \> \> (\ingoal({\sf at(?3:ball ?1:room)}) \myor \\
      \> \> \> \ingoal({\sf $\neg$holding(?3:ball)}) \myor\\
      \> \> \> \ingoal({\sf free-arm})
      \> \> )) \mythen \\
      \> {\sf Drop(?3 ?1)}\\
      \myif (\incur({\sf at-robby(?1:room)}) \myand \\
      \> \> (\ingoal({\sf at-robby(?2:room)}) \myor\\
      \> \> \> \ingoal({\sf $\neg$at-robby(?1:room)}))\\
      \> \> ) \mythen \\
      \> {\sf Move(?1 ?2)}%\\
\end{tabbing}
\hrule
}}
\caption{A template learned by the \distill algorithm that solves all
  gripper-domain problems involving one ball two
  rooms, and one robot with one gripper.}
\label{alg:gripper-learned}
\end{table*}

%examples.
%truck@1, item@2->truck@2, item@1: mlmum
%truck@1, item@2->item@1, truck@1: mlmu
%truck@1, item@2->truck@1, item@truck: mlm
%truck@1, item@2->truck@2, item@truck: ml
%truck@1, item@1->item@truck: l
%wow; could it solve it only from those 5 plans?? i think so. must
 %check tomorrow. FIXME! CHECK ME!

Our results show that templates achieve a significant reduction in
space usage compared to case-based or analogical plan libraries. In
addition, templates are also able to situationally generalize known
problems to solve problems that have not been seen, but are composed
of previously-seen situations.


%%%%%%%%%%%%   PLANNING   %%%%%%%%%%%%
\subsubsection{Planning with Templates}
\label{sec:planning}

Our algorithm for generating plans from templates is shown in
Table~\ref{alg:plan}. As previously mentioned, while executing the
template, we must keep track of a current state and of the current
solution plan. The current state is initialized to the initial state,
and the solution plan is initialized to the empty plan. Executing the
template consists of applying each of the statements to the current
state. Each statement in the template is either an plan step, an if
statement, or a while loop. If the current statement is a plan step,
make sure it is applicable, then append it to the solution plan and
apply it to the current state. If the current statement is an if
statement, check to see whether it applies to the current state. If it
does, apply each of the statements in its body; if not, go on to the
next statement. If the current statement is a while loop, check to see
whether it applies to the current state. If it does, apply each of the
statements in its body until the conditions of the loop no longer
apply. Then go on to the next statement.

\begin{table*}[h!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: Template $T$, initial state $\cal I$, current state $\cal C$\\
\> (initialized to $\cal I$), and goal state $\cal G$.\\
{\bf Output}: Plan $P$ that solves the given problem.\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myprocedure Apply\_Template($T$, $\cal I$, $\cal C$, $\cal G$):\\
\> $P$ \myassign $\emptyset$\\
\> \myfor each statement $S_n$ in $T$ \mydo \\
\> \> $P$ \myassign $P$ $+$ Apply\_Statement($S_n$, $\cal I$, $\cal C$, $\cal G$)\\
\> \myif $\cal G$ is satisfied by $\cal C$ \mythen \\
\> \> \myreturn $P$\\
\> \myelse \\
\> \> FAIL\\
\\
\myprocedure Apply\_Statement($S$, $\cal I$, $\cal C$, $\cal G$):\\
\> $P$ \myassign $\emptyset$\\
\> \myif $S$ is an if statement \mythen \\
\> \> \myif Applies\_Now($S$, $\cal C$, $\cal G$) \mythen \\
\> \> \> \myfor each statement $S_i$ in the body of $S$ \mydo \\
\> \> \> \> $P$ \myassign $P$ $+$ Apply\_Statement($S_i$, $\cal C$, $\cal G$)\\
\> \myif $S$ is a while statement \mythen \\
\> \> \mywhile Applies\_Now($S$, $\cal I$, $\cal C$, $\cal G$) \mydo \\
\> \> \> \myfor each statement $S_i$ in the body of $S$ \mydo \\
\> \> \> \> $P$ \myassign $P$ $+$ Apply\_Statement($S_i$, $\cal C$, $\cal G$)\\
\> \myif $S$ is a plan step \mythen \\
\> \> \myif \mynot Applicable($S$, $\cal C$) \mythen \\
\> \> \> FAIL\\
\> \> $\cal C$ \myassign Apply\_Step($S$, $\cal C$)\\
\> \> $P$ \myassign $S$\\
\> \myreturn $P$\\
\end{tabbing}
\hrule
}}
\caption{Template-based plan generation.}
\label{alg:plan}
\end{table*}

Sometimes there may be many ways to apply an if statement or a while
loop to the current state. For example, if we have a statement like,
``\myif (\incur({\sf not-eaten(?a:apple)})) \mythen {\sf eat(?a)}'',
and there are several uneaten apples in the current state, it is
unclear which apple should be eaten. However, one of our primary
assumptions is that all objects that match the conditions may be
treated the same, so, in this case, it doesn't matter which apple is eaten.


%%%%%%%%%%%%   FAILURE   %%%%%%%%%%%%
\paragraph{Detecting and Handling Failures}
\label{sub:failure}

There are three ways a template may fail to generate the correct
solution plan. It may have run through the whole template and found no
solution steps at all, though the initial state is not the same as the
goal state. Or, it may have found some plan steps to execute, but, by
the end of the template, did not reach the goal state. Finally, it may
have found some plan steps to execute, but found that they were not
applicable to the current state. A failure is detected when we attempt
to execute steps that are not applicable in the current state or when
the template finishes executing and its final state does not match the
goal state. The way we currently handle failures is by handing the
problem off to a generative planner, and then to add that new solution
to the template.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "proposal"
%%% End: 
