基于改進蟻群算法的移動機器人火災救援路徑規劃方法

昝新宇，張鐵峰, 苑津莎

(華北電力大學電氣與電子工程學院，保定 071003)

近年來，中國每年發生數萬起火災事故[1-2]，嚴重影響著人們正常的生產生活。隨著機器人技術的迅速發展，機器人因其智能、高效等優點受到各行各業的青睞，因此移動機器人參與火災救援已成為未來發展趨勢。為此，探究移動機器人在火災救援中如何快速到達待救援點執行救援任務，具有十分重要的研究意義。

關于火災救援路徑規劃的問題，李珊珊等[3]針對多起點、多終點的大型火災救援路線，設計了一種組合優化路徑規劃方法，可以計算出安全、快速的救援路徑，提高了火災救援的效率；劉軍[4]采用蟻群算法與遺傳算法結合方式，改善了超市火災環境下消防員滅火救援路徑；張蘇英等[5]提出一種改進蟻群算法，優化了大型綜合建筑火災疏散路徑;張麗杰等[6]針對復雜建筑火災中的人員疏散路徑優化策略問題，構建了一種以最短時間、最小風險水平和最大疏散容量為目標的路徑優化模型，并結合自適應果蠅算法對模型求解。

在移動機器人路徑規劃方面，Luo等[7]為解決蟻群算法搜索效率低、收斂速度慢等問題，提出一種優化蟻群算法，并通過實驗仿真驗證了該算法能夠提高移動機器人路徑規劃效率；王蘇彧等[8]提出了一種基于自適應導向的優化蟻群算法，通過優化算法的收斂速度和尋優能力，進而提高了移動機器人自主規劃路徑的能力；Ranaweera等[9]提出了一種粒子群優化算法來尋找消防救援機器人的最短路徑，并通過模擬實驗驗證了改進算法的效率遠高于傳統算法；李理等[10]提出了一種多啟發因素改進蟻群算法，該算法計算出的路徑在路徑長度、轉彎次數以及坡度平滑性三因素綜合性能上具有較大的提高，進而增強了移動機器的環境適應能力。

當前，中外學者針對移動機器人火災救援路徑規劃問題的研究較少，而且在已有方法中只考慮了距離因素，沒有考慮影響路徑選擇的其他因素。對此，現考慮多因素針對移動機器人火災救援路徑規劃的影響，提出一種基于改進蟻群算法的移動機器人火災救援路徑方法。方法考慮多因素分配各路徑上的信息素，指導螞蟻尋找最優路徑。通過動態調整信息素和啟發式函數影響因子，以期提升算法的搜索能力與收斂速度。

1 環境描述

環境模型的構建對于移動機器人路徑規劃至關重要，通過部署在建筑物內的無線傳感設備獲取環境信息，然后根據柵格法[11]建立環境模型。通過MATLAB仿真，仿真結果如圖1所示。

綠色圓點為移動機器人的起始位置，紅色圓點為待救援位置；黑色柵格表示障礙物，白色柵格表示自由空間；紅色柵格表示火源中心，黃色柵格表示火源周圍蔓延區域；綠色深淺表示坡度大小，顏色越深表示坡度越大

針對移動機器人在火災救援過程中對于安全性方面的要求非常高，規劃出的路徑盡量遠離障礙物、火源以及蔓延區域，即使頂點也要避免觸碰。因此規定每個柵格中心為節點，螞蟻的運動軌跡可以理解為從當前節點到下一節點轉移的累積過程。同時為了避免移動機器人在轉彎過程中發生碰撞，只有目標柵格和轉角處柵格均為自由柵格時，才能向該目標節點轉移，如圖2所示。

圖2 轉彎示意圖

2 傳統蟻群算法

蟻群算法是Dorigo提出的一種模擬螞蟻種群覓食行為的智能仿生算法[12]。該算法具有并行計算、正反饋、魯棒性強等優點，因此許多學者將蟻群算法用于路徑規劃，并取得較好的效果。信息素模型和啟發式函數的構建是蟻群算法優劣的關鍵因素[13]。信息素是蟻群發出的指引信息并隨著時間揮發，路徑上的信息素濃度越高，越能指導螞蟻沿該路徑前進；啟發式函數則相當于螞蟻根據自身所處環境進行判斷的依據。

螞蟻在搜索過程中根據轉移概率選擇下一步前進方向，轉移概率為

(1)

(2)

每只螞蟻在使用信息素的同時也會分泌信息素，并且會隨著迭代次數的增加，信息素會在路徑上積累，同時也會揮發減少。傳統蟻群算法的信息素更新模型為

τi,j(t+1)=(1-ρ)τi,j(t)+ρΔτi,j(t)

(3)

(4)

式中：ρ為信息素揮發度；Δτi,j(t)為第t次迭代中信息素在節點i至節點j上的增量；Q為信息素常數；Lk為第k只螞蟻從起點至終點走過的路徑長度。

3 改進蟻群算法

3.1 多因素啟發式函數

傳統蟻群算法的啟發式信息與當前節點到下一節點的距離成反比，這促使螞蟻選擇距離短的路徑。但是，在實際環境中決定路徑優劣的因素不止距離一種，還有路徑的曲折程度、顛簸程度等因素。移動機器人在火災救援中多轉彎一次可能會浪費大量的寶貴救援時間，顛簸程度較大的路況不僅會影響移動機器人的速度，可能還會損壞機器設備。因此，規劃一條綜合指標最好的路線對于移動機器人參與火災救援至關重要。為此，針對影響路徑優劣的多因素引入多因素啟發式函數，來計算轉移概率，并同時引入阻尼系數，加快算法后期的收斂速度，即

(5)

(6)

式中：φ(i,j,q)為距離因素，即當前節點的各個相鄰節點至目標節點的歐式距離的倒數；φi,j(t)為曲折程度，即當前轉向若與上次轉向相同，則其值就較大，反之則較小；υ(i,j)為顛簸程度，即當前節點與下一個節點的高度差的倒數；ζ為阻尼系數；tmax為最大迭代次數。

3.2 改進信息素更新規則

信息素更新主要模擬自然界中螞蟻信息素隨時間的積累和揮發過程。將最大-最小蟻群系統(MMAS)的基本模型與多因素啟發式函數相結合，對信息素更新規則進行改進。

每當一只螞蟻到達終點時，信息素根據式(7)、式(8)進行局部更新。所有螞蟻完成一次迭代后，所有螞蟻行走的過程中，會存在綜合指標最小的路徑，全局信息素只對其更新，從而增加當前綜合性最優路徑對后續蟻群尋優的影響，如式(9)所示。

(7)

Sk(t)=xLk(t)+yFk(t)+zTk(t)

(8)

(9)

式中：Sk(t)為第k只螞蟻在第t次迭代中所走路徑的綜合指標；Smin(t)為第t次迭代中最小的綜合指標；Lk(t)為路徑長度；Fk(t)為螞蟻訪問過節點的高度均方差；Tk(t)為轉彎次數；x、y、z分別為路徑長度、顛簸程度以及曲折程度的相對重要性，可以根據實際需要進行調節。為了防止算法停滯，將信息素限制在[τmin,τmax]范圍內，如式(10)所示。

(10)

式(10)中：τmin、τmax分別為信息素的最小值和最大值，取值可以根據實際的場景進行設計。

3.3 動態調整信息素和啟發式函數影響因子

信息素影響因子反映了信息素在蟻群搜索中的相對重要性[14]，其值過大或過小，都會導致蟻群算法找不到最優解。啟發式函數影響因子反映了蟻群尋找最優解過程中先驗性的相對重要程度[15]，其值增大，加速算法的收斂，但同時會減小算法的隨機性；減小時，則相反。

因此信息素和啟發式函數影響因子對于蟻群算法至關重要，為了提升算法收斂速度和搜索能力，提出了一種動態調整信息素和啟發式函數影響因子的方法。算法初期，針對信息素分布差別較小，螞蟻的搜索過程可能混亂，這時啟發式函數在蟻群搜索中起主要引導作用，螞蟻更多地依據自身環境選擇前進方向；隨著信息素不斷地更新，信息素的分布差別變得明顯，此時信息素和啟發式函數共同引導蟻群尋優過程，螞蟻在選擇下一節點時，需要同時考慮自身環境和前面螞蟻留下的信息素。如式(11)、式(12)所示。

(11)

(12)

式中：α為信息素影響因子；β為啟發式函數影響因子；ζ為一個百分比常數；A、B、C、D、E為正整數，可隨環境不同改變取值。

3.4 改進算法流程

步驟1地圖障礙物、火源等位置信息以及參數初始化。其中螞蟻數量m=50，最大迭代次數tmax=100，信息素強度Q=100，其他的參數作為變量根據實驗環境進行設置。

步驟2設置起始坐標與終點坐標。

步驟3禁忌表初始化。

步驟4確定信息素和啟發式函數影響因子。根據式(11)和式(12)分別計算信息素和啟發式函數影響因子。

步驟5路徑選擇。由式(3)和式(5)分別計算信息素與多因素啟發式函數，然后由式(1)計算螞蟻每個前進方向的概率，最后利用輪盤賭決定螞蟻下一個轉移節點。

步驟6更新禁忌表。

步驟7判斷當前螞蟻是否到達終點坐標位置，若是，繼續執行算法；否則，返回步驟5。

步驟8由式(8)計算螞蟻走過路徑的綜合指標，由式(7)進行信息素局部更新。

步驟9判斷是否所有螞蟻完成搜索，若是，繼續執行算法；否則，增加螞蟻數量，即m=m+1，然后返回步驟3。

步驟10更新全局信息素。需要找到本次迭代中綜合指標最佳的路徑，并根據式(9)進行全局信息素更新。

步驟11判斷迭代次數是否達到最大迭代次數，若是，比較各迭代次數中綜合指標最佳的路徑，輸出最優路徑，結束算法；否則，增加迭代次數，即t=t+1,m=1，然后返回步驟3。

改進的算法流程如圖3所示。

圖3 改進算法流程

4 實驗仿真與分析

使用MATLAB R2019a仿真軟件對算法進行仿真，模擬移動機器人在火災救援中規避障礙物和火源及蔓延區域的路徑規劃過程。設定30 m×30 m的區域內均勻分布傳感設備，時刻監視火源及蔓延區域情況；移動機器人的起始坐標為(0.5,0.5)m，待救援位置即終點坐標為(29.5,29.5)m。初始環境如圖1所示。根據經驗和實驗仿真對比進行參數取值，算法的參數配置如表1所示。

表1 改進蟻群算法的參數配置

將改進蟻群算法、文獻[10]算法和傳統蟻群算法在相同的環境模型中進行實驗仿真。3種不同算法計算出最佳救援路線如圖4所示。

藍色實線為傳統蟻群算法的規劃路線；黑色虛線為文獻[10]算法計算出的最佳路徑；紅色實線為本文算法規劃的最佳路徑

為了驗證改進算法的優越性，進行了多次實驗仿真，如圖5和表2所示。通過比較3個算法的實驗結果，在路徑長度、路徑高度均方差以及轉彎次數3個指標上本文算法均小于傳統蟻群算法和文獻[10]算法，比較3個算法的綜合指標可以看出，本文算法計算出的路徑在多因素上明顯優于文獻[10]算法和傳統蟻群算法。并且本文算法較大地提高了算法的收斂速度，降低了穩定迭代次數，提升了算法的搜索能力，使螞蟻初始尋路就能找到綜合指標較好的路徑。在算法穩定性方面，本文算法多次實驗計算出的最優路徑中的各項指標波動較小，明顯優于文獻[10]算法和傳統蟻群算法。

表2 本文算法、文獻[10]算法及傳統蟻群算法的結果對比

連續10次實驗中不同算法平均運行時間如表3所示，雖然本文算法運行時間稍長于傳統算法，但迭代穩定時間明顯小于傳統蟻群算法和文獻[10]算法。由此可見，本文算法的執行效率顯然優于傳統蟻群算法和文獻[10]算法，可以幫助移動機器人快速找到一條多因素綜合性最優的路徑。

表3 連續10次實驗中不同算法平均運行時間

可見，本文算法在多因素綜合性能上有了較大提升，并且具有較好的全局搜索能力和收斂速度。因此，該方法可以使移動機器人有效避開障礙物和火源區域，找到一條安全、快速的救援路線，大大提高了火災救援的效率。

5 結論

針對移動機器人在火災救援中路徑規劃的多種影響因素，提出了一種基于改進蟻群算法的路徑規劃方法。

(1)改進蟻群算法通過引入多啟發式函數和改進全局信息素更新策略，更好地引導蟻群向綜合性最優的路徑靠近。

(2)通過對信息素和啟發式函數影響因子動態調整，提升了算法的搜索能力和收斂速度。

(3)通過實驗仿真驗證和3種方法的對比分析，驗證了本文算法能夠滿足移動機器人救援路徑規劃快速決策的需要，較好地提高了火災救援的效率。

改進算法在傳統蟻群算法基礎上針對啟發式函數和信息素更新方式等方面進行了優化，沒有考慮初始信息素差別分布，在今后的研究中，可以利用神經網絡對其進行優化，使路徑規劃方法更加高效、智能。