SLAM: SLAM的发展历程（WIKI）
??????? 參考維基百科： https://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping
??????? 你們叫他SLAM，我還是習(xí)慣叫他三維重建......當(dāng)夏日的中午，你看到一只鳥兒飛在叢林中，鳥兒偶爾被樹葉遮擋，時(shí)隱時(shí)現(xiàn)，但你總能估計(jì)出鳥兒下一時(shí)刻大致的位置。在很多時(shí)刻，人腦潛意識(shí)下使用了濾波，概率密度估計(jì)的最大似然，整個(gè)過(guò)程表現(xiàn)模型為EM方法。
??????? 在機(jī)器人學(xué)中，SLAM為面對(duì)未知環(huán)境進(jìn)行即時(shí)位置和地圖重建。現(xiàn)階段最流行的方法為基于視覺(jué)的濾波方法，比如離子濾波和EKF方法。基于雷達(dá)的方法也可以用于稀疏SLAM問(wèn)題，卻缺乏一定的適用性和親人性。
??????? 在AI行業(yè)里，總會(huì)這樣說(shuō)，怎樣才能達(dá)到人的水平。SLAM問(wèn)題對(duì)應(yīng)了人熟悉未知環(huán)境并根據(jù)位置環(huán)境不斷確定自身位置的過(guò)程，這個(gè)過(guò)程中所獲的信息一般只是視覺(jué)信息，因此，構(gòu)建類人的方法，使用純視覺(jué)傳感器來(lái)完成SLAM成為一個(gè)更接近于AI的研究方向，且其可達(dá)性顯而易見。
?
古老的歷史
?????? 基于激光雷達(dá)構(gòu)建場(chǎng)景是古老并且可信的方法，激光雷達(dá)也是精確場(chǎng)景使用最多的SLAM傳感器。它們提供機(jī)器人本體與周圍環(huán)境障礙物間的距離信息。常見的激光雷達(dá)，例如SICK、Velodyne還有我們國(guó)產(chǎn)的rplidar等，都可以拿來(lái)做SLAM。激光雷達(dá)能以很高精度測(cè)出機(jī)器人周圍障礙點(diǎn)的角度和距離，從而很方便地實(shí)現(xiàn)SLAM、避障等功能。
Problem definition
???? Given a series of sensor observations o t {\displaystyle o_{t}} over discrete time stepst {\displaystyle t}, the SLAM problem is to compute an estimate of the agent's location x t {\displaystyle x_{t}} and a map of the environmentm t {\displaystyle m_{t}}. All quantities are usually probabilistic, so the objective is to compute:
P ( m t , x t | o 1 : t ) {\displaystyle P(m_{t},x_{t}|o_{1:t})}
???? Applying Bayes' rule gives a framework for sequentially updating the location posteriors, given a map and a transition functionP ( x t | x t ? 1 ) {\displaystyle P(x_{t}|x_{t-1})},
P ( x t | o 1 : t , m t ) = ∑ m t ? 1 P ( o t | x t , m t ) ∑ x t ? 1 P ( x t | x t ? 1 ) P ( x t ? 1 | m t , o 1 : t ? 1 ) / Z {\displaystyle P(x_{t}|o_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1})/Z}
???? Similarly the map can be updated sequentially by
P ( m t | x t , o 1 : t ) = ∑ x t ∑ m t P ( m t | x t , m t ? 1 , o t ) P ( m t ? 1 , x t | o 1 : t ? 1 , m t ? 1 ) {\displaystyle P(m_{t}|x_{t},o_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1})}
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 ofEM algorithm.
???? ?? 被看作一個(gè)EM方法
Algorithms
?????????? Statistical techniques used to approximate the above equations includeKalman 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'sProject Tango.
?????????? 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, 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 locationx t {\displaystyle x_{t}} and 0 if inconsistent.
???????? 地圖：表示真實(shí)環(huán)境的數(shù)據(jù)映射，一般使用拓?fù)鋱D地圖表示全局的地圖結(jié)構(gòu)。另外的一種表達(dá)方式為網(wǎng)格地圖，網(wǎng)格地圖為離散坐標(biāo)系的全覆蓋。拓?fù)涞貓D和網(wǎng)格地圖有各自的優(yōu)點(diǎn)，并適用于不同的環(huán)境。
?
?
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.[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 viaimage 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 modelP ( 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 LiDAR,3D Flash LIDAR, 2D or 3Dsonar 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[7] (sensing by local touch only), 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) ormulti-angulation in conjunction with SLAM as a tribute to erratic wireless measures. A kind of SLAM for human pedestrians uses a shoe mountedinertial 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 anindoor positioning system.[9]
???????? For some outdoor applications, the need for SLAM has been almost entirely removed due to high precision differentialGPS 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.
???????? 傳感器：SLAM有時(shí)需要不同的傳感器，在數(shù)據(jù)獲取上表現(xiàn)為高斯獨(dú)立的性質(zhì)。傳感器模型可分為基于標(biāo)記的模型和基于原始數(shù)據(jù)的模型。其區(qū)別在于有沒(méi)有對(duì)數(shù)據(jù)進(jìn)行標(biāo)記和假設(shè)。
???????? 光學(xué)傳感器有一維和二維、三維激光雷達(dá)，或者更多的是圖像傳感器。隨著移動(dòng)攝影設(shè)備的普及，基于視覺(jué)的SLAM成為主流。
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 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.
?????????? 動(dòng)力學(xué)模型：轉(zhuǎn)移概率用以描述環(huán)境模型，包含了運(yùn)動(dòng)模型和一部分環(huán)境噪音模型。對(duì)于2d機(jī)器人，動(dòng)力學(xué)模型通常用一個(gè)旋轉(zhuǎn)和移動(dòng)的混合模型進(jìn)行表述，并附加一定的獨(dú)立噪音。由于噪音的分布一般不是高斯的，但接近于高斯，因此使用一個(gè)傳感器模型相對(duì)于動(dòng)力學(xué)模型更好一些。
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]
???????? Popular techniques for handling multiple objects includeJoint Probabilistic Data Association Filter (JPDAF) and probability hypothesis density filter (PHD).
???????? 多目標(biāo)：數(shù)據(jù)關(guān)聯(lián) 和計(jì)算復(fù)雜度估計(jì)使用到 多個(gè)待分析的目標(biāo)。一個(gè)有意義的提升是基于特征的SLAM的使用，廣泛使用機(jī)器學(xué)習(xí)的方法（如一個(gè)貝葉斯分類器）。
?
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.[citation needed]
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 comparingbag of words vectors of SIFT features from each previously visited location.
?? ?? ? 閉環(huán)檢測(cè)：是一個(gè)識(shí)別是否進(jìn)入先前環(huán)境的過(guò)程，檢測(cè)到閉環(huán)可以相應(yīng)的提高可信度，降低誤差。經(jīng)典的閉環(huán)檢測(cè)的算法是使用基于局部特征SIFT的詞包模型，匹配每一個(gè)走過(guò)的場(chǎng)景。
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.
???????? 動(dòng)態(tài) SLAM 把 Agent ”將要去哪兒“ 這個(gè)議題結(jié)合起來(lái)。
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[according to whom?].
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 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]
?
????????? 復(fù)雜度：SLAM是一個(gè)計(jì)算復(fù)雜的問(wèn)題，持續(xù)的曾來(lái)那個(gè)地圖和環(huán)境增加了過(guò)程的復(fù)雜度.........
?
Implementations
????????? Various SLAM algorithms are implemented in the open-sourcerobot operating system (ROS) libraries.
????????? 執(zhí)行環(huán)境：一般的SLAM算法，都實(shí)現(xiàn)了對(duì)ROS的兼容，可以在ROS上運(yùn)行。
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.
?
??????? SLAM問(wèn)題最先是由Smith?Self?和Cheeseman?在1988年提出來(lái)的，被認(rèn)為是實(shí)現(xiàn)真正全自主移動(dòng)機(jī)器人的關(guān)鍵。 由?Smith, R.C. and P. Cheeseman, 提出的論文：On the Representation and Estimation of Spatial Uncertainty. 《International Journal of Robotics Research》, 1986. 5(4): p. 56 -- 68. 以濾波的形式表示SLAM問(wèn)題。
??????? 基于統(tǒng)計(jì)的濾波器思路，把SLAM寫成一個(gè)運(yùn)動(dòng)方程和觀測(cè)方程，以最小化這兩個(gè)方程中的噪聲項(xiàng)為目的，使用典型的濾波器思路來(lái)解決SLAM問(wèn)題。
????? ?具體方法：當(dāng)一個(gè)幀到達(dá)時(shí)，我們能（通過(guò)碼盤或IMU）測(cè)出該幀與上一幀的相對(duì)運(yùn)動(dòng)，但是存在噪聲，是為運(yùn)動(dòng)方程。同時(shí)，通過(guò)傳感器對(duì)路標(biāo)的觀測(cè)，我們測(cè)出了機(jī)器人與路標(biāo)間的位姿關(guān)系，同樣也帶有噪聲，是為觀測(cè)方程。通過(guò)這兩者信息，我們可以預(yù)測(cè)出機(jī)器人在當(dāng)前時(shí)刻的位置。同樣，根據(jù)以往記錄的路標(biāo)點(diǎn)，我們又能計(jì)算出一個(gè)卡爾曼增益，以補(bǔ)償噪聲的影響。于是，對(duì)當(dāng)前幀和路標(biāo)的估計(jì)，即是這個(gè)預(yù)測(cè)與更新的不斷迭代的過(guò)程。
????? ? 隨后的時(shí)間里，Se, S., D. Lowe and J. Little,的論文： Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks. 《The international Journal of robotics Research》, 2002. 21(8): p. 735--758.中使用了卡爾曼濾波的方法。
????? ? 使用EKF的方法是一段時(shí)間內(nèi)的SLAM主流方法。
?????? EKF來(lái)由：KF使用高斯分布表示后驗(yàn)概率，這個(gè)高斯分布的均值為ut，協(xié)方差記為Et. 高斯線性的主要問(wèn)題在于，他們只有在運(yùn)動(dòng)模型f 和 測(cè)量模型h 是線性的情況下才比較接近實(shí)際情況。對(duì)于非線性的f 和h ，濾波器更新的結(jié)果往往不是高斯的。因此使用KF的定位算法需要將運(yùn)動(dòng)模型和傳感器模型進(jìn)行線性化（linearize），使用一個(gè)線性函數(shù)對(duì)非線性函數(shù)進(jìn)行局部近似。通過(guò)一個(gè)一階泰勒展開式對(duì) f 和 h 進(jìn)行線性化的卡爾曼濾波器為EKF。
??????? 稀疏圖集：SALM問(wèn)題通過(guò)不同的概率技術(shù)得到解決，包括EKF方法。使用EKF方法只需增加狀態(tài)向量和環(huán)境中地標(biāo)的位置，且EKF方法對(duì)地圖和狀態(tài)向量進(jìn)行二次更新（O(n^2)）。對(duì)于小地圖，計(jì)算方法是可行的。對(duì)于大地圖，則常常使用圖松弛-稀疏圖集的方法進(jìn)行地圖更新。
????? ? BA方法：21世紀(jì)之后，SLAM研究者開始借鑒SFM（Structure from Motion）問(wèn)題中的方法，把平差方法--捆集優(yōu)化BA（Bundle Adjustment）引入到SLAM中來(lái)。優(yōu)化方法和濾波器方法有根本上的不同。它并不是一個(gè)迭代的過(guò)程，而是考慮過(guò)去所有幀中的信息，這是一個(gè)最小二乘和最大似然的區(qū)別。通過(guò)優(yōu)化，把誤差平均分到每一次觀測(cè)當(dāng)中。在SLAM中的Bundle Adjustment常常以圖的形式給出，所以研究者亦稱之為圖優(yōu)化方法（Graph Optimization）。圖優(yōu)化可以直觀地表示優(yōu)化問(wèn)題，可利用稀疏代數(shù)進(jìn)行快速的求解，表達(dá)回環(huán)也十分的方便，因而成為現(xiàn)今視覺(jué)SLAM中主流的優(yōu)化方法。
???????
The Future
???????? SLAM始終是一個(gè)計(jì)算復(fù)雜的問(wèn)題，增量地圖的更新帶來(lái)的計(jì)算代價(jià)是不可避免的，正是由于計(jì)算能力的提升，以及殘差和函數(shù)矩陣的稀疏性的認(rèn)識(shí)，BA方法在視覺(jué)SLAM才有更廣泛的流行。實(shí)時(shí)性需要有強(qiáng)有力的計(jì)算能力作為支撐，硬件的提升是促進(jìn)SLAM發(fā)展的潛力所在。
?
總結(jié)
以上是生活随笔為你收集整理的SLAM: SLAM的发展历程（WIKI）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 支付宝每天转账限额多少
- 下一篇： 清博指数