A randomized approach to minimum distance localization /

This thesis addresses the problem of minimum distance localization in environments that may have structural self-similarities. In other words, how can a robot most efficiently collect sensor data to estimate its position and rule out ambiguity (as opposed to merely increasing accuracy). The formalism is that a mobile robot is placed at an unknown location inside a 2 D self-similar environment modeled by a simple polygon P . The robot has a map of P, can sense its environment and hence compute visibility data. However, the self-similarities in the environment mean that the same visibility data may correspond to several different locations. The goal, therefore, is to determine the true initial location of the robot by distinguishing amongst several possibilities consistent with the sensed visibility data, while minimizing the distance traveled by the robot. We present two randomized approximation algorithms that efficiently solve the problem of minimum distance localization. The performance of our localization algorithms is validated and explored via extensive experiments on a range of simulated environments