Society for Industrial and Applied Mathematics (SIAM) Journal on Computing

Volume 27, Number 2

pp. 583-604, 1998.

## Localizing a Robot with Minimum Travel

### Gregory Dudek, Kathleen Romanik, Sue Whitesides

**Abstract.**

Localizing a Robot with Minimum Travel: SIAM Journal on Computing Vol. 27, Iss. 2
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.

**Key words.** robot, localization, positioning, navigation, sensing, visibility, optimization, NP-hard, competitive strategy

**AMS Subject Classifications**. 68Q25, 68T99, 68U05, 68U30

**DOI**. 10.1137/S0097539794279201