多目標空地異構無人系統協同任務分配方法

范博洋,趙高鵬,薄煜明,吳祥

(南京理工大學 自動化學院,江蘇 南京 210094)

0 引言

在復雜的戰場環境中,功能有限的單一種類無人裝備因工作方式、工作空間、載荷性能等因素限制,無法單獨完成復雜多樣的作戰任務[1]。如旋翼無人機(UAV)具有快速靈活、視野開闊、受環境影響較小等優點,但其受限于自身載荷較小、續航時間短等不足,在大范圍多目標的偵察任務中需要UAV集群的協同工作。地面無人車(UGV)具有載荷能力強、續航時間長等優點,但其受地形環境限制較大,偵察視野有限[2]。而空地異構無人系統結合空地無人平臺各自優勢協同作戰,是適應未來戰場的必然選擇。因此,研究空地異構無人系統的協同任務分配具有現實意義。

無人系統協同任務分配是指考慮多目標任務和無人平臺自身功能,對系統內無人裝備的任務進行優化配置,使無人系統以最小代價協同完成任務[3]。無人系統的異構通常分為兩類：一個是結構上的異構,主要由無人平臺自身的因素造成,如運動能力、載荷能力的不同或能源動力限制等導致無人裝備執行任務的空間和范圍不同;另一個是功能上的異構,主要由無人平臺搭載的有效載荷造成,如傳感器種類或武器性能不同等因素導致無人裝備所能執行任務的種類不同[4-7]。由于無人系統協同任務分配可以視為多旅行商問題,本質上是NP-hard問題[8],具有多種異構性質的因素會導致約束數量的增加,從而導致求解任務分配的計算量顯著增加,特別是對于大規模問題。

目前,對兩種不同類型的異構無人系統任務分配問題均有大量的研究。對于結構上的異構系統,Murray等[9]研究了異構機器人投遞系統的任務分配,地面車輛和UAV分別從倉庫出發向多個目標點投送物資后返回,由UAV發揮速度優勢,地面車輛來彌補UAV航程和載荷能力的不足。Ha等[10]研究了地面車輛搭載UAV進行物資投遞的任務分配,對于符合UAV航程約束的目標點,由地面車輛在相鄰的目標點釋放并回收UAV來完成投遞任務,發揮UAV的速度優勢,但該方法并不涉及同時使用多無人機(UAVs)的分配以及UAV降落點的選擇。Bae等[6-7]研究了由行動速度不同的一組機器人組成的異構系統,對機器人從不同倉庫出發向多個目標執行投遞任務后再返回的任務分配問題提出了一種啟發式的優化算法。Chen等[11]研究了異構UAVs對區域的協同覆蓋,由于UAV的速度和傳感器性能的差別導致了可覆蓋區域大小不同,對不同覆蓋區域的分配問題提出了一種基于整數線性規劃的方法。Chen等[12]同樣研究了異構UAVs對區域的協同覆蓋,提出用密度聚類的方法為UAV的覆蓋區域進行劃分。Banfi等[13]研究了一種UGVs-UAVs任務分配框架,設計一個圖神經網絡估計UGVs-UAVs的分組和完成任務的代價,并使用混合整數線性規劃對估計結果進行實際任務分配用以訓練網絡。對于功能上的異構系統,Arbanas等[14]研究了一種由UGV搭載一架UAV的異構無人系統,UGV具有收放UAV的能力,UAV從空中引導UGV進行避障。Shima等[15]和Edison等[16]研究了UAVs對多個地面目標協同執行受時序優先級約束的確認、攻擊和毀傷評估3種任務的任務分配,考慮了時間、資源、可飛路徑等多項約束。Feo-Flushing等[17]研究了將任務拆分為多個不同類型的子任務,分配給功能不同的多個機器人來執行,分別提出啟發式和精確的算法來解決任務分配問題。Zhao等[18]研究了一種異構UAVs系統,不同類型的UAV具有執行不同任務的能力,對應多個目標需要執行多種任務,因此提出一種基于強化學習的方法解決了任務分配的問題。Chen等[19]提出一種多目標蟻群優化算法解決異構UAVs系統的任務分配問題。

現有的異構無人系統任務分配研究主要聚焦對無人平臺各自合理分配,將無人系統任務分配看作多個無人平臺的分工,彼此之間少有協作,尤其忽略了無人平臺彼此之間的關聯對任務分配結果的影響。例如關于UGV回收UAV集群位置的自主選擇,這將使UGV與UAV的任務分配具有耦合因素,更能體現異構無人系統的協同與合作。

針對以上問題,本文研究UGV與多架旋翼UAV組成空地異構無人系統對作戰區域內的多個目標進行協同偵察與打擊的任務分配問題。該空地異構無人系統既包含結構上的異構,又包含功能上的異構。由UAV執行偵察任務,UGV在執行打擊任務的同時需要在合適的地點釋放、回收UAV,使得整個系統在最短的時間有效完成任務。在目標數量較多的環境下,本文先將作戰區域內目標點聚類劃分為若干子任務區域,并對子區域間進行任務分配。再在子區域內將UAV的任務分配模型與UGV的任務分配模型相結合,考慮二者之間的耦合,在給出任務分配的同時,還確定了UGV收放UAV的位置,使得空地異構無人系統的任務分配結果符合約束條件。本文的研究思路如圖1所示,貢獻主要包括兩個方面：1) 建立了空地異構無人系統協同任務分配模型;2)提出一種結合聚類算法和啟發式算法的多目標空地異構無人系統協同任務分配方法,求解對大范圍、多目標、可回收的空地異構無人系統任務分配。

1 協同任務分配問題模型

1.1 問題描述

假設空地異構無人系統的作戰場景為較大范圍內具有數量較多的待偵察和待打擊目標。UGV續航能力強并可以攜帶攻擊武器,其在執行任務的過程中能量不會耗盡,而UAV的續航能力有限,只具有偵察載荷。本文假設無人系統擁有戰前情報支援,可以獲得戰場衛星地圖以及可靠的目標位置。UGVG={g}與UAVsU={u1,u2,…}對作戰區域內多目標點T={t1,t2,…}進行協同偵察與打擊,作戰區域內目標點的位置、數量以及待執行任務類型等信息都是已知的,其中全部目標點均為待偵察目標Ts?T,部分特定的目標點為待打擊目標Ta?T。

考慮空地異構無人系統的特點,作戰過程如圖2所示,各UAV的飛行路徑由不同顏色區分。UGV搭載UAV進入作戰區域,并自主決定釋放點tre釋放多架UAV,由UAV對分配的目標點依次進行偵察,同時UGV向已被偵察的待打擊目標點依次運動并進行火力打擊,UAV執行完作戰區域內的偵察任務后前往降落點tl降落回UGV。在整個作戰過程中,UGV以速度vg在地面行駛,UAV以速度vu勻速飛行,飛行高度為hu。無人系統在作戰區域內的候選降落點Tland=(Ta∪tre)中自主選擇UAV的降落點tl∈Tland。

圖2 多目標空地異構無人系統協同作戰過程示意圖Fig.2 Schematic diagram of collaborative operation process of multi-target air-ground heterogeneousunmanned system

多目標空地異構無人系統協同任務分配問題可以描述成多旅行商問題的形式,每一個任務分配方案即是該多旅行商問題的一個解,表示為指派空地異構無人系統中的各個無人裝備對不同數量的目標點執行不同類型任務的時序序列。本文將空地異構無人系統的協同任務分配模型拆分為UAVs任務分配模型和UGV任務分配模型,對其分別求解,并同時考慮二者間的耦合成分,即UGV收放UAV的位置和時間。本文將無人裝備在目標點間的運動估計簡化為無障礙的直線運動。

1.2 問題建模

1.2.1 UAVs任務分配模型

為最小化各UAV協同執行任務及返回降落點所使用的總時間,UAVs任務分配模型的目標函數如 式(1)所示：

(1)

UAV的航程約束如式(2)所示,UAV從起飛執行任務到安全降落所使用時間不能超過其最大續航時間。

(2)

UAV的偵察任務約束條件如式(3)和式(4)所示,所有待偵察的目標都需要被偵察,且只需偵察一次。

(3)

(4)

式中：Ns為待偵察的目標數量。

UAV的降落約束如式(5)～式(7)所示,所有出動的UAV都要安全降落,且UGV到達降落點時間不能晚于UAV。

(5)

(6)

(7)

1.2.2 UGV任務分配模型

為最小化UGV執行任務所使用的總時間,UGV任務分配模型的目標函數如式(8)：

(8)

UGV的回收約束如式(9)所示,UGV要先于UAV到達降落點。

?u∈UT,Jwait≥0

(9)

UGV的打擊任務約束如式(10)和式(11)所示,所有待攻擊的目標都需要被攻擊,且只需攻擊一次。

(10)

(11)

式中：Nd為待攻擊的目標數量。

目標點的任務時序約束如式(12)所示,對任意待攻擊的目標,都須先由UAV進行偵察后,UGV再執行攻擊任務。

(12)

2 多目標空地異構無人系統協同任務分配方法

采用兩步法對多目標空地異構無人系統協同任務分配問題進行求解：

1)使用密度最大值聚類方法[20]將作戰區域按目標密度進行劃分,得到n個子任務區域{C1,C2,…,Cn}。再將子任務區域的任務分配問題近似為UGV遍歷各區域的排序,其優化目標為最小化UGV遍歷各區域所使用的時間。使用子區域內密度值最大點來代表區域位置,可以利用UGV任務分配模型,使用混合粒子群算法對UGV在子任務區域間轉移的任務分配問題進行求解,得到最優解PC={1,2,…,n}為UGV在子任務區域間執行任務的次序。

多目標空地異構無人系統協同任務分配的流程圖如圖3所示,圖中itCC、itCM分別是子區域間任務分配的當前迭代次數和最大迭代次數,itUC、itUM是UAV任務分配的當前迭代次數和最大迭代次數,itGC、itGM是UGV任務分配的當前迭代次數和最大迭代次數。

圖3 多目標空地異構無人系統協同任務分配方法流程圖Fig.3 Process of the task allocation method for multi-target air-ground heterogeneous unmanned system

2.1 子任務區域劃分

在面向大范圍多目標的復雜戰場環境中,UAV有限的航程是限制空地異構無人系統完成任務能力的重要約束。在目標分布不均衡、存在多個密集目標群和稀疏目標點的作戰場景下,劃分子任務區域,將密集目標群和稀疏目標點區分開來,使用UGV攜帶UAV在區域間機動轉移,減少UAV在稀疏目標點間的往返,有效的提高空地異構無人系統在航程約束下進行任務分配的能力。密度值最大聚類以空間區域的目標稠密程度作為發現簇的依據,能夠有效的發現任意形狀的簇,對于稀疏目標點可以單獨劃分,符合本文分離密集目標群和稀疏目標點的需要。該方法可以自動發現簇的數量,無需人工確定,其參數選擇取決于密度閾值的設定,與目標點的實際分布無關。

2.1.1 密度最大值聚類

定義目標點tp與tq間的距離dist(tp,tq)為歐式距離,tp,tq∈T。目標點tp的鄰域N(tp,ε)為以tp為核心、半徑ε區域內所包含的目標點,即

N(tp,ε)={tq|dist(tp,tq)≤ε}

(13)

目標點tp的密度ρp定義為tp的鄰域N(tp,ε)內包含所有目標的數量,即

ρ(tp)=|N(tp,ε)|

(14)

定義最大密度值點為

tmax={tp|tp∈T;?tq∈T,ρ(tp)≥ρ(tq)}

(15)

定義按與最大密度值點距離排列的目標點序列為

Smax={tp,tq,…,tn|dist(tmax,tp)≤
dist(tmax,tq)≤…≤dist(tmax,tn)}

(16)

定義簇Ch與Cm間距離為兩個簇中最近兩個目標點之間的距離,即

dist(Ch,Cm)=min(dist(tp,tk))

(17)

式中：tp∈Ch;tk∈Cm。

密度最大值聚類分為兩步：

ρ(tp)≥minDens,tp∈Smax

(18)

2) 合并基本簇。對第1步得到的基本簇集C*,將簇間距離小于簇距離閾值minDist的簇合并為一個簇,即

(19)

最終得到簇集C={C1,C2,…}。

2.1.2 參數選擇

密度值最大聚類的參數包括：鄰域半徑ε、密度閾值minDens和簇距離閾值minDist。其中鄰域半徑和密度閾值決定基本簇的產生,在本文假設的作戰場景下,一定范圍內目標數量超過一個閾值則可以視為一個重要陣地,應當被劃分為同一個任務區域。簇距離閾值決定如何合并基本簇,同時也決定如何劃分稀疏目標點,該參數的選取與UAV的性能相關聯,本文中驗證實驗的參數由多次實驗調整取得。

2.2 混合粒子群優化算法

2.2.1 適應度值設計

2.2.1.1 對子任務區域的任務分配

粒子適應度值表示為UGV完成在各子區域間轉移所用時間之和,各子區域的位置由區域內密度值最大的任務點代表：

(20)

式中：Tmax?T為各子任務區域內密度值最大的任務點的集合;pathG(ti,tj)為UGV從目標ti到目標tj所需時間。

2.2.1.2 對UAV的任務分配

粒子適應度值表示為各UAV完成被分配的任務所用時間與到達降落點所用時間之和。

(21)

2.2.1.3 對UGV的任務分配

粒子適應度值表示為UGV完成被分配的任務所用時間與等待全部UAV降落完成所用時間之和：

(22)

式中：costwait為UGV等待全部UAV降落的時間。

2.2.2 粒子表示

粒子表示采用整數編碼的形式,每一個粒子代表多目標空地異構無人系統協同任務分配的一種方案,包括系統中全部UGV和UAV的任務時序序列,該粒子須滿足任務約束條件式(3)、式(4)、式(10)和式(11)。例如,一個包含一輛UGV和4架UAV的空地異構無人系統,待分配的偵察目標為16個,序號為1～16,其中目標[4,7,10,13]同時為待打擊的目標,則表示一種任務分配方案的粒子如圖4 所示。

圖4 粒子表示方法Fig.4 A sample of the particle code

2.2.3 交叉操作

粒子通過與極值交叉得到新的粒子,交叉方法采用整數交叉法。首先選擇交叉位置和交叉片段大小,然后將粒子與極值的交叉位置上的值進行交換。產生的新粒子可能會出現目標重復分配及目標缺失,因此還需對新粒子進行調整。在新粒子中保留由交叉位置得到的新分配目標點,對在非交叉位置上存在的與新分配目標點重復的目標點,用缺失的目標點進行替換。當存在多個重復目標點時,被替換位置與替換目標點使用隨機匹配,使得新粒子滿足任務約束條件式(3)、式(4)、式(10)和式(11)。假定隨機選取交叉位置為第4個UAV的第2個目標,交叉片段大小為2,操作方法如圖5所示。

圖5 交叉操作方法Fig.5 A sample of the crossover operation

2.2.4 變異操作

粒子通過自身變異得到新的粒子,變異方法采用粒子某個任務序列中的兩目標次序互換。首先選擇變異位置,然后把兩個變異位置互換,顯然新粒子滿足任務約束條件式(3)、式(4)、式(10)和式(11)。假定選擇的變異位置為第2個UAV的第2位和第4位,操作方法如圖6所示。

圖6 變異操作方法Fig.6 A sample of the mutation operation

2.2.5 粒子更新策略

對UGV任務分配時,只有當新粒子的適應度值小于舊粒子且新粒子滿足回收約束條件式(9)和任務時序約束條件式(12)時才更新粒子。

對子任務區域任務分配時,只有當新粒子的適應度值小于舊粒子才更新粒子。

2.2.6 極值更新策略

極值更新分為個體極值更新和群體極值更新：

1) 個體極值更新：當新粒子的適應度值小于舊粒子極值的適應度時,更新新粒子為個體極值。

2) 群體極值更新：在不同階段的任務分配中使用混合粒子群算法,群體極值更新策略不同：

① UAV任務分配：在個體極值中符合UAV的航程約束條件式(2)的解未搜索到,且所有個體極值中最小適應度值小于群體極值的適應度值時,更新該個體極值為群體極值;在個體極值中搜索到符合UAV的航程約束條件式(2)的解,但群體極值不符合航程約束時,更新符合航程約束條件式(2)的所有個體極值中適應度值最小的個體極值為群體極值;當群體極值符合航程約束條件式(2),且所有符合航程約束條件式(2)的個體極值中最小適應度值小于舊群體極值的適應度值時,更新該個體極值為群體極值。

② UGV任務分配和子任務區域任務分配：只有當所有個體極值中最小適應度值小于群體極值的適應度值時,才更新該個體極值為群體極值。

3 仿真實驗

為驗證本文所述方法,在12 000 m×12 000 m場景下驗證聚類劃分子任務區域的效果,在6 000 m×6 000 m和12 000 m×12 000m兩種不同的場景中對由一輛UGV搭載4架UAV組成的空地異構無人系統進行多目標協同任務分配,并分析結果。其中6 000 m×6 000 m場景主要驗證在較小范圍內多目標空地異構無人系統協同任務分配的能力;12 000 m×12 000 m場景驗證在較大范圍內存在偏離密集目標區域的稀疏目標點的情況下,結合子任務區域劃分的多目標空地異構無人系統協同任務分配方法的能力。目標點坐標使用均勻分布隨機生成,得到的目標區域既有多個密集的目標群,也有稀疏的目標點,能夠近似模擬真實場景中重要區域部署兵力較多、非重要區域部署兵力較少的兵力部署的特點。假設半徑1 000 m范圍內有5個目標點的區域為一個重要陣地。UGV的速度為20 km/h,UAV的速度為30 km/h,最大飛行時間為30 min。計算機配置為AMD RyzenTM7 PRO 4750G@3.6 GHz,32 GB內存,采用Ubuntu 20.04操作系統。

3.1 聚類效果評估

在12 000 m×12 000 m作戰場景下使用均勻分布隨機生成50個目標點,圖7給出了使用密度值最大聚類進行子任務區域劃分的效果。

圖7 密度值最大聚類效果圖Fig.7 Result of density peak clustering

本文使用Davies-Bouldin指數(DBI)為評價標準：

(23)

DBI值越小,簇內的目標點分布越緊密,簇間的最小距離越大,這符合本文對子區域劃分的要求。

表1給出了在12 000 m×12 000 m作戰場景下使用密度值最大聚類、DBSCAN和k-means算法進行聚類的效果評估。其中密度值最大聚類的鄰域半徑、密度閾值由重要陣地的假設得到,簇距離閾值由多次實驗獲得;DBSCAN算法采用保留噪聲點的方式,其密度閾值由多次實驗獲得;k-means算法隨機選擇初始中心點。可以看出,密度值最大聚類可以得到子區域內目標點分布更緊密、子區域間距離更大的任務區域劃分。

表1 12 000 m×12 000 m范圍聚類劃分結果對比Table 1 Comparison of clustering results in the range of 12 000 m×12 000 m

3.2 較小范圍內的任務分配仿真

6 000 m×6 000 m范圍內的目標分布如圖8所示,隨機分布50個目標點個目標點由藍色點標出,其中有17個隨機點為待打擊目標,由黑色方框標記。黑色點為UGV的出發點。

圖8 6 000 m×6 000 m范圍內目標分布圖Fig.8 Target distribution map in the range of 6 000 m×6 000 m

多目標空地異構無人系統協同任務分配方法的參數如表2所示。多目標空地異構無人系統協同任務分配結果如表3和圖9所示。

表2 6 000 m×6 000 m范圍協同任務分配方法參數Table 2 Parameters of thecollaborative task allocation method in the range of 6 000 m×6 000 m

表3 6 000 m×6 000 m范圍協同任務分配結果Table 3 Collaborative task allocation in the range of 6 000 m×6 000 m

圖9 6 000 m×6 000 m范圍內協同任務分配示意圖Fig.9 Schematic diagram of the collaborative taskallocation in the range of 6 000 m×6 000 m

由于區域內目標點的分布較為密集,密度值最大聚類算法將整個任務區域劃分為一個子區域。規劃的UAVs釋放點在距離目標點[19]的50 m處,坐標為(365 m,106 m),降落點為目標點40的位置,UGV等待UAVs降落時間Jwait=5.36 s,各UAV的飛行時間為[1 718.11 s,1 340.85 s,1 562.53 s,1 643.87 s],各子區域內的任務分配結果滿足UAVs的航程約束式(2)、偵察任務約束式(3)和式(4)、降落約束式(5)～式(7)、UGV的回收約束式(9)、打擊任務約束式(10)和式(11)以及目標點的任務時序約束式(12)。

圖9為協同任務分配結果的示意圖。各UAV飛行時間的收斂曲線如圖10所示,從圖中可以看出混合粒子群優化算法在第555次迭代中得到滿足航程約束式(2)的解,在1 800次迭代后基本收斂到穩定值。整個多目標空地異構無人系統協同任務分配計算用時859.9 s。

圖10 各UAV飛行時間曲線Fig.10 Flight time curves of UAVs

3.3 較大范圍內的任務分配仿真

12 000 m×12 000 m范圍內的目標分布如圖11所示,隨機分布50個目標點由藍色點標出,其中有17個隨機點為待打擊目標,由黑色方框標記。黑色點為UGV的出發點。

圖11 12 000 m×12 000 m范圍內目標分布圖Fig.11 Target distribution map in the range of 12 000 m×12 000 m

若不對作戰區域進行劃分,混合粒子群優化算法的參數如表4所示。任務分配結果如表5所示,各UAV的飛行時間為[3 401.53 s,2 884.75 s,2 491.79 s,2 704.78 s],超過其最大續航時間,違反了UAVs的航程約束條件式(2),任務分配失敗。

表4 12 000 m×12 000 m范圍不劃分子任務區域的協同任務分配方法參數Table 4 Parameters of the task allocation method without clustering in the range of 12 000 m×12 000 m

表5 12 000 m×12 000 m范圍不聚類劃分子任務區域的協同任務分配結果Table 5 Task allocation result without clustering in the range of 12 000 m×12 000 m

結合密度值最大聚類算法對作戰區域進行劃分,空地異構無人系統協同任務分配方法的參數如表6所示。密度值最大聚類將作戰區域劃分為 16個子任務區域,子任務區域的劃分和任務分配結果如圖12所示。

表6 12 000 m×12 000 m范圍協同任務分配方法參數Table 6 Parameters of the collaborative task allocation method in the range of 12 000 m×12 000 m

圖12 子任務區域的劃分和任務分配Fig.12 Clustering and task allocation

圖13 12 000 m×12 000 m范圍內多目標空地異構無人系統協同任務分配示意圖Fig.13 Schematic diagram of the collaborative task allocation for multi-target air-ground heterogeneous unmanned system in the range of 12 000 m×12 000 m

圖13為多目標空地異構無人系統協同任務分配結果的示意圖。整個協同任務分配計算用時277.93 s。

4 結論

本文首先基于多目標、大面積的戰場環境假設,構建空地異構無人系統協同任務分配模型,提出一種多目標空地異構無人系統協同任務分配方法,最后通過兩種不同的環境中的仿真實驗,證明了本文方法的有效性。得出以下主要結論：

1) 在較小作戰環境內,本文方法能夠滿足約束條件,有效地為空地異構無人系統進行協同任務分配。

2) 在較大作戰環境內,由于約束條件限制,UAVs無法在一次出動中完成設定任務,本文方法通過結合密度值最大聚類、混合粒子群優化算法,將整個戰場劃分為多個子任務區域,并為空地異構無人系統在區域間轉移和區域內作戰進行協同任務分配,使其滿足約束條件。