## 2018 |

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. |

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. |

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 Forthcoming Arxiv 1801.00885v2 (Accepted Journal of Computational Physics), Forthcoming. 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}, year = {2018}, date = {2018-01-01}, journal = {Arxiv 1801.00885v2 (Accepted Journal of Computational Physics)}, 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 = {forthcoming}, 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. |