基于一致性群組算法的多無人機自主協(xié)同任務分配

馬云紅，劉云昊，楊譽喬，王鼎涵，張 健

（1.西北工業(yè)大學，西安 710072；2.北京航空航天大學，北京 100191）

1 引 言

隨著無人機的輕量化、智能化發(fā)展，無人機在各個領域發(fā)揮越來越重要的作用[1-2]，凸顯了無人機智能化的優(yōu)勢，多無人機自主協(xié)同執(zhí)行多任務成為可能。同時，隨著無人機的作用得到不斷的開發(fā)和拓展，無人機的協(xié)同任務分配逐步由單無人機執(zhí)行單任務，轉變?yōu)閱螣o人機執(zhí)行多任務，再到多無人機執(zhí)行單任務的任務聯(lián)盟任務分配問題。即多無人機需要適時組成小的“任務聯(lián)盟”合作完成一個復雜的任務。例如，在進行大宗貨物搬運或者危險環(huán)境的救援等活動時，需要不止一架無人機執(zhí)行任務。這種依靠多無人機自主組隊解決大型復雜任務的需求在現(xiàn)代化空戰(zhàn)中更為迫切[3]。因此，對于多無人機能夠自主協(xié)同完成不同類型不同數(shù)量任務的任務分配問題研究具有重要意義。

無人機任務分配通常是指一定的任務集合由多架無人機執(zhí)行，根據(jù)任務的屬性和任務的位置確定最佳的任務分配方案，使得無人機執(zhí)行完成所有任務的時間最短或者收益最大。任務分配本質上是一種組合優(yōu)化問題，可以用一般的解決NP-hard 問題的方法求解。文獻[4-5]采用啟發(fā)式空間搜索方法求解車輛完成多個任務的最優(yōu)任務路徑問題的解。文獻[6]采用了蟻群算法進行這類問題的求解。文獻[7]采用了遺傳算法進行動態(tài)最優(yōu)任務路徑優(yōu)化。文獻[8-9]將遺傳算法擴展到多個無人機多任務分配問題求解。文獻[10]采用改進NSGA 算法實現(xiàn)無人機聯(lián)盟多任務的任務分配。然而，現(xiàn)有的這些算法，主要解決了靜態(tài)規(guī)劃，依賴對全局信息的獲取。而自主任務規(guī)劃要求能夠根據(jù)動態(tài)變化的場景進行實時規(guī)劃。分散算法是無人機之間基于實時信息共享的實時任務分配，可以應對實時變化的場景，成為多無人機自主協(xié)同任務分配的重要手段。文獻[11]基于分散合作優(yōu)化解決了任務目標函數(shù)獨立的凸優(yōu)化問題，但僅適用于具有連續(xù)決策變量的凸優(yōu)化函數(shù)。文獻[12]采用基于分散化計算的匈牙利任務分配算法，可以解決目標函數(shù)獨立的任務分配。這些算法可以在通信可靠的前提下實現(xiàn)基于中央集中控制中心的優(yōu)化計算。但是，對于多無人機自主協(xié)同完成多任務來說，無人機通常處于敵方控制區(qū)域，沒有傳統(tǒng)通信基礎設施進行通信輔助，特別是如果在空域或水下環(huán)境執(zhí)行任務時，甚至沒有通用基礎通信條件，不能保證所有信息同時共享。為此需要設計基于無人機之間的信息共享的分散算法，提升無人機自主任務分配的適用性和魯棒性，也降低對集中節(jié)點的指揮的依賴。文獻[13]引入的基于一致性的拍賣算法（Consensus Based Bundle Algorithm，CBBA）算法，是一種基于協(xié)商機制的一致性規(guī)劃方法，用于求解車輛完成運輸任務的車輛路徑問題。文獻[14]基于拓展的CBBA 算法進行了軌裝配航天器的任務分配研究。文獻[15]采用合同網算法進行了多任務的分配。文獻[16]提出部分重規(guī)劃思想，結合合同競拍實現(xiàn)了實時動態(tài)任務分配。這些文獻完成了一致性算法下的任務分配。但是，在多無人機協(xié)同執(zhí)行多任務的情形下，有些任務是有時間約束的，即必須在制定的時間內完成，否則失去作戰(zhàn)價值。這類任務分配問題就是帶有時間窗約束的任務分配問題。文獻[17]討論了帶時間窗約束的郵遞員路徑問題。采用的是把具有時間約束的客戶和沒有時間約束的客戶先聚類后求解的方法，再基于多目標優(yōu)化的思想實現(xiàn)了帶有時間限制的最佳郵遞路徑問題。文獻[18]提出了一種聚類第一路線和第二路線的算法，即根據(jù)目標的時間窗口對目標進行聚類，然后為每個聚類生成運輸問題，再用單純形算法逐步解決這些運輸問題，可以在短時間內找到高質量的解決方案。但這個算法還是一種集中式優(yōu)化，需要所有信息共享，而且也不能解決多無人機協(xié)同同時到達任務的時間約束問題。本文基于目前的研究基礎，對不同類型的任務分配問題，采用基于合同競拍的機制實現(xiàn)實時任務分配，并重點解決帶時間窗限制的多無人機自主協(xié)同執(zhí)行一個復雜任務分配問題的求解。

2 任務分配問題模型

2.1 單無人機單任務的任務分配模型

為了建立一般化的多無人機多任務分配模型，首先分析最簡單的任務分配模型–單無人機執(zhí)行單任務的任務分配模型。對于單無人機執(zhí)行單任務的任務分配問題，是指限定多無人機中的每個無人機只能執(zhí)行一個任務。單無人機執(zhí)行單任務的任務分配的目的是將Nt個任務分配給Na個無人機，保證目標函數(shù)達到最優(yōu)的任務分配方案，其對應的數(shù)學模型如下：

其中，xij表示第i個無人機執(zhí)行第j個任務，xij= 1表示第i個無人機執(zhí)行第j個任務，xij=0表示第i個無人機不執(zhí)行第j個任務；c ij表示第i個無人機執(zhí)行第j個任務的收益。式（2）表示一個任務只能由一個無人機執(zhí)行的約束，式（3）表示一個無人機只能執(zhí)行一個任務的約束。

2.2 單無人機多任務的任務分配模型

單無人機執(zhí)行多任務的任務分配問題，是指多無人機中的每個無人機可以執(zhí)行多個任務，其具體任務數(shù)量受無人機能力、任務執(zhí)行難度等條件限制。單無人機對多任務分配的目標是將Nt個任務分配給Na個無人機。其中，每個無人機可以分配Lt的任務數(shù)量，并使任務收益最大。相應的數(shù)學模型如下：

其中，式(5)表示無人機最多執(zhí)行Lt個任務。式(6)表示每個任務由一架無人機執(zhí)行，式(7)保證所有任務都要執(zhí)行。

2.3 多無人機聯(lián)盟協(xié)同執(zhí)行多任務的任務分配模型

將需要兩架及以上無人機合作完成一個任務的分配，定義為無人機聯(lián)盟協(xié)同執(zhí)行多任務的分配問題，而同時參與協(xié)同執(zhí)行一個任務的無人機小組定義為任務聯(lián)盟。

因此，多無人機任務聯(lián)盟協(xié)同執(zhí)行任務的分配問題，是指每個無人機可以執(zhí)行多個任務，同時有些任務又要求多架無人機組成聯(lián)盟共同完成的復雜情況。任務聯(lián)盟的成員數(shù)量定義為聯(lián)盟規(guī)模。任務聯(lián)盟規(guī)模一般有定值和最小值兩種情況，如大宗物品搬運任務的規(guī)模一般為某個定值，即需要多少無人機完成搬運，集中救援則可以設置為最小值，即最少需要多少無人機參與救援，也可以設定為定值，即指定固定的無人機數(shù)量完成特定的任務。本文的任務聯(lián)盟的規(guī)模采用定值。即任務聯(lián)盟任務分配是將Nt個任務分配給Na個代理無人機，其中的復雜任務需要特定規(guī)模的無人機聯(lián)盟完成。在任務聯(lián)盟協(xié)同完成任務的前提下，以最優(yōu)的資源組合完成所有的任務。記無人機可以分配Lt的任務數(shù)量，無人機聯(lián)盟規(guī)模設定為Lj，相應的數(shù)學模型表示為

其中，式（9）是對無人機最多執(zhí)行Lt個任務的約束。式（10）表示復雜任務至少需要有Lj個無人機完成。式（11）約定所有任務都要完成。式（12）約定無人機i執(zhí)行任務j的時刻位于任務j的執(zhí)行時間區(qū)間。Tij-start表示無人機i執(zhí)行任務j的開始時間，Tjmin為任務j的可執(zhí)行的開始時間，Tjmax是任務j的可執(zhí)行的結束時間。

3 任務分配算法

3.1 基于一致性的拍賣算法原理

本文采用基于一致性的競拍算法實現(xiàn)任務分配，即將任務作為待拍賣的貨品，無人機根據(jù)自身完成任務的能力（到達任務的時間）對任務進行競價，最后以所有無人機的收益綜合最大達成拍賣，從而實現(xiàn)任務分配。常規(guī)的拍賣活動是一種集中式的控制機制，通常由拍賣師負責控制拍賣流程，是一種集中式的任務分配。本文的任務分配采用競拍機制，但是拍賣結果是由所有競拍者通過信息共享和通信協(xié)商達成一致實現(xiàn)的，即競拍過程不需要控制中心進行計算并發(fā)放指令，而是完全依靠無人機借助通信網絡進行信息交互，沖突消解，最終完成一致性和協(xié)調，得到最佳任務分配。這是一種分散式的任務分配，可以保證無人機在自帶的通信設備情形下自主協(xié)商，完成任務分配。

3.2 單無人機單任務的任務分配的基于競拍的一致性算法

3.2.1 變量定義

定義任務分配問題為Na個無人機執(zhí)行Nt個任務，則N a×Nt的矩陣表示任務分配結果，其元素為xij，xij= 1，表示無人機i執(zhí)行任務j，xij=0表示無人機i不執(zhí)行任務j。定義xi為狀態(tài)向量，其長度為Nt，Nt是任務數(shù)量，xi記錄無人機i認為當前自己獲得的任務狀態(tài)。記yi為勝者投標價格向量，長度為Nt，記錄勝者的投標價格。ytj記錄無人機i認為的任務j的勝者投標價格。ci稱為出價向量，長度為Nt，記錄無人機i對所有任務的出價。cij表示無人機i對任務j的出價，如果不出價則cij= 0。hi稱為有效出價向量，長度為Nt，記錄無人機i的每個任務出價是否有效。如果cij＞yij，即無人機i的出價大于目前它認為對任務j的最高出價，則hij= 1，否則hij= 0。Ji是代理無人機i的有效投標任務，代表無人機i所有的有效出價中最高的一個對應的任務。g為N a×Na的通信矩陣，gik= 1表示無人機i可以與無人機k通信，gik= 0則表示無人機i不能與無人機k通信。zi是勝者向量，長度為Nt，記錄每個任務的競標成功無人機編號，zij是無人機i收到的投標信息中對任務i的最高投標價格對應的無人機編號，I為無人機集合，J為任務集合。

3.2.2 基于競拍的一致性算法流程

基于以上定義，基于競拍的一致性算法（Consensus Based Auction Algorithm，CBAA）流程如下所述。CBAA 算法分為拍賣階段和一致性階段。第一階段是拍賣階段。如果無人機i沒有任務，則進入拍賣環(huán)節(jié)，否則直接進入一致性階段。在拍賣階段，每一個無人機i根據(jù)自身完成任務的“能力”對任務j進行投標競價。無人機i根據(jù)上一輪(t- 1)的拍賣結果和本輪(t)自己的出價情況更新兩個向量xi和yi。第t輪次拍賣階段的偽代碼如下：

CBAA 算法的第二階段是一致性階段。每一個無人機i都將它最新的列表yi傳送給它通信可達的鄰近無人機k，同時從代理無人機k獲取對方的yk，通過協(xié)商協(xié)議達成一致，消除沖突。協(xié)商原則包括：如果一個無人機發(fā)現(xiàn)對于某一個任務其他無人機的出價高于自己，那么該無人機放棄這個任務；如果兩個無人機發(fā)現(xiàn)對于某一個任務的出價相同，則編號小的無人機獲勝，編號大的無人機放棄這個任務。為了解決異步通信過程中的通信不同步問題，CBAA 引入時間印記s標識數(shù)據(jù)時戳，這樣每輪的數(shù)據(jù)僅通信一次，降低通信損耗。一致性階段的偽代碼如下：

3.3 基于CBBA 的單無人機執(zhí)行多任務的任務分配

在無人機可以執(zhí)行多個任務的情形下，仍然采用基于一致性協(xié)商的合同競拍機制進行任務分配。將每個無人機執(zhí)行的任務表示成一個任務序列，稱為拍賣包。每個拍賣包標明了無人機執(zhí)行多個任務的順序。競價時，增加一個未被執(zhí)行的任務進入任何一架無人機的序列。即CBBA 算法。CBBA 算法的第一階段是拍賣包構建階段。即每個無人機執(zhí)行的所有任務形成一個拍賣包，拍賣包中的任務順序就是無人機執(zhí)行任務的路徑。一個無人機i確定對任務Ji投標后，將該任務Ji插入其先前路徑中某一處，則無人機i的拍賣包就相應地產生一個收益值。如果這個收益值大于當前的贏家，無人機i將把任務Ji添加到它的拍賣包中。一直重復這個過程，直到無人機i不能再添加任務到它的路徑上。最后，無人機i更新它認為的中標向量zi和中標價格向量yi，進入下一輪競標。CBBA 算法的拍賣包構建階段偽代碼如下：

CBBA 算法的第二階段是一致性階段。每一個無人機i都將它的最新向量表zi，yi和si傳達給所有可以通信的無人機，并根據(jù)它們各自的拍賣價格進行協(xié)商和沖突消解。一致性過程中的三個響應行為“更新”yij=ykj,zij=zkj，“重置”yij=0,zij=?和“保留”yij=yij,zij=zij。這個沖突消解的過程中，如果兩個無人機i和k對位于i拍賣包中的特定任務j有沖突，則失敗的無人機（假設是k）不僅需要重置任務j，還需要重置競拍包內j之后的所有任務，確保后續(xù)CBBA 拍賣包在建立階段的競拍方案的合理性。如果兩個無人機發(fā)現(xiàn)對于某一個任務的出價相同，約定編號小的無人機的獲勝。一致性階段協(xié)議一致性沖突消解原則如表1 所示。根據(jù)表1 的沖突消解原則協(xié)商達成本輪一致，形成本輪競價結果。

表1 一致性階段沖突消解原則Table 1 Principles of conflict resolution

3.4 基于CBGA 的任務聯(lián)盟任務分配算法

基于與CBBA 算法類似的拍賣包構建過程和一致性階段過程，本文提出CBGA 算法，完成任務聯(lián)盟任務分配問題的求解。定義N a×Nt的矩陣xi，如果無人機i認為無人機k獲得了任務j，那么xikj= 1，否則xikj= 0。

CBGA 算法的拍賣包構建階段偽代碼如下：

Procedure Bundle（xi(t-1),yi(t-1),bi(t-1),pi(t-1),zi(t-1)）

3.5 時間窗限制的群組拍賣算法（CBGA-TW）

3.5.1 CBGA 算法的不足

CBGA 算法可以實現(xiàn)任務聯(lián)盟完成復雜任務的任務分配，但是沒有考慮到復雜任務合作執(zhí)行的時間問題，如大宗貨物的搬運和危險環(huán)境的救援需要多架無人機同時執(zhí)行搬運任務，無人機協(xié)同打擊也需要同時到達。

3.5.2 基于時間窗的CBGA-TW 算法

為了實現(xiàn)任務協(xié)同的同時到達要求，本文對CBGA 算法進行了改進，提出了一種有時間窗限制的CBGA-TW 算法。算法通過引入時間窗限制，解決合作執(zhí)行任務的同時到達時間約束問題。

CBGA-TW 算法加入了對協(xié)同同時到達的時間窗約束，設計了能夠體現(xiàn)時間窗約束的收益值，通過收益值的競價，解決滿足同時到達的時間約束問題。

在CBGA-TW 算法的第一階段，如果是Lj=1的簡單任務，則采取CBBA 算法進行解算。對于任務聯(lián)盟任務，如果該任務尚未分配給足夠多的無人機或者無人機i的出價高于現(xiàn)在投標價格中的最小值，則認為是對于該任務的有效出價。CBGA-TW 算法的出價cij的表達式設計為

其中，Tij-start表示無人機i執(zhí)行任務j的開始時間，Tjmin為任務j的可執(zhí)行的開始時間，Tjmax是任務j的可執(zhí)行的結束時間，e-λΔT是對時間的懲罰項，只有能在規(guī)定時間內執(zhí)行任務的無人機才能獲得收益，即如果無人機能夠執(zhí)行該任務的時間大于任務的結束時間，則收益值為0，如果無人機能夠執(zhí)行的時間位于任務的執(zhí)行時間窗內，則加入一個獎懲因子，時間差越小，收益值越大。保證滿足帶時間窗限制的任務獲得優(yōu)先分配權，也滿足了時間窗的約束。

這里特別指出，每個無人機的收益值包括任務自身的價值以及由于任務時間滿足時間窗約束的獎懲系數(shù)。而無人機對任務的出價是基于無人機到達任務的飛行代價或者飛行距離計算的。無人機到達目標的飛行距離越短，飛行時間就越短，則可以給出的出價越高。這表示在計算無人機的任務收益時考慮了執(zhí)行任務的時間，但是沒有考慮環(huán)境中有障礙情形的避障飛行的距離，僅采用到達任務的直線距離的飛行時間。收益函數(shù)的收益表達式加上時間窗約束的獎懲因子，可以針對時間窗滿足條件進行任務估價，如果超過任務執(zhí)行時間的收益值為 0。通過收益函數(shù)的評價限定了無人機聯(lián)盟協(xié)同完成任務的同時達到。因此，基于這個收益函數(shù)的出價再經過一致性競拍，可以得到最快時間完成所有任務的任務分配方案，同時保證需要多架無人機協(xié)同完成的任務的可靠執(zhí)行。

4 基于CBGA-TW 任務分配仿真

包含帶時間窗約束的多無人機任務聯(lián)盟任務分配是本文綜合考慮多種約束的復雜任務分配問題，以這類問題的任務分配進行本文的算法仿真驗證。設定仿真任務場景如下：多架異構型無人機執(zhí)行不同類型的任務分配。即6 架無人機完成12 個任務，其中Ⅰ型無人機3 架，Ⅱ型無人機代理3 架；Ⅰ型任務6 項，每個任務需要5 s 的執(zhí)行時間，Ⅱ型任務6 項，每個任務需要10 s 的執(zhí)行時間。無人機型號和它能夠執(zhí)行的任務匹配，即Ⅰ型無人機可以執(zhí)行Ⅰ型任務，Ⅱ型無人機可以執(zhí)行Ⅱ型任務。其中任務2 和任務7 設定為需要兩架無人機共同完成的任務,即L2=L7= 2,任務2 和任務7 的時間窗都設置為[5,15]。將無人機執(zhí)行任務的時間（到達任務時間）作為出價和收益標準。參與作戰(zhàn)的無人機之間都可以通信，即

針對上述任務場景進行CBGA-TW 算法仿真,采用Matlab R2016b 軟件作為仿真計算平臺,并假設所有無人機間都能通信并正常收發(fā)數(shù)據(jù)。

仿真結果如圖1 和圖2 所示。

圖1 CBGA-TW 任務分配結果Fig.1 Task allocation results with CBGA-TW

圖1 中Δ表示無人機的位置，×表示任務位置，實線表示規(guī)劃后的代理無人機的路徑。不同的顏色表示不同的無人機類型和任務類型，相同顏色進行無人機和任務匹配。

仿真結果顯示，經過約0.224937 s，11 輪的CBGA-TW 解算之后，所有任務得到最佳競價方案，得到該場景下的任務分配結果。執(zhí)行這組任務的總時間，即多無人機完成最后一個任務的時間為39.354 s，得到的總收益為749.6437。

通過圖1 和圖2 可以看到，任務2 被同時分配給了無人機1 和無人機2，任務7 被分配給了無人機4 和無人機5，兩個任務都在時間窗限制內執(zhí)行，滿足了時間窗約束并達到同步，實現(xiàn)了多無人機協(xié)同執(zhí)行一個復雜任務?？梢哉f明CBGA-TW 算法能夠有效解決帶時間約束的任務聯(lián)盟的任務分配問題。

圖2 CBGA-TW 任務分配結果甘特圖Fig.2 Gantt chart of CBGA-TW task allocation result

可以發(fā)現(xiàn)，采用CBGA-TW 算法的多無人機聯(lián)盟任務分配是基于時間窗限制的群組拍賣算法，通過時間窗限制條件的加入，保證了任務的同時執(zhí)行。依靠無人機之間通信和一致協(xié)商，可以達到最終的協(xié)同任務執(zhí)行方案。整個過程不需要集中控制中心或人工參與，提升了多無人機自主任務分配、自主協(xié)同作戰(zhàn)的能力。同時，本文提到的單無人機執(zhí)行單任務的無人機任務分配和單無人機執(zhí)行多任務的任務分配，也是基于無人機之間的通信協(xié)商的一致性競拍協(xié)商機制完成的，也是自主任務分配。

5 結 論

本文進行了一致性群算法的多無人機協(xié)同作戰(zhàn)的自主任務分配，包括單無人機執(zhí)行單任務的多無人機任務分配、單無人機執(zhí)行多任務的任務分配，以及無人機任務聯(lián)盟的任務分配。本文提出了基于時間窗限制的多無人機一致性群組拍賣算法CBGA-TW 算法，解決了在時間約束下的無人機聯(lián)盟同時到達并執(zhí)行任務的任務分配的問題求解。本文仿真驗證了算法的有效性。同時說明基于信息共享的無集中控制的任務分配，可以完成多無人機自主任務聯(lián)盟任務分配，提升了多無人機自主任務分配、自主協(xié)同作戰(zhàn)的能力。