1031`S`Ì

任意数の制約階層化
2007/10/31
上田研究室
M2 西村光弘
背景
強い制約（必ず満たされなければならな
い）のみで記述し、期待される挙動をする
モデルを作るのは容易でない
デバグのための有用な情報を得るのに


手間がかかる
情報はあるがあまり有用でない
2
書き換え規則に基づく制約階層
の導入
HCC
処理系
書き換え
処理系
制約階層の
概念を含む
ファイル
（ユーザ記述）
計算結果
HCC
ファイル
書き換え
計算
3
書き換え規則
Strong C1
Weak C2
強い制約と弱い制約が両
方存在


強い制約を残す
弱い制約を削除
片方しか制約がない

C1,
if S(C1)≠φ then {
if S(C1)∩S(C2)≠φ then
S(H)=S(C1)∩S(C2)
else
S(H)=S(C1)
}
else
S(H)=S(C2)
その制約を適用
4
問題点
３階層以上に同様の概念を適用した
↓
元のHCC処理系でエラーなく動くソースに書き換
えるのは難しい
理由
 制約の強弱を判定する部分の外部に判定する制約を
置かない限り、判定が不可能だから
 つまり、HCCファイル上から消し去れない制約が２つ
以上あるとこの書き換えは不可能
5
初期値はエラーの
起こる直前のフェーズ
最終値
階層化の別アプローチ
HCC処理系を動かす
＋サンプルをとる
階層化したHCC
ファイルを読み込む
制約の強弱をはずす
初期値を最終値に設定
制約を元の状態に戻す
HCC処理系を動かす
＋サンプルをとる
エラーを検出
エラーを検出した
フェーズで制約の
強弱を見に行き、
弱い制約を削除
NO
YES
6
例
x
30
20
10
x=10,
初期値
always {
x’
weak x'=10,
-5 0 5 10
if(x>20) then medium x'=5,
when(x=30) do{
do strong always x'=-5 watching(x=10)
}
}
7
期待どおりに動かない例１
x=10,
always {
if(x<10) then medium x’=20,
weak x'=10,
if(x>20) then medium x'=5,
when(x=30) do{
do strong always x'=-5 watching(x=5)
}
}
エラーではなくinfになるため、ポイントフェーズ
にはいる点をエラーのみでは判断できない
8
期待どおりに動かない例２
x=10, y=20, y'=0,x'=1,
always{
cont(y),
cont(x),
weak y''=-9.8,
weak x''=0,
if(y=0) then{
if(prev(y')>-0.00001) then always y'=0
else storng y'=-0.8*prev (y')
},
if(x=>20) then strong x'=-prev(x')
},
ポイントフェーズで制約エラーになり、
変数の値が書き換わるモデル
9
縮小プログラム
y=20, y'=0,
always{
cont(y),
weak y''=-9.8,
if(y=0) then storng y'=-0.8*prev
(y')
初期値のprevは設定できない
}
y=-2.664535e-15, prev(y')=-1.979899e+01,
always{
cont(y),
if(y=0) then storng y'=-0.8*prev (y')
}
10
考察
エラーがでるまでHCCを走らせるだけでは
制約の強弱が捉えきれない
→フェーズごとに制約をチェックする
ポイントフェーズから値を引き継いで新た
に始めることができない
→フェーズごとに区切って、異なるソースを動か
すことが難しいので、キューもしくはストアから
制約の強弱を判定して、計算されるまでに削
除する必要がある
11
階層化の別アプローチ（その２）
HCC処理系内部の変更


一度全ての制約をstoreにtellする
エラーが起こると
 衝突する制約を判定
 制約の強弱を識別
 弱いほうの制約から削除する（キューから？）
 storeを初期化する
 もう一度、制約をstoreにtellする
 エラーが起こらなくなるかor制約が１つになるまで繰り返す
12
Point phase処理（笹嶋論文参照）
a1, a2, … at∈A ：エージェントの集合
ct ：エージェントat で追加される制約
σ ：Tell 操作で追加された制約の集合である制約ストア。

初期制約ストアをσ0 とする。
エージェントat によって制約ct が追加されたときの制約ストアをσt で表すと、
σ0 とσt の差分の列< c0, c1,…ct > を制約トレースと呼ぶ。
S ：この制約トレース内の制約と, それに対応したエージェントの列P の集合
point phaseでは、A が空になるまで処理が続けられる。
制約ストアσt に制約ct がTell される。ここで制約の矛盾が返されると制約エ
ラーを返し処理を中断する。
size(σt) > size(σt-1) で先の制約ct が制約ストアに追加されたことを確認し
て制約トレースにPt が追加される。
13
Point phaseアルゴリズム
S ← {}; t ← 0;
while A do
tell ct to σt;
if Constraint Error then break;
if size(σt) > size(σt-1)
then {
Pt← Pt∪<at, ct>;
S ← S∪Pt;
σt←σt-1; t ← t + 1;
}
end while
エージェントの集合：a1, a2・・・at∈A
制約ストア: σt
制約: ct
Pt = <at, ct>
集合S : P1, P2,・・・∈S
14
Queue有り
S ← {}; t ← 0;
while a∈A do
enqueue(q, a);
キュー： q
エージェントの集合：a1, a2・・・at∈A
制約ストア: σt
制約: ct
Pt = <at, ct>
集合S : P1, P2,・・・∈S
end while
while q do
at ← dequeue(q);
tell ct to σt;
if Constraint Error then break;
if size(σt) > size(σt-1)
then Pt← Pt∪<at, ct>; S ← S∪Pt;σt←σt-1; t ← t + 1;
end while
15
階層化別アプローチ２・アルゴリズム
S ← {}; t ← 0;
while all a∈A do
enqueue(q, a);
end while
キュー： q
エージェントの集合：a1, a2・・・at∈A
制約ストア: σt
制約: ct
Pt = <at, ct>
集合S : P1, P2,・・・∈S
集合∑:σ1,σ2・・・σt∈∑
:here
while q do
at ← dequeue(q);
tell ct to σt;
if Constraint Error then{
for(i=1…t) σi ← {};
q = NULL;
while A do
enqueue(q, at);
end while
remove checkconst(aconfl,variable name) from qt;
goto here;}
if size(σt) > size(σt-1)
then Pt← Pt∪<at, ct>; S ← S∪Pt;σt←σt-1; t ← t + 1;
end while
16
Checkconst関数
最後にtellして衝突した
制約をもつエージェント
checkconst(aconfl,variable name){
極小部分集合を求めるアルゴリズム
→aconflのcconflと衝突する制約集合C
各制約の強さを識別番号として保持してお
くとして、最弱のものをとってreturn
１つしかなければ→エラー
}
17
今後の予定
極小部分集合を求めるアルゴリズム
制約の強さの型を決める
Checkconst関数を実装
18
参考文献
細部博史:ユーザーインターフェースにおける制
約解消法の研究動向
http://research.nii.ac.jp/~hosobe/cs00tut/ind
ex.html
笹嶋唯: 「ハイブリッド並行制約プログラミングに
おける制約エラー説明機能の設計と実装」２００
６
Bjorn Carlson and Vineet Gupta：The hcc
Programmer's Manual,1999
19

Download Report