同時定位與地圖構建
同時定位與地圖構建[1](英語:Simultaneous localization and mapping,簡稱SLAM),又稱同步定位與地圖創建[2],是機械人學中的一個概念:機械人從未知環境的未知地點出發,在運動過程中通過重複觀測到的地圖特徵(比如,牆角,柱子等)定位自身位置和姿態,再根據自身位置增量式的構建地圖,從而達到同時定位和地圖構建的目的。
歷史
有關於SLAM的一個開創性工作是以R.C. Smith和P. Cheeseman為代表,在1986年作出的對空間不確定性的估測的研究。[3][4]其他該領域的開拓工作由Hugh F. Durrant-Whyte (頁面存檔備份,存於互聯網檔案館)的研究團隊在1990年代初所作出。[5]
由Sebastian Thrun帶領的團隊設計出STANLEY自動駕駛車於2005年勝出了由美國國防高級研究計劃局(DARPA)發起的DARPA無人駕駛車大賽,其後在2007年再設計出另一自動駕駛車JUNIOR勝出了同樣由美國國防高級研究計劃局發起的城市無人駕駛車挑戰賽。當中的同步定位與地圖構建系統引起了全球廣泛注意,現在同步定位與地圖構建已被廣泛應用在機械人吸塵器,例如Neato Robotics的XV11,Google的自動駕駛汽車等。
操作性定義
這裏說的地圖,是用來在環境中定位,以及描述當前環境以便於規劃航線的一個概念;它通過記錄以某種形式的感知獲取的信息,用以和當前的感知結果相比較,以支撐對現實定位的評估。在定位評估方面,地圖提供的幫助程度,與感知的精度和質量成反相關。地圖通常反映了它被描繪出來的時刻的環境狀態,所以它並不一定反映它被使用的時刻的環境狀態。
在誤差和噪音條件下,定位和地圖構建技術上的複雜度不支持兩者同時獲得連續的解。SLAM是這樣一個概念:把兩方面的進程都捆綁在一個循環之中,以此支持雙方在各自進程中都求得連續解;不同進程中相互迭代的反饋對雙方的連續解有改進作用。
地圖構建,是研究如何把從一系列傳感器收集到的信息,集成到一個一致性的模型上的問題。它可以被描述為「第一核心問題」——「這個世界長什麼樣?」地圖構建的核心部分是環境的表達方式以及傳感器數據的解釋。
與之相比,定位,是在地圖上估測機械人的坐標和姿勢形態的問題;換而言之,機械人需要回答這裏的「第二核心問題」:「我在哪?」典型的解包含以下兩個方面:追蹤——通常機械人的初始位置已知;全局定位——通常只給出很少,甚至不給出有關於起始位置環境特徵的先驗信息。
所以,SLAM被定義為以下問題:在建立新地圖模型或者改進已知地圖的同時,在該地圖模型上定位機械人。實際上,這兩個核心問題如果分開解決,將毫無意義;必須同時求解。
在機械人能夠根據一系列觀測值回答「這個世界長什麼樣」之前,它需要知道的額外信息很多,比如以下:
技術上的問題
SLAM可以被看做是一個雞生蛋蛋生雞的問題:完美的定位需要用到一個無偏差的地圖;但這樣的地圖又需要精確的位置估測來描繪。這就是一個迭代數學問題解決策略的初始條件。作為對比,原子軌道模型可以被看做一個在不精確的觀測條件下說明足夠多的結果的經典方法。
再者,由於多個傳感器對機械人的相對運動的辨別存在固有的不確定性,上一節提到的兩個「核心問題」也不像看起來的那麼簡單。一般來說,由於技術環境中總會考慮噪聲,所以SLAM方法要考慮的不只是數學上的緊湊解,也包括與那些和結果相關的物理概念的相互作用。
如果在地圖構建的下一個迭代步驟中,測得的距離和方向有可預知的一系列不精確度——通常由傳感器有限的的精確度和外加的環境噪聲所引起,那麼附加到地圖上的所有特徵都將會含有相應的誤差。隨着時間的推移和運動的變化,定位和地圖構建的誤差累計增加,將會對地圖本身和機械人的定位、導航等能力的精度產生很大的扭曲。
有許多技術能補償這些誤差,比如那些能再現某些特徵過去的值的方法(也就是說,圖像匹配法或者環路閉合檢測法),或者對現有的地圖進行處理——以融合該特徵在不同時間的不同值。此外還有一些用於SLAM統計學的技術可起到作用,包括卡爾曼濾波、粒子濾波 (頁面存檔備份,存於互聯網檔案館)(實際上是一種蒙特卡羅方法)以及掃描匹配的數據範圍。
地圖構建
在機械人技術社區中,SLAM的地圖構建通常指的是建立與環境幾何一致的地圖。而一般算法中建立的拓撲地圖只反映了環境中的各點連接關係,並不能構建幾何一致的地圖。因此,這些拓撲算法不能被用於SLAM。
在實用中,SLAM通常要被剪裁至適應可獲得的資源,於是可以看出它的目標不是完美,而是操作實用性。已經發佈的SLAM方法已被應用於無人機、無人潛艇、行星探測車、最近大熱的家政機械人 (頁面存檔備份,存於互聯網檔案館)、甚至人體內部。[7]
學界大致都認為,SLAM問題的「正在得到解決」是過去十年間機械人研究領域的最重大成果之一。[8] 該領域中仍有許多有待解決的難題,比如圖像匹配和計算複雜度等方面的相關問題。
基於SLAM文獻的最新研究進展中,有一條值得注意,就是對SLAM的概率論基礎進行重新估測。這個充滿了冒險家特質的方法大意如下:通過引入隨機有限集的、多目標的貝葉斯濾波器,使得基於特徵的SLAM算法獲得卓越的性能,以此跳過對圖像匹配的依賴;但作為代價,測量中的假警報率和漏檢率都會被提升。[9] 這裏面的算法是基於概率假設密度濾波的方法來改進的。[10]
傳感
SLAM研究中經常使用許多不同型號的傳感器來獲得地圖數據。這些數據帶有統計獨立的誤差。[來源請求]這個統計獨立是解決度量偏差和檢測中的噪聲的強制需求。簡單來說,就是任何一個東西都很難測的準確。比如一根1米長的棍子,你第一次測量的時候可能是1.02米,第二次測量時1.05米,...。總之測量的時候多多少少都會有一些誤差在裏面,因此SLAM算法本身必須要有效的處理這些測量誤差。
這些傳感器可以是光學的,比如1D的(單波束)或者2D的(掃描)激光測距儀、3D Flash LIDAR、2D或3D聲吶傳感器以及一個或多個2D攝像頭。從2005年開始,使用可視化傳感器(攝像頭)對SLAM的研究(可視化SLAM)如火如荼地展開,因為從那時起攝像頭開始普及(比如說手機普遍帶有攝像頭)。[11]
新近的方法使用了准光學的無線測距法,同時把三角測距法等幾何方法應用於SLAM中,用以消除微弱無線信號對測量的影響。
一種為走路者設計的SLAM應用使用了一個裝在鞋頭的慣性測量單元作為主要傳感器,該設計依賴於走路者能自動規避牆體這一假設。這個名為FootSLAM的設計可被用於自動建立建築物的樓面佈置圖,從而方便建立該建築的室內定位系統。[12]
此外,通過聚眾收集多個用戶的手機信號強度與加速度數據,iFrame系統可以合成二維室內地圖。並且隨着用戶數的增加,來逐步加強地圖的精度。[13]
定位
傳感器的結果會作為定位算法的輸入。由幾何知識可知,對於n維的定位問題,任何傳感輸出必須包含至少一個多點定位和n+1個判別方程。為了算出結果,有關於在絕對或相對的循環和鏡像坐標系統下得到的結果的先驗知識也是必要的。
建模
以上結果對地圖構建的貢獻,可以在「2D建模並分別表示」或者在「3D建模並在2D上投影表示」中工作得一樣出色。作為建模的一部分,機械人本身的運動學特徵也要被考慮進去,用以提高在固有背景噪聲下的傳感精度。構建的動態模型需平衡不同傳感器、不同局部誤差模型給出來的貢獻值,並最終包含一個基於地圖本身的銳利的可視化描述,這包括機械人的位置和方向等雲概率信息。地圖構建就是這樣一個動態模型的最終運算結果。
參見
- 卡爾曼濾波
- 蒙特卡洛定位法
- 粒子濾波
- Stanley:DARPA地面無人車挑戰賽冠軍,一輛成功使用了SLAM技術的無人車
- 深度圖像的圖像配准
- 移動機械人編程工具包項目:一組開源、跨平台的SLAM資料庫。
- Multi Autonomous Ground-國際機械人競賽:一項160萬美元的國際競賽,要求參賽者讓多台無人車合作給一大片區域繪製地圖。
參考資料
- ^ 田野; 陳宏巍; 王法勝; 陳興文. 室内移动机器人的SLAM算法综述. 計算機科學. 2021, 48 (09).
- ^ 趙洋; 劉國良; 田國會; 羅勇; 王梓任; 張威; 李軍偉. 基于深度学习的视觉SLAM综述. 機械人. 2017, 39 (06).
- ^ Smith, R.C.; Cheeseman, P. On the Representation and Estimation of Spatial Uncertainty (PDF). The International Journal of Robotics Research. 1986, 5 (4): 56–68 [2008-04-08]. doi:10.1177/027836498600500404. (原始內容存檔 (PDF)於2020-09-28).
- ^ Smith, R.C.; Self, M.;Cheeseman, P. Estimating Uncertain Spatial Relationships in Robotics (PDF). Proceedings of the Second Annual Conference on Uncertainty in Artificial Intelligence. UAI '86. University of Pennsylvania, Philadelphia, PA, USA: Elsevier: 435–461. 1986 [2013-03-12]. (原始內容 (PDF)存檔於2010-07-02).
- ^ Leonard, J.J.; Durrant-whyte, H.F. Simultaneous map building and localization for an autonomous mobile robot. Intelligent Robots and Systems' 91.'Intelligence for Mechanical Systems, Proceedings IROS'91. IEEE/RSJ International Workshop on. 1991: 1442–1447 [2008-04-08]. doi:10.1109/IROS.1991.174711.
- ^ Definition according to OpenSLAM.org, a platform for SLAM researchers. [2013-03-12]. (原始內容存檔於2018-04-16).
- ^ Mountney, P.; Stoyanov, D. Davison, A. Yang, G-Z. Simultaneous Stereoscope Localization and Soft-Tissue Mapping for Minimal Invasive Surgery (PDF). MICCAI. 2006, 1: 347–354 [2010-07-30]. doi:10.1007/11866565_43. (原始內容存檔 (PDF)於2017-01-12).
- ^ Durrant-Whyte, H.; Bailey, T. Simultaneous Localization and Mapping (SLAM): Part I The Essential Algorithms (PDF). Robotics and Automation Magazine. 2006, 13 (2): 99–110 [2008-04-08]. doi:10.1109/MRA.2006.1638022. (原始內容存檔 (PDF)於2007-06-12).
- ^ J. Mullane, B.-N. Vo, M. D. Adams, and B.-T. Vo,. A random-finite-set approach to Bayesian SLAM, (PDF). IEEE Transactions on Robotics. 2011, 27 (2): 268–282 [2013-03-12]. doi:10.1109/TRO.2010.2101370. (原始內容 (PDF)存檔於2013-05-16).
- ^ R. P. S. Mahler,. Statistical Multisource-Multitarget Information Fusion.. Artech House,. 2007.
- ^ Karlsson, N.; Di Bernardo, E.;Ostrowski, J;Goncalves, L.;Pirjanian, P.;Munich, M. The vSLAM Algorithm for Robust Localization and Mapping. Int. Conf. on Robotics and Automation (ICRA). 2005.
- ^ Robertson, P.; Angermann, M.;Krach B. Simultaneous Localization and Mapping for Pedestrians using only Foot-Mounted Inertial Sensors (PDF). Ubicomp 2009. Orlando, Florida, USA: ACM. 2009 [2013-03-12]. doi:10.1145/1620545.1620560. (原始內容 (PDF)存檔於2010-08-16).
- ^ Qiu, C.; Mutka, M. iFrame: Dynamic indoor map construction through automatic mobile sensing. PerCom 2016. Sydney, Australia: IEEE. 2016 [2018-01-30]. doi:10.1109/PERCOM.2016.7456500. (原始內容存檔於2018-01-30).
外部連結
- 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.