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

趙慧武，王 鵬，郭江宇

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

0 引言

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

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

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

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

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

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

Θi=

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

(6)

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

minLi=d(Θi)

(7)

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

(8)

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

(9)

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

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

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

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

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

在多維目標搜索空間中，假設(shè)粒子Pk在t時刻的位置向量和速度向量分別是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]之間的隨機自然數(shù)；c1和c2通常情況下都取值為2；pb(·)是粒子Pk的個體極值；gb(·)是種群當前找到的全局極值；慣性權(quán)重w取(0.5, 0.9)之間的隨機數(shù)。

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

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

(12)

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

(13)

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

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

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

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

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

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

3 算法仿真

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

表1 目標情況

表2 飛行器情況

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

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

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

表3 飛行器代價、收益指標

4 結(jié)論

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

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