Stochastic Optimization for Autonomous Navigation, Leveraging Parallel Computation

Abstract

Stochastic Optimal Control (SOC) is a framework that allows disturbances and uncertainty in system models to be accounted for in its optimization framework. Despite accounting for this uncertainty, many first and second order methods for solving SOC problems are subject to local minima and are most appropriate for solving convex problems. Another class of SOC solvers, sample-based optimal controllers, are able to sample widely over the control space and thus see into various convex regions of the cost landscape, avoiding local minima. However, these methods suffer from issues of computational tractability and the curse of dimensionality. A common method to mitigate this issue is to use importance sampling to ensure the samples are focused in regions that most inform the solver. As such, much of the research in this area seeks to understand performance as a function of this sampling - and how to modify the sampling distribution to achieve better performance. To deepen our understanding of these methods we instead explore their computational aspects.

Specifically, we implement the Model Predictive Path Integral (MPPI), and Cross-Entropy-Method (CEM) algorithms in an extensible controls framework and benchmark them on a navigation task. We then evaluate common navigation performance metrics as a function of the number of particles. We also evaluate how quickly the algorithms are able to run using sequential evaluation, a threadpool parallelization backend, and a GPU parallelization backend.

Additionally, we propose a framework for interoperable parallelization in C++. Allowing the same C++ code to be parallelized on a CPU or on an NVIDIA GPU device with clean high-level interfaces and data structures C++ programmers are accustomed to. We discuss the utility of this framework in developing parallelized sampling-based algorithms in C++, and compare this work with another modern multiprocessing framework - thrust.