The brushfire algorithm uses a grid to approximate distance, and hence the repul- sive function. It produces a map of distance values to the nearest obstacle.
The wave-front planner affords the simplest solution to the local minima problem, but can only be implemented in spaces that are represented as grids.
If we knew that many paths were to be planned in the same environment, then it would make sense to construct a data structure once and then use that data structure to plan subsequent paths more quickly. This data structure is often called a map, and mapping is the task of generating models of robot environments from sensor data.
The defining characteristics of a visibility map are that its nodes share an edge if they are within line of sight of each other, and that all points in the robot’s free space are within line of sight of at least one node on the visibility map.
These structures represent the free space by the union of simple regions called cells. The shared boundaries of cells often have a physical meaning such as a change in the closest obstacle or a change in line of sight to surrounding obstacles.
The trapezoidal decomposition comprises two-dimensional cells that are shaped like trapezoids. Some cells can be shaped like triangles, which can be viewed as degenerate trapezoids where one of the parallel sides has a zero-length edge. To form the decomposition, at each vertex draw two segments, one called an upper vertical extension and the other called a lower vertical extension. The upper and lower vertical extensions start at the vertex and terminate when they first intersect an edge of the polygon that lies immediately above and below it, respectively.