We conjecture that a key advantage of the original Markov localization technique lies in its ability to recover from extreme localization failures. Re-localization after a failure is often more difficult than global localization from scratch, since the robot starts with a belief that is centered at a completely wrong position. Since the filtering techniques use the current belief to select the readings that are incorporated, it is not clear that they still maintain the ability to recover from global localization failures.
To analyze the behavior of the filters under such extreme conditions,
we carried out a series of experiments during which we manually
introduced such failures into the data to test the robustness of these
methods in the extreme. More specifically, we ``tele-ported'' the
robot at random points in time to other locations. Technically, this
was done by changing the robot's orientation by 180 
degree
and shifting it by 0 
cm, without letting the robot know.
These perturbations were introduced randomly, with a probability of
0.005 per meter of robot motion. Obviously, such incidents make the
robot lose track of its position. Each method was tested on 20
differently corrupted versions of both datasets. This resulted in a
total of more than 50 position failures in each dataset. For each of
these failures we measured the time until the methods re-localized the
robot correctly. Re-Localization was assumed to have succeeded if the
distance between the estimated position and the reference path was
smaller than 45cm for more than 10 seconds.
Table 3: Summary of recovery experiments.
Table 3 provides re-localization results for the
various methods, based on the two different datasets. Here
represents the average time in seconds
needed to recover from a localization error. The results are
remarkably different from the results obtained under normal
operational conditions. Both conventional Markov localization and the
technique using distance filters are relatively efficient in
recovering from extreme positioning errors in the first dataset,
whereas the entropy filter-based approach is an order of magnitude
less efficient (see first row in Table 3). The
unsatisfactory performance of the entropy filter in this experiment is
due to the fact that it disregards all sensor measurements that do not
confirm the belief of the robot. While this procedure is reasonable
when the belief is correct, it prevents the robot from detecting
localization failures. The percentage of time when the position of
the robot was lost in the entire run is given in the second row of the
table. Please note that this percentage includes both, failures due
to manually introduced perturbations and tracking failures. Again,
the distance filter is slightly better than the approach without
filter, while the entropy filter performs poorly. The average times
to recover from failures on the second
dataset are similar to those in the first dataset. The bottom row in
Table 3 provides the percentage of failures for
this more difficult dataset. Here the distance filter-based approach
performs significantly better than both other approaches, since it is
able to quickly recover from localization failures and to reliably
track the robot's position.
The results illustrate that despite the fact that sensor readings are processed selectively, the distance filter-based technique recovers as efficiently from extreme localization errors as the conventional Markov approach.