粒子濾波理論

粒子濾波理論模擬方法來實現(xiàn)遞推貝葉斯濾波，適用、目標(biāo)跟蹤、本章首先概述用于求解目標(biāo)狀態(tài)后驗概率的貝葉多樣性喪失問題，提出了一種量子進(jìn)化粒子濾波算法。貝葉斯濾波動態(tài)系統(tǒng)的目標(biāo)跟蹤問題可以通過圖2.1所示的狀態(tài)空間模型來描述。本節(jié)在貝葉斯濾波框架下討論目標(biāo)跟蹤問題。圖2.1 狀態(tài)空間模型Fig.2.1 Statespacemodel在目標(biāo)跟蹤問題中，動態(tài)系統(tǒng)的狀態(tài)空間模型可描述為xkf(xk1)uk1ykh(xk)vk

(2.1)f(h(xkykuk為過程vkXkx0:kx0x1,?xk與Yky1:ky1,?,yk}xkxk-1有關(guān)。另外ykkxk有關(guān)。貝式求解后驗概率密度pXk|Yk或濾波概率密度pxk|Yk)。新過程則利用最新的測量值對先驗概率密度進(jìn)行修正，得到后驗概率密度。xk1|Yk1，貝葉斯濾波的具體過程如下：p(xk,xk1|Yk1)p(xk|xk1,Yk1)p(xk1|Yk1)

(2.2)xk1xk與Yk1相互獨(dú)立，因此

(2.3)xk1Chapman-Komolgorov方程(2.4)pxk|Yk1pxk|Yk：kyk后，利用貝葉斯公式對先驗概率密度進(jìn)行更新，得到后驗概率p(x

xk,Yk1)p(xk|Yk1)k k p(y

k|Yk1)\*MERGEFORMAT(2.5)ykxk決定，即)p(yk|xk)因此p(x

|Yk1)k k p(y

k|Yk1)\*MERGEFORMAT(2.7)yk|Yk1為歸一化常數(shù)

|Yk1)p(yk|xk)p(xk|Yk1)dxk(MAP)準(zhǔn)則或最小均方誤差(MMSE)準(zhǔn)則，將具有極大后驗概率密度的狀態(tài)或條件均值作為系統(tǒng)狀態(tài)的估計值，即?AP

argminp(x

|Y)??[f(x|Y]

f(f(x)p(x

k k kxk\*MERGEFORMAT(2.9)階或二階Taylor級數(shù)展開的擴(kuò)展Kalman濾波得到廣泛應(yīng)用[119]濾中方案便是基于蒙特卡洛模擬的粒子濾波器。粒子濾波2050年代，Hammersley便采用基于序貫重要性采樣(Sequentialimportance2060年代后期，HandschinMayne122]2070Hachnkahi以及Zaritskii等學(xué)者的一系列研究工作使得序貫蒙特卡洛方法得到進(jìn)一步發(fā)展[123][126]。限卡洛方法成功解決了一系列高維積分問題[127-130]。SmithGelfand提出的采樣-重采樣思想Bayesian推理提供了一種易于實現(xiàn)的計算策略[131]。隨后，SmithGordon2090年代初將重采樣(Resampling)步驟引入到粒子濾波中，在一定程度上解決了序貫重要性采樣的權(quán)值退化問題，并由此產(chǎn)生了第一個可實現(xiàn)的SIR(SamplingimportanceNodestar21世紀(jì)，粒子濾波器成為[133-135]，IEEE出版的論文集“SequentialMonteCarloMethodsinPractice”對粒子濾波器進(jìn)行了詳細(xì)介紹[136]。貝葉斯重要性采樣蒙特卡洛模擬是一諾特卡洛模擬方法利用所求狀態(tài)空間中大量的樣本點(diǎn)來近似逼近待估計變量的后驗概率分布，px|YNx(ii1,?N，則有k k k1N (i)N(xkxk)Ni1

(2.11)xk為連續(xù)變量(x-xk為單位沖激函數(shù)(狄拉克函數(shù))，即x-xk)0,xxk，且(x)dx1。xkP(xk|Yk可近似逼近為P(x

1

x(i))k k N

i1

k k(2.12)

x(i))1,x

x(i);

x(i))0,x

x(i)。k k k k k k k k1圖2.2 經(jīng)驗概率分布函數(shù)Fig.2.2 Empiricalprobabilitydistributionfunctionkkx(i)為從后驗概率密度函數(shù)pxkk估計可以用求和方式逼近，即

f(xk的期望1N (i)Nf(xk)Ni1

(2.13)構(gòu)造概率模型。對于本身具有隨機(jī)性質(zhì)的問題，主要工作是正確地描述和模擬這個概用蒙特卡洛方法求解需要事先構(gòu)造一個人為的概率過程，將它的某些參量視為問題的解。從指定概率分布中采樣。產(chǎn)生服從己知概率分布的隨機(jī)變量是實現(xiàn)蒙特卡洛方法模擬試驗的關(guān)鍵步驟。建立各種估計量的估計。一般說來，構(gòu)造出概率模型并能從中抽樣后，便可進(jìn)行現(xiàn)模擬試驗。隨后，就要確定一個隨機(jī)變量，將其作為待求解問題的解進(jìn)行估計。qxk|Yk，從中生成采樣粒子，利用這些隨機(jī)樣本的加權(quán)和來逼近后驗濾波概率密度px|Y)，如圖2.3所示。令{x(iw(ii1,?.N}x(i)為k k k k kkk時刻第iw(i，則后驗濾波概率密度可以表示為kp(x

|Y)w(i)(x

x(i))Nk k k k N(2.14)其中，wwk

p(x(i)|Y) k kk q(x(i)|Yk

(2.15)圖2.3 重要性采樣Fig.2.3 Importancesampling當(dāng)采樣粒子的數(shù)目很大時，式(2.14)便可近似逼近真實的后驗概率密度函數(shù)。任意函數(shù)的期望估計為1N (i)

p(x(i)|Y) 1N

(i) (i)

NN

) k kk q(x(i)|Yk

NN

)wk(2.16)序貫重要性采樣算法在基于重要性采樣的蒙特卡洛模擬方法中，估計后驗濾波概率需要利用所有的觀測數(shù)x0:k|y1:k)q(x0:k1|y1:k1)q(xk|x0:k1,y1:k)

k(2.18)k(2.19)后驗概率密度函數(shù)的遞歸形式可以表示為p(x

0:k k

yk|Yk1)p(yk|x0:k,Yk1)p(xk|x0:k1,Yk1)p(x0:k1|Yk1)xk)p(xk|xk1)p(x0:k1|Yk1)p(yk|Yk1)(2.20)k粒子權(quán)值w(i)的遞歸形式可以表示為kwwk

p(x(i)|Y) 0:k k0:k q(x(i)|Y0:k p(y|x(i))p(x(i)|x(i))p(x(i) |Y ) k k k 1 1q(x(i)|x(i)

,Y)q(x(i) |Y )k k

k1(i)

|x(i))p(x(i)|x(i))k k k 1

(2.21)q(x(i)|x(i)

,Y)k k通常，需要對粒子權(quán)值進(jìn)行歸一化處理，即(i)

w(i)?k

k Nkw(i)Nki1

(2.22)計。序貫重要性采樣算法的流程可以用如下偽代碼描述：[{x(i),w(i)}N

]SIS({x(i),w(i)}N,Y)k k Fori=1:N

1 i1 kq(x(i)|x(i),Y)x(i)；k 0:k1 k kkw(i；kEndFor幾乎不起作用的粒子更新上，使得估計性能下降。通常采用有Neff來衡量粒子權(quán)值的退化程度，即eff N N/(1var(w*(i)eff

(2.23)*(i)

p(x(i)|y)wk k 1:k

(2.24)q(x |q(x |x )k k1 1:k有效粒子數(shù)越小，表明權(quán)值退化越嚴(yán)重。Neff可以近似為1?efN1

(2.25)k(w(i))2ki1在進(jìn)行序貫重要性采樣時，若?ef小于事先設(shè)定的某一閾值，則應(yīng)當(dāng)采取一些措施加(1)選擇合適的重要性概率密度函數(shù)；(2)在序貫重要性采樣之后，采用重采樣方法。重要密度函數(shù)的選擇pxk|xk1作為重要性概率密度函數(shù)。此時，粒子的權(quán)值為k w(i)w(i)k

|x(i))

k 慮最新觀測數(shù)據(jù)所提供的信息，從中抽取的樣本與真實后驗分布產(chǎn)生的樣本存在一定的偏k k {w(k

Doucet等給出的最優(yōu)重要性概率密度函數(shù)為q(x(i)|x(i),y)p(x(i)|x(i),y)k 1 k k 1 kp(y

|x(i),x(i))p(x(i)|x(i)) k k 1 k 1|x p|x

(i)k p(y

|x(i))p(x(i)|x(i)) k k k k1p(y

|x(i))k k1

(2.27)此時，粒子的權(quán)值為k w(i)w(i)k

(i)|x k |x (2.28)以px(i)|x(i),y作為重要性概率密度函數(shù)需要對其直接采樣。x為有限離k 1 k k散狀態(tài)或px(i)|x(i),ypy|x(i))才存在解析解。在實際情況中，構(gòu)造k 1 k k k1從2.4所示。圖2.4 移動粒子至高似然區(qū)域Fig.2.4 Movethesamplesinthepriortoregionsofhighlikelihoodkk1時刻最有前途(預(yù)測似然度大)的粒子擴(kuò)展k時刻[137]，從而生成采樣粒子。與SIR濾波器相比，當(dāng)粒子的似然函數(shù)位于先驗分布的引入輔助變量mk1時刻的粒子列表，應(yīng)用貝葉斯定理，聯(lián)合概率密度函數(shù)p(y

|xm)p(x|xm)wmk k k 1 1生成{x(im(i)}N

的重要性概率密度函數(shù)q(x,m|x

(2.29)k i1

k 0:k1 1:kq(x,m|x ,y)p(y|m)p(x|xm)wm

(2.30)k 0:k1 1:k k k k k1 k1mp(x

或預(yù)測均k kmE{x|xm。

k k k k k1qx|m,y)p(x|xm

，由于k 1:k k k1

(2.31)則有q(m|y)p(y|m)wm

(2.32)1:k k k 1kw(i)為kw(i)wm(i)

p(y|x(i)

)p(xi|xm(i))k k

p(y|x(i))k k k q(x,m|xk

|m(i))k k k

k k k(2.33)采用局部線性化的方法來逼近pxk|xk1,yk)是另一種提高粒子采樣效率的有效方法。擴(kuò)展Kalman粒子濾波與UncentedUKF或者EKF，并將它作為重要性概率密度函數(shù)[138]。另外，利用似然函數(shù)的梯度信息，采用牛頓迭代[139]或均值漂移等方法移動粒子至高似然區(qū)域，也是一種可行的方案，如圖2.5所示。以上這些方法的共同特點(diǎn)是將最新的觀測數(shù)據(jù)融入到系統(tǒng)狀態(tài)的轉(zhuǎn)移過程中，引導(dǎo)粒子到高似然區(qū)密度函數(shù)所需的粒子數(shù)。,N1}ki),}kk ?(i),(i)k k i),?i)k kk圖2.5 結(jié)合均值漂移的粒子濾波算法Fig.2.5 Particlefiltercombinedwithmeanshift重采樣方法Bootstrap的p(?(i)x(i))?(i){?(i),?(i)N更新為{x(i),1/NNk k k k k 1 k 1式(Multinomialresampling)重采樣、殘差重采樣(Residualresampling)、分層重采樣(Stratifiedresampling)與系統(tǒng)重采樣(Systematicresampling)等。殘余重采樣法具有效率高、實現(xiàn)方便的

NiN?(i)，其中

k k k k?(i)N1N?(i)Ni選擇余下的Nk k k的主要過程為

NNi2.6所示。殘余重采樣Ni1Nj,j1,?Nk。生成N[，1]l?k；k 對于每個i，尋找歸一化權(quán)值累計量大于或等于i的最小標(biāo)號mm1

l

i落在區(qū)間[

xm2.6所示。mm1kkx(i經(jīng)重采樣后的個數(shù)為步驟(3)Nimm1kk圖2.6 殘差重采樣Fig.2.6 ResidualResampling重采樣并沒有從根本上解決權(quán)值退化問題。重采樣后的粒子之間不再是統(tǒng)計獨(dú)立關(guān)系，給估計結(jié)果帶來額外的方差。重采樣破壞了序貫重要性采樣算法的并行性，不利于VLSI硬目之間進(jìn)行有效折衷。k1N個權(quán)值為1/Nx(ikk?(i)kk?(i)重新設(shè)置為1/N。k圖2.7 SIR算法示意圖Fig.2.7 SIRalgorithm標(biāo)準(zhǔn)的粒子濾波算法流程為：k0：對于i12,?Np(x)生成采樣粒子{x(i)}N0k1,2?，循環(huán)執(zhí)行以下步驟：

0 k ①重要性采樣：對于i,?N{?(i)k k?(i)k②{?(i)?(i)}{x(i)1/N}；k k kk

N??? k k k退化現(xiàn)象，但重采樣方法也會帶來一些其它的問題。重采樣需要綜合所有的粒子才能實現(xiàn)，法是增加馬爾可夫蒙特卡洛(Markovchainmontecarlo,MCMC)移動步驟[141]卡洛方法(GibbsMetropolis-Hastings采樣等)利用不可約馬爾可夫過程可逆平穩(wěn)分布p?k|kkk|?k的馬爾科夫鏈變換之后，若滿足

k(k|?k)p(?k|k)d?kp(k|k)(2.34)更為有利的位置。qx中生成粒子的具體步驟為：從[0,1]vU[0,1；k k x*px*|x(ik k q(x*)p(x(i)|x*) * *k k ，否則，