Motion planning is a difficult and widely studied problem in robotics. Current research aims not ony to find feasible paths, but to ensure paths have certain properties, e.g., shortest or safest paths. This is difficult for current state-of-the-art sampling-based techniques as they typically focus on simply finding any path.
The medial axis is the set of all points equidistant between two or more obstacle boundaries. For an n-dimensional space, the medial axis is an n-1-dimensional manifold which represents the connectivity of the space. Thus, the medial axis is a useful tool for computing high clearance motions and paths.
We use the observation that any point, free or not, may be retracted to the medial axis by monitoring when the witness point (for collision) changes during the retraction. We use this function to apply medial axis retraction two two large classes of sampling based motion planning algorithms: PRMs and RRTs. We develop two sampling-based algorithms: MAPRM and MARRT and show their effectiveness in solving narrow passage problems and generating high clearance solutions.