基于改進合同網的異構無人機協同對地任務分配

廖承城，陶偉，劉韜

（1.四川大學計算機學院，成都610065；2.中國艦船研究設計中心，武漢430064）

0 引言

有人機（MAV）/無人機（UAV）編隊協同作戰過程中，編隊的戰術指揮控制和任務管理由任務控制站完成，對地攻擊以及偵察任務由無人機自主完成。無人機任務分配主要關注點為：即在滿足無人機戰術技術指標、任務要求、平臺和武器性能約束、戰術使用條件的前提下，通過對無人機進行任務分配，將不同位置、不同價值、不同威脅的目標合理快速分配給不同類型、不同價值、不同能力的無人機，以最大限度的提高整體作戰能力[1]，最大限度的利用無人機資源。

無人機任務分配是一個多約束的復雜優化問題，求解過程復雜，需要較大的計算成本和時間成本，在大規模動態任務規劃中面臨著挑戰。近年來，國內外對任務分配的研究取得了長足的發展，目前求解方法較多，包括：①基于混合整數規劃模型的確定性算法[2]，如窮舉法[3]、動態規劃法[4]等；②基于啟發式的智能算法，如遺傳算法[5]、粒子群算法[6]、模擬退火算法[7]等；③基于分布式模型的算法，如基于滿意決策理論的方法[8]、基于合同網的方法[9]等。

但無論是確定性方法還是啟發式方法，本質上都屬于集中式任務分配方法，存在一個中心節點負責所有任務分配問題。雖然該方法在一定條件下可以獲得全局最優解，但由于數據傳輸都需要通過唯一的一個控制中心進行，處理信息量太大，不易滿足實時性要求，且可靠性、可維護性、抗干擾性都不高，在實際應用中存在很多問題。隨著無人機自主性的興起，信號集中控制往往與無人機的自主性捆綁在一起。提高分布式控制能力是無人機智能化、自主化的必然要求。雖然近年來分布式任務分配方法的研究取得了很大進展，但與集中式方法相比還存在較大差距，不能對無人機形成有效的協同控制。同時，隨著戰場環境的日益復雜，單一類型無人機已經不能滿足需求，有的任務需要偵察功能無人機，有的任務需要打擊功能無人機，分配場景就單一場景變成異構場景，需要考慮更多的戰場環境任務分配指標。

為彌補集中式任務分配方法的不足，有效地支持無人機編隊作戰[10]，本文將無人機視為在有限控制下具有一定自主決策能力的智能體，并按照一定的規律對無人機進行歸類和分層，以改進合同網算法作為智能體之間的任務協商準則，考慮更多的任務分配指標，最終實現無人機編隊實時的分層次分布式任務分配[11]，以適應復雜多變的戰場環境。

1 基于合同網的任務分配理論

合同網算法通過模擬經濟行為中招標-投標-中標機制，處理任務的委派和遷移工作。合同網的基本思想是通過各節點間的招投標過程來分配任務，并在招標者和投標者的雙向選擇中引入一定的協商機制和約束條件。當招標者有任務需要其他節點幫助時，招標者就會將該任務信息廣播給其他節點，即任務發布過程。接收到任務信息的其他節點收到邀請以后會先評估自己解決這一問題的能力，如果符合，計算出投標價值，然后成為投標者。最后，招標者會評估每位投標者的投標價值，動態的將當前任務轉移給合適的投標人，從而實現分布式任務分配。

合同網任務分配模型[7]由多個可以互相傳遞信息的代理組成，每個代理都具有相互間通信和一定的信息處理能力的個體，具備先進且充分的自主能力，具有全局通信和信息快速處理的能力。可以將這些代理分為三種，即招標代理、投標代理和中標代理。其中招標代理初始時由MAV擔任，在任務重分配和任務均衡過程中UAV也可以通過競爭成為招標者，投標和中標代理由UAV擔任。基于合同網的任務分配主要有六個步驟，其中包含四個基本步驟和二個擴展步驟，如圖1所示。

圖1 合同網擴展步驟圖

步驟1：任務發布

當MAV發現有任務需要分配時，它會立刻將該任務信息廣播給可能響應的UAV，此時MAV成為招標者，其他無人機則成了投標者，完成任務發布階段。

步驟2：任務投標

從招標者處獲得任務信息的無人機將評估自身是否有能力完成該項任務，并計算完成這項任務所需要花費的成本。只要它們有完成這項任務的意愿，就向招標者投標，從而成為投標者參與任務競標。

步驟3：任務中標

發布任務后，招標者將會進入待標狀態。當收到某個投標者的任務投標信息時，招標者會保存其投標信息。當收到所有投標者的投標信息后，或達到預定的任務投標截止日期，招標者將停止接收標書，并對投標信息進行綜合評估，然后選擇最合適的投標者，將合同授權信息發送給此投標者，為下一步的合同簽約做好準備。如果此投標者成為了該任務的投標人，則其他投標者將會收到投標失敗的信息。

步驟4：簽約合同

投標者收到合同授權后，會向招標者發一份確認書，確保該合同履行，且合同此刻正式成立。如果投標者不能正常履行合同，則應向招標者發出取消合同的消息，然后任務分配流程將返回至步驟3，招標者會重新評估其他投標信息，并從中選擇最合適的投標者，在合同正式簽約后，贏得合同的投標者開始執行任務，確保合同履行。

為使MAV能夠更有效地監控每架無人機的任務執行情況，對基于傳統合同網任務分配方法進行擴展，增加以下兩個步驟：

步驟5：狀態更新

中標者應及時將合同任務信息上報給MAV，從而MAV可以在全局視圖中標注每架無人機的任務順序，監控每架無人機的任務執行情況，無人機可以在合同任務狀態發生變化時向MAV提出更新，即觸發更新機制。

步驟6：心跳保持

MAV會為每架無人機維護一個心跳保持包。在任務執行過程中，無人機需要定期向MAV報告任務執行情況。如果MAV在連續的周期內沒有接收到來自無人機的信息，則認為該無人機已損壞或發生錯誤，同時MAV會主動向該無人機詢問信息，如果無人機沒有回復詢問信息，MAV將接管剩余的任務，并將它們實時拍賣給其他無人機，此刻將執行一輪任務重分配。

2 基于改進合同網的任務分配模型

2.1 任務分配建模

本文針對多架作戰無人機偵察和攻擊地面多個目標問題進行研究。假設當前有N架無人機，M個地面目標，需要將M個地面目標分配給N架無人機，其中無人機集合記為Vi={V1,V2,…,Vi,…,Vn}，1≤i≤N，其中Vi表示第i架無人機，一架無人機可以接收多個任務形成對應的任務序列。目標任務點集合記為Tj={T1,T2,…,Tj,…,Tm}，1≤j≤M，其中Tj表示第j個目標任務點，每個單任務只能由單架無人機獨立完成。

構建任務分配矩陣QN×M：

定義無人機i的任務序列為Si，例如3號無人機分配到的任務序列為5、6、3、2號任務，用任務序列集合表示為Si={T5,T6,T3,T2}。

2.2 任務分配效益函數

招標者發現新任務，通過“招標-投標-中標”過程完成對任務的分配，中標者是獲取新任務后無人機編隊整體收益最大的無人機。任務分配的編隊收益主要考慮能力匹配原則、最小代價作戰原則、負載均衡原則。將目標的收益價值、飛行航程和無人機受到的威脅程度作為評價作戰效能的主要指標，并以此作為衡量多無人機協同任務分配方案優劣的重要戰術指標。

（1）任務收益價值函數

任務收益價值由目標價值和無人機執行任務的能力決定，無人機執行任務時，可以通過對目標價值的評估，來引導任務分配的優化，該指標可以使無人機更青睞于高價值的任務目標。假設無人機Vi執行打擊任務Tj，對該目標的損毀概率為Pi(Tj)，目標任務Tj的價值為Value（Tj），目標價值表明了目標的戰略重要程度。則此單次打擊任務所獲得的收益價值為Reward（Tj）。

（2）任務開銷成本函數

任務開銷成本主要包含兩方面：路徑代價和威脅代價。

首先，路徑代價主要考慮的是飛行時間和燃油消耗這兩方面，較小的路徑代價開銷可以使得任務分配趨向節約作戰時間和燃油兩方向。任務預分配時將采取就近原則，即盡可能分配距離較近的任務目標，一旦任務目標確定則為無人機設計航程盡量短的路徑規劃。

其次，威脅程度小可以確保無人機的存活率，有效避免無人機被敵方摧毀，從而引導目標分配向著減小無人機任務毀傷代價的方向進行。通過該指標使無人機遠離戰場威脅，安全航行，避免被摧毀代價。

假設第i架無人機被分配攻擊任務目標Tj，則路徑代價函數可以定義為：

其中，leni(Tj)表示第i架無人機到任務目標Tj的航程距離，lenmax表示所有無人機相對于任務目標Tj的最大航程。

威脅代價函數可以定義為:

其中Value（Tj）表示第i架無人機的價值，與無人機武器掛載有關；Ri(Tj)表示無人機攻擊目標Tj被擊毀的概率。

根據任務分配的評價標準，任務開銷成本主要由飛行航程代價和威脅代價共同決定，由于收益價值函數與開銷成本函數具有不同的量綱，開銷成本函數需要進行歸一化處理，引入權重變量δ，歸一化處理后得到開銷成本函數如下

其中Costi(Tj)表示任務開銷成本，Value（Tj）表示第i架無人機的價值，Ri(Tj)表示無人機攻擊目標Tj被擊毀的概率，Pathi表示路勁開銷代價，PThri(Tj)表示任務威脅代價。

（3）任務效能函數

根據主要評定指標，任務效能由任務收益價值和任務開銷成本共同決定，得到任務效能函數如下：

其中Proi(Tj)表示任務優先級值。將任務優先級值放入任務分配有效性函數中，引導分配過程中關注任務緊急程度指標，優先委派緊急程度高的目標任務。

2.3 任務分配約束條件

在得到任務分配效能函數之后，無人機協同競拍不同類型任務，為實現最大總體效能，定義多約束條件如下所示：

2.4 任務分配負載均衡

雖能夠以流程優化后的合同網算法完成協商以及在上述約束條件下實現任務分配，但依舊存在著任務分配不合理的情況，例如有的無人機負載過高，有的無人機任務量較少甚至沒有任務，資源利用率不高，整體效能較低的缺點。針對這些問題，本文引入了任務負載率指標RtLoadi(Si)，即無人機的相對工作量大小。

首先，定義無人機i的任務負載為tLoadi(Si)，即無人機i執行完所有任務所需要的代價。

在上式中N為無人機總數量，Si為無人機i的執行任務序列。

其次，如果當前無人機都具備任務拍賣的能力，則應通過比較任務負載的方式決定誰更有機率成為招標者。當多架無人機同時申請任務拍賣權時，將根據任務負載率來決定下一輪拍賣權的歸屬，任務負載率較大的無人機獲得拍賣權的概率較大，任務負載率求解過程如公式（10）所示：

其中負載率RtLoadi(Si)具體含義應描述為：

RtLoadi(Si)＜0，表示無人機i的負載低于系統中無人機的平均負載；RtLoadi(Si)＞0，表示無人機i的負載高于系統中無人機的平均負載；RtLoadc(Sc)＞RtLoadk(Sk)，表示無人機c的任務負載高于無人機k的任務負載，即c無人機比k無人機更有機會獲得下一次任務拍賣權，進行合同交換，將過多的任務分配給其他無人機承擔，從而減少無人機負載壓力，更充分的利用無人機資源。

當有新任務發布，或者觸發重分配時，所有的無人機會重新計算自己的任務負載率，判斷是否要參與此次拍賣，進而實現實時任務分配。整體任務分配流程圖如圖2所示。

圖2 任務分配流程圖

為更有效實現全局任務分配負載均衡，根據上述定義的任務負載指標，增加任務分配約束條件如公式（11）所示，表示每架無人機的任務工作量應滿足一定的平衡。

2.5 任務重分配后效能計算

當出現突發情況，例如無人機突發故障時，會立即觸發實時任務重分配，并通過合同的買賣和交換操作，使得重分配后的全局任務負載更加均衡：

（1）任務買賣

首先，爭奪拍賣權，選擇當前系統中任務負載最高的無人機作為拍賣者，任務負載低于0的無人機只能作為競拍者；然后，對于已經獲取到拍賣權的無人機，需要從自身任務集中選出無法繼續執行的任務并用于拍賣，隨后進入拍賣環節，即任務重分配環節；最后通過改進合同網算法計算每一種拍賣情況所獲得的整體收益，選擇出最優的分配方案，然后根據分配方案把任務分配給對應的無人機。

假設無人機i為拍賣者，無人機j為競標者，而Costi(Si)表示無人機i執行任務序列Si所需要的開銷代價。無人機i由于任務負載量過大，拍賣目標Tk后新的任務序列為Si-k，代價減少為C1，如公式（12）所示。

無人機j初始執行任務序列為Sj，競拍獲得目標Tk之后的任務序列為Sj+k，代價增加為C2,如公式（13）所示。

因為只有一個C1，而競標者有多個，即C2有多種情況，建立矩陣統計所有的C1-C2的結果并記錄對應的任務拍賣關系。通過分析可知，當拍賣者和對應拍賣目標確定之后，拍賣者所決定的代價減少是一個定值，即C1大小不變。而此時競標者所決定的代價增加存在多種情況，即C2具有多個值結果。若要使得系統代價減少最多、整體效能最優，應使得C1-C2最大，即求C2最小值，也就是從潛在競拍者中選擇C2最小的無人機作為此次競拍勝出者即可。

（2）任務交換

而任務交換通常是在任務買賣之后進行，用于解決任務買賣后存在的分配不合理問題。由交換的性質可知，各無人機的任務數在交換之后仍保持不變，其流程如所示。

假設當前交換組合是無人機i和無人機j，其交換后的開銷分別是C1和C2，則該組合交換后總代價減少量可表示為C1+C2，然后分別記錄系統中所有可能的交換組合的對應總代價減少量，并生成交換代價矩陣，若要使得整體減少量最大、整體效能最優，則根據交換代價矩陣判斷并找出需要交換的任務即可。

3 仿真與結果分析

3.1 實驗描述

該本文以異構多無人機為仿真對象，在x，y∈[0,1000]的二維地面區域里進行仿真實驗，x表示地面區域的長，y表示地面區域的寬。本文實驗環境中有6架無人機，分別用V_i表示，i∈{1,2,3,4,5,6}，其中V1、V3、V6三架無人機具備偵察模塊，另外三架無人機具備打擊模塊。任務目標點總計有20個，其中9個為正方形標記點的偵察任務，11個為三角形標記點的打擊任務。為簡化無人機和任務點，仿真模擬均以質點的形式表現。

實驗初始化狀態如圖3所示，無人機初始時均勻分布在Y=1水平軸線上；任務目標點隨機分布在二維地面區域，為方便對應識別，其中三角形表示打擊任務點，正方形表示任務偵察點。無人機初始參數如表1所示，其中無人機類型為1表示該無人機為偵察無人機，類型為2表示打擊型無人機。任務點參數如表2所示，其中包含任務點的打擊價值，打擊需求、偵察需求、威脅等級等信息。

表1 無人機狀態初始信息表

表2 任務點初始狀態信息表

圖3 實驗環境初始化狀態表

3.2 仿真結果與分析

首先對傳統合同網算法對無人機協同任務分配情況進行仿真模擬，二維實驗場景如圖4所示，從圖4左上小圖可以看出V1無人機的當前任務集狀態為空，處于資源閑置狀態，無人機資源沒有被充分利用，路程代價明顯較高，整個系統資源分配明顯不均衡狀態。

如圖4右上小圖所示，是利用改進合同算法對無人機協同任務進行分配的結果，可以看出無人機V1現在已經申請到任務集，在考慮成本代價、威脅代價、路徑代價和執行任務收益等情況下實現整體任務分配均衡，其中表3較好說明了任務集分配具體情況。

表3 任務分配集表

如圖4中左下小圖所示，模擬無人機故障情況下的任務分配情況，假定偵察型和攻擊型無人機中各有一臺損壞，分別是V1、V2無人機，此刻無人機V1已經執行完任務T4，無人機V2還未開始執行任務，由于突發故障，這兩架無人機將會把剩下任務拍賣出去，由剩下的無人機競拍，產生一輪新的任務重分配。通過改進合同網算法，系統及時響應并快速進行一輪任務重分配，考慮無人機負載、開銷代價以及任務優先程度，使得任務承載更加均衡，分配結果如圖4中右下小圖所示。

圖4 實驗仿真結果圖集

為了驗證上訴分配結果的有效性，進行了多次模擬仿真，分配效能和時間統計如表4所示，其中n表示當前是第幾次模擬仿真，e表示當次模擬仿真整體效能，t表示當次仿真模擬所用時間。

表4 整體效能和運行時間統計表

通過對表4分析可以得到，傳統合同網算法的整體效能平均值在13.82，任務分配平均收斂時間需要0.54s。而改進合同網算法的整體效能要高很多，其整體效能平均值在20.34，算法平均收斂時間比較穩定，需要0.44s。綜上所述，說明基于改進合同網算法的任務分配整體效能有明顯提升，在增加多個影響指標后，其算法執行時間依舊保持穩定，且比傳統合同網算法收斂更快，可以說明改進合同網算法能夠很好地對分布式任務分配模型進行求解，提高無人機資源利用率，優化無人機全局負載情況，整體效能較高，具有較好的擴展性和適用性。

4 結語

任務分配問題是多無人機任務規劃的關鍵問題之一，且分布式任務分配是一個重要的技術發展趨勢。本文將無人機視為具有一定自主決策能力的智能體，并對傳統合同網算法進行優化，考慮更多的戰場影響指標，例如成本代價、開銷代價、威脅代價以及任務優先級等，構建更加符合實際作戰需求的任務分配模型，設定合理的約束條件，引入負載均衡機制，增加任務買賣和任務交換環節，使得整體效能更高，同時該方法能進行實時任務分配，增強了無人機在復雜戰場中的動態適應性。仿真結果表明，相比于傳統合同網算法，基于改進合同網算法的任務分配方法具有較好的時間效率和分配效果，且整體效能高，能夠有效應對突發情況并實時進行任務重分配，更加符合當前多無人機協同作戰的特點和實際任務的需求。由于算法收斂時間一定程度上與計算機硬件性能存在一定關系，實驗中的收斂時間會隨著計算機性能不同而有所不同，下一步將會增大任務分配規模同時考慮目標動態性等問題，讓仿真模擬更逼近實際作戰任務想定。