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, the rod has three-degrees of freedom and 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 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. Using these two types of edges the rod-HGVG satisfies the condition for the roadmap in planar case, and can be generated incrementally using only distance information.

In three dimensional workspace, the rod's configuration space R3 X S2 has five dimensions. Thus, it is natural to first define a five-way equidistant structure which we term rod-GVG edges. Just like the planar rod-GVG, the three-dimensional rod-GVG (henceforth called the rod-GVG), is not necessarily connected. Just like the planar case, we decompose R3 X S2 into cells, also called junction regions, and "connect" them with 1-tangent edges, structures that are analogous to $R$-edges. However, the rod-GVG edges by themselves are not retracts of the junction regions. Instead, the set of configurations equidistant to four obstacles forms a retract of a junction region. This four-way equidistant structure has two dimensions, and thus this structure, with the 1-tangent-edges and rod-GVG edges do not form a roadmap. Therefore, we define an additional structures called 2-tangent edges, which are four-way equidistant with an additional constraint. The rod-HGVG comprises rod-GVG edges, 1-tangent-edges, and 2-tangent-edges.

Howie Choset
Ji Yeong Lee