Parameterized Differential Dynamic Programming

Authors: Alex Oshin, Matthew D. Houghton, Michael J. Acheson, Irene M. Gregory, Evangelos A. Theodorou · RSS 2022

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

PDDP adds time-invariant parameters to DDP so controls and parameters get joint second-order updates, used for online model identification in MPC and for timing flight-mode switches.

Why it matters

A single second-order solver can identify model parameters online while controlling the system, and can choose how long a hybrid system spends in each mode. The paper reports, to the authors' knowledge, the first use of switching-time optimization to plan transitions between flight regimes, applied to NASA's Lift+Cruise VTOL concept.

Problem

Many robot planning problems involve unknown or tunable time-invariant parameters, such as a payload mass or the time spent in each mode of a hybrid system. Earlier DDP-based approaches updated such parameters through the trajectory's initial condition, which shifts the whole nominal trajectory and hurts convergence. Hybrid-systems trajectory optimization has also mostly targeted legged robots with reduced models, with little work on aircraft such as urban air mobility vehicles that switch between hover, transition and cruise.

Proposed solution

The authors write a general optimal control objective in which parameters enter both the dynamics and the cost, and derive Parameterized DDP: the backward pass expands the value function in state and parameters, giving control gains, a parameter feedforward update and a feedback term that keeps controls stable when parameters change. They prove convergence to a stationary point from any initialization under a line-search condition and regularization, and compare updating controls and parameters simultaneously, alternately, or only after the controls converge (STO-DDP). The same algorithm is applied to moving horizon estimation run alongside MPC, and to switching-time optimization with a fixed number of steps per mode, sub-stepped integration and a projected Newton solver that keeps time scales nonnegative.

Key insights

Treating parameters explicitly inside the dynamics and cost, instead of through the initial state, gives second-order joint updates of controls and parameters regardless of how the parameters are defined.
Alternating between control updates and parameter updates escaped local minima better than updating both at once or waiting for the controls to converge.
Combining moving horizon estimation with MPC lets the controller correct a badly wrong model within a few steps and then reach the goal.
For switching-time problems, keeping the number of timesteps per mode constant and integrating with smaller substeps preserves the convergence properties and avoids numerical failure.

Main results

Quadrotor MHE+MPC: mass and inertia estimates went from initial guesses of 1 kg and 1 kg·m² to the true 0.468 kg and 4.856×10⁻³ / 8.801×10⁻³ kg·m² within 15 MHE steps (under 0.2 s of execution time); the vehicle then reached its target in 3 s total.
Ant quadruped (Brax physics, 117-dimensional state): leg lengths went from 1.0 m and 2.0 m to the true 0.443 m and 0.726 m within 4 MHE steps.
Cartpole: pole mass estimated correctly (true 0.5 kg from an initial 2 kg) within 50 steps once the pole began to move; little progress was made in the first 15 steps.
Multi-target cartpole switching-time task, 1000 random initializations: the alternating scheme reached a cost about half an order of magnitude lower on average than the simultaneous scheme and STO-DDP.
NASA Lift+Cruise (500 initializations): a time-optimal vertical takeoff of 5.63 s followed by 9.79 s to reach cruise speed; the reverse manoeuvre slowed from cruise to hover within 500 ft in 6.87 s and landed in 4.87 s.
A CPU-only MATLAB implementation took about 1.5 s per iteration on the Lift+Cruise task on an Intel i7-9850H, and under 1 s per iteration on the other tasks.

Limitations

The authors call the runtime fairly slow for MPC (about 1.5 s per iteration on the Lift+Cruise task) and say better parallelization is needed for real-time use.
The simultaneous scheme depends heavily on the initial control trajectory (it was warm-started with 5 standard DDP iterations) and fell into poor solutions on the quadrotor and Lift+Cruise tasks.
On the Lift+Cruise task the alternating scheme trailed STO-DDP for the first 50 iterations while the controls were still poor.
The method assumes full state observability and dynamics and costs that are twice differentiable in states, controls and parameters; convergence relies on regularization to keep Hessians positive definite.
All experiments are in simulation; no hardware tests are reported.

Field impact

The paper was a finalist for the RSS 2022 Best Student Paper Award. It names no code or data release.

Abstract

Differential Dynamic Programming (DDP) is an efficient trajectory optimization algorithm relying on second-order approximations of a system's dynamics and cost function, and has recently been applied to optimize systems with time-invariant parameters. Prior works include system parameter estimation and identifying the optimal switching time between modes of hybrid dynamical systems. This paper generalizes previous work by proposing a general parameterized optimal control objective and deriving a parametric version of DDP, titled Parameterized Differential Dynamic Programming (PDDP). A rigorous convergence analysis of the algorithm is provided, and PDDP is shown to converge to a minimum of the cost regardless of initialization. The effects of varying the optimization to more effectively escape local minima are analyzed. Experiments are presented applying PDDP on multiple robotics systems to solve model predictive control (MPC) and moving horizon estimation (MHE) tasks simultaneously. Finally, PDDP is used to determine the optimal transition point between flight regimes of a complex urban air mobility (UAM) class vehicle exhibiting multiple phases of flight.

Open Source Robotics