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

After 22 cycles, the density shows a reduced number of peaks (see Figure 36.13). This indicates that the filter is incorporating sensor observations and the statistical dynamics model to effectively eliminate a number of potential ambiguity possibilities.

After 100 cycles ( Figure 36.14), the filter has converged to a single ambiguity.

The global state estimate and associated standard deviation result for this simulation are shown in Figure 36.15. The shape of the uncertainty bound clearly shows the effects described above. As the likelihood of each integer ambiguity realization changes, the overall uncertainty changes and eventually collapses to the centimeter level.

In the next section, we will move to our final nonlinear filter algorithm, the sampling particle filter.

In a similar manner to the grid particle filter, the sampling particle filter, also known as a the sequential Monte Carlo (SMC) filter, represents the state density function using a weighted collection of particles. However, we seek to address the computational scaling problems inherent in grid‐based approaches by exploiting an approach that focuses computation on the regions of the state space with the highest likelihood. This is accomplished by randomly sampling the state space.

Figure 36.15 Grid particle filter position error and one‐sigma uncertainty. Note that the error uncertainty collapses once sufficient information is available to resolve the integer ambiguity.

The main advantage of this approach is the potential to more completely sample the important areas of the state space, while limiting the total number of particles required. This is a useful advantage over the grid particle filter, which can require unreasonable numbers of particles as the state dimensionality and domain increase. While sampling particle filtering approaches are suboptimal, their computational advantages make them attractive for a larger range of applications.

We begin by describing the concept of Monte Carlo integration, which is subsequently used to develop a basic recursive estimation algorithm.

The fundamental enabling concept for the sampling particle filter is the concept of Monte Carlo integration. Given an integral in the following form:

(36.99)

where Ω is an n x‐dimensional region in with volume

(36.100)

If N independent samples are uniformly drawn from Ω , that is, { x [1], x [2], ⋯, x [N]} ∈ Ω, then the integral can be approximated as

(36.101)

which approaches equality as

(36.102)

Now consider the case where the function in the integrand, g ( x), can be expressed as the product

(36.103)

where p ( x) is a probability density function; thus, p ( x) ≥ 0 and ∫ p ( x) d x= 1. If N independent samples, x [i], can be drawn in accordance with p (·), then the integral can be estimated as the sample mean of the transformed particles:

(36.104)

The resulting error in the estimate is unbiased and, most importantly, scales as the reciprocal of the square root of N . This is an important result as it indicates that the error is independent of the dimensionality of the state, as long as the particles are properly sampled from the distribution of x. This is an important distinction from the grid filter, which requires particles that increase geometrically with the number of dimensions in the state vector [6].

Unfortunately, it is not always possible to generate samples from arbitrary density functions. This motivates additional development of the concept known as importance sampling.

To further our discussion of importance sampling, it is convenient to introduce the concept of a proposal density, chosen to resemble (and provide support over) the true density of x, while retaining the ability to generate samples. An illustration of a proposal‐density sampling approach is shown in Figure 36.16.

Given a random vector with true density p ( x) and particles sampled from a proposal density, q ( x), Eq. 36.103can be rewritten as

(36.105)

Figure 36.16 Proposal sampling illustration. In this example, the particles are generated using the proposal density (q) and subsequently weighted to represent the desired density (π).

The resulting estimate of the integral, assuming N independent particles sampled from q (·), is given by

(36.106)

(36.107)

where the ratio between the true density and the proposal density can be expressed as particle importance weights:

(36.108)

Substituting Eq. 36.108into Eq. 36.107yields

(36.109)