We consider the problem of localizing a robot in a known environment m
odeled by a simple polygon P. We assume that the robot has a map of P
but is placed at an unknown location inside P. From its initial locati
on, the robot sees a set of points called the visibility polygon V of
its location. In general, sensing at a single point will not suffice t
o uniquely localize the robot, since the set H of points in P with vis
ibility polygon V may have more than one element. Hence, the robot mus
t move around and use range sensing and a compass to determine its pos
ition (i.e., localize itself). We seek a strategy that minimizes the d
istance the robot travels to determine its exact location. We show tha
t the problem of localizing a robot with minimum travel is NP-hard. We
then give a polynomial time approximation scheme that causes the robo
t to travel a distance of at most (k - 1)d, where k = \H\, which is no
greater than the number of re ex vertices of P, and d is the length o
f a minimum length tour that would allow the robot to verify its true
initial location by sensing. We also show that this bound is the best
possible.