雷鋒網(wǎng)按：本文作者SLAMTEC（思嵐科技公號slamtec-sh）技術(shù)顧問，專注SLAM及相關(guān)傳感器研發(fā)應(yīng)用。本文是《機器人自主移動的秘密》系列第三篇。

我們先來看看SLAM與路徑規(guī)劃的關(guān)系。

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

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

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

要實現(xiàn)這個過程，運動規(guī)劃要實現(xiàn)至少兩個層次的模塊，一個叫做全局規(guī)劃，這個和我們車載導(dǎo)航儀有一點像，它需要在地圖上預(yù)先規(guī)劃一條線路，也要有當前機器人的位置。這是由我們的SLAM系統(tǒng)提供出來的。行業(yè)內(nèi)一般會用叫做A*的算法來實現(xiàn)這個過程，它是一種啟發(fā)式的搜索算法，非常優(yōu)秀。它最多的應(yīng)用是在游戲中，比如像星際爭霸、魔獸爭霸之類的即時戰(zhàn)略游戲，都是使用這個算法來計算單位的運動軌跡的。

當然，僅僅規(guī)劃了路徑還是不夠的，現(xiàn)實中會有很多突發(fā)情況，比如正巧有個小孩子擋道了，就需要調(diào)整原先的路徑。當然，有時候這種調(diào)整并不需要重新計算一遍全局路徑，機器人可能稍微繞一個彎就可以。此時，我們就需要另一個層次的規(guī)劃模塊，叫做局部規(guī)劃。它可能并不知道機器人最終要去哪，但是對于機器人怎么繞開眼前的障礙物特別在行。

   

這兩個層次的規(guī)劃模塊協(xié)同工作，機器人就可以很好的實現(xiàn)從A點到B點的行動了，不過實際工作環(huán)境下，上述配置還不夠。比如A＊算法規(guī)劃的路徑是根據(jù)已知地圖，預(yù)先規(guī)劃好的，一旦機器人前往目的地的過程中遇到了新的障礙物，就只好完全停下來，等待障礙物離開或者重新規(guī)劃路徑了。如果掃地機器人買回家，必須先把屋子都走一遍以后才肯掃地，那用戶體驗就會很差。

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

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

   

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

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

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

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

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

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

針對掃地機器人，我們將其特有的路徑規(guī)劃功能預(yù)先內(nèi)置在SLAMWARE中，方便廠家進行整合，不需要進行二次開發(fā)。

第二篇傳送入口：《實際應(yīng)用中，SLAM究竟是如何實現(xiàn)的？》。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。