headgraphic
loader graphic

Loading content ...

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

Subramani, D.N., Q.J. Wei and P.F.J. Lermusiaux, 2017. Stochastic Time Optimal Path Planning in Uncertain, Strong, and Dynamic Flows. Computer Methods in Applied Mechanics and Engineering. Sub-judice.

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 di erent 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

The Extrinsic Geometry of Continuous Time Matrix Algorithms

Feppon, F. and P.F.J. Lermusiaux, 2017. The Extrinsic Geometry of Continuous Time Matrix Algorithms. In preparation.

A geometric framework is introduced for the systematic study of a class of maps called oblique projections. These include orthogonal projections, i.e. maps that project points of a finite dimensional ambient vector space to the closest point of an embedded manifold, but also their generalizations to non euclidean ambient spaces. Typical everyday examples involve the truncated SVD, the polar decomposition, linear subspace filters, and projectors over the dominant eigenspaces of symmetric and non symmetric matrices. A methodology is proposed for the systematic derivation of the differential of these maps, and of convergent continuous time matrix algorithms that allow to dynamically track their values on time dependent matrices. It is shown that these maps are characterized by a bundle of normal spaces that provide the image manifold with a differentiable structure. Generalizations of classical properties of embedded Riemannian manifolds, such as the Gauss equation and the Weingarten identity, are found by replacing the ambient scalar product with the duality bracket. Previous differentiability results obtained for orthogonal projections onto embedded Riemannian manifolds are extended to oblique projections in the non euclidean setting. The framework is applied to the study of the maps above and their image manifold in an embedded setting, that include the Stiefel and the Orthogonal group, the Isospectral and the Grassman manifold, and the bi-Grassman manifold or the set of fixed rank linear projectors.

A Geometric Approach to Dynamical Model–Order Reduction

Feppon, F. and P.F.J. Lermusiaux, 2017. A Geometric Approach to Dynamical Model-Order Reduction. SIAM Journal on Matrix Analysis and Applications, sub-judice.

Any model order reduced dynamical system that evolves a modal decomposition to approximate the discretized solution of a stochastic PDE can be related to a vector field tangent to the manifold of fixed rank matrices. The Dynamically Orthogonal (DO) approximation is the canonical reduced order model for which the corresponding vector field is the orthogonal projection of the original system dynamics onto the tangent spaces of this manifold. The embedded geometry of the fixed rank matrix manifold is thoroughly analyzed.  The curvature of the manifold is characterized and related to the smallest singular value through the study of the Weingarten map.  Differentiability results for the orthogonal projection onto embedded manifolds are reviewed and used to derive an explicit dynamical system for tracking the truncated Singular Value Decomposition (SVD)  of a time-dependent matrix. It is demonstrated that the error made by the DO approximation remains controlled under the minimal condition that the original solution stays close to the low rank manifold, which translates into an explicit dependence of this error on the gap between singular values.  The DO approximation is also justified as the dynamical system that applies instantaneously the SVD truncation to optimally constrain the rank of the reduced solution.  Riemannian matrix optimization is investigated in this extrinsic framework to provide algorithms that adaptively update the best low rank approximation of a smoothly varying matrix.  The related gradient flow provides a dynamical system that converges to the truncated SVD of an input matrix for almost every initial data.

Dynamically Orthogonal numerical schemes for efficient stochastic advection and Lagrangian transport.

Feppon, F. and P.F.J. Lermusiaux, 2017. Dynamically Orthogonal numerical schemes for efficient stochastic advection and Lagrangian transport. SIAM Review, In press.

Quantifying the uncertainty of Lagrangian motion can be performed by solving a large number of ordinary differential equations with random velocities, or equivalently a stochastic transport partial differential equation (PDE) for the ensemble of flow-maps. The Dynamically Orthogonal (DO) decomposition is applied as an efficient dynamical model order reduction to solve for such stochastic advection and Lagrangian transport. Its interpretation as the method that applies instantaneously the truncated SVD on the matrix discretization of the original stochastic PDE is used to obtain new numerical schemes. Fully linear, explicit central advection schemes stabilized with numerical filters are selected to ensure efficiency, accuracy, stability, and direct consistency between the original deterministic and stochastic DO advections and flow-maps. Various strategies are presented for selecting a time-stepping that accounts for the curvature of the fixed rank manifold and the error related to closely singular coefficient matrices. Efficient schemes are developed to dynamically evolve the rank of the reduced solution and to ensure the orthogonality of the basis matrix while preserving its smooth evolution over time. Finally, the new schemes are applied to quantify the uncertain Lagrangian motions of a 2D double gyre flow with random frequency and of a stochastic flow past a cylinder.

Numerical Schemes for Dynamically Orthogonal Equations of Stochastic Fluid and Ocean Flows

Ueckermann, M.P., P.F.J. Lermusiaux and T.P. Sapsis, 2013. Numerical Schemes for Dynamically Orthogonal Equations of Stochastic Fluid and Ocean Flows. J. Comp. Phys., 233, 272-294, doi: 10.1016/j.jcp.2012.08.041.

The quantification of uncertainties is critical when systems are nonlinear and have uncertain terms in their governing equations or are constrained by limited knowledge of initial and boundary conditions. Such situations are common in multiscale, intermittent and non- homogeneous fluid and ocean flows. The Dynamically Orthogonal (DO) field equations provide an efficient time-dependent adaptive methodology to predict the probability density functions of such flows. The present work derives efficient computational schemes for the DO methodology applied to unsteady stochastic Navier-Stokes and Boussinesq equations, and illustrates and studies the numerical aspects of these schemes. Semi-implicit projection methods are developed for the mean and for the orthonormal modes that define a basis for the evolving DO subspace, and time-marching schemes of first to fourth order are used for the stochastic coefficients. Conservative second-order finite-volumes are employed in physical space with Total Variation Diminishing schemes for the advection terms. Other results specific to the DO equations include: (i) the definition of pseudo-stochastic pressures to obtain a number of pressure equations that is linear in the subspace size in- stead of quadratic; (ii) symmetric Total Variation Diminishing-based advection schemes for the stochastic velocities; (iii) the use of generalized inversion to deal with singular subspace covariances or deterministic modes; and (iv) schemes to maintain orthonormal modes at the numerical level. To verify the correctness of our implementation and study the properties of our schemes and their variations, a set of stochastic flow benchmarks are defined including asymmetric Dirac and symmetric lock-exchange flows, lid-driven cavity flows, and flows past objects in a confined channel. Different Reynolds number and Grashof number regimes are employed to illustrate robustness. Optimal convergence under both time and space refinements is shown as well as the convergence of the probability density functions with the number of stochastic realizations.

Quantifying, predicting, and exploiting uncertainties in marine environments

Rixen, M., P.F.J. Lermusiaux and J. Osler, 2012. Quantifying, Predicting and Exploiting Uncertainties in Marine Environments, Ocean Dynamics, 62(3):495–499, doi: 10.1007/s10236-012-0526-8.

Following the scientific, technical and field trial initiatives ongoing since the Maritime Rapid Environmental Assessment (MREA) conferences in 2003, 2004 and 2007, the MREA10 conference provided a timely opportunity to review the progress on various aspects of MREA, with a particular emphasis on marine environmental uncertainty management. A key objective of the conference was to review the present state-of-the art in Quantifying, Predicting and Exploiting (QPE) marine environmental uncertainties. The integration of emerging environmental monitoring and modeling techniques into data assimilation streams and their subsequent exploitation at an operational level involves a complex chain of non-linear uncertainty transfers, including human factors. Accordingly the themes for the MREA10 conference were selected to develop a better understanding of uncertainty, from its inception in the properties being measured and instrumentation employed, to its eventual impact in the applications that rely upon environmental information.

Contributions from the scientific community were encouraged on all aspects of environmental uncertainties: their quantification, prediction, understanding and exploitation. Contributions from operational communities, the consumers of environmental information who have to cope with uncertainty, were also encouraged. All temporal and spatial scales were relevant: tactical, operational, and strategic, including uncertainty studies for topics with long-term implications. Manuscripts reporting new technical and theoretical developments in MREA, but acknowledging effects of uncertainties to be accounted for in future research, were also included.

The response was excellent with 87 oral presentations (11 of which were invited keynote speakers) and 24 poster presentations during the conference. A subset of these presentations was submitted to this topical issue and 22 manuscripts have been published by Ocean Dynamics.

Dynamical criteria for the evolution of the stochastic dimensionality in flows with uncertainty

Sapsis, T.P. and P.F.J. Lermusiaux, 2012. Dynamical criteria for the evolution of the stochastic dimensionality in flows with uncertainty. Physica D, 241(1), 60-76, doi:10.1016/j.physd.2011.10.001.

We estimate and study the evolution of the dominant dimensionality of dynamical systems with uncertainty governed by stochastic partial differential equations, within the context of dynamically orthogonal (DO) field equations. Transient nonlinear dynamics, irregular data and non-stationary statistics are typical in a large range of applications such as oceanic and atmospheric flow estimation. To efficiently quantify uncertainties in such systems, it is essential to vary the dimensionality of the stochastic subspace with time. An objective here is to provide criteria to do so, working directly with the original equations of the dynamical system under study and its DO representation. We first analyze the scaling of the computational cost of these DO equations with the stochastic dimensionality and show that unlike many other stochastic methods the DO equations do not suffer from the curse of dimensionality. Subsequently, we present the new adaptive criteria for the variation of the stochastic dimensionality based on instantaneous i) stability arguments and ii) Bayesian data updates. We then illustrate the capabilities of the derived criteria to resolve the transient dynamics of two 2D stochastic fluid flows, specifically a double-gyre wind-driven circulation and a lid-driven cavity flow in a basin. In these two applications, we focus on the growth of uncertainty due to internal instabilities in deterministic flows. We consider a range of flow conditions described by varied Reynolds numbers and we study and compare the evolution of the uncertainty estimates under these varied conditions.

Dynamically orthogonal field equations for continuous stochastic dynamical systems

Sapsis, T.P. and P.F.J. Lermusiaux, 2009. Dynamically orthogonal field equations for continuous stochastic dynamical systems. Physica D, 238, 2347-2360, doi:10.1016/j.physd.2009.09.017.

In this work we derive an exact, closed set of evolution equations for general continuous stochastic fields described by a Stochastic Partial Differential Equation (SPDE). By hypothesizing a decomposition of the solution field into a mean and stochastic dynamical component, we derive a system of field equations consisting of a Partial Differential Equation (PDE) for the mean field, a family of PDEs for the orthonormal basis that describe the stochastic subspace where the stochasticity `lives’ as well as a system of Stochastic Differential Equations that defines how the stochasticity evolves in the time varying stochastic subspace. These new evolution equations are derived directly from the original SPDE, using nothing more than a dynamically orthogonal condition on the representation of the solution. If additional restrictions are assumed on the form of the representation, we recover both the Proper Orthogonal Decomposition equations and the generalized Polynomial Chaos equations. We apply this novel methodology to two cases of two-dimensional viscous fluid flows described by the NavierStokes equations and we compare our results with Monte Carlo simulations.

Uncertainty Estimation and Prediction for Interdisciplinary Ocean Dynamics

Lermusiaux, P.F.J., 2006. Uncertainty Estimation and Prediction for Interdisciplinary Ocean Dynamics. Refereed manuscript, Special issue on "Uncertainty Quantification". J. Glimm and G. Karniadakis, Eds. Journal of Computational Physics, 217, 176-199. doi: 10.1016/j.jcp.2006.02.010.

Scientific computations for the quantification, estimation and prediction of uncertainties for ocean dynamics are developed and exemplified. Primary characteristics of ocean data, models and uncertainties are reviewed and quantitative data assimilation concepts defined. Challenges involved in realistic data-driven simulations of uncertainties for four-dimensional interdisciplinary ocean processes are emphasized. Equations governing uncertainties in the Bayesian probabilistic sense are summarized. Stochastic forcing formulations are introduced and a new stochastic-deterministic ocean model is presented. The computational methodology and numerical system, Error Subspace Statistical Estimation, that is used for the efficient estimation and prediction of oceanic uncertainties based on these equations is then outlined. Capabilities of the ESSE system are illustrated in three data-assimilative applications: estimation of uncertainties for physical-biogeochemical fields, transfers of ocean physics uncertainties to acoustics, and real-time stochastic ensemble predictions with assimilation of a wide range of data types. Relationships with other modern uncertainty quantification schemes and promising research directions are discussed.

Quantifying Uncertainties in Ocean Predictions

Lermusiaux, P.F.J., C.-S. Chiu, G.G. Gawarkiewicz, P. Abbot, A.R. Robinson, R.N. Miller, P.J. Haley, W.G. Leslie, S.J. Majumdar, A. Pang and F. Lekien, 2006. Quantifying Uncertainties in Ocean Predictions. Refereed invited manuscript. Oceanography, Special issue on "Advances in Computational Oceanography", T. Paluszkiewicz and S. Harper (Office of Naval Research), Eds., 19, 1, 92-105, doi: 10.5670/oceanog.2006.93.

A multitude of physical and biological processes occur in the ocean over a wide range of temporal and spatial scales. Many of these processes are nonlinear and highly variable, and involve interactions across several scales and oceanic disciplines. For example, sound propagation is influenced by physical and biological properties of the water column and by the seabed. From observations and conservation laws, ocean scientists formulate models that aim to explain and predict dynamics of the sea. This formulation is intricate because it is challenging to observe the ocean on a sustained basis and to transform basic laws into generic but usable models. There are imperfections in both data and model estimates. It is important to quantify such uncertainties to understand limitations and identify the research needed to increase accuracies, which will lead to fundamental progress. There are several sources of uncertainties in ocean modeling. First, to simplify models (thereby reducing computational expenses), explicit calculations are only performed on a restricted range of spatial and temporal scales (referred to as the “scale window”) (Nihoul and Djenidi, 1998). Influences of scales outside this window are neglected, parameterized, or provided at boundaries. Such simplifications and scale reductions are a source of error. Second, uncertainties also arise from the limited knowledge of processes within the scale window, which leads to approximate representations or parameterizations. Third, ocean data are required for model initialization and parameter values; however, raw measurements are limited in coverage and accuracy, and they are often processed with the aim of extracting information within a predetermined scale window. Initial conditions and model parameters are thus inexact. Fourth, models of interactions between the ocean and Earth system are approximate and ocean boundary conditions are inexact. For example, effects of uncertain atmospheric fluxes can dominate oceanic uncertainty. Fifth, miscalculations occur due to numerical implementations. All of the above leads to differences between the actual values (unknown) and the measured or modeled values of physical, biological, and geo-acoustical fields and properties.

Evolving the subspace of the three-dimensional multiscale ocean variability: Massachusetts Bay

Lermusiaux, P.F.J., 2001. Evolving the subspace of the three-dimensional multiscale ocean variability: Massachusetts Bay. Journal of Marine Systems, Special issue on "Three-dimensional ocean circulation: Lagrangian measurements and diagnostic analyses", 29/1-4, 385-422, doi: 10.1016/S0924-7963(01)00025-2.

A data and dynamics driven approach to estimate, decompose, organize and analyze the evolving three-dimensional variability of ocean fields is outlined. Variability refers here to the statistics of the differences between ocean states and a reference state. In general, these statistics evolve in time and space. For a first endeavor, the variability subspace defined by the dominant eigendecomposition of a normalized form of the variability covariance is evolved. A multiscale methodology for its initialization and forecast is outlined. It combines data and primitive equation dynamics within a Monte-Carlo approach. The methodology is applied to part of a multidisciplinary experiment that occurred in Massachusetts Bay in late summer and early fall of 1998. For a 4-day time period, the three-dimensional and multivariate properties of the variability standard deviations and dominant eigenvectors are studied. Two variability patterns are discussed in detail. One relates to a displacement of the Gulf of Maine coastal current offshore from Cape Ann, with the creation of adjacent mesoscale recirculation cells. The other relates to a Bay-wide coastal upwelling mode from Barnstable Harbor to Gloucester in response to strong southerly winds. Snapshots and tendencies of physical fields and trajectories of simulated Lagrangian drifters are employed to diagnose and illustrate the use of the dominant variability covariance. The variability subspace is shown to guide the dynamical analysis of the physical fields. For the stratified conditions, it is found that strong wind events can alter the structures of the buoyancy flow and that circulation features are more variable than previously described, on multiple scales. In several locations, the factors estimated to be important include some or all of the atmospheric and surface pressure forcings, and associated Ekman transports and downwelling/upwelling processes, the Coriolis force, the pressure force, inertia and mixing.