基于改進(jìn)蟻群算法的消防救援機(jī)器人路徑規(guī)劃方法

丁金虎

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

關(guān)鍵詞：蟻群算法；算法改進(jìn)；消防救援機(jī)器人；路徑規(guī)劃；BIM技術(shù)

中圖分類號(hào)：TU998.1 ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? ? ? ?文章編號(hào)：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

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

1 ?蟻群算法的原理及實(shí)現(xiàn)步驟

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

2 ?基于改進(jìn)蟻群算法的消防救援機(jī)器人路徑規(guī)劃方法

2.1 ?利用BIM技術(shù)構(gòu)建室內(nèi)環(huán)境模型

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

2.2 ?結(jié)合火場(chǎng)情況改進(jìn)蟻群算法

2.2.1 ?提取更新信息素過(guò)程優(yōu)化

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

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

式中：k表示不小于零的常數(shù)，C表示其他節(jié)點(diǎn)信息素初始化值。得到的可行解能夠繞過(guò)多數(shù)障礙物展開(kāi)搜索，可降低螞蟻尋徑盲目性。之后，應(yīng)以節(jié)點(diǎn)對(duì)最優(yōu)路徑的貢獻(xiàn)為基礎(chǔ)，更改信息素更新規(guī)則，即

式中：Lmin、Lkmin分別表示上次迭代及當(dāng)前迭代次數(shù)的最短路徑，Lbmin是迭徑次數(shù)中的最低值，？琢為調(diào)節(jié)系數(shù)，pathmin表示當(dāng)前迭代次數(shù)中螞蟻路徑為最短路徑，path指當(dāng)前迭代次數(shù)中其他螞蟻的有效路徑。利用此規(guī)則可確保當(dāng)前迭代次數(shù)下，最短路徑節(jié)點(diǎn)間具有最高的信息素濃度，可使法算收斂速度有所提升。為防止全局搜索時(shí)信息素?fù)]發(fā)因子為固定常數(shù)導(dǎo)致搜索效率下降，需對(duì)此因子做出改進(jìn)，即

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

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

為降低下個(gè)最佳節(jié)點(diǎn)選擇難度，應(yīng)在具有可訪問(wèn)性且存在多個(gè)出口指向目標(biāo)的節(jié)點(diǎn)中篩選下一節(jié)點(diǎn)，而節(jié)點(diǎn)附近障礙物數(shù)量是節(jié)點(diǎn)能否正確獲取的影響因素，二者成反比關(guān)系。為此，應(yīng)添加概率因子Pij，概率因子的計(jì)算公式為

式中：C（8，N）表示節(jié)點(diǎn)j附近障礙物所有可能分布的情況個(gè)數(shù)，C（8-N-1，1）則為節(jié)點(diǎn)j出口分布情況個(gè)數(shù)，根據(jù)此公式可以得到新啟發(fā)函數(shù)定義公式

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

2.2.3 ?躲避特定障礙物

為避免利用蟻群算法求解時(shí)出現(xiàn)螞蟻被困在半封閉障礙物中，導(dǎo)致有效循環(huán)參與螞蟻數(shù)量不足引發(fā)算法運(yùn)算效率降低問(wèn)題，致使機(jī)器人救援時(shí)間延長(zhǎng)而增大被困人員安全隱患。需要設(shè)定螞蟻進(jìn)入半封閉式障礙空間的條件限制，達(dá)到特定條件下，便自動(dòng)解除螞蟻循環(huán)。尋找路徑螞蟻位置坐標(biāo)及目標(biāo)點(diǎn)坐標(biāo)分別為（i，j）與（S，E）時(shí)，螞蟻跳出循環(huán)的必要條件有4個(gè)，一是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個(gè)條件之一時(shí)，說(shuō)明螞蟻進(jìn)入了半封閉障礙物中，此時(shí)應(yīng)使螞蟻跳出循環(huán)，并將螞蟻當(dāng)前所在位置的節(jié)點(diǎn)權(quán)值調(diào)整為0[4]。

2.2.4 ?選擇逃生路徑

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

2.3 ?改進(jìn)蟻群算法在全局路徑規(guī)劃中的實(shí)現(xiàn)

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

3 ?基于改進(jìn)蟻群算法的消防救援機(jī)器人路徑規(guī)劃仿真實(shí)驗(yàn)

3.1 ?路徑規(guī)劃仿真

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

圖1（b）是利用修改期望值并采用揮發(fā)系數(shù)自適應(yīng)方法的改進(jìn)蟻群算法規(guī)劃的路徑（虛線）及本文提出算法路徑（實(shí)線）的對(duì)比，這2種算法的最優(yōu)路徑長(zhǎng)度均為28.04 m，平均路徑長(zhǎng)度分別是30.87 m與29.73 m，迭代次數(shù)分別是19次與8次。說(shuō)明復(fù)雜程度、障礙物相同條件下，本文提出的改進(jìn)蟻群算法平均路徑長(zhǎng)度更短，迭代次數(shù)更少。而2種算法仿真10次達(dá)到最優(yōu)路徑的次數(shù)分別為2次與8次，意味著本文提出的改進(jìn)蟻群算法穩(wěn)定性更佳。而后繼續(xù)在20 m×20 m、30 m×30 m 2種柵格環(huán)境下展開(kāi)仿真，發(fā)現(xiàn)本文提出的攻進(jìn)蟻群算法均可在較少迭代次數(shù)、良好收斂性的基礎(chǔ)上快速找到最優(yōu)路徑，說(shuō)明此算法在復(fù)雜環(huán)境中也較為適用。

3.2 ?算法性能對(duì)比

立足全局路徑規(guī)劃下將本文提出的改進(jìn)蟻群算法，分別與傳統(tǒng)蟻群算法及改進(jìn)勢(shì)場(chǎng)蟻群算法進(jìn)行對(duì)比。在已知搭建障礙物信息的情況下，利用柵格法構(gòu)建環(huán)境模型，將環(huán)境規(guī)模設(shè)定為20 m×20 m，柵格邊長(zhǎng)設(shè)定為1 m，改進(jìn)蟻群算法的其他參數(shù)均與上文相同，在圖2所示的3種不同柵格障礙物設(shè)置情況下進(jìn)行仿真。

分析發(fā)現(xiàn)，在復(fù)雜度均為20 m×20 m、障礙物也一致的情況下，3種算法結(jié)果對(duì)比（詳見(jiàn)表１），１＃柵格障礙情況下，本文改進(jìn)蟻群算法的最優(yōu)路徑長(zhǎng)度與改進(jìn)勢(shì)場(chǎng)蟻群算法相同，而平均路徑長(zhǎng)度、迭代次數(shù)均優(yōu)于傳統(tǒng)蟻群算法及改進(jìn)勢(shì)場(chǎng)蟻群算法。

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

4 ?結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 喬佳，史艷霞，王浩陳.基于改進(jìn)蟻群算法的森林火災(zāi)救援機(jī)器人三維路徑規(guī)劃[J].消防科學(xué)與技術(shù)，2023，42（7）：989-994.

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

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

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

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