1

Caging Grasps of Rigid and Partially Deformable
3D Objects with Double Fork and Neck Features
Anastasiia Varava, Danica Kragic, and Florian T. Pokorny

Abstract—Caging provides an alternative approach to pointcontact based rigid grasping which relies on reasoning about the
global free configuration space of an object under consideration.
While substantial progress has been made towards the analysis,verification and synthesis of cages of polygonal objects in theplane, the use of caging as a tool for manipulating generalcomplex objects in 3D remains challenging. Furthermore, many
objects are naturally partially deformable, making classical rigid
caging methods inapplicable. In this work, we formally generalize
the caging condition in 3D to caging of objects up to a defined
set of deformations and propose a novel framework for thesynthesis and verification of caging grasps on a specific classof 3D objects which exhibit geometric features we call double
forks and necks. We consider the synthesis and verification of acaging grasps on 3D objects by means of one or more caging toolsthat can be arranged to form an approximate closed loop aroundthe identified neck or double fork features of the object. As a
key theoretical tool, we utilize an augmentation of the classicaltopological invariant – the linking number, allowing us to prove
sufficient conditions for such cages to exist, even in the casewhen the object under consideration is partially deformable. We
present and evaluate an algorithm for synthesizing and verifying
such caging grasps on triangular surface meshes in 3D.

Fig. 1. Illustration of human manipulations exhibiting two types of cagesof rigid and partialy deformable objects studied and formalized in this work.
The objects in the first row have a neck feature - a thin object ‘neck’ withthicker ends at both sides. The second row showcases deformable objects that
contain an inscribed double fork, intuitively consisting of a pair of inscribedcurves whose ends are sufficiently spread spacially to prevent the loop formedby the human hand from moving arbitrarily far away from the object.

Index Terms—Cage, grasping, shape features

I. I NTRODUCTION
To manipulate an object in its environment, a robot requires
the ability to synthesize manipulator configuration that will
enable it to control the pose of an object up to some degree. For a rigid object in particular, one may consider animmobilizing grasp of an object. However, most analyticalgrasp synthesis frameworks [3], [19], require a knowledgeof physical properties such as friction coefficients and centerof mass, while current data-driven learning-based methods[4] require large corpora of prior training data with similar
sets of objects, physical parameters and robot embodiment
to infer grasps. Furthermore, many objects as depicted inFig. 1 naturally allow some degree of deformability, making
well-established frameworks for rigid grasping inapplicable.
Similarly, even when the object under consideration is rigid,
new generations of robots relying on soft hands [6], require
new paradigms for manipulation not based on the rigid object
assumption.
An alternative to grasping, is the notion of a cage, where
the robot generates a joint-configuration which prohibits the
A. Varava and D. Kragic are with the Computer Vision and Active Perception Lab, Centre for Autonomous Systems, School of Computer Science andCommunication, Royal Institute of Technology (KTH), SE-100 44 Stockholm,
Sweden. E-mail: {varava, dani}@kth.se
F. T. Pokorny is with AMPLab and Automation Lab, University of California, Berkeley, CA 94720 Berkeley, USA. E-mail: ftpokorny@berkeley.edu

object from moving arbitrarily far away, while not necessarily
immobilizing the object completely. Cages can furthermore
serve as a waypoint to a form or force closure grasp [24].
While substantial progress to the synthesis of caging grasps
on polygons in 2D has been made in recent years [20], [23],[21], the generation of cages in 3D has remained a difficult
challenge, with recent works making progress on specific basic
shape primitives [17], [18]. A reason why the synthesis of
caging grasps on general 3D objects has remained elusive isthat the caging condition requires reasoning about the global
topology of the configuration space of an object, rather thanjust a local geometric analysis as in the case of form and force
closure. Additionally, many objects in the environment exhibit
some degree of deformability. Consider the examples in Fig. 1.
Each of these human hand configurations intuitively cages theobject under consideration, because both extremities of the
caged object are larger than the loop formed by the humanhand.
The main goal of this paper is to provide a formal framework allowing us to formalize, algorithmically verify andsynthesize caging configurations similar to the ones displayedin the figure above. For this purpose, we define the notions of a‘double fork’ and ‘neck’ in an object and provide an algorithm
to both determine these features and to verify the caging condition for a given loop representing the manipulator and a meshrepresentation of the object. For this purpose we introduce anapproach formalizing when a loop encloses a ‘thin’ part of an2

object. This requires the use of several ideas from topology,
and in particular linking numbers. Our approach allows us
to discuss caging under partial deformations in 3D, thereby
extending the types of objects that can be analyzed from prior
works that required a restricted set of shape primitives [18] orthe existence of holes [22], [29] in an object. The second goalof the paper is to provide algorithms for shape analysis andcage verification. Finally, we also provide simple algorithms
generating caging configuration for a PR2 robot, simulated in
OpenRave [9]. However, providing and evaluating a complete
framework for this is beyond the scope of the paper, as themain purpose of the proposed algorithms is to illustrate how
one can use our theoretical results.
The rest of the paper is organized as follows: in the next
section, we briefly review the history of caging in the robotic
manipulation context. Section III contains a general overview
of our system. Section IV recalls some notions from topology,
used in Section V. Section V covers the theoretical backgroundof our approach: we define the necessary constructions andderive the sufficient conditions for the caging tool to boundthe mobility of the object, represented as a graph. In Section
VI, we describe our methodology and discuss practical ways
to extract a graph representation from an object. Finally, wesummarize our results and discuss possible directions of future
work in Section VII.
II. M OTIVATION AND R ELATED W ORK
Here, we briefly review key aspects of related prior works
on caging in robotics, and the relationship between caging andgrasping research in particular.
A. Caging
Following early work of [2] who considered sufficientconditions for a sphere to be caged by a net, the notion ofa planar cage was introduced in 1990 by Kuperberg [15] asa set of n coplanar points lying in the complement to theinterior of a given polygon and preventing it from moving
arbitrarily far from its initial position. In the robotics context,
these points can be considered as fingertip positions of a robot
manipulating an object in the plane. In general, the caging
problem in 2D or 3D consists of determining a configurationof one or several robotic grippers or caging tools such that an
object of interest cannot escape arbitrarily far, and additional
obstacles in the environment can also be considered in thisapproach.
The derivation of necessary and sufficient caging conditions
poses a highly challenging problem due to the complex
geometric structure of the free configuration space of realworld objects. Several works were devoted to the case of 2D
object representations, as even in this simplified case the exact
computation of caging configurations poses a challenging
problem. Early work of [23] proposed an algorithm computing
a set of configurations of a two-fingered hand to cage planar
non-convex objects. Subsequently, [20], [31] addressed closely
related problems and [20] proposed an algorithm reporting
all two-finger caging sets for a given concave polygon. This
result was extended by [31], where an algorithm that returns

all caging placements of a third finger is also described whena polygonal object and a placement of two other fingers isprovided.
The caging problem becomes even more challenging when
we move to the 3D-objects. The work [21] proposed an algorithm that computes all two-finger caging configurations for
non-convex polytopes, where the fingertips are approximatedby points or spheres. In [24], a notion of a pregrasping
cage is introduced: a caging configuration from which theobject can be grasped without breaking the cage. The fingers
are again approximated as points, and pregrasping cages arestudied via grasping functions: scalar functions defined on
the finger formation that control the process of going froma cage to a grasp. However, in these works the fingertips areapproximated by points or spheres, and more complex hand
representations are not taken into account. In [17], [18], theauthors proposed intuitively determined conditions for caging
a small collection of parametrically defined simple objects in
3D, such as discs, tori and objects with ‘waists’. In [18],this approach is generalised to objects for which geometricsub-structure is pre-determined and stored in a database. For
general 3D objects and manipulators, there currently does notexist a provably correct practical caging algorithm to the bestof our knowledge.
In this work, we propose sufficient conditions for caging
objects in 3D with particular well-defined shape properties.
A core contribution of our approach is the use of a graphbased shape representation in conjunction with a techniquefor rigorously proving that an object is caged. Our approachis flexible with respect to the choice of the manipulator type:
it is applicable for a set of fingertips, an entire hand, an arm,or a system of cooperating mobile robots as long as thesemanipulators can form an approximate closed caging loop.
The present work constitutes a further evolution and extension of a sequence of previous works by our group [22],[29], [30] which introduced an approach to caging 3D objects
that exhibit holes (non-trivial first homology) with complex
multifingered robotic hands. We previously considered bothcontrol strategies to guide the robot arm/hand towards a caging
configuration and an augmented task-space RRT planner forplanning hand and arm motions to achieve caging configurations. In the current work, we focus in particular on the novel
theoretical aspects of our contribution and the proposed shape
representation.
B. Grasping
The caging problem has been considered as a complement to
the traditional force-closure grasping approach [3], [19] which
is based on the calculation of the forces exerted by the robot
and the friction between the contacting surfaces, and hence
relies on the determination of contact points and normals to theobject surface at these points. Therefore, a detailed knowledgeof the manipulated object’s local geometry and the robot’s poseis crucial in this context.
An important advantage of caging is that it relies on
global geometric information about the object’s shape andmanipulator’s configuration which may be estimated more3robustly than local friction coefficients and contact normals.
Furthermore, while in force and form closure grasping, themanipulator is required to tightly establish contact with theobject, thereby introducing an additional hard constraint, this isoften not necessary when a caging grasp is considered instead.
One of the disadvantages of our approach is that it requiresa three-dimensional model of the object. For instance, in[26] the authors compute grasping points using raw vision
input in a data-driven manner without requiring a threedimensional object model. While data-driven approaches tograsping provide an exciting avenue of recent research [4][16],training a data-driven model requires large corpora of training
data, which is especially challenging for objects that exhibit
deformability. Our object-model based approach, while being
applicable only to objects with neck or double fork features,
instead allows us to perform a complete geometric analysis ofpreviously unseen models with these features, and enables us
to synthesize cages and study their properties formally.
In this paper, we work with deformable objects and, in particular, generalize the notion of caging to this case. However,
we do not attempt to model the deformability in the sense ofpredicting the deformations of the object, like it has been donein [12]. We do not consider physical properties of objects andsimply allow them to be partially deformable under certain
constraints.
III. OVERVIEW OF OUR APPROACH

Fig. 2. Overview of our approach to caging.

The focus of this work is on the shape representation,
theory and algorithmic synthesis and verification of caging
configurations. Fig. 2 outlines our approach for the twonovel shape representations we propose. The first is based on‘skeletonization and double forks’ (first row) and the secondon object features we call ‘necks’ (second row). Intuitively,

Fig. 3. Consider two ‘obstacles’, containing points u and v respectively which
are large enough to block the displayed loop from escaping. In this case, theloop cages the two obstacles connected via p. In this paper, these ‘obstacles’
correspond to wide parts of an object; the presence of such parts makes theobject suitable for caging with our approach.

both of these shape features can be considered as narrow partsof the object, around which the caging tool is placed.
The third row outlines previous work [22], [29], [30] bysome of the coauthors and collaborators. As input to ourpipeline, we consider a point-cloud or a mesh of an object, seeFig. 2a,b). In our previous work (third row), we consideredobjects that exhibit tunnels/voids as formalized by a nontrivial first homology group. We previously extracted a shortest
homology basis resulting in a collection of loops that furnishedan object representation suitable for caging. In the case of the
depicted tea cup, this basis consisted of a single tight loop
winding around the handle. Using such loops, control andmotion planning algorithms for caging were developed [22],[29], [30].
In the present paper, we consider the initial (either point
cloud or mesh) representation of the object. We define andextract shape features from the object, place the manipulator
around the narrow part, derive sufficient caging conditions,and prove that the resulting configuration yields a valid cage.
We abstract the caging tool/manipulator by means of a closed
loop l ∈ R3 in the complement of the interior of the object.
We call l the caging loop. Examples of caging loops include
loops formed by two arms with locked hands that are closed
around an object, two touching fingers, etc.
To bound the mobility of the object such as the depicted bear
and bust our caging approach considers placing a loop arounda narrow part of the object as illustrated in Fig. 3. Intuitively,
this representation allows us to work with partially deformableobjects, provided the ‘wide parts’ preserve a lower bound on
their size under deformation. Double forks and necks are two
examples of this geometric structure, proposed in this paper.
While, at first sight, this approach appears to be intuitive andrather simple, a key difficulty we resolve is to algorithmicallydetermine these features and to algorithmically verify weathera caging loop ‘surrounds’ the finite narrow part in a way thatis invariant under a set of continuous deformations of theobject. Section VI reviews the required technical backgroundon topology that may be skipped by experienced reader.
Section V presents the core formalizations of our approach,including:A generalization of caging for partially deformable objects (Def. 11);
• Definition of neck and double fork features;• Formalization of when the manipulator is placed ‘around’
the object;•

4

Proof of sufficient conditions for caging objects withnecks and double forks.
Section VI provides algorithms and implementation results.
The contributions of this section are:• algorithms for detection of double forks and necks in amesh, representing the object;• an algorithm constructing the caging loop candidates
around the computed shape features;• a simple algorithm computing caging configurations fora PR2 robot, simulated in OpenRAVE [8];• an algorithm verifying a given caging configuration,
based on the sufficient conditions derived in Section V.
•

Fig. 5. Two embeddings of the space O into R3

Furthermore, we recall the notion of an isotopy:
IV. T OPOLOGICAL BACKGROUND
Here we provide underlying notions from topology requiredin Section V. This section can be skipped by a reader familiar
with general and algebraic topology. Further details can befound in [13].
A. Deformations: homotopy and isotopy
To work with deformable objects, we require a formal
definition of a continuous deformation. Intuitively, a continuous deformation allows stretching and bending, but disallows
actions such as cutting and gluing. In topology, a continuous
deformation between two maps f, g : X → Y can beformalized by means of the notion of a homotopy. Using thenotation I = [0, 1], we have:
Definition 1. Let X, Y be topological spaces, and let
f, g : X → Y be continuous functions. A continuous
map H : X × I → Y , such that for each x ∈ X :H(x, 0) = h0 (x) = f (x), H(x, 1) = h1 (x) = g(x), is calleda homotopy between f and g. Respectively, the functions f
and g are called homotopic if there exists a homotopy between
them.

Fig. 4. Let f : I → X, g : I → X be paths in the space X. Then f
can be deformed to g by means of a homotopy H : I × I → X, where
H(s, t) = ht (s) for each s, t ∈ I.

Here, the parameter t ∈ [0, 1] can be considered as a timeparameter deforming f to g as t varies from 0 to 1. One of thesimplest examples of a homotopy is a homotopy of paths, seeFig. 4. In our approach, it is convenient to consider the object
as an abstract topological space O, embedded in R3 whosegeometric shape and position are specified by an embedding:Definition 2. A map f : X → Y between topological spaces
X and Y is called an embedding if f is a homeomorphism 1
between X and its image f (X).

Definition 3. A homotopy H between two embeddings f andg from X to Y is called an isotopy if, for each t ∈ I, the map
ft : X → Y defined by ft (x) = H(x, t) is an embedding.
We consider the deformable object’s shape and position ata particular time instance to be formalized by a corresponding
embedding ι : O → R3 , see Fig 5, and represent object deformations and position changes by means of special homotopies
of its embedding called isotopies:
Given an initial initial shape and position of a deformableobject O0 ⊂ R3 , and model deformations and movement of
the object towards a final configuration O1 ⊂ R3 , as a corresponding isotopy between the initial embedding ι0 : O → R3 ,
ι0 (O) = O0 , and the final embedding, ι1 : O → R3 ,
ι1 (O) = O1 .
B. The fundamental group and linking numbers
In order to formally describe when the manipulator is placedaround a narrow part of an object, we build on the notion of
the linking number, an integer quantity that can be computedfor two closed curves in R3 . When the linking number of
two curves is non-zero, these curves are linked and can inparticular not be ‘pulled apart’ under continuous deformationsof the curves (see Fig.6). We will extend the notion of linking
numbers to define a linkability condition for neck and double
fork features of an object which themselves do not necessarily
contain closed curves. This will allow us to formally verify
caging configurations.
For this purpose, we recall the notion of the fundamentalgroup. A loop in a topological space X is given by a curvef : I → X whose end-points coincide: f (0) = f (1). A loopthat can be continuously contracted to a point is called trivial.
For x0 ∈ X, let L(x0 ) = {f : I → X : f (0) = x0 = f (1)}be the set of loops in X with base point x0 . We consider
two loops f, g ∈ L(x0 ) equivalent if there exists a homotopy
between f and g that keeps x0 fixed. The equivalence classof a loop f ∈ L(x0 ) is denoted by [f ]. Depending on the
topological properties of the space X, two loops may or may
not be continuously deformable into to each other, see Fig 7.
Definition 4. The fundamental group of X with a base point
x0 consists of the set of the equivalence classes of loops withbase point x0 and is denoted π1 (X, x0 ).
1 A homeomorphism is a continuous bijection with a continuous inverse.

5

The above definition is useful for our theoretical frameworkin Section V. Namely, we use it to work with the linkability
relation, between the object and the manipulator.
Definition 7. The linking number between two differentiable
loops α, β : S1 → R3 that are each homeomorphic to acircle in R3 can be computed directly by means of the Gauss
Linking Integral:
I Iα(s) − β(t)1
, α0 (s) × β 0 (t)idsdt.
hlk(α, β) =4π S1 S1 kα(s) − β(t)k3
Fig. 6. The linking number lk(α, β) of curves α and β is equal to 1, whilelk(α, γ) = lk(β, γ) = 0. The reason for that is α and β ‘pass through’ eachother, while γ is completely disjoint from both of them.

A discrete version of the above formula, for the case ofpiecewise linear loops α, β : S1 → R3 is discussed in [14]and can be used to efficiently determine the linking number inthe piecewise linear case. Thus, the above definition provides
a practical approach to compute lk(α, β) in Section VI.
V. T HEORETICAL C ONTRIBUTION
In this section, we first generalize the notion of caging to
the case of deformable objects and show that our definition
is consistent with the classical case for rigid objects. Further,
we formally define double fork and neck features, as well asclasses of object deformations preserving these features. This
allows us to prove sufficient caging conditions for partially deformable objects exhibiting the neck and double-fork features.

Fig. 7. The displayed space X (grey region) has a hole, thus the loop γ
cannot be deformed into α, so that [γ] 6= [α], while α and β are homotopy
equivalent, so that [α] = [β]. In this case X is hence not simply connected.

We denote by −f the direction-reversed loop −f (t) =f (t−1) for t ∈ I and by f ◦g the concatenated loop following
first g at twice the speed and then f at twice the speed. The
fundamental group in fact forms an algebraic group underconcatenation and direction-reversal of loops and allows us to
study properties of a topological space X. When X is pathconnected (i.e., if there is a path joining any two points in X),
the choice of base point is in fact unimportant for our purposessince the groups π1 (X, x) ∼= π1 (X, x0 ) are isomorphic for any
0x, x ∈ X. In particular, the fundamental group is called trivial
when every loop can be contracted to a point. We define:
Definition 5. A topological space X is called simplyconnected if X is path-connected and has trivial fundamentalgroup.
Fig. 7 visualizes a space that is not simply connected, while
e.g. X = R3 provides an example of a simply connected space.
We now can provide two equivalent (up to sign) definitionsof the linking number. We refer the reader to [25] for moredetails. The first definition is convenient for our theoreticalframework, while the second serves for computational purposes.
Definition 6. Consider two loops α, β in R3 both homeomorphic to a circle in R3 and such that α ∩ β = ∅. Then β
represents an element in the fundamental group π1 (R3 − α),which is isomorphic to Z. The loop β is hence mapped to an
integer, called the linking number lk(α, β). In particular, iflk(α, β) 6= 0, then β is non-trivial in π1 (R3 − α).

A. Caging under deformability assumption
We start our formalization with the definition of the object.
If we assume the object to be rigid, it can be defined simply
as a subset of R3 . However, as we want to allow object
deformations, we need to distinguish between the conceptof the object and its shape. For this purpose, we represent
the object as an abstract topological space, and introduce thenotion of its shape – the way it is placed into R3 by meansof an embedding:Definition 8. Let O be a compact topological space. Assume
that it can be embedded into R3 : let ι : O → R3 be an
embedding. Then we call O the object, and the image of theembedding O = ι(O) its shape.
Mathematically, the above definition allows degeneratecases when the object has no thickness. For example, a curvein R3 satisfies the above definition of the shape. To be realistic,
we avoid these cases by adding an assumption about the shapeof the object:
Assumption 1. Assume that for any shape O of the object
O there exists a non-empty open set U ⊂ R3 , such that O =cl(U ).
In the above cl(U ) denotes the closure of U . We distinguishbetween a situation when the manipulator is in contact withthe object, but does not penetrate the object itself, and whenthe manipulator penetrates the object.
Definition 9. Let O ⊂ R3 be the shape of the object O. A
point x ∈ (O − int(O)) is said to be in contact with theobject, while a point x ∈ int(O) is said to penetrate theobject.

6

Now we can define the notion of caging. Let us start withthe classical assumption that the object is rigid. In this case, theobject can escape only by means of rigid body motions. The
following definition formalizes caging under this assumption.
Definition 10. Consider an object of the shape O and let
M ⊂ R3 be a set. We define the free configuration space of O
with respect to M to be the set of rigid transformations notcausing penetrations with the object:

medial axis to a graph. This skeleton yields a geometric graph
G = (V, E) that lies in the object and a function, reflecting the
distance from each point on the graph to the object’s surface
is also provided. Note though that our approach is general anddoes not depend on a particular skeletonization technique. We
introduce the following definition, see Fig. 8.

CO = {g ∈ SE(3) : M ∩ g.int(O) = ∅}.
If the identity element e ∈ CO corresponding to an
initial configuration of O relative to M lies in a boundedpath-component of CO , we say that the set M cages theobject O. Here g.x ∈ R3 denotes the result of applying therigid transformation g ∈ SE(3) to x ∈ R3 , and similarlyg.int(O) = {g.x ∈ R3 : x ∈ int(O)}.
Note that with the above notion of caging, we allow contacts
between M and O but disallow penetrations. Note further that
M can be an arbitrary set, such as a discrete number of points,
a curve, etc.
We want to generalize the notion of caging by allowing theobject to be deformable. In this case, the object can escapefrom the manipulator not only by rigid body motions, butalso by changing its shape. Thus, an escaping path can be
represented by an isotopy, as defined in Section IV. Since weassume that the caging tool is rigid, we can without loss ofgenerality center our coordinate system at the manipulator andassume that its position is fixed.
Definition 11. Consider an object O with shape O given by
the embedding i : O → O and let M ⊂ R3 be a set. We saythat an isotopy H : O × I → R3 with H(x, 0) = i(x) for
all x ∈ O is a non-penetrating isotopy of the object withrespect to M if int(H(O, t)) ∩ M = ∅ for all t ∈ I. Let
D be a subset containing all the non-penetrating isotopies ofO ⊂ R3 . D specifies a set of allowable deformations. Assume
that M is fixed in space. We say that M cages O under Ddeformations if any non-penetrating isotopy H ∈ D satisfies
dist(M, H(O, t)) ≤ C for all t ∈ I and for some fixed C ≥ 0.

Fig. 8. Different examples of double forks. The set of central vertices canbe either finite or infinite.

Definition 12. Let u, u0 , v, v 0 ∈ R3 and let p : I → R3 andp0 : I → R3 be two embeddings, such that p is a path inR3 from u to v, while p0 is a path in R3 from u0 to v 0 . Ifdist(p, {u0 , v 0 }) > d, dist(p0 , {u, v}) > d and p ∩ p0 6= ∅ wesay that p, p0 form a double fork with diameter d. The set ofvertices C = {v ∈ V : v ∈ p ∩ p0 } is called the set of central
vertices.
Since, according to Assumption 1, our object always has
some thickness, it is convenient to consider the double fork
together with some neighbourhood:Definition 13. Given a double fork consisting of p, p0 : I →R3 and with parameter d and ε > 0, we define a double forkof a thickness ε as DFε = DFε (p(I), p0 (I)) = {x ∈ R3 :dist(x, p(I)) ≤ ε or dist(x, p0 (I)) ≤ ε}.
Let us now consider objects with another geometric feature
which we refer to as a neck.

By the distance between M and H(O, t) in the above
definition we mean the infimum of the distances between any
two of their respective points,
dist(M, H(O, t)) =infkx − ykx∈M,y∈H(O,t)

Remark 1. Observe that the previous notion of caging under
rigid transformations in Def. 10 corresponds to a particularclass of isotopies induced by rigid transformations. See Lemma
1 in the Appendix for the detailed explanation.
B. Double fork and neck features

Fig. 9. A neck Nε,d (f (I)) and a caging loop l

Let us now consider our first shape feature, which we referto as a double fork.
We consider a graph embedded into the object we want to
cage. Such a graph G can be obtained using a skeletonization
technique. We in particular rely on the technique proposed in[7] where a skeleton of the object is obtained by retracting its

Intuitively, a neck of the object is a constriction which issituated between two wider parts. We use this feature to extract
a simplified geometrical representation of the object, which
can be considered as its ‘core’. Formally, we define this asfollows:

7

Definition 14. Let f : I → R3 be an embedding. For ε > 0
and d > ε, we define a neck Nε,d (f (I)) of diameter d andthickness ε as follows: Nε,d (f (I)) = {x ∈ R3 : kx−f (s)k ≤ε for some s ∈ I or kx − f (0)k ≤ d or kx − f (1)k ≤ d}.

either of its endpoints must ‘go through’ the loop at least once.
However, the process of ‘going through’ the loop for a point
also must be adequately formalized. The following proposition
makes this precise:Intuitively, we can imagine two spheres (note that, in degenerate cases, they can intersect) of radius d, inscribed into theobject O (see Fig.9) and connected by an ε-neighbourhood of
the defining curve f . The term ‘neck’ is inspired by ‘choking
loops’ proposed in [11].
One can notice that in fact, any object with a neck contains adouble fork as well. Indeed, assume we have a neck consistingof two spheres and a path between them, and let u and u0
be diametrically opposed on one sphere, and v and v 0 be
diametrically opposed on the other sphere. Let p connect uand v, p0 connect u0 and v 0 . Now each vertex is located at
a distance to the other path of at least the smaller sphere’s
radius. However, note that the diameter of the corresponding
double fork is half the diameter of the initial neck. Since thediameter of the feature will be directly related to the cagabilityof the object, we consider a neck as a separate shape feature
here.

Proposition 1. Let l ⊂ R3 be a loop homeomorphic to acircle. Consider a path f : I → W f ree = R3 − l, f (0) = u,
f (1) = v, linkable to l via a S(l)-avoiding augmentation.
Assume f can be continuously deformed to a path f 0 : I →W f ree , such that f 0 ∩ S(l) = ∅, by a homotopy F : I × I →W f ree , F (s, 0) = f (s), F (s, 1) = f 0 (s). Then ∃t ∈ I suchthat F (0, t) ∈ S(l) or F (1, t) ∈ S(l).

C. The linkability relation
We now define the ‘linkability’ relation between the caging
loop and a curve inside the object. We address this byintroducing a superset of the loop which distinguishes curves
that go through the loop from those that go around the loop.
Algorithmically, we then compute linkability with the help of
the linking number, recalled in Section IV.
Let a loop l be located in R3 . We want to split all thepossible curves in R3 into two classes: those which ‘pass
through l’, and those which do not. Given a query qurve
f , we approach this problem by first constructing a special
curve g with the same end-points as f that avoids a superset
S(l) of the loop l entirely - we call this curve an S(l)avoiding augmentation. We then show how an investigation ofhomotopy classes then leads to a classification of ‘linkability’generalizing the classical linking number concept in topology.
To reach a formally correct derivation, we will require thatR3 − S(l) is simply connected. This is the case in particular,when S(l) is given by the convex hull of l.
Definition 15. Consider a path f : I → W f ree = R3 −l, f (0) = u, f (1) = v and where l denotes a loop in R3
homeomorphic to a circle. Let S(l) denote a subset of R3
containing l such that R3 −S(l) is simply-connected. The path
f is called linkable to l via a S(l)-avoiding augmentation
if there exists another path g : I → W f ree from u to v suchthat g ∩ S(l) = ∅ and the loop f ◦ −g is not null-homotopic
in W f ree .
Note that any path which is linkable to l via a S(l)-avoiding
augmentation intuitively ‘passes through l’. However, S(l) can
be constructed in different ways, and for each particular S(l)a set of all paths linkable to l is a subset of all paths passing
through l.
Let us now consider a curve passing through the loop l.
In order for it to escape from l via a continuous deformation,

Fig. 10. A homotopy between the paths f and f 0

Proof. Assume the contrary that for all t ∈ I, F (0, t) ∈/ S(l)and F (1, t) ∈/ S(l). Let us denote ft (s) = F (s, t), so thatf0 = f and f1 = f 0 . Similarly, let us = F (s, 0), vs = F (s, 1)
for all s ∈ I. Finally, let ui uj (vi vj ) denote the corresponding
path from ui to uj (from vi to vj ) in F (0, .) (respectively, in
F (1, .)), where i, j ∈ I, i 6= j.
Let g = u0 u1 ◦ f1 ◦ v1 v0 , see Fig. 10. Consider a familyof paths φt : I → W f ree defined as φt = u0 u(1−t) ◦ f(1−t) ◦v(1−t) v0 , t ∈ I. This defines a path homotopy deforming φ0 =u0 u1 ◦ f1 ◦ v1 v0 = g to φ1 = f0 . So, g ' f0 . Recall thatf1 ∩ S(l) = ∅. Moreover, by our assumption, for all t ∈ I :ut ∈/ S(l), vt ∈/ S(l). So, g does not intersect with S(l). Recall
now that f0 is linkable to l. So, there exists a path g 0 ⊂ W f ree
from u0 to v0 such that g 0 ∩ S(l) = ∅ and the loop f ◦ −g 0
is not null-homotopic. Finally, note that g ' g 0 , since both ofthem can be considered as a paths in R3 − S(l). Therefore,f ◦ −g ' f ◦ −g 0 . This leads us to contradiction.
Let us now discuss how to algorithmically check whether agiven path p from u to v is linkable to the loop l with respect
to some S(l). First of all, we have to properly construct S(l).
For our implementation, we choose S(l) = Conv(l), where
Conv(l) denotes the convex hull of l. Note that R3 − S(l) is
simply-connected since S(l) can be contracted to a point in
R3 and hence π1 (R3 − S(l)) ' π1 (R3 − {0}) = {0}.
To determine if a path f from u to v such that u, v ∈/ S(l) =Conv(l) is linkable via a Conv(l) avoiding augmentation, we
will algorithmically determine an arbitrary path paux from u tov in the complement of Conv(l). The relation of being linkable
does not depend on the particular choice of paux ∈ R3 − S(l),since R3 − S(l) is simply-connected and therefore for any

8other path p0aux ∈ R3 − S(l) with the same endpoints the loopp ◦ −paux can be continuously deformed to p ◦ −p0aux .
Finally, we have to check whether the resulting loop p ◦−paux is non-trivial in R3 − l for which we will utilize thelinking number lk(l, p ◦ −paux ).
D. Sufficient caging conditions for objects with double forks
and necks
Now we can prove sufficient caging conditions for objects
with double fork and neck features. Since we want our objects
to be partially deformable – i.e., to preserve shape features
under deformations – we start with defining the classes ofallowed deformations.
In the definition of a double fork of the thickness ε, we
consider two paths p, p0 as a subset of the object DFε . Since inour context this structure is crucial for an object to be suitablefor caging, we consider it as a ‘skeleton’ of the object inthe sense that its deformations induce the deformations of theentire object. To formalize this, we introduce the following
definition.
Definition 16. Let O be an object of a shape O, where ι :O → R3 , ι(O) = O is the corresponding embedding, andι−1 : O → O is its inverse. Let DF = DFε (p(I), p0 (I)) ⊂ O
be double fork of diameter d and thickness ε. Consider an
isotopy H : O × I → R3 , such that H(x, 0) = ι(x). If foreach t ∈ I a pair of paths H(ι−1 (p(I)), t), H(ι−1 (p0 (I)), t)
yields a double fork of a diameter d, then H is called a double
fork preserving deformation of the object with respect to DF .
Now we can prove caging conditions for objects with double
forks:
Theorem 1. Let O be an object of a shape O ⊂ R3 ,ι(O) = O
be the corresponding embedding, and ι−1 : O → O is its
inverse. Let l be a loop in R3 , representing the manipulator.
Let S(l) be a subset of R3 containing l such that R3 − S(l)is simply-connected. Let p, p0 : I → O be two embeddings,
linkable to l via S(l)-avoiding augmentations and supposethat p, p0 form a double fork with parameter d > 0. Let ε > 0
and assume DF = DFε (p(I), p0 (I)) to be a subset of O.
Finally, assume O ∩ l = ∅.
Consider the deformation class FP of the object O, suchthat any deformation H in FP is non-penetrating with respect
to l and double fork preserving with respect to DF .
If diam(S(l)) < d, then l cages the object O under FPdeformations.
Proof. Suppose on the contrary that for any C ≥ 0 there exists
an isotopy H in class FP taking the object O at distancegreater than C away from l. Let C = 2 · diam(S(l)). Then,the images H(ι−1 (p(I)), 1) ⊂ R3 and H(ι−1 (p0 (I)), 1) ⊂R3 of p and p0 are separated from l at a distance greaterthan diam(S(l)). Therefore, the paths H(ι−1 (p(I)), 1) andH(ι−1 (p0 (I)), 1) do not intersect S(l) and therefore are notlinkable to l via S(l)-avoiding augmentation. Hence, by Proposition 1 there exists a first time t at which one of the end-pointsof the deforming p, p0 is in S(l). Without loss of generality,
assume x = H(ι−1 (p(0)), t) ∈ S(l). Since the deformed p0 (I)Fig. 11. The escaping process at time t. The boundary of O is depicted withdashed curve. The image of p is depicted in blue, while the caging loop is in
red.

is at that point either still linkable to l, and therefore intersects
S(l), or an endpoint of p0 (I) lies also in S(l), we have twopoints in S(l), whose distance from each other is at leastd > diam(S(l)), which is a contradiction, see Fig.11.
Let us now consider objects with necks. Although any neckcontains a double fork of a smaller diameter, and thus can beconsidered as a special case of the latter feature, our caging
conditions for double forks are more strict than the ones fornecks, and thus we formulate them as a separate theorem.
Similarly to the case of a double fork, we consider f (s)as a ‘skeleton’ of the object, and we hence assume that its
deformations induce the corresponding deformations of theentire object.
Definition 17. Let O be an object of shape O ⊂ R3 , whereι : O → R3 , ι(O) = O is the corresponding embedding, andι−1 : O → O is its inverse. Let a neck N = Nε,d (f (I)), for f :I → O be contained in O. Consider an isotopy H : O × I →R3 , H(x, 0) = ι(x). H is a neck preserving deformation
with respect to N , if for each t ∈ I the image H(ι−1 (f (I)), t)
forms a neck with parameters ε, d, which is a subset of thecorresponding image of O:
Nε,d (H(ι−1 (f (I)), t)) ⊂ H(O, t).
Theorem 2. Let O be an object of the shape O ⊂ R3 , ι(O) =O be the corresponding embedding, and ι−1 : O → O be its
inverse. Let the neck N = Nε,d (f (I)) be its subset, wheref : I → R3 is an embedding, and ε > 0, d > 0 are realconstants. Assume that O ∩ l = ∅. Let f be linkable to l via
an S(l)-avoiding augmentation. Consider a deformation class
N P of the object O, such that each deformation H in N P
is non-penetrating with respect to l and neck preserving withrespect to N . Then, the object O is caged by l under N Pdeformations if diam(S(l)) < d.
Proof. Suppose the result does not hold. Then for any realC ≥ 0 the deformation class N P contains a non-penetratingisotopy HC : O × I → R3 between of O and H(O, 1) suchthat dist(l, H(O, 1)) > C. Let C = 2 · diam(S(l)) < d, andconsider an isotopy H ∈ B leading the object at a distance
C away from the manipulator l. Since H(ι−1 (f (I)), 1) ⊂H(O, 1), we have dist(l, H(ι−1 (f (I), 1)) > diam(S(l)).
Therefore, H(ι−1 (f (I)), 1) does not intersect S(l) and hence
is not linkable to l via S(l)-avoiding augmentation. Then, by
Proposition 1, there exists t ∈ I such that H(ι−1 (f (0)), t) ∈S(l) or H(ι−1 (f (1)), t) ∈ S(l). Assume, by reversing the9orientation of f if necessary, that H(ι−1 (f (0)), t) ∈ S(l).
Then dist(H(ι−1 (f (0)), t), l) ≤ diam(S(l)). But, since thehomotopy is non-penetrating, we have dist(H(O, t), l) > d,and hence d < diam(S(l)) which leads to a contradiction.
E. Approximate caging loops
In practice, we may be interested in caging objects by two
or more caging tools such as fingers, arms or mobile robots
placed at a small distance from each other such that thesecaging tools almost form a closed loop. Consider, for example
the case of the PR2 gripper in Fig.12. While the fingers cannot
close completely, we can still utilize such configurations aslong as the distance between the fingertips is small enough.
We now formalize this using the notion of an ε-augmented
caging loop.

Fig. 12. A PR2 gripper caging a scoop by an approximate caging loop

Definition 18. Let Γ = (γ1 , γ2 , ..., γn ), γi : I → R3 , bea tuple of piecewise linear curves contained in the caging
manipulator and let and let A = (a1 , a2 , ..., an ), be a tupleof linear line segments such that ai connects ai (0) ∈ R3
to ai (1) ∈ R3 and maxi kai (0) − ai (1)k = ε. Suppose
furthermore that γi (1) = ai (0) and γi+1 (0) = ai (1) fori ∈ {1, . . . , n − 1} and γ1 (0) = an (1), so that the loopelε (Γ, A) = γ1 , a1 , γ2 , . . . , an forms a closed loop. Suppose
further that elε (Γ, A) is homotopy equivalent to a circle. Then
we call elε = elε (Γ, A) an ε augmented caging loop.

that can change their thickness only up to some threshold.
Intuitively, we can imagine this as a dense ‘core’ inside theobject, which preserves its thickness while we squeeze theobject.
Definition 19. Let O be an object of the shape O ⊂ R3 ,and let p : I → O an embedded curve in O. Assume that{x ∈ R3 : dist(x, p(I)) ≤ ε} ⊂ O for some ε ≥ 0. Then adeformation H : O × I → R3 of the object is ε−thicknesspreserving with respect to p, if for any t ∈ I we have{x ∈ R3 : dist(x, H(ι−1 (p(I)), t)) ≤ ε} ⊂ H(O, t).
We now can formulate a corollary of Proposition 1:
Corollary 1 (of Proposition 1). Let elε0 = elε (Γ, A) be an0
ε -augmented caging loop, consisting of the set of segments
Γ, representing the caging tools, and a set A of virtual
segments, connecting their endpoints. Let O ⊂ R3 be an
object, and let p : I → O an embedding into O, such that{x ∈ R3 : dist(x, p(I)) ≤ ε} ⊂ O, where ε > ε0 . Assume
that p is linkable to elε0 via S(elε0 )-avoiding augmentation, andO does not collide with the set of caging tools: O ∩ Γ = ∅.
Consider a deformation class T P of the object O, consistingof ε−thickness preserving deformations with respect to p,
non-penetrating with respect to Γ. Then for any isotopy
H ∈ T P, such that H(ι−1 (p(I)), 1) ∩ S(elε0 ) = ∅, there
exists t ∈ I for which either H(ι−1 (p(0)), t) ∈ S(elε0 ) orH(ι−1 (p(1)), t) ∈ S(elε0 ).
Proof. By Proposition 1 we know that the statement holds forthe deformation class T P 0 ⊂ T P consisting of ε−thicknesspreserving deformations with respect to p, non-penetratingwith respect to elε0 . Suppose that the statements does nothold for T P. Let H ∈ T P − T P 0 be such an isotopy.
Since H ∈ T P but H ∈/ T P 0 , there exists a momentof time t ∈ I, such that the image H(ι−1 (p(I)), t) passes
through at least one of the virtual segments in A. Supposethat y ∈ H(ι−1 (p(I)), t) ∩ A. On the one hand, note that
dist(y, Γ) ≤ ε0 , since the length of the longest segment in A
is ε0 . Hence, {x ∈ R3 : dist(x, y) ≤ ε0 } ∩ Γ 6= ∅. On theother hand, H is ε−thickness preserving with respect to p,y ∈ H(ι−1 (p(I)), t), and therefore {x ∈ R3 : dist(x, y) ≤ε} ⊂ H(O, t). Recall that ε > ε0 , and hence {x ∈ R3 :dist(x, y) ≤ ε0 } ⊂ {x ∈ R3 : dist(x, y) ≤ ε} ⊂ H(O, t). So,
H(O, t) ∩ Γ 6= ∅, which yields a contradiction.
Corollary 1 implies the sufficient conditions for caging
objects with double forks and necks features by several caging
tools.

Fig. 13. A ε-augmented caging loop.

Deformations such as squeezing might change the thicknessof the object, which is also important for caging by several
tools. When we have an ε-augmented caging loop, we impose
an additional important restriction on the class of allowed
deformations of our objects. Namely, we consider objects

Proposition 2. Let O ⊂ R3 be an object under consideration,and let elε0 be an ε0 −augmented caging loop, representing theset of manipulators. Let p, p0 : I → O be two embeddings,
linkable to elε0 via S(elε0 )-avoiding augmentations and suppose0that p, p form a double fork with parameter d > 0. Let ε > ε0and assume DF = DFε (p(I), p0 (I)) to be a subset of O.
Finally, assume O ∩ Γ = ∅.
Consider the deformation class FP aug of the object O,
such that any deformation H in FP aug is non-penetrating

10

with respect to Γ, double fork preserving with respect to DF ,and ε−thickness preserving with respect to both of p and p0 .
If diam(S(elε0 )) < d then elε0 cages the object O under
FP aug -deformations.
Proof. Suppose on the contrary that for any C ≥ 0 there exists
an isotopy H in class FP aug taking the object O at distancegreater than C away from elε0 . Let C = 2·diam(S(elε0 )). Then,the images H(ι−1 (p(I)), 1) ⊂ R3 and H(ι−1 (p0 (I)), 1) ⊂ R3
of p and p0 are separated from elε0 at a distance greaterthan diam(S(elε0 )). Therefore, the paths H(ι−1 (p(I)), 1) andH(ι−1 (p0 (I)), 1) do not intersect S(elε0 ) and therefore are
not linkable to elε0 via S(elε0 )-avoiding augmentation. From
Corollary 1 we know that there exists a first time t at which
one of the endpoints of the deforming p, p0 is in S(elε0 ). Further
reasoning precisely as in Theorem 1, we obtain the result.

from O based on their distance to the surface ∂O of the object.
We also add edges, triangles and tetrahedra as soon as allof their vertices are added. Let ds : O → R be a function
reflecting the distance to ∂O: ds(x) = dist(x, ∂O). At eachstep i of the Alg. 1, we consider a superlevel Oa+i = {x ∈ O :ds(x) ≥ ai }, where the parameter ai is increased at each step:
maxx∈O ds(x) = a0 > a1 > a2 .. > an = 0. As a result, we
obtain a nested family of superlevel sets, called a filtration:
Oa+0 ⊂ Oa+1 ⊂ Oa+2 ⊂ .. ⊂ Oa+n = O.

Let us now consider the objects with neck feature. Note that
we do not have to impose any additional restrictions on the
deformation class N P from Theorem 2, since any deformation
which is neck preserving with respect to some Nε,d (f (I)) is
obviously ε-thickness preserving with respect to f . Therefore,
the statement of Theorem 1 holds for any ε0 -augmented caging
loop, provided ε0 < ε, where ε is the second neck’s parameter.
Fig. 14. Superlevels of the function reflecting the distance to the boundary

VI. A LGORITHMIC IMPLEMENTATIONIn this section, we provide algorithms for computing andverifying caging configurations. Our approach analyses theshape of the object and extracts double forks and necks
contained in it. Since a neck feature can be considered asa special but important case of a double fork, which provides
us more freedom in the choice of a manipulator, we start theshape analysis of the object with searching for necks in it. If nonecks are detected, we search for double forks. We furthermore
generate caging loops using the extracted information andpresent applications with a PR2 robot. Finally, we run our
verification algorithm on the synthesized configurations toprove that the resulting configurations are valid cages.
In this section, we assume that the object’s shape is represented as a mesh O. The difference between the object O andits shape O is important for theoretical reasoning, as it allows
us to consider deformations of the object. However, we do notmodel deformations from the algorithmic point of view: westart with the initial shape of the object and analyse its features,
assuming they are preserved by the possible deformations.
Hence, in this section we do not distinguish between the object
and its shape. Mathematically, this means that O = O ⊂ R3
throughout this section.
A. ‘Neck’ recognition
Let us discuss the computation of neck features. A generalapproach to determine necks has been introduced in [11] basedon the concept of persistent homology (see [10]). Here, we
describe a simplified approach that is applicable in our setting.
Let O be a tetrahedral mesh, representing the object. If we are
given a surface triangle mesh, it can be tetrahedralized at apreprocessing stage, for example with the help of Tetgen([28]).
We start with an empty set and then incrementally add vertices

In this process, the number of connected component in thefiltration changes: new components appear, while the others
merge. In particular, we are interested in those points, after
the addition of which different connected components in thefiltration Oa+i merge. Let us illustrate the example in Fig. 14,
where we depict two different superlevel sets, corresponding
to filtration values ai > aj . The superlevel set Oa+i consists of
two disjoint components and is depicted in blue. It is a subsetof Oa+j , which is connected and depicted in yellow on theright side of the figure. A path f depicted in black connects
the disjoint components of Oa+i through Oa+j . Note that the
distance from f to the boundary of the object is not less thanaj , and the distance from its endpoints to the boundary is
greater or equal than ai . Therefore, we can conclude that theshape under consideration contains a neck Naj ,ai (f ).
Let us now consider our technique in detail. Alg.1 computes
necks with parameter d, given a tetrahedral mesh O and aparameter d. A mesh O consists of four sets: V , E, F and T ,representing vertices, edges, faces and tetrahedra respectively.
The subset ∂O ⊂ O contains those vertices which are locatedat the boundary of the object. For each vertex, edge, face andtetrahedron we store a binary flag which has value ‘True’ if theobject is located at the boundary ∂O, and ‘False’ otherwise.
We represent a neck as a path f inside the object O suchthat its endpoints are located at a distance d (or greater) fromthe boundary ∂O of the object, while the distance from it
to the path f itself is not less than ε. We therefore store apath as a list of edges from O as well as the parameters dand ε for each neck. At each step, we decrease a and add
to the filtration Oa+ points from O located at a distance notless than a to the surface ∂O. Once both of the endpointsof an edge are in the filtration, we add this edge to thefiltration as well. Analogously, we add faces (tetrahedra) once

11

all of their edges (faces) are in the filtration. We do this bymeans of function Update-Filtration. Once all vertices, edges,
triangles and tetrahedra are added, we compute the connectedcomponents of the resulting mesh. At each moment of time,each connected component has its unique ID number. For eachvertex, we store the ID number of the connected component
containing it in the array ConComp. ID of a connectedcomponent is an integer number. When we add a new pointv to the filtration, we consider all the vertices adjacent to it
in O. If none of them is in the filtration, then v forms a newconnected component in Oa+ . We let ConComp[v] be equal
to the minimal integer number which has not yet been used todenote any connected component. Otherwise, we add v to an
already existing connected component by letting ConComp[v]to be equal to the ID of the corresponding component. If in
the filtration there are more than one connected component
containing vertices adjacent to v in O, then this meansthat adding v results in the merging of these components.
Assume that C1 , C2 , .., Cm are the connected components inthe filtration containing at least one vertex, adjacent to v in O.
Then, once we add v, we modify ConComp so that all thevertices from C1 , C2 , .., Cm and v have the same value in it.
For this purpose, we select the component with the minimal
ID number among the components C1 , C2 , .., Cm , and assign
ConComp[u] to be equal to it for all the vertices u fromC1 ∪ C2 ∪ .. ∪ Cm ∪ {v}. This mechanism is implemented in
the function Merge-Comp.
Suppose C1 , C2 ⊂ Oa+ are two connected components,
merged into one after the addition of a point v together withthe corresponding edges, faces and tetrahedra to the filtration.
Let x1 = arg maxx∈C1 ds(x), x2 = argmaxx∈C2 ds(x). We
can determine a path f connecting x1 and x2 in Oa+ . This
path is computed by Find-Path, resulting in a neck, whose
first parameter is equal to min{dist(x1 , ∂O), dist(x2 , ∂O)}.
The values of their second parameter, reflecting the thicknessof the object, may vary and are not computed at this stage.
Instead, we compute them further if necessary.

Algorithm 1: Compute-Necks(mesh O, mesh ∂O, float d)
input : a tetrahedral mesh O = (V, E, F, T );a surface mesh representing the boundary of the object ∂O;neck parameter doutput: a set of necks with parameter d
nextID ← 0
Nd ← ∅
foreach v ∈ O do
D[v] ← Compute-Dist-To-Surface(v, O)
end
V ← Sort-Vertices-by-Distance(V , D)a =← Max-Element(D)while a > 0 do
N ewV ert ← Vertices-at-Distance(V , d, D)
Oa+ ← Update-Filtration(O, Oa+ , N ewV ert)
foreach v ∈ N ewV ert do
ConComp[v] ← ∞size ← 0f ←∅foreach u ∈ Adjacent(v) do
if u ∈ Oa+ and ConComp[u] 6= ConComp[v] thenif ConComp[v] 6= ∞ thenuCentre ← ConComCentre(V , ConComp,u)vCentre ← ConComCentre(V , ConComp,v)
size ← Max(size, Min(D[uCentre],
D[vCentre]))Merge-Comp(u, v, ConComp)if size ≥ d and f = ∅ thenf ← Find-Path(Oa+ , uCentre, vCentre)
end
end
else
ConComp[v] ← ConComp[u]
end
end
end
if ConComp[v] = ∞ then
ConComp[v] ← nextID
nextID ← nextID + 1
end
if size ≥ d thenNd = Nd ∪ f
endenda ← Next-Distance-To-Surface(O, Oa+ , D, a)end
return Nd

B. ‘Double fork’ recognition
We start by generating a skeleton G = (V, E) of an object
using the algorithm of [7]. This algorithm generates a skeleton
as a subset of the medial axis. More precisely, the authors
consider balls of maximal radius defined by the medial axis.
These balls touch the object’s surface and the authors define
the medial geodesic function (MGF) to be the length of theshortest surface path connecting these points. The skeleton isthen defined as the singular set of MGF. Unlike the medialaxis, which might be a two-dimensional surface, this skeleton
is always one-dimensional and represented as a graph. The
MGF values are provided for each edge of the skeleton graphas a part of the output of their software and provide size
information about the object.
We denote the MGF value by geod(e) for e ∈ E.
We also extend this function to vertices: geod(v) =mini∈{1,..,n} geod(ei ), where {e1 , .., en } ⊂ E is the set ofedges incident to v ∈ V . In our current implementation, we
assume the skeleton graph G to be a tree. In the future, weplan to consider more general skeletons as well, for example,
by working with spanning trees.
Our goal is to find double forks in the skeleton graph.
We are interested in double forks with a parameter greaterthan or equal to some predefined threshold d. We stop thealgorithm once a double fork with a required parameter isfound. Otherwise, the algorithm terminates after considering
all the promising sets of vertices of the graph.
All the graphs in this section are assumed to be undirected.
For convenience, we introduce a special notation for paths ingraphs. Let p : u → v denote a path between the vertices uand v in a graph. We will also use the notation (u, v) for anedge between vertices u and v.
Definition 20. Consider a skeleton as a graph G = (V, E).
Let Gdv ⊂ G be the subgraph, defined by Gdv = ({u ∈ V :dist(u, v) ≥ d}, {e ∈ E : dist(e, v) ≥ d}) for some v ∈ V
and d > 0. Then the subgraph Gdv is called d-separated fromv.

12

In the above definition, dist(., .) denotes the Euclidean
distance in R3 . Intuitively, Gdv is just a subgraph of G separated
from v by a distance not less than d. Note that Gdv is likely
do consist of several connected components.
Recall the definition of a double fork. It imposes two
conditions on the distances between the parts of the double
fork: dist(p, {u0 , v 0 }) > d and dist(p0 , {u, v}) > d. These
conditions can be rewritten as p ⊂ Gdu0 ∩Gdv0 and p0 ⊂ Gdu ∩Gdv .
Consequently, the pairs {u, v} and {u0 , v 0 } are also separated
from each other:u, v ∈ Gdu0 ∩ Gdv0 ,u0 , v 0 ∈ Gdu ∩ Gdv .

Moreover, any double fork is obviously connected due tocondition p ∩ p0 6= ∅. From this we conclude that the centre Cof a double fork must lie at a distance not less than d from all
the vertices u, v, u0 , v 0 , and therefore we have the following
condition:
C ⊂ Gdu ∩ Gdv ∩ Gdu0 ∩ Gdv0 6= ∅These observations give us a way to compute double forks
in G, see Alg. 2.
Let d be a threshold determining the minimal acceptableparameter of a double fork. As a preprocessing stage, we
compute a real valued symmetric |V | × |V | matrix D, containing pairwise distances between vertices in G: Dvi ,vj =dist(vi , vj ) for each pair (vi , vj ) ∈ V × V . For this purpose
we use the function Distance.
The key idea of this algorithm is to find a set of vertices{u, v, u0 , v 0 } satisfying all the conditions to form a double
fork. In the first step of our algorithm, we are searching forvertices that might be located at the centre of some double
fork. We enumerate all the vertices in the graph and consider
those which potentially could be located at a centre of a double
fork. In order to speed up the computations, we consider only
those vertices which are located at a distance not greater than
0.2RG , where RG = dist(x, M ) and M is the centre ofmass of the set V ⊂ R3 . This selection is performed by thefunction Vert-at-Dist, and the centre of mass is the output of
the corresponding function Centre-of-Mass. Then, for eachselected vertex a we enumerate all the vertices in the graph ata distance not less than d to a, and consider them as candidates
for the first vertex of the double fork – u. At this step, we build
a path pu : a → u in G. The function Find-Path is used forthis purpose. After that, for each pair (a, u), we enumerate all
the vertices at a distance greater or equal than d to pu andconsider them as promising candidates for u0 . We search fora path pu0 : a → u0 in Gdu . If there is no such a path, we
consider the next candidate for u0 . Once pu0 is found, having
a triple (a, u, u0 ), we enumerate all the vertices in G which
are located at a distance greater or equal than d to pu0 , andconsider them as candidates for being v. We search for a path
pv : a → v in Gdu0 . Finally, having {a, u, u0 , v} we enumerate
the vertices separated from pu and pv at least at a distanced and choose v 0 among them. Now u, v, u0 , v 0 together withp = pu ∪ pv and p0 = pu0 ∪ pv0 form a double fork.
Let us now discuss in detail how the above used functions
are implemented.

Algorithm 2: Compute-Double-Fork(mesh O, graph G =(V, E), float d)
input : a mesh O, representing the object;a skeleton G = (V, E);
the lowest acceptable double fork parameter doutput: a fork of parameter dforeach u ∈ V do
foreach v ∈ V do
Du,v ← Distance(u, v)
endend
M ← Centre-of-Mass(G)R←0foreach v ∈ V do
if Dv,M > R thenR ← Dv,M
end
end
foreach a ∈ V do
if dist (a, M ) ≤ 0.2R thenU C ← Vert-at-Dist(V , {a}, d)foreach u ∈ U C dopu ← Construct-Path(G, a, u)
if pu = ∅ thencontinueend
U 0 C ← Vert-at-Dist(V , pu , d)foreach u0 ∈ U 0 C do
pu0 ← Construct-Path(G, a, u0 )if pu0 = ∅ thencontinueend
V C ← Vert-at-Dist(V , pu0 , d)foreach v ∈ V C do
pv ← Construct-Path(G, a, v)
if pv = ∅ thencontinueend
0
V C ← Vert-at-Dist(V , pu ∪ pv , d)foreach v 0 ∈ V 0 C do
pv0 ← Construct-Path(G, a, v 0 )if pv0 = ∅ thencontinueend
p = pu ∪ pv
p0 = pu0 ∪ pv0
return {u, v, u0 , v 0 }, p ∪ p0
end
end
end
end
end
end
return ∅Centre-of-Mass(Graph G)
Given a geometric graph G = (V, E), this function
computes a centre of mass of V ⊂ R3 .
• Vert-at-Dist(Set S, Set D, Float d)This function returns a subset S 0 of the set S ⊂ R3 , suchthat each point from S 0 lies at a distance greater thanor equal to the parameter d ∈ R to any point of the set
D ⊂ R3 .
• Find-Path(Graph G, Vertex u, Vertex v)
The goal of this function is to find a path between thevertices u and v in the undirected graph G. For thispurpose, we run Breadth-first search in G starting at u,
and then recover the path p : u → v once v is reached.
If we cannot reach v from u, the function returns empty

•

13

path.
C. Caging loop synthesis
Let us now describe an approach towards constructing
caging loops. We assume that we have already analysed theshape of the object O, and have found either a neck formed
by a path p, or a double fork formed by a pair of paths (p, p0 ).
In our algorithm, we consider the edges contained in theobject’s surface ∂O as a graph G. The output of the algorithm
is given by a piecewise linear loop l in this graph. In order
to construct a loop, we need a starting point M inside O.
Intuitively, M is the point around which we construct a loop,
and it is located at the centre of a narrow part of the object.
Our algorithm aims to construct a short loop as follows.
Formally, assume we have an object with a double fork(p, p0 ). Let M ∈ p ∩ p0 be a point, such that M =arg minx∈p∩p0 (geod(x)). In the case of a neck, let M =arg minx∈p (ds(x)). In order to unify our notation for bothcases Algorithms 3, 4, 5, 7 accept as input both p and p0 ,however, we set p0 = ∅ in case of a neck features.
We
start
by
selectingavertexv0=
arg minv∈∂O dist(v, M ). We will explore the verticesof ∂O in the increasing order of their geodesic distance to v0 .
Here we approximate the geodesic distance by considering
the shortest edge paths, determined by means of the Dijkstra’salgorithm, as explained below. Let the set V ertices containthe vertices from ∂O. We gradually add explored vertices
from V ertices to the set M arked. So, at the initial stage
M arked = ∅. We will also need a graph Gmarked consistingof the vertices from the set M arked, and the edges from∂O such that both their endpoints are in M arked. Initially,
Gmarked is empty.
For each vertex v in G, we need their distance to the initialpoint v0 . By distance here we mean an approximation of thegeodesic distance – the geometric length of the minimal edge
path from v0 to v. In addition, for each vertex v we will store
its immediate ancestor in the shortest path from v0 to v. For example, assume that we have a path path = {v0 , v1 , ..., vn , v}.
The length of this path is the sum of the geometric length of
its edges, and the immediate ancestor of v in this path is vn .
This information will be stored in the arrays Distance andAncestor, where Ancestor[v] denotes the immediate ancestorof the vertex v in the shortest path from v0 , and Distance[v]is the length of this path. We run Dijkstra’s algorithm in G
starting from the point v0 , in order to compute the arrays
Distance and Ancestor.
For convenience, we sort the vertices in V ertices in an
increasing order of their distance from v0 by running SortVertices-by-Distance. We explore the vertices from V ertices
in this order, and add them to the set M arked. When two
adjacent vertices are added to M arked, we add the edge
between them to Gmarked . In this process, the graph Gmarked
grows on the surface of the object, and tends to cover the entire
surface ∂O (i.e., to become equal to G).
Although in our algorithm we consider only a 1-skeletonof ∂O and therefore do not work with its faces, in Fig. 15
we visualize in purple the faces whose edges and vertices arein Gmarked . Intuitively, the process of adding vertices andedges to Gmarked resembles a gradual growth of a surface
patch on the mesh, see Fig. 15. Since the object is bounded,
the boundary vertices of this ‘patch’ are becoming closer andcloser to each other, and at some moment merge. In Fig. 15, we
illustrate this merging for the neck of the bear mesh. When thismerging occurs, the resulting closed edge path forms a shortloop around the narrow part of the object which we return asa caging loop candidate in Alg.3.
Algorithm 3: Caging-Loop-Generation(mesh O, path p,path p0 )input : a mesh O, representing the object ;two paths p and p0 inside O, representing the double fork or neck
output: a caging loop l
if p0 = ∅ then// If p0 = ∅, then we deal with a neck formed by p
M ← arg minx∈p (ds(x))
endelse// If p0 6= ∅, then we deal with a double fork formed by (p, p0 )M ← arg minx∈p∩p0 (geod(x))
endVertices ← {v : v ∈ ∂O}
Marked ← ∅v0 ← arg minv∈∂O (dist(v, M ))G ← G(V = Vertices, E = {e = (v1 , v2 ) : v1 , v2 ∈ V, e ∈ ∂O})
Gmarked ← G(V = ∅, E = ∅)Distance, Ancestor ← Dijkstra(G, v0 )Sort-Vertices-by-Distance(Vertices, Distance)
while Vertices 6= Marked dov = Vertices.next()
foreach u ∈ Adjacent(v) do
if u ∈ Marked thenpath ← Find-Path(Gmarked , u, Ancestor[v])if Length(path) > deg(v) − 1 thenl ← (v, u)∪path ∪(Ancestor[v], v)
if Verify-Caging-Loop(O, p, p0 , l) thenreturn l
end
end
end
end
Marked.push(v)Add-Vertex-To-Graph(Gmarked , (v))
foreach u ∈ Adjacent(v) do
if u ∈ Marked then
Add-Edge-To-Graph(Gmarked , (v, u))
end
end
end
return ∅Fig. 15. Illustration of Alg.3. Currently explored vertices and edges are
depicted in black; faces whose edges and vertices are black, are depicted
in purple and a resulting caging loop is shown in red.

14

At each step, we consider a vertex v ∈ V ertices. We search
for its immediate neighbours in G, and consider those of themwhich are already in M arked. Let u ∈ M arked be one ofthese neighbours. First of all, we check whether we can obtaina caging loop already at this step. In order to do this, wesearch for the edge-wise shortest path in Gmarked between u
and Ancestor[v], see Fig. 15 for the intuition. We search forthis path by running Find-Path, which is the implementationof the breadth-first path search between two points in a given
graph. If the length of this path is long enough (longer thandeg(v) − 1 edges, where deg(v) is the degree of the current
vertex v), then we suppose that this path together with theedges (Ancestor[v], v) and (v, u) forms a loop. The reason
why we want the path to be longer than deg(v) − 1 is that weneed to eliminate a priori degenerate loops consisting only of
the neighbours of the vertex v. We then run our verification
algorithm in order to check whether this loop is a valid cage. If
not, we continue the process. Namely, we mark v and append
all the edges connecting it to vertices from M arked.
Compute-Dist-To-Surface(Vertex v, Mesh O) In thisfunction, we enumerate all the faces in the boundary ∂Oof O, and compute the distance between each face andthe vertex v. The distance to the surface ∂O is given by
the minimum of these distances.
• Sort-Vertices-by-Distance(Vertices V , Array D) Thisfunction returns an array containing vertices in a decreasing order of their distances to the surface.
• Vertices-at-Distance(Vertices V , Float d, Array D)
This functions selects vertices from V located at a
distance d to the boundary ∂O. The distances are stored
in the array D.
• Update-Filtration(MeshO, Mesh Oa+ , Array
N ewV ert) This functions adds the vertices fromthe array N ewV ert to the filtration Oa+ . It also adds thecorresponding edges, faces and tetrahedra from O: eachof them is added once all its vertices are in Oa+ .
• ConComCentre(Vertices V , Array ConComp, Integeru) Given an ID number ConComp[u] of a connectedcomponent, this function returns a point belonging to it,such that its distance to the boundary is the largest in thiscomponent.
• Find-Path(Mesh
Oa+ , Integer uCentre, Integer
vCentre) This function computes a path betweenuCentre and vCentre in Oa+ using depth-first search.
+• Next-Distance-To-Surface(Mesh O, Mesh Oa , Array
D, Float a) This function returns distance to the object’s
boundary from the closest vertex in O − Oa+ . If O = Oa+ ,it returns zero.
•

We have implemented the algorithms for double forks andnecks detection in Python, see Fig. 16 for the examples. We
utilized Python MayaVi module for the visualization of ourmeshes. The meshes are taken from [1], [5] and [27]. The
computation time for the given objects on an Intel i7 CPU
laptop is presented in tables under the figure. In the caseof the screen and the table, we did not find any appropriate
neck features. Instead, for these objects we managed to finddouble forks. The drawback of the skeletonization technique

we currently use [7] is that it requires meshes of a rather highresolution. For this reason, we consider the screen and thetable models in a higher resolution when computing double
forks. In contrast, for the neck detection algorithm we use
simplified meshes with the lower number of vertices, which
speeds up the computation. Both necks and double forks
detection algorithms require some preprocessing: in the case ofnecks we tetrahedralize the mesh, while in the case of double
forks we extract a skeleton from the object. In both cases, werely on already existing software: [28] for tetrahedralizationand [7] for skeleton extraction. Both of these techniques arerather efficient, but potentially can be replaced by alternatives.
D. Synthesis of caging configurations for PR2
Since the purpose of this work is to introduce a new
representation of objects, suitable for caging, we do not focus
on motion planning and control here, however we now discuss two simple approaches to compute caging configurations
which we evaluate with a simulated PR2 robot. Consider aPR2 manipulator, and let the vectors Vd and Vh indicated inFig. 17 define its orientation.
Our first approach is described in Alg. 4. Here, a precomputed approximate caging loop is fit to the PR2 manipulator(s)as follows: Let la denote the approximate caging loop, consisting of vertices {v1 , v2 , .., vn = v1 } ⊂ R3 and the edges
between them, such that each vertex has exactly two adjacentvertices. As a preparatory step, we ensure that the loop is
constructed in such a way that any triple {vi−1 , vi , vi+1 } ⊂ ladoes not consist of three collinear points - this can be achievedfor example by means of an infinitesimal perturbation of thevertices.
First, we compute a point C, which is a centre of mass of
all the vertices in the loop. Then we enumerate the vertices
in la , and for each v ∈ la , we take its immediate neighbours,vi and vj . The triple {vi , v, vj } defines a plane πv . Consider
a projection πv (C) of C onto πv , and let V1 = πv (C) − v.
Let V2 ⊥ V1 be another vector in πv , see Fig. 18. We place
the manipulator at a distance from the loop and in such a
way that Vd is collinear to V1 , and Vh is collinear to V2 . We
then linearly approach the object by moving the robot hand
direction V1 towards the object.
Once collision occurs, we close the fingers until collisionand extract a new caging loop lh from the resulting hand configuration, and run our verification algorithm. This approach
focuses on narrow parts corresponding to our initial caging
loop candidate la . Note that due to collisions the hand might
however not be able to reach a final caging configuration for
any of these approach directions along the loop - in future weplan to focus on motion planning algorithms for this purpose.
A second simple caging synthesis algorithm is described in
Alg. 5. Here, we do not compute an initial caging loop la but
instead, we compute a simple graph Gc , suitable for caging,
and attempt to close the PR2’s fingers around it. In the caseof neck, we let Gc = p, where p is the path forming the neckwhile in the case of a fork formed by the paths p and p0 , welet Gc = p ∩ p0 .
For any e ∈ Gc , we perform the procedure described in
Alg. 6. Let M be a centre of mass of the segment e. Consider

15

Fig. 16. In the first row, the original meshes are presented. In the second row, shape features are extracted. The first three columns depict objects for which
we extracted neck features, while the last two columns show objects with double fork features. We show corresponding filtrations for the first three columns inthe second row. The connected components depicted in blue merge to the larger components depicted in yellow. The paths, connecting the blue components,
are depicted in black. In the last two columns the objects are depicted together with the double forks in the second column. The third row displays resulting
caging loops.
model
bust
queen
bear
table
screennumber of vert. in the tetr. mesh
12862
5990
12939
1661
21917

model
table
screennumber of vert. in the skeleton
1148
1584

number of vert. on the surface
7047
3589
7106
1464
11109
number of vert. in the mesh
10650
16218

Fig. 17. The vectors Vd and Vh define the direction of the hand. The
curve α together with its augmentation a forms an augmented caging loop,
representing the manipulator.

necks detection
1524 ms
682 ms2472 ms
1901 ms
5317 ms

double forks detection
1776 ms
3799 msloop(s) construction
1203 ms
297 ms1458 ms––loop(s) construction
748 ms613 msFig. 18. The approximate caging loop la and the vectors V1 and V2 .
The former is pointing towards the centre of the loop, while the latter isperpendicular to it.

the plane µ orthogonal to e and passing through M . We sample
a random vector V1 in µ with respect to uniform distribution,

16

Algorithm 4: Loop-Based-Caging-Generation(mesh O,
path p, path p0 , loop la )Algorithm 6: Cage-Around-Edge(mesh O, path p, path p0 ,edge e)input : a triangle mesh O, representing the object;
two paths p and p0 in O, representing the double fork or neck;an approximate caging loop la ⊂ ∂O
output: a caging configuration cf

input : a triangle mesh O, representing the object ;two paths p and p0 in O, representing the double fork or neck ;an edge e, around which the object should be caged
output: a caging configuration cf

C ← Centre-Of-Mass(la )foreach v ∈ la dovi , vj ← Adjacent-Vertices(v, la )πv ← Plane(v, vi , vj )πv (C) ← Project-Onto-Plane(πv , C)
V1 ← (πv (C) − v)
V2 ← Compute-Orthogonal-Vector(πv , V1 , v)
EEF-position← Collision-Free-EEF-Position (V1 , V2 , O)
c0 ← Solve-IK(EEF-position)
cf ← Move-Until-Collision(c0 , V1 , O)
cf ← Close-Gripper-Until-Collision()l ← Extract-Caging-Loop(cf )if Verify-Caging-Loop(O, p, p0 , l) thenreturn cf
end
end
return ∅M ← Middle-of-Segment(e)i←0while i < 50 doi←i+1V1 ← Generate-Random-Orthogonal-Vector(~e, M )V2 ← ~e × V1
EEF-position← Collision-Free-EEF-Position (V1 , V2 , O)
c0 ← Solve-IK(EEF-position)
cf ← Move-Until-Collision(c0 , V1 , O)
cf ← Close-Gripper-Until-Collision()l ← Extract-Caging-Loop(cf )if Verify-Caging-Loop(O, p, p0 , l) thenreturn cf
end
end
return ∅Algorithm 5: Region-Based-Caging-Generation(mesh O,
path p, path p0 )input : a triangle mesh O, representing the object ;two paths p and p0 in O, representing the double fork or neck
output: a caging configuration cf
Gc ← ∅ // Gc is a 1D cageable subset of O
if p0 = ∅ then// If p0 = ∅, then we deal with a neck formed by p
Gc ← pend
else// If p0 6= ∅, then we deal with a double fork formed by (p, p0 )Gc ← p ∩ p0
end
foreach e ∈ p ∪ p0 do
w1 , w2 ← Incident(e)if (w1 ∈ p ∩ p0 and w2 ∈/ p ∩ p0 ) or (w1 ∈/ p ∩ p0 andw2 ∈ p ∩ p0 ) thenGc ← Gc ∪ {e}endendforeach e ∈ Gc do
cf ← Cage-Around-Edge(O, p, p0 , e)if cf 6= ∅ thenreturn cf
end
end
return ∅and compute another vector V2 in µ, orthogonal to V1 . Then,
we place the robot’s hand into a collision free configurationsuch that Vd is collinear to V1 , Vh is collinear to V2 , and theend effector is located at a small distance from M . We thenmove the hand towards M until collision and close the fingers.
Finally, we extract the caging loop representation from the
manipulator’s configuration, and run our verification algorithm
in order to check whether our configuration is a cage. If theverification fails, we sample another random vector V1 andrepeat the procedure. If we are not able to construct a caging
configuration for the edge e after repeating this procedure 50
times, we consider the next edge from Gc .
If the object is big enough, we can also use two hands of thePR2 as caging tools. In this case, each of the hands approaches

the object, as described above. The only restriction we impose
is that the angle between the vectors, defining the direction
3π
and π. This is to ensureof each hand, must be between
4
that the hands are placed roughly in opposition to each other.
Since now we are dealing with two independent manipulators,
a single augmented caging loop runs through both hands, as
described in the previous section. We extract the caging loop
representation and run the verification algorithm.
We have implemented our cage generation algorithms using
OpenRave. They are simple, as in this paper we only want toillustrate how one can cage an object given its shape featuresand precomputed examples of caging loops. Here we provide
some illustrations of the successful output, Fig. 19. A study on
how to choose a caging generation algorithm (the loop-basedor the region-based) and how many grippers to use for eachparticular object is beyond the scope of this paper. We planto get back to this problem and incorporate it with motion
planning in the near future. When the position of the robot
base and the object are chosen properly, and objects features
are computed, it takes 10-15 seconds at the average to computeand verify a caging configuration. In the case of a bear mesh
we have generated the cage based on a previously computed
approximate caging loop (see Fig. 16). For the shown monitor
mesh, this approach however failed due to collisions of therobot hand as the upper part of the monitor prevents therobot hand from approaching it. Our second approach however
returns a cage utilizing both of the PR2’s hands. In the caseof a wine glass, we computed a neck and both of our caging
methods described above succeeded. The figure displays thecaging configuration of the PR2 hand computed with the latter
algorithm based on Gc .
E. Verification of a given caging configuration
Let us now discuss how to verify whether a configuration
constructed by our algorithm is a valid cage. Theorems 1, 2
provide us with a constructive way to perform such a verification. Indeed, assume that we are given an object O ⊂ R3 ,

17

Fig. 19. In the first case, the caging configuration was generated based on the loop around the neck of the bear. At the second figure, the cage was generated
based on a neck representation of the object (second approach). In the third case, we did not manage to fit the precomputed approximate caging loop due tothe obstacle presence. The caging configuration was generated based on the double fork representation (second approach).

Algorithm 7: Verify-Caging-Loop(mesh O, path p, path
p0 , loop l)
input : a tetrahedral mesh O, representing the object;paths p, p0 ∈ R3 ;a loop l, representing a rigid manipulator
output: ‘l is a valid cage’ – True or Undecided
ε ← Get-Loop-Augmentation(l)Conv ← Convex-Hull(l)paug ← Construct-Augmentation(p, Conv)
if no augmentation found thenreturn Undecidedend
if p0 = ∅ then// If p0 = ∅, then we deal with a neck formed by pif ε ≤ minx∈p (ds(x)) thenif lk(p, paug ) 6= 0 thenreturn True
end
else
return Undecided
end
end
else
return Undecided
end
end
else
// If p0 6= ∅, then we deal with a double fork formed by (p, p0 )p0aug ← Construct-Augmentation(p0 , Conv)
if no augmentation found thenreturn Undecided
end
if ε ≤ minx∈(p∪p0 ) (ds(x)) thenif lk(p, paug ) 6= 0 and lk(p0 , p0aug ) 6= 0 thenreturn True
end
else
return Undecided
end
end
else
return Undecided
end
end

and a piecewise-linear closed curve l, representing the caging
tool. Our goal is to check whether l bounds the mobility ofO.
As input to our verification algorithm, we consider l,together with some paths p, p0 ⊂ O (allowing one of them

to be empty in case of a neck feature). Alg.7 then determines
if p is linkable to l via an S(l)−avoiding augmentation, where
we consider S(l) = Conv(l) To do so, we compute S(l)and an augmentation paug (and similarly p0aug , in the caseof a double fork), connecting the endpoints of p (and p0 )through the complement of S(l) by means of ConstructAugmentation(Path f , Set Conv(l)). We then compute thelinking number lk(p, paug ) and test if ε ≤ minx∈p (ds(x))(neck case) or ε ≤ minx∈(p∪p0 ) (ds(x)) (double fork case) toapply Theorems 2 and 1 respectively.
In detail, Construct-Augmentation(Path f , Set Conv(l))
constructs a path f 0 , connecting the endpoints u, v of f via
the complement of Conv(l) and returns failure if u or v
lies in Conv(l). We linearly rescale Conv(l) by a factor of
2 and call the resulting set M , so that Conv(l) is strictly
contained in M . We then determine closest vertices u0 =arg minx∈∂M (dist(x, u)) and v 0 = arg minx∈∂M (dist(x, v))
and return an edge path p from u0 to v 0 through the edgesof ∂M using breadth-first search on the graph of edgesof ∂M . The function then returns the concatenated path
f 0 = (u, u0 ) ∪ p ∪ (v 0 , v).

VII. C ONCLUSIONS AND FUTURE WORK
We proposed a methodology for the synthesis and provably
correct verification of caging grasps on a class of 3D objects
that exhibit geometric features which we call necks and double
forks. We utilized the classical notion of the linking number
from algebraic topology as the basis for proving the sufficientconditions for caging grasps and have proposed algorithms tocompute necks, double forks as well as resulting caging loops
and caging configurations for a PR2 manipulator. In future
work, we are planning to integrate motion planning and toprovide an extensive experimental evaluation of the techniqueon natural objects and different caging tools. Apart from this,we plan to try different skeletonization techniques to extract
double forks. In particular, we want to try approaches allowing
to extract a skeleton from an imperfect point cloud. We arealso planning to investigate further classes of features suitablefor caging 3D objects.

18

R EFERENCES[1] INRIA gamma research group repository. https://www.rocq.inria.fr/
gamma/gamma/download/download.php. Accessed: 2015-11-09.
[2] A. S. Besicovitch. A net to hold a sphere. The Mathematical Gazette,pages 106–107, 1957.
[3] A. Bicchi and V. Kumar. Robotic grasping and contact: A review. In
ICRA, pages 348–353. Citeseer, 2000.
[4] Jeannette Bohg, Aythami Morales, Tamim Asfour, and Danica Kragic.
Data-driven grasp synthesisa survey. Robotics, IEEE Transactions on,
30(2):289–309, 2014.
[5] X. Chen, A. Golovinskiy, and T. Funkhouser. A benchmark for 3D
mesh segmentation. ACM Transactions on Graphics (Proc. SIGGRAPH),
28(3), August 2009.
[6] R. Deimel and O. Brock. A novel type of compliant, underactuatedrobotic hand for dexterous grasping. In Proceedings of Robotics: Scienceand Systems, Berkeley, USA, July 2014.
[7] T. K. Dey and J. Sun. Defining and computing curve-skeletons withmedial geodesic function. In Symposium on Geometry Processing, pages
143–152, 2006.
[8] R. Diankov. Automated Construction of Robotic Manipulation Programs. PhD thesis, Carnegie Mellon University, Robotics Institute,
August 2010.
[9] R. Diankov, S. S. Srinivasa, D. Ferguson, and J. Kuffner. Manipulation
planning with caging grasps. In Humanoid Robots, 2008. Humanoids
2008. 8th IEEE-RAS International Conference on, pages 285–292. IEEE,
2008.
[10] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete and Computational Geometry,
28(4):511–533, 2002.
[11] X. Feng and Y. Tong. Choking loops on surfaces. IEEE Trans. Vis.
Comput. Graph., 19(8):1298–1306, 2013.
[12] K. Gopalakrishnan and K. Goldberg. D-space and deform closure grasps
of deformable parts. The International Journal of Robotics Research,
24(11):899–910, 2005.
[13] A. Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002.
[14] K. Klenin and J. Langowski. Computation of writhe in modeling ofsupercoiled DNA. Biopolymers, 54:307–317, 2000.
[15] W. Kuperberg. Problems on polytopes and convex sets. In DIMACS
Workshop on polytopes, pages 584–589, 1990.
[16] Jeffrey Mahler, Florian T Pokorny, Brian Hou, Melrose Roderick,Michael Laskey, Mathieu Aubry, Kai Kohlhoff, Torsten Kroeger, James
Kuffner, and Ken Goldberg. Dex-net 1.0: A cloud-based network of 3d
objects for robust grasp planning using a multi-armed bandit model withcorrelated rewards. 2016.
[17] S. Makita and Y. Maeda. 3d multifingered caging: Basic formulationand planning. In Intelligent Robots and Systems, 2008. IROS 2008.
IEEE/RSJ International Conference on, pages 2697–2702. IEEE, 2008.
[18] S. Makita, K. Okita, and Y. Maeda. 3d two-fingered caging for two typesof objects: sufficient conditions and planning. International Journal of
Mechatronics and Automation, 3(4):263–277, 2013.
[19] R. M. Murray, Z. Li, and S. Sastry. A mathematical introduction to
robotic manipulation. CRC press, 1994.
[20] P. Pipattanasomporn and A. Sudsang. Two-finger caging of concave
polygon. In Robotics and Automation, 2006. ICRA 2006. Proceedings
2006 IEEE International Conference on, pages 2137–2142. IEEE, 2006.
[21] P. Pipattanasomporn and A. Sudsang. Two-finger caging of nonconvex
polytopes. Robotics, IEEE Transactions on, 27(2):324–333, 2011.
[22] F. T. Pokorny, J. A. Stork, and D. Kragic. Grasping objects with holes: A
topological approach. In Robotics and Automation (ICRA), 2013 IEEE
International Conference on, pages 1100–1107. IEEE, 2013.
[23] E. Rimon and A. Blake. Caging planar bodies by one-parameter
two-fingered gripping systems. The International Journal of Robotics
Research, 18(3):299–318, 1999.
[24] A. Rodriguez, M. T. Mason, and S. Ferry. From caging to grasping.
The International Journal of Robotics Research, pages 886–900, 2012.
[25] D. Rolfsen. Knots and links, volume 346. American Mathematical Soc.,
1976.
[26] Ashutosh Saxena, Justin Driemeyer, and Andrew Y Ng. Robotic
grasping of novel objects using vision. The International Journal of
Robotics Research, 27(2):157–173, 2008.
[27] P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser. The princeton shapebenchmark. In Shape modeling applications, 2004. Proceedings, pages
167–178. IEEE, 2004.
[28] Hang Si. Constrained delaunay tetrahedral mesh generation and refinement. Finite elements in Analysis and Design, 46(1):33–46, 2010.

[29] J. A. Stork, F. T. Pokorny, and D. Kragic. Integrated motion and clasp
planning with virtual linking. In IEEE/RSJ International Conference onIntelligent Robots and Systems (IROS), Tokyo, Japan, 2013.
[30] J. A. Stork, F. T. Pokorny, and D. Kragic. A topology-based object
representation for clasping, latching and hooking. In IEEE-RAS International Conference on Humanoid Robots (HUMANOIDS13), Atlanta,
USA, 2013.
[31] M. Vahedi and A. F. van der Stappen. Caging polygons with two andthree fingers. The International Journal of Robotics Research, 27(1112):1308–1324, 2008.

A PPENDIX
Here we present the proof of the supporting claim used in
Section V.
Lemma 1. Caging under rigid transformations (Def. 10)
is an example of caging under D-deformations (Def. 11),
where D-deformations is a class of isotopies representing rigid
transformations.
Proof. Any path g : I → SE(3) such that g(t).int(O) ∩M = ∅ for all t ∈ I starting at the identity element e = g(0)corresponds exactly to an isotopy H : O × I → R3 definedby H(x, t) = g(t).x and preserving distances between points:kx − x0 k = kH(x, t) − H(x0 , t)k for all x, x0 ∈ O and t ∈ I.
Furthermore, H(x, 0) = e.x = x = ι(x) for all x ∈ O.
Let us denote the class of isotopies generated by such paths
g : I → SE(3) by D. Since SE(3) = R3 ×SO(3), and SO(3)is compact, the identity element e ∈ CO = {g ∈ SE(3) :M ∩g(int(O)) = ∅} lies in a bounded path-component of CO
if and only if the distance between the initial and any otherreachable position of the object is bounded: dist(O, g(t).O) ≤C for all t ∈ I, g : I → SE(3) and for some fixed C ≥ 0.
Since M does not change its position in the space, the latter
implies that for any reachable position of the object its distanceto M is bounded as well: dist(M, g(t).O) ≤ C 0 for all t ∈ I
and for some real constant C 0 ≥ 0.
The latter implies that for any D-isotopy H and for eacht ∈ I we haveinf

kx1 − x2 k ≤ C 0

x1 ∈M,x2 ∈H(O,t)

for some real constant C 0 ≥ 0.

Anastasiia Varava received a B.Sc. degree in Computer Science from Karazin Kharkiv National University, Ukraine, in 2013 and a M.Sc. degree in Computer Science from the University of Nice Sophia
Antipolis, France, in 2014. She is a Ph.D. student
at the Centre for Autonomous Systems and theComputer Vision and Active Perception Lab, KTH
Royal Institute of Technology, Stockholm, Sweden.
She is interested in mathematical representations for
robotic manipulation.

19

Danica Kragic (SM’12) received the M.Sc. degree
in Mechanical Engineering from TU Rijeka, Rijeka,
Croatia, in 1995 and the Ph.D. in Computer Sciencefrom the KTH Royal Institute of Technology, Stockholm, Sweden, in 2001. She is a Professor with the
School of Computer Science and Communication,
KTH Royal Institute of Technology. Her researchinterests include computer vision and robotics. Prof.
Kragic is a Member of the Swedish Royal Academyof Sciences and Swedish Young Academy. She
received the 2007 IEEE Robotics and Automation
Society Early Academic Career Award.

Florian T. Pokorny received his B.Sc. degree inMathematics from the University of Edinburgh anda Master of Advanced Study (Part III) from the
University of Cambridge. After that, he completed
his Ph.D. in Mathematics at the University of Edinburgh. He is a Postdoctoral Researcher at the
AMPLab and the Berkeley Automation Science Lab
at the University of California, Berkeley. Before
that, he was a Postdoctoral Researcher at the Centre
for Autonomous Systems and the Computer Vision
and Active Perception Lab, KTH Royal Institute ofTechnology. He is interested in robotic manipulation, machine learning andtopological data analysis.