\section{Background}

\subsection{Plan Analysis}

Many researchers have addressed the problems of annotating orderings
and of finding partially ordered plans. We discuss a selection of the
research investigating annotation and partial ordering.

\subsubsection{Triangle Tables}

Triangle tables are one of the earliest forms of
annotation~\cite{nilsson72learnex}. In this approach, totally ordered
plans are expanded into triangle tables that display which add-effects
of each operator remain after the execution of each subsequent
operator. From this, it is easy to compute which operators supply
preconditions to other operators, and thus to identify the relevant
effects of each operator and why they are needed in the plan. Fikes,
Hart, and Nilsson used triangle tables for plan reuse and
modification. The annotations help to identify which sub-plans are
useful for solving the new problem and which operators in these
sub-plans are not relevant or applicable in the new situation.

Regnier and Fade alter the calculation of the triangle table by
finding which add-effects of each operator are \textit{needed} by
subsequent operators (instead of which add-effects remain after the
execution of subsequent operators)~\cite{regnierfade91}. They use the
dependencies computed in this modified triangle table to create a
partial ordering of the totally ordered plan.

The triangle table approach has been applied only to plans without
conditional effects. When conditional effects are introduced, it is no
longer obvious what conditions each operator ``needs'' in order for
the plan to work correctly. Although we do not use the triangle table
structure, our needs analysis approach can be seen as an extension of
the triangle table approach to handle conditional effects.

\subsubsection{Validation Structures}

Another powerful approach to annotation is the validation
structure~\cite{rao89thesis,rao92valstruct,rao94ebgpo}. This structure
is an annotated partial order created during the planning process.
Each partial order link is a 4-tuple called a validation: $<e, t', c,
t>$, where the effect $e$ of step $t'$ satisfies the condition $C$ of
the step $t$. The validation structure acts as a proof of correctness
of the plan, and allows plan modification to be cast as fixing
inconsistencies in the proof. This approach is shown to be effective
for plan reuse and modification~\cite{rao92valstruct} and for
explanation-based generalization of partially ordered and partially
instantiated plans~\cite{rao94ebgpo}. The approach has not been
applied to plans with conditional effects. Although ~\cite{rao89thesis}
presents an algorithm for using the validation structures of plans
with conditional effects to enable modification and reuse, no method
is presented for finding these structures. And since the structures
are created during the planning process, no method is presented for
finding validation structures of any observed plans, even those
without conditional effects.

\subsubsection{Derivational Analogy}

Derivational analogy~\cite{veloso94analogy} is another interesting
approach to and use of annotation. In this approach, decisions made
during the planning process are explicitly recorded along with the
justifications for making them and unexplored alternate decisions.
This approach has been shown to be effective for reusing not only
previous plans, but also previous lines of reasoning. The approach can
handle conditional effects, but, like the validation structure
approach, is applicable only to plans that have been created and
annotated by the underlying planner.

\subsubsection{Operator Graphs}

The final approach to annotation that we will discuss is the operator
graph~\cite{smith93postponing,smith96recursion}. This approach does
not analyze plans, but rather interactions between operators relevant
to a problem. The operator graph includes one node per operator, and
one node per precondition of each operator. A link is made between
each node representing a preconditions of an operator and the operator
node, and between the node of each operator which satisfies a
particular precondition and the node representing that precondition. A
threat link is also added between the node of each operator which
deletes a particular precondition and the node representing that
precondition. Smith and Peot use these operator graphs before the
planning process to discover when threat resolution may be
postponed~\cite{smith93postponing} and to analyze potential
recursion~\cite{smith96recursion}. Operator graphs do not apply to
domains with conditional effects, and are less applicable to plan
reuse and behavior modeling than other approaches, since they analyze
operator interactions, not plans.

\subsubsection{Partially Ordering Totally Ordered Plans}

There has been some previous work on finding partial orderings of
totally ordered plans. As previously mentioned, Regnier and
Fade~\cite{regnierfade91} used triangle tables to do this for plans
without conditional effects. Veloso et al also presented a
polynomial-time algorithm for finding a partial ordering of a totally
ordered plan without conditional effects~\cite{veloso90nonlin}. The
algorithm adds links between each operator precondition and the most
recent previous operator to add the condition. It then resolves
threats and eliminates transitive edges. However, B{\"a}ckstr{\"o}m
shows that this method is not guaranteed to find the most parallel
partial ordering, and that, in fact, finding the \textit{optimal}
partial ordering according to any metric is
NP-complete~\cite{backstrom93harder}.

\subsubsection{Partial Order Planning}

There has been a great deal of research into generating partially
ordered plans from scratch. UCPOP~\cite{ucpop} is one of the most
prominent partial-order planners that can handle conditional effects.
One of the strengths of UCPOP is its non-determinism; it is able to
find all partially ordered plans that solve a particular problem.
However, it is difficult to use the same technique to partially order
a given totally ordered plan. The total order contains valuable
information about dependencies and orderings, but the UCPOP method
would discard this information and analyze the orderings from scratch.
Not only is this inefficient, but it may result in a partial ordering
of the totally ordered steps that is not consistent with the total
order.

Graphplan~\cite{graphplan}, another well-known planner, is also able
to find partially ordered plans in domains with conditional
effects~\cite{graphplanCE}.  However, it produces suboptimal and
non-minimal (overconstrained) partial orderings, which does not suit
our purpose. Consider the plan in which the steps $op\_a\_1 \ldots
op\_a\_n$ may run in parallel with the steps $op\_b\_1 \ldots
op\_b\_n$. Graphplan would find the partial ordering shown in
Figure~\ref{fig:badpo} because it only finds parallelism within an
individual time step. In the first time step, $op\_a\_1$ and
$op\_b\_1$ may run in parallel, but there is no other operator that
may run in parallel with them, so Graphplan moves to the second time
step (in which $op\_a\_2$ and $op\_b\_2$ may run in parallel).
Graphplan constrains the ordering so that no operators from one time
step may run in parallel with operators from another. None of the
ordering constraints between $op\_a$ steps and $op\_b$ steps help
achieve the goal, so they are not included in the partial ordering
created by \textsc{Sprawl}, shown in Figure~\ref{fig:goodpo}.
\textsc{Sprawl} reveals the independence of the two sets of operators.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.70\columnwidth]{gpbadpo}
    \caption{
      %
      This partial ordering, found by Graphplan, contains many
      irrelevant ordering constraints.
      %
      }
    \label{fig:badpo}
  \end{center}
\end{figure}
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.70\columnwidth]{sprawlgoodpo}
    \caption{
      %
      This partial ordering, found by \textsc{Sprawl}, contains only
      necessary ordering constraints.
      %
      }
    \label{fig:goodpo}
  \end{center}
\end{figure}


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

\subsection{Domain Knowledge to Reduce Planning Search}

A large body of work has focussed on acquiring and using domain
knowledge to reduce planning search. Our work seeks to avoid this
search altogether by generating a domain-specific planning algorithm.

\subsubsection{Control Rules}

Much of the work on learning domain knowledge for planning is focused
on learning control
rules~\cite{Mint:book,katukam94learning,etzioni93staticanal}, 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. They do not reduce the complexity of
the planning task, since they cannot \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 example
plans.  However, they have been shown to reduce dramatically the
planning time required for certain problems. 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}. Also, using control rules
introduces a new problem for planners: when to create and save a new
rule. Unrestricted learning creates a \textit{utility} problem, in
which learning more information can actually be counterproductive: it
can take longer to search through a library of rules to find the ones
that would help to solve a planning problem than to find the solution
to the problem by planning from scratch~\cite{minton88thesis}.

\subsubsection{Macro Operators}

Another common type of learned control knowledge for planning is the
macro operator~\cite{nilsson72learnex,korf85macro}, which combines a
frequently-occurring sequence of operations into one combined
operator. A macro 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
hierarchically decomposable 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, Macros, like control rules, suffer from the utility problem:
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.
Although they can decrease the search depth, the added breadth can
make planning searches slower, so, as with control rules, it is
difficult to determine when to add a new macro operator.  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.


%\subsubsection{Iterative and Recursive Macro Operators}
%
%Some work has addressed learning programs for planning, but this has
%been limited to learning
%\textit{iterative}~\cite{shell89iterativemacs} and
%\textit{recursive}~\cite{schmid01thesis} macros: macro operators that
%contain repeated sequences of steps.


\subsubsection{Case-Based Reasoning}

Another approach to learning planning knowledge, case-based reasoning,
attempts to avoid generative planning entirely for many
problems~\cite{chef,rao92valstruct,book-leake}.  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.  Utility is also a problem for case-based
planners; many handle libraries of tens of thousands of
cases~\cite{veloso94book-thesis}, but, as with control rules, as the
libraries get larger, the search times for relevant cases can exceed
the time required to plan from scratch for a new case.  Other
difficulties with case-based planning include finding an appropriate
similarity metric between problems, determining how to modify an
existing plan to solve a new problem, and determining 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}.

\subsubsection{Analogical Reasoning}

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

\subsubsection{Hierarchical Planning}

Domain knowledge is also used to hierarchically divide planning
domains~\cite{sacerdoti74abstrips,knoblock90learning,knoblock94automatically}.
This allows the planner to simplify the problem by reasoning about it
at a higher level of abstraction. The planner must then use the
abstracted solution to find a solution to the full problem. The
greatest difficulty with hierarchical planning is identifying a good
abstraction hierarchy. Such a hierarchy will abstract away enough
details that problem solving is easy at the highest level, but will
not abstract away important details; the abstract solution must be
easily transformable into a solution at lower levels of abstraction.
Information about how to hierarchically divide planning problems may
be user-supplied~\cite{sacerdoti74abstrips} or may be discovered
automatically through an analysis of the planning
domain~\cite{sacerdoti74abstrips,knoblock90learning,knoblock94automatically}.

\subsubsection{Skeletal Planning}

Skeletal planning combines hierarchical planning and case-based
reasoning by storing previously generated plans and selectively
abstracting them to reduce the size of the case library. The theory
behind skeletal planning is that plans in a particular domain are
divided into a limited number of plan classes and that a single
abstract skeletal plan can represent the solutions for all plans in a
given class~\cite{friedland85skeletal}. Skeletal planning work does
not assume that these classes are given to the problem solver.
Instead, problem instances are encountered and stored in the case
library. When several similar plans are encountered, they are
generalized into a skeletal plan that is an abstracted version of all
of them. Most skeletal planning work has relied on human users to do
this generalization, but some work has been done on applying
explanation-based learning to the automatic acquisition of skeletal
plans~\cite{bergmann92skelka}.

\subsubsection{Meta-Planning}

Work in meta-planning seeks to allow planners to reason about the
planning process as well as about the problem they are solving.
Meta-planning is used both to reason explicitly about which planning
steps to take next (such as working on a particular goal, refining an
operator, or propagating a constraint)~\cite{stefik81metaplan}, to
plan how to resolve goal conflicts or other problems in
planning~\cite{wilensky81complexsit}, or to explicitly formulate
constraints about the kind of plan that should be found (one which
uses the fewest resources, achieves the most goals, maximizes the
value of the goals achieved, or avoids impossible
goals)~\cite{wilensky81complexsit}.


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

\subsection{Automatic Program Generation}

A great deal of work in many fields has addressed the problem of
automatically generating programs. This work can be divided into two
main classes: deductive program synthesis, in which programs are
generated from specifications; and inductive program synthesis, in
which, as in our work, programs are generated from example executions.
Descriptions of work applying inductive program synthesis to planning
and action selection follow a brief summary of general deductive and
inductive program synthesis.

\paragraph{Deductive Program Synthesis}

Deductive program synthesis is the automatic generation of programs
from specifications. Researchers have identified many different
approaches to attacking this problem. Manna and
Waldinger~\cite{mannawal92deduc} approach this task as theorem
proving: a user describes the input and the desired output of the
algorithm and the program synthesis system uses a constructive proof
of the algorithm's existence to identify the algorithm. Smith's KIDS
system~\cite{smith91kids} solves program synthesis in a transformative
way: after specifing types and basic functions over those types, the
user writes program specifications in a formal language. The KIDS
system then applies correctness-preserving transformations to those
specifications to create an algorithm that fulfills them. Williams
describes the TA system~\cite{williams88learning}, which learns to
generate programs that satisfy specifications by examining and
modifying other programs.

Rich and Waters explore many of the difficulties of deductive program
synthesis~\cite{richwaters92autprog}. For example, although many claim
that deductive program synthesis will become feasible for end users
who are not familiar with programming, program synthesis systems
require extensive domain knowledge in the form of types and functions
over those types. Generating this domain knowledge requires
familiarity with programming methods. Also, these systems depend on
program specifications written by their users, so the specifications
must be complete and correct in every situation for the resulting
program to be correct. But writing complete and correct specifications
is a difficult task, and Rich and Waters argue that user-written
specifications actually cannot be complete; not only would
completeness require that the user specified how the system should act
in every possible situation, but it would also require the user to
specify fuzzy requirements for efficiency and hard-to-formulate
tradeoffs between different aspects of the generated system's
performance.

\paragraph{Inductive Program Synthesis}

In part to sidestep the excessive demands of completely and correctly
describing a desired system, many researchers have investigated
inductive program synthesis, or the automatic generation of an
algorithm from examples of its desired execution (either example
traces of the execution or example input-output pairs). Programs
generated inductively cannot be guaranteed to be correct or complete,
but input-output pairs (or traces) are often easier to generate than
complete and correct specifications, and the generated programs
usually cover the ``common cases'' (the problems like those they are
induced from).

Our work on extracting algorithmic models of behavior from observed
executions falls within the category of inductive program synthesis
(IPS). However, previously developed approaches to IPS are not
immediately applicable to our problem. Some IPS algorithms induce
programs from input-output pairs~\cite{muggle91ilp,muggle94ilp}. In
planning, this corresponds to inducing an algorithm from example
initial and goal states, a formidable task. The problem is made easier
in general IPS systems because they are also given a good deal of
background information about programming techniques and methods to
apply to a problem. This corresponds to background knowledge about how
to solve different planning problems in a particular domain. We have
chosen not to provide such knowledge.

Some approaches to IPS use program traces as
input~\cite{bauer79examples,lau01thesis}, as does our work. However,
the traces are annotated to mark the beginnings and ends of loops, to
specify loop invariants and stopping conditions, to mark conditionals,
etc. This kind of labelling cannot be obtained automatically from
observed executions, so we do not allow it in our work.

Finally, whereas many approaches to IPS must attempt to induce the
purpose of the steps from many examples~\cite{lau01thesis}, in our
planning-based approach, the purpose of each step is automatically
deduced via plan analysis. This information is critical to rapidly and
correctly identifying the conditions for executing a sequence of steps
or for terminating a loop.


\subsubsection{Iterative and Recursive Macro Operators}

Inductive program synthesis has been used to generate iterative and
recursive macro operators~\cite{schmid01thesis,schmid00applying,shell89iterativemacs,shavlik90recitEBL}. These macros capture repetative behavior
and can drastically reduce planning search by encapsulating an
arbitrarily long string of operators. However, this technique does not
attempt to replace the generative planner, and so does not eliminate
planning search.


\subsubsection{Decision Lists for Planning}

Some work has focussed on analyzing example plans to reveal a strategy
for planning in a particular domain in the form of a decision
list~\cite{khardon99action}, or 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 based on coverage and accuracy on the state-action pairs
extracted from the example plans, and adding the best pair (according
to some quality criterion) 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 decision 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, it 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}. Part of the reason it may need so
many examples is that by breaking up example plans into state-action
pairs, it also disposes of much of the information contained in the
plans, such as sequencing and looping behaviors. Also, enumerating all
possible conditions and evaluating them against every observed
state-action pair may become prohibitively slow for more complex
domains than Blocksworld.


%\subsubsection{Inducing Grammars}

%\cite{demarcken96thesis}


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

\subsection{Universal Planning}

Some researchers have sought to avoid the planning search problem by
aquiring and using ``universal plans,'' or pre-computed functions that
map state and goal combinations to actions. Our work can be seen as a
new method of storing and acquiring universal plans.

The simplest form of a universal plan is a table with an entry for
every possible situation (state and goal) that specifies the action to
take in that situation, as in general solutions to Markov decision
processes, or the Q tables of standard reinforcement
learning~\cite{mitchellAI}. In complex domains, the size of these
tables is prohibitively large, as is the cost of acquiring them.  Many
methods have been developed to store this information more compactly.

Many researchers have used reinforcement learning to acquire compact Q
functions rather than the prohibitively large Q tables. One common
form of Q function is a neural network~\cite{anderson87strategy}. Q
functions may also be represented as decision trees. This format has
been found to be very expressive, frequently outperforming neural
network representations~\cite{pyeatt98decision}, however, the decision
tree format is less compressed than neural networks. Some work has
been done on generating more compressed decision tree Q functions by
avoiding the repetition of common substructures within the
tree~\cite{uther00lumberjack}. Relational reinforcement learning
provides a method for learning a Q function represented as a logical
regression tree over parameterized operators and
predicates~\cite{dzeroski98rrl,driessens01rrl}. This allows a solution
to one problem to be used to solve another similar problem.  However,
Q functions learned in this way from small problems cannot be applied
to larger or more complex problems, and it is unclear whether the size
of the learned regression tree is prohibitive for interesting problems
in complex domains.

Decision trees have also been used in a purely planning context.
Schoppers suggests decision trees splitting on state and goal
predicates~\cite{schoppers87universal}, but finds these trees by
conducting a breadth-first search for solutions---a method which is
too time-consuming for most domains.

Other researchers have used Ordered Binary Decision Diagrams (OBDDs)
to represent universal
plans~\cite{cimatti98obdd,cimatti98strong,jensen00obdd}. OBDDs provide
an effective way to compress a universal plan without losing
precision, however are currently generated via blind backwards search
from goal states, a method that is impractical in complex domains.

%One of the primary difficulties with universal planning methods has
%been the prohibitive time and processing required to acquire a
%universal plan \fixme{citation or something?}.  Another difficulty has
%been in keeping the size of the model compact while maintaining its
%expressivity.  There has been limited success in applying the most
%compact models to complex domains. \fixme{outrageous claim?
%  citations?}


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