DIMACS TR: 95-40
Localizing a Robot with Minimum Travel
Authors: 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 minumum 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.
Paper available at:
DIMACS Home Page