Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling : Charles Pisula, University of North Carolina, Chapel Hill, NC Kenneth Hoff III, University of North Carolina, Chapel Hill, NC Ming C. Lin, University of North Carolina, Chapel Hill, NC Dinesh Manocha, University of North Carolina, Chapel Hill, NC

doi:10.1201/9781439864135-40

Chapter

Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling

Chapter

ABSTRACT

Probabilistic roadmap methods have recently received considerable attention as a practical approach for mo tion planning in complex environments. These algo rithms 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 perfor mance of the planner through narrow passages in con figuration space, some researchers have proposed algo rithms for sampling along or near the medial axis of the free space. However, their usage has been limited be cause of the practical complexity of computing the me dial axis or the cost of computing such samples.