Overview

Probabilistic roadmap methods have recently received considerable attention as a practical approach for motion planning in complex environments. These algorithms sample a number of configurations in the free space and build a roadmap. Their performance varies as a function of the sampling strategies and relative configurations of the obstacles. To improve the performance of the planner through narrow passages in configuration space, some researchers have proposed algorithms for sampling along or near the medial axis of the free space. However, their usage has been limited because of the practical complexity of computing the medial axis or the cost of computing such samples.

In this paper, we present efficient algorithms for sampling near the medial axis and building roadmap graphs for a free-flying rigid body. We use a recent algorithm for fast computation of discrete generalized Voronoi diagrams accelerated by graphics hardware [10]. We initially compute a bounded error discretized Voronoi diagram of the obstacles in the workspace and use it to generate samples in the free space. We use multi-level connection strategies and local planning algorithms to generate roadmap graphs. We also utilize the distance information provided by our Voronoi algorithm for fast proximity queries and sampling the configurations. The resulting planner has been applied to a number of free flying...