A Unified Perspective on Multiple Shooting In Differential Dynamic Programming

Wenhao Yu, He Li, Wenhao Yu 0003, Tingnan Zhang, Patrick M. Wensing

TL;DR

This paper introduces a unified framework for Differential Dynamic Programming (DDP) that incorporates multiple shooting (MS) techniques. This novel approach significantly improves the robustness of DDP to initial guesses, a common limitation of traditional single-shooting DDP, while maintaining local quadratic convergence and enabling broader algorithmic improvements.

What Problem Does This Paper Address?

Differential Dynamic Programming (DDP) is a powerful tool for solving nonlinear optimal control problems, widely used in robotics for tasks like locomotion and manipulation. However, standard DDP is a single-shooting method, meaning it's highly sensitive to the initial guess of the trajectory. A poor initial guess can lead to divergence or convergence to suboptimal solutions. Multiple shooting (MS) addresses this by dividing the trajectory into segments, allowing for independent initialization and optimization of "shooting states" at segment boundaries. While MS-DDP exists, this paper aims to unify existing MS-DDP approaches, provide a more robust derivation that explicitly handles "defects" (discontinuities at shooting states), and introduce algorithmic enhancements for better convergence and reliability.

Methods

The core contribution is a novel derivation for the DDP backward pass that explicitly accounts for defects introduced by multiple shooting. This allows for the integration of second-order dynamics information, leading to local quadratic convergence. This unified derivation also serves to reconcile and generalize several previously proposed MS-DDP algorithms.

Beyond the core derivation, the authors introduce several algorithmic enhancements:

  • Adaptive Merit Function: A mechanism to balance minimizing the cost function and reducing dynamic infeasibility (defects). It adaptively adjusts a weighting parameter to ensure progress.
  • Improved Acceptance Condition: An Armijo-like condition that uses an "expected cost change" (EC) model. This EC model is derived to be exact for linear dynamics and quadratic cost approximations, improving upon previous approximated models.
  • Penalty Method: A technique to improve convergence for problems with higher nonlinearity, particularly when using a small number of shooting segments. It adds a penalty term to the cost function to encourage better connection between segments.
  • Unified Framework: The paper presents a framework that can synthesize various DDP configurations by choosing different backward sweep dynamics (first-order vs. second-order) and forward roll-out methods (nonlinear vs. hybrid).

Datasets

The paper does not introduce new datasets. Instead, it benchmarks its proposed MS-DDP framework on three standard robotic control problems:

  • Acrobot: A two-link manipulator requiring a swing-up motion.
  • Quadrotor: A rigid body with four thrust inputs, tasked with trajectory optimization.
  • Kuka iiwa 7-DoF Manipulator: A complex robotic arm performing a swing motion.

Additionally, the framework is applied to a quadruped robot (MIT Mini Cheetah) for Model Predictive Control (MPC) of dynamic locomotion tasks, including jumping.

Key Insights and Ideas

  • Unification is Powerful: By providing a single, unified derivation for the MS-DDP backward pass, the authors demonstrate how various existing MS-DDP algorithms can be seen as special cases of their framework. This simplifies understanding and opens doors for new combinations.
  • Second-Order Dynamics Matter: Incorporating second-order dynamics in the backward pass, enabled by the defect-aware derivation, leads to significantly faster local convergence (quadratic vs. linear).
  • Exact Expected Cost Change is Crucial: Using an exact model for expected cost change, rather than approximations, is shown to be critical for robust convergence, especially in scenarios where defects are present.
  • Penalty Method for Nonlinearity: The penalty method proves effective in reducing the number of iterations required for convergence, particularly for more nonlinear problems or when using fewer shooting segments.
  • MS-DDP Excels in Dynamic Scenarios: The framework demonstrates superior performance over single-shooting DDP in highly dynamic tasks like quadruped jumping, where initial guess sensitivity is a major hurdle.

Key Results

  • Local Convergence: The MS-DDP with second-order dynamics and nonlinear roll-out consistently achieves quadratic convergence, outperforming first-order methods. Hybrid roll-out shows intermediate convergence rates.
  • Acceptance Condition: The proposed exact EC model significantly improves convergence compared to approximated ECs, enabling progress where others fail.
  • Penalty Method: For the manipulator and quadrotor examples, the penalty method reduced the number of iterations to converge, especially for problems with higher nonlinearity (fewer shooting nodes). For the manipulator with four shooting nodes, it achieved 48 fewer iterations.
  • Quadruped MPC: In a quadruped locomotion MPC task, MS-DDP successfully recovered from a lateral velocity disturbance during a jump, while SS-DDP diverged. This highlights the practical benefits of MS-DDP for robust real-time control.

Limitations and Future Work

  • Statistical Assessment: The authors acknowledge that future work should focus on generalizing the results to more problems and conducting broader statistical assessments.
  • Hardware Implementation: While hardware results are qualitatively validated, the paper notes that the 50 Hz MPC rate was insufficient for stable jumping due to model mismatch, suggesting a need for higher rates or QP-based whole-body controllers.
  • Generalization: The paper focuses on specific robotic systems; extending the framework to a wider range of applications and more complex dynamics could be a future direction.

Summary updated

Abstract

Differential Dynamic Programming (DDP) is an efficient computational tool for solving nonlinear optimal control problems. It was originally designed as a single shooting method and thus is sensitive to the initial guess supplied. This work considers the extension of DDP to multiple shooting (MS), improving its robustness to initial guesses. A novel derivation is proposed that accounts for the defect between shooting segments during the DDP backward pass, while still maintaining quadratic convergence locally. The derivation enables unifying multiple previous MS algorithms, and opens the door to many smaller algorithmic improvements. A penalty method is introduced to strategically control the step size, further improving the convergence performance. An adaptive merit function and a more reliable acceptance condition are employed for globalization. The effects of these improvements are benchmarked for trajectory optimization with a quadrotor, an acrobot, and a manipulator. MS-DDP is also demonstrated for use in Model Predictive Control (MPC) for dynamic jumping with a quadruped robot, showing its benefits over a single shooting approach.
BibTeX
@inproceedings{yu2023unified,
  author = {Wenhao Yu and He Li and Wenhao Yu and Tingnan Zhang and Patrick M. Wensing},
  title = {{A Unified Perspective on Multiple Shooting In Differential Dynamic Programming}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  doi = {10.1109/iros55552.2023.10342217},
}
Figure