Data-driven grasp synthesis using shape matching and task-based pruning

Human grasps, especially whole-hand grasps, are difficult to animate because of the high number of degrees of freedom of the hand and the need for the hand to conform naturally to the object surface. Captured human motion data provides us with a rich source of examples of natural grasps. However, for each new object, we are faced with the problem of selecting the best grasp from the database and adapting it to that object. This paper presents a data-driven approach to grasp synthesis. We begin with a database of captured human grasps. To identify candidate grasps for a new object, we introduce a novel shape matching algorithm that matches hand shape to object shape by identifying collections of features having similar relative placements and surface normals. This step returns many grasp candidates, which are clustered and pruned by choosing the grasp best suited for the intended task. For pruning undesirable grasps, we develop an anatomically-based grasp quality measure specific to the human hand. Examples of grasp synthesis are shown for a variety of objects not present in the original database. This algorithm should be useful both as an animator tool for posing the hand and for automatic grasp synthesis in virtual environments.     

Automated Gripper Jaw Design and Grasp Planning for Sets of 3D Objects

An algorithm for automatically generating a common jaw design and planning grasps for a given set of polyhedral objects is presented. The algorithm is suitable for a parallel‐jaw gripper equipped with three cylindrical fingers. The common jaw design eliminates the need for custom made grippers and tool changing. The proposed jaw configuration and planning approach reduces the search associated with locating the finger contacts from six degrees‐of‐freedom to one degree‐of‐freedom. Closed‐form algorithms for checking force closure and for predicting jamming are developed. Three quality metrics are introduced to improve the quality of the planned grasps. The first is a measure of the sensitivity of the grasp to errors between the actual and planned finger locations. The second is a measure of the efficiency of the grasp in terms of the contact forces. The third is a measure of the dependence of force closure on friction. These quality metrics are not restricted to cylindrical fingers and can be applied to n finger grasps. Running on a standard PC, the algorithm generated a solution in less than five minutes for a set of five objects with a total of 456 triangular facets. © 2003 Wiley Periodicals, Inc.     

Computer simulations of association-based image search mechanisms basing on theory of active perception

We discuss an approach to development of an associative memory model from the viewpoint of the theory of active perception. The theory of active perception allows one to develop the treebased memory model without the defects of the kd-tree and the vp-tree. Applications of the proposed model for solving problems of an image search by content from database are described. Also, we present the results of computer simulations directed at searching of similar and distorted images.     

Static grip selection for robot-based automated assembly systems

In this article we present an algorithmic approach to determine the suitable grasp of an object in an automated assembly environment. The algorithm is based on the available object surfaces and the initial and final task constraints and gripper characteristics. If the imposed task and gripper constraints do not allow a possible grasp, intermediate motions may need to be made to reorient the part. Once a set of possible grasps which statisfy task and gripper constraints are found, the stability of each grasp is analyzed using screw theory. An optimal grasp is one which minimizes the grasping forces over the possible set of grasps. Results utilizing our methodology are presented. Our method can be interfaced with CAD database such as a solid modelling system based on boundary representation for automatic selection of grasping configurations.     

Semantic grasping: planning task-specific stable robotic grasps

We present an example-based planning framework to generate semantic grasps, stable grasps that are functionally suitable for specific object manipulation tasks. We propose to use partial object geometry, tactile contacts, and hand kinematic data as proxies to encode task-related constraints, which we call semantic constraints. We introduce a semantic affordance map, which relates local geometry to a set of predefined semantic grasps that are appropriate to different tasks. Using this map, the pose of a robot hand with respect to the object can be estimated so that the hand is adjusted to achieve the ideal approach direction required by a particular task. A grasp planner is then used to search along this approach direction and generate a set of final grasps which have appropriate stability, tactile contacts, and hand kinematics. We show experiments planning semantic grasps on everyday objects and applying these grasps with a physical robot.     

Efficient models for grasp planning with a multi-fingered hand

This paper presents a simple grasp planning method for a multi-fingered hand. Its purpose is to compute a context-independent and dense set or list of grasps, instead of just a small set of grasps regarded as optimal with respect to a given criterion. By context-independent, we mean that only the robot hand and the object to grasp are considered. The environment and the position of the robot base with respect to the object are considered in a further stage. Such a dense set can be computed offline and then used to let the robot quickly choose a grasp adapted to a specific situation. This can be useful for manipulation planning of pick-and-place tasks. Another application is human–robot interaction when the human and robot have to hand over objects to each other. If human and robot have to work together with a predefined set of objects, grasp lists can be employed to allow a fast interaction.The proposed method uses a dense sampling of the possible hand approaches based on a simple but efficient shape feature. As this leads to many finger inverse kinematics tests, hierarchical data structures are employed to reduce the computation times. The data structures allow a fast determination of the points where the fingers can realize a contact with the object surface. The grasps are ranked according to a grasp quality criterion so that the robot will first parse the list from best to worse quality grasps, until it finds a grasp that is valid for a particular situation.     

Finding locally optimum force-closure grasps

This paper presents an iterative procedure to find locally optimum force-closure grasps on 3D objects, with or without friction and with any number of fingers. The object surface is discretized in a cloud of points, so the approach is applicable to objects with any arbitrary shape. The approach finds an initial force-closure grasp that is then iteratively improved through an oriented search procedure. The grasp quality is measured considering the largest perturbation wrench that the grasp can resist with independence of the direction of perturbation. The efficiency of the algorithm is illustrated through numerical examples.     

Data-driven grasping

This paper propose a novel framework for a data driven grasp planner that indexes partial sensor data into a database of 3D models with known grasps and transfers grasps from those models to novel objects. We show how to construct such a database and also demonstrate multiple methods for matching into it, aligning the matched models with the known sensor data of the object to be grasped, and selecting an appropriate grasp to use. Our approach is experimentally validated in both simulated trials and trials with robots.     

A 3D shape segmentation approach for robot grasping by parts

Neuro-psychological findings have shown that human perception of objects is based on part decomposition. Most objects are made of multiple parts which are likely to be the entities actually involved in grasp affordances. Therefore, automatic object recognition and robot grasping should take advantage from 3D shape segmentation. This paper presents an approach toward planning robot grasps across similar objects by part correspondence. The novelty of the method lies in the topological decomposition of objects that enables high-level semantic grasp planning.In particular, given a 3D model of an object, the representation is initially segmented by computing its Reeb graph. Then, automatic object recognition and part annotation are performed by applying a shape retrieval algorithm. After the recognition phase, queries are accepted for planning grasps on individual parts of the object. Finally, a robot grasp planner is invoked for finding stable grasps on the selected part of the object. Grasps are evaluated according to a widely used quality measure. Experiments performed in a simulated environment on a reasonably large dataset show the potential of topological segmentation to highlight candidate parts suitable for grasping.     

Application of density-based outlier detection to database activity monitoring

To prevent internal data leakage, database activity monitoring uses software agents to analyze protocol traffic over networks and to observe local database activities. However, the large size of data obtained from database activity monitoring has presented a significant barrier to effective monitoring and analysis of database activities. In this paper, we present database activity monitoring by means of a density-based outlier detection method and a commercial database activity monitoring solution. In order to provide efficient computing of outlier detection, we exploited a kd-tree index and an Approximated k-nearest neighbors (ANN) search method. By these means, the outlier computation time could be significantly reduced. The proposed methodology was successfully applied to a very large log dataset collected from the Korea Atomic Energy Research Institute (KAERI). The results showed that the proposed method can effectively detect outliers of database activities in a shorter computation time.     

A human-like real-time grasp synthesis method for humanoid robot hands

This paper addresses a real-time grasp synthesis of multi-fingered robot hands to find grasp configurations which satisfy the force closure condition of arbitrary shaped objects. We propose a fast and efficient grasp synthesis algorithm for planar polygonal objects, which yields the contact locations on a given polygonal object to obtain a force closure grasp by a multi-fingered robot hand. For an optimum grasp and real-time computation, we develop the preference and the hibernation process and assign the physical constraints of a humanoid hand to the motion of each finger. The preferences consist of each sublayer reflecting the primitive preference similar to the conditional behaviors of humans for given objectives and their arrangements are adjusted by the heuristics of human grasping. The proposed method reduces the computational time significantly at the sacrifice of global optimality, and enables grasp posture to be changeable within 2-finger and 3-finger grasp. The performance of the presented algorithm is evaluated via simulation studies to obtain the force-closure grasps of polygonal objects with fingertip grasps. The architecture suggested is verified through experimental implementation to our developed robot hand system by solving 2- or 3-finger grasp synthesis.     

Grasp synthesis for planar and solid objects

This article presents an analysis of the mechanics for multifingered grasps of planar and solid objects. We present a method that is intuitive and computationally efficient. We combine the search for finger grasp positions with finger (manipulation and squeezing) force calculations into a single method. Physically, the squeezing and frictional effects between the fingers and the grasped objects are fully visualized through our approach. Mathematically, we reduced the complexity of finger force calculations when comparing our scheme with previously available schemes. Examples are used to illustrate the effectiveness and efficiency of our scheme. Based upon the analysis of grasp mechanics, an algorithm for quantatively choosing the grasp points is proposed to ensure stable grasps.     

Multi-fingered grasp synthesis based on the object dynamic properties

The grasping and manipulation of objects, especially when they are heavy with respect to the hand power capability, requires the synthesis of grasp configurations that explicitly take into account the dynamic properties of the object. Specifically, suitable grasp configurations reducing gravitational and inertial effects during object manipulation, and minimizing and equally distributing the grasping forces among all the available fingers, must be computed. A new method for fast synthesis of multi-fingered grasp configurations is proposed in this paper. In particular, to reduce the computational complexity, all the regions of the object surface favoring the synthesis of minimal inertia grasps are evaluated first. Then, a reduced number of discrete grasping regions are selected on the basis of the fingertip size, model uncertainty, and surface curvature. Finally, an exhaustive search of the optimal grasp configurations with respect to the grasp quality is performed. Several case studies and comparisons with other methods are proposed to demonstrate the effectiveness of the proposed approach.     

Multisensor controlled robot system for recognizing and tracking moving multiple objects

This paper presents a cost-efficient, real-time vision-sensor system for identifying, locating and tracking objects that are unknown and randomly placed on a moving conveyor belt. The visual information obtained from a conventional frame-store unit and an end-effector based proximity sensor outputs are incorporated in a fuzzy-logic control algorithm to make the robotic manipulator grasp moving objects. The robot movements are going to be the result of the comparative measurements made by the sensors after the motion of the moving target is predicted and the gripper is brought into a zone close to the object to be grasped by the application of a vision system. The mobile object is traced by controlling the motion of the end-effector with an end-effector based infrared proximity sensors and conveyor position encoder by keeping the gripper's axis to pass through a median plane of the moving object. With this procedure and using the fuzzy-logic control, the system is adapted to pursue of a mobile object. Laboratory experiments are presented to demonstrate the performance of this system. ©1999 John Wiley & Sons, Inc.     

Learning of grasp selection based on shape-templates

The ability to grasp unknown objects still remains an unsolved problem in the robotics community. One of the challenges is to choose an appropriate grasp configuration, i.e., the 6D pose of the hand relative to the object and its finger configuration. In this paper, we introduce an algorithm that is based on the assumption that similarly shaped objects can be grasped in a similar way. It is able to synthesize good grasp poses for unknown objects by finding the best matching object shape templates associated with previously demonstrated grasps. The grasp selection algorithm is able to improve over time by using the information of previous grasp attempts to adapt the ranking of the templates to new situations. We tested our approach on two different platforms, the Willow Garage PR2 and the Barrett WAM robot, which have very different hand kinematics. Furthermore, we compared our algorithm with other grasp planners and demonstrated its superior performance. The results presented in this paper show that the algorithm is able to find good grasp configurations for a large set of unknown objects from a relatively small set of demonstrations, and does improve its performance over time.     

A complete and efficient algorithm for searching 3-D form-closure grasps in the discrete domain

A complete and efficient algorithm is proposed for searching form-closure grasps of n hard fingers on the surface of a three-dimensional object represented by discrete points. Both frictional and frictionless cases are considered. This algorithm starts to search a form-closure grasp from a randomly selected grasp using an efficient local search procedure until encountering a local minimum. The local search procedure employs the powerful ray-shooting technique to search in the direction of reducing the distance between the convex hull corresponding to the grasp and the origin of the wrench space. When the distance reaches a local minimum in the local search procedure, the algorithm decomposes the problem into a few subproblems in subsets of the points according to the existence conditions of form-closure grasps. A search tree whose root represents the original problem is employed to perform the searching process. The subproblems are represented as children of the root node and the same procedure is recursively applied to the children. It is proved that the search tree generates O(KlnK/n) nodes in case a from-closure grasp exists, where K is the number of the local minimum points of the distance in the grasp space and n is the number of fingers. Compared to the exhaustive search, this algorithm is more efficient, and, compared to other heuristic algorithms, the proposed algorithm is complete in the discrete domain. The efficiency of this algorithm is demonstrated by numerical examples.     

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Abstract. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation. Received June 9, 1998 / Accepted January 31, 2000     

基于局部指纹曲面片的点云三维物体识别

提出一种新的基于局部描述符的点云物体识别算法。算法根据点云的位置信息提取出邻域以及曲率信息,进而得到形状索引信息。根据形状索引提取到特征点,在每个特征点根据样条拟合原理得到测地距离和矢量夹角分割曲面得到曲面片集。每个曲面片的等距测地线构成了曲面片指纹,通过矢量和半径的变化描述,可以把每个模型物体得到的曲面片集描述存入数据库。对于给定的一个物体,根据上面步骤同样得到其曲面片集描述,通过和数据库中模型物体曲面片集的比对,得到初始识别结果。对每对初始识别结果进行对应滤波后,通过最近点迭代方法得到最终的识别结果。最后通过具体的实验说明了算法的有效性和高效性。     

On the generation of a variety of grasps

In everyday life, people use a large diversity of hand configurations while reaching out to grasp an object. They tend to vary their hands position/orientation around the object and their fingers placement on its surface according to the object properties such as its weight, shape, friction coefficient and the task they need to accomplish. Taking into account these properties, we propose a method for generating such a variety of good grasps that can be used for the accomplishment of many different tasks. Grasp synthesis is formulated as a single constrained optimization problem, generating grasps that are feasible for the hand’s kinematics by minimizing the norm of the joint torque vector of the hand ensuring grasp stability. Given an object and a kinematic hand model, this method can easily be used to build a library of the corresponding object possible grasps. We show that the approach is adapted to different representations of the object surface and different hand kinematic models.     

A New Methodology for Human Grasp Prediction

Grasping is an essential requirement for digital human models (DHMs). It is a complex process and thus a challenging problem for DHMs, involving a skeletal structure with many degrees-of-freedom (DOFs), cognition, and interaction between the human and objects in the environment. Furthermore, grasp planning involves not only finding the shape of the hand and the position and orientation of the wrist but also the posture of the upper body required for producing realistic grasping simulations. In this paper, a new methodology is developed for grasping prediction by combining a shape-matching method and an optimization-based posture prediction technique. We use shape matching to pick a hand shape from a database of stored grasps, then position the hand around the object. The posture prediction algorithm then calculates the optimal posture for the whole upper body necessary to execute the grasp. The proposed algorithm is tested on a variety of objects in a 3-D environment. The results are realistic and suggest that the new method is more suitable for grasp planning than conventional methods. This improved performance is particularly apparent when the nature of the grasped objects is not known a priori , and when a complex high-DOF hand model is necessary.