Paper Menu >>
Journal Menu >>
![]() I. J. Communications, Network and System Sciences. 2008; 1: 1-103 Published Online February 2008 in SciRes (http://www.SRPublishing.org/journal/ijcns/). Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 Particle Filtering with Multi Proposal Distributions Fasheng WANG1,2, Qingjie ZHAO2, Yingbo ZHANG1, Liqun ZHANG2 1Neusoft Institute of Information, Northeastern University, P.R.China 2Beijing Key Lab of Intelligent Information School of Computer Science and Technology, Beijing Institute of Technology, P.R.China E-mail: {wangfasheng, zhangyingbo}@neusoft.edu.cn {zhaoqj, wangfasheng, zhangliqun}@bit.edu.cn Abstract Particle filtering algorithm has been applied to various fields due to its capacity to handle nonlinear/non-Gaussian dynamic problems. One crucial issue in particle filtering is the selection of the proposal distribution that generates the particles. In this paper, we give a novel strategy for selecting proposal distribution. Firstly, divide-conquer strategy is used, in which the particles used are divided into several parts. Afterward, different parts of particles are drawn from different proposal distributions. People can flexibly adjust how many of the particles drawn from specific proposal distributions according to their idiographic requirements. We provide simulation results that show its efficiency and performance. Keywords: Sequential Monte Carlo, Proposal Distribution, Multiple Proposal Distributions 1. Introduction As is known to all, most important real world applications are nonlinear and/or non-Gaussian. Nonlinear filtering problems exist in many fields including statistical signal processing, bio-statistics, economics, and engineering such as communications, radar tracking, sonar ranging, target tracking, car positioning, robot localization, and so on [1]. There are a variety of solutions for these problems, among which the extended Kalman filter (EKF) is well known. This kind of filters is based on linearizing technique that linearize the process model and measurement model by using Taylor series expansions. However, it is likely to diverge when the linearizing approximation methods give poor representations of the nonlinear functions. The unscented Kalman filter (UKF) is another kind of interesting solutions, which is founded on the fact that it is easier to approximate a Gaussian distribution than it is to approximate an arbitrary nonlinear function [12][15]. Unlike the EKF, the UKF does not use the approximated models of the nonlinear process and the observation, but approximates the distribution of the state random variable by using a set of samples. It is shown that the UKF can acquire more accurate estimation results than the EKF can, This work was supported by the National Natural Science foundation of China, Granted NO.60772063 but might lead to notable errors for non-Gaussian distributions. In recent years, particle filters have drawn much attention in adaptive processing of nonlinear and non- Gaussian problems. It has been proved that the performance of particle filter is much better than traditional nonlinear filtering methods, such as the EKF, UKF, etc. [2][3]. The basic idea of particle filtering algorithm is to represent the required probability density function (PDF) by a set of random samples with associated weights. In the past decades, this method has been applied with great success to a variety of nonlinear/non-Gaussian filtering problems that was raised in communication fields, such as channel equalization [4], problems in MIMO wireless communication [5][6], phase tracking [7], problems in digital communication [19] etc. In addition, it is also widely used in vision tracking [3], robot localization [8- 10], positioning and navigating [11], and so on. A key issue in particle filtering algorithm is the selection of the proposal distribution which is generally hard to design. There are many proposal distributions proposed in the literature, among which the EKF [12][13] and the UKF [15] are well-known, as well as the transition prior [16]. Using EKF and UKF as proposal distributions, we get the Extended Kalman Particle Filter (EKPF) and the Unscented Particle Filter (UPF) [12][15], ![]() PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 23 Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 respectively. The famous CONDENSATION algorithm uses transition prior as the proposal distribution [16]. But the EKPF can diverge for strong nonlinearity cases, while the UPF is not applicable to general non-Gaussian model and has very high time cost. The CONDENSATION algorithm does not use the latest incoming information which contains very valuable data. In order to solve the problems that are encountered by several existing particle filters, in this paper, we give a multi-proposal-distribution based particle filter, which is based on the EKF, UKF, and the transition prior. The particles used in the experiments are firstly divided into two parts, with one part (c percent) drawn from the EKF and UKF, another part (1-c percent) drawn from the transition prior. It gives not only higher accuracy but also lower time with proper choice of c. The remainder of the paper is organized as follows. In Section 2, we give a brief introduction of particle filtering algorithm. The multi-proposal-distribution based particle filter (MPD-PF) is given in Section 3. Section 4 shows the simulation results. Conclusions are drawn in Section 5. 2. Particle Filtering We adopt the following dynamical models: ),( 11 −− =kkkk vxfx (1) ),(kkkk uxhz = (2) where xk∈x n R denotes the system state at time k, and zk ∈z n R denotes the observations at time k. The functions k fand k hare the system transition model function and measurement model function respectively. The noise processes are vk and uk, the process noise and measurement noise, respectively. According to the basic idea of particle filters, let N i i k i kwx 1:0 },{ =denotes a random measure used to represent the posterior density function p(x0:k|z1:k). },...,0,{ :0 Nixi k= is a set of support particles with associated weights {i k w, i=0,…,N}, and x0:k show the states up to time k. When N tends to the infinity, the posterior density function can be approximated by: ∑ = −≈ N i i kk i kkk xxwzxp 1 :0:0:1:0 )()|( δ (3) where δ(.) denotes the Dirac delta function. Many of the particle filters rely on the principle of importance sampling [17]. Because it is usually difficult to directly draw particles from the posterior density, we can generate particles from a proposal distribution density function q(), which is also known as an importance function, and the weights are assigned according to: )(/)|( :1:0 ⋅= qzxpw kk i k (4) So the choice of proposal distribution q(.) is of great importance. Assume the particles i k x:0 are drawn from an importance density q(x0:k|z1:k). Considering the following factorization: )|(),|()|( 1:11:0:11:0:1:0 −−− = kkkkkkk zxqzxxqzxq (5) Suppose we have gotten the approximation of the posterior distribution at time k-1, that is, p(x0:k-1|z1:k-1) can be represented by the particle set N i i k i kwx 111:0 },{ =−− , which are drawn from i k x1:0 −~ )|(1:01:0 −− kk yxq. The particle weights are computed by using the formula: )|(/)|(1:11:01:11:01 −−−−− =k i kk i k i kzxqzxpw (6) In the following step, we aim to obtain N i i k i kwx 1:0},{ = using the new observation zk. So long as we get the particles i k x and augment them onto the old particle trajectory, the new trajectory can be acquired. The new particles are generated as follows: ),|(~ :01:0 k i kk i kzxxqx − (7) The recursive equation for calculating weights can be obtained using Bayesian rules: ),|( )|()|( 1 1 1 k i k i k i k i k i kk i k i kzxxq xxpxzp ww − − − ∝ (8) Generally, the generic particle filter uses the transition prior p(xk|xk-1)as the importance density function [12][16]. It has been proved that the proposal distribution ),|(),|( :11:0:11:0 kkkkkk zxxpzxxq−− = is optimal [12]. One of the drawbacks of particle filter is degeneracy problems. After several iterations, all but one particle would probably have negligible weights. In order to solve the problem, the resampling method is introduced [17], [18]. There are several resampling methods, such as systematic resampling, residual resmapling, etc. In this paper, the residual resampling method is used for all the experiments. The generic particle filtering algorithm can be shown as algorithm 1. ![]() 24 F.S. WANG ET AL. Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 3. MPD-Based Particle Filter The particles used are firstly divided into two parts – c percent and 1-c percent. The MPD-PF first uses a mixed Kalman filter, which combines the UKF and the EKF, to draw c percent the particles. Afterwards, it uses its transition prior for another part – 1-c percent. Choice of c can affect the performance of the MPD-PF greatly. But one can choose it flexibly according to practical requirement. For the c percent particles, suppose we have obtained the estimates of the state and the corresponding covariance at time k-1, )( 1 i k x−and )( 1 ˆi k P−. At the next time step k, the UKF is firstly used to update the particles. The sigma points used in this process are calculated using the equation (see [12]), ai k )( 1− χ =[ ai k x)( 1− ai ka ai kPnx )( 1 )( 1)( −− +± λ ] (9) The particles are propagated into the future through the nonlinear models (equation (1) and (2)), ),( )( 1 )( 1 )( 1| vi k xi k xi kkf−−− = χχχ ),( )( 1 )( 1| )( 1| ui k xi kk i kkhZ−−− = χχ (10) The predicted state and corresponding covariance can be obtained, ∑ = −− =a n j xi kkj m j ukf i kkWx 2 0 )( 1|, )()( 1| χ (11) ∑ = −−−−− −−= a n j T ukf i kk xi kkj ukf i kk xi kkj c j ukf i kk xxWP 2 0 )( 1| )( 1|, )( 1| )( 1|, )()( 1| ]][[ χχ (12) where )(m j W and )(c j W are weights of sigma points (see [12] and [14]), na=nx+nv+nu. And, the predicted measurement can be computed using, ∑ = −− =a n jukf i kkj m j ukf i kk ZWz 2 0 )( 1|, )()( 1| (13) If a new measurement zk is obtained, update the predicted estimates as follow, )( )( 1| )( 1| )( ukf i kkkk ukf i kk ukf i kzzKxx −− −+= (14) T kzzk i kk ukf i kKPKPP kk ~~ )( 1| )( ˆ−= − (15) where Kk is the Kalman gain, calculated with equation 1 ~~ − =kkkk zzzxk PPK, ∑ = −−−− −−= a kk n j Ti kk i kkj i kk i kkj c jzz zZzZWP 2 0 )( 1| )( 1|, )( 1| )( 1|, )( ~~ ]][[ (16) ∑ = −−−− −−= a kk n j Ti kk i kkj i kk i kkj c jzx zZxWP 2 0 )( 1| )( 1|, )( 1| )( 1|, )( ~ ~]][[ χ (17) Here, we have obtained state and corresponding covariance estimates through UKF-update process. Consequently, we use the EKF to do the update process with the pre-computed state estimate ukf i k x)( as input. First, predict the state and covariance using the following, )()( )()( 1 )( 1| ukf i k i k ekf i kk xfxfx == −− (18) )()()()( 1 )()( 1| iT kk i k iT k i k i k ekf i kk GQGFPFP += −− (19) The Kalman gain can be calculated, 1)()( 1| )()()()()( 1|][ − −− += iT k ekf i kk i k iT kk i k iT k ekf i kkk HPHURUHPK (20) So, the updated state and covariance estimates at time k are, ekf i kk i kk ekf i kk ekf i kPHKPP )( 1| )()( 1| )( ˆ−−−= (21) Algorithm 1: Generic Particle Filter Step 1. Initialization. k=0 (1) FOR i=0, …, N Draw the states i x0 from the prior )( 0 xp ; END FOR Step 2. FOR k=1, 2, … (1) FOR i=1,…,N Draw ),|(~ 1k i k i k i kzxxqx −; Assign the particle a weight according to Equ.(8); END FOR (2) FOR i=1,…,N Normalize the weights∑= =N j j k i k i kwww 1 /; END FOR (3) Resample Eliminate the samples with low importance weights and multiply the samples with high importance weights, to obtain N random sample i k x:0 which are approximately distributed according to)|( :1:0kk zxp; FOR i=1, …, N, leti k w=1/N, END FOR END FOR Step 3. k=k+1, goto Step2 or end executing. ![]() PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 25 Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 ))(( ˆ)( 1| 1)()()( 1| )( ekf i kkkk iT k ekf i k ekf i kk ekf i kxhzRHPxx − − −−+= (22) where Q is process noise covariance and R is measurement noise covariance. F)(i k, G)(i kand H)(i k, U)( i kare the Jacobians of the process and measurement models, respectively. The estimatesekf i k x)( and ukf i k P)( ˆare the estimates to be computed at time k. For the other 1-c percent of the particles, we can directly compute the state estimates using the state transition model (2), )( )( 1 )( 1| i k i kk xfx−− = (23) The MPD-PF algorithm can be shown as in Algorithm 2. Algorithm 2: The MPD-PF algorithm Step 1. Initialization: k=0 (1) FOR i=1…N, draw the particles )( 0 i x from the prior p(x0) and set: )(]))([( ]0,0,)[(][ ]))([( )( )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 )( 0 RQPdiagxxxxEP xxEx xxxxEP xEx iTaiaiaiaiai TTiaiai Tiiiii ii =−−= == −−= = ENDFOR Step 2. FOR k=1,2,… (1). FOR i=1,…,cN, - Update the particles using the UKF, and obtain the state estimate ukf i k x)( and covariance estimate ukf i k P)( ˆ. - Using the EKF to do the update process: Let)( 1 i k x−=ukf i k x)( , and compute one-step-ahead estimates of the state and the covariance with the equations (18-19). Compute the updated state and covariance estimates with the equations (21-22). Let ukf i k i k ekf i k i kPPxx )()()()( ˆˆ ,== . - Draw) ˆ ,(),|(~ ˆ)()( :1 )( 1:0 )()( i k i kk i k i k i kPxNzxxqx = − //c percent particles are drawn here. - Assign the particle a weight, i k waccording to Equ. (8). ENDFOR (2). FOR i=cN+1,…,N - Directly compute the state estimate using Equ. (23). - Draw)|(~ ˆ)( 1 )( 1| )( i k i kk i kxxpx −− //1-c percent particles are drawn here - Assign the particle a weight. (3). FOR i=1,…,N, Normalize the weights, ∑= =Nj j k i k i kwww :1 / ENDFOR (4). RESAMPLE: Eliminate the samples with low importance weights and multiply the samples with high importance weights, to obtain N random samples i k x:0 approximately distributed according to the posterior PDF p(x0:k|z1:k). FOR i=1,…,N let i k w=1/N. ENDFOR Step 3. k=k+1, goto Step2 or end executing. 4. Experimental Results In this section, we present the experimental results of the MPD-PF algorithm and compare the performance of several existing particle filtering algorithms. The system and the measurement models used in the experiment are: [ ] 11 5.0)1(04.0sin1−− + +− + = kkk vxkx π (24) 30 30 25.0 2.0 2 > ≤ ⎩ ⎨ ⎧ +− + =k k ux ux z kk kk k (25) where vk denotes a Gamma random variable and )2,3( a ζ modeling the process noise, and the measurement noise uk is drawn from a Gaussian distribution N(0,0.0001). 200 particles are used and the process is repeated 100 times for time-steps k=1,..,60. The output of the algorithm is the mean of samples set which can be computed using (22): ∑ = =N j j kk x N x 1 1 ˆ (26) The Mean Square Errors (MSE) of each run is defined as 2/1 1 2 ) ˆ ( 1⎟ ⎠ ⎞ ⎜ ⎝ ⎛−= ∑ = T k kk xx T MSE (27) The program run on a computer with CPU: Celeron 2.66GHz and Memory: 1GB. If c is set to be 0.3, Figure 1 shows the comparison of the estimates to the system state generated from a single run of different particle filters. It is shown that the estimates of the PF and the EKPF bias the true state very large at some time steps, but the UPF and the MPD-PF can improve the performance. Figure 2 shows the comparison of the Root MSE of different particle filters generated over 100 runs. It is clearly shown that the MPD-PF gives the best performance compared to other particle filters, which also ![]() 26 F.S. WANG ET AL. Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 can be seen in Table 1. Table 2 gives the average time of the UPF and the MPD-PF spent after 100 independent runs. The UPF spent longer running-time – 26.8 seconds, while the MPD-PF spent much shorter – 17.6 seconds. So, from Table I and II, we can clearly see that the MPD-PF gives us much higher accuracy with lower time cost, when the parameter c is set to be 0.3. 010 20 30 40 50 60 -5 0 5 10 15 20 Time E(x t ) Estimated state and True state Noisy observations True x PF estimate EKPF estimate UPF estimate MPD-PF estimate Figure 1. Estimates generated by different particle filters Table 1. The means and the variances of the MSE over 100 independent runs (c=0. 3). MSE Algorithm Mean variance PF 0.21374 0.052091 EKPF 0.28551 0.02258 UPF 0.054599 0.004701 MPD-PF 0.016846 5.8999e-006 Figure 3 shows changing trend of the MSE of different particle filters, while the value of parameter c is increasing. From this figure, we can see that MPD-PF gives the best performance whatever the value of c. As to executing time of the particle filters, Figure 4 gives the changing trend of the executing time of the particle filters, from which we can see that, when the value of parameter c is turning bigger, the time cost of MPD-PF is increasing at the same time. At the point of c=0.8, it exceeds the UPF. For users with different requirements, they can flexibly adjust the value of parameter c according to their practical needs. 5. Conclusion In this paper, multi-proposal-distribution based particle filter is introduced. It first takes a divide-conquer strategy, which draws the required particles using different proposals, and can give a better performance than several particle filters. The simulation results show that it can give much higher accuracy than the other particle filters, especially that, it can save a lot of executing time. With proper choice of c, the MPD-PF can supply us a fast and efficient way in dealing with some nonlinear filtering problems in real world applications, such as signal processing problems and nonlinear situations raised in wireless communications, etc. For people with different practical requirements, they can flexibly adjust the value of parameter c in order to obtain ideal results. Table 2. The average time of UPF and MPD-PF used in the experiment Algorithm Time (seconds) UPF 26.8 MPD-PF 16.62 010 20 30 40 50 60 0 0. 2 0. 4 0. 6 0. 8 1 1. 2 1. 4 Time Root MS PF EKPF UPF MPD-PF Figure 2. Root MSE of different particle filters after 100 independent runs (c=0.3). ![]() PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 27 Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 0.10.2 0.3 0.4 0.50.6 0.7 0.8 0.91 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Values of parameter c Root MSE of Different Particle Filters PF EKPF MPD-PF UPF Figure 3. Changing trendline of MSE 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 10 15 20 25 30 value of parameter c Average time of different PFs over 100 runs PF EKPF UPF PF-MPD Figure 4. Changing trendline of execution time. 6. References [1] J. H. Kotecha and P. M. Djuric, “Gaussian Particle Filtering”, IEEE Transactions on signal processing. vol.51, no.10, 2003, pp. 2592-2601. [2] N.J. Gordon, D.J. Salmond, A.F.M. Smith, “Novel approach to nonlinear/non-Gaussian Bayesian state estimation”, IEE. proceedings-F, vol.140, no.2, 1993, pp.107-113 [3] Rui Y, Chen Y., “Better proposal distributions: Object tracking using unscented particle filter”, IEEE Conf. on Computer Vision and Pattern Recognition, 2001, pp. 786−793. [4] H. Kamel, W. Badawy. “Adaptive equalization of a communication channel in a non-Gaussian noise environment”, Proc. of 3rd International IEEE- NEWCAS Conference, Jun. 19-22 2005. pp.395-398 [5] Y.M. Liang, H.W. Luo, X.X. Zhao, H.B. Zhang, C.G. Y. “Nonlinear Channel Estimation Based on Particle Filtering for MIMO-OFDM Systems”, Proc. of International Conference on Communications, Circuits and Systems, Vol. 1. Jun. 2006. pp.347-351. [6] S. Haykin, K. Huber, Zhe Chen. “Bayesian Sequential State Estimation for MIMO Wireless Communications”. Proc. of the IEEE. Vol. 92 Issue 3. Mar. 2004. pp.439-454. [7] Anis Ziadi, Gerard Salut. “Non-overlapping deterministic Gaussian particles in maximum likelihood non-linear filtering- phase tracking application”. Proc. of International Symposium on Intelligent Signal Processing and Communication Systems. 2005. pp. 645-648 [8] FANG Zheng, TONG Guo-Feng, XU Xin-He, “A Robust and Efficient Algorithm for Mobile Robot Localization”. ACTA Automatic Sinica, Vol. 33, NO. 1. Jan. 2007. pp. 48-53. [9] Cody Kwok, Dieter Fox, and Marina Meila, “Real- Time Particle Filters”, Proceedings of the IEEE, vol.92, no. 3, Mar. 2004, pp.469-484. [10] Christian Plagemann, Dieter Fox, Wolfram Burgard, “Efficient Failure Detection on Mobile Robots Using Particle Filters with Gaussian Process Proposals”, proceedings of International Joint Conference on Artificial Intelligence, Hyderabad, India. Jan. 6-12, 2007. pp. 2185-2190. [11] F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson, J. Nordlund, “Particle filters for positioning, navigation, and tracking”, IEEE Transactions on Signal Processing, 2002, pp.425−437. [12] Rudolph van der Merwe, Arnaud Doucet, Nando de Freitas, Eric Wan, “The unscented particle filter”, Technical report. Cambridge University. Engineering Department. 2000. [13] Greg Welch, Gary Bishop, “An Introduction to the Kalman Filter”, Technical Report, TR 95-041, University of North Carolina at Chapel Hill, 2004. [14] Simon J. Julier and Jeffrey K. Uhlmann, “Unscented Filtering and Nonlinear Estimation”, proceedings of the IEEE, vol. 92. no. 3, 2004, pp.401-422. [15] Eric A. Wan and Rudolph van der Merwe, “The Unscented Kalman Filter for Nonlinear Estimation”, proceedings of ASSPCC, 2000, pp.153-158. [16] Michael Isard, Andrew Blake, “Condensation – conditional density propagation for visual tracking”, International Journal of Computer Vision, 1998. pp. 5~28 [17] M. Sanjeev Arulampalam, Simon Maskell, N. Gordon and T. Clapp, “A tutorial on particle filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking.” IEEE Transactions on signal processing, vol.50, no.2, 2002, pp.174-188. ![]() 28 F.S. WANG ET AL. Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103 [18] Arnaud Doucet, “On Sequential Simulation-Based Methods for Bayesian Filtering”, Technical report. Signal Processing Group, Department of Engineering, University of Cambridge, 1998. [19] Tanya Bertozzi, Didier Le Ruyet, Gilles Rigal and Han Vu-Thien, “On Particle Filtering for Digital Communications”, Proc. of 4th IEEE Workshop on Signal Processing Advances in Wireless Communications, 2003, pp570-574. |