趙慶璐，周成平

（華中科技大學(xué)自動化學(xué)院多譜信息處理技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室，武漢 430074）

0 引言

由于防空體系的不斷完善、戰(zhàn)場環(huán)境的瞬息萬變，單個飛行器的突防概率明顯降低，與此同時，在實(shí)際應(yīng)用中往往需要同時對多個目標(biāo)進(jìn)行協(xié)同攻擊甚至飽和攻擊。因此，多任務(wù)的協(xié)同航跡規(guī)劃是當(dāng)前亟待解決的問題。所謂協(xié)同航跡規(guī)劃是指在指定的規(guī)劃空間中，滿足飛行器自身約束、環(huán)境約束、協(xié)同約束等條件下，規(guī)劃出從發(fā)射點(diǎn)集到目標(biāo)點(diǎn)集的無碰撞的最優(yōu)航跡組合，使得發(fā)射時間區(qū)間和到達(dá)目標(biāo)時間區(qū)間盡可能小。Chandler［1］等和 Mclain［2］等提出了基于Voronoi圖的協(xié)同航跡規(guī)劃方法，該方法減小了解空間，加快了收斂速度，但沒有包括地形高度信息，無法通過調(diào)整高度規(guī)避威脅，并且無法解決基于匹配輔助制導(dǎo)的規(guī)劃問題;鄭昌文［3］、嚴(yán)平［4］、史戰(zhàn)偉［5］、葉嬡嬡［6］等提出了基于進(jìn)化算法的協(xié)同航跡規(guī)劃方法，該類方法雖然隱含了單任務(wù)與協(xié)同航跡共同進(jìn)化的機(jī)制，但對單任務(wù)進(jìn)化方向的引導(dǎo)力較弱，收斂速度慢，當(dāng)任務(wù)數(shù)較多時不能滿足規(guī)劃的時間約束。

文中提出了一種基于遺傳算法的協(xié)同航跡規(guī)劃方法。該方法的主要特點(diǎn)是采用雙層進(jìn)化機(jī)制，不同飛行器形成各自的航跡種群用于下層進(jìn)化，對不同飛行器的航跡進(jìn)行不同的組合形成協(xié)同航跡組種群用于上層進(jìn)化。在規(guī)劃的過程中，通過狀態(tài)表征矩陣表征各飛行器在協(xié)同航跡組中的貢獻(xiàn)，進(jìn)而引導(dǎo)飛行器向使協(xié)同代價變小的方向進(jìn)化，收斂速度快，可以減少協(xié)同規(guī)劃的時間。

1 基于遺傳算法的協(xié)同航跡規(guī)劃

1.1 協(xié)同規(guī)劃模型

根據(jù)協(xié)同作戰(zhàn)的應(yīng)用背景，協(xié)同規(guī)劃主要有以下幾種模式:指定發(fā)射時間序列，使到達(dá)時間窗口盡可能小;指定到達(dá)時間序列，使發(fā)射時間窗口盡可能小;指定發(fā)射時間序列和到達(dá)時間序列，使到達(dá)時間誤差盡可能小;指定某個任務(wù)的發(fā)射時間或到達(dá)時間，使發(fā)射時間窗口和到達(dá)時間窗口盡可能小。在真實(shí)的作戰(zhàn)環(huán)境下，某個任務(wù)可能具有戰(zhàn)略意義，對該任務(wù)的發(fā)射時間或到達(dá)時間也就有強(qiáng)約束，因此文中的研究內(nèi)容針對最后一種模式，即指定某個任務(wù)的發(fā)射時間或到達(dá)時間，使發(fā)射時間區(qū)間和到達(dá)時間區(qū)間盡可能小。

1.2 協(xié)同規(guī)劃算法

1.2.1 雙層進(jìn)化機(jī)制

本算法首先將協(xié)同規(guī)劃問題拆分成多個子問題，每個子問題為單任務(wù)規(guī)劃，所有子問題的解的組合構(gòu)成協(xié)同規(guī)劃問題的一個完整解。利用遺傳算法為每個子問題初始化一個子種群，從不同的子種群中選擇航跡進(jìn)行組合形成協(xié)同航跡組種群，子種群在進(jìn)化的過程中受到協(xié)同航跡組種群提供的信息的引導(dǎo)，同時協(xié)同航跡組種群隨著各子種群的進(jìn)化而進(jìn)化。其中，子種群的進(jìn)化對應(yīng)本算法的下層進(jìn)化，協(xié)同航跡組種群的進(jìn)化對應(yīng)本算法的上層進(jìn)化。

1.2.2 下層進(jìn)化評價與引導(dǎo)信息

下層進(jìn)化是指各飛行器的可行航跡種群的進(jìn)化，為了提高進(jìn)化效率、加快收斂速度，文中首次提出了狀態(tài)表征矩陣的概念，用于表征各飛行器的航跡在協(xié)同航跡組中的貢獻(xiàn)，狀態(tài)表征矩陣如下式所示:

式中:N為任務(wù)數(shù);K為協(xié)同航跡組數(shù);m為指定的任務(wù)編號;aij表示第j個任務(wù)在第i個協(xié)同航跡組中的貢獻(xiàn)，aij的定義如下:

式中:lengthij表示第i個協(xié)同航跡組中任務(wù)j的航跡長度，lengthim表示第i個協(xié)同航跡組中指定任務(wù)的航跡長度。根據(jù)狀態(tài)表征矩陣求出引導(dǎo)每個任務(wù)進(jìn)化的αi、β算子，其中 αi引導(dǎo)任務(wù)i進(jìn)化，β引導(dǎo)指定的任務(wù)進(jìn)化，αi、β的定義如下式所示:

1.2.3 上層進(jìn)化評價與引導(dǎo)信息

上層進(jìn)化是指協(xié)同航跡組種群的進(jìn)化，它通過協(xié)同評價函數(shù)引導(dǎo)，協(xié)同航跡組的評價函數(shù)應(yīng)綜合考慮影響協(xié)同性能的各種因素，文中結(jié)合實(shí)際應(yīng)用背景以及協(xié)同規(guī)劃模型，主要從以下兩個方面進(jìn)行評價:

1）協(xié)同航跡組中各任務(wù)的單航跡代價;

2）發(fā)射時間窗口與到達(dá)時間窗口。

評價函數(shù)的定義如下:

式中:T1為發(fā)射時間窗口;T2為到達(dá)時間窗口為協(xié)同航跡組中單航跡的代價之和;fi為任務(wù)i對應(yīng)的航跡代價;ω1、ω2、ω3為權(quán)系數(shù)，通過調(diào)節(jié)權(quán)系數(shù)的大小可以使協(xié)同航跡組向不同的方向進(jìn)化。

1.2.4 碰撞檢測與調(diào)整

航跡碰撞檢測的空間是四維空間，即在同一時刻不同航跡的三維坐標(biāo)之間的距離是否小于最小安全距離，具體的檢測方法是:以最早的發(fā)射時間tmin為起點(diǎn)，按照一定的時間間隔Δt沿時間軸采樣，計算航跡在當(dāng)前時刻的三維坐標(biāo)進(jìn)而求出飛行器之間的距離，直到達(dá)到最晚到達(dá)時間tmax。若在所有時刻飛行器之間的距離均大于最小安全距離，則飛行器之間無碰撞，否則首先通過局部速度調(diào)節(jié)避免碰撞，若不能滿足要求，則通過高度調(diào)整避免碰撞。

1.2.5 算法描述

在本算法中，若任務(wù)數(shù)為N，則協(xié)同航跡組由N條航跡組成，算法的終止條件為:達(dá)到最大進(jìn)化代數(shù)或最優(yōu)個體滿足代價要求，具體步驟如下:

1）為每個任務(wù)隨機(jī)生成大小為M的可行航跡種群;

2）隨機(jī)生成K個協(xié)同航跡組;

3）若終止條件滿足，轉(zhuǎn)7），否則，轉(zhuǎn)4）;

4）若達(dá)到上層最大進(jìn)化代數(shù)，轉(zhuǎn)6），否則，轉(zhuǎn)5）;

5）按適應(yīng)度大小選擇協(xié)同航跡組執(zhí)行上層進(jìn)化，轉(zhuǎn)4）;

6）計算αi、β算子引導(dǎo)各任務(wù)的可行航跡種群執(zhí)行下層進(jìn)化，轉(zhuǎn)3）;

7）選擇協(xié)同代價最小的協(xié)同航跡組進(jìn)行碰撞檢測與調(diào)整，進(jìn)化過程結(jié)束。

2 在有向航跡網(wǎng)絡(luò)圖上的應(yīng)用

文中將該算法應(yīng)用于有向航跡網(wǎng)絡(luò)圖［7］，網(wǎng)絡(luò)圖的生成是在考慮飛行器自身約束和環(huán)境約束的條件下，將柵格規(guī)劃空間按一定大小劃分為格網(wǎng)空間，在格網(wǎng)中選擇匹配點(diǎn)或GPS導(dǎo)航點(diǎn)，然后以某一網(wǎng)格為起點(diǎn)向其它網(wǎng)格擴(kuò)展連接，直到所有的網(wǎng)格擴(kuò)展完成。擴(kuò)展過程中考慮的約束條件主要有:匹配輔助制導(dǎo)約束、禁飛區(qū)/威脅區(qū)約束、水平機(jī)動約束、高度機(jī)動約束、飛行管道約束、飛行高度約束。生成的有向航跡網(wǎng)絡(luò)圖如圖1所示。

圖1 網(wǎng)絡(luò)圖示意圖

2.1 網(wǎng)絡(luò)圖存儲結(jié)構(gòu)

在有向航跡網(wǎng)絡(luò)圖上規(guī)劃的實(shí)質(zhì)是圖搜索，即將合適的航跡段進(jìn)行連接。為了減小內(nèi)存訪問數(shù)據(jù)庫的頻率、加快規(guī)劃速度，將網(wǎng)絡(luò)圖分兩層進(jìn)行存儲:規(guī)劃層、節(jié)點(diǎn)層。其中，規(guī)劃層包含在規(guī)劃的過程中所用到的航跡段信息，節(jié)點(diǎn)層包含航跡段上的具體節(jié)點(diǎn)信息，兩層之間的橋梁是航跡段編號。網(wǎng)絡(luò)圖在數(shù)據(jù)庫中的存儲結(jié)構(gòu)如圖2所示。

圖2 航跡網(wǎng)絡(luò)圖存儲結(jié)構(gòu)示意圖

2.2 種群初始化

本算法用染色體表示航跡，如圖3所示。染色體上的節(jié)點(diǎn)（基因）包含如下信息:航跡段編號IDi、航跡段長度Li、航跡段代價Ci，即任務(wù)的可行航跡是航跡網(wǎng)絡(luò)上特定航跡段的組合。對每個任務(wù)隨機(jī)初始化M條航跡，組成該任務(wù)的可行航跡種群，用于下層進(jìn)化。

圖3 染色體結(jié)構(gòu)

若任務(wù)總數(shù)為N，則初始化生成了M*N條染色體，從每個任務(wù)種群中隨機(jī)選擇一條染色體，N條染色體構(gòu)成一個協(xié)同航跡組（個體），初始化K個個體組成協(xié)同航跡組種群，用于上層進(jìn)化。

2.3 下層進(jìn)化算子

在遺傳算法中引導(dǎo)種群進(jìn)化的算子多種多樣，考慮到染色體的結(jié)構(gòu)以及規(guī)劃空間的特殊性，在下層進(jìn)化中選擇變異算子作為種群的進(jìn)化算子。隨機(jī)選擇擾動點(diǎn)，若αi≥0，表示任務(wù)i的航跡在所有航跡中較長，則在擾動點(diǎn)處按概率選擇較短的航跡段，否則選擇較長的航跡段;同理，若β≥0，表示指定任務(wù)的航跡在所有航跡中較短，則在擾動點(diǎn)處按概率選擇較長的航跡段，否則選擇較短的航跡段。對航跡p的隨機(jī)擾動點(diǎn)執(zhí)行變異操作的公式如下:

2.4 上層進(jìn)化算子

在上層進(jìn)化中采用兩種進(jìn)化算子:交叉算子、變異算子，如圖4所示。

圖4 進(jìn)化算子

交叉算子:按適應(yīng)度大小選擇兩個父代個體，隨機(jī)選擇交叉點(diǎn)將兩個體分割為兩部分，然后將兩父代個體的后半部分相互交換，生成兩個新的子個體，兩父個體的交叉點(diǎn)位置相同。

變異算子:按適應(yīng)度大小選擇父代個體，隨機(jī)選擇變異點(diǎn)，從變異點(diǎn)所對應(yīng)的任務(wù)的航跡種群中隨機(jī)選取一條替換原來的航跡，生成新的子個體。

3 實(shí)驗(yàn)結(jié)果

本算法在 CPU為 Core E7200 2.53 GHz、內(nèi)存2.0 GB的PC機(jī)上進(jìn)行了實(shí)驗(yàn)，運(yùn)行環(huán)境為Windows XP，編程環(huán)境為VS2005。實(shí)驗(yàn)使用了分辨率為30*30的數(shù)字地形高程圖和模擬生成的禁飛區(qū)數(shù)據(jù)，實(shí)驗(yàn)中的參數(shù)設(shè)置如下:ω1=0、ω2=0.9、ω3=0.1，實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

圖5 二維顯示

圖6 剖面顯示

其中，多邊形區(qū)域表示禁飛區(qū)，旗幟和三角形分別表示發(fā)射區(qū)和目標(biāo)區(qū)，航跡上的圓點(diǎn)表示導(dǎo)航點(diǎn)。同時文中對標(biāo)準(zhǔn)遺傳算法進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖7、圖8所示。

表1給出了以上任務(wù)的部分實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)中任務(wù)①為指定的任務(wù)，表示協(xié)同航跡組的收斂程度，式中:li為協(xié)同航跡組中任務(wù)i對應(yīng)的航跡長度。實(shí)驗(yàn)結(jié)果表明，該算法與標(biāo)準(zhǔn)遺傳算法相比，在兩者規(guī)劃出的協(xié)同航跡組的收斂程度相近的情況下，該算法能夠大大的減少規(guī)劃時間。

圖7 二維顯示

圖8 剖面顯示

表1 實(shí)驗(yàn)數(shù)據(jù)

4 結(jié)論

文中提出了一種基于遺傳算法的協(xié)同航跡規(guī)劃方法，該方法采用雙層進(jìn)化機(jī)制，即單任務(wù)進(jìn)化、協(xié)同進(jìn)化，并通過狀態(tài)表征矩陣引導(dǎo)各任務(wù)種群進(jìn)化，加快了收斂速度。實(shí)驗(yàn)結(jié)果表明，在滿足飛行器自身約束、環(huán)境約束、協(xié)同約束的條件下，該方法能夠在較短的時間內(nèi)規(guī)劃出較優(yōu)的協(xié)同航跡組。

［1］Chandler P，Rasmussen S，Pachter M.UAV cooperative path planning［C］//Proc Guidance，Navigation and Control Conf，AIAA，2000.

［2］McLain T，Beard R.Trajectory planning for coordinated rendezvous of unmanned air vehicles［C］//Proc Guidance，Navigation and Control Conf，AIAA，2000.

［3］鄭昌文，丁明躍，周成平，等.多飛行器協(xié)調(diào)航跡規(guī)劃方法［J］.宇航學(xué)報，2003，24（2）:115－120.

［4］Yan Ping，Ding Mingyue，Zheng Changwen.Coodinated route planning via Nash equilibrium and evolutionary computation［J］.Chinese Journal of Aeronautics，2006，19（1）:18－23.

［5］史戰(zhàn)偉，周成平，丁明躍，等.基于進(jìn)化計算的多無人飛行器協(xié)同航跡規(guī)劃［J］.戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2007（5）:49－53.

［6］葉媛媛，閔春平.多無人機(jī)協(xié)同航路規(guī)劃的共同進(jìn)化方法［J］.計算機(jī)仿真，2007，24（5）:37－39.

［7］周志鵬，周成平，趙慶璐.一種用于航跡規(guī)劃的網(wǎng)絡(luò)圖構(gòu)造方法研究［J］.彈箭與制導(dǎo)學(xué)報，2013，33（4）:67－70.

［8］吳昊，任敏，薛宏濤，等.航跡數(shù)據(jù)庫及其在航跡規(guī)劃中的應(yīng)用研究［J］.系統(tǒng)仿真技術(shù)及其應(yīng)用，2007（10）:534－537.