一種改進重采樣的粒子濾波算

王瑞 肖宇峰 朱鴿

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

關鍵字：粒子濾波；重采樣；線性組合；多樣性

一、引言

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

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

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

二、基本粒子濾波算法

對于離散時間動態系統，算法可采用以下模型描述：

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

其中，為k時刻的狀態，分別為系統噪聲和觀測噪聲。算法的目的是根據觀測數據遞推的估計出系統狀態的后驗概率分布。

粒子濾波通過迭代，采用有限的加權樣本近似系統狀態的后延概率密度。可表示為：px0：kzk=1Ni=1N未（x0：k-x0：ki）（3）

但在實際的問題中，很難從后驗概率中直接采樣的到粒子，通常采用一種易于采樣的已知概率分布函數，我們稱之為重要性密度函數，一般選擇重要性密度函數為狀態轉移概率密度函數。基本粒子濾波算法步驟如下：

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

b.狀態更新。K-1時刻，粒子集{}通過系統狀態方程進行迭代，得到k時刻的狀態估計。

c.觀測更新。當得到觀測量時，對預測的粒子進行權值更新并歸一化。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.重采樣。計算有效粒子數，當其小于給定閾值時，進行重采樣。復制高權值粒子代替低權值粒子，并保持粒子數目不變，歸一化權值。

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

三、重采樣

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

通過觀測方程更新粒子權值后，計算有效粒子數，當其小于給定閾值時，進行重采樣過程。閾值通常設置為粒子總數的2/3，有效粒子數定義為：

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

四、改進重采樣粒子濾波

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

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

式中：是通過線性組合產生的新樣本點。為重復選擇的高權值粒子點，為將淘汰的低權值粒子。若產生的新樣本點的權值比原采樣點的權值小，L為0到1之間的隨機數。

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

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

五、仿真分析

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

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

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

六、結束語

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

參看文獻：

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

[2]付夢印，鄧志紅，閆麗萍.Kalman濾波理論及其在導航系統中的應用[M].2版.北京：科學出版社，2010：185-202.