基于BSO-GA算法的機器人子區域覆蓋路徑規劃

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

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

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

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

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

1 環境建模

1.1 建立柵格地圖

課題組運用柵格法創建作業環境模型，柵格大小由機器人作業范圍決定。每個柵格包含3種狀態：空閑、完全占據和部分占據。對于完全或部分被障礙物占據的柵格都視為障礙區域；對于完全處于空閑狀態的柵格視為自由區域。

1.2 區域分割

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

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

(1)

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

(2)

則稱p0為臨界點。

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

2 算法設計

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

2.1 頭腦風暴(BSO)算法

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

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

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

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

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

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

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

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

(3)

(4)

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

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

(5)

6)若達到設定的最大迭代次數，則輸出結果；若還未達到，則跳轉至1)。

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

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

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

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

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

(6)

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

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

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

4)產生新想法。第1階段已在2.1節進行了相關說明，故此不再贅述。經選擇后，對其進行更新。

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

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

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

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

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

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

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

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

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

6)判斷是否滿足終止條件，若滿足，迭代結束；否則，跳轉至3)繼續循環，直至滿足條件為止。

3 基于BSO-GA算法的子區域覆蓋路徑規劃仿真

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

圖1 環境建模Figure 1 Environment modeling

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

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

表1 BSO-GA算法參數設定Table 1 Parameters setting of BSO-GA algorithm

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

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

圖2 BSO-GA規劃路徑結果Figure 2 Path planning results of BSO-GA

再分別運用優化算法BSO，SA，GA和GA-SA對子區域⑦和⑧進行覆蓋路徑規劃，結果如表2和圖3所示。

表2 仿真結果Table 2 Simulation results

圖3 其他優化算法規劃路徑結果Figure 3 Path planning results of other optimization algorithms

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

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

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

圖5 往復法規劃路徑結果Figure 5 Results of path planning by reciprocating method

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

圖6 各子區域內部覆蓋路徑Figure 6 Internal coverage path of sub-area

4 結論

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

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