Localizing a Robot with Minimum Travel


(A first paper on this work appears in the Proceedings of the 6th annual ACM-SIAM Symposium on Discrete Algorithms. A more complete version will appear sometime in SIAM J. Computing; see below to download.)

Authors:

  • Gregory Dudek (dudek@cim.mcgill.ca),
  • Kathleen Romanik (romanik@dimacs.rutgers.edu),
  • Sue Whitesides (sue@cs.mcgill.ca)

    We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location. The robot must move around and use range sensing and a compass to determine its position (i.e. localize itself). From its initial location, the robot sees a set of points called the visibility polygon V of its location. In general, this will not suffice to uniquely localize the robot, since the set H of points in P with visibility polygon V may have more than one element. To address this difficulty, we combine information from multiple vantage points seeking a strategy that minimizes the distance the robot travels to determine its exact location. An optimal localization strategy would direct the robot to follow a minimum length path to verify its location, but this is impossible to compute without {\em a priori} knowing which of the hypothetical locations in H is the true initial location of the robot.

    In this paper, we define a natural, algorithmic variant of the problem of localizing a robot with minimum travel. We then show this variant is NP-hard. Finally, we give a polynomial time approximation scheme that causes the robot to travel a distance of at most k = |H| times d, where d is the length of a minimum length tour that would allow the robot to verify its true initial location by sensing. This is remarkable in view of the fact that the length d of such a minimum length tour cannot be determined without a priori knowledge of which hypothetical location in H is the true one, and yet our strategy determines a path whose length is provably within a factor k of the best possible without using such a priori knowledge.

    A full paper in postscript form is available via this hot link (300 KB).

    Research supported by NSERC, FCAR, National Network of Centres of Excellence IRIS programme