Seminar by Apurva Mudgal
A Near-tight Approximation Algorithm for Robot Localization
Apurva Mudgal
Indian Institute of Technology, Ropar
Date: Monday, April 5, 2010
Time: 5:15 PM
Venue: CS102.
Abstract:
Localization is a fundamental problem in robotics. The "kidnapped robot" possesses a compass and a map of its environment; it must determine its location at a minimum cost of travel distance. The problem is $NP$-hard to even minimize within a factor of $c\log n$, where $n$ is the map size. No efficient approximation algorithm is known. We give an $O(\log^3 n)$-factor approximation algorithm which runs is 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 $c\log^{2-\varepsilon}(n)$ lower bound, assuming $NP$ is not contained in $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.