樊永生,連云霞,楊 臻

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

0 概述

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

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

1 虛擬士兵及環(huán)境建模

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

虛擬士兵是作戰(zhàn)仿真的關(guān)鍵支撐技術(shù)。在作戰(zhàn)仿真中,依據(jù)人的真實骨骼架構(gòu)與骨骼關(guān)聯(lián),構(gòu)建以骨骼為基礎(chǔ)、具有高還原度的虛擬士兵模型[9],如圖1所示。

圖1 士兵骨骼架構(gòu)

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

圖2 虛擬士兵3種基礎(chǔ)動作建模

1.2 士兵視覺模型的建立

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

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

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

2)判斷敵方目標(biāo)或障礙物威脅是否在視覺范圍之內(nèi);

3)分析可見性;

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

5)生成感知能力。

根據(jù)人眼視度,即人的肉眼可視角度的度數(shù),水平視度120°,縱向視度60°構(gòu)建士兵視覺感知模型觸發(fā)器,當(dāng)有敵方目標(biāo)或障礙物威脅進入該區(qū)域時即被觸發(fā)器識別,如圖3所示。

圖3 虛擬士兵視覺觸發(fā)器

1.3 平原環(huán)境地形建模

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

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

圖4 地圖模型

2 改進煙花算法

2.1 改進煙花算法介紹

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

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

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

(1)

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

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

(2)

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

(3)

路徑個體經(jīng)過位移操作和變異操作,使用映射規(guī)則保證變異后的路徑個體處于可行域內(nèi),以避免算法陷入局部最優(yōu)。

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

(4)

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

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

(5)

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

2.2 改進煙花算法流程

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

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

2.3 改進煙花算法在路徑規(guī)劃中的應(yīng)用

本文改進煙花算法在路徑規(guī)劃中的應(yīng)用如下:

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

pij=(1-θij)eij

(6)

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

(7)

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

(8)

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

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

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

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

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

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

3 仿真實現(xiàn)

3.1 仿真模塊的功能

采用Unity3D游戲引擎[14-15]構(gòu)建視景仿真系統(tǒng),將路徑規(guī)劃過程可視化,并記錄相關(guān)數(shù)據(jù)。該模塊主要實現(xiàn)以下功能:

1)實現(xiàn)主控制界面與士兵路徑規(guī)劃界面的人性化交互。

2)士兵路徑規(guī)劃算法選擇及初始化設(shè)置。

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

3.2 仿真模塊的具體實現(xiàn)

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

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

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

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

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

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

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

圖6 虛擬士兵路徑規(guī)劃可視化過程

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

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

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

圖8 煙花算法規(guī)劃路徑

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

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

表1 第1組和第4組仿真數(shù)據(jù)結(jié)果

4 結(jié)束語

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