The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

We present a new roadmap for a rod-shaped robot operating in a three-dimensional workspace, whose configuration space is diffeomorphic to R 3 x S 2. 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.

Notes

Associated Lab(s) / Group(s): Biorobotics

Associated Project(s): Retract-like structures for SE(2) and SE(3)

Number of pages: 41

Text Reference

Ji Yeong Lee and Howie Choset, "Sensor-based Planning for a Rod-shaped Robot in Three Dimensions: Piecewise Retracts of R3 x S2," The International Journal of Robotics Research, Vol. 24, No. 5, May, 2005, pp. 343 - 383.

BibTeX Reference

@article{Lee_2005_6153,
   author = "Ji Yeong Lee and Howie Choset",
   title = "Sensor-based Planning for a Rod-shaped Robot in Three Dimensions: Piecewise Retracts of R3 x S2",
   journal = "The International Journal of Robotics Research",
   pages = "343 - 383",
   month = "May",
   year = "2005",
   volume = "24",
   number = "5",
}

The Robotics Institute

Menu