Leveraging Cone Double Description for Multi-contact Stability of Humanoids with Applications to Statics and Dynamics

Stéphane Caron, Quang-Cuong Pham and Yoshihiko Nakamura. RSS 2015, Roma, Italy, July 2015.


We build on previous works advocating the use of the Gravito-Inertial Wrench Cone (GIWC) as a general contact stability criterion (a "ZMP for non-coplanar contacts"). We show how to compute this wrench cone from the friction cones of contact forces by using an intermediate representation, the surface contact wrench cone, which is the minimal representation of contact stability for each surface contact. The observation that the GIWC needs to be computed only once per stance leads to particularly efficient algorithms, as we illustrate in two important problems for humanoids : "testing robust static equilibrium" and "time-optimal path parameterization". We show, through theoretical analysis and in physical simulations, that our method is more general and/or outperforms existing ones.

Humanoid climbing a box using tilted support surfaces


  title = {Leveraging Cone Double Description for Multi-contact Stability of Humanoids with Applications to Statics and Dynamics},
  author = {Caron, St{\'e}phane and Pham, Quang-Cuong and Nakamura, Yoshihiko},
  booktitle = {Robotics: Science and System},
  year = {2015},
  month = jul,
  doi = {10.15607/RSS.2015.XI.028},


In your previous work, you provided an analytical formula for the contact wrench cone. Why don't you use it in this paper?

Unfortunately the analytical formula of the contact wrench cone is only known (yet) for a single contact. In multi-contact, the best call so far is to use numerical algorithms such as the double description method.

According to Figure 2, you use the double-description method to compute the span matrix \(V_{surf}\) at each contact. Is this necessary?

It is not, as we later found out: local span matrices are straightforward to compute, as detailed for instance in the introduction of this paper. The only point where the double description remains necessary so far is for computing the gravito-inertial face matrix \(U_{stance}.\)

What is the link between the matrix \(U_{stance}\) in this paper and the matrices \(A_O\) or \(A_G\) used in your 3D-COM pattern generator?

In this paper, the gravito-inertial wrench coordinates \(w_{GI} = (f_{GI}, \tau_{GI})\) are taken at the origin \(O\) of the world frame. Using proper notations, we should have written \(w^{gi}_O\) to acknowledge this reference point. (We apologize for the non-standard notations.) Our later works uses the net contact wrench, i.e. the sum of all contact wrenches applied to the robot, which yields the opposite of the gravito-inertial one: \(w^{c}_O = -w^{gi}_O.\) Therefore, the face matrices are opposed as well: \(U_{stance} = -A_O.\)

Given an \(n \times m\) matrix \(V,\) is it the case that its dual (face or H-representation) matrix \(U = V^F\) has shape \(m \times n?\)

It is not always the case, as you can see in Table I of the paper. In single support, redundant inequalities simplify and the \(6 \times 16\) span matrix of the wrench cone has a \(16 \times 6\) face dual. However, in double-support the dual of the \(6 \times 32\) span matrix typically has more than 100 rows.

The cdd library gives me the error "Numerical inconsistency is found. Use the GMP exact arithmetic." What can I do?

It may happen that your problem is "doable" but you ended up hitting some near-singular configuration. In such cases, a simple hack is to perturb the input (contact locations, or coordinates where the CWC is taken) by some epsilon.

Another cause of numerical instabilities are vectors that are "almost" rational, for instance with coordinates such as 0.4 + 1e-12. Rounding up coordinates to a sound number of decimals can filter out those.

If none of the above apply, you can try with rational rather than floating point numbers. In that case, I'd advise using PPL or its Python wrapper pyparma rather than cdd.

What about calling the Canonicalize() function in cdd to remove redundant rays from the input V-description?

In my experience this extra step only make matters worse (with regards to numerical-inconsistency errors), so I would advise against doing it. Also, note that, even if your input V-description is irreducible, cdd may output you a non-minimal H-description.

Numerical instabilities seem to happen more often in stances with more contacts. Why?

Unfortunately I have only an intuition here: making more contacts implies a resultant polyhedron with more faces, i.e. with more rays in the V-description and more hyperplanes in the H-one. This increases the risk of "tricky" faces (of very small area) in the output polyhedron, especially if some of your input rays are nearly aligned. My guess is that these make the double-description fail when it tries to cut (c.f. Fukuda's paper on the algorithm) by an "almost meaningless" hyperplane.

One footnote of the paper mentions Dirac fields. Are you referring here to the Dirac delta function and its higher dimensional versions?

Yes, in this case we refer to the Dirac delta function, that is to say, a distribution that concentrates forces at the vertices of the contact area. You will find a bit more discussion on this point, along with a proof of the corresponding proposition, at the end of Section III of this study of surface contacts.
© Stéphane Caron — All content on this website is under the CC BY 4.0 license.