Parallel and Constrained Differential Dynamic Programming for Model Predictive Control

Abstract

Differential Dynamic Programming (DDP) has become a popular approach to performing trajectory optimization for complex, underactuated robots. However, using DDP in dynamic environments presents three practical challenges. First, the evaluation of dynamics derivatives during optimization creates a computational bottleneck, particularly in implementations that capture second-order dynamic effects. Second, constraints on the states (e.g., boundary conditions, collision constraints) require additional care since the state trajectory is implicitly defined from the inputs and dynamics. Third, computing solutions fast enough for online robotic motion planning can be challenging. This thesis addresses these problems by first building on recent work on Unscented Dynamic Programming (UDP)—which eliminates dynamics derivative computations in DDP—to support general nonlinear state and input constraints to high precision using an augmented Lagrangian. We then leverage parallel computations for increased throughput and systematically analyze the insights, challenges, tradeoffs, and benefits of implementing a parallelized variant of DDP on both a multi-core CPU and a graphics processing unit (GPU). Finally, we present results demonstrating the performance of our constrained UDP (CUDP) and parallel DDP algorithms on several simulated robot systems including a quadrotor and a 7-DoF robotic arm.