路徑規(guī)劃技術(shù)是掃地機器人研究的核心內(nèi)容之一，機器人定位與環(huán)境地圖構(gòu)建就是為路徑規(guī)劃服務(wù)的。所謂機器人路徑規(guī)劃技術(shù)，就是機器人根據(jù)自身傳感器對環(huán)境的感知，自行規(guī)劃出一條安全的運行路線，同時高效完成作業(yè)任務(wù)。

通常，移動機器人路徑規(guī)劃需要解決3個問題：

1）使機器人能從初始位置運動到目標(biāo)位置;

2）用一定的算法使機器人能繞開障礙物，并且經(jīng)過某些必須經(jīng)過的點完成相應(yīng)的作業(yè)任務(wù);

3）在完成以上任務(wù)的前提下，盡量優(yōu)化機器人運行軌跡。

移動機器人的路徑規(guī)劃根據(jù)其目的的不同可以分為兩種，一種是傳統(tǒng)的點到點的路徑規(guī)劃，另一種就是完全遍歷路徑規(guī)劃。

點到點的路徑規(guī)劃是一種從起始點到終點的運動策略，它要求尋找一條從始點到終點的最優(yōu)（如代價最小、路徑最短、時間最短）并且合理的路徑，使移動機器人能夠在工作空間順利地通行而不碰到任何障礙物。完全遍歷路徑規(guī)劃是一種在二維工作空間中特殊的路徑規(guī)劃，指在滿足某種性能指標(biāo)最優(yōu)或準優(yōu)的前提下，尋找一條在設(shè)定區(qū)域內(nèi)從始點到終點且經(jīng)過所有可達到點的連續(xù)路徑。

對于掃地機器人來說，其作業(yè)任務(wù)是清掃房間，它的路徑規(guī)劃屬于完全遍歷路徑規(guī)劃，需滿足兩個指標(biāo)：遍歷性和不重復(fù)性。所謂遍歷性是指掃地機器人運動軌跡需要最大程度的遍布所有可大空間，它反映的是機器人的工作質(zhì)量問題。所謂不重復(fù)性是指掃地機器人的行走路線應(yīng)盡量避免重復(fù)，反映的是機器人的工作效率問題。

掃地機器人的自主尋路可以分為兩種：隨機覆蓋法和路徑規(guī)劃式。

隨機覆蓋法

隨機覆蓋法，有人也稱為隨機碰撞式導(dǎo)航，但這并非是指機器人真正與環(huán)境中的物體產(chǎn)生碰撞，也非毫無章法的在地板上隨機移動，換言之在工程操作中“隨機”也是一個難以達到要求，隨機覆蓋法是指機器人根據(jù)一定的移動算法，如三角形、五邊形軌跡嘗試性的覆蓋作業(yè)區(qū)，如果遇到障礙，則執(zhí)行對應(yīng)的轉(zhuǎn)向函數(shù)。這種方法是一種以時間換空間的低成本策略，如不計時間可以達到 100%覆蓋率。隨機覆蓋法不用定位、也沒有環(huán)境地圖，也無法對路徑進行規(guī)劃，所以其移動路徑基本依賴于內(nèi)置的算法，算法的優(yōu)劣也決定了其清掃質(zhì)量與效率的高低。

美國iRobot公司研發(fā)的iRobot Roomba 3-8系列是隨機碰撞尋路系統(tǒng)的典型代表。

據(jù)稱，其采用iAdapt智能化清掃技術(shù)的專利技術(shù)，這是一種軟、硬件相結(jié)合的智能化AI清掃系統(tǒng)，硬件由Roomba前方的若干紅外探測器、底部灰塵偵測器和落差傳感器、毛刷膠刷邊刷測速系統(tǒng)等等組成，通過Roomba的硬件傳回的信息，iRobot自身的軟件可以對回傳信息進行分析，根據(jù)紅外回傳信息的強度、范圍、高度、轉(zhuǎn)速、電流大小、阻力等參數(shù)，計算出前方障礙物大致形狀，再經(jīng)過軟件的處理運算，得出的結(jié)果就是Roomba下一步清潔方式，Roomba以每秒60次的速度計算周邊障礙物的情況，同時根據(jù)所處環(huán)境作出40余種清掃動作，如圍繞、折返、螺旋、貼邊、轉(zhuǎn)身等等。

其次iRobot采用面積模糊判定算法，根據(jù)房間面積自動設(shè)定清掃時長。和路徑規(guī)劃不同的是，Roomba開始收集算法估算所需的兩個重要參數(shù)：單次行進距離和單位時間碰撞頻率。單次行進距離越長則間接代表房間面積越大，走幾步就調(diào)頭則間接代表房間面積較小。每次碰撞Roomba都能收集到相關(guān)信息，單位時間內(nèi)碰撞頻率越高代表房間面積越小，碰撞頻率低則表示需要清掃的面積較大。

市面上大多數(shù)掃地機器人雖都采用隨機碰撞尋路方式，然而清潔效率卻差異很大，歸根到底還是軟件算法上的問題，這也是為什么同樣大家買的都是隨機碰撞尋路方式的掃地機器人，在覆蓋率與效率上面卻有天壤之別。

路徑規(guī)劃式

規(guī)劃式導(dǎo)航需要建立起環(huán)境地圖并進行定位。對路徑規(guī)劃的研究已經(jīng)持續(xù)很多年了，也提出了很多種類的方法。不同的方法有各自的優(yōu)缺點，適用范圍各不相同，沒有一種路徑規(guī)劃方法能適用于所有的環(huán)境信息。其中的人工勢場法、柵格法、模板模型法、人工智能法等是路徑規(guī)劃中很典型的方法，并且受到越來越多的關(guān)注。下面將分別介紹上述這些典型的路徑規(guī)劃方法。

1.人工勢場法

人工勢場法是機器人導(dǎo)航中提出的一種虛擬力法，其基本方法是將機器人在周圍環(huán)境中的運動設(shè)計成在一種勢場中的運動，是對機器人運動環(huán)境的一種抽象描述，機器人在場中具有一定的抽象勢能，勢能源有兩種：斥力極和引力極。

機器人在不希望進入的區(qū)域和障礙物屬于斥力極：目標(biāo)及機器人系統(tǒng)建議通過的區(qū)域為引力極。在極的周圍產(chǎn)生相應(yīng)的勢，在任何一點的勢為該點產(chǎn)生的勢之和。該勢的負梯度稱為勢力。勢場的建立主要用于動態(tài)避障，此時的引力極是局部環(huán)境中的中間目標(biāo)，斥力極則是局部環(huán)境中的障礙物。引力和斥力的合力作為機器人的加速力，來控制機器人的運動方向和計算機器人的位置。該方法結(jié)構(gòu)簡單，便于低層的實時控制，在實時避障和平滑的軌跡控制方面，得到了廣泛的應(yīng)用。但對存在的局部最優(yōu)解的問題，容易產(chǎn)生死鎖現(xiàn)象，因而可能使機器人在到達目標(biāo)點之前就停留在局部最優(yōu)點。

2.柵格法

設(shè)定移動機器人實際幾何形狀可用方形區(qū)域表示。規(guī)劃過程中將機器人縮為一個點，而環(huán)境中的障礙物邊界做相應(yīng)的擴展及模糊化處理。采用網(wǎng)格表示工作空間，即把工作空間劃分為一個個大小相同的方格，方格大小與機器人幾何外形相同。

用柵格法表示環(huán)境：使用大小相同的柵格劃分機器人的工作空間，并用柵格數(shù)組來表示環(huán)境，每個柵格是兩種狀態(tài)之一，或者在自由空間中，或者在障礙物空間中。這種方法的特點是簡單，易于實現(xiàn)，從而為路徑規(guī)劃的實現(xiàn)帶來了很多方便，具有表示不規(guī)則障礙物的能力;其缺點是表示效率不高，存在著時空開銷與精度之間的矛盾，柵格的大小直接影響著環(huán)境信息存儲量的大小和規(guī)劃時間的長短。柵格劃分大了，環(huán)境信息存儲量就小了，規(guī)劃時間短，分辨率下降，在密集環(huán)境下發(fā)現(xiàn)路徑的能力減弱;柵格劃分小了，環(huán)境分辨率高，在密集環(huán)境下發(fā)現(xiàn)路徑的能力強，但環(huán)境的存儲量大。所以柵格的大小直接影響著控制算法的性能。

3.模板模型法

另外一種常用的方法是模板模型。DeCaravalh提出了一種依靠二維清潔環(huán)境的地圖并且是基于完全遍歷路徑規(guī)劃的模板。為了完成完全遍歷路徑規(guī)劃，DeCaravalh定義了五種模板，分別是：前進模型（Towards Model），沿邊轉(zhuǎn)向模型（Side Shift）、回逆跟蹤（Backtracker），U轉(zhuǎn)彎模型，U轉(zhuǎn)彎交替模型。模板模型法是基于先驗知識和先前的環(huán)境地圖遍歷機器人讓得到的環(huán)境信息來匹配事先定義的模板。因此，整個路徑就是一系列的模板組成的。在這個方法中，為了簡化路徑規(guī)劃過程，環(huán)境事先擴大，這樣這種小巧靈活的機器人就可以考慮成一個質(zhì)點。基于模板的模型完全遍歷路徑規(guī)劃，它要求事先定義環(huán)境模型和模板的記憶，因此對于變化著的環(huán)境就不好處理了，比如在遍歷機器人的工作過程中突然出現(xiàn)一個障礙等。

4.人工智能法

近年來有許多學(xué)者利用模糊邏輯、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法等現(xiàn)代計算智能技術(shù)來解決機器人的路徑規(guī)劃問題，并取得了一些可喜的成果。

1）模糊控制算法

模糊控制方法應(yīng)用與路徑規(guī)劃，是一種很有特色的方法，是在線規(guī)劃中通常采用的一種規(guī)劃方法，包括建模和全局規(guī)劃。它用若干個傳感器探測前方道路和障礙物的狀況，依據(jù)駕駛員的駕車經(jīng)驗制定模糊控制規(guī)則，用于處理傳感器信息，并輸出速度、加速度、轉(zhuǎn)角等控制量，指導(dǎo)小車的前進。該方法最大的優(yōu)點是參與人的駕駛經(jīng)驗，計算量不大，能夠?qū)崿F(xiàn)實時規(guī)劃，可以做到克服勢場法易產(chǎn)生的局部極點問題，效果比較理想。

模糊控制的路徑規(guī)劃方法特別適用于局部避碰規(guī)劃，具有設(shè)計簡單、直觀、速度快、效果好等特點。

2）神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃

神經(jīng)網(wǎng)絡(luò)已經(jīng)被應(yīng)用到很多的工程領(lǐng)域，機器人領(lǐng)域當(dāng)然也不例外。神經(jīng)網(wǎng)絡(luò)在路徑規(guī)劃中的應(yīng)用也很多。Tse為清掃移動機器人從一個地方到另外一個地方的運輸，提出了BP神經(jīng)網(wǎng)絡(luò)，這個模型通過自學(xué)習(xí)能進行自主導(dǎo)航的路徑規(guī)劃。避障的完全遍歷路徑規(guī)劃能夠通過離線學(xué)習(xí)達到，并且有運動行為，路線規(guī)劃和全局路徑規(guī)劃三個步驟。在運動行為階段機器人通過各種傳感器采集3d環(huán)境信息，然后把這些信息輸入到BP神經(jīng)網(wǎng)絡(luò)中，機器人可以清掃周邊的區(qū)域直到周邊沒有未清掃區(qū)域。在路線規(guī)劃階段，清潔機器人要決定一條最短的路徑通向工作空間中其他未清掃區(qū)域，在全局路徑規(guī)劃中，產(chǎn)生一個全局環(huán)境地圖，然后機器人從起始點開始，清掃整個工作空間。

3）遺傳算法

遺傳算法是由JohnH oland在70年代早期發(fā)展起來的一種自然選擇和群體遺傳機理的搜索算法。它模擬了自然選擇和自然遺傳過程中發(fā)生的繁殖，交配和突變現(xiàn)象。它將每個可能的解看作是群體（所有可能解）中的一個個體，并將每個個體編碼成字符串的形式，根據(jù)預(yù)定的目標(biāo)函數(shù)對每個個體進行評價，給出一個適合值。開始時總是隨機地產(chǎn)生一些個體（即候選解），根據(jù)這些個體的適合度利用遺傳算法（選擇、交叉、變異）對這些個體進行交叉組合，得到一個新的個體。這一群新的個體由于繼承了上一代的一些優(yōu)良性質(zhì)，因而明顯優(yōu)于上一代，這樣逐步朝著更優(yōu)解的方向進化。遺傳算法對于復(fù)雜的優(yōu)化問題無需建模和進行復(fù)雜的運算，只要用遺傳算法的三種算子就能找到優(yōu)化解，因而在各種領(lǐng)域中得到了廣泛的應(yīng)用。在機器人相關(guān)領(lǐng)域研究中，遺傳算法已被應(yīng)用于機械手的軌跡生成、多機器人的路徑規(guī)劃、冗余機械手的障礙避碰。

另一方面，當(dāng)遺傳算法與模糊邏輯，人工神經(jīng)網(wǎng)絡(luò)等技術(shù)相結(jié)合，組合成一個智能學(xué)習(xí)和進化系統(tǒng)時，便顯示了它的強大威力。有很多學(xué)者綜合運用上述智能方法作了路徑規(guī)劃的嘗試。如Toshio Fukuda等人提出了一個具有“結(jié)構(gòu)化智能”的機器人導(dǎo)航系統(tǒng)。它以模糊控制器為核心。路徑規(guī)劃的一種分層決策機構(gòu)，并且根據(jù)反饋得到的獎賞，懲罰信息進行學(xué)習(xí)和進化。其優(yōu)點是系統(tǒng)自學(xué)習(xí)能力，這也是其研究的側(cè)重點，然而他們把系統(tǒng)做的比較復(fù)雜，效率較低。

總結(jié)

移動機器人的路徑規(guī)劃技術(shù)已經(jīng)取得了豐碩成果，但各種方法各有優(yōu)缺點，也沒有一種方法能適用于任何場合，如模版匹配方法過于依賴機器人過去的經(jīng)驗; 人工勢場路徑規(guī)劃方法通常存在局部極小點和計算量過大的問題。不過隨著科技不斷發(fā)展，這些問題都會出現(xiàn)新的解決或者替代方法，同時機器人應(yīng)用領(lǐng)域還將不斷擴大，機器人工作環(huán)境會更復(fù)雜，移動機器人路徑規(guī)劃這一課題領(lǐng)域還將不斷深入。