D*Lite算法下逃生最佳路徑規(guī)劃設(shè)計(jì)探析

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

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

關(guān)鍵詞：D*Lite算法；路徑規(guī)劃；最佳路徑；逃生規(guī)劃

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

1D*Lite路徑規(guī)劃算法

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

2建立柵格及實(shí)驗(yàn)

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

3仿真測試

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

作者:張俊 陳偉利 單位:吉林建筑大學(xué)電氣與計(jì)算機(jī)學(xué)院