Misplaced Pages

Set inversion

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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(Y ) = {x ∈ R | 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 to R and the set Y is a box of R (i.e. a Cartesian product of p intervals of R).

When f is nonlinear the set inversion problem can be solved using interval analysis combined with a branch-and-bound algorithm.

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

  1. if f () ⊂ Y we conclude that ⊂ X;
  2. if f () ∩ Y = ∅ we conclude that ∩ X = ∅;
  3. Otherwise, the box 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) 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() where f (x1, x2) = x
1 + x
2 is represented on the figure.

For instance, since + = + = does not intersect the interval , we conclude that the box  ×  is outside X. Since + = + = is inside , we conclude that the whole box  ×  is inside X.

A ring defined as a set inversion problem

Application

Set inversion is mainly used for path planning, for nonlinear parameter set estimation, for localization or for the characterization of stability domains of linear dynamical systems.

References

  1. 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.
  2. Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0.
  3. 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 (22): 7733–7738. Bibcode:1997JPhA...30.7733J. doi:10.1088/0305-4470/30/22/012.
  4. 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).
  5. Colle, E.; Galerne, S. (2013). "Mobile robot localization by multiangulation using set inversion". Robotics and Autonomous Systems. 66 (1): 39–48. doi:10.1016/j.robot.2012.09.006.
  6. Drevelle, V.; Bonnifait, Ph. (2011). "A set-membership approach for high integrity height-aided satellite positioning" (PDF). GPS Solutions. 15 (4): 357–368. Bibcode:2011GPSS...15..357D. doi:10.1007/s10291-010-0195-3. S2CID 121728552.
  7. Walter, E.; Jaulin, L. (1994). "Guaranteed characterization of stability domains via set inversion" (PDF). IEEE Trans. Autom. Control. 39 (4): 886–889. doi:10.1109/9.286277.
Category:
Set inversion Add topic