Constrained Differential Dynamic Programming Revisited

Yuichiro Aoyama, George I. Boutselis, Akash Patel, Evangelos A. TheodorouICRA 2020

Abstract

Differential Dynamic Programming (DDP) has become a well established method for unconstrained trajectory optimization. Despite its several applications in robotics and controls however, a widely successful constrained version of the algorithm has yet to be developed. This paper builds upon penalty methods and active-set approaches, towards designing a Dynamic Programming-based methodology for constrained optimal control. Regarding the former, our derivation employs a constrained version of Bellman's principle of optimality, by introducing a set of auxiliary slack variables in the backward pass. In parallel, we show how Augmented Lagrangian methods can be naturally incorporated within DDP, by utilizing a particular set of penalty-Lagrangian functions that preserve second-order differentiability. We demonstrate experimentally that our extensions (individually and combinations thereof) enhance significantly the convergence properties of the algorithm, and outperform previous approaches on a large number of simulated scenarios.

Introduction

Trajectory optimization is a fundamental component of modern robotics, enabling agents to compute optimal paths while adhering to physical laws and environmental constraints. Differential Dynamic Programming (DDP) is a prominent "indirect" method favored for its computational efficiency, as it exploits the temporal structure of optimal control problems to decompose them into smaller, sequential sub-problems.

Despite its success in unconstrained scenarios, extending DDP to handle state and control constraints remains a significant challenge. While "direct" methods like Sequential Quadratic Programming (SQP) handle constraints robustly, they often fail to exploit temporal structure as effectively as DDP, leading to higher computational costs for long-horizon problems. Previous attempts to constrain DDP have frequently struggled with numerical instability, poor convergence, or the requirement for a feasible initial guess. This paper introduces two novel extensions—S-KKT and AL-DDP—to address these limitations.

Methodology

The authors propose a framework that integrates slack variables and Augmented Lagrangian methods into the DDP architecture.

S-KKT: Slack-Variable KKT Approach

Traditional constrained DDP often relies on active-set methods, which can be numerically unstable due to the discrete nature of constraint activation. In contrast, the S-KKT approach introduces auxiliary slack variables into the Karush-Kuhn-Tucker (KKT) conditions during the backward pass. By employing a primal-dual interior-point methodology, inequality constraints are transformed into a smooth system of equations, facilitating a more stable optimization landscape.

Algorithm 1: The modified backward pass for constrained DDP using slack variables.

AL-DDP: Smooth Augmented Lagrangian DDP

The second contribution, AL-DDP, utilizes an Augmented Lagrangian framework to incorporate constraints as penalties within the cost function. A key innovation is the use of a specific class of penalty-Lagrangian functions that are twice-differentiable. This preservation of second-order smoothness is crucial for DDP, which relies on Hessian information for quadratic convergence.

Hybrid AL-S-KKT

To leverage the robustness of Augmented Lagrangian methods and the precision of interior-point methods, a hybrid approach is proposed. AL-DDP is used to warm-start the optimization from potentially infeasible initializations, followed by S-KKT to refine the trajectory to high precision.

Experiments and Results

The proposed methods were evaluated on three benchmarks: a 2D car navigating obstacles, a cart-pole system with state limits, and a high-dimensional quadrotor flight task.

Comparison of trajectory optimization methods: (a) Former method, (b) Active set, and (c) the proposed S-KKT approach.

The experimental results highlight several key advantages:

  • Computational Efficiency: In the quadrotor task, S-KKT achieved solutions nearly 70 times faster than standard SQP solvers (10.7s vs 748s).
  • Robustness to Infeasibility: S-KKT successfully converged even when the initial trajectory violated constraints by significant margins (e.g., 0.3m in the 2D car task), a scenario where previous DDP variants typically fail.
  • Improved Convergence: The hybrid AL-S-KKT method consistently outperformed individual methods in complex, highly constrained environments.

Discussion

The success of these methods underscores the importance of maintaining second-order differentiability in constrained optimization. By avoiding "hard" switching logic (like standard max functions), the algorithm maintains the mathematical properties required for DDP's efficiency. Furthermore, the use of slack variables provides a continuous mechanism for constraint handling, leading to smoother updates and better stability.

Conclusion

This work demonstrates that with proper mathematical formulations—specifically the use of slack variables and smooth penalty functions—DDP can be effectively extended to handle complex constraints. Future work includes extending this framework to stochastic systems to handle uncertainty and integrating these constrained optimization techniques into reinforcement learning frameworks for safety-critical applications.

Summary updated

Abstract

Differential Dynamic Programming (DDP) has become a well established method for unconstrained trajectory optimization. Despite its several applications in robotics and controls however, a widely successful constrained version of the algorithm has yet to be developed. This paper builds upon penalty methods and active-set approaches, towards designing a Dynamic Programming-based methodology for constrained optimal control. Regarding the former, our derivation employs a constrained version of Bellman's principle of optimality, by introducing a set of auxiliary slack variables in the backward pass. In parallel, we show how Augmented Lagrangian methods can be naturally incorporated within DDP, by utilizing a particular set of penalty-Lagrangian functions that preserve second-order differentiability. We demonstrate experimentally that our extensions (individually and combinations thereof) enhance significantly the convergence properties of the algorithm, and outperform previous approaches on a large number of simulated scenarios.
BibTeX
@inproceedings{aoyama2020constrained,
  author = {Yuichiro Aoyama and George I. Boutselis and Akash Patel and Evangelos A. Theodorou},
  title = {{Constrained Differential Dynamic Programming Revisited}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2020},
}
Figure