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

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

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

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

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

1 相關(guān)工作

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

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

2 路徑規(guī)劃模型研究

2.1 環(huán)境建模

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

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

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

圖3 柵格地圖Fig.3 Grid map

2.2 區(qū)域分解

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

圖4 區(qū)域分解示意圖Fig.4 Schematic diagram of area decomposition

基于區(qū)域分解法的全覆蓋路徑規(guī)劃方法主要完成子區(qū)域內(nèi)部遍歷和子區(qū)域間連接轉(zhuǎn)換工作[11]。

2.3 子區(qū)域遍歷

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

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

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

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

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

圖6 傳統(tǒng)遍歷法Fig.6 Traditional traversal method

2.4 全區(qū)域覆蓋

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

2.4.1 遺傳算法基本原理

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

2.4.2 遺傳算法在路徑規(guī)劃中的實(shí)現(xiàn)

1)編碼

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

2)初始種群的形成

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

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)適應(yīng)度函數(shù)

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

(1)

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

wdist+wtime=1

(2)

機(jī)器人對填埋場巡檢時，轉(zhuǎn)彎消耗時間和轉(zhuǎn)彎個數(shù)成正比，適應(yīng)度函數(shù)也可表達(dá)為

(3)

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

4)選擇

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

(1)設(shè)種群大小為N，以錦標(biāo)賽的規(guī)則選出k個適應(yīng)值最高的個體。

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

(4)

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

5)交叉和變異

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

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

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

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

k=PcGn

(5)

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

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

實(shí)際操作如下。

交叉前，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。

如果需要較大的交叉概率，可以適當(dāng)增加交叉點(diǎn)的個數(shù)，配對的路徑序列可以同時對2或3個子區(qū)域進(jìn)行交叉重組。

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

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

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

變異前，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對垃圾填埋場紅外巡檢機(jī)器人全覆蓋路徑規(guī)劃進(jìn)行仿真，生成一條最優(yōu)路徑，驗(yàn)證所設(shè)計(jì)算法對實(shí)現(xiàn)路徑規(guī)劃的高效可行性。

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

圖9 地圖仿真Fig.9 Map simulation

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

圖10 機(jī)器人行走路徑Fig.10 Robot walking path

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

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

圖11 算法最優(yōu)解收斂曲線Fig.11 Convergence curve of optimal solution of algorithm

4 結(jié)論

針對垃圾填埋場裸模滲漏檢測工作，提出采用紅外巡檢機(jī)器人代替人工完成巡檢任務(wù)，將全覆蓋路徑規(guī)劃運(yùn)用到填埋場這個特殊環(huán)境中去。采用矩形分解法對整個區(qū)域進(jìn)行分解，將模板模型法和改進(jìn)的遺傳算法相結(jié)合構(gòu)成一個成熟的全覆蓋路徑規(guī)劃模型，為機(jī)器人找到一條最優(yōu)巡檢路徑?；贛ATLAB仿真結(jié)果表明，所改進(jìn)算法對尋找全覆蓋最優(yōu)路徑有著顯著效果，且較普通算法有較快的收斂速度、較低的重復(fù)覆蓋率和能耗。其除卻文中所用領(lǐng)域亦可應(yīng)用在智能機(jī)器人室內(nèi)外清潔、礦區(qū)等地的全覆蓋采樣、工廠機(jī)器人智能運(yùn)輸貨物等領(lǐng)域，且不會造成大量的路徑冗余和較高的重復(fù)覆蓋率，有較高的實(shí)用性。