The Perception Model for Proximity Sensors

 

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]):

1. Known obstacles: If the sensor detects an obstacle the resulting distribution is modeled by a Gaussian distribution with mean at the distance to this obstacle. Let denote the probability of measuring distance d if the robot is at location l, assuming that the sensor beam is reflected by the closest obstacle in the map (along the sensor beam). We denote the distance to this specific obstacle by . The probability is then given by a Gaussian distribution with mean at :

    

   The standard deviation of this distribution models the uncertainty of the measured distance, based on

   • the granularity of the discretization of L, which represents the robot's position,
   • the accuracy of the world model, and
   • the accuracy of the sensor.

   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.

    

2. Unknown obstacles: In Markov localization, the world model generally is assumed to be static and complete. However, mobile robot environments are often populated and therefore contain objects that are not included in the map. Consequently, there is a non-zero probability that the sensor is reflected by an obstacle not represented in the world model. Assuming that these objects are equally distributed in the environment, the probability of detecting an unknown obstacle at distance is independent of the location of the robot and can be modeled by a geometric distribution. This distribution results from the following observation. A distance is measured if the sensor is not reflected by an obstacle at a shorter distance and is reflected at distance . The resulting probability is

    

   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.

Obviously, only one of these two cases can occur at a certain point in time, i.e., the sensor beam is either reflected by a known or an unknown object. Thus, is a a mixture of the two distributions and . To determine the combined probability of measuring a distance if the robot is at location l we consider the following two situations: A distance is measured, if {

1. the sensor beam is
   1. not reflected by an unknown obstacle before reaching distance

       

   2. and reflected by the known obstacle at distance

       

2. OR the beam is
   1. reflected neither by an unknown obstacle nor by the known obstacle before reaching distance

      

   2. and reflected by an unknown obstacle at distance

       

The parameter in Equation (25) denotes the probability that the sensor detects the closest obstacle in the map. These considerations for the combined probability are summarized in Equation (28). By double negation and insertion of the Equations (24) to (27), we finally get Equation (31).

    

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.