6.3.4 A Decomposition for a Line-Segment Robot

This section presents one of the simplest cell decompositions that involves nonlinear models, yet it is already fairly complicated. This will help to give an appreciation of the difficulty of combinatorial planning in general. Consider the planning problem shown in Figure 6.21. The robot, ${\cal A}$, is a single line segment that can translate or rotate in ${\cal W}= {\mathbb{R}}^2$. The dot on one end of ${\cal A}$ is used to illustrate its origin and is not part of the model. The C-space, ${\cal C}$, is homeomorphic to ${\mathbb{R}}^2 \times {\mathbb{S}}^1$. Assume that the parameterization ${\mathbb{R}}^2 \times [0,2 \pi] {/\sim}$ is used in which the identification equates $\theta = 0$ and $\theta = 2 \pi$. A point in ${\cal C}$ is represented as $(x,y,\theta)$.

Figure 6.21: Motion planning for a line segment that can translate and rotate in a 2D world.