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