Research

Our research is guided by the desire to perform (1) real-time uncertainty quantification and control and use (2) high-fidelity system models together with data to enable automated systems. Many approaches to these problems are either too narrow in application scope or limited by the curse of dimensionality; they require exponentially increasing computational expense with the number of degrees of freedom. Algorithmic breakthroughs are needed to allow high performance and reliable autonomous and robotic systems that can effectively explore, operate, and learn about complex environments. Our research aims to enable

  1. Optimality guarantees for systems with high dimensional and nonlinear dynamics
  2. Increased confidence and expansion of the role of simulation and high-fidelity modeling for autonomy
  3. Incorporation of uncertainty in dynamic environments into the decision making process of autonomous agents

These breakthroughs will lie at the intersection of both (i) computational science and engineering and (ii) autonomy.

gorodetsky_research

Current Projects

Multifidelity uncertainty quantification

The ability to leverage multiple simulation models of low-fidelity for accelerating the propagation of uncertainty through a high-fidelity model has been demonstrated to be one of the prime enabling technologies for addressing UQ in application areas where complex large-scale high-fidelity physical models and data are challenged by prohibitive computational costs.

Examples of multi-fidelity information sources arising in fluid dynamics that can be fused into a unified set of predictions

Predictive models for these application areas typically require fine resolution of the physical state space and the incorporation of a large number of additional degrees of freedom describing design variables, uncertain parameters, and structural parameters. Furthermore, comprehensive analysis algorithms for uncertainty quantification, optimization, and design can easily require millions of model evaluations to fully explore all of the degrees of freedom and to obtain highly resolved simulations. Because many of the most important simulation models require high-performance computing to obtain just a single evaluation for a fixed set of parameters and the output of a large-scale simulation might require up to a terabyte of storage space, performing these analyses for the highest of fidelity models is currently either impractical or requires significant assumptions.

In this research we study new modeling paradigms for fusing information from multiple information sources together. The approaches that we take are mainly statistical and cover topics that include: control variates, importance sampling, and Bayesian networks.

  1. Gorodetsky, A. A., Jakeman, J.D., Geraci, G., Eldred, M.S., "MFNETS: multifidelity data-driven networks for Bayesian learning and prediction." Accepted, International Journal of Uncertainty Quantification 2020
  2. Jakeman, J., Eldred, M. S., Geraci, G., Gorodetsky, A.A. "Adaptive multi-index collocation for uncertainty quantification and sensitivity analysis." International Journal for Numerical Methods in Engineering, 121 (2019) : 1314 – 1343. https://doi.org/10.1002/nme.6268
  3. Gorodetsky, A. A., Geraci, G., Eldred M. S., Jakeman, J. "A generalized approximate control variate framework for multifidelity uncertainty quantification." Journal of Computational Physics, 408, (2020): 109257. https://doi.org/10.1016/j.jcp.2020.109257

Bayesian system identification

Capability-aware multi-agent assignment

We are seeking to enable a group of autonomous agents to jointly accomplish a challenging dynamic task. A majority of existing methods typically tackle this problem by greatly simplifying agent dynamics and doing a nearest-neighbor assignment. Our approach seeks to broadly develop multi-agent assignments that enable general and heterogeneous sets of agents to optimally accomplish a task by leveraging individual capabilities. The main questions we address are:

Optimal assignments of a group of quadcopters to locations on a circle.
  1. How can a group of agents be distributed to accomplish a task?
  2. How does the assignment process leverage knowledge of the agent capabilities while retaining optimality?
  3. We are developing tools that leverage optimal transport theory to create methods that require up to 50% less energy than the current state of the art approaches

Publications:

  1. Kachar, K.G., Gorodetsky, A. A., Dynamic Multi-agent assignment via discrete optimal transport. 2020, arXiv preprint https://arxiv.org/abs/1910.10748 local hosted link

Bayesian inference for low-rank matrices and tensors

Useful machine learning (ML) models must balance interpretability, computational expense, expressivity, and prediction uncertainty. For example, shallow ML models such as linear regression or the perceptron have been studied for decades, are well understood and efficiently computed, and their uncertainty can be quantified via linear inverse problems. However, they often lack the expressiveness to deal with complex nonlinear phenomena exhibited by many applications. More expressive models use deep networks; however are they are also more data hungry and lack robustness to noise.

Bayesian posteriors of low-rank factors in matrix completion, these shapes are very difficult to sample and yield computational inefficiencies

In many natural and social science applications, data is often relational—it describes links between entities. We can efficiently represent relational data involving only one or two groups of entities as matrices, and for more entities as tensors. Examples include the similarity matrix of structure between two chemical compounds or user ratings of movies. Low-rank matrix and tensor factorization methods provide one of the simplest and most effective means of discovering structure from such relational data. The main idea behind this approach, posed in context of movie ratings, is as follows: a user's rating of a movie can be modeled by inner product of the user's and movie's hidden feature vectors. In the context of scientific simulation data, we might ask: Given a set of experimental observations at certain design conditions, what is the likely result of the experiments for those design conditions not performed? Answering this question requires discovering low-dimensional structure that links experimental results and their design conditions. This low-dimensional structure can then be used to relate features of different experiments to predict results for unseen experiments.

In this project, we have rigorously analyzed why both sampling-based procedures are so expensive for this problem, and, relatedly, why approximate variational inference methods underperform the sampling-based alternatives. We discovered that the particular probability distributions arising in this problem have certain symmetries that create algorithmic difficulties. We discovered that these difficulties arise because the common way to pose this problem insufficiently specifies how prior information needed for Bayesian inference is converted into a prior probability distribution. We have demonstrated that a different characterization of prior information, can lead to probability distributions that are more amenable for both sampling and approximation. As a result, we are able to achieve significantly better algorithmic performance. This result indicates that it may soon be possible to more widely leverage the Bayesian probabilistic approaches to yield predictions with quantified uncertainty in this very important and prevalent class of problems.

  1. De, S., Salehi, H. and Gorodetsky, A., "Efficient MCMC Sampling for Bayesian Matrix Factorization by Breaking Posterior Symmetries." 2020, arXiv preprint https://arxiv.org/abs/2006.04295, local hosted link

Funding Sources

Previous Projects

A foundational technique that enables UQ and control for high-fidelity systems is the approximation of computationally intensive aspects of a problem in a simpler way. Examples include

  • Approximating the likelihood to make Markov chain Monte Carlo for Bayesian inference faster
  • Approximate dynamic programming for enabling the solution of large scale dynamic programming problems arising from Markov decision processes

Low-rank tensor decompositions

Tensor decompositions

Tensor decompositions, or high-dimensional analogues of the matrix SVD, are a promising technique to break the curse of dimensionality associated with storing high dimensional data. For instance, a seven-dimensional array with one hundred points in each dimension includes one trillion points in total, whereas a low-rank representation can generate an accurate representation with 70000 points if certain structure exists. We have developed continuous extensions to low-rank tensor decompositions that enable low-rank approximation and computation with high-dimensional functions. The framework enables adaptive, efficient, and flexible algorithms that scale polynomially with dimensionality. For example, we obtain scaling for adaptive integration of functions with up to 600 dimensions, and 7 orders of magnitude compression of cost functionals in stochastic optimal control.

  1. Gorodetsky, A. A., Karaman, S., and Marzouk, Y., "A continuous analogue of the tensor-train decomposition." Computer Methods in Applied Mechanics and Engineering 347 (2019): 59-84. https://doi.org/10.1016/j.cma.2018.12.015
  2. Gorodetsky, A. A., and Jakeman, J. D., "Gradient-based optimization for regression in the functional tensor-train format." Journal of Computational Physics 374 (2018): 1219-1238. https://doi.org/10.1016/j.jcp.2018.08.010

Experimental design

Our optimal design strategy (left) compared to others

One problem prevalent in surrogate modeling is the question of how to allocate resources for analyzing high-fidelity models with a limited computational budget. To enable control and UQ for such models, experimental design strategies must be developed to effectively explore the parameter space to build accurate models. Our work contributes to experimental design for Gaussian process regression through developing an optimization algorithm to choose experiments that minimize the average predicted uncertainty of the surrogate. We showed that the resulting approximation properties are superior to those of other common design choices, especially for problems with complex input parameter geometries.

  1. Gorodetsky, A. A., and Marzouk, Y., "Mercer Kernels and Integrated Variance Experimental Design: Connections Between Gaussian Process Regression and Polynomial Approximation" SIAM/ASA Journal on Uncertainty Quantification (2016): 4:1, 796-828. https://doi.org/10.1137/15M1017119

Markov decision processes and stochastic optimal control

Time lapse image showing the quadcopter passing through the window

Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality.

We have proposed compressed versions of dynamic programming algorithms, such as value iteration and policy iteration, that alleviate the curse of dimensionality in problems that exhibit low-rank structure. The run time of the new algorithms scales polynomially with dimension and polynomially with the rank of the value function. The algorithms are applied to challenging simulated and experimental problems. For instance, we consider an experimental quadcopter for which we develop a controller using a nonlinear, non-holonomic, non-control-affine dynamical system model. The compressed controller requires roughly 1 MB of space in compressed format; an equivalent look up table would have required around 20 TB of memory. I embedded the control on a quadcopter to demonstration maneuvering a quadcopter through a small window, as shown in Figure 3. The low-rank dynamic programming algorithms are widely applicable, and we have applied them to syntactically co-safe linear temporal logic specifications and to differential games

  1. Gorodetsky, A.A., Karaman, S. and Marzouk, Y.M., 2015, July. Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition. In Robotics: Science and Systems. https://doi.org/10.15607/RSS.2015.XI.015
  2. Gorodetsky A. A., Karaman, S., and Marzouk Y.~M. "High-dimensional stochastic optimal control using continuous tensor decompositions." International Journal of Robotics Research, 37.2-3 (2018): 340-377. https://doi.org/10.1177/0278364917753994
  3. Tal, E., Gorodetsky, A. and Karaman, S., 2018, June. Continuous tensor train-based dynamic programming for high-dimensional zero-sum differential games. In 2018 Annual American Control Conference (ACC) (pp. 6086-6093). IEEE. https://10.23919/ACC.2018.8431472
  4. Alora, J. I., Gorodetsky, A. A., Karaman, S., Marzouk, Y. and Lowry, N., "Automated synthesis of low-rank control systems from sc-LTL specifications using tensor-train decompositions," 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, 2016, pp. 1131-1138, https://doi.org/10.1109/CDC.2016.7798419

Low-rank data assimilation

Filtering of Lorenz 1996 System

We seek to extend Bayesian state estimation techniques to dynamical systems with larger state dimensions. This task is important to application areas including autonomy, weather prediction, ocean monitoring, vehicle tracking and many others. The problem is computationally challenging because it requires performing Bayesian inference repeatedly and, for some applications, in real time, and because it requires propagating a probability distribution through nonlinear dynamical systems. Analytic solutions to practical applications often do not exist, and both of these tasks are enormously challenging.

We have developed an algorithm that enables the extension of the class of integration-based Gaussian framework for filtering nonlinear dynamical systems to problems with tens of dimensions. Historically, this framework has only been applied to dynamical systems with a handful of dimensions. Utilizing low-rank functional approximations we created a robust and accurate Gaussian filtering algorithm that scales quadratically with dimension and polynomially with rank. Future applications will explore its use in real-time systems.

  1. Gorodetsky, A. A., Karaman, S., and Marzouk, Y. M., "Low-rank tensor integration for Gaussian filtering of continuous time nonlinear systems," 2017 IEEE 56th Annual Conference on Decision and Control (CDC), Melbourne, VIC, 2017, pp. 2789-2794. https://10.1109/CDC.2017.8264064

System identification

Eigenvalues of an indentified system

One common problem when dealing with autonomous systems is understanding the system model. Often, instead of a specified system model, there exists a large amount of system-response data in the form of a Hankel matrix. The goal of system identification is to use experimental or simulated data to compute a reduced-order model to be used within design, optimization, and control. For systems with many inputs, many outputs, or large time-series of system-response data, established methods that factorize the Hankel matrix, such as the singular value decomposition (SVD) are prohibitively expensive. We have developed algorithms to reduce the complexity of traditional algorithms from cubic to quadratic with respect to Hankel matrix size. This reduction is realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation. The resulting algorithm yields results almost indistinguishable from an SVD-based approach, but with 25 times speedup.

  1. Kramer, B., and Gorodetsky, A. "System identification via CUR-factored Hankel approximation." SIAM Journal on Scientific Computing, 40.2 (2018): A848-A866. https://doi.org/10.1137/17M1137632

Copyright (c) 2020, Alex Gorodetsky, goroda@umich.edu License: CC BY-SA 4.0