韓國國，范柄堯

（1.山西天地王坡煤業(yè)有限公司，山西 晉城 043300；2.中國煤炭科工集團太原研究院，陜西 太原 030006）

1 前言

近年來，各大煤礦對井下安全生產(chǎn)的要求越來越高，設(shè)備自動化、智能化替代人力已成為重要的解決辦法。井下移動設(shè)備移動頻繁，一直以來都是安全生產(chǎn)的隱患，為保證移動設(shè)備的安全運行，確保人員及設(shè)備的安全，需要對可移動設(shè)備的運動規(guī)劃問題進行探討和研究。

移動設(shè)備包括綜采設(shè)備，連采設(shè)備和輔助運輸車輛和井下移動機器人，其中各大學(xué)者針對輔助運輸車輛和自主移動機器人在煤礦井下這一復(fù)雜環(huán)境下的運動規(guī)劃問題研究的較多，文獻[4]采用人工魚群算法對井下救援機器人進行路徑規(guī)劃，通過將環(huán)境模型中威脅區(qū)域距離檢測的與算法相結(jié)合，實現(xiàn)了在較短的時間內(nèi)得到目前環(huán)境下的最優(yōu)路徑。但是路徑點數(shù)量的選擇對算法效果的影響較大；文獻[5]通過改進人工勢場法對礦井中障礙物密集且移動較多的導(dǎo)航裝置進行路徑避障處理；文獻[6]通過局部到全局的梯度-坐標(biāo)輪換法進行煤礦搜救機器人最優(yōu)路徑規(guī)劃。另外，還有采用各類傳感器、視頻輔助等方法進行輔助運輸和避障處理，均取得了不錯的效果。本文主要采用差分進化算法針對輔助運輸車輛在煤礦井下這一復(fù)雜環(huán)境下的運動規(guī)劃問題進行探索。

差分進化(Differential Evolution，DE)算法是由Storn和Price提出的一種基于種群的智能優(yōu)化算法，該算法能夠用來解決連續(xù)領(lǐng)域的優(yōu)化問題。優(yōu)點是在全局、并行搜索過程中具有魯棒性強，操作原理簡單以及尋優(yōu)性能良好等，現(xiàn)在已經(jīng)成為進化領(lǐng)域的研究熱點。

鑒于差分進化算法在連續(xù)域的突出表現(xiàn)，本文將其用于解決煤礦井下可移動設(shè)備的無碰撞最短路徑規(guī)劃問題。

2 煤礦井下移動設(shè)備路徑規(guī)劃問題模型

針對煤礦井下可移動設(shè)備路徑規(guī)劃問題，設(shè)計使可移動設(shè)備從起始點到目標(biāo)點的路徑模型。本文將可移動設(shè)備縮小為一個質(zhì)點，將各個障礙物設(shè)置成不同半徑的圓，煤礦井下可移動設(shè)備運行的最短無碰撞路徑模型如下：

式中，f表示可移動設(shè)備運行的最短無碰撞路徑；設(shè)起始位置坐標(biāo)為目標(biāo)坐標(biāo)為x2，…xn為將x0和xn+1關(guān)于x軸n+1等分后的n個點，b為x0和xn+1的n+1等分值。y1，y2，…yn為x1，x2，…

xn所對應(yīng)的路徑點；考慮到相鄰兩路徑點連線可能與障礙物相交而形成不可行路徑，使用懲罰函數(shù)ωi處理這種情況。ε＞1為懲罰因子，可以使不可行路徑變長；表示障礙物k的圓心到相鄰兩路徑點yi yi-1所在直線的垂直距離；表示第k個障礙物的影響范圍，Rk為第k個障礙物的半徑，為一個較小的數(shù)；Sk表示線段yi yi-1是否與第k個障礙物相交，相交Sk=0，否則Sk=1。

3 基于差分進化算法的路徑規(guī)劃

3.1 種群初始化

差分進化算法的初始化種群設(shè)置如下為：

式中，NP為種群規(guī)模，D為維數(shù)。

3.2 變異操作

DE算法有很多變異策略，本文采用的變異方式為DE/rand/1，此變異操作具體是指在每一代種群中選擇三個互異的個體yr1,g、yr2,g和yr3,g，把其中兩個個體yr2,g和yr3,g進行差分處理并經(jīng)過縮放因子F( 1 0＜F＜ )縮放后，與第三個個體yr1,g相加得到變異向量vi,g，如式(6)所示。

3.3 交叉操作

本文采用二項式交叉方式進行操作，試驗向量中至少有一個分量由變異向量產(chǎn)生。具體操作如式（7）所示：

式中，j=1,2,…,D, CR∈(0,1)為交叉率，jrand為[1,D]內(nèi)隨機選擇的整數(shù)。

3.4 選擇操作

為產(chǎn)生下一代的目標(biāo)向量yi,g+1，根據(jù)目標(biāo)向量yi,g和試驗向量ui,g的適應(yīng)值f()?來選擇最優(yōu)個體，具體步驟如式(8)所示：

4 實驗仿真

4.1 環(huán)境參數(shù)設(shè)置

針對煤礦井下可移動設(shè)備無碰撞最短路徑規(guī)劃問題，本文將差分進化算法(DE/rand/1/bin)進行仿真實驗，為了保證試驗的公平性，針對算法的參數(shù)進行如下設(shè)置：

移動設(shè)備的環(huán)境條件設(shè)置如下：將移動設(shè)備在以下兩個環(huán)境中進行仿真試驗，其中環(huán)境1中有兩個障礙物，障礙物的情況如下：半徑都為1，坐標(biāo)原點分別為(-15，-10)、（15，10）的圓；環(huán)境2中有三個障礙物，障礙物的情況如下：半徑為1，坐標(biāo)原點分別為（20，5)、(-20，-5)和(0，0)的圓。

參數(shù)設(shè)置：針對差分進化算法，種群規(guī)模NP=15D，終止條件為，CR與F設(shè)置如下：CR=0.8，F(xiàn)min=0.1，F(xiàn)max=0.8。

通過差分進化算法完成移動設(shè)備的路徑規(guī)劃時，算法的每一次循環(huán)矩陣的維數(shù)D和可移動設(shè)備路徑點的數(shù)量有密切關(guān)系，本文使用不包括開始點和目標(biāo)點的路徑點n來表示數(shù)量(D=n)，由此得到本文的路徑點數(shù)量n和路徑點間隔d有關(guān)，關(guān)系式如下：

式中，x0為出發(fā)點橫坐標(biāo)，xn+1為目標(biāo)點橫坐標(biāo)。

4.2 實例分析

圖1為DE的最優(yōu)路徑，針對環(huán)境1和2，算法都能找到從開始點到目標(biāo)點的最短路徑。如圖1(a)、(b)所示，特別是針對環(huán)境2這種障礙物較多的情形，DE算法也能夠找到最短路徑。

圖1 最優(yōu)路徑圖

差分進化算法能夠針對不同環(huán)境和路徑點間隔得到到高質(zhì)量的解，是一種有效的路徑規(guī)劃方法。

5 結(jié)語

本文提出將差分進化算法用于解決煤礦井下可移動設(shè)備在復(fù)雜環(huán)境下的無碰撞最短路徑規(guī)劃問題。實驗結(jié)果顯示，差分進化算法可以獲得高質(zhì)量的解，有效解決煤礦井下可移動設(shè)備在復(fù)雜環(huán)境下的路徑尋優(yōu)問題。