考慮中繼充電的小型無人機(jī)偵察路徑規(guī)劃

毛慧婷 石建邁 周玉珍 劉 忠

1.國防科技大學(xué)系統(tǒng)工程學(xué)院信息系統(tǒng)工程重點(diǎn)實(shí)驗室 湖南長沙 410073

隨著高技術(shù)作戰(zhàn)體系日趨完善,現(xiàn)代戰(zhàn)爭對戰(zhàn)場信息的及時獲取和空間的爭奪日趨激烈,對作戰(zhàn)對象的目標(biāo)偵察以及位置獲取等提出了更高的需求.當(dāng)前軍事偵察技術(shù)主要包括有人駕駛飛機(jī)偵察、無人機(jī)偵察以及衛(wèi)星遙感偵察,在這些技術(shù)中,無人機(jī)偵察技術(shù)由于其響應(yīng)及時、部署靈活且無人員傷亡風(fēng)險等特點(diǎn),得到了廣泛的應(yīng)用.同時傳感器技術(shù)、信息傳輸網(wǎng)絡(luò)以及飛行器平臺的飛速發(fā)展,為無人機(jī)在戰(zhàn)場上的偵察提供了強(qiáng)有力的技術(shù)支撐[1].

在實(shí)際作戰(zhàn)過程中和軍事運(yùn)籌研究中,無人機(jī)路徑規(guī)劃都屬于十分重要的課題[2].無人機(jī)偵察路徑規(guī)劃主要是指在某一特定戰(zhàn)場中,盡可能地減少無人機(jī)的使用數(shù)量,在較短時間內(nèi)完成所有既定目標(biāo)的偵察任務(wù),提高偵察效率.Shetty 等考慮了基于目標(biāo)優(yōu)先級的多無人機(jī)任務(wù)分配以及路徑規(guī)劃問題,采用禁忌搜索算法對問題進(jìn)行求解[3].Mufalli 等在多無人機(jī)路徑規(guī)劃過程中考慮了無人機(jī)（unmanned aerial vehicle,UAV）的載荷約束,即無人機(jī)續(xù)航能力受載荷重量影響,建立了其規(guī)劃模型,并通過列生成與啟發(fā)式算法求解了該問題[4].Evers 等研究了考慮目標(biāo)時間窗口約束的多無人機(jī)偵察路徑規(guī)劃問題[5].Mahmud 等研究了如何避免無人機(jī)被敵方預(yù)測的偵察路徑規(guī)劃問題[6],提出了一種協(xié)作路徑規(guī)劃方法.

隨著無人機(jī)小型化、智能化的發(fā)展趨勢,具有體積小、隱蔽性強(qiáng)、運(yùn)用靈活、成本低等優(yōu)勢的小型無人機(jī)在戰(zhàn)場近距離偵察中得到越來越廣泛的應(yīng)用.但是小型無人機(jī)續(xù)航里程短,從基地出發(fā)后其可服務(wù)的范圍半徑就受到相應(yīng)的限制,這大大降低了偵察效率,使其難以完成所有偵察任務(wù).尤其對于區(qū)域內(nèi)分布較為分散的目標(biāo)點(diǎn)來說,無人機(jī)的偵察任務(wù)更為艱巨.為解決這方面的問題,國防科技大學(xué)羅志浩、劉瑤、劉忠等提出了應(yīng)用地面車輛搭載小型無人機(jī)協(xié)同進(jìn)行戰(zhàn)場情報偵察的作戰(zhàn)運(yùn)用模式[7-8].地面車輛作為移動平臺,可以攜帶小型無人機(jī)在戰(zhàn)場大范圍內(nèi)機(jī)動,在運(yùn)動過程中放飛和回收小型無人機(jī),并為無人機(jī)提供充電、更換電池等保障.無人機(jī)不斷在地面車輛上起飛降落,通過多次續(xù)航,完成戰(zhàn)場目標(biāo)的偵察任務(wù).Sundar 研究了單無人機(jī)的路徑規(guī)劃,且允許無人機(jī)返回基地進(jìn)行充電[9].Bingxi 提出了同時考慮任務(wù)優(yōu)先分配和充電站選址的大規(guī)模搜救任務(wù)規(guī)劃,且規(guī)定在充電站的充電時間是一定的[10].Ribeiro 研究了無人機(jī)在采礦業(yè)中用于帶式輸送機(jī)檢測系統(tǒng)的場景[11],但同時規(guī)定無人機(jī)在充電站只能充滿電.在民用領(lǐng)域,各大商業(yè)物流公司將小型無人機(jī)用于“最后一公里”配送,以提高物流配送效率.如：Coelho 等通過設(shè)計雙層路徑模型,在動態(tài)需求的環(huán)境下,允許無人機(jī)在既定充電點(diǎn)進(jìn)行充電以完成配送[12].Chiang 等將車輛與無人機(jī)協(xié)同進(jìn)行包裹配送,并利用遺傳算法求解證明該配送模式可大大降低空氣污染和能源消耗[13].劉瑤、劉忠等應(yīng)用模擬退火算法求解車輛與無人機(jī)協(xié)同進(jìn)行快遞配送的路徑優(yōu)化問題[14].在這些研究中,通過地面車輛的輔助,有效拓展了無人機(jī)的偵察范圍,但是受續(xù)航能力限制,無人機(jī)仍然只能在車輛行駛路線的一定范圍內(nèi)進(jìn)行偵察活動,并且車輛與無人機(jī)路徑規(guī)劃時需要考慮兩者在時空方面的密切協(xié)同.

為了克服小型無人機(jī)續(xù)航能力的限制,提出一種新的小型無人機(jī)戰(zhàn)場偵察應(yīng)用模式.通過為我方作戰(zhàn)裝備,如裝甲車輛、運(yùn)輸車輛等,加裝小型無人機(jī)快速無線充電設(shè)備,使其成為小型無人機(jī)的中繼充電平臺.在作戰(zhàn)過程中,這些裝備因各自任務(wù)分散部署到戰(zhàn)場上時,就形成了一個可為小型無人機(jī)進(jìn)行中繼充電的充電站網(wǎng)絡(luò).小型無人機(jī)在執(zhí)行偵察任務(wù)過程中,當(dāng)電量不足時,可以到附近具備充電能力的我方作戰(zhàn)裝備上進(jìn)行快速充電,然后繼續(xù)執(zhí)行任務(wù).這種情況下,在優(yōu)化無人機(jī)偵察路徑的過程中,還需要優(yōu)化選擇中繼充電點(diǎn)的決策.這種考慮中繼充電的無人機(jī)路徑規(guī)劃問題與商業(yè)領(lǐng)域電動汽車的路徑規(guī)劃比較相似[15].兩者的共同之處在于,在執(zhí)行任務(wù)過程中都需要訪問充電點(diǎn)進(jìn)行充電,以增加續(xù)航能力,完成后續(xù)任務(wù).不同之處在于,充電汽車在等待和服務(wù)客戶時是不消耗電量的,而小型無人機(jī)在目標(biāo)附近等待和對目標(biāo)進(jìn)行偵察時,都會消耗電量,并且偵察目標(biāo)時由于傳感器開始工作,其耗電速度更快.因此,需要針對戰(zhàn)場上小型無人機(jī)這種新型運(yùn)用模式的路徑規(guī)劃問題,研究新的模型和求解算法,提高小型無人機(jī)戰(zhàn)場偵察的指揮控制效率.

1 問題描述與建模

在考慮中繼充電的小型無人機(jī)偵察規(guī)劃問題中,多架小型無人機(jī)從臨時基地出發(fā)對戰(zhàn)場上的多個目標(biāo)進(jìn)行偵察,偵察過程中電量不足時,可以尋求我方在戰(zhàn)場上的搭載快速無線充電設(shè)備的作戰(zhàn)平臺進(jìn)行快速充電,然后繼續(xù)執(zhí)行偵察任務(wù),每架無人機(jī)通過多次中繼充電接力,協(xié)同完成戰(zhàn)場區(qū)域內(nèi)所有預(yù)定目標(biāo)的偵察任務(wù).圖1給出了一個無人機(jī)中繼充電模式下的偵察飛行路徑示意圖.

圖1 無人機(jī)中繼充電飛行路徑示意圖Fig 1 Schematic diagram of UAV routing with recharging

考慮中繼充電的無人機(jī)路徑規(guī)劃問題中的關(guān)鍵要素與約束如下.

1.1 小型無人機(jī)

執(zhí)行偵察任務(wù)的小型無人機(jī)為鋰電池驅(qū)動,電池容量是確定的,無人機(jī)飛行時消耗電量與飛行速度和距離相關(guān).無人機(jī)搭載的傳感器在偵察目標(biāo)時消耗電量與偵察精度和時間相關(guān),不偵察目標(biāo)時,偵察傳感器關(guān)閉,不消耗電量.當(dāng)無人機(jī)懸停在偵察點(diǎn)上方等待合適的目標(biāo)偵察窗口時,仍需要消耗電量,但電量消耗速度小于飛行或偵察時的消耗速度.無人機(jī)從基地出發(fā),完成偵察任務(wù)后必須回到基地.

1.2 中繼充電平臺

我方一些作戰(zhàn)平臺,如裝甲車、運(yùn)輸車輛、導(dǎo)彈發(fā)射車等裝備,事前安裝了快速無線充電設(shè)備.這些平臺因各自的任務(wù)分散部署在戰(zhàn)場上,能夠為無人機(jī)進(jìn)行快速充電,為無人機(jī)的充能量與充電時間相關(guān),且充電函數(shù)已知.這些作戰(zhàn)平臺在戰(zhàn)場上的位置和無人機(jī)指揮中心是信息共享的.

1.3 偵察目標(biāo)

需要偵察的目標(biāo)分布在戰(zhàn)場不同位置,并且每個偵察目標(biāo)只能在給定的時間窗口進(jìn)行偵察,并且每個目標(biāo)的偵察時間與精度是任務(wù)給定的,目標(biāo)的位置信息也已知.

在給定上述信息的情況下,考察中繼充電的無人機(jī)偵察路徑規(guī)劃問題,通過優(yōu)化每架無人機(jī)訪問偵察目標(biāo)和中繼充電平臺的飛行路徑來最小化偵察任務(wù)完成的總時間和無人機(jī)使用數(shù)量.應(yīng)用混合整數(shù)規(guī)劃建模方法,建立考察中繼充電的無人機(jī)偵察路徑規(guī)劃的數(shù)學(xué)模型.

首先,模型中采用的參數(shù)變量符號如下：

點(diǎn)集V1 偵察目標(biāo)集合F 中繼充電點(diǎn)及其副本集合{0} 無人機(jī)基地{n+1} 同為無人機(jī)基地,用來表述無人機(jī)返回的節(jié)點(diǎn)序號V0 表示偵察目標(biāo)、中繼充電點(diǎn)和出發(fā)點(diǎn)的集合,即Vn+1 表示偵察目標(biāo)、中繼充電點(diǎn)和返回點(diǎn)的集合,即V 所有點(diǎn)的集合參數(shù)dij 無人機(jī)從偵察目標(biāo)i 飛到j(luò) 的耗電量tij 偵察目標(biāo)i 到j(luò) 的飛行時間g 無人機(jī)電池的充電率si 目標(biāo)i 的偵察時間ei 目標(biāo)i 偵察時間窗口的最早開始時間li 目標(biāo)i 偵察時間窗口的最晚開始時間Q 無人機(jī)的電池容量α 一架無人機(jī)的權(quán)重系數(shù)β 總體偵察時間的權(quán)重系統(tǒng),α+β=1 si 無人機(jī)完成目標(biāo)i 偵察任務(wù)的耗電量cw 無人機(jī)單位等待時間的耗電率cuav 無人機(jī)單位使用成本決策變量ui 目標(biāo)i 的開始偵察時間,i∈V1 yi 無人機(jī)到達(dá)目標(biāo)點(diǎn)i 時的剩余電量,i∈V1 qi 無人機(jī)在充電站i 的充電量,i∈F Yi 無人機(jī)離開充電站i 時的電量,i∈F δi 無人機(jī)在目標(biāo)i 的等待時間,i∈V1 xij 當(dāng)無人機(jī)從點(diǎn)i 飛往點(diǎn)j 時,為1,否則為0 zj 當(dāng)選擇中繼點(diǎn)i（i∈F）進(jìn)行充電時為1,否則為0

數(shù)學(xué)規(guī)劃模型如下：

在模型中,目標(biāo)函數(shù)（1）通過加權(quán)最小化無人機(jī)使用數(shù)量和總體偵察時間.約束（2）確保每個目標(biāo)被偵察一次.約束（3）處理偵察點(diǎn)與中繼充電點(diǎn)之間的連接性.約束（4）確保每個點(diǎn)的飛入次數(shù)和飛出次數(shù)是相等的.約束（5）限定偵察目標(biāo)訪問時間的可行性.約束（6）限定訪問中繼充電點(diǎn)的時間可行性.約束（7）限定訪問偵察目標(biāo)的時間窗口.約束（8）和（9）確保無人機(jī)離開偵察目標(biāo)或中繼充電點(diǎn)時電量是非負(fù)的.約束（10）確定無人機(jī)離開中繼充電點(diǎn)時的電池狀態(tài).約束（11）確保充電量不超過無人機(jī)電池容量.約束（12）～（14）為變量限定約束.

對比充電汽車路徑規(guī)劃模型,可以看出,中繼充電無人機(jī)路徑規(guī)劃不需要考慮貨物裝備問題,其攜帶的傳感器重量是恒定的,但是無人機(jī)在等待過程中以及在偵察目標(biāo)點(diǎn)進(jìn)行偵察時都在消耗電量,需要建立相應(yīng)的約束進(jìn)行建模,而充電汽車在等待和目標(biāo)點(diǎn)服務(wù)時不消耗電能,相應(yīng)模型中也沒有體現(xiàn).同時大部分充電汽車采用電池充滿策略,而無人機(jī)為了盡快完成偵察任務(wù),在中繼點(diǎn)進(jìn)行部分充電,只充后續(xù)路徑需要的電量,以節(jié)省時間.

從模型特點(diǎn)來看,當(dāng)前充電汽車路徑規(guī)劃的相關(guān)算法難以直接解決該問題,需要研究新的算法,設(shè)計新的智能搜索策略和算子,為中繼充電無人機(jī)偵察路徑規(guī)劃提供高效求解算法.

2 算法設(shè)計

考慮到小型無人機(jī)在偵察過程中需要中繼充電的問題復(fù)雜性,本文設(shè)計了一種改進(jìn)的蟻群算法.蟻群算法是一種新的仿生類隨機(jī)型搜索算法,仿照自然界中螞蟻覓食的自然現(xiàn)象,由意大利學(xué)者Dorigo 等提出,具有群體合作、正反饋選擇、并行計算等特點(diǎn).近年來蟻群算法逐漸被用于求解各種車輛路徑規(guī)劃問題[16-20],是一種有效的求解手段.

為適應(yīng)本文中的小型無人機(jī)偵察路徑問題特點(diǎn),本文對蟻群算法進(jìn)行了兩方面的改進(jìn).首先考慮到充電站的選擇和充電水平的確定,設(shè)計了一個最優(yōu)充電站插入啟發(fā)式算法；其次,鑒于問題的復(fù)雜性,引入局部搜索算法,擴(kuò)大蟻群算法迭代過程中的搜索空間,增加最優(yōu)解的搜索概率.改進(jìn)蟻群算法的主要步驟如算法1.

算法1 改進(jìn)的蟻群算法1 參數(shù)初始化2 構(gòu)造初始解3 初始化信息素濃度4 While 迭代次數(shù)小于Max_iteration 5 對所有的k 個螞蟻,并行構(gòu)建其NR 解,直至完成所有螞蟻的路徑構(gòu)建6 插入充電站啟發(fā)式算法7 局部搜索8 信息素更新9 End While 10 輸出最優(yōu)可行解

2.1 蟻群初始解構(gòu)造

其中,dij表示邊＜i,j＞的長度,lj表示下一個目標(biāo)點(diǎn)j的最晚服務(wù)時間,該值越小表示其時間窗越緊迫.

2.2 信息素更新

在信息素的更新機(jī)制中引入了信息素?fù)]發(fā)機(jī)制.本文采用精英螞蟻策略,即不僅采用搜索產(chǎn)生的最優(yōu)解更新信息素濃度,其余精英螞蟻產(chǎn)生的較優(yōu)路徑也會被用于信息素濃度的更新.其更新方式如下：

2.3 充電站插入啟發(fā)式算法

由于小型無人機(jī)電池容量有限,其續(xù)航里程受到電量水平的限制.蟻群算法求解出的不考慮充電站（no-recharged,NR）的解（φ0）,其路徑一般不滿足里程約束.因此,需要在這些路徑中插入充電站對無人機(jī)適當(dāng)充電才能保證偵察任務(wù)的順利完成.本文設(shè)計了一個充電站最優(yōu)插入啟發(fā)式算法解決該問題,算法主要步驟如算法2.

充電站插入算法的基本思路如下：首先確定該路徑的行駛里程是否超出無人機(jī)最大續(xù)航里程,然后找出無人機(jī)可到達(dá)的最遠(yuǎn)目標(biāo)點(diǎn),即無人機(jī)可以到達(dá)該目標(biāo)點(diǎn),但無法訪問下一個目標(biāo)點(diǎn).尋找距離該目標(biāo)點(diǎn)后最近的充電站,插入至該目標(biāo)點(diǎn)后.檢查剩余路徑是否可行,如不可行,則按該方法繼續(xù)插入充電站,直至路徑可行.

算法2 充電站插入啟發(fā)式算法Input:初始NR 解Output:最優(yōu)可行解1 For 不可行解in 2 找到UAV 能到達(dá)的最遠(yuǎn)客戶點(diǎn)3 For 前一個充電站/倉庫和最遠(yuǎn)客戶點(diǎn)之間的所有節(jié)點(diǎn)4 在當(dāng)前點(diǎn)之后插入距離最近的充電站5 確定充電量6 檢查時間窗是否可行7 If 路徑時間窗不可行8 將時間窗不可行的客戶點(diǎn)移除該路徑9 將移除的點(diǎn)加入集合10 Else 11 從中移除可行路徑并將其加入12 End if 13 End for 14 End for 15 While中的NR 解采用鄰近點(diǎn)搜索17 重復(fù)以上1-14 行18 End While 16 對

確定了充電站的插入位置之后,即可通過后續(xù)飛行路徑所需要的實(shí)際電量對無人機(jī)進(jìn)行充電.由于無人機(jī)除了飛行時間和偵察時間要耗電之外,若無人機(jī)在該偵察點(diǎn)最早偵察開始時間之前到達(dá),無人機(jī)需要懸停在偵察點(diǎn)上方進(jìn)行等待,該等待過程同樣需要耗電.因此,無人機(jī)在后續(xù)偵察點(diǎn)的等待時間內(nèi)的耗電量會影響前一個充電站的充電水平,進(jìn)而影響無人機(jī)所需要的充電時間.同樣地,無人機(jī)在充電站的充電時間很大程度上會影響后續(xù)偵察點(diǎn)等待時間的長短.因此,這兩者因素的交互影響使得如何確定無人機(jī)在充電點(diǎn)的充電水平變得更為復(fù)雜.為了解決該問題,本文允許無人機(jī)在充電站可以多充電,即先不考慮充電時間計算出后續(xù)飛行路徑所需要的耗電量確定無人機(jī)的充電水平.一旦確定了相應(yīng)的充電時間之后,其后續(xù)路徑的等待時間有可能會相應(yīng)縮短,進(jìn)而使得無人機(jī)在到達(dá)下一個充電點(diǎn)或者基地時往往會有剩余電量,這就是多充電原則.

當(dāng)充電水平確定之后,檢查該回路上的目標(biāo)偵察點(diǎn)時間窗約束是否仍然滿足.若有目標(biāo)點(diǎn)的時間窗不滿足,則將該目標(biāo)點(diǎn)從該路徑中移除并將其添加到集合.在整個充電站插入的過程中,可行解的接受第一準(zhǔn)則首先是盡可能保留較多的目標(biāo)點(diǎn),其次則是接受較低成本的可行解.

2.4 局部搜索算法

局部搜索算法可以在一定程度上防止蟻群算法陷入局部最優(yōu)解,擴(kuò)展蟻群算法單次迭代過程中的搜索范圍,提高搜索的可行解質(zhì)量.在本文中,局部搜索算法主要由移除算子與插入算子兩部分構(gòu)成,其通過不斷破壞與重構(gòu)當(dāng)前解,增加解的多樣性.考慮到在局部搜索過程中每進(jìn)行一次解的調(diào)整,充電站的最優(yōu)插入也會不同,因此,本文的局部搜索是在移除充電站的路徑上進(jìn)行的.在完成迭代后,再通過插入充電站生成可行解.

2.4.1 移除算子

本文采用的移除算子可以分為兩類：路徑移除與目標(biāo)點(diǎn)移除.路徑移除是指將路徑上的所有目標(biāo)點(diǎn)移除,目標(biāo)點(diǎn)移除是選擇一定數(shù)量的目標(biāo)點(diǎn)移除.移除的數(shù)量根據(jù)總目標(biāo)點(diǎn)數(shù)決定,其首先根據(jù)總目標(biāo)數(shù)確定一個特定區(qū)間,然后在區(qū)間內(nèi)隨機(jī)選擇.

1）隨機(jī)路徑刪除：隨機(jī)路徑刪除算子通過隨機(jī)選擇一條路徑,將該路徑中的所有目標(biāo)點(diǎn)加入到移除列表中實(shí)現(xiàn)移除.隨機(jī)選擇刪除算子可以擴(kuò)大搜索空間.

2）最短路徑刪除：最短路徑刪除算子是選擇所有路徑中最短的,將該路徑中的所有目標(biāo)點(diǎn)加入到移除列表中.其目的是盡量提高車輛利用率.

3）結(jié)束最早路徑刪除：結(jié)束最早路徑刪除算子通過選擇路徑中返回時間最早的路徑,將該路徑上所有目標(biāo)點(diǎn)加入到移除列表中實(shí)現(xiàn)移除.其設(shè)計主要基于對現(xiàn)實(shí)因素的考量,最大化車輛的工作時長.

5）最差目標(biāo)點(diǎn)刪除：最差目標(biāo)點(diǎn)刪除算子對每個目標(biāo)點(diǎn)計算其距離前后相連目標(biāo)點(diǎn)的距離之和,并對所有點(diǎn)進(jìn)行排序,然后移除最大的個目標(biāo)點(diǎn).該算子如圖2所示.

圖2 最差目標(biāo)點(diǎn)刪除算子Fig 2 Worst-distance target removal

6）基于時間窗的目標(biāo)點(diǎn)刪除：基于時間窗的目標(biāo)點(diǎn)刪除算子,首先隨機(jī)選擇一個目標(biāo)點(diǎn),然后移除其余目標(biāo)點(diǎn)中最晚服務(wù)開始時間與該目標(biāo)點(diǎn)最晚服務(wù)開始時間最接近的目標(biāo)點(diǎn),重復(fù)該過程直至刪除個目標(biāo)點(diǎn).

7）基于距離的目標(biāo)點(diǎn)刪除：基于距離的目標(biāo)點(diǎn)刪除算子先隨機(jī)選擇一個目標(biāo)點(diǎn),然后移除距離該目標(biāo)點(diǎn)最近的目標(biāo)點(diǎn),重復(fù)該過程直至刪除個目標(biāo)點(diǎn).該算子如圖3所示.

圖3 基于距離的目標(biāo)點(diǎn)刪除算子Fig 3 Proximity-based target removal

2.4.2 插入算子

插入算子主要是將移除的目標(biāo)節(jié)點(diǎn)重新插入路徑中,在插入算子的設(shè)計中只考慮當(dāng)前路徑時間窗以及車輛容量的可行性,而不考慮車輛里程的約束.

1）貪婪插入：在依次插入移除的目標(biāo)點(diǎn)時,選擇所有可插入位置中使得插入成本增加最少的位置.

2）后悔值-2 插入：計算每個移除的節(jié)點(diǎn)的前兩個最佳插入位置,計算這兩種插入方式的成本差.選擇差值較大的目標(biāo)點(diǎn),將其插入最佳位置.

3）基于模擬退火準(zhǔn)則插入：找出所有被移除目標(biāo)點(diǎn)的最優(yōu)和次優(yōu)插入位置,并以一定的概率接受次優(yōu)解.

4）優(yōu)先插入準(zhǔn)則：首先計算出每一個被移除的目標(biāo)點(diǎn)可重新插回當(dāng)前解的位置個數(shù),按該數(shù)值進(jìn)行升序排序,依次選擇目標(biāo)點(diǎn)插入其最優(yōu)插入位置.該算子的目的是盡可能將所有客戶點(diǎn)成功插回,避免重新指派一架無人機(jī).

在局部搜索過程中,移除算子與插入算子具有相同的權(quán)重,采用輪盤賭方式隨機(jī)選擇算子的組合.局部搜索算法的主要步驟見算法3.

3 實(shí)驗分析

由于無人機(jī)在整個飛行、偵察以及懸停等待過程中所消耗的電量水平均有所不同,假定耗電率均與所耗時間線性相關(guān).且無人機(jī)在充電站會根據(jù)實(shí)際需求進(jìn)行適當(dāng)充電,因此,其充電時間與充電水平、充電速率均相關(guān).本實(shí)驗中關(guān)于無人機(jī)的相關(guān)參數(shù)設(shè)定見表1.

表1 無人機(jī)相關(guān)參數(shù)Table 1 Related parameters of UAV

為了驗證本文的模型與算法,在實(shí)驗中分別對4種規(guī)模案例（A,B,C,D）進(jìn)行求解,分別含有5,10,15,100 個目標(biāo)偵察點(diǎn)以及相對應(yīng)的充電平臺數(shù)量（包括基地）分別為4,4,5 和21.算法所有代碼由Visual C++ 編程實(shí)現(xiàn),在處理器為Intel（R）Core（TM）i5 -8265U,內(nèi)存8 G 的筆記本電腦上運(yùn)行,蟻群算法相關(guān)的參數(shù)值設(shè)定為P=30,α=5,β=5,γ=10,=0.25,Q=100,種群迭代100 次,算法停止.結(jié)果如表2所示.

表2 4 個案例的計算結(jié)果Table 2 The results of the four cases

算法3 局部搜索Input:不考慮充電站的NR 解Output:最優(yōu)可行解1 初始化算子權(quán)重2 插入充電站生成可行解3 4 While 迭代次數(shù)小于最大迭代次數(shù)5 隨機(jī)選擇移除算子,并生成移除列表6隨機(jī)選擇插入算子,將列表中的客戶點(diǎn)重新插入7 調(diào)用插入算法插入充電站，生成當(dāng)前可行解8 if 總成本低于9 10 End if 11 移除中所有解,得到新的最優(yōu)解12 End While

在飛行偵察路徑中,所有無人機(jī)均從基地出發(fā),結(jié)束偵察任務(wù)后返回基地.路線中序號代表目標(biāo)偵察點(diǎn)以及充電站,括號內(nèi)的數(shù)值表示無人機(jī)在該充電站的實(shí)際充電水平,具體飛行路線如圖4所示.實(shí)驗結(jié)果顯示改進(jìn)的蟻群算法可以在18 s 內(nèi)解決15 個目標(biāo)點(diǎn)以內(nèi)的小規(guī)模,可以在25 min 內(nèi)解決包含100個目標(biāo)點(diǎn)的大規(guī)模案例.

圖4 不同規(guī)模案例的飛行路徑Fig 4 The routes for cases of different size

為了進(jìn)一步確定改進(jìn)蟻群算法的效果,應(yīng)用傳統(tǒng)蟻群算法對4 個案例進(jìn)行了求解,并將計算結(jié)果和改進(jìn)蟻群的計算結(jié)果進(jìn)行了對比,如表3所示.可以看出,對于5 個偵察點(diǎn)的小規(guī)模案例,兩者都得到了相同的最優(yōu)解,而對于另外3 個中等規(guī)模和大規(guī)模的案例,改進(jìn)蟻群算法明顯優(yōu)于傳統(tǒng)蟻群算法.因此,從計算時間和效果來看,改進(jìn)蟻群算法具有較高的實(shí)際應(yīng)用價值.

表3 蟻群改進(jìn)前后求解方案目標(biāo)值對比Table 3 The results of the four cases

4 結(jié)論

針對小型無人機(jī)在復(fù)雜戰(zhàn)場環(huán)境下的目標(biāo)情報偵察任務(wù)中的應(yīng)用,提出了一種中繼充電模式下的無人機(jī)偵察路徑規(guī)劃問題.當(dāng)無人機(jī)電量不足時,允許無人機(jī)在偵察過程中可以飛往特定的充電平臺進(jìn)行快速充電以完成后續(xù)偵察任務(wù),且采用部分充電策略來盡可能地減少充電時間,從而更快速地完成戰(zhàn)場偵察.通過改進(jìn)蟻群算法對問題進(jìn)行求解,實(shí)驗結(jié)果顯示改進(jìn)蟻群算法明顯優(yōu)于傳統(tǒng)蟻群算法,并且對于大規(guī)模問題的計算時間控制在25 min 以內(nèi),在實(shí)際任務(wù)規(guī)劃中具有較高的應(yīng)用價值.

在未來智能化、無人化戰(zhàn)爭中,越來越多的小型無人機(jī)將被用于執(zhí)行各種作戰(zhàn)任務(wù),中繼充電模式具有廣闊的應(yīng)用前景.無人機(jī)中繼充電路徑優(yōu)化作為一類新的路徑規(guī)劃問題,還存在很多擴(kuò)展研究方向,如無人機(jī)偵察過程中充滿著很多不確定因素和風(fēng)險因素,在路徑規(guī)劃中增加敵方威脅、目標(biāo)動態(tài)變化等因素的影響,研究不確定中繼充電路徑規(guī)劃方法,為復(fù)雜動態(tài)戰(zhàn)場環(huán)境下的小型無人機(jī)指揮控制提供理論支撐.