掃地機(jī)器人該如何進(jìn)行路徑規(guī)劃？需要解決什么問題？

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

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

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

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

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

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

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

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

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

隨機(jī)覆蓋法

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

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

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

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

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

路徑規(guī)劃式

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

1.人工勢場法

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

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

2.柵格法

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

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

3.模板模型法

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

4.人工智能法

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

1）模糊控制算法

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

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

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

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

3）遺傳算法

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

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

總結(jié)

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