ARNE's application requires it to follow efficient paths to user-specified delivery points. This chapter describes how these paths are planned.

Path planning serves two purposes in this thesis. First, it is obviously necessary to move during exploration and, although some of these movements (e.g. during wall-following) may be completely reactive and not use the map, others will require ARNE to go to a specified viewpoint while avoiding known obstacles. These movements will need to be planned.

Another, less obvious, need for path planning is in the measurement of map quality. As will be seen in Chapter 10, map quality is measured by predicting how successful ARNE would be at a number of test tasks, given the latest map. Path planning is needed to make this evaluation.

Section 7.4 described the construction of a free-space map from the list of confirmed features. Path planning is based totally on this map.

The planning technique used in this thesis was first presented by Jarvis and Byrne and is described by McKerrow (1991). A ‘distance transform’ is calculated which indicates, for any given cell in the free-space map, which of the neighbouring cells is closest to the goal. This information can be used repeatedly to generate a list of cells through which the robot can reach the goal.

Section 8.1 gives a brief overview of the technique and Section 8.2 gives the implementation details.

The paths derived from the distance transform are often unnecessarily jerky, giving a zigzag path to the goal.