煤礦救援機器人路徑規(guī)劃的蟻群優(yōu)化算法

郭 泰，顏 鋌

(重慶應(yīng)用技術(shù)職業(yè)學(xué)院，重慶 401520)

煤礦作業(yè)具有潛在危險性，利用機器人代替人類進入礦井危險區(qū)域采集信息，可保障煤礦井下作業(yè)安全性，為煤礦救援決策提供有效依據(jù)[1]。煤礦井下作業(yè)電氣設(shè)備需為滿足嚴格要求與規(guī)定的高防爆設(shè)備，煤礦救援機器人安全性需高于煤礦井下設(shè)備安全性能[2]。應(yīng)用于煤礦井下救援的儀器設(shè)備應(yīng)為隔爆型。煤礦救援機器人井下作業(yè)時，地理環(huán)境復(fù)雜，容易由于碰撞破壞其隔爆性能，形成煤塵火花等造成礦井二次垮塌、引爆水、火、障礙物等爆炸等二次災(zāi)害。煤礦救援機器人應(yīng)用于礦井作業(yè)中時，應(yīng)避開水、火、障礙物等危險區(qū)域[3]。研究煤礦救援機器人路徑規(guī)劃問題，可令煤礦救援機器人充分發(fā)揮其作用。規(guī)劃煤礦救援機器人行駛路徑時，應(yīng)充分考慮礦井所具有的復(fù)雜環(huán)境，避開水、火、障礙物等危險區(qū)域，尋找無障礙最優(yōu)路徑[4-5]。煤礦救援機器人路徑規(guī)劃問題屬于多障礙、高信息量的多約束問題，采用傳統(tǒng)尋優(yōu)算法容易造成求解陷入局部最優(yōu)，無法獲取最優(yōu)全局規(guī)劃路徑。

目前針對機器人路徑規(guī)劃研究較多，徐梁等[6-8]分別利用改進ACO、粒子群算法以及負反饋機制應(yīng)用于路徑規(guī)劃中，可有效獲取路徑規(guī)劃的全局最優(yōu)解，但存在計算過于復(fù)雜的缺陷，為此提出了煤礦救援機器人路徑規(guī)劃的蟻群優(yōu)化算法，該算法利用蟻群優(yōu)化算法獲取煤礦救援機器人路徑規(guī)劃的最優(yōu)解，障礙物分布密集區(qū)域仍可保持最優(yōu)路徑規(guī)劃結(jié)果。通過實例分析驗證所研究算法具有較高的全局路徑規(guī)劃有效性，礦井的復(fù)雜環(huán)境下仍具有極高的路徑規(guī)劃能力，可快速獲取無障礙物、避開水、火、障礙物等分布的最短路徑，規(guī)劃性能優(yōu)越。

1 蟻群優(yōu)化算法

1.1 環(huán)境建模與問題描述

用規(guī)格為r×r的正方形區(qū)域表示煤礦救援機器人尺寸，設(shè)救援機器人規(guī)劃空間為包含眾多大小為r×r的柵格組成，編號全部柵格建立柵格化地圖模型。標(biāo)記規(guī)劃空間中柵格為障礙柵格以及自由柵格[9]，當(dāng)水、火、障礙物等分布占有柵格部分或全部以及完全不包含水、火、障礙物等分布時，分別用障礙柵格g∈O以及自由柵格表示。設(shè)規(guī)劃空間大小為R×C，ng表示柵格編號，(xg，yg)表示柵格坐標(biāo)，可得表達式：

(1)

式中，「?為取整符號；mod為求余符號。

可得柵格內(nèi)煤礦救援機器人路徑規(guī)劃問題目標(biāo)函數(shù)：

(2)

(3)

式中，T為目標(biāo)柵格；N(g)為柵格g的鄰域；S為柵格g起點柵格；q為最優(yōu)路徑中柵格數(shù)量；dgigi+1為柵格gi與gi+1間的中心距離。

1.2 確定煤礦救援機器人可行駛路徑

煤礦救援機器人可行駛路徑數(shù)量用表示，確定可行駛路徑可提升路徑搜索速度[10]，避免局部優(yōu)化問題，機器人可行駛路徑：

(4)

式中，stal(i)為起點的聚度；m為移動障礙物數(shù)量；r為可繞過移動障礙物的路徑數(shù)量；al為條路徑中障礙物數(shù)量。

存在數(shù)量為m的障礙物分布于數(shù)量為r的道路中時，可得該路徑上障礙物數(shù)量共m/r個。將起點i的聚度轉(zhuǎn)化為：

(5)

數(shù)量為m的障礙物集中于其中一條路徑時，可將聚度公式轉(zhuǎn)化為：

(6)

利用式(6)獲取最大可能聚度值。

1.3 傳統(tǒng)蟻群算法

煤礦救援機器人從i處移動至j處時，做出定義：時間為t時，蟻群在位置i與j處留下的信息濃度用殘留信息量ij(t)表示，di，j為2點間距用表示，τ為處于[0，1]的揮發(fā)因子。利用以下公式調(diào)整蟻群迭代一次后不同路徑上信息濃度：

τi，j(t+1)=ρτi，j(t)+Δτi，j

(7)

式中，ρ為信息素保留率；Δτi，j為蟻群經(jīng)過此條路徑時所增加的信息濃度，其計算公式：

(8)

螞蟻k經(jīng)過節(jié)點i與節(jié)點j時，可得公式：

(9)

式中，Q為常數(shù)；Lk為螞蟻k所經(jīng)過路徑總長度。

螞蟻k由位置i移動至位置j的概率公式為：

(10)

螞蟻k從i處移動到j(luò)處可視程度公式：

(11)

式中，allowed為蟻群可行駛路徑集，螞蟻k行走的全部節(jié)點均存儲于該集合中時，表示螞蟻k實現(xiàn)一次迭代，此時煤礦救援機器人完成一次可行路徑選取[11]；α為路徑的信息濃度；β為啟發(fā)式因子重要性；η為啟發(fā)因子。

1.4 蟻群優(yōu)化算法

1.4.1 改進信息素規(guī)則

采用蟻群算法搜索最優(yōu)路徑時，利用調(diào)節(jié)不同路徑信息素聚集蟻群至最優(yōu)路徑附近，通過信息素更新規(guī)則改進[12]，同時提升以及降低螞蟻行駛于最優(yōu)路徑以及最差路徑的信息素濃度，令蟻群快速獲取最優(yōu)路徑。信息素規(guī)則改進公式：

(12)

式中，τnew為信息素揮發(fā)系數(shù)；ρ為新路徑信息素；τold為原路徑信息素；δ為調(diào)節(jié)因子；Dbest為最優(yōu)解；Dworst為最差解。

通過以上過程改進信息素更新規(guī)則，令迭代過程中可較大概率遍歷最優(yōu)路徑[13]，縮小煤礦救援機器人路徑規(guī)劃搜索范圍，提升蟻群優(yōu)化算法獲取最優(yōu)解效率。

1.4.2 限制信息素閾值

信息素閾值限制形式：

(13)

式中，τi，j為節(jié)點i至j的信息素；τmin為最小信息素；τmax為最大信息素。

通過以上過程限制，信息素位于[τmin，τmax]，可保障所獲取的信息素變化于合理范圍內(nèi)，避免信息素?zé)o窮大或無窮小[14]，限制最優(yōu)路徑以及最差路徑中信息素濃度差異。

1.4.3 改進轉(zhuǎn)移概率

改進蟻群算法中的啟發(fā)因子，提升算法獲取最優(yōu)解概率[15]，定義優(yōu)化后啟發(fā)因子公式：

(14)

式中，djEnd為柵格節(jié)點j至終點間距，其公式：

(15)

式中，(xj，yj)為節(jié)點坐標(biāo)值；(xEnd，yEnd)為終點坐標(biāo)值。

優(yōu)化所獲取啟發(fā)因子ηjEnd越小，表示被選中該柵格節(jié)點j概率越高。

將隨機選擇參數(shù)r0加入算法中，利用多樣性的解提升算法全局尋優(yōu)能力。r∈(0，1)與r0∈(0，1)分別為隨機數(shù)以及隨機選擇參數(shù)，當(dāng)r

(16)

(17)

式中，t為時間變量；s為可行走柵格節(jié)點。

2 實例分析

選取某煤礦規(guī)格為80 m×4 m的巷道進行實驗。礦井下部分區(qū)域分布有水、火、障礙物等，巷道下所分布水、火、障礙物等均低于5%，未存在超標(biāo)情況。為保障煤礦救援機器人安全行駛，設(shè)置煤礦內(nèi)水、火、障礙物等高于3%的區(qū)域為機器人行駛危險區(qū)域。充分考慮煤礦巷道內(nèi)的水、火等分布以及巨石、土堆等障礙物，建立實驗區(qū)域巷道環(huán)境模型如圖1所示。

從圖1實驗結(jié)果可以看出，本文算法可有效依據(jù)煤礦的礦井巷道環(huán)境建立環(huán)境模型。所建立環(huán)境模型有效考慮水、火、障礙物等分布情況，并將巨石、土堆等障礙物均建立于模型環(huán)境中，提升煤礦救援機器人路徑規(guī)劃的行駛安全性。

實驗設(shè)置機器人起點與終點坐標(biāo)分別為(5，0.5)、(80，10)。選取ACO算法(參考文獻[6])、粒子群算法(參考文獻[7])以及負反饋算法(參考文獻[8])作為對比算法，不同算法搜尋機器人行駛最優(yōu)路徑時收斂曲線如圖2所示。由圖2實驗結(jié)果可以看出，采用本文算法規(guī)劃煤礦救援機器人行駛最優(yōu)路徑，僅需20次左右即可快速獲取最優(yōu)解，算法步入平穩(wěn)趨勢；ACO算法、粒子群算法以及負反饋算法搜尋機器人最優(yōu)行駛路徑時，均需要80次以上收斂曲線趨于穩(wěn)定。對比結(jié)果說明，本文算法采用蟻群優(yōu)化算法具有較高的收斂性能，可快速搜尋煤礦救援機器人最優(yōu)行駛路徑。

圖2 收斂曲線對比

采用4種算法規(guī)劃煤礦救援機器人最優(yōu)行駛路徑結(jié)果如圖3所示。

由圖3實驗結(jié)果可以看出，采用不同算法均可有效獲取煤礦救援機器人最優(yōu)行駛路徑。本文算法所獲取機器人最優(yōu)行駛路徑可有效避免水、火等分布以及巨石、土堆等障礙物；ACO算法、粒子群算法以及負反饋算法雖同樣可以獲取機器人最優(yōu)行駛路徑，但僅可躲避巨石等障礙物，未考慮水、火、障礙物等分布情況。煤礦救援機器人行駛于礦井巷道中，容易由于碰撞火花與水、火、障礙物等接觸出現(xiàn)二次爆炸等嚴重情況，本文算法所獲取機器人最優(yōu)行駛路徑有效躲避水、火、障礙物等分布區(qū)域，提升煤礦救援機器人行駛安全性。

統(tǒng)計采用本文算法規(guī)劃煤礦救援機器人行駛路徑的最優(yōu)路徑長度、最優(yōu)轉(zhuǎn)角數(shù)量以及最優(yōu)危險度，統(tǒng)計結(jié)果如圖4—圖6所示。

圖4 最優(yōu)路徑長度

由圖4—圖6實驗結(jié)果可以看出，相比于其他算法，本文算法具有較強的收斂速度以及全局尋優(yōu)能力，本文算法采用蟻群優(yōu)化算法規(guī)劃煤礦救援機器人具有較高有效性。本文算法可快速獲取具有最優(yōu)綜合性能的可行駛路徑，規(guī)劃效果優(yōu)越。本文算法應(yīng)用于煤礦救援機器人路徑規(guī)劃時，充分考慮煤礦巷道工作區(qū)域的復(fù)雜性以及危險性，所獲取路徑規(guī)劃結(jié)果長度最短，最優(yōu)轉(zhuǎn)角數(shù)量最少，最優(yōu)危險度最低，驗證采用本文算法所獲取最優(yōu)解具有較高質(zhì)量。

圖6 最優(yōu)危險度

為驗證本文算法采用蟻群優(yōu)化算法的準(zhǔn)確性，在上述實驗參數(shù)和環(huán)境的基礎(chǔ)上，進行對比實驗，不同方法的魯棒性和運算效率對比結(jié)果如圖7、圖8所示。

圖7 不同方法的魯棒性對比

圖8 不同方法的運算效率對比

由圖7和圖8可知，相比其他方法，本文算法采用蟻群優(yōu)化算法規(guī)劃煤礦救援機器人具有較高的魯棒性和運算效率。本文算法可準(zhǔn)確獲取可行駛路徑，規(guī)劃效果優(yōu)越。驗證采用本文算法所獲取最優(yōu)解具有較高準(zhǔn)確性。

測試不同方法進行煤礦救援機器人路徑規(guī)劃的參數(shù)對比如圖9所示。分析圖9得知，本文方法降低了疏散時間，提高了救援機器人的可靠性抵達能力。

圖9 參數(shù)性能對比

3 結(jié)語

通過機器人路徑規(guī)劃獲取無障礙物影響，且行駛長度最短的路徑即機器人行駛的最優(yōu)路徑。蟻群算法應(yīng)用于機器人路徑規(guī)劃時具有易陷入局部最優(yōu)、運算過于復(fù)雜的缺陷。煤礦救援機器人應(yīng)用過程中具有較高復(fù)雜性，煤礦救援機器人運行于礦井時，不僅需要考慮路徑最短問題，最優(yōu)路徑規(guī)劃時還需躲避水、火、障礙物等區(qū)域。將蟻群優(yōu)化算法應(yīng)用于煤礦救援機器人路徑規(guī)劃中，通過信息素更新規(guī)則等部分優(yōu)化算法，令蟻群算法信息素濃度處于合理范圍，提升蟻群優(yōu)化算法尋找最優(yōu)路徑的運算效率，提升算法全局尋優(yōu)性能。通過實驗驗證，采用該算法可有效獲取煤礦救援機器人的最優(yōu)路徑規(guī)劃結(jié)果，快速獲取最優(yōu)可行解，所獲取機器人路徑規(guī)劃結(jié)果有效避開水、火、障礙物等部位，在復(fù)雜礦井環(huán)境下仍具有較高的尋優(yōu)能力，可應(yīng)用于環(huán)境復(fù)雜的煤礦救援機器人路徑規(guī)劃中。