The localization problem for mobile robots

A fundamental task for an autonomous mobile robot is that of localization | determining its location in a known environment. This problem arises in settings that range from the computer analysis of aerial pho-tographs to the design of autonomous Mars rovers. Guibas, Motwani, and Raghavan have given geomet-ric algorithms for the problem of enumerating loca-tions for a robot consistent with a given view of the environment. Here, we provide an on-line algorithm for a robot to move within its environment so as to uniquely determine its location. The algorithm im-proves asymptotically on strategies based purely on the \spiral search " technique of Baeza-Yates, Culberson, and Rawlins; an interesting feature of our approach is the way in which the robot is able to identify \crit-ical directions " in the environment which allow it to perform late stages of the search more eciently.