二次區域劃分的全覆蓋路徑規劃

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

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

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

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

1 全覆蓋路徑規劃流程

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

圖1 全覆蓋路徑規劃流程

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

2.1 區域劃分

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

2.2 四邊形網格劃分

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

圖2 四邊形網格劃分

(1)

式中：0表示未被覆蓋的元胞；1表示已經被覆蓋的元胞。

2.3 運動方向選擇

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

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

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

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

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

2)將按照優先級找出的相鄰元胞狀態值加1，更新當前元胞；

3)當所有元胞狀態值都為1時，停止演變；

4)當子區域發生變化時，對元胞重新初始化。

元胞自動機能夠很好地表述子區域中每一個需要遍歷的位置，并且可以知道當前所在位置的元胞狀態，能夠對子區域做到精確劃分，從而對所需要遍歷的區域進行全覆蓋規劃。

2.4 鄰接路徑

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

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

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

圖4 全覆蓋路徑規劃示意

3 對比驗證實驗

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

3.1 仿真實驗

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

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

圖5 小環境仿真實驗

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

圖6 有障礙物的中等環境仿真實驗

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

圖7 有不同大小物體的大環境仿真實驗

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

圖8 不規則環境仿真實驗

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

3.2 實驗對比

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

圖9 常見環境對比實驗

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

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

圖10 中央有物體環境對比實驗

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

表1 全覆蓋路徑規劃數據分析

3.3 實驗軌跡

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

圖11 實際運動軌跡

4 結論

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

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