Page 348 - Autonomous Mobile Robots

338 Autonomous Mobile Robots

is constant time per step. Local maps are joined periodically into a global
2
absolute map, in a O(n ) step. Given that most of the updates are carried out on
a local map, these techniques also reduce the harmful effects of linearization.
2
To avoid the O(n ) step, the constrained relative submap filter [12] proposes
to maintain the independent local map structure. Each map contains links to
other neighboring maps, forming a tree structure (where loops cannot be rep-
resented). In Atlas [13], network coupled feature maps [14], and constant time
SLAM [15] the links between local maps form an adjacency graph. These tech-
niques do not impose loop consistency in the graph, sacrificing the optimality
of the resulting global map. Hierarchical SLAM [16] proposes a linear time
technique to impose loop consistency, obtaining a close to optimal global map.
The FastSLAM technique [17] uses particle filters to estimate the vehicle tra-
jectory and each one has an associated set of independent EKF to estimate the
location of each feature in the map. This partition of SLAM into a localization
and a mapping problem, allows to obtain a computational complexity O(log(n))
with the number of features in the map. However, its complexity is linear with
the number of particles used. The scaling of the number of particles needed
with the size and complexity of the environment remains unclear. In particular,
closing loops causes dramatic particle extinctions that map result in optimistic
(i.e., inconsistent) uncertainty estimations.
Another class of SLAM techniques is based on estimating sequences of
robot poses by minimizing the discrepancy between overlapping laser scans.
The map representation is the set of robot poses and the corresponding set
of laser scans. The work in Reference 18 uses scan matching between close
robot poses and global correlation to detect loops. The poses along the loop
are estimated using consistent pose estimation [19], whose time complexity is
3
O(n ) on the number of robot poses, making the method unsuitable for real
time execution in large environments. More recently, a similar approach to
build consistent maps with many cycles has been proposed in Reference 20.
This method obtains correspondences between vehicle poses using the iterative
closest point algorithm. Using a quadratic penalty function, correspondences
are incorporated into an optimization algorithm that recomputes the whole tra-
jectory. This process is iterated until convergence. Neither computing time nor
computational complexity are reported. There are two fundamental limitations
in this class of techniques, compared to EKF-based SLAM. First, there is no
explicit representation of the uncertainty in the estimated robot poses and the
resulting map. As a consequence, their convergence and consistency properties
remain unknown. Second, they largely rely on the high precision and density
of data provided by laser scanners. They seem hard to extend to sensors that
give more imprecise, sparse, or partial information such as sonar or monocular
vision.
This chapter describes the basic algorithm to deal with the SLAM problem
from the above mentioned EKF-based perspective. We describe techniques that

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c009” — 2006/3/31 — 16:43 — page 338 — #8