\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 in\_goal\_state} }
\newcommand{\incur}{{\bf in\_current\_state} }
\newcommand{\ininit}{{\bf in\_initial\_state} }
\newcommand{\suchthat}{{\bf such that} }
\newcommand{\myassign}{$\leftarrow$ }
\newcommand{\distill}{{\sc Distill} }
\newcommand{\dsPlanner}{{\sc dsPlanner} }
\newcommand{\iterant}{{\sc Iterant} }
\newcommand{\repeatalg}{{\sc Iterant} }
\newcommand{\fixme}[1]{{\bf FIXME: #1}}
\newcommand{\hide}[1]{}

\graphicspath{{figs/}}

\title{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}
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 \iterant algorithm for
identifing repeated structures in observed plans and show how to
convert looping plans into domain-specific template 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}

Intelligent problem solving requires the ability to select actions
autonomously from a specific state to reach objectives. Planning
algorithms provide approaches to look ahead and select a complete
sequence of actions. Given a domain description consisting of
preconditions and effects of the actions the planner can take, an
initial state, and a goal, a planning program returns a sequence of
actions to transform the initial state into a state in which the goal
is statisfied. Classical planning research has addressed this problem
in a domain-independent manner---the same algorithm generates a
complete plan for any domain specification. However,
domain-independent 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 showed how to use example plans to learn
non-looping domain-specific planners (or dsPlanners), which can solve
problems of limited size~\cite{template2}. Here, we present the novel
\iterant algorithm to learn looping dsPlanners from individual example plans. Loops allow the learned dsPlanner to capture the repetative structure in many large-scale planning problems and to use this structure to attack arbitrarily large problems.

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. In our tests, the best general-purpose
planners were unable to solve simple problems with more than a few
hundred objects within our two-minute time limit, while learned
dsPlanners were able to solve similar problems with tens of thousands
of objects in seconds. And because dsPlanners are learned directly
from example plans, there is no need for tedious hand coding.

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.

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

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
parallel non-nested one-variable 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{nilsson72learnex,Mint:book,rao92valstruct}.
We focus here
on methods that learn and exploit repeated structure within plans.

Case-based and analogical reasoning approaches attempt to avoid generative planning entirely for many problems~\cite{chef,rao92valstruct,book-leake}. Entire plans are stored and indexed as \emph{cases} for later retrieval. When a new problem is presented, the case-based reasoner searches through its case library for similar problems. If an exact match is found, the previous plan may be returned with no changes. Otherwise, the reasoner must either try to modify a previous case to solve the new problem or to plan from scratch. Many case-based reasoners handle libraries fo tens of thousands of cases~\cite{veloso94book-thesis}, but as the libraries get larger, the search times for relevant cases can exceed the time required to plan from scratch for a new case. It is also difficult to find an appropriate similarity metric between problems and to determine when it would be faster simply to plan for the new problem from scratch. However, case-based planners have succeeded in solving larger problems than can be solved by generative planning alone, and, in general, find solutions faster than generative planners~\cite{chef}.

A variant of case-based reasoning that deserves mention is analogical
reasoning, which also stores case libraries and attempts to modify
previous cases to solve new
problems~\cite{veloso94book-thesis,veloso94analogy}. However, in addition to storing
the problem and the plan, analogical reasoners also store the
problem-solvign rationale behind each plan step. This makes it easier
to modify previous cases to solve new problems. However, deciding when
to abandon modification and plan from scratch is still a problem, as
are retrieving cases from the library and determining whether to save
new cases.

The internal analogy technique is a variant of analogical reasoning
which attempts to reuse experience within a single planning
episode~\cite{hickman91internal}. Instead of reusing problem-solving
experience from solving previous problems, the technique seeks to
reuse experience from the current planning episode to solving other
goals of the same problem, thus exploiting the repeated structure
within problem solutions.

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

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 Shavlik's algorithm BAGGER2~\cite{shavlik90recitEBL},
which uses example solutions and domains and background knowledge in
the form of recurrences to learn an algorithm for problem solving also
in the form of recurrences. BAGGER2 was able to learn such algorithms
from very few examples, but relied on background knowledge and was
unable to identify parallel repetition (like a set of parallel {\sf
load-object} steps in a transport-domain problem). Our work can be
seen as an extension of this work. In this work, we remove the
reliance on background knowledge and address richly structured
parallel repetition.

Another example of the strategy-learning approach is the decision
list~\cite{khardon99action}: a list of condition-action pairs.
Conditions consist of lists of predicates true in the current state
and in the goal state and are of limited length. The decision list is
created by transforming the example plans into a set of state-action
pairs, enumerating all possible condition-action pairs, evaluating
each according to some quality criterion, and adding the ``best'' pair
to the decision list, eliminating covered state-action examples, until
all examples are covered. Planning with the decision list consists of
repeatedly checking the condition-action rules against the current
state and goal. When a rule applies, the action is attempted, and
matching begins again from the beginning of the list.

The decision list algorithm can find a strategy even when the plans it
is given cannot be described by a simple strategy (e.g., they are
optimal solutions to NP-hard problems). However, the original decision
list work by Khardon is able to solve fewer than 50\% of 20-block
Blocksworld problems, and requires background knowledge about the
domain and several thousand state-action pairs to achieve that
coverage~\cite{khardon99action}. This work was later extended by
Mart{\'i}n and Geffner, who used a different language to describe the
rules of the decision list. This allowed them to eliminate the need
for background knowledge, to learn policies from several hundred
examples, and to achieve coverage of over 70\% of 20-block
problems. However, their approach only addresses domains with unary
actions.

The decision list approach requires so many examples in part because
by breaking up example plans into state-action pairs, it disposes of
much of the information contained in the plans, such as sequencing and
looping behaviors. We believe that by preserving this information we
will be able to achieve broad coverage from as few as one
example. Enumerating all possible conditions and evaluating them
against every observed state-action pair may become prohibitively slow
for more complex domains than Blocksworld.

%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~\cite{khardon99action}.

Finally, many researchers have explored hand writing domain-specific planners,
e.g.,~\cite{bacchus01tlplan,nau03shop2}. These planners are able to
solve larger problems than can 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}

In order for dsPlanners 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 dsPlanner, it must be possible to simulate
the execution of the plan. However, since dsPlanner learning requires
full models of the planning operators, this is not an additional
problem.

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~\cite{AIMag-AIPS98} 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.

DsPlanner~\ref{dsp:blocks} shows a dsPlanner that solves
block-stacking problems in the Blocksworld
domain~\cite{AIMag-AIPS98}. The task is accomplished with three while
loops. The first unstacks all blocks. The second stacks the bottom
block of each eventual tower. The third loop stacks the subsequent
blocks in each tower.

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

\begin{dsplanner}[htb!]
\caption{A simple but suboptimal dsPlanner that solves BlocksWorld-domain problems.}
\label{dsp:blocks}
\begin{dsplanneric}
%\COMMENT{unstack everything}
\WHILE{\incur({\sf on-block(v?1:block v?2:block)}) \myand \incur({\sf clear(v?1:block)})}
	\STATE {\sf move-block-to-table(?1:block ?2:block)}
\ENDWHILE
%\COMMENT{stack the first blocks}
\WHILE{\ingoal({\sf on-block(v?1:block v?2:block)}) \myand \mynot(\ingoal({\sf on-block(v?2:block v?3:block)})) \myand \incur({\sf clear(v?1:block)}) \myand \incur({\sf clear(v?2:block)})}
	\STATE {\sf move-table-to-block(?1:block ?2:block)}
\ENDWHILE
%\COMMENT{stack subsequent blocks}
\WHILE{\ingoal({\sf on-block(v?1:block v?2:block)}) \myand \incur({\sf on-table(v?1:block)}) \myand \incur({\sf on-block(v?2:block v?3:block)})}
	\STATE {\sf move-table-to-block(?1:block ?2:block)}
\ENDWHILE
\end{dsplanneric}
\end{dsplanner}


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

Our algorithm for generating plans from dsPlanners is shown in
Algorithm~\ref{alg:plan}. As previously mentioned, while executing the
dsPlanner, 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
dsPlanner consists of applying each of the statements to the current
state. Each statement in the dsPlanner 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{algorithm}[htb!]
\caption{DsPlanner-based plan generation}
\label{alg:plan}
\begin{ealgorithmic}
\INPUT DsPlanner $T$, current state $\cal C$ (initialized to the initial state of the problem), and goal state $\cal G$.
\OUTPUT Plan $P$ that solves the given problem.
\STATE $P$ \myassign $\emptyset$
\FORALL{statements $S_n$ in $T$}
	\STATE $P$ \myassign $P$ $+$ Apply\_Statement($S_n$, $\cal C$, $\cal G$)
\ENDFOR
\IF{$\cal G$ is satisfied by $\cal C$}
	\STATE \myreturn $P$
\ELSE
	\STATE FAIL
\ENDIF
\end{ealgorithmic}
\end{algorithm}

\begin{algorithm}[htb!]
\caption{Apply\_Statement: Applying a dsPlanner statement to the current state}
\label{alg:apply}
\begin{ealgorithmic}
\INPUT Statement $S$, current state $\cal C$, goal state $\cal G$.
\OUTPUT Plan fragment $P$ generated by applying $S$ to $\cal C$ and $\cal G$. In the process of applying it, $\cal C$ is changed.
\STATE $P$ \myassign $\emptyset$
\IF{$S$ is an if statement}
	\IF{Applies\_Now($S$, $\cal C$, $\cal G$)}
		\FORALL{statements $S_i$ in the body of $S$}
			\STATE $P$ \myassign $P$ $+$ Apply\_Statement($S_i$, $\cal C$, $\cal G$)
		\ENDFOR
	\ENDIF
\ELSIF{$S$ is a while statement}
	\WHILE{Applies\_Now($S$, $\cal C$, $\cal G$)}
		\FORALL{statements $S_i$ in the body of $S$}
			\STATE $P$ \myassign $P$ $+$ Apply\_Statement($S_i$, $\cal C$, $\cal G$)
		\ENDFOR
	\ENDWHILE
\ELSIF{$S$ is a plan step}
	\IF{\mynot Applicable($S$, $\cal C$)}
		\STATE FAIL
	\ENDIF
	\STATE $\cal C$ \myassign Apply\_Step($S$, $\cal C$)
	\STATE $P$ \myassign $S$
\ENDIF
\STATE \myreturn $P$
\end{ealgorithmic}
\end{algorithm}

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.

There are three ways a dsPlanner may fail to generate the correct
solution plan. It may have run through the whole dsPlanner 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 dsPlanner, 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 dsPlanner 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 adding that
new solution to the dsPlanner.


\section{Identifying Loops in Example Plans}

The current version of the \iterant 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
\iterant---identifying loop candidates and creating a
loop from a candidate)---and illustrate the operation of \iterant 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). They are illustrated in Figure~\ref{fig:subplans}.

\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.
\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:subplans} are matching steps (as shown in
Figure~\ref{fig:matching}, as are the two paint operators.

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

\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}.

\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.8\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*}

\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. 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 \iterant 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 \iterant Algorithm}

The \iterant 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}.

The \iterant 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{\iterant: 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 \iterant 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,
\iterant 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 Rocket-Domain Example}

We will now describe the operation of the \iterant algorithm on a
simple example plan from the rocket domain, illustrated in
Figure~\ref{fig:rocket}. First, \iterant searches for sets of parallel
matching steps. It finds the steps {\sf load(o1, r, s)}, {\sf load(o2,
r, s)}, and {\sf load(o3, r, s)}, which differ only in one variable,
which ranges over the values {\sf o1}, {\sf o2}, and {\sf
o3}.\footnote{It could also have identified the {\sf unload} loop
first.} These three one-step parallel matching subplans are then sent
to LargestCommonSubplan, which searches for a larger subplan common to
at least two of them.

\begin{figure*}[htb!]
\begin{center}
\includegraphics[width=.8\linewidth]{rocketpo}
\centerline{(a)}
\vspace{.25in}
\includegraphics[width=.8\linewidth]{rocketloopsfound}
\centerline{(b)}
\end{center}
\caption{An example plan in the rocket domain that involves moving objects o1, o2, and o3 from location s to location d using rocket r. The minimal annotated partial ordering of the plan is shown in (a).\hide{Arrows represent ordering constraints in the plan and are annotated with the reasons for the constraints. In the interest of simplicity, types are not specified.}\hide{First, all objects are loaded into the rocket at location s. Then the rocket is moved from location s to location d. Finally, all objects are unloaded from the rocket at location d.} The plan after loops are identified is shown in (b). Loops are surrounded by dotted lines. The loop variables are written as {\sf lv1} and {\sf lv2}, and range over all values that meet the conditions of the loops (in these cases, {\sf o1}, {\sf o2}, and {\sf o3}). Conditions for the loops are shown above them.}
\label{fig:rocket}
\end{figure*}

LargestCommonSubplan begins by finding the \emph{StepAhead} set for
each parallel track. There is one step in \emph{StepAhead} for each
track: the corresponding {\sf unload} operator. The step {\sf fly(r,
s, d)} is not a possible step ahead since it is not causally linked to
the {\sf load} operators. LargestCommonSubplan also finds the
\emph{StepBack} set for each track. It is empty; since these are the
first three steps in the plan and are parallel to each other, they do
not depend on any other plan steps. The {\sf unload} steps cannot be
added to the subplans, although they are matching, since they are not
threat-independent. LargestCommonSubplan thus returns the original
one-step subplan.

A new loop is then created to represent the common one-step
subplan. The loop body is created by replacing the differing values
({\sf o1}, {\sf o2}, and {\sf o3}) with the new loop variable, {\sf
lv1}: {\sf load(lv1, r, s)}. The conditions of the loop are that the
current state satisfies the conditions of the steps within it ({\sf
at(lv1, s)} and {\sf at(r, s)}) and that the goal state contains the
goals supported by the steps in the loop body ({\sf at(lv1, d)}).

This process repeats to uncover the {\sf unload} loop, and the
resulting plan is shown in Figure~\ref{fig:rocket}(b).

\hide{\begin{figure*}
\begin{center}
\includegraphics[width=.8\linewidth]{rocketloopsfound}
\end{center}
\caption{The example rocket-domain plan shown in Figure~\ref{fig:rocketpo} after the loops have been identified. Loops are surrounded by dotted lines. The loop variables are written as {\sf lv1} and {\sf lv2}, and range over all values that meet the conditions of the loops (in these cases, {\sf o1}, {\sf o2}, and {\sf o3}). Conditions for the loops are shown above them.}
\label{fig:rocketloopsfound}
\end{figure*}}

\subsection{A Multi-Step Loop Example}

The \iterant algorithm is also able to detect multi-step
loops. We now describe its operation on an example plan from an
artificial domain, illustrated in
Figure~\ref{fig:artificialpo2}. First, \iterant 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=.8\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=.8\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 discussed
in~\cite{nilsson72learnex}, 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. We describe how to identify loops and
their conditions in the section, ``Identifying Loops in Example
Plans''. Plan steps not contained within loops are part of 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 goals of
the problem and the goal-state terms that the steps support. We
describe how to execute dsPlanners in the section, ``Defining
and Using DsPlanners''.


\section{Results}

We compare general-purpose planning to planning using learned looping
dsPlanners.\footnote{We used the latest versions of several of the
best-performing general-purpose planners from the third international
planning competition in 2002: {\sc vhpop} version 3.0, {\sc mips}
version 3, {\sc ff} version 2.3, and {\sc lpg} version 1.2.1.} 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
but 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\hide{HACK!!!~\ref{fig:rocketresults}} 8 shows the results of
executing several different general-purpose planners and the
\emph{learned} dsPlanner on large-scale problems of this form. The
learned dsPlanner is orders of magnitude more efficient on large
problems than these 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(?v1:object, ?2:location)}) \myand \incur({\sf at(?3:rocket, ?2:location)}) \myand \ingoal({\sf at(?v1:object, ?4:location)})}
\hide{	\STATE operator $\leftarrow$ {\sf load(?v1:object ?3:rocket ?2:location)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE{\sf load(?v1:object ?3:rocket ?2:location)}
\ENDWHILE
\IF{\incur({\sf at(?1:rocket ?2:location)}) \myand \incur({\sf in(?3:object ?1:rocket)}) \myand \ingoal({\sf at(?3:object ?4:location)})}
\hide{	\STATE operator $\leftarrow$ {\sf fly(?1:rocket ?2:location ?4:location)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE {\sf fly(?1:rocket ?2:location ?4:location)}
\ENDIF
\WHILE{\incur({\sf in(?v1:object, ?2:rocket)}) \myand \incur({\sf at(?2:rocket ?3:location)}) \myand \ingoal({\sf at(?v1:object, ?3:location)})}
\hide{	\STATE operator $\leftarrow$ {\sf unload(?v1:object ?2:rocket ?3:location)}
	\STATE execute operator
	\STATE plan $\leftarrow$ plan $+$ operator}
	\STATE {\sf unload(?v1:object ?2:rocket ?3:location)}
\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\hide{HACK!!~\ref{fig:artificialresults}} 9 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(?v1:type1)}
	\STATE {\sf op2(?v1:type1)}
	\STATE {\sf op3(?v1:type1)}
\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 \repeatalg algorithm for
automatically recognizing template planners from example plans in a
specific domain. In particular, we focus on identifying loops in
observed plans and on converting looping plans into looping
domain-specific template planning programs (dsPlanners). The
\repeatalg algorithm identifies 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
\repeatalg algorithm are able to take advantage of the repeated structures in some 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 much larger problems than general-purpose planners can handle.

The applications of this work are much broader than rapid action
selection. Agents operate in a world populated by other agents,
both human and machine. A fundamental task of these intelligent
systems is to reason about the behavior of the agents around them so
they can interact appropriately. Our work on extracting algorithmic
models of behavior from observed executions could allow computers to be
programmed by demonstration, allowing anyone, not just trained
professionals, to program computers to perform complex tasks. It could
help create general-purpose robots that could be trained to do a new
task in minutes, simply by watching it be done. It could facilitate
the cooperation of heterogenous agents by allowing them to quickly
build models of each others' behavior, or could allow agents to
predict and avoid the troublesome behavior of adversarial or
non-cooperative agents. It could allow software to predict accurately
and pre-execute commands for users, or even to automatically complete
tasks like planning travel and scheduling meetings based on
observations of the user's preferences.

\bibliography{big}
\bibliographystyle{aaai}

\end{document}
