To appear in the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013.
This copy is for personal use only. c 2013 IEEE/RSJ
Prints will be available at http://ieeexplore.ieee.org shortly.

Classical Grasp Quality Evaluation: New Algorithms and Theory
Florian T. Pokorny and Danica Kragic

Abstract— This paper investigates theoretical properties of awell-known L1 grasp quality measure Q whose approximationQ−l is commonly used for the evaluation of grasps and where
the precision of Q−
l depends on an approximation of a cone bya convex polyhedral cone with l edges. We prove the Lipschitz
continuity of Q and provide an explicit Lipschitz bound that canbe used to infer the stability of grasps lying in a neighbourhoodof a known grasp. We think of Q−
l as a lower bound estimate
to Q and describe an algorithm for computing an upperbound Q+ . We provide worst-case error bounds relating Q
and Q−
l . Furthermore, we develop a novel grasp hypothesis
rejection algorithm which can exclude unstable grasps much
faster than current implementations. Our algorithm is basedon a formulation of the grasp quality evaluation problem as
an optimization problem, and we show how our algorithm
can be used to improve the efficiency of sampling based grasp
hypotheses generation methods.

I. I NTRODUCTION
One of the key problems in robotics is the questionof how to generate viable grasps. Many aspects, such as
the kinematics of a robot, collision avoidance, the object
representation, resistance to noise and task constraints fora particular manipulation problem need to be investigatedto form a useful grasp. This work focusses on grasping at
the contact level which forms the foundation for many stateof the art grasp synthesis algorithms [1], [2], [3]. Graspingat the contact level is concerned with the generation ofpoint-contacts on an object of interest such that physicalconstraints, formulated in terms of the forces acting on an
object, are satisfied. In their pioneering work two decadesago, Ferrari and Canny [4] introduced several grasp quality
measures which have found a wide application in robotics[2] and which have sparked the creation of several closely
related grasp quality measures [3]. We investigate an L1
grasp quality measure Q introduced in [4] which is a functionof the contact points and contact surface normals formedby the grasp and which, for a particular friction coefficient,takes positive values if the resulting grasp can withstandwrenches in an arbitrary direction. Importantly, the magnitude of Q furthermore yields a measurement which allows
to rank grasps by their physical stability. In this paper, weestablish some of the basic – as of yet unstudied – propertiesof the function Q which can be estimated by a function
Q−l defined in terms of an approximation of the Coulomb
friction cones by regular polyhedral cones with l edges (seeFig. 1). All major robot grasp simulation environments such
The authors are with the Computer Vision and Active Perception Lab,
Centre for Autonomous Systems, KTH Royal Institute of Technology,
Stockholm, Sweden {fpokorny, dani}@kth.se
This work was supported by the EU project FLEXBOT (FP7-ERC279933) and the Swedish Foundation for Strategic Research.

(a) F (0, 0, 1)(b) F3 (0, 0, 1)(c) F8 (0, 0, 1)(d) F20 (0, 0, 1)(e) F (0, 0, 1)(f) F3 (0, 0, 1)(g) F8 (0, 0, 1)(h) F20 (0, 0, 1)

Fig. 1. Friction cone F (0, 0, 1) in normal direction (0, 0, 1) in a) anduniform polyhedral cone approximations of that cone with 3, 8, and 20
edges in b)-d). The top row of figures assumes a friction coefficient ofµ = 1 while the bottom row displays the corresponding cones for µ = 21 .

as GraspIT [5], OpenGrasp [6] and Simox [7] implement
such an approximation. Based on our theoretical insights,
we devise an algorithm for the rejection of unstable grasp
configurations which we show in experiments to be up to 600
times faster than an implementation based solely on Q−
l . Our
contributions can be summarized as follows:• We rephrase a characterization of Q as a minimization
problem described by [8] and extend their work byproviding a coordinate independent efficient descriptionof the objective function.
• We suggest and evaluate a new optimization method for
determining an upper bound Q+ for Q.
−• We prove results on the continuity properties of Ql .
• We prove that Q is Lipschitz continuous and provide
an explicit Lipschitz constant.
−• We relate the classical approximation Ql of grasp
quality to Q and provide a worst-case error bound.
• We introduce a very fast algorithm for removing the
majority of unstable grasp hypotheses from a set ofgrasps candidates which gives rise to a new efficientmethod for finding stable grasps.
Our paper is structured as follows: in Section II, we review
related work and recall the basic definition of Q−
l and Q.
In Section III, we begin our investigation of the theoreticalproperties of L1 grasp quality and devise a novel efficientalgorithm for the rejection of unstable grasps and for theestimation of upper bounds. In Section IV, we present anevaluation of the theory and the algorithms developed in
Section III. Finally, we conclude our work and describe
future work in Section V.

II. BACKGROUND AND RELATED WORK
Consider a grasp configuration g with m contacts
c1 , . . . , cm ∈ R3 located on some surface with corresponding
inward pointing unit normal vectors n1 , . . . , nm ∈ S2 ={x ∈ R3 : kxk = 1} and centre of mass z ∈ R3 :g = (c1 , . . . , cm , n1 , . . . , nm , z).

(1)

For any given inward pointing normal direction n ∈ S2 , theCoulomb friction model with friction coefficient µ > 0 statesthat any force f ∈ R3 that can be exerted without slippage ata point p on a surface and with inward pointing normal n has
to lie in the friction cone F (n) = {f ∈ R3 : kf t k 6 µf ⊥ },where f = f ⊥ n + f t , f ⊥ ∈ R and f t ∈ R3 is a vector
tangent to the object (i.e. satisfying hf t , ni = 0).
In the robotics literature, this constraint is often madeexplicit by fixing an arbitrary orthonormal basis of the planetorthogonal to n, i.e. t1 , t2 , such thatp f = αt1 + βt2 and2F (n) = {f = λn + αt1 + βt2 : α + β 2 6 µλ}. Here,
we shall avoid this choice t1 , t2 and work instead with acoordinate-independent formulation of the friction cones. We
thus have F (n) = {f ∈ R3 : kf − hf, nink 6 µhf, ni},
where h, i denotes the standard inner product and k.k thecorresponding norm on R3 . To every force f at contact c
and for a centre of mass z, we can associate the wrench
wc,z (f ) = (f, (c − z) × f ) ∈ R6 . In [4], the space of all
wrenches (w1 , . . . , wm ) which P
can be exerted at (c1 , . . . , cm )musing the grasp g and such that i=1 fi⊥ 6 1 is considered.
Any allowable such wrench lies inP
the convex hull W =mConv({0} ∪ S(g)),
where
S(g)
=
{
i=1 αi wci ,z (fi ) : fi ∈Pm
D(ni ), αi > 0, i=1 αi = 1} = Conv({wc1 ,z (D(n1 )) ∪. . . ∪ wcm ,z (D(nm ))}), and where
D(n) = {f ∈ R3 : hf, ni = 1, and kf − hf, nink 6 µ}denotes the disc obtained by intersecting the cone F (n) withthe plane normal to n and ‘at height one’. Since this discis the convex hull of a circle D(n) = Conv(C(n)), where
C(n) = {f ∈ R3 : hf, ni = 1 and kf − hf, nink = µ}, we
finally have that
S(g) = Conv(wc1 ,z (C(n1 )) ∪ . . . ∪ wcm ,z (C(nm ))).

grasp) precisely if arbitrary small wrenches of maximal norm
Q(g) can be resisted by the grasp. The main downside of theabove approach is that there currently exists no analytic wayof determining Q(g). The earlier work of [4] studied Q using
a different method by introducing an approximation by afunction Q−
l which we shall discuss next. An alternative approach of [8] showed that a numerical optimization of Eq. 2
with a standard out-of-the-box matlab optimization function
can also be used to determine q(g) approximately, while [9]approximate q(g) by iteratively growing a polyhedral convex
hull approximation to S(g).
Approximate L1 grasp quality: Q−lFerrari and Canny [4] defined an algorithm that provides
an approximation to Q. All popular grasp simulation
environments such as GraspIt [5], Simox [7] and OpenGrasp[6] implement a version of this algorithm. To approximate
D(n), one proceeds by using l > 3 edges f1 , . . . , fl ∈ C(n)such that D(n) ≈ Conv({f1 , . . . , fl }); see Fig. 1 for an
illustration. If we space these edges uniformly, so that
2πj
fj = n + µ(cos( 2πjl )t1 + sin( l )t2 ), we obtain a regularapproximation Dl (n) = Conv({fj : j = 1, . . . , l}) of thedisc D(n), so that D(n) ≈ Dl (n) and an approximation
Fl (n) = Conv({0} ∪ Dl (n)) of the truncated friction cone,so that Fl (n) ≈ Conv({0} ∪ D(n)) as displayed in Fig. 1.
Note that this definition of fj depends on a choice oforthonormal basis t1 , t2 for the tangent space orthogonal
to the line spanned by n. Using the above approximation,
one then computes an approximation of S(g) by Sl− (g) =Conv ({wij = wci ,z (fij ) : i ∈ {1, . . . , m}, j ∈ {1, . . . , l}}),where fij for j = 1, . . . , l are equally spaced edges onC(ni ). A quality measure Q−
l is then defined as the distancefrom the origin to the closest facet of Sl− (g) if the origin is
contained in the interior. If this is not the case, we define
the quality to be equal to zero. In order to compute Q−
l (g),
all major state of the art implementations then use the
Quickhull library [10] which converts the description of theconvex hull Sl− (g) into its dual form as an intersection ofaffine half-spaces, where λj ∈ R, vj ∈ R6 , kvj k = 1:

Exact L1 grasp quality: Q
Let S be a bounded convex set and denote by d(0, S) thesigned distance from the origin to S, so that −d(0, S) is theradius of the largest ball around the origin which still fits
inside S if such a ball exists and it is the negative of theradius of the largest ball entirely outside Int S(g) otherwise.
The support function hS (z) = sups∈S hs, zi is a convex
function and −d(0, S) can be expressed as (c.f. [8] up achange in sign and notation):−d(0, S) = min hS (z).
kzk=1

(2)

Up to a change in sign, the work [8] defines the quality ofa grasp by considering q(g) = −d(0, S(g)). The function
q can take negative values and Q(g) = max(0, q(g)) =−d(0, Conv({0} ∪ S(g)) is positive (indicating a stableSl− (g) =N\{x ∈ R6 : hx, vj i 6 λj },

(3)

j=1

and which can then be used for computing grasp quality−
since Q−l (g) = max(0, minj λj ). Recent work that uses Ql
includes [2], where a sampling based strategy towards thedetermination of a stable grasp is presented. The work of[11] uses the approximation Q−
l together with a gradient
based approach to find such grasps, while [8] investigatesq instead. Recent examples of the usage and developmentof grasp quality measures includes the work of [12] and[13] where kinematic constraints are also incorporated. Moreclassically, the work of [14] defines a quality measurethat relies on a polyhedral cone approximation, but which
decouples moments from forces.

III. T HEORETICAL CONTRIBUTIONSIn this section, we investigate some of the basic but
previously unstudied properties of the grasp quality measuresQ−l and Q.
Computational complexity and error estimates
Let us begin our discussion of Q−
l and Q by having a lookat the time-complexity for computing Q−
l in practice. As canbe seen in Fig. 2(a), the time required to compute Q−l scalesrather unfavourably as the number l of edges per frictioncone is increased. Since sampling based grasp hypothesis
generation methods such as [2] typically require thousandsof evaluations of Q−
l , a low number of edges between 6 and 8
is often chosen in real-world applications. Our first task shallbe to describe worst-case error bounds for the approximationof Q by Q−l .
200

approximations Fl converge to F as the number l of edges
is increased. This yields the second statement.
Note that, since Q(g) = max(0, q(g)), the above lemma
tells us also that q(g) can be approximated by Q−
l (g) forsufficiently large l if q(g) > 0. The function q does howevercontain additional information when it is negative. Notehere that some implementations define Q−
l (g) = minj λj ,using the affine half-plane description of Sl− (g). In thiscase, negative values of Q−
l can be attained. When the grasp
quality is defined in this way and when it is negative, Q−l (g)is the signed distance to the closest hyperplane {x ∈ R6 :hx, vj i 6 λj } among the hyperplanes describing Sl− (g)which is not necessarily a good approximation to q(g) forsmall l. We have the following result:Lemma 3.2. Suppose Q−
l (g) is computed using l uniformly
spaced edges to approximate the friction cones, and supposethat the friction coefficient is given by µ > 0. Define

time (sec.)defErr(r, l) =

150

50
0

5

10
l

15

20

(a) Mean computation time in seconds for Q−
l for 10000 uniformly sampled
grasps with three contact points c1 , c2 , c3 such that kci k 6 2, foruniformly sampled corresponding normals ni in the sphere S2 and for
friction coefficient µ = 1. The centre of mass z was set to 0 for eachgrasp. The mean is obtained from 10 runs of the experiment.

Err(r, l)

1.5
1
0.5
0

Q−
l (g) − Q(g) ,where r > 0 and g denotes a grasp with m contact points
ci , normals ni ∈ S2 and with centre of mass z as in Eq. 1.
Then Err(r, l) 6 µ(1 + r)(1 − cos( πl )).

100

0

max

g:kci −zk6r, ∀i=1,...,m

0

5

10
l

15

20

(b) Maximal approximation error bound Err(r, l) (vertical axis) for approximating each friction cone using various numbers of uniformly spacededges (horizontal axis), for friction coefficient µ = 1 and for r = 2.
Fig. 2.

Let us first state a rather simple fact:
Lemma 3.1. For any grasp g, we have 0 6 Q−
l (g) 6 Q(g).
Furthermore, kQ(g) − Q−
(g)k
→
0
as
l
→
∞
when Q−ll (g)is computed using a uniform approximation of the friction
cones with l edges.
Note that Q(g) (Q−l (g) respectively) is equal to the

Proof.
radius of the largest ball centred at the origin and inside
S(g) (Sl− (g) respectively) if such a ball exists and zerootherwise. Furthermore, Sl− (g) ⊂ S(g) for all l ∈ N which
implies the first statement. Finally, the convex hull Sl− (g)clearly converges to S(g) as l → ∞, since the friction cone

Proof. Note that µ(1−cos( πl )) is the maximal distance fromany point on the disc D(n) to the approximation Dl (n) for
arbitrary n ∈ S2 . Given wrenches w = (f, (c − z) × f ) and
w0 = (f 0 , (c − z) × f 0 ) with kf − f 0 k 6 ε, we observe thatkw − w0 k 6 kf − f 0 k + kc − zkkf − f 0 k
6 ε(1 + kc − zk).
To prove the result, we only need to consider g for whichq(g) > 0 since otherwise both Q−
l (g) and Q(g) =max(0, q(g)) are zero. Suppose there exists g such that−kci − zk 6 r and Q(g) − Q−l (g) = q(g) − Ql (g) =π∗
6λ > µ(1 + r)(1 − cos( l )). Consider z ∈ R , kz ∗ k = 1
such that −d(0, Sl− (g)) = hS − (g) (z ∗ ). Then, by definition,l−∗Q−l (g) = max(0, hS − (g) (z )) and hence Sl (g) ⊆ {x ∈ldefR6 : hx, z ∗ i 6 hS − (g) (z ∗ )} ⊆ H = {x ∈ R6 : hx, z ∗ i 6l∗Q−l (g)}. Consider p = q(g)z . We have kpk = q(g),so p ∈ S(g), and furthermore, since d(p, H) = λ, we−
have
Pm d(p, Sl (g)) > λ. Now p can be expressed as p =α (f , (c −z)×fj ), for some fj ∈ D(nj ) and αj > 0,
Pj=1 j j j ˆαLet fj be the closest point to fj in Dl (nj ) andj j = 1.Pm
define p̂ = j=1 αj (fˆj , (cj − z) × fˆj ). Clearly, p̂ ∈ Sl− (g),
but

X 
kp − p̂k 6
αj kfˆj − fj k + kfˆj − fj kkcj − zkjπ
6 µ(1 + r)(1 − cos( )) < λ.
lHence, we have arrived at a contradiction.
Figure 2(b), displays the convergence of these errors. Forl = 20, we obtain a maximal error of 0.037 for r = 2. Note
that, while the computational complexity blows up quickly
as l → ∞, the error bound converges rather slowly to zero.

Continuity

Theorem 3.3. There does not exist any continuous edgeassignment f : S2 → R3 such that f (n) ∈ C(n) for alln ∈ S2 , and where f is defined on the whole sphere of unit
normal directions S2 .

so that the argument of the exponential tends to zero andis continuous, resulting in the identity matrix after exponentiation. The argument of the exponential is however
not continuous as n → (0, 0, −1) which can be seen byconsidering a normal on a small circle around the southpole: let n = (sin ε cos θ, sin ε sin θ, − cos ε). Then we cancompute that, for small ε > 0, R(n) = e(π−ε)ξ(− sin θ,cos θ,0) .
Since this formula still depends on θ as ε → 0, we see that
there is no unique limit as ε → 0 which illuminates thediscontinuity predicted by the theorem above. We shall use
one of the possible limits,


1 0
0
π
eπξ(−1,0,0) =  0 −1 0 (using θ = ),2
0 0 −1

Proof. Suppose there was such an assignment. The vectors
v(n) = f (n) − n are non-zero and lie in the tangent plane
Tn S2 of the sphere S2 at n and hence form a non-vanishingcontinuous vector-field on S2 . However, since the Eulercharacteristic χ(S2 ) = 2, any continuous vector field on S2
must have at least one zero. This result is also known as the‘hairy ball theorem’. This results in a contradiction.

as the definition of R(0, 0, −1). Recall also that, by Rodriguez’ formula, a rotation about a unit vector v by anangle θ is given by eθξv = I + ξv sin θ + ξv2 (1 − cos θ),
for v ∈ R3 such that kvk = 1. This formula can then be
used to efficiently evaluate R(n) for all n ∈ S2 without thesouth-pole, where we define R(n) as discussed above. Tosummarize, we have found that

The above result implies in particular that there is no
continuous way of approximating S(g) (that is continuous
as a map g 7→ S(g)) using a polyhedral approximation of
the truncated cones Conv({0} ∪ C(ni )). While the maximal‘jumps’ in the approximation clearly tend to zero as thenumber of edges of the polyhedral approximation of friction
cones is increased, such an approximation scheme mightcause problems when methods depending on continuity, suchas gradient based methods, are to be used for grasp synthesis.
Let us now study the discontinuity of this map in thecase of a particularly nice assignment of cones to normaldirections. We define the standard approximate disk withfriction coefficient µ, with l defining edges, and with inward pointing
normal direction
(0, 0, 1) by Dl (0, 0, 1)
 =

2πj
Conv
µ cos 2πj
,
µ
sin
,
1
:
j
∈
{1,
.
.
.
,
l}
, so
l
l
that Fl (0, 0, 1) = Conv({0} ∪ Dl (0, 0, 1)). See Fig. 1 fora visualization. In order to define a cone for a new normal
direction n, we rotate Dl (0, 0, 1) about the axis (0, 0, 1) × n
by an angle of arccos(h(0, 0, 1), ni). An explicit formula forthis process can be given elegantly in screw coordinates byDl (n) = R(n)Dl (0, 0, 1), where
R(n) = exp arccos(h(0, 0, 1), ni)ξ (0,0,1)×n ,Lemma 3.4. The above assignment of uniform polyhedralcones with l edges given by n 7→ Fl (n) is a continuous
map on the punctured sphere S2+ = S2 − {(0, 0, −1)}. Whenconsidered as a map on the whole sphere S2 , the map has a
discontinuity at (0, 0, −1).

to the parameter g, we will now show that this is in fact not
the case. Recall that Sl− (g) is a convex hull determined byapproximating the truncated friction cones Conv({0}∪C(n))
using C(n) ≈ Conv({f1 (n), . . . , fl (n)}). We now show that
there cannot exist any continuous map n 7→ fj (n) assigningnormal directions n ∈ S2 to edges fj (n) of the truncatedfriction-cone Conv({0} ∪ C(n)):

k(0,0,1)×nk

the exponential denotes the matrix exponential, and
0 −z y0 −x  .
ξ(x,y,z) =  z−y x0Note that, for k(0, 0, 1) × nk 6= 0, the above map iscontinuous and well-defined. So the only potential problem
occurs at the poles (0, 0, 1) and (0, 0, −1). As n → (0, 0, 1),
arccos(h(0, 0, 1), ni)arccos(h(0, 0, 1), ni)=→ 1,k(0, 0, 1) × nk|sin(arccos(h(0, 0, 1), ni))|

In Fig. 3, we exemplify how the above results leads to a
discontinuity of the function g 7→ Q3 (g). Consider fixed
2π
contact points c1 = (0, − sin( 2π3 − 0.6), cos( 3 − 0.6)),4π
4πc2 = (0, − sin( 3 − 0.6), cos( 3 − 0.6)) and a variable
contact c3 (ε, θ) = (− sin(ε) cos(θ), − sin() sin(θ), cos(ε)).
We chose corresponding normals given by nj = −cj to forma grasp g(ε, θ). Fig. 3 displays the quality Q3 (g(ε, θ)), forπ 3π
θ = − 3π
4 , 2 , 4 depicted in red, black (dashed) and blue
respectively and for ε ∈ [−0.01, 0.01] (horizontal axis). At
ε = 0, c3 (0, θ) = (0, 0, 1) for all approach directions θ, but
we can observe that Q3 (g(ε, θ)) has a limit depending on
the approach angle θ as ε → 0.
0.24

Q3 (g(ε, θ))

While one might think that the approximation Sl− (g) ofS(g) which determines Q−
l varies continuously with respect

0.22

0.2

0.18

−0.01

−0.005

0
ε

0.005

0.01

Fig. 3. Illustration of the discontinuity of Q3 (g(ε, θ)) for three contacts
on a sphere and where we continuously vary one contact c3 (ε, θ) near thenorth-pole for three different approach directions θ ∈ {− 3π, π 3π }. At
4 2 4
ε = 0, c3 (0, θ) = (0, 0, 1) for all θ ∈ [0, 2π).

Properties of q and Q
In [8], q is characterized (up to changes in notation) as:
q(g) ==minhS(g) (u)minmax hWi (g) (u),u∈R6 :kuk=1

u∈R6 :kuk=1 i=1,...,mwhere S(g) = Conv(∪m
i=1 Wi (g)), Wi (g) = wci ,z (C(ni )) ⊂R6 , and hWi (g) (u) = supw∈Wi (g) hu, wi is the support function for the convex set Wi (g). By picking an orthonormal
basis t1 , t2 of the tangent space at each contact, the authors
then simplified the above by determining an explicit formulafor hWi (g) (u). We will now provide a basis independent
formula for hWi (g) (u).
Let us observe that wc,z is a linear map and thatthwc,z (x), ui = hx, wc,z(u)i, where for u = (a, b) ∈ R3 ×
36t
R = R , we have the adjoint wc,z(a, b) = a + b × (c − z).
Hence, hWi (g) (u) = supx∈C(ni ) hx, wcti ,z (u)i. This problem
can however be solved without a choice of coordinate frame:
Lemma 3.5. For w ∈ R3 , we have, for n ∈ S2 and for
friction coefficient µ > 0,

above by |hni , a + b × (ci − z)i − hn0i , a + b × (c0i − z 0 )i| +µ|kni × (a + b × (ci − z)k − kn0i × (a + b × (c0i − z 0 )k|. A
simple calculation involving the facts that kak 6 1, kbk 6
1, kci − zk 6 r, |v × w| 6 kvkkwk and |hv, wi| 6
kvkkwk yields that the first summand above is boundedby kni − n0i k(1 + kci − zk) + k(ci − z) − (c0i − z 0 )k 6
(1 + r)d(g, g 0 ), while the second summand is bounded byµ(kni −n0i k(1+r)+k(ci −z)−(c0i −z 0 )k) 6 µ(1+r)d(g, g 0 ).
Hence, |li,a,b (g) − li,a,b (g 0 )| 6 (1 + µ)(1 + r)d(g, g 0 ) andli,a,b is Lipschitz continuous with constant L for fixed i, a, b.
It follows now that maxi li,a,b (g) is Lipschitz continuous andq(g) =min

max li,a,b (g)(a,b)∈R6 ,kuk=1 i=1,...,mis also Lipschitz with the same constant. This is true because,in general, ϕ(x) = inf α∈A fα (x) and ϕ(x) = supα∈A fα (x)are Lipschitz with constant L if all fα are Lipschitz withconstant L and ϕ is bounded. To see this, observe thatfα (x) 6 fα (y) + Ld(x, y) for all α. Then supα∈A fα (x) 6supα∈A fα (y) + Ld(x, y). Swapping the roles of x, y thenyields the result in the sup case. The inf case is similar. The
last claim regarding Q also follows from the above.

sup hx, wi = hn, wi + µkn × wk.
x∈C(n)

Hence, for u = (a, b) ∈ R3 × R3 = R6 , we have1hWi (g) (a, b) = hni , a+b×(ci −z)i+µkni ×(a+b×(ci −z))k.
Proof. We can verify directly that the formula for
hWi (g) (x) = −qWi (g) (−x) found on p.6, [8] yields theabove result for an arbitrary choice of orthonormal basis{e1 , e2 , e3 } such that e1 = n.

0−1

Theorem 3.6. We haveq(g) =min6u∈R ,kuk=1

hS(g) (u) =min
6max hWi (g) (u),u∈R ,kuk=1 i=1,...,mwhere hS(g) is convex on R6 . Observe that q is invariant
under fixed translation of the grasp centre and contact
positions. Furthermore, let B(r) = {x ∈ R3 : kxk 6 r}.
Then q is Lipschitz continuous on grasps with m contact
points lying in the set X = {(c1 , . . . , cm , n1 , . . . , nm , z) :(ci − z) ∈ B(r), ni ∈ S2 } with a Lipschitz constant given
by L = (1 + µ)(1 + r) and where we choose the distancemeasureXX
d(g, g 0 ) =k(ci − z) − (c0i − z 0 )k +kni − n0i kiifor grasps g = (c1 , . . . , cm , n1 , . . . , nm , z) and g =(c01 , . . . , c0m , n01 , . . . , n0m , z 0 ) ∈ X. We hence have|q(g) − q(g 0 )| 6 Ld(g, g 0 ) for all g, g 0 ∈ X.
Since Q(g) = max(0, q(g)), Q is also Lipschitz continuouswith the same constant L on X.
Proof. hS(g) is a support function of a convex set and hence
convex. To prove the statement about Lipschitz continuity,
consider the function li,a,b (g) = hWi (g) (a, b). We have,for k(a, b)k 6 1, that |li,a,b (g) − li,a,b (g 0 )| is bounded

Fig. 4. Illustration of the usage of a Lipschitz constant L for a function
q : R → R which we might not be able to evaluate, but for which wehave computable bounds q − (x) 6 q(x) 6 q + (x). The Lipschitz condition|q(x) − q(x0 )| 6 L |x − x0 | forces the graph of q to the left and right ofthe depicted blue and red cones. Regions for which q < 0 (red bar), or forwhich q > 0 (blue bar), can be deduced from points where q + (x) < 0(red point) and q − (x) > 0 (blue point) respectively.

Note that q(g) is now described by a minimization ofa convex function hS(g) over the non-convex sphere S5 ={u ∈ R6 : kuk = 1}. Furthermore, our Lipschitz constant
L allows us to infer a whole stable (unstable) region aroundany point for which q > 0 (q < 0). While we cannot easily
visualize the concept of Lipschitz continuity in 6 dimensions,the reader unfamiliar with Lipschitz continuity is referred toFig. 4 which provides an example of Lipschitz bounds in one
dimension. Given our Lipschitz constant L, we can globallybound possible values of q using |q(g) − q(g 0 )| 6 Ld(g, g 0 ).
This inequality forces the graph of q to lie inside certain
regions around any known value q(g) as depicted in Fig. 4.
In particular, if we have a lower-bound estimate to q(g) ata grasp g, the Lipschitz bound implies that q(g 0 ) is globally
lower-bounded by the inequality as indicated in the figure.
From a single grasp with q(g) > 0 (q(g) < 0), we canhence infer the existence of a whole region around g whereq > 0 (q < 0 respectively). As illustrated in Fig.4, Lipschitz

bounds can hence be used to improve the efficiency ofsampling based grasp synthesis approaches, e.g. by quickly
determining stable and unstable parameter regions.
Detecting unstable grasps quickly
Note that, since q is given as a minimization problem, anyu ∈ R6 such that kuk = 1 yields an upper bound qu+ (g) =maxi=1,...,m hWi (g) (u) which can be computed quickly for
fixed u. Observe furthermore that we have the following:
Lemma 3.7. q(g) >minu∈R6 :kuk61 hS(g) (u).

0 if and only if 0=

Proof. If 0 = minu∈R6 :kuk61 hS(g) (u), then q(g) > 0 by
definition. Suppose q(g) > 0. Note that hS(g) (0) = 0 andany x ∈ R6 such that kxk 6 1 is of the form tw for somet ∈ [0, 1], w ∈ S5 . Now we have hS(g) (tw) = thS(g) (w) >0, and the result follows.
The lemma above is very handy since the minimization ofa convex function over the bounded convex set {x ∈ R6 :kxk 6 1} is a standard problem. In particular, we can search
for minima of hS(g) using the subgradient method [15] andstop once we find u ∈ R6 such that hS(g) (u) < 0 since thenuq(g) 6 hS(g) ( kuk) < 0, and we can conclude that the grasp
g is unstable.
It is clear from the definition that hS(g) is not smooth
everywhere. However, due to its explicit description as aconvex enveloping function, we can attempt to apply the
projected subgradient approach to find a minimizer.
Let us first recall that for any convex function f : Rn → R,a subgradient at x ∈ Rn is a vector s ∈ Rn such that f (y) >f (x)+hs, y−xi for all y ∈ Rn . The set of all subgradients at
x is denoted by ∂f (x). If f is differentiable at x, ∂f (x) ={∇f (x)}. Importantly, if f (x) = max(fS 1 (x), . . . , fm (x)),∂f (x) is given by the convex hull of i:fi (x)=f (x) ∂fi (x).
The subgradient method [15] for minimizing a function f ,updates xk to xk+1 = xk −αk sk , where sk is any subgradientof f at xk and αk > 0 is small. To solve minx∈C f (x) fora convex set C, this step is replaced with xk+1 = P (xk −αk sk ), where P (x) is the projection of x onto C. To apply
this method, we now simply need to compute subgradients.
Observe that, if kni × (a + b × (ci − z))k > 0, hWi (g) issmooth with ∂hWi (g) (a, b) = {∇hWi (g) (a, b)}, and where∂hWi (g)the partial derivatives are given by ∂a(a, b) = (ni )j +j∂hWi (g)hni ×ej ,ni ×(a+b×(ci −z))iand ∂b(a, b) = ((ci − z) ×
kni ×(a+b×(ci −z))ikjhni ×(ej ×(ci −z),ni ×(a+b×(ci −z))in)j +µ. If kn×(a+b×(ci −kni ×(a+b×(ci −z))ikµz))k = 0, it can be easily seen that hWi (g) has a subgradientgiven by s = (ni , (ci − z) × ni ).
We thus propose Algorithm 1 to determine quickly if
a grasp is unstable. The method Subgradient(hS(g) , u)denotes any subgradient of hS(g) at u ∈ B(1) = {x ∈ R6 :kxk 6 1}. The algorithm starts at u = 0 and applies aprojected subgradient algorithm for hS(g) on B(1) to finda minimum. It follows from the proof of Lemma 3.7 thatq(g) < 0 if this minimum is negative, and this fact is used in
the algorithm. Subgradient(hS(g) , u) returns a subgradient

Algorithm 1 Returns ”unstable” if a grasp can be determinedto satisfy q(g) < 0 and ”undetermined” otherwise.
Require: N ∈ N, grasp gi ← 0, u ← 0 ∈ R6 , q ← ∞while q > 0 and i < N doq = min(q, hS(g) (u))
s ← Subgradient(hS(g) , u)1su ← u − 1+iksk
if kuk > 1 thenuu ← kuk
end ifi←i+1
end while
return ”unstable” if q < 0, else return ”undetermined”
Algorithm 2 Determine an upper bound q + (g) > q(g).
Require: M, N ∈ N, grasp g
q+ ← ∞
for r ∈ {1, 2, . . . , M } dou ← RandomSample(S5 )for i ∈ {1, 2, . . . , N } doq + = min(q + , hS(g) (u))
s ← Subgradient(hS(g) , u)s1u ← u − 4√i kskuu ← kuk
end forend forreturn q +of the function hWi (g) for the first i ∈ {1, . . . , m} suchthat hS(g) (u) = hWi (g) (u). At points where hWi (g) isdifferentiable, the gradient is returned, otherwise, we return1(ni , (ci − z) × ni ) as discussed above. The decay rate 1+i
and normalization by ksk was chosen empirically based on
satisfactory performance in our experiments (see Section IV).
Determining the upper bounds q + , Q+
We propose Alg. 2 to determine an upper-bound forq(g). Here, RandomSample(S5 ) returns a uniform random
sample on the sphere S5 ⊂ R6 . We chose a decay factor
given by an inverse square root term in order to slowly
decrease the step-size of the subgradient descent method. We
define Q+ (g) = max(0, q + (g)). If one is only interested in
the computation of Q+ (g) rather than q + (g), Alg. 2 couldin future be optimized by terminating as soon as q + (g) 6 0.
+
Note that we now have Q−
l (g) 6 Q(g) 6 Q (g).
IV. E XPERIMENTS
Lower and upper bounds
Let us now experimentally study the convergence prop+
erties of Q−
l and Q . We generated a set U of 100000
random grasps with three contacts by sampling uniformly
from the set D(2) = B(2)3 × (S2 )3 × {0}, so that an elementg = (c1 , c2 , c3 , n1 , n2 , n3 , 0) ∈ D(2) determines a grasp
with three contact points ci ∈ B(2) = {x ∈ R3 : kxk 6 2},

0.5
mean error

corresponding normals ni ∈ S2 , and with centre of massat the origin. We computed the value of Q−
l on thesegrasp sets for l ∈ {3, 4, . . . , 20} edges. Given our error
estimate, the maximal error for l = 40 edges is at mostErr(2, 40) = 0.0092 and we used Q−
40 ≈ Q to calculatean ‘approximate ground truth’ for the data set. We used−the errors d− (g) = Q−l (g) − Q40 (g) to benchmark theconvergence towards Q(g) = max(0, q(g)) as the numberof edges is increased. To evaluate Algorithm 2, we usedM ∈ {5, 10, 20, 30, 40, 50} random samples and N = 1000
iterations and recorded timings and the differences d+ (g) =Q+ (g) − Q−
40 (g). We then split U into 10 equally sized sets
and studied the variation in mean errors in Fig. 5, while
Fig. 6 displays the worst-case performance on the whole+
set U . We observe that both Q−
l and Q converge quickly
towards Q. While our implementation of Algorithm 2 iscurrently not parallelized, it can be easily parallelized infuture due to its simplicity. Quickhull’s [10] algorithm which
is used to compute Q−
l (g) = max(0, minj λj ) (see Eq. 3)
is quite complicated in comparison and currently not threadsafe. For our algorithm, we determined a good decay rate of1√
empirically, but alternative rates and an implementation
4 iusing line-search could potentially boost performance further.
In applications where a precise value of q needs to be approximated, our results show that our algorithm can quickly+
provide an upper-bound, so that Q−
l (g) 6 Q(g) 6 Q (g)enabling us to make precise statements about the unknown
quantity Q(g).

0

−0.5
0

50

100
time (sec.)

150

200

Fig. 6. Worst-case errors for our data-set of 100000 random grasps for
Q+ and Q− are shown against mean computation time per 10000 grasp
quality evaluations for 10 repetitions of our experiment with 10000 random−
grasps each. The red curve displays the errors ming∈U Q−
l (g) − Q40 (g),for l = 3, 4, . . . , 20 increasing from left to right, while the blue curve
displays the errors maxg∈U (Q+ (g) − Q−
40 (g)) using Alg. 2, for M ∈{5, 10, 20, 30, 40, 50} increasing from left to right and for N = 1000
iterations.

ci , normals ni and centre of mass at the origin, and which
satisfied Q−
20 = 0, i.e. they were unstable with respect to the0quality measure Q−
20 . We now partition U into ten equally00sized subsets U1 , . . . , U10 and tested the performance of ourunstable grasp determination Algorithm 1 on these subsets.
As can be seen in Fig. 7, our algorithm can quickly identify
the majority of unstable grasps in U 0 , with 97% of all grasps
in Ui0 correctly classified after 0.086 seconds on average.
98%
recognition rate

0.01

mean error

0
−0.01

96%
94%
92%

−0.02
0.06
−0.03
−0.04
0

50

100
time (sec.)

150

200

Fig. 5. Mean errors relating Q+ and Q− to Q−
40 and computation timeper 10000 grasp quality evaluations are shown. The red curve displays themean and standard deviation (indicated by bars below the curve) for the−errors d− (g) = Q−l (g) − Q40 (g), for l = 3, 4, . . . , 20 increasing fromleft to right, while the blue curve displays the mean and standard deviation(indicated by bars above the curve) for the errors d+ (g) = Q+ (g)−Q−
40 (g)
when using Alg. 2 with M ∈ {5, 10, 20, 30, 40, 50} increasing from left
to right and for N = 1000 iterations.

Fast unstable grasp rejection
We generated a set U 0 of approximately unstable grasps
with three contacts by sampling uniformy in D(2) = B(2)3 ×(S2 )3 × {0} until we obtained a set of 100000 sample
grasps g = (c1 , c2 , c3 , n1 , n2 , n3 , 0) ∈ D(2) with contacts

0.07

0.08 0.09
0.1
time (sec.)

0.11

0.12

Fig. 7.
The percentage of correctly recognized unstable grasps andthe average computation time together with the standard deviation for
10 repetitions of the experiment are displayed. Data-points are orderedaccording to the number of maximal iterations N = 50, 100, 150, . . . , 1000
increasing in increments of 50 from left to right. Note that the averagecomputation time for evaluating Q8 on 10000 unstable grasps is about 12s,
while our algorithm can correctly rule out 97% of those grasps as unstablein about 0.086 seconds, resulting in an approximate 140-fold improvementin performance. If the same calculation was carried out using Q20 , ouralgorithm results in an approximate 2224-fold performance gain.

Finally, we tested our unstable grasp rejection algorithm asfollows: we consider the same set of 100000 random grasps
considered in Fig. 2(a). This time, we first, run Algorithm
1 with N = 400 maximal iterations. We then evaluate Q−lonly on those grasps which our algorithm does not classify
as unstable. This results in an algorithm that is between
49% and 503% faster than using Q−
l by itself, as can beseen in Fig. 8 and 9. Our grasp quality evaluation algorithm
is approximately 5 times faster than a simple evaluation

time (sec.)

200

100

0

0

5

10

15

Fig. 8. Computation time when using a first pass of Alg. 1 with N = 400(red circles) as compared a direct evaluation of Q−l (red crosses) on ourrandomly sampled grasps as in Fig. 2(a) and for a friction coefficient ofµ = 1. The blue circles and crosses depict the analogous plot for µ = 0.2.
We observe a substantial speedup when using our algorithm, especially fora lower friction coefficient of µ = 0.2.

speedup

6
4
2
10

15

400
200
0

5

10

15

20

l
Fig. 10. Relative speedup improvement (vertical axis) multiple when using−
a first pass of Alg. 1 before evaluating Q−
l rather than evaluating Ql by
itself for friction coefficient µ = 0.2. The horizontal axis displays the lparameter for the computation of Q−
l . The graph was obtained by evaluating
grasp quality on a set of 100000 uniform grasp samples as in Fig. 2(a).

quality measure that needs to compute largest inscribing balls
for a convex hull of wrenches such as the L∞ metric of [4].
Furthermore, the algorithm can easily p
be adapted to scaled
wrench metrics of the form k(f, p)k = kf k2 + λkpk2 , for
λ > 0 and wrenches (f, p) ∈ R3 ×R3 = R6 . We have shownthat our algorithms can dramatically improve the efficiencyof grasp quality evaluation. This improvement is particularly
evident in the case of low friction coefficients which posesa challenge to existing approaches. We are currently working on an optimized implementation of our approach andare in particular investigating a further optimization of thesubgradient methods used in Algorithm 1 and 2.
R EFERENCES

20

l

5

600
speedupof Ql for l > 8 while yielding exactly the same quality
values on stable grasps. Next, we considered the same setof grasps, but reduced the friction coefficient to µ = 0.2(e.g. polythene plastic against steel). While we obtained
approximately 17.8% stable grasps under Q−
20 for µ = 1(e.g. copper against copper), we now only obtain 0.09%
stable grasps with respect to Q−
20 and on our random grasp
set U . As can be seen by the blue crosses, the computationof Q−
l , takes even slightly longer for µ = 0.2, while ouralgorithm with a first pass of Alg.1 now performs very wellas indicated by the blue circles. Our algorithm computes Q3
in 0.037s, Q8 in 0.056s and Q20 in 0.397s per batch of
10000 grasps. This amounts to an improvement of a factor−−of 15 (vs Q−
3 ), 241 (vs. Q8 ) and 600 (vs. Q20 ) as indicatedby Fig. 10. Our algorithm could hence be used to speed up
grasp synthesis algorithms, and it could in particular enable
such algorithms to quickly find grasps on objects with low
friction coefficients for which sampling based methods were
up to now unsuitable.

20lFig. 9. Relative speedup improvement (vertical axis) multiple when using a−first pass of Alg. 1 before evaluating Q−
l rather than evaluating Ql by itself
for friction coefficient µ = 1. The horizontal axis displays the l parameterfor the computation of Q−
l . The graph was obtained by evaluating grasp
quality on a set of 100000 uniform grasp samples as in Fig. 2(a).

V. C ONCLUSION
In this paper, we have extended the theoretical foundation
for the study of a popular L1 grasp quality measure which
is based on an approximation of a friction cone by a convex
polyhedral cone. Several related grasp quality measures thathave been proposed in the literature [4], [14] are also
dependent on such an approximation. While we have chosen
to concentrate on the L1 grasp quality measure introduced by[4], it is clear that our algorithm can be adapted to any grasp[1] A. Bicchi and V. Kumar, “Robotic grasping and contact: A review,”
in IEEE ICRA, 2000, pp. 348–353.
[2] C. Borst, M. Fischer, and G. Hirzinger, “Grasping the dice by dicing
the grasp,” in IEEE/RSJ IROS, 2003, pp. 3692–3697.
[3] R. Suárez, M. Roa, and J. Cornella, “Grasp quality measures,” Universitat Polytècnica de Catalunya, Tech. Rep., 2006.
[4] C. Ferrari and J. Canny, “Planning optimal grasps,” IEEE ICRA, pp.
2290–2295, 1992.
[5] A. Miller and P. Allen, “Graspit! a versatile simulator for robotic
grasping,” IEEE Robotics Aut. Mag., vol. 11, no. 4, pp. 110–122, 2004.
[6] B. León, S. Ulbrich, R. Diankov, G. Puche, M. Przybylski, A. Morales,
T. Asfour, S. Moisio, J. Bohg, J. Kuffner, and R. Dillmann, “Opengrasp: A toolkit for robot grasping simulation,” in SIMPAR, ser.
Lecture Notes in Computer Science. Springer Berlin Heidelberg,
2010, vol. 6472, pp. 109–120.
[7] N. Vahrenkamp, M. Kröhnert, S. Ulbrich, T. Asfour, G. Metta,
R. Dillmann, and G. Sandini, “Simox: A robotics toolbox for simulation, motion and grasp planning,” in IEEE Int. Conf. on Intelligent
Autonomous Systems (IAS), 2012.
[8] Y. Zheng and W.-H. Qian, “Improving grasp quality evaluation,”
Robotics and Autonomous Systems, vol. 57, no. 6-7, pp. 665–673,
2009.
[9] Y. Zheng, “An efficient algorithm for a grasp quality measure,” IEEE
Trans. on Robotics, vol. 29, no. 2, pp. 579–585, 2013.
[10] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The quickhull
algorithm for convex hulls,” ACM Trans. Math. Software, vol. 22,
no. 4, 1996.
[11] X. Zhu and J. Wang, “Synthesis of force-closure grasps on 3-D objects
based on the Q distance,” IEEE Trans. on Robotics and Automation,
vol. 19, no. 4, pp. 669–679, 2003.
[12] B. Huang, S. El-Khoury, M. Li, J. J. Bryson, and A. Billard, “Learninga Real Time Grasping Strategy,” in IEEE ICRA, 2013.
[13] S. El-Khoury, M. Li, and A. Billard, “Bridging the gap: One shot
grasp synthesis approach,” in IEEE/RSJ IROS, 2012, pp. 2027–2034.
[14] B. Mirtich and J. Canny, “Easily computable optimum grasps in 2-D
and 3-D,” in IEEE ICRA, 1994, pp. 739 –747 vol.1.
[15] K. Kiwiel, Methods of Descent for Nondifferentiable Optimization, ser.
Lecture notes in mathematics. Springer-Verlag, 1985.