A Voronoi-based hybrid motion planner

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 using this 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.

Authors

• Mark Foskey
• Maxim Garber
• Ming Lin 0003
• Dinesh Manocha

Keywords

• Orbital robotics
• Path planning
• Robot sensing systems
• Graphics
• Sampling methods
• Computer science
• Random number generation
• Benchmark testing
• Topology
• Character generation
• Random Sampling
• Rigid Body
• Voronoi Diagram
• Discrete Approximation
• Degrees Of Freedom
• Major Axis
• Line Segment
• Configuration Space
• Benchmark Results
• Edge Pixels
• Robot Path