時(shí)序耦合約束下的多無人機(jī)協(xié)同任務(wù)決策研究

張耀中, 陳嵐, 史國慶, 郭操

(1.西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072; 2.沈陽飛機(jī)設(shè)計(jì)研究所, 遼寧 沈陽 110035)

無人機(jī)(unmanned aerial vehicle,UAV)具有隱身性好、自主能力強(qiáng)、可重回收等特點(diǎn),能夠代替有人機(jī)執(zhí)行“枯燥、惡劣、危險(xiǎn)”的任務(wù),減少參戰(zhàn)人員的傷亡,降低裝備和使用成本等,其軍事地位正不斷提高,逐漸成為現(xiàn)代戰(zhàn)場上的重要作戰(zhàn)力量[1]。早期的無人機(jī)由于功能單一通常執(zhí)行戰(zhàn)場目標(biāo)偵察、跟蹤、監(jiān)視等單類型任務(wù),隨著無人機(jī)平臺(tái)以及各類載荷技術(shù)的快速發(fā)展,無人機(jī)的功能不斷完善,任務(wù)能力不斷增強(qiáng),已經(jīng)逐步轉(zhuǎn)化為能夠執(zhí)行一系列復(fù)雜任務(wù)的多用途空中作戰(zhàn)平臺(tái),如壓制敵防空系統(tǒng)(suppression of enemy air defense,SEAD)、電子攻擊、滲透式偵察/打擊等任務(wù)。SEAD主要指對特定區(qū)域的敵方防空系統(tǒng)(預(yù)警雷達(dá)站、地面防空導(dǎo)彈雷達(dá)陣地以及通信/指揮控制站等)實(shí)施打擊摧毀,使其暫時(shí)或永久失去作戰(zhàn)能力,從而極大削弱敵方的防空力量[2]。

在SEAD作戰(zhàn)任務(wù)中,假定每個(gè)目標(biāo)都已事先偵察確認(rèn),則需要無人機(jī)分別對這些目標(biāo)執(zhí)行打擊和毀傷評估2類子任務(wù)[3]。且打擊任務(wù)完成后必須在特定的時(shí)間內(nèi)執(zhí)行相應(yīng)的毀傷評估任務(wù),因此這2類子任務(wù)間具有特定的時(shí)序耦合約束關(guān)系。

如何有效執(zhí)行特定時(shí)序耦合約束下的多個(gè)任務(wù)已經(jīng)成為當(dāng)前無人機(jī)協(xié)同打擊領(lǐng)域的研究熱點(diǎn)問題之一。國內(nèi)外的研究者提出了不少相應(yīng)的解決方案,并取得了一定的成果,如文獻(xiàn)[4]以多無人機(jī)協(xié)同執(zhí)行搜索——打擊任務(wù)為背景,提出了一種PTCFA聯(lián)盟組建算法,在搜索到目標(biāo)時(shí),由leader組建針對該目標(biāo)的打擊聯(lián)盟和毀傷評估聯(lián)盟,同時(shí)滿足相應(yīng)的約束條件,是一種比較有效的分配方法,但是該算法對無人機(jī)資源約束做了較多的簡化處理。文獻(xiàn)[5]對集中式控制和分布式控制進(jìn)行比較后認(rèn)為當(dāng)無人機(jī)執(zhí)行相互約束性強(qiáng)的任務(wù)時(shí),集中式控制往往能獲得更好的性能。文獻(xiàn)[6]同時(shí)考慮了多無人機(jī)的空間協(xié)同約束、任務(wù)執(zhí)行時(shí)序約束和時(shí)間約束等多類協(xié)同約束關(guān)系,給出了求解策略,但算法搜索空間巨大,難以在有效時(shí)間尋找最優(yōu)解。文獻(xiàn)[7]考慮了單任務(wù)規(guī)劃中的優(yōu)先級(jí)約束,規(guī)定具有較低優(yōu)先級(jí)的任務(wù)必須在具有較高優(yōu)先級(jí)的任務(wù)執(zhí)行之后才能被分配,但算法在考慮2種以上任務(wù)類型時(shí)的尋優(yōu)時(shí)間隨著任務(wù)的增多而呈指數(shù)增長,大規(guī)模動(dòng)態(tài)任務(wù)規(guī)劃難以實(shí)現(xiàn)。文獻(xiàn)[8]采用分布式方法建立了具有時(shí)序約束的任務(wù)分配模型,將任務(wù)按優(yōu)先級(jí)分層,運(yùn)用擴(kuò)展的一致性束算法進(jìn)行求解,對比集中式算法,求解結(jié)果相對較差但可行。文獻(xiàn)[9]針對多異構(gòu)無人機(jī)協(xié)同任務(wù)規(guī)劃問題構(gòu)建了分層控制算法,在考慮無人機(jī)的異構(gòu)性、資源有限性以及任務(wù)多樣性等復(fù)雜約束條件下,針對任務(wù)中存在的死鎖問題提出了一種基于圖論算法的解鎖方法,取得了較好的效果。

通過對相關(guān)文獻(xiàn)的分析可以看出,目前對耦合約束特性下協(xié)同任務(wù)決策問題的研究已經(jīng)取得了不少成果。但是由于任務(wù)間特定的耦合關(guān)系導(dǎo)致任務(wù)分配過程具有一定的復(fù)雜性,針對特定任務(wù)時(shí)序耦合下協(xié)同分配問題的研究仍然較少。本文通過研究多異構(gòu)無人機(jī)協(xié)同執(zhí)行SEAD任務(wù)過程中存在的時(shí)序耦合約束,提出了一種基于遺傳算子的離散引力搜索算法(GSA-GA)對問題進(jìn)行求解,通過仿真驗(yàn)證了算法的有效性,并采用蒙特卡羅仿真實(shí)驗(yàn)與離散粒子群算法(DPSO)進(jìn)行了對比,仿真結(jié)果表明該算法具備更好的收斂性和更快的收斂速度。

1 具有時(shí)序耦合約束時(shí)的協(xié)同任務(wù)決策問題建模

1.1 問題描述

設(shè)有3種類型(約定為A/B/C型)共M架無人機(jī),無人機(jī)配置信息如表1所示,用集合U={U1,U2,…,UM}表示。任務(wù)場景中有N個(gè)待摧毀目標(biāo),用集合T={T1,T2,…,TN}表示,要求無人機(jī)在任務(wù)航程最短約束下對所有目標(biāo)執(zhí)行打擊和毀傷評估2種任務(wù),要求目標(biāo)必須在打擊任務(wù)完成后的特定時(shí)間約束內(nèi)完成相應(yīng)的毀傷評估任務(wù)。

表1 無人機(jī)配置信息表

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

在無人機(jī)執(zhí)行SEAD任務(wù)時(shí)要求無人機(jī)在任務(wù)區(qū)內(nèi)飛行的時(shí)間越短越好,因此,以最小化所有無人機(jī)中的最大任務(wù)航程為目標(biāo)函數(shù),定義如下:

F=min(maxVi)i=1,2,…M

(1)

式中,Vi表示第i架無人機(jī)的任務(wù)航程。i=1,2,…M為無人機(jī)編號(hào)。

假設(shè)無人機(jī)在任務(wù)執(zhí)行過程中的飛行高度和速度恒定,則第i架無人機(jī)的航程為:

Vi=vi×(eTni-sTni)+D(Tni,BP)

(2)

式中,vi為第i架無人機(jī)的速度;eTni為任務(wù)Tni的完成時(shí)刻;sTni為任務(wù)Tni的開始執(zhí)行時(shí)刻;D(Tni,BP)為任務(wù)Tni與基地BP的歐式距離,計(jì)算公式為:

(3)

xBP,yBP,xTni,yTni分別為基地BP與任務(wù)Tni的位置坐標(biāo)。

(4)

pi表示第i架無人機(jī)的初始位置,Ti(ni-1,ni)表示第i架無人機(jī)從任務(wù)ni-1所在的位置飛向任務(wù)ni所在位置需要的時(shí)間,其計(jì)算公式為:

(5)

1.3 約束條件

時(shí)序耦合約束下協(xié)同任務(wù)決策問題中的約束條件如下:

1) 確保每個(gè)目標(biāo)的打擊和毀傷評估任務(wù)都能被執(zhí)行:

(6)

(7)

Tjh為目標(biāo)Tj的第h類任務(wù)(h=1,2),h=1表示打擊任務(wù),h=2表示毀傷評估任務(wù)。

2) 確保每個(gè)任務(wù)只能被執(zhí)行1次:

(8)

3) 確保每架無人機(jī)至少被分配1個(gè)任務(wù):

(9)

4) 滿足任務(wù)執(zhí)行的時(shí)序耦合約束:

sTjh+xijh*tijh≤eTjh

(10)

eTjh≤sTj(h+1)

(11)

tijh為無人機(jī)Ui執(zhí)行任務(wù)Tjh的任務(wù)執(zhí)行時(shí)間;sTjh表示任務(wù)Tjh的開始執(zhí)行時(shí)刻,eTjh表示任務(wù)Tjh的完成時(shí)刻。

5) 航程約束:

Vi≤Vmaxi

(12)

Vmaxi為無人機(jī)Ui的最大航程。

6) 武器載荷資源約束:

(13)

Ri為無人機(jī)Ui攜帶的武器載荷數(shù)量。

7) 打擊任務(wù)和毀傷評估任務(wù)的時(shí)序約束:

eTj1+Inter-min≤sTj2

(14)

eTj1+Inter-max≥sTj2

(15)

Inter-min和Inter-max分別為打擊任務(wù)和毀傷評估任務(wù)間的最小和最大時(shí)間間隔。

2 基于遺傳算子的混合引力搜索算法

2.1 引力搜索算法

引力搜索算法(gravitation search algorithm,GSA)是由克曼大學(xué)教授Esmat Rashidi等人在2009年提出的元啟發(fā)式優(yōu)化算法,其本質(zhì)是模擬自然界中的萬有引力現(xiàn)象,并將其演化成隨機(jī)搜索最優(yōu)解的過程[12]。GSA算法的原理如下:

1) 個(gè)體表示:

假設(shè)在一個(gè)D維搜索空間中,存在N個(gè)個(gè)體構(gòu)成的群體,第i個(gè)個(gè)體的位置為:

(16)

2) 質(zhì)量計(jì)算:

每個(gè)個(gè)體的慣性質(zhì)量由個(gè)體所在位置所決定的適應(yīng)度值決定,在t時(shí)刻,個(gè)體Xi的質(zhì)量用Mi(t)表示,計(jì)算公式如下:

(17)

式中,fi(t)表示個(gè)體Xi在t時(shí)刻的適應(yīng)度值,b(t)和w(t)分別表示在第t次迭代中所有GSA個(gè)體的最好適應(yīng)度值和最差適應(yīng)度值。

3) 引力計(jì)算:

在t時(shí)刻,個(gè)體i和個(gè)體j之間在第l維的萬有引力計(jì)算公式為:

(18)

式中,Mpi(t)表示在t時(shí)刻個(gè)體i的被動(dòng)引力質(zhì)量,Maj(t)表示在t時(shí)刻個(gè)體j的主動(dòng)引力質(zhì)量,s是防止分母為0的控制常量,Rij(t)為個(gè)體i和個(gè)體j在t時(shí)刻的距離。G(t)表示t時(shí)刻的引力常數(shù),它由開始的某一初始值,隨著時(shí)間的推移,迭代步數(shù)的增加不斷地減小,其計(jì)算公式為:

(19)

式中,T表示最大迭代次數(shù),G0和α為固定常數(shù)。參考文獻(xiàn)[13],通過多次試驗(yàn)數(shù)據(jù)表明G0取100,α取20時(shí)算法具有最好的收斂性能。

Rij(t)表示個(gè)體i和個(gè)體j在t時(shí)刻的距離:

Rij(t)=‖Xi(t),Xj(t)‖

(20)

式中,Xi(t)和Xj(t)分別為個(gè)體i和個(gè)體j在t時(shí)刻的位置。而在t時(shí)刻,個(gè)體i在第l維上受到的合力等于其他所有個(gè)體對其作用力的總和,計(jì)算公式如下:

(21)

4) 位置更新:

引力搜索算法來源于對萬有引力現(xiàn)象的模擬,它遵循經(jīng)典的牛頓第二定律。當(dāng)個(gè)體受到其他個(gè)體的引力作用后會(huì)產(chǎn)生相應(yīng)的加速度,因此,根據(jù)公式(20)計(jì)算得到的引力以及牛頓第二定律,個(gè)體i在第l維獲得的加速度等于其受到合力與其自身慣性質(zhì)量的比值,計(jì)算公式為:

(22)

式中,Mii(t)為個(gè)體i在t時(shí)刻的慣性質(zhì)量,其值等于(17)式中的Mi(t)。

每一次更新過程中,個(gè)體根據(jù)引力產(chǎn)生的加速度更新自身的速度和位置,更新方式如公式(22)所示:

(23)

2.2 個(gè)體編碼模式

針對問題特點(diǎn),我們采用了一個(gè)4N維的數(shù)組表示一個(gè)個(gè)體,分為2部分:任務(wù)分配(task allocation)部分和任務(wù)排序(task sequencing)部分,其中個(gè)體的前2N維為任務(wù)分配部分,余下2N維表示任務(wù)的排序方式。

任務(wù)分配部分表示了N個(gè)目標(biāo)共2N個(gè)任務(wù)的分配結(jié)果,即哪個(gè)目標(biāo)的哪個(gè)任務(wù)分配給哪架UAV。該部分共有2N個(gè)位,由N個(gè)目標(biāo)依次按照目標(biāo)編號(hào)排列,從第一個(gè)位開始,每兩個(gè)位代表一個(gè)目標(biāo),其中第一個(gè)位表示攻擊任務(wù),第二個(gè)位表示毀傷評估任務(wù)。每個(gè)位的取值為當(dāng)前位所代表任務(wù)可供選擇的UAV順序編號(hào),有效保證了各任務(wù)被分配給能夠執(zhí)行該任務(wù)的UAV。

任務(wù)排序部分表示了所有任務(wù)的排序情況,由2N個(gè)位組成,每個(gè)位由目標(biāo)的編號(hào)編碼,每個(gè)目標(biāo)的編號(hào)出現(xiàn)2次,出現(xiàn)的順序表示該目標(biāo)兩個(gè)任務(wù)間的先后順序,目標(biāo)編號(hào)i出現(xiàn)的第j次,表示該目標(biāo)的第j個(gè)任務(wù)。設(shè)定j=1表示攻擊任務(wù),j=2表示毀傷評估任務(wù)。如此編碼,可保證攻擊任務(wù)和毀傷評估任務(wù)的時(shí)序耦合約束。

2.3 個(gè)體解碼模式

個(gè)體信息的解碼是在編碼的基礎(chǔ)上,采用相反的處理模式,將編碼得到的數(shù)據(jù)通過一定的方式轉(zhuǎn)換成所求解問題的可行解決方案,用解碼得到的數(shù)據(jù)計(jì)算出當(dāng)前方案的適應(yīng)度值,即目標(biāo)函數(shù)值,并通過目標(biāo)函數(shù)值的大小評判當(dāng)前解決方案的優(yōu)劣。

算法的具體解碼步驟如下:

Step1 對個(gè)體的任務(wù)分配部分進(jìn)行解碼。

1) 初始化各無人機(jī)的任務(wù)集合為空集,即Tsequencei=?;

2) 從左至右依次讀取第k位上的值i,若k為奇數(shù),則j=(k+1)/2,h=1;若k為偶數(shù),則j=k/2,h=2,將Tjh加入到Tsequencei中。

Step2 對個(gè)體的任務(wù)排序部分進(jìn)行解碼。

1) 從左至右依次讀取第k位上的值j,每個(gè)j代表的是目標(biāo)Tj上的一個(gè)任務(wù),若j是第h次出現(xiàn),則表示Tjh。當(dāng)k=2N得到所有任務(wù)的排列順序Ts;

2) 將Tsequencei根據(jù)Ts重新排列任務(wù)順序,當(dāng)Tjh和Tkl都在Tsequencei中時(shí),將兩者按照Ts中的先后順序重新排列。

Step3 輸出各無人機(jī)的任務(wù)執(zhí)行序列Tsequencei。

2.4 種群初始化與個(gè)體更新策略

以隨機(jī)數(shù)方法對每個(gè)個(gè)體進(jìn)行初始信息賦值。對于個(gè)體中的任務(wù)分配部分通過(23)式更新個(gè)體的位置和速度,更新后的個(gè)體位置需要進(jìn)行可行性修正。首先對每一位的值采用四舍五入的方法進(jìn)行取整,其次,對取整后的每一位進(jìn)行合法性判斷,若該位的取值不在該位表示任務(wù)的可執(zhí)行無人機(jī)集合內(nèi),則采用就近原則,以集合的邊界元素代替。

對于任務(wù)排序部分的更新,本文引入遺傳算法中的交叉和變異操作對該部分進(jìn)行更新。

1) 交叉:交叉操作是利用父代個(gè)體經(jīng)過一定的操作組合后產(chǎn)生新個(gè)體,從而達(dá)到在不破壞有效模式的前提下對解空間進(jìn)行高效搜索的目的。采用改進(jìn)的POX交叉方法,對個(gè)體的任務(wù)排序部分進(jìn)行交叉操作,進(jìn)而達(dá)到更新的目的。改進(jìn)后的POX交叉操作每一次只產(chǎn)生一個(gè)新個(gè)體,算法步驟如下:Step1:從目標(biāo)集{T1,T2,…Tn}隨機(jī)抽取一個(gè)目標(biāo)子集Tset;

Step2 選擇需要進(jìn)行交叉操作的個(gè)體X1和X2,若X1的適應(yīng)度函數(shù)優(yōu)于X2,則將X1中包含在目標(biāo)子集Tset中的目標(biāo)復(fù)制到新的個(gè)體C中,保持位置和順序不變;

Setp3 將X2中不包含在Tset中的目標(biāo)復(fù)制到C中,保持順序不變;

Step4 若新個(gè)體C的適應(yīng)度函數(shù)優(yōu)于X2,則保存新個(gè)體,并替代原來的個(gè)體X2。如圖1所示,含有4個(gè)目標(biāo),隨機(jī)抽取的目標(biāo)集Tset={2,3},X1要優(yōu)于X2,將X1中包含目標(biāo)2,3的位復(fù)制到新個(gè)體C中,然后將X2中去掉目標(biāo)2,3后,剩下的部分按照原來的次序依次復(fù)制到C的除去2,3所在位的其他位,從而產(chǎn)生新個(gè)體C。

圖1 POX交叉操作

2) 變異:變異操作是通過隨機(jī)改變個(gè)體的某些位,從而產(chǎn)生較小擾動(dòng)生成新個(gè)體,增加種群多樣性,在一定程度上控制引力搜索算法的局部搜索能力。我們采用基于鄰域搜索變異操作,在個(gè)體的任務(wù)分配部分不變的情況下,采用基于鄰域搜索的變異方法,能夠更好地通過局部范圍內(nèi)的搜索找到適合任務(wù)分配部分的任務(wù)排序,從而改善子代性能。其算法操作步驟如下:

Step1 在個(gè)體的任務(wù)排序部分隨機(jī)選擇r個(gè)位,并生成其排序的所有鄰域;

Step2 計(jì)算所有鄰域的適應(yīng)度函數(shù)值,選出最佳個(gè)體作為子代,并代替原來的個(gè)體。

引入遺傳算子改進(jìn)后的混合引力遺傳搜索算法(GSA-GA)的處理流程如圖2所示。

圖2 GSA-GA算法流程圖

3 仿真算例與分析

設(shè)定任務(wù)場景中有5架UAV和9個(gè)待摧毀目標(biāo),無人機(jī)相關(guān)信息如表2所示。

表2 無人機(jī)相關(guān)信息

目標(biāo)及返回基地信息如表3所示。假設(shè)無人機(jī)執(zhí)行完成打擊任務(wù)的時(shí)間為0.05 h,執(zhí)行完成毀傷評估任務(wù)的時(shí)間為0.1 h,且毀傷評估任務(wù)和打擊任務(wù)的最小時(shí)間間隔為0.1 h,最大時(shí)間間隔不能超過0.5 h。

表3 目標(biāo)及基地位置信息

基于以上作戰(zhàn)想定,采用改進(jìn)的引力搜索算法進(jìn)行仿真,種群規(guī)模為30,最大迭代次數(shù)為100次。仿真得到最優(yōu)任務(wù)分配結(jié)果如表4所示,各子任務(wù)被執(zhí)行時(shí)刻如表5所示,圖3為最優(yōu)任務(wù)分配結(jié)果下的無人機(jī)執(zhí)行任務(wù)過程示意圖。

表4 最優(yōu)分配結(jié)果

表5 任務(wù)執(zhí)行時(shí)刻表

由表4可以看出,分配結(jié)果中各UAV的資源約束和航程約束是完全滿足的,由表5可以看出,各目標(biāo)的打擊與評估任務(wù)是滿足任務(wù)間的時(shí)間耦合約束的。

圖3 無人機(jī)執(zhí)行任務(wù)過程示意圖

為了驗(yàn)證GSA-GA算法的性能,針對上述問題,采用離散粒子群算法(DPSO)進(jìn)行仿真對比分析,DPSO參數(shù)參照文獻(xiàn)[11]設(shè)置為:粒子種群規(guī)模為30,最大迭代次數(shù)為100,ω=0.5,c1=0.3,c2=0.2,圖4所示為2種算法求解下的收斂曲線。由圖中可以看出,相對于DPSO算法,改進(jìn)的引力搜索算法能夠較快地收斂到最優(yōu)解。但是由于2種算法均屬于啟發(fā)式優(yōu)化算法,求得的結(jié)果往往不一定是最優(yōu)解,也可能是次優(yōu)解,因而單一的仿真結(jié)果并不能準(zhǔn)確地比較出2種算法在求解任務(wù)分配問題上的優(yōu)劣,針對以上問題分別采用2種算法進(jìn)行200次蒙特卡羅法仿真實(shí)驗(yàn),2種算法的收斂過程如圖4所示,統(tǒng)計(jì)結(jié)果如表6所示。

圖4 GSA-GA和DPSO的收斂曲線

表6 GSA-GA與DPSO算法對比分析

如表6所示,經(jīng)過200次隨機(jī)求解,改進(jìn)的GSA-GA算法得到的最佳適應(yīng)度為2 577.8,最差適應(yīng)度為2 720.5,平均適應(yīng)度為2 585.9 km,平均收斂代數(shù)為20代,平均消耗時(shí)間為1.073 s,相比于DPSO算法,在最佳適應(yīng)度、平均收斂代數(shù)及平均消耗時(shí)間上均有更好的表現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)表明,改進(jìn)的GSA-GA算法能夠更高效地對時(shí)序耦合約束下多UAV協(xié)同任務(wù)決策問題進(jìn)行求解。

4 結(jié) 論

多無人機(jī)協(xié)同任務(wù)決策問題是一個(gè)十分復(fù)雜的典型NP-Hard問題,本文以多無人機(jī)協(xié)同執(zhí)行SEAD任務(wù)為背景,重點(diǎn)關(guān)注任務(wù)間的時(shí)序耦合關(guān)系,對時(shí)序耦合約束下的多無人機(jī)任務(wù)分配問題進(jìn)行了數(shù)學(xué)建模,提出了一種基于遺傳算子的混合引力遺傳搜索算法 (GSA-GA)并應(yīng)用于任務(wù)分配問題的求解,通過算例仿真實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性和合理性,并采用蒙特卡羅仿真方法對改進(jìn)算法與離散粒子群算法進(jìn)行了對比分析,結(jié)果表明GSA-GA 算法能夠更快地收斂,尋優(yōu)結(jié)果更優(yōu)。從而為無人機(jī)執(zhí)行具有時(shí)序耦合約束任務(wù)時(shí)的協(xié)同任務(wù)分配問題提供了科學(xué)的決策依據(jù)。