| Volume 24 Issue 5 - Publication Date: 1 May 2005 |
| |
| Sensor-based Planning for a Rod-shaped
Robot in Three Dimensions:Piecewise Retracts of R3 × S2 |
| |
| J.Y. Lee Korea Institute
of Science and Technology, Seoul, Korea and H. 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 R3 × S2. 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 con- figurations. 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. |
| |
| Multimedia Key |
= Video |
 = Data |
= Code |
= Image |
|
| |
|
Extension |
Type |
Description |
1 |
|
Example
One: The rod-HGVG in a rectangular environment, without the rod-GVG
edges (17.2 MB). |
2 |
|
Example
Two: The rod-HGVG in a large rectangular environment, with the
rod-GVG edges (19.6 MB). |
|
| |
| Return
to Contents |
