蔣林， 張燕飛， 馬先重， 朱建陽(yáng)， 雷斌

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

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

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

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

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

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

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

2.1 區(qū)域劃分

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

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

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

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

(1)

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

2.3 運(yùn)動(dòng)方向選擇

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

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

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

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

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

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

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

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

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

2.4 鄰接路徑

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

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

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

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

3 對(duì)比驗(yàn)證實(shí)驗(yàn)

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

3.1 仿真實(shí)驗(yàn)

本文在不同大小，不同構(gòu)造的環(huán)境中共做了4組仿真實(shí)驗(yàn)： 1)中間無(wú)障礙物的小環(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所示，在中間無(wú)障礙物的環(huán)境下，利用本文所提算法對(duì)環(huán)境進(jìn)行全覆蓋路徑規(guī)劃。首先判斷所給環(huán)境地圖，室內(nèi)無(wú)中間物體，采用相鄰分解法將該環(huán)境分解為3個(gè)子區(qū)域，再利用元胞自動(dòng)機(jī)原理對(duì)子區(qū)域進(jìn)行二次劃分，并得到覆蓋路徑，最后建立子區(qū)域之間的連接，得到全覆蓋路徑。從圖5可以看出根據(jù)本文所提算法能對(duì)無(wú)障礙物的小環(huán)境進(jìn)行全覆蓋路徑規(guī)劃，從而證明本文所提算法的可行性和實(shí)用性。如果像素值變化，則說(shuō)明地圖內(nèi)部有物體占據(jù)的情況。

圖5 小環(huán)境仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)對(duì)比

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

圖9 常見(jiàn)環(huán)境對(duì)比實(shí)驗(yàn)

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

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

圖10 中央有物體環(huán)境對(duì)比實(shí)驗(yàn)

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

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

3.3 實(shí)驗(yàn)軌跡

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

圖11 實(shí)際運(yùn)動(dòng)軌跡

4 結(jié)論

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

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