馬培蓓， 紀(jì) 軍， 范作娥

(海軍航空工程學(xué)院，山東 煙臺 264001)

0 引言

多導(dǎo)彈協(xié)同任務(wù)規(guī)劃的目的是最大限度地利用威脅、禁/避飛區(qū)等戰(zhàn)場環(huán)境信息，利用導(dǎo)彈間相互通信的數(shù)據(jù)鏈，以及集識別、通信、導(dǎo)航于一體的戰(zhàn)術(shù)信息分配系統(tǒng)實現(xiàn)在飛行航跡上相互配合，協(xié)同有效地組織多枚導(dǎo)彈以完成共同任務(wù)為目標(biāo)，為導(dǎo)彈設(shè)計出從出發(fā)點到目標(biāo)點滿足各項機動性能的協(xié)同飛行航跡，并通過獲得更高的戰(zhàn)效和對資源的充分利用，達(dá)到比單枚導(dǎo)彈更優(yōu)的戰(zhàn)術(shù)效果［1－3］。

當(dāng)前協(xié)同航跡規(guī)劃普遍研究的方法是通過選擇合適的代價函數(shù)［4］預(yù)先規(guī)劃好一組航跡，需要大量的計算時間;文獻(xiàn)［5］提出一種基于幾何航跡規(guī)劃算法的參數(shù)最優(yōu)化方法用以解決最優(yōu)航跡問題;文獻(xiàn)［6］提出一種非線性模型預(yù)測跟蹤控制方法，在障礙回避、輸入、狀態(tài)約束條件下可用于解決航跡規(guī)劃問題;文獻(xiàn)［7］是以威脅源中心點為生長點構(gòu)造威脅分布的Voronoi圖，通過搜索最小代價路徑實現(xiàn)多UCAV協(xié)同路徑規(guī)劃。

目前大部分研究都局限在無人機等單一飛行器的航跡規(guī)劃問題上，對以多導(dǎo)彈為研究對象的協(xié)同航跡規(guī)劃問題則少有涉及，另外現(xiàn)有的航跡規(guī)劃方法大多沒有充分考慮到戰(zhàn)場環(huán)境，威脅均簡單作為點目標(biāo)處理，沒有考慮到威脅的類型和強度差別以及禁/避飛區(qū)等面狀區(qū)域?qū)Χ囡w行器協(xié)同航跡的影響，沒有充分考慮多導(dǎo)彈協(xié)同航跡規(guī)劃約束的復(fù)雜性，針對上述問題，本文重點研究了具有戰(zhàn)場環(huán)境約束的多枚導(dǎo)彈的協(xié)同任務(wù)規(guī)劃問題，包括戰(zhàn)場環(huán)境建立、初始航跡生成、航跡動態(tài)優(yōu)化處理和協(xié)同目標(biāo)分配等。

1 問題的描述

多導(dǎo)彈協(xié)同任務(wù)規(guī)劃的目的是為每枚導(dǎo)彈生成航路保證導(dǎo)彈能同時或按照一定的時間間隔到達(dá)各自的目標(biāo)點，并且盡量回避威脅。這樣生成的航路對每個單一的導(dǎo)彈來說，不一定是最優(yōu)的，但對于整個導(dǎo)彈編隊來說，一定是最優(yōu)的或次優(yōu)的。由于導(dǎo)彈的航跡規(guī)劃需要處理非結(jié)構(gòu)化、大范圍、復(fù)雜的規(guī)劃環(huán)境，這對許多傳統(tǒng)的路徑規(guī)劃算法提出了挑戰(zhàn)，因為過分冗長的時間往往失去了實際的可行性。為了滿足協(xié)同作戰(zhàn)的要求，需要同時規(guī)劃多枚導(dǎo)彈到達(dá)多目標(biāo)的航路并滿足其在空間上和時間上的協(xié)同關(guān)系。

文獻(xiàn)［8］中基于最短切線法的威脅規(guī)避算法進(jìn)行預(yù)先規(guī)劃。最短切線威脅規(guī)避算法，是指根據(jù)切線最短和協(xié)調(diào)次數(shù)最少的原則，在一定的假設(shè)條件下，從目標(biāo)點開始，按照攻擊方向的反方向依次逆推直至發(fā)射點，在此航路基礎(chǔ)上進(jìn)一步考慮威脅存在情況，按照修正后的航路走切線的思想，將處于威脅區(qū)域內(nèi)的航路點調(diào)整為安全航路。圖1和圖2分別給出了威脅為5個的情況下，攻擊角度λ＜0和攻擊角度λ＞0的航跡規(guī)劃的結(jié)果。

但文獻(xiàn)［8］只研究了單枚導(dǎo)彈攻擊同一個目標(biāo)的多航路規(guī)劃問題，這與多枚導(dǎo)彈的協(xié)同航路規(guī)劃問題相比，雖然也需要生成多條不同的航路，但它們之間有著本質(zhì)的區(qū)別。

1)單枚導(dǎo)彈多航路規(guī)劃生成的各條航路的起始點和目標(biāo)點都相同，但在多導(dǎo)彈協(xié)同航路規(guī)劃中，不同導(dǎo)彈的起始點和目標(biāo)點并不一定相同;

2)單枚導(dǎo)彈多航路規(guī)劃算法一般對實時性不要求，但多導(dǎo)彈協(xié)同航路規(guī)劃要求在線進(jìn)行實時航路再規(guī)劃;

3)單導(dǎo)彈多航路規(guī)劃只要求生成在空間上較為離散的多條航路即可，但多導(dǎo)彈協(xié)同航路規(guī)劃還需要滿足各導(dǎo)彈之間的協(xié)同性要求，即要求導(dǎo)彈相互之間不能碰撞以及各導(dǎo)彈必須同時或依次到達(dá)目標(biāo)。

圖1 λ＜0時仿真結(jié)果Fig.1 Simulation results when λ ＜0

圖2 λ＞0時仿真結(jié)果Fig.2 Simulation results when λ ＞0

2 多導(dǎo)彈協(xié)同航跡規(guī)劃算法

多導(dǎo)彈協(xié)同系統(tǒng)實質(zhì)是一個多動態(tài)的實體，各導(dǎo)彈之間通過數(shù)據(jù)鏈共享信息或任務(wù)完成一個共同的目標(biāo)，但此目標(biāo)大于每枚導(dǎo)彈的目標(biāo)，即一枚導(dǎo)彈的航路最優(yōu)不能代表多導(dǎo)彈協(xié)同系統(tǒng)的航路最優(yōu)，有時為了提高整個系統(tǒng)的協(xié)同性，不得不犧牲個體的最優(yōu)性。下面研究存在威脅和禁飛區(qū)的戰(zhàn)場環(huán)境下多導(dǎo)彈協(xié)同航跡規(guī)劃算法。

2.1 建立戰(zhàn)場環(huán)境

導(dǎo)彈通常主要遭受兩種類型的威脅:一是探測性威脅，另一種是殺傷性威脅。探測性威脅主要指各種普通對空雷達(dá)、預(yù)警機雷達(dá)等，其威脅度計算模型有多種，最常用的是根據(jù)雷達(dá)方程計算。

即認(rèn)為威脅源對于威脅作用范圍內(nèi)的導(dǎo)彈的威脅度與導(dǎo)彈到威脅源距離的四次方成反比，如式(2)所示。

殺傷性威脅主要指各種防空導(dǎo)彈、高炮等。常用的計算方法如式(3)表示。

其中:(xi，yi，hi)為威脅源的位置;(xj，yj，hj)為導(dǎo)彈的位置;K為威脅源戰(zhàn)技指標(biāo)，是和導(dǎo)彈反射面積有關(guān)的系數(shù);和分別為探測性威脅源的探測近界和遠(yuǎn)界;和分別為殺傷性威脅源的最小和最大殺傷距離;，為導(dǎo)彈與威脅源的距離。表1描述了典型的威脅及殺傷距離和威脅度。

表1 典型威脅Table 1 Typical threats

2.2 戰(zhàn)場環(huán)境下V圖的建立

由于戰(zhàn)場環(huán)境中的威脅存在類型和強度的差別，在構(gòu)造戰(zhàn)場環(huán)境的V圖形式化表達(dá)時，必須建立任意兩個威脅體之間的等價關(guān)系，此時建立的V圖已不是傳統(tǒng)意義上基于歐氏距離的V圖，稱之為擴展V圖(Extended Voronoi，EV)?；跀U展V圖的基本原理和性質(zhì)如下所示［9］。

性質(zhì)1:設(shè)Wi，Wj是平面內(nèi)兩個威脅點，并且 Wj的威脅值是Wi的k倍，假設(shè)k＞1，則到Wj的距離是到Wi距離的k倍的點的軌跡是圓。

性質(zhì)2:在局部空域內(nèi)，若 Wi，Wj，Wk是平面內(nèi) 3個威脅點，并且Wi的威脅值是Wj，Wk的k倍，且k＞1，而Wj，Wk的威脅值相等。

性質(zhì)3:在局部空域內(nèi)，若 Wi，Wj，Wk是平面內(nèi) 3個威脅點，Wj，Wk的威脅值是 Wi的 k倍，且 k＞1，而Wj，Wk的威脅值相等。

遵循擴展V圖的性質(zhì)1、性質(zhì)2和性質(zhì)3，建立基于不同威脅的擴展V圖，如圖3所示。

圖3 不同類型威脅的擴展V圖構(gòu)造Fig.3 Extended Voronoi for different type of threats

在構(gòu)造擴展V圖時，禁飛區(qū)和避飛區(qū)作為面狀生長目標(biāo)處理，所生成的V圖的邊很可能非直線，而存在曲線的情形。本文僅考慮禁/避飛區(qū)的作用距離均為10000 m的情況，如圖4所示。

圖4 僅包括禁/避飛區(qū)的擴展V圖Fig.4 Extended Voronoi for no-fly zones

2.3 經(jīng)典Dijkstra算法的改進(jìn)和實現(xiàn)

Dijkstra算法是解決這種問題的最有效算法之一，其時間復(fù)雜性是O(n2)。經(jīng)典的Dijkstra算法是用于求解從連通圖中的一個頂點出發(fā)到圖中其他所有頂點的最短航跡，并且也只給出了從起始點到其他各點的最短航跡的長度，而沒有給出源點到其他各點的最短航跡所經(jīng)過的中間點，本文求解的問題要求給出中間節(jié)點，因此對Dijkstra算法做了適當(dāng)?shù)男薷摹?/p>

第1點修改:Dijkstra算法的結(jié)束條件。

經(jīng)典Dijkstra算法中，按航跡長度遞增產(chǎn)生各頂點的最短航跡，求得從源點到所有頂點的最短航跡時，算法自動結(jié)束。而在修改后的Dijkstra算法中，每當(dāng)求得一個頂點的航跡后，就判斷該頂點是否為規(guī)劃目標(biāo)點，若是規(guī)劃目標(biāo)點就結(jié)束，否則繼續(xù)。

第2點修改:把Dijkstra算法用于記錄起始點到每一頂點的航跡長度的數(shù)組進(jìn)行了擴充。

在經(jīng)典Dijkstra算法中，算法結(jié)束時只給出源點到各頂點的最短航跡長度，具體源點到各頂點的最短航跡途中經(jīng)過了哪些中間點，由于數(shù)據(jù)結(jié)構(gòu)的原因，算法并沒有保存。而對算法修改后，當(dāng)搜索到目標(biāo)點后，就可以利用前驅(qū)信息，向前追蹤到規(guī)劃的起始點，求得最短航跡的全部頂點編號，從而可以繪制出規(guī)劃所得的航跡。通過上述思想改進(jìn)的Dijkstra算法，結(jié)果得到一系列航跡控制點，可將它們保存在一個矩陣中。

實際上Dijkstra算法在執(zhí)行過程中產(chǎn)生了以初始點s為根節(jié)點的一棵樹，隨著算法的執(zhí)行，該樹向四面八方延伸，直到達(dá)到節(jié)點為止，算法的時間復(fù)雜性為O(n2)。顯然有些分支無益于最短航跡的求得，需要及早刪去某些多余的分支，從而減少計算最短航跡的所需要的時間，進(jìn)一步降低算法的復(fù)雜性。假設(shè)在V圖中任意給定兩點s和t，則需沿著方向不斷尋找邊和節(jié)點加入航跡隊列。首先找出航跡長度的限定值;然后利用該限定值降低算法執(zhí)行過程中產(chǎn)生的二叉樹的規(guī)模;最后，由二叉樹節(jié)點的標(biāo)記可以計算出最短航跡及其長度。如果將此算法對與s關(guān)聯(lián)的未考慮的邊重新執(zhí)行常數(shù)次，則可求得s與t之間更短的航跡，具體算法可參見文獻(xiàn)［10］，此算法的時間復(fù)雜性為O(n)。

2.4 航跡縮短與平滑

導(dǎo)彈的初始航跡經(jīng)過的航跡點過多，則導(dǎo)彈需要過度頻繁地轉(zhuǎn)彎。在導(dǎo)彈機動性能的限制條件下，需要進(jìn)一步優(yōu)化導(dǎo)彈飛行航跡，通過沿著初始航跡的方向縮短航跡長度，消除不必要的轉(zhuǎn)彎點。

本文提出了基于視線的航跡縮短算法，具體算法步驟為:

1)在初始航跡的每個航跡段(Voronoi邊)上增加若干個新的節(jié)點(節(jié)點的數(shù)量可以變化)，這里假定每條Voronoi邊被分成10段，這些節(jié)點替代了之前圍繞著威脅區(qū)和禁/避飛區(qū)的點，以此用以提供縮短航跡所需的更多的節(jié)點;

2)將導(dǎo)彈的位置點作為優(yōu)化航跡的第一個節(jié)點，目標(biāo)的位置點作為最后一個節(jié)點，直接將導(dǎo)彈節(jié)點與目標(biāo)節(jié)點相連，連線稱為視線;

3)檢查產(chǎn)生的視線是否與威脅區(qū)或禁/避飛區(qū)有相交點，如果沒有相交點，則此視線即成為一條新的航跡段;如果有交叉點，則將導(dǎo)彈節(jié)點與目標(biāo)點的前一個節(jié)點相連，再次判斷是否與威脅區(qū)或禁/避飛區(qū)有相交點;

4)上述過程不斷重復(fù)，直到產(chǎn)生的視線不與威脅區(qū)或禁/避飛區(qū)有任何相交，則此視線相對應(yīng)的最后一個節(jié)點又成為新的開始點。將新的開始點與目標(biāo)點相連，遵循相同的原則進(jìn)行判斷，直到開始點與目標(biāo)點相重合，則新的經(jīng)過縮短的優(yōu)化航跡產(chǎn)生。

航跡縮短前后的仿真結(jié)果如圖5所示。

通過縮短航跡既可有效回避威脅，又可使飛行航跡縮短，有效節(jié)省燃料。但由于縮短的航跡仍然存在轉(zhuǎn)角急劇變化的情況，不能滿足導(dǎo)彈最小轉(zhuǎn)彎半徑的要求，因此要進(jìn)一步研究航跡平滑的問題。

圖5 航跡縮短的例子Fig.5 Example of path shortening

解決這一問題目前可以采用彈簧鏈路法、B樣條平滑法等，上述方法雖然有效，但計算量相對較大。本文采用一種更為簡單的方法，即在任意兩條相關(guān)的直線段之間增加轉(zhuǎn)彎段，轉(zhuǎn)彎半徑與導(dǎo)彈的過載與速度等側(cè)向機動能力是密切相關(guān)的。取任意3個航路點Ai－1，Ai，Ai+1(不在同一條直線上)，航路段之間的航向轉(zhuǎn)彎角為ψi，如圖6所示。

圖6 路徑平滑示意圖Fig.6 Sketch of path smoothing

導(dǎo)彈航跡最初由直線段 Ai－1Ai切換到直線段AiAi+1，增加了轉(zhuǎn)彎段之后，最小轉(zhuǎn)彎半徑圓與 Ai－1Ai相切于Bi點，與AiAi+1相切于Ci點。從圖中可以看出，半徑 R 分別與 Ai－1Ai，AiAi+1垂直，則:

圖7 航跡平滑的例子Fig.7 Example of path smoothing

通過航跡縮短與平滑的動態(tài)優(yōu)化處理措施，導(dǎo)彈飛行航跡大大縮短，也滿足了導(dǎo)彈最小轉(zhuǎn)彎半徑、速度、過載限制等戰(zhàn)術(shù)指標(biāo)要求。

3 協(xié)同目標(biāo)分配

多枚導(dǎo)彈得到了縮短的、可飛的軌跡之后，還需要“進(jìn)一步解決哪枚導(dǎo)彈攻擊哪個目標(biāo)”的問題，即協(xié)同目標(biāo)分配問題。其目標(biāo)是將不同位置、不同價值的目標(biāo)分配給不同的導(dǎo)彈，盡力提高殺傷概率，避免重復(fù)攻擊和遺漏，力求整體效益最大，代價最小。

通常將目標(biāo)分配考慮為一類MMKP(Multi-dimensional，Multi-choice Knapsack Problem)問題，原理敘述如下:從集合I中選出一組滿足所有問題約束的項，使其價值之和最大，其數(shù)學(xué)模型為［11］

式中:n為項數(shù)且n＞1;pj為項j的價值且pj＞0;xj為對應(yīng)項j的變量，且:

rij＞0為項j耗用資源i的量;bi為資源的總量;m為約束數(shù)，m＞1。一個定義完整的MMKP應(yīng)該滿足rij＜bi并且。而本文所研究的多導(dǎo)彈協(xié)同目標(biāo)分配問題指的是m=1的一類特殊的0/1背包問題，即指派問題。指派問題是0/1背包問題的特例，其最優(yōu)解具有這樣的性質(zhì)，若從系數(shù)矩陣C的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣B，那么以B矩陣為系數(shù)矩陣求得的最優(yōu)解和原系數(shù)矩陣求得的最優(yōu)解相同。

本文采用匈牙利算法求解指派問題，為了降低問題的復(fù)雜性，確定以下約束條件:1)每個目標(biāo)僅僅被攻擊一次;2)每枚導(dǎo)彈僅僅攻擊一個目標(biāo)。

通過此約束確保每個目標(biāo)都能被攻擊到，防止遺漏，但同時也避免了被重復(fù)攻擊，從而有效減小了任務(wù)分配可能的組合數(shù)量。

4 仿真結(jié)果分析

應(yīng)用本節(jié)算法在 Intel Pentium Dual E22002.2 GHz，2 GB內(nèi)存的PC上進(jìn)行了仿真實驗，運行環(huán)境為Windows XP，規(guī)劃環(huán)境大小為200 km ×200 km，禁/避飛區(qū)和威脅區(qū)為模擬生成的圓形區(qū)域。

將某型號反艦導(dǎo)彈考慮為一個質(zhì)心，不考慮重力影響，不考慮地球曲率影響。導(dǎo)彈初始速度v=340 m/s，最大法向(合成)過載為nmax≤2g，最大滾轉(zhuǎn)角限制為導(dǎo)彈最小轉(zhuǎn)彎半徑，取平飛高度為200 m，導(dǎo)彈轉(zhuǎn)向結(jié)束后為穩(wěn)定航向所需走的最短距離為1 km，導(dǎo)彈最大拐彎角度為90°，假設(shè)目標(biāo)靜止。

導(dǎo)彈和目標(biāo)的初始坐標(biāo)分別為:導(dǎo)彈1(15.11 km，135.29 km);導(dǎo)彈 2(26.79 km，92.52 km);導(dǎo)彈 3(46.62 km，52.04 km);導(dǎo)彈 4(73.07 km，32.65 km);目標(biāo)1(113.51 km，188.31 km)，戰(zhàn)術(shù)價值為 60;目標(biāo) 2(143.61 km，160.37 km)，戰(zhàn)術(shù)價值為 80;目標(biāo) 3(171.92 km，74.85 km)，戰(zhàn)術(shù)價值為90;目標(biāo)4(160.69 km，127.87 km)，戰(zhàn)術(shù)價值為80。

共有4個禁飛區(qū)和4個威脅區(qū)，其位置坐標(biāo)為:禁飛區(qū)1(66.33 km，150.11 km);禁飛區(qū) 2(104.97 km，123.88 km);禁飛區(qū) 3(82.95 km，82.83 km);禁飛區(qū) 4(135.52 km，60.03 km)，探測距離均為 10 km;威脅 1(122.94 km，86.82 km)，區(qū)域半徑 30 km，威脅度 0.8;威脅2(68.89 km，111.99 km)，區(qū)域半徑10 km，威脅度0.8;威脅 3(87.79 km，151.17 km)，區(qū)域半徑 5 km ，威脅度 0.5;威脅 4(105.3 km，35.96 km)，區(qū)域半徑 10 km，威脅度0.8。

在未考慮協(xié)同目標(biāo)分配情況下，規(guī)劃了16條最優(yōu)飛行航跡，如圖8所示。

圖8 4枚導(dǎo)彈攻擊4個目標(biāo)的最優(yōu)航跡Fig.8 Optimal paths for four missiles attacking four targets

在考慮協(xié)同目標(biāo)分配的情況下，協(xié)同航跡規(guī)劃如圖9所示，即由導(dǎo)彈1攻擊目標(biāo)2，導(dǎo)彈2攻擊目標(biāo)4，導(dǎo)彈3攻擊目標(biāo)1，導(dǎo)彈4攻擊目標(biāo)3，此時航跡總體代價最小。

圖9 協(xié)同分配后的最優(yōu)航跡Fig.9 Optimal path after cooperative assignment

其終端航跡角度分別為 － 156°、132°、－ 66°和－114°。

5 結(jié)束語

本文針對具有戰(zhàn)場環(huán)境約束多導(dǎo)彈協(xié)同任務(wù)規(guī)劃問題展開研究。根據(jù)多導(dǎo)彈協(xié)同的特點，在研究了具體的戰(zhàn)場環(huán)境模型，考慮了不同威脅作用距離和威脅度、威脅代價、距離代價基礎(chǔ)上將禁/避飛區(qū)和威脅區(qū)作為面狀生長目標(biāo)建立了擴展Voronoi圖并結(jié)合改進(jìn)Dijkstra算法取得了代價最小的航跡;進(jìn)一步采用基于視線的航跡縮短算法與航跡平滑算法，產(chǎn)生了滿足導(dǎo)彈機動性能的平滑的可飛行航跡;最后采用基于MMKP的協(xié)同目標(biāo)分配算法獲得了總體代價最小的多導(dǎo)彈協(xié)同航跡。仿真結(jié)果表明了此算法的有效性。具有戰(zhàn)場環(huán)境約束的多導(dǎo)彈協(xié)同任務(wù)規(guī)劃算法可應(yīng)用在多導(dǎo)彈協(xié)同攻擊多目標(biāo)，結(jié)合時間約束條件對目標(biāo)實施飽和攻擊等方面。

［1］BORTOFF S A.Path planning for UAVs［C］//The Proceedings of American Control Conf，2000:364-368.

［2］CHANDLER P R.Meir Pachter Complexity in UAV cooperative control［C］//The Proceedings of American Control Conf，2002:1831-1836.

［3］符小衛(wèi)，高曉光.多架無人作戰(zhàn)飛機協(xié)同作戰(zhàn)的幾個關(guān)鍵問題［J］.電光與控制，2003，10(3):19-22.

［4］BEARD R，MCLAIN T.Cooperative path planning for timing-critical missions［C］//Proceedings of the American Control Conference，Denver，Colorado，2003:296-301.

［5］YANG G，KAPILA V.Optimal path planning for unmanned air vehicles with kinematic and tactical constraints［C］//Proceedings of the 41st IEEE Conference on Decision and Control，(Las Vegas，NV)，2002:1301-1306.

［6］KIM H J，SHIM D H，SASTRY S.Nonlinear model predictive tracking control for rotorcraft-based unmanned aerial vehicles［C］//Proceedings of the American Control Conference，(Anchorage，AK)，2002:3576-3581.

［7］高曉光，符小衛(wèi)，宋紹梅.多UCAV航跡規(guī)劃研究［J］.系統(tǒng)工程理論與實踐，2004(5):140-143.

［8］張友安，范作娥.反艦導(dǎo)彈航路規(guī)劃與威脅規(guī)避算法［J］.吉林大學(xué)學(xué)報，2008，38(3):746-752.

［9］高曉光，楊有龍.基于不同威脅體的無人作戰(zhàn)飛機初始路徑規(guī)劃［J］.航空學(xué)報，2003，24(5):435-438.

［10］周培德.計算幾何—算法設(shè)計與分析［M］.3版.北京:清華大學(xué)出版社，2008.

［11］王樂.對解決背包問題的遺傳禁忌搜索算法的研究［D］.鄭州:鄭州大學(xué)，2006.