{'fraction_non_alphanumeric': 0.03306575939609803, 'fraction_numerical': 0.013555898144702568, 'mean_word_length': 4.730124885775205, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved Particle Filters for Vehicle Localisation

The ability to track a moving vehicle is of crucial importance in numerous applications. The task has often been approached by the importance sampling technique of particle filters due to its ability to model non-linear and non-Gaussian dynamics, of which a vehicle travelling on a road network is a good example. Particle filters perform poorly when observations are highly informative. In this paper, we address this problem by proposing particle filters that sample around the most recent observation. The proposal leads to an order of magnitude improvement in accuracy and efficiency over conventional particle filters, especially when observations are infrequent but low-noise.


Introduction
Tracking a moving vehicle is a central and difficult problem arising in different contexts ranging from military applications to robotics (Thrun, 2002;Gordon et al., 2002). It consists of computing the best estimate of the vehicle's trajectory based on noisy sensor measurements. In this paper, we are interested in vehicle tracking when the road network is known.
Several strategies have been developed to track a vehicle on a road network (Lou et al., 2009;Chawathe, 2007;Wenk et al., 2006;Alt et al., 2003;Huabei Yin and Wolfson;Pink and Hummel, 2008). We focus on the particle filter method (Gordon et al., 1993). The method has had numerous successes in this area due to its flexibility to handle cases where the dynamic and observation models are non-linear and/or non-Gaussian. It is an importance sampling technique that approximates the target distribution by sampling from a series of intermediate proposal distributions.
Critically, in common with any important sampling method, the performance of particle filters is strongly dependent on the choice of the proposal distribution. If the proposal is not well matched to the target distribution, then the method produces samples that have low effective sample size and, as a result, it requires a prohibitively large number of particles to represent the target distribution accurately. The problem typically arises under highly informative observation regimes, in which the current observation provides significant information about the current state but the state dynamics are weak.
The particle filter community has developed various approaches to mitigate the deficiency. One approach attaches a post-sampling step that moves particles sampled from the proposal distribution towards the target distribution using Markov Chain Monte Carlo moves (Andrieu et al., 2010;Fox et al., 2001;Van Der Merwe et al., 2000) or by solving partial differential equations (Li and Coates, 2016;Daum et al., 2010;Daum and Huang, 2007;Khan and Ulmke, 2014). An alternative approach improves the proposal distribution by giving it additional information about the current (Montemerlo and Thrun, 2007;Kong et al., 1994;Liu and Chen, 1998) or even future observations (Lin et al., 2013) or their approximations (Pitt and Shephard, 1999). Several authors considered conditioning the proposal distribution on the current observation only (Lin et al., 2005;Fox et al., 2001). The approaches successfully increased the effective sample size, but, often at the cost of high computational complexity or analytical intractability. The construction of good, but also computationally efficient proposal distributions is still an open research question.
In this paper, we propose an improved particle sampling scheme that is both computationally efficient and mathematically robust. The approach generates proposals based on the current sensor observation only, leading to good alignment between the proposal and the target distribution even with a small sample size. It converges to the desired target distribution at faster rates than standard particle filters, especially when observations are highly informative, e.g. infrequent but low-noise. It is easy to implement and avoids the computational and analytical complexity of the discussed alternatives with other proposal distributions or post-sampling moves. It also presents a simpler approach to sample weighing than those previously proposed with the same proposal distribution (Lin et al., 2005;Fox et al., 2001).
The paper is structured as follows. We present the problem statement in Section 2, followed by a description of the standard particle filters in Section 3. We introduce the proposed particle filters method in Section 4. We outline the application of the method to vehicle tracking in Section 5 and present results in Section 6. We conclude by summarising the paper's contributions in Section 7.

Problem statement
The key idea of particle filters is to estimate the marginal posterior distribution p(x t | z 0:t ) where x t is the state of the system at time t and z 0:t = {z 0 , . . . , z t } is a sequence of measurements collected up to time step t. We call the posterior the belief and use the following notation In the context of vehicle tracking, the belief is our estimate of the vehicle position at time t given all measurements collected until then. The measurements include GPS readings and controls, which carry information about vehicle motion between consecutive timestamps. Denoting a GPS reading at time t by y t and a control in the time interval (t − 1; t] by u t−1 , we have Bel(x t ) = p(x t | y 0:t , u 0:t−1 ) Particle filters estimate Bel(x t ) recursively. In order to arrive at a recursive equation, we note we can use Bayes rule to decompose Equation 2 to Bel(x t ) = p(y t | x t , y 0:t−1 , u 0:t−1 )p(x t | y 0:t−1 , u 0:t−1 ) p(y t | y 0:t−1 , u 0:t−1 ) The underlying assumption of particle filters is that the system follows the Markov assumption, that is, measurements y t are conditionally independent of past measurements and controls given knowledge of the state x t :

This conveniently simplifies Equation 3 to
We integrate out the position at x t−1 in order to arrive at the following recursive form which can be simplified again using Markov assumption by noting that: Finally, we arrive at a recursive estimator known as Bayes filter : where η is a normalising constant. The Bayes filter equation is the basis for particle filters and the improved particle filters that we propose in this paper.

Particle Filters
Particle filters approximate the belief Bel(x) by a set of m weighted samples distributed according to Bel(x): where each x (i) is a sample (a state) and w (i) are non-negative weights called importance factors that determine the importance of each sample.
The particle filters method operates recursively. It begins by generating m samples x (i) 0 from the initialisation distribution Bel(x 0 ) = p(x 0 ) and annotates them by the uniform importance factor 1/m. Subsequently, it estimates Bel(x t ) at any future timestamp t by performing a three-step recursive update, computing the expression in Equation 4 from the right to the left.
for k = 1, . . . , m : 1. Sample a state x t−1 by drawing a random x (i) t−1 from the sample set representing Bel(x t−1 ) according to the distribution defined through the importance factors w (i) t−1 .
2. Use the sample x (i) t−1 and the control u t−1 to generate a sample x (j) t according to the so-called transition probability p(x t | x t−1 , u t−1 ).
3. Finally, use the observation y t to weigh the sample x (j) t by the non-normalized importance factor given by the so-called observation probability given the observation y t .
Further below, it will be important to notice that the particle filters method is, in fact, an importance sampling scheme. It approximates Bel(x t ) using a proposal distribution given by The proposal approximates the desired posterior Consequently, the importance factors are given by the quotient

Improved Particle Filters
We propose an improved particle sampling scheme in which x t are sampled directly around the most recent observation y t according to the proposal distribution: This new proposal distribution possesses orthogonal strengths to the one in Equation 5, in that it generates samples that are highly consistent with the most recent sensor measurement but ignorant of past measurements and controls. As such, we expect it to outperform conventional particle filters in systems where the current observation provides more information about the current state than the underlying state dynamics.
The importance factors for these samples are again calculated by the quotient: Since Bel(x t−1 ) is represented by a set of samples x (i) t−1 weighted by importance factors w (i) t−1 , the (non-normalised) importance factor for any sample x (j) t can be approximated by The importance factor reflects the likelihood of the sample given past measurements and controls. This is orthogonal to the previous definition in Equation 7, where it depends on the current measurement only.
Overall, the proposed sampling scheme changes how data and controls are used in belief estimation: the current measurement is now used for sampling (instead of weighing); past measurements and controls are used for calculating importance factors (instead of sampling).
The scheme is implemented recursively. It initialises Bel(x 0 ) by generating m samples around the first observation y 0 according to the observation probability p(y t | x t ). The samples are assigned the uniform importance factor of 1/m. Subsequently, it estimates Bel(x t ) at timestamps t > 0 using a two-step recursive update: for k = 1, . . . , m : 1. Generate a sample x (i) t according to the observation probability p(y t | x t ).
2. Use the sample set representing Bel(x t−1 ) to weight the sample x In the context of vehicle tracking, the estimates of Bel(x t ) approximate the vehicle position at time t. If instead of the single-time approximation, you are interested in finding the most likely trajectory that the vehicle traversed until time t, it can be computed via the following dynamic programming routine. It corresponds to finding the sequence x 0:t that maximises the posterior p(x 0:t | y 0:t , u 0:t−1 ).

Choose a sample x
(i) t from the sample set representing Bel(x t ) that has the highest importance factor w (i) t .

Use the sample x
t−1 , i.e. is the most likely preceding state. Repeat this step until you reach t = 0.

Data
We tested the improved particle filters method on a GPS trajectory of a police patrol vehicle during its night shift (9am to 7am) in the London Borough of Camden on February 9 th 2015. The dataset contains 4,800 GPS points that were emitted roughly every second when moving. It was acquired for research purposes as part of the "Crime, Policing and Citizenship" project 1 .

Implementation
In order to apply the improved particle filters to vehicle tracking, we need to specify the form of the observation probability p(y t | x t ) and the transition probability p(x t | x t−1 , u t−1 ). Their forms depend on the vehicle's dynamics and the type of sensor used for localisation (a GPS receiver in our case). The distributions are time-invariant; hence we will omit the time index t in the following derivations.

Observation probability
Definition We model the conditional probability p(y | x) of observing a GPS point y, represented by its easting and northing coordinates: as a two-dimensional Gaussian distribution with the mean vector µ representing the true vehicle position x   and the covariance Σ that is constant across space, i.e. isotropic covariance This representation of p(y | x) reflects our expectation that GPS observations are normally distributed around the true vehicle positions.
Proposal Generation In the proposed method, we use the observation probability p(y | x) to sample possible vehicle positions on the road network (see Equation 8). In order to efficiently generate samples on the road network (as shown in Figure 1b), we want to analytically project the two-dimensional p(y | x) onto individual road segments.
We begin with the general form of a two-dimensional Gaussian distribution for p(y | x) We precompute the inverse of the covariance matrix and use it together with the partitioning (11), (12), and (13) to rewrite (14) as We successfully factor p(y | x) into a product of two Gaussian distributions along the easting and northing directions due to the isotropic properties of the covariance matrix in (13). In fact, the factorisation of p(y | x) holds for any other orthogonal coordinate system. Therefore, we replace the easting-nothing coordinates with orthogonal distances from x dictated by the road segment that x is on: a (distance to the road segment), b (distance along the road segment).
Under the new coordinate system x and y are partitioned as and p(y | x) becomes The above definition enables us to generate proposals x in accordance with the observation model p(y | x) (as specified in Equation 8): 1. Firstly, sampling a road segment that x in on such that y a ∼ N (0, σ) 2. Secondly, sampling the position of x along the segment such that y b ∼ N (0, σ)

Transition probability
We set the transition probability p(x t | x t−1 , u t−1 ) to be a linear estimate equal to the Cartesian distance between GPS points x t−1 and x t (the control u t ) plus an additive Gaussian noise. This is a simplistic assumptions that could be further explored, however, it is not the focus of this paper.

Validation
In the absence of the ground truth about vehicle positions at any point in time, we propose a validation framework based on the well-established technique of cross-validation (Barber, 2012). We remove every 10th GPS points from the available GPS trajectory. We then infer the path taken by the vehicle given the incomplete trajectory and the road network. Finally, we measure the distance between each removed point and the inferred path. The distances across all removed points form the distribution of the prediction error.

Results
A series of tests was conducted to elucidate the difference between the standard and the proposed particle filters. We found that the modified proposal distribution consistently outperforms conventional particle filters in terms of accuracy. As expected, largest gains in accuracy are observed on datasets with long sampling intervals as their observations are infrequent and hence become highly informative. Figure 2 plots the prediction error (in meters) of both algorithms for different sampling intervals and levels of sensor noise, using m = 10 samples only. It shows that the proposed method has lower median error across all examined sampling rates and sensor noise levels, as well as much lower error variation.
We evaluated the ability of both methods to track a vehicle over time. When they fail to track a vehicle, it means that all positions that they propose are completely unlikely given sensor data, i.e. particle weights sum up to zero. The standard particle filter basically fails when sensor measurements are infrequent (with m = 10 samples). Figure 3a shows that it is unable to track the vehicle nearly 70% of the time when the sampling interval increases to one minute. In the same scenario, the proposed method gives excellent results that show little variation to changes to sampling intervals.
On the contrary, the proposed method fails to track when sensors are very noisy. Although it shows high accuracy (see Figure 2b), it is prone to high failure rates as the level of sensor noise increases (Figure 3b). This weakness reflects the orthogonal limitations of the two approaches: our method generates samples that are highly consistent with the most recent measurement (which makes it sensitive to sensor noise), whereas the conventional approach samples in accordance with past measurements (inefficient when sampling rates are low).  Figure 2: Accuracy of the improved particle filters (red) and the standard particle filters (blue) on GPS data with varied sampling rate and sensor noise, represented as 25th, 50th and 75th percentiles of prediction errors.    : Accuracy and robustness of the improved particle filters (red) and the conventional particle filters (blue) as a function of the number of samples used. Accuracy is shown as the 25th, 50th and 75th percentiles of prediction errors.
(a) accuracy (b) failure rate Figure 5: Accuracy and robustness of the standard particle filters as the number of samples is increased to very large values. Accuracy is shown as the 25th, 50th and 75th percentiles of prediction errors.
Finally, we tested the sensitivity of the proposed method to the number of samples used. Figure  4 shows comparative results on GPS data with the sampling interval of 70 seconds. The proposed method yields significantly better results, both in terms of accuracy and robustness to failure. When only m = 10 samples are used, it reduces the estimation error by almost 10 meters and the percentage of failure by as much as 68%. The performance is further improved when more samples are used, but the gain is small compared to the conventional particle filters. In fact, the proposed method with m = 100 samples is more accurate and robust than the conventional particle filters with as many as m = 10000 samples (see Figure 5). Therefore, it can be reliably used with a small number of samples, making it highly computationally efficient.

Conclusions
This paper describes a modified particle filters method that shows uniformly superior accuracy to the conventional particle filters. The improved algorithm utilizes a different proposal distribution which uses only the most recent observation in the position prediction process. In doing so, it makes more efficient use of the particles, particularly in situations in which the transition noise is high in relation to the observation noise.
The main contribution of the paper is the proposal distribution itself and the derivation of the associated importance weights that guarantees convergence to the same posterior distribution as the standard particle filters. An important contribution is also the projection of a two-dimensional Gaussian onto a network of roads, which enables efficient sampling on the road network from a spatial Gaussian.
The theoretical contributions are complemented by experimental results of vehicle tracking using a police GPS dataset. The new algorithm is consistently more accurate than the standard particle filters, with largest gains in accuracy on sparse GPS data. It requires much fewer samples to yield good performance. In fact, as few as fifty samples are sufficient to outperform the standard method with 10,000 particles in terms of accuracy and proneness to failure. We believe that our results illustrate that particle filters can be radically improved if one carefully chooses a proposal distribution, such that it extracts the most information from the available data.