D*Lite算法下逃生最佳路徑規(guī)劃設(shè)計探析
前言：想要寫出一篇引人入勝的文章？我們特意為您整理了D*Lite算法下逃生最佳路徑規(guī)劃設(shè)計探析范文，希望能給你帶來靈感和參考，敬請閱讀。
摘要：現(xiàn)如今高層建筑增多，建筑結(jié)構(gòu)復(fù)雜，而在逃生規(guī)劃指示方面大多還停留在固定燈光指引，固定的出口指示牌這一階段，當(dāng)發(fā)生火災(zāi)時往往很多人對建筑環(huán)境不熟悉，慌亂中不能準確辨識指示標識，錯失最佳逃生良機，造成大量的人員傷亡。本次研究結(jié)合柵格法建模通過建筑內(nèi)部固定的傳感器監(jiān)測火情，將建筑環(huán)境信息經(jīng)過處理，并合理進行柵格化，運用D*lite增量啟發(fā)式路徑規(guī)劃算法，在瞬息萬變的火場中時刻更新路徑，若將各自的路徑信息同步顯示給受困人員和救援人員，能達到指導(dǎo)作用，提高逃生和救援的效率，大幅降低人員傷亡。
關(guān)鍵詞：D*Lite算法；路徑規(guī)劃；最佳路徑；逃生規(guī)劃
火災(zāi)是現(xiàn)如今最常威脅國家公共安全和社會穩(wěn)定的重大災(zāi)害之一，據(jù)統(tǒng)計近幾年來，我國每年發(fā)生火災(zāi)就有十多萬起，死亡2000多人，傷3000到4000人，造成直接損失高達10億多元人民幣，嚴重威脅人民群眾生命財產(chǎn)安全。隨著高層建筑的日益增多，建筑群日益密集，這樣的環(huán)境復(fù)雜人員流量多，當(dāng)發(fā)生火災(zāi)時，人員往往都是隨波逐流，更容易發(fā)生意外，而且建筑物本身結(jié)構(gòu)和材料具有復(fù)雜性，建筑內(nèi)部裝飾大多易燃，導(dǎo)致煙霧擴散快、火勢大、火災(zāi)撲救困難等特點，如何實現(xiàn)安全、快速、高效的進行逃生，以及救援人員如何快速明確的救援被困人員，這是對于公共安全的一個重大挑戰(zhàn)。生成路徑的算法有很多種，比如Dijkstra算法、A*算法、D*算法、LDP*算法等，其中Dijkstra算法是其中的經(jīng)典算法之一，許多算法都是由此算法演變，A*算法[1]正是如此，改善了Dijkstra算法的盲目式搜索，運用啟發(fā)式搜索，使得搜索范圍縮小，提高了效率。而當(dāng)環(huán)境信息時刻變化時（例如火災(zāi)現(xiàn)場），重復(fù)調(diào)用靜態(tài)環(huán)境路徑規(guī)劃算法已經(jīng)不太適用，在1994年AnthonyStentz提出動態(tài)的A*算法，即D*算法，擬解決在未知環(huán)境下的尋路問題。后在2004年Koenig和Likhachev受到“增量式”搜索的啟示，提出了LDP*算法，它通過收集之前尋路產(chǎn)生的信息，從而在重新規(guī)劃路徑時節(jié)省時間。后他們倆又在LDP*的基礎(chǔ)上提出D*lite算法，解決起點實時變化、終點固定的尋路問題。D*lite算法是先在最初的環(huán)境地圖集中反向搜索并規(guī)劃一條最佳路徑。在其接近目標點的過程中，通過在局部范圍的搜索去應(yīng)對動態(tài)障礙點的出現(xiàn)。通過增量搜索的數(shù)據(jù)再利用直接在受阻礙的當(dāng)前位置重新規(guī)劃出一條最優(yōu)路徑，然后繼續(xù)前進。增量式(啟發(fā)式)搜索算法利用以往問題的經(jīng)驗加快對當(dāng)前問題的搜索，從而加快對相似搜索問題序列的搜索。本文就結(jié)合建筑里固定傳感器反饋的信息，形成一個細粒度的柵格化的“路徑場”，再通過D*lite算法，做出最優(yōu)的路徑規(guī)劃。
1D*Lite路徑規(guī)劃算法
D*Lite算法是由SvenKoenig和MaximLikhachev基于LDP*(LifelongPlanningA*)算法并且結(jié)合A*算法的思想和動態(tài)SWSF-FP的增量啟發(fā)式搜索算法，適合面對周圍環(huán)境未知或者周圍環(huán)境存在動態(tài)變化的場景。算法初始化把所處環(huán)境分為一個個合適的小柵格。算法利用啟發(fā)函數(shù)計算平面上柵格的代價估計值，每個小柵格都可作為一個小節(jié)點，每次都選擇代價估計值最小的節(jié)點作為拓展的最佳節(jié)點，并搜索計算其最近相鄰的8個柵格的代價估計值，以此類推，直到找到目標位置。當(dāng)中途遇到障礙物，進行二次規(guī)劃時，D*Lite算法從目標節(jié)點展開搜索計算周圍節(jié)點，可以利用前一次路徑規(guī)劃所計算出的節(jié)點信息，以此減少重復(fù)計算次數(shù)，提高二次規(guī)劃效率。在首次規(guī)劃路徑時，用g（s）表示從當(dāng)前節(jié)點到終點位置的實際代價值，用啟發(fā)函數(shù)h（s）表示從當(dāng)前節(jié)點到起點位置的估計值。當(dāng)在對當(dāng)前節(jié)點相鄰8個柵格做拓展時，g（s）的值會被重新考量，這樣可以保證其為最小代價值。一個點的rhs值是它的父代節(jié)點中g(shù)值加上這兩點之間的代價中的最小值，相當(dāng)于一個點從父代節(jié)點到達這個點的最小代價。其實在算法的大部分過程中，g值和rhs值是相等的。當(dāng)計算出一個格子的rhs（s），把rhs（s）值賦給g（s），方程如下[2]：（1）D*Lite中引入的rhs(right-handside)，表示相對目標點的估計值，當(dāng)一個點的g=rhs值時稱這個點為局部一致的點，否則稱這個點為局部不一致。其中局部不一致的情況還可細分成為局部過一致和局部欠一致：當(dāng)一個點的g>rhs值時，這個點為局部過一致，通常是有障礙物刪除；當(dāng)一個點的g<rhs值時，這個點為局部欠一致，通常是檢測到了新增的障礙物。通過一個點的局部一致性來判斷當(dāng)前點是否需要計算。它的定義公式如下：（2）啟發(fā)函數(shù)h(s)計算如下：（3）D*Lite中，需要通過兩個k值來判斷一個點的優(yōu)先級，k值越小優(yōu)先級越高，先判斷第一個k1值，如果第一個k1值相等再判斷第二個k2值，算法會優(yōu)先選擇距離終點近的點。它們的公式如下：（4）（5）km表示人移動距離的疊加，初始化時km設(shè)置為0，如果不引入這個參數(shù)的話，當(dāng)檢測障礙物時就需要把優(yōu)先隊列中的全部節(jié)點都重新計算一遍k值，增加了計算量。引入之后就可以一定程度上保證k值的一致性，減少計算量。當(dāng)k1=k2時，路徑規(guī)劃完成，算法規(guī)劃流程如圖1如所示。
2建立柵格及實驗
面對環(huán)境信息，采用柵格法建模將受困人員所處環(huán)境分解成一個個固定大小的柵格，柵格的密度影響了路徑規(guī)劃的精度，但精度過高會導(dǎo)致計算量大幅增加，影響規(guī)劃效率，精度過低容易導(dǎo)致規(guī)劃出來的路徑粗糙，也容易造成穿墻的情況。本文建立了一個20×20的柵格模型為例，模擬火災(zāi)場景如圖2所示。若某一柵格內(nèi)不存在障礙物稱為自由柵格，反之稱為障礙柵格(用黑色格子表示)。柵格法將受困人員抽象為位于柵格中心的一點，將障礙物擴展得到障礙邊界柵格[3]。紅色表示目標點，黃色表示起始點，綠色表示規(guī)劃的路徑，紫色表示地圖上突然出現(xiàn)的障礙物（突發(fā)的火情點，人員通過危險系數(shù)大）。圖3是D*lite初始狀態(tài)下的路徑規(guī)劃，當(dāng)受困人員在前進過程中，不斷檢查該路徑上的柵格是否發(fā)生變化，當(dāng)火情發(fā)生變化，且蔓延到該路徑上時，D*lite將第一次重新規(guī)劃路徑，繞過火情嚴重點如圖4所示，而當(dāng)火情再次蔓延，封住之前規(guī)劃路徑的前進通道時，D*lite將第二次規(guī)劃，選擇另一方向前進抵達目標結(jié)點如圖5所示。
3仿真測試
本文將學(xué)校公共教學(xué)館為模擬環(huán)境，利用Unity3D游戲引擎與BIM構(gòu)建視景仿真系統(tǒng)[4]實現(xiàn)對受困人員逃生規(guī)劃路徑的模擬測試如圖6所示。設(shè)置了2個受困人員為模型，右側(cè)深色部分表示火情嚴重區(qū)，實驗使用D*lite算法自動尋路，結(jié)果分別為兩位受困人員成功規(guī)劃了最短逃生路徑。通過對比常用路徑規(guī)劃算法，D*Lite算法能很好地適用于起點時刻變化，終點不變的未知環(huán)境的路徑規(guī)劃。得力于它的增量啟發(fā)式搜索，使它能在環(huán)境變化時減少重規(guī)劃次數(shù)以及較小的重規(guī)劃影響節(jié)點數(shù)。當(dāng)發(fā)生火災(zāi)時它能以較短的時間高效的規(guī)劃逃生及救援路徑，一定程度上大幅度減少人員傷亡。也能將受困人員換成救援人員，目標位置為無法正常移動的受困人員，使在救援時救援人員準確判斷濃煙滾滾的高層建筑的復(fù)雜環(huán)境，避免黑箱式救援而誤入“死路”，在降低救援人員的傷亡概率的同時，提高救援效率。
作者:張俊 陳偉利 單位:吉林建筑大學(xué)電氣與計算機學(xué)院