\documentclass[twoside,11pt]{article}
\input epsf %% at top of file
\usepackage{jair}
\usepackage{theapa}

%%% stuff that shoudl appear before the begin{document} command, not 
%%% including macros (which are defined separately)
%%% packages to load
\usepackage{epsfig}
\usepackage{rotating}
\usepackage{psfrag}
\usepackage{graphics}

\newcommand{\insertfigure}[2]{\begin{center}
                              \ \psfig{figure=figures/#1.eps,height=#2}
                              \end{center}}

\newcommand{\inserttwofigures}[3]{\begin{center}
                              \ \psfig{figure=figures/#1.eps,height=#3}
                              \ \psfig{figure=figures/#2.eps,height=#3}
                              \end{center}}

% load font definition, text abbrev commands, etc.
\include{macros}


\setlength{\textfloatsep}{.25in}

\jairheading{19}{2003}{355-398}{10/02}{10/03}
\ShortHeadings{Ensuring Consistency in Hierarchical Execution}
{Wray \& Laird}
\firstpageno{355}

\begin{document}

\title{An Architectural Approach to \\ Ensuring Consistency in Hierarchical
Execution
      }

\author{\name Robert E. Wray \email wrayre@acm.org \\
       \addr Soar Technology, Inc., 3600 Green Court, Suite 600 \\
Ann Arbor, MI 48105 USA
       \AND
       \name John E. Laird \email laird@umich.edu \\
       \addr The University of Michigan, 1101 Beal Avenue \\
Ann Arbor, MI 48109 USA}

\maketitle

\begin{abstract}

Hierarchical task decomposition is a method used in many agent systems
to organize agent knowledge.  This work shows how the combination of a
hierarchy and persistent assertions of knowledge can lead to
difficulty in maintaining logical consistency in asserted
knowledge. We explore the problematic consequences of persistent
assumptions in the reasoning process and introduce novel potential
solutions.  Having implemented one of the possible solutions,
\emph{\dhj}, its effectiveness is demonstrated with an empirical
analysis.


\end{abstract}

% main text



\section{Introduction}


The process of executing a task by dividing it into a series of
hierarchically organized subtasks is called
\emph{\htd}. %\cite[Tambe??]{null00}.
\Htd\  has been used in a large number of agent systems, including the Adaptive Intelligent
Systems architecture \cite{Hayes-Roth90:Architecture}, ATLANTIS
\cite{Gat91:Integrating}, Cypress \shortcite{Wilkins94:Planning}, the
Entropy Reduction Engine \cite{Bresina93:Reactive}, the Procedural
Reasoning System
\cite{Georgeff87:Reactive}, RAPS
\cite{Firby87:Investigation}, 
Soar
\cite{Laird87:Soar,Laird90:Integrating}, 
and Theo
\shortcite{Mitchell90:Becoming,Mitchell91:Theo}, and is a
cornerstone in belief-desire-intention-based agent implementations
\cite{Rao91:Modeling,Wooldridge00:Reasoning}.
\Htd\ helps both  an agent's knowledge developer and the agent itself
manage environmental complexity.  For example, an agent may consider
high-level tasks such as ``find a power source'' or ``fly to Miami''
independent of low-level subtasks such as ``go east 10 meters'' or
``turn to heading 135.''  The low-level tasks can be chosen
dynamically based on the currently active high level tasks and the
current situation; thus the high-level task is progressively
decomposed into smaller subtasks.  This division of labor simplifies
the design of agents, thus reducing their cost.  Additional advantages of
\htd\ include knowledge sharing
(a low-level subtask can be invoked for many different high-level
procedures), modularity (the decomposition helps insulate subtasks
from interaction with other knowledge) and the naturalness of
this representation \cite{Simon69:Sciences}.

Without careful design, it can be difficult to ensure consistent
reasoning in agents employing hierarchical task decompositions.  By
``consistency,'' we mean that reasoning does not lead to a set of
assertions that contains a contradiction.  Ensuring consistency
becomes much more difficult to solve -- and thus more costly -- as the
complexity of an agent's knowledge grows.  Although this problem can
be solved through careful design of agent knowledge, such an approach
requires an understanding of all possible interactions in the
hierarchy.  Thus, the correctness of this solution depends on the
skill and vigilance of the knowledge engineer.  Our bias is to seek
solutions in which the operation of an agent's primitive memories and
processes are structured to ensure inconsistencies do not arise.
Thus, we will prefer architectural solutions to knowledge-based
ones.  Architectural solutions can guarantee consistency for all
tasks and domains, reducing brittleness due to omissions in task
knowledge.  Further, while developing an architectural solution may be
costly, it should be less costly than repeatedly developing
knowledge-based solutions for different domains.

The following sections describe the inconsistency problem and
introduce a space of solutions to the problem, including two novel
solutions.  Through both theoretical and empirical analysis, one of
the new solutions, \emph{\dhj}, is shown to provide an efficient
architectural solution to the problem of ensuring reasoning
consistency in hierarchical execution.





\section{Maintaining Reasoning Consistency in Hierarchical Agents}


This section describes the inconsistency problem in greater detail.
We review methods for ensuring consistency in non-hierarchical systems
and discuss the limitations of these approaches in hierarchical
systems.


\subsection{Consistency in Non-hierarchical Systems}
\label{tms}



Truth maintenance systems (TMSs) are often used to maintain
consistency in non-hier\-arch\-ical systems
\cite{Doyle79:Truth,McDermott91:General,Forbus93:Building}.  An
inference engine uses domain knowledge to create two different kinds
of assertions of knowledge in an agent's knowledge base:
\emph{assumptions} and \emph{entailments}.  The inference engine
\emph{enables} assumptions that it has decided to treat as being true,
without requiring that the assertion be justified.  Agents often treat
environmental percepts as assumptions or ``unquestioned beliefs''
\cite{Shoham93:Agent}.  Entailments are justified assertions.  A data
structure, the \emph{justification}, captures the reasons for
asserting the entailment.  When the reasons no longer hold (the
entailment is no longer justified), the TMS retracts it from the set
of asserted beliefs. Thus, a TMS automatically manages the assertion
and retraction of entailments as an agent's situation changes,
ensuring all  entailments are consistent with the external
environment and the enabled assumptions.

Careful construction of the domain knowledge is required to ensure
that no enabled assumptions are contradictory.  For example, if some
assumption is inconsistent with the current input, then the agent must
have domain knowledge that recognizes the situation and removes the
assumption.  Thus, when an agent utilizes a TMS, the problem of
maintaining consistency in reasoning is largely one of managing
assumptions through the agent's domain knowledge.

Assumptions often reflect hypothetical reasoning about the world
(hence ``assumptions'').  However, assumptions can be used to
represent any persistent feature.  Although researchers have explored
structuring the external environment to provide persistent memory
\cite{Agre97:Lifeworld}, internal, persistent memory is usually
necessary in agent domains.  For example, persistence is required for
hypothetical reasoning, nonmonotonic revisions of assertions (such as
when counting), and remembering.

 
\begin{figure}
\insertfigure{hier}{3.0in}
\caption{A hierarchical agent. }
\label{hier.3}
\end{figure}

\subsection{Truth Maintenance in Hierarchical Agents}
\label{tms.hier}

The TMS agent framework introduced above can be extended to
hierarchical agent architectures.  In such an agent, the inference
engine and TMS are more or less identical to those of a non-hierarchical
agent. When the agent initiates a new subtask via dynamic \htd, it
also creates a new database that will contain assumptions and
entailments specific to the subtask.  Further decomposition can result
in a stack of subtasks, each containing entailments and assumptions
specific to the subtask, as shown in Figure~\ref{hier.3}.  We consider
the creation and deletion of these distinct databases of assertions 
the \emph{sine qua non} of a hierarchical architecture.  The
architecture decomposes the task not only by identifying relevant
subtasks, but also by dynamically organizing its memory according to
the current decomposition.

A new system component, ``hierarchy maintenance,'' is responsible for
creating and destroying the subtask databases when subtasks begin and
terminate.  When a subtask is achieved (or determined to be no longer
worth pursuing), hierarchy maintenance responds by immediately
removing all the assertions associated with the subtask.  This
function is of central importance in hierarchical architectures because
it allows the agent to automatically retract all assertions associated
with a terminated subtask,  requiring no agent knowledge to
``clean up'' or remove individual assertions associated with the
terminated subtask.  The hierarchy maintenance component can
efficiently remove the assertions because they are (conceptually)
located in a distinct unit, the subtask database.

\begin{figure}[h]
\psfrag{Level 1}{Subtask$_1$}
\psfrag{Level 2}{Subtask$_2$}
\psfrag{Level 3}{Subtask$_3$}
\insertfigure{fhj.3}{3.5in} %was fixed
\caption{An example of hierarchy maintenance.  Assumptions (``a'') and  entailments (``e'') are asserted within subtasks.}
\label{fhj.3}
\end{figure}

An agent's hierarchy maintenance function can be employed to help
maintain consistency, illustrated notionally in
Figure~\ref{fhj.3}. The agent architecture identifies assertions at
each of the higher levels in the hierarchy that led to a new subtask.
These assertions together form a subtask ``support set.''  In
Figure~\ref{fhj.3}, assertions $a_{14}$, $a_{15}$, $e_{14}$, and
$e_{19}$ form the support set for $Subtask_2$ while $a_{12}$,
$a_{22}$, $e_{22}$ ``support'' $Subtask_3$.  These support sets, in
effect, form justifications for subtasks in the hierarchy.  When an
assertion in a support set is removed (e.g., $a_{22}$), the agent
responds by removing the subtask ($Subtask_3$).  While not all
hierarchical architectures use architectural processes to create and
destroy subtask databases, this example illustrates how an
architectural hierarchical maintenance function can be realized via a
process similar to that of justification in truth maintenance.


Within a specific subtask, reason maintenance can go on as before.
However, the hierarchical structure adds a complication to the
maintenance of logical consistency.  Assumptions at some level in the
hierarchy can be dependent on entailments and assumptions in higher
levels of the hierarchy.\footnote{Assumptions in a lower level subtask
are always at least \emph{indirectly} dependent on the higher level
assertions.  This observation will be exploited in
Section~\ref{chap:3:sec:dhj}.}  This dependence relationship is
suggested in Figure~\ref{hier.3} by the curved lines extending from
one subtask to the one below it.  Higher levels of the hierarchy form
a ``context'' for reasoning in the local subtask.

For execution agents embedded in dynamic domains, the hierarchical
context may change at almost any time. The changing context is not
problematic for entailments; the TMS can readily determine dependent
context changes and retract affected entailments.  However, changes in
higher levels of the hierarchy (such as those deriving from inputs)
may also invalidate the assumptions of lower levels.  Without any
additional architectural mechanisms, domain knowledge is required to
ensure consistency among assumptions and the hierarchical context as
in non-hierarchical systems.  The domain knowledge for ensuring
consistency in the assumptions is complicated by the necessity of
spanning multiple (possibly many) subtasks.  We refer to such
knowledge as ``across-level'' consistency knowledge.  As described in
further detail below, identifying and creating across-level
consistency knowledge is a tedious, costly, and often incomplete
process.  Across-level knowledge must explicitly consider the
interactions between different subtasks (in different levels of the
hierarchy), rather than focus solely on the local subtask,
compromising the benefit of the hierarchical decomposition.


Before continuing, we note that hierarchical architectures should be
contrasted with hierarchical task network (HTN) planners
\cite{Sacerdoti75:Nonlinear,Erol94:HTN} and execution-oriented
systems that use HTN representations, such as DECAF
\cite{Graham00:Towards} and RETSINA
\cite{Sycara96:Distributed}.  A planning problem for
an HTN planner is represented by an initial task network that can
consist of primitive and non-primitive tasks.  The planner uses
operators to find a plan to solve the tasks.  Methods allow the
planner to match non-primitive tasks with other task networks that
describe how to accomplish the task; thus, methods enable hierarchical
decomposition of the planning problem into a family of connected task
networks.  

The main difference between HTN systems and hierarchical architectures
is that the planner represents its plan in a single global state.
That is, while methods represent decomposition steps, the hierarchical
structure of an evolving plan is represented in a blackboard-like
database that does not also reflect the structure of the
decomposition.  The following sections discuss problems and especially
solutions that depend on the hierarchical \emph{organization} of
asserted knowledge during execution, in addition to a hierarchical
task decomposition encoded as an agent's task knowledge.  Thus, the
following will not be generally applicable to HTN-based execution
systems.  However, HTN systems need to address the inconsistency
problem; Section~\ref{approach:limit} examines the consequences of
global state with respect to inconsistency arising from persistence in
a hierarchy.


\begin{figure}
\insertfigure{blocksforjair}{2.5in}
\caption{Failing to respond to relevant changes in hierarchical context in the \BW.}
\label{fig:chap2.brittle}
\end{figure}


\subsection{Failing to Respond to Relevant Changes in Hierarchical Context}

As mentioned in the introduction, when an agent fails to respond to a
relevant change in its hierarchical context and leaves a
now-inconsistent assumption enabled, the resulting behavior can become
irrational; that is, not consistent with its knowledge.  This section
explores how such irrational behavior can arise with several
illustrative examples.



\subsubsection{The Blocks World}

We use a variant of the blocks world to illustrate the inconsistency
problem in a domain familiar to most readers.  This domain is an
execution domain rather than a planning domain, which we call the
``\BW'' to reflect this difference from the static blocks world used
in planning.  We assume the agent has knowledge to build an ordered
tower (\ass{1}-\reli{on}-\ass{2}-\reli{on}-\ass{3}) without resorting
to planning and uses \htd\ to determine what actions to take as it
builds the tower.  

In Figure~\ref{fig:chap2.brittle}, the agent is placing \obj{block-2}
on the table, in order to reach \obj{block-3} and begin the goal
tower.  The \op{put-down} subtask finds an {empty} location on the
table.  The agent places the \reli{empty} assertion in the memory
associated with the \op{put-down} subtask.  In the figure, the space
immediately to the left of the gripper was chosen.  Whether or not a
space is empty may not be directly observable but may need to be
inferred from a number of other facts in the domain and stored as an
assumption in memory.  Assume the \reli{empty} assertion is an
assumption.  Now, assume \obj{block-3} is suddenly placed underneath
\obj{block-2}.  The result is an inconsistency between the assumption
(the location is a good place to put \obj{block-2}) and the
hierarchical context (the location is no longer a good place to put
the block on the table).

If the agent fails to recognize that \obj{block-3} has moved, it will
attempt to put \obj{block-2} into the same location occupied by
\obj{block-3}.  This behavior is irrational, or not consistent with
the agent's goals and knowledge (assuming the agent has knowledge that
indicates that blocks should not be placed in positions already
occupied by other blocks).  The inconsistency arises because the agent
has failed to recognize its previously-derived assumption
(\reli{empty}) is no longer true in the current situation.

Although this example may appear contrived, this specific situation
arose in an experimental system developed to explore architecture and
learning issues.  Of course, it is possible in such a simple domain to
reformulate the task such that the problem does not occur.  This
reformulation of the task via changes to or additions of knowledge is
{\em exactly} the solution we wish to avoid.  That is, we desire that
the architecture guarantee consistency between the hierarchical
context and local assumptions such that the architecture provides 
{\em a priori} constraints (guidance) in the knowledge development
process and increased robustness in execution (via consistency).  The
conclusion returns to this example to describe how an architectural
solution to the inconsistency problem solves this particular problem
-- without requiring any reformulation of the agent's task knowledge.


\subsubsection{TacAir-Soar}
\label{problem.TAS}

\begin{figure}
\insertfigure{patrol-tasks}{.5in}
\caption{Decomposition of behavior into subtasks.}
\label{fig:tas.intercept.decomp}
\end{figure}

TacAir-Soar agents pilot virtual military aircraft in a complex,
real-time computer simulation of tactical combat
\shortcite{Tambe95:Intelligent,Jones99:Automated}.  The TacAir-Soar domain
is only indirectly accessible (each agent uses simulated aircraft
sensor models and can perceive only what a pilot in a real aircraft
would sense), nondeterministic (from the point of view of the agent,
the behavior of other agents cannot be strictly predicted or
anticipated), non-episodic (the decisions an agent makes early in the
simulation can impact later options and capabilities), dynamic (the
world changes in real time while the agent is reasoning), and
continuous (individual inputs have continuous values).  Domains with
these characteristics are the most difficult ones in which to create
and apply agents
\cite{Russell95:Artificial}.

The domain knowledge of TacAir-Soar agents is organized into over 450
subtasks; during execution, the resulting hierarchical task
decomposition sometimes reaches depths of greater than 10 subtasks.
Each agent can have one of several different mission roles, among them
flying a patrol mission, and acting as a partner or ``wing'' to some
other agent's ``lead.''



\begin{figure}[b]
\insertfigure{count-planes}{.615in}
\caption{Trace of behavior leading to intercept tactic in TacAir-Soar.}
\label{tas.attack.3}
\end{figure}


Consider a pair of planes on patrol, which have been given specific
instructions for engaging enemy aircraft.  When enemy aircraft enter
the patrol area, the lead agent decides to \op{intercept} the
aircraft.  The lead then decomposes the intercept into a series of
situation-dependent subtasks, which themselves may be further
decomposed.  For example, Figure~\ref{fig:tas.intercept.decomp} shows
that the complex task of intercepting an enemy aircraft has been
decomposed into a decision to turn the agent's aircraft to a specific
heading.  The agent turns to this heading in order to get close enough
to the enemy agent (via \op{achieve-proximity}) to launch an attack.

Assume three different kinds of attack can be chosen for an
\op{intercept}. The first tactic (\op{scare}) is to engage and attempt
to scare away enemy planes without using deadly force.  This tactic is
selected when the rules of engagement specify that deadly force should
not be used, regardless of the number of aircraft in the area.  One of
the remaining two tactics will be chosen when deadly force is allowed.
\op{Offensive attack} is appropriate when friendly planes outnumber or
equal enemy planes.  \op{Defensive attack} is used when enemy planes
outnumber friendly planes.

Choosing between offensive and defensive attack requires counting the
current aircraft in the area.  Figure~\ref{tas.attack.3} shows the
evolution of an executing example decomposition. The agent must count
\emph{relevant} enemy and friendly planes.  Determining a plane's
``side'' and its relevance to the count often requires remembering and
is sufficiently complex that entailment of the count is not possible.
For instance, non-combatant aircraft should not be counted, requiring
some reasoning about the type of each aircraft.  If the agent
determines that enemy planes outnumber friendly ones, the agent
selects \op{defensive-attack}, leading to further decomposition.

What happens if an enemy plane flees, thus reducing the actual count
of relevant enemy planes by one?  The count maintained by the agent is
now invalid. Standard TMS mechanisms are insufficient because the
count was asserted as an assumption. If the actual number of enemy and
friendly planes is now equal, then the agent should switch its tactic
to offensive attack.  Continuing the defensive attack is not
consistent with the agent's knowledge.  Additionally, other
``friendly'' agents participating in the attack may base their
behavior on the expectation that the agent is pursuing an offensive
attack.  Thus the agent needs to recognize the inconsistency and
remove the current count.

Figure~\ref{ab.inconsistency-persistence.3} presents a conceptual
illustration of the problem.  Assumptions are represented as squares,
entailments as circles.  The horizontal line represents a hierarchical
relationship between the assertions (i.e., assumptions and
entailments) in the hierarchical context (above the line) and
assertions in a local subtask (below the line).  The arrowed lines
represent dependence in the creation of an assertion.  As in the
previous examples, some reasoning in the subtask may require
persistence, leading to the creation of an assumption such as
assumption \ass{1}.  However, the persistent assertion may still
depend on other assertions.  This work focuses on the dependent
assertions in the higher level context, such as  \ass{A},
\ass{B}, \ass{C},
\ass{D}, and \ass{E}$_1$ in the figure.


Suppose the world changes so that \ass{E}$_1$ is retracted from memory
and \ass{E}$_2$ is asserted. Assumption \ass{1} remains in memory.  If
\ass{E}$_2$ would not also lead to \ass{1} (e.g., it could lead to
some new assumption \ass{2}, as shown), then \ass{1} is no longer
justified and may not be consistent with the higher level context.
Whether or not this potential inconsistency among the assertions leads
to inconsistent behavior depends on the use of assumption \ass{1} in
later reasoning.


\begin{figure}
  \begin{center}
    \insertfigure{ab.inconsistency.Visio}{1.5in}
    \caption[Inconsistency due to persistence]{Inconsistency due to persistence. }
    \label{ab.inconsistency-persistence.3}
  \end{center}
\end{figure}



\section{Solutions}
\label{sec:3.solutions}

Our goal is to develop architectural solutions that allow an agent to
support persistent assumptions and simultaneously avoid
inconsistencies across the hierarchical context that can lead to
irrational behavior.  Before introducing two new architectural
solutions, however, we examine knowledge-based approaches and their
consequences in order to provide further rationale for the architectural
approach.

\subsection{Knowledge-based Solutions}
\label{approach:kbac}

Inconsistency can be avoided in hierarchical agents by creating domain
knowledge that recognizes potential inconsistencies and responds by
removing assumptions.  Many planning and agent systems use explicit
domain knowledge to represent knowledge about the interactions among
assertions in the world.  For example, the Entropy Reduction Engine
(ERE)
\cite{Bresina93:Reactive} is one agent system that relies on this
\emph{knowledge-based assumption consistency} (KBAC).  ERE requires
\emph{domain constraints}, or knowledge that describes the physics of
the task domain.  Domain constraints identify impossible conditions.
For instance, a domain constraint would indicate that a robot cannot
occupy two different physical locations simultaneously.

In ERE, domain constraints are specifically used ``to maintain
consistency in the current world model state during execution''
\cite[pp. 166]{Bresina93:Reactive}.  However, many other architectures
use KBAC as well (perhaps in conjunction with other methods).  
KBAC knowledge can be viewed simply as domain knowledge that must be
added to the system to achieve consistent behavior.

KBAC will always be necessary to maintain consistency among the
assumptions within a level of the hierarchy.  However, in order to
guarantee consistency for assumptions distributed throughout the
hierarchy, all possible inter\-actions leading to inconsistency must
be identified \emph{throughout the hierarchy}.  This knowledge
engineering problem can add significant cost to agent development.  A
knowledge designer must not only specify the conditions under which an
assumption is asserted but also {\em all} the conditions under which
it must be removed.  In the TacAir-Soar interception example, when the
enemy plane flees, the agent requires knowledge that disables all
assumptions that depend upon the number of enemy airplanes.
Similarly, in the \BW, the agent must have knowledge that recognizes
any situation, in any subtask, that should cause the disabling of
\reli{empty}.  In both cases, this KBAC knowledge ``crosses'' levels
of the hierarchy.  A complete KBAC solution requires that an agent's
knowledge capture \emph{all} potential dependencies between
assumptions in a local subtask and any higher levels in the hierarchy.

Although it will be possible to encode complete across-level
consistency knowledge for simple domains,  experience in
TacAir-Soar and other complex agent systems has convinced us that KBAC
requires significant investments of time and energy.  Further, because
it is often not possible to enumerate all conditions under which an
assumption must be removed, agents are also brittle, failing in
difficult-to-understand, difficult-to-duplicate ways.  

The insufficiency of knowledge-based solutions led us to consider
architectural solutions to the problem.  Architectural solutions
eliminate the need for domain knowledge encoded only to address
inconsistency between the hierarchical context and assumptions within
a subtask.  Thus, the cost of developing individual agents should be
reduced.  In addition to their generality, by definition,
architectural solutions are also complete, and thus able to guarantee
consistency between the hierarchical context and assumptions within a
subtask, at all times, for any agent task.  Such completeness should
improve the robustness of agent systems, especially in situations not
explicitly anticipated by their designers.


\subsection{\aj}
\label{chap:3:sec:aj}

\nocomment{ CONSIDER CALLING ASSUMPTION JUSTIFICATIONS ``CONTEXT JUSTIFICATIONS''}

One potential architectural solution to the inconsistency problem is
to justify each assumption in the hierarchy with respect to assertions
in higher levels of the hierarchy.  \emph{\aj} is an extension of
the truth maintenance approaches to consistency outlined previously.
Each assumption in the hierarchy is treated as if it were an
entailment with respect to dependent assertions higher in the
hierarchy.  A new data structure, the assumption justification, is
created that captures the reasons in the hierarchical context for a
particular assumption.  Locally, an assumption is treated exactly like
an assumption in a non-hierarchical system.  However, when the
assumption justification is no longer supported (indicating a change
in the dependent hierarchical context), the architecture retracts the
assumption.


Refer again to Figure~\ref{fhj.3}. When the agent asserts
$a_{34}$, the architecture builds an assumption justification for the
assumption that includes $a_{22}$ and $a_{21}$.  If the agent retracts
$a_{21}$, the assumption justification for $a_{34}$ is no longer
supported and the architecture also retracts $a_{34}$.  The
architecture ensures reasoning consistency across hierarchy levels
because an assumption persists no longer than the context
assertions that led to its creation.


\aj\ solves the inconsistency problem because all dependencies in 
the hierarchical context are captured in the justification.  Within
the subtask, domain knowledge is still required to ensure consistency
among the enabled as\-sump\-tions in the subtask.  However, no
across-level consistency knowledge is needed.  \aj\ still supports
local nonmonotonic and hypothetical reasoning.  Thus, \aj\ appears to
meet functional evaluation criteria.  However, in order to assess
its impact on performance, some implementation details must be
considered.

\begin{figure}[h]
%\rule{\textwidth}{.5mm}
\framebox[\textwidth]{
\begin{minipage}{\textwidth}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxxxxxxxxxxxxxx\=xxx\=xxx\=xxx\=xxx  \kill

\textbf{PROC} $create\_new\_assertion(\ldots)$ \\
\> An assumption justification is  computed when each new assertion A is \\
\> created. Thus, assumption justifications are computed for both \\
\> assumptions and entailments. \\
\> $\ldots$\\
\> $A_{just} \leftarrow create\_justification(\ldots)$ \\
\>\> Justifications can be created via well-known, textbook algorithms \\
\>\> \cite<e.g.,>{Forbus93:Building,Russell95:Artificial}  \\

\> $A_{aj} \leftarrow  make\_assumption\_justification\_for\_assertion(A)$ \\
\>$\ldots$\\
\textbf{END} \\


\\

\textbf{PROC} $make\_assumption\_justification\_for\_assertion(assertion\, A)$ \\
\> AJ $\leftarrow$ NIL \\
%\> LIST J $\leftarrow A_{just}$ \\
%\>\>Initialize J to a list of assertions, the justification of A, \\
        \>\textbf{FOR} Each assertion $j$  in $A_{just}$, the justification of A  \\
$\bigcirc \! \! \! \! 1$      
          \>\>     \textbf{IF} ($Level(j) \quad\mbox{closer to the root  than}\quad Level(A)$) \\
         \>\>\>   AJ $\leftarrow append(j,AJ)\quad$ (add $j$ to the assumption justification) \\         

$\bigcirc \! \! \! \! 2$
             \>\>   \textbf{ELSE }$\quad$ ($j$ and $A$ at the same level)\\
          \>\>\>   AJ $\leftarrow concatenate(j_{aj}, AJ) \quad$ (add assumption justification of $j$ to \\
\>\>\>\>\>\>\>\>assumption justification of A) \\
%\>\>\textbf{END-IF} \\
%\>\textbf{END-FOR} \\
 \\
\> return AJ, a list of assertions comprising the assumption justification of A \\
\textbf{END} \\

\\
\textbf{PROC} $Level(assertion \quad A)$ \\
\> Return the subtask level associated with assertion A


\end{tabbing}
\end{minipage}
}
%\rule{\textwidth}{.5mm}
\caption{A procedure for building assumption justifications.}
\label{tab:aj:proc}
\end{figure}

\subsubsection{Implementing Assumption Justification}

Creating assumption justifications requires computing context
dependencies for each assumption, similar to the computation of
justifications for entailments.\footnote{The \aj\ procedure, as
presented, requires that the inference engine record a justification
for every assertion during the course of processing.  In Soar, the
architecture in which \aj\ was implemented, these calculations are
available from its production rule matcher for both assumptions and
entailments.  However, justification calculations for assumptions may
not be supported in other architectures, requiring modifications to
the underlying inference engine.  \citeA{Laird95:Evolution} and the
\emph{Soar User's Manual} \cite{Laird99:Soar8UserManual} describe the
specific mechanisms of justification creation in Soar.}
Figure~\ref{tab:aj:proc} outlines a procedure for computing the
assumption justification data structure.  This procedure is invoked
when any assertion is created.  This procedure creates assumption
justifications for every assertion in a local subtask; that is, for
entailments as well as assumptions.  This approach allows the
architecture to cache context dependencies for each local assertion.
The advantage of this caching is that the architecture can simply
concatenate the assumption justifications of the local assertions
contributing directly to the creation of the assumption (in $\bigcirc
\! \! \! \! 2$).  We chose this caching option for computing
assumption justifications over an ``on-demand'' implementation that
would, when an assumption was created, recursively follow local
dependencies until all context dependencies were determined.  The
advantage of the caching implementation is that the context
dependencies for any assertion must be computed only once, even when a
local assertion contributes to the creation of multiple local
assumptions.

The procedure that creates an assumption justification loops over the
assertions in the justification of a new assertion \ass{A}.  The
assertions in the justification can be either context or local
assertions.  Context assertions, in $\bigcirc \!  \! \! \! 1$, are
added to the assumption justification directly.  However, local
assertions should not be added to the assumption justification because
the assumption justification should include only context dependencies.
For example, the architecture can retract a local assertion for
reasons other than a change in the hierarchical context (e.g., a
non-monotonic reasoning step or a change in enabled assumptions in the
subtask) and in these cases, the agent should not necessarily retract
dependent assumptions.  Because assumption justifications for all
local assertions in the justification have already been computed
(i.e., they are cached, as described above), the assumption
justification of a local assertion $j$ can simply be added to the
assumption justification of \ass{A}, as in $\bigcirc \! \! \! \! 2$.
For an on-demand implementation, the procedure here would recur
through local assertions, until all context dependencies for local
assertions contributing to \ass{A} had been identified.





The worst-case computational complexity of this algorithm is
polynomial in the number of assertions in the subtask.  The addition
of a higher-level assertion can be done in constant-time (a single
pointer reference).  However, $\bigcirc \! \! \! \! 2$ must uniquely
add context assertions from the assumption justification of the local
assertion.  There are at most $(n-1)$ local assumption justifications
whenever the $nth$ assertion is created.  Thus, the concatenation
needs to be performed no more than $(n-1)$ times for any call to the
assumption justification procedure.  This limit provides an upper
bound of $O(n)$ on the complexity of the assumption justification
procedure: the worst-case cost of building an individual assumption
justification is linear in the number of assertions, $n$, in the
level.  However, the architecture executes the assumption
justification procedure for every assertion in the level.  Thus, the
worst case cost for building all the justifications in a particular
level is $O(1 + 2 \ldots + n)$ or $O(n^2)$.


\begin{figure}
%\inserttwofigures{nonmon.3}{switch.3}{1.0in}
\psfrag{(a)}{\LARGE (a) }
\psfrag{(b)}{\LARGE (b) }
\insertfigure{ajtechnical}{1.0in}
\caption{Technical problems with \aj.  In (a), an assumption replaces another assumption nonmonotonically.  In (b), multiple assumption justifications for the same assumption must be supported.}
\label{nonmon.3}
\label{switch.3}
\end{figure}


Non-monotonic changes complicate the implementation.  The architecture
must disable a replaced assumption, rather than delete it, because the
initial assumption may need to be restored.  For example, in
Figure~\ref{nonmon.3}~(a), assume that the assertion of {\bf E} leads
to both the assertion of {\bf 2} in the local subtask and the
retraction of {\bf 1} (i.e., {\bf 2} is a revision of {\bf 1}).  If
the agent retracts {\bf E}, \aj\ will retract {\bf 2}, as desired, but
it must also re-enable {\bf 1}.  Thus, assumption {\bf 1} must remain
available in memory, although disabled.

Figure~\ref{switch.3}~(b) illustrates a second problem.  An assumption
can have multiple assumption justifications. These justifications can
change as reasoning progresses.  Assumption {\bf 1} initially depends
on assertions {\bf A}, {\bf B}, and {\bf C} in higher levels.  Now
assume that later in the processing, the agent removes {\bf A}, which
normally would result in the retraction of {\bf 1}.  However, in the
meantime, the context has changed such that {\bf 1} is now also
justified by \{{\bf C}, {\bf D}, {\bf E}\}.  Now when the agent
removes {\bf A}, the architecture should not immediately retract {\bf
1} but must determine if {\bf 1} is justified from other sources.


An  implementation of \aj\ in Soar was completed by members of
the Soar research group at the University of Michigan.  Experiments
using Air-Soar, a flight simulator domain \shortcite{Pearson93:Symbolic},
showed that the overhead of maintaining all prior assumptions in a level
produced a significant negative impact on agent performance.  In this
domain, \aj\ incurred significant computational cost, requiring at
least 100\% more time than the original Air-Soar agent.  Further, the
number of assumption justifications maintained within a level
continued to grow during execution, for the reasons explained above.
Some subtasks required minutes to execute as the aircraft performed a
maneuver, leading to large (and problematic) increases in the amount
of memory required.  Thus, \aj\ failed to meet efficiency requirements
on both theoretical and empirical grounds.  Although the limitations
of \aj\ might be improved by developing solutions to its technical
problems, we abandoned further exploration of this approach after such
strongly discouraging results.

\subsection{Dynamic Hierarchical Justification}
\label{chap:3:sec:dhj}

Figure~\ref{fhj.3} introduced the notion of a support set for
subtasks.  Both the Procedural Reasoning System (PRS)
\cite{Georgeff87:Reactive} and Soar \cite{Laird87:Soar} use
architectural mechanisms to retract complete levels of a subtask
hierarchy when the support set no longer holds.  In this section, we
consider a solution that leverages the hierarchy maintenance function
to ensure consistency between assumptions and the higher level
context.

A significant disadvantage of the support set in existing systems is
that it is \emph{fixed}.  In Soar, the support set is computed for the
initiation of the subtask but is not updated to reflect reasoning that
occurs within the subtask.  For example, in Figure~\ref{fhj.3},
suppose that assumption $a_{34}$ depends on assumptions $a_{22}$ and
$a_{21}$ (represented by the dashed, arrowed lines). The support set
does not include $a_{21}$; this assertion may not have even been
present when $Subtask_3$ was created.  When a local assumption depends
on an assertion not in the support set, then a change in that
assertion will not directly lead to the retraction of the assumption
(or the subtask).  Thus, approaches using such {\em \fhj} (FHJ) still
require knowledge-based solutions for consistency.  FHJ is discussed
further in Section~\ref{approach:fhj}.



We propose a novel solution, \emph{\dhj} (DHJ), that is similar to
\fhj, but dynamically updates the support set as reasoning
progresses.  Assumption justifications for individual assumptions are
unnecessary.  However, one consequence of this simplification is that
a subtask (and all assertions within it) will be retracted when the
dependent context changes.  Refer to Figure~\ref{fhj.3}.  When a DHJ
agent asserts $a_{34}$ in Figure~\ref{fhj.3}, the architecture updates
the support set for $Subtask_3$ to include $a_{21}$. Assumption
$a_{22}$ is already a member of the support set and need not be added
again. When any member of the support set for $Subtask_3$ changes, the
architecture retracts the entire subtask.  Thus \dhj\ enforces
reasoning consistency across the hierarchy because a \emph{subtask}
persists only as long as all dependent context assertions.




\begin{figure}[h]
%\rule{\textwidth}{.5mm}
\framebox[\textwidth]{
\begin{minipage}{\textwidth}
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxxxxxxxxxxxxxxxxxxx\= \kill

\textbf{PROC} $create\_new\_assertion(\ldots)$ \\
\> Whenever a new assumption is asserted, the support set is updated \\ 
\> to include any additional context dependencies.  \\
\> $\ldots$\\
\> $A_{just} \leftarrow create\_justification(\ldots)$ \\
\> \textbf{IF} A is an assumption\\
%\>\>$A_{subtask_{support\_set}}$ : = $append(A\rightarrow subtask\rightarrow support\_set,$ \\
%\>\>$S \leftarrow A_{subtask} \quad$ 
\>\>S is the subtask in which A is asserted \\
\>\>$S_{support\_set} \leftarrow append(S_{support\_set}, add\_dependencies\_to\_support\_set(A)) $ \\

\>$\ldots$\\
\textbf{END} \\

\\
\textbf{PROC} $add\_dependencies\_to\_support\_set(assertion\, A)$ \\
%\>Initialize J to the list of assertions $A_{just}$, the justification of A \\
        \>\textbf{FOR} Each assertion  $j$ in $A_{just}$, the justification of A   \\ 
$\bigcirc \! \! \! \! 1$      
          \>\>     \textbf{IF} $\left\{ Level(j) \quad\mbox{closer to the root  than}\quad Level(A) \right\}$ \\

           \>\>\>\>              $append(j,S)\quad$ (append context dependency to support set) \\
\\
$\bigcirc \! \! \! \! 2$
             \>\>   \textbf{ELSEIF} \{ \>\>\> $Level(j) \quad$ same as $Level(A)  \quad\mbox{AND}\quad $ \\
              \>\>\> \> \>    $j$ is NOT an assumption $\quad\mbox{AND}\quad $ \\
\>\>\> \> \>  $j$ has not previously been inspected \} \\
$\bigcirc \! \! \! \! 3$               \>\>\>\>          $S \leftarrow append(S,add\_dependencies\_to\_support\_set(j))$ \\
\>\>\>\>\>(compute support set dependencies for $j$ and add to S) \\
$\bigcirc \! \! \! \! 4$               \>\>\>\>          $j_{inspected} \leftarrow true \quad $ \\
\>\>\>\>\>($j$'s context dependencies have now been added to the support set) \\

%\>\>\textbf{END-IF} \\
%\>\textbf{END-FOR} \\

\\
\> return S, the list of new dependencies in the support set \\ 
\textbf{END} \\


%         \>\>\textbf{END(IF)} \\
%\>\textbf{END(FOR)} \\
%\textbf{END(PROC)} \\

\\
\textbf{PROC} $Level(assertion \quad A)$ \\
\> Return the subtask level associated with assertion A

\end{tabbing}
\end{minipage}
}
%\rule{\textwidth}{.5mm}
\caption{A procedure for \dhj.}
\label{tab:dhj:proc}
\end{figure}


\subsubsection{Implementing \dhj}

Figure~\ref{tab:dhj:proc} outlines the procedure for computing the
support set in DHJ.  As in \aj, the architecture can directly add
context assertions to the support set $\bigcirc \! \!  \! \! 1$.  When
the architecture computes the dependencies for a local assertion
$\bigcirc \! \!  \! \! 3$, the assertion is marked as having been
inspected $\bigcirc \! \!  \! \! 4$.  Inspected assertions can simply
be ignored in the future $\bigcirc \! \!  \! \!  2$, because the
architecture has already added the assertion's dependencies to the
support set.  The architecture will also ignore dependent, local
assumptions $\bigcirc \! \!  \! \! 2$ because the dependencies of
those assumptions will have already been added to the support set.
Because DHJ needs to inspect any local assertion only once, context
dependencies are computed on-demand, rather than cached as in \aj.
Condition $\bigcirc \! \!  \! \! 2$ will be true whenever there is a
local entailment whose context dependencies have not yet been
computed.  These dependencies are determined by calling
$add\_dependencies\_to\_support\_set$ recursively.  Recursive
instantiations of $add\_dependencies\_to\_support\_set$ each receive a
local assertion in the justification of an uninspected entailment,
$j$, and return a list comprising the context dependencies of $j$.
The return value is then appended to the support set \ass{S} in the
prior instantiation of $add\_dependencies\_to\_support\_set$.

The recursive call to $add\_dependencies\_to\_support\_set$ at
$\bigcirc \! \!  \! \! 3$ is the only non-constant time operation in
the procedure.  It must be made only once for any assertion $j_i$ and
thus the worst case complexity to compute the dependencies is linear
in the number of assertions in the level, as in \aj.  However, DHJ
requires only a single inspection of any individual assertion, rather
than repeated inspections for each new assumption as in \aj.  Thus the
architecture needs to call $add\_dependencies\_to\_support\_\-set$ at
most $n$ times for any subtask consisting of $n$ assertions, and the
worst case cost of updating the support set in a level remains $O(n)$.
This reduction in complexity potentially makes \dhj\ a more efficient
solution than \aj, especially as the number of local assertions
increases.

Additionally, the two technical problems outlined for \aj\ do not
impact DHJ.  DHJ never needs to restore a previous assumption. When a
dependency changes, the architecture retracts the entire level.  Thus,
DHJ can immediately delete replaced assumptions from memory.  DHJ
collects all dependencies for assumptions, so there is no need to
switch from one justification to another.  In
Figure~\ref{switch.3}~(b), dependencies {\bf A}, {\bf B}, {\bf C},
{\bf D}, and {\bf E} are all added to the support set.  These
simplifications can make the support set overly specific but reduce
the memory and computation overhead required by \dhj.








\dhjabbr\ retractions will sometimes be followed by the
\emph{regeneration} of the subtask and the re-assertion of reasoning
that was retracted.  For example, if the enemy plane fled as described
in the TacAir-Soar scenario, DHJ would retract the entire level
associated with the counting subtask.  The count would then need to be
re-started from the beginning.  Section~\ref{sec:interruption}
examines potential problems introduced by interruption and
regeneration.  The cost incurred through the regeneration of
previously-derived assertions is the primary drawback of \dhj.


\subsection{Implications of \dhj}

 \dhj\ solves the specific problem of maintaining reasoning
consistency in a hierarchy, guaranteeing consistency and utilizing an
efficient algorithm. The heuristic \dhjabbr\ employs assumes that
assumptions are so closely associated with their subtasks that
retracting subtasks is nearly equivalent to retracting individual
assumptions.  This section explores the implications of this
heuristic, focusing on task decompositions, the impact on the agent's
ability to use persistent assumptions, and the feasibility of
interrupting an agent (with a subtask retraction) in the midst of
reasoning.


\subsubsection{The Influence of the Task Decomposition}
\label{dhj:decompositions}



An agent's reasoning can be viewed as knowledge search
\cite{Newell90:UTC}.  From this perspective, the inconsistency problem
is failure to backtrack in knowledge search.  The world changes,
leading to changes in the agent hierarchy. The agent must retract some
of the knowledge it has previously asserted, so it should backtrack to
a knowledge state consistent with the world state.\footnote{Obviously,
this world state will usually be different than the agent's initial
state and it is often impossible to return to a prior state in an
execution system.  We use ``backtrack'' in this section to refer to
the retraction of asserted execution knowledge such that any remaining
asserted knowledge is consistent with the currently perceived world
state.}  Each solution can be described in terms of the way its
achieves (or avoids) backtracking in the knowledge search.  For
instance, KBAC leads to knowledge-based backtracking, in which the
KBAC knowledge tells the agent how to correct its assumptions given
the current situation.


\begin{figure}
\psfrag{A}{\Large \textbf{A}}
\psfrag{B}{\Large \textbf{B}}
\psfrag{C}{\Large \textbf{C}}
\psfrag{D}{\Large \textbf{D}}
\psfrag{E}{\Large \textbf{E}}
\psfrag{F}{\Large \textbf{F}}
\psfrag{G}{\Large \textbf{G}}
\psfrag{H}{\Large \textbf{H}}
\psfrag{1}{\Large \textbf{1}}
\psfrag{2}{\Large \textbf{2}}
\psfrag{(a)}{\Large (a) }
\psfrag{(b)}{\Large (b) }
\insertfigure{compare.new}{1.00in}
\caption{Examples of (a) disjoint dependencies  and  (b) intersecting  assumption dependencies.}
\label{compare.3}
\end{figure}

Assumption Justification is a form of dependency-directed
backtracking \cite{Stallman77:Forward}.  In dependency-directed
backtracking, regardless of the chronological order in which an
architecture makes assertions, the architecture can identify and
retract those assertions that contributed to failure in a search and
retain all other assertions.  In
\aj, the architecture retracts only those assumptions that are
directly affected by a change in the context.  Assumptions created
later in the processing, not dependent on the change, are unaffected.
Consider the examples in Figure~\ref{compare.3}.  In (a), assumptions
{\bf 1} and {\bf 2} each depend upon disjoint sets of assertions.
With \aj, removal of any assertion in {\bf 1}'s assumption
justification will result in the retraction of {\bf 1}; {\bf 2} is
unchanged, even if the architecture asserted {\bf 2} after~{\bf 1}.


\dhj\ is similar to \emph{backjumping} \cite{Gaschnig79:Performance}.
Backjumping heuristically determines the state  to which a
current search should backtrack or ``backjump.''  The heuristics used
by backjumping are based on syntactic features of the problem.  For
instance, in constraint satisfaction problems, the backjumping
algorithm identifies which variable assignments are related to other
variable assignments via the constraints specified in the problem
definition.  When a violation is discovered, the algorithm backtracks
to the most recent, related variable \cite{Dechter90:Enhancement}.
Intervening variable assignments are discarded.  In DHJ, when an
assertion in the hierarchy changes, the system ``backjumps'' in its
knowledge search to the highest subtask in the hierarchy not dependent
on the change.  In Figure~\ref{compare.3} (a) all dependent assertions
are collected in the support set for the subtask. If any of the higher
level assertions change, the entire subtask is removed.

When using \solutionabbr, as in backjumping, some previous knowledge
search may need to be repeated after backtracking.  Assume the removal
of the subtask in Figure~\ref{compare.3} (a) was due to a change in
\ass{A}.  If a similar subtask is reinitiated, assumption \ass{2} may
need to be regenerated.  This regeneration is \emph{unnecessary}
because \ass{2} did not need to be retracted to avoid inconsistency.
Under \dhj, the agent retracts \emph{all} reasoning in the dependent
subtask (and all lower levels in the hierarchy); assertions not
dependent on the change in the context can also be removed.  Thus, like
backjumping, DHJ uses a syntactic feature of reasoning (decomposition
into subtasks) to choose a backtracking point and this backtracking is
not always as conservative as possible.

Although the subtask decomposition is a syntactic feature of the
knowledge search, it is a strongly principled one, reflecting a
semantic analysis of the task by a knowledge designer.
Hierarchical task decomposition is based on the premise that tasks can
be broken down into discrete units that have little interaction with
other units; they are \emph{nearly decomposable}
\cite{Simon69:Sciences}.  Thus, the goal of a hierarchical
decomposition is to separate mostly independent subtasks from one
another.  A consequence of this separation is that dependencies in
higher levels will be limited as much as possible (interaction between
subtasks should be minimized) and the dependencies among the
assertions in any particular subtask will be shared (otherwise, the
subtask could be subdivided into two or more independent subtasks).
Of course, it is often possible to decompose a given task in many
different ways.  In most cases the domain imposes minimal constraint
and the knowledge engineer has significant latitude in crafting the
task decomposition.

In the situation illustrated in Figure~\ref{compare.3}, (b) would be a
more complete decomposition of a task by the knowledge engineer than (a),
assuming the two alternatives represent a decomposition of the same
task.  In (b), the number of dependent assertions does not necessarily
grow as a function of the number of assumptions in the local level,
while in (a) it does.  Further, in (a), two independent assumptions
are being pursued.  These assumptions could potentially be inferred in
separate subtasks in an alternate decomposition.  In (b), on the other
hand, the assumptions in the subtask are closely tied together in
terms of their dependencies and thus better asserted within the same
subtask.  Because the dependencies of assumptions {\bf 1} and {\bf 2}
have considerable overlap in (b), \aj\ pays a high overhead cost to
track individual assumptions because (most) everything in the local
subtask would be removed simultaneously if assertions {\bf B}, {\bf
C}, or {\bf D} changed.  Because \solutionabbr\ incurs no such
overhead, \solutionabbr\ is a better choice when the intersection
between assumption dependencies is high.  Task knowledge structured
more like the situation in (b), rather than (a) would lead to few
\emph{unnecessary} retractions.  Because (b) appears to better reflect
well-decomposed tasks, \dhj\ will constrain the knowledge
development process and improve the resulting decompositions.
Consequently, nearly-decomposed tasks should allow \solutionabbr\
to avoid most unnecessary regenerations while avoiding the processing
overhead of \aj.

\subsubsection{Limiting Persistence under \dhjabbr}

\dhjabbr\ limits persistence in subtasks, resulting in assumptions
that are not as persistent as assumptions in typical truth maintenance
systems. This section explores the consequences of these limitations
to determine if \dhjabbr\ architectures\footnote{For clarity, and
because \aj\ has already been eliminated as a candidate solution, the
following discussion focuses exclusively on \dhjabbr.  However, \aj\
limits persistence similarly.  } can still provide the persistence
necessary for agent execution (Section~\ref{tms}).

\dhjabbr\ will retract a subtask  when a potential inconsistency
could impact hypothetical and recursive reasoning like counting.
Consider the aircraft classification and counting example.  Perhaps an
aircraft's altitude contributes to a hypothetical classification of
the aircraft (e.g., particular altitude and speed combinations might
suggest a reconnaissance aircraft).  The agent would create
assumptions locally that depend on this aircraft's altitude.  If the
altitude (or an altitude boundary) changes, then the assumption should
be retracted.  This retraction is required to avoid inconsistency.  If
the contact's altitude no longer suggests that it is a reconnaissance
aircraft, then the assumption that depended on that assertion should
be removed. \dhjabbr\ captures these dependencies and performs the
retraction.  The agent now has the opportunity to reconsider the
classification of the aircraft, or pursue other tasks if the
classification is no longer important.

\dhjabbr\ will also retract a subtask if an assumption was created in
the local subtask for the purpose of remembering some input (or
elaboration of input).  For example, if an agent needed to remember a
particular aircraft's altitude at a particular point in time, then
that assumption cannot be stored in a local subtask.  \dhjabbr\ limits
persistence in such a way that remembering \emph{within} a local
subtask is generally impossible.

In order to remember previous situations, assumptions can be asserted
in the root task. Any assumption asserted in this level will never be
retracted because there are no higher level dependencies (assuming
percepts are associated with the top level and not a higher ``input
level,'' as in Theo, Mitchell et al., \nocite{Mitchell91:Theo} 1991).
The primary drawback of this requirement for remembering is that
remembered items are no longer local to the subtask that created them,
requiring additional domain knowledge to manage remembered
assumptions.  However, remembering already requires domain knowledge;
it is not possible to remember an assertion regardless of its
dependencies and also be able to retract it architecturally.

These examples show that \dhj\ still allows all forms of persistence,
but trades capturing dependencies for nonmonotonic assumptions in
local subtasks with remembering assumptions in the root task, where no
dependencies are captured.  Because \dhjabbr\ forces remembered items
into the root task, it also suggests that a fundamental aspect of this
root task should be managing these remembered assumptions.  We view
this requirement as a positive consequence of \dhjabbr, because it
forces knowledge engineers to better recognize the reasons for
creating an assumption (e.g., remembering vs. a hypothetical) and
circumscribes remembering so that we can now develop or adopt
functional or temporal theories to manage assumptions created for
remembering \cite<e.g.,>{Allen91:Time,Altmann02:Forgetting}.


\subsubsection{Recovery from Interruption with \dhjabbr}
\label{sec:interruption}

\dhj\ makes an agent more reactive to its environment, ensuring
that relevant changes in the environment lead to the retraction of any
dependent subtasks.  \dhjabbr\ imposes an automatic interruption of
the agent for a subtask retraction, without evaluating the state of
the system first.  Although automatic interruption increases the
reactivity of the system, it can lead to difficulties if there is no
way to override it. In this section we examine two cases where
uncontrolled interruption can cause problems.  The
problems arise because \dhjabbr\ biases the system to be reactive;
that is, to  respond automatically to changes in the environment without
deliberation. However, in both cases, additional agent knowledge can
overcome that bias and make the system more deliberate and avoid
uncontrolled interruption.

The first problem arises when there is a sequence of actions that must
be completed without interruption in order for a subgoal to be
achieved. If the processing is interrupted, then it is possible,
because of the dynamics of the world, that the task cannot be
resumed. For example, imagine an aircraft nearing the point where it
can launch a missile at a target.  When the task is interrupted and
then resumed, the aircraft's position may have changed enough,
relative to the target, that additional steering commands are
necessary before the missile can be launched.  In this case, it may be
preferable not to interrupt the original launch sequence once it has
begun.


%\footnote{Section~\ref{chap:data:sec:utas:response} provides an empirical examination of this particular situation for \soarS\ and \soarE\ agents.}

Consider two possible approaches to achieving this capability with
\dhj\ architectures. The first is to move the processing to the root
task.  Because the root task is not interrupted, the processing will
not be interrupted. However, this approach greatly restricts how a
task can be hierarchically decomposed and thus should be considered
only as a last resort. The second approach is to add new reasoning for
the task that ``freezes'' the external situation with respect to
additional reasoning in the subtask.  The new processing initiates the
execution of the subtask and creates persistent structures in the root
task.  These persistent structures represent a deliberate commitment
to not being interrupted.  The remaining processing in the subtask
accesses only these structures in the execution of the task.  Thus,
because they are persistent, even if there are changes to the
surrounding situation that would have interrupted the subtask, its
processing is now insensitive to those changes and interruption is
prevented.  This approach also requires additional reasoning to
recognize completion of the uninterruptible behavior and remove the
persistent structures built by the initial subtask. This reasoning
reflects a deliberate act, signaling that the commitment no longer
holds. In the abstract, together these additions provide a mechanism
for overcoming automatic interruption. The disadvantage of this
approach is that, as part of the system design, those subgoals that
cannot be interrupted must be identified beforehand. For those
subtasks, additional agent knowledge must be implemented to create and
remove encapsulations of any dynamic data.

A more critical problem for \dhjabbr\ is the ``Wesson Oil'' problem:
when someone is cooking dinner and a higher-priority activity suddenly
occurs (a hurt child), the cook should turn off the stove (a
``cleanup'' procedure) before leaving for the hospital
\cite{Gat91:Reliable}.  This problem occurs when there is a change in
the hierarchical context at a level far from the terminal level of the
hierarchy.  In this situation, similar tasks may not be resumed or
initiated following the interruption.  The agent must therefore
recognize whether ``cleanup'' of the external and/or internal states is
necessary, and, if so, perform that cleanup.  Even with \dhjabbr, the
agent can still behave appropriately if it has the right knowledge. In
particular, the agent must be able to recognize partially completed
tasks (like cooking dinner) and be able to select cleanup actions
specific to the task state (like turning off a stove burner). Because
\dhjabbr\ requires all remembered assumptions to be asserted in the
root level of the hierarchy, this recognition task has internal state
available; it need not try to reconstruct that state from the external
environment alone.  However, it does require some analysis of the task
domain(s) by a knowledge engineer so that any interruptible activity
requiring cleanup include triggering assertions for cleanup in the
root task.

This work was prompted by a desire for architectural solutions to
inconsistency, yet maintaining consistency efficiently can lead to
interruptions, which, under \dhjabbr, requires knowledge-based
solutions to problems arising from automatic
interruption.\footnote{\dhj\ could also be used as a trigger for
meta-level deliberation rather than immediate subtask retraction.  It
would then possibly provide an architectural solution to the question
of when to deliberate about potential inconsistency for
\emph{intention reconsideration} (see Section~\ref{dis:intent}). }
However, most of the requirements imposed by \dhjabbr\ are positive
consequences.  Subtask retractions and observed recovery in the
development process help define what must be remembered in the root
task for cleanup, which is significantly different than the laborious
process of debugging agent programs that are failing due to
inconsistency.  In theory, \dhj\ imposes requirements for handling
interruptions that do pose serious questions about its overall
utility.  In practice, we have not found addressing these questions to
be a problem in a variety of recent agent implementations using the
Soar-\dhjabbr\ architecture
\shortcite<e.g.,>{Laird01:Anticipation,Wray02:Intelligent}.

%Assanie02:Directable,Chown02:Architecture,




\section{Empirical Evaluation of \dhj}
\label{chap:data}

Architectural mechanisms like \dhjabbr\ must be efficient.  We have
demonstrated that the algorithm itself is efficient, but the question
of its impact on the overall behavior generation capability of an
agent remains an open question due to interruption and regeneration.
Given the complexity of both agent-based systems and the domains in
which they are applied, analytical evaluations must be extremely narrow
in scope, and even then require specialized techniques
\cite{Wooldridge00:Reasoning}.  This section instead pursues an
empirical evaluation of \dhj, focusing on efficiency and responsiveness
in two domains at extremes in the continua of agent domain
characteristics.  Because the architectural solution to inconsistency
was motivated by the cost (and incompleteness) of knowledge-based
solutions, knowledge development costs will also be estimated.

\subsection{Methodological Issues}

\dhj\ is a general solution, applicable in a wide range of agent
tasks.  In order to evaluate such a solution, a number of
methodological issues must be addressed.  The following describes
three important issues and the choices made for this evaluation.

\subsubsection{Relative \emph{vs.} Absolute Evaluation}

What constitutes ``good'' or ``poor'' cost and performance
evaluations?  In general, an absolute evaluation of performance and
cost is difficult because the task itself, in addition to the agent's
knowledge and architecture, determines overall cost and performance
results.

We circumvent this problem by making relative comparisons between
agents using the original, \fhj\ Soar architecture (``\soarS\
agents'') and new agents (``\soarE\ agents'').  The \soarS\ agents
provide cost and performance benchmarks, obviating the need for
absolute evaluations.

\subsubsection{Addressing Multiple Degrees of Freedom in Agent Design}

Even when architecture and task are fixed, many different
functional agents can be developed.  How can one know if comparative
results are valid and general if the experimenter has control over
both benchmarks and new agents? 

\soarE\ agents will be compared to   agents previously
implemented by others.  Such systems will provide good performance
targets, because they were optimized for performance, and will minimize
bias, because they were developed independently.

\soarS\ systems were used as fixed benchmarks, and were not  modified.  
\soarE\ agents use the identical task
decompositions employed by the \soarS\ agents and the same initial
knowledge base.  We observed opportunities to improve performance in
the \soarE\ agents by modifying either the task decomposition or
re-designing significant portions of the agent knowledge base.
However, agent knowledge was modified only when necessary for correct
behavior, in order to ensure that \soarE\ agents remained tightly
constrained by their \soarS\ counterparts, thus limiting bias in
the evaluation.
 
\subsubsection{The Choice of Representative Tasks}

This evaluation will be limited to execution agents in the \BW\ and in
a reduced-knowledge version of TacAir-Soar (``micro-TacAir-Soar'').
The choice of only a few tasks or domains is a considerable drawback
of benchmarks \cite{Hanks93:Benchmarks}.  Although these choices were
motivated primarily by the availability of domains with pre-existing
\soarS\ agents, the two domains do represent opposite extremes for many
domain characteristics.  Micro-TacAir-Soar, like TacAir-Soar, is
inaccessible, nondeterministic, dynamic, and continuous, while the \BW\
simulator used in the experiments is accessible, deterministic, static
and discrete.  The primary motivation for using the \BW, which is less
representative of typical agent tasks than Micro-TacAir-Soar, is to
assess the cost of employing \dhjabbr\ in a domain where \emph{a
priori} it appears it would not be useful (although
Section~\ref{conclusion} suggests \dhjabbr\ can prove useful even in
relatively static domains).  Thus, the \BW\ will provide a baseline
for the actual cost of deploying the algorithm, even though little benefit is
expected from its deployment in this domain.



\subsection{Evaluation Hypotheses}

Although specific expectations will differ in different domains, 
differences in the dimensions of knowledge cost and performance can be
anticipated when comparing \soarE\ agents to baseline agents.  The
following discusses the expectations and the metric(s) used for each
dimension.

\subsubsection{Knowledge Engineering Cost}

Knowledge engineering effort in \soarE\ agents should decrease in
comparison to previously developed agents.   Knowledge
in Soar is represented with production rules.  Each production
represents a single, independent knowledge unit.  We assume the
addition of more productions represents an increase in cost and
measure knowledge cost by counting the number of productions in each
type of agent.  The number of productions, of course, provides only a
coarse metric of cost because the complexity of individual productions
varies significantly. However, the productions that will be removed in
\soarE\ agents are often the most difficult ones to create.
Therefore, the difference in number of productions is probably a
conservative metric for knowledge cost in
\solutionabbr.

\subsubsection{Performance: Efficiency and Responsiveness}
\label{chap:data:sec:metric}

In general, overall performance should change little in \soarE\
agents, as compared to \soarS\ counterparts.  Although \solution\ does
add a new architectural mechanism, the algorithm itself is efficient
and should not contribute to significant differences in performance.
Further, less domain knowledge will need to be asserted because all
across-level consistency knowledge is now incorporated in the
architecture.  Thus, if applying across-level KBAC knowledge
represented a significant expense in the overall cost of executing a
task, \soarE\ agents might perform better than
\soarS\ agents.

There are two specific exceptions to this expectation.  First, in
domains where consistency knowledge is (mostly) unnecessary for task
performance, \soarS\ agents may perform better than \soarE\ agents.
For example, the \BW\ requires little consistency knowledge but the
\dhjabbr\ architecture will still update the support set, even though few
inconsistency-causing context changes should arise.  

Second, if regeneration is problematic, overall performance will
suffer.  In \soarE, whenever the dependent context changes, a subtask
will be retracted.  If the change does not lead to a different choice
of subtask, the subtask will be necessarily regenerated.  Thus, under
\soarE, some subtask regeneration will occur, and, if regeneration is
significant, performance degradation will result.

CPU execution time provides a simple, single dimension of gross
performance.  The CPU time reported for individual experiments
reflects the time the agent spends reasoning and initiating actions
rather than the time it takes to execute those actions in the
environment.

\noindent{\textbf{Decisions:}}
\label{chap:data:sec:decisions}
In Soar, subtasks correspond  to the selection of 
\emph{operators} and subgoals for implementing  operators.
The selection of an operator is called a
\emph{decision}.  When Soar selects an operator, it tries
to apply the operator.  Soar reaches an \emph{impasse}
when it cannot apply a newly selected operator.  These non-primitive
operators lead to the generation of a subgoal in the subsequent
decision.  For example, Soar selects the \op{put-down} operator in one
decision and creates a subgoal to implement \op{put-down} in the
subsequent decision.  Together, these two steps constitute the
notion of a subtask in Soar.

The number of decisions can thus be used as an indication of the
number of subtasks undertaken for a task.  In \soarS, a subtask was
generally never interrupted until it terminated (either successfully
or unsuccessfully).  In \soarE, subtasks will be interrupted whenever
a dependent change occurs. Thus, decisions should increase in \soarE\
agents because subtasks will be interrupted and re-started.  Further,
if decisions increase substantially (suggesting significant
regeneration), overall performance will degrade.

\noindent{\textbf{Production Firings:}} A production rule ``fires'' when its
conditions match and its result is applied to the current
situation. Production firings should decrease in \soarE\ for two
reasons.  First, any across-level consistency knowledge that was
previously used in \soarS\ agents will no longer be necessary (or
represented); therefore, this knowledge will not be accessed.  Second,
any reasoning that occurred after inconsistency arose in \soarS\
agents will be interrupted and eliminated. However, production firings
will increase if significant regeneration is necessary.

\subsection{Empirical Evaluation in the Blocks World}


Agents in this \BW\ domain have execution knowledge to transform any
initial configuration of three blocks into an ordered tower using 
a simulated gripper arm.  The table in this simulation has a width of 
nine blocks.  The agent's task goal is always to build the
\ass{1}-\reli{on}-\ass{2}-\reli{on}-\ass{3} tower.    Each
agent built a tower from each of the resulting 981 unique, non-goal,
initial configurations of blocks.  Table~\ref{tab:bw:summary}
summarizes the results of these tasks.  As expected, total knowledge
decreased. Overall performance improved.  Decisions increased, as
expected, but the number of rule firings increased as well, which was
not anticipated.

\begin{table}
\begin{centering}
%\small
\begin{tabular}{l  r r   r r  }
\hline
                    & \multicolumn{2}{c}{\soarS}    &    \multicolumn{2}{c}{\soarE}    \\ 
                    &  \multicolumn{1}{c}{$\bar{x}$}  & \multicolumn{1}{c}{s.d.} &  \multicolumn{1}{c}{$\bar{x}$}  & \multicolumn{1}{c}{s.d.} \\ \hline
Rules               & {188} & --- &   {175} & ---    \\ %\hline
Decision Avg.       & 87.1   & 20.9 &   141.1 &   38.7    \\ %\hline
%Avg. Outputs        & 22.3   &  6.1 &   22.3  &   6.1 \\ %\hline
%Avg. Elaboration                           
%       Cycles       & 274.3  & 65.8 &   562.9 & 155.7 \\ %\hline
Avg. Rule Firings   & 720.3  & 153.5&   855.6 & 199.6 \\ %\hline
Avg. CPU Time (ms)  & 413.1  & 121.6&   391.6 &  114.0\\ \hline
\end{tabular}
\caption[Summary of knowledge and performance data from the 
Blocks World]{Summary of knowledge and performance data from the 
Blocks World.  The agents performed the tower-building task for each
of 981  configurations.  Task order was randomly
determined.}
\label{tab:bw:summary}
\end{centering}
\end{table}


\subsubsection{Knowledge Differences}

Total knowledge decreased about 7\% in the \soarE\ agent.  This small
reduction is consistent with expectation.  The aggregate comparison is
misleading because knowledge was both added (16 productions) and
deleted~(29).

\noindent{\textbf{Removing Consistency Knowledge}:}
In Soar, the subtask operator and subgoal are terminated separately.
Soar monitors impasse-causing assertions to determine if a subgoal
(such as the subtask goal) should be removed via \fhjabbr.  However,
the removal of a subtask operator requires knowledge.  The original,
\fhjabbr\ architecture treats the initiation of an operator as a
persistent assumption and requires knowledge to recognize when a
selected operator should be interrupted or terminated.  This knowledge
can be categorized as consistency knowledge because it determines the
time at which a subtask should be terminated, even when the initiating
conditions for the subtask no longer hold.

In \solutionabbr, only the effects of operators are persistent; all
other assertions are entailments of the situation.  Thus, the
initiation of a subtask is now treated as an entailment and a subtask
remains selected only as long as the initiation conditions for the
subtask hold.  This change removes the need for knowledge to terminate
the subtask: when the subtask initiation conditions are no longer
true, the subtask is automatically retracted.  Thus, termination
knowledge was removed for all subtask operators.

\noindent{\textbf{Filling Gaps in Domain Knowledge}:} The persistence
of subtasks in the original architecture allows \soarS\ agents to
ignore large parts of the state space in their domain knowledge.  For
example, the knowledge that initiates \op{stack} and \op{put-on-table}
subtasks assumes that the gripper is currently not holding a block.
As these tasks are executed, the gripper, of course, does grasp
individual blocks. The conditions for initiating \op{stack} or
\op{put-on-table} when holding a block were ignored in the original
domain knowledge.

The \dhjabbr\ agent now requires knowledge to determine which subtasks
it should choose when holding blocks, because subtasks can be
interrupted while the agent still holds a block.  16 productions were
necessary, primarily for the \op{stack} and \op{put-on-table}
operators.  It is important to note that this knowledge is necessary
domain knowledge.  \soarS\ agents could not solve any problem in which
they began a task holding a block because they lacked domain knowledge
for these states.  These additions are thus a positive consequence of
\soarE. The architecture's enforcement of consistency revealed gaps in
domain knowledge.

\subsubsection{Performance Differences}
\label{chap:data:sec:bw:perf}

Somewhat surprisingly, overall performance of the \soarE\ agents
(measured in CPU time) improves slightly in comparison to the \soarS\
agents, even though both decisions and production firings increase.
Each of the Soar-specific performance metrics are considered
individually below, and then the overall performance improvement is
considered.

\noindent{\textbf{Decisions}:} 
\soarS\ agents, on average,  made
considerably fewer decisions than \soarE\ agents.  The difference was
consistent across every task.  These additional decisions result from
the removal and subsequent regeneration of subtasks.  For example,
when the agent picks up a block in pursuit of a
\op{stack} task, the selection of the 
\op{stack} task must be regenerated.  The knowledge in the \soarE\ agents 
could be modified to avoid testing specific configurations of
blocks and thus avoid many of these regenerations.

\noindent{\textbf{Production Firings}:} 
The number of production firings also increased in the Blocks World.
The increase in production firings can be attributed to the knowledge
added to the system and the regeneration of subtasks that made the
additions necessary.  The relative increase in number of production
firings (19\%) was much smaller than the increase in decisions (62\%).
The smaller difference can be attributed to the productions that were
removed (and thus did not fire).

\noindent{\textbf{CPU Time}:} Generally, 
when production firings increase in Soar, an increase in CPU time is
expected.  However, CPU time in \soarE\ decreased slightly in
comparison to \soarS\ even though production firings increased.  To
explain this result, some additional aspects of Soar's processing must
be considered.

The match cost of a production is not constant but grows linearly with
the number of \emph{tokens}, partial instantiations of the production
\cite{Tambe91:Eliminating}. Each token indicates what conditions in
the production have matched and the variable bindings for those
conditions.  Thus, each token represents a node in a search over the
agent's memory for matching instantiation(s) of the production.  The
more specific a production's conditions are, the more constrained the
search through memory, and thus it costs less to generate the
instantiation.

The new productions added to the \soarE\ Blocks World agent were more
specific to the agent's memory (i.e., its external and internal state)
than the productions removed.  Further, simply having fewer total
productions also can reduce the amount of total search in
memory.\footnote{The RETE algorithm \cite{Forgy79:Efficient} shares
condition elements across different productions.  Thus, the removal of
productions only decreases the total search if removed productions
contain condition elements not appearing in the remaining productions.
We did not perform an exhaustive analysis of the condition elements to
determine if the removed productions reduce the number of unique
condition elements in the RETE network.}  An informal inspection of
the match time and tokens for several \soarS\ and \soarE\ runs showed
that the number of tokens decreased in \soarE\ by 10-15\%.  This
reduction in token activity is the primary source of improvement in
\BW\ \soarE\ agent CPU time. This improvement, of course, is not a
general result and provides no guarantee that in some other task or
domain the cost of matching will not increase rather than decrease.

%\noindent{\textbf{Responsiveness}:}  Responsiveness is ignored in the \BW\ because the domain is static.  


\subsection{Empirical Evaluation in $\mu$TacAir-Soar}
\label{chap:data:sec:utas}

Converting \TAS\ to the \solutionabbr\ architecture would be very
expensive, requiring many months of effort.  \soarE\ agents were
instead developed for a research and instruction version of
TacAir-Soar, ``Micro-TacAir-Soar'' ($\mu$TAS).  $\mu$TAS agents use
the TacAir-Soar simulation environment (ModSAF) and interface but have
knowledge to fly only a few missions, resulting in an order of
magnitude decrease in the number of productions in the agents.
However, $\mu$TAS uses the same tactics and doctrine for its missions
as TacAir-Soar.

In \utas, a team of two agents (``lead'' and ``wing'') fly the patrol
mission described previously.  They engage any hostile aircraft that
are headed toward them and are within a specific range. The lead
agent's primary role is to fly the patrol route and intercept enemy
planes.  The wing's responsibility is to fly in formation with the
lead.  Because the total knowledge is significantly reduced,
converting \utas\ \soarE\ agents should be relatively inexpensive.
However, the results should be representative of \TAS\ because \utas\
retains the complexity and dynamics of \TAS.

The patrol mission has no clearly-defined task termination condition
like the \BW.  To address this problem, each agent in the simulation
executes for ten minutes of simulator time.  During this time, each
agent has the opportunity to take off, fly in formation with its
partner on patrol, intercept one enemy agent, and return to patrol
after the intercept.  In an actual \TAS\ scenario, these activities
would normally be separated by much larger time scales.  However, an
agent spends much of its time on a patrol mission simply monitoring
the situation (waiting), rather than taking new actions.  Ten minutes
of simulated time proved to be brief enough that overall behavior was
not dominated by wait-states, while also providing time for a natural
flow of events.

When running for a fixed period of time, an increase in the number of
decisions can be attributed to regeneration or simply an improvement
in decision cycle time.  We avoid this potential confusion by running
the simulator with a constant cycle time.  In this mode, each
simulator update represents 67~milliseconds of simulated time.
Because each agent now runs for a fixed period of time with fixed
updates, each \soarS\ and
\soarE\ agent will execute the same number of decisions.  Any problems
due to regeneration will be apparent in the number of rule firings and
degradation in responsiveness.  Additionally, the general results do
not change significantly if the scenarios are executed with the
real-time mode normally used for \TAS\ agents.  The fixed cycle simply
eliminates some variability.

Although the patrol scenario was designed to minimize variation from
run to run, the \utas\ simulator is inherently stochastic and the
specific actions taken by an agent and the time course of those
actions varies when the same task is repeated.  To control for this
variation, each scenario was run for the lead and wing agents
approximately 50 times. Logging and data collection significantly
impacted CPU time and other performance statistics.  In order to
control for this effect, we actually ran each scenario 99 times,
randomly choosing one agent (lead or wing) to perform logging
functions (and discarding its performance measures).  The other agent
performed no logging functions.  Data from logging agents was used to
create Figure~9.  The performance measures of the ``no logging''
agents were recorded at the conclusion of each scenario and are
summarized in Table~\ref{tab:utas:summary}.

\subsubsection{Improving Task Decompositions}
\label{chap:data:sec:know-changes}

\uTAS\ \soarE\ agents required extensive knowledge revision.
Such revision was not unexpected.  For instance, unlike the
\BW, \utas\ agents  remember many percepts, such as the last
known location of an enemy aircraft.  As previously described,
assertions for remembering must now be located in the root level of the
hierarchy, thus requiring some knowledge revision.  However, other
problems were discovered.  In some cases, \soarS\ agents \emph{took
advantage} of inconsistency in asserted knowledge.  In other words,
the \soarS\ agent not only allowed inconsistency in the assertions but
actually depended on those inconsistencies to apply new knowledge.
There were two major categories of this knowledge.  ``Within-level''
consistency knowledge recognized specific inconsistencies (e.g.,
retraction of the proposal for the subtask) as a trigger for actions
such as ``clean up'' of the subtask state.  ``Complex subtasks''
allowed the non-interruptible execution of a complex procedure
regardless of the continuing acceptability of the subtask.  In both
cases, agent knowledge was modified to remove any dependence on
inconsistency. Appendix~A provides further explanation of the
original knowledge and subsequent changes.
Section~\ref{chap:data:sec:utas:know} summarizes the changes
quantitatively.



\begin{table}
\begin{centering}
%\small
\begin{tabular}{l  r  r @{~~~~~~}  r  r @{~~~~~~~~~~~} r  r @{~~~~~~} r  r }
\hline
             & \multicolumn{4}{c}{Lead Agent} & \multicolumn{4}{c}{Wing Agent} \\ \cline{2-5} \cline{6-9}
                  & \multicolumn{2}{c}{\soarS}      & \multicolumn{2}{c}{\soarE}     & \multicolumn{2}{c}{\soarS}      & \multicolumn{2}{c}{\soarE} \\ \hline


Rules             &   \multicolumn{2}{c}{591}    & \multicolumn{2}{c}{539}    &   \multicolumn{2}{c}{591}   &  \multicolumn{2}{c}{539}      \\ %\hline

Number of runs ($n$)&   \multicolumn{2}{c}{~43}      &  \multicolumn{2}{c}{~53}     &    \multicolumn{2}{c}{~56}    &   \multicolumn{2}{c}{~46}    \\ \hline

                           &  {$\bar{x}$}  & {s.d.} &  {$\bar{x}$}  & {s.d.} &  {$\bar{x}$}  & {s.d.} &  {$\bar{x}$}  & {s.d.} \\ %\hline

Decisions 
            &  8974 &   0.0    & 8974   &   0.0   &   8958  &   0.0   &  8958 &   0.0    \\ %\hline
Outputs  
            & 109.1 &   6.71   & 142.8  &   7.03  &   1704  &   42.7  &  869  &   12.8    \\ %\hline


%Elaboration Cycles 
%($\bar{x},\, s.d.$)
%            &  1590 &  96.9    & 1991   &   109   &   11820 &   296   &  7246 &   130    \\ %\hline

Rule Firings 
            &  2438 &   122    & 2064   &   81.1  &   16540 &   398   &  6321 &   104    \\ %\hline

CPU Time (msec)
            &  1683 &  301     & 1030   &   242   &   12576 &   861   &  2175 &   389    \\ \hline


\end{tabular}
\caption{Summary of $\mu$TAS run data.}
\label{tab:utas:summary}
\end{centering}
\end{table}





\subsubsection{Results}


Table~\ref{tab:utas:summary} lists average data for the \soarS\ and
\soarE\ lead and wing agents for the patrol/intercept scenario after
the modifications to the \soarE\ agent's knowledge base were
completed.  The results in this domain are consistent with
expectations: total knowledge decreases, rule firings decrease and
performance improves, substantially so for the \soarE\ wing agent.
The following sections explore each of these results in greater
detail.


\subsubsection{Knowledge Differences}
\label{chap:data:sec:utas:know}




Table~\ref{tab:utas:knowledge} quantifies the changes to the Soar
production rules described above.\footnote{The \soarE\ agent data was
generated with a knowledge base that included some changes to
accommodate learning \cite{Wray98:Ensuring} and these changes are
included in the table for completeness.  The presence of these rules
in the knowledge base has negligible impact on the performance data
reported here.}  Modifications include deletions, additions and
changes.  A rule was considered ``changed'' only if its conditions
changed slightly, but it made the same type of computation for the
same subtask.  For example, most of the ``changed'' within-level
consistency knowledge now refers to an entailed structure rather than
one created as an assumption, but that structure is located in the same
subtask.  This somewhat restrictive definition of a change inflates
the addition and deletion accounting.  In many cases a production was
``deleted'' and then immediately ``added'' to a different subtask.
For example, the productions that manipulate motor commands were all
moved from local subtasks to the highest subtask.  Almost all the
additions and deletions in the ``Remembering'' category can be
attributed to this move, which required no synthesis of new production
knowledge.





Total knowledge required for the \soarE\ agents decreased.  This
approximately 9\% reduction was achieved by making some type of
modification to about 40\% of the \soarS\ agent rules, and may seem a
modest gain, given the conversion cost.  However, this cost is an
artifact of the chosen methodology.  Had the \soarE\ agents been
constructed in this domain without previously existing \soarS\ agents,
at least a 9\% decrease in the total knowledge would be expected.
This result thus suggests a reduction in the cost of the agent design.
The high conversion cost does suggest that converting a much larger
system, like \TAS, would probably be very costly.  On the other hand,
the modifications were made evident by identifiable regenerations in
the architecture.  Thus, the 235 total changes made to the \soarS\
knowledge base were much easier to make than constructing a similar
number of rules.

\begin{table}
\begin{centering}
\begin{tabular}{ l  r  r  r  r  r  r   r }
\hline
& \begin{sideways}\parbox{1.2in}{Across-level \\ Consistency} \end{sideways} & 
  \begin{sideways}\parbox{1.2in}{Remembering} \end{sideways} & 
  \begin{sideways}\parbox{1.2in}{Within-level \\ Consistency} \end{sideways} &  
  \begin{sideways}\parbox{1.2in}{Complex \\ Subtasks} \end{sideways} & 
  \begin{sideways}\parbox{1.2in}{Learning} \end{sideways} &  
  \begin{sideways}\parbox{1.2in}{Miscellaneous} \end{sideways} &  
  TOTALS \\ \hline
\multicolumn{7}{l}{\soarS\ Agent:} & 591 \\ %\hline
Deletions: &   44  & 36 &  9  & 10 &  4 & 8 & (111) \\ %\hline
Additions: &    0  & 32 &  5  & 21 &  0 & 1 & 59  \\ \hline
\multicolumn{7}{l}{\soarE\ Agent:} & {539}\\ %\hline
Additional Changes:   &    0  & 33 &  8  & 0  & 24 & 0 & 65 \\ \hline
\end{tabular}
\caption[Quantitative changes to 
production rules for the \soarE\ \utas\ agent]{Quantitative summary of changes to 
production rules in the \soarS\ agent knowledge base for 
\soarE\ agents.  }
\label{tab:utas:knowledge}
\end{centering}
\end{table}



\subsubsection{Performance Differences}
\label{chap:data:sec:utas:perf}


As the performance results in Table~\ref{tab:utas:summary} show,
\soarE\ agents improved in performance relative to their \soarS\
peers.  However, the improvements of the lead and wing agents was
substantially different.  Differences in the tasks of 
lead and wing pilots led to the differences in relative
improvements.



\noindent{\textbf{Lead and Wing Agents}:} The
lead and wing agent share the same knowledge base but perform
different tasks in the \utas\ scenario.\footnote{The agents share the
same knowledge base because they can dynamically swap roles during
execution.  For instance, if the lead exhausts its long-range
missiles, it will order the wing to take over the lead role, and then
take the role of wing itself.}  These differences lead to differences
in their absolute performance.  Recall that the lead's primary
responsibility is to fly the patrol route and intercept enemy
aircraft.  On the other hand, the wing's primary mission role is to
follow the lead.  These different tasks require different responses in
the agents.

An agent's overall reasoning activity is often correlated with its
output activity; that is, the commands it sends to the external
environment to take action in it.
Figure~\ref{fig:utas.soar8.time.vs.cum.outputs.5} summarizes the
output activity of two pairs of lead and wing agents (\soarS\ \&
\soarE) over the course of a ten-minute scenario.  The output activity
of both leads is mostly concentrated at a few places over the course
of the scenario (\op{take-off}, \op{intercept}, \op{launch-missile},
and when resuming patrol following the intercept).  The wings' most
concentrated output activity occurs when the leads turn to a new leg
of the patrol and the wings must follow the lead through a 180 degree
turn.  In the remainder of this section, we focus only on \soarE\
agents to contrast lead and wing agent behavior.  The discussion of
the performance metrics will examine differences between \soarS\ and
\soarE\ leads and wings.

\begin{figure}
\psfig{figure=figures/CumulativeOutputsWithFHJ.EPS,height=4.0in}
\caption[Cumulative outputs for \soarE\ agents in \utas]{Cumulative outputs over the course of one ten minute 
  scenario for \soarE\ (black) and \soarS\ (gray) agents.  Cumulative outputs for lead agents are represented with solid lines, wing agents with dashed lines.}
\label{fig:utas.soar8.time.vs.cum.outputs.5}
\end{figure}


The lead actually spends most of the scenario waiting, with short
bursts of reasoning and output activity occurring at tactically
important junctures in the scenario.  On patrol, the lead flies
straight and makes a decision to turn when it reaches the end of a
patrol leg.  The lead monitors the environment and searches for enemy
planes.  This search is (mostly) passive; the agent's radar notifies
the agent if any new entities have been detected.  After detecting and
classifying an enemy plane as a potential threat, the lead commits to
an intercept.  The lead immediately makes a number of course, speed,
and altitude adjustments, based on the tactical situation.  These
actions are evident in the figure by the pulse labeled ``intercept.''
The lead spends most of the time in the intercept closing the distance
between the aircraft to get within weapon range, again having to
maneuver very little and thus requiring few actions in the environment
(thus the relatively flat slope following intercept).  When the agent
reaches missile range of the enemy plane, the lead executes a number
of actions very quickly.  The lead steers the plane into a launch
window for the missile, pushes the fire button, waits for the missile
to clear, and then determines a course to maintain radar contact as
the missile flies to its target (at \op{launch-missile}).  Once the
intercept has been completed, the lead resumes its patrol task.
Again, it issues a large number of output commands in a short period
of time.  These examples show that the lead's reasoning focuses
primarily on reacting to discrete changes in the tactical situation
(patrol leg ended, enemy in range, etc.) and the behavior generally
requires little continuous adjustment.

The execution of the wing's \op{follow-leader} task, on the other
hand, requires reaction to continuous change in the lead's position in
order to maintain formation.  Position corrections require observing
the lead's position, recognizing an undesired separation in the
formation, and then responding by adjusting speed, course, altitude,
etc.  Because the wing is following the lead throughout the scenario,
it is executing this position maintenance knowledge almost constantly.
When the lead is flying straight and level, as on a patrol leg, the
wing's task does not require the generation of many outputs.  In
Figure~\ref{fig:utas.soar8.time.vs.cum.outputs.5}, these periods of
little activity are evident in the periodic flat segments in the
wing's cumulative outputs.  When the lead begins a maneuver (e.g., a
turn), the wing must maintain the formation throughout the maneuver.
During a turn the wing generates many motor commands as it follows the
lead.  Because the turn takes a few seconds to complete, the outputs
increase gradually over the course of the turn, as can be seen in the
figure.  Thus, the wing periodically encounters a dynamic situation
that requires significant reasoning and motor responses.  Further, the
response to this change is not discrete, as in the lead, but occurs
continuously over the course of the lead's maneuver.

These differences in the tasks for the two agents account for the
relatively large absolute differences in the performance metrics
between the lead and wing agents.  Because the wings are adjusting
their positions relative to the leads, they issue many more output
commands than the leads, which requires many more inferences to
determine what those commands should be.


\noindent{\textbf{Decisions}:}    
The differences between decisions in the lead and wing is due to an
artifact of the data collection.  The lead agents ran for an extra
second after the wings halted in order to initiate data collection.


\noindent{\textbf{Production Firings}:} In both the lead and wing
agents, production firings decrease.  However, the wing's production
firings decrease by 62\%, while in the lead, the decrease is only
15\%.  One reason for the large improvement in the \soarE\ wing is due
to the elimination of some redundant output commands in the \soarS\
agents.  The \soarS\ wing sometimes issues the same motor command more
than once.  The reason for this duplication is that a specific motor
command is computed locally, and is thus not available to other
subtasks.  In some cases, two subtasks may issue the same motor
command.  When the command is stored locally, a command may be issued
again because the agent cannot recognize that the command has already
been issued by another subtask.  Because motor commands are remembered
in the top subtask by \soarE\ agents, they can be inspected by all
subtasks.  The \soarE\ wing thus never issues a redundant motor
command.  The large relative decrease in outputs in the wing agent
from \soarS\ to \soarE\
(Figure~\ref{fig:utas.soar8.time.vs.cum.outputs.5}) can be attributed
to this improvement.  Production firings decrease with the decrease in
output activity because most reasoning activity in the wing concerns
reacting to the lead's maneuvers.

In contrast to the wing, the lead's average number of outputs actually
increases.  Regeneration is the source of these additional outputs.
In a few situations, a \soarE\ agent's subtask for adjusting heading,
speed or altitude can get updated repeatedly in a highly dynamic
situation (e.g., a hard turn).  The \soarS\ agent uses subtask
knowledge to decide if the current output command needs to be updated.
However, in \soarE, the subtask may be retracted due to dependence on
a changing value (e.g., current heading).  When the subtask is
regenerated following a retraction, the lead may generate a slightly
different motor command.  For example, the lead might decide to turn
to heading 90.1$^\circ$ instead of 90.2$^\circ$.  This decision causes
the generation of a new output command that would not have been
re-issued in \soarS\ agents and accounts for the small increase in
outputs.  It also suggests
that without the self-imposed constraint of the methodology, the
knowledge base could be further modified to avoid this regeneration
and further decrease production firings.

Although the large magnitude of the improvement in the wing is
primarily due to remembering motor commands, both agents also needed
less consistency knowledge and thus accessed less knowledge while
performing the same task.  The agents perform the same tasks using
less knowledge.

\noindent{\textbf{CPU Time}:} CPU time decreases in both the \soarE\
lead and wing agents.  The improvement in the lead (39\%) is about
half the improvement in the wing (81\%).  These differences are due
primarily to the decrease in production firings.  There are fewer
production firings and thus fewer instantiations to generate, leading
to improvements in CPU time.  Match time also improved, contributing
to the overall performance improvement.\footnote{As in the \BW, these
trends are based on a few observations of the data, rather than a
significant analysis.  In particular, in \utas, data for the number of
tokens generated was not collected.  The results reported here are
consistent with the expectation that the token activity falls in
\soarE\ agents, as compared to \soarS\ agents.}  The larger
improvements in CPU time as compared to production firings
improvements (39\% vs. 15\% in the lead, 81\% vs. 62\% in the wing)
might be attributable to decreases in both the number of rule firings
and match time.  Again, these results offer no guarantee that match
time will always decrease with \solutionabbr.  It is important to
note, however, in two very different domains \solutionabbr\ reduces
total knowledge and further constrains the remaining knowledge.  The
architecture then leveraged these small differences for improved
overall performance.


\subsubsection{Differences in Responsiveness}
\label{chap:data:sec:utas:response}

\begin{table}
\begin{centering}
\begin{tabular}{l r r r  r  }
\hline
& {Avg. In-Range Time} &  {Avg. Launch Time} &  {Reaction Time} & \\  %\hline
& {(sec)} &  {(sec)} &  {(sec)} & $n$ \\  \hline
\soarS\ & 161.816    & 162.084 &  .268 & 95  \\ %\hline
\soarE\ & 162.048    & 162.993 &  .945 & 99  \\ \hline
\end{tabular}
\caption{A comparison of average reaction times for launching a missile in 
  \utas.}
\label{tab:utas:reaction-time}
\end{centering}
\end{table}

Because CPU time decreases in the \soarE\ agents, responsiveness
should generally improve.  However, because some agent knowledge has
been split into several different subtasks, some actions may not
be initiated as quickly as would be initiated by the \soarS\ agent.
In this section, we explore differences in responsiveness in one of
these situations.

When an enemy plane comes in range, the agent executes a series of
actions, leading to the firing of a missile.  \emph{Reaction time} is
the difference between the time at which an enemy agent comes in range
and the time when the agent actually pushes the fire button to launch
a missile.  This reaction time is one measure of the agent's
responsiveness.  As Table~\ref{tab:utas:reaction-time} shows, the
\soarS\ agent is able to launch the missile in just over a quarter of
a second.  However, the \soarE\ agent is about three-and-a-half times
slower than the \soarS\ agent in launching the missile, taking almost
a full second, on average.  



Split subtasks, regeneration, and subtask selection all contribute to
the increase in reaction time. Splitting a subtask with $n$ steps,
which may have all been executed in a single decision previously, may
now take $n$ decisions in the \soarE\ agent.  Only a few actions are
necessary for launching a missile so one would expect an increase of,
at most, a few hundred milliseconds for this change.  However, by
dividing subtasks into separate steps, the sequential series of
actions can be interrupted.  In particular, a number of regenerations
occur under the \op{launch-missile} subtask as the agent prepares to
fire the missile in a highly dynamic situation.  The agent sometimes
chooses to undertake a similar action because the situation has
changed enough that a slightly different action might be necessary, as
described above.  The result is that the \soarE\ agents are taking
more accurate aim than the \soarS\ agents, as they are responding more
quickly to the dynamics of the environment.  This ``aiming,'' however
takes more time, although the increase in time is not tactically
significant (i.e., enemy planes were not escaping that were previously
hit by \soarS\ agents).





Some additional re-engineering of the knowledge would improve the
reaction time (e.g., as described in Section~\ref{sec:interruption}).
However, decreases in responsiveness  will be difficult to avoid, in general.
\dhj\ requires that subtasks with different dependencies be initiated
and terminated separately, or risk unnecessary regeneration.  However,
by splitting complex tasks into separate subtasks, individual actions
are delayed both because the subtasks are now separate procedures, and
because the selection for a particular subtask in the series can be
postponed when additional subtask choices are available.

\begin{figure}[h]
\psfig{figure=figures/SummaryFigure.EPS,height=3.5in}
\caption{Mean CPU Time \emph{vs.} knowledge in productions for \soarS\
(black) and \soarE\ (gray) agents in the \BW\ and \utas. The graph
includes the actual distribution of CPU time for each agent as well as
the mean for each agent.  Means for the \BW\ agents are illustrated
with squares, \utas\ lead agents with triangles, and \utas\ wing agents
with diamonds. }
\label{empirical.summary} 
\end{figure}



\subsection{Summary of Empirical Evaluations}

Figure~\ref{empirical.summary} summarizes results from the \BW\ and
\utas.  In both domains, \soarE\ agents require fewer total
productions, suggesting a decrease in knowledge cost.  Performance is
roughly the same in the \BW\ and for the lead agents in \utas.  The
\soarE\ wing agents show a much greater improvement in overall
performance, which is due both to \solutionabbr\ and to changes in
knowledge.  These results suggest that \solution\ can be expected to
reduce engineering effort and not degrade performance in a variety of
domains, simple and complex.  However, response time in some
situations may decrease.







\section{Discussion}


\label{sec:discussion}

Solutions other than KBAC and the new solutions introduced here can be
developed for the inconsistency problem \cite{Wray98:Ensuring}.  We
briefly introduce a few additional solutions, and also consider the
relationship of \dhj\ to intention reconsideration in
belief-desire-intention agents and belief revision.


\subsection{Other solutions to inconsistency across the hierarchy}

In this section, we review other existing architectural  solutions to
the problem of inconsistency arising from persistence in a hierarchy
of assertions.

\subsubsection{Limiting Persistence}
\label{approach:limit}

One obvious approach to eliminating inconsistency arising from
persistence is to disallow persistent assumptions altogether.  This
approach was adopted in Theo \cite{Mitchell91:Theo}.  All reasoning
in Theo is entailed from sensors; only perceptual inputs are
unjustified.  Theo cannot reason non-monotonically about any
\emph{particular} world state; only the world can change
non-monotonically.  Thus, Theo cannot generally remember previous
inputs.

Another possible limitation would be to restrict all assumptions to a
single memory (global state), or, equivalently, allow assumptions only
in the root level of the hierarchy in a hierarchical architecture.
This solution ensures that the hierarchical context is always
consistent (all assertions within an associated subtask are
entailments) and also allows persistence.  Because HTN execution
systems such as RETSINA and DECAF, mentioned previously, have only a
global state, they obviously do not suffer from inconsistency over a
hierarchy.  However, the interactions between persistent assertions
and new information derived from sensors will be a problem in systems
with global state.

RETSINA has recently adopted \emph{rationale-based monitoring}
\cite{Veloso98:Rationale-based} to identify environmental changes
that could impact a currently executing task network
\shortcite{Paolucci99:Planning}.
{Rationale-based monitoring} uses the structure of plan knowledge (in
this case, plan operators, including task networks) to alleviate
inconsistency.  Monitors for relevant world features are created
dynamically as planning progresses by identifying pre-conditions in
operators and instantiating them via a straightforward taxonomy of
monitor types (e.g., a monitor for quantified conditions).  The
collection of monitors form a
\emph{plan rationale}, ``reasons that support a planner's decisions''
\cite{Veloso98:Rationale-based}.  Plan rationales are thus similar
to the justifications used in truth maintenance.  Monitors are
activated when a pre-condition element in the world changes.  They
then inform the planner of the change, and the planner can then
deliberate about whether the change should impact the plan under
construction and, if so, consider appropriate repairs.

Rationale-based monitoring is similar to \dhj, especially because they
both leverage the structures of their (different) underlying task
representations to provide consistency.  However, there are two
important differences.  First, because \dhjabbr\ identifies the
specific subtask impacted by a change, it does not require
deliberation to determine the impact of the change; immediate return
to a consistent knowledge state is possible.  When a monitor is
activated in rationale-based monitoring, the planner must first
determine where and how the plan is affected, which can require
deliberation. Second, because monitors trigger deliberation, rather
than automatically retracting reasoning, an agent using
rationale-based monitoring can determine if the plan should be
repaired and how.  \dhjabbr\ (as implemented) does not offer this
flexibility; retraction is automatic.  Automatic retraction assumes
the cost of retrieving (or regenerating) pre-existing plan knowledge
is less costly than deliberation to determine if/how the plan can be
revised.  Because plan modification can be as expensive as plan
generation \cite{Nebel95:Plan}, this assumption is reasonable.
However, invoking a deliberate revision process could circumvent
potential problems arising from recovery from interruption
(Section~\ref{sec:interruption}).


\subsubsection{Fixed Hierarchical Justification}
\label{approach:fhj}

As mentioned previously, both the pre-DHJ version of Soar and the
Procedural Reasoning System (PRS) \cite{Georgeff87:Reactive} use \fhj\
to retract complete levels of the hierarchy when the support set no
longer holds.  In PRS, the support set consists of a set of context
elements that must hold during the execution of the subtask.  These
elements are defined by a knowledge engineer.  \fhj\ offers a complete
solution to the inconsistency problem if context references within the
reasoning in a subtask are limited to the support set.  This approach
guarantees consistency.  However, it requires that the knowledge
designer identify all potentially relevant features used in reasoning
within the subtask.  Additionally, the resulting system may be overly
sensitive to the features in the support set if those features only
rarely impact reasoning, leading to unnecessary regeneration.

\fhj\ requires less explicit consistency knowledge than
knowledge-based solutions.  However, KBAC knowledge is still required
if access to the whole task hierarchy is possible.  Thus, an agent's
ability to make subtask-specific reactions to unexpected changes in
the environ\-ment is limited by the knowledge designer's ability to
anticipate and explicitly encode the consequences of those changes.




\subsection{Intention Reconsideration} 
\label{dis:intent}

In the belief-desire-intention (BDI) model of agency, an intention
represents a commitment to achieving a goal
\cite{Rao91:Modeling,Wooldridge00:Reasoning}.  An intention is thus
similar to the instantiation of a subtask in a hierarchical
architecture.

\dhj\ can be viewed as a partial implementation 
of \emph{intention reconsideration}
\cite{Schut00:Intention,Schut01:Principles}.  Intention reconsideration
is the process of determining when an agent should abandon its
intentions (due to goal achievement, recognition of failure, or
recognition that the intention itself is no longer desired).  \dhj\ is
only a partial implementation of intention reconsideration because it
is only able to capture syntactic features of the problem solving
(i.e., the identification of dependencies via the support set) to
determine when to reconsider an intention.  Situations that require
deliberation to determine that an intention should be abandoned are
not captured in
\dhjabbr.\footnote{\dhjabbr\ does not preclude deliberate reconsideration.
However, Soar (as the testbed for the exploration of
\dhjabbr) does not provide  an architectural solution for
deliberate reconsideration.  Thus, these situations will be addressed
through knowledge and the deliberative processes of the architecture.}
Schut \& Wooldridge (2001) describe an initial attempt to allow the
run-time determination of reconsideration policies.  An optimal policy
would maximize the likelihood that deliberate intention
reconsideration actually leads to abandoning an intention (i.e., the
agent reconsiders when reconsideration is necessary).  In contrast,
\dhj\ offers a low-cost, always available, domain general process for
abandoning intentions, but cannot automatically identify
reconsiderations requiring semantic analysis of the problem state.

In BDI models, agents can choose to execute their current action plans
with or without reconsidering their current intentions first.  Kinny
and Georgeff (1991) \nocite{Kinny91:Commitment} showed that, in more
static domains, ``bold'' agents that never reconsider their intentions
perform more effectively than ``cautious'' agents that always
reconsider before executing a plan step.  The opposite is true in
highly dynamic domains: ``cautious'' agents out perform ``bold'' ones.
Both Soar and PRS can be described as being cautious via \fhj.  That
is, at each plan step, the architectures determine if elements in the
support set remain asserted before executing the step.  \fhjabbr\
approaches are, in effect, more ``bold'' than they appear, because
they do not reconsider intentions when assertions have changed in the
dependent context, but not in the support set.  \dhj\ provides more
``cautious'' agents, because it ensures that the agent's
reconsideration function takes into account {all} context dependencies
for subtask reasoning.  From the perspective of intention
reconsideration, the problems introduced by more dynamic domains
prompted us to explore more ``cautious'' solutions.

The results of the empirical analysis were somewhat consistent with
those of Kinny \& Georgeff.  The ``cautious'' \dhjabbr\ agents
performed better than less ``cautious'' \fhjabbr\ agents in the highly
dynamic \uTAS\ domain.  In the \BW, the performance differences were
more equivocal.  In comparison to \fhjabbr\, the number of new
intentions increased with \dhj\ (measured as Soar decisions).  While
there was a slight overall performance improvement with \dhjabbr, it
was due to improvements in the match time of productions, a
Soar-specific measure that likely will not generalize to other
systems.  These results suggest that \dhjabbr\ is possibly overly
cautious in static domains.  However, because \dhj\ did not present a
significant performance cost and unexpectedly played a constructive
role in agent execution even in the static domain, \dhjabbr\ seems
warranted in both static and dynamic domains.



\subsection{Belief Revision}

Belief Revision refers to the process of changing beliefs to
accommodate newly acquired information.  The inconsistency problem is
an example of the need for revision in asserted beliefs: some change
in the hierarchical context (deriving ultimately from perceived
changes in the world) leads to a situation in which a currently
asserted assumption would not (necessarily) be regenerated if it were
re-derived.  Theories of belief revision identify functions that can
be used to update a belief set so that it remains consistent.

The best known theory of belief revision is the ``AGM'' theory
\cite{Alchourron85:Logic,Gardenfors88:Knowledge,Gardenfors92:Belief}.
AGM is a \emph{coherence} theory, meaning that changes to beliefs are
determined based on mutual coherence with one another.  This approach
contrasts with the \emph{foundations} approach, in which
justifications (reasons) determine when/how to revise a belief set.
Obviously,
\dhj\ is an extension to the foundations approach to belief 
revision.  However, as the foundations and coherence
approaches can be  reconciled \cite{Doyle94:Reason}, in this section we
explore the repercussions of \dhj\ in the context of the AGM theory of
belief revision.


In AGM theory, when a new sentence is presented to a database of
sentences representing the current knowledge state, an agent is faced
with the task of revising its knowledge base via one of three
processes: expansion (adding sentences to the knowledge base),
contraction (removing sentences from the knowledge base) and revision
(a combination of expansions and contractions).  AGM theory emphasizes
making minimal changes to a knowledge base and epistemic entrenchment,
a notion of the usefulness of a sentence within the database. AGM theory
prefers that sentences with high epistemic entrenchment (relative to
other sentences) are retained during revision.

Comparing \dhj\ to \aj\ suggests that it is sometimes cheaper to
remove a subtask (and all asserted beliefs associated with that
subtask) than it is to compute the minimal revision with \aj.  In the
context of belief revision, this result is not surprising, since it
has been shown that computing a minimal revision to a knowledge base
can be computationally harder than deduction
\cite{Eiter92:Complexity}.  This theoretical result has led to
applications that compute belief updates via incremental derivations
of a belief state, rather than via belief revision
\cite{Kurien00:Back}.

The power of the heuristic approach used by \solutionabbr\ over the
analytic solution follows from the characteristics outlined in
Section~\ref{dhj:decompositions}: the hierarchical structure and
organization of the agent assertions and the efficiency of the
underlying reasoning system to regenerate any unnecessarily removed
assertions.  Assumptions (persistent beliefs) are associated with
particular subtasks in hierarchical architectures.  A change in
perception (an epistemic input) leads to a revision.  Rather than
determining the minimal revision, \dhjabbr\ uses a heuristic that, in
this context, says that persistent beliefs in a subtask have similar
epistemic entrenchment to the subtask/intention itself.  In some
cases, this heuristic will be incorrect, leading to regeneration, but,
when correct, it provides a much simpler mechanism for revision.
G\"{a}rdenfors (1988) anticipates such conclusions, suggesting that
systems possessing additional internal structure (as compared to the
the relatively unstructured belief sets of AGM theory) may provide
additional constraints for orderings of epistemic entrenchment.











\section{Conclusion} 
\label{conclusion}

The empirical results from both the \BW\ and \utas\ domains were
consistent with expectations: knowledge engineering cost decreased and
overall performance in \soarE\ was roughly the same (or slightly
improved) in comparison to independently-developed \soarS\ benchmarks.
Development cost decreases because the designer is freed from the task
of creating across-level consistency knowledge.  One drawback of
\dhjabbr\ is that responsiveness can degrade when regeneration occurs.

\dhjabbr\ has been incorporated into the currently released version of
Soar (Soar~8) for over 3 years and the experience of users further
confirms that development cost decreases.  It is partly true that
developers need a deeper understanding of the architecture to realize
this benefit.  However, \solutionabbr\ removes the need for the
encoding of across-level consistency knowledge, which has proven
difficult to understand and encode in many systems.  \dhjabbr\ also
makes understanding the role of assumptions in Soar systems more
straightforward, by imposing design and development constraints.  For
instance, the knowledge designer must now think about why, when, and
where persistence should be used in the agent.  Once the knowledge
designer determines the functional role of some persistent assumption,
\solutionabbr\ guides the development of the knowledge necessary for
that assumption.  For a nonmonotonic or hypothetical assumption, no
knowledge must be created that ``looks outside'' the subtask in order
to ensure consistency (i.e., no across-level knowledge is necessary).
Assumptions for remembering must be asserted in the root level of the
hierarchy, and knowledge must be created to manage the remembered
assumption.  Functions of the root task now include monitoring,
updating, and removing remembered assumptions (we are developing
domain-general methods for managing these remembered assumptions to
further reduce cost).  Thus, while \solutionabbr\ does increase the
complexity of the architecture, it makes design decisions more
explicit and manageable than previous KBAC approaches.

Regeneration, seemingly one of the drawbacks of \dhjabbr, also
contributes to decreased knowledge development costs.  Regeneration
serves as a debugging tool, allowing immediate localization of problem
areas in the domain knowledge (and its specific decomposition).  This
debugging aid contrasts with previous knowledge development in which
inconsistency often became evident only in irrational behavior, making
it often difficult to determine the actual source of a problem.
Thus, in addition to reducing total knowledge necessary for some task,
\solution\ might also reduce the cost per knowledge unit when creating
agent knowledge by localizing problems via regeneration.  However, if
it is the case that some domain cannot be decomposed into nearly
decomposable subunits, regeneration could be debilitating.


Another positive consequence of \solutionabbr\ is that an agent may
behave more robustly in novel situations not anticipated by the
knowledge engineer.  For example, as a simple experiment, the \soarS\
and \soarE\ \BW\ agents were placed in the situation described in
Figure~\ref{fig:chap2.brittle}.  The \soarS\ agent fails when the
block moves because it lacks knowledge to recognize moving blocks; the
knowledge designer assumed a static domain. With the same knowledge,
however, the \soarE\ agent responds to this situation gracefully. In
the specific situation in Figure~\ref{fig:chap2.brittle}, the \soarE\
agent immediately retracts the \op{put-on-table(3)} subtask, because
\obj{block-3} is on the table, and thus the selection of that subtask
is no longer consistent with the current situation. The agent then
chooses \op{stack(2,3)} and decomposes this subtask into actions to
put \obj{block-2} on \obj{block-3}.  If a new block (e.g.,
\obj{block-4}) is placed in the \reli{empty} space below
\obj{block-2}, the architecture responds by retracting the subtask
goal for \op{put-down(2)} (i.e., the subtask that contains the
\reli{empty} assumption).  It then begins to search for empty spaces
in order to continue its attempt to put \obj{block-2} on the table.
Because the architecture, rather than agent knowledge, ensures
consistency across the hierarchy, \soarE\ agents should be less
brittle in situations not explicitly anticipated in agent design.

\solutionabbr\ also provides a solution to the problem of learning
rules with non-contemporaneous constraints \cite{Wray96:Compilation}.
Non-contemporaneous constraints arise when temporally distinct
assertions (e.g., red light, green light) are collected in a single
learned rule via knowledge compilation.  A rule with
non-contemporaneous constraints will not lead to inappropriate
behavior but rather will never apply.  This problem makes it difficult
to use straightforward explanation-based learning approaches to
operationalize agent execution knowledge.  Non-contemporaneous
constraints arise when the architecture creates persistent assumptions
that can become inconsistent with the hierarchical context
\cite{Wray96:Compilation}.  Because \solutionabbr\ never allows such
inconsistency, it solves the non-contemporaneous problem.  For
instance, agents in both the \BW\ and \utas\ were able to learn
unproblematically in the new architecture, with no/little knowledge
re-design. \citeA{Wray98:Ensuring} provides additional details and an
empirical assessment of the learning.

\solution\ operates at a higher level of granularity than \aj\ or
knowledge-based solution methods, trading fine-grained consistency for
lower computational cost.  This higher level of abstraction does
introduce additional cost in execution.  In particular, necessary
regeneration led to some redundancy in knowledge search in both the
\BW\ and \utas\ agents. Although overall efficiency improved, some of
the improvement was due to improvements in the average match cost of
productions, which cannot be guaranteed in all domains or in other
architectures. Further, \solution\ requires that complex subtasks be
split into distinct subtasks.  This requirement improves the knowledge
decomposition and reduces regeneration in performance but can reduce
responsiveness.  However, with the straightforward compilation of
reasoning in subtasks that \solutionabbr\ enables, the reduction in
responsiveness can be overcome with learning \cite{Wray98:Ensuring}.

Although the implementation and evaluation of \dhjabbr\ was limited to
Soar, we attempted to reduce the specificity of the results to Soar in
two ways.  First, we identified the problems that across-level
consistency knowledge introduces in knowledge-based approaches: it is
expensive to develop, degrades the modularity and simplicity of the
hierarchical representation, and is only as robust as the knowledge
designer's imagination.  When agents are developed in sufficiently
complex domains, the expense of creating this knowledge will grow
prohibitive.  This cost may lead additional researchers to consider
architectural assurances of consistency.  Second, \solution\ gains its
power via the structure of hierarchically decomposed tasks.  Although
specific implementations may differ for other agent architectures, the
heuristic simplifications employed by \solutionabbr\ should transfer
to any architecture utilizing a hierarchical organization of memory
for task decomposition.  \solution\ is an efficient, architectural
solution that ensures reasoning consistency across the hierarchy in
agents employing hierarchical task decompositions.  This solution
allows agents to act more reliably in complex, dynamic environments
while more fully realizing low cost agent development via \htd.
  

\section*{Acknowledgments}

This work would not have been possible without those who contributed
directly to the development and evaluation of \solution.  Scott
Huffman, John Laird and Mark Portelli implemented \aj\ in Soar.  Ron
Chong implemented a precursor to \solutionabbr. Randy Jones, John
Laird, and Frank Koss developed \uTAS.  Sayan Bhattacharyya, Randy
Jones, Doug Pearson, Peter Wiemer-Hastings, and other members of the
Soar group at the University of Michigan contributed to the
development of the \BW\ simulator.  The anonymous reviewers provided
valuable, constructive comments on earlier versions of the manuscript.
This work was supported in part by a University of Michigan Rackham
Graduate School Pre-doctoral fellowship, contract N00014-92-K-2015
from the Advanced Systems Technology Office of DARPA and NRL, and
contract N6600I-95-C-6013 from the Advanced Systems Technology Office
of DARPA and the Naval Command and Ocean Surveillance Center, RDT\&E
division.  Portions of this work were presented at the 15$^{th}$
National Conference on Artificial Intelligence in Madison, Wisconsin.
\nocite{Wray98:Maintaining}

%\begin{figure}
%\psfrag{Y Data}{\LARGE Productions }
%\psfrag{X Data}{\LARGE CPU (time) }
%\insertfigure{GraphTestForJAIR}{3.0in}
%\caption{Technical problems with \aj.  In (a), an assumption replaces another assumption nonmonotonically.  In (b), multiple assumption justifications for the same assumption must be supported.}
%\end{figure}


%\begin{figure}
%\psfrag{Y Data}{\LARGE Productions }
%\psfrag{X Data}{\LARGE CPU (time) }
%\insertfigure{BlocksForJAIR}{1.0in}
%\caption{Technical problems with \aj.  In (a), an assumption replaces another assumption nonmonotonically.  In (b), multiple assumption justifications for the same assumption must be supported.}
%\end{figure}

\appendix

\section*{Appendix A: Improving Task Decompositions} 

This appendix describes in detail the changes that were made to the 
\utas\ agent knowledge for \solutionabbr.  

\noindent{\textbf{Remembering:}}
Figure~\ref{fig:tas.intercept.decomp} showed an agent computing a new
heading as a subtask of the \op{achieve\--prox\-im\-ity} subtask.
This calculation usually depends upon the current heading.  When the
agent generates the command to turn, the heading changes soon
thereafter.  In this situation, the \soarE\ agent must ``remember''
that it has already made a decision to turn to a new heading by
placing the assumption that reflects the new heading in the top level.
If it places the assumption in the local level, then the new current
heading will trigger the removal of \op{turn-to-heading} and then
regeneration of the subtask (if the agent determines that it still
needs to turn to some new heading).

In the \soarS\ agents, all output commands (such as turn to some
specific heading) were asserted as assumptions in the local subtask.
The \soarE\ agent's knowledge was changed to issue output
commands directly to the output interface (which, in Soar, is always
part of the highest subtask in the hierarchy).  No unnecessary
regeneration now occurs because the agent remembers all motor commands
and generates a new one only when a different output is necessary.
This change, of course, requires consistency knowledge because the
motor commands are unjustified and thus must be explicitly removed, as is
true for any remembered knowledge with \dhjabbr.

\noindent{\textbf{Within-level Consistency Knowledge:}}
\dhj, like all solutions to the across-level consistency
problem, still requires consistency knowledge within an individual
subtask.  Some of this knowledge in the \soarS\ agents is used to
remove intermediate results in the execution of a subtask.  This
``clean up'' knowledge allows the agent to remove local assertions
that contributed to some terminating subtask and thus avoid the
(mis)use of these assertions in later reasoning.

As an example, consider the \op{achieve-proximity} subtask.  This
subtask is used in a number of different situations when an agent
needs to get closer to another agent. If the wing strays too far from
the lead, it may invoke \op{achieve-proximity} to get back into
formation with the lead.  The lead uses \op{achieve-proximity} to get
close enough to an enemy aircraft to launch a missile.  The subtask
requires many local computations as the agent reasons about what
heading it should take to get closer to another aircraft.  The
specific computation depends on what information is available about
the other aircraft.  When the wing is pursuing the lead, it may know
the lead's heading and thus calculate a collision course to maximize
the rate of convergence.  Sometimes the other agent's heading is not
available.  In this case, the agent simply moves toward the current
location of the other agent.  These local computations are stored in
the local subtask.  When \op{achieve-proximity} is terminated in the
\soarS\ agent, the agent removes the local structure.  Removing the
structure is important both because it interrupts entailment of the
local structure (e.g., calculation of the current collision course)
and guarantees that if the agent decides to \op{achieve-proximity}
with a different aircraft, supporting data structures are properly
initialized.  This knowledge thus maintains consistency in the local
subtask by removing the local structure when the
\op{achieve-proximity} subtask is no longer selected.

The \soarS\ agent could recognize when it was going to remove a
subtask.  The termination conditions in \soarS\ agents acted as a
signal to the within-level consistency knowledge.  The knowledge that
removes the local structure for \op{achieve-proximity} can be
summarized as: ``if the \op{achieve-proximity} operator is selected,
but its initiation conditions no longer hold, then remove the local
\op{achieve-proximity} data structure.''  Thus, the \soarS\ agent uses
a recognition of an inconsistency in the assertions to trigger the
activation of this within-level consistency knowledge.

When the subtask's initiating conditions are no longer supported in
the \soarE\ agents, the selected subtask is removed immediately. Thus,
the \soarE\ agent never has the opportunity to apply the \soarS\
agent's within-level consistency knowledge.  The failure to utilize
this knowledge led to a number of problems, including more
regenerations than expected.

To solve this problem, the local subtask data structure was created as
an entailment of the initiation conditions of the subtask itself.
When the subtask initiation conditions no longer held, both the
subtask selection and the local structure are immediately removed  by
the architecture, requiring no additional knowledge.  Thus, this
change obviated the need for some within-level consistency knowledge.
However, the local data structure may need to be regenerated if a
subtask is temporarily displaced.  For instance, the \soarS\
within-level consistency knowledge could determine under what
conditions the local structure should be removed.  The \soarE\
solution has lost that flexibility.

\noindent{\textbf{Subtasks with Complex Actions:}}
\soarS\ agents can execute a number of actions in rapid
succession, regardless of any inconsistency in the local assertions.
A single subtask operator can be initiated in a situation representing
the conditions under which to apply the first action in a sequence,
and terminated when the last step in the sequence has applied.  If
some intermediate step invalidates the initiation conditions, the
subtask still executes the actions.  

Consider the process of launching a missile.
An actual missile launch requires only the push of a button, assuming
that previous steps such as selecting the target and an appropriate
missile have been accomplished beforehand.  After pushing the fire
button, the pilot must fly straight and level for a few seconds while
the missile rockets ignite and launch the missile into flight.  Once the
missile has cleared the aircraft, the agent ``supports'' the missile
by keeping radar contact with the target.  In \soarS\ agents, the
\op{push-fire-button} subtask includes both the act of pushing the
fire button and counting while the missile clears the aircraft.  These
tasks have different and mutually exclusive dependencies.  The
initiation condition for \op{push-fire-button} requires
that no missile is already launched.  However, the subsequent counting
requires monitoring the newly launched missile.

\soarE\ agents using the \soarS\ knowledge base 
always remove the \op{push-fire-but\-ton} subtask as soon as the missile
is perceived to be in the air, interrupting the complete procedure.
Regeneration of the \op{push-fire-button} subtask occurs because the
agent never waits for the missile to clear and thus never realizes
that the missile just launched needs to be supported.  The \soarE\
agent unsuccessfully fires all  available missiles at the enemy
plane.

Pushing the fire button and waiting for the missile to clear are
independent tasks which happen to arise in serial order in the domain.
We enforced this independence by creating a new subtask,
\op{wait-for-missile-to-clear}, which depends only on having a newly
launched missile in the air.  The \soarE\ agent now pushes the fire
button, selects \op{wait-for-missile-to-clear} to count a few seconds
before taking any other action, and then  supports the
missile if it clears successfully.


This solution reduces regeneration and improves behavior quality but
it does have a non-trivial cost.  Whenever a subtask is split, the
effects of subtask actions no longer occur in rapid succession within
a decision.  Instead, the effect of the first subtask occurs in one
decision, the effect of the second subtask in the second decision,
etc.  Thus, this solution can compromise responsiveness.




\vskip 0.2in
%\bibliography{general,personal,knowledge-representation,nonmonotonic-reasoning,software-engineering,cog-sci,soar,agents,textbooks,planning}
\bibliographystyle{theapa}

%\begin{thebibliography}{}

% \bibitem[Names(Year)]{label} or \bibitem[Names(Year)Long names]{label}.
% (\harvarditem{Name}{Year}{label} is also supported.)
% Text of bibliographic item
%\bibitem[]{}

%\end{thebibliography}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Agre\ \BBA\ Horswill}{Agre\ \BBA\
  Horswill}{1997}]{Agre97:Lifeworld}
Agre, P.~E.\BBACOMMA\  \BBA\ Horswill, I. \BBOP1997\BBCP.
\newblock \BBOQ Lifeworld analysis\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 6},
  111--145.

\bibitem[\protect\BCAY{Alchour\'{r}on, G\"{a}rdenfors,\ \BBA\
  Makinson}{Alchour\'{r}on et~al.}{1985}]{Alchourron85:Logic}
Alchour\'{r}on, C.~E., G\"{a}rdenfors, P., \BBA\ Makinson, D. \BBOP1985\BBCP.
\newblock \BBOQ On the logic of theory change: {P}artial meet contraction and
  revision functions\BBCQ\
\newblock {\Bem Journal of Symbolic Logic}, {\Bem 50\/}(2), 510--530.

\bibitem[\protect\BCAY{Allen}{Allen}{1991}]{Allen91:Time}
Allen, J.~F. \BBOP1991\BBCP.
\newblock \BBOQ Time and time again\BBCQ\
\newblock {\Bem International Journal of Intelligent Systems}, {\Bem 6\/}(4),
  341--355.

\bibitem[\protect\BCAY{Altmann\ \BBA\ Gray}{Altmann\ \BBA\
  Gray}{2002}]{Altmann02:Forgetting}
Altmann, E.~M.\BBACOMMA\  \BBA\ Gray, W.~D. \BBOP2002\BBCP.
\newblock \BBOQ Forgetting to remember: {T}he functional relationship of decay
  and interference\BBCQ\
\newblock {\Bem Psychological Science}, {\Bem 13}, 27--33.

\bibitem[\protect\BCAY{Bresina, Drummond,\ \BBA\ Kedar}{Bresina
  et~al.}{1993}]{Bresina93:Reactive}
Bresina, J., Drummond, M., \BBA\ Kedar, S. \BBOP1993\BBCP.
\newblock \BBOQ Reactive, integrated systems pose new problems for machine
  learning\BBCQ\
\newblock In Minton, S.\BED, {\Bem Machine Learning Methods for Planning},
  \BPGS\ 159--195. Morgan Kaufmann, San Francisco, CA.

\bibitem[\protect\BCAY{Dechter}{Dechter}{1990}]{Dechter90:Enhancement}
Dechter, R. \BBOP1990\BBCP.
\newblock \BBOQ Enhancement schemes for constraint processing: {B}ackjumping,
  learning and cutset decomposition\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 41}, 273--312.

\bibitem[\protect\BCAY{Doyle}{Doyle}{1979}]{Doyle79:Truth}
Doyle, J. \BBOP1979\BBCP.
\newblock \BBOQ A truth maintenance system\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 12}, 231--272.

\bibitem[\protect\BCAY{Doyle}{Doyle}{1994}]{Doyle94:Reason}
Doyle, J. \BBOP1994\BBCP.
\newblock \BBOQ Reason maintenance and belief revision\BBCQ\
\newblock In G\"{a}rdenfors, P.\BED, {\Bem Belief Revision}, \BPGS\ 29--51.
  Cambridge University Press, Cambridge, UK.

\bibitem[\protect\BCAY{Eiter\ \BBA\ Gottlob}{Eiter\ \BBA\
  Gottlob}{1992}]{Eiter92:Complexity}
Eiter, T.\BBACOMMA\  \BBA\ Gottlob, G. \BBOP1992\BBCP.
\newblock \BBOQ On the complexity of propositional knowledge base revision,
  updates, and counterfactuals\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 57}, 227--270.

\bibitem[\protect\BCAY{Erol, Hendler,\ \BBA\ Nau}{Erol
  et~al.}{1994}]{Erol94:HTN}
Erol, K., Hendler, J., \BBA\ Nau, D.~S. \BBOP1994\BBCP.
\newblock \BBOQ {HTN} planning: Complexity and expressivity\BBCQ\
\newblock In {\Bem Proceedings of the 12$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 1123--1128.

\bibitem[\protect\BCAY{Firby}{Firby}{1987}]{Firby87:Investigation}
Firby, R.~J. \BBOP1987\BBCP.
\newblock \BBOQ An investigation into reactive planning in complex
  domains\BBCQ\
\newblock In {\Bem Proceedings of the 6$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 202--206.

\bibitem[\protect\BCAY{Forbus\ \BBA\ deKleer}{Forbus\ \BBA\
  deKleer}{1993}]{Forbus93:Building}
Forbus, K.~D.\BBACOMMA\  \BBA\ deKleer, J. \BBOP1993\BBCP.
\newblock {\Bem Building Problem Solvers}.
\newblock MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{Forgy}{Forgy}{1979}]{Forgy79:Efficient}
Forgy, C.~L. \BBOP1979\BBCP.
\newblock {\Bem On the Efficient Implementation of Production Systems}.
\newblock Ph.D.\ thesis, Computer Science Department, Carnegie-Mellon
  University.

\bibitem[\protect\BCAY{G\"{a}rdenfors}{G\"{a}rdenfors}{1988}]{Gardenfors88:Kno%
wledge}
G\"{a}rdenfors, P. \BBOP1988\BBCP.
\newblock {\Bem Knowledge in Flux: Modeling the Dynamics of Epistemic States}.
\newblock MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{G\"{a}rdenfors}{G\"{a}rdenfors}{1992}]{Gardenfors92:Bel%
ief}
G\"{a}rdenfors, P. \BBOP1992\BBCP.
\newblock \BBOQ Belief revision\BBCQ\
\newblock In Pettorossi, A.\BED, {\Bem Meta-Programming in Logic}.
  Springer-Verlag, Berlin, Germany.

\bibitem[\protect\BCAY{Gaschnig}{Gaschnig}{1979}]{Gaschnig79:Performance}
Gaschnig, J. \BBOP1979\BBCP.
\newblock \BBOQ Performance measurement and analysis of certain search
  algorithms\BBCQ\
\newblock \BTR\ CMU-CS-79-124, Computer Science Department, Carnegie-Mellon
  University, Pittsburgh, Pennsylvania.

\bibitem[\protect\BCAY{Gat}{Gat}{1991a}]{Gat91:Integrating}
Gat, E. \BBOP1991a\BBCP.
\newblock \BBOQ Integrating planning and reacting in a heterogeneous
  asynchronous architecture for mobile robots\BBCQ\
\newblock {\Bem SIGART BULLETIN}, {\Bem 2}, 71--74.

\bibitem[\protect\BCAY{Gat}{Gat}{1991b}]{Gat91:Reliable}
Gat, E. \BBOP1991b\BBCP.
\newblock {\Bem Reliable, Goal-directed Control of Autonomous Mobile Robots}.
\newblock Ph.D.\ thesis, Virginia Polytechnic Institute and State University,
  Blacksburg, VA.

\bibitem[\protect\BCAY{Georgeff\ \BBA\ Lansky}{Georgeff\ \BBA\
  Lansky}{1987}]{Georgeff87:Reactive}
Georgeff, M.\BBACOMMA\  \BBA\ Lansky, A.~L. \BBOP1987\BBCP.
\newblock \BBOQ Reactive reasoning and planning\BBCQ\
\newblock In {\Bem Proceedings of the 6$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 677--682.

\bibitem[\protect\BCAY{Graham\ \BBA\ Decker}{Graham\ \BBA\
  Decker}{2000}]{Graham00:Towards}
Graham, J.\BBACOMMA\  \BBA\ Decker, K. \BBOP2000\BBCP.
\newblock \BBOQ Towards a distributed, environment-centered agent
  framework\BBCQ\
\newblock In Wooldridge, M.\BBACOMMA\  \BBA\ Lesperance, Y.\BEDS, {\Bem Lecture
  Notes in Artificial Intelligence: Agent Theories, Architectures, and
  Languages VI (ATAL-99)}. Springer-Verlag, Berlin.

\bibitem[\protect\BCAY{Hanks, Pollack,\ \BBA\ Cohen}{Hanks
  et~al.}{1993}]{Hanks93:Benchmarks}
Hanks, S., Pollack, M., \BBA\ Cohen, P.~R. \BBOP1993\BBCP.
\newblock \BBOQ Benchmarks, test beds, controlled experimentation and the
  design of agent architectures\BBCQ\
\newblock {\Bem AI Magazine}, {\Bem 14}, 17--42.

\bibitem[\protect\BCAY{Hayes-Roth}{Hayes-Roth}{1990}]{Hayes-Roth90:Architectur%
e}
Hayes-Roth, B. \BBOP1990\BBCP.
\newblock \BBOQ An architecture for adaptive intelligent systems\BBCQ\
\newblock In {\Bem Workshop on Innovative Approaches to Planning, Scheduling
  and Control}, \BPGS\ 422--432.

\bibitem[\protect\BCAY{Jones, Laird, Neilsen, Coulter, Kenny,\ \BBA\
  Koss}{Jones et~al.}{1999}]{Jones99:Automated}
Jones, R.~M., Laird, J.~E., Neilsen, P.~E., Coulter, K.~J., Kenny, P., \BBA\
  Koss, F.~V. \BBOP1999\BBCP.
\newblock \BBOQ Automated intelligent pilots for combat flight simulation\BBCQ\
\newblock {\Bem AI Magazine}, {\Bem 20\/}(1), 27--41.

\bibitem[\protect\BCAY{Kinny\ \BBA\ Georgeff}{Kinny\ \BBA\
  Georgeff}{1991}]{Kinny91:Commitment}
Kinny, D.\BBACOMMA\  \BBA\ Georgeff, M. \BBOP1991\BBCP.
\newblock \BBOQ Commitment and effectiveness of situated agents\BBCQ\
\newblock In {\Bem Proceedings of the 12$^{th}$ International Joint Conference
  on Artificial Intelligence}, \BPGS\ 82--88.

\bibitem[\protect\BCAY{Kurien\ \BBA\ Nayak}{Kurien\ \BBA\
  Nayak}{2000}]{Kurien00:Back}
Kurien, J.\BBACOMMA\  \BBA\ Nayak, P.~P. \BBOP2000\BBCP.
\newblock \BBOQ Back to the future for consistency-based trajectory
  tracking\BBCQ\
\newblock In {\Bem Proceedings of the 17$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 370--377.

\bibitem[\protect\BCAY{Laird}{Laird}{2001}]{Laird01:Anticipation}
Laird, J.~E. \BBOP2001\BBCP.
\newblock \BBOQ It knows what you are going to do: {A}dding anticipation to a
  {Q}uakebot\BBCQ\
\newblock In {\Bem Proceedings of the 5$^{th}$ International Conference on
  Autonomous Agents}, \BPGS\ 385--392.

\bibitem[\protect\BCAY{Laird, Congdon,\ \BBA\ Coulter}{Laird
  et~al.}{1999}]{Laird99:Soar8UserManual}
Laird, J.~E., Congdon, C.~B., \BBA\ Coulter, K.~J. \BBOP1999\BBCP.
\newblock \BBOQ Soar user's manual version 8.2\BBCQ\
\newblock Manual, Department of Electrical Engineering and Computer Science,
  University of Michigan, http://ai.eecs.umiuch.edu/soar/docs.html.

\bibitem[\protect\BCAY{Laird, Newell,\ \BBA\ Rosenbloom}{Laird
  et~al.}{1987}]{Laird87:Soar}
Laird, J.~E., Newell, A., \BBA\ Rosenbloom, P.~S. \BBOP1987\BBCP.
\newblock \BBOQ {S}oar: {A}n architecture for general intelligence\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 33}, 1--64.

\bibitem[\protect\BCAY{Laird\ \BBA\ Rosenbloom}{Laird\ \BBA\
  Rosenbloom}{1990}]{Laird90:Integrating}
Laird, J.~E.\BBACOMMA\  \BBA\ Rosenbloom, P.~S. \BBOP1990\BBCP.
\newblock \BBOQ Integrating execution, planning, and learning in {S}oar for
  external environments\BBCQ\
\newblock In {\Bem Proceedings of the 8$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 1022--1029.

\bibitem[\protect\BCAY{Laird\ \BBA\ Rosenbloom}{Laird\ \BBA\
  Rosenbloom}{1995}]{Laird95:Evolution}
Laird, J.~E.\BBACOMMA\  \BBA\ Rosenbloom, P.~S. \BBOP1995\BBCP.
\newblock \BBOQ The evolution of the {S}oar cognitive architecture\BBCQ\
\newblock In Steier, D.\BBACOMMA\  \BBA\ Mitchell, T.\BEDS, {\Bem Mind Matters:
  {C}ontributions to Cognitive and Computer Science in Honor of {A}llen
  {N}ewell}. Lawrence Erlbaum Associates, Hillsdale, NJ.

\bibitem[\protect\BCAY{McDermott}{McDermott}{1991}]{McDermott91:General}
McDermott, D. \BBOP1991\BBCP.
\newblock \BBOQ A general framework for reason maintenance\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 50}, 289--329.

\bibitem[\protect\BCAY{Mitchell, Allen, Chalasani, Cheng, Etzioni, Ringuette,\
  \BBA\ Schlimmer}{Mitchell et~al.}{1991}]{Mitchell91:Theo}
Mitchell, T.~M., Allen, J., Chalasani, P., Cheng, J., Etzioni, O., Ringuette,
  M., \BBA\ Schlimmer, J.~C. \BBOP1991\BBCP.
\newblock \BBOQ Theo: {A} framework for self-improving systems\BBCQ\
\newblock In VanLehn, K.\BED, {\Bem Architectures for Intelligence}, \BCH~12,
  \BPGS\ 323--355. Lawrence Erlbaum Associates, Hillsdale, NJ.

\bibitem[\protect\BCAY{Mitchell}{Mitchell}{1990}]{Mitchell90:Becoming}
Mitchell, T.~M. \BBOP1990\BBCP.
\newblock \BBOQ Becoming increasingly reactive\BBCQ\
\newblock In {\Bem Proceedings of the 8$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 1051--1058.

\bibitem[\protect\BCAY{Nebel\ \BBA\ Koehler}{Nebel\ \BBA\
  Koehler}{1995}]{Nebel95:Plan}
Nebel, B.\BBACOMMA\  \BBA\ Koehler, J. \BBOP1995\BBCP.
\newblock \BBOQ Plan reuse versus plan generation: {A} theoretical and
  empirical analysis\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 76}, 427--454.

\bibitem[\protect\BCAY{Newell}{Newell}{1990}]{Newell90:UTC}
Newell, A. \BBOP1990\BBCP.
\newblock {\Bem Unified Theories of Cognition}.
\newblock Harvard University Press, Cambridge, MA.

\bibitem[\protect\BCAY{Paolucci, Shehory, Sycara, Kalp,\ \BBA\ Pannu}{Paolucci
  et~al.}{1999}]{Paolucci99:Planning}
Paolucci, M., Shehory, O., Sycara, K.~P., Kalp, D., \BBA\ Pannu, A.
  \BBOP1999\BBCP.
\newblock \BBOQ A planning component for {RETSINA} agents\BBCQ\
\newblock In Wooldridge, M.\BBACOMMA\  \BBA\ Lesperance, Y.\BEDS, {\Bem Lecture
  Notes in Artificial Intelligence: Agent Theories, Architectures, and
  Languages VI (ATAL-99)}, \BPGS\ 147--161, Berlin. Springer-Verlag.

\bibitem[\protect\BCAY{Pearson, Huffman, Willis, Laird,\ \BBA\ Jones}{Pearson
  et~al.}{1993}]{Pearson93:Symbolic}
Pearson, D.~J., Huffman, S.~B., Willis, M.~B., Laird, J.~E., \BBA\ Jones, R.~M.
  \BBOP1993\BBCP.
\newblock \BBOQ A symbolic solution to intelligent real-time control\BBCQ\
\newblock {\Bem Robotics and Autonomous Systems}, {\Bem 11}, 279--291.

\bibitem[\protect\BCAY{Rao\ \BBA\ Georgeff}{Rao\ \BBA\
  Georgeff}{1991}]{Rao91:Modeling}
Rao, A.~S.\BBACOMMA\  \BBA\ Georgeff, M.~P. \BBOP1991\BBCP.
\newblock \BBOQ Modeling rational agents within a {BDI}-architecture\BBCQ\
\newblock In {\Bem Proceedings of the 2$^{nd}$ International Conference on
  Principles of Knowledge Representation and Reasoning}, \BPGS\ 471--484.

\bibitem[\protect\BCAY{Russell\ \BBA\ Norvig}{Russell\ \BBA\
  Norvig}{1995}]{Russell95:Artificial}
Russell, S.\BBACOMMA\  \BBA\ Norvig, P. \BBOP1995\BBCP.
\newblock {\Bem Artificial Intelligence: A Modern Approach}.
\newblock Prentice Hall, Upper Saddle River, NJ.

\bibitem[\protect\BCAY{Sacerdoti}{Sacerdoti}{1975}]{Sacerdoti75:Nonlinear}
Sacerdoti, E.~D. \BBOP1975\BBCP.
\newblock \BBOQ The nonlinear nature of plans\BBCQ\
\newblock In {\Bem Proceedings of the 4$^{th}$ International Joint Conference
  on Artificial Intelligence}, \BPGS\ 206--214.

\bibitem[\protect\BCAY{Schut\ \BBA\ Wooldridge}{Schut\ \BBA\
  Wooldridge}{2000}]{Schut00:Intention}
Schut, M.\BBACOMMA\  \BBA\ Wooldridge, M. \BBOP2000\BBCP.
\newblock \BBOQ Intention reconsideration in complex environments\BBCQ\
\newblock In {\Bem Proceedings of the 4$^{th}$ International Conference on
  Autonomous Agents}, \BPGS\ 209--216.

\bibitem[\protect\BCAY{Schut\ \BBA\ Wooldridge}{Schut\ \BBA\
  Wooldridge}{2001}]{Schut01:Principles}
Schut, M.\BBACOMMA\  \BBA\ Wooldridge, M. \BBOP2001\BBCP.
\newblock \BBOQ Principles of intention reconsideration\BBCQ\
\newblock In {\Bem Proceedings of the 5$^{th}$ International Conference on
  Autonomous Agents}, \BPGS\ 340--347.

\bibitem[\protect\BCAY{Shoham}{Shoham}{1993}]{Shoham93:Agent}
Shoham, Y. \BBOP1993\BBCP.
\newblock \BBOQ Agent-oriented programming\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 60\/}(1), 51--92.

\bibitem[\protect\BCAY{Simon}{Simon}{1969}]{Simon69:Sciences}
Simon, H.~A. \BBOP1969\BBCP.
\newblock {\Bem The Sciences of the Artificial}.
\newblock MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{Stallman\ \BBA\ Sussman}{Stallman\ \BBA\
  Sussman}{1977}]{Stallman77:Forward}
Stallman, R.~M.\BBACOMMA\  \BBA\ Sussman, G.~J. \BBOP1977\BBCP.
\newblock \BBOQ Forward reasoning and dependency-directed backtracking in a
  system for computer aided circuit analysis\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 9\/}(2), 135--196.

\bibitem[\protect\BCAY{Sycara, Decker, Pannu, Williamson,\ \BBA\ Zeng}{Sycara
  et~al.}{1996}]{Sycara96:Distributed}
Sycara, K., Decker, K., Pannu, A., Williamson, M., \BBA\ Zeng, D.
  \BBOP1996\BBCP.
\newblock \BBOQ Distributed intelligent agents\BBCQ\
\newblock {\Bem IEEE Expert}, {\Bem 11\/}(6), 36--46.

\bibitem[\protect\BCAY{Tambe}{Tambe}{1991}]{Tambe91:Eliminating}
Tambe, M. \BBOP1991\BBCP.
\newblock {\Bem Eliminating Combinatorics from Production Match}.
\newblock Ph.D.\ thesis, Carnegie-Mellon University.
\newblock (Also published as Technical Report CMU-CS-91-150, Computer Science
  Department, Carnegie Mellon University.).

\bibitem[\protect\BCAY{Tambe, Johnson, Jones, Koss, Laird, Rosenbloom,\ \BBA\
  Schwamb}{Tambe et~al.}{1995}]{Tambe95:Intelligent}
Tambe, M., Johnson, W.~L., Jones, R.~M., Koss, F., Laird, J.~E., Rosenbloom,
  P.~S., \BBA\ Schwamb, K. \BBOP1995\BBCP.
\newblock \BBOQ Intelligent agents for interactive simulation
  environments\BBCQ\
\newblock {\Bem AI Magazine}, {\Bem 16\/}(1), 15--39.

\bibitem[\protect\BCAY{Veloso, Pollack,\ \BBA\ Cox}{Veloso
  et~al.}{1998}]{Veloso98:Rationale-based}
Veloso, M.~M., Pollack, M.~E., \BBA\ Cox, M.~T. \BBOP1998\BBCP.
\newblock \BBOQ Rationale-based monitoring for planning in dynamic
  environments\BBCQ\
\newblock In {\Bem Proceedings of the 4$^{th}$ International Conference on
  Artificial Intelligence Planning Systems}, \BPGS\ 171--180.

\bibitem[\protect\BCAY{Wilkins, Myers, Lowrance,\ \BBA\ Wesley}{Wilkins
  et~al.}{1995}]{Wilkins94:Planning}
Wilkins, D.~E., Myers, K.~L., Lowrance, J.~D., \BBA\ Wesley, L.~P.
  \BBOP1995\BBCP.
\newblock \BBOQ Planning and reacting in uncertain and dynamic
  environments\BBCQ\
\newblock {\Bem Journal of Experimental and Theoretical Artificial
  Intelligence}, {\Bem 7\/}(1), 197--227.

\bibitem[\protect\BCAY{Wooldridge}{Wooldridge}{2000}]{Wooldridge00:Reasoning}
Wooldridge, M. \BBOP2000\BBCP.
\newblock {\Bem Reasoning about Rational Agents}.
\newblock MIT Press, Cambridge, MA.

\bibitem[\protect\BCAY{Wray}{Wray}{1998}]{Wray98:Ensuring}
Wray, R.~E. \BBOP1998\BBCP.
\newblock {\Bem Ensuring Reasoning Consistency in Hierarchical Architectures}.
\newblock Ph.D.\ thesis, University of Michigan.
\newblock Also published as University of Michigan Technical Report
  CSE-TR-379-98.

\bibitem[\protect\BCAY{Wray\ \BBA\ Laird}{Wray\ \BBA\
  Laird}{1998}]{Wray98:Maintaining}
Wray, R.~E.\BBACOMMA\  \BBA\ Laird, J. \BBOP1998\BBCP.
\newblock \BBOQ Maintaining consistency in hierarchical reasoning\BBCQ\
\newblock In {\Bem Proceedings of the 15$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 928--935.

\bibitem[\protect\BCAY{Wray, Laird,\ \BBA\ Jones}{Wray
  et~al.}{1996}]{Wray96:Compilation}
Wray, R.~E., Laird, J., \BBA\ Jones, R.~M. \BBOP1996\BBCP.
\newblock \BBOQ Compilation of non-contemporaneous constraints\BBCQ\
\newblock In {\Bem Proceedings of the 13$^{th}$ National Conference on
  Artificial Intelligence}, \BPGS\ 771--778.

\bibitem[\protect\BCAY{Wray, Laird, Nuxoll,\ \BBA\ Jones}{Wray
  et~al.}{2002}]{Wray02:Intelligent}
Wray, R.~E., Laird, J.~E., Nuxoll, A., \BBA\ Jones, R.~M. \BBOP2002\BBCP.
\newblock \BBOQ Intelligent opponents for virtual reality trainers\BBCQ\
\newblock In {\Bem Proceedings of the Interservice/Industry Training,
  Simulation and Education Conference (I/ITSEC) 2002}.

\end{thebibliography}



\end{document}














