煤礦救援機器人路徑規劃的蟻群優化算法

郭 泰，顏 鋌

(重慶應用技術職業學院，重慶 401520)

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

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

1 蟻群優化算法

1.1 環境建模與問題描述

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

(1)

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

可得柵格內煤礦救援機器人路徑規劃問題目標函數：

(2)

(3)

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

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

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

(4)

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

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

(5)

數量為m的障礙物集中于其中一條路徑時，可將聚度公式轉化為：

(6)

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

1.3 傳統蟻群算法

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

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

(7)

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

(8)

螞蟻k經過節點i與節點j時，可得公式：

(9)

式中，Q為常數；Lk為螞蟻k所經過路徑總長度。

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

(10)

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

(11)

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

1.4 蟻群優化算法

1.4.1 改進信息素規則

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

(12)

式中，τnew為信息素揮發系數；ρ為新路徑信息素；τold為原路徑信息素；δ為調節因子；Dbest為最優解；Dworst為最差解。

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

1.4.2 限制信息素閾值

信息素閾值限制形式：

(13)

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

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

1.4.3 改進轉移概率

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

(14)

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

(15)

式中，(xj，yj)為節點坐標值；(xEnd，yEnd)為終點坐標值。

優化所獲取啟發因子ηjEnd越小，表示被選中該柵格節點j概率越高。

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

(16)

(17)

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

2 實例分析

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

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

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

圖2 收斂曲線對比

采用4種算法規劃煤礦救援機器人最優行駛路徑結果如圖3所示。

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

統計采用本文算法規劃煤礦救援機器人行駛路徑的最優路徑長度、最優轉角數量以及最優危險度，統計結果如圖4—圖6所示。

圖4 最優路徑長度

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

圖6 最優危險度

為驗證本文算法采用蟻群優化算法的準確性，在上述實驗參數和環境的基礎上，進行對比實驗，不同方法的魯棒性和運算效率對比結果如圖7、圖8所示。

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

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

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

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

圖9 參數性能對比

3 結語

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