通信延遲約束下多無人機(jī)任務(wù)指派沖突消解

符小衛(wèi), 馮 鵬, 高曉光, 劉 重

(西北工業(yè)大學(xué)電子信息學(xué)院, 陜西 西安 710072)

0 引 言

近年來,隨著對無人機(jī)(unmanned aerial vehicle, UAV)作戰(zhàn)的深入探索,多架UAV協(xié)同完成指定任務(wù)成為研究的重點(diǎn)方向。多UAV(multi UAV,multi-UAV)協(xié)同作戰(zhàn)是指在不確定性的戰(zhàn)場環(huán)境下布放成群的[1]中小型UAV,在廣闊的空域范圍內(nèi)對UAV編隊進(jìn)行任務(wù)分配[2]和航路規(guī)劃[3],以完成搜索打擊等一系列任務(wù)。同時,由于單架UAV能力有限,僅能基于自身的傳感器和局部信息進(jìn)行控制與決策,所以UAV編隊需要通過機(jī)間通信實(shí)現(xiàn)高效率的[4]協(xié)同任務(wù)指派。

multi-UAV任務(wù)指派是編隊完成協(xié)同搜索[5-6]之后面臨的另一重要課題,研究的領(lǐng)域有很多方面,例如通信約束[7-8]、異構(gòu)性[9-10]以及UAV集群[11-12]的任務(wù)分配等。在早期,大多數(shù)研究的是中心式任務(wù)指派結(jié)構(gòu)[13-15],即任務(wù)指派中心站收集每架UAV的局部信息,并基于所有信息為UAV編隊進(jìn)行任務(wù)指派。之后,分布式任務(wù)指派結(jié)構(gòu)[16-17]逐漸成為主流。在分布式結(jié)構(gòu)下,由于每架UAV對于戰(zhàn)場情景認(rèn)知的不一致,編隊可能會生成相互沖突的任務(wù)指派方案,此時一致性算法能夠有效地解決沖突。文獻(xiàn)[18-19]運(yùn)用卡爾曼濾波器(Kalman filter,KF)進(jìn)行信息處理,保證編隊信息的一致性,從而實(shí)現(xiàn)無沖突的任務(wù)指派。文獻(xiàn)[20]提出僅在基于不同認(rèn)知信息生成的指派方案存在差異時才建立通信,以較小的通信代價保證了任務(wù)指派的一致性。拍賣算法(auction algorithm,AA)[21]是另一種有效的任務(wù)指派方法。文獻(xiàn)[22]建立競標(biāo)中心接收所有UAV的投標(biāo)信息,并根據(jù)預(yù)設(shè)的價值評估規(guī)則從中選擇具有最大價值的投標(biāo)。文獻(xiàn)[23]使用交換手段,并通過鏈接低通信代價的本地談判環(huán)節(jié)來保持動態(tài)化復(fù)雜環(huán)境下拍賣結(jié)果的最佳性。但由于以上文獻(xiàn)的算法實(shí)時性較差,不能適應(yīng)快速變化的戰(zhàn)場環(huán)境[24];并且為了達(dá)到一致的任務(wù)指派,需要大量的機(jī)間通信,這在存在通信限制的真實(shí)環(huán)境中很難實(shí)現(xiàn)。

由于通信延遲和丟包等約束的存在,編隊內(nèi)信息流存在不完整性和不確定性,由此導(dǎo)致各架UAV已知信息集合的差異化。差異化的信息集合會生成不一致的任務(wù)指派方案,進(jìn)而導(dǎo)致指派沖突。由此可見,通信約束會嚴(yán)重影響任務(wù)指派的可靠性,破壞任務(wù)指派的時序要求。因此,UAV編隊在任務(wù)指派過程中必須考慮通信系統(tǒng)中的不確定性因素。

本文針對multi-UAV協(xié)同任務(wù)指派過程中的任務(wù)沖突問題,設(shè)計了一種帶比較閾值的任務(wù)指派沖突預(yù)測及消解機(jī)制。該機(jī)制對由局部信息生成的本地收益矩陣進(jìn)行進(jìn)一步分析處理,設(shè)計比較閾值對矩陣中最大兩項收益值進(jìn)行比較分析,從而預(yù)測可能存在的指派沖突,并進(jìn)一步消解沖突。

最后,本文在MultiUAV2[25]仿真平臺上對提出的帶比較閾值的沖突消解機(jī)制進(jìn)行仿真驗(yàn)證。結(jié)果表明,提出的算法能提高UAV編隊在通信約束條件下的任務(wù)指派性能。

1 multi-UAV協(xié)同任務(wù)指派模型

1.1 UAV運(yùn)動模型

本文設(shè)定編隊中每個UAV都運(yùn)行相同的簡化動力學(xué)模型,即去掉高度自由度,且UAV具有恒定的前進(jìn)速度及按最大轉(zhuǎn)彎速率進(jìn)行轉(zhuǎn)向。

基于以上假設(shè),動力學(xué)方程為

(1)

式中,x、y為UAV的橫坐標(biāo)和縱坐標(biāo);v、θ、Ωmax為UAV的速度、航跡方位角和最大轉(zhuǎn)彎率;i表示UAV編號;ui為輸入控制變量,且

ui={-1,0,1}

(2)

式中,ui=-1表示左轉(zhuǎn)向;ui=0表示直線飛行;ui=1表示右轉(zhuǎn)向。假定每架UAV的最大轉(zhuǎn)彎速率和標(biāo)稱速度是相同的。

1.2 multi-UAV協(xié)同任務(wù)指派模型

multi-UAV協(xié)同任務(wù)指派是以任務(wù)收益為基礎(chǔ),選擇對于UAV編隊最優(yōu)的任務(wù)執(zhí)行方案。而任務(wù)執(zhí)行成本或收益與到達(dá)任務(wù)執(zhí)行位置的路徑長度或時間有直接的關(guān)系。

設(shè)定由Nu架UAV組成的UAV編隊,即UAV集合為

U={1,2,…,Nu}

(3)

經(jīng)過搜索發(fā)現(xiàn)的目標(biāo),根據(jù)摧毀目標(biāo)相應(yīng)的收益,劃分到已知類別中。當(dāng)發(fā)現(xiàn)目標(biāo)時,用j對目標(biāo)進(jìn)行編號,可以得到j(luò)=1,2,…,Nt,其中Nt是發(fā)現(xiàn)的目標(biāo)數(shù)量,設(shè)定目標(biāo)集合為

T={1,2,…,Nt}

(4)

Vj表示目標(biāo)j的價值。假設(shè)UAV在開始執(zhí)行任務(wù)時,沒有關(guān)于目標(biāo)數(shù)目和位置的具體信息,但潛在目標(biāo)類型的相關(guān)信息是已知的。

UAV默認(rèn)執(zhí)行對全域的搜索任務(wù),同時還對每個目標(biāo)需要執(zhí)行分類、攻擊和毀傷評估3類任務(wù),即對每個目標(biāo)執(zhí)行的任務(wù)集合為

M={C,A,V}

(5)

式中,C表示分類任務(wù);A表示攻擊任務(wù);V表示毀傷評估任務(wù)。UAV執(zhí)行任務(wù)必須滿足嚴(yán)格的順序要求,即先分類后攻擊最后毀傷評估。且對目標(biāo)每項任務(wù)的完成會導(dǎo)致目標(biāo)狀態(tài)的更新,產(chǎn)生下一項要完成的任務(wù),直至所有任務(wù)全部完成。Pc、Pk、Pv分別表示成功執(zhí)行分類、攻擊、毀傷評估任務(wù)的概率。

令m為UAV所需完成的任務(wù)編號,Nm表示對目標(biāo)執(zhí)行的任務(wù)數(shù)量。UAV可以執(zhí)行4種不同的任務(wù),即搜索(m=0)、分類(m=1)、攻擊(m=2)、毀傷評估(m=3)。令Ns=Nm·Nt表示UAV對所有目標(biāo)需要執(zhí)行的任務(wù)總數(shù),則

S={1,2,…,Ns}

(6)

代表任務(wù)指派與執(zhí)行的獨(dú)立階段。在每個階段中,只允許一架UAV對一個目標(biāo)執(zhí)行一種任務(wù)。在這里,階段的意義只是在算法中人為地分割任務(wù)指派的過程,并不存在于實(shí)際的任務(wù)執(zhí)行中。

定義一個二元決策變量，即

Xi,j,k∈{0,1}

(7)

當(dāng)UAVi∈U在算法階段k∈S對目標(biāo)j∈T執(zhí)行任務(wù)時,Xi,j,k=1;否則,Xi,j,k=0。

2 基本指派算法

有容量限制的轉(zhuǎn)運(yùn)指派算法用于分時段網(wǎng)絡(luò)最優(yōu)化模型,每次運(yùn)行該模型,都為UAV編隊進(jìn)行任務(wù)指派。該模型在離散時間點(diǎn)上,在所有UAV上同時運(yùn)行,并為每架UAV指派最多一項任務(wù)。當(dāng)發(fā)現(xiàn)新目標(biāo)或目標(biāo)狀態(tài)改變時,新信息輸入到模型中,算法都會被再次運(yùn)行解算。這一線性規(guī)劃能夠以網(wǎng)絡(luò)流程的形式進(jìn)行描述,如圖1所示。

圖1 multi-UAV任務(wù)指派網(wǎng)絡(luò)流圖Fig.1 Flow chart of multi-UAV assignment network

有容量限制的轉(zhuǎn)運(yùn)指派網(wǎng)絡(luò)優(yōu)化模型可表示為

(8)

約束條件為

?i=1,2,…,Nu

(9)

(10)

(11)

3 分布式估計與沖突消解機(jī)制

3.1 分布式估計

為了運(yùn)行分布式協(xié)同任務(wù)指派算法,每架UAV都需要友機(jī)的現(xiàn)時位置信息。為了提高UAV編隊的資源利用和作戰(zhàn)性能,UAV只在必要的時刻開啟通信,交流位置狀態(tài)信息。又由于存在著通信延遲的影響,需要本機(jī)對友機(jī)的位置狀態(tài)進(jìn)行預(yù)測和估計,這就是分布式估計。本文設(shè)計運(yùn)用KF對UAV位置狀態(tài)進(jìn)行預(yù)測和估計。

把UAV動力學(xué)模型改寫為

(12)

式中,xi=[xi,yi,vxi,vyi]T;i∈U表示UAV編號;ωi表示外部干擾因素。

(13)

為了分布式估計,需要把每個UAV動力學(xué)模型離散化表示,即

xi[n]=Φxi[n-1]+Bi[n-1]ui[n-1]+Γωi[n-1]

(14)

(15)

式中,離散周期T1等于量測周期。量測方程為

(16)

式中,vi[n]∈R2為零均值量測噪聲序列,以及

(17)

Pi[n/n-1]=ΦPi[n-1]ΦT+Qaw

Ki[n]=Pi[n/n-1]HT(HPi[n/n-1]HT+Ri)-1

Pi[n]=Ki[n]RiKi[n]T+

(I-Ki[n]H)Pi[n/n-1](I-Ki[n]H)T

(18)

(19)

每架UAV同時運(yùn)行所有動力學(xué)模型,對所有UAV的位置狀態(tài)進(jìn)行實(shí)時估計與判斷，即

xi,l[n+1]=Φxi,l[n]+Bi,l[n]ui,l[n]

(20)

式中,xi,l表示UAV(i∈U)運(yùn)行UAV(l∈U)的動力學(xué)模型對其位置狀態(tài)的估計。再定義本地位置狀態(tài)誤差為

(21)

當(dāng)該誤差大于某一給定的閾值時,觸發(fā)糾偏機(jī)制。判定式為

ei[n]TEei[n]>ε1

(22)

(23)

模型更新后,本地系統(tǒng)誤差為零,即ei[n]=0。在UAVi廣播位置信息后,周圍友機(jī)經(jīng)過一段時間延遲,即在ni+δil[ni]時刻接收到此信息。此處,δil[ni]表示時變通信延遲,與UAVi和UAVl的相對位置有關(guān)。UAVl接收到延遲的信息,更新估計模型,以此更加準(zhǔn)確地估計UAVi的狀態(tài)信息。UAVl估計UAVi的位置為

(24)

3.2 沖突預(yù)測與消解

收益矩陣的最大值所代表的任務(wù)即是本階段所要指派的任務(wù)。本地收益值計算為

(25)

估計友機(jī)的收益值為

Bl,j,s=f(xi,l[n])

(26)

再深入探究,正是由于收益矩陣的最大值與次大值相差很小,所以輕微的計算誤差就會產(chǎn)生大小關(guān)系的轉(zhuǎn)變,從而導(dǎo)致任務(wù)指派的沖突。由此抓到了問題的關(guān)鍵。

本文提出,在收益矩陣形成后,比較其最大元素和次大元素的差值,若小于某給定值ε2,則判定可能存在沖突,反之則沒有沖突。計算每一階段的收益矩陣后,都要用該閾值ε2檢測是否存在潛在沖突。

在某一階段k∈S,UAVi∈U首先選擇其收益矩陣的最大元素max1i,j(Bi,j,k),然后找到矩陣的次大元素max2i,j(Bi,j,k),其中j∈T。若

max1i,j(Bi,j,k)-max2i,j(Bi,j,k)<ε2(ε2>0)

(27)

成立,則表示存在潛在沖突。

閾值ε2大小的選取關(guān)系到整個算法沖突預(yù)測的性能。選取較小數(shù)值的ε2可以減少UAV通信,但也降低了成功預(yù)測沖突的概率;而正好相反,大值選取較大數(shù)值的ε2是以增加網(wǎng)絡(luò)的通信壓力為代價,提高成功預(yù)測沖突的可能性。

結(jié)合黨和國家大政方針和重要紀(jì)念活動制訂宣講計劃和方案，增強(qiáng)時政宣講時效性。將時政宣講與課堂教學(xué)有機(jī)結(jié)合。每次思政課必須實(shí)施“時政5分鐘”，關(guān)注最新國內(nèi)國際熱點(diǎn)話題，教師做好點(diǎn)評。利用班會或者第二課堂活動由教師指導(dǎo)開展時事熱點(diǎn)專題討論。每位教師每學(xué)期至少進(jìn)行集體時政宣講1次，人數(shù)不少于2個自然班。鼓勵教師積極參加時政宣講活動。

當(dāng)式(27)成立時,表明算法任務(wù)指派可能存在沖突。此時,本地UAV開啟通信模式,向友機(jī)廣播包含量測信息的投標(biāo)向量

φi=[ijmkβi]T

(28)

式中,i、j、m、k∈Z+分別表示UAV編號、任務(wù)所針對的目標(biāo)、指派任務(wù)及當(dāng)前任務(wù)階段。βi=max1i,j(Bi,j,k)表示本地收益矩陣的最大元素。

友機(jī)收到廣播信息后,檢查是否與自身得到的任務(wù)指派方案一致,并把指派方案的所有信息廣播出去。當(dāng)UAV收到來自所有友機(jī)的反饋信息后,比較所有方案的收益,選擇收益最大的任務(wù)作為最終指派方案。因?yàn)楫?dāng)開啟廣播通信后,每架UAV都會收到來自所有UAV的信息,這些信息是相同的,所以最終所有UAV會做出相同的任務(wù)指派決策。這就是整個沖突消解的過程。

3.3 UAV優(yōu)先級設(shè)定

當(dāng)UAV編隊成功預(yù)測沖突并進(jìn)行廣播通信后,若2架或以上的UAV提出的指派任務(wù)取得相同的收益值,則各架UAV在選擇最終指派方案時就會產(chǎn)生沖突:到底選擇其中的哪一架執(zhí)行任務(wù)？為了解決這個沖突,考慮對UAV編隊設(shè)置優(yōu)先級。設(shè)Π表示對UAV的優(yōu)先級排序,且UAVi∈U的優(yōu)先級為

Πi=i(?i=1,2,…,Nu)

(29)

此方法等同于對所有UAV進(jìn)行編號,序列號碼越小的UAV擁有越高的優(yōu)先級。當(dāng)發(fā)生上述指派沖突時,比較所有收益值相同的任務(wù)的源指派UAV的優(yōu)先級,把優(yōu)先級最高UAV指派的任務(wù)設(shè)置為最終執(zhí)行的任務(wù)。

4 仿真驗(yàn)證

為驗(yàn)證本文算法的有效性,在MultiUAV2仿真平臺上進(jìn)行仿真驗(yàn)證。

為了與本文提出的沖突消解機(jī)制比較,本章采用簡單的協(xié)商決策方法作為對比算法。即當(dāng)沖突方案的不同執(zhí)行方(UAV)到達(dá)沖突任務(wù)地點(diǎn)時,相互通信后發(fā)現(xiàn)沖突存在;交流狀態(tài)信息后對沖突目標(biāo)進(jìn)行局部的重新指派;勝者執(zhí)行原任務(wù),敗者離開該目標(biāo),飛向下一項任務(wù)地點(diǎn)。

4.1 算法驗(yàn)證仿真

仿真將任務(wù)區(qū)域設(shè)定在6 km×20 km的區(qū)域范圍內(nèi),區(qū)域內(nèi)設(shè)定了3個目標(biāo),使用4架相同類型的UAV組成編隊執(zhí)行搜索、分類、打擊及毀傷評估任務(wù)。當(dāng)UAV編隊完成所有任務(wù)或仿真時間達(dá)到200 s時仿真停止。設(shè)定UAV的初始航向角是0°,最大轉(zhuǎn)彎率Ωmax=0.2 rad/s,恒定速度馬赫數(shù)為0.333,傳感器寬度為0.6 km。設(shè)定UAV編隊的通信延遲為0.5 s,算法中ε2取值為2。設(shè)定編隊成功進(jìn)行分類、打擊及評估的概率分別是Pc=0.6、Pk=0.8、Pv=1.0。UAV的初始位置和目標(biāo)位置如表1和表2所示。

表1 UAVs初始位置

表2 目標(biāo)位置

采用簡單的協(xié)商決策方法時,編隊完成對全部目標(biāo)的分類任務(wù)、1號目標(biāo)和3號目標(biāo)的打擊任務(wù)及1號目標(biāo)的毀傷評估任務(wù),但未完成對2號目標(biāo)的打擊和毀傷評估任務(wù)及對3號目標(biāo)的毀傷評估。UAV編隊的完整軌跡如圖2所示。

圖2 簡單協(xié)商決策時UAV編隊的完整航跡Fig.2 Whole trajectory of UAV formation with simple negotiation decision making

在①處,1號UAV與3號UAV同時飛向3號目標(biāo)位置,試圖對3號目標(biāo)執(zhí)行任務(wù),這就是由于編隊信息不一致導(dǎo)致的任務(wù)指派沖突。當(dāng)他們逐漸接近時,通過相互通信發(fā)現(xiàn)彼此的任務(wù)方案存在沖突,在重新計算任務(wù)收益后,最終由具有較高任務(wù)收益的1號UAV對3號目標(biāo)執(zhí)行任務(wù)。而此時3號UAV不得不盤旋轉(zhuǎn)彎飛向下一任務(wù)點(diǎn)。在這個過程中,任務(wù)沖突浪費(fèi)了3號UAV的大量時間與資源,大大降低編隊執(zhí)行任務(wù)的效率。

在②處,1號UAV在空中盤旋,等待對1號目標(biāo)執(zhí)行毀傷評估任務(wù)。盤旋等待的過程浪費(fèi)了大量的時間與資源,卻沒有任何收益。而且在復(fù)雜未知的戰(zhàn)場環(huán)境中,原地盤旋極易導(dǎo)致UAV暴露,對整個編隊產(chǎn)生巨大威脅。好的算法應(yīng)該盡量避免盤旋等待的頻次與時間。UAV過多的盤旋等待浪費(fèi)任務(wù)執(zhí)行時間和資源,大大影響編隊執(zhí)行任務(wù)的效率。優(yōu)良的算法通過精確的計算與指派,有效避免UAV的盤旋等待,使編隊更快地完成既定任務(wù)。

在③處,4號UAV在遠(yuǎn)離戰(zhàn)場的情境下再次加入戰(zhàn)場,對2號目標(biāo)執(zhí)行任務(wù),這特別不符合任務(wù)收益最大化的目標(biāo)。這種情況是由于在不良的通信條件下,編隊內(nèi)各UAV的信息不能一致,UAV單體基于自身信息達(dá)到的局部最優(yōu)并不是編隊的全局最優(yōu)。

當(dāng)加入本文提出的沖突消解機(jī)制后,UAV編隊完成對所有目標(biāo)的分類、打擊以及毀傷評估任務(wù)。編隊的完整航跡如圖3所示。

圖3 帶沖突消解機(jī)制時UAV編隊的完整航跡Fig.3 Whole trajectory of UAV formation with conflictresolution mechanism

在①處,1號UAV與3號UAV正在飛向2號目標(biāo)處,準(zhǔn)備相繼對2號目標(biāo)完成打擊與毀傷評估任務(wù)。由于沖突消解機(jī)制的存在,即使1號UAV與3號UAV距離很近,任務(wù)收益相近,也能正確地指派任務(wù)執(zhí)行的時序,保證在單體信息相近的情況下實(shí)現(xiàn)無沖突的任務(wù)指派。

在②處,4號UAV對1號目標(biāo)執(zhí)行攻擊任務(wù)后自毀,編隊在很早的時間點(diǎn)就完成對1號目標(biāo)的3項任務(wù),整個過程緊湊合理,充分利用編隊資源。沒有出現(xiàn)圖2中所示的4號UAV在未得到任何任務(wù)指派的情況下遠(yuǎn)離戰(zhàn)場,而后又不合理地返回戰(zhàn)場執(zhí)行任務(wù)的情況。

通過仿真表明,提出的沖突消解機(jī)制能有效地解決任務(wù)指派過程中的任務(wù)沖突問題,相較于一般方法大大提高了編隊的任務(wù)執(zhí)行效率。由于沖突消解與任務(wù)指派同時完成,發(fā)生在任務(wù)執(zhí)行之前,這對編隊的航路規(guī)劃和自身生存保障都有極大的積極作用。

4.2 蒙特卡羅仿真

為說明本文提出的沖突消解機(jī)制對UAV編隊任務(wù)指派性能的提升,又在MultiUAV2仿真平臺上進(jìn)行蒙特卡羅仿真。仿真采用任務(wù)完成率作為性能分析的指標(biāo)。

設(shè)定通信延遲為1 s,設(shè)置3種情況如表3所示。通過50次蒙特卡羅仿真對所提出的沖突消解機(jī)制在通信延遲情況下的性能進(jìn)行評估。仿真中的變量為隨機(jī)產(chǎn)生的目標(biāo)位置,其他的基本設(shè)定與仿真1相同。

表3 蒙特卡羅仿真算例設(shè)置

圖4和圖5分別表示編隊在1 s通信延遲下采用簡單的協(xié)商決策方法和加入沖突消解機(jī)制后執(zhí)行任務(wù)全過程的通信數(shù)據(jù)率。

圖4 情況1情境下的通信數(shù)據(jù)率Fig.4 Communication data rate in case 1

圖5 情況2情境下的通信數(shù)據(jù)率Fig.5 Communication data rate in case 2

圖4中,峰值數(shù)據(jù)率為50.625 kb/s,平均數(shù)據(jù)率為0.666 2 kb/s,存在至少15個通信高峰;圖5中,峰值通信率為32.5 kb/s,平均數(shù)據(jù)率為0.303 3 kb/s,存在10個通信高峰。對比可以看出,在加入沖突消解機(jī)制后,通信數(shù)據(jù)率明顯減小,說明該機(jī)制降低了編隊內(nèi)的通信頻次,節(jié)省了大量的通信資源,在應(yīng)對惡劣通信環(huán)境時有很好的表現(xiàn)。

圖6表示編隊的攻擊任務(wù)和毀傷評估任務(wù)在不同場景下的對比情況,以平均任務(wù)完成率為依據(jù)。

圖6 不同情境的任務(wù)完成率對比Fig.6 Comparison of task completion rate in different cases

從圖6中可以看出,完整的通信環(huán)境下協(xié)同控制效果是最好的,攻擊和毀傷評估的任務(wù)完成率分別為92%和70.7%。當(dāng)存在通信時延時,效果會變差,攻擊和毀傷評估的任務(wù)完成率分別為61%和46%;在加入本文提出的沖突消解機(jī)制后,兩項任務(wù)的完成率分別為80.3%和67.7%,編隊的任務(wù)執(zhí)行能力有了很大提升。該蒙特卡羅仿真驗(yàn)證了本文提出的沖突消解機(jī)制的有效性。

針對通信延遲量對本文算法性能的影響,通過在不同通信延遲條件下與簡單協(xié)商決策進(jìn)行對比驗(yàn)證,并從以下兩方面進(jìn)行分析。

(1) 通信延遲量對任務(wù)完成率的影響。隨著通信延遲量的增加,UAV之間狀態(tài)信息和估計結(jié)果的差異不斷擴(kuò)大,因此導(dǎo)致指派沖突的存在概率大大增加。編隊頻繁預(yù)測到潛在沖突并開啟通信消解沖突,降低了任務(wù)指派的有效性和可靠性,編隊取得任務(wù)指派一致性的時間也不斷增長。因此,隨著通信延遲的增加,任務(wù)完成率不斷下降。相比之下,沖突消解機(jī)制可以通過調(diào)節(jié)閾值ε2以靈活應(yīng)對通信延遲量的變化。在通信延遲較高時,可以選擇較小的ε2以提高任務(wù)指派的效率。因此,沖突消解機(jī)制受通信延遲的影響更小,具有更優(yōu)良的表現(xiàn)。

(2) 通信延遲量對算法計算時間的影響。如(1)所述,通信延遲量的增加主要導(dǎo)致沖突消解過程反復(fù)運(yùn)行,解決沖突所需的算法輪次不斷增多。但單次的沖突預(yù)測及消解算法與通信延遲沒有關(guān)聯(lián),因此算法的計算時間受通信延遲量的影響較小。

以上仿真實(shí)例證明,本文提出的算法可以有效地預(yù)測和消解指派沖突,同時在這個過程中,可以大大降低通信頻率,減少通信代價。

5 結(jié) 論

在本文中,為研究multi-UAV任務(wù)指派過程中的沖突消解,首先建立UAV動力學(xué)模型以及任務(wù)指派模型。以分布式有容量限制的轉(zhuǎn)運(yùn)指派算法為基礎(chǔ),提出合理的算法解決由通信延遲導(dǎo)致的指派沖突。通過仿真對比表明,該算法能真實(shí)有效地預(yù)測和解決指派過程中的沖突,保證UAV編隊完成對指定空域目標(biāo)的搜索打擊任務(wù)。但此算法也有不足,在通信條件極其惡劣時,不能較好地解決沖突。進(jìn)一步的工作是研究在高通信延遲和低通信效率下對沖突的預(yù)測和解決。

參考文獻(xiàn)：

[1] SURESH M, GHOSE D. UAV grouping and coordination tactics for ground attack missions[J]. IEEE Trans.on Aerospace & Electronics Systems, 2012, 48(1): 673-692.

[2] ELLOUMI S. An efficient linearization for the constrained task allocation problem[J].Applied Spectroscopy, 2015,56(9):1170-1175.

[3] DI B, ZHOU R, DUAN H B. Potential field based receding horizon motion planning for centrality-aware multiple UAV coope-rative surveillance[J].Aerospace Science and Technology,2015,46: 386-397.

[4] LI J, HAN Y. Optimal resource allocation for packet delay minimization in multi-layer UAV networks[J]. IEEE Communications Letters, 2017, 21(3): 580-583.

[5] HU J W, XIE L H, LUM K J, et al. Multi-agent information fusion and cooperative control in target search[J]. IEEE Trans.on Control Systems Technology, 2013, 21(4): 1223-1235.

[6] ZHAO W, MENG Q, CHUNG P W. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario[J]. IEEE Trans.on Cybernetics, 2016, 46(4): 902-915.

[7] 符小衛(wèi), 李建, 高曉光. 帶通信約束的多無人機(jī)協(xié)同搜索中的目標(biāo)分配[J]. 航空學(xué)報, 2014, 35(5): 1347-1356.

FU X W, LI J, GAO X G. Target allocation in multi-UAV cooperative search with communication constraints[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(5): 1347-1356.

[8] LIU L, MICHAEL N, SHELL D A. Communication constrained task allocation with optimized local task swaps[J]. Autonomous Robots, 2015, 39(3): 429-444.

[9] 邸斌, 周銳, 丁全心. 多無人機(jī)分布式協(xié)同異構(gòu)任務(wù)分配[J]. 控制與決策, 2013, 28(2): 274-278.

DI B, ZHOU R, DING Q X. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and Decision, 2013, 28(2): 274-278.

[10] 孫海波,周銳,鄒麗,等.通信和測量受限條件下異構(gòu)多UAV分布式協(xié)同目標(biāo)跟蹤方法[J].航空學(xué)報,2011,32(2):299-310.

SUN H B, ZHOU R, ZOU L, et al. Distributed cooperation target tracking for heterogenous multi-UAV under communication and measurement constraints[J]. Acta Aeronautica et Astronautica Sinica, 2011, 32(2): 299-310.

[11] WEI Y, MADEY G R, BLAKE M B. Agent-based simulation for UAV swarm mission planning and execution[C]∥Proc.of the Agent-Directed Simulation Symposium, 2013: 7-14.

[12] WEI Y, BLAKE M B, MADEY G R. An operation-time simulation framework for UAV swarm configuration and mission planning[J].Procedia Computer Science,2013,18(1):1949-1958.

[13] BELLINGHAM J, TILLERSON M, RICHARDS A, et al. Multi-task allocation and path planning for cooperating UAVs[C]∥Proc.of the Conference on Cooperative Control:Models,2003:1-19.

[14] CASSANDRAS C, LI W. A receding horizon approach for solving some cooperative control problems[C]∥Proc.of the IEEE Conference on Decision and Control, 2002: 3760-3765.

[15] ALIGHANBARI M. Task assignment algorithms for teams of UAVs in dynamic environments[M]. Cambridge: Massachusetts Institute of Technology, 2004.

[16] CASTANON D, WU C. Distributed algorithms for dynamic reassignment[C]∥Proc.of the IEEE Conference of Decision and Control, 2003: 13-18.

[17] SHIMA T, RASMUSSEN S J, CHANDLER P. UAV team decision and control using efficient collaborative estimation[C]∥Proc.of the American Control Conference, 2005: 4107-4112.

[18] REN W, BEARD R, KINGSTON D. Multi-agent Kalman consensus with relative uncertainty[C]∥Proc.of the American Control Conference, 2005: 1865-1870.

[19] ALIGHANBARI M, HOW J P. An unbiased Kalman consensus algorithm[C]∥Proc.of the American Control Conference, 2006: 6.

[20] DIONNE D, RABBATH C A. Multi-UAV decentralized task allocation with intermittent communications: the DTC algorithm[C]∥Proc.of the American Control Conference, 2007: 5406-5411.

[21] BERTSEKAS D P. The auction algorithm for assignment and other network flow problems[J].Interfaces,1990,20(4):133-149.

[22] LAGOUDAKIS M G, BERHAULTT M, KOENIGT S, et al. Simple auctions with performance guarantees for multi-robot task allocation[C]∥Proc.of the IEEE/RSI International Confe-rence on Intelligent Robots and Systems, 2004, 40(3): 698-705.

[23] AHMED A, PATEL A, BROWN T, et al. Task assignment for a physical agent team via a dynamic forward/reverse auction mechanism[C]∥Proc.of the International Conference on Integration of Knowledge Intensive Multi-Agent Systems, 2004: 311-317.

[24] WEI C, HINDRIKS K V, JONKER C M. Dynamic task allocation for multi-robot search and retrieval tasks[J]. Applied Intelligence, 2016,2016(2): 1-19.

[25] RASMUSSEN S J, MITCHELL J W, CHANDLER P R, et al. Introduction to the MultiUAV2 simulation and its application to cooperative control research[C]∥Proc.of the American Control Conference, 2005: 4490-4501.