粒子濾波器基本原理.ppt

粒子濾波器基本原理,主要內(nèi)容,1 動態(tài)系統(tǒng)模型及狀態(tài)估計問題 2 遞推Bayesian濾波器 3 粒子濾波器 4 小結(jié),1 動態(tài)系統(tǒng)模型(1),動態(tài)系統(tǒng)(Dynamic System)通過兩個方程建模： 狀態(tài)轉(zhuǎn)移方程(state transition equation) 測量方程(measurement equation),1 動態(tài)系統(tǒng)(狀態(tài)轉(zhuǎn)移方程),狀態(tài)轉(zhuǎn)移方程：,其中： fk: 轉(zhuǎn)移函數(shù)（可能是非線性的） xk, xk-1: 當前和前一時刻狀態(tài) uk-1: 已知的輸入 vk-1: 狀態(tài)噪聲(可能是非Gaussian),1 動態(tài)系統(tǒng)(測量方程),測量方程：,其中： hk: 測量函數(shù)（可能是非線性的） xk: 當前時刻狀態(tài) uk: 已知的輸入 nk: 測量噪聲(可能是非Gaussian),1 狀態(tài)估計問題,xk: 未知的，待估計的系統(tǒng)狀態(tài) z1：k: 已知系統(tǒng)測量(z1：k =zj, j=1,k ) 狀態(tài)估計問題： 根據(jù)已知的測量z1：k估計未知的狀態(tài)xk 實質(zhì)：計算后驗概率密度函數(shù)(pdf) p(xk|z1:k),2 遞推Bayesian濾波器,遞推地構(gòu)造后驗概率密度函數(shù)(pdf) p(xk|z1:k): 已知p(xk-1|z1:k-1)和zk，求p(xk|z1:k),假設(shè)：初始分布p(x0)是已知的（ p(x0)是對系統(tǒng)初始狀態(tài)知識的刻畫）。 p(xk|z1:k)可以通過以下兩個步驟遞推地獲得： 預測(prediction) 校正(update),2 遞推Bayesian濾波器(預測),預測(prediction)： 設(shè)k-1時刻的概率密度函數(shù)p(xk-1|z1:k-1)是已知的。預測階段包括通過Chapman-Kolmogorov等式使用狀態(tài)轉(zhuǎn)移方程來獲得k時刻狀態(tài)的先驗概率密度函數(shù)：,(1),2 遞推Bayesian濾波器(校正),校正(update)： 在k時刻，當測量有效時，通過Bayes規(guī)則進行校正,其中，規(guī)格化常量：,似然度,先驗概率,(2),2 遞推Bayesian濾波器(推導),2 遞推Bayesian濾波器(估計),估計：,(3),2 Bayesian濾波器(問題),理論上的解，在實際的應(yīng)用中，(1),(2),(3)中的積分是難以計算的。幾種特殊情況可以求解： 有限狀態(tài)空間（積分轉(zhuǎn)換為求和） 線性系統(tǒng)，高斯噪聲（kalman filter）,3 粒子濾波器(Particle Filter),粒子濾波器是（混合）動態(tài)系統(tǒng)估計的Monte Carlo （即隨機選擇）方法，它通過隨機選擇的樣本（或稱粒子）集來近似后驗概率分布 其優(yōu)點是： 非線性系統(tǒng) 非參數(shù)方法，可以表示任意分布（不受高斯假設(shè)約束） 在單個粒子可以同時表示離散和連續(xù)狀態(tài) 計算復雜度可調(diào)節(jié)(只與粒子數(shù)N有關(guān)) 適合處理高維狀態(tài)空間問題,Monte Carlo近似,考察積分問題：,Monte Carlo采樣使用一組獨立隨機變量來近似真實積分，設(shè)從概率分布P(x)抽取N個獨立同分布隨機樣本x(1),x(N),則上式的Monte Carlo近似為,重要性采樣,問題：難以從真實分布采樣。 重要性采樣：基本思想是選擇一個建議分布（proposal distribution）q(x)代替p(x)。假設(shè)q(x)的支撐集涵蓋了p(x)的支撐集。,重寫積分公式有：,重要性采樣,Monte Carlo重要性采樣利用一組從q(x)抽取的獨立同分布樣本對上式加權(quán)近似：,規(guī)格化,為使權(quán)重和為1，對權(quán)重進行規(guī)格化處理：,3 粒子濾波器,粒子濾波器（Particle filter PF),又稱為序列蒙特卡羅(Sequential Monte Carlo, SMC）方法. 兩種基本的PF算法： 序列重要性采樣算法（Sequential Importance Sampling, SIS），又稱為bootstrap filtering , the condensation algorithm 樣本重要性重采樣（Sample Importance Resampling Filter, SIR）,3 粒子濾波器框架（SIS算法）,權(quán)重計算,3 粒子濾波器框架（SIS算法）,重要性采樣（退化問題 Degeneracy Problem）,SIS存在退化現(xiàn)象：經(jīng)過幾次迭代后，除了一個例子外，其余的粒子的權(quán)值都變得微不足道。 退化問題導致大量的計算能力用于更新微不足道的粒子。,退化問題處理方法： 強力法：許多許多的粒子（低效） 選擇好的重要性函數(shù)（困難） 重采樣 （主流方法）,3 粒子濾波器框架（SIS算法）,3 粒子濾波器框架（SIR算法）,樣本重要性重采樣（Sample Importance Resampling Filter, SIR）從SIS推導而來，滿足以下兩個條件： 重要性q(.)密度 取先驗密度 , 重采樣：每一時間步都進行重采樣,重采樣過程,特點：權(quán)重高的粒子更多地被選中,3 粒子濾波器框架（SIR算法）,重采樣（采用基于順序統(tǒng)計量(order statistics)的算法可以在O(Ns)的時間內(nèi)實現(xiàn)重采樣）: 生成樣本集 ，使得 ； 然后令,3 粒子濾波器框架（SIR算法）,3 粒子濾波器框架（SIR算法）,重采樣（樣本枯竭現(xiàn)象 sample impoverishment）,SIR樣本枯竭現(xiàn)象：權(quán)重較高的粒子被統(tǒng)計地選擇多次，這導致粒子集喪失多樣性（a loss of diversity among the particles），因為許多樣本表示同一點。,3 粒子濾波器（缺點）,缺點 粒子數(shù)目N過大增加計算復雜度 過小則難以得到滿意的近似 退化問題 采樣枯竭的問題,4 小結(jié),動態(tài)系統(tǒng)通過狀態(tài)轉(zhuǎn)移方程和測量方程建模。 遞推Bayesian濾波器通過預測和校正兩個步驟來求后驗概率密度函數(shù)p(xk|z1:k)，但是一種理論上的解，其積分難以計算。 粒子濾波器通過一組隨機選擇的帶權(quán)樣本來表示后驗密度函數(shù)，在這些樣本和權(quán)值的基礎(chǔ)上計算估計。,4 小結(jié),粒子濾波器的優(yōu)點：非線性，非高斯，混合系統(tǒng)，計算復雜度可調(diào)節(jié)，高維問題 兩種典型的粒子濾波器算法：序列重要性采樣算法（SIS),采樣重要性重采樣算法(SIR)。 粒子濾波器的問題： SIS存在退化現(xiàn)象； SIR樣本枯竭現(xiàn)象； N的選擇問題。,參考文獻,1 M. S. Arulampalam, S. Maskell, N. Gordon, T. Clapp. A Tutorial on Partic