Simultaneous localization and mapping (SLAM) is a process where a computer constructs or updates a map of an unknown environment while simultaneously keeping track of an entity's location within it. While this initially appears to be a chicken or the egg problem, there are several algorithms known to solve it in, at least approximately, tractable time for certain environments. Popular approximate solution methods include the particle filter, extended Kalman filter, covariance intersection, and GraphSLAM. SLAM algorithms are based on concepts in computational geometry and computer vision, and are used in robot navigation, robotic mapping and odometry for virtual reality or augmented reality. SLAM algorithms are tailored to the available resources and are not aimed at perfection but at operational compliance. Published approaches are employed in self-driving cars, unmanned aerial vehicles, autonomous underwater vehicles, planetary rovers, newer domestic robots and even inside the human body. == Mathematical description of the problem == Given a series of controls u t {\displaystyle u_{t}} and sensor observations o t {\displaystyle o_{t}} over discrete time steps t {\displaystyle t} , the SLAM problem is to compute an estimate of the agent's state x t {\displaystyle x_{t}} and a map of the environment m t {\displaystyle m_{t}} . All quantities are usually probabilistic, so the objective is to compute P ( m t + 1 , x t + 1 | o 1 : t + 1 , u 1 : t ) {\displaystyle P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t})} Applying Bayes' rule gives a framework for sequentially updating the location posteriors, given a map and a transition function P ( x t | x t − 1 ) {\displaystyle P(x_{t}|x_{t-1})} , P ( x t | o 1 : t , u 1 : t , m t ) = ∑ m t − 1 P ( o t | x t , m t , u 1 : t ) ∑ x t − 1 P ( x t | x t − 1 ) P ( x t − 1 | m t , o 1 : t − 1 , u 1 : t ) / Z {\displaystyle 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} where Z {\displaystyle Z} is the normalization constant, which ensures all the probabilities sum up to 1. Similarly the map can be updated sequentially by P ( m t | x t , o 1 : t , u 1 : t ) = ∑ x t ∑ 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 ) {\displaystyle 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})} 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 an expectation–maximization algorithm. == Algorithms == Statistical techniques used to approximate the above equations include Kalman filters and particle filters (the algorithm behind Monte Carlo Localization). They provide an estimation of the posterior probability distribution 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. Other approximation methods achieve improved computational efficiency by using simple bounded-region representations of uncertainty. Set-membership techniques are mainly based on interval constraint propagation. 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 ARCore which replaces their prior augmented reality computing platform named Tango, formerly Project 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, 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. 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 to simplify computation. Under such assumption, P ( m t | x t , m t − 1 , o t ) {\displaystyle P(m_{t}|x_{t},m_{t-1},o_{t})} are set to 1 if the new map's cells are consistent with the observation o t {\displaystyle o_{t}} at location x t {\displaystyle x_{t}} 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 localization only task, perhaps allowing for moving objects such as cars and people only to be updated in the map at runtime. === 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. 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 which 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 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 which location can be estimated by a sensor, such as Wi-Fi access points or radio beacons. Raw-data approaches make no assumption that landmarks can be identified, and instead model P ( o t | x t ) {\displaystyle P(o_{t}|x_{t})} directly as a function of the location. Optical sensors may be one-dimensional (single beam) or 2D- (sweeping) laser rangefinders, 3D high definition light detection and ranging (lidar), 3D flash lidar, 2D or 3D sonar sensors, and one or more 2D cameras. Since the invention of local features, such as SIFT, there has been intense research into visual SLAM (VSLAM) using primarily visual (camera) sensors, because of the increasing ubiquity of cameras such as those in mobile devices. Follow up research includes. Both 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), radar SLAM, acoustic SLAM, and Wi-Fi-SLAM (sensing by strengths of nearby Wi-Fi access points). Recent approaches apply quasi-optical wireless ranging for multi-lateration (real-time locating system (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. 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 which likelihoods are so sharp that they completely dominate the inference. However, GPS sensors may occasionally decline or go down entirely, e.g. during times of military conflict, which are of particular interest to some robotics applications. === Kinematics modeling === The P ( x t | x t − 1 ) {\displaystyle P(x_{t}|x_{t-1})} 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 con
Read more →
