Landmark selection for vision-based navigation

Abshncl-Recent work in Le object recognition commu-nity bas yielded a class of interest paint-based features that are stable under significant changes in scale, viewpoint, and illumination, making them ideally suited to landmark-based nmjgation. Although many such features may be visible in a given view of the robot’s environment, only B few such features are necessary lo estimate the robot’s position and orientation. In this paper, we address the problem of automatically selecting, from the entire set of features visible in the robot’s environment, the minimum (oplimal) set by which the robot can navigate its environmenL Specifically, we decompose the world into a small number of maximally sized regions such that a1 each position in a givcn region, the same small set of features is visible. We introduce a navel graph theoretic formulation of the problem and prove that it is NP-complete. Nexl, we introduee a number of approximation algurilhms and evaluate them on both synthetic and rral dau. I