任意数の制約階層化 2007/10/31 上田研究室 M2 西村　光弘

背景 強い制約（必ず満たされなければならない）のみで記述し、期待される挙動をするモデルを作るのは容易でない デバグのための有用な情報を得るのに 手間がかかる 情報はあるがあまり有用でない

書き換え規則に基づく制約階層の導入 書き換え 処理系 HCC 処理系 制約階層の 概念を含む ファイル 計算結果 HCC ファイル 書き換え （ユーザ記述）

書き換え規則 強い制約と弱い制約が両方存在 片方しか制約がない C1, if S(C1)≠φ then { Strong C1 if S(C1)∩S(C2)≠φ then S(H)=S(C1)∩S(C2) else S(H)=S(C1) } S(H)=S(C2) Strong C1 Weak C2 強い制約と弱い制約が両方存在 強い制約を残す 弱い制約を削除 片方しか制約がない その制約を適用

問題点 ３階層以上に同様の概念を適用した ↓ 元のHCC処理系でエラーなく動くソースに書き換えるのは難しい 理由 制約の強弱を判定する部分の外部に判定する制約を置かない限り、判定が不可能だから つまり、HCCファイル上から消し去れない制約が２つ以上あるとこの書き換えは不可能

階層化の別アプローチ HCC処理系を動かす 階層化したHCC ＋サンプルをとる ファイルを読み込む 制約の強弱をはずす 初期値を最終値に設定 初期値はエラーの 起こる直前のフェーズ 最終値 階層化の別アプローチ HCC処理系を動かす ＋サンプルをとる 階層化したHCC ファイルを読み込む 制約の強弱をはずす 初期値を最終値に設定 制約を元の状態に戻す HCC処理系を動かす ＋サンプルをとる エラーを検出した フェーズで制約の 強弱を見に行き、 弱い制約を削除 NO エラーを検出 YES

例 x=10, always { weak x'=10, if(x>20) then medium x'=5, 30 20 10 x=10, always { weak x'=10, if(x>20) then medium x'=5, when(x=30) do{ do strong always x'=-5 watching(x=10) } 初期値 x’ -5 5 10

エラーではなくinfになるため、ポイントフェーズ 期待どおりに動かない例１ 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になるため、ポイントフェーズ にはいる点をエラーのみでは判断できない

期待どおりに動かない例２ ポイントフェーズで制約エラーになり、 変数の値が書き換わるモデル 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') ポイントフェーズで制約エラーになり、 変数の値が書き換わるモデル

縮小プログラム 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') }

考察 エラーがでるまでHCCを走らせるだけでは制約の強弱が捉えきれない ポイントフェーズから値を引き継いで新たに始めることができない →フェーズごとに制約をチェックする ポイントフェーズから値を引き継いで新たに始めることができない →フェーズごとに区切って、異なるソースを動かすことが難しいので、キューもしくはストアから制約の強弱を判定して、計算されるまでに削除する必要がある

階層化の別アプローチ（その２） HCC処理系内部の変更 一度全ての制約をstoreにtellする エラーが起こると 衝突する制約を判定 制約の強弱を識別 弱いほうの制約から削除する（キューから？） storeを初期化する もう一度、制約をstoreにtellする エラーが起こらなくなるかor制約が１つになるまで繰り返す

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 が追加される。

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

Queue有り S ← {}; t ← 0; end while while q do at ← dequeue(q); エージェントの集合：a1, a2・・・at∈A 制約ストア: σt 制約: ct Pt = <at, ct> 集合S : P1, P2,・・・∈S S ← {}; t ← 0; while a∈A do enqueue(q, a); 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;

階層化別アプローチ２・アルゴリズム キュー： q エージェントの集合：a1, a2・・・at∈A 制約ストア: σt 制約: ct S ← {}; t ← 0; while all a∈A do enqueue(q, a); end while :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); 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; キュー： q エージェントの集合：a1, a2・・・at∈A 制約ストア: σt 制約: ct Pt = <at, ct> 集合S : P1, P2,・・・∈S 集合∑:σ1,σ2・・・σt∈∑

Checkconst関数 checkconst(aconfl,variable name){ 極小部分集合を求めるアルゴリズム 最後にtellして衝突した 制約をもつエージェント checkconst(aconfl,variable name){ 極小部分集合を求めるアルゴリズム →aconflのcconflと衝突する制約集合C 各制約の強さを識別番号として保持しておくとして、最弱のものをとってreturn １つしかなければ→エラー }

今後の予定 極小部分集合を求めるアルゴリズム 制約の強さの型を決める Checkconst関数を実装

参考文献 細部博史:ユーザーインターフェースにおける制約解消法の研究動向http://research.nii.ac.jp/~hosobe/cs00tut/index.html 笹嶋唯: 「ハイブリッド並行制約プログラミングにおける制約エラー説明機能の設計と実装」２００６ Bjorn Carlson and Vineet Gupta：The hcc Programmer's Manual,1999