DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

Candidate: Marek Teichmann

Advisor: Bud Mishra

DOCTORAL DISSERTATION DEFENSE

Candidate: Marek Teichmann

Advisor: Bud Mishra

**Grasping and Fixturing:
A Geometric Analysis
and an Implementation **

2:00 p.m., Thursday, September 14, 1995

Conference room 1221, 12th floor 719 Broadway

Abstract

The problem of immobilizing an object by placing ``fingers'' (or
points) on its boundary occurs in the field of dexterous manipulation,
manufacturing and geometry. In this dissertation, we consider the
purely static problems of good grasp and fixture set synthesis, and
explore their connection to problems in computational and combinatorial
geometry. Two efficient randomized approximation algorithms are
proposed for finding the smallest cover for a given convex set and for
finding the largest magnitude by which a convex set can be scaled and
still be covered by a cover of a given size. They generalize an
algorithm by Clarkson. The cover points are selected from a set of *n*points. The following bounds are valid for both types of problems. For
the former, *c* is the size of the optimal cover, and for the latter,
*c* is the desired cover size. In both cases, a cover of size `$4 cd \lg c$`

is returned.

The running time depends on the set to be covered. Covering an
*n*-vertex polytope in `$R^d$`

takes `$O(c^2 n \log n \log c)$`

expected
time, and covering a ball takes

$O(nc^{1+\delta}+c^{\lfloor{d/2}\rfloor+1}\log n\log^{\lfloor{d/2}\rfloor} c)$expected time. These algorithms have applications to finding a good grasp or fixture set. An

`$O(n^2 \log n)$`

algorithm for finding optimal 3 finger grasps
for
We also introduce a new grasp efficiency measure based on a certain
class of ellipsoids, invariant under rigid motions of the object
coordinate system. To our knowledge, this is the first measure having
this property. We also introduce a new *reactive* grasping
paradigm which does not require a priori knowledge of the object. This
paradigm leads to several reactive algorithms for finding a grasp for
parallel jaw grippers and three finger robot hands equipped with simple
sensors. We show their correctness and discuss our implementation of
one such algorithm: a parallel jaw gripper with light-beam sensors
which we have built. A short video demonstration will also be shown.