In the past, two methods have emerged as dominant for path planning in discrete grid maps. The first is the distance transform or shortest path method as described in Lengyel et al.
[7].
In this method, the goal destination is labeled with a distance value of
0.
All other locations are labeled with very high values.
The algorithm begins at the destination and each iteration visits
all locations adjacent to locations visited in the previous iteration.
The distance value for site i adjacent to previously visited site j
is updated by:
where 
is the cost or distance associated with moving from site
i to site j.
The distance transform expands around the destination in a wave front, parting at and propagating around obstacles. The shortest path from any location to the destination can then be found by following the connected sites with minimum d until d = 0 is reached.
One of the problems with this method is that it inherently comes as close to obstacles as is allowed. Another problem is that it is often applied with only 4-connected graphs. This yields a shortest path with a Manhattan distance measure that is often not desirable. Eight-connected graphs (as shown in Figure 8) yield a more direct path that is better in most applications.
Figure 8: Manhattan (left) and chamfer (right) distance connectedness
Another popular approach is the use of potential fields [6] [1]. In this case, each obstacle applies a repelling field to the robot, while the goal applies an attractive field. By applying gradient descent to the resultant potential field landscape, one can obtain a safe path, keeping obstacles at a maximum distance during the approach to the goal. One of the drawbacks, however, is the necessity to constrain the problem with a fixed boundary. Without this, it can lead to paths that stray quite far from the goal with the intent of staying away from obstacles.
In our approach, we combine the potential fields with the shortest
path method.
We first construct a labeling, 
, for all grid locations
that contains the chamfer distance to the nearest obstacle.
We then apply the wave front search starting from the goal.
However, the distance penalty for each visited site is modified by a
cost multiplier 
based on the distance to the nearest obstacle.
Thus, for a site i visited from j,
The weighting function 
begins at a high penalty
at d = 1 and ramps linearly down to 1 at
d equal to a safe distance related to the size of the robot
and the speed at which it moved.
Figure 9: Distance from obstacles labeling
Figure 10: Final cost function with path indicated
Figure 9 shows the distance labeling for the map displayed in Figure 12. One can see that the labeling clearly indicates the skeleton of the region surrounded by the obstacles as the safest. Figure 10 shows the result of applying our approach; the total cost function is mapped, as well as the chosen path.