Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

Click here to sign up for SAGE Journal Email Alerts today!

Sign In to gain access to subscriptions and/or personal tools.
The International Journal of Robotics Research
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Varadhan, G.
Right arrow Articles by Manocha, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

A Simple Algorithm for Complete Motion Planning of Translating Polyhedral Robots

Gokul Varadhan

University of North Carolina, varadhan{at}cs.unc.edu

Shankar Krishnan

AT&T Research Labs, krishnas{at}research.att.com

T. V.N. Sriram

University of North Carolina, tvn{at}cs.unc.edu

Dinesh Manocha

University of North Carolina, dm{at}cs.unc.edu

We present a new sampling-based algorithm for complete motion planning. Our algorithm relies on computing a 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 star-shaped region. The resulting set of guards capture the intra-region connectivity—the connectivity between points belonging to the same star-shaped region. We capture the inter-region connectivity by computing connectors that link guards of adjacent regions. The guards and connectors are combined to obtain the star-shaped roadmap. We present an efficient algorithm to compute the roadmap in a deterministic manner without explicit computation of the free space. We show that the star-shaped roadmap captures the connectivity of the free space, thereby enabling us to perform complete motion planning. Our approach is relatively simple to implement. We apply our approach to perform motion planning of robots with translational and rotational degrees of freedom (dof). We highlight its performance in challenging scenarios with narrow passages or when there is no collision-free path for robots with low degrees of freedom.

Key Words: robot motion planning • configuration space • star-shaped roadmaps • deterministic sampling

The International Journal of Robotics Research, Vol. 25, No. 11, 1049-1070 (2006)
DOI: 10.1177/0278364906071199
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?