改進煙花算法在虛擬士兵路徑規劃中的應用

樊永生,連云霞,楊 臻

(中北大學 a.大數據學院; b.機電工程學院,太原 030051)

0 概述

路徑規劃是虛擬作戰技術[1]研究中的重要領域,利用尋路算法使虛擬士兵以最小代價從起始位置到達目標位置[2],從而提高虛擬士兵的存活率。文獻[3]將感知模型與路徑規劃相結合,能夠提高虛擬士兵路徑規劃的效率和能力,對路徑規劃行為進行精確模擬。文獻[4]通過A*算法實現在三維場景中獲取兩點之間的尋路路線。文獻[5]將A*算法應用到虛擬船員路徑規劃當中,實現虛擬船員的路徑規劃。但A*算法的復雜度和尋路能力與柵格細化程度相關,且所規劃的路徑轉折頻繁、效率較低,不符合真實士兵的前進方式。蟻群算法[6]、遺傳算法等其他智能算法存在搜索機制不佳、容易陷入局部最優等問題,因此,研究虛擬士兵的路徑規劃問題具有重要意義。作為具有爆炸式搜索機制的新型群體智能算法,煙花算法在求解復雜優化問題方面有較好的性能。文獻[7]將煙花算法融入到免疫遺傳算法中,形成煙花爆炸式免疫算法。文獻[8]提出線性權重法與煙花算法結合的混合算法,解決了多目標無人機任務規劃問題。但煙花算法的變異操作會導致煙花個體變成“不連續”路徑。

本文將可視圖法、士兵視覺模型與改進煙花算法相結合，提出一種基于改進煙花算法的路徑規劃算法。使用Unity3D游戲引擎將路徑規劃過程可視化，并將所提算法與煙花算法、A*算法進行比較分析。

1 虛擬士兵及環境建模

1.1 士兵三維模型和動作模型的建立

虛擬士兵是作戰仿真的關鍵支撐技術。在作戰仿真中,依據人的真實骨骼架構與骨骼關聯,構建以骨骼為基礎、具有高還原度的虛擬士兵模型[9],如圖1所示。

圖1 士兵骨骼架構

虛擬士兵的基礎動作建模包括站立、站著跑、蹲下瞄準和開槍,如圖2所示。

圖2 虛擬士兵3種基礎動作建模

1.2 士兵視覺模型的建立

虛擬士兵視覺模型的設計主要體現視覺的有限性特征,仿真人眼使行為更加逼真。視覺模型通過對感知對象是否在虛擬士兵視覺范圍內的可見性分析,結合記憶腳本模塊之前的信息判斷對象是否可見,最終生成感知能力。

模型的建立分為以下步驟:

1)確定虛擬士兵的視覺范圍;

2)判斷敵方目標或障礙物威脅是否在視覺范圍之內;

3)分析可見性;

4)結合記憶腳本判斷敵方目標或障礙物威脅是否可見;

5)生成感知能力。

根據人眼視度,即人的肉眼可視角度的度數,水平視度120°,縱向視度60°構建士兵視覺感知模型觸發器,當有敵方目標或障礙物威脅進入該區域時即被觸發器識別,如圖3所示。

圖3 虛擬士兵視覺觸發器

1.3 平原環境地形建模

虛擬士兵在平原環境中進行對抗,可在地形中設置有輪胎、障礙墻等隱蔽物。可視圖法[10-11]建模時間短,占用儲存空間小,因此,使用可視圖法處理地形數據。

以障礙物為基礎,用近似凸多邊形表示障礙物,構建電子地圖。然后把虛擬士兵的出發位置、障礙物多邊形的頂點以及目標位置用線段連接,并保證這些線不會與障礙物相交,這些線即為“可視線”,而構成“可視線”的端點即為“可視點”,形成一張“可視圖”,采用搜索算法尋找從起始點到目標點的最優路徑。通過可視圖法建立的地圖模型如圖4所示,在障礙物的頂點中確定最優的、最適合放到路徑中的頂點,由頂點的連接線段穿行于空間中的多邊形障礙物之間,從起始點通往目標點的任何一條最短路徑,都是一條多邊形路徑,其中,內部節點是地圖模型中的頂點。

圖4 地圖模型

2 改進煙花算法

2.1 改進煙花算法介紹

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

煙花個體變異時產生的變化是隨機的,因此可能會出現“不連續”路徑。本文在煙花算法中加入插入和刪除操作,一方面可以消除“不連續”路徑,另一方面可以對路徑進行進一步優化。同時,將士兵視覺模型與算法結合,加強士兵對環境威脅的判斷,有利于規劃出更加安全的路徑。

煙花算法使用適應度度量煙花路徑個體或火花路徑個體可能達到或是接近最優解的優良程度,而改進煙花算法會根據適應度以及火花路徑個體到最優個體的距離來決定其是否保留。在爆炸中每個煙花路徑個體產生的火花數量Si為:

(1)

其中,Si表示第i個煙花路徑個體產生的火花路徑個體個數,m用來限制產生的火花路徑個體總數,Ymax是當前種群中適應度值最差路徑個體的適應度值,f(xi)表示路徑個體xi的適應度值,ε是績效常數,以避免出現分母為零的情況。

采用式(2)限制每個煙花路徑個體產生火花路徑個體的數量,即:

(2)

每個煙花路徑個體的爆炸幅度Ai如式(3)所示。

(3)

路徑個體經過位移操作和變異操作,使用映射規則保證變異后的路徑個體處于可行域內,以避免算法陷入局部最優。

位移操作是對煙花路徑個體的每一維進行位移,其表達式如式(4)所示。

(4)

其中,rand(0,Ai)表示在幅度Ai內生成的均勻隨機數。

為進一步提高種群的多樣性,在改進煙花算法中引入了高斯變異。在煙花種群中隨機選擇煙花路徑個體,對其選擇一定數量的維度進行高斯變異。高斯變異如式(5)所示。

(5)

變異操作會使路徑出現間斷(相鄰兩路徑點間的連線穿過障礙物的內部),引入插入操作處理間斷路徑。刪除操作是用來刪除煙花或火花之中2個一樣的路徑點之間的冗余路徑點以及相同路徑點中的1個,簡化路徑。

2.2 改進煙花算法流程

改進煙花算法的流程如圖5所示。

圖5 改進煙花算法自動尋路流程

2.3 改進煙花算法在路徑規劃中的應用

本文改進煙花算法在路徑規劃中的應用如下:

1)構建適應度函數。對抗仿真需要考慮路徑的長短和隱蔽需求,路徑中某一線段的代價值為:

pij=(1-θij)eij

(6)

其中,eij表示從i節點到j節點的線段長度,θij為隱蔽系數,其值在0到1之間,值越大則表示隱蔽程度越好。路徑的代價值可表示為:

(7)

其中,n表示這條路徑通過路徑點(去除起點和終點)的數量。在路徑規劃過程中,需要優先考慮路徑代價值最小,因此個體適應度評價函數如式(8)所示。

(8)

其中,Pmax是一個合適且相對較大的數。

2)在戰場中虛擬士兵根據視覺感知判斷路徑點是否存在危險。對于障礙物和威脅,士兵將信息記錄下來并與記憶腳本進行對比,如果記憶庫沒有該威脅,則加入,由此做出決斷。給定對抗仿真的初始和目標位置,對于存在危險的路徑點,直接排除在外,然后將剩余的路徑點作為路徑規劃的路徑點,把起始點、目標點和中間路徑點用線段連接起來。算法初始化,將連接出發點和目標點的所有線段作為解空間,在解空間中隨機生成N個煙花,將最優煙花的爆炸半徑設置為整個搜索空間,每一個煙花個體代表一條路徑。路徑由路徑點組合形成。

每個煙花個體使用符號標記,設共有n個路徑點和m條線段,假設起始點為S,目標點為G,用wi(i=1,2,…,n)表示路徑點,一條具體的路徑P:S→w12→w16→w23→G可以用節點序列{12,16,23}表示,序列的數字是路徑點wi的下標,其中不包括起點和終點。如果用bj做wi的下標,則P煙花可以表示為(wb12,wb16,wb23)。

群體中的路徑個體進行位移和變異操作。位移是將所選煙花路徑個體中某部分路徑點序列進行如式(4)所示的位移操作。變異即引入高斯變異,在煙花路徑種群中隨機選擇煙花,對所選煙花再選擇一定數量的維度執行高斯變異。比如,該條路徑中包含7個路徑點,則可以選擇7維中隨機維進行如式(5)所示的變異。

5)判斷是否需要刪除操作。刪除路徑個體中2個一樣的路徑點之間的冗余路徑點,同時刪除兩相同路徑點中的1個,實現路徑的簡化。然后對煙花路徑個體或火花路徑個體節點序列的第i(i=1,2,…,n)位操作,判斷兩點wbj-1和wbj+1之間可否成為連續可通行路徑,若是則刪除wbj,否則不執行刪除操作。

6)根據路徑點的數量設定合適的迭代次數,計算最優路徑。由于爆炸半徑是趨于減小的,因此若迭代次數夠大、火花數量夠多,算法收斂,最優解存在,即最優路徑存在。

3 仿真實現

3.1 仿真模塊的功能

采用Unity3D游戲引擎[14-15]構建視景仿真系統,將路徑規劃過程可視化,并記錄相關數據。該模塊主要實現以下功能:

1)實現主控制界面與士兵路徑規劃界面的人性化交互。

2)士兵路徑規劃算法選擇及初始化設置。

3)對士兵路徑規劃算法的應用增加槍械對抗測試,在界面實時顯示作戰情況,并將評估結果顯示在NGUI界面中。

3.2 仿真模塊的具體實現

該模塊主要是將虛擬士兵路徑規劃過程可視化。在對抗仿真中,虛擬士兵分別使用本文算法、A*算法和煙花算法進行尋路,然后將每種算法規劃的路徑進行對比。

虛擬士兵在平原環境中使用某型步槍進行對抗仿真,仿真分3組進行:

1)士兵A使用A*算法,士兵B使用改進煙花算法。

2)士兵A使用A*算法,士兵B使用煙花算法。

3)士兵A使用改進煙花算法,士兵B使用煙花算法。

每組仿真中槍械參數和士兵生命數相同,有一方士兵犧牲則生命數減1,同時重新規劃路徑,直至生命數為0,2個虛擬士兵規劃路徑長度相同,但起始點和目標點的位置隨機出現在地圖中的固定區域。

每組仿真中虛擬士兵根據每次的路徑規劃到達目標位置開始對抗,雙方命中率計算公式相同。為使仿真結果更有說服力,每組士兵進行50次測試。測試結束后,顯示評估結果,其中,每次測試數據通過文本儲存,平均路徑長度、平均規劃時間和命中率在界面顯示,可視化過程如圖6所示。

圖6 虛擬士兵路徑規劃可視化過程

在第1組仿真測試中,參與對抗仿真的2個虛擬士兵路徑如圖7所示。從圖7可以看出,使用A*算法尋路的士兵A與使用改進煙花算法尋路的士兵B相比,A*算法路徑轉彎頻繁,效率較低,可得出改進煙花算法簡捷高效,可行性高。

圖7 第1組仿真中虛擬士兵的路徑

在第2組和第3組仿真測試中,虛擬士兵使用煙花算法進行自動尋路路徑如圖8所示。由圖8可以看出,使用煙花算法所規劃的路徑“穿過”障礙物的內部,路徑不可行。第2組和第3組中士兵B均使用煙花算法尋路,故2組不可行。

圖8 煙花算法規劃路徑

由3組仿真可以看出,改進煙花算法在進行路徑規劃時優于煙花算法和A*算法。

為了使仿真結果更加真實可靠,設計第4組仿真。士兵A使用改進煙花算法,士兵B使用A*算法,測試50次。第1組和第4組的仿真數據結果如表1所示。從表1可以看出,與A*算法相比,改進煙花算法規劃的路徑平均長度減少約21%,平均規劃時間減少約45%,平均轉彎次數明顯減少。此外,利用改進煙花算法進行自動尋路的士兵在相同條件下的命中率更高,證實改進煙花算法的優越性和可行性。

表1 第1組和第4組仿真數據結果

4 結束語

針對虛擬士兵在作戰仿真中路徑規劃存在“不連續”的問題,本文在煙花算法中加入插入和刪除操作,結合視景仿真系統真實地再現對抗仿真中的路徑規劃。仿真結果表明,與A*算法、煙花算法相比,改進煙花算法具有較強的搜索能力,能夠減少路徑長度,節省規劃時間,且命中率較高。該方法為虛擬戰場中的路徑規劃提供新的思路和方法，也可廣泛應用于虛擬行人視覺模型路徑規劃。