連云霞+樊永生+余紅英+楊臻

摘 要： 針對(duì)傳統(tǒng)D*Lite算法存在的頻繁轉(zhuǎn)彎、過于靠近障礙物的問題提出改進(jìn)D*Lite算法。該算法使用煙花算法中的映射規(guī)則將過于靠近障礙物的格子判定在安全范圍之外，并使用煙花算法對(duì)D*Lite算法規(guī)劃好的路徑中的關(guān)鍵轉(zhuǎn)折點(diǎn)間的路徑進(jìn)行二次規(guī)劃以減少不必要的轉(zhuǎn)彎。路徑規(guī)劃結(jié)果顯示，所提出的改進(jìn)D*Lite算法能夠?qū)崿F(xiàn)虛擬士兵最優(yōu)路徑搜索并且效率更高。仿真結(jié)果分析表明，所提出的算法比已有的改進(jìn)D*Lite算法更優(yōu)，可以有效減少路徑中不必要的轉(zhuǎn)彎，且使路徑與障礙物保持合適的距離。

關(guān)鍵詞： D*Lite算法； 煙花算法； 虛擬士兵； 路徑規(guī)劃； 關(guān)鍵轉(zhuǎn)折點(diǎn)； 路徑平滑

中圖分類號(hào)： TN915.5?34； TP391.9 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）06?0023?05

Abstract： Aiming at the problems of virtual soldiers′ frequent turning and close proximity to obstacles in the traditional D*Lite algorithm， an improved D*Lite algorithm is proposed. In the algorithm， the mapping rules in firework algorithm are used to determine the lattice too close to the obstacle beyond the safe range. The firework algorithm is used to make secondary planning for the path between the key turning points in the path planned by D*Lite algorithm， so as to reduce unnecessary turns. The path planning results show that the improved D*Lite algorithm can achieve the optimal path search for virtual soldiers and has high efficiency. The analysis of simulation results show that the proposed algorithm is better than the existing improved D*Lite algorithm， can effectively reduce unnecessary turns in the path， and keep an appropriate distance between path and obstacles.

Keywords： D*Lite algorithm； firework algorithm； virtual soldier； path planning； key turning point； path smoothing

0 引 言

隨著國(guó)防事業(yè)的迅猛發(fā)展，越來越多的高端技術(shù)被應(yīng)用到軍事理論與實(shí)際工作中[1]。在虛擬戰(zhàn)場(chǎng)中，將尋路算法應(yīng)用到虛擬士兵[2]路徑規(guī)劃問題中，為虛擬士兵規(guī)劃出一條安全快捷的路徑，使虛擬士兵模擬真實(shí)情況繞過障礙物，付出最小的代價(jià)沿著這條路徑從起始位置到達(dá)目標(biāo)位置[3]，從而有效提高仿真真實(shí)性。

D*Lite算法是一種高效的動(dòng)態(tài)路徑規(guī)劃方法。文獻(xiàn)[4]使用D*Lite算法解決了在不確定環(huán)境下目標(biāo)移動(dòng)時(shí)的無人飛行器三維航跡規(guī)劃問題。D*Lite算法也存在著不足。算法長(zhǎng)度優(yōu)先，所以搜索到的路徑存在頻繁轉(zhuǎn)彎。此外，算法在路徑規(guī)劃中只有遇到障礙物時(shí)才重新搜索最短可行路徑，因此所規(guī)劃路徑可能會(huì)過于靠近障礙物。此前有不少人對(duì)D*Lite算法進(jìn)行了改進(jìn)。張浩、孫新柱提出增強(qiáng)D*Lite算法[5]，針對(duì)復(fù)雜障礙物的可優(yōu)化路徑給出路徑優(yōu)化方法；張曉冉、居鶴華在D*Lite算法中引入Bresenham畫線算法[6]，并通過建立分辨率高于全局障礙圖的局部障礙圖實(shí)時(shí)重規(guī)劃?rùn)C(jī)器人當(dāng)前位置到目標(biāo)點(diǎn)的最優(yōu)路徑。但上述方法都存在一定的局限性，并不完全適用于本文的仿真，所以本文提出一種新的改進(jìn)D*Lite算法。

本文針對(duì)D*Lite算法的不足引入煙花算法，利用改進(jìn)后的D*Lite算法進(jìn)行路徑規(guī)劃。通過Unity3D游戲引擎設(shè)計(jì)了平原環(huán)境中的虛擬士兵作戰(zhàn)仿真，使自動(dòng)尋路可視化，并與張曉冉等人的改進(jìn)D*Lite算法進(jìn)行對(duì)比，將理論付諸實(shí)踐，對(duì)路徑規(guī)劃問題具有指導(dǎo)意義。

1 地形信息建模

路徑規(guī)劃首先需要考慮地圖建模。所研究仿真為虛擬士兵在平原環(huán)境中的作戰(zhàn)仿真，地形中設(shè)置輪胎、墻等來模擬戰(zhàn)場(chǎng)中士兵的隱蔽物。

采用柵格地圖對(duì)士兵所處平原環(huán)境進(jìn)行建模。將虛擬戰(zhàn)場(chǎng)的三維空間轉(zhuǎn)變成有限的二維空間，并將虛擬戰(zhàn)場(chǎng)所占空間區(qū)域劃分為固定大小的柵格，柵格的大小稱為柵格粒度，其大小的確定需要考慮地圖的尺寸、虛擬士兵的移速、虛擬士兵的尺寸等。如果粒度過小，計(jì)算量就會(huì)變大，降低路徑規(guī)劃的時(shí)效性；如果粒度過于大，會(huì)導(dǎo)致所規(guī)劃的路徑不精準(zhǔn)，顯得粗糙[7]。

把虛擬戰(zhàn)場(chǎng)中的柵格映射到空間坐標(biāo)系中，將虛擬士兵的活動(dòng)空間離散化為在橫軸上坐標(biāo)從1～10，在縱軸上坐標(biāo)從A～J的二維坐標(biāo)系，如圖1所示。endprint

柵格化后的地圖模型如圖2所示。

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

D*Lite算法是一種常用、高效的動(dòng)態(tài)路徑規(guī)劃算法。該算法利用啟發(fā)函數(shù)計(jì)算二維平面上節(jié)點(diǎn)的代價(jià)估計(jì)值，每次選擇具有最小代價(jià)估計(jì)值的節(jié)點(diǎn)作為最佳擴(kuò)展方向，并迭代搜索計(jì)算周圍8個(gè)格子的代價(jià)估計(jì)值，直到找到目標(biāo)位置[8]。進(jìn)行二次規(guī)劃時(shí)，D*Lite算法從目標(biāo)節(jié)點(diǎn)展開扇形搜索，可以再次利用前一次路徑規(guī)劃所計(jì)算出的信息，減少重復(fù)計(jì)算，提高二次規(guī)劃效率。

D*Lite算法在首次路徑規(guī)劃時(shí)，用g（s）表示從出發(fā)點(diǎn)到當(dāng)前位置的代價(jià)值，用啟發(fā)函數(shù)h（s）表示從當(dāng)前位置到出發(fā)位置的啟發(fā)值。g（s）是從目標(biāo)位置前往當(dāng)前位置的最小代價(jià)值，在對(duì)當(dāng)前位置周圍8個(gè)格子做擴(kuò)展時(shí)，g（s）會(huì)被重新計(jì)算，這樣可以保證其為最小代價(jià)值。當(dāng)計(jì)算出一個(gè)格子的rhs（s），把rhs（s）值賦給g（s），方程如下：

[g（s）=rhs（s）] （1）

式中，rhs（s）表示Right Hand Side的值，表示相對(duì)目標(biāo)點(diǎn)的估計(jì)值。其計(jì)算公式如下：

[rhs（s）=0， s=sgoalmins′∈Pred（s）（g（s′）+c（s′，s））， others] （2）

而h（s）的計(jì)算公式為：

[h（s，sstart）=0， s=sstartc（s，s′）+h（s′，sgoal）， others] （3）

k1和k2作為優(yōu)先隊(duì)列排列參數(shù)，虛擬士兵在分析周圍格子時(shí)會(huì)計(jì)算格子的這兩個(gè)參數(shù)，將最小k1值格子選為下一格子。k1和k2的計(jì)算公式如下：

[k1（s）=min（g（s），rhs（s））+h（s）] （4）

[k2（s）=min（g（s），rhs（s））] （5）

當(dāng)k1和k2相等時(shí)，路徑規(guī)劃完成。D*Lite路徑規(guī)劃算法的流程圖如圖3所示。

3.1 煙花算法

煙花算法是近年來提出的全局最優(yōu)算法，有著良好的優(yōu)化性能。煙花算法主要由爆炸算子、變異操作、映射規(guī)則和選擇策略四部分組成[9]。其主要思想是通過交互傳遞信息（直接或間接地）使群體對(duì)環(huán)境的適應(yīng)性逐代變得越來越好，從而求得全局最優(yōu)解或足夠接近最優(yōu)解的近似解。在煙花算法中，對(duì)下一代的選擇引入免疫濃度思想，在選擇時(shí)與火花相似的火花越多，火花被選中的概率就越小，保證了火花的多樣性[10]。

3.2 改進(jìn)D*Lite算法路徑規(guī)劃

將煙花算法引入D*Lite算法，利用煙花算法的映射規(guī)則保證所規(guī)劃路徑與障礙物保持合適距離，然后通過煙花算法對(duì)關(guān)鍵轉(zhuǎn)折點(diǎn)之間的路徑進(jìn)行平滑處理，從而實(shí)現(xiàn)虛擬士兵作戰(zhàn)仿真中最優(yōu)路徑規(guī)劃。

仿真過程中，改進(jìn)D*Lite路徑規(guī)劃算法的流程圖如圖4所示。

具體步驟如下：

1） 將虛擬士兵感知到的環(huán)境格子化，如圖5所示。圖5中用格子S表示士兵所在的位置，也就是路徑的出發(fā)位置，用格子Y表示戰(zhàn)場(chǎng)中的目標(biāo)地點(diǎn)，黑色格子表示在虛擬士兵在行進(jìn)過程中遇到的障礙，劃線格子表示地圖上的威脅。

2） 規(guī)劃最優(yōu)路徑。應(yīng)用煙花算法中的映射規(guī)則，對(duì)可以行走的區(qū)域里的格子進(jìn)行安全等級(jí)的判定，這樣虛擬士兵在路徑規(guī)劃時(shí)就可以將過于靠近障礙物的格子判定在安全范圍之外，從而優(yōu)先選擇相對(duì)安全的格子，實(shí)現(xiàn)遠(yuǎn)離存在復(fù)雜障礙物的危險(xiǎn)區(qū)域、減少干擾的目的。然后使用D*Lite算法規(guī)劃路徑，所規(guī)劃路徑如圖6所示。

3） 選取關(guān)鍵轉(zhuǎn)折點(diǎn)。從D*Lite算法所規(guī)劃的路徑點(diǎn)組合中的第二個(gè)路徑點(diǎn)開始，如果這個(gè)節(jié)點(diǎn)的方向和前一鄰近的節(jié)點(diǎn)的父節(jié)點(diǎn)一致，那么就可以認(rèn)為該相鄰節(jié)點(diǎn)為冗余節(jié)點(diǎn)，刪除掉這個(gè)節(jié)點(diǎn)并更新路徑點(diǎn)組合；這樣按順序處理所有規(guī)劃的路徑節(jié)點(diǎn)，最后得到只包含起始點(diǎn)、轉(zhuǎn)折點(diǎn)和目標(biāo)點(diǎn)的路徑點(diǎn)組合，稱為關(guān)鍵轉(zhuǎn)折點(diǎn)。

4） 構(gòu)建適應(yīng)度函數(shù)。煙花算法中，使用適應(yīng)度度量煙花或火花在優(yōu)化計(jì)算中接近于最優(yōu)解的優(yōu)良程度，而煙花算法會(huì)根據(jù)適應(yīng)度以及火花到最優(yōu)個(gè)體的距離來決定其是否保留，所以適應(yīng)度會(huì)影響到算法的收斂性和穩(wěn)定性，進(jìn)而對(duì)算法的效率產(chǎn)生直接影響[11]。同時(shí)考慮路徑的長(zhǎng)短以及作戰(zhàn)中的隱蔽需求，用式（6）來表達(dá)某一路徑的代價(jià)值：

[C=12i=1nj=1npij] （6）

選取下式作為個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)：

[T=Pmax-C， C

式中，Pmax是一個(gè)合適的，相對(duì)較大的數(shù)。

5） 關(guān)鍵轉(zhuǎn)折點(diǎn)間路徑平滑。從起始點(diǎn)開始，選定兩個(gè)相近的關(guān)鍵轉(zhuǎn)折點(diǎn)作為出發(fā)位置和目標(biāo)位置。將兩個(gè)關(guān)鍵轉(zhuǎn)折點(diǎn)間的二維空間進(jìn)行再次柵格化。然后煙花算法初始化，隨機(jī)生成N個(gè)煙花，每一個(gè)煙花個(gè)體代表一條路徑。路徑由出發(fā)位置和目標(biāo)位置間的路徑點(diǎn)連線形成。根據(jù)適應(yīng)度函數(shù)計(jì)算每一個(gè)煙花的適應(yīng)度的值，并根據(jù)適應(yīng)度值產(chǎn)生火花。

6） 位移和變異操作。讓群體中的每個(gè)火花經(jīng)歷位移操作和變異操作。位移操作是對(duì)煙花的每一維進(jìn)行位移，表達(dá)式如下：

[Δxki=xki+rand（0，Ai）] （8）

式中，rand（0，Ai）表示在幅度Ai內(nèi)生成的均勻隨機(jī)數(shù)。為進(jìn)一步提高種群的多樣性，在煙花算法中引入了高斯變異[12]。在煙花種群中隨機(jī)選擇一個(gè)煙花，對(duì)選擇到的煙花再選擇一定數(shù)量的維度進(jìn)行高斯變異。

通過煙花的爆炸、火花的選擇，即可產(chǎn)生一條在兩個(gè)鄰近關(guān)鍵轉(zhuǎn)折點(diǎn)間的近似最優(yōu)路徑。所有的關(guān)鍵轉(zhuǎn)折點(diǎn)之間路徑優(yōu)化過后，即生成全局最優(yōu)路徑，如圖7所示。

7） 檢查環(huán)境參數(shù)變化。虛擬士兵前進(jìn)過程中，檢查路徑上相關(guān)格子是否發(fā)生變化。當(dāng)環(huán)境信息發(fā)生變化且這種變化對(duì)最優(yōu)路徑上格子的參數(shù)有影響時(shí)，D*Lite的路徑規(guī)劃結(jié)果以及更新的格子如圖8所示。

如果虛擬戰(zhàn)場(chǎng)環(huán)境信息變化，但是這種改變對(duì)已有最優(yōu)路徑無影響，即不會(huì)影響現(xiàn)有的路徑規(guī)劃結(jié)果，則算法不更新路徑。在圖7的基礎(chǔ)上加入一個(gè)障礙格子和威脅格子，如圖9所示。可知，D*Lite算法不會(huì)更新和擴(kuò)展其他格子。

4 仿真測(cè)試與結(jié)果分析

4.1 仿真模塊功能與實(shí)現(xiàn)

利用Unity3D游戲引擎構(gòu)建視景仿真系統(tǒng)實(shí)現(xiàn)對(duì)虛擬士兵作戰(zhàn)仿真過程中所規(guī)劃路徑的測(cè)試。設(shè)置三個(gè)虛擬士兵在同等條件下持相同槍械在平原環(huán)境中進(jìn)行作戰(zhàn)仿真，士兵A使用D*Lite算法進(jìn)行自動(dòng)尋路，士兵B使用文獻(xiàn)[6]提出的改進(jìn)D*Lite算法進(jìn)行自動(dòng)尋路，士兵C使用本文提出的改進(jìn)D*Lite算法進(jìn)行自動(dòng)尋路，通過比較幾種算法所規(guī)劃路徑的平滑度以及是否距離障礙物過近來判斷算法的優(yōu)劣性。

使用D*Lite算法規(guī)劃的虛擬士兵A的路徑如圖10所示。由圖10可知，D*Lite所規(guī)劃的路徑轉(zhuǎn)彎頻繁，與真實(shí)士兵路徑相差較大。

使用文獻(xiàn)[6]改進(jìn)D*Lite算法規(guī)劃的虛擬士兵B的路徑如圖11所示。由圖11可知，該改進(jìn)D*Lite算法所規(guī)劃的路徑雖然沒有冗余轉(zhuǎn)彎，但是過于靠近障礙物。

使用本文提出的改進(jìn)D*Lite算法規(guī)劃的虛擬士兵C的路徑如圖12所示。由圖12可知，利用本文提出的改進(jìn)D*Lite算法所規(guī)劃的路徑更加平滑，不存在多余轉(zhuǎn)彎，并且路徑與障礙物距離合適，符合虛擬士兵作戰(zhàn)仿真對(duì)于路徑規(guī)劃的要求。

4.2 仿真結(jié)果分析

通過程序驅(qū)動(dòng)虛擬士兵作戰(zhàn)仿真系統(tǒng)對(duì)改進(jìn)D*Lite算法在路徑規(guī)劃中的優(yōu)化應(yīng)用進(jìn)行驗(yàn)證。經(jīng)過多次測(cè)試，所得試驗(yàn)數(shù)據(jù)見表1。由數(shù)據(jù)可得，本文提出的改進(jìn)D*Lite算法效率高、適應(yīng)性強(qiáng)，搜尋到的路徑轉(zhuǎn)折次數(shù)明顯減少且相對(duì)D*Lite算法和已有的改進(jìn)D*Lite算法更優(yōu)。

5 結(jié) 語

本文使用煙花算法對(duì)D*Lite算法進(jìn)行改進(jìn)，有效地減少了所規(guī)劃路徑中不必要的轉(zhuǎn)彎，并解決了路徑過于靠近障礙物的問題。通過對(duì)比相同條件下利用D*Lite算法、已有的改進(jìn)D*Lite算法以及本文所提出的改進(jìn)D*Lite算法進(jìn)行自動(dòng)尋路的三個(gè)虛擬士兵的路徑，驗(yàn)證了利用煙花算法改進(jìn)D*Lite算法的優(yōu)越性，為虛擬士兵在虛擬戰(zhàn)場(chǎng)的路徑規(guī)劃提供了新的思路，也增強(qiáng)了虛擬士兵作戰(zhàn)仿真的實(shí)用性，為虛擬士兵班組動(dòng)態(tài)對(duì)抗路徑規(guī)劃研究打下堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)

[1] 張育軍.虛擬現(xiàn)實(shí)技術(shù)在軍事領(lǐng)域的應(yīng)用與發(fā)展[J].科技創(chuàng)新與應(yīng)用，2014（15）：290?291.

ZHANG Yujun. The application and development of virtual reality technology in the military field [J]. Technology innovation and applications， 2014（15）： 290?291.

[2] 榮明，李小龍，王欽釗，等.三維虛擬士兵建模與仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2012，24（4）：843?847.

RONG Ming， LI Xiaolong， WANG Qinzhao， et al. Modeling and simulation of 3D virtual soldiers [J]. Journal of system simulation， 2012， 24（4）： 843?847.

[3] 吳潤(rùn)方，王魯.A*尋路算法在即時(shí)戰(zhàn)略游戲中的應(yīng)用[J].科技廣場(chǎng)，2016（4）：164?166.

WU Runfang， WANG Lu. Application of A* routing algorithm in instant strategic game [J]. Science mosaic， 2016（4）： 164?166.

[4] 陳俠，劉冬.應(yīng)用D*Lite算法的目標(biāo)移動(dòng)時(shí)無人機(jī)三維航跡規(guī)劃[J].電光與控制，2013，20（7）：1?5.

CHEN Xia， LIU Dong. An improved D*Lite algorithm based 3D path planning for UAVs when target is moving [J]. Electronics optics & control， 2013， 20（7）： 1?5.

[5] 張浩，孫新柱.增強(qiáng)D*Lite在自主移動(dòng)機(jī)器人安全路徑規(guī)劃中應(yīng)用[J].河北工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，31（2）：89?92.

ZHANG Hao， SUN Xinzhu. Application of improved D* Lite in security path planning of autonomous mobile robot [J]. Journal of Hebei University of Engineering （Natural science edition）， 2014， 31（2）： 89?92.

[6] 張曉冉，居鶴華.采用改進(jìn)D*Lite算法的自主移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)測(cè)量與控制，2011，19（1）：155?157.

ZHANG Xiaoran， JU Hehua. Path planning of autonomous mobile robot using improved D*Lite algorithm [J]. Computer measurement and control， 2011， 19（1）： 155?157.endprint

[7] 李凱業(yè).基于改進(jìn)分層D*搜索算法的室內(nèi)路徑規(guī)劃問題研究[D].合肥：合肥工業(yè)大學(xué)，2015.

LI Kaiye. Research on indoor path planning based on improved hierarchical D*search algorithm [D]. Hefei： Hefei University of Technology， 2015.

[8] 隨裕猛，陳賢富，劉斌.D?star Lite算法及其動(dòng)態(tài)路徑規(guī)劃實(shí)驗(yàn)研究[J].微型機(jī)與應(yīng)用，2015，34（7）：16?19.

SUI Yumeng， CHEN Xianfu， LIU Bin. D?star Lite algorithm and its experimental study on dynamic path planning [J]. Microcomputer and its applications， 2015， 34（7）： 16?19.

[9] 朱啟兵，王震宇，黃敏.帶有引力搜索算子的煙花算法[J].控制與決策，2016，31（10）：1853?1859.

ZHU Qibing， WANG Zhenyu， Huang Min. Fireworks algorithm with gravitational search operator [J]. Control and decision， 2016， 31（10）： 1853?1859.

[10] 張以文，吳金濤，趙姝，等.基于改進(jìn)煙花算法的Web服務(wù)組合優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2016，22（2）：422?432.

ZHANG Yiwen， WU Jintao， ZHAO Shu， et al. Optimization service composition based on improved firework algorithm [J]. Computer integrated manufacturing systems， 2016， 22（2）： 422?432.

[11] 胡慶生.煙花算法及其應(yīng)用[D].西安：陜西師范大學(xué)，2016.

HU Qingsheng. Fireworks algorithm and its application [D]. Xian： Shaanxi Normal University， 2016.

[12] 陳璇，樊永生，余紅英，等.自適應(yīng)煙花算法在重型裝備裝載中的應(yīng)用[J].科學(xué)技術(shù)與工程，2016，16（25）：296?300.

CHEN Xuan， FAN Yongsheng， YU Hongying， et al. Application of adaptive algorithm of fireworks in the heavy equipment loading [J]. Science technology and engineering， 2016， 16（25）： 296?300.endprint