毛慧婷 石建邁 周玉珍 劉 忠

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

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

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

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

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

1 問題描述與建模

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

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

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

1.1 小型無人機

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

1.2 中繼充電平臺

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

1.3 偵察目標

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

算法1 改進的蟻群算法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表示下一個目標點j的最晚服務(wù)時間,該值越小表示其時間窗越緊迫.

2.2 信息素更新

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

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

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

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

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

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

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

2.4 局部搜索算法

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

2.4.1 移除算子

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

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

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

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

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

圖2 最差目標點刪除算子Fig 2 Worst-distance target removal

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

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

圖3 基于距離的目標點刪除算子Fig 3 Proximity-based target removal

2.4.2 插入算子

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

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

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

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

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

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

3 實驗分析

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

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

為了驗證本文的模型與算法,在實驗中分別對4種規(guī)模案例（A,B,C,D）進行求解,分別含有5,10,15,100 個目標偵察點以及相對應(yīng)的充電平臺數(shù)量（包括基地）分別為4,4,5 和21.算法所有代碼由Visual C++ 編程實現(xiàn),在處理器為Intel（R）Core（TM）i5 -8265U,內(nèi)存8 G 的筆記本電腦上運行,蟻群算法相關(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 隨機選擇移除算子,并生成移除列表6隨機選擇插入算子,將列表中的客戶點重新插入7 調(diào)用插入算法插入充電站，生成當前可行解8 if 總成本低于9 10 End if 11 移除中所有解,得到新的最優(yōu)解12 End While

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

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

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

表3 蟻群改進前后求解方案目標值對比Table 3 The results of the four cases

4 結(jié)論

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

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