李瑞琳，崔 巍，馮彥翔，楊宜康

(西安交通大學自動化科學與工程學院，陜西 西安 710049)

0 引言

由于具有靈活性強、裝配便捷、成本消耗低等優(yōu)勢[1],無人機已廣泛應(yīng)用在搜救、交通巡查、遙感測繪等領(lǐng)域[2]。單架無人機經(jīng)常無法保證任務(wù)的高效執(zhí)行,因此需要多架無人機組成無人集群聯(lián)合或協(xié)同執(zhí)行任務(wù)。無人集群協(xié)同任務(wù)分配是指綜合考慮任務(wù)特點、平臺性能和任務(wù)環(huán)境,以優(yōu)化目標為牽引,將任務(wù)分配給多架無人機,使得整個系統(tǒng)執(zhí)行任務(wù)消耗的成本最低或效率最高[3]。近年來,無人集群任務(wù)分配問題已成為無人集群協(xié)同規(guī)劃領(lǐng)域亟需解決的關(guān)鍵問題[4]。

無人集群任務(wù)分配模型一般分為單一任務(wù)模型和多任務(wù)模型。單一任務(wù)模型包括多旅行商問題模型[5]、車輛路徑問題模型[6]等;多任務(wù)模型有網(wǎng)絡(luò)流模型和混合整數(shù)線性規(guī)劃模型[7]等。單任務(wù)模型中各個任務(wù)間的模型空間相互獨立,而多任務(wù)模型中多個任務(wù)間的模型空間是共享的,但在實際場景下,可能產(chǎn)生蹺蹺板現(xiàn)象,即部分任務(wù)效果提升,但另一部分任務(wù)效果下降。

無人集群任務(wù)分配方法分為集中式和分布式兩種思路。集中式任務(wù)分配算法中由中央處理單元整合全局信息做出決策[8],常見的集中式方法有最優(yōu)化方法[8-9]和元啟發(fā)式算法[10-17]。其中,文獻[14]提出一種遺傳-蟻群混合算法并對偵察任務(wù)分配問題進行求解;文獻[15]提出了基于粒子收斂程度的自適應(yīng)慣性權(quán)重與量子門變異算子,改造了標準量粒子群算法;文獻[16]引入二進制矩陣與自適應(yīng)慣性因子對偵察任務(wù)進行分配求解。集中式方法結(jié)構(gòu)簡單,但速度較慢,魯棒性差。

分布式任務(wù)分配方法通過各無人機之間的交流、協(xié)商、決策,協(xié)同分配任務(wù),因此分布式方法靈活性強,對單點故障具有一定魯棒性,能降低安全風險和成本。分布式方法有拍賣算法[18-20]、合同網(wǎng)算法及其相應(yīng)的改進算法(extend contract net protocol, ECNP)等[21-23]。其中,文獻[19]提出一致性聯(lián)盟包算法(consensus-based bundle algorithm, CBBA),采用基于市場的決策策略作為分配任務(wù)選擇機制,并使用基于局部通信的共識作為沖突消解機制;文獻[22]對CBBA算法進行了改進,考慮了異步通信、時間敏感和動態(tài)的任務(wù)、任務(wù)空間中的障礙和干擾等問題。文獻[24]提出性能影響算法(performance impact algorithm, PI)來解決無人集群任務(wù)分配問題,優(yōu)化利益問題的總體目標。相比于CBBA算法中每個無人機致力于降低其局部成本,PI算法旨在優(yōu)化整個系統(tǒng)的總體成本。

同集中式方法相比,分布式任務(wù)分配算法依賴智能體之間的交流通信質(zhì)量,很少考慮真實環(huán)境中的一些要素。例如,文獻[25]考慮了無人機飛行能力、任務(wù)執(zhí)行時間窗等約束條件,但忽略了任務(wù)執(zhí)行時間長度的約束;文獻[26]提出了一種“閉環(huán)CBBA”,考慮任務(wù)完成后無人機返回起飛基地,但忽略了任務(wù)分配過程中的各項約束;文獻[27]基于CBBA框架提出了CBBATW算法,對任務(wù)有效時間窗、車輛燃油成本進行了適當?shù)奶幚?但在任務(wù)時間窗約束較嚴格時,容易出現(xiàn)任務(wù)無法完全分配問題;文獻[28]對PI算法引入動態(tài)重調(diào)度模塊和Softmax函數(shù)以應(yīng)對環(huán)境的動態(tài)變化,但沒有考慮到任務(wù)的時間窗約束等條件。

針對上述問題,文中基于分布式PI算法框架,考慮具有時間窗約束的無人集群協(xié)同任務(wù)分配問題,提出一種以任務(wù)平均完成時間最小為優(yōu)化目標的分布式任務(wù)分配算法(distributed allocation with time windows,DATW)。文中的時間窗約束屬于“硬約束”,即任務(wù)必須在時間窗內(nèi)被執(zhí)行,否則不予分配。整個算法在所有無人機上并行運行,通過反復(fù)執(zhí)行任務(wù)添加、沖突消解和任務(wù)再分配三個階段,得到滿足時間窗約束的任務(wù)分配結(jié)果。最后進行不同規(guī)模的仿真實驗,驗證所提算法的可行性和實用性。研究的主要創(chuàng)新點為:

1) 將任務(wù)的時間窗約束嵌入到PI分布式算法架構(gòu)中,使得被分配的任務(wù)均滿足時間窗約束。

2) 同傳統(tǒng)PI算法相比,針對因不滿足時間窗約束而無法分配的任務(wù),提出新的第三個階段:以無人機局部時間成本最小為優(yōu)化目標的任務(wù)再分配策略。由此任務(wù)再分配階段提高了13.76%的任務(wù)分配成功率。

3) 與CBBATW算法[27]相比,提出的DATW算法的任務(wù)分配成功率平均值提高了21.94%,任務(wù)平均完成時間降低了24.25 s,所以性能更好。

4) 相比于ECNP算法[23],DATW算法不受無人機通信拓撲變化的影響,在各種拓撲下都能進行充分交流,適應(yīng)性更強。

1 問題描述

本研究考慮時間窗約束的無人集群協(xié)同任務(wù)分配問題。給定m個任務(wù)Nt={t1,t2, …,tm}和n架無人機Nu={u1,u2, …,un},且n>m。任務(wù)tj∈Nt由二元組表示,其中l(wèi)oc(tj)=(xj,yj,zj)是tj三維坐標,Dj是執(zhí)行任務(wù)tj所需時間;無人機ui∈Nu由表示,loc(ui)=(xi,yi,zi)是ui的初始位置坐標,vi表示飛行速度。無人機的動態(tài)情況改變會影響其飛行性能。因此,為了簡化計算,假設(shè)無人機ui的速度vi為一個常數(shù)。無人機之間通過局部鏈路進行通信,相應(yīng)的通信拓撲網(wǎng)絡(luò)可用n×n維的對稱鄰接矩陣G表示,其元素Gih=1表示無人機ui和uh互為鄰近無人機,彼此可以交換共享信息;Gih=0表示ui和uh不能通信。

在實際情況下,無人集群任務(wù)分配結(jié)果會受到來自于無人機和任務(wù)兩個方面因素的影響。

1) 無人機因素

由于不同無人機具有不同速度,其執(zhí)行任務(wù)的時間成本也不同。令tj∈Pi,無人機ui開始執(zhí)行任務(wù)tj的時間Tj(Pi)可表示為:

(1)

式中:tk表示路徑Pi中tj的前一個任務(wù);dis(·)表示兩個坐標之間的歐幾里得距離。

無人機ui完成任務(wù)tj所需的“時間成本”Fj(Pi)可表示為:

Fj(Pi)=Tj(Pi)+Dj

(2)

無人機執(zhí)行任務(wù)能力受限影響可表示為[24]:

|Pi|≤Li,?ui∈Nu

(3)

式中:|Pi|表示Pi中的任務(wù)數(shù);Li表示無人機ui的執(zhí)行任務(wù)數(shù)上限。

2) 任務(wù)因素

任務(wù)的開始執(zhí)行時間必須滿足時間窗“硬”約束。令任務(wù)tj必須不早于時間Tj_start執(zhí)行,不晚于時間Tj_end執(zhí)行,即:

Tj(Pi)∈[Tj_start,Tj_end]

(4)

在任務(wù)分配問題中,最小化原則可以分為MiniSum和MiniMax。MiniSum準則一般用于最小化所有無人機的資源總消耗或完成每個任務(wù)的平均成本,而MiniMax則是最小化成本最高的無人機的成本。對于無等待分配問題,由于任務(wù)時間窗約束的存在,意味著一個無人機的任務(wù)分配情況會改變另一個無人機的可用選擇,每個無人機的時間成本會受到其他無人機的影響。此時,MiniMax準則難以反映不同無人機之間的關(guān)系,而MiniSum準則可以在無等待任務(wù)分配上獲得更好的效果,因此文中選擇MiniSum準則。

在滿足上述無人機和任務(wù)約束的前提下,以任務(wù)的平均時間成本為優(yōu)化目標,研究無人集群協(xié)同任務(wù)分配問題,相應(yīng)的數(shù)學模型為:

(5)

s.t.Pi∩Pj=?,?i≠j

(6)

|Pi|≤Li,?ui∈Nu

(7)

Tj_start≤Tj(Pi)≤Tj_end,?tj∈Pi,?ui∈Nu

(8)

其中,式(5)為目標函數(shù),表示任務(wù)的平均時間成本最小;式(6)規(guī)定每個任務(wù)只能指派給一個無人機,且不能重復(fù)分配[24];式(7)規(guī)定無人機ui一次執(zhí)行任務(wù)數(shù)不能超過Li;式(8)引入了一個非凸約束,規(guī)定任務(wù)的開始執(zhí)行時間滿足時間窗約束。全局優(yōu)化目標是非凸的,它由無人機的任務(wù)列表、任務(wù)坐標和每個無人機的飛行速度共同決定。因此所研究的多無人機任務(wù)分配問題是NP-hard問題[29-30],無法通過簡單計算直接獲得全局最優(yōu)解。

2 無人集群分布式任務(wù)分配算法

文中提出一種考慮時間窗約束的分布式任務(wù)分配算法(DATW)。所提出的DATW算法在所有無人機上并行運行。無人機之間通過局部通信拓撲交換信息,記錄所有任務(wù)的分配結(jié)果和任務(wù)增益等信息。算法主要包括任務(wù)添加、沖突消解和任務(wù)再分配三個階段。算法先循環(huán)迭代執(zhí)行前兩個階段,當所有無人機記錄的任務(wù)分配對象列表一致且在一段時間內(nèi)不發(fā)改變時,開始執(zhí)行第三個階段,繼續(xù)將一些未分配的任務(wù)分給無人機。經(jīng)過多輪迭代后,最終得到任務(wù)平均時間成本最小且滿足時間窗約束的無沖突任務(wù)分配結(jié)果。

首先,定義無人機ui記錄的信息列表。

1) 任務(wù)分配對象列表

Zi=[Zi1,Zi2, … ,Zim]T表示無人機ui記錄的所有任務(wù)的分配對象,分量Zij=k表示ui認為任務(wù)tj被分配給了uk。如果ui認為tj未分配,則Zij趨近無窮大,即Zij→∞。

2) 任務(wù)增益列表

Qi=[Qi1,Qi2, … ,Qim]T表示無人機ui記錄的所有任務(wù)的增益。當Zij=k時,Qij等于將任務(wù)tj從Pk中刪除后,uk的時間成本的減少量。注意,如果Zij→∞,則令Qij→∞。

3) 任務(wù)開始執(zhí)行時間列表

Ti=[Ti1,Ti2, … ,Tim]T表示無人機ui記錄的所有任務(wù)的開始執(zhí)行時間。當Zij=k時,Tij反映uk開始執(zhí)行任務(wù)tj的時間。如果Zij→∞,則令Tij→∞。

4) 時間戳列表

si=[si1,si2, … ,sin]T記錄無人機ui從無人機uh獲得最新信息的時刻,分量sih可表示為[19]:

(9)

式中τr表示ui接收uh信息的時刻。

初始時,令Pi=?,Zij→∞,Qij→∞,?tj。無人機ui與鄰近無人機在通信中互換上述四種信息。

2.1 任務(wù)添加階段

1) 任務(wù)增益

假設(shè)任務(wù)tj位于Pi中,令Pi?tj表示將tj從Pi中移除后剩余的任務(wù)序列,增益qij(Pi?tj)表示將tj從Pi刪除后無人機ui時間成本的變化量,按式(10)計算[24]:

(10)

增益qij(Pi?tj)反應(yīng)了tj對于ui當前時間成本的“貢獻值”。當tj?Pi時,令qij(Pi?tj)→∞。

2) 任務(wù)邊際增益

(11)

在任務(wù)添加階段給無人機ui分配任務(wù)時,只有當任務(wù)tj同時滿足下面兩個條件,它才會被允許插入到Pi中。

(12)

圖1 ui執(zhí)行的任務(wù)添加過程Fig.1 The process of adding tasks performed by ui

2.2 沖突消解階段

若算法在所有無人機上并行執(zhí)行,同一項任務(wù)可能會同時分配給多個無人機,產(chǎn)生分配沖突。因此,為獲得無沖突的任務(wù)分配結(jié)果,還需執(zhí)行沖突消解過程。在這個階段無人機反復(fù)迭代執(zhí)行協(xié)商一致和任務(wù)刪除兩步驟,直到消除了所有沖突并且所有無人機的任務(wù)分配信息保持一致,達成全局共識,即Qi=Qh,?ui∈Nu,uh∈Nu且ui≠uh。

2.2.1 協(xié)商一致步驟

假設(shè)Gih=1,無人機ui與鄰近無人機uh通過局部通信拓撲進行信息交換,共享Zi和Zh、Qi和Qh、Ti和Th、si和sh,并按照一定的交流規(guī)則更新相應(yīng)信息。實際上,當無人機ui收到鄰近uh發(fā)來的信息后,會根據(jù)Zi和si來判斷接收到的信息是否為任務(wù)tj的最新信息,并以降低自身時間成本為目標,按照表1所示的交流規(guī)則決定是否更新自身存儲的信息Zi,Qi和Ti。表1共包含以下三種操作:

表1 無人機交流規(guī)則Table 1 UAV communication rule

1) 更新(update):Zij=Zhj,Qij=Qhj,Tij=Thj;

2) 保留(leave):不執(zhí)行任何操作;

3) 重置(reset):Zij→∞,Qij→∞,Tij→∞。

其中,默認操作為保留。此外,儲存在無人機ui上的時間戳si表示獲得信息的最新時間,因此ui每次接收信息后都需要按照式(9)更新si。

2.2.2 任務(wù)刪除步驟

利用局部通信網(wǎng)進行協(xié)商一致步驟后,無人機ui檢查當前任務(wù)路徑Pi,從中刪除集合A={tj∈Pi|Zij≠i}和集合B={tj∈Pi|Tj(Pi)Tj_end}中的任務(wù)。其中,A表示Zi和Pi不匹配的任務(wù)集合,B表示不符合時間窗約束的任務(wù)集合。

首先,無人機ui根據(jù)式(13),將能夠最大程度減小執(zhí)行時間成本的任務(wù)tk從Pi和A中同時移除。重復(fù)此過程,直到A中的所有任務(wù)都不再滿足(13)或A為空。

(13)

若上述過程結(jié)束后A≠?,將A中任務(wù)的執(zhí)行者重置為ui,即對于所有剩余任務(wù)tj∈A,令Zij=i。

然后,無人機ui檢查自身序列Pi,一旦存在任務(wù)tj∈Pi不滿足時間窗約束,則將tj從序列Pi中移除,并重置信息列表Zij→∞,Qij→∞,Tij→∞。無人機ui每移除一個任務(wù)tj,都需要重新計算Pi中各任務(wù)的開始執(zhí)行時間,判斷是否出現(xiàn)不符合時間窗約束的新任務(wù)。重復(fù)迭代執(zhí)行這個過程,直至Pi上的所有任務(wù)滿足時間窗約束。當任務(wù)刪除操作結(jié)束后,重新計算Pi中每個任務(wù)tj的增益Qij和任務(wù)開始時間Tij。

無人機ui重復(fù)執(zhí)行上述協(xié)商一致和任務(wù)刪除兩個步驟,當多輪迭代后任務(wù)分配結(jié)果不再發(fā)生改變,表明已實現(xiàn)無沖突任務(wù)分配且滿足時間窗約束,完成了沖突消解階段。可以由圖2來描述這個階段。

圖2 ui執(zhí)行的沖突消解階段Fig.2 Conflict resolution phase of ui

2.3 任務(wù)再分配階段

一般情況下,執(zhí)行前兩個階段后得到的任務(wù)分配結(jié)果能夠涵蓋所有任務(wù),但在時間窗約束較苛刻的情況下,可能有一些任務(wù)沒有被分配。令C表示前兩個階段后未分配的任務(wù)集合。為了使更多的任務(wù)在滿足時間窗約束的條件下被分配,還需對C中的任務(wù)執(zhí)行第三個階段——任務(wù)再分配。再分配階段包含任務(wù)添加和沖突消解兩步驟,只將C中的任務(wù)從無人機上移除或添加,對C之外已經(jīng)分配的任務(wù)不再進行操作。

2.3.1 任務(wù)添加步驟

為了避免出現(xiàn)任務(wù)被同一個無人機重復(fù)添加再刪除的操作,對無人機ui定義一個向量Mi。初始時令Mi[tj]=0,?tj∈C。若tj被ui添加到Pi,但因違反時間窗約束而又從Pi移出后,令Mi[tj]=1。

任務(wù)tj∈C只有滿足下述條件3和條件4才會被允許插入無人機ui的路徑Pi中的合適位置。

條件3:Zij≠i,Mi[tj]=0;

(14)

不同于式(12),本輪任務(wù)添加僅考慮了任務(wù)對于無人機的邊際增益,將式(14)中的任務(wù)tk添加到Pi后,無人機ui的局部時間成本增加量最小。重復(fù)上述任務(wù)添加過程,直至式(14)不再滿足或者ui執(zhí)行的任務(wù)數(shù)已達最大承載量。

2.3.2 沖突消解步驟

任務(wù)再分配沖突消解也分為協(xié)商一致和任務(wù)刪除兩部分。

1) 協(xié)商一致

因為是針對C中任務(wù)的再分配過程,所以在此交流過程中,無人機只交換與C中任務(wù)相關(guān)的信息。協(xié)商一致的規(guī)則如表1,具體執(zhí)行操作同2.2.1節(jié)中的更新、保留和重置操作。

2) 任務(wù)刪除

無人機ui需要刪除A′={tj∈Pi|Zij≠i}和B′={tj∈Pi|Tj(Pi)Tj_end}中的任務(wù)。其中,ui移除A′中任務(wù)的方法與2.2.2節(jié)相同。而對于任務(wù)tj∈B′,將任務(wù)tj從序列Pi中移除時,執(zhí)行操作:Zij→∞,Qij→∞,Tij→∞,Mi[tj]=1。Mi[tj]設(shè)置為1是為了保證在當前任務(wù)再分配階段中,tj將不會再被添加進Pi,從而避免無效的任務(wù)添加和移除,提高任務(wù)分配效率。無人機ui每移除一個任務(wù)tj,都需要重新計算Pi中任務(wù)的開始執(zhí)行時間,判斷是否出現(xiàn)不符合時間窗約束的新任務(wù)。

無人機ui重復(fù)迭代地移除B′中任務(wù),直至B′=?,即Pi中的所有任務(wù)滿足時間窗約束。任務(wù)刪除過程結(jié)束后,計算Qij和Tij,?tj∈Pi。

2.4 收斂性分析

文中所提出的DATW算法包括任務(wù)初分配和任務(wù)再分配兩部分。其中,任務(wù)初分配過程對應(yīng)于2.1節(jié)和2.2節(jié)描述的任務(wù)添加和沖突消解兩個階段。初分配結(jié)果可能不會覆蓋全部任務(wù),因此需要執(zhí)行2.3節(jié)中的任務(wù)再分配階段,盡可能的提高任務(wù)分配成功率。

DATW算法基于迭代優(yōu)化原理展開,每一架無人機在每輪迭代中的目標是降低全局時間成本,并盡可能把所有任務(wù)分配給無人機。具體來講,每架無人機計算執(zhí)行自身任務(wù)路徑的時間成本,并與其他無人機視角下對應(yīng)任務(wù)的執(zhí)行成本相比較,遞歸地選擇從自身任務(wù)路徑中保留或移除任務(wù),以此來降低全局時間成本。同時,通過第三個任務(wù)再分配階段,盡可能地分配任務(wù)。最終實現(xiàn)最小化任務(wù)平均完成時間的總目標。

任務(wù)分配過程中,每架無人機的任務(wù)增益列表不斷更新,反映了當前的分配情況。當所有無人機的任務(wù)分配信息保持一致,達成全局共識,即Qi=Qh,?ui∈Nu,uh∈Nu且ui≠uh時,算法收斂。

DATW算法在所有無人機上并行執(zhí)行,流程圖如圖3所示。

圖3 DATW算法流程圖Fig.3 Flow chart of DATW algorithm

DATW算法具體步驟可總結(jié)如下:

Step 1 根據(jù)2.1節(jié)執(zhí)行任務(wù)添加階段。

Step 2 根據(jù)2.2節(jié)循環(huán)執(zhí)行沖突消解階段,直到所有無人機的增益列表不發(fā)生改變。

Step 3 循環(huán)執(zhí)行Step 1和Step 2,直到所有無人機不添加或移除任務(wù),或迭代次數(shù)超過20輪。計算未分配任務(wù)集合C,若C=?,算法結(jié)束。

Step 4 對C中的任務(wù)執(zhí)行再分配階段任務(wù)添加。

Step 5 執(zhí)行再分配階段沖突消解,循環(huán)執(zhí)行再分配協(xié)商一致階段和再分配任務(wù)刪除階段,直到所有無人機的增益列表不發(fā)生改變。

Step 6 循環(huán)Step 4和Step 5,直到所有無人機不添加或移除任務(wù),算法結(jié)束。

3 算法仿真分析

假設(shè)任務(wù)分布在10 000 m×10 000 m×1 000 m的三維區(qū)域,無人機初始時分布在10 000 m× 10 000 m二維平面,無人機的飛行速度恒為50 m/s,每架無人機最多執(zhí)行任務(wù)數(shù)為5,任務(wù)時間窗口的最晚完成時間不大于500 s,任務(wù)的執(zhí)行時間均為30 s。針對無人機數(shù)為n和任務(wù)數(shù)為m的算例,隨機生成所有無人機和任務(wù)的坐標和每個任務(wù)對應(yīng)的時間窗約束條件。注意當時間窗約束較為嚴格時,可能存在無法分配的任務(wù)。

文中進行了兩組實驗:第一組驗證在不同規(guī)模算例中DATW算法的任務(wù)再分配階段的有效性;第二組驗證不同通信拓撲環(huán)境下DATW算法的適用性,檢驗算法能否成功分配所有任務(wù),分析所有任務(wù)都分配后的任務(wù)的平均完成時間。第二組實驗同時與CBBATW[27]算法和ECNP[23]算法進行了對比分析,為了能夠與DATW算法進行對比,對CBBATW和ECNP依據(jù)實驗場景進行了必要的調(diào)整。

為更方便評估任務(wù)分配解的質(zhì)量,首先規(guī)定任務(wù)分配成功率為μ=M/m,其中M為分配給集群系統(tǒng)的任務(wù)個數(shù)。在實驗1中只對比分析解的成功率μ,在實驗2中先比較任務(wù)完全分配的概率,再分析對比μ=100%的場景中所有任務(wù)的平均完成時間。

實驗1 在通信拓撲為全聯(lián)通情況下(如圖4(a)所示),考慮6種規(guī)模的無人集群任務(wù)分配問題n×m∈{(3, 7), (6, 12), (9, 20), (12, 25), (15, 30), (30, 70)}。令DATW_1表示不具備任務(wù)再分配階段的DATW算法。對于每種算例,隨機生成10個場景,在每個場景上分別運行DATW_1和DATW算法,統(tǒng)計每種算例中μ的最大值、平均值和最小值。實驗結(jié)果如表2所示。通過仿真可知,在所有算例中,DATW算法取得比DATW_1算法更好的任務(wù)分配成功率,平均提高了13.76%的任務(wù)成功分配率。這表明了文中所提出的任務(wù)再分配階段是有效的且高效的,在滿足時間窗約束的前提下,能盡可能把任務(wù)分配給無人集群系統(tǒng)。

表2 DATW算法有效性驗證Table 2 Validation of DATW algorithm %

圖4 四種通信拓撲Fig.4 Four communication topologies

實驗2 無人集群內(nèi)部的通信拓撲關(guān)系會對信息交流產(chǎn)生較大影響。諸如全聯(lián)通網(wǎng)(見圖4(a))的密集通信拓撲能促進集群無人機之間的信息交流,而實際上受限于通信鏈路約束,無人集群系統(tǒng)之間往往以稀疏通信拓撲為主(如鏈形、星形、環(huán)形拓撲,見圖4(b)～圖4(d)。

為了全面驗證文中提出的DATW算法在不同通信拓撲下的性能和適應(yīng)性,本實驗分別考慮3種規(guī)模的算例,即n×m∈{(6, 12), (12, 25), (30, 70)}。每種規(guī)模下隨機生成場景數(shù)為30,在每個場景上基于上述四種拓撲分別運行DATW算法、CBBATW算法和ECNP算法,分別統(tǒng)計μ=100%的概率。同時,統(tǒng)計當μ=100%時,任務(wù)的平均完成時間的最大值、最小值和平均值,實驗結(jié)果如表3所示。通過仿真可以得出:1)在全聯(lián)通拓撲下,ECNP算法性能表現(xiàn)最好,DATW算法稍差一點,但遠比CBBATW算法表現(xiàn)好,CBBATW算法在(30, 70)的算例中任務(wù)完全分配概率僅為33.33%,相應(yīng)的任務(wù)平均完成時間也明顯高于DATW和ECNP算法;2) ECNP算法在鏈形、星形、環(huán)形拓撲下,任務(wù)完全分配率大幅下降,任務(wù)平均完成時間增大,性能變差,這說明ECNP算法依賴于通信拓撲。但DATW和CBBATW在鏈形、星形、環(huán)形拓撲下的實驗結(jié)果和全聯(lián)通拓撲下的結(jié)果相近,這表明DATW和CBBATW算法受拓撲關(guān)系影響較小,適應(yīng)性更強;3) CBBATW算法隨實驗規(guī)模增大,性能大幅降低,成功分配所有任務(wù)的概率最低,在所有算例μ=100%的場景中的任務(wù)平均完成時間均值最低,與CBBATW算法相比,DATW算法的任務(wù)完全分配率平均提升了21.94%,平均完成時間提升了24.25 s。因此,DATW算法能盡可能地成功分配所有的任務(wù),且得到的解質(zhì)量更好。

表3 四種拓撲下三種算法性能表現(xiàn)Table 3 Performance of three algorithms under four topologies

4 結(jié)論

針對具有時間窗約束的無人集群協(xié)同任務(wù)分配問題,提出一種分布式任務(wù)分配算法DATW,其優(yōu)化目標是最小化任務(wù)平均完成時間。仿真實驗結(jié)果表明,DATW提出的任務(wù)再分配階段將任務(wù)成功分配率提升了13.76%,并且所提算法可以適應(yīng)各種通信拓撲,相比于ECNP算法,DATW和CBBATW在不同拓撲下性能表現(xiàn)穩(wěn)定,同時DATW的平均任務(wù)完全分配率比CBBATW高21.94%,任務(wù)平均完成時間小24.25 s,因此獲得的任務(wù)分配結(jié)果質(zhì)量更好,性能更好。但文中對無人機和任務(wù)的一些參數(shù)進行了簡化,并未考慮到實際環(huán)境中障礙物和威脅的存在,未來可以更接近實際地研究分布式任務(wù)分配算法,提升算法在現(xiàn)實環(huán)境下的實用性。