I Introduction
This paper develops algorithms to automatically plan grasping poses for assembly tasks. It focuses on industrial endeffectors, and plans grasp configurations for these endeffectors considering CAD models of target objects.
Developing grasp planning algorithms is important to manufacturing using “teachingless” robotic manipulators. Modern robotic manipulation systems use manually annotated or pretaught grasp configurations to perform certain tasks, which is not only costly but also difficult to redeploy. Automatic grasp synthesis or planning algorithms could bypass the annoying manual work and enable fast redeployment for varying and changing manufacture. For this reason, lots of studies in the field of robotic grasp have been devoted to automatic grasp planning and many grasp planning algorithms have been developed. These algorithms are able to plan grasps considering forces and collisions. However, they hardly meet the requirements of fully automatic manufacturing applications like binpicking and assembly. The requirements include but are not limited to: (1) Large number of candidate grasps: The grasp planner is expected to provide a large number of candidate grasp poses for optimization. (2) Stableness: The grasp planner must have little dependency on the quality of CAD models. (3) Precision: Object poses do not change much after being grasped by the planned grasps.
On the other hand, stateoftheart grasp planning studies concentrate on theoretical aspects like grasp closures and qualities, or applicational aspects like grasping using multifinger hands, dexterous hands, and hands with tactile and force sensors. Grasp planning for popular industrial endeffectors, e.g. parallel grippers and suction cups, is usually ignored since grasping rigid objects using suction cups and parallel grippers is considered to be easy and solved. In this paper, we reinspect this opinion and restudy the grasp planning problem for parallel grippers. After reviewing previous work, we found that although grasp planner for parallel grippers had existed for decades, they do not really meet the requirements of industrial tasks: Some oldfashioned algorithms could plan grasps for simple polytopes, but they cannot tackle complicated mesh models and output satisfying number of grasps; Modern grasp planning algorithms aim to find stable grasps. They cannot find a large amount of grasping poses and don’t consider about their precision. It is difficult to use the planned grasps for industrial tasks like binpicking and assembly, etc.
Under this background, this paper develops new grasp planning algorithms for industrial bin picking and assembly. The problem setting is formulated as follows. The input includes: (1) Kinematic models of industrial endeffectors like suction cups, parallel grippers, and threefingeroneparameter grippers; (2) Watertight models of rigid objects. The output is: A set of automatically planned grasp configurations. The algorithms assume: (1) The objects have rigid bodies. Soft or changeable objects are not considered; (2) The endeffectors and manipulators are actuated using position control to ensure fast operation. Tactile or F/T sensors are not available.
The undergoing core technique of the developed algorithms is superimposed segmentation. The algorithms preprocess a mesh model by peeling it into facets. Each facet is allowed to overlap with others and is thus called superimposed segmentation. The overlap and sizes of segments are controlled by several tunable parameters, which allow users to change the quality of planned grasps following the requirements of their applications. The superimposed segments are used to determine contact and compute parallel facets. Grasp poses for popular industrial endeffectors are planned considering the contact and parallel facets.
The developed algorithms could plan a large number of precise grasps with little dependency on the quality of CAD models. Object positions change less than 2 after being grasped the planned grasps. The computational cost and the stability of the algorithms in the presence of lowquality CAD models, as well as the number of planned grasps and their precision are analyzed in detail in the experimental section using both simulational and realworld experiments. The effect of the tunable parameters is analyzed by comparing the results of varying values. A real dualarm regrasp and assembly system is also implemented to show the efficacy of the proposed algorithms.
The rest of the paper is organized as follows. Section II reviews related work. Section III discusses the fundamental technique like superimposed segmentation and sampling contact points. Section IV presents details of grasp planning algorithms using the fundamental technique. Section V is the experimental section. Section VI draws conclusions.
Ii Related Work
This paper develops modelbased grasp planning algorithms for suction cups and parallel grippers. Accordingly, this section reviews related studies on grasp theories and grasp planning of suction cups and parallel grippers, with a special focus on the preprocessing of mesh models.
Iia Grasp theories and grasp planning
Grasp theories study form/force closure and closure qualities. The theoretical studies are applicable to suction cups, parallel grippers, as well as other robotic hands. Some early work like [1][2] studied point fingers and polygonal objects, with later extensions to more realistic scenarios like curved surfaces and fingers [3][4][5][6][7], considering grasp stability [8][9][10] and grasp metrics [11][12]
. The early theoretical studies were mostly 2D, and the concentration was to estimate the stability of grasps and the resistance to external wrenches. The theoretical studies were extended to 3D polyhedral objects or mesh models composed of flat faces later, assuming to be hard point contacts. Examples include
[13], [14], etc. Some other studies optimized the planned grasps [15] using some quality metrics [16].Planning grasp poses for realworld objects and realworld endeffectors are more challenging than the early theoretical studies. There is a big gap between the computed results and realworld executions. One has to consider many factors like contact regions, object surface curvatures, resistance to torque caused by gravity forces, kinematics of robot hands, etc., to secure stable and exact grasps. Several previous studies challenged these difficulties. For example, Wolter et al. [17] considered the geometry of grippers during the automatic generation of grasps for 3D rectilinear objects. Jones et al. [18] considered the parallel faces of a 3D object as well as the mesh model of a robot gripper to plan two finger grasps for pickandplace operations. Liu et al. [19] used the attractive regions of an object to plan stable grasps. Pozzi et al. [20] discussed grasp qualities considering the kinematic structures of underactuated and compliant hands. Shi et al. [21] considered about environmental constraints as well as the kinematic constraints of robot hands to plan accessible grasps for binpicking and kitting tasks. Li et al. [22] used stretching ropes (cord geometry) to find the contact of a hand jaw with object surfaces and hence plan the grasps. Ciocarlie et al. [23] considered about local geometry and structures at contact points and modeled friction forces using soft models. Harada et al. [24]
discussed about a gripper with soft finger pads attached to the finger tips and analyzed object mesh models considering the depth of contacts. These studies used gripper models and their kinematic structures to ensure feasibility, and considered about contact properties by analyzing the meshes around contact regions.
Our work plans grasp for suction cups and parallel grippers. For these simple endeffectors, the form/force closure theory is converted to comparing surface normals at the contacts. The kinematic constraints, contact, and quality of grasps are considered in segmentation, sampling, and nested collision detection. The quality of the planned grasps depends on the preprocessing of mesh models, which is further reviewed below.
IiB Preprocessing mesh models
Two major approaches to preprocess the mesh models for grasp planning are (1) primitive fitting and (2) surface segmentation. The first approach represents mesh models using a set of shape primitives, and plans grasp by considering the fitting errors or using preannotated grasps. The second approach represents mesh models using coplanar triangle sets. Each coplanar segmented triangle set is named a facet and equals to one constitutional polygon of a polyhedron.
For primitive fittingbased grasp planning, Goldfeder et al. [25] represented a mesh model using recursive splitting and fitting of primitive superquadrics [26]. ElKhoury et al. [27] fitted segmented point clouds using primitive superquadrics and used preannotated training sets to learn grasp points from the fitted models. Xue et al. [28] also used primitive superquadrics to fit models and plan grasps for Schunk Anthromorph Hands. Other than superquadricsbased fitting, Miller et al. [29] represented a mesh model using a set of primitive mesh models like boxes and spheres, and use a set of rules defined on the primitives to generate grasps for the mesh model. Hueber et al. [30] fitted mesh models using different levels of primitive boxes and planned grasp by evaluating the annotated grasps on the primitives. Bonilla et al. [31] also fitted mesh models using primitive boxes, and planned grasps using geometric information extracted from the primitive boxes. Nagata et al. [32] proposed an interactive method for grasp planning by assuming shape primitives. Yamanobe et al. [33] defined the gripping configurations of several shape primitives and used primitive shape representation to planning grasps for mobile manipulators. Curtis et al. [34] used primitives to learn grasps. Instead of explicitly fitting primitives, the authors used learned grasping knowledge on a set of primitive objects to speed up the process of planning successful grasps for novel objects. Harada et al. [35] used cylinders to fit banana point clouds, and planned robust grasps by analyzing the projections of the point clouds on the cylindrical axes denoted by the fitted cylinders. The grasp moduli space proposed by Porkorny et al. [36] is also a primitive fitting approach. The primitive fitting approaches do not assure the stability of planned grasps and exact object poses after grasping. Some further evaluations or optimizations are needed to make the results practical.
For surface segmentationbased grasp planning, Harada et al. [24] clustered triangle meshes by using a parameter denoting softness of contacts and implemented grasp planning for grippers with soft finger pads. Tsuji et al. [37] used multilevel clustering [38] to find the concavity and convexity of mesh models, and used stress distribution models to plan stable grasps. Hang et al. [39] also used multilevel clustering to plan grasps. The difference is their goal was not to find grasping features. Instead, they use different levels of simplification for iterative searching of stable grasps under reachability constraints. In a later work, Hang et al. [40] extended the study to fingertip spaces and used multiresolution contacts to expedite grasp synthesis. The results of the multilevel planning were demonstrated in [41] using an Allegro hand. The hand could gait to different configurations as the weights of objects change. Some of the primitive fitting approaches also have a segmentation step, where meshes or point clouds are segmented for fitting [27][42].
The algorithms developed in this paper use surface segmentation to plan contacts and estimate closure qualities. Unlike previous work which segmented each triangle into a single facet or performed multilevel segmentation, the algorithms allow superimposed segmentation. Each triangle is repeatedly segmented into different facets, and the overlap and thickness of facets are controlled by tunable parameters pertaining to surface normals. By using sampled contact regions on the superimposed segmentations and leveraging torque resistance, one may automatically plan a large number of stable and precise grasp configurations for suction cups and parallel grippers.
Iii Preprocessing Mesh Models
Iiia Superimposed segmentation
Superimposed segmentation provides uniform facets. Conventional approaches [38][43] cluster each triangle into a single facet, resulting in uneven facets – Some of them could be very large, while others are very small. Unlike the conventional approaches, superimposed segmentation allows one triangle to be repeatedly clustered to multiple facets, making all facets uniform (equally large). The clustered facets do not exclusively occupy the triangles that might also belong to other facets.
The superimposed segmentation is computed as follows. First, the algorithm initiates a seed triangle and scans the surrounding triangles of the seed. See the left part of Fig.2 for example. The purple triangle is the seed triangle, and the algorithm scans the triangles surrounding it. If the angle between the normal of the seed triangle and the normal of a nearby triangle is smaller than a threshold , the adjacent triangle is clustered into the same facet as the seed triangle. In the figure, the angles between the black arrows and the purple arrow are equal to or smaller than , the related triangles are clustered into the purple facet. In contrast, the angles between the grey arrows and the purple arrow are larger than , the related triangles are not included. is a tunable parameter which controls the planarity of a facet.
After clustering the first facet, the algorithm initiates a new seed triangle and repeats the clustering by starting from the new seed. The routine to initiate a new seed is as follows. The algorithm scans the surrounding triangles of the previous seeds and checks the angles between the normals of the previous seeds and the normals of the surrounding triangles. If an angle is larger than , the related triangle is selected as the new seed. The right part of Fig.2 shows an example. The angle between the green normal and the purple normal is larger than . Thus, the green the triangle with the green normal is selected as the new seed. The algorithm repeats the clustering process by using new seed and generates a new facet (the green facet shown in the right part of Fig.2). is a tunable parameter which controls the superimposition of facets.
During clustering, all triangles are repeatedly scanned, which allows one triangle to be clustered into multiple facets. The facets could superimpose with each other. On the other hand, the normals of all previous seeds are compared when initiating a new seed, which ensures each facet to be unique and the algorithm to stop properly.
IiiB Sampling contact points
IiiB1 Sampling and distributing
Contact points are computed by sampling the surface of the object mesh model. The sampling is performed over the whole surface to provide evenly distributed contact points on the mesh. After sampling, the sampled points are repeatedly distributed to the superimposed facets as their contact points. Note that we avoided sampling individual facets since it only provides evenly distributed contact points on individual facets, the overall distribution relies on segmenting methods. In cases where facets are small, individual sampling may fail to produce contact points.
Take Fig.3 for example. In the left part, the whole mesh surface is sampled. In the right part, the sampled points are distributed to superimposed facets. The surface is sampled once and the sampled points are distributed to individual facets repeatedly. The method ensures the contact points on each facet have equal density and are evenly distributed. It is irrelevant to the segmentation methods. Also, the method distributes the samples to multiple facets without sampling again. It avoids repeated computation and improves algorithm efficiency.
IiiB2 Removing bad samples
The output of sampling and distributing cannot be used directly, since the distributed samples might be (1) near the boundary of facets and (2) near to each other. In the first case, attaching fingerpads to the sampled points near facet boundaries lead to unstable grasps. In the second case, attaching fingerpads to the near points produces similar grasping configurations, which results in a large number of similar grasps and is wasteful. To avoid the problems, we perform two refining processes where the first one computes the distance between a contact point and the boundary of its facet. The points with distances smaller than will be removed. The second one removes the contact points that are too close to others. The remaining contact points after being refined by the first process are further screened using the Radius Nearest Neighbour (RNN) algorithm to remove nearby points with a distance smaller than . Like and , and are tunable parameters of the grasp planner.
In practice, is determined by the size of finger pads. An endeffector contacts with objects at a region, instead of a single point. specifies the radius of the contact region. It controls the density of planned grasps by removing nearby candidates.
IiiB3 Stability
The SoftFinger Contact (SFC) model proposed in [44] is used to estimate the stability of a grasp. The force and torque exerted by one SFC is expressed as:
(1) 
Here, indicates the tangential force at the contact. indicates the torque at the contact. indicates the load applied in the direction of the contact normal.
is the eccentricity parameter which captures the relationship between maximum frictional force and moment. Under the Winler elastic foundation model,
is(2) 
where is the elastic modules of the foundation over the thickness of the soft finger pad. is the contact surface between the finger pad and the object. is the distance between a differential contact point and the center of the contact region. is the depth of the soft penetration. These symbols are illustrated in Fig.6.
Using to denote the radius of the the contact curvature, can be represented by
(3) 
where is the maximum depth of the soft penetration. Following the definition of curvature, could be computed using , where is the distance between the center of the th in the facet and the center of the seed triangle, is the angle between the normal of the th triangle and the normal of the seed triangle. The computation is illustrated in Fig.6(b). is essentially determined by the geometry of a facet. is used as a tunable parameter to control the stability of planned grasps. Since the goal of stability estimation is to make sure the object is stable at an arbitrary pose (Fig.6(c)), a planned grasp must meet^{1}^{1}1
Here, we are considering the worst case where the gripping torque must resist the largest torque caused by gravity. During manipulation, the largest external torque appears when gravity direction is perpendicular to vector
.(4) 
where is the distance between the (center of mass) of the object and the center of contacts. From (2), (3), and (4) we obtain
(5) 
This equation is used to determine the stability of planned grasps.
Iv Planning the Grasp Configurations
Using the superimposed facets and the sampled contact points, we develop algorithms to plan grasps for suction cups and parallel grippers.
Iva Suction cups
We assume a suction endeffector has only one suction cup. The grasp planning algorithm for a single suction cup is a twostep process. In the first step, the algorithm finds the possible orientations to attach the suction cup to the sampled and refined contact points. Since the approaching direction must be perpendicular to the contact region, the endeffector’s orientation is only changeable by rotating around the approaching direction. The algorithm poses the suction cup to the contact points from the changeable orientations and removes the infeasible (collided) grasps. In the second step, the algorithm examines the resistance of planned suction configurations to external torques caused by gravity. The pseudocode of the algorithm is shown in Fig.7.
For each contact point, the algorithm discretizes the rotation around the contact normal into discreteangles, and computes the rotation matrices. The number of discretized values is determined by . The algorithm poses the eemesh (mesh model of the end effector) using the computed rotation matrices and checks the collision between the eemesh and the objmesh (mesh model of the object). Line 3 of the pseudocode iterates through the discrete orientations. Line 6 poses the eemesh to a with rotation matrix . Line 7 checks the collision between eemesh and objmesh.
In the second step, the algorithm further examines the resistance to external torques. The function (, , ) in line 8 of the pseudocode performs the examination. The function computes the Euclidean distance between and (the of the object), and checks if Eq.(4) is met.
IvB Twofinger parallel grippers
Grasp planning for twofinger parallel grippers is a threestep process. In the first step, the planner for twofinger parallel grippers first finds parallel facets and computes candidate contact pairs by examining the contact points on the parallel facets. Compared with suction cups which need one contact point, the planner for twofinger parallel grippers needs two contact points with opposite contact normals. Thus, the algorithm involves an extra step to prepare the candidate contact pairs. The second and third steps are similar to suction cups. In step two, the algorithm finds the possible orientations to attach the parallel gripper to the candidate contact pairs. In step three, the algorithm examines the stability of the planned grasps.
The pseudocode of the grasp planner for twofinger parallel grippers is shown in Fig.9. In the first block (lines 1 to 8), the algorithm finds candidate contact pairs. For each pair of parallel facets, the algorithm initiates a ray that starts from a contact point on one facet and points to the inverse direction of the contact normal. It detects the intersection between the ray and the other facet. If an intersection exists, the contactintersection pair is saved as a candidate. Whether two facets in a pair are parallel is determined by a tunable parameter (see line 3). In the second block (lines 10 to 22), the algorithm performs collision detection and examines stability. The algorithm invokes two nested functions in the second block. In the first call (line 14), the algorithm checks if the stroke of the gripper collides with the object. Stroke is represented by cylinders which do not have orientation. In the second call (line 20), the algorithm checks if the whole hand (both fingers and palm) collides with the object. The algorithm poses the fingertips to the center of the contact pairs and performs collision at different rotations around the axis formed by the two contacts. During the process, the planner attaches one finger pad to one position of a contact pair, and attaches the other finger pad to the other position of the contact pair. Suppose the two parallel fingers are , , the contact pair is [, ], the algorithm attaches to , attaches to , rotates the gripper around the axis , and checks the collision between eemesh and objmesh at every orientation (lines 15 to 20).
Fig.10 shows the results of grasp planning for a Robotiq85 gripper and an electric drill. The CAD model of the drill is shown in Fig.10(a). The collision between strokes and the model is detected at line 14 of Fig.9. Fig.10(b.13) draw some results of the collision detection. The red cylinders show the strokes that collide with the object and are removed to avoid repeated collision checking at different orientations. The white cylinders are further examined in line 20 of Fig.9 to see if there is a collision between the whole hand and the object. The discretized orientations at one contact pair and the results of wholehand collision detection are illustrated in Fig.10(c). The red hands indicate the collided grasps found by . The white ones are the planned grasps.
IvC Threefinger parallel grippers
In addition, the planner proposed in this paper is applicable to threefinger parallel grippers where two fingers are actuated together against a third finger.
The process is similar to grasp planning for twofinger parallel grippers, except that the two fingers on one side of the parallel gripper are treated as a single finger. Its pseudocode is shown in Fig.11. In the first step, the planner finds parallel facets and computes candidate contact pairs (not shown in Fig.11). In the second step, the planer poses the fingertips to the center of the contact pairs and performs collision detection at different rotations around the axis formed by the two contacts (Fig.11). The algorithm also invokes two nested functions. The first invocation checks the collision of strokes (line 8). The second invocation checks the collision of the whole hand (line 11). However, different from the twofinger case, the stroke of a threefinger gripper is represented by three cylinders, which changes with hand orientation. Thus, both the two invocations are performed under a specific orientation (both are invoked inside the initialized by line 3). If the stroke is collision free, the planner attaches one finger pad to one position of a contact pair and attaches the center of the other two finger pads to the other position of the contact pair (line 9). Suppose the three fingers are , , and where is at one side of a parallel gripper, and are on the other side. The contact pair is named [, ]. The algorithm attaches to , attaches to , and examines the distances between and objmesh, and and objmesh (line 9). The algorithm requires  and  where is a tunable parameter. The parameter controls the contact between the two fingers and the object surface. If the distances meet the requirements, the algorithm checks the collision between the gripper and the object (line 10). In the third step, the algorithm examines the stability (line 12).
Fig.12 shows the results of grasp planning for a threefinger gripper and a tube connector. Some exemplary results of collision detection with strokes are illustrated in Fig.12(b.1b.2). Fig.12(b.1) shows both the collided (red) and collisionfree (white) strokes. The twofinger side is in the front. The strokes are rotated around the axis passing through the contact pair. Fig.12(b.2) is a clear view without the collided ones. The collisionfree strokes are further examined in the second collision detection. Some exemplary results are illustrated in Fig.12(c.1) (a collided grasp configuration) and Fig.12(c.2) (a collisionfree grasp configuration).
V Analysis and Demonstrations
Va Tunable parameters
In the algorithms, seven tunable parameters are prepared for user configuration. The parameters and their functions are shown in Table.I. This section analyzes the parameters and compares the performance of different parameter settings by comparing the different planned results. In practice, users may set the parameters according to the needs of their robotic systems.
Name  Function  Where 

Control the planarity of each facet  Appeared in superimpose segmentation  
Control the overlap of facets  Appeared in superimpose segmentation  
Control the distance between contacts and facet boundaries  Appeared in removing bad samples  
Control the radius of contact regions  Appeared in removing bad samples  
Control the stability of the planned grasps  Appeared in all grasp planners  
Control the parallelity of two facets  Appeared in the planners for two and threefinger grippers  
Control the distances between finger pads and object surfaces  Appeared in the planner for threefinger grippers  
The number of discretized rotation angles around contact normals  Appeared in all grasp planners 
Parameter 1: is used to control the planarity of each facet during the superimposed segmentation. Smaller leads to flatter and smaller facets. Fig.13(a) shows the segmented results of the electric drill shown in Fig.10(a) using different . The facets are drawn with random offsets from their original position to give a clear view. Each facet is given a random color. As becomes smaller, facets become flatter and smaller. In the extreme case where = , each triangle is treated as a facet.
Parameter 2: is used to control the overlap of superimposed segmentation. Smaller leads to more overlap between facets. Fig.13(b) shows the segmented results of the tube connector shown in Fig.12(a) using different . Like Fig.13(a), each facet is drawn with a random offset and a random color. As becomes smaller, facets become more overlapped.
Parameter 3: is used to control the distance between contacts and facet boundaries. Fig.14(a) shows the results of contact sampling using the metal workpiece shown in Fig.8(a) and different . Only samples on the bottom of the object are drawn and the resulting samples are drawn in blue color. A smaller leads to a smaller clearance between contact samples and facet boundaries (hence less robust results).
Parameter 4: is used to control the radius of contact regions or the density of contact sampling. Fig.14(b) shows the sampling results of the metal workpiece using different . The samples are drawn in red. A smaller leads to denser contact samples on the object surface (hence more planned grasps).
Parameter 5: is used to control the stability of the planned grasps. An example is shown in Fig.16(a). The object is the Stanford bunny (the last model in Fig.17). As decreases, the planner reduces to grasp flat facets near the center of mass to maintain stability.
Parameter 6: is used to control the parallelity of the facet pairs in the grasp planning. Values with a larger offset from lead to more candidate “parallel” facet pairs to attach the finger pads and hence more planned grasps. On the other hand, values with larger offsets result in unstable grasping configurations. Fig.15 shows the parallel facets of a toy wheel using different . Arrows indicate facet normals. Two facets with the same arrow color are parallel. Like Fig.13(a), the facets are drawn with random offsets from their original position to give a clear view. As becomes smaller, “parallel” facets become less parallel. Meanwhile, the number of parallel facets becomes larger.
Parameter 7: is used to control the distances between finger pads and object surfaces in the grasp planning for threefinger grippers. Larger values indicate the planner allows a large difference in distances between finger pads and object surfaces. In that case, there will be more planned grasps. Meanwhile, the results are less robust since two fingers cannot touch object surfaces at the same time. Fig.16(b) shows the planned grasps of the tube connector shown in Fig.12(b) using different . As becomes larger, the planned grasp configurations become denser. The object, which is obstructed by hands in the figure, is at the same pose as Fig.12(b). The results also show that when equals 0, there are no lateral grasps. As becomes larger, the number of lateral grasps increase.
Parameter 8: In addition, determines the number of discretized rotation angles around contact normals. A larger leads to denser results, as is shown in Fig.16(c).
VB Performance
VB1 Computational costs
The computational costs of planning grasps for various objects using the method are shown in Fig.17. Six objects are used. From left to right, they are (1) a bearing housing, (2) a toy wheel, (3) an electric drill, (4) a tube connector, (5) a metal workpiece, and (6) a plastic workpiece. The information of these mesh models, including the number of vertices and the number of triangle faces, is shown in an upper section of the table in Fig.17. The details of computational cost, including the time spent on superimposed segmentation, sampling, removing bad samples 1 (refinement 1 of Fig.4), removing bad samples 2 (refinement 2 of Fig.4), planning contact pairs, and the two nested collision detection, are shown in a lower section of the table in Fig.17. The results are obtained by running the algorithms on a LENOVO ThinkPad P70 mobile workstation. One core of an Intel Xeon E31505M v5 @ 2.80GHz 4 Core CPU is used. The memory size is 16.0GB. The algorithms are implemented using python 2.7.11 32 bit. The results are the average values of ten executions using the following parameter settings: =, =, =2, =3, =1.5, =, =3, =8.
The top two timeconsuming rows are marked by red and blue shadows in Fig.4. The first one is , which required a few seconds for a few thousand triangles. The results are reasonable as we are performing meshtomesh collision detections. The second one is “Remove Bad Samples 1” (see Section III.B.2) and Fig.4). The cost is also reasonable since it measures the distances of each sampled contact point to the boundaries of facets.
VB2 Influence of mesh quality
Fig.18 shows the performance of the algorithms using a model with different mesh qualities. The meshes are drawn in Fig.18(18). The number of vertices and triangles of the meshes decreases from 1 to 8. The two charts in the figure show the normalized time cost and the normalized number of planned grasps on these models. Here, the maximum values are normalized as 1, the other values are normalized to values between 0 and 1. The maximum values are used as denominators for normalization. They are listed in the lowerleft corner of the figure. In Chart (a), the different curves show the changes of various cost. The meanings of the colors are also shown in the lowerleft corner. All curves in (a) are the results of the same parameter settings: =, =, =2, =3, =1.5, =, =3, =8. The two curves in Chart (b) show the number of planned grasps. The red curve is the changes of grasp number using the same parameter setting. The blue curve shows the results using a different value (=). The two curves show that the algorithms are stable to lowquality mesh models: The number of planned grasps does not significantly decrease along with reduced vertices and triangles. For =, the number of planned grasps is considered to have similar values in the red shadow (spans from 1 to 4). For =, the number of planned grasps is considered to have similar values in the blue shadow (spans from 1 to 6).
VB3 Precision of the planned grasps
We further measure the precision of the planned grasps using a Robotiq85 twofinger parallel gripper and some objects. The experiment settings are shown in the right part of Fig.19. The objects include (a) the Stanford bunny, and (b) the bearing housing. AR markers are attached to the objects to precisely detect the changes of poses before and after closing the fingers. The grasps with approaching directions that have less than 40 degree angle from the vertical direction, as shown in the left part of Fig.19, are selected as the candidate grasps. They are used to grasp the objects. The difference in object poses (the difference in the AR marker’s and positions, namely and ) before and after closing the fingers are measured as the precision.
The results of the Stanford bunny after grasping are shown in Fig.20. In the left case, was set to , and 6 candidate grasps were found. The maximum change after grasping using these planned grasps was =1.00 and =4.5. When was changed to (the right part of Fig.20), only 1 candidate grasp was found. Its change was =0.25 and =1.00.
The Stanford bunny does not have many graspable parallel pairs. The available data might not be enough to demonstrate the precision of the planned grasps. Thus, we further examined the planned grasps of the bearing housing. The and before and after grasping the bearing housing using the planned grasps are shown in Fig.21. The first two rows of the table are the results using parameter settings: =, =, =2, =3, =1.5, =, =3, =8. The lower two rows are the results using a different . =. When =, there are 44 candidate grasps. Two failures are encountered during the experiments using these planned grasps. The failure cases are marked in red shadows. When =, there are 32 candidate grasps, and all of them can successfully hold the object. The maximum position change after grasping are (=2.19, =1.90), and (=1.95, =1.88) in the two cases respectively. They are marked in red frames. With the results of these two models, we confirm that the planned grasps have satisfying precision and are suitable to be used by assembly routines (e.g. spiral search). Also, we may change the parameters of the algorithms and seek a balance between precision and the number of planned grasps according to the requirements of specific tasks (industrial binpicking or assembly).
For readers’ convenience, we summarize the detailed changes of segmentation and planned grasps of the Stanford bunny with different parameter settings in Fig.22. In (a), and are fixed to , decreases from left to right. The number of planned grasps increases as decreases. In (b), and are fixed to , decreases from left to right. The sizes of facets increase significantly as decreases (The sizes of facets are measured by the average number of triangles). Meanwhile, as the sizes of facets increases, the number of planned grasps increases significantly. In (c), and are fixed to , decreases from left to right. The number of facets decreases slightly as decreases. There are no necessary relations between and the size of facets, and between and the number of planned grasps.
VC Some robotic assembly examples using the grasp planner
The proposed method is implemented as a plugin of an open source project named PYHIRO (available on Github at https://github.com/wanweiwei07/pyhiro), where the goal is to build a system that conducts assembly tasks without human teach. The input to the system is the CAD models of objects and kinematic parameters of robots and hands. The output is a sequence of grasp configurations and robot poses for assembly. The proposed grasp planning is a preprocessing component of the project. It prepares preannotated grasp configurations for regrasp planning and motion planning. This subsection presents some examples of robotic assembly using the systems and the proposed grasp planning algorithms.
The first example is to use a Kawada Nextage robot (Kawada Industries, Inc.) to assemble a wheel to a support shown in Fig.23(a). The hands used were two Robotiq F85 grippers. The input is the initial positions and orientations of the wheel and the support in a robot’s workspace (the initial poses are shown in Fig.23(c)). The system automatically plans grasps, invalidates collided grasp configurations, and plans motion sequences using the collisionfree grasps. The planned collisionfree grasps for assembling the two objects are shown in Fig.23(b). Two exemplary planned sequences are shown in Fig.23(d.1) and (d.2). The realworld execution using one sequence is shown in Fig.23. The planned grasps are precise enough to guarantee successful pickandplace and regrasp.
The second example is to use a dualarm UR3 robot (Universal Robots A/S) to pick up a vacuum fastener and fasten a bolt. The robot plans a bunch of candidate grasps using the proposed algorithms, and chooses a suitable grasp to pick up the vacuum fastener in Fig.24(ac). The planned grasp is precise enough to align the suction tooltip and fasten the bolt in Fig.24(d). Like the first example, the gripper used is the Robotiq F85 gripper.
The third example is to hand over an electric drill from the right hand of an HRP5P robot (BNational Inst. of AIST, Japan, http://y2u.be/ARpd5J5gDMk) to its left hand. The gripper is a threefinger parallel gripper. The robot could precisely hold the object using the planned grasps (Fig.25(ab)), which allows the left hand to insert its thumb into the narrow space between the index and middle fingers of the right hand Fig.25(cd).
Vi Conclusions and Future Work
In this paper, we proposed grasp synthesis algorithms that are efficient, have high precision, and are highly configurable with several tunable parameters. The algorithms focused on industrial endeffectors like grippers and suction cups, and can be used in industrial tasks like binpicking and assembly. The efficiency, precision, and configurability of the proposed method meet the requirements of these tasks. The proposed planner is demonstrated to be practical by a realworld robotic assembly task.
We envision our future research focusing on noncontinuous contacts. In this paper, a finger pad is assumed to be continuously in contact with a flat surface of an object, which makes it difficult to find grasps on noncontinuous surfaces, e.g. grasp the screw threads of a bolt. In the future, we will use surface simplification, reconstruction, and multicontact analysis to plan grasps and challenge the difficulty.
References
 [1] J. K. Salibury, “Kinematic and Force Analysis of Articulated Hands,” in Robot Hands and the Mechanics of Manipulation, pp. 2–167, The MIT Press, 1985.
 [2] B. Mishra, , J. T. Schwartz, and M. Sharir, “On the Existence and Synthesis of Multifinger Positive Grips,” Algorithmica, vol. 2, pp. 541–558, 1987.
 [3] V.D. Nguyen, “Constructing ForceClosure Grasps,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1368–1373, 1986.
 [4] Y. Funahashi, T. Yamada, M. Tate, and Y. Suzuki, “Grasp Stability Analysis Considering the Curvatures at Contact Points,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 3040–3046, 1996.
 [5] E. Rimon and J. W. Burdick, “Mobility of Bodies in Contact – I: A New 2nd Order Mobility Index for MultipleFinger Grasps,” IEEE Transactions on Robotics and Automation, vol. 14, pp. 696–708, 1998.
 [6] YunHui Liu, “Computing nFinger FormClosure Grasps on Polygonal Objects,” The International Journal of Robotics Research, vol. 19, no. 2, pp. 149–158, 2000.
 [7] A. F. van der Stappen, “Immobilization: Analysis, Existance, and Outputsensitive synthesis,” in ComputerAided Design and Manufacturing, pp. 162–187, AMSDIMACS, 2005.
 [8] D. J. Montatna, “The Condition for Contact Grasp Stability,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 412–417, 1991.
 [9] A. Bicchi, “On the Closure Properties of Grasping,” The International Journal of Robotics Research, vol. 14, pp. 319–334, 1995.
 [10] W. S. Howard and V. Kumar, “On the Stability of Grasped Objects,” IEEE Transactions on Robotics and Automation, 1996.
 [11] B. Mishra, “Grasp metrics: Optimality and Complexity,” in Proceedings of Workshop on Algorithmic Foundations of Robotics, pp. 137 –165, 1995.
 [12] M. A. Roa and R. Suárez, “Grasp Quality Measures: Review and Performance,” Journal of Autonomous Robots, vol. 38, pp. 65–88, 2015.
 [13] J. Ponce, S. Sullivan, A. Sudsang, and J. Merlet, “On Computing Fourfinger Equilibrium and Forceclosure grasps of Polyhedral Objects,” IEEE Transactions on Robotics and Automation, vol. 16, pp. 11–35, 1997.
 [14] Y. Liu, M. Lam, and D. Ding, “A Complete and Efficient Algorithm for Searching 3D Form Closure Grasps in the Discrete Domain,” IEEE Transactions on Robotics and Automation, vol. 20, pp. 805–816, 2004.
 [15] M. Fischer and G. Hirzinger, “Fast Planning of Precision Grasps for 3D Objects,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 120– 126, 1997.
 [16] A. Miller and P. Allen, “Examples of 3D Grasp Quality Computations,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1240– 1246, 1997.
 [17] J. D. Wolter, R. A. Volz, and A. C. Woo, “Automatic Generation of Gripping Positions,” IEEE Transactions on System, Man, and Cybernetics, vol. 15, pp. 204–213, 1985.
 [18] J. L. Jones and T. LozanoPerez, “Planning TwoFingered Grasps for PickandPlace Operations on Polyhedra,” in IEEE International Conference on Robotics and Automation, pp. 683–687, 1990.
 [19] C. Liu, H. Qiao, J. Su, and P. Zhang, “VisionBased 3D Grasping of 3D Objects With a Simple 2D Gripper,” IEEE Trans. Systems, Man, and Cybernetics: Systems, vol. 44, no. 5, pp. 605–620, 2014.
 [20] M. Pozzi, M. Malvezzi, and D. Prattichizzo, “On Grasp Quality Measures: Grasp Robustness and Contact Force Distribution in Underactuated and Compliant Robotic Hands,” IEEE Robotics and Automation Letters, vol. 2, no. 1, pp. 329–336, 2017.
 [21] J. Shi and G. S. Koonjul, “RealTime Grasping Planning for Robotic BinPicking and Kitting Applications,” IEEE Transactions on Automation Science and Engineering, vol. 14, no. 2, pp. 809–819, 2017.
 [22] Y. Li, J. P. Saut, J. Pettr , A. Sahbani, and F. Multon, “Fast Grasp Planning Using Cord Geometry,” IEEE Transactions on Robotics, vol. 31, no. 6, pp. 1393–1403, 2015.
 [23] M. Ciocarlie, C. Lackner, and P. Allen, “Soft Finger Model with Adaptive Contact Geometry for Grasping and Manipulation Tasks,” in Proceedings of Joint EuroHaptics Conference and Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, pp. 219–224, 2007.
 [24] K. Harada, T. Tsuji, K. Nagata, N. Yamanobe, K. Maruyama, A. Nakamura, and Y. Kawai, “Grasp Planning for Parallel Grippers with Flexibility on Its Grasping Surface,” in Proceedings of IEEE International Conference on Robotics and Biomimetics, pp. 1540–1546, 2011.
 [25] C. Goldfeder, P. K. Allen, C. Lackner, and R. Pelossof, “Grasp Planning via Decomposition Trees,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 4679–4684, 2007.

[26]
H. Zha, T. Hoshide, and T. Hasegawa, “A ecursive Fittingandsplitting
Algorithm for 3D Object Modeling using Superquadrics,” in
Proceedings of International Conference on Pattern Recognition
, pp. 658–662, 1998.  [27] S. ElKhoury, A. Sahbani, and V. Perdereau, “Learning the Natural Grasping Component,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2957–2962, 2007.
 [28] Z. Xue, A. Kasper, J. M. Zoellner, and R. Dillmann, “An Automatic Grasp Planning System for Service Robots,” in Proceedings of International Conference on Advanced Robotics, pp. 1–6, 2009.
 [29] A. T. Miller, S. Knoop, H. I. Christensen, and P. K. Allen, “Automatic Grasp Planning Using Shape Primitives,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1824–1829, 2003.
 [30] K. Huebner, S. Ruthotto, and D. Kragic, “Minimum Volume Bounding Box Decomposition for Shape Approximation in Robot Grasping,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1628–1633, 2008.
 [31] M. Bonilla, D. Resasco, M. Gabiccini, and A. Bicchi, “Grasp Planning with Soft Hands using Bounding Box Object Decomposition,” in Proceedings of International Conference on Intelligent Robots and Systems, pp. 518–523, 2015.
 [32] K. Nagata, T. Miyasaka, D. N. Nenchev, N. Yamanobe, K. Maruyama, S. Kawabata, and Y. Kawai, “Picking up An Indicated Object in a Complex Environment,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2109–2116, 2010.
 [33] N. Yamanobe and K. Nagata, “Grasp Planning for Everyday Objects Based on Primitive Shape Representation for Parallel Jaw Grippers,” in Proceedings of IEEE International Conference on Robotics and Biomimetics, pp. 1565–1570, 2010.
 [34] N. Curtis and J. Xiao, “Efficient and Effective Grasping of Novel Objects through Learning and Adapting a Knowledge Base,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2252–2257, 2008.
 [35] K. Harada, K. Nagata, T. Tsuji, N. Yamanobe, A. Nakamura, and Y. Kawai, “Probabilistic Approach for Object Bin Picking Approximated by Cylinders,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 3727–3732, 2013.
 [36] F. T. Pokorny, K. Hang, and D. Kragic, “Grasp Moduli Spaces,” in Proceedings of Robotics: Science and Systems, 2013.
 [37] T. Tsuji, S. Uto, K. Harada, R. Kurazume, T. Hasegawa, and K. Morooka, “Grasp Planning for Constricted Parts of Objects Approximated with Quadric Surfaces,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2447–2453, 2014.
 [38] M. Garland, A. Willmott, and P. S. Heckbert, “Hierarchical Face Clustering on Polygonal Surfaces,” in Proceedings of Symposium on Interactive 3D Graphics, pp. 49–58, 2001.

[39]
K. Hang, J. A. Stork, F. T. Pokorny, and D. Kragic, “Combinatorial Optimization for Hierarchical Contactlevel Grasping,” in
Proceedings of IEEE International Conference on Robotics and Automation, pp. 381–388, 2014.  [40] K. Hang, J. A. Stork, and D. Kragic, “Hierarchical Fingertip Space for Multifingered Precision Grasping,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1641–1648, 2014.
 [41] K. Hang, M. Li, J. A. Stork, Y. Bekiroglu, F. T. Pokorny, A. Billard, and D. Kragic, “Hierarchical Fingertip Space: A Unified Framework for Grasp Planning and InHand Grasp Adaptation,” IEEE Transactions on Robotics, vol. 32, no. 4, pp. 960–972, 2016.
 [42] Y. Zhang, A. Koschan, and M. Abidi, “Superquadrics Based 3D Object Representation of Automotive Parts Utilizing Part Decomposition,” in Proceedings of International Conference on Quality Control by Artificial Vision, pp. 241–251, 2003.
 [43] A. D. Kalvin and R. H. Taylor, “Superfaces: Polygonal Mesh Simplification with Bounded Error,” IEEE Computer Graphics and Applications, vol. 16, no. 3, pp. 64–77, 1996.
 [44] K. Harada, T. Tsuji, S. Uto, N. Yamanobe, K. Nagata, and K. Kitagaki, “Stability of softfinger grasp under gravity,” in Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 883–888, 2014.
 [45] W. Wan and K. Harada, “Developing and Comparing Singlearm and Dualarm Regrasp,” IEEE Robotics and Automation Letters, pp. 243–250, 2016.
 [46] W. Wan and K. Harada, “Integrated Assembly and Motion planning using Regrasp Graphs,” Robotics and Biomimetics, vol. 3:18, 2016.
 [47] W. Wan and K. Harada, “Achieving High Success Rate in Dualarm Handover Using Large Number of Candidate Grasps,” Advanced Robotics, pp. 1111–1125, 2016.
 [48] W. Wan and K. Harada, “Regrasp Planning using 10,000 Grasps,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. –, 2017.
Comments
There are no comments yet.