Active Learning Active Subspace Chaotic Dynamics Chebfun Control Variates Differential Games Dynamic Programming Dynamical Systems Electric Propulsion Experimental Design Gaussian Process Regression Graphical Models Kalman Filtering Linear Temporal Logic Low-rank approximation Markov Decision Processes model reduction Motion Planning Multi-Agent Systems Multifidelity Methods Optimal Control Polynomial Approximation Sensitivity Analysis Stochastic Optimal Control Support Vector Machines Surrogate models System Identification Tensor decompositions Tensor-train decomposition Uncertainty Quantification
2019 |
Kachar, Koray G; Gorodetsky, Alex A Dynamic multi-agent assignment via discrete optimal transport Journal Article Forthcoming Forthcoming. Abstract | Links | BibTeX | Tags: Multi-Agent Systems, Optimal Control, Optimal Transport @article{Kachar2019, title = {Dynamic multi-agent assignment via discrete optimal transport}, author = {Koray G. Kachar and Alex A. Gorodetsky}, url = {https://arxiv.org/abs/1910.10748 http://www.alexgorodetsky.com/wp-content/uploads/2019/10/kachar_gorodetsky_dot.pdf}, year = {2019}, date = {2019-10-23}, abstract = {We propose an optimal solution to a deterministic dynamic assignment problem by leveraging connections to the theory of discrete optimal transport to convert the combinatorial assignment problem into a tractable linear program. We seek to allow a multi-vehicle swarm to accomplish a dynamically changing task, for example tracking a multi-target swarm. Our approach simultaneously determines the optimal assignment and the control of the individual agents. As a result, the assignment policy accounts for the dynamics and capabilities of a heterogeneous set of agents and targets. In contrast to a majority of existing assignment schemes, this approach improves upon distance-based metrics for assignments by considering cost metrics that account for the underlying dynamics manifold. We provide a theoretical justification for the reformulation of this problem, and show that the minimizer of the dynamic assignment problem is equivalent to the minimizer of the associated Monge problem arising in optimal transport. We prove that by accounting for dynamics, we only require computing an assignment once over the operating lifetime --- significantly decreasing computational expense. Furthermore, we show that the cost benefits achieved by our approach increase as the swarm size increases, achieving almost 50% cost reduction compared with distance-based metrics. We demonstrate our approach through simulation on several linear and linearized problems. }, keywords = {Multi-Agent Systems, Optimal Control, Optimal Transport}, pubstate = {forthcoming}, tppubtype = {article} } We propose an optimal solution to a deterministic dynamic assignment problem by leveraging connections to the theory of discrete optimal transport to convert the combinatorial assignment problem into a tractable linear program. We seek to allow a multi-vehicle swarm to accomplish a dynamically changing task, for example tracking a multi-target swarm. Our approach simultaneously determines the optimal assignment and the control of the individual agents. As a result, the assignment policy accounts for the dynamics and capabilities of a heterogeneous set of agents and targets. In contrast to a majority of existing assignment schemes, this approach improves upon distance-based metrics for assignments by considering cost metrics that account for the underlying dynamics manifold. We provide a theoretical justification for the reformulation of this problem, and show that the minimizer of the dynamic assignment problem is equivalent to the minimizer of the associated Monge problem arising in optimal transport. We prove that by accounting for dynamics, we only require computing an assignment once over the operating lifetime --- significantly decreasing computational expense. Furthermore, we show that the cost benefits achieved by our approach increase as the swarm size increases, achieving almost 50% cost reduction compared with distance-based metrics. We demonstrate our approach through simulation on several linear and linearized problems. |
Jakeman, John; Eldred, Michael S; Geraci, Gianluca; Gorodetsky, Alex Adaptive Multi-index collocation for uncertainty quantification and sensitivity analysis Journal Article Forthcoming arXiv, Forthcoming. Abstract | Links | BibTeX | Tags: Multifidelity Methods, Sensitivity Analysis, Surrogate models, Uncertainty Quantification @article{Jakeman2019, title = {Adaptive Multi-index collocation for uncertainty quantification and sensitivity analysis}, author = {John Jakeman and Michael S. Eldred and Gianluca Geraci and Alex Gorodetsky}, url = {https://arxiv.org/abs/1909.13845}, doi = {arXiv:1909.13845}, year = {2019}, date = {2019-10-01}, journal = {arXiv}, abstract = {In this paper, we present an adaptive algorithm to construct response surface approximations of high-fidelity models using a hierarchy of lower fidelity models. Our algorithm is based on multi-index stochastic collocation and automatically balances physical discretization error and response surface error to construct an approximation of model outputs. This surrogate can be used for uncertainty quantification (UQ) and sensitivity analysis (SA) at a fraction of the cost of a purely high-fidelity approach. We demonstrate the effectiveness of our algorithm on a canonical test problem from the UQ literature and a complex multi-physics model that simulates the performance of an integrated nozzle for an unmanned aerospace vehicle. We find that, when the input-output response is sufficiently smooth, our algorithm produces approximations that can be over two orders of magnitude more accurate than single fidelity approximations for a fixed computational budget.}, keywords = {Multifidelity Methods, Sensitivity Analysis, Surrogate models, Uncertainty Quantification}, pubstate = {forthcoming}, tppubtype = {article} } In this paper, we present an adaptive algorithm to construct response surface approximations of high-fidelity models using a hierarchy of lower fidelity models. Our algorithm is based on multi-index stochastic collocation and automatically balances physical discretization error and response surface error to construct an approximation of model outputs. This surrogate can be used for uncertainty quantification (UQ) and sensitivity analysis (SA) at a fraction of the cost of a purely high-fidelity approach. We demonstrate the effectiveness of our algorithm on a canonical test problem from the UQ literature and a complex multi-physics model that simulates the performance of an integrated nozzle for an unmanned aerospace vehicle. We find that, when the input-output response is sufficiently smooth, our algorithm produces approximations that can be over two orders of magnitude more accurate than single fidelity approximations for a fixed computational budget. |
Alben, Silas; Gorodetsky, Alex; Kim, Donghak; Deegan, Robert D Semi-implicit methods for the dynamics of elastic sheets Journal Article Journal of Computational Physics, In Press , 2019. Abstract | Links | BibTeX | Tags: Chaotic Dynamics, Dynamical Systems, Numerical methods @article{Alben2019, title = {Semi-implicit methods for the dynamics of elastic sheets}, author = {Silas Alben and Alex Gorodetsky and Donghak Kim and Robert D. Deegan}, url = {https://authors.elsevier.com/c/1Zpmp508HiGzG doi:10.1016/j.jcp.2019.108952 http://www.alexgorodetsky.com/wp-content/uploads/2019/09/Alben-et-al.-2019-Semi-implicit-methods-for-the-dynamics-of-elastic-sheets.pdf}, doi = {10.1016/j.jcp.2019.108952}, year = {2019}, date = {2019-09-16}, journal = {Journal of Computational Physics}, volume = {In Press}, abstract = {Recent applications (e.g. active gels and self-assembly of elastic sheets) motivate the need to efficiently simulate the dynamics of thin elastic sheets. We present semi-implicit time stepping algorithms to improve the time step constraints that arise in explicit methods while avoiding much of the complexity of fully-implicit approaches. For a triangular lattice discretization with stretching and bending springs, our semi-implicit approach involves discrete Laplacian and biharmonic operators, and is stable for all time steps in the case of overdamped dynamics. For a more general finite-difference formulation that can allow for general elastic constants, we use the analogous approach on a square grid, and find that the largest stable time step is two to three orders of magnitude greater than for an explicit scheme. For a model problem with a radial traveling wave form of the reference metric, we find transitions from quasi-periodic to chaotic dynamics as the sheet thickness is reduced, wave amplitude is increased, and damping constant is reduced.}, keywords = {Chaotic Dynamics, Dynamical Systems, Numerical methods}, pubstate = {published}, tppubtype = {article} } Recent applications (e.g. active gels and self-assembly of elastic sheets) motivate the need to efficiently simulate the dynamics of thin elastic sheets. We present semi-implicit time stepping algorithms to improve the time step constraints that arise in explicit methods while avoiding much of the complexity of fully-implicit approaches. For a triangular lattice discretization with stretching and bending springs, our semi-implicit approach involves discrete Laplacian and biharmonic operators, and is stable for all time steps in the case of overdamped dynamics. For a more general finite-difference formulation that can allow for general elastic constants, we use the analogous approach on a square grid, and find that the largest stable time step is two to three orders of magnitude greater than for an explicit scheme. For a model problem with a radial traveling wave form of the reference metric, we find transitions from quasi-periodic to chaotic dynamics as the sheet thickness is reduced, wave amplitude is increased, and damping constant is reduced. |
Jorns, Benjamin A; Gorodetsky, Alex; Lasky, Ian; Kimber, Angela; Dahl, Peter; Peter, Benjamin St.; Dressler, Rainer Uncertainty Quantification of Electrospray Thruster Array Lifetime Conference The 30th International Electric Propulsion Conference, University of Vienna, Austria, 2019. Abstract | Links | BibTeX | Tags: Electric Propulsion, Uncertainty Quantification @conference{Jorns2019, title = {Uncertainty Quantification of Electrospray Thruster Array Lifetime}, author = {Benjamin A. Jorns and Alex Gorodetsky and Ian Lasky and Angela Kimber and Peter Dahl and Benjamin St. Peter and Rainer Dressler}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2019/10/IEPC-2019-317.pdf}, year = {2019}, date = {2019-09-15}, publisher = {The 30th International Electric Propulsion Conference, University of Vienna, Austria}, abstract = {A numerical investigation into the performance and lifetime of an electrospray array thruster of pressurized-capillary emitters is presented. A series of modules based on the Electrospray Propulsion Engineering Toolkit (ESPET) are employed to create a reduced fidelity model for the operation of a colloidal thruster. New modules are added to this toolkit to enable predictions of lifetime including scaling laws for beam divergence, pro- pellant deposition on the extractor grid, and failure due to backstreaming current. The impact of uncertainty on performance and lifetime is also quantified. Sources of uncertainty considered include both physics-based model parameters and manufacturing tolerances A Monte Carlo analysis is applied to generate probability distribution functions for key per- formance parameters including thrust, efficiency, and specific impulse. The median perfor- mance values are shown to agree qualitatively with typical performance conditions for this pressure-fed configuration of an electrospray array. Probability of failure curves are also generated for both a single emitter and an array of emitters operated on the same power supply. It is found that as the uncertainty in design parameters or the number of emitters increases, the lifetime of the array decreases. Parametric analyses are also performed with the goal to optimize thruster performance while accounting for uncertainty. To this end, it is shown that there is an optimum throttling point for achieving maximum predicted total impulse. This proof of concept thus illustrates the potential capability of this approach for guiding design and optimization.}, keywords = {Electric Propulsion, Uncertainty Quantification}, pubstate = {published}, tppubtype = {conference} } A numerical investigation into the performance and lifetime of an electrospray array thruster of pressurized-capillary emitters is presented. A series of modules based on the Electrospray Propulsion Engineering Toolkit (ESPET) are employed to create a reduced fidelity model for the operation of a colloidal thruster. New modules are added to this toolkit to enable predictions of lifetime including scaling laws for beam divergence, pro- pellant deposition on the extractor grid, and failure due to backstreaming current. The impact of uncertainty on performance and lifetime is also quantified. Sources of uncertainty considered include both physics-based model parameters and manufacturing tolerances A Monte Carlo analysis is applied to generate probability distribution functions for key per- formance parameters including thrust, efficiency, and specific impulse. The median perfor- mance values are shown to agree qualitatively with typical performance conditions for this pressure-fed configuration of an electrospray array. Probability of failure curves are also generated for both a single emitter and an array of emitters operated on the same power supply. It is found that as the uncertainty in design parameters or the number of emitters increases, the lifetime of the array decreases. Parametric analyses are also performed with the goal to optimize thruster performance while accounting for uncertainty. To this end, it is shown that there is an optimum throttling point for achieving maximum predicted total impulse. This proof of concept thus illustrates the potential capability of this approach for guiding design and optimization. |
Wildey, T; Gorodetsky, Alex; Belme, A C; Shadid, John N Robust uncertainty quantification using response surface approximations of discontinuous functions Journal Article Forthcoming Forthcoming. Abstract | Links | BibTeX | Tags: Support Vector Machines, Surrogate models, Uncertainty Quantification @article{Wildey2019, title = {Robust uncertainty quantification using response surface approximations of discontinuous functions}, author = {T. Wildey and Alex Gorodetsky and A.C. Belme and John N. Shadid}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2019/04/robust_UQ_discontinuous_surrogate.pdf doi:10.1615/Int.J.UncertaintyQuantification.2019026974}, year = {2019}, date = {2019-04-30}, abstract = {This paper considers response surface approximations for discontinuous quantities of interest. Our objective is not to adaptively characterize the interface defining the discontinuity. Instead, we utilize an epistemic description of the uncertainty in the location of a discontinuity to produce robust bounds on sample-based estimates of probabilistic quantities of interest. We demonstrate that two common machine learning strategies for classification, one based on nearest neighbors (Voronoi cells) and one based on support vector machines, provide reasonable descriptions of the region where the discontinuity may reside. In higher dimensional spaces, we demonstrate that support vector machines are more accurate for discontinuities defined by smooth interfaces. We also show how gradient information, often available via adjoint-based approaches, can be used to define indicators to effectively detect a discontinuity and to decompose the samples into clusters using an unsupervised learning technique. Numerical results demonstrate the epistemic bounds on probabilistic quantities of interest for simplistic models and for a compressible fluid model with a shock-induced discontinuity.}, keywords = {Support Vector Machines, Surrogate models, Uncertainty Quantification}, pubstate = {forthcoming}, tppubtype = {article} } This paper considers response surface approximations for discontinuous quantities of interest. Our objective is not to adaptively characterize the interface defining the discontinuity. Instead, we utilize an epistemic description of the uncertainty in the location of a discontinuity to produce robust bounds on sample-based estimates of probabilistic quantities of interest. We demonstrate that two common machine learning strategies for classification, one based on nearest neighbors (Voronoi cells) and one based on support vector machines, provide reasonable descriptions of the region where the discontinuity may reside. In higher dimensional spaces, we demonstrate that support vector machines are more accurate for discontinuities defined by smooth interfaces. We also show how gradient information, often available via adjoint-based approaches, can be used to define indicators to effectively detect a discontinuity and to decompose the samples into clusters using an unsupervised learning technique. Numerical results demonstrate the epistemic bounds on probabilistic quantities of interest for simplistic models and for a compressible fluid model with a shock-induced discontinuity. |
Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef A Continuous Analogue of the Tensor-Train Decomposition Journal Article Computer Methods in Applied Mechanics and Engineering, 347 , pp. 59-84, 2019. Abstract | Links | BibTeX | Tags: Chebfun, Low-rank approximation, Polynomial Approximation, Surrogate models, Tensor decompositions, Tensor-train decomposition, Uncertainty Quantification @article{Gorodetsky2018d, title = {A Continuous Analogue of the Tensor-Train Decomposition}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/12/ftrain.pdf }, doi = {10.1016/j.cma.2018.12.015}, year = {2019}, date = {2019-04-15}, journal = {Computer Methods in Applied Mechanics and Engineering}, volume = {347}, pages = {59-84}, abstract = {We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. The FT represents functions using a tensor-train ansatz by replacing the three-dimensional TT cores with univariate matrix-valued functions. The main contribution of this paper is a framework to compute the FT that employs adaptive approximations of univariate fibers, and that is not tied to any tensorized discretization. The algorithm can be coupled with any univariate linear or nonlinear approximation procedure. We demonstrate that this approach can generate multivariate function approximations that are several orders of magnitude more accurate, for the same cost, than those based on the conventional approach of compressing the coefficient tensor of a tensor-product basis. Our approach is in the spirit of other continuous computation packages such as Chebfun, and yields an algorithm which requires the computation of âcontinuousâ matrix factorizations such as the LU and QR decompositions of vector-valued functions. To support these developments, we describe continuous versions of an approximate maximum-volume cross approximation algorithm and of a rounding algorithm that re-approximates an FT by one of lower ranks. We demonstrate that our technique improves accuracy and robustness, compared to TT and quantics-TT approaches with fixed parameterizations, of high-dimensional integration, differentiation, and approximation of functions with local features such as discontinuities and other nonlinearities.}, keywords = {Chebfun, Low-rank approximation, Polynomial Approximation, Surrogate models, Tensor decompositions, Tensor-train decomposition, Uncertainty Quantification}, pubstate = {published}, tppubtype = {article} } We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. The FT represents functions using a tensor-train ansatz by replacing the three-dimensional TT cores with univariate matrix-valued functions. The main contribution of this paper is a framework to compute the FT that employs adaptive approximations of univariate fibers, and that is not tied to any tensorized discretization. The algorithm can be coupled with any univariate linear or nonlinear approximation procedure. We demonstrate that this approach can generate multivariate function approximations that are several orders of magnitude more accurate, for the same cost, than those based on the conventional approach of compressing the coefficient tensor of a tensor-product basis. Our approach is in the spirit of other continuous computation packages such as Chebfun, and yields an algorithm which requires the computation of âcontinuousâ matrix factorizations such as the LU and QR decompositions of vector-valued functions. To support these developments, we describe continuous versions of an approximate maximum-volume cross approximation algorithm and of a rounding algorithm that re-approximates an FT by one of lower ranks. We demonstrate that our technique improves accuracy and robustness, compared to TT and quantics-TT approaches with fixed parameterizations, of high-dimensional integration, differentiation, and approximation of functions with local features such as discontinuities and other nonlinearities. |
Geraci, Gianluca; Eldred, Michael S; Gorodetsky, Alex; Jakeman, John AIAA Scitech 2019 Forum, 2019. Abstract | Links | BibTeX | Tags: Bayesian Networks, Control Variates, Multifidelity Methods, Uncertainty Quantification @conference{Geraci2019AIAAb, title = {Recent advancements in Multilevel-Multifidelity techniques for forward UQ in the DARPA Sequoia project}, author = {Gianluca Geraci and Michael S. Eldred and Alex Gorodetsky and John Jakeman}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2019/04/geraci_et_al_aiaa_scitech_2019.pdf}, doi = {10.2514/6.2019-0722}, year = {2019}, date = {2019-01-01}, booktitle = {AIAA Scitech 2019 Forum}, abstract = { In the context of the DARPA funded project SEQUOIA we are interested in the design under uncertainty of a jet engine nozzle subject to the performance requirements of a reconnaissance mission for a small unmanned military aircraft. This design task involves complex and expensive aero-thermo-structural computational analyses where it is of a paramount importance to also include the effect of the uncertain variables to obtain reliable predictions of the device's performance. In this work we focus on the forward propagation analysis which is a key part of the design under uncertainty workflow. This task cannot be tackled directly by means of single fidelity approaches due to the prohibitive computational cost associated to each realization. We report here a summary of our latest advancement regarding several multilevel and multifidelity strategies designed to alleviate these challenges. The overall goal of these techniques is to reduce the computational cost of analyzing a high-fidelity model by resorting to less accurate, but less computationally demanding, lower fidelity models. The features of these multifidelity UQ approaches are initially illustrated and demonstrated on several model problems and afterward for the aero-thermo-structural analysis of the jet engine nozzle.}, keywords = {Bayesian Networks, Control Variates, Multifidelity Methods, Uncertainty Quantification}, pubstate = {published}, tppubtype = {conference} } In the context of the DARPA funded project SEQUOIA we are interested in the design under uncertainty of a jet engine nozzle subject to the performance requirements of a reconnaissance mission for a small unmanned military aircraft. This design task involves complex and expensive aero-thermo-structural computational analyses where it is of a paramount importance to also include the effect of the uncertain variables to obtain reliable predictions of the device's performance. In this work we focus on the forward propagation analysis which is a key part of the design under uncertainty workflow. This task cannot be tackled directly by means of single fidelity approaches due to the prohibitive computational cost associated to each realization. We report here a summary of our latest advancement regarding several multilevel and multifidelity strategies designed to alleviate these challenges. The overall goal of these techniques is to reduce the computational cost of analyzing a high-fidelity model by resorting to less accurate, but less computationally demanding, lower fidelity models. The features of these multifidelity UQ approaches are initially illustrated and demonstrated on several model problems and afterward for the aero-thermo-structural analysis of the jet engine nozzle. |
2018 |
Gorodetsky, Alex; Geraci, Gianluca; Eldred, Michael S; Jakeman, John A Generalized Approximate Control Variate Framework for Multifidelity Uncertainty Quantification Journal Article Forthcoming Preprint, Forthcoming. Abstract | Links | BibTeX | Tags: Monte Carlo Sampling, Multifidelity Methods, Uncertainty Quantification @article{Gorodetsky2018c, title = {A Generalized Approximate Control Variate Framework for Multifidelity Uncertainty Quantification}, author = {Alex Gorodetsky and Gianluca Geraci and Michael S. Eldred and John Jakeman}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2019/06/acv_mf_uq_2.pdf}, year = {2018}, date = {2018-11-12}, journal = {Preprint}, abstract = {We describe and analyze a Monte Carlo (MC) sampling framework for accelerating the estimation of statistics of computationally expensive simulation models using an ensemble of models with lower cost. Our approach uses control variates, with unknown means that must be estimated from data, to reduce the variance in statistical estimators relative to MC. Our framework unifies existing multi-level, multi-index, and multi-fidelity MC algorithms and leads to new and more efficient sampling schemes. Our results indicate that the variance reduction achieved by existing algorithms that explicitly or implicitly estimate control means, such as multilevel MC and multifidelity MC, is limited to that of a single linear control variate with known mean regardless of the number of control variates. We show how to circumvent this limitation and derive a new family of schemes that make full use of all available information sources. In particular, we demonstrate that a significant gap can exist, of orders of magnitude in some cases, between the variance reduction achievable by current %recursive schemes and our generalized schemes. We also present initial sample allocation approaches for exploiting this gap, which yield the greatest benefit when augmenting the high-fidelity model evaluations is impractical because, for instance, they arise from a legacy database. Several analytic examples and two PDE problems (viscous Burger's and steady state diffusion) are considered to demonstrate the methodology.}, keywords = {Monte Carlo Sampling, Multifidelity Methods, Uncertainty Quantification}, pubstate = {forthcoming}, tppubtype = {article} } We describe and analyze a Monte Carlo (MC) sampling framework for accelerating the estimation of statistics of computationally expensive simulation models using an ensemble of models with lower cost. Our approach uses control variates, with unknown means that must be estimated from data, to reduce the variance in statistical estimators relative to MC. Our framework unifies existing multi-level, multi-index, and multi-fidelity MC algorithms and leads to new and more efficient sampling schemes. Our results indicate that the variance reduction achieved by existing algorithms that explicitly or implicitly estimate control means, such as multilevel MC and multifidelity MC, is limited to that of a single linear control variate with known mean regardless of the number of control variates. We show how to circumvent this limitation and derive a new family of schemes that make full use of all available information sources. In particular, we demonstrate that a significant gap can exist, of orders of magnitude in some cases, between the variance reduction achievable by current %recursive schemes and our generalized schemes. We also present initial sample allocation approaches for exploiting this gap, which yield the greatest benefit when augmenting the high-fidelity model evaluations is impractical because, for instance, they arise from a legacy database. Several analytic examples and two PDE problems (viscous Burger's and steady state diffusion) are considered to demonstrate the methodology. |
Tal, Ezra; Gorodetsky, Alex; Karaman, Sertac Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games Inproceedings Forthcoming American Control Conference (ACC), Milwaukee, WI, Forthcoming. Abstract | Links | BibTeX | Tags: Differential Games, Stochastic Optimal Control, Tensor decompositions @inproceedings{Tal2018, title = {Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games}, author = {Ezra Tal and Alex Gorodetsky and Sertac Karaman}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/03/tal-ea-ACC2018.pdf}, year = {2018}, date = {2018-06-28}, booktitle = {American Control Conference (ACC)}, address = {Milwaukee, WI}, abstract = {Zero-sum differential games are a prominent research topic in a wide variety of fields ranging from motion planning under adversarial conditions to economics modeling. In the field of robust control, synthesis using game theory can also be used to obtain performance guarantees. However, most existing computational methods for differential games suffer from the curse of dimensionality, i.e., the computational requirements grow exponentially with the dimensionality of the state space. In the present work, we aim to alleviate the curse of dimensionality with a novel dynamic-programming-based algorithm that uses a continuous tensor-train approximation to represent the value function. This approximation method can represent and compute with high-dimensional tensors using computational resources that grow polynomially with dimensionality and polynomially with the rank of the value function. The proposed algorithm is shown to converge to optimal solutions with arbitrary bounds for a general class of differential games. The new algorithm is demonstrated using several game scenarios, achieving more than five orders of magnitude savings in memory and three order of magnitude in computational cost in a six-dimensional problem, when compared to the standard value iteration.}, keywords = {Differential Games, Stochastic Optimal Control, Tensor decompositions}, pubstate = {forthcoming}, tppubtype = {inproceedings} } Zero-sum differential games are a prominent research topic in a wide variety of fields ranging from motion planning under adversarial conditions to economics modeling. In the field of robust control, synthesis using game theory can also be used to obtain performance guarantees. However, most existing computational methods for differential games suffer from the curse of dimensionality, i.e., the computational requirements grow exponentially with the dimensionality of the state space. In the present work, we aim to alleviate the curse of dimensionality with a novel dynamic-programming-based algorithm that uses a continuous tensor-train approximation to represent the value function. This approximation method can represent and compute with high-dimensional tensors using computational resources that grow polynomially with dimensionality and polynomially with the rank of the value function. The proposed algorithm is shown to converge to optimal solutions with arbitrary bounds for a general class of differential games. The new algorithm is demonstrated using several game scenarios, achieving more than five orders of magnitude savings in memory and three order of magnitude in computational cost in a six-dimensional problem, when compared to the standard value iteration. |
Geraci, Gianluca; Eldred, Michael S; Gorodetsky, Alex; Jakeman, John Leveraging active subspaces for efficient multifidelity uncertainty quantification Inproceedings Forthcoming ECCM-ECCFD, Glasgow, Scotland, UK, 2018 Forthcoming. Abstract | Links | BibTeX | Tags: Active Subspace, Multifidelity Methods, Uncertainty Quantification @inproceedings{Geraci2018AS, title = {Leveraging active subspaces for efficient multifidelity uncertainty quantification}, author = {Gianluca Geraci and Michael S. Eldred and Alex Gorodetsky and John Jakeman}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/06/geraci_as_eccomas.pdf}, year = {2018}, date = {2018-06-12}, organization = {ECCM-ECCFD, Glasgow, Scotland, UK, 2018}, abstract = {In this work, we focus on sampling-based methods for forward uncertainty propagation, and in particular, on multifidelity sampling methods that employ a control variate approach. The novel component of this work is to accelerate the sampling by relying on important directions, as for instance in Active Subspaces. The idea consists of discovering the important directions for each model in order to provide a reduced dimensional link between the parameterization of each model fidelity and the relevant quantities of interest. This accomplishes two goals: (i) enhancing the correlation between models, and (ii) providing a mechanism to effectively bridge dissimilar input parameterizations. We demonstrate the performance of our approach for two model problems.}, keywords = {Active Subspace, Multifidelity Methods, Uncertainty Quantification}, pubstate = {forthcoming}, tppubtype = {inproceedings} } In this work, we focus on sampling-based methods for forward uncertainty propagation, and in particular, on multifidelity sampling methods that employ a control variate approach. The novel component of this work is to accelerate the sampling by relying on important directions, as for instance in Active Subspaces. The idea consists of discovering the important directions for each model in order to provide a reduced dimensional link between the parameterization of each model fidelity and the relevant quantities of interest. This accomplishes two goals: (i) enhancing the correlation between models, and (ii) providing a mechanism to effectively bridge dissimilar input parameterizations. We demonstrate the performance of our approach for two model problems. |
Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions Journal Article International Journal of Robotics Research, 37 (2-3), pp. 340-377, 2018. Abstract | Links | BibTeX | Tags: Dynamic Programming, Markov Decision Processes, Stochastic Optimal Control, Tensor decompositions @article{Gorodetsky2018, title = {High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/1611.04706.pdf}, doi = {10.1177/0278364917753994}, year = {2018}, date = {2018-03-19}, journal = {International Journal of Robotics Research}, volume = {37}, number = {2-3}, pages = {340-377}, abstract = {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: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g., the value function) in a compressed format, and directly perform dynamic programming computations (e.g., value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in "compressible" problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to ten orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture.}, keywords = {Dynamic Programming, Markov Decision Processes, Stochastic Optimal Control, Tensor decompositions}, pubstate = {published}, tppubtype = {article} } 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: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g., the value function) in a compressed format, and directly perform dynamic programming computations (e.g., value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in "compressible" problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to ten orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture. |
Kramer, Boris; Gorodetsky, Alex System identification via CUR-factored Hankel approximation Journal Article SIAM Journal on Scientific Computing, 40 (2), pp. A848–A866, 2018, ISSN: 1095-7197. Abstract | Links | BibTeX | Tags: Low-rank approximation, model reduction, System Identification @article{Kramer2018, title = {System identification via CUR-factored Hankel approximation}, author = {Boris Kramer and Alex Gorodetsky}, url = {http://www.alexgorodetsky.com/wp-content/uploads/2018/06/sisc_cur_sysid.pdf}, doi = {10.1137/17M1137632}, issn = {1095-7197}, year = {2018}, date = {2018-03-15}, journal = {SIAM Journal on Scientific Computing}, volume = {40}, number = {2}, pages = {A848–A866}, abstract = {Subspace-based system identification for dynamical systems is a sound, system-theoretic way to obtain linear, time-invariant system models from data. The interplay of data and systems theory is reflected in the Hankel matrix, a block-structured matrix whose factorization is used for system identification. For systems with many inputs, many outputs, or large time-series of system-response data, established methods based on the singular value decomposition (SVD)---such as the eigensystem realization algorithm (ERA)---are prohibitively expensive. In this paper, we propose an algorithm to reduce the complexity of the ERA from cubic to linear, with respect to Hankel matrix size. Furthermore, our memory requirements scale at the same rate because we never require loading the entire Hankel matrix into memory. These reductions are realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation of the Hankel matrix. The CUR decomposition is obtained using a maximum-volume based cross approximation scheme that selects a small number rows and columns to form the row and column space of the approximation. We present a worst-case error bound for our resulting system identification algorithm, and we demonstrate its computational advantages and accuracy on a numerical example. The example demonstrates that the resulting identification yields almost indistinguishable results compared with the SVD-based ERA, yet comes with significant computational savings.}, keywords = {Low-rank approximation, model reduction, System Identification}, pubstate = {published}, tppubtype = {article} } Subspace-based system identification for dynamical systems is a sound, system-theoretic way to obtain linear, time-invariant system models from data. The interplay of data and systems theory is reflected in the Hankel matrix, a block-structured matrix whose factorization is used for system identification. For systems with many inputs, many outputs, or large time-series of system-response data, established methods based on the singular value decomposition (SVD)---such as the eigensystem realization algorithm (ERA)---are prohibitively expensive. In this paper, we propose an algorithm to reduce the complexity of the ERA from cubic to linear, with respect to Hankel matrix size. Furthermore, our memory requirements scale at the same rate because we never require loading the entire Hankel matrix into memory. These reductions are realized by replacing the SVD with a CUR decomposition that directly seeks a low-rank approximation of the Hankel matrix. The CUR decomposition is obtained using a maximum-volume based cross approximation scheme that selects a small number rows and columns to form the row and column space of the approximation. We present a worst-case error bound for our resulting system identification algorithm, and we demonstrate its computational advantages and accuracy on a numerical example. The example demonstrates that the resulting identification yields almost indistinguishable results compared with the SVD-based ERA, yet comes with significant computational savings. |
Eldred, Michael S; Geraci, Gianluca; Gorodetsky, Alex; Jakeman, John Multilevel-Multifidelity Approaches for Forward UQ in the DARPA SEQUOIA project Inproceedings 2018 AIAA Non-Deterministic Approaches Conference, AIAA SciTech Forum, Kissimmee, Florida, 2018. Abstract | Links | BibTeX | Tags: Multifidelity Methods, Polynomial Approximation, Surrogate models, Tensor decompositions @inproceedings{Eldred2018, title = {Multilevel-Multifidelity Approaches for Forward UQ in the DARPA SEQUOIA project}, author = {Michael S. Eldred and Gianluca Geraci and Alex Gorodetsky and John Jakeman}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/main-1.pdf}, doi = {10.2514/6.2018-1179 }, year = {2018}, date = {2018-01-08}, booktitle = {2018 AIAA Non-Deterministic Approaches Conference, AIAA SciTech Forum}, address = {Kissimmee, Florida}, abstract = {Within the SEQUOIA project, funded by the DARPA EQUiPS program, we pursue algorithmic approaches that enable comprehensive design under uncertainty, through in- clusion of aleatory/parametric and epistemic/model form uncertainties within scalable for- ward/inverse UQ approaches. These statistical methods are embedded within design pro- cesses that manage computational expense through active subspace, multilevel-multifidelity, and reduced-order modeling approximations. To demonstrate these methods, we focus on the design of devices that involve multi-physics interactions in advanced aerospace vehicles. A particular problem of interest is the shape design of nozzles for advanced vehicles such as the Northrop Grumman UCAS X-47B, involving coupled aero-structural-thermal simu- lations for nozzle performance. In this paper, we explore a combination of multilevel and multifidelity forward and inverse UQ algorithms to reduce the overall computational cost of the analysis by leveraging hierarchies of model form (i.e., multifidelity hierarchies) and solution discretization (i.e., multilevel hierarchies) in order of exploit trade offs between solution accuracy and cost. In particular, we seek the most cost effective fusion of informa- tion across complex multi-dimensional modeling hierarchies. Results to date indicate the utility of multiple approaches, including methods that optimally allocate resources when estimator variance varies smoothly across levels, methods that allocate sufficient sampling density based on sparsity estimates, and methods that employ greedy multilevel refinement.}, keywords = {Multifidelity Methods, Polynomial Approximation, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {inproceedings} } Within the SEQUOIA project, funded by the DARPA EQUiPS program, we pursue algorithmic approaches that enable comprehensive design under uncertainty, through in- clusion of aleatory/parametric and epistemic/model form uncertainties within scalable for- ward/inverse UQ approaches. These statistical methods are embedded within design pro- cesses that manage computational expense through active subspace, multilevel-multifidelity, and reduced-order modeling approximations. To demonstrate these methods, we focus on the design of devices that involve multi-physics interactions in advanced aerospace vehicles. A particular problem of interest is the shape design of nozzles for advanced vehicles such as the Northrop Grumman UCAS X-47B, involving coupled aero-structural-thermal simu- lations for nozzle performance. In this paper, we explore a combination of multilevel and multifidelity forward and inverse UQ algorithms to reduce the overall computational cost of the analysis by leveraging hierarchies of model form (i.e., multifidelity hierarchies) and solution discretization (i.e., multilevel hierarchies) in order of exploit trade offs between solution accuracy and cost. In particular, we seek the most cost effective fusion of informa- tion across complex multi-dimensional modeling hierarchies. Results to date indicate the utility of multiple approaches, including methods that optimally allocate resources when estimator variance varies smoothly across levels, methods that allocate sufficient sampling density based on sparsity estimates, and methods that employ greedy multilevel refinement. |
Gorodetsky, Alex; Jakeman, John Gradient-based Optimization for Regression in the Functional Tensor-Train Format Journal Article Journal of Computational Physics, 374 , pp. 1219–1238, 2018. Abstract | Links | BibTeX | Tags: Regression, Surrogate models, Tensor decompositions @article{Gorodetsky2018b, title = {Gradient-based Optimization for Regression in the Functional Tensor-Train Format}, author = {Alex Gorodetsky and John Jakeman}, url = {https://arxiv.org/abs/1801.00885v2 https://www.sciencedirect.com/science/article/pii/S0021999118305321}, doi = {10.1016/j.jcp.2018.08.010}, year = {2018}, date = {2018-01-01}, journal = {Journal of Computational Physics}, volume = {374}, pages = {1219--1238}, abstract = {We consider the task of low-multilinear-rank functional regression, i.e., learning a low-rank parametric representation of functions from scattered real-valued data. Our first contribution is the development and analysis of an efficient gradient computation that enables gradient-based optimization procedures, including stochastic gradient descent and quasi-Newton methods, for learning the parameters of a functional tensor-train (FT). The functional tensor-train uses the tensor-train (TT) representation of low-rank arrays as an ansatz for a class of low-multilinear-rank functions. The FT is represented by a set of matrix-valued functions that contain a set of univariate functions, and the regression task is to learn the parameters of these univariate functions. Our second contribution demonstrates that using nonlinearly parameterized univariate functions, e.g., symmetric kernels with moving centers, within each core can outperform the standard approach of using a linear expansion of basis functions. Our final contributions are new rank adaptation and group-sparsity regularization procedures to minimize overfitting. We use several benchmark problems to demonstrate at least an order of magnitude lower accuracy with gradient-based optimization methods than standard alternating least squares procedures in the low-sample number regime. We also demonstrate an order of magnitude reduction in accuracy on a test problem resulting from using nonlinear parameterizations over linear parameterizations. Finally we compare regression performance with 22 other nonparametric and parametric regression methods on 10 real-world data sets. We achieve top-five accuracy for seven of the data sets and best accuracy for two of the data sets. These rankings are the best amongst parametric models and competetive with the best non-parametric methods.}, keywords = {Regression, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {article} } We consider the task of low-multilinear-rank functional regression, i.e., learning a low-rank parametric representation of functions from scattered real-valued data. Our first contribution is the development and analysis of an efficient gradient computation that enables gradient-based optimization procedures, including stochastic gradient descent and quasi-Newton methods, for learning the parameters of a functional tensor-train (FT). The functional tensor-train uses the tensor-train (TT) representation of low-rank arrays as an ansatz for a class of low-multilinear-rank functions. The FT is represented by a set of matrix-valued functions that contain a set of univariate functions, and the regression task is to learn the parameters of these univariate functions. Our second contribution demonstrates that using nonlinearly parameterized univariate functions, e.g., symmetric kernels with moving centers, within each core can outperform the standard approach of using a linear expansion of basis functions. Our final contributions are new rank adaptation and group-sparsity regularization procedures to minimize overfitting. We use several benchmark problems to demonstrate at least an order of magnitude lower accuracy with gradient-based optimization methods than standard alternating least squares procedures in the low-sample number regime. We also demonstrate an order of magnitude reduction in accuracy on a test problem resulting from using nonlinear parameterizations over linear parameterizations. Finally we compare regression performance with 22 other nonparametric and parametric regression methods on 10 real-world data sets. We achieve top-five accuracy for seven of the data sets and best accuracy for two of the data sets. These rankings are the best amongst parametric models and competetive with the best non-parametric methods. |
2017 |
Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef Low-rank tensor integration for Gaussian filtering of continuous time nonlinear systems Inproceedings 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 2789-2794, Melbourne, VIC, Australia, 2017, ISBN: 978-1-5090-2873-3. Abstract | Links | BibTeX | Tags: Dynamical Systems, Kalman Filtering, Tensor decompositions @inproceedings{Gorodetsky2017, title = {Low-rank tensor integration for Gaussian filtering of continuous time nonlinear systems}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/main.pdf}, doi = {10.1109/CDC.2017.8264064}, isbn = {978-1-5090-2873-3}, year = {2017}, date = {2017-12-12}, booktitle = {2017 IEEE 56th Annual Conference on Decision and Control (CDC)}, pages = {2789-2794}, address = {Melbourne, VIC, Australia}, abstract = {Integration-based Gaussian filters such as un-scented, cubature, and Gauss-Hermite filters are effective ways to assimilate data and models within nonlinear systems. Traditionally, these filters have only been applicable for systems with a handful of states due to stability and scalability issues. In this paper, we present a new integration method for scaling quadrature-based filters to higher dimensions. Our approach begins by decomposing the dynamics and observation models into separated, low-rank tensor formats. Once in low-rank tensor format, adaptive integration techniques may be used to efficiently propagate the mean and covariance of the distribution of the system state with computational complexity that is polynomial in dimension and rank. Simulation results are shown on nonlinear chaotic systems with 20 state variables.}, keywords = {Dynamical Systems, Kalman Filtering, Tensor decompositions}, pubstate = {published}, tppubtype = {inproceedings} } Integration-based Gaussian filters such as un-scented, cubature, and Gauss-Hermite filters are effective ways to assimilate data and models within nonlinear systems. Traditionally, these filters have only been applicable for systems with a handful of states due to stability and scalability issues. In this paper, we present a new integration method for scaling quadrature-based filters to higher dimensions. Our approach begins by decomposing the dynamics and observation models into separated, low-rank tensor formats. Once in low-rank tensor format, adaptive integration techniques may be used to efficiently propagate the mean and covariance of the distribution of the system state with computational complexity that is polynomial in dimension and rank. Simulation results are shown on nonlinear chaotic systems with 20 state variables. |
Gorodetsky, Alex Massachusetts Institute of Technology, 2017. Abstract | Links | BibTeX | Tags: Dynamic Programming, Kalman Filtering, Stochastic Optimal Control, Surrogate models, Tensor decompositions @phdthesis{Gorodetsky2017b, title = {Continuous low-rank tensor decompositions, with applications to stochastic optimal control and data assimilation}, author = {Alex Gorodetsky}, url = {http://hdl.handle.net/1721.1/108918}, year = {2017}, date = {2017-02-02}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, abstract = {Optimal decision making under uncertainty is critical for control and optimization of complex systems. However, many techniques for solving problems such as stochastic optimal control and data assimilation encounter the curse of dimensionality when too many state variables are involved. In this thesis, we propose a framework for computing with high-dimensional functions that mitigates this exponential growth in complexity for problems with separable structure. Our framework tightly integrates two emerging areas: tensor decompositions and continuous computation. Tensor decompositions are able to effectively compress and operate with low-rank multidimensional arrays. Continuous computation is a paradigm for computing with functions instead of arrays, and it is best realized by Chebfun, a MATLAB package for computing with functions of up to three dimensions. Continuous computation provides a natural framework for building numerical algorithms that effectively, naturally, and automatically adapt to problem structure. The first part of this thesis describes a compressed continuous computation framework centered around a continuous analogue to the (discrete) tensor-train decomposition called the function-train decomposition. Computation with the function-train requires continuous matrix factorizations and continuous numerical linear algebra. Continuous analogues are presented for performing cross approximation; rounding; multilinear algebra operations such as addition, multiplication, integration, and differentiation; and continuous, rank-revealing, alternating least squares. Advantages of the function-train over the tensor-train include the ability to adaptively approximate functions and the ability to compute with functions that are parameterized differently. For example, while elementwise multiplication between tensors of different sizes is undefined, functions in FT format can be readily multiplied together. Next, we develop compressed versions of value iteration, policy iteration, and multilevel algorithms for solving dynamic programming problems arising in stochastic optimal control. These techniques enable computing global solutions to a broader set of problems, for example those with non-affine control inputs, than previously possible. Examples are presented for motion planning with robotic systems that have up to seven states. Finally, we use the FT to extend integration-based Gaussian filtering to larger state spaces than previously considered. Examples are presented for dynamical systems with up to twenty states.}, keywords = {Dynamic Programming, Kalman Filtering, Stochastic Optimal Control, Surrogate models, Tensor decompositions}, pubstate = {published}, tppubtype = {phdthesis} } Optimal decision making under uncertainty is critical for control and optimization of complex systems. However, many techniques for solving problems such as stochastic optimal control and data assimilation encounter the curse of dimensionality when too many state variables are involved. In this thesis, we propose a framework for computing with high-dimensional functions that mitigates this exponential growth in complexity for problems with separable structure. Our framework tightly integrates two emerging areas: tensor decompositions and continuous computation. Tensor decompositions are able to effectively compress and operate with low-rank multidimensional arrays. Continuous computation is a paradigm for computing with functions instead of arrays, and it is best realized by Chebfun, a MATLAB package for computing with functions of up to three dimensions. Continuous computation provides a natural framework for building numerical algorithms that effectively, naturally, and automatically adapt to problem structure. The first part of this thesis describes a compressed continuous computation framework centered around a continuous analogue to the (discrete) tensor-train decomposition called the function-train decomposition. Computation with the function-train requires continuous matrix factorizations and continuous numerical linear algebra. Continuous analogues are presented for performing cross approximation; rounding; multilinear algebra operations such as addition, multiplication, integration, and differentiation; and continuous, rank-revealing, alternating least squares. Advantages of the function-train over the tensor-train include the ability to adaptively approximate functions and the ability to compute with functions that are parameterized differently. For example, while elementwise multiplication between tensors of different sizes is undefined, functions in FT format can be readily multiplied together. Next, we develop compressed versions of value iteration, policy iteration, and multilevel algorithms for solving dynamic programming problems arising in stochastic optimal control. These techniques enable computing global solutions to a broader set of problems, for example those with non-affine control inputs, than previously possible. Examples are presented for motion planning with robotic systems that have up to seven states. Finally, we use the FT to extend integration-based Gaussian filtering to larger state spaces than previously considered. Examples are presented for dynamical systems with up to twenty states. |
2016 |
Alora, John Irvin; Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef; Lowry, Nathan Automated synthesis of low-rank control systems from sc-LTL specifications using tensor-train decompositions Inproceedings 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1131-1138, Las Vegas, NV, USA, 2016, ISBN: 978-1-5090-1837-6. Abstract | Links | BibTeX | Tags: Linear Temporal Logic, Stochastic Optimal Control, Tensor decompositions @inproceedings{Alora2016, title = {Automated synthesis of low-rank control systems from sc-LTL specifications using tensor-train decompositions}, author = {John Irvin Alora and Alex Gorodetsky and Sertac Karaman and Youssef Marzouk and Nathan Lowry}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/Alora.Gorodetsky.ea_.CDC16.pdf}, doi = {10.1109/CDC.2016.7798419}, isbn = {978-1-5090-1837-6}, year = {2016}, date = {2016-12-12}, booktitle = {2016 IEEE 55th Conference on Decision and Control (CDC)}, pages = {1131-1138}, address = {Las Vegas, NV, USA}, abstract = {Correct-by-design automated construction of control systems has attracted a tremendous amount of attention. However, most existing algorithms for automated construction suffer from the curse of dimensionality, i.e., their run time scales exponentially with increasing dimensionality of the state space. As a result, typically, systems with only a few degrees of freedom are considered. In this paper, we propose a novel algorithm based on the tensor-train decomposition that solves stochastic optimal control problems with syntactically co-safe linear temporal logic specifications. We show that, under certain conditions, the run time of the proposed algorithm scales polynomially with the dimensionality of the state space and the rank of the optimal cost-to-go function. We demonstrate the algorithm in a six-dimensional problem instance involving a simple airplane model. In this example, the proposed algorithm provides up to four orders of computational savings when compared to the standard value iteration algorithm.}, keywords = {Linear Temporal Logic, Stochastic Optimal Control, Tensor decompositions}, pubstate = {published}, tppubtype = {inproceedings} } Correct-by-design automated construction of control systems has attracted a tremendous amount of attention. However, most existing algorithms for automated construction suffer from the curse of dimensionality, i.e., their run time scales exponentially with increasing dimensionality of the state space. As a result, typically, systems with only a few degrees of freedom are considered. In this paper, we propose a novel algorithm based on the tensor-train decomposition that solves stochastic optimal control problems with syntactically co-safe linear temporal logic specifications. We show that, under certain conditions, the run time of the proposed algorithm scales polynomially with the dimensionality of the state space and the rank of the optimal cost-to-go function. We demonstrate the algorithm in a six-dimensional problem instance involving a simple airplane model. In this example, the proposed algorithm provides up to four orders of computational savings when compared to the standard value iteration algorithm. |
Gorodetsky, Alex; Marzouk, Youssef Mercer Kernels and Integrated Variance Experimental Design: Connections Between Gaussian Process Regression and Polynomial Approximation Journal Article SIAM/ASA Journal of Uncertainty Quantification, 4 (1), pp. 796-828, 2016, ISSN: 2166-2525. Abstract | Links | BibTeX | Tags: Experimental Design, Gaussian Process Regression, Polynomial Approximation @article{Gorodetsky2016, title = {Mercer Kernels and Integrated Variance Experimental Design: Connections Between Gaussian Process Regression and Polynomial Approximation }, author = {Alex Gorodetsky and Youssef Marzouk}, doi = {10.1137/15M1017119}, issn = {2166-2525}, year = {2016}, date = {2016-07-21}, journal = {SIAM/ASA Journal of Uncertainty Quantification}, volume = {4}, number = {1}, pages = {796-828}, abstract = {This paper examines experimental design procedures used to develop surrogates of computational models, exploring the interplay between experimental designs and approximation algorithms. We focus on two widely used approximation approaches, Gaussian process (GP) regression and nonintrusive polynomial approximation. First, we introduce algorithms for minimizing a posterior integrated variance (IVAR) design criterion for GP regression. Our formulation treats design as a continuous optimization problem that can be solved with gradient-based methods on complex input domains without resorting to greedy approximations. We show that minimizing IVAR in this way yields point sets with good interpolation properties and that it enables more accurate GP regression than designs based on entropy minimization or mutual information maximization. Second, using a Mercer kernel/eigenfunction perspective on GP regression, we identify conditions under which GP regression coincides with pseudospectral polynomial approximation. Departures from these conditions can be understood as changes either to the kernel or to the experimental design itself. We then show how IVAR-optimal designs, while sacrificing discrete orthogonality of the kernel eigenfunctions, can yield lower approximation error than orthogonalizing point sets. Finally, we compare the performance of adaptive GP regression and adaptive pseudospectral approximation for several classes of target functions, identifying features that are favorable to the GP + IVAR approach.}, keywords = {Experimental Design, Gaussian Process Regression, Polynomial Approximation}, pubstate = {published}, tppubtype = {article} } This paper examines experimental design procedures used to develop surrogates of computational models, exploring the interplay between experimental designs and approximation algorithms. We focus on two widely used approximation approaches, Gaussian process (GP) regression and nonintrusive polynomial approximation. First, we introduce algorithms for minimizing a posterior integrated variance (IVAR) design criterion for GP regression. Our formulation treats design as a continuous optimization problem that can be solved with gradient-based methods on complex input domains without resorting to greedy approximations. We show that minimizing IVAR in this way yields point sets with good interpolation properties and that it enables more accurate GP regression than designs based on entropy minimization or mutual information maximization. Second, using a Mercer kernel/eigenfunction perspective on GP regression, we identify conditions under which GP regression coincides with pseudospectral polynomial approximation. Departures from these conditions can be understood as changes either to the kernel or to the experimental design itself. We then show how IVAR-optimal designs, while sacrificing discrete orthogonality of the kernel eigenfunctions, can yield lower approximation error than orthogonalizing point sets. Finally, we compare the performance of adaptive GP regression and adaptive pseudospectral approximation for several classes of target functions, identifying features that are favorable to the GP + IVAR approach. |
2015 |
Gorodetsky, Alex; Karaman, Sertac; Marzouk, Youssef Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition Inproceedings Proceedings of Robotics: Science and Systems, Rome, Italy, 2015. Abstract | Links | BibTeX | Tags: Dynamic Programming, Motion Planning, Stochastic Optimal Control, Tensor-train decomposition @inproceedings{Gorodetsky2015, title = {Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition}, author = {Alex Gorodetsky and Sertac Karaman and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/p15.pdf}, doi = {10.15607/RSS.2015.XI.015}, year = {2015}, date = {2015-07-01}, booktitle = {Proceedings of Robotics: Science and Systems}, address = {Rome, Italy}, abstract = {Stochastic optimal control problems frequently arise as motion control problems in the context of robotics. Unfortunately, all existing approaches that guarantee arbitrary precision suffer from the curse of dimensionality: the computational effort invested by the algorithm grows exponentially fast with increasing dimensionality of the state space of the underlying dynamic system governing the robot. In this paper, we propose a novel algorithm that utilizes compressed representations to efficiently solve stochastic optimal control problems with arbitrary precision. The running time of the new algorithms scale linearly with increasing dimensionality of the state space! The running time also depends polynomially on the rank of the value function, a measure that quantifies the intrinsic geometric complexity of the value function, due to the geometry and physics embedded in the problem instance at hand. The new algorithms are based on the recent analysis and algorithms for tensor decomposition, generalizing matrix decomposition algorithms, e.g., the singular value decomposition, to three or more dimensions. In computational experiments, we show the computational effort of the new algorithm also scales linearly with the discretization resolution of the state space. We also demonstrate the new algorithm on a problem involving the perching of an aircraft, represented by a nonlinear non-holonomic longitudinal model with a seven-dimensional state space, the full numerical solution to which was not obtained before. In this example, we estimate that the proposed algorithm runs more than seven orders of magnitude faster, when compared to the naive value iteration}, keywords = {Dynamic Programming, Motion Planning, Stochastic Optimal Control, Tensor-train decomposition}, pubstate = {published}, tppubtype = {inproceedings} } Stochastic optimal control problems frequently arise as motion control problems in the context of robotics. Unfortunately, all existing approaches that guarantee arbitrary precision suffer from the curse of dimensionality: the computational effort invested by the algorithm grows exponentially fast with increasing dimensionality of the state space of the underlying dynamic system governing the robot. In this paper, we propose a novel algorithm that utilizes compressed representations to efficiently solve stochastic optimal control problems with arbitrary precision. The running time of the new algorithms scale linearly with increasing dimensionality of the state space! The running time also depends polynomially on the rank of the value function, a measure that quantifies the intrinsic geometric complexity of the value function, due to the geometry and physics embedded in the problem instance at hand. The new algorithms are based on the recent analysis and algorithms for tensor decomposition, generalizing matrix decomposition algorithms, e.g., the singular value decomposition, to three or more dimensions. In computational experiments, we show the computational effort of the new algorithm also scales linearly with the discretization resolution of the state space. We also demonstrate the new algorithm on a problem involving the perching of an aircraft, represented by a nonlinear non-holonomic longitudinal model with a seven-dimensional state space, the full numerical solution to which was not obtained before. In this example, we estimate that the proposed algorithm runs more than seven orders of magnitude faster, when compared to the naive value iteration |
2014 |
Gorodetsky, Alex; Marzouk, Youssef Efficient Localization of Discontinuities in Complex Computational Simulations Journal Article SIAM Journal on Scientific Computing, 36 (6), pp. A2584-A2610, 2014, ISSN: 1095-7197. Abstract | Links | BibTeX | Tags: Active Learning, Support Vector Machines, Surrogate models @article{Gorodetsky2014, title = {Efficient Localization of Discontinuities in Complex Computational Simulations }, author = {Alex Gorodetsky and Youssef Marzouk}, url = {https://alexgorodetsky.com/wp-content/uploads/2018/02/discontinuity_detection.pdf}, doi = {10.1137/140953137}, issn = {1095-7197}, year = {2014}, date = {2014-11-04}, journal = {SIAM Journal on Scientific Computing}, volume = {36}, number = {6}, pages = {A2584-A2610}, abstract = {Surrogate models for computational simulations are input-output approximations that allow computationally intensive analyses, such as uncertainty propagation and inference, to be performed efficiently. When a simulation output does not depend smoothly on its inputs, the error and convergence rate of many approximation methods deteriorate substantially. This paper details a method for efficiently localizing discontinuities in the input parameter domain, so that the model output can be approximated as a piecewise smooth function. The approach comprises an initialization phase, which uses polynomial annihilation to assign function values to different regions and thus seed an automated labeling procedure, followed by a refinement phase that adaptively updates a kernel support vector machine representation of the separating surface via active learning. The overall approach avoids structured grids and exploits any available simplicity in the geometry of the separating surface, thus reducing the number of model evaluations required to localize the discontinuity. The method is illustrated on examples of up to eleven dimensions, including algebraic models and ODE/PDE systems, and demonstrates improved scaling and efficiency over other discontinuity localization approaches.}, keywords = {Active Learning, Support Vector Machines, Surrogate models}, pubstate = {published}, tppubtype = {article} } Surrogate models for computational simulations are input-output approximations that allow computationally intensive analyses, such as uncertainty propagation and inference, to be performed efficiently. When a simulation output does not depend smoothly on its inputs, the error and convergence rate of many approximation methods deteriorate substantially. This paper details a method for efficiently localizing discontinuities in the input parameter domain, so that the model output can be approximated as a piecewise smooth function. The approach comprises an initialization phase, which uses polynomial annihilation to assign function values to different regions and thus seed an automated labeling procedure, followed by a refinement phase that adaptively updates a kernel support vector machine representation of the separating surface via active learning. The overall approach avoids structured grids and exploits any available simplicity in the geometry of the separating surface, thus reducing the number of model evaluations required to localize the discontinuity. The method is illustrated on examples of up to eleven dimensions, including algebraic models and ODE/PDE systems, and demonstrates improved scaling and efficiency over other discontinuity localization approaches. |
0000 |
Geraci, Gianluca; Eldred, Michael S; Gorodetsky, Alex; Jakeman, John 0000. Abstract | Links | BibTeX | Tags: Control Variates, Graphical Models, Multifidelity Methods, Uncertainty Quantification @conference{Geraci2019AIAA, title = {Recent advancements in Multilevel-Multifidelity techniques for forward UQ in the DARPA Sequoia Project}, author = {Gianluca Geraci and Michael S. Eldred and Alex Gorodetsky and John Jakeman}, editor = {AIAA Scitech Forum}, url = {https://arc.aiaa.org/doi/abs/10.2514/6.2019-0722}, doi = {10.2514/6.2019-0722}, abstract = {n the context of the DARPA funded project SEQUOIA we are interested in the designunder uncertainty of a jet engine nozzle subject to the performance requirements of a recon-naissance mission for a small unmanned military aircraft. This design task involves complexand expensive aero-thermo-structural computational analyses where it is of a paramount im-portance to also include the effect of the uncertain variables to obtain reliable predictions ofthe device’s performance. In this work we focus on the forward propagation analysis which isa key part of the design under uncertainty workflow. This task cannot be tackled directly bymeans of single fidelity approaches due to the prohibitive computational cost associated to eachrealization. We report here a summary of our latest advancement regarding several multileveland multifidelity strategies designed to alleviate these challenges. The overall goal of thesetechniques is to reduce the computational cost of analyzing a high-fidelity model by resortingto less accurate, but less computationally demanding, lower fidelity models. The features ofthese multifidelity UQ approaches are initially illustrated and demonstrated on several modelproblems and afterward for the aero-thermo-structural analysis of the jet engine nozzle}, keywords = {Control Variates, Graphical Models, Multifidelity Methods, Uncertainty Quantification}, pubstate = {published}, tppubtype = {conference} } n the context of the DARPA funded project SEQUOIA we are interested in the designunder uncertainty of a jet engine nozzle subject to the performance requirements of a recon-naissance mission for a small unmanned military aircraft. This design task involves complexand expensive aero-thermo-structural computational analyses where it is of a paramount im-portance to also include the effect of the uncertain variables to obtain reliable predictions ofthe device’s performance. In this work we focus on the forward propagation analysis which isa key part of the design under uncertainty workflow. This task cannot be tackled directly bymeans of single fidelity approaches due to the prohibitive computational cost associated to eachrealization. We report here a summary of our latest advancement regarding several multileveland multifidelity strategies designed to alleviate these challenges. The overall goal of thesetechniques is to reduce the computational cost of analyzing a high-fidelity model by resortingto less accurate, but less computationally demanding, lower fidelity models. The features ofthese multifidelity UQ approaches are initially illustrated and demonstrated on several modelproblems and afterward for the aero-thermo-structural analysis of the jet engine nozzle |