Received: from SOUTH-STATION-ANNEX.MIT.EDU by po8.MIT.EDU (5.61/4.7) id AA22177; Sun, 15 Feb 98 19:47:53 EST
Received: from ALBACORE.MIT.EDU by MIT.EDU with SMTP
	id AA04720; Sun, 15 Feb 98 19:47:26 EST
Received: (from jleonard@localhost) by albacore.mit.edu (950413.SGI.8.6.12/950213.SGI.AUTOCF) id TAA07746; Sun, 15 Feb 1998 19:47:53 -0800
Date: Sun, 15 Feb 1998 19:47:53 -0800
Message-Id: <199802160347.TAA07746@albacore.mit.edu>
From: John Leonard <jleonard@albacore.mit.edu>
To: abennett@MIT.EDU
Subject: article.tex (newer version)



Drew,
Here's a newer version.

\documentclass[11pt]{article}
%% Would really like to send this paper to AIJ
%% jl 2/6/98

%%% Nov20_03 is mission 1 (first result)
%%% May22_01 is mission 2 (eastern side)
%%% Jan29_24 is mission 3 (heading and speed biases and external
%%% current)

%%% Jun12_04 is mission 4 (LUT)
%%% Jun13_01 is mission 5 (cost function 1:1)
%%% Jun13_05 is mission 6 cost function 50:1 (50:1 heading to distance)
%%% Jun13_06 is mission 7 cost function 50:1 (1:50 heading to distance)

\usepackage{tgrind}
\usepackage{psfig}
\usepackage{subfigure}
\usepackage{rotating}

\def\i{\item}
\def\bc{\begin{center}}         \def\ec{\end{center}}
\def\bi{\begin{itemize}}        \def\ei{\end{itemize}}
\def\bn{\begin{enumerate}}      \def\en{\end{enumerate}}
\def\btr{\begin{tabular}}       \def\etr{\end{tabular}}
\def\btb{\begin{tabbing}}       \def\etb{\end{tabbing}}

\newcommand{\upline}{\vspace*{-\baselineskip}}
\newcommand{\up}{\vspace*{-6pt}}
\newcommand{\downline}{\vspace*{\baselineskip}}
\newcommand{\down}{\vspace*{\baselineskip}}

%% \renewcommand{\psfig}{}

\oddsidemargin 0.2cm
\evensidemargin 0cm
\textwidth 16.59cm
\topmargin -1.25cm
\textheight 22.94cm


%% Change title to adaptive contour following?

\title{A behavior-based approach to adaptive feature mapping with
autonomous underwater vehicles} 
\author{Andrew A. Bennett\\Walt Disney Imagineering\\
P.O. Box 1403\\
Cambridge, MA 02142-0010
 \and John
J. Leonard\\ 
Dept.\ of Ocean Engineering \\
Massachusetts Institute of Technology\\
Cambridge, MA 02139-4307\\
} \date{}
\markright{\fbox{DRAFT: \today}}

\begin{document}
\maketitle
\pagestyle{myheadings}
\thispagestyle{myheadings}

\begin{abstract}
This paper presents a technique for adaptively tracking bathymetric
contours using an autonomous underwater vehicle (AUV) equipped with a
point sensor.  An adaptive feature mapping behavior was developed to
address the problem of how to locate and map features of unknown
extent in an environment where \emph{a priori} information is
unavailable. This behavior was implemented as part of the Layered
Control architecture used by the AUV \emph{Odyssey II}.  The new
adaptive feature mapping behavior builds on previous work in layered
control by incorporating planning and mapping capabilities which allow
the vehicle to alter its trajectory on-line in response to sensor data
to successfully track contour features.  New waypoints are selected by
evaluating the expected utility of visiting a given location balanced
against the expected cost of visiting a particular cell.  The
technique has been developed assuming sensor input in the form of a
single, narrow-beam altimeter sensor attached to a non-holonomic,
dynamically controlled survey-class AUV such as the \emph{Odyssey II}.
Testing has been conducted in a simulation of the Charles River basin
constructed from real bathymetry data, using the seven meter contour
line of a prominent trench in the river as the target feature.  The
adaptive contour following behavior is demonstrated to track the
contour despite navigation error and environmental disturbances,
supplying a capability to autonomously detect and follow distinctive
bathymetric features using a point sensor.  The behavior provides a
foundation for future research in tracking of dynamic water-column
features and for concurrent mapping and localization in natural
terrain using a point sensor.
\end{abstract}


{\bf Keywords}: Autonomus underwater vehicles, intelligent control,
navigation, adaptive sampling.

\vspace{0.25in}

\section{Introduction}

This paper presents a behavior-based approach to the problem of
adaptively mapping contour features using a survey-class AUV such as
the Odyssey II~\cite{bellingham94} equipped with a single
downward-looking sonar.  The approach was developed to address the
challenge of how to use a survey class AUV to map adaptively
distinctive bathymetric features such as trenches.  A prominent trench
in the Charles River was used as the basis for a simulation study of
how to perform adaptive feature mapping using a behavior-based
approach to high-level control.

Adaptive contour following is one example of a larger class of
problems known as feature relative navigation which require the AUV to
determine its trajectory on-line in response to sensor data.  Feature
relative navigation tasks are difficult because they require the
integration of techniques from intelligent control, navigation, and
mapping in real-time to enable the AUV to perform its mission safely
and efficiently.  Behavior-based control approaches are attractive for
feature relative navigation tasks because of their low computational
requirements and potential for real-time response in dynamic
environments. However, the types of missions performed with AUVs to
date have been restricted to reactive tasks such as bottom following,
homing, and obstacle avoidance.  By considering the task of adaptive
feature mapping, in this paper we aim to apply a behavior-based
control approach to a more complex type of mission than has been
attempted previously.

The desirable aspects for adaptively mapping a feature in a
pre-designated area such as the Charles River are:
\begin{itemize}
\item quickly finding instances of a given feature type,
\item adequately sampling the feature once it is found, and
\item efficiently locating all instances of a feature of a given size
within the assigned region.
\end{itemize}
The technique developed should retain these attributes when there is 
navigation uncertainty and external disturbances such as currents.

The structure of this paper is as follows.  Section~\ref{back-sec}
motivates the problem we are considering from the standpoint of
potential applications.  Section~\ref{review-sec} provides background
for the problem in terms of previous research in high-level control of
AUVs.  Section~\ref{prob-sec} defines the problem formally and states
the assumptions used in our simulation study.
Section~\ref{method-sec} describes our new technique for adaptive
contour following and Section~\ref{results-sec} presents simulation
results that demonstrate the success of the method both with and
without navigation error and external currents.  Finally,
Section~\ref{future-sec} presents our conclusions and discusses future
research.  An Appendix gives the parameter values for the behavior
that were used in the experiments.

\section{Motivation}\label{back-sec}

There is great interest in the development of information processing
and intelligent control techniques that can enable an autonomous
underwater vehicle (AUV) to navigate relative to features of interest
in the ocean environment and to maximize the amount of sensor data
obtained from these features.  Three scenarios in which the capability
to navigate relative to \emph{contour} features are: 1) adaptive
mapping of a region, 2) adaptive mapping of a dynamic feature, and 3)
geophysical navigation using natural terrain features.

Automated survey of ice keels in the Arctic presents one instance of
the problem of adaptive region mapping.  Recently oil companies have
expressed interest in drilling for oil in the Sea of Okhotsk off of
the eastern coast of Russia~\cite{unep97}.  Although the sea is prone
to thick seasonal ice cover, the technology now exists to install
bottom-mounted well heads, which means that expensive ice-proof
off-shore production platforms are no longer necessary.  However, the
Sea of Okhotsk is not only prone to winter ice but also portions of it
are relatively shallow.  Consequently, ice keels carve trenches into
the seabed each winter as the pack ice moves about.  These ice keels
could easily cut oil pipelines laid on the seabed, resulting in both a
huge financial loss and an ecological disaster.  It would be desirable
for AUVs to survey the extent and distribution of both the ice keels
and the trenches dug out by ice keels in the area to provide
information on how deeply new oil pipelines should be buried. 
 
To perform this mission, an AUV should be capable of locating and
mapping the extent, depth, and distribution of ice keels and trenches
so that researchers can develop an understanding of how the ice keels
move and affect the seabed over time --- thereby allowing proper
placement of oil pipelines.  This requires repeated under-ice missions
to locate and identify all trenches in a region.  Because of the
nature of the problem, there is no \emph{a priori} map for the vehicle
to work with and only the most basic environmental information
(e.g. average depth, overall slope, etc.).

The Haro Strait experiment, performed in July, 1996, presents a good
motivating scenario for adaptive mapping of dynamic ocean
features~\cite{schmidt96}.  The objective of this type of mission is
to locate and examine a feature whose dynamic nature makes its shape,
extent, and location impossible to predict in detail.  Adapting the
vehicle path to follow such a feature allows us to both map a feature
whose \emph{a priori} location is unknown and to follow a feature as
it moves through or with the water column.  Examples of this type of
mission are mapping of mixing zones, rapid-response situations,
locating fronts (thermal, salinity, turbidity, etc.) and tracking
dynamic features such as upwellings, thermal plumes, or eddies.

The third application, geophysical navigation using natural terrain
features, is a technique whereby a vehicle matches sensor measurements
to an {\em a priori} map to determine its position.  Kamgar-Parsi has
presented techniques for matching observed terrain contours with an
{\em a priori} map~\cite{kamgar-parsi89}.  To enable vehicles equipped
with a single altimeter to navigate in this way, the vehicle must be
able to follow a contour line on the bottom to obtain enough
measurements from different parts of the contour to be useful for
matching to the map. 

In each of these three scenarios, it it desirable for the AUV to
detect and track contour features in the data measured by the vehicle
sensors.  These tasks are beyond the current state-of-the-art of what
has been demonstrated to date in high-level control of AUVs.

\section{Related Research}\label{review-sec}

%% We consider the problem of adaptive feature mapping using a
%% behavior-based approach to high-level control of AUVs.  

High-level control architecture design has been realized as an
important problem both in autonomous underwater vehicle research and
in the fields of mobile robotics and AI in general~\cite{mataric97}.
Three main schools of thought have emerged: (1) planning-based
systems, (2) behavior-based systems, and (3) hybrid systems, which
incorporate characteristics of the first two categories.

Planning based systems typically rely on a central world model to
verify sensor information and generate actions~\cite{chatila85a,
giralt84a, laird90, moravec89a}.  The information in the central model
is then used by a \emph{planner} to determine a course of action
necessary to satisfy the vehicle's goals.  Planners can be quite
powerful if sufficient time and information is available.  Their chief
drawback is the inability to handle rapidly changing environments in a
timely fashion~\cite{brooks90,brooks91a}.

Behavior-based systems embed the robot's control strategy in a set of
preprogrammed condition-reaction pairs, or ``reflexes.''  Reactive
systems are characterized by no internal models, minimal state, and
simple programming.  They operate over a limited time horizon.  They
are favored for their speed and have proven effective when the number
of behaviors is low and the problem can be completely specified at
design-time.  They are limited during execution by their inability to
store information dynamically.

A criticism of behavior-based systems is that because the specific
meaning of what a behavior is has not been precisely pinned down,
behavior-based systems lack a rigorous set of definitions and an
associated systems analysis.  Further, this lack of rigorous
definitions makes it difficult to perform direct comparisons of the
performance of different systems.  However, it is this same lack of
rigid definitions that has allowed so many ideas in so many forms and
implementations to be attempted.

In spite of the criticism, there are elements that all behavior-based
systems have in common: 1) There is no centralized representation
operated on by one controlling reasoner; representations are instead
distributed among many different behaviors or competencies and are
maintained and updated in a distributed fashion.  2) All
behavior-based systems contain multiple separate behaviors, each of
which functions independently of the others.  3) The resulting vehicle
actions are determined externally to the behaviors, either through a
prioritization scheme~\cite{bellingham90c}, a voting
scheme~\cite{payton90}, or spreading of activation~\cite{maes91}.

Hybrid systems attempt to find a compromise between these two
extremes.  The most promising approach has been to employ a reactive
low-level system with a planner-based high-level decision maker.  This
has resulted in a large an diverse body of work, ranging from
internalized plans~\cite{payton90} to contingency
plans~\cite{connell92} and many more.  A common division of labor is
to utilize low-level competencies to handle immediate vehicle safety
while the high-level planner determines the optimal action sequence to
satisfy the mission goals~\cite{bennett93}.

The rest of this section reviews the historical development of
behavior-based AUV control. Good examples of the other two types of
system are presented by the Draper Laboratory's planning-based system
developed for the DARPA AMMT project~\cite{regan96}, and the Naval
Postgraduate School's Tri-level Control Architecture developed for the
Pheonix AUV~\cite{healey96}.

\subsection{The Subsumption Architecture}

Brooks' seminar work in development of the \emph{subsumption
architecture} at the MIT AI lab during the 1980s came as a reaction to
the ``traditional'' high-level control architectures which were then
prevalent~\cite{brooks85}.  In traditional high-level control, a task
is broken into \emph{functional units}, each executed in turn after
the other (Figure \ref{fig:BBAIvsTrad}a). This form of decomposition
assumes that each task is composed of sub-tasks which in turn may or
may not be further decomposed.  The execution of these tasks is
\emph{sequential}, i.e. the next function using as its input the
output of the previous function.  In the subsumption architecture,
vehicle functionality is viewed as a series of \emph{concurrent}
task-achieving behaviors (see Figure \ref{fig:BBAIvsTrad}b).  These
behaviors are each achieved separately and then tied together to form
the robot control system.  The advantages of this system are: (1)
concurrent execution of multiple behaviors, (2) multiple goals
(e.g. trying to achieve a point in space while avoiding obstacles),
(3) expandability -- new behaviors can be added onto existing layers,
and (4) robustness -- older, underlying layers maintain core
competency beneath overlaying behaviors.

In the development of a behavior-based control system, one first
creates a complete root control system, referred to as the
\emph{zeroth} layer, or level 0 competence.  This is thoroughly
debugged and tested.  Once proven, we add another layer of competence
onto this, called the first level competence.  Level 1 can monitor the
same input data as level 0 and can also monitor its output (see Figure
\ref{fig:layer_diagram}).  These layers are each finite state machines
and execute continuously, issuing their own instructions to the
actuators while at the same time inhibiting the output of those layers
below them if necessary.  The complexity of the overall behavior of
the robot emerges from the interaction of these layers.

In practice, this form of control quickly revealed fundamental
problems associated with \emph{scaling} and \emph{situatedness}.  The
problem of scaling is a result of the number of interconnections,
which in the worst case can increase as the factorial of the number of
behaviors implemented on the vehicle.  The resulting complexity of
interactions was cited as a virtue of behavior based systems, since
the goal was emergent intelligence and complexity.  However, this same
complexity was considered a shortcoming by the autonomous vehicle
community for essentially the same reason: if all of the interactions
could not be adequately modeled and predicted, the vehicle's behavior
in a given situation also could not be modeled and predicted.  This
meant that a vehicle programmed with a purely subsumptive architecture
could not be completely trusted to perform as predicted when
confronted with a complex task.

The second shortcoming is commonly referred to as
\emph{situatedness}~\cite{bennett93}.  This is also a natural side
effect of a subsumptive system.  Since each behavior is a finite state
machine, running concurrently with all the others, the current
behavior suite is the only state the vehicle as a whole will function
in.  Such systems are also referred to as \emph{non-taskable} systems.
That is, the vehicle cannot be assigned a new task without
reprogramming the whole system.  In spite of these limitations,
behavior-based control remains attractive because of the potential
benefits of fast reaction times and computational
simplicity~\cite{bellingham90c, bennett93, mataric97}.

\subsection{Layered Control}

Bellingham and Consi proposed the concept of \emph{layered control} as
an adaptation of the subsumption architecture suitable for high-level
control of AUVs.  Three primary contributions were made: (1) a
methodology for keeping layered control simple~\cite{bellingham90c},
(2) an extension to accommodate mission planning~\cite{bellingham90},
and (3) a validation of the approach via implementation on numerous
AUV platforms~\cite{bellingham94}.  The approach grew out of an effort
to address the problem of scaling.  The principal difference between
layered control and the subsumption architecture is the restriction of
the interaction between layers.  In a layered control system, each
layer is assigned a relative priority number and executes without
interacting with any other.  Conflicting outputs are then resolved
using a fixed prioritization scheme, with higher priority layers
overriding lower ones.  In general, mission safety functions (e.g.
obstacle avoidance) have the highest priority.  These
non-interconnected layers are referred to as \emph{behaviors}; the
primary difference is that layers can interconnect, while behaviors
cannot.

In the subsumption architecture, each layer can look into and
influence those beneath it.  Thus, if a newly added layer needs
processed sensor information it can obtain that information from a
lower layer via the interconnection of layers.  Because a layered
control system expressly prohibits interaction between behaviors,
there is now the potential for redundant processing among behaviors
when each behavior needs to process the same sensor information in the
same way.  To prevent this, sensor processing is pushed ``outside'' of
the layered control system and pre-processed for all of the behaviors.
Sensor data is then made available to all behaviors via a central data
structure.  Although this violates the premise of parallel execution
and speed, sensor data processing is a critical prerequisite to all
behaviors, and therefore is not truly an additional burden.  In this
way, many of the problems of interconnections and scaling found with a
purely subsumptive system are avoided.

To extend layered control to handle multi-phase missions, state
configured layered control (SCLC)~\cite{bellingham90b} was
proposed. In SCLC, multiple sets of simple behaviors chosen from a
central behavior library.  Different sets are executed at each phase
as the mission unfolds.  The advantage of this approach is the
reduction in the number of active behaviors at any time.  This
reduces, but does not eliminate, the interaction issues found in any
behavior-based intelligent control system.

\subsection{Adaptive Sampling}

The problem of adaptive sampling with AUVs is closely related to the
high-level control problem.  The goal is to control the trajectory of
the AUV to obtain a sampling pattern that will most efficiently
characterize a given phenomenon.  There are two primary forms of
adaptive sampling: \emph{field based} and \emph{feature based}.  A
field based approach attempts to determine the best sampling interval
or locations to adequately characterize a distributed phenomenon.  The
sampling interval, speed, and locations depend upon the spatial \&
temporal capabilities (i.e. maneuvering, speed) and the resolution \&
dynamic characteristics of the sensors employed.

Bellingham \emph{et al.}~\cite{bellingham96,Willcox96} examined the
problem of adaptive sampling of a distributed oceanic phenomenon using
the survey-class AUV \emph{Odyssey II}.  The best path was determined
based upon the presumed spatial frequency of the phenomenon, its rate
of evolution and the speed \& endurance of the AUV.  The resulting
path was designed to be the optimum sampling strategy needed to obtain
the best possible distribution of statistical information about a
region, given the duration and speed restrictions imposed by the
vehicle.  Cooperative strategies were also examined; i.e. the spatial
and temporal information obtained using coordinated fleets of AUVs.

Singh~\cite{singh95} and Burien~\cite{burien96a,burien96} examined the
issue of field based adaptive sampling from the perspective of
gradient following in an effort to locate the local maxima or minima
in a given search area.  The approach proved effective in two
different scenarios using a sonar in Herring Pond, near Falmouth,
Massachusetts (Singh), and in simulation using bathymetric and thermal
data (Burien).  Their technique is designed to locate the local maxima
or minima and not map a distributed feature.

A feature based approach is designed to locate one or more features in
the world and map their number and/or extent.  In this case, the
vehicle responds to the presence or absence of a feature.  It is
designed to maximize the vehicle's ``time on target'' or ratio of the
time spent examining features vs. total mission time.

Information theoretic approaches such as in Stewart~\cite{stewart88},
Singh~\cite{singh95a} and Aramaki~\cite{aramaki95} used a sonar as the
sensor and treated the entire world as one feature.  Portions of this
``feature'' were then imaged until either the change in the rate of
new information dropped below a given threshold (Singh), or confidence
in the value of a given voxel (Stewart) or pixel (Aramaki) exceeded a
given threshold.


%% Proponents of different types of control architecture  
%% add ``lines and boxes'' quote ?
 
\section{Problem Statement}\label{prob-sec}
Motivated in particular by the underice mapping scenario discussed
above in Section~\ref{back-sec}, we address the challenge of how to
use the AUV Odyssey II equipped with just a sonar altimeter to map
adaptively the trench in the Charles River in Boston, MA, as shown in
Figure~\ref{fig:charles_7m_contour}.  A bathymetric feature like the
Charles River trench would enable repeatable tests of different
adaptive sensing strategies in the future.  Dynamic features such as
ice keels and ocean fronts are very interesting scientifically, but
would present a greater challenge for comparison of different FRN
techniques.


%% Now start with the mathematical problem statement.  
%% \subsection{Assumptions}

A survey class vehicle, such as the AUV \emph{Odyssey
II}~\cite{bellingham94}, is assumed to be the type of AUV employed to
map the feature.  The choice of vehicle class has a direct impact on
the problem approach due to the nature of dynamic control of
survey-class AUVs (i.e. minimum speed at which the vehicle is
controllable and a finite turning radius). The results in this paper
were obtained using the full vehicle software and dynamic simulation
environment for the Odyssey II developed by
Bellingham~\cite{bellingham94}, and hence the software developed in
the simulation study would translate directly to the vehicle for
future field testing.

A sonar altimeter (rather than a swath-type sensor) is chosen as the
primary sensor because it is both commonly available and because it
can be viewed as a point sensor, thereby avoiding a solution which is
unique to the peculiarities of the sonar sensing modality.  It is
desirable to develop FRN techniques which can be generalized in the
future to apply to conductivity, temperature, and depth (CTD)
measurements of dynamic ocean features.  

The methodology used is based on a simulated ocean environment which
in turn is based on real data wherever possible.  The simulator
employed has been used by the MIT Autonomous Underwater Vehicles
Laboratory, and has been validated by several years of field
tests~\cite{bellingham94}.  The sensor model is based on the
characteristics of the Tritech Model ST500 conical beam sonar
transducer with simulated noise modeled after that found in data
obtained in tests with the AUV \emph{Odyssey IIb} in the Charles
River.  The bathymetry of the test area is derived from sonar
altimeter data collected in the Charles River basin during the summer
of 1993.  

%% \subsection{Formal problem statement}

Incorporating these assumptions, the problem can be summarized as
follows. The AUV moves in the horizontal plane at constant depth $z$
and has position and heading ${\bf x}(k) = (x(k), y(k), \psi(k))$,
where $k$ is the current step of discrete time.  The pitch and roll
$\theta$ and $\phi$ of the vehicle are assumed to be maintain at zero
degrees by the vehicle's dynamic controller.  The vehicle is
controlled by specifying its forward speed $u(k)$ and yaw rate $r(k)$.
The speed and yaw rate are constrained by: $0 \leq u_{min} \leq
u_{max}$ and $|r(k)| \leq r_{max}$.  A navigation system is available
that produces position estimates for the vehicle
$(\hat{x}(k),\hat{y}(k))$ with known error characteristics and an
altimeter sensor that produces measurements of the height of the
vehicle off the bottom $Z(k) = f(x,y) - z$, where $f(x,y)$ is a
single-valued height function that represents the bottom bathymetry.
The vehicle is assumed to have a ``waypoint controller'' that steers
the vehicle through a sequence of desired waypoints ${\bf x}_i$ for
$i=1 \ldots n$.  The problem is to process the altimeter and
navigation sensor measurements to choose the sequence of waypoints
that the vehicle follow to accomplish the objectives of detecting and
tracking instances of a desired contour line consisting of all
locations $\{ (x_i, y_i)\}$ such that $f(x_i, y_i) = z_c$, where $z(k)
= z_c$.


\section{Approach}\label{method-sec}

To solve this problem, we developed a new behavior for adaptive
feature mapping which represents an extension of layered control that
incorporates planning and mapping capabilities within an ``adaptive
behavior''.  Before implementing the approach, which is described in
more detail below, we first attempted to solve the problem above with
two less complex approaches: a simple reactive technique, aligned with
Brooks' philosophy of behavior design, and a state-configured layered
control approach, which attempted to decompose adaptive feature
mapping into a multi-phase mission.  Both attempts were unsuccessful,
and are described in more detail in~\cite{bennett97}.

%% \subsection{Implementation 1: A Simple Reactive System}

The simple reactive system consisted of two behaviors, ``follow'' and
``turn''.  The follow behavior held a steady vehicle heading as long
as a feature was being detected, while the turn behavior reversed
course, alternating to the left and to the right, whenever a feature
was passed. The problem with this approach was that it was very
unreliable.  While it worked properly sometimes, more often than not
it would simply get lost. Figures~\ref{fig:mar05_01}
and~\ref{fig:may14_04} show two representative runs.

A key problem with the first implementation was that once the feature
was lost, the vehicle would simply wander off in a random direction.
The simple reactive behavior approach had no memory.  It found a
feature through random motion, and it tried to track a feature with a
very simple strategy.  To improve the vehicle performance, the second
implementation, adopted a state-configured layered control approach to
decompose the mission into multiple phases.  A spiral search phase was
added to complement the detect and follow phases of the simple
reactive system.  The result (illustrated in
Figure~\ref{fig:simmay29_01}) was that the vehicle did much better in
not losing a feature once it found it, but the actual trajectory that
resulted was random and inefficient.

Based on the experience with these implmentations, a new strategy was
adopted, resulting in our third implementation, which we call the {\tt
trench\_finder}, We chose to keep the layered control structure, to
retain its attractive characteristics, but to expand greatly the
capabilities of an individual behavior.  In our case, the additional
``intelligence'' is not at some higher level but is instead embedded
in the low-level behaviors in a restricted fashion.  Specifically,
simple mapping and planning capabilities are added to the behavior.
Our goal is to provide notions of history (what have I seen before?)
and prediction (what should I expect to see next?).  The result is a
large increase in vehicle capability and functionality through an
incremental increase in the complexity of the intelligent control
system.  We refer to the new behavior as an ``adaptive behavior'', and
feel the development of adaptive behaviors for other types of missions
provides one way forward to extend layered control to achieve other
high-level control capabilities that previously might not be
considered possible with a behavior-based control approach.

In a pure state configured layered control system, the states are
pre-defined before the mission.  This can lead to two key problems: 1)
contingency planning and 2) adaptability.  Mataric observes that the
solution to the former is to develop a system whereby ``reactive,
constant-time run-time strategies can be derived from a planner, by
computing all possible plans off-line beforehand~\cite{mataric97}.''
If the planner is sufficiently thorough, then all possible states can
be anticipated, and therefore the necessary state will be available
when required.  This, however, leaves the problem of adaptability.
The vehicle mission shown in Figure \ref{fig:simmay29_01} has
sufficient states to address the basic problem at hand, i.e. mapping
the trench, but it is dependent on the random changes in direction
brought about by the behavior's reactive nature to move the vehicle
into unmapped parts of the feature.  This is inefficient and prone to
possible failure if conditions are such that portions of the feature
are never reached.  A superior method would be for the behavior of the
vehicle to \emph{adapt} to the feature to insure that all of it is
adequately mapped.

A sufficiently complex state table may be capable of performing this
mission, but it would have to be tailored to each feature and, given
the assumption that there is no \emph{a priori} information available,
would not be feasible under the constraints we have placed upon the
survey.  What is required is a behavior which does not merely change
its output according to some pre-determined mapping function, but
instead changes itself in response to current and past sensory
information, i.e. a behavior which learns and adapts to the
environment.  This learning may take place within the behavior or as a
separate function.  The output is then the result of \emph{planning}
on the part of the behavior, based upon the current information and
any predictions the planner may make.

To accomplish this in the framework of the existing AUV layered
control system, the concept of an \emph{adaptive behavior} was
developed.  Adaptive behaviors are behaviors which are capable of
adapting their output to the current environment based on information
obtained during the course of a mission.  Unlike a more traditional
behavior, an adaptive behavior has (or has access to) memory, a
capacity for planning and can contain multiple states internally (see
Figure \ref{fig:int_beh_cartoon}).  This capacity allows the behavior
to alter its output in response to the current situation while taking
mission history into account.

Adaptive behaviors are also, by design, encapsulated.  This means
that their internal states and interactions are known in advance of
their use, making them predictable in the field.  By doing this, a
user can employ sophisticated ``canned'' vehicle competencies  -- with the
knowledge of how they will function -- without the need to model multiple
behavior interactions in the field.  In keeping with the layered
control paradigm, the adaptive behavior is assigned a priority
lower (less important) than any safety behaviors that may be employed
during the mission (e.g. {\tt power\_monitor}, {\tt
obstacle\_avoidance}, etc.).  The output is restricted to vehicle
heading, depth and speed, while inputs are restricted to a few
mission-specific global parameters.

As mentioned above, the memory of the adaptive behavior may or may
not be internal to the behavior itself (depending on whether we wish
to share the information with other behaviors).  In either case, for
the purposes of adaptive feature mapping we will employ
mission-specific memory in the form of a map of the exploration area
which is constructed and maintained during the course of the mission.

\subsection{Mapping}

To properly sample a feature, we need to insure that we explore as
much of the feature as possible in the time allotted.  As shown in the
previous section, while a purely reactive system can be made robust,
it lacks the ability to deliberately search out unknown regions.  To
do this requires some form of memory (``I have been here before'').

To this end a \emph{mapper} was designed and implemented.  The
function of the mapper is to construct and maintain a data structure
which represents the history of vehicle activities related to the
feature-relative search aspects of the mission.  To be useful to an
autonomous vehicle, the map (data structure) must meet certain
criteria:
\begin{itemize}
\item{}The map should accommodate different types of features
extracted from a broad range of sensor types.  The map must be
extensible so that new sensors can be easily integrated into the
mapping framework.

\item{}The implemented data structure should be easy to search
efficiently.  This allows for easy modification and updating and
allows for the eventual use of prediction based on current
data.

\item{}The data structure should be amenable to the use of multiple
representations of features.  This allows for the possibility of
map-based navigation using multiple sensor modalities (see
Tuohy~\cite{tuohy93b}) as well as the simultaneous use of both
area-based representations and feature-based representations.

\item{}The map should include the ability to partition information.  
In particular we wish to be able to differentiate between
\emph{feature} vs. \emph{non-feature} and between \emph{known} vs.
\emph{unknown} regions.
\end{itemize}

These requirements can be satisfied with a form of \emph{grid-based}
representation.  A grid-based map has the advantages of simplicity and
flexibility.  A grid-based map is easy to search and manipulate.  The
particular form of grid-based map we have employed is constructed in
the form of a multi-dimensional matrix.  Thus, an $[m \times n \times
D]$ matrix can represent $D$ different $[m \times n]$ maps of a given
region.  Our matrix has at least $D = 2 \times s$ dimensions, where
$s$ is the number of sensor modalities employed.  For each sensor, one
layer of $D$ represents the \emph{feature map} while the second
represents the \emph{visitation map}.

The \emph{feature map} is the representation of the feature of
interest as perceived by the associated sensor type.  It partitions
the world into two categories: \emph{feature} or \emph{no feature}.
It makes no assumptions about whether the vehicle (or sensor) has
visited a given area or not other than maintaining an estimate of the
sensor readings in a cell determined to be \emph{feature}.  In the
case of a bathymetric feature, the \emph{feature map} maintains the
average depth in each \emph{feature} cell.

The \emph{visitation map} tracks all locations in the search area in
which the associated sensor has been employed.  In the case of a point
sensor such as temperature, this corresponds to the vehicle location
at the time of sensing.  When the sensor can be remotely employed
(e.g. a scanning sonar), this will correspond to all areas where the
sensor has been active, which may or may not include the vehicle's
actual track.  Thus, a horizontally employed conical sonar beam would
(in the case of a two dimensional visitation map) project into a
fan-shaped structure overlaid onto the visitation map.

The visitation map partitions the world into \emph{visited}
regions and \emph{unvisited} regions.  Just as with the feature map,
\emph{unvisited} cells are empty while \emph{visited} cells contain
relevant information about that region.  Note that the set of
\emph{feature} cells is a wholly contained subset of the set of all
\emph{visited} cells.

If the feature is distributed in a three dimensional region (a thermal
plume, for example) then each map becomes an array of voxels rather
than pixels.  Extending the map is a question of increasing the
dimensionality $D$ of the array, adding an extra layer to account for
each layer of voxels.  Extensions of the same multi-dimensional array
search and update methods can still be employed, although they become
much more complex and time-consuming~\cite{yamauchi96}.

The values of $m$ and $n$ are dictated by the dimensions of the search
area and the chosen cell size.  The cell size is dictated by both the
dimensions of the features being sought and the spatial resolution of
the sensor modality.  In the case of a point sensor mounted on a
dynamically-controlled vehicle such as the AUV \emph{Odyssey}, the
turning radius of the vehicle will influence effective sensor
``spatial resolution.''  It is desirable that the size of the feature
be much larger than the vehicle's turning radius.  In most cases, the
lower bound of cell size will be dictated by the dynamic capabilities
of the sensor platform.

In the case of our bathymetric feature mapper, the matrix is $m \times
n \times 2$ where the two maps are the bathymetric feature map and the
bathymetric visitation map.  Because we are employing a sonar
altimeter in search of trench-like features, our visitation map is
updated by vehicle location via the navigator.  The feature map logs
all locations which the vehicle has visited and which meet the feature
detector's criteria for candidate trench-like features.  The cell
counts $m$ and $n$ are dictated by the chosen survey area which have a
characteristic cell size of $10 \times 10$ meters.  This size is
generally set to be in excess twice the turning radius of the AUV to
prevent the problem of ``trapping,'' which can occur in a simple
trajectory generator if the vehicle attempts to sample a small cell
via the shortest path.  The solution to this potential pitfall is the
implementation of a more intelligent trajectory generation scheme
and/or monitoring of vehicle progress to catch such situations.


\subsection{Waypoint generation}\label{sec:waypoint_gen}

With a map available, the AUV now has a sense of history.  If it knows
where it has been, then it can also \emph{plan} where to go next.
Using the map as it is created allows the {\tt trench\_finder} to make
decisions about where more of a feature is likely to be found, thereby
improving the overall efficiency of the mapping operation.  If all of
a feature has been found, {\tt trench\_finder} can then seek out more
features in the assigned area.  These two functions are referred to as
``locating more feature'' and ``seeking new features.''

The {\tt trench\_finder} is designed to give preference to locating
more of a known feature based on those elements of a feature that have
already been located.  It does so by creating a set of candidate cells
$\{C\}$, which are those cells which are adjacent to feature cells
$\{F\}$ and not members of the visitation cell set $\{\bar{V}\}$.
This is performed via map superposition (see Figure
\ref{fig:overlay_ex}).  This set of candidate cells $\{C\}$ are then
ranked according to distance and orientation relative to the AUV, with
preference given to those cells in the immediate path.  The {\tt
trench\_finder} ranks these according to either a previously generated
lookup table (see Figure \ref{fig:waypoint}) or a cost funtion
which can apply different weights to heading and speed
changes.    The cost function 
\begin{eqnarray}
\mathcal{W} & = & min\left\{\alpha\sqrt{(X_{wp} - X_{veh})^2 + (Y_{wp} -
Y_{veh})^2} \right. \nonumber \\
            &   & \left. + \beta \left|\theta_{veh} -
            tan^{-1}\left(\frac{Y_{wp}-Y_{veh}}{X_{wp}-X_{veh}}\right)\right|_{0 < \Delta\theta < \pi} \right\}
\label{eqn:cost_fcn}
\end{eqnarray}
where $\alpha$ and $\beta$ are weights which alter the relative cost
of turning vs. distance to candidate waypoints.  When using the cost
function, the vehicle determines where to go next by compiling a list
of candidate waypoints as explained in Section \ref{sec:waypoint_gen}.
It then ranks these candidates by cost value $\mathcal{W}$, low to
high, and proceeds to visit each waypoint in sequence.

Each time the adjacency map is updated the list of candidate cells is
also updated and re-ranked according to the current vehicle location
and orientation.  If no more of a known feature is available, then
{\tt trench\_finder} will seek out new features.  This occurs when the
list of candidate cells is empty ($[C] = \emptyset$).  Seeking new
features is performed by first setting the {\tt waypoint} sub-behavior
to proceed to the center of the largest unmapped region.  Upon
arrival, the planner disables {\tt waypoint} and instructs the {\tt
search} behavior to execute a spiral search pattern until either a) a
new feature is found, or b) the spiral covers the area.  If the
vehicle completes its spiral search without locating any new features,
then it will proceed to the largest remaining unmapped area in the
search zone and repeat the process.

\subsection{{\tt trench\_finder} Internal Structure}\label{sec:tf_description} 

The internal construction of the {\tt trench\_finder} can be thought
of as consisting of a supervisory planning state and eight internal
states, many of which alter their internal settings in response to the
mission data and to the overall mission goals (see Figure
\ref{fig:final_tf_states}).  Only one internal state is active at any
time, with the transition between states triggered according to the
current vehicle location and status of the on-board map.  The states
are:

\begin{itemize}
\item[]{\tt initialize} - Execution of {\tt trench\_finder} begins
by reading in the global mission parameters from the mission script.
These parameters include:
 \begin{itemize}

  \item[]north\_lim, south\_lim, east\_lim, west\_lim - Boundaries of
  the search area, defined by the user in meters.  The vehicle origin
  is set by the navigation system (e.g. long baseline, dead reckoning).

  \item[]search\_mode - The type of search mode to be used by the
  vehicle when attempting to locate features in the search zone.
  Modes available are spiral, lawnmower, wagon wheel (i.e. radiating
  out from a point such as a hole in the ice), rectangular, or a simple
  reactive search (i.e. set out at a random heading until one edge of the
  search zone is reached).

  \item[]search\_center\_north, search\_center\_east - If the user
  wishes, a starting point of the search may be explicitly defined.

  \item[]search\_interval - The interval between legs of the search.
  Rectangular searches use this interval directly while a spiral search
  uses $2 \pi$ times this interval.  

  \item[]detect\_thresh - If the user has any \emph{a priori}
  information about the feature such as a threshold value, it is
  entered here.

  \item[]detect\_type - {\tt trench\_finder} can trigger off of slope,
  depth, or a combination of the two.  Depth can be defined as a
  specific threshold or a range of values.

 \end{itemize}

\item[]{\tt delay} - The behavior waits for sensor filters and
settings to initialize and stabilize before attempting to read and
process the data structure.

\item[]{\tt transit} - Transit causes {\tt trench\_finder} to behave
like a simple waypoint routine.  Its function is to steer the vehicle
into the survey area from the launch point.  If search\_center
coordinates have been specified, transit will take the vehicle to that
location, breaking off prematurely if a potential feature is
discovered and the vehicle is within the search zone.  If no search
coordinates have been specified, then transit will take the vehicle to
a point which is equidistant from the narrower of the boundaries and
that same distance from the western or southern end (see Figure
\ref{fig:search_center}).

\item[]{\tt survey} - If desired, a coarse survey of the search zone
may be conducted using either the spiral or lawnmower survey patterns.
This initial survey is intended to seed the waypoint state with
candidate initial search sites.  The course survey can be set by the
user to be at a search interval of 10 to 100 times the standard search
interval.

\item[]{\tt search} - The search state is the default {\tt
trench\_finder} state whenever there are no current waypoints
available.  A search is performed at the start of the mission and at
any point in the mission when no more candidate feature locations are
currently available from the {\tt waypoint} state.  The search type
may be in the form of a traditional lawnmower search, a simple
rectangular box pattern, an Archimedean spiral search (the default
search state), or a wagon wheel search which consists of multiple
legs radiating out from a central starting point (e.g. a hole in ice
cover, a recharging station, or a communications buoy).

\item[]{\tt follow} - When a previously unmapped feature element has
been detected {\tt trench\_finder} switches to the follow state.  This
state instructs the vehicle to hold course until the feature is
passed.  Once the feature has been passed, the follow state switches
to the waypoint state to acquire more of the new feature.

\item[]{\tt waypoint} - Waypoint is the primary active {\tt
trench\_finder} state.  This state examines a list of candidate
feature locations and chooses where to direct the vehicle to go to
next.  Waypoint transitions to the follow state when a feature has
been detected.  If no further candidate waypoints are currently
available, execution is passed back to the search state.

\item[]{\tt boundary} - Boundary is a {\tt trench\_finder}-specific
safety state.  If the vehicle passes outside of the search zone in the
course of tracking a sensed feature or searching for a new feature,
waypoint will direct the vehicle back into the search zone by setting
a waypoint location centered in the search field.  Transition from
this state occurs immediately upon the vehicle's re-entry into the
search area.

\end{itemize}

All state transitions are governed by the {\tt planner} supervisory
state which monitors the current vehicle state, location, and
orientation.  This information is combined with the on-board maps to
determine which state is appropriate at the moment.  The general
sequence of state priorities is boundary (if the vehicle is outside
the search area), waypoint (if waypoint generation results in a
nonzero waypoint list), search (if no waypoints are currently
available), and follow (if a feature is detected.   The values of the
parameters used in the implementation are provided in a tabel in the
Appendix.  

\section{Results}\label{results-sec}

Samples of the performance of the {\tt trench\_finder} behavior are
shown in Figures~\ref{fig:simnov20_03} through
\ref{fig:simmay22_01_bmaps}.  Figures~\ref{fig:simnov20_03} through
\ref{fig:simnov20_03_bmaps} and Figures \ref{fig:simmay22_01} through
\ref{fig:simmay22_01_bmaps} show typical simulation results initiated
in two different part of the Charles River, in which accurate
navigation information is provided to the vehicle.
Figure~\ref{fig:simnov20_03} shows the vehicle track from the
perspective of the entire basin.  The vehicle launch point was moved
near the trench to simplify the examination of the trench finding
phase of the mission.  In this mission the vehicle can be seen to
locate and map the entire main trench.  In
Figure~\ref{fig:simnov20_03_close} the vehicle path can be seen to
make occasional excursions to what appear to be outlying locations.
This is due to the vehicle running out of ``nearby'' candidate
locations and so it returns to less likely candidate waypoints.

Figure \ref{fig:simnov20_03_fmap} shows the vehicle's feature map.
The ``*'' symbols denote the cells which contain candidate features.
Figure \ref{fig:simnov20_03_vmap} is the visitation map of all cells
which the vehicle has sensed -- in this case (with a downward looking
altimeter) the vehicle has also physically visited these cells.
Finally, Figure \ref{fig:simnov20_03_bmaps} shows the union of the two
maps.  The mission was halted before all candidate cells had been
exhausted and a new spiral search was begun.  Note the unsearched
cells (candidate waypoints) at 650 North by 840 East and all along the
feature cells at 1140 East.  We can see from
Figure \ref{fig:simnov20_03_close} that there is more of the feature of
interest (the 7 m contour) just to the east, which we would expect to
be found had the mission continued.

In Figures~\ref{fig:simmay22_01} through \ref{fig:simmay22_01_bmaps}
the vehicle was launched south of the northeastern trench.  In this
case the vehicle started the mission with a preliminary spiral survey
until it located a portion of the target feature.  At that point, the
vehicle began to map the trench as before.  In
Figure~\ref{fig:simmay22_01_close} the vehicle path can be seen in
more detail.  Note that the northeast trench is composed of two pits
with a small saddle in between.  In this mission the vehicle has
migrated from the first trench to the second during the survey.  Given
sufficient time, we expect that it would have completed its survey of
the second part of the trench and returned to the first.  Figures
\ref{fig:simmay22_01_fmap}, \ref{fig:simmay22_01_vmap}, and
\ref{fig:simmay22_01_bmaps} are the \emph{feature map},
\emph{visitation map}, and the combination of the two (as used by the
waypoint planner), respectively.

%% \section{Effect of Navigation Error and External Forces}\label{perf-sec}

%% {\bf Show results.  Discuss the effects of nav error, external currents,
%% cell size search radius, search pattern.}

Given that the adaptive feature mapping behavior works well given
accurate navigation information, the next important question to ask
is how well does this technique perform in the presence of navigation
error and external currents?   This section considers this question by
showing the performance of the technique in one challenging run with
fairly high levels of error.   A more detailed performance analysis is
contained in~\cite{bennett97}. 

The form and effect of navigation error depends upon the type of
navigation system employed.  For AUVs such as the \emph{Odyssey II},
navigation is either an externally referenced system, such as LBL or
the WHOI SHARPS/SNAP system, or wholly internal navigation system such
as dead reckoning and/or INS. Externally referenced systems such as
LBL are susceptible to error due to missed beacon pings, multipath
signals, and even extraneous beacon signals from other arrays (see
Vaganay, \emph{et al}~\cite{vaganay96}).  Internally referenced
systems are susceptible to unmodeled and/or unsensed external forces
on the vehicle and to unmodeled biases brought about by sensor
miscalibration or failure.  Common sources of such
undetected/unmodeled influences are sideslip during turing maneuvers,
vehicle fouling (e.g.  kelp, rope, old nets, etc.), and external
currents.  Common sensor errors are compass bias (mismounted compass,
unmodeled magnetic influences) and speed sensor bias (friction,
limited dynamic range).  

Steady external forces which act upon the whole of the vehicle (such
as currents) are particularly hard to model and predict in a dead
reckoning or INS navigation system.  This is due to the fact that the
vehicle drifts along within the current itself.  The INS system cannot
measure such a steady-state drift due to the lack of acceleration, and
a dead-reckoner which relies on a speed sensor that measures
waterspeed relative to the vehicle will similarly be mislead by the
lack of relative motion between the vehicle and the current as it
drifts along.  Navigation errors build up quickly when the {\tt
trench\_finder} behavior relies solely upon such a dead-reckoning
system.

Figures \ref{fig:simjan29_24_tclose} and \ref{fig:simjan29_24_drclose}
show the combined effects of a -1.1 degree heading bias, a 5 cm/s
speed sensor bias, and an external current of 0.4 cm/s N, 11 cm/s E.
Mission duration was 8 hours 20 minutes, starting at [800 E, 700 N] and
finishing at approximately [450 E, 400 N], traveling a total path length
of 24.5 km. While the dead reckoning navigation system showed steadily
increasing error, the actual vehicle path overlapped the original path
for the last portion of the mission, showing {\tt trench\_finder}'s
ability to maintain contact with a feature despite disturbances.

Additional simulations which illustrate different cost function
weightings, cell sizes, and variation of other parametrs are contained
in~\cite{bennett97}.

\section{Conclusion and Future Research}\label{future-sec}

This paper has presented a behavior-based approach to adaptive feature
mapping.  We introduced the concept of an ``adaptive behavior'' which
incorporates mapping and prediction functions within a single behavior
as part of the Odyssey II layered control architecture.  The behavior
was demonstrated to successfully track the 7 meter contour in the
Charles River despite the presence of navigation error and currents.
The key step was to incorporate a grid-based map and a waypoint
generation scheme within the adaptive feature mapping behavior.  The
adaptive behavior alters its own internal state in response to the
sensed environment, taking into account the mission history.  It
builds up a map of feature locations, uses this map to generate
candidate locations for other parts of the feature, and uses these
candidate locations as navigation waypoints.  The new approach meets
the challenge posed at the outset of the paper of adaptively mapping
the Charles River trench.

Efforts to perform this task using `traditional'' behaviors (without
mapping and prediction) were extremely frustrating~\cite{bennett97}.
Initial attempts to find the trench with a purely reactive system
failed because the AUV would easily lose track of the feature.  A new
implementation using state configured layered control prevented the
vehicle from losing the feature, but the AUV could easily become
``trapped,'' inefficiently revisiting the same terrain over and over
again, and failing to fully map the feature.  One of the positive
lessons learned from this work is that if one expands the definition
of ``what is a behavior'' to incorporate simple planning and mapping
capabilities, then more complex behavior is possible.  By keeping the
planning and mapping functions bound inside this adaptive behavior,
the complexity is kept hidden from other behaviors.



Returning to the motivating scenarios described in
Section~\ref{back-sec}, we believe that the new adpative feature
mapping behavior provides an important building block for realization
of improved mapping and sampling capabilities for AUVs.  The full
potential of AUVs to revolutionize ocean sampling~\cite{curtin93}
cannot be realized until methods are developed to allow AUVs to react
to sensor data in real-time as it is being acquired.  An exciting
possibility for extension of this work is to consider the problem of
tracking dynamic water column features.  Initial work in this
direction is presented in~\cite{bennett97}.

Concurrent mapping and localization using natural terrain feature
embodies one of the ultimate goals of mobile robotics
research~\cite{smith97b}.  Can an AUV build a map of an unknown
environment while using that map to navigate?  One intriguing
possibility is that an AUV could use the new behavior presented here
to be able to re-localize itself by finding and tracking a distintive
contour.  This capability is suggested in
Figure~\ref{fig:simjan29_24_drclose}, in which the vehicle overruns
the same terrain as encountered during the initial part of its
mission, executing nearly the same trajectory.  This is further
supported by Figure~\ref{fig:simjan29_24_ch_drpath}, which displays
the contour extracted by processing the data from the mission.  This
can be considered a type of desirable ``emergent behavior'' resulting
from fairly simple decision rules which demonstrates one of the
desirable characteristics of using a behavior-based control approach.

The simulation study described here is only one step in the
development of new adaptive feature mapping capabilities for
AUVs. Future testing with an actual vehicle is essential to verify the
validity of the technique.  An important characteristic of our work is
that is was performed using the full operating version of the Odyssey
II simulation and control software environment~\cite{bellingham94b}.
The new behavior could be readily ported to an actual Odyssey II
vehicle if an opportunity for field trials became available.

\section*{Acknowledgements}

This work was partially supported by the MIT Sea Grant College
Program, NASA, the Naval Undersea Warfare Center, and the Henry L. and
Grace Doherty Assistant Professorship in Ocean Utilization.  The
authors would like to thank James G. Bellingham, Chryssostomos
Chryssostomodis and all the members of the MIT Sea Grant AUV
Laboratory for their support. 

\appendix
\section{ Parameters Definitions and Values Used in the Simulation} 

\begin{table}
\begin{center}
\begin{tabular}{|l|l|l|} \hline
Symbol or variable &Description &Nominal value \\ \hline \hline
$\left[ \begin{array}{cc}
	X_{west} &Y_{south} \\ X_{east} &Y_{north}
	\end{array} \right]$ &$WESN$ search zone boundaries. 
		&$\left[ \begin{array}{cc}
		200 &200 \\ 2000 &1600
		\end{array} \right]$ \\
$\eta$		&Search mode {\scriptsize (Spiral, Lawnmower, Wagon Wheel, Reactive)} &Spiral \\
$\alpha$	&Search Interval &$15.75$ m \\
$\mathcal{D}$	&Detection type {\scriptsize (scalar, gradient)}
		&Scalar \\
$\tau$		&Detection threshold &$7.0$ m \\
$\delta$	&Deadband	&$\pm 2$ cm \\
$\rho$		&Waypoint adjacency search radius &2 cells \\
{\tt data\_filter}	&Data filtering	&Moving window \\
{\tt cell\_size}	&Map cell size	&$10 \times 10$ meters \\
{\tt waypoint\_method}	&Waypoint search method{\scriptsize (LOOKUP,
DIRECTIONAL, COST)}	&LOOKUP \\
{\tt follow\_mode}	&Contour vs. region search	&CONTOUR \\
$\left[ \begin{array}{cc} \mathcal{O}_{east} &\mathcal{O}_{north}
\end{array} \right]$	&Search origin &$\left[ 800, 700
\right]$ \\
\hline
\end{tabular} \label{tab:inputs}
\caption[{\tt trench\_finder} inputs]{Inputs for {\tt trench\_finder}
and nominal values used in the Charles River basin.}
\end{center}
\end{table}

The values of the {\tt trench\_finder} behavior inputs are listed in
Table \ref{tab:inputs} and are described below: 
\begin{itemize}
\item Search area - The boundaries of the search zone, in meters,
from an origin chosen by the user at launch time.  Unless otherwise
stated, operations are assumed to take place in the first quadrant.

\item Search mode - When the vehicle is searching in an attempt to
locate a feature, it can do so by one of several methods: a spiral
pattern, lawnmower search, wagon wheel search (i.e. multiple legs
radiating out from a central launch point - particularly useful when
the vehicle has been launched from an ice hole), and a simple reactive
search (i.e. the vehicle chooses a random heading and maintains it
until a feature is found or a search area boundary is reached, then it
turns back into the search area on a new arbitrary heading).

\item Search interval - Used for lawnmower and spiral searches; it is
defined as the interval between laps of a lawnmower-type search and
$\frac{1}{2\pi}$ times the interval between spiral laps, respectively.
This should be set according to the characteristic dimensions of the
feature.  For most potential targets, it is recommended that the
interval be set at no larger than one half the average expected short
axis of the feature (if known).

\item Detection type - {\tt trench\_finder} is designed to detect
gradient or scalar threshold values.  In the case of a point sensor,
the gradient is constructed from sensory information obtained along
the vehicle's path (the user must therefore be aware that the gradient
constructed by the vehicle is the one which is perceived by the
vehicle along its track and not necessarily the steepest gradient).
Note also that construction of the estimated gradient using a point
sensor necessitates a delay due to the need to construct the gradient
from present plus recent sensor data.  Either gradient or threshold
values are compared against filtered vehicle sensory data to determine
if the current vehicle location is coincident with a potential feature
of interest.

\item Detection threshold - {\tt trench\_finder} is designed to detect
a specific value or gradient.  This initial value is derived from
basic \emph{a priori} information about the environment.  In the case
of static bathymetric features, a specific contour value, bottom
gradient, or mean seafloor depth is entered which acts as a threshold
for the detector.  In rapid response situations (e.g. satellite
directed response), the threshold may be derived from remote sensing
data.  Significant deviations from local mean values may also be
employed.

\item Data filtering - Raw sensor data is filtered via a moving
average filter~\cite{bennett97}.  All activities performed by {\tt
trench\_finder} are then based on this filtered data stream.

\item Dead band - The purpose of data filtering is to minimize the
effects of noise and false information in the system.  The dead band
operates on the assumption that the sensed, filtered data has temporal
variability which exceeds the dynamic characteristics of the vehicle
-- resulting in unnecessary and undesirable oscillations in the
vehicle trajectory as it attempts to follow the feature.  To prevent
this undesirable vehicle maneuvering over the feature, a dead band is
installed.  The {\tt trench\_finder} uses a dead band of $\pm2$ cm,
based on field experiments conducted in the Charles River.

\item Cell size - The map cell size is based on the conflicting
demands of the desire to maximize the resolution of the feature
description being generated, minimize the time spent sampling any one
feature, and the dynamic limitations of the AUV.  If the intent is to
map the distribution of features, then a larger cell size can be
employed (limited by the estimated characteristic size of the
feature).  Larger cells result in a low resolution mapping of the
region, while smaller cells yield a more detailed map, but at the cost
of more vehicle time necessary to generate the map.

\item Waypoint search radius - {\tt trench\_finder} searches for
candidate features by first examining the region immediately adjacent
to known feature elements.  The vehicle then chooses which of these
cells to visit by comparing this list of candidate waypoints to a
lookup table of map cells which are immediately adjacent to the
vehicle (see Figure \ref{fig:waypoint}).  This search can be expanded
to encompass all map cells within a radius of two cells, if desired.

\item Waypoint search method - the waypoint search method determines
how the vehicle ranks candidate waypoints.  Methods available are
pre-compiled lookup tables (either vehicle heading-dependent or
heading-independent) or a cost/utility function.

\item Contour vs. region search - {\tt trench\_finder} can be set to
search for a specific contour or gradient or a range of
contours/gradients.  It will also search all of an area on one side or
another of a defined contour.  If that contour is closed, it will
search the interior or exterior of that contour, as desired.

\item Starting point - If a specific starting point in the search area
is desired, it is given here.  If not, the starting point is defined
as shown in Figure \ref{fig:search_center}.
\end{itemize}


\bibliographystyle{plain}
\bibliography{/usr2/deslab9/jleonard/refs,/usr/deslab2/abennett/Thesis/drew_refs}

%%% move all figures below here: 

\clearpage


\begin{figure}
 \centerline{\psfig{width=0.7\textwidth,figure=Chapter3/Charles_with_7m_contour.epsc}}
\caption[Charles River 7 m feature]{Charles River basin with 7 m contour highlighted.}
\label{fig:charles_7m_contour}
\end{figure}


\begin{figure}
\centerline{\subfigure[Traditional intelligent control]{\psfig{width=0.5\textwidth,figure=Chapter3/trad_decomp.eps}}
	\subfigure[Behavior based intelligent
	control]{\psfig{width=0.5\textwidth,figure=Chapter3/BBAI.eps}}}
\caption[Traditional vs. behavior based intelligent
	control]{Traditional functional decomposition of intelligent
	control for a mobile robot system vs. behavior based
	decomposition of a mobile robot~\protect\cite{brooks85}.}
\label{fig:BBAIvsTrad}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/layer_diagram.eps}}
\caption[Subsumption diagram]{Subsumption is a series of competence
layers.  Each layer can suppress the layer below it~\protect\cite{brooks85}.}
\label{fig:layer_diagram}
\end{figure}


\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmar05_01_path.epsc}}
\caption{Example of a successful trench finding mission using a simple reactive system.}
\label{fig:mar05_01}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay14_04_path.eps}}
\caption{Example of an unsuccessful trench finding mission using a
simple reactive system.}
\label{fig:may14_04}
\end{figure}


\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay29_01_path.epsc}}
\caption{State configured layered control implementation, in which a
spiral search phase is executed whenever the vehicle loses the feature.}
\label{fig:simmay29_01}
\end{figure}

\begin{figure}
%% \centerline{\psfig{width=0.7\textwidth,figure=Chapter3/adapt_beh_cartoon.eps}}
\caption{Schematic of an adaptive behavior incorporated into a layered
control system.}
\label{fig:int_beh_cartoon}
\end{figure}


\begin{figure}
\centerline{\psfig{width=0.5\textwidth,figure=Chapter3/overlay_ex.eps}}
\caption[Candidate waypoint generation process]{Waypoint candidate
generation process.  The \emph{feature map} on the upper left tracks
all known candidate features.  The \emph{visitation map} on the upper
right tracks all places where the vehicle has been.  Candidate
waypoints are determined by examining the intersection of the two
maps.  bBsed on the assumption that natural features are continuous,
candidate waypoints are defined as those areas which are adjacent to
or near a known feature or features, but which have not yet been
visited by the vehicle.  This list of candidate waypoints is then
ranked, as shown in Figure \ref{fig:waypoint}.}
\label{fig:overlay_ex}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.25\textwidth,figure=Chapter3/waypoint.eps}~~~~\psfig{width=0.4\textwidth,figure=Chapter3/lookup_table.eps}}
\caption{(Left) Waypoints are visited by the vehicle in
a sequence determined by a relative ranking of the candidate
waypoints.  This ranking can be based on a lookup table or based on a
function of distance and location relative to the current vehicle
location and orientation.  (Right) Sample pre-generated
waypoint lookup table.  In this particular table, no special preference
is given to any particular direction.  Other lookup tables may be
biased towards one particular direction, resulting in the vehicle
working its way from waypoint to waypoint along that direction.} 
\label{fig:waypoint}
\end{figure}

\begin{figure}
\centerline{\psfig{height=6in,figure=Chapter3/final_tf_states.eps}}
\caption{Flow of control within the adaptive contour following
behavior.  At each time step, one of the states above is active.
Transitions between states are determined based on current navigation
and sensor information and the content of the visibility and feature
maps that have been created thus far during the mission.}
%% {\tt trench\_finder} behavior.}
\label{fig:final_tf_states}
\end{figure}

\clearpage

\begin{figure}
\centerline{\subfigure{\psfig{height=1.5in,figure=Chapter3/search_center_EW.eps}} 
	\subfigure{\psfig{height=2.5in,figure=Chapter3/search_center_NS.eps}}}
\caption{Initial search starting point determination.  The starting
point is set to maximize the initial search efficiency in the even
that features are few or non-existent.}
\label{fig:search_center}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simnov20_03_path.epsc}}
\caption{Vehicle path for Mission 1.  Vehicle is started near feature
to save transit time, but has no \emph{a priori} information about the
feature.}
\label{fig:simnov20_03}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simnov20_03_close.epsc}}
\caption{Close up of vehicle path
for Mission 1.}
\label{fig:simnov20_03_close}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simnov20_03_fmap.epsc}}
\caption{Feature map generated by the adaptive
contour follower for Mission 1.}
\label{fig:simnov20_03_fmap}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simnov20_03_vmap.eps}}
\caption{Visitation map generated by {\tt trench\_finder} Mission 1.}
\label{fig:simnov20_03_vmap}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simnov20_03_bmaps.eps}}
\caption{Feature map (``+'') overlaid onto the visitation map (``o'')
generated by {\tt trench\_finder} for Mission 1.  Note the unvisited
candidate adjacency cells along the eastern edge of the feature.}
\label{fig:simnov20_03_bmaps}
\end{figure}


\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay22_01_path.epsc}}
\caption{Vehicle path for Mission 2.}
\label{fig:simmay22_01}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay22_01_close.epsc}}
\caption{Close up of vehicle path for Mission 2.}
\label{fig:simmay22_01_close}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay22_01_fmap.eps}}
\caption{Feature map Mission 2.}
\label{fig:simmay22_01_fmap}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay22_01_vmap.eps}}
\caption{Visitation map for Mission 2.}
\label{fig:simmay22_01_vmap}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter3/simmay22_01_bmaps.eps}}
\caption{Overlay of feature map and visitation maps for Mission 2.}
\label{fig:simmay22_01_bmaps}
\end{figure}


\begin{figure}
%%% Figure 4-24, page 135
\centerline{\psfig{width=0.6\textwidth,figure=Chapter4/simjan29_24_diff.eps}}
\caption{Error growth in dead reckoning navigation system for Mission
3 ( shown in Figure \protect\ref{fig:simjan29_24_tclose}).  Note that
while the dead reckoner believed the vehicle was approximately 350
meters away from the true position, the vehicle itself had actually
lapped the feature and was working its way around the feature for a
second time.}
\label{fig:simjan29_24_diff}
\end{figure}

\begin{figure}
%%% Figure 4-25, page 136
\centerline{\psfig{width=0.7\textwidth,figure=Chapter4/simjan29_24_tclose.epsc}} 
\caption{Actual vehicle path for Mission 3, in which there was a
heading bias of -1.1 degrees, a speed bias of -5 cm/s, and an external
current of 0.4 cm/s N, 11 cm/s E.  The vehicle started its mission at
[800 E, 700 N] and ended at approximately [450 E, 400 N].} 
\label{fig:simjan29_24_tclose}
\end{figure}

\begin{figure}
%%% Figure 4-26, page 137
\centerline{\psfig{width=0.7\textwidth,figure=Chapter4/simjan29_24_drclose.epsc}}
\caption{Dead reckoned vehicle path from Mission 3 (compare with
Figure \protect\ref{fig:simjan29_24_tclose}).  Note that while the
dead reckoner navigation error continued to increase, the {\tt
trench\_finder} behavior continued to successfully map the feature.}
\label{fig:simjan29_24_drclose}
\end{figure}

\begin{figure}
\centerline{\psfig{width=0.7\textwidth,figure=Chapter5/simjan29_24_ch_drpath.epsc}}
\caption{Resulting estimated contour from mission shown in Figure
\protect\ref{fig:simjan29_24_drclose}.  The correspondence between the
extracted contours at the beginning and the ned of the mission suggest
the viability of using this method to reset the vehicle position and
correct for dead reckoning error growth.}
\label{fig:simjan29_24_ch_drpath}
\end{figure}


\end{document}
