采用馬氏決策過程和后驗克拉美羅下界的多被動式移動傳感器長期調(diào)度方法

徐公國,單甘霖,段修生

(1.陸軍工程大學(xué)電子與光學(xué)工程系,050003,石家莊;2.石家莊鐵道大學(xué)機(jī)械工程學(xué)院,050003,石家莊)

現(xiàn)代化網(wǎng)絡(luò)戰(zhàn)爭中,傳感器的種類與功能日趨多樣化、復(fù)雜化。隨著傳感器載體機(jī)動性能的增強,可移動傳感器的應(yīng)用范圍也越來越廣泛,并逐漸成為傳感器管理研究中的一個重要分支[1]。面向目標(biāo)跟蹤任務(wù)需求,通過對可移動傳感器的合理調(diào)度(又稱傳感器控制),能夠有效擴(kuò)展傳感器系統(tǒng)的時空感知范圍,提高目標(biāo)的空間分辨率,還有助于提高系統(tǒng)的戰(zhàn)場生存能力。

從任務(wù)目標(biāo)出發(fā),常見的傳感器管理方法有基于協(xié)方差[2]、基于信息論[3]以及基于克拉美羅下界[4](CRLB)等方法。近年來,隨著管理安全任務(wù)需求的增加,基于風(fēng)險控制[5-7]的傳感器管理方法逐漸成為新的研究熱點。例如:文獻(xiàn)[5]對主動傳感器的輻射風(fēng)險進(jìn)行控制研究;文獻(xiàn)[6-7]重點分析了傳感器管理中的操作損失風(fēng)險。從求解建模方法出發(fā),主要的傳感器管理方法有基于規(guī)劃論[8]、基于智能優(yōu)化[9]以及基于馬爾科夫決策過程(MDP)[7,10]等方法。此外,博弈論[11]、市場拍賣[12]和多維協(xié)商機(jī)制[13]也在傳感器管理研究中有所應(yīng)用。但是,已有文獻(xiàn)多針對靜態(tài)傳感器進(jìn)行研究,針對移動傳感器管理調(diào)度的研究相對比較少。

現(xiàn)有的移動傳感器管理研究可分為兩方面:一是單個傳感器移動軌跡規(guī)劃[14-18],重在獲取更高的目標(biāo)跟蹤收益;二是多移動傳感器網(wǎng)絡(luò)的控制[19-21],重在研究傳感器之間的拓?fù)浣Y(jié)構(gòu)和協(xié)同方法。例如,文獻(xiàn)[14-17]針對單個移動傳感器利用隨機(jī)集多目標(biāo)濾波理論進(jìn)行研究,使用目標(biāo)狀態(tài)先驗和后驗分布之間的信息散度作為傳感器移動的獎勵函數(shù),實現(xiàn)了移動傳感器的有效調(diào)度;文獻(xiàn)[18]提出了一種目標(biāo)導(dǎo)向的多伯努利濾波方法,并基于Bhattacharyya距離實現(xiàn)了傳感器的移動控制;針對多移動傳感器,文獻(xiàn)[19]利用目標(biāo)狀態(tài)的一步預(yù)測收益對多測距傳感器的調(diào)度問題進(jìn)行研究,并基于Gauss-seidel和線性規(guī)劃松弛算法進(jìn)行求解,得出了傳感器的近似優(yōu)化軌跡,但運算復(fù)雜度較高;文獻(xiàn)[20]利用蜂擁控制策略對移動傳感器網(wǎng)絡(luò)的拓?fù)溥B通性進(jìn)行研究,在保證目標(biāo)跟蹤精度的同時,有效降低了網(wǎng)絡(luò)能耗;文獻(xiàn)[21]利用分布式控制方法對大規(guī)模移動傳感器網(wǎng)絡(luò)的控制問題進(jìn)行了初步分析。

但是,上述傳感器管理方法多以當(dāng)前最小代價或最優(yōu)收益為調(diào)度目標(biāo),沒有考慮當(dāng)前傳感器調(diào)度動作帶來的長期影響,且求解方法的計算復(fù)雜度較高,難以滿足任務(wù)決策的實時性需求。因此,本文針對上述問題,面向機(jī)動目標(biāo)跟蹤任務(wù),提出了一種基于部分可觀馬爾科夫決策過程(POMDP)和后驗克拉美羅下界(PCRLB)的多被動式移動傳感器長期調(diào)度方法。該方法具有一定遠(yuǎn)視性,使得生成的決策調(diào)度方案更具合理性。同時,為快速獲取傳感器調(diào)度方案,給出了一種基于分支定界技術(shù)的改進(jìn)決策樹搜索算法。最后的仿真實驗結(jié)果表明了所提傳感器調(diào)度方法與改進(jìn)決策樹優(yōu)化求解算法的有效性和先進(jìn)性。

1 問題描述

與主動式傳感器不同,被動式傳感器的良好隱身性使其在偵察、監(jiān)視、跟蹤等任務(wù)中更具優(yōu)勢。例如,在偵察作戰(zhàn)過程中,紅外、電視傳感器都得到了廣泛應(yīng)用。本文對僅有角度量測的多被動式移動傳感器的長期調(diào)度問題進(jìn)行研究,旨在尋求多被動式移動傳感器的最佳協(xié)同機(jī)動方案,從而獲得更好的目標(biāo)跟蹤收益。

(a)場景1

(b)場景2圖1 多被動傳感器協(xié)同機(jī)動示意圖

由于被動傳感器量測的不完整性,多個被動傳感器協(xié)同工作才能獲得良好的目標(biāo)定位信息。圖1給出了多被動傳感器協(xié)同機(jī)動示意圖,考慮兩個被動傳感器,圖1中實線協(xié)方差橢圓表示目標(biāo)位置的先驗不確定性,虛線協(xié)方差橢圓表示目標(biāo)位置的后驗不確定性。場景1中兩個傳感器的量測在X方向上提供的信息都非常有限,目標(biāo)的后驗不確定性只是略有減少。而場景2中,由于傳感器量測在X和Y方向上都提供了較多的量測信息,故目標(biāo)的后驗不確定性大幅減少。可見被動傳感器之間的相對位置關(guān)系對目標(biāo)狀態(tài)估計的準(zhǔn)確度具有較大影響。

當(dāng)目標(biāo)發(fā)生機(jī)動時,如何提前調(diào)度多個被動傳感器到達(dá)理想位置,并實現(xiàn)對目標(biāo)的協(xié)同跟蹤處理就顯得尤為重要。

2 基于POMDP的傳感器調(diào)度模型

傳感器可看作是一個智能體,由于目標(biāo)狀態(tài)的不可觀測性,故基于POMDP理論框架構(gòu)建傳感器調(diào)度模型并進(jìn)行求解,具體的數(shù)學(xué)描述如下。

2.1 調(diào)度動作

假定在偵察網(wǎng)絡(luò)中有M個被動式傳感器資源,且均被放置在可移動載體(例如車載、機(jī)載等)上,并能夠以一定的速度進(jìn)行機(jī)動。定義調(diào)度動作Ak表示在k時刻的所有傳感器的聯(lián)合調(diào)度動作,Ak=[a1,k,a2,k,…,aM,k]。其中,傳感器m的調(diào)度動作為am,k=[rm,k,φm,k],1≤m≤M;rm,k表示傳感器m的機(jī)動距離;φm,k表示傳感器m的機(jī)動方向。

考慮實際情況,由于傳感器運動能力的限制,調(diào)度動作要滿足一定的約束條件。圖2給出了傳感器單步機(jī)動方式,假設(shè)傳感器運動速度保持不變,則有rm,k=vmδt,vm表示傳感器m的速度,δt表示運動時間。同時,由于運動慣性的存在,機(jī)動方向只能在一定范圍內(nèi)取值,即φm,min≤φm,k≤φm,max,且有φm,min=-φm,max。

圖2 傳感器單步機(jī)動方式

2.2 系統(tǒng)狀態(tài)及狀態(tài)轉(zhuǎn)移律

(1)

此外,由于目標(biāo)狀態(tài)無法直接觀測,考慮到容積卡爾曼濾波(CKF)算法在處理非線性系統(tǒng)上的優(yōu)越性,采樣CKF算法進(jìn)行目標(biāo)狀態(tài)估計,面向機(jī)動目標(biāo)并結(jié)合交互多模型(IMM)算法進(jìn)行濾波。以3個運動模型為例,本文目標(biāo)狀態(tài)估計的流程如圖3所示。由于篇幅限制,CKF和IMM算法的具體步驟可參見文獻(xiàn)[22-23]。

圖3 目標(biāo)狀態(tài)估計流程示意圖

2.3 系統(tǒng)觀測及觀測律

(2)

(3)

進(jìn)而,系統(tǒng)的狀態(tài)觀測律可表示為

(4)

式中:h(·)表示非線性量測方程;vk為零均值、協(xié)方差為Rk的高斯白噪聲。

2.4 單步調(diào)度與長期調(diào)度代價

傳感器長期調(diào)度的核心是依據(jù)對系統(tǒng)未來狀態(tài)的預(yù)測,傳感器事先進(jìn)行機(jī)動,從而減少目標(biāo)狀態(tài)的不確定性,提高目標(biāo)跟蹤的精度。PCRLB給出了目標(biāo)狀態(tài)估計誤差的理論下界,可用于對移動傳感器的長期調(diào)度控制[24-27]。由文獻(xiàn)[27]可知,PCRLB為Fisher信息矩陣的逆,定義J(Sk)為Fisher信息矩陣,J(Sk)滿足以下遞推公式

(5)

其中

(6)

式中:Hk+1為非線性量測方程h(·)的雅可比矩陣。由于PCRLB的對角元素表示目標(biāo)在各狀態(tài)分量上的誤差下界,因此利用PCRLB的跡來構(gòu)建調(diào)度代價函數(shù)。誤差下界應(yīng)該越小越好,故代價函數(shù)為最小化函數(shù)。

定義f(Sk,Ak,…,Ak+nk,nk)為在系列調(diào)度動作[Ak,…,Ak+nk]下的代價函數(shù),nk為決策步長,即決策時預(yù)測分析的步數(shù)。當(dāng)nk=1時,即為短期調(diào)度(又叫非遠(yuǎn)視調(diào)度),此時單步代價函數(shù)為

f(Sk,Ak,1)=tr[J(Sk+1,Ak)-1]

(7)

當(dāng)進(jìn)行長期調(diào)度(預(yù)測多步)時,即nk>1時,傳感器調(diào)度動作的選擇不僅要考慮調(diào)度動作的即時代價,還應(yīng)考慮該調(diào)度動作對系統(tǒng)未來狀態(tài)的影響,以及所帶來的未來代價,因此對傳感器進(jìn)行長期調(diào)度時,其代價函數(shù)為

f(Sk,Ak,…,Ak+nk,nk)=tr[J(Sk+1,Ak)-1]+

(8)

式中:α為折扣系數(shù),表示對未來期望代價的重視程度;τ為計數(shù)變量。

(9)

(10)

3 基于無跡采樣的長期代價計算

由式(8)可見,未來期望代價是計算長期調(diào)度代價的基礎(chǔ),但由于當(dāng)前時刻無法準(zhǔn)確預(yù)知未來系統(tǒng)狀態(tài),這就需要足夠的樣本來估算未來期望代價。傳統(tǒng)的方法常借助于蒙特卡洛采樣來求取累積代價均值,以達(dá)到近似求取未來期望代價的目的。需要注意的是,無論決策步長nk和目標(biāo)數(shù)如何取值,蒙特卡洛采樣都需要收集大量的隨機(jī)樣本,這會帶來很大的計算負(fù)擔(dān)。

為減少計算負(fù)擔(dān),給出了一種基于無跡采樣的長期代價近似計算方法,該方法能夠根據(jù)具體的目標(biāo)跟蹤場景生成一定數(shù)量的確定性樣本,尤其在目標(biāo)數(shù)量較小的場景中,可大大減少計算復(fù)雜度,具體步驟如下。

(11)

(12)

在獲取到Sigma點后,按照下式

(13)

(14)

(15)

f(Xk,Ak,…,Ak+nk,nk)=tr[J(Xk+1,Ak)-1]+

(16)

4 問題優(yōu)化求解

4.1 問題決策樹構(gòu)建

為加快決策速度并滿足在線調(diào)度的實時性需求,本節(jié)對傳感器機(jī)動方向進(jìn)行離散化,并給出了一種基于分支定界技術(shù)的改進(jìn)決策樹快速優(yōu)化搜索求解方法。該方法能夠避免復(fù)雜的數(shù)學(xué)運算,可以在較短時間內(nèi)獲得問題的近似最優(yōu)解,如圖4所示。

圖4 機(jī)動方向離散化

(17)

圖5 調(diào)度問題決策樹示意圖

4.2 基于分支定界的改進(jìn)UCS搜索算法

常用的決策樹搜索算法有寬度優(yōu)先搜索(BFS)、深度優(yōu)先搜索(DFS)和標(biāo)準(zhǔn)代價搜索(UCS)[28]算法。以圖6中的決策樹為例,圈外數(shù)字代表代價函數(shù)值,圈內(nèi)數(shù)字代表決策樹分支的搜索順序。UCS算法優(yōu)先打開最優(yōu)(即代價函數(shù)最小)分支,當(dāng)搜索到2節(jié)點時,已到達(dá)最低層,故此時的最小代價值為4。由于節(jié)點3的代價值已經(jīng)大于當(dāng)前最小代價值,故節(jié)點5和6就不需要再打開計算,直接刪除即可。

圖6 UCS搜索算法示意圖

由此可見,如果能盡早確定更小的最小代價值,可增加刪除分支的數(shù)量,加快決策樹的搜索速度。因此,引入分支定界技術(shù),通過估計節(jié)點的下界來及時刪除下界大于當(dāng)前最優(yōu)收益的分支,同時可優(yōu)先展開具有更小下界的節(jié)點,從而盡早獲取更小的最小代價值。由式(16)可見,精確最優(yōu)下界的獲取難度較大,若通過精確求解的方式獲取最優(yōu)下界會額外增加搜索和存儲空間,無法達(dá)到加快搜索的目的。因此,為減少問題的計算復(fù)雜度,給出一種下界值的近似估計方法。

通過實驗發(fā)現(xiàn),在同一跟蹤任務(wù)下,由于傳感器工作性能的穩(wěn)定性以及目標(biāo)跟蹤的連續(xù)性,單步跟蹤代價不會發(fā)生較大變化。因此,當(dāng)決策步長為nk時,第k+nl層節(jié)點的下界為

Lf(Xk,Ak,…,Ak+nl,nk)=f(Xk,Ak,…,Ak+nl,nl)+

(18)

輸入決策步長nk、系統(tǒng)狀態(tài)Sk及其協(xié)方差

輸出傳感器調(diào)度動作序列Ak,…,Ak+nk

步驟1初始化決策樹的根節(jié)點,并初始化最小代價值fmin和折扣系數(shù)α。

步驟2展開當(dāng)前節(jié)點的所有子節(jié)點,并計算子節(jié)點的代價值。如果當(dāng)前節(jié)點深度為nk且節(jié)點的代價值小于fmin,則令fmin為該節(jié)點的代價值;否則,將該節(jié)點存入列表中,并按照代價值進(jìn)行升序排序。計算打開節(jié)點的下界值,如果節(jié)點的下界值大于fmin,則剔除該節(jié)點,不再展開。循環(huán)處理決策樹列表中的節(jié)點,直至決策樹列表為空。

步驟3重復(fù)運行步驟2,直至達(dá)到?jīng)Q策步長nk。

步驟4輸出最小代價值fmin對應(yīng)的分支路徑,即為傳感器最優(yōu)調(diào)度動作序列。

5 仿真實驗

為驗證所提多被動式移動傳感器長期調(diào)度方法的有效性和先進(jìn)性,在以下多種場景下進(jìn)行仿真實驗,并與已有同類方法進(jìn)行對比分析。

5.1 所提方法與同類調(diào)度方法的對比實驗

實驗參數(shù)設(shè)置如下。偵察任務(wù)區(qū)域內(nèi)有1個機(jī)動目標(biāo),目標(biāo)初始位置為(200,580) m,目標(biāo)在X、Y方向上的初始速度分別為20、0.5 m/s,采樣時間為60 s,采樣間隔δt為1 s。目標(biāo)在15～25 s做左轉(zhuǎn)彎運動(轉(zhuǎn)彎速率為1 rad/s),40～50 s做右轉(zhuǎn)彎運動(轉(zhuǎn)彎速率為1 rad/s),其余時間做勻速直線運動,目標(biāo)可能的運動模型如下式

(19)

模型的初始分布概率為0.33、0.34、0.33,各模型之間的轉(zhuǎn)移概率矩陣為

(20)

傳感器為兩個被動測角傳感器,初始位置均為(100,500) m,采樣間隔內(nèi)最大機(jī)動距離為20 m,可機(jī)動方向為前進(jìn)方向的±45°。根據(jù)離散化模型,將傳感器可機(jī)動方向細(xì)分為5種,即分別為{45°,22.5°,0°,-22.5°,-45°}。兩個傳感器的量測性能一致,量測誤差分別為0.052、0.052。折扣系數(shù)α=1,即將未來代價與即時代價設(shè)置成同等重要。

此外,為更好地分析本文所提長期調(diào)度方法的性能,同時采用固定速度調(diào)度方法、文獻(xiàn)[7]中基于協(xié)方差控制的一步預(yù)測短期調(diào)度方法以及文獻(xiàn)[10]中基于PCRLB的一步預(yù)測短期調(diào)度方法進(jìn)行對比實驗。其中,固定速度調(diào)度方法中傳感器1在X、Y方向上的運動速度分別為14、4 m/s,傳感器2在X、Y方向上的運動速度分別為20、1 m/s,實驗結(jié)果如圖7～圖10所示。

圖7 不同調(diào)度方法下目標(biāo)估計位置的RMSE

圖7給出了不同調(diào)度方法下目標(biāo)估計位置的均方根誤差(RMSE,設(shè)為RMSE)。由圖7可以看出,在一定的決策步長范圍內(nèi),與固定速度調(diào)度方法[7]和短期調(diào)度方法[20]相比,本文所提長期調(diào)度方法的目標(biāo)估計位置的RMSE更小,即目標(biāo)跟蹤誤差更小,且隨著決策步長的增加,目標(biāo)的跟蹤精度整體向好的趨勢發(fā)展。

圖8～10分別為固定速度調(diào)度方法、基于PCRLB的短期調(diào)度方法和長期調(diào)度(nk=3)方法下的目標(biāo)運動軌跡和傳感器運動軌跡示意圖。圖8～10中橢圓為目標(biāo)估計位置的誤差協(xié)方差橢圓。由圖10可見,所提移動傳感器長期調(diào)度方法能夠有效控制傳感器向合理方向移動,并使多傳感器之間保持有效的協(xié)同機(jī)制。與其他兩種調(diào)度方法相比,本文所提方法的目標(biāo)跟蹤誤差協(xié)方差橢圓最小,傳感器運動軌跡也更加平滑,進(jìn)一步驗證了所提移動傳感器長期調(diào)度方法的優(yōu)越性。

圖8 固定速度調(diào)度方法下傳感器運動軌跡

圖9 短期調(diào)度方法(PCRLB)下傳感器運動軌跡

圖10 長期調(diào)度方法(nk=3)下傳感器運動軌跡

注:方法1:固定速度調(diào)度方法;方法2:文獻(xiàn)[7]方法;方法3:文獻(xiàn)[11]方法;方法4:長期調(diào)度方法(nk=2);方法5:長期調(diào)度方法(nk=3);方法6:長期調(diào)度方法(nk=4);方法7:長期調(diào)度方法(nk=5);方法8:長期調(diào)度方法(nk=6)圖11 不同調(diào)度方法下目標(biāo)估計位置的

表1給出了不同調(diào)度方法的單次決策平均運行時間,仿真運行環(huán)境為Matlab2014a,計算機(jī)內(nèi)存為8 GB,CPU為Core.i7。由實驗結(jié)果可以看出,與短期調(diào)度方法相比,長期調(diào)度方法雖然在運算時間上有所增加,但當(dāng)決策步長nk在一定范圍內(nèi),長期調(diào)度方法同樣能夠滿足實時性要求。隨著nk增加,長期調(diào)度方法中的單次決策時間會逐漸增加,直至超過采樣時間,因此當(dāng)使用長期調(diào)度方法時,nk的選擇不宜過大。

表1 不同調(diào)度方法的單次決策平均運行時間對比

為驗證所提基于分支定界的改進(jìn)UCS決策樹優(yōu)化搜索算法的有效性,在不同決策步長下,與窮舉算法和UCS算法進(jìn)行了對比實驗,決策樹展開節(jié)點數(shù)如圖12所示。所提改進(jìn)UCS算法相較于其他兩種算法,展開的節(jié)點數(shù)更少,優(yōu)化速度也更快。決策步長越長,展開的節(jié)點數(shù)越多,故能節(jié)省更多的系統(tǒng)存儲空間,可有效減小系統(tǒng)負(fù)擔(dān)。

圖12 決策樹展開節(jié)點數(shù)隨決策步長的變化

5.2 本文方法對不同目標(biāo)航跡的跟蹤實驗

為驗證本文移動傳感器長期調(diào)度方法對不同目標(biāo)航跡的適用性,采用不同目標(biāo)航跡進(jìn)行實驗。令場景1中的目標(biāo)航跡為航跡1,圖13和圖14中的目標(biāo)航跡為航跡2和航跡3。其中,航跡2的目標(biāo)初始位置為(200,730) m,在X、Y方向上的初始速度分別為20、0 m/s;航跡3的目標(biāo)初始位置為(200,730) m,在X、Y方向上的初始速度分別為18、-5 m/s。目標(biāo)運動噪聲與傳感器性能參數(shù)保持不變。蒙特卡羅實驗次數(shù)為100,nk分別取值2、3、4,實驗結(jié)果見表2。

圖13 航跡2跟蹤效果圖

圖14 航跡3跟蹤效果圖

表2 不同航跡下目標(biāo)估計位置的

5.3 本文方法在3種傳感器場景下的跟蹤實驗

實驗參數(shù)設(shè)置如下。偵察任務(wù)區(qū)域內(nèi)有1個機(jī)動目標(biāo),目標(biāo)運動參數(shù)與5.1節(jié)保持一致。傳感器數(shù)為3,傳感器工作性能有所差異。實驗1時,3個傳感器的量測誤差分別為0.062、0.042、0.022;實驗2時,3個傳感器的量測誤差分別為0.022、0.042、0.062。利用長期調(diào)度方法(nk=3)對移動傳感器進(jìn)行協(xié)同控制,實驗結(jié)果如圖15、16所示。

圖15 實驗1傳感器運動軌跡

圖16 實驗2傳感器運動軌跡

同時可以發(fā)現(xiàn),性能較差的傳感器會自動組成一組,構(gòu)成性能更好的“傳感器”,并與另一傳感器進(jìn)行協(xié)同跟蹤。通過分析,原因是當(dāng)兩個性能較好的“傳感器”對目標(biāo)進(jìn)行協(xié)同跟蹤時,會使傳感器系統(tǒng)在各方向上的量測信息都比較準(zhǔn)確,目標(biāo)跟蹤誤差也更小。

6 結(jié) 論

本文面向機(jī)動目標(biāo)跟蹤需求,對多被動式移動傳感器的調(diào)度問題進(jìn)行研究,提出了一種基于多步預(yù)測的移動傳感器長期調(diào)度方法。該方法不僅考慮傳感器調(diào)度動作所引起的即時代價,還兼顧其對系統(tǒng)未來跟蹤代價的影響。實驗結(jié)果表明,與固定和短期調(diào)度方法相比,長期調(diào)度方法能夠有效提高目標(biāo)的跟蹤精度。此外,本文給出了一種改進(jìn)的決策樹快速優(yōu)化搜索算法,對解決相關(guān)決策問題有一定的借鑒意義。未來的研究工作將進(jìn)一步貼近實際戰(zhàn)場環(huán)境,對雜波環(huán)境下的多機(jī)動目標(biāo)跟蹤問題進(jìn)行研究。