Multidisciplinary Simulation, Estimation, and Assimilation Systems (MSEAS)

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, 2013. Science of Autonomy: Time-Optimal Path Planning and Adaptive Sampling for Swarms of Ocean Vehicles. Chapter 11, Springer Handbook of Ocean Engineering: Autonomous Ocean Vehicles, Subsystems and Control, Tom Curtin (Ed.), submitted.

“Science of Autonomy” results obtained by our MSEAS group and recent collaborators are summarized. We present a subset of our results on time-optimal path planning for swarms of ocean vehicles and review some of our research in adaptive sampling. The path planning and adaptive sampling schemes and approaches presented were illustrated by their applications in idealized and realistic ocean conditions. In coming decades, in light of the increasing human population on Earth, the ocean, with the water and life it contains, is likely to become more and more important. Since data collection and operations at sea are expensive, utilizing all of the knowledge we have to plan such collections and operations is logical and most important. Useful knowledge here combines science and engineering, including observation, modeling, prediction, estimation and control. Today, one can only assume that the science of autonomy will play an increasing role in ocean applications. This is because sustaining healthy interactions between the ocean and humans is vital to life on Earth. These interactions will have to be intelligently and autonomously managed.

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., 2013. Time-Optimal Path Planning in Dynamic Flows using Level Set Equations: Theory and Schemes. J. Comp. Phys., submitted.

We develop a computationally efficient, partial differential equation based methodology that predicts the time-optimal paths of autonomous vehicles navigating in continuous, strong and dynamic flow-fields, obviating the need for heuristics. The goal is to predict a sequence of steering directions so that vehicles can best utilize or avoid flow 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 type of flow. We show that our algorithm is computationally efficient – the computational cost grows geometrically with spatial dimensions – 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 avail- able. 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.

Path Planning in Time Dependent Flow Fields using Level Set Methods

Lolla, T.; Ueckermann, M.P.; Yigit, K.; Haley, P.J.; Lermusiaux, P.F.J., 2012, Path planning in time dependent flow fields using level set methods, 2012 IEEE International Conference on Robotics and Automation (ICRA), 166-173, 14-18 May 2012, doi: 10.1109/ICRA.2012.6225364.

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.

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.

Adaptive Acoustical-Environmental Assessment for the Focused Acoustic Field-05 At-sea Exercise

Wang, D., P.F.J. Lermusiaux, P.J. Haley, W.G. Leslie and H. Schmidt, 2006. Adaptive Acoustical-Environmental Assessment for the Focused Acoustic Field-05 At-sea Exercise, Oceans 2006, 6pp, Boston, MA, 18-21 Sept. 2006, doi: 10.1109/OCEANS.2006.306904.

Path Planning Methods for Adaptive Sampling of Environmental and Acoustical Ocean Fields

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.

Adaptive sampling aims to predict the types and locations of additional observations that are most useful for specific objectives, under the constraints of the available observing network. Path planning refers to the computation of the routes of the assets that are part of the adaptive component of the observing network. In this paper, we present two path planning methods based on Mixed Integer Linear Programming (MILP). The methods are illustrated with some examples based on environmental ocean fields and compared to highlight their strengths and weaknesses. The stronger method is further demonstrated on a number of examples covering multi-vehicle and multi-day path planning, based on simulations for the Monterey Bay region. The framework presented is powerful and flexible enough to accommodate changes in scenarios. To demonstrate this feature, acoustical path planning is also discussed.