DEPARTMENT OF COMPUTER SCIENCE
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 npoints. 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 n sided polygons is also given.

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.