This work considers sensor based motion planning for rod-shaped robots in unknown environments. The motion planning scheme is based on the rod hierachical generalized Voronoi graph (rod-HGVG). The rod-HGVG is a roadmap for the rod-like robots, and is an extension of a prior roadmap for point-like robots. The rod-HGVG is defined in terms of distance functions, thus amenable to sensor based implementation.

In the planar case, the rod has three degrees of freedom and the rod-HGVG consists of two component (1) rod-GVG and (2) r-edges. The rod-GVG is the set of configurations equidistant to three obstacles. This is a one-dimensional structure, but not necessarily connected. The r-edges connect disconnected r-edges, by exploiting the fact that the point-GVG is connected in the plane. The r-edges are the set of conigurations that is “tangent” to point-GVG edges. Using these two types of edges the rod-HGVG satisfies the condition for the roadmap in the planar case, and can be generated incrementally using only distance information.

In the three-dimensional case, the rod has five degrees of freedom. But, in this case, the rod-GVG, which is the set of five-way equidistant configurations, does not always exist for all environments. So a new structure is introduced, which is in some sense, an extension of r-edges in planar case. The rod-GVG, this new structure and the r-edges are the components of the rod-HGVG in the three dimensional case, and it will be shown that the rod-HGVG with these three components has the roadmap property for the environment where the point-GVGs are connected. For the environments where the point-GVG is not connected, we will need another higher-level structure.