王瑞 肖宇峰 朱鴿

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

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

一、引言

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

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

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

二、基本粒子濾波算法

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

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

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

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

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

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

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

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

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

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

三、重采樣

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

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

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

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

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

KL距離，是信息論中的相對(duì)熵，常用來(lái)衡量?jī)蓚€(gè)隨機(jī)分布的相似度。其定義式如下：L=[1Nw]1/m （13）

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

五、仿真分析

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

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

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

六、結(jié)束語(yǔ)

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

參看文獻(xiàn)：

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

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