改進D*Lite算法在虛擬士兵路徑規(guī)劃中的應(yīng)用

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

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

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

中圖分類號： TN915.5?34； TP391.9 文獻標識碼： A 文章編號： 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 引 言

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

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

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

1 地形信息建模

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

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

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

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

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

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

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

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

式中，rhs（s）表示Right Hand Side的值，表示相對目標點的估計值。其計算公式如下：

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

而h（s）的計算公式為：

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

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

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

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

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

3.1 煙花算法

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

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

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

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

具體步驟如下：

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

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

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

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

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

選取下式作為個體適應(yīng)度評價函數(shù)：

[T=Pmax-C， C

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 仿真結(jié)果分析

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

5 結(jié) 語

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

參考文獻

[1] 張育軍.虛擬現(xiàn)實技術(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é)報，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] 吳潤方，王魯.A*尋路算法在即時戰(zhàn)略游戲中的應(yīng)用[J].科技廣場，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算法的目標移動時無人機三維航跡規(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] 張浩，孫新柱.增強D*Lite在自主移動機器人安全路徑規(guī)劃中應(yīng)用[J].河北工程大學(xué)學(xué)報（自然科學(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] 張曉冉，居鶴華.采用改進D*Lite算法的自主移動機器人路徑規(guī)劃[J].計算機測量與控制，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è).基于改進分層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算法及其動態(tài)路徑規(guī)劃實驗研究[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] 張以文，吳金濤，趙姝，等.基于改進煙花算法的Web服務(wù)組合優(yōu)化[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