A Survey of Cell Decomposition-based Path Planning

In this article, six obstacle-avoidance path planners are introduced to find the free path in the Euclidean plane with obstacles. Using the Dijkstra’s shortest path algorithm in a connected graph, this study discusses six path planners based on cell decompositions of the free space (obstacle avoidance space) and uses their centroids to plan the shortest free path from the start point to the end point. The six free path planners include: trapezoid decomposition, wavefront decomposition, polygon decomposition, windmill decomposition, brushfire decomposition and delaunay triangulation. In this research, we compare the time and space complexities of connected graph and advantages and disadvantages of each path planner.