Optimization-Based Control for Dynamic Legged Robots

Patrick M. Wensing; Michael Posa; Yue Hu; Adrien Escande; Nicolas Mansard; Andrea Del Prete

Source-linked AI summary

Optimization-Based Control for Dynamic Legged Robots

Patrick M. Wensing, Michael Posa, Yue Hu, Adrien Escande, Nicolas Mansard, Andrea Del Prete

arXiv:2211.11644v1Nov 21, 2022cs.RO

TL;DR

General optimal control formulations for legged robots remain difficult to solve online because intermittent contacts and high-dimensional dynamics create computational challenges. This survey synthesizes model-based optimization strategies for contact treatment, model simplification, and numerical solution, while identifying links with learning-based methods. It concludes that contact-implicit methods still face speed and nonconvexity challenges, while fixed contact sequences and simplified models remain important for practical online optimization.

Problem
Online solution of general legged-robot optimal control problems is limited by intermittent environmental contacts and many robot degrees of freedom.
Method
The survey synthesizes model-based optimization approaches according to contact treatment, dynamic-model simplification, and numerical solution methods.
Results
Contact-implicit methods avoid prescribing contact sequences but retain speed and nonconvexity challenges, while fixed contact sequences remain the most viable option for practical online optimization.
Takeaways & Limitations
Combining planning or learning with contact-implicit methods is identified as a next step, while simplified models remain pertinent for near-term online optimization.

Abstract

from arXiv · show

In a world designed for legs, quadrupeds, bipeds, and humanoids have the opportunity to impact emerging robotics applications from logistics, to agriculture, to home assistance. The goal of this survey is to cover the recent progress toward these applications that has been driven by model-based optimization for the real-time generation and control of movement. The majority of the research community has converged on the idea of generating locomotion control laws by solving an optimal control problem (OCP) in either a model-based or data-driven manner. However, solving the most general of these problems online remains intractable due to complexities from intermittent unidirectional contacts with the environment, and from the many degrees of freedom of legged robots. This survey covers methods that have been pursued to make these OCPs computationally tractable, with specific focus on how environmental contacts are treated, how the model can be simplified, and how these choices affect the numerical solution methods employed. The survey focuses on model-based optimization, covering its recent use in a stand alone fashion, and suggesting avenues for combination with learning-based formulations to further accelerate progress in this growing field.

I. INTRODUCTION

Optimization-based control has helped legged robots progress toward reliable locomotion and autonomy in complex environments. This survey synthesizes model-based optimization methods, their computational challenges, and connections to learning-based approaches.

I. INTRODUCTION: Optimization-based control has played a central role in milestone demonstrations that advanced legged robots toward reliable locomotion.The survey places this progress within advances in robot design and control over the past decade.
I. INTRODUCTION: Predictive controllers iteratively improve motion plans using an explicit system model, whereas reactive controllers act only on the current instant.Reactive execution may be model-based or model-free.
I. INTRODUCTION: Model-based control naturally incorporates safety constraints and can generalize through first-principles models, but its guarantees depend on model accuracy and perceptual inputs remain difficult to formulate.These limitations motivate interest in learning-based strategies for hard-to-model and perception-related aspects.
I. INTRODUCTION: The survey organizes recent advances around contact treatment, simplified dynamic models, and numerical methods that make optimal control computationally tractable.Its stated goal is to provide a synthesized entry point for early-stage graduate students and follow-on reading for experts.
I. INTRODUCTION: The reviewed optimal control problem includes state, torque, and contact-force trajectories subject to dynamics, contact, kinematic, input, and task-specific constraints.The cost can encode objectives such as energy consumption or distance to a target.
I. INTRODUCTION: Although the formulation can encode diverse movements, its computational complexity reflects non-smooth or stiff dynamics, nonconvexity, and high dimensionality.The survey focuses on making the problem tractable for offline trajectory optimization and online model predictive control.

A. Contact Models

Contact modeling choices determine whether legged-robot dynamics are smooth, hybrid, or complementarity-based, and therefore constrain the optimization tools available. The survey also links model simplification, transcription choices, and hierarchical decomposition to computational tractability.

A. Contact Models: Visco-elastic contact models can produce continuous differentiable dynamics, but realistic behavior requires large stiffness values that create stiff differential equations.Smoothing can support differentiability, while stiffness increases numerical difficulty.
A. Contact Models: Rigid contact produces hybrid dynamics because contact events impose instantaneous velocity changes to prevent penetration.The resulting optimal control problem can be formulated as an LCP or MIP, typically requiring less efficient customized optimization techniques.
A. Contact Models: Fixing the contact order makes the dynamics time-varying and differentiable, enabling smooth optimization but requiring contact phases to be guessed in advance.This trade-off is central when contact sequences are not known beforehand.
A. Contact Models: Reduced-order models address the high-dimensional nonlinear multibody dynamics by retaining key behavior with fewer state variables.The Linear Inverted Pendulum, for example, models the center of mass and contact locations while neglecting joint details.
A. Contact Models: Direct shooting and direct collocation are the principal robotics transcription families, while DDP offers favorable computation and a locally optimal feedback policy.Contact modeling choices affect which transcription tools and algorithms remain available.
A. Contact Models: State-of-the-art methods often decompose the full problem into smaller hierarchical subproblems, such as solving footsteps before motions with fixed footsteps.The survey describes the design of such decompositions as more art than science.
A. Contact Models: When optimization is too slow for model predictive control, reactive stabilizing controllers execute the computed motion or compensate for omitted modeling details.The omitted aspects can result from simplified trajectory-optimization models.

III. CONTACT

Physical contact creates stiff, discontinuous dynamics that complicate optimization-based control. Approaches therefore choose between rigid hybrid representations and smoothed or softened contact models, with different numerical and differentiation consequences.

Modeling contact: Physical frictional contact is difficult to treat computationally because it produces stiff and/or discontinuous equations of motion.Contact-model and contact-scheduling choices consequently shape the force parameterization, constraints, and solution methods.
Modeling contact: Visco-elastic contact models maintain continuous dynamics but require large stiffness values for realistic behavior, creating numerical challenges for simulation and optimization.Rigid-body approximations remain the focus of the review, despite their own nonsmooth contact transitions.
Numerical implications: Directly introducing stiff or discontinuous contact dynamics yields poorly conditioned optimization problems, motivating hybrid formulations or softened contact forces.The choice affects the sensitivity of trajectories to initial conditions, especially around impact events.
Hybrid dynamics: Hybrid models represent contact through modes, guards, and reset maps, with impulsive impacts producing instantaneous velocity jumps.Within each mode, the dynamics are differentiable; transition events carry the contact complexity.
Complementarity models: Complementarity formulations encode non-penetration and unilateral force conditions by requiring λn ≥0 and λn ⊥φ(q), with analogous constraints for friction.These formulations can be expressed in time-stepping or continuous models.

3) Pathologies:

Hybrid and contact-implicit formulations can exhibit non-unique, nonexistent, or poorly differentiable solutions. These pathologies complicate trajectory tracking, local optimization, and simultaneous contact-mode planning.

Pathologies: Hybrid multi-contact formulations can have no solution or infinitely many solutions, reflecting high sensitivity associated with stiff dynamics.When solutions are non-unique, planners assuming uniqueness may select trajectories that are practically impossible to track.
Hybrid differentiability: Hybrid trajectory derivatives typically exist when the mode sequence remains constant, but they often fail when perturbations change which contacts occur.A trajectory that does not make contact provides no local derivative information about initiating contact.
Differentiable simulation: Differentiable simulators provide local gradients consistently, but connect model accuracy and stiffness to the conditioning of the resulting optimization problem.The precise trade-off between modeling inaccuracies and numerical performance remains unknown.
Contact sequencing: Known contact sequences make discretized hybrid optimal control differentiable, whereas unknown sequences require the optimizer to determine contact ordering as well as motion.Minimal coordinates are efficient but complicate force constraints and state-dimension changes during mode transitions.
Planning methods: Mixed-integer, bilevel, and sampling-based methods jointly address discrete contact sequences and continuous motion, but contact-implicit approaches instead embed mode relationships in nonlinear programs.These alternatives include MIPs, RRTs, and PRMs for contact or collision-aware planning.

3) Contact-implicit planning:

Contact-implicit optimization embeds contact-mode relationships into nonlinear programs, while simplified dynamics reduce the dimensionality of whole-body planning. These methods improve tractability but retain conditioning and feasibility challenges.

Contact-implicit planning: Contact-implicit methods encode state-force relationships directly in nonlinear programs, using complementarity constraints or smooth contact approximations instead of discrete mode variables.They can violate strict complementarity before convergence and may require high-quality initial guesses.
Contact-implicit planning: Gradient-based methods can discover new contact modes when paired with differentiable contact models, while rigid-model approaches require other strategies for contact discovery.Smoothing may guide mode discovery when trajectories encounter new contacts.
Summary: Contact planning remains the main challenge for arbitrary locomotion in complex environments because gradient-based optimization is fundamentally unsuited to non-smooth contact-implicit problems.When the contact sequence is known beforehand, transcription methods can focus primarily on physical realism.
Simplified models: Centroidal dynamics exactly projects whole-body dynamics onto center-of-mass and net-momentum variables while relaxing joint-space constraints.This simplification motivates reduced optimization over CoM, angular momentum, contact locations, and contact forces.
Simplified models: Centroidal models reduce dimensionality but can admit motions that violate whole-body geometry or actuation limits, motivating combinations of whole-body kinematics and centroidal dynamics.Whole-body-feasible motions form only a subset of centroidal-feasible motions.
Centroidal optimization: Centroidal optimization remains nonlinear because angular momentum contains bilinear terms (pi − pCoM) × λi, prompting bounds, McCormick relaxations, or trajectory parameterizations.Some relaxations introduce integer variables, while fixed contact locations and Bézier parameterizations can avoid nonlinear effects.
Contact-force simplification: The Contact Wrench Cone aggregates friction-constrained contact forces into a 6D cone that supports static-stability checks and center-of-mass motion generation.Polygonal friction approximations make the cone polyhedral and enable computational-geometry tools.

B. Other Simplified Models

Simplified locomotion models reduce computational burden by retaining contact-relevant dynamics while imposing different motion assumptions. The LIP model further enables convex optimization because its fixed-height dynamics are linear.

Modeling simplifications: Centroidal dynamics project whole-body equations without restricting feasible movements, whereas other simplified models impose artificial motion restrictions or approximations.The survey identifies centroidal, SRB, and LIP models as successful simplifications for legged locomotion planning.
Single-rigid-body model: The SRB model treats a quadruped as having approximately configuration-invariant rotational inertia because many quadruped robots have light legs.It is a restricted centroidal momentum model with a constant mass-distribution shape.
Linear inverted pendulum: The LIP model fixes CoM height, removes orientation dynamics, and represents level-ground contacts through a Center of Pressure.These assumptions simplify humanoid gait planning.
Linear inverted pendulum: Linear LIP dynamics enable convex optimization for planning CoM and CoP trajectories and linear-systems tools such as LQR for tracking.The natural frequency of the LIP is represented by g/h.
Extensions: Height-varying models extend the LIP by treating height changes as perturbations or by incorporating them directly through a variable stiffness-like parameter.Constraint tightening can be used with perturbation models to ensure robust feasibility.

C. Summary

The survey emphasizes direct numerical methods for tractable trajectory optimization in legged robotics, while recognizing that modeling choices and contact modes shape the resulting problem. It identifies direct methods as especially prominent because they transcribe continuous-time OCPs into finite-dimensional NLPs solvable with established optimization techniques.

Modeling choices: Simplified models reduce computational burden while focusing modeling detail on motion limitations imposed by environmental contacts.Centroidal dynamics impose no motion restrictions, whereas SRB and LIP models add restrictions or approximations.
Modeling choices: Automatic discovery of simple locomotion models remains an open problem, with dimensionality-reduction tools from learning identified as a possible direction.The survey reviews existing models based on physics and expert intuition.
Contact modes: For locomotion, a fixed phase sequence yields a multi-phase problem whose mode switches use guard constraints and reset maps to represent contact transitions or impacts.The phase index partitions the time horizon into intervals with potentially discontinuous transitions.
Numerical methods: OCP solution methods fall into global HJB-based methods, local indirect methods, and local direct methods.The survey focuses mainly on direct methods for continuous-time problems because of their prominence in robotics applications.
Numerical methods: Direct methods transcribe the OCP into a finite-dimensional NLP by discretizing states and controls, enabling solution with established techniques such as Sequential Quadratic Programming.They are broadly adopted in legged robotics and accommodate systems of differential-algebraic equations.

A. Multiple shooting

Direct shooting and collocation transcribe trajectory optimization differently: shooting integrates dynamics over segments, while collocation approximates trajectories with polynomials and enforces dynamics at collocation points. DDP provides a local iterative alternative whose constraint handling and derivative requirements motivate several extensions.

A. Multiple shooting: Multiple shooting discretizes the horizon into segments, adds each segment’s initial state to the decision variables, and enforces continuity between integrated segments.Each segment is associated with a numerical simulation, and continuity constraints eliminate defects between neighboring segments.
A. Multiple shooting: Multiple shooting is used for whole-body motion generation with predefined contact modes, including rigid contacts and instantaneous inelastic impacts.The resulting optimization problem is multi-phase with discontinuous phase transitions.
B. Collocation: Direct collocation discretizes states and controls over finite elements, representing controls finitely and states with polynomials.States and controls at collocation points become optimization variables alongside endpoint states.
B. Collocation: Collocation enforces zero endpoint defects and matches the polynomial slope to the dynamics at each collocation point.The number and placement of collocation points affect how accurately the NLP approximates the original OCP.
B. Collocation: Collocation has generated walking motions for whole-body bipeds and quadrupeds with predefined contact sequences, including periodic motions using HZD virtual constraints.The cited quadruped formulation modifies collocation constraints for contact-aware motion generation.
C. Differential Dynamic Programming (DDP): DDP uses a local quadratic expansion of the Q function to avoid exhaustive state-space exploration in nonconvex optimal control problems.It can be viewed as an efficient iterative method related to solving the banded KKT system of a collocation-transcribed unconstrained OCP.
C. Differential Dynamic Programming (DDP): DDP requires second derivatives of the dynamics for quadratic convergence, motivating popular Hessian-approximation variants such as iLQR and iLQG.Computing full second derivatives can be challenging for complex systems.
C. Differential Dynamic Programming (DDP): Original DDP handles only system-dynamics constraints, but extensions address box, nonlinear inequality, implicit, hybrid, multi-phase, and multiple-shooting settings.These extensions broaden DDP’s applicability to contact-rich legged-robot problems.

D. Contact Implicit Considerations

Contact-implicit optimization jointly selects contact modes and trajectories, coupling contact modeling choices to the available transcription method. Complementarity constraints and their relaxations create explicit trade-offs between impact handling, accuracy, and computational complexity.

D. Contact Implicit Considerations: Contact-implicit formulations optimize the contact mode sequence rather than assuming it in advance, making contact models and transcription strategies tightly coupled.Shooting methods require gradients relating state and control changes to trajectory outcomes.
D. Contact Implicit Considerations: Direct collocation contact-implicit methods use complementary constraints, with high-order schemes typically assuming modes remain unchanged within each finite element.Impact handling can occur at element boundaries or within elements with different accuracy implications.
D. Contact Implicit Considerations: Impacts enforced at element boundaries require additional complementarity constraints, whereas allowing impacts within elements sacrifices integration accuracy.Relaxing LCP constraints introduces a separate accuracy–computational-complexity trade-off.
E. Summary: Direct methods remain the most attractive trajectory-optimization approaches in robotics, while DDP and sparse QP solvers offer routes toward faster shooting and collocation.Contact-implicit strategies require especially careful contact-modeling choices because those choices affect the available transcription approach.
E. Summary: Learning can support trajectory optimization by providing warm-start policies or trajectories, learned value functions, or simplified components such as footholds.These strategies are presented as complementary uses of learning around model-based optimization.
E. Summary: Reactive control components may execute plans generated with simplified models because fast OCP solutions still leave whole-body details to define.Instantaneous reactive schemes are widely used to generate motion directly or execute online trajectories.
E. Summary: Quadratic-program reactive controllers can solve instantaneous control problems very quickly, from hundreds of microseconds to a few milliseconds.They rely on suitable assumptions and objective–constraint formulations.

1) Task Dynamics:

Task dynamics convert geometric, velocity, force, and contact requirements into constraints involving robot accelerations, torques, and contact forces. Differentiation and task-space error definitions make these requirements suitable for optimization-based control.

Task dynamics: Differentiating a task error twice yields an expression affine in acceleration, combining the task Jacobian, its derivative, and explicit time dependence.For q̇ = ν, ë_i = J_i(q)ν̇ + J̇_i(q,ν)ν + a_i(q,ν,t), with a_i = ∂²e_i/∂t².
Task dynamics: Task regulation sets the desired task derivative or acceleration, producing equality or inequality constraints linear in the relevant control variables.The required differentiation order depends on whether the task becomes affine in ν̇, τ, or λ.
Task types: Geometric tasks represent errors between current and desired positions or orientations, covering center-of-mass, body, posture, gaze, and contact-related requirements.Non-Euclidean errors use a meaningful task-space difference operator rather than ordinary subtraction.
Task types: Other tasks directly constrain joint speeds, centroidal momentum, accelerations, torques, or contact forces without requiring task-error regulation.Examples include speed limits, momentum tasks, acceleration and torque limits, friction constraints, and direct force references.

3) Regulation of Equality Tasks:

Equality-task regulation uses derivative feedback, PD laws, or control Lyapunov functions, while contact and inequality constraints require special handling. Instantaneous enforcement remains limited by feasibility, discontinuities, and future state evolution.

3) Regulation of Equality Tasks:: Derivative-level equality tasks use desired derivative feedback, while geometric equality tasks commonly use PD acceleration regulation.Critical damping is typically obtained with K_d = 2K_p^1/2.
3) Regulation of Equality Tasks:: Constant PD gains track well near a trajectory but can cause large accelerations or slow convergence when task errors become large.Variable gains and clamping or scaling the desired acceleration are proposed remedies.
3) Regulation of Equality Tasks:: Hard-contact equality tasks commonly impose zero acceleration, although damping may better stabilize contacts during slippage.Contact initiation can rapidly change the optimization formulation and therefore the resulting controls.
3) Regulation of Equality Tasks:: A control Lyapunov function enforces exponential convergence through an inequality, but guarantees depend on persistent feasibility, which remains difficult with practical robot models.The CLF-QP condition is V̇_i ≤ −γ_iV_i.
4) Regulation of Inequality Tasks:: Velocity-level inequalities can be regulated using next-step conditions, whereas position-level inequalities are harder because they may conflict with acceleration constraints.The next-step method sets ė_i^d = −e_i/Δt and works well for small controller time steps.
4) Regulation of Inequality Tasks:: Position constraints remain precarious under instantaneous control, motivating predictive strategies that use lookahead over system evolution.Methods combining position- and acceleration-level inequalities can guarantee compatibility only under assumptions such as constant acceleration bounds.

B. Resolution

Instantaneous control assumes a fixed contact state and a short control period, allowing task aggregation into linear constraints. Solver design then trades variable elimination and numerical structure against computational cost and robustness.

B. Resolution: Instantaneous schemes assume the state is known and constant over a short control period, typically 1–10 ms, with a fixed contact state.These assumptions support solving the control problem within each cycle.
B. Resolution: Approximating friction cones as pyramids converts aggregated task, contact, and dynamics requirements into linear constraints on accelerations, contact forces, and torques.The resulting constraints separate non-contact tasks from contact constraints.
B. Resolution: The optimized variables are integrated or directly commanded depending on the robot interface: accelerations yield configurations or velocities, while torques are sent to torque-controlled robots.Position- and velocity-controlled robots integrate the computed acceleration once or twice.
B. Resolution: Regularization tasks help select a unique solution when the controller is underdetermined, while task conflicts require explicit arbitration during optimization.Typical regularizers include posture, zero contact force, or zero torque tasks.
B. Resolution: Variable elimination can reduce computation by exploiting dynamics or contact structure, but manually removing variables is useful only when it preserves solver-relevant properties.Examples eliminate torques, accelerations, or contact forces using system structure, positive definiteness, or contact nullspaces.
B. Resolution: The number of variables alone does not determine computational cost because elimination can destroy sparsity or convert simple bounds into general constraints.Solvers may handle numerical issues better when variables are retained.

2) Arbitrating conflict:

Because practical task sets often conflict, reactive controllers arbitrate violations through weighted or hierarchical priorities, commonly using quadratic programming. This preserves rapid instantaneous control while allowing extensions that incorporate longer-term objectives and contact effects.

2) Arbitrating conflict:: Conflicting task requirements are handled by assigning violation measures and prioritizing them through weighted sums, strict hierarchies, or both.The violation measure is commonly based on the L2 norm.
2) Arbitrating conflict:: Quadratic-program formulations retain top-priority inequalities and selected equalities as constraints, while minimizing weighted squared violations of lower-priority tasks.A representative use tracks a simplified-model trajectory while minimizing joint torques within bounds.
2) Arbitrating conflict:: QP-based reactive control is widely used because mature off-the-shelf solvers make constrained whole-body optimization accessible.Its development includes inverse-dynamics formulations handling unilateral contact forces.
2) Arbitrating conflict:: Reactive QPs can incorporate value-function terms, passivity-based methods, impact-robust controls, and soft-contact strategies.Value-function terms add long-term performance considerations to an otherwise instantaneous formulation.
2) Arbitrating conflict:: Hierarchical QPs let designers specify explicit priority levels, combine same-level tasks with weights, and allow top-priority constraints to remain infeasible.Lexicographic least-squares and hierarchical QP formulations support inequality constraints at multiple priority levels.
2) Arbitrating conflict:: Instantaneous methods complement predictive control by exploiting local linear structure to achieve rapid computation rates.The instantaneous formulation turns some nonlinear constraints into linear ones.

VII. OUTLOOK AND PROSPECTS

The survey identifies progress and open challenges in contact handling, model complexity, and numerical transcription for optimization-based legged-robot control. It highlights formal analysis, formulation expertise, and integration with reinforcement learning as priorities for future work.

Main trends for optimization with contacts: Contact-implicit methods increasingly avoid prescribing gait or contact sequences, but non-convexity and solution speed remain challenges.For near-term online optimization, fixing contact sequences and timing remains the most viable practical option.
Main trends in the dynamic models adopted for model-based optimization: Model-predictive control has increasingly adopted complex models, including full robot models, while non-convexity keeps simpler models relevant.The review links this trend to improved gradient-based methods and fast dynamics-derivative libraries, while identifying parallelization as a possible future direction.
Main trends for transcription: Differential dynamic programming and contact-aware collocation have gained emphasis, but convergence to infeasible solutions remains an open challenge across transcription methods.Specialized Riccati-like solvers and simultaneous methods may offer scalability and additional parallelism.
Formal Analysis: Formal theory for locomotion optimization remains limited, especially for stability, recursive feasibility, and robustness under bounded or stochastic uncertainty.Existing nonlinear MPC theory mainly addresses regulation to equilibrium or tracking feasible reference trajectories.
Reducing the Expertise Required: Model-based control still requires substantial expertise to design cost functions and constraints, leaving human-guided formulation and tuning as persistent bottlenecks.The survey notes that even simple tasks can have difficult-to-specify objectives, such as binary success for opening a door.
Optimal Control Versus or With RL?: Reinforcement learning offers generality and handles non-smooth contact-implicit problems without gradients, while model-based optimization can reduce exploration and support safer learning.The survey presents shared optimal-control fundamentals as a basis for combining the two approaches.