基于LAP的MHT算法在多目標跟蹤中的應用

仵浩，呂文平

(1. 空軍工程大學 防空反導學院，陜西 西安 710051；2. 中國人民解放軍94907部隊，江西 南昌 330000)

0 引言

彈道導彈具有射程遠、威力大、精度高等優良的戰術性能，在現代戰爭中兼具實戰打擊能力和戰略威懾效應。因此，發展導彈防御能力成為軍事強國競相追逐的、制衡彼此的目標。目標跟蹤作為彈道導彈防御作戰閉合環路的關鍵環節，其優劣程度直接影響整個防御行動的可行性和有效性。考慮到當前飽和攻擊及多彈頭突防仍是彈道導彈防御面臨的現實威脅，本文從彈道導彈防御中的多目標跟蹤問題出發，著重解決其中的數據關聯問題[1]。對此，相關文獻已做了很多有價值研究和探索，如(按復雜度的降序排列)多假設跟蹤(MHT)、多維(SD)分配、聯合概率數據互聯(JPDA)以及兩維(2D)分配(單掃描處理)算法等[2-9]。雖然，MHT的復雜度較高，但它對其他算法卻有非常好的兼容性和一致性[10-11]。本文考慮彈道導彈防御作戰的緊時性要求，嘗試基于采用線性分配方法(linear assignment programming，LAP)對MHT關聯假設進行簡化，以降低其復雜性進而滿足導彈防御作戰需求。

1 MHT關聯假設構建及概率計算

在彈道導彈防御多目標跟蹤中，為了實現測量值與目標之間的關聯匹配，MHT算法跟蹤過程中需要依據測量值和目標構建多個假設的匹配對，并計算所有匹配假設的概率，進而依據概率確認并選擇最優匹配假設，從而完成測量值與目標之間的關聯。

假設：

(1) 傳感器探測過程中，每個目標至多有1個測量值；

(2) 每個測量值都只與1個目標相關；

(3) 傳感器測量數據每一步中都得到更新；

(4) 彈道導彈目標未采取任何EA(electronic attacts)技術。

則MHT算法的基本過程如下[12]：

Zk=zk,m,m=1,2,…,mk.

(1)

測量值在雷達垂直坐標系中定義，zk,m可表示為目標在特定坐標系中的位置測量值ξ,γ，ζ的形式，即

zk,m=ξk,m,γk,m,ζk,m.

(2)

(3)

式中：ψh=ψmjh,m=1,2,…,mk；ψmjh表示在每個關聯假設ψh中第m個測量值屬于(來自于)第j個目標，下標g為全局指針，h為關聯假設指針。運用貝葉斯定律，式(3)可寫為

(4)

令PΩk=C，即為常量，則有

(5)

進一步可寫成

(6)

由于每個關聯假設ψh中的事件組ψmjh之間相互獨立，則進一步可得

(7)

(8)

可得

(9)

(10)

依據文獻[15-16]，差分為

(11)

(12)

式中：Pj,kk-1為更新后的估計協方差；Rk為噪聲協方差；HΓ,k,j為觀測矩陣。

表1所示為測量值-目標關聯中關聯概率矩陣β·的一個實例，共有5個目標J=5，7個測量值M=7。

2 基于LAP的可行假設構建及最佳關聯選擇

最佳關聯的確定依據每個關聯假設的概率進行選擇，在傳統MHT算法中，需要計算所有假設的概率(遍歷所有假設)，然后才能選擇出其中概率最大的假設作為最終的關聯。這導致隨著目標數目的增加，采用上述遍歷計算方法時會導致計算量組合爆炸，難以實時應用。

為了應對上述問題，可以采取多假設篩選技術[17]進行處理：即在每次獲得新的測量值需要進行數據關聯的時候，在所有的關聯假設中預選擇N個可行假設，然后分別計算這N個假設的概率并從中選出最佳假設實現測量值與目標之間的關聯。這種思想的優勢在于：每次測量值-目標之間關聯的過程中，將需要計算的假設限定在N個，只需對它們的概率進行計算，從而可大大減小每步跟蹤過程中的計算量，便于計算機實現。

然而，如何從大量關聯假設中預選出這N個可行假設則對MHT算法的有效性非常關鍵。考慮到每一步跟蹤過程中可以得到測量值-目標之間的關聯概率矩陣β·，因此，可以考慮采用線性分配方法LAP對β·進行處理，從而構造出N個可行假設。即從β·中的概率大小出發，優先選擇那些概率較大的匹配對，據此再構建假設，這樣便可以保證構建的假設是所有可能假設中概率最大的N個。

基于上述考慮，建立基于LAP的MHT假設構建方法如下：

(1) 生成關聯概率矩陣PA

依據式(10)～(12)計算β·中每個測量值-目標匹配對的概率Pm,j，構建關聯概率矩陣

(13)

(2) 對關聯概率矩陣PA中的元素進行編號

編號方法為在關聯概率矩陣PA中從左至右、先行后列(左至右、上至下)依次進行。每個編號代表測量值和目標之間的一個匹配對，且每個編號對應一個概率，構建的假設的概率將依據這些概率和式(9)進行計算，即

(14)

(15)

(3) 基于LAP進行關聯假設構建

基于LAP構造假設的宗旨在于構造N個概率相對最大的可行假設，因此在可行假設構建過程中，需要不斷在PA依據概率大小進行匹配對的選擇和移除，即采取2步策略：

第1步：初始選擇(構建第1個假設)。秉持概率最大原則，選擇每個目標與之相關概率最大的匹配對組成第1個假設，依據式(14)可知，這種方法構建的第1個假設的概率將是所有可能假設中最大的。

第2步：替換迭代(構建其余假設)。其余(N-1)個可行假設的構造方法同樣遵循概率最大原則，方法和上述方法相同，即逐次在之前構建的假設的基礎上進行匹配對的替換(即移除和再選擇，移除其中的某個匹配對，并在未被選擇的匹配對中選擇概率最大的替換)，直至N個可行假設全部構造完畢。

(4) 選擇概率最大的關聯假設進行數據關聯

得到N個假設之后，按概率高低進行排序，并從中選擇概率最大的假設將測量值與目標之間進行關聯。依據上述方法對表1進行實例分析，得到的10個假設如表2所示。

表2 10個關聯假設中的測量值的匹配目標Table 2 Ten matching target of measure value with an assumption of relationship

建立了基于LAP的多假設構造和數據關聯方法之后，便可以基于EKF建立MHT跟蹤算法，其基本流程如圖1所示。

圖1 基于MHT算法的彈道導彈目標跟蹤過程示意圖Fig.1 Progress sketch map of ballistic missiles' target tracking based on MHT algorithm

3 仿真分析

3.1 MHT算法對鄰近發射和軌跡交叉的多目標的跟蹤能力

首先測試MHT算法對多目標鄰近發射和軌跡交叉時的適用性，將導彈的發射時間置于同一時刻，并運用MHT算法進行多目標跟蹤，仿真結果如圖2，3所示。

可見，所有彈道導彈均能夠被MHT算法良好跟蹤，且軌跡交叉的彈道導彈也能夠被MHT算法迅速區分并分別跟蹤。這初步說明本文建立的MHT算法對鄰近發射和軌跡交叉的多目標具有較好的分辨能力，跟蹤性能較好。

圖2 MHT算法對雙彈道導彈目標的跟蹤效果Fig.2 Tracking effect of MHT algorithm to double ballistic missile targets

圖3 MHT算法對三彈道導彈目標的跟蹤效果Fig.3 The tracking effect of MHT algorithm to three ballistic missile targets

3.2 MHT算法對變加速度目標的跟蹤能力仿真

為了檢驗MHT算法在更多種類彈道導彈目標跟蹤過程中的適用性，接下來測試MHT算法對變加速度目標的跟蹤性能。首先，設2枚彈道導彈同時發射，并設置彈道導彈加速度為非線性(分段推進)，仿真結果如圖4a)所示。可見，由于彈道導彈在第1級推進結束之后(80 s)，存在一個突然減速過程，這導致MHT算法在跟蹤到彈道導彈發射后80 s時突然停止，跟蹤失敗。表明上述設置的MHT算法對變加速運動的多目標的跟蹤效果并不理想。

但MHT算法對相同變加速度運動的單目標的跟蹤效果卻非常好，如圖4b)所示。究其原因為單目標時MHT算法無需多目標匹配，實際上就是單目標的卡爾曼濾波算法，故跟蹤效果較好。

圖4 MHT算法對變加速運動彈道導彈 目標助推段的跟蹤效果Fig.4 Boost phase tracking effect of MHT algorithm to ballistic missile targets with variable accelerated motion

圖5 仿真過程中目標助推段加速度Fig.5 Boost phase acceleration of target in simulation progress

圖6 跟蹤過程中MHT算法差分變化情況Fig.6 Different change of MTH algorithm in progress of tracking

為了改進MHT算法中的上述缺點，采用門限技術對其進行處理。從MHT的跟蹤過程可知，式(13)給出了每種測量值和目標匹配的概率(也就是對每種匹配進行了打分)，在MHT算法中即要求關聯匹配假設的聯合概率達到最大，這也就是使得目標狀態估計值和測量值之間的距離最小。因此，利用差分協方差建立距離門限為

(16)

式中：G為設定的門限值。

這就增加了一個約束：當距離D的絕對值超出門限值G時，MHT算法將采取簡單地進行匹配，而不進行選擇概率最大的匹配。經過仿真試驗，門限值G設為2時，MHT算法具有較好的性能。

下面對改進后的MHT算法進行仿真實驗。仿真中令MHT算法跟蹤2個均為兩級推進的彈道導彈，結果如圖7所示。

圖7 改進MHT算法跟蹤同時發射雙目標Fig.7 Tracking of double target lunched at the same time with improved MTH algorithm

可見，在彈道導彈由一級轉二級推進過程中，MHT算法對它們的跟蹤存在一個微小的波動，這是因為此時，由于距離超出門限值，算法初始化了2個額外的測量值(如k=64,j=2;k=65,m=4)，并進行了不正確的關聯，這種過程大約維持了6個步長(即6 s，時間步長為1 s)，在MHT算法進行到第70個仿真步長時，已經收斂到每個目標的真實飛行軌跡。

更多目標的仿真測試結果表明，修改后的MHT算法能夠較好地滿足對多目標的跟蹤需求，如圖8所示。圖8中所示為當6枚彈道導彈依次間隔2～10 s發射時(換級推進發生在80～90 s)，MHT算法對這6枚彈道導彈的跟蹤情況，可見MHT算法不僅對彈道導彈進行了良好的跟蹤，對拋出的一級發動機也進行有效跟蹤，這有利于進行目標識別。

圖8 改進MHT算法跟蹤近同時發射六目標Fig.8 Tracking of six targets lunched almost at the same time with improved MTH algorithm

4 結束語

本文僅是對彈道導彈多目標跟蹤復雜性降級問題的初步嘗試，研究中作了很多簡化和假設，特別是對彈道導彈的機動突防考慮不足。在后續研究中，若將多目標跟蹤領域的交互式多模型(interacting multiple model，IMM)技術引入到MHT算法中，將使得多假設中各分支的分值估計更準確，進一步改善其對考慮目標機動的彈道導彈的跟蹤性能。

參考文獻：

[1] 張洪波, 鄭偉, 朱隆魁，等. 彈道導彈進攻中多目標突防的效能分析[J]. 宇航學報, 2007, 28(2):394-397.

ZHANG Hong-bo, ZHENG Wei, ZHU Long-kui, et al. The Effectiveness Analysis of Multi-Target Penetration Ballistic Missile Attack [J]. Journal of Astronautics, 2007, 28(2): 394-397.

[2] PULFORD G W. Taxonomy of Multiple Target Tracking Methods [J]. IEE Proc-Radar Sonar Navig, 2005, 152(5): 291-304.

[3] BLACKMAN S S. Multiple Hypothesis Tracking for Multiple Target Tracking [J]. IEEE A&.E Systems Magazine, 2004, 19(1): 5-18.

[4] Bert Rakdham. Efficient Multiple Hypothesis Track Processing of Boost-Phase Ballistic Missiles Using IMPULSE-Generated Threat Models[D]. U.S. Monterey: Naval Postgraduate School, 2006.

[5] BAR-SHALOM Y,BLACKMAN S S. Dimensionless Function for Multiple Hypothesis Tracking [J]. IEEE Trans on Aerospace and Electronics Systems, 2007, 43(1): 392-400.

[6] POPP R L,PATTIPATI K R,BAR-SHALOM Y. m-Best S-D Assignment Algorithm with Application to Multitarget Tracking[J]. IEEE Trans on Aerospace and Electronics Systems, 2001, 37(1): 22-39.

[7] DEB S, YEDDANAPUDI M, PATTIPATI K R, et al. A Generalized S-D Assignment Algorithm for Multisensor-Multitarget State Estimation [J]. IEEE Trans on Aerospace and Electronic Systems, 1997, 33(2): 523-538.

[8] KIRUBARAJAN T, BAR-SHALOM Y, PATTIPATI K R. Efficient Multisensor Fusion Using Multidimensional Data Association [J]. IEEE Trans on Aerospace and Electronics Systems, 2001, 37(2): 386-398.

[9] 湯軍, 孫偉. 彈道目標跟蹤的自適應多維分配相關算法[J]. 彈道學報, 2011, 23(2): 72-75.

TANG Jun, SUN Wei. Adaptive Multi-Dimension Assignment Algorithm for Tracking Ballistic Target [J]. Journal of Ballistics, 2011, 23(2): 72-75.

[10] 何佳洲, 吳傳利, 周志華，等. 多假設跟蹤技術綜述[J]. 火力與指揮控制, 2004, 29(6): 1-4.

HE Jia-zhou, WU Chuan-li, ZHOU Zhi-hua, et al. Survey of Multiple Hypothesis Tracking [J]. Fire Control and Command Control, 2004, 29(6): 1-4.

[11] MORI S. Tracking and Classifying Multiple Targets Without a Priori Identification [J]. IEEE Transactions on Aerospace and Electronic Systems, 1986, 31(5): 401-409.

[12] REID D B. An Algorithm for Tracking Multiple Targets [J]. IEEE Transaction on Automatic Control, 1978, 24(6): 1202-1211.

[13] NAGARAJAN V， CHIDAMBARA M R, SHARMA R N. New Approach to Improved Detection and Tracking Performance in Track-While-Scan Radars [J]. IEEE Proceedings, 1987, 134(1): 89-112.

[14] STONE L D, BARLOW C A, CORWIN T L. Bayesian Multiple Target Tracking [M]. Maryland：Artch House,1999.

[15] COX I J, HINGORANI S L. An Efficient Implementation of Reid’s Multiple Hypothesis Tracking Algorithm and Its Evaluation for the Purpose of Visual Tracking [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(2): 138-150.

[16] BAR-SHALOM Y,LI X. Estimation and Tracking-Principles, Techniques, and Software [J]. IEEE Antennas and Propagation, 1996，38(1): 62-63.

[17] DANCHICK R, NEWNAM G E. A Fast Method for Finding the Exact N-Best Hypotheses for Multitarget Tracking [J]. IEEE Transactions on Aerospace and Electronic Systems, 1993, 29(2): 555-560.