基于深度強化學習的多目標跟蹤技術研究

楊麒霖,劉 俊,管 堅,莫倩倩,陳華杰,谷 雨,石義芳

(杭州電子科技大學 通信信息傳輸與融合技術國防重點學科實驗室,浙江 杭州 310018)

0 引言

多目標跟蹤問題是指由于目標的出現和消失,目標的數量及其軌跡隨時間變化,根據傳感器接收的量測數據聯合估計目標數量及其軌跡的問題[1]。其本質是將量測和目標進行對應匹配,也就是數據關聯問題。當雜波密集并且同時跟蹤多個密集目標時,數據關聯尤為困難。目前,廣泛采用的多目標跟蹤算法包括概率數據關聯(Probability Data Association,PDA)、聯合概率數據關聯[2-3](Joint Probability Data Association,JPDA)濾波器、多假設跟蹤[4](Multiple Hypothesis Tracking,MHT)和隨機有限集[5](Random Finite Set,RFS)等算法。傳統的多目標跟蹤算法如JPDA和MHT側重于數據關聯,但在目標關聯困難時很難有效解決問題,并且會消耗大量計算資源。

因此,基于RFS理論的濾波器應運而生。 Mahler[6]采用有限集統計理論提出了多目標貝葉斯濾波器的一種易于計算的近似方法——概率假設密度濾波器。它通過傳遞多目標后驗密度實現多目標狀態的估計。RFS不再過多關注數據關聯,而是直接尋求多目標狀態的最優和次優估計。RFS理論通過把多目標狀態表示為一個RFS,從而使多目標能夠在單目標貝葉斯估計相同的框架下進行處理[7]。在這一框架下,基于RFS的跟蹤算法能夠處理非常復雜的多目標跟蹤問題。

但是,在RFS理論中多目標的狀態是無法區分的,因此無法輸出不同目標各自的航跡信息。為了解決這一問題,Vo等人[8]提出了標簽RFS的概念,并提出了一種廣義標簽多伯努利(Generalized Labeled Multi-Bernoull,GLMB),它可以為每個目標的狀態添加唯一的標簽。由于GLMB分布是標準多目標似然函數的共軛先驗,因而極大地方便了貝葉斯多目標濾波公式的計算,最終在GLMB分布的基礎上,Vo等人[9]推導出能夠輸出目標航跡的 δ-GLMB濾波器。針對GLMB濾波器計算復雜度高的問題,Reuter等人[10]提出一種與之性能相近的近似實現方法——標簽多伯努利(Labeled Multi-Bernoull,LMB)濾波器。之后,Vo等人[11]和Reuter等人[12]提出了一種將預測和更新結合為一的GLMB和LMB濾波器的有效實現方法,對于每次迭代只需要一個截斷過程,便可以使用標準的分配算法來執行。

傳統的多目標跟蹤中采用的分配算法主要有Murty算法和Gibbs采樣等。Murty算法的最優時間復雜度為O(KN3),最差時間復雜度為O(KN4),其中K為最優分配方案的數量,N為代價矩陣規模。而Gibbs采樣雖然在運行耗時上有較大提升,但是會損失跟蹤精度。特別是在大規模代價矩陣的最優化問題中,算法時間復雜度呈指數上升,將耗費大量的計算資源。

最優分配問題是經典的組合優化(Combinatorial Optimization,CO)問題之一,在CO領域中節約計算成本一直是研究者們致力解決的問題。通常來說,CO問題找到一個最優解需要消耗大量的時間成本。許多用于解決CO問題的傳統算法是由領域專家設計的使用手工構建的啟發式算法,這些啟發式算法順序地構造該類問題的解決方案,但是由于問題的復雜性,它通常不是最優的,并可能會耗費大量計算時間。近年來,隨著機器學習領域的發展,人們發現將強化學習和其他技術應用于CO是可行而又有效的,因此,CO領域開始傾向于采用強化學習來解決問題[13-15]。

針對上述算法中存在的計算量大、運行時間長等問題,本文采用LMB濾波算法,結合利用CO領域中的深度強化學習技術,建立如圖1所示的多目標跟蹤算法模型。在盡量保證跟蹤性能的情況下降低多目標跟蹤算法計算負擔,提升跟蹤速度,以增強跟蹤系統的實效性。

圖1 系統結構模型Fig.1 System model diagram

1 LMB濾波器

1.1 標簽隨機有限集建模

(1)

鑒于RFS理論不能為多目標估計提供航跡信息,在標簽RFS中引入了標簽空間L的概念。

p0：k(X0：k|Z0：k)∝gk(Zk|Xk)fk|k-1(Xk|Xk-1)·

p0：k-1(X0：k-1|Z0：k-1)。

(2)

結合貝葉斯濾波框架,在標簽RFS理論中,多目標狀態預測和更新公式分別為：

1.2 濾波預測與更新

在標簽RFS的基礎上,Vo等人[8]提出了GLMB濾波,該濾波是一種滿足共軛先驗的貝葉斯濾波,即從當前時刻開始,如果多目標濾波預測密度滿足GLMB的形式,則下一時刻的多目標密度也是GLMB形式。而LMB分布是GLMB分布的一種特殊近似。因此,LMB濾波器可通過貝葉斯預測和更新方程隨時間向前遞歸傳遞LMB濾波密度。則LMB多目標預測密度為：

πk|k-1(X|Zk-1)=Δ(X)·

(5)

(6)

(7)

式中：i≤R表示存活目標i和量測j之間的關聯概率,R+1≤i≤P表示新生目標和量測之間的關聯概率,量測下標j的取值為[-1,M],其中j=0表示目標漏檢概率,j=-1表示目標消亡或者未出生的概率。

由于目標狀態和量測之間存在非常多的可能性,計算所有的狀態與量測的組合是極其困難的也是不現實的,并且大部分可能性都需要被截斷。通常采用的方法是求解以下最優化問題：

(8)

式中：S為分配矩陣,C為代價矩陣。將C中每個元素定義為：

(9)

代價矩陣C=[C1C2C3]由三個塊組成：目標的漏檢矩陣C1、消亡矩陣C2以及目標與量測的關聯矩陣C3。表示漏檢的C1矩陣是P×P對角矩陣,其中元素Ci,j為目標i漏檢的可能性權值,所有非對角元素設置為零,C2矩陣對角線元素表示第i個目標消失或未出生的權重,其余非對角元素也置零;C3為P×M關聯矩陣,其中每個元素表示對應目標到量測的關聯權重。

2 基于深度強化學習的二分圖匹配

2.1 問題定義

將要進行最優化分配算法的代價矩陣C定義為一個二分圖G=(U,V,E),其中,U為含有P個元素的目標X集合,V為含有(2P+M)個元素的目標不同狀態的集合,E為連接兩側節點的帶權邊的集合。

帶權二分圖如圖2所示,圖中左右側分別為 二分圖的U和V節點集合,兩側節點以不同權值的邊相連接,有邊相連的節點被稱為鄰居。其中,節點in1和in2分別表示目標xn的漏檢和消亡狀態(例如n在圖2中的取值為1和2),i3、i4分別表示兩個量測目標,連接兩側節點的邊的權值為代價矩陣C中的非零元素。至此,代價矩陣的最優化任務轉化為二分圖的最大權重匹配任務。

圖2 帶權二分圖Fig.2 Weighted bipartite graph

2.2 強化學習與馬爾可夫決策過程

強化學習是機器學習領域中的一種方法,強化學習討論的問題如圖3所示,圖為在復雜不確定的環境中,智能體通過感知所處的狀態s依據策略π采取不同的動作a與環境進行交互,從而獲得最大的獎勵r。

圖3 強化學習Fig.3 Reinforcement learning

為了將強化學習應用于CO中,二分圖匹配問題需要被建模為一個順序決策過程,其中智能體通過執行一系列動作來與環境交互,以找到解決方案。馬爾可夫決策過程為建模這類問題提供了廣泛使用的數學框架。因此,將二分圖匹配問題建模為一個馬爾可夫決策過程。

狀態空間S：空間S內的狀態s是一組已選定的匹配和當前的部分二分圖。當二分圖的最后一個節點到達時s達到最終狀態。

動作空間A：每個時間步長t時,節點vt及其邊會一起到達。智能體可以選擇將vt與其在U中的鄰居進行匹配,也可以選擇不匹配。因此,在時間t時,A中能采取的動作數量為|Ngbr(vt)|+1,其中Ngbr(vt)是節點vt的在U中的鄰居節點集合。

獎勵函數R：獎勵r=R(s,a)定義為當前狀態s下智能體采用動作a選擇的邊的權重。最終狀態下的獎勵r為二分圖最終匹配方案的總權重。

狀態轉移：如果當前時間的節點vt被匹配給U中的節點,那么狀態將會相應更新。無論當前節點是否匹配,都將進入下一狀態并且下一節點與之前的動作無關。

2.3 深度學習架構

采用前饋神經網絡作為強化學習的策略網絡,當節點vt到達時,策略網絡的輸入5個特征向量的級聯(w,m,ht,gt,nt)。特征向量w和m的級聯為：(w0,…,wu,…,w|U|,m0,…,mu,…,m|U|)∈2(|U|+1),wu為當前節點vt與節點u的邊的權重,mu表示該節點是否可以進行匹配的二進制標識。特征向量h,g,n包含一系列節點的歷史特征。網絡的輸出是大小為|U|+1的概率向量。

2.4 算法訓練

網絡訓練使用標準的REINFORCE算法[16]：

?J(θ|s)=Epθ(π|s)·

[((G(π|s)-b(s))?lnpθ(π|s)]。

(10)

為了減小梯度的方差,在訓練迭代中添加了基線函數b(s),訓練中基線函數b(s)初始化為匹配方案的獎勵G(π|s)并以式(11)更新：

b′(s)=βb(s)+(1-β)G(π|s)。

(11)

2.5 模型輸出

訓練好的深度強化學習網絡將輸出代價矩陣的一個最優解S1。為了輸出代價矩陣的k個次優解,在二分圖G中將S1中的每個目標關聯的邊E(i,j)以及節點i和j的邊刪除,生成圖G1;再將圖G1作為模型的輸入,輸出次優解S2;以此類推即可輸出k個次優解Si。

將多個次優解的集合矩陣S作為分配矩陣,向前傳遞多伯努利后驗密度,完成一次完整的濾波更新。

3 實驗結果與分析

為了驗證本文算法的性能,設計了非線性條件下目標數較多的復雜場景下的仿真實驗場景,包含了多目標軌跡交叉、平行等多目標運動狀態。

設傳感器位于坐標原點,傳感器可獲取目標和雜波共同生成的位置量測。傳感器可檢測區域為 [-2 000,2 000] m×[0,2 000] m的矩形區域,采樣間隔為1 s?？傆^測時長100 s,在觀測時間內一共有 15個真實目標出現,各目標運動軌跡如圖4所示。

圖4 目標真實軌跡Fig.4 Real tracks of targets

各目標初始狀態及其起始、終止時間如表1所示,其中初始狀態向量表示目標的x方向的坐標和速度、y方向的坐標和速度以及目標運動的角速度。雜波數量服從λ=10的泊松分布并在傳感器監視區域內服從均勻分布。

表1 各目標運動狀態

進行100次蒙特卡洛實驗,對不同濾波器的跟蹤過程的OSPA(2)誤差[17-18]和運行時間進行統計。實驗結果將本文算法記為LMB-DRL,基于兩種不同分配算法的LMB濾波器記為LMB-Murty和LMB-Gibbs,除此之外還與GLMB濾波算法進行實驗對比。各濾波器的運行時間和平均OSPA(2)如圖5所示。

圖5 平均OSPA(2)誤差對比Fig.5 Comparison of average OSPA(2)

從圖5和表2可以看出,LMB濾波器對新生目標不夠敏感,在新目標出現時各LMB濾波器都會有較大誤差,而GLMB濾波器在跟蹤新生目標時的誤差較小;LMB-Murty濾波器取得了最好的OSPA(2)性能,但是運行時間也是最長的;LMB-DRL在保證了跟蹤性能的情況下,降低了運算成本,提升了跟蹤的實時性,體現了本文算法的可行性。

表2 各濾波器運行時間和平均OSPA(2)對比

4 結論

提出了一種與深度強化學習結合的多目標跟蹤濾波算法,在保證跟蹤性能的前提下大大減少了跟蹤過程的計算成本,特別是目標數量較多的跟蹤場景中效果會更顯著。但是由于濾波算法的分配環節的計算復雜度與深度強化的網絡結構有關,因此即使是較為簡單的場景也需要一定的計算復雜度。未來展望是設計一種自主學習的強化學習方法,在低復雜度的情況下使用啟發式算法并訓練學習匹配特征,高復雜度情況下自動決策進行最佳匹配。