Two and Three Finger Caging of Polygons and Polyhedra

Multi-finger caging offers a rigorous and robust approach to robot grasping. This thesis provides several novel algorithms for caging polygons and polyhedra in two and three dimensions. Caging refers to a robotic grasp that does not necessarily immobilize an object, but prevents it from escaping to infinity. The first algorithm considers caging a polygon in two dimensions using two point fingers. The second algorithm extends the first to three dimensions. The third algorithm considers caging a convex polygon in two dimensions using three point fingers, and considers robustness of this cage to variations in the relative positions of the fingers.

This thesis describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on a contact-space formulation. It shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand’s configuration space appear as critical points of the inter-finger distance function in contact space. Second, these critical points can be graphically characterized directly on the object’s boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

A second algorithm is developed for finding caging formations of a 3D polyhedron for two point fingers using a lower dimensional contact-space formulation. Results from the two-dimensional algorithm are extended to three dimension. Critical points of the inter-finger distance function are shown to be identical to the critical points of the cage. A decomposition of contact space into 4D regions having useful properties is demonstrated. A geometric analysis of the critical points of the inter-finger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. With these properties established, the search algorithm from the two-dimensional case may be applied to the three-dimensional problem. An implemented example demonstrates the method.

This thesis also presents a study of cages of convex polygonal objects using three point fingers. It considers a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. It analyzes robustness of caging grasps to variations in the relative position of the fingers without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages.

On the Cesari fixed point method in a Banach space

In a paper published in 1961, L. Cesari [1] introduces a method which extends certain earlier existence theorems of Cesari and Hale ([2] to [6]) for perturbation problems to strictly nonlinear problems. Various authors ([1], [7] to [15]) have now applied this method to nonlinear ordinary and partial differential equations. The basic idea of the method is to use the contraction principle to reduce an infinite-dimensional fixed point problem to a finite-dimensional problem which may be attacked using the methods of fixed point indexes.

The following is my formulation of the Cesari fixed point method:

Let B be a Banach space and let S be a finite-dimensional linear subspace of B. Let P be a projection of B onto S and suppose Г≤B such that pГ is compact and such that for every x in PГ, P^-1x∩Г is closed. Let W be a continuous mapping from Г into B. The Cesari method gives sufficient conditions for the existence of a fixed point of W in Г.

Let I denote the identity mapping in B. Clearly y = Wy for some y in Г if and only if both of the following conditions hold:

(i) Py = PWy.

(ii) y = (P + (I - P)W)y.

Definition. The Cesari fixed paint method applies to (Г, W, P) if and only if the following three conditions are satisfied:

(1) For each x in PГ, P + (I - P)W is a contraction from P^-1x∩Г into itself. Let y(x) be that element (uniqueness follows from the contraction principle) of P^-1x∩Г which satisfies the equation y(x) = Py(x) + (I-P)Wy(x).

(2) The function y just defined is continuous from PГ into B.

(3) There are no fixed points of PWy on the boundary of PГ, so that the (finite- dimensional) fixed point index i(PWy, int PГ) is defined.

Definition. If the Cesari fixed point method applies to (Г, W, P) then define i(Г, W, P) to be the index i(PWy, int PГ).

The three theorems of this thesis can now be easily stated.

Theorem 1 (Cesari). If i(Г, W, P) is defined and i(Г, W, P) ≠0, then there is a fixed point of W in Г.

Theorem 2. Let the Cesari fixed point method apply to both (Г, W, P₁) and (Г, W, P₂). Assume that P₂P₁=P₁P₂=P₁ and assume that either of the following two conditions holds:

(1) For every b in B and every z in the range of P₂, we have that ‖b=P₂b‖ ≤ ‖b-z‖

(2)P₂Г is convex.

Then i(Г, W, P₁) = i(Г, W, P₂).

Theorem 3. If Ω is a bounded open set and W is a compact operator defined on Ω so that the (infinite-dimensional) Leray-Schauder index i_LS(W, Ω) is defined, and if the Cesari fixed point method applies to (Ω, W, P), then i(Ω, W, P) = i_LS(W, Ω).

Theorems 2 and 3 are proved using mainly a homotopy theorem and a reduction theorem for the finite-dimensional and the Leray-Schauder indexes. These and other properties of indexes will be listed before the theorem in which they are used.