Simultaneous localization and mapping
Encyclopedia
Simultaneous localization and mapping (SLAM) is a technique used by robot
s and autonomous vehicles to build up a map within an unknown environment (without a priori knowledge), or to update a map within a known environment (with a priori knowledge from a given map), while at the same time keeping track
of their current location.
and comparing it to a current set of perceptions. The benefit of a map in aiding the assessment of a location increases as the precision and quality of the current perceptions decrease. Maps generally represent the state at the time that the map is drawn; this is not necessarily consistent with the state of the environment at the time the map is used.
The complexity of the technical processes of locating and mapping under conditions of errors and noise do not allow for a coherent solution of both tasks. Simultaneous localization and mapping (SLAM) is a concept that binds these processes in a loop and therefore supports the continuity of both aspects in separated processes; iterative feedback from one process to the other enhances the results of both consecutive steps.
Mapping is the problem of integrating the information gathered by a set of sensors into a consistent model and depicting that information as a given representation. It can be described by the first characteristic question, What does the world look like? Central aspects in mapping are the representation of the environment and the interpretation of sensor data.
In contrast to this, localization is the problem of estimating the place (and pose
) of the robot relative to a map; in other words, the robot has to answer the second characteristic question, Where am I? Typically, solutions comprise tracking, where the initial place of the robot is known, and global localization, in which no or just some a priori knowledge of the environmental characteristics of the starting position is given.
SLAM is therefore defined as the problem of building a model leading to a new map, or repetitively improving an existing map, while at the same time localizing the robot within that map. In practice, the answers to the two characteristic questions cannot be delivered independently of each other.
Before a robot can contribute to answering the question of what the environment looks like, given a set of observations, it needs to know e.g.:
It is a complex task to estimate the robot's current location without a map or without a directional reference. Here, the location is just the position of the robot or might include, as well, its orientation.
model may be seen as a classic approach of how to communicate sufficient results under conditions of imprecise observation.
Beyond, the answering of the two characteristic questions is not as straightforward as it might sound due to inherent uncertainties in discerning the robot's relative movement from its various sensor
s. Generally, due to the budget of noise in a technical environment, SLAM is not served with just compact solutions, but with a bunch of physical concepts contributing to results.
If at the next iteration
of map building the measured distance and direction traveled has a budget of inaccuracies, driven by limited inherent precision of sensors and additional ambient noise, then any features being added to the map will contain corresponding errors. Over time and motion, locating and mapping errors build cumulatively, grossly distorting the map and therefore the robot's ability to determine (know) its actual location and heading with sufficient accuracy.
There are various techniques to compensate for errors, such as recognizing features that it has come across previously, and re-skewing recent parts of the map to make sure the two instances of that feature become one. Some of the statistical techniques used in SLAM include Kalman filter
s, particle filter
s (aka. Monte Carlo method
s) and scan matching of range data.
s are a method of environment representation which capture the connectivity (i.e., topology
) of the environment rather than creating a geometrically accurate map. As a result, algorithms that create topological maps are not referred to as SLAM.
SLAM is tailored to the available resources, hence not aimed at perfection, but at operational compliance. The published approaches are employed in unmanned aerial vehicles, autonomous underwater vehicles
, planetary rovers
, newly emerging domestic robot
s and even inside the human body.
It is generally considered that "solving" the SLAM problem has been one of the notable achievements of the robotics research in the past decades.
The related problems of data association and computational complexity are amongst the problems yet to be fully resolved.
A significant recent advance in the feature based SLAM literature involved the re-examination 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. Algorithms were developed based on Probability Hypothesis Density (PHD) filtering techniques.
Such optical sensors may be one dimensional (single beam) or 2D- (sweeping) laser rangefinders, 3D Flash LIDAR
, 2D or 3D sonar
sensors and one or more 2D camera
s. 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.
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 special 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. This approach called FootSLAM can be used to automatically build floor plans of buildings that can then be used
by an indoor positioning system
.
in the early 1990s.
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
s and autonomous vehicles to build up a map within an unknown environment (without a priori knowledge), or to update a map within a known environment (with a priori knowledge from a given map), while at the same time keeping track
Dead reckoning
In navigation, dead reckoning is the process of calculating one's current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time, and course...
of their current location.
Operational definition
Maps are used to determine a location within an environment and to depict an environment for planning and navigation; they support the assessment of actual location by recording information obtained from a form of perceptionPerception
Perception is the process of attaining awareness or understanding of the environment by organizing and interpreting sensory information. All perception involves signals in the nervous system, which in turn result from physical stimulation of the sense organs...
and comparing it to a current set of perceptions. The benefit of a map in aiding the assessment of a location increases as the precision and quality of the current perceptions decrease. Maps generally represent the state at the time that the map is drawn; this is not necessarily consistent with the state of the environment at the time the map is used.
The complexity of the technical processes of locating and mapping under conditions of errors and noise do not allow for a coherent solution of both tasks. Simultaneous localization and mapping (SLAM) is a concept that binds these processes in a loop and therefore supports the continuity of both aspects in separated processes; iterative feedback from one process to the other enhances the results of both consecutive steps.
Mapping is the problem of integrating the information gathered by a set of sensors into a consistent model and depicting that information as a given representation. It can be described by the first characteristic question, What does the world look like? Central aspects in mapping are the representation of the environment and the interpretation of sensor data.
In contrast to this, localization is the problem of estimating the place (and pose
Pose (computer vision)
In computer vision and in robotics, a typical task is to identify specific objects in an image and to determine each object's position and orientation relative to some coordinate system. This information can then be used, for example, to allow a robot to manipulate an object or to avoid moving...
) of the robot relative to a map; in other words, the robot has to answer the second characteristic question, Where am I? Typically, solutions comprise tracking, where the initial place of the robot is known, and global localization, in which no or just some a priori knowledge of the environmental characteristics of the starting position is given.
SLAM is therefore defined as the problem of building a model leading to a new map, or repetitively improving an existing map, while at the same time localizing the robot within that map. In practice, the answers to the two characteristic questions cannot be delivered independently of each other.
Before a robot can contribute to answering the question of what the environment looks like, given a set of observations, it needs to know e.g.:
- the robot's own kinematicsKinematicsKinematics is the branch of classical mechanics that describes the motion of bodies and systems without consideration of the forces that cause the motion....
, - which qualities the autonomous acquisition of information has, and,
- from which sources additional supporting observations have been made.
It is a complex task to estimate the robot's current location without a map or without a directional reference. Here, the location is just the position of the robot or might include, as well, its orientation.
Technical problems
SLAM can be thought of as a chicken or egg problem: An unbiased map is needed for localization while an accurate pose estimate is needed to build that map. This is the starting condition for iterative mathematical solution strategies. In comparison, the atomic orbitalAtomic orbital
An atomic orbital is a mathematical function that describes the wave-like behavior of either one electron or a pair of electrons in an atom. This function can be used to calculate the probability of finding any electron of an atom in any specific region around the atom's nucleus...
model may be seen as a classic approach of how to communicate sufficient results under conditions of imprecise observation.
Beyond, the answering of the two characteristic questions is not as straightforward as it might sound due to inherent uncertainties in discerning the robot's relative movement from its various sensor
Sensor
A sensor is a device that measures a physical quantity and converts it into a signal which can be read by an observer or by an instrument. For example, a mercury-in-glass thermometer converts the measured temperature into expansion and contraction of a liquid which can be read on a calibrated...
s. Generally, due to the budget of noise in a technical environment, SLAM is not served with just compact solutions, but with a bunch of physical concepts contributing to results.
If at the next iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
of map building the measured distance and direction traveled has a budget of inaccuracies, driven by limited inherent precision of sensors and additional ambient noise, then any features being added to the map will contain corresponding errors. Over time and motion, locating and mapping errors build cumulatively, grossly distorting the map and therefore the robot's ability to determine (know) its actual location and heading with sufficient accuracy.
There are various techniques to compensate for errors, such as recognizing features that it has come across previously, and re-skewing recent parts of the map to make sure the two instances of that feature become one. Some of the statistical techniques used in SLAM include Kalman filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
s, particle filter
Particle filter
In statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...
s (aka. Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
s) and scan matching of range data.
Mapping
SLAM in the mobile robotics community generally refers to the process of creating geometrically consistent maps of the environment. Topological mapTopological map
In cartography and geology, a topological map is one that has been simplified so that only vital information remains and unnecessary detail has been removed. These maps lack scale, and distance and direction are subject to change and variation, but the relationship between points is maintained...
s are a method of environment representation which capture the connectivity (i.e., topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
) of the environment rather than creating a geometrically accurate map. As a result, algorithms that create topological maps are not referred to as SLAM.
SLAM is tailored to the available resources, hence not aimed at perfection, but at operational compliance. The published approaches are employed in unmanned aerial vehicles, autonomous underwater vehicles
Autonomous Underwater Vehicle
An autonomous underwater vehicle is a robot which travels underwater without requiring input from an operator. AUVs constitute part of a larger group of undersea systems known as unmanned underwater vehicles, a classification that includes non-autonomous remotely operated underwater vehicles...
, planetary rovers
Rover (space exploration)
A rover is a space exploration vehicle designed to move across the surface of a planet or other astronomical body. Some rovers have been designed to transport members of a human spaceflight crew; others have been partially or fully autonomous robots...
, newly emerging domestic robot
Domestic robot
A domestic robot is a robot used for household chores. Thus far, there are only a few limited models, though science fiction writers and other speculators have suggested that they could become more common in the future...
s and even inside the human body.
It is generally considered that "solving" the SLAM problem has been one of the notable achievements of the robotics research in the past decades.
The related problems of data association and computational complexity are amongst the problems yet to be fully resolved.
A significant recent advance in the feature based SLAM literature involved the re-examination 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. Algorithms were developed based on Probability Hypothesis Density (PHD) filtering techniques.
Sensing
SLAM will always use several different types of sensors to acquire data with statistically independent errors. Statistical independence is the mandatory requirement to cope with metric bias and with noise in measures.Such optical sensors may be one dimensional (single beam) or 2D- (sweeping) laser rangefinders, 3D Flash LIDAR
3D Flash LIDAR
- About LIDAR :LIDAR, is an acronym which stands for Light Detection And Ranging based on a laser-radar paradigm. RADAR is the process of transmitting, receiving, detecting, and processing and electromagnetic wave that reflects from a target, a technology that was developed by the German Army in...
, 2D or 3D sonar
Sonar
Sonar is a technique that uses sound propagation to navigate, communicate with or detect other vessels...
sensors and one or more 2D camera
Camera
A camera is a device that records and stores images. These images may be still photographs or moving images such as videos or movies. The term camera comes from the camera obscura , an early mechanism for projecting images...
s. 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.
Recent approaches apply quasi-optical wireless
Wireless
Wireless telecommunications is the transfer of information between two or more points that are not physically connected. Distances can be short, such as a few meters for television remote control, or as far as thousands or even millions of kilometers for deep-space radio communications...
ranging for multi-lateration
Trilateration
In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and...
(RTLS
RTLS
RTLS may refer to:* Real-time locating system - general techniques for asset and staff tracking using wireless hardware and real-time software* Ravenna Training and Logistics Site - an Ohio Army National Guard base....
) or multi-angulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
in conjunction with SLAM as a tribute to erratic wireless measures.
A special kind of SLAM for human pedestrians uses a shoe mounted inertial measurement unit
Inertial measurement unit
An inertial measurement unit, or IMU, is an electronic device that measures and reports on a craft's velocity, orientation, and gravitational forces, using a combination of accelerometers and gyroscopes. IMUs are typically used to maneuver aircraft, including UAVs, among many others, and...
as the main sensor and relies on the fact that
pedestrians are able to avoid walls. This approach called FootSLAM can be used to automatically build floor plans of buildings that can then be used
by an indoor positioning system
Indoor Positioning System
An indoor positioning system is a term used for a network of devices used to wirelessly locate objects or people inside a building. Generally the products offered under this term do not comply with the International standard ISO/IEC 24730 on real-time locating systems . There is currently no de...
.
Locating
The results from sensing will feed the algorithms for locating. According to propositions of geometry, any sensing must include at least one lateration and (n+1) determining equations for an n-dimensional problem. In addition, there must be some additional a priori knowledge about orienting the results versus absolute or relative systems of coordinates with rotation and mirroring.Modeling
Contribution to mapping may work in 2D modeling and respective representation or in 3D modeling and 2D projective representation as well. 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.Literature
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. Other pioneering work in this field was conducted by the research group of Hugh F. Durrant-WhyteHugh F. Durrant-Whyte
Professor Hugh F. Durrant-Whyte is known for his pioneering work on probabilistic methods for robotics. The algorithms developed in his group since the early 1990s permit autonomous vehicles to deal with uncertainty and to localize themselves despite noisy sensor readings .From 1986-1995...
in the early 1990s.
See also
- Kalman filterKalman filterIn statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
- Monte Carlo localizationMonte Carlo localizationIn robotics and sensors, Monte Carlo localization is a Monte Carlo method to determine the position of a robot given a map of its environment based on Markov localization. It is basically an implementation of the particle filter applied to robot localization, and has become very popular in the...
- Particle filterParticle filterIn statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...
- RegistrationImage registrationImage registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, from different times, or from different viewpoints. It is used in computer vision, medical imaging, military automatic target...
of range images - The Mobile Robot Programming Toolkit (MRPT) projectMobile Robot Programming ToolkitThe Mobile Robot Programming Toolkit is a cross-platform and open source C++ library aimed to help robotics researchers to design and implement algorithms related to Simultaneous Localization and Mapping , computer vision and motion planning...
: A set of open-source, cross-platform libraries covering SLAM through particle filterParticle filterIn statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...
ing and Kalman FilteringKalman filterIn statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
.
External links
- SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping)
- Andrew Davison research page at Imperial College LondonImperial College LondonImperial College London is a public research university located in London, United Kingdom, specialising in science, engineering, business and medicine...
about SLAM using vision - Autonomous and Perceptive Systems research page at University of GroningenUniversity of GroningenThe University of Groningen , located in the city of Groningen, was founded in 1614. It is one of the oldest universities in the Netherlands as well as one of its largest. Since its inception more than 100,000 students have graduated...
about visual SLAM - openslam.org A good collection of open source code and explanations of SLAM.
- Matlab Toolbox of Kalman Filtering applied to Simultaneous Localization and Mapping Vehicle moving in 1D, 2D and 3D
- SLAM Example using Processing.js of Feature-Based Navigation.