張海龍, 夏 維, 胡笑旋, 楊 斌, 湯 航

(1.合肥工業(yè)大學(xué)管理學(xué)院, 安徽 合肥 230009; 2.過程優(yōu)化與智能決策教育部重點實驗室,安徽 合肥 230009; 3.北京遙感信息研究所, 北京 100192)

0 引 言

隨著海上活動日益頻繁,對海洋動目標(biāo)搜索有著極大的應(yīng)用需求,如海洋營救、浮游生物監(jiān)測、海上緝私等。但動目標(biāo)運動的不確定性,使對其搜索極為復(fù)雜[1]。早期關(guān)于動目標(biāo)搜索的研究主要集中于在目標(biāo)分布規(guī)律已知的條件下,給出搜索資源的最優(yōu)分配方案及航跡規(guī)劃方案,以快速高效地搜索到目標(biāo)[2-5]。這種資源分配方案適用于無人機、機器人、偵查艇等航跡可規(guī)劃的偵查資源,然而這類偵查資源應(yīng)用于海上動目標(biāo)搜索時,受視距和活動范圍限制,效果不甚理想[6]。成像衛(wèi)星可從空間軌道上利用星載遙感設(shè)備對指定區(qū)域?qū)嵤┏上?獲取目標(biāo)情報信息[7]。因不受地理國界等因素限制,將其應(yīng)用于海洋動目標(biāo)搜索的研究引起了學(xué)者重視。文獻[8-9]將成像衛(wèi)星搜索海上動目標(biāo)問題看作傳感器資源調(diào)度問題,基于貝葉斯估計和信息熵度量提出了解決此類問題的通用方法,并介紹了在信息不確定條件下基于高斯分布的目標(biāo)運動預(yù)測模型。文獻[10]采用了強化學(xué)習(xí)的方法求解多星搜索海上多個移動目標(biāo)的傳感器調(diào)度問題。文獻[11]研究了電子偵查衛(wèi)星與成像衛(wèi)星協(xié)同進行海洋移動目標(biāo)搜索的機制。文獻[12]將海上動目標(biāo)搜索問題分解成為遙感器規(guī)劃調(diào)度問題和動目標(biāo)狀態(tài)預(yù)測問題的求解框架,基于此求解框架,動目標(biāo)搜索過程中不斷獲得環(huán)境信息,并利用所得信息指導(dǎo)后續(xù)搜索。為更好的描述動目標(biāo)運動及搜索過程中環(huán)境信息變化,部分學(xué)者使用搜索圖[13-15]建立動目標(biāo)搜索環(huán)境模型。文獻[16]利用搜索圖表示目標(biāo)運動情況,并根據(jù)搜索結(jié)果采用不同的方法更新搜索圖。文獻[17]綜合考慮目標(biāo)概率分布及環(huán)境信息,建立動目標(biāo)搜索的感知信息圖,在此基礎(chǔ)上搜索動目標(biāo)。上述研究較好的解決了平坦地域或海面條件下動目標(biāo)搜索問題。

在現(xiàn)實情況下,目標(biāo)所處環(huán)境可能存在障礙物或探測裝置影響目標(biāo)運動,從而影響對目標(biāo)的搜索。如文獻[18]考慮環(huán)境中存在感知探測裝置,待搜索運動目標(biāo)能夠通過探測裝置獲得無人機的位置信息,從而改變運動策略,減少位置暴露。文獻[19]在動態(tài)任務(wù)分配的研究中,制定了機器人在探測到環(huán)境中障礙物時的反應(yīng)策略。文獻[20]在搜索海域存在障礙物的情況下,將啟發(fā)式搜索算法應(yīng)用于對水下動目標(biāo)的搜索,并建立了水下動目標(biāo)規(guī)避模型,使搜索器在進行水下動目標(biāo)搜索時能有效地規(guī)避障礙,提高搜索效率。但在考慮環(huán)境障礙物情況下利用衛(wèi)星進行海面動目標(biāo)搜索相關(guān)研究較少。

本文針對衛(wèi)星搜索多障礙物海面動目標(biāo)問題,利用搜索圖建立動目標(biāo)搜索環(huán)境模型,基于目標(biāo)馬爾可夫運動過程,提出一種面向多障礙物搜索海面的動目標(biāo)運動預(yù)測方法。搜索圖在根據(jù)衛(wèi)星探測信息進行更新之后以此運動預(yù)測方法再次更新,指導(dǎo)衛(wèi)星下次搜索。仿真實驗驗證了本文方法在解決面向多障礙物海面衛(wèi)星搜索海洋動目標(biāo)問題的有效性。

1 問題描述

多障礙物海面指海面存在如礁石等障礙物,在此海面航行的動目標(biāo)需規(guī)避海面障礙物。設(shè)搜索任務(wù)起始時間為Ts,截止時間為Te。目標(biāo)搜索首先根據(jù)獲得的情報信息,判斷任務(wù)區(qū)域R,任務(wù)區(qū)域指目標(biāo)在整個搜索周期內(nèi)的最大活動范圍。為方便問題處理,將R進行網(wǎng)格劃分,編號為1～M。成像衛(wèi)星從空間軌道上利用星載遙感器觀測R,對R中的NT個動目標(biāo)進行搜索,如圖1所示。

圖1 多障礙物海面上衛(wèi)星搜索動目標(biāo)示意圖Fig.1 Diagrammatic sketch of moving targets search onmulti-obstacle sea by satellite

NS顆成像衛(wèi)星在[Ts,Te]內(nèi)對任務(wù)區(qū)域R內(nèi)的NT個動目標(biāo)進行搜索,同時任務(wù)區(qū)域中存在NB個位置固定的障礙物。目標(biāo)做隨機馬爾可夫運動,并在運動過程中探測周圍障礙物,經(jīng)過一個時間步長,可從當(dāng)前所在網(wǎng)格隨機運動到任一相鄰的無障礙物網(wǎng)格。當(dāng)衛(wèi)星過境R時,從其觀測條帶集合中選擇一條目標(biāo)存在概率最大的條帶進行觀測,直至搜索任務(wù)結(jié)束。

2 問題建模

針對多障礙物海面動目標(biāo)搜索問題,在確定任務(wù)區(qū)域并進行網(wǎng)格劃分后,利用搜索圖建立反映目標(biāo)和環(huán)境信息的環(huán)境模型。設(shè)pi(t)為t時刻網(wǎng)格i中目標(biāo)存在概率,則t時刻的搜索圖定義為

SM(t)={pi(t)|i∈{1,2,…,M}}

(1)

在搜索過程中,搜索圖根據(jù)一定規(guī)則進行更新,并基于搜索圖提供的信息確定衛(wèi)星過境觀測時目標(biāo)存在概率最大的條帶。

2.1 基于探測信息的搜索圖更新模型

(2)

(3)

pi(tk)=0

(4)

(5)

式(2)和式(3)中,pd和pf會受到遙感器側(cè)向擺動影響,本文假設(shè)這些影響可以忽略且所有衛(wèi)星攜帶相同能力的遙感器資源。

2.2 基于目標(biāo)運動預(yù)測的搜索圖更新模型

目標(biāo)運動規(guī)律未知給衛(wèi)星搜索海面動目標(biāo)觀測計劃的制定帶來困難[25]。在平坦海面條件下,常采用基于高斯分布的目標(biāo)運動預(yù)測方法[8-9,23]減少搜索過程中因目標(biāo)運動帶來的不確定性。本文在使用搜索圖建立多障礙物海面動目標(biāo)搜索環(huán)境模型的基礎(chǔ)上,根據(jù)目標(biāo)馬爾可夫運動特性[26-28]分析海面障礙物對目標(biāo)運動的影響,提出面向多障礙物搜索海面的動目標(biāo)運動預(yù)測方法以減少搜索過程中目標(biāo)運動的不確定性。設(shè)搜索圖網(wǎng)格空間為I,L(t)=j(1≤j≤M,j∈I),表示在t時刻目標(biāo)處于編號為j的網(wǎng)格中。圖2為搜索圖網(wǎng)格空間的示意圖。目標(biāo)運動狀態(tài)為目標(biāo)經(jīng)過一個時間步長Δt能夠移動到當(dāng)前網(wǎng)格的相鄰網(wǎng)格,或仍停留在該網(wǎng)格。

圖2 搜索圖網(wǎng)格空間示意圖Fig.2 Diagrammatic sketch of the grid space of search map

假設(shè)t時刻目標(biāo)在標(biāo)號為5的網(wǎng)格中,即L(t)=5。經(jīng)過一個時間步長在t+Δt時刻目標(biāo)僅能移動到與5相鄰的網(wǎng)格1,2,3,4,6,7,8,9,或仍停留在網(wǎng)格5,故搜索圖中每個網(wǎng)格都對應(yīng)著一個3×3的目標(biāo)轉(zhuǎn)移概率矩陣,這些轉(zhuǎn)移概率矩陣定義了目標(biāo)的馬爾可夫運動過程。將海面動目標(biāo)的運動狀態(tài)按照一步轉(zhuǎn)移概率來表示,在t時刻目標(biāo)的一步轉(zhuǎn)移概率為

(6)

式中,Aj表示網(wǎng)格j及其相鄰的網(wǎng)格空間集合。式(6)表示在t時刻目標(biāo)處于網(wǎng)格j中,經(jīng)過Δt目標(biāo)運動到網(wǎng)格i中的概率。

(7)

在對動目標(biāo)搜索時,若已知待搜索目標(biāo)的情報信息,可以利用情報信息給出符合目標(biāo)實際運動情況的目標(biāo)轉(zhuǎn)移概率。當(dāng)不知目標(biāo)情報信息時,假設(shè)目標(biāo)經(jīng)過Δt移動到相鄰網(wǎng)格或在當(dāng)前網(wǎng)格保持靜止的概率分布服從均勻分布,即取

(8)

海面動目標(biāo)在運動過程中利用感知裝置對周圍環(huán)境進行探測,若相鄰網(wǎng)格存在障礙物,目標(biāo)能探測到該障礙物并進行規(guī)避。圖3為多障礙物海面上搜索圖網(wǎng)格空間示意圖。

圖3 多障礙物海面上搜索圖網(wǎng)格空間示意圖Fig.3 Diagrammatic sketch of the grid space of search map formulti-obstacle sea

若t時刻目標(biāo)處于網(wǎng)格j中,探測到相鄰網(wǎng)格空間中網(wǎng)格e存在障礙物,則令

(9)

對于當(dāng)前網(wǎng)格j及不存在障礙物的相鄰網(wǎng)格i，有

(10)

式中,η為網(wǎng)格j相鄰網(wǎng)格存在的障礙物總數(shù)且η<8。

圖3中,若目標(biāo)在t時刻位于編號為5的網(wǎng)格中,并探測到相鄰網(wǎng)格2和6存在障礙物,則目標(biāo)會規(guī)避障礙物,由式(9)得

對于不存在障礙物的網(wǎng)格i(i=1,3,4,5,7,8,9),由式(10)得

則目標(biāo)t時刻在網(wǎng)格5的一步轉(zhuǎn)移概率矩陣為

因成像衛(wèi)星分別在離散的時間點t1,t2,…,tk,…獲得觀測時間窗口,在衛(wèi)星第k次過境R進行觀測后,根據(jù)獲取的探測信息采用式(2)～式(5)更新搜索圖,獲得目標(biāo)后驗概率分布。在衛(wèi)星第k+1次過境R前目標(biāo)將持續(xù)在R內(nèi)運動,搜索圖需根據(jù)目標(biāo)運動特征進行更新,獲得第k+1次觀測前目標(biāo)先驗概率分布。設(shè)tk+1-tk=mkΔt(mk≥0),mk為兩次相鄰觀測時刻tk與tk+1相差的時間步長個數(shù)。目標(biāo)在一個時間步長內(nèi)完成一次在搜索圖網(wǎng)格空間上的轉(zhuǎn)移,則在第k次觀測與第k+1次觀測之間共完成了mk次運動轉(zhuǎn)移。

由目標(biāo)一步轉(zhuǎn)移概率,可得目標(biāo)m步轉(zhuǎn)移概率為

(11)

對于m步轉(zhuǎn)移概率滿足切普曼-柯爾莫哥洛夫方程式[29-30]:

(12)

由上述分析可知,在已知動目標(biāo)的初始概率分布及其一步轉(zhuǎn)移概率的條件下就可以求得在有限時間和狀態(tài)空間下目標(biāo)運動預(yù)測概率分布。已知在第k次觀測后,目標(biāo)在網(wǎng)格j中的后驗概率為pj(tk),tk+1-tk=mkΔt,mk≥0。假設(shè)tk時刻目標(biāo)在網(wǎng)格j中,則目標(biāo)在tk+1時刻移動到網(wǎng)格i中的概率為

(tk)=P{L(tk+mkΔt)=i|L(tk)=j}

(13)

由于目標(biāo)必然在R中移動,則有

(tk)=1,j∈I

(14)

進一步可得第k+1次觀測時目標(biāo)存在于網(wǎng)格i的先驗概率為

(tk)pj(tk)

(15)

綜上,在解決面向多障礙物海面衛(wèi)星搜索動目標(biāo)問題時,根據(jù)衛(wèi)星第k次過境探測信息更新搜索圖后,再采用目標(biāo)運動預(yù)測方法再一次更新搜索圖,從而獲得第k+1次衛(wèi)星觀測時目標(biāo)在搜索圖中的先驗概率分布,以指導(dǎo)衛(wèi)星觀測。

3 仿真與分析

本節(jié)針對衛(wèi)星搜索多障礙物海面動目標(biāo)問題進行仿真實驗。為驗證本文方法效果,在搜索過程中目標(biāo)運動預(yù)測環(huán)節(jié)將其與不采用目標(biāo)運動預(yù)測方法,以及基于高斯分布的目標(biāo)運動預(yù)測方法進行對比。其中不采用目標(biāo)運動預(yù)測方法即搜索圖在根據(jù)探測信息更新后不再基于目標(biāo)運動預(yù)測進行更新;基于高斯分布的目標(biāo)運動預(yù)測方法即在根據(jù)探測信息進行搜索圖更新后再基于該方法進行搜索圖更新?；诟咚狗植嫉哪繕?biāo)運動預(yù)測方法[8-9]假設(shè)目標(biāo)速度為v,目標(biāo)位置在x方向和y方向上保持獨立。目標(biāo)做勻速運動,將對目標(biāo)運動的隨機擾動視為方差為ξ的高斯白噪聲。設(shè)tk時刻目標(biāo)在(xk,yk),tk+1-tk=mkΔt,則tk+1時刻目標(biāo)轉(zhuǎn)移到(xk+1,yk+1)的概率分布服從高斯分布:

p{(xk+1,yk+1)|(xk,yk)}=

(16)

式中

(17)

(18)

(19)

針對這3種策略,以目標(biāo)存在概率最大化為目標(biāo)函數(shù),確定成像衛(wèi)星過境任務(wù)區(qū)域時所選觀測條帶。

(20)

實驗建立目標(biāo)任務(wù)區(qū)域如表1所示,并設(shè)定任務(wù)區(qū)域內(nèi)有6個待搜索運動目標(biāo)。

表1 任務(wù)區(qū)域位置

選取6顆衛(wèi)星對任務(wù)區(qū)域內(nèi)的目標(biāo)進行搜索,衛(wèi)星信息如表2所示。

表2 衛(wèi)星信息

設(shè)定衛(wèi)星星載遙感器pd=0.85,pf=0.15,仿真時間段為[1 Aug 2017 12:00:00.000 UTCG,2 Aug 2017 12:00:00.000 UTCG]。計算得衛(wèi)星在仿真時間段內(nèi)共有9次過境任務(wù)區(qū)域,如表3所示。

3.1 方法可行性驗證

將任務(wù)區(qū)域以0.1°的粒度劃分為60×60的網(wǎng)格,并編號1～3 600。設(shè)定目標(biāo)速度估計在10～15節(jié),時間步長Δt=0.5 h。仿真開始前各網(wǎng)格目標(biāo)存在概率設(shè)為0.5。通過隨機生成的方法生成3組任務(wù)區(qū)域內(nèi)的障礙物位置,使障礙物分別覆蓋網(wǎng)格空間中的200、400、600個網(wǎng)格。在無障礙物以及障礙物分別覆蓋200、400、600個網(wǎng)格4種情景下,在根據(jù)探測信息利用式(2)～式(5)進行搜索圖更新的基礎(chǔ)上,對不采用目標(biāo)運動預(yù)測方法、采用基于高斯分布的目標(biāo)運動預(yù)測方法、采用面向多障礙物搜索海面動目標(biāo)運動預(yù)測方法3種策略分別設(shè)計了仿真實驗,衛(wèi)星搜索仿真實驗過程如圖4所示。每組實驗重復(fù)100次,計算并比較了各策略下平均每個目標(biāo)發(fā)現(xiàn)次數(shù)。仿真實驗結(jié)果如圖5所示。

表3 衛(wèi)星過境任務(wù)區(qū)域時間窗信息

圖4 衛(wèi)星搜索仿真示意圖Fig.4 Diagrammatic sketch of satellite search simulation

由圖5仿真實驗結(jié)果可得出以下結(jié)論:

(1) 與經(jīng)驗相符,無論任務(wù)區(qū)域內(nèi)障礙物覆蓋網(wǎng)格數(shù)量多少,不采用目標(biāo)運動預(yù)測方法平均每個目標(biāo)發(fā)現(xiàn)次數(shù)最少。這說明在衛(wèi)星搜索動目標(biāo)時進行目標(biāo)運動預(yù)測能有效提高發(fā)現(xiàn)目標(biāo)次數(shù)。

(2) 在任務(wù)區(qū)域障礙物覆蓋網(wǎng)格數(shù)為0時,即平坦海面條件下,本文方法效果接近于常用的基于高斯分布的目標(biāo)運動預(yù)測方法,且明顯高于不采用目標(biāo)運動預(yù)測方法,是可以接受的。隨著環(huán)境中障礙物覆蓋的網(wǎng)格數(shù)量增加,3種策略下平均每個目標(biāo)發(fā)現(xiàn)次數(shù)都在增加。這是因為環(huán)境中障礙物的增加另一方面使目標(biāo)在任務(wù)區(qū)域內(nèi)的活動范圍減小,因此更容易發(fā)現(xiàn)目標(biāo)。但從增長速度上來看,不采用目標(biāo)運動預(yù)測方法和采用基于高斯分布的目標(biāo)運動預(yù)測方法增長速度大致相同,而采用本文方法平均每個目標(biāo)發(fā)現(xiàn)次數(shù)快速增長,說明在衛(wèi)星搜索多障礙物海面上航行的動目標(biāo)問題上,采用本文方法做目標(biāo)運動預(yù)測時衛(wèi)星搜索效果更好。

圖5 不同障礙物規(guī)模下各策略平均每個目標(biāo)發(fā)現(xiàn)次數(shù)Fig.5 Average number of target detection of per strategyunder different obstacle scales

3.2 方法效果分析

為分析搜索效果隨衛(wèi)星過境觀測次數(shù)變化趨勢,在環(huán)境中障礙物覆蓋網(wǎng)格數(shù)為600的情況下,在根據(jù)探測信息進行搜索圖更新的基礎(chǔ)上,針對3種策略重復(fù)100次實驗,計算平均發(fā)現(xiàn)目標(biāo)個數(shù)隨衛(wèi)星過境任務(wù)區(qū)域次數(shù)的變化情況,如圖6所示。

圖6 平均目標(biāo)發(fā)現(xiàn)個數(shù)隨衛(wèi)星過境次數(shù)變化Fig.6 Average number of target detection changes withsatellite transit times

由圖6可知,隨著衛(wèi)星搜索的進行,采用本文方法相比于其他兩種方法平均發(fā)現(xiàn)目標(biāo)個數(shù)最多且增長速度較快。實驗結(jié)果說明面向多障礙物海面條件下衛(wèi)星搜索海上動目標(biāo)時,在目標(biāo)運動預(yù)測過程中采用本文方法能在有限的搜索機會下更多最快地搜索到目標(biāo),使有限的可用衛(wèi)星資源得到充分的利用。

3.3 方法穩(wěn)定性分析

在環(huán)境中障礙物覆蓋600個網(wǎng)格的情形下針對3種策略進行100次仿真實驗,統(tǒng)計各策略下每組實驗發(fā)現(xiàn)目標(biāo)次數(shù),計算并比較各方法下發(fā)現(xiàn)目標(biāo)次數(shù)平均值及方差,如表4所示。

表4 目標(biāo)發(fā)現(xiàn)次數(shù)頻次統(tǒng)計表

由表4統(tǒng)計結(jié)果可知,在衛(wèi)星搜索多障礙物海面動目標(biāo)時本文方法具有更好的穩(wěn)定性。

3.4 方法效率分析

海面動目標(biāo)搜索一般具有較高的時敏性要求,搜索方法需能快速響應(yīng)任務(wù)需求。為分析方法的效率,分別在不同的網(wǎng)格劃分規(guī)模下,根據(jù)探測信息進行搜索圖更新的基礎(chǔ)上,針對3種策略進行實驗。如表5所示記錄了在網(wǎng)格劃分規(guī)模分別為10×10,20×20,30×30,40×40,50×50,60×60下實驗的耗時數(shù)據(jù)。

表5 目標(biāo)運動預(yù)測方法實驗耗時統(tǒng)計

由表5可知,隨著網(wǎng)格劃分規(guī)模的增加,各方法耗時都在增長。當(dāng)不采用目標(biāo)運動預(yù)測方法時,因缺少目標(biāo)運動預(yù)測環(huán)節(jié),實驗耗時最少。但由上述方法可行性及方法效果分析可知,不進行目標(biāo)運動預(yù)測時搜索效果最差。在采用目標(biāo)運動預(yù)測的情況下,本文方法實驗耗時明顯小于采用基于高斯分布的目標(biāo)運動預(yù)測方法,且隨著網(wǎng)格劃分規(guī)模的增加實驗耗時差距更顯著。結(jié)合上述方法效果和方法穩(wěn)定性分析可得出,本文方法綜合性能較優(yōu)。

4 結(jié) 論

本文研究面向多障礙物海面衛(wèi)星搜索動目標(biāo)問題,為更有效地利用有限的衛(wèi)星資源實現(xiàn)更多更快地搜索到海面動目標(biāo),本文使用搜索圖建立多障礙物海面動目標(biāo)搜索環(huán)境模型,并分析了目標(biāo)規(guī)避海面障礙物對其運動的影響,提出一種基于目標(biāo)馬爾可夫運動特征的運動預(yù)測方法,用于計算目標(biāo)轉(zhuǎn)移概率。本文方法在已知搜索圖中目標(biāo)初始概率分布及一步轉(zhuǎn)移概率的條件下可預(yù)測出有限時間和狀態(tài)空間下目標(biāo)運動概率分布,從而為衛(wèi)星搜索提供目標(biāo)環(huán)境信息。仿真實驗結(jié)果驗證了所提出的方法的可行性、有效性及穩(wěn)定性,能較好地解決面向多障礙物海面衛(wèi)星搜索動目標(biāo)問題。