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

\jairheading{1}{1994}{139-158}{9/93}{1/94}
\ShortHeadings{Teleo-Reactive Programs}%
{Nilsson}
\firstpageno{139}

\begin{document}

\title{Teleo-Reactive Programs for Agent Control}

\author{\name Nils J. Nilsson \email nilsson@cs.stanford.edu \\
       \addr Robotics Laboratory, Department of Computer Science \\
       Stanford University, Stanford, CA 94305 USA}

\maketitle
\begin{abstract}

A  formalism is presented for computing and organizing actions for autonomous  
agents in dynamic environments. We introduce the notion of {\it  
teleo-reactive (T-R) programs} whose execution entails the construction of  
circuitry for the continuous computation of the parameters and conditions on  
which agent action is based.  In addition to continuous feedback, T-R  
programs support parameter binding and recursion.  A primary difference  
between T-R programs and many other circuit-based systems is that the  
circuitry of T-R programs is more compact; it is constructed at run time and  
thus does not have to anticipate {\it all} the contingencies that might arise  
over all possible runs.  In addition, T-R programs are intuitive and easy to  
write and are written in a form that is compatible with automatic planning  
and learning methods.  We briefly describe some experimental applications of  
T-R programs in the control of simulated and actual mobile robots.  


\end{abstract}

\section{Introduction}

Autonomous agents, such as mobile robots, typically operate in dynamic and  
uncertain environments.  Such environments can be sensed only imperfectly,  
effects on them are not always completely predictable, and they may be  
subject to changes not under the agent's control.   Designing agents to  
operate in these environments has presented challenges to the standard   
methods of artificial intelligence,  which are based on explicit declarative  
representations and reasoning processes.  Prominent among the alternative  
approaches are the so-called {\it behavior-based}, {\it situated}, and {\it  
animat} methods \cite{Brooks,Maes,Kaelbling,Wilson}, which convert sensory  
inputs into actions in a much more direct fashion than do AI  systems based  
on representation and reasoning.  Many of these alternative approaches share  
with control theory the central notion that continuous feedback from the  
environment is a necessary component of effective action.

Perhaps it is relatively easier for control theorists than it is for computer  
scientists to deal with continuous feedback because control theorists are  
accustomed to thinking of their controlling mechanisms as composed of analog  
electrical circuits or other physical systems rather than as automata with  
discrete read-compute-write cycles.  The notions of goal-seeking  
servo-mechanisms, homeostasis, feedback, filtering, and stability---so  
essential to control in dynamic environments---were all developed with analog  
circuitry in mind. Circuits, by their nature, are continously responsive to  
their inputs.

In contrast, some of the central ideas of computer science, namely sequences,  
events, discrete actions, and subroutines, seem at odds with the notion of  
continuous feedback.  For example,  in conventional programming when one  
program calls another, the calling program is suspended until the called  
program returns control.  This feature is awkward in applications in which  
the called program might encounter unexpected environmental circumstances  
with which it was not designed to cope.  In such cases, the calling program  
can regain control only through interrupts explicitly provided by the  
programmer.

To be sure, there have been attempts to blend control theory and computer  
science.   For example, the work of Ramadge and Wonham \cite{Ramadge} on {\it  
discrete-event systems} has used the computer science notions of events,  
grammars, and discrete states to study the control of processes for which  
those ideas are appropriate.  A  book by Dean and Wellman \cite{Dean}  
focusses on the overlap between control theory and artificial intelligence.   
But there has been little effort to import fundamental control-theory ideas  
into computer science.  That is precisely what I set out to do in this paper.

I propose a computational system that works differently 

than do conventional ones.  The formalism has what I call {\it circuit  
semantics} \cite{Nilsson}; program execution produces (at least conceptually) 

electrical circuits, and it is these circuits that are 

used for control. While importing the control-theory concept of continuous  
feedback, I nevertheless 

want to retain useful ideas of computer science.  My control 

programs will have parameters that can be bound at run 

time and passed to subordinate routines. They can have 

a hierarchical organization, and they can be recursive.  In contrast with  
some of the behavior-based approaches, I  want the programs to be responsive  
to stored models of the environment as well as to their immediate sensory  
inputs.

The presentation of these ideas will be somewhat informal in line with my  
belief that formalization is best done after a certain amount of experience  
has been obtained.  Although preliminary experiments indicate that the  
formalism works quite well, more work remains to be done to establish its  
place in agent control.

\section{Teleo-Reactive Sequences}  


\subsection{Condition-Action Rules}

A teleo-reactive (T-R) sequence is an agent control program that directs the  
agent toward a goal (hence {\it teleo}) in a manner that takes into account  
changing environmental circumstances (hence {\it reactive}).  In its simplest  
form, it consists of an ordered set of production rules:

\begin{eqnarray*}
K_1 & \rightarrow & a_1 \\
K_2 & \rightarrow & a_2 \\
 & \cdots &  \\
 K_i & \rightarrow & a_i  \\
 & \cdots &  \\
  K_m & \rightarrow & a_m  

\end{eqnarray*}

The $K_i$ are conditions (on sensory inputs and on a model of the world), and  
the $a_i$ are actions (on the world or which change the model).   A T-R  
sequence is interpreted in a manner roughly similar to the way in which some  
production systems are interpreted.  The list of rules is scanned from the  
top for the first rule whose condition part is satisfied, and the  
corresponding action is executed.  T-R sequences differ substantively from  
conventional production systems, however.  T-R actions can be  {\it durative}  
rather than discrete.  A durative action is one that continues indefinitely.   
For example, a mobile robot is capable of executing the durative action {\it  
move}, which propels the robot ahead (say at constant speed) indefinitely.   
Such an action contrasts with a discrete one, such as {\it move forward one  
meter}.   In a T-R sequence, a durative action continues so long as its  
corresponding condition remains the first true condition.  When the first  
true condition changes, the action changes correspondingly. Thus, unlike  
production systems in computer science, the conditions must be {\it  
continuously} evaluated; the action associated with the {\it currently} first  
true condition is always the one being executed.  An action terminates only  
when its energizing condition ceases to be the first true condition.

Indeed, rather than thinking of T-R sequences in terms of the computer  
science idea of discrete events, it is more appropriate to think of them as  
being implemented by circuitry.  For example, the sequence above can be  
implemented by the circuit shown in figure 1.  Furthermore, we imagine that  
the conditions, $K_i$, are also being continuously computed.

\begin{figure}[htb]
\centerline{\epsffile{circuit.eps}}
\caption{Implementing a T-R Sequence in Circuitry} 

\end{figure}


The actions, $a_i$, of a T-R sequence can either be primitive actions, or  
they can be T-R sequences themselves.  Thus, programs written in this  
formalism can be hierarchical (even recursive, as we shall see later).  In  
the case of hierarchical programs, it is important to realize that {\it all}  
conditions at {\it all} levels of the hierarchy are continuously being  
evaluated; a high level sequence can redirect control through a different  
path of lower level sequences as dictated by the values of the conditions at  
the various levels.

In writing a T-R sequence, a programmer ordinarily works backward from  
whatever goal condition the sequence is being designed to achieve. The  
condition $K_1$ is taken to be the goal condition, and the corresponding  
action, $a_1$, is the null action.  The condition $K_2$ is the weakest  
condition such that when it is satisfied (and $K_1$ is not), the durative  
execution of $a_2$ will (all other things being equal) eventually achieve  
$K_1$.  And so on.   Each non-null action, $a_i$, is supposed to achieve a  
condition,  $K_j$, strictly higher in the list ($j < i$).  The conditions are  
therefore {\it regressions} \cite{Nilssonbook} of higher conditions through  
the actions that achieve those higher conditions.  


Formally, we say that a T-R sequence satisfies the {\it regression property}  
if each condition, $K_i$ ($m \geq i > 1$), is the regression of some higher  
condition in the sequence, $K_j$ ($j < i$), through the action $a_i$.  We say  
that a T-R sequence is {\it complete} if and only if $K_1 \vee \cdots \vee  
K_i \vee \cdots \vee K_m$ is a tautology.  A T-R sequence is {\it universal}  
if it satisfies the regression property and is complete. It is easy to see  
that a universal T-R sequence will always achieve its goal condition, $K_1$,  
if there are no sensing or execution errors.


Sometimes an action does not have the effect that was 

anticipated by the agent's designer (the {\it normal} effect), and sometimes  
exogenous events (separate from the actions of the agent) change 

the world in unexpected  ways.  These 

phenomena, of course, are the reason continuous feedback 

is required.  Universal T-R sequences, like universal plans \cite{Schoppers},   
are robust in the face of occasional deviations from normal execution. They  
can also exploit serendipitous effects;  it may accidentally happen that an  
action achieves a condition higher in the list of condition/action rules than  
normally expected.  Even if an action sometimes does not achieve its normal  
effect (due to occasional sensing or execution errors), nevertheless {\it  
some} action will be executed.  So long as the environment does not too often  
frustrate the achievement of the normal effects of actions, the goal  
condition of a universal T-R sequence will ultimately be achieved.   


\subsection{An Example}

The following rather simple example should make these ideas more concrete.   
Consider the simulated robots in figure 2.  Let's suppose that these robots  
can move bars around in their two-dimensional world. The robot on the right  
is holding a bar, and we want the other robot to go to and grab the bar  
marked $A$.  We presume that this robot can sense its environment and can  
evaluate conditions which tell it whether or not it is already grabbing bar  
$A$ ({\it is-grabbing}), facing toward bar $A$ ({\it facing-bar}), positioned  
with respect to bar $A$ so that it can reach and grab it ({\it  
at-bar-center}), on the perpendicular bisector of bar $A$ ({\it  
on-bar-midline}), and facing a zone on the perpendicular bisector of bar $A$  
>from which it would be appropriate to move toward bar $A$ ({\it  
facing-midline-zone}).  Let's assume also that these conditions have some  
appropriate amount of hysteresis so that hunting behavior is dampened.   
Suppose the robot is capable of executing the primitive actions {\it  
grab-bar}, {\it move}, and {\it rotate} with the obvious effects.  Execution  
of the following T-R sequence will result in the robot grabbing bar $A$:

\vskip .2in

\begin{tabular}{rcl}
{\it is-grabbing} & $\rightarrow$ & {\it nil} \\
{\it at-bar-center} $\wedge$ {\it facing-bar} & $\rightarrow$ & {\it  
grab-bar} \\
{\it on-bar-midline} $\wedge$ {\it facing-bar} & $\rightarrow$ & {\it move}  
\\
{\it on-bar-midline} & $\rightarrow$ & {\it rotate}  \\
{\it facing-midline-zone} & $\rightarrow$ & {\it move}  \\
{\it T} & $\rightarrow$ & {\it rotate}  

\end{tabular}

\vskip .2in

\begin{figure}[htb]
\centerline{\epsffile{bots.eps}}
\caption{Robots and Bars} 

\end{figure} 


Notice how each properly executed action in this sequence achieves the  
condition in the rule above it.  In this way, the actions inexorably proceed  
toward the goal. Occasional setbacks merely cause delays in achieving the  
goal so long as the actions usually\footnote{We do not choose to define {\it  
usually} more precisely here, although a probabilistic analysis could be  
given.} achieve their normal effects.

\section{Teleo-Reactive Programs} 


\subsection{Rules with Variables}

We can generalize the notion of a T-R sequence by permitting the rules to  
contain free variables that are bound when the sequence is ``called.''  We  
will call such a sequence a {\it T-R program}. Additional generality is  
obtained if we assume that the variables are not necessarily bound to  
constants but to quantities whose values are continuously being computed (as  
if by circuitry) as the environment changes.  


A simple example involving having a robot go to a designated goal location in  
two dimensions will serve to illustrate.  Suppose the goal location is given  
by the value of the variable {\it loc}.  At run time, {\it loc} will be bound  
to a pair of $X,Y$ coordinates, although we allow the binding to change  
during run time.  At any time during the process, the robot's $X,Y$ position  
is given by the value of the variable {\it position}.  (We assume that the  
robot has some kind of navigational aid that reliably and continuously  
computes the value of {\it position}.)  From the instantaneous values of {\it  
loc} and {\it position}, the robot can compute the direction that it should  
face to proceed in a straight line toward {\it loc}.  Let the value of this  
direction at any time be given by the value of the function {\it course}({\it  
position}, {\it loc}).  At any time during the process, the robot's angular  
heading is given by the value of the variable {\it heading}.  Using these  
variables, the T-R program to drive the robot to {\it loc} is:

\vskip .2in

\underline{{\it goto}({\it loc})}


\begin{tabular}{rcl}
{\it equal}({\it position}, {\it loc}) & $\rightarrow$ & {\it nil} \\
{\it equal}({\it heading}, {\it course}({\it position}, {\it loc})) &  
$\rightarrow$ & {\it move} \\
{\it T} & $\rightarrow$ & {\it rotate}  

\end{tabular}

\vskip .2in

Implementing {\it goto}({\it loc}) in circuitry is straightforward.  The  
single parameter of the program is {\it loc} whose (possibly changing) value  
is specified at run time by a user, by a higher level program, or by  
circuitry.  The other (global) parameters, {\it position} and {\it heading},   
are provided by circuitry, and we assume that the function {\it course} is  
continuously being computed by circuitry.  Given the values of all of these  
parameters, computing which action to energize is then computed by circuitry  
in the manner of figure 1. 


\subsection{Hierarchical Programs}

Our formalism allows writing hierarchical and recursive programs in which the  
actions in the rules are themselves T-R programs.  As an example, we can  
write a recursive navigation program that calls {\it goto}.  Our new  
navigation program requires some more complex sensory functions.  Imagine a  
function {\it clear-path}({\it place1}, {\it place2}) that has value $T$ if  
and only if the direct path is clear between {\it place1} and {\it place2}.   
(We assume the robot can compute this function, continuously, for {\it  
place1} = {\it position}, and {\it place2} equal to any target location.)   
Also imagine a function {\it new-point}({\it place1}, {\it place2}) that  
computes an intermediate position between {\it place1} and {\it place2}  
whenever {\it clear-path} does not have value $T$.  The value of {\it  
new-point} lies appropriately to the side of the obstacle determined to be  
between  {\it place1} and {\it place2} (so that if the robot heads toward  
{\it new-point} first and then toward {\it place2}, it can navigate around  
the obstacle).  Both {\it clear-path} and {\it new-point} are continuously  
computed by perceptual systems with which we endow the robot.  We'll name our  
new navigation program {\it amble}({\it loc}).  Here is the code:

\vskip .2in

\underline{{\it amble}({\it loc})}

\begin{tabular}{rcl}
{\it equal}({\it position}, {\it loc}) & $\rightarrow$ & {\it nil} \\
{\it clear-path}({\it position}, {\it loc}) & $\rightarrow$ & {\it goto}({\it  
loc}) \\
{\it T} & $\rightarrow$ & {\it amble}({\it new-point}({\it position}, {\it  
loc}))  

\end{tabular}

\vskip .2in

We show in figure 3 the path that a robot controlled by this program might  
take in navigating around the obstacles shown.  (The program doesn't  
necessarily compute shortest paths; we present the program  here simply as an  
illustration of recursion.)  Note that if the obstacle positions or goal  
location change during execution, these changes will be reflected in the  
values of the parameters used by the program, and program execution will  
proceed in a manner appropriate to the changes.  In particular, if a clear  
path ever becomes manifest between the robot and the goal location, the robot  
will abandon moving to any subgoals that it might have considered and begin  
moving directly to the goal.

\begin{figure}[htb]
\centerline{\epsffile{nav.eps}}
\caption{Navigating using {\it amble}} 

\end{figure} 


The continuous computation of parameters involved in T-R programs and the  
ability of high level programs to redirect control account for the great  
robustness of this formalism.

A formal syntax for T-R programs  is given in \cite{Nilsson}.  


\subsection{Implementational Issues}

The T-R formalism, with its implicit assumption of continuous computation of  
conditions and parameters, should be thought of as a fully legitimate  
``level'' in the hierarchy of program structure controlling the agent,  
regardless of how this level is implemented by levels below---just as  
computer scientists think of list processing as a level of actual operation  
even though it is implemented by more primitive logical operations below.  If  
we assume (as we do) that the pace of events in the agent's environment is  
slow compared with the amount of time taken to perform the ``continuous''  
computations required in a T-R program, then the T-R programmer is justified  
in assuming ``real'' continuous sensing as s/he writes programs (even though  
the underlying implentation may involve discrete sampling).  We recommend the  
T-R formalism only for those applications for which this assumption is  
justified.  For those applications, the T-R level shields the programmer from  
having to worry about how that level is implemented and greatly facilitates  
program construction.  


There are several different ways in which T-R programs can be interpreted  
into lower level implementations.  It is beyond the scope of this paper to do  
more than point out some obvious methods, and we leave important questions  
about the properties of these methods to subsequent research.  One method of  
implementation involves the construction of actual or simulated circuits  
according to the basic scheme of figure 1.  First, the top level  
condition-computing circuits (including circuits for computing parameters  
used in the conditions) are constructed and allowed to function.  A specific  
action, say $a_i$, is energized as a result.  If $a_i$ is primitive, it is  
turned on, keeping the circuitry in place and functioning until some other  
top-level action is energized, and so on.  If $a_i$ is a T-R sequence, the  
circuitry needed to implement it is constructed (just as was done at the top  
level), an action is selected, and so on---and all the while levels of  
circuitry above are left functioning.  As new lower level circuitry is  
constructed, any circuitry no longer functioning (that is, circuitry no  
longer ``called'' by functioning higher level circuitry) can be garbage  
collected.

There are  important questions of parameter passing and of timing in this  
process which I do not deal with here---relying on the assumption that the  
times needed to create circuitry and for the circuitry to function are  
negligible compared to the pace of events in the world.   This assumption is  
similar to the {\it synchrony hypothesis} in the {\small ESTEREL} programming  
language \cite{Berry} where it is assumed that a program's reaction   
``$\ldots $ takes no time {\it with respect to the external environment},  
which remains invariant during [the reaction].''

Although there is no reason in principle that circuitry could not be  
simulated or actually constructed (using some sort of programmable network of  
logic gates), it is also straightforward to implement a T-R program using  
more standard computational techniques.  T-R programs can be written as  
{\small LISP} {\tt cond} statements,  and durative actions can be simulated  
by iterating very short action increments.  For example, the increment for  
the {\it move} action for a simulated robot might move the robot ahead by a  
small amount. After each action increment, the top level {\small LISP} {\tt  
cond} is executed anew, and of course all of the functions and parameters  
that it contains are evaluated anew.  In our  simulations of robots moving in  
two-dimensional worlds (to be discussed below), the computations involved are  
sufficiently fast to effect a reasonable pace with apparent smooth motion.

This implementation method essentially involves sampling the environment at  
irregular intervals.  Of course, there are questions concerning how the  
computation times (and thus the sampling rate)  affect the real-time aspects  
of agent behavior which we do not address here---again assuming the sampling  
rate to be very short. 


Whatever method is used to interpret T-R programs, care must be taken not to  
conflate the T-R level with the levels below.  The programmer ought not to  
have to think about circuit simulators or sampling intervals but should  
imagine that sensing is done continuously and immediately. 


\subsection{Graphical Representations}

The {\it goto} program can be represented by a graph as well as by the list  
of rules used earlier.  The graphical representation of this program is shown  
in figure 4.  The nodes are labeled by conditions, and the arcs by actions.  
To execute the graphical version of the program, we look for the shallowest  
true node (taking the goal condition as the root) and execute the action  
labeling the arc leading out from that node.   


\begin{figure}[htb]
\centerline{\epsffile{graph.eps}}
\caption{Graphical Representation of  {\it goto}} 

\end{figure} 




In the graph of figure 4, each action normally achieves the condition at the  
head of its arc (when the condition at the tail of the arc is the shallowest  
true condition).  If there is more than one action that can achieve a  
condition, we would have a tree instead of a single-path graph.  A more   
general graph, then, is a {\it teleo-reactive tree} such as that depicted in  
figure 5.   T-R trees are executed by searching for the shallowest true node  
and executing the action labeling the arc leaving that node.  Alternatively,  
we could search for that true node judged to be on a path of least cost to  
the goal, where some appropriate heuristic measure of cost is used.  [For  
simplicity, the phrase ``shallowest true node'' will be taken to mean either  
the shallowest true node (literally) or the true node on a path of least cost  
to the goal.] Ties among several equally shallow true nodes are broken  
according to a fixed tie-breaking rule. In figure 5 we see that, in  
particular, there are at least two ways to achieve condition $K_1$.  One way  
uses action $a_2$ (when $K_2$ is the shallowest true node), and one way uses  
action $a_3$ (when $K_3$ is the shallowest true node).     


In analogy with the definitions given for T-R sequences, a T-R tree {\it  
satisfies the regression property} if every non-root node is the regression  
of its parent node through the action linking it with its parent.  A T-R tree  
is {\it complete} if the disjunction of all of its conditions is a tautology.   
A T-R tree is {\it universal} if and only if it satisfies the regression  
property and is also complete.  With a fixed tie-breaking rule, a T-R tree  
becomes a T-R sequence.  If a T-R tree is universal, then so will be the  
corresponding T-R sequence. 


One might at first object to this method for executing a T-R tree on the  
grounds that the sequence of actions that emerge will hop erratically from  
one path to another.  But if the tree satisfies the regression property, and  
if the heuristic for measuring cost to the goal is reasonable, then (however  
erratic the actions may appear to be), each successfully executed action  
brings the agent closer to the goal.



\begin{figure}[htb]
\centerline{\epsffile{tree.eps}}
\caption{A T-R Tree} 

\end{figure} 


\section{Experiments}

We have carried out several preliminary experiments with agents 

programmed in this language (using LISP {\tt cond} statements and short
action increments).  One set of experiments uses simulated robots acting 

in a two-dimensional space, called {\it Botworld} \footnote{The original 

Botworld interface, including the primitive perceptual 

functions and actions for its robots, was designed and 

implemented by Jonas Karlsson for the NeXT computer system 

\cite{Karlsson}.  Subsequently, Patrick Teo implemented 

a version that runs under X-windows on any of several 

different workstations \cite{Teo1,Teo2}.  The latter version 

allows the simulation of several robots simultaneously---each 

under the control of its own independently running process.},  of  
construction materials, structures made from 

these materials, and other robots.  The construction materials 

are bars, and the robots are to build structures by connecting 

the bars in various ways.  A robot can turn and move, 

can grab and release a suitably adjacent bar, can turn 

and move a grabbed bar, and can connect a bar to other 

bars or structures.  The robots continuously sense whether 

or not they are holding a bar, and they ``see''  in 

front of them (giving them information about the location 

of bars and structures).  Because of the existence of 

other robots which may change the world in sometimes 

unexpected ways, it is important for each robot to sense 

certain critical aspects of its environment continuously.

A typical Botworld graphical display is shown in figure 6.

\begin{figure}[htb]
\centerline{\epsffile{display1.eps}}
%\psfig{file=display.eps, width=3.0 in}
\caption{Botworld Display} 

\end{figure} 


 We have written various T-R programs that cause the robots to build  
structures of various kinds (like the triangle being constructed in figure  
6).  A robot controlled by one of these programs exhibits homeostatic  
behavior. So long as the main goal (whatever it is) is satisfied,  the robot  
is inactive.  Whenever the goal (for whatever reason) is not satisfied,  the  
robot becomes active and persists until it achieves the goal.  If another  
agent achieves part or all of the goal, the robot carries on appropriately  
>from the situation it finds itself in to complete the process.  

 

In our experiments, the conditions used in the T-R rules are conditions on a  
model of the environment that the robot constructs from its sensory system  
and maintains separately from the T-R mechanism.  The use of a model permits  
a robot  to perform its actions in response to all the sensory stimuli (past  
and present) that have been used to help construct the model.  But, if the  
T-R actions include {\it direct} changes to the model (in addition to those  
changes resulting from perceived changes to the environment), then there is a  
potential for undesirable instabilities (as with any system with positive  
feedback). (The problem of how to model the environment and how this model  
should be updated in response to sensory data is a separate major research  
problem outside the scope of the work reported here.)  


In other experiments, we have used the  Nomadic Technologies 100 series  
mobile robot.  The robot is equipped with a ring of 16 infrared sensors  and  
a ring of 16 sonar sensors.  It is controlled via a radio modem by a  
Macintosh II running Allegro Common Lisp.   We have implemented robust T-R  
programs for some simple office-environment tasks, such as wall-following and  
corridor-following \cite{Galles}.  The programs were initially developed and  
debugged using the Nomadics simulator of the actual robot; very few changes  
had to be made in porting the programs from the simulator to the robot.  In  
performing these tasks, the robot is highly reactive and persistent even in  
the face of occasional extreme sonar or infrared range errors and deliberate  
attempts to confuse it. The robot quickly adapts to sudden changes in the  
environment, such as those caused by people sharing the hallways. 



In writing T-R programs, one need only be concerned with inventing 

the appropriate predicates using the available perceptual 

functions and model database.    One does not need to worry about providing 

interrupts of lower level programs so higher level ones 

can regain control.  We have found that debugging T-R programs presents 

some challenges, though.  Since they are designed to 

be quite robust in the face of environmental uncertainty, 

they also sometimes work rather well even though they 

are not completely debugged.  These residual errors might 

not have undesirable effects until the programs are used 

in higher level programs---making the higher ones more 

difficult to debug.


\section{Other Approaches for Specifying Behavior}

There have been several formalisms proposed for prescribing 

sensory-directed, real-time activity in dynamic environments. 

Some of these are closely related to the T-R formalism 

proposed here.  In this section I point out the major 

similarities and differences between T-R programs and 

a representative, though not complete, sample of their 

closest relatives.  The other reactive formalisms are of two types, namely,  
those that sample their environments at discrete intervals (perhaps rapidly  
enough to be sufficiently reactive), and those that  create circuitry (like  
T-R programs).  The discrete-sampling systems do not abstract this activity  
into a higher level in which the environment is monitored continuously, and  
most of the circuitry-creating systems do so prior to run time (unlike T-R  
programs which create circuitry at run time).

\subsection{Discrete-Sampling Systems}

\subsubsection{Production Systems} 


As has already been mentioned, T-R programs are similar to production systems  
\cite{Waterman}. The intermediate-level actions (ILAs) used 

in the SRI robot Shakey \cite{Shakey}  were programmed using 

production rules and were very much like T-R programs.  A T-R program also  
resembles a plan represented in triangle-table 

form constructed by STRIPS \cite{Fikes}.  

Each of the conditions of a T-R sequence 

corresponds to a triangle table kernel.  In the  

PLANEX execution system for triangle tables, the 

action corresponding to the highest-numbered satisfied 

kernel is executed.  A major difference between all of these previous  
production-system style
programs  and T-R programs is that T-R programs are continuously responsive  
to the environment while ordinary production systems are not.

\subsubsection{Reactive Plans} 

 

Several researchers have adopted the approach of using 

the current situation to index into a set of pre-arranged 

action sequences   \cite{Georgeff,Schoppers,Firby}.  This set can either be  
large enough 

to cover a substantial number of the situations in which 

an agent is likely to find itself or it can cover 

all possible situations.  In the latter case, the plan 

set is said to be {\it universal}.  Unlike T-R programs, these systems
explicitly sample their environments at discrete time steps rather than  
continuously.  As  with T-R programs, time-space trade-offs must be taken 

into account when considering how many different conditions 

must be anticipated in providing reactive plans.  Ginsberg 

has noted that in several domains, the number of situations 

likely to be encountered by the agent is so intractably 

large that the agent is forced to postpone most of 

its planning until run time when  situations are actually 

encountered \cite{Ginsberg}.  (For further discussion of this point, see  
\cite{Selman}.)  T-R programs have the advantage that at least a rudimentary  
form of planning, namely parameter binding, is done at run time.  The PRS  
system \cite{Georgeff} is capable of more extensive planning at run time as  
well as reacting appropriately to its current situation.


\subsubsection{Situated Control Rules}

Drummond \cite{Drummond} introduces the notion of a 

{\it plan net}  which is a kind of Petri net \cite{Reisig} for representing  
the effects of actions (which 

can be executed in parallel).  Taking into account the 

possible interactions of actions, he then projects the 

effects of all possible actions from a present state 

up to some horizon.  These effects are represented 

in a structure called a  {\it plan projection}. The plan projection is  
analyzed to see, for each state 

in it, which states {\it possibly}  have a path to 

the goal state.  This analysis is a forward version 

of the backward analysis used by a programmer in producing 

a T-R tree.  {\it Situated control rules}  are the 

result of this analysis; they constrain the actions that 

might be taken at any state to those which will result 

in a state that still possibly has a path to the goal.  Plan nets and Petri  
nets are based on discrete events and thus are not continuously responsive to  
their environments in the way that T-R programs are.

\subsection{Circuit-Based Systems}
 

Kaelbling has proposed a formalism called GAPPS 

\cite{Kaelbling1,Kaelbling},  involving {\it goal 

reduction rules}, for implicitly describing how to 

achieve goals.  The GAPPS  programmer defines 

the activity of an agent by providing sufficient goal 

reduction rules to connect the agent's goals with the 

situations in which it might find itself.  These rules 

are then compiled into circuitry for real-time control 

of the agent.  Rosenschein and Kaelbling \cite{Rosenschein} 

call such circuitry {\it situated automata}.  


A collection of GAPPS  rules for achieving 

a goal can be thought of as an implicit specification 

of a T-R program in which the computations needed to construct 

the program are performed when the rules are compiled. 

The GAPPS programmer typically exerts less 

specific control over the agent's activity---leaving some 

of the work to the search process performed by the 

GAPPS compiler.  For example, a T-R program 

to achieve a goal, $p$ , can be implicitly specified 

by the following GAPPS  rule:

{\tt (defgoalr (ach ?p) 


\hspace{1.0in} (if ((holds ?p) (do nil))

\hspace{1.0in} ((holds (regress ?a ?p)) (do ?a)) 


\hspace{1.0in} (T ach (regress ?a ?p))  )) }

\noindent The recursion defined by this rule bottoms out 

in rules of the form: 


{\tt (defgoalr (ach $\phi$) 


\hspace{1.0in}((holds $\psi$) (do $\alpha$)) )}

\noindent where $\phi$ and $\psi$ are conditions and $\alpha$ is a specific  
action.

GAPPS compiles its rules into circuitry before run time, whereas the circuit  
implementation of a T-R program depends on parameters that are bound at run  
time. Both systems result in control that is continuously responsive to the  
environment.

In implementing a system to play a video game, Chapman 

\cite{Chapman} compiles production-like rules into digital 

circuitry for real-time control using an approach that 

he calls ``arbitration macrology.'' As in situated automata, 

the compilation process occurs prior to  run time.

Brooks has developed a behavior language, BL, \cite{Brooks1}, for writing  
reactive robot control programs 

based on his ``subsumption architecture'' \cite{Brooks}.  A similar   
language, {\small ALFA},  has been implemented by Gat \cite{Gat}. 

Programs written in these languages compile into structures 

very much like circuits.   Again, compilation occurs prior to run time.  It  
has been relatively straightforward 

to translate examples of subsumption-architecture programs 

into T-R programs.

In all of these circuit-based systems, pre-run-time 

compiling means that more circuitry must be built than 

might be needed in any given run because all possible 

contingencies must be anticipated at compile time.\footnote{Agre's ``running  
arguments'' construct \cite{Agre} is one example of a circuit-based system  
that can add circuitry at run time as needed.} But in T-R programs,  
parameters are bound at run time, and only that circuitry required for these  
specific bindings is constructed.  


\section{Future Work}

The T-R formalism might easily be augmented to embody some features that have 

not been  discussed in this paper.   Explicit reference 

to time in specifying actions might be necessary.  For 

example, we might want to make sure that some action 

$a$  is not initiated until after some time 

$t_1$ and ceases after some time 

$t_2$.  Time predicates, whose time 

terms are evaluated using an internal clock, may suffice 

for this purpose.  


Also, in some applications we may 

want to control which conditions in a T-R program are actually 

tested.  It may be, for example, that some conditions 

won't have to be checked because their truth or falsity 

can be guessed with compelling accuracy.   


Simultaneous and asynchronous execution of multiple actions can be achieved  
by allowing the right-hand side of rules to contain {\it sets} of actions.   
Each member of the set is then duratively executed asynchronously and  
independently (so long as the condition in the rule that sustains this set  
remains the highest true condition).  Of course, the programmer must decide  
under what conditions it is appropriate to call for parallel actions.  Future  
work on related formalisms might reveal ways in which parallel actions might  
{\it emerge} from the interaction of the program and its environment rather  
than having to be explicitly programmed.

Although we intend that T-R programs for agent control be written by human  
programmers, we are also interested in methods for modifying them by  
automatic planning and machine learning. We will briefly discuss some of our  
preliminary ideas on planning and learning here.

T-R trees resemble the search trees constructed by those planning systems  
that work backwards from a goal condition.  The overall goal is the root of  
the tree; any non-root node $g_i$ is the regression of its parent node, $g_j$  
through the action, $a_k$, connecting them.  This similarity  suggests that  
T-R trees can be constructed (and modified) by an automatic planning system  
capable of regressing conditions through durative actions.  Indeed  triangle  
tables \cite{Fikes}, a degenerate form of T-R tree consisting of only a  
single path, were constructed by an automatic planning system and an  
EBL-style generalizer \cite{Mitchell}. 


The reader might object that there is no reason to 

suppose that the search trees produced by an automatic 

planning process will contain nodes whose conditions are 

those that the agent is likely to encounter in its 

behavior.  A process of incremental modification, however,  should gradually  
make these constructed trees
more and more matched to the agent's environment.  If a tree for achieving a  
desired goal has no true nodes in a certain situation, 

it is as if the search process employed by an automatic 

planner had not 

yet terminated because no subgoal in the search tree was satisfied 

in the current state.  In this case, the planning system 

can be called upon to continue to search; that is, 

the existing T-R tree will be expanded until a true node is 

produced. Pruning of T-R trees can be accomplished by keeping 

statistics on how often their nodes are satisfied.  

Portions of the trees that are never or seldom used 

can be erased.  Early unpublished work by Scott Benson indicates that T-R  
programs can be effectively generated by automatic planning methods  
\cite{Benson}.

In considering learning mechanisms, we note first that T-R sequences are  
related to a class of Boolean functions that Rivest has termed {\it  
k-decision lists}  \cite{Rivest,Kohavi}.  A $k$-decision list is an ordered  
list of condition-value pairs in which each condition is a conjunction of  
Boolean variables of length at most $k$, and each value is a truth value ($T$  
or $F$).  The value of the Boolean function represented by a $k$-decision  
list is that value associated with the highest true condition.  Rivest has  
shown that such functions are polynomially PAC learnable and has presented a  
supervised learning procedure for them.  We can see that a T-R sequence whose  
conditions are limited to $k$-length conjunctions of Boolean features is a  
slight generalization of $k$-decision lists.  The only difference is that  
such a T-R sequence can have more than two different ``values'' (that is,  
actions).  We observe that such a T-R sequence (with, say, $n$ different  
actions) is also PAC learnable since its actions can be encoded with $\log_2  
n$ decision lists.  George John \cite{John} has investigated a supervised  
learning mechanism for learning T-R sequences.

Typically, the conditions used in T-R programs are conjunctions of  
propositional features of the robot's world and/or model. Because a linear  
threshold function can implement conjunctions, one is led to propose a neural  
net implementation of a T-R sequence.  The neural net implementation, in  
turn, evokes ideas about possible learning mechanisms.  Consider the T-R  
sequence:

\begin{eqnarray*}
K_1 & \rightarrow & a_1 \\
K_2 & \rightarrow & a_2 \\
 & \cdots &  \\
 K_i & \rightarrow & a_i  \\
 & \cdots &  \\
  K_m & \rightarrow & a_m  

\end{eqnarray*}

\noindent Suppose  we stipulate that the $K_i$ are linear threshold functions  
of a set of propositional features.
The $a_i$ are not all necessarily distinct; in fact we will assume that there  
are only $k \leq m$ distinct actions.  Let these be denoted by $b_1, \cdots,  
b_k$. The network structure in figure 7 implements such a T-R sequence.


\begin{figure}[htb]
\centerline{\epsffile{neuralnet.eps}}
\caption{A Neural Net that Implements a T-R Sequence} 

\end{figure} 


The propositional features tested by the conditions are grouped into an  
$n$-dimensional  binary (0,1) vector, {\bf {\sf X}} called the {\it input  
vector}.  The $m$ conditions are implemented by $m$ threshold elements having  
weighted connections to the components of the input vector.  The process of  
finding the first true condition is implemented by a layer containing  
appropriate inhibitory weights and AND units such that only one AND unit can  
ever have an output value of 1, and that unit corresponds to the first true  
condition. A unique action is associated with each condition through a layer  
of binary-valued weights and OR-unit {\it associators}.  Each AND unit is  
connected to one and only one associator by a non-zero weight.  Since only  
one AND unit can have a non-zero output, only that unit's associator  can  
have a non-zero output.  (But each associator could be connected to multiple  
AND units.)  For example, if action $b_i$ is to be associated with conditions  
$K_j$ and $K_l$, then there will be unit weights from the {\it j}-th and {\it  
l}-th AND units to the associator representing action $b_i$ and zero-valued  
weights from all other AND units to that associator.  The action selected for  
execution is the action corresponding to the single associator having the  
non-zero output.  We are investigating various learning methods suggested by  
this neural net implementation.

Work must also be done on the question of  what constitutes a {\it goal}.  I  
have assumed 

goals of achievement.  Can mechanisms be found that 

continously avoid making certain conditions true (or false) 

while attempting to achieve others?  Or suppose  priorities 

on a number of possibly mutually contradictory conditions 

are specified; what are reasonable methods for attending 

to those achievable goals having the highest priorities? 


Also, it will be interesting to ask in what sense T-R programs 

can be proved to be correct. It would seem that verification would have to  
make assumptions about 

the dynamics of the environment; some environments might 

be so malevolent that agents in them could never achieve 

their goals.  Even so, a verifier equipped with a model of the effects of  
actions could at least check to see that the regression property was  
satisfied and note any lapses.  


More work remains on methods of implementing or interpreting T-R programs and  
the real-time properties of implementations.  These properties will, of  
course, depend on the depth of the T-R program hierarchy and on the  
conditions and features that must be evaluated.

Finally, it might be worthwhile to investigate ``fuzzy'' versions of T-R  
trees.  One could imagine fuzzy  predicates that would energize actions with  
a ``strength'' that depends on the degree to which the predicates are true.   
The SRI robot, Flakey, uses a fuzzy controller \cite{Flakey}.



\section{Conclusions}

I have presented a formalism for specifying actions in 

dynamic and uncertain domains.  Since this work rests 

on ideas somewhat different than those of conventional 

computer science, I expect that considerably more analysis 

and experimentation will be required before the T-R formalism 

can be fully evaluated.  The need in robotics for control-theoretic 

ideas such as homeostasis, continuous feedback, and stability 

appears to be  sufficiently strong, however, that it 

seems appropriate for candidate formalisms  embodying 

these ideas to be put forward for consideration. 


Experiments with the language will produce a stock of 

advice about how to write T-R programs effectively.  

Already, for example,  it is apparent that a sustaining 

condition in a T-R sequence must be carefully specified 

so that it is no more restrictive than it really needs 

to be; an overly restrictive condition is likely to 

 be rendered false by the very action that it is supposed 

to sustain before that action succeeds in making a higher condition in the  
sequence true.  But, of course, overly restrictive conditions won't occur in  
T-R programs that satisfy the regression property.

To be usefully employed, T-R programs (or any programs controlling agent  
action) need to be embodied in an overall agent architecture that integrates  
perceptual processing, goal selection, action computation, environmental  
modeling, and planning and learning mechanisms.  Several architectural  
schemes have been suggested, and we will not summarize them here except to  
say that three layers of control are often delineated.  A typical example is  
the SSS architecture of Connell \cite{Connell}.  His top  
(\underline{S}ymbolic) layer does overall goal setting and sequencing, the  
middle (\underline{S}ubsumption) level selects specific actions, and the  
lower (\underline{S}ervo) level exerts standard feedback control over the  
effectors.  We believe T-R programs would most appropriately be used in the  
middle  level of such architectures.

The major limitation of T-R programs is that they involve much more  
computation than do programs that check only relevant conditions.  Most of  
the conditions computed by a T-R program in selecting an action are either  
irrelevant to the situation at hand or have values that might be accurately  
predicted (if the programmer wanted to take the trouble to do so).  We are  
essentially trading computing time for ease of programming, and our  
particular trade will only be advantageous in certain applications.  Among  
these, I think, is the mid-level control of robots and (possibly) software  
agents.


In conclusion, there are three main features embodied in the T-R formalism.   
One is {\it continuous computation} of the parameters and conditions on which  
action is based.  T-R programs allow for continuous feedback while still  
supporting parameter binding and recursion.   The second feature is the {\it  
regression} relationship between conditions in a T-R program.  Each condition  
is the regression of some condition closer to the goal through an action that  
normally achieves that closer-to-the-goal condition.  The regression property  
assures robust goal-seeking behavior.  Third, the conceptual circuitry  
controlling action is constructed at {\it run time}, and this feature permits  
programs to be universal while still being compact.  In addition, T-R  
programs are intuitive and easy to write and are written in a formalism that  
is compatible with automatic planning and learning methods.

\acks{I trace my interest in reactive, yet purposive, systems 

to my early collaborative work on triangle tables and 

ILAs.  Several former Stanford students, including Jonas Karlsson, 

Eric Ly, Rebecca Moore, and Mark Torrance, helped in the early stages of this  
work.  I also want to thank my sabbatical hosts, Prof. Rodney Brooks at MIT,  
Prof. Barbara Grosz at Harvard, and the people at the Santa Fe Institute.   
More recently,  I have benefitted from discussions with Scott Benson, George  
John, and Ron Kohavi.  I also thank the anonymous referees for their helpful  
suggestions.  This work was performed under NASA Grant NCC2-494 and NSF Grant  
IRI-9116399.}

\vskip 0.2in
\bibliographystyle{theapa}
%
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Agre}{Agre}{1989}]{Agre}
Agre, P. (1989). The Dynamic Structure of Everyday Life. Tech. rep. TR 1085,  
AI Lab., Massachusetts Institute of Technology.

\bibitem[\protect\BCAY{Benson}{Benson}{1993}]{Benson}
Benson, S. (1993). Unpublished working paper. Robotics Laboratory, Stanford  
University.

\bibitem[\protect\BCAY{Berry \& Gonthier}{Berry \& Gonthier}{1992}]{Berry}
Berry, G., \& Gonthier, G. (1992). The {\small ESTEREL}  Synchronous  
Programming Language.   {\it Science of Computer Programming}, {\it 19}, no.  
2, 87-152, November.

\bibitem[\protect\BCAY{Brooks}{Brooks}{1986}]{Brooks}
Brooks, R. (1986). A Robust Layered Control System 

for a Mobile Robot.  {\it IEEE Journal of Robotics and 

Automation}, March.

\bibitem[\protect\BCAY{Brooks}{Brooks}{1989}]{Brooks1}
Brooks, R. (1989). The Behavior Language User's Guide. Seymour Implementation  
Note 2, AI Lab., Massachusetts Institute of Technology. 


\bibitem[\protect\BCAY{Chapman}{Chapman}{1990}]{Chapman} 

Chapman, D. (1990). Vision, Instruction and Action. Tech. rep. 1204, AI Lab.,  
Massachusetts Institute of Technology.

\bibitem[\protect\BCAY{Connell}{Connell}{1993}]{Connell}
Connell, J. (1993).  SSS:  A Hybrid Architecture Applied to Robot Navigation.  
Research Report, IBM Research Division, T. J. Watson Research Center,  
Yorktown Heights, NY 10598.

\bibitem[\protect\BCAY{Dean \& Wellman}{Dean \& Wellman}{1991}]{Dean}
Dean, T., \& Wellman, M. (1991).  {\it Planning and Control}. San Francisco,  
CA: Morgan Kaufmann.

\bibitem[\protect\BCAY{Drummond}{Drummond}{1989}]{Drummond}
Drummond,  M. (1989).  Situated Control Rules.  {\it In Proc. First  
International 

Conf. on Principles of Knowledge Representation and Reasoning}.
San Francisco, CA: Morgan Kaufmann.

\bibitem[\protect\BCAY{Fikes, Hart \& Nilsson}{Fikes, Hart \&  
Nilsson}{1972}]{Fikes}
Fikes, R., Hart, P., \& Nilsson, N. (1972). Learning and 

Executing Generalized Robot Plans. {\it Artificial Intelligence}, {\it  3},  
251-288.

\bibitem[\protect\BCAY{Firby}{Firby}{1987}]{Firby}
Firby, R. (1987). An Investigation into Reactive Planning in 

Complex Domains.  {\it In Proc. AAAI-87}. San Francisco, CA: Morgan Kaufmann.

\bibitem[\protect\BCAY{Galles}{Galles}{1993}]{Galles}
Galles, D. (1993). Map Building and Following Using Teleo-Reactive Trees. In  
{\it
Intelligent Autonomous Systems: IAS-3}, Groen, F. C. A., Hirose, S. \&  
Thorpe, C. E. (Eds.), 390-398. Washington:  IOS Press.

\bibitem[\protect\BCAY{Gat}{Gat}{1991}]{Gat}
Gat, E. (1991). ALFA: A Language for Programming Reactive Robotic Control  
Systems. {\it In Proceedings 1991 IEEE Robotics and Automation Conference}.

\bibitem[\protect\BCAY{Georgeff \& Lansky}{Georgeff \&  
Lansky}{1987}]{Georgeff}
Georgeff, M., \& Lansky, A. (1989).  Reactive Reasoning and 

Planning.  {\it In Proc. AAAI-87}. San Francisco, CA: Morgan Kaufmann.

\bibitem[\protect\BCAY{Ginsberg}{Ginsberg}{1989}]{Ginsberg}
Ginsberg, M. L. (1989). Universal Planning: An (Almost) Universally 

Bad Idea.  {\it AAAI Magazine}, {\it 10}, no. 4, 

40-44, Winter.

\bibitem[\protect\BCAY{John}{John}{1993}]{John}
John, G. (1993).  `SQUISH: A Preprocessing Method for Supervised Learning of  
T-R Trees from Solution Paths, (unpublished). Robotics Laboratory, Stanford  
University.

\bibitem[\protect\BCAY{Kaelbling}{Kaelbling}{1988}]{Kaelbling1}
Kaelbling, L. P. (1988). Goals as Parallel Program Specifications. 

{\it In Proceedings AAAI-88}, 60-65. Menlo Park, CA: American 

Association for Artificial Intelligence.

\bibitem[\protect\BCAY{Kaelbling \& Rosenschein}{Kaelbling \&  
Rosenschein}{1990}]{Kaelbling}
Kaelbling, L. P., \& Rosenschein, S. J. (1990). Action and 

Planning in Embedded Agents. {\it Robotics and Autonomous 

Systems}, {\it 6}, nos. 1 and 2, 35-48, June.

\bibitem[\protect\BCAY{Karlsson}{Karlsson}{1990}]{Karlsson} 

Karlsson, J. (1990). Building a Triangle Using Action Nets.  Unpublished  
project paper. Computer Science  Dept., Stanford University. June.


\bibitem[\protect\BCAY{Kohavi \& Benson}{Kohavi &\ Benson}{1993}]{Kohavi}
Kohavi, R., \& Benson, S. (1993). Research Note on Decision Lists. {\it  
Machine Learning}, {\it 13}, 131-134.

\bibitem[\protect\BCAY{Maes}{Maes}{1989}]{Maes}
Maes, P. (1989). How to Do the Right Thing. {\it Connection Science}, {\it  
1}, no.3, 291-323.

\bibitem[\protect\BCAY{Mitchell, Keller \& Kedar-Cabelli}{Mitchell, Keller \&  
Kedar-Cabelli}{1986}]{Mitchell}
Mitchell, T. M., Keller, R. M., \& Kedar-Cabelli, S. 

T. (1986). Explanation-based Generalization:  A Unifying View.
{\it Machine Learning}, {\it 1}, 47-80.

\bibitem[\protect\BCAY{Nilsson}{Nilsson}{1980}]{Nilssonbook}
Nilsson, N. J. (1980). {\it Principles of Artificial Intelligence}. San  
Francisco, CA: Morgan Kaufmann.

\bibitem[\protect\BCAY{Nilsson}{Nilsson}{1984}]{Shakey}
Nilsson, N. (Ed.) (1984).  Shakey the Robot. Tech. Note 323, Artificial  
Intelligence Center, SRI International, Menlo Park, CA 94025.

\bibitem[\protect\BCAY{Nilsson}{Nilsson}{1992}]{Nilsson}
Nilsson, N. (1992).  Toward Agent Programs with Circuit Semantics. Tech. rep.  
STAN-CS-92-1412, Department of Computer Science, Stanford University.

\bibitem[\protect\BCAY{Ramadge \& Wonham}{Ramadge \& Wonham}{1989}]{Ramadge}
Ramadge, P. J. G., \& Wonham, W. M. (1989). The Control of Discrete Event  
Systems. {\it Proceedings of the IEEE}, {\it 77}, no. 1, 81-98, January.

\bibitem[\protect\BCAY{Reisig}{Reisig}{1985}]{Reisig}
Reisig, W. (1985). {\it Petri Nets:  An Introduction}, Springer 

Verlag.

\bibitem[\protect\BCAY{Rivest}{Rivest}{1987}]{Rivest}
Rivest, R. L. (1987). Learning Decision Lists.  {\it Machine Learning}, {\it  
2},  229-246.

\bibitem[\protect\BCAY{Rosenschein \& Kaelbling}{Rosenschein \&  
Kaelbling}{1986}]{Rosenschein} 

Rosenschein, S. J. \& Kaelbling, L.P. (1986). The Synthesis 

of Machines with Provable Epistemic Properties. {\it In Proceedings of the  
1986 Conference 

on Theoretical Aspects of Reasoning about Knowledge}. Halpern, J. (Ed.),   
83-98, San Francisco, CA: Morgan Kaufmann. (Updated version: Technical 

Note 412, Artificial Intelligence Center, SRI International, 

Menlo Park, CA.)

\bibitem[\protect\BCAY{Saffiotti, Ruspini \& Konolige}{Saffiotti, Ruspini \&  
Konolige}{1993}]{Flakey}
Saffiotti, A., Ruspini, E., \& Konolige, K. (1993). Integrating Reactivity  
and Goal-directedness in a Fuzzy Controller. {\it In Proc. of the 2nd  
Fuzzy-IEEE Conference}, San Francisco, CA.


\bibitem[\protect\BCAY{Schoppers}{Schoppers}{1987}]{Schoppers}
Schoppers, M. J. (1987). Universal Plans for Reactive Robots in Unpredictable  
Domains. {\it In Proceedings of IJCAI-87}. San Francisco, CA: Morgan  
Kaufmann.

\bibitem[\protect\BCAY{Selman}{Selman}{1993}]{Selman}
Selman, B. (1993). Near-Optimal Plans, Tractability, and Reactivity. Tech.  
rep., AI Dept., AT\&T Bell Laboratories.

\bibitem[\protect\BCAY{Teo}{Teo}{1991}]{Teo1}
Teo, P. C-S. (1991). ``Botworld,'' (unpublished).  Robotics Laboratory,  
Computer Science Dept., Stanford University, December.

\bibitem[\protect\BCAY{Teo}{Teo}{1992}]{Teo2}
Teo, P. C-S. (1992). Botworld Structures, (unpublished).  Robotics  
Laboratory, Computer Science Dept., Stanford University, June.

\bibitem[\protect\BCAY{Waterman \& Hayes-Roth}{Waterman \&  
Hayes-Roth}{1978}]{Waterman}
Waterman, D. A. \& Hayes-Roth, F. (1978). An Overview of 

Pattern-Directed Inference Systems. In {\it Pattern-Directed 

Inference Systems}, Waterman, D. A. \& Hayes-Roth, 

F. (Eds.), 3-22. New York:Academic Press.

\bibitem[\protect\BCAY{Wilson}{Wilson}{1991}]{Wilson}
Wilson, S. (1991). The Animat Path to AI. In  {\it From Animals to Animats;  
Proceedings of the First International Conference on the Simulation of  
Adaptive Behavior}, Meyer, J. A., \& Wilson, S. (Eds.). Cambridge, MA: The  
MIT Press/Bradford Books.


\end{thebibliography} 

 \end{document}
 




