The map-building and exploration strategies of a simple, sonar-equipped, mobile robot; an experimental, quantitative evaluation.

This thesis documents an experimental investigation into the map-building and exploration capabilities of a mobile robot. A map enables a robot to predict the state of its environment and plan its actions accordingly. This ability is essential in a wide range of practical applications. The map-building research begins with a thorough experimental evaluation of the robot's ultrasonic rangefinder, leading to a model which minimises the uncertainty caused by the wide beam and uneven signal strength of the sensor. Two types of map are used: a set of line and point features, and a grid-based free-space map. Potential features are extracted from the processed sonar data and classed as 'confirmed' if detected repeatedly. The free-space map is derived from the set of confirmed features. A distance transform algorithm is then used to plan paths on this map. This research places exceptional stress on the need for practical experimentation and quantitative, statistical, evaluation of the results. For this to be possible, it is essential to have a clearly-defined measure of map quality. A novel metric is defined which predicts the effectiveness of the robot if it were to use the map to execute a set of test tasks. This metric is shown to correspond closely to an intuitive understanding of quality. The confirmed features are used by a Kalman filter to estimate the robot's position relative to known objects. This localisation algorithm is shown to produce dramatic improvements in map quality in the later stages of exploration. Exploration strategies are tested experimentally in a range of environments and starting positions. The results are evaluated and compared statistically. The tested strategies range from totally reactive to primarily map-based. The most promising results are observed from hybrid exploration strategies which combine the robustness of reactive navigation and the directive power of map-based strategies