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⁻¹ =. It can also be viewed as the problem of describing the solution set of the quantified constraint "Y", where Y is a constraint, e.g. an inequality, describing the set Y.
In most applications, f is a function from Rⁿ to R^p and the set Y is a box of R^p.
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^p made with non-overlapping boxes. For each box, we perform the following tests:

if f ⊂ Y we conclude that ⊂ X;
if f ∩ Y = ∅ we conclude that ∩ X = ∅;
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 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 = x + x 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.

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.