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
SIAM Journal on Computing
Paper
The robot localization problem
Abstract
We consider the following problem: given a simple polygon script P signand a star-shaped polygon script V sign, find a point (or the set of points) in script P sign from which the portion of script P sign that is visible is translation-congruent to script V sign. The problem arises in the localization of robots equipped with a range finder and a compass - script P sign is a map of a known environment, script V sign 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 script P sign so that any subsequent query script V sign is answered in optimal time O(m+log n+A), where m and n are the number of vertices in script V sign and script P sign and script A sign is the number of points in script P sign that are valid answers (the output size). Our technique uses O(n5) space and preprocessing in the worst case; within certain limits, we can trade off smoothly between the query time and the preprocessing time and space. In the process of solving this problem, we also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon script P sign. 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 finally show that a single localization query script V sign can be answered in time O(mn) with no preprocessing.