This work considers sensor based motion planning for rodshaped robots in unknown environments. The motion planning scheme is based on the rod hierachical generalized Voronoi graph (rodHGVG). The rodHGVG is a roadmap for the rodlike robots, and is an extension of a prior roadmap for pointlike robots. The rodHGVG 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 rodHGVG consists of two component (1) rodGVG and (2) redges. The rodGVG is the set of configurations equidistant to three obstacles. This is a onedimensional structure, but not necessarily connected. The redges connect disconnected redges, by exploiting the fact that the pointGVG is connected in the plane. The redges are the set of conigurations that is "tangent" to pointGVG edges. Using these two types of edges the rodHGVG satisfies the condition for the roadmap in the planar case, and can be generated incrementally using only distance information.
In the threedimensional case, the rod has five degrees of freedom. But, in this case, the rodGVG, which is the set of fiveway equidistant configurations, does not always exist for all environments. So a new structure is introduced, which is in some sense, an extension of redges in planar case. The rodGVG, this new structure and the redges are the components of the rodHGVG in the three dimensional case, and it will be shown that the rodHGVG with these three components has the roadmap property for the environment where the pointGVGs are connected. For the environments where the pointGVG is not connected, we will need another higherlevel structure.
