ISSN:
1432-0541
Keywords:
Key words. Multifinger robot hands, Grasping, Closure grasps, Grasp metrics, Fixturing, Polytope covering, Approximate geometric algorithms.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Given an object with n points on its boundary where fingers can be placed, we give algorithms to select a ``strong'' grasp with the least number c of fingers (up to a logarithmic factor) using several measures of goodness. Along similar lines, given an integer c , we find the ``best'' κ c log c finger grasp for a small constant κ . In addition, we generalize existing measures for the case of frictionless assemblies of many objects in contact. We also give an approximation scheme which guarantees a grasp quality close to the overall optimal value where fingers are not restricted to preselected points. These problems translate into a collection of convex set covering problems where we either minimize the cover size or maximize the scaling factor of an inscribed geometric object L . We present an algorithmic framework which handles these problems in a uniform way and give approximation algorithms for specific instances of L including convex polytopes and balls. The framework generalizes an algorithm for polytope covering and approximation by Clarkson [Cla] in two different ways. Let $\gamma = 1/{\lfloor d/2 \rfloor}$ , where d is the dimension of the Euclidean space containing L . For both types of problems, when L is a polytope, we get the same expected time bounds (with a minor improvement), and for a ball, the expected running time is $O(n^{1+\delta} + (nc)^{1/(1+\gamma/(1+\delta))} + c \log(n/c) (c \log c)^{\lfloor d/2 \rfloor} )$ for fixed d , and arbitrary positive δ . We improve this bound if we allow in addition a different kind of approximation for the optimal radius. We also give bounds when d is not a constant.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004539910017
Permalink