A theory on grasping objects using effectors with curved contact surfaces and its application to whole-arm grasping

Abstract

This paper develops a theoretical framework for grasping objects using customized effectors that have curved contact surfaces, and presents its application to the problem of robotic whole-arm grasping. We present a collection of immobilizing grasps and cages that can effectively restrain the mobility of a wide range of object shapes including polyhedra. Each of the grasps or cages is formed by at most three effectors with appropriate contact surfaces in contrast to customary point fingertips. We also discuss the morphology of the curved contact surfaces that can realize the grasps and cages; the surfaces can simply be planar, cylindrical, or spherical. Stable grasps are obtained by simple motion planning and control. Our theory is based on a conservative assumption that all contacts are frictionless, rigid, unilateral. Finally, we present a robotic system, comprised of a software suite and a modular reconfigurable manipulator outfitted with exchangeable end-effectors and arm links, demonstrating the theory and our approach to whole-arm grasping.

Keywords

Robotic grasping robotic caging whole-arm grasping modular robot system

1. Introduction

This paper is concerned with developing a theoretical framework for robotic grasping using effectors (or “fingers”) with curved contact surfaces. Effectors with appropriate curvature properties can be effective for restraining the mobility of objects. For example, between the two grasps shown in Figures 1(a) and (b), each of which has one point and one planar contact, the latter shows a more restrictive grasp where the object cannot actually escape from the effectors due to the concavity of the effector surface contacting the vertex. We also present one application of the idea to a scenario of whole-arm grasping objects, implemented on a modular robot system with exchangeable end-effectors and arm links. Figure 1(c) shows a grasp by the modular manipulator outfitted with two end-effectors that have curved contact surfaces.

Fig. 1.

The tetrahedron is grasped by (a) the two planar effectors, (b) the planar and concave effectors, and (c) the modular manipulator.

It has been customary to employ the abstraction of point fingers in developing theories for robotic grasping and caging (see Section 2); this approach has the advantage of generality, but there are challenges in, for example, designing a physical system providing a sufficient number of independently controlled fingers that can realize the theories. Indeed, most practical solutions in autonomous grasping involve specially designed hardware and control algorithms that are tailored only to a couple of objects to be handled or grasped. A robotic system that can grasp a wide variety of object shapes without many different types of effectors or complex multi-fingered hands can save time and cost in a wide range of scenarios, from handling material in a warehouse to clearing rubble in an unstructured environment. In addition, it is imperative to develop planning algorithms that can guarantee the stability of the process of grasp acquisition and robustness to inevitable sensing/positioning errors; however, the complexity in modeling compliance or friction accurately is one of the challenges that make it hard to develop such algorithms.

We present a novel theory of three types of immobilizing grasps and cages that can effectively restrain the mobility of any object modeled as a polyhedron. The grasps and cages are formed by at most three effectors with curved contact surfaces, which can simply be a planar, cylindrical, or spherical one. The cages allow us to obtain stable grasps by simple motion planning and control in a manner robust to errors and uncertainties. In addition, the theory is extended with more types of grasps and cages. We apply the theory to developing hardware and software for stable, robust object grasping with a modular robot system, which can adapt to the sizes and shapes of a wide variety of objects. Our work is based on a conservative assumption that two bodies in contact can only push each other (unilateral contact) and there is neither friction nor compliance in contact.

This paper is organized as follows. In the following section, we review the relevant literature in the areas of robotic grasping and caging. Section 3 introduces some concepts and terminology necessary to develop our theory and algorithms. Section 4 discusses three types of immobilizing grasps using effectors with curved contact surfaces that can be applied to a wide range of object shapes including polyhedra. Section 5 discusses three types of cages derived from the immobilizing grasps and explains how to establish sufficient conditions for caging. Section 6 presents an algorithm for synthesizing the immobilizing grasps and cages. Section 7 presents one application of our theory to whole-arm grasping with implementation on a modular robot system. We conclude in Section 8, with suggestions for future work. In the Appendix, we extend our theory by adding more types of three- and two-dimensional grasps and cages.

2. Related work

Robotic grasping has been an active research area over the past few decades; see Bicchi and Kumar (2000) for a general survey. Section 2.1 outlines the literature focusing on immobilizing objects with multiple contacts. Section 2.2 introduces prior work on caging objects. Section 2.3 reviews modular robotic approaches to manipulation tasks. This paper builds on our earlier work presented in Seo et al. (2013).

2.1. Prehensile approach

We begin by discussing the closure properties of grasps. A grasp is defined as force closed (Nguyen, 1988) if and only if it can resist any external wrench. If a grasp is force closed with frictionless contacts, it is said to be form closed (Lakshminarayana, 1978) or immobilized (Rimon and Burdick, 1998a). Trinkle (1992) proposed a quantitative test formulated as a linear program for detecting form closure. Markenscoff et al. (1990) showed that it is possible to immobilize a three-dimensional object with seven frictionless point contacts, using first-order theories based on contact normals. Algorithms for synthesizing force or form closed grasps have been presented by Borst et al. (1999), Ponce et al. (1997) and van der Stappen et al. (1999). Rimon and Burdick (1998a, 1998b) developed a second-order mobility theory for rigid bodies in contact where the curvature properties at the contacts are taken into account. Czyzowicz et al. (1991) showed that $n + 1$ frictionless point contacts suffice to immobilize a general n-dimensional polytope by using the effects of relative curvature; thus, for a three-dimensional object, four frictionless point contacts suffice for immobilization.

It has been discovered that the stability of a grasp depends on the geometry of the grasp, contact forces, and material properties. Mason and Salisbury (1985) established a framework for testing the stability of a grasp: a grasp is stable if its stiffness matrix is positive definite. Cutkosky and Kao (1989) showed that grasp stability is a function of local geometry, fingertip models, and the compliance of the fingers. Nguyen (1989) proved that all force-closed grasps can be made stable. Howard and Kumar (1996) established a framework for analyzing grasp stability that takes compliance, contact forces, and the local curvature properties of the bodies in contact into account. It was shown that immobilization implies dynamic stability with elastic contacts (Rimon and Burdick, 1998a; 1998b).

In practice, having a large number of contacts can be beneficial to grasp stability; however, synthesizing such a grasp can be computationally intractable. Pollard (2004) presented an efficient algorithm for synthesizing manycontact grasps based on user-provided examples. Similar approaches can also be seen in the literature on whole-body grasping (Hsiao and Lozano-Perez, 2006) and enveloping grasping (Trinkle et al., 1988). Napier (1956) showed that there are two approaches to achieving stability in human grasping: power grip and precision grip. Whole-body grasps and enveloping grasps are in the same vein as the human power grip, where an object is held by a large number of contacts between the flexed fingers and the palm.

Since Hanafusa et al. (1977) presented one of the earliest examples of robotic hands, various robotic hands have been developed. Our work is relevant to the approach of building simple yet versatile end-effectors that can be seen in Dollar and Howe (2010), Jacobsen et al. (1986), Kragten et al. (2011), Mason et al. (2012) and Ulrich et al. (1988). Another relevant approach can also be seen in the literature on modular fixturing (Brost and Goldberg, 1996; Ponce, 1996). Recently, there has been growing interest in developing robotic systems that can grasp/manipulate objects with some autonomy. Saxena et al. (2008) presented a vision-based approach to robotic grasping and demonstrated real systems that can grasp previously unknown objects using two-dimensional images; similar approaches can be seen in Bowers and Lumia (2003) and Morales et al. (2002). Hudson et al. (2012) developed an autonomy system that can perform dexterous, high-precision tasks such as key insertion.

2.2. Non-prehensile approach

In contrast to the prehensile approach, the literature on caging investigates how to arrange “obstacles” (that is, robotic fingers or effectors) around an object so as to bound its mobility without necessarily making contact. Caging allows us to sidestep some difficult issues such as modeling contacts or optimizing contact forces although the caged object may have some freedom to move. Rimon and Blake (1999) formulated a technique for computing the cages of two-fingered hands; Davidson and Blake (1998a) extended their result to three-fingered hands. Vahedi and van der Stappen (2008a, 2008b, 2008c, 2009) provided an algorithm for synthesizing cages of two and three fingers around polygonal objects and formalized the concepts of squeezing and stretching cages for polygonal objects, which were generalized by Rodriguez and Mason (2009) to address objects in Euclidean spaces of arbitrary dimension. Allen et al. (2012) presented a simpler algorithm for computing two-fingered cages for polygons based on contact space analysis. Wan et al. (2012) proposed a solution to synthesizing three-fingered cages on the plane where two of the fingers are fixed. Fruchard (2012), Maehara (2011) and Zamfirescu (1995) investigated how to cage objects with a single circle. Rodriguez et al. (2012) discussed the relationship between caging and grasping: they investigated when a cage can be a useful waypoint to an equilibrium grasp.

Recently, there have been efforts to take advantage of caging to make robotic grasping tasks robust. Davidson and Blake (1998b) presented error-tolerant, vision-based planar grasping by closing the fingers that form a cage. Gopalakrishnan and Goldberg (2002) presented a simple gripper with two vertical, parallel cylindrical jaws that can stably grasp objects by forming a cage on concavities. Diankov et al. (2008) proposed a motion-planning algorithm for performing manipulation tasks with cages, relaxing task constraints. Yokoi et al. (2009) presented an approach to transporting objects using cages formed by not only robots, but also the environment such as the walls. Cappelleri et al. (2011a, 2011b) employed cages formed by micro-manipulators for transporting and manipulating micro-scale polygonal parts. Dogar and Srinivasa (2011) showed that simple manipulation such as quasi-static pushing can help robots stably cage and grasp objects, even in clutter. There is a body of literature featuring decentralized approaches to caging; we refer the reader to Section 2.3.

2.3. Modular approach to robotic manipulation

The literature on multi-robot manipulation provides techniques for handling objects in a cooperative manner. When multiple robots manipulate a common object, it is necessary to control both the motion of the object and the internal forces exerted on the object (Murray et al., 1994). In addition, the dynamics of such systems are typically subject to unilateral constraints: the robots can only push or pull (for example, by cable tension) the object. Bernard et al. (2011), Cheng et al. (2009), Fink et al. (2011), Murray (1996), Sreenath and Kumar (2013) and Sugar and Kumar (1999) provided solutions to the problem with application to ground or aerial transport. The literature shows that robotic object handling can be facilitated by caging with a team of multiple robots: Fink et al. (2008), Kosuge et al. (1999), Montemayor and Wen (2005) and Pereira et al. (2004) presented approaches to developing decentralized control algorithms. Some of the literature on cooperative transport took inspiration from the behavior of social insect colonies (Berman et al., 2011; Kube and Bonabeau, 2000).

3. Preliminaries: Caging and grasping

This section introduces some concepts and terminology related to the caging and grasping that we use in developing our theory and algorithms.

3.1. Caging

A cage around an object bounds its mobility (Figure 2(a)): the caged object cannot be moved arbitrarily far from its original position without penetrating the surrounding effectors forming the cage. Equivalently, a cage can also be defined in terms of the mobility of the surrounding effectors by regarding the object as an obstacle: according to Rodriguez et al. (2012), a cage is a configuration of effectors that lies in a compact, connected component of the free space (LaValle, 2006) of the system of the effectors (note that the system is assumed to move as a single rigid body).

Fig. 2.

(a) Caging a triangle with three point effectors. (b) Immobilizing the regular triangle with the three point effectors located at the center of each edge. (c) Clamping the tetrahedron with the two planar effectors contacting the vertex–face pair. In (b) and (c) the arrows are involved unit contact wrenches under the assumption of frictionless, rigid, unilateral contact.

Rodriguez et al. (2012) formalized the concept of an F-cage, which is generally stricter than that of a cage. Let F be a scalar function defined on effector configurations. Then an F-cage is a configuration of the effectors that cage an object, even if they have freedom to move while maintaining the value of F. An F-cage is an F-squeezing (stretching) cage if it still cages the object even if the effectors have freedom to move while decreasing (increasing) the value of F.

3.2. Contact

In this work, we are mainly concerned with an object modeled as a polyhedron in contact with effector surfaces. There can then be three types of contact geometry: point, line, and planar contact (Mason, 2001; Mason and Salisbury, 1985). For example, Figure 2(c) shows one point and one planar contact between the two planar effector surfaces and the object. A contact can apply a contact wrench (Mason, 2001; Murray et al., 1994), a contact force/moment pair, given by the positive linear combinations of unit contact wrenches, which are normalized, linearly independent vectors that span the vector space of the contact wrenches (see Figures 2(b) and (c)). Our work is based on an ideal yet conservative assumption that all contacts are frictionless, rigid, unilateral (unilateral contacts can only push an object); then, the unit contact wrenches are the vectors of the normalized screw coordinates only of the inward-pointing contact normals (Mason, 2001). If we assumed more realistic, yet capable (for example, frictional, soft, or bilateral) contacts, more types of unit contact wrenches should be considered (Murray et al., 1994); this shows the conservativeness of our assumption.

A line contact can be made on a virtual edge (Peshkin and Sanderson, 1986), which is composed only of the vertices delimiting the edge without the interior (Figure 3). It can be seen that a “real” edge and a virtual edge are indistinguishable in terms of their ability to produce contact wrenches under the assumption of frictionless, rigid, unilateral contact if we are given a sufficiently large effector surface that can contact all the delimiting vertices: in Figure 3, even if the virtual edge were real (like edge $\bar{QR}$ ), the number of unit contact wrenches would still be the same, that is, two. Similarly, a planar contact can also be made on a virtual face.

Fig. 3.

The plane is contacting the virtual edge $\bar{PQ}$ between the two “real” vertices P and Q. The arrows are involved unit contact wrenches under the assumption of frictionless, rigid, unilateral contact.

3.3. Grasping

To grasp an object is to restrain its mobility by making contacts with effectors. A grasp can be in equilibrium if the net contact wrench, the sum of all contact wrenches, can be made zero in such a way that not all contact wrenches are equal to zero (Rimon and Burdick, 1998a). If there is no object twist, a linear/angular velocity pair (Murray et al., 1994), consistent with the contacts of an equilibrium grasp, the object is said to be immobilized to the first order (Rimon and Burdick, 1998a) (or form-closed (Mason, 2001)), that is, the configuration of the object is an isolated point in the free space. Even if such a twist exists, any finite motion may be restricted by considering surface curvature effects. For example, in Figure 2(b), the object may instantaneously rotate about its centroid (so a first-order kinematic analysis does not predict immobility), but any finite rotation results in penetrating the effectors. This idea is formalized using the concept of second-order immobility presented by Rimon and Burdick (1998a, 1998b); they discovered that second-order immobility suffices for not only complete immobility, which means that the configuration of the grasped object is isolated from the free space, but also local, dynamic, asymptotical stability of the grasped object. Seven (four) point effectors are required to immobilize a polyhedral object to the first (second) order with frictionless, rigid, unilateral contacts (Czyzowicz et al., 1991; Markenscoff et al., 1990). Such immobility conditions are purely geometric; information on contact geometry is thus sufficient to investigate first- or second-order immobility. The immobilizing grasps we will present also exploit surface curvature effects as second-order immobility. An equilibrium grasp is called a grasping cage (Rodriguez et al., 2012) if it can also cage the object; a grasping cage is not necessarily an immobilizing grasp.

3.4. Clamping

Clamping (Bose et al., 1996), also known as parallel-jaw grasping, is one way to realize equilibrium grasps by holding an object between two parallel planar “jaws”. An object that is clamped can only move on the plane of the jaws, without penetrating them. If the jaws can exert frictional forces, the grasp can be force closed: an arbitrary contact wrench can be applied. Consider the antipodal pair of a convex polyhedral object, which is the intersection of the object with a pair of parallel support planes; an antipodal pair can thus be a vertex–vertex, vertex–edge, vertex–face, edge–edge, edge–face, or face–face pair. According to Bose et al. (1996), all convex polyhedra can be clamped with parallel-jaw grippers. The grippers are then on one of the last four types of antipodal pairs, that is, vertex–face, edge–edge, edge–face, or face–face; such an element pair can determine the width of a polyhedron, the minimum distance between two parallel supporting planes. Figure 2(c) shows a clamp on a vertex–face pair.

4. Immobilizing objects using effectors with curved contact surfaces

Here, we discuss how to immobilize a three-dimensional object using at most three contacts, each of which can be a point, line, or planar contact made by an effector with a curved contact surface that can be represented as a two-dimensional manifold with a boundary. In Sections 4.1, 4.2, and 4.3, we present three types of immobilizing grasps that can be applied to objects modeled as polyhedra; we also discuss the geometry of effector surfaces that can realize the grasps. In Section 4.4, we show that any polyhedron can be immobilized by the grasps and discuss how the assumption of polyhedral objects can be relaxed.

4.1. Immobilizing with three point contacts

Here we show that it is possible to immobilize a polyhedron with three point contacts. We begin by choosing three vertices where the contacts can be made. See Figure 4(a). Let P and Q be two vertices of the given polyhedron where two point contacts can be made with a pair of parallel planes perpendicular to $\bar{PQ}$ ; the inward-pointing (toward the interior of the polyhedron) contact normals at P and Q point towards each other. Let R be a vertex, not on $ξ$ (the line of $\bar{PQ}$ ), where a point contact can be made with a plane such that the ray of the inward-pointing contact normal intersects $ξ$ .

Fig. 4.

(a) $(P, Q, R)$ is a vertex–vertex–vertex triple where three point contacts immobilizing the octahedron can be made. (b) The front view of the octahedron with the two curved effectors contacting P and Q. The effector surfaces, except for the points contacting P and Q, can locally be embedded inside the ball shown, whose diameter has end-points P and Q. (c) An immobilizing grasp by the effectors with a spherical surface. (d) An immobilizing grasp by the cone-shaped effectors.

Three point contacts on P, Q, and R made by curved effector surfaces can immobilize the polyhedron if: (1) a neighborhood of the effector surface around the point contacting P (Q), except for the point itself, can be embedded inside the ball whose diameter has end-points P and Q (Figure 4(b)); and (2) a neighborhood of the effector surface around the point contacting R, except for the point itself, can be embedded inside the cylinder of radius $d (R, ξ)$ with axis $ξ$ , where $d (R, ξ)$ denotes the shortest distance between R and $ξ$ . If condition (1) is satisfied, as can be seen in Figure 4(b), the polyhedron cannot move at all except for rotating about $ξ$ because $\bar{PQ}$ is at a configuration that is isolated from the free space: any finite displacement of $\bar{PQ}$ results in penetrating the effectors at P or Q. Furthermore, if condition (2) is satisfied, the polyhedron cannot rotate about $ξ$ because the rotation results in penetrating the effector at R. Two example grasps are shown in Figures 4(c) and (d): effectors with a spherical surface of a sufficiently small radius (Figure 4(c)) or effectors with a cusp (Figure 4(d)) can satisfy the two conditions.

4.2. Immobilizing with a point, a line, and a planar contact

Here we show that it is possible to immobilize a polyhedron with one point, one line, and one planar contact. We begin by choosing a vertex, an edge, and a face where the contacts can be made. See Figure 5(a). At P and □QRST, a point and a planar contact can be made with a pair of parallel planes. The ray of the inward-pointing contact normal at the vertex intersects the interior of the face; the inward-pointing contact normals at the face point toward the vertex. Among the edges incident to P, choose the one with the least slope with respect to the face, that is, $\bar{PS}$ .

Fig. 5.

(a)(P, $\bar{PS}$ , □QRST is a vertex–edge–face triple where a point, a line, and a planar contact immobilizing the pyramid can be made. (b) The front view of the object with the two effectors contacting the vertex and the face. The curved effector surface contacting the vertex, P, can be locally embedded inside the space between the two supporting planes, except for the point contacting P. (c) An immobilizing grasp by the effectors with a spherical, a cylindrical, and a planar surface. (d) An immobilizing grasp where the point (line) contact is made by the cone-shaped (V-shaped) effector.

Three (one point, one line, and one planar) contacts on the vertex (P), edge ( $\bar{PS}$ ), and face (□QRST) by curved effector surfaces can immobilize the polyhedron if: (1) the contact area of the planar contact contains a neighborhood of $P'$ , the foot of the perpendicular line from P to the face (Figure 5(b)); (2) a neighborhood of the effector surface around the point contacting P, except for the point itself, can be embedded inside the half-space below (towards the interior of the polyhedron) the plane contacting P (Figure 5(b)); and (3) a neighborhood of the effector surface around the line segment contacting $\bar{PS}$ , except for the line segment itself, can be embedded inside the cone formed by rotating $\bar{PS}$ about $ξ$ (the line of $\bar{PP'}$ ). If conditions (1) and (2) are satisfied, as can be seen in Figure 5(b), the polyhedron cannot move at all except for rotating about $ξ$ because the two effectors at the vertex and face are not only clamping it but also restricting any translation. Furthermore, if condition (3) is satisfied, the polyhedron cannot rotate about $ξ$ because the rotation results in penetrating the effector at $\bar{PS}$ . Two example grasps are shown in Figures 5(c) and (d).

4.3. Immobilizing with two line contacts

Here we show that it is possible to immobilize a polyhedron with two line contacts. We begin by choosing two edges where the contacts can be made. See Figure 6(a). $\bar{PQ}$ and $\bar{RS}$ are two skew edges of the given polyhedron where two line contacts can be made with a pair of parallel planes that are perpendicular to $ξ$ , the common perpendicular of the edges. $ξ$ and the two edges intersect in the interior of the edges. The inward-pointing contact normals at one edge point towards the other edge.

Fig. 6.

(a) $(\bar{PQ}, \bar{RS})$ is an edge–edge pair where two line contacts immobilizing the tetrahedron can be made. (b) The front view of the object with the two curved effectors contacting the edges. The effector surfaces can be locally embedded inside the space between the two supporting planes (except for the line segments contacting the object). (c) An immobilizing grasp by the effectors with a cylindrical surface. (d) An immobilizing grasp by the two V-shaped effectors.

Two line contacts on the edges by curved effector surfaces can immobilize the polyhedron if a neighborhood of the effector surface around the line segment contacting $\bar{PQ}$ ( $\bar{RS}$ ), except for the line segment itself, can be embedded in the half-space below (above) the plane contacting it (Figure 6(b)). Note that the two contact areas (the line segments) and $ξ$ should intersect. If the condition is satisfied, as can be seen in Figure 6(b), the effectors are not only clamping the polyhedron but also restricting any planar motion: one of the effectors only allows the object to translate along the line of its contact, but such motion is not allowed by the other effector. Two example grasps are shown in Figures 6(c) and (d).

4.4. Analysis

The three types of grasps discussed in Sections 4.1, 4.2, and 4.3 are complete: every polyhedron can be immobilized by applying at least one of the grasps. We break the analysis into two theorems.

First, we show that the grasp of three point contacts discussed in Section 4.1 suffices to immobilize all polyhedra.

Theorem 1. Every polyhedron can be immobilized by three frictionless, rigid, unilateral point contacts made by appropriately curved effector surfaces.

Proof. Every polyhedron has a vertex–vertex pair $(P, Q)$ that admits two parallel supporting planes perpendicular to $\bar{PQ}$ and contacting only P and Q, respectively, in such a way that the interior of the polyhedron is between the planes. Consider the collection of the vertices of the polyhedron. Let $(P, Q)$ be a pair of vertices determining the maximum distance between two vertices of the collection. Consider two planes $Π_{P}$ and $Π_{Q}$ perpendicular to $\bar{PQ}$ and contacting the polyhedron respectively at P and Q. No other vertex of the polyhedron can be located on $Π_{P}$ and $Π_{Q}$ because $(P, Q)$ determines the maximum distance: $Π_{P}$ ( $Π_{Q}$ ) is supporting the polyhedron only at P (Q). Therefore, $(P, Q)$ is a desired vertex pair.

Next, we can find an additional vertex, not on $ξ$ (the line of $\bar{PQ}$ ), which admits a supporting plane whose inward-pointing normal at the vertex directly points to $ξ$ . Consider one vertex that is the most distant from $ξ$ and denote the vertex as R; let $ξ'$ be a line parallel to $ξ$ and passing through R. If R is the only vertex of the polyhedron on $ξ'$ , R must be a pointed vertex that admits a supporting plane whose inward-pointing normal at R directly points towards $ξ$ . R is then the desired vertex. In case there are multiple vertices lying on $ξ'$ , first choose a point on $ξ'$ as its origin, then pick the vertex that is the most distant from the origin, and denote the vertex as R. It can be seen that R is the desired vertex.

Constructively, as explained in Section 4.1, we get immobility with three appropriately curved effector surfaces respectively contacting P, Q, and R. Note that P, Q, and R are on the convex hull of the polyhedron; otherwise, P and Q do not determine the maximum distance and R is not the most distant from $ξ$ , either.

We now show that the other two types of grasps discussed in Sections 4.2 and 4.3 are also complete in the sense that every polyhedron whose vertices are in general position, not admitting any pair of either two planes or a line and a plane that are parallel, can be immobilized by at least one of those grasps.

Theorem 2. Every polyhedron whose vertices are in general position such that there is no pair of either two planes or a line and a plane that are parallel, where each line (plane) is determined by a distinct collection of two (three) vertices, can be immobilized by either (1) one point, one line, and one planar contact or (2) two line contacts made by appropriately curved effector surfaces; the contacts are frictionless, rigid, unilateral.

Proof. Consider the convex hull of the given polyhedron. Because the convex hull does not have any pair of either two faces or an edge and a face that are parallel, it can be clamped at one of its antipodal vertex–face or edge–edge pairs. The convex hull (and thus the original polyhedron) can then be immobilized using the pair by applying the grasp discussed in Sections 4.2 or 4.3.

Note that the grasps employed in Theorem 2 might have contacts on virtual edges or faces that are on the convex hull but are not real elements of the original polyhedron.

In the Appendix, more types of two- and three-dimensional immobilizing grasps are presented, in addition to the collection of the complete grasps.

Remark: In addition to all polyhedral shapes, the three types of grasps can actually be applied to immobilizing a wider range of shapes. Essentially, any given object shape can be immobilized using the grasps if it is possible to make the right set of contacts with effectors having the right curvature properties, as discussed in Sections 4.1, 4.2, and 4.3. For example, even if the vertices P, Q, and R in Figure 4(c) were not actually pointed, it would be possible to immobilize the object with the three point contacts at P, Q, and R in the way discussed in Section 4.1 as long as the actual object geometry around P, Q, and R does not intersect the effector surfaces. Similarly, the place where a line (planar) contact is made does not have to be a perfect polyhedron edge (face) in order for the grasps presented in Sections 4.2 and 4.3 to be applied.

5. Caging objects using effectors with curved contact surfaces

Based on the three types of immobilizing grasps discussed in Section 4, it can be seen that every polyhedron can be caged by two effectors.

Corollary 1. Every polyhedron can be caged by two appropriately curved effector surfaces, each of which is accommodating a single vertex, edge, or face.

Proof. According to Sections 4.1, 4.2, or 4.3, it is possible to cage a polyhedron with two curved effector surfaces making contacts at a vertex–vertex, vertex–face, or edge–edge pair. For example, Figure 7 shows three types of cages obtained by the two effectors at the antipodal pairs in Figures 4(c), 5(c), and 6(c), respectively. According to Theorems 1 and 2, every polyhedron can be caged by at least one of the three types of cages.

Fig. 7.

Cages of two effectors with curved contact surfaces. The inscribed shapes (the right circular cone in (b) and the tetrahedron $P' Q' R' S'$ in (c)) are used to establish sufficient conditions for caging in Section 5.1.

Although the effectors are contacting the objects in Figure 7, a cage does not necessarily have to make contacts with the object. In order to see if an object is caged, it is necessary to take the overall effector geometry into account because it is required to verify the compactness of the component of the free space to which the configuration of the object belongs, which is a non-local property. For example, the distance between effectors is critical in our discussion on caging here. In contrast, recall that we need only local curvature properties in establishing the immobilizing grasps in Section 4.

In this section, we address how to establish sufficient conditions for caging three-dimensional objects in analytical (Section 5.1) and empirical (Section 5.2) manners. In Section 5.3, we present a theoretical analysis on how to acquire stable grasps from the cages and discuss how our assumption of polyhedral objects can be relaxed.

5.1. Analytical method

Here we present three types of cages that are derived from the three types of immobilizing grasps. Considering a simpler object geometry that can be inscribed in the original shape, we discuss how to establish sufficient conditions for caging in an analytical manner.

5.1.1. Caging on a vertex–vertex pair

Consider a vertex–vertex pair of a given polyhedron such as $(P, Q)$ in Figure 7(a), allowing us to establish the immobilizing grasp discussed in Section 4.1. Here we investigate how to cage the two vertices assumed to be rigidly connected (see the line segment $\bar{PQ}$ in Figure 8(a)).

Fig. 8.

(a) The planar view shows vertices P and Q contained in the curved effectors. (b) A cage of two hemispherical effectors.

Consider two curved effectors that can contain the vertices, as shown in Figure 8(a). If the maximum clearance between the effectors is less than $d (P, Q)$ , the distance between P and Q, they can cage the line segment $\bar{PQ}$ . For example, consider a pair of effectors of the same hemisphere that are facing each other and only allowed to relatively translate on their common axis, $η$ (Figure 8(b)). The maximum clearance between the two effectors is then the distance between one point on the boundary of one effector and the foot of the perpendicular line from the point to the other effector, denoted as $c_{m ax}$ in the figure. If $δ$ , the distance between the two planes on which the boundaries of the effectors lie (Figure 8(b)), is small enough to guarantee $c_{m ax} < d (P, Q)$ , $\bar{PQ}$ (and thus the original object) is caged.

5.1.2. Caging on a vertex–face pair

Consider a vertex–face pair of a given polyhedron such as (P, □QRST) in Figure 7(b), allowing us to establish the immobilizing grasp discussed in Section 4.2. Here we investigate how to cage a right circular cone that can be inscribed in the convex hull of the vertex and face (see the right circular cone with apex P in Figure 7(b)).

First, suppose that two infinitely large planar effectors are clamping the right circular cone at the apex and base. We now allow the effectors to move in such a way that they remain parallel to each other (Figure 9(a)). If their distance $δ$ is less than a, the side length of the cone, the cone can stably be clamped again by decreasing $δ$ ; moreover, the distance between the apex and the effector at the base is always larger than h, the height of the cone. It can then be seen that any curved effector surface containing the vertex in such a way that its maximum height is less than a and the boundary lies below h, cages the cone along with the planar effector at the base (Figure 9(b)). For example, consider a hemispherical effector configured such that its boundary is parallel to the planar effector and only allowed to relatively translate along its axis, $η$ (Figure 9(c)). Then the cone (and thus the original object) is caged with the effectors if $δ$ , the distance between the planar effector and the plane of the boundary of the hemispherical effector, is small enough to guarantee: (1) the apex is contained in the hemispherical effector; (2) $δ + r_{e} < a$ ; and (3) $δ < h$ : (2) and (3) guarantee that the apex cannot escape from the hemispherical effector containing it by the analysis above. If the base belongs to a real face of the original object, the planar effector at the base only has to be as large as a disk of radius $r + r_{e}$ , in order to support the base (Figure 9(c)). In case the face is virtual, the planar effector should be at least as large as the face itself.

Fig. 9.

(a) The planar view shows the right circular cone in Figure 7(b) is contained between the two parallel planar effectors. (b) The curved and planar effectors are caging the cone. (c) A cage of the hemispherical and planar effectors. The hemispherical effector is only allowed to translate along its axis $η$ .

5.1.3. Caging on an edge–edge pair

Consider an edge–edge pair of a given a polyhedron such as $(\bar{PQ}, \bar{RS})$ in Figure 7(c), allowing us to immobilize the polyhedron as discussed in Section 4.3. Here we investigate how to cage a tetrahedron that can be inscribed in the convex hull of the two edges (see the tetrahedron $P' Q' R' S'$ in Figure 7(c)).

First, suppose that two infinitely large planar effectors are clamping the tetrahedron $P' Q' R' S'$ . We now allow the effectors to move in such a way that they remain parallel to each other (Figure 10(a)). If their distance $δ$ is less than a, the smallest value among $d (\bar{P' Q'}, R')$ , $d (\bar{P' Q'}, S')$ , $d (\bar{R' S'}, P')$ , and $d (\bar{R' S'}, Q')$ (each term denotes the shortest distance between the edge and the vertex), the tetrahedron can stably be clamped again by decreasing $δ$ . Because of the stability, the heights of $P'$ and $Q'$ from the planar effector at the bottom have a lower bound, $a'$ , which can be found by rotating the tetrahedron about $\bar{R' S'}$ lying on the planar effector. It can then be seen that any curved effector surface containing edge $\bar{P' Q'}$ in such a way that its maximum height is less than a and the boundary lies below $a'$ (Figure 10(b)) cages the tetrahedron along with the planar effector at the bottom. Similarly, the heights of $R'$ and $S'$ are upper bounded; then, the planar effector at the bottom can also be replaced by an effector with a curved surface. For example, consider half-cylindrical effectors configured such that their boundaries are parallel to each other and only allowed to relatively translate along $η$ (Figure 10(c)). Then the tetrahedron (and thus the original object) is caged with the effectors if $δ$ , the distance between the two planes on which the boundaries of the effectors lie, is small enough to guarantee: (1) the edges are contained in the effectors; (2) $δ + r_{1} + r_{2} < a$ ; and (3) $r_{1}$ ( $r_{2}$ ) is large enough to contain the lowest (highest) positions of $P'$ and $Q'$ ( $R'$ and $S'$ ): (2) and (3) guarantee that the edges cannot escape from the effectors containing them by the analysis above. The half-cylindrical effectors should be at least as long as the edges of the original object that they are containing.

Fig. 10.

(a) The planar view shows tetrahedron $P' Q' R' S'$ in Figure 7(c) is contained between the two parallel planar effectors. (b) The planar effector at the bottom and the curved effector are caging the tetrahedron. (c) A cage of the two half-cylindrical effectors. They are only allowed to translate along their common perpendicular, $η$ .

5.2. Empirical method

Sufficient conditions for caging can also be established in an empirical manner by making use of off-the-shelf motion-planning algorithms, particularly when the effector geometry is analytically challenging. We here employed a sampling-based motion planner implementing an RRT-based algorithm, available in ROS;¹ our approach is in the same vein of using sampling-based path planning for (dis)assembly planning (Ferre and Laumond, 2004; Le et al., 2009; Sundaram et al., 2001). In the experiment below, changing the distance between two effectors at intervals of 1 cm, we see if the motion planner can find paths for an object between the two effectors to reach random target configurations sufficiently far from the effectors; for each query distance, denoted by $δ$ below, the effector pair was not considered a cage if it was possible for the object to escape at least once in 10 trials.

First, we consider a scenario where two torus-shaped effectors are caging an object on a vertex–vertex pair. Figure 11(a) shows how we set up experiments with the cone-like object. The effectors are only allowed to translate along $η$ , their common axis of rotation. Let $δ$ denote the distance between the two planes of the two circles, each of which represents the center of each torus tube. When $δ = 0.86$ m (Figure 11(b)), the motion planner failed to find an escaping path for the object in 10 trials (each trial took 0.01–0.06 s on a 2.53 GHz/4 GB machine). Therefore, we can empirically conclude that the object is caged if $δ \leq 0.86$ m.

Fig. 11.

Establishing cages in an empirical manner. (a) and (b) Caging on a vertex–vertex pair. (c) and (d) Caging on a vertex–face pair. (e) and (f) Caging on an edge–edge pair.

Second, we consider a scenario where a torus-shaped and a planar effector are caging an object on a vertex–face pair. Figure 11(c) shows our experimental setup with the cone object: the square-shaped planar effector is contacting the base of the cone; the torus-shaped effector is allowed to translate along $η$ , its axis of rotation collinear to the axis of the cone. When $δ = 0.5$ m (Figure 11(d)), where $δ$ is the distance between the planar effector and the plane on which the circle representing the center of the torus tube lies, the motion planner failed to find an escaping path for the object in 10 trials (each trial took 0.01– 0.04 s on a 2.53 GHz/4 GB machine). Therefore, we can empirically conclude that the object is caged if $δ \leq 0.5$ m.

Third, we consider a scenario where two open-ended, half-cylindrical effectors are caging an object on an edge–edge pair. In the experimental setup shown in Figure 11(e), the effectors are only allowed to translate along $η$ , their common perpendicular. The motion planner could not find an escaping path for the object when $δ = 0.35$ m (Figure 11(f)), where $δ$ is the distance between the two planes on which the boundaries of the effectors lie, in 10 trials (each trial took 0.02–0.04 s on a 2.53 GHz/4 GB machine). Therefore, we can empirically conclude that the object is caged if $δ \leq 0.35$ m.

In the trials above, the sampling-based motion planner did not have to try to take samples on a lower dimensional manifold of the configuration space, which can be hard because such manifolds have measure zero, since our intention was to see how far the two effectors can be separated from each other while still caging the object.

5.3. Analysis

The sufficiency of our caging conditions allows us to address errors/uncertainties in not only fabricating the effectors but also sensing and control relating to grasp acquisition. We now discuss how to get a grasping cage (recall Section 3.3) from any of the cages discussed so far. We also discuss how to relax the assumption of polyhedral objects.

Theorem 3. For the cages discussed in Sections 5.1 and 5.2, a grasping cage is obtained if the two effectors are controlled such that the relative velocity is along $η$ and $δ$ monotonically decreases until contact is established, which is assumed to be frictionless, rigid, unilateral (see Figures 8(b), 9(c), 10(c), and 11 for $η$ and $δ$ ).

Proof. We first show that $δ$ is a grasping function (Rodriguez et al., 2012) for the cages. In each cage, the configuration space of the two effectors can be represented as $M = SE (3) \times SE (3)$ ; $δ$ is a semi-algebraic scalar function $δ : M \to R$ invariant with respect to the rigid transformations of the effectors as a whole, in that it is the distance between the effectors. Furthermore, the pre-images of $δ$ do not cage the object below (above) a certain value m (M) such that $m < M$ , for example, $m = 0$ and $M = h$ in Figure 9(c). Then $δ$ is a grasping function according to Rodriguez et al. (2012).

In addition, the cages are $δ$ - squeezing cages (Section 3.1) in that the object remains caged even if $δ$ decreases. Then, there exists a path in $M$ that leads the effectors into a configuration that can realize a grasping cage. Furthermore, in terms of the one-dimensional set representing the relative configuration space of the two effectors, $δ$ can be considered as a convex, that is, linear, function. Then, by the result of Rodriguez et al. (2012), we get to a grasping cage only by moving the effectors such that $δ$ monotonically decreases.

Rodriguez et al. (2012) discovered that the role of grasping functions in grasping is analogous to that of Lyapunov functions in stability analysis. Specifically, Theorem 3 shows that an object caged by any of our cages can be stabilized by simply moving the effectors closer to each other by relative translation. A translation that monotonically decreases $δ$ in the cages will be referred to as a squeezing motion in the remaining discussion. During a squeezing motion, we may add more contacts to further secure the grasp.

Remark: In addition to all polyhedral shapes, the three types of cages, each of which makes use of a vertex–vertex, a vertex–face, or an edge–edge pair, can actually be applied to a wider range of shapes. Essentially, if a polyhedron model of a given object is geometrically conservative such that the vertices, edges, and faces of the model are inscribed in the actual object geometry, then caging the polyhedron model guarantees that the actual object is also caged. The stability of squeezing motions is also guaranteed by the conservativeness. Note, however, that if the polyhedron approximation is too conservative, the cage might intersect the actual object geometry.

6. Synthesizing grasps and cages

In this section, we present an algorithm for finding element pairs/triples for the immobilizing grasps and cages discussed in the previous sections. Our pseudocode is presented in Algorithm 1. Given the model of an object, the output of the algorithm specifies where to place effectors in order to obtain the immobilizing grasps/cages. The following paragraphs elaborate each line of the algorithm.

Algorithm 1. Finding element pairs/triples for immobilizing/caging.
Input: Object model: a polygonal mesh.
Output: Element pairs and triples labeled with instructions on placing effectors.
1: Compute the convex hull of the mesh.
2: For the convex hull, search for element triples (pairs) for the grasps of Sections 4.1 and 4.2 (Section 4.3).
3: Append instructions on placing effectors to each element pair or triple.

Line 1: We first compute the convex hull of the object model. The convex hull is essentially our object in the algorithm by considering that the vertices, edges, and faces lying on the convex hull suffice to guarantee the completeness of our grasps and cages (see Theorems 1 and 2 and Corollary 1). It takes $O (n \log n)$ expected time to compute the convex hull of a given polyhedron, where n is the number of the vertices (de Berg et al., 2000).

Line 2: We then compute the antipodal pairs of the convex hull that are vertex–vertex (for the grasps of Section 4.1), vertex–face (for the grasps of Section 4.2), and edge–edge pairs (for the grasps of Section 4.3). Given a polyhedron with n vertices, its antipodal pairs can be computed in $O (n^{2})$ time by applying a technique introduced by Brown (1979). Among them, choose the ones that admit supporting planes as illustrated in Figures 4(a), 5(a), and 6(a); it takes $O (1)$ time to see if each pair satisfies the condition. For each vertex–vertex pair, we search for another vertex that is the most distant from the line of the two vertices (see the proof of Theorem 1); as a result, the pair is augmented into a triple of the three vertices in $O (n)$ time. For each vertex–face pair, we search for the edge with the least slope with respect to the face, among the ones incident to the vertex (recall Figure 5(a)); as a result, the pair is augmented into a triple of the vertex, edge, and face in $O (n)$ time.

Line 3: Finally, each element pair or triple from Line 2 is labeled with instructions on how to place effectors. First, the label shows if the constituent elements are real (lying on the original mesh) or virtual (lying only on the convex hull). Second, the label shows the positions and orientations at which effectors should aim. For a vertex–vertex–vertex triple, we specify the coordinates of the vertices and the inward-pointing normals of the three supporting planes. For a vertex–edge–face triple, for example, P, $\bar{PS}$ , and □QRST in Figure 5(a), we specify the coordinates of P, the midpoint of $\bar{PS}$ , and the foot of the perpendicular line from P to □QRST; the inward-pointing normals of the two supporting planes; and the normal vector to $\bar{PS}$ that directly points to $ξ$ . For an edge–edge pair, for example, $\bar{PQ}$ and $\bar{RS}$ in Figure 6(a), we specify the coordinates of the two intersections between $ξ$ and the two edges, along with the inward-pointing normals of the two supporting planes. Figure 12 shows such a label for an edge–edge pair. The labeling can be done in $O (1)$ time for each pair or triple.

Fig. 12.

The label for the edge–edge pair, $(\bar{PQ}, \bar{RS})$ .

Figure 13(a) shows an example object; Figures 13(b), (c), and (d) show some element pairs found by running the algorithm. The convex hull of the rock model has 162 vertices, 480 edges, and 320 faces; it took 0.02 s to find 21 vertex–vertex, 9 vertex–face, and 18 edge–edge pairs with our C++ implementation running on a 2.53 GHz/4 GB machine. The vertex–vertex and vertex–face pairs (Figures 13(b) and (c)) can be augmented into the element triples for immobilizing grasps as explained in Line 2.

Fig. 13.

(a) A polyhedral rock model with 1000 faces (courtesy of Malcolm Lambert, Intresto Pty Ltd). (b), (c), and (d) respectively show a vertex–vertex pair, a vertex–face pair, and an edge–edge pair found by running our algorithm. The reference frames are positioned and oriented such that the origin is at the contact position and the z-axis is along the contact normal, according to the label of each element pair.

A given object model can be immobilized by making contacts with any of the resultant element pairs or triples: we contact target elements with curved effector surfaces, whose curvature is sufficiently large, positioned and oriented as the label specifies. For caging purposes, we do not have to search for the third element in Line 2. Furthermore, effectors do not necessarily have to be controlled to make contacts with their target elements: the target positions for a pair of effectors caging an object can be moved away from the positions specified in the label as long as their distance $δ$ remains less than $δ^{*}$ , the largest acceptable value of $δ$ for the cage to be valid, along the line of the inward-pointing normals. Note, in fact, that the target positions can be moved away even farther because the caging conditions are sufficient.

Because all the elements found by Algorithm 1 (possibly except for the edge of a vertex–edge–face triple) are on the convex hull, that is, the outer frontier of the object, some of them can be virtual. An effector for a virtual edge or face should be large enough to contact all the vertices delimiting the virtual element. If it were not for an effector with a sufficiently large surface for a given virtual element, we would instead need to make contact with a smaller real element in the interior of the convex hull. Then, we may forgo computing the convex hull and proceed with the original mesh although it can take more time and the returned elements may be less easy to access in the case that they are in the interior of the convex hull.

Remark: It can be seen that closedness of input meshes, that is, whether an input mesh is homeomorphic to a closed manifold (compact manifold without boundary) or not, is not a pre-condition for computing antipodal pairs. This implies that Algorithm 1 may be applied to object models that are imperfectly perceived with holes due to, for example, visual occlusion.

7. Whole-arm grasping using end-effectors with curved contact surfaces

In this section, we address how our theory can be applied to a scenario where two collaborating manipulator arms, which may be the arm–torso chain of a humanoid robot or two collaborating industrial robot arms, are grasping objects using end-effectors with curved contact surfaces. The stability of the two-effector cages discussed in Section 5 allows us to add more contacts not necessarily from the end-effectors; the scenario may then be called whole-arm grasping, as can be seen in Figure 14. Whole-arm grasping can be particularly effective for grasping large, bulky objects such as rocks, with relatively small end-effectors. Without fabricating dedicated end-effectors, the curved shapes may be emulated in some way, for example, cupping the fingers of a multi-fingered end-effector. Section 7.1 presents our algorithm for whole-arm grasping. Section 7.2 discusses the implementation of whole-arm grasping on a modular robot system. Section 7.3 presents a set of experiments.

Fig. 14.

Two planar whole-arm grasps by the PR2. The robot is grasping the prismatic objects using the entire arm chain.

7.1. Approach and algorithm

Our approach to whole-arm grasping is composed of two phases: pre-shaping and squeezing. In the pre-shaping phase, a robot cages an object using its two end-effectors with curved contact surfaces as discussed in Section 5. In the squeezing phase, the robot performs a squeezing motion for the end-effectors. During the squeezing motion, not only the end-effectors but also other links can be made to contact the object without adversely affecting the stability of the object if we assume that the robot is position-controlled without compliance, in addition to the assumption of frictionless, rigid, unilateral contact.

Corollary 2. Suppose that the end-effectors of a robot, which is position-controlled without compliance, are caging an object as discussed in Section 5. A grasping cage is obtained if the robot is controlled such that the end-effectors are performing a squeezing motion until contact, which is assumed to be frictionless, rigid, unilateral, is established.

Proof. The same argument as the proof of Theorem 3 can also be applied here by regarding: (1) $M$ as the configuration space of the robot itself; and (2) $δ$ , the distance between the two end-effectors, as the grasping function again.

The corollary shows that as long as the end-effectors are squeezing, the final state is guaranteed to be a stable equilibrium grasp that can be composed of contacts from the whole body of the robot. Our approach can facilitate planning and control for grasping: in the pre-shaping phase, the robot can aim at any of the cages, whose collection is not a set of measure zero in the configuration space; the squeezing phase can be performed in a blind manner, only by position-control, without direct feedback of the object pose. In fact, the two-phase approach has some similarities with multi-fingered grasping (Miller et al., 2003): approaching an object followed by “closing” the hand.

Our pseudocode is presented in Algorithm 2. The algorithm takes as input an initial configuration of the robot $c_{i} \in M_{R}$ , where $M_{R}$ is the configuration space of the robot; it returns a reference trajectory for the robot to follow, $γ (s) : [0, 1] \to M_{R}$ , where s is a non-dimensional parameter increasing with time. The following paragraphs elaborate each line of the algorithm.

Algorithm 2. Motion planning for whole-arm grasping.
Input: Robot’s initial configuration, $c_{i} \in M_{R}$
Output: Reference trajectory for the robot, $γ (s) : [0, 1] \to M_{R}$
1: Construct two configurations: $c_{p} \in M_{R}$ for pre-shaping,
$c_{s} \in M_{R}$ for squeezing.
2: Plan a trajectory $γ_{i p}$ from $c_{i}$ to $c_{p}$ for the pre-shaping.
3: Plan a trajectory $γ_{p s}$ from $c_{p}$ to $c_{s}$ for the squeezing
(possibly in parallel with Line 2).
4: Concatenate $γ_{i p}$ and $γ_{p s}$ into $γ$ , the resultant trajectory from
$c_{i}$ to $c_{s}$ via $c_{p}$ .

Line 1: We first construct $c_{p}, c_{s} \in M_{R}$ that are supposed to describe configurations at which pre-shaping and squeezing should aim, respectively (Figure 15). They can thus be interpreted as desirable waypoints for whole-arm grasping. $c_{p}$ is constructed such that the two end-effectors cage the object in a kinematically feasible manner. $c_{s}$ is constructed such that the robot deliberately intersects the object. These tasks are essentially inverse kinematics problems.

Fig. 15.

The robot is currently in configuration $c_{p}$ , where the curved end-effectors of the arm chain are caging the object. The wireframe shows the configurations of the end-effectors at $c_{s}$ , after the squeezing motion.

Line 2: We plan for a trajectory from $c_{i}$ to $c_{p}$ . During the motion, we do not want the robot to interact with the object; thus any collisions should be avoided. This can be addressed by ordinary path-planning algorithms which are commonly available. Ultimately, some manipulations such as quasi-static pushing (Mason, 2001) may be needed to reach $c_{p}$ .

Line 3: We now plan for a trajectory from $c_{p}$ to $c_{s}$ realizing a squeezing motion. The geometry of the object can be ignored; however, the robot should be treated as a closed kinematic chain in the sense that the two end-effectors are only allowed to approach each other by relative translation. This is generally a hard problem due to the kinematic closure, but can be solved efficiently for planar chains, as will be discussed in Section 7.2.

It is sufficient to control the robot to follow the resultant trajectory in a quasi-static manner, by considering that only the relative configuration of the object and robot matters in caging and squeezing. In fact, the motion of the robot is necessarily interrupted on the way because it is planned to “collide” with the object. Under the assumption of being frictionless, rigid, with unilateral contact, the configuration where the robot, which is position-controlled without compliance, stops moving is an acceptable grasp that can realize a caged, equilibrium grasp by Corollary 2.

Remark: Algorithm 2 can also be applied to grasping with frictional, compliant contact as explained in the following paragraphs.

First, with friction, we can actually have more candidates for an acceptable grasp. When friction is present, the robot might get stuck on the way during a squeezing motion because non-zero friction can cause jamming and wedging (Mason, 2001). However, both phenomena imply force-closure, which in turn implies the involved wrenches are in equilibrium. Thus a jammed or wedged configuration can also be an acceptable grasp. In conclusion, friction helps improve the stability of a grasp, as also discussed by Rimon and Burdick (1998a).

Second, non-rigid objects can also be grasped stably with the algorithm. If we assume a rigid robot moving with a stiff position-control servo loop, a non-rigid object will be deformed during a squeezing motion by contact forces exerted by the robot. Since we take advantage of caging, the object will not be lost during the squeezing motion as long as the caging conditions are satisfied with the deformed geometry. The stability of a non-rigid object under a squeezing motion can be verified by online or offline computation. For online computation, we need to keep track of points of interest (for example, the vertices P and Q in Figure 7(a)) by, for example, visual deformation servoing (Navarro-Alarcon et al., 2014), and verify the corresponding caging conditions. For offline catalog work, we need to consider how to map the deformation of a wide variety of non-rigid objects by, for example, measuring contact forces or joint efforts. A squeezing motion should terminate as soon as the stability of the object is jeopardized.

7.2. Implementing whole-arm grasping

Here we present hardware/software that implements our approach to whole-arm grasping.

7.2.1. Hardware

Our idea of using effectors with curved contact surfaces in robotic grasping can be applied to a wide variety of robotic platforms; here, we employ a modular robot system, which can be a way to maximize adaptability and versatility. According to Sections 4 and 5, we may need a collection of end-effectors with a range of not only shapes but also curvature properties, for practical applications. Thus, a modular robot system with exchangeable end-effectors and attachable/detachable modular arm links allows us to quickly adapt to the sizes and shapes of a wide variety of objects.

Our robot is assembled with CKbot modules² (Davey et al., 2012; Park and Yim, 2009), our chain style modular robot system. Each CKbot module can be used as a one-degree-of-freedom swivel or elbow joint (Figure 16(a)). Figure 16(b) shows three subassemblies: one spine and two (left and right) arms. The spine, composed of two swivel joints and one elbow joint, provides all the three rotational degrees of freedom by realizing z–y–z Euler angles. The arms are planar manipulators composed only of elbow joints assembled such that their axes of rotation are parallel. Although Figure 16(b) shows arms composed of three modules, the modular architecture allows us to assemble more links easily.

Fig. 16.

(a) Two types of CKbot modules providing one rotational degree of freedom. The left one (swivel joint) provides continuous rotation; the right one (elbow joint) is limited to 180° rotation. (b) Two three-degrees-of-freedom planar arms and a three-degrees-of-freedom spine between them. (c) A finished two-armed robot. (d) 3D printed end-effectors that can be docked to the robot.

The two arms are attached to the top of the spine such that the whole arm chain is again a planar open kinematic chain. The torque capacity of the spine essentially prevents adding more arms. Although it may not be straightforward to form the immobilizing grasps of Section 4 featuring up to three contacts with the two-armed configuration that is usually supposed to have two end-effectors, the planar chain actually suffices to realize the immobilizing grasps for the following reason. For each point, line, or planar contact, consider the net wrench that is the combination of all the contact wrenches exerted at the contact. The three (or two) net wrenches in any of our immobilizing grasps should be coplanar (from a planar pencil); otherwise, it is impossible to even guarantee equilibrium, which is necessary for immobility. Thus, three effectors appropriately positioned on the planar arm chain can form the immobilizing grasps. Our cages and squeezing motions discussed in Section 5 can also be realized by the planar architecture because two end-effectors suffice for caging and they are only required to approach to each other. In Figure 16(c), the finished two-armed robot is shown. Figure 16(d) shows 3D printed end-effectors compatible with CKbot; the effector shapes are derived from our theory discussed in Sections 4 and 5.

7.2.2. Software

Our software implementing whole-arm grasping for the hardware platform is organized as ROS³ packages written in C++ and Python. Figure 17 shows the architecture of our software. The move_group node in the center, organized as MoveIt!⁴ packages, works as an integrator between the hardware and a human user. The software provides a user with high-level methods for grasp synthesis (Algorithm 1) and motion planning for pre-shaping and squeezing (Algorithm 2); the robot is then position-controlled to follow the resultant reference trajectory. In the following paragraphs, we further explain how Algorithm 2 is implemented for our robot with the planar arm chain.

Fig. 17.

Software architecture.

First, the inverse kinematics solver for Line 1 of Algorithm 2 is based on the well-studied closed-form solutions of the inverse kinematics of a planar 3R manipulator (planar manipulator with three revolute joints); see Figure 18(a). For an arm with three CKbot modules (exactly a planar 3R manipulator), there can be two solutions commonly known as the “elbow-up” and “elbow-down” configurations. The method can also be applied to solving the inverse kinematics of an arm with n CKbot modules, where $n > 3$ , by converting the complete problem into appropriate subproblems that the solver can address.

Fig. 18.

(a) The planar arm chain is composed of two planar 3R manipulators connected to the base (the longest link). At the configuration $c_{p}$ , the end-effectors are caging the object. $c_{s}$ shows a target configuration which a squeezing motion can aim at. (b) Around each link $\bar{p_{x} p_{y}}$ of the planar 2R manipulator, two level sets of $d (x, \bar{p_{x} p_{y}})$ are shown. Such a level set allows us to model the actual collision hull of a link that may not be a line segment.

Second, the squeezing in Line 3 of Algorithm 2 is based on energy-based motion planning. An algorithm presented by Iben et al. (2009) generates an interpolation sequence without any self-intersections between two simple polygons. In the algorithm, link lengths are allowed to be monotonically changed; this allows us to implement squeezing motions. The resultant motion basically reconfigures the two polygons “towards each other” according to a metric defined between a pair of polygons, for example, the $ℓ^{2}$ -norm on the vector of vertex coordinates. Whenever the direct reconfiguration increases the value of an energy function such as

E = \sum \frac{1}{d {(p_{i}, \bar{p_{j} p_{j + 1}})}^{2}}

(1)

where the denominator can be the squared shortest distance between joint $p_{i}$ and link $\bar{p_{j} p_{j + 1}}$ connecting the joints $p_{j}$ and $p_{j + 1}$ ( $i \neq j, j + 1$ ) (see Figure 18(a) for the notation), we follow the downward gradient of $E$ to avoid collisions. This energy-based planning can be performed efficiently even for a hyper-redundant arm.

7.2.3. Extending Iben et al.’s algorithm

The energy-based motion-planning algorithm explained in the previous paragraph is applicable to line segment links without joint limits, that is, $θ_{i} \in [- π, π]$ where $θ_{i}$ is the angle of joint $p_{i}$ ( $θ_{i} = 0$ when the two incident links are collinear). We further discuss how to adapt the algorithm so as to address joint limits and link shapes that are not line segments.

First, given narrower joint ranges ( $θ_{i} \in [- ℓ_{i}, u_{i}]$ where $0 < ℓ_{i}, u_{i} < π$ for each $θ_{i}$ ), suppose that at a certain instant there are one or more joint angles close to their limit, that is, $θ_{j} \in [- ℓ_{j}, - ℓ_{j} + ε_{1}]$ or $θ_{j} \in [u_{j} - ε_{2}, u_{j}]$ for some $ε_{1}, ε_{2} > 0$ , and j. If the arm chain is described as a concave polygon at that instant, we propose to apply an expansive motion (Connelly et al., 2003) to unfolding all joints such that each $θ_{j}$ can return to the “safe” range, that is, $θ_{j} \in [- ℓ_{j} + ε_{1}, 0]$ or $θ_{j} \in [0, u_{j} - ε_{2}]$ . During an expansive motion for a closed chain, every joint is monotonically unfolded ( $| θ_{i} |$ is decreasing for all i) until the chain is convexified. Such a motion always exists as long as the chain is described as a simple, concave polygon and is computed by convex optimization (Connelly et al., 2003). In case the arm chain is described as a convex polygon at the instant, there also exists such an angle-monotone motion to bring the joint angles back to the safe range (Aichholzer et al., 2001).

Second, in order to avoid collisions among links with non-zero volume, we use ${(d (p_{i}, \bar{p_{j} p_{j + 1}}) - δ_{j})}^{2}$ as the denominator of each term of $E$ where $δ_{j}$ is determined for each link $\bar{p_{j} p_{j + 1}}$ such that the collection of x values on the level set $d (x, \bar{p_{j} p_{j + 1}}) - δ_{j} = 0$ can address the collision hull of the link (Figure 18(b)). With the adaptation, however, two adjacent links overlap each other around the joint connecting them; in practice, this issue can be mitigated by having links move on different planes.

7.3. Experiments

A set of experiments was run to evaluate our hardware/software implementation and its performance on the task of grasping objects. We first see how accurately our robot can position its end-effectors; we then proceed to grasping objects.

7.3.1. End-effector positioning

Positioning end-effectors is critical to successful grasping; thus, we first evaluated the positioning accuracy of our hardware/software implementation. We assembled a robot with two arms; each arm is composed of three link modules as already shown in Figure 16(c). We set up three target configurations for the robot such that: (1) the tips of the right and left arms are level at the same height (Experiment 1); (2) the tip of the right arm is higher than that of the left arm (Experiment 2); and (3) the tip of the right arm is lower than that of the left arm (Experiment 3). For each target configuration, a total of 25 trials was conducted and we measured the actual, final positions of the tip of the right arm using the Vicon motion capture system.⁵ Figure 19 illustrates the results; Table 1 enumerates the data points measured. The average positioning error of the 75 trials was 3.73 cm.

Fig. 19.

The figure illustrates the results of Experiments 1, 2, and 3. In (a), (b), and (c), the simulated robot in the upper panel shows the target configuration for Experiments 3, 1, and 2, respectively; the real robot was controlled to the targets as shown in the lower panels: the △, ◯, and □ symbols represent data points showing the actual, final positions of the tip of the right arm in Experiments 3, 1, and 2, respectively, with respect to the reference frame as shown attached at the tip of the right arm of the simulated robots. In principle, the data points were expected to coincide with the origin of the frame (see the * mark at the top of the graph).

Table 1.

The results of Experiments 1, 2, and 3 are summarized in the first, second, and third columns, respectively. Each entry of the column shows a triple of numbers that represent the x-, y-, and z-directional positioning errors, with respect to the reference frame shown in Figure 19, measured in mm with the number of times it appeared.

x-, y-, z-Error (mm)	Frequency	x-, y-, z-Error (mm)	Frequency	x-, y-, z-Error (mm)	Frequency
(−17, −16, −24)	6	(−19, −32, −20)	19	(−19, −3, −31)	19
(−17, −15, −24)	3	(−19, −32, −21)	2	(−19, −4, −30)	3
(−18, −17, −23)	3	(−19, −31, −19)	1	(−19, −4, −31)	2
(−17, −16, −23)	3	(−19, −32, −19)	1	(−19, −3, −30)	1
(−17, −15, −23)	2	(−19, −31, −20)	1
(−17, −16, −25)	2	(−20, −32, −21)	1
(−18, −16, −23)	2
(−17, −17, −22)	1
(−18, −18, −23)	1
(−17, −17, −23)	1
(−18, −17, −24)	1

In computer simulations, there were no errors in positioning end-effectors; thus, the errors in the real experiments are mostly due to hardware such as tolerance, mechanical play, motor backlash, or compliance. Obviously, the positioning errors are not negligible by considering that each arm is approximately 30 cm long. The arm length of the robot can be compared with the arm length of infants (the mean of the upper arm length of infants aged 3–5 months is 12.8 cm (McDowell et al., 2008)); for comparison, it is known that neonate infants can position their hands within 1.5 cm of objects, which they touch or occasionally grasp (Bower, 1970).

7.3.2. Whole-arm grasping

The positioning experiments suggest the appropriate sizes of end-effectors for successful grasping without position calibration. Figure 20 shows the CAD models of our end-effectors fabricated for grasping experiments. The dimensions of the effectors were determined to address the x- and z-directional positioning errors (recall Figure 19 for the axes and Table 1 for the error data). For example, for the torus-shaped effector in Figure 20(a), the inner radius of the torus was determined to be 46 mm, larger than the maximum positioning error on the xz-plane from Experiments 1, 2, and 3; for the cylindrical effector in Figure 20(b), the inner radius of the cylinder was also determined to be 46 mm for the same reason. The end-effectors are supposed to be squeezed along the y-axis; thus, the y-directional errors can be addressed by our approach that takes advantage of squeezing. Although the end-effectors appearing in Figure 20 look different from the examples in Section 5.1, the end-effectors are sufficient to grasp objects based on Theorem 3 and Corollary 2 in that their geometry is more conservative than the examples. For example, the torus-shaped end-effector in Figure 20(a) can be regarded as the boundary of the hemispherical effector in Section 5.1; moreover, the torus-shaped effector was empirically analyzed in Section 5.2.

Fig. 20.

(a) A torus-shaped end-effector. (b) A cylindrical end-effector; in the model, material usage was minimized to reduce weight and cost. The units are in mm.

We ran three sets of experiments to evaluate the capability of our system: grasping an object using its vertex–vertex pair (Experiment 4), vertex–face pair (Experiment 5), and edge–edge pair (Experiment 6). In each set of experiment, a total of 25 trials was conducted and we verified if the robot could grasp an object, perceived by the Vicon system, via pre-shaping and squeezing without any position calibration. The results are summarized in Table 2.

Table 2.

The results of Experiments 4, 5, and 6.

Grasp type	Successes/trials
Experiment 4: vertex–vertex grasping	22/25
Experiment 5: vertex–face grasping	23/25
Experiment 6: edge–edge grasping	25/25

The snapshots in Figure 21 show the robot grasping objects via pre-shaping and squeezing, demonstrating Theorem 3 by showing that caged, equilibrium grasps can be obtained from our cages, and verifying the soundness of our approach to whole-arm grasping (Corollary 2). The robot was controlled until joint torque saturation occurred during the squeezing. The final grasps shown in the rightmost panels of Figure 21 were obtained from cages on a vertex–vertex, a vertex–face, and an edge–edge pair discussed in Section 5. According to Corollary 1, the way the robot is grasping the box in Figure 21(a) can be applied to any polyhedral shape; almost all polyhedral shapes can be grasped in exactly the same way as grasping the tetrahedral object in either Figures 21(b) or (c). In the failed trials, the two arms were moving in an asynchronized manner (possibly due to an unexpected communication error) or the end-effectors were dynamically interacting with the object (or the support under the object).

Fig. 21.

(a) The robot is grasping the box with the two torus-shaped end-effectors that can cage and grasp the vertex–vertex pair. (b) The robot is grasping the tetrahedral object also with the two torus-shaped end-effectors that can cage and grasp the vertex–face pair; one of the torus-shaped effectors was used to contact the face. (c) The robot is grasping the tetrahedral object with the two cylindrical end-effectors that can cage and grasp the edge–edge pair.

Finally, Table 3 shows the average time frame to perform pre-shaping and squeezing, for 25 trials. In the table, the planning times show how long it takes to run the respective software components (pre-shape() or squeeze(), recall Figure 17) on a 2.53 GHz/4 GB machine. The executing times show how long it takes for the robot to execute the computed plans. It can be seen that if pre-shaping and squeezing are planned in a parallel manner, as mentioned in Algorithm 2, they may be executed in a seamless manner without interruption because the time to pre-shape can be compared with the time to plan for squeezing. The methods pre-shape() and squeeze() were implemented in Python.

Table 3.

The time frame to perform the two phases of whole-arm grasping.

Pre-shaping				Squeezing
Planning time (s)		Executing time (s)		Planning time (s)
min	max	min	max	min	max
0.21	0.41	4.7	6.4	1.72	6.41

8. Conclusion

We have presented three types of immobilizing grasps and cages and shown that they can be applied to a wide range of object shapes including polyhedra. Each of the grasps or cages is formed by at most three effectors with appropriately curved contact surfaces. The immobilizing grasps depend on the local curvature properties of the effectors, whereas the cages are formulated by global parameters, such as the distance between the effectors. A stable grasp can be obtained from any of our cages by a squeezing motion; it also allows us to get a whole-arm grasp. In the Appendix that follows, the collection of the complete grasps and cages is extended to include more types of grasps and cages for two- or three-dimensional objects. Our theory was implemented on a modular robotic platform that can enhance the versatility and adaptability needed in robotic grasping, compared to a customary manipulator with a fixed configuration. Not only pick-and-place tasks, but also a variety of post-grasp manipulation tasks can potentially be facilitated by the secure grasps using the effectors with curved contact surfaces.

Our future research directions include extending the theory, enhancing autonomy, and finding more applications. First, our theoretical framework can be extended in a number of directions. In order to guarantee performance under frictional, compliant contact, the effects of friction and compliance should be treated in a more quantitative manner. Approaches may include incorporating accurate and tractable models of finger–object contact, contact friction, and the compliance of the robot joints and links. Second, there are many great benefits to enhanced autonomy. For example, autonomous robotic systems can eliminate human errors and work safely in dangerous environments such as outer space or the ocean floor. Our objectives for enhancing autonomy include incorporating more sensing capabilities; for example, visual sensing will be beneficial to not only perceiving objects to grasp but also guaranteeing the safety of squeezing motions. The level of autonomy can also be greatly increased by enabling proper interaction with the environment, which will facilitate grasping an object in clutter. Another interesting direction is to develop hardware and software supporting efficient self-reconfiguration: such a system can adapt itself to grasp an arbitrary object by autonomously exchanging end-effectors or attaching more arm links. Third, effectors with curved contact surfaces can be used as not only “hands” but also “feet” for walking or running. RHex (Johnson and Koditschek, 2013; Saranli et al., 2001) showed the versatility of single-bodied legs without any internal degrees of freedom; leg stiffness will be an important factor as discussed by Galloway et al. (2011). Our approach can also be useful in manufacturing, eliminating the need of redesigning fixtures according to objects.

Footnotes

Appendix: Extending our theory

Here we discuss how to extend the collection of the grasps/cages presented in Sections 4 and 5: more types of grasps/cages can be added by employing other types of antipodal pairs. We also discuss grasping and caging two-dimensional objects with curved effectors on the plane.

We first show that it is possible to immobilize a polyhedron with one point and one line contact made by curved effector surfaces, which are frictionless, rigid, unilateral. See Figure 22(a). O and $\bar{AB}$ are a vertex–edge pair of the given polyhedron where a point and a line contact can be made with a pair of parallel planes that are perpendicular to $ξ$ , the line connecting the vertex and its foot of the perpendicular line to the edge (the foot of the perpendicular line is in the interior of the edge). The inward-pointing contact normal at the vertex points towards the edge and vice versa. With respect to the reference frame whose origin is O, the three unit contact wrenches (the arrows in Figure 22(a)) are:

(s_{1}, s_{01}) = (0, - 1, 0, 0, 0, 0)

(s_{2}, s_{02}) = (0, 1, 0, 0, 0, b)

(s_{3}, s_{03}) = (0, 1, 0, 0, 0, - a)

For a differential twist $(t, t_{0}) = (t_{1}, t_{2}, t_{3}, t_{4}, t_{5}, t_{6})$ to be consistent with the unit contact wrenches, each of the reciprocal products of the twist and the unit contact wrenches must be zero:

- t_{5} = 0

t_{5} + b t_{3} = 0

t_{5} - a t_{3} = 0

Then, the solutions are of the form:

(t, t_{0}) = (t_{1}, t_{2}, 0, t_{4}, 0, t_{6})

because $t_{3}$ and $t_{5}$ must be zero. If O is being contacted by the apex of a cone-shaped effector, as can be seen in Figure 22(a), the velocity of O cannot have non-zero x- and z-components with respect to the reference frame; otherwise, O will penetrate the effector. In other words, $t_{4}$ and $t_{6}$ can also be made zero; then, the solutions must actually be of the form:

(t, t_{0}) = (t_{1}, t_{2}, 0, 0, 0, 0)

This is a zero-pitch screw (pure rotation) where the first three components give the direction of the rotation axis, which should pass through O. This rotation instantaneously moves $\bar{AB}$ in a direction perpendicular to the plane of O, A, and B, but can be restricted by contacting $\bar{AB}$ with a V-shaped effector, as can be seen in Figure 22(a). The polyhedron is then immobilized with the point and line contacts on the vertex–edge pair; at the same time, the two effectors are also forming a cage, with their distance along $ξ$ as a grasping function similarly to the previous two-effector cages.

We additionally show that it is possible to immobilize a polyhedron with one planar and two point contacts made by curved effector surfaces, which are frictionless, rigid, unilateral. See Figure 22(b). Consider an edge–face pair that determines the width of the convex hull of the given polyhedron, denoted as $\bar{AB}$ and □QRST. At each vertex of the edge, consider a set of unit contact wrenches, each of which is perpendicular to one of the faces containing the vertex and points towards the interior of the polyhedron; then each of A and B has three such unit contact wrenches because there are three faces meeting at each vertex. Also consider a set of unit contact wrenches at the face, each of which is perpendicular to the face towards the interior at one vertex delimiting the face; then □QRST has four such unit contact wrenches at Q, R, S, and T. The grasp of one planar and two point contacts shown in Figure 22(b) can always be made in equilibrium, by considering that the edge–face pair even admits a clamp. To be more specific, consider the following linear feasibility program

(2)

Find {c_{i}} such that \sum c_{i} \hat{w_{i}} = 0, c_{i} > 0, and \sum c_{i} = 1

where ${\hat{w_{i}}}$ is the collection of all the unit contact wrenches. The grasp can be made in equilibrium by configuring the effectors according to a solution to the program: the terms of $\sum c_{i} \hat{w_{i}}$ can be divided into three groups affiliated with the two vertices and face; each effector should be configured to exert the sum of one group of the wrenches, which is the positive linear combination of the unit contact wrenches at the element the effector is contacting. For example, in Figure 22(b), the two hemispherical effectors are configured such that their axes of symmetry, $ξ_{1}$ and $ξ_{2}$ , pass through A and B, the points of contact, and intersect at O, whose foot on the line perpendicular to the plane of □QRST lies on the area of the planar contact. Under the equilibrium, the object can only move on the plane of the planar contact. If the two curved effectors on the two vertices are sufficiently concave, the object can in fact be immobilized because any finite motion of $\bar{AB}$ results in penetrating the effectors. This idea can also be applied to immobilizing a polyhedral object on a face–face antipodal pair (Figure 22(c)).

The objects in Figures 22(b) and (c) are also caged by the three effectors. One approach to establishing a grasping function here is to assume a control strategy that moves the three effectors as a three-fingered gripper system with one parameter that controls the opening of the gripper, as also discussed by Davidson and Blake (1998a) for three point fingers. Let $δ$ denote the opening parameter of the gripper: as $δ$ increases, the three effectors shown in Figures 22(b) and (c) monotonically move away from O by translation along the axes ( $ξ_{1}$ , $ξ_{2}$ , and $ξ_{3}$ ). In each of the grasps shown in Figures 22(b) and (c), all the instantaneous motions of the object penetrate the effectors, which in turn guarantees that the configuration of the object is completely isolated from its free space (Rimon and Burdick, 1998a). Then it can be seen that the opening parameter $δ$ is a grasping function, similar to Theorem 3. Constructing caging conditions for three effectors may be harder than two-effector cages; for point effectors, refer to Davidson and Blake (1998a).

Two-dimensional grasping: Our approach can also be applied to grasping two-dimensional objects with effectors that can be represented as one-dimensional manifolds with a boundary on the plane. Every polygonal object can be immobilized on the plane by two such curved effectors of appropriately chosen dimensions. In Figure 23(a), the two curved effectors are immobilizing the object by two point contacts; in Figure 23(b), the object is immobilized by a point and a line contact. The two types of grasps are complete: every polygon can be immobilized by two point contacts made by appropriately concave effectors on a pair of vertices determining the diameter (the maximum distance between two vertices); every polyhedron whose vertices are in general position such that there is no pair of two parallel lines, where each line is determined by a distinct collection of two vertices, can be immobilized by a point and a line contact made by appropriately concave effectors on a vertex–edge pair determining the width.

As a corollary, every polygon can be caged by two curved effectors: the effectors in Figures 23(a) and (b) are also caging the polygon. Sufficient conditions for caging can be derived by applying the results of Sections 5.1 and 5.2 (see the similarity between Figure 8 and Figure 23(a), or between Figure 9 and Figure 23(b)).

We can also add more types of grasps and cages; for example, as shown in Figure 23(c), two-point effectors suffice to immobilize/cage some concave polygons as discussed by Vahedi and van der Stappen (2008a).

Funding

We gratefully acknowledge the support of the NSF (grant numbers 1328805 and 1138847) and the ARL (grant number W911NF-10-2-0016).

Notes

References

Aichholzer

Demaine

Erickson

Hurtado

Overmars

Soss

. (2001) Reconfiguring convex polygons. Computational Geometry: Theory and Applications 20(1–2): 85–95.

Allen

Burdick

Rimon

(2012) Two-fingered caging of polygons via contact-space graph search. In: 2012 IEEE international conference on robotics and automation (ICRA‘12), St. Paul, MN, USA, 14–18 May 2012, pp. 4183–4189. Piscataway: IEEE Press.

Berman

Lindsey

Sakar

Kumar

Pratt

(2011) Experimental study and modeling of group retrieval in ants as an approach to collective transport in swarm robotic systems. Proceedings of the IEEE 99(9): 1470–1481.

Bernard

Kondak

Maza

Ollero

(2011) Autonomous transportation and deployment with aerial robots for search and rescue missions. Journal of Field Robotics 28(6): 914–931.

Bicchi

Kumar

(2000) Robotic grasping and contact: A review. In: 2000 IEEE international conference on robotics and automation (ICRA‘00), San Francisco, USA, 24–28 April 2000. Piscataway: IEEE Press.

Borst

Fischer

Hirzinger

(1999) A fast and robust grasp planner for arbitrary 3D objects. In: 1999 IEEE international conference on robotics and automation (ICRA‘99), vol. 3, Detroit, USA, 10–15 May 1999, pp. 1890–1896Piscataway: IEEE Press.

Bose

Bremner

Toussaint

(1996) All convex polyhedra can be clamped with parallel jaw grippers. Computational Geometry: Theory and Applications 6(5): 291–302.

Bower

(1970) Demonstration of intention in the reaching behaviour of neonate humans. Nature 228(5272): 679–681.

Bowers

Lumia

(2003) Manipulation of unmodeled objects using intelligent grasping schemes. IEEE Transactions on Fuzzy Systems 11(3): 320–330.

10.

Brost

Goldberg

(1996) A complete algorithm for designing planar fixtures using modular components. IEEE Transactions on robotics and Automation 12(1): 31–46.

11.

Brown

(1979) Geometric transforms for fast geometric algorithms. PhD Thesis, Carnegie-Mellon University Pittsburgh, USA.

12.

Cappelleri

Fatovic

(2011a) Caging grasps for micromanipulation & microassembly. In: IEEE/RSJ international conference on intelligent robots and systems (IROS‘11), San Francisco, USA, 25–30 September 2011, pp. 925–930. Piscataway: IEEE Press.

13.

Cappelleri

Fatovic

Shah

(2011b) Caging micromanipulation for automated microassembly. In: 2011 IEEE international conference on robotics and automation (ICRA‘11), Shanghai, China, 9–13 May 2011, pp. 3145–3150. Piscataway: IEEE Press.

14.

Cheng

Fink

Kumar

Pang

(2009) Cooperative towing with multiple robots. Journal of Mechanisms and Robotics 1(1): 011008.

15.

Connelly

Demaine

Rote

(2003) Blowing up polygonal linkages. Discrete & Computational Geometry 30(2): 205–239.

16.

Cutkosky

Kao

(1989) Computing and controlling compliance of a robotic hand. IEEE Transactions on Robotics and Automation 5(2): 151–165.

17.

Czyzowicz

Stojmenovic

Urrutia

(1991) Immobilizing a polytope. In: Dehne

Sack

J-R

Santoro

(eds) Algorithms and Data Structures. Berlin Heidelberg: Springer, pp. 214–227.

18.

Davey

Sastra

Piccoli

Yim

(2012) Modlock: A manual connector for reconfigurable modular robots. In: IEEE/RSJ international conference on intelligent robots and systems (IROS‘12), Vilamoura, Portugal, 7–12 October 2012, pp. 3217–3222. Piscataway: IEEE Press.

19.

Davidson

Blake

(1998a) Caging planar objects with a three-finger one-parameter gripper. In: 1998 IEEE international conference on robotics and automation (ICRA‘98), vol. 3, Leuven, Belgium, 16–21 May 1998, pp. 2722–2727. Piscataway: IEEE Press.

20.

Davidson

Blake

(1998b) Error-tolerant visual planning of planar grasp. In: 6th international conference on computer vision, Bombay, India, 4–7 January 1998, pp. 911–916. Piscataway: IEEE Press.

21.

de Berg

Van Kreveld

Overmars

Schwarzkopf

(2000) Computational Geometry. Berlin Heidelberg: Springer.

22.

Diankov

Srinivasa

Ferguson

Kuffner

(2008) Manipulation planning with caging grasps. In: 8th IEEE-RAS international conference on humanoid robots, Daejeon, Korea, 1–3 December 2008, pp. 285–292. Piscataway: IEEE Press.

23.

Dogar

Srinivasa

(2011) A framework for push-grasping in clutter. Robotics: science and systems VII, Los Angeles, USA, pp. 65–72. Cambridge, MA: MIT Press.

24.

Dollar

Howe

(2010) The highly adaptive SDM hand: Design and performance evaluation. International Journal of Robotics Research 29(5): 585–597.

25.

Ferre

Laumond

(2004) An iterative diffusion algorithm for part disassembly. In: 2004 IEEE international conference on robotics and automation (ICRA‘04), vol. 3, New Orleans, USA, 26 April –1 May 2004, pp. 3149–3154. Piscataway: IEEE Press.

26.

Fink

Hsieh

Kumar

(2008) Multi-robot manipulation via caging in environments with obstacles. In: 2008 IEEE international conference on robotics and automation (ICRA‘08), Pasadena, USA, 19–23 May 2008, pp. 1471–1476. Piscataway: IEEE Press.

27.

Fink

Michael

Kim

Kumar

(2011) Planning and control for cooperative manipulation and transportation with aerial robots. International Journal of Robotics Research 30(3): 324–334.

28.

Fruchard

(2012) Small holding circles. Geometriae Dedicata 157(1): 397–405.

29.

Galloway

Clark

Yim

Koditschek

(2011) Experimental investigations into the role of passive variable compliant legs for dynamic robotic locomotion. In: 2011 IEEE international conference on robotics and automation (ICRA‘11), Shanghai, China, 9–13 May 2011, pp. 1243–1249. Piscataway: IEEE Press.

30.

Gopalakrishnan

Goldberg

(2002) Gripping parts at concave vertices. In: 2002 IEEE international conference on robotics and automation (ICRA‘02), vol. 2, Washington DC, USA, 11–15 May 2002, pp. 1590–1596. Piscataway: IEEE Press.

31.

Hanafusa

Asada

. (1977) Stable prehension by a robot hand with elastic fingers. In: 7th international symposium on industrial robots, Tokyo, Japan, pp. 361–368.

32.

Howard

Kumar

(1996) On the stability of grasped objects. IEEE Transactions on Robotics and Automation 12(6): 904–917.

33.

Hsiao

Lozano-Perez

(2006) Imitation learning of whole-body grasps. IEEE/RSJ international conference on intelligent robots and systems (IROS‘06), Beijing, China, 9—15 October 2006, pp. 5657–5662. Piscataway: IEEE Press.

34.

Hudson

Howard

Jain

Bajracharya

Myint

.(2012) End-to-end dexterous manipulation with deliberate interactive estimation. In: 2012 IEEE international conference on robotics and automation (ICRA‘12), St. Paul, USA, 14–18 May 2012, pp. 2371–2378. Piscataway: IEEE Press.

35.

Iben

O’Brien

Demaine

(2009) Refolding planar polygons. Discrete & Computational Geometry 41(3): 444–460.

36.

Jacobsen

Iversen

Knutti

Johnson

Biggers

(1986) Design of the Utah/MIT dextrous hand. In: 1986 IEEE international conference on robotics and automation (ICRA‘86), vol. 3, San Francisco, USA, 7–10 April 1986, pp. 1520–1532. Piscataway: IEEE Press.

37.

Johnson

Koditschek

(2013) Toward a vocabulary of legged leaping. In: 2013 IEEE international conference on robotics and automation (ICRA‘13), Karlsruhe, Germany, 6–10 May 2013, pp. 2568–2575. Piscataway: IEEE Press.

38.

Kosuge

Hirata

Asama

Kaetsu

Kawabata

(1999) Motion control of multiple autonomous mobile robots handling a large object in coordination. In: 1999 IEEE international conference on robotics and automation (ICRA‘99), vol. 4, Detroit, USA, 10–15 May 1999, pp. 2666–2673. Piscataway: IEEE Press.

39.

Kragten

Baril

Gosselin

Herder

(2011) Stable precision grasps by underactuated grippers. IEEE Transactions on Robotics 27(6): 1056–1066.

40.

Kube

Bonabeau

(2000) Cooperative transport by ants and robots. Robotics and Autonomous Systems 30(1): 85–101.

41.

Lakshminarayana

(1978) Mechanics of Form Closure. American Society of Mechanical Engineers.

42.

LaValle

(2006) Planning Algorithms. Cambridge: Cambridge University Press.

43.

Cortés

Siméon

(2009) A path planning approach to (dis)assembly sequencing. In: 2009 IEEE international conference on automation science and engineering (CASE‘09), Bangalore, India, 22–25 August 2009, pp. 286–291. Piscataway: IEEE Press.

44.

Maehara

(2011) On the diameter of a circle to hold a cube. In: Akiyama

Kano

Tan

(eds) Computational Geometry, Graphs and Applications. Berlin Heidelberg: Springer, pp. 147–153.

45.

Markenscoff

Papadimitriou

(1990) The geometry of grasping. International Journal of Robotics Research 9(1): 61–74.

46.

Mason

(2001) Mechanics of Robotic Manipulation. Cambridge: MIT Press.

47.

Mason

Rodriguez

Srinivasa

Vazquez

(2012) Autonomous manipulation with a general-purpose simple hand. International Journal of Robotics Research 31(5): 688–703.

48.

Mason

Salisbury

(1985) Robot Hands and the Mechanics of Manipulation. Cambridge: MIT Press.

49.

McDowell

(2008) Anthropometric reference data for children and adults: United States, 2003-2006. Report for the US Department of Health and Human Services.

50.

Miller

Knoop

Christensen

Allen

(2003) Automatic grasp planning using shape primitives. In: 2003 IEEE international conference on robotics and automation (ICRA‘03), vol. 2, Taipei, Taiwan, 14–19 September 2003, pp. 1824–1829. Piscataway: IEEE Press.

51.

Montemayor

Wen

(2005) Decentralized collaborative load transport by multiple robots. In: 2005 IEEE international conference on robotics and automation (ICRA‘05), Barcelona, Spain, 18–22 April 2005, pp. 372–377. Piscataway: IEEE Press.

52.

Morales

Sanz

Del Pobil

(2002) Vision-based computation of three-finger grasps on unknown planar objects. In: IEEE/RSJ international conference on intelligent robots and systems (IROS‘02), vol. 2, Lausanne, Switzerland, 30 September–4 October 2002, pp. 1711–1716. Piscataway: IEEE Press.

53.

Murray

(1996) Trajectory generation for a towed cable system using differential flatness. In: IFAC world congress, San Francisco, USA, 30 June–5 July 1996, pp. 395–400.

54.

Murray

Sastry

(1994) A Mathematical Introduction to Robotic Manipulation. Boca Raton: CRC Press.

55.

Napier

(1956) The prehensile movements of the human hand. Journal of Bone and Joint Surgery 38B(4): 902–913.

56.

Navarro-Alarcon

Liu

Romero

(2014) On the visual deformation servoing of compliant objects: Uncalibrated control methods and experiments. International Journal of Robotics Research. Epub ahead of print 12 June 2014. DOI: 10.1177/0278364914529355.

57.

Nguyen

(1988) Constructing force-closure grasps. International Journal of Robotics Research 7(3): 3–16.

58.

Nguyen

(1989) Constructing stable grasps. International Journal of Robotics Research 8(1): 26–37.

59.

Park

Yim

(2009) Distributed control and communication fault tolerance for the CKbot. In: ASME/IFToMM international conference on reconfigurable mechanisms and robots (ReMAR‘09), London, UK, 22–24 June 2009, pp. 682–688. Piscataway: IEEE Press.

60.

Pereira

Campos

Kumar

(2004) Decentralized algorithms for multi-robot manipulation via caging. International Journal of Robotics Research 23(7–8): 783–795.

61.

Peshkin

Sanderson

(1986) Reachable grasps on a polygon: The convex rope algorithm. IEEE Transactions on Robotics and Automation 2(1): 53–58.

62.

Pollard

(2004) Closure and quality equivalence for efficient synthesis of grasps from examples. International Journal of Robotics Research 23(6): 595–613.

63.

Ponce

(1996) On planning immobilizing fixtures for three-dimensional polyhedral parts. In: 1996 IEEE international conference on robotics and automation (ICRA‘96), Minneapolis, USA, 22–28 April 1996, pp. 509–514. Piscataway: IEEE Press.

64.

Ponce

Sullivan

Sudsang

Boissonnat

Merlet

(1997) On computing four-finger equilibrium and force-closure grasps of polyhedral objects. International Journal of Robotics Research 16(1): 11–35.

65.

Rimon

Blake

(1999) Caging planar bodies by one-parameter two-fingered gripping systems. International Journal of Robotics Research 18(3): 299–318.

66.

Rimon

Burdick

(1998a) Mobility of bodies in contact. I. A 2nd-order mobility index for multiple-finger grasps. IEEE Transactions on Robotics and Automation 14(5): 696–708.

67.

Rimon

Burdick

(1998b) Mobility of bodies in contact. II. How forces are generated by curvature effects. IEEE Transactions on Robotics and Automation 14(5): 709–717.

68.

Rodriguez

Mason

(2009) Two finger caging: Squeezing and stretching. In: Chirikjian

Choset

Morales

Murphey

(eds) Algorithmic Foundation of Robotics VIII. Berlin Heidelberg: Springer, pp. 119–133.

69.

Rodriguez

Mason

Ferry

(2012) From caging to grasping. International Journal of Robotics Research 31(7): 886–900.

70.

Saranli

Buehler

Koditschek

(2001) RHex: A simple and highly mobile hexapod robot. International Journal of Robotics Research 20(7): 616–631.

71.

Saxena

Driemeyer

(2008) Robotic grasping of novel objects using vision. International Journal of Robotics Research 27(2): 157–173.

72.

Seo

Yim

Kumar

(2013) Restraining objects with curved effectors and its application to whole-arm grasping. In: 16th international symposium on robotics research (ISRR‘13), Singapore, 16–19 December 2013.

73.

Sreenath

Kumar

(2013) Dynamics, control and planning for cooperative manipulation of payloads suspended by cables from multiple quadrotor robots. In: Robotics: science and systems, Berlin, Germany, 24–28June2013.

74.

Sugar

Kumar

(1999) Multiple cooperating mobile manipulators. In: 1999 IEEE international conference on robotics and automation (ICRA‘99), vol. 2, Detroit, USA, 10–15 May 1999, pp. 1538–1543. Piscataway: IEEE Press.

75.

Sundaram

Remmler

Amato

(2001) Disassembly sequencing using a motion planning approach. In: 2001 IEEE international conference on robotics and automation (ICRA‘01), vol. 2, Seoul, Korea, 21–26 May 2001, pp. 1475–1480. Piscataway: IEEE Press.

76.

Trinkle

(1992) On the stability and instantaneous velocity of grasped frictionless objects. IEEE Transactions on Robotics and Automation 8(5): 560–572.

77.

Trinkle

Abel

Paul

(1988) An investigation of frictionless enveloping grasping in the plane. International Journal of Robotics Research 7(3): 33–51.

78.

Ulrich

Paul

Bajcsy

(1988) A medium-complexity compliant end effector. In: 1988 IEEE international conference on robotics and automation (ICRA‘88), Philadelphia, USA, 24–29 April 1988, pp. 434–436. Piscataway: IEEE Press.

79.

Vahedi

van der Stappen

(2008a) Caging polygons with two and three fingers. International Journal of Robotics Research 27(11–12): 1308–1324.

80.

Vahedi

van der Stappen

(2008b) Caging convex polygons with three fingers. In: IEEE/RSJ international conference on intelligent robots and systems (IROS‘08), Nice, France, 22–26 September 2008, pp. 1777–1783. Piscataway: IEEE Press.

81.

Vahedi

van der Stappen

(2008c) Towards output-sensitive computation of two-finger caging grasps. In: 2008 IEEE international conference on automation science and engineering (CASE‘08), Arlington, USA, 23–26 August 2008, pp. 73–78. Piscataway: IEEE Press.

82.

Vahedi

van der Stappen

(2009) On the complexity of the set of three-finger caging grasps of convex polygons. In: Robotics: science and systems, Seattle, USA, 28June–1July2009.

83.

van der Stappen

Wentink

Overmars

(1999) Computing form-closure configurations. In: 1999 IEEE international conference on robotics and automation (ICRA‘99), vol. 3, Detroit, USA, 10–15 May 1999, pp. 1837–1842. Piscataway: IEEE Press.

84.

Wan

Fukui

Shimosaka

Sato

Kuniyoshi

(2012) On the caging region of a third finger with object boundary clouds and two given contact positions. In: 2012 IEEE international conference on robotics and automation (ICRA‘12), St. Paul, USA, 14–18 May 2012, pp. 4154–4161. Piscataway: IEEE Press.

85.

Yokoi

Kobayashi

Maeda

(2009) 2D Caging manipulation by robots and walls. In: IEEE international symposium on assembly and manufacturing (ISAM‘09), Seoul, Korea, 17–20 November 2009, pp. 16–21. Piscataway: IEEE Press.

86.

Zamfirescu

(1995) How to hold a convex body?Geometriae Dedicata 54(3): 313–316.