1
今年8月，雷鋒網將在深圳舉辦一場盛況空前有全球影響力的人工智能與機器人創新大會。屆時雷鋒網將發布“人工智能&機器人Top25創新企業榜”榜單。目前，我們正在拜訪人工智能、機器人領域的相關公司，從中篩選最終入選榜單的公司名單。如果你也想加入我們的榜單之中，請聯系：2020@leiphone.com。
雷鋒網按：本文作者張玉坤/劉偉，來自北郵人機與認知實驗室（公號：人機與認知實驗室）。
路徑規劃技術是掃地機器人研究的核心內容之一，機器人定位與環境地圖構建（后面雷鋒網專欄將會更新）就是為路徑規劃服務的。所謂機器人路徑規劃技術，就是機器人根據自身傳感器對環境的感知,自行規劃出一條安全的運行路線,同時高效完成作業任務。
通常，移動機器人路徑規劃需要解決3個問題：
1）使機器人能從初始位置運動到目標位置；
2）用一定的算法使機器人能繞開障礙物,并且經過某些必須經過的點完成相應的作業任務；
3）在完成以上任務的前提下,盡量優化機器人運行軌跡。
移動機器人的路徑規劃根據其目的的不同可以分為兩種，一種是傳統的點到點的路徑規劃，另一種就是完全遍歷路徑規劃。
點到點的路徑規劃是一種從起始點到終點的運動策略，它要求尋找一條從始點到終點的最優(如代價最小、路徑最短、時間最短)并且合理的路徑，使移動機器人能夠在工作空間順利地通行而不碰到任何障礙物。完全遍歷路徑規劃是一種在二維工作空間中特殊的路徑規劃，指在滿足某種性能指標最優或準優的前提下，尋找一條在設定區域內從始點到終點且經過所有可達到點的連續路徑。
對于掃地機器人來說，其作業任務是清掃房間，它的路徑規劃屬于完全遍歷路徑規劃，需滿足兩個指標：遍歷性和不重復性。所謂遍歷性是指掃地機器人運動軌跡需要最大程度的遍布所有可大空間，它反映的是機器人的工作質量問題。所謂不重復性是指掃地機器人的行走路線應盡量避免重復，反映的是機器人的工作效率問題。
掃地機器人的自主尋路可以分為兩種：隨機覆蓋法和路徑規劃式。
隨機覆蓋法，有人也稱為隨機碰撞式導航，但這并非是指機器人真正與環境中的物體產生碰撞，也非毫無章法的在地板上隨機移動，換言之在工程操作中“隨機”也是一個難以達到要求，隨機覆蓋法是指機器人根據一定的移動算法，如三角形、五邊形軌跡嘗試性的覆蓋作業區，如果遇到障礙，則執行對應的轉向函數。這種方法是一種以時間換空間的低成本策略，如不計時間可以達到 100%覆蓋率。隨機覆蓋法不用定位、也沒有環境地圖，也無法對路徑進行規劃，所以其移動路徑基本依賴于內置的算法，算法的優劣也決定了其清掃質量與效率的高低。
美國iRobot公司研發的iRobot Roomba 3-8系列是隨機碰撞尋路系統的典型代表。
據稱，其采用iAdapt智能化清掃技術的專利技術，這是一種軟、硬件相結合的智能化AI清掃系統，硬件由Roomba前方的若干紅外探測器、底部灰塵偵測器和落差傳感器、毛刷膠刷邊刷測速系統等等組成，通過Roomba的硬件傳回的信息，iRobot自身的軟件可以對回傳信息進行分析，根據紅外回傳信息的強度、范圍、高度、轉速、電流大小、阻力等參數，計算出前方障礙物大致形狀，再經過軟件的處理運算，得出的結果就是Roomba下一步清潔方式，Roomba以每秒60次的速度計算周邊障礙物的情況，同時根據所處環境作出40余種清掃動作，如圍繞、折返、螺旋、貼邊、轉身等等。
其次iRobot采用面積模糊判定算法，根據房間面積自動設定清掃時長。和路徑規劃不同的是，Roomba開始收集算法估算所需的兩個重要參數：單次行進距離和單位時間碰撞頻率。單次行進距離越長則間接代表房間面積越大，走幾步就調頭則間接代表房間面積較小。每次碰撞Roomba都能收集到相關信息，單位時間內碰撞頻率越高代表房間面積越小，碰撞頻率低則表示需要清掃的面積較大。
市面上大多數掃地機器人雖都采用隨機碰撞尋路方式，然而清潔效率卻差異很大，歸根到底還是軟件算法上的問題，這也是為什么同樣大家買的都是隨機碰撞尋路方式的掃地機器人，在覆蓋率與效率上面卻有天壤之別。
規劃式導航需要建立起環境地圖并進行定位。對路徑規劃的研究已經持續很多年了，也提出了很多種類的方法。不同的方法有各自的優缺點，適用范圍各不相同，沒有一種路徑規劃方法能適用于所有的環境信息。其中的人工勢場法、柵格法、模板模型法、人工智能法等是路徑規劃中很典型的方法，并且受到越來越多的關注。下面將分別介紹上述這些典型的路徑規劃方法。
1.人工勢場法
人工勢場法是機器人導航中提出的一種虛擬力法，其基本方法是將機器人在周圍環境中的運動設計成在一種勢場中的運動，是對機器人運動環境的一種抽象描述，機器人在場中具有一定的抽象勢能，勢能源有兩種:斥力極和引力極。
機器人在不希望進入的區域和障礙物屬于斥力極:目標及機器人系統建議通過的區域為引力極。在極的周圍產生相應的勢，在任何一點的勢為該點產生的勢之和.該勢的負梯度稱為勢力。勢場的建立主要用于動態避障，此時的引力極是局部環境中的中間目標，斥力極則是局部環境中的障礙物。引力和斥力的合力作為機器人的加速力，來控制機器人的運動方向和計算機器人的位置。該方法結構簡單，便于低層的實時控制，在實時避障和平滑的軌跡控制方面，得到了廣泛的應用。但對存在的局部最優解的問題，容易產生死鎖現象，因而可能使機器人在到達目標點之前就停留在局部最優點。
2.柵格法
設定移動機器人實際幾何形狀可用方形區域表示。規劃過程中將機器人縮為一個點，而環境中的障礙物邊界做相應的擴展及模糊化處理。采用網格表示工作空間，即把工作空間劃分為一個個大小相同的方格，方格大小與機器人幾何外形相同。
用柵格法表示環境：使用大小相同的柵格劃分機器人的工作空間，并用柵格數組來表示環境，每個柵格是兩種狀態之一，或者在自由空間中，或者在障礙物空間中。這種方法的特點是簡單，易于實現，從而為路徑規劃的實現帶來了很多方便，具有表示不規則障礙物的能力；其缺點是表示效率不高，存在著時空開銷與精度之間的矛盾，柵格的大小直接影響著環境信息存儲量的大小和規劃時間的長短。柵格劃分大了，環境信息存儲量就小了，規劃時間短，分辨率下降，在密集環境下發現路徑的能力減弱；柵格劃分小了，環境分辨率高，在密集環境下發現路徑的能力強，但環境的存儲量大。所以柵格的大小直接影響著控制算法的性能。
3.模板模型法
另外一種常用的方法是模板模型。DeCaravalh提出了一種依靠二維清潔環境的地圖并且是基于完全遍歷路徑規劃的模板。為了完成完全遍歷路徑規劃，DeCaravalh定義了五種模板，分別是：前進模型(Towards Model)，沿邊轉向模型(Side Shift)、回逆跟蹤(Backtracker)，U轉彎模型，U轉彎交替模型。模板模型法是基于先驗知識和先前的環境地圖遍歷機器人讓得到的環境信息來匹配事先定義的模板。因此，整個路徑就是一系列的模板組成的。在這個方法中，為了簡化路徑規劃過程，環境事先擴大，這樣這種小巧靈活的機器人就可以考慮成一個質點。基于模板的模型完全遍歷路徑規劃，它要求事先定義環境模型和模板的記憶，因此對于變化著的環境就不好處理了，比如在遍歷機器人的工作過程中突然出現一個障礙等。
4.人工智能法
近年來有許多學者利用模糊邏輯、人工神經網絡、遺傳算法等現代計算智能技術來解決機器人的路徑規劃問題，并取得了一些可喜的成果。
1)模糊控制算法
模糊控制方法應用與路徑規劃，是一種很有特色的方法，是在線規劃中通常采用的一種規劃方法，包括建模和全局規劃。它用若干個傳感器探測前方道路和障礙物的狀況，依據駕駛員的駕車經驗制定模糊控制規則，用于處理傳感器信息，并輸出速度、加速度、轉角等控制量，指導小車的前進。該方法最大的優點是參與人的駕駛經驗，計算量不大，能夠實現實時規劃，可以做到克服勢場法易產生的局部極點問題，效果比較理想。
模糊控制的路徑規劃方法特別適用于局部避碰規劃，具有設計簡單、直觀、速度快、效果好等特點。
2)神經網絡路徑規劃
神經網絡已經被應用到很多的工程領域，機器人領域當然也不例外。神經網絡在路徑規劃中的應用也很多。Tse為清掃移動機器人從一個地方到另外一個地方的運輸，提出了BP神經網絡，這個模型通過自學習能進行自主導航的路徑規劃。避障的完全遍歷路徑規劃能夠通過離線學習達到，并且有運動行為，路線規劃和全局路徑規劃三個步驟。在運動行為階段機器人通過各種傳感器采集3d環境信息，然后把這些信息輸入到BP神經網絡中，機器人可以清掃周邊的區域直到周邊沒有未清掃區域。在路線規劃階段，清潔機器人要決定一條最短的路徑通向工作空間中其他未清掃區域，在全局路徑規劃中，產生一個全局環境地圖，然后機器人從起始點開始，清掃整個工作空間。
3)遺傳算法
遺傳算法是由JohnH oland在70年代早期發展起來的一種自然選擇和群體遺傳機理的搜索算法。它模擬了自然選擇和自然遺傳過程中發生的繁殖，交配和突變現象。它將每個可能的解看作是群體(所有可能解)中的一個個體，并將每個個體編碼成字符串的形式，根據預定的目標函數對每個個體進行評價，給出一個適合值。開始時總是隨機地產生一些個體(即候選解)，根據這些個體的適合度利用遺傳算法(選擇、交叉、變異)對這些個體進行交叉組合，得到一個新的個體。這一群新的個體由于繼承了上一代的一些優良性質，因而明顯優于上一代，這樣逐步朝著更優解的方向進化。遺傳算法對于復雜的優化問題無需建模和進行復雜的運算，只要用遺傳算法的三種算子就能找到優化解，因而在各種領域中得到了廣泛的應用。在機器人相關領域研究中，遺傳算法已被應用于機械手的軌跡生成、多機器人的路徑規劃、冗余機械手的障礙避碰。
另一方面，當遺傳算法與模糊邏輯，人工神經網絡等技術相結合，組合成一個智能學習和進化系統時，便顯示了它的強大威力。有很多學者綜合運用上述智能方法作了路徑規劃的嘗試。如Toshio Fukuda等人提出了一個具有“結構化智能”的機器人導航系統。它以模糊控制器為核心。路徑規劃的一種分層決策機構，并且根據反饋得到的獎賞，懲罰信息進行學習和進化。其優點是系統自學習能力，這也是其研究的側重點，然而他們把系統做的比較復雜，效率較低。
移動機器人的路徑規劃技術已經取得了豐碩成果，但各種方法各有優缺點，也沒有一種方法能適用于任何場合，如模版匹配方法過于依賴機器人過去的經驗; 人工勢場路徑規劃方法通常存在局部極小點和計算量過大的問題。不過隨著科技不斷發展，這些問題都會出現新的解決或者替代方法，同時機器人應用領域還將不斷擴大，機器人工作環境會更復雜，移動機器人路徑規劃這一課題領域還將不斷深入。
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
