Source-linked AI summary
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
TL;DR
Legged-robot optimal control needs efficient handling of multi-contact dynamics, geometric state representations, and difficult nonlinear trajectories. Crocoddyl combines sparse analytical derivatives with differential-geometric modeling and introduces FDDP, which accepts infeasible trajectories and keeps gaps open during exploratory rollouts. The framework computes highly dynamic maneuvers such as jumping and front-flipping in milliseconds, with reported motions converging in 10 to 34 iterations and under 0.5 seconds overall.
Problem
Existing legged-robot optimal-control frameworks can use inefficient differentiation and fail to explicitly handle the geometric structure and difficult dynamics of legged systems.
Method
Crocoddyl uses sparse analytical derivatives, differential-geometric state representations, and FDDP, which accepts infeasible guesses and keeps rollout gaps open early.
Results
The framework computes jumping and front-flip maneuvers in milliseconds; reported motions converge within 10 to 34 iterations with total computation time below 0.5 s.
Takeaways & Limitations
FDDP’s improved globalization enables Crocoddyl to solve complex highly dynamic maneuvers in few iterations without adding extra decision variables.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Crocoddyl addresses limitations of existing legged-robot optimal-control frameworks by combining efficient multi-contact modeling with FDDP. The framework targets highly dynamic maneuvers while handling system geometry and infeasible trajectories.
- I. INTRODUCTION: Multi-contact optimal control can generate whole-body motions and policies for legged robots reacting robustly to unexpected events in real time.Existing approaches may mishandle robot orientation during flight and angular-momentum regulation can cause tracking errors.
- I. INTRODUCTION: Recent nonlinear MPC frameworks solve optimal-control problems through iterative LQR or DDP, but often use inefficient numerical or automatic differentiation and omit geometric structure.Crocoddyl instead uses tailored analytical and sparse derivatives for fast computation.
- I. INTRODUCTION: The framework computes highly dynamic maneuvers such as jumping and front-flipping, addressing the stated drawbacks in existing approaches.The paper presents these maneuvers as a demonstration of the framework’s capabilities.
- I. INTRODUCTION: FDDP handles infeasible state-control guesses and improves globalization without adding the extra decision variables used by direct multiple-shooting formulations.An infeasible warm-start contains trajectories inconsistent with the system dynamics.
- I. INTRODUCTION: Crocoddyl models multi-contact optimal control for multibody systems using differential-manifold states, torque and contact-force controls, and admissible state-control sets.The state is x = (q, v), while the control is u = (τ, λ).
B. Contacts as holonomic constraints
Crocoddyl represents contacts as holonomic, scleronomic constraints and solves the resulting contact-force relation analytically. Stabilization gains improve numerical integration, while omitted inequality constraints can be added through penalization or related strategies.
- B. Contacts as holonomic constraints: The contact model uses holonomic scleronomic frame-placement constraints, φ(q) = 0, with Jc as the contact Jacobian.This formulation reduces the contact dynamics to an analytically solvable lower-level problem.
- B. Contacts as holonomic constraints: Equation (2) expresses contact forces from the state and torques, with a unique solution when Jc is full-rank.The contact Jacobian is expressed in the local frame, and a0 is the desired acceleration in constraint space.
- B. Contacts as holonomic constraints: PD gains similar to Baumgarte stabilization are defined to improve numerical-integration stability.The gains act on contact velocity and acceleration together with the pose error between reference and current contact placements.
- B. Contacts as holonomic constraints: Because Equation (2) neglects friction-cone constraints and joint limits, the resulting dynamics are equality-constrained and can use an unconstrained DDP solver.Inequality constraints can still be incorporated using penalization, active-set, or Augmented Lagrangian strategies.
1) Efficient rollout and derivative computation:
The rollout and derivative computation avoid full KKT inversion by exploiting matrix structure and analytical derivatives. This connects contact-dynamics Jacobians to efficient multibody kinematics and dynamics routines.
- 1) Efficient rollout and derivative computation:: During numerical integration, Crocoddyl avoids inverting the entire KKT matrix by describing system acceleration and contact evolution in a reduced form.This is the central structural simplification used for efficient rollout computation.
- 1) Efficient rollout and derivative computation:: Analytical chain-rule differentiation expresses the Jacobians of y(·) and g(·) through derivatives from Recursive Newton-Euler Algorithm and kinematics routines.The derivative construction reuses structured multibody dynamics and kinematics calculations.
- 1) Efficient rollout and derivative computation:: A blockwise matrix in Equation (5) is inverted using an LDU decomposition.This complements the structured decomposition used for efficient derivative and rollout calculations.
2) Impulse dynamics:
The paper describes impulse dynamics for multibody systems and situates them within DDP-based optimal control. These formulations support efficient treatment of contact transitions and trajectory optimization.
- Impulse dynamics: Impulse dynamics model transitions into contact using restitution, contact impulses, and discontinuous generalized velocities before and after impact.Perfectly inelastic collision sets the contact velocity to zero with e = 0.
- Impulse dynamics: Cholesky decomposition is used to compute impulse dynamics and their derivatives efficiently.
- Differential dynamic programming: DDP locally approximates the optimal flow around state and control variations, decomposing optimal control into simpler subproblems.The decomposition uses Bellman’s principle of optimality.
- Differential dynamic programming: The Riccati recursion sequentially solves the local control problems and produces feed-forward terms and feedback gains at each discretization point.The Q terms represent a linear-quadratic approximation of the control Hamiltonian.
- Differential dynamic programming: The paper emphasizes linearizing cost and dynamics around a trajectory guess, including treatment of geometric dynamical-system structure.This geometric treatment is relevant when using structures such as manifolds and symplectic integrators.
B. The role of gaps in multiple-shooting
Multiple-shooting introduces intermediate shooting states and equality constraints to close gaps between rollout states and decision variables. The SQP formulation solves these constraints through QP iterations and trajectory updates.
- The role of gaps in multiple-shooting: Multiple-shooting adds intermediate states xk as decision variables and equality constraints that close gaps between shooting nodes.These gaps are also called defects in multiple-shooting literature.
- The role of gaps in multiple-shooting: Each dynamics gap compares the rollout state f(xk, uk) at the next interval with the next shooting state xk+1.
- The role of gaps in multiple-shooting: The direct multiple-shooting formulation can be approached as Sequential Quadratic Programming, where each iteration builds and solves a single QP.
- The role of gaps in multiple-shooting: The QP solution provides a search direction and a step length α for updating the next trajectory guess.
- The role of gaps in multiple-shooting: The updated trajectory need not close the dynamics gaps immediately.
1) KKT problem of the multiple-shooting formulation:
The multiple-shooting KKT formulation characterizes primal and dual feasibility for each shooting interval. Solving its first-order conditions yields search directions whose step size controls gap contraction.
- KKT problem of the multiple-shooting formulation: The KKT problem is formulated for a single shooting interval to derive the multiple-shooting search direction.
- KKT problem of the multiple-shooting formulation: The KKT matrix contains local cost derivatives, including gradients and Hessian blocks for state and control variables.
- KKT problem of the multiple-shooting formulation: The configuration lies on a manifold and system derivatives lie in its tangent space.
- KKT problem of the multiple-shooting formulation: Equations (12) and (13) represent dual and primal feasibility conditions from the first-order necessary conditions of optimality.
- KKT problem of the multiple-shooting formulation: The Lagrangian multipliers for the KKT problem are λk and λk+1.
- KKT problem of the multiple-shooting formulation: An α-step contracts the gap at interval k by a factor of (1 − α), while only α = 1 closes it completely.
C. Nonlinear rollout avoids merit function
The nonlinear rollout avoids both linear-prediction error and the need for a merit function in the SQP-style treatment of multiple-shooting gaps. It preserves the intended gap contraction during forward passes.
- Nonlinear rollout avoids merit function: The method uses a nonlinear rollout to avoid the linear-prediction error associated with the search direction.
- Nonlinear rollout avoids merit function: Avoiding a merit function removes a device that SQP often uses to compensate for local line-search errors.The paper states that selecting a suitable merit function is challenging.
- Nonlinear rollout avoids merit function: The nonlinear rollout predicts the gaps after an α-step and maintains the search direction’s gap contraction rate.
- Nonlinear rollout avoids merit function: The forward rollout combines feed-forward terms and feedback gains computed during the backward pass.
- Nonlinear rollout avoids merit function: With α = 1, the FDDP forward pass behaves exactly like the classical DDP forward pass, which always closes the gaps.
D. Backward pass under an infeasible guess trajectory
FDDP modifies the backward pass so it can operate on infeasible state-control guesses, mapping value-function derivatives between shooting nodes while preserving the Hessian.
- Motivation: Classical DDP requires an initial forward pass, effectively limiting warm starts to a control trajectory U0.An initial state trajectory is easy to obtain, but constructing a corresponding control trajectory beyond quasi-static maneuvers is difficult.
- Modified backward pass: FDDP adapts the backward pass to accept infeasible state-control trajectories.An infeasible warm-start contains state and control trajectories that are inconsistent with the system dynamics.
- Modified backward pass: The method maps the Value function Jacobian and Hessian from the next shooting node to the current node using an LQ approximation.The Jacobian varies linearly while the Hessian remains constant under the assumed approximation.
- Modified backward pass: After the deflection caused by the gap, the Value function Jacobian is updated while its Hessian remains unchanged.The update is expressed as xk+1 = Vxk+1 + Vxxk+1¯fk+1.
E. Accepting a step
FDDP evaluates trial steps with an expected-cost-reduction model that accounts for dynamics gaps and uses a Goldstein-based acceptance rule during infeasible iterations.
- Expected reduction: The expected total cost reduction must include the deflection introduced by dynamics gaps when evaluating a trial step.The standard expectation proposed in prior work omits this deflection.
- Expected reduction: Closing the gaps according to the linear rollout yields the expected cost-reduction model used by FDDP.When all gaps are closed, this model matches the expectation reported in prior work.
- Line search: FDDP uses the Goldstein condition instead of the Armijo condition because the expected cost change can be an ascent direction during infeasible iterations.The acceptance rule therefore accommodates trial steps taken before feasibility is restored.
- Line search: The line-search parameters used in the paper are b1 = 0.1 and b2 = 2.These are adjustable parameters in the cost-reduction acceptance condition.
IV. RESULTS
Crocoddyl applies FDDP to quadrupedal and bipedal gaits and to highly dynamic jumps and front-flips, achieving millisecond-scale computation from simple or infeasible warm starts.
- B. Highly-dynamic maneuvers: The experiments deliberately omit friction-cone constraints and torque limits, although inequality constraints can be included through quadratic penalization.The reported maneuver results therefore evaluate FDDP without those constraints active.
- A. Various legged gaits: FDDP computes walking, trotting, pacing, and bounding for quadruped and biped robots in the order of milliseconds.These gaits use a predefined sequence of contacts and step timings and are computed in around 12 iterations.
- A. Various legged gaits: The framework uses a cost function combining center-of-mass and foot-placement tracking with state and control regularization.The experiments warm-start the state using linear interpolation between nominal body postures of contact configurations.
- A. Various legged gaits: Impulse dynamics enforce zero contact velocity during switching phases, and the authors observed improved convergence compared with penalizing contact velocity.The state is regularized toward the nominal robot posture alongside tracking and control-regularization costs.
- B. Highly-dynamic maneuvers: Highly dynamic front-flips and jumps are computed in 12–36 iterations and in the order of milliseconds from a naïve, infeasible warm start.The experiments use the same initialization, weights, and cost functions as the gait experiments, with added state regularization during impacts.
- B. Highly-dynamic maneuvers: FDDP keeps gaps open for several early iterations in jumping motions, where this behavior is particularly important.Highly dynamic maneuvers show lower improvement rates during their first iterations, while the method can exhibit super-linear convergence in practice.
- B. Highly-dynamic maneuvers: FDDP outperforms classical DDP in highly dynamic maneuvers because feasible rollouts can be unstable and far from the solution.The authors attribute classical DDP’s difficulty to a poor globalization strategy caused by inappropriate feasible rollouts in the first iterations.
C. Runtime, contraction, and convergence
FDDP keeps gaps open during early iterations, supporting convergence for highly dynamic maneuvers despite slower initial improvement. The reported motions converge within 10–34 iterations and under 0.5 seconds overall, while the framework targets efficient high-frequency computation.
- Contraction and convergence: Keeping gaps open is particularly important for highly-dynamic maneuvers such as jumping, followed by often observed super-linear convergence after gap closure.When gaps are closed, the FDDP forward pass behaves like the DDP forward pass for a multiple-shooting formulation with equality constraints.
- Contraction and convergence: Highly-dynamic maneuvers initially improve more slowly, while FDDP with impact models shows competitive convergence rates against reported results.The same slower early improvement occurs in quadrupedal walking with four-feet support phases lasting Δt = 2 ms.
- Runtime: 10 to 34 iterations and less than 0.5 s overall computation time were reported for the motions.This summarizes the reported convergence range and total computation time.
- Maneuver demonstrations: Fig. 3 illustrates generated jumping-obstacle and front-flip maneuvers in humanoid, biped, and quadruped robots.The top, middle, and bottom snapshots correspond to humanoid jumping obstacles, a biped front-flip, and quadruped jumping obstacles, respectively.
- Runtime: FDDP avoids extra decision variables, reducing factorization-related per-iteration costs, while retaining cubic complexity in matrix dimension.The framework also uses efficient contact-dynamics and derivative computation to solve highly dynamic maneuvers at high frequencies.