The next experiment described here is carried out based on data collected with the mobile robot Rhino during the 1994 AAAI mobile robot competition [Simmons1995]. Figure 16(a) shows an occupancy grid map [Moravec & Elfes1985, Moravec1988] of the environment, constructed with the techniques described in [Thrun et al. 1998a, Thrun1998b]. The size of the map is , and the grid resolution is 15cm.
Figure 16(b) shows a trajectory of the robot along with measurements of the 24 ultrasound sensors obtained as the robot moved through the competition arena. Here we use this sensor information to globally localize the robot from scratch. The time required to process this data on a 400MHz Pentium II is 80 seconds, using a position probability grid with an angular resolution of 3 degrees. Please note that this is exactly the time needed by the robot to traverse this trajectory; thus, our approach works in real-time. Figure 16(b) also marks positions of the robot after perceiving 5 (A), 18 (B), and 24 (C) sensor sweeps. The belief states during global localization at these three points in time are illustrated in Figure 17.
The figures show the belief of the robot projected onto the -plane by plotting for each -position the maximum probability over all possible orientations. More likely positions are darker and for illustration purposes, Figures 17(a) and 17(b) use a logarithmic scale in intensity. Figure 17(a) shows the belief state after integrating 5 sensor sweeps (see also position A in Figure 16(b)). At this point in time, all the robot knows is that it is in one of the corridors of the environment. After integrating 18 sweeps of the ultrasound sensors, the robot is almost certain that it is at the end of a corridor (compare position B in Figures 16(b) and 17(b)). A short time later, after turning left and integrating six more sweeps of the ultrasound ring, the robot has determined its position uniquely. This is represented by the unique peak containing 99% of the whole probability mass in Figure 17(c).
Figure 18 illustrates the ability of Markov localization to correct accumulated dead-reckoning errors by matching ultrasound data with occupancy grid maps. Figure 18(a) shows a typical 240m long trajectory, measured by Rhino's wheel-encoders in the 1994 AAAI mobile robot competition arena. Obviously, the rotational error of the odometry quickly increases. Already after traveling 40m, the accumulated error in the orientation (raw odometry) is about 50 degrees. Figure 18(b) shows the path of the robot estimated by Markov localization, which is significantly more correct.