First consider making a cell decomposition for the case in which the segment can only translate. The method from Section 4.3.2 can be used to compute by treating the robot-obstacle interaction with Type EV and Type VE contacts. When the interior of touches an obstacle vertex, then Type EV is obtained. An endpoint of touching an object interior yields Type VE. Each case produces an edge of , which is polygonal. Once this is represented, the vertical decomposition can be used to solve the problem. This inspires a reasonable numerical approach to the rotational case, which is to discretize into values, , for , and [20]. The obstacle region, , is polygonal for each case, and we can imagine having a stack of polygonal regions. A roadmap can be formed by connecting sampling points inside of a slice in the usual way, and also by connecting samples between corresponding cells in neighboring slices. If is large enough, this strategy works well, but the method is not complete because a sufficient value for cannot be determined in advance. The method is actually an interesting hybrid between combinatorial and sampling-based motion planning. A resolution-complete version can be imagined.

In the limiting case, as tends to infinity, the surfaces of become curved along the direction. The conditions in Section 4.3.3 must be applied to generate the actual obstacle regions. This is possible, but it yields a semi-algebraic representation of in terms of implicit polynomial primitives. It is no easy task to determine an explicit representation in terms of simple cells that can be used for motion planning. The method of Section 6.3.3 cannot be used because is not polyhedral. Therefore, special analysis is warranted to produce a cell decomposition.

The general idea is to construct a cell decomposition in by considering only the translation part, . Each cell in is then lifted into by considering as a third axis that is ``above'' the plane. A cylindrical decomposition results in which each cell in the plane produces a cylindrical stack of cells for different values. Recall the cylinders in Figures 6.18 and 6.19. The vertical axis corresponds to in the current setting, and the horizontal axis is replaced by two axes, and .

To construct the decomposition in
, consider the various
robot-obstacle contacts shown in Figure 6.22. In Figure
6.22a, the segment swings around from a fixed .
Two different kinds of contacts arise. For some orientation (value of
), the segment contacts , forming a Type EV contact. For
three other orientations, the segment contacts an edge, forming Type
VE contacts. Once again using the *feature* concept, there are
four orientations at which the segment contacts a feature. Each
feature may be either a vertex or an edge. Between the two contacts
with and , the robot is not in collision. These
configurations lie in
. Also, configurations for which the
robot is between contacts (the rightmost contact) and are
also in
. All other orientations produce configurations in
. Note that the line segment cannot get from being between
and to being between and , unless the
position is changed. It therefore seems sensible that these must
correspond to different cells in whatever decomposition is made.

Steven M LaValle 2012-04-20