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.