\documentclass{article}
\usepackage{aaai}
\usepackage{times}
%\usepackage{helvet}
%\usepackage{courier}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{algorithm}
\usepackage{ealgorithmic}
\usepackage{dsplanner}
\usepackage{dsplanneric}
\usepackage{epic,eepic,epsfig}
\include{epsf}

\newcommand{\ang}[1]{#1^{\circ}}
\newcommand{\mywhile}{{\bf while} }
\newcommand{\myendwhile}{{\bf endwhile} }
\newcommand{\mylet}{{\bf let} }
\newcommand{\myif}{{\bf if} }
\newcommand{\mythen}{{\bf then} }
\newcommand{\myendif}{{\bf endif} }
\newcommand{\mydo}{{\bf do} }
\newcommand{\myreturn}{{\bf return} }
\newcommand{\myfor}{{\bf for} }
\newcommand{\myuntil}{{\bf until} }
\newcommand{\myelse}{{\bf else} }
\newcommand{\mynot}{{\bf not} }
\newcommand{\myand}{{\bf and} }
\newcommand{\myor}{{\bf or} }
\newcommand{\mytrue}{{\bf true} }
\newcommand{\myfalse}{{\bf false} }
\newcommand{\myprocedure}{{\bf procedure} }
\newcommand{\mygoal}{{\bf goal state} }
\newcommand{\mycur}{{\bf current state} }
\newcommand{\mysame}{{\bf same} }
\newcommand{\ingoal}{{\bf inGoalState} }
\newcommand{\incur}{{\bf inCurState} }
\newcommand{\suchthat}{{\bf such that} }
\newcommand{\myassign}{$\leftarrow$ }
\newcommand{\distill}{{\sc Distill} }
\newcommand{\dsPlanner}{{\sc dsPlanner} }
\newcommand{\loopdistill}{ Loop{\sc Distill} }
\newcommand{\loopdistillnospace}{ Loop{\sc Distill}}
\newcommand{\fixme}[1]{{\bf FIXME: #1}}
\newcommand{\remove}[1]{{\bf I PLAN TO REMOVE THIS ENTIRELY: #1}}
\newcommand{\hide}[1]{}

\graphicspath{{figs/}}

\title{\loopdistillnospace: Learning Looping Domain-Specific Planners from Example Plans}

\author{Elly Winner and Manuela Veloso\\
  Computer Science Department\\ Carnegie Mellon University\\ 5000
  Forbes Avenue\\ Pittsburgh, PA 15213-3891, USA\\ (412) 268-4801\\
  \{elly,mmv\}@cs.cmu.edu}

\begin{document}
\maketitle

%models demonstrated behavior

\begin{abstract}
Because general-purpose planning methods have difficulty with
large-scale planning problems, researchers have resorted to hand
writing domain-specific planners to solve them. An interesting
alternative is to use example plans to demonstrate how to solve
problems in a particular domain and to use that information to
automatically learn domain-specific planners. In this paper, we
present the \loopdistill algorithm for identifing repeated structures in
observed plans and show how to convert looping plans into
domain-specific planners, or dsPlanners. Looping dsPlanners are able
to apply experience acquired from the solutions to small problems to solve
arbitrarily large ones. We show that automatically learned dsPlanners
are able to solve large-scale problems much more effectively than
are state-of-the-art general-purpose planners and are able to solve
problems many orders of magnitude larger than general-purpose planners
can solve.
\hide{Planners are powerful tools for problem solving because they provide a
complete sequence of actions to achieve a goal from a particular
initial state. Classical planning research has addressed this problem
in a domain-independent manner---the same algorithm generates a
complete plan for any domain specification. This generality comes at a
cost; domain-independent planners have difficulty with large-scale
planning problems. To deal with this, researchers have resorted to
hand writing domain-specific planners to solve them. An interesting
alternative is to use example plans to demonstrate how to solve
problems in a particular domain and to use that information to
automatically learn domain-specific planners that model the observed
behavior. In this paper, we present the \loopdistill algorithm for
identifing repeated structures in observed plans and show how to
convert looping plans into domain-specific planners, or
dsPlanners. Looping dsPlanners are able to apply experience acquired
from the solutions to small problems to solve arbitrarily large
ones. We show that automatically learned dsPlanners are able to solve
large-scale problems much more quickly than are state-of-the-art
general-purpose planners and are able to solve problems many orders of
magnitude larger than general-purpose planners can solve.}
\end{abstract}

\section{Introduction}

General-purpose planners have traditionally had difficulty with
large-scale planning problems, although many large-scale problems have
a repetative structure, because they do not capture or reason about
such repetition. Instead, to solve large-scale problems, programmers
have had to rely on the tedious and difficult process of hand writing
special-purpose planners that may precisely encode the repeated
structure. However, example plans are often available, and can
demonstrate this structure.

In previous work, we introduced the concept of automatically-generated
domain-specific planning programs (or dsPlanners) and showed how to
use example plans to learn non-looping dsPlanners, which can solve
problems of limited size~\cite{template2}. Here, we present the novel
\loopdistill algorithm for automatically identifing the repeated
structure of example plans to learn looping dsPlanners. DsPlanners
execute independently of a general-purpose planning program and are
very efficient; they return a solution plan in time that is linear in
the size of the dsPlanner and of the problem, modulo state-matching
effort. We show that looping dsPlanners can solve large-scale planning
problems more quickly than can general-purpose planners and that they
can solve much larger problems than can general-purpose planners. And
because dsPlanners are learned directly from example plans, there is
no need for tedious hand coding.

\hide{Identifying loops in observed plans allows the plans to be reused to
quickly solve arbitrarily large similar problem instances. Our
research focuses on compressing looping plans into compact
domain-specific planning programs that can solve larger and more
complex problems than can current general-purpose planning
techniques. However, loop identification could also be used for other
purposes, such as improving the performance of case-based or
analogical planning methods or identifying promising candidates for
macro learning.}

\hide{In some domains, finding optimal solutions is NP-complete. Therefore,
dsPlanners learned automatically from a finite number of example plans
cannot be guaranteed to find optimal plans. Our goal is to extend the
\emph{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.}

We first discuss related work. We then define dsPlanners and explain
how we use them to generate the solution plans for new problems. Then
we discuss classes of loops, describe our algorithm for identifying
loops in observed plans, and illustrate its behavior with
examples. Next we present the results of using plans with identified
loops as planners and compare this to using state-of-the-art
general-purpose planners. Finally, we present our conclusions.


\section{Related Work}

Many research efforts have sought to automatically improve
general-purpose planning efficiency, most commonly by using learned or
hand-written domain knowledge to reduce generative planning search
e.g.~\cite{Mint:book,rao92valstruct}.
We focus here
on methods that learn and exploit repeated structure within plans.

Case-based and analogical reasoning, e.g.,
~\cite{chef,veloso94book-thesis}, apply planning experience from solving
previous problems to solving a new one. Similarly, the internal
analogy technique~\cite{hickman91internal} reuses the planning
experience gleaned from solving one part of a particular problem to
solving other parts of the same problem.

Iterative and recursive macro operators and control rules, e.g.,
~\cite{shell89iterativemacs,schmid03book}, capture
repetitive behavior and can drastically reduce planning search by
encapsulating an arbitrarily long string of operators. However, unlike
our approach, this technique does not attempt to replace the
generative planner, and so does not eliminate planning search.

Context free grammars have also been used to extract instantiated
patterns in examples that exhibit structural
dependencies~\cite{02oates}, but don't capture how to use these
patterns to solve new problems.

Some work, like our own, has focussed on analyzing example plans to
reveal a strategy for planning in a particular domain. One example of
this approach is BAGGER2, which learns recurrences that capture some
kinds of repetition~\cite{shavlik90recitEBL}. BAGGER2 was able to
learn recurrences from very few example plans, but relied on
background knowledge and wasn't able to capture parallel repetition.

Another example of the strategy-learning approach is the decision
list~\cite{khardon99action}: a list of condition-action pairs derived
from example state-action pairs. This technique also relies on
background knowledge, is able to solve fewer than 50\% of 20-block
Blocksworld problems, and requires over a thousand state-action pairs
to achieve that coverage.

Finally, many researchers have explored hand writing domain-specific
planners, e.g.,~\cite{bacchus01tlplan,nau03shop2}.
These planners are
able to solve more problems than general-purpose planners, and are
able to solve them more quickly~\cite{ipc02results}, but often require
months or years to create.


\section{Defining and Using DsPlanners}

In this section, we explain in detail the form of the dsPlanners our
algorithm learns and how they are used for planning.

\subsection{Defining DsPlanners}
\label{sec:definition}

A dsPlanner 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.
DsPlanners are composed of the following programming constructs and
planning-specific operators:
\begin{itemize} \itemsep 0pt
\item \mywhile loops and \myendwhile statements;
\item \myif, \mythen, \myelse, and \myendif statements;
\item logical structures (\myand, \myor, \mynot);
\item \ingoal and \incur operators;
\item numbered and typed variables;
\item the ``v'' variant indicator for \mywhile loops;
\item plan predicates; and
\item plan operators.
\end{itemize}

Variables are introduced in if-statement and while-loop
conditions. Any objects in the problem which match the conditions may
be assigned to the variables. Those assignments hold thoughout the
conditions and body of the if statement or while loop. While-loop
variable assignments hold throughout the iterations of the loop unless
the variable is labelled ``v'' for variant, in which case it may be
reassigned at each iteration.

DsPlanner~\ref{dsp:gripper-small} shows a dsPlanner that solves all
gripper-domain problems involving moving balls
between rooms. The dsPlanner 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 ball,
and drop the ball.

\begin{dsplanner}[htb!]
\caption{A simple dsPlanner that solves all gripper-domain problems involving moving balls from one room to another.}
\label{dsp:gripper-small}
\begin{dsplanneric}
\WHILE{\incur({\sf at(v?1:ball v?2:room)}) \myand 
	\ingoal({\sf at(v?1:ball v?3:room)})}
	\IF{\incur(\sf{at-robby(?5:room)})}
		\STATE {\sf move(?5 ?2)}
        \ENDIF
	\IF{\incur(\sf{at-robby(?3:room)})}
		\STATE {\sf move(?3 ?2)}
        \ENDIF
	\STATE {\sf pick(?1 ?2)}
	\STATE {\sf move(?2 ?3)}
	\STATE {\sf drop(?1 ?3)}
\ENDWHILE
\end{dsplanneric}
\end{dsplanner}


\subsection{Planning with DsPlanners}
\label{sub:dsplanning}

To use the dsPlanner to solve a planning problem, first initialize the
current state to the initial state and the solution plan to the empty
plan. Then apply each of the statements to the current state. Each
statement in the dsPlanner is either a 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.

\hide{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(?1:apple)})) \mythen {\sf eat(?1)}'',
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.}

A failure is detected when we attempt to execute steps that are not
applicable in the current state or when the dsPlanner finishes
executing and its final state does not match the goal state.
We currently handle failures is by handing the problem off to a
generative planner, and then adding that new solution to the
dsPlanner.


\section{Identifying Loops in Example Plans}

The current version of the \loopdistill algorithm identifies all
non-nested parallel loops over one variable in an observed plan. In
the remainder of this section, we discuss some relevant definitions,
describe in detail the two main portions of the
\loopdistill---identifying loop candidates and creating a
loop from a candidate)---and illustrate the operation of \loopdistill with
two examples.

\subsection{Definitions}
\label{sub:defs}

\paragraph{Subplans} are connected components within in a
partially-ordered plan when the initial and goal states are excluded
(otherwise every set of steps would be a connected component). Two
subplans of a painting and transport domain problem are illustrated in
Figure~\ref{fig:matching}. There are many other possible subplans, but the steps {\sf paint(obj1)} and {\sf paint(obj3)} are not a subplan, since they are not a connected component within the partial ordering.

\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.6\linewidth]{matchingsubplans}
\end{center}
\caption{Two matching subplans of length 1 are surrounded by dotted lines and represent an unrolled loop.}
\label{fig:matching}
\end{figure*}

\hide{\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.8\linewidth]{subplans}
\end{center}
\caption{An example plan in a painting and transport domain is
  shown. In the given plan, some objects need to be painted and some
  need to be loaded into a truck. Painting must be done before
  loading. Three different subplans are surrounded by dotted
  lines. There are many other possible subplans, but the steps {\sf
    paint(obj1)} and {\sf paint(obj3)} are not a subplan, since they
  are not a connected component within the partial ordering.}
\label{fig:subplans}
\end{figure*}}

\paragraph{Matching Subplans} are subplans that satisfy the following criteria:
\begin{itemize} \itemsep 0pt
\item they are non-overlapping,
\item they consist of the same operators,
\item the operators in each subplan are causally linked to each other
  in the same way,
\item they have the same conditions and effects in the plan,
\item they unify with respect to one variable.
\end{itemize}

We also use the term ``matching steps'' as a special case of matching
subplans (in which the subplans are of length one). The two load
operators in Figure~\ref{fig:matching} are matching steps, as are the
two paint operators.

\paragraph{Parallel Subplans} are causally- and threat-independent of
each other. Figure~\ref{fig:matching} shows two parallel subplans
within an example plan.

\hide{\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.8\linewidth]{parallelsubplans}
\end{center}
\caption{Three parallel subplans are surrounded by dotted lines.}
\label{fig:parallelsubplans}
\end{figure*}}

\paragraph{An Unrolled Loop} is a set of matching subplans. One of two
unrolled loops in the painting and transport example is shown in
Figure~\ref{fig:matching}.

\paragraph{A Loop} replaces an unrolled loop in the plan. The body of
the loop consists of the common subplan in the unrolled loop, but with
the differing variable converted into a loop variable. The conditions
on its execution are: that the goal state contains all goal terms that
are supported by steps within the unrolled loop, and that the current
state when the loop is executed contains all the conditions for the
steps within the unrolled loop to execute correctly and support the
goals of the plan.\hide{ The loop represented by the unrolled loop shown in
Figure~\ref{fig:matching} is shown in Figure~\ref{fig:loop}.

\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.8\linewidth]{loop}
\end{center}
\caption{The painting and transport problem after the load loop is identified. The loop is surrounded by dotted lines. The loop variable is written as {\sf ?1}, and ranges over all values that meet the conditions of the loop (in this case, {\sf obj1} and {\sf obj2}). Conditions for the loop are shown above the loop.}
\label{fig:loop}
\end{figure*}}

\paragraph{A Parallel Loop} is a loop in which each iteration of the loop is
causally independent from the others---the iterations may be executed
in any order. The loop shown in Figures~\ref{fig:matching}
and~\ref{fig:loop} is a parallel loop. A loop may also have a
multi-step body with complex causal structure; it may even include
other loops.\footnote{Note that an observed total-order execution of a
multi-step parallel loop need not present the steps of the loop in a
specific order---it could be any topological sort of the loop.} The
current version of \loopdistill is able to identify all non-nested
parallel loops in observed plans.

\paragraph{A Serial Loop} is a loop in which each iteration of the loop is causally linked to the others---there is
a specific order in which the iterations must be executed. For
example, in a package-transport domain, one loop may describe a
particular delivery vehicle visiting different locations, loading and
unloading packages at each one. Each iteration of the loop consists of
loading and unloading packages and then moving from the current
location to a new one. These iterations must be executed in a specific
order since the {\sf move} operations are causally linked.


\subsection{The \loopdistill Algorithm}

The \loopdistill algorithm can handle domains with conditional effects,
but we assume that it has access to a minimal annotated consistent
partial ordering of the observed total order plan. Previous work has
shown how to find minimal annotated consistent partial orderings of
totally-ordered plans given a model of the operators~\cite{sprawl} and
has shown that STRIPS-style operator models are learnable through
examples and experimentation~\cite{CarGil90}, so this assumption is
not restrictive.

The \loopdistill algorithm, formalized in Algorithm~\ref{alg:repeat},
first identifies an unrolled loop (described in the Section
``Identifying Unrolled Loops'') and then converts it into a loop
(described in the Section ``Converting Unrolled Loops into Loops'').
The unrolled loop is then removed from the plan and replaced by the
loop.

\begin{algorithm}[htb!]
\caption{\loopdistill: Identify non-nested one-variable parallel loops in an observed plan.}
\label{alg:repeat}
\begin{ealgorithmic}
\INPUT Minimal annotated partially ordered plan $\cal{P}$.
\OUTPUT $\cal{P}$ with all non-nested one-variable parallel loops identified.
\FORALL{steps $i$ in $\cal{P}$}
	\STATE $M_i \leftarrow$ all parallel matching steps with i in $\cal{P}$
	\IF{$M_i \neq \emptyset$}
		\STATE $\cal{C} \leftarrow$ LargestCommonSubplan($M_i + i$, $\cal{P}$)
		\STATE $\cal{L} \leftarrow$ MakeLoop($\cal{C}$)
		\STATE $\cal{P} \leftarrow \cal{P} - \cal{C}$
		\STATE $\cal{P} \leftarrow \cal{P} + \cal{L}$
        \ENDIF
\ENDFOR
\end{ealgorithmic}
\end{algorithm}

\subsection{Identifying Unrolled Loops}
\label{sub:idcandidate}

The first step in the \loopdistill algorithm is to identify a parallel
unrolled loop: a set of parallel matching subplans within the observed
plan. This process begins with the identification of a set of parallel
matching steps, as described in Algorithm~\ref{alg:repeat}. Next,
\loopdistill finds the largest parallel matching subplan common to at
least two of those steps. This process takes place in the procedure
LargestCommonSubplan, formalized in
Algorithm~\ref{alg:findsubplan}. LargestCommonSubplan recursively
tries every possible expansion of the existing subplan and returns the
one with the most steps per parallel track. First, it identifies the
sets of steps that supply conditions to the steps in each parallel
track of the existing subplan (\emph{StepBack}) and the set of steps
that rely on effects of the steps in each parallel track of the
existing subplan (\emph{StepAhead}). The initial and goal states are
not considered as steps ahead or back. Then, it explores each of these
steps as a possible way to expand the subplan. For each step in
\emph{StepBack} and \emph{StepAhead} for each track, it finds which
other tracks also have a matching step in \emph{StepBack} or
\emph{StepAhead}. If there is at least one other track, the current subplans with the new steps added are recorded as a new unrolled loop.
At the end of this process, there is a set of new unrolled
loops. LargestCommonSubplan is then recursively applied to each of
these to further expand them. The largest resulting candidate is then
returned by the algorithm as the final unrolled loop.

\begin{algorithm}[htb!]
\caption{LargestCommonSubplan: Identify largest parallel matching subplans of an observed plan common to at least two of the given parallel matching subplans.}
\label{alg:findsubplan}
\begin{ealgorithmic}
\INPUT set $\cal{A}$ of parallel matching subplans $S_1 .. S_m$, minimal annotated partially ordered plan $\cal{P}$.
\OUTPUT Set of largest parallel matching subplans of plan $\cal{P}$ common to at least two of $S_1 .. S_m$.
\FORALL{$S_i$ in $S_1 .. S_m$}
	\STATE $StepAhead_{S_i} \leftarrow$ steps causally linked from $S_i$
	\STATE $StepBack_{S_i} \leftarrow$ steps causally linked to $S_i$
\ENDFOR
\STATE $UnrolledLoops \leftarrow \cal{A}$
\FOR{$i = 1$ to $m$}
	\FOR{$NewSteps \leftarrow$ first $StepAhead_{S_i}$, then $StepBack_{S_i}$}
		\FORALL{$s$ in $NewSteps_{S_i}$}
			\STATE $NewExpLoop \leftarrow \{S_i + s\}$
			\FORALL{$j \neq i$}
				\IF{$\exists$ parallel matching step $s'$ in $NewSteps_{S_j}$}
					\STATE $NewExpLoop \leftarrow NewExpLoop + \{S_j + s'\}$
					\STATE $NewSteps_{S_j} \leftarrow NewSteps_{S_j} - s'$
                                \ENDIF
                        \ENDFOR
			\IF{$|NewExpLoop| > 1$}
				\STATE $UnrolledLoops \leftarrow UnrolledLoops + NewExpLoop$
				\STATE $NewSteps_{S_i} \leftarrow NewSteps_{S_i} - s$
                        \ENDIF
                \ENDFOR
       \ENDFOR
\ENDFOR
\FORALL{sets $\cal{N} \neq \cal{A}$ in $UnrolledLoops$}
	\STATE $\cal{N} \leftarrow$ LargestCommonSubplan($\cal{N}, \cal{P}$)
\ENDFOR
\STATE \myreturn set $\cal{N}$ in $UnrolledLoops$ with the largest subplan
\end{ealgorithmic}
\end{algorithm}

\subsection{Converting Unrolled Loops into Loops}
\label{sub:makeloop}

Once an unrolled loop is identified, it must be converted into a
loop. As previously defined, an unrolled loop is a set of matching
subplans differing in only one variable. The body of the loop is the
subplan---with a new loop variable replacing the differing
variable. The conditions for the loop's execution are requirements on
the goal state and on the current state while the loop is executing,
as described in the Section ``Definitions''. The unrolled loop
subplans are then removed from the plan and replaced by the new loop.

\begin{algorithm}[htb!]
\caption{MakeLoop: Create the loop described by the given unrolled loop.}
\label{alg:makeloop}
\begin{ealgorithmic}
\INPUT Unrolled loop: set of matching subplans $S_1 .. S_m$, minimal annotated partially ordered plan $\cal{P}$.
\OUTPUT The loop described by $S_1 .. S_m$.
\STATE \mylet $v_i$ be the variable in $S_i$ that $\forall j$ is not in $S_j$
\STATE \mylet $v_{loop}$ be the loop variable
\STATE $Loop.body \leftarrow$ $S_1$ with $v_{loop}$ replacing $v_1$
\STATE $Loop.conditions \leftarrow \emptyset$
\FORALL{steps $s$ in $Loop.body$}
	\FORALL{conditions $c$ of $s$ not satisfied by steps in $Loop.body$}
		\STATE $Loop.conditions \leftarrow Loop.conditions + CurrentStateContains(c)$
        \ENDFOR
	\FORALL{goal terms $g$ dependent on $s$}
		\STATE $Loop.conditions \leftarrow Loop.conditions + GoalStateContains(c)$
        \ENDFOR
\ENDFOR
\end{ealgorithmic}
\end{algorithm}

\subsection{A Multi-Step Loop Example}

We will now illustrate the operation of the \loopdistill algorithm on
a simple example plan from an artificial domain, illustrated in
Figure~\ref{fig:artificialpo2}. First, \loopdistill searches for a set
of parallel matching steps. It finds the steps {\sf op1(x)} and {\sf
  op1(y)}, which differ only in the values {\sf x} and {\sf y}. These
two one-step parallel matching subplans are then sent to
LargestCommonSubplan, which searches for a larger subplan common to
both of them.

\begin{figure}[htb!]
	%\begin{minipage}[h]{.48\linewidth}
	  \begin{center}
	  \includegraphics[width=.7\columnwidth]{artificialpo2}
          \caption{An example annotated partially ordered plan in an artificial domain that includes a multi-step loop consisting of the steps op1, op2, and op3. The original totally ordered plan could have been any topological sort of this partial ordering.}
          \label{fig:artificialpo2}
	  \end{center}
	%\end{minipage} \hfill
\end{figure}

LargestCommonSubplan begins by finding the \emph{StepAhead} set for
each parallel track. There is one step in \emph{StepAhead} for each
track: {\sf op3(x)} and {\sf op3(y)}, respectively. There are no
elements in the \emph{StepBack} set, since neither of these steps
depends on any other plan step. Because adding these steps preserves
the parallelism and matching of {\sf op1(x)} and {\sf op1(y)}, they
can be added to the subplans. This is the only way to expand the
original subplans, and so is the only element in the list of unrolled
loops.

LargestCommonSubplan is then executed recursively on this new set of
subplans. There are now no elements in \emph{StepAhead} for any track,
but there is one in \emph{StepBack} for each parallel track: {\sf
op2(x)} and {\sf op2(y)}, on which {\sf op3(x)} and {\sf op3(y)}
depend. Adding these steps also preserves the parallelism and matching of the
existing subplans, so they are added as well. Again, this is the only
way to expand the given subplan. LargestCommonSubplan is executed one
last time on this new loop expansion and is unable to find any possible
``steps ahead'' or ``steps back,'' so this loop expansion is returned.

A new loop is then created to represent the common branching
three-step subplan. The loop body is assigned to the common subplan,
with a new loop variable, {\sf lv}, replacing the differing values,
{\sf x} and {\sf y}. The conditions of the loop are that the current
state satisfies the conditions of the steps within it ({\sf s(lv)})
and that the goal state contains the goals supported by the steps in
the loop body ({\sf g(lv)}). The resulting plan is shown in
Figure~\ref{fig:artificialloopsfound}.

\begin{figure}[htb!]
	%\begin{minipage}[h]{0.48\linewidth}
  \begin{center}
	  \includegraphics[width=.7\columnwidth]{artificialloopsfound}
	  \caption{The example plan shown in Figure~\ref{fig:artificialpo2} after the loop has been identified. The loop is surrounded by dotted lines. The loop variable is written as {\sf lv}, and ranges over all values that meet the conditions of the loop (in this case, {\sf x} and {\sf y}). The conditions of the loop are shown above it.}
	  \label{fig:artificialloopsfound}
	  \end{center}
	%\end{minipage}
\end{figure}

\section{Using Looping Plans as Domain-Specific Planners}

Here, we briefly describe how to convert a looping plan into a looping
dsPlanner capable of solving similar problems of arbitrary
size. First, the plan is parameterized: values are replaced by
variables.\footnote{Two discrete objects in a plan are never allowed
  to map onto the same variable as this can lead to invalid plans.}
The planner is a total ordering of the partially ordered plan. Loops
are described as while statements: while the conditions for the loop
hold, execute the body of the loop. Plan steps not contained within
loops are expressed as if statements: if the conditions of the steps
hold, execute the steps. The conditions of a set of steps are the
current-state terms required for the steps to execute correctly and
support the goal-state terms that are dependent on those steps.


\section{Results}

We compare general-purpose planning, using several well-known
general-purpose planners, to planning using learned looping
dsPlanners. To illustrate the effectiveness of identifying loops in
plans, our tests focus on performance on large-scale problems of the
same form as the example plans. We show that the learned dsPlanners
capture the structure of the example plans and are able to apply this
knowledge very efficiently to solving much larger problems. In these
situations, planning using dsPlanners scales orders of magnitude more
effectively than does general-purpose planning.

\subsection{Rocket-Domain Results}

The dsPlanner learned from the rocket-domain example shown in
Figure~\ref{fig:rocket} is shown in dsPlanner~\ref{dsp:rocket}. The
problems on which we tested the planners vary in the number of objects
to transport, but have a single rocket and two locations and consist
of the same initial and goal states: the initial state consists of
{\sf at(rocket, source)}, and for all objects {\sf obj} in the
problem, the initial state contains {\sf at(obj, source)} and the goal
state contains {\sf at(obj,
  destination)}. Figure~\ref{fig:rocketresults} shows the results of
executing several different general-purpose planners and the
\emph{learned} dsPlanner on large-scale problems of this
form. Runtimes for the dsPlanner do not include the time required to
learn the dsPlanner, though this is negligible~\footnote{It takes less
  than a second to learn the dsPlanner for the rocket-domain example
  shown in Figure~\ref{fig:rocket}.}. The learned dsPlanner is orders
of magnitude more efficient on large problems than the
general-purpose planners, and is able to solve problems with more than
60,000 objects in under a minute.

\begin{dsplanner}[htb!]
\caption{dsPlanner based on the rocket domain problem shown in Figure~\ref{fig:rocket}\hide{and~\ref{fig:rocketloopsfound}}. The variable in each loop is indicated by a ``v'' preceeding its name. \hide{In future example dsPlanners, for the sake of compactness, we replace the operator executing and plan updating and returning notation with the name of the operator to execute and add to the plan.}}
\label{dsp:rocket}
\begin{dsplanneric}
\hide{\STATE plan $\leftarrow \{\}$}
\WHILE{\incur({\sf at(v?1:obj, ?2:loc)}) \myand \incur({\sf at(?3:rocket, ?2:loc)}) \myand \ingoal({\sf at(v?1:obj, ?4:loc)})}
\hide{	\STATE operator $\leftarrow$ {\sf load(?1 ?3 ?2)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE{\sf load(?1 ?3 ?2)} \ENDWHILE
\IF{\incur({\sf at(?1:rocket ?2:loc)}) \myand \incur({\sf in(?3:obj ?1:rocket)}) \myand \ingoal({\sf at(?3:obj ?4:loc)})}
\hide{	\STATE operator $\leftarrow$ {\sf fly(?1 ?2 ?4)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE {\sf fly(?1 ?2 ?4)} \ENDIF
\WHILE{\incur({\sf in(v?1:obj, ?2:rocket)}) \myand \incur({\sf at(?2:rocket ?3:loc)}) \myand \ingoal({\sf at(v?1:obj, ?3:loc)})}
\hide{	\STATE operator $\leftarrow$ {\sf unload(?1 ?2 ?3)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE {\sf unload(?1 ?2 ?3)} \ENDWHILE
\hide{\STATE \myreturn plan}
\end{dsplanneric}
\end{dsplanner}


\begin{figure}[htb!]
\begin{center}
\includegraphics[width=1.0\columnwidth]{fullpagerockettall-crop}
\caption{Timing results of several general-purpose planners and of the learned dsPlanner shown in DsPlanner~\ref{dsp:rocket} on large-scale rocket-domain delivery problems. All timing results were obtained on an 800-MHz pentium II with 512 MB of RAM.}
\end{center}
\label{fig:rocketresults}
\end{figure}

\subsection{Multi-Step Loop Domain Results}

The dsPlanner learned from the multi-Step loop domain example shown in
Figures~\ref{fig:artificialpo2} and~\ref{fig:artificialloopsfound} is
shown in DsPlanner~\ref{dsp:artificial}. As with the rocket domain,
the problems on which we tested the planners vary in the number of
objects but consist of the same initial and goal states: for all
objects {\sf obj} in the problem, the initial state contains {\sf
s(obj)} and the goal state contains {\sf
g(obj)}. Figure~\ref{fig:artificialresults} shows the results of
executing several different general-purpose planners and the learned
dsPlanner on large-scale problems of this form. The \emph{learned}
dsPlanner scales much better to large problems than these
general-purpose planners, and is able to solve problems with as many
as 40,000 objects in under a minute.

\begin{dsplanner}[htb!]
\caption{DsPlanner based on the multi-step loop domain problem shown in Figures~\ref{fig:artificialpo2} and~\ref{fig:artificialloopsfound}.}
\label{dsp:artificial}
\begin{dsplanneric}
%\REQUIRE
%\ENSURE
\WHILE{\incur({\sf s(?v1:type1)} \myand \ingoal({\sf g(?v1:type1)}))}
	\STATE {\sf op1(?1)}
	\STATE {\sf op2(?1)}
	\STATE {\sf op3(?1)} \ENDWHILE
\end{dsplanneric}
\end{dsplanner}

\begin{figure}[htb!]
\begin{center}
\includegraphics[width=1.0\columnwidth]{fullpagemsltall-crop}
\caption{Timing results of several general-purpose planners and of the learned dsPlanner shown in dsPlanner~\ref{dsp:artificial} on large-scale multi-step loop domain problems.}
\end{center}
\label{fig:artificialresults}
\end{figure}


\section{Conclusion}

In this paper, we contribute the \loopdistill algorithm for
automatically identifying repeated structures in observed plans,
determining the body and conditions of the loop they represent, and
converting looping plans into looping domain-specific planning
programs (dsPlanners). The \loopdistill algorithm identifies parallel
loops by finding sets of parallel matching subplans and then
converting each set into a loop.  Our results show that the looping
dsPlanners learned by the \loopdistill algorithm are able to take
advantage of the repeated structures in planning problems and solve
those problems more quickly than can current state-of-the-art
general-purpose planners. In these situations, planning using
dsPlanners scales more effectively than general-purpose planning and
extends the solvability horizon by solving problems orders of
magnitude larger than general-purpose planners can handle.

\bibliography{shorty}
\bibliographystyle{aaai}

\end{document}

