粒子滤波算法综述

第20卷第4期

Vol.20No.4

　控　制　与　决　策

　Controland

Decision　

2005年4月

　Apr.2005

　　文章编号:1001-0920(2005)04-0361-05

粒子滤波算法综述

胡士强,敬忠良

1,2

(1.上海交通大学自动化系,上海200030;2.河北科技大学自动化系,湖北石家庄050054)

摘　要:对粒子滤波算法的原理和应用进行综述.首先针对非线性非高斯系统的状态滤波问题,阐述粒子滤波的原理;然后在分析采样-重要性-重采样算法基础上,讨论粒子滤波算法存在的主要问题和改进手段;最后从概率密度函数的角度出发,将粒子滤波方法与其他非线性滤波算法进行比较,阐明了粒子滤波的适应性,给出了粒子滤波在一些研究领域中的应用,并展望了其未来发展方向.关键词:粒子滤波;概率密度;非线性滤波;算法中图分类号:TP14　　　　文献标识码:A

Overviewofparticlefilteralgorithm

HUShi-qiang1,2,JINGZhong-liang1

(1.DepartmentofAutomation,

ShanghaiJiaotongUniversity,

Shanghai200030,China;

2.Departmentof

Automation,HebeiUniversityofScienceandTechnology,Shijiazhuang050054,China.Correspondent:HUShi-qiang,E-mail:[email protected])

Abstract:TheAlgorithmandapplicationsrelatedtoparticlefilteraresurveyed.Aimingatthenonlinear/non-Gaussianfilterproblem,thegenericideasofparticlefilteraregiven,basedontheanalysisofstandardalgorithmofsampling-importance-resamplingfilter,theproblemsofparticlefilterarediscussedandsomeimprovementmethods

areillustrated.Fromviewofprobabilitydensityfunction,thecomparisonsbetweenparticlefilterandothersnon-linearfilteralgorithmsandapplicabilityareintroduced,someapplicationsinthedevelopedareasarereviewed,Finally,furtherresearchdirectionsarepointedout.

Keywords:particlefilter;probabilitydensity;non-linearfilter;algorithm

1　引　　言

　　近年来,科研人员在机动目标跟踪、信号传输与压缩、金融领域数据分析、图像处理等方面提出许多非线性滤波新方法[1～4],这些算法都是基于贝叶斯采样估计的顺序重要采样(SIS)滤波思想.Hammersley等在20世纪50年代末就提出了基本的SIS方法,并在60年代使其得到了进一步发展,但上述研究始终未能解决粒子数匮乏现象和计算量制约等问题,因此未引起人们的重视.直到1993年由Gordon等[1]提出了一种新的基于SIS的Bootstrap非线性滤波方法,从而奠定了粒子滤波算

　　收稿日期:2004-05-13;修回日期:2004-07-12.

[6]

[5]

法的基础.

粒子滤波是指:通过寻找一组在状态空间中传播的随机样本对概率密度函数p(xkûzk)进行近似,以样本均值代替积分运算,从而获得状态最小方差估计的过程,这些样本即称为“粒子”.采用数学语言描述如下:对于平稳的随机过程,假定k-1时刻系统的后验概率密度为p(xk-1ûzk-1),依据一定原则选取n个随机样本点,k时刻获得测量信息后,经过状态和时间更新过程,n个粒子的后验概率密度可近似为p(xkûzk).随着粒子数目的增加,粒子的概率密度函数逐渐逼近状态的概率密度函数,粒子滤波

　　基金项目:国家自然科学基金项目(60375008);中国博士后科学基金项目(2003034265);上海市博士后基金项目

(SH0325);河北省博士基金项目(B2004510).

　　作者简介:胡士强(1969—),男,河北定州人,教授,博士后,从事非线性滤波、图像理解等研究;敬忠良(1960—),

362控　　制　　与　　决　　策

wk=

p(z1:kûx0:k)p(x0:k)

q(xkûx0:k-1,z1:k)q(x0:k-1ûz1:k)wk-1

kkkk-1.

q(xkûx0:k-1,z1:k)

第20卷

估计即达到了最优贝叶斯估计的效果[4].

粒子滤波算法摆脱了解决非线性滤波问题时随机量必须满足高斯分布的制约条件,并在一定程度上解决了粒子数样本匮乏问题,因此近年来该算法在许多领域得到成功应用.目前已有许多会议和讨论组都将粒子滤波作为专题进行深入讨论和学术交流

[7～9]

(7)

由概率密度p(xk-1ûz1:k-1),利用重采样方法可得N个随机样本点{xk-1}i=1,则概率密度函数可表示为

p(xk-1ûz1:k-1)=更新概率密度函数为

∑w

i=1N

ik-1

D(xk-1-xk-1);(8)

2　基本粒子滤波算法

2.1　最优贝叶斯估计

假定动态时变系统描述如下:

xk=fk(xk-1,vk-1),zk=hk(xk,nk).

(1)

p(xkûz1:k)≈

其中

w=w

Nik

ik-1

∑wD(x

i=1

-xik).

(9)

若已知状态的初始概率密度函数为p(x0ûz0)=p(x0),则状态预测方程为

p(xkûz1:k-1)=p(xûx∫

k-1

p(zkûxik)p(xikûxik-1)

,q(xkûxk-1,zk)

(10)

)p(xk-1ûz1:k-1)dxk-1;kkk1:k-1.

p(zkûz1:k-1)

(2)

样本点{xk}i=1可由k-1时刻的样本点{sk-1}i=1通过式(1)获得.

SIS方法的实现步骤如下:

1)从q(xkûxk-1,zk)中随机抽取n个有限样本;2)逐点计算对应的p(xkûxk-1)和p(zkûxk);3)利用式(10)计算对应样本的重要性权系数;4)对权进行归一化处理,即

状态更新方程为

p(xkûz1:k)=

其中

p(zkûz1:k-1)=

(3)

∫

p(zkûxk)p(xkûz1:k-1)dxk.(4)

w=w

ikik

　　式(2)～(4)描述了最优贝叶斯估计的基本思想,但式(2)中的积分项仅对某些动态系统获得解析解[10],对于非高斯非线性系统,由于SIS方法受到计算量的制约,始终没有较好的解决办法.2.2　SIS算法

基于随机采样运算的蒙特卡罗方法可将积分运算转化为有限样本点的求和运算,即状态概率密度分布可用如下经验概率分布近似表述:

dp(x0∶kûz1:k)=N∑Dxi0:k(dx0:k),

i=1

∑w.

j=1

(11)

　　5)利用式(9)对p(xkûz1:k)进行估计.

3　粒子滤波算法存在的主要问题

　　对于SIS算法而言,粒子数匮乏是其主要缺陷.粒子数匮乏是指随着迭代次数增加,粒子丧失多样性的现象.Doucet从理论上证明了SIS算法出现粒子数匮乏现象的必然性.降低该现象影响的最有效方法是选择重要性函数和采用重采样方法.3.1　重要性函数选择

选取重要性函数的准则是使重要性权重的方差最小.Liu等

[12]

[11]

(5)

其中p(xkûz1:k)表示Z观测序列下x的概率密度.蒙特卡罗方法的核心是将式(2)中的积分问题转化为有限样本点的概率转移累加过程,但在实际中由于p(xkûz1:k)可能是多变量、非标准概率分布,通常需要借助一些采样性算法.重要性函数是指概率分布与p(xkûz1:k)相同,概率密度分布q(x0:kûz1:k)已知且容易从中采样的分布函数,重要性采样需要得到k时刻以前所有的观测数据.因此实际中多采用可实现递推估计的SIS算法.

若将重要性函数q(x0:kûz1:k)写成如下连乘积形式:

证明了最优重要性函数为

q(xkûx0:k-1,z1:k)=p(xkûx0:k-1,z1:k).但采用最优重要性函数需要从p(xkûx0:k-1,z1:k)采样并计算积分.从应用角度看[1,13],多数重要性函数都采用次优算法容易实现的q(xkûx0:k-1,z1:k)=p(xkûxk-1).3.2　重采样

重采样算法是降低粒子匮乏现象的另一种方法,其思想是通过对粒子和相应权表示的概率密度函数重新采样,增加权值较大的粒子数.最常用的重采样方法是随机采样方法[14].其过程是:首先产生n个在[0,1]上均匀分布的随机数{Ll:l=1,2,…,n},然后通过搜索算法找到满足以下条件的整数m,使得

jj=0

j=0

m-1

q(x0:kûz1:k)=q(x0)∏q(xjûx0:j-1,z1:j),(6)

j=1

并假设状态符合马尔科夫过程,在给定状态下,观测

第4期胡士强等:粒子滤波算法综述363

　　记录样本x(km),并将其作为新样本集中的采样,

i=将区间[0,1]按K

态的后验概率,而且对非高斯情况核函数和核带宽系数不能达到最优,它只是一种次优滤波方法.4.3　自适应粒子滤波算法

自适应粒子滤波算法

[20]

∑wj(i=1,2,…,n)分成n个

j=0

小区间,当随机数Ll落在第m个区间Im=(Km-1,K]时,对应样本x

(m)

可有效解决粒子滤波

进行复制.

在采样总数仍保持为n的情况下,权值较大的样本被多次复制,从而实现重采样过程.显然,重采样过程是以牺牲计算量和鲁棒性来降低粒子数匮乏现象.

的计算量问题,其基本思想是在估计过程中采样粒子数不再保持固定值,而是根据滤波性能动态改变.其核心步骤是引入Kullback-Leibler距离描述粒子滤波的近似误差,K-L距离用于表示不同概率分布p和q的差异,即

K(p,q)=

4　粒子滤波算法的改进算法

　　为解决粒子滤波的粒子数匮乏,出现了许多针对状态空间模型的改进算法,如辅助变量粒子滤波算法、局部线性化方法、拒绝采样方法等[15～17].针对重采样改进方法,文献[18,19]通过引入遗传算法和进化算法,增加重采样过程中粒子的多样性;文献[20]则根据滤波性能动态调整粒子数.4.1　辅助采样-重采样方法

辅助采样-重采样粒子滤波的实现方法是:选择重要性函数,满足

q(xk,iûz1:k)∝p(zkûLik)p(xkûxik-1)wik-1,(13)其中辅助变量i表示k-1时刻采样粒子的索引.

重要性权值wk为

kjkjkik-1j

=wk∝wk-1q(xk,iûz1:k)

∑p(x)logq(x).

(17)

　　自适应粒子滤波算法通过不断计算粒子滤波,得到估计后验概率密度与真实后验概率密度的K-L距离,确定粒子滤波性能的高低.当概率密度集中在状态空间中的某部分时,可采用较少的粒子数,而概率密度分散在状态空间中的绝大部分时,需采用较多的粒子数,这也符合贝叶斯估计的思想.

5　与其他非线性滤波方法的比较

　　随着粒子滤波方法在许多领域中的成功应用,研究人员认为在解决所有状态估计的滤波问题时,获得滤波性能最好的方法就是粒子滤波算法,它甚至优于卡尔曼滤波方法.实际上,粒子滤波作为处理非线性系统状态估计问题的方法之一,也存在着算法适应性和估计精度问题.5.1　扩展卡尔曼滤波

kjkj.

p(zkûLik)

(14)

扩展卡尔曼滤波(EKF)方法作为处理非线性系统的经典方法,其思想是将非线性函数在估计点附近进行泰勒级数展开.扩展卡尔曼滤波方法有两个弱点:1)未考虑误差的分布情况;2)认为状态误差可通过一个独立的线性系统产生.这在应用上造成了状态估计精度有时较低,并易出现滤波发散等情况.

5.2　Unscented卡尔曼滤波

Julier提出了Unscented卡尔曼滤波(UKF)算法[22],扩展卡尔曼滤波算法是通过线性化方法来逼近非线性状态状态方程和测量方程.UKF算法的核心思想是变换(UT),UT方法认为状态的概率密度分布,可通过能完全表述密度函数的均值和方差的有限个样本点来描述,通过直接使用状态或测量的非线性方程映射这些样本点,加权求和得到更新的均值和方差.若将非线性方程采用泰勒级数展开式表示,可看出UKF方法将精确到与三阶泰勒级数展开式相当的均值和方差.采用UKF可得到比

[23]

EKF更好的滤波性能.

5.3　EKF,UKF,PF3种算法的比较

　　辅助采样-重采样算法的辅助采样在k-1时刻进行,并考虑k时刻的测量信息zk,这样使得在过程噪声较小时,采样粒子更接近k时刻的真实状态,从而可获得比标准粒子滤波更高的滤波精度;但当过程噪声较大时,滤波效果不如标准粒子滤波算法.4.2　规则化采样方法

规则化方法与标准粒子滤波算法仅在重采样过程中有所区别[21],标准粒子滤波采用式(8)的离散形式计算p(xkûz1:k),而规则化方法则采用如下的连续形式计算p(xkûz1:k):

d(xkûz1:k)≈p

∑wK

i=1

(xk-xik).

(15)

其中K(õ)和h分别是满足

MISE(pd)=

d(xkûz1:k)-p(xkûz1:k)]2dxk.[p

(16)

的核密度函数和核带宽系数.

规则化采样方法可有效缓解重采样过程造成的粒子多样性匮乏问题,在过程噪声较小时可获得较,

364控　　制　　与　　决　　策第20卷

曼滤波方法的变形和改进形式,因此受到线性卡尔曼滤波算法的条件制约,即系统状态应满足高斯分布.对于非高斯分布的状态模型,若仍简单地采用均值和方差表征状态概率分布,将导致滤波性能变差.粒子滤波算法不需要对状态变量的概率密度作过多的约束,它是非高斯非线性系统状态估计的“最优”滤波器.表1给出了不同状态方程和观测方程的概率分布特性时的不同滤波方法.

表1　各种滤波算法的适应性范围

状态方程观测方程线性高斯线性非高斯

线性高斯KFPF

线性非高斯

非线性高斯

非线性非高斯PFPFPFPF

度采用交互式粒子滤波方法,对由随机波动模型描述的股票交易数据进行预测分析,说明了算法的有效性;[29]采用粒子滤波方法研究了风险估值问题,它利用分位数重要性重采样方法给出了利率的最佳估计,进而可确定最合理的投资组合.从上述文献可以看出,粒子滤波对于处理基于随机波动模型和风险估值的金融数据有着良好的应用前景.6.3　计算机视觉

近年来,依据序列图像对感兴趣区域进行持续跟踪问题引起人们的广泛关注.目前图像跟踪的难点在于:1)由于复杂背景的影响,在目标运动区域提取(目标的出现与消失)方面缺乏有效的手段;2)由于目标被障碍物遮挡的影响,使测量数据出现断续现象,基于扩展卡尔曼滤波等方法出现失跟等问题;3)密集目标的线路交叉跟踪问题.

对于上述问题,文献[30]率先在计算机视觉领域引入了粒子滤波算法;[31]较系统地研究了采用粒子滤波算法如何实现目标的轮廓跟踪,其研究重点是如何选择重要性函数和避免粒子数的匮乏现象;[32]系统地总结了粒子滤波方法在计算机视觉中的应用,从中可系统了解粒子滤波在计算机视觉中的应用成果和最新发展趋势.

6.4　状态监视与故障诊断

状态监视的实质是状态的在线估计,故障诊断是一定准则下的状态异常检测.文献[33]研究了采用粒子滤波方法对复杂工业过程中的热交换器特征参数,结合EM算法进行辨识,获得了满意的实时控制效果;[34]给出了粒子滤波在汽车辅助避碰系统中的应用,采用基于双峰高斯假设条件,同时给出了基于卡尔曼滤波和粒子滤波两种汽车周围目标的跟踪算法,结果显示采用粒子滤波算法更容易确定辅助避碰决策;[35]研究了不完全量测信息下非线性模型采用粒子滤波进行人体行为异常检测,并以机场停机坪旁行人的异常行走路线为例,说明了采用粒子滤波方法处理判定状态“缓慢”变化的有效性.

PFEKF/UKF/PFPF

非线性高斯EKF/UKF/PF非线性非高斯

PFEKF/UKF/PFPF

　　由贝叶斯估计方法看出,卡尔曼滤波方法是线性高斯系统的最优滤波器,而粒子滤波作为采样贝

叶斯估计算法,只是随着采样粒子数的不断增大,逐渐趋向状态的后验概率密度.粒子滤波算法与其他非线性滤波方法一样,也是一种次优的滤波方法.粒子滤波在解决非高斯分布系统时具有明显的优势.

6　粒子滤波的应用

6.1　机动目标跟踪

对目标进行定位和跟踪是典型的动态系统状态估计问题,在模型满足高斯线性条件下,卡尔曼滤波器可获得最好的跟踪效果.但在诸如纯角度跟踪的运动模型中,线性、高斯假设条件常常不能满足,出现滤波精度下降和发散现象.将Gordon等

[1]

提出

的粒子滤波方法应用到纯角度跟踪问题中,获得了较好的跟踪精度.随后,文献[24]研究了多目标跟踪与传感器管理问题;[25]研究了多目标跟踪与数据融合问题;[26]给出了基于粒子滤波的群目标跟踪算法等.

粒子滤波用于目标跟踪的成果表明,粒子滤波能较好地处理测量断续、群目标跟踪、雷达跟踪多路径等传统难题,因此它是目标跟踪中非线性问题的数学支撑工具之一.6.2　金融领域数据分析

金融领域的许多问题(如:证券投资走向分析、风险投资最优决策等)都可归结为模糊随机系统估值问题.文献[27]针对随机波动模型的特点,即模型具有明显的非线性和非高斯的“厚尾”特性,利用真实数据和粒子滤波方法计算SV模型参数的似然函数和边界似然函数,说明了粒子滤波算法在计算SV[7　展望与结论

　　粒子滤波方法作为一种基于贝叶斯估计的非线

性滤波算法,在处理非高斯非线性时变系统的参数估计和状态滤波问题方面有独到的优势,因此获得了很大的发展.但由于粒子滤波是近年来出现的新算法,算法本身还不很成熟,仍有大量的问题亟待解决,主要体现在以下几个方面:

1)重要性函数的选取直接影响粒子滤波性能的高低.虽然出现了许多针对实际问题的改进算法,但对通用问题缺乏一般借鉴意义.根据系统的先验,

第4期胡士强等:粒子滤波算法综述365

函数选择,成为目前重要性函数选取研究方向的热点.

2)经典的重采样方法虽然在克服粒子数匮乏方面具有良好的效果,但计算量的扩张随着粒子数的增加而成级数增加,对有实时性要求的系统中,粒子滤波的可实现性成为主要问题.将成熟的多种不同寻优方法引入重采样过程,以便更快地提取到反映系统概率特征的典型“粒子”,逐渐成为重采样方法研究的重点.

3)从粒子滤波的数学基础上看,粒子滤波的收敛性尚未解决,若能有效解决收敛性问题,则对粒子匮乏现象的抑制将有很大帮助.同时作为滤波算法,如何评价粒子滤波的性能也是需要认真考虑的问题.

4)多种非线性滤波方法的结合.虽然粒子滤波能有效解决非高斯、非线性系统的滤波问题,但由于其算法运算的实时性问题、状态初始概率选取问题,使粒子滤波距离工程应用尚有一定差距.根据系统不同阶段体现的不同统计特性,将粒子滤波与其他非线性滤波方法相结合,避免非线性系统的近似线性化,减小非线性系统线性化后的高阶截断误差和非高斯噪声带来的影响,是实际问题中采用粒子滤波方法的又一研究方向.

5)粒子滤波算法的硬件实现.为了提高粒子滤波算法的运算速度和鲁棒性,研究粒子滤波的硬件实现方法尤为关键.粒子滤波硬件实现的基本思想是:将粒子滤波划分为初始采样、重采样、状态更新等不同过程,利用流水线实现分时并行处理.但实用化粒子滤波算法器尚未研制成功.

6)拓展粒子滤波新的应用领域.由于粒子滤波算法出现较晚,碍于学科间的差异,粒子滤波仅限于有限的几个领域.从分析算法的思想可以看出,只要针对非线性状态估计系统建立起相应的模型,在采用Kalman滤波效果不理想的情况下,便可尝试采用粒子滤波算法.

目前,粒子滤波算法在国外发展很快,并取得了许多研究成果,而国内相关研究则刚刚起步.若能对上述问题进行深入研究,必将促进粒子滤波算法理论和应用的发展,在非高斯、非线性系统的数据分析和处理领域紧跟世界发展趋势.参考文献(References)

[1]GordonN,SalmondD.Novelapproachtonon-linear

andnon-GaussianBayesianstateestimation[J].Procof

InstituteElectricEngineering,1993,140(2):107-113.[2]MacCormickJ,BlakeA.Aprobabilisticexclusion

principlefortrackingmultipleobjects[A].The7thIEEEIntConfonComputerVision[C].Kerkyra,1999:572-578.

[3]CarpenterJ,CliffordP.Improvedparticlefilterfor

nonlinearproblems[J].IEEProcofRadar,SonarandNavigation,1999,146(1):2-7.

[4]DoucetA,GordonN.SequentialmonteCarlomethods

inpractice[M].NewYork:Springer-Verlag,2001.[5]HammersleyJM,MortonKW.Poorman’sMonte

Carlo[J].JoftheRoyalStatisticalSocietyB,1954,16(1):23-38.

[6]HandschinJE.MonteCarlotechniquesforprediction

andfilteringofnon-linearstochasticprocesses[J].Automatica,1970,6(3):555-563.

[7]FearnheadP.SequentialMonteCarlomethodsinfilter

theory[R].Oxford:MertonCollege,1998.[8]SanjeevM,SimonMaskell.Atutorialonparticle

filtersfor

onlinenonlinear/non-GaussianBayesian

tracking[J].IEEETransonSignalProcessing,2002,50(2):174-188.

[9]CrisanD,DoucetA.Asurveyofconvergenceresults

onparticlefilteringmethodsforpractitioners[J].IEEETransonSignalProcessing,2002,50(2):736-746.[10]HaykinSKalman.Filteringandneuralnetworks[M].

NewYork:JohnWileyandSons,2001.[11]DoucetA,

sampling

GodsillS.OnsequentialMonteCarlomethods

for

Bayesian

filtering[R].

Cambridge:UniversityofCambridge,1998:1-36.[12]LiuJS,ChenR.SequentialMonteCarlomethodsfor

dynamicalsystems[J].JoftheAmericanStatisticalAssociation,1998,93(5):1032-1044.

[13]LiuJS,ChenR.Blinddeconvolutionviasequential

imputation[J].

Jof

theAmericanStatistical

576.Association,1995,90(2):567-[14]KitagawaG.MonteCarlofilterandsmootherfornon-Gaussiannonlinearstatespacemodels[J].1-25.[15]PittMK,

ShephardN.Filteringviasimulation:

Jof

theAmerican

Auxiliaryparticlefilters[J].

Jof

ComputationalandGraphicalStatistics,1996,5(1):

StatisticalAssociation,1999,94(2):590-599.[16]BerzuiniC,BestN.Dynamicconditionalindependence

modelsandMarkovchainMonteCarlomethods[J].JoftheAmericanStatisticalAssociation,1997,92(5):1403-1412.

[17]BelvikenE,AcklamPJ.MonteCarlofiltersfornon-linearstateestimation[J].Automatica,2001,37(1):177-183.

(下转第371页)

第4期

参考文献(References)

唐功友等:带有持续扰动非线性系统的前馈-馈反最优控制

[6]BeardRW,

SaridisGN,

WenJT.

371

Galerkin

[1]LindquistA,YakubovichVA.Optimaldampingof

forcedoscillationsindiscrete-timesystems[J].IEEE

TransAutomaticControl,1997,42(6):786-802.[2]TangGY.Feedforwardandfeedbackoptimalcontrol

forlinearsystemswithsinusoidaldisturbances[J].HighTechnologyLetters,2001,17:16-19.

[3]唐功友,赵艳东,陈显利.带正弦干扰的线性时滞系统的

次优控制[J].控制与决策,2004,19(5):529-533.(TangGY,ZhaoYD,ChenXL.Suboptimalcontrolfor

time-delay

linear

systems

under

sinusoidal

disturbances[J].ControlandDecision,2004,19(5):529-533.)[4]LiH,

HuSJ,ChengZ.Multiple-steppredictive

controlforoffshorestructure[J].ChinaOceanEnginee-ring,1999,13:231-246.

[5]MieleA.Optimaltrajectoriesandguidancetrajectories

foraircraftflightthroughwindshears[A].Proc29th

IEEEConfonDecisionandControl[C].Hawaii,1990:737-746.

approximationofthegeneralizedHamilton-Jacobi-Bellmanequation[J].Automatica,1997,33(12):2159-2177.

[7]ChananeB.Optimalcontrolofnonlinearsystems:A

recursiveapproach[J].ComputersandMathematicswithApplications,1998,35(3):29-33.

[8]NishikawaY,SannomiyaN,ItakuraH.Amethodfor

suboptimaldesignofnonlinearfeedbacksystems[J].Automatica,1971,7(6):703-712.

[9]唐功友,曲海鹏,高延铭.一类非线性系统次优控制的

灵敏度法[J].青岛海洋大学学报,2002,32(4):615-620.(TangGY,QuHP,GaoYM.Sensitivityapproachofsuboptimalcontrolforaclassofnonlinearsystems[J],620.)JOceanUniversityQingdao,2002,32(4):615-[10]LancasterP,LererL,TismenetskyM.Factored

formsforsolutionsofAX-XB=CandX-AXB=Cincompanionmatrices[J].

LinearAlgebraandIts

49.Applications,1984,62(3):19-

　　(上接第365页)

[18]HiguchiT.

MonteCarlofilteringusinggenetics

[27]ChibS,NardariF,ShephardN.MarkovchainMonte

Carlomethodsforstochasticvolatilitymodels[J].Jof316.Econometrics,2002,8(1):281-[28]PapavasiliouA.Adaptiveparticle

2002.

[29]HeinrichA.Applicationsofstatisticalbootstrappingin

finance[R].Oxford:UniversityofOxford,2000.[30]IsardM,BlakeA.Condensation-conditionaldensity

propagationforvisualtacking[J].JofComputerVision,1998,29(1):5-28.

[31]IsardM,BlakeA.Condensation:Unifyinglow-level

andhigh-leveltrackinginastochasticframework[A].ProcoftheFifthEuropeanConfonComputerVision[C].Berlin,1998:893-908.

[32]MaccormickJ,MaccormickF.Stochasticalgorithms

forvisualtracking[M].Paris:TelosPress,2003.[33]MoralesR,PooleD.Real-timemonitoringofcomplex

industrialprocesseswithparticlefilters[R].Orlando:

UniversityofBritishColumbia,2003.[34]KarlssonR,

JanssonJ.

Model-based

statistical

trackinganddecisionmakingforcollisionavoidanceapplication[R].VolvoCar/Control&CommunicationActiveSafety,2003:1-6.

[35]VaswaniN,ChellappaR.Aparticlefilteringapproach

toabnormalitydetectioninnonlinearsystemsanditsapplication

abnormalactivity

detection[R].

filters

with

algorithmoperator[J].JofStatisticalComputation23.andSimulation,1997,59(1):1-[19]MoYW,XiaoDY.Hybridsystemmonitoringand

diagnosingbasedonparticlefilteralgorithm[J].ActaAutomationSinica,2003,29(3):641-648.

[20]FoxD.Adaptingthesamplesizeinparticlefilters

throughKLD-sampling[R].Washington:University

ofWashington,2003:1-27.

[21]DoucetA,GordonN.SequentialMonteCarlomethods

inpractice[M].NewYork:Springer-Verlag,2001.[22]JulierSJ,UhlmannJK.Anewmethodforthe

nonlineartransformationofmeansandcovarianceinfiltersandestimators[J].IEEETransonAutomaticControl,2000,45(3):477-482.

[23]WanEA,VanderMerweR.TheunscentedKalman

filterfornonlinearestimation[J].ProcofSignalProcessing,2000,3(1):153-158.

[24]DoucetA,DavyM.Particlefilteringformulti-target

trackingandsensormanagement[A].The5thIntConfonInformationFusion[C].Annapolis,2002:474-481.[25]HueC,CadreJ,PerezP.SequentialMonteCarlo

methodsformultipletargettrackinganddatafusion[J].IEEETransonSignalProcessing,2002,50(2):309-325.

[26]StorvikG.Particlefiltersforstate-spacemodelswith

thepresenceofunknownstaticparameters[J].IEEEapplications[R].Princeton:UniversityofPrinceton,

第20卷第4期

Vol.20No.4

　控　制　与　决　策

　Controland

Decision　

2005年4月

　Apr.2005

　　文章编号:1001-0920(2005)04-0361-05

粒子滤波算法综述

胡士强,敬忠良

1,2

(1.上海交通大学自动化系,上海200030;2.河北科技大学自动化系,湖北石家庄050054)

Overviewofparticlefilteralgorithm

HUShi-qiang1,2,JINGZhong-liang1

(1.DepartmentofAutomation,

ShanghaiJiaotongUniversity,

Shanghai200030,China;

2.Departmentof

Automation,HebeiUniversityofScienceandTechnology,Shijiazhuang050054,China.Correspondent:HUShi-qiang,E-mail:[email protected])

Keywords:particlefilter;probabilitydensity;non-linearfilter;algorithm

1　引　　言

　　收稿日期:2004-05-13;修回日期:2004-07-12.

[6]

[5]

法的基础.

　　基金项目:国家自然科学基金项目(60375008);中国博士后科学基金项目(2003034265);上海市博士后基金项目

(SH0325);河北省博士基金项目(B2004510).

　　作者简介:胡士强(1969—),男,河北定州人,教授,博士后,从事非线性滤波、图像理解等研究;敬忠良(1960—),

362控　　制　　与　　决　　策

wk=

p(z1:kûx0:k)p(x0:k)

q(xkûx0:k-1,z1:k)q(x0:k-1ûz1:k)wk-1

kkkk-1.

q(xkûx0:k-1,z1:k)

第20卷

估计即达到了最优贝叶斯估计的效果[4].

[7～9]

(7)

由概率密度p(xk-1ûz1:k-1),利用重采样方法可得N个随机样本点{xk-1}i=1,则概率密度函数可表示为

p(xk-1ûz1:k-1)=更新概率密度函数为

∑w

i=1N

ik-1

D(xk-1-xk-1);(8)

2　基本粒子滤波算法

2.1　最优贝叶斯估计

假定动态时变系统描述如下:

xk=fk(xk-1,vk-1),zk=hk(xk,nk).

(1)

p(xkûz1:k)≈

其中

w=w

Nik

ik-1

∑wD(x

i=1

-xik).

(9)

若已知状态的初始概率密度函数为p(x0ûz0)=p(x0),则状态预测方程为

p(xkûz1:k-1)=p(xûx∫

k-1

p(zkûxik)p(xikûxik-1)

,q(xkûxk-1,zk)

(10)

)p(xk-1ûz1:k-1)dxk-1;kkk1:k-1.

p(zkûz1:k-1)

(2)

样本点{xk}i=1可由k-1时刻的样本点{sk-1}i=1通过式(1)获得.

SIS方法的实现步骤如下:

1)从q(xkûxk-1,zk)中随机抽取n个有限样本;2)逐点计算对应的p(xkûxk-1)和p(zkûxk);3)利用式(10)计算对应样本的重要性权系数;4)对权进行归一化处理,即

状态更新方程为

p(xkûz1:k)=

其中

p(zkûz1:k-1)=

(3)

∫

p(zkûxk)p(xkûz1:k-1)dxk.(4)

w=w

ikik

基于随机采样运算的蒙特卡罗方法可将积分运算转化为有限样本点的求和运算,即状态概率密度分布可用如下经验概率分布近似表述:

dp(x0∶kûz1:k)=N∑Dxi0:k(dx0:k),

i=1

∑w.

j=1

(11)

　　5)利用式(9)对p(xkûz1:k)进行估计.

3　粒子滤波算法存在的主要问题

选取重要性函数的准则是使重要性权重的方差最小.Liu等

[12]

[11]

(5)

若将重要性函数q(x0:kûz1:k)写成如下连乘积形式:

证明了最优重要性函数为

jj=0

j=0

m-1

q(x0:kûz1:k)=q(x0)∏q(xjûx0:j-1,z1:j),(6)

j=1

并假设状态符合马尔科夫过程,在给定状态下,观测

第4期胡士强等:粒子滤波算法综述363

　　记录样本x(km),并将其作为新样本集中的采样,

i=将区间[0,1]按K

态的后验概率,而且对非高斯情况核函数和核带宽系数不能达到最优,它只是一种次优滤波方法.4.3　自适应粒子滤波算法

自适应粒子滤波算法

[20]

∑wj(i=1,2,…,n)分成n个

j=0

小区间,当随机数Ll落在第m个区间Im=(Km-1,K]时,对应样本x

(m)

可有效解决粒子滤波

进行复制.

在采样总数仍保持为n的情况下,权值较大的样本被多次复制,从而实现重采样过程.显然,重采样过程是以牺牲计算量和鲁棒性来降低粒子数匮乏现象.

K(p,q)=

4　粒子滤波算法的改进算法

辅助采样-重采样粒子滤波的实现方法是:选择重要性函数,满足

q(xk,iûz1:k)∝p(zkûLik)p(xkûxik-1)wik-1,(13)其中辅助变量i表示k-1时刻采样粒子的索引.

重要性权值wk为

kjkjkik-1j

=wk∝wk-1q(xk,iûz1:k)

∑p(x)logq(x).

(17)

5　与其他非线性滤波方法的比较

kjkj.

p(zkûLik)

(14)

5.2　Unscented卡尔曼滤波

[23]

EKF更好的滤波性能.

5.3　EKF,UKF,PF3种算法的比较

d(xkûz1:k)≈p

∑wK

i=1

(xk-xik).

(15)

其中K(õ)和h分别是满足

MISE(pd)=

d(xkûz1:k)-p(xkûz1:k)]2dxk.[p

(16)

的核密度函数和核带宽系数.

规则化采样方法可有效缓解重采样过程造成的粒子多样性匮乏问题,在过程噪声较小时可获得较,

364控　　制　　与　　决　　策第20卷

表1　各种滤波算法的适应性范围

状态方程观测方程线性高斯线性非高斯

线性高斯KFPF

线性非高斯

非线性高斯

非线性非高斯PFPFPFPF

6.4　状态监视与故障诊断

PFEKF/UKF/PFPF

非线性高斯EKF/UKF/PF非线性非高斯

PFEKF/UKF/PFPF

　　由贝叶斯估计方法看出,卡尔曼滤波方法是线性高斯系统的最优滤波器,而粒子滤波作为采样贝

6　粒子滤波的应用

6.1　机动目标跟踪

[1]

提出

　　粒子滤波方法作为一种基于贝叶斯估计的非线

1)重要性函数的选取直接影响粒子滤波性能的高低.虽然出现了许多针对实际问题的改进算法,但对通用问题缺乏一般借鉴意义.根据系统的先验,

第4期胡士强等:粒子滤波算法综述365

函数选择,成为目前重要性函数选取研究方向的热点.

[1]GordonN,SalmondD.Novelapproachtonon-linear

andnon-GaussianBayesianstateestimation[J].Procof

InstituteElectricEngineering,1993,140(2):107-113.[2]MacCormickJ,BlakeA.Aprobabilisticexclusion

principlefortrackingmultipleobjects[A].The7thIEEEIntConfonComputerVision[C].Kerkyra,1999:572-578.

[3]CarpenterJ,CliffordP.Improvedparticlefilterfor

nonlinearproblems[J].IEEProcofRadar,SonarandNavigation,1999,146(1):2-7.

[4]DoucetA,GordonN.SequentialmonteCarlomethods

inpractice[M].NewYork:Springer-Verlag,2001.[5]HammersleyJM,MortonKW.Poorman’sMonte

Carlo[J].JoftheRoyalStatisticalSocietyB,1954,16(1):23-38.

[6]HandschinJE.MonteCarlotechniquesforprediction

andfilteringofnon-linearstochasticprocesses[J].Automatica,1970,6(3):555-563.

[7]FearnheadP.SequentialMonteCarlomethodsinfilter

theory[R].Oxford:MertonCollege,1998.[8]SanjeevM,SimonMaskell.Atutorialonparticle

filtersfor

onlinenonlinear/non-GaussianBayesian

tracking[J].IEEETransonSignalProcessing,2002,50(2):174-188.

[9]CrisanD,DoucetA.Asurveyofconvergenceresults

onparticlefilteringmethodsforpractitioners[J].IEEETransonSignalProcessing,2002,50(2):736-746.[10]HaykinSKalman.Filteringandneuralnetworks[M].

NewYork:JohnWileyandSons,2001.[11]DoucetA,

sampling

GodsillS.OnsequentialMonteCarlomethods

for

Bayesian

filtering[R].

Cambridge:UniversityofCambridge,1998:1-36.[12]LiuJS,ChenR.SequentialMonteCarlomethodsfor

dynamicalsystems[J].JoftheAmericanStatisticalAssociation,1998,93(5):1032-1044.

[13]LiuJS,ChenR.Blinddeconvolutionviasequential

imputation[J].

Jof

theAmericanStatistical

576.Association,1995,90(2):567-[14]KitagawaG.MonteCarlofilterandsmootherfornon-Gaussiannonlinearstatespacemodels[J].1-25.[15]PittMK,

ShephardN.Filteringviasimulation:

Jof

theAmerican

Auxiliaryparticlefilters[J].

Jof

ComputationalandGraphicalStatistics,1996,5(1):

StatisticalAssociation,1999,94(2):590-599.[16]BerzuiniC,BestN.Dynamicconditionalindependence

modelsandMarkovchainMonteCarlomethods[J].JoftheAmericanStatisticalAssociation,1997,92(5):1403-1412.

[17]BelvikenE,AcklamPJ.MonteCarlofiltersfornon-linearstateestimation[J].Automatica,2001,37(1):177-183.

(下转第371页)

第4期

参考文献(References)

唐功友等:带有持续扰动非线性系统的前馈-馈反最优控制

[6]BeardRW,

SaridisGN,

WenJT.

371

Galerkin

[1]LindquistA,YakubovichVA.Optimaldampingof

forcedoscillationsindiscrete-timesystems[J].IEEE

TransAutomaticControl,1997,42(6):786-802.[2]TangGY.Feedforwardandfeedbackoptimalcontrol

forlinearsystemswithsinusoidaldisturbances[J].HighTechnologyLetters,2001,17:16-19.

[3]唐功友,赵艳东,陈显利.带正弦干扰的线性时滞系统的

次优控制[J].控制与决策,2004,19(5):529-533.(TangGY,ZhaoYD,ChenXL.Suboptimalcontrolfor

time-delay

linear

systems

under

sinusoidal

disturbances[J].ControlandDecision,2004,19(5):529-533.)[4]LiH,

HuSJ,ChengZ.Multiple-steppredictive

controlforoffshorestructure[J].ChinaOceanEnginee-ring,1999,13:231-246.

[5]MieleA.Optimaltrajectoriesandguidancetrajectories

foraircraftflightthroughwindshears[A].Proc29th

IEEEConfonDecisionandControl[C].Hawaii,1990:737-746.

approximationofthegeneralizedHamilton-Jacobi-Bellmanequation[J].Automatica,1997,33(12):2159-2177.

[7]ChananeB.Optimalcontrolofnonlinearsystems:A

recursiveapproach[J].ComputersandMathematicswithApplications,1998,35(3):29-33.

[8]NishikawaY,SannomiyaN,ItakuraH.Amethodfor

suboptimaldesignofnonlinearfeedbacksystems[J].Automatica,1971,7(6):703-712.

[9]唐功友,曲海鹏,高延铭.一类非线性系统次优控制的

formsforsolutionsofAX-XB=CandX-AXB=Cincompanionmatrices[J].

LinearAlgebraandIts

49.Applications,1984,62(3):19-

　　(上接第365页)

[18]HiguchiT.

MonteCarlofilteringusinggenetics

[27]ChibS,NardariF,ShephardN.MarkovchainMonte

Carlomethodsforstochasticvolatilitymodels[J].Jof316.Econometrics,2002,8(1):281-[28]PapavasiliouA.Adaptiveparticle

2002.

[29]HeinrichA.Applicationsofstatisticalbootstrappingin

finance[R].Oxford:UniversityofOxford,2000.[30]IsardM,BlakeA.Condensation-conditionaldensity

propagationforvisualtacking[J].JofComputerVision,1998,29(1):5-28.

[31]IsardM,BlakeA.Condensation:Unifyinglow-level

andhigh-leveltrackinginastochasticframework[A].ProcoftheFifthEuropeanConfonComputerVision[C].Berlin,1998:893-908.

[32]MaccormickJ,MaccormickF.Stochasticalgorithms

forvisualtracking[M].Paris:TelosPress,2003.[33]MoralesR,PooleD.Real-timemonitoringofcomplex

industrialprocesseswithparticlefilters[R].Orlando:

UniversityofBritishColumbia,2003.[34]KarlssonR,

JanssonJ.

Model-based

statistical

trackinganddecisionmakingforcollisionavoidanceapplication[R].VolvoCar/Control&CommunicationActiveSafety,2003:1-6.

[35]VaswaniN,ChellappaR.Aparticlefilteringapproach

toabnormalitydetectioninnonlinearsystemsanditsapplication

abnormalactivity

detection[R].

filters

with

algorithmoperator[J].JofStatisticalComputation23.andSimulation,1997,59(1):1-[19]MoYW,XiaoDY.Hybridsystemmonitoringand

diagnosingbasedonparticlefilteralgorithm[J].ActaAutomationSinica,2003,29(3):641-648.

[20]FoxD.Adaptingthesamplesizeinparticlefilters

throughKLD-sampling[R].Washington:University

ofWashington,2003:1-27.

[21]DoucetA,GordonN.SequentialMonteCarlomethods

inpractice[M].NewYork:Springer-Verlag,2001.[22]JulierSJ,UhlmannJK.Anewmethodforthe

nonlineartransformationofmeansandcovarianceinfiltersandestimators[J].IEEETransonAutomaticControl,2000,45(3):477-482.

[23]WanEA,VanderMerweR.TheunscentedKalman

filterfornonlinearestimation[J].ProcofSignalProcessing,2000,3(1):153-158.

[24]DoucetA,DavyM.Particlefilteringformulti-target

trackingandsensormanagement[A].The5thIntConfonInformationFusion[C].Annapolis,2002:474-481.[25]HueC,CadreJ,PerezP.SequentialMonteCarlo

methodsformultipletargettrackinganddatafusion[J].IEEETransonSignalProcessing,2002,50(2):309-325.

[26]StorvikG.Particlefiltersforstate-spacemodelswith

thepresenceofunknownstaticparameters[J].IEEEapplications[R].Princeton:UniversityofPrinceton,

粒子滤波算法综述

相关文章