1、第36卷增刊華中科技大學學報(自然科學版)()Vol.36Sup.Oct.2008一種快速高斯粒子濾波算法陳鵬1,2錢徽1朱淼良1(1浙江大學計算機科學與技術學院,浙江杭州310027;2安徽師范大學物理與電子信息學院,安徽蕪湖241000)摘要:為改善高斯粒子濾波(GPF)算法的實時性,研究了一種快速的GPF算法.在GPF的預測及更新步驟中用初始粒子群的線性變換取代高斯分布采樣,以降低生成新粒子群所需時間,提高濾波算法的運行速度.對兩種生成粒子群方法的復雜度及粒子群所代表的分布進行了分析,分析結果表明:線性變換法和高斯采樣法生成的粒子群所代表的分布相同,且線性變換法的運行效率更高.將粒子濾波

2、算法(PF),GPFGPFT,明:改進后GPF算法預測性能不變,速度得到了提高,生成,6ms.關鍵詞:;高斯采樣法:167124512(2008)S120291204AfastGaussianparticlefilteringalgorithmChenPeng1,2QianHui1ZhuMiaoliang1(1CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China;2CollegeofPhysicsandElectronicInformation,AnhuiNormalUniversity,Wu

3、hu241000,AnhuiChina)Abstract:AfastGaussianparticlefiltering(GPF)algorithmwithoutsamplingstepispresentedtoim2provethereal2timeperformanceofGPFalgorithm.ThenewestimatoryieldsbetterperformancebyreplacingGaussiansamplingwithlineartransformation.Thedistributionfunctionrepresentedbytheparticlesofthesetwoa

4、lgorithmsisidenticalandthecomputingtimeoflineartransformationislessthanthatofGaussiansampling.Particlefiltering(PF)algorithm,GPFalgorithm,andimprovedGPFalgorithmareappliedtotwonumericalexamplesrespectively,oneisaone2dimensionaldiscrete2timenonlineartime2varyingmodel,theotherisatwo2dimensionalbearing

5、onlytracking(BOT)model.SimulationresultsarepresentedtodemonstratethelowercomplexityofthenewGPFalgorithmoverconventionalGPFalgorithmandPFalgorithm.ImprovedGPFalgorithmcangenerate1000particlesin22ms,6mslessthanthatofGPFalgorithmwiththesameestimationaccuracy.Keywords:nonlinearsystems;Gaussianparticlefi

6、lter;MonteCarlomethod;algorithm;lineartrans2formationmethod;Gaussiansamplingmethod高斯粒子濾波(GPF)算法是粒子濾波(PF)算法的一種變形,它通過高斯分布來近似未知變量的后驗分布1,實時性上要優于粒子濾波算法,性能上要優于擴展卡爾曼濾波(EKF)、無味卡爾曼濾波(UKF)等算法,在非線性估計、目標跟蹤、機器人定位等領域具有廣泛的應用前景.在粒子收稿日期:2008207215.數過多的情況下,這種算法仍會因為采樣帶來的效率問題而影響其應用范圍.為此提出一種改進的高斯粒子濾波算法.隨著計算機性能的提高,基于貝葉斯理

7、論的粒子濾波算法近年來在國內外得到廣泛重視和應用,針對其不足的改進算法也層出不窮.粒子濾波作者簡介:陳鵬(19752),男,講師,E2mail:chenpeng.基金項目:浙江省科技廳重大項目(2006c13096).292華中科技大學學報(自然科學版)第36卷思想最早可追溯至文獻2提出的蒙特卡羅方法.文獻3提出基本的順序重要采樣(SIS)方法,文獻4證明了SIS方法出現粒子退化現象的必然性.為解決SIS方法的退化現象,文獻5,6分別提出了重要性重采樣技術,文獻7則證明了最優重要性函數.文獻8,9將概率分布近似為高斯分布或高斯和分布,文獻10將這種思想與粒子濾波框架結合,提出了GPF及高斯采樣

8、粒子濾波(GSPF)算法.,)且相態變量的線性變換不變性可知BtN(互獨立.因此,對I1的樣本值做以上線性變換后a0+,得到的樣本a1+,at+,aN+是I2的樣本值.由于I2和I2的每個隨機2)且相互獨變量均服從同樣的高斯分布N(,立,因此a0+,a1+,at+,aN+也是I2的樣本值.由定理1可知改進后算法生成的粒子群與GPF算法生成的粒子群服從同一個分布,因此改進的GPF算法與GPF算法除了生成粒子群的方式有差別外,沒有本質上的差異.1算法原理與分析無采樣的高斯粒子濾波算法是對高斯粒子濾波算法的改進,目的在于減小采樣過程對算法實時性的影響.,GPF.由于初始粒子群可以在程序運行前事先建立

9、,因此高斯采樣生成初始粒子群所需時間對算法的實時性沒有影響.這也為使用復雜度更高更精確的高斯采樣算法生成初始粒子群提供了方便.由于對一個粒子的線性變換只需一次乘法和一次加法,與對高斯分布的采樣相比所需時間少,因此用線性變換代替高斯采樣可以提高速度.線性變換方法具體如下:初始粒子群為a0,a1,at,aN,其中每個粒子均從標準高斯分布中相互獨立地采樣得到,對每個粒子進行以下線性變換,bt=at+(0tN).線性變換后得到的粒子群為a0+,a1+,at+,aN+.將GPF算法中的高斯采樣過程替換為對初始粒子群的線性變換過程,即可得到無采樣的高斯粒子濾波算法.定理1設隨機向量I1=A0,A1,At,

10、AN,AtN(0,1)且相互獨立,I1的樣本值為a0,a1,at,aN,則a0+,a1+,at+,aN+是隨機向量I2=B0,B1,)且相互Bt,BN的樣本值,其中BtN(,獨立.證明對隨機向量I1的每個隨機變量At進行線性變換,Bt=At+(0tN),得到隨機向量IB.由正2=0,B1,Bt,BN.N個粒子N.Ziggurat4N次加法.使用基于2complement的算法12速度上比Ziggurat算法提高24%.可見生成同樣數量的粒子集,線性變換法的時間復雜度為O(N),高斯分布采樣法的時間復雜度至少為O(3N).線性變換法所需時間相對要少,因此用線性變換代替高斯采樣可以提高速度.2算法

11、仿真將粒子濾波算法、高斯粒子濾波算法及改進后的高斯粒子濾波算法分別應用于一維及二維非線性系統,軟件環境為Matlab,硬件環境為奔騰IV2.4GHz,512Mbyte內存.2.1一維仿真模型一維仿真模型的狀態方程和測量方程如下xt+1=xt/2+25xt/(1+x2t)+(1)8cos(1.2t)+t;yt=xt/20+et,(2)式中:t和et為相互獨立的白噪聲變量,tN(0,10),etN(0,1);xtN(0,5).這是一個具有可加噪聲的離散非線性時變系統6,設xt為待預測的電壓狀態變量,yt為測量變量.可將此模型看作是在電阻上加載規律變化的電壓,根據測量的功率值來預測其電壓值.算法需要

12、根據t時刻yt值預測t+1時刻狀態變量xt+1的值,粒子數設為2000,仿真步驟如下:a.設置系統參數,并置t=0,生成x0;b.根據系統設置的參數生成相應的變量值t和et;c.由式(1)生成狀態變量下一步的實際值增刊陳鵬等:一種快速高斯粒子濾波算法293xt+1,由式(2)生成測量變量值yt;d.分別由PF算法13、GPF算法及改進后的GPF算法,根據測量值生成狀態變量的預測值xt+1;e.置t=t+1,轉b.2.2二維仿真模型預期是一致的.由于GPF算法取消了重要性重采樣過程,所需時間少于PF算法采樣時間.表1數據表明,每生成1000個粒子,改進后的GPF算法平均需時22ms,比GPF算法

13、(28ms)及PF算法(30ms)需時都要少.二維仿真模型采用基于角度的目標跟蹤(BOT)模型,即在有噪聲情況下對二維運動目標進行跟蹤.模型中使用的傳感器只能測量角度,不能測量與目標的相對距離.為簡化起見,仿真中角度傳感器位于xy平面的原點.狀態方程為Xn=Xn-1+n(n=1,2,N),式中:Xn=xn,vxn,yn,vynT,xn和yn為目標的坐標位置,vxn和vyn分別為目標在x方向和y方向的速度;n=xn,ynT;1100100000.51.算法GPF算法真實狀態;3高斯粒子濾;4改進算法預測值=00系統噪聲為零均值高斯白噪聲,即nN(0,22的單位矩陣).初始狀態向量X0wI2)(I

14、2為2×描述了目標的初始位置和速度,初始狀態的先驗分布概率為X0N(0,P0).測量數據為附加有高斯噪聲的目標角度,測量方程為(3)znarctan(yn/xn)+n.測量噪聲為零均值高斯白噪聲,即nN(0,2).值得注意的是,根據式(3),從測量數據中得不到目標的距離信息,算法將根據狀態向量的先驗分布及測量數據跟蹤目標.可將此模型看作物體在空中運動,根據物體與觀察者間的角度變化來預測這一物體的具體位置.仿真時,設置的目標初始狀態為X0=-0.050,0.001,0.700,-0.055,系統和測T圖2PF算法、GPF算法及無采樣的GPF算法目標跟蹤結果表13種算法仿真結果比較處理時

15、間/ms平均相對誤差/%改進的GPF算法GPF算法PF算法222830354127=0.001,=0.005.量的噪聲由上文規定,且粒子數設為5000,共仿真24步.仿真步驟類似一維仿真模型的仿真步驟.2.3仿真結果與分析一維仿真模型的仿真結果(100步)見圖1.二維仿真模型的仿真結果(24步)見圖2.一維模型仿真的統計數據見表1(表中處理時間為生成1000個粒子集的平均處理時間).可見改進后的GPF算法在預測精度基本不變的情況下,運行時間減少了.由圖1及表1可知,GPF算法和改進后的GPF算法精度都要比PF算法的低.這與GPF算法及改進后的GPF算法都是用單高斯分仿真結果證明改進的GPF算法

16、達到了預期目的.與改進前的算法相比,預測精度基本不變,運行時間減少了.對于無法用單高斯較好近似的非線性系統,可采用帶相關權值的多高斯濾波算法(GSPF)10以獲得較好估計.由于GSPF也是用高斯近似,因此可用同樣的方法替代高斯采樣過程以提高其效率.參考文獻1KotechaJH,DjuricPM.GaussianparticlefilteringJ.IEEETransactionsonSignalProcessing,2003,51(10):259222601.2MetropolisN,UlamS.TheMonteCarlomethodJ.JournaloftheAmericanStatisti

17、calAssociation,布近似未知變量的后驗分布,精度應有所降低的294華中科技大學學報(自然科學版)68.第36卷1949,44(247):3352341.3HammersleyJM,MortonKW.PoormansMonteCarloJ.JournaloftheRoyalStatisticalSocietyB,1954,16(1):23238.4DoucetA,GodsillS,AndrieuC.OnsequentialMonteCarlosamplingmethodsforBayesianfilteringJ.StatisticsandComputing,2000,10(3):1

18、972208.5RubinDB.UsingtheSIRalgorithmtosimulatepos2teriordistributionsM.Oxford:OxfordUniversityPress,1988.6GordonNJ,SalmondDJ,SmithAFM.Novelap2proachtononlinear/non2GaussianBayesianstateesti2mationJ.RadarandSignalProcessing,IEEPro2ceedingsF,1993,140(2):1072113.7LiuJS,ChenR.SequentialMonteCarlomethods

19、fordynamicsystemsJ.JournaloftheticalAssociation,:11044.8fGauss.,1970,7:6329AlspachDL,SorensonHW.NonlinearBayesianes2timationusingGaussiansumapproximationJ.IEEETransactionsonAutomaticControl,1972,17:4392448.10KotechaJH,DjuricPM.Gaussiansumparticlefil2teringJ.IEEETransactionsonSignalProcessing,2003,51

20、(10):260322613.11MarsagliaG,TsangWW.TheZigguratmethodforgeneratingrandomvariablesJ.JournalofStatisti2calSoftware,2000,5(8):127.12RubinH,JohnsonBC.Efficientgenerationofex2ponentialandnormaldeviatesJ.JournalofStatis2ticalComputationand,2006,76(6):5092518.systems.Linko¨pings:Depart2Engineering,Linko¨pingsUniver2sitet,2006.(上接第290頁)11KaelblingLP,LittmanML,MooreAW.Rein2forcementlearning:asurveyJ.JournalofArtifi2cialIntelligenceResearch,1996,4(1):2372285.12TaskarB,ChatalbashevV,KollerD,etal.Learn2ingstructuredpredictionmodels:alargemarginap2proachCProceedingsofthe22ndInte