Star-shaped Roadmaps

Conference Version

Gokul Varadhan, Dinesh Manocha, "Star-shaped Roadmaps - A Deterministic Sampling Approach for Complete Motion Planning", Robotics Science & Systems 2005

Technical Report

Gokul Varadhan, Dinesh Manocha, "Star-shaped Roadmaps - A Deterministic Sampling Approach for Complete Motion Planning", UNC Technical Report TR05-001

Abstract

We present a simple approach for complete motion planning using deterministic sampling. Our approach relies on computing a novel
star-shaped roadmap of the free space. We partition the free space into star-shaped regions such that a single point called the guard can
see every point in the region. The resulting set of guards capture the intra-region connectivity. We capture the inter-region
connectivity by computing connectors that connect guards of adjacent regions. We use the guards and connectors to construct a star-shaped
roadmap of the free space. We show how to construct the roadmap in a deterministic manner without computing an explicit representation of
the free space. We prove that the star-shaped roadmap captures the connectivity of the free space and provides sufficient information to
perform complete motion planning. One of the benefits of our approach is that it eliminates the need for explicit local planning; the
star-shaped property provides it implicitly. Our approach is relatively simple to implement.

Videos


Notes:


3D Assembly (Translation)





Planar Translating and rotating robot






Planar Articulated robot with 3 revolute joints