同时定位和地图构建

**同時定位與地圖構建**（英語：Simultaneous localization and mapping，簡稱 **SLAM**）是一種概念：希望機器人從未知環境的未知地點出發，在運動過程中通過重複觀測到的地圖特徵（比如，牆角，柱子等）定位自身位置和姿態，再根據自身位置增量式的構建地圖，從而達到同時定位和地圖構建的目的。

## 歷史

有關於 SLAM 的一個開創性工作是以 R.C. Smith 和 P. Cheeseman 為代表，在 1986 年作出的對空間不確定性的估測的研究。其他該領域的開拓工作由 Hugh F. Durrant-Whyte （頁面存檔備份，存於網際網路檔案館）的研究團隊在 1990 年代初所作出。

由 Sebastian Thrun 帶領的團隊設計出 STANLEY 自動駕駛車於 2005 年勝出了由美國國防高級研究計劃局（DARPA）發起的 DARPA 無人駕駛車大賽賽，其後在 2007 年再設計出另一自動駕駛車 JUNIOR 勝出了同樣由美國國防高級研究計劃局發起的城市無人駕駛車挑戰賽。當中的同步定位與地圖構建系統引起了全球廣泛注意，現在同步定位與地圖構建已被廣泛應用在機器人吸塵器，例如 Neato Robotics 的 XV11，Google 的自動駕駛汽車等。

## 操作性定義

這裡說的地圖，是用來在環境中定位，以及描述當前環境以便於規劃航線的一個概念；它通過記錄以某種形式的感知獲取的信息，用以和當前的感知結果相比較，以支撐對現實定位的評估。在定位評估方面，地圖提供的幫助程度，與感知的精度和質量成反相關。地圖通常反映了它被描繪出來的時刻的環境狀態，所以它並不一定反映它被使用的時刻的環境狀態。

在誤差和噪音條件下，定位和地圖構建技術上的複雜度不支持兩者同時獲得連續的解。SLAM 是這樣一個概念：把兩方面的進程都捆綁在一個循環之中，以此支持雙方在各自進程中都求得連續解；不同進程中相互迭代的反饋對雙方的連續解有改進作用。

地圖構建，是研究如何把從一系列傳感器收集到的信息，集成到一個一致性的模型上的問題。它可以被描述為「第一核心問題」——「這個世界長什麼樣？」地圖構建的核心部分是環境的表達方式以及傳感器數據的解釋。

與之相比，定位，是在地圖上估測機器人的坐標和姿勢形態的問題；換而言之，機器人需要回答這裡的「第二核心問題」：「我在哪？」典型的解包含以下兩個方面：追蹤 —— 通常機器人的初始位置已知；全局定位 —— 通常只給出很少，甚至不給出有關於起始位置環境特徵的先驗信息。

所以，SLAM 被定義為以下問題：在建立新地圖模型或者改進已知地圖的同時，在該地圖模型上定位機器人。實際上，這兩個核心問題如果分開解決，將毫無意義；必須同時求解。

在機器人能夠根據一系列觀測值回答「這個世界長什麼樣」之前，它需要知道的額外信息很多，比如以下：

* 它自身的運動學特徵，
* 信息的自動獲得需要什麼樣的品質，
* 附加的支持觀測值能從哪些源得到。在沒有地圖或者方向參考的前提下，對機器人的當前位置估測是一個複雜的任務。這裡的 "位置" 可以簡單指代機器人的所處方位，也可以包括它的姿勢形態。

## 技術上的問題

SLAM 可以被看做是一個雞生蛋蛋生雞的問題：完美的定位需要用到一個無偏差的地圖；但這樣的地圖又需要精確的位置估測來描繪。這就是一個迭代數學問題解決策略的起始條件。作為對比，原子軌道模型可以被看做一個在不精確的觀測條件下說明足夠多的結果的經典方法。

再者，由於多個傳感器對機器人的相對運動的辨別存在固有的不確定性，上一節提到的兩個「核心問題」也不像看起來的那麼簡單。一般來說，由於技術環境中總會考慮噪聲，所以 SLAM 方法要考慮的不只是數學上的緊湊解，也包括與那些和結果相關的物理概念的相互作用。

如果在地圖構建的下一個迭代步驟中，測得的距離和方向有可預知的一系列不精確度 —— 通常由傳感器有限的的精確度和外加的環境噪聲所引起，那麼附加到地圖上的所有特徵都將會含有相應的誤差。隨著時間的推移和運動的變化，定位和地圖構建的誤差累計增加，將會對地圖本身和機器人的定位、導航等能力的精度產生很大的扭曲。

有許多技術能補償這些誤差，比如那些能再現某些特徵過去的值的方法（也就是說，圖像匹配法或者環路閉合檢測法），或者對現有的地圖進行處理 —— 以融合該特徵在不同時間的不同值。此外還有一些用於 SLAM 統計學的技術可起到作用，包括卡爾曼濾波、粒子濾波 （頁面存檔備份，存於網際網路檔案館）（實際上是一種蒙特卡羅方法）以及掃描匹配的數據範圍。

### 地圖構建

在機器人技術社區中，SLAM 的地圖構建通常指的是建立與環境幾何一致的地圖。而一般算法中建立的拓撲地圖只反映了環境中的各點連接關係，並不能構建幾何一致的地圖。因此，這些拓撲算法不能被用於 SLAM。

在實用中，SLAM 通常要被剪裁至適應可獲得的資源，於是可以看出它的目標不是完美，而是操作實用性。已經發布的 SLAM 方法已被應用於無人機、無人潛艇、行星探測車、最近大熱的家政機器人 （頁面存檔備份，存於網際網路檔案館）、甚至人體內部。

學界大致都認為，SLAM 問題的「正在得到解決」是過去十年間機器人研究領域的最重大成果之一。
該領域中仍有許多有待解決的難題，比如圖像匹配和計算複雜度等方面的相關問題。

基於 SLAM 文獻的最新研究進展中，有一條值得注意，就是對 SLAM 的概率論基礎進行重新估測。這個充滿了冒險家特質的方法大意如下：通過引入隨機有限集的、多目標的貝葉斯濾波器，使得基於特徵的 SLAM 算法獲得卓越的性能，以此跳過對圖像匹配的依賴；但作為代價，測量中的假警報率和漏檢率都會被提升。 
這裡面的算法是基於概率假設密度濾波的方法來改進的。

### 傳感

SLAM 研究中經常使用許多不同型號的傳感器來獲得地圖數據。這些數據帶有統計獨立的誤差。這個統計獨立是解決度量偏差和檢測中的噪聲的強制需求。簡單來說，就是任何一個東西都很難測的準確。比如一根 1 米長的棍子，你第一次測量的時候可能是 1.02 米，第二次測量時 1.05 米，...。總之測量的時候多多少少都會有一些誤差在裡面，因此 SLAM 算法本身必須要有效的處理這些測量誤差。

這些傳感器可以是光學的，比如 1D 的（單波束）或者 2D 的（掃描）雷射測距儀、3D Flash LIDAR、2D 或 3D 聲吶傳感器以及一個或多個 2D 攝像頭。從 2005 年開始，使用可視化傳感器（攝像頭）對 SLAM 的研究（可視化 SLAM）如火如荼地展開，因為從那時起攝像頭開始普及（比如說手機普遍帶有攝像頭）。

新近的方法使用了准光學的無線測距法，同時把三角測距法等幾何方法應用於 SLAM 中，用以消除微弱無線信號對測量的影響。

一種為走路者設計的 SLAM 應用使用了一個裝在鞋頭的慣性測量單元作為主要傳感器，該設計依賴於走路者能自動規避牆體這一假設。這個名為 FootSLAM 的設計可被用於自動建立建築物的樓面布置圖，從而方便建立該建築的室內定位系統。

此外，通過聚眾收集多個用戶的手機信號強度與加速度數據，iFrame 系統可以合成二維室內地圖。並且隨著用戶數的增加，來逐步加強地圖的精度。

### 定位

傳感器的結果會作為定位算法的輸入。由幾何知識可知，對於 n 維的定位問題，任何傳感輸出必須包含至少一個多點定位和 n+1 個判別方程。為了算出結果，有關於在絕對或相對的循環和鏡像坐標系統下得到的結果的先驗知識也是必要的。

### 建模

以上結果對地圖構建的貢獻，可以在「2D 建模並分別表示」或者在「3D 建模並在 2D 上投影表示」中工作得一樣出色。作為建模的一部分，機器人本身的運動學特徵也要被考慮進去，用以提高在固有背景噪聲下的傳感精度。構建的動態模型需平衡不同傳感器、不同局部誤差模型給出來的貢獻值，並最終包含一個基於地圖本身的銳利的可視化描述，這包括機器人的位置和方向等雲概率信息。地圖構建就是這樣一個動態模型的最終運算結果。

## 參見

* 卡爾曼濾波
* 蒙特卡洛定位法
* 粒子濾波
* Stanley：DARPA 地面無人車挑戰賽冠軍，一輛成功使用了 SLAM 技術的無人車
* 深度圖像的圖像配准
* 移動機器人編程工具包項目：一組開源、跨平台的 SLAM 資料庫。
* Multi Autonomous Ground - 國際機器人競賽：一項 160 萬美元的國際競賽，要求參賽者讓多台無人車合作給一大片區域繪製地圖。

## 參考資料

## 外部連結

* Probabilistic Robotics by Sebastian Thrun, Wolfram Burgard and Dieter Fox with a clear overview of SLAM. （頁面存檔備份，存於網際網路檔案館）
* SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping).
* Andrew Davison （頁面存檔備份，存於網際網路檔案館） research page at Imperial College London about SLAM using vision.
* Autonomous and Perceptive Systems （頁面存檔備份，存於網際網路檔案館） research page at University of Groningen 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.
* FootSLAM research page at DLR including the related Wifi SLAM and PlaceSLAM approaches.