IEEE Robotics & Automation Magazine - June 2015 - 49

0.6
0.4
0.2
0.0

Easy

Medium
(a)

Hard

1.0

PRM*
fIRS
SPARS

0.6

Successes Ratio

PRM*
fIRS
SPARS

Successes Ratio

1.0

0.4
0.2
0.0

Easy

Medium
(b)

Hard

PRM*
fIRS
SPARS

0.6
0.4
0.2
0.0

Easy

Medium
(c)

Hard

Figure 8. The success ratio of online query resolution given a precomputed roadmap after (a) 1,000, (b) 10,000, and (c) 30,000
iterations. Given small roadmaps, only the easy environment can be solved, but for larger precomputed roadmaps, the success ratio
increases for the harder challenges. IRS has an equivalent success ratio to PRM*, but the success ratio of SPARS suffers in harder
instances.

number of novel obstacles increases, the near-optimality
guarantees are not valid, but the path degradation does not
exceed the stretch factor.

Construction Time
The average construction time depends upon both the number of iterations and the amount of computation performed in
every iteration. A fast IRS iteration is typically faster than a
PRM) one, and this results in a reduced construction time for
IRS. SPARS introduces a small computational overhead for
reasoning about which edges and vertices to retain, but it is
still in the order of PRM) as it benefits from the sparsity of the
computed data structure. The construction is a process that
can also be parallelized on a computing cloud to increase the
frequency with which the roadmap can be updated.
Communication Overhead
Once the roadmap is computed, it needs to be transmitted to
the local workstation. This involves serializing the data structure, communicating it using individual Robot Operating System (ROS) messages, and then deserializing it. Figure 9 shows
the time it takes to perform these operations for roadmaps of
different sizes computed by the varying algorithms. These
times are dominated by the serialization and deserialization
process. The actual communication costs are significantly
lower. The data suggest a major benefit in computing lightweight data structures in terms of effectively communicating
them to a robot from a remote machine. For PRM) road-

PRM*
fIRS
SPARS

25
Time (s)

Success Ratio
The success ratio, shown in Figure 8, is lower for smaller roadmaps for scenes where there are novel objects. The easy environment is solved by all three methods. The success ratio
improves, however, as the amount of precomputation increases, motivating the need for investigating appropriate roadmap
precomputation schemes. The PRM) and IRS methods exhibit
similar success ratio across the different environments. The
success ratio of the SPARS method, however, suffers in the
harder environments. This is reasonable as this is the sparsest
roadmap returned.

Grasped Graph

20
15
10
5
0

500

1,000

2,000

5,000

10,000

Number of Nodes in the Graph
Figure 9. The cost of transmitting the data structure between two
remote machines for roadmaps of different sizes computed by
different approaches.

maps, it was not even possible to transmit them in individual
ROS messages above a certain size (more than 5,000 iterations), and a more complex communication process is
needed. The roadmap edges are storing information, i.e., a
sequence of configurations, which is useful during the online
resolution but increase the storage and communication overhead of dense roadmap solutions.
Discussion
This article emphasizes the emerging opportunities in industrial automation due to the availability of computing as a service with the advent of cloud computing. The objective is to
motivate efforts at the intersection of motion planning and
cloud computing, especially in the context of flexible, adaptive
factory floors that employ modern, compliant manipulators.
This article proposes a synergistic cloud-robot process for
addressing manipulation problems, where the computational
load is split between the local workstation and the remote
cloud facility. In this process, standard motion-planning roadmaps [8], [9] can be seen as the main form of interaction
between the cloud and individual robots. The capability of
roadmaps to effectively answer path planning queries depends
on their size and density. Recently proposed algorithms
June 2015

IEEE ROBOTICS & AUTOMATION MAGAZINE

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