1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

Simultaneous localization and mapping

This is an old revision of this page, as edited by Trappist the monk (talk |
contribs) at 18:34, 17 July 2015 (replace/remove deprecated cs1|2 parameters;
using AWB). The present address (URL) is a permanent link to this revision,
which may differ significantly from the current revision.

In robotic mapping, simultaneous localization and

mapping (SLAM) is the computational problem of
constructing or updating a map of an unknown environment
while simultaneously keeping track of an agent's location
within it. While this initially appears to be a chicken-and-
egg problem there are several algorithms known for solving
it, at least approximately, in tractable time for certain
environments. Popular approximate solution methods
include the particle filter and extended Kalman filter.
2005 DARPA Grand Challenge winner
SLAM algorithms are tailored to the available resources, STANLEY performed SLAM as part of
hence not aimed at perfection, but at operational its autonomous driving system.
compliance. Published approaches are employed in self-
driving cars, unmanned aerial vehicles, autonomous
underwater vehicles, planetary rovers, newly emerging
domestic robots and even inside the human body.[1]

Problem definition
Given a series of sensor observations over discrete time steps
, the SLAM problem is to compute an estimate of the agent's
location and a map of the environment . All quantities A map generated by a SLAM Robot.
are usually probabilistic, so the objective is to compute:

Applying Bayes' rule gives a framework for sequentially updating the location posteriors, given a
map and a transition function ,

Similarly the map can be updated sequentially by

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 1/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

Like many inference problems, the solutions to inferring the two variables together can be found,
to a local optimum solution, by alternating updates of the two beliefs in a form of EM algorithm.

Algorithms
Statistical techniques used to approximate the above equations include Kalman filters, particle
filters (aka. Monte Carlo methods) and scan matching of range data. They provide an estimation of
the posterior probability function for the pose of the robot and for the parameters of the map. Set-
membership techniques are mainly based on interval constraint propagation.[2][3] They provide a
set which encloses the pose of the robot and a set approximation of the map.

Bundle adjustment is another popular technique for SLAM using image data. Bundle adjustment
jointly estimates poses and landmark positions, increasing map fidelity, and is used in many
recently commercialized SLAM systems such as Google's Project Tango (https://www.google.com/
atap/projecttango/).

New SLAM algorithms remain an active research area, and are often driven by differing
requirements and assumptions about the types of maps, sensors and models as detailed below.
Many SLAM systems can be viewed as combinations of choices from each of these aspects.

Mapping

Topological maps are a method of environment representation which capture the connectivity (i.e.,
topology) of the environment rather than creating a geometrically accurate map. Topological
SLAM approaches have been used to enforce global consistency in metric SLAM algorithms.[4]

In contrast, grid maps use arrays (typically square or hexagonal) of discretized cells to represent a
topological world, and make inferences about which cells are occupied. Typically the cells are
assumed to be statistically independent in order to simplify computation. Under such assumption,
are set to 1 if the new map's cells are consistent with the observation at
location and 0 if inconsistent.

Sensing

SLAM will always use several different types of sensors, and the powers and limits of various
sensor types have been a major driver of new algorithms.[5] Statistical independence is the
mandatory requirement to cope with metric bias and with noise in measures. Different types of
sensors give rise to different SLAM algorithms whose assumptions are which are most appropriate
to the sensors. At one extreme, laser scans or visual features provide details of a great many points
within an area, sometimes rendering SLAM inference unnecessary because shapes in these point
clouds can be easily and unambiguously aligned at each step via image registration. At the opposite
extreme, tactile sensors are extremely sparse as they contain only information about points very
close to the agent, so they require strong prior models to compensate in purely tactile SLAM. Most
practical SLAM tasks fall somewhere between these visual and tactile extremes.

Sensor models divide broadly into landmark-based and raw-data approaches. Landmarks are
uniquely identifiable objects in the world whose location can be estimated by a sensor -- such as
wifi access points or radio beacons. Raw-data approaches make no assumption that landmarks can
be identified, and instead model directly as a function of the location.

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 2/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

Optical sensors may be one-dimensional (single beam) or 2D- (sweeping) laser rangefinders, 3D
High Definition LiDAR, 3D Flash LIDAR, 2D or 3D sonar sensors and one or more 2D cameras.[5]
Since 2005, there has been intense research into VSLAM (visual SLAM) using primarily visual
(camera) sensors, because of the increasing ubiquity of cameras such as those in mobile devices.[6]
Visual and LIDAR sensors are informative enough to allow for landmark extraction in many cases.
Other recent forms of SLAM include tactile SLAM (sensing by local touch only),[7] radar SLAM,[8]
and wifi-SLAM (sensing by strengths of nearby wifi access points). Recent approaches apply quasi-
optical wireless ranging for multi-lateration (RTLS) or multi-angulation in conjunction with SLAM
as a tribute to erratic wireless measures. A kind of SLAM for human pedestrians uses a shoe
mounted inertial measurement unit as the main sensor and relies on the fact that pedestrians are
able to avoid walls to automatically build floor plans of buildings. by an indoor positioning
system.[9]

For some outdoor applications, the need for SLAM has been almost entirely removed due to high
precision differential GPS sensors. From a SLAM perspective, these may be viewed as location
sensors whose likelihoods are so sharp that they completely dominate the inference. However GPS
sensors may go down entirely or in performance on occasions, especially during times of military
conflict which are of particular interest to some robotics applications.

Kinematics modeling

The term represents the kinematics of the model, which usually include information
about action commands given to a robot. As a part of the model, the kinematics of the robot is
included, to improve estimates of sensing under conditions of inherent and ambient noise. The
dynamic model balances the contributions from various sensors, various partial error models and
finally comprises in a sharp virtual depiction as a map with the location and heading of the robot as
some cloud of probability. Mapping is the final depicting of such model, the map is either such
depiction or the abstract term for the model.

For 2D robots, the kinematics are usually given by a mixture of rotation and "move forward"
commands, which are implemented with additional motor noise. Unfortunately the distribution
formed by independent noise in angular and linear directions is non-Gaussian, but is often
approximated by a Gaussian. An alternative approach is to ignore the kinematic term and read
odometry data from robot wheels after each command -- such data may then be treated as one of
the sensors rather than as kinematics.

Multiple objects

The related problems of data association and computational complexity are among the problems
yet to be fully resolved, for example the identification of multiple confusable landmarks. A
significant recent advance in the feature-based SLAM literature involved the re-examination of the
probabilistic foundation for Simultaneous Localisation and Mapping (SLAM) where it was posed in
terms of multi-object Bayesian filtering with random finite sets that provide superior performance
to leading feature-based SLAM algorithms in challenging measurement scenarios with high false
alarm rates and high missed detection rates without the need for data association.[10]

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 3/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

Popular techniques for handling multiple objects include Joint Probabilistic Data Association
Filter (JPDAF) and probability hypothesis density filter (PHD).

Moving objects

Non-static environments, such as those containing other vehicles or pedestrians, continue to

present research challenges. SLAM with DATMO is a model which tracks moving objects in a
similar way to the agent itself.

Loop closure

Loop closure is the problem of recognizing a previously-visited location and updates the beliefs
accordingly. This can be a problem because model or algorithm errors can assign low priors to the
location. Typical loop closure methods apply a second algorithm to measure some type of sensor
similarity, and re-set the location priors when a match is detected. For example this can be done by
storing and comparing bag of words vectors of SIFT features from each previously visited location.

Exploration

"Active SLAM" studies the combined problem of SLAM with deciding where to move next in order
to build the map as efficiently as possible. The need for active exploration is especially pronounced
in sparse sensing regimes such as tactile SLAM. Active SLAM is generally performed by
approximating the entropy of the map under hypothetical actions. "Multi agent SLAM" extends
this problem to the case of multiple robots coordinating themselves to explore optimally.

Biological inspiration

In neuroscience, the hippocampus appears to be involved in SLAM-like computations giving rise to

place cells and has formed the basis for bio-inspired SLAM systems such as RatSLAM. Bio-inspired
methods are not currently competitive with engineering approaches however.

Complexity

Researchers and experts in artificial intelligence have struggled to solve the SLAM problem in
practical settings: that is, it required a great deal of computational power to sense a sizable area
and process the resulting data to both map and localize.[11] A 2008 review of the topic
summarized: "[SLAM] is one of the fundamental challenges of robotics . . . [but it] seems that
almost all the current approaches can not perform consistent maps for large areas, mainly due to
the increase of the computational cost and due to the uncertainties that become prohibitive when
the scenario becomes larger."[12] Generally, complete 3D SLAM solutions are highly
computationally intensive as they use complex real-time particle filters, sub-mapping strategies or
hierarchical combination of metric topological representations, etc.[13] Robots that use embedded
systems cannot fully implement SLAM because of their limitation in computing power. Nguyen V.,
Harati A., & Siegwart R. (2007) presented a fast, lightweight solution called OrthoSLAM, which
breaks down the complexity of the environment into orthogonal planes. By mapping only the

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 4/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

planes that are orthogonal to each other, the structure of most indoor environments can be
estimated fairly accurately. OrthoSLAM algorithm reduces SLAM to a linear estimation problem
since only a single line is processed at a time.[13]

History
A seminal work in SLAM is the research of R.C. Smith and P. Cheeseman on the representation
and estimation of spatial uncertainty in 1986.[14][15] Other pioneering work in this field was
conducted by the research group of Hugh F. Durrant-Whyte in the early 1990s.[16] which showed
that solutions to SLAM exist in the infinite data limit. This finding motivates the search for
algorithms which are computationally tractable and approximate the solution. The self-driving
STANLEY car won the DARPA Grand Challenge and included a SLAM system, bringing SLAM to
worldwide attention. Mass-market SLAM implementations can now be found in consumer robot
vacuum cleaners such as the Neato XV11. Self-driving cars by Google and others have now received
licenses to drive on public roads in some US states.

See also
Structure from motion
Kalman filter
Monte Carlo localization
Particle filter
List of SLAM Methods
DARPA Grand Challenge winner Stanley, a vehicle using SLAM techniques
Registration of range images
The Mobile Robot Programming Toolkit (MRPT) project: A set of open-source, cross-platform
libraries covering SLAM through particle filtering and Kalman Filtering.
Multi Autonomous Ground-robotic International Challenge: A $1.6 million international
challenge requiring multiple vehicles to collaboratively map a large area
Stereophotogrammetry

References
1. Mountney, P. (2006). "Simultaneous Stereoscope Localization and Soft-Tissue Mapping for
Minimal Invasive Surgery" (http://www.sciweavers.org/external.php?u=http%3A%2F%2Fwww.d
oc.ic.ac.uk%2F%7Epmountne%2Fpublications%2FMICCAI%25202006.pdf&p=). MICCAI. 1:
347–354. doi:10.1007/11866565_43 (https://doi.org/10.1007%2F11866565_43). Retrieved
2010-07-30. {{cite journal}}: Unknown parameter |coauthors= ignored (|author=
suggested) (help)
2. Jaulin, L. (2009). "A nonlinear set-membership approach for the localization and map building
of an underwater robot using interval constraint propagation" (http://www.ensta-bretagne.fr/jauli
n/paper_reder_ieee_tro.pdf) (PDF). IEEE Transactions on Robotics.
3. Jaulin, L. (2011). "Range-only SLAM with occupancy maps; A set-membership approach" (htt
p://www.ensta-bretagne.fr/jaulin/paper_dig_slam.pdf) (PDF). IEEE Transactions on Robotics.
4. Cummins, Mark; Newman, Paul (June 2008). "FAB-MAP: Probabilistic localization and
mapping in the space of appearance" (http://www.robots.ox.ac.uk/~mjc/Papers/IJRR_2008_Fa
bMap.pdf) (PDF). The International Journal of Robotics Research. 27 (6): 647–665.
doi:10.1177/0278364908090961 (https://doi.org/10.1177%2F0278364908090961). Retrieved
23 July 2014.

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 5/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

5. Magnabosco, M., Breckon, T.P. (February 2013). "Cross-Spectral Visual Simultaneous

Localization And Mapping (SLAM) with Sensor Handover" (http://www.durham.ac.uk/toby.breck
on/publications/papers/magnabosco13slam.pdf) (PDF). Robotics and Autonomous Systems.
63 (2): 195–208. doi:10.1016/j.robot.2012.09.023 (https://doi.org/10.1016%2Fj.robot.2012.09.0
23). Retrieved 5 November 2013.
6. Karlsson, N. (2005). The vSLAM Algorithm for Robust Localization and Mapping (http://ieeexpl
ore.ieee.org/xpls/abs_all.jsp?arnumber=1570091&tag=1). Int. Conf. on Robotics and
Automation (ICRA). {{cite conference}}: Unknown parameter |coauthors= ignored
(|author= suggested) (help)
7. Marck, J.W. Mohamoud, A., v.d.Houwen, E., van Heijster, R. (2013). Indoor radar SLAM A
radar application for vision and GPS denied environments. Radar Conference (EuRAD), 2013
European.
8. Fox, C., Evans, M., Pearson, M. and Prescott, T. (2012). Tactile SLAM with a biomimetic
whiskered robot. Proc. IEEE Int. Conf. on Robotics and Automation (ICRA),.
9. Robertson, P.; Angermann, M.; Krach B. (2009). Simultaneous Localization and Mapping for
Pedestrians using only Foot-Mounted Inertial Sensors (http://www.kn-s.dlr.de/indoornav/ubicom
p2009_final_my_pub.pdf) (PDF). Ubicomp 2009. Orlando, Florida, USA: ACM.
doi:10.1145/1620545.1620560 (https://doi.org/10.1145%2F1620545.1620560).
10. J. Mullane, B.-N. Vo, M. D. Adams, and B.-T. Vo, (2011). "A random-finite-set approach to
Bayesian SLAM," (http://www.ee.uwa.edu.au/~bnvo/vo/MVAV_SLAM11.pdf) (PDF). IEEE
Transactions on Robotics. 27 (2): 268–282. doi:10.1109/TRO.2010.2101370 (https://doi.org/10.
1109%2FTRO.2010.2101370).
11. Brynjolfsson, Erik; McAfee, Andrew (Jan 20, 2014). The Second Machine Age: Work, Progress,
and Prosperity in a Time of Brilliant Technologies. W. W. Norton & Company. p. 52.
ISBN 9780393239355.
12. Aulinas, Josep (2008). "The SLAM Problem: A Survey" (http://dl.acm.org/citation.cfm?id=15668
99.1566949). Proceedings of the 2008 Conference on Artificial Intelligence Research &
Development: 363–71. Retrieved July 15, 2015.
13. Nguyen, V.; Harati, A; Siegwart, R., "A lightweight SLAM algorithm using Orthogonal planes for
indoor mobile robotics," Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ
International Conference on , vol., no., pp.658,663, Oct. 29 2007-Nov. 2 2007
14. Smith, R.C.; Cheeseman, P. (1986). "On the Representation and Estimation of Spatial
Uncertainty" (http://www.frc.ri.cmu.edu/~hpm/project.archive/reference.file/Smith&Cheeseman.
pdf) (PDF). The International Journal of Robotics Research. 5 (4): 56–68.
doi:10.1177/027836498600500404 (https://doi.org/10.1177%2F027836498600500404).
Retrieved 2008-04-08.
15. Smith, R.C.; Self, M.; Cheeseman, P. (1986). "Estimating Uncertain Spatial Relationships in
Robotics" (http://www-robotics.usc.edu/~maja/teaching/cs584/papers/smith90stochastic.pdf)
(PDF). Proceedings of the Second Annual Conference on Uncertainty in Artificial Intelligence.
UAI '86. University of Pennsylvania, Philadelphia, PA, USA: Elsevier. pp. 435–461. {{cite
conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
16. Leonard, J.J.; Durrant-whyte, H.F. (1991). "Simultaneous map building and localization for an
autonomous mobile robot" (http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=174711).
Intelligent Robots and Systems' 91.'Intelligence for Mechanical Systems, Proceedings
IROS'91. IEEE/RSJ International Workshop on: 1442–1447. doi:10.1109/IROS.1991.174711 (h
ttps://doi.org/10.1109%2FIROS.1991.174711). Retrieved 2008-04-08.

External links
Probabilistic Robotics by (http://www.probabilistic-robotics.org/)Sebastian Thrun, Wolfram
Burgard and Dieter Fox with a clear overview of SLAM.

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 6/7
1/8/24, 8:51 PM Simultaneous localization and mapping - Wikipedia

SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping) (http://oc
w.mit.edu/courses/aeronautics-and-astronautics/16-412j-cognitive-robotics-spring-2005/project
s/1aslam_blas_repo.pdf).
Andrew Davison (http://www.doc.ic.ac.uk/%7Eajd/index.html) research page at Imperial
College London about SLAM using vision.
Autonomous and Perceptive Systems (http://www.ai.rug.nl/~gert/as/) research page at
University of Groningen about visual SLAM.
openslam.org (http://openslam.org/) A good collection of open source code and explanations of
SLAM.
Matlab Toolbox of Kalman Filtering applied to Simultaneous Localization and Mapping (http://ei
a.udg.es/~qsalvi/Slam.zip) Vehicle moving in 1D, 2D and 3D.
SLAM Example (http://rogerstuckey.com/2011/02/21/slam-html5/) using Processing.js (http://pr
ocessingjs.org/) of Feature-Based Navigation.
FootSLAM research page (http://www.kn-s.dlr.de/indoornav/footslam_video.html) at DLR
including the related Wifi SLAM and PlaceSLAM approaches.
SLAM lecture (https://www.youtube.com/watch?v=B2qzYCeT9oQ&list=PLpUPoM7Rgzi_7YWn
14Va2FODh7LzADBSm) Online SLAM lecture based on Python.

Retrieved from "https://en.wikipedia.org/w/index.php?

title=Simultaneous_localization_and_mapping&oldid=671889899"

https://en.wikipedia.org/w/index.php?title=Simultaneous_localization_and_mapping&oldid=671889899 7/7