Set inversion for χ-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 (SIVIA) 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 branching algorithms involving if statements. As an illustration, the static localization of a robot from bounded-error range measurements is considered. The notion of remoteness, introduced for an archetypal but realistic sonar model, allows this problem to be cast into the set-inversion framework.