一種JPDA 的快速算法

袁富宇，石汪權(quán)，蒲 勇

（江蘇自動(dòng)化研究所，江蘇 連云港 222061）

0 引言

聯(lián)合概率互聯(lián)算法（JPDA）［2］是雜波環(huán)境下多目標(biāo)跟蹤的一種有效方法。類似于概率互聯(lián)算法（PDA）［1］，JPDA 算法對(duì)于落入目標(biāo)預(yù)測波門內(nèi)的所有量測點(diǎn)都要考慮，即波門內(nèi)的所有量測點(diǎn)都參與濾波計(jì)算，但參與的“力度”有所不同，這個(gè)“力度”就是量測點(diǎn)與目標(biāo)航跡的互聯(lián)概率。JPDA 算法的復(fù)雜性就在于互聯(lián)概率的計(jì)算，要考慮所有量測點(diǎn)與所有目標(biāo)航跡關(guān)系的可能性及其概率，即聯(lián)合事件及其概率。聯(lián)合事件的個(gè)數(shù)隨量測點(diǎn)（包括雜波）數(shù)目與目標(biāo)航跡數(shù)的增長呈指數(shù)級(jí)增長，這使得JPDA 算法在雜波密集環(huán)境及目標(biāo)數(shù)目很大的情況下變得不適用［6-9］（實(shí)時(shí)性較差），相關(guān)內(nèi)容請(qǐng)參考文獻(xiàn)［3-4，10-15］。

1 相關(guān)波門計(jì)算的優(yōu)化改進(jìn)

在JPDA 算法中，為判斷量測點(diǎn)是否落入某一目標(biāo)航跡預(yù)測波門內(nèi)，需要計(jì)算變量

2 濾波方差的簡化計(jì)算

3 確認(rèn)矩陣的降維

在傳感器探測過程中，除非所有目標(biāo)都集中在某一狹小區(qū)域，使得它們的航跡預(yù)測波門相互重疊，一般情況下多數(shù)目標(biāo)在范圍較大的空間分布（除了編隊(duì)目標(biāo)、航路交叉目標(biāo)等），預(yù)測波門不會(huì)全部相互重疊。若此時(shí)再用統(tǒng)一的確認(rèn)矩陣進(jìn)行互聯(lián)概率的計(jì)算，將會(huì)帶來“巨大”的無謂計(jì)算量（呈指數(shù)級(jí)增長）。因此，有必要對(duì)多目標(biāo)進(jìn)行分類，把航跡預(yù)測波門相互重疊的目標(biāo)分成一類，稱為“關(guān)聯(lián)目標(biāo)類”。每一探測周期可能會(huì)有多個(gè)這樣的關(guān)聯(lián)目標(biāo)類，當(dāng)然，有些類中可能僅有一批目標(biāo)，但沒有空目標(biāo)類。然后，再對(duì)每一關(guān)聯(lián)目標(biāo)類形成各自的確認(rèn)矩陣，這樣確認(rèn)矩陣維數(shù)可能會(huì)下降許多。

關(guān)聯(lián)目標(biāo)類生成方法如下：

1）對(duì)所有目標(biāo)航跡和當(dāng)前周期所有（相關(guān)）量測形成確認(rèn)矩陣（行對(duì)應(yīng)量測，列對(duì)應(yīng)目標(biāo)航跡，第1 例除外）。

2）對(duì)所有目標(biāo)序號(hào)進(jìn)行循環(huán)計(jì)算：①若當(dāng)前目標(biāo)航跡i 已被分類，跳到下一批目標(biāo)；②新關(guān)聯(lián)目標(biāo)類標(biāo)志：類序號(hào)、類中目標(biāo)數(shù)量、類中目標(biāo)序號(hào)等；③從確認(rèn)矩陣中取出當(dāng)前目標(biāo)航跡的相關(guān)向量，即目標(biāo)對(duì)應(yīng)的列向量v1i（由0、1 組成）；④對(duì)當(dāng)前目標(biāo)航跡序號(hào)后的剩余目標(biāo)航跡序號(hào)進(jìn)行循環(huán)確認(rèn)：抽取后續(xù)目標(biāo)j 的相關(guān)向量v2j；如果內(nèi)積〈v1i，v2j〉＞0，那么目標(biāo)航跡j 與目標(biāo)航跡i 同為關(guān)聯(lián)類（有共同的量測量）；v1i+v2j→v1i；⑤循環(huán)④結(jié)束后檢查當(dāng)前關(guān)聯(lián)目標(biāo)類中是否加入了新目標(biāo)，若是返回④重新循環(huán)一次，否則轉(zhuǎn)⑥；⑥繼續(xù)目標(biāo)序號(hào)循環(huán)分類。

通過上述操作就可以把所有目標(biāo)航跡分成相互“獨(dú)立”的關(guān)聯(lián)目標(biāo)類，關(guān)聯(lián)目標(biāo)類中可能包含多批目標(biāo)，也可能僅有一批目標(biāo)（不存在空類），包含多批目標(biāo)的關(guān)聯(lián)目標(biāo)類中的目標(biāo)至少有一個(gè)公共相關(guān)量測量（否則它們也關(guān)聯(lián)不到一起），單目標(biāo)類中的目標(biāo)可能一個(gè)相關(guān)量測也沒有。因此，即使多批目標(biāo)航跡的預(yù)測波門有重疊，但沒有公共相關(guān)量測的話，也不能劃為一個(gè)關(guān)聯(lián)類（目標(biāo)關(guān)聯(lián)的紐帶是公共相關(guān)量測）。

4 互聯(lián)概率的遞歸計(jì)算

如果采用拆分矩陣的辦法來計(jì)算互聯(lián)事件的概率，那么可能會(huì)占用較大的內(nèi)存空間。因此，建議采用遞歸函數(shù)的形式遞歸計(jì)算會(huì)減少對(duì)內(nèi)存的需求。

首先，對(duì)單目標(biāo)關(guān)聯(lián)類應(yīng)用標(biāo)準(zhǔn)PDA 算法即可；其次，對(duì)僅有一個(gè)相關(guān)量測的多目標(biāo)關(guān)聯(lián)類進(jìn)行特殊處理；最后，對(duì)具有多個(gè)相關(guān)量測的多目標(biāo)關(guān)聯(lián)類采用遞歸計(jì)算形式處理：1）形成關(guān)聯(lián)目標(biāo)類的確認(rèn)矩陣；2）對(duì)關(guān)聯(lián)類中每一批目標(biāo)計(jì)算與之相關(guān)的量測的互聯(lián)概率：對(duì)類中所有目標(biāo)序號(hào)循環(huán)（第一重循環(huán)）。

4.1 計(jì)算所選目標(biāo)與相關(guān)量測的互聯(lián)概率

對(duì)類中所選目標(biāo)的所有相關(guān)量測量序號(hào)循環(huán)（第二重循環(huán)）。

如果當(dāng)前目標(biāo)t 與當(dāng)前量測j 在關(guān)聯(lián)類確認(rèn)矩陣中對(duì)應(yīng)的元素為0，那么兩者的互聯(lián)概率置0：βtj（k）=0；

否則，從關(guān)聯(lián)類確認(rèn)矩陣中刪除當(dāng)前目標(biāo)航跡序號(hào)對(duì)應(yīng)的列，刪除當(dāng)前量測序號(hào)對(duì)應(yīng)的行（即互聯(lián)事件的第一個(gè)節(jié)點(diǎn)已確定，就是“當(dāng)前量測是當(dāng)前目標(biāo)的真實(shí)量測”），形成新的子確認(rèn)矩陣。對(duì)該子確認(rèn)矩陣進(jìn)行遞歸拆分，以計(jì)算互聯(lián)事件后續(xù)節(jié)點(diǎn)的所有可能情況，每一路徑（遵照確認(rèn)矩陣拆分原則［2，8］）結(jié)束時(shí)計(jì)算該互聯(lián)事件發(fā)生的概率，并對(duì)這些所有的互聯(lián)事件概率累加記錄（這些互聯(lián)事件的首節(jié)點(diǎn)都相同）。

4.2 計(jì)算所選目標(biāo)沒有量測的概率（對(duì)應(yīng)βt0（k））

刪除當(dāng)前目標(biāo)t 的航跡序號(hào)對(duì)應(yīng)的列，形成新的子確認(rèn)矩陣，對(duì)該子確認(rèn)矩陣進(jìn)行遞歸拆分，每一互聯(lián)事件的首節(jié)點(diǎn)都相同，即“當(dāng)前目標(biāo)t 沒有真實(shí)量測”，最后累加求出βt0（k）。

5 仿真計(jì)算

為使仿真結(jié)論具有一定的可信性，本文選擇5種目標(biāo)態(tài)勢（二維探測），對(duì)上述多種簡化/優(yōu)化改進(jìn)進(jìn)行驗(yàn)證比較。比較的性能指標(biāo)選用通常的誤跟率和跟蹤精度。誤跟率的計(jì)算考慮跟蹤結(jié)束前連續(xù)n 個(gè)周期（本文選取n=6）的濾波值與相應(yīng)真值（都轉(zhuǎn)化為量測量B、D）的差值，只要n 個(gè)差值同時(shí)不大于量測誤差均方根，就認(rèn)為此次仿真計(jì)算正確跟蹤上了。記錄每一探測周期的跟蹤誤差，再統(tǒng)計(jì)計(jì)算每一周期的跟蹤誤差均方根。

5.1 算例描述

為簡單起見，探測器位于大地直角坐標(biāo)原點(diǎn)靜止不動(dòng)，所有目標(biāo)速度VT=20 kn（水面航行目標(biāo)），選取量測誤差σB=0.1°，σD=80 m，虛警密度=0.3（每平方公里個(gè)數(shù)，泊松分布），探測周期10 s，每次仿真計(jì)算100 個(gè)周期，統(tǒng)計(jì)100 次。

態(tài)勢1：D0=100 km，α=10°，目標(biāo)數(shù)Nt=2～10，交叉點(diǎn)位于目標(biāo)航跡中點(diǎn)；

態(tài)勢2：D0=100 km，α=360°/（2～Nt），目標(biāo)數(shù)Nt=2～10，交叉點(diǎn)位于目標(biāo)航跡中點(diǎn)；

態(tài)勢3：D0=100 km，Dt1=0.5 km～2 km，Dt2=0.5 km～2 km，目標(biāo)數(shù)Nt=4～10，交叉點(diǎn)兩側(cè)的目標(biāo)航跡長度相等；

態(tài)勢4：D0=100 km，Dt=0.5 km～2 km，目標(biāo)數(shù)Nt=2～10；

態(tài)勢5：D0=100 km，Dt1=0.5 km～1.5 km（橫向間距），Nt=4～7，dD=0.5 km～1.5 km（縱向間距）。

圖1 同向聚攏交叉仿真態(tài)勢

圖2 相向聚攏交叉仿真態(tài)勢

圖3 平行交叉仿真態(tài)勢圖

圖4 雁形編隊(duì)仿真態(tài)勢

圖5 “特混”編隊(duì)仿真態(tài)勢

5.2 點(diǎn)航相關(guān)計(jì)算改進(jìn)驗(yàn)證

R0（k|k-1）表示預(yù)測量測協(xié)方差代替所有量測協(xié)方差進(jìn)行相關(guān)計(jì)算，Rj（k）表示利用每一量測的協(xié)方差進(jìn)行相關(guān)計(jì)算。每一態(tài)勢列出了每一批目標(biāo)的誤跟率、平均誤跟率及100 次統(tǒng)計(jì)計(jì)算所用時(shí)間。在態(tài)勢3 中取Dt1=Dt2=0.8 km，在態(tài)勢4 中取Dt=0.8 km。

從表1 中可看出，用R0（k|k-1）代替Rj（k）是完全可以的，誤跟率保持不變。兩者的跟蹤精度幾乎完全一樣，此處就不再畫出精度圖了（它們幾乎會(huì)重合在一起）。

表1 互聯(lián)分類相關(guān)計(jì)算改進(jìn)仿真結(jié)果

5.3 濾波方差計(jì)算改進(jìn)驗(yàn)證

表2 中P0表示量測量方差皆用R0（k|k-1）代替，Pj表示用各量測量自身的方差Rj（k）。

表2 濾波方差計(jì)算改進(jìn)仿真結(jié)果

可以看出，兩者的誤跟率相差無幾，每一周期的濾波精度也幾乎一樣（誤差曲線基本重合在一起，故沒有畫出），仿真計(jì)算100 次所需時(shí)間也相差不大（當(dāng)然P0所用時(shí)間會(huì)少一些），具體應(yīng)用時(shí)可根據(jù)面對(duì)的多目標(biāo)環(huán)境選擇P0或Pj策略（目標(biāo)少就選Pj，多的話可以選擇P0）。

5.4 確認(rèn)矩陣降維改進(jìn)驗(yàn)證

由于計(jì)算公式完全一樣，改進(jìn)方法只是在計(jì)算策略上做了一些優(yōu)化改進(jìn)，因此，降維改進(jìn)和原JPDA 算法的計(jì)算結(jié)果完全一樣，可能會(huì)由于隨機(jī)數(shù)的選取原因會(huì)有微小差異。因此，本小節(jié)的驗(yàn)證主要比較降維前后的計(jì)算用時(shí)（100 次統(tǒng)計(jì)計(jì)算總時(shí)間）。為了盡快算出結(jié)果，與5.3 小節(jié)相比，態(tài)勢1 和態(tài)勢5 都減少了目標(biāo)批數(shù)。

從表3 可以看出，確認(rèn)矩陣降維改進(jìn)后的互聯(lián)概率計(jì)算方法明顯減少了很多計(jì)算時(shí)間。在不很密集的條件下，如果目標(biāo)數(shù)目和雜波率都再提高，那么兩者用時(shí)差距更大。因此，降維優(yōu)化的改進(jìn)效果是顯著的。

表3 確認(rèn)矩陣降維改進(jìn)仿真結(jié)果

6 結(jié)論

本文對(duì)標(biāo)準(zhǔn)JPDA 算法做了一些計(jì)算的簡化/優(yōu)化改進(jìn)，提出一種JPDA 快速算法，目的在保證JPDA 效果不變的前提下盡量減少其計(jì)算量。主要對(duì)實(shí)際應(yīng)用場景中點(diǎn)跡相關(guān)判斷計(jì)算、狀態(tài)方差計(jì)算做了改進(jìn)，尤其是提出一種用于確認(rèn)矩陣降維的關(guān)聯(lián)目標(biāo)類的簡便尋找方法。同時(shí)建議在確認(rèn)矩陣拆分時(shí)采用遞歸函數(shù)調(diào)用的方法，以減少對(duì)內(nèi)存空間的占用。仿真算例表明，通過降維，能夠極大減少算法的計(jì)算量，優(yōu)化改進(jìn)效果是顯著的。

另外，在仿真計(jì)算過程中發(fā)現(xiàn)有些航次“出奇”地耗時(shí)，初步分析認(rèn)為波門內(nèi)包含了過多的“量測”量，這說明波門過大。而波門計(jì)算又受到量測方差、狀態(tài)方差的影響，因此，對(duì)波門、狀態(tài)變化、狀態(tài)方差之間相互影響的關(guān)系，有必要進(jìn)行深入細(xì)致的分析研究。自適應(yīng)地限制波門內(nèi)的量測參與濾波也許是縮小計(jì)算量的另一途徑。