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

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

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

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

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

1 環(huán)境建模

1.1 建立柵格地圖

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

1.2 區(qū)域分割

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

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

(1)

當在此空間中的任意一點p0滿足以下條件時：

(2)

則稱p0為臨界點。

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

2 算法設(shè)計

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

2.1 頭腦風暴(BSO)算法

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

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

2)對N個想法進行適應度值評價。

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

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

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

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

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

(3)

(4)

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

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

(5)

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

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

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

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

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

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

(6)

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

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

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

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

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

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

首先，生成隨機數(shù)r5∈(0,1)，將pe,ps,pi構(gòu)成行向量，對其橫向累加得到(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隨機將某子串中的個體依次向后(前)移位;倒位算子以概率pi隨機將某子串中的個體依次倒位;換位算子以概率pe隨機交換某位置的個體。

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

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

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

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

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

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

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

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

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

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

課題組利用BSO-GA算法規(guī)劃子區(qū)域內(nèi)部覆蓋路徑，而GA-SA融合算法由于模擬退火算法(simulated annealing,SA)的引入，能夠在一定程度上改善GA陷入局部最優(yōu)的缺陷。因此，將本文算法與BSO，GA，SA和GA-SA算法進行效果對比，以驗證本文融合算法的有效性?，F(xiàn)將各空閑柵格中心點看作目標點，對圖1(c)中9個區(qū)域進行內(nèi)部路徑規(guī)劃。以子區(qū)域⑦和⑧為例，分別運用往復法及優(yōu)化算法BSO，GA，SA，GA-SA，BSO-GA在普通環(huán)境區(qū)域⑦和特殊環(huán)境區(qū)域⑧(存在鋸齒障礙物、凹形障礙物)下進行全覆蓋路徑規(guī)劃。實驗環(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相應參數(shù)設(shè)置如表1所示。

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

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

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

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

再分別運用優(yōu)化算法BSO，SA，GA和GA-SA對子區(qū)域⑦和⑧進行覆蓋路徑規(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)較好，路徑交叉及重復現(xiàn)象也比較少，但其運行時間是BSO-GA算法的近30倍；當覆蓋面積較大時，BSO算法就顯現(xiàn)出收斂性較差的缺陷，出現(xiàn)了大量如圖3(a)所示的路徑冗余，自然距離大大增加；覆蓋面積較小時同樣出現(xiàn)了如圖3(b)所示路徑交叉現(xiàn)象；而GA算法總距離隨著迭代次數(shù)增加呈現(xiàn)階梯式下降，在收斂前出現(xiàn)了如圖4所示的2～3個平臺期，說明其易陷入局部最優(yōu)；由于SA算法每次循環(huán)僅對一個解實施擾動并更新，因此從圖4(a)中可以看出，當覆蓋面積較大時收斂速度較為緩慢。

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

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

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

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

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

4 結(jié)論

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

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