A Near-tight Approximation Algorithm for the Robot Localization Problem

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 even to minimize within factor $clog n$, where $n$ is the map size. No efficient approximation algorithm is known.

We give an $O(log3 n)$-factor algorithm which runs in polynomial time. 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 $clog^{2-epsilon} n$ lower bound, assuming $NP notsubseteq 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.