IEEE Robotics & Automation Magazine - June 2015 - 48

most dense. The IRS roadmaps have the same vertices as
PRM) but fewer edges, while SPARS also removes nodes. The
statistics are recorded for ten different random seeds and different roadmap sizes
varying from 1,000 to
10,000 and 30,000 iteraThe construction is a
tions for all three algorithms. Given the multiprocess that can also be
modal nature of the
parallelized on a computing manipulation roadmap,
each iteration corresponds to an attempt to
cloud to increase the
add both a transit and a
transfer node to the roadfrequency with which the
map. Thus, a PRM) roadmap after 10,000 iteraroadmap can be updated.
tions has 20,000 nodes
and about 800,000 edges.

PRM*
fIRS
SPARS

Time (s)

1.2
1.0
0.8
0.6
0.4
0.2
0.0

Easy

Medium
(a)

Hard

9
8
7
6
5
4
3
2
1
0

PRM*

Solution Length
The average solution length, shown in Figure 7, gives a measure of achieved path quality. PRM) generates roadmaps of
increased connectivity and, as expected, achieves the best
path quality. Despite having a lot fewer vertices and edges,
SPARS outperforms IRS in many cases. Overall, the path
degradation is smaller than the stretch factor of the methods used ^t = 2h across the various environments. As the

fIRS

100

SPARS

PRM*

fIRS

SPARS

80
Time (s)

1.4

Time (s)

Query Resolution
Figure 6 compares the methods in terms of running time.
The cost of the lazy evaluation approach is affected by the
presence of novel obstacles. The query resolution time is

also affected by the size of the roadmap, which directly
relates to the number of A ) expansions as well as the probability of finding collision-free solutions. In most cases,
SPARS outperforms IRS, and IRS outperforms PRM) due
to sparsity and reduced size. The relative performance of
PRM) tends to degrade as bigger roadmaps are computed
because the A ) calls become increasingly more expensive.
As the number of obstacles increases, these results are
affected by a lower success rate.
An incremental A ) approach was also tested instead of the
lazy method, where the heuristic search directly explores the
roadmap for the shortest collision-free path. This approach
results in significantly slower online query resolution times
and the corresponding data are not reported here.

60
40
20

Easy

Medium
(b)

Hard

Easy

Medium
(c)

Hard

PRM*
fIRS
SPARS

Easy

Medium
(a)

Hard

90
80
70
60
50
40
30
20
10
0

PRM*
fIRS
SPARS

Easy

Medium
(b)

Hard

Path Length

90
80
70
60
50
40
30
20
10
0

Path Length

Figure 6. The online query resolution time for returned paths given a precomputed roadmap after (a) 1,000, (b) 10,000, and (c)
30,000 iterations. There is a small difference between the running time of the methods when the input roadmaps are small. When
the roadmaps become larger, enough precomputation is available so that the hard problems are also solved, and the benefits of the
sparse representations become significant.

90
80
70
60
50
40
30
20
10
0

PRM*
fIRS
SPARS

Easy

Medium
(c)

Hard

Figure 7. The path quality of returned paths given a precomputed roadmap after (a) 1,000, (b) 10,000, and (c) 30,000 iterations.
There is some small degradation in path quality for the paths returned by the sparse roadmaps, but the path degradation is
significantly lower than the theoretical guarantees.

IEEE ROBOTICS & AUTOMATION MAGAZINE

June 2015

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