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

Charles Pisula, Kenneth Hoff III, Ming C. Lin, Dinesh Manocha
[ geom | planning | papers ]

ABSTRACT: 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 when the path of a robot has to pass through narrow passages, 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 using graphics hardware [HCKLM99]. 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 rigid bodies in 2D (with 3-dof) and 3D (with 6-dof) and compared with the performance of earlier planners using a uniform sampling of the configuration space. Its performance varies with different environments and we obtain 25% to over 1000% speed-up.


2D Movies:

3D Movies:

All Movies:

Benchmark Data:


WAFR 2000 Paper(.ps) / Paper (.pdf) / Color plate (.doc)
Bench1.avi / Bench2.avi / Bench3.avi

Bench4.avi / Bench5.avi / Bench6.avi

AVI Format / MPG Format /

2D / 3D / GVD Computation.


2D Benchmark Environments:: (2DOF & 3DOF)

Benchmark 1: An image of a 3DOF planning environment. The robot (in red) moves from the lower left corner through the channel to the upper right corner.

Benchmark 2: An image of a 2DOF planning environment. The robot navigates a very long narrow passage, the entire maze, from the current position to the open area in the upper left.

Benchmark 3: An image of a 3DOF planning environment. The robot, a music stand must navigate a large model (approx. 12,000 polygons).


3D Benchmark Environments:: (3DOF & 6DOF)

Benchmark 4: A simple 6DOF planning environment. The red block must move from the top to bottom area via the straight tube.

Benchmark 5: A 6DOF that appears similar to that of Benchmark 4. However, the cspace has tighter narrow passages due to the relatively few number of valid angles in the elbow joints.

Benchmark 6: A complex 6DOF environment (approx. 2200 polygons). The goal is to move the piano through the window.


Some Related Projects

  • Hsu's Planner – Information on Stanford's Randomized Path Planner.
  • Fast GVD – UNC's Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware.
  • PQP – UNC's Proximity Query Package.
  • Move3D – A generic motion planner developed by Robotics Group at LAAS-CNRS.
  • UNC Geometry – Current projects in Geometric Computing and Physically-Based Computing at UNC.
  • Mechanical Contact Analysis – Research at Purdue on the use and visualization of Configuration Space.

Special Thanks


Copyright 1999. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author"s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

last updated: 12/12/1999