The relaxed intersection of m sets corresponds to the classical intersection between sets except that it is allowed to relax few sets in order to avoid an empty intersection. This notion can be used to solve constraints satisfaction problems that are inconsistent by relaxing a small number of constraints. When a bounded-error approach is considered for parameter estimation, the relaxed intersection makes it possible to be robust with respect to some outliers.

Definition

edit

The q-relaxed intersection of the m subsets   of  , denoted by   is the set of all   which belong to all   's, except   at most. This definition is illustrated by Figure 1.

 
Figure 1. q-intersection of 6 sets for q=2 (red), q=3 (green), q= 4 (blue), q= 5 (yellow).

Define  

We have  

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

Example

edit

Consider 8 intervals:            

We have

             

Relaxed intersection of intervals

edit

The relaxed intersection of intervals is not necessary an interval. We thus take the interval hull of the result. If  '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  . Then, we easily get the set

 

which corresponds to a union of intervals. We then return the smallest interval which contains this union.

Figure 2 shows the function   associated to the previous example.

 
Figure 2. Set-membership function associated to the 6 intervals.

Relaxed intersection of boxes

edit

To compute the q-relaxed intersection of m boxes of  , 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. [2] 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.

 
Figure 3. The red box corresponds to the 4-relaxed intersection of the 6 boxes

Relaxed union

edit

The q-relaxed union of   is defined by

 

Note that when q=0, the relaxed union/intersection corresponds to the classical union/intersection. More precisely, we have

 

and

 

De Morgan's law

edit

If   denotes the complementary set of  , we have

 

 

As a consequence

 

Relaxation of contractors

edit

Let   be m contractors for the sets  , then

 

is a contractor for   and

 

is a contractor for  , where

 

are contractors for

 

Combined with a branch-and-bound algorithm such as SIVIA (Set Inversion Via Interval Analysis), the q-relaxed intersection of m subsets of   can be computed.

Application to bounded-error estimation

edit

The q-relaxed intersection can be used for robust localization [3] [4] or for tracking. [5]

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

We propose here a simple example [7] to illustrate the method. Consider a model the ith model output of which is given by

 

where  . Assume that we have

 

where   and   are given by the following list

 

The sets   for different   are depicted on Figure 4.

 
Figure 4. Set of all parameter vectors consistent with exactly 6-q data bars (painted red), for q=1,2,3,4,5.

References

edit
  1. ^ Jaulin, L.; Walter, E.; Didrit, O. (1996). Guaranteed robust nonlinear parameter bounding (PDF). In Proceedings of CESA'96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation).
  2. ^ Jaulin, L.; Walter, E. (2002). "Guaranteed robust nonlinear minimax estimation" (PDF). IEEE Transactions on Automatic Control. 47 (11): 1857–1864. doi:10.1109/TAC.2002.804479.
  3. ^ Kieffer, M.; Walter, E. (2013). Guaranteed characterization of exact non-asymptotic confidence regions in nonlinear parameter estimation (PDF). In Proceedings of IFAC Symposium on Nonlinear Control Systems, Toulouse : France (2013).
  4. ^ 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.
  5. ^ Langerwisch, M.; Wagner, B. (2012). "Guaranteed Mobile Robot Tracking Using Robust Interval Constraint Propagation". Intelligent Robotics and Applications..
  6. ^ Jaulin, L. (2009). "Robust set membership state estimation; Application to Underwater Robotics" (PDF). Automatica. 45: 202–206. doi:10.1016/j.automatica.2008.06.013.
  7. ^ Jaulin, L.; Kieffer, M.; Walter, E.; Meizel, D. (2002). "Guaranteed robust nonlinear estimation with application to robot localization" (PDF). IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews. 32 (4): 374–381. doi:10.1109/TSMCC.2002.806747. S2CID 17436801. Archived from the original (PDF) on 2011-04-28.