Hybrid cc

Programming in hybrid
constraint languages
上田研究室 M2
中村好一
The relations between the cc languages
cc
cc
Default cc
Timed cc
= cc + defaults
Default cc
Timed cc
= cc + time
Timed default cc
Hybrid cc
= cc + defaults
+cont.time
Timed Default cc
= cc + defaults
+ discrete time
Hybrid cc
Hybrid cc
 ハイブリッドシステムのモデリングと検証を行う言語として考
案された
 離散的・連続的な動作を表現できる
Example: 部屋の温度を管理するエアコン
・部屋の温度は、連続的な微分方程式に従って変化する
・誰かが窓を開ける、中にいる人が出て行くなどの行動は
方程式を離散的に変化させる
The cc
Programming Language
制約storeとAgent(tell,ask)から構成される計算モデルを持つ
Example program: x=10,x’=0,if x>0 then x’’=-10
X = 10
X’ = 0
X = 10
if x>0 then
x’’=-10
x’ = 0
store
if y=0 then
z=1
store
if x>0 then
x’’=-10
if x>0 then
x’’=-10
if y=0 then
z=1
if y=0 then
z=1
x’’=-10
if y=0 then
z=1
x’ = 0, x = 10
store
Basic combinators:
c
add constraint c to the store.
if c then A
if c is entailed by the store, execute subprogram A, otherwise wait.
A, B
execute subprograms A and B in independently.
unless c then A if c will not be entailed in the current phase, execute A (default cc).
x’ = 0, x = 10
store
if y=0 then
z=1
x’ = 0, x =10,
x’’ = -10
Hybrid cc –
the language and its use
c : tell the constraint c
if d then A : if d holds,reduce to A
if d else A : reduce to A unless d holds
A,B : Parallel Composition
new V in A : V is local to A
hence A : execute A at every instant
after now
Hcc Example1
x=10,x'=0,
hence{if x>0 then x''=-10,
if x=0 then x' = -0.5*x'}
t=0
t=0+
t=1.414-
t=1.414
Hcc Example2
#Prey & Predator(in Hcc)#
py=8, //prey
pd=2, //predator
pd’=0.2,
always py’=0.08*py – 0.04*py*pd //prey growth
always {
cont(pd)
if(pd>=0.5*py) then
pd’=-0.1*pd+0.02*py*pd
else
pd’=-0.06*pd+0.02*py*pd
},
sample(pd), sample(py)
Prey&Predator
Figure:Prey&Predator
Computational model
プログラムにおける処理順序
1. Point Phase(離散的変化が起こる時点)
2. Interval Phase(連続的変化が起こる時点)
※ 1 , 2を交互に繰り返し行う
The Control Constructs and
Execution of hcc
 Hccの実行順序
1. Point Phaseから始まる
2. Point Phaseにおけるすべての計算を行う
3. Interval Phaseに移る
4. プログラム中の微分方程式の積分を行う(4th order Runge-Kutta法)
5. 制約の状態が変化、制約の矛盾が発生、処理時間が経過した場合に
積分を終える
6. 処理後、再びPoint Phaseに移る
同様に、1 ~ 6を繰り返す
Execution of hcc
Example;
X =0,hence{x’=1,if(x=2) then y=1}
In the interval phase following x=0,x evolves continuously
according to x’=1,through the interval(0,2) until x=2 is about to
become true.
At this point the set of constraints may change,so the next point
phase is started.
Continuous Constraints
ContConstr ::= Term RelOp Term | cont(LVariable)| lcont(LVariable)
RelOp ::= = | >= | <= | := =
Term ::= LVariableExpr | Constant | Term BinOp Term |
UnOp(Term) | dot(Term,Num) | Term’| (Term)
LVariableExpr ::= Lvariable | Uvariable.LVariableExpr
BinOp ::= + | - | ※| / |^
UnOp ::= - |log | exp | prev
・Lvariables are strings which start with a lowercase character.
・Constants are floating point numbers.
・exp(x) is the exponential function e^x.
・Term’ denotes the derivative of Term.
・dot(Term , n) denotes the nth derivative of Term(n is a natural number) .
Ask Constraints
(for Continuous Constraints)
AContConstr
ARelOp
::= Term ARelOp Term
::= = | >= |<= | < | > | !=
Non-arithmetic Constraints
Dconstr ::= UVariableExpr | UVarExpr = Dexpr
UVariableExpr ::= UVariable | UVariableExpr.UVariableExpr
Dexpr ::= UVariableExpr | prev(UVariableExpr) |
String
|(VarList)HccAgent
|(VarList)[VarList]HccAgent
|UVariableExpr(VarList)
[VarList]HccAgent
VarList ::= Uvariable | Lvariable | VarList,VarLIst
・Uvariable is a string starting with an uppercase character.
・HccAgent is hcc Agent.
Closure & Class definition
Closure definition: X = (A,x) Agent
Class definition: X = (m,n)[A,m] Agent
Closure definition
X = (A,x)Agent
Example:
P = (n,m,Q){
if n > 0 then
new m1 in {Q(n-1,m1,Q), m:= m1*n}
else
m=1
},
Fact = (n,m) {P(n,m,P)},
Fact(10,m)
Class Definition
X = (m,n)[A,m] Agent
Example:
Planet = (initvx,initvy,initpx,initpy,m)[px,py,mass]{
px = initpx, py = initpy, px’= initvx, py’ = initvy,
always{
mass=m,
px’’:=sum(F.x,Force(F),F.Target = Self),
py’’:=sum(F.x,Force(F),F.Target = Self)
}
}
Boolean Constraints
BoolConstr ::= Atom | StrConstr | ContConstr |
Bool && BoolConstr | (BoolConstr)
ABoolConstr ::= Atom | StrConstr | AContConstr |
ABool && ABoolConstr
ABoolConstr || ABoolConstr |
(ABoolConstr)
Reduction Rules
Tell : <(Γ, c),σ,next, default → <Γ,σ U {c},next, default}
σ|- d
Ask :
<(Γ,if d then A),σ,next, default> → <(Γ,A),σ,next, default>
else : <(Γ,if d else A),σ,next,else> → <Γ,σ,next,(else, if d else A)>
Γ
σ
next
: denotes a set of Hybrid cc program fragments.
: denotes the store.
: the set of program fragments to be run in the next phase.
default : a set of suspended else statements.
σ |- c : denotes entailment checking.
Reduction rules(for Hence)
The rule for hence A differs in point and interval phases
Hence Point : <(Γ,hence A), σ, next , default> →
<Γ , σ, <next , hence A>, default>
Hence Interval : <(Γ, hence A), σ, next , default> →
<(Γ, A), σ, (next , A , hence A), default>
Γ
: denotes a set of Hybrid cc program fragments.
σ
: denotes the store.
next : the set of program fragments to be run in the next phase.
default : a set of suspended else statements.
σ |- c : denotes entailment checking.
The algorithm for interpreter
1. Run the reduction rules on the current <Γ,σ,next default>,
till no further reductions can take place.
2. If σ is inconsistent , return 0 (false).
3. If default is empty , return 1 (true).
4. Remove one statement from default – if c else A.
If σ |- c , go to step 3.
5. Add A to Γ. Run the interpreter on the current state.
If the result is 1 and σ |-/ c , return 1.
6. Undo the effects of the previous step by backtracking.
Run the interpreter on the current state.
If the result is 1 and σ |-/ c , return 1. Otherwise return 0.
A Hybrid cc program A is run as follows.
1. Run interpreter with Γ = A , and empty σ, next and default
in the point phase. If the result is 0, abort.
2. Run the interval phase with Γ= next , as returned by the point
phase.
σ , next and default are again empty. If the result is 0, abort.
Record all the tells , and also the ask constraints that were checked
during the phase.
3. Integrate the arithmetic constraints that were told in the previous
step,until one of the ask constraints changes status(i.e.goes from
false to true or unknown, etc.). Go to step 1 with Γ= next.
Nonlinear equations
 Indexicals
 Interval splitting
 The Newton-Raphson method
 The Simplex method
上記の４つを組み合わせて、非線形型制約の充足処理を行う
Indexicals
 与式f(x,y)=0をx=g(y)と書き換える方法
Example :
x + y =0, x  [0,3], and y  [-1, -2].
Then the indexical x =-y is used to set to [1, 2].
Interval splitting
 区間[a,b]を繰り返し分割する方法
 a1:smallest number 0∈f([a1,b]) and a≦a1.
Hence,if 0∈f([a,(a+b)/2]),then a1∈[a,(a+b)/2],
otherwise a1∈[(a+b)/2,b]
b1も同様に行う
Example: x^2=1 and x [-∞ , ∞].
It follows that 0 [-∞ , 0].
0 / [-∞ , -100]. a1 is determined to be in [-100 , 0].
Eventually, a1 is determined to be –1.
The Newton-Raphson method
 方程式f(x)=0の近似解を求める方法
 Intervalが狭い範囲で効果を発揮する
任意の関数f(x)について、f(x)=0なる点xを求める。
図のように適当な初期値x0においてf(x)に接線を引けば、
接線の方程式はy-f(x0)=f’(x0)(x-x0)である。したがって、
この接線とX軸との交点x1はy=0とおいて、x1=x0-f(x0)/f’(x0)
で与えられる。
次にx1でのf(x)への接線とx軸との交点をx2とする、という操作
を繰り返すと、交点はf(x)=0の解に近づく。i番目の繰り返しで、
xi+1=xi-f(xi)/f’(xi)になるので、適当なεを決めておき、
|xi+1-xi|<εになったら、xi+1を解とみなす。
Splitting & Newton-Raphson method

SplittingとNewton-Raphson methodを組み合わせる(clp
Newton)。
Example:
x^2=1 and x∈I=[-∞, ∞]
1.
2.
3.
4.
Split I recursively until I is split down to [-2,-1].
Applying the N-R method=[-1,-1] is produced.
Similarly,[1,1] is produced.
Only –1 and 1 are solutions to the equation.
The Control Constructs and
Execution of hcc
 Hccの実行順序
1. Point Phaseから始まる
2. Point Phaseにおけるすべての計算を行う
3. Interval Phaseに移る
4. プログラム中の微分方程式の積分を行う(4th order Runge-Kutta法)
5. 制約の状態が変化、制約の矛盾が発生、処理時間が経過した場合に
積分を終える
6. 処理後、再びPoint Phaseに移る
同様に、1 ~ 6を繰り返す
Runge-Kutta algorithm
k1  2k 2  2k3  k 4
yi 1  yi 
6
k1  hf xi , yi 
k2 
h

k 3  hf  xi  , y i  
2
2

・4次のルンゲクッタ法
k1 
h

k 2  hf  xi  , yi  
2
2

k 4  hf xi  h, yi  k 3 
Runge-Kutta algorithm
1. A点における傾きから
k1を計算
2. B点(xi+h/2,yi+k1/2)におけ
る傾きからk2を計算
3. C点(xi+h/2,yi+k2/2)におけ
る傾きからk3を計算
4. D点(xi+h,yi+k3)における
傾きからk4を計算
5. k1 ~k4の重み付き平均を
増分として、これをyiに加える
ことによりyi+1を求める
k1=h(xi,yi),k2=hf(xi+h/2,yi+k1/2),
k3=hf(xi+h/2,yi+k2/2),
k4=hf(ti+h,xi+k3)
yi+1=yi+(k1+2k2+2k3+k4)/6
y(x)
(xi+1,yi+1)
D
k4
k3
C
k2
(xi,yi)
k1
B
A
h/2
xi
h/2
xi+1/2
xi+1
x
Program Example
ball.hcc
/* A simple example of a ball bouncing on the floor.
*/
y = 10, y' = 0,
// initial conditions
hence {
if y > 0 then y'' = -10, // free fall
if y = 0 then
// bounce
if (prev(y') > -0.000001) then always y' = 0 // end of bouncing
else y' = -0.5 * prev(y')
},
sample(y)
ボールの軌道(5秒間)
1.20E+01
1.00E+01
8.00E+00
6.00E+00
4.00E+00
2.00E+00
0.00E+00
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
+0 E-0 E-0 E-0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0 E+0
E
00 00 00 00 20 50 80 10 40 70 00 30 60 90 20 50 80
0. 3. 6. 9. 1. 1. 1. 2. 2. 2. 3. 3. 3. 3. 4. 4. 4.
系列1
参考文献
 B.Carlson and V.Gupta.Hybrid cc with interval constraints.
 V.Gupta,R.Jagadeesan,V.A.Saraswat,and D.Bobrow.
Programming in hybrid concurrent constraint languages.In Panos
Antsakis,Wolf Kohn,Anil Nerode,and Sankar Sastry,editors,Hybrid
Systems Ⅱ,volume999 of Lecture Notes in Computer Science,1995
 V.Gupta,R.Jagadeesan,V.Saraswat,and D.Bobrow.
Programming in hybrid constraint languages

Download Report