機器人的SLAM和導航系統(tǒng)技術(shù)分析

這種地圖看起來和人們所認知的地圖沒什么區(qū)別，它最早由NASA的Alberto Elfes在1989年提出，在火星探測車上就用到過，其本質(zhì)是一張位圖圖片，但其中每個“像素”則表示了實際環(huán)境中存在障礙物的概率分布。

一般來說，采用激光雷達、深度攝像頭、超聲波傳感器等可以直接測量距離數(shù)據(jù)的傳感器進行SLAM時，可以使用該地圖。這種地圖也可以通過距離測量傳感器、超聲波（早期）、激光雷達（現(xiàn)在）繪制出來。

2.特征點地圖

特征點地圖，是用有關(guān)的幾何特征（如點、直線、面）表示環(huán)境，常見于vSLAM（視覺SLAM）技術(shù)中。

相比柵格地圖，這種地圖看起來就不那么直觀了。它一般通過如GPS、UWB以及攝像頭配合稀疏方式的vSLAM算法產(chǎn)生，優(yōu)點是相對數(shù)據(jù)存儲量和運算量比較小，多見于最早的SLAM算法中。

3.直接表征法

直接表征法中，省去了特征或柵格表示這一中間環(huán)節(jié)，直接用傳感器讀取的數(shù)據(jù)來構(gòu)造機器人的位姿空間。

上圖就是直接記錄了屋子內(nèi)天花板畫面的圖像地圖。這種方法就像衛(wèi)星地圖一樣，直接將傳感器原始數(shù)據(jù)通過簡單處理拼接形成地圖，相對來說更加直觀。

4.拓撲地圖

拓撲地圖，是一種相對更加抽象的地圖形式，它把室內(nèi)環(huán)境表示為帶結(jié)點和相關(guān)連接線的拓撲結(jié)構(gòu)圖，其中結(jié)點表示環(huán)境中的重要位置點（拐角、門、電梯、樓梯等），邊表示結(jié)點間的連接關(guān)系，如走廊等。

這種方法只記錄所在環(huán)境拓撲鏈接關(guān)系，這類地圖一般是由前幾類地圖通過相關(guān)算法提取得到。

比如掃地機器人要進行房間清掃的時候，就會建立這樣的拓撲地圖：

5.小結(jié)

在機器人技術(shù)中，SLAM的地圖構(gòu)建通常指的是建立與環(huán)境幾何一致的地圖。

一般算法中建立的拓撲地圖只反映了環(huán)境中的各點連接關(guān)系，并不能構(gòu)建幾何一致的地圖，因此，這些拓撲算法不能被用于SLAM。

直接表征法類似衛(wèi)星地圖，它是直接使用傳感器（一般是圖像傳感器）構(gòu)建得到。這種方法的信息冗余度最大，對于數(shù)據(jù)存儲是很大的挑戰(zhàn)，同時，機器人要從中提取出有用的數(shù)據(jù)也要耗費一番周折，因此在實際應用中很少使用。

特征點地圖又是另一個極端，雖然數(shù)據(jù)量少，但是它往往不能反應所在環(huán)境的一些必須的信息，比如環(huán)境中障礙物的位置。vSLAM技術(shù)中，多采用這種地圖來解決機器人定位問題。想讓機器人進行自主避障和路徑規(guī)劃，還需要額外配置距離傳感器，如激光雷達、超聲波來完成。

柵格地圖，或者Occupancy Map（占據(jù)地圖）恰好介于其中，一方面它能表示空間環(huán)境中的很多特征，機器人可以用它來進行路徑規(guī)劃，另一方面，它又不直接記錄傳感器的原始數(shù)據(jù)，相對實現(xiàn)了空間和時間消耗的最優(yōu)。因此，柵格地圖是目前機器人所廣泛應用的地圖存儲方式。

二、定位及傳感器選擇

當你打開手機中的導航軟件，在選擇前往目的地的最佳路線之前，首先要做的動作是什么呢？沒錯，就是定位。我們要先知道自己在地圖中的位置，才可以進行后續(xù)的路徑規(guī)劃。

在機器人實時定位問題中，由于通過機器人運動估計得到的機器人位置信息通常具有較大的誤差，我們還需要使用測距單元得到的周圍環(huán)境信息更正機器人的位置。

目前，常見的測距單元包括激光測距、超聲波測距以及圖像測距三種。其中，憑借激光良好的指向性和高度聚焦性，激光雷達已經(jīng)成為移動機器人的核心傳感器，同時它也是目前最可靠、最穩(wěn)定的定位技術(shù)。

自1988年被提出以來，SLAM的理論研究發(fā)展十分迅速。在實際應用時，除配備激光雷達外，還需要機器人具有IMU（慣性測量單元）、里程計來為激光雷達提供輔助數(shù)據(jù)，這一過程的運算消耗是巨大的，傳統(tǒng)上需要PC級別的處理器，這也成為限制SLAM廣泛應用的瓶頸之一。

三、傳感器數(shù)據(jù)預處理

這是一個完整的SLAM和導航系統(tǒng)的主要架構(gòu)圖：

其中，SLAM核心過程包括3個步驟，第一步稱為預處理。我們知道，激光雷達和其他雷達設(shè)備一樣，某一個時刻只能獲取它所在位置的環(huán)境信息。

這就是我們所說的點云，它只能反映機器人所在環(huán)境中的一個部分。第一步預處理就是對激光雷達原始數(shù)據(jù)進行優(yōu)化，剔除一些有問題的數(shù)據(jù)，或者進行濾波。

四、匹配

第二步是匹配，也就是說把當前這一個局部環(huán)境的點云數(shù)據(jù)在已經(jīng)建立地圖上尋找到對應的位置，這個步驟非常關(guān)鍵。

這個是ICP的點云匹配算法，用于實現(xiàn)匹配。說這個過程關(guān)鍵，就是因為它的好壞，直接影響了SLAM構(gòu)建地圖的精度。這個過程和我們玩拼圖游戲有點類似，就是在已經(jīng)拼好的畫面中找到相似之處，確定新的一個拼圖該放在哪里。

在SLAM過程中，需要將激光雷達當前采集的點云（紅色部分）匹配拼接到原有地圖中。

如果不進行匹配過程，所構(gòu)建的地圖可能就亂成一團，變成這樣。

五、地圖融合

在這個部分完畢以后，就進行第三步，地圖融合，也就是將這一輪來自激光雷達的新數(shù)據(jù)拼接到原始地圖當中，最終完成地圖的更新。

就像這個圖一樣，這個過程是永遠伴隨SLAM過程的。

數(shù)據(jù)融合和簡單的貼圖是有很大的差異的。因為實際上傳感器描繪的世界存在一定的誤差，或者正巧在這個時間環(huán)境有了變化，例如機器人旁邊闖入了一只小貓。

因此，實際要進行的過程會更加復雜，需要用很多概率算法，并采用濾波的方式進行融合。將上述這個過程逐次執(zhí)行，就最終產(chǎn)生了我們看到的柵格地圖。

六、Loop Closure（回環(huán)）問題

這個過程聽起來其實并不復雜，但是要處理好有很大難度。這里舉幾個例子，比如叫做Loop Closure（回環(huán)）問題。

如果匹配算法不足夠優(yōu)秀，或者環(huán)境中存在很不巧的干擾，當機器人繞著環(huán)境一圈后，就會發(fā)現(xiàn)原本是應該閉合的一個環(huán)形走廊斷開了。

比如正常地圖應該這樣：

如果處理不好，實際地圖就成這樣：

對于環(huán)境比較大的場景，回環(huán)問題是不得不面對的，但現(xiàn)實總是不完美的，即使是激光雷達這種高精度傳感器，也難免存在誤差。

而回環(huán)問題的難點恰恰在于在一開始出現(xiàn)少許誤差的時候，并不會被發(fā)覺，直到機器人繞著環(huán)路一圈，隨著誤差的累加，發(fā)現(xiàn)環(huán)路已經(jīng)無法閉合時，此時已經(jīng)釀成大錯，一般很難回天。

當然這個問題并不是無解，一個好的商用化SLAM系統(tǒng)，回環(huán)問題是否能很好的解決，就成為評判這個系統(tǒng)實力的指標了。

除了算法層面的回環(huán)問題，SLAM實際應用中還有很多這種坑，比如走廊問題與外界干擾問題。

以外界干擾問題來說，通常，激光雷達作為機器人的眼睛，一般是安裝在底盤上的，它能看到的視野很有限。當受到外界干擾（人類或者寵物等等）后，機器人很容易丟失定位精度，無法正常完成后續(xù)的建圖工作。

當機器人安裝SLAMWARE后，機器人受到干擾，可以完全不受影響，照樣能夠正常工作。

目前，SLAM的開源實現(xiàn)代表多為學術(shù)界，實際應用有很多Corner Case要處理，需要傳感器、系統(tǒng)參數(shù)、其他輔助設(shè)備的聯(lián)合調(diào)優(yōu)。

一般來說，上述的SLAM過程對于運算消耗是巨大的，雖然并沒有達到像訓練神經(jīng)網(wǎng)絡(luò)動用服務器集群那種地步，但傳統(tǒng)上需要PC級別的處理器。

除配備激光雷達外，還需要機器人具有IMU（慣性測量單元）、里程計來為激光雷達提供輔助數(shù)據(jù)，否則SLAM系統(tǒng)也難以得到運行?？偟膩碚f，SLAM算法本身是一個對于外部系統(tǒng)有著多種依賴的算法，這是一個切實的工程問題。

七、算法優(yōu)化及商用

很多機器人，比如掃地機是不可能裝一個PC進去的，為了讓SLAM能在這類設(shè)備里運行，除了解決激光雷達成本外，還要對SLAM算法做出很好的優(yōu)化。

八、路徑規(guī)劃

那么，機器人利用SLAM技術(shù)得到了有效的空間信息后，它是怎樣實現(xiàn)路徑規(guī)劃的？SLAM和路徑規(guī)劃之間關(guān)系是怎樣的？

實際上，SLAM算法本身只是完成了機器人的定位和地圖構(gòu)建兩件事情，與我們說的導航定位并不是完全等價的。這里的導航，其實是SLAM算法做不了的。它在業(yè)內(nèi)叫做運動規(guī)劃(Motion Planning)。

運動規(guī)劃是一個很大的概念，從機械臂的運動、到飛行器的飛行，再到這里我們說的掃地機的清掃路徑規(guī)劃，都是運動規(guī)劃的范疇。

我們先談談針對掃地機這類輪式機器人的運動規(guī)劃。這里所需的基礎(chǔ)能力就是路徑規(guī)劃，也就是一般在完成SLAM后，要進行一個叫做目標點導航的能力。通俗的說，就是規(guī)劃一條從A點到B點的路徑出來，然后讓機器人移動過去。

1.全局規(guī)劃

要實現(xiàn)這個過程，運動規(guī)劃要實現(xiàn)至少兩個層次的模塊，一個叫做全局規(guī)劃，這個和我們車載導航儀有一點像，它需要在地圖上預先規(guī)劃一條線路，也要有當前機器人的位置。這是由我們的SLAM系統(tǒng)提供出來的。

行業(yè)內(nèi)一般會用叫做A*的算法來實現(xiàn)這個過程，它是一種啟發(fā)式的搜索算法，非常優(yōu)秀。

它最多的應用，是在游戲中，比如像星際爭霸、魔獸爭霸之類的即時戰(zhàn)略游戲，都是使用這個算法來計算單位的運動軌跡的。

2.局部規(guī)劃

當然，僅僅規(guī)劃了路徑還是不夠的，現(xiàn)實中會有很多突發(fā)情況，比如正巧有個小孩子擋道了，就需要調(diào)整原先的路徑。

當然，有時候這種調(diào)整并不需要重新計算一遍全局路徑，機器人可能稍微繞一個彎就可以。此時，我們就需要另一個層次的規(guī)劃模塊，叫做局部規(guī)劃。

它可能并不知道機器人最終要去哪，但是對于機器人怎么繞開眼前的障礙物特別在行。

3.已知地圖（A*）與未知地圖（D*）算法

這兩個層次的規(guī)劃模塊協(xié)同工作，機器人就可以很好的實現(xiàn)從A點到B點的行動了，不過實際工作環(huán)境下，上述配置還不夠。

比如A＊算法規(guī)劃的路徑是根據(jù)已知地圖，預先規(guī)劃好的，一旦機器人前往目的地的過程中遇到了新的障礙物，就只好完全停下來，等待障礙物離開或者重新規(guī)劃路徑了。如果掃地機器人買回家，必須先把屋子都走一遍以后才肯掃地，那用戶體驗就會很差。

為此，也會有針對這類算法的改進，比如SLAMWARE內(nèi)我們采用改良的D*算法進行路徑規(guī)劃，這也是美國火星探測器采用的核心尋路算法。這是一種動態(tài)啟發(fā)式路徑搜索算法，它讓機器人在陌生環(huán)境中行動自如，在瞬息萬變的環(huán)境中游刃有余。

D*算法的最大優(yōu)點是不需要預先探明地圖，機器人可以和人一樣，即使在未知環(huán)境中，也可以展開行動，隨著機器人不斷探索，路徑也會時刻調(diào)整。

4.空間覆蓋（space coverage）

以上是目前大部分移動機器人都需要的路徑規(guī)劃算法，而掃地機器人作為最早出現(xiàn)在消費市場的服務機器人之一，它需要的路徑規(guī)劃算法更為復雜。

一般來說，掃地機需要這么幾個規(guī)劃能力：貼邊打掃、折返的工字形清掃以及沒電時候自主充電。單單依靠前面介紹的D*這類算法，無法滿足這些基礎(chǔ)需要。

掃地機器人還需要有額外的規(guī)劃算法，比如針對折返的工字形清掃，有很多問題要處理。掃地機如何最有效進行清掃而不重復清掃？如何讓掃地機和人一樣，理解房間、門、走廊這種概念？

針對這些問題，學術(shù)界長久以來有一個專門的研究課題，叫做空間覆蓋（space coverage），同時也提出了非常多的算法和理論。其中，比較有名的是Morse Decompositions，掃地機通過它實現(xiàn)對空間進行劃分，隨后進行清掃。

20世紀70年代，卡內(nèi)基梅隴大學（CMU）完全依靠超聲波做到了現(xiàn)在我們掃地機的行為，當然造價也十分昂貴。

前面介紹的從A點到B點移動路徑規(guī)劃也是實現(xiàn)這類更高級路徑規(guī)劃的基礎(chǔ)。實際上，要從SLAM實現(xiàn)到掃地機器人所需要的這些功能，還是有非常多的工作要做的。

編輯：黃飛

?