A Near-Tight Approximation Algorithm for the Robot Localization Problem

Abstract

Localization is a fundamental problem in robotics. The “kidnapped robot” possesses a compass and map of its environment; it must determine its location at a minimum cost of travel distance. The problem is NP-hard [G. Dudek, K. Romanik, and S. Whitesides, SIAM J. Comput., 27 (1998), pp. 583–604] even to minimize within factor $c\log n$ [C. Tovey and S. Koenig, Proceedings of the National Conference on Artificial Intelligence, Austin, TX, 2000, pp. 819–824], where n is the map size. No approximation algorithm has been known. We give an $O(\log^3n)$-factor algorithm. The key idea is to plan travel in a “majority-rule” map, which eliminates uncertainty and permits a link to the $\frac{1}{2}$-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a $c\log^{2-\epsilon}n$ lower bound, assuming $NP\not\subseteq ZTIME(n^{polylog(n)})$, for the grid graphs commonly used in practice. We also extend the algorithm to polygonal maps by discretizing the problem using novel geometric techniques.