IEEE Robotics & Automation Magazine - June 2013 - 49

Note that this is a challenging environment for practically all existing data association techniques, as they would
probably match parallel corridors in an incorrect correspondence, leading to failure in the environment's topology estimation.
Our grid matching strategy, as decribed previously, is
applied for every pair of overlapping grid maps, starting
from the inner loop. Once an overlap is successfully processed, the final configuration of the minimization is used
as a new edge in the graph, and the graph error is minimized as described in a previous section. This process is
iterated until no new overlaps are detected.
Figure 14 presents the initial graph, in which only
odometry edges exist, and the global grid map that would
result from a projection of all the submaps, which is clearly
topologically inconsistent. (Figure 14 shows both the initial
and the global result, which happens to be wrong.) The
final result, on the other hand, presents a very good alignment of parallel corridors, despite the fact that there are no
positive correspondences or place revisits that could be
used for this purpose. As far as we know, only the proposed
minimization strategy that computes a physically feasible
configuration for overlapping submaps can handle this
information. Despite the known limitations of the grid
matching approach, due to its high dependency on the initial relative pose and the need for some overlap, to our
knowledge, no other existing technique can produce this
result with a similar data set, which is yet another contribution of this article. Some further experiments and discussion can be found in [18].
Obviously, this strategy can be efficiently applied because
of GPUs' computational power. Table 6 shows the required
time for processing the whole experiment. In this example,
the SuperLU solver (instead of CNC) is used for the graph
minimization, as pointed out by the results shown in Table 4.
Nevertheless, the grid matching algorithm GPU speedup
becomes clearly visible (>55X).
Real
The second experiment was performed with the Fr079 data
set preprocessed in 28 consecutive submaps with the same
characteristics and following the same procedure as in the
simulated scenario. In this case, however, the new edges introduced in the graph as a result of handling overlapping grid
maps (as described in section on grid matching) correspond
to actual matchings. Figure 15 shows the initial submaps, the
resulting global map that would result from these submaps,
and the final result after applying our correction. This experiment shows that the presented strategy could also be useful
for typical data association problems (given a sufficiently
good initial estimate).
Table 7 summarizes the computation times required for
processing this experiment, showing a similar performance to
the simulated case.
Any attempt to maximize the usage of multiple CPU
cores is done along this work. The main aim of this work

Figure 13. The submaps configuration in the spiral corridor
simulated experiment.

(a)

(b)

Figure 14. (a) The initial graph and resulting grid map and (b) the
final graph and resulting grid map of the spiral corridor experiment,
after being processed in just 2.48 s with a GTX280 GPU.

Table 6. Processing time, spiral trajectory experiment.
Processor

Time (s)

2-GHz Core 2 Duo T7250

145.82

3.2-GHz Pentium D

139.45

GF8400M GS (laptop)

12.32

GTX280 (desktop)

2.48

is not only to significantly reduce computation time but
also to identify which problems can be efficiently solved
by the GPU to release the CPU as much as possible for its
concurrent and continuous operation in a mobile robot
multitasking system.
june 2013

IEEE ROBOTICS & AUTOMATION MAGAZINE

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