Abstract

S. Koenig, A. Mudgal and C. Tovey. A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem. In Symposium on Discrete Algorithms (SODA), pages 133-142, 2006.

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 number of vertices. No approximation algorithm has been known. We give a O(log3 n)-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-ε n lower bound, assuming NP ⊄ 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.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.


This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.