Sensor based planning for rod shaped robots in three dimensions: piece-wise retracts of R/sup 3/×S/sup 2/

Abstract

We describe a new roadmap, termed the rod-HGVG, for motion planning of a rod-shaped robot operating in a three-dimensional volume. This roadmap is defined in terms of work space distance enabling us to prescribe an incremental construction procedure. This allows the rod to explore its configuration space, R/sup 3//spl times/S/sup 2/, without ever explicitly constructing the configuration space. In fact, the rod robot need not know the work space ahead of time. We term the rod-HGVG a piecewise retract because it comprises many retracts. Homotopy theory asserts that there cannot be in general a one dimensional retract of noncontractable five-dimensional space. Instead, we define an exact cellular decomposition on R/sup 3//spl times/S/sup 2/ and a retract in each cell. Next, we "connect" the retracts of each cell forming a piecewise retract of the rod's configuration space.