Читать книгу Position, Navigation, and Timing Technologies in the 21st Century - Группа авторов - Страница 31

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)dx = 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.103 can 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.108 into Eq. 36.107 yields

(36.109)

Finally, the collection of particle weights can be normalized via

(36.110)

then Eq. 36.109 becomes

(36.111)

which we will exploit to develop a recursive estimator.