D*Lite算法下逃生最佳路徑規劃設計探析

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了D*Lite算法下逃生最佳路徑規劃設計探析范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要：現如今高層建筑增多，建筑結構復雜，而在逃生規劃指示方面大多還停留在固定燈光指引，固定的出口指示牌這一階段，當發生火災時往往很多人對建筑環境不熟悉，慌亂中不能準確辨識指示標識，錯失最佳逃生良機，造成大量的人員傷亡。本次研究結合柵格法建模通過建筑內部固定的傳感器監測火情，將建筑環境信息經過處理，并合理進行柵格化，運用D*lite增量啟發式路徑規劃算法，在瞬息萬變的火場中時刻更新路徑，若將各自的路徑信息同步顯示給受困人員和救援人員，能達到指導作用，提高逃生和救援的效率，大幅降低人員傷亡。

關鍵詞：D*Lite算法；路徑規劃；最佳路徑；逃生規劃

火災是現如今最常威脅國家公共安全和社會穩定的重大災害之一，據統計近幾年來，我國每年發生火災就有十多萬起，死亡2000多人，傷3000到4000人，造成直接損失高達10億多元人民幣，嚴重威脅人民群眾生命財產安全。隨著高層建筑的日益增多，建筑群日益密集，這樣的環境復雜人員流量多，當發生火災時，人員往往都是隨波逐流，更容易發生意外，而且建筑物本身結構和材料具有復雜性，建筑內部裝飾大多易燃，導致煙霧擴散快、火勢大、火災撲救困難等特點，如何實現安全、快速、高效的進行逃生，以及救援人員如何快速明確的救援被困人員，這是對于公共安全的一個重大挑戰。生成路徑的算法有很多種，比如Dijkstra算法、A*算法、D*算法、LDP*算法等，其中Dijkstra算法是其中的經典算法之一，許多算法都是由此算法演變，A*算法[1]正是如此，改善了Dijkstra算法的盲目式搜索，運用啟發式搜索，使得搜索范圍縮小，提高了效率。而當環境信息時刻變化時（例如火災現場），重復調用靜態環境路徑規劃算法已經不太適用，在1994年AnthonyStentz提出動態的A*算法，即D*算法，擬解決在未知環境下的尋路問題。后在2004年Koenig和Likhachev受到“增量式”搜索的啟示，提出了LDP*算法，它通過收集之前尋路產生的信息，從而在重新規劃路徑時節省時間。后他們倆又在LDP*的基礎上提出D*lite算法，解決起點實時變化、終點固定的尋路問題。D*lite算法是先在最初的環境地圖集中反向搜索并規劃一條最佳路徑。在其接近目標點的過程中，通過在局部范圍的搜索去應對動態障礙點的出現。通過增量搜索的數據再利用直接在受阻礙的當前位置重新規劃出一條最優路徑，然后繼續前進。增量式(啟發式)搜索算法利用以往問題的經驗加快對當前問題的搜索，從而加快對相似搜索問題序列的搜索。本文就結合建筑里固定傳感器反饋的信息，形成一個細粒度的柵格化的“路徑場”，再通過D*lite算法，做出最優的路徑規劃。

1D*Lite路徑規劃算法

D*Lite算法是由SvenKoenig和MaximLikhachev基于LDP*(LifelongPlanningA*)算法并且結合A*算法的思想和動態SWSF-FP的增量啟發式搜索算法，適合面對周圍環境未知或者周圍環境存在動態變化的場景。算法初始化把所處環境分為一個個合適的小柵格。算法利用啟發函數計算平面上柵格的代價估計值，每個小柵格都可作為一個小節點，每次都選擇代價估計值最小的節點作為拓展的最佳節點，并搜索計算其最近相鄰的8個柵格的代價估計值，以此類推，直到找到目標位置。當中途遇到障礙物，進行二次規劃時，D*Lite算法從目標節點展開搜索計算周圍節點，可以利用前一次路徑規劃所計算出的節點信息，以此減少重復計算次數，提高二次規劃效率。在首次規劃路徑時，用g（s）表示從當前節點到終點位置的實際代價值，用啟發函數h（s）表示從當前節點到起點位置的估計值。當在對當前節點相鄰8個柵格做拓展時，g（s）的值會被重新考量，這樣可以保證其為最小代價值。一個點的rhs值是它的父代節點中g值加上這兩點之間的代價中的最小值，相當于一個點從父代節點到達這個點的最小代價。其實在算法的大部分過程中，g值和rhs值是相等的。當計算出一個格子的rhs（s），把rhs（s）值賦給g（s），方程如下[2]：（1）D*Lite中引入的rhs(right-handside)，表示相對目標點的估計值，當一個點的g=rhs值時稱這個點為局部一致的點，否則稱這個點為局部不一致。其中局部不一致的情況還可細分成為局部過一致和局部欠一致：當一個點的g>rhs值時，這個點為局部過一致，通常是有障礙物刪除；當一個點的g<rhs值時，這個點為局部欠一致，通常是檢測到了新增的障礙物。通過一個點的局部一致性來判斷當前點是否需要計算。它的定義公式如下：（2）啟發函數h(s)計算如下：（3）D*Lite中，需要通過兩個k值來判斷一個點的優先級，k值越小優先級越高，先判斷第一個k1值，如果第一個k1值相等再判斷第二個k2值，算法會優先選擇距離終點近的點。它們的公式如下：（4）（5）km表示人移動距離的疊加，初始化時km設置為0，如果不引入這個參數的話，當檢測障礙物時就需要把優先隊列中的全部節點都重新計算一遍k值，增加了計算量。引入之后就可以一定程度上保證k值的一致性，減少計算量。當k1=k2時，路徑規劃完成，算法規劃流程如圖1如所示。

2建立柵格及實驗

面對環境信息，采用柵格法建模將受困人員所處環境分解成一個個固定大小的柵格，柵格的密度影響了路徑規劃的精度，但精度過高會導致計算量大幅增加，影響規劃效率，精度過低容易導致規劃出來的路徑粗糙，也容易造成穿墻的情況。本文建立了一個20×20的柵格模型為例，模擬火災場景如圖2所示。若某一柵格內不存在障礙物稱為自由柵格，反之稱為障礙柵格(用黑色格子表示)。柵格法將受困人員抽象為位于柵格中心的一點，將障礙物擴展得到障礙邊界柵格[3]。紅色表示目標點，黃色表示起始點，綠色表示規劃的路徑，紫色表示地圖上突然出現的障礙物（突發的火情點，人員通過危險系數大）。圖3是D*lite初始狀態下的路徑規劃，當受困人員在前進過程中，不斷檢查該路徑上的柵格是否發生變化，當火情發生變化，且蔓延到該路徑上時，D*lite將第一次重新規劃路徑，繞過火情嚴重點如圖4所示，而當火情再次蔓延，封住之前規劃路徑的前進通道時，D*lite將第二次規劃，選擇另一方向前進抵達目標結點如圖5所示。

3仿真測試

本文將學校公共教學館為模擬環境，利用Unity3D游戲引擎與BIM構建視景仿真系統[4]實現對受困人員逃生規劃路徑的模擬測試如圖6所示。設置了2個受困人員為模型，右側深色部分表示火情嚴重區，實驗使用D*lite算法自動尋路，結果分別為兩位受困人員成功規劃了最短逃生路徑。通過對比常用路徑規劃算法，D*Lite算法能很好地適用于起點時刻變化，終點不變的未知環境的路徑規劃。得力于它的增量啟發式搜索，使它能在環境變化時減少重規劃次數以及較小的重規劃影響節點數。當發生火災時它能以較短的時間高效的規劃逃生及救援路徑，一定程度上大幅度減少人員傷亡。也能將受困人員換成救援人員，目標位置為無法正常移動的受困人員，使在救援時救援人員準確判斷濃煙滾滾的高層建筑的復雜環境，避免黑箱式救援而誤入“死路”，在降低救援人員的傷亡概率的同時，提高救援效率。

作者:張俊 陳偉利 單位:吉林建筑大學電氣與計算機學院