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.

Steven M LaValle 2012-04-20