Sensor-based planning for a rod-shaped robot in three dimensions: Piecewise retracts of R3 multiplied by S2

This work presents new algorithms to explore an unknown configuration space for a rod-shaped robot operating in a three-dimensional workspace and a convex body operating in the plane, whose configuration spaces are diffeomorphic to $R3$ × S2 and SE(2), respectively. These algorithms, by design, allow the robot to explore its configuration space, without ever explicitly constructing the configuration space. The backbones of this approach are new roadmaps, termed the rod hierarchical generalized Voronoi graph (rod-HGVG) and the convex hierarchical generalized Voronoi graph (convex-HGVG). These roadmaps can be used to explore the unknown configuration space using only the sensor data. One of the challenges in defining the roadmap revolves around a homotopy theory result that asserts that there cannot be, in general, a one-dimensional retract of non-contractible space with dimension greater than two. Instead, we define an exact cellular decomposition on the free configuration space and a retract in each cell (each cell is contractible). Next, we “connect” the retracts of each of the cells using a roadmap of workspace. We call this method a piecewise retract because it comprises many retracts. Exploiting the fact that these roadmaps are defined in terms of workspace distance measurements, we prescribe incremental procedures to construct these roadmaps which use distance information which can be obtained from conventional range sensors.