Landmark selection for path execution

A commonly used approach to self-location is for the robot to use point features or landmarks. Landmarks are typically difficult to detect and track with video or range sensors, and hence it is sensible to try to minimize the number of times the robot abandons the tracking of an already detected landmark to detect and pursue another. The problem we address in this paper is how to select the landmarks that the robot is to detect and track over different parts of a given path. We propose several algorithms with different amounts of flexibility, generality and complexity. We address the uniform cost case (all landmarks have equal cost of detection and tracking), and the weighted cost case (each landmark has its own cost). We also treat the case of different sets of landmarks having different utility measures. The algorithm complexity is low-order polynomial in the number of landmarks k, the number of straight line segments of the path, and the number of shadows cast on the path by each landmark, except when we want to take into account the usefulness of landmarks in groups, which is exponential in k.