IEEE Robotics & Automation Magazine - June 2015 - 45

q d Q is a configuration for the manipulator (e.g., a sevendimensional configuration for a Baxter arm), p is the configuration of the single object (a six-dimensional rigid body configuration), and t specifies the type of the manipulation state,
i.e., a transfer or a transit. The roadmap is a graph with vertices
that correspond to individual manipulation states and edges
that correspond to local paths connecting such states.
A transfer state is a state where the manipulator is grasping
the object. A transit state is a state where the object is in a stable configuration without any forces exerted by the manipulator. In a transit state, the manipulator may not be grasping the
object. A transition state corresponds to stable grasps and is
both a transfer and a transit state (see Figure 3). Thus, a multimodal roadmap is needed for manipulation, which contains
two types of nodes. The nodes correspond to transfer and
transit states. The edges between nodes of the first type correspond to the robot transferring an object, while the edges
between nodes of the second type correspond to the robot
moving in the environment while the object is placed in a stable configuration. An edge reaching a transition state leads to
the robot grasping an object in a stable configuration.
A popular approach for generating such roadmaps is to
follow a sampling-based process, such as in the Probabilistic
Roadmap Method (PRM) [9]. The nodes/states of the roadmap are sampled, and an attempt is made to connect pairs of
neighboring nodes according to a metric as long as the edge/
local path between the two nodes in the pair is collision-free.
In the context of manipulation, the first step in the construction of the manipulation roadmap R is to sample transition
states. This can be achieved by first sampling a stable, collision-free object configuration p and then using inverse kinematics to define the corresponding manipulator's grasping
configuration q (Figure 4). If the inverse kinematics function
returns a solution and the resulting configuration (q, p) is
collision-free, then two states are generated with the same
configuration: one of the transit type and one of the transfer
type. Both of these states are inserted in R, and an edge is
added between them.
Given the set of transition states and edges, the method
needs to proceed to separately explore the transit and the transfer subset of the state space in a PRM fashion. For the transit
component, additional grasping configurations for the manipulator are sampled, where the object is no longer required to be
in a stable configuration. Then, neighboring transit states
according to a configuration space metric are considered for
connection by interpolating between the two configurations. If
the interpolated path is collision-free, the edge is added to the
roadmap. The same process is repeated for transfer states. The
objective is to achieve a roadmap that has the minimum number of connected components so that the manipulator is able to
transfer objects among the sampled transition states.
Using a Precomputed Roadmap
To effectively utilize the roadmap R, which is computed on
the cloud and on the local workstation, a lazy evaluation process for computing the shortest collision-free path is helpful.

Algorithm 1. LazyEval ^R^V, Eh, S, x s, x g h.

# ShortestPath ^R^V, Eh, x s, x gh;
while r ! 4 and ColFree ^r, Sh ! True do

1 r
2
3
4
5

for e d E + r so that ColFree ^e, Sh = False do
E = E\e;

r ! Shortest Path ^R^V, E h, x s, x g h;

6 return r;

In particular, Algorithm 1 provides an outline of the operation on the local workstation. The algorithm assumes the
availability of the manipulation roadmap R (V, E) that has
been computed and transmitted by the cloud. The algorithm
also has access to the latest local-sensing data S. The sensing
data can be in the form of an unfiltered point cloud, which
can be used by appropriate software packages [18] to perform
collision checking given a manipulation state x for the robot
and the object. This means that no expensive processes for
modeling the world need to be executed on the local workstation since raw data can be used directly.
The algorithm starts by searching the roadmap for a solution path r from the start manipulation state x s to goal one
x g (Line 1). This typically entails a heuristic search process
on the graph. The shortest path r on the roadmap is then
tested for collisions given the latest sensing data S (Line 2).
If the path is collision-free, then it can be returned (Lines 2
and 6). If it is not, then all the edges e d E of R that were
used by the path r are removed (Lines 3 and 4). Then, a new
solution path is computed on the updated roadmap (Line 5).
If no solution path is found after the removal of edges, a failure to find a solution is reported by returning an empty path
(Lines 2 and 6).
Every time that the process of Algorithm 1 is completed,
any edges that have been removed from the roadmap are
reinserted as they may be useful in consecutive queries and

Figure 4. The transition states for a Baxter robot and an object
corresponding to stable grasping configurations. Given the object
placement and grasp, an inverse kinematics solution can be used
to compute the grasping arm configuration.

June 2015

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2015