Particle filtering

As mentioned so far, the discrete distributions can be estimated by using samples. In fact, it turns out that the Voronoi regions over the samples do not even need to be carefully considered. One can work directly with a collection of samples drawn randomly from the initial probability density, $p(x_1)$. The general method is referred to as particle filtering and has yielded good performance in applications to experimental mobile robotics. Recall Figure 1.7 and see Section 12.2.3.

Let $S \subset X$ denote a finite collection of samples. A probability distribution is defined over $S$. The collection of samples, together with its probability distribution, is considered as an approximation of a probability density over $X$. Since $S$ is used to represent probabilistic I-states, let $P_k$ denote the probability distribution over $S_k$, which is computed at stage $k$ using the history I-state ${\eta}_k$. Thus, at every stage, there is a new sample set, $S_k$, and probability distribution, $P_k$.

The general method to compute the probabilistic I-state update proceeds as follows. For some large number, $m$, of iterations, perform the following:

1. Select a state $x_k \in S_k$ according to the distribution $P_k$.
2. Generate a new sample, $x_{k+1}$, for $S_{k+1}$ by generating a single sample according to the density $p(x_{k+1}\vert x_k,u_k)$.
3. Assign the weight, $w(x_{k+1}) = p(y_{k+1} \vert x_{k+1})$.

After the $m$ iterations have completed, the weights over $S_{k+1}$ are normalized to obtain a valid probability distribution, $P_{k+1}$. It turns out that this method provides an approximation that converges to the true probabilistic I-states as $m$ tends to infinity. Other methods exist, which provide faster convergence [536]. One of the main difficulties with using particle filtering is that for some problems it is difficult to ensure that a sufficient concentration of samples exists in the places where they are needed the most. This is a general issue that plagues many sampling-based algorithms, including the motion planning algorithms of Chapter 5.