Set inversion

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 (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[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:

  1. if f ([x]) ⊂ Y we conclude that [x] ⊂ X;
  2. if f ([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  −1([4,9]) where f (x1, x2) = x2
1 + x2
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.

A ring defined as a set inversion problem

Application

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]

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". GPS Solutions. 15 (4): 357–368. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.