IEEE Robotics & Automation Magazine - June 2014 - 62

achieved with an entropy filter. The result is a fast, reliable,
and robust method of fusing maps for multiple-robot SLAM.
It should be mentioned that the assumption in this article
is that the individual maps developed by each robot are accurate and consistent.
To summarize, the proposed novel method for map fusion
has the following key advantages.
● It accounts for uncertainties in the occupancy grid maps
using the PGVD.
● It considers the uncertainty of the calculated transformation by linearization.
● It is fast and robust compared to other methods.
● It is able to preferentially match areas of the maps that are
more certain.
Background
The GVD is a type of roadmap [17] that is the locus of
points that are equidistant to at least the two closest obstacles. The GVD has the following two important properties
that will be exploited.
1) The GVD is connected because the set of free space is connected and connectivity is maintained under a deformation retraction [17].
2) The GVD of a map is unique and is invariant to transformations because it is a retraction [17].
The GVD can be interpreted as a topological representation
of the map structure that contains the key information intrinsic to the map but in a much more compact form.
There are different methods to generate GVD for a map.
Mathematical morphological operations [18] are a fast and
reliable method to build a GVD. In Blum's method, introduced in [19], the GVD is developed using a maximal
inscribed circle method that is inefficient for large maps. A
dynamic version of the GVD, which improves performance
near nonconvex obstacles, is proposed by Lau et al. [20].
Although this method has good results, it is time-consuming.
Beeson et al. [21] propose an extended Voronoi graph
algorithm to improve the efficiency of building the GVD
when the robot is limited with its sensory horizon. This
method performs well in noisy environments by eliminating
spurious junctions.
Previous Topological Approaches to SLAM
Voronoi graphs and graph matching in its different forms
have many applications in SLAM. There are many topological
solutions for single-robot SLAM, such as the works by Choset
et al. [22], [23], the annotated generalized Voronoi graph
(AGVG) [24], the work by Beeson et al. [25], Bayesian inference [26], and the semantic approach with place labeling by
Friedman et al. [27].
Choset and Nagatani [22] propose a topological SLAM
algorithm for a single robot based on the GVD. In [24], an
AGVG is used for single-robot SLAM. The proposed method
is based on a matching scheme for solving the data association problem. This method identifies the corresponding parts
of the map in two tree-formed Voronoi graphs. One form
62

IEEE ROBOTICS & AUTOMATION MAGAZINE

June 2014

represents a local observation, and the other form represents
the internal map of the robot.
In [28], a solution to detect and recognize topological features is proposed using Delaunay triangulations. In [27], a
semantic approach is used by a robot to generate a topological
map that can identify different places. Identified places can be
used for different autonomy applications.
A multiple-robot SLAM based on topological map merging using both structural and geometrical characteristics of
the Voronoi graph is proposed in [29]. The assumption in this
article is that a robot will be able to recognize areas of the map
that correspond to vertices. In this case, the topological map is
built on the occupied space as opposed to the free space. The
method in [29] is claimed to be fast. However, a limitation is
that the maps are not updated.
In this article, a skeletonization approach is extended to be
probabilistic and used for map matching of multiple robots. A
common problem encountered when using skeletonization
for SLAM is that the skeleton has no closed-form solution,
and heuristic methods for generating it tend to be slow. In our
approach, morphological operations are used to generate the
GVD, as explained in the "Building the Probabilistic GVD"
section. The proposed approach is fast enough to be used in
real time and guarantees connectedness of the skeleton [18].
In addition, the probabilistic nature of the proposed PGVD
allows areas of the maps that are known with higher certainty
to be preferentially matched.
Transforming Occupancy Grid Maps
with an Uncertain Transformation
In general, any type of uncertainty in this context is identified as
having five main causes: environment, sensors, robots, models,
and computations. Thrun et al. state that "uncertainty arises if
the robot lacks critical information for carrying out its task" [3].
Map fusion involves dealing with two types of uncertainty.
1) Uncertainty due to pose and sensor measurements: This
kind of uncertainty is represented within the occupancy
grid map. Specifically, it originates from the uncertain
pose of each robot and is embedded in the map of the
robot. This can be considered as a form of uncertainty at
the individual robot level. Throughout this article, the
terms uncertainty and map uncertainty refer to this type
unless otherwise stated.
2) Uncertainty due to transformation: If we can estimate the
uncertainty in the transformation that relates two maps,
then we can account for this uncertainty in the fusion process. In this article, the terms transformation uncertainty,
rotation uncertainty, and translation uncertainty are used to
refer to this type of uncertainty.
The uncertainty associated with the relative transformation matrix is represented as a covariance matrix. The covariance error is propagated through the probabilistic transformation function using the LUP formulation, a novel
map-merging method introduced in [1] and expanded upon
here. This section addresses the propagation of the uncertainty in transformation given the transformation matrix and

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