Page 346 - Autonomous Mobile Robots

336 Autonomous Mobile Robots

9.1 INTRODUCTION
The concept of autonomy of mobile robots encompasses many areas of
knowledge, methods, and ultimately algorithms designed for trajectory control,
obstacle avoidance, localization, map building, and so forth. Practically,
the success of a path planning and navigation mission of an autonomous
vehicle depends on the availability of both a sufficiently reliable estimation
of the vehicle location and an accurate representation of the navigation area.
Schematically, the problem of map building consists of the following steps
(1) Sensing the environment of the vehicle at time k using onboard sensors
(e.g., laser scanner, vision, or sonar); (2) Representation of sensor data (e.g.,
feature- or raw-data-based approaches); (3) Integration of the recently perceived
observations at time k with the previously learned structure of the environment
estimated at time k − 1.
The simplest approach to map building relies on the vehicle location estim-
ates provided by dead-reckoning. However, as reported in the literature [1], this
approach is unreliable for long-term missions due to the time-increasing drift of
those estimates (Figure 9.1a). Consequently, a coupling arises between the map
building problem and the improvement of dead-reckoning location estimates
(Figure 9.1b). Different approaches to the so-called simultaneous localization
and mapping (SLAM) problem have populated the robotics literature during
the last decade.
The most popular approach to SLAM dates back to the seminal work of
Smith et al. [2] where the idea of representing the structure of the navigation
area in a discrete-time state-space framework was originally presented. They
introduced the concept of stochastic map and developed a rigorous solution to
the SLAM problem using the extended Kalman filter (EKF) perspective. Many
successful implementations of this approach have been reported in indoor [1],
outdoor [3], underwater [4], and air-borne [5] applications.
The EKF-based approach to SLAM is characterized by the existence of a
discrete-time augmented state vector, composed of the location of the vehicle
and the location of the map elements, recursively estimated from the available
sensor observations gathered at time k, and a model of the vehicle motion,
between time steps k −1 and k. Within this framework, uncertainty is represen-
ted by probability density functions (pdfs) associated with the state vector, the
motionmodel, andthesensorobservations. Itisassumedthatrecursivepropaga-
tion of the mean and the covariance of those pdfs conveniently approximates
the optimal solution of this estimation problem.
The time and memory requirements of the basic EKF–SLAM approach
2
result from the cost of maintaining the full covariance matrix, which is O(n )
where n is the number of features in the map. Many recent efforts have
concentrated on reducing the computational complexity of SLAM in large
environments. Several current methods address the computational complex-
ity problem by working on a limited region of the map. Postponement [6]

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c009” — 2006/3/31 — 16:43 — page 336 — #6