粒子濾波理論一看就懂要點(diǎn)

2粒子濾波理論粒子濾波通過(guò)非參數(shù)化的蒙特卡洛(MonteCarlo)模擬方法來(lái)實(shí)現(xiàn)遞推貝葉斯濾波，適用于任何能用狀態(tài)空間模型描述的非線性系統(tǒng)，精度可以逼近最優(yōu)估計(jì)。粒子濾波器具有簡(jiǎn)單、易于實(shí)現(xiàn)等特點(diǎn)，它為分析非線性動(dòng)態(tài)系統(tǒng)提供了一種有效的解決方法，從而引起目標(biāo)跟蹤、信號(hào)處理以及自動(dòng)控制等領(lǐng)域的廣泛關(guān)注。本章首先概述用于求解目標(biāo)狀態(tài)后驗(yàn)概率的貝葉斯濾波理論，隨后介紹具有普遍適用性的粒子濾波器，最后針對(duì)當(dāng)前粒子濾波器存在的粒子多樣性喪失問(wèn)題，提出了一種量子進(jìn)化粒子濾波算法。2.1貝葉斯濾波動(dòng)態(tài)系統(tǒng)的目標(biāo)跟蹤問(wèn)題可以通過(guò)圖2.1所示的狀態(tài)空間模型來(lái)描述。本節(jié)在貝葉斯濾波框架下討論目標(biāo)跟蹤問(wèn)題。圖2.SEQ圖2.\*ARABIC1狀態(tài)空間模型Fig.2.SEQFig._2.\*ARABIC1Statespacemodel在目標(biāo)跟蹤問(wèn)題中，動(dòng)態(tài)系統(tǒng)的狀態(tài)空間模型可描述為MACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r1\hSEQMTChap\hMACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r2\hSEQMTChap\h 其中分別為狀態(tài)轉(zhuǎn)移方程與觀測(cè)方程，為系統(tǒng)狀態(tài)，為觀測(cè)值，為過(guò)程噪聲，為觀測(cè)噪聲。為了描述方便，用與分別表示到時(shí)刻所有的狀態(tài)與觀測(cè)值。在處理目標(biāo)跟蹤問(wèn)題時(shí)，通常假設(shè)目標(biāo)的狀態(tài)轉(zhuǎn)移過(guò)程服從一階馬爾可夫模型，即當(dāng)前時(shí)刻的狀態(tài)只與上一時(shí)刻的狀態(tài)有關(guān)。另外一個(gè)假設(shè)為觀測(cè)值相互獨(dú)立，即觀測(cè)值只與時(shí)刻的狀態(tài)有關(guān)。貝葉斯濾波為非線性系統(tǒng)的狀態(tài)估計(jì)問(wèn)題提供了一種基于概率分布形式的解決方案。貝葉斯濾波將狀態(tài)估計(jì)視為一個(gè)概率推理過(guò)程，即將目標(biāo)狀態(tài)的估計(jì)問(wèn)題轉(zhuǎn)換為利用貝葉斯公式求解后驗(yàn)概率密度或?yàn)V波概率密度，進(jìn)而獲得目標(biāo)狀態(tài)的最優(yōu)估計(jì)。貝葉斯濾波包含預(yù)測(cè)和更新兩個(gè)階段，預(yù)測(cè)過(guò)程利用系統(tǒng)模型預(yù)測(cè)狀態(tài)的先驗(yàn)概率密度，更新過(guò)程則利用最新的測(cè)量值對(duì)先驗(yàn)概率密度進(jìn)行修正，得到后驗(yàn)概率密度。假設(shè)已知時(shí)刻的概率密度函數(shù)為，貝葉斯濾波的具體過(guò)程如下：(1)預(yù)測(cè)過(guò)程，由得到：當(dāng)給定時(shí)，狀態(tài)與相互獨(dú)立，因此上式兩端對(duì)積分，可得Chapman-Komolgorov方程 （？？？？？）(2)更新過(guò)程，由得到：獲取時(shí)刻的測(cè)量后，利用貝葉斯公式對(duì)先驗(yàn)概率密度進(jìn)行更新，得到后驗(yàn)概率假設(shè)只由決定，即因此其中，為歸一化常數(shù)貝葉斯濾波以遞推的形式給出后驗(yàn)(或?yàn)V波)概率密度函數(shù)的最優(yōu)解。目標(biāo)狀態(tài)的最優(yōu)估計(jì)值可由后驗(yàn)(或?yàn)V波)概率密度函數(shù)進(jìn)行計(jì)算。通常根據(jù)極大后驗(yàn)(MAP)準(zhǔn)則或最小均方誤差(MMSE)準(zhǔn)則，將具有極大后驗(yàn)概率密度的狀態(tài)或條件均值作為系統(tǒng)狀態(tài)的估計(jì)值，即波概率密度，如圖2.3所示。令表示一支撐點(diǎn)集，其中為是時(shí)刻第個(gè)粒子的狀態(tài)，其相應(yīng)的權(quán)值為，則后驗(yàn)濾波概率密度可以表示為其中，圖2.SEQ圖2.\*ARABIC3重要性采樣Fig.2.SEQFig._2.\*ARABIC3Importancesampling當(dāng)采樣粒子的數(shù)目很大時(shí)，式(2.14)便可近似逼近真實(shí)的后驗(yàn)概率密度函數(shù)。任意函數(shù)的期望估計(jì)為2.2.2序貫重要性采樣算法在基于重要性采樣的蒙特卡洛模擬方法中，估計(jì)后驗(yàn)濾波概率需要利用所有的觀測(cè)數(shù)據(jù)，每次新的觀測(cè)數(shù)據(jù)來(lái)到都需要重新計(jì)算整個(gè)狀態(tài)序列的重要性權(quán)值。序貫重要性采樣作為粒子濾波的基礎(chǔ)，它將統(tǒng)計(jì)學(xué)中的序貫分析方法應(yīng)用到的蒙特卡洛方法中，從而實(shí)現(xiàn)后驗(yàn)濾波概率密度的遞推估計(jì)。假設(shè)重要性概率密度函數(shù)可以分解為設(shè)系統(tǒng)狀態(tài)是一個(gè)馬爾可夫過(guò)程，且給定系統(tǒng)狀態(tài)下各次觀測(cè)獨(dú)立，則有后驗(yàn)概率密度函數(shù)的遞歸形式可以表示為粒子權(quán)值的遞歸形式可以表示為通常，需要對(duì)粒子權(quán)值進(jìn)行歸一化處理，即序貫重要性采樣算法從重要性概率密度函數(shù)中生成采樣粒子，并隨著測(cè)量值的依次到來(lái)遞推求得相應(yīng)的權(quán)值，最終以粒子加權(quán)和的形式來(lái)描述后驗(yàn)濾波概率密度，進(jìn)而得到狀態(tài)估計(jì)。序貫重要性采樣算法的流程可以用如下偽代碼描述：Fori=1:N(1)時(shí)間更新，根據(jù)重要性參考函數(shù)生成采樣粒子；(2)量測(cè)更新，根據(jù)最新觀測(cè)值計(jì)算粒子權(quán)值；EndFor粒子權(quán)值歸一化，并計(jì)算目標(biāo)狀態(tài)。為了得到正確的狀態(tài)估計(jì)，通常希望粒子權(quán)值的方差盡可能趨近于零。然而，序貫蒙特卡洛模擬方法一般都存在權(quán)值退化問(wèn)題。在實(shí)際計(jì)算中，經(jīng)過(guò)數(shù)次迭代，只有少數(shù)粒子的權(quán)值較大，其余粒子的權(quán)值可忽略不計(jì)。粒子權(quán)值的方差隨著時(shí)間增大，狀態(tài)空間中的有效粒子數(shù)較少。隨著無(wú)效采樣粒子數(shù)目的增加，使得大量的計(jì)算浪費(fèi)在對(duì)估計(jì)后驗(yàn)濾波概率分布幾乎不起作用的粒子更新上，使得估計(jì)性能下降。通常采用有效粒子數(shù)來(lái)衡量粒子權(quán)值的退化程度，即有效粒子數(shù)越小，表明權(quán)值退化越嚴(yán)重。在實(shí)際計(jì)算中，有效粒子數(shù)可以近似為在進(jìn)行序貫重要性采樣時(shí)，若小于事先設(shè)定的某一閾值，則應(yīng)當(dāng)采取一些措施加以控制。克服序貫重要性采樣算法權(quán)值退化現(xiàn)象最直接的方法是增加粒子數(shù)，而這會(huì)造成計(jì)算量的相應(yīng)增加，影響計(jì)算的實(shí)時(shí)性。因此，一般采用以下兩種途徑：(1)選擇合適的重要性概率密度函數(shù)；(2)在序貫重要性采樣之后，采用重采樣方法。2.2.3重要密度函數(shù)的選擇重要性概率密度函數(shù)的選擇對(duì)粒子濾波的性能有很大影響，在設(shè)計(jì)與實(shí)現(xiàn)粒子濾波器的過(guò)程中十分重要。在工程應(yīng)用中，通常選取狀態(tài)變量的轉(zhuǎn)移概率密度函數(shù)作為重要性概率密度函數(shù)。此時(shí)，粒子的權(quán)值為轉(zhuǎn)移概率的形式簡(jiǎn)單且易于實(shí)現(xiàn)，在觀測(cè)精度不高的場(chǎng)合，將其作為重要性概率密度函數(shù)可以取得較好的濾波效果。然而，采用轉(zhuǎn)移概率密度函數(shù)作為重要性概率密度函數(shù)沒有考慮最新觀測(cè)數(shù)據(jù)所提供的信息，從中抽取的樣本與真實(shí)后驗(yàn)分布產(chǎn)生的樣本存在一定的偏差，特別是當(dāng)觀測(cè)模型具有較高的精度或預(yù)測(cè)先驗(yàn)與似然函數(shù)之間重疊部分較少時(shí)，這種偏差尤為明顯。選擇重要性概率密度函數(shù)的一個(gè)標(biāo)準(zhǔn)是使得粒子權(quán)值的方差最小。Doucet等給出的最優(yōu)重要性概率密度函數(shù)為此時(shí)，粒子的權(quán)值為以作為重要性概率密度函數(shù)需要對(duì)其直接采樣。此外，只有在為有限離散狀態(tài)或?yàn)楦咚购瘮?shù)時(shí)，才存在解析解。在實(shí)際情況中，構(gòu)造最優(yōu)重要性概率密度函數(shù)的困難程度與直接從后驗(yàn)概率分布中抽取樣本的困難程度等同。從最優(yōu)重要性概率密度函數(shù)的表達(dá)形式來(lái)看，產(chǎn)生下一個(gè)預(yù)測(cè)粒子依賴于已有的粒子和最新的觀測(cè)數(shù)據(jù)，這對(duì)于設(shè)計(jì)重要性概率密度函數(shù)具有重要的指導(dǎo)作用，即應(yīng)該有效利用最新的觀測(cè)信息，在易于采樣實(shí)現(xiàn)的基礎(chǔ)上，將更多的粒子移動(dòng)到似然函數(shù)值較高的區(qū)域，如圖2.4所示。圖2.SEQ圖2.\*ARABIC4移動(dòng)粒子至高似然區(qū)域Fig.2.SEQFig._2.\*ARABIC4Movethesamplesinthepriortoregionsofhighlikelihood輔助粒子濾波算法利用時(shí)刻的信息，將時(shí)刻最有前途(預(yù)測(cè)似然度大)的粒子擴(kuò)展到時(shí)刻ADDINEN.CITE<EndNote><Cite><RecNum>142</RecNum><record><rec-number>142</rec-number><ref-typename="JournalArticle">17</ref-type><contributors></contributors><titles><title>PittM,ShephardN.Filteringviasimulation:auxillaryparticlefilter.JournalofAmericanStatisticalAssociation,1999,94:590-599</title></titles><dates></dates><urls></urls></record></Cite></EndNote>[137]，從而生成采樣粒子。與SIR濾波器相比，當(dāng)粒子的似然函數(shù)位于先驗(yàn)分布的尾部或似然函數(shù)形狀比較狹窄時(shí)，輔助粒子濾波能夠得到更精確的估計(jì)結(jié)果。輔助粒子濾波引入輔助變量來(lái)表示時(shí)刻的粒子列表，應(yīng)用貝葉斯定理，聯(lián)合概率密度函數(shù)可以描述為生成的重要性概率密度函數(shù)為其中為由預(yù)測(cè)出的與相關(guān)的特征，可以是采樣值或預(yù)測(cè)均值。定義，由于則有此時(shí)，粒子權(quán)值為采用局部線性化的方法來(lái)逼近是另一種提高粒子采樣效率的有效方法。擴(kuò)展Kalman粒子濾波與Uncented粒子濾波算法在濾波的每一步迭代過(guò)程中，首先利用最新觀測(cè)值，采用UKF或者EKF對(duì)各個(gè)粒子進(jìn)行更新，得到隨機(jī)變量經(jīng)非線性變換后的均值和方差，并將它作為重要性概率密度函數(shù)ADDINEN.CITE<EndNote><Cite><RecNum>144</RecNum><record><rec-number>144</rec-number><ref-typename="JournalArticle">17</ref-type><contributors></contributors><titles><title>vanderMerweR,A.DoucetA,deFreitasJFG,WanE.TheUnscentedParticleFilter.In:LeenTK,DietterichTG,TrespV,eds.AdvancesinNeuralInformationProcessingSystems.MA,USA:MITPress,2000</title></titles><dates></dates><urls></urls></record></Cite></EndNote>[138]。另外，利用似然函數(shù)的梯度信息，采用牛頓迭代ADDINEN.CITE<EndNote><Cite><RecNum>146</RecNum><record><rec-number>146</rec-number><ref-typename="JournalArticle">17</ref-type><contributors></contributors><titles><title>ChenZ,HuberK.Robustparticlefilterswithapplicationsintrackingandcommunications.TechnologyReport,AdaptiveSystemsLab,McMasterUniversity,2003</title></titles><dates></dates><urls></urls></record></Cite></EndNote>[139]或均值漂移ADDINEN.CITE<EndNote><Cite><RecNum>147</RecNum><record><rec-number>147</rec-number><ref-typename="JournalArticle">17</ref-type><contributors></contributors><titles><title>ShanC,WeiY,TanT.Realtimehandtrackingbycombiningparticlefilteringandmeanshift.IEEEInternationalConferenceonAutomaticFaceandGestureRecognition,Seoul,Korea,2004:669-674</title></titles><dates></dates><urls></urls></record></Cite></EndNote>[140]等方法移動(dòng)粒子至高似然區(qū)域，也是一種可行的方案，如圖2.5所示。以上這些方法的共同特點(diǎn)是將最新的觀測(cè)數(shù)據(jù)融入到系統(tǒng)狀態(tài)的轉(zhuǎn)移過(guò)程中，引導(dǎo)粒子到高似然區(qū)域，由此產(chǎn)生的預(yù)測(cè)粒子可較好地服從狀態(tài)的后驗(yàn)概率分布，從而有效地減少描述后驗(yàn)概率密度函數(shù)所需的粒子數(shù)。圖2.SEQ圖2.\*ARABIC5結(jié)合均值漂移的粒子濾波算法Fig.2.SEQFig._2.\*ARABIC5Particlefiltercombinedwithmeanshift2.2.4重采樣方法針對(duì)序貫重要性采樣算法存在的權(quán)值退化現(xiàn)象，Gordon等提出了一種名為Bootstrap的粒子濾波算法。該算法在每步迭代過(guò)程中，根據(jù)粒子權(quán)值對(duì)離散粒子進(jìn)行重采樣，在一定程度上克服了這個(gè)問(wèn)題。重采樣方法舍棄權(quán)值較小的粒子，代之以權(quán)值較大的粒子。重采樣過(guò)程在滿足條件下，將粒子集合更新為。重采樣策略包括固定時(shí)間間隔重采樣與根據(jù)粒子權(quán)值進(jìn)行的動(dòng)態(tài)重采樣。動(dòng)態(tài)重采樣通常根據(jù)當(dāng)前的有效粒子數(shù)或最大與最小權(quán)值比來(lái)判斷是否需要進(jìn)行重采樣。常用的重采樣方法包括多項(xiàng)式(Multinomialresampling)重采樣、殘差重采樣(Residualresampling)、分層重采樣(Stratifiedresampling)與系統(tǒng)重采樣(Systematicresampling)等。殘余重采樣法具有效率高、實(shí)現(xiàn)方便的特點(diǎn)。設(shè)，其中為取整操作。殘余重采樣采用新的權(quán)值選擇余下的個(gè)粒子，如圖2.6所示。殘余重采樣的主要過(guò)程為(1)計(jì)算剩余粒子的權(quán)值累計(jì)量。(2)生成在個(gè)[0，1]區(qū)間均勻分布的隨機(jī)數(shù)；(3)對(duì)于每個(gè)，尋找歸一化權(quán)值累計(jì)量大于或等于的最小標(biāo)號(hào)，即。當(dāng)落在區(qū)間時(shí)，被復(fù)制一次，如圖2.6所示。這樣，每個(gè)粒子經(jīng)重采樣后的個(gè)數(shù)為步驟(3)中被選擇的若干粒子數(shù)目與之和。圖2.SEQ圖2.\*ARABIC6殘差重采樣Fig.2.SEQFig._2.\*ARABIC6ResidualResampling重采樣并沒有從根本上解決權(quán)值退化問(wèn)題。重采樣后的粒子之間不再是統(tǒng)計(jì)獨(dú)立關(guān)系，給估計(jì)結(jié)果帶來(lái)額外的方差。重采樣破壞了序貫重要性采樣算法的并行性，不利于VLSI硬件實(shí)現(xiàn)。另外，頻繁的重采樣會(huì)降低對(duì)測(cè)量數(shù)據(jù)中野值的魯棒性。由于重采樣后的粒子集中包含了多個(gè)重復(fù)的粒子，重采樣過(guò)程可能導(dǎo)致粒子多樣性的喪失，此類問(wèn)題在噪聲較小的環(huán)境下更加嚴(yán)重。因此，一個(gè)好的重采樣算法應(yīng)該在增加粒子多樣性和減少權(quán)值較小的粒子數(shù)目之間進(jìn)行有效折衷。圖2.7為粒子濾波算法的示意圖，該圖描述了粒子濾波算法包含的時(shí)間更新、觀測(cè)更新和重采樣三個(gè)步驟。時(shí)刻的先驗(yàn)概率由個(gè)權(quán)值為的粒子近似表示。在時(shí)間更新過(guò)程中，通過(guò)系統(tǒng)狀態(tài)轉(zhuǎn)移方程預(yù)測(cè)每個(gè)粒子在時(shí)刻的狀態(tài)。經(jīng)過(guò)觀測(cè)值后，更新粒子權(quán)值。重采樣過(guò)程舍棄權(quán)值較小的粒子，代之以權(quán)值較大的粒子，粒子的權(quán)值被重新設(shè)置為。圖2.SEQ圖2.\*ARABIC7SIR算法示意圖Fig.2.SEQFig._2.\*ARABIC7SIRalgorithm標(biāo)準(zhǔn)的粒子濾波算法流程為：(1)粒子集初始化，：對(duì)于，由先驗(yàn)生成采樣粒子(2)對(duì)于，循環(huán)執(zhí)行以下步驟：①重要性采樣：對(duì)于，從重要性概率密度中生成采樣粒子，計(jì)算粒子權(quán)值，并進(jìn)行歸一化；②重采樣：對(duì)粒子集進(jìn)行重采樣，重采樣后的粒子集為；③輸出：計(jì)算時(shí)刻的狀態(tài)估計(jì)值：。粒子濾波中的權(quán)值退化問(wèn)題是不可避免的。雖然重采樣方法可以在一定程度上緩解權(quán)值退化現(xiàn)象，但重采樣方法也會(huì)帶來(lái)一些其它的問(wèn)題。重采樣需要綜合所有的粒子才能實(shí)現(xiàn)，限制了粒子濾波的并行計(jì)算。另外，根據(jù)重采樣的原則，粒子權(quán)值較大的粒子必然會(huì)更多的被選中復(fù)制，經(jīng)過(guò)若干步迭代后，必然導(dǎo)致相同的粒子越來(lái)越多，粒子將缺乏多樣性，可能出現(xiàn)粒子退化現(xiàn)象，從而使?fàn)顟B(tài)估計(jì)產(chǎn)生較大偏差。針對(duì)粒子退化問(wèn)題，一個(gè)有效的解決方法是增加馬爾可夫蒙特卡洛(Markovchainmontecarlo,MCMC)移動(dòng)步驟ADDINEN.CITE<EndNote><Cite><RecNum>148</RecNum><record><rec-number>148</rec-number><ref-typename="JournalArticle">17</ref-type><contributors></contributors><titles><title>GilksW,BerzuiniC.Followingamovingtarget-BayesianinferencefordynamicBayesianmodels.JournaloftheRoyalStatisticalSociety,SeriesB,2001,63(1):127-146</title></titles><dates></dates><urls></urls></record></Cite></EndNote>[141]。馬爾可夫鏈蒙特卡洛方法(如Gibbs采樣、Metropolis-Hastings采樣等)利用不可約馬爾可夫過(guò)程可逆平穩(wěn)分布的性質(zhì)，將馬爾可夫過(guò)程的平穩(wěn)分布視為目標(biāo)分布，通過(guò)構(gòu)造馬爾可夫鏈產(chǎn)生來(lái)自目標(biāo)分布的粒子。粒子退化問(wèn)題是由于重采樣使得粒子過(guò)分集中在某些狀態(tài)上而導(dǎo)致的，對(duì)重采樣后的粒子進(jìn)行馬爾可夫跳轉(zhuǎn)可以提高粒子群的多樣性，同時(shí)保證