Robot localization - theory and practice

We consider the first stage of the robot localization problem described as follows: 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 occurs if, 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 moved. An idealized version of this problem, where the robot has a range sensor, a polygonal map, and a compass (all of which are exact, i.e. without any noise), was solved by Guibas-Motwani-Raghavan (1995). In the contest of their method, we first show that the preprocessing bounds can be expressed slightly sharper in the number of reflex vertices of the map. Then we describe an approach to modifying their scheme such that it can be applied to more realistic scenarios (e.g., with uncertain sensors) as well