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

李燊

（沈陽新松機器人自動化股份有限公司，遼寧 沈陽 100169）

0 引言

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

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

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

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

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

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

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

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

1.1 路線生成

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

首先對柵格地圖進行預處理，即對柵格地圖邊界做封閉處理，并將障礙物以機器人半徑進行膨脹。

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

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

圖1 路線生成

1.2 子區(qū)域劃分

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

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

圖2 沿障礙物邊緣搜索

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

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

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

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

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

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

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

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

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

1.3 子區(qū)域的遍歷

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

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

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

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

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

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

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

2 結(jié)論

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