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

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(log³ 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 log^2-ε n lower bound, assuming NP ⊈ ZTIME(n^polylog(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.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Joseph C. Culberson , Gregory J. E. Rawlins, Searching in the plane, Information and Computation, v.106 n.2, p.234-252, Oct. 1993 [doi>10.1006/inco.1993.1054]
• 2: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 3: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 4: I. J. Cox, Blanche - an experiment in guidance and navigation of an autonomous robot vehicle, IEEE Trans. on Robotics and Automation (1991), pp. 193--204.
• 5: Ernest Davis, Representing and acquiring geographic knowledge, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 6: Gregory Dudek , Kathleen Romanik , Sue Whitesides, Localizing a Robot with Minimum Travel, SIAM Journal on Computing, v.27 n.2, p.583-604, April 1998 [doi>10.1137/S0097539794279201]
• 7: Guy Even , Guy Kortsarz , Wolfgang Slany, On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.318-327, July 03-05, 2002
• 8: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 9: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 10: Jacob E. Goodman , Joseph O'Rourke, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 11: Leonidas J. Guibas , Rajeev Motwani , Prabhakar Raghavan, The robot localization problem in two dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.259-268, September 1992, Orlando, Florida, United States
• 12: Eran Halperin , Robert Krauthgamer, Polylogarithmic inapproximability, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780628]
• 13: Jon M. Kleinberg, The Localization Problem for Mobile Robots, FOCS 1994, pp. 521--531.
• 14: D. P. Miller, D. J. Atkinson, B. H. Wilcox, and A. H. Mishkin, Autonomous navigation and control of a Mars rover, Automatic Control in Aerospace (Selected papers from IFAC Symposium, Tsukuba, Japan, 1989), Pergamon, Oxford, UK, 1989.
• 15: C. Ming Wang, Location estimation and uncertainty analysis for mobile robots, Autonomous robot vehicles, Springer-Verlag New York, Inc., New York, NY, 1990
• 16: Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
• 17: W. D. Rencken, Concurrent localisation and map building for mobile robots using ultrasonic sensors, In Proc. of IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (1993), pp. 2129--2197.
• 18: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 19: Reid Simmons , Richard Goodwin , Karen Zita Haigh , Sven Koenig , Joseph O'Sullivan, A layered architecture for office delivery robots, Proceedings of the first international conference on Autonomous agents, p.245-252, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267723]
• 20: W. Thompson, H. Pick, B. Bennett, M. Heinrichs, S. Savitt and K. Smith, Map-based localization: The 'drop-off' problem, Proc. DARPA Image Understanding Workshop (1990), pp. 706--719.
• 21: Craig A. Tovey , Sven Koenig, Gridworlds as Testbeds for Planning with Incomplete Information, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.819-824, July 30-August 03, 2000
• 22: G. Weib, C. Wetzler and E. Von Puttkamer, Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans, Proc. of the Intl. Conf. on Intelligent Robots and Systems (1994), pp. 595--601.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming
      I.2.9 Robotics
          Subjects: Sensors

General Terms:
Algorithms, Design, Theory