A framework for using the workspace medial axis in PRM planners

Probabilistic roadmap (PRM) planners have been very successful in path planning for a wide variety of problems, especially applications involving robots with many degrees of freedom. These planners randomly sample the configuration space, building up a roadmap that connects the samples. A major problem is finding valid configurations in tight areas, and many methods have been proposed to more effectively sample these regions. By constructing a skeleton-like subset of the free regions of the workspace, these heuristics can be strengthened. The skeleton provides a concise description of the workspace topology and an efficient means of finding points with maximal clearance from the obstacles. We examine the medial axis as a skeleton, including a method to compute an approximation to it. The medial axis is a two-equidistant surface in the workspace. We form a heuristic for finding difficult configurations using the medial axis, and demonstrate its effectiveness in a planner for rigid objects in a 3D workspace.