A Fast and Approximate Medial Axis Sampling Technique

Abstract

One key aspect to planning safe motions for a robot requires maintaining a minimum distance from obstacles. The medial axis, or the set of all points equidistant to two or more obstacles, is useful for planning in this context. However, it is computationally intensive to compute this structure directly. As such, prior research proposed directly sampling this structure to avoid its explicit computation. In this paper, we revisit the computational cost of these sampling-based techniques for motion planning, and we propose a novel approximation algorithm that significantly reduces the necessary collision detection invocations in generating samples near the medial axis. At its core, our technique approximates the clearance of a configuration by reasoning about the clearance of nearby configurations. Ultimately, our approach reduces the computational burden of planning on or near the medial axis.