5.2.3 Low-Dispersion Sampling

Figure 5.4: Reducing the dispersion means reducing the radius of the largest empty ball.
\begin{figure}\begin{center}
\begin{tabular}{ccc}
\psfig{figure=figs/dispersion....
...dispersion & & (b) $L_\infty$ dispersion
\end{tabular}\end{center}
\end{figure}

This section describes an alternative to random sampling. Here, the goal is to optimize a criterion called dispersion [738]. Intuitively, the idea is to place samples in a way that makes the largest uncovered area be as small as possible. This generalizes of the idea of grid resolution. For a grid, the resolution may be selected by defining the step size for each axis. As the step size is decreased, the resolution increases. If a grid-based motion planning algorithm can increase the resolution arbitrarily, it becomes resolution complete. Using the concepts in this section, it may instead reduce its dispersion arbitrarily to obtain a resolution complete algorithm. Thus, dispersion can be considered as a powerful generalization of the notion of ``resolution.''



Subsections

Steven M LaValle 2020-08-14