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 2D 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.