Abstract
Common approaches for robot navigation use Bayesian filters like particle filters, Kalman filters and their extended forms. We present an alternative and supplementing approach using constraint techniques based on spatial constraints between object positions. This yields several advantages. The robot can choose from a variety of belief functions, and the computational complexity is decreased by efficient algorithms. The paper investigates constraint propagation techniques under the special requirements of navigation tasks. Sensor data are noisy, but a lot of redundancies can be exploited to improve the quality of the result. We introduce two quality measures: The ambiguity measure for constraint sets defines the precision, while inconsistencies are measured by the inconsistency measure. The measures can be used for evaluating the available data and for computing best fitting hypothesis. A constraint propagation algorithm is presented.