改進D*Lite算法在虛擬士兵路徑規劃中的應用

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

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

關鍵詞： D*Lite算法； 煙花算法； 虛擬士兵； 路徑規劃； 關鍵轉折點； 路徑平滑

中圖分類號： 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 引 言

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

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

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

1 地形信息建模

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

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

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

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

2 D*Lite路徑規劃算法

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

D*Lite算法在首次路徑規劃時，用g（s）表示從出發點到當前位置的代價值，用啟發函數h（s）表示從當前位置到出發位置的啟發值。g（s）是從目標位置前往當前位置的最小代價值，在對當前位置周圍8個格子做擴展時，g（s）會被重新計算，這樣可以保證其為最小代價值。當計算出一個格子的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作為優先隊列排列參數，虛擬士兵在分析周圍格子時會計算格子的這兩個參數，將最小k1值格子選為下一格子。k1和k2的計算公式如下：

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

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

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

3.1 煙花算法

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

3.2 改進D*Lite算法路徑規劃

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

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

具體步驟如下：

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

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

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

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

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

選取下式作為個體適應度評價函數：

[T=Pmax-C， C

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

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

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

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

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

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

7） 檢查環境參數變化。虛擬士兵前進過程中，檢查路徑上相關格子是否發生變化。當環境信息發生變化且這種變化對最優路徑上格子的參數有影響時，D*Lite的路徑規劃結果以及更新的格子如圖8所示。

如果虛擬戰場環境信息變化，但是這種改變對已有最優路徑無影響，即不會影響現有的路徑規劃結果，則算法不更新路徑。在圖7的基礎上加入一個障礙格子和威脅格子，如圖9所示。可知，D*Lite算法不會更新和擴展其他格子。

4 仿真測試與結果分析

4.1 仿真模塊功能與實現

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

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

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

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

4.2 仿真結果分析

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

5 結 語

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

參考文獻

[1] 張育軍.虛擬現實技術在軍事領域的應用與發展[J].科技創新與應用，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].系統仿真學報，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*尋路算法在即時戰略游戲中的應用[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] 陳俠，劉冬.應用D*Lite算法的目標移動時無人機三維航跡規劃[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在自主移動機器人安全路徑規劃中應用[J].河北工程大學學報（自然科學版），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算法的自主移動機器人路徑規劃[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] 李凱業.基于改進分層D*搜索算法的室內路徑規劃問題研究[D].合肥：合肥工業大學，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算法及其動態路徑規劃實驗研究[J].微型機與應用，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服務組合優化[J].計算機集成制造系統，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] 胡慶生.煙花算法及其應用[D].西安：陜西師范大學，2016.

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

[12] 陳璇，樊永生，余紅英，等.自適應煙花算法在重型裝備裝載中的應用[J].科學技術與工程，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