Cell Decomposition method has becoming a common technique in geometric path planning involving the division of the workspace into several convex region called cells. The main idea of this method is a feasible path between the initial configuration and goal configuration can be found by subdividing the free spaces in robot’s configuration into smaller region called cells. Usually, the free spaces are decomposed into trapezoidal and triangular cells.
The generated partition is associated with a graph, such that each cell refers to a unique vertex and each pair of the geometrically adjacent cells corresponds to a unique edge. After the decomposition, the connectivity graph will be constructed by connecting the cells that shares the similar boundary. Then, the shortest feasible path between the start and end node will be computed by using the graph searching algorithm.