Adapting the sampling distribution in PRM planners based on an approximated medial axis

Abstract

Probabilistic roadmap planners have proven to be effective in solving complex path planning problems. These planners sample the configuration space to compute a representation of its free space connectivity. One of the major difficulties for this approach is the planning of a path through narrow configuration space passages, since samples are placed inside narrow passages only with small probability. To address this problem, approaches have been devised that rely on the medial axis of the workspace to bias sampling in configuration space such that the probability of generating samples inside narrow passages is increased. This paper introduces a novel algorithm for computing an approximation to the medial axis, which can be computed more efficiently than the exact or discretized medial axis. We demonstrate that, compared to the true medial axis, this approximation is equally well suited to bias the sampling in probabilistic roadmap planners. Furthermore, we present a novel sampling strategy based on the approximated medial axis. This strategy results in high sampling density in narrow passages, while sampling open spaces sparsely. Experiments demonstrate the effectiveness of the medial axis approximation and its application to motion planning based on the proposed sampling scheme.