We will now describe experiments aimed at characterizing the precision of position estimates. Our experiments also characterize the time needed for global localization in relation to the size of the grid cells. Figure 19 shows a path of the robot Rhino in the Computer Science Department's building at the University of Bonn. This path includes 22 reference positions, where the true position of the robot was determined using the scan matching technique presented in [Gutmann & Schlegel1996, Lu & Milios1994]. All data recorded during this run were split into four disjoint traces of the sensor data. Each of these different traces contained the full length of the path, but only every fourth sensor reading which was sufficient to test the localization performance.
Figure 20(a) shows the localization error averaged over the four runs and all reference positions. The error was determined for different sizes of grid cells, using a laser range-finder or ultrasound sensors. These results demonstrate (1) that the average localization error for both sensors is generally below the cell size and (2) that laser range-finders provide a significantly higher accuracy than ultrasound sensors. When using the laser range-finder at a spatial resolution of 4cm, the average positioning error can even be reduced to 3.5cm.
Figure 20(b) shows the average CPU-time needed to globally localize the robot as a function of the size of the grid cells. The values represent the computation time needed on a 266MHz Pentium II for global localization on the path between the starting point and position 1. In this experiment, we used a fixed angular resolution of four degrees. In the case of 64cm cell size, the average localization time is approximately 2.2 seconds. Of course, the effective time needed for global localization in practice highly depends on the structure of the environment and the amount of information gathered on the path of the robot. For example, due to the symmetry of the corridor of this office environment, the robot is not able to localize itself unless it enters a room. The reader may notice that recently, we developed a decision-theoretic method for actively guiding the robot to places which allow it to resolve ambiguities during global localization [Fox et al. 1998a, Fox1998]. Based on this method, the localization process becomes more efficient, especially in office environments with a lot of indistinguishable places as, for example, long corridors.
The experiments described above demonstrate that our metric variant of Markov localization is able to efficiently estimate the position of a mobile robot in dynamic environments. It furthermore can deal with approximate models of the environment such as occupancy grid maps or rough outline maps. Finally, it is able to efficiently and accurately estimate the position of a mobile robot even if ultrasound sensors are used.
