KNOWPIA
WELCOME TO KNOWPIA

In mathematics, **set inversion** is the problem of characterizing the preimage *X* of a set *Y* by a function *f*, i.e., *X* = *f*^{ −1}(*Y* ) = {*x* ∈ **R**^{n} | *f*(*x*) ∈ *Y* }. It can also be viewed as the problem of describing the solution set of the quantified constraint "*Y*(*f* (*x*))", where *Y*( *y*) is a constraint, e.g. an inequality, describing the set *Y*.

In most applications, *f* is a function from **R**^{n} to **R**^{p} and the set *Y* is a box of **R**^{p} (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 **R**^{p} 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, i.e., union of non-overlapping boxes.
The algorithm can be made more efficient by replacing the inclusion tests by contractors.

The set *X* = *f*^{ −1}([4,9]) where *f* (*x*_{1}, *x*_{2}) = *x*^{2}_{1} + *x*^{2}_{2} is represented on the figure.

For instance, since [−2,1]^{2} + [4,5]^{2} = [0,4] + [16,25] = [16,29] does not intersect the interval [4,9], we conclude that the box [−2,1] × [4,5] is outside *X*. Since [−1,1]^{2} + [2,√5]^{2} = [0,1] + [4,5] = [4,6] is inside [4,9], we conclude that the whole box [−1,1] × [2,√5] is inside *X*.

Set inversion is mainly used for path planning, for nonlinear parameter set estimation,^{[3]}^{[4]} for localization^{[5]}^{[6]}
or for the characterization of stability domains of linear dynamical systems.^{[7]}

**^**Jaulin, L.; Walter, E. (1993). "Set inversion via interval analysis for nonlinear bounded-error estimation" (PDF).*Automatica*.**29**(4): 1053–1064. doi:10.1016/0005-1098(93)90106-4.**^**Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (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**: 7733–7738. Bibcode:1997JPhA...30.7733J. doi:10.1088/0305-4470/30/22/012.**^**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). doi:10.1016/j.robot.2012.09.006.**^**Drevelle, V.; Bonnifait, Ph. (2011). "A set-membership approach for high integrity height-aided satellite positioning".*GPS Solutions*.**15**(4).**^**Walter, E.; Jaulin, L. (1994). "Guaranteed characterization of stability domains via set inversion" (PDF).*IEEE Trans. Autom. Control*.**39**(4).