1、1Simultaneous Localization and Mapping即時定位與地圖構建即時定位與地圖構建 2SLAM指的是機器人在自身位置不指的是機器人在自身位置不確定的條件下確定的條件下,在完全未知環境中在完全未知環境中創建地圖創建地圖,同時利用地圖進行自主同時利用地圖進行自主定位和導航。定位和導航。 SLAM問題可以描述為問題可以描述為: 機器機器人在未知環境中從一個未知位置開人在未知環境中從一個未知位置開始移動始移動,在移動過程中根據位置估在移動過程中根據位置估計和傳感器數據進行自身定位計和傳感器數據進行自身定位,同同時建造增量式地圖。時建造增量式地圖。3SLAM（Simulta

2、neous Localization And Mapping ）中文稱中文稱 “同步定位及建圖同步定位及建圖” 是目前在機器人定位方面的熱門研究課題。到目是目前在機器人定位方面的熱門研究課題。到目前為止，也取得了不少進展。前為止，也取得了不少進展。定位定位(localization): 機器人必須知道自己在機器人必須知道自己在 環境中位置。環境中位置。建圖建圖(mapping): 機器人必須記錄環境中特機器人必須記錄環境中特 征的位置（如果知道自己的位置）征的位置（如果知道自己的位置）SLAM： 機器人在定位的同時建立環境地圖機器人在定位的同時建立環境地圖其基本原理是運過概率統計的方法，通過多

3、特征其基本原理是運過概率統計的方法，通過多特征匹配來達到定位和減少定位誤差的。匹配來達到定位和減少定位誤差的。 基本的基本的SLAM應用的應用的kalman filter。 Sk表示傳感器測試獲取數據，表示傳感器測試獲取數據，Mk-1表示第表示第K-1時刻的局部地圖，時刻的局部地圖，Rk表示表示K時刻機器人的位姿。時刻機器人的位姿。4SLAM問題包括四個基本方面問題包括四個基本方面1） 如何進行環境描述，即環境地如何進行環境描述，即環境地圖的表示方法；圖的表示方法；2） 怎樣獲得環境信息，機器人在怎樣獲得環境信息，機器人在環境中漫游并記錄傳感器的感知數環境中漫游并記錄傳感器的感知數據，這涉及到

4、機器人的定位與環境據，這涉及到機器人的定位與環境特征提取問題；特征提取問題；3） 怎樣表示獲得的環境信息，并怎樣表示獲得的環境信息，并根據環境信息更新地圖，這需要解根據環境信息更新地圖，這需要解決對不確定信息的描述和處理方法；決對不確定信息的描述和處理方法；4） 發展穩定、可靠的發展穩定、可靠的SLAM方法。方法。5該領域所涉及的關鍵性問題可以歸結為：該領域所涉及的關鍵性問題可以歸結為：(1) 地圖的表示方式地圖的表示方式 (大致可分為大致可分為3類類:柵格表示、幾何特征表示和拓撲圖表示柵格表示、幾何特征表示和拓撲圖表示)(2) 不確定性信息處理方法不確定性信息處理方法-不確定性信息處理必須解

5、決以下問題：不確定性信息處理必須解決以下問題： 在地圖和位置的表示中，如何描述運動和感知信息的不確定性? 在迭代過程中，如何處理舊信息與新信息的關系，連續更新地圖與位置? 如何依據不確定的信息進行決策?(3) 數據的關聯；數據的關聯； (為了獲得全局的環境地圖和實現定位，還需要將不同時間、不同地 點的感知信息進行匹配和聯合，存在局部數據之間的關聯問題，也存在局部數據與全局數據的關聯與匹配問題)(4) 自定位；自定位； (移動機器人的定位按照有無環境地圖可以分為基于地圖的定位和無地圖的定位)(5) 探索規劃探索規劃 (主要目的是提高地圖創建的效率，使機器人在較短的時間內感知范圍覆蓋盡可能大的區域

6、，在這方面的研究成果較少)6環境的描述環境的描述-地圖地圖 目前各國研究者已經提出了多種表示法，大致可分為三類：柵格表示、幾何信息表示和拓撲圖表示，每種方法都有自己的優缺點。 柵格地圖表示法即將整個環境分為若干相同大小的柵格，對于每個柵格各指出其中是否存在障礙物。這種方法最早由Elfes和Moravec提出，而后Elfes進行了進一步的研究。優點是(1)創建和維護容易，(2)盡量保留了整個環境的各種信息，(3)借助于該地圖，可以方便地進行自定位和路徑規劃。缺點在于：當柵格數量增大時(在大規模環境或對環境劃分比較詳細時)，對地圖的維護行為將變得困難，同時定位過程中搜索空間很大，如果沒有較好的簡化

7、算法，實現實時應用比較困難。 幾何信息地圖表示法是指機器人收集對環境的感知信息，從中提取更為抽象的幾何特征，例如線段或曲線，使用這些幾何信息描述環境。該表示法更為緊湊，且便于位置估計和目標識別。幾何方法利用卡爾曼濾波在局部區域內可獲得較高精度，且計算量小，但在廣域環境中卻難以維持精確的坐標信息。幾何信息的提取需要對感知信息作額外處理，且需要一定數量的感知數據才能得到結果。 拓撲地圖抽象度高，特別在環境大而簡單時。這種方法將環境表示為一張拓撲意義中的圖(graph)，圖中的節點對應于環境中的一個特征狀態、地點。如果節點間存在直接連接的路徑則相當于圖中連接節點的弧。優點是：(1)有利于進一步的路徑

8、和任務規劃，(2)存儲和搜索空間都比較小，計算效率高，(3)可以使用很多現有成熟、高效的搜索和推理算法。缺點在于對拓撲圖的使用是建立在對拓撲節點的識別匹配基礎上的，如當環境中存在兩個很相似的地方時，拓撲圖方法將很難確定這是否為同一點。7 SLA M中定位與環境特征提取中定位與環境特征提取移動機器人自定位與環境建模問題是緊密相關的。環境模型的準確性依賴于定位精度，而定位的實現又離不開環境模型。在未知環境中，機器人沒有什么參照物，只能依靠自己并不十分準確的傳感器來獲取外界信息，如同一個盲人在一個陌生環境中摸索的情況。這種情況下，定位是比較困難的。有地圖的定位和有定位的地圖創建都是容易解決的，但無地

9、圖的定位和未解決定位的地圖創建如同雞-蛋問題，無從下手。已有的研究中對這類問題的解決方法可分為兩類：一類利用自身攜帶的多種內部傳感器(包括里程儀、羅盤、加速度計等)，通過多種傳感信息的融合減少定位的誤差，使用的融合算法多為基于卡爾曼濾波的方法。這類方法由于沒有參考外部信息，在長時間的漫游后誤差的積累會比較大。另一類方法在依靠內部傳感器估計自身運動的同時，使用外部傳感器(如激光測距儀、視覺等)感知環境，對獲得的信息進行分析提取環境特征并保存，在下一步通過對環境特征的比較對自身位置進行校正。但這種方法依賴于能夠取得環境特征。環境特征提取的方法有：(1)Hough transform是一類基于灰度圖

10、探察直線和其他曲線的方法。該方法需要一簇能被搜索的預準備的特定曲線，并根據顯示的灰度圖中一簇曲線產生曲線參數。(2)Clustering分析是一種數據探測工具，對于未分類樣例是有效的，同時，它的目標就是把所針對對象分組成自然類別或基于相似性或距離的簇類。在被提取對象類別未知的情況中，簇技術是一類比Hough Transform更有效的技術。簇類應是以凝聚為中心，而不是支離破碎的、不相交的。而環境特征有時是很難提取出的，例如：環境特征不夠明顯時；傳感器信息比較少，難以從一次感知信息中獲得環境特征。 8不確定信息的描述和處理方法不確定信息的描述和處理方法 在未知環境中，環境信息的不確定性尤為明顯。

11、研究人員已經提出了多種用來處理不確定性的度量方法，如模糊度量、概率度量、信任度量、可能性度量、證據理論度量等等。目前在SLAM中使用較多的主要是模糊度量和概率度量的方法。 以概率描述信息的不確定性，其優點在于：適應不確定模型，對于性能差的傳感器也適用，在實際應用中魯棒性較好，在很多實現中得到應用。缺點是計算量較大，算法建立在一定假設條件上，而假設的合理性有爭議。因此，有些學者認為使用模糊度的描述方法更適合于該任務。他們認為模糊邏輯(fuzzy logic)提供了一個關于處理不確定信息更自然的框架，是一個更為魯棒且有效的工具(尤其對于聲納感知過程引起的不確定性)。同時，在對多種不確定性信息進行建

12、模和融合時有更多的操作符供選擇。 9幾種典型幾種典型SLAM方法方法 目前SLAM方法大致可分為兩類：一類為基于概率模型的方法，另一類為非概率模型方法。許多基于卡爾曼濾波的SLAM方法如完全SLAM、壓縮濾波、FastSLAM就屬于概率模型方法。非概率模型方法有SM-SLAM、掃描匹配、數據融合(data association)、基于模糊邏輯等。 在一個未知的室內結構化環境中提出了基于柵格表示的局部模型與基于幾何信息表示的全局模型相結合的環境建模方式。環境特征的提取采用了Hough transform與Clustering相結合的方法。感知數據的融合采用了擴展卡爾曼濾波方式。 提出的算法不需

13、任何人為設定的參照物(如路標、燈塔)并且可適用于非多邊形及動態環境，同時和基于SLAM的卡爾曼濾波策略比較，其計算復雜度較小、與路標數量、環境大小無關。環境建模策略由3部分構成：(1)收集環境信息；(2)掃描注冊；(3)構建柵格地圖。在掃描注冊中綜合使用了幾何模式匹配與掃描匹配。環境特征提取采用Hough transform技術。采用HIMM (Histogramic In-Motion Mapping)方法來構建柵格地圖。在定位方面，融合使用地圖匹配與基于Petri網的離散事件控制策略。 有以下優勢：(1)在無任何人工路標的情況下，能創建準確地圖；(2)擴展了掃描匹配的應用范圍，使其能應用于

14、非多邊形的環境；(3)提高了幾何模式匹配在多邊形環境中的精確度；(4)每次掃描注冊精度都將與以前所有局部區域掃描結果進行比較，以保證全局地圖的準確性；(5)計算復雜度較小。離散事件控制策略的運用能更好的進行位置估測與對定位錯誤的處理。 提出了使用SM(Set Membership)方法，解決同種多機器人SLAM問題。在地圖融合方面，把2D地圖分解為兩個1D地圖來進行，進一步降低計算復雜度。在SLAM中使用SP-Model(Symmetries and Perturbations Model)，對任何幾何元素它提供了一個統一的表示方式，并避免了參數過多的問題。10說明：機器人在定位誤差隨著機器人

15、的移動而增加。說明：機器人在定位誤差隨著機器人的移動而增加。 說明：機器人在定位誤差隨著機器人的移動而增加，但是由于有了路標的糾正，其誤差相對就小了很多。說明：機器人在定位誤差隨著機器人的移動而增加，但是由于有了路標的糾正，其誤差相對就小了很多。11說明：通過說明：通過2次對路標的測定，其定位誤差已經大大減少次對路標的測定，其定位誤差已經大大減少 說明：經過說明：經過3次誤差校正，其定位精度已經很好了，但是隨著路標位置的丟失，其定位誤差又一次的擴大了。次誤差校正，其定位精度已經很好了，但是隨著路標位置的丟失，其定位誤差又一次的擴大了。12基于霍夫曼方法的基于霍夫曼方法的SLAM的基本過程為：的

16、基本過程為： 1）使用）使用extend kalman filter （EKF) 進行定位進行定位 2）獲取所有的路標和機器人的位置信息作為先決條件）獲取所有的路標和機器人的位置信息作為先決條件 3）使用矢量方程來存儲路標和機器人的位置）使用矢量方程來存儲路標和機器人的位置4）通過循環迭代來減少每次的誤差量）通過循環迭代來減少每次的誤差量13狀態估計是卡爾曼濾波的重要組成部分。一般來說，根據觀測數據狀態估計是卡爾曼濾波的重要組成部分。一般來說，根據觀測數據對隨機量進行定量推斷就是估計問題，特別是對動態行為的狀態估對隨機量進行定量推斷就是估計問題，特別是對動態行為的狀態估計，它能實現實時運行狀態

17、的估計和預測功能。比如對飛行器狀態計，它能實現實時運行狀態的估計和預測功能。比如對飛行器狀態估計。狀態估計對于了解和控制一個系統具有重要意義，所應用的估計。狀態估計對于了解和控制一個系統具有重要意義，所應用的方法屬于統計學中的估計理論。最常用的是最小二乘估計，線性最方法屬于統計學中的估計理論。最常用的是最小二乘估計，線性最小方差估計、最小方差估計、遞推最小二乘估計等。其他如風險準小方差估計、最小方差估計、遞推最小二乘估計等。其他如風險準則的貝葉斯估計、最大似然估計、隨機逼近等方法也都有應用。則的貝葉斯估計、最大似然估計、隨機逼近等方法也都有應用。 受噪聲干擾的狀態量是個隨機量，不可能測得精確值

18、，但可對受噪聲干擾的狀態量是個隨機量，不可能測得精確值，但可對它進行一系列觀測，并依據一組觀測值，按某種統計觀點對它進行它進行一系列觀測，并依據一組觀測值，按某種統計觀點對它進行估計。使估計值盡可能準確地接近真實值，這就是最優估計。真實估計。使估計值盡可能準確地接近真實值，這就是最優估計。真實值與估計值之差稱為估計誤差。若估計值的數學期望與真實值相等，值與估計值之差稱為估計誤差。若估計值的數學期望與真實值相等，這種估計稱為無偏估計。卡爾曼提出的遞推最優估計理論，采用狀這種估計稱為無偏估計。卡爾曼提出的遞推最優估計理論，采用狀態空間描述法，在算法采用遞推形式，卡爾曼濾波能處理多維和非態空間描述法

19、，在算法采用遞推形式，卡爾曼濾波能處理多維和非平穩的隨機過程。平穩的隨機過程。 卡爾曼濾波理論的提出，克服了威納濾波理論的局限性使其在卡爾曼濾波理論的提出，克服了威納濾波理論的局限性使其在工程上得到了廣泛的應用，尤其在控制、制導、導航、通訊等現代工程上得到了廣泛的應用，尤其在控制、制導、導航、通訊等現代工程方面。工程方面。 14圖圖1：初始位置：初始位置（由于機器人相對于路標（由于機器人相對于路標A的位置為估計值，所以路標的位置為估計值，所以路標A用圓圈表示用圓圈表示A的實際的可能值在圓圈內）的實際的可能值在圓圈內）15圖圖2：機器人移動到新位置：機器人移動到新位置（在新的位置，機器人相對于（

20、在新的位置，機器人相對于A的真實值可能落在圈內）的真實值可能落在圈內）16圖圖3：路標：路標C被觀測到被觀測到（在新的位置，路標（在新的位置，路標C被觀測到，路標被觀測到，路標C的相對于的相對于A的位置也是一個估計值（更大的圈）的位置也是一個估計值（更大的圈）17圖圖4：路標：路標B被觀測到被觀測到18圖圖5：機器人返回到初始位置：機器人返回到初始位置（此時機器人的位置相對于沒有移動前更加不確定，一個超大的橢圓表示了其可能的真實位置值范圍）（此時機器人的位置相對于沒有移動前更加不確定，一個超大的橢圓表示了其可能的真實位置值范圍）19圖圖6：對：對A點的重新測量點的重新測量（通過對（通過對A的重新測量，圖的重新測量，圖4中的超大橢圓值被大大的縮小了，其位置真值落入了一個比較小的范圍內）中的