陳宇 張公平 宋韜 溫欣玲 馬正祥 劉兆瑜 秦玉鑫

摘要：在復雜的戰(zhàn)場作戰(zhàn)環(huán)境中可能存在多個動態(tài)威脅，如何快速規(guī)劃出最優(yōu)航路是攻擊任務順利執(zhí)行的關鍵。本文提出一種在文化算法框架下稀疏A*算法與遺傳算法（Genetic Algorithm，GA）相結合的動態(tài)航路規(guī)劃算法，用于多任務空地武器多目標協同任務優(yōu)化中。算法基于文化算法思想框架，首先利用稀疏A*算法快速獲取初始航路及航路點信息，并將獲取到的信息作為知識送入信仰空間存儲，指導遺傳算法對種群空間個體在有效范圍內優(yōu)選可行航路點，從而實現最優(yōu)化目標任務分配及航路獲取。仿真結果表明，算法能夠有效避開威脅，減少遺傳算法規(guī)劃整體航路的飛行距離，完成多任務空地武器多目標協同任務規(guī)劃。

關鍵詞： 空地武器;協同優(yōu)化;任務分配;遺傳算法;稀疏A*算法

中圖分類號： TJ762.2?? 文獻標識碼： A?? 文章編號： 1673-5048（2021）02-0062-07

0 引? 言

任務規(guī)劃作為提高空地武器（如巡飛彈、無人機等）的自主飛行能力以及作戰(zhàn)效能的關鍵技術，越來越受到國內外研究人員的青睞。復雜戰(zhàn)場環(huán)境中，常需要采用多機協同行動對某個區(qū)域進行多個任務執(zhí)行[1]，并且在多任務多空地武器協同任務規(guī)劃中，飛行過程可能存在多個威脅，任務規(guī)劃的目的是如何確?？盏匚淦鲝钠痫w點到終止點規(guī)劃出一條最優(yōu)航路[2-3]，避開威脅并完成各攻擊目標的最優(yōu)化任務分配，主要涉及任務分配和航路規(guī)劃兩個方面的內容[4]。多任務協同目標分配下的航路規(guī)劃方法主要包括確定性方法和啟發(fā)式方法，確定性方法主要包括Dijkstar算法[5]、A*算法[6]、梯度法等，該類方法雖然能夠保證航路最優(yōu)，但對大范圍復雜空域環(huán)境建模和動態(tài)航路規(guī)劃時，無法滿足實時性要求;啟發(fā)式方法主要包括GA算法[7-8]、PSO算法[9-10]、蟻群算法[11-12]等，該類方法可用于協同目標分配及動態(tài)航路規(guī)劃過程中，但是由于搜索的隨機性，導致迭代計算周期長，且劣質搜索過程容易陷入局部最優(yōu)解，求解效率及精度較低。通過文獻查閱，目前單機航路規(guī)劃問題研究較為成熟，而多機協同的航路規(guī)劃問題是非常復雜的組合優(yōu)化問題（NP-hard）[13]，但研究不夠深入，特別是對航路任務規(guī)劃的時間、空間協同綜合考慮不足。

針對以上問題，本文提出一種在文化算法框架下的多任務空地武器目標協同優(yōu)化任務規(guī)劃算法，綜合考慮A*算法在靜態(tài)環(huán)境下搜索速度快的特點，同時兼顧遺傳算法（Genetic Algorithm，GA）對復雜模型進行優(yōu)化的適應性能力，通過調節(jié)算法算子，選取最優(yōu)航路點以滿足實時性和精度要求，完成復雜環(huán)境下快速任務分配及動態(tài)航路規(guī)劃。最后，通過仿真實驗驗證本文提出算法的有效性。

1 問題描述

當作戰(zhàn)任務分配方案確定后，在預知地形和各種威脅源的前提下，除了需要綜合考慮油耗代價、轉彎角等空地武器自身約束外，重要問題是如何有效避開敵方雷達監(jiān)控區(qū)域、禁飛區(qū)、導彈車等軍事打擊的威脅代價[14-15]，規(guī)劃出一條滿足空地武器性能且飛行代價最低的航路，成功打擊地面多目標任務。為簡化研究問題，首先做出如下假設：

（1） 各空地武器巡航高度固定，且飛行速度一致，相互不存在飛行空域沖突;

（2） 各攻擊目標任務不存在時間先后等級順序;

（3） 各無人機所受的飛行威脅在不同高度下相同。

基于以上假設，可以把空地武器多目標協同優(yōu)化任務規(guī)劃問題等效建模為二維坐標系下帶有約束條件的最短路徑優(yōu)先遍歷問題。

1.1 多級威脅約束環(huán)境地圖模型構建

復雜戰(zhàn)場作戰(zhàn)環(huán)境中，敵方對空地武器的防御主要包括導彈、高炮、雷達等，也包括地形、惡劣天氣以及其他未知威脅等。針對這些威脅按照其作用范圍、方式、強度，可采用特征方程進行建模：

（1） 防空導彈攻擊區(qū)域是以自身坐標為中心，向外擴展的從近邊界到遠邊界的區(qū)域，在三維空間中類似于空心的鼓形，其水平截面形狀是圓周形。空地武器在目標區(qū)域飛行過程中飛行高度比較低，一般不會超過導彈的最大攻擊高度。因此，導彈威脅建模時可忽略高度影響，從而簡化模型。仿真實驗中以某點作為威脅中心，以一定半徑的圓周及作用強度來表示不同擊落概率的威脅區(qū)域（高炮威脅與導彈威脅類似）;

（2） 由于雷達不受白天黑夜以及天氣因素的影響，配合防空武器具備強大的殺傷力，仿真實驗中同樣以某位置為中心，以一定半徑的圓周及作用強度來表示不同擊落概率的雷達防空威脅區(qū)域;

（3） 惡劣天氣的影響范圍可等效為一個圓柱空間，在某高度下的威脅為一定半徑的圓形區(qū)域;

（4） 地形威脅包括山體或高層建筑物等立體型障礙，在某高度下的威脅用長方形表示其模型。

綜上所述，多空地武器戰(zhàn)場作戰(zhàn)環(huán)境中的二維地圖威脅全概率表達式可表示為

P（x，y）=∑ma=1∑nb=1（pab）（x，y）（1）

式中：（pab）（x，y）表示不同威脅源在數字地圖柵格（x，y）處的威脅概率;a表示威脅源種類數目;b表示某種威脅源的個數。因此，復雜戰(zhàn)場環(huán)境可映射為二維全概率綜合數字地圖。如圖1所示。

1.2 無人機任務規(guī)劃模型構建

假設多空地武器作戰(zhàn)對敵方多目標進行攻擊，攻擊前通過偵察已預知復雜戰(zhàn)場環(huán)境中各目標種類差異、空地武器載荷能力以及戰(zhàn)場環(huán)境威脅約束、協同約束等，對協同任務規(guī)劃進行建模：E為戰(zhàn)場環(huán)境，待執(zhí)行任務的多空地武器集合為A={a1，a2，…，ai，…，an}，數量為n，體現載彈量M的價值集合VA={v1，v2，…，vi，…，vm};待攻擊目標集合T={t1，t2，…，tj，…，tm}，數量為m，價值集合VT={v1，v2，…，vj，…，vm}，體現待攻擊目標的等級高低。在戰(zhàn)場環(huán)境構建的帶威脅二維地圖中，假設某空地武器所在位置坐標為（xi（t），yi（t）），待攻擊目標點位置坐標為（xj（t），yj（t）），每枚空地武器的任務執(zhí)行路線為Pi。如空地武器對3個目標進行攻擊ri=[t1→t3→t5]，任務執(zhí)行路線為P={（x1（t），y1（t）），（x3（t），y3（t）），（x5（t），y5（t））}。

多空地武器執(zhí)行作戰(zhàn)任務的目的是在自身損傷代價最小的情況下，消滅目標價值最高的待攻擊目標，同時避開戰(zhàn)場威脅，任務完成的時間最少，飛行距離最短，但實際戰(zhàn)場環(huán)境中，很難保證各個指標均為最優(yōu)。因此，為達到整體效能最高，需要對如下指標賦予相應的權值。

1.2.1 目標函數

空地武器執(zhí)行作戰(zhàn)任務的目的是在避免任務執(zhí)行中意外損毀的情況下，有效消滅目標對象，且攻擊任務執(zhí)行時間最短。本文對目標函數中的不同指標進行歸一化處理。

（1）損傷代價

在對目標對象攻擊過程中，空地武器如何能夠有效地避開敵方雷達、高射炮、導彈以及地形、惡劣天氣等威脅，以保證空地武器損傷代價最小是任務關鍵：

min f1=∑ni=1∑mj=1xij·Kij（2）

式中： Kij為第i枚空地武器打擊第j個目標的威脅概率。

（2）飛行總距離

滿足各空地武器飛行油耗（距離）限制，有效避開各威脅的情況下，根據待攻擊目標任務的摧毀等級，各空地武器完成對待攻擊目標的任務分配，且各空地武器飛行總距離之和最短：

min f2=min∑ni=1∑mj=1sij（3）

式中：sij為第i枚空地武器打擊第j個目標的飛行距離。

（3）任務執(zhí)行時間

戰(zhàn)場環(huán)境復雜，瞬息萬變，如何以最短的時間對目標進行攻擊是取得勝利的關鍵。另外，為了增大對某攻擊目標的摧毀成功率，減少空地武器損傷，多空地武器可在指揮員要求下同時對同一目標進行攻擊，目標函數可通過設置權重系數實現時間協同：

min f3=min∑ni=1∑mj=1xij·（i，i+1）j（4）

式中： t（i，i+1）j為第i枚與第i+1枚空地武器打擊第j個目標的時間間隔。

1.2.2 約束條件

在航路評價建模中，設置空地武器在執(zhí)行下一動作前需要進行一定距離的平飛，最小直飛航路長度Lmin，空地武器最大轉彎角θ。空地武器目標攻擊執(zhí)行能力約束如下：

1≤∑mj=1xij|（i∈R）≤M

∑ni=1∑mj=1xij·Vij≤Vall（5）

式中：M為第i架無人機的最大載彈量。假設各空地武器均需載彈從起點到達終點，最小載彈量不少于1枚，即需要攻擊不少于1個目標。多枚空地武器對各目標任務進行攻擊的過程中，載彈總量不能大于待攻擊目標的總價值Vall。

實際戰(zhàn)場中，各目標任務抵抗攻擊的能力不同，對各攻擊目標設置不同級別值level，代表需要多少導彈攻擊后方可被摧毀。對各無人機設置的航路長度均不能超過油耗限值下的飛行距離;另外，在對某目標進行攻擊任務時，還應盡可能規(guī)劃多枚空地武器同時到達，以避免待攻擊目標展開防御措施等。

綜上所述，多目標協同任務規(guī)劃目標函數Z=min{α（εf1+θf2）+βf3}時，航路規(guī)劃為最優(yōu)。其中，0≤α，β，ε，θ≤1，0≤α+β≤1，0≤ε+θ≤1，α，β，ε，θ的權重取值取決于指揮員對各攻擊任務的決策部署。

2 算法設計

本文運用文化算法的結構思想[13]，提出了一種稀疏A*算法與GA相結合的，適用于威脅及目標任務動態(tài)環(huán)境下的航路規(guī)劃算法。文化算法是一種模擬人類社會演化過程的雙層進化系統，其主要思想是根據信仰空間的知識和經驗指導種群空間個體的進化，使種群朝有利的方向發(fā)展。文化算法思想結構的基本框架如圖2所示。

在文化算法框架中，種群空間與信仰空間相互溝通，相互制約，信仰空間指導種群空間進行解的優(yōu)化，更新并存儲初始航路坐標、節(jié)點信息以及尋優(yōu)空間。種群空間定期通過接受函數Accept（） 提取個體信息進行進化，通過Update（） 函數為信仰空間提供知識的更新，并根據從信仰空間提取的知識使用Influence（）函數定期影響和指導種群進化。

本文通過引入文化算法框架，在種群空間中首先運用稀疏A*算法，根據約束條件快速規(guī)劃出一條距離最短的航路，同時運用GA完成各目標攻擊任務的多機協同分配，信仰空間指導種群空間中算法計算的有效范圍，提高了優(yōu)化的速度。當局部環(huán)境發(fā)生變化時，無需重規(guī)劃整條航路，只需將受影響的有效范圍中提取出來的航路點信息進行篩選，在有效范圍內進行局部航路重規(guī)劃即可。該算法能夠有效避開威脅，同時減小動態(tài)航路規(guī)劃時間。

2.1 稀疏A*算法

A*算法作為一種成熟的搜索算法，被廣泛應用于靜態(tài)環(huán)境下的航跡規(guī)劃問題中。A*算法雖然加入了啟發(fā)函數，提高了算法的計算速度，但由于算法全方位搜索的思想，雖然能夠找到全局最優(yōu)解，但一定程度上也影響了算法的搜索速度。A*模型的搜索模型如圖3所示。

由該搜索模型可以看到，從P（i）點開始進行航跡搜索，傳統A*算法的搜索方向是八個方向。但是，當攻擊目標任務點確定在P（i）某一個方向時，搜索過程中可忽略不必要的冗余節(jié)點，從而提高算法最優(yōu)解的搜索速度。本文在傳統A*算法基礎上進行搜索方向上的優(yōu)化，算法初期排除與目標點方向相反的搜索節(jié)點，然后朝著目標點的方向，按照扇形區(qū)域進行搜索，扇形的圓心角可根據需要進行設置，最小角度為無人機最大轉彎角度θ的兩倍，即2θ[16]。由于規(guī)定了算法的搜索方向，避免了全方位搜索，使搜索的節(jié)點大幅度減少，提高了算法的實時性。

在航路規(guī)劃過程中，航路代價函數通過航路長度和威脅代價進行評價，航路長度與威脅代價之間通常相互矛盾，本文首先根據稀疏A*算法確定航路評價函數：

f（i，j）=g（i，j）|（x，y）+h（i，j）|（x，y）（6）

式中：g（i，j）|（x，y）表示各空地武器從起始點O到當前節(jié)點位置i|（xi，yi）的代價函數;h（i，j）|（x，y）表示當前位置（x，y）到目標點E的代價啟發(fā)函數：

g（i，j）|（x，y）=∑ni=1∑mj=1（ω1lij+ω2fij）

h（i，j）|（x，y）=∑ni=1ω3di（x，y）（7）

式中：lij，fij分別為第i枚空地武器從節(jié)點j-1到節(jié)點j之間的航路長度及威脅值;ω1，ω2，ω3為權重系數。為使空地武器在威脅相對小的區(qū)域內完成飛行及攻擊任務，某段飛行航路中的威脅指數如下：

fij=∑ni=1∑sk=1Kk/（Rik） （8）

式中：Kk代表第k個威脅源的強度;Rik表示第i個空地武器距離第k個威脅源的距離;s表示威脅源個數。待攻擊的目標任務節(jié)點為必經節(jié)點，di（x，y）為第i枚空地武器從當前節(jié)點位置j到目標點之間的航路估計長度。

2.2 遺傳算法

GA在問題的解集中進行搜索，解集中的每個解均為基因經特定編碼構成的個體，一定數目的個體組成種群[17]。該種群中的每個個體都是帶有特征的染色體，染色體由基因序列組成，每條染色體代表問題的一個可能解。染色體根據問題域中適應度的大小選擇個體，并以交叉、變異等方式不斷進化，適應度越高的個體越容易被選中，因此，種群的整體適應度不斷提高，最后得到的適應度最高的染色體所代表的解，即為問題的最優(yōu)解。

首先，通過稀疏A*算法在靜態(tài)環(huán)境下進行規(guī)劃獲取初始航路點，作為GA中的初始種群個體，航路中的部分航路點在空地武器飛行有效范圍內通過交叉、變異算子作用，由父代個體進化為新的子代個體，從而生成新的航路。在交叉、變異算子作用下生成的新航路示意圖如圖4所示。

可以看出，在綜合考慮威脅性和約束性權重后，因威脅位置變化而產生兩條父代航路，將第一條航路的前半部分和第二條航路的后半部分組合，其余的部分組合，生成兩個新的子代航路。

空地武器飛行過程中，因威脅位置等發(fā)生變化，借助稀疏A*算法規(guī)劃出當前位置到下一目標位置的新航路，并通過航路點確定有效范圍，以一定變異概率隨機指定某個（些）航路點做變異運算，最優(yōu)個體不做變異操作。針對航路規(guī)劃中動態(tài)威脅改變的實際問題，可通過引入擾動算子、刪除算子、插入算子、平滑算子實現子航路優(yōu)選。各算子變異運算獲取優(yōu)選子代航路示意圖如圖5。圖5（a）所示，如初始航路可行，可在有效范圍內加以較小的擾動，以提高航路適應值，如果威脅改變而導致原航路不可行，則可適當增大擾動幅度以獲得可行優(yōu)選航路;如圖5（b）所示，如果初始航路不可行，通過刪除航路中的航路點可獲得可行優(yōu)選航路;如圖5（c）所示，在兩個相鄰航路點中間插入航路點，可避開威脅區(qū)域，獲得可行優(yōu)選航路;如圖5（d）所示，當航路中出現威脅而導致無法通過，在航路中相鄰兩個航路點附近各插入一個航路點，以獲得可行優(yōu)選航路;另外，如果轉彎角度過大，超過空地武器最大轉彎角度，可通過平滑算子增加航路點以滿足空地武器性能約束。

2.3 算法實現

本文提出算法首先根據多無人機多目標協同任務規(guī)劃目標函數，借助稀疏A*算法規(guī)劃出多無人機初始航路，將航路中的航路點信息傳遞給文化算法框架模型中的信仰空間。信仰空間包括兩個部分，一部分作為形式知識，存儲最優(yōu)航路中的航路點信息;另一部分作為規(guī)范知識，用來存儲航路點的有效范圍，作為GA尋優(yōu)空間存儲在信仰空間的規(guī)范知識中。有效范圍的確定規(guī)則：沿航路點方向，在避開威脅的情況下包絡的區(qū)域。

如圖6所示，當戰(zhàn)場環(huán)境的某個區(qū)域出現突發(fā)威脅，影響無人機沿原有航路飛行時，需要對原規(guī)劃航路進行重規(guī)劃，只需對突發(fā)威脅影響的部分航路進行重規(guī)劃，以該段航路兩端未受影響的航路點作為航路重規(guī)劃的起點和終點，通過稀疏A*算法與GA相結合，在有效范圍內通過GA優(yōu)選航路點，從而獲得可行最優(yōu)航路。算法步驟如下：

step 1：多空地武器任務執(zhí)行前，使用稀疏A*算法規(guī)劃出各空地武器飛行初始航路;

step 2：提取航路中的航路點信息，確定有效范圍，并將信息作為形式知識在文化算法的信仰空間中進行存儲;

step 3：確定有效范圍，并在有效范圍內通過GA確定優(yōu)選航路點，獲取優(yōu)選航路;

step 4：多空地武器按照優(yōu)選航路飛行，如遇突發(fā)威脅，進入step 5;否則進入step 6;

step 5：以突發(fā)威脅影響的航路兩端航路點作為起點與終點，在有效范圍內使用稀疏A*算法進行航路重規(guī)劃;返回step 2;

step 6：判斷各空地武器是否飛抵目標點;否，返回step 4;是，飛行任務結束。

3 算法仿真驗證

為驗證本文提出算法的有效性，利用Matlab R2016a進行仿真算法程序編寫，并借助GUI設計完成算法實驗驗證。想定某作戰(zhàn)部隊派出多枚空地武器載彈從單/多基地同時起飛到達目標任務終點，飛行途中需要對多個軍事目標展開攻擊任務[15]。

3.1 多目標協同優(yōu)化任務規(guī)劃

為測試本文提出的多無人機多目標協同任務規(guī)劃及航路規(guī)劃算法的準確性。仿真程序中對多架無人機起飛降落位置、攻擊目標位置及強度、威脅位置及等級參數進行設置，同時設置執(zhí)行目標攻擊任務的無人機機群數量。具體如下：設置雷達威脅1個，導彈威脅1個，禁飛區(qū)威脅數2個，惡劣天氣威脅1個;多無人機其起飛點位置S坐標（xi（t），yi（t））|i=1=（100，50），終止點位置E坐標（400，450）;待攻擊目標任務5個，分別設置待攻擊目標t1，t3，t5的價值v=1（為簡化仿真驗證過程，等效為1架無人機投1枚彈后，該目標即被摧毀），目標t2，t4的價值為v=3，目標t1，t2，t3，t4，t5的位置坐標（xj（t），yj（t））|j=1，2，3，4，5分別為（160，225），（275，150），（375，300），（150，400），（225，175）;空地武器最大偏航角=45°，最小直飛距離=4 km;稀疏A*算法中為避免重復擴展節(jié)點的問題，擴展節(jié)點數小于7;GA個體數目小于200，最大進化代數500，進化結束條件為達到最大進化代數或該代種群適應度均方差不大于0.001，交叉概率0.7，變異概率0.2。通過運行仿真程序對多空地武器多攻擊目標協同優(yōu)化任務規(guī)劃性能進行驗證，如圖7所示。

由本文算法規(guī)劃出的4枚空地武器目標攻擊路線分別為：P1，P2，P3，P4，各空地武器從起飛到終點，途經各目標任務點的飛行航路如下：P1：S→t5→t2→t3→E，P2：S→t2→E，P3：S→t4→E，P4：S→t1→t4→E。全部待攻擊任務目標均能夠被有效摧毀，驗證了本文提出算法能夠較好地完成多任務空地武器多目標協同優(yōu)化任務規(guī)劃。利用GA各算子優(yōu)化后的新航路較稀疏A*算法[16]規(guī)劃的初始航路總路程短，這是由于文化算法框架下，結合稀疏A*算法規(guī)劃的航路中各航路點能夠在有效范圍內進行航路優(yōu)化，從而實現目標函數代價值最小，在有效避開威脅的前提下，航路最短。

3.2 單目標協同任務規(guī)劃

為驗證本文算法在多空地武器、單目標下的優(yōu)化規(guī)劃性能，假設4枚空地武器分別從4個起飛點出發(fā)，位置坐標分別為：（xi（t），yi（t））|i=1，2，3，4=（150，50），（450，230），（400，300），（170，450）;終止點（xE（t），yE（t））=（160，250）。其他參數設置不變。

通過運行仿真程序，對本文提出算法在多空地武器攻擊單目標協同任務規(guī)劃性能進行驗證，仿真實驗結果如圖8所示。

可以看出，各空地武器分別從4個不同起始點向目標點進行飛行，并能夠有效地避開各種威脅到達攻擊任務目標終點，在實際戰(zhàn)場作戰(zhàn)中，為確?？盏匚淦髂軌蛲瑫r攻擊目標，可規(guī)劃各空地武器的起飛時間，以實現各空地武器同時到達。

3.3 威脅動態(tài)改變下的算法驗證

當空地武器任務執(zhí)行過程中，威脅位置及強度均有可能發(fā)生變化，為驗證本文提出算法在重規(guī)劃航路中的有效性，仿真任務執(zhí)行途中禁飛區(qū)及導彈威脅位置發(fā)生動態(tài)改變時，本文算法重規(guī)劃出的局部飛行航路，如圖9所示。

由圖9（b）可以看出，當空地武器飛至坐標點（225，225）時，因禁飛區(qū)1與導彈威脅位置變化，初始航路從當前航路點到下一航路點重規(guī)劃出一條新的航路，新航路能夠有效避開威脅影響，并且以最短飛行距離飛抵終點。驗證了本文提出算法在航路重規(guī)劃中的有效性。

為了比較不同算法的時間復雜度，對多空地武器單起飛點、單終止點以及多起飛點、單終止點的戰(zhàn)場環(huán)境進行仿真實驗。分別應用本文提出算法與稀疏A*算法及GA進行測試，取10次獨立仿真實驗結果的平均值，各算法比較結果如表1所示。

由表1可以看出，本文算法基于稀疏A*算法得到初始航線及航路點，如因威脅變化需要重規(guī)劃飛行航線時，本文算法在文化算法框架下，對有效范圍內引入遺傳算子重規(guī)劃子路徑，從而實現航線優(yōu)化，較傳統GA的航路規(guī)劃時間短，并且當問題復雜時，算法的計算時間無法保證實時性。在航路不發(fā)生動態(tài)規(guī)劃時，稀疏A*算法能夠快速規(guī)劃出航線，飛行總時間最短，但是當威脅影響初始航線時，算法失效。本文算法結合稀疏A*算法能夠快速獲取初始航線，并且借助GA完成了對動態(tài)航線的重規(guī)劃。

4 結 束 語

針對多空地武器多目標協同優(yōu)化任務規(guī)劃問題，本文基于文化算法結構，結合稀疏A*算法與GA實現最優(yōu)化航路規(guī)劃，完成多目標及單目標任務優(yōu)化仿真實驗。實驗結果表明，該算法能夠根據復雜戰(zhàn)場環(huán)境下的任務需求，為多空地武器規(guī)劃出滿足生存概率和攻擊任務的優(yōu)選航路。

參考文獻：

[1] 劉超. 基于改進遺傳算法的多無人機航路規(guī)劃方法[J]. 火力與指揮控制，2019，44（1）： 18-22.

Liu Chao. Method of Path Planning for Multi-UAV Based on Improved Genetic Algorithm[J]. Fire Control & Command Control，2019，44（1）： 18-22.（in Chinese）

[2] Reynolds R G，Kinnaird-Heether L. Optimization Problem Solving with Auctions in Cultural Algorithms[J]. Memetic Computing，2013，5（2）： 83-94.

[3] 歐陽志宏，李修和. 基于任務區(qū)分的無人機航路規(guī)劃方法[J]. 彈箭與制導學報，2017，37（3）： 114-118.

Ouyang Zhihong，Li Xiuhe. Methods of Route Planning of UAV Based on Task Differentiation[J]. Journal of Projectiles，Rockets，Missiles and Guidance，2017，37（3）： 114-118.（in Chinese）

[4] 謝啟龍，宋龍，魯浩，等. 協同導航技術研究綜述[J]. 航空兵器，2019，26（4）： 23-30.

Xie Qilong，Song Long，Lu Hao，et al. Review of Collaborative Navigation Technology[J]. Aero Weaponry，2019，26（4）： 23-30.（in Chinese）

[5] 梁國偉，王社偉，趙雪森. 多無人機協同任務分配方法[J]. 火力與指揮控制，2014，39（11）： 13-17.

Liang Guowei，Wang Shewei，Zhao Xuesen. Method Research on Cooperative Task Allocation for Multiple UCAVs[J]. Fire Control & Command Control，2014，39（11）： 13-17.（in Chinese）

[6] 占偉偉，王偉，陳能成，等. 一種利用改進A*算法的無人機航跡規(guī)劃[J]. 武漢大學學報： 信息科學版，2015，40（3）： 315-320.

Zhan Weiwei，Wang Wei，Chen Nengcheng，et al. Path Planning Strategies for UAV Based on Improved A* Algorithm[J]. Geoma-tics and Information Science of Wuhan University，2015，40（3）： 315-320.（in Chinese）

[7] 李湘清，孫秀霞，王棟，等. 基于遺傳算法的UCAV動態(tài)任務分配模型及研究[J]. 系統仿真學報，2008，20（16）： 4387-4389.

Li Xiangqing，Sun Xiuxia，Wang Dong，et al. Dynamic UCAV Mission Assignment Using Genetic Algorithm[J]. Journal of System Simulation，2008，20（16）： 4387-4389.（in Chinese）

[8] Manathara J G，Sujit P B，Beard R W. Multiple UAV Coalitions for a Search and Prosecute Mission[J]. Journal of Intelligent & Robotic Systems，2011，62（1）： 125-158.

[9] 曹良秋，吳立巍. 基于遺傳算法的無人機航路規(guī)劃研究[J]. 科技創(chuàng)新與應用，2018（24）： 27-30.

Cao Liangqiu，Wu Liwei. Research on Unmanned Aerial Vehicle（UAV） Route Planning Based on Genetic Algorithm[J]. Techno-logy Innovation and Application，2018（24）： 27-30.（in Chinese）

[10] 方群，徐青. 基于改進粒子群算法的無人機三維航跡規(guī)劃[J]. 西北工業(yè)大學學報，2017，35（1）： 66-73.

Fang Qun，Xu Qing. 3D Route Planning for UAV Based on Improved PSO Algorithm[J]. Journal of Northwestern Polytechnical University，2017，35（1）： 66-73.（in Chinese）

[11] Liu J H，Yang J G，Liu H P，et al. An Improved Ant Colony Algorithm for Robot Path Planning[J]. Soft Computing，2017，21（19）： 5829-5839.

[12] 李煒，張偉. 基于粒子群算法的多無人機任務分配方法[J]. 控制與決策，2010，25（9）： 1359-1363.

Li Wei，Zhang Wei. Method of Tasks Allocation of Multi-UAVs Based on Particles Swarm Optimization[J]. Control and Decision，2010，25（9）： 1359-1363.（in Chinese）

[13] 龐強偉，胡永江，李文廣，等. 多無人機協同偵察任務規(guī)劃方法研究綜述[J]. 電訊技術，2019，59（6）： 741-748.

Pang Qiangwei，Hu Yongjiang，Li Wenguang，et al. Research on Multi-UAV Cooperative Reconnaissance Mission Planning Methods： An Overview[J]. Telecommunication Engineering，2019，59（6）： 741-748.（in Chinese）

[14] Yao P，Wang H L，Su Z K. Cooperative Path Planning with Applications to Target Tracking and Obstacle Avoidance for Multi-UAVs[J]. Aerospace Science and Technology，2016，54： 10-22.

[15] 劉暢，謝文俊，張鵬，等. 多基地多無人機航跡避障任務規(guī)劃[J]. 計算機工程，2019，45（11）： 275-280.

Liu Chang，Xie Wenjun，Zhang Peng，et al. Mission Planning for Multi-Base Multi-UAV Obstacle Avoidance[J]. Computer Engineering，2019，45（11）： 275-280.（in Chinese）

[16] 李軍華，劉群芳. 基于稀疏A*算法與文化算法的無人機動態(tài)航跡規(guī)劃[J]. 應用科學學報，2017，35（1）： 128-138.

Li Junhua，Liu Qunfang. Dynamic Path Planning of Unmanned Aerial Vehicle Based on Sparse A* Algorithm and Cultural Algorithm[J]. Journal of Applied Sciences，2017，35（1）： 128-138.（in Chinese）

[17] 張弛，丁軼. 基于遺傳算法的無人機航路規(guī)劃研究[J]. 信息化研究，2018，44（4）： 10-16.

Zhang Chi，Ding Yi. Research on UAV Route Planning Based on Genetic Algorithm[J]. Informatization Research，2018，44（4）： 10-16.（in Chinese）

Research on Multi-Mission Airborne Weapon Multi-Target

Cooperative Optimization Planning Algorithm

Chen Yu1*，Zhang Gongping2，3，Song Tao4，Wen Xinling1，Ma Zhengxiang1，Liu Zhaoyu1，Qin Yuxin1

（1. Zhengzhou Institute of Aeronautics，Zhengzhou 450046，China;2. China Airborne Missile Academy，Luoyang 471009，China;

3. Aviation Key Laboratory of Science and Technology on Airborne Guided Weapons，Luoyang 471009，China;

4. School of Aerospace Engineering，Beijing Institute of Technology，Beijing 100081，China）

Abstract： In a complex battlefield environment，there may be multiple dynamic threats，how to quickly plan the optimal flight path is the key to the successful execution of the attack mission. Under the cultural algorithm framework，a kind of dynamic flight path planning algorithm used in the multi-mission airborne weapon multi-target cooperative optimization planning combining sparse A* algorithm with Genetic Algorithm （GA） algorithm is proposed. Based on the cultural algorithm framework，the sparse A* algorithm is used to quickly obtain information of initial flight path and navigation nodes，and the acquired information is sent to the belief space as knowledge for storage，so as to guide the population space to achieve the optimal target task allocation and route acquisition by GA algorithm within the effective range. Simulation results show that the algorithm can effectively avoid? threats，reduce the overall flight distance of flight path，and complete the multi-mission airborne weapon multi-target collaborative planning.

Key words： air-to-surface weapon;collaborative optimization;task assignment;genetic algorithm;sparse A* algorithm

收稿日期：2020-02-07

基金項目：國家自然科學基金項目（51975539）;航空科學基金重點實驗室項目（20170155）;河南省科技攻關項目（192102210109;202102210137;212102210517）

作者簡介：陳宇（1978-），男，河南鄭州人，副教授，博士，研究方向為無人機飛控導航技術。