Interpreting the C-space

It is important to consider the topological implications of $ {\cal C}$. Since $ {\mathbb{S}}^1$ is multiply connected, $ {\mathbb{R}}\times {\mathbb{S}}^1$ and $ {\mathbb{R}}^2 \times {\mathbb{S}}^1$ are multiply connected. It is difficult to visualize $ {\cal C}$ because it is a 3D manifold; however, there is a nice interpretation using identification. Start with the open unit cube, $ (0,1)^3 \subset {\mathbb{R}}^3$. Include the boundary points of the form $ (x,y,0)$ and $ (x,y,1)$, and make the identification $ (x,y,0) \sim
(x,y,1)$ for all $ x,y \in (0,1)$. This means that when traveling in the $ x$ and $ y$ directions, there is a ``frontier'' to the C-space; however, traveling in the $ z$ direction causes a wraparound.

It is very important for a motion planning algorithm to understand that this wraparound exists. For example, consider $ {\mathbb{R}}\times {\mathbb{S}}^1$ because it is easier to visualize. Imagine a path planning problem for which $ {\cal C}= {\mathbb{R}}\times {\mathbb{S}}^1$, as depicted in Figure 4.8. Suppose the top and bottom are identified to make a cylinder, and there is an obstacle across the middle. Suppose the task is to find a path from $ {q_{I}}$ to $ {q_{G}}$. If the top and bottom were not identified, then it would not be possible to connect $ {q_{I}}$ to $ {q_{G}}$; however, if the algorithm realizes it was given a cylinder, the task is straightforward. In general, it is very important to understand the topology of $ {\cal C}$; otherwise, potential solutions will be lost.

Figure 4.8: A planning algorithm may have to cross the identification boundary to find a solution path.
\begin{figure}\centerline{\psfig{file=figs/cylinderpath.eps,width=2.3in}}\end{figure}

The next section addresses $ SE(n)$ for $ n=3$. The main difficulty is determining the topology of $ SO(3)$. At least we do not have to consider $ n > 3$ in this book.

Steven M LaValle 2012-04-20