Real-Time Loop Closure in 2D LIDAR SLAM
Wolfgang Hess
1
, Damon Kohler
1
, Holger Rapp
1
, Daniel Andor
1
Abstract— Portable laser range-finders, further referred to as
LIDAR, and simultaneous localization and mapping (SLAM)
are an efficient method of acquiring as-built floor plans.
Generating and visualizing floor plans in real-time helps the
operator assess the quality and coverage of capture data. Build-
ing a portable capture platform necessitates operating under
limited computational resources. We present the approach used
in our backpack mapping platform which achieves real-time
mapping and loop closure at a 5 cm resolution. To achieve real-
time loop closure, we use a branch-and-bound approach for
computing scan-to-submap matches as constraints. We provide
experimental results and comparisons to other well known
approaches which show that, in terms of quality, our approach
is competitive with established techniques.
I. INTRODUCTION
As-built floor plans are useful for a variety of applications.
Manual surveys to collect this data for building management
tasks typically combine computed-aided design (CAD) with
laser tape measures. These methods are slow and, by em-
ploying human preconceptions of buildings as collections
of straight lines, do not always accurately describe the true
nature of the space. Using SLAM, it is possible to swiftly
and accurately survey buildings of sizes and complexities that
would take orders of magnitude longer to survey manually.
Applying SLAM in this field is not a new idea and is
not the focus of this paper. Instead, the contribution of this
paper is a novel method for reducing the computational
requirements of computing loop closure constraints from
laser range data. This technique has enabled us to map
very large floors, tens-of-thousands of square meters, while
providing the operator fully optimized results in real-time.
II. RELATED WORK
Scan-to-scan matching is frequently used to compute
relative pose changes in laser-based SLAM approaches, for
example [1]–[4]. On its own, however, scan-to-scan matching
quickly accumulates error.
Scan-to-map matching helps limit this accumulation of
error. One such approach, which uses Gauss-Newton to find
local optima on a linearly interpolated map, is [5]. In the
presence of good initial estimates for the pose, provided in
this case by using a sufficiently high data rate LIDAR, locally
optimized scan-to-map matching is efficient and robust.
On unstable platforms, the laser fan is projected onto the
horizontal plane using an inertial measurement unit (IMU)
to estimate the orientation of gravity.
Pixel-accurate scan matching approaches, such as [1],
further reduce local error accumulation. Although compu-
tationally more expensive, this approach is also useful for
1
All authors are at Google.
loop closure detection. Some methods focus on improving
on the computational cost by matching on extracted features
from the laser scans [4]. Other approaches for loop closure
detection include histogram-based matching [6], feature de-
tection in scan data, and using machine learning [7].
Two common approaches for addressing the remaining
local error accumulation are particle filter and graph-based
SLAM [2], [8].
Particle filters must maintain a representation of the full
system state in each particle. For grid-based SLAM, this
quickly becomes resource intensive as maps become large;
e.g. one of our test cases is 22,000 m
2
collected over a 3 km
trajectory. Smaller dimensional feature representations, such
as [9], which do not require a grid map for each particle, may
be used to reduce resource requirements. When an up-to-
date grid map is required, [10] suggests computing submaps,
which are updated only when necessary, such that the final
map is the rasterization of all submaps.
Graph-based approaches work over a collection of nodes
representing poses and features. Edges in the graph are con-
straints generated from observations. Various optimization
methods may be used to minimize the error introduced by
all constraints, e.g. [11], [12]. Such a system for outdoor
SLAM that uses a graph-based approach, local scan-to-scan
matching, and matching of overlapping local maps based on
histograms of submap features is described in [13].
III. SYSTEM OVERVIEW
Google’s Cartographer provides a real-time solution for
indoor mapping in the form of a sensor equipped backpack
that generates 2D grid maps with a r = 5 cm resolution. The
operator of the system can see the map being created while
walking through a building. Laser scans are inserted into a
submap at the best estimated position, which is assumed to be
sufficiently accurate for short periods of time. Scan matching
happens against a recent submap, so it only depends on
recent scans, and the error of pose estimates in the world
frame accumulates.
To achieve good performance with modest hardware re-
quirements, our SLAM approach does not employ a particle
filter. To cope with the accumulation of error, we regularly
run a pose optimization. When a submap is finished, that is
no new scans will be inserted into it anymore, it takes part
in scan matching for loop closure. All finished submaps and
scans are automatically considered for loop closure. If they
are close enough based on current pose estimates, a scan
matcher tries to find the scan in the submap. If a sufficiently
good match is found in a search window around the currently
estimated pose, it is added as a loop closing constraint to the
2016 IEEE International Conference on Robotics and Automation (ICRA)
Stockholm, Sweden, May 16-21, 2016
978-1-4673-8026-3/16/$31.00 ©2016 IEEE 1271