Matt Strong

Matt Strong

CS PhD at Stanford University

← Paper Digest

Crocoddyl: An Efficient and Versatile Framework for Multi-Contact Optimal Control

Carlos Mastalli, Rohan Budhiraja, Wolfgang Merkt, Guilhem Saurel, Bilal Hammoud, Maximilien Naveau, Justin Carpentier, Ludovic Righetti, Sethu Vijayakumar, Nicolas Mansard

Seminal September 2019

TL;DR An open-source optimal control library for legged robots with a given contact sequence, built around FDDP, a DDP variant that starts from infeasible guesses and keeps dynamics gaps open in early iterations. Gaits, jumps and a front-flip converge in 10-34 iterations and under 0.5 s, with single iterations running at up to 859.6 Hz.

What they do

Crocoddyl is an open-source library for multi-contact optimal control: given a predefined sequence of contacts and timings, it computes a whole-body state trajectory and a feedback control policy for a legged robot. Its solver, Feasibility-driven DDP (FDDP), changes classical DDP so it can start from infeasible guesses and behave like a multiple-shooting method without adding decision variables.

How it works

  • Contact dynamics. Contacts are holonomic constraints on frame placements with Baumgarte-like stabilization, and contact switches use impulse dynamics. Derivatives are analytical and sparse (RNEA and kinematics derivatives, Cholesky factorizations), and the floating base is an SE(3) element.
  • Infeasible backward pass. Following Giftthaler et al., the Riccati recursion accounts for gaps between shooting nodes, so the solver can be warm-started with full state and control trajectories.
  • Rollout that keeps gaps open. A step of length α shrinks each gap by a factor (1−α), matching a Newton step on the KKT conditions of multiple shooting with equality constraints only. With α = 1 the gaps close and FDDP behaves like DDP. No merit function is needed.
  • Step acceptance. An expected cost reduction that includes the gaps, checked with the Goldstein condition instead of Armijo, since the step can increase the cost during infeasible iterations.

Results

  • Walking, trotting, pacing and bounding converge in around 12 iterations. Jumps (ANYmal, iCub) and a biped front-flip take 12-36 iterations from a naive, infeasible warm-start.
  • All motions converge in 10-34 iterations and under 0.5 s total, with 60-115 nodes. On the jumps, FDDP keeps the gaps open for a few iterations.
  • One iteration runs at up to 859.6 Hz (ANYmal jump, 60 nodes, i9-9900K). Its cost grows linearly with the number of nodes and does not depend on the number of contacts. Running the derivatives on 4-8 threads roughly halves it.
  • Impulse models at contact switches converged better than penalizing contact velocity.

Limitations

FDDP handles only equality constraints: the experiments ignore friction cones and torque limits, which could enter only as penalties for now. The contact sequence and timings must be given. No hardware experiments are reported.

Videos

Full video (YouTube)

Figures

From Figure 1: the ANYmal quadruped traversing an obstacle with a highly-dynamic jump computed by Crocoddyl.
From Figure 1: the ANYmal quadruped traversing an obstacle with a highly-dynamic jump computed by Crocoddyl.
From Figure 3: snapshots of a front-flip maneuver generated by FDDP for a biped robot.
From Figure 3: snapshots of a front-flip maneuver generated by FDDP for a biped robot.
From Figure 2: normalized total gap norm and step length (top) and normalized cost (bottom) per iteration for each mo...
From Figure 2: normalized total gap norm and step length (top) and normalized cost (bottom) per iteration for each motion. Gaps close in the first iteration for biped walking and quadruped gaits, while FDDP keeps them open for the early iterations of the jumps, which also improve more slowly over the first nine iterations.
From Figure 5: computation frequency of one solver iteration for each motion on PC1 (i7-6700K, 4 threads, typical of ...
From Figure 5: computation frequency of one solver iteration for each motion on PC1 (i7-6700K, 4 threads, typical of on-board robot computers) and PC3 (high-performance i9-9900K, 8 threads).
Abstract

We introduce Crocoddyl (Contact RObot COntrol by Differential DYnamic Library), an open-source framework tailored for efficient multi-contact optimal control. Crocoddyl efficiently computes the state trajectory and the control policy for a given predefined sequence of contacts. Its efficiency is due to the use of sparse analytical derivatives, exploitation of the problem structure, and data sharing. It employs differential geometry to properly describe the state of any geometrical system, e.g. floating-base systems. Additionally, we propose a novel optimal control algorithm called Feasibility-driven Differential Dynamic Programming (FDDP). Our method does not add extra decision variables which often increases the computation time per iteration due to factorization. FDDP shows a greater globalization strategy compared to classical Differential Dynamic Programming (DDP) algorithms. Concretely, we propose two modifications to the classical DDP algorithm. First, the backward pass accepts infeasible state-control trajectories. Second, the rollout keeps the gaps open during the early "exploratory" iterations (as expected in multiple-shooting methods with only equality constraints). We showcase the performance of our framework using different tasks. With our method, we can compute highly-dynamic maneuvers (e.g. jumping, front-flip) within few milliseconds.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.