Landmark selection for path execution

Abstract

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 addressed is how to select the landmarks that the robot is to detect and track over different parts of a given path. Several algorithms with different amounts of flexibility, generality and complexity are proposed. The authors 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). The case of different sets of landmarks having different utility measures is also treated. 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 taking into account the usefulness of landmarks in groups, which is exponential in k.