未知環境下異構多無人機協同搜索打擊中的聯盟組建

劉重，高曉光，符小衛，牟之英（.西北工業大學電子信息學院，陜西西安709；.航空電子綜合技術重點實驗室，上海0033）

未知環境下異構多無人機協同搜索打擊中的聯盟組建

劉重1，高曉光1，符小衛1，牟之英2
（1.西北工業大學電子信息學院，陜西西安710129；2.航空電子綜合技術重點實驗室，上海200233）

為了提高多架異構無人機在未知環境下協同執行搜索打擊任務時的效能，提出了一種未知環境下的異構多無人機協同搜索打擊中的聯盟組建方法，研究了實時性較高且適應于未知環境下的任務分配機制。以最小化目標打擊時間和最小化聯盟規模為優化指標，以滿足同時打擊和資源需求為約束條件，建立了聯盟組建模型；為了提高聯盟組建的實時性，提出了一種分階次優聯盟快速組建算法（MSOCFA）。算法復雜度分析說明了該算法是一個多項式時間算法，并且通過與粒子群優化算法進行仿真對比，驗證了該算法具有較低的計算復雜度，滿足實時性要求。為了使得多架無人機能自主協同完成搜索打擊任務，設計了基于有限狀態機（FSM）的多無人機分布式自主協同控制策略。仿真驗證了未知環境下的異構多無人機協同搜索打擊中的聯盟組建方法的合理性和可行性。使用蒙特卡洛法驗證了無人機數量和目標數量對聯盟組建的影響，即無人機數量越多，目標數量越少，其平均任務完成時間越短。

控制科學與技術；多無人機；協同搜索打擊；聯盟組建；有限狀態機；蒙特卡洛方法

0　引言

無人機具有零傷亡、高機動性、隱身性能好、費用低等優勢，被廣泛應用于作戰環境中的搜索打擊任務。然而，面對日趨復雜的現代戰場環境，由于單架無人機的性能受到載荷等限制，執行對多目標的作戰任務必須要多架異構無人機協同才能完成。多架異構無人機能夠有效執行對多目標搜索打擊任務的前提是多無人機之間能夠進行有效的任務分配[1]。

針對任務分配問題，許多學者進行了研究并取得了一系列成果，提出了諸如動態網絡流優化（DNFO）、混合整數線性規劃（MILP）、多維多選擇背包問題（MMKP）及多無人機協同多任務分配問題（CMTAP）等模型來解決任務分配問題。文獻[2-3]在研究廣域搜索攻擊問題時，以無人機為供應商，任務為網絡上的物流，任務分配的結果作為需求，無人機執行任務的代價或收益作為任務在網絡中流動的代價，建立DNFO模型，通過對網絡流量總代價最小化實現多無人機任務分配。文獻[4-6]針對多架同構無人機執行空對地攻擊任務問題，建立了相應的MILP模型，在該模型中假設無人機在執行了攻擊任務后會損傷而不能繼續執行其他任務，因此要求無人機的數目多于目標的數目。在此基礎上，文獻[7]以多架無人機執行壓制敵防空系統任務為背景，建立了相應的MILP模型。文獻[8]將多無人機任務分配描述為多維多選擇背包問題。文獻[9]以最小化所有無人機的飛行距離或者完成任務的時間為優化目標，建立了多無人機協同多任務分配模型，利用遺傳算法對該模型進行了求解。此外，還有應用合同網[10]、基于多智能體滿意決策論[11]等方法求解多無人機任務分配。總的來說，上述方法存在著這樣的問題：1）現有無人機任務分配模型和方法中通常假設無人機是同構的并且不考慮資源的消耗，與實際作戰不符；2）任務分配問題的求解方法實時性不高；3）需要預先知道目標的數量、位置等信息。然而多架無人機協同執行搜索打擊任務時，由于環境的未知不確定性，目標的數量、位置等信息對無人機來說事先是未知的。因而上述問題對傳統的多無人機任務分配方法提出了挑戰。

多無人機系統可看作是多Agent系統（MAS）. 在MAS中，當單個Agent不能或不能有效完成特定的任務時，Agent就必須形成聯盟來完成。聯盟是為完成某個共同任務而結合在一起的多個個體。通過組建聯盟實現任務分配，在多機器人（MRS）領域也得到了深入的研究，因此可以借鑒MAS和MRS中聯盟組建的思路來解決多架異構無人機協同執行搜索打擊任務時的任務分配問題。文獻[12]以對策論中的多人合作博弈為基礎，采用分布式問題求解（DPS）方法從無聯系的多Agent構建出有聯系的多Agent聯盟，以解決多Agent任務分配問題。在文獻[12]的基礎上，文獻[13-14]針對競爭環境下MRS聯盟組建問題，提出一種基于市場拍賣機制的聯盟組建算法。文獻[15]提出了一種改進的核心法來組建聯盟，實現了多Agent多任務分配和資源分配。然而MAS中資源可轉移且無損耗的特點導致MAS中的聯盟組建方法不能直接應用于多無人機聯盟組建。MRS中雖然資源不可轉移且是可損耗的，但是MRS中的聯盟組建算法實時性不高，不適用于因飛行速度較快而對算法實時性要求很高的多無人機系統。

因此，設計實時性較高的且適用于未知環境下的異構多無人機聯盟組建算法，以提高多無人機協同執行搜索打擊任務時的效能，是一個值得研究的技術難點。本文針對這一問題進行研究。

1　問題描述

如圖1所示，使用N架異構無人機對一片未知區域的M個靜止目標執行搜索打擊任務。這些無人機是異構的，體現在它們攜帶不同種類和數量的任務資源。每架無人機有唯一的編號Ai（i=1，2，…，N），其中無人機Ai攜帶有n種不同類型的任務資源（這些任務資源隨著任務的執行而消耗），用當前資源向量表示：

圖1　多架異構無人機執行搜索打擊任務示意圖Fig.1　Schematic diagram of UAVs perfoming a search and attack mission

當多架無人機開始執行搜索打擊任務時，目標的信息對于無人機來說是未知的，那么無人機需要以一定的搜索方式對任務區域展開搜索，在一定的探測距離內發現目標。假設無人機Ai發現目標Tj時，可以獲知目標Tj的位置信息和資源信息。這里的資源信息指的是打擊目標Tj所需的資源類型和數量，用資源需求向量表示：

每架無人機均可以與其他各架無人機進行通信。如圖1所示，當無人機Ai發現了目標Tj后，Ai成為聯盟長機（CL）并將目標Tj的位置信息和資源信息廣播給其他各架無人機，組建聯盟完成對目標Tj的打擊，這一過程稱之為聯盟組建提議。

對其他各架無人機而言，當接收到聯盟組建提議消息后，對照自身所擁有的資源類型和數量，如果自身存在所需資源中的任何一種資源的話，就對Ai作出回應，將自身的最早到達時間（ETA）和當前資源向量反饋給無人機Ai.這一過程稱之為聯盟組建投標。其中Ak的最早到達時間ETA可由從其當前位置到目標位置的Dubins路徑來確定，而作出回應的無人機Ak稱之為潛在聯盟成員（PCM）.

聯盟長機Ai接收到其他各架無人機的反饋信息后，其任務就是組建聯盟。這一過程稱之為聯盟組建，構成聯盟的無人機稱之為聯盟成員（CM）.所組建的聯盟需要滿足以下約束和條件：1）為了縮短搜索打擊任務的完成時間，要求在最短的時間內實現對目標的打擊；2）要求聯盟的規模最小，這是因為搜索打擊任務的完成時間是由搜索時間和打擊時間這兩部分構成，若每次組建聯盟時都使其規模最小，就可盡量使得更多的無人機參與對未知區域的搜索，在更短的時間內發現目標，從而縮短整個搜索打擊任務的完成時間；3）為了對目標進行全方位打擊，要求各個聯盟成員同時對目標發起攻擊；4）為了確保目標能被擊毀，要求聯盟中各聯盟成員所擁有的資源總和滿足打擊需求。

無人機Ai發現了目標Tj時所組建的聯盟記為，該聯盟的資源向量（各聯盟成員的當前資源向量之和）為表示所有的潛在聯盟成員PCM和聯盟長機CL所組成的集合，λk表示無人機Ak∈Λ的最早到達時間ETA，那么聯盟組建問題可以描述為

2　聯盟組建方法

2.1分階次優聯盟快速組建算法

由（3）式可以看出聯盟組建問題是一個組合優化問題，隨著無人機數量和目標數量的增加，該優化問題的求解將變得非常困難，因此，本文提出了一種分階次優聯盟快速組建算法（MSOCFA）.

如圖2所示，當無人機Ai發現了目標Tj時，Ai首先確定出打擊目標Tj的資源需求向量如果無人機Ai的當前資源向量中并且無人機Ai不隸屬于任何一個聯盟，那么無人機Ai不需要組建聯盟直接打擊目標Tj；否則如果無人機Ai不能擁有打擊目標Tj所需的全部資源，則成為聯盟長機并將目標Tj的位置信息和資源信息廣播給其他各架無人機。其他各架無人機Ak接收到聯盟組建提議消息后，若自身處于“空閑”（即當前正在執行搜索任務）時，則對照自身所擁有的資源類型和數量，如果自身存在所需資源中的任何一種資源的話，就對聯盟長機Ai作出回應，將自身的最早到達時間λk和當前資源向量反饋給聯盟長機Ai.聯盟長機Ai綜合所有的反饋信息來組建聯盟。如果聯盟組建成功，就將聯盟組建結果和整個聯盟的最早到達時間發送給其他各架無人機；否則將聯盟組建失敗信息廣播出去。最后，所組建聯盟中的各個聯盟成員需要根據整個聯盟的最早到達時間重新規劃各自的攻擊路徑（Dubins路徑）以實現對目標的同時打擊，而沒有成為聯盟成員的無人機則繼續執行搜索任務。

圖2　聯盟快速組建過程示意圖Fig.2　Flow chart of coalition formation process

在以上聯盟快速組建過程中，聯盟長機Ai采用MSOCFA決策出聯盟MSOCFA主要分兩個階段：第1階段，確定能夠滿足最短到達時間條件的所有無人機集合；第2階段，裁剪第1階段得到的集合以獲得最小規模的聯盟。MSOCFA兩個階段的偽代碼分別如圖3和圖4所示。

圖3　MSOCFA第1階段偽代碼Fig.3　Pseudo code of first stage of MSOCFA

圖4　MSOCFA第2階段偽代碼Fig.4　Pseudo code of second stage of MSOCFA

在算法的第2階段中，通過裁剪第1階段得到的集合以獲得最小規模的聯盟。具體過程是，依次考察Cij中的每一架無人機，試探性地將無人機Aq從聯盟中移除，如果移除無人機Aq后聯盟的資源向量仍然滿足打擊目標所需的資源約束，那么就將無人機Aq從聯盟中移除；否則，保留無人機Aq.循環結束后，就能得到最小規模的聯盟Λ.

定理1 MSOCFA的第1階段能夠確定滿足最短到達時間條件的無人機集合。

證明：設所有的潛在聯盟成員和聯盟長機構成集合Λ=｛A1，A2，…，AN′｝，相應地Λ中各架無人機的最早到達時間構成集合ETAs=｛λ1，λ2，…，λN′｝，并且假設在MSOCFA的第1階段中，將ETAs中的元素按升序排列，假設排序后的結果為 Λu=｛λi1，λi2，…，λiN′｝，Λa=｛Ai1，Ai2，…，AiN′｝，并且 Λu中的元素滿足性質 λik≤λik+1，?k∈｛1，…，N′-1｝.對于任意的整數r∈｛1，…，N′｝，令λir｝，那么的最短到達時間為λir.MSOCFA第1階段的實質是找到最小的整數v∈｛1，…，N′｝，使得是滿足打擊資源需求的無人機集合。既然中的元素是升序排列的，那么從中剔除任意一個非Aiv的元素，均不會改變無人機集合的最短到達時間λir，況且如果剔除Aiv后，無人機集合將不滿足打擊資源需求，因此是滿足最短到達時間條件的無人機集合，定理1得證。

2.2沖突消解

2.2.1多架無人機同時偵察到同一目標

當多架無人機同時偵察到同一目標時，這些無人機均會發起聯盟組建請求，導致資源競爭沖突，從而形成死鎖。本文采用令牌機制來避免死鎖，具體做法是：為每架無人機分配一個令牌數（i=1，2，…，N）來表征每架無人機的優先級，令牌數越大，無人機的優先級越高，那么優先成為聯盟長機。

2.2.2一架無人機同時偵察到多個目標

當一架無人機同時偵察到多個目標時，該無人機無法為所偵察到的多個目標同時組建聯盟，因此也產生沖突。此時需要為每個目標分配一個令牌數來表征打擊每個目標的優先級（假設無人機偵察到目標時即可獲知該目標的令牌數），令牌數越大，目標優先被打擊。

2.2.3多架無人機同時偵察到多個目標

當多架無人機同時偵察到多個目標時，同樣會因為同時發起聯盟組建請求，而導致資源競爭沖突，形成死鎖，此時需要綜合應用無人機令牌數和目標的令牌數來消解沖突。例如，如果有4架無人機A1、A2、A3、A4搜索打擊2個目標T1、T2，無人機令牌數的大小順序為若A1偵察到T2的同時A4偵察到T1，A1和A4均成為聯盟長機，這時候由于A1的優先級高于A4，那么A1優先組建聯盟，此時A1作為長機，A2和 A3作為潛在聯盟成員（A4已成為長機，故不作為潛在聯盟成員），組建出聯盟當聯盟組建完畢后，A4才能組建聯盟，此時潛在聯盟成員集合為｛A2｝，組建出聯盟

值得注意的是還存在這樣一種情況，若A1同時偵察到T1、T2，與此同時，A4也同時偵察到T1、T2.由于A1的優先級高于A4，那么A1優先組建聯盟，此時A1作為長機，它需要在所發現的目標T1、T2中挑選出一個目標作為打擊對象，由于T1的令牌數TNT1大于T2的令牌數，那么T1優先被打擊，即首先由A1作為長機組建聯盟完成對T1的打擊，然后才讓A4作為長機組建聯盟完成對T2的打擊。

2.3算法復雜度分析

為了說明MSOCFA具有較高的實時性，需要對其復雜度進行分析，提出如下定理2.

定理2 MSOCFA算法復雜度為O（N（lgN+ 2m））.

定理2說明MSOCFA是復雜度為O（N（lg N+ 2m））多項式時間算法，具有較低的計算復雜度，一般能夠滿足實時性要求[16]。

3　協同打擊策略

多無人機同時打擊問題在本質上是多無人機集結問題。針對這一問題，本文設計了一種同時打擊策略來實現聯盟成員對目標的同時打擊。具體做法是：首先，當聯盟組建完成后，聯盟長機將各個聯盟成員最早到達時間的最大值作為整個聯盟的最早到達時間，并以通信的方式提供給聯盟成員。然后，各個聯盟成員根據整個聯盟的最早到達時間，采用Dubins曲線原理來協同調整聯盟成員各自的飛行路徑，使得能夠按照規定時間到達目標點。最后，各個聯盟成員在路徑跟蹤算法的作用下沿著Dubins路徑飛抵目標點，從而實現對目標的同時打擊。該同時打擊策略僅需要聯盟長機將整個聯盟的最早到達時間，以通信的方式一次性下達給聯盟成員，不需要持續通信，從而減少了無人機之間的通信量，提高了隱蔽性。

3.1無人機數學模型

無人機安裝有自動駕駛儀，其飛行速度和高度可以保持恒定。為了簡化問題，假設無人機處于不同的飛行高度上，因此暫不考慮多無人機之間的碰撞問題，計劃作為后續工作加以完善。在二維平面內，無人機的數學模型[17]為

式中：v為無人機速度；Ψ∈[0，2π）為無人機的偏航角，按照東向為0，逆時針為正；WΨ為自動駕駛儀的增益；Ψc為偏航角制導指令，由路徑跟蹤制導律給出。

3.2基于Dubins曲線的協同路徑規劃方法

圖5　基于Dubins曲線的協同路徑規劃示意圖Fig.5　An example of selecting Dubins path

Dubins曲線[18]是由一段圓弧和一段直線構成，圓弧的半徑r稱之為Dubins曲線的半徑。聯盟成員通過調整各自的Dubins曲線的半徑r來實現同時到達目標點。當給定無人機的位置和航向，沿Dubin曲線飛行有兩種選擇：1）Dubins較短路徑（如圖5中的Ds）；2）Dubins較長路徑（如圖5中的Dl）.本文選擇Dubins較長路徑Dl作為聯盟成員抵達目標點的飛行路徑，這是因為如果選擇Dubins較短路徑Ds會出現無法規劃出抵達目標點的Dubins飛行路徑的情況，該情況如圖5所示。假設由無人機A1和A2構成聯盟去打擊目標T，如果選擇Dubins較短路徑Ds作為聯盟成員A1和A2抵達目標點T的飛行路徑，無人機A1需要按照增大Dubins曲線的半徑r的方式來調整自身飛行路徑的長度，使得但是隨著半徑r的增大，當目標T位于以r為半徑的圓（圖5中用虛線表示）的內部時，A1無法規劃出抵達目標點的Dubins較短路徑。此時，A1或許可以選擇Dubins較長路徑但是如果無論A1如何增大轉彎半徑r，均會使得從而無法規劃出滿足協同要求的路徑。為了避免這種“路徑長度不連續”情況的出現，本文選擇Dubins較長路徑Dl作為聯盟成員抵達目標點的飛行路徑，即無人機A1通過增大半徑r，使得.另外考慮到無人機的飛行速度較快，要求路徑規劃算法具有較好的實時性，而采用一種單一規則的通用模型可以減少計算量，節省計算時間。故基于以上兩點，本文統一采用Dubins較長路徑Dl來規劃到達目標點的路徑。

3.3Dubins路徑的跟蹤制導控制

4　多無人機分布式自主協同控制策略

本文采用有限狀態機（FSM）來實現多無人機分布式自主協同控制。多無人機協同執行搜索打擊任務時，無人機存在著以下6種任務狀態：1）搜索狀態；2）聯盟組建提議狀態；3）聯盟組建投標狀態；4）聯盟組建狀態；5）Dubins路徑規劃狀態；6）目標打擊狀態。這6種任務狀態及其狀態轉移規則（I1～I11）如圖6所示。

圖6　無人機任務狀態及其轉移規則Fig.6　Mission state of UAV and its transition

4.1搜索狀態

每架無人機的初始狀態為搜索狀態。當無人機處于搜索狀態時，無人機以一種隨機搜索的方式，對任務區域內的目標進行搜索。在隨機搜索策略下，無人機在任務區域內一定角度沿直線飛行，到達搜索邊界時，無人機以最小轉彎半徑轉彎，進行邊界規避，再次進入搜索區域，以一個新的角度繼續沿直線飛行。無人機的邊界規避策略可參考文獻[20].若無人機發現目標Tj并且自身所擁有的任務資源不能完成對Tj的打擊，就成為聯盟長機（I1），進入聯盟組建狀態；如果自身所擁有的任務資源足夠完成對Tj的打擊（I2），就進入攻擊路徑規劃狀態。如果無人機沒有發現目標，但接收到長機發來的聯盟組建提議消息時（I3），該無人機成為潛在聯盟成員，進入聯盟組建投標狀態。當無人機沒有發現目標或者所有的目標均被擊毀或者無人機的資源耗盡（I4）時，無人機處于搜索狀態。

4.2聯盟組建提議狀態

聯盟長機進入聯盟組建提議狀態后，將聯盟組建提議消息廣播給其他各架無人機。聯盟組建提議消息主要包括目標Tj的位置信息和打擊該目標所需的資源信息當聯盟長機接收到所有潛在聯盟成員發送的聯盟組建投標消息時（I5），進入聯盟組建狀態。

4.3聯盟組建投標狀態

無人機進入聯盟組建投標狀態后，根據聯盟長機發送的目標Tj的位置信息計算出自身的最早到達時間λk，并將聯盟組建投標消息反饋給聯盟長機Ai。聯盟組建投標消息主要包括最早到達時間λk和當前資源向量之后無人機一直監聽聯盟長機Ai發送聯盟組建結果。如果聯盟組建成功并且該無人機成為聯盟成員（I6），則進入攻擊路徑規劃狀態。如果聯盟組建失敗或者該無人機沒有成為聯盟成員（I7），則進入搜索狀態。

4.4聯盟組建狀態

聯盟長機進入聯盟組建狀態后，則綜合所有的反饋信息來組建聯盟，并將聯盟組建結果消息反饋給所有的潛在聯盟成員。聯盟組建結果消息主要包括聯盟組建是否成功、聯盟成員編號集合、整個聯盟的最早到達時間以及聯盟的資源向量如果聯盟組建成功并且聯盟長機成為聯盟成員（I8），則進入攻擊路徑規劃狀態。如果聯盟組建失敗或者聯盟長機沒有成為聯盟成員（I9），則進入搜索狀態。

4.5攻擊路徑規劃狀態

在攻擊路徑規劃狀態中，無人機需要根據整個聯盟的最早到達時間重新規劃各自的攻擊路徑以實現對目標的同時打擊。當Dubins攻擊路徑規劃完成后（I10），進入目標打擊狀態。

4.6目標打擊狀態

在目標打擊狀態中，無人機沿著各自規劃出的Dubins攻擊路徑飛行，當到達目標點時，完成對目標的打擊，相應地減少自身的資源。當目標被擊毀時（I11），無人機重新進入搜索狀態，回歸“空閑”。

5　仿真結果與分析

首先，在5.1節中設置一個相對復雜的任務想定，來分析MSOCFA的合理性和可行性，同時來驗證基于令牌數的沖突消解機制能夠有效消解多架無人機協同執行搜索打擊任務時，聯盟組建過程中由于資源競爭所導致的沖突。其次，為了消除單次仿真的偶然性，更客觀全面地評估任務完成的效果，在5.2節中，使用蒙特卡洛法分析無人機數量和目標數量對聯盟組建的影響。然后，在未知環境中，除了要考慮目標出現位置的隨機性外，還應考慮到目標出現時間的隨機性，因此在5.3節中，設置目標的出現時間是隨機的，來檢驗MSOCFA能否對隨機出現的目標成功組建聯盟。最后，在5.4節中，將MSOCFA與文獻[21]中的PSO算法進行對比仿真，驗證了MSOCFA具有較高的實時性，并且該對比仿真也說明，在平均任務完成率方面，MOCFA方法優于PSO方法。

5.1MSOCFA的仿真結果與分析

在仿真算例1中，任務區域設定為2 000m× 2 000m的矩形區域，區域內設定了3個目標，使用6架無人機執行搜索和打擊任務。無人機的速度v=15m/s，最小轉彎半徑rmin=100 m，最大探測距離smax=300m，仿真步長設為0.1 s.無人機和目標的初始狀態見表1和表2，算例1的結果如圖7所示。

表1　無人機初始狀態（算例1）Tab.1　Initial state of UAVs（Scenario 1）

表2　目標初始狀態（算例1）Tab.2　Initial state of targets（Scenario 1）

在t=0 s時，A1發現目標T1、T3的同時A2也發現了目標T1、T3，由于A1的令牌數比A2的令牌數大，那么A1優先組建聯盟，此時A1作為長機，它需要在所發現的目標T1、T3中挑選出一個目標作為打擊對象。又由于T1的令牌數大于T3的令牌數，那么目標T1優先被打擊，即首先由A1作為長機組建聯盟完成對目標T1的打擊，將目標T1的信息發送給潛在聯盟成員A3、A4、A5和A6（A1和A2這時候由于發現目標而成為了長機）。長機A1的聯盟組建結果為其最早到達時間為105.3 s，其資源向量為（3，7，7），而打擊目標T1的資源需求向量為（3，2，2），因此可以完成對目標T1的打擊。

圖7　6架無人機和3個目標的仿真結果（算例1）Fig.7　Simulation results of 6 UAVs and 3 targets（Scenario 1）

緊接著當A1完成聯盟的組建后，A2才可以組建聯盟，此時A2從它所發現的目標T1、T3中挑選一個作為打擊對象，由于目標T1已經被分配，因此A2將目標T3作為打擊對象。由于A2的當前資源向量，而打擊目標T3的資源需求向量（0，0，1），也就是說A2擁有打擊T3所需的全部資源，因此A2不需要組建聯盟，直接完成對T3的打擊，如圖7所示，A2沿著規劃出的Dubins路徑飛抵目標T3，其最早到達時間為48.4 s.

在t=5.4 s時，A4發現了目標T2，A4成為長機，將目標T2的信息發送給潛在聯盟成員A5（此時僅有A5是處于“空閑”的）。長機A4的聯盟組建結果為，最早到達時間為112.9 s，其資源向量為（2，2，1），而打擊T2的資源需求向量為（2，1，1），故可以完成對T2的打擊。整個任務完成時間為119.3 s.整個過程中，聯盟組建結果如表3所示。

表3　聯盟組建結果（算例1）Tab.3　Results of coalition formation（Scenario 1）

上述仿真結果驗證了MSOCFA的合理性和可行性，并且引入令牌機制后能有效消解多架無人機協同執行搜索打擊任務時，聯盟組建過程中由于資源競爭所導致的沖突。當多架無人機執行搜索打擊任務時，發現目標后采用MSOCFA組建聯盟，可以集中優勢兵力在較短的時間內完成對目標的打擊，并減少資源的浪費，提高了任務的執行效率。

5.2無人機數量和目標數量對MSOCFA的影響

為了進一步分析無人機數量和目標數量對MSOCFA的影響，消除單次仿真的偶然性，更客觀、全面地評估任務完成的效果，按照Monte-Carlo法的思想，選取目標的數量為5、10和15，同時設定無人機的數量為5、10、15和20，分別進行12組實驗。每組實驗分別進行100次仿真，統計出每組實驗的平均任務完成時間（AMCT）和平均任務完成率（APMC）.任務完成率定義為：（擊毀目標數/目標總數）×100%.

每次仿真中，任務區域、無人機的速度、最小轉彎半徑、最大探測距離和仿真步長與5.1中一致，同時設定最大仿真時間為t=1 000 s.目標的位置、無人機的初始位置和初始航向均是隨機生成的。其中，在目標Tj的資源需求向量中，第q種資源（m=3）的數量為0～3內的隨機整數；在無人機Ai的當前資源向量中，第p種資源（n=3）的數量為2～4之間的隨機整數。每組實驗的平均任務完成率和平均任務完成時間的統計結果分別如圖8、圖9所示。

圖8　不同無人機數量和目標數量下的平均任務完成率Fig.8　Comparison of averagemission completion rates

從統計結果可以看出：

1）當無人機數量一定時，目標數量越少，平均任務完成時間越短；

2）當目標數量一定時，無人機數量越多，平均任務完成時間越短；

圖9　不同無人機數量和目標數量下的平均任務完成時間Fig.9　Comparison of averagemission completion times

3）當無人機數量過少時，其平均任務完成率低于100%，其平均任務完成時間為1 000 s.這是因為在這種情況下，當無人機發現目標時，由于無人機的資源消耗殆盡，不能組建聯盟完成對所發現目標的打擊，而轉入搜索狀態，直到仿真結束，即t=1 000 s.例如當無人機的數量為5架，目標的數量為15個時，平均任務完成率僅為53%，平均任務完成時間為1 000 s.但隨著無人機數量的增多，其資源也相應地增多，就能成功地組建聯盟完成對所有目標的打擊，因此其平均任務完成率逐漸增大，直至達到100%.其平均任務完成時間則會相應地減少，原因就在于隨著無人機數量的增多，無人機發現目標所用的時間就越短，那么任務完成時間也就越短。

4）無人機和目標的數量和位置是隨機生成的，可見MSOCFA算法對任意數量、任意位置的無人機和目標均有效。

5.3目標出現時間隨機時的仿真結果與分析

在未知環境中，除了要考慮目標出現位置的隨機性外，還應考慮到目標出現時間的隨機性，因此需要設置目標的出現時間是隨機的，來檢驗MSOCFA能否對隨機出現的目標成功組建聯盟。

在仿真算例2中，任務區域、無人機的速度、最小轉彎半徑、最大探測距離和仿真步長與5.1中一致，設置4架無人機搜索打擊2個目標的任務想定，無人機和目標的初始狀態見表4和表5，其中目標T1的出現時間是預先未知且是隨機的。

表4　無人機初始狀態（算例2）Tab.4　Initial state of UAVs（Scenario 2）

表5　目標初始狀態（算例2）Tab.5　Initial state of targets（Scenario 2）

如圖10所示，在t=71.9 s時，A1發現T2，由于打擊T2所需的資源向量為=（2，2，2），而A1的當前資源向量為=（1，0，3），A1沒有足夠的資源，因此成為聯盟長機，組建聯盟中的聯盟成員為A1和A3，其最早到達時間為87.8 s，其資源向量為（2，2，4）.打擊完 T2后，A1的當前資源向量變為=（0，0，1），A3的當前資源向量變為=（0，0，1）.

圖10　t=71.9 s時，A1發現T2（算例2）Fig.10　A1detects T2for t=71.9 s（Scenario 2）

如圖11所示，在t=172.0 s時，目標T1出現。在圖12中，當t=172.3 s時，A2發現T1，由于打擊T1所需的資源向量為=（2，3，2），而A2的當前資源向量為=（1，1，1），A2沒有足夠的資源，因此成為聯盟長機，組建聯盟中的聯盟成員為A2、A3和A4，其最早到達時間為137.9 s，其資源向量為（2，3，2）.打擊完T1后，A2的當前資源向量變為=（0，0，0），A3的當前資源向量變為=（0，0，0），A4的當前資源向量變為=（0，0，0）.整個任務完成時間為316.3 s.算例2的最終仿真結果如圖13所示。

5.4MSOCFA與PSO的仿真對比

為了驗證MSOCFA具有較高的實時性，將本文方法與文獻[21]的PSO算法進行對比，重點考察任務完成時間與算法的時間開銷。實驗環境為Intel（R）Core（TM）Duo CPU，主頻2.4GHz，內存為2 GB DDRII.仿真平臺開發工具為Microsoft Visual C++6.0.在算例3中，采用4架無人機協同搜索打擊4個目標，無人機和目標的初始狀態分別如表6和表7所示。

圖11　t=172.0 s時，目標T1出現（算例2）Fig.11　Target T1appears for t=172.0 s（Scenario 2）

圖12　t=172.3 s時，A2發現T1（算例2）Fig.12　A2detects T1for t=172.3 s（Scenario 2）

圖13　4架無人機和2個目標的仿真結果（算例2）Fig.13　Simulation results of 4 UAVs and 2 targets（Scenario 2）

表6　無人機初始狀態（算例3：MSOCFA與PSO仿真對比）Tab.6　The initial states of 4 UAVs in the comparison simulations using MSOCFA and PSO（Scenario 3）

表7　目標初始狀態（算例3：MSOCFA與PSO仿真對比）Tab.7　The initial states of target in the comparison simulations using MSOCFA and PSO（scenario 3）

圖14　采用MSOCFA的仿真結果Fig.14　Mission performance achieved using MSOCFA

圖14為采用MSOCFA算法的仿真結果，當t= 0 s時，A1發現T1，由于A1的當前資源向量=（2，3，4），而打擊T1的資源需求向量=（1，1，2），也就是說A1擁有打擊T1所需的全部資源，因此A1不需要組建聯盟，直接完成對T1的打擊。當t=0.9 s時，A3發現T4成為長機，將T4的信息發送給潛在聯盟成員A2、A4，建聯盟，其最早到達時間為156.9 s.當t=190.3 s時，A1發現T2成為長機，將T2的信息發送給潛在聯盟成員A2、A3、A4，建聯盟=，其最早到達時間為81.9 s.當t=284.1 s時，A3發現T3成為長機，將T3的信息發送給潛在聯盟成員A1、A2、A4，建聯盟其最早到達時間為122.9 s.整個搜索打擊任務的完成時間為406.5 s.MSOCFA算法給出的聯盟組建結果如表8所示。

表8　采用MSOCFA時的聯盟組建結果Tab.8　The details of coalition formation using MSOCFA

圖15為采用PSO算法的仿真結果。表9給出了采用PSO求解得到的最優聯盟組建結果，A1首先完成對T1的打擊，然后與A4一起形成聯盟完成對T4的打擊。A2、A3分別打擊T3、T2.整個任務的完成時間為157.4 s.

圖15　采用PSO時的仿真結果Fig.15　Mission performance achieved using PSO

表9　采用PSO的聯盟組建結果Tab.9　The details of coalition formation using PSO

MSOCFA與PSO的對比結果如表10所示，可以看出，在任務完成時間上，PSO優于MSOCFA，產生這一結果有兩方面的原因：一方面，正如文獻[21]所指出的，采用PSO求解聯盟組建問題時，需要預先知道目標的數量、位置和打擊目標所需的資源向量，因此無人機不需要對整個作戰區域進行搜索，直接根據預先掌握的信息組建聯盟完成對所有目標的打擊。而采用MSOCFA不需要預先知道目標的數量、位置和打擊目標所需的資源向量等信息，那么無人機需要對目標進行搜索，當發現目標時，才組建聯盟。另一方面，PSO算法得到的是全局最優聯盟組建方案，而MSOCFA為了提高算法的實時性，通過分階段求解策略來降低問題的復雜程度。雖然MSOCFA得不到嚴格的全局最優解，但是其給出的聯盟組建結果是合理和可行的。況且在算法時間開銷方面，PSO算法的CPU計算時間為17.3 s，而MSOCFA的CPU計算時間為64 ms，因此在算法的實時性方面，MSOCFA明顯優于PSO算法，從而驗證了MSOCFA具有較高的實時性。

表10　MSOCFA與PSO的對比Tab.10　Comparison of MSOCFA and PSO

為了更為全面地比較MSOCFA與PSO這兩種算法的性能，按照Monte-Carlo法的思想，選取目標的數量為10，同時設定無人機的數量為5、10、15和20，分別進行4組實驗。每組實驗分別進行100次仿真，統計出每組實驗的平均任務完成率、平均任務完成時間、平均CPU計算時間。

每次仿真中，任務區域、無人機的速度、最小轉彎半徑、最大探測距離和仿真步長與5.1節一致，同時設定最大仿真時間為t=1 000 s.PSO算法的迭代次數為5 000次。目標的位置、無人機的初始位置和初始航向均是隨機生成的。每組實驗的平均任務完成率、平均任務完成時間、平均CPU計算時間的統計結果分別如圖16～圖19所示。

從統計結果可以看出：

1）在任務完成時間上，PSO優于MSOCFA，其原因在算例3中已做分析。

2）當無人機數量過少時（例如5架無人機搜索打擊10個目標），PSO的任務完成率為0%，這是因為無人機的數量過少，無人機系統所有資源總和不足以完成對所有目標的打擊，當采用PSO算法時，求解不出聯盟組建問題的全局最優解，因而平均任務完成率為0%.

3）當無人機數量過少時（例如5架無人機搜索打擊10個目標），盡管采用MSOCFA時的平均任務完成率也不能達到100%（這是因為無人機系統所有資源總和不足以完成對所有目標的打擊），但是其平均任務完成率為78.2%，比基于PSO的聯盟組建策略要高。這是因為，在MSOCFA算法中，當無人機發現目標時，才會動態地組建聯盟，執行對該目標的打擊，因此先前被發現的目標能被摧毀。但隨著搜索打擊任務的執行，無人機的資源消耗殆盡，不能組建聯盟完成對后續發現目標的打擊，而轉入搜索狀態，直到仿真結束。

圖16　不同聯盟組建策略下的平均任務完成率（MSOCFA vs.PSO）Fig.16　Comparison of averagemission completion rates（MSOCFA vs.PSO）

圖17　不同聯盟組建策略下的平均任務完成時間（MSOCFA vs.PSO）Fig.17　Comparison of averagemission completion times（MSOCFA vs.PSO）

圖18　MSOCFA算法的平均CPU計算時間Fig.18　Mean time taken to complete a simulation using MSOCFA

圖19　PSO算法的平均CPU計算時間Fig.19　Mean time taken to complete a simulation using PSO

4）隨著無人機數量的增多，PSO的CPU計算時間呈指數增長，雖然MSOCFA的CPU計算時間也隨著無人機數量的增加而增長，但是不同于PSO算法，并不呈指數形式增長，其增長得較為緩慢。并且當無人機數量為5、10、15、20時，MSOCFA算法的CPU計算時間均遠小于 PSO算法，由此可見，MSOCFA的實時性明顯高于PSO算法。

上述Monte Carlo仿真對比實驗說明：任務完成率與所采用的聯盟組建策略是有關系的，在平均任務完成率方面，MOCFA方法優于 PSO方法；MSOCFA算法比PSO算法具有較高的實時性。

6　結論

本文借鑒聯盟的思想來解決未知環境下異構多無人機協同搜索打擊時的任務分配問題。得到了如下結論：

1）提出以最小化目標打擊時間和最小化聯盟規模為優化指標，以同時打擊和滿足打擊資源需求為約束條件的聯盟組建模型。該模型適用于解決異構多無人機在未知環境下協同執行搜索打擊任務時的任務分配問題。

2）由于聯盟組建問題是一個組合優化問題，提出了分階次優聯盟快速組建算法MSOCFA.算法復雜度分析證明了該算法是一個多項式時間算法，能夠滿足實時性要求，并且通過與PSO算法進行仿真對比也驗證了該算法具有較高的實時性。另外對比仿真也說明，在平均任務完成率方面，MSOCFA方法優于PSO方法。

3）使用多次仿真統計了不同無人機數量和不同目標數量下的平均任務完成率和平均任務完成時間，驗證了無人機數量和目標數量對聯盟組建的影響，即無人機數量越多，目標數量越少，其平均任務完成時間越短；但是當無人機數量過少時，其平均任務完成率低于100%，其原因在于無人機的資源不足，無法組建出聯盟完成對所發現目標的打擊。

4）在本文中，沒有考慮諸如通信距離、通信時延等通信約束對聯盟組建的影響，所以還需考慮無人機之間的通信約束條件，對聯盟組建方法作進一步完善。除此之外，后續工作還需要針對無人機之間的避撞問題問題，進一步研究無人機的感知與規避技術，以保證無人機的飛行安全。

（References）

[1]Shima T，Rasmussen S.UAV cooperative decision and control challenges and practical approaches[M].Philadelphia：Society for industrial and Applied Mathematics，2009.

[2]Schumacher C，Chandler PR，Rasmussen SR.Task allocation for wide area searchmunitions via network flow optimization[C]∥AIAA Guidance，Navigation，and Control Conference and Exhibit.Montreal，QC：AIAA，2001.

[3]Schumacher C，Chandler P R，Rasmussen S R.Task allocation for wide area search munitions via iterative network flow[C]∥AIAA Guidance，Navigation，and Control Conference and Exhibit. Monterey，CA：AIAA，2002.

[4]Schumacher C，Chandler P R，Pachter M，et al.UAV task assignmentwith timing constrains[C]∥AIAA Guidance，Navigation，and Control Conference and Exhibit.Austin，Texas：AIAA，2003.

[5]Schumacher C，Chandler P R，Pachter M，et al.UAV task assignmentwith timing constrains via mixed integer linear programming[C]∥AIAA 3rd Unmanned Unlimited Technical Conference，Workshop and Exhibit.Chicago，Illinois：AIAA，2004.

[6]Schumacher C，Chandler PR，Pachter M，et al.Constrained optimization for UAV task assignment[C]∥AIAA Guidance，Navigation，and Control Conference and Exhibit.Providence，RI：AIAA，2004.

[7]Darrah M A，Niland W M，Stolarik BM.Multiple UAV dynamic task allocation usingmixed integer linear programming in a SEAD mission[C]∥AIAA InfoTech at Aerospace：Advancing Contemporary Aerospace Technologies and Their Integration.Arlington，VA：AIAA，2005.

[8]Alighanbari M，How JP.Decentralized task assignment for unmanned aerial vehicles[C]∥Proceedings of the44th IEEEConference on Decision and Control，and the European Control Conference.Seville，Spain：IEEE，2005：5668-5673.

[9]Shima T，Rasmussen SJ，Sparks A G，etal.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J].Computers&Operations Research，2006，33（11）：3252-3269.

[10]錢艷平，夏潔，劉天宇.基于合同網的無人機協同目標分配方法[J].系統仿真學報，2011，23（8）：1672-1676. QIAN Yan-ping，XIA jie，LIU Tian-yu.Task assignment scheme based on contract net[J].Journal of System Simulation，2011，23（8）：1672-1676.（in Chinese）

[11]廖沫，陳宗基.基于滿意決策的多機協同目標分配算法[J].北京航空航天大學學報，2007，33（1）：81-85. LIAO Mo，CHEN Zong-ji.Coordinated target assignment in multi-UAV based on satisficing decision theory[J].Journal of Beijing Universityof Aeronautics andAstronautics，2007，33（1）：81-85.（in Chinese）

[12]Shehory O，Kraus S.Methods for task allocation via agent coalition formation[J].Artificial Intelligence，1998，101（1/2）：165-200.

[13]Service T C，Adams JA.Coalition formation for task allocation：theory and algorithms[J].Autonomous Agents and Multi-Agent Systems，2011，22（2）：225-248.

[14]Vig L，Adams JA.Multi-robot coalition formation[J].IEEE Transactions on Robotics，2006，22（4）：637-649.

[15]Chalkiadakis G，Markakis E，Boutilier C.Coalition formation under uncertainty：bargaining equilibria and the Bayesian core stability concept[C]∥Proceedings of the6th International Joint Conference on Autonomous Agents&Multiagent System.Honolulu，HI：the Association for Computing Machinery，2007：412-419.

[16]Cormen TH，Leiserson C E，Rivest R L.Introduction to algorithms[M].3rd ed.New York：MIT Press，2009.

[17]Nelson D R，Barber D B，McLain TW，et al.Vector field path following for miniature air vehicles[J].IEEE Transactions on Robotics，2007，23（3）：519-529.

[18]Tsourdos A，White B，Shanmugavel M.Cooperative path planning of unmanned aerial vehicles[M].Bognor Regis：John Wiley and Sons Ltd，2011.

[19]Ambrosino G，Ariola M，Ciniglio F，et al.Path generation and tracking in 3-D for UAVs[J].IEEE Transactions on Control Systems Technology，2009，17（4）：980-988.

[20]符小衛，李建，高曉光.帶通信約束的多無人機協同搜索中的目標分配[J].航空學報，2014，35（5）：1347-1356. FU Xiao-wei，LI Jian，GAO Xiao-guang.Target allocation in multi-UAV cooperative search with communication constraints [J].Acta Aeronautica et Astronautica Sinica，2014，35（5）：1347-1356.（in Chinese）

[21]Sujit P B，Georget JM，Beard R.Multiple UAV task allocation using particle swarm optimization[C]∥AIAA Guidance，Navigation and Control Conference and Exhibit.Honolulu，HI：AIAA，2008.

Coalition Formation of Multiple Heterogeneous Unmanned Aerial Vehicles in Cooperative Search and Attack in Unknown Environment

LIU Zhong1，GAO Xiao-guang1，FU Xiao-wei1，MOU Zhi-ying2
（1.School of Electronics and Information，Northwestern Polytechnical University，Xi'an 710129，Shaanxi，China；2.Science and Technology on Avionics Integration Laboratory，Shanghai200233，China）

A novelmethod for coalition formation ofmultiple heterogeneous unmanned aerial vehicles in cooperative search and attack in unknown environment is presented to improve the cooperative search and attack effectivenesses ofmultiple heterogeneous unmanned aerial vehicles.A coalition formation model is established based on theminimum target attack time and theminimum coalition scalewith the constraints of required resources and simultaneous strike.A multistage sub-optimal coalition formation algorithm （MSOCFA）that has low computational complexity is proposed to solve the optimization problem of coalition formation.The performances ofMSOCFA and partical swarm optimization algorithms are compared in terms ofmission performance，complexity of algorithm and time taken to form the coalitions.In order to enable themultiple cooperative unmanned aerial vehicles to accomplish the search and attack missions autonomously，a distributed autonomous control strategy is proposed，which is based on the finite-statemachine（FSM）.The simulation results show the rationality，validity and high real-time performance of the proposed method for the coalition formation ofmultiple heterogeneous unmanned aerial vehicles in cooperative search and attack in the unknown environment.Monte Carlomethod is employed to validate the impact of the number of unmanned aerial vehicles and targets on coalition formation.The reduced average mission completion time relates to the decreased number of targets and the increased the number of unmanned aerial vehicles.

control science and technology；multi-unmanned aerial vehicle；cooperative search and prosecute；coalition formation；finite-statemachine；Monte Carlomethod

V 279

A

1000-1093（2015）12-2284-14

10.3969/j.issn.1000-1093.2015.12.011

2014-12-15

航空科學基金、航空電子系統綜合技術重點實驗室聯合項目（20155553041）；中央高校基本科研業務費專項資金項目（3102015ZY092）

劉重（1985—），男，博士研究生。E-mail：15829732829@163.com；高曉光（1957—），女，教授，博士生導師。E-mail：xggao@nwpu.edu.cn