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