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

(南京理工大學(xué) 自動(dòng)化學(xué)院,江蘇 南京 210094)

0 引言

在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境中,功能有限的單一種類無人裝備因工作方式、工作空間、載荷性能等因素限制,無法單獨(dú)完成復(fù)雜多樣的作戰(zhàn)任務(wù)[1]。如旋翼無人機(jī)(UAV)具有快速靈活、視野開闊、受環(huán)境影響較小等優(yōu)點(diǎn),但其受限于自身載荷較小、續(xù)航時(shí)間短等不足,在大范圍多目標(biāo)的偵察任務(wù)中需要UAV集群的協(xié)同工作。地面無人車(UGV)具有載荷能力強(qiáng)、續(xù)航時(shí)間長等優(yōu)點(diǎn),但其受地形環(huán)境限制較大,偵察視野有限[2]。而空地異構(gòu)無人系統(tǒng)結(jié)合空地?zé)o人平臺(tái)各自優(yōu)勢(shì)協(xié)同作戰(zhàn),是適應(yīng)未來戰(zhàn)場(chǎng)的必然選擇。因此,研究空地異構(gòu)無人系統(tǒng)的協(xié)同任務(wù)分配具有現(xiàn)實(shí)意義。

無人系統(tǒng)協(xié)同任務(wù)分配是指考慮多目標(biāo)任務(wù)和無人平臺(tái)自身功能,對(duì)系統(tǒng)內(nèi)無人裝備的任務(wù)進(jìn)行優(yōu)化配置,使無人系統(tǒng)以最小代價(jià)協(xié)同完成任務(wù)[3]。無人系統(tǒng)的異構(gòu)通常分為兩類：一個(gè)是結(jié)構(gòu)上的異構(gòu),主要由無人平臺(tái)自身的因素造成,如運(yùn)動(dòng)能力、載荷能力的不同或能源動(dòng)力限制等導(dǎo)致無人裝備執(zhí)行任務(wù)的空間和范圍不同;另一個(gè)是功能上的異構(gòu),主要由無人平臺(tái)搭載的有效載荷造成,如傳感器種類或武器性能不同等因素導(dǎo)致無人裝備所能執(zhí)行任務(wù)的種類不同[4-7]。由于無人系統(tǒng)協(xié)同任務(wù)分配可以視為多旅行商問題,本質(zhì)上是NP-hard問題[8],具有多種異構(gòu)性質(zhì)的因素會(huì)導(dǎo)致約束數(shù)量的增加,從而導(dǎo)致求解任務(wù)分配的計(jì)算量顯著增加,特別是對(duì)于大規(guī)模問題。

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

現(xiàn)有的異構(gòu)無人系統(tǒng)任務(wù)分配研究主要聚焦對(duì)無人平臺(tái)各自合理分配,將無人系統(tǒng)任務(wù)分配看作多個(gè)無人平臺(tái)的分工,彼此之間少有協(xié)作,尤其忽略了無人平臺(tái)彼此之間的關(guān)聯(lián)對(duì)任務(wù)分配結(jié)果的影響。例如關(guān)于UGV回收UAV集群位置的自主選擇,這將使UGV與UAV的任務(wù)分配具有耦合因素,更能體現(xiàn)異構(gòu)無人系統(tǒng)的協(xié)同與合作。

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

1 協(xié)同任務(wù)分配問題模型

1.1 問題描述

假設(shè)空地異構(gòu)無人系統(tǒng)的作戰(zhàn)場(chǎng)景為較大范圍內(nèi)具有數(shù)量較多的待偵察和待打擊目標(biāo)。UGV續(xù)航能力強(qiáng)并可以攜帶攻擊武器,其在執(zhí)行任務(wù)的過程中能量不會(huì)耗盡,而UAV的續(xù)航能力有限,只具有偵察載荷。本文假設(shè)無人系統(tǒng)擁有戰(zhàn)前情報(bào)支援,可以獲得戰(zhàn)場(chǎng)衛(wèi)星地圖以及可靠的目標(biāo)位置。UGVG={g}與UAVsU={u1,u2,…}對(duì)作戰(zhàn)區(qū)域內(nèi)多目標(biāo)點(diǎn)T={t1,t2,…}進(jìn)行協(xié)同偵察與打擊,作戰(zhàn)區(qū)域內(nèi)目標(biāo)點(diǎn)的位置、數(shù)量以及待執(zhí)行任務(wù)類型等信息都是已知的,其中全部目標(biāo)點(diǎn)均為待偵察目標(biāo)Ts?T,部分特定的目標(biāo)點(diǎn)為待打擊目標(biāo)Ta?T。

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

圖2 多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同作戰(zhàn)過程示意圖Fig.2 Schematic diagram of collaborative operation process of multi-target air-ground heterogeneousunmanned system

多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配問題可以描述成多旅行商問題的形式,每一個(gè)任務(wù)分配方案即是該多旅行商問題的一個(gè)解,表示為指派空地異構(gòu)無人系統(tǒng)中的各個(gè)無人裝備對(duì)不同數(shù)量的目標(biāo)點(diǎn)執(zhí)行不同類型任務(wù)的時(shí)序序列。本文將空地異構(gòu)無人系統(tǒng)的協(xié)同任務(wù)分配模型拆分為UAVs任務(wù)分配模型和UGV任務(wù)分配模型,對(duì)其分別求解,并同時(shí)考慮二者間的耦合成分,即UGV收放UAV的位置和時(shí)間。本文將無人裝備在目標(biāo)點(diǎn)間的運(yùn)動(dòng)估計(jì)簡化為無障礙的直線運(yùn)動(dòng)。

1.2 問題建模

1.2.1 UAVs任務(wù)分配模型

為最小化各UAV協(xié)同執(zhí)行任務(wù)及返回降落點(diǎn)所使用的總時(shí)間,UAVs任務(wù)分配模型的目標(biāo)函數(shù)如 式(1)所示：

(1)

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

(2)

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

(3)

(4)

式中：Ns為待偵察的目標(biāo)數(shù)量。

UAV的降落約束如式(5)～式(7)所示,所有出動(dòng)的UAV都要安全降落,且UGV到達(dá)降落點(diǎn)時(shí)間不能晚于UAV。

(5)

(6)

(7)

1.2.2 UGV任務(wù)分配模型

為最小化UGV執(zhí)行任務(wù)所使用的總時(shí)間,UGV任務(wù)分配模型的目標(biāo)函數(shù)如式(8)：

(8)

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

?u∈UT,Jwait≥0

(9)

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

(10)

(11)

式中：Nd為待攻擊的目標(biāo)數(shù)量。

目標(biāo)點(diǎn)的任務(wù)時(shí)序約束如式(12)所示,對(duì)任意待攻擊的目標(biāo),都須先由UAV進(jìn)行偵察后,UGV再執(zhí)行攻擊任務(wù)。

(12)

2 多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配方法

采用兩步法對(duì)多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配問題進(jìn)行求解：

1)使用密度最大值聚類方法[20]將作戰(zhàn)區(qū)域按目標(biāo)密度進(jìn)行劃分,得到n個(gè)子任務(wù)區(qū)域{C1,C2,…,Cn}。再將子任務(wù)區(qū)域的任務(wù)分配問題近似為UGV遍歷各區(qū)域的排序,其優(yōu)化目標(biāo)為最小化UGV遍歷各區(qū)域所使用的時(shí)間。使用子區(qū)域內(nèi)密度值最大點(diǎn)來代表區(qū)域位置,可以利用UGV任務(wù)分配模型,使用混合粒子群算法對(duì)UGV在子任務(wù)區(qū)域間轉(zhuǎn)移的任務(wù)分配問題進(jìn)行求解,得到最優(yōu)解PC={1,2,…,n}為UGV在子任務(wù)區(qū)域間執(zhí)行任務(wù)的次序。

多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的流程圖如圖3所示,圖中itCC、itCM分別是子區(qū)域間任務(wù)分配的當(dāng)前迭代次數(shù)和最大迭代次數(shù),itUC、itUM是UAV任務(wù)分配的當(dāng)前迭代次數(shù)和最大迭代次數(shù),itGC、itGM是UGV任務(wù)分配的當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

圖3 多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配方法流程圖Fig.3 Process of the task allocation method for multi-target air-ground heterogeneous unmanned system

2.1 子任務(wù)區(qū)域劃分

在面向大范圍多目標(biāo)的復(fù)雜戰(zhàn)場(chǎng)環(huán)境中,UAV有限的航程是限制空地異構(gòu)無人系統(tǒng)完成任務(wù)能力的重要約束。在目標(biāo)分布不均衡、存在多個(gè)密集目標(biāo)群和稀疏目標(biāo)點(diǎn)的作戰(zhàn)場(chǎng)景下,劃分子任務(wù)區(qū)域,將密集目標(biāo)群和稀疏目標(biāo)點(diǎn)區(qū)分開來,使用UGV攜帶UAV在區(qū)域間機(jī)動(dòng)轉(zhuǎn)移,減少UAV在稀疏目標(biāo)點(diǎn)間的往返,有效的提高空地異構(gòu)無人系統(tǒng)在航程約束下進(jìn)行任務(wù)分配的能力。密度值最大聚類以空間區(qū)域的目標(biāo)稠密程度作為發(fā)現(xiàn)簇的依據(jù),能夠有效的發(fā)現(xiàn)任意形狀的簇,對(duì)于稀疏目標(biāo)點(diǎn)可以單獨(dú)劃分,符合本文分離密集目標(biāo)群和稀疏目標(biāo)點(diǎn)的需要。該方法可以自動(dòng)發(fā)現(xiàn)簇的數(shù)量,無需人工確定,其參數(shù)選擇取決于密度閾值的設(shè)定,與目標(biāo)點(diǎn)的實(shí)際分布無關(guān)。

2.1.1 密度最大值聚類

定義目標(biāo)點(diǎn)tp與tq間的距離dist(tp,tq)為歐式距離,tp,tq∈T。目標(biāo)點(diǎn)tp的鄰域N(tp,ε)為以tp為核心、半徑ε區(qū)域內(nèi)所包含的目標(biāo)點(diǎn),即

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

(13)

目標(biāo)點(diǎn)tp的密度ρp定義為tp的鄰域N(tp,ε)內(nèi)包含所有目標(biāo)的數(shù)量,即

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

(14)

定義最大密度值點(diǎn)為

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

(15)

定義按與最大密度值點(diǎn)距離排列的目標(biāo)點(diǎn)序列為

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

(16)

定義簇Ch與Cm間距離為兩個(gè)簇中最近兩個(gè)目標(biāo)點(diǎn)之間的距離,即

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

(17)

式中：tp∈Ch;tk∈Cm。

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

ρ(tp)≥minDens,tp∈Smax

(18)

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

(19)

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

2.1.2 參數(shù)選擇

密度值最大聚類的參數(shù)包括：鄰域半徑ε、密度閾值minDens和簇距離閾值minDist。其中鄰域半徑和密度閾值決定基本簇的產(chǎn)生,在本文假設(shè)的作戰(zhàn)場(chǎng)景下,一定范圍內(nèi)目標(biāo)數(shù)量超過一個(gè)閾值則可以視為一個(gè)重要陣地,應(yīng)當(dāng)被劃分為同一個(gè)任務(wù)區(qū)域。簇距離閾值決定如何合并基本簇,同時(shí)也決定如何劃分稀疏目標(biāo)點(diǎn),該參數(shù)的選取與UAV的性能相關(guān)聯(lián),本文中驗(yàn)證實(shí)驗(yàn)的參數(shù)由多次實(shí)驗(yàn)調(diào)整取得。

2.2 混合粒子群優(yōu)化算法

2.2.1 適應(yīng)度值設(shè)計(jì)

2.2.1.1 對(duì)子任務(wù)區(qū)域的任務(wù)分配

粒子適應(yīng)度值表示為UGV完成在各子區(qū)域間轉(zhuǎn)移所用時(shí)間之和,各子區(qū)域的位置由區(qū)域內(nèi)密度值最大的任務(wù)點(diǎn)代表：

(20)

式中：Tmax?T為各子任務(wù)區(qū)域內(nèi)密度值最大的任務(wù)點(diǎn)的集合;pathG(ti,tj)為UGV從目標(biāo)ti到目標(biāo)tj所需時(shí)間。

2.2.1.2 對(duì)UAV的任務(wù)分配

粒子適應(yīng)度值表示為各UAV完成被分配的任務(wù)所用時(shí)間與到達(dá)降落點(diǎn)所用時(shí)間之和。

(21)

2.2.1.3 對(duì)UGV的任務(wù)分配

粒子適應(yīng)度值表示為UGV完成被分配的任務(wù)所用時(shí)間與等待全部UAV降落完成所用時(shí)間之和：

(22)

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

2.2.2 粒子表示

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

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

2.2.3 交叉操作

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

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

2.2.4 變異操作

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

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

2.2.5 粒子更新策略

對(duì)UGV任務(wù)分配時(shí),只有當(dāng)新粒子的適應(yīng)度值小于舊粒子且新粒子滿足回收約束條件式(9)和任務(wù)時(shí)序約束條件式(12)時(shí)才更新粒子。

對(duì)子任務(wù)區(qū)域任務(wù)分配時(shí),只有當(dāng)新粒子的適應(yīng)度值小于舊粒子才更新粒子。

2.2.6 極值更新策略

極值更新分為個(gè)體極值更新和群體極值更新：

1) 個(gè)體極值更新：當(dāng)新粒子的適應(yīng)度值小于舊粒子極值的適應(yīng)度時(shí),更新新粒子為個(gè)體極值。

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

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

② UGV任務(wù)分配和子任務(wù)區(qū)域任務(wù)分配：只有當(dāng)所有個(gè)體極值中最小適應(yīng)度值小于群體極值的適應(yīng)度值時(shí),才更新該個(gè)體極值為群體極值。

3 仿真實(shí)驗(yàn)

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

3.1 聚類效果評(píng)估

在12 000 m×12 000 m作戰(zhàn)場(chǎng)景下使用均勻分布隨機(jī)生成50個(gè)目標(biāo)點(diǎn),圖7給出了使用密度值最大聚類進(jìn)行子任務(wù)區(qū)域劃分的效果。

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

本文使用Davies-Bouldin指數(shù)(DBI)為評(píng)價(jià)標(biāo)準(zhǔn)：

(23)

DBI值越小,簇內(nèi)的目標(biāo)點(diǎn)分布越緊密,簇間的最小距離越大,這符合本文對(duì)子區(qū)域劃分的要求。

表1給出了在12 000 m×12 000 m作戰(zhàn)場(chǎng)景下使用密度值最大聚類、DBSCAN和k-means算法進(jìn)行聚類的效果評(píng)估。其中密度值最大聚類的鄰域半徑、密度閾值由重要陣地的假設(shè)得到,簇距離閾值由多次實(shí)驗(yàn)獲得;DBSCAN算法采用保留噪聲點(diǎn)的方式,其密度閾值由多次實(shí)驗(yàn)獲得;k-means算法隨機(jī)選擇初始中心點(diǎn)?？梢钥闯?密度值最大聚類可以得到子區(qū)域內(nèi)目標(biāo)點(diǎn)分布更緊密、子區(qū)域間距離更大的任務(wù)區(qū)域劃分。

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

3.2 較小范圍內(nèi)的任務(wù)分配仿真

6 000 m×6 000 m范圍內(nèi)的目標(biāo)分布如圖8所示,隨機(jī)分布50個(gè)目標(biāo)點(diǎn)個(gè)目標(biāo)點(diǎn)由藍(lán)色點(diǎn)標(biāo)出,其中有17個(gè)隨機(jī)點(diǎn)為待打擊目標(biāo),由黑色方框標(biāo)記。黑色點(diǎn)為UGV的出發(fā)點(diǎn)。

圖8 6 000 m×6 000 m范圍內(nèi)目標(biāo)分布圖Fig.8 Target distribution map in the range of 6 000 m×6 000 m

多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配方法的參數(shù)如表2所示。多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配結(jié)果如表3和圖9所示。

表2 6 000 m×6 000 m范圍協(xié)同任務(wù)分配方法參數(shù)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范圍協(xié)同任務(wù)分配結(jié)果Table 3 Collaborative task allocation in the range of 6 000 m×6 000 m

圖9 6 000 m×6 000 m范圍內(nèi)協(xié)同任務(wù)分配示意圖Fig.9 Schematic diagram of the collaborative taskallocation in the range of 6 000 m×6 000 m

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

圖9為協(xié)同任務(wù)分配結(jié)果的示意圖。各UAV飛行時(shí)間的收斂曲線如圖10所示,從圖中可以看出混合粒子群優(yōu)化算法在第555次迭代中得到滿足航程約束式(2)的解,在1 800次迭代后基本收斂到穩(wěn)定值。整個(gè)多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配計(jì)算用時(shí)859.9 s。

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

3.3 較大范圍內(nèi)的任務(wù)分配仿真

12 000 m×12 000 m范圍內(nèi)的目標(biāo)分布如圖11所示,隨機(jī)分布50個(gè)目標(biāo)點(diǎn)由藍(lán)色點(diǎn)標(biāo)出,其中有17個(gè)隨機(jī)點(diǎn)為待打擊目標(biāo),由黑色方框標(biāo)記。黑色點(diǎn)為UGV的出發(fā)點(diǎn)。

圖11 12 000 m×12 000 m范圍內(nèi)目標(biāo)分布圖Fig.11 Target distribution map in the range of 12 000 m×12 000 m

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

表4 12 000 m×12 000 m范圍不劃分子任務(wù)區(qū)域的協(xié)同任務(wù)分配方法參數(shù)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范圍不聚類劃分子任務(wù)區(qū)域的協(xié)同任務(wù)分配結(jié)果Table 5 Task allocation result without clustering in the range of 12 000 m×12 000 m

結(jié)合密度值最大聚類算法對(duì)作戰(zhàn)區(qū)域進(jìn)行劃分,空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配方法的參數(shù)如表6所示。密度值最大聚類將作戰(zhàn)區(qū)域劃分為 16個(gè)子任務(wù)區(qū)域,子任務(wù)區(qū)域的劃分和任務(wù)分配結(jié)果如圖12所示。

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

圖12 子任務(wù)區(qū)域的劃分和任務(wù)分配Fig.12 Clustering and task allocation

圖13 12 000 m×12 000 m范圍內(nèi)多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配示意圖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為多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配結(jié)果的示意圖。整個(gè)協(xié)同任務(wù)分配計(jì)算用時(shí)277.93 s。

4 結(jié)論

本文首先基于多目標(biāo)、大面積的戰(zhàn)場(chǎng)環(huán)境假設(shè),構(gòu)建空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配模型,提出一種多目標(biāo)空地異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配方法,最后通過兩種不同的環(huán)境中的仿真實(shí)驗(yàn),證明了本文方法的有效性。得出以下主要結(jié)論：

1) 在較小作戰(zhàn)環(huán)境內(nèi),本文方法能夠滿足約束條件,有效地為空地異構(gòu)無人系統(tǒng)進(jìn)行協(xié)同任務(wù)分配。

2) 在較大作戰(zhàn)環(huán)境內(nèi),由于約束條件限制,UAVs無法在一次出動(dòng)中完成設(shè)定任務(wù),本文方法通過結(jié)合密度值最大聚類、混合粒子群優(yōu)化算法,將整個(gè)戰(zhàn)場(chǎng)劃分為多個(gè)子任務(wù)區(qū)域,并為空地異構(gòu)無人系統(tǒng)在區(qū)域間轉(zhuǎn)移和區(qū)域內(nèi)作戰(zhàn)進(jìn)行協(xié)同任務(wù)分配,使其滿足約束條件。