Research Description:

This work considers senssor 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 planar case, rod-HGVG consists of two component (1) rod-GVG and (2) R-edges.

Since the rod in a plane has three degrees-of-freedom (two translations and one rotation), it is natural to define the rod-GVG edge ss the set of configurations equidistant to three obstacles. This is a one-dimensional structure, however the rod-GVG edges are not necessarily connected.

Rod-GVG edges

The R-edges connect disconnected r-edges, by exploting the fact that the point-GVG is connected in plane. The R-edges are the set of conigurations that is “tangent” to point-GVG edges.

R-edges

WIth these two types of edges, the rod-HGVG forms a connected set, thus forms a roadmap. The accessibility procedure is defined as the fixed-orientation gradient ascent. I.e., the rod moves away from the first closest obstacle until it reaches a double equidistant configuration space, without rotation. Then, the rod moves away from the two closest obstacles without rotation, while maintaining double equidistence. To show the connectivity, we decompose the configurations space into the junction regions. The junction region is defined as a pre-image of a connected component of the rod-GVG edge. Then, the rod-GVG can be seen as the retract of of a junction region. The GVG-edge and R-edge are defined in terms of distance information, therefore can be constructed incrementally using only sensor-information.

Howie Choset
Ji Yeong Lee