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.

D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\Omega(n\log n/\log\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log 2 n ) upper bound.