11institutetext: University of Leeds, UK.
22institutetext: University of California, Berkeley, USA.

# Multi-Object Grasping in the Plane

Wisdom C. Agboh 1122 Jeffrey Ichnowski 22 Ken Goldberg 22 Mehmet R. Dogar 11

###### Abstract

We consider the problem where multiple rigid convex polygonal objects rest in
randomly placed positions and orientations on a planar surface visible from an
overhead camera. The objective is to efficiently grasp and transport all
objects into a bin. Specifically, we explore multi-object push-grasps where
multiple objects are pushed together before the grasp can occur. We provide
necessary conditions for multi-object push-grasps and apply these to filter
inadmissible grasps in a novel multi-object grasp planner. We find that our
planner is 19 times faster than a Mujoco simulator baseline. We also propose a
picking algorithm that uses both single- and multi-object grasps to pick
objects. In physical grasping experiments, compared to a single-object picking
baseline, we find that the multi-object grasping system achieves 13.6% higher
grasp success and is 59.9% faster. See https://sites.google.com/view/multi-
object-grasping for videos, code, and data.

Figure 1: Robot picks five objects at once with a multi-object grasp in a
cluttered scene.

##  1 Introduction

There has been a recent increase in demand for fast and efficient robot
picking systems around the world, especially for warehouses [6, 20, 22, 15].
State-of-the-art robot picking systems use only single-object grasps. As robot
motion is increasingly becoming the bottleneck of pick-and-place systems [17,
16], reducing the number of arm motions with multi-object grasps has the
potential to increase speed significantly. Furthermore, in cluttered scenes
like Fig. 1, some of the objects may not have the necessary free space around
them for the gripper to pick them individually in contrast to multi-object
grasps.

Prior-work [31, 32, 11] studied multi-object grasps for the case where objects
are already in contact and ready to be grasped. However, objects are
oftentimes apart and must be pushed/squeezed together before a multi-object
grasp is possible. We call these _multi-object push-grasps_. They require
physics-based predictions of how objects will move when the grippers close,
e.g. to predict whether the objects will remain inside the grasp or whether
they will slide out.

One approach to synthesizing such multi-object push-grasps is to divide it
into two steps. Sakamoto et al. [26] proposed a system to pick two cuboids at
once. Their approach pushes and aligns the objects first before grasping them.
Such a two-step approach may not be feasible in cluttered scenes with more
than two objects where object access is limited.

In this work, we propose a single-step multi-object push-grasp where objects
are pushed and grasped simultaneously as the robot closes its gripper. One way
to achieve that is to create models of objects in a physics simulator,
generate single-step candidate grasps, and test them until a successful grasp
is found. However, this is computationally expensive given the large number of
physics simulations that could be required to find a grasp [2, 3, 14].

Therefore, we propose necessary conditions for multi-object push-grasping. We
use these necessary conditions in a novel multi-object grasp planner to rank
and filter grasp candidates, before testing them in a physics simulator. The
result is a multi-object grasp planner that, on average, tests only two grasp
candidates in a physics simulator before finding a successful one. In
addition, we propose a picking system that uses the multi-object grasp planner
to pick single or multiple objects at each time.

In simulation experiments, we find that our multi-object grasp planner is 19
times faster than a physics simulator baseline. In physical picking
experiments compared to a single object picking baseline, we find that the
multi-object grasping system achieves 13.6% higher grasp success, and is 59.9%
faster. In summary, this work contributes:

  * •

Necessary conditions for multi-object push-grasping.

  * •

Theorems and proofs on the necessary conditions.

  * •

A multi-object grasp planner.

  * •

A picking system that uses both single and multi-object grasps.

  * •

Simulation experiments that compare our grasp planner with a physics simulator
baseline and physical experiments that compare our picking system with a
single object grasping baseline.

##  2 Related work

Picking multiple objects from a table or a bin is a common robotics problem
[20]. Most prior work [23, 19] in picking focus on single object grasping.
Recently, Sakamoto et al. [26] proposed a picking system that uses both one-
and two-object grasps to pick cuboids. In this work, we propose a picking
system that can grasp an arbitrary number of extruded convex polygonal objects
at once.

A key question here is how to synthesize or generate grasps. There is a large
body of work on synthesizing single-object grasps. They typically fall into
one of two categories — analytic or data driven. The analytic methods [24, 25,
18] assume known object model and contact locations. They find grasps that can
resist external wrenches or constrain the object’s motion. On the other hand,
data-driven approaches [4, 9, 21] generate grasping models that map directly
from sensor readings like an RGB-D image to a successful grasp through various
machine learning techniques.

Considering multi-object grasps, in several works [10, 11, 13], conditions for
enveloping grasps of multiple objects using a multi-fingered robot hand, under
the rolling contact assumption are proposed. Multiple objects (already in
grasp wrench equilibrium) are grasped and lifted up towards the gripper’s
palm. Harada et al. [12] introduced active force closure for multiple objects.
The work derives conditions to generate an arbitrary acceleration on multiple
objects grasped with a multi-fingered robot hand. Yoshikawa et al. [33]
proposed a condition to achieve power grasps where they formulate the multi-
object optimal power grasp problem and minimize finger joint torques.

Other works [29, 28, 31, 32] propose methods to evaluate the grasp stability
of multiple planar objects grasped by a multi-fingered robot hand. Fingers are
replaced with 2D spring models and grasp stability is analysed through
potential energy stored in the grasp. Yamada and Yamamoto [30] extended these
multi-object grasp stability analyses to the 3D case, under both rolling and
sliding contact. Results in these multi-object grasping works are mostly only
numerical simulations, without real-robot multi-object grasps. In this paper,
we derive conditions for equilibrium multi-object grasps, under the
frictionless point-contact model. We also show real-robot multi-object grasps.

Recently, Chen et al. [5] investigated the problem of dipping a robot hand
inside a pile of identical spherical objects, closing the hand and estimating
the number of objects remaining in the hand after lifting. Shenoy et al. [27]
also studied multi-object grasping in a similar setting of identical spherical
objects, but with a goal of transferring the picked objects to another bin.
Their approach generates a pre-grasp configuration and flexion strategy that
corresponds to the desired number of objects to be picked from a given pile.
Our work is focused on multi-object grasps of complex-shaped objects where
physics predictions play a major role.

At the heart of various push-grasping methods [7, 6, 15] is the need to make
physics-based predictions of how objects will move when pushed and potentially
squeezed together. It is computationally expensive to predict the result of
these contact interactions [1]. Thus, we propose necessary conditions for
multi-object push-grasping for the first time to the best of our knowledge. We
use these conditions in a novel multi-object grasp planner to synthesize
multi-object grasps. Thereafter, we use our grasp planner in a novel picking
system that generates both single and multi-object grasps and picks randomly
placed objects.

##  3 Problem statement

We consider the problem where multiple rigid convex polygonal objects rest in
randomly placed positions and orientations on a planar surface visible from an
overhead camera. The goal is to develop a picking algorithm that efficiently
grasps and transports all objects to a bin, using both single- and multi-
object grasps. We assume a parallel-jaw gripper and objects that are extruded
convex polygons. We assume all objects have uniform mass and known geometry.
The state $\mathbf{x}$ is the position and orientation of all objects:
$\mathbf{x}=[\\{x_{\\_}{i},y_{\\_}{i},\theta_{\\_}{i}\\}],\hskip
2.84526pt\mathrm{for}\hskip 2.84526pt\mathrm{i}\hskip
2.84526pt\mathrm{=}\hskip 2.84526pt\mathrm{0},\dots,N_{\\_}{o}-1,$ where
$N_{\\_}{o}$ is the number of objects on the table, $x_{\\_}i$, $y_{\\_}i$,
and $\theta_{\\_}{i}$ represent the 2D pose of object $i$, provided by an
overhead camera. We represent single and multi-object grasp actions in the
same way: $\mathbf{u}=[x_{\\_}{g},y_{\\_}{g},\theta_{\\_}{g}]$ , where
$x_{\\_}{g},y_{\\_}{g}$, and $\theta_{\\_}{g}$ represent the desired grasp
pose of the gripper, after which the jaws close with a maximum force
$f_{\\_}{g}$.

The grasp action involves four steps. (1) Moving the open gripper above the
initial desired grasp pose, and lowering down until just above the
surface/table. (2) Closing the gripper jaws. (3) Moving the gripper upwards,
off the table, and above the bin. (4) Opening the jaws such that objects fall
into the bin.

##  4 Multi-Object Grasps

To plan multi-object grasps, we need to understand conditions under which a
multi-object grasp will succeed or fail. In this section, we study the
conditions to obtain an equilibrium grasp for single and multiple planar,
convex polygonal objects. Equilibrium grasps on an object occur when the
grippers can apply forces and torques consistent with the contact model
assumed at contact points, such that the net wrench on the object is zero. We
study these grasps for multiple objects, under the frictionless point-contact
model.

(a)(b)$f_{\\_}g$$\hat{\mathbf{n}}_{\\_}{l}$$\hat{\mathbf{n}}_{\\_}{r}$$\frac{\pi}{2}$$f_{\\_}g$$f_{\\_}g$$f_{\\_}g$

Figure 2: Frictionless equilibrium grasps for single convex polygonal objects,
with a parallel-jaw gripper. There are two possible grasp conditions in the
frictionless case: (a) Two parallel edges. (b) Vertex and an opposing edge.
The vertex has a perpendicular projection onto the edge.

In single-object grasping, under this contact model, the contact force from
the left (l) and right (r) gripper plates can be written as:
$\mathbf{f}_{\\_}{i}=f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{i},\hskip
2.84526pti\in\\{l,r\\}$, where $\hat{\mathbf{n}}_{\\_}{i}$ is the surface
inward unit normal at the respective contact point, and $f_{\\_}{g}$ is the
magnitude of a maximum gripper force. We seek equilibrium grasps under the
frictionless point contact model. Thus, contact forces from the left and right
grippers must satisfy:

$\displaystyle
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{l}+f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{r}=\mathbf{0},\hskip
8.53581pt\mathbf{p}_{\\_}{l}\times
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{l}+\mathbf{p}_{\\_}{r}\times
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{r}=\mathbf{0},$ (1)

where $\mathbf{p}_{\\_}{l}$ and $\mathbf{p}_{\\_}{r}$ are the position vectors
of the left and right contact points respectively. Eq. 1 implies that for
parallel-jaw grippers on a convex polygonal object, we can achieve equilibrium
grasps only if the two contact normals have opposing directions
($\hat{\mathbf{n}}_{\\_}{l}=-\hat{\mathbf{n}}_{\\_}{r}$), and lie on the same
line. These are antipodal grasps.

Antipodal grasps on a convex polygonal object occur under any of the following
two necessary conditions: (i) two parallel edges as shown in Fig. 2a, and (ii)
one vertex and an opposing edge where the perpendicular projection of the
vertex lies inside the corresponding edge, as shown in Fig. 2b. There is a
possible third case of grasping the convex polygonal object at two vertices,
however that is unstable in the frictionless case and we do not consider such
grasps.

We extend the initial frictionless equilibrium grasp analysis to the multi-
object case. To achieve an equilibrium grasp in the multi-object case, each
object in the multi-object grasp must individually be in an antipodal grasp
from contacts with grippers or neighbouring objects. In this work, we restrict
our study to multi-object grasps where each object involved is kept in
equilibrium by only two neighbouring objects or one object and a gripper
plate. This implies that all contact normals across all objects must lie on
the same line. We show a sample frictionless equilibrium multi-object grasp in
Fig. 3.

Specifically, from the single object equation, Eq. 1, the multi-object
equilibrium grasp equations for a set of $n_{\\_}{o}$ objects become:

$\displaystyle
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{l_{\\_}i}+f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{r_{\\_}i}=\mathbf{0},\hskip
8.53581pti\in\\{0,1,\dots,n_{\\_}{o}-1\\}$ (2)
$\displaystyle\mathbf{p}_{\\_}{l_{\\_}i}\times
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{l_{\\_}i}+\mathbf{p}_{\\_}{r_{\\_}i}\times
f_{\\_}{g}\hat{\mathbf{n}}_{\\_}{r_{\\_}i}=\mathbf{0},\hskip
8.53581pti\in\\{0,1,\dots,n_{\\_}{o}-1\\},$ (3)

where $\hat{\mathbf{n}}_{\\_}{l_{\\_}i}$ and
$\hat{\mathbf{n}}_{\\_}{r_{\\_}i}$ are the left and right contact normals for
object $i$. For an equilibrium grasp, we find that
$\hat{\mathbf{n}}_{\\_}{l_{\\_}i}=-\hat{\mathbf{n}}_{\\_}{r_{\\_}i}$, and both
contact normals must lie on the same line for object
$i\in\\{0,1,\dots,n_{\\_}{o}-1\\}$. This also implies that all normals across
all $n_{\\_}{o}$ objects will lie on the same line.

$f_{\\_}g$$\hat{\mathbf{n}}_{\\_}{l_{\\_}i}$$\hat{\mathbf{n}}_{\\_}{r_{\\_}i}$$\hat{\mathbf{n}}_{\\_}{l_{\\_}{i+1}}$$\hat{\mathbf{n}}_{\\_}{r_{\\_}{i+1}}$$\hat{\mathbf{n}}_{\\_}{l_{\\_}{i+2}}$$\hat{\mathbf{n}}_{\\_}{r_{\\_}{i+2}}$$f_{\\_}g$

Figure 3: A sample frictionless equilibrium grasp for multiple convex
polygonal objects. Each object is in an antipodal grasp and all contact
normals lie on the same line.

##  5 Multi-Object Push Grasps

Objects almost never start in contact, fully aligned and ready to be grasped
as shown in the previous section and in other prior work [13, 30, 33]. It is
the case in practice that objects are usually apart and need to be squeezed
together in a multi-object push-grasp. Hence, the need to make physics-based
predictions of how objects will move as the robot pushes them together.

###  5.1 Two Necessary Conditions

Physics simulation for multi-object grasping is computationally expensive. We
aim to avoid simulations and significantly speed-up multi-object grasp
planning. In this section, we propose two necessary conditions for a multi-
object push-grasp to succeed. We propose these conditions for the frictionless
point-contact model. The conditions are: multi-object diameter function and
intersection area. If any of these conditions is violated, the push-grasp is
guaranteed to fail. We use these necessary conditions to filter out
inadmissible grasps, and therefore to avoid computationally expensive
simulations of these grasps.

###  5.2 Multi-Object Diameter Function

$o^{s}_{\\_}{0}$$o^{s}_{\\_}{i}$$o^{s}_{\\_}{n_{\\_}{0}-1}$$f_{\\_}{g}$$f_{\\_}{g}$$f_{\\_}{g}$$f_{\\_}{g}$$S$$h_{\\_}{0}$$h_{\\_}f$$w_{\\_}g$$b_{\\_}l$$b_{\\_}r$

Figure 4: A multi-object grasp. We show the initial internal rectangular
region $S$, the gripper stroke $w_{\\_}g$, the left and right minimum gripper
distances to objects, $b_{\\_}{l}$ and $b_{\\_}{r}$ respectively, the initial
multi-object grasp diameter ($h_{\\_}{0}$) and the final multi-object grasp
diameter ($h_{\\_}{f}$). We also show that $h_{\\_}{0}\geq h_{\\_}{f}$ for any
equilibrium multi-object grasp.

In single-object grasping, consider quasi-statically closing a parallel-jaw
gripper such that both jaws simultaneously make the first contact with the
object. The distance between the jaws at this initial contact is called the
diameter, first introduced by Goldberg [8] for frictionless grasping. Let this
initial diameter be $d_{\\_}{0}$. As we continue to close the grippers past
this initial contact, the diameter must decrease until it reaches a local
minimum value, at the stable grasp configuration. Let this final diameter be
$d_{\\_}{f}$. Thus, for any stable single-object grasp, we have that:
$d_{\\_}{0}\geq d_{\\_}{f}$. Next, we extend the single-object diameter
condition to the multi-object case.

We begin by introducing the multi-object grasping diameter ($h$). We
illustrate how to compute $h$ given a grasp $\mathbf{u}$ in Fig. 4. We define
the initial internal region between the parallel-jaw grippers to be the
internal rectangular region, $S$. Let $o^{s}_{\\_}{i}=S\cap O_{\\_}{i}$, be
the intersection polygon between $S$ and object $O_{\\_}i$. Let $w_{\\_}g(t)$
be the gripper stroke at time $t$. Let $b_{\\_}{l}(t)$ be the shortest
distance between $o^{s}_{\\_}{0}$ and the left jaw, and $b_{\\_}{r}(t)$ be the
shortest distance between $o^{s}_{\\_}{n_{\\_}{0}-1}$ and the right jaw. Then,
the multi-object grasp diameter is:

$\displaystyle h(t)=w_{\\_}{g}(t)-(b_{\\_}{l}(t)+b_{\\_}{r}(t)).$ (4)

Let $h_{\\_}{0}$ be the initial multi-object grasp diameter at time
$t_{\\_}{0}$, and let $h_{\\_}{f}$ be the corresponding final multi-object
grasp diameter, at time $t_{\\_}{f}$ when the grippers become stationary after
closing.
$h_{\\_}{0}=h(t_{\\_}{0})=w_{\\_}{g}(t_{\\_}{0})-(b_{\\_}{l}(t_{\\_}{0})+b_{\\_}{r}(t_{\\_}{0}))$,
and
$h_{\\_}{f}=h(t_{\\_}{f})=w_{\\_}{g}(t_{\\_}{f})-(b_{\\_}{l}(t_{\\_}{f})+b_{\\_}{r}(t_{\\_}{f}))$.
When the grippers become stationary at $t_{\\_}{f}$,
$b_{\\_}{l}(t_{\\_}{f})=b_{\\_}{r}(t_{\\_}{f})=0$, and
$h_{\\_}{f}=w_{\\_}{g}(t_{\\_}{f})$. Since parallel-jaw grippers close in only
one direction, it implies that $w_{\\_}{g}(t_{\\_}{i})\geq
w_{\\_}{g}(t_{\\_}{i+1})$, where $t_{\\_}{i+1}>t_{\\_}{i}$, and by extension
$w_{\\_}{g}(t_{\\_}{0})\geq w_{\\_}{g}(t_{\\_}{f})$. Therefore, any multi-
object grasp will satisfy:

$\displaystyle h_{\\_}{0}\geq h_{\\_}{f}$ (5)

In Fig. 4, we show a sample multi-object initial diameter $h_{\\_}{0}$ and
final diameter $h_{\\_}{f}$, for a frictionless multi-object grasp.

The multi-object grasp diameter condition in Eq. 5 requires knowledge of
$h_{\\_}{f}$ which in turn requires a physics simulation to compute. This
defeats the purpose of this condition.

######  Theorem 5.1.

Given a set of $n_{\\_}{o}$ objects, there exists a constant multi-object
grasp diameter, $h_{\\_}{f_{\\_}\mathrm{min}}$ such that any grasp
$\mathbf{u}$, with some initial multi-object grasp diameter $h_{\\_}{0}$ is
guaranteed to fail when $h_{\\_}{0}<h_{\\_}{f_{\\_}\mathrm{min}}$.

######  Proof 5.2.

Every polygonal object $i$ in a successful multi-object grasp of $n_{\\_}{o}$
objects has a final diameter $d^{i}_{\\_}{f}$, at time $t_{\\_}{f}$ when the
grippers become stationary after they close. This corresponds to a multi-
object grasp diameter
$h_{\\_}{f}=\sum^{n_{\\_}{0}-1}_{\\_}{i=0}d^{i}_{\\_}{f}$. This summation is
true for any successful multi-object grasp because contact normals across all
$n_{\\_}{o}$ objects must lie on the same line (Eq. 2 and Eq. 3).

$h_{\\_}{f_{\\_}{min}}$

Figure 5:  All possible unique final multi-object grasp diameters for a
rectangle and an isosceles triangle. There are only two unique multi-object
grasp configurations (excluding vertex-vertex contacts). The left
configuration has the minimum multi-object diameter
$h_{\\_}{f_{\\_}\mathrm{min}}$.

Every object has a minimum final diameter ($d^{i}_{\\_}{f_{\\_}{min}}$), at
which a stable frictionless single-object grasp will occur. We can enumerate
all final object grasp diameters for any convex polygonal object under the
frictionless point-contact model using the two conditions shown in Fig. 2. Let
the finite number of possible final diameters be $N^{i}_{\\_}{d_{\\_}f}$ for a
given object $i$. The minimum final diameter can then be written as:

$\displaystyle
d^{i}_{\\_}{f_{\\_}\mathrm{min}}=\min(d^{i}_{\\_}{f_{\\_}{j}}),\hskip
8.53581ptj\in\\{0,1,\dots,N^{i}_{\\_}{d_{\\_}{f}}-1\\}.$ (6)

Then, we compute the minimum multi-object grasp diameter
$h_{\\_}{f_{\\_}\mathrm{min}}$ at which a stable frictionless multi-object
grasp of $n_{\\_}{o}$ objects will occur as:

$\displaystyle
h_{\\_}{f_{\\_}\mathrm{min}}=\sum^{n_{\\_}{o}-1}_{\\_}{i=0}d^{i}_{\\_}{f_{\\_}{min}}.$
(7)

Recall from Eq. 5 that $h_{\\_}{0}\geq h_{\\_}{f}$ for any multi-object grasp,
but $d^{i}_{\\_}{f}\geq d^{i}_{\\_}{f_{\\_}\mathrm{min}}$ which implies
$h_{\\_}{f}\geq h_{\\_}{f_{\\_}\mathrm{min}}$. Therefore any successful multi-
object grasp must satisfy:

$\displaystyle h_{\\_}{0}\geq h_{\\_}{f_{\\_}\mathrm{min}}.$ (8)

Thus, if the initial multi-object grasp diameter is less than the minimum
possible final multi-object grasp diameter
($h_{\\_}{0}<h_{\\_}{f_{\\_}\mathrm{min}}$), the grasp $\mathbf{u}$ is
guaranteed to fail. This means that $h_{\\_}{0}$ is so small that as the
gripper closes, a stable multi-object grasp diameter can never be reached,
completing the proof. ∎

For example, consider the case in Fig. 5, where we have two objects such that
$n_{\\_}{o}=2$. The rectangular object ($O_{\\_}0$) has two unique stable
grasp configurations under frictionless grasping with a parallel-jaw gripper
($N^{0}_{\\_}{d_{\\_}{f}}=2$), disregarding the other configurations due to
symmetry, and vertex-vertex grasps. Similarly, the triangular object
($O_{\\_}1$) has only one unique stable grasp configuration
($N^{1}_{\\_}{d_{\\_}{f}}=1$), again disregarding vertex-vertex grasps. Thus,
there are two unique multi-object grasp configurations in the frictionless
case and the left configuration has the minimum multi-object grasp diameter
$h_{\\_}{f_{\\_}\mathrm{min}}$. We show an example of a grasp that failed due
to a violation of the multi-object grasp diameter condition in Fig. 7(top).

###  5.3 Intersection Area

Each object in a multi-object equilibrium grasp needs to also be in a single-
object equilibrium grasp. This requires at least two contacts, whether from
the parallel jaws or other objects. Thus, as the gripper closes, if we predict
no contacts for at least one object, the multi-object grasp fails.

Let $A_{\\_}{i}(t)=\mathrm{Area}(o^{s}_{\\_}{i})$, be the area of the
intersection polygon for object $i$, during a multi-object grasp. Then, we
require the intersection area for each object be greater than zero when the
gripper closes. $A_{\\_}{i}(t)$ changes as the gripper closes with constant
force $f_{\\_}{g}$, and hence is a function of time. Thus, the intersection
area necessary condition for $n_{\\_}{o}$ objects become:

$\displaystyle A_{\\_}{i}(t_{\\_}{f})>0,\hskip
2.84526pti\in\\{0,1,\dots,n_{\\_}{o}-1\\}$ (9)

where $t_{\\_}f>0$ is when the gripper becomes stationary after closing.
Knowing exactly how $A_{\\_}{i}(t)$ changes as the gripper closes requires a
physics simulation, which defeats the purpose of this condition. However,
observe that if the starting intersection area for an object is zero it is
likely to remain so as the gripper closes. This is especially true when the
object of interest is sufficiently far away from $S$.

$m_{\\_}{j}$$O_{\\_}{i}$$m_{\\_}{j+1}$$M=m_{\\_}{j}+m_{\\_}{j+1}$$\hat{\mathbf{n}}_{\\_}{S}$$f_{\\_}{g}$$f_{\\_}{g}$$S$

Figure 6: An illustration of the intersection area necessary condition’s
proof. $M=\sum^{n_{\\_}{o}-1}_{\\_}{j=1}m_{\\_}{j}$ is an upper bound on
$\epsilon$, the minimum distance between $O_{\\_}{i}$ and $S$ such that the
multi-object grasp is guaranteed to fail when $A_{\\_}{i}(0)=0$.

######  Theorem 5.3.

Given an object $O_{\\_}{i}$ in a multi-object grasp $\mathbf{u}$ of
$n_{\\_}{o}$ objects, if $A_{\\_}{i}(0)=0$ then there exists some minimum
distance $\epsilon>0$ between $O_{\\_}{i}$ and $S$ such that the multi-object
grasp is guaranteed to fail if the distance between $O_{\\_}i$ and $S$ is
larger than $\epsilon$.

######  Proof 5.4.

Consider Fig. 6. Object $O_{\\_}i$ moves towards $S$ and can subsequently
achieve $A_{\\_}{i}(t_{\\_}{f})>0$ only when there is contact between it and
other objects as the gripper closes. $\epsilon$ is the minimum distance
between $O_{\\_}{i}$ and $S$ where surrounding objects cannot make contact as
the gripper closes with grasp $\mathbf{u}$. Let $m_{\\_}{j}$ for a surrounding
object $j$ be the length of its longest diagonal, and let
$M=\sum^{n_{\\_}{o}-1}_{\\_}{j=1}m_{\\_}{j}$ be the sum of such diagonals for
all other objects. This is the farthest other ($n_{\\_}{o}-1$) objects can be
lined up along the normal direction ($\hat{\mathbf{n}}_{\\_}{S}$) of $S$ to
reach $O_{\\_}i$. Assuming quasi-static grasping, other objects cannot make
contact with $O_{\\_}{i}$ beyond $M$. It is an upper bound on $\epsilon$ such
that $\epsilon\leq M$. Therefore if $O_{\\_}{i}$ is at least $M$ minimum
distance away from the internal rectangular region and $A_{\\_}{i}(0)=0$, the
multi-object grasp, including the object $O_{\\_}i$ is guaranteed to fail,
which completes the proof. ∎

In practice, $M$ would be too large to provide useful grasp filtering. Recall
that there is a minimum grasp diameter ($h_{\\_}{f_{\\_}\mathrm{min}}$) at
which a multi-object grasp succeeds. This means that starting at $h_{\\_}{0}$,
the grippers can only move a maximum distance of
$\Delta{h_{\\_}\mathrm{max}}=h_{\\_}{0}-h_{\\_}{f_{\\_}\mathrm{min}}$,
otherwise the grasp fails. Under quasi-static grasping and given that the
motion of objects in $S$ are only due to the gripper motion, we assume each
surrounding object will move at most by $\Delta{h_{\\_}\mathrm{max}}$ along
$\hat{\mathbf{n}}_{\\_}S$ and towards $O_{\\_}{i}$. Given, that
$\Delta{h}_{\\_}\mathrm{max}$ is small for a standard parallel-jaw gripper, we
assume that contacts from surrounding objects $O_{\\_}{j}$ will be too short
to bring object $O_{\\_}{i}$ into the internal rectangular region $S$.
Therefore, we approximate $\epsilon=0$, such that the relaxed intersection
area condition becomes:

$\displaystyle A_{\\_}{i}(0)>0,\hskip
2.84526pti\in\\{0,1,\dots,n_{\\_}{o}-1\\}.$ (10)

For example, take Fig. 6 where the multi-object grasp diameter condition is
satisfied. Since $A_{\\_}{i}(0)=0$, the grasp is guaranteed to fail with the
relaxed condition in Eq. 10. We show an example of a multi-object grasp that
failed due to a violation of the intersection area necessary condition in Fig.
7 (bottom).

Figure 7: Two examples of grasps that failed due to a violation of the two
conditions. Top row: Multi-object diameter failure. Bottom row: intersection
area failure. The black rectangles are the parallel jaws of the gripper.

##  6 Picking System

In this section, we detail a picking system that uses both single and multi-
object grasps to pick objects placed in random positions and orientations. In
the following subsections, we present the main picking algorithm and the
multi-object grasp planner.

1 do

2 $\mathbf{x}$, $N_{\\_}{o}$ $\leftarrow$ GetCurrentState(.)

3 objgroups $\leftarrow$ CreateObjGroups($\mathbf{x}$)

4 rankedobjgroups $\leftarrow$ RankObjGroups(objgroups)

5

6 for  _objgroup $\mathbf{in}$ $\mathrm{ranked\\_obj{\\_}groups}$_ do

7 $\mathbf{u}$ $\leftarrow$ GraspPlanner($\mathbf{x}$, objgroup)

8 if  _ $\mathbf{u}$ $!$$=$ {}_ then

9 Execute $\mathbf{u}$

10 break

11while  _$N_{\\_}{o}$ $>$ $\mathrm{0}$ $\mathbf{and}$ $\mathrm{time}$
$\mathrm{remaining}$_;

Algorithm 1 Picking Algorithm

###  6.1 Picking Algorithm

We present a picking algorithm in Alg. 1. Given a current state $\mathbf{x}$
containing $N_{\\_}{o}$ objects (line 2), the algorithm finds a multi-object
grasp for the largest group of objects that can be grasped together, using the
GraspPlanner(.) subroutine (line 6) and executes the grasp, until no objects
are left on the table or a time limit is reached (line 10). The
CreateObjGroups(.) subroutine (line 3) loops through center points of objects
and creates groups of all objects whose centers are within half a gripper
width radius. Thereafter it eliminates all object groups that have a superset
in the object groups list, apart from the single objects. The RankObjGroups(.)
subroutine (line 4) ranks the list of object groups by their size, such that
the grasp planner attempts to find a grasp for the largest object groups
first. We provide details of the GraspPlanner(.) subroutine in the subsequent
section. A grasp execution can result in failure where desired objects escape
the grippers and other objects can be displaced from their original poses. The
online nature of Alg. 1, allows it to continue finding new grasps until fully
clearing the table or running out of time.

###  6.2 Grasp Planner (GP)

In this section, we propose a multi-object grasp planner. It is summarized in
Alg. 2. The GraspPlanner(.) returns a grasp $\mathbf{u}$ if it can find one
for the current group of objects, $obj{\\_}group$, given the current state.

Input : $\mathbf{x}$: Current state, objgroup: Objects in the potential grasp

Output : $\mathbf{u}$: A grasp action

1

2graspcands $\leftarrow$ GenGraspCands($\mathbf{x}$, objgroup)

3 rankedgraspcands $\leftarrow$ RankGraspCands(graspcands)

4 for  _$\mathbf{u}$ $\mathbf{in}$ $\mathrm{ranked\\_grasp\\_cands}$_ do

5 if  _$\mathbf{not}$ $\mathrm{GraspFailure}$($\mathbf{x}$, $\mathbf{u}$)_
then

6 if  _$\mathrm{CheckGraspSuccess}$($\mathbf{x}$, $\mathbf{u}$)_ then

7 return _$\mathbf{u}$_

8return {}

Algorithm 2 Grasp Planner (GP)

First, the algorithm generates multiple grasp candidates (line 1). Second, it
ranks these grasp candidates based on their likelihood of being successful
(line 2). Finally, we sequentially test grasps to find a successful one (lines
3–6). To test a multi-object grasp we first use a grasp filtering system. We
check if the grasp satisfies the two neccessary conditions outlined in Sec. 5
on line 4. If the necessary conditions are satisfied, we check for grasp
success using a physics simulator (line 5). We explain the main subroutines in
the following paragrasphs:
GenGraspCands( ): Recall that a grasp action is parametrized as the position
and orientation of the gripper:
$\mathbf{u}=[x_{\\_}{g},y_{\\_}{g},\theta_{\\_}{g}]$. The gripper reaches the
desired pose and closes. Given a group of objects, we first find the convex
hull of all of the objects. Then, we generate $N_{\\_}{p}$ position samples
that uniformly cover the convex hull. At each position sample, we generate
$N_{\\_}{\theta}$ orientation samples. We reject samples that result in
collisions, between the jaws and any object — inside or outside the group.
RankGraspCands( ): We aim to find a parameter that quickly predicts the
likelihood of a multi-object push-grasp success and use this parameter to rank
grasp candidates. Recall the two necessary conditions for multi-object push-
grasp success in Sec. 5 — multi-object diameter and intersection area. These
conditions suggest that the larger the area of the intersection polygon for
each object, the more likely a grasp will be successful. Therefore, we propose
to use the total intersection area
($A_{\\_}{T}=\sum^{n_{\\_}{o}-1}_{\\_}{i=0}A_{\\_}{i}$) as a heuristic to
judge how successful a grasp will be. The higher the total area, the more
likely the grasp will be successful. $A_{\\_}{i}$ is computed as the area of
intersection between object $O_{\\_}i$ and $S$.
GraspFailure( ): We filter multi-object grasps using the two conditions
provided in Sec. 5 — multi-object grasp diameter and intersection area. If any
of the two necessary conditions is not satisfied, the multi-object grasp is
guaranteed to fail.
CheckGraspSuccess( ): To check the success of a grasp $\mathbf{u}$, we use a
physics simulator where we assume objects are rigid, and have a uniform mass
distribution. We close the gripper at the specified pose, then lift it above
the table to check that the grasp is stable. Using a physics simulator means
that our grasp planning system has no false positives for simulation
experiments. However, we expect some grasps to fail in physical experiments
due to uncertainty in state and model parameters and aleatory uncertainty
related to friction, sensing, and control.

##  7 Experiments and Results

We conduct simulation and physical experiments to evaluate the multi-object
push-grasping necessary conditions, grasp planner, and picking system. In the
following subsections, we explain the general setup, experimental details,
baselines, and results.

###  7.1 Setup in Simulation and Physical Experiments:

The robot is a UR5 with Robotiq 2F-85 gripper. We use Mujoco 2.1.0 as the
physics simulator. In all experiments, we use a fixed set of objects, shown in
Fig. 1. It contains a total of 33 objects from 3-sided to 6-sided convex
polygons. We create a model of these objects in Mujoco where we ensure that
objects are rigid and have a uniform mass distribution. In physical
experiments, we use an RGB-D camera to estimate the pose of objects on a
table. We approximate the frictionless case by selecting low ($\mu=0.01$)
friction parameters in Mujoco.

###  7.2 Evaluation of Necessary Conditions in Simulation:

In this section, we conduct simulation experiments to evaluate the proposed
necessary conditions for multi-object push-grasping. We use a physics
simulator to get ground-truth multi-object push-grasping results. If a
necessary condition is violated, the grasp is predicted to fail (negative). If
the ground truth also fails, we term this a true negative, otherwise it is a
false negative. An important question here is what percentage of true
negatives can we predict using these necessary conditions? Are there any false
negatives? These questions will specifically help us evaluate the practicality
of our intersection area assumption in Sec. 5.

Figure 8: Simulation experimental evaluation of the necessary conditions for
multi-object push-grasping. Using both the intersection area (Int. Area) and
the multi-object diameter (Diameter) necessary conditions, we can predict on
average across all objects 93.4% of true-negative grasps in any given set of
grasp candidates. The average number of grasp candidates in any given scene is
193.19 $\pm$ 1.54. All errors are within 95% confidence interval of the mean.

We consider classes of 2-object to 7-object grasps (limited only by gripper
width). For each multi-object grasp class, we create $200$ randomly generated
scenes. That is a total of 1200 grasping scenes. Thereafter, for each grasp
scene, we generate $N_{\\_}{p}\times N_{\\_}{\theta}=70\times 7$ grasp
candidate samples, and reject samples in collision. For each grasp candidate,
we check both multi-object push-grasping necessary conditions and compare
results to a Mujoco simulation of the grasp. We record any true negatives and
any false negatives, across all grasp candidates, grasp scenes, and classes.

Results on evaluating the necessary multi-object push-grasping conditions can
be found in Fig. 8. We did not record any false negatives across any object
class—a result that supports the mild intersection area assumption. A majority
of the true-negative grasps (85.4% on average) were predicted by the
intersection area condition, while the multi-object diameter function
predicted 8%. Both conditions combined predicted 93.4% of true negatives, with
a 0.5% overlap between their predictions only for the 2-object case. We find
that the multi-object grasp diameter condition violations reduce with
increasing number of objects (from 31% for two objects), while violations for
the intersection area increased. See Fig. 7 for grasps that failed due to a
violation of the multi-object diameter condition and the intersection area
condition.

###  7.3 Grasp Planning Experiments in Simulation

We conduct experiments in simulation to evaluate the multi-object grasp
planner. Our goal here is to understand the effects of the grasp filtering and
ranking systems. We follow the same process as Sec. 7.2 to generate random
scenes and corresponding grasp candidates. In each scene, we use the grasp
planner (GP) and three baselines to find a grasp. We record the grasp planning
time — total time to return a grasp or report that no successful grasp was
found. We also record the number of grasp samples tested/considered before a
grasp is found.

Baseline 1 (Rand-Phys): This is a version of the multi-object grasp planner
where we randomize the grasp candidates after they are generated (no grasp
ranking). Then test each grasp sequentially in only the physics simulator (no
grasp filtering), until a grasp is found or all grasp candidates are tested.

Baseline 2 (Rank-Phys): This is a version of the multi-object grasp planner
that ranks grasps but tests grasps sequentially using only the physics
simulator (no grasp filtering).

Baseline 3 (Rand-Fil-Phys): Here we randomize the grasp candidates (no
ranking) as in baseline 1, but use grasp filtering and physics simulator, like
the multi-object grasp planner.

Results: We show simulation multi-object grasp planning experimental results
in Fig. 9. Planning time results are in Fig. 9(a), results on grasps tested in
the physics simulator are in Fig. 9(b). Our proposed approach (GP) has the
lowest planning time of 2.2 seconds on average which is 19 times faster than
directly using only a physics simulator (Rand-Phys). We find that the grasp
ranking method reduced the number of tested grasps by 93.44%, when we compare
Rand-Phys and Rank-Phys.

(a) Planning time.

(b) Number of tested grasps.

Figure 9: Experimental results in simulation on multi-object grasp planning.
Our approach (GP) found a grasp or reported that none exists in 2.2 seconds on
average which is 19 times faster than the Mujoco physics simulator baseline
(Rand-Phys), thanks to a fast grasp filtering system. GP tests an average of 2
candidate grasps before a successful grasp is found. That is 16.2 times less
candidate grasps using the ranking system, compared to a random approach
(baselines Rand-Phys, and Rand-Fil-Phys). Error bars are shown within 95%
confidence interval of the mean.

###  7.4 Physical Experiments

We conduct physical picking experiments to evaluate the picking system
presented in this work, in comparison to a single object picking system.
Details of this single-object picking system can be found below.

Single object picking system: We use the same multi-object picking algorithm
and grasp planner for single object picking. However, we restrict the number
of objects to a randomly chosen single object.

Metrics: We compare both picking systems based on success rate, percentage of
objects picked, and picks per hour. Success rate: the percentage of grasp
attempts that moved at least one object into the box. Percent picked: the
fraction of objects that were moved to the box. Picks per hour (PPH): total
number of objects picked per hour, through single or multi-object grasps.

Physical experiment details: We create 20 picking scenes where we randomly
place 33 objects in different positions and orientations. We clustered objects
arbitrarily to create opportunities for multi-object grasps. In each scene, we
use both the multi-object picking system and the single-object picking system
to generate grasps. We replicated the scene manually between the two picking
systems, leading to a total of 40 real-robot runs. Please see Fig. 1 for a
sample real-world scene. A failed grasp attempt is where the robot misses a
grasp (all objects escape), or where all objects fall out of the gripper
before they reach the box.

Results: Picking results can be found in Table. 1. Both systems picked a
similar percentage of objects. However, the multi-object grasping system
achieved 13.6% higher grasp success. A major source of grasp failure is
uncertainty in state and model parameters. This affects success rates of both
picking systems. The single-object system suffers more as it makes more grasp
attempts aimed at picking single objects that are oftentimes not easily
accessible due to clutter. We find that the multi-object grasping system is
59.9% faster than the single object picking baseline. This is in spite of the
fact that uncertainty can sometimes aid the single-object picking system in
grasping more than one object at a time.

Table 1: Physical picking experimental results with 20 scenarios, each with 33 objects, placed in different random positions and orientations. Methods | Success rate (%) | Percent picked | PPH
---|---|---|---
Single-Object | 73.31 $\pm$ 4.84 | 97.77 $\pm$ 1.42 | 212.59 $\pm$ 19.03
Multi-Object | 83.33 $\pm$ 4.29 | 99.52 $\pm$ 0.48 | 340.08 $\pm$ 27.09

##  8 Discussion and future work

We consider the planar multi-object grasping problem where multiple convex
polygonal objects are grasped and transported to a bin. We provide necessary
conditions for multi-object push grasping under the frictionless point contact
model, and their corresponding theorems and proofs. Our experiments suggest a
significant speed-up in grasp planning time compared to a physics simulator
baseline. We also find a reduction in overall picking time, compared to a
single-object picking system. Grasps were planned without considering
uncertainty. This lead to grasp failure. We will extend this work to generate
robust multi-object grasps and to consider general 3D objects, including
deformables, as opposed to only planar convex polygonal objects.

## References

  * Agboh and Dogar [2018] Wisdom C. Agboh and Mehmet R. Dogar.  Pushing fast and slow: Task-adaptive planning for non-prehensile manipulation under uncertainty.  In _WAFR_ , 2018.
  * Agboh et al. [2019] Wisdom C. Agboh, Daniel Ruprecht, and Mehmet. R. Dogar.  Combining coarse and fine physics for manipulation using parallel-in-time integration.  _ISRR_ , 2019.
  * Agboh et al. [2020] Wisdom C. Agboh, Daniel Ruprecht, and Mehmet R. Dogar.  Parareal with a learned coarse model for robotic manipulation.  _Comput. Visual Sci._ , 23(8), 2020.
  * Bohg et al. [2014] Jeannette Bohg, Antonio Morales, Tamim Asfour, and Danica Kragic.  Data-driven grasp synthesis—a survey.  _IEEE Transactions on Robotics_ , 30(2):289–309, 2014.
  * Chen et al. [2021] Tianze Chen, Adheesh Shenoy, Anzhelika Kolinko, Syed Shah, and Yu Sun.  Multi-object grasping - estimating the number of objects in a robotic grasp.  In _IROS_ , 2021.
  * Danielczuk et al. [2018] Michael Danielczuk, Jeffrey Mahler, Chris Correa, and Ken Goldberg.  Linear Push Policies to Increase Grasp Access for Robot Bin Picking.  In _CASE_ , 2018.
  * Dogar and S. Srinivasa [2011] Mehmet Dogar and Siddhartha S. Srinivasa.  A framework for push-grasping in clutter.  In _RSS_ , 2011.
  * Goldberg [1993] Kenneth Y. Goldberg.  Orienting polygonal parts without sensors.  _Algorithmica_ , 10:201–225, 1993.
  * Goldfeder and Allen [2011] Corey Goldfeder and Peter K. Allen.  Data-driven grasping.  _Autonomous Robots_ , 31:1–20, 2011.
  * Harada and Kaneko [1998a] K. Harada and M. Kaneko.  Enveloping grasp for multiple objects.  In _ICRA_ , 1998a.
  * Harada and Kaneko [1998b] K. Harada and M. Kaneko.  Kinematics and internal force in grasping multiple objects.  In _IROS_ , 1998b.
  * Harada et al. [2000a] K. Harada, M. Kaneko, and T. Tsuji.  Active force closure for multiple objects.  In _Advances in Robot Kinematics_ , pages 155–164, 2000a.
  * Harada et al. [2000b] K. Harada, M. Kaneko, and T. Tsujii.  Rolling-based manipulation for multiple objects.  _IEEE Transactions on Robotics and Automation_ , 16(5):457–468, 2000b.
  * Hasan et al. [2020] Mohamed Hasan, Matthew Warburton, Wisdom C. Agboh, Mehmet R. Dogar, Matteo Leonetti, He Wang, Faisal Mushtaq, Mark Mon-Williams, and Anthony G. Cohn.  Human-like planning for reaching in cluttered environments.  In _ICRA_ , 2020.
  * Huang et al. [2021] Huang Huang, Marcus Dominguez-Kuhne, Vishal Satish, Michael Danielczuk, Kate Sanders, Jeff Ichnowski, Andrew Lee, Anelia Angelova, Vincent Olivier Vanhoucke, and Ken Goldberg.  Mechanical Search on Shelves using LAX-RAY: Lateral Access X-RAY.  In _IROS_ , 2021.
  * Ichnowski et al. [2020a] Jeffrey Ichnowski, Yahav Avigal, Vishal Satish, and Ken Goldberg.  Deep learning can accelerate grasp-optimized motion planning.  _Science Robotics_ , 5(48), 2020a.
  * Ichnowski et al. [2020b] Jeffrey Ichnowski, Michael Danielczuk, Jingyi Xu, Vishal Satish, and Ken Goldberg.  Gomp: Grasp-optimized motion planning for bin picking.  In _ICRA_ , 2020b.
  * Kehoe et al. [2013] Ben Kehoe, Akihiro Matsukawa, Sal Candido, James Kuffner, and Ken Goldberg.  Cloud-based robot grasping with the google object recognition engine.  In _ICRA_ , 2013.
  * Lou et al. [2021] Xibai Lou, Yang Yang, and Changhyun Choi.  Collision-aware target-driven object grasping in constrained environments.  In _ICRA_ , 2021.
  * Mahler and Goldberg [2017] Jeffrey Mahler and Ken Goldberg.  Learning deep policies for robot bin picking by simulating robust grasping sequences.  In _CoRL_ , volume 78, pages 515–524, 2017.
  * Mahler et al. [2016] Jeffrey Mahler, Florian T Pokorny, Brian Hou, Melrose Roderick, Michael Laskey, Mathieu Aubry, Kai Kohlhoff, Torsten Kröger, 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 with correlated rewards.  In _ICRA_ , 2016.
  * Matsumura et al. [2019] Ryo Matsumura, Yukiyasu Domae, Weiwei Wan, and Kensuke Harada.  Learning based robotic bin-picking for potentially tangled objects.  In _IROS_ , 2019.
  * Morrison et al. [2020] Douglas Morrison, Peter Corke, and Jürgen Leitner.  Learning robust, real-time, reactive robotic grasping.  _IJRR_ , 39(2-3):183–201, 2020.
  * Prattichizzo and Trinkle [2008] Domenico Prattichizzo and Jeffrey C. Trinkle.  Grasping.  In _Springer Handbook of Robotics_ , pages 671–700, 2008.
  * Rodriguez et al. [2012] Alberto Rodriguez, Matthew T Mason, and Steve Ferry.  From caging to grasping.  _IJRR_ , 31(7):886–900, 2012.
  * Sakamoto et al. [2021] Takumi Sakamoto, Weiwei Wan, Takao Nishi, and Kensuke Harada.  Efficient picking by considering simultaneous two-object grasping.  In _IROS_ , 2021.
  * Shenoy et al. [2021] Adheesh Shenoy, Tianze Chen, and Yu Sun.  Multi-object grasping - generating efficient robotic picking and transferring policy.  _CoRR_ , 2021.
  * Yamada et al. [2005a] T. Yamada, N. Mimura, and Y. Funahashi.  Grasp stability analysis of two objects with both friction and frictionless contacts in two dimensions.  In _IEEE International Symposium on Micro-NanoMechatronics and Human Science_ , 2005a.
  * Yamada et al. [2005b] T. Yamada, T. Ooba, T. Yamamoto, N. Mimura, and Y. Funahashi.  Grasp stability analysis of two objects in two dimensions.  In _ICRA_ , 2005b.
  * Yamada and Yamamoto [2015] Takayoshi Yamada and Hidehiko Yamamoto.  Static grasp stability analysis of multiple spatial objects.  _Journal of Control Science and Engineering_ , 3:118–139, 2015.
  * Yamada et al. [2009] Takayoshi Yamada, Shuichi Yamanaka, Manabu Yamada, Yasuyuki Funahashi, and Hidehiko Yamamoto.  Grasp stability analysis of multiple planar objects.  In _ROBIO_ , 2009.
  * Yamada et al. [2012] Takayoshi Yamada, Manabu Yamada, and Hidehiko Yamamoto.  Stability analysis of multiple objects grasped by multifingered hands with revolute joints in 2d.  In _IEEE International Conference on Mechatronics and Automation_ , 2012.
  * Yoshikawa et al. [2001] T. Yoshikawa, T. Watanabe, and M. Daito.  Optimization of power grasps for multiple objects.  In _ICRA_ , 2001.