A Voronoi-Based Framework for Motion Planning and Maintainability Applications
Mark Foskey	foskey@cs.unc.edu
Maxim Garber	garber@cs.unc.edu
Ming C. Lin	lin@cs.unc.edu
Dinesh Manocha	dm@cs.unc.edu

Abstract: We present a new approach for motion planning and maintainability studies in complex 3D CAD environments. It automatically computes a collision-free path for a moving object among stationary and completely known obstacles. Our framework uses a combination of analytic, criticality-based and probabilistic techniques to compute the path. It starts with a global strategy that uses an approximate Voronoi diagram of the workspace, computed using graphics hardware. It refines the resulting path with bridges computed by a localized path planner. The resulting system has been used for planning the path of free-flying rigid as well as articulated bodies. Applications of our system include robot motion planning, part removal, and assembly planning. We have implemented a simple planner within this framework and tested it on a number of benchmarks.

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.