1、2 粒子濾波理論粒子濾波通過(guò)非參數(shù)化的蒙特卡洛(Monte Carlo)模擬方法來(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、圖2.1 狀態(tài)空間模型 Fig. 2.1 State space model在目標(biāo)跟蹤問(wèn)題中，動(dòng)態(tài)系統(tǒng)的狀態(tài)空間模型可描述為xk=f(xk-1)+uk-1yk=h(xk)+vk(2.1)其中f(),h()分別為狀態(tài)轉(zhuǎn)移方程與觀測(cè)方程，xk為系統(tǒng)狀態(tài)，yk為觀測(cè)值，uk為過(guò)程vk為觀測(cè)噪聲。噪聲，為了描述方便，用Xk=x0:k=x0,x1, ,xk與Yk=y1:k=y1, ,yk分別表示0到k時(shí)刻所有的狀態(tài)與觀測(cè)值。在處理目標(biāo)跟蹤問(wèn)題時(shí)，通常假設(shè)目標(biāo)的狀態(tài)轉(zhuǎn)移過(guò)程服從一階馬爾可夫模型，即當(dāng)前時(shí)刻的狀態(tài)xk只與上一時(shí)刻的狀態(tài)xk-1有關(guān)。另外一個(gè)假設(shè)為觀測(cè)值相互獨(dú)立，即觀測(cè)值yk只與k時(shí)刻的狀態(tài)x

3、k有關(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)概率密度p(Xk|Yk)或?yàn)V波概率密度p(xk|Yk)，進(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è)已知k-1時(shí)刻的概率密度函數(shù)為p(xk-1|Yk-1)，貝葉斯濾波的具體過(guò)程如下： (1) 預(yù)測(cè)過(guò)程，由p(xk-1|Yk-1)得到p(xk|Yk-1)：p(xk,xk-1|Yk-1)=p(x

4、k|xk-1,Yk-1)p(xk-1|Yk-1) (2.2)當(dāng)給定xk-1時(shí)，狀態(tài)xk與Yk-1相互獨(dú)立，因此p(xk,xk-1|Yk-1)=p(xk|xk-1)p(xk-1|Yk-1) (2.3)上式兩端對(duì)xk-1積分，可得Chapman-Komolgorov方程p(xk|Yk-1)=p(xk|xk-1)p(xk-1|Yk-1)dxk-1(2.4)(2) 更新過(guò)程，由p(xk|Yk-1)得到p(xk|Yk)：獲取k時(shí)刻的測(cè)量yk后，利用貝葉斯公式對(duì)先驗(yàn)概率密度進(jìn)行更新，得到后驗(yàn)概率p(yk|xk,Yk-1)p(xk|Yk-1)p(yk|Yk-1)p(xk|Yk)=(2.5)假設(shè)yk只由xk決

5、定，即p(yk|xk,Yk-1)=p(yk|xk) (2.6)因此p(xk|Yk)=p(yk|xk)p(xk|Yk-1)p(yk|Yk-1)(2.7)其中，p(yk|Yk-1)為歸一化常數(shù)p(yk|Yk-1)=p(yk|xk)p(xk|Yk-1)dxk (2.8)貝葉斯濾波以遞推的形式給出后驗(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ì)值，即kMAPx =argminp(xk|Yk) (2.9)xkSE x ) d (2.10)

6、kM Mx =fEx(Y)=|fx(pkx)(kY| kkkk貝葉斯濾波需要進(jìn)行積分運(yùn)算，除了一些特殊的系統(tǒng)模型（如線性高斯系統(tǒng)，有限狀態(tài)的離散系統(tǒng)）之外，對(duì)于一般的非線性、非高斯系統(tǒng)，貝葉斯濾波很難得到后驗(yàn)概率的封閉解析式。因此，現(xiàn)有的非線性濾波器多采用近似的計(jì)算方法解決積分問(wèn)題，以此來(lái)獲取估計(jì)的次優(yōu)解。在系統(tǒng)的非線性模型可由在當(dāng)前狀態(tài)展開的線性模型有限近似的前提下，基于一階或二階Taylor級(jí)數(shù)展開的擴(kuò)展Kalman濾波得到廣泛應(yīng)用119。在一般情況下，逼近概率密度函數(shù)比逼近非線性函數(shù)容易實(shí)現(xiàn)。據(jù)此，Julier與Uhlmann提出一種Unscented Kalman濾波器，通過(guò)選定的si

7、gma點(diǎn)來(lái)精確估計(jì)隨機(jī)變量經(jīng)非線性變換后的均值和方差，從而更好的近似狀態(tài)的概率密度函數(shù)，其理論估計(jì)精度優(yōu)于擴(kuò)展Kalman濾波一中方案便是基于蒙特卡洛模擬的粒子濾波器。 120。獲取次優(yōu)解的另外2.2 粒子濾波早在20世紀(jì)50年代，Hammersley便采用基于序貫重要性采樣(Sequential importance sampling,SIS)的蒙特卡洛方法解決統(tǒng)計(jì)學(xué)問(wèn)題121。20世紀(jì)60年代后期，Handschin與Mayne使用序貫蒙特卡洛方法解決自動(dòng)控制領(lǐng)域的相關(guān)問(wèn)題122。20世紀(jì)70年代，Handschin、Akashi以及Zaritskii等學(xué)者的一系列研究工作使得序貫蒙特卡洛

8、方法得到進(jìn)一步發(fā)展126。限于當(dāng)時(shí)的計(jì)算能力以及算法本身存在的權(quán)值退化問(wèn)題，序貫重要性采樣算法沒(méi)有受到足夠重視，在隨后較長(zhǎng)一段時(shí)間內(nèi)進(jìn)展較為緩慢。直到20世紀(jì)80年代末，計(jì)算機(jī)處理能力的巨大進(jìn)展使得序貫蒙特卡洛方法重新受到關(guān)注。Tanizaki、Geweke等采用基于重要性采樣的蒙特卡洛方法成功解決了一系列高維積分問(wèn)題127-130。Smith與Gelfand提出的采樣-重采樣思想為Bayesian推理提供了一種易于實(shí)現(xiàn)的計(jì)算策略131。隨后，Smith與Gordon等人合作，于20世紀(jì)90年代初將重采樣(Resampling)步驟引入到粒子濾波中，在一定程度上解決了序貫重要性采樣的權(quán)值退化問(wèn)

9、題，并由此產(chǎn)生了第一個(gè)可實(shí)現(xiàn)的SIR(Sampling importance resampling)粒子濾波算法(Bootstrap濾波)132，從而掀起粒子濾波的研究熱潮。美國(guó)海軍集成水下監(jiān)控系統(tǒng)中的Nodestar便是粒子濾波應(yīng)用的一個(gè)實(shí)例。進(jìn)入21世紀(jì)，粒子濾波器成為一個(gè)非常活躍的研究領(lǐng)域，Doucet、Liu、Arulampalam等對(duì)粒子濾波的研究作了精彩的總結(jié)，IEEE出版的論文集“Sequential Monte Carlo Methods in Practice”對(duì)粒子濾波器進(jìn)行了詳細(xì)介紹136。 133-135123124, 125蒙特卡洛模擬是一種利用隨機(jī)數(shù)求解物理和數(shù)學(xué)問(wèn)

10、題的計(jì)算方法，又稱為計(jì)算機(jī)隨機(jī)模擬方法。該方法源于第一次世界大戰(zhàn)期間美國(guó)研制原子彈的曼哈頓計(jì)劃，著名數(shù)學(xué)家馮 諾伊曼作為該計(jì)劃的主持人之一，用馳名世界的賭城，摩納哥的蒙特卡洛來(lái)命名這種方法。蒙特卡洛模擬方法利用所求狀態(tài)空間中大量的樣本點(diǎn)來(lái)近似逼近待估計(jì)變量的后驗(yàn)概率分布，如圖2.2所示，從而將積分問(wèn)題轉(zhuǎn)換為有限樣本點(diǎn)的求和問(wèn)題。粒子濾波算法的核心思想便是利用一系列隨機(jī)樣本的加權(quán)和表示后驗(yàn)概率密度，通過(guò)求和來(lái)近似積分操作。假設(shè)可以從(i)后驗(yàn)概率密度p(xk|Yk)中抽取N個(gè)獨(dú)立同分布的隨機(jī)樣本xk，i=1, ,N，則有p(xk|Yk)1NN(xi=1k(i)-xk) (2.11)這里xk為連續(xù)

11、變量，(x-xk)為單位沖激函數(shù)(狄拉克函數(shù))，即(x-xk)=0,xxk，且(x)dx=1。當(dāng)xk為離散變量時(shí)，后驗(yàn)概率分布P(xk|Yk)可近似逼近為1NNP(xk|Yk)(xi=1k(i)-xk) (2.12)其中，(xk-xk(i)=1,xk=xk(i); (xk-xk(i)=0,xkxk(i)。圖2.2 經(jīng)驗(yàn)概率分布函數(shù)Fig. 2.2 Empirical probability distribution function(i)設(shè)xk為從后驗(yàn)概率密度函數(shù)p(xk|Yk)中獲取的采樣粒子，則任意函數(shù)f(xk)的期望估計(jì)可以用求和方式逼近，即Ef(xk)|Yk=f(xk)p(xk|Yk)

12、dxk=1NNi=1f(xk) (2.13)(i)蒙特卡洛方法一般可以歸納為以下三個(gè)步驟：(1)構(gòu)造概率模型。對(duì)于本身具有隨機(jī)性質(zhì)的問(wèn)題，主要工作是正確地描述和模擬這個(gè)概率過(guò)程。對(duì)于確定性問(wèn)題，比如計(jì)算定積分、求解線性方程組、偏微分方程等問(wèn)題，采用蒙特卡洛方法求解需要事先構(gòu)造一個(gè)人為的概率過(guò)程，將它的某些參量視為問(wèn)題的解。(2)從指定概率分布中采樣。產(chǎn)生服從己知概率分布的隨機(jī)變量是實(shí)現(xiàn)蒙特卡洛方法模擬試驗(yàn)的關(guān)鍵步驟。 (3)建立各種估計(jì)量的估計(jì)。一般說(shuō)來(lái)，構(gòu)造出概率模型并能從中抽樣后，便可進(jìn)行現(xiàn)模擬試驗(yàn)。隨后，就要確定一個(gè)隨機(jī)變量，將其作為待求解問(wèn)題的解進(jìn)行估計(jì)。 在實(shí)際計(jì)算中，通常無(wú)法直接從

13、后驗(yàn)概率分布中采樣，如何得到服從后驗(yàn)概率分布的隨機(jī)樣本是蒙特卡洛方法中基本的問(wèn)題之一。重要性采樣法引入一個(gè)已知的、容易采樣的重要性概率密度函數(shù)q(xk|Yk)，從中生成采樣粒子，利用這些隨機(jī)樣本的加權(quán)和來(lái)逼近后驗(yàn)濾波概率密度p(xk|Yk)，如圖2.3所示。令xk(i),wk(i),i=1, .N表示一支撐點(diǎn)集，其中xk(i)為是k時(shí)刻第i個(gè)粒子的狀態(tài)，其相應(yīng)的權(quán)值為wk(i)，則后驗(yàn)濾波概率密度可以表示為Np(xk|Yk)=其中，wi=1(i)kx(k-xki() (2.14)w(i)kp(xk|Yk)q(x(i)k(i)|Yk)(2.15)圖2.3 重要性采樣 Fig. 2.3 Impor

14、tance sampling當(dāng)采樣粒子的數(shù)目很大時(shí)，式(2.14)便可近似逼近真實(shí)的后驗(yàn)概率密度函數(shù)。任意函數(shù)f(xk)的期望估計(jì)為Ef(xk)|Yk=1NNi=1f(x(i)k)p(xk|Yk)q(xk|Yk)(i)(i)=1NNi=1f(xk)wk (2.16)(i)(i)在基于重要性采樣的蒙特卡洛模擬方法中，估計(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ù)q(x0:k|y1:k)可以分解為q(x0

15、:k|y1:k)=q(x0:k-1|y1:k-1)q(xk|x0:k-1,y1:k) (2.17)設(shè)系統(tǒng)狀態(tài)是一個(gè)馬爾可夫過(guò)程，且給定系統(tǒng)狀態(tài)下各次觀測(cè)獨(dú)立，則有kp(x0:k)=p(x0)p(xi|xi-1) (2.18)i=1kp(y1:k|x1:k)=p(yi|xi) (2.19)i=1后驗(yàn)概率密度函數(shù)的遞歸形式可以表示為p(x0:k|Yk)=p(yk|x0:k,Yk-1)p(x0:k|Yk-1)p(yk|Yk-1)p)x(kx|=p(yk|x0:kY,-k10-:kY1-,kp1x)Y|-(0kY:-1|k1)=p(yk|Yk-1)p(yk|xk)px(kx|k-1p)x0k(:-p(

16、yk|Yk-1)1k-1)(2.20)粒子權(quán)值wk(i)的遞歸形式可以表示為w(i)kp(x0:k|Yk)q(x(i)0:k(i)|Yk)(i)=p(yk|xk)p(xkq(xk(i)(i)(i)|-1xki()p0(:-xk1i()1i()|-kY11|0x:k-1,Y)q(0x-k:k(i)(i)(i)|-Yk)=w(i)k-1p(yk|xk)p(xk|xk-1)q(x(i)k|x(i)0:k-1,Yk)(2.21)通常，需要對(duì)粒子權(quán)值進(jìn)行歸一化處理，即w(i)k=wkN(i)(2.22)(i)kwi=1序貫重要性采樣算法從重要性概率密度函數(shù)中生成采樣粒子，并隨著測(cè)量值的依次到來(lái)遞推求得相

17、應(yīng)的權(quán)值，最終以粒子加權(quán)和的形式來(lái)描述后驗(yàn)濾波概率密度，進(jìn)而得到狀態(tài)估計(jì)。序貫重要性采樣算法的流程可以用如下偽代碼描述：xk,wki=1=SIS(xk-1,wk-1i=1,Yk)(i)(i)N(i)(i)NFor i=1:N(i)(i)(i)(1)時(shí)間更新，根據(jù)重要性參考函數(shù)q(xk|x0:k-1,Yk)生成采樣粒子xk；(2)量測(cè)更新，根據(jù)最新觀測(cè)值計(jì)算粒子權(quán)值wk； End For粒子權(quán)值歸一化，并計(jì)算目標(biāo)狀態(tài)。為了得到正確的狀態(tài)估計(jì)，通常希望粒子權(quán)值的方差盡可能趨近于零。然而，序貫蒙特(i)卡洛模擬方法一般都存在權(quán)值退化問(wèn)題。在實(shí)際計(jì)算中，經(jīng)過(guò)數(shù)次迭代，只有少數(shù)粒子的權(quán)值較大，其余粒子的

18、權(quán)值可忽略不計(jì)。粒子權(quán)值的方差隨著時(shí)間增大，狀態(tài)空間中的有效粒子數(shù)較少。隨著無(wú)效采樣粒子數(shù)目的增加，使得大量的計(jì)算浪費(fèi)在對(duì)估計(jì)后驗(yàn)濾波概率分布幾乎不起作用的粒子更新上，使得估計(jì)性能下降。通常采用有效粒子數(shù)Neff來(lái)衡量粒子權(quán)值的退化程度，即Neff=N/(1+var(wk) (2.23)p(xk|y1:k)q(x(i)k(i)*(i)w*(i)k=|x(i)k-1,y1:k)(2.24)有效粒子數(shù)越小，表明權(quán)值退化越嚴(yán)重。在實(shí)際計(jì)算中，有效粒子數(shù)Neff可以近似為Neff1N(2.25)(i)k(wi=1)2小于事先設(shè)定的某一閾值，則應(yīng)當(dāng)采取一些措施加在進(jìn)行序貫重要性采樣時(shí)，若Neff以控制。

19、克服序貫重要性采樣算法權(quán)值退化現(xiàn)象最直接的方法是增加粒子數(shù)，而這會(huì)造成計(jì)算量的相應(yīng)增加，影響計(jì)算的實(shí)時(shí)性。因此，一般采用以下兩種途徑：(1)選擇合適的重要性概率密度函數(shù)；(2)在序貫重要性采樣之后，采用重采樣方法。重要性概率密度函數(shù)的選擇對(duì)粒子濾波的性能有很大影響，在設(shè)計(jì)與實(shí)現(xiàn)粒子濾波器的過(guò)程中十分重要。在工程應(yīng)用中，通常選取狀態(tài)變量的轉(zhuǎn)移概率密度函數(shù)p(xk|xk-1)作為重要性概率密度函數(shù)。此時(shí)，粒子的權(quán)值為wk=wk-1p(yk|xk) (2.26)(i)(i)(i)轉(zhuǎn)移概率的形式簡(jiǎn)單且易于實(shí)現(xiàn)，在觀測(cè)精度不高的場(chǎng)合，將其作為重要性概率密度函數(shù)可以取得較好的濾波效果。然而，采用轉(zhuǎn)移概率密

20、度函數(shù)作為重要性概率密度函數(shù)沒(méi)有考慮最新觀測(cè)數(shù)據(jù)所提供的信息，從中抽取的樣本與真實(shí)后驗(yàn)分布產(chǎn)生的樣本存在一定的偏差，特別是當(dāng)觀測(cè)模型具有較高的精度或預(yù)測(cè)先驗(yàn)與似然函數(shù)之間重疊部分較少時(shí)，這種偏差尤為明顯。(i)N選擇重要性概率密度函數(shù)的一個(gè)標(biāo)準(zhǔn)是使得粒子權(quán)值wki=1的方差最小。Doucet等給出的最優(yōu)重要性概率密度函數(shù)為q(xk|xk-1,yk)=p(xk|xk-1,yk)=(i)(i)(i)(i)p(yk|xk,xk-1)p(xk|xk-1)(i)(i)(i)(i)p(yk|xk-1)(i)=p(yk|xk)p(xk|xk-1)p(yk|xk-1)(i)(i)(i)(i)(2.27)此時(shí)，

21、粒子的權(quán)值為wk=wk-1p(yk|xk-1) (2.28)(i)(i)(i)以p(xk(i)|xk(i-)1,yk)作為重要性概率密度函數(shù)需要對(duì)其直接采樣。此外，只有在xk為有限離散狀態(tài)或p(xk(i)|xk(i-)1,yk)為高斯函數(shù)時(shí)，p(yk|xk(i-)1)才存在解析解。在實(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ù)值

22、較高的區(qū)域，如圖2.4所示。圖2.4 移動(dòng)粒子至高似然區(qū)域Fig. 2.4 Move the samples in the prior to regions of high likelihood輔助粒子濾波算法利用k時(shí)刻的信息，將k-1時(shí)刻最有前途(預(yù)測(cè)似然度大)的粒子擴(kuò)展到k時(shí)刻137，從而生成采樣粒子。與SIR濾波器相比，當(dāng)粒子的似然函數(shù)位于先驗(yàn)分布的尾部或似然函數(shù)形狀比較狹窄時(shí)，輔助粒子濾波能夠得到更精確的估計(jì)結(jié)果。輔助粒子濾波引入輔助變量m來(lái)表示k-1時(shí)刻的粒子列表，應(yīng)用貝葉斯定理，聯(lián)合概率密度函數(shù)p(xk,m|y1:k)可以描述為p(xk,m|y1:k)p(yk|xk)p(xk,m|

23、y1:k-1)=p(yk|xk)p(xt|m,y1:k-1)p(m|y1:k-1)mmm=p(yk|xk)p(xk|xk-1)wk-1 (2.29)生成xk,m(i)(i)i=1的重要性概率密度函數(shù)q(xk,m|x0:k-1,y1:k)為q(xk,m|x0:k-1,y1:k)p(yk|k)p(xk|xk-1)wk-1 (2.30)(i)NmmmNm其中k為由xk-1i=1預(yù)測(cè)出的與xk相關(guān)的特征，可以是采樣值k p(xk|xk-1)或預(yù)測(cè)均mm值km=Exk|xkm-1。定義q(xk|m,y1:k)=p(xk|xkm-1)，由于q(xk,m|y1:k)=q(xk|m,y1:k)q(m|y1:k

24、) (2.31)則有q(m|y1:k)=p(yk|k)wk-1 (2.32)mm此時(shí)，粒子權(quán)值wk(i)為(i)im(i)ww(i)kmk(i)p(yk|xk)p(xk|xkm)q(xk,m|x0:k-1,yk)=p(yk|xk)p(yk|mk(i)(i)(2.33)采用局部線性化的方法來(lái)逼近p(xk|xk-1,yk)是另一種提高粒子采樣效率的有效方法。擴(kuò)展Kalman粒子濾波與Uncented粒子濾波算法在濾波的每一步迭代過(guò)程中，首先利用最新觀測(cè)值，采用UKF或者EKF對(duì)各個(gè)粒子進(jìn)行更新，得到隨機(jī)變量經(jīng)非線性變換后的均值和方差，并將它作為重要性概率密度函數(shù)。另外，利用似然函數(shù)的梯度信息，采用

25、牛頓迭代或均值漂移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ù)。138139(i)-1xk,N-1(i) kx,N-1(i)(i) kx,wk(i)(i) k kx,w(i)xk,N-1圖2.5 結(jié)合均值漂移的粒子濾波算法 Fig. 2.5 Particle filter combined with mean shift針對(duì)序貫重要性采樣算法存在的權(quán)值退化現(xiàn)象，Gordon等提出了一種

26、名為Bootstrap的粒子濾波算法。該算法在每步迭代過(guò)程中，根據(jù)粒子權(quán)值對(duì)離散粒子進(jìn)行重采樣，在一定程度上克服了這個(gè)問(wèn)題。重采樣方法舍棄權(quán)值較小的粒子，代之以權(quán)值較大的粒子。重采樣過(guò)(i)(i)(i)(i)N k k(i)條件下，將粒子集合x k k(i)1N更新為xk程在滿足p(x=xk)=w,w,1/N1。重采樣策略包括固定時(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)式(Multinomial resampling)重采樣、殘差重采樣(Residual resampling)、分層重采

27、樣(Stratifiedresampling)與系統(tǒng)重采樣(Systematic resampling)等。殘余重采樣法具有效率高、實(shí)現(xiàn)方便的(i)特點(diǎn)。設(shè)Ni= k，其中Nw 為取整操作。殘余重采樣采用新的權(quán)值w*i(k)=N-k(1w-Ni(k)N)選擇余下的Nk=N-Ni個(gè)粒子，如圖2.6所示。殘余重采樣ii=1N的主要過(guò)程為(1) 計(jì)算剩余粒子的權(quán)值累計(jì)量j,j=1, ,Nk 。 (2) 生成Nk在個(gè)0，1區(qū)間均勻分布的隨機(jī)數(shù)ll=k1 ；ii(3) 對(duì)于每個(gè)，尋找歸一化權(quán)值累計(jì)量大于或等于的最小標(biāo)號(hào)m，即Nm-1<<m。當(dāng)落在區(qū)間m-1,m時(shí)，xk被復(fù)制一次，如圖2.6所

28、示。lim這樣，每個(gè)粒子xk經(jīng)重采樣后的個(gè)數(shù)為步驟(3)中被選擇的若干粒子數(shù)目與N之和。i(i)圖2.6 殘差重采樣 Fig. 2.6 Residual Resampling重采樣并沒(méi)有從根本上解決權(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

29、為粒子濾波算法的示意圖，該圖描述了粒子濾波算法包含的時(shí)間更新、觀測(cè)更新和重采樣三個(gè)步驟。k-1時(shí)刻的先驗(yàn)概率由N個(gè)權(quán)值為1/N的粒子xk(i-)1近似表示。在時(shí)間(i) k更新過(guò)程中，通過(guò)系統(tǒng)狀態(tài)轉(zhuǎn)移方程預(yù)測(cè)每個(gè)粒子在k時(shí)刻的狀態(tài)x。經(jīng)過(guò)觀測(cè)值后，更(i)k新粒子權(quán)值w。重采樣過(guò)程舍棄權(quán)值較小的粒子，代之以權(quán)值較大的粒子，粒子的權(quán)值被重新設(shè)置為1/N。圖2.7 SIR算法示意圖 Fig. 2.7 SIR algorithm標(biāo)準(zhǔn)的粒子濾波算法流程為： (1) 粒子集初始化，k=0：(i)N對(duì)于i=1,2, ,N，由先驗(yàn)p(x0)生成采樣粒子x0i=1(2) 對(duì)于k=1,2,，循環(huán)執(zhí)行以下步驟：(i)N ki=1，計(jì) 重要性采樣：對(duì)于i=1,2, ,N，從重要性概率密度中生成采樣粒子xk，并進(jìn)行歸一化； 算粒子權(quán)值w(i)(i)k k(i)進(jìn)行重采樣，重采樣后的粒子集為xk,w,1/N； 重采樣：對(duì)粒子集x(i)Nk= 輸出：計(jì)算k時(shí)刻的狀態(tài)估計(jì)值：xxi=1(i)k k(i)。 w粒子濾波中的權(quán)值退化問(wèn)題是不可避免的。雖然重采樣方法可以在一定程度上緩解權(quán)值退化現(xiàn)象，但重采樣方法也會(huì)帶來(lái)一些其它的問(wèn)題。重采樣需要綜合所有的粒子才能實(shí)現(xiàn)，限制了粒子濾