測距式傳感器同時定位與地圖創建綜述

劉建華，劉華平，楊建國，高蒙，孫富春

（1．東華大學機械工程學院，上海201620；2．石家莊鐵道大學電氣與電子工程學院，河北石家莊050043；3．清華大學智能技術與系統國家重點實驗室，北京100084）

·信息交流·

測距式傳感器同時定位與地圖創建綜述

劉建華1，2，劉華平3，楊建國1，高蒙2，孫富春3

（1．東華大學機械工程學院，上海201620；2．石家莊鐵道大學電氣與電子工程學院，河北石家莊050043；3．清華大學智能技術與系統國家重點實驗室，北京100084）

移動機器人的同時定位與地圖創建（SLAM）是當前機器人領域中的熱點問題，基于測距傳感器SLAM實質是距離信息的在線提取和描述，本文針對這一問題進行了詳細介紹。此外，闡述了測距式機器人SLAM的解決思路、關鍵技術和實現方法；重點探討了擴展卡爾曼濾波（EKF）、粒子濾波（PF）和矩陣奇異值分解（SVD）3種主要方法的實現過程和存在的問題；對基于測距式的SLAM方法需要解決問題、完善的方面及研究前景進行了闡述。

移動機器人；測距；擴展卡爾曼濾波；粒子濾波；奇異值分解；同時定位與地圖創建

同時定位與地圖創建（simultaneous localization and mapping，SLAM）是移動機器人研究領域中一個關鍵技術［1］，是在未知環境中通過自定位過程獲取周圍環境信息，并在行進過程中逐步構建周圍環境的增量式地圖，同時不斷地重復觀測已構建的地圖來消除不確定因素，進而完成自身位姿的精確估計［2］。因此，機器人位姿估計和地圖構建之間的相互依賴使SLAM問題變得極富挑戰性，需要在高維空間中搜索解決方法［3］。

目前，國內外的研究重點側重于基于特征地圖的定位方法［4］，即通過存儲在地圖中的環境特征與抽象所感知真實環境的特征是否匹配及相對于機器人SLAM的位置來確定機器人的當前位姿，因此環境地圖的表示方式是否合適以及環境特征提取是否準確，直接影響環境特征匹配的效率，進而影響機器人定位和地圖構建的準確性和實時性；測距傳感器由于具有數據處理簡單、實時性高和魯棒性好等優點，得到了廣泛的應用；基于測距式傳感器的機器人定位和地圖構建的基本思想是通過融合傳感器信息，把自身與參照點（如障礙物、環境特征等）及其相互關系的距離信息和方位信息在線抽象描述為全局地圖信息。

基于測距式傳感器機器人SLAM主要從3方面考慮：環境特征的提取方法、地圖的表示方式和解決SLAM問題的核心算法［2］。本文總結目前流行的基于測距式傳感器的SLAM方法，從以上3方面進行了歸類和比較，指出需要解決的關鍵問題，并根據已有的研究成果提出未來的研究方向。

1 典型傳感器類型及其作用

根據機器人所攜帶傳感器在SLAM系統中的主要作用，傳感器大致可分為兩大類，一類是本體傳感器（也稱內部傳感器），如里程計、陀螺儀、指南針、速度或加速度計等；另一類是外部傳感器，如激光雷達、超聲波、紅外線、微波雷達、kinect［5］，機器人通過外部傳感器可以獲得真實環境特征的抽象描述及距離信息或圖像深度信息。基于測距式的SLAM主要框架是采用本體傳感器和外部傳感器相融合的定位方法，利用本體傳感器來實現機器人航跡推算，通過外部傳感器（一種或多種）抽象獲得的外部環境特征及其距離信息與已構建環境地圖的特征匹配，消除航跡推算的累積誤差，獲得當前機器人的位姿偏差，并不斷修正機器人自身位姿，構建增量式的環境地圖。

2 環境模型及測距式傳感器特征提取

真實環境的抽象描述也稱為地圖構建，即用點和線或柵格的集合近似表達真實環境，是將真實環境中連續場景表示成2?D區段，是移動機器人SLAM的一個重要環節［6?7］。地圖中環境特征表征的準確與否直接影響機器人定位和構建地圖的精確性，因此環境特征的表示要注重特征的魯棒性和穩定性。測距式傳感器SALM的環境模型主要有2類，基于特征的地圖和密集型地圖（柵格地圖），前者主要應用于稀疏障礙物或結構化環境，將環境特征作為路標信息，后者主要應用于非結構化環境。在平面坐標系中機器人根據2條相交的直線就可以完成自定位，由于環境中存在諸如角、線的特征較多，而從測距式傳感器檢測到的原始數據中提取這些特征相對容易，其存儲與匹配也簡潔方便，因此采用角、線描述環境成為機器人SLAM問題中最常用的特征描述方式。針對缺少角、線特征的環境，文獻［6，8?9］通過提取天花板的角、線特征來完成機器人定位；此外，根據機器人所在環境的特點，提取具有獨特信息的特征作為路標信息，文獻［10?12］提取環境中圓作為定位路標信息，文獻［6］提取環境中矩形特征作為定位路標信息。隨著環境的復雜性越來越高，對環境二維建模不能滿足需要，文獻［13?14］等提取環境三維特征作為定位路標信息。柵格地圖模型是根據測距傳感器的原始數據獲得障礙物占據柵格情況，從而構建環境地圖［2］。

測距式傳感器采集真實環境的數據是點的集合，如何對這些離散的點處理獲得環境的抽象描述，即局部地圖，很多文獻采用了Hough變換的方法進行局部地圖的構建，但其計算量非常大，很難保證局部地圖構建實時性的要求，文獻［15］比較詳細地分析比較了11種數據點提取特征直線的算法，其中以數據分割擬合（split?and?merge）算法較優，因此該算法得到了廣泛應用；此后，研究者在分析總結上述算法的基礎上，對這些算法做了改進，也提出了很多不同的特征提取算法，如文獻［16］通過建立角點函數來衡量掃描點是角點特征的程度，利用非極大值抑制方法去除干擾信息來提取環境的角點特征，文獻［17］根據split?and?merge算法思想，采用模糊聚類算法分割數據，利用最小二乘法擬合。

直線參數使線段分割的魯棒性和線段提取的精度得到了很大提高，也顯著提高了算法效率。此外，有研究者將比較成熟的優化算法應用到環境特征的提取，如文獻［18］將自組織競爭學習神經網絡（self?organizing feature mapping，SOM）方法用于激光雷達數據的處理，提取更加精確的環境線段、角點等特征，提高了算法的計算效率以及分類性能得到進一步的提高。也有研究者采用卡爾曼濾波對環境的線段等特征進行提取，不僅對線段特征的誤差標準等概率特性進行較好地描述和更新，而且受傳感器的非線性影響也較小。

3 基于測距式傳感器SLAM常用方法

目前，未知環境中機器人利用測距式傳感器的距離信息完成SLAM任務，其基本思想是通過尋找當前局部環境地圖與已獲得的增量式全局環境地圖間的對應關系，減少航跡推算誤差造成的移動機器人定位的不確定性［19］，獲得盡可能精確的機器人當前位姿信息，完備全局環境地圖。目前主要方法可分為基于貝葉斯理論的概率推理定位算法和基于矩陣分解的定位算法兩大類。前者把概率理論應用到移動機器人定位過程中，即在機器人每個可能的位置設置一種概率值，根據機器人運動過程中測距式傳感器感知到的新環境距離信息更新機器人可能位置的概率值，從而減少機器人位置不確定性。其實質是把移動機器人SLAM問題認為是貝葉斯評估過程，通過融合內部傳感器輸入數據和外部傳感器觀測數據，完成移動機器人隱式位姿的預測及更新，使其隱式位姿狀態信度達到最優。比較典型的方法有：基于擴展卡爾曼濾波（extended kalman filter，EKF）和基于粒子濾波（particle filter，PF）SLAM。后者通過分析數據矩陣的特點，把矩陣分解出能反映原矩陣的某些特征的因式矩陣，通過回歸計算因式矩陣獲得當前機器人的位姿和環境信息，完成SLAM任務。

3．1 基于EKF的SLAM定位方法

EKF是將非線性模型（運動模型和觀測模型）在狀態向量的鄰域內泰勒展開，并取其一階或二階項近似表示機器人的運動模型與觀測模型。該方法的基本思想是通過對包含移動機器人與環境特征之間的關系以及機器人運動模型、觀測模型不確定性信息的雅可比矩陣的迭代過程，完成誤差協方差矩陣和增益矩陣的遞推計算。正常情況下，雅可比矩陣是單調遞減且收斂的，因此，對雅可比矩陣的處理是EKF的核心。

基于擴展卡爾曼濾波器的SLAM方法是通過增量評估移動機器人位姿和環境特征位置的聯合后驗概率來估計機器人位姿和構建地圖，是一個循環迭代地估計與校正過程。即機器人根據運動模型估計其新位置，根據機器人觀測模型估計其可能觀測到的環境特征的距離信息；計算估計的觀測值間與實際的觀測值之間的誤差，利用協方差計算卡爾曼濾波增益參數，并利用該參數對機器人的估計位置校正；將新觀測到的環境特征信息加入地圖，逐步完成增量式環境地圖的構建。在估計與校正過程中若系統狀態的協方差較大，則用觀測值校正，使系統偏差變小；若觀測協方差較大，則認為觀測值不可靠，對觀測值做輕微校正［20］。

以EKF理論為基礎的SLAM的方法存在一些固有的缺陷。缺陷一是非線性誤差的存在［2］，由于EKF算法在估計點處通過泰勒展開式對非線性系統進行局部線性化，舍去了高階項，雖然簡化了問題，但使系統產生了截斷誤差。如系統非線性程度較高時，由于系統無法滿足上述線性化假設而產生很大的誤差，從而造成系統不收斂的嚴重后果，因而基于EKF的SLAM的精度和魯棒性受到影響。針對EKF線性化存在的誤差，研究者在如何提高SLAM問題的精度上展開了研究，提出了許多改進算法。如文獻［21］提出迭代擴展卡爾曼濾波算法（iterated extended Kalman filter，IEKF），結合激光雷達傳感器采集的外部環境特征信息，在測量更新階段多次迭代濾波估計值，從而減少由于泰勒展開局部線性化帶來的截斷誤差，提高了SLAM的定位精度，但是其缺點是由于迭代次數的增加，計算量會增大；文獻［22］針對EKF中觀測噪聲方差估計不準確導致濾波器性能下降甚至發散的問題，將模糊卡爾曼濾波技術應用于基于聲吶的移動機器人的定位中，提出了根據信息方差理論值和實際值的一致程度在線調整觀測噪聲方差的自適應調節算法，解決了系統觀測噪聲水平不確定的問題，其性能優于EKF；文獻［23］在光電系統中利用差分方式實現非線性函數線性化的EKF算法，這種方法無需計算復雜的雅克比陣，且能得到更好的定位跟蹤精度；文獻［2，24］提出將隨機梯度下降法引入SLAM問題，達到最小化系統非線性誤差的影響，但是系統的收斂速度變慢了。

基于擴展的卡爾曼濾波器方法得到機器人領域廣泛地接受，但隨著SLAM問題研究的深入，出現了計算復雜度和數據關聯問題，即缺陷二。協方差陣的引入是EKF的最大特點，對協方差陣的計算也是該算法的核心。當環境中的不確定因素和環境特征增加時，協方差陣的元素平方級增加，計算量復雜度為O（K2）（K為特征數目）［25］，即使在某一刻只觀測到一個特征，整個協方差陣元素都必須更新，計算量急劇增加。此外，機器人與環境特征及環境特征與環境特征之間的交叉相關性進一步增加了計算復雜度。文獻［26］采用FPGA技術和并行處理流程完成多個特征同時匹配過程，提高了特征匹配效率；文獻［27］采用表示環境特征之間相對位置的相對地圖代替絕對地圖，解決了環境特征之間的相關問題；文獻［28］用稀疏化信息矩陣代替協方差矩陣，即稀疏擴展信息濾波方法，使更新時間變為常數，不隨特征的增加而增加。

另外，基于EKF的SLAM算法存在2個較難解決的問題：1）假設觀測量與環境特征的數據關聯為已知，即認為它們之間必存在數據關聯，一旦觀測值和環境特征之間出現微小的關聯錯誤，將會導致EKF濾波器發散而使SLAM過程失敗。2）機器人狀態向量無法表征機器人的歷史路徑，無法解耦地圖信息與機器人狀態的關系，當環境地圖增大時導致計算量急劇增大。因此，該方法不適合大規模環境和動態環境的SLAM。

目前，在EKF的SLAM方法的基礎上，提出了一些改進算法，如無跡變換的UKF?SLAM、容積卡爾曼濾波SLAM、平方根容積卡爾曼濾波SLAM等。通過不同的方法獲得SLAM的后驗概率密度，提高了定位精度。

3．2 基于PF的SLAM定位方法

PF是20世紀90年代中后期發展起來的一種比較新的濾波算法。文獻［29］將PF與機器人運動及感知的概率模型相結合，提出了PF的定位方法；其主要思想是用多個濾波器來估計機器人的各個可能位置的概率，利用觀測對每個濾波器進行加權處理，使機器人最有可能位置的概率越來越大［30］。在實際應用中，基于PF的SLAM方法是用一組相關權重的隨機樣本集合，以及基于這些樣本的估計來近似表征后驗概率密度函數，采用樣本均值代替積分運算來獲得狀態最小方差估計的過程。

SLAM主要任務是位姿估計和地圖構建，2者之間又存在相互依賴的關系，這使基于PF的SLAM問題變得非常復雜。文獻［31］提出了SLAM問題的一種有效解決方案，即后驗概率估計的處理方法，其基本思想是通過Rao?Blackwellized將SLAM問題分解為軌跡估計過程與地圖估計過程。先用粒子濾波器估計移動機器人的運動軌跡，再用卡爾曼濾波估計環境地圖，從而將SLAM問題轉化為低維估計問題［32?33］。

式中：s1：t為移動機器人軌跡，u1：t－1為里程計測量，m為觀測z1：t得到的地圖。

在已知s1：t和z1：t的條件下，可以得到地圖的后驗概率p（m｜s1：t，z1：t），而建圖的Rao?Blackweiiized通過PF方法得到機器人潛在軌跡的后驗概率p（s1：t｜z1：t，u1：t－1），并為每個粒子分配一個合適的“粒子地圖”，該地圖是在給定了由相應粒子所表示的s1：t和z1：t條件下建立；換言之，機器人在未知環境中循環運行一圈，每個粒子都估計機器人的軌跡，并相應保留一個“粒子地圖”，該地圖根據軌跡估計不斷更新，即根據已知位姿構建地圖。

常用的Rao?Blackweiiized粒子濾波器建圖過程主要有以下4個步驟：

1）采樣，子代粒子是從當前粒子中根據建議分布q采樣得到；

2）每個粒子賦重要性權值：

3）重采樣，其包含2層意思：1）用有限粒子近似一個連續分布，2）重采樣允許在真實分布與建議分布有差異的情況下使用粒子濾波器；

4）地圖估計，通過已知位姿更新每個粒子的“粒子地圖”。

在Rao?Blackwellized粒子濾波的基礎上，Monte?merlo等［33］提出FastSLAM算法，與基于EKF的SLAM方法不同，其用不同的粒子表征機器人的歷史路徑，能夠解耦地圖特征信息與機器人狀態信息；即將SLAM問題看成機器人行進軌跡的PF估計和機器人位姿估計上環境特征位置卡爾曼濾波估計過程。粒子濾波器中每個粒子代表機器人的一條可能的行進軌跡，利用觀測值計算各個粒子的權重。具體到每個粒子，機器人的行進軌跡是確定的，環境特征標志之間相互獨立，特征標志的觀測信息僅與機器人的位姿有關。每個粒子采用N個卡爾曼濾波器分別估計地圖中N個特征的位置。對于FastSLAM算法的復雜度，如果采用K個粒子實現SLAM，總共有KN個卡爾曼濾波器，其復雜度為O（KN），利用一些算法（如樹型數據結構）進行優化，其復雜度可以進一步減小到O（KlogN）［25］。針對數據關聯錯誤，通過減小該粒子的權重來降低關聯錯誤對定位的影響［34］。FastSLAM方法的另一個優點是相比較于卡爾曼濾波定位方法，可以較好地解決機器人的非線性和非高斯運動問題。

以PF為理論基礎的FastSLAM算法，FastSLAM1．0和FastSLAM2．0有2個版本。FastsLAM1．0用粒子濾波器估計移動機器人位姿，用EKF估計環境特征。但其直接把SLAM過程模型作為采樣粒子重要性函數，從重要性函數抽取的樣本不能準確表達真實的后驗概率密度函數，當環境觀測值噪聲較小時，易造成嚴重的樣本退化問題和定位精度下降。FatSLAM2．0用EKF遞歸估計機器人位姿，構建融入機器人前期位姿信息的高斯分布函數為重要函數，緩解了樣本退化問題，提高了算法的精度。針對測距式傳感器，如激光雷達，影響粒子濾波器性能主要因素是建議分布的選擇和選擇性采樣。由于激光掃描儀的精度導致了峰值很高的似然函數，與大部分粒子濾波器選用里程計運動模型p（st｜st－1，ut－1）為建議分布不同，其選用高斯建議分布。這樣既考慮了最近觀測數據，也為高效采樣提供了可能，其結果比用里程計運動模型更具有確定性［3］。在重采樣過程中，低權值粒子被高權值粒子代替，這有可能刪除較好的粒子。在構建圖過程中，尤其在嵌套環路環境中，外層環路構建圖中需要的粒子并不一定是內層環路高權值的粒子。文獻［35］介紹了一種衡量有效粒子數的方法來評價當前粒子集能否表征后驗估計，只有在需要時重采樣才被執行，降低了較好粒子被替換的幾率。文獻［36］通過迭代卡爾曼濾波方法融入新的觀測值，用復制樣本與剔除樣本的線性組合降低樣本退化及樣本貧化。

綜上所述，FastSLAM算法獲取建議分布函數與估計環境特征位置依然是基于EKF理論，同樣存在樣本退化問題。因此，FastSLAM算法發展趨勢主要從以下2方面考慮：

1）改進機器人位姿路徑評估的粒子濾波。改進建議分布使其近似真實分布；改進重采樣策略；改進自適應機制，如自適應粒子數目、自適應重采樣技術及自適應運動模型。

2）改進環境特征評估的EKF。采用混合卡爾曼濾波器、UT變換的無跡卡爾曼濾波和無跡粒子濾波等方法提高計算的有效性。

3．3 基于矩陣奇異值分解（SVD）的SLAM方法

矩陣的分解因式是原矩陣特殊存在形式，能明顯反映出原矩陣的某些特征，從而為系統分析提供有效的計算方法和理論分析根據。矩陣SVD是一種應用比較廣泛的分解形式。在基于卡爾曼濾波定位算法中，協方差矩陣對舍入誤差較敏感，特別是高維的復雜系統，在迭代過程中經常出現矩陣病態問題，導致協方差矩陣失去對稱性和正定性，從而導致算法失效。文獻［37?38］通過協方差矩陣迭代分解計算，避免了協方差陣的求逆運算，減少了計算量，提高了算法的穩定性。文獻［39］通過激光雷達獲得障礙物和方向距離信息，求取直線交點坐標作為路標，建立路標的相關矩陣，由直線、路標和相關矩陣構成局部地圖，通過匹配局部地圖與全局地圖找出最優的關聯匹配，利用SVD獲得路標在全局坐標系和局部坐標系下的關系，完成地圖的更新。文獻［40］將測距式SALM問題看成距離信息矩陣SVD的過程，通過把距離矩陣SVD得到包含有路標信息和機器人位姿的2個矩陣；通過線性回歸算法或機器學習算法得到路標信息和機器人位姿，較好解決了傳感器數據不同步和數據遺漏問題，其實質是在系統狀態空間搜索識別子空間，與其它定位算法相比，不需要線性化模型，具有計算量小、跟蹤性能好等優點。

文獻［39?40］將基于矩陣SVD的SLAM與傳統的基于概率“位置預測－觀測－測量－預測－匹配更新”過程比較，只依靠測距傳感器來完成機器人的SLAM問題，從理論上避免了運動模型的偏差和“綁架”問題。

表1列出了3種方法的優缺點及其改進算法。

表1 3種方法的優缺點及其改進算法Table 1 The characteristics of the three methods and the improved algorithm

4 結論與展望

目前，有關移動機器人SLAM研究成果很多，并逐步趨于成熟，使得智能移動機器人的工作環境從辦公環境向著未知、非結構化環境方面延伸。結合目前實際應用，未知環境中移動機器人的SLAM問題有待從算法效率、應用領域等方面進一步完善［50］。

1）作為目前移動機器人定位主流的概率算法，需要對系統和觀測模型中的噪聲做在線自適應評估，對在線實時執行的SLAM算法做深入的研究，實現對移動機器人位姿的有效評估；

2）引入智能化優化算法和多種非線性濾波器相結合的方法，雖然目前已有一些這方面的研究成果，但仍有很大的研究空間；

3）研究粒子濾波中粒子數目與濾波器收斂速度的關系，針對如何克服粒子退化和保持粒子多樣性問題，研究自適應重采樣策略及提高粒子多樣性修復能力的方法，研究考慮了測距傳感器精度的粒子建議分布；

4）如何更高效地將測距傳感器與其他異質傳感器信息進行策略級的高級融合；

5）為使機器人在較短的時間內能夠感知的范圍盡可能大，進而提高SLAM地圖創建的效率，應在探索規劃方面展開研究；

6）考慮二維動態環境和三維動態環境下機器人SLAM問題；

7）對于多機協作SLAM技術提高地圖創建的準確性和魯棒性，急需解決自定位多機協作模式、系統控制結構、局部子地圖融為全局地圖的融合算法及多機分布式多傳感器間信息融合等問題。

總體而言，在未來的工作中，將在現有工作基礎上，重點需要在信息融合、多機協作系統、室外動態環境的三維實時重建算法等方面開展進一步的研究。

［1］WANG Heng，HUANG Shoudong，KHOSOUSSI K，et al．Dimensionality reduction for point feature SLAM problems with spherical covariance matrices［J］．Automatica，2015，51：149?157．

［2］VALIENTE D，GIL A，FERNáNDEZ L，et al．A compari?son of EKF and SGD applied to a view?based SLAM ap?proach with omnidirectional images［J］．Robotics and Auton?omous Systems，2014，62（2）：108?229．

［3］STACHNISS C．機器人地圖創建與環境探索［M］．陳白帆，劉麗玨，譯，北京：國防工業出版社，2013：75．

［4］程華彬，張穎超．基于超聲波傳感器的移動機器人定位研究［J］．傳感器與微系統，2013，32（4）：58?60，64． CHENG Huabin，ZHANG Yingchao．Research on localiza?tion of mobile robot based on ultrasonic wave sensor［J］．Transducer and Microsystem Technologies，2013，32（4）：58?60，64．

［5］韓崢，劉華平，黃文炳，等．基于Kinect的機械臂目標抓取［J］．智能系統學報，2013，8（2）：1?8．HAN Zheng，LIU Huaping，HUANG Wenbing，et al．Ki?nect?based object grasping by manipulator［J］．CAAI Trans?actions on Intelligent System，2013，8（2）：1?8．

［6］HWANG S Y，SONG J B．Monocular vision?based global lo?calization using position and orientation of ceiling features［C］／／IEEE International Conference on Robotics and Auto?mation（ICRA）．Karlsruhe，Germany，2013：3770?3775．

［7］WURM K M，STACHNISS C，GRISETTI G．Bridging the gap between feature?and grid?based SLAM［J］．Robotics and Autonomous Systems，2010，58（2）：140?148．

［8］CHOI H，KIM D Y，HWANG J P，et al．Efficient simulta?neous localization and mapping based on ceiling?view：ceil?ing boundary feature map approach［J］．Advanced Robotics，2012，26（5?6）：653?671．

［9］HWANG S Y，SONG J B，KIM M S．Robust extraction of arbitrary?shaped features in ceiling for upward?looking cam?era?based SLAM［C］／／Proceedings of the 18th IFAC World Congress．Milano，Italy，2011：8165?8170．

［10］ZHANG S，ADAMS M，TANG F，et al．Geometrical fea?ture extraction using 2D range scanner［C］／／The Fourth International Conference on Control and Automation．Mont?real，Canada，2003：901?905．

［11］STURM J，KONOLIGE K，STACHNISS C，et al．Vision?based detection for learning articulation models of cabinet doors and drawers in household environments［C］／／IEEE InternationalConferenceonRoboticsandAutomation（ICRA）．Anchorage，USA，2010：362?368．

［12］WU Zhe，KONG Qinjie，LIU Jiapeng，et al．A rectangle detection method for real?time extraction of large panel edge［C］／／The 6th International Conference on Image and Graphics（ICIG）．Hefei，China，2011：382?387．

［13］De La PUENTE P，RODRíGUEZ?L D，VALERO A，et al．3D feature based mapping towards mobile robots’enhanced performance in rescue missions［C］／／IEEE／RSJ Interna?tionalConferenceonIntelligentRobotsandSystems（IROS）．St Louis，USA，2009：1138?1143．

［14］KHAN S，DOMETIOS A，VERGINIS C，et al．RMAP：a rectangular cuboid approximation framework for 3D environ?ment mapping［J］．Autonomous Robots，2014，37（3）：261?277．

［15］NGUYEN V，MARTINRLLI A，TOMATIS N，et al．A comparison of line extraction algorithms using 2D range da?ta for indoor mobile robotics［J］．Autonomous Robots，2007，23（2）：97?111．

［16］滿增光，葉文華，肖海寧，等．從激光掃描數據中提取角點特征的方法［J］．南京航空航天大學學報，2012，44（3）：379?383．MAN Zengguang，YE Wenhua，XIAO Haining，et al．Method for corner feature extraction from laser scan data［J］．Journal of Nanjing University of Aeronautics＆Astro?nautics，2012，44（3）：379?383．

［17］徐君，張國良，王俊龍．一種基于激光傳感器的自適應直線提取算法［J］．計算機工程與應用，2013，49（2）：43?47．XU Jun，ZHANG Guoliang，WANG Junlong．Self?adaption segmentation algorithm for line extraction based on laser sensor［J］．Computer Engineering and Applications，2013，49（2）：43?47．

［18］于金霞，蔡自興，段琢華．基于激光雷達的環境特征提取方法研究［J］．計算機測量與控制，2007，15（11）：1550?1552．YU Jinxia，CAI Zixing，DUAN Zhuohua．Research on en?vironmental features extraction with laser scanner［J］．Com?puter Measurement＆Control，2007，15（11）：1550?1552．

［19］LU Feng，MILIOS E．Globally consistent range scan align?ment for environment mapping［J］．Autonomous Robots，1997，4（4）：333?349．

［20］王璐，蔡自興．未知環境中移動機器人并發建圖與定位（CML）的研究進展［J］．機器人，2004，24（4）：380?384．WANG Lu，CAI Zixing．Progress of CML for mobile robots in unknown environments［J］．Robot，2004，24（4）：380?384．

［21］強敏利，張萬緒．IEKF濾波在移動機器人定位中的應用［J］．電子技術應用，2013，39（2）：74?77．QIANG Minli，ZHANG Wanxu．Application of iterated ex?tended Kalman filtering in mobile robot localization［J］．Application of Electronic Technique，2013，39（2）：74?77．

［22］王曉娟，王宣銀．基于模糊卡爾曼濾波的移動機器人定位研究［J］．計算機工程與應用，2011，47（2）：204?206，216．WANG Xiaojuan，WANG Xuanyin．Research on mobile ro?bot localization based on fuzzy Kalman filtering［J］．Com?puter Engineering and Applications，2011，47（2）：204?206，216．

［23］鄒衛軍，薄煜明．差分線性化EKF濾波方法研究［J］．計算機工程與應用，2009，45（9）：64?66．ZOU Weijun，BO Yuming．Research of EKF based on dif?ferential linearization［J］．Computer Engineering and Appli?cations，2009，45（9）：64?66．

［24］BERGER C．Weak constraints network optimiser［C］／／Pro?ceedings of the IEEE International Conference on Robotics and Automation（ICRA）．Saint Paul，USA，2012：1270?1277．

［25］SCHLEICHER D，BERGASA L M，OCA?A M，et al．Re? al?time hierarchical stereo Visual SLAM in large?scale envi?ronments［J］．Robotics and Autonomous Systems，2010，58（8）：991?1002．

［26］IDRIS M Y I，AROF H，NOOR N M，et al．A co?proces?sor design to accelerate sequential monocular SLAM EKF process［J］．Measurement，2012，45（8）：2141?2152．

［27］LEONARD J J，DURRANT?WHYTE H F，COX I J．Dy?namic map building for an autonomous mobile robot［J］．The International Journal of Robotics Research，1992，11（4）：286?298．

［28］LEONARD J J，JACOB H，FEDER S．A computationally efficient method for large?scale concurrent mapping and lo?calization［C］／／Proceedings of the Ninth International Symposium on Robotics Research．Snowbird，Utah，USA，1999：169?176．

［29］PAGAC D，NEBOT E M，DURRANT?WHYTE H．An evi?dential approach to map?building for autonomous vehicles［J］．IEEE Transactions on Robotics and Automation，1998，14（4）：623?629．

［30］CADENA C，NEIRA J．SLAM in O（logn）with the com?bined Kalman?information filter［J］．Robotics and Autono?mous Systems，2010，58（11）：1207?1219．

［31］MURPHY K P．Bayesian map learning in dynamic environ?ments［C］／／Proceedings of the Conference on Neural Infor?mation Processing System（NIPS）．Denver，USA，1999：1015?1021．

［32］宋宇，李慶玲，康軼非，等．平方根容積Rao－Blackwil?lised粒子濾波SLAM算法［J］．自動化學報，2014，40（2）：357?367．SONG Yu，LI Qingling，KANG Yifei，et al．SLAM with square?root cubature Rao?Blackwillised particle filter［J］．Acta Automatica Sinica，2014，40（2）：357?367．

［33］MONTEMERLO M，THRUN S．Simultaneous localization andmappingwithunknowndataassociationusing FastSLAM［C］／／IEEE International Conference on Robot?ics and Automation．Taipei，China，2003：1985?1991．

［34］康軼非，宋永端，宋宇，等．不依賴里程計的機器人定位與地圖構建［J］．浙江大學學報：工學版，2014，48（3）：414?422．KANG Yifei，SONG Yongduan，SONG Yu，et al．Simulta?neous localization and mapping without relying on odometer［J］．Journal of Zhejiang University：Engineering Science，2014，48（3）：414?422．

［35］LIU J S．Metropolized independent sampling with compari?sons to rejection sampling and importance sampling［J］．Statistics and Computing，1996，6（2）：113?119．

［36］王宏健，王晶，劉振業．基于迭代擴展Kalman濾波建議分布和線性優化重采樣的快速同步定位與構圖［J］．電子與信息學報，2014，36（2）：318?324．WANG Hongjian，WANG Jing，LIU Zhenye．Fast simulta?neous localization and mapping based on iterative extended Kalman filter proposal distribution and linear optimization resampling［J］．Journal of Electronics＆Information Tech?nology，2014，36（2）：318?324．

［37］張友民，焦凌云，陳洪亮，等．基于奇異值分解的固定區間平滑新方法［J］．控制理論與應用，1997，14（4）：579?583．ZHANG Youmin，JIAO Lingyun，CHEN Hongliang，et al．A new fixed?interval smoothing algorithm based on singular value decomposition［J］．Control Theory＆Applications，1997，14（4）：579?583．

［38］曲從善，許化龍，譚營．一種基于奇異值分解的非線性濾波新算法［J］．系統仿真學報，2009，21（9）：2650?2653．QU Congshan，XU Hualong，TAN Ying．New nonlinear fil?tering algorithm based on SVD［J］．Journal of System Simu?lation，2009，21（9）：2650?2653．

［39］丁帥華，陳雄，韓建達．基于局部子圖匹配的SLAM方法［J］．機器人，2009，31（4）：296?303．DING Shuaihua，CHEN Xiong，HAN Jianda．A new solu?tion to SLAM problem based on local map matching［J］．Robot，2009，31（4）：296?303．

［40］BOOTS B，GORDON G J．A spectral learning approach to range?only SLAM［C］／／Proceedings of the 30th Interna?tional Conference on Machine Learning（ICML）．Atlanta，Georgia，USA，2013：19?26．

［41］VAN DER MERWE R，WAN E A．The square?root un?scented Kalman filter for state and parameter?estimation［C］／／2001 IEEE International Conference on Acoustics，Speech and Signal Processing．Salt Lake，USA，2001：3461?3464．

［42］BHARANI CHANDRA K P，GU D W，POSTLETHWAITE I．Cubature Kalman filter based localization and mapping［C］／／18th IFAC World Congress．Milano，Italy，2011：2121?2125．

［43］康軼非，宋永端，宋宇，等．平方根容積卡爾曼濾波在移動機器人SLAM中的應用［J］．機器人，2013，35（2）：186?193．KANG Yifei，SONG Yongduan，SONG Yu，et al．Square?root cubature Kalman filter and its application to SLAM of an mobile robot［J］．Robot，2013，35（2）：186?193．

［44］KIM C，SAKTHIVEL R，CHUNG W K．Unscented Fast?SLAM：a robust and efficient solution to the SLAM problem［J］．IEEE Transactions on Robotics，2008，24（4）：808?820．

［45］KIM C，KIM H K，CHUNG W K．Exactly Rao?Black?wellized unscented particle filters for SLAM［C］／／2011 IEEE International Conference on Robotics and Automa?tion．Shanghai，China，2011：3589?3594．

［46］KURT?YAVUZ Z，YAVUZ S．A comparison of EKF，UKF，FastSLAM2．0，and UKF?based FastSLAM algo?rithms［C］／／The 16th International Conference on Intelli?gent Engineering Systems．Lisbon，Portugal，2012：37?43．

［47］張國良，湯文俊，敬斌，等．輔助粒子濾波算法改進的UFastSLAM算法［J］．哈爾濱工業大學學報，2012，44（11）：123?128．ZHANG Guoliang，TANG Wenjun，JING Bin，et al．Im?proved UFastSLAM algorithm based on auxiliary particle fil?ter［J］．Journal of Harbin Institute of Technology，2012，44（11）：123?128．

［48］SONG Y，LI Q L，KANG Y F，et al．CFastSLAM：a new Jacobian free solution to SLAM problem［C］／／IEEE Inter?national Conference on Robotics and Automation（ICRA）．Saint Paul，USA，2012：3063?3068．

［49］穆靜，蔡遠利，張俊敏．容積粒子濾波算法及其應用［J］．西安交通大學學報，2011，45（8）：13?17．MU Jing，CAI Yuanli，ZHANG Junmin．Cubature particle filter and its application［J］．Journal of Xi’an Jiaotong Uni?versity，2011，45（8）：13?17．

［50］于金霞，王璐，蔡自興．未知環境中移動機器人自定位技術［M］．北京：電子工業出版社，2011．

A survey of range?only SLAM for mobile robots

LIU Jianhua1，2，LIU Huaping3，YANG Jianguo1，GAO Meng2，SUN Fuchun3

（1．College of Mechanical Engineering，Donghua University，Shanghai 201620，China；2．College of Electrical and Electronic Engi?neering，Shijiazhuang Tiedao University，Shijiazhuang 050043，China；3．Key Laboratory of Intelligent Technology and Systems，Tsin?ghua University，Beijing 100084，China）

This paper details the research on simultaneous localization and mapping（SLAM）for mobile robots，currently a hot spot in robotics．The essence of range?only SLAM is online extraction and representation of range in?formation．The basic idea，key technology，and solution for range?only SLAM are discussed；then a performance comparison of the fundamental methods is made．Three of the most commonly used methods：Kalman filter，particle filter and singular value decomposition are discussed in detail，emphasizing the realization process and some practi?cal problems．Further research，on the problems，improvements，and development prospects for range?only SLAM，is discussed．

mobile robot；range?only；Kalman filter；particle filter；singular value decomposition；simultaneous lo?calization and mapping（SLAM）

劉建華，男，1974年生，副教授，主要研究方向為計算機控制與仿真、機器人路徑規劃、機器人定位。參與并完成省部級項目6項。發表學術論文30余篇，其中被EI檢索7篇，ISTP收錄6篇。

劉華平，男，1976年生，副教授，博士，主要研究方向為智能控制與機器人、視頻跟蹤與檢測、智能交通等。主持國家自然科學基金2項，發表學術論文50余篇，其中被SCI、EI收錄10余篇。

楊建國，男，1951年生，教授，博士生導師，主要研究方向為機電一體化、自動化。任中國自動化學會制造技術專業委員會委員，中國機械工程學會高級會員，教育部《數字化紡織服裝技術工程研究中心》常務副主任，上海市工程圖學會理事等。主持并完成國家自然基金項目2項，國家“863”計劃項目4項、國家技術創新項目1項及省部級科技攻關項目5項。獲得發明專利3項，發表學術論文60余篇，其中被EI、ISTP收錄10余篇。

TP24

A

1673?4785（2015）05?0655?08

10．11992／tis．201403017

http：／／www．cnki．net／kcms／detail／23．1538．tp．20150930．1556．018．html

劉建華，劉華平，楊建國，等．測距式傳感器同時定位與地圖創建綜述［J］．智能系統學報，2015，10（5）：655?662．

英文引用格式：LIU Jianhua，LIU Huaping，YANG Jianguo，et al．A survey of range?only SLAM for mobile robots［J］．CAAI Transactions on Intelligent Systems，2015，10（5）：655?662．

2014?03?05．

日期：2015?09?30．

國家高技術研究發展計劃資助項目（2007AA04Z232）；國家自然科學基金資助項目（61075027，91120011）；河北省自然科學基金資助項目（F2010001106，F2013210094）．

楊建國．E?mail：lfengju＠163．com．