\section{Introduction}

\subsection{Motivation}

Intelligent agents must be able to autonomously develop and execute a
strategy for achieving their goals in a complex environment, and must
adapt that strategy quickly to deal with unexpected changes. Solving
complex problems with classical domain-independent planning techniques
has required prohibitively high search efforts or tedious hand-coded
domain knowledge, while universal planning and action-selection
techniques have proven difficult to extend to complex environments.

Researchers have focused on making general-purpose planning more
efficient by using either learned or hand-coded control knowledge to
reduce search and thereby speed up the planning process. Machine
learning approaches have relied on automatically extracting control
information from domain and example plan analysis, with relative
success in simple domains.  Hand-coded control knowledge (or
hand-written domain-specific planners) has proved more useful for more
complex domains. However, it frequently requires weeks of work and
great specific knowledge of the details of the underlying
domain-independent planner for humans to formalize useful rules.

In my previous work, I have shown that example plans can reveal more
than control information: they can also reveal the process behind
their generation. I have introduced {\sc Sprawl}, an algorithm for
finding the rationale underlying observed example plans. I have also
introduced {\sc Distill}, an algorithm for extracting simple
non-repeating programs, or templates, from example plans supplemented
with their rationales. For my thesis, I will extend these techniques
to extract rich algorithmic models of behavior from observed
executions by developing methods of identifying and extracting complex
repeated structures in example plan bases.

The applications of this work are much broader than rapid action
selection. Agents operate in a world populated by many 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. My work on extracting algorithmic
models of behavior from observed excutions 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.


\subsection{Approach}

There are three main steps towards achieving this goal. The first is
to find the rationale underlying example plans by identifying and
explaining the choices made by the agent in constructing the plan.
The second step is to construct a domain-specific planner that
reflects the choices and preferences observed in the example plans and
identified in the rationale. The third step is to use this
domain-specific planner to predict behavior or to solve new problems,
and to extend or repair it in the presence of unsolved problems or new
example plans.

\subsubsection{Identifying Underlying Rationales}

In order to predict and duplicate the behavior patterns of an observed
agent, we must understand how the actions chosen by that agent help to
achieve its goals. I call this understanding the \textit{rationale}
behind the plan. Previous approaches to plan analysis focus either on
annotating plans or on finding partially ordered plans. Approaches to
annotating orderings have been unable to handle domains with
conditional effects or have relied on the underlying planner to
provide the annotation, making them unable to analyze observed plans.
Some approaches to partial ordering have explored finding a partial
ordering of a totally ordered plan, though most deal with finding a
partially ordered plan from scratch. While building on this previous
work, we focus instead on identifying and explaining the choices made
in creating an observed plan.

In Section~\ref{sub:sprawl}, I present an algorithm that reveals the
rationale underlying observed plans with conditional effects in the
form of an annotated partial ordering. The partial ordering reflects
the ordering constraints in the plan, helping to identify independent
tracks of execution. The ordering constraints are annotated with the
reasons they are necessary, allowing subplans to be matched and
extracted from complete plans in a principled way~\cite{sprawl}.


\subsubsection{Extracting Domain-Specific Planners}

A principle difficulty in learning from example plans and in agent
modelling is using the choices and preferences reflected in observed
plans to construct a theory of behavior that can then be used to
imitate or predict the actions of an observed planner. Previous
approaches fall into two categories: those that extract control
knowledge from the example plans that is then used to guide later
planning search and those that compile exhaustive databases of
observed plans and predict or generate actions by matching those
databases.

I propose to develop learning techniques that avoid the cost of
planning from scratch and of maintaining exhaustive databases by
compiling observed example plans into compact
domain-specific planners which are able to duplicate the behavior
shown in the example plans and to solve new problems based on that
behavior. In Section~\ref{sub:template}, I present an algorithm that
moves towards this goal. The algorithm extracts simple, non-looping
programs, or templates, from example plans supplemented with their
rationales. I show that these templates, while storing little
information, succeed in capturing observed behavior and in solving
many new problems. In fact, templates extracted from only a few
example plans are able to solve all problems in limited
domains~\cite{template1}.


\subsubsection{Using and Maintaining Domain-Specific Planners}

Because my work will focus on extracting domain-specific planners from
example plans, it will also have to address how to use and maintain
planners which may be incomplete and incorrect. An incomplete planner
can result when the example plans given to the learning algorithm
cause it to learn a program that cannot solve all problems in a given
domain. This will become evident when the planner is given a problem
not solvable by its current program. An incorrect planner may result
when the learning algorithm optimistically identifies loops in the
observed example plans, or identifies loop conditions incorrectly. The
planner will be revealed to be incorrect when subsequent execution on
a new problem identifies non-executable steps in the loop.

Incomplete planners can be extended to cover new problems by querying
an external generative planner for the solutions to the new problems
and then incorporating the resulting example plans into the
domain-specific planner, either by extracting a new domain specific
planner from the updated database of solutions or by online
modification. Extracting a new planner from scratch could allow the
learning algorithm to develop a better (more compact, more general)
program, but online modification would save the learning algorithm the
substantial cost of maintaining a database of observed plans and of
generating the new planner from scratch each time it is found to be
incomplete.

It is not clear how to repair incorrect planners. One possibility is
to remove loops found to be incorrect. Another possiblity is to add
new conditions to the loops to better characterize their looping and
stopping conditions. The problem may even be solvable simply by
incorporating the new, troublesome plans into the domain-specific
planner. I propose to investigate different methods for repairing
incorrect planners and for generating planners unlikely to be
incorrect.


\subsection{Expected Contributions}
\begin{enumerate}
 \item A domain-independent algorithm for extracting the rationale
  behind an observed plan.
 \item An algorithm for extracting domain-specific planners from
  example plans.
 \item An algorithm for repairing or extending domain-specific
  planners in the presence of new example plans.
\end{enumerate}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "proposal"
%%% End: 
