\documentclass{article}
\usepackage{graphicx}
\usepackage{times}
\usepackage{aaai}

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

\begin{document}
%\bibliographystyle{plain}

\date{}
\maketitle

%%%%%%%%%%%%   ABSTRACT   %%%%%%%%%%%%
\begin{abstract}
very abstract stuff goes here.
\end{abstract}

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

motivation:planning is the gold standard for action selection

key strength: guarantees

key weakness: slow

should related work be part of introduction? if so, it would go
here. would help to introduce some of the ideas---sequencing \&
structure information.

templates: programs that generate plans with no search\
\begin{itemize}
\item fully capture seqs and structures of plan
\item represent knowledge compactly (eliminate search-\&-storage prob)
\item automatically ``generalize'' knowledge via while, exists ops
\end{itemize}


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

Much of the work on learning control knowledge for planning is focused
on learning \textit{control rules}~\cite{minton88thesis}, which act as
a search heuristic during the planning process by ``recommending'' at
certain points which branch of the planning tree the planner should
explore first. Control rules do not reduce the complexity of the
planning task, since they are not able to \textit{eliminate} branches
of the search tree. They also capture only very local information
(preference choices at specific branches of the planning search tree),
ignoring common sequences of actions or repeated structures in the
example plans. However, in practice, they have been shown to reduce
dramatically the planning time required for certain problems.
\fixme{WHAT KINDS OF PROBLEMS ARE CONTROL RULES REALLY GOOD AT?? WHAT
  KINDS DO THEY STINK AT??} Learning and managing control rules are
the two biggest difficulties in using them. It is difficult for people
to write good control rules, in part because one must know the
problem-solving architecture of the planner in order to provide useful
advice about how it should make choices~\cite{minton88thesis}.  And
computer-learned control rules are often
ineffective~\cite{minton88thesis}. Finally, using control rules
introduces a new problem for planners: when to create and save a new
rule. Large databases of rules create a storage and search problem,
frequently labeled the \textit{utility} problem, in which it can take
longer to find the rules that would help solve a planning problem than
to find the solution by planning from scratch~\cite{minton88thesis}.

Another common type of learned control knowledge for planning is the
\textit{macro operator}~\cite{nilsson72learnex,korf85macro}, which
combines frequently-occurring sequences of operations into one larger
operator that can then be applied by the planner in one step, thus
eliminating the search required to find the entire sequence again.
Macros have been shown to be very effective for reducing search in
certain domains, such as towers of Hanoi and sliding n-puzzle, because
they can capture the common repeated sequences that make up almost
every solution in these domains. However, as with control rules, it is
difficult to determine when to add a new macro operator, since adding
too many can slow down the planning process. Each new macro operator
adds a new branch to the planning tree at every search node. Even
though they can decrease the search depth, the added breadth often
makes planning searches slower. Some research has studied the problem
of how to learn only the most useful macros~\cite{minton85selgen}, but
the efficacy of macros has, in general, been limited to hierarchically
decomposable domains.

Another approach to learning planning knowledge, \textit{case-based
  reasoning}, attempts to avoid generative planning entirely for many
problems~\cite{chef}.  Entire plans are stored and indexed as
\textit{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. As with control rules and macros, it is not always clear when
to save a new case into the library. Many case-based planners handle
libraries of tens of thousands of cases \fixme{(CITATION??)}, but storing so
many cases introduces the storage and search problem previously noted
with control rules. Another difficulty with case-based planning is
finding an appropriate similarity metric between problems. Sharing
more similar terms does not necessarily make the \textit{solutions} to
two problems more alike, which makes it difficult for case-based
reasoners to judge which candidate case is the best match for a new
problem. It is very difficult to modify an existing plan to solve a
new problem, and frequently even more difficult to determine whether
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, and to, in
general, find solutions faster than generative planners~\cite{chef}.

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

Some work has also been done on learning programs for planning,
however, this has been limited to learning
\textit{iterative}~\cite{shell89iterativemacs} or
\textit{recursive}~\cite{schmid01thesis} macros: macro operators that
contain repeated sequences of steps.

\begin{itemize}
\item program learning (ute's stuff--what else??)
\item learning for planning
  \begin{itemize}
  \item control knowledge
    \begin{itemize}
    \item difficult for people to write control rules
    \item must know internals of planner to write good control rules
    \item computer-learned rules often less effective
    \item storage and search problem with lists of rules
    \item doesn't usually eliminate search
    \item captures only local info (at a specific branch)---not seqs or
      structures
    \end{itemize}
  \item macro
    \begin{itemize}
    \item can capture some sequence information
    \item good at specific kinds of problems: towers of hanoi, sliding
      8-puzzle
    \item new problem: when to add new op
    \item adds a new branch at ever search node. often makes search
      longer
    \end{itemize}
  \item case-based
    \begin{itemize}
    \item captures more sequence info---ignores structure
    \item best case: no planning search
    \item storage, search, retrieval prob with cases
    \item modification problem difficult
    \item new problem: when to replan from scratch?
    \end{itemize}
  \item ---skeletal?
  \item analogical
    \begin{itemize}
    \item captures sequence info and \textit{some} structure
    \item best case still no planning search
    \item still have storage, search and retrieval prob
    \item extra info makes modifying old plans easier, but it's still
      diff
    \item deciding when to replan still a problem
    \end{itemize}
  \end{itemize}
\end{itemize}


%%%%%%%%%%%%   WHAT IS A TEMPLATE   %%%%%%%%%%%%
\section{What Is A Template}
\label{sec:whatstemplate}

a domain-dependent planning program

\begin{itemize}
\item WHILE loops
\item IF, THEN, ELSE constructs
\item EXISTS operator
\item INITSTATE-HAS, CURSTATE-HAS and GOALSTATE-HAS operators
\item logical structures (AND, OR, NOT)
\item various type tests (best mentioned later?)
\end{itemize}


%%%%%%%%%%%%   BUILDING TEMPLATES   %%%%%%%%%%%%
\section{Building Templates}
\label{sec:building}

learn templates by observing planning episodes

assume known operator set. exists work to find this (CITE)

templates model \textit{style} of observed plans
\begin{itemize}
\item mimic efficiency
\item capture characteristic behavior patterns
\end{itemize}

incrementally adapt template with each new plan
\begin{itemize}
\item can learn on-the-fly with backup planner
\item can learn with stored plan libraries
\end{itemize}

\emph{no guarantee of optimality}

assumption: rich ops (allow ces)

\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: Rich partial order $\cal R$, current template $T_i$.\\
{\bf Output}: New template $T_i+1$, updated with new plan $\cal R$\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
{\bf procedure} Update\_Template($\cal R$, $T_i$):\\
1. temp $\leftarrow$ Identify\_Cycles($\cal R$)\\
2. $T_i+1$ $\leftarrow$ Incorporate\_Matches(temp, $T_i$)\\
3. $T_i+1$ $\leftarrow$ Incorporate\_Unmatched(temp, $T_i$, $T_i+1$)\\
\\
{\bf procedure} Recurse\_Need(c, term, $\cal P$):\\
8. \>Add\_Causal\_Link(choose one way to create term, $S_c$, $\cal P$)\\
9. \>Recurse\_Need(c-1, term.create, $\cal P$)\\
10. \>Recurse\_Need(c-1, term.protect, $\cal P$)\\\
\end{tabbing}
\hrule
}}
\caption{Updating a Template with a new observed plan.}
\label{alg:update}
\end{table}

issue: find first match? find ``best'' match? find ALL matches for
every possible subset? v. confusing tradeoffs here.

issue: identify cycles? are all repeated steps cycles per se? every
step is really a cycle, with some terminating condition.

issue: speaking of non-cyclic cycles, what about finding a code
segment that's like some other thing but without the cycle (the cycle
is executed, say, only once). we need to check to see if it's really
the same--is it subsumed??

how to describe eventual alg? yoik. perhaps we could skip describing
as an alg, and just show example templates?

eventual alg, current alg? how to separate these? have un-done
procedure in eventual? note that it's not done yet? describe
large-scale idea, then describe what we've already done. shd these be
2 sep secs? what shd they be called?


%%%%%%%%%%%%   GENERALIZATION   %%%%%%%%%%%%
\section{Generalizing Examples}
\label{sec:gen}

we want some gen but not all kinds--what do we mean by similar
SITUATIONS?

can't be individual object dependent, but can be type-dependent. hope
in future that it can be type-dependent to the point that we can say
such-and-such is applicable to all fruits except apples. typeof
tests and such. perhaps even sametype, which of course would have to
specify whether it means superclass--after all, everything's an
object--or exactly the same type. what about superclass, but one step
down from object?! dizzying, isn't it? perhaps separate tests for
these various things.


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

how to turn a template into a plan, given a situation--all kinds of
gen/matching issues. do we generalize over type hierarchy?

we do not currently generalize over type hierarchy; we should.

basically, every statement is either a loop (if or while) or a plan
step. when you hit a plan step, try to apply it. if it doesn't
apply, we have failure. otherwise, add it to to current-plan list and
update the current state. when you hit a loop, check whether it is
applicable. ISSUE--it may be applicable to different sets of
objects. i.e., IF EXISTS ?a:apple THEN eat(?a:apple). are there
situations in which this could be
problematic? might we need to backtrack over these choices? i refuse
to allow for this possibility. if so, then loops are incompletely
specified/don't cover enough. we wish to work on problems that are
solvable with ``situational'' programs--and if it matters which choice
you take whether you can solve the problem, then it's got some kind of
variable dependency thing, and we don't try to handle that. so
there. pick first match; it should all work out. though of course, we
have no optimality guarantees.


%%%%%%%%%%%%   FAILURE   %%%%%%%%%%%%
\section{Detecting and Handling Failures}
\label{sec:failure}

how do we know that the template can't handle a situation we see? what
do we do about it?

we know it can't handle a situation for one of two reasons:
\begin{itemize}
\item ran thru the whole template and have no applicable plan steps (\&
  didn't start at goal)
\item have some plan steps, but they don't result in goal state
\end{itemize}

what do we do about it? best thing seems to be to get the solution
from the planner \& then add that solution to template knowledge.

ISSUE with this: what about partial solutions? shouldn't we try to use
them? how can we use them? ??
\begin{itemize}
\item if we get a partial plan starting from the initial state but
  that doesn't solve the goal, it may be legit to try the resulting
  final state (or some intermediate states) in the planner.
\item if there's a subclass way to do it, see if it's applicable to
  the superclass. or if there's a co-class way to do it (i.e. if you
  can do it for oranges, and you've got an apple, check to see if it's
  applicable/works for apples). this only works if we do smart type
  things. which we should.
\item if we see other ways to get to the goal (not starting at the
  current state but at some other (set of) state(s)) it MIGHT be
  worthwhile trying to get to those states from the initial state with
  the planner. HOWEVER, there would have to be some serious checking
  ahead of time to see whether they even include the same objects/are
  potentially reachable/etc.
\end{itemize}

of course, none of this is done.

%%%%%%%%%%%%   CURRENT ALG \& RESULTS   %%%%%%%%%%%%
\section{Current Algorithm and Results}
\label{sec:cur}

insert algorithm here,

show example ``found'' template \& original 6 plans here. is the rocket
domain a decent one? should we have example results in other domains
at this point? will we have room for them?


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

what kinds of probs can/could this solve?

can't solve things that just are search. find-the-hidden-bone
problems, or find-the-shortest-route, or chess, or go. if you can't
write a program to solve the problem, neither can the computer.

how do i be more ``rigorous'' about that?

is there any other class of problems (than search-constrained ones)
this approach couldn't solve?

point out that it can solve some fast but suboptimally--perhaps more
discussion about that class--that you can write a program to solve,
but that require search to solve optimally (blocks world, logistics).


%%%%%%%%%%%%   FUTURE WORK   %%%%%%%%%%%%
\section{Future Work}
\label{sec:future}

\begin{itemize}
\item finish missing sections of the algorithm
  \begin{itemize}
  \item introduce exists operator
  \item introduce while loops
  \item higher-order matching
  \item add type generalization? add type logic?
  \end{itemize}
\item speed-test against other planning algs
\item study number/kind of example plans necessary for ``total''
  learning
\item study ``learnability'' of different domains
\item test efficacy for agent modelling
\item look into non-online methods of incorporating plans into the
  template
\item study size vs mimicry tradeoff. how to regulate?
\end{itemize}


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

rehash

no nice solution comes free. each introduces its own set of new
problems. new problems introduced by templates concept:
\begin{itemize}
\item size vs mimicry
\item how to incorporate plans
\item order of plan incorporation
\item number of examples
\item ``quality''/kind of examples
\end{itemize}

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


%\bibliography{po}

\end{document}