About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1992
Conference paper
The robot localization problem in two dimensions
Abstract
We consider the following problem: given a simple polygon V and a star-shaped polygon V, find a point (or the set of points) in T from which the portion of V that is visible is congruent to V. The problem arises in the localization of robots using a range-finder - V is a map of a known environment, V is the portion visible from the robot's position, and the robot must use this information to determine its position in the map. We give a scheme that preprocesses V so that any subsequent query V is answered in optimal time O(m + log n + A), where m and n are the number of vertices in V and V, and A is the number of points in V that are valid answers (the output size). Our technique allows us to trade off smoothly between the query time and the preprocessing time or space. We also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon V. We then consider a variant of the localization problem in which there is a maximum distance to which the robot can "see" - this is motivated by practical considerations, and we outline a similar solution for this case. We also show that a single localization query V can be answered in time O(mn) with no preprocessing.