View source for Simultaneous localization and mapping

{{short description|computational problem of constructing a map while tracking an agent's location within it}}
[[File:Stanley2.JPG|thumb|240px|2005 [[DARPA Grand Challenge]] winner [[Stanley (vehicle)|STANLEY]] performed SLAM as part of its autonomous driving system]]
[[File:RoboCup Rescue arena map generated by robot Hector from Darmstadt at 2010 German open.jpg|thumb|A map generated by a SLAM Robot.]]
In [[Mobile robot navigation|navigation]], [[robotic mapping]] and [[odometry]] for [[virtual reality]] or [[augmented reality]], '''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.<ref>{{Cite journal|last=Durrant-Whyte|first=H.|last2=Bailey|first2=T.|date=2006|title=Simultaneous localization and mapping: part I|url=https://ieeexplore.ieee.org/document/1638022/|journal=IEEE Robotics & Automation Magazine|language=en-US|volume=13|issue=2|pages=99–110|doi=10.1109/mra.2006.1638022|issn=1070-9932|via=|citeseerx=10.1.1.135.9810}}</ref><ref>{{Cite journal|last=Bailey|first=T.|last2=Durrant-Whyte|first2=H.|date=2006|title=Simultaneous localization and mapping (SLAM): part II|url=https://ieeexplore.ieee.org/document/1678144/|journal=IEEE Robotics & Automation Magazine|language=en-US|volume=13|issue=3|pages=108–117|doi=10.1109/mra.2006.1678144|issn=1070-9932|via=}}</ref><ref name=":0">{{Cite journal|last=Cadena|first=Cesar|last2=Carlone|first2=Luca|last3=Carrillo|first3=Henry|last4=Latif|first4=Yasir|last5=Scaramuzza|first5=Davide|last6=Neira|first6=Jose|last7=Reid|first7=Ian|last8=Leonard|first8=John J.|date=2016|title=Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age|url=https://ieeexplore.ieee.org/document/7747236/|journal=IEEE Transactions on Robotics|language=en-US|volume=32|issue=6|pages=1309–1332|doi=10.1109/tro.2016.2624754|issn=1552-3098|via=|arxiv=1606.05830}}</ref><ref name=":1">{{Citation|last=Perera|first=Samunda|title=Exploration: Simultaneous Localization and Mapping (SLAM)|date=2014|url=https://doi.org/10.1007/978-0-387-31439-6_280|work=Computer Vision: A Reference Guide|pages=268–275|editor-last=Ikeuchi|editor-first=Katsushi|publisher=Springer US|language=en|doi=10.1007/978-0-387-31439-6_280|isbn=9780387314396|access-date=2019-07-16|last2=Barnes|first2=Dr.Nick|last3=Zelinsky|first3=Dr.Alexander}}</ref> 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]], [[extended Kalman filter]], [[Covariance intersection]], and [[GraphSLAM]].

SLAM algorithms are tailored to the available resources, hence not aimed at perfection, but at operational compliance. Published approaches are employed in [[self-driving cars]], [[unmanned aerial vehicles]], [[Autonomous Underwater Vehicle|autonomous underwater vehicles]], [[Rover (space exploration)|planetary rovers]], newer [[domestic robot]]s and even inside the human body.<ref name=Mountney2006>{{cite journal
 | author = Mountney, P.
 | collaboration = Stoyanov, D.; Davison, A.; Yang, G-Z.
 | year = 2006
 | title = Simultaneous Stereoscope Localization and Soft-Tissue Mapping for Minimal Invasive Surgery
 | journal= MICCAI
 | volume = 1
 | pages = 347–354
 | url = http://www.sciweavers.org/external.php?u=http%3A%2F%2Fwww.doc.ic.ac.uk%2F%7Epmountne%2Fpublications%2FMICCAI%25202006.pdf&p= 
 | accessdate = 2010-07-30
 | doi = 10.1007/11866565_43
| series = Lecture Notes in Computer Science
 | isbn = 978-3-540-44707-8
 }}</ref>

== Problem definition ==

Given a series of controls <math>u_t</math> and sensor observations <math>o_t</math> over discrete time steps <math>t</math>, the SLAM problem is to compute an estimate of the agent's location <math>x_t</math> and a map of the environment <math>m_t</math>. All quantities are usually probabilistic, so the objective is to compute:

:<math> P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t}) </math>

Applying [[Bayes' rule]] gives a framework for sequentially updating the location posteriors, given a map and a transition function <math>P(x_t|x_{t-1})</math>,

:<math> P(x_t|o_{1:t},u_{1:t},m_t) =  \sum_{m_{t-1} } P(o_{t}|x_t, m_t,u_{1:t}) \sum_{x_{t-1}} P(x_t|x_{t-1}) P(x_{t-1}|m_t, o_{1:t-1},u_{1:t}) /Z </math>

Similarly the map can be updated sequentially by

:<math> P(m_t|x_t,o_{1:t},u_{1:t}) =  \sum_{x_t} \sum_{m_t}  P(m_t | x_t, m_{t-1}, o_t,u_{1:t} )   P(m_{t-1},x_t|o_{1:t-1},m_{t-1},u_{1:t}) </math>

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 filter]]s and [[particle filter]]s (aka. [[Monte Carlo method]]s). They provide an estimation of the posterior probability function for the pose of the robot and for the parameters of the map. Methods which conservatively approximate the above model using [[Covariance intersection]] are able to avoid reliance on statistical independence assumptions to reduce algorithmic complexity for large-scale applications.<ref>{{cite conference | last1= Julier |first1=S. |last2=Uhlmann |first2=J. | title = Building a Million-Beacon Map. | conference = Proceedings of ISAM Conference on Intelligent Systems for Manufacturing, | year = 2001|url=https://www.spiedigitallibrary.org/conference-proceedings-of-spie/4571/0000/Building-a-million-beacon-map/10.1117/12.444158.short}}</ref> Other approximation methods achieve improved computational efficiency by using simple bounded-region representations of uncertainty.<ref>{{cite conference | last1= Csorba |first1=M. |last2=Uhlmann |first2=J. | title = A Suboptimal Algorithm for Automatic Map Building. | conference = Proceedings of the 1997 American Control Conference, | year = 1997|url=https://ieeexplore.ieee.org/abstract/document/611857/}}</ref>

[[Set estimation|Set-membership techniques]] are mainly based on [[interval propagation|interval constraint propagation]].<ref>
{{cite journal|last1=Jaulin|first1=L.|
title=A nonlinear set-membership approach for the localization and map building of an underwater robot using interval constraint propagation|
journal=IEEE Transactions on Robotics|volume=25|pages=88–98|
year=2009|
url=http://www.ensta-bretagne.fr/jaulin/paper_reder_ieee_tro.pdf|doi=10.1109/TRO.2008.2010358}}
</ref><ref>
{{cite journal|last1=Jaulin|first1=L.|
title=Range-only SLAM with occupancy maps; A set-membership approach|
journal=IEEE Transactions on Robotics|volume=27|issue=5|pages=1004–1010|
year=2011|
url=http://www.ensta-bretagne.fr/jaulin/paper_dig_slam.pdf|doi=10.1109/TRO.2011.2147110}}
</ref> 
They provide a set which encloses the pose of the robot and a set approximation of the map. [[Bundle adjustment]], and more generally [[Maximum a posteriori estimation]] (MAP), is another popular technique for SLAM using image data, which jointly estimates poses and landmark positions, increasing map fidelity, and is used in commercialized SLAM systems such as Google's [https://developers.google.com/ar/ ARCore] which replaces their previous [[augmented reality]] project '[[Project Tango|Tango]]'. MAP estimators compute the most likely explanation of the robot poses and the map given the sensor data, rather than trying to estimate the entire posterior probability.

New SLAM algorithms remain an active research area,<ref name=":0" /> 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 map]]s 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.<ref name=cummins2008>
{{cite journal
|last1=Cummins |first1=Mark
|last2=Newman |first2=Paul
|title=FAB-MAP: Probabilistic localization and mapping in the space of appearance
|journal=The International Journal of Robotics Research
|date=June 2008
|volume=27|issue=6|pages=647–665
|doi=10.1177/0278364908090961
|url=http://www.robots.ox.ac.uk/~mjc/Papers/IJRR_2008_FabMap.pdf
|accessdate=23 July 2014}}</ref>

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, <math>P(m_t | x_t, m_{t-1}, o_t ) </math> are set to 1 if the new map's cells are consistent with the observation <math>o_t</math> at location <math>x_t</math> and 0 if inconsistent.

Modern [[self driving cars]] mostly simplify the mapping problem to almost nothing, by making extensive use of highly detailed map data collected in advance.   This can include map annotations to the level of marking locations of individual white line segments and curbs on the road.   Location-tagged visual data such as Google's [[StreetView]] may also be used as part of maps.   Essentially such systems simplify the SLAM problem to a simpler [[Robot localization|localisation]] only task, perhaps allowing for moving objects such as cars and people only to be updated in the map at runtime.

=== Sensing ===
{{see also|3D scanner}}
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.<ref name="magnabosco13slam">{{cite journal| last1=Magnabosco |first1=M. |last2=Breckon |first2=T.P. |title=Cross-Spectral Visual Simultaneous Localization And Mapping (SLAM) with Sensor Handover| journal=Robotics and Autonomous Systems|date=February 2013 |volume=63 |issue=2 |pages=195–208 |doi=10.1016/j.robot.2012.09.023 |url=http://www.durham.ac.uk/toby.breckon/publications/papers/magnabosco13slam.pdf |accessdate=5 November 2013}}</ref> Statistical independence is the mandatory requirement to cope with metric bias and with noise in measurements. Different types of sensors give rise to different SLAM algorithms whose assumptions are most appropriate to the sensors. At one extreme, laser scans or visual features provide details of many points within an area, sometimes rendering SLAM inference is unnecessary because shapes in these point clouds can be easily and unambiguously aligned at each step via [[image registration]]. At the opposite extreme, [[tactile sensor]]s 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 <math>P(o_t|x_t)</math> directly as a function of the location.

Optical sensors may be one-dimensional (single beam) or 2D- (sweeping) [[laser rangefinder]]s, 3D High Definition LiDAR, [[3D Flash LIDAR]], 2D or 3D [[sonar]] sensors and one or more 2D [[camera]]s.<ref name="magnabosco13slam" /> 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.<ref name=KarlssonEtAl2005>{{cite conference
 | author = Karlsson, N.
 | collaboration = Di Bernardo, E.; Ostrowski, J; Goncalves, L.; Pirjanian, P.; Munich, M.
 | year = 2005
 | title = The vSLAM Algorithm for Robust Localization and Mapping
 | conference = Int. Conf. on Robotics and Automation (ICRA)
 | url = http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1570091&tag=1
}}</ref> Visual and [[Lidar|LIDAR]] sensors are informative enough to allow for landmark extraction in many cases. Other recent forms of SLAM include tactile SLAM<ref>{{cite conference | last1= Fox |first1=C. |last2=Evans |first2=M. |last3=Pearson |first3=M. |last4=Prescott |first4=T. | title = Tactile SLAM with a biomimetic whiskered robot. | conference = Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), | year = 2012|url=http://eprints.uwe.ac.uk/18384/1/fox_icra12_submitted.pdf}}</ref> (sensing by local touch only), radar SLAM,<ref>{{cite conference | last1=Marck |first1=J.W. |last2=Mohamoud |first2=A. |last3=v.d. Houwen |first3=E. |last4=van Heijster |first4=R. | title = Indoor radar SLAM A radar application for vision and GPS denied environments. | conference = Radar Conference (EuRAD), 2013 European | year = 2013|url=http://publications.tno.nl/publication/34607287/4nJ48k/marck-2013-indoor.pdf}}</ref> acoustic SLAM,<ref>Evers, Christine, Alastair H. Moore, and Patrick A. Naylor. "[https://spiral.imperial.ac.uk/bitstream/10044/1/38877/2/2016012291332_994036_4133_Final.pdf Acoustic simultaneous localization and mapping (a-SLAM) of a moving microphone array and its surrounding speakers]." 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2016.</ref> and wifi-SLAM (sensing by strengths of nearby wifi access points).<ref>Ferris, Brian, Dieter Fox, and Neil D. Lawrence. "[https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-399.pdf Wifi-slam using gaussian process latent variable models]." IJCAI. Vol. 7. No. 1. 2007.</ref> Recent approaches apply quasi-optical [[wireless]] ranging for [[Trilateration|multi-lateration]] ([[Real-time locating system|RTLS]]) or [[Triangulation|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]].<ref name=RobertsonEtAl2009>{{cite conference
 |last1       = Robertson
 |first1      = P.
 |last2       = Angermann
 |first2      = M.
 |last3       = Krach
 |first3      = B.
 |year        = 2009
 |title       = Simultaneous Localization and Mapping for Pedestrians using only Foot-Mounted Inertial Sensors
 |conference  = Ubicomp 2009
 |location    = Orlando, Florida, USA
 |publisher   = ACM
 |url         = http://www.kn-s.dlr.de/indoornav/ubicomp2009_final_my_pub.pdf
 |doi         = 10.1145/1620545.1620560
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20100816040331/http://www.kn-s.dlr.de/indoornav/ubicomp2009_final_my_pub.pdf
 |archivedate = 2010-08-16
}}</ref>

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 <math>P(x_t|x_{t-1})</math> 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.<ref name=MullaneVoAdams2>{{cite journal
| first1= John
| last1=Mullane
| first2=Ba-Ngu
| last2=Vo
| first3=Martin D.
| last3=Adams
| first4=Ba-Tuong
| last4=Vo 
| title=A random-finite-set approach to Bayesian SLAM
| journal= IEEE Transactions on Robotics
| volume= 27
| issue = 2 
| pages= 268–282
| year= 2011
| url = http://www.ee.uwa.edu.au/~bnvo/vo/MVAV_SLAM11.pdf
| doi = 10.1109/TRO.2010.2101370
}}</ref>

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

=== Multiple cameras ===

''Collaborative SLAM'' combines images from multiple cameras to generate 3D maps.<ref>Zou, Danping, and Ping Tan. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.463.8135&rep=rep1&type=pdf Coslam: Collaborative visual slam in dynamic environments]." IEEE transactions on pattern analysis and machine intelligence 35.2 (2012): 354-366.</ref>

=== Moving objects ===

Non-static environments, such as those containing other vehicles or pedestrians, continue to present research challenges.<ref>{{Cite journal|last=Perera|first=Samunda|last2=Pasqual|first2=Ajith|date=2011|editor-last=Bebis|editor-first=George|editor2-last=Boyle|editor2-first=Richard|editor3-last=Parvin|editor3-first=Bahram|editor4-last=Koracin|editor4-first=Darko|editor5-last=Wang|editor5-first=Song|editor6-last=Kyungnam|editor6-first=Kim|editor7-last=Benes|editor7-first=Bedrich|editor8-last=Moreland|editor8-first=Kenneth|editor9-last=Borst|editor9-first=Christoph|title=Towards Realtime Handheld MonoSLAM in Dynamic Environments|url=https://link.springer.com/chapter/10.1007/978-3-642-24028-7_29|journal=Advances in Visual Computing|series=Lecture Notes in Computer Science|language=en|publisher=Springer Berlin Heidelberg|pages=313–324|doi=10.1007/978-3-642-24028-7_29|isbn=9783642240287}}</ref><ref name=":1" /> SLAM with DATMO is a model which tracks moving objects in a similar way to the agent itself.<ref name=Wang2007>{{cite journal
| last1 = Wang
| first1 = Chieh-Chih
| last2 = Thorpe
| first2 = Charles
| last3 = Thrun
| first3 = Sebastian
| last4 = Hebert
| first4 = Martial
| last5 = Durrant-Whyte
| first5 = Hugh
| title = Simultaneous Localization, Mapping and Moving Object Tracking
| journal = Int. J. Rob. Res.
| volume = 26
| number = 9
| year = 2007
| pages = 889–916
| url = https://www.ri.cmu.edu/pub_files/pub4/wang_chieh_chih_2007_1/wang_chieh_chih_2007_1.pdf
| doi = 10.1177/0278364907081229
| publisher = Sage Publications, Inc.
}}</ref>

=== Loop closure ===

Loop closure is the problem of recognizing a previously-visited location and updating 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 compute some type of sensor measure 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 model in computer vision|bag of words]] vectors of [[Scale-invariant feature transform|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,<ref name="Howard">{{cite journal|last1=Howard|first1=MW|last2=Fotedar|first2=MS|last3=Datey|first3=AV|last4=Hasselmo|first4=ME|title= The temporal context model in spatial navigation and relational learning: toward a common explanation of medial temporal lobe function across domains|journal=Psychological Review|volume=112|issue=1|pages=75–116|publisher= 2005, Psychol Rev. 112(1):75-116.|pmc=1421376|year=2005|pmid=15631589|doi=10.1037/0033-295X.112.1.75}}</ref><ref name="Fox & Prescott">{{cite book|last1=Fox|first1=C|title=The 2010 International Joint Conference on Neural Networks (IJCNN)|pages=1–8|last2=Prescott|first2=T|chapter=Hippocampus as Unitary Coherent Particle Filter |publisher=2010, International Joint Conference on Neural Networks |doi=10.1109/IJCNN.2010.5596681|year=2010|isbn=978-1-4244-6916-1}}</ref><ref name="RatSLAM">{{cite book|last1=Milford|first1=MJ|last2=Wyeth|first2=GF|last3=Prasser|first3=D |title=RatSLAM: a hippocampal model for simultaneous localization and mapping.| publisher= Proceedings. ICRA'04. IEEE International Conference on. Vol. 1. IEEE, 2004.|url=https://eprints.qut.edu.au/37593/1/c37593.pdf}}</ref> giving rise to [[place cells]], and has formed the basis for bio-inspired SLAM systems such as RatSLAM.

=== 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.<ref name="W. W. Norton & Company">{{cite book|last1=Brynjolfsson|first1=Erik|last2=McAfee|first2=Andrew|title=The Second Machine Age: Work, Progress, and Prosperity in a Time of Brilliant Technologies|date=Jan 20, 2014|publisher=W. W. Norton & Company|isbn=9780393239355|page=52}}</ref> 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."<ref>{{cite journal|last1=Aulinas|first1=Josep|title=The SLAM Problem: A Survey|journal=Proceedings of the 2008 Conference on Artificial Intelligence Research & Development|date=2008|pages=363–71|url=http://dl.acm.org/citation.cfm?id=1566899.1566949|accessdate=July 15, 2015}}</ref> 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.

<ref name="Nguyen, V. 2007. pp.658,663">Nguyen, V.; Harati, A; Siegwart, R., "[https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/154237/eth-7839-01.pdf?sequence=1 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</ref> 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 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.<ref name="Nguyen, V. 2007. pp.658,663"/>

== Implementations ==

Various SLAM algorithms are implemented in the open-source [[robot operating system]] (ROS) libraries, often used together with the [[Point Cloud Library]] for 3D maps or visual features from [[OpenCV]].

== 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.<ref name=Smith1986>{{cite journal
 | author = Smith, R.C.
 |author2=Cheeseman, P.
 | year = 1986
 | title = On the Representation and Estimation of Spatial Uncertainty
 | journal = The International Journal of Robotics Research
 | volume = 5
 | issue = 4
 | pages = 56–68
 | url = http://www.frc.ri.cmu.edu/~hpm/project.archive/reference.file/Smith&Cheeseman.pdf
 | doi = 10.1177/027836498600500404 
 | accessdate = 2008-04-08
}}</ref><ref name=Smith1986b>{{cite conference
 |author      = Smith, R.C.
 |author2     = Self, M.
 |author3     = Cheeseman, P.
 |year        = 1986
 |title       = Estimating Uncertain Spatial Relationships in Robotics
 |conference  = UAI '86
 |location    = University of Pennsylvania, Philadelphia, PA, USA
 |booktitle   = Proceedings of the Second Annual Conference on Uncertainty in Artificial Intelligence
 |pages       = 435–461
 |publisher   = Elsevier
 |url         = http://www-robotics.usc.edu/~maja/teaching/cs584/papers/smith90stochastic.pdf
 |url-status     = dead
 |archiveurl  = https://web.archive.org/web/20100702155505/http://www-robotics.usc.edu/~maja/teaching/cs584/papers/smith90stochastic.pdf
 |archivedate = 2010-07-02
}}</ref> Other pioneering work in this field was conducted by the research group of [[Hugh F. Durrant-Whyte]] in the early 1990s.<ref name=Leonard1991>{{cite journal
 | author = Leonard, J.J.
 |author2=Durrant-whyte, H.F.
 | year = 1991
 | title = Simultaneous map building and localization for an autonomous mobile robot
 | journal = Intelligent Robots and Systems' 91.'Intelligence for Mechanical Systems, Proceedings IROS'91. IEEE/RSJ International Workshop on
 | pages = 1442–1447
 | url = http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=174711 
 | accessdate = 2008-04-08
 | doi = 10.1109/IROS.1991.174711
|isbn=978-0-7803-0067-5
 }}</ref> 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 and JUNIOR cars, led by [[Sebastian Thrun]], won the DARPA Grand Challenge and came second in the DARPA Urban Challenge in the 2000s, and included SLAM systems, bringing SLAM to worldwide attention. Mass-market SLAM implementations can now be found in consumer robot vacuum cleaners.<ref>{{Cite news|url=https://www.technologyreview.com/s/541326/the-roomba-now-sees-and-maps-a-home/|title=With a Roomba Capable of Navigation, iRobot Eyes Advanced Home Robots|last=Knight|first=Will|work=MIT Technology Review|access-date=2018-04-25|language=en}}</ref> [[Self-driving cars]] by Google and others have now received licenses to drive on public roads in some US states.

== See also ==

* [[Computational photography]]
* [[Kalman filter]]
* [[Inverse depth parametrization]]
* [[List of SLAM Methods]]
* [[Mobile Robot Programming Toolkit|The Mobile Robot Programming Toolkit (MRPT) project]]: A set of open-source, cross-platform libraries covering SLAM through [[particle filter]]ing and [[Kalman filter|Kalman Filtering]].
* [[Monte Carlo localization]]
* [[Multi Autonomous Ground-robotic International Challenge]]: A $1.6 million international challenge requiring multiple vehicles to collaboratively map a large area
* [[Neato Robotics]]
* [[Particle filter]]
* [[Project Tango]]
* [[image registration|Registration]] of range images
* [[Robotic mapping]]
*''[[Stanley (vehicle)|Stanley]]'', a [[DARPA]] Grand Challenge vehicle winner using SLAM techniques
* [[Stereophotogrammetry]]
* [[Structure from motion]].

== References ==
{{reflist}}

== External links ==
* [http://www.probabilistic-robotics.org/ Probabilistic Robotics by [[Sebastian Thrun]], [[Wolfram Burgard]] and [[Dieter Fox]] with a clear overview of SLAM.] 
* [https://dspace.mit.edu/bitstream/handle/1721.1/36832/16-412JSpring2004/NR/rdonlyres/Aeronautics-and-Astronautics/16-412JSpring2004/A3C5517F-C092-4554-AA43-232DC74609B3/0/1Aslam_blas_report.pdf SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping)].
* [http://www.doc.ic.ac.uk/%7Eajd/index.html Andrew Davison] research page at [[Imperial College London]] about SLAM using vision.
* [https://openslam-org.github.io/ openslam.org] A good collection of open source code and explanations of SLAM.
* [http://eia.udg.es/~qsalvi/Slam.zip Matlab Toolbox of Kalman Filtering applied to Simultaneous Localization and Mapping] Vehicle moving in 1D, 2D and 3D.
* [https://web.archive.org/web/20120313064730/http://www.kn-s.dlr.de/indoornav/footslam_video.html FootSLAM research page] at [[German Aerospace Center|DLR]] including the related Wifi SLAM and PlaceSLAM approaches.
* [https://www.youtube.com/watch?v=B2qzYCeT9oQ&list=PLpUPoM7Rgzi_7YWn14Va2FODh7LzADBSm SLAM lecture] Online SLAM lecture based on Python.

{{Robotics}}

{{DEFAULTSORT:Simultaneous Localization And Mapping}}
[[Category:Robot navigation]]
[[Category:Applied machine learning]]