588 IEEE TRANSACTIONS ON ROBOTICS, VOL. 21, NO. 4, AUGUST 2005
Hierarchical SLAM: Real-Time Accurate
Mapping of Large Environments
Carlos Estrada, José Neira, and Juan D. Tardós
Abstract—In this paper, we present a hierarchical mapping
method that allows us to obtain accurate metric maps of large en-
vironments in real time. The lower (or local) map level is composed
of a set of local maps that are guaranteed to be statistically inde-
pendent. The upper (or global) level is an adjacency graph whose
arcs are labeled with the relative location between local maps. An
estimation of these relative locations is maintained at this level
in a relative stochastic map. We propose a close to optimal loop
closing method that, while maintaining independence at the local
level, imposes consistency at the global level at a computational
cost that is linear with the size of the loop. Experimental results
demonstrate the efficiency and precision of the proposed method
by mapping the Ada Byron building at our campus. We also
analyze, using simulations, the precision and convergence of our
method for larger loops.
Index Terms—Large maps, local maps, loop closing, stochastic
mapping.
I. INTRODUCTION
O
VER THE past few years, there has been an increasing
interest in reducing the computational time and memory
requirements when performing simultaneous localization and
mapping (SLAM) in large areas (see [1] and [2] and the refer-
ences therein). The method presented here, hierarchical SLAM,
addresses the complexity of mapping large areas by building a
set of independent local stochastic maps. By limiting the max-
imum local map size, this can be carried out in constant time per
step. The system is completed with an upper global level con-
taining a graph whose nodes correspond to the local maps and
whose arcs represent adjacency relations. The metric informa-
tion about the relative location between adjacent maps is also
stored at the global level using a stochastic map representation.
An additional advantage of this approach is its natural exten-
sion to multirobot map building: several robots can contribute
new local maps or refine previously built local maps.
Several current methods address the computational com-
plexity problem by working on a limited region of the map.
Postponement [3] and the compressed filter [4] significantly
reduce the computational cost without sacrificing precision,
although they require an
step on the total number of
landmarks to obtain the full map. The split covariance intersec-
tion method [5] limits the computational burden but sacrifices
Manuscript received March 22, 2004; revised September 15, 2004. This paper
was recommended for publication by Associate Editor G. Oriolo and Editor
I. Walker upon evaluation of the reviewers’ comments. This work was sup-
ported in part by the Dirección General de Investigación of Spain under Project
DPI2000-1265 and Project DPI2003-07986.
The authors are with the Department of Computer Science and Sys-
tems Engineering, University of Zaragoza, 50018 Zaragoza, Spain (e-mail:
cestrada@unizar.es; jneira@unizar.es; tardos@unizar.es).
Digital Object Identifier 10.1109/TRO.2005.844673
precision: it obtains a conservative estimate. The sparse ex-
tended information filter [6] is able to obtain an approximate
map in constant time per step, except during loop closing. All
cited methods work on a single absolute map representation
and confront divergence due to nonlinearities as uncertainty
increases when mapping large areas [7].
In contrast, sequential map joining [8] and the constrained
local submap filter [9] propose to build stochastic maps rela-
tive to a local reference, guaranteed to be statistically indepen-
dent. By limiting the size of the local map, this operation is con-
stant time per step. Local maps are joined periodically into a
global absolute map, in an
step. Given that most of the
updates are carried out on a local map, these techniques reduce
the harmful effects of linearization [7].
The constrained relative submap filter (CRSF) [10] proposes
to maintain the local map structure. Each map contains links to
other neighboring maps, forming a tree structure (where loops
cannot be represented). The method converges by revisiting the
local maps and updating the links through correlations. In the
Atlas system [1], the constant-time SLAM (CTS) algorithm
[11], and our approach, the links between local maps form
an adjacency graph. The main difference is that neither the
Atlas system nor CTS impose loop consistency in the graph,
sacrificing the optimality of the resulting global map. Instead,
the location of a local map relative to a given base is computed
by composing transformations along the most precise path
throughout the graph. Bailey [12] proposes a similar approach
called the network coupled feature maps (NCFM). The coupling
(relative location) between two adjacent local maps is estimated
using the constraints imposed by common features found by a
batch data association algorithm. However, the method ignores
the correlations appearing between the coupling estimates. The
author conjectures that this still produces consistent results, but
no proof or experimental validation is provided.
It is well known that, even in small environments, imposing
loop consistency increases the precision of the resulting map
[13]. However, closing large loops is an especially difficult task.
The first key problem is the reliable detection of loops. This
requires data association techniques that do not rely on a precise
estimation of the vehicle location. In this study, we use the RS
linear time relocation algorithm of [14]. The reader may consult
this paper for additional details and further references on the
subject.
The second key problem is that linearized methods like the
extended Kalman filter (EKF) fail to obtain accurate map esti-
mations due to the large uncertainties appearing in large loops.
Several researchers have addressed the problem of loop closing
while building metric maps. In [15], the authors make use of the
expectation-maximization (EM) algorithm to simultaneously
1552-3098/$20.00 © 2005 IEEE
Authorized licensed use limited to: Yulong Zhao. Downloaded on June 17,2020 at 22:28:28 UTC from IEEE Xplore. Restrictions apply.