interval propagation

A contractor associated to an equation involving the variables x₁,...,x_n is an operator which contracts the intervals [x₁],..., [x_n] (that are supposed to enclose the x_i's) without removing any value for the variables that is consistent with the equation.

A contractor is said to be atomic if it is not built as a composition of other contractors. The main theory that is used to build atomic contractors are based on interval analysis.

Example. Consider for instance the equation

: $$

x_1+x_2 =x_3,

which involves the three variables x₁,x₂ and x₃.

The associated contractor is given by the following statements

: $$

[x_3]:=[x_3] \cap ([x_1]+[x_2])

: $$

[x_1]:=[x_1] \cap ( [x_3]-[x_2])

: $$

[x_2]:=[x_2] \cap ( [x_3]-[x_1])

For instance, if

: $$

x_1 \in [-\infty ,5],

: $$

x_2 \in [-\infty ,4],

: $$

x_3 \in [ 6,\infty]

the contractor performs the following calculus

: $$

x_3=x_1+x_2 \Rightarrow x_3 \in [6,\infty ] \cap ([-\infty,5]+[-\infty ,4]) =[6,\infty ] \cap [-\infty ,9]=[6,9].

: $$

x_1=x_3-x_2 \Rightarrow x_1 \in [-\infty ,5]\cap ([6,\infty]-[-\infty ,4]) =[-\infty ,5] \cap [2,\infty ]=[2,5].

: $$

x_2=x_3-x_1 \Rightarrow x_2 \in [-\infty ,4]\cap ([6,\infty]-[-\infty ,5]) = [-\infty ,4] \cap [1,\infty ]=[1,4].

File:Before contraction.gif

File:After contraction.gif

For other constraints, a specific algorithm for implementing the atomic contractor should be written. An illustration is the atomic contractor associated to the equation

: $$

x_2=\sin(x_1),

is provided by Figures 1 and 2.

For more complex constraints, a decomposition into atomic constraints (i.e., constraints for which an atomic contractor exists) should be performed. Consider for instance the constraint

: $$

x+\sin (xy) \leq 0,

could be decomposed into

: $$

a=xy

: $$

b=\sin (a)

: $$

c=x+b.

The interval domains that should be associated to the new intermediate variables are

: $$

a \in [-\infty ,\infty ] ,

: $$

b \in [-1 ,1 ] ,

: $$

c \in [-\infty ,0].

The principle of the interval propagation is to call all available atomic contractors until no more contraction could be observed.

{{cite book|last=Cleary|first=J.L.|

title= Logical arithmetic|

year=1987|publisher=Future Computing Systems}}

As a result of the Knaster-Tarski theorem, the procedure always converges to intervals which enclose all feasible values for the variables. A formalization of the interval propagation can be made thanks to the contractor algebra. Interval propagation converges quickly to the result and can deal with problems involving several hundred of variables.

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

title= Localization of an underwater robot using interval constraints propagation|

year=2006|publisher=In Proceedings of CP 2006|

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

Consider the electronic circuit of Figure 3.

File:Electronic circuit to illustrate the interval propagation.gif Assume that from different measurements, we know that

: $$

E \in [23V,26V]

: $$

I\in [4A,8A]

: $$

U_1 \in [10V,11V]

: $$

U_2 \in [14V,17V]

: $$

P \in [124W,130W]

: $$

R_{1} \in [0 \Omega,\infty ]

: $$

R_{2} \in [0 \Omega,\infty ].

From the circuit, we have the following equations

: $$

P=EI

: $$

U_{1}=R_{1}I

: $$

U_{2}=R_{2}I

: $$

E=U_{1}+U_{2}.

After performing the interval propagation, we get

: $$

E \in [24V,26V]

: $$

I \in [4.769A,5.417A]

: $$

U_1 \in [10V,11V]

: $$

U_2 \in [14V,16V]

: $$

P \in [124W,130W]

: $$

R_{1} \in [1.846 \Omega,2.307 \Omega]

: $$

R_{2}\in [2.584 \Omega,3.355 \Omega].

{{Reflist|2}}

Category:Algebra of random variables

Category:Numerical analysis

Category:Statistical approximations