LOCALIZING A ROBOT WITH MINIMUM TRAVEL. Kathleen A. Romanik, Gregory
Dudek, Sue Whitesides, McGill University, MontrÈal, QuÈbec,
Canada (NIST address: Building 220, Room B124, NIST, Gaithersburg, MD 20899,
301-975-5068, email: romanik@cme.nist.gov)

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|**,
which is no greater than the number of reflex vertices of **P,** 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.