SLAM:Google cartography演算法分析專題—-《real-time loop closure in 2D LIDAR SLAM》論文翻譯(四)

SLAM:Google cartography演算法分析專題—-《real-time loop closure in 2D LIDAR SLAM》論文翻譯(四)
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

摘要

行動式鐳射測距儀(也就是LIDAR)以及實時定位和繪圖(slam)都是比較有效的一種建立平面圖的方法。實時生成和繪製平面圖能很好的評估捕獲的資料的質量。因此建立一個在有限的資源下可接入的平臺是非常有必要的。這篇論文提供了一種在mapping 平臺後臺使用的方法來實現5cm解析度的實時繪圖和閉環檢驗。為了達到實時閉環檢測,我們使用了分支上界法來計算scan-to-map的匹配作為約束。


一、介紹

建立平面圖對於各種應用都是非常有用的。吧啦巴拉巴拉….(以上是一些簡單的關於這些技術的重要性的介紹。這部分不做翻譯,相信大家的水平也是可以理解的,因為我都理解了。嗯,就是這樣的)。但是需要說明的一點是:SLAM並不是這篇論文所主要的研究,這篇論文的contribution在於減少了計算量,提高了計算效率,對於大平面圖更加適用。


二、相關工作

這裡涉及到幾種的匹配演算法:


  1. scan-to-scan matching:會累計誤差,最終誤差會很大
  2. scan-to-map matching:減少了誤差的累計(本篇論文使用方法)
  3. pixel-accurate scan matching:最後有說這個演算法在後臺用於將scan點集和最近的submap進行匹配,生成loop closing的約束條件。

解決區域性誤差的累計有兩種方法:一種是粒子濾波法,一個基於圖的SLAM方法(graph-based)。這篇文章使用的是後者。講一下關於graph-based的吧。
graph-based是一種工作於基於位姿和特徵的集合的方法。圖中的邊表示從觀察結果中生成的約束,節點表示的是位姿和特徵。對於優化由約束引進的誤差有很多方法,比如文中的參考文獻11,12。對於室外繪圖的系統使用詳情見參考論文13。
對於第二部分也就不多解釋了,接下來重點來了!第三,四,五部分是這篇論文的核心,基本的理論知識闡述!非常重要,重要到我都沒看明白就只能先翻譯一下了。


三、系統概述

google的cartographer提供了一種室內實時繪圖的解決方法,這種方法是基於鐳射雷達的。繪製的是2D影象,解析度是5cm。鐳射資料scans會以最佳的位置插入到submap中,這個最佳的位置假設在一段時間內是很準確的。scan matching必須是和它相對應的submap進行匹配,所以它只和最近的scan點集有關。(??這部分有些疑問,是這麼理解嗎?還是說scan matching必須在submap之前進行匹配?)對於位姿的估計誤差會在全域性的幀當中積累起來。
綜合硬體等條件,這篇論文使用的是pose optimization來處理誤差累計(如何使用pose optimization實現累計誤差的優化?????接下來講的是關於位姿優化演算法??)當一個子圖構建完成之後,不在有其它的scan插入這個子圖當中,這個已有的子圖會用來作為loop closing的scan matching。所有子圖和scan點集都會被用來進行loop closure。如果他們( 他們指的是submap和scan,還是scan和scan,還是submap和submap???)離的足夠近的話,那麼就會嘗試在子圖中找到相應的scan。

當一個新的laser scan加入到地圖中時,如果該laser scan的估計位姿與地圖中某個submap的某個laser scan的位姿比較接近的話,那麼通過某種 scan match策略就會找到該閉環

以上是對泡泡機器人公眾號的文章引用的一段話。泡泡機器人文章
如果在當前估計位置的視窗範圍內找到一個足夠好的匹配結果,那麼這個匹配結果就會被用來作為優化問題的閉環檢測約束條件。(匹配的結果?指的是什麼?也就是需要儲存什麼?)每隔幾秒就進行閉環檢測,按照經驗來說,就是一個位置點被重複訪問之後就算達到閉環了(這個重複訪問是如何判斷的,兩個位姿的距離足夠小??)這樣的判斷要求閉環檢測必須在新的點被加入到submap中之前完成。如果不是,可能會導致失敗.為了達到這樣的目的(之前提高的必選檢測在前的目的??),通過使用分支上界法以及對於每個完成的submap有對應的幾個預處理的網格(several precomputed grids per finished submap).


四、區域性二維的實時定位和繪圖

這個系統實現2DSLAM結合了區域性的和全域性的方法,區域性和全域性的方法都對LIDAR觀測到的位置進行了優化。位置的表示位置表示
這個位置表示包括(x,y)座標的轉化,以及角度的旋轉,實際上就是對scan點集的優化。平臺採用的是IMU測量方向,然後將其對映到2D平面上。
在這篇論文的區域性方法中,每個連續的點集被拿來和整個地圖的一部分進行匹配,就是和submap進行匹配。使用一種非線性的優化方法將submap和scan點集聯絡起來,這也是scan matching的過程。區域性方法積累的誤差在之後的第五部分的全域性方法去掉。


1、scans

submap的構建是不斷的校準點集和submap的座標。文中將點集表示成H=scan點集表示,這個scan點集的在submap點集的位置被表示成scan點集的符號表示,這個位置轉為submap的位置方法如下:
轉換方式


2、submaps

一個submap是由連續的幾個scans建立的,這些submap採用的是概率網格M :概率網格表示概率網格2
這個代表著離散網格點中概率值(這個部分真沒懂是怎麼樣的對映關係)。這個值可以作為表示這個網格是否為障礙物的概率。對於每個網格點,論文中都定義了一個相應的畫素,這個畫素包含了所有靠近這個網格點的scan points。
無論什麼時候一個scan點集被插入到這個概率網格中,一個包含網格點的hits集合以及一個miss集合都會被重新計算。對於每一次的hit,我們將這個最近的網格點加入hit集合,對於每一次的miss,我們將每個畫素關聯的網格插入這個miss集合,對於已經在hit集合中的網格點不需要插入。
對於每一個之前沒有觀察到的網格點都會根據他們所在集合是hit還是miss賦予一個概率值概率表示
如果一個網格點已經被觀察到了,我們將會更新這個概率值。通過以下的方式(hit的修改):
概率更新公式
對於miss的網格點的修改也是同樣的。貼出論文中的圖:
scan命中
灰色的網格代表的是一次scan點集的範圍,黑色的點表示hit(是障礙物的)的網格。


3、Ceres scan matching

在將一個scan點集插入submap中之前,這個scan點集的位置必須使用Ceres-based的scan matcher的方法進行優化(這個優化是相對於submap的位置)。這個scan matcher目的是為了找到一個點集位置,這個點集的位置在submap中的概率最大,將其作為一個非線性最小二乘問題。如下:
ceres scan match

公式中的各個符號解釋自己看啦!對於M這個函式,這篇論文中使用的是雙三次插值法(bicubic interpolation)。這個函式的數學優化往往比網格解析度優化有更高的準確性。因為這是一個區域性的優化,所以一個好的初值很重要。IMU被用來測量scan match中的角度旋轉引數theta。一個高概率的scan matcher 或者一個高的pixel-accurate scan matching方法會被用來彌補IMU不能使用的情況,儘管複雜度很高。


五、閉環的實現

因為一個submap是有少數的幾個連續scan點集生成的,所以誤差很小。這篇論文中優化所有點集和submap位置的方法使用的是Sparse Pose Adjustment(參見原論文的[2])。一個scan點集唄插入submap中的這個相對位置會被儲存下來,用於之後的閉環優化。除了這些位置資訊,還有的包含scan點集和submap,而且這個submap不再變化的時候,都會被用來作為閉環檢測。一個scan matcher一直會在後臺不斷的執行,當一個好的scan match被找到之後,這個相應的位置也會被加入到優化問題中。


1、優化問題

閉環的優化,就像scan matching 一樣,也被表示成非線性最小二乘問題。每隔幾秒,就會使用Ceres計算一個解決方法。計算方式如下:
優化問題
同樣,符號的表示我也不一一闡述了。自己看吧~
其實這個就是一個損失函式,比如Huber loss等等。使用損失函式的目的是減少加入到優化問題中的離群點對於系統的影響。


2、Branch-and-bound scan matching

對於優化的,pixel-accurate match還是非常感興趣的。這個匹配演算法公式如下:找到最佳的位置點
修改位置點
,其中的W表示的是一個視窗大小,M是之前M函式一個延伸。這裡的含義以及包括接下來的演算法1的含義,在我理解看來就是在一個新的scan點集的周圍畫一個圓(視窗),然後不斷的修改x,y,以及角度來找一個最佳的位置。這個位置的修改不能超過一定的範圍。這個範圍是點集的最大範圍。同時角度變化step也設定如下:
引數設定
以上的這些引數都是演算法中涉及的。
其實呢,個人覺得這個演算法的思想就是不斷的在視窗內找到這個最佳位置。
但是這篇論文呢,並沒有採用這種方法(真的要注意啦!只是介紹了這種方法,但是並木有采用)採用的是分支上界法來計算這個最佳位置。這個演算法就是演算法2了。分支上界法就是每個分支代表一種可能。使用DFS找到最佳的那個位置即可。他和演算法1一樣都是解決的相同的問題。只不過這個節點的score是可能的最大值而已。為了達到一個實際的演算法,需要分為以下幾步:節點選擇,分支,計算上限。對於這三步,論文中有具體講解。節點選擇採用的是DFS,對於分支演算法,採用的是演算法2。演算法3是將節點選擇和分支結合到一起之後的演算法。
對於計算上限的地方,採用的是提前處理的網格:預處理網格表示,預處理的每個網格有一個初始假設高度,能夠讓我們計算這個scan的score。至於接下來的計算過程。我就自動忽略了,因為實在是沒get到!淚崩~


實驗結果部分自動忽略了翻譯。嗯,可以自己去看。


總結

這篇論文闡述了一個2D的SLAM的系統,這個系統採用了閉環檢測的scan-to-submap matching,同時還有圖優化(graph optimization)。一個submap的建立是使用的是區域性的,基於網格的(grid-based)SLAM方法。在後臺,所有的點集與相近的submap的匹配使用的是pixel-accurate scan matching的方法,然後建立閉環檢測的約束。這個約束圖(基於submap和scan pose的)都會週期性的在後臺被更改。這個操作是採用GPU加速將已完成的submap和當前的submap進行結合。


以上,就是這篇文章的大概了。整個系統圖可以盜用一下作者jsgaobiao的部落格裡面的圖:
整個系統構建圖

上圖中對於scan與scan集合成submap採用的是grid-based 的SLAM方法。生成約束關係的scan和submap的匹配演算法採用的是pixel-accurate scan matching的方法。目前還沒看程式碼,不是很清楚這部分。

相關文章

程式語言 最新文章