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