基于改進蟻群算法的消防救援機器人路徑規劃方法

丁金虎

摘 ?要：該文介紹蟻群算法的基本原理與實現步驟，利用BIM技術構建火災建筑室內環境模型，結合火場情況對蟻群算法進行改進，逐一闡述優化信息素提取更新過程、改進啟發函數、躲避特定障礙物、選擇逃生路徑的具體方法，分析全局路徑規劃中改進蟻群算法的實現方式，最后展開規劃路徑仿真實驗。通過與2種不同改進算法的路徑規劃能力進行對比，得出該文所提出改進蟻群算法的優越性，同時還通過算法性能分析發現，此算法的最佳性能、時間性能、魯棒性均優于其他算法，得出消防救援機器人路徑規劃過程中改進蟻群算法具有應用可行性與優越性的結論。

關鍵詞：蟻群算法；算法改進；消防救援機器人；路徑規劃；BIM技術

中圖分類號：TU998.1 ? ? ?文獻標志碼：A ? ? ? ? ?文章編號：2095-2945（2024）14-0133-04

Abstract： In this chapter， the basic principle and implementation steps of ant colony algorithm are introduced， the indoor environment model of fire building is constructed by using BIM technology， and the ant colony algorithm is improved according to the situation of fire scene. The specific methods of optimizing pheromone extraction and updating process， improving heuristic function， avoiding specific obstacles and choosing escape path are expounded one by one， and the implementation of improved ant colony algorithm in global path planning is analyzed. Finally， the path planning simulation experiment is carried out， and by comparing with the path planning ability of two different improved algorithms， the superiority of the improved ant colony algorithm proposed in this paper is obtained. At the same time， through the performance analysis of the algorithm， it is found that this algorithm has better performance， time performance and robustness than other algorithms. It is concluded that the improved ant colony algorithm has application feasibility and superiority in the process of fire and rescue robot path planning.

Keywords： ant colony algorithm; algorithm improvement; fire and rescue robot; path planning; BIM technology

發生火災的建筑室內環境往往較為復雜，煙氣會影響普通激光雷達的運行效果，無法獲取準確的室內布局圖，因而救援路徑規劃難度較大。為此，本文提出了利用BIM技術獲取建筑物基礎信息，再基于改進蟻群算法規劃消防救援機器人的救援路徑。此種方式能夠精準獲得建筑室內信息并繪制出準確的室內地圖，有效收集障礙物實體信息，且能彌補傳統蟻群算法路徑規劃效率低、性能不佳的弊端。

1 ?蟻群算法的原理及實現步驟

蟻群算法是模擬螞蟻尋食行動所構建的算法，螞蟻之間可通過釋放信息素傳遞信息，從而不受環境限制快速找出到達食物地點的通往路徑。路徑構建、信息素更新是蟻群算法的兩大核心，算法初始階段會給出固定信息素濃度，迭代一次螞蟻便完成一次尋食，并計算探尋路徑，之后再更新信息素濃度[1]。由于短距離線路較長距離線路殘留信息素濃度更高，因而其是路徑算法的最優解。蟻群算法共有3種模型，分別是螞蟻數量系統、螞蟻密度系統、螞蟻圈系統，根據旅行商問題（TSP）解決中3種模型的應用效果對比發現，螞蟻圈系統表現最為優勢，因而本文的算法信息素更新機制選用此算法。蟻群算法的實現需經過8個步驟：一是初始化算法參數，二是更新迭代次數，三是設置螞蟻放置位置，四是基于動態轉移概率選擇前往位置，五是在禁忌表中加入走過位置，六是循環結束后更新全局信息素求得路徑解，七是判斷循環完成情況并對比路徑解找出循環可行解，八是判斷循環（迭代）次數的最大值達成情況并對比各次循環可行解，找出最優解。

2 ?基于改進蟻群算法的消防救援機器人路徑規劃方法

2.1 ?利用BIM技術構建室內環境模型

為縮短救援時間，需基于建筑BIM圖中的建筑材料信息、樓層出口位置信息展開火災仿真，可為消防救援機器人提供火場全局地圖，通過局部避障、采用遠程控制方式，遠程操控機器人快速實施救援。BIM模型數據庫涵蓋多個數據庫引擎，可為BIM數據讀寫提供支持。因此，可將BIM模型視作建筑數據源，可在模型讀寫基礎上，運用路徑規劃算法完成室內路徑規劃任務。本文利用分類提取法提取BIM建筑信息。采用過濾器歸類BIM中各個幾何元素，收集信道參數預測需應用的建筑構件元素集，再判斷各元素類型，提取并存儲元素屬性中的絕對位置、幾何尺寸等信息，以保存文件為基礎，構建環境信息數組矩陣，之后采用柵格法創建柵格地圖。

2.2 ?結合火場情況改進蟻群算法

2.2.1 ?提取更新信息素過程優化

為平衡算法的收斂速度及隨機性，應對信息素初始獲取及更新過程進行調整，利用柵格間距離計算方法得到節點權值及障礙物分布情況，再預處理障礙物，根據起點及目標點間射線與障礙物是否接觸選擇需要預處理的障礙物，并標記預處理障礙物在下柵格圖中的邊界點，以之作為障礙物的起點或末點，注意相交障礙物交點不可作為邊界點[2]。再將鄰近障礙物距離射線最近的邊界點相連，便可繪制出多線段構建的初始路徑R，此路徑上的信息素可按式（1）初始化

？子（R）=kC， ?（1）

式中：k表示不小于零的常數，C表示其他節點信息素初始化值。得到的可行解能夠繞過多數障礙物展開搜索，可降低螞蟻尋徑盲目性。之后，應以節點對最優路徑的貢獻為基礎，更改信息素更新規則，即

式中：Lmin、Lkmin分別表示上次迭代及當前迭代次數的最短路徑，Lbmin是迭徑次數中的最低值，？琢為調節系數，pathmin表示當前迭代次數中螞蟻路徑為最短路徑，path指當前迭代次數中其他螞蟻的有效路徑。利用此規則可確保當前迭代次數下，最短路徑節點間具有最高的信息素濃度，可使法算收斂速度有所提升。為防止全局搜索時信息素揮發因子為固定常數導致搜索效率下降，需對此因子做出改進，即

式中：GD表示拐點參數平均值，T表示迭代次數。在第T次迭代的拐點參數平均值比第T-1代迭代更高時，增大信息素揮發因子可使算法全局搜索能力得到有效提升，由于消防救援機器人行走路徑中的直角優化為鈍角，因而機器人可快速獲取到最優路徑。

2.2.2 ?改進啟發函數

為降低下個最佳節點選擇難度，應在具有可訪問性且存在多個出口指向目標的節點中篩選下一節點，而節點附近障礙物數量是節點能否正確獲取的影響因素，二者成反比關系。為此，應添加概率因子Pij，概率因子的計算公式為

式中：C（8，N）表示節點j附近障礙物所有可能分布的情況個數，C（8-N-1，1）則為節點j出口分布情況個數，根據此公式可以得到新啟發函數定義公式

式中：djs表示j點與s點（終點）間的距離，這一距離會對啟發函數產生影響，且目標點對路徑吸引力更大。概率因子的添加，使節點障礙物個數成為了節點選擇的重要影響因素，即節點j附近障礙物數量越少，概率因子Pij值越大，獲得的啟發函數也越大，此節點的被選擇概率將會大幅提升[3]。由此規劃出的路徑可有效避讓障礙物較多區域，可為機器人救援安全性及高效性提供保障。

2.2.3 ?躲避特定障礙物

為避免利用蟻群算法求解時出現螞蟻被困在半封閉障礙物中，導致有效循環參與螞蟻數量不足引發算法運算效率降低問題，致使機器人救援時間延長而增大被困人員安全隱患。需要設定螞蟻進入半封閉式障礙空間的條件限制，達到特定條件下，便自動解除螞蟻循環。尋找路徑螞蟻位置坐標及目標點坐標分別為（i，j）與（S，E）時，螞蟻跳出循環的必要條件有4個，一是i與j分別不大于S與E，（i+1，j）=0、（i，j+1）=0；二是i不大于S、j不小于E，（i+1，j）=0、（i，j-1）=0；三是i與j分別不小于S與E，（i-1，j）=0、（i，j-1）=0；四是i不小于S、j不大于E，（i-1，j）=0、（i，j+1）=0。滿足這4個條件之一時，說明螞蟻進入了半封閉障礙物中，此時應使螞蟻跳出循環，并將螞蟻當前所在位置的節點權值調整為0[4]。

2.2.4 ?選擇逃生路徑

由于被困人員存在個體差異，年齡、性別、性格不同的個性，對應急疏散行為的反應并不一致。男性逃生者比女性逃生者更愿意尋找火源滅火，可向此類被困者提供火源及滅火裝置位置信息，引導其控制火勢或降低逃生路徑危險節點溫度。而幼齡及老齡被困人員疏散能力弱于中青年被困者，可利用救援機器人對其實施救援。除此之外，理智型性格被困人員較情緒型、混合型性格被困人員更易于通過權衡利弊篩選逃生路徑。為此，消防救援時需要規劃長短不一的2種逃生路徑：一是短距離逃生路徑，在不超出人體耐受度的情況下，通過穿越危險點逃生；二是遠距離逃生路徑，避讓危險點選擇其他出路逃生。老人、兒童則停留在安全地帶，危險區內的特殊人員，可按規劃路徑轉移至安全位置，再等待救援。

2.3 ?改進蟻群算法在全局路徑規劃中的實現

消防救援機器人利用改進蟻群算法實施救援時，可先利用BIM圖分析建筑室內布局、建筑材料，基于傳感器感知獲取火源位置信息，根據材料成分信息提前預測或約束火災建筑可能出現垮塌的區域，并規劃出不經過垮塌區的機器人救援路徑，從而使局部路徑規劃難度降低，以此節約救援時間[5]。全局路徑規劃中，改進蟻群算法的實現要經過以下步驟：一是構建環境模型；二是提取FDS仿真數據，獲取危險區一氧化碳含量及溫度值；三是預處理障礙物以獲得較優路徑，以增大路徑信息素初始值；四是初始化蟻群算法參數；五是將螞蟻設置于起點準備實施搜索；六是選擇下一節點并向禁忌表添加節點，并于路徑探索后更新信息素，此步驟循環多次；七是將螞蟻位置重新設置為起點并將禁忌表清空；八是判斷迭代次數是否達到預設值，根據判斷結果選擇結束迭代循環或繼續循環；九是基于FDS仿真數據，判斷不同被困人員逃生速度與路徑的適合度，路徑合格應完成輸出，否則應重新選擇逃生節點并從障礙物預處理環節開始尋徑。

3 ?基于改進蟻群算法的消防救援機器人路徑規劃仿真實驗

3.1 ?路徑規劃仿真

將改進蟻群算法的參數設置為螞蟻數目50個、迭代100次、信息素因子及啟發函數因子分別為1個與5個、信息素初始值及初始揮發因子分別為1個與0.5個。路徑規劃仿真時，選取其他研究專家的改進蟻群算法與本文提出的改進蟻群算法進行對比，圖1（a）是基于改進勢場蟻群算法的機器人最優路徑（虛線）及本文所提出算法的規劃路徑（實線）的對比圖，二者最優路徑長度分別是31.56 m與30.97 m，平均路徑分別是31.97 m與31.43 m，而迭代次數分別是8次與9次，仿真10次達到最優路徑的次數分別為9次與8次。由此可見，障礙物相同時，本文所提出的改進蟻群算法雖比迭代次數多出一個，但最短路徑及平均路徑更短。

圖1（b）是利用修改期望值并采用揮發系數自適應方法的改進蟻群算法規劃的路徑（虛線）及本文提出算法路徑（實線）的對比，這2種算法的最優路徑長度均為28.04 m，平均路徑長度分別是30.87 m與29.73 m，迭代次數分別是19次與8次。說明復雜程度、障礙物相同條件下，本文提出的改進蟻群算法平均路徑長度更短，迭代次數更少。而2種算法仿真10次達到最優路徑的次數分別為2次與8次，意味著本文提出的改進蟻群算法穩定性更佳。而后繼續在20 m×20 m、30 m×30 m 2種柵格環境下展開仿真，發現本文提出的攻進蟻群算法均可在較少迭代次數、良好收斂性的基礎上快速找到最優路徑，說明此算法在復雜環境中也較為適用。

3.2 ?算法性能對比

立足全局路徑規劃下將本文提出的改進蟻群算法，分別與傳統蟻群算法及改進勢場蟻群算法進行對比。在已知搭建障礙物信息的情況下，利用柵格法構建環境模型，將環境規模設定為20 m×20 m，柵格邊長設定為1 m，改進蟻群算法的其他參數均與上文相同，在圖2所示的3種不同柵格障礙物設置情況下進行仿真。

分析發現，在復雜度均為20 m×20 m、障礙物也一致的情況下，3種算法結果對比（詳見表１），１＃柵格障礙情況下，本文改進蟻群算法的最優路徑長度與改進勢場蟻群算法相同，而平均路徑長度、迭代次數均優于傳統蟻群算法及改進勢場蟻群算法。

由于最佳性能分析當中，最佳性能指標決定著算法的優化性能[6]，本文改進蟻群算法、改進勢場蟻群算法與被困者位置處的優化距離均有所變短，但根據最佳性能指標分析得知，最佳性能指標數值最小，算法優越性越好，因而，本文提出的改進蟻群算法的優化性能最佳（見表2）。按照同樣方法對不同柵格障礙情況下對3種算法的時間性能、魯棒性能進行分析發現，本文所提出的改進蟻群算法的收斂速度更快、魯棒性也更強。通過3大性能指標對比結果分析，可以得出本文提出的改進蟻群算法具有良好的優勢性能，在消防救援機器人路徑規劃方面更為適用。

4 ?結束語

本文提出的改進蟻群算法，采用分類提取方式從BIM圖中提取建筑空間布局及材料信息，生成機器人可識別的柵格圖，并規劃出最佳救援路徑。通過仿真分析發現，本文提出的改進蟻群算法在最優路徑尋找時具有迭代次數少、收斂性能佳的優勢，且適用于復雜環境，并且最佳性能、時間性能、魯棒性均較為優越，此算法在消防救援機器人救援路徑規劃方面具有較高應用價值。

參考文獻：

[1] 王俊彭，宋屹峰，趙娟平，等.基于蟻群算法的人員疏散機器人路徑規劃方法[J].工業儀表與自動化裝置，2023（4）：77-83，88.

[2] 喬佳，史艷霞，王浩陳.基于改進蟻群算法的森林火災救援機器人三維路徑規劃[J].消防科學與技術，2023，42（7）：989-994.

[3] 王宏北，黃民，黃小龍，等.基于改進蟻群算法的消防機器人路徑規劃[J].北京信息科技大學學報（自然科學版），2021，36（4）：82-87.

[4] 王鉀.基于BIM和優化蟻群算法的建筑消防疏散路徑規劃[D].西安：西安建筑科技大學，2020.

[5] 周鵬.基于BIM和自適應蟻群算法的建筑消防疏散研究[D].西安：西安建筑科技大學，2019.

[6] 鄭家風，田思慶.基于改進蟻群算法的煤礦救援機器人全局路徑規劃研究[J].電腦知識與技術，2018，14（24）：171-172，184.