基于BSO-GA算法的機(jī)器人子區(qū)域覆蓋路徑規(guī)劃

董雅文，楊靜雯*，劉文慧，張寶鋒

(1.西安工程大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710048；2.西安理工大學(xué) 機(jī)械與精密儀器工程學(xué)院，陜西 西安 710048)

隨著信息化、工業(yè)化的不斷融合，機(jī)器人等智能化設(shè)備得到了越來越廣泛的應(yīng)用，路徑規(guī)劃作為機(jī)器人的關(guān)鍵技術(shù)之一，深刻影響著機(jī)器人的作業(yè)質(zhì)量和作業(yè)效率。路徑規(guī)劃一般可分為傳統(tǒng)點(diǎn)到點(diǎn)式路徑規(guī)劃以及全覆蓋式路徑規(guī)劃。點(diǎn)到點(diǎn)路徑規(guī)劃是最常見、最基本的路徑規(guī)劃問題，它需要在作業(yè)空間中尋找從起點(diǎn)到終點(diǎn)的一條無碰撞最優(yōu)或較優(yōu)路徑；全覆蓋式路徑規(guī)劃則要求機(jī)器人在作業(yè)空間中尋找一條經(jīng)過封閉區(qū)域中所有可達(dá)區(qū)域的路徑，同時(shí)某些性能達(dá)到最優(yōu)或較優(yōu)。目前，全覆蓋式路徑規(guī)劃已應(yīng)用到了很多領(lǐng)域，如機(jī)器人清潔、噴涂、消毒、排雷和探傷檢測(cè)等。

整體而言，與傳統(tǒng)點(diǎn)到點(diǎn)路徑規(guī)劃問題相比，針對(duì)全覆蓋式路徑規(guī)劃問題的研究相對(duì)較少，但近些年來全覆蓋式路徑規(guī)劃逐漸成為研究熱點(diǎn)。目前針對(duì)全覆蓋式路徑規(guī)劃的研究主要集中在4個(gè)方面：①以神經(jīng)網(wǎng)絡(luò)作為切入點(diǎn)研究的全覆蓋路徑規(guī)劃，如運(yùn)用生物激勵(lì)神經(jīng)網(wǎng)絡(luò)及各種改進(jìn)算法[1-5]、具有長(zhǎng)短期記憶層的卷積神經(jīng)網(wǎng)絡(luò)[6]等來規(guī)劃覆蓋路徑；②基于區(qū)域分割的全覆蓋路徑規(guī)劃，主要探討子區(qū)域覆蓋的路徑規(guī)劃、遍歷順序的確定和銜接路線規(guī)劃問題；③從環(huán)境建模著手來提高全覆蓋效率，如對(duì)柵格添加屬性值[7]及運(yùn)用正六邊形柵格建模[8]等；④在機(jī)器人全覆蓋行進(jìn)過程中制定一系列規(guī)則及策略進(jìn)而達(dá)到提高覆蓋率、降低遺漏率的目的，如回溯機(jī)制[9]、分治思想[10]、阿基米德螺線走法[11]和沿邊學(xué)習(xí)機(jī)制[12]等。其中，針對(duì)基于區(qū)域分割的全覆蓋路徑規(guī)劃問題，周利坤等[13]運(yùn)用區(qū)域分割法進(jìn)行環(huán)境建模，各區(qū)域內(nèi)部采用內(nèi)螺旋法覆蓋，最后以鄰接矩陣和深度優(yōu)先搜索(depth first search,DFS)確定油泥區(qū)的銜接順序和最短路徑，完成油泥區(qū)的覆蓋。該方法能夠以較高覆蓋率和較低重復(fù)率來完成油泥區(qū)的覆蓋任務(wù)，但各子區(qū)域內(nèi)部采用內(nèi)螺旋法覆蓋，在面對(duì)不規(guī)則的分區(qū)環(huán)境時(shí)，會(huì)產(chǎn)生較多冗余路徑。馬全坤等[14]在用矩形分割創(chuàng)建環(huán)境模型后，通過記憶模擬退火算法搜索出任務(wù)最優(yōu)目標(biāo)點(diǎn)行走順序，然后使用A*算法進(jìn)行跨區(qū)域銜接路徑規(guī)劃。研究結(jié)果表明，重復(fù)率控制在4.2%左右，且遍歷路徑規(guī)劃能夠達(dá)到100%；但在子區(qū)域內(nèi)部行走陷入死區(qū)時(shí)，往復(fù)式覆蓋并不能有效逃離。李楷[15]針對(duì)子區(qū)域存在鋸齒形障礙物的情況提出了起始點(diǎn)方向優(yōu)先(starting point direction first,SPDF)局部區(qū)域覆蓋方法，研究結(jié)果表明，與局部區(qū)域覆蓋(boustrophedon cellular decomposition,BCD)算法相比，SPDF局部區(qū)域覆蓋算法首次覆蓋百分比平均值提高了近20%；但當(dāng)環(huán)境出現(xiàn)多種類型障礙物時(shí)，該方法不能有效應(yīng)對(duì)。張赤斌等[16]采用Boustrophedon分解進(jìn)行區(qū)域分割，各子區(qū)域內(nèi)部采用往復(fù)式覆蓋，利用蟻群算法進(jìn)行區(qū)域遍歷順序優(yōu)化，研究結(jié)果表明，遍歷順序?qū)θ采w效率有著重要的影響，但該方法并不能達(dá)到100%覆蓋的效果。唐東林等[17]運(yùn)用矩形分割法創(chuàng)建環(huán)境模型，將往復(fù)式覆蓋與路徑選擇函數(shù)相結(jié)合，研究結(jié)果表明此方法能夠有效逃離死區(qū)，但不能有效規(guī)劃凹形障礙物周圍覆蓋路徑。郭典新等[18]針對(duì)割草機(jī)器人全覆蓋路徑規(guī)劃問題，在完成單元分割創(chuàng)建環(huán)境模型后，采用改進(jìn)的往復(fù)式和回行式覆蓋，依據(jù)地塊形狀規(guī)劃其覆蓋路徑，研究結(jié)果表明該方法能有效減少重、漏作業(yè)現(xiàn)象，但該方法并未考慮障礙物較為復(fù)雜的情況。

目前，基于區(qū)域分割的全覆蓋路徑規(guī)劃的研究較多文獻(xiàn)仍采用傳統(tǒng)方法來規(guī)劃區(qū)域內(nèi)部覆蓋路徑，而傳統(tǒng)方法對(duì)環(huán)境普遍適應(yīng)性較差。課題組在完成環(huán)境建模和區(qū)域分割后，采用頭腦風(fēng)暴-遺傳融合算法(brain storm optimization -genetic algorithm，BSO-GA)對(duì)子區(qū)域內(nèi)部進(jìn)行全覆蓋路徑規(guī)劃。利用優(yōu)化算法規(guī)劃全覆蓋路徑，一定程度上避免現(xiàn)有方法適應(yīng)性不強(qiáng)的問題；同時(shí)BSO算法中引入GA變異操作的思想，能夠提高算法的隨機(jī)性和收斂速度，使其能夠較好地完成作業(yè)。

1 環(huán)境建模

1.1 建立柵格地圖

課題組運(yùn)用柵格法創(chuàng)建作業(yè)環(huán)境模型，柵格大小由機(jī)器人作業(yè)范圍決定。每個(gè)柵格包含3種狀態(tài)：空閑、完全占據(jù)和部分占據(jù)。對(duì)于完全或部分被障礙物占據(jù)的柵格都視為障礙區(qū)域；對(duì)于完全處于空閑狀態(tài)的柵格視為自由區(qū)域。

1.2 區(qū)域分割

區(qū)域分割是將復(fù)雜的作業(yè)環(huán)境依據(jù)障礙物的分布情況劃分為多個(gè)子區(qū)域，使得各子區(qū)域內(nèi)部不再包含障礙物。這種化整為零的思想在很大程度上降低了機(jī)器人全覆蓋路徑規(guī)劃的實(shí)現(xiàn)難度。區(qū)域劃分與后續(xù)子區(qū)域覆蓋規(guī)劃的優(yōu)劣也有著密切聯(lián)系。課題組采用莫爾斯分解[19]對(duì)作業(yè)區(qū)域進(jìn)行劃分，它不僅能夠處理多邊形障礙物的環(huán)境劃分，而且分解完成之后的子區(qū)域較少，可以減少機(jī)器人路徑冗余，進(jìn)而降低能耗、節(jié)省時(shí)間。

莫爾斯分解是一種基于臨界點(diǎn)分析的精確單元分割法，通過構(gòu)造莫爾斯函數(shù)進(jìn)行切片掃描來劃分區(qū)域。莫爾斯函數(shù)是定義在k維空間的可導(dǎo)函數(shù)。對(duì)于一個(gè)莫爾斯函數(shù)h:Rk→R，其在任一點(diǎn)p的一階導(dǎo)數(shù)為：

(1)

當(dāng)在此空間中的任意一點(diǎn)p0滿足以下條件時(shí)：

(2)

則稱p0為臨界點(diǎn)。

切片是根據(jù)確定的莫爾斯函數(shù)定義的一個(gè)覆蓋空間的余維數(shù)流形[20]，其形狀取決于所選的莫爾斯函數(shù)，并能夠產(chǎn)生不同的單元分割形式。當(dāng)切片掃過目標(biāo)區(qū)域遇到障礙物時(shí)，會(huì)把空間區(qū)域分割成更小的切片。當(dāng)切片離開障礙物時(shí)，一些小切片會(huì)聚合起來。這些區(qū)域聚合性發(fā)生變化的點(diǎn)是障礙物的臨界點(diǎn)。莫爾斯函數(shù)依據(jù)作業(yè)環(huán)境靈活選取。

2 算法設(shè)計(jì)

子區(qū)域內(nèi)部覆蓋路徑規(guī)劃常用的方法是往復(fù)式覆蓋法和螺旋式覆蓋法，但這類方法在環(huán)境中存在鋸齒形、凹形障礙物以及起始點(diǎn)不固定等情況時(shí)，不能做出有效應(yīng)對(duì)。針對(duì)上述問題，課題組采用優(yōu)化算法來完成子區(qū)域內(nèi)部的覆蓋，使其在一般和特殊環(huán)境下都可以有效完成作業(yè)。課題組以各柵格中心點(diǎn)為目標(biāo)，機(jī)器人成功遍歷各中心點(diǎn)至少一次則代表完成該柵格的覆蓋?？紤]到遍歷點(diǎn)數(shù)過多，依據(jù)區(qū)域劃分結(jié)果對(duì)各目標(biāo)點(diǎn)進(jìn)行分組，這樣能夠很大程度上縮小搜索空間，進(jìn)而將此問題轉(zhuǎn)化為旅行商問題進(jìn)行求解。旅行商求解的最短路徑即為子區(qū)域內(nèi)部的較優(yōu)路徑。

2.1 頭腦風(fēng)暴(BSO)算法

頭腦風(fēng)暴優(yōu)化(brain storm optimization，BSO)算法由SHI[21]于2011年提出，其主要思想源于多人集思廣益商討并解決問題。BSO算法根據(jù)頭腦風(fēng)暴的過程引出了4個(gè)操作過程，即初始化全部個(gè)體、聚類、新想法生成和想法選擇，主要步驟有6個(gè)。

1)初始化參數(shù)及全部想法。在BSO中將獨(dú)立個(gè)體稱為想法，首先模擬頭腦風(fēng)暴過程中每一輪產(chǎn)生N個(gè)想法。

2)對(duì)N個(gè)想法進(jìn)行適應(yīng)度值評(píng)價(jià)。

3)對(duì)N個(gè)想法進(jìn)行聚類。通過聚類算法將其劃分為M組，通過排序的方式選出最優(yōu)想法(組中心個(gè)體)。為保持種群多樣性，生成隨機(jī)數(shù)r1∈(0,1)，若r1

4)產(chǎn)生新想法為BSO的核心部分。產(chǎn)生新想法主要有2個(gè)階段，即選擇和更新。

第1階段為選擇。首先按照概率值pb先選擇基于1組或2組產(chǎn)生新想法;其次按照概率值pc,pd再選擇是基于組中心還是基于組內(nèi)隨機(jī)個(gè)體產(chǎn)生新想法。具體過程為：①生成隨機(jī)數(shù)r2∈(0,1)，若r2

第2階段為更新，更新想法的方式有2種:

①選擇1個(gè)想法(組中心想法或組內(nèi)隨機(jī)想法)作為Xs,對(duì)Xs進(jìn)行擾動(dòng)生成新想法，則有

(3)

(4)

式中：itermax為最大迭代次數(shù)；iternow為當(dāng)前迭代次數(shù)；k用來控制logsig函數(shù)的變化速率；rrand為服從(0,1)均勻分布的隨機(jī)數(shù)。

②選擇2個(gè)想法(2個(gè)組中心想法或2個(gè)組內(nèi)隨機(jī)想法)作Xs1，Xs2混合可得：

(5)

6)若達(dá)到設(shè)定的最大迭代次數(shù)，則輸出結(jié)果；若還未達(dá)到，則跳轉(zhuǎn)至1)。

BSO算法與其他模仿生物遺傳和覓食等群體行為的優(yōu)化算法不同，它通過模擬人類交流溝通解決問題，能夠在全局搜索和局部搜索之間達(dá)到較好的平衡，即采用數(shù)據(jù)分析將想法分組集合，組內(nèi)搜索各自解空間中的局部最優(yōu)解，然后經(jīng)過組之間的交流溝通來得到全局最優(yōu)解。同時(shí)，個(gè)體經(jīng)更新操作進(jìn)一步豐富了種群的多樣性，這使其在求解優(yōu)化問題中表現(xiàn)出了良好的性能。

2.2 頭腦風(fēng)暴-遺傳(BSO-GA)融合算法

BSO個(gè)體通過式(3)和式(5)進(jìn)行更新的方式在解決本文問題時(shí)適用性不強(qiáng)，易陷入局部最優(yōu)，收斂性較差。因此，課題組引入遺傳算法(genetic algorithm,GA)對(duì)個(gè)體實(shí)施變異，即倒位、移位和換位產(chǎn)生子代的思想，將其作為BSO基于1個(gè)想法更新的方式，并借鑒文獻(xiàn)[22]提出的改進(jìn)交叉操作，采用基于2個(gè)想法的貪心交叉完成混合產(chǎn)生新想法，主要有6個(gè)步驟。

1)初始化BSO和GA算法參數(shù)及全部想法。如BSO種群數(shù)N、最大迭代次數(shù)Gmax、聚類數(shù)M和選擇1個(gè)聚類概率、GA換位概率pe、移位概率ps和倒位概率pi等。接下來則按照種群數(shù)N隨機(jī)生成初始想法。

2)適應(yīng)度評(píng)價(jià)。對(duì)于本文中所要解決的全覆蓋路徑規(guī)劃問題，只需機(jī)器人在子區(qū)域內(nèi)行走路徑最短即可。這里采用Euclidean距離表示行走路徑長(zhǎng)度L，適應(yīng)度函數(shù)為:

(6)

式中：n表示子區(qū)域內(nèi)部需要遍歷點(diǎn)的數(shù)量;(xi,yi)表示各點(diǎn)坐標(biāo)。

3)對(duì)N個(gè)想法進(jìn)行聚類。采用K-Means算法將其分為M組，根據(jù)pa判斷組中心是否會(huì)被隨機(jī)產(chǎn)生想法取代。

相關(guān)統(tǒng)計(jì)顯示，急性腎衰傷的發(fā)生率在5%到20%左右，手術(shù)是引起急性腎衰傷的主要因素，其中心胸外科，心內(nèi)科以及神經(jīng)外科發(fā)生急性腎衰傷的概率相對(duì)較高，急性腎衰傷在臨床中具有較高的病死率，通常病死率將超過30%[2] 。

4)產(chǎn)生新想法。第1階段已在2.1節(jié)進(jìn)行了相關(guān)說明，故此不再贅述。經(jīng)選擇后，對(duì)其進(jìn)行更新。

在本研究中，解空間為解的所有排列順序集合，可表示為：

S={(s1,s2,…,sn)|(s1,s2,…,sn)為子區(qū)域內(nèi)部需要遍歷點(diǎn)(1,2,…,n)的循環(huán)排列}。

首先，生成隨機(jī)數(shù)r5∈(0,1)，將pe,ps,pi構(gòu)成行向量，對(duì)其橫向累加得到(pe,pe+ps，pe+ps+pi)，分別判斷r5與pe,pe+ps,pe+ps+pi的大小，找到首先滿足“≥r5”關(guān)系的位置，若pe≥r5，執(zhí)行交換算子；若pe+ps≥r5，執(zhí)行移位算子；若pe+ps+pi≥r5，執(zhí)行倒位算子。

其中：移位算子以概率ps隨機(jī)將某子串中的個(gè)體依次向后(前)移位;倒位算子以概率pi隨機(jī)將某子串中的個(gè)體依次倒位;換位算子以概率pe隨機(jī)交換某位置的個(gè)體。

②若Xs1,Xs2為組中心想法或組內(nèi)隨機(jī)想法，對(duì)Xs進(jìn)行貪心交叉操作實(shí)現(xiàn)更新。

a)隨機(jī)生成起點(diǎn)如a=s3，分別在Xs1,Xs2中搜尋s3的左鄰，分別為s2,s4，根據(jù){s3,s2},{s3,s4}距離大小決定下一點(diǎn)，若{s3,s2}距離小，則Xs11第2位為s2。

b)將s3從Xs1,Xs2中剔除，再次隨機(jī)生成起始點(diǎn)b=s5，在Xs1,Xs2搜尋s5的左鄰，為s6,s4，根據(jù){s5,s6},{s5,s4}距離大小決定下一點(diǎn)，依此類推，直至Xs1中只剩下一個(gè)元素。此時(shí)，可以得到Xs11。

c)同理，通過搜尋右鄰可以得到Xs22。

5)想法選擇。生成新想法Xn后，若Xn比Xs適應(yīng)度值更優(yōu)，那么將其替換。

6)判斷是否滿足終止條件，若滿足，迭代結(jié)束；否則，跳轉(zhuǎn)至3)繼續(xù)循環(huán)，直至滿足條件為止。

3 基于BSO-GA算法的子區(qū)域覆蓋路徑規(guī)劃仿真

通過莫爾斯分解將作業(yè)區(qū)域進(jìn)行分割，然后運(yùn)用BSO-GA算法完成子區(qū)域覆蓋，為驗(yàn)證該方法的有效性，通過消毒機(jī)器人對(duì)門診大廳進(jìn)行作業(yè)來完成實(shí)驗(yàn)仿真。設(shè)定消毒機(jī)器人的作業(yè)范圍為1 m×1 m，即柵格大小為1 m×1 m，門診大廳面積為400 m2，那么柵格數(shù)為20×20。首先模擬作業(yè)環(huán)境進(jìn)行環(huán)境建模，結(jié)果如圖1(a)所示。

圖1 環(huán)境建模Figure 1 Environment modeling

得出作業(yè)環(huán)境柵格模型后，依據(jù)環(huán)境模型特點(diǎn)，選取莫爾斯函數(shù)為直線簇{yp=ypi|ypi∈[0,20]}對(duì)作業(yè)區(qū)域進(jìn)行掃描，以區(qū)域④～⑥為例，現(xiàn)有4條直線Ⅰ～Ⅳ，如圖1(b)所示Ⅰ和Ⅱ間的直線未被障礙物分割，因此，默認(rèn)分段數(shù)為1，即Ⅰ和Ⅱ間區(qū)域?yàn)?個(gè)子區(qū)域；Ⅱ和Ⅲ間直線被分為3段，即Ⅱ和Ⅲ間區(qū)域被分割成3個(gè)子區(qū)域；Ⅲ和Ⅳ間直線分段數(shù)為1，自由區(qū)域的連通性發(fā)生了改變，可得臨界點(diǎn)為兩障礙物的8個(gè)頂點(diǎn)。因此，當(dāng)直線Ⅰ掃過作業(yè)區(qū)域時(shí)，可得出Ⅱ和Ⅲ間有3個(gè)子區(qū)域，完成區(qū)域分割。同理可得經(jīng)掃描后，共9個(gè)子區(qū)域，如圖1(c)所示。

課題組利用BSO-GA算法規(guī)劃子區(qū)域內(nèi)部覆蓋路徑，而GA-SA融合算法由于模擬退火算法(simulated annealing,SA)的引入，能夠在一定程度上改善GA陷入局部最優(yōu)的缺陷。因此，將本文算法與BSO，GA，SA和GA-SA算法進(jìn)行效果對(duì)比，以驗(yàn)證本文融合算法的有效性?，F(xiàn)將各空閑柵格中心點(diǎn)看作目標(biāo)點(diǎn)，對(duì)圖1(c)中9個(gè)區(qū)域進(jìn)行內(nèi)部路徑規(guī)劃。以子區(qū)域⑦和⑧為例，分別運(yùn)用往復(fù)法及優(yōu)化算法BSO，GA，SA，GA-SA，BSO-GA在普通環(huán)境區(qū)域⑦和特殊環(huán)境區(qū)域⑧(存在鋸齒障礙物、凹形障礙物)下進(jìn)行全覆蓋路徑規(guī)劃。實(shí)驗(yàn)環(huán)境為MATLAB R2016b，5種算法種群規(guī)模均設(shè)為50，迭代次數(shù)為1 000。SA算法的T0=0.025，α=0.99，內(nèi)層循環(huán)次數(shù)為15；GA算法的pc=0.8,pm=0.2;BSO-GA相應(yīng)參數(shù)設(shè)置如表1所示。

表1 BSO-GA算法參數(shù)設(shè)定Table 1 Parameters setting of BSO-GA algorithm

分別將子區(qū)域⑦和⑧局部放大并提取各中心點(diǎn)，運(yùn)用BSO-GA算法進(jìn)行路徑規(guī)劃，結(jié)果如圖2所示。

由圖2(a)和(c)可以看出，所有柵格(中心點(diǎn))均覆蓋，覆蓋率為100%，且無路徑重復(fù)及交叉現(xiàn)象。圖2(b)在100代左右總距離收斂至79.00 m并趨于穩(wěn)定，圖2(d)在50代左右收斂至28.83 m并趨于穩(wěn)定。并將其分別運(yùn)行20次，總距離均能收斂至79.00和28.83 m，平均用時(shí)26和19 s?？梢钥闯鼍哂休^強(qiáng)的穩(wěn)定性及良好的全局收斂性。

圖2 BSO-GA規(guī)劃路徑結(jié)果Figure 2 Path planning results of BSO-GA

再分別運(yùn)用優(yōu)化算法BSO，SA，GA和GA-SA對(duì)子區(qū)域⑦和⑧進(jìn)行覆蓋路徑規(guī)劃，結(jié)果如表2和圖3所示。

表2 仿真結(jié)果Table 2 Simulation results

圖3 其他優(yōu)化算法規(guī)劃路徑結(jié)果Figure 3 Path planning results of other optimization algorithms

由圖3、圖4和表2可得，無論是在一般環(huán)境還是特殊環(huán)境下，GA-SA算法在BSO，SA，GA，GA-SA 這4種算法中表現(xiàn)較好，路徑交叉及重復(fù)現(xiàn)象也比較少，但其運(yùn)行時(shí)間是BSO-GA算法的近30倍；當(dāng)覆蓋面積較大時(shí)，BSO算法就顯現(xiàn)出收斂性較差的缺陷，出現(xiàn)了大量如圖3(a)所示的路徑冗余，自然距離大大增加；覆蓋面積較小時(shí)同樣出現(xiàn)了如圖3(b)所示路徑交叉現(xiàn)象；而GA算法總距離隨著迭代次數(shù)增加呈現(xiàn)階梯式下降，在收斂前出現(xiàn)了如圖4所示的2～3個(gè)平臺(tái)期，說明其易陷入局部最優(yōu)；由于SA算法每次循環(huán)僅對(duì)一個(gè)解實(shí)施擾動(dòng)并更新，因此從圖4(a)中可以看出，當(dāng)覆蓋面積較大時(shí)收斂速度較為緩慢。

圖4 總迭代曲線Figure 4 Total iteration curve

運(yùn)用傳統(tǒng)往復(fù)法規(guī)劃路徑結(jié)果如圖5所示。往復(fù)法默認(rèn)上、下、左、右4個(gè)行駛方向?yàn)榍斑M(jìn)方向，由圖5(a)可知，在一般環(huán)境中，該方法能夠很好地完成覆蓋任務(wù)，但由于環(huán)境存在凹形障礙物，圖5(b)中出現(xiàn)了遺漏點(diǎn)A，并且機(jī)器人在行走至B時(shí)陷入死點(diǎn)(上、下、左、右均為已完成覆蓋區(qū)域或障礙區(qū)域)，由于未能有效脫困，從而導(dǎo)致了圖5(b)右下方6個(gè)遺漏點(diǎn)；當(dāng)從右邊界開始往復(fù)覆蓋時(shí)，同樣由于存在鋸齒形障礙物，出現(xiàn)圖5(c)的遺漏點(diǎn)F，凹形障礙物內(nèi)部的3個(gè)點(diǎn)C,D,E也為遺漏狀態(tài)。由此可見，往復(fù)法在規(guī)劃路徑時(shí)，易出現(xiàn)遺漏及陷入死點(diǎn)的情況。綜上，無論是與所列優(yōu)化算法相比，還是與傳統(tǒng)往復(fù)法相比，本文方法在解決子區(qū)域內(nèi)部覆蓋路徑規(guī)劃問題時(shí)表現(xiàn)較好且適應(yīng)性較強(qiáng)。

圖5 往復(fù)法規(guī)劃路徑結(jié)果Figure 5 Results of path planning by reciprocating method

現(xiàn)運(yùn)用BSO-GA算法對(duì)所有區(qū)域進(jìn)行路徑規(guī)劃，結(jié)果如圖6所示，子區(qū)域①～⑨行走距離分別1.48，11.41，59.00，9.00，54.00，9.00，79.00，28.83和28.83 m；規(guī)劃時(shí)間分別為12.3，11.0，30.7，9.7，30.2，9.8，26.0，19.0和12.2 s，將其累加得到整個(gè)區(qū)域行走距離共為280.55 m，時(shí)間共為160.9 s。由圖6可知，本文方法所得路徑?jīng)]有交叉重復(fù)、遺漏及陷入死點(diǎn)的情況，在距離和時(shí)間上均占據(jù)優(yōu)勢(shì)，且覆蓋率能夠達(dá)到100%，可以較好的完成覆蓋任務(wù)。

圖6 各子區(qū)域內(nèi)部覆蓋路徑Figure 6 Internal coverage path of sub-area

4 結(jié)論

課題組針對(duì)基于區(qū)域分割的全覆蓋路徑規(guī)劃問題進(jìn)行了一定的探索，在完成環(huán)境建模及區(qū)域分割后，提出了BSO-GA算法，有效克服了傳統(tǒng)方法存在的問題。結(jié)果表明，無論在普通還是特殊的作業(yè)環(huán)境中，與其他優(yōu)化算法相比，BSO-GA算法在距離、運(yùn)行時(shí)間上均占據(jù)一定優(yōu)勢(shì)，能夠較好地完成覆蓋作業(yè)。

相關(guān)有待深入研究的問題：①尋找精確度更高的環(huán)境建模及區(qū)域分割方法；②規(guī)劃覆蓋路徑時(shí)將路線轉(zhuǎn)角作為約束考慮，或同傳統(tǒng)方法結(jié)合，進(jìn)一步提高覆蓋方法的效率；③以最短路徑銜接各區(qū)域模塊是下一步需要關(guān)注的問題；④由于優(yōu)化算法的隨機(jī)性導(dǎo)致最優(yōu)路徑一致性不大，因此，如何依據(jù)作業(yè)環(huán)境選取最滿意路徑也是需要關(guān)注的問題。