二次區(qū)域劃分的全覆蓋路徑規(guī)劃

蔣林， 張燕飛， 馬先重， 朱建陽， 雷斌

(1.武漢科技大學(xué) 冶金裝備及其控制教育部重點實驗室，湖北 武漢 430081； 2.武漢科技大學(xué) 機器人與智能系統(tǒng)研究院，湖北 武漢 430081)

機器人作為近幾年人工智能領(lǐng)域的代表產(chǎn)物，已經(jīng)被應(yīng)用到各行各業(yè)。室內(nèi)移動機器人是機器人領(lǐng)域的一個大的分支，在生產(chǎn)生活中很常見。全覆蓋路徑規(guī)劃(complete coverage path planning, CCPP)[1-2]，即根據(jù)建圖中[3]獲取的先驗信息設(shè)計一條可以遍歷環(huán)境中所有區(qū)域的路徑，也就是常說的CCPP問題。CCPP算法作為室內(nèi)移動機器人研究的重要組成部分，國內(nèi)外專家學(xué)者對其研究已有很多，但也存在一些不足。

全覆蓋路徑規(guī)劃算法主要分為3種：傳統(tǒng)法、柵格法和單元分解法。傳統(tǒng)法主要分為3類：弓字形方法[4-5]、回字形方法[6-8]以及模板法[9]，雖然傳統(tǒng)法簡單易實行，但是會出現(xiàn)路徑冗余，覆蓋率低,容易陷入死區(qū)等問題。Le等[1]提出的基于螺旋生成樹的規(guī)劃算法，其降低了遍歷重疊度，但規(guī)劃的路徑轉(zhuǎn)彎次數(shù)變多，路徑距離變長。Choset[10]提出通過單元分解法[11]得到全覆蓋路徑，其降低了規(guī)劃的難度，但是需要考慮分解方法、鄰接圖建立以及子區(qū)域全覆蓋如何選擇的問題。針對子區(qū)域覆蓋率低，李楷等[12]提出基于回溯法進行全覆蓋規(guī)劃，具有運行效率高、重復(fù)率低的優(yōu)點，但是回溯機制建立困難。謝坤霖等[13]提出子區(qū)域分解結(jié)合啟發(fā)式搜索算法的全覆蓋路徑規(guī)劃算法，解決了高重復(fù)率、復(fù)雜路徑尋路效率低等問題，但對于不規(guī)則障礙物周圍會出現(xiàn)盲區(qū)，導(dǎo)致部分區(qū)域無法清潔，并且評價函數(shù)選取困難。Zelinsky等[14]提出將柵格法與距離轉(zhuǎn)換法結(jié)合，實現(xiàn)全覆蓋全局路徑規(guī)劃，但該算法會使計算量增加且重復(fù)率高。梁嘉俊等[15]提出一種改進的勢場柵格算法，解決了路徑的計算復(fù)雜度高這一問題，但是對于大環(huán)境所規(guī)劃出的路徑效果差，覆蓋率較低。趙慧南等[16]提出基于柵格法的全覆蓋路徑規(guī)劃方法，該算法能夠防止機器人陷入死區(qū)并能夠有效避開障礙物，但算法復(fù)雜，計算量大。劉晶等[17]提出結(jié)合A*的生物激勵路徑搜索算法，降低路徑重復(fù)率，使機器人可以脫離死區(qū)，但該算法增加了計算量并且需要建立移動規(guī)則。雖然上述算法都能實現(xiàn)室內(nèi)移動機器人全覆蓋路徑規(guī)劃的功能，但是仍存在一些不足，因此本文提出室內(nèi)移動機器人基于區(qū)域二次劃分的全覆蓋路徑規(guī)劃算法，通過得到子區(qū)域，然后利用元胞自動機原理對子區(qū)域進行二次劃分，得到子區(qū)域的覆蓋路徑，建立鄰接路徑，從而完成整個地圖的規(guī)劃路徑。

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

室內(nèi)移動機器人基于區(qū)域二次劃分的全覆蓋路徑規(guī)劃算法，首先判斷所獲得的室內(nèi)環(huán)境地圖中間是否存在占據(jù)的物體，根據(jù)環(huán)境的差異采用不同區(qū)域劃分算法對地圖進行區(qū)域劃分，得到不同大小相鄰的子區(qū)域。然后將子區(qū)域二次劃分，利用元胞自動機原理對子區(qū)域進行四邊形網(wǎng)格劃分，得到子區(qū)域的網(wǎng)格圖，定義元胞和相鄰元胞集合模型，制定演化規(guī)則，確定移動機器人的運動方法，從而得到子區(qū)域的覆蓋路徑。根據(jù)子區(qū)域的劃分順序，連接當(dāng)前子區(qū)域的起點元胞和相鄰子區(qū)域的終點元胞得到相鄰子區(qū)域的連接路徑，從而完成整個地圖的規(guī)劃路徑。本文算法流程如圖1所示。在室內(nèi)移動機器人實際運動過程中，移動機器人根據(jù)所規(guī)劃的全覆蓋路徑運動，不斷發(fā)布元胞位置，機器人自動調(diào)用局部路徑規(guī)劃器進行局部導(dǎo)航，使得機器人根據(jù)規(guī)劃好的路線去遍歷一個個元胞空間，從而完成室內(nèi)移動機器人全覆蓋路徑規(guī)劃的功能。

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

2 基于二維元胞自動機的子區(qū)域二次分解

2.1 區(qū)域劃分

首先判斷建立的環(huán)境地圖內(nèi)部是否有障礙物或者其他物體占據(jù)內(nèi)部空間，若地圖內(nèi)部被占據(jù)，則采用線掃分割法(boustrophedon cellular decomposition, BCD)[18-19]對區(qū)域分解；若地圖中間沒有障礙物，則采用相鄰分解法。針對環(huán)境地圖不同的情況采用不同的區(qū)域劃分方式，能夠更為準(zhǔn)確地劃分地圖中的區(qū)域，從而提高全覆蓋路徑規(guī)劃的覆蓋能力。

2.2 四邊形網(wǎng)格劃分

為了保證全覆蓋路徑規(guī)劃的區(qū)域覆蓋率，需要對區(qū)域劃分得到的子區(qū)域進行二次劃分。元胞自動機[20]是在一個元胞狀態(tài)有限并且處于離散元胞空間，其在時間、空間、狀態(tài)上都是離散的。對于移動機器人模型來說，其運動在二維空間，對于二維空間來說，常用的網(wǎng)格劃分方式有三角形、四邊形以及六邊形網(wǎng)格劃分。三角形網(wǎng)格相鄰元胞較少而六邊形網(wǎng)格存在計算機難以表達的問題，所以對于子區(qū)域二次劃分，本文采用的四邊形網(wǎng)格劃分，其相鄰元胞較多便于表達機器人的運動方向，并且四邊形網(wǎng)格便于存儲和操作。如圖2所示，對于已經(jīng)劃分好的子區(qū)域，本文采用四邊形網(wǎng)格繼續(xù)劃分，劃分好的一個個小四邊形也就是元胞。元胞的狀態(tài)值可以描述當(dāng)前元胞是否被移動機器人遍歷，相鄰元胞集合可以描述移動機器人的運動方向。四邊形網(wǎng)格劃分能夠保證子區(qū)域中所有位置被遍歷。

圖2 四邊形網(wǎng)格劃分

(1)

式中：0表示未被覆蓋的元胞；1表示已經(jīng)被覆蓋的元胞。

2.3 運動方向選擇

移動機器人運動方向由相鄰元胞集合模型決定，相鄰元胞集合模型主要分為馮·諾依曼(Von.Neuman)型、馬哥勒斯(Margolus neighborhoods)型和摩爾(Moore)型。Von.Neuman型相鄰元胞集合模型機器人只能在上、下、左、右4個方向上移動，不符合移動機器人運動規(guī)則，也不利于移動機器人進行全覆蓋路徑規(guī)劃。而Margolus型相鄰元胞集合模型每次將一個2×2的元胞塊做統(tǒng)一處理，不符合移動機器人實際運動。因此，本算法采用Moore型領(lǐng)域描述室內(nèi)移動機器人運動方向，Moore型相鄰元胞集合模型將當(dāng)前元胞左、左上、上、右上、右、右下、下、左下8個方向上對應(yīng)的相鄰元胞設(shè)為領(lǐng)域，即機器人可以向這個8個方向任意移動，

每一個元胞中心位置也就是室內(nèi)移動機器人全覆蓋路徑規(guī)劃中的子路徑點，在移動機器人實際運動過程中可以作為導(dǎo)航點使用，并且元胞的邊長略小于機器人直徑D，即R

圖3 Moore型相鄰元胞集合模型

利用Moore型相鄰元胞集合模型得到移動機器人可移動的8個運動方向，本文算法按照上、左、右、下、左上、右上、右下、左下的運動順序建立優(yōu)先級，按照優(yōu)先級選擇下一個要遍歷的元胞。并以子區(qū)域的左上角的頂點元胞中心位置為起點，開始對子區(qū)域中的所有元胞進行遍歷，當(dāng)子區(qū)域被覆蓋完之后，子區(qū)域的元胞狀態(tài)值發(fā)生變化，元胞自動機變?yōu)槠椒€(wěn)型，即子區(qū)域的每一個元胞處于固定狀態(tài)，不隨時間變化而變化。在機器人整個運動方向選擇過程中元胞自動機的演化規(guī)則為：

1)中心元胞狀態(tài)等于1時，按照優(yōu)先級找出一個相鄰元胞狀態(tài)值為0的鄰居；

2)將按照優(yōu)先級找出的相鄰元胞狀態(tài)值加1，更新當(dāng)前元胞；

3)當(dāng)所有元胞狀態(tài)值都為1時，停止演變；

4)當(dāng)子區(qū)域發(fā)生變化時，對元胞重新初始化。

元胞自動機能夠很好地表述子區(qū)域中每一個需要遍歷的位置，并且可以知道當(dāng)前所在位置的元胞狀態(tài)，能夠?qū)ψ訁^(qū)域做到精確劃分，從而對所需要遍歷的區(qū)域進行全覆蓋規(guī)劃。

2.4 鄰接路徑

對于子區(qū)域的鄰接路徑，現(xiàn)有研究大部分采用貪心算法根據(jù)當(dāng)前情況選取局部最優(yōu)解，即終點與最近子區(qū)域的起點的連線為貪心算法所得到的鄰接路徑。但這種算法鄰接路徑較長，所得到的路徑只考慮當(dāng)前，并不能照顧到全局，從而會增加路徑長度。根據(jù)本文算法劃分的子區(qū)域索引來看，索引相鄰的子區(qū)域距離近，鄰接路徑不會出現(xiàn)穿過其他子區(qū)域的情況。所以按照子區(qū)域的劃分順序，將相鄰子區(qū)域進行連接，即將前一子區(qū)域的終點與當(dāng)前子區(qū)域的起點直接相連得到子區(qū)域鄰接路徑。用貪心算法和本文算法對圖2進行全覆蓋路徑規(guī)劃，得到如圖4的路徑。

從圖4中可以看出，利用貪心算法所得到的鄰接路徑長度較長，規(guī)劃混亂，并且會增加計算量，導(dǎo)致規(guī)劃時間過長。而按照本文所提算法得到的路徑長度較短，子區(qū)域連接規(guī)整，并且降低了計算復(fù)雜度。

如圖4所示，子區(qū)域2的終點和子區(qū)域3的起點連接的路徑直接穿過障礙物，室內(nèi)移動機器人在實際中是無法運動的。所以對于這種情況下，機器人在實際運動過程中采用導(dǎo)航點的發(fā)布，按照子區(qū)域的遍歷順序，逐步發(fā)布子區(qū)域中每一個元胞的中心位置給移動機器人，機器人按照所規(guī)劃的全覆蓋路徑進行運動。在相鄰2個子區(qū)域之間，終點與起點之間移動機器人自動調(diào)用機器人的路徑規(guī)劃器進行本地實時路徑規(guī)劃[21]，從而規(guī)劃出一條連接相鄰子區(qū)域無碰撞的路徑。在實際運動過程中，本文采用Trajectory Rollout算法對2個子區(qū)域的鄰接路徑進行規(guī)劃，該算法能夠使機器人躲避障礙物，并以一個較快的速度向目標(biāo)位置運動。Trajectory Rollout算法通過對機器人當(dāng)前的速度和角度采樣，針對每個采樣，計算軌跡，通過評價函數(shù)對軌跡打分，選出最優(yōu)路徑。Trajectory Rollout算法能夠使機器人躲避障礙物，并以一個較快的速度向目標(biāo)位置運動。

圖4 全覆蓋路徑規(guī)劃示意

3 對比驗證實驗

為了驗證本文所提算法的可行性和實用性，利用ROS系統(tǒng)下的RVIZ仿真軟件進行了4組仿真實驗驗證算法的可行性和實用性，并通過2組對比實驗驗證所提算法的優(yōu)越性。本文采用Rviz顯示室內(nèi)場景環(huán)境以及全覆蓋路徑規(guī)劃所規(guī)劃的路徑。系統(tǒng)仿真所用計算機為聯(lián)想E540筆記本，CPU為i5 4210M，采用Turtlebot機器人進行仿真。

3.1 仿真實驗

本文在不同大小，不同構(gòu)造的環(huán)境中共做了4組仿真實驗： 1)中間無障礙物的小環(huán)境，環(huán)境大小為7.164 m×9.580 m；2)中間有障礙物的中等環(huán)境，環(huán)境大小為20.140 m×35.142 m；3)中間有障礙物的大環(huán)境，環(huán)境大小為53.540 m×79.042 m；4)中間有障礙物的不規(guī)則環(huán)境，環(huán)境大小為10.157 m×10.201 m。

小環(huán)境如圖5所示，在中間無障礙物的環(huán)境下，利用本文所提算法對環(huán)境進行全覆蓋路徑規(guī)劃。首先判斷所給環(huán)境地圖，室內(nèi)無中間物體，采用相鄰分解法將該環(huán)境分解為3個子區(qū)域，再利用元胞自動機原理對子區(qū)域進行二次劃分，并得到覆蓋路徑，最后建立子區(qū)域之間的連接，得到全覆蓋路徑。從圖5可以看出根據(jù)本文所提算法能對無障礙物的小環(huán)境進行全覆蓋路徑規(guī)劃，從而證明本文所提算法的可行性和實用性。如果像素值變化，則說明地圖內(nèi)部有物體占據(jù)的情況。

圖5 小環(huán)境仿真實驗

如圖6所示在中間有2個障礙物的中等環(huán)境下，內(nèi)部障礙物大小分別為4.986 m×4.450 m和7.232 m×6.659 m。利用BCD算法將其分為7個子區(qū)域，并且通過元胞自動機實現(xiàn)子區(qū)域的覆蓋路徑，最終得到如圖8所示的全覆蓋路徑。從圖6中可以看出，對所給中等面積的室內(nèi)環(huán)境本文算法可以很好地完成全覆蓋路徑規(guī)劃，覆蓋率高。

圖6 有障礙物的中等環(huán)境仿真實驗

在圖7所示的大環(huán)境中，中間有部分環(huán)境被不同大小的物體占據(jù)，中間物體的大小分別為8.450 m×12.278 m和16.210 m×37.696 m。利用本文算法將該環(huán)境分成不同的子區(qū)域，再對子區(qū)域進行覆蓋規(guī)劃，從而得到如圖7所示的路徑。從圖7中可以看出，本文算法對中間有不同大小的物體占據(jù)的大環(huán)境同樣適用，并且不受室內(nèi)環(huán)境地圖大小的影響，從而證明本文算法的可行性。

圖7 有不同大小物體的大環(huán)境仿真實驗

如圖8所示，該地圖環(huán)境內(nèi)部有不規(guī)則物體，并且環(huán)境墻體為鋸齒狀，環(huán)境并不規(guī)整。利用本文所提算法對該環(huán)境進行區(qū)域劃分，劃分為6個子區(qū)域，分別對子區(qū)域進行覆蓋路徑規(guī)劃得到如圖8所示的全覆蓋路徑。從圖8中可以看出本文所提算法可適用于不規(guī)則的環(huán)境，并且在有不規(guī)整物體的環(huán)境下同樣適用。

圖8 不規(guī)則環(huán)境仿真實驗

機器人室內(nèi)環(huán)境地圖一般都是由一個個單通道的像素點組成的。從上面4組實驗中可以看出該算法在不同大小、不同形狀的環(huán)境中都能對其進行子區(qū)域劃分、子區(qū)域二次劃分、子區(qū)域路徑覆蓋，并且能夠?qū)Νh(huán)境100%覆蓋。并且根據(jù)路徑規(guī)劃圖可以看出所提算法的可行性和實用性。

3.2 實驗對比

為了證明所提算法的高效性，本文采用2組對比實驗進行驗證。對比算法分別為：相鄰分解法、元胞自動機以及柵格法，實驗對比環(huán)境如圖9和圖10所示。圖9環(huán)境的大小為7.464 m×9.580 m，環(huán)境中出現(xiàn)的墻體長度為4.848 m；圖10環(huán)境的大小為6.280 m×8.713 m，中間占據(jù)的物體大小為1.212 m×1.212 m。

圖9 常見環(huán)境對比實驗

常見環(huán)境如圖9(a)所示，在同一環(huán)境采用不同的算法對其進行全覆蓋路徑規(guī)劃，圖9(a)相鄰分解法將該環(huán)境分為5個子區(qū)域，子區(qū)域連接路徑長度20.755 m，轉(zhuǎn)彎次數(shù)為104次；圖9(b)利用元胞自動機進行覆蓋得到的路徑轉(zhuǎn)彎次數(shù)為46次，路徑重復(fù)率較高，雖然能夠得到全覆蓋路徑，但路徑遍歷混亂并且產(chǎn)生12.587 m的重復(fù)路徑；圖9(c)中柵格轉(zhuǎn)折次數(shù)高達235次，遍歷路徑變長，從而消耗機器人大量的能量；圖9(d)中本文算法將環(huán)境劃分為3個子區(qū)域，轉(zhuǎn)彎次數(shù)34次，子區(qū)域連接路徑較短，路徑長度僅為11.495 m。從實驗結(jié)果來看，本文所提算法與其他對比算法具有轉(zhuǎn)折次數(shù)少，覆蓋效率高，遍歷重疊度低的優(yōu)點。

中間有物體占據(jù)的環(huán)境如圖10所示，在同一環(huán)境進行全覆蓋路徑規(guī)劃。采用不同的算法進行實驗：圖10(a)使用相鄰分解法將該環(huán)境分為5個子區(qū)域，子區(qū)域連接路徑長度為31.336 m，轉(zhuǎn)彎次數(shù)為156次，并且從圖10中可以看出將2個子區(qū)域誤劃分成同一子區(qū)域，規(guī)劃路徑效率差；圖10(b)利用元胞自動機進行全覆蓋路徑規(guī)劃所得到的路徑轉(zhuǎn)彎次數(shù)為76次，路徑重復(fù)率較高，盡管得到了全覆蓋路徑，但路徑遍歷混亂且遍歷路徑長度加長，還產(chǎn)生了12.472 m的重復(fù)路徑；圖10(c)柵格法轉(zhuǎn)折次數(shù)高達102次，遍歷總路徑變長，從而消耗機器人大量的能量；圖10(d)中使用本文算法將環(huán)境劃分為4個子區(qū)域，轉(zhuǎn)彎次數(shù)為90次，子區(qū)域連接路徑較短，路徑長度為12.783 m。從實驗結(jié)果看，本文所提算法減少路徑冗余、降低重復(fù)率、減少轉(zhuǎn)彎次數(shù)、覆蓋率高。

圖10 中央有物體環(huán)境對比實驗

通過對比實驗數(shù)據(jù)，如表1所示，可以發(fā)現(xiàn)相鄰分解法由中間物體的環(huán)境無法準(zhǔn)確劃分子區(qū)域，會對子區(qū)域進行錯誤規(guī)劃，并且子區(qū)域連接路徑長，轉(zhuǎn)彎次數(shù)較多。利用元胞自動機所規(guī)劃的全覆蓋路徑規(guī)劃混亂，會產(chǎn)生冗余路徑，不符合機器人的實際運動規(guī)律。柵格法轉(zhuǎn)彎次數(shù)最多，路徑總長度最長，機器人會消耗大量的能量，而本文所提算法子區(qū)域連接路徑較短，轉(zhuǎn)彎次數(shù)少，并且覆蓋率高。通過對比分析可知，本文雖然增加了少部分的連接路徑，但降低了轉(zhuǎn)彎次數(shù)，減少了機器人的能量消耗，規(guī)劃路徑規(guī)整，遍歷重疊度低，覆蓋率高，相比其他算法，更有優(yōu)勢。

表1 全覆蓋路徑規(guī)劃數(shù)據(jù)分析

3.3 實驗軌跡

在移動機器人實際運動中，按照子區(qū)域遍歷順序，機器人對子區(qū)域的每一個元胞進行遍歷。當(dāng)遇到2個子區(qū)域的鄰接路徑時，移動機器人自動進行局部路徑規(guī)劃，從而規(guī)劃出一條連接相鄰子區(qū)域無碰撞的全覆蓋路徑。選取2種不同環(huán)境地圖進行移動機器人全覆蓋路徑規(guī)劃，機器人實際運動軌跡圖如圖11所示。從圖11中可以看出環(huán)境中的子區(qū)域逐一被遍歷，并且按照機器人的局部路徑規(guī)劃器的Trajectory Rollout算法選取相鄰子區(qū)域之間的最優(yōu)路徑，得到如圖11的鄰接路徑，鄰近路徑會根據(jù)機器人實際運動而改變。從實驗軌跡圖來看，本文所提算法具有實用價值。

圖11 實際運動軌跡

4 結(jié)論

1)本文提出的基于二次區(qū)域劃分的全覆蓋路徑規(guī)劃算法，通過得到子區(qū)域，然后利用元胞自動機原理對子區(qū)域進行二次劃分，得到子區(qū)域的覆蓋路徑，建立鄰接路徑，從而完成整個地圖的規(guī)劃路徑。

2)通過多組實驗結(jié)果證明本文所提算法具有可行性和實用性，與相鄰分解法、元胞自動機和柵格法相比，降低了遍歷重疊度，減少了轉(zhuǎn)彎次數(shù)，增加了覆蓋率。