Set inversion
Set inversion is the problem of characterizing the pre-image X of a set Y by a function f, i.e., X=f -1(Y) = {x ∈ Rn | f(x) ∈ Y}.
In most applications, f is a function from Rn to Rp and the set Y is a box of Rp (i.e. a Cartesian product of p intervals of R).
When f is nonlinear the set inversion problem can be solved [1] using interval analysis combined with a branch and bound algorithm. [2]
The main idea consists in building a paving of Rp made with non-overlapping boxes. For each box [x], we perform the following tests:
- if f([x]) ⊂ Y we conclude that [x] ⊂ X;
- if f([x]) ∩ Y = ∅ we conclude that [x] ∩ X = ∅;
- Otherwise, the box [x] the box is bisected except if its width is smaller than a given precision.
To check the two first tests, we need an interval extension (or an inclusion function) [f] for f. Classified boxes are stored into subpavings.
Example The set X=f −1([4,9]) where f(x1, x2) = x12 + x22 is represented on the figure.
Application Set inversion is mainly used for nonlinear parameter estimation [3] [4] for localization [5] or for stability analysis.
References
- ^ Jaulin, Luc; Walter, Eric (1993). "Set inversion via interval analysis for nonlinear bounded-error estimation" (PDF). Automatica. 29 (4).
- ^ Jaulin, Luc; Kieffer, Michel; Didrit, Olivier; Walter, Eric (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0.
- ^ Jaulin, L.; Godet, J.L; Walter, E.; Elliasmine, A.; Leduff, Y. (1997). "Light scattering data analysis via set inversion" (PDF). Journal of Physics A: Mathematical and General. 30.
- ^ Braems, I.; Berthier, F.; Jaulin, L.; Kieffer, M.; Walter, E. (2001). "Guaranteed Estimation of Electrochemical Parameters by Set Inversion Using Interval Analysis" (PDF). Journal of Electroanalytical Chemistry. 495 (1).
- ^ Colle, E.; Galerne, S. (2013). "Mobile robot localization by multiangulation using set inversion". Robotics and Autonomous Systems. 66 (1).