改進(jìn)煙花算法在虛擬士兵路徑規(guī)劃中的應(yīng)用

樊永生,連云霞,楊 臻

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

0 概述

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

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

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

1.1 士兵三維模型和動(dòng)作模型的建立

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

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

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

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

1.2 士兵視覺(jué)模型的建立

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

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

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

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

3)分析可見(jiàn)性;

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

5)生成感知能力。

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

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

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

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

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

圖4 地圖模型

2 改進(jìn)煙花算法

2.1 改進(jìn)煙花算法介紹

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

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

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

(1)

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

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

(2)

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

(3)

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

位移操作是對(duì)煙花路徑個(gè)體的每一維進(jìn)行位移,其表達(dá)式如式(4)所示。

(4)

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

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

(5)

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

2.2 改進(jìn)煙花算法流程

改進(jìn)煙花算法的流程如圖5所示。

圖5 改進(jìn)煙花算法自動(dòng)尋路流程

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

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

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

pij=(1-θij)eij

(6)

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

(7)

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

(8)

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

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

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

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

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

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

3 仿真實(shí)現(xiàn)

3.1 仿真模塊的功能

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

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

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

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

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

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

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

1)士兵A使用A*算法,士兵B(niǎo)使用改進(jìn)煙花算法。

2)士兵A使用A*算法,士兵B(niǎo)使用煙花算法。

3)士兵A使用改進(jìn)煙花算法,士兵B(niǎo)使用煙花算法。

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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