蟻群算法在多障礙場所疏散路徑規劃中的應用

張嘉琪 張言

摘要：文章將柵格蟻群算法應用于多障礙場所的人員動態疏散中，對該算法提出了一些改進方法，使其搜索效率得到了一定的提高，針對所研究對象具有多障礙物、難疏散的特點，根據火災發生時場所環境的變化特點，對場所環境進行動態分析，規劃出在最大限度保證人員安全的前提下的最短路徑，使人員在緊急情況下安全快速地所找到出口，避免緊急情況下找不到出路盲目逃生，大大提高了疏散效率，減少人員傷亡。仿真模擬結果顯示，該算法是解決動態疏散路徑規劃問題的有效方法。

關鍵詞：安全；蟻群算法；多障礙場所；路徑規劃

隨著建筑行業的發展，建筑物種類和結構越來越多樣化，然而建筑火災也隨之發生地越來越頻繁，由于火災造成的人員傷亡和經濟損失極為嚴重。尤其是多障礙物的公共場所，由于場所障礙物較多，人員對場所的環境也不熟悉，所以一旦發生火災，逃生極為困難。當發生火災的時候人員的恐慌和從眾心理使得群眾盲目逃生，傳統疏散指示圖達不到預期的疏散效果，而且火災發生時火焰和煙氣態勢的發展變化，造成路徑通行能力的動態變化，而目前建筑物中普遍使用的大多為固定方向式指示標志，存在著當安全出口附近發生火災時會將人員引向危險區域的隱患。蟻群算法是受到自然界中螞蟻覓食行為啟發而提出的一種仿生進化算法。研究發現，當發生火災時，人員逃生特性和蟻群覓食有一定的相似性，因此，根據蟻群算法對建筑空間進行網格模型劃分，定義和描述建筑空間各網格的靜態屬性和動態屬性；根據火災報警系統提供的火警信息搜索人員疏散的最優路徑，利用軟件程序控制技術，實現路徑優化算法和消防探測控制系統的數據傳遞，通過控制程序把最優路徑快速規劃出來，這樣人們可以很直觀地看到當前最優逃生路徑，避免在障礙物較多的場所找不到出口，減少了盲目逃生帶來的恐慌。

一、環境模型的建立

將要規劃路徑的區域劃分成大小相同的柵格，將原本有障礙物的柵格標記為不可行區域，剩下的柵格就是正常情況下的可行區域。在可行區域定點安裝溫度和煙氣傳感器，火災發生時，如果某區域內的溫度和煙氣傳感器數值有任何一個超過了安全閾值，則該區域內的柵格被自動定義為障礙柵格，路徑只能在可行區域內規劃。

影響動態疏散的因素有現場溫度、煙氣濃度以及人群擁擠狀況等，對這些因素加以權重分析得出每個柵格的風險值，根據風險最小的原則來規劃路徑。用下面的函數來確定由柵格i轉移到柵格j的風險值大小

式中T、C、ρ分別表示各柵格對應的溫度、危險氣體濃度和人流密度，a、b、c為相應的權重系數， 表示從柵格i到柵格j的路線長度。最優疏散路徑 即從當前點到出口累計風險值最小的一條路徑

二、柵格蟻群算法的原理及改進

1.傳統蟻群算法的原理

設要規劃路徑的起點為S點，目標為O點。螞蟻從起點S出發尋找路徑，只能從其所在柵格的相鄰柵格中選擇一個前行。第k只螞蟻在t時刻從柵格i選擇柵格j行走的概率為：

表示第k只螞蟻在時段（t，t+1）留在路徑（i，j）上的信息素，列迭代之后，螞蟻最佳的路徑上，從而使算法收斂。

2.蟻群算法的改進

對于路徑規劃問題，柵格蟻群算法存在可優化空間。

因為在火災逃生中螞蟻搜索的目標是已知的，所以可以使用目標函數啟發法提高螞蟻搜索效率，引入啟發函數h（x）如下：

其中，啟發因子c是一個大于0的常數，決定了螞蟻受目標啟發的程度，c越大螞蟻受到的啟發強度越大。引入該啟發函數后，螞蟻的狀態轉移概率變為：

改進之后在進行動態路徑規劃時可以減少循環次數，從而快速得到較好的路徑規劃結果。

三、蟻群算法的流程

設表示啟發因子和信息揮發率。

第一步：初始化m、x、α、β、c、ρ、x、y等參數；

第二步：判斷本次規劃是不是首次規劃，如果是，將信息素初始化為常數；否則將信息素設定為上次規劃保存的信息素值；

第三步：當x小于y時進入循環，否則轉到第八步；

第四步：對每一只螞蟻從起點開始按照式（7）選擇下一個柵格搜索路徑直到找到目標。如果沒有找到目標則讓其回到起點重新搜索并且失敗次數加一。若失敗次數累計達到最大允許失敗次數z則程序結束并返回未找到路徑；

第五步：對每只螞蟻找到的路徑與全局最佳路徑比較，如果比全局最佳路徑更好則將該路徑更新全局最佳路徑；

第六步：對全局最佳的路徑按照式（8）更新信息素；

第七步：循環計數x加一，轉到第三步；

第八步：保存本次規劃時螞蟻產生的信息素；

第九步：程序結束，將全局最佳路徑作為結果輸出。

四、仿真實驗

為了驗證柵格蟻群算法在多障礙區域的路徑規劃效果，選取某超市作為試驗樣本，

在LabVIEW2015開發環境下將實驗模型的建筑平面圖轉換為在該環境下可用的簡易地圖。并在LabView2015開發環境下將算法程序按照前文所述的方法和流程編寫出來。

運行該程序，在前面板添加兩個標識點S和O，分別代表起點和出口，該程序規劃結果如圖中L1，即為從起點S到出口O的最短路徑，用時60毫秒。如果在這條路徑上選擇一點A設置為障礙點，并重新規劃路徑，則該程序規劃結果如圖中L2，即為在避開該障礙點A的前提下，從起點S到出口O的最短路徑，用時71毫秒。

五、實驗結論

該仿真實驗結果表明，在多障礙場所利用改進后的柵格蟻群算法規劃逃生路徑是安全可行的，該算法既能保證避開障礙物，也可以實時動態避開危險區域，并且在此前提下迅速規劃出最短的逃生路線。

參考文獻：

陳慶全.基于蟻群算法的動態人員疏散模擬[J].軟件時空，2012，（10）：424-426.

段鵬飛.面向大型場館疏散的改進多蟻群算法[J].計算機應用研究，2013，（02）：357-359.

趙容齊.基于人工勢場法的機器人路徑規劃研究[D].山東：山東大學，2008.

王樹西，吳政學.改進的Dijkstra最短路徑算法及其應用研究[J].計算機科學，2012，（05）：223-228.

王榮，江東，韓惠.基于Floyd方法的最短路徑算法優化算法[J].甘肅科學學報，2012，（04）：110-114.

石鐵峰.改進遺傳算法在移動機器人路徑規劃中的應用[J].計算機仿真，2011，（04）：193-195.

邱莉莉.基于改進蟻群算法的機器人路徑規劃[D].上海：東華大學，2015.