ハイブリッド並行制約プログラミングにおける制約エラー説明機能の実装

ハイブリッド並行制約プログラミングにおける
制約エラー説明機能の設計と実装
2006年度卒業論文
1G03R090-5 笹嶋唯
指導：上田和紀教授
ハイブリッド並行制約プログラミング


ハイブリッド並行制約プログラミング（hybrid cc）は時間軸に沿った連続的・離
散的変化からなるハイブリッドシステムを表現できる宣言型言語
実行は2つのフェーズの繰り返し



連続変化 interval phase
離散変化 point phase
プログラムは既存実装であるhybrid ccインタプリタ（hybrid cc処理系）で解釈さ
れシミュレーション結果を得る
可視化ツール
Hybrid ccプログラム
y=20, y‘=0,
x=0, x'=3,
always{
cont(y),cont(x),
x''=0,
if(y>0) then y‘’=-9.8,
if(y=0) then y‘=0.7*prev(y’)},
sample(x,y)
出力
Hybrid cc
インタプリタ
y::
0.000000e+00
1.000000e+01 1.000000e+01
1.000000e-02
9.999510e+00 9.999510e+00
2.000000e-02
9.998040e+00 9.998040e+00
・・・・
研究の目的と背景



制約はpoint phaseで制約ストアに追加(Tell)される。制約ス
トアに矛盾があれば制約エラーとなる。
問題点
 制約エラーが生じても、デバッグに有効な情報を返さない
制約エラー発生時に処理系がプログラム実行中の制約情報
を教えてくれるとデバッグが行いやすくなる
ビリヤードモデル

Ballクラス
Ball = (initpx, initpy, initvx, initvy)
[px, py, vx, vy, ChangeX, ChangeY] {
px = initpx, py = initpy,
vx = initvx, vy = initvy,
・・・・・・
},
Collisions()
Collisions = (){
always forall Ball(A) do forall Ball(B) do {
If(当たり判定) then {
衝突後のBallの挙動計算
}
},

Hybrid ccでモデリング

摩擦は無視で完全弾性衝突とする

球同士の衝突のみを表現

Ballをクラス、当たり判定、衝突後の挙動
をCollisions()で表現
問題点

3つの球が同時衝突するとエラーが発生し
計算が中断されてしまう
制約エラー


Bとの衝突に
よって速度Vab
が生じる

B
A
A
Cとの衝突に
よって速度Vac
が生じる
C
制約の矛盾を原因とするエラー
制約エラーで即時計算が中断される
例：ビリヤードモデルにおける3物体衝突
AとBの衝突によって生じる速度Vab
A.V = Vab,
AとCの衝突によって生じる速度Vac
A.V = Vac,
A.V = Vab, A.V = Vac
制約の矛盾が発生
制約エラー説明機能設計
Hybrid ccプログラム
構文解析
point phase処理・計算
処理データ
制約、エージェント
制約トレースへの記録
interval phase処理・計算
制約エラー発生
制約エラー処理
制約トレースの追加
サンプル値出力
制約トレースの出力
上書きされた変数の出力
制約ストア表示
制約エラー説明機能実装





hybrid cc処理系を改良 - C++で実装
制約エラー説明モードの追加
制約トレースの表示
 あるpoint phaseにおいて今まで追加された制約と記述を記録し管理
制約ストア表示
 制約エラー検出時の制約ストアと制約の矛盾を起こした制約の表示
上書きのあった変数の表示
 変数の上書きが起こると制約エラーが起こる。エラーの原因となった
変数名と値の出力
以前の処理系出力例：ビリヤードモデル
制約エラー検出時のpoint phase処理
Point phase開始
Doing Point computation...
Unexpected failure!
Last statement executed was:
c = (B.py+(-(A.py)))*1/(B.px+(-(A.px)))
最後に実行された記述
（今までのサンプル値の出力）
・・・・・
Constraint error!
• 記述だけでは、どのオブジェクトでエラーが発生したのかがわからない
• 制約エラーの原因である制約情報が一切ない
出力例：ビリヤードモデル
the following variable might be set incorrectly .....
varibale name:
B1.vy
latest variable value:
latest access value:
21.650635 ]
ConstrTrace List---------------
上書きされた変数名
[ 21.650635 , 21.650635 ]
[ -21.650635 , -
代入しようとした計算値
制約トレース表示開始
Agent (15) --ix = (prev(B.vx)+c*prev(B.vy))*1/(1.00000+c^2.00000)
Tell Constraint --ix$6+(((prev(B1.vx)+c$1*prev(B1.vy))*1/(1.00000+c$1^
2.00000))) = 0.00000
Agent (14) ---B.vx = prev(B.vx)+(-ix)
Tell Constraint ---B1.vx+(-prev(B1.vx))+ix$6 = 0.00000
・・・・・・・・
既に代入されている計算値
制約を制約ストアに
加えた記述
加えられた制約
出力例：ビリヤードモデル
---- last constraint store state --->>latest tell-constraint
最後に追加された制約
---- c$1+(-((B1.py+(-A1.py))*1/(B1.px+(-A1.px)))) = 0.00000
>>constraint list
制約ストアの最終状態。制約をリスト表示
0> ix$6+(((prev(B1.vx)+c$1*prev(B1.vy))*1/(1.00000+c$1^2.00000)))
= 0.00000
1> B1.vx+(-prev(B1.vx))+ix$6 = 0.00000
2> B1.vy+(-prev(B1.vy))+c$1*ix$6 = 0.00000
3> c$0+(-((B1.py+(-A2.py))*1/(B1.px+(-A2
・・・・・・
プログラムの修正
ビリヤードモデルの場合、ユーザーは以下の手順で修
正する
上書きされた変数を見る

1.

B1.vyが値の衝突を起こしている

B1.vy = 21.56 ? B1.vy = -21.56?
上書きされた変数を縛る制約を制約トレースから探す
2.


B1.vy+c$0*ix$4+(-prev(B1.vy)) = 0.00000
B1.vy+(-prev(B1.vy))+c$1*ix$6 = 0.00000
上の制約をTellしたエージェントに問題がある
3.

B.vy = prev(B.vy)+(-(c*ix))
解決案



矛盾の原因となる制約をTellしたエージェントを修正する
上書きされた変数の初期値を修正する－微小値εずらす
まとめと今後の課題

まとめ


制約に関する情報が増えたため、制約エラーを起こすプログラム
のデバッグは以前に比べて容易に行うことができるようになった
問題のある記述、制約の検出機能の改良

ユーザーに依存するのではなく、処理系が自動的に問題のある
記述、制約の特定を目標とする
y=20, y‘=0,
x=0, x'=3,
always{
cont(y),cont(x),
//連続量
x''=0,
if(y>0) then y‘’=-9.8, //重力による自由落下
if(y=0) then y‘=-0.7*prev(y’) //地面に衝突
},
sample(x,y)
//Ｘ、Ｙのサンプル値を取得
A
B

Download Report