基于D*Lite 算法的逃生最佳路徑規(guī)劃設(shè)計(jì)

張 俊 陳偉利

（吉林建筑大學(xué)電氣與計(jì)算機(jī)學(xué)院，吉林 長(zhǎng)春 130000）

火災(zāi)是現(xiàn)如今最常威脅國(guó)家公共安全和社會(huì)穩(wěn)定的重大災(zāi)害之一，據(jù)統(tǒng)計(jì)近幾年來(lái)，我國(guó)每年發(fā)生火災(zāi)就有十多萬(wàn)起，死亡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ò)散快、火勢(shì)大、火災(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)場(chǎng)），重復(fù)調(diào)用靜態(tài)環(huán)境路徑規(guī)劃算法已經(jīng)不太適用，在1994 年Anthony Stentz 提出動(dòng)態(tài)的A*算法，即D*算法，擬解決在未知環(huán)境下的尋路問(wèn)題。后在2004 年Koenig 和Likhachev 受到“增量式”搜索的啟示，提出了LDP*算法，它通過(guò)收集之前尋路產(chǎn)生的信息，從而在重新規(guī)劃路徑時(shí)節(jié)省時(shí)間。后他們倆又在LDP*的基礎(chǔ)上提出D*lite 算法，解決起點(diǎn)實(shí)時(shí)變化、終點(diǎn)固定的尋路問(wèn)題。

D*lite 算法是先在最初的環(huán)境地圖集中反向搜索并規(guī)劃一條最佳路徑。在其接近目標(biāo)點(diǎn)的過(guò)程中，通過(guò)在局部范圍的搜索去應(yīng)對(duì)動(dòng)態(tài)障礙點(diǎn)的出現(xiàn)。通過(guò)增量搜索的數(shù)據(jù)再利用直接在受阻礙的當(dāng)前位置重新規(guī)劃出一條最優(yōu)路徑，然后繼續(xù)前進(jìn)。增量式(啟發(fā)式)搜索算法利用以往問(wèn)題的經(jīng)驗(yàn)加快對(duì)當(dāng)前問(wèn)題的搜索，從而加快對(duì)相似搜索問(wèn)題序列的搜索。本文就結(jié)合建筑里固定傳感器反饋的信息，形成一個(gè)細(xì)粒度的柵格化的“路徑場(chǎng)”，再通過(guò)D*lite 算法，做出最優(yōu)的路徑規(guī)劃。

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

D*Lite 算法是由Sven Koenig 和Maxim Likhachev 基于LDP*(Lifelong Planning A*)算法并且結(jié)合A*算法的思想和動(dòng)態(tài)SWSF-FP 的增量啟發(fā)式搜索算法，適合面對(duì)周?chē)h(huán)境未知或者周?chē)h(huán)境存在動(dòng)態(tài)變化的場(chǎng)景。

算法初始化把所處環(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ì)值，以此類(lèi)推，直到找到目標(biāo)位置。當(dāng)中途遇到障礙物，進(jìn)行二次規(guī)劃時(shí)，D*Lite 算法從目標(biāo)節(jié)點(diǎn)展開(kāi)搜索計(jì)算周?chē)?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í)在算法的大部分過(guò)程中，g 值和rhs 值是相等的。當(dāng)計(jì)算出一個(gè)格子的rhs（s），把rhs（s）值賦給g（s），方程如下[2]：

D* Lite 中引入的rhs(right-hand side)，表示相對(duì)目標(biāo)點(diǎn)的估計(jì)值，當(dāng)一個(gè)點(diǎn)的g=rhs 值時(shí)稱(chēng)這個(gè)點(diǎn)為局部一致的點(diǎn)，否則稱(chēng)這個(gè)點(diǎn)為局部不一致。其中局部不一致的情況還可細(xì)分成為局部過(guò)一致和局部欠一致：當(dāng)一個(gè)點(diǎn)的g＞rhs 值時(shí)，這個(gè)點(diǎn)為局部過(guò)一致，通常是有障礙物刪除；當(dāng)一個(gè)點(diǎn)的g＜rhs 值時(shí)，這個(gè)點(diǎn)為局部欠一致，通常是檢測(cè)到了新增的障礙物。通過(guò)一個(gè)點(diǎn)的局部一致性來(lái)判斷當(dāng)前點(diǎn)是否需要計(jì)算。它的定義公式如下：

D*Lite 中，需要通過(guò)兩個(gè)k 值來(lái)判斷一個(gè)點(diǎn)的優(yōu)先級(jí)，k 值越小優(yōu)先級(jí)越高，先判斷第一個(gè)k1 值，如果第一個(gè)k1 值相等再判斷第二個(gè)k2 值，算法會(huì)優(yōu)先選擇距離終點(diǎn)近的點(diǎn)。它們的公式如下：

km表示人移動(dòng)距離的疊加，初始化時(shí)km設(shè)置為0，如果不引入這個(gè)參數(shù)的話(huà)，當(dāng)檢測(cè)障礙物時(shí)就需要把優(yōu)先隊(duì)列中的全部節(jié)點(diǎn)都重新計(jì)算一遍k 值，增加了計(jì)算量。引入之后就可以一定程度上保證k 值的一致性，減少計(jì)算量。當(dāng)k1=k2時(shí)，路徑規(guī)劃完成，算法規(guī)劃流程如圖1 如所示。

圖1 D*lite 算法流程圖

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

面對(duì)環(huán)境信息，采用柵格法建模將受困人員所處環(huán)境分解成一個(gè)個(gè)固定大小的柵格，柵格的密度影響了路徑規(guī)劃的精度，但精度過(guò)高會(huì)導(dǎo)致計(jì)算量大幅增加，影響規(guī)劃效率，精度過(guò)低容易導(dǎo)致規(guī)劃出來(lái)的路徑粗糙，也容易造成穿墻的情況。本文建立了一個(gè)20×20 的柵格模型為例，模擬火災(zāi)場(chǎng)景如圖2 所示。若某一柵格內(nèi)不存在障礙物稱(chēng)為自由柵格，反之稱(chēng)為障礙柵格(用黑色格子表示)。柵格法將受困人員抽象為位于柵格中心的一點(diǎn)，將障礙物擴(kuò)展得到障礙邊界柵格[3]。紅色表示目標(biāo)點(diǎn)，黃色表示起始點(diǎn)，綠色表示規(guī)劃的路徑，紫色表示地圖上突然出現(xiàn)的障礙物（突發(fā)的火情點(diǎn)，人員通過(guò)危險(xiǎn)系數(shù)大）。

圖2 初始地圖柵格場(chǎng)景

圖3 是D*lite 初始狀態(tài)下的路徑規(guī)劃，當(dāng)受困人員在前進(jìn)過(guò)程中，不斷檢查該路徑上的柵格是否發(fā)生變化，當(dāng)火情發(fā)生變化，且蔓延到該路徑上時(shí)，D*lite 將第一次重新規(guī)劃路徑，繞過(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 初始路徑規(guī)劃

圖4 第一次重規(guī)劃

圖5 第二次重規(guī)劃

3 仿真測(cè)試

本文將學(xué)校公共教學(xué)館為模擬環(huán)境，利用Unity3D 游戲引擎與BIM構(gòu)建視景仿真系統(tǒng)[4]實(shí)現(xiàn)對(duì)受困人員逃生規(guī)劃路徑的模擬測(cè)試如圖6 所示。設(shè)置了2 個(gè)受困人員為模型，右側(cè)深色部分表示火情嚴(yán)重區(qū)，實(shí)驗(yàn)使用D*lite 算法自動(dòng)尋路，結(jié)果分別為兩位受困人員成功規(guī)劃了最短逃生路徑。

圖6 公共教學(xué)館仿真測(cè)試

4 結(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)位置為無(wú)法正常移動(dòng)的受困人員，使在救援時(shí)救援人員準(zhǔn)確判斷濃煙滾滾的高層建筑的復(fù)雜環(huán)境，避免黑箱式救援而誤入“死路”，在降低救援人員的傷亡概率的同時(shí)，提高救援效率。