A near-tight approximation lower bound and algorithm for the kidnapped robot problem

Sven Koenig, Apurva Mudgal, Craig A. ToveySODA 2006 · OpenReview

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(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.
BibTeX
@inproceedings{koenig2006near,
  author = {Sven Koenig and Apurva Mudgal and Craig A. Tovey},
  title = {{A near-tight approximation lower bound and algorithm for the kidnapped robot problem}},
  booktitle = {SODA},
  year = {2006},
  url = {https://openreview.net/forum?id=0vNoYMoUqgF},
}

Loading related content...

Figure