Soft Comput DOI 10.1007/s00500-016-2377-6

METHODOLOGIES AND APPLICATION

Optimizing force closure grasps on 3D objects using a modified genetic algorithm V. Rakesh1

· Utkarsh Sharma2 · S. Murugan1 · S. Venugopal1 · T. Asokan2

© Springer-Verlag Berlin Heidelberg 2016

Abstract The problem of automated grasp generation is exacerbated by the infinite types of objects to be handled by robots. In this work, the issue is cast as an optimization problem and a modified genetic algorithm-based approach has been formulated for the synthesis of high-quality grasps. The convex hull of the grasp contact wrenches is built, and the largest ball is inscribed within it. The radius of this resulting ball, centered at the origin, is used to represent the grasp quality. An initial feasible grasp is increased in quality by generating wrench population considering the complete body for an exhaustive search. Tessellated objects are utilized for the planner to ensure the applicability of the approach on complex shapes. The performance efficacy of the proposed method is numerically showcased through various frictional and non-frictional prehensile contact examples and is featured along with the results of an existing heuristic method on similar models with moderate and dense tessellation. Keywords Robot grasp synthesis · Tessellated object · Convex hull · Grasp quality · Modified genetic algorithm (GA)

Communicated by V. Loia.

B

V. Rakesh [email protected]

1

Robotics and Remote Handling Section, Indira Gandhi Centre for Atomic Research (IGCAR), Kalpakkam, Tamil Nadu 603 102, India

2

Department of Engineering Design, Indian Institute of Technology Madras, Chennai 600 036, India

1 Introduction Reliable and safe grasping of objects, akin to human handling, is a fundamental need and very challenging to accomplish in the robotic world. In order to use robots effectively, grasp planning becomes imperative for robotic hands and tools. Research on robot grasp synthesis is devoted to generating schemes to find the best possible location for robot finger contact on the object. In order to achieve a stable grasp, two concepts are studied extensively in literature; (a) Form Closure achieves complete kinematical restraint of the object. In this case, the positions of the fingers ensure object immobility, (b) Force Closure grasps completely restrains the object in such a manner that the fingers can apply appropriate forces on the object to resist disturbances in any direction. The fundamental difference between form closure and force closure is the dependence on friction, for the latter, signifying that it requires fewer contacts (Mason 2001). Force closure (FC) and form closure are the most important issues during studies for ensuring stability. In this regard, Reulaux (1963) and Lakshminarayana (1978) specify the sufficiency conditions for form closure of 2-D and 3-D objects. Research conducted on force and form closure, through analytical approaches, has been discussed at length by Bicchi (1995). Ding et al. (2000) designed an algorithm for n-finger force closure grasps seeded from an initial random grasp. Local minima problems are also encountered in certain cases for the algorithm with 7-finger form closure given by Ding et al. (2001). When the complexity of the object model becomes unwieldy, Li et al. (2003) came up with an algorithm for 3-finger grasps for 3-D objects by converting it into a 2-D problem. Liu et al. (2004) gave an efficient algorithm for the heuristic determination of form

123

V. Rakesh et al.

closure grasps for objects with a given set of discrete surface points. Heuristics and computational methods are used to solve for the force-form closure, posed as an optimization problem. Mirtich and Canny (1994) search all combinations of possibilities for finding an optimal grasp. Niparnan and Sudsang (2004) have proposed a method for fast computation of 4-fingered FC grasps from surface points. They utilize an efficient approach to trim the grasp search space by locating regions of friction cone intersection along with randomized checking for FC condition. Gradient descent-based techniques have also been used by Zhu and Wang (2003) and Zhu and Ding (2004). Choosing the best candidate grasp from pregenerated grasp sets has been in the scheme of reported work (Fischer and Hirzinger 1997; Borst et al. 2003; Miller et al. 2003). Lippiello et al. (2010, 2013) reduce the computational complexity by searching regions of minimal inertial grasp on the object. Thereafter a reduced selected set of grasps are searched for the optimal grasp based on quality. El-Khoury and Sahbani (2010) have developed a strategy for grasping unknown 3D objects by using a strategy that identifies the handles on the object as related to the task. This theme of grasping by parts is also reflected in the work of Huebner et al. (2008) where they approximate objects using multiple bounding boxes by fit-and-split. Good grasps on the complete object are obtained by planning grasps on one or more parts of the object. Genetic algorithms have also been considered within the realm of heuristic grasp planning methods. In this context, Fernandez and Walker (1998) proposed a genetic programming to find quality grasps using three-fingered robot hands, though the approach was tested only with three-fingered grasps for regular shapes and with a binding on the allowed hand-object placement. Chella et al. (2007) presented a blend of genetic algorithm and neural network which was demonstrated only for 2D objects represented with parametric functions. Furthermore, Mannepalli et al. (2010) used GA for prismatic 2D objects. Daoud et al. (2011) provide a grasp improvement strategy using GA, but the method is shown for regular shapes of known geometry. The major contribution of the current work is the use of a modified GA (detailed subsequently) for a generalized grasp planner for complex objects. Additionally, the formulation and implementation of grasp synthesis problem, in the frame-work of the modified GA also forms an important contribution of the present work, thereby facilitating the search and generation of high-quality grasps. It is evident that there is a need to search for efficient methods and algorithms for the synthesis of grasps on 3dimensional objects. A good grasp planner should devise a formulation enabling the synthesis of stable grasps which can be adapted to different objects. This effectively means that the representation of the object should be simple for

123

the grasp planner to process, without increasing the process time. Despite large efforts to devise planners for complex object models, these methods are subject to two major issues. The first issue is that analytically it is difficult to process complex objects for automated grasp generation. The second point of contention is that computational times required for such cases are prohibitively high. These challenging aspects form the motivation and objective for the interesting study of generating optimized high-quality grasps, in the current work. Section 2 briefly presents the background terminology involved in the current work along with the problem statement. The computational tools, along with details of the adopted methodology, are detailed in Sect. 3. To evaluate the feasibility, the implementation of the method on a few case studies, and the results are presented along with an existing heuristic method on similar models, with moderate and dense tessellation, in Sect. 4. The last section (Sect. 5) concludes the work encapsulating the contributions and discusses the future work. In this work, the grasp search approaches are object-centric and the results are applicable in the domain of fixture design also. The reachability of the solution grasps by any specific hand model is not addressed within the ambit of this work.

2 Terminology, notation and problem definition In order to ensure form closure, i.e., with frictionless contacts, a minimum of four and seven fingers are necessary in the 2D and 3D cases, respectively (Reulaux 1963; Lakshminarayana 1978). Markenscoff et al. (1990) proved that these conditions are applicable for objects whose surfaces do not possess rotational symmetries. With the Coulomb friction model, for force closure, three and four fingers are necessary for 2D and 3D objects, respectively (Markenscoff et al. 1990). In certain specific cases, it may be possible to achieve force closure with fewer fingers (Nguyen 1988; Chen and Burdick 1993). As an example, two contacts on opposite sides of 2D object like a parallelogram or a square (i.e., with parallel edges) produce a force closure grasp. 2.1 Wrenches and grasp quality The robot finger-tip exerts forces at the contact points and also generates torques with respect to the center of mass. The force and torque vector concatenation defines the wrench at a contact. In practice, robot finger-tips offer very limited resistance to rotation and hence behave like a hard finger, thereby giving point contacts (Nguyen 1986). In the analysis of prehensile contacts, as in the scope of this work, a point contact is defined by the position p i and the corresponding contact normal n i , where p i ∈ R3 , n i ∈ R3 , as shown in

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Fig. 1 a The robot finger-tip contact points, p i and the corresponding normals, n i . b Linearizing the friction cone at robot finger-tip contact

Fig. 1a. The triangulated surface representation used for the body is also depicted in Fig. 1a. In frictionless cases, for a contact force f i applied by the finger-tips, the corresponding wrench is expressed as  ωi =

fi τi



 = αi

ni pi × ni

 (1)

where α i is the magnitude of the force (a non-negative constant) and τ i the torque with respect to the center of mass (CM). For the specific case, of α i = 1 primitive contact wrenches arise. The Coulomb friction model at the contact point ensures no-slippage if the grasp force satisfies f 2i x

+

f 2i y

≤μ

2

f 2i z

(2)

where f i x , f i y are the tangential components and f i z is the normal component of the grasp force at the contact point. The coefficient of friction is denoted by μ. The friction cone is defined by the nonlinear constraint in Eq. (2), and simplified by a linearized r -sided pyramid, as shown in Fig. 1b. The normalized vector along edge j, of the cone, is represented by s i j , for the grasp force f i , at contact point i. This enables us to represent the grasp force by fi =

r 

αi j s i j ; αi j ≥ 0

(3)

j=1

The wrench at the point i is given by ωi =

r  j=1

 αi j ω i j ; ω i j =

si j pi × s i j

 (4)

Fig. 2 Depiction of GWS and grasp quality for a hypothetical 2-D object

The primitive contact wrenches are represented by ω i j . Therefore, the m-fingered grasp G = { p1 , p2 , . . . , pm } has corresponding wrench set as: W = {ω11 , ω12 , . . . , ω1r , . . . , ω i1 , ω i2 , . . . , ω i r , . . . , ω m1 , ω m2 , . . . , ω mr }

(5)

and W ∈ R6×mr denotes the grasp matrix, for the frictional case. In order to evaluate successful grasps, the notion of grasp quality was introduced by Ferrari et al. (Ferrari and Canny 1992) which is most popularly used among the many proposed in literature (Suárez et al. 2006, Roa and Suárez 2015). This is characterized as the radius of the largest wrench space ball, inscribed within the convex hull of the grasp contact wrenches (Fig. 2), with the center at the origin. It is essen-

123

V. Rakesh et al.

tially a measure of the largest perturbation wrench that the grasp can withstand from any direction. For a grasp with form or force closure, the origin lies inside the convex hull of the grasp contact wrenches. 2.2 Problem definition The problem, as defined in this work, is to find high-quality grasps on complex objects with an exhaustive global search over the complete shape. The intention is to do it in reasonable run times to achieve this. The grasp synthesis is to be conducted for both non-frictional and frictional cases. 2.3 Assumptions and inputs As mentioned in Sect. 2.1, point contacts between the robot fingers and the object are considered. A tessellated object (triangulated mesh) scheme is used as an input to the automated grasp planner. The set  of a large number triangular meshes, ensures that the accuracy of the shape are adequately represented for complex objects. Each point on the object surface is denoted by position vectors pi with respect to the CM and also has a corresponding contact normal n i pointing inwards into the body, as already depicted in Fig. 1 a. It must be noted that the triangles must have a homogenous size. This helps to ensure that each of planar surfaces have an ample number of triangles. Non-homogeneity in the triangle sizes may lead to a dense concentration of smaller triangles on certain surfaces with a sparse number of bigger triangles on other surfaces. Under such circumstances, the number of potential contact points on the latter surfaces could be drastically reduced.

3 Proposed solution scheme and computational tools In this paper, the proposed solution scheme derives an optimal grasp synthesis by an exhaustive search with modified genetic algorithm (GA). An initial FC grasp is necessary to initiate the search by the modified GA. 1. An initial force closure grasp is generated using the method of hyper-plane generation, i.e., Algorithm 1 proposed by Roa and Suarez (2007, 2009). 2. The initial grasp is improved in quality by the modified GA procedure (detailed subsequently). The quality of the grasp, as mentioned in Sect. 2.1 is the objective function for the optimization algorithm. The exhaustive global search procedure to ensure the increase in quality is the predominant contribution of this work. The various aspects of the steps outlined above are detailed in the following sections.

123

Fig. 3 Synthesizing an FC grasp (Roa and Suarez 2007, 2009)

3.1 Force closure test A given grasp is said to be a force closure grasp iff the origin lies strictly inside the convex hull of the primitive contact wrenches. Such a test is expensive in terms of computational running time. The test is carried out in two phases. First, the equation of the facets is derived from the vertices. In the second phase, these equations are utilized to check whether the origin lies on the same side for all the facets of the convex hull. The sufficiency condition dictates that any other point, within the convex hull must also lie on the same side as the origin with respect to all the facets. In this case, the centroid of the hull is used for the verification. This is because the centroid of the convex hull must necessarily lie within the convex hull. Degenerate cases must be irrevocably discarded.

3.2 Generating the force closure grasp This section briefly describes the procedure for generating the FC grasp if the FC test as depicted in the previous Sect. 3.1 fails, as proposed by Roa and Suarez (2007, 2009). One of the points from the failed FC grasp is replaced with the origin in the grasp wrench space as shown in Fig. 3. The intermediate convex hull resulting due to example wrenches ω1 , ω2 and O is also shown in the Fig. 3. The supporting hyper-planes H 1 and H 2 at the origin for this intermediate convex hull are determined. The common region χ 2 , obtained from these supporting hyper-planes on the other side of the origin, is only searched for a potential wrench, ω3 . It is abundantly clear that replacing the origin, O with this wrench, ω3 ensures that the new convex hull strictly includes the origin and thus makes it a FC grasp.

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Minimize {C ost Funct i on}

(6)

Subject to: m  j=1 n 

Xi j ≤ 1

for every i

(6a)

Xi j = 1

for every j

(6b)

i=1

X i j ∈ {0, 1}

Fig. 4 Assignment matrix of the robot finger with the surface positions depicting the requirements (a)–(b)

Specific details about this algorithm/method for generating the FC grasp, can be found in Roa and Suarez (2007, 2009).

(6c)

The assignment problem is a zero-one problem where variable X i j takes value ‘1’ when position ‘i’ is assigned to object point ‘j’ and ‘0’ denotes that no finger is assigned to the object body point in question. This aspect is enforced by condition 6a above. A finger at an object body point generates a corresponding wrench with respect to the object center of mass. It must be noted that the notion associated with building the cost matrix, as in case of the assignment problem, does not hold true here, i.e., there is no cost associated with a single robot finger assigned to a surface position. The corresponding requirement, as described above, cast as an optimization problem, can also be stated as: Maximize {Grasp Quality, Q}

3.3 Methodology details The grasp synthesis, as specified here, is similar to a flowshop scheduling problem or a general assignment problem. The current requirement, as it stands, can be stated as:

p

where

p = { p1 , p2 , . . . , p m }

subject to :

pi ∈ 

and

p i = p j ; ∀ p i , p j ∈ p, i = j , and i ≤ j , j ≤ m

(a) Among all the triangulated points, only one fingertip lands on a body point. (b) A particular finger can be assigned only to one position on the object. (c) The cost function according to the placement conditions in (a) and (b) should be minimized. The requirements (a)–(b) are shown through the matrix in Fig. 4. The locations of the ‘1’ in the matrix suggest the existence of a particular finger at a specific location of the body. It is assumed that there are ‘m’ fingers of the robot and the body is well represented by ‘n’ surface points. It follows that for a highly detailed representation of the body for the grasp planner, ‘n’ would be a high number. This naturally poses a serious challenge for a grasp planner to conduct an exhaustive search with a high number of body points, in acceptably short run-times. For most practical cases, the value of ‘m’ can be as high as 7. The assignment problem can be mathematically formulated as:

(7) (7a) (7b) (7c)

The details about the cost function, Q are described in the next section. 3.3.1 Cost function As discussed in Sect. 2.1, a candidate grasp is represented as G = { p1 , p2 , .... pm }. The cost function is the quality associated with the grasp and is framed as follows: 1. Calculate the convex hull of the wrench corresponding to the points in G. 2. If the convex hull contains the origin, then the grasp is a feasible FC grasp and the quality, Q, is measured as the perpendicular distance of the convex hull facet, closest to the origin. Since the function is to be minimized in the implementation, the quality is assigned as −Q. 3. If the convex hull does not contain the origin, the candidate solution is penalized with a high score. In essence, it suffices to use any penalty value that borders on the upper bound possible for the cost function, which in this case is zero. Hence, any value greater than zero will be adequate.

123

V. Rakesh et al.

3.3.2 Details about the modified GA A typical genetic algorithm (Goldberg 1989; Deb 2009), in its rudimentary form, generates an initial population with a corresponding fitness value for each individual. Then the best individuals are selected, and genetic operations viz. crossover and mutation are performed on them. The individuals produced as a result of these genetic operations are checked for their fitness and incorporated into the population. The GA iterations for optimization are closed by following one of the two criteria: either after convergence is reached or after a predecided number of generations (generation limit) are passed. The algorithm differs in minor representations depending on the domain of use. The genetic algorithm used to solve the grasp synthesis problem here, requires a special crossover and mutation function because of reasons mentioned herein. Binary encoding of length ‘n’ is used with exactly ‘m’ number of ‘1’s. As a special requirement of the problem at hand, the number of ‘1’s on a bit string should remain m during and after the crossover and mutation function. (a) Encoding A binary encoding is used with a total string length of n where m number of ‘1’s are present. Hence, – The bit string length is n. A bit denotes a wrench which corresponds to a body surface point in case of frictionless grasps and a set of j wrenches corresponding to the jsided linearization of friction cone associated with a body surface point in case of frictional grasps. – The total number of ones is m denoting number of robot finger positions. (b) Crossover A sophisticated crossover, with the ability to preserve the number of ‘1’s, is implemented. The total number of ‘1’s should remain ‘m’ before and after the crossover. This was proposed as the Genetic Fix method by Ngo and Li (1998). A novel application of this method is used in this work. Implementation of the Crossover A first-in-last-out (FILO) stack is instantiated to store the bit position, ‘k’, from two mating parents, A and B, such that the corresponding bit pair position ( Ak , B k ) is an opposite pair. A bit pair ( Ak , B k ) is said to be opposite if Ak ⊕ B k = 1, where ⊕ denotes the exclusive-OR (XOR) operator. In order to perform the crossover, two random points c1 and c2 are generated as sites for starting and ending the search and execution of the crossover if and when

Fig. 5 Example of crossover in modified GA

Let s1 be the top element in the stack. Now, A j and As1 , are compared. If they are same, then j is pushed into the stack; otherwise, the pair denoted by j is exchanged with the pair identified by s1 and simultaneously s1 is popped from the stack. The process is continued up to c2 . An illustrating example is depicted in Fig. 5. (c) Mutation The mutation operation has to be necessarily conducted in opposite bit pairs for a particular individual represented in binary. This is necessary to conserve the number of ‘1’s in an individual. As an implementation example, let the ith bit position of an individual be denoted by bi . A random b j is located such that bi ⊕ b j = 1, for mutating bi . On locating this, bi and b j are swapped. 3.4 Algorithm steps The general pathway to conduct the search for a high-quality grasp based on the scheme proposed in this work is as follows:   1. An initial FC grasp G 1 = p1 , . . . . . . , p7 is found using Algorithm 1 given by Roa and Suarez (2007, 2009) along with the associated wrench set W 1 = {ω1 , . . . . . . , ω7 }. 2. For the initial population, randomly generate the population members, one less than population size, with the binary encoding scheme defined in Sect. 3.3. The left out population member is assigned the binary vector associated with the wrench found in step 1 to guarantee a FC Grasp. 3. Run the GA till generations do not exceed the generation limit. 4. Firstly evaluate the fitness of each population member of the initial population. 5. For each generation (a) Apply the selection operation to get the parents, based on the fitness of the population members. (b) Perform genetic operations of crossover and mutation on the parents obtained in the previous step as explained in Sect. 3.3.2 to arrive at new population. (c) Evaluate fitness of the new population.

Ai ⊕ B i = 1, and c1 < i < c2 The particular site position i is pushed into the stack and process is continued till an index j is found A j ⊕ B j = 1.

123

The algorithm as detailed in the previous sections are tested on four different objects, as case studies, to its performance efficacy.

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Fig. 6 a Rectangular parallelepiped. b Chess knight

4 Case studies Case studies have been conducted for the grasp synthesis strategy using the modified GA, as proposed in this work on four different types of objects. The algorithms have been implemented within the MATLAB programming environment on a personal computer running Windows 7, with an Intel i3, 2.2 GHz processer. For the objects, the non-frictional (NF), i.e., frictionless, as well as the frictional grasp synthesis is conducted using our proposed method, to generate optimal grasp. The first two of the four objects used for the case studies are a rectangular parallelepiped and a chess knight model, shown in Fig. 6a and b respectively. The results of implementation and details of the other two objects are discussed subsequently. The objects differ among themselves with plane flat surfaces, re-entrant curves, convex body curvatures and also a type (Stanford Bunny) containing long/sleek appendages 4.1 Non-frictional grasp case studies The non-frictional grasp synthesis is carried for the rectangular parallelepiped and chess knight and the details of the same are given in the ensuing subsections. 4.1.1 Non-frictional grasp on rectangular parallelepiped A rectangular parallelepiped, as shown in Fig. 6a, demonstrates the efficacy of the randomized algorithm to generate the initial feasible FC grasp. Seven fingers have been used to ensure FC grasp for the non-frictional case in 3-D (Ref. Sect. 2). The implementation of optimization algorithm is validated by results depicted for the rectangular parallelepiped case study in Roa and Suarez (2009). It must be noted that

in this work, the parallelepiped surface has been replicated with moderately dense tessellation of 1880 triangles showcased along the similar lines of the one presented in Roa and Suarez (2009), with 1628 triangles. The algorithms were run successively 50 times to generate the average initial FC grasp quality and final optimized grasp quality. The results from one of the runs from the 50 trials are demonstrated in Fig. 7a and b, respectively. The red arrows represent the finger-tip positions. In this particular run, the initial grasp quality of 0.010 was gradually improved over 30 generations, to 0.275 using a population size of 400 for the GA, as shown in Fig. 7c. The GA optimization required 34.5 s for this run. Over a span of 50 trial runs on the parallelepiped, the average initial grasp quality of IQ = 0.017 was increased to a final grasp quality of FQ = 0.200. The individual ratio of FQ/IQ for each run was calculated, and the average of 50 such ratios is seen to be 39.8. The denser tessellation and moderate generation number of 30 justifies the slightly high average time of 35.1 s required for the grasp optimization. It is seen that slightly more computational run time has actually ensured a much higher final grasp quality. As an original scheme proposed in this work, for grasp quality improvement, by the modified GA, one of the salient points to note is that the GA parameters viz. number of generations and population size play an important role. This is depicted in Fig. 8. For the rectangular parallelepiped, the optimization algorithm was run 50 times for various combinations of the population size and generation limit. The population sizes used was 50, 100, 200 and 400. On the other hand, the number of generations used was 10, 20 and 30. Hence, the average result of the 50 runs for these 12 combinations has been shown in Fig. 8. An impor-

123

V. Rakesh et al.

Fig. 7 a The initial FC grasp on a rectangular parallelepiped. b The GA optimized FC grasp. c Grasp quality increase during the GA progress

Fig. 8 Average quality versus population with different generation limits for non-frictional grasp on rectangular parallelepiped

tant point to note is that extremely high-quality values may be achieved for high population sizes and with high generation limit. Depending on the magnitude of quality desired, the user has to decide on the trade-off on the times required. 4.1.2 Non-frictional grasp on chess knight Optimal grasp synthesis was also done for non-frictional case of a chess knight of Fig. 6b. This object has again been used as a similar case along the lines of model used in Roa and

123

Suarez (2009). A higher tessellation of 21,357 triangles has been used to render the object surface. A particular result of the grasp synthesis and optimization is shown in Fig. 9. The modified GA used a population size of 200 with a generation limit of 20. An initial FC grasp of quality 0.002 was improved to 0.129 taking a run time of 38.6 s for the optimization procedure. This is shown in Fig. 9c. Over 50 runs the average initial grasp quality of IQ = 0.057 was improved to an average final quality of FQ = 0.126. The average of the ratios of the final grasp quality to the initial grasp quality is seen to be 32.4, over 50 runs.

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Fig. 9 a The initial FC grasp on a chess knight. b The GA optimized FC grasp. c Grasp quality increase during the GA progress

The average run time is 63.8 s. The high average final grasp quality demonstrates the necessity and use of the proposed modified GA method for grasp quality enhancement. Changing the generation limit and population sizes, the optimization procedure was applied on the chess knight, with each particular combination run for 50 times. The results are shown in Fig. 10. It is seen again that the very high grasp qualities of 0.163 may be ensured by using high generation limits and population sizes. 4.2 Frictional grasp case studies The frictional grasp synthesis is implemented for the test case objects, and the details of the same are given in the succeeding subsections. 4.2.1 Frictional grasp on chess knight The frictional grasp planning, with 4 fingers (Ref. Sect. 2), was also done for the chess knight. In this current work, the implementation to generate the initial FC grasp ensures that all the primitive wrenches for a particular finger-tip have to necessarily lie in the region χ 2 (Ref. Fig. 3) to ensure strict initial FC grasp generation. For each tip position, an 8-sided pyramid has been used for the linearly approximation of the friction cone, and a friction coefficient of 0.2 is assumed. Using a generation limit of 20 and a population size of 200, the results from one of the runs has been shown in Fig. 11c. The grasp quality improves from 0.033 to 0.162 in 389.3 s. The average values of the initial and final grasp quality are IQ = 0.065 and FQ = 0.146 over 50 runs. The average of the ratios of the final grasp quality to the initial grasp quality, is seen to be 4.6, over 50 runs. The average time for these runs is 368.8 s. These case studies show the general applicability of the method for optimal grasp synthesis.

Using different population size and generation limit as parameters, the plots of Fig. 12, shows the possibility of ensuring high-quality grasp as the user may require. 4.2.2 Frictional grasp on Stanford Bunny and Duck In order to further check the performance efficacy of the method, the grasp optimization for the frictional case, through modified GA, was tested on two models of Stanford Bunny and a Duck, shown in Fig. 13. The Stanford Bunny has been represented with a dense tessellation of 33,352 triangles on its surface. The duck has been modeled with a moderate surface tessellation of 8228 triangles. In a trial run, a high quality of 0.170 is achieved on the Stanford Bunny model from an initial grasp quality of 0.078. This takes 407.1 s for the optimization, with a population size of 200 and a generation limit of 20. The result is shown in Fig. 14. The optimization was tested over 50 runs and the average initial grasp quality of IQ = 0.072 was improved to a final grasp quality of FQ = 0.197 with average optimization run times of 359.6 s. The average of the ratios of the final grasp quality to the initial grasp quality, is seen to be 3.9, over 50 runs. The result from a trial run, for the grasp optimization on the Duck model, is shown in Fig. 15. For the specific run of Fig. 15, the optimization algorithm improved the initial grasp quality of 0.139 to an enhanced value of 0.308, within a generation limit of 20 and a population size of 200. The run time in this trial was 367.2 s. Successive multiple runs (50 in number) improved the average initial grasp quality of IQ = 0.086 to a final grasp quality of FQ = 0.186. The average run time taken was 327.3 s. The average of the ratios of the final grasp quality to the initial grasp quality, is seen to be 3.2, over 50 runs.

123

V. Rakesh et al.

Fig. 10 Average quality versus population with different generation limits for non-frictional grasp on chess knight

Fig. 11 a The initial frictional FC grasp on a chess knight. b The GA optimized frictional FC grasp. c Grasp quality increase during the GA progress

4.3 Summary of results The results of the case studies in Sects. 4.1– 4.2 using models of moderate and high tessellation demonstrate that the present method using modified GA is capable of increasing the grasp quality value. The running time provides an estimate about the computational cost of the method, and not necessarily the relative merit of this method. The objects utilized are similar to the ones used by Roa and Suarez (2007,

123

2009). In fact, due to the absence of standard models for comparison in this domain, the objects, for the case studies in this work, have been provided with moderate and high tessellation. The moderate and high tessellations help to exhibit that the method is applicable for processing detailed models, thereby also increasing the available resolution of the search space for the optimization design variables. The progress of the grasp quality improvement in Figs. 7c, 9c, 11c, 14c and 15c shows that there are phases when the

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Fig. 12 Average quality versus population with different generation limits for frictional grasp on chess knight

Fig. 13 a Stanford Bunny. b Duck

grasp quality increases suddenly. The reason for this can be traced to the fact that each individual member of the population, in the modified GA pool, is a n-length binary string with a sparse number of ‘1’s. The total number of ‘1’s is m, and n >> m. The modified crossover and mutations operation (Ref. Sect. 3.3.2) which involve the manipulation of the ‘1’s contribute to the grasp quality improvement. The paucity of the ‘1’s in the string lead to the sporadic jumps of the grasp quality. For example, in the case of the frictional grasp on chess knight with four fingers, the binary string length of an

individual member of the modified GA is 21357 and there are only 4 sites populated with ‘1’ in the string. Therefore, with rigorous experiments on test-cases, it is decided to use the generation limit to terminate the process. The results of the individual runs in Sects. 4.1.1– 4.2.1 show that though moderate and high tessellation models were used in the proposed optimization method, yet the processing for the grasp quality improvement is achieved in satisfactorily short times. It may be noted that though the time taken for the non-frictional parallelepiped is longer, the quality

123

V. Rakesh et al.

Fig. 14 a The initial frictional FC grasp on a Stanford Bunny. b The GA optimized FC grasp. c Grasp quality increase during the GA progress

Fig. 15 a The initial frictional FC grasp on a duck. b The GA optimized frictional FC grasp. c Grasp quality increase during the GA progress Table 1 Average optimization results over 50 runs Method

Modified GA method

Non-frictional parallelepiped

Non-frictional knight

Frictional knight

1880 triangles

21,357 triangles

21,357 triangles

Final quality

Time (s)

Final quality

Time (s)

Final quality

Time (s)

0.200 in 30 gen. with pop size 400

35.0

0.126 in 20 gen. with pop. size 200

63.8

0.146 in 20 gen. with pop. size 200

368.8

achieved by the proposed optimization method is high. The optimization on the chess knight without friction achieves a high quality of 0.129 in a short time of 38.6 s. The quality and time values are 0.075 and 70.2 s for the existing method by Roa and Suarez (2009) for a similar model represented with 4750 triangles.

123

The average optimization results of the modified GA algorithm over 50 runs are summarized in Table 1, to provide a ready look-up. The particular population (pop.) size and the generation (gen.) have also been mentioned in the table, for the current work using the modified GA algorithm.

Optimizing force closure grasps on 3D objects using a modified genetic algorithm

Table 1 shows the average results over 50 runs. In the case of the frictionless knight, a high quality of 0.126 is generated in 63.8 s. For a similar model, a quality of 0.069 is achieved by the method of Roa and Suarez (2009). By the modified GA method, qualities of a corresponding order like 0.060 and 0.070 are achieved in very short time of 7.2 s and 10.2 s, respectively. From the average results of the modified GA method, for the case of the chess knight with friction, it is seen that a quality of 0.146 is achieved in 368.8 s, with a population size of 200 in 20 generations, with a high tessellation of 21,357 triangles. The similar model by Roa and Suarez (2009) using 4750 triangles resulted in a quality of 0.040. Referring to Fig. 12, it is also seen that, on an average, a short time of 93.5 s is also adequate to achieve a quality of 0.103.

5 Conclusions In the work presented in this paper, the meta-heuristic nature of population-based GA search provides a decent formulation for solving these types of assignment problems. A meager number of calls to the expensive FC test have ensured that the implementation returns high-quality grasps on tessellated objects very quickly in short times. There is a need to plan and check automated grasp synthesis for robots in a virtual environment thereby eliminating costly manufacturing cycles (and re-building). Moreover, the efficacy of the grasp synthesis schema, in terms of computational efforts, also dictate its’ induction for online or offline use. In this context, this work has been prototyped as an effort for a new grasping scheme on a virtual/digital environment as a test bed. The biggest lacuna, as visible in this domain, is the lack of ’one-scheme-fits-all’ kind of planner. Hence, the current work makes a reasonable attempt toward the creation of a generalized planner for complex objects, using modified GA. Acknowledgments The authors gratefully acknowledge the colleagues at IGCAR for their constant encouragement during this study. The authors also thank the editor and anonymous reviewers for their insightful and constructive suggestions and careful review of the paper. Compliance with ethical standards Conflict of interest The authors declare that they have no conflict of interest. Ethical approval This article does not contain any studies with human participants or animals performed by any of the authors.

References Bicchi A (1995) On the closure properties of robotic grasping. Int J Robot Res 14(4):319–334 Borst Ch, Fischer M, Hirzinger G (2003) Grasping the dice by dicing the grasp. In: Proceedings of IEEE/RSJ international conference on intelligent robots and systems

Chella A, Dindo H, Matraxia F, Pirrone R (2007) Real-time visual grasp synthesis using genetic algorithms and neural networks. In: Proceedings of the 10th congress of the Italian association for artificial intelligence on AI*IA 2007: artificial intelligence and humanoriented computing (AI*IA ’07). Springer, Berlin, pp 567–578 Chen I, Burdick J (1993) Finding antipodal point grasps on irregularly shaped objects. IEEE Trans Rob Autom 9(4):507–512 Daoud N, Gazeau J, Zeghloul S, Arsicault M (2011) A fast grasp synthesis method for online manipulation. Rob Auton Syst 59(6):421– 427 Deb K (2009) Optimization for engineering design: algorithms and examples. PHI Learning Pvt. Ltd, New Delhi Ding D, Liu Y, Shen YT, Xiang GL (2000) An efficient algorithm for computing a 3D form-closure grasp. In: Proceedings of IEEE international conference on robotics and automation Ding D, Liu YH, Wang MY (2001) On computing inmobilizing grasps of 3-D curved objects. In: Proceedings of the IEEE international symposium on computational intelligence in robotics and automation, pp 11–16 El-Khoury S, Sahbani A (2010) A new strategy combining empirical and analytical approaches for grasping unknown 3D objects. Rob Auton Syst 58(5):497–507 Fernandez J, Walker I (1998) Biologically inspired robot grasping using genetic programming. In: Proceedings of IEEE international conference on robotics and automation, pp. 3032–3039 Ferrari C, Canny J (1992) Planning optimal grasps. In: Proceedings of the IEEE international conference on robotics and automation, pp 2290–2295 Fischer M, Hirzinger G (1997) Fast planning of precision grasps for 3D objects. In: Proceedings of IEEE/RSJ international conference on intelligent robots and systems Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Huebner K, Ruthotto S, Kragic D (2008) Minimum volume bounding box decomposition for shape approximation in robot grasping. In: Proceedings of the IEEE international conference on robotics and automation, pp 1628–1633 Lakshminarayana K (1978) Mechanics of form closure. ASME Technical Report 78-DET-32 Li JW, Liu H, Cai HG (2003) On computing three-finger force-closure grasps of 2D and 3D objects. IEEE Trans Rob Autom 19(1):155– 161 Lippiello V, Siciliano B, Villani L (2010) Fast multi-fingered grasp synthesis based on object dynamic properties. In: Proceedings of the IEEE/ASME international conference on advanced intelligent mechatronics (AIM), pp 1134–1139 Lippiello V, Siciliano B, Villani L (2013) Multi-fingered grasp synthesis based on the object dynamic properties. Rob Auton Syst 61(6):626–636 Liu YH, Lam ML, Ding D (2004) A complete and efficient algorithm for searching 3-D form closure grasps in the discrete domain. IEEE Trans Rob Autom 20(5):805–816 Mannepalli S, Dutta A, Saxena A (2010) A multi-objective GA based algorithm for 2D form and force closure grasp of prismatic objects. Int J Robot Autom 25(2) Markenscoff X, Ni L, Papadimitriou CH (1990) The geometry of grasping. Int J Rob Res 9(1):61–74 Mason MT (2001) Mechanics of robotic manipulation. MIT Press, Cambridge Miller AT, Knoop S, Allen PK, Christensen HI (2003) Automatic grasp planning using shape primitives. In: Proceedings of IEEE international conference on robotics and automation Mirtich B, Canny J (1994) Easily computable optimum grasps in 2D and 3D. In: Proceedings of IEEE international conference on robotics and automation, pp 739–747

123

V. Rakesh et al. Ngo CY, Li VOK (1998) Fixed channel assignment in cellular radio networks using a modified genetic algorithm. IEEE Trans Veh Technol 47(1):163–172 Nguyen V (1986) The synthesis of stable force-closure grasps. Technical Report 905, MIT Artificial Intelligence Laboratory Nguyen V (1988) Constructing force-closure grasps. Int J Rob Res 7(3):3–16 Niparnan N, Sudsang A (2004) Fast computation of 4-fingered force-closure grasps from surface points. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS), pp 3692–3697 Reulaux F (1963) The kinematics of machinery. Dover, New York Roa MA, Suarez R (2007) Geometrical approach for grasp synthesis on discretized 3D objects. In: Proceedings of the 2007 IEEE/RSJ international conference on intelligent robots and systems

123

Roa MA, Suarez R (2009) Finding locally optimum force-closure grasps. Robot Comput Integr Manuf 25:536–544 Roa MA, Suárez R (2015) Grasp quality measures: review and performance. Auton Robots 38(1):65–88. doi:10.1007/ s10514-014-9402-3 Suárez R, Roa M, Cornella J (2006) Grasp quality measures. Technical Report IOC-DT-P 2006-10, Universitat Politècnica de Catalunya, Institut d’Organització i Control de Sistemes Industrials Zhu X, Wang J (2003) Synthesis of force-closure grasps on 3D objects based on the Q distance. IEEE Trans Rob Autom 19(3):669–679 Zhu X, Ding H (2004) Planning force-closure grasps on 3-D objects. In: Proceedings of IEEE international conference on robotics and automation