多飛行器協同任務分配粒子群算法研究

趙慧武，王 鵬，郭江宇

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

0 引言

現如今，飛行器在目標搜索、對地攻擊、空中搜救、交通巡查以及快遞運輸等軍用和民用領域發揮著重要作用[1]。單架飛行器往往無法高效率的完成復雜多變的任務。因此，需要使用多個同構或異構飛行器協同完成任務。如何使得多飛行器控制系統更好的適應復雜的任務環境和靈活多變的任務要求，是近年來國內外科研人員研究重點[2]，特別是多飛行器協同任務分配問題，已成為飛行器自主導航領域亟需解決的關鍵問題[3]。

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

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

1 數學模型

以二維戰場環境多架飛行器多對地面目標開展協同攻擊為研究背景。假設任務背景中不存在禁飛區、地形障礙等威脅，任務環境已知，同時考慮目標對飛行器的防空威脅。

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

Θi=

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

(6)

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

minLi=d(Θi)

(7)

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

(8)

通過上述分析，可得飛行器任務分配問題的數學模型為：

(9)

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

其中，s1，s2和s3分別是威脅代價、航程代價以及攻擊收益對應的權重。

2 多飛行器粒子群協同任務分配算法

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

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

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

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

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

(12)

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

(13)

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

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

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

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

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

步驟4: 如果迭代次數達到最大迭代次數，則停止迭代并輸出全局極值為當前最優解，否則，轉入步驟2。

3 算法仿真

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

表1 目標情況

表2 飛行器情況

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

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

圖1 任務分配適應度指標變化圖

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

4 結論

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

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