Compression Algorithms for Enabling High-Dimensional Motion Planning

Autonomous systems that operate in real time pose unique challenges for reliable, accurate, and optimal uncertainty quantification and control. Many algorithms with strong optimality guarantees encounter the curse-of-dimensionality; their computational expense grows exponentially with the size of the state space. In this talk, we describe new developments in low-rank multilinear algebra that enable foundational algorithms within autonomy for high-dimensional systems. We demonstrate how compression techniques based on a continuous extension of tensor decompositions can be used to solve Markov decisions processes (MDPs) that arise in systems described by stochastic differential equations. The resulting dynamic programming algorithms scale polynomially with dimension with guaranteed convergence. Applications to stochastic optimal control, differential games, and linear temporal logic are discussed. Experimental results are shown for an agile quadcopter system, where we achieve 7 orders of magnitude compression of a discretized space with $10^12$ states. Finally, new research directions aimed towards embedding such schemes for online learning are described.

Alex Gorodetsky is an Assistant Professor in Aerospace Engineering at the University of Michigan. His research interests include using applied mathematics and computational science to enable autonomous decision making under uncertainty. He is especially interested in controlling systems that must act in complex environments that can be simulated using a large amount of computational resources. Toward this goal, he pursues research in wide-ranging areas including uncertainty quantification, statistical inference and machine learning, numerical analysis, function approximation, control, and optimization.
Prior to returning to the University of Michigan, Alex was the John von Neumann Postdoctoral Research Fellow at Sandia National Laboratories in Albuquerque, New Mexico. At Sandia, Alex worked in the Optimization and Uncertainty Quantification Group on algorithms for propagating uncertainty through complex physical systems. Alex completed his Ph.D. (2016) and S.M. (2012) in the Department of Aeronautics and Astronautics at the Massachusetts Institute of Technology, where he worked on algorithms for stochastic optimal control and estimation in dynamical systems. He received his B.S.E (2010) in Aerospace Engineering from the University of Michigan.