Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

SAGETRACK

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 ISI 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 Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati  
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

T. V.N. Sriram

University of North Carolina

Dinesh Manocha

University of North Carolina

We present an algorithm for complete path planning for translating polyhedral robots in three dimensions. We compute a roadmap of the free space that captures its connectivity. The roadmap is constructed without computing an explicit representation of the free space. It encodes the complete connectivity of free space and allows us to perform exact path planning. We construct a roadmap by performing a sampling of the free space in a deterministic fashion. We obtain a set of deterministic samples by generating an adaptive volumetric grid. Our algorithm is simple to implement and uses two tests: a complex cell test and a star-shaped test during sample generation. These tests can be efficiently performed on polyhedral objects using max-norm distance computation and linear programming. We demonstrate the performance of our algorithm on environments with very small narrow passages or no collision-free paths.

Key Words: complete motion planning • Minkowski sum • connectivity roadmap • deterministic sampling

The International Journal of Robotics Research, Vol. 24, No. 11, 983-995 (2005)
DOI: 10.1177/0278364905059061
Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati    What's this?