\section{Proposed Work}

I propose to study the problem of dynamically learning a compact
algorithmic model of agent behavior from observed action sequences. In
general, there is no compact model, since an agent could act randomly.
Even worse, it is impossible to learn a compact algorithmic model of
the behavior of an agent acting optimally to solve NP-hard problems,
since there is no such model. However, realistically, agents do not
act randomly; they act to achieve their goals. They also do not act
optimally when faced with NP-hard problems because of the prohibitive
cost of generating optimal action sequences. For these reasons, I
believe that it is possible to learn a compact algorithmic model of
agent behavior in many realistic situations.

In particular, I propose to:
\begin{itemize}
\item Continue to develop algorithms to extract programs from observed
 executions;
\item Investigate how to modify or repair the programs online in the
 presence of new information;
\item Show that a program can be learned from example traces of its
 execution.
\end{itemize}



\subsection{Main Focus}

The main focus of my work will be on extracting rich domain-specific
planning programs from example plans and on using and maintaining the
programs as the planner gains more experience.

\subsubsection{Acquiring Programs from Examples}

They key contribution of this thesis will be an algorithm for
extracting domain-specific planning programs from example plans. I
have already made some progress towards this goal; as described in
Section~\ref{sub:template}, I have demonstrated how to extract
non-looping programs from example plans and to combine those programs
into compressed representations of the learner's
experience~\cite{template1}.

Three main steps in the learning algorithm remain to be completed. The
first is extracting simple loops (loops without sub-loops or
conditionals) from example plans. I have drafted an algorithm, shown
in Table~\ref{alg:idloops}, to identify both parallel and serial
simple loops in example plans. The second step is extracting complex
loops (loops with sub-loops and conditionals) from example plans. The
third step is merging templates with simple and complex loops.

\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myprocedure Identify\_Loops(Minimal annotated consistent partial
order plan $\cal P$):\\
\> change \myassign \mytrue \\
\> \mywhile(change) \mydo \\
\> \> change \myassign \myfalse \\
\> \> $\forall$ fan outs\\
\> \> \> $\forall$ fans with same sequences:\\
\> \> \> \> identify varying parameter(s),\\
\> \> \> \> introduce new variable for them\\
\> \> \> \> \myif fans then have same init conds \& results \mythen \\
\> \> \> \> \> newloop \myassign empty while loop\\
\> \> \> \> \> newloop.conditions \myassign fans.init conds \& results\\
\> \> \> \> \> newloop.body \myassign fan.sequence\\
\> \> \> \> \> replace fans with newloop\\
\> \> \> \> \> reconnect condition and result arcs\\
\> \> \> \> \> change \myassign \mytrue\\
\> \> $\forall$ sequences\\
\> \> \> use string-matching algs to find repeated seqs\\
\> \> \> $\forall$ repeated sequences\\
\> \> \> \> \myif last repetition has different outcome \mythen\\
\> \> \> \> \> identify varying parameter(s) (if any)\\
\> \> \> \> \> introduce new variable for them\\
\> \> \> \> \> newloop \myassign empty while loop\\
\> \> \> \> \> newloop.conditions \myassign \mynot last outcome \myand
any common conditions\\
\> \> \> \> \> newloop.body \myassign sequence\\
\> \> \> \> \> replace sequence with newloop\\
\> \> \> \> \> reconnect condition and result arcs\\
\> \> \> \> \> change \myassign \mytrue\\
\> \> \> \> \myelse \myif sequences operate over all elements of a
particular type \mythen\\
\> \> \> \> \> identify which elements as varying parameter\\
\> \> \> \> \> introduce new variable for them\\
\> \> \> \> \> newloop \myassign empty while loop\\
\> \> \> \> \> newloop.conditions \myassign \mynot all elements are
taken care of \myand
any common conditions\\
\> \> \> \> \> newloop.body \myassign sequence\\
\> \> \> \> \> replace sequence with newloop\\
\> \> \> \> \> reconnect condition and result arcs\\
\> \> \> \> \> change \myassign \mytrue
\end{tabbing}
\hrule
}}
\caption{Identifying loops in an observed plan}
\label{alg:idloops}
\end{table}


\subsubsection{Use and Repair of Acquired Programs}

A necessary component of the use of acquired programs will be
repairing the programs as new problems reveal flaws in the current
program and extending them as new examples reveal more information
about problem solving in the domain.

Since the domain-specific planning programs are acquired from a set of
observed examples, their completeness cannot be guaranteed. And since
the learning algorithm must infer the existence of loops in the
observed plans, it may falsely identify some loops, fail to identify
others, and incorrectly determine the invariants and stopping
conditions of others. These errors in the program will be identified
when new problems cannot be solved or are solved incorrectly by the
program.

I plan to deal with incompleteness by querying the observed agent or
an external generative planner for a solution to the new problem and
merging that solution into the program as another example plan.  It is
not clear how to handle incorrectness in the program. I will
investigate several possibilities. One is to remove incorrect loops.
Another is to add new conditions to the loops to better characterize
their looping and stopping conditions. It may also be possible to
address the problem simply by merging a solution to the problem
causing the incorrectness into the template.

As for incorporating new examples into the program, I envision the
learning algorithm as one that can be executed either on- or offline.
When the domain-specific planner is first constructed, it makes more
sense to allow the learning algorithm to access many observed plans
simultaneously, allowing it to merge the plans into a program in the
best way.  However, I expect that the planning system will also
encounter new examples in the course of its planning experience. In
this case, I expect we will find it to be better in terms of time and
space utilization to allow the system to merge the new plans into its
current program online rather than constructing a new planner from
scratch after including the new plans in a large database.


\subsubsection{Example-Bounded Soundness, Completeness, and Optimality}

Much planning research seeks to provide guarantees about the behavior
of planning algorithms: that they are \textit{sound} (any solution
plan they find is guaranteed to be executable and to achieve the
goals), \textit{complete} (if there is a solution plan, they are
guaranteed to find it), and \textit{optimal} (the solution plan they
find is guaranteed to be as good as the best possible solution,
according to some quality criterion). Since templates are extracted
from an arbitrary set of example plans, they cannot a priori be
guaranteed to be sound, complete, or optimal.  However, we can still
make some guarantees.

To address soundness, I will supplement the automatically generated
templates with a plan verifier that will determine whether the
solution plan created by the template is executable and whether it
satisfies the goals. Thus, all solution plans returned by the template
planning system will be sound: they will be executable and will
achieve the goals.

As for completeness, an acquired template will be guaranteed to be
able to solve the problems from which it was acquired. However, it
cannot currently be guaranteed to solve any other problems. I hope to
be able to extend the template planning and learning algorithm to
guarantee that it will be able to find all solutions composed of
non-interacting subplans of observed example plans.

Finally, we can make no claims about optimality. Even if the examples
used to generate the template were optimal, the template may not be,
since a new problem may be solved suboptimally with the same technique
that solved a previous problem optimally. However, the generated
template will reflect the choices and preferences demonstrated in the
example plans from which it was acquired. Therefore, the solutions it
will generate will be similar in type to those from which it was
learned.



\subsection{Other Possible Directions}

I am very interested in many other research directions. Following are
descriptions of some of the problems I hope to have a chance to
address in my thesis.


\subsubsection{Agent Modelling}

I would like to study the applicability of the algorithms I develop
for learning programs from example executions to agent modelling
problems. I believe the algorithms will be especially useful for user
modelling problems that involve not only solving a problem, but
generating a solution that reflects the observed user preferences,
like travel planning or generating driving directions. Where needed, I
will introduce new domains to describe these problems.


\subsubsection{Using Partial Solutions}

Even when an acquired program fails to solve a given problem, its
execution may result in a partial solution. Although such a partial
solution would not solve the complete problem, it might solve part of
the problem, leaving a smaller and more manageable problem for the
teacher or generative planner. It is also possible that the new
problem would be solvable if a loop were revealed in the existing
program. It may be possible to identify this situation and to reveal
the location and conditions of the loop based on the structure of the
program and of the new problem. This would allow the system to solve
the new problem and extend the learned program without falling back on
the teacher or generative planner. I am interested in investigating in
which situations these partial solutions can be used to reduce or
eliminate the system's reliance on external sources to find the
complete solution.

There are also cases in which the acquired program fails to provide
even a partial solution but may contain information useful for solving
the given problem. For example, the program may be able to solve a
similar problem, but for objects of different types. Or, the steps
that would solve the problem have conditions not fulfilled by the
current problem. The system could check whether these solutions are
executable in the new situation. If they are, the program could be
generalized to the new situation, and the problem could be solved
without relying on external sources.


\subsubsection{Active Learning}

If the system were provided a generative planner or teacher, it
could query for solutions to unsolved problems instead of waiting for
them to be provided. I am interested in how the system could identify
gaps in its knowledge, how it could determine which queries would be
most useful, and how it could test whether its current program is
complete (whether it is able to solve all problems in the domain).


\subsubsection{``Programmable'' Domains}

I would like to investigate existing domains to determine which are
\textit{programmable}, or in which there exist compact algorithms that
can solve all problems in the domain. I am interested in what
separates programmable from non-programmable domains. I may also
present new domains to more clearly illustrate the features of a
programmable domain.



\subsection{Evaluation}

The evaluation of my work will be based on evaluating the three main
features of the system. The first is the efficacy and robustness of
the program learning algorithm. The primary test of the learning
algorithm will be to determine whether it can reconstruct hand-written
programs when presented with random traces from them. I will also
investigate how many examples are needed to reconstruct the program
and whether more are necessary with online versus offline learning. I
will test the robustness of the algorithm by investigating whether
programs are learnable from example traces not taken from a
pre-written program, but provided by humans or ordinary planners.
These examples will not exhibit the regularity of those taken from a
pre-written program and it will thus be more challenging to extract a
program from them.

I will also compare planning with learned programs to planning with
other forms of learned information and to planning from scratch.  I
will compare the speed of problem solving using the different methods,
the maximum problem sizes each of the methods can handle, and the
efficiency of the solutions generated by each of the different
methods.

Finally, I will evaluate the ability of the learned program to predict
the behavior or human or computer agents. Accurately predicting agent
behavior requires a much more accurate model of behavior than learning
to solve problems based on observed behavior. It is unclear whether a
system built to extract information about problem solving will be
accurate enough to be useful for agent modelling.

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