Transcript I 1

Constraint Reasoning for
Differential Models
Jorge Cruz
CENTRIA - Centre for Artificial Intelligence
DI/FCT/UNL
June 2009
1
PRESENTATION OUTLINE
• Constraint Reasoning
• Constraint Reasoning for Differential Models
• Examples: Drug Design / Epidemic Study
• Conclusions and Future Work
2
Constraint Reasoning
Continuous CSP (CCSP):
Constraint Satisfaction Problem (CSP):
set of variables
Intervals of reals
[a,b]
set of domains
set of constraints
Solution:
Numeric
(=,,)
Many
assignment of values which satisfies all the constraints
GOAL Find Solutions;
Find an enclosure of the solution space
3
Constraint Reasoning
Continuous Constraint Satisfaction Problem (CCSP):
[1,5]
y
Interval Domains
Numerical Constraints
y = x2
x+y+z  5.25
Many Solutions
x=1, y=1, z=1
...
Solution:
x=1, y=1, z=3.25
...
x
[0,2]
zx
z
[,]
assignment of values which satisfies all the constraints
GOAL Find solutions;
Find an enclosure of the solution space
4
Representation of Continuous Domains
[r1..r2]
r
[f1 .. f2]
R
F
[r..r]
F-interval
F-box
5
Solving CCSPs:
Branch and Prune algorithms
constraint propagation
box split
Safe Narrowing Functions
Strategy for
isolate canonical solutions
provide an enclosure of the solution space
6
Constraint Reasoning (vs Simulation)
Represents uncertainty as intervals of possible values
Uses safe methods for narrowing the intervals
accordingly to the constraints of the model
[0,2]
x
Simulation:
Constraint
Reasoning:
0
x1? 1
2
[1,2]
y=
x2
[1,5]
y
0 no
1
4 y4?
[1,4]
7
How to narrow the domains?
[0,2]
y=
x2
[1,5]
x
y
Safe methods are based on Interval Analysis techniques
x[a,b] x2[a,b]2=
[0,max(a2,b2)]
[min(a2,b2),max(a2,b2)]
if a0b
otherwise
If x[0,2]
Then y[0,2]2 =[0,max(02,22)]=[0,4]
 y[1,5]  y[0,4]
 y[1,5]  [0,4]
 y[1,4]
8
How to narrow the domains?
[0,2]
y=
x2
[1,5]
x
y
Safe methods are based on Interval Analysis techniques
x[a,b] x2[a,b]2=
[0,max(a2,b2)]
[min(a2,b2),max(a2,b2)]
if a0b
otherwise
NFy=x²: Y’  YX2
9
Newton Method for Finding Roots of Univariate Functions
Let f be a real function, continuous in [a,b] and differentiable in (a..b)
Accordingly to the mean value theorem:
r1,r2[a,b] [min(r1,r2),max(r1,r2)] f(r1)=f(r2)+(r1  r2)f’()
If r2 is a root of f then f(r2)=0 and so:
r1,r2[a,b] [min(r1,r2),max(r1,r2)] f(r1)=(r1  r2)f’()
And solving it in order to r2:
r1,r2[a,b] [min(r1,r2),max(r1,r2)] r2= r1f(r1)/f’()
Therefore, if there is a root of f in [a,b] then, from any point r1 in [a,b]
the root could be computed if we knew the value of 
10
Newton Method for Finding Roots of Univariate Functions
The idea of the classical Newton method is to start with an initial
value r0 and compute a sequence of points ri that converge to a root
To obtain ri+1 from ri the value of  is approximated by ri:
ri+1= rif(ri)/f’()  rif(ri)/f’(ri)
30
20
f(x)
10
r2
0
0
1
2
3
4
r5
r16
r0 r2 r1
7
8 r2
r 1 9 r0
10
0
-10
-20
x
11
Newton Method for Finding Roots of Univariate Functions
Near roots the classical Newton method has quadratic convergence
However, the classical Newton method may not converge to a root!
30
20
r1=+
f(x)
10
0
0
1
2
3
r
4
5
6
7
8
9
10
0
-10
-20
x
12
Interval Extension of the Newton Method
The idea of the Interval Newton method is to start with an initial
interval I0 and compute an enclosure of all the r that may be roots
r1,r[a,b] [min(r1,r),max(r1,r)] r= r1f(r1)/f’()
If r is a root within I0 then:
r1I0 r r1f(r1)/f’(I0)
 I0
(all the possible values of  are considered)
In particular, with r1=c=center(I0) we get the Newton interval function:
r  cf(c)/f’(I0) = N(I0)
Since root r must be within the original interval I0, a smaller safe
enclosure I1 may be computed by:
I1 = I0  N(I0)
13
Interval Extension of the Newton Method
The idea of the Interval Newton method is to start with an initial
interval I0 and compute an enclosure of all the r that may be roots
30
20
10
f(x)
r1
0
0
1
2
3
4
5
6
7
8
9
I0
c
-10
10
N(I0)
I1
-20
x
14
How to narrow the domains?
[0,2]
y=
x2
x
[1,5]
y
Safe methods are based on Interval Analysis techniques
y  x2 = 0
F(Y) = Y  [0,2]2
F’(Y) = 1
yY x[0,2] yx2=0  y N( Y)  c( Y) 
If x[0,2] and y[1,5]
2
3

[
0
,
2
]
Then y N([1,5])  3 
 [0,4]
1
 y[1,5]  [0,4]
 y[1,4]
F(c( Y))
F' ( Y)
Interval Newton method
15
How to narrow the domains?
[0,2]
y=
x2
x
[1,5]
y
Safe methods are based on Interval Analysis techniques
y  x2 = 0
F(Y) = Y  [0,2]2
F’(Y) = 1
yY x[0,2] yx2=0  y N( Y)  c( Y) 
F(c( Y))
F' ( Y)
Interval Newton method
2

c
(
Y
)

X

NFy=x²: Y’  Y  c( Y) 


1


16
How to narrow the domains?
[0,2]
y=
[1,5]
x2
x
y
Safe methods are based on Interval Analysis techniques
NFy=x²: Y’  YX2
2

c
(
Y
)

X

NFy=x²: Y’  Y  c( Y) 


1


½)
+
NFy=x²: X’  (XY½)(XY
2 

Y

c
(
X
)

NFy=x²: X’  X  c( X) 

 2X 

contractility
correctness
Y’  Y
yY yY’  ¬xX y=x2
X’  X
xX xX’  ¬yY y=x2
17
Solving a Continuous Constraint Satisfaction Problem
Constraint Propagation
[1,4]
[1,5]
y
 NFy=x²: Y’  YX2
½)
+
 NFy=x²: X’  (XY½)(XY
y = x2
x+y+z  5.25
x
[0,2]
[1,2]
zx
 NFx+y+z5.25: X’  X([,5.25]YZ)
 NFx+y+z5.25: Y’  Y([,5.25]XZ)
z
[,]
[,3.25]
[1,3.25]
 NFx+y+z5.25: Z’  Z([,5.25]XY)
 NFzx: X’  X(Z[0,])
 NFzx: Z’  Z(X[0,])
18
Solving a Continuous Constraint Satisfaction Problem
Constraint Propagation
[1,3.25]
[1,4]
[1,5]
y
y = x2
x+y+z  5.25
x
[0,2]
[1,2]
[1,3.25]
zx
 NFy=x²: Y’  YX2
½)
+
 NFy=x²: X’  (XY½)(XY
 NFx+y+z5.25: X’  X([,5.25]YZ)
 NFx+y+z5.25: Y’  Y([,5.25]XZ)
z
[,]
[,3.25]
[1,3.25]
 NFx+y+z5.25: Z’  Z([,5.25]XY)
 NFzx: X’  X(Z[0,])
 NFzx: Z’  Z(X[0,])
19
Solving a Continuous Constraint Satisfaction Problem
Constraint Propagation + Branching
Stopping Criterion
[1,3.25]
y
y = x2
x+y+z  5.25
x
[1,3.25]
x
y
z
1
1
1
1
1
3.25
x
3.25
1.5
zx
z


y = x2  y = 3.25
2.25
1.5  5.25
x+y+z
  z  2-3.25
zx
<3.25
[1,3.25]
20
How to deal with change in dynamic models?
Typically through differential equations
Classical constraint methods do not address
differential models directly
Differential model:
dv
v
dt
solution
v(0)  [0.5,1.0]
v(1)  [1.0,2.0]
Constraint model:
v(t)=v(0)et
Variables: x0, x1
Domains: [0.5,1][-1,2]
Constraints: x1 = x0e
And without using the solution form?
x0[0.5,2/e]
(non linear models)
x1[0.5e,2]
21
Constraint Reasoning for
Differential Models
3
2
dv
v
dt
1
v(0)  [0.5,1.0]
0
v(1)  [1.0,2.0]
0
0,5
1
-1
-2
All functions from [0,1] to R
22
Constraint Reasoning for
Differential Models
3
2
dv
v
dt
1
v(0)  [0.5,1.0]
0
v(1)  [1.0,2.0]
0
0,5
1
-1
-2
Functions s from [0,1] to R such that:
t[0,1]
ds(t )
 s(t )
dt
23
Constraint Reasoning for
Differential Models
3
2
dv
v
dt
1
v(0)  [0.5,1.0]
0
v(1)  [1.0,2.0]
0
0,5
1
-1
-2
Functions s from [0,1] to R such that:
t[0,1]
ds(t )
 s(t )
dt
s(0)  [0.5,1.0]
24
Constraint Reasoning for
Differential Models
dv
v
dt
v(0)  [0.5,1.0]
v(1)  [1.0,2.0]
3
2
I1
1
I0
0
0
0,5
1
-1
-2
Functions s from [0,1] to R such that:
t[0,1]
ds(t )
 s(t )
dt
s(0)  [0.5,1.0]
s(1)  [1.0,2.0]
25
Extended Continuous Constraint Satisfaction Problem
[1,5]
y
y=
CSDP
x2
x+y+z  5.25
x
[0,2]
zx
dv
v
dt
v(0)  y
v(1)  z
z
[,]
ODE system
Trajectory properties
NFCSDP: Y’  ...
Z’  ...
Implicit representation of the trajectory
Explicit representation of its properties which can be
integrated with the other constraints
Developed safe methods for narrowing the intervals
representing the possible property values
26
Trajectory Properties
maximum
k
value
areak
k
continuous function
k
minimum
firstk
t
timeMaximum
timek
27
Solving a CSDP
Maintain a safe trajectory enclosure
1.5
and safe enclosures for each
trajectory property:
s1( t)TR1
x 1  I1
0
0
t
6
x 2  I2
x 3  I3
1.5
x4  I4
x 5  I5
s2( t)TR2
...
0
0
t
6
28
Use Narrowing functions for pruning the domains through propagation
Solving a CSDP
b
max s (t )
1.5
1t3
a
TR
I
x I
s  TR
continuous function
0
0
t
6
Maximum Narrowing Functions
I  I  [a,b]
where a is the maximum lower bound of the point enclosures within [1,3]
b is the maximum upper bound of the gap enclosures within [1,3]
tp[1,3] TR (tp)  TR (tp)  [,c]
[tp1,tp2][1,3] TR ([tp1,tp2])  TR ([tp1,tp2])  [,c]
where c is the upper bound of I
29
Solving a CSDP
ds(t )
 0.7s(t )
dt

s(0) [1.25]
1.75
1.5
s(1) [, ]
t[0,1] s(t) [, ]
0.75
TR
0
0
t
0.30.408
1

Interval Picard Operator
For: t[0,1] Assume: s(t) s(0)[0.5,0.5]=[0.75,1.75]
t[0,0.3]
then: ds(t )  0.7  [0.75,1.75]  [1.225,0.525]
dt
s(t) [1.25] [0,0.3][1.225,0.525]=[0.8825,1.25]
30
Solving a CSDP
ds(t )
 0.7s(t )
dt

s(0) [1.25]
s(1) [, ]
1.5
t[0,1] s(t) [, ]
TR
Interval Picard Operator (gap enclosure):
t[0,0.3] s(t) [0.8825,1.25]
0
0
t
0.3
1

Interval Taylor Series (point enclosure):
ti=0
ti+1=0.3 h=0.3 =[0,0.3]
 0h.k3k ( k )
k h p 1 0( .p31p)1
s(0)=[1.25] s()=[0.8825,1.25]
ss((0t.i3)1 )[1s.(25
ti )]  
s ( (0t.i7)) [1.25]   s
(()0.7) p 1 [0.8825,1.25]
kk!!
 ( p 1)! ( p  1)!
k 1 
s ( k ) (t )  ( 0.7) k s(t )
p=0  s(0.3)[0.9875,1.0647]
p

p=1  s(0.3)[1.0069,1.0151]
p=2  s(0.3)[1.0131,1.0138]
Trajectory Narrowing Function
31
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[-1.0,2.0]
0
0
NF
0,5
1
-1
-2
TR =[0,1][-,]
32
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[-1.0,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0]:(0,1][-,]
33
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[-1.0,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0]:(0,1)[-,]:[1][-1.0,2.0]
Based on an Interval Taylor Series method
34
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[-1.0,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0 ]:(0,0.5)[0.45,1.8]:[0.5][0.82,1.65]:(0.5,1)[-,]:[1][-1.0,2.0]
35
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[-1.0,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0 ]:(0,0.5)[0.45,1.8]:[0.5][0.82,1.65]:(0.5,1)[0.8,2.9]:[1][1.35,2.0]
36
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[1.35,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0 ]:(0,0.5)[0.45,1.8]:[0.5][0.82,1.65]:(0.5,1)[0.8,2.9]:[1][1.35,2.0]
37
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[1.35,2.0]
0
0
0,5
1
-1
NF
-2
TR =[0][0.5,1.0 ]:(0,0.5)[0.45,1.8]:[0.5][0.82,1.22]:(0.5,1)[0.8,2.1]:[1][1.35,2.0]
38
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
3
2
I0=[0.5,1.0]
1
I1=[1.35,2.0]
0
0
NF
0,5
1
-1
-2
TR =[0][0.5,0.74]:(0,0.5)[0.45,1.3]:[0.5][0.82,1.22]:(0.5,1)[0.8,2.1]:[1][1.35,2.0]
39
Example:
Constraint Satisfaction Differential Problem
ODES,[0,1](xODE)
Value0(x0)
Value1(x1)
(fixed point)
3
2
I0=[0.5,0.74]
1
I1=[1.35,2.0]
0
0
0,5
1
-1
-2
TR =[0][0.5,0.74]:(0,0.5)[0.45,1.3]:[0.5][0.82,1.22]:(0.5,1)[0.8,2.1]:[1][1.35,2.0]
40
Application to Drug Design
Differential model of the drug absorption process:
concentration of the drug in the gastro-intestinal tract
concentration of the drug in the blood stream
dx(t )
  p1 x(t )  D(t )
dt
dy(t )
 p1 x(t )  p2 y (t )
dt
2 if 0.0  t  0.5
drug intake regimen: D(t )  
0 if 0.5  t  6.0
Periodic limit cycle (p1=1.2, p2=ln(2)/5):
1
1,5
y(t)
x(t)
0,5
1
0
0,5
0
1
2
3
t
4
5
6
0
1
2
3
t
4
5
6
41
Application to Drug Design
Important properties of drug concentration are:
maximum
y(t)
minimum
area1.0
time1.1
CSDP framework can be used for:
Bound the parameters (e.g p1) by imposing bounds on these properties
Should be kept between 0.8 and 1.5
Area under curve above 1.0 between 1.2 and 1.3
Cannot exceed 1.1 for more than 4 hours
p1[0.0 , 4.0]
p1[1.3 , 1.4]
42
Application to Drug Design
Important properties of drug concentration are:
maximum
y(t)
minimum
area1.0
time1.1
CSDP framework can be used for:
Compute safe bounds for these properties for chosen parameters
p1[1.3 , 1.4]
Is guaranteedly kept between 0.881 and 1.462 ([0.8,1.5])
Area under curve above 1.0 between 1.282 and 1.3 ([1.2,1.3])
Exceeds 1.1 for 3.908 to 3.967 hours (<4.0)
43
Application to Epidemic Studies
The SIR model of epidemics:
Susceptibles: can catch the disease
Infectives: have the disease and can transmit it
Removed: had the disease and are immune or dead
dS(t )
 rS (t ) I (t )
dt
Parameters
dI (t )
 rS (t ) I (t )  aI (t )
dt
r
a
dR(t )
 aI (t )
dt
efficiency of the disease transmission
recovery rate from the infection
44
Application to Epidemic Studies
The SIR model of epidemics:
Population
800
S(t)
R(t)
rend
600
400
imax
I(t)
200
0
0
2
4
6
8
10 12 14 16 18 20 22 24
tmax
t
tend
Important questions about an infectious disease are:
the maximum number of infectives: imax
the time that it starts to decline: tmax
when will it ends: tend
how many people will catch the disease: rend
45
Application to Epidemic Studies
The SIR model of epidemics:
Population
800
S(t)
R(t)
rend
600
400
imax
I(t)
200
0
0
2
4
6
8
10 12 14 16 18 20 22 24
tmax
t
tend
CSDP framework can be used for:
Bound the parameters according to the information available about the
spread of a disease on a particular population (ex: boarding school)
46
Predict the behaviour of an infectious disease from its parameter ranges
Conclusions and Future Work
• the work extends Constraint Reasoning with ODEs
• it may support decision in applications where one is
interested in finding the range of parameters for which
some constraints on the ODE solutions are met
• it is an expressive and declarative constraint approach
• it relies on safe methods that do not eliminate solutions
• directions for further research:
Explore alternative safe methods
Apply to different models
Extend to PDEs
47
Bibliography
• Jorge Cruz. Constraint Reasoning for Differential Models
Vol: 126 Frontiers in Artificial Intelligence and Applications, IOS Press 2005
• Ramon E. Moore. Interval Analysis
Prentice-Hall 1966
• Eldon Hansen, G. William Walster. Global Optimization Using Interval Analysis
Marcel Dekker 2003
• Jaulin, L., Kieffer, M., Didrit, O., Walter, E. Applied Interval Analysis
Springer 2001
Links
• Interval Computations (http://www.cs.utep.edu/interval-comp/)
A primary entry point to items concerning interval computations.
• COCONUT (http://www.mat.univie.ac.at/~neum/glopt/coconut/)
Project to integrate techniques from mathematical programming, constraint
programming, and interval analysis.
48