Set inversion for chi-algorithms, with application to guaranteed robot localization

Characterizing the set of all parameter vectors such that their image by a vector belongs to a given set is a set-inversion problem. The algorithm set inversion via interval analysis (STVIA) makes it possible to perform this task in an approximate but guaranteed way. In the examples treated so far, the function to be inverted was given either explicitly or by a sequential algorithm. In this paper, this approach is extended to the case of branchin g algorithms involving if statements. As an illustration, the static locali zation of a robot from bounded-error range measurements is considered. The notion of remoteness, introduced for an archetypal but realistic sonar mode l, allows this problem to be cast into the set-inversion framework. (C) 200 0 IMACS/Elsevier Science B.V. All rights reserved.