Rather than trying to sample close to the boundary, another strategy is to force the samples to be as far from the boundary as possible. Let be a metric space. Let a maximal ball be a ball such that no other ball can be a proper subset. The centers of all maximal balls trace out a one-dimensional set of points referred to as the medial axis. A simple example of a medial axis is shown for a rectangular subset of in Figure 5.30. The medial axis in is based on the largest balls that can be inscribed in . Sampling on the medial axis is generally difficult, especially because the representation of is implicit. Distance information from collision checking can be used to start with a sample, , and iteratively perturb it to increase its distance from [635,971]. Sampling on the medial axis of has also been proposed . In this case, the medial axis in is easier to compute, and it can be used to heuristically guide the placement of good roadmap vertices in .
Steven M LaValle 2012-04-20