Research Description:

This work considers sensor-based 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 workspace distance functions, thus amenable to sensor based implementation. We assume that there is an array of sensors along the length of the robot.

Rod-GVG edges.

Initially we assume that the point-GVG is connected in the given environment. As in the planar rod-HGVG, we use the point-GVG to connect the retracts of the configuration space. Thus, we define the one-tangent-edge R_{ijk}, which is analogous to R-edge of the planar rod-HGVG, as the set of the configurations that is (i) three-way equidistant to C_i, C_j and C_k and (ii) tangent to point-GVG edge F_{ijk}. Recall that the point-GVG edges terminates at the boundaries of obstacles or the four-way-equidistant point (called meet-point). Likewise, the one-tangent-edge terminates at the boundaries of the obstacles or a four-way-equidistant configuration.

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 CF_{ijklm} 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. Moreover, the rod-GVG edges may not exist at all if the rod is "small". This is not surprising since in general placements of the obstacles, there is no five-way-equidistant point in three dimensional space. Also, since one-tangent-edges terminates at the four-way-equidistant configurations, the one-tangent-edges and the rod-GVG edges are not connected to each other. This means that we need additional structures.

This additional structure is 2-tangent-edges, which is the set of four-way-equidistant configurations with an additional constraint. Note that the set of four-way-equidistant configurations is two-dimensional set, and since we want to define one-dimensional structure, we need an additional constraint. Before we describe this additional constraint, first, we need to discuss the four-way-equidistant face CF_{ijkl}. CF_{ijkl} is two-dimensional set and diffeomorphic to S^2, if the rod is small. This can be seen easily, since given a rod with an arbitrary orientation, we can find a four-way-equidistant configuration of rod with the same orientation by a series of distant gradient ascent. Also, note that the one-tangent-edges terminates at the CF_{ijkl}, as described above. Moreover, the intersection of two four-way-equidistant faces CF_{ijkl} and CF_{ijkm} is the rod-GVG edge CF_{ijklm}. I.e., roughly speaking, the one-tangent-edges and the rod-GVG edges are connected to the CF_{ijkl}, thus it is a good candidate to connect the one-tangent-edges and the rod-GVG edges. Still, we need to introduce an additional constraints to obtain an one-dimensional structure, and also the constrains gurantees that the one-dimensional structures are connected themselves and also connected to the one-tangent-edge and the rod-GVG edges. The constraint we use is the tangency condition, more specificially, the 2-tangent-edge is defined to be the set of rod configurations that are four-way-equidistant and tangent to the point two-way-equidistant face.

One-tangent-edges

As in the planar case, the accessibility is defined using the gradient ascent, denote H3(q,t). However, in three-dimensional case, the fixed-orientation gradient ascent will move the rod to the four-way equidistant configuration surface, which is two-dimensional. Thus, to direct the rod to the rod-HGVG, we need extra step, which is full gradient ascent, denoted HJ(q,t). Of course, we could do the full gradient ascent, but as we will see later, this two-step accessibility is used in the connectivity property.

Two-tangent-edges

To show the connectivity, again as in the planar case, we perform the cellular decomposition of the configuration space. The junction region J_{ijkl} is defined as the pre-image of a four-way equidistant configuration surface CF_{ijkl}. Then it can be shown that the union of the four-way equidistant configuration surfaces and the 1-tangent-edges forms a connected set. However, since CF_{ijkl} is a two-dimensional structure, this union is not a roadmap yet. Therefore, we need to define the one dimensional structure on CF_{ijkl}, which is 2-tangent-edge. In other words, it need to be shown that the 2-tangent-edges on a four-way-equidistant configuration surface forms a connected network such that they connect the 1-tangent-edges terminating at the CF_{ijkl}.

It is easy to see that intersection of three 2-tangent-edge is also the endpoint of the one-tangent-edge. More difficult to show is that the 2-tangent-edges are connected to each other and the rod-GVG edges are also connected to the 2-tangent-edges. The proof can be found in the paper, but the basic idea is to show that (i) each of the 2-tangent-edges are connected one-dimensional manifolds on the set diffeomorphic to S^2, and using the fact that the one-tangent-edges terminate at the point on intersection of the two-tangent-edges, to show the 2-tangent-edges forms a connected network. For the rod-GVG edge, we can show that it actually has a dual role with the one-tangent-edge. In other words, we can show that the two adjacent four-way-equidistant faces are connected by either one-tangent-edges or rod-GVG edges, but not by both. Following these steps, we can show that the rod-HGVG is connected if there is no boundary edges, i.e. the configurations that has zero distance to four obstacles.

If there is a bounday edge, the rod-HGVG defined above may actually be disconnected. In this case, we use the boundary edge to connect the disconnected rod-HGVG component. The idea is that since the boundary edges are the boundary component of the CF_{ijkl}, if the rod-HGVG is disconnected, then the end points of the rod-HGVG must be the on the boundary edges.

A 2-tangent-edges (yellow) are connected to two boundary edges (red) Two 2-tangent-edges (yellow) are connected by a boundary edge (red)

Howie Choset
Ji Yeong Lee