一種基于新的單元分解法的全覆蓋路徑規(guī)劃算法

李燊

（沈陽(yáng)新松機(jī)器人自動(dòng)化股份有限公司，遼寧 沈陽(yáng) 100169）

0 引言

全覆蓋路徑規(guī)劃算法是指在一個(gè)有限且有界的區(qū)域內(nèi)，獲得一條能夠覆蓋除了障礙物外所有區(qū)域的路徑[1-2]。一個(gè)好的全覆蓋路徑規(guī)劃算法，應(yīng)滿足覆蓋率高、重復(fù)率盡量低。

目前，已有全覆蓋路徑規(guī)劃算法主要有隨機(jī)法、模板法、單元分解法、柵格法等[3-4]。其中隨機(jī)法讓機(jī)器人隨機(jī)選擇一個(gè)方向前進(jìn)，遇到障礙物后轉(zhuǎn)向再繼續(xù)前進(jìn)。這種方法簡(jiǎn)單，但無(wú)法保證全覆蓋[4]，一般用于未知環(huán)境中。模板法采用預(yù)先設(shè)定的模板與當(dāng)前環(huán)境信息比較，進(jìn)而選擇下一步路徑，但模板法缺乏對(duì)整個(gè)環(huán)境的規(guī)劃，效率較低。

單元分解法是將含有障礙物的整個(gè)區(qū)域，分解成若干無(wú)障礙的子區(qū)域，子區(qū)域之間采用某種算法進(jìn)行遍歷。常用單元分解法有Trapeziodal分解法[5]和Boustrophedon分解法[6]。Trapeziodal分解法是將一條直線掃過(guò)目標(biāo)區(qū)域，當(dāng)直線遇到多邊形障礙物的頂點(diǎn)時(shí)，產(chǎn)生IN,OUT,MIDDLE三種情形，依據(jù)不同情形將環(huán)境分成若干梯形子區(qū)域。為了減少相鄰子區(qū)域邊界處的重復(fù)覆蓋，Boustrophedon單元分解法在Trapeziodal分解法基礎(chǔ)上進(jìn)一步合并MIDDLE操作產(chǎn)生的子區(qū)域，減少子區(qū)域個(gè)數(shù)，進(jìn)而減少重復(fù)的覆蓋，提高效率，但相鄰子區(qū)域邊界仍有重復(fù)覆蓋問(wèn)題。以上單元分解法，障礙物需為為多邊形。為了解決非多邊形的障礙物問(wèn)題，morse分解法[7]以morse函數(shù)的等值線與障礙物的切點(diǎn)作為關(guān)鍵點(diǎn),以關(guān)鍵點(diǎn)為頂點(diǎn)，障礙物的邊界和等值線為邊，對(duì)地圖進(jìn)行分區(qū)，同時(shí)選擇不同的morse函數(shù)可以劃分成不同的子區(qū)域，生成不同的規(guī)劃路線。但此方法復(fù)雜且未解決相鄰子區(qū)域邊界重復(fù)覆蓋問(wèn)題。

在基于柵格地圖的全覆蓋路徑規(guī)劃方法中，文獻(xiàn)［8］采用wavefront算法標(biāo)記各個(gè)柵格的代價(jià)值，然后在從起點(diǎn)開(kāi)始，在相鄰的未覆蓋的柵格中的找到代價(jià)最大的作為下一個(gè)目標(biāo)點(diǎn)，如果代價(jià)相同則隨機(jī)選擇其中一個(gè)。

基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)[9]的柵格覆蓋規(guī)劃方法是將神經(jīng)元與柵格地圖離散坐標(biāo)對(duì)應(yīng)，通過(guò)規(guī)定障礙物和非障礙物對(duì)神經(jīng)元輸入激勵(lì)和抑制的不同，進(jìn)而判斷機(jī)器人的位置，該方法可用于未知環(huán)境，并對(duì)未知環(huán)境中動(dòng)態(tài)障礙物實(shí)時(shí)避障。

柵格覆蓋法的目的都是遍歷所有空閑柵格，柵格的大小往往設(shè)置成機(jī)器人的寬度，而“部分占用”的柵格也被當(dāng)作整體障礙物柵格，對(duì)于較大的機(jī)器人，會(huì)造成遺漏很多區(qū)域未覆蓋。

本文提出一種全覆蓋路徑規(guī)劃方法，采用一種新的基于柵格地圖的單元分解方法,該方法對(duì)障礙物形狀無(wú)任何要求，同時(shí)地圖柵格的大小不必按機(jī)器人寬度設(shè)置，適用于高分辨率柵格地圖。首先，在地圖的空閑區(qū)域以機(jī)器人寬度為間隔生成若干條平行路線,然后根據(jù)相鄰路線的端點(diǎn)是否屬于同一障礙物，將所有路線劃分成不同的區(qū)域，在子區(qū)域內(nèi)機(jī)器人沿著已生成的路線往復(fù)運(yùn)動(dòng)，然后按照最短距離原則遍歷子區(qū)域。

1 全覆蓋路徑規(guī)劃

1.1 路線生成

柵格地圖將機(jī)器人周圍空間分解成若干單元格,依據(jù)障礙物占有情況將環(huán)境劃分為空閑區(qū)域和占有區(qū)域。如圖1所示，深色柵格代表占有柵格，用1表示，所圍成區(qū)域?yàn)檎加袇^(qū)域，白色柵格代表空閑柵格，用0表示，所圍成區(qū)域?yàn)榭臻e區(qū)域。

首先對(duì)柵格地圖進(jìn)行預(yù)處理，即對(duì)柵格地圖邊界做封閉處理，并將障礙物以機(jī)器人半徑進(jìn)行膨脹。

設(shè)機(jī)器人直徑為柵格寬度的倍，從地圖最左側(cè)有空閑柵格的第一列開(kāi)始，每間隔（k-1）列生成路線，有路線的列稱為路線列。為了圖示清晰，本文中取k=2。

生成路線的具體方法，如圖1所示，從路線列的最低端至最頂端遍歷柵格狀態(tài)，當(dāng)柵格狀態(tài)由占用柵格變?yōu)榭臻e柵格時(shí)，即由1變成0時(shí)，此處為0的柵格作為路線的一個(gè)端點(diǎn)，為了以下描述方便，這里我們稱為1的障礙物柵格為路線的下端點(diǎn)；當(dāng)柵格狀態(tài)由0變?yōu)?時(shí)，此處為0的柵格為路線的另一個(gè)端點(diǎn)，為1的障礙物柵格我們稱為路線的上端點(diǎn)。路線表示為，路線下端點(diǎn)為，路線上端點(diǎn)為，其中n表示路線的列數(shù)序號(hào)，m表示所在路線列上路線的序號(hào)。

圖1 路線生成

1.2 子區(qū)域劃分

子區(qū)域的劃分就是把在空閑區(qū)域生成的路線劃分為若干子區(qū)域，劃分的原則為：如果兩條相鄰路線的上端點(diǎn)屬于同一障礙物區(qū)域，下端點(diǎn)屬于同一障礙物區(qū)域，則這兩條路線屬于同一個(gè)子區(qū)域。

劃分區(qū)域的基本方法為：從地圖的左側(cè)至右側(cè)遍歷所有路線列，首先把第一路線列中所有路線分別放入新的不同子區(qū)域中，然后繼續(xù)向右側(cè)遍歷其他路線列上的路線，對(duì)于路線，以圖2所示為例，從下端點(diǎn)開(kāi)始，沿著障礙物邊緣向左側(cè)搜索，如果能找到其左側(cè)相鄰路線列中某一路線的下端點(diǎn)；同時(shí)從的上端點(diǎn)開(kāi)始沿著障礙物邊緣向左側(cè)搜索，如果也能找到左側(cè)相鄰路線列中的上端點(diǎn)，則將加入到所屬的子區(qū)域，否則建立新的子區(qū)域，并加入。

圖2 沿障礙物邊緣搜索

圖3 子區(qū)域的劃分

劃分區(qū)域的關(guān)鍵在于如何從路線端點(diǎn)沿障礙物邊緣向左側(cè)搜索相鄰路線列中路線的端點(diǎn)。對(duì)于路線的下端點(diǎn)，首先將下端點(diǎn)作為當(dāng)前柵格，搜索的具體流程如下：

①判斷當(dāng)前柵格左上角的柵格是否為1，如果不是1，轉(zhuǎn)到②；如果是1，如圖4中a所示，從左上角柵格開(kāi)始，在此列繼續(xù)向上遍歷柵格狀態(tài)，直到柵格狀態(tài)由1變?yōu)?，即找到障礙物邊緣柵格R，然后轉(zhuǎn)至⑤。如果直至地圖上邊界柵格仍未變成0，說(shuō)明從障礙物邊緣向左側(cè)搜索，未找到相鄰路線列中路線的端點(diǎn)，轉(zhuǎn)到⑥。

②判斷當(dāng)前柵格的左側(cè)柵格是否為1，如果不為1，則轉(zhuǎn)到③；如果為1，如圖4中b所示，則找到相鄰列障礙物邊緣柵格R，轉(zhuǎn)到⑤。

③判斷當(dāng)前柵格的左下角柵格是否為1，如果不為1，則轉(zhuǎn)到④；如果為1，如圖4中c所示，則找到相鄰列障礙物邊緣柵格R，轉(zhuǎn)到⑤。

④判斷當(dāng)前柵格的下方柵格是否為1，如果不為1，轉(zhuǎn)到⑥；如果為1，如圖4中d所示，從這個(gè)下方柵格開(kāi)始在當(dāng)前列向下沿著為1的柵格遍歷，直到其左列相鄰柵格為1，即找到相鄰列障礙物邊緣柵格R，轉(zhuǎn)到⑤；如果向下遍歷柵格時(shí)，柵格狀態(tài)變?yōu)?或者一直遍歷到地圖下邊界，仍未在左側(cè)列中找到R，則說(shuō)明從沿著障礙物邊緣向左側(cè)搜索，未找到相鄰路線列中路線的端點(diǎn)，轉(zhuǎn)到⑥。

圖4 從向左側(cè)沿障礙物邊緣搜索

⑥返回并輸出無(wú)結(jié)果，即未找到相鄰路線列中某路線端點(diǎn)。

圖5 從向左側(cè)沿障礙物邊緣搜索

1.3 子區(qū)域的遍歷

如果把子區(qū)域作為一個(gè)節(jié)點(diǎn)，那么子區(qū)域的遍歷就是機(jī)器人從初始節(jié)點(diǎn)出發(fā)，用最短的路程依次走過(guò)其他節(jié)點(diǎn)。本文采用最短距離原則進(jìn)行子區(qū)域的遍歷。

子區(qū)域作為節(jié)點(diǎn)的位置可以取子區(qū)域的中心，在本文中用子區(qū)域中間路線的中點(diǎn)來(lái)代替。假設(shè)子區(qū)域包含有條路線，中間路線取左起第條，子區(qū)域節(jié)點(diǎn)位置即為該路線中點(diǎn)。同時(shí)，我們把子區(qū)域最左側(cè)路線的兩個(gè)端點(diǎn)和最右側(cè)路線的兩個(gè)端點(diǎn)稱為子區(qū)域的四個(gè)頂點(diǎn)。

在子區(qū)域內(nèi)機(jī)器人按生成路線往復(fù)運(yùn)動(dòng)，即采用弓字形路徑規(guī)劃，機(jī)器人在該子區(qū)域的最終位置在該子區(qū)域頂點(diǎn)處。然后采用A*算法規(guī)劃?rùn)C(jī)器人當(dāng)前位置到其他未走過(guò)子區(qū)域節(jié)點(diǎn)的路徑并計(jì)算路徑距離，選擇距離最近的子區(qū)域作為下一個(gè)目標(biāo)子區(qū)域。

確定好目標(biāo)子區(qū)域后，計(jì)算當(dāng)前位置與目標(biāo)子區(qū)域四個(gè)頂點(diǎn)的距離，此距離為采用A*算法規(guī)劃路徑并計(jì)算的路徑距離。選擇距離最近的頂點(diǎn)作為的目標(biāo)點(diǎn),到達(dá)目標(biāo)子區(qū)域后繼續(xù)按已生成路線進(jìn)行弓字形路徑規(guī)劃。如此反復(fù)，直至走完所有子區(qū)域中的所有路線。

如圖6所示為仿真實(shí)驗(yàn)中，子區(qū)域的遍歷順序。圖7為最終規(guī)劃的全覆蓋路線。

圖6 子區(qū)域遍歷順序

圖7 全覆蓋路徑規(guī)劃

2 結(jié)論

本文提出的全覆蓋路徑規(guī)劃方法，采用了新的針對(duì)已知柵格地圖的單元分解法，該方法簡(jiǎn)單，實(shí)用性強(qiáng)，覆蓋率高，對(duì)障礙物形狀無(wú)限制，可應(yīng)用于高分辨率地圖，仿真結(jié)果表明了算法的有效性。本文方法中，子區(qū)域的遍歷時(shí)采用了A*算法規(guī)劃當(dāng)前位置與子區(qū)域各節(jié)點(diǎn)和頂點(diǎn)的路徑并計(jì)算距離，對(duì)于子區(qū)域多的復(fù)雜環(huán)境，運(yùn)算時(shí)間長(zhǎng)。因此，如何更高效地進(jìn)行子區(qū)域的遍歷，也是本文的下一步重點(diǎn)研究?jī)?nèi)容。