劉 輝，肖 克，王京擘

（青島大學(xué) 自動(dòng)化學(xué)院，青島 266071）

0 引言

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

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

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

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

1.1 環(huán)境建模

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

當(dāng)x為負(fù)數(shù)時(shí)，其值為柵格坐標(biāo)中的最大橫坐標(biāo)M-0.5，在不碰到障礙物情況下，礦車(chē)可以向周?chē)陌藗€(gè)柵格移動(dòng)。

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

1.2 蟻群算法介紹

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

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

2 改進(jìn)的蟻群算法

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

螞蟻在尋路時(shí)有時(shí)會(huì)陷入各種障礙之中，但由于許多障礙對(duì)螞蟻尋找最優(yōu)路徑并不會(huì)產(chǎn)生較大影響，因此本文提出一種障礙探索機(jī)制，僅對(duì)影響螞蟻尋找最優(yōu)路徑的障礙進(jìn)行規(guī)避。螞蟻在選擇下一柵格時(shí)，首先對(duì)下一柵格的周?chē)h(huán)境進(jìn)行探索，如果其周?chē)齻€(gè)距離目標(biāo)點(diǎn)最近的柵格都包含障礙，則證明其會(huì)阻礙螞蟻尋找最優(yōu)路徑或者陷入死鎖，因此會(huì)減小此柵格的選擇。

障礙探索的幾種情況如圖2所示，假設(shè)紅旗位置為螞蟻所在的當(dāng)前節(jié)點(diǎn)的位置，它的一個(gè)可選柵格s為圓點(diǎn)所在柵格，螞蟻的搜索范圍為圓點(diǎn)周?chē)嚯x目標(biāo)點(diǎn)最近的三個(gè)柵格，即觀察柵格i，j，k是否都包含有障礙物，若三個(gè)柵格都包含有障礙，則圓點(diǎn)所在柵格的障礙影響因子設(shè)為相對(duì)較大的值，避免選擇此類(lèi)柵格。若三個(gè)柵格不全為障礙，則該柵格的障礙影響因子為零，該柵格為可行柵格。

因此，下一柵格點(diǎn)s的對(duì)于螞蟻搜尋路徑的障礙影響因子為：

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

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

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

2.2 礦車(chē)速度影響因子

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

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

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

2.3 改進(jìn)信息素策略

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

圖3 路徑融合示意圖

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

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

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

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

2.4 改進(jìn)算法流程圖

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

圖4 改進(jìn)蟻群算法流程圖

3 仿真實(shí)驗(yàn)

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

3.1 仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

4 結(jié)語(yǔ)

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