Login
Login

set inversion

{{Short description|Mathematical problem of finding the set mapped by a specified function to a certain range}}

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 ∈ Rn | f(x) ∈ Y }. It can also be viewed as the problem of describing the solution set of the quantified constraint "Y(f{{hairsp}}(x))", where Y(y) is a constraint, e.g. an inequality, describing the set 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

{{cite journal|last1=Jaulin|first1=L.|last2=Walter|first2=E.|title=Set inversion via interval analysis for nonlinear bounded-error estimation|journal=Automatica|year=1993|volume=29|issue=4|url=http://www.ensta-bretagne.fr/jaulin/paper_automatica93.pdf

|doi=10.1016/0005-1098(93)90106-4|pages=1053–1064}}

using interval analysis combined with a branch-and-bound algorithm.

{{cite book|last1=Jaulin|first1=L.|last2=Kieffer|first2=M.|last3=Didrit|first3=O.|last4=Walter|first4=E.|

title=Applied Interval Analysis|year=2001|publisher=Springer|location=Berlin|isbn=1-85233-219-0}}

The main idea consists in building a paving of Rp made with non-overlapping boxes. For each box [x], we perform the following tests:

  1. if f{{hairsp}}([x]) ⊂ Y we conclude that [x] ⊂ X;
  2. if f{{hairsp}}([x]) ∩ Y = ∅ we conclude that [x] ∩ X = ∅;
  3. 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.

Example

The set X = f{{hairsp}}−1([4,9]) where f{{hairsp}}(x1, x2) = x{{su|b=1|p=2}} + x{{su|b=2|p=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,{{sqrt|5}}]2 = [0,1] + [4,5] = [4,6] is inside [4,9], we conclude that the whole box [−1,1] × [2,{{sqrt|5}}] is inside X.

File:Wiki ring.png

Application

Set inversion is mainly used for path planning, for nonlinear parameter set estimation,

{{cite journal|last1=Jaulin|first1=L.|last2=Godet|first2=J.L|

last3=Walter|first3=E.|last4=Elliasmine|first4=A.|

last5=Leduff|first5=Y.|

title=Light scattering data analysis via set inversion|journal=Journal of Physics A: Mathematical and General|year=1997|volume=30|issue=22 |url=http://www.ensta-bretagne.fr/jaulin/simcf4.pdf|doi=10.1088/0305-4470/30/22/012|pages=7733–7738|bibcode=1997JPhA...30.7733J}}

{{cite journal|last1=Braems|first1=I.|last2=Berthier|first2=F.|last3=Jaulin|first3=L.|last4=Kieffer|first4=M.|last5=Walter|first5=E.|

title=Guaranteed Estimation of Electrochemical Parameters by Set Inversion Using Interval Analysis|journal=Journal of Electroanalytical Chemistry|year=2001|volume=495|issue=1|url=http://www.ensta-bretagne.fr/jaulin/electrochimie.pdf}}

for localization

{{cite journal|last1=Colle|first1=E.|last2=Galerne|first2=S.|

title=Mobile robot localization by multiangulation using set inversion|journal=Robotics and Autonomous Systems|year=2013|volume=66|issue=1|pages=39–48 |doi=10.1016/j.robot.2012.09.006}}

{{cite journal|last1=Drevelle|first1=V.|last2=Bonnifait|first2=Ph.|

title=A set-membership approach for high integrity height-aided satellite positioning|

journal=GPS Solutions|year=2011|volume=15|issue=4|pages=357–368 |doi=10.1007/s10291-010-0195-3 |bibcode=2011GPSS...15..357D |s2cid=121728552 |url=https://hal.science/hal-00608133/file/Drevelle_rev3_HAL.pdf}}

or for the characterization of stability domains of linear dynamical systems.

{{cite journal|last1=Walter|first1=E.|last2=Jaulin|first2=L.|

title=Guaranteed characterization of stability domains via set inversion|

journal=IEEE Trans. Autom. Control|year=1994|volume=39|issue=4|pages=886–889 |doi=10.1109/9.286277 |url=http://www.ensta-bretagne.fr/jaulin/IEEEStab.pdf}}

References

{{Reflist|2}}

Category:Topology