趙 坤, 隨旭東, 梁 靜, 岳彩通, 李功平, 于坤杰

(1.中國電子科技集團公司 第二十七研究所,河南 鄭州 450001; 2.鄭州大學(xué) 電氣與信息工程學(xué)院,河南 鄭州 450001)

近年來,隨著無人飛行平臺科技水平的快速發(fā)展,其應(yīng)用場景已經(jīng)廣泛融入社會生產(chǎn)生活的各個方面。目前,無人飛行平臺已經(jīng)被廣泛應(yīng)用于通信中繼、農(nóng)業(yè)植保、搜查救援等多個重要領(lǐng)域[1-3],極大地減輕了相關(guān)工作量,產(chǎn)生了巨大的經(jīng)濟與社會效益。但是由于單無人飛行平臺的工作能力有限,多無人飛行平臺合作執(zhí)行任務(wù)成為目前主流的研究與應(yīng)用趨勢,解決雙平臺任務(wù)協(xié)作調(diào)度問題是推廣到多平臺應(yīng)用的基礎(chǔ),因此本文選擇以雙無人飛行平臺入手解決傳感器規(guī)劃調(diào)度問題。

無人飛行平臺具有行動便捷、造價低廉等優(yōu)勢,因此現(xiàn)階段對于地面目標(biāo)的捕獲、探測都是依靠無人飛行平臺來進行。在無人飛行平臺執(zhí)行任務(wù)之前,需要根據(jù)飛行航線、搭載設(shè)備、目標(biāo)情況等對任務(wù)進行規(guī)劃。隨著飛行平臺集成化程度的提高與所需捕獲目標(biāo)數(shù)目的增多,人工制定調(diào)度方案已經(jīng)不能滿足實際需求。目前,雙無人飛行平臺的傳感器調(diào)度規(guī)劃主要面臨著以下問題。

(1)由于兩個無人飛行平臺對于同一目標(biāo)群體進行捕獲,因此兩個平臺的任務(wù)之間存在復(fù)雜的耦合關(guān)系,并且需要考慮平臺間的協(xié)同問題[4-5]。需要根據(jù)無人飛行平臺所攜帶的探測設(shè)備與航線對任務(wù)進行合理的分配。

(2)在執(zhí)行任務(wù)的過程中,需要考慮多方面的因素。首先,需要保證在規(guī)劃調(diào)度中獲得盡可能高的任務(wù)收益[6]。其次,在任務(wù)中需要最大程度上顧及所有的目標(biāo),同時也需要考慮捕獲設(shè)備的空閑情況。

(3)由于無人飛行平臺數(shù)據(jù)處理能力的限制,平臺所搭載的傳感器在同一時刻只能捕獲一定數(shù)目的目標(biāo)[7]。因此,傳感器的分配與捕獲目標(biāo)的取舍都會對任務(wù)結(jié)果產(chǎn)生巨大的影響。

本文以無人飛行平臺航程占比作為任務(wù)初步分配指標(biāo),采用多傳感器共同捕獲與任務(wù)遷移方法來提高任務(wù)收益,針對雙無人飛行平臺的傳感器調(diào)度問題提出有效的解決方案,并通過仿真實驗驗證了算法的有效性。

1 相關(guān)工作

無人飛行平臺已經(jīng)被廣泛應(yīng)用到了目標(biāo)的跟蹤捕獲領(lǐng)域,如何通過飛行平臺所接收的信息規(guī)劃跟蹤方案是一個巨大挑戰(zhàn),根據(jù)無人飛行平臺目標(biāo)跟蹤算法所應(yīng)用的方向,可將其分為3類。第1類是基于相關(guān)濾波的目標(biāo)跟蹤算法,如Li等[8]提出基于增強記憶的相關(guān)濾波算法,通過學(xué)習(xí)記憶存檔等方法使得濾波器可以有效地跟蹤目標(biāo),但跟蹤精度不高。第2類是基于深度學(xué)習(xí)的目標(biāo)跟蹤算法,如Danelljan等[9]提出通過卷積層將輸出映射為響應(yīng)圖確定目標(biāo)跟蹤位置,但需要相關(guān)硬件的幫助才能滿足任務(wù)的實時性需求。第3類是基于相關(guān)濾波與深度學(xué)習(xí)相結(jié)合的目標(biāo)跟蹤算法,如Ma等[10]提出先利用卷積層特征調(diào)整分辨率,再訓(xùn)練相關(guān)濾波器,結(jié)合了兩者的特征,實現(xiàn)了對目標(biāo)的有效跟蹤,但相關(guān)技術(shù)還不成熟。

相較于單無人飛行平臺,多無人飛行平臺協(xié)作在時間效率、容錯性以及工作范圍等方面都明顯優(yōu)于前者,但也面臨著調(diào)度復(fù)雜、碰撞安全等問題。為解決上述存在的問題,越來越多的研究者開始從事多無人平臺協(xié)作的研究。針對多無人飛行平臺的任務(wù)規(guī)劃系統(tǒng),主要根據(jù)自主性分為3類:在低自主性系統(tǒng)中,飛行平臺自身無自主行動能力,并按照提前規(guī)劃的路徑執(zhí)行任務(wù),任務(wù)的收益與規(guī)劃效果密切相關(guān);在一般自主性系統(tǒng)中,無人飛行平臺具有一定的自主性,操作人員只需要選定任務(wù)區(qū)域,無人機即可自主規(guī)劃任務(wù);在高自主性系統(tǒng)中,無須操作人員干預(yù),系統(tǒng)即可根據(jù)外部環(huán)境狀態(tài)的變化自行規(guī)劃任務(wù)。對于多無人飛行平臺任務(wù)協(xié)作,Skorobogatov等[11]對于目前多無人飛行系統(tǒng)的分類、應(yīng)用及一些技術(shù)細(xì)節(jié)都進行了詳細(xì)敘述。

在單無人飛行平臺的多傳感器調(diào)度領(lǐng)域,目前已經(jīng)有部分學(xué)者提出了一些可行方案。如趙坤等[12]使用遺傳算法,提出一種結(jié)合目標(biāo)價值,解決復(fù)雜約束條件的傳感器調(diào)度方案。張龍龍等[13]使用幾何精度稀疏因子作為衡量適應(yīng)度函數(shù)的指標(biāo),利用遺傳算法實現(xiàn)對于傳感器調(diào)度的自動規(guī)劃。劉睿等[14]在文獻[12-13]的基礎(chǔ)上,根據(jù)目標(biāo)的捕獲情況,提出一種目標(biāo)的拆分合并機制,減輕了目標(biāo)任務(wù)之間的耦合,可以搜索到較為優(yōu)秀的傳感器資源配置方案。在多無人飛行平臺的多傳感器調(diào)度領(lǐng)域,Emami等[15]提出一種使用無人機群收集地面信息的研究方法,通過聯(lián)合控制無人機速度與采集數(shù)據(jù)計劃盡可能多地減少數(shù)據(jù)包的丟失,但缺點是任務(wù)覆蓋的范圍較小。Khodaparast等[16]設(shè)計了一種基于多無人機系統(tǒng)的數(shù)據(jù)傳輸網(wǎng)絡(luò),通過控制調(diào)度相關(guān)傳感器的使用,擴大任務(wù)的覆蓋范圍。Zheng等[17]提出了一種基于多無人機多傳感器調(diào)度的兩級自適應(yīng)變量領(lǐng)域搜索算法,提升了算法的規(guī)劃效率。Fei等[18]設(shè)計了一種使用機器學(xué)習(xí)方法對多傳感器數(shù)據(jù)進行數(shù)據(jù)融合的方法,有效提升了多無人機系統(tǒng)執(zhí)行任務(wù)時的精度與收益。由于上述工作解決調(diào)度問題的計算時間較長,不能滿足對于調(diào)度任務(wù)實時性的要求[19]。此外,上述工作在進行傳感器調(diào)度時,并未考慮傳感器資源沖突區(qū)域的分配,因此浪費了大量的任務(wù)收益。為解決在雙無人飛行平臺背景下,傳感器調(diào)度中存在的算法耗時與傳感器資源沖突區(qū)域調(diào)度問題,本文設(shè)計了結(jié)合多傳感器共同捕獲與任務(wù)遷移方法的雙無人飛行平臺的傳感器調(diào)度算法。

2 算法原理

2.1 算法框架

本文所設(shè)計的算法主要包含4個步驟,算法流程圖如圖1所示。首先,根據(jù)平臺航線與目標(biāo)的位置關(guān)系,給每個飛行平臺分配預(yù)定的任務(wù)。其次,通過目標(biāo)、傳感器與飛行平臺的適配情況進行預(yù)分配,對于稀缺的傳感器資源與獨立的目標(biāo)進行標(biāo)記。再次,以任務(wù)收益為依據(jù),對每個平臺進行上的傳感器與目標(biāo)的分配進行匹配。最后,對于未完成既定捕獲任務(wù)的目標(biāo)進行任務(wù)遷移,將未完成的任務(wù)遷移到有空閑捕獲資源的航段。

圖1 算法流程圖Figure 1 Algorithm flowchart

2.2 平臺任務(wù)分配及評價指標(biāo)

由于雙無人飛行平臺的目標(biāo)種群相同,大部分目標(biāo)都處于可以被兩個平臺捕獲的位置,因此兩個平臺的任務(wù)之間存在較強的耦合關(guān)系。為了簡化求解難度,本文算法以每個平臺的探測范圍與目標(biāo)的相交距離為依據(jù),利用可探測范圍的比例初步分配兩個平臺之間的任務(wù)。對平臺任務(wù)進行分配后,則將雙平臺協(xié)作的捕獲任務(wù)簡化為了兩個單平臺的目標(biāo)捕獲任務(wù)。無人飛行平臺的目標(biāo)捕獲任務(wù)可以表示為

(1)

為了直觀地比較算法的結(jié)果,本文采用與文獻[14]相同的評價機制。任務(wù)收益P的定義如下:

(2)

(3)

2.3 目標(biāo)及傳感器的預(yù)處理

由于傳感器資源是有限的,目標(biāo)之間存在競爭關(guān)系,為了減少目標(biāo)爭奪傳感器資源的情況,需要在分配之前對于目標(biāo)與傳感器進行預(yù)處理操作。目標(biāo)的預(yù)處理如圖2所示。

圖2 目標(biāo)的預(yù)處理Figure 2 Preprocessing of the target

圖2中,F1與F2為雙無人飛行平臺的預(yù)定航線,虛線代表所屬目標(biāo)可被捕獲的空間范圍。目標(biāo)T1、T2、T5均可被兩個無人飛行平臺捕獲,目標(biāo)T3僅可被平臺F2所在的航線捕獲,T4僅可被F1所在航線捕獲,因此,由于T3與T4的獨立歸屬性將其標(biāo)記為獨立目標(biāo),在對相應(yīng)的平臺進行規(guī)劃調(diào)度時,提高相對應(yīng)目標(biāo)的調(diào)度優(yōu)先級。

在進行調(diào)度任務(wù)規(guī)劃之前,對于目標(biāo)進行逐個的判斷,記錄可以用來對目標(biāo)Ti進行捕獲的所有傳感器Sj。如圖3所示,目標(biāo)T2可以被傳感器S2、S5、S6與S9捕獲,因此目標(biāo)T2在傳感器調(diào)度中的選擇較多,而目標(biāo)T4、T5、T7與T8僅可以被傳感器S2捕獲。如果目標(biāo)T2分配到了傳感器S2,那么在后續(xù)的調(diào)度中,上述只有1個可用傳感器的目標(biāo)就有很大的概率沒有可用的傳感器。將傳感器S2標(biāo)記為稀缺傳感器后,在進行傳感器調(diào)度時,目標(biāo)T2、T6就會優(yōu)先選擇其他非稀缺傳感器,可以有效地降低對于稀缺傳感器資源的競爭。

圖3 傳感器的預(yù)處理Figure 3 Preprocessing of the sensor

2.4 傳感器的調(diào)度分配

傳感器調(diào)度中最重要的工作就是分配合適的傳感器、目標(biāo)與平臺組合,為了解決傳感器調(diào)度中調(diào)度規(guī)模大以及目標(biāo)較多不易處理等問題,本文設(shè)計了航段拆分與多傳感器協(xié)同捕獲的策略。由于飛行平臺的航線由多個連續(xù)航段組成,因此每一航段上都存在著若干個需要捕獲的目標(biāo)。如果從整個航線的角度對傳感器進行規(guī)劃調(diào)度,那么調(diào)度的規(guī)模相較于每一航段來說是倍數(shù)式增長的;從航段角度入手逐段解決調(diào)度問題,需要考慮的規(guī)劃調(diào)度的規(guī)模就會有大幅度的減少,拆分操作的定義如下:

Fi=[Fi-1,Fi-2,…,Fi-n];

(4)

(5)

式中:Fi代表第i條航線;Fi-j代表i航線上的j航段同時由Fi-j組成1個捕獲狀態(tài)列表;OT1,1代表航段Fi-j在第1個捕獲位置上目標(biāo)T1的狀態(tài),當(dāng)狀態(tài)為1時表示對此位置進行捕獲操作,為0時表示不進行捕獲。

多傳感器協(xié)同捕獲可以有效地解決目標(biāo)較多時,某一目標(biāo)對傳感器資源長時間占用的問題。如圖4所示,假設(shè)無人飛行平臺上共搭載了4個捕獲傳感器,對5個等距且捕獲次數(shù)相等的目標(biāo)都可以進行捕獲,箭頭表示飛行平臺的航向,點線表示目標(biāo)可捕獲的范圍,由于篇幅原因部分目標(biāo)的可捕獲航段進行了省略。在使用單一傳感器捕獲目標(biāo)的情況下,飛行到T5時前4個目標(biāo)已經(jīng)占據(jù)了所有可用傳感器。當(dāng)采用多傳感器協(xié)同捕獲的策略后,在目標(biāo)T1進入捕獲范圍之后,4個可用傳感器對T1進行協(xié)同捕獲,捕獲效率將提升4倍;當(dāng)目標(biāo)T2進入捕獲范圍以后,對于目標(biāo)T1只保留主捕獲傳感器,將剩余3個傳感器全部釋放給目標(biāo)T2。采取多傳感器協(xié)同捕獲目標(biāo)后,目標(biāo)T1的捕獲距離縮短了3/5,T2的距離縮短了2/5,當(dāng)目標(biāo)T5進入捕獲范圍之后,存在2個可用傳感器,解決了單傳感器捕獲中目標(biāo)占據(jù)傳感器資源時間較長的問題,減輕了傳感器的調(diào)度壓力。

圖4 多傳感器協(xié)同捕獲Figure 4 Multi-sensor collaborative capture

對于傳感器的調(diào)度,本文采取的規(guī)劃方法是按捕獲順序逐個進行的,以任務(wù)收益為基礎(chǔ)對傳感器進行規(guī)劃調(diào)度。具體操作如下。

步驟1 將航線按航段拆分,將航段所對應(yīng)目標(biāo)的捕獲任務(wù)按航段所占航程的比例進行分配,初始化每一航段的傳感器狀態(tài)集合Aa,i并讀取在傳感器預(yù)處理中得到的可用傳感器列表Ij。(其中,a表示傳感器標(biāo)號,i表示航段編號,j為目標(biāo)編號)。

步驟2 對于第i航段的目標(biāo)j根據(jù)其可用傳感器列表Ii,檢查在目標(biāo)捕獲起始位置傳感器的空閑情況。

步驟3 如果存在空閑的傳感器a,則將目標(biāo)j加入到Aa,i中,對于處于占用狀態(tài)的傳感器,檢查占用傳感器資源的目標(biāo)中是否存在本傳感器非此目標(biāo)主捕獲傳感器的情況,如果存在則釋放相關(guān)資源,釋放的目標(biāo)中未完成捕獲任務(wù)的部分轉(zhuǎn)移到釋放目標(biāo)的主捕獲傳感器的任務(wù)中。將目標(biāo)的捕獲任務(wù)均分給當(dāng)前所有對于目標(biāo)j的可用空閑傳感器。如果不存在可用傳感器,則執(zhí)行步驟4。

步驟4 根據(jù)當(dāng)前目標(biāo)j的可用傳感器列表Ij,讀取列表中占用傳感器的目標(biāo)編號,并計算目前占用Ij傳感器中所有目標(biāo)與目標(biāo)j重疊的捕獲航程,選擇重疊捕獲航程距離Lmin的最小的目標(biāo)Tmin。目標(biāo)j僅需完成本航段所預(yù)定捕獲任務(wù)即可,如本航段的可捕獲航程大于預(yù)定捕獲任務(wù),那么兩者之間存在差值Lj。若滿足Lj≥Lmin,那么當(dāng)前目標(biāo)j的捕獲任務(wù)的起點則移動到目標(biāo)Tmin的終點處,同時當(dāng)前目標(biāo)j的捕獲任務(wù)的終點后移距離Lmin;如果Lj

步驟5 將當(dāng)前目標(biāo)j的捕獲起點與終點向后移動Lj后,計算目前占用Ij傳感器中所有目標(biāo)與目標(biāo)j重疊的捕獲航程與威脅程度的乘積,若目標(biāo)為獨立目標(biāo)則將目標(biāo)威脅程度加1進行計算,此結(jié)果為重疊航程的捕獲價值。選取具有最小重疊價值Pmin的目標(biāo)TPmin對比目標(biāo)j的重疊價值Pj。若滿足Pj≥Pmin,則將TPmin的終點截斷到目標(biāo)j的起點;若滿足Pj

在傳感器狀態(tài)集Aa,i中,對于實施目標(biāo)捕獲的航段位置使用1進行標(biāo)記;對于可進行目標(biāo)捕獲的航段,若未進行捕獲的位置使用-1進行標(biāo)記。圖5表述了所采用方法的步驟。對目標(biāo)T2進行任務(wù)調(diào)度時與目標(biāo)T1發(fā)生資源競爭,此時T2處于未安排捕獲任務(wù)的航段長度滿足T1與T2沖突航段移動條件,因此T2的調(diào)度任務(wù)的起點與終點后移即可解決傳感器資源競爭問題。

圖5 重疊捕獲航段的移動Figure 5 Movement of overlapping capture flight segments

2.5 任務(wù)遷移

在傳感器調(diào)度過程中,由于資源沖突問題,會導(dǎo)致部分目標(biāo)的預(yù)定捕獲任務(wù)不能完成,因此設(shè)計任務(wù)遷移機制將未完成的任務(wù)通過遷移到本目標(biāo)的其他航段,或者遷移到本傳感器下其他有空閑資源目標(biāo)的航段來對未完成的任務(wù)進行補分配。具體流程如下。

步驟1 對于未完成既定捕獲任務(wù)的目標(biāo)j,檢測此目標(biāo)是否在多個航段上被捕獲,如果可以則執(zhí)行步驟2,否則執(zhí)行步驟3。

步驟2 統(tǒng)計目標(biāo)j在所有航段上未進行捕獲任務(wù)的航段的傳感器狀態(tài)列表的空閑情況,若上述傳感器資源占用未超出上限,則可將此位置作為任務(wù)遷移的選擇。若執(zhí)行此操作后目標(biāo)j仍有任務(wù)未完成,則執(zhí)行步驟3。

步驟3 檢測所有航段上與目標(biāo)j存在資源競爭關(guān)系的目標(biāo),監(jiān)測競爭目標(biāo)是否存在未進行捕獲任務(wù)航段的傳感器資源占用未超出上限的情況,若存在則可將競爭目標(biāo)目前占用的傳感器資源遷移給目標(biāo)j。在任務(wù)遷移之后,遷移目標(biāo)的捕獲次數(shù)會發(fā)生如下變化:

(6)

ETx=CTx+MTx。

(7)

式中:CTx表示目標(biāo)Tx的捕獲總次數(shù);n為航線數(shù);m為航線上的航段數(shù);MTx為遷移的捕獲次數(shù)。

為了便于理解任務(wù)遷移的具體流程,圖6展示了步驟2中同目標(biāo)之間任務(wù)遷移的示意圖。在航段1、2上對同一目標(biāo)都可對其進行捕獲,但是由于傳感器資源的競爭關(guān)系,致使在航段1上有部分任務(wù)未完成。經(jīng)過搜索發(fā)現(xiàn)同一目標(biāo)在航段2上存在部分空閑資源,那么即可將在航段1上未完成的任務(wù)遷移到航段2的任務(wù)上。

圖6 同目標(biāo)之間任務(wù)遷移Figure 6 Task transfer between the same target

3 仿真實驗

為了驗證雙無人飛行平臺的多傳感器調(diào)度算法(multi-sensor scheduling algorithm for dual unmanned flight platforms,DUFP-MSS)在雙無人平臺任務(wù)環(huán)境下的性能,本文選取文獻[14]中的GA-TSP作為對比算法,從調(diào)度規(guī)劃時間與調(diào)度任務(wù)收益兩方面對算法的性能進行評估。本文選取10個不同目標(biāo)個數(shù)的測試問題進行比較。出于數(shù)據(jù)安全和保密性考慮,測試問題的航線以及目標(biāo)相關(guān)的參數(shù)依據(jù)實際航線的數(shù)據(jù)特征和規(guī)律重新生成,其中目標(biāo)所處高度及目標(biāo)威脅程度等參數(shù)與航線的固有屬性相關(guān),一旦航線確定這些參數(shù)也成為固定值。算法在每個測試問題上獨立運行30次,表1分別記錄了10個測試問題中捕獲目標(biāo)的個數(shù)。測試問題的詳細(xì)信息可在https:∥github.com/cilabsxd/DUFP-MSS-Test-Data下載。

表1 測試問題的目標(biāo)個數(shù)Table 1 Target number of test questions

表2記錄了DUFP-MSS與GA-TSP在10個測試問題上獨立運行30次的平均時間與方差。由結(jié)果可知,GA-TSP的運行速度相較于DUFP-MSS更慢,并且30次運行時間的方差較大。這是因為GA-TSP采取進化算法來解決規(guī)劃問題,由于傳感器規(guī)劃調(diào)度問題屬于有較強約束的問題,因此GA-TSP生成子代的過程中不易生成可行解,浪費了大量的運行時間,而DUFP-MSS在進行調(diào)度安排時采取逐段求解的方法,減少了大量的約束條件,運行速度更快。

表2 算法的運行時間Table 2 Algorithm running time

表3記錄了DUFP-MSS與GA-TSP在10個測試問題上獨立運行30次的平均任務(wù)收益。DUFP-MSS在10個測試問題上的結(jié)果都明顯優(yōu)于GA-TSP,這是由于DUFP-MSS采取了逐段調(diào)度的方法使得傳感器資源的競爭減小,并且采用了任務(wù)遷移的補分配機制。而GA-TSP在進行調(diào)度規(guī)劃任務(wù)時,不能解決傳感器資源競爭的問題,且沒有考慮傳感器中存在稀缺資源的問題。通過比較可知,DUFP-MSS無論是在運行速度還是任務(wù)收益上都優(yōu)于GA-TSP。DUFP-MSS在計算任務(wù)收益時,使用目標(biāo)威脅程度作為主要參考依據(jù),在對同一任務(wù)進行重復(fù)多次調(diào)度時,由于任務(wù)中所有目標(biāo)的威脅程度不變,因此所有目標(biāo)的優(yōu)先調(diào)度順序也是不變的。DUFP-MSS多次調(diào)度的任務(wù)收益為定值,所以方差為0;而GA-TSP在進行任務(wù)調(diào)度時,任務(wù)收益與其隨機初始化種群有一定聯(lián)系,此外在進化過程中突變是隨機的,因此多次調(diào)度的任務(wù)收益會有波動,其任務(wù)收益具有一定的方差。

表3 算法的任務(wù)收益Table 3 Algorithm task benefits

4 結(jié)論

本文通過將無人飛行平臺任務(wù)分配、目標(biāo)及傳感器預(yù)處理、傳感器調(diào)度分配與任務(wù)遷移相結(jié)合,提出了一種解決雙無人飛行平臺的多傳感器調(diào)度問題的高效算法,可以在極短時間內(nèi)給出一個較為合理的傳感器調(diào)度方案。通過比較現(xiàn)有算法,驗證了DUFP-MSS的有效性。DUFP-MSS相較于GA-TSP可以取得較高的任務(wù)收益,同時運行時間減少了3個數(shù)量級,在算法穩(wěn)定性方面也具有較大的優(yōu)勢。

在雙無人飛行平臺的多傳感器調(diào)度問題領(lǐng)域仍有一些問題沒有得到充分的研究。首先,目前解決傳感器資源沖突問題是從局部考慮的,下一步需要研究如何從全局去協(xié)調(diào)傳感器解決資源沖突問題。其次,多無人飛行器協(xié)同工作已成為發(fā)展與應(yīng)用的主要趨勢,如何協(xié)同多個飛行器共同執(zhí)行任務(wù)并進行合理分配仍需要進一步的研究。