Multi-Armed Bandit Models for 2D Grasp Planning with Uncertainty
Michael Laskey1 , Jeff Mahler1 , Zoe McCarthy1 , Florian T. Pokorny1 , Sachin Patil1 ,Jur van den Berg4 , Danica Kragic3 , Pieter Abbeel1 , Ken Goldberg2

Abstract— For applications such as warehouse order fulfillment, robot grasps must be robust to uncertainty arising fromsensing, mechanics, and control. One way to achieve robustness
is to evaluate the performance of candidate grasps by sampling
perturbations in shape, pose, and gripper approach and to compute the probability of force closure for each candidate to identify a grasp with the highest expected quality. Since evaluating
the quality of each grasp is computationally demanding, priorwork has turned to cloud computing. To improve computational
efficiency and to extend this work, we consider how MultiArmed Bandit (MAB) models for optimizing decisions can beapplied in this context. We formulate robust grasp planning
as a MAB problem and evaluate convergence times towards
an optimal grasp candidate using 100 object shapes from theBrown Vision 2D Lab Dataset with 1000 grasp candidates
per object. We consider the case where shape uncertainty isrepresented as a Gaussian process implicit surface (GPIS) with
Gaussian uncertainty in pose, gripper approach angle, andcoefficient of friction. We find that Thompson Sampling and
the Gittins index MAB methods converged to within 3% of the
optimal grasp up to 10x faster than uniform allocation and 5x
faster than iterative pruning.

I. I NTRODUCTION
Consider a robot fulfilling orders in a warehouse, where
it encounters new consumer products and must handle themquickly. While planning grasps using analytic methods requires knowledge of contact locations and surface normals, arobot may not be able to measure these quantities exactly due
to sensor imprecision and missing data, which could result
from occlusions, transparency, or highly reflective surfaces.
A common measure of grasp quality is force closure,the ability to resist external forces and torques in arbitrary
directions [28]. To cope with uncertainty, recent work has
explored computing the probability of force closure given
uncertainty in pose [9], [25], [43] and object shape [21],[30]. To compute the probability of force closure, MonteCarlo integration over sampled perturbations in the uncertain quantities can be applied [9], [22], [25], [43]. However, performing Monte-Carlo integration for each candidate
grasp hypothesis is computationally expensive. Past work
1 Department

of Electrical Engineering and Computer Sciences;{mdlaskey,
jmahler,pabbeel}@berkeley.edu

zmccarthy,

ftpokorny,sachinpatil,

2 Department

of Industrial Engineering and Operations Research andDepartment of Electrical Engineering and Computer Sciences; gold-

berg@berkeley.edu
1−2 University of California, Berkeley; Berkeley, CA 94720, USA
3 Computer Vision and Active Perception Lab, Centre for Autonomous
Systems, School of Computer Science and Communication, KTH RoyalInstitute of Technology, Stockholm, Sweden; dani@kth.se
4 Google; Amphitheatre Parkway, Mountain View, CA 94043, USA;jurvandenberg@gmail.com

Fig. 1: Number of samples (i.e. iterations of arm pulls) versus the normalized
probability of force closure PF for the best estimated grasp after t samples,PF (Γk̄,t ), out of 1000 candidate grasps using uniform allocation, iterative
pruning (eliminating candidates that perform poorly on initial samples), andour proposed Multi-Armed Bandit (MAB) algorithms (Gittins indices andThompson Sampling). The normalized PF is given by the ratio of PF (Γk̄,t )to the highest PF value in the candidate grasp set PF (Γ∗ ) averaged
over 100 independent runs on randomly selected objects from the Brown
Vision 2D Dataset [5]. The highest quality grasp was determined by brute
force search over all candidate grasps (which requires 10x more iterations
than all methods shown) [22]. Uniform allocation and iterative pruning
converge to within 3% of the highest quality grasp (the dashed grey line)
in approximately 40,000 and 20,000 iterations, respectively. In comparison,
the MAB methods both converge in approximately 4,000 iterations.

has looked at leveraging cloud computing to parallelize
this computation in order to overcome this problem andproposed a heuristic for adaptive sampling known as iterative
pruning [21], [22], [23]. In this work, we aim to extend
these methods by reducing the number of samples needed
to converge to a high-quality grasp.
Our main contribution is formulating the grasp selection
problem as a Multi-Armed Bandit (MAB) and showing that
it is possible to allocate sampling effort to grasps withan estimated higher probability of force closure [3], [26],[36]. A standard MAB has a set of possible options, or‘arms’ [3] that each return a numeric reward from a stationary distribution. The goal in a MAB problem is to select asequence of arm pulls to maximize the expected reward. We
formulate the problem of ranking a set of candidate grasps
according to a quality metric in the presence of uncertainty
as a MAB problem and consider the MAB algorithm as ananytime algorithm that terminates either once a user-defined
confidence level is met or at a given stopping time.

We study this formulation using probability of force
closure [9], [22], [43] as a quality metric under uncertainty
in pose, shape, gripper approach, and friction coefficient.
We model shape uncertainty using Gaussian process implicit
surfaces (GPISs), a Bayesian representation of shape uncertainty that has been used in various robotic applications [11],[18]. Uncertainty in pose is modeled as a normal distribution around the orientation and 2D position of the object
while uncertainty in grasp approach is modeled as a normal
distribution around the center and angle of the grasp axis
for a parallel jaw gripper. We furthermore model uncertainty
in friction coefficient as a normal distribution around an
expected friction coefficient.
We compare Thompson sampling and Gittins indices, twopopular algorithms for solving the MAB problem, against
uniform allocation and an adaptive sampling method known
as iterative pruning, which iteratively reduces the set ofcandidate grasps based on the sample mean [22], in termsof the number of samples needed to find a grasp withhighest estimated probability of force closure on objects
in the Brown Vision 2D Dataset, a dataset of 2D planar
objects [5], [9]. Our simulation results show that Thompson
Sampling, a MAB algorithm, required 5x fewer samples
than iterative pruning and 10x fewer samples than uniform
allocation to determine a grasp within 3% of the estimatedhighest probability of force closure grasp among a set of1000 grasp candidates per object and averaged over 100
objects.
II. R ELATED W ORK
Many works on grasp planning focus on finding grasps
by maximizing a grasp quality metric. Grasp quality is often
measured by the ability to resist external perturbations to
the object in wrench space [13], [33]. For example, Liuet al. used gradients on grasp metrics to guide a mutlifingered hand towards a grasp [29]. Analytical quality metrics typically assume precisely known object shape, object
pose, and locations of contact [8], [10]. Work on graspingunder uncertainty has considered uncertainty in the stateof a robotic gripper [16], [41] and uncertainty in contact
locations with an object [44]. Furthermore, recent work hasstudied the effects of uncertainty in object pose and gripper
positioning [4], [19].
Brook, Ciocarlie, and Hsiao [4], [19] studied a Bayesianframework to evaluate the probability of grasp success given
uncertainty in object identity, gripper positioning, and poseby simulating grasps on deterministic mesh and point cloudmodels. Weisz et al. [43] found that grasps ranked by probability of force closure subject to uncertainty in object pose
were empirically more successful on a physical robot thangrasps planned using deterministic wrench space metrics.
Similarly, Kim et al. [25] planned grasps using dynamic
simulations over perturbations in object pose and found thatthe planned grasps were more successful on a physical robot
than those planned with classical wrench space metrics.
Recent work has also studied uncertainty in object shape,
motivated by the use of low-cost sensors and tolerancesin part manufacturing. Christopoulos et al. [9] sampled
spline fits for 2-dimensional planar objects and ranked a
set of randomly generated grasps by probability of force
closure. Kehoe et al. [21], [22] sampled perturbations inshape for extruded polygonal objects to plan push grasps
for parallel-jaw grippers. Several recent works have alsostudied using Gaussian process implicit surfaces (GPISs)
to represent shape uncertainty motivated by its ability tomodel spatial noise correlations and to integrate multiple
sensing modalities [11], [12], [18], [30]. Dragiev et al. [11]uses GPIS to actively explore shapes with tactile sensing tofind a hand posture that aligned the gripper fingers to an
object’s surface normals [12]. Mahler et al. used the GPIS
representation to find locally optimal antipodal grasps whichframed grasp planning as an optimization problem [30].
Some probabilistic grasp quality measures, such as probability of force closure, are computed using Monte-Carlo integration [9], [22], [25], [43]. This approach involves samplingfrom distributions on uncertain quantities and averaging thequality over these samples to empirically estimate a probability distribution [6]. It can be computationally expensive
though to sample all proposed grasps to convergence. To
address this, Kehoe et al. [21] proposed an adaptive sampling
procedure called iterative pruning, which periodically discards a subset of the grasps that seem unlikely to be of highprobability of force closure. However, the method pruned
grasps using only the sample mean, which could discard
good grasps in practice. We propose modeling the problem
as a Multi-Armed Bandit, which selects the next grasp to
sample based on past observations instead [3], [26].
A. MAB Model
The MAB model, originally described by Robbins [36], isa statistical model of an agent attempting to make a sequenceof correct decisions while concurrently gathering information
about each possible decision. Solutions to the MAB model
have been used in applications for which evaluating all
possible options is expensive or impossible, such as the
optimal design of clinical trials [38], market pricing [37],and choosing strategies for games [40].
A traditional MAB example is a gambler with K independent one-armed bandits, also known as slot machines. Whenan arm is played (or “pulled” in the literature), it returns anamount of money from a fixed reward distribution that is
unknown to the gambler. The goal of the gambler is to comeup with a method to maximize the average rewards over all
pulls. If the gambler knew the arm with the highest expected
reward, the gambler would only pull that arm. However, since
the reward distributions are unknown, a successful gambler
needs to trade off exploiting the arm that currently yields thehighest expected reward and exploring new arms. Developinga policy that successfully trades between exploration andexploitation reward has been the focus of extensive research
since the problem formulation [3], [36].
At each time step, the MAB algorithm incurs regret, thedifference between the expected reward of the best arm
and that of the selected arm. Bandit algorithms minimizecumulative regret, the sum of regret over the entire sequenceof arm choices. Lai and Robbins [26] showed that the cumulative regret of the optimal solution to the bandit problem
is bounded by a logarithmic function of the number of arm
pulls. They presented an algorithm called Upper Confidence
Bound (UCB) that obtains this bound asymptotically [26].
The algorithm maintains a confidence bound on the distribution of reward based on prior observations and pulls thearm with the highest upper confidence bound.
In the robotics field, Hsu et al. applied MAB models
to improve the performance and reduce computation timeof the probabilistic roadmap motion planner by adaptively
sampling waypoints [20]. Matikainen et al. formulated policy
learning as choosing a state machine from a known libraryof state machines. They then used a MAB algorithm toimprove the computational speed of finding the best statemachine [31]. Lauri and Ritala used MAB models to solve a
relaxed mixed observable POMDP problem and achieve an
efficient solution [27].
B. Bayesian Algorithms for MAB
We consider Bayesian MAB algorithms that use previous
samples to form a belief distribution on the parameters specifying the distribution of each arm [1], [42]. Bayesian methods have been shown empirically to outperform UCB [7],[2]. Bayesian algorithms maintain a belief distribution on
the arm payoff for each of the arms. For instance a Bernoulli
random variable p can be used to represent a binary grasping
metric like force closure. The prior typically placed on a
Bernoulli variable is its conjugate prior, the Beta distribution.
Beta distributions are specified by shape parameters α andβ, where (α > 0 and β > 0).
One benefit of the Beta prior on Bernoulli reward distributions is that updates to the belief distribution after observing
rewards from arm pulls can be derived in closed form.
At timestep t = 0, we pull arm k and observe reward
Rk,0 , where Rk,0 ∈ {0, 1}. The posterior of the Beta
distribution after this observation is αk,1 = αk,0 + Rk,0 ,βk,1 = βk,0 + 1 − Rk,0 , where αk,0 and βk,0 are the prior
shape parameters for arm k before any samples are evaluated.
Given the current belief αk,t , βk,t for an arm k at time t,
the expected Bernoulli parameter, p̄k,t , is:p̄k,t =

#Successes + αk,0αk,t=.
αk,t + βk,t#Trials + αk,0 + βk,0Methods such as Value Iteration can compute optimal
policies for a discrete MDP with respect to the discountfactor γ [3]. However, the curse of dimensionality affects
performance because for K arms, a finite horizon of T , anda Beta-Bernoulli distribution on each arm, the state space isexponential in size with respect to K. Using the fact thatpulling an arm only changes the state of the arm pulled,
Gittins showed that instead of solving the K-dimensional
MDP one can solve K 1-dimensional optimization problems
for each arm k and for each state xk,t = {αk,t , βk,t } up toa timestep T [42].
The solution to the optimization problem assigns each state
an index v(xk,t ), which can be thought of as the expectedvalue for each state. The indices can then be used to forma policy, where at each timestep the agent selects the arm
kt where kt = argmax v(xk,t ). The indices for the Beta1≤k≤K

Bernoulli case are computed offline and can be found in[14]. We refer the reader to [14] for a more detailed analysisof the Gittins index method.
2) Thompson Sampling: The computational cost of determining the Gittins indices can increase exponentially as thediscount factor approaches 1. However, in the case of finding
the best arm, we want to plan for long-term reward andthus want γ as close to 1 as possible. Due to computational
constraints we must use a smaller γ, but this can lead tothe algorithm pulling only the most promising arm for many
iterations [24].
Algorithm 1: Thompson sampling for Beta-Bernoulli
Process
Result: Current Best Arm, Γ∗Initialize Beta(αk,0 = 1,βk,0 = 1) ∀k ∈ K
for t=1,2,...,T do
Draw pk,t ∼ Beta(αk,t ,βk,t ) for k = 1, ..., K
Pull arm kt = argmax pk,tk∈KObserve reward Rk,t ∈ {0, 1}
if k = kt then
αk,t+1 ← αk,t + Rkt ,tβk,t+1 ← βk,t + 1 − Rkt ,telse
αk,t+1 ← αk,tβk,t+1 ← βk,t(1)

All arms are initialized with prior Beta distributions, which
is normally Beta(αk,0 = 1, βk,0 = 1) for k ≤ K to reflect a
uniform prior on the parameter of the Bernoulli distribution,
pk,0 .
1) The Gittins Index Method: One MAB method is to treat
the problem as a Markov Decision Process (MDP) and touse Markov Decision theory. Formally, a MDP is defined bysets of states, actions, transition probabilities between states,
a reward function, and a discount factor [3]. In the BetaBernoulli MAB case, the set of actions consists of K arms
and the set of states are the Beta posterior on each arm, or
the values of αk,t and βk,t .

Thompson sampling is an alternative to the Gittins index
method that is not prone to this problem. In Thompson
sampling, for each arm draw pk,t ∼ Beta(αk,t , βk,t ) and pull,
the arm with the highest pk,t is drawn. A reward, Rk,t , isthen observed and the corresponding Beta distribution is updated. Sampling from a Beta distribution is computationallyinexpensive and implemented in most scientific computing
libraries [32]. Thompson sampling does make an assumptionthat sampling from the Beta distribution for each arm issignificantly computationally cheaper than actually pulling
an arm. The full algorithm is shown in Algorithm 1.
The intuition for Thompson sampling is that the randomFig. 2: Illustration of our grasping model for parallel jaw grippers on amechanical switch. Jaw placements are illustrated by rectangles closing
along the dashed line. A grasp plan centered at y (plus symbol) at angle
ψ consists of 2D locations for each of the parallel jaws j1 and j2 . Whenfollowing the grasp plan, the jaws contact the object at locations c1 andc2 , and the object has outward pointing unit surface normals n1 and n2
at these locations. Together with the center of mass of the object z, thesevalues can be used to determine the forces and torques that a grasp canapply to an object.

samples of pk,t allow the method to explore. However, as
more samples are received, the method focuses on promisingarms, since the Beta distributions approach delta distributions
as the number of samples drawn tends towards infinity [1].
Chapelle et al. demonstrated empirically that Thompson
sampling achieved lower cumulative regret than traditional
bandit algorithms like UCB for the Beta-Bernoulli case [7].
Agrawal et al. recently proved an upper bound on theasymptotic complexity of cumulative regret for Thompson
sampling that is sub-linear for k-arms and logarithmic in thecase of 2 arms [1].
III. G RASP P LANNING P ROBLEM D EFINITION
We consider grasping a rigid planar object from above
using parallel-jaw grippers. We assume that the interaction
between the gripper and object is quasi-static [21], [22]. We
consider uncertainty in shape, pose, gripper approach, andfriction coefficient. We assume that the distributions on thesequantities are given and can be sampled from. While we only
consider grasping planar objects, our method can work onplanar slices of a 3D object.
A. Candidate Grasp Model
The grasp model is illustrated in Fig. 2. We formulate theMAB problem for planar objects using parallel-jaw grippers
as modeled in Fig. 2. Similar to [30], we parameterize agrasp using a grasp axis, the axis of approach for two jaws,
with jaws of width wj ∈ R and a maximum width wg ∈ R.
The two location of the jaws can be specified as j1 , j2 ∈ R2 ,where ||j1 − j2 ||2 ≤ wg . We define a grasp consisting of thetuple Γ = {j1 , j2 }.
Given a grasp and an object, we define the contact points
as the spatial locations at which the jaws come into contact
with the object when following along the grasp axis, c1 , c2 ∈R2 . We also refer to the unit outward pointing surface
normals at the contact points as n1 , n2 ∈ R2 , the object

Fig. 3: A graphical model of the relationship between the uncertain
parameters we consider. Uncertainty in object shape θ, object pose ξ, andgrasp approach angle ρ affect the points of contact c with the object andthe surface normals n at the contacts. Uncertainty in friction µ coefficientaffects the forces and torques used to compute our quality measure, theprobability of force closure PF . The shaded nodes denote the observed
values.

center of mass as z ∈ R2 and the friction coefficient asµ ∈ R.
B. Sources of Uncertainty
We consider uncertainty in object shape, object pose, grasp
approach angle, and friction coefficient. Fig. 3 illustrates agraphical model of the relationship between these sources of
uncertainty. In this section, we describe our model of eachsource of uncertainty.
1) Shape Uncertainty: Uncertainty in object shape resultsfrom sensor imprecision and missing sensor data, which canoccur due to transparency, specularity, and occlusions [30].
Following [30], we represent the distribution over possible
surfaces given sensing noise using a Gaussian process implicit surface (GPIS). A GPIS represents a distribution oversigned distance functions (SDFs). A SDF is a real-valued
function over spatial locations f : R2 → R that is greaterthan 0 outside the object, 0 on the surface and less than 0
inside the object. A GPIS is a Gaussian distribution over SDF
values at a fixed set of query points X = {x1 , ...xn }, xi ∈R2 , f (xi ) ∼ N (µf (xi ), Σf (xi )), where µf (·) and Σf (·)
are the mean and covariance functions of the GPIS [35].
See Mahler et al. for details on how to estimate a mean andcovariance function and sample shapes from a GPIS [30].
For convenience, in later sections we will refer to the GPIS
parameters as θ = {µf (x), Σf (x)}.
2) Pose Uncertainty: In 2-dimensional space, the poseof an object T is defined by a rotation angle φ and thetwo translation coordinates t = (tx , ty ), summarized inparameter vector ξ = (φ, t)T ∈ R3 . We 
assume Gaussianˆ Σξ , where ξˆ
uncertainty on the pose parameters ξ ∼ N ξ,
corresponds to the expected pose of the object.
3) Approach Uncertainty: In practice, a robot may not
be able to execute a desired grasp Γ = {ji , j2 } exactly due
to errors in actuation or feedback measurements used for
trajectory following [21]. We model approach uncertainty
as Gaussian uncertainty around the angle of approach andcentroid of a straight line grasp Γ. Formally, let ŷ = 21 (j1 +j2 ) denote the center of a planned grasp axis and ψ̂ denotethe clockwise angle that the planned axis j1 − j2 makeswith the y-axis of the 2D coordinate system on our shape
representation. We model uncertainty in the approach centeras y ∼ N (ŷ, Σy ) and uncertainty in the approach angle asψ ∼ N (ψ̂, σψ2 ). To shorten notation, the remainder of thispaper we will refer to the uncertain approach parametersas ρ = {y, ψ}. In practice Σ2y and σψ2 can be set fromrepeatability measurements for a robot [34].
4) Friction Uncertainty: As shown in [17], [44], uncertainty in friction coefficient can cause grasp quality to significantly vary. However, friction coefficients may be uncertain
due to factors such as the presence of material between agripper and an object (e.g. dust, water, moisture), variationsin the gripper material due to manufacturing tolerances, ordue to a misclassification of the object surface to be grasped.
We model uncertainty in friction coefficient as Gaussian
noise, µ ∼ N (µ̂, σµ2 ).

metric. We refer to this as a brute force approach. Thismethod has been evaluated for shape uncertainty [9], [21]and pose uncertainty [43] but may require many samples
for each of a large set of candidates to converge to the true
value. More recent work has considered adaptive sampling
to discard grasps that are not likely to be optimal without
fully evaluating their quality [22].
To try and reduce the number of samples needed, we
instead maximize the sum of PF values for each sampled
grasp Γk,t at time t up to a given time Ts :maxΓk,∗ ∈GTsX

PF (Γk,t )

(3)

t=1

The goal is to perform as well as Equation 2 in as few
samples as possible [39]. We then formulate the problem
as a MAB model and compare two different Bayesian MAB
algorithms, Thompson sampling and Gittins indices.
IV. G RASP P LANNING AS A M ULTI -A RMED BANDIT

C. Grasp Quality
We measure the quality of a grasp using the notion ofprobability of force closure [21], [22], [25], [43] given agrasp Γ. Force closure is considered as a binary-valued
quantity F that is 1 if the grasp can resist wrenches inarbitrary directions and 0 otherwise. Let W ∈ R3 denotethe contact wrenches derived from contact locations c1 , c2 ,normals n1 , n2 , friction coefficient µ, and center of mass
z for a given grasp and shape. If the origin lies within theconvex hull of W, then the grasp is in force closure [28].
We rank grasps using the probability of force closure given
uncertainty in shape, pose, robot approach, and friction
coefficient [9], [22]:PF (Γk ) = P (F = 1|Γk , θ, ξ, ρ, µ) .
To estimate PF (Γk ), we first generate samples from the
distributions on θ, ξ, ρ, and µ. Using the relationships definedby the graphical model in Fig. 3, we next compute thecontact locations c1 , c2 given a sampled SDF, pose, andgrasp approach by ray tracing along the grasp axis definedby Γk = {j1 , j2 } [30]. We then compute the surface normals
n1 , n2 at the contacts using the gradient of the sampled SDF
at the contact locations. Finally, we use these quantities tocompute the forces and torques that can be applied to form
the contact wrench set W and evaluate the force closure
condition [28].
D. Objective
Given the sources of uncertainty and their relationships
as described above, the grasp planning objective is to find agrasp that maximizes the probability of force closure from a
set of candidate grasps G = {Γ1 , ..., ΓK }:Γ∗ = argmax PF (Γk )

(2)

Γk ∈G

One method to approximately find such a grasp is toexhaustively evaluate PF (Γk ) for all grasp in G using MonteCarlo integration and then sort the plans by this quality

We frame the grasp selection problem of Section III-D as
a MAB problem. Each arm corresponds to a different grasp,
Γk , and pulling an arm corresponds to sampling from thegraphical model in Fig. 3 and evaluating the force closure
condition. Since force closure is a binary value, each grasp
Γk has a Bernoulli reward distribution with probability offorce closure, PF (Γk ). In a MAB, we want to minimize
cumulative regret which is an equivalent objective to theobjective of Equation 3.
The proposed algorithm is an anytime algorithm because
it can be stopped at any point during its computation to
return the current estimate of the best grasp or wait until
a 95% confidence interval is smaller than some threshold .
Using the quantile function of the beta distribution, B, we
can measure the 95% confidence interval as:
B(0.025, αk,t , βk,t ) ≤ PF (Γk,t )) ≤ B(0.975, αk,t , βk,t ).

(4)

To summarize, the algorithm terminates and returns k̄, ora grasp that has the highest estimated PF when t ≥ Ts or|B(0.025, αk̄,t , βk̄,t ) − B(0.975, αk̄,t , βk̄,t )| ≤ .
V. S IMULATION E XPERIMENTS
We used the Brown Vision Lab 2D dataset [5] of 2D
objects as in [9]. We downsampled the silhouette by afactor of 2 to create a 40 x 40 occupancy map, whichcontained 1 if the object was observed and 0 if it was
not observed. We computed a quadtree representation of the
SDF and removed information about the SDF on grid cells
corresponding to uniformly chosen quadtree cells to simulate
localized uncertainty in shape perception. We then construct
a GPIS using the same method as proposed in [30]. The
noise parameters in approach, pose, and friction coefficientwere set to the following variances: σψ2 = 0.2 rads2 , σy2 = 3
grid cells2 , σµ2 = 0.4, σφ2 = 0.3 rads2 and σt2 = 3 grid cells2 .
We performed experiments for the case of two hard contacts
in 2-D. We drew random grasps Γ by uniformly samplingthe√ angle of the grasp axis around a circle with radius
2M , where M is the dimension of the workspace, and thensampling the circle’s origin from a zero mean Gaussian withvariance 10 units2 . All experiments were run on a machinewith OS X with a 2.7 GHz Intel core i7 processor and 16
GB 1600 MHz memory in Matlab 2013b. Figure 5 displays
examples of GPIS models using the GPIS-Blur method [30]as well as resulting grasp samples.
A. Multi-Armed Bandit Experiments
For our experiments, we consider selecting an optimal
grasp among |G| = 1000 candidates per object. We draw
samples from our graphical model using the technique described in Sec. III-C. We calculated the expected performance over 100 randomly selected shapes in the Brown Vision Lab 2D dataset and for the grasps planned by Thompson
sampling, Gittins indices, iterative pruning [22] and uniform
allocation. Uniform allocation selects a grasp at random fromthe set to sample the next candidate and thus does not use any
prior information. Iterative pruning prunes grasps every 1000
iterations based on lowest sample mean and removes 10% of
the current grasp set. We set the discount factor γ = 0.98 for
the Gittins method, which was the highest we could computein a reasonable amount of time due to the exponential growthin computation time with respect to γ [14].
In Fig. 1, we plot time t vs. P (Γk̄,t )/P (Γ∗ ), the normalized probability of force closure for the grasp returned by
the algorithm. Non-MAB methods such as uniform sampling
and iterative pruning (eliminating candidate grasps basedon sample mean) eventually converge to within 3% of the
optimal grasp, requiring approximately 40,000 and 20,000
iterations. Gittins indices and Thompson sampling perform
significantly better, converging after only 4000 iterations.
In Fig. 5, we select a stopping time Ts = 10, 000, whichcorresponds to 10 samples per grasp on average, and foreach method visualize the grasp returned, Γk̄,10,000 .
The time per iteration is ti = ta + tp , where ta is thetime to decide which arm to pull next and tp is the time
taken to draw a sample from the graphical model in Fig.
3. The time per iteration for Thompson sampling, Gittins
indices, iterative pruning and uniform allocation is 31.6,
31.2, 30.4 and 30.2 ms. Most of ti is dominated by sampling
time, since tp ≈ 30 ms. Sampling from our graphicalmodel in Fig. 3 involves drawing samples form a GPIS, ahigh dimensional Gaussian, and evaluating the probabilityof force closure metric. The MAB algorithm can also be
terminated when the 95% confidence interval around thereturned grasp (see Equation 4) is below a set threshold in size. We plot the algorithm’s confidence intervals aroundthe returned grasp PF (Γk̄ ) vs. the number of samples drawn
in Fig. 4 for the Gittins index method, Thompson sampling,
iterative pruning [22] and uniform allocation. As illustrated,the confidence interval for Thompson sampling and Gittins
indices converges at a faster rate than the other two methods.
B. Sensitivity Analysis
We also analyze the performance of Thompson samplingunder variations in noise from friction coefficient uncertainty,
shape uncertainty, rotational pose, and translation pose. We

Fig. 4: Number of samples versus the algorithm’s 95% confidence intervals
from Eq. 4 on the probability of force closure of the best estimated grasp
after t samples using uniform allocation, iterative pruning, Gittins indices,
and Thompson Sampling. The values are averaged over 100 independentruns on randomly selected objects from the Brown Vision 2D Dataset [5]with 1,000 candidate grasps for each object. An increasingly narrow confidence interval indicates that the algorithm allocated an increasing numberof samples to its estimate of the best grasp.

Fig. 6: Number of samples versus the probability of force closure of the best
estimated grasp after t samples PF (Γk̄,t ) using uniform allocation, iterative
pruning, Gittins indices, and Thompson sampling over 1,000 candidate
grasps. We generated 1,000 samples for each grasp hypothesis from thegraphical model. For the top 500 grasp hypotheses, we sorted samples
such that unstable samples preceeded force closed samples and, for thebottom 500 grasp hypotheses, we sorted samples such that stable grasps
preceeded unstable grasps. This provides misleading observations to thebandit algorithms. The normalized PF is the ratio of the best estimatedgrasp at iteration t, PF (Γk̄,t ), to the highest PF in the candidate grasp
set PF (Γ∗ ) averaged over 100 independent runs on randomly selected
objects from the Brown Vision 2D Dataset [5]. The highest quality grasp wasdetermined by brute force search over all candidate grasps (which required
10x more iterations than any of these methods [22]). The results suggestthat when samples are misleadingly ordered, the best policy is uniform
allocation.

increase the variance parameters across a set range for eachparameter to simulate low, medium and high levels of noise.
All experiments were averaged across 100 objects randomly
selected from the Brown dataset with |G| = 1000.
For the friction coefficient, we varied σµ2 across the values{0.05, 0.2, 0.4}. As illustrated in Table 1, the performanceof the bandit algorithm remains largely unchanged, with

Fig. 5: We show two objects from the Brown 2D dataset [5] where data is omitted at randomly chosen rectangular nodes of a quadtree representation.
The resulting GPIS models are visualized using GPIS-Blur [30], where uncertain areas appear more blurry. Grasps with the highest estimated normalized
probabilty of force closure PF after 10,000 samples using uniform allocation, iterative pruning, Gittins indices, and Thompson sampling are displayed.
For reference, we also show the grasp with highest PF after brute force evaluation using 100,000 samples and the nominal shape. The candidate grasp set
was of size |G| = 1000 for each object.

typical convergence to zero in simple regret in less than 5000
iterations. For rotational uncertainty in pose, we varied σφ2across the set {0.03, 0.12, 0.24} radians2 . As illustrated inTable 1, the performance of the bandit algorithms is affectedby the change in rotation. An increase in variance to 0.24
radians2 causes the simple regret to not converge until around6432 samples or an average of 6.4 samples per grasp.
For translational uncertainty in pose, we varied σt2 in therange of {3, 12, 24} units2 (on a 40 x 40 unit workspace).
Our results indicate that the performance of the bandit
algorithms is affected by a change in translation and anincreased noise of σt2 = 24 causes the algorithm to notconverge until 8763 evaluations for Thompson sampling.
C. Worst Case
The MAB algorithms use the observations of samples
drawn to decide which grasp to sample next from. To show
worst case performance under such a model, we generated
1000 samples for each grasp hypothesis from the graphicalmodel. For the top 500 grasp hypotheses, we sorted samples
such that unstable samples (F = 0) preceeded force closed(F = 1) samples and, for the bottom 500 grasp hypotheses,
we sorted samples such that stable grasps preceeded unstablegrasps. This provides misleading observations to the bandit
algorithms. We demonstrate in Fig. 6 a case where theobservations are misleading. As illustrated in Fig. 6, allmethods are affected by worst case performance. The results
suggest that, when the observations are misleading, thepreferred policy is uniform allocation of grasp samples.
VI. D ISCUSSION AND F UTURE W ORK
In this work, we proposed a multi-armed bandit approachto efficiently identify high-quality grasps under uncertainty inshape, pose, friction coefficient and approach. A key insight

Uncertainty
Type
Orientation σφ
Position σt
Friction σµ# of Samples Until Convergence
Low
MediumHigh
Uncertainty
Uncertainty
Uncertainty
4230
5431
6432
4210
5207
8763
4985
4456
4876

TABLE I: Number of iterations until convergence to within 3% of grasp withthe highest estimated probability of force closure PF for Thompson sam2 = {0.03, 0.12, 0.24}
pling under uncertainty in the object orientation σφ2
2
radians , uncertainty in the object position σt = {3, 12, 24} units2 , and
2 = {0.05, 0.2, 0.4} on a 40×40 grid
uncertainty in friction coefficient σµaveraged over 100 independent runs on random objects from the Brown
Vision 2D Dataset. High variance in position and orientation uncertainty
increases the amount of iterations needed for the bandit algorithm toconverge.

from our work is that exhaustively sampling each grasp isinefficient, and we found that a MAB approach gives priority
to promising grasps and can reduce computational time.
Initial results have shown MAB algorithms to outperformthe methods of prior work, uniform allocation and iterative
pruning [21], [22] in terms of finding a higher quality grasp
faster. However, as shown in Fig. 6, there are some pathological cases that can mislead bandit algorithms to focus samples
on the wrong grasps. Fortunately, the probability of manysuccessive samples being misleading rapidly approaches zeroas the time horizon is increased.
In future work, we plan to scale our method to 3D objects.
This could substantially increase the number of candidate
grasps, further motivating the use of cloud computing. Glazebrook and Wilkinson showed that the Gittins index method
could be parallelized by simply dividing the arms into M
subsets, where M is the number of cores, and solving
each MAB separately. [15]. A similar method could also be
applied for Thompson sampling. Another promising scheme
for parallelizing the MAB is to sample M arms at each
iteration. We will explore both of these approaches in futurework.

VII. ACKNOWLEDGMENTS
This work is supported in part by the U.S. National Science Foundation under Award IIS-1227536, NSF-Graduate
Research Fellowship, and by grants from Google. We thankthe AMPLab, UC Berkeley and our colleagues who gave
feedback and suggestions, in particular Sanjay Krishnan,Peter Bartlett, Steve McKinley and Dylan Hadfield-Menell.
R EFERENCES[1] S. Agrawal and N. Goyal, “Analysis of thompson sampling for themulti-armed bandit problem,” arXiv preprint arXiv:1111.1797, 2011.
[2] P. Bachman and D. Precup, “Greedy confidence pursuit: A pragmatic
approach to multi-bandit optimization,” in Machine Learning andKnowledge Discovery in Databases. Springer, 2013, pp. 241–256.
[3] A. G. Barto, Reinforcement learning: An introduction. MIT press,
1998.
[4] P. Brook, M. Ciocarlie, and K. Hsiao, “Collaborative grasp planning with multiple object representations,” in Proc. IEEE Int. Conf.
Robotics and Automation (ICRA). IEEE, 2011, pp. 2851–2858.
[5] Brown University Vision Lab, “2d planar database,” https://vision.
lems.brown.edu/content/available-software-and-databases.
[6] R. E. Caflisch, “Monte carlo and quasi-monte carlo methods,” Acta
numerica, vol. 7, pp. 1–49, 1998.
[7] O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,” in Advances in Neural Information Processing Systems, 2011,
pp. 2249–2257.
[8] J.-S. Cheong, H. Kruger, and A. F. van der Stappen, “Output-sensitive
computation of force-closure grasps of a semi-algebraic object,” vol. 8,
no. 3, pp. 495–505, 2011.
[9] V. N. Christopoulos and P. Schrater, “Handling shape and contact
location uncertainty in grasping two-dimensional planar objects,” inIntelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on. IEEE, 2007, pp. 1557–1563.
[10] M. T. Ciocarlie and P. K. Allen, “Hand posture subspaces for dexterous
robotic grasping,” Int. J. Robotics Research (IJRR), vol. 28, no. 7, pp.
851–867, 2009.
[11] S. Dragiev, M. Toussaint, and M. Gienger, “Gaussian process implicit
surfaces for shape estimation and grasping,” in Proc. IEEE Int. Conf.
Robotics and Automation (ICRA), 2011, pp. 2845–2850.
[12] ——, “Uncertainty aware grasping and tactile exploration,” in Robotics
and Automation (ICRA), 2013 IEEE International Conference on.
IEEE, 2013, pp. 113–119.
[13] C. Ferrari and J. Canny, “Planning optimal grasps,” in Proc. IEEE Int.
Conf. Robotics and Automation (ICRA), 1992, pp. 2290–2295.
[14] J. Gittins, K. Glazebrook, and R. Weber, Multi-armed bandit allocation
indices. John Wiley & Sons, 2011.
[15] K. Glazebrook and D. Wilkinson, “Index-based policies for discounted
multi-armed bandits on parallel machines,” Annals of Applied Probability, pp. 877–896, 2000.
[16] K. Y. Goldberg and M. T. Mason, “Bayesian grasping,” in Robotics andAutomation, 1990. Proceedings., 1990 IEEE International Conference
on. IEEE, 1990, pp. 1264–1269.
[17] K. Hang, F. T. Pokorny, and D. Kragic, “Friction coefficients andgrasp synthesis,” in IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS), Tokyo, Japan, 2013.
[18] G. A. Hollinger, B. Englot, F. S. Hover, U. Mitra, and G. S. Sukhatme,“Active planning for underwater inspection and the benefit of adaptivity,” Int. J. Robotics Research (IJRR), vol. 32, no. 1, pp. 3–18, 2013.
[19] K. Hsiao, M. Ciocarlie, and P. Brook, “Bayesian grasp planning,” in
ICRA 2011 Workshop on Mobile Manipulation: Integrating Perception
and Manipulation, 2011.
[20] D. Hsu, G. Sánchez-Ante, and Z. Sun, “Hybrid prm sampling witha cost-sensitive adaptive strategy,” in Robotics and Automation, 2005.
ICRA 2005. Proceedings of the 2005 IEEE International Conference
on. IEEE, 2005, pp. 3874–3880.
[21] B. Kehoe, D. Berenson, and K. Goldberg, “Estimating part tolerance
bounds based on adaptive cloud-based grasp planning with slip,” in Automation Science and Engineering (CASE), 2012 IEEE International
Conference on. IEEE, 2012, pp. 1106–1113.
[22] ——, “Toward cloud-based grasping with uncertainty in shape: Estimating lower bounds on achieving force closure with zero-slip pushgrasps,” in Robotics and Automation (ICRA), 2012 IEEE International
Conference on. IEEE, 2012, pp. 576–583.

[23] B. Kehoe, S. Patil, P. Abbeel, and K. Goldberg, “A survey ofresearch on cloud robotics and automation,” Automation Science andEngineering, IEEE Transactions on, vol. 12, no. 2, pp. 398–409, 2015.
[24] F. Kelly et al., “Multi-armed bandits with discount factor near one:The bernoulli case,” The Annals of Statistics, vol. 9, no. 5, pp. 987–
1001, 1981.
[25] J. Kim, K. Iwamoto, J. J. Kuffner, Y. Ota, and N. S. Pollard,“Physically-based grasp quality evaluation under uncertainty,” inRobotics and Automation (ICRA), 2012 IEEE International Conference
on. IEEE, 2012, pp. 3258–3263.
[26] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation
rules,” Advances in applied mathematics, vol. 6, no. 1, pp. 4–22, 1985.
[27] M. Lauri and R. Ritala, “Optimal sensing via multi-armed bandit
relaxations in mixed observability domains,” in Robotics and Automation, 2015. ICRA 2015. Proceedings of the 2005 IEEE International
Conference on. IEEE, 2015.
[28] Z. Li and S. S. Sastry, “Task-oriented optimal grasping by multifingered robot hands,” Robotics and Automation, IEEE Journal of, vol. 4,
no. 1, pp. 32–44, 1988.
[29] G. Liu, J. Xu, X. Wang, and Z. Li, “On quality functions for grasp
synthesis, fixture planning, and coordinated manipulation,” Automation
Science and Engineering, IEEE Transactions on, vol. 1, no. 2, pp.
146–162, 2004.
[30] J. Mahler, S. Patil, B. Kehoe, J. van den Berg, M. Ciocarlie, P. Abbeel,and K. Goldberg, “Gp-gpis-opt: Grasp planning under shape uncertainty using gaussian process implicit surfaces and sequential convex
programming.”[31] P. Matikainen, P. M. Furlong, R. Sukthankar, and M. Hebert, “Multiarmed recommendation bandits for selecting state machine policies
for robotic systems,” in Robotics and Automation (ICRA), 2013 IEEE
International Conference on. IEEE, 2013, pp. 4545–4551.
[32] MATLAB, version 7.10.0 (R2010a).
Natick, Massachusetts: The
MathWorks Inc., 2010.
[33] A. T. Miller and P. K. Allen, “Graspit! a versatile simulator for robotic
grasping,” Robotics & Automation Magazine, IEEE, vol. 11, no. 4, pp.
110–122, 2004.
[34] B. Mooring and T. Pack, “Determination and specification of robot
repeatability,” in Robotics and Automation. Proceedings. 1986 IEEE
International Conference on, vol. 3. IEEE, 1986, pp. 1017–1023.
[35] C. Rasmussen and C. Williams, Gaussian processes for machinelearning. MIT Press, 2006.
[36] H. Robbins, “Some aspects of the sequential design of experiments,”
in Herbert Robbins Selected Papers. Springer, 1985, pp. 169–177.
[37] M. Rothschild, “A two-armed bandit theory of market pricing,” Journalof Economic Theory, vol. 9, no. 2, pp. 185–202, 1974.
[38] R. Simon, “Optimal two-stage designs for phase ii clinical trials,”
Controlled clinical trials, vol. 10, no. 1, pp. 1–10, 1989.
[39] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger, “Gaussian
process optimization in the bandit setting: No regret and experimental
design,” arXiv preprint arXiv:0912.3995, 2009.
[40] D. L. St-Pierre, Q. Louveaux, and O. Teytaud, “Online sparse bandit
for card games,” in Advances in Computer Games. Springer, 2012,
pp. 295–305.
[41] F. Stulp, E. Theodorou, J. Buchli, and S. Schaal, “Learning to grasp
under uncertainty,” in Robotics and Automation (ICRA), 2011 IEEE
International Conference on. IEEE, 2011, pp. 5703–5708.
[42] R. Weber et al., “On the gittins index for multiarmed bandits,” The
Annals of Applied Probability, vol. 2, no. 4, pp. 1024–1033, 1992.
[43] J. Weisz and P. K. Allen, “Pose error robust grasping from contact
wrench space metrics,” in Robotics and Automation (ICRA), 2012
IEEE International Conference on. IEEE, 2012, pp. 557–562.
[44] Y. Zheng and W.-H. Qian, “Coping with the grasping uncertainties
in force-closure analysis,” Int. J. Robotics Research (IJRR), vol. 24,
no. 4, pp. 311–327, 2005.