6.2.2 Vertical Cell Decomposition

Cell decompositions will be defined formally in Section 6.3, but here we use the notion informally. Combinatorial methods must construct a finite data structure that exactly encodes the planning problem. Cell decomposition algorithms achieve this partitioning of $ {\cal C}_{free}$ into a finite set of regions called cells. The term $ k$-cell refers to a $ k$-dimensional cell. The cell decomposition should satisfy three properties:

  1. Computing a path from one point to another inside of a cell must be trivially easy. For example, if every cell is convex, then any pair of points in a cell can be connected by a line segment.
  2. Adjacency information for the cells can be easily extracted to build the roadmap.
  3. For a given $ {q_{I}}$ and $ {q_{G}}$, it should be efficient to determine which cells contain them.
If a cell decomposition satisfies these properties, then the motion planning problem is reduced to a graph search problem. Once again the algorithms of Section 2.2 may be applied; however, in the current setting, the entire graph, $ {\cal G}$, is usually known in advance.6.3 This was not assumed for discrete planning problems.

Figure 6.2: There are four general cases: 1) extending upward and downward, 2) upward only, 3) downward only, and 4) no possible extension.

Steven M LaValle 2012-04-20