Line-Search Filter Differential Dynamic Programming for Optimal Control with Nonlinear Equality Constraints
Mingda Xu, Stephen Gould, Iman Shames
AI summary
Problem
Extending differential dynamic programming to handle nonlinear equality constraints remains underexplored, with existing augmented Lagrangian and merit function methods offering limited formal convergence guarantees.
Approach
The algorithm employs a step filter and backtracking line search to accept trial steps, using the Lagrangian instead of the cost in acceptance criteria and perturbing the value function Hessian during the backward pass to ensure stability.
Key results
- Rigorous proof of local quadratic convergence for constrained DDP
- Novel filter criteria using the Lagrangian and perturbed Hessian for robust step acceptance
- Primal-dual interior point extension for handling inequality constraints alongside equalities
- Demonstrated superior robustness and lower iteration counts on contact-implicit robotics trajectory optimization tasks
Why it matters
Provides a theoretically grounded, faster, and more robust alternative to augmented Lagrangian methods for solving constrained optimal control problems in robotics and embedded systems.
Abstract
We present FilterDDP, a differential dynamic programming algorithm for solving discrete-time, optimal control problems (OCPs) with nonlinear equality constraints. Unlike prior methods based on merit functions or the augmented Lagrangian class of algorithms, FilterDDP uses a step filter in conjunction with a line search to handle equality constraints. We identify two important design choices for the step filter criteria which lead to robust numerical performance: 1) we use the Lagrangian instead of the cost in the step acceptance criterion and, 2) in the backward pass, we perturb the value function Hessian. Both choices are rigorously justified, for 2) in particular by a formal proof of local quadratic convergence. In addition to providing a primal-dual interior point extension for handling OCPs with both equality and inequality constraints, we validate FilterDDP on three contact implicit trajectory optimisation problems which arise in robotics.