Abstract

C. Tovey and S. Koenig. Localization: Approximation and Performance Bounds to Minimize Travel Distance.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^{2} 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}.

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.