This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Lee, J. Y. Articles by Choset, H. Search for Related Content Social Bookmarking                   What's this?

Sensor-based Planning for a Rod-shaped Robot in Three Dimensions: Piecewise Retracts of R3 x S2

Korea Institute of Science and Technology (KIST), Seoul, Korea, jiyeongl{at}andrew.cmu.edu

Howie Choset

Carnegie Mellon University, Pittsburgh, PA 15213, USA

We present a new roadmap for a rod-shaped robot operating in a three-dimensional workspace, whose configuration space is diffeomorphic to R ³ x S ². This roadmap is called the rod hierarchical generalized Voronoi graph (rod-HGVG) and can be used to find a path between any two points in an unknown configuration space using only the sensor data. More importantly, the rod-HGVG serves as a basis for an algorithm to explore an unknown configuration space without explicitly constructing it. Once the rod-HGVG is constructed, the planner can use it to plan a path between any two configurations. One of the challenges in defining the roadmap revolves around a homotopy theory result, which asserts that there cannot be a one-dimensional deformation retract of a non-contractible space with dimension greater than two. Instead, we define an exact cellular decomposition on the free configuration space and a deformation retract in each cell (each cell is contractible). Next, we "connect" the deformation retracts of each of the cells using a roadmap of the workspace. We call this roadmap a piecewise retract because it comprises many deformation retracts. Exploiting the fact that the rod-HGVG is defined in terms of workspace distance measurements, we prescribe an incremental procedure to construct the rod-HGVG that uses the distance information that can be obtained from conventional range sensors.

Key Words: motion planning • sensor-based planning • rod-shaped robot • Voronoi diagram • roadmap • exploration • retract • piece-wise retract

The International Journal of Robotics Research, Vol. 24, No. 5, 343-383 (2005)
DOI: 10.1177/0278364905053687


CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?