閆輝 包衛(wèi)東 王吉 張大宇

1.國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院湖南長(zhǎng)沙410073

隨著無線通信、導(dǎo)航飛控、結(jié)構(gòu)設(shè)計(jì)、機(jī)體材料等技術(shù)的快速發(fā)展,無人駕駛飛機(jī)(Unmanned Aerial Vehicle, UAV) 的性能水平不斷提升, 無人機(jī)代替人執(zhí)行軍事任務(wù)逐漸成為主流應(yīng)用方向[1], UAV 被廣泛應(yīng)用于物資運(yùn)輸、應(yīng)急救援和目標(biāo)跟蹤等領(lǐng)域中.然而,隨著應(yīng)用場(chǎng)景復(fù)雜性的增加,單個(gè)無人機(jī)暴露出續(xù)航能力、負(fù)載能力和計(jì)算能力不足等問題[2].多無人機(jī)協(xié)同憑借分布式架構(gòu), 提高了無人系統(tǒng)的靈活性和魯棒性,通過能力互補(bǔ)和行動(dòng)協(xié)調(diào),有效地減輕單個(gè)無人機(jī)的負(fù)擔(dān), 具備智能化程度高、機(jī)動(dòng)靈活性強(qiáng)、群體抗毀性好等優(yōu)勢(shì).因此,如何在多無人機(jī)之間實(shí)現(xiàn)高效快速的協(xié)同成為當(dāng)前研究的熱點(diǎn)問題[3].

多無人機(jī)協(xié)同目標(biāo)分配問題是多無人機(jī)協(xié)同技術(shù)中的重點(diǎn)與難點(diǎn)問題之一.與單個(gè)無人機(jī)相比,多無人機(jī)目標(biāo)分配面臨計(jì)算復(fù)雜度高、任務(wù)序列優(yōu)化、多無人機(jī)協(xié)調(diào)與協(xié)作等問題, 需要綜合權(quán)衡無人機(jī)電量、續(xù)航、速度、飛行距離等因素,給出多無人機(jī)的目標(biāo)分配與調(diào)度策略[4?5].目前已經(jīng)有學(xué)者在相關(guān)領(lǐng)域進(jìn)行了大量的研究,例如:文獻(xiàn)[6]針對(duì)復(fù)雜任務(wù)場(chǎng)景下無人機(jī)集群自組織偵察的特點(diǎn), 提出了一種面向集群自組織偵察的作戰(zhàn)建模與仿真方法.文獻(xiàn)[7]提出了一種基于交換匹配的UAV 部署算法來實(shí)現(xiàn)無人機(jī)部署的聯(lián)合優(yōu)化問題, 實(shí)現(xiàn)了計(jì)算復(fù)雜度和最優(yōu)性之間的良好平衡.文獻(xiàn)[8]利用間歇異步通信原理建立了分布式動(dòng)態(tài)任務(wù)分配模型, 實(shí)現(xiàn)了多無人機(jī)對(duì)多個(gè)運(yùn)動(dòng)目標(biāo)的路徑跟蹤.文獻(xiàn)[9] 提出了一種基于多無人機(jī)網(wǎng)絡(luò)的分布式數(shù)據(jù)融合算法框架,為多個(gè)UAV 融合現(xiàn)場(chǎng)數(shù)據(jù)提供了一種有效的方法.文獻(xiàn)[10]針對(duì)多無人機(jī)協(xié)同對(duì)地打擊的任務(wù)區(qū)集結(jié)問題, 建立了基于一致性理論的分布式控制結(jié)構(gòu).文獻(xiàn)[11]提出一種分層優(yōu)化的機(jī)制解決多無人機(jī)多任務(wù)航跡規(guī)劃問題.文獻(xiàn)[12] 建立了追求飛行成本最小并考慮時(shí)間約束的多無人機(jī)任務(wù)分配優(yōu)化模型,提出列生成算法對(duì)飛行方案進(jìn)行優(yōu)化.文獻(xiàn)[13]采用基于快速一致性控制算法的協(xié)同控制結(jié)構(gòu),在合作博弈框架下給出多無人機(jī)系統(tǒng)自組織協(xié)同與優(yōu)化控制問題描述.文獻(xiàn)[14]提出了一種基于蟻群優(yōu)化的方法, 該方法可以實(shí)現(xiàn)多無人機(jī)任務(wù)分配計(jì)算需求和解決方案質(zhì)量之間的平衡.文獻(xiàn)[15]針對(duì)多架無人機(jī)的航跡距離、安全性、時(shí)間以及空間的協(xié)同性進(jìn)行規(guī)劃, 運(yùn)用多目標(biāo)優(yōu)化算法生成多組可供選擇的解.值得注意的是,當(dāng)前的模型和方法在實(shí)際應(yīng)用中存在諸如嚴(yán)格的模型假設(shè)和高計(jì)算成本等缺點(diǎn).針對(duì)多無人機(jī)協(xié)同目標(biāo)分配問題中的實(shí)際約束,本文著眼于優(yōu)化多無人系統(tǒng)的整體電量消耗,提出了一種基于任務(wù)接力的多無人機(jī)協(xié)同目標(biāo)分配策略,以延長(zhǎng)多無人機(jī)系統(tǒng)協(xié)同工作時(shí)間.本文的主要工作如下:

1)將現(xiàn)實(shí)場(chǎng)景中目標(biāo)的地理空間約束建模為無向加權(quán)圖.

2) 建模了異構(gòu)目標(biāo)的重要度, 并提出重要度動(dòng)態(tài)變化模型.

3)提出了基于任務(wù)接力的多無人機(jī)協(xié)同調(diào)度策略及其在特殊場(chǎng)景下的拓展策略.

4)通過大量仿真實(shí)驗(yàn)驗(yàn)證了本文所提出方法的可行性與有效性.

1 問題描述

圖1 展示了多無人機(jī)協(xié)同目標(biāo)分配的典型場(chǎng)景,該場(chǎng)景可抽象成如下問題: 給定一定數(shù)量的無人機(jī)和目標(biāo),目標(biāo)的位置相對(duì)固定,無人機(jī)對(duì)目標(biāo)進(jìn)行監(jiān)視或打擊.每個(gè)目標(biāo)的重要程度不同,且會(huì)隨著時(shí)間的推移發(fā)生變化.每個(gè)目標(biāo)至少分配一架無人機(jī),且重要度越高的目標(biāo)需要分配的無人機(jī)越多.因此,當(dāng)目標(biāo)重要度發(fā)生變化時(shí), 多無人機(jī)系統(tǒng)的協(xié)同分配策略也要進(jìn)行相應(yīng)地調(diào)整.

圖1 多無人機(jī)協(xié)同目標(biāo)分配的典型場(chǎng)景Fig.1 Typical scenario of multi-UAV cooperative target allocation

下面給出多無人機(jī)協(xié)同目標(biāo)分配問題研究對(duì)象的數(shù)學(xué)描述.

1.1 無人機(jī)群建模

假設(shè)某無人機(jī)群共包含n架無人機(jī), 記為U={u1,u2,··· ,un},第i架無人機(jī)記為ui= {si,bi,其中si,bi,分別表示飛行速度、電池電量、無人機(jī)懸停能耗功率和無人機(jī)飛行能耗功率.本文將飛行速度設(shè)為常量, 無人機(jī)電池電量在執(zhí)行任務(wù)過程中逐漸減小.

1.2 目標(biāo)建模

綜合考慮目標(biāo)在地理空間上的離散性和無人機(jī)在目標(biāo)之間飛行的環(huán)境約束, 本文采用無向加權(quán)圖的形式對(duì)目標(biāo)進(jìn)行建模, 即G= {V,E,D,I}.其中,V表示目標(biāo)的集合,E表示連接目標(biāo)的邊集合,D是關(guān)聯(lián)邊距離的集合,I是目標(biāo)重要度的集合.假設(shè)場(chǎng)景中有m個(gè)目標(biāo),則目標(biāo)集合為V={v1,v2,··· ,vm}.

1.2.1 目標(biāo)編號(hào)方式

假定目標(biāo)之間構(gòu)成的無向加權(quán)圖是連通圖, 即任意兩個(gè)目標(biāo)之間至少存在一條可達(dá)路徑.為了提高基于任務(wù)接力的無人機(jī)調(diào)度策略的生成效率, 對(duì)目標(biāo)的編號(hào)方式進(jìn)行規(guī)范.

1) 選取連接度最小的目標(biāo)作為初始節(jié)點(diǎn), 記為目標(biāo)v1.若有多個(gè)目標(biāo)的連接度均為最小度,則在其中隨機(jī)選取一個(gè)目標(biāo)作為初始節(jié)點(diǎn).

2)在與目標(biāo)vi(1 ≤i

3)若目標(biāo)vi+1的連接度為1,則表明目標(biāo)vi+1僅與目標(biāo)vi相連.退回目標(biāo)vi,尋找除已編號(hào)目標(biāo)以外,vi一步可達(dá)的目標(biāo)節(jié)點(diǎn)中連接度最小的節(jié)點(diǎn),作為下一節(jié)點(diǎn),記為目標(biāo)vi+2.

4)重復(fù)上述步驟2 和步驟3 直至所有目標(biāo)完成編號(hào).

1.2.2 目標(biāo)距離計(jì)算

對(duì)于任意兩個(gè)目標(biāo)vj和vk,如果它們?cè)诘乩砜臻g中存在一條不經(jīng)過其他目標(biāo)而直接相連的通路,則將它們之間的邊表示為ej,k= 1.目標(biāo)之間的邊集可以表示如下.

如果ej,k= 1, 則它們間的距離記為dj,k, 邊的距離集D由式(2)確定:

考慮到任意兩個(gè)目標(biāo)之間至少存在一條路徑,雖然存在兩個(gè)目標(biāo)之間無法直接相連, 但是可以以邊的距離集D為基礎(chǔ), 通過Floyd-Warshall 算法[16]等方式計(jì)算無向加權(quán)圖中所有頂點(diǎn)對(duì)之間的最短路徑,進(jìn)而得到任意兩個(gè)目標(biāo)之間的最短路徑.本文將所有目標(biāo)對(duì)之間的最短路徑表示為二維矩陣, 如式(3)所示.

其中,wj,k表示目標(biāo)vj和vk之間的最短路徑.

1.2.3 目標(biāo)重要度建模

將無人機(jī)群執(zhí)行任務(wù)的總調(diào)度次數(shù)劃分為τ,記為T= {1,2,··· ,τ}.目標(biāo)vj在t時(shí)刻的重要度記為因此,目標(biāo)在t時(shí)刻的重要度集合如式(4)所示.

基于式(4),目標(biāo)的重要度集合I記為:

目標(biāo)重要度衡量目標(biāo)在實(shí)際場(chǎng)景中的重要程度,如目標(biāo)活動(dòng)范圍、目標(biāo)價(jià)值、目標(biāo)數(shù)量等,重要度越高的目標(biāo)所需分配的無人機(jī)數(shù)量越多.例如,一個(gè)包含10 架無人機(jī)的機(jī)群執(zhí)行監(jiān)視任務(wù),計(jì)劃對(duì)4 片區(qū)域進(jìn)行監(jiān)視,這4 片區(qū)域在t時(shí)刻出現(xiàn)敵軍的人數(shù)分別為10,40,20,30.按照目標(biāo)區(qū)域中包含的人數(shù)給出目標(biāo)的歸一化權(quán)重為0.1,0.4,0.2,0.3.進(jìn)一步,按照目標(biāo)歸一化權(quán)重為每個(gè)目標(biāo)分配無人機(jī).以第一個(gè)目標(biāo)為例,其歸一化權(quán)重為0.1,則需分配0.1×10=1架無人機(jī).依此類推,每個(gè)目標(biāo)需分配的無人機(jī)數(shù)量分別為1,4,2,3.值得注意的是,目標(biāo)權(quán)重歸一化過程中可能存在無法整除的情況, 而現(xiàn)實(shí)問題中無人機(jī)數(shù)量應(yīng)當(dāng)為整數(shù).因此,本文提出“個(gè)體近似+整體約束”的方式對(duì)需分配的無人機(jī)數(shù)量進(jìn)行取整.

“個(gè)體近似”是指先按照如上述例子的計(jì)算方法計(jì)算每個(gè)目標(biāo)需分配的無人機(jī)數(shù)量,并依次采用“四舍五入”的方式對(duì)目標(biāo)分配無人機(jī)數(shù)近似取整.特別地,由于每個(gè)目標(biāo)都至少分配1 架無人機(jī),本文規(guī)定當(dāng)目標(biāo)需分配無人機(jī)數(shù)量近似取整后為0 時(shí), 該目標(biāo)需分配的無人機(jī)數(shù)量強(qiáng)制設(shè)為1.

“整體約束”是指以實(shí)際無人機(jī)數(shù)量總和為約束,對(duì)“個(gè)體近似”后的目標(biāo)需分配無人機(jī)數(shù)量進(jìn)行整體調(diào)整, 消解需分配無人機(jī)數(shù)量總和與實(shí)際無人機(jī)數(shù)量總和不匹配的沖突.具體來講,“整體約束”分為以下3 條規(guī)則.

規(guī)則1.當(dāng)需分配無人機(jī)數(shù)量總和等于實(shí)際無人機(jī)數(shù)量總和時(shí), 目標(biāo)需分配無人機(jī)數(shù)量滿足整體約束,無需調(diào)整.

規(guī)則2.當(dāng)需分配無人機(jī)數(shù)量總和大于實(shí)際無人機(jī)數(shù)量總和時(shí),需分配無人機(jī)數(shù)量最多的目標(biāo)(同時(shí)存在多個(gè)時(shí),任選其一)分配無人機(jī)數(shù)量減1.重復(fù)此規(guī)則,直至規(guī)則1 被滿足.

規(guī)則3.當(dāng)需分配無人機(jī)數(shù)量總和小于實(shí)際無人機(jī)數(shù)量總和時(shí),需分配無人機(jī)數(shù)量最少的目標(biāo)(同時(shí)存在多個(gè)時(shí),任選其一)分配無人機(jī)數(shù)量加1.重復(fù)此規(guī)則,直至規(guī)則1 被滿足.

為了詳細(xì)闡述以“個(gè)體近似+整體約束”的方式對(duì)需分配的無人機(jī)數(shù)量進(jìn)行取整的過程, 下面以兩個(gè)例子分別闡述:

示例1.假定敵軍人數(shù)為20, 40, 20, 30, 每個(gè)目標(biāo)需分配的無人機(jī)數(shù)量約為1.8,3.6,1.8, 2.7.“個(gè)體近似”后需分配的無人機(jī)數(shù)量分別為2,4,2,3.按照“整體約束”規(guī)則2,調(diào)整后的需分配無人機(jī)數(shù)量分別為2,3,2,3.

示例2.假定敵軍人數(shù)為20, 40, 20, 10, 每個(gè)目標(biāo)需分配的無人機(jī)數(shù)量約為2.2,4.4,2.2, 1.1.“個(gè)體近似”后需分配的無人機(jī)數(shù)量分別為2,4,2,1.按照“整體約束”規(guī)則3,調(diào)整后的需分配無人機(jī)數(shù)量分別為2,4,2,2.

本文將目標(biāo)需分配的無人機(jī)數(shù)量定義為目標(biāo)重要度,并給出如下推論:

推論.給定n架無人機(jī)和m個(gè)目標(biāo),對(duì)于任意目標(biāo)vj在t時(shí)刻的重要度一定有1 ≤≤n?m+1成立.

證明.由于每個(gè)目標(biāo)至少分配一架無人機(jī),因此,等式左邊1 ≤顯然成立.理論上不允許存在無人機(jī)閑置狀態(tài),因此,有考慮一種極端情況: 除了目標(biāo)vj外,其他所有目標(biāo)的重要度均為1,那么目標(biāo)vj的重要度為=n?m+1,因此,等式右邊≤n?m+1 成立.

由于實(shí)際任務(wù)場(chǎng)景的變化, 單個(gè)目標(biāo)的重要度會(huì)隨著時(shí)間的推移而動(dòng)態(tài)變化.本文將目標(biāo)重要度與分配的無人機(jī)數(shù)量相關(guān)聯(lián), 因此, 所有目標(biāo)的重要度之和保持不變, 即為無人機(jī)群總數(shù).根據(jù)目標(biāo)重要度的變化, 無人機(jī)群的協(xié)同目標(biāo)分配策略也應(yīng)進(jìn)行相應(yīng)的調(diào)整.不失一般性, 記t時(shí)刻和t?1 時(shí)刻目標(biāo)重要度分別為和則目標(biāo)重要度的變化量記為表示集合對(duì)應(yīng)位置元素相減,即:

定義1.輸出目標(biāo)集在t時(shí)刻,<0 的目標(biāo)集被定義為輸出目標(biāo)集,即:

定義2.輸入目標(biāo)集: 在t時(shí)刻,> 0 的目標(biāo)集被定義為輸入目標(biāo)集,即:

2 基于任務(wù)接力的目標(biāo)分配策略

2.1 基本調(diào)度策略

多無人機(jī)協(xié)同目標(biāo)分配策略是本文研究的核心,為了均衡無人機(jī)群電量負(fù)載,提升調(diào)度效率,本文從以下3 個(gè)方面對(duì)無人機(jī)群的電池負(fù)載進(jìn)行優(yōu)化,提出了一種基于任務(wù)接力的多無人機(jī)協(xié)同目標(biāo)分配策略.

1)無人機(jī)的機(jī)動(dòng)路線選擇輸出目標(biāo)集到輸入目標(biāo)集之間的最短路徑.

2)為無人機(jī)分配新的目標(biāo)時(shí),在相同條件下,優(yōu)先調(diào)度電池電量更多的無人機(jī).

3) 采用整體分配成本最小的分配策略, 優(yōu)化無人機(jī)群的電量消耗.

需要注意的是, 這種分配策略并不一定對(duì)單個(gè)無人機(jī)是最優(yōu)的.下面給出本文提出的多無人機(jī)協(xié)同目標(biāo)分配策略.首先將t時(shí)刻和t?1 時(shí)刻的目標(biāo)重要度集合和拓展為矩陣的形式,如式(9)所示.

Xt稱為t時(shí)刻無人機(jī)分配矩陣,表示t時(shí)刻第i個(gè)目標(biāo)被分配了一架無人機(jī).因此,成立.無人機(jī)分配的變化量ΔXt=Xt?Xt-1 即為無人機(jī)目標(biāo)分配策略矩陣.(= ?1,= 1)組成一組調(diào)度策略,意味著從目標(biāo)vi釋放一架無人機(jī)分配給目標(biāo)vk.對(duì)于目標(biāo)vi,在t時(shí)刻共需釋放的無人機(jī)總數(shù)為無人機(jī)目標(biāo)分配策略矩陣ΔXt中第i行值為?1 的元素個(gè)數(shù),記為

令= 1 表示t時(shí)刻無人機(jī)uj被分配給目標(biāo)vi,因此,t時(shí)刻分配給目標(biāo)vi的無人機(jī)集合如式(10)所示.

如前所述,在相同條件下,優(yōu)先調(diào)度電池電量更多的無人機(jī).下面根據(jù)t時(shí)刻電池電量對(duì)中的無人機(jī)進(jìn)行重新排序,得到有序集合如式(11)所示.

根據(jù)無人機(jī)調(diào)度策略和關(guān)聯(lián)邊距離集合D, 可以計(jì)算出每架無人機(jī)的分配成本:

其中,wi,k為目標(biāo)vi至目標(biāo)vk的最短距離,T為完成t時(shí)刻所有無人機(jī)調(diào)度所需的最大時(shí)間.當(dāng)某個(gè)目標(biāo)需要釋放多架無人機(jī)至不同的目標(biāo)時(shí), 剩余電量較多的無人機(jī)將會(huì)被優(yōu)先指派給飛行距離較遠(yuǎn)的目標(biāo).

通過一個(gè)包含3 個(gè)目標(biāo)和5 架無人機(jī)的案例,說明了本文提出的基于任務(wù)接力的多無人機(jī)協(xié)同目標(biāo)分配策略.目標(biāo)在t?1 時(shí)刻和t時(shí)刻的重要度如圖2所示.

圖2 目標(biāo)重要度變化Fig.2 Changes in target importance

t?1 時(shí)刻和t時(shí)刻的目標(biāo)重要度集合分別為It?1= {1,2,2} 和It= {2,2,1}, 將它們拓展成無人機(jī)分配矩陣的形式,如式(13)和(14)所示.

則t時(shí)刻無人機(jī)目標(biāo)分配策略矩陣為:

組成兩組調(diào)度策略,其含義分別為從目標(biāo)v2釋放一架無人機(jī)分配至目標(biāo)v1,從目標(biāo)v3釋放一架無人機(jī)分配至目標(biāo)v2.

顯然, 上述案例在本質(zhì)上是需要從目標(biāo)v3釋放一架無人機(jī)至目標(biāo)v1.本文設(shè)計(jì)的基于任務(wù)接力的目標(biāo)分配策略引入了一種類似“接力跑”的形式,相當(dāng)于在目標(biāo)v2處實(shí)現(xiàn)一次“交接”.如果直接從目標(biāo)v3釋放一架無人機(jī)ui至目標(biāo)v1,相當(dāng)于無人機(jī)ui需要獨(dú)立飛行完成從目標(biāo)v3至目標(biāo)v2和從目標(biāo)v2至目標(biāo)v1兩段路徑.而在本文提出的調(diào)度策略中,分別從目標(biāo)v3和目標(biāo)v2釋放無人機(jī)ui和無人機(jī)uj,無人機(jī)ui從目標(biāo)v3至目標(biāo)v2和無人機(jī)uj從目標(biāo)v2至目標(biāo)v1這兩段路徑是可以并行完成的.這種調(diào)度策略具備3 方面優(yōu)勢(shì): 1)縮短調(diào)度任務(wù)的完成時(shí)間;2)使無人機(jī)群電量負(fù)載更加均衡; 3) 調(diào)度策略求解復(fù)雜度低,加速生成調(diào)度策略.

2.2 拓展調(diào)度策略

然而由于目標(biāo)拓?fù)浣Y(jié)構(gòu)的復(fù)雜性, 上述調(diào)度策略在實(shí)際應(yīng)用中可能會(huì)遇到一些不合理的情況.以圖3 所示包含4 個(gè)目標(biāo)和5 架無人機(jī)的情況為例:

圖3 拓展的調(diào)度策略Fig.3 Expanded scheduling strategy

目標(biāo)在t?1 時(shí)刻和t時(shí)刻的目標(biāo)重要度集合分別為It?1={1,2,1,1}和It={1,1,1,2},t?1 時(shí)刻和t時(shí)刻對(duì)應(yīng)的無人機(jī)分配矩陣分別如下.

則t時(shí)刻無人機(jī)目標(biāo)分配策略矩陣為:

按照式(18) 所示, 無人機(jī)調(diào)度策略應(yīng)為從目標(biāo)v2釋放一架無人機(jī)分配至目標(biāo)v3,從目標(biāo)v3釋放一架無人機(jī)分配至目標(biāo)v4.

容易發(fā)現(xiàn),目標(biāo)v3和目標(biāo)v4之間沒有直接相連的路徑.因此,按照上述調(diào)度策略從目標(biāo)v3釋放的無人機(jī)需要先經(jīng)過目標(biāo)v2, 再到達(dá)目標(biāo)v4.與此同時(shí),目標(biāo)v2需要釋放一架無人機(jī)至目標(biāo)v3.顯然,上述兩架無人機(jī)在調(diào)度時(shí)存在路徑的重疊,即從目標(biāo)v3至目標(biāo)v2和從目標(biāo)v2至目標(biāo)v3之間的飛行是重復(fù)的,造成了資源的浪費(fèi).此時(shí),最優(yōu)調(diào)度策略應(yīng)為直接從目標(biāo)v2釋放一架無人機(jī)至目標(biāo)v4.

為避免上述問題,本文在2.1 節(jié)所述基本調(diào)度策略的基礎(chǔ)上, 引入了拓展調(diào)度策略對(duì)基于基本調(diào)度策略生成的多無人機(jī)目標(biāo)分配方案進(jìn)行檢查與修正.將從目標(biāo)vi至目標(biāo)vj的調(diào)度策略記為st(i,j), 調(diào)度策略的總數(shù)記為Z,拓展調(diào)度策略的算法如下:

?

算法1 檢查了基本調(diào)度策略中是否存在資源浪費(fèi)的問題,并對(duì)不合理的策略進(jìn)行修正.首先遍歷所有策略,檢查是否存在一個(gè)策略stz1(i,j)的輸入目標(biāo)vj與另一個(gè)策略stz2(j,k)的輸出目標(biāo)相同,如第3 行所示.如果存在, 則通過式(3) 獲得策略stz1(i,j) 的輸出目標(biāo)vi至輸入目標(biāo)vj的距離wi,j、策略stz2(j,k)的輸出目標(biāo)vj至輸入目標(biāo)vk的距離wj,k以及策略stz1(i,j)的輸出目標(biāo)vi至策略stz2(j,k)的輸入目標(biāo)vk的距離wi,k, 并比較max{wi,j,wj,k}和wi,k的大小.如果max{wi,j,wj,k}>wi,k,則說明目標(biāo)vi至目標(biāo)vk的距離遠(yuǎn)小于目標(biāo)vi至目標(biāo)vj和目標(biāo)vj至目標(biāo)vk的距離之和,即基本調(diào)度策略中存在資源的浪費(fèi).在這種情況下, 將調(diào)度策略修改為從目標(biāo)vi直接釋放一架無人機(jī)至目標(biāo)vk,取消目標(biāo)vj的“接力”,即刪除原有調(diào)度策略stz1(i,j) 和stz2(j,k), 并引入新的調(diào)度策略stz_new(i,k),如第4 ～7 行所示.

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

為了驗(yàn)證本文提出的基于任務(wù)接力的多無人機(jī)協(xié)同目標(biāo)分配策略的有效性, 本節(jié)設(shè)計(jì)了3 種對(duì)比策略, 并通過一系列度量指標(biāo)對(duì)4 種分配策略進(jìn)行比較.

1) 隨機(jī)策略: 隨機(jī)生成從輸出目標(biāo)集至輸入目標(biāo)集的多無人機(jī)目標(biāo)分配策略.

2)貪婪策略:根據(jù)貪婪算法[17]生成從輸出目標(biāo)集至輸入目標(biāo)集的多無人機(jī)目標(biāo)分配策略.

3)匈牙利策略:根據(jù)匈牙利法[18]生成從輸出目標(biāo)集至輸入目標(biāo)集的多無人機(jī)目標(biāo)分配策略.

本文通過以下度量指標(biāo)對(duì)4 種調(diào)度策略的性能進(jìn)行比較.

1)調(diào)度次數(shù): 在仿真過程中,目標(biāo)重要度每發(fā)生一次變化,無人機(jī)群進(jìn)行一次目標(biāo)分配調(diào)度;調(diào)度次數(shù)指仿真過程中無人機(jī)群調(diào)度策略執(zhí)行的最大次數(shù),度量分配策略的有效性.

2)剩余電量均值:每輪調(diào)度時(shí),所有無人機(jī)剩余電池電量的平均值, 度量分配策略在電量消耗上的均衡性.

3)累積飛行距離均值:當(dāng)前調(diào)度時(shí),無人機(jī)群平均飛行距離之和, 度量分配策略在飛行距離上的整體情況.

4) 最大的飛行時(shí)長(zhǎng): 每輪調(diào)度時(shí), 所有無人機(jī)飛行時(shí)長(zhǎng)的最大值, 度量分配策略響應(yīng)任務(wù)的時(shí)效性.

5)最大電量消耗:每輪調(diào)度時(shí),無人機(jī)群中懸停電量與飛行電量之和最大的無人機(jī)消耗的總電量,度量無人機(jī)群電量消耗的整體水平.

6)能耗效率:每輪調(diào)度時(shí),所有無人機(jī)平均飛行能耗與懸停能耗的比值,度量電量消耗的有效性.

3.1 實(shí)驗(yàn)設(shè)置

構(gòu)建了一個(gè)目標(biāo)數(shù)為6, 無人機(jī)數(shù)量為20 的多無人機(jī)協(xié)同目標(biāo)分配實(shí)驗(yàn)場(chǎng)景.每輪模擬隨機(jī)生成目標(biāo)重要度,每個(gè)目標(biāo)的重要度大于1 且小于5, 所有目標(biāo)的總重要度為20.考慮到無人機(jī)的異構(gòu)性,將無人機(jī)分為3 類,3 類無人機(jī)的數(shù)量分別被設(shè)置為6架、9 架和5 架.無人機(jī)的配置如表1 所示.

表1 無人機(jī)配置參數(shù)Table 1 Configuratio of UAVs

為了反映目標(biāo)在地理空間中的離散性, 任意兩個(gè)目標(biāo)拓?fù)溥B接的概率設(shè)置為0.5.對(duì)于兩個(gè)拓?fù)渖舷噙B的目標(biāo),它們之間的距離設(shè)置為0.1 km 和0.5 km之間的隨機(jī)值,目標(biāo)的地理分布如圖4 所示.

圖4 目標(biāo)的地理分布Fig.4 Geographical distribution of targets

如1.2.2 節(jié)式(3) 所述, 目標(biāo)之間的最短路徑記為二維矩陣Wp,本例中Wp如下:

圖5 展示了4 種目標(biāo)分配策略在第一輪調(diào)度時(shí)的策略.在圖5 的每個(gè)子圖中,橫軸代表了目標(biāo)編號(hào),共有6 個(gè)目標(biāo),縱軸表示無人機(jī)編號(hào),共有20 架無人機(jī).圖中的箭頭表示無人機(jī)調(diào)度策略,箭尾對(duì)應(yīng)的橫軸編號(hào)表示該無人機(jī)在第一輪調(diào)度開始前分配的目標(biāo), 箭頭對(duì)應(yīng)的橫軸編號(hào)表示該無人機(jī)在第一輪調(diào)度后分配的目標(biāo).圓點(diǎn)表示無人機(jī)在當(dāng)前時(shí)刻被分配的目標(biāo)與上一時(shí)刻相同.以圖5(a)為例,第一輪的調(diào)度策略為:無人機(jī)u20從目標(biāo)v6前往目標(biāo)v1,無人機(jī)u18從目標(biāo)v6前往目標(biāo)v5, 無人機(jī)u17從目標(biāo)v6前往目標(biāo)v4,無人機(jī)u9從目標(biāo)v3前往目標(biāo)v5,其他無人機(jī)原地待命.顯然,4 種目標(biāo)分配策略在第一輪調(diào)度時(shí)產(chǎn)生了較大的不同, 本文提出的基于任務(wù)接力的無人機(jī)目標(biāo)分配策略需調(diào)動(dòng)的無人機(jī)為6 架次,明顯高于其他3 種策略(均為4 架次).

圖5 第一輪調(diào)度策略Fig.5 Scheduling strategies in the firs round

3.2 性能分析

3.2.1 調(diào)度次數(shù)

圖6 比較了4 種策略在調(diào)度次數(shù)上的性能,橫軸表示了實(shí)驗(yàn)編號(hào),縱軸表示最大調(diào)度次數(shù).每次實(shí)驗(yàn)的目標(biāo)重要度隨機(jī)生成, 因此, 調(diào)度次數(shù)也不同.可以看出,各組策略的變化趨勢(shì)相似,但接力策略的最大調(diào)度次數(shù)明顯高于其他策略, 證明本文提出的調(diào)度策略能有效提升無人機(jī)群執(zhí)行任務(wù)時(shí)的調(diào)度次數(shù),體現(xiàn)了該策略的有效性.

圖6 調(diào)度次數(shù)對(duì)比Fig.6 Comparison of scheduling times

不失一般性,以第一組實(shí)驗(yàn)為例,對(duì)比4 種策略在不同度量指標(biāo)下的性能.

3.2.2 剩余電量均值

圖7 比較了4 種策略在平均剩余電量上的性能.橫軸表示每種策略的調(diào)度次數(shù), 柱狀圖對(duì)應(yīng)主要縱坐標(biāo),表示剩余電量的均值,折線圖對(duì)應(yīng)次要縱坐標(biāo),表示剩余電量的方差.在相同的調(diào)度次數(shù)下,剩余電量均值越大,表示無人機(jī)群的續(xù)航能力越好;剩余電量的方差越小,說明無人機(jī)群的電池消耗越均衡.隨著調(diào)度次數(shù)的增加, 每種策略下剩余電量均值呈下降趨勢(shì).在每輪調(diào)度中,剩余電量均值由高到低的排序?yàn)榻恿Σ呗?、匈牙利策略、貪婪策略和隨機(jī)策略.隨著調(diào)度次數(shù)的增加, 接力策略的剩余電量均值明顯高于其他3 種策略,而隨機(jī)策略的剩余電量均值明顯低于其他3 種策略.剩余電量方差呈先下降后上升的趨勢(shì).這是由于所有的策略都優(yōu)先調(diào)度剩余電量較多的無人機(jī),因此,無人機(jī)群內(nèi)各架無人機(jī)的剩余電量趨于平衡.當(dāng)電量趨于一致后,由于重要度變化的不確定性, 部分無人機(jī)的電量消耗多于其他無人機(jī),方差隨之增大.在第13 次調(diào)度之后,本文提出的接力策略的剩余電量方差明顯低于其他3 種策略,說明接力策略有效地保證了無人機(jī)群調(diào)度時(shí)的負(fù)載均衡性.

圖7 剩余電量均值對(duì)比Fig.7 Comparison of average remaining energy

3.2.3 累積飛行距離均值

圖8 比較了4 種策略在累積飛行距離上的性能.柱狀圖對(duì)應(yīng)主要縱坐標(biāo),表示累積飛行距離的均值,折線圖對(duì)應(yīng)次要縱坐標(biāo),表示累積飛行距離的方差.隨著調(diào)度次數(shù)的增加, 每種策略的累積飛行距離均值和方差均呈上升趨勢(shì).顯然,接力策略的累積飛行距離均值要高于其他調(diào)度策略.這是由于接力策略在單次調(diào)度任務(wù)中傾向于調(diào)動(dòng)更多的無人機(jī), 可能會(huì)導(dǎo)致兩個(gè)目標(biāo)之間無人機(jī)的調(diào)度需要借助經(jīng)過第3 個(gè)目標(biāo), 導(dǎo)致飛行距離增加.例如, 需要從目標(biāo)v1釋放一架無人機(jī)至目標(biāo)v3, 接力策略可能會(huì)指揮目標(biāo)v1釋放一架無人機(jī)至目標(biāo)v2,同時(shí)目標(biāo)v2釋放一架無人機(jī)至目標(biāo)v3,而目標(biāo)v1與目標(biāo)v3之間的最短距離可能小于目標(biāo)v1至目標(biāo)v2與目標(biāo)v2至目標(biāo)v3之間的距離之和.因此,接力策略在累積飛行距離上要高于其他調(diào)度策略.同時(shí),由于更多無人機(jī)的調(diào)動(dòng)使得接力策略的累積飛行距離方差在多數(shù)情況下明顯小于其他策略, 這從側(cè)面體現(xiàn)了接力策略具有更好的負(fù)載均衡性.

圖8 累積飛行距離對(duì)比Fig.8 Comparison of cumulative fligh distance

3.2.4 最大飛行時(shí)長(zhǎng)

圖9 比較了4 種策略在最大飛行時(shí)長(zhǎng)上的性能.一般來說, 接力策略的最大飛行時(shí)長(zhǎng)要低于其他調(diào)度策略.雖然接力策略在每輪調(diào)度中的累積飛行距離均值要高于其他策略, 但是由于該策略每輪調(diào)動(dòng)的無人機(jī)架次更多, 縮短了每架無人機(jī)的飛行距離,因此,能夠縮短每輪調(diào)度所需的飛行時(shí)長(zhǎng),使無人機(jī)更快地完成在不同目標(biāo)之間的轉(zhuǎn)移任務(wù).

圖9 最大飛行時(shí)長(zhǎng)對(duì)比Fig.9 Comparison of maximum fligh time

3.2.5 最大電量消耗

圖10 比較了4 種策略在最大電量消耗上的性能.由于目標(biāo)重要度的隨機(jī)變化,每輪調(diào)度的最大電量消耗呈隨機(jī)波動(dòng).在大多輪調(diào)度中,接力策略的最大電量消耗低于其他3 種調(diào)度策略, 這是由于接力策略傾向于在每輪調(diào)度時(shí)調(diào)動(dòng)更多的無人機(jī), 降低了每架無人機(jī)的飛行距離,消耗的電量隨之下降.因此,無人機(jī)群在電量消耗上更為均衡,與剩余電量的結(jié)論相對(duì)應(yīng).

圖10 最大電量消耗對(duì)比Fig.10 Comparison of maximum energy consumption

3.2.6 能耗效率

圖11 比較了4 種策略在能耗效率上的性能.能耗效率越高, 表明無人機(jī)群消耗的電量更多地用于飛行而不是懸停, 進(jìn)而說明無人機(jī)群的電量利用率越高.每輪調(diào)度的能耗效率呈隨機(jī)波動(dòng),接力策略的能耗效率在多數(shù)情況下要高于其他策略, 而其他策略的能耗效率沒有明顯的優(yōu)劣.這是由于接力策略每次調(diào)度的用時(shí)小于其他調(diào)度策略, 降低了無人機(jī)的懸停時(shí)間,進(jìn)而減少了懸停能耗,提高了能耗效率.

圖11 能耗效率對(duì)比Fig.11 Comparison of energy consumption efficiency

4 結(jié)論

本文研究了目標(biāo)重要度動(dòng)態(tài)變化的情況下, 無人機(jī)群協(xié)同目標(biāo)分配問題.首先,采用無向加權(quán)圖對(duì)目標(biāo)進(jìn)行抽象與建模,并給出目標(biāo)編號(hào)方式.根據(jù)目標(biāo)在不同時(shí)刻重要度的變化, 提出基于任務(wù)接力的多無人機(jī)協(xié)同目標(biāo)分配策略.該策略在調(diào)度任務(wù)中傾向于調(diào)動(dòng)更多的無人機(jī), 以實(shí)現(xiàn)無人機(jī)群的負(fù)載均衡, 并縮短調(diào)度任務(wù)完成的時(shí)間.在此基礎(chǔ)上, 考慮特殊情況下該策略的不合理之處, 提出拓展調(diào)度策略, 保證了本文提出的基于任務(wù)接力的調(diào)度策略在特殊場(chǎng)景下的合理性與有效性.通過仿真實(shí)驗(yàn),對(duì)比了基于任務(wù)接力的調(diào)度策略與基于隨機(jī)規(guī)則、貪婪算法與匈牙利法構(gòu)建的其他3 種調(diào)度策略在調(diào)度次數(shù)、剩余電量均值等指標(biāo)上的性能.結(jié)果表明, 本文提出的基于任務(wù)接力的調(diào)度策略能夠保證無人機(jī)群電量負(fù)載均衡,有效提升無人機(jī)群的調(diào)度效率.