時間窗約束下的無人集群分布式任務分配算法

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

1) 無人機因素

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

(1)

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

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

Fj(Pi)=Tj(Pi)+Dj

(2)

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

|Pi|≤Li,?ui∈Nu

(3)

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

2) 任務因素

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

Tj(Pi)∈[Tj_start,Tj_end]

(4)

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

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

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

2 無人集群分布式任務分配算法

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

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

1) 任務分配對象列表

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

2) 任務增益列表

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

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

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

4) 時間戳列表

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

(9)

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

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

2.1 任務添加階段

1) 任務增益

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

(10)

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

2) 任務邊際增益

(11)

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

(12)

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

2.2 沖突消解階段

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

2.2.1 協(xié)商一致步驟

假設Gih=1,無人機ui與鄰近無人機uh通過局部通信拓撲進行信息交換,共享Zi和Zh、Qi和Qh、Ti和Th、si和sh,并按照一定的交流規(guī)則更新相應信息。實際上,當無人機ui收到鄰近uh發(fā)來的信息后,會根據Zi和si來判斷接收到的信息是否為任務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 任務刪除步驟

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

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

(13)

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

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

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

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

2.3 任務再分配階段

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

2.3.1 任務添加步驟

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

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

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

(14)

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

2.3.2 沖突消解步驟

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

1) 協(xié)商一致

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

2) 任務刪除

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

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

2.4 收斂性分析

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

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

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

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

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

DATW算法具體步驟可總結如下:

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

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

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

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

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

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

3 算法仿真分析

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

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

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

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

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

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

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

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

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

4 結論

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