ハイブリッド並行制約プログラミング における制約の階層化

Presentation on theme: "ハイブリッド並行制約プログラミング における制約の階層化"— Presentation transcript:

1 ハイブリッド並行制約プログラミング における制約の階層化
ハイブリッド並行制約プログラミング　　　における制約の階層化 2008/2/8 上田研究室 学籍番号：3606U079-7 西村　光弘

2 ハイブリッド並行制約 プログラミング言語（HCC）
制御を可能とする。 制約プログラミングに基づいた宣言型モデリング言語 py=8, //initial value of prey pd=2,　　//initial value of predator always py’=0.08*py – 0.04*py*pd, //prey growth pd’=0.2, always { cont(pd),　　//連続値宣言 if (pd >= 0.5*py) then //predator growth pd’= -0.1*pd *py*pd else pd’= -0.06*pd *py*pd }, sample(pd, py) 目標 実行中に計算・シミュレーションが破綻しないロバスト性 より実用的かつ容易に記述できるインタラクティブ環境 HCCは連続的変化と離散的変化からなるハイブリッドシステムを表現するのに適したモデリング言語です。右図はHCCのコードの例 そして目標は２点ありますが、本研究では赤くハイライトしてある、より実用的かつ容易に記述できるようにすること目標にしました。 prey ＆ predator code

3 背景と目的 背景 目的 HCCに階層化を導入する ユーザの期待する挙動のHCCコードに、到るまでの思考過程が難しい
理由 ある変数に関わる制約がすべて同一階層上にある すべての制約間に矛盾がなくモデリングすることが難しい 並行処理を時間の経過と共に追うのが困難 HCC特有の表現（cont,lcont） HCCプログラミングで制約間矛盾をチェックする個数が多くなる 全変数のpointフェーズでcont, lcontが必要かチェックしなければならない x=1とx=5が矛盾するという単純なチェックではない x=10, x’=0 always{x’’=-9.8, if(x=0) then x’=-prev(x’)}の4制約があって変数x,x’,x’’についてそれぞれシミュレート時間の内、矛盾がないかどうか、cont,lcontが必要となるかどうか 目的 より実用的かつ容易に記述できるモデリング言語へ 　　　　　　　　　　　　　　　　　　　　　　↓ 　 　　　　HCCに階層化を導入する 例 背景として、ある程度HCCコードを記述してみて、ユーザの期待する挙動のHCCコードに、到るまでの思考過程が難しいと考えました。 その理由は、3点あり～。cont,lcontの必要性を考えなければならないことです。 具体例としてx=1とx=5が矛盾するという単純なチェックで済むのではなく、次で説明しますが、このような4制約があって変数x,x’,x’’についてそれぞれシミュレート時間の内、矛盾がないかどうか、cont,lcontが必要となるかどうかという程度のチェックが必要になるということです。 上記のような難しさがあり、目的としてより実用的かつ容易に記述できるようにするためHCCに階層化を導入することを検討しました。

4 x’=-14、x’’=-9.8から導かれるx’=14であるから制約矛盾
思考過程が難しい例 自由落下モデル（1変数1パラメータ最も単純なモデル） x=10, x’=0 always{x’’=-9.8, if(x=0) then x’=-prev(x’)} x x’ x’’ ? x 直近のinterval phase point phase interval phase integration 10 x’=-14、x’’=-9.8から導かれるx’=14であるから制約矛盾 導関数がある変数は値が引き継がれる。 導関数の値が書き換わる時、 変数値が引き継がれないためcont(x)の宣言が必要となる 研究の動機となる思考過程が難しい例を紹介します。 右図のような自由落下モデルを記述したいとして上記のコードを記述したとします。このコードをHCC処理系で動かすと期待した解は得られません。 まず、赤丸の点で制約矛盾のためエラーが起こります。理由１ 次は赤丸の点からxの値が定まりません。理由２ このように単純なモデルでも、期待した挙動をするHCCコードを作成するまでに青枠でくくった部分の思考過程が必要だという難しさがあります。 t 期待するHCCコード x=10, x’=0 always{cont(x), if(x=0) then x’=-prev(x’) else x’’=-9.8}

5 制約階層 制約を以下の制約に分類する 比較子・・・同じ強さの制約間の矛盾を解消するための基準 必須制約(required)
required x+y=z strong x=2 medium x=4,y=3 weak y=1,z=1 解 x=2, y=3, z=5 制約を以下の制約に分類する 必須制約(required) 必ず満たす制約 矛盾があると解なし 選好制約(strong, medium, weak) できるだけ満たすべき制約に優先度（強さ）をつける 強い制約が優先的に充足される 比較子・・・同じ強さの制約間の矛盾を解消するための基準 本研究の制約階層では、同じ強さの階層間での制約の矛盾はエラーとして考える 制約階層を導入するつもりですが、一般的な制約階層の概念について例を用いて説明します。 簡単に言うと、制約階層は制約を必須制約と選好制約に分類し、優先度をつけるというものです。 必須制約としてx+y=z　選好制約としてstrong、medium、weakをこのように記述したとします。 どう考えるかというと、優先度の高い上の行から制約を満たすように値を計算します。 時間あれば関連研究

6 HCCの制約階層化 制約の優先度がなくても計算が破綻しない 制約間の矛盾がある 計算し結果を出力 矛盾する制約同士の優先度を識別
最も弱い制約を削除 同階層上で矛盾する→エラー HCCコードを処理系で読み込み、制約の優先度がなくても計算が破綻しないコードについてはそのまま計算し結果を出力します。 一方、制約間の矛盾がある場合は、矛盾する制約同士の優先度を識別し、最も弱い制約を削除します。矛盾する制約同士が同階層上であるならエラーを返します。 以上を基本にすえてsyntaxとsemanticsに階層化概念を追加しました。追加したところは赤枠で囲った部分です。

7 現状のHCCコードと階層化後のコード 現状のHCCコード 階層化後のコード Ball =()[x, y]{ Ball =()[x, y]{
x = 1, x' = 6, y = 40, y' = 0, 　　always { 　　　　cont(x), 　　　　cont(y), 　　　　if (y = 30 && 0<x && x<10) 　　　　|| (y = 20 && 0<x && x<20) 　　　　|| (y = 10 && 0<x && x<30) 　　　　|| (y = 0 && x>=30) 　　　　|| (30<x && x<60 && y=30) 　　　　　　then {x''=0, y' = -0.9 * prev(y') 　　　　} else if (x=10 && 20<y && y<30) 　　　　|| (x=20 && 10<y && y<20) 　　　　|| (x=30 && 0<y && y<10) 　　　　　　then {x' = -0.9 * prev(x'), y'' = -10 　　　　} else if (x = 0 && y>=0) 　　　　|| (x=70 && y>=0) then {x' = -prev(x'), y' = 20 　　　　} else { 　　　　　　if (20<x && x<30 && 25<y && y<50) then {y'' = -3, x''=-1} 　　　　　　else if (30<x && x<40 && 0<y && y<20) then {y'' = -3, x''=1} 　　　　　　else if (40<x && x<60 && y>30) then {x''=0,y''=-12} 　　　　　　else {y'' = -10, x''=0} 　　　　} 　　} }, Ball =()[x, y]{ 　　x = 1, x' = 6, 　　y = 40, y' = 0, 　　always { 　　　　strong{ 　　　　　　if (y = 30 && 0<x && x<10) 　　　　　　|| (y = 20 && 0<x && x<20) 　　　　　　|| (y = 10 && 0<x && x<30) 　　　　　　|| (y = 0 && x>=30) 　　　　　　|| (30<x && x<60 && y=30) 　　　　　　　　then {x''=0, y' = -0.9 * prev(y')}, 　　　　　　if (x=10 && 20<y && y<30) 　　　　　　|| (x=20 && 10<y && y<20) 　　　　　　|| (x=30 && 0<y && y<10) 　　　　　　　　then {x' = -0.9 * prev(x'), y'' = -10}, 　　　　　　if (x = 0 && y>=0) 　　　　　　|| (x=70 && y>=0) then {x' = -prev(x'), y' = 20} 　　　　} 　　　　medium { 　　　　　　if (20<x && x<30 && 25<y && y<50) then {y'' = -3, x''=-1}, 　　　　　　if (30<x && x<40 && 0<y && y<20) then {y'' = -3, x''=1}, 　　　　　　if (40<x && x<60 && y>30) then {x''=0,y''=-12} 　　　　weak {y'' = -10, x''=0} 　　} }, 現状のHCCコードと理想とする階層化後のコードの概観図です。 現状のHCCコード 階層化後のコード

8 制約階層の有効性・評価項目 定義したSyntax,Semanticsに基づき、現処理系で以下４点について有効性を確かめる実験をした
記述の多様化 構文の書き換えができる利点を説明 フールプルーフ設計 ユーザのミスを吸収することで、思考量を減らす 可読性 コード量・jump文の減少による可読性の向上 デバグへの利用 制約のチェック量の減少によるデバグ効率向上 定義したSyntax,Semanticsに基づき、現処理系で以下４点について有効性を確かめる実験をしました。 記述の多様化、フールプルーフ設計、可読性、デバグへの利用の4点です。

9 記述の多様化 書き換え可能な構文・モデル if elseの構造 状態遷移モデル タグのためのunless
記述の多様化では書き換え可能な構文・モデルを示しました。 上側が現状のHCCコードで、下側が階層化導入後のコードです。

10 記述の多様化による利点 ・左図の構造の多用を回避できる （左図の構造は状態遷移モデルやタグを 使用したクラスに分割する変換は可能）
　　　　　　　並行プログラミング ある時間に矛盾する制約が存在してはいけない ・左図の構造の多用を回避できる （左図の構造は状態遷移モデルやタグを 　使用したクラスに分割する変換は可能） ・状態遷移モデルのような型を知らなくても 　記述可能になる ・記述しているモデルが状態遷移モデルと 　気づかない場合も記述可能になる if{ } else { } } } else { }else{ } スケルトンは辞める HCCが逐次ではなく並行プログラミングで、かつ各時間ごとに矛盾する制約が存在してはいけないため、左図のような構造になりがちです。 これだと可読性が落ち、コードを追加するにも条件を考える手間がかかります。 しかし、制約階層化による記述の多様化により左図構造の多用を回避できます。

11 フールプルーフ設計 現状 階層化後 現状 階層化後
制約の有無の観点からプログラミングを考えると，全時間において制約が無いという時間がなく，かつ矛盾する制約が２つ以上存在してはいけない 全時間において、 各変数に必ず制約が必要 矛盾する制約が無い 階層化後 選好制約のweakで代表されるデフォルトとなる制約の宣言によって，全時間において制約が無いという時間は存在しなくなる．さらに，同階層の制約の整合性が保てるなら矛盾する制約がいくら存在してもかまわないことになる． １変数１パラメータに対する時間ごとの制約の有無を表した図 現状では全時間において、各変数に必ず制約が必要で、かつ矛盾する制約が無いというのが処理系が正常動作する必要条件です。 階層化後ではデフォルトとなる制約の宣言によって，制約が無いという時間は存在しなくなります。さらに，同階層の制約の整合性が保てるなら矛盾する制約がいくら存在してもかまわないことになります。 制約1 制約1 制約2 制約2 制約3 制約3 制約4 制約4 t t 現状 階層化後 HCC処理系時間

12 実際のコーディング時の利点 HCC処理系特有の連続量宣言であるcont, lcontの削除 重力加速度などをユーザがデフォルトに設定
現状では毎ポイントフェーズごとの制約チェックする必要がある 最も弱いデフォルト制約とすると、階層化後ならユーザは意識せずコーディング可能 重力加速度などをユーザがデフォルトに設定 ユーザのミスによる、制約が存在しない時間が無くなる 優先度の高い制約を用いてコード追加 未読のコードに、矛盾なくコードを追加しやすい HCC処理系特有の連続量宣言であるcont, lcontの削除が可能となり、コーディングの際にどの変数にcontをつけなければならないかなど考える必要が無くなります。 重力加速度などをユーザがデフォルトに設定することで、ユーザのミスによる、制約が存在しない時間が無くなります。 優先度の高い制約を用いてコード追加することで、未読のコードに、矛盾なくコードを追加しやすいなどの利点があります。

13 階層化設計 （HCC処理系内部の制約ストアの入出力操作 による階層化アルゴリズム）
階層化設計の問題点（phaseごとに制約をチェックする．point phaseから値を引き継いで新たに始めることができないこと）を踏まえて、point phaseとinterval phaseを別々にエラーが発生するかみる． point phaseとinterval phaseの処理はほぼ同様なので１つのほうのアルゴリズムを示す． 他２つのアルゴリズムの問題点を考慮してHCC処理系の制約ストアの入出力操作を改変することよって階層化設計を行いました。 実行処理アルゴリズム

14 まとめと今後の課題 まとめ 記述の多様化・フールプルーフ設計・可読性の向上・デバグへの利用の４点について、有効性を示す実験を行った。
３通りのアルゴリズムに従い、階層化設計について各々実験を行った。その実験結果をもとに現状最良と思われる設計を考案した。 今後の課題 制約階層案を実装し，設計したアルゴリズムが実際に正しく挙動するかを証明すること 時間ごとに制約の強弱を切り替え可能とする制約階層を実現すること 階層宣言を使用できる場合が増加。より記述の多様性が増し、多くの制約に対し明示的に優先度が宣言できる。それに加え、コード量を激減できる。 まとめ 記述の多様化・フールプルーフ設計・可読性の向上・デバグへの利用の４点について、有効性を示す実験を行った。 特にフールプルーフ設計の点において，コーディングにおいて制約過多，制約不足といった状況の解消支援をする本研究の目的に適した検証が行えたと思われる ３通りのアルゴリズムに従い、階層化設計について各々実験を行った。その実験結果をもとに現状最良と思われる設計を考案した。 今後の課題 制約階層案を実装し，設計したアルゴリズムが実際に正しく挙動するかを証明すること 時間ごとに制約の切り替え可能とする制約階層を実現すること 階層宣言を使用できる場合が増加 設計の中の１つの項目である矛盾しあう２つの制約を見つけるというアルゴリズムはそれだけでもデバグに非常に有効である．

15 参考文献 細部博史:ユーザインタフェースのための線形等式・不等式制約解消系 コンピュータソフトウェア,Vol.19,No.6,pp.13-20,日本ソフトウェア科学会, Bjorn Carlson and Vineet Gupta：Hybrid cc with interval constraints,1997 Bjorn Carlson and Vineet Gupta：The hcc Programmer's Manual,1999 Alan Borning, Bjorn Feldman-Benson, Molly Wilson：Constraint Hierarchies,1992, OOPSLA '87 Proceedings, pages 48-60, October, Page 27 of 31

16 以降予備スライド 関連研究 関連研究全体 HCCの制御構文例 書き換えモデル（unless） 可読性・デバグに関する考察
cont,lcontの説明 cont,lcontを省略できる理由 比較子の説明 階層化設計１（書き換え規則アルゴリズム） 階層化設計２ （HCC処理系外部から操作による階層化アルゴリズム） 実装の問題点 可読性のためのコード書き換え

17 関連研究 従来の研究 Grifonにおける制約の階層化 本研究の新規性
従来の制約階層の研究としては，GUIにおいてユーザによる記述に多少の制約矛盾を含んでいたとしても最適解を導き出せるという研究が多い Grifonにおける制約の階層化 Grifonとは、論理的な概念や関係を表すようなアニメーションを柔軟に表現することを目的とした制約に基づくアニメーション作成システム。この研究では、Grifon における幾何制約とハイブリッド並行制約が矛盾し合う制約過多な状況でも適切な最適解を得られるようにするため、強さと呼ばれる制約の優先度を可能にする制約階層を実現している。 本研究の新規性 本研究はHCC言語の記法を制約階層に基づいて変換し明示的に階層構造を記述可能にすることで、ユーザ支援をする。 コードの記述を多様化し、フールプルーフ設計を施すことで、実用的かつ容易に記述できる ユーザの記述の誤りに対し、期待しない結果を返す誤りであるならば解を補正するのではなく 　エラーとし出力し，記述の誤りの原因を限定させる

18 関連研究まとめ Grifonにおける制約の階層化
Grifonとは、論理的な概念や関係を表すようなアニメーションを柔軟に表現することを目的とした制約に基づくアニメーション作成システムである。この研究では、Grifon における幾何制約とハイブリッド並行制約が矛盾し合う制約過多な状況でも適切な最適解を得られるようにするため、強さと呼ばれる制約の優先度を可能にする制約階層を実現している。 ユーザインタフェースのための線形等式・不等式制約解消系 ユーザインタフェースを応用対象とし、線形等式および不等式制約からなる制約階層を処理するための制約解消系を構築している。その制約解消の実現は，HiRise制約解消系における等式制約処理法に対して、新たに考案した不等式制約処理法を組み合わせることで行っている。そして実験により、この制約解消系が、制約が1,000個を超える状況でもUIを実現するのに十分に高速な制約解消ができることを示している。 可読性を重視したプログラムの生成に関する研究 プログラムを人間とコンピュータとの間のインターフェイス(双方向の意志伝達手段)と位置付け、その際に重要となってくることの一つとして、“可読性”という概念を取り上げている。そして、物理分野の数値シミュレーションコード(有限要素法解析)生成支援システムを作成して、プログラム生成支援システムが可読性を重視したプログラムを生成することによって、信頼性の高いプログラムを構築することを可能としている。 ハイブリッド並行制約プログラミングにおける制約エラー説明機能の設計と実装 この研究ではプログラム実行中に制約エラーが発生した場合、その原因の解明に有用とされる制約の遷移、詳細をユーザーに提供する制約エラー説明機能の設計と実装を行っている。

19 Hccの制御構文 hence A always A do A until ac when ac do A
if ac then A, if not(ac) then Bと等価 acがtrueであればAに簡約され、not(ac)がtrueであればBに簡約される。 注意すべきことは、acがtrueでないからといって、not(ac)がtrueになるとは限らないということである。 if ac then A else B not(ac)がtrueであればBに簡約される。 acが判定されない(unknown)であればBに簡約される。 Unless ac then B hence A 出現した最初のphaseだけ何もせず、以後全てのphaseでAを実行する。 always A 出現したpoint phaseも含め、全てのphaseでAを実行する。 このAgentは、出現したpoint phaseで、Aを実行する。 そして、acがtrueになったphaseで、Aの実行を停止する。 acがtrueになった最初のphaseでもAの実行がある点である。 do A until ac when ac do A acが初めてtrueになったときにAを実行する。

20 書き換えモデル（unless）

21 可読性・デバグ 可読性 タグの使用・コード量の減少は実現できる 可読性は必ずしも高くなったといえない デバグへの利用
デバグに関しては明示的に記述してある同階層間の制約のみをチェックするだけで良くなる。更に、設計の過程で矛盾する制約を見つける必要性があることが分かったので、矛盾する制約をユーザに提示できれば、ユーザは制約のチェックをする必要がなくなる。 できているモデルに対する追加にも有効

22 cont,lcont どちらも変数が連続的であることを宣言している ・cont(x) 直前のintervalフェーズの終わりでの変数xの値を
pointフェーズにコピーしてくる ・lcont(x) 直前のpointフェーズの変数xの値を intervalフェーズにコピーしてくる

23 cont,lcont省略の設計上の問題の無さ
連続変数x 離散変化を含む変数x x x 現状ならば、離散変化を 起こさせる制約と衝突する 2 1 1 現状でも問題なし t t

24 比較子 least-squares-better weighted-sum-better
制約の誤差の2乗の和を最小化(最小2乗法) 例：strong x = y, weak x = 0, weak y = 2 → 解 x = 1, y = 1 weighted-sum-better 制約の誤差の和を最小化 locally-predicate-better/locally-error-better (直観的には)任意の順に制約の誤差を最小化

25 考察：２階層までの階層化には利用可能である
階層化設計１ （書き換え規則アルゴリズム） ユーザに記述してもらう理想とする（制約の階層化を意識しない）ソースから、Hybrid CCで矛盾の生じないソースへ変換するプリコンパイラをつくる。右下図に載せている評価基準に従い、規則を保ちつつ書き換える処理系を作成する。 考察：２階層までの階層化には利用可能である ただし、拡張性に欠ける

26 階層化設計２ （HCC処理系外部から操作による階層化アルゴリズム）
正常にシミュレート時間が終わった場合はそのまま計算結果を返す。 エラー検出し停止した場合、エラーを検出したフェーズで，衝突した制約２つを特定し、弱い制約は削除しそのフェーズを実行する。そのフェーズを計算し終えたらファイルAから元のコードを作成し、続きから計算を始める。 上記を繰り返し、シミュレート時間終わりまで計算する。

27 実装の現問題点 タグの付け替え 評価の順番 衝突するストア内の制約の識別 例 requied x+y=3 weak x=0 weak y=2
ｙを導いた制約 R：x+y=3, W：x=0→W☆：y=3 dequeue(W:y=2)→エラーとするには？ 案１：R=0,W=3として新しいタグZ=1.5→エラーが返せない 案２：R∧W → W 評価の順番 W:x=0→W:y=2(→ W:x=0 and W:y=2) → R:x+y=3 → エラー W:x=0, W:y=2の２つとも削除すると値がでない 片方だけ優先させると，評価の順番によって値が変わる

28 可読性のためのコード書き換え