G. Dudek, K. Romanik, S. Whitesides We consider the problems related to localizing a mobile robot in an environment for which the robot has a map. In particular, we are interested in the global localization problem, where no prior location estimate is available. The formalization of the localization problem is to determine the position of the robot, which has a compass and a various alternative sensing alternatives, such as having range sensing device. Since several positions in the environment may generate the same sensory data, we seek to minimize the distance the robot must travel to determine its exact location. One example of this class of problem is that of a point robot in an n-vertex polygonal environment with a perfect range sensor. The view from a single position can have up to an n-fold ambiguity. We have shown that finding the optimal shortest path to resolve the ambiguity is NP-complete. We are developing both lower bound results and algorithms with provable good performance in comparison to the optimal.