C. Holleman and L. E. Kavraki, “A Framework for Using the Workspace Medial Axis in PRM Planners,” in Proc. of the International Conference on Robotics and Automation (ICRA), San Fransisco, CA, 2000, vol. 2, pp. 1408–1413.
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.
Publisher: http://dx.doi.org/10.1109/ROBOT.2000.844795
PDF preprint: http://kavrakilab.org/publications/holleman-kavraki2000framework-for-using.pdf