A near-tight approximation lower bound and algorithm for the kidnapped robot 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 [6] even to minimize within factor c log n[21], where n is the number of vertices. No approximation algorithm has been known. We give a O(log3n)-factor algorithm. The key idea is to plan travel in a 'majority-rule' map, which eliminates uncertainty and permits a link to the 1/2-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a c log2-en lower bound, assuming NP n ZTIME(npolylog(n)), for the grid graphs commonly used in practice. We also introduce a new hypothesis equivalence decomposition of the plane, built from pairs of aspect graph duals, in order to extend the algorithm to polygonal maps.