Localizing a Robot with Minimum Travel

摘要

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 su ce 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 di culty, 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 a priori knowing which of the hypothetical locations in H is the true initial location of the robot. In this paper, we de ne a natural, algorithmic variantof 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 = jHj 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.