IEEE Robotics & Automation Magazine - June 2014 - 61

are preferentially used in the merging process because of the
probabilistic nature of the PGVD.
Introduction
The ability of an autonomous agent to sense its environment
and situate itself within this environment is a cornerstone of
mobile robotics. SLAM is the process of sensing an unknown
environment and concurrently generating a consistent map of
the world by fusing the available sensor data. As such, the
pose of a robot can be estimated and an environment map
can be built [2].
Extensive literature exists on SLAM for a single robot (for
a review, see [3]). However, exploring unknown environments with multiple mobile agents has received comparatively
less attention and can have significant advantages, including
the following:
● Exploration and mapping can be done more rapidly.
● A distributed system is more robust to failures [4].
● The results are more accurate due to the redundancy of data.
With the stated benefits of multiple-robot SLAM comes
significant challenges in implementation. The two main problems to overcome are map merging without a global position
reference and map fusion incorporating map uncertainty.
This article addresses both issues using only information
within the maps in a robust and scalable way.
Abstract geometrical perception is a foundation for highlevel reasoning and knowledge sharing. When multiple
robots are supposed to explore and map an unknown environment cooperatively, there is a need to provide a logical
infrastructure so that the robots can share their spatial perception and decide how to use the shared knowledge. If the
salient information from the maps is extracted and shared
among robots, the speed and accuracy of the mutual perception will improve, and communication channels will not be
burdened with large amounts of unprocessed data.
A topological map is an abstract world representation in
the form of connected paths and intersections. Humans and
insects use topological maps to navigate, argue about paths
and positions, and avoid obstacles [5]. As an example, pigeons
have been shown to use highways and their intersections as a
topological map to fly over long distances [6].
The general approach taken here is to achieve SLAM
through graph matching where a graph is some reduced-form
topological representation of the higher-level map structure
[7]. The GVD described in the following sections is an appropriate graph structure.
Multiple-Robot SLAM
Past approaches to collaborative SLAM can be generally categorized based on whether they share raw sensor data [8] or
processed maps [4]. Sharing raw sensor data results in more
flexibility but requires high bandwidth and reliable communication between robots as well as more processing power.
In contrast, sharing maps helps use less bandwidth and
reduces the need to process raw data; however, the performance is dependent on the map quality. The latter method

is referred to as map merging or map fusion and is the
approach taken here.
Multiple-robot SLAM can also be categorized based on the
method used to process measurement data. In feature-based
SLAM [9], which is usually performed by cameras, unique
objects called features or landmarks are extracted from measurements and used for localization. The spatial distribution
of the features represents a model of the world. Feature-based
multiple-robot SLAM has been implemented using an information filter [10], an extended Kalman filter [11], and a particle filter [12].
An alternative paradigm is view-based SLAM [13], which
uses entire laser scans. Scans are matched using scan-matching algorithms. Our approach uses view-based SLAM. Thrun
proposes a probabilistic multiple-robot view-based SLAM
algorithm in [14]. This method is robust; however, the
approximate initial poses of the robots are assumed to be
known before the start of the mission.
A view-based multiple-robot SLAM algorithm is proposed
by Howard using a particle filter [8], where it is assumed that
robots will meet each other in the environment to determine
their relative poses. This method is moderately fast but
demands high computational power and memory since it is
based on particle filtering.
An effective and fast approach to multiple-robot SLAM
rests on the concept of map merging or map fusion [15]. In
[4], a solution is presented based on occupancy map merging.
This method uses map distance as a similarity index and tries
to find similar patterns in two maps based on a random walk
algorithm. The drawback of this method is that it can fail,
especially when there are few similar patterns in both maps.
This method is time-consuming and therefore problematic in
large-scale maps that are common in indoor environments. A
similar method is proposed in [16], with simulated annealing
and hill climbing used to merge maps. This method becomes
ineffective in maps with fewer overlaps.
The contribution of this research is a novel map fusion algorithm that exploits the properties of the GVD to achieve
fast and accurate map fusion for large maps. In addition, the
uncertainty in the maps is used to build a PGVD that encapsulates not only the topological structure of the map but also
the confidences associated with different areas of the map.
Once the PGVDs are built, the edges are matched using a
two-dimensional (2-D) cross-correlation that will preferentially match the areas of the maps that have higher confidences. The resulting transformation can align maps to generate a
global map. However, there is an uncertainty associated with
this calculated transformation, which should also be propagated to the maps. The novel linearized uncertainty propagation (LUP) approach proposed in this research accounts for
the uncertainty of the transformation. In LUP, if the transformation for each cell of the map is linearized, then the Gaussian uncertainty of the transformation is propagated to the
transformed cell. This process is performed on all transformed cells; therefore, the resulting map carries the uncertainty of the transformation. Final map fusion is then
June 2014

IEEE ROBOTICS & AUTOMATION MAGAZINE

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