Global path planning algorithms refer to a group of navigation algorithms that plans an optimal path from a point of origin to a given goal in a known environment. This group of algorithms requires the environment to be free from dynamic and unforeseen obstacles. In this section, two key global path planning algorithms: navigation functions and roadmaps will be discussed.
The most widely used global path planning algorithm is perhaps the navigation function computed from the “wave-front expansion” (J.-C Latombe, 1991; Howie Choset et al, 2005) algorithm due to its practicality, ease in implementation and robustness. The navigation function N is the Manhattan distance to the goal from the free space in the environment. The algorithm requires information of the environment provided to the robot to be represented as an array of grid cells.
The navigation function assigns a numeric value N to each cell with the goal cell having the lowest value, and the other unoccupied cells having progressively higher values such that a steepest descent from any cell provides the path to the goal. The value of the unoccupied cell increases with the distance from the goal. Each grid cell is either free or occupied space denoted by gCfree and gCoccupied. First, the value of N is set to ‘0’ at the goal cell gCgoal. Next, the value of N is set to ‘1’ for every 1-Neighbor (see Figure 1 for the definition of 1-Neighbors) of gCgoal which is in gCfree. It is assumed that the distance between two 1-Neighbors is normalized to 1. In general, the value of each gCfree cell is set to N+1 (e.g., ‘2’) for every unprocessed gCfree 1-Neighbor of the grid cell with value N (e.g., ‘1’). This is repeated until all the grid cells are processed.
The shaded cells are the 1-Neighbor of the cell (x, y) and the number shows the priority of the neighboring cells
Finally, a path to the goal is generated by following the steepest descent of the N values. To prevent the path from grazing the obstacles, the grid cells which are less than a safety distance α from the obstacles are omitted in the computation of the navigation function. Figure 2 shows a path generated by the navigation function. The black cells are the obstacles and the grey cells are the unsafe regions.
Path generated by the navigation function