Improved Resampling Procedure Based on Genetic Algorithm in Particle Filter

ZHANG Min, JIA Hai-tao, and SHEN Zhen

(1. Library, University of Electronic Science and Technology of China Chengdu 611731;2. Research Institute of Electronic Science and Technology, University of Electronic Science and Technology of China Chengdu 611731)

Improved Resampling Procedure Based on Genetic Algorithm in Particle Filter

ZHANG Min1, JIA Hai-tao2, and SHEN Zhen2

(1. Library, University of Electronic Science and Technology of China Chengdu 611731;2. Research Institute of Electronic Science and Technology, University of Electronic Science and Technology of China Chengdu 611731)

Particle filtering is a nonlinear and non-Gaussian dynamical filtering system. It has found widespread applications in detection, navigation, and tracking problems. The strong maneuverability of target tracking brings heavy impact on particle attributes in resampling process of particle filters, such as, particle state, particle weights, and so on. This paper proposes a new particle filter algorithm based on genetic algorithm optimization. This algorithm combines the hereditability and aberrance of the genetic algorithm into the resampling procedure of particle filter to improve the adaptability of maneuvering target tracking.

genetic algorithm; maneuvering target tracking; nonlinear filtering; particle filter; particle resampling

Target tracking is used in many application areas, such as the defense system, radar system, sonar system, aeronautical system, satellite system, and autonomous robots[1]. For anyone target tracking system, it must solve two basic tasks. One is the accurate estimation procedure, which needs to infer the accurate estimation of target position from noise measurement data. The other is predicting the target position in the next time that can be used to control the tracker to catch the target[2]. So the kernel problem of target tracking is to estimate the states of the moving target, such as position, velocity, and acceleration. Most target tracking algorithms belong to Bayesian theoretic, such as Kalman filter and particle filter, which they are popular Bayesian filters for target tracking because of their probabilistic nature[3].

The particle filter algorithm was first proposed in Ref.[4]. In recent years, the particle filter (PF), as an effective estimator for the nonlinear filtering problem, has been widely used in many fields, including signal processing, biostatistics, economics, and engineering.

The kernel of particle filters is designing the posterior probability density functions based on a sample (or particle). This allows the filter to handle the nonlinearity of system, as well as the non-Gaussian nature of noise processes.

PF can sufficiently estimate the system states when the number of particles (i.e., estimations of thestate vectors that evolve in parallel) is large. In Ref.[5], a particle filtering algorithm for tracking was introduced, which focuses on geometric properties of the sensor network configuration, and the algorithm was derived from geometry. In Ref.[6], a tracking method was proposed that first estimated the positions of a target in its most recent past and then fit them with a piece-wise trajectory. In Ref.[7], another method for distributed tracking in binary sensor networks was developed, which was derived by using hidden state estimation and the Viterbi algorithm.

Up to today, particle is one of the most success non-liner filters. But there are some optimization researches in maneuvering target tracking. During tracking strong maneuvering targets, continuous or strong motor will take heavy impacts on the particle filter re-sampling process. Concisely to say, this strong mobility or continuous motor will make the particle weights that can correctly estimate target state turn smaller, or even be abandoned, and the particle weights which have not contribution even be increased infinitely, and this group of particles cannot correctly estimate the target state. So this paper proposes a new particle filter algorithm based on genetic algorithm optimization. This algorithm takes the descendiblity and aberrance of the genetic algorithm into particle filter resampling procedure, which seems to more adapt the maneuvering target tracking.

1 Particle Filter Theory

Considering a single target tracking problem, xkis the target motion state vector at time k:

wherevk～N(μ,Σ)andN(μ,Σ)are noise sequence which have the Gaussian distribution with mean μ and covariance matrix Σ, ωkis observation noise sequence and is independent of vk, f(?)is nonlinear state function, zkis observation vector obtained at time k, and h(?)is nonlinear measurement function. Let X0:k={x0,x1,,xk} and Z0:k={z0,z1,,zk}denote the vectors of the motion states and the observation states of target from beginning to timek.

In the following discussion, the notation p(?)is used to denote a probability density function (PDF), for exampleindicates that the particles are distributed according to the pdf of the true state[9].

Using statistics theoretics, the system is completely described as follows[10]:

1)p(xn|xn?1). The state transition probability density function. It desribes the evolution of the system from time n?1 to n. Alternatively, the same could be described with a state transition model of the formxn=Φ(xn?1,vn), where vnis a noise process.

2)p(zn|xn). Observation likelihood density, describing the conditional likelihood of observation given state. As before, this relationship could be in the form of an observation model zn=h(xn)+nn, where nnis a noise process which is independent of vn.

3)p(xn). The prior state probability atttime.

It is assumed that the X0:n={x0,x1,,xn}is a homogeneous Markov chain, the conditional probability density of xngiven by the past states x0:n?1=(x0,x1,,xn?1) only depends on xn?1, through the transition densityp(xn|xn?1), and the conditional probability density of zngiven by the statesx0:tand the past observationsz0:n?1only depends on xtthrough the conditional likelihood p(zn|xn)[11].

The objective of filtering is to estimate the posterior density of the state given by the past observationsp(xn|z1:n). As new observations arrive, a recursive update of the posterior density is given by the recursive Bayesian filter. It is defined as[12]:

In most applications, the posterior density of the state vector p(xn|z1:n) is interested. In particle filtering, densities are approximated by a set of samples (particles)In the state space, their associated normalized probability weights satisfy

Then the posterior density of the state vector can be approximated as[13]:

where δ(?) is the Dirac Delta function centered atxn. The setis the weights of particle set that representthe posterior density at timen, and is estimated recursively fromThe initial particlesetobtained from sampling the prior densityπ0=p(x0)[14].

In general, it is difficult to sample directly from the full posterior density. To overcome this difficulty, the method of importance sampling is used. The particlesare drawn from an easy sampling function q(?) called importance density. So the normalized weights is written as[15]:

The importance density is factorized as follows[16]:

So the weights can be updated sequentially as[17]:

One of the most common particle-filtering algorithms is the sampling importance resampling (SIR) filter. It updates the sample sets that represent the posterior about the map and the trajectory of the vehicle. The process can be summarized by the following four steps[18].

1) Sampling: The next generation of particlesis obtained from the generationsampling from the proposal distribution π. Usually, a probabilistic motion model is used as the proposal distribution.

2) Importance weighting: According to the importance sampling principle, an individual importance weightis assigned to each particle. The weights account for the fact that the proposal distribution π is, in general, not equal to the target distribution of successor states.

3) Resampling: Particles are drawn with the replacement proportional to their importance weight. This step is necessary, since only a finite number of particles are used to approximate a continuous distribution. Furthermore, resampling allows us to apply a particle filter in situations in which the target distribution differs from the proposal. After resampling, all the particles have the same weight[19].

4) Map estimation: For each particle, based on the trajectoryof that sample and the history of observationsz0:n, the corresponding map estimation p(xn|z1:n) is computed[20].

2 Improved Algorithm

Without the resampling step, the basic particle filter would suffer from the sample depletion. This means that all particles not a few will have negligible weights after a while. The resampling step resolves the reduction of the effects of degeneracy. The basic idea of resampling is to drop particles that have small weights and to concentrate on those which have large weights. A new set of samples is generated by resampling the set of samples and taking out the particles that have small weights.rNsamples from the current set, proportionally to their weights. In this new set, for instance, the samples with the lowest probabilities will disappear. Next, the weights associated with the samples are scaled in order to represent the probability associated with each sample. In fact the resulting set of samples is an independency density sample from the discrete posterior probability functionp(xt|z0:t). Therefore, the weights can now be reset asFig. 1 shows the resampling procedure.

The common resampling procedure would duplicate the old ones that have high weights, which might lead to a loss of diversity (named sample impoverishment). It is very severe and in a poor way that all particles may collapse at a single point with a few iterations if the process noise is very small. Especially there is some mutation in target state when it maneuvers. Without considering this mutation, the particles will not represent the posterior density of target state, and would generate degeneracy of particles.

Aiming at the resampling step, this paper proposes an improved algorithm whose main idea is generatingsome aberrance particles in the resampling procedure. Once the target state has been maneuvered, some aberrance particles would work well and have high weights, which will increase the diversity and make the particle filter suit to maneuvering target tracking. Figure 2 shows the algorithm flow.

The improved algorithm detail step is:

1) Sorting particles into three types: the normal particle, aberrance particle, and best particle. The best particles would maintain its state in the resampling procedure, while the aberrance particle would randomly alter its state.

2) Evaluating the maneuvering. Here a maneuvering parameter is used to evaluate the target maneuvering. The function of maneuvering parameter is:

where βmis maneuvering parameter andis the mean value of n?1iterative loop weights.

3) If the maneuvering parameter is beyond the evaluation threshold, there might have some target maneuvering. The resampling procedure would augment the weights of the aberrance particles. Whereas, resampling procedure would debase the weights of the aberrance particles.

4) Recording the best particle’s state in every iterative loop. The resampling procedure would eliminate the best particle which is no longer the best in three iterative loops.

5) If the maneuvering parameter is beyond the evaluation threshold, the resampling procedure would revive the best particle record in three iterative loops.

The main idea of this improved algorithm is taking the aberrance and descendiblity of the genetic algorithm to increase the diversity of the resampling procedure in order to adapt to maneuvering target tracking.

3 Simulation

For validating the proposed algorithm, this paper takes a filter simulation for a maneuvering target tracking.

Set the nonlinear state function as:

and the observation function:

where v(n),ω(n) is Gaussian distribution with mean 0 and variance4,0.01. The standard particle filter, weights choice resampling (WCR filter), linear optimal resampling (LOR filter), and the improved filter are used to estimate the target state. Fig. 3 shows the simulation results.

The filter estimation error is shown as Fig. 4.

At the same time, the Kalman filter is simulated. The performances of three filters are shown in Table 1.

4 Conclusion

This paper presents a new particle filter algorithm based on genetic algorithm optimization. This algorithm takes the descendiblity and aberrance of the genetic algorithm into particle filter resampling procedure, which seems to be more adaptive to the maneuvering target tracking. The simulation proves that the improved algorithm suits maneuvering target tracking.

Reference

[1] ARORA A. A line in the sand: a wireless sensor network for target detection, classification, and tracking[J]. Comput Netw, 2004, 46(5): 605-634.

[2] BUGALLO M F, LU T, DJURI′C P M. Target tracking by multiple particle filtering[C]//Proceedings of IEEE Aerospace Conference. Big Sky, MO, USA: IEEE, 2007: 153-156.

[3] DJURI′C P M, LU T, BUGALLO F. Multiple particle filtering[C]//Proceedings of the IEEE 32nd International Conference on Acoustics, Speech and Signal Processing (ICASSP’2007). Honolulu, Hawaii, USA: IEEE, 2007: 1181-1184.

[4] ISARD M, BLAKE A. Condensation-conditional density propagation for visual tracking[J]. IJCV, 1998, 29(1): 5-28.

[5] ASLAM J, BUTLER Z, CONSTANTIN F V, et al. Tracking a moving object with a binary sensor network[C]//Proc 1st Int Conf Embedded Networked Sensor Syst. Los Angeles, CA, USA: [s.n.], 2003:150-161.

[6] KIM W, MECHITOV K, CHOI J Y, et al. On target tracking with binary proximity sensors[C]//Proc 4th Int Symp Inf Process Sensor Netw. Los Angeles, CA, USA: IPSN, 2005.

[7] OH S, SASTRY S. Tracking on a graph[C]//Proc 4th Int Symp Inf Process Sensor Networks. Los Angeles, CA, USA: IPSN, 2005.

[8] GRISETTI G, STACHNISS C, BURGARD W. Improvedtechniques for grid mapping with rao-blackwellized particle filters[J]. IEEE Transactions on Robotics, 2007, 23(1): 34-46.

[9] LASKA B N M, BOLIC M, GOUBRAN R A. Particle filter enhancement of speech spectral amplitudes[J]. IEEE Transactions on Audio, Speech, and Language Processing, 2010,18(8): 2155- 2167.

[10] GUSTAFSSON F. Particle filter theory and practice with positioning applications[J]. IEEE A&E Systems Magazine. Part 2: Tutorlals-Gustafsson, 2010, 25(7): 53-81.

[11] MARTINEZ-ESPLA J J, MARTINEZ-MARIN T, LOPEZ-SANCHEZ J M. A particle filter approach for insar phase filtering and unwrapping[J]. IEEE Transactions on Geoscience and Remote Sensing, 2009, 47(4): 1197-1211.

[12] SANKARANARAYANAN A C, SRIVASTAVA A, CHELLAPPA R. Algorithmic and architectural optimizations for computationally efficient particle filtering[J]. IEEE Transactions on Image Processing, 2008, 17(5): 737-748.

[13] CHENG Qi. An efficient two-stage sampling method in particle filter[J]. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(3): 2666-2672.

[14] WANG Ya-feng, ZHANG You-an, LIU Hua-ping, et al. Central difference particle filter applied to transfer alignment for sins on missiles[J]. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(1): 375-387.

[15] CLOSAS P, BUGALLO M F. Improving accuracy by iterated multiple particle filtering[J]. IEEE Signal Processing Letters, 2012, 19(8): 531-534.

[16] HU Xiao-li, SCHON T B, LJUNG L. A basic convergence result for particle filtering[J]. IEEE Transactions on Signal Processing, 2008, 56(4): 1337-1348.

[17] NICOLI M, MORELLI C, RAMPA V. A jump markov particle filter for localization of moving terminals in multipath indoor scenarios[J]. IEEE Transactions on Signal Processing, 2008, 56(8): 3801-3809.

[18] SEONG-HOON P W, WAEL W M, FARID G. A kalman/particle filter-based position and orientation estimation method using a position sensor/ inertial measurement unit hybrid system[J]. IEEE Transactions on Industrial Electronics, 2010, 57(5): 1787-1798.

[19] SUTHARSAN S, KIRUBARAJAN T, LANG T, et al. An optimization-based parallel particle filter for multitarget tracking[J]. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(2): 1601-1618.

[20] BRANKO R, SANJEEV A. Bernoulli particle filter with observer control for bearings-only tracking in clutter[J]. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48(3): 2405- 2415.

編 輯 黃 莘

基于遺傳算法改進(jìn)的粒子濾波重采樣模型

張 民1，賈海濤2，沈 震2
(1. 電子科技大學(xué)圖書館 成都 611731；2. 電子科技大學(xué)電子科學(xué)技術(shù)研究院 成都 611731)

提出一種基于遺傳算法改進(jìn)的新粒子濾波算法，該算法對于每次迭代計(jì)算出的最差粒子并未簡單地進(jìn)行丟棄，而是將這些最差粒子利用生物遺傳中的遺傳性和變異性將其進(jìn)行修正。該算法利用最差粒子數(shù)據(jù)與種群中特殊數(shù)據(jù)進(jìn)行交叉變異方法來增強(qiáng)粒子種群中的多樣性，從而有利于粒子濾波對機(jī)動目標(biāo)的跟蹤；同時(shí)保留部分粒子在未來進(jìn)行喚醒也體現(xiàn)了多樣性。該算法更有利于實(shí)現(xiàn)粒子濾波在機(jī)動目標(biāo)跟蹤的適應(yīng)性，提高其跟蹤效果。

遺傳算法; 機(jī)動目標(biāo)跟蹤; 非線性濾波器; 粒子濾波; 重采樣

TN953

A

10.3969/j.issn.1001-0548.2015.03.005

2014 ? 09 ? 02；

2015 ? 04 ? 27

國家自然科學(xué)基金(61172117)

張民(1969 ? )，男，高級工程師，主要從事計(jì)算機(jī)網(wǎng)絡(luò)、智能計(jì)算等方面的研究.

date：2014 ? 09 ? 02; Revised date: 2015 ? 04 ? 27

Foundation：Support by the National Science Foundation of China(61172117)

Biography：ZHANG Min was born in 1969, and his research interests include computer network and computational intelligence.