A grid-based approach

Perhaps the most straightforward way to numerically compute probabilistic I-states is to approximate probability density functions over a grid and use numerical integration to evaluate the integrals in (11.57) and (11.58).

A grid can be used to compute a discrete probability distribution that approximates the continuous probability density function. Consider, for example, using the Sukharev grid shown in Figure 5.5a, or a similar grid adapted to the state space. Consider approximating some probability density function $p(x)$ using a finite set, $S \subset X$. The Voronoi region surrounding each point can be considered as a ``bucket'' that holds probability mass. A probability is associated with each sample and is defined as the integral of $p(x)$ over the Voronoi region associated with the point. In this way, the samples $S$ and their discrete probability distribution, $P(s)$ for all $s \in S$ approximate $p(x)$ over $X$. Let $P(s_k)$ denote the probability distribution over $S_k$, the set of grid samples at stage $k$.

In the initial step, $P(s)$ is computed from $p(x)$ by numerically evaluating the integrals of $p(x_1)$ over the Voronoi region of each sample. This can alternatively be estimated by drawing random samples from the density $p(x_1)$ and then recording the number of samples that fall into each bucket (Voronoi region). Normalizing the counts for the buckets yields a probability distribution, $P(s_1)$. Buckets that have little or no points can be eliminated from future computations, depending on the desired accuracy. Let $S_1$ denote the samples for which nonzero probabilities are associated.

Now suppose that $P(s_k\vert{\eta}_k)$ has been computed over $S_k$ and the task is to compute $P(s_{k+1}\vert{\eta}_{k+1})$ given $u_k$ and $y_{k+1}$. A discrete approximation, $P(s_{k+1}\vert s_k,u_k)$, to $p(x_{k+1}\vert x_k,u_k)$ can be computed using a grid and buckets in the manner described above. At this point the densities needed for (11.57) have been approximated by discrete distributions. In this case, (11.38) can be applied over $S_k$ to obtain a grid-based distribution over $S_{k+1}$ (again, any buckets that do not contain enough probability mass can be discarded). The resulting distribution is $P(s_{k+1}\vert{\eta}_k,u_k)$, and the next step is to consider $y_{k+1}$. Once again, a discrete distribution can be computed; in this case, $p(x_{k+1}\vert y_{k+1})$ is approximated by $P(s_{k+1}\vert y_{k+1})$ by using the grid samples. This enables (11.58) to be replaced by the discrete counterpart (11.39), which is applied to the samples. The resulting distribution, $P(s_{k+1}\vert{\eta}_{k+1})$, represents the approximate probabilistic I-state.