As mentioned above, the likelihood that a sensor reading s is measured at position l has to be computed for all positions l in each update of the Markov localization algorithm (see Table 1). Therefore, it is crucial for on-line position estimation that this quantity can be computed very efficiently. [Moravec1988] proposed a method to compute a generally non-Gaussian probability density function over a discrete set of possible distances measured by an ultrasound sensor at location l. In a first implementation of our approach [Burgard et al. 1996] we used a similar method, which unfortunately turned out to be computationally too expensive for localization in real-time.
To overcome this disadvantage, we developed a sensor-model which allows to compute solely based on the distance to the closest obstacle in the map along the direction of the sensor. This distance can be computed by ray-tracing in occupancy grid maps or CAD-models of the environment. In particular, we consider a discretization of possible distances measured by a proximity sensor. In our discretization, the size of the ranges is the same for all i, and corresponds to the maximal range of the proximity sensor. Let denote the probability of measuring a distance if the robot is at location l. In order to derive this probability we first consider the following two cases (see also [Hennig1997, Fox1998]):
The standard deviation of this distribution models the uncertainty of the measured distance, based on
Figure 4(a) gives examples of such Gaussian distributions for ultrasound sensors and laser range-finders. Here the distance to the closest obstacle is 230cm. Observe here that the laser sensor has a higher accuracy than the ultrasound sensor, as indicated by the smaller variance.
In this equation the constant is the probability that the sensor is reflected by an unknown obstacle at any range given by the discretization.
A typical distribution for sonar and laser measurements is depicted in Figure 4(b). In this example, the relatively large probability of measuring 500cm is due to the fact that the maximum range of the proximity sensors is set to 500cm. Thus, this distance represents the probability of measuring at least 500cm.
To obtain the probability of measuring , the maximal range of the sensor, we exploit the following equivalence: The probability of measuring a distance larger than or equal to the maximal sensor range is equivalent to the probability of not measuring a distance shorter than . In our incremental scheme, this probability can easily be determined:
To summarize, the probability of sensor measurements is computed incrementally for the different distances starting at distance cm. For each distance we consider the probability that the sensor beam reaches the corresponding distance and is reflected either by the closest obstacle in the map (along the sensor beam), or by an unknown obstacle.
In order to adjust the parameters , and of our perception model we collected eleven million data pairs consisting of the expected distance and the measured distance during the typical operation of the robot. From these data we were able to estimate the probability of measuring a certain distance if the distance to the closest obstacle in the map along the sensing direction is given. The dotted line in Figure 5(a) depicts this probability for sonar measurements if the distance to the next obstacle is 230cm. Again, the high probability of measuring 500cm is due to the fact that this distance represents the probability of measuring at least 500cm. The solid line in the figure represents the distribution obtained by adapting the parameters of our sensor model so as to best fit the measured data. The corresponding measured and approximated probabilities for the laser sensor are plotted in Figure 5(b).
The observed densities for all possible distances to an obstacle for ultrasound sensors and laser range-finder are depicted in Figure 6(a) and Figure 6(c), respectively. The approximated densities are shown in Figure 6(b) and Figure 6(d). In all figures, the distance is labeled ``expected distance''. The similarity between the measured and the approximated distributions shows that our sensor model yields a good approximation of the data.
Please note that there are further well-known types of sensor noise which are not explicitly represented in our sensor model. Among them are specular reflections or cross-talk which are often regarded as serious sources of noise in the context of ultra-sound sensors. However, these sources of sensor noise are modeled implicitly by the geometric distribution resulting from unknown obstacles.