IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

1

Grasping Optimization using a Required External
Force Set
Tetsuyou Watanabe, Member, IEEE, and Tsuneo Yoshikawa, Fellow, IEEE

Abstract— In this paper, we investigate optimal grasp points
on an arbitrary shaped grasped object using a required external
force set. The required external force set is given based on a task,
and consists of the external forces and moments, which must bebalanced by virtue of contact forces applied by a robotic hand.
When the origin is in the interior of the set, a force-closure grasp
is required. When the dimension of the set is one, an equilibrium
grasp is required. Therefore we can investigate whatever thedesired grasp is, such as when the desired grasp is a force-closureand equilibrium grasps. Also, we only have to consider the forces
contained in a given required external force set, not the whole
set of generable resultant forces. Furthermore, we can avoid
the frame invariant problem (the criterion value changes withthe change of the task (object) coordinate frame)). We consider
an optimization problem from the viewpoint of decreasing themagnitudes of the contact forces needed to balance any external
force and moment contained in a given required external force
set. In order to solve the problem, we present an algorithm basedon a branch-and-bound method. We also present some numericalexamples to show the validity of our approach.
Index Terms— Optimization, Grasping, Branch-and-boundmethod, Required external force set

I. I NTRODUCTION
Consider using a robotic hand to lift an object off a table.
If the object can not be grasped with appropriate contact positions between the object and the robotic hand, the gravitational
force of the object may not be able to be counteracted and theobject may fail to be lifted. In the same fashion, in order tomanipulate an object in a desired direction, we must grasp theobject with appropriate contact positions. Selecting the contact
positions is a very important issue for grasping. This article
deals with optimal grasp synthesis on general objects.
Much attention has been given to investigating optimal grasp
points on a grasped object [1]–[20]. This research can beclassified into the following two categories: 1) research aimed
at investigating optimal grasp points or regions for balancing
gravitational force (namely, aimed at an equilibrium grasp)[1]–[3], 2) research aimed at investigating optimal grasp points
or regions for achieving force-closure grasps [4]–[20]. Forceclosure implies that, if external force and moment in any
direction are applied to a grasped object, the external force
and moment can be resisted and the motion of the object canbe restrained.
T. Watanabe is with Department of Mechanical Engineering, Yamaguchi
University, Yamaguchi, Japan (te-watanabe@ieee.org).
T. Yoshikawa is with College of Information Science and Engineering,
Ritsumeikan University, Japan (yoshikawa@ci.ritsumei.ac.jp).

An upper bound of the magnitude of resistible external
force and moment in force-closure grasps exists. Therefore,
the magnitude can be used as a criterion for grasps. Li etal. [21] evaluated a volume of the largest task ellipsoid. The
ellipsoid can be embedded in a set constructed by resultant
forces and moments, which can be applied to a grasped object
by a robotic hand. But the computation of the volume isvery complex. Using this criterion, then, makes it difficult toinvestigate optimal grasp points. Commencing with Mirtich
et al. [4], some researchers [5]–[7] have investigated optimal
grasp points, which minimize the magnitudes of contact forcesneeded to balance an external force. In these researches, themagnitudes of external force and moment, which must bebalanced, were set to be lower than one. Since this setting was
not based on a substantial reason, the authors in [4]–[7] were
faced with the problem: ”How do we handle the difference
between the units of the external force and moment whenevaluating the criterion (the magnitude of the needed contact
forces)”? Markenscoff et al. [5] only evaluated force. Mirtich
et al. [4] made two different criterions for force and momentand evaluated the magnitudes of contact force required tobalance external force and moment separately. Mangialardi
et al. [6] assumed external force and moment were applied
individually to a grasped object. Wang et al. [7] indirectly
evaluated the magnitudes of resistible external forces andmoments by the magnitude of the contact force of the clamp.
In sum, the class of the set of external forces to be balanced
has been limited in these studies [4]–[7]. Also, whole resultant
forces, applicable to a grasped object, must be evaluated.
In this article, we investigate optimal grasp points using
a required external force set [22], [23]. This set is given
based on a given task and consists of the external forces andmoments, which must be balanced by virtue of contact forces
applied by a robotic hand. In this case, then, the problem
of criteria regarding unit does not arise(because the set isbased on a task). Even when an object is manipulated, we
can use this set. We can construct the set by external forces
and moments which correspond to the required accelerationsor the motion of the object in the manipulation. Therefore,
optimal grasp points irrespective of both how to control therobotic hand and how to manipulate the object are investigated.
When the origin is in the interior of the set, a force-closure
grasp is required. When the dimension of the set is one, anequilibrium grasp is required. Therefore, by using the set, we
can investigate any desirable grasp including force-closure andequilibrium grasps. In addition, only the forces contained in agiven required external force set need be evaluated, and not thec 2002 IEEE
0000–0000/00$00.00 IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 20072

whole generable resultant force. A required external force set
is based on a given task, and if the task (object) coordinate
frame changes, the required external force set also changes
according to the change of the task (object) coordinate frame.
Criterion value does not change irrespective of the change ofthe task (object) coordinate frame. In other words, we can
avoid the frame invariant problem (criterion value changes
with the change of the task (object) coordinate frame).
In this article, we consider a problem for investigating
optimal grasp points from the view point of decreasing themagnitudes of contact forces needed to balance the external
forces contained in a required external force set. Commencing
with Li et al. [21], there are some researches dealing with grasp
synthesis from this viewpoint (task-oriented grasp synthesis).
Teichmann et al. [8] considered the problem of searching thegrasp points, which minimize the number of contact points,
needed to balance any external force and moment containedin a given set. Zhu et al. [9], [10], [24] presented a quantitative
measure of grasp, which is defined as the gauge function of aconvex polyhedral set in the wrench space (this set corresponds
to a required external force set). Based on the measure,they developed algorithms ”for optimal grasp synthesis on
polygonal objects [9]”, and ”for grasp synthesis on objects
where contact points are located on a surface represented by
one continuous function [10]”. But, the used set corresponding
to required external force set was assumed to contain the origin
in its interior, and only a force-closure grasp was considered in
the above researches [8]–[10], [24]. Therefore, the benefit ofaiming at any desirable grasp was lost. In addition, Teichmann
et al. did not consider friction at the contact points, and did
not show any numerical examples to verify the effectivenessof their approach. Pollard [25] considered grasp synthesis inwhich the used set corresponding to required external force
set was not assumed to contain the origin in its interior.
However, she did not deal with optimization of grasp. While
there have been a number of works concerning grasp synthesis,
we observed that no optimal grasp synthesis on general objects
yet has been done using the concept of required external force
set which does not necessarily contain the origin in its interior.
To deal with this kind of optimal grasp synthesis, in thispaper, we develop an algorithm based on a branch-and-boundmethod. In this method, a convex, polyhedral, required external
force set is used. When a given required external force set is
not a convex polyhedron, we use a convex polyhedron circumscribed in the convex hull of the original, given, required
external force set. In this way, we can deal with any kindof required external force sets. Therefore, we can deal withany desired grasps, including force-closure and equilibrium
grasps. This method can also find the global optimal solution
with a small computational time, and can deal with grasp of
any number of fingers.
In many cases the treatable shape of an object is restrictedin the investigation of optimal grasp points. The shape wasrestricted to a polygon or a polyhedron in [1], [2], [5], [9],[11]–[13], [18]. Every contact point was assumed to be on asurface represented by one continuous function in [1], [2], [5],[6], [10], [11]. In this case, two problems to solve occur: one
problem is to select the optimal surfaces represented by one

continuous function where we will locate contact points, andthe other problem is to select the optimal contact points. In
this article, admissible contact points are assumed to be given
by a collection of discrete candidate locations. When a set ofpoints is not given, but the geometry of a grasped object is, we
represent the geometry of the grasped object as a set of points.
In this case, if every point is close enough to its adjacentpoint in order to attain linearity between the constraints of the
problem for the neighboring points, an accurate solution canbe obtained. Then, any arbitrary shaped object can be treated.
Also, we can deal with the above two problems (how to selectsurfaces and how to select points) simultaneously.
Note that our algorithm can also be extended to the case ofutilizing another criterion such as accuracy and manipulability.
This paper is organized as follows. First, we define theproblem for investigating optimal grasp points using a required
external force set. Next, we present an algorithm to solve theproblem. Lastly, numerical examples are presented to show
the effectiveness of our approach.
A. Related works
A survey about equilibrium and force-closure grasps wasdone by Shimoga [26]. In this survey, computation of contact
forces for achieving equilibrium and force-closure grasps is
discussed as well as criteria for grasping dexterity. Anothersurvey [11] discussed the following topics: the number offingers required for force closure, testing for force closure andplanning force-closure grasps i.e., the computation of contact
forces for force closure. Next, we briefly review anotherresearch aspect; namely, the investigation of grasp points forequilibrium and force-closure grasps.
As for the investigation of grasp points for equilibrium
grasp, Omata [1], [2] investigated the regions of contact points
on a convex polyhedral object to balance the gravitational
force. Trinkle et al. [3] considered where contact points should
be located, in the case of lifting an object off a table without
friction using two fingers.
As for the investigation of grasp points for force closure,
we can further classify the research according to whether themagnitudes of resistible external forces are a subject of interest
or not. Research with no interest in the magnitudes, conductedby Nguyen [12], showed a method for investigating the regionsof contact positions for achieving force closure. Chen et al.
[13] presented a graphical method for investigating optimal
contact positions when a 2-D and 3-D object are grasped bythree and four fingers respectively, using some grasp qualities:
robustness, manipulability, and task compatibility. Chen etal. [14] investigated optimal contact positions for 2-finger
grasps, based on the concept of antipodal points and graspingenergy function. Ponce et al. [11] showed that force closureusing four fingers can be classified into concurrent grasp,
pencil grasp and regulus grasp. The authors also developed
a method for investigating the regions of contact positions
that can construct a concurrent grasp. Van der Stappen et al.
[15] presented algorithms to compute not only force-closure
grasp but also second-order-immobility grasp on polygonal
objects, based on a geometric search. Liu [16] presented a new

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

sufficient and necessary condition for force-closure grasps, andbased on it, developed an algorithm to compute force-closure
grasps of n fingers on polygonal objects. Ding et al. [17]investigated the contact positions on a polyhedral object toachieve force closure, using a method based on a qualitative
test algorithm [27] based on a ray-shooting problem. Ding etal. [18] investigated an eligible set of fixturing surfaces ona polyhedral workpiece for achieving force closure first, andthen investigated the optimal fixturing positions on the eligible
set, which minimize the locating error of the workpiece. Li etal. [19] investigated contact regions of fingers on polygonal
objects to achieve force closure, and evaluated the stabilityof the contact regions by each convex polyhedron composing
the contact regions. Liu et al. [20] presented an algorithm tocompute 3-D force-closure grasps on objects represented bydiscrete points. The algorithm combines a local search processwith a recursive problem decomposition strategy.
As for the research with an interest in the magnitudes ofresistible external forces, Markenscoff et al. [5] investigated
the grasp points which minimize the magnitudes of contact
forces needed to balance gravitational force. The gravitational
force was assumed to be applied to a polygonal object in the
direction perpendicular to the object. The grasp was done by
three fingers with frictional point contacts. Markenscoff et al.
[5] also investigated the grasp points minimizing the magnitudes of contact forces needed to balance an external force.
The external force was assumed to be applied to a polygonal
object in any direction and its magnitude was assumed to
be lower than one. The grasp was done by four fingers withfrictionless point contacts. Mirtich et al. [4] first investigated
the sets of grasp points, which minimize the magnitudes ofcontact forces needed to balance an external force, and theninvestigated the grasp points which minimize the magnitudes
of contact forces needed to balance an external moment,
among the selected sets of grasp points. The external moment
was assumed to be perpendicular to the grasp plane made by
the grasp points and its magnitude was assumed to be lower
than one. The external force was assumed to be applied inany direction and its magnitude was assumed to be lower thanone. The grasp was done by two or three fingers. Mangialardi
et al. [6] investigated the grasp points which minimize theaverage magnitude of the normal components of contact forces
required to balance external force and moment. The external
force and moment were assumed to be applied to a grasped
object individually in any direction with a unit magnitude.
Each grasp point was assumed to be on a surface represented
by one continuous function. Wang et al. [7] investigated the
fixturing points which minimize the magnitudes of contact
forces needed to balance external force and moment. The
object was assumed to be fixed by six locators and one clamp.
The locators were assumed to be able to passively apply acontact force without friction. The clamp was assumed to beable to actively apply a contact force without friction. Wanget al. considered some algorithms in the search for the optimal
positions of the locators when a certain contact force is applied
to the object by the clamp. Note that we can indirectly evaluate
the magnitudes of resistible external forces and moments by
the magnitude of the contact force of the clamp.

3

II. P ROBLEM D EFINITIONIn this section, we define a problem for investigating optimal
grasp points, using a required external force set. First, we describe the target system, statics, and the frictional constraints.
Second, we define the required external force set. Lastly, weformulate the problem for optimal grasp.
A. Target System
We consider the case where an arbitrary shaped rigid object
is grasped by m fingers of a robotic hand. We make thefollowing assumptions.
• Each finger makes a frictional point contact with theobject at the fingertip.
• A unique normal direction at each contact point can beobtained.
• Each finger can apply any desired contact forces to theobject using a force-feedback control.
• Dynamic effects are negligible. Quasi-static motion andstatic grasp are considered.
B. Statics and Frictional Constraints
First, we describe the relation between contact forces andexternal force and moment applied to the object. Let C be a
set of all possible candidates of contact points. Let
N ={pCN i (i = 1, 2, · · · , m)|pCN i ∈ C}(1)

be a combination of m contact points selected from C, where
pCN i ∈ Rd represents the position of the ith contact point(i = 1, 2, · · · , m), d = 2 in two-dimensional space, and d = 3
in three-dimensional space.
Let f N i ∈ Rd be the contact force applied to the object
at the ith contact point (by the ith finger). Let w∈ RD be
the external force and moment applied to the object (withrespect to a frame fixed at the object), where D = 3 in twodimensional space and D = 6 in three-dimensional space.
Then, the object is in equilibrium if the following equation
holds;
Σm
i=1 GN i f N i = −w.
Here, GN i is
⎛

(2)

⎞
0
⎠ ∈ RD×d
1
Gij = ⎝−(pCN iy − poy ) (pCN i x − pox )10

in two-dimensional space, where pCN ix and pCN iy represent
the x and y components of pCN i respectively, and pox and poy
represent the x and y components of po respectively, where
po represents the position of the origin of the frame fixed at
the object, andI
GN i =∈ RD×d[(pCN i − po ) × ]in three-dimensional space, where I represents an identify matrix, and [a×] represents a skew symmetric matrix equivalent
to the cross product operation ([ a × ]b = a × b).

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

4

Next, the frictional constraint at the ith contact point (i =1, 2, · · · , m) can be represented by
Ff N i = {f N i | t2fN i ,1 +t2fN i ,2 ≤ μN i nfN i , nfN i ≥ 0} (3)where S denotes the set of all possible candidates of N . This
problem investigates the combination of contact points, which
minimizes the magnitude of contact forces needed to balance
any external force and moment contained in the given required
external force set.

in three-dimensional space, where nfN i denotes the normal
force component of f N i , tfN i ,1 and tfN i ,2 denote the tangential force components of f N i , and μN i denotes the frictionalcoefficient at the ith contact point. Note that in (3), tfN i ,2 =0 can represent the frictional constraint in two-dimensional
space.
Aggregating (3) for all contact points, we obtain
Ff N = {f N |f N i ∈ Ff N i , ∀ i},

(4)

where
f N = f TN 1 , f TN 2 · · · f TN m

T.

C. Required External Force Set
We define the required external force set as follows.
Required External Force Set We call an external force(moment) exerted on the object, required to be balanced forcompleting a given task, a ”required external force”. We
call a set, composed of all possible required external forces,
a ”required external force set” WR ⊂ RD . Note that therequired external force set must be given such that if webalance all the forces contained in the required external force
set, the stable grasp can be guaranteed.
D. Problem for Optimal Grasp
Based on the above discussion, we formulate a problem forinvestigating optimal grasp points, using a required external
force set. Let |f N i |(= f TN i f N i ) be the norm of the contact
force at the ith contact point. Let φ be the largest norm among|f N i |’s (i = 1, 2, · · · , m);
φ = max |f N i |.
iThen, φ has the following relation with the contact force atevery contact point;φ ≥ f TN i f N i (i = 1, 2, · · · , m).
In general, there exist an infinite number of combinationsof contact points, in which we can balance any external force
and moment contained in a given, required external force
set. If the external force can be balanced by small contact
forces, we receive the following benefits; (1) prevention of
the contact forces from deforming or destroying the object,(2) reduction of the perturbation of the resultant force andmoment resulting from the perturbation of the contact forces(such perturbation can cause a disturbing force resulting fromthe difference between the external force and its balancing
force), and (3) ability to grasp the object stably. We define thefollowing problem.
Problem for Optimal Grasp Find the combination ofcontact points N ∗ which gives ρ such thatρ = min max

min

N ∈S w∈WR f
N i satisfy (2),(3)φ(5)

III. A LGORITHM
In this section, we present an algorithm to solve the problem(5) defined in the previous section. For the development of
the algorithm, the candidate contact points are assumed to
be given by a finite number of points. When not a set ofpoints, but the geometry of a grasped object is given, we
represent the geometry of the grasped object as a set of points.
In this case, if every point is close enough to its adjacentpoint in order to attain linearity between the constraints of the
problem for the neighboring points, an accurate solution canbe obtained. Therefore, we have only to select the optimal
contact points from the candidate contact points. Let n be
the number of the candidate contact points. Then, the numberof the candidate N ’s can be expressed by C(n, m). (Notethat C(n, m) represents the number of combinations where
we select m from n.) Let Nk be the kth N contained in S
(k = 1, 2, · · · , C(n, m)).
In order to solve the problem defined in (5), we use abranch-and-bound method [28], [29]. The branch-and-boundmethod is often applied to a problem to find an optimal
solution among a finite number of feasible solutions. The
feasible solutions are the solutions of subproblems into which
we divide the original problem. This method finds the optimal solution by enumerating the solutions of the feasible
subproblems. In the process, we eliminate the subproblems
which we don’t have to solve, by using a relaxed problem
obtained by relaxing the constraints of the subproblem. Thiselimination reduces the computational time required. Note thatthe solution of the relaxed problem gives a lower/upper boundof the solution of the original subproblem.
First, we formulate a required external force set. Second,
we define some subproblems and a relaxed problem of the
problem defined in (5). Lastly, we describe the procedure of
the algorithm.
A. Required External Force Set
We represent a required external force set as a convex
polyhedron. However, it is possible that a given required
external force set is not a convex polyhedron, as shown in
Fig.1. In such a case, we will define a new required external
force set that is a convex polyhedron circumscribed in theconvex hull of the given original required external force set, asshown in Fig.1. The new required external force set (a convex
polyhedron) contains the original, required, external force set.
Therefore, if we can balance all the forces contained in the
new required external force set, we can also balance all theforces contained in the original required external force set.
Then, the stable grasp can be guaranteed if we balance all theforces contained in the new required external force set.
Next, let A1 be the set of generable resultant forces and A2
be a given non-convex polyhedral required external force set.

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

Fig. 1.

How to make a convex polyhedral required external force set

We seek the grasp points whose A1 must contain A2 (the grasp
points such that A1 ⊃ A2 ) . Denoting the convex hull of A1 bycoA1 , we can get the relation: coA1 ⊃ coA2 [30]. Here, since
the set of generable resultant forces is a polyhedral convex set[31], A1 = coA1 , then A1 ⊃ coA2 . Hence, the result for theconvex hull of the non-convex polyhedral required external
force set is the same as the result for a non-convex polyhedral
required external force set.
coA2 is given by:ll

coA2 = {λ j aj ,j=1

λj = 1, λj ≥ 0, aj ∈ A2 , l ∈ L}.
j=1

If l is finite, coA2 becomes a convex polyhedron. When coA2
isn’t a convex polyhedron, we approximate the convex hull
by a convex polyhedron circumscribed in the convex hull(let l be finite). If the approximation is accurate enough, theresult for the convex polyhedral required external force set
circumscribed in the convex hull of the non-convex polyhedral
required external force set is almost the same as the result fora non-convex polyhedral required external force set.
Accordingly, the given required external force set WR canbe expressed by a convex polyhedron composed of l vertexes:WR= {w = Σlj=1 λj w vj , Σlj=1 λj = 1,
λj ≥ 0(j = 1, 2, · · · , l)}B. Subproblems and the Relaxed Problem
First, we consider the case where the object is grasped at
the contact points belonging to the kth (a certain) combinationof contact points Nk . Then, the following subproblem can beobtained.
Subproblem 1
max

min

φ

(7)

k

If we solve Subproblem1 for every Nk (k = 1 , 2 , · · · ,C(n, m)), we can obtain the solution of the original problem(5).
Next, in Subproblem1 (when the object is grasped at
the contact points belonging to Nk ), we consider balancing
the required external force, wvj , which is the jth vertex
of WR . Then, we can obtain the following subproblem ofSubproblem1.
Subproblem 2
minsubject toφTf Nk i f Nk i ≤ φ (i = 1, 2, · · · , m)Σm
i=1 GNk i f Nk i = −w vj
f Nk i ∈ Ff Nk i (i = 1, 2, · · · , m)Now, we consider the case where we can obtain the optimal
solution of Subproblem2 for every wvj with N fixed at Nk(k is fixed, j = 1, 2, · · · , l). Let ρNk ,vj be the solution of
Subproblem2 for wvj where N = Nk . Then, the largest ρNk ,vj
among ρNk ,vj ’s (k is fixed, j = 1, 2, · · · , l) is the solution of
Subproblem1 (for Nk ). The following is the proof.
Proof: Let ρNk be the optimal value of Subproblem1 for
Nk . Let ρNk ,vj max be the largest ρNk ,vj among ρNk ,vj ’s (k isfixed, j = 1, 2, · · · , l). Then, it is obvious that
ρNk ≥ ρNk ,vj max .
The outline of the proof is such that if the contact forces
f Nk i , whose magnitudes are lower than or equal to ρNk ,vj max ,can satisfy (2),(3) for every w ∈ WR , ρNk ,vj max becomes the
optimal value of Subproblem1 for Nk .
Let f ∗Nk ,j = (f ∗Nk 1,j )T · · · (f ∗Nk m,j )T T be the contact
forces which give the ρNk ,vj . For every contact force f Nk i , weconsider the l-sided convex polyhedron of the contact force,
whose jth vertex is f ∗Nk i,j ;FNk i = {f = Σlj=1 λj f ∗Nk i,j , Σlj=1 λj = 1,
λj ≥ 0 (j = 1, 2, · · · , l)} (i = 1, 2, · · · , m).
The relation between ρNk ,vj max and f ∈ FNk i (i = 1, 2,· · · , m) can be given by;
ρNk ,vj max ≥ Σlj=1 λj ρNk ,vj≥ Σlj=1 λj (f ∗Nk i,j )T f ∗Nk i,j ,≥ (Σlj=1 λj f ∗Nk i,j )T Σlj=1 λj f ∗Nk i,j ,(Σlj=1 λj = 1, λj ≥ 0, i = 1, 2, · · · , m).

(6)

where wvj denotes the jth vertex of WR .

w∈WR f
N i satisfy (2),(3)5(8)

In other words, the magnitude of every contact force f ∈ FNk i(i = 1, 2, · · · , m) is lower than or equal to ρNk ,vj max .
Next, we consider whether f ∈ FNk i (i = 1, 2, · · · , m) cansatisfy (2), (3) for every w ∈ WR .
First, since the frictional constraints (3) is convex, the contact force contained in FNk i satisfies the frictional constraint;f ∈ Ff N i , ∀ f ∈ FNk i , i.
Second, the resultant force applied by contact forces contained in FNk i (i = 1, 2, · · · , m) can be represented by∗ll
Wr = {Σmi=1 GNk i Σj=1 λj f Nk i,j , Σj=1 λj = 1, λj ≥ 0,

(j = 1, 2, · · · , l)}.
= {−Σlj=1 λj w vj , Σlj=1 λj = 1, λj ≥ 0, (j = 1, 2, · · · , l)}= −WR .
Then, f ∈ FNk i (i = 1, 2, · · · , m) can satisfy (2), (3) for
every w ∈ WR . Hence, ρNk = ρNk ,vj max .
In sum, we can solve Subproblem1 by solving Subproblem2
for every wvj .
Based on a linear inequality representation of a second ordercone constraint and the formulation by Buss et al. [32], theinequality constraints of Subproblem2 can be rewritten by theIEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

6

Step 1
Set LIST, ρˆ = ρˆ , ρˆ N k = ρˆ N k
Edge

Select Nk from the LIST

Step 2Friction Cone

j=1

Set


(a) f T
Nk i f Nk i ≤ φ

Find

Circumscribed Convex Polyhedral Cone

Eliminate Nk

ρ N k ,v j (Solve Subproblem 2)

N

Can we get ?
Y
Set j=j+1(b) Friction coneFig. 2. Convex polyhedron and convex polyhedral cone circumscribed in theconstraints of Subproblem2

N

j>l?
Y

Step 3following constraints with respect to the symmetric matrices
F Nk i and P Nk i ;φI
f Nk iF Nk i =OT
f Nk iφ⎞⎛μNk i nfNk i
0
tfNk i ,10μNk i nfNk i tfNk i ,2 ⎠  O (9)P Nk i = ⎝tfNk i ,1
tfNk i ,2 μNk i nfNk i

ρ N k ,v j , ρˆ = ρ N k , ρˆ N k = ρ N k , ˆj = arg max ρ N k ,v j
Set ρ N k = maxjjStep 4

where V Nk i ∈ Rd×L denotes the matrix whose jth column
is v Nk ij , which is the jth unit edge vector of the frictional
convex polyhedral cone (V Nk i =(v Nk i1 · · · v Nk iL )), uNk i (≥o)∈ RL denotes the vector whose jth element represents themagnitude of the contact force in the v Nk ij direction, and eκ ∈Set k=k+1
N

Is Nk contained in the LIST ?
Y
Find ρ̂ N k ,v ˆj (Solve Relaxed Problem )Eliminate Nk

N

Can we get ?
Ywhere F Nk i  O means F Nk i is a positive semidefinite
matrix. Then, we can solve Subproblem2 by using a positive
semidefinite program (see appendix and [33], [34]).
Next, we define a relaxed problem whose constraints arelinear constraints relaxing (containing) the constraints ofSubproblem2. This relaxed problem is the problem of finding
Nk ’s for which we do not have to solve Subproblem1 (andSubproblem2), with a small computational time. Of course,
Subproblem2 can be used to find the Nk ’s. However, since a
linear programming (simplex method) requires less computational time than a positive semidefinite program, we use therelaxed problem. Note that the solution of the relaxed problem
gives a lower bound of the solution for the corresponding
Subproblem2; namely, that of the corresponding Subproblem1,
since the constraints of the relaxed problem contain theconstraints of the corresponding Subproblem2. Utilizing thelower bound, we will find Nk ’s for which we do not haveto solve Subproblem1 (for details, please refer to the section
III-C).
Among the constraints of Subproblem2, we approximate
f TNk i f Nk i ≤ φ by a convex polyhedron circumscribed in
the constraint (Fig.2(a)). We approximate the friction cone
(3) by a L-sided convex polyhedral cone circumscribed in
the friction cone (Fig.2(b)) [35]. Hence, we can define thefollowing relaxed problem.
Relaxed Problem
minφsubject to eTκ V Nk i uNk i ≤ φ (i = 1,· · ·,m, κ = 1,· · ·,d)(10)−eTκ V Nk i uNk i ≤ φ (i = 1,· · ·,m, κ = 1,· · ·,d)Σmi=1 GNk i V Nk i uNk i = −w vj

k=1

Set

Compute ρˆ N k = max{ρˆ N k , ρˆ N k ,v ˆj }Nρˆ ≥ ρˆ N k ?

Yk > NN ?
Y

NStep 5Compute kˆ = arg min{ρˆ N k , v ˆj }k

Step 6j=1

Set

Find ρ N kˆ ,v j (Solve Subproblem 2)

N
Set

Eliminate N kˆN

Can we get ?
Y
Set j=j+1
j>l?
Yρ N ˆ = max ρ N ˆ ,v j , ρˆ N ˆ = ρ N ˆ , ˆj = arg max ρ N ˆ ,v j
k

j

k

k

k

j

k

N

ρˆ ≥ ρ N ?
k̂

Y
IF

ρˆ > ρ N ˆ ,kρˆ = ρ N ˆkStep 7N| ρˆ − ρ N k |< ε ,∀N k ∈ LIST ?

Y
FinishFig. 3.

Flow chart of the algorithm

Rd denotes the vector whose κth element is 1 and whose otherelements are 0 (for example, e1 =(1 0 0)T in three-dimensional
space). Note that the Relaxed Problem can be solved by asimplex method.

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

7

C. Procedure of Algorithm
In this subsection, we describe the procedure of the algorithm to solve the problem defined in (5). Fig.3 shows the flow
chart of the algorithm. We define the following nomenclatures:ρ̂
The (best known) feasible solution at each iteration
ρNk The solution of Subproblem1 for Nk
ρ̂Nk The (best known) lower bound of the solution of
Subproblem1 at each iteration (This bound is used
to find eliminable Nk ’s in Step 4.)
ρNk ,vj The solution of Subproblem2 for Nk and w vjρ̂Nk ,vj The solution of the Relaxed Problem for Nk and w vj
LIST The list of feasible Nk ’s
NN The number of the feasible Nk ’s (NN ≤ C(n, m))
The lower bound value of ρ̂ (the initial value of ρ̂)ρ̂ρ̂Nk The lower bound value of ρ̂Nk (the initial value ofρ̂Nk )
Step 1 Put all feasible (candidate) Nk ’s into the LIST . Set
ρ̂= ρ̂ and ρ̂Nk = ρ̂Nk (k = 1, 2, · · · , NN ).
Step 2 First, we search the first eligible value of ρ̂, solving
Subproblem1 at a certain Nk . Select a certain Nk fromthe LIST and solve Subproblem1 for the Nk as shownin Fig.4(a). Here is how to solve Subproblem1. First,
compute the solutions of the all Subproblem2s which are thesubproblems of Subproblem1 for the Nk (Compute ρNk ,vj ’s(k is fixed, j = 1, 2, · · · , l)). If there exists at least one
Subproblem2 which has no solution, the Subproblem1 has no
solution. If there exist the solutions of the all Subproblem2s,
the largest ρNk ,vj among the solutions ρNk ,vj ’s (k is fixed,
j = 1, 2, · · · , l) becomes the solution of the Subproblem1(ρNk = maxj {ρNk ,vj }).
Step 3 If we can get the solution of the Subproblem1 in
Step 2 (ρNk = maxj {ρNk ,vj }), substitute the solution into ρ̂(ρ̂= ρNk ), also substitute the solution into ρ̂Nk (ρ̂Nk = ρNk ).
Let ĵ be the number of the largest ρNk ,vj (ĵ=arg maxj
{ρNk ,vj }). Let w vĵ be the wvj which gives the solution ρNk .
If we can not get the solution, we eliminate the Nk from the
LIST and go back to Step2. Note that we select wvĵ for the
search, supposing the corresponding ρN ,vĵ at every Nk willk
be most possibly the largest among ρNk ,vj ’s (j = 1, 2, · · · , l).
Step 4 Solve the Relaxed Problem where wvj = w vĵ , andat every Nk contained in the LIST (j is fixed to be ĵ. k is
the number of each Nk contained in the LIST ) as shown in
Fig.4(b). In other words, we fix w vj and search the eliminable
Nk ’s. If we cannot get the solution at a certain Nk , we musteliminate the Nk from the LIST . If we can get the solutionρ̂N ,vĵ at a certain Nk , compute ρ̂Nk = max{ρ̂Nk , ρ̂N ,vĵ }.
kkTherefore, we compute the (best known) lower bound of
the solution of Subproblem1 for the Nk at this moment. Ifρ̂ <ρ̂Nk , eliminate the Nk from the LIST . At the end of thissubsection we present the proof for why the eliminations areapproved.
Step 5 Let Nk̂ be the Nk at which ρ̂N ,vĵ is the least amongkρ̂N ,vĵ ’s at all Nk ’s contained in the LIST (k̂=arg minkk{ρ̂N ,vĵ }). Note that we select Nk̂ for the search, supposingkNk̂ will most possibly be the optimal Nk .
Step 6 Solve Subproblem1 for the Nk̂ as shown in Fig.4(a). If

Nk

Nk

wvj

wvj
(a) Step 2(6)Fig. 4.

(b) Step 4

The diagram of Step 2(6) and Step 4

we can get the solutionρN (ρN = maxj {ρN ,vj }), substitutek̂k̂k̂
the solution into ρ̂Nk . Also, substitute the w vj , which gives
the solution, into w vĵ . Note that ĵ=arg maxj {ρN ,vj }. Ifk̂
we cannot get the solution or ρ̂ <ρN , eliminate the Nk̂ fromk̂
the LIST and go back to Step5. If ρ̂ >ρN , ρ̂ =ρN .
k̂k̂Step 7 If we can get the relation |ρ̂ − ρNk | <  ( denotes
an arbitrary small positive value) at all Nk ’s contained in the
LIST , finish the loop. Otherwise, go back to Step4.
Remark: This algorithm belongs to a branch-and-boundalgorithm. Since the algorithm should conceptually enumerate
all possible solutions of the finite number of problems, it
always convergences at the global optimum. In Step 4, we
evaluate the alternatives of the solutions and judge whether
the Nk is non-optimal or not, within a small computational
time. Next, we eliminate Nk ’s which are revealed to be nonoptimal. This fast elimination in Step 4 enables (users) to
reduce the search domain, and to avoid an exhaustive search,thus shortening the computational time.
The following proof illustrates why the eliminations areapproved in Step 4.
Proof: The set of the constraints of Relaxed Problem
contains that of Subproblem2. Therefore, if there is no solution
to the relaxed problem, then there is also no solution to
the corresponding Subproblem2. If there is a solution to therelaxed problem, then the solution to the relaxed problem
gives a lower bound of the solution of the corresponding
Subproblem2: ρ̂Nk ,vj ≤ ρNk ,vj . Let Gj,Nk be the set of j’s
whose corresponding ρNk ,vj has already been solved at theiteration. Then, the following relation holds:
ρ̂Nk = max {ρ̂Nk ,vj } ≤ max{ρ̂Nk ,vj }j∈Gj,Nkj≤ max{ρNk ,vj } = ρNk .
j

If ρ̂ <ρ̂Nk , then ρ̂ <ρNk . Therefore, we can see that the Nk
is not optimal, and we can eliminate the Nk .
IV. N UMERICAL E XAMPLES
In order to show the effectiveness of our approach, we show
some numerical examples in this section.
A. Examples in Two-Dimensional SpaceWe show the target objects and the candidate contact points
in Fig.5. In this figure, the points on the objects indicate thecandidate contact points. The number of the candidate contact
points is 56 in Case I and 86 in Case II. Note that the candidate

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

8

TABLE I710

ρ IN THE PROBLEM DEFINED IN (5)5(a) Case I

53μ2 fingers
3 fingers

1
0
-1
-3

0.1
3.71
3.13

(b) Case II
-10
-5

-3

-1

1

3

5

7

-10

(a) Case I
Fig. 5.

0.5
0.919
0.724

-5

-5
-7
-7

0.3
1.38
0.978

-5

0

5

μ
2 fingers
3 fingers

10(b) Case II

0.1
35.1
6.21

0.3
6.44
2.77

0.5
3.92
2.01

Target objects and candidate contact points

4

7

7

5

5

3

3

2
m

0
-2

1

1

-1

-1

-3

-3

-5

-5

-4
4

(a) Case I
Fig. 6.

2
f y 0 -2

-4

-4

-2

0 f
x

2

4

(b) Case II-7-7

Fig. 7.

where s denotes the area of each object, g=0.01 denotes the
specific gravity of each object, and γ denotes the distance
between the geometric center of each object and the vertex
closer to the geometric center than any other vertexes. Here,we consider the following case;
The gravitational force (external force) can be applied
to the object in any arbitrary direction, resulting from the
motion of the robotic arm equipped with the robotic hand.
• The external moment can be applied to the object resulting from the displacement of the position of the centerof gravity. The position of the center of gravity can move
within the circle. The center of the circle is the geometriccenter, and the radius of the circle is 0.8γ.
•

-3

-1

1

3

5

7

(a) 2 fingers

Required external force set

contact points are sampled such that the candidate contact
points are uniformly distributed. The object coordinate frame
is located at the geometric center of each object (the reference
frame is also located at the same geometric center).
Letting fx and fy be the x and y components of the external
force, respectively, and m be the external moment, we set therequired external force set as follows:
⎛
⎛
⎞
⎞
8
wxj
fx
WR = {⎝ fy ⎠ =(λ1j ⎝ wyj ⎠j=1m
0.8γsg
⎞
⎛
2
8
wxj
⎠),
wyj
+ λ2j ⎝
λij = 1, λij ≥ 0} (11)i=1 j=1−0.8γsg
π π
sg
wxj =
+ j)
π cos(
cos( 8 )
8
4
π π
sg
wyj =
sin( + j)cos( π8 )
8
4

-5

-7
-7

-5

-3

-1

1

3

5

7

(b) 3 fingers

Optimal grasp points in Case I

In this case, a convex hull of the WR can be written by
WR = {(fx , fy , m)T | fx2 + fy2 ≤ sg,−0.8γsg ≤ m ≤ 0.8γsg}.
And, we approximated fx2 + fy2 ≤ sg by a regular octahedron circumscribed in the sets (see Fig.6). Thus, we can obtain
the WR given by (11).
The computation was done in the cases where the numberof fingers is 2 and 3 and where the frictional coefficient is0.1, 0.3, and 0.5. When we obtain some optimal Nk ’s bydisregarding symmetrically arranged Nk ’s, we searched the(optimal) Nk which minimizes the criterion

m


max
min
f TN i f N iw∈WR f
N i satisfy (2),(3)i=1among the obtained optimal Nk ’s. By this search, we canobtain the grasp points which minimize the norm of contact
forces needed to balance any external force and moment
contained in the required external force set.
The results of the optimal combination of contact points areshown in Fig.7 and Fig.8. The results regarding the optimalvalue of the problem defined in (5), ρ, are shown in Table I.
In Fig.7 and Fig.8, (a) shows the results in the case where theobject is grasped by 2 fingers, (b) shows the results in the casewhere the object is grasped by 3 fingers, and the arrows show
the obtained optimal grasp points. Note that we show eitherof the obtained 2 optimal combinations of contact points inthe case where their arrangements are symmetric. Note alsothat we show only one optimal combination of contact points

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

9

10
2
1.5

5

1
0.5
0

0

−0.5
−1
3
2
1

-5

0
−1
−2

-10
-10

-5

0

5

Fig. 10.

10

−2

−1

0

1

2

3

Optimal grasp points in three-dimensional space (n = 429)(a) 2 fingers

10

B. Example in Three-Dimensional Space
The target object and the candidate contact points are shownin Fig.9. The target object is a triangular√ prism whose base isa right isosceles triangle (4 × 4 × 4 2). The points on theobject indicate the candidate contact points. Note that Fig.9,
for ease of viewing, does not show the candidate contact
points on the bottom face and on the back side (this sidecorresponds to the hypotenuse of the top/bottom face). We
included the candidate contact points on the bottom face inthe same way as those on the top face. We included thecandidate contact points on the back side in the same way as
those on the front sides. The number of the candidate points
is 429 (78 for the top and bottom faces, 91 for the every
front side and the back side). Note that the candidate contact
points are sampled such that the candidate contact points are
uniformly distributed. The object coordinate frame is locatedat the geometric center of the object (the reference frame isalso located at the same geometric center). We used a 16-sided
frictional convex polyhedral cone in the Relaxed Problem. We
set the following required external force set, considering thesimilar situation of the case in two-dimensional space.

μ=0.1
μ=0.3

5

μ=0.5

0
-5
-10
-10

-5

0

5

10

(b) 3 fingers
Fig. 8.

Optimal grasp points in Case II

2

WR = {(f T , mT )T | − sg ≤ fi ≤ sg,− 0.8γsg ≤ mi ≤ 0.8γsg (i = 1, 2, 3)}

1

0

−1
3

3
2

2
1

1
0

0
−1

−1
−2

−2

Fig. 9. Target object and candidate contact points in three-dimensional space(n = 429)

in Fig.7(a), (b), and Fig.8(a), since the optimal combinationof contact points was the same for every magnitude of thefrictional coefficient.
From Fig.8(b), we can see that the optimal grasp points
approach the symmetric arrangement with the increase of themagnitude of the frictional coefficient. Here, the symmetricarrangement means any angles, between any two of threelines connecting ”the geometric center of the object” and ”theoptimal grasp points”, are 120◦ . From Table I, we can see thatthe magnitude of contact forces needed to balance the required
external force, becomes small with increases of the magnitudeof the frictional coefficient and the number of fingers.

(12)

where f and m denote the external force and moment
respectively, fi and mi denote the ith components of f andm respectively, s denotes the volume of the object, g=0.01
denotes the specific gravity of the object, and γ denotes the
distance between the geometric center of the object and theface which is closer to the geometric center than any otherfaces. Here, we consider the following case;• The gravitational force (external force) can be applied
to the object in any arbitrary direction, resulting from the
motion of the robotic arm equipped with the robotic hand.
• The external moment can be applied to the object resulting from the displacement of the position of the centerof gravity. The position of the center of gravity canmove within the sphere. The center of the sphere is thegeometric center, and the radius of the sphere is 0.8γ.
In this case, a convex hull of WR can be written by√
WR = {(f T , mT )T | f T f ≤ sg, mT m ≤ 0.8γsg}.
√And, we approximated f T f ≤ sg and mT m ≤ 0.8γsg
by cubes circumscribed in the sets. Thus, we can obtain theIEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 200710

WR given by (12).
The number of the fingers was set to 3. The frictionalcoefficient was set to 0.3.
The result of the optimal combination of contact points
is shown in Fig.10. In Fig.10, the arrows, whose tip is a
black sphere, show the obtained optimal grasp points. X
shows the position of the origin of the reference frame.
The gray triangle shows the projection drawing of the triangle, made by the three optimal grasp points, on the bottom face of the object. The positions of the obtained optimal grasp points were (0.3590,−4/3,0)T , (2/3,2/3,0)T , and(−4/3, 0.3590, 0)T . The optimal value of the problem (5), ρ,
was 0.688.
From this result, we can see that the optimal point on theback side is located at the projection of the X point (origin)on the back side, and the optimal point on the every front
side is located at the position shifting a little toward the backside from the projection of the X point (origin) on the front
side. For the confirmation, we compute ρ in the case where
we grasp the object at the projection of the X point (origin)on every side. The ρ was 0.718, which is bigger than 0.688(the optimal value).
C. Efficiency of the algorithm
Branch-and-bound-algorithm completely does not guarantee
a smaller computational time than an exhaustive enumerating
search. However, in a practical sense, the eliminations of
redundant enumeration through child problems dramaticallyreduce the computational time. Here, we discuss the efficiencyof our algorithm, from the view point of iteration number,elimination number of Nk ’s, sampling effect of contact points,
and reduction of computational time.
First, we consider the iteration number of our algorithm,
using the following nomenclatures:Nsdpj The number of Nk ’s where the number of thecalculated Subproblem2s is j(≤ l).
Nsimj The number of Nk ’s where the number of thecalculated Relaxed Problems is j(≤ l).
nsdp The number of constraints of Subproblem2 (=3m + m(d + 1)).
nsim The number of constraints of the Relaxed Problem (= 2md + D).
Note that if j of Nsdpj (Nsimj ) is smaller than l, thecorresponding Nk ’s are eliminated before all possible
corresponding Subplblem2s (relaxed Problems) are calculated.
When we do the exhaustive enumerating search (enumerating
all possible solutions of Subproblem1(2)), Nsdpl is equal toNN .
Since the number of iterations of a positive semidefinite
program is given by O(9(nsdp )2.5 ) where setting X 0 = S 0 =10I and ε = 1 × 10−7 (see appendix), the total iteration
number for calculating
Subproblem2s in our algorithm islgiven by O( j=1 Nsdpj j9(nsdp )2.5 ). Similarly, since thenumber of iterations of a linear program (simplex method)is given by O(2nsim ), the total iteration number needed to
calculatel the Relaxed Problems in our algorithm is given by
O( j=1 Nsimj j2nsim ). The total iteration number for theexhaustive enumerating search is given by O(NN l9(nsdp )2.5 ).

2

1

0

−1
3

3
2

2
1

1
0

0
−1

−1
−2

−2

(a) n = 105

2
1
0
-1
3

3
2

2
1

1
0

0
-1

-1
-2

-2

(b) n = 217

2

1

0

−1
3

3
2

2
1

1
0

0
−1

−1
−2

−2

(c) n = 285

2

1

0

−1
3

3
2

2
1

1
0

0
−1

−1
−2

−2

(d) n = 341
Fig. 11.

Target object and candidate contact points for various n’s

Here we assume that the eliminations of redundant enumerations are efficiently done (refer to Fig.13∼16 at the later
discussion). Therefore, the following relation holds:lNsdpj jNsdpl l = NN l.

j=1

In this case, the relation between the total iteration numbers”for Subproblem2s in our algorithm” and ”for an exhaustive

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

2
1.5
1
0.5
0
−0.5
−1
3
2
1
0
−1
−2

−2

−1

0

1

2

3

(a) n = 105
2

1

0

-1
3

2

1

0

-1

-2

-2

-1

0

1

2

3

(b) n = 217
2
1.5
1
0.5
0
−0.5
−1
3
2
1
0
−1
−2

−2

−1

0

1

2

3

(c) n = 285
2
1.5
1
0.5
0
−0.5
−1
3
2
1
0
−1
−2

−2

−1

0

1

2

3

(d) n = 341
Fig. 12.

Optimal grasp points for various n’s

enumerating search” is given by:lO(

Nsdpj j9(nsdp )2.5 )O(NN l9(nsdp )2.5 ).

(13)

j=1

l
On the other hand, since j=1 Nsimj j < NN l, 2nsim
9(nsdp )2.5 , the relation between the total iteration numbers”for Relaxed Problems in our algorithm” and ”for an exhaustive enumerating search” is given by:lNsimj j2nsim )O(

O(NN l9(nsdp )2.5 ).

(14)

j=1

The total iteration number for our algorithm is given by
the summation of the iteration numbers for Subproblem2s and11

Relaxed Problems. From (13) and (14), since both the iteration
numbers are much smaller than that for an exhaustive enumerating search, the total iteration number for our algorithm ismuch smaller than that for an exhaustive enumerating search.
In addition, the computational time at each iteration for a
Relaxed Problem is much smaller than that for a Subproblem2.
Hence, total computational time for our algorithm is muchsmaller than that for an exhaustive enumerating search.
Next, we show the efficiency of our algorithm using anelimination number of Nk ’s, the number of candidate contact
points (related with sampling effect of contact points), andcomputational time in the practical numerical examples as
described in sections IV-A and IV-B. Our algorithm was
implemented in C/C++ and the calculations were done on
a Dell Dimension 8400 computer (CPU: Pentium 4 3.4GHz,
Memory: 1GB).
Fig.13 (a), (b) and (c), respectively, show the computational time, the number of calculated Subproblem2s, and thenumber of calculated Relaxed Problems in each case of twodimensional examples (the fictional coefficient is 0.3). From
Fig.13 (c) (and (b)), we can see that the number of calculated
Relaxed Problems is much larger than the number of calculated
Subproblem2s, and then that the eliminations of redundant
enumeration are efficiently done in every case. But, from
Fig.13 (a), we can see that the computational time does notalways depend on the number of candidate contact points. It isalso clear that the computational time increases with increaseof the number of fingers.
To investigate the sampling effect of contact points, we
calculated for various numbers of candidate contact points inthe case of the three-dimensional example in section IV-B.
Fig.11 (a) ∼ (d) and Fig.9 show the target object and thecandidate contact points for each case. Fig.12 (a) ∼ (d) and
Fig.10 show the obtained optimal contact points for each case.
Fig.14 (a), (b) and (c), respectively, show the computationaltime, the number of calculated Subproblem2s, and the numberof calculated Relaxed Problems for each case. Simultaneously,
we computed Subproblem2 in place of the Relaxed Problem
to find Nk ’s which we do not have to solve for Subproblem1.
Fig.15 (a) and (b), respectively, show the computational time
and the number of calculated Subproblem2s for each case inthis example.
From Fig.12 (a) ∼ (d) and Fig.10, we can see that the
optimal contact points are almost the same and therefore,
the sampling effect of contact points is small with respect
to optimal contact points. From Fig.14, we can see that thecomputational time increases with increase of the number ofcandidate contact points, and that the number of calculated
Relaxed Problems is much larger than the number of calculated
Subproblem2s. This result shows that the eliminations of
redundant enumeration work effectively in our algorithm.
Comparing Fig.14 with Fig.15, it is clear that the computational time is dramatically reduced for the eliminationsof redundant enumeration using the Relaxed Problem (seeFig.15 (a). In Fig.15 (a), the reference value represents theresults when using our original algorithm (Fig.14 (a)), and theobtained value represents the results when using eliminations
by Subproblem2.). It means that the eliminations of redundant

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

(Nc=56)
Case II

3200

Ns2 (×10 )(Nc=86)

150
100
50
0
3

Case II(Nc=86)

When using eliminations
by Subproblem

2000(Nc=56)

1500

When using eliminations
by Relaxed Problem

1000
500
0
0

100

200

300

2

Nf

(a) Tc [sec](a) Tc [min](b) Ns2
Case I(Nc=56)5

Nr (×10 )2

Case II(Nc=86)1.5
1

Ns2 of Case I(Nc=56)0.5

Ns2 of Case II(Nc=86)

18
16
14
12
10
8
6
4
2
0
0

100

200

300

3

Fig. 15. Performances for the cases using eliminations by Subproblem2(three-dimensional space); (a) Tc : Computational time [min], and (b) Ns2 :Number of calculated Subproblem2s. Note that Nc denotes the number ofcandidate contact points.

(c) NrFig. 13.
Performances for the cases in two-dimensional space; (a) Tc :Computational time [sec], (b) Ns2 : Number of calculated Subproblem2s, and(c) Nr : Number of calculated Relaxed Problems. Note that Nc denotes thenumber of candidate contact points, and Nf denotes the number of fingers.
4035
3

Ns2 (×10 )

25
20
15
10
5
0
300

400

15

0

100

200

300

400

500

Nc

(a) Tc [min]
100

200

300

400

500

(b) Ns2NrNs25(a) Tc [min]5

When using eliminations
by Relaxed Problem

20

0

Nc

Nr (×10 )

25

5

Nc

18
16
14
12
10
8
6
4
2
0

When using eliminations
by Modified Relaxed Problem

30

10

0

500

35

NMr (×10 )Tc [min]

30

10
9
8
7
6
5
4
3
2
1
0

40

Tc [min]

Nf

200

500

(b) Ns2
2

100

400

Nc

0

0

500

3
Nf

2.5

400

Nc

5

2

Case I

Ns2 (×10 )Tc [sec]

250

2500

5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0

Case I

Tc [min]

300

12

18
16
14
12
10
8
6
4
2
0
0

100

200

300

400

500

Nc

(b) NM r
0

100

200

300

400

500

Nc

(c) NrFig. 16. Performances for the cases where the Modified Relaxed Problem
is used in place of Subproblem2 and Relaxed Problem (three-dimensional
space); (a) Tc : Computational time [min], and (b) NM r : Number of calculated
Modified Relaxed Problems. Note that Nc denotes the number of candidate
contact points.

Fig. 14. Performances for various numbers of candidate contact points (threedimensional space); (a) Tc : Computational time [min], (b) Ns2 : Numberof calculated Subproblem2s, and (c) Nr : Number of calculated Relaxed
Problems. Note that Nc denotes the number of candidate contact points.

enumeration by the Relaxed Problem work effectively in ouralgorithm.

In our approach, the number of the candidate combinationsof contact points is C(n, m), and the number becomes large
with increase of the candidate contact points or the number offingers. Here, we introduce a way to further reduce the computational time. We consider the following Modified RelaxedIEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

13

Problem:
Modified Relaxed Problem
min
φ
√


T
subject to eκ V Nk i uN i ≤ φ/ 2 (i = 1,· · ·,m, κ = 1,· · ·,d)k√−eTκ V Nk i uN i ≤ φ/ 2 (i = 1,· · ·,m, κ = 1,· · ·,d)points in a smaller computational time. The efficiency of thismethod is clear from Fig.13∼16.

k





Σm
i=1 GNk i V Nk i uN i = −w vjk

where V Nk i ∈ Rdenotes the matrix whose jth column isv N i which is the jth unit edge vector of the L-sided convex
d×L

k j





polyhedral cone inscribed in the friction cone (V Nk i =( v N i1k
· · · v N i )), and uN i (≥ o)∈ RL denotes the vector whosek Lkjth element represents the magnitude of contact force in thev Nk ij direction.
The Modified Relaxed Problem is obtained by linearizing
the constraints of Subproblem2. Note that the constraints of the
Modified Relaxed Problem is contained in the constraints ofSubproblem2, and thus, the solution of the Modified Relaxed
Problem is a feasible solution of Subproblem2, different fromthe solution of the Relaxed Problem (note that the solutionof the Relaxed Problem is possibly not a feasible solution of
Subproblem2).
By using the Modified Relaxed Problem in place of both
Subproblem2 and the Relaxed Problem in our algorithm, we
can not only reduce the computational time, but also get a suboptimal feasible solution. In this case, instead of seeking thesolution to Subproblem1 for every Nk , we seek the solution to
the following problem, which linearizes original Subproblem1:
Linearized Subproblem1
max

min

wvj ∈WR f N i ∈Ω

φ,

k

√
⎧ T 
⎫

eκ V Nk i uN i ≤ φ/ 2 (i = 1,· · ·,m, κ = 1,· · ·,d) ⎪
⎪
⎨
⎬
k
√



Ω = −eTκ V Nk i uN i ≤ φ/ 2 (i = 1,· · ·,m, κ = 1,· · ·,d) .
k
⎪
⎪


⎩
⎭
Σm
i=1 GNk i V Nk i uN i = −w vjk

Fig.16 (a) and (b), respectivelly, show the computationaltime and the number of calculated Modified Relaxed Problems
for each case. The obtained optimal contact points for eachcase are same as those as shown in Fig.12 (a) ∼ (d) and
Fig.10. Hence, we can get enough optimal grasp points bythis Modified Relaxed Problem- based algorithm. Comparing
Fig.14 (a) with Fig.16 (a), it is clear that the Modified Relaxed
Problem- based algorithm requires a smaller computationaltime (see Fig.16 (a). In Fig.16 (a), the reference value represents the results when using our original algorithm (Fig.14(a)), and the obtained value represents the results when using
Modified Relaxed Problem- based algorithm.). Thus, if only
(sub-)optimal contact points are needed and an optimal value
is not needed, the (sub-)optimal contact points can be obtainedin smaller computational time using the Modified Relaxed
Problem- based algorithm.
The other way to further reduce the computational time is by
first reducing the candidate contact points and searching the
optimal grasp points, and second, by searching the optimal
grasp points among the original candidate contact points near
the obtained optimal grasp points. By following this way to
reduce computational time, we get approximate optimal grasp

V. C ONCLUSION
In this article, we have investigated optimal grasp points
on a grasped object using the concept of a required external
force set. By using the required external force set, we candeal with any desired grasps, including force-closure andequilibrium grasps. Also, we only have to consider the forces
contained in a given required external force set, and not
the whole generable resultant forces. In addition, we can
avoid the frame invariant problem (criterion value changes
with the change of the task (object) coordinate frame). We
have considered an optimization problem from the viewpointof decreasing the magnitudes of the contact forces needed
to balance any required external force contained in a given
required external force set. In order to solve the problem,
we have presented an algorithm based on a branch-and-boundmethod. We have also presented some numerical examples inorder to show the validity of our approach. In addition, we
discuss the efficiency of our algorithm, from the view pointof iteration number, elimination number of combinations ofcontact points, sampling effect of contact points and reductionof computational time.
In this article, we have assumed that each finger makes africtional point contact with the object. However, even wheneach finger makes a soft-finger contact with the object, we canstill use our approach due to an expression of the frictional
constraints corresponding to (9) as proposed by Buss et al.
[32].
In addition, even when we would like to use anothercriterion such as manipulability and accuracy, we can stilluse our approach if we can find the value of the criterion
for a certain required external force at certain grasp points by
utilizing a programming method such as a sequential quadratic
programming.
A PPENDIX I
P OSITIVE S EMIDEFINITE P ROGRAM [33]Here we summarize a positive semidefinite program. A
positive semidefinite program is formulated as follows:
m
bi yi
min
i=1
(15)
m
subject to
i=1 Ai yi − C = S, S  O
where Ai , C, S are n × n symmetric matrices. The dual
problem of this problem is given bymax
C •X
subject to Ai • X (i = 1, · · · , m), X  O(16)where X is a n×n symmetric matrix, X •Y denotes the innerproduct of X and Y , namely, the trace of X T Y , TrX T Y .
These problems can be regarded as an extension of a standard
linear program. Similarly as a linear program, the problem issolved by a primal-dual interior-point method in a polynomial
time. The number of iteration is given by O(n2.5 log(X 0 •Y 0 ε−1 )) where X 0 and Y 0 are the initial value of X andY , respectively, and ε is the accuracy of an optimal solution.

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007

R EFERENCES[1] T. Omata, “Fingertip positions of a multifingered hand,” Proc. of IEEE
International Conference on Robotics and Automation, pp. 1562–1567,
1990.
[2] ——, “Finger position computation for 3-dimentional equilibrium
grasp,” Proc. of IEEE International Conference on Robotics and Automation, pp. 216–222, 1993.
[3] J. C. Trinkle and R. P. Paul, “Planning for dexterous manipulation withsliding contacts,” The International Journal of Robotics Research, vol. 9,
no. 3, pp. 24–48, 1990.
[4] B. Mirtich and J. Canny, “Easily computable optimum grasps in 2d and 3-d,” Proc. of IEEE International Conference on Robotics andAutomation, pp. 739–747, 1994.
[5] X. Markenscoff and C. H. Papadimitriou, “Optimum grip of a polygon,”
The International Journal of Robotics Research, vol. 8, no. 2, pp. 17–29,
1989.
[6] L. Mangialardi, G. Mantriota, and A. Trentadue, “A three-dimensional
criterion for the determination of optimal grip points,” Robotics &Computer-integrated Manufacturing, vol. 12, no. 2, pp. 157–167, 1996.
[7] M. Y. Wang and D. M. Pelinescu, “Optimizing fixture layout in a pointset domain,” IEEE Transactions on Robotics and Automation, vol. 17,
no. 3, pp. 312–323, 2001.
[8] M. Teichmann and B. Mishra, “Probabilistic algorithms for efficient
grasping and fixturing,” Algorithmica, vol. 26, pp. 345–363, 2000.
[9] X. Zhu, H.Ding, and H. Li, “A quantitative measure for multi-fingered
grasps,” Proc. of IEEE/ASME International Conference on AdvancedIntelligent Mechatronics, pp. 213–219, 2001.
[10] X. Zhu and J. Wang, “Synthesis of force-closure grasps on 3-d objects
based on the q distance,” IEEE Transactions on Robotics and Automation, vol. 19, no. 4, pp. 669–679, 2003.
[11] J. Ponce, S. Sullivan, A. Sudsang, J. Boissonnat, and J. Merlet, “On
computing four-finger equiliburium and force-closure grasps of polyhedral objects,” The International Journal of Robotics Research, vol. 16,
no. 1, pp. 11–35, 1997.
[12] V. Nguyen, “Constructing force-closure grasps,” The International Journal of Robotics Research, vol. 7, no. 3, pp. 3–16, 1988.
[13] Y. Chen, I. D. Walker, and J. B. Cheatham, “Grasp synthesis for planarand solid objects,” Journal of Robotic Systems, vol. 10, no. 2, pp. 153–
186, 1993.
[14] I. Chen and J. W. Burdick, “Finding antipodal point grasps on irregularly
shaped objects,” IEEE Transactions on Robotics and Automation, vol. 9,
no. 4, pp. 507–512, 1993.
[15] A. F. V. der Stappen, C. Wentink, and M. H. Overmars, “Computing
immobilizing grasp of polygonal parts,” The International Journal of
Robotics Research, vol. 19, no. 5, pp. 467–479, 2000.
[16] Y. Liu, “Computing n-finger form-closure grasps on polygonal objects,”
The International Journal of Robotics Research, vol. 19, no. 2, pp. 149–
158, 2000.
[17] D. Ding, Y. Liu, J. Zhang, and A. Knoll, “Computation of fingertip positions for a form-closure grasp,” Proc. of IEEE International Conferenceon Robotics and Automation, pp. 2217–2222, 2001.
[18] D. Ding, Y. Liu, and M. Y. Wang, “Automatic selection of fixturing
surfaces and fixturing points for polyhedral workpieces,” IEEE Transactions on Robotics and Automation, vol. 17, no. 6, pp. 833–841, 2001.
[19] Y. Li, Y. Yu, and S. Tsujio, “Force control of robot manipulators,” Proc.
of the IEEE International Conference on Robotics and Automation, pp.
3749–3754, 2002.
[20] Y. Liu, M. Lam, and D. Ding, “A complete and efficient algorithm
for searching 3-d form-closure grasps in the discrete domain,” IEEE
Transactions on Robotics and Automation, vol. 20, no. 5, pp. 805–815,
2004.
[21] Z. Li and S. S. Sastry, “Task-oriented optimal grasping by multifingered
robot hands,” IEEE Transactions on Robotics and Automation, vol. 4,
no. 1, pp. 32–44, 1988.
[22] Y. Yu, K. Takeuchi, and T. Yoshikawa, “Optimization of robot hand
power grasps,” Proc. of IEEE International Conference on Robotics andAutomation, pp. 3341–3347, 1998.
[23] T. Yoshikawa, T. Watanabe, and M. Daito, “Optimization of powergrasps for multiple objects,” Proc. of IEEE International Conferenceon Robotics and Automation, pp. 1786–1791, 2001.
[24] X. Zhu, H. Ding, and J. Wang, “Grasp analysis and synthesis basedon a new quantitative measure,” IEEE Transactions on Robotics andAutomation, vol. 19, no. 6, pp. 942–953, 2003.
[25] N. S. Pollard, “Closure and quality equivalence for efficient synthesis ofgrasps from examples,” The International Journal of Robotics Research,
vol. 23, no. 6, pp. 595–613, 2004.

14[26] K. B. Shimoga, “Robot grasp synthesis algorithms: A survey,” TheInternational Journal of Robotics Research, vol. 15, no. 3, pp. 230–
266, 1996.
[27] Y. Liu, “Qualitative test and force optimization of 3-d frictional
form-closure grasps using linear programming,” IEEE Transactions on
Robotics and Automation, vol. 15, no. 1, pp. 163–173, 1999.
[28] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs, New
jersey, 1982.
[29] L. Stocco, S. E. Salcudean, and F. Sassani, “Fast constrained global
minimax optimization of robot parameters,” Robotica, vol. 16, pp. 595–
605, 1999.
[30] H. Fukawa, H. Nakayama, and T. Tanino, Linear Algebra and Convex
Analysis. Corona Publishing, 1991, (in Japanese).
[31] X. Zhang, Y. Nakamura, and K. Yoshimoto, “Mechanical analysis ofgrasps with defective contacts using polyhedral convex set theory,”
Journal of the robotics society of Japan, vol. 14, no. 1, pp. 105–113,
1996, (In Japanese).
[32] M. Buss, H. Hashimoto, and J. B. Moore, “Dexterous hand grasping
force optimization,” IEEE Transactions on Robotics and Automation,
vol. 12, no. 3, pp. 406–418, 1996.
[33] K. Fujisawa, M. Fukuda, M. Kojima, and K. Nakata, “Numericalevaluation of the sdpa (semidefinite programming algorithm),” The High
Performance Optimization, Kluwer Academic Publishers, pp. 267–301,
1999.
[34] L. Han, J. C. Trinkle, and Z. X. Li, “Grasp analysis as linear matrix
inequality problems,” IEEE Transactions on Robotics and Automation,
vol. 16, no. 6, pp. 663–674, 2000.
[35] J. Kerr and B. Roth, “Analysis of multifingered hands,” The International
Journal of Robotics Research, vol. 4, no. 4, pp. 3–17, 1986.