Information Technology Journal

Year: 2010 | Volume: 9 | Issue: 5 | Page No.: 942-948
DOI: 10.3923/itj.2010.942.948

Out-of-Sequence Measurement Algorithm Based on Gaussian Particle Filter

Wei Wang, Xin-Han Huang and Min Wang

Abstract: Out-of-sequence-measurements problem tend to arise in multi-sensors target tracking, due to communication delays and varying signal pre-processing time. A number of studies have addressed the processing of out-of-sequence-measurements when the target dynamics and measurement models are linear or nonlinear. To solve this problem more effectively, a novel out of sequence measurement processing algorithm is developed and presented in this study. It based on sequential Bayesian formula and Gaussian particle filter. In essence, this algorithm uses importance sampling to update the posterior means and their covariances and also approximates the posterior distributes by single Gaussians. Both theoretical analysis and simulation results show that it has low complexity, its performance is consistent with standard sequential processing algorithm and it is asymptotically optimal as numbers of particles tends to infinity.

Keywords: Out-of-sequence measurement, sequential Bayesian estimation and Gaussian particle filtering

INTRODUCTION

A typical structure of multi-sensors target tracking structure is the centralized tracking structure, in which all measurements from the sensors are sent to the tracking centre for data fusion. Ideally, all sensors make their own measurements simultaneously and then all these measurements are sent to the tracking centre at the same time for synchronistic fusion. Thus, system tracks are updated in time. However, due to communication delays and variable signal pre-processing time, all measurements from sensors do not always arrive at the centre simultaneously, which can lead to Out-of-Sequence Measurements (OOSMs) problem. Thus, once a measurement arrives, the system tracks are to be updated. The OOSMs problem exists in some multi-sensors systems (Van der Merwe et al., 2004; Jung and Tsiotras, 2007; Bar-Shalom, 2002; Subramanyam and Prasad, 2006; Cheng et al., 2007). In this case, though the standard filtering algorithms for in-sequence measurements are still valid after OOSMs are abandoned, the tracking performance can become deteriorated/poor. Therefore, special algorithms for tackling the OOSMs problem should be put forward. Here, we assume that each measurement adheres to a time stamp in the OOSMs problem discussed here.

Since, the OOSMs problem is identified, researchers have designed a number of optimal and suboptimal algorithms. The most naive solution is to use buffering and measurement reprocessing to handle OOSMs. However, the computation and memory requirements of the method are very sensitive/great. Hilton et al. (1993) proposed an approximation algorithm, i.e., B1 algorithm. Subsequently, Bar-Shalom (2002) improved it and introduce an optimal algorithm, A1 algorithm. However, both of these algorithms assume that the latent/lag is less than or equal to a sampling interval. Recently, multi-lag OOSM algorithms (Challa et al., 2003; Bar-Shalom et al., 2004; Hong et al., 2003; Zhang et al., 2002; Shen et al., 2009a, b; Orton and Marrs, 2005) are also put forward. Among them, there are several algorithms (Zhang et al., 2002; Mallicka and Zhang, 2005) are optimal. Challa et al. (2003) used the fixed-lag smoothing framework to handle the OOSMs problem in clutter environments. More recently, Bar-Shalom et al. (2004) proposed two more economical and practical algorithms, Al1 algorithm and Bl1 algorithm, by defining an equivalent measurement. These algorithms mentioned above are mostly aimed at linear dynamic models and linear/nonlinear measurement model with additive Gaussian white noises. At present, a common characteristic of almost all OOSM processing algorithms is that all OOSMs will be indiscriminatingly incorporated and fused when they arriving at the tracking centre. However, not all OOSMs contribute to improvement on tracking performance. Therefore, Tasoulis et al. (2009) proposed threshold techniques to select useful OOSMs, which can save computational costs while maintaining near optimal performance.

Particle filter can directly use non-linear state space model to achieve good tracking performance. In the particle filter, the posterior distribution is approximated as a weighted set of particles which are sampled from the proposal distribution. Through properly placed and propagated particles, the posterior distributions can be updated sequential over time. Though theoretically particle filter provided optimal results asymptotically as the number of particles tend to infinity, it has a serious particles deprivation problem. However, the so-called resampling technology can counter the problem. Hence, the particle filtering generally consists of three steps: sampling, weighting and resampling. Through the proper selection of the proposed distribution, the use of sampling-resampling steps and a set of weighted random sampling to approximate the posterior densities, Bayesian updating, the state estimation can be obtained. Ortan and Marrs (2005) first extend the particle filtering algorithm to tackle multi-targets tracking problem with arbitrary delayed OOSMs. Its computational costs do not increase with increase of the number of lags. However, a large quality of particles and weights need to be stored in advance in this algorithm. Kotecha and Djuric (2003a, b) proposed Gaussian particle filter which uses importance sampling to update the posterior means and their covariances and also approximates the posterior and priori distributions by Gaussians. The Gaussian filter is asymptotically optimal in the limit of an infinite number of particles. As it has dispensed with re-sampling, its computational costs are lower than particle filter, besides more suitable for parallel implementation. In addition, the performance of Gaussian particle filter is superior by far to Extended Kaman Filter (EKF) and Unscented Kalman Filter (UKF) (Kotecha and Djuric, 2003a, b).

This study introduces a novel out-of-sequence measurement processing algorithm based on Gaussian particle filter. In essence, this algorithm uses importance sampling to update the posterior means and their covariances and also approximates the posterior distributed by single Gaussians. Both theoretical analysis and simulation results show that it has low complexity, its performance is consistent with standard sequential processing algorithm and it is asymptotically optimal as the number of particles tends to infinity.

FORMULATION OF THE PROBLEM

Consider a discrete-time nonlinear state space model:

where, x_n is the unobserved target state vector at time n, w_{n, n-1} is the cumulative process noise vector form time n-1 to time n, f_n,n-1( ·) is the discrete-time nonlinear state transition function, z_n is the sensor measurement vector at time n, v_n is the measurement noise vector, h( ·) is the nonlinear function of the unobserved target state vector.

We assume that no measurement is received at initial time 0 and there is only a prior distribution of the target state p(x₀). Additionally, we assume that the prior distribution of the target state, the process noise vector and the measurement noise vector are uncorrelated with each other.

Let, Z^0:k = {z_i}^k_i=0 be the set of in-sequence measurement sequence received by tracking centre up to time k. We assume that the posterior density of the target state:

can be obtained by using the prediction equation:

Then, we can use some specified performance criteria to obtain the target state estimation at time k. Thus, the filter generalize the set of target state estimations:

Subsequently, we receive an l-step-lag OOSM z_d, where, k-l-1 ≤d<k-l. Next, we will use the OOSM z_d to update the posterior density p(x_n |Z^0:n) in order to get the latest posterior density.

Further, the corresponding state estimation:

can be obtained.

REVIEW OF GAUSSIAN PARTICLE FILTERING

The Gaussian particle filer, also known as the GPF, is thoroughly described by Kotecha and Djuric (2003a, b). The formulation of Kotecha and Djuric (2003a, b) is repeated here, to prepare for deriving the novel OOSM processing algorithm. Gaussian particle filtering calculations for one sample interval are proposed in this section. After the GPF first approximate the filtering and predicting distributions in Eq. 3 and 4 as Gaussians, it uses importance sampling/Monte Carlo integral to calculate the corresponding integrals.

The Gaussian particle filter starts with and and it performs time update and measurement update calculations to determine and . The prior density and likelihood function in GPF algorithm are approximated to Gaussians, too.

Firstly, we use the posterior density:

to general a set of samples, denoted as . Secondly, after substituting a sample into the prior density , we can accordingly sample a particle from . Last, the set of sample can be obtained. Subsequently, we will calculate the prior estimation and its covariance , that is:

Thus, we can approximate the prior density as:

Next, we sample particles, denoted as , from the importance function , then calculate corresponding weight of particle x_s^(j) as:

and normalize weight as:

Eventually, the updated posterior estimation and its covariance can be calculated as:

Thus, we can approximate the prior density as:

For GPF, a simple choice for the importance function is:

since, samples from this density can be easily obtained. Another choice is where, and are obtained from the measurement update step of the EKF or from UKF.

DERIVATION OF GAUSSIAN PARTICLE FILTERING ALGORITHM WITH OOSMs

The goal of this section is to derive Gaussian particle filtering algorithm dealing with OOSMs (OOSM-GPF), based on Eq. 5. After we use the GPF mentioned earlier to process the set of in-sequence measurements Z^0:k and obtain the state estimation and its covariance , the delayed measurement z_d arrive at the tracking centre. Because the delayed measurement z_d is observed before time k, the standard GPF become invalid now. We develop here the OOSM-GPF algorithm to processing the OOSMz_d. As is mentioned by Orton and Marrs (2005) because the particles may present any posterior density of interest, the particle filter can be extended to the case of OOSM.

The OOSM-GPF can be derived from the Eq. 5. Firstly, we use the importance function to generate a set of samples, denoted as . Secondly, we calculate the corresponding weights using equation:

and normalize weight as:

Finally, the updated posterior estimation and its covariance can be calculated as:

In order to demonstrate the validity and correctness of algorithm above, theorem 1 is presented as follows.

Theorem 1: Assume that at time k, is known up to a proportionality constant. On receiving the OOSMz_d, the OOSM-GPF measurement updates the filtering distribution with Monte Carlo integration:

Then, the rth moment of in Eq. 13 converges almost surely to .

Proof: The process of proof is similar to Kotecha and Djuric, 2003a, b). From Eq. 10 and 11, the rth moment is taken as:

where, the convergence is with probability one as M→ ∞.

We assume that the target dynamic model is linear, that is:

Correspondingly, in Eq. 10, if we obtain the information contained in the state x_k, then the information about the set contained in the set Z^0:k will become redundancy. Besides, the measurement noise sequence contained in the set Z^0:k is uncorrelated with both the state x_k and the measurement z_d, when the process noise and measurement noise are Gaussian, so we can get:

Thus, we can get that:

We can see that when weight Eq. 15 is taken, one need to calculate the likelihood function:

That is to say, the backward predict estimation need to be calculated first. If the target dynamic model is linear, that is:

then we can get a backward predict estimation:

For the OOSM-GPF, a simple choice for the importance function:

An alternative is where, and are obtained from the measurement update step of the EKF with OOSMs or from UKF with OOSMs.

DISCUSSION

From theorem 1, we can deduce that divergence can be avoided by using the OOSM-GPF algorithm unlike other OOSM extended kalman filtering (OOSM-EKF) algorithms (Bar-Shalom, 2002; Bar-Shalom et al., 2004) and that the OOSM-GPF algorithm provides more accurate estimates of the first two moments as the number of particles tend to infinity than other OOSM-EKF algorithms. These OOSM-EKF algorithms provide only the same results as the in-sequence processing algorithms based on EKF at most. However, Simulation results in section VI show that the OOSM-GPF algorithm has almost same results as the in-sequence processing algorithm based on GPF. Although, the EKF have been successfully implemented in some nonlinear problems, but when the model is highly nonlinear or when the posterior distributions are multimodal, it provides poor approximations or even diverges. In addition, the performance of Gaussian particle filter is superior by far to the EKF and the UKF (Kotecha and Djuric, 2003a, b).

Both the OOSM-PF and OOSM-GPF algorithms use importance sampling to obtain particles. Unlike the OOSM-PF algorithm, resampling is not required in the OOSM-GPF algorithm. In the OOSM-PF algorithm, we must use the so-called resampling technology to counter the particles deprivation problem. However, it may be computationally expensive. Hence, the OOSM-GPF algorithm have a computational advantage over the OOSM-PF algorithm. In addition, resampling is not suitable for parallel operation. Hence, the OOSM-GPF algorithm is more amenable for fully parallel implementation in VISL.

Because of the use of the weighted set of particles, the computation time for the OOSM-GPF and the OOSM Particle Filtering (OOSM-PF) algorithms (Orton and Marrs, 2005) is much higher than the OOSM-EKF algorithm. However, when we implement the OOSM-GPF and OOSM-PF algorithms in parallel, their computation times can reduce much. Due to the additional resampling required in the OOSM-PF algorithm, the OOSM-GPF has much less a computation time than the OOSM-PF algorithm.

Theorem 1 demonstrates that we can estimate all moments by using importance sampling. Hence, following our theorem, the posterior distribution related to OOSM can be approximated by more accurate distributions other than Gaussian. For example, Gaussian mixtures approximation can be considered.

SIMULATION RESULTS

We only consider the bearings-only tracking problem here. We assume a dynamic target is tracked with two sensors of the same type and sample rate in 2-dimension Cartesian coordinate system. The two sensors S1 and S2 are both still and are located on (10 m, -10 m) and (10 m, 10 m), respectively. The motion of real target is uniform linear motion. The initial state of real target is:

Target dynamic model:

is taken to be a CV model with the system transition matrix:

where, is the target state vector, is the target ’s position vector in 2-dimension Cartesian coordinate system, is the target ’s velocity vector in 2-dimension Cartesian coordinate system and is the zero-mean, uncorrelated, discrete-time Gaussian white noise process with its covariance:

where, q is Process noise spectral density.

Measurement model is taken as:

where, is the position of sensor i, θⁱ_n is the measurement of sensor i, w_n,n-1 is the zero-mean, uncorrelated, discrete-time Gaussian white measurement noise with variance σ²_v.

Assuming that initial target state and its covariance are and , respectively. The process noise spectral density is set to q = 0.0001 m²/sec³. The sampling cycle of each of sensors is T_n,n-1 = 3 sec. The standard deviation of bearing measurement is σ_v = 0.02 rad. We here use 10000 particles in the simulation scenario and the posterior p(x_k |Z^1:k) as the proposal distribution.

We consider four different simulation scenarios and every scenario consists of 14 measurements with an OOSM with different lags at the end. The 14 measurements observed by sensors S1 and S2, respectively. Every scenario with different lag is according to the corresponding line in Table 1. The first column in Table 1 show different lag step. We use time stamps of the measurements to denote corresponding measurements in Table 1 and every measurement has own sensor ID. Time stamps of each line are arranged according to the order they arrive at the centre. The last column represents OOSMs with different lags. 200 Monte Carlo run are used for all three algorithms used, including abandonment of the OOSM, GPF measurement reprocessing and OOSM-GPF processing, for every scenarios.

Table 2 shows traces of covariances of state estimation error at final time t = 20.5 sec for following cases:

The RMS errors for target position and velocity among three algorithms are compared at the final state estimate at time t = 20.5 sec in Table 3.

From Table 2 and 3, we can see that the differences of RMS error and that of traces of covariances between GPF measurement reprocessing and OOSM-GPF updating are fairly small. But, we can also see that abandoning the OOSM can generalize large errors and the effect of abandoning the OOSM becomes lower with the number of lag is increase.

Table 4 shows that Normalized Estimation Error Squared (NEES) (Bar-Shalom et al., 2001) for the final state estimates at time t = 20.5 sec in the same scenarios. The 95% probability region for the NEES is, based on the distribution (200 runs with a 4-dimensional target state) is (3.6176, 4.4014). The results for the new algorithm OOSM-GPF and the algorithm processing OOSM in sequence fall in this region, that is to say, their state estimates are both consistent. However, the algorithm abandoning the OOSM doesn ’t yield similar result.

All results above show that the algorithm OOSM-GPF performs as well as the in-sequence processing.

CONCLUSION

In muliti-sensors target tracking systems, out-of-sequence measurements problem tend to emerge as a result of communication delays and varying signal pre-processing times. Based on the sequential Bayesian formula and Gaussian particle filter, this study presents a novel out-of-sequence measurement processing algorithm, which uses importance sampling to update the posterior means and their covariances and also approximates the posterior distributes by single Gaussians. Both theoretical analysis and simulation results demonstrate the efficiency of the new algorithm. It has low complexity and is asymptotically optimal in the limit of an infinite number of particles. Its performance is consistent with standard sequential processing algorithm. However, the backward predicted values of current particle state are needed in the computation of importance weights. Future work should concern how to compute the backward predicted values for nonlinear dynamic model.

ACKNOWLEDGMENT

This study was supported by the National Natural Science Foundation of China (No. 60873032).

REFERENCES