PaperlayerView exact revision on arXiv

Source-linked AI summary

MPC for Humanoid Gait Generation: Stability and Feasibility

Nicola Scianca, Daniele De Simone, Leonardo Lanari, Giuseppe Oriolo

arXiv:1901.08505v3cs.ROcs.SYeess.SY

TL;DR

Humanoid gait generation must address internal CoM/ZMP instability as well as recursive feasibility, problems not resolved merely by constraining the ZMP. IS-MPC uses a tail-dependent stability constraint and establishes that, with sufficient preview and an anticipative tail, recursive feasibility implies internal stability.

  • Problem

    A ZMP trajectory can admit CoM trajectories that diverge from it, and terminal constraints in MPC gait generation raise a recursive-feasibility question.

    Source: §I · pp. 1–2

  • Method

    IS-MPC constrains future ZMP velocities using the current system state, with the post-horizon tail chosen using available preview information.

    Source: §I · p. 2, A. Stability Constraint · p. 8

  • Results

    With an anticipative tail and sufficiently long preview, IS-MPC is recursively feasible, and recursive feasibility implies internal stability of the CoM/ZMP dynamics.

    Source: §X · p. 15

  • Takeaways & Limitations

    The appropriate stability constraint depends on future commanded motion, and preview information in the tail is essential to preserve feasibility.

    Source: §I · p. 2, §X · p. 15

Abstract

from arXiv · show

We present IS-MPC, an intrinsically stable MPC framework for humanoid gait generation which incorporates an explicit stability constraint in the formulation. The proposed method uses as prediction model a dynamically extended LIP where ZMP velocities are the control inputs, producing in real time a gait (including footsteps with the associated timing) that realizes omnidirectional motion commands coming from an external source. The stability constraint links the future ZMP velocities to the current system state so as to guarantee the essential requirement that the generated CoM trajectory is bounded with respect to the ZMP trajectory. Since the control horizon of the MPC algorithm is finite, only part of the future ZMP velocities are decision variables of the QP problem; the remaining part, called tail, must be either conjectured or anticipated using preview information on the reference motion. Several possible options for the tail are discussed, and each of them is shown to correspond to a specific terminal constraint. A theoretical analysis of the feasibility of the generic MPC iteration is developed and used to obtain sufficient conditions for recursive feasibility. Finally, it is proved that IS-MPC guarantees stability of the CoM/ZMP dynamics if it is recursively feasible. Simulation and experimental results on the NAO and the HRP-4 humanoids are presented to illustrate the performance of the proposed method.

I. INTRODUCTION

The paper frames humanoid gait generation as an internal-stability and recursive-feasibility problem, then introduces IS-MPC and its real-time footstep-generation framework. Its analysis links recursive feasibility to CoM/ZMP stability and identifies preview-dependent tail choice as central.

I. INTRODUCTION

  • Keeping the ZMP within the support polygon does not by itself ensure internal stability: CoM trajectories can diverge from the ZMP despite dynamic balance.The paper identifies boundedness of the CoM trajectory relative to the ZMP trajectory as the relevant stability issue.Source: §I · pp. 1–2
  • Earlier MPC gait methods generate ZMP and CoM trajectories under balance and kinematic constraints, while stability approaches include long horizons and terminal-state constraints.The paper cautions that a terminal constraint alone does not automatically establish internal stability in this setting.Source: §I · pp. 1–2
  • IS-MPC adds an explicit constraint linking future ZMP velocities to the current state, with the unoptimized post-horizon tail conjectured or anticipated.The paper discusses truncated, periodic, and anticipative tails, each corresponding to a specific terminal constraint.Source: §I · p. 2
  • With an anticipative tail and sufficiently long preview, IS-MPC is recursively feasible; recursive feasibility implies internal stability of the CoM/ZMP dynamics.The paper also argues that the appropriate terminal constraint depends on future commanded motion.Source: §I · p. 2

II. PROBLEM AND APPROACH

  • An external source supplies previewed omnidirectional velocity commands; the framework generates candidate footsteps and timing, then uses IS-MPC to produce actual footstep positions and a CoM trajectory.The paper assumes the control horizon does not exceed the reference preview horizon.Source: §II · pp. 2–3

III. CANDIDATE FOOTSTEP GENERATION

The footstep-generation module uses high-level reference velocities to choose step timing and candidate locations. Its timing rule adjusts both step duration and length with Cartesian speed, while leaving angular velocity out of the rule.

III. CANDIDATE FOOTSTEP GENERATION

  • Candidate footsteps are generated synchronously with IS-MPC from high-level reference velocities, with step timing and candidate locations selected before the MPC stage.Footstep timing is variable, so the number of footsteps in the preview horizon may change at each sampling instant.Source: §III · p. 3
  • Step timing and footstep orientation are generated outside IS-MPC, preserving its linear structure while allowing it to adapt footstep positions.The position adaptation is intended to retain reactivity to disturbances.Source: §III · p. 3

A. Candidate Footstep Timing

  • The step-duration rule uses Cartesian speed and cruise parameters; deviations from cruise speed change both step duration and step length.The cruise speed is the ratio of cruise step length to cruise step duration.Source: A. Candidate Footstep Timing · pp. 3–4
  • The reference angular velocity is excluded from the timing rule because curved and straight paths are treated similarly at the same Cartesian speed.At zero Cartesian speed, the rule yields the maximum step duration for turning in place.Source: A. Candidate Footstep Timing · p. 4
  • The timing rule is iterated over the preview horizon to obtain footstep timestamps, stopping when the next timestamp would fall outside that horizon.The figure compares the proposed speed-dependent duration rule with constant-duration and constant-step-length alternatives.Source: A. Candidate Footstep Timing · p. 4, Figure 2 · p. 4

B. Candidate Footstep Placement

Candidate footsteps are distributed around a reference path integrated from the commanded motion, with their timing and the robot’s kinematic constraints taken into account. IS-MPC then enforces ZMP, kinematic, and CoM/ZMP stability constraints.

B. Candidate Footstep Placement

  • Candidate footsteps are distributed around an integrated reference trajectory according to their timing, while accounting for the robot’s kinematic constraints.The template model supports omnidirectional paths, including lateral and diagonal walks; the figure illustrates circular, L-shaped, and diagonal motion.Source: B. Candidate Footstep Placement · p. 4, Figure 3 · p. 5
  • The candidate footstep sequence and its timing are sent to IS-MPC, which determines final footstep positions while leaving orientations and timing unchanged.Examples include circular walking with orientation tangent to the path and lateral or diagonal walking with fixed orientation.Source: B. Candidate Footstep Placement · p. 4

IV. IS-MPC: PREDICTION MODEL AND CONSTRAINTS

  • IS-MPC constrains the ZMP to the support polygon, enforces kinematic feasibility, and adds a stability constraint that bounds the CoM trajectory relative to the ZMP.The first two constraint types apply throughout the control horizon; the stability constraint is a scalar condition for each coordinate.Source: §IV · p. 5

A. Prediction Model

The prediction model uses a dynamically extended LIP with ZMP velocity as its control input. ZMP constraints enforce balance in single and double support, with a conservative linear moving constraint used during double support.

A. Prediction Model

  • The prediction model uses a dynamically extended LIP with ZMP velocity as the control input, held piecewise constant over sampling intervals.The LIP describes CoM motion for a biped on a flat horizontal floor at constant height, without rotational effects.Source: A. Prediction Model · p. 5
  • Each iteration plans over Tc≤Tp and selects ZMP-velocity inputs and footstep positions for steps within the control horizon.Footsteps do not appear in the prediction model; they enter through the constraints.Source: A. Prediction Model · pp. 5–6

B. ZMP Constraints

  • In single support, the admissible ZMP region is approximated by a rectangle centered on the footstep and oriented with it.The constraint uses the piecewise-linear ZMP profile.Source: B. ZMP Constraints · p. 6
  • Sampled-time ZMP constraints enforce the support-polygon bound throughout the horizon because ZMP motion is linear within each sampling interval.The constraint is imposed throughout the control horizon and for the associated footsteps.Source: B. ZMP Constraints · p. 6
  • During double support, a same-shaped ZMP region roto-translates between footsteps, remaining inside the support polygon with a slightly conservative linear constraint.The moving constraint avoids the nonlinear boundary of the convex hull of the two footsteps.Source: B. ZMP Constraints · p. 6, Figure 6 · p. 6

C. Kinematic Constraints

The section specifies kinematic limits on footstep placement and an explicit stability constraint. The constraint links future ZMP velocities to the current state so the CoM remains bounded relative to the ZMP.

C. Kinematic Constraints

  • Each footstep is restricted to a support-foot-oriented rectangle displaced in the coronal direction, enforcing the robot’s kinematic limits.The constraint applies to all footsteps in the control horizon.Source: C. Kinematic Constraints · p. 6

V. IS-MPC: ENFORCING STABILITY

  • Because the LIP is inherently unstable, a ZMP inside the support polygon can still accompany CoM divergence; the stability constraint requires bounded CoM motion relative to the ZMP.Divergence can make the gait infeasible in practice because of the robot’s kinematic limitations.Source: §V · pp. 6–7

A. Stability Constraint

  • For any input ZMP trajectory, one special initialization of the unstable CoM component cancels divergence; the stability constraint enforces this initialization against the current state.The constraint is rearranged to constrain control variables so the stable initialization matches the state at the start of the horizon.Source: A. Stability Constraint · pp. 7–8
  • Future ZMP velocities beyond the control horizon are unknown, so preview information is used to conjecture a tail and make the stability constraint causal.The constraint depends on an infinite sum of those future velocities.Source: A. Stability Constraint · p. 8

B. Tails

The tail represents assumed ZMP velocities beyond the finite control horizon; different assumptions yield corresponding stability and terminal constraints. A zero-velocity truncated tail suits a preview indicating the robot will stop at the horizon.

B. Tails

  • The paper considers truncated, periodic, and anticipative tails, each corresponding to a specific terminal constraint.The choice depends on the assumed behavior of ZMP velocities after the control horizon.Source: B. Tails · p. 8

1) Truncated Tail:

  • A truncated tail sets post-horizon ZMP velocities to zero, a sensible choice when preview indicates the robot will stop at the control horizon.Its terminal constraint is equivalent to the capturability constraint introduced in.Source: 1) Truncated Tail · p. 8

B. Tails

  • A periodic tail infinitely repeats the control-horizon ZMP velocities when reference velocities are periodic, including constant references.The control horizon is typically chosen as the gait period or a multiple of it.Source: 2) Periodic Tail · p. 8

2) Periodic Tail:

For a periodic tail, the infinite sums in the constraints can be rewritten. An anticipative tail uses previewed footstep information to produce a finite stability-constraint expression suitable for real-time implementation.

2) Periodic Tail:

  • With a periodic tail, the infinite summation can be rewritten to obtain the stability and terminal constraints.The terminal constraint can also be rewritten using the LIP dynamics.Source: 2) Periodic Tail · p. 8

3) Anticipative Tail:

  • The anticipative tail samples the derivative of an admissible ZMP trajectory generated from candidate footsteps beyond the control horizon.After the preview horizon, the residual tail can be truncated or made periodic; the resulting stability constraint has finitely many terms and remains suitable for real-time implementation.Source: 3) Anticipative Tail · pp. 8–9

VI. IS-MPC: ALGORITHM

  • Each IS-MPC iteration solves a QP using the prediction model and constraints, including the stability constraint.Source: §VI · p. 9

A. Formulation of the QP Problem

The QP combines kinematic and axis-separated stability constraints, with the stability expression determined by the selected tail. Simulations show that the embedded constraint preserves CoM boundedness when standard MPC loses stability at a short horizon or increased CoM height.

A. Formulation of the QP Problem

  • The QP includes kinematic constraints and separate x- and y-axis stability constraints, whose expression depends on the selected truncated, periodic, or anticipative tail.The stability expression is equivalent to imposing the corresponding terminal constraint; the CoM coordinate enters through xu.Source: A. Formulation of the QP Problem · p. 9

B. Generic Iteration

  • Each iteration solves the QP, extracts the first control samples, integrates the model over the next sampling interval, and returns the CoM trajectory and footstep sequence.Initialization uses current CoM position and velocity and ZMP position, from measurements or model prediction.Source: B. Generic Iteration · p. 9

VII. IS-MPC: FEASIBILITY AND STABILITY

  • The feasibility and stability analysis establishes conditions for recursive feasibility and proves internal stability when IS-MPC is recursively feasible.The section evaluates the controller independently of the footstep-generation module.Source: §VII · p. 9

A. Effect of the Stability Constraint

B. Feasibility Analysis

The stability constraint improves boundedness but shrinks the set of states for which the QP has a solution. The feasibility analysis characterizes that set and shows how preview of candidate footsteps can support recursive feasibility.

B. Feasibility Analysis

  • The stability constraint reduces the QP feasibility region and can leave the system in a state with no solution satisfying all constraints.Feasibility is analyzed independently of whether a particular iteration is feasible.Source: B. Feasibility Analysis · p. 10
  • Preview information in the candidate-footstep sequence can be used to achieve recursive feasibility, meaning feasibility at one iteration is retained at later iterations.The section proceeds from determining feasibility at a given time to analyzing this recursive property.Source: B. Feasibility Analysis · pp. 10–11

1) Feasibility Regions:

  • With given footsteps and fixed orientation, the feasibility problem separates into decoupled x- and y-coordinate problems; the general coupled case can use a coordinate change.The analysis assumes fixed footsteps, so kinematic constraints are not enforced.Source: 1) Feasibility Regions · p. 11
  • Proposition 4 characterizes feasibility through an admissible range for xu, which identifies the feasible region in state space via the prediction-model state relation.The range is the condition for solvability of the current IS-MPC QP.Source: 1) Feasibility Regions · p. 11
  • The admissible range's extension depends on the ZMP-region dimension and approaches dz,x as the control horizon increases, while its midpoint depends on the selected tail.The range shifts toward the next ZMP admissible region as a step approaches in the illustrated anticipative-tail cases.Source: 1) Feasibility Regions · p. 11, Figure 12 · p. 12

2) Recursive Feasibility:

For an anticipative tail, a sufficiently large preview horizon provides a sufficient condition for recursive feasibility. The required horizon depends on robot and foot properties, and the condition does not rule out shorter horizons or other tails.

2) Recursive Feasibility:

  • With an anticipative tail, IS-MPC is recursively feasible if the preview horizon Tp is sufficiently large.This is a sufficient condition, established by showing feasibility at the next iteration from feasibility at the current one.Source: 2) Recursive Feasibility · p. 12
  • A longer preview horizon is needed for taller or faster robots, or robots with more compact feet.The stated factors are larger η or ZMP-velocity bound and smaller dz,x, respectively.Source: 2) Recursive Feasibility · p. 12
  • The preview-horizon condition is sufficient only, so recursive feasibility may also hold with a shorter horizon or a different tail.The paper gives a case where a periodic tail is a sufficiently accurate conjecture and recursive feasibility is achieved.Source: 2) Recursive Feasibility · p. 12

3) Recursive Feasibility — Simulations:

The tail choice determines whether IS-MPC preserves recursive feasibility, and recursive feasibility guarantees internal stability. The framework also permits shorter control horizons, while its simulations demonstrate response to changing and turning motion commands.

3) Recursive Feasibility — Simulations:

  • For regular footsteps, the truncated tail loses feasibility, while the periodic tail preserves it; for forward-then-backward steps, the periodic tail fails and the anticipative tail preserves feasibility.The tail must match the expected ZMP motion: periodic is suitable for the regular sequence, while anticipation captures the irregular reversal.Source: 3) Recursive Feasibility — Simulations · p. 13, Figure 13 · p. 13, Figure 14 · p. 13

C. Recursive feasibility implies stability

  • If IS-MPC is recursively feasible, its CoM trajectory is bounded with respect to the ZMP; an anticipative tail with sufficient preview can guarantee recursive feasibility.The proof links repeated enforcement of the stability constraint to internal stability, provided the tail approximation is sufficiently accurate.Source: C. Recursive feasibility implies… · p. 13, D. Wrapping up · p. 13

D. Wrapping up

  • The control horizon may be arbitrarily small, but reducing it shrinks the feasibility region; after initialization within that region, recursive feasibility depends on preview horizon.Shorter control horizons can reduce computation and the interval over which candidate footsteps are needed.Source: D. Wrapping up · pp. 13–14

VIII. SIMULATIONS

  • In simulation, an abrupt increase in commanded forward velocity was realized by increasing both step length and frequency, while a separate simulation generated a cusp trajectory.The cusp simulation used changing forward velocity and angular velocity commands, with an anticipative tail.Source: §VIII · p. 14

IX. EXPERIMENTS

Experiments on NAO and HRP-4 demonstrate locomotion under forward-backward and L-shaped commands, and measured HRP-4 ZMP behavior is reported alongside admissible-region constraints. The conclusions connect recursive feasibility to internal stability and state conditions for feasibility and preview.

IX. EXPERIMENTS

  • HRP-4's measured ZMP violated the restricted admissible-region constraints but remained within the original simulation region.The comparison is between the measured ZMP reconstructed from ankle force-torque sensors and the nominal ZMP region.Source: §IX · p. 15, Figure 19 · p. 15
  • NAO and HRP-4 completed forward-backward and L-shaped walking experiments.The experiments used opposite forward velocities for the forward-backward motions and sequential forward and lateral velocities for the L-shaped motions.Source: §X · p. 15, §IX · p. 15, Figure 20 · p. 16

X. CONCLUSIONS

  • IS-MPC uses an explicit stability constraint whose tail can be selected according to available preview information to accommodate different gaits.The conclusions state that the constraint options can be interpreted as terminal constraints.Source: §X · p. 15
  • The authors report that anticipative-tail IS-MPC is recursively feasible with sufficiently long preview, and that recursive feasibility implies internal stability.The paper presents the method as the first MPC-based gait generation approach with an explicit proof of internal stability.Source: §X · p. 15
  • The method is reported to apply to NAO and HRP-4 without significant adaptation; on-board NAO experiments show the algorithm is viable despite limited computing capabilities.Future work includes robustness to unmodeled dynamics and disturbances, extension to 2.5D terrain, and investigating learning techniques with MPC to improve performance.Source: §X · pp. 15–16

APPENDIX

The appendix collects properties used in the proofs, including linearity and time shifting.

APPENDIX

  • The appendix introduces compact notation for properties used in the proofs.It states that Properties 1–3 follow by explicitly computing the integral in (A.1).Source: APPENDIX · p. 16
  • Property 1 concerns linearity in xz(t).The passage identifies the property but does not state its displayed relation.Source: APPENDIX · p. 16
  • Property 4 relates the stability condition for a time-shifted xz(t−T) to the condition for the original xz(t).It is introduced for the case where xz(t) = 0 for t < tk.Source: APPENDIX · pp. 16–17
Loading 1901.08505v3…