Loading content ...

In this paper, we adopt a reachability-based
approach to deal with the pursuit-evasion differential game
between two players in the presence of dynamic environmental
disturbances (e.g., winds, sea currents). We give conditions for
the game to be terminated in terms of reachable set inclusions.
Level set equations are defined and solved to generate the
reachable sets of the pursuer and the evader. The corresponding
time-optimal trajectories and optimal strategies can be retrieved
immediately afterwards. We validate our method by applying
it to a pursuit-evasion game in a simple flow field, for which an
analytical solution is available.We then implement the proposed
scheme to a problem with a more realistic flow field.

The optimal interception of ships sailing on the ocean surface has numerous applications,
including search and rescue operations, inspections of ship’s hulls, ship repair and refueling, naval operations
and planning, and recovery of underwater platforms. Interest in utilizing autonomous undersea vehicles (AUVs)
for these operations has been increasing in recent years. In that case, the optimal recovery of these underwater
vehicles by surface ships is also crucial. The time-sensitive nature of these operations render the search for
an optimal route from a given point of deployment to a (possibly moving) target of paramount importance.
However, numerous factors, including complex coastal geometry, time-varying and complicated currents, and a
moving ship wake (further disrupting the local near-ship currents) make this a very challenging problem. Our
present research motivation is thus to apply and extend our theory and schemes for optimal path planning of
autonomous vehicles operating for long durations in strong and dynamic currents to the optimal
interception of surface vessels. The long-term goal is to develop autonomy for AUVs to enable intercept and
proximity operations with underway surface vessels, predicting and optimally using dynamic wakes, surface
waves, and underwater currents. After extending our time-optimal path planning to the ship interception
problem, we study a set of simulated experiments for the Buzzards Bay, Vineyard Sound, and Elizabeth
Islands region in Massachusetts. We combine realistic data-assimilative ocean modeling with rigorous time-
optimal control and simple ship and wake modeling. To show the versatility of the autonomy approach and also
illustrate how it is needed even for the simplest of the cases, we consider several different scenarios: environments
with no flow at all but with several straits, cases with time-varying currents, and finally proximity operations
considering the effects of ship wakes. We extended our time-optimal path planning to ship interception and illustrated results for
varied scenarios in the southern littoral of Massachusetts for varied ship and AUV speeds, start locations,
and behaviors, with and without currents, and with and without ship wake effects.

Edwards, J., J. Smith, A. Girard, D. Wickman, D. N. Subramani, C. S. Kulkarni,
P.J. Haley, Jr., C. Mirabito, S. Jana, P. F. J. Lermusiaux, 2017. *Data-driven Learning and Modeling
of AUV Operational Characteristics for Optimal Path Planning*. In: Oceans '17 MTS/IEEE Aberdeen, 19-22 June 2017, In press.

Autonomous underwater vehicles (AUVs) are employed in many applications such as ocean
sensing, search and rescue operations, acoustic surveillance, and oil and gas exploitation. With advances in
AUV capability and increasing mission complexity, there is a demand for predicting all reachable locations,
prolonging endurance, and reducing operational costs by optimally utilizing ocean flow forecasts for navigation.
For such optimal navigation, we recently developed new theory, schemes, and computational systems for exact
partial differential equation-based path planning. This new level-set path planning was applied in
realistic re-analysis simulations for the sustained coordinated operation of multiple collaborative AUVs for
time-, coordination- and energy- optimal missions. In the present paper, our goal is to demonstrate
our level-set path planning in real-time sea exercises with real AUVs in shallow coastal ocean regions with
strong and dynamic currents. Our specific objectives are to report the (i) improvements to our 4-D primitive
equation ocean modeling system for accurately forecasting the currents in the Buzzard’s Bay and Vineyard
Sound region, (ii) results of the time-optimal path planning of REMUS 600 AUVs using our fundamental
theory and real-time forecasts, (iii) portability of our software systems for real-time optimal path prediction
in multiple regions and its ability to work with the AUV navigation software. These exercises were the first sea tests of our new theory and software. Our ocean forecasts had skill and time-optimal path forecasts worked with REMUS 600’s. We also identified relationships between
the REMUS 600’s rpm and nominal in-water speed. The results open a new era of optimal AUV missions.

We integrate data-driven ocean modeling with the stochastic Dynamically
Orthogonal (DO) level-set optimization methodology to compute and study energy-optimal
paths, speeds, and headings for ocean vehicles in the Middle-Atlantic Bight (MAB) region.
We hindcast the energy-optimal paths from among exact time-optimal paths for
the period 28 August 2006 to 9 September 2006. To do so, we first obtain a data-assimilative
multiscale re-analysis, combining ocean observations with implicit two-way nested multiresolution
primitive-equation simulations of the tidal-to-mesoscale dynamics in the region.
Second, we solve the reduced-order stochastic DO level-set partial differential equations
(PDEs) to compute the joint probability of minimum arrival-time, vehicle-speed
time-series, and total energy utilized. Third, for each arrival time, we select the vehiclespeed
time-series that minimize the total energy utilization from the marginal probability
of vehicle-speed and total energy. The corresponding energy-optimal path and headings
are obtained through a particle backtracking equation. Theoretically, the present
methodology is PDE-based and provides fundamental energy-optimal predictions without
heuristics. Computationally, it is three- to four-orders of magnitude faster than direct
Monte Carlo methods. For the missions considered, we analyze the effects of the regional
tidal currents, strong wind events, coastal jets, shelfbreak front, and other local
circulations on the energy-optimal paths. Results showcase the opportunities for vehicles
that intelligently utilize the ocean environment to minimize energy usage, rigorously
integrating ocean forecasting with optimal control of autonomous vehicles.

In this paper a reachability-based approach is adopted to deal with the
pursuit-evasion dierential game between one evader and multiple pursuers
in the presence of dynamic environmental disturbances (e.g., winds, sea
currents). Conditions for the game to be terminated are given in terms
of reachable set inclusions. Level set equations are defined and solved to
generate the forward reachable sets of the pursuers and the evader. The
time-optimal trajectories and the corresponding optimal strategies are sub-
sequently retrieved from these level sets. The pursuers are divided into
active pursuers, guards, and redundant pursuers according to their respec-
tive roles in the pursuit-evasion game. The proposed scheme is implemented on problems with both simple and realistic time-dependent flow fields, with and without obstacles.

A theoretical synthesis of forward reachability for minimum–time control of anisotropic vehicles operating in strong and dynamic flows is provided. The synthesis relies on the computation of the forward reachable set of states. Using ideas rooted in the theory of non–smooth calculus, we prove that this set is governed by the viscosity solution of an unsteady Hamilton–Jacobi (HJ) equation. We show that the minimum arrival time satisfies a static HJ equation, when a special local controllability condition holds. Results are exemplified by applications to a sailboat moving in a uniform wind–field and autonomous underwater gliders operating in the Sulu Archipelago.

Regional ocean models are capable of forecasting conditions for usefully long intervals of time
(days) provided that initial and ongoing conditions can be measured. In resource-limited circumstances, the
placement of sensors in optimal locations is essential. Here, a nonlinear optimization approach to determine
optimal adaptive sampling that uses the Genetic Algorithm (GA) method is presented. The method determines
sampling strategies that minimize a user-defined physics-based cost function. The method is evaluated using
identical twin experiments, comparing hindcasts from an ensemble of simulations that assimilate data selected
using the GA adaptive sampling and other methods. For skill metrics, we employ the reduction of the
ensemble root-mean-square-error (RMSE) between the “true” data-assimilative ocean simulation and the
different ensembles of data-assimilative hindcasts. A 5-glider optimal sampling study is set up for a 400 km x
400 km domain in the Middle Atlantic Bight region, along the New Jersey shelf-break. Results are compared
for several ocean and atmospheric forcing conditions.

A stochastic optimization methodology is formulated for computing energy–optimal paths from among time–optimal paths of autonomous vehicles navigating in a dynamic flow field. Based on partial differential equations, the methodology rigorously leverages the level–set equation that governs time–optimal reachability fronts for a given relative vehicle speed function. To set up the energy optimization, the relative vehicle speed is considered to be stochastic and new stochastic Dynamically Orthogonal (DO) level–set equations are derived. Their solution provides the distribution of time–optimal reachability fronts and corresponding distribution of time–optimal paths. An optimization is then performed on the vehicle’s energy–time joint distribution to select the energy–optimal paths for each arrival time, among all stochastic time–optimal paths for that arrival time. Numerical schemes to solve the reduced stochastic DO level–set equations are obtained and accuracy and efficiency considerations are discussed. These reduced equations are first shown to be efficient at solving the governing stochastic level-sets, in part by comparisons with direct Monte Carlo simulations.To validate the methodology and illustrate its overall accuracy, comparisons with `semi–analytical’ energy–optimal path solutions are then completed. In particular, we consider the energy–optimal crossing of a canonical steady front and set up its `semi–analytical’ solution using a dual energy–time nested nonlinear optimization scheme. We then showcase the inner workings and nuances of the energy–optimal path planning, considering different mission scenarios. Finally, we study and discuss results of energy-optimal missions in a strong dynamic double–gyre flow field.

Lermusiaux P.F.J, T. Lolla, P.J. Haley. Jr., K. Yigit, M.P. Ueckermann, T. Sondergaard and W.G. Leslie, 2016. *Science of Autonomy: Time-Optimal Path Planning and Adaptive Sampling for Swarms of Ocean Vehicles*. Chapter 21, Springer Handbook of Ocean Engineering: Autonomous Ocean Vehicles, Subsystems and Control, Tom Curtin (Ed.), pp. 481-498. doi:10.1007/978-3-319-16649-0_21.

We present a novel stochastic optimization method to compute energy-optimal paths, among all time-optimal paths, for vehicles traveling in dynamic unsteady currents. The method defines a stochastic class of instantaneous nominal vehicle speeds and then obtains the energy-optimal paths within the class by minimizing the total time-integrated energy usage while still satisfying the strong-constraint time-optimal level set equation. This resulting stochastic level set equation is solved using a dynamically orthogonal decomposition and the energy-optimal paths are then selected for each arrival time, among all stochastic time-optimal paths. The first application computes energy-optimal paths for crossing a steady front. Results are validated using a semi-analytical solution obtained by solving a dual nonlinear energy-time optimization problem. The second application computes energy-optimal paths for a realistic mission in the Middle Atlantic Bight and New Jersey Shelf/Hudson Canyon region, using dynamic data-driven ocean field estimates.

Lolla, T., P.J. Haley. Jr. and P.F.J. Lermusiaux, 2015. *Path Planning in Multi-scale Ocean Flows: Coordination and Dynamic Obstacles*. Ocean Modelling, 94, 46-66. DOI: 10.1016/j.ocemod.2015.07.013.

As the concurrent use of multiple autonomous vehicles in ocean missions grows, systematic control for their coordinated operation is becoming a necessity. Many ocean vehicles, especially those used in longer–range missions, possess limited operating speeds and are thus sensitive to ocean currents. Yet, the effect of currents on their trajectories is ignored by many coordination techniques. To address this issue, we first derive a rigorous level-set methodology for distance–based coordination of vehicles operating in minimum time within strong and dynamic ocean currents. The new methodology integrates ocean modeling, time-optimal level-sets and optimization schemes to predict the ocean currents, the short-term reachability sets, and the optimal headings for the desired coordination. Schemes are developed for dynamic formation control, where multiple vehicles achieve and maintain a given geometric pattern as they carry out their missions. Secondly, we obtain an efficient, non–intrusive technique for level-set-based time–optimal path planning in the presence of moving obstacles. The results are time-optimal path forecasts that rigorously avoid moving obstacles and sustain the desired coordination. They are exemplified and investigated for a variety of simulated ocean flows. A wind–driven double–gyre flow is used to study time-optimal dynamic formation control. Currents exiting an idealized strait or estuary are employed to explore dynamic obstacle avoidance. Finally, results are analyzed for the complex geometry and multi–scale ocean flows of the Philippine Archipelago.

Petillo, S., H. Schmidt, P.F.J. Lermusiaux, D. Yoerger and A. Balasuriya, 2015. *Autonomous & Adaptive Oceanographic Front Tracking On Board Autonomous Underwater Vehicles*. Proceedings of IEEE OCEANS'15 Conference, Genoa, Italy, 18-21 May, 2015.

Oceanic fronts, similar to atmospheric fronts, occur at the interface of two fluid (water) masses of varying characteristics. In regions such as these where there are quantifiable physical, chemical, or biological changes in the ocean environment, it is possible—with the proper instrumentation—to track, or map, the front boundary.

In this paper, the front is approximated as an isotherm that is tracked autonomously and adaptively in 2D (horizontal) and 3D space by an autonomous underwater vehicle (AUV) running MOOS-IvP autonomy. The basic, 2D (constant depth) front tracking method developed in this work has three phases: detection, classification, and tracking, and results in the AUV tracing a zigzag path along and across the front. The 3D AUV front tracking method presented here results in a helical motion around a central axis that is aligned along the front in the horizontal plane, tracing a 3D path that resembles a slinky stretched out along the front.

To test and evaluate these front tracking methods (implemented as autonomy behaviors), virtual experiments were conducted with simulated AUVs in a spatiotemporally dynamic MIT MSEAS ocean model environment of the Mid-Atlantic Bight region, where a distinct temperature front is present along the shelfbreak. A number of performance metrics were developed to evaluate the performance of the AUVs running these front tracking behaviors, and the results are presented herein.

Cococcioni M., B. Lazzerini and P.F.J. Lermusiaux, 2015. *Adaptive Sampling Using Fleets of Underwater Gliders in the Presence of Fixed Buoys using a Constrained Clustering Algorithm*. Proceedings of IEEE OCEANS'15 Conference, Genoa, Italy, 18-21 May, 2015.

This paper presents a novel way to approach the problem of how to adaptively sample the ocean using fleets of underwater gliders. The technique is particularly suited for those situations where the covariance of the field to sample is unknown or unreliable but some information on the variance is known. The proposed algorithm, which is a variant of the well-known fuzzy C-means clustering algorithm, is able to exploit the presence of non-maneuverable assets, such as fixed buoys. We modified the fuzzy C-means optimization problem statement by including additional constraints. Then we provided an algorithmic solution to the new, constrained problem.

The level set methodology for time-optimal path planning is employed to predict collision-free and fastest time trajectories for swarms of underwater vehicles deployed in the Philippine Archipelago region.
To simulate the multiscale ocean flows in this complex region, a data-assimilative primitive-equation ocean modeling system is employed with
telescoping domains that are interconnected by implicit two-way nesting.
These data-driven multiresolution simulations provide a
realistic flow environment, including variable large-scale currents,
strong jets, eddies, wind-driven currents and tides.
The properties and capabilities of the rigorous level set methodology are
illustrated and assessed quantitatively for several vehicle types and mission scenarios.
Feasibility studies of all-to-all broadcast missions, leading to minimal time transmission between source and receiver locations, are performed using a large number of vehicles.
The results with gliders and faster propelled vehicles are compared.
Reachability studies, i.e.~determining the boundaries of regions that can be reached by vehicles for exploratory missions, are then exemplified and analyzed.
Finally, the methodology is used to determine the optimal strategies
for fastest time pick-up of deployed gliders by means of
underway surface vessels or stationary platforms.
The results highlight the complex effects of multiscale flows on the optimal paths,
the need to utilize the ocean environment for more efficient autonomous
missions and the benefits of including ocean forecasts in the planning of time-optimal paths.

We develop an accurate partial differential equation based methodology that predicts the time-optimal paths of autonomous vehicles navigating in any continuous, strong and dynamic ocean currents, obviating the need for heuristics. The goal is to predict a sequence of steering directions so that vehicles can best utilize or avoid currents to minimize their travel time. Inspired by the level set method, we derive and demonstrate that a modified level set equation governs the time-optimal path in any continuous flow. We show that our algorithm is computationally efficient and apply it to a number of experiments. First, we validate our approach through a simple benchmark application in a Rankine vortex flow for which an analytical solution is available. Next, we apply our methodology to more complex, simulated flow-fields such as unsteady double-gyre flows driven by wind stress and flows behind a circular island. These examples show that time-optimal paths for multiple vehicles can be planned, even in the presence of complex flows in domains with obstacles. Finally, we present, and support through illustrations, several remarks that describe specific features of our methodology.

We develop and illustrate an efficient but rigorous
methodology that predicts the time-optimal paths of ocean
vehicles in dynamic continuous flows. The goal is to best
utilize or avoid currents, without limitation on these currents
nor on the number of vehicles. The methodology employs a
new modified level set equation to evolve a wavefront from
the starting point of vehicles until they reach their desired
goal locations, combining flow advection with nominal vehicle
motions. The optimal paths of vehicles are then computed
by solving particle tracking equations backwards in time.
The computational cost is linear with the number of vehicles
and geometric with spatial dimensions. The methodology is
applicable to any continuous flows and many vehicles scenarios.
Present illustrations consist of the crossing of a canonical
uniform jet and its validation with an optimization problem,
as well as more complex time varying 2D flow fields, including
jets, eddies and forbidden regions.

Wang, D., P.F.J. Lermusiaux, P.J. Haley, D. Eickstedt, W.G. Leslie and H. Schmidt, 2009. *Acoustically Focused Adaptive Sampling and On-board Routing for Marine Rapid Environmental Assessment.* Special issue of Journal of Marine Systems on "Coastal processes: challenges for monitoring and prediction", Drs. J.W. Book, Prof. M. Orlic and Michel Rixen (Guest Eds), 78, S393-S407, doi: 10.1016/j.jmarsys.2009.01.037.

The goal of adaptive sampling in the ocean is to predict
the types and locations of additional ocean measurements that
would be most useful to collect. Quantitatively, what is most useful
is defined by an objective function and the goal is then to optimize
this objective under the constraints of the available observing network.
Examples of objectives are better oceanic understanding, to
improve forecast quality, or to sample regions of high interest. This
work provides a new path-planning scheme for the adaptive sampling
problem. We define the path-planning problem in terms of
an optimization framework and propose a method based on mixed
integer linear programming (MILP). The mathematical goal is to
find the vehicle path that maximizes the line integral of the uncertainty
of field estimates along this path. Sampling this path can improve
the accuracy of the field estimates the most. While achieving
this objective, several constraints must be satisfied and are implemented.
They relate to vehicle motion, intervehicle coordination,
communication, collision avoidance, etc. The MILP formulation is
quite powerful to handle different problem constraints and flexible
enough to allow easy extensions of the problem. The formulation
covers single- and multiple-vehicle cases as well as singleand
multiple-day formulations. The need for a multiple-day formulation
arises when the ocean sampling mission is optimized for
several days ahead. We first introduce the details of the formulation,
then elaborate on the objective function and constraints, and
finally, present a varied set of examples to illustrate the applicability
of the proposed method.

Lermusiaux, P.F.J, 2007. *Adaptive Modeling, Adaptive Data Assimilation and Adaptive Sampling.* Refereed invited manuscript. Special issue on "Mathematical Issues and Challenges in Data Assimilation for Geophysical Systems: Interdisciplinary Perspectives". C.K.R.T. Jones and K. Ide, Eds. Physica D, Vol 230, 172-196, doi:
10.1016/j.physd.2007.02.014.

The problem of how to optimally deploy a suite of sensors to estimate the oceanographic
environment is addressed. An optimal way to estimate (nowcast) and predict (forecast)
the ocean environment is to assimilate measurements from dynamic and uncertain regions
into a dynamical ocean model. In order to determine the sensor deployment strategy
that optimally samples the regions of uncertainty, a Genetic Algorithm (GA) approach
is presented. The scalar cost function is defined as a weighted combination of a sensor
suite’s sampling of the ocean variability, ocean dynamics, transmission loss sensitivity,
modeled temperature uncertainty (and others). The benefit of the GA approach is that the
user can determine “optimal” via a weighting of constituent cost functions, which can
include ocean dynamics, acoustics, cost, time, etc. A numerical example with three gliders,
two powered AUVs, and three moorings is presented to illustrate the optimization
approach in the complex shelfbreak region south of New England.

Variabilities in the coastal ocean environment span
a wide range of spatial and temporal scales. From an acoustic
viewpoint, the limited oceanographic measurements and today’s
ocean modeling capabilities can’t always provide oceanic-acoustic
predictions in sufficient detail and with enough accuracy. Adaptive
Rapid Environmental Assessment (AREA) is a new adaptive sampling
concept being developed in connection with the emergence
of the Autonomous Ocean Sampling Network (AOSN) technology.
By adaptively and optimally deploying in-situ measurement
resources and assimilating these data in coupled nested ocean
and acoustic models, AREA can dramatically improve the ocean
estimation that matters for acoustic predictions and so be
essential for such predictions. These concepts are outlined and
preliminary methods are developed and illustrated based on
the Focused Acoustic Forecasting-05 (FAF05) exercise. During
FAF05, AREA simulations were run in real-time and engineering
tests carried out, within the context of an at-sea experiment
with Autonomous Underwater Vehicles (AUV) in the northern
Tyrrhenian sea, on the eastern side of the Corsican channel.

Yilmaz, N.K., C. Evangelinos, N.M. Patrikalakis, P.F.J. Lermusiaux, P.J. Haley, W.G. Leslie, A.R. Robinson, D. Wang and H. Schmidt, 2006a. *Path Planning Methods for Adaptive Sampling of Environmental and Acoustical Ocean Fields*, Oceans 2006, 6pp, Boston, MA, 18-21 Sept. 2006, doi: 10.1109/OCEANS.2006.306841.