填埋場裸膜紅外巡檢機器人最優路徑規劃

孟彩茹， 杜金鵬， 張維民， 陳亞宇， 魏浩良

(河北工程大學機械與裝備工程學院， 邯鄲 056038)

目前，垃圾填埋場環境污染是制約中國生態發展的重要因素之一。在填埋場建設過程中，受多種因素影響，防滲層會產生不同程度的損傷，由于垃圾滲濾液中含有大量有毒污染物，一旦滲漏會對周圍土壤環境、水資源以及人體健康造成極大危害[1]。因此在填埋場建設初期做好裸膜檢測，發現破損并及時修復具有重要意義。傳統的人工巡檢方法效率低下且漏檢率高，已無法滿足檢測要求。本文基于紅外探傷理論采用紅外巡檢機器人代替人工完成巡檢，節省了大量人力物力。為了能有效提高巡檢效率，筆者對巡檢機器人全覆蓋路徑規劃算法展開研究。

在機器人路徑規劃方面，曹曉燕等[2]針對貨物運輸問題開發設計了基于遺傳算法的貨運路徑規劃系統，提高了貨運效率，但整體路徑規劃系統適用性低，性能不穩定；韓孟宜等[3]設計了混合遺傳算法，將遺傳算法與節約算法、鄰域搜索算法相結合，實現了應急物資快速配送，求解結果較標準遺傳算法更優，但其計算量大，路徑規劃耗時長；Di等[4]提出了采用神經網絡算法完成未知動態環境下移動機器人路徑規劃的方法，并用遺傳算法調整和訓練神經網絡，使機器人以較平滑的路徑實現高效率避障；吳飛龍等[5]將A*算法和動態窗口法相融合實現了實時動態避障，極大減少了路徑長度和機器人運行時間，但其不適用于全覆蓋路徑規劃；Li等[6]通過簡化信息素的存儲方法來改進蟻群算法；昝新宇等[7]根據路徑中多因素綜合指標分配信息素來改進蟻群算法，二者都有效提升了算法收斂速度和穩定性，但在初始信息素差別分布上考慮不足。

在對垃圾填埋場路徑規劃中，以上算法在局部區域覆蓋以及點到點的路徑轉移中有顯著效果，但因填埋場障礙分布的特殊性，這些算法雖能完成路徑規劃，但巡檢效率較低，易陷入局部最優。全覆蓋路徑規劃要求紅外巡檢機器人合理高效的遍歷垃圾填埋場內除障礙物以外的所有二維空間[8]。垃圾填埋場區域寬闊，各填埋單元都建有圓柱狀導氣石籠，用來導排垃圾陳化過程中產生的沼氣，屬于路徑規劃中的障礙物。垃圾填埋場最優巡檢路徑規劃，可簡化為性能評價函數最優值求解問題，主要包括：覆蓋面積百分率、重復覆蓋率和能量消耗等[9]。因此，現提出一種模板模型法與改進的遺傳算法相結合的全覆蓋路徑規劃模型，能有效提高機器人巡檢效率。

1 相關工作

對紅外巡檢機器人路徑規劃，要先了解所規劃的環境并對其建模；然后根據障礙物的分布對其進行區域分解，規劃分解后的各子區域遍歷方式；最后基于改進后的遺傳算法對垃圾填埋場完成全覆蓋路徑規劃。具體流程如圖1所示。

圖1 全覆蓋路徑規劃流程圖Fig.1 Flow chart of full coverage path planning

2 路徑規劃模型研究

2.1 環境建模

獲取垃圾填埋場場地形狀和各障礙物分布信息，建立相應環境模型。圖2為垃圾填埋場示意圖，黑色為障礙物，白色為可行域。

采用柵格法[10]對垃圾填埋場進行環境建模。規定紅外巡檢機器人檢測范圍與柵格大小相同，將垃圾填埋場分解為n×n柵格單元，建立一個n×n的二維矩陣，矩陣中的每一個元素代表一個柵格。如圖3所示。

圖2 填埋場示意圖Fig.2 Schematic diagram of landfill site

圖3 柵格地圖Fig.3 Grid map

2.2 區域分解

垃圾填埋場中各單元都設有導氣石籠，其分布較為規律整齊。為避免產生大量子區域造成路徑冗余，采用區域分解法中的矩形分解法對環境進行優化分解，將整個區域分解為較規則的矩形子區域，按照從左到右從上到下規則，依次對區域分塊編號，并用Q1,Q2,…,Q11表示，如圖4所示，垃圾填埋場區域分解后示意圖。

圖4 區域分解示意圖Fig.4 Schematic diagram of area decomposition

基于區域分解法的全覆蓋路徑規劃方法主要完成子區域內部遍歷和子區域間連接轉換工作[11]。

2.3 子區域遍歷

遍歷所有子區域就是對垃圾填埋場的全覆蓋。在子區域內部遍歷中，針對垃圾填埋場地形和障礙物分布，采用模板模型法定義機器人巡檢模式，用一系列模板模型規劃出覆蓋各子區域的路徑[12]。其核心模板模型有前行(towards marker，TM)，右轉(right turn,RT),左轉(left turn,LT)，U形轉彎(U turn,UT),躲避障礙(steer clear of obstacle,SCOO)，內螺旋(inside spin,IS),其具體巡檢模式如圖5所示。

對于無障礙物子區域，可以直接使用往復式遍歷法和螺旋法[13]，其具體模型如圖6所示。

圖6(a)為往復式遍歷模型，是一種階梯式遍歷方法，圖中黑點為起點和終點，首先確定紅外巡檢機器人起始位置和最初運動方向，以往復式運動方式遍歷該區域。圖6(b)為螺旋法中內螺旋模型，保證紅外巡檢機器人在該區域的邊沿位置起步，使其沿著該區域邊緣螺旋式的由外向內進行遍歷。這兩種方法都能對無障礙物區域實現高效全覆蓋。

對于存在障礙物的區域主要通過模板模型法中躲避障礙模型(SCOO)的行走方式來避障，經過環境建模和對填埋場的區域分解，障礙物都分布在各子區域邊界處，SCOO模式可以很好地完成避障。

圖5 模板示意圖Fig.5 Schematic diagram of formwork

圖6 傳統遍歷法Fig.6 Traditional traversal method

2.4 全區域覆蓋

在對垃圾填埋場區域分解和子區域遍歷方式確定后，規劃各子區域間連接路徑。研究基于遺傳算法的全覆蓋路徑規劃，找到各子區域間路徑轉移最優解，減少其重復覆蓋率和能耗。由于遺傳算法的萬向性，使得它比一般隨機搜索算法效率要高，且使用簡單、魯棒性強，對實際問題有高度適應性[14]。

2.4.1 遺傳算法基本原理

遺傳算法能實現優勝劣汰，可以使問題解逐代優化，逼近最優解。遺傳操作主要有選擇、交叉、變異，其中交叉和變異決定著整個算法的收斂速度和全局尋優能力[15]。其基本原理如圖7所示。

2.4.2 遺傳算法在路徑規劃中的實現

1)編碼

通過編碼將求解問題表示成遺傳空間的染色體或個體。各子區域間遍歷順序決定著路徑規劃的優劣，本文研究中采用排列編碼方式對各子區域遍歷順序進行編碼。染色體由頭部和主體兩部分組成，頭部表示各子區域間排列順序，主體表示各子區域內節點遍歷順序，由節點連線組成，如圖8所示。

2)初始種群的形成

傳統遺傳算法中初始種群一般隨機產生，這樣雖然簡單，但會消耗計算資源出現大量不可行路徑，且使算法收斂速度變慢。因此，初始路徑序列由相鄰子區域并根據啟發式最鄰近算法來生成，可以快速優化，加快收斂速度，而生成的初始路徑序列就是染色體的頭部。根據圖4各子區域的編號，生成大量初始路徑序列，具體如下。

head1:Q1,Q2,Q3,Q4,Q7,Q6,Q5,Q8,Q9,Q10,Q11；

head2:Q1,Q2,Q5,Q8,Q9,Q10,Q7,Q6,Q3,Q4,Q11。

3)適應度函數

適應度函數用來評價遺傳算法解的優劣，直接影響著遺傳算法的收斂速度和成敗，其值越大，解就越優。針對機器人巡檢路徑問題，適應度函數由總距離和總時長兩個約束條件組成。覆蓋總時長主要取決于機器人的轉彎次數，距離和時間值越大，適應度值越小，所以適應度函數為

(1)

式(1)中：c為調整常數，使適應度值保持在0～1，便于分析；∑dist和∑time分別為機器人行駛總距離和總時間，且∑dist>0，∑time>0；wdist和wtime分別為距離和時間的權重比例。

wdist+wtime=1

(2)

機器人對填埋場巡檢時，轉彎消耗時間和轉彎個數成正比，適應度函數也可表達為

(3)

式(3)中：∑turn為機器人總轉彎次數；wturn為轉彎的權重比例。根據垃圾填埋場地形和障礙物分布形勢，設定wdist=0.6，wturn=0.4是較為合理的。

4)選擇

選擇是以適應度為準則從群體中選擇優勝個體。將錦標賽選擇法和隨機遍歷選擇法相結合，以加快收斂速度和增強全局尋優能力。錦標賽法是從群體中選擇M個個體，選出其中適應度值最高的個體遺傳到下一代，重復此操作，使得適應值較好的個體有更大的“生存機會”。隨機遍歷選擇法要先計算個體被選中的概率，定義指針選擇距離，然后等距離選擇個體，對于不同適應值個體選擇機會相對均等。選擇步驟如下。

(1)設種群大小為N，以錦標賽的規則選出k個適應值最高的個體。

(2)根據隨機遍歷選擇法，計算第i條路徑被選中的概率，計算公式為

(4)

式(4)中：P(bi)為選中個體bi的概率；F(bi)為個體bi的適應度值。然后進行等距離選擇個體。

5)交叉和變異

交叉和變異是遺傳算法中的重要操作，交叉能產生大量新個體，決定整個算法的收斂速度;而變異對于產生新個體有輔助作用，影響算法的局部搜索能力[16]。

交叉操作中，要求其不能破壞表現優良個體，同時還可以有效產出較好的新個體。對交叉概率Pc進行模糊優化，使遺傳算法尋優性能更加，具體優化方式如下：前期交叉概率應小，以避免收斂速度過快；種群適應值方差較大時，增大交叉概率；種群適應值較為優良的則減小交叉概率；對于接近的高適應值個體和距離較遠的個體應施以較大的交叉概率。交叉概率Pc的一般取值范圍為0.25～0.75。

基于路徑規劃的交叉重組具體步驟如下。

(1)根據交叉概率選取k組適應值較大的染色體，即

k=PcGn

(5)

式(5)中：Gn為種群大小。隨后對k組染色體進行兩兩隨機配對。

(2)配對后，在[0,n]間生成一個隨機數，確定交叉點的位置。比如隨機數為6，則將在第6位進行交叉重組。

實際操作如下。

交叉前，head1:Q1,Q2,Q3,Q4,Q7,Q6(UT),Q5,Q8,Q9,Q10,Q11；head2:Q1,Q2,Q5,Q8,Q9,Q10(IS),Q7,Q6,Q3,Q4,Q11。

交叉后，head1:Q1,Q2,Q3,Q4,Q7,Q6(IS),Q5,Q8,Q9,Q10,Q11；head2:Q1,Q2,Q5,Q8,Q9,Q10(UT),Q7,Q6,Q3,Q4,Q11。

如果需要較大的交叉概率，可以適當增加交叉點的個數，配對的路徑序列可以同時對2或3個子區域進行交叉重組。

變異操作中，主要對群體中個體串基因進行改變。當遺傳算法通過交叉重組接近最優解領域時，可以利用變異操作的局部尋優能力加快算法收斂速度。變異概率Pm取值較小，根據實際情況對變異進行優化。

種群適應度值方差較大時應減小變異概率，可以保證算法穩定性；種群適應度值方差較小時應加大變異概率，可以加快淘汰劣質個體；種群適應值較高的個體應取較小的變異概率。變異概率一般為0.01～0.2。

基于路徑規劃的變異操作具體步驟為：①對群體中所有個體以事先設定的變異概率判斷是否進行變異；②選中的變異個體隨機選取兩個位置進行變異操作。比如隨機兩個位置是3和9，實際操作如下。

變異前，head3:Q1,Q11,Q10,Q9,Q8,Q5,Q2,Q3,Q4,Q7,Q6。

變異后，headnew3:Q1,Q11,Q4,Q9,Q8,Q5,Q2,Q3,Q10,Q7,Q6。

3 仿真

基于MATLAB對垃圾填埋場紅外巡檢機器人全覆蓋路徑規劃進行仿真，生成一條最優路徑，驗證所設計算法對實現路徑規劃的高效可行性。

仿真主要分為兩部分：第一部分要對填埋場環境采用柵格法進行仿真，處理成為31×31個柵格，如圖9所示，其中黑色柵格表示障礙物，白色柵格表示可行域。第二部分為繪制紅外巡檢機器人在地圖上的行走路徑。首先要對填埋場采用矩形分解法進行區域分解仿真，將整個區域分解為多個子區域，如圖10中藍色線為各子區域間邊界線；然后結合模板模型算法和改進的遺傳算法對整個區域進行全覆蓋路徑規劃。

圖9 地圖仿真Fig.9 Map simulation

遺傳算法中，種群大小為11的階乘，根據上述所提優化方法設定交叉概率為0.4、0.6、0.75，變異概率為0.1、0.2，經過迭代換算最終得出最優路徑，如圖10(a)所示，圖10(a)中綠色三角形符號為機器人行走的起點和終點。圖10(b)為普通遺傳算法對該環境的路徑仿真結果。

圖10 機器人行走路徑Fig.10 Robot walking path

由圖10可得改進算法的重復覆蓋率為1.21%，普通算法的重復覆蓋率為2.43%，改進算法的行走時間比普通算法的快1.14倍。較改進算法，普通算法規劃出的路徑重復覆蓋率較大，并且拐彎次數較多，耗費大量時間。

圖11為改進前后算法求最優解的收斂曲線，圖中可以看出兩個算法在開始時收斂都較快；改進算法在逐漸向最優靠近，普通算法會出現浮動，可能產生局部最優解；改進算法在迭代80次時趨于穩定，而普通算法則在迭代110次才趨于穩定，并且適應度值較改進算法低。結果表明所提算法對垃圾填埋場紅外巡檢機器人最優路徑規劃是可行有效的。

圖11 算法最優解收斂曲線Fig.11 Convergence curve of optimal solution of algorithm

4 結論

針對垃圾填埋場裸模滲漏檢測工作，提出采用紅外巡檢機器人代替人工完成巡檢任務，將全覆蓋路徑規劃運用到填埋場這個特殊環境中去。采用矩形分解法對整個區域進行分解，將模板模型法和改進的遺傳算法相結合構成一個成熟的全覆蓋路徑規劃模型，為機器人找到一條最優巡檢路徑。基于MATLAB仿真結果表明，所改進算法對尋找全覆蓋最優路徑有著顯著效果，且較普通算法有較快的收斂速度、較低的重復覆蓋率和能耗。其除卻文中所用領域亦可應用在智能機器人室內外清潔、礦區等地的全覆蓋采樣、工廠機器人智能運輸貨物等領域，且不會造成大量的路徑冗余和較高的重復覆蓋率，有較高的實用性。