一種改進(jìn)重采樣的粒子濾波算

王瑞 肖宇峰 朱鴿

摘要：重采樣過程是解決粒子濾波中粒子退化問題的有效手段，但隨著算法迭代會引起粒子多樣性的喪失。本文提出一種線性組合的重采樣算法改進(jìn)方法，解決多樣性問題。具體為：判斷有效粒子數(shù)，進(jìn)入重采樣過程，得到將淘汰與復(fù)制的粒子，并用它們的線性組合作為新的濾波粒子。通過實驗證明，此方法對于粒子數(shù)不大的情況效果良好。

關(guān)鍵字：粒子濾波；重采樣；線性組合；多樣性

一、引言

粒子濾波（PF）是一種基于蒙特卡羅思想的概率濾波[1，2]。通過對概率密度函數(shù)采樣得到一組在狀態(tài)空間傳播的隨機(jī)樣本，來對后驗概率密度進(jìn)行估計。采用概率的方法，用樣本均值代替復(fù)雜的積分運算，以獲得系統(tǒng)狀態(tài)的最小方差估計。具體過程為：對于平穩(wěn)隨機(jī)過程，在K-1時刻獲取n個隨機(jī)樣本點，通過狀態(tài)更新和時間更新來預(yù)測K時刻的系統(tǒng)狀態(tài)。隨著粒子數(shù)的增加，粒子濾波逐漸逼近最優(yōu)貝葉斯估計。

PF算法主要步驟有重要性采樣、權(quán)值更新和重采樣過程。重采樣過程的引進(jìn)，解決了粒子退化的問題。其主要方法是當(dāng)有效粒子數(shù)小于閾值時，復(fù)制高權(quán)值粒子代替要淘汰的低權(quán)值粒子，并保持粒子數(shù)不變。與此同時，重采樣過程帶來了粒子多樣性的喪失的問題，嚴(yán)重影響了算法的精確度。

本文主要工作是對基本粒子濾波的重采樣部分進(jìn)行改進(jìn)。以將淘汰的小權(quán)值粒子與待復(fù)制的高權(quán)值粒子的組合產(chǎn)生新粒子，這種方式可避免粒子的重復(fù)采用，克服粒子多樣性喪失的問題。Matlab仿真證明，本文方法有效，能一定程度改善算法性能。

二、基本粒子濾波算法

對于離散時間動態(tài)系統(tǒng)，算法可采用以下模型描述：

狀態(tài)方程：xk=fx（xk-1，wk） （1）；觀測方程： zk=hkxk，vk （2）

其中，為k時刻的狀態(tài)，分別為系統(tǒng)噪聲和觀測噪聲。算法的目的是根據(jù)觀測數(shù)據(jù)遞推的估計出系統(tǒng)狀態(tài)的后驗概率分布。

粒子濾波通過迭代，采用有限的加權(quán)樣本近似系統(tǒng)狀態(tài)的后延概率密度?？杀硎緸椋簆x0：kzk=1Ni=1N未（x0：k-x0：ki）（3）

但在實際的問題中，很難從后驗概率中直接采樣的到粒子，通常采用一種易于采樣的已知概率分布函數(shù)，我們稱之為重要性密度函數(shù)，一般選擇重要性密度函數(shù)為狀態(tài)轉(zhuǎn)移概率密度函數(shù)?；玖Ｗ訛V波算法步驟如下：

a.初始化。在k=0時刻，從已知的先驗概率分布中采樣N個粒子，得到初始樣本集{}，i=1，，權(quán)重均設(shè)置為1/N。

b.狀態(tài)更新。K-1時刻，粒子集{}通過系統(tǒng)狀態(tài)方程進(jìn)行迭代，得到k時刻的狀態(tài)估計。

c.觀測更新。當(dāng)?shù)玫接^測量時，對預(yù)測的粒子進(jìn)行權(quán)值更新并歸一化。wki∝wk-1pzkxkip（xki|xk-1i）q（xki|x0：k-1i，zk） （4），w～ki=wki/i=1Nwki （5），后驗概率密度近似為：p（xk|zk）=i=1Nwki未（xk-xki） （6）

d.重采樣。計算有效粒子數(shù)，當(dāng)其小于給定閾值時，進(jìn)行重采樣。復(fù)制高權(quán)值粒子代替低權(quán)值粒子，并保持粒子數(shù)目不變，歸一化權(quán)值。

e.輸出結(jié)果可得到系統(tǒng)的后驗概率密度：P～xkzk=1NI=1N未（xk-x～ki） （7）狀態(tài)估計為xk～=E（x）P～xkzk=xP～xkzkdx=1Ni=1kx～ki （8），令k=k+1，返回b。

三、重采樣

為了解決粒子濾波算法退化問題，提高算法精確度，引入了重采樣過程。重采樣的基本思想是通過復(fù)制高權(quán)值粒子代替低權(quán)值粒子。

通過觀測方程更新粒子權(quán)值后，計算有效粒子數(shù)，當(dāng)其小于給定閾值時，進(jìn)行重采樣過程。閾值通常設(shè)置為粒子總數(shù)的2/3，有效粒子數(shù)定義為：

Neff=N1+var（w～ki） （9），有效樣本越小，說明退化越嚴(yán)重。其中：wki=p（xki|xk-1i）q（xki|x0：k-1i ，z1：k） =（10），通常，近似為： Neff～=1i=1N（wki）2 （11）。

四、改進(jìn)重采樣粒子濾波

在極端情況下，傳統(tǒng)重采樣算法在經(jīng)過若干次的迭代后，所有的采樣粒子都是一個高權(quán)值粒子的副本，嚴(yán)重影響算法性能。解決算法多樣性的方法之一是為每個粒子引入馬氏鏈蒙特卡羅方法（MCMC）移動步驟。其基本思想是通過利用馬爾科夫傳遞函數(shù)傳遞粒子，使之位于狀態(tài)空間中更希望的位置。這種方法弊端明顯，增加了算法的計算復(fù)雜度，其時間耗費比基本粒子濾波高一倍，影響算法實時性。左軍毅等人提出一種自適應(yīng)的部分重采樣方法。由于傳統(tǒng)的重采樣是對整個粒子集進(jìn)行重采樣，這種過度采樣帶來了樣本匱乏現(xiàn)象，因此作者提出只對一部分粒子進(jìn)行重采樣，最終的粒子集由重采樣后的粒子和未采樣的粒子構(gòu)成。這種方法實際上實在退化現(xiàn)象和樣本匱乏之間做了適當(dāng)?shù)恼壑?。提出一種改進(jìn)的系統(tǒng)重采樣方法，即靈敏重采樣方法，比較粒子的權(quán)值后，僅保留權(quán)值較大的粒子，然后基于擬蒙特卡洛方法來繁殖后代，此算法能夠有效抑制樣本匱乏現(xiàn)象，提高粒子濾波算法的估計精確度。但是該算法的代價仍是增加了計算時間，雖然可以以較少的粒子數(shù)來實現(xiàn)算法，但也僅僅能到到有限的精度與時間上的平衡。

本文提出組合重采樣算法，充分利用低權(quán)值粒子，當(dāng)需要進(jìn)行重采樣時，通過待復(fù)制的高權(quán)值粒子和待淘汰的低權(quán)值粒子的線性組合產(chǎn)生新的樣本點。其組合方式如下：xn=xs+L（xa-xs） （12）。

式中：是通過線性組合產(chǎn)生的新樣本點。為重復(fù)選擇的高權(quán)值粒子點，為將淘汰的低權(quán)值粒子。若產(chǎn)生的新樣本點的權(quán)值比原采樣點的權(quán)值小，L為0到1之間的隨機(jī)數(shù)。

KL距離，是信息論中的相對熵，常用來衡量兩個隨機(jī)分布的相似度。其定義式如下：L=[1Nw]1/m （13）

在基本的粒子濾波中，重采樣過程是簡單地淘汰與復(fù)制粒子完成的，直接丟失了部分粒子信息。而在改進(jìn)的組合重采樣粒子濾波中，是通過線性組合，把將淘汰的粒子信息融合到新產(chǎn)生的粒子中。因此可以用KL距離計算并得到，使用本文改進(jìn)的算法，總可以使得重采樣后的近似概率分布和重采樣前的概率分布更接近，從而得到比基本重采樣更好地對狀態(tài)的估計。

五、仿真分析

采用matlab對算法進(jìn)行仿真研究。系統(tǒng)為一維非線性系統(tǒng)。狀態(tài)方程和觀測方程使用的經(jīng)典方程，如下：wki>KNnj1/m （14），K（p，q）=xp（x）lgp（x）q（x） （15）

式中和是獨立的高斯白噪聲序列，且測量噪聲的均值為0，方差R=1，，N=50。

實驗仿真比較的是基本粒子濾波和本文改進(jìn)粒子濾波方法得到的 xk=0.5xk-1+2.5xk-11+xk-12+8cos[1.2（k-1）]+ wk-1 （16）

六、結(jié)束語

針對基本粒子濾波的粒子多樣性問題。本文提出了一種基于線性組合重采樣的粒子濾波方法。從實驗仿真可以看出，此方法在一定程度上解決了多樣性問題，相比于基本粒子濾波，在粒子數(shù)量不大時具有更好地性能。但當(dāng)粒子數(shù)量較多時算法優(yōu)越不明顯，值得進(jìn)一步的研究。

參看文獻(xiàn)：

[1]朱志宇.粒子濾波算法及其應(yīng)用[M].北京：科學(xué)出版社，2010：4-8，114-125.

[2]付夢印，鄧志紅，閆麗萍.Kalman濾波理論及其在導(dǎo)航系統(tǒng)中的應(yīng)用[M].2版.北京：科學(xué)出版社，2010：185-202.