Piano Scene

V-Plan: A Voronoi-Based Hybrid Motion Planner

Mark Foskey foskey@cs.unc.edu
Maxim Garber garber@cs.unc.edu
Ming C. Lin lin@cs.unc.edu
Dinesh Manocha dm@cs.umd.edu

Abstract: We present a hybrid path planning algorithm for rigid and articulated bodies translating and rotating in a 3D workspace. Our approach generates a Voronoi roadmap in the workspace and combines it with ``bridges'' computed by a randomized path planner with Voronoi-biased sampling. The Voronoi roadmap is computed from a discrete approximation to the generalized Voronoi diagram (GVD) of the workspace, which is generated using graphics hardware. By this use of the GVD, portions of the path can be generated without random sampling, substantially reducing the number of random samples needed for the full query. The planner has been implemented and tested on a number of benchmarks. Some preliminary comparisons with a randomized motion planner indicate that our planner performs more than an order of magnitude faster in several challenging scenarios.
PREPRINT
A Voronoi-Based Hybrid Motion Planner
Mark Foskey, Maxim Garber, Ming Lin, and Dinesh Manocha

Proc. IEEE RSJ Int. Conf. Intell. Robot. Syst., 2001: PDF (356 KB)
Univ. N. Carolina Chapel Hill Dep. Comput. Sci. Tech. Rep. TR00-025, 2000: PDF (245 KB), HTML (41 KB)
EXAMPLE PATHS
Piano
Winding Tunnel
2D Maze
Articulated Robot in a 2D Maze
3D Maze
Walls with Holes
Pegs

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.


foskey@cs.unc.edu
Last updated: June, 28, 2001