Séminaire de Mécanique d'Orsay

Le Jeudi 20 juin 2019 à 14h00 - Salle de conférences du LIMSI

Compression algorithms for enabling high-dimensional motion planning

Alex Gorodetsky
Dpt. Aerospace Eng. Univ. Michigan, USA

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.

Accès Salle de conférences du LIMSI