Fast and flexible determination of force-closure independent regions to grasp polygonal objects

Fast and flexible determination of force-closure independent regions to grasp polygonal objects Jordi Cornellà, Raúl Suárez IOC-DT-P-2005-2 Gener 2005 Fast and Flexible Determination of Force-Closure Independent Regions to Grasp Polygonal Objects∗ Jordi Cornell`aRa´ul Su´arez Institut d’Organitzaci´o i Control de Sistemes Industrials (IOC-UPC) Av. Diagonal 647 Planta 11, 08028 Barcelona, SPAIN Emails: [email protected], [email protected]c.es Abstract Force-closure independent regions are parts of the object edges such that a grasp with a finger in each region ensures a force-closure grasp. These regions are useful to provide some robustness to the grasp in the presence of uncertainty as well as in grasp planning. Most of the approaches to the computation of these regions for Nfingers work on the contact space, implying a N-dimensional problem. This paper presents a new approach to determine independent regions on polygonal objects considering Nfriction or frictionless contacts. The approach works on the object space, implying that it is always a two-dimensional problem and, since it is not necessary to compute all the force-closure space, it becomes a very fast approach. Besides, the approach is also flexible since constraints on the fingers placement can be easily introduced. Some graphical examples are included in the paper showing the simplicity of the methodology. 1 Introduction The obtention of grasps capable of ensuring the immobility of the object despite external disturbances has been a topic of great interest in grasping and manipulation of objects. These grasps are characterized by the properties of form-closure (the position of the fingers ensures the object immobility) or force-closure (the forces applied by the fingers ensure the object immobility) [1]. In order to select a grasp among all the possible force-closure grasps (hereafter FC grasps), algorithms that optimize a quality criterion (for instance, [2], [3], [4]) or algorithms based on heuristics criterions (for instance, [5], [6]) were developed. These algorithms determine fingertips or “precision” grasps, i.e., grasps formed by a set of contacts points on the object where the fingertips will be placed, and they require a good precision in the fingertip placements (in [2] and [3] the robustness in front of the fingers positioning errors is partially treated). In a real execution, the final grasp and the theoretical grasp may differ due to fingers positioning errors. A metric for measuring the sensitivity of a grasp to positioning errors can be found in [7]. In order to provide robustness to the grasp in front of these errors, Nguyen [8] introduced the concept of independent regions, i.e, regions on the object boundary such that a finger in each region ensures ∗This work was partially supported by the CICYT projects DPI2004-03104 and DPI2002-03540 1 a FC grasp independently of the exact contact point, and he developed a geometrical approach to determine the maximum independent regions on polygonal objects using four frictionless contacts and two friction contacts. The problem of determining independent regions using four frictionless contacts was also treated in [9]. Ponce and Faverjon [10] and Ponce et al. [11] extended Nguyen’s approach to three finger grasps on polygonal objects and to four finger grasps on polyhedral objects, respectively. These works are based on a sufficient condition implying that only a subset of FC grasps are evaluated and they are specific for a given number of fingers. Liu [12] and Li, Yu and Tsujio [13] proposed algorithms to determine all the N-finger FC grasps on polygonal objects. These algorithms have not been used to compute independent regions, although in [13] the most stable grasp considering fingers positioning errors is determined. Recently, Pollard [14] presented an approach to determine independent regions on 3D objects based on initial examples, but the selection of a good initial example for a given object is a critical step. This paper deals with the problem of determining independent regions on polygonal objects considering Nfriction or frictionless contacts. Since the space defined by all the FC grasps may be concave (this result can be obtained from [12] and [13] and it will be also shown here) it is decomposed into a set of convex subspaces, establishing each one a necessary and sufficient condition for the existence of a FC grasp and, in order to obtain it, at least one of these conditions must be satisfied. The computational cost of the decomposing algorithm for Nfingers is O(N3). A condition to determine independent regions on each subspace is also presented and, using its geometrical interpretation, the problem of determining independent regions is reduced to find two particular points on the object space. The approach is very fast since it is applied on the object space and it is not necessary to compute the N-dimensional space of all the FC grasps, whose computational cost is at least O(N3log N). Besides, other constraints on the fingers placement can be easily introduced, providing flexibility to the algorithm. The approach developed here follows a previous work of the authors [15] where linear programming were used to obtain maximum independent region on the contact space, while in this paper a faster approach is presented. The main assumptions considered in this work are: 1. Grasped objects are planar and polygonal-shaped. 2. The object edges where the fingers will contact are given. 3. Forces applied by the fingers act only against the object boundary. 4. The fingertip is a point. Note that in this approach there is no constraint regarding the number of fingers neither the number of fingers per edge. 2 Wrench Space 2.1 Representation of forces and torques Let fibe the maximum force exerted by each finger on the object boundary at each contact point. In the absence of friction, fiis the applied force normal to the object boundary and it produces a torque τiwith respect to the object’s center of mass. Considering that fiis normalized to be fi= 1, the components of fi(respect to the reference frame of the object) and τiform the wrench vector ωi=[cosθisin θiτi]T,whereθiindicates the direction normal tho the contact edge. Since fi=1,τiis equal to the distance difrom the object’s center of mass (CM) to the line of action of fi(see Fig. 1.a). 2 fifi fix fiy θi di edge edge ϕ fi,r fi,l fi,t −fi,t fi,n d i,r d i,l di,t di,n CM CM xx yy a)b) Figure 1: a) Frictionless contact; b) Friction contact, where fi,l and fi,r are the primitive forces, fi,n is the normal force and fi,t is the tangential force. When friction is taken into account, fican be decomposed in two components fi,n and fi,t which are respectively normal and tangent to the contact edge (see Fig. 1.b). In order to avoid that the finger slips on the edge, the Coulomb’s law must be accomplished: |fi,n|≥µ|fi,t|,where µis the friction coefficient. This implies that fican be applied in a range of directions around the normal of the contact edge, determining the friction cone. Then, ficanbeexpressedasa positive linear combination of two forces: fi=αi,lfi,l +αi,rfi,r (1) where fi,l and fi,r are the forces along the boundaries of the friction cone, usually called primitive forces. Then, the wrench produced in a contact point can be expressed as a linear combination of two primitive wrenches: ωi=αi,lωi,l +αi,rωi,r (2) with ωi,r =[cos(θi−ϕ)sin(θi−ϕ)τi,r]T(3) ωi,l =[cos(θi+ϕ)sin(θi+ϕ)τi,l]T(4) where θiindicates the direction normal to the contact edge, ϕ= arctan µand τi,r and τi,l are the torques produced by fi,r and fi,l, respectively. Considering that the torque component of each primitive wrench is produced by the corresponding force components tangential and normal to the edge (see Fig. 1.b), we obtain: τi,r =τi,n +τi,t (5) τi,l =τi,n −τi,t (6) where τi,n and τi,t are the torques produced by fi,n and fi,t, respectively. Therefore, the relation between the two primitive torques is τi,r =τi,l +2τi,t (7) 3 2.2 Constraint on the finger forces The forces applied by the fingers can be subject to different constraints [16]. The constraint considered in this work is that the total force exerted by all the fingers is limited, for instance, due to a maximum available power for all the finger actuators. Then, the applied forces can generate a resultant wrench ω= N  i=1 αiωiwith N  i=1 αi≤1(8) where Nis the number of contacts. If friction contacts are considered, then αi=αi,l +αi,r is a linear approximation. Geometrically, the resultant wrench produced by a grasp can be any one inside the polyhedron P1defined in the wrench space as: P1=ConvexHull( N  i=1 {ωi})(9) and, for a FC grasp, P1must contain the origin [17]. 3 Force-closure space Definition 1 The contact space is the space defined by Nparamaters that represent the contact points on a given edges of an object.  Since the direction of the normal force and the primitive forces are known when the contact edge is given, there is a univocal relation between the torque produced by these forces and the exact contact point. Thus, the parameters used in this paper to define the contact space will be the torques produced by the normal forces when frictionless contacts are considered and the torques produced by the primitive forces when friction contacts are considered. Definition 2 The force-closure space, FC-space, is the subset of the contact space where FC grasps are produced.  A methodology to obtain the FC-space as the union of a set of convex subspaces is presented in this section. The obtained result is similar to the result in [13], although the initial considerations are different (in [13] there is not any constraint on the finger forces). Besides, the approach developed here determine additional information on the finger forces that is quite useful in the determination of the independent regions. 3.1 Convex FC-subspace using frictionless contacts Consider four frictionless contacts applying forces fi,i=1, ..., 4. Let Pfbe the polygon defined by these forces (it coincides with the projection of P1on the force space). In order to obtain a FC grasp, 0∈P fmust be satisfied. The following terms will be used in the determination of the FC-subspaces. Definition 3 The Real Range of τi,Ri, is the set of values of τiproduced by the contact force fi that are physically possible due to the length of the contact edge.  4 Definition 4 The Directional Range of τi,Rfci, is the set of values of τiproduced by the contact force fithat allow a FC grasp considering that the contact edge has infinite length (i.e. only the “direction” of the edge is considered).  From the two above definitions, the existence of a FC grasp implies that Ri∩Rfci=Ø. Since Riis known, the set of valid torques that produces a FC grasp can be determined by finding Rfci. Four frictionless contacts generate the minimum number of wrenches necessary to obtain a FC grasp [18], generating a convex hull P1with minimum number of faces. Since a FC grasp must satisfy 0∈P 1[17] and P1is convex, the Directional Range Rfci,i=1, ..., 4, is a continuous set that has one or two finite extremes. Then, the type of Directional Range can be: Infinite:Rfcihas only one finite extreme τim. Then, Rfci=[τim,∞)orRfci=(−∞,τ im]. Limited:Rfcihave two finite extremes τimand τim. Then, Rfci=τim,τ imor Rfci=τim,τ im. Proposition 1 Consider four applied contact forces fi,i=1, ..., 4. The number of extremes and, therefore, the type of the Directional Range Rfciof each torque τi, can be determined knowing how many pairs of the following coefficients are non-positive: βi,jk =sin(θi−θk) sin(θj−θk)(10) βi,kj =sin(θj−θi) sin(θj−θk)(11) where θi,θjand θkare the directions of the respective forces.  Proof: Let τimbe an extreme of Rfci.SinceP1is convex, if τimdefines a vertex of P1,then 0∈∂P1,∂P1being the boundary of P1,and0can be expressed as a positive linear combination of the three vertices that define the face of ∂P1containing 0, i.e. 0=αiωim+αjωj+αkωkwith αi,α j,α k≥0andαi+αj+αk=1. Solving this expression for ωimresults cos θi=βi,jk cos θj+βi,kj cos θk(12) sin θi=βi,jk sin θj+βi,kj sin θk(13) τim=βi,jkτj+βi,kjτk(14) with βi,jk ≤0andβi,kj ≤0 (since ωim=0,βi,jk and βi,kj can not be simultaneously null). Then, there are three equalities with only two unknowns, βi,jk and βi,kj. If the forces fjand fkare not parallel, equalities (12) and (13) are independent, and the two unknowns βi,jk and βi,kj can be obtained from them as equations (10) and (11). If fjand fkare parallel (i.e. θj=θk+tπ,t∈{0,1}, meaning that there are two fingers on the same edge or on parallel edges) equalities (12) and (13) have no solution for βi,jk and βi,kj, and therefore, from equation (14), τimdoes not exist. Since no more than two forces can have the same direction in a four frictionless FC grasp, a minimum of one extreme always exist. As a result, the number of extremes of Rfciare determined using information related only with the applied forces without taking into account the values of the torques.  Proposition 2 Given four applied forces, there are the following number of each type of Directional Ranges: 5 fx fx fx fy fy fy fh fh fh fi fi fi fj fj fj fk fk fk −fh −fh −fk −fj Pf Pf Pf a)b)c) Figure 2: Examples of the determination of the types of Directional Ranges from the applied forces: a) General case: Rfciand Rfcjare Infinite and Rfchand Rfckare Limited; b) Particular case: Rfckis Limited and Rfch,Rfciand Rfcjare Infinite; c) Particular case: the four Directional Ranges are Infinite. General case: If all the angles between the applied forces are different from π, there are two Infinite and two Limited Directional Ranges (Fig. 2a). Particular cases: If the angle between two forces is π, there are three Infinite and one Limited Directional Ranges (Fig. 2b), and if the angles between two pairs of forces are π, the four Directional Ranges are Infinite (Fig. 2c).  Proof: From Proposition 1 the type of Directional Range of τiis determined by the number of pairs of coefficients βi,jk and βi,kj that are non-positive, for {i, j, k}∈{1,2,3,4}and i=j=k.From equations (10) and (11), these coefficients depend on the directions of three applied forces, which also define the coefficients βj,ik and βj,ki,andβk,ji and βk,ij, with the following relations between them βi,jk =1 βj,ik =−βk,ji βk,ij (15) βi,kj =−βj,ki βj,ik =1 βk,ij (16) These relations imply that if one pair of coefficients is non-positive so are the other two pairs, determining one extreme for Rfci,Rfcjand Rfck. Then, a valid subset of three forces generates three extremes. Since each force appears in three from the four possible subsets of forces, two subsets of forces determine the extremes, otherwise there would be a Directional Range with more than two extremes or without any extreme, which is not possible. In the general case, the two subsets of forces generate six different finite extremes for the four Directional Ranges. Therefore, there are two Directional Ranges with two extremes (so they are Limited), and two Directional Ranges with one extreme (so they are Infinite). In the particular case that the angle between two forces is π, the two subsets of forces generate five different finite extremes and one infinite extreme. Therefore, there are one Directional Range with two finite extremes (so it is Limited), and three Directional Ranges with one extreme (so they are Infinite). In the particular case that the angle between two pairs of forces is π, the two subsets of forces 6 generate four different finite extremes and two infinite extremes. Therefore, the four Directional Ranges have one finite extreme (so they are Infinite).  Knowing the directions of four applied forces, it can be easily identified which torques have Limited and which ones have Infinite Directional Ranges (it can be checked from equations (10) and (11)): in the general case, the two Infinite Directional Ranges correspond to the torques generated by the two forces that lie between the negated of the other two (as in Fig 2a), and in the particular case that the angle between to forces is π, the three Infinite Directional Ranges correspond two the torques generated by the other two forces and the force that lies between them (as in Fig 2b). Lemma 1 Let Rfciand Rfcjbe two Infinite Directional Ranges with fiand fjdefining two consecutive vertices of Pf.IfRfcitends to ±∞ then Rfcjtends to ∓∞. Proof: Consider first the general case with two Infinite and two Limited Directional Ranges. Let Rfckbe one of the two Limited Directional Ranges. It is not known a priori if Rfck=[τk1,τ k2] or Rfck=[τk2,τ k1], then the two cases must be considered. If Rfck=[τk1,τ k2]thenτk1≤τk≤τk2. Substituting τk1and τk2by their expressions derived from equation (14), we obtain βk,hjτh+βk,jhτj≤τk≤βk,ihτi+βk,hiτh(17) If τiand τjare solved from equation (17), then τi≤1 βk,ih (τk−βk,hiτh)(18) τj≥1 βk,jh (τk−βk,hjτh)(19) Therefore, τihas an upper bound while τjhas a bottom bound implying that Rfcitends to −∞ and Rfcjtends to +∞.IfRfck=[τk2,τ k1] then, with the same reasoning, equivalent equations to (18) and (19) are obtained with swapped inequalities. Then, τihas a bottom bound while τj has an upper bound implying that Rfcitends to +∞and Rfcjtends to −∞. The two particular cases can be tackle as limits of the general case. Adding δθ arbitrarily small to one of the aligned forces, the particular cases are transformed into the general case. Then, the above procedure can be applied obtaining the same results when δθ →0.  From Lemma 1, the following necessary and sufficient condition for the existence of a FC grasp can be enunciated. Necessary and sufficient condition: Four frictionless contacts allow a FC grasp if and only if sign(σ)=sign() (20) with σ=βi,hkτh+βi,khτk−τi(21) =βj,hkτh+βj,khτk−τj(22) where τiand τjhave Infinite Directional Ranges and fiand fjdefine two consecutive vertices of Pf 7 τiτj τh τh τkτk S+ i S− i S+ j S− j σ=0 =0 a)b) Figure 3: Polyhedrons resulting from the projection of: a) S+ iand S− ion the subspace {τh,τk,τi}; b) S+ jand S− jon the subspace {τh,τk,τj}. Considering the Real Range of each torque, the geometrical interpretation of this necessary and sufficient condition is: (S+ i∩S− j)∪(S− i∩S+ j)= Ø (23) where S+ i,S− i,S+ jand S− jare the following polytopes: S+ i={{τh,τ i,τ j,τ k}|τh∈Rh,τ i∈Ri,τ k∈Rk,σ ≥0} S− i={{τh,τ i,τ j,τ k}|τh∈Rh,τ i∈Ri,τ k∈Rk,σ ≤0} S+ j={{τh,τ i,τ j,τ k}|τh∈Rh,τ j∈Rj,τ k∈Rk,≥0} S− j={{τh,τ i,τ j,τ k}|τh∈Rh,τ j∈Rj,τ k∈Rk,≤0} These polytopes can be represented as polyhedrons in two different 3-dimensional subspaces defined by {τh,τi,τk}and {τh,τj,τk}, as in Fig. 3. By construction S+ i∩S− jand S− i∩S+ jare convex sets. Therefore, four applied forces determine two convex FC-subspaces. Equations (21) and (22) have another useful geometrical property on the object space: the lines of action of fh,fiand fkintersect at the same point when σ= 0, and the lines of action of fh, fjand fkintersect at the same point when = 0. Grasps with this property was called critical grasps in [9] since it separates the FC grasps from the non-FC grasps. In [9] it was considered that any intersection of three forces may determine a critical grasp. Equations (21) and (22) restrict this result determining only two intersections and the three forces that intersect in each one. 3.2 Convex FC-subspaces using friction contacts. The procedure developed to obtain the necessary and sufficient condition for frictionless contacts is based on the knowledge of four applied forces. Since the primitive forces that define the friction cones are also known given the contact edges, the procedure developed in the previous subsection can also be applied with four primitive forces when friction is considered. Note that the primitive torques are not independent of each other and they must satisfy equation (7) to obtain a real FC grasp. 8