基于A*算法的地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線選擇模型研究*

陳寶印 申 銘 黃 橫 張廣品

(防空兵指揮學(xué)院研究生16隊(duì)1) 鄭州 450052)(75240部隊(duì)2) 潮州 521041)(73136部隊(duì)3) 廈門 361023)

1 引言

地空導(dǎo)彈部隊(duì)主要擔(dān)負(fù)的是地面部隊(duì)和重點(diǎn)目標(biāo)的對(duì)空安全等任務(wù)。由于擔(dān)負(fù)任務(wù)的特殊性,其成為敵人打擊的重點(diǎn)。兵力機(jī)動(dòng)是提高地空導(dǎo)彈部隊(duì)生存能力和再次抓住戰(zhàn)機(jī)的有效途徑。1999年南斯拉夫的地空導(dǎo)彈部隊(duì)在抗擊北約的空襲中就進(jìn)一步說明地空導(dǎo)彈機(jī)動(dòng)靈活作戰(zhàn)是保護(hù)自己、消滅敵人的有效方法之一。然而,在機(jī)動(dòng)的過程中機(jī)動(dòng)路線可能有多條,如何快速、隱蔽、安全的到達(dá)指定地域,是指揮員在選擇機(jī)動(dòng)路線時(shí)必須面對(duì)的現(xiàn)實(shí)問題。同時(shí)在機(jī)動(dòng)的過程中,影響的因素很多,從分析影響地空導(dǎo)彈部隊(duì)機(jī)動(dòng)因素出發(fā),應(yīng)用A*算法定量的給出選擇地空導(dǎo)彈部隊(duì)最佳機(jī)動(dòng)路線的數(shù)學(xué)模型,為指揮員在戰(zhàn)時(shí)的輔助決策支持提供了依據(jù)。

2 影響地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的因素及量化

圖1 影響因素

正確分析確定地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線的影響因素,是機(jī)動(dòng)路線問題的前提。影響地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線的因素很多,為簡便起見,主要考慮線路的路長、線路的路況、線路上的障礙(如壕溝、涵洞、橋梁和水深)、線路的隱蔽性、部隊(duì)的自身防護(hù)能力和當(dāng)時(shí)的氣象條件等影響因素,如圖1所示。設(shè)每一影響因素的量化值為Ekji,其中k、j表示節(jié)點(diǎn)編號(hào),i表示第i個(gè)影響因素(k=1,2,3,…,n-1;j=2,3,4,…,n;i=1,2,3,…,6)。同時(shí),這些因素又包含其子因素。各子因素量化值為Ekjir建立數(shù)學(xué)模型就要綜合考慮衡量這六個(gè)因素,從而選擇一條最佳的機(jī)動(dòng)路線。

2.1 路長因素及量化

路長:地空導(dǎo)彈部隊(duì)機(jī)動(dòng)所經(jīng)過路段的實(shí)際長度。在地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的過程中,每條線路節(jié)點(diǎn)之間的距離都是不等的,而在戰(zhàn)時(shí),時(shí)間就是生命,所以線路路長是影響部隊(duì)機(jī)動(dòng)的因素之一。根據(jù)以上假設(shè),路長因素量化值可設(shè)為Ekj2。

2.2 路況因素及量化

路況因素主要是指線路的道路等級(jí)、道路的交通情況和可維修性等等。如在水泥地面和在泥土路面及崎嶇的山路上,即使是相同的距離,機(jī)動(dòng)所需要的時(shí)間也是不相等的。而道路的等級(jí)、道路交通情況和可維修性可通過評(píng)判打分的方法得到其量化數(shù)據(jù),故根據(jù)以上假設(shè)路況因素量化值可設(shè)為Ekj3,各子因子的量化值分別設(shè)為Ekj31和Ekj 32,則Ekj3=Ekj31+Ekj 32+Ekj33。(在個(gè)數(shù)值相加之前應(yīng)對(duì)其進(jìn)行無量化處理,可參考2.5)

式中:Ekj 31為道路的等級(jí)量化值,Ekj32為線路可維修性,Ekj33為道路的交通情況。對(duì)于某段路的評(píng)價(jià)可簡化為(好,較好,差)三個(gè)等級(jí),同樣可通過專家評(píng)判獲得量化數(shù)據(jù)。

2.3 障礙因素及量化

在障礙因素中,主要考慮機(jī)動(dòng)中遇到的壕溝、涵洞、橋梁和水深等因素,這些影響因素主要限制地空導(dǎo)彈部隊(duì)的通行,如壕溝太寬、涵洞太矮、橋梁承重太小、水深太深等都無法使部隊(duì)通過。這些影響因素的量化值都是BOOL值,即0或1。能夠通行即為1,不能通行即為0。根據(jù)假設(shè),障礙因素的量化值可設(shè)為Ekj4,各子因素的量化值設(shè)為Ekj41,Ekj42,Ekj43,Ekj44,則 Ekj4=Ekj41?Ekj42?Ekj43?Ekj44。

式中Ekj 41表示壕溝能否通行,Ekj 42表示涵洞能否穿越,Ekj43表示橋梁承重能否達(dá)到,Ekj44表示水深是否超過最大涉水深度。

2.4 隱蔽性因素及量化

地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的目的就是快速機(jī)動(dòng),抓住戰(zhàn)機(jī),保護(hù)自己免遭攻擊。所以選擇隱蔽性好的線路,同樣也可以達(dá)到快速機(jī)動(dòng)的目的。在隱蔽性不好的線路上機(jī)動(dòng),容易暴露目標(biāo)。隨著高技術(shù)偵察裝備的不斷發(fā)展,特別是空中偵察裝備,使部隊(duì)在大多數(shù)情況下都必須很好地隱蔽自己免遭對(duì)方發(fā)現(xiàn)。這里主要考慮遭敵衛(wèi)星和偵察飛機(jī)發(fā)現(xiàn)的概率。假設(shè)隱蔽性因素的量化值(等于不能被敵偵察發(fā)現(xiàn)的概率)為Ekj5。

其中,r為目標(biāo)與背景光度,a為氣象因子系數(shù),u為目標(biāo)形狀修正因子,pt為衛(wèi)星的分辨力,L為目標(biāo)的幾何尺寸,pw為武器被識(shí)別概率,v為飛機(jī)飛行速度,d為搜索寬度,s為機(jī)動(dòng)區(qū)域,t為搜索時(shí)間,w為偵察衛(wèi)星的數(shù)目,f為偵察飛機(jī)的數(shù)目。

故可得:Ekj5=1-P。

2.5 自身防護(hù)因素和氣象因素及量化

自身防護(hù)能力是指地空導(dǎo)彈武器在執(zhí)行戰(zhàn)斗任務(wù)的過程中,采取自身保護(hù)和偽裝措施而達(dá)到的自身防衛(wèi)能力。防護(hù)能力越強(qiáng),其生存能力就越強(qiáng)。

氣象因素這里主要考慮天氣情況和晝夜情況。天氣情況如天氣的惡劣程度,晝夜情況如是白天還是黑夜,主要影響能見度。

在本模型中,由于在相同時(shí)刻自身的防護(hù)能力和氣象條件的量化值都是相同的,故在模型中其量化值將不予考慮。

2.6 影響因素量化值的無量綱化

3 A*算法的基本原理[2]

A*算法是建立在Dijkstra算法基礎(chǔ)上的啟發(fā)式搜索算法,在Dijkstra算法基礎(chǔ)上引入了當(dāng)前節(jié)點(diǎn)的估價(jià)函數(shù) f(n)。其關(guān)鍵就是建立估價(jià)函數(shù)

式中,f(n)是從初始點(diǎn)通過節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的估價(jià)函數(shù)。g(n)為從初始點(diǎn)開始,沿著產(chǎn)生的路徑,移動(dòng)到節(jié)點(diǎn)n的移動(dòng)耗費(fèi)。h(n)為從節(jié)點(diǎn)n移動(dòng)到目標(biāo)點(diǎn)的預(yù)估移動(dòng)耗費(fèi)。

A*算法的實(shí)現(xiàn)步驟如下:

1)以起點(diǎn)為第1個(gè)路徑節(jié)點(diǎn),尋找與之相連的候選節(jié)點(diǎn);2)對(duì)與之相連的每一個(gè)候選節(jié)點(diǎn)計(jì)算其估價(jià)函數(shù)值 f(n),選出 f(n)值最小的節(jié)點(diǎn)作為下一個(gè)路徑節(jié)點(diǎn);3)如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),則結(jié)束搜索,否則,進(jìn)入步驟2),以新的路徑節(jié)點(diǎn)為起點(diǎn)繼續(xù)搜索,并記錄搜索到的最短路徑,直至目標(biāo)節(jié)點(diǎn)。

4 適合防空兵機(jī)動(dòng)路線選擇的A*改進(jìn)算法

4.1 改進(jìn)思路

在地空導(dǎo)彈機(jī)部隊(duì)機(jī)動(dòng)過程中,由于各種影響因素的存在,同時(shí)各影響因素所占有的比重也是不同的,為分析問題的方便,我們引入機(jī)動(dòng)能力影響因子的概念,即把機(jī)動(dòng)過程中的相關(guān)影響因素轉(zhuǎn)化成權(quán)重值。然后將g(n)的值乘以這個(gè)權(quán)重值,再利用A*算法進(jìn)行求解。公式如下:

e為每段路的機(jī)動(dòng)能力影響因子。

4.2 算法實(shí)現(xiàn)步驟

在算法的實(shí)現(xiàn)過程中,要構(gòu)造兩個(gè)鏈表。分別存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn),分別稱為OPEN表和CLOSE表。算法實(shí)現(xiàn)步驟如下:

1)初始化設(shè)置。設(shè)置初始節(jié)點(diǎn):ds=0,ps=Φ;其他點(diǎn):ds=∞,ps=?(未知);將起始節(jié)點(diǎn)s標(biāo)號(hào),記k=s。并將起始點(diǎn)信息加載到OPEN表中,CLOSE表賦值為空。

2)機(jī)動(dòng)能力因子計(jì)算。首先計(jì)算起始點(diǎn)s到其他直接連接的未標(biāo)記的點(diǎn)j的機(jī)動(dòng)能力因子ekj。

3)距離計(jì)算。計(jì)算從所有標(biāo)記點(diǎn)的點(diǎn)到其他直接連接的未標(biāo)記的點(diǎn)j的距離。即搜索距離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn),求 f(j)的最小值,將節(jié)點(diǎn)j從OPEN表中刪除并加載到CLOSE表中。判斷節(jié)點(diǎn) j是否為終結(jié)點(diǎn),如果是,轉(zhuǎn)向步驟5);否則轉(zhuǎn)向步驟4)。

4)判斷節(jié)點(diǎn)j的節(jié)點(diǎn)信息是否在確定的范圍內(nèi),如果在范圍內(nèi),則擴(kuò)展節(jié)點(diǎn)j;否則加載節(jié)點(diǎn)j的節(jié)點(diǎn)信息并進(jìn)行擴(kuò)展。轉(zhuǎn)向步驟3)。

5)從節(jié)點(diǎn) j開始,利用回溯的方法輸出起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑,以及最短距離,算法終止。

4.3 機(jī)動(dòng)能力因子計(jì)算

根據(jù)影響地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的因素,在確定每一個(gè)影響因素的量化之后,可建立如下計(jì)算公式計(jì)算從所有標(biāo)記的節(jié)點(diǎn)k到其他直接連接的未標(biāo)記節(jié)點(diǎn)j的機(jī)動(dòng)能力影響因子:

式中,Ekji為第i個(gè)影響因素的量化值;qi為第i個(gè)影響因素所占有的比重。

計(jì)算后,代入機(jī)動(dòng)能力因素計(jì)算式即可。

5 實(shí)例分析

根據(jù)上述設(shè)計(jì),現(xiàn)以一個(gè)實(shí)例來具體說明A*算法在地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線選擇中的應(yīng)用。如圖2所示,為某地空導(dǎo)彈部隊(duì)從S1～S8可能機(jī)動(dòng)的路線節(jié)點(diǎn)及可能經(jīng)過的路段。

圖2 機(jī)動(dòng)路線樹

1)由圖2可知,該地空導(dǎo)彈部隊(duì)可能的機(jī)動(dòng)路線一共有8條,即:

表1 可能路徑表

2)設(shè)定每一個(gè)影響因素的權(quán)重 qi為(0.4,0.1,0.2,0.3),根據(jù)4.3節(jié)可算得每段路的機(jī)動(dòng)能力因子ei。

3)對(duì)所有影響地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的因素,利用前面給出的數(shù)學(xué)模型求取Ekji,如表2所示。

表2 各影響因素值

4)根據(jù)前面的數(shù)學(xué)模型,利用VC++6.0編寫仿真程序,可得到地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線選擇的結(jié)果,計(jì)算結(jié)果如表3所示。

表3 A*算法計(jì)算結(jié)果表

從表3可以得到地空導(dǎo)彈部隊(duì)機(jī)動(dòng)在圖2的地圖中各可能路線的評(píng)價(jià)值,因此很容易看出哪條路徑最適合于機(jī)動(dòng)。表3中路徑3的評(píng)價(jià)值最小,即S1-S4-S6-S8為最佳的機(jī)動(dòng)路線。

6 結(jié)語

利用A*算法計(jì)算地空導(dǎo)彈部隊(duì)機(jī)動(dòng)的最佳路徑,方法簡單,設(shè)置的數(shù)據(jù)少,選擇的速度快,而且易于編程實(shí)現(xiàn),是解決地空導(dǎo)彈部隊(duì)機(jī)動(dòng)路線選擇問題的有效途徑。在實(shí)際問題中,可根據(jù)地空導(dǎo)彈部隊(duì)執(zhí)行任務(wù)的特殊性,靈活的選擇影響因素,具有一定的推廣價(jià)值。

[1]張野鵬.作戰(zhàn)模擬基礎(chǔ)[M].北京:高等教育出版社,2004,7

[2]漆陽華,等.A*的改進(jìn)路徑規(guī)劃算法[J].信息與電子工程,2009(4)

[3]張最良.軍事運(yùn)籌學(xué)[M].北京:高等教育出版社,2004

[4]康鳳舉.現(xiàn)代仿真技術(shù)與應(yīng)用[M].北京:國防工業(yè)出版社,2001,9

[5]王永慶.人工智能原理與方法[M].西安:西安交通大學(xué)出版社,1998,5

[6]杜國紅,等.坦克分隊(duì)CGF實(shí)體智能機(jī)動(dòng)行為仿真[J].系統(tǒng)仿真學(xué)報(bào),2006(7)

[7]王潔,等.地空導(dǎo)彈火力單元最佳兵力機(jī)動(dòng)線路的選擇[J].系統(tǒng)工程與電子技術(shù),2003(1)

[8]楊建軍.科學(xué)研究方法概論[M].北京:國防工業(yè)出版社,2006,7