The note of Robot Motion Planning -Chapter 5_robotic motion planning: cell decompositions

原理

• 将 free space 分解成不重叠的区域集合（cells）。
• 构造并搜索表示单元间邻接关系的连通图。
• 搜索成功，得到由Cell组成的序列（channel）。

区域分解应具有以下两个特征：

• 每个单元尽可能相似，使计算单元中的任何两个configurations的路径简单。
• 任意两个单元间的邻接性容易测试。容易找到两个共享边界单元的路径。

1 Polygonal Configuration Space

env : $c=R_2$, C-obstacle region CB forms a polygonal region in C.
free space $C_{free}$ is bounded.

**DEFINITION 1: A convex polygonal decomposition K,**of $C_{free}$ is
a finite collection of convex polygons, called cells, such that the interiors of any two cells do not intersect and the union of all the cells is equal to$cl(C_{free})$. Two cells K and K’ in K are adjacent if only if K n K’ is a line segment of non-zero length.

DEFINITION 2: The connectivity graph G associated with a convex polygonal decomposition $k$ of $C_{free}$ is the non-directed graph specified as follows:

• G’s nodes are the cells in $K$.
• Two nodes in G are connected by a link if and only if the corresponding cells are adjacent.

The exact cell decomposition algorithm for planning a free path
connecting the two configurations is the following:

1. Generate a convex polygonal decomposition $k$ of $C_{free}$.
2. Construct the connectivity graph G associated with $k$.
3. Search G for a sequence of adjacent cells between $q_{init}$ and
   $q_{goal}$·
4. If the search terminates successfully, return the generated sequence of cells; otherwise, return failure.