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

\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: 
