馬培蓓， 紀 軍， 范作娥

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

0 引言

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

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

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

1 問題的描述

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

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

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

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

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

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

圖1 λ＜0時仿真結果Fig.1 Simulation results when λ ＜0

圖2 λ＞0時仿真結果Fig.2 Simulation results when λ ＞0

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

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

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

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

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

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

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

表1 典型威脅Table 1 Typical threats

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

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

性質(zhì)1:設Wi，Wj是平面內(nèi)兩個威脅點，并且 Wj的威脅值是Wi的k倍，假設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圖構造Fig.3 Extended Voronoi for different type of threats

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

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

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

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

第1點修改:Dijkstra算法的結束條件。

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

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

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

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

2.4 航跡縮短與平滑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 協(xié)同目標分配

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

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

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

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

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

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

4 仿真結果分析

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

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

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

共有4個禁飛區(qū)和4個威脅區(qū)，其位置坐標為:禁飛區(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é)同目標分配情況下，規(guī)劃了16條最優(yōu)飛行航跡，如圖8所示。

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

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

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

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

5 結束語

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

［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)的幾個關鍵問題［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］張友安，范作娥.反艦導彈航路規(guī)劃與威脅規(guī)避算法［J］.吉林大學學報，2008，38(3):746-752.

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

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

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