基于改進蟻群算法的無人礦車路徑規(guī)劃研究

劉 輝，肖 克，王京擘

（青島大學 自動化學院，青島 266071）

0 引言

無人采礦技術為智能采礦技術發(fā)展的重要領域之一，而礦物運輸對于礦區(qū)發(fā)展起著舉足輕重的作用，無人礦車有助于實現(xiàn)安全生產，降低人工成本，提升運行效率，成為在無人采礦技術中的重要組成部分。由于礦區(qū)坡度較大、地形復雜，對無人礦車的行駛速度和軌跡都有很大的影響，因此如何根據(jù)礦區(qū)復雜地形對無人礦車進行安全合理的軌跡規(guī)劃成為了急需解決的問題。常用的路徑規(guī)劃方法有傳統(tǒng)路徑規(guī)劃算法A*算法[1]等和一些智能優(yōu)化算法，如遺傳算法[2]、模擬退火算法[3]、蟻群算法[4～7]等。

蟻群算法具有較強的魯棒性、優(yōu)秀的分布式機制[8]，在路徑規(guī)劃領域有著較好的表現(xiàn)。但蟻群算法也存在一些問題，如收斂速度較慢、搜索范圍較小容易陷入局部最優(yōu)路徑等。一些研究者通過修改傳統(tǒng)蟻群算法狀態(tài)轉移規(guī)則中的影響因素來提高算法的性能。文獻[9]提出采用等級反饋制度對適應度較強的螞蟻和較差螞蟻的信息素分別按照一定比例進行增強和減弱。為了避免陷入局部最優(yōu)，文獻[10]根據(jù)目標點信息自適應的調整啟發(fā)式函數(shù)。還有一些研究者將蟻群算法與其它路徑規(guī)劃算法相結合，文獻[11]中結合蟻群算法與人工勢場法，在迭代初期通過人工勢場對信息素進行初始化。文獻[12]加入了多策略進化機制并通過A*算法優(yōu)化初始信息素設置。

本文在礦區(qū)復雜環(huán)境的基礎上，根據(jù)傳統(tǒng)的路徑規(guī)劃算法，提出了改進的蟻群路徑規(guī)劃算法。通過柵格法建立模型，緊密結合礦區(qū)環(huán)境，通過坡度-速度模型將礦區(qū)環(huán)境中礦車的速度引入到狀態(tài)轉移規(guī)則中。由于礦區(qū)環(huán)境復雜，使用常規(guī)的蟻群算法容易進入障礙陷阱，因此引入障礙探索機制，對環(huán)境進行充分的探索。最后將局部最優(yōu)路徑融合，使每一代螞蟻能夠獲得較好的路徑。

1 環(huán)境建模與蟻群算法介紹

1.1 環(huán)境建模

常用的環(huán)境建模方法有柵格法[13]、可視圖法[14]和拓撲法[15]等。本文采用柵格法對礦區(qū)工作環(huán)境進行建模，模型如圖1所示，黑色柵格表示礦區(qū)中的礦堆，礦坑等障礙物。通過M×M個單位柵格的序號i和坐標（x，y）來描述礦車與環(huán)境之間的關系，單位柵格的坐標則是每個柵格的中心位置，柵格坐標與序號轉換公式如下：

當x為負數(shù)時，其值為柵格坐標中的最大橫坐標M-0.5，在不碰到障礙物情況下，礦車可以向周圍的八個柵格移動。

圖1 環(huán)境模型示意圖

1.2 蟻群算法介紹

蟻群算法是一種用來尋找優(yōu)化路徑的啟發(fā)式算法，Marco Dorigo通過螞蟻在尋找食物時的搜尋路徑的行為提出了蟻群算法，算法模仿螞蟻產生信息素，通過螞蟻間正反饋的方法來引導螞蟻的行為。傳統(tǒng)蟻群算法的狀態(tài)轉移概率公式為：

其中，Pijk（t）為在螞蟻k在時刻t從節(jié)點i到節(jié)點j的概率；τij（t）為在時刻t節(jié)點i到節(jié)點j的信息素濃度；ηij（t）表示在時刻t節(jié)點i到節(jié)點j之間距離的倒數(shù)；Jk（i）為節(jié)點i的下一可行節(jié)點集合；α和β分別為信息素濃度因子和啟發(fā)函數(shù)因子。

2 改進的蟻群算法

2.1 改進啟發(fā)函數(shù)

螞蟻在尋路時有時會陷入各種障礙之中，但由于許多障礙對螞蟻尋找最優(yōu)路徑并不會產生較大影響，因此本文提出一種障礙探索機制，僅對影響螞蟻尋找最優(yōu)路徑的障礙進行規(guī)避。螞蟻在選擇下一柵格時，首先對下一柵格的周圍環(huán)境進行探索，如果其周圍三個距離目標點最近的柵格都包含障礙，則證明其會阻礙螞蟻尋找最優(yōu)路徑或者陷入死鎖，因此會減小此柵格的選擇。

障礙探索的幾種情況如圖2所示，假設紅旗位置為螞蟻所在的當前節(jié)點的位置，它的一個可選柵格s為圓點所在柵格，螞蟻的搜索范圍為圓點周圍距離目標點最近的三個柵格，即觀察柵格i，j，k是否都包含有障礙物，若三個柵格都包含有障礙，則圓點所在柵格的障礙影響因子設為相對較大的值，避免選擇此類柵格。若三個柵格不全為障礙，則該柵格的障礙影響因子為零，該柵格為可行柵格。

因此，下一柵格點s的對于螞蟻搜尋路徑的障礙影響因子為：

其中，Dis（s）表示柵格s到目標點的距離，根據(jù)柵格位置的不同，動態(tài)調整障礙影響因子的大小。G（i）∈{0，1}為柵格i的狀態(tài)，0表示無障礙、1表示有障礙。i，j，k為s附近的三個離目標點距離最短的柵格且滿足：

最后將最優(yōu)路徑影響因子與距離啟發(fā)信息進行權衡，得出節(jié)點s最終的啟發(fā)函數(shù)為：

本節(jié)提出一種障礙探索機制，對障礙物進行提前規(guī)避，減少了螞蟻選擇一些延長路徑的節(jié)點和陷阱點的概率，在一定程度上提高了算法的性能，且保障了礦車的安全。

2.2 礦車速度影響因子

由于礦區(qū)環(huán)境復雜，地形崎嶇不平，當?shù)V車在坡度較大區(qū)域行駛時會產生大量的能量損耗，也對礦車的安全性有一定影響。因此我們將礦區(qū)環(huán)境中的坡度等因素考慮入我們建立的環(huán)境模型中。我們采用榮健博士論文[16]中的車輛速度與坡度等因素的數(shù)學模型：

其中，v2為上坡Δt時間段后車輛的速度，v1為Δt之前的速度，Δt為經過的時間步長。P表示車輛功率質量比，δ與KF表示車輛的慣性阻力系數(shù)與風阻系數(shù)，i，f為坡度與摩擦阻力，g表示重力加速度，G表示車輛的空載質量與實際載重。

為了簡化模型，本文中在起始柵格設置初始速度，將上一柵格到達當前柵格的速度和當前柵格i到達下一柵格j的速度Vij(t)近似代替式(6)中的v1，v2。環(huán)境坡度隨著y坐標的減小逐漸增大。將速度預測模型加入柵格狀態(tài)轉移模型中，使得在路程較短的情況下更多的選擇坡度較小柵格，以減少能量損耗、更短的時間完成任務。

2.3 改進信息素策略

在傳統(tǒng)的蟻群算法中，在一代螞蟻尋找路徑后更新全部信息素，因此會導致出現(xiàn)收斂速度較慢，收斂到局部最優(yōu)等問題。為了使每代螞蟻尋找完路徑之后能探索距離與時間綜合最優(yōu)的路徑，使下一代螞蟻在此較優(yōu)路徑的基礎上探尋更優(yōu)的路徑，因此在每代螞蟻尋找完路徑之后采用局部距離時間綜合最優(yōu)路徑融合的方法。

圖3 路徑融合示意圖

首先根據(jù)式(7)挑選出每代螞蟻中距離與時間綜合最優(yōu)的幾只優(yōu)秀螞蟻，對它們局部的距離時間綜合最優(yōu)的路徑進行融合，重新組成一條可能更優(yōu)的路徑。距離與時間權衡公式如下：

其中D為路徑長度；T為走過該路徑消耗的時間，根據(jù)柵格之間的速度與距離得出；ξ代表時間的重要程度。圖中為第n代螞蟻中前三條最優(yōu)的路徑，ai表示螞蟻i所走過的節(jié)點。若路徑之間存在相同節(jié)點，則對比螞蟻的相同節(jié)點之間的距離與時間，根據(jù)式(7)取出兩節(jié)點之間的最優(yōu)路徑。圖中陰影柵格表示了融合后的最優(yōu)路徑，融合公式如下：

其中Flir（t）為第t代優(yōu)秀螞蟻r從節(jié)點l到節(jié)點j的距離與時間綜合評價指標，Lljr（t）為第t代優(yōu)秀螞蟻r從節(jié)點l到節(jié)點j的路徑，L12（t）表示優(yōu)秀螞蟻1和優(yōu)秀螞蟻2的融合路徑。k，m與g，n代表螞蟻經過的相同的節(jié)點中兩個最近的節(jié)點。另外加入了歷史最優(yōu)螞蟻路徑同融合路徑進行對比選擇更優(yōu)路徑，使算法在前期能夠通過融合路徑更好地探索最優(yōu)路徑，而在后期會較多選擇歷史最優(yōu)路徑，加大對最優(yōu)路徑的利用，公式如下：

則新的信息素更新公式如下：

2.4 改進算法流程圖

改進算法步驟如圖4所示，首先對地圖進行處理和參數(shù)初始化，螞蟻在選擇每個可選節(jié)點時先對其周圍探索區(qū)域進行探索，在信息素、啟發(fā)式信息、速度的共同作用下選擇節(jié)點。當螞蟻到達目標點時記錄路徑，挑選出優(yōu)秀螞蟻進行路徑融合，增強融合路徑和歷史最短路徑中較優(yōu)路徑的信息素。當?shù)竭_最大迭代次數(shù)后，輸出最優(yōu)路徑。

圖4 改進蟻群算法流程圖

3 仿真實驗

為驗證本文改進的蟻群算法的有效性，在MATLAB 2014a軟件環(huán)境進行仿真實驗，并與傳統(tǒng)蟻群算法進行比較。柵格環(huán)境大小為20×20，每個柵格大小表示100m×100m，即礦區(qū)環(huán)境大小為2km×2km，并且柵格顏色的加深，表示礦區(qū)坡度不斷變大，根據(jù)柵格之間的速度和距離求解出完成路徑規(guī)劃所需的時間。實驗設置每代螞蟻的個數(shù)M=50，最大迭代次數(shù)為50次，信息素影響因子α=1，信息素蒸發(fā)系數(shù)ρ=0.5，啟發(fā)式影響因子β=7，距離啟發(fā)信息影響因子σ=1，最優(yōu)路徑影響因子比例δ=2，速度影響因子γ=1。

3.1 仿真實驗結果

圖5和圖6為兩種障礙物復雜度不同的仿真環(huán)境，可以看出由于改進的蟻群算法由于加入了障礙探索機制，對于一些阻礙螞蟻尋找最優(yōu)路徑的點和陷阱點，算法對其提前進行了屏蔽，避免了如圖5中傳統(tǒng)蟻群算法陷入了一些障礙中。在圖6環(huán)境中，雖然兩種算法都找到了最短路徑，但改進的算法有著較快的收斂速度，如圖7所示，改進算法在16代左右就收斂到了最優(yōu)路徑，相比傳統(tǒng)蟻群算法在29代左右收斂有了明顯的提升，另外在相同路長情況下，改進的算法較多的選擇坡度較小的柵格，以21.07min到達目標點，比傳統(tǒng)蟻群算法21.19min完成用時更短。

圖5 仿真環(huán)境1及仿真結果

圖6 仿真環(huán)境2及仿真結果

圖7 仿真環(huán)境2收斂曲線

最后選取了30×30柵格的新環(huán)境并進行了多次實驗，結果取其平均值，最終結果如表1所示，可以看出改進的蟻群算法在兩種環(huán)境中所用路長和時長較為穩(wěn)定，且都優(yōu)于傳統(tǒng)蟻群算法。

表1 改進蟻群算法與傳統(tǒng)蟻群算法性能對比

4 結語

本文針對礦區(qū)環(huán)境下的礦車路徑規(guī)劃問題，提出了一種改進的蟻群路徑規(guī)劃算法。首先考慮到礦區(qū)環(huán)境的復雜性，提出一種障礙探索機制，對于一些會阻礙螞蟻尋找最優(yōu)路徑的節(jié)點和陷阱點進行規(guī)避，避免螞蟻增加其路徑長度和陷入死鎖，對礦車的安全性也帶來一定提升。結合礦區(qū)部分區(qū)域坡度較大問題，將坡度-速度模型加入狀態(tài)轉移概率公式中，在路徑較短的前提下，盡可能的選擇坡度較小的區(qū)域，以加快運輸時間。最后采用優(yōu)秀螞蟻路徑融合的方法，提高了路徑探索率，一定程度上避免收斂到局部最優(yōu)路徑。經仿真驗證，改進的蟻群算法在復雜的礦區(qū)環(huán)境下能夠規(guī)劃出一條距離和時間較短、安全性較高的路徑。