Abstract

Abstract: Localization, which is the determination of one's location in a known terrain, is a fundamental task for autonomous robots. This paper presents several new basic theoretical results about localization. We show that, even under the idealized assumptions of accurate sensing and perfect actuation, it is intrinsically difficult to localize a robot with a travel distance that is close to minimal. Our result helps to theoretically justify the common use of fast localization heuristics, such as greedy localization, which always moves the robot to a closest informative location (where the robot makes an observation that decreases the number of its possible locations). We show that the travel distance of greedy localization is much larger than minimal in some terrains because the closest informative location can distract greedy localization from a slightly farther, but much more informative, location. However, we also show that the travel distance of greedy localization can be larger, but not much larger, than the terrain size n. Thus, the travel distance of greedy localization scales well with the terrain size and is much larger than minimal in some terrains, not because it is large with respect to the terrain size, but because the minimal travel distance is exceptionally small in these terrains. As a corollary to our analysis, we show that the travel distance of greedy mapping (which always moves the robot to a closest location, where it makes an observation that increases its knowledge of the terrain) cannot be much larger than the terrain size. In theoretical terms, we prove the NP-hardness of minimization of travel distance for localization to within a logarithmic factor of the terrain size. We prove that the travel distance of greedy localization is at least order n/log² n larger than minimal in some terrains and that it is at least order n log n / log log n in the worst case. Finally, we prove that the travel distance of both greedy localization and greedy mapping is at most order n log n. Previously, it was only known that it is NP-hard to localize with minimal travel distance and that the travel distances of greedy localization and greedy mapping are at most order n^3/2.

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.