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

郭 泰，顏 鋌

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

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

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

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

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

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

(1)

式中，「?為取整符號(hào)；mod為求余符號(hào)。

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

(2)

(3)

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

1.2 確定煤礦救援機(jī)器人可行駛路徑

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

(4)

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

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

(5)

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

(6)

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

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

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

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

(7)

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

(8)

螞蟻k經(jīng)過(guò)節(jié)點(diǎn)i與節(jié)點(diǎn)j時(shí)，可得公式：

(9)

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

螞蟻k由位置i移動(dòng)至位置j的概率公式為：

(10)

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

(11)

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

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

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

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

(12)

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

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

1.4.2 限制信息素閾值

信息素閾值限制形式：

(13)

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

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

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

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

(14)

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

(15)

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

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

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

(16)

(17)

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

2 實(shí)例分析

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

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

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

圖2 收斂曲線對(duì)比

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

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

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

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

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

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

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

圖7 不同方法的魯棒性對(duì)比

圖8 不同方法的運(yùn)算效率對(duì)比

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

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

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

3 結(jié)語(yǔ)

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