Relocalization - theory and practice

We consider the following problem: a robot is at an unknown position in an indoor-environment and has to do a complete relocalization, that is, it has to enumerate all positions that it might be located at. This problem occur s when, for example, the robot "wakes up" after a breakdown (e.g., a power failure or maintenance works) and the possibility exists that it has been m oved meanwhile. An idealized version of this problem, where the robot has a range sensor, a polygonal map, and a compass, all of which are exact, that is, without any noise, was solved by Guibas et al. [5]. In the context of their method, we first show that the preprocessing bounds can be expressed slightly sharper. Then we describe an approach to modifying their scheme su ch that it can be applied to more realistic scenarios (e.g., with uncertain sensors) as well. (C) 1999 Elsevier Science B.V. All rights reserved.