next up previous
Next: Experimental Results Up: Grid-based Representation of the Previous: Pre-Computation of the Sensor

Selective Update


The selective update scheme is based on the observation that during global localization, the certainty of the position estimation permanently increases and the density quickly concentrates on the grid cells representing the true position of the robot. The probability of the other grid cells decreases during localization and the key idea of our optimization is to exclude unlikely cells from being updated.

For this purpose, we introduce a thresholdgif tex2html_wrap_inline3297 and update only those grid cells l with tex2html_wrap_inline3303 . To allow for such a selective update while still maintaining a density over the entire state space, we approximate tex2html_wrap_inline3305 for cells with tex2html_wrap_inline3307 by the a priori probability of measuring tex2html_wrap_inline3309 . This quantity, which we call tex2html_wrap_inline3311 , is determined by averaging over all possible locations of the robot:


Please note that tex2html_wrap_inline3311 is independent of the current belief state of the robot and can be determined beforehand. The incremental update rule for a new sensor measurement tex2html_wrap_inline3309 is changed as follows (compare Equation (9)):


By multiplying tex2html_wrap_inline3311 into the normalization factor tex2html_wrap_inline3319 , we can rewrite this equation as


where tex2html_wrap_inline3321 .

The key advantage of the selective update scheme given in Equation (39) is that all cells with tex2html_wrap_inline3323 are updated with the same value tex2html_wrap_inline3325 . In order to obtain smooth transitions between global localization and position tracking and to focus the computation on the important regions of the state space L, for example, in the case of ambiguities we use a partitioning of the state space. Suppose the state space L is partitioned into n segments or parts tex2html_wrap_inline3333 . A segment tex2html_wrap_inline3335 is called active at time t if it contains locations with probability above the threshold tex2html_wrap_inline3297 ; otherwise we call such a part passive because the probabilities of all cells are below the threshold. Obviously, we can keep track of the individual probabilities within a passive part tex2html_wrap_inline3335 by accumulating the normalization factors tex2html_wrap_inline3325 into a value tex2html_wrap_inline3345 . Whenever a segment tex2html_wrap_inline3335 becomes passive, i.e. the probabilities of all locations within tex2html_wrap_inline3335 no longer exceed tex2html_wrap_inline3297 , the normalizer tex2html_wrap_inline3353 is initialized to 1 and subsequently updated as follows: tex2html_wrap_inline3357 . As soon as a part becomes active again, we can restore the probabilities of the individual grid cells by multiplying the probabilities of each cell with the accumulated normalizer tex2html_wrap_inline3353 . By keeping track of the robot motion since a part became passive, it suffices to incorporate the accumulated motion whenever the part becomes active again. In order to efficiently detect whether a passive part has to be activated again, we store the maximal probability tex2html_wrap_inline3361 of all cells in the part at the time it becomes passive. Whenever tex2html_wrap_inline3363 exceeds tex2html_wrap_inline3297 , the part tex2html_wrap_inline3335 is activated again because it contains at least one position with probability above the threshold. In our current implementation we partition the state space L such that each part tex2html_wrap_inline3335 consists of all locations with equal orientation relative to the robot's start location.

To illustrate the effect of this selective update scheme, let us compare the update of active and passive cells on incoming sensor data. According to Equation (39), the difference lies in the ratio tex2html_wrap_inline3373 . An example of this ratio for our model of proximity sensors is depicted in Figure 11 (here, we replaced tex2html_wrap_inline3309 by a proximity measurement tex2html_wrap_inline3001 ).


In the beginning of the localization process, all cells are active and updated according to the ratio depicted in Figure 11. The measured and expected distances for cells that do not represent the true location of the robot usually deviate significantly. Thus, the probabilities of these cells quickly fall below the threshold tex2html_wrap_inline3297 .

Now the effect of the selective update scheme becomes obvious: Those parts of the state space that do not align well with the orientation of the environment, quickly become passive as the robot localizes itself. Consequently, only a small fraction of the state space has to be updated as soon as the robot has correctly determined its position. If, however, the position of the robot is lost, then the likelihood ratios for the distances measured at the active locations become smaller than one on average. Thus the probabilities of the active locations decrease while the normalizers tex2html_wrap_inline3345 of the passive parts increase until these segments are activated again. Once the true position of the robot is among the active locations, the robot is able to re-establish the correct belief.

In extensive experimental tests we did not observe evidence that the selective update scheme has a noticably negative impact on the robot's behavior. In contrast, it turned out to be highly effective, since in practice only a small fraction (generally less than 5%) of the state space has to be updated once the position of the robot has been determined correctly, and the probabilities of the active locations generally sum up to at least 0.99. Thus, the selective update scheme automatically adapts the computation time required to update the belief to the certainty of the robot. This way, our system is able to efficiently track the position of a robot once its position has been determined. Additionally, Markov localization keeps the ability to detect localization failures and to relocalize the robot. The only disadvantage lies in the fixed representation of the grid which has the undesirable effect that the memory requirement in our current implementation stays constant even if only a minor part of the state space is updated. In this context we would like to mention that recently promising techniques have been presented to overcome this disadvantage by applying alternative and dynamic representations of the state space [Burgard et al. 1998b, Fox et al. 1999].

next up previous
Next: Experimental Results Up: Grid-based Representation of the Previous: Pre-Computation of the Sensor

Dieter Fox
Fri Nov 19 14:29:33 MET 1999