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 the state 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.

Considering a single target tracking problem, ${x_k}$is the target motion state vector at time $k$:

where ${v_k}~N(\mu ,\Sigma )$ and $N(\mu ,\Sigma )$ are noise sequence which have the Gaussian distribution with mean μ and covariance matrix Σ, ${\omega _k}$ is observation noise sequence and is independent of ${v_k}$, $f( \cdot )$ is nonlinear state function, ${z_k}$ is observation vector obtained at time k, and $h( \cdot )$ is nonlinear measurement function. Let ${X_{0:k}} = \{ {x_0},{x_1}, \cdots ,{x_k}\} $ and ${Z_{0:k}} = \{ {z_0},{z_1}, \cdots ,{z_k}\} $ denote the vectors of the motion states and the observation states of target from beginning to time k.

In the following discussion, the notation $p( \cdot )$ is used to denote a probability density function (PDF), for example $x_n^{(i)}~p(x_n^{})$ indicates 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({x_n}|{x_{n - 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 form ${x_n} = \Phi ({x_{n - 1}},{v_n})$, where ${v_n}$ is a noise process.

2)$p({z_n}|{x_n})$. Observation likelihood density, describing the conditional likelihood of observation given state. As before, this relationship could be in the form of an observation model ${z_n} = h({x_n}) + {n_n}$, where ${n_n}$ is a noise process which is independent of ${v_n}$.

3)$p({x_n})$. The prior state probability at t time.

It is assumed that the ${X_{0:n}} = \{ {x_0},{x_1}, \cdots ,{x_n}\} $ is a homogeneous Markov chain, the conditional probability density of ${x_n}$ given by the past states ${x_{0:n - 1}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}})$ only depends on ${x_{n - 1}}$, through the transition density $p({x_n}|{x_{n - 1}})$, and the conditional probability density of ${z_n}$ given by the states ${x_{0:t}}$ and the past observations ${z_{0:n - 1}}$ only depends on ${x_t}$ through the conditional likelihood $p({z_n}|{x_n})$ ^[11].

The objective of filtering is to estimate the posterior density of the state given by the past observations $p({x_n}|{z_{1: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(x_n^{}|z_{1:n}^{})$ is interested. In particle filtering, densities are approximated by a set of samples (particles) $\{ x_n^{(i)}\} _{i = 1}^{{N_p}}$. In the state space, their associated normalized probability weights satisfy $\sum\limits_{i = 1}^{{N_p}} {\{ W_n^{(i)}\} } = 1$. Then the posterior density of the state vector can be approximated as^[13]:

where $\delta ( \cdot )$ is the Dirac Delta function centered at ${x_n}$. The set $W_n^{(i)}$ is the weights of particle set that represent the posterior density at time n, and is estimated recursively from $W_{n - 1}^{(i)}$. The initial particle set $W_0^{(i)}$ is obtained from sampling the prior density ${\pi _0} = p({x_0})$^[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 particles $x_n^{(i)}$ are drawn from an easy sampling function $q( \cdot )$ 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 particles $\{ x_n^{(i)}\} $ is obtained from the generation $\{ x_{n - 1}^{(i)}\} $ by sampling 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 weight $w_n^{(i)}$ is 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 trajectory $x_{0:n}^{(i)}$ of that sample and the history of observations $z_{0:n}^{}$, the corresponding map estimation $p({x_n}|{z_{1:n}})$ is computed ^[20].

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. ${N_r}$samples from the current set, proportion-ally 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 function $p(x_t^{}|{z_{0:t}})$. Therefore, the weights can now be reset as $w_t^i = \frac{1}{{{N_r}}}$. Fig. 1 shows the resampling procedure.

Fig. 1

Fig. 1 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 generating some 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 ${\beta _m}$ is maneuvering parameter and $\bar w_{n - 1}^{}$ is the mean value of $n - 1$ iterative 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.

Fig. 2

Fig. 2 Improved algorithm flow

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),\omega (n)$ is Gaussian distribution with mean 0 and variance 4, 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.

Fig. 3

Fig. 3 Simulation results for four filters

The filter estimation error is shown as Fig. 4.

Fig. 4

Fig. 4 Estimation Errors for four filters

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

Table 1

Table 1 Filtering performance for three filters

Table 1 Filtering performance for three filters Algorithm ConvergeNCE time MSE Mean of error Average valid particle number Standard particle filter 0.221 4 0.026 7 0.635 1 12.843 Weights choice resampling 0.157 85 0.019 62 0.331 63 16.237 Linear optimal resampling 0.168 74 0.027 74 0.312 53 17.357 Improved particle filter 0.144 62 0.011 52 0.254 06 18.412

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.