Tata Institute of Fundamental Research
A Near-tight Approximation Algorithm for the Robot Localization Problem
Seminar
Speaker:
Apurva Mudgal
Indian Institute of Technology, Ropar
Department of Computer Science and
Engineering
Nangal Roa
Date:
Monday, 28 Jun 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
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 even to minimize within factor $c\\log 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 $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.
| Speaker: | Apurva Mudgal Indian Institute of Technology, Ropar Department of Computer Science and Engineering Nangal Roa |
| Date: | Monday, 28 Jun 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
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 even to minimize within factor $c\\log 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 $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.
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 $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.