The robot localization problem in two dimensions

Abstract

We consider the following problem: given a simple polygon P and a star-shaped polygon V, find a point (or the set of points) in P from which the portion of P that is visible is congruent to V. The problem arises in the localization of robots using a range-finder—P 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 P 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 P, and A is the number of points in P 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 P. 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.