# An Underactuated Vehicle Localization Method in Marine Environments

Tauhidul Alam1, Gregory Murad Reis2, Leonardo Bobadilla2, and Ryan N. Smith3 1
T. Alam is currently affiliated with the State University of New York at Old
Westbury<EMAIL_ADDRESS>2 G. M. Reis and L. Bobadilla are
with the School of Computing and Information Sciences, Florida International
University, Miami, FL 33199, USA (e-mail:{greis003<EMAIL_ADDRESS>3
R. N. Smith is with the Department of Physics and Engineering, Fort Lewis
College, Durango, CO 81301, USA<EMAIL_ADDRESS>
###### Abstract

The underactuated vehicles are apposite for the long-term deployment and data
collection in spatiotemporally varying marine environments. However, these
vehicles need to estimate their positions (states) with intrinsic sensing in
their long-term trajectories. In previous studies, autonomous underwater
vehicles have commonly used vision and range sensors for autonomous state
estimation. Inspired by the intrinsic sensing and the persistent deployment,
we investigate the localization problem (state estimation) for an inexpensive
and underactuated drifting vehicle called a drifter. In this paper, we present
a localization method for the drifter making use of the observations of a
proprioceptive sensor, i.e., compass. We create the water flow pattern within
a given region from ocean model predictions, develop a stochastic motion
model, and analyze the persistent water flow behavior. Given a distribution of
initial deployment states of the drifter at a particular depth of the water
column within the region and the water flow pattern, our method finds
attractors and their transient groups at the given depth as the persistent
behavior of the water flow. A most-likely localized trajectory of the drifter
for a sequence of compass observations is generated based on the persistent
behavior of the water flow and hidden Markov model. Our simulation results
based on data from ocean model predictions substantiate good performance of
our proposed localization method with a low error rate of the state estimation
in the long-term trajectory of the drifter.

##  I Introduction

The application of underactuated underwater vehicles has attracted
considerable interests in ocean monitoring [1], ocean observation [2], and
coral reef surveying [3, 4] since they require minimal resources in the
actuation and sensing. Also, these vehicles are suitable for persistent
deployment [5] in marine environments to tackle several oceanographic tasks.
The fundamental requirement for autonomous underwater vehicles is the ability
to estimate their positions in a marine environment prior to addressing other
tasks. This estimation of position in a marine environment for underwater
vehicles is referred to as the localization problem. This localization problem
is also critical for the long-term autonomy of the underwater vehicles.
Therefore, we aim herein to solve the localization problem for an inexpensive
and underactuated drifting vehicle called a drifter during its long-term
deployment in a marine environment; which is a challenging task in a GPS-
denied and communication-challenged environment at the middle water column of
an ocean.

Figure 1:  Two examples of drifters observing the marine environments at
particular depths [6, 3].

The conventional underwater vehicles use data about a marine environment from
extrinsic sensors such as camera, sonar, lidar and radar for determining their
positions [7, 8, 9]. The use of these extrinsic sensors will result in
excessive resource utilization and accompanying cost for solving the
localization problem. Furthermore, these sensors will not work in various
underwater scenarios such as murky water, fluctuating water temperature, and
highly variable water currents. Moreover, the data transfer of these sensor-
based localization methods suffers from low bandwidth, high latency, and
significant packet loss in the underwater environment. These vehicles also
make use of Doppler Velocity Logs (DVL) and GPS for precision localization
near the water surface of a marine environment [10, 11]. However, both GPS and
DVL observations are unavailable after the mid-water column of the marine
environment. Our minimally-actuated drifter can only rely on a proprioceptive
sensor, e.g., compass, and water currents for finding its position while it
floats at a specific depth of a marine environment.

Our localization problem for drifters involves the potential trajectory
estimation for a sequence of sensor observations taking into account the long-
term ocean dynamics. The drifter is equipped with proprioceptive sensors such
as an inertial measurement unit (IMU) and compass, temperature sensor, WiFi
communication module, and a Raspberry PI computing unit. The drifter floats on
the water carried by currents, waves, and wind and collects data on
environmental attributes such as temperature, salinity, turbidity, and
chlorophyll contents. This drifter has an endurance of days to weeks during
its deployment. These vehicles can control the buoyancy to change its depth
for drifting at a particular water current layer. They are also called
profiling floats [2]. In this scenario, the localization is crucial since the
drifter needs to know its locations along its long-term trajectory in a marine
environment. The localization of the drifter is also challenging because of
the spatiotemporal dynamics of the environment, the disturbances caused by
ocean currents, and the limited sensing and actuation capabilities of the
vehicle itself. Two examples of drifting vehicles to observe marine
environments are shown in Fig. 1.

The contribution of our paper is as follows. We propose a data-driven
localization method for the underactuated drifter. Our proposed method creates
a spatiotemporally varying water current field [12], develops a stochastic
model, and finds the long-term water flow pattern. Then, we generate a most
likely trajectory of the drifter in a marine environment for localizing the
drifter. A dynamical system technique called the generalized cell-to-cell
mapping (GCM) [13] is applied for finding the long-term behavior of the water
flow from the projected motion along with uncertainties in the form of a
Markov Chain. Given a distribution of initial deployment locations of the
drifter at a specific depth of the water column and a sequence of compass
observations, our method finds attractors and their transient groups as the
long-term behavior of the environment. Then, our problem is framed as a Hidden
Markov Model over the space of the environment and the compass observations.
Finally, we apply the Viterbi algorithm [14] to find the most likely sequence
of states of the drifter trajectory for the given sequence of its compass
observations.

##  II Background

Several AUV localization methods apply recursive Bayesian filters, e.g.,
particle filters [15, 16] and Kalman filters [17, 11] utilizing sensor data
such as Doppler velocity log (DVL), inertial navigation system (INS), acoustic
sensors, and range sensors. However, these methods are computationally
expensive and require a large amount of memory capacity. Also, a minimally-
actuated and resource-constrained underwater vehicle like a drifter which is
designed for long-term deployment [5], cannot avail the requirements of these
Bayesian filters based methods. In [12, 18], the velocity analysis of
spatiotemporally varying water current correlating with the velocity of the
vehicle is incorporated to limit error growth in the position estimation.
These closely related works are applicable for deep-diving and expensive AUVs
that estimate the position through several sensor data fusion. Moreover, a
number of closely related limited sensing localization methods for mobile
robots have been proposed in [19, 20, 21] where the robots entail less memory
and computation to solve their localization task. The authors of this stream
of research consider the motion model of simple ground robots whereas we take
into account the dynamics of an underwater drifter combined with the water
flow pattern.

A method to localize underwater gliders in observation networks is proposed in
[22] utilizing the travel time of acoustic signals from near-surface acoustic
sources. An algorithm is developed to estimate an AUV’s position from the time
difference of arrival measurements in a long baseline acoustic positioning
system [23]. Range-based simultaneous AUV and multi-beacon localization in the
presence of unknown ocean currents is presented in [24]. A cooperative
positioning algorithm is proposed for a fully mobile network of AUVs that
perform acoustic ranging and data exchange with one another in extended
duration missions over large areas [9]. The acoustic system methods discussed
above need expensive infrastructure which includes the long base-line (LBL)
and short or ultra short base-line (SBL) systems along with a set of
transponders and modems, and the support of a surface ship. This expensive
infrastructure limits the application of the acoustic system methods in long-
term missions.

Vision-based localization approaches of underwater robots are proposed in [7,
25] which rely on the detection of a collection of features or patterns in
subsea offshore structures for the pose estimation of robots. These vision-
based underwater robot localization methods work well in experimental setups
and structured environments. However, it is hard to deploy these tools in
deep-sea or in unstructured environments. Map-based localization methods in
structured environments using bio-inspired flow sensing are presented in [26,
27, 28] that exploit the extraction of flow features and the speed or pressure
estimation. An IMU and a laser-based vision system is utilized for the
localization of underwater vehicles [29]. An experimental work is described in
[10] on the comparison of acoustic localization with GPS for surface
operation, and the comparison of acoustic and visual methods for underwater
operations. In our previous work [30], we present a tracking algorithm using a
whitening technique for estimating the state trajectory of an AUV from the GPS
observation history to infer its location.

Our work is motivated by the analysis of mid-water current field aided
localization methods [12, 18]. Furthermore, this work is proposed for an
underactuated drifter with intrinsic sensing during its persistent deployment.

##  III Model and Problem Definition

In this section, we model the representation of the environment, and present
the motion model for the specific underactuated underwater vehicle. Then, we
formally state the problem we consider.

###  III-A Model Definition

We consider a 2-D environment where a workspace is a marine environment at a
particular depth or current layer of the water column denoted as ${\cal
W}=\mathbb{R}^{2}$. We also consider the stability of the vertical water
current profile in the environment. Let ${\cal O}$ be the land and littoral
region of the environment which is considered an inaccessible region for the
drifter. The free water space of the marine environment at a given layer is
composed of all navigable locations for the drifter, and it is defined as
$E={\cal W}\setminus{\cal O}$. We discretize the workspace ${\cal W}$ as a 2-D
grid. This grid is also called a cell workspace as this discretized grid is a
collection of cells. Each grid point has a geographic coordinate in the form
of longitude and latitude $(x_{t},y_{t})$ in which $x_{t},y_{t}\in\mathbb{R}$.
The geographic coordinate of each grid point represents the center of an
equal-sized cell $z$. Hence, each cell in the grid is represented as
$z=(x_{t},y_{t})$. We model each drifter as a point robot without considering
its orientation. The state space of the drifter is denoted by $X=E$. A state
of the drifter in the state space is indexed by a cell index
$z\in\\{1,\ldots,N\\}$ where $N$ represents the total number of cells in $X$.
Let $Z=\\{1,\ldots,N\\}$ denote the set of all cells in the state space. Let
$x_{I}$ be a known initial deployment state of the drifter. A probability
distribution of initial deployment states of the drifter is defined as $\pi$.
A state trajectory of the drifter is denoted as $\tilde{x}:[0,t]\rightarrow X$
for a finite time interval $[0,t]$. Let $Y$ be the observation space of
compass output values, which include eight directions (N, NE, E, SE, S, SW, W,
NW) and a ninth idle operation (staying at the same location). An observation
history of the compass for the drifter is defined as
$\tilde{y}:[0,t]\rightarrow Y$.

###  III-B Problem Formulation

We consider that the drifter moves autonomously in the free water space $E$
according to the currents or waves of the marine environment. In each cell $z$
of $E$, except the boundary ones, we consider the simplified scenario that a
drifter has a total of nine actions, based on the currents, wind, and waves at
the specific layer of the water column. From a non-boundary cell $z$, the set
of actions for the drifter are moving towards the eight neighboring directions
and the idle action. We assume that the drifter moves from one cell $z$ to
another cell $z^{\prime}$ in the free water space $E$ following one of the
nine actions, considered as the steady motion of the drifter. We include noise
and uncertainty in the movement along with the steady motion to account for
the modeling error and unmodeled dynamics. When the drifter collides with a
boundary cell $z$, then it will either stay in the same cell or move to one of
the neighboring cells. All the potential options are assumed to have uniform
probability.

The drifter makes use of a proprioceptive sensor named compass and its passive
movements based on the long-term ocean dynamics for its state estimation. We
assume that the drifter keeps track of the observations of compass readings to
estimate its state or position. The drifter motion is derived from the
predicted ocean model. The long-term ocean current flow will help us
understand the potential trajectory of the drifter associated with the history
of compass observations. In the long run, this trajectory will provide the
estimation of the probable final state of the drifter in the mid-water column
of a marine environment. In this context, we formulate our localization
problem for the drifter as follows.

Problem 1. Localization of a drifter using ocean dynamics and proprioceptive
sensing:

Given the long-term ocean dynamics and the sensing observation history
$\tilde{y}$ of compass readings for a drifter, reconstruct the most likely
localized trajectory $\tilde{x}$ of the drifter.

##  IV Method

In this section, we detail our method for solving the problem stated in
Section III.

###  IV-A Data Acquisition

We use the Regional Ocean Modeling System (ROMS) [31] predicted oceanic
current data in the Southern California Bight (SCB) region, California, USA,
as illustrated in Fig. 2, which is contained within
$33^{\circ}17^{\prime}60^{\prime\prime}$ N to $33^{\circ}42^{\prime}$ N and
$-117^{\circ}42^{\prime}$ E to $-118^{\circ}15^{\prime}36^{\prime\prime}$ E.
The model predictions of water current used herein are from July 2011. ROMS is
an open-source ocean model that is widely accepted and supported throughout
the oceanographic and modeling communities. Furthermore, the model was
developed to study ocean processes along the western U.S. coast which is our
area of interest. The ROMS current velocity prediction data are provided at
depths from $0$ m to $125$ m and for $24$ hours of the forecast for a
consecutive number of days. The four dimensions of the $4$-D ROMS current
velocity prediction data consist of three spatial dimensions, e.g., longitude,
latitude, and depth, associated with time. The three velocity components of
oceanic currents are the northing current ($u$), the easting current ($v$),
and the vertical current ($w$). These velocity components are given based on
the four dimensions (time, depth, longitude, and latitude). We assume that the
vertical current velocity ($w$) is zero while a drifter floats at a particular
current layer. We are using herein the water current velocity prediction data
at a particular depth for a specific time.

Figure 2:  The area of interest in the SCB region, California.

###  IV-B Create the Water Flow Pattern

We create a vector field at a particular depth or a given water layer in our
marine environment of interest from the ROMS ocean current predictions data.
Ocean current velocity prediction data for a specific time and at a particular
layer can be represented as a vector field. Let the vector field on a cell $z$
at a particular layer of the environment $E$ be $F(z)$. For a cell $z$ at a
particular layer, the easting velocity component along the latitude axis is
denoted by $u(z)$, the northing velocity component along the longitude axis is
denoted by $v(z)$, and the vertical velocity component is denoted by $w(z)$.
The vector field based on two velocity components for a cell $z$ at a given
layer is specified as:

$F(z)=[u(z),v(z)].$ (1)

The vertical velocity component of the ocean current $w(z)$ at the
corresponding layer is considered zero. Thus, we create the vector field for
the given layer. Then, we find flow lines of the water flow from the vector
field. Flow lines of the water flow over the vector field $F$ are the
trajectories or paths traveled by a point robot at the given layer whose
velocity field is the vector field.

To find the water flow pattern, we need all flow lines from cells in $Z$ at
the given layer for a small time step $\Delta t$ so that we can map one cell
to another cell based on these flow lines. To calculate the next mapped cell
$z(\Delta t)$ after a small time interval $\Delta t$ from each initial cell at
time zero $z(0)$, we use the Euler integration method as follows:

$z(\Delta t)=z(0)+\Delta t\hskip 2.0ptF(z(0)).$ (2)

It gives the endpoint of the flow line from the initial cell $z$ after the
small time $\Delta t$. After that, we use the Euclidean distance for locating
the nearest cell from this endpoint. This nearest cell $z^{\prime}$ becomes
the next mapped cell of the initial cell $z$. Following this process, we
obtain all flow lines for the small time step $\Delta t$ at the given layer.
Finally, we get the next mapped cell for each cell in the environment $E$ at
the corresponding layer.

###  IV-C Long-Term Water Flow Analysis

Given the cell mapping from the vector field and flow lines for the given 2-D
current layer in the previous step, we apply the GCM method [13, 32] for
finding the long-term behavior of the created water flow pattern. Let $r$ be
the probability of the steady or perfect motion of the water flow. Once we add
the uncertainty in the water flow, we get a set of mapped cells at a
particular layer for each cell $z$. Let $A(z)\subset Z$ represent the set of
mapped cells at the given layer of a cell $z$ and $p_{zz^{\prime}}$ denote the
mapping probability of cell $z$ being mapped into one of the mapped cells
$z^{\prime}$. The mapping probability $p_{zz^{\prime}}$ has the following
properties:

$p_{zz^{\prime}}\geq 0,\hskip 10.0pt\sum_{z^{\prime}\in
A(z)}p_{zz^{\prime}}=1.$ (3)

For a non-boundary cell $i$, the mapping probability for the perfect motion
$p_{ij}=r$ from cell $i$ to cell $j$ at the same layer, and the mapping
probability for imperfect motion $p_{ij}=\frac{(1-r)}{(|A(i)|-1)}$ from cell
$i$ to cell $j$ at the same layer. The calculated next mapped cell from the
previous step identifies the mapped cell for the perfect motion. For a
boundary cell $i$, we select all neighboring cells including the same boundary
cell as a set of potential mapped cells with a uniform probability. Due to the
nature of this cell mapping, the system evolution of GCM is expressed as:

$p(n+1)=Pp(n)\text{ or }p(n)=P^{n}p(0),$ (4)

where $P$ is the one-step transition probability matrix, $P^{n}$ is the
$n$-step transition probability matrix, $p(0)$ is the initial probability
distribution vector, $p(n)$ is the $n$-step probability distribution vector.
Let $p_{ij}$ be the ($i,j$)-th element of $P$. It is called the one-step
transition probability from cell $i$ to cell $j$. Let $p_{ij}^{n}$ be the
($i,j$)-th element of $P^{n}$. It is called the $n$-step transition
probability from cell $i$ to cell $j$. If it is possible, through the mapping,
to go from cell $i$ to cell $j$, then we call cell $i$ leads to cell $j$,
symbolically $i\Rightarrow j$. Analytically, cell $i$ leads to cell $j$ if and
only if there exists a positive integer $m$ such that $p^{m}_{ij}>0$. If cell
$i$ leads to cell $j$ and cell $j$ leads to cell $i$, then it is said that
cell $i$ communicates with cell $j$ or cell $j$ communicates with cell $i$.
This will be denoted by $i\Leftrightarrow j$.

This system evolution of GCM leads to a homogeneous finite Markov chain which
determines the long-term behavior of the marine ecosystem. To better
understand the properties of GCM [32], we discuss some relevant definitions in
the following:

###### Definition 1

(Persistent Cell) A cell $z$ is called a persistent cell if it has the
property that when the system is in $z$ at a certain moment, it will return to
$z$ at some time in the future.

###### Definition 2

(Transient Cell) A cell that is not persistent is called a transient cell. It
leads to a persistent group in some number of steps.

###### Definition 3

(Persistent Group or Attractor) A set of cells that is closed under the
mapping is said to form a persistent group if and only if every cell in that
set communicates with every other cell. Each cell belonging to a persistent
group is called a persistent cell. A persistent group is also termed as an
attractor.

Let $g$ be the total number of persistent groups in the system at a given
layer. Let $B_{i}$ be an $i$-th persistent group or a set of persistent cells
in $i$-th group where $B_{i}\subset Z$ and $i\in\\{1,\ldots,g\\}$. Thus, the
set of all persistent groups or attractors at the given layer is denoted as
${\cal B}=\\{B_{1},\ldots,B_{g}\\}$. If a transient cell $j$ leads to the
$i$-th persistent group $B_{i}$, then we call $B_{i}$ a domicile of cell $j$.
A transient cell can also have several domiciles.

###### Definition 4

(Single-domicile and Multiple-domicile) Those transient cells that have only
one domicile are called single-domicile transient cells, and those that have
more than one are called multiple-domicile transient cells.

All the single-domicile transient cells having one particular persistent group
as their common domicile form the domain of attraction of that persistent
group at the same layer. A multiple-domicile transient cell having two or more
persistent groups as its domicile is a cell in the boundary region between the
domains of attraction of these persistent groups. Transient cells are further
divided into transient groups according to the number of domiciles they have.
Let $B(j)$ where $j=\\{1,2,\ldots,g\\}$ be the set of all single-domicile
transient cells having $j$-th persistent group as its domicile. We call this
$j$-th single-domicile transient group. It populates the domain of attraction
of $j$-th persistent group. Let $B(i,j)$ where $i,j=\\{1,2,\ldots,g\\}$, and
$i<j$, be the set of all multiple-domicile transient cells having $i$-th and
$j$-th persistent groups as their domiciles. We call this $(i,j)$-th two-
domicile transient group. The region populated by this group is called the
boundary regions of $i$-th and $j$-th domains of attractions. Hence, we define
the set of transient groups at the given layer as ${\cal T}$.

First, we find all persistent groups ${\cal B}$ and all transient groups
${\cal T}$ from all the cells $Z$ in the environment $E$ at the given layer.
Let $N_{p}$ be the total number of persistent cells and $N_{t}$ be the total
number of transient cells at the same layer. Hence, the total number of cells
$N$ at the same layer can be defined as $N=N_{p}+N_{t}$. Let ${\cal L}$ be the
set of all persistent cells and ${\cal M}$ be the set of all transient cells
at the same layer. Therefore, the set of all cells at the same layer can be
specified as:

$Z={\cal L}\cup{\cal M}.$ (5)

We associate herein between the system evolution of GCM and the directed graph
theory. To obtain the properties of GCM from this association, Algorithm 1
takes as input a geometric description of the environment $E$, and the vector
field $F$, the observation space $Y$, a sequence of compass observations
$\tilde{y}$, and a distribution of initial deployment states $\pi$. It returns
the set of persistent groups ${\cal B}$, the set of transient groups ${\cal
T}$, and the most likely trajectory of the drifter $\tilde{x}$ for the
observation history $\tilde{y}$ at the given layer of the environment. For the
given layer of the environment, Algorithm 1 creates a directed graph $G$
without adding weights to the edges of $G$ from the set of cells $Z$.
Additionally, for each cell $z\in Z$, it finds the geographic location ($x,y$)
(line 4). From this geographic location ($x,y$), it gets the location
($x^{\prime},y^{\prime}$) of the next mapped cell based on the vector field
$F$ as explained before (line 5). Taking the motion uncertainty into
consideration, it computes the set of mapped cells $Z^{\prime}$ where
$Z^{\prime}\subset Z$ (line 6). All cells $z,Z^{\prime}$ are added to the
vertices set and their ordered pairs ($z,z^{\prime}$), where $z^{\prime}\in
Z^{\prime}$, are added the edges set of $G$ (line 7$-$8).

Input: $E$, $F$, $Y$, $\tilde{y}$, $\pi$ – Environment, Vector field,
Observation Space, Observation history, Initial deployment distribution

Output: ${\cal B}$, ${\cal T}$, $\tilde{x}$ – Set of persistent groups, Set of
transient groups, Most likely trajectory

1 $G.V\leftarrow\emptyset,\quad G.E\leftarrow\emptyset,\quad{\cal
B}\leftarrow\emptyset,\quad{\cal
T}\leftarrow\emptyset,\quad{R}\leftarrow\emptyset$

2 for  _$i\leftarrow 1\text{ to }N$_ do

3 $z\leftarrow i$

4 $x,y\leftarrow\textsc{CellLocation}(z)$

5 $x^{\prime},y^{\prime}\leftarrow\textsc{MappedCell}(x,y,F)$

6 $Z^{\prime}\leftarrow\textsc{MappedCellSet}(x^{\prime},y^{\prime})$ // Add
uncertainty

7 $G.V\leftarrow G.V\cup Z^{\prime}\cup\\{z\\}$

8 $G.E\leftarrow G.E\cup\\{(z,z^{\prime})\mid z^{\prime}\in Z^{\prime}\\}$

9

10$S\leftarrow\textsc{StronglyConnectedComponent}(G)$

11 $C\leftarrow\textsc{TransitiveClosure}(G)$

12

13${\cal B}\leftarrow\textsc{FindPersistentGroups}(S,C)$

14 ${\cal L}\leftarrow\textsc{FindUnion}(\cal B)$

15 $\mathcal{M}\leftarrow Z\setminus\mathcal{L}$

16 ${\cal T}\leftarrow\textsc{FindTransientGroups}({\cal B},{\cal M},C)$

17 $P\leftarrow\textsc{TransitionMatrix}(S,C,r)$

18 $Q\leftarrow\textsc{EmissionMatrix}(S,C,Y,r)$

19 $\lambda\leftarrow\textsc{HMM}(P,Q,\pi)$

20 $\tilde{x}\leftarrow\textsc{Viterbi}(\lambda,\tilde{y})$

21 return _${\cal B}$ , ${\cal T}$, $\tilde{x}$ _

22

Algorithm 1 TrajectoryEstimation($E,F,Y,\tilde{y},\pi$)

Next, it finds the set of strongly connected components $S$ from $G$ using
Tarjan’s strongly connected component algorithm [33] (line 9). We define the
connectivity matrix as $C$ and it is calculated from the transitive closure of
$G$ (line 10). From $S$ and $C$, Algorithm 1 finds the set of $g$ persistent
groups ${\cal B}$ using the function FindPersistentGroups (line 11). In this
function, if each vertex in a strongly connected component communicates to all
other vertices in the strongly connected component then this strongly
connected component is found as a persistent group and each cell of this
persistent group is classified as a persistent cell. Otherwise, each cell of
this strongly connected component is classified as a transient cell. Taking
the union of $g$ persistent group sets, we get the set of all persistent cells
${\cal L}$ (line 12). Aside from all the persistent cells, the remaining cells
from $Z$ represent the set of transient cells ${\cal M}$ (line 13). Thus, it
classifies all the cells $Z$ in the environment $E$ at the given layer into
the set of persistent cells ${\cal L}$ and the set of transient cells ${\cal
M}$. To determine the set of single-domicile and multiple-domicile transient
groups ${\cal T}$ using the function FindTransientGroups (line 14), we check
if there is any path or connectivity from each transient cell to cells in all
$g$ persistent groups according to the connectivity matrix $C$ of graph $G$.
Accordingly, we find the set of transient groups ${\cal T}$. Finally, the set
of persistent groups or attractors ${\cal B}$ and the set of transient groups
or domains of attractions ${\cal T}$ characterize the long-term water flow of
the marine environment at the given layer.

###  IV-D Generate the Most Likely Localized Trajectory for a Drifter

Given the collection of persistent groups or attractors and their associated
transient groups or domains of attractions as the long-term water flow of the
marine environment at the given layer, we generate the most likely trajectory
of the drifter $\tilde{x}$ for its localization in the environment. Generation
of the most likely trajectory of the drifter for its state estimation is
modeled as a hidden Markov model (HMM). This hidden Markov model is defined by
six elements. These elements are the state space $X$, the observation space
$Y$, the one-step transition probability matrix $P$, the emission transition
or observation transition probability matrix $Q$, an initial state
distribution $\pi$, and a compass observation history $\tilde{y}$. To
characterize this model, Algorithm 1 calculates the transition probability
matrix $P$ from the strongly connected components $S$, the connectivity matrix
$C$, and the probability of reliable or perfect motion $r$ (line 15). It also
computes the emission transition probability matrix $Q$ from the elements
mentioned before along with the observation space $Y$ (line 16). We obtain a
compass observation history of the drifter $\tilde{y}$ simulating the Markov
chain $P$ from a distribution of initial deployment states $\pi$. An HMM
object is characterized as $\lambda=(P,Q,\pi)$ (line 17). Given a sequence of
compass observations $\tilde{y}$ and the HMM object $\lambda$, Algorithm 1
computes the optimal hidden state sequence $\tilde{x}$ that best explains the
compass observation sequence $\tilde{y}$ (line 18). This optimal hidden state
sequence or the most likely trajectory of the drifter is computed using the
Viterbi algorithm [14], which is a dynamic programming algorithm. This most
likely hidden state sequence is also termed as the Viterbi path. This
trajectory of the drifter represents its localized trajectory for the given
compass observation sequence. Thus, we generate the most likely localized
trajectory of the drifter from deterministic (a known initial state $x_{I}$)
and probabilistic (a set of initial states including the neighbors of the
original initial state) distribution of initial deployment states $\pi$ for
different compass observation sequences.

##  V Simulation Results

We validated our method through simulations using the ROMS [31] ocean current
predictions data in the SCB region. An ocean environment was considered as the
simulation environment for the drifter movements having one $2$D water current
predictions of a given layer (i.e., $10$ m). The $2$D ocean water space was
tessellated into a grid map. The resolution of the grid map was set to
$21\times 29$. The vector field from the ocean current predictions was
calculated at the given layer of the environment. The flow lines of the ocean
current data were generated through the Euler numerical integration method
from all locations of the water space at the given layer for a small time
$\Delta t$ which was the time to pass a cell. Thus, we found the cell mapping
of each cell location of the water space at the corresponding layer. The
vector field and the flow lines for this vector field of the simulated
environment are illustrated in Fig. 3.

|
---|---
(a) | (b)
Figure 3:  Vector field and flow lines: (a) The vector field generated from ROMS current prediction data; (b) Flow lines for a small time step $\Delta t$ from all locations along with added red uncertain movements depicted inside the red box. |
---|---
(a) | (b)
Figure 4:  (a)$-$(b) Attractors (blue and red regions) and associated
transient groups (the cyan region for the blue attractor, the orange region
for the red attractor, and the magenta region for both attractors); (a) The
white original trajectory and the black most likely trajectory for the given
compass observation sequence/history and the deterministic distribution of the
yellow initial location; (b) The white original trajectory and the black most
likely trajectory for the given compass observation sequence/history and the
probabilistic distribution of the yellow initial locations. Both trajectories
localized at the green final locations.

We implemented Algorithm 1 in a simulation to find the long-term water flow
behavior of the considered water current layer and generate the most likely
trajectory of the drifter based on the long-term water flow in the simulated
environment. From the simulation run, we found two persistent groups and three
transient groups where two of them are single-domicile transient groups and
one is a multiple-domicile transient group. The long-term behavior of the
simulated environment and two instances (both deterministic, i.e., a known
initial state and probabilistic, i.e., the nondeterministic neighboring states
around the initial deployment state) of the generated most likely localized
trajectory of the drifter are shown in Fig. 4.

Figure 5:  Comparison of the estimation error in the final location and the
whole trajectory for the various number of steps in the compass observation
sequence. Figure 6:  Comparison of the estimation error in the final location
and the whole trajectory for different long-term regions (persistent groups or
attractors and transient groups) of the environment. Figure 7:  Comparison of
the estimation error in the final location and the whole trajectory for
deterministic and probabilistic localization methods.

For the quantitative analysis of our localization method, we calculated the
Euclidean distance between the generated and actual final locations of the
drifter in its trajectory as the final location estimation error. For the
whole drifter trajectory, we also calculated the Euclidean distance between
the generated and actual locations for each observation and summed up these
distances for all observations that represents the whole trajectory estimation
error. This is also the total deviation of the generated trajectory from the
original trajectory of the drifter. For each of the five number of steps
($20$, $40$, $60$, $80$, $100$) in the compass observation sequence, we ran
the simulation $50$ times using the deterministic method and recorded the
estimation error. Then, we compared the results of estimation error for the
final location of the trajectory and for the whole trajectory with respect to
these various number of steps ($20$, $40$, $60$, $80$, $100$) in the compass
observation sequence which is illustrated in Fig. 5. We computed the same
error for different long-term regions (attractors $B_{1}$, $B_{2}$, and
transient groups $B(1)$, $B(2)$, $B(1,2)$) of the environment for $40$ steps
in the compass observation sequence from $20$ deterministic simulation runs
and show their comparison in Fig. 6. We also ran the simulation $50$ times for
$50$ steps in the compass observation sequence using both deterministic and
probabilistic methods in terms of the initial states and stored the estimation
error for the final location of the trajectory and for the whole trajectory.
The results of the estimation error of deterministic and probabilistic
localization methods were compared and are shown in Fig. 7.

##  VI Conclusion and Future Work

In this paper, we presented a localization method for an underactuated drifter
floating at a particular depth of the water column in a marine environment.
First, we created the vector field to study the water flow pattern from the
ROMS ocean current predictions data of the mid-water column. The water flow
pattern was characterized as a stochastic model. The generalized cell-to-cell
mapping method was applied to determine the persistent behavior of the water
flow taking the stochastic model into account. Based on the persistent
behavior of water flow, we generated the most likely localized trajectory of
the drifter for a distribution of initial deployment states and the
observation history from the compass inside the drifter using a hidden Markov
model. Our results demonstrate that the final state estimation error is very
low and the whole trajectory deviation increases with the increase of the
observation length. Therefore, our localization method works considerably well
although it depends on the observations from the intrinsic sensor of the
drifter.

In the future, we can do the temporal analysis of our method to evaluate the
variability of the generated localized trajectory of the drifter over space
and time. The neighboring current layers of a given layer in a marine
environment can be incorporated for taking the vertical motion of our passive
drifter into account in our localization method. Our ideas can be also
extended for the vehicles that have the capability of horizontal motion
control in addition to the vertical motion capability. An example of such
propeller-driven, long-range AUV is called Tethys which can be used to conduct
oceanic missions over periods of weeks or even months without a ship [34].
Moreover, our proposed method is a solution to the passive localization
problem. The inclusion of more motion capabilities to the profiling drifter in
order to guarantee more accurate localization which will help develop a
solution to the active localization problem.

Our previous work [35] develops a control policy using a Markov decision
process (MDP) on the fully observable states of the predicted ocean current
model. We can combine this localization method with the previous control
method by introducing a partially observable Markov decision process (POMDP)
framework.

## Acknowledgments

We would like to acknowledge the financial support of a Florida International
University Graduate School Dissertation Year Fellowship. We offer our thanks
to the Coordination for the Improvement of Higher Education Personnel (CAPES),
Brazil, for the doctoral scholarship. This work is also supported in part by
the U.S. Department of Homeland Security under Grant Award Number
2017-ST-062000002, by the Office of Naval Research Award Number N000141612634,
and by the National Science Foundation MRI Award Number 1531322.

## References

  * [1] A. Molchanov, A. Breitenmoser, and G. S. Sukhatme, “Active drifters: Towards a practical multi-robot system for ocean monitoring,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 545–552, 2015.
  * [2] R. N. Smith and V. T. Huynh, “Controlling buoyancy-driven profiling floats for applications in ocean observation,” IEEE Journal of Oceanic Engineering, vol. 39, no. 3, pp. 571–586, 2014.
  * [3] M. Xanthidis, A. Q. Li, and I. Rekleitis, “Shallow coral reef surveying by inexpensive drifters,” in Proceedings of the MTS/IEEE OCEANS-Shanghai, pp. 1–9, 2016.
  * [4] A. Q. Li, I. Rekleitis, S. Manjanna, N. Kakodkar, J. Hansen, G. Dudek, L. Bobadilla, J. Anderson, and R. N. Smith, “Data correlation and comparison from multiple sensors over a coral reef with a team of heterogeneous aquatic robots,” in Proceedings of the International Symposium on Experimental Robotics (ISER), pp. 717–728, 2016.
  * [5] T. Alam, G. M. Reis, L. Bobadilla, and R. N. Smith, “A data-driven deployment approach for persistent monitoring in aquatic environments,” in Proceedings of the IEEE International Conference on Robotic Computing (IRC), 2018\.
  * [6] Autonomous Profiling Floats. Available at http://navis.sea-birdscientific.com/.
  * [7] T. Palmer, D. Ribas, P. Ridaoy, and A. Malliosy, “Vision based localization system for AUV docking on subsea intervention panels,” in Proceedings of the MTS/IEEE Oceans-Europe, pp. 1–10, 2009.
  * [8] F. Maurelli, Y. Petillot, A. Mallios, P. Ridao, and S. Krupinski, “Sonar-based AUV localization using an improved particle filter approach,” in Proceedings of the MTS/IEEE Oceans-Europe, pp. 1–9, 2009.
  * [9] A. Bahr, J. J. Leonard, and M. F. Fallon, “Cooperative localization for autonomous underwater vehicles,” International Journal of Robotics Research, vol. 28, no. 6, pp. 714–728, 2009.
  * [10] P. Corke, C. Detweiler, M. Dunbabin, M. Hamilton, D. Rus, and I. Vasilescu, “Experiments with underwater robot localization and tracking,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 4556–4561, 2007.
  * [11] M. Karimi, M. Bozorg, and A. Khayatian, “A comparison of DVL/INS fusion by UKF and EKF to localize an autonomous underwater vehicle,” in Proceedings of the First RSI/ISM International Conference on Robotics and Mechatronics (ICRoM), pp. 62–67, 2013.
  * [12] L. Medagoda, J. C. Kinsey, and M. Eilders, “Autonomous underwater vehicle localization in a spatiotemporally varying water current field,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 565–572, 2015.
  * [13] C. S. Hsu, Cell-to-cell mapping: A method of global analysis for nonlinear systems, vol. 64.  Springer Science & Business Media, 2013.
  * [14] G. D. Forney, “The Viterbi algorithm,” Proceedings of the IEEE, vol. 61, no. 3, pp. 268–278, 1973.
  * [15] N. Y. Ko, T. G. Kim, and Y. S. Moon, “Particle filter approach for localization of an underwater robot using time difference of arrival,” in Proceedings of the MTS/IEEE OCEANS-Yeosu, pp. 1–7, 2012.
  * [16] F. Maurelli, S. Krupinski, Y. Petillot, and J. Salvi, “A particle filter approach for AUV localization,” in Proceedings of the MTS/IEEE OCEANS, pp. 1–7, 2008.
  * [17] A. Alcocer, P. Oliveira, and A. Pascoal, “Study and implementation of an EKF GIB-based underwater positioning system,” Control Engineering Practice, vol. 15, no. 6, pp. 689–701, 2007.
  * [18] L. Medagoda, S. B. Williams, O. Pizarro, J. C. Kinsey, and M. V. Jakuba, “Mid-water current aided localization for autonomous underwater vehicles,” Autonomous Robots, vol. 40, no. 7, pp. 1207–1227, 2016.
  * [19] J. M. O’Kane and S. M. LaValle, “Localization with limited sensing,” IEEE Transactions on Robotics, vol. 23, no. 4, pp. 704–716, 2007.
  * [20] T. Alam, L. Bobadilla, and D. A. Shell, “Space-efficient filters for mobile robot localization from discrete limit cycles,” IEEE Robotics and Automation Letters, vol. 3, no. 1, pp. 257–264, 2018.
  * [21] L. H. Erickson, J. Knuth, J. M. O’Kane, and S. M. LaValle, “Probabilistic localization with a blind robot,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1821–1827, 2008\.
  * [22] J. Sun, S. Liu, J. Yu, A. Zhang, and F. Zhang, “Localization of underwater gliders with acoustic travel-time in an observation network,” in Proceedings of the MTS/IEEE OCEANS-Shanghai, pp. 1–5, 2016.
  * [23] D. J. Thomson, S. E. Dosso, and D. R. Barclay, “Modeling AUV localization error in a long baseline acoustic positioning system,” IEEE Journal of Oceanic Engineering, 2017.
  * [24] M. Bayat, N. Crasta, A. P. Aguiar, and A. M. Pascoal, “Range-based underwater vehicle localization in the presence of unknown ocean currents: Theory and experiments,” IEEE Transactions on Control Systems Technology, vol. 24, no. 1, pp. 122–139, 2016.
  * [25] M. Carreras, P. Ridao, R. García, and T. Nicosevici, “Vision-based localization of an underwater robot in a structured environment,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), vol. 1, pp. 971–976, 2003.
  * [26] N. Muhammad, G. Toming, J. A. Tuhtan, M. Musall, and M. Kruusmaa, “Underwater map-based localization using flow features,” Autonomous Robots, vol. 41, no. 2, pp. 417–436, 2017.
  * [27] J. F. Fuentes-Pérez, N. Muhammad, J. A. Tuhtan, R. Carbonell-Baeza, M. Musall, G. Toming, and M. Kruusmaa, “Map-based localization in structured underwater environment using simulated hydrodynamic maps and an artificial lateral line,” in Proceedings of the IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 128–134, 2017.
  * [28] N. Muhammad, N. Strokina, G. Toming, J. Tuhtan, J.-K. Kämäräinen, and M. Kruusmaa, “Flow feature extraction for underwater robot localization: Preliminary results,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1125–1130, 2015.
  * [29] G. C. Karras and K. J. Kyriakopoulos, “Localization of an underwater vehicle using an IMU and a laser-based vision system,” in Proceedings of the Mediterranean Conference on Control and Automation (MED), pp. 1–6, 2007.
  * [30] G. M. Reis, H. Leon, T. Alam, J. Anderson, L. Bobadilla, and R. N. Smith, “A whitening-based tracking algorithm for autonomous underwater vehicles,” in Proceedings of the MTS/IEEE OCEANS-Kobe, 2018.
  * [31] A. F. Shchepetkin and J. C. McWilliams, “The regional oceanic modeling system (ROMS): a split-explicit, free-surface, topography-following-coordinate oceanic model,” Ocean Modelling, vol. 9, no. 4, pp. 347–404, 2005.
  * [32] L. Hong and J. Xu, “Crises and chaotic transients studied by the generalized cell mapping digraph method,” Physics Letters A, vol. 262, no. 4, pp. 361–375, 1999.
  * [33] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146–160, 1972.
  * [34] B. W. Hobson, J. G. Bellingham, B. Kieft, R. McEwen, M. Godin, and Y. Zhang, “Tethys-class long range AUVs-extending the endurance of propeller-driven cruising AUVs from days to weeks,” in Proceedings of the IEEE/OES Autonomous Underwater Vehicles (AUV), pp. 1–8, 2012.
  * [35] T. Alam, G. M. Reis, L. Bobadilla, and R. N. Smith, “A data-driven deployment and planning approach for underactuated vehicles in marine environments,”  Submitted to IEEE Journal of Oceanic Engineering, 2018. Under review.