一种改进重采样的粒子滤波算

王瑞 肖宇峰 朱鸽

摘要：重采样过程是解决粒子滤波中粒子退化问题的有效手段，但随着算法迭代会引起粒子多样性的丧失。本文提出一种线性组合的重采样算法改进方法，解决多样性问题。具体为：判断有效粒子数，进入重采样过程，得到将淘汰与复制的粒子，并用它们的线性组合作为新的滤波粒子。通过实验证明，此方法对于粒子数不大的情况效果良好。

关键字：粒子滤波；重采样；线性组合；多样性

一、引言

粒子滤波（PF）是一种基于蒙特卡罗思想的概率滤波[1，2]。通过对概率密度函数采样得到一组在状态空间传播的随机样本，来对后验概率密度进行估计。采用概率的方法，用样本均值代替复杂的积分运算，以获得系统状态的最小方差估计。具体过程为：对于平稳随机过程，在K-1时刻获取n个随机样本点，通过状态更新和时间更新来预测K时刻的系统状态。随着粒子数的增加，粒子滤波逐渐逼近最优贝叶斯估计。

PF算法主要步骤有重要性采样、权值更新和重采样过程。重采样过程的引进，解决了粒子退化的问题。其主要方法是当有效粒子数小于阈值时，复制高权值粒子代替要淘汰的低权值粒子，并保持粒子数不变。与此同时，重采样过程带来了粒子多样性的丧失的问题，严重影响了算法的精确度。

本文主要工作是对基本粒子滤波的重采样部分进行改进。以将淘汰的小权值粒子与待复制的高权值粒子的组合产生新粒子，这种方式可避免粒子的重复采用，克服粒子多样性丧失的问题。Matlab仿真证明，本文方法有效，能一定程度改善算法性能。

二、基本粒子滤波算法

对于离散时间动态系统，算法可采用以下模型描述：

狀态方程：xk=fx（xk-1，wk） （1）；观测方程： zk=hkxk，vk （2）

其中，为k时刻的状态，分别为系统噪声和观测噪声。算法的目的是根据观测数据递推的估计出系统状态的后验概率分布。

粒子滤波通过迭代，采用有限的加权样本近似系统状态的后延概率密度。可表示为：px0：kzk=1Ni=1N未（x0：k-x0：ki）（3）

但在实际的问题中，很难从后验概率中直接采样的到粒子，通常采用一种易于采样的已知概率分布函数，我们称之为重要性密度函数，一般选择重要性密度函数为状态转移概率密度函数。基本粒子滤波算法步骤如下：

a.初始化。在k=0时刻，从已知的先验概率分布中采样N个粒子，得到初始样本集{}，i=1，，权重均设置为1/N。

b.状态更新。K-1时刻，粒子集{}通过系统状态方程进行迭代，得到k时刻的状态估计。

c.观测更新。当得到观测量时，对预测的粒子进行权值更新并归一化。wki∝wk-1pzkxkip（xki|xk-1i）q（xki|x0：k-1i，zk） （4），w～ki=wki/i=1Nwki （5），后验概率密度近似为：p（xk|zk）=i=1Nwki未（xk-xki） （6）

d.重采样。计算有效粒子数，当其小于给定阈值时，进行重采样。复制高权值粒子代替低权值粒子，并保持粒子数目不变，归一化权值。

e.输出结果可得到系统的后验概率密度：P～xkzk=1NI=1N未（xk-x～ki） （7）状态估计为xk～=E（x）P～xkzk=xP～xkzkdx=1Ni=1kx～ki （8），令k=k+1，返回b。

三、重采样

为了解决粒子滤波算法退化问题，提高算法精确度，引入了重采样过程。重采样的基本思想是通过复制高权值粒子代替低权值粒子。

通过观测方程更新粒子权值后，计算有效粒子数，当其小于给定阈值时，进行重采样过程。阈值通常设置为粒子总数的2/3，有效粒子数定义为：

Neff=N1+var（w～ki） （9），有效样本越小，说明退化越严重。其中：wki=p（xki|xk-1i）q（xki|x0：k-1i ，z1：k） =（10），通常，近似为： Neff～=1i=1N（wki）2 （11）。

四、改进重采样粒子滤波

在极端情况下，传统重采样算法在经过若干次的迭代后，所有的采样粒子都是一个高权值粒子的副本，严重影响算法性能。解决算法多样性的方法之一是为每个粒子引入马氏链蒙特卡罗方法（MCMC）移动步骤。其基本思想是通过利用马尔科夫传递函数传递粒子，使之位于状态空间中更希望的位置。这种方法弊端明显，增加了算法的计算复杂度，其时间耗费比基本粒子滤波高一倍，影响算法实时性。左军毅等人提出一种自适应的部分重采样方法。由于传统的重采样是对整个粒子集进行重采样，这种过度采样带来了样本匮乏现象，因此作者提出只对一部分粒子进行重采样，最终的粒子集由重采样后的粒子和未采样的粒子构成。这种方法实际上实在退化现象和样本匮乏之间做了适当的折中。提出一种改进的系统重采样方法，即灵敏重采样方法，比较粒子的权值后，仅保留权值较大的粒子，然后基于拟蒙特卡洛方法来繁殖后代，此算法能够有效抑制样本匮乏现象，提高粒子滤波算法的估计精确度。但是该算法的代价仍是增加了计算时间，虽然可以以较少的粒子数来实现算法，但也仅仅能到到有限的精度与时间上的平衡。

本文提出组合重采样算法，充分利用低权值粒子，当需要进行重采样时，通过待复制的高权值粒子和待淘汰的低权值粒子的线性组合产生新的样本点。其组合方式如下：xn=xs+L（xa-xs） （12）。

式中：是通过线性组合产生的新样本点。为重复选择的高权值粒子点，为将淘汰的低权值粒子。若产生的新样本点的权值比原采样点的权值小，L为0到1之间的随机数。

KL距离，是信息论中的相对熵，常用来衡量两个随机分布的相似度。其定义式如下：L=[1Nw]1/m （13）

在基本的粒子滤波中，重采样过程是简单地淘汰与复制粒子完成的，直接丢失了部分粒子信息。而在改进的组合重采样粒子滤波中，是通过线性组合，把将淘汰的粒子信息融合到新产生的粒子中。因此可以用KL距离计算并得到，使用本文改进的算法，总可以使得重采样后的近似概率分布和重采样前的概率分布更接近，从而得到比基本重采样更好地对状态的估计。

五、仿真分析

采用matlab对算法进行仿真研究。系统为一维非线性系统。状态方程和观测方程使用的经典方程，如下：wki>KNnj1/m （14），K（p，q）=xp（x）lgp（x）q（x） （15）

式中和是独立的高斯白噪声序列，且测量噪声的均值为0，方差R=1，，N=50。

实验仿真比较的是基本粒子滤波和本文改进粒子滤波方法得到的 xk=0.5xk-1+2.5xk-11+xk-12+8cos[1.2（k-1）]+ wk-1 （16）

六、结束语

针对基本粒子滤波的粒子多样性问题。本文提出了一种基于线性组合重采样的粒子滤波方法。从实验仿真可以看出，此方法在一定程度上解决了多样性问题，相比于基本粒子滤波，在粒子数量不大时具有更好地性能。但当粒子数量较多时算法优越不明显，值得进一步的研究。

参看文献：

[1]朱志宇.粒子滤波算法及其应用[M].北京：科学出版社，2010：4-8，114-125.

[2]付梦印，邓志红，闫丽萍.Kalman滤波理论及其在导航系统中的应用[M].2版.北京：科学出版社，2010：185-202.