Localizing a Robot with Minimum Travel

Gregory Dudek
Kathleen Romanik
Sue Whitesides


We consider the problem of localizing a robot in a known environment
modeled 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 location, 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 to uniquely localize the robot, since the set $H$ of
points in $P$ with visibility polygon $V$ may have more than one
element.  Hence, the robot must move around and use range sensing and
a compass to determine its position (i.e.\ localize itself).  We seek
a strategy that minimizes the distance the robot travels to determine
its exact location.  We show that the problem of localizing a robot
with minimum travel is NP-hard.  We then give a polynomial time
approximation scheme that causes the robot to travel a distance of at
most $(k-1)d$, where $k = |H|$ and $d$ is the length of 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.