We address the problem of minimum distance localization in
environments that may contain self-similarities. A mobile robot is placed at an
unknown location inside a 2D self-similar polygonal environment P. The
robot has a map of P and can compute visibility data through sensing.
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 robot's true initial location while minimizing the distance
traveled by the robot. We present two randomized approximation algorithms that
solve minimum distance localization. The performance of our algorithms is
evaluated empirically.