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

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

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

中圖分類(lèi)號(hào)： TJ762.2?? 文獻(xiàn)標(biāo)識(shí)碼： A?? 文章編號(hào)： 1673-5048（2021）02-0062-07

0 引? 言

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

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

1 問(wèn)題描述

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

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

（2） 各攻擊目標(biāo)任務(wù)不存在時(shí)間先后等級(jí)順序;

（3） 各無(wú)人機(jī)所受的飛行威脅在不同高度下相同。

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

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

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

（1） 防空導(dǎo)彈攻擊區(qū)域是以自身坐標(biāo)為中心，向外擴(kuò)展的從近邊界到遠(yuǎn)邊界的區(qū)域，在三維空間中類(lèi)似于空心的鼓形，其水平截面形狀是圓周形?？盏匚淦髟谀繕?biāo)區(qū)域飛行過(guò)程中飛行高度比較低，一般不會(huì)超過(guò)導(dǎo)彈的最大攻擊高度。因此，導(dǎo)彈威脅建模時(shí)可忽略高度影響，從而簡(jiǎn)化模型。仿真實(shí)驗(yàn)中以某點(diǎn)作為威脅中心，以一定半徑的圓周及作用強(qiáng)度來(lái)表示不同擊落概率的威脅區(qū)域（高炮威脅與導(dǎo)彈威脅類(lèi)似）;

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

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

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

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

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

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

1.2 無(wú)人機(jī)任務(wù)規(guī)劃模型構(gòu)建

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

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

1.2.1 目標(biāo)函數(shù)

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

（1）損傷代價(jià)

在對(duì)目標(biāo)對(duì)象攻擊過(guò)程中，空地武器如何能夠有效地避開(kāi)敵方雷達(dá)、高射炮、導(dǎo)彈以及地形、惡劣天氣等威脅，以保證空地武器損傷代價(jià)最小是任務(wù)關(guān)鍵：

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

式中： Kij為第i枚空地武器打擊第j個(gè)目標(biāo)的威脅概率。

（2）飛行總距離

滿(mǎn)足各空地武器飛行油耗（距離）限制，有效避開(kāi)各威脅的情況下，根據(jù)待攻擊目標(biāo)任務(wù)的摧毀等級(jí)，各空地武器完成對(duì)待攻擊目標(biāo)的任務(wù)分配，且各空地武器飛行總距離之和最短：

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

式中：sij為第i枚空地武器打擊第j個(gè)目標(biāo)的飛行距離。

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

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

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

式中： t（i，i+1）j為第i枚與第i+1枚空地武器打擊第j個(gè)目標(biāo)的時(shí)間間隔。

1.2.2 約束條件

在航路評(píng)價(jià)建模中，設(shè)置空地武器在執(zhí)行下一動(dòng)作前需要進(jìn)行一定距離的平飛，最小直飛航路長(zhǎng)度Lmin，空地武器最大轉(zhuǎn)彎角θ?？盏匚淦髂繕?biāo)攻擊執(zhí)行能力約束如下：

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

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

式中：M為第i架無(wú)人機(jī)的最大載彈量。假設(shè)各空地武器均需載彈從起點(diǎn)到達(dá)終點(diǎn)，最小載彈量不少于1枚，即需要攻擊不少于1個(gè)目標(biāo)。多枚空地武器對(duì)各目標(biāo)任務(wù)進(jìn)行攻擊的過(guò)程中，載彈總量不能大于待攻擊目標(biāo)的總價(jià)值Vall。

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

綜上所述，多目標(biāo)協(xié)同任務(wù)規(guī)劃目標(biāo)函數(shù)Z=min{α（εf1+θf(wàn)2）+βf3}時(shí)，航路規(guī)劃為最優(yōu)。其中，0≤α，β，ε，θ≤1，0≤α+β≤1，0≤ε+θ≤1，α，β，ε，θ的權(quán)重取值取決于指揮員對(duì)各攻擊任務(wù)的決策部署。

2 算法設(shè)計(jì)

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

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

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

2.1 稀疏A*算法

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

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

在航路規(guī)劃過(guò)程中，航路代價(jià)函數(shù)通過(guò)航路長(zhǎng)度和威脅代價(jià)進(jìn)行評(píng)價(jià)，航路長(zhǎng)度與威脅代價(jià)之間通常相互矛盾，本文首先根據(jù)稀疏A*算法確定航路評(píng)價(jià)函數(shù)：

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

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

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é)點(diǎn)j-1到節(jié)點(diǎn)j之間的航路長(zhǎng)度及威脅值;ω1，ω2，ω3為權(quán)重系數(shù)。為使空地武器在威脅相對(duì)小的區(qū)域內(nèi)完成飛行及攻擊任務(wù)，某段飛行航路中的威脅指數(shù)如下：

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

式中：Kk代表第k個(gè)威脅源的強(qiáng)度;Rik表示第i個(gè)空地武器距離第k個(gè)威脅源的距離;s表示威脅源個(gè)數(shù)。待攻擊的目標(biāo)任務(wù)節(jié)點(diǎn)為必經(jīng)節(jié)點(diǎn)，di（x，y）為第i枚空地武器從當(dāng)前節(jié)點(diǎn)位置j到目標(biāo)點(diǎn)之間的航路估計(jì)長(zhǎng)度。

2.2 遺傳算法

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

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

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

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

2.3 算法實(shí)現(xiàn)

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

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

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

step 2：提取航路中的航路點(diǎn)信息，確定有效范圍，并將信息作為形式知識(shí)在文化算法的信仰空間中進(jìn)行存儲(chǔ);

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

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

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

step 6：判斷各空地武器是否飛抵目標(biāo)點(diǎn);否，返回step 4;是，飛行任務(wù)結(jié)束。

3 算法仿真驗(yàn)證

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

3.1 多目標(biāo)協(xié)同優(yōu)化任務(wù)規(guī)劃

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

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

3.2 單目標(biāo)協(xié)同任務(wù)規(guī)劃

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

通過(guò)運(yùn)行仿真程序，對(duì)本文提出算法在多空地武器攻擊單目標(biāo)協(xié)同任務(wù)規(guī)劃性能進(jìn)行驗(yàn)證，仿真實(shí)驗(yàn)結(jié)果如圖8所示。

可以看出，各空地武器分別從4個(gè)不同起始點(diǎn)向目標(biāo)點(diǎn)進(jìn)行飛行，并能夠有效地避開(kāi)各種威脅到達(dá)攻擊任務(wù)目標(biāo)終點(diǎn)，在實(shí)際戰(zhàn)場(chǎng)作戰(zhàn)中，為確?？盏匚淦髂軌蛲瑫r(shí)攻擊目標(biāo)，可規(guī)劃各空地武器的起飛時(shí)間，以實(shí)現(xiàn)各空地武器同時(shí)到達(dá)。

3.3 威脅動(dòng)態(tài)改變下的算法驗(yàn)證

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

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

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

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

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

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

參考文獻(xiàn)：

[1] 劉超. 基于改進(jìn)遺傳算法的多無(wú)人機(jī)航路規(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] 歐陽(yáng)志宏，李修和. 基于任務(wù)區(qū)分的無(wú)人機(jī)航路規(guī)劃方法[J]. 彈箭與制導(dǎo)學(xué)報(bào)，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] 謝啟龍，宋龍，魯浩，等. 協(xié)同導(dǎo)航技術(shù)研究綜述[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] 梁國(guó)偉，王社偉，趙雪森. 多無(wú)人機(jī)協(xié)同任務(wù)分配方法[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] 占偉偉，王偉，陳能成，等. 一種利用改進(jìn)A*算法的無(wú)人機(jī)航跡規(guī)劃[J]. 武漢大學(xué)學(xué)報(bào)： 信息科學(xué)版，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動(dòng)態(tài)任務(wù)分配模型及研究[J]. 系統(tǒng)仿真學(xué)報(bào)，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] 曹良秋，吳立巍. 基于遺傳算法的無(wú)人機(jī)航路規(guī)劃研究[J]. 科技創(chuàng)新與應(yī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] 方群，徐青. 基于改進(jìn)粒子群算法的無(wú)人機(jī)三維航跡規(guī)劃[J]. 西北工業(yè)大學(xué)學(xué)報(bào)，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] 李煒，張偉. 基于粒子群算法的多無(wú)人機(jī)任務(wù)分配方法[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] 龐強(qiáng)偉，胡永江，李文廣，等. 多無(wú)人機(jī)協(xié)同偵察任務(wù)規(guī)劃方法研究綜述[J]. 電訊技術(shù)，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] 劉暢，謝文俊，張鵬，等. 多基地多無(wú)人機(jī)航跡避障任務(wù)規(guī)劃[J]. 計(jì)算機(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*算法與文化算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃[J]. 應(yīng)用科學(xué)學(xué)報(bào)，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] 張弛，丁軼. 基于遺傳算法的無(wú)人機(jī)航路規(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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（51975539）;航空科學(xué)基金重點(diǎn)實(shí)驗(yàn)室項(xiàng)目（20170155）;河南省科技攻關(guān)項(xiàng)目（192102210109;202102210137;212102210517）

作者簡(jiǎn)介：陳宇（1978-），男，河南鄭州人，副教授，博士，研究方向?yàn)闊o(wú)人機(jī)飛控導(dǎo)航技術(shù)。