relaxed intersection

The q-relaxed intersection of the m subsets

$X\_\{1\},\backslash dots\; ,X\_\{m\}$

of $R^\{n\}$,

denoted by

$$

X^{\{q\}}=\bigcap^{\{q\}}X_{i}

is the set of all

$$

x \in R^{n}

which belong to all

$$

X_{i}

's, except

$q$

at most.

This definition is illustrated by Figure 1.

File:Wiki q inter def.jpg

Define

$$

\lambda (x) =\text{card} \left\{ i\ |\ x\in X_{i}\right\}.

We have

$$

X^{\{q\}}=\lambda ^{-1}([m-q,m]) .

Characterizing the q-relaxed intersection is a thus a set inversion problem.

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

title= Guaranteed robust nonlinear parameter bounding|

year=1996|publisher=In Proceedings of CESA'96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation)|

url=http://www.ensta-bretagne.fr/jaulin/paper_CESA96.pdf}}

Consider 8 intervals:

$$

X_{1}=[1,4],

$$

X_{2}=\ [2,4],

$$

X_{3}=[2,7],

$$

X_{4}=[6,9],

$$

X_{5}=[3,4],

$$

X_{6}=[3,7].

We have

$$

X^{\{0\}} = \emptyset,

$$

X^{\{1\}}=[3,4],

$$

X^{\{2\}}=[3,4],

$$

X^{\{3\}}=[2,4] \cup [6,7],

$$

X^{\{4\}}=[2,7],

$$

X^{\{5\}}=[1,9],

$$

X^{\{6\}}=]-\infty ,\infty [.

The relaxed intersection of intervals is not necessary an interval. We thus take

the interval hull of the result. If $X\_i$'s are intervals, the relaxed

intersection can be computed with a complexity of m.log(m) by using the

Marzullo's algorithm. It suffices to

sort all lower and upper bounds of the m intervals to represent the

function $\backslash lambda$. Then, we easily get the set

$$

X^{\{q\}}=\lambda^{-1}([m-q,m])

which corresponds to a union of intervals.

We then return the

smallest interval which contains this union.

Figure 2 shows the function

$\backslash lambda(x)$

associated to the previous example.

File:Wiki qinter intervals.jpg

To compute the q-relaxed intersection of m boxes of

$R^\{n\}$, we project all m boxes with respect to the n axes.

For each of the n groups of m intervals, we compute the q-relaxed intersection.

We return Cartesian product of the n resulting intervals.

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

title=Guaranteed robust nonlinear minimax estimation|

journal=IEEE Transactions on Automatic Control|

year=2002|volume=47|issue=11 |pages=1857–1864 |doi=10.1109/TAC.2002.804479 |

url=http://www.ensta-bretagne.fr/jaulin/paper_qminimax.pdf}}

Figure 3 provides an

illustration of the 4-relaxed intersection of 6 boxes. Each point of the

red box belongs to 4 of the 6 boxes.

File:Wiki q inter 6box.jpg

The q-relaxed union of $X\_1,\backslash dots\; ,X\_m$ is defined by

$$

\overset{\{q\}}{\bigcup}X_{i}=\bigcap^{\{m-1-q\}}X_i

Note that when q=0, the relaxed union/intersection corresponds to

the classical union/intersection. More precisely, we have

$$

\bigcap^{\{0\}}X_{i} =\bigcap X_i

and

$$

\overset{\{0\} }{\bigcup}X_{i} =\bigcup X_i

If $\backslash overline\{X\}$ denotes the complementary set of $X\_i$, we have

$$

\overline{\bigcap^{\{q\}}X_i} = \overset{\{q\}}{\bigcup}\overline{X_i}

$$

\overline{\overset{\{q\} }{\bigcup }X_i}=\bigcap^{\{q\}}\overline{X_i}.

As a consequence

$$

\overline{\bigcap\limits^{\{q\}}X_i}=\overline{\overset{\{m-q-1\} }{\bigcup }X_i}=\bigcap^{\{m-q-1\}}\overline{X_i}

Let $C\_1,\backslash dots\; ,C\_m$ be m contractors for the sets $X\_1,\backslash dots\; ,X\_m$,

then

$$

C([x]) =\bigcap^{\{q\}}C_i([x]).

is a contractor for $X^\{\backslash \{q\backslash \}\}$

and

$$

\overline{C}([x]) =\bigcap^{\{m-q-1\}}\overline{C}_i([x])

is a contractor for $\backslash overline\{X\}^\{\backslash \{q\backslash \}\}$, where

$$

\overline{C}_1,\dots,\overline{C}_{m}

are contractors for

$$

\overline{X}_1,\dots ,\overline{X}_m.

Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the q-relaxed

intersection of m subsets of $R^\{n\}$ can be computed.

The q-relaxed intersection can be used for robust localization

{{cite book|last1=Kieffer|first1=M.|last2=Walter|first2=E.|

title= Guaranteed characterization of exact non-asymptotic confidence regions in nonlinear parameter estimation|

year=2013|publisher=In Proceedings of IFAC Symposium on Nonlinear Control Systems, Toulouse : France (2013)|

url=http://hal-supelec.archives-ouvertes.fr/docs/00/81/94/88/PDF/Nolcos2013_KW.pdf}}

{{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=http://hal.archives-ouvertes.fr/hal-00608133/en/}}

or for tracking.

{{cite journal|last1=Langerwisch|first1=M.|last2=Wagner|first2=B.|

title=Guaranteed Mobile Robot Tracking Using Robust Interval Constraint Propagation|

journal=Intelligent Robotics and Applications|

year=2012}}.

Robust observers can also be implemented using the relaxed intersections to be robust with respect to outliers.

{{cite journal|last=Jaulin|first=L.|

title=Robust set membership state estimation; Application to Underwater Robotics|

journal=Automatica|

year=2009|volume=45|

url=http://www.ensta-bretagne.fr/jaulin/paper_sauce_automatica.pdf|

doi=10.1016/j.automatica.2008.06.013|pages=202–206}}

We propose here a simple example

{{cite journal|last1=Jaulin|first1=L.|last2=Kieffer|first2=M.|last3=Walter|first3=E.|last4=Meizel|first4=D.|title=Guaranteed robust nonlinear estimation with application to robot localization |journal=IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews |year=2002|volume=32|issue=4 |pages=374–381 |url=http://www.ensta-bretagne.fr/jaulin/robab.pdf|url-status=dead|archiveurl=https://web.archive.org/web/20110428224956/http://www.ensta-bretagne.fr/jaulin/robab.pdf|archivedate=2011-04-28 |doi=10.1109/TSMCC.2002.806747|s2cid=17436801 }}

to illustrate the method.

Consider a model the ith model output of which is given by

$$

f_i(p)=\frac{1}{\sqrt{2\pi p_2}}\exp (-\frac{(t_i-p_1)^{2}}{2p_2})

where $p\backslash in\; R^\{2\}$. Assume that we have

$$

f_i(p) \in [y_i]

where $t\_i$ and $[y\_i]$ are given by the following list

$$

\{ (1,[0;0.2]),(2,[0.3;2]),(3,[0.3;2]),(4,[0.1;0.2]),(5,[0.4;2]),(6,[-1;0.1]) \}

The sets $\backslash lambda^\{-1\}(q)$ for different $q$ are depicted on

Figure 4.

File:Wiki qinter robab.jpg

{{Reflist|2}}

Category:Satisfiability problems

Category:Estimation theory