多飛行器協(xié)同任務(wù)分配粒子群算法研究

趙慧武，王 鵬，郭江宇

(1 北方自動(dòng)控制技術(shù)研究所，太原 030006；2 32381部隊(duì)，北京 100071)

0 引言

現(xiàn)如今，飛行器在目標(biāo)搜索、對(duì)地攻擊、空中搜救、交通巡查以及快遞運(yùn)輸?shù)溶娪煤兔裼妙I(lǐng)域發(fā)揮著重要作用[1]。單架飛行器往往無(wú)法高效率的完成復(fù)雜多變的任務(wù)。因此，需要使用多個(gè)同構(gòu)或異構(gòu)飛行器協(xié)同完成任務(wù)。如何使得多飛行器控制系統(tǒng)更好的適應(yīng)復(fù)雜的任務(wù)環(huán)境和靈活多變的任務(wù)要求，是近年來(lái)國(guó)內(nèi)外科研人員研究重點(diǎn)[2]，特別是多飛行器協(xié)同任務(wù)分配問(wèn)題，已成為飛行器自主導(dǎo)航領(lǐng)域亟需解決的關(guān)鍵問(wèn)題[3]。

多飛行器協(xié)同任務(wù)分配問(wèn)題可定義為：給定飛行器種類(lèi)及數(shù)量，根據(jù)一定的物理環(huán)境信息和任務(wù)要求，將一個(gè)或多個(gè)任務(wù)分配給一個(gè)飛行器，所有飛行器完成所分配的任務(wù)的同時(shí)，使得整個(gè)飛行器編隊(duì)的整體效能達(dá)到最優(yōu)[4]。在給飛行器分配任務(wù)的過(guò)程中，還需考慮飛行器的載彈有限性、多任務(wù)時(shí)序約束以及實(shí)時(shí)規(guī)劃有效性等要求。從理論上講，多飛行器協(xié)同任務(wù)分配問(wèn)題屬于NP-hard的排列組合問(wèn)題，難以完全避免組合爆炸，對(duì)于規(guī)模較大的飛行器編隊(duì)很難得到最佳任務(wù)分配方案[5]。目前，很多學(xué)者提出了多種計(jì)算可行的協(xié)同任務(wù)分配算法，比如基于合同網(wǎng)“招標(biāo)-投標(biāo)-中標(biāo)”的市場(chǎng)拍賣(mài)機(jī)制，提出了多Agent分布式任務(wù)分配算法[6-7]；智能優(yōu)化算法因?yàn)榫哂徐`活、易實(shí)現(xiàn)和計(jì)算復(fù)雜度低的特點(diǎn)，被廣泛的用于多飛行器協(xié)同任務(wù)分配的研究，常用的算法包括遺傳算法[8]、蟻群算法[9]和粒子群算法[10-12]等。

文中主要研究了多飛行器協(xié)同攻擊多個(gè)地面目標(biāo)的任務(wù)分配問(wèn)題，提出了任務(wù)分配粒子群算法。首先，建立飛行器任務(wù)分配時(shí)必須滿足的攻擊上限約束以及航程約束，構(gòu)造任務(wù)分配需付出的代價(jià)函數(shù)和收益函數(shù)，進(jìn)而建立多飛行器協(xié)同任務(wù)分配問(wèn)題的數(shù)學(xué)模型。然后，為每個(gè)粒子定義了相應(yīng)的任務(wù)分配向量，建立粒子的連續(xù)化的位置屬性與任務(wù)分配解的“一一對(duì)應(yīng)”的關(guān)系，即實(shí)現(xiàn)了粒子連續(xù)性解的離散化。最后，建立多飛行器協(xié)同任務(wù)分配的粒子群算法，并進(jìn)行了數(shù)字仿真實(shí)驗(yàn)，驗(yàn)證了所提算法的有效性。

1 數(shù)學(xué)模型

以二維戰(zhàn)場(chǎng)環(huán)境多架飛行器多對(duì)地面目標(biāo)開(kāi)展協(xié)同攻擊為研究背景。假設(shè)任務(wù)背景中不存在禁飛區(qū)、地形障礙等威脅，任務(wù)環(huán)境已知，同時(shí)考慮目標(biāo)對(duì)飛行器的防空威脅。

假定系統(tǒng)包含Nu架飛行器U={U1,U2,…,UNu}和Nt個(gè)目標(biāo)T={T1,T2,…,TNt}，Nu

Θi=

(1)

為了更好的描述上述過(guò)程，利用xij表示第i架飛行器Ui執(zhí)行任務(wù)Θi時(shí)是否攻擊了第j個(gè)目標(biāo)。

(2)

本質(zhì)上，飛行器的協(xié)同任務(wù)分配是個(gè)排列組合問(wèn)題。通過(guò)為飛行器合理分配攻擊目標(biāo)，保證飛行器編隊(duì)整體作戰(zhàn)性能最好。在飛行器任務(wù)分配中，通常需要考慮以下的約束、代價(jià)與收益。

約束條件：飛行器的載彈能力有限，單次執(zhí)行任務(wù)時(shí)只能攻擊有限個(gè)數(shù)目標(biāo)，令飛行器Ui的能力上限是Qi,max。此約束表示為：

(3)

受機(jī)載燃油限制，飛行器只能在有限距離內(nèi)連續(xù)飛行，因此飛行器Ui的飛行路程不能超過(guò)最大航程Li,max。此約束表示為：

d(Θi)≤Li,max,?i∈{1,2,…,Nu}

(4)

每個(gè)目標(biāo)只能分配給一個(gè)飛行器，不能重復(fù)分配。此約束表示為：

(5)

(6)

航程代價(jià)：飛行器需要飛行一定航程完成攻擊任務(wù)。航程越長(zhǎng)，消耗機(jī)載燃油越多。通過(guò)將航程代價(jià)指標(biāo)最小化，盡可能的減少資源消耗。飛行器Ui執(zhí)行Θi的航程代價(jià)函數(shù)為：

minLi=d(Θi)

(7)

攻擊收益：飛行器攻擊目標(biāo)將會(huì)獲得一定的收益，其大小由目標(biāo)本身價(jià)值和飛行器對(duì)目標(biāo)的殺傷概率決定。通過(guò)將收益指標(biāo)最大化，能盡可能的提高作戰(zhàn)性能。假設(shè)pij,T是飛行器Ui對(duì)目標(biāo)Tj的殺傷概率，Vj,T是目標(biāo)Tj的價(jià)值。飛行器Ui執(zhí)行Θi任務(wù)后收益函數(shù)為：

(8)

通過(guò)上述分析，可得飛行器任務(wù)分配問(wèn)題的數(shù)學(xué)模型為：

(9)

s.t. 式(3)～式(5)
xij∈{0,1},?i∈{1,2,…,Nu},?j∈{1,2,…,Nt}

其中，s1，s2和s3分別是威脅代價(jià)、航程代價(jià)以及攻擊收益對(duì)應(yīng)的權(quán)重。

2 多飛行器粒子群協(xié)同任務(wù)分配算法

粒子群算法(PSO)是20世紀(jì)90年代出現(xiàn)的智能進(jìn)化算法。一定數(shù)目的粒子組成種群，每個(gè)粒子代表問(wèn)題的一個(gè)潛在解，利用適應(yīng)度函數(shù)評(píng)估粒子的優(yōu)劣，追隨當(dāng)前粒子種群中的最優(yōu)解和粒子歷史最優(yōu)解，持續(xù)迭代更新粒子種群以追尋到全局最優(yōu)解。

算法初始化時(shí)隨機(jī)選擇一群粒子。每個(gè)粒子有兩個(gè)連續(xù)性特征屬性：位置和速度。在迭代過(guò)程中，粒子需要追蹤兩個(gè)極值：第一個(gè)是粒子自身歷史的最優(yōu)解，稱(chēng)為個(gè)體極值；另一個(gè)是整個(gè)種群當(dāng)前的最優(yōu)解，稱(chēng)為全局極值。所有粒子基于這兩個(gè)極值更新位置和速度，從而盡快向最優(yōu)解靠攏。

在多維目標(biāo)搜索空間中，假設(shè)粒子Pk在t時(shí)刻的位置向量和速度向量分別是Yk(t)和Zk(t)，它們按照式(10)～式(11)演化：

Zk(t+1)=wZk(t)+c1Rand1()(pb(t)-Yk(t))+
c2Rand2()(gb(t)-Yk(t))

(10)

Yk(t+1)=Yk(t)+Zk(t)

(11)

其中：Rand1()和Rand2()是分布在[0, 1]之間的隨機(jī)自然數(shù)；c1和c2通常情況下都取值為2；pb(·)是粒子Pk的個(gè)體極值；gb(·)是種群當(dāng)前找到的全局極值；慣性權(quán)重w取(0.5, 0.9)之間的隨機(jī)數(shù)。

設(shè)粒子的位置和速度都是Nt維向量，即它們的維度等于目標(biāo)個(gè)數(shù)，這樣任務(wù)分配問(wèn)題的解空間是Nt維的。我們將粒子Pk的位置分量Ykj限制在[-Nu,Nu]之間。即當(dāng)Ykj≥Nu時(shí)，令Ykj=Nu;當(dāng)Ykj<-Nu時(shí)，令Ykj=-Nu。

令函數(shù)K(z)表示不大于z的最大整數(shù)，比如K(2.3)=2。為了從粒子Pk的位置向量Yk提煉出相應(yīng)的任務(wù)分配解，定義個(gè)一個(gè)Nt維分配向量Ak=(Ak1,Ak2,…,AkNt)，其中分量Akj由式(12)計(jì)算:

(12)

分配向量Ak對(duì)應(yīng)的任務(wù)分配方案表示：第Akj架飛行器被分配給了第j個(gè)目標(biāo)。相應(yīng)的xij可由式(13)計(jì)算:

(13)

數(shù)字i在Ak中出現(xiàn)時(shí)的下標(biāo)的順序集合組成了第i架飛行器任務(wù)的Θi。所有飛行器的任務(wù){(diào)Θi，i∈{1,2,…,Nu}}組成了粒子Pk對(duì)應(yīng)的任務(wù)分配解。值得注意的是，Ak的每個(gè)分量只對(duì)應(yīng)一個(gè)飛行器編號(hào)，因此給每個(gè)目標(biāo)只分配一個(gè)無(wú)人機(jī)，滿足式(5)。但是基于Ak得到的任務(wù)分配解可能不滿足式(3)與式(4)，因此并不一定是可行的。在更新粒子時(shí)，檢驗(yàn)相應(yīng)的任務(wù)分配解是否可行，如果不可行，則舍棄重新更新，直至得到滿足式(3)和式(4)的解。

綜上所述，多飛行器協(xié)同任務(wù)分配問(wèn)題的粒子群算法為：

步驟1: 設(shè)定粒子種群規(guī)模大小、最大迭代次數(shù)。初始化粒子位置和速度，為每個(gè)粒子建立分配向量，使得對(duì)應(yīng)的解滿足式(3)～式(5)，并計(jì)算個(gè)體極值和全局極值。

步驟2: 計(jì)算每個(gè)粒子適應(yīng)度指標(biāo)，如果優(yōu)于該粒子當(dāng)前個(gè)體極值，則更新該個(gè)體極值；如果某個(gè)體極值好于當(dāng)前的全局極值，則更新全局極值。

步驟3: 按照式(10)和式(11)更新每個(gè)粒子Pk的位置向量和速度向量，計(jì)算相應(yīng)的任務(wù)分配向量Ak以及任務(wù)分配解Θi，i∈{1,2,…,Nu}。如果所得解是可行的，則接受Pk的更新；否則，不接受，重新更新粒子Pk直至得到可行任務(wù)分配方案。

步驟4: 如果迭代次數(shù)達(dá)到最大迭代次數(shù)，則停止迭代并輸出全局極值為當(dāng)前最優(yōu)解，否則，轉(zhuǎn)入步驟2。

3 算法仿真

已知任務(wù)區(qū)域內(nèi)有14個(gè)目標(biāo)T1～T14，有3個(gè)飛行器U1～U3。每個(gè)目標(biāo)的位置、價(jià)值、威脅等屬性如表1所示。飛行器的位置、價(jià)值等屬性如表2所示。每架飛行器最大航程為500 km。假設(shè)一個(gè)目標(biāo)對(duì)于不同的飛行器具有相同的威脅概率，一個(gè)飛行器對(duì)不同的目標(biāo)具有相同的殺傷概率。

表1 目標(biāo)情況

表2 飛行器情況

假設(shè)粒子群算法有20個(gè)粒子，迭代2 000次，威脅代價(jià)、航程代價(jià)以及攻擊收益對(duì)應(yīng)的權(quán)重s1=2,s2=1,s3=3。

圖1給出算法迭代過(guò)程中，每一代更新中全局最優(yōu)粒子的適應(yīng)度函數(shù)指標(biāo)。由圖1可以看出，隨著迭代次數(shù)增加，適應(yīng)度函數(shù)得到了優(yōu)化，最后收斂至穩(wěn)定值。迭代過(guò)程完成后，可得一個(gè)方案：Θ1=(T9,T10,T11,T12,T13,T14)，Θ2=(T1,T2,T3,T4,T7,T8)，Θ3=(T5,T6)，其中的各個(gè)飛行器的代價(jià)與收益情況如表3所示。

圖1 任務(wù)分配適應(yīng)度指標(biāo)變化圖

表3 飛行器代價(jià)、收益指標(biāo)

4 結(jié)論

利用粒子群算法求解多飛行器協(xié)同任務(wù)分配問(wèn)題。首先，建立考慮飛行器載彈能力以及航程約束的數(shù)學(xué)模型，通過(guò)分析多飛行器可能遭受的威脅、付出的航程代價(jià)以及打擊目標(biāo)后獲得的收益，構(gòu)造出粒子群算法的適應(yīng)度函數(shù)。然后，基于每個(gè)粒子的位置向量建立了對(duì)應(yīng)的任務(wù)分配向量，從中提取出每個(gè)粒子對(duì)應(yīng)的任務(wù)分配解，實(shí)現(xiàn)了粒子群算法連續(xù)性解的離散化。最后，利用粒子群算法進(jìn)化原理，建立了一種

多飛行器協(xié)同任務(wù)分配方法，該方法的可行性可由仿真實(shí)驗(yàn)證明。提出的模型法和分配算法也可應(yīng)用到其他多無(wú)人集群協(xié)同任務(wù)分配中。