Position, Navigation, and Timing Technologies in the 21st Century

Figure 36.8 MMAE integer ambiguity particle weights (subset). The correct ambiguity particle (N=7) likelihood increases over time while the outliers are determined to be less likely.

Figure 36.9 Probability density function (PDF) and cumulative density function example (CDF).

(36.71)

The particle filter uses a collection of weighted delta functions to represent the pdf:

(36.72)

where w [j]is a scalar weighting value for the j ‐th particle with location x [j]. As mentioned previously, the sum of weights must be unity:

(36.73)

An example pdf represented by a collection of weighted particles is shown in Figure 36.10. This importance sampling strategy allows us to represent any pdf with a desired level of fidelity, given enough particles. Additional details regarding importance sampling are provided in Section 36.3.7.

In addition to representing arbitrary pdfs of random vectors, successful nonlinear estimation requires the ability to determine the resulting pdfs after applying nonlinear transformations to random vectors. In general, this can be intractable; however, representing the pdf using the collection of weighted particles makes the transformation relatively straightforward. An example of the effect of some sample nonlinear transformations is shown in Figure 36.11.

One of the most common functions necessary for filtering applications is calculation using the expectation operator. The expectation operator is defined as

(36.74)

where E [·] is the expectation operator, g ( x) is an arbitrary function of the random vector x, and p ( x) is the pdf of the random vector.

Based on this definition, we can easily calculate some common expectations of the weighted particle pdf. The first is the mean, which is defined as E [ x]:

(36.75)

Substituting the pdf of xfrom Eq. 36.72, rearranging the summation and integral, and then applying the sifting property:

(36.76)

(36.77)

(36.78)

This shows that the mean of a weighted particle random variable can be calculated as the weighted sum of particles.

The above development can be applied identically to the general expectation function case with the following result:

(36.79)

This can easily be extended to represent a set of sufficient statistics for an arbitrary density function. As a result, it can be shown that any density function can be represented to arbitrary accuracy, given enough particles. Because we seek estimation methods that are computationally feasible, we are searching for methods that give us “good enough” performance (e.g. accuracy and stability) with limited computational resources.

In the next section, we investigate one approach, known as the grid particle filter, to representing the location of our particle collection.

Figure 36.10 Importance sampling used to represent arbitrary density functions. The density function is represented by a combination of particle locations and weights (represented by arrows), which can be varied independently.

Figure 36.11 Visualization of nonlinear transformation on a random variable. Given uniform random variables x , y , the effects of three nonlinear transformations show that the density can change significantly during transformation.

One approach to addressing the generalized nonlinear estimation requirement to maintain the full probability density is the so‐called grid particle filter. The grid particle filter maintains a discrete collection of possible system states and associates a probability with each of those states (i.e. particles). This approach is optimal given systems with the following conditions:

1 The state vector is truly discrete or can be accurately approximated using a discretization of the state space.

2 The number of discrete states is computationally tractable.

Given these conditions, the state density function can be expressed as a weighted collection of particles (repeated from Eq. 36.72)

(36.80)

where the particle weights, w [j], must sum to one. Because the particle locations are assumed to be static, the filtering operation is performed over the collection of weights. This allows the filter to maintain the density function as the collection of propagation and update steps are applied. At this point, it is relatively straightforward to derive the propagation and update relations for the collection of particles.

We begin with the propagation from time k – 1 to k . Assume that the posterior density function at time k – 1 is given by

(36.81)