Constrained Differential Dynamic Programming for Trajectory Optimization

15 concepts15 papers1 proposal

When controlling a complex robotic system—whether it is a quadruped navigating rugged terrain, an autonomous vehicle negotiating a crowded intersection, or a surgical robot maneuvering inside a human eye—the core challenge is solving a trajectory optimization problem. The system must find a sequence of control inputs that minimizes a cost function (such as time or energy) while obeying both the non-linear physics of the system and strict safety boundaries.

Historically, roboticists faced a stark trade-off. They could either use general-purpose Non-Linear Programming (NLP) solvers, which handle complex constraints well but scale poorly with the length of the trajectory, or they could use Differential Dynamic Programming (DDP), which is incredibly fast but struggles to enforce hard constraints.

A powerful class of algorithms bridges this gap by embedding constraint-handling mechanisms directly into the recursive steps of DDP. This combination allows robots to calculate safe, optimal paths in real time by preserving the linear computational complexity of dynamic programming.

The Efficiency of Traditional DDP

To understand why traditional DDP breaks down under constraints—and how modern variants fix it—we must first look at how standard DDP exploits the structure of time.

A trajectory optimization problem over a time horizon $T$ is inherently high-dimensional. If you try to optimize every control input at every time step simultaneously using a generic optimization solver, the computational cost typically scales cubically with the horizon length, $O(T^3)$.

DDP avoids this curse of dimensionality by applying Bellman’s Principle of Optimality. It breaks the global optimization problem down into a sequence of smaller, localized subproblems by sweeping backward through time.

Starting at the final time step $T$ and moving backward to the present, DDP constructs a local quadratic approximation of the action-value function (often called the $Q$-function) at each stage:

$$Q(x, u) \approx \frac{1}{2} \begin{bmatrix} x \\ u \end{bmatrix}^T \begin{bmatrix} Q_{xx} & Q_{xu} \\ Q_{ux} & Q_{uu} \end{bmatrix} \begin{bmatrix} x \\ u \end{bmatrix} + \begin{bmatrix} Q_x \\ Q_u \end{bmatrix}^T \begin{bmatrix} x \\ u \end{bmatrix}$$

Because this approximation is unconstrained and strictly quadratic, finding the optimal control update $\delta u$ is simple: you take the derivative with respect to $u$, set it to zero, and solve a linear system. This yields a feedback control law:

$$\delta u = -Q_{uu}^{-1} Q_{ux} \delta x - Q_{uu}^{-1} Q_u$$

This local optimization takes constant time per step. By repeating this process backward from $T$ to $0$, DDP solves the entire trajectory optimization problem in $O(T)$ linear time.

Why Hard Constraints Break the Sweep

The elegance of the DDP backward pass relies entirely on the assumption that the local $Q$-function is smooth and unconstrained. In the real world, however, trajectories are bounded by hard constraints. For example, as shown by Ji Woong Kim et al. in Towards Autonomous Eye Surgery by Combining Deep Imitation Learning with Optimal Control, a retinal surgery robot must strictly enforce a physical pivot point at the eye's entry site to avoid tearing tissue. Similarly, Wencong Wang et al. demonstrate in Trajectory Planning of a Semi-Trailer Train Based on Constrained Iterative LQR that autonomous trucks must respect strict geometric limits on their articulation angles to prevent jackknifing.

If you try to enforce these boundaries by simply "clipping" the control inputs or adding naive penalty functions to the cost, the mathematical foundation of DDP crumbles. Clipping controls introduces sharp kinks into the value function, making it non-differentiable and breaking the Taylor expansions used in the backward pass. Soft penalties, on the other hand, lead to severe numerical ill-conditioning; as you increase the penalty weight to enforce a hard boundary, the optimization landscape warps into a steep, narrow canyon, causing the solver to stall or diverge.

The Solution: Stage-Wise Constraint Embedding

The core insight of modern constrained DDP frameworks is that constraints should be solved locally within each step of the backward pass, rather than globally or via external penalties. Instead of minimizing an unconstrained quadratic $Q$-function at each time step, the solver minimizes the $Q$-function subject to a localized set of linear or linearized constraints:

$$\min_{u} Q(x, u) \quad \text{subject to} \quad g(x, u) \le 0$$

By solving this constrained optimization problem at each stage of the recursive sweep, the algorithm can compute a control update law that inherently respects the boundaries, passing the constrained derivatives back to the preceding time step. Researchers achieve this through two primary mathematical paradigms:

1. Primal-Dual Interior-Point DDP

Interior-point methods handle inequality constraints by augmenting the objective function with a logarithmic barrier function, such as $-\mu \ln(-g(x,u))$, where $\mu$ is a positive barrier parameter. As the system approaches the constraint boundary ($g \to 0$), the log-barrier approaches infinity, naturally pushing the trajectory away from the edge.

As detailed by Kun Cao 0002 et al. in DIRECT: A Differential Dynamic Programming Based Framework for Trajectory Generation, integrating interior-point methods directly into the recursive steps of DDP allows the solver to handle safety corridors and physical actuator limits smoothly. Rather than treating the barrier parameter as a static penalty, the authors update both the primal variables (states and controls) and the dual variables (Lagrange multipliers) simultaneously during the Riccati sweep.

This approach is further extended to learning frameworks by Kun Cao et al. in A Differential Dynamic Programming Framework for Inverse Reinforcement Learning, demonstrating that embedding primal-dual interior-point steps into DDP allows robots to recover underlying cost functions and constraints directly from noisy expert demonstrations.

2. Proximal and Augmented Lagrangian DDP

While interior-point methods keep the trajectory strictly inside the feasible region, they can struggle if the initial guess starts outside the allowed boundaries. To solve this, researchers turn to Augmented Lagrangian and proximal methods.

The Augmented Lagrangian approach combines the benefits of regular Lagrange multipliers with a quadratic penalty term. During the DDP backward pass, the algorithm solves a localized Karush-Kuhn-Tucker (KKT) system at each time step. If a constraint is violated, the corresponding Lagrange multiplier is updated iteratively.

In ALGAMES: A Fast Solver for Constrained Dynamic Games, Mac Schwager et al. leverage this formulation to solve multi-agent interactions and collision avoidance in real-time autonomous driving scenarios. Because the multipliers absorb the constraint forces, the method avoids the numerical instability of pure penalty methods while ensuring precise constraint satisfaction.

Taking this a step further, Wilson Jallet et al. introduce ProxDDP: Proximal Constrained Trajectory Optimization. By integrating proximal algorithms into the DDP framework, the authors provide a mathematically robust way to handle implicit dynamics and hard operational constraints simultaneously. The proximal operator acts as a regularizer, ensuring that even when a quadruped robot experiences sudden foot-ground impacts or hits torque limits, the numerical solver remains stable and converges rapidly.

[Global Trajectory Optimization Problem]
                 │
                 ▼ (Exploit Temporal Structure)
[Stage-Wise Decomposition (Backward Pass Sweep)]
                 │
   ┌─────────────┴─────────────┐
   ▼                           ▼
[Time Step t]               [Time Step t-1]
Local Q-Function            Local Q-Function
   │                           │
   ▼ (Embed Constraints)       ▼ (Embed Constraints)
Min Q(x,u) s.t. g(x,u) <= 0   Min Q(x,u) s.t. g(x,u) <= 0
(Interior-Point / Proximal)  (Interior-Point / Proximal)
   │                           ▲
   └───────────┬───────────────┘
               │ (Pass Constrained Value Derivatives)
               ▼
[Result: O(T) Linear Complexity + Hard Safety Guarantees]

Managing the Conservative Nature of Barriers

One common issue with embedding strict safety boundaries into trajectory planners is that they can make the solver overly conservative. If a robot cannot find a perfectly valid path immediately, it may refuse to explore the environment altogether.

To counter this, Joshua E. Kuperman et al. propose a modification in Improved Exploration for Safety-Embedded Differential Dynamic Programming Using Tolerant Barrier States. The authors introduce "tolerant barrier states" that allow the trajectory planner to temporarily and virtually violate safety boundaries during the intermediate iterations of the optimization process. By giving the solver the mathematical freedom to "break the rules" during the planning phase, the robot can navigate through narrow passages and discover globally optimal paths that a strictly conservative barrier method would reject outright.

Why It Works: Preserving the Block-Tridiagonal Structure

The ultimate reason why constrained DDP works so efficiently comes down to matrix structure. If you write out the full optimality conditions for a trajectory optimization problem across all time steps, you get a massive system of equations. For general optimization problems, this matrix is dense, leading to the slow $O(T^3)$ solution time.

However, because time only flows forward, the states and controls at time step $t$ only directly affect the states at time step $t+1$. This gives the global system of equations a highly sparse, block-tridiagonal structure.

By solving the constraints locally at each stage of the DDP backward pass, the algorithm decouples the spatial constraints (like obstacle avoidance at a specific moment) from the global temporal sequence. The solver never has to invert a massive, dense matrix. Instead, it performs a sequence of small matrix inversions at each time step, maintaining the highly desired $O(T)$ linear complexity while guaranteeing that the final trajectory strictly respects the physical boundaries of the real world.

Key Foundational Work

Towards Autonomous Eye Surgery by Combining Deep Imitation Learning with Optimal Control (2020) — contributed 1 concept elements to this direction.
Helicopter Safe Landing Trajectory after Main Rotor Actuator Failures (2020) — contributed 1 concept elements to this direction.
Path Planning and Flight Controller Scheduling for an Autonomous Helicopter (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constrained_trajectory_optimization_d9704475,
  title = {constrained trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-trajectory-optimization/rdr_d9704475d726417a9428f093eec96104},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_constrained_trajectory_optimization_d9704475_v1,
  title = {constrained trajectory optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-trajectory-optimization/rdr_d9704475d726417a9428f093eec96104/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake