loader graphic

Loading content ...

Graph-Search and Differential Equations for Time-Optimal Vessel Route Planning in Dynamic Ocean Waves

Mannarini, G., D.N. Subramani, P.F.J. Lermusiaux, and N. Pinardi, 2020. Graph-Search and Differential Equations for Time-Optimal Vessel Route Planning in Dynamic Ocean Waves, IEEE Transactions on Intelligent Transportation Systems 21(8), 3581-3593, doi:10.1109/TITS.2019.2935614

Time-optimal paths are evaluated by VISIR (“discoVerIng Safe and effIcient Routes”), a graph-search ship routing model, with respect to the solution of the fundamental differential equations governing optimal paths in a dynamic wind-wave environment. The evaluation exercise makes use of identical setups: topological constraints, dynamic wave environmental conditions, and vessel-ocean parametrizations, while advection by external currents is not considered. The emphasis is on predicting the time-optimal ship headings and Speeds Through Water constrained by dynamic ocean wave fields. VISIR upgrades regarding angular resolution, time-interpolation, and static navigational safety constraints are introduced. The deviations of the graph-search results relative to the solution of the exact differential equations in both the path duration and length are assessed. They are found to be of the order of the discretization errors, with VISIR’s solution converging to that of the differential equation for sufficient resolution.


A Forward Reachability Equation for Minimum-Time Path Planning in Strong Dynamic Flows

Lolla, T. and P.F.J. Lermusiaux, 2020. A Forward Reachability Equation for Minimum-Time Path Planning in Strong Dynamic Flows. SIAM Journal on Control and Optimization, sub-judice.

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.

Three-dimensional Time-Optimal Path Planning in the Ocean

Kulkarni, C.S. and P.F.J. Lermusiaux, 2020. Three-Dimensional Time-Optimal Path Planning in the Ocean, Ocean Modelling, 152, 101644. doi:10.1016/j.ocemod.2020.101644

Autonomous underwater vehicles (AUVs) operate in the three-dimensional and time-dependent marine environment with strong and dynamic currents. Our goal is to predict the time history of the optimal three-dimensional headings of these vehicles such that they reach the given destination location in the least amount of time, starting from a known initial position. We employ the exact differential equations for time-optimal path planning and develop theory and numerical schemes to accurately predict three-dimensional optimal paths for several classes of marine vehicles, respecting their specific propulsion constraints. We further show that the three-dimensional path planning problem can be reduced to a two-dimensional one if the motion of the vehicle is partially known, e.g. if the vertical component of the motion is forced. This reduces the computational cost. We then apply the developed theory in three-dimensional analytically known flow fields to verify the schemes, benchmark the accuracy, and demonstrate capabilities. Finally, we showcase time-optimal path planning in realistic data-assimilative ocean simulations for the Middle Atlantic Bight region, integrating the primitive-equation of the Multidisciplinary Simulation Estimation and Assimilation System (MSEAS) with the three-dimensional path planning equations for three common marine vehicles, namely propelled AUVs (with unrestricted motion), floats (that only propel vertically), and gliders (that often perform sinusoidal yo-yo motions in vertical planes). These results highlight the effects of dynamic three-dimensional multiscale ocean currents on the optimal paths, including the Gulf Stream, shelfbreak front jet, upper-layer jets, eddies, and wind-driven and tidal currents. They also showcase the need to utilize data-assimilative ocean forecasts for planning efficient autonomous missions, from optimal deployment and pick-up, to monitoring and adaptive data collection.


Risk-Optimal Path Planning in Stochastic Dynamic Environments

Subramani, D.N. and P.F.J. Lermusiaux, 2019. Risk-Optimal Path Planning in Stochastic Dynamic Environments. Computer Methods in Applied Mechanics and Engineering, 353, 391–415. doi:10.1016/j.cma.2019.04.033

We combine decision theory with fundamental stochastic time-optimal path planning to develop partial-differential-equations-based schemes for risk-optimal path planning in uncertain, strong and dynamic flows. The path planning proceeds in three steps: (i) predict the probability distribution of environmental flows, (ii) compute the distribution of exact time-optimal paths for the above flow distribution by solving stochastic dynamically orthogonal level set equations, and (iii) compute the risk of being suboptimal given the uncertain time-optimal path predictions and determine the plan that minimizes the risk. We showcase our theory and schemes by planning risk-optimal paths of unmanned and/or autonomous vehicles in illustrative idealized canonical flow scenarios commonly encountered in the coastal oceans and urban environments. The step-by-step procedure for computing the risk-optimal paths is presented and the key properties of the risk-optimal paths are analyzed.


Stochastic Time-Optimal Path-Planning in Uncertain, Strong, and Dynamic Flows

Subramani, D.N., Q.J. Wei, and P.F.J. Lermusiaux, 2018. Stochastic Time-Optimal Path-Planning in Uncertain, Strong, and Dynamic Flows. Computer Methods in Applied Mechanics and Engineering, 333, 218–237. doi:10.1016/j.cma.2018.01.004

Accounting for uncertainty in optimal path planning is essential for many applications. We present and apply stochastic level-set partial differential equations that govern the stochastic time-optimal reachability fronts and time-optimal paths for vehicles navigating in uncertain, strong, and dynamic flow fields. To solve these equations efficiently, we obtain and employ their dynamically orthogonal reduced-order projections, maintaining accuracy while achieving several orders of magnitude in computational speed-up when compared to classic Monte Carlo methods. We utilize the new equations to complete stochastic reachability and time-optimal path planning in three test cases: (i) a canonical stochastic steady-front with uncertain flow strength, (ii) a stochastic barotropic quasi-geostrophic double-gyre circulation, and (iii) a stochastic flow past a circular island. For all the three test cases, we analyze the results with a focus on studying the effect of flow uncertainty on the reachability fronts and time-optimal paths, and their probabilistic properties. With the first test case, we demonstrate the approach and verify the accuracy of our solutions by comparing them with the Monte Carlo solutions.With the second, we show that different flow field realizations can result in paths with high spatial dissimilarity but with similar arrival times. With the third, we provide an example where time-optimal path variability can be very high and sensitive to uncertainty in eddy shedding direction downstream of the island. Keywords: Stochastic Path Planning, Level Set Equations, Dynamically Orthogonal, Ocean Modeling, AUV, Uncertainty Quantification

A Future for Intelligent Autonomous Ocean Observing Systems

Lermusiaux, P.F.J., D.N. Subramani, J. Lin, C.S. Kulkarni, A. Gupta, A. Dutt, T. Lolla, P.J. Haley Jr., W.H. Ali, C. Mirabito, and S. Jana, 2017. A Future for Intelligent Autonomous Ocean Observing Systems. The Sea. Volume 17, The Science of Ocean Prediction, Part 2, J. Marine Res. 75(6), pp. 765–813. https://doi.org/10.1357/002224017823524035

Ocean scientists have dreamed and recently started to realize an ocean observing revolution with autonomous observing platforms and sensors. Critical questions to be answered by such autonomous systems are where, when, and what to sample for optimal information, and how to optimally reach the sampling locations. Definitions, concepts, and progress towards answering these questions using quantitative predictions and fundamental principles are presented. Results in reachability and path planning, adaptive sampling, machine learning, and teaming machines with scientists are overviewed. The integrated use of differential equations and theory from varied disciplines is emphasized. The results provide an inference engine and knowledge base for expert autonomous observing systems. They are showcased using a set of recent at-sea campaigns and realistic simulations. Real-time experiments with identical AUVs in the Buzzards Bay and Vineyard Sound region first show that our predicted time-optimal paths were faster than shortest distance paths. Deterministic and probabilistic reachability and path forecasts issued and validated for gliders and floats in the northern Arabian Sea are then presented. Novel Bayesian adaptive sampling for hypothesis testing and optimal learning are finally shown to forecast the observations most informative to estimate the accuracy of model formulations, the values of ecosystem parameters and dynamic fields, and the presence of Lagrangian Coherent Structures.

Northern Arabian Sea Circulation-Autonomous Research (NASCar): A Research Initiative Based on Autonomous Sensors

Centurioni, L.R., V. Hormann, L. D. Talley, I. Arzeno, L. Beal, M. Caruso, P. Conry, R. Echols, H. J. S. Fernando, S. N. Giddings, A. Gordon, H. Graber, R. Harcourt, S. R. Jayne, T. G. Jensen, C. M. Lee, P. F. J. Lermusiaux, P. L’Hegaret, A. J. Lucas, A. Mahadevan, J. L. McClean, G. Pawlak, L. Rainville, S. Riser, H. Seo, A. Y. Shcherbina, E. Skyllingstad, J. Sprintall, B. Subrahmanyam, E. Terrill, R. E. Todd, C. Trott, H. N. Ulloa, and H. Wang, 2017. Northern Arabian Sea Circulation-Autonomous Research (NASCar): A Research Initiative Based on Autonomous Sensors. Oceanography 30(2):74–87, https://doi.org/​10.5670/oceanog.2017.224.

The Arabian Sea circulation is forced by strong monsoonal winds and is characterized by vigorous seasonally reversing currents, extreme differences in sea surface salinity, localized substantial upwelling and widespread submesoscale thermohaline structures. Its complicated sea surface temperature patterns are important for the onset and evolution of the Asian Monsoon. Here we describe a program that aims to elucidate the role of upper ocean processes and atmospheric feedbacks in setting the sea surface temperature properties of the region. The wide range of spatial and temporal scales and the difficulty of accessing much of the region with ships due to piracy motivated a novel approach based on state-of-the-art autonomous ocean sensors and platforms. The extensive dataset that is being collected, combined with numerical models and remote sensing data, confirms the role of planetary waves in the reversal of the Somali Current system. These data also document the fast response of the upper equatorial ocean to the monsoon winds through changes in temperature and salinity and the connectivity of the surface currents across the northern Indian Ocean. New observations of thermohaline interleaving structures and mixing in setting the surface temperature properties of the northern Arabian Sea are also discussed.

Optimal Planning and Sampling Predictions for Autonomous and Lagrangian Platforms and Sensors in the Northern Arabian Sea

Lermusiaux, P.F.J., P.J. Haley Jr., S. Jana, A. Gupta, C.S. Kulkarni, C. Mirabito, W.H. Ali, D.N. Subramani, A. Dutt, J. Lin, A. Y. Shcherbina, C. M. Lee, and A. Gangopadhyay, 2017. Optimal Planning and Sampling Predictions for Autonomous and Lagrangian Platforms and Sensors in the Northern Arabian Sea. Oceanography 30(2):172–185, https://doi.org/10.5670/oceanog.2017.242.

Where, when, and what to sample, and how to optimally reach the sampling locations, are critical questions to be answered by Autonomous and Lagrangian Platforms and Sensors. For a reproducible scientific sampling approach, answers should be quantitative and provided using fundamental principles. Concepts and recent progress towards this principled approach are first overviewed, focusing on reachability, path planning, and adaptive sampling. Results of a real-time forecasting and planning experiment completed during February-April 2017 for the Northern Arabian Sea Circulation – Autonomous Research program are then presented. The predictive skill, layered fields, and uncertainty estimates obtained using our MIT MSEAS multi-resolution ensemble ocean modeling system are first studied. With such inputs, deterministic and probabilistic three-dimensional reachability forecasts issued daily for gliders and floats are then showcased and validated. Our Bayesian adaptive sampling framework is finally shown to forecast in real-time the observations that are most informative for estimating classic ocean fields but also secondary-variables such as Lagrangian Coherent Structures.

Energy-optimal path planning in the coastal ocean

Subramani, D. N., P. J. Haley Jr., and P. F. J. Lermusiaux, 2017. Energy-optimal path planning in the coastal ocean. Journal of Geophysical Research Oceans, 122, 3981–4003. doi:10.1002/2016JC012231.

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.

Multiple-Pursuer-One-Evader Pursuit Evasion Game in Dynamic Flow Fields

Sun, W., P. Tsiotras, T. Lolla, D. N. Subramani, and P. F. J. Lermusiaux, 2017. Multiple-Pursuer-One-Evader Pursuit Evasion Game in Dynamic Flow Fields. Journal of Guidance, Control and Dynamics, 40 (7), 1627-1637. DOI: 10.2514/1.G002125

In this paper a reachability-based approach is adopted to deal with the pursuit-evasion di erential 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 defi ned 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 fi elds, with and without obstacles.

Validation of Genetic Algorithm Based Optimal Sampling for Ocean Data Assimilation

Heaney, K. D., P. F. J. Lermusiaux, T. F. Duda and P. J. Haley Jr., 2016.Validation of Genetic Algorithm Based Optimal Sampling for Ocean Data Assimilation. Ocean Dynamics. 66: 1209-1229. doi:10.1007/s10236-016-0976-5.

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.

Energy-optimal Path Planning by Stochastic Dynamically Orthogonal Level-Set Optimization

Subramani, D.N. and P.F.J. Lermusiaux, 2016. Energy-optimal Path Planning by Stochastic Dynamically Orthogonal Level-Set Optimization. Ocean Modeling, 100, 57–77. DOI: 10.1016/j.ocemod.2016.01.006

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.

Science of Autonomy: Time-Optimal Path Planning and Adaptive Sampling for Swarms of Ocean Vehicles

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.

The science of autonomy is the systematic development of fundamental knowledge about autonomous decision making and task completing in the form of testable autonomous methods, models and systems. In ocean applications, it involves varied disciplines that are not often connected. However, marine autonomy applications are rapidly growing, both in numbers and in complexity. This new paradigm in ocean science and operations motivates the need to carry out interdisciplinary research in the science of autonomy. This chapter reviews some recent results and research directions in time-optimal path planning and optimal adaptive sampling. The aim is to set a basis for a large number of vehicles forming heterogeneous and collaborative underwater swarms that are smart, i.e. knowledgeable about the predicted environment and their uncertainties, and about the predicted effects of autonomous sensing on future operations. The methodologies are generic and applicable to any swarm that moves and senses dynamic environmental fields. However, our focus is underwater path planning and adaptive sampling with a range of vehicles such as AUVs, gliders, ships or remote sensing platforms.

Path Planning in Multi-scale Ocean Flows: Coordination and Dynamic Obstacles

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.


Time-Optimal Path Planning in Dynamic Flows using Level Set Equations: Realistic Applications

Lolla, T., P.J. Haley, Jr. and P.F.J. Lermusiaux, 2014. Time-Optimal Path Planning in Dynamic Flows using Level Set Equations: Realistic Applications. Ocean Dynamics, 64, 10:1399–1417. DOI: 10.1007/s10236-014-0760-3.

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.

Time-Optimal Path Planning in Dynamic Flows using Level Set Equations: Theory and Schemes

Lolla, T., P.F.J. Lermusiaux, M.P. Ueckermann and P.J. Haley, Jr., 2014. Time-Optimal Path Planning in Dynamic Flows using Level Set Equations: Theory and Schemes. Ocean Dynamics, 64, 10:1373–1397. DOI: 10.1007/s10236-014-0757-y.

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.

Acoustically Focused Adaptive Sampling and On-board Routing for Marine Rapid Environmental Assessment

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.

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 computational capabilities are not always able to provide oceanic-acoustic predictions in high-resolution and with enough accuracy. Adaptive Rapid Environmental Assessment (AREA) is an adaptive sampling concept being developed in connection with the emergence of Autonomous Ocean Sampling Networks and interdisciplinary ensemble predictions and adaptive sampling via Error Subspace Statistical Estimation (ESSE). By adaptively and optimally deploying in situ sampling resources and assimilating these data into coupled nested ocean and acoustic models, AREA can dramatically improve the estimation of ocean fields that matter for acoustic predictions. These concepts are outlined and a methodology is developed and illustrated based on the Focused Acoustic Forecasting-05 (FAF05) exercise in the northern Tyrrhenian sea. The methodology first couples the data-assimilative environmental and acoustic propagation ensemble modeling. An adaptive sampling plan is then predicted, using the uncertainty of the acoustic predictions as input to an optimization scheme which finds the parameter values of autonomous sampling behaviors that optimally reduce this forecast of the acoustic uncertainty. To compute this reduction, the expected statistics of unknown data to be sampled by different candidate sampling behaviors are assimilated. The predicted-optimal parameter values are then fed to the sampling vehicles. A second adaptation of these parameters is ultimately carried out in the water by the sampling vehicles using onboard routing, in response to the real ocean data that they acquire. The autonomy architecture and algorithms used to implement this methodology are also described. Results from a number of real-time AREA simulations using data collected during the Focused Acoustic Forecasting (FAF05) exercise are presented and discussed for the case of a single Autonomous Underwater Vehicle (AUV). For FAF05, the main AREA-ESSE application was the optimal tracking of the ocean thermocline based on ocean-acoustic ensemble prediction, adaptive sampling plans for vertical Yo-Yo behaviors and subsequent onboard Yo-Yo routing.

Path Planning of Autonomous Underwater Vehicles for Adaptive Sampling Using Mixed Integer Linear Programming

Yilmaz, N.K., C. Evangelinos, P.F.J. Lermusiaux and N. Patrikalakis, 2008. Path Planning of Autonomous Underwater Vehicles for Adaptive Sampling Using Mixed Integer Linear Programming. IEEE Transactions, Journal of Oceanic Engineering, 33 (4), 522-537. doi: 10.1109/JOE.2008.2002105.

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.

Adaptive Modeling, Adaptive Data Assimilation and Adaptive Sampling.

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.

For efficient progress, model properties and measurement needs can adapt to oceanic events and interactions as they occur. The combination of models and data via data assimilation can also be adaptive. These adaptive concepts are discussed and exemplified within the context of comprehensive real-time ocean observing and prediction systems. Novel adaptive modeling approaches based on simplified maximum likelihood principles are developed and applied to physical and physical-biogeochemical dynamics. In the regional examples shown, they allow the joint calibration of parameter values and model structures. Adaptable components of the Error Subspace Statistical Estimation (ESSE) system are reviewed and illustrated. Results indicate that error estimates, ensemble sizes, error subspace ranks, covariance tapering parameters and stochastic error models can be calibrated by such quantitative adaptation. New adaptive sampling approaches and schemes are outlined. Illustrations suggest that these adaptive schemes can be used in real time with the potential for most efficient sampling.

Environmental Prediction, Path Planning and Adaptive Sampling: Sensing and Modeling for Efficient Ocean Monitoring, Management and Pollution Control

Lermusiaux, P.F.J., P.J. Haley Jr. and N.K. Yilmaz, 2007. Environmental Prediction, Path Planning and Adaptive Sampling: Sensing and Modeling for Efficient Ocean Monitoring, Management and Pollution Control. Sea Technology, 48(9), 35-38.


Non-linear Optimization of Autonomous Undersea Vehicle Sampling Strategies for Oceanographic Data-Assimilation

Heaney, K.D., G. Gawarkiewicz, T.F. Duda and P.F.J. Lermusiaux, 2007. Non-linear Optimization of Autonomous Undersea Vehicle Sampling Strategies for Oceanographic Data-Assimilation. Special issue on "Underwater Robotics", Journal of Field Robotics, 24(6), 437-448, doi:10.1002/rob.20183.

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.