論文紹介： The Theory of Hybrid Automata

論文紹介：
The Theory of Hybrid Automata
2006/07/03
上田研究室 M1
西村光弘
1
Hybrid Automataの由来
• ハイブリッドシステムとは離散と連続の内容を両
方伴う動的システムである。エンベデッドコン
ピュータがユビキタスになるにつれて、ハイブリッ
ドシステムはsafety-criticalなアプリケーションに
ますます利用されるようになっている。（現在進
行形）
• Safety-criticalなアプリには厳しい信頼性が必
要！
• そこで、ハイブリッドオートマトンはハイブリッドシ
ステムのための正規モデルとして提案されてき 2
た
Syntax概要
• 典型的なハイブリッドシステムの例はアナログのプラントのデジタル
な制御である
– Control mode：controllerの離散状態はグラフの節点（vertices）によって
モデル化される
– Control switches：controllerの離散動学（dynamics）はグラフの枝（edge）
によってモデル化される
– Plantの連続状態はRn内の点（point）によってモデル化される
– Plantの連続動学は方程式のようなflow conditionsによってモデル化され
る
• Plantの振る舞いはcontroller stateに依存
– 各control modeでは一つのflow conditonを決定
– 各control switchではjump conditionで決められている通りに状態の離散
変化を引き起こしてもよい
• Controllerの振る舞いはplant stateに依存
– 各control modeではplant状態の不変量conditionを連続的に監視する
– 不変量conditionに違反があると、plant stateの連続変化がcontrol switch
を引き起こす
3
Definition1.1 : Syntax
• 変数
– 実数上の変数xの有限セット X={x1,…,xn}
– 微分を表すxと離散変化後の変数を表すx’のセットXとX’がある
• 制御グラフ
– 有限有向マルチグラフ(V,E)
» Vの節点：制御モード、Eの枝：制御スイッチ
• 制御モード（v∈V）に割り当てられる述語ラベルを付与さ
れた機能(init,inv,flow)
– 初期条件init(v)：Xからなる自由変数をもつ述語
– 不変量条件inv(v)：Xからなる自由変数をもつ述語
– フロー条件flow(v)：X∪Xからなる自由変数をもつ述語
• 制御スイッチ（e∈E）の枝に付与される機能(jump)
– ジャンプ条件jump(e)：XとX’からなる自由変数をもつ述語
• イベント
– イベントの有限セットΣ
– 制御スイッチにイベントを割り当てるのにE→ Σと書く
4
Syntaxの図例
– 温度の制御（サーモスタット）
• 連続量 x: 温度
• 制御モード On とOff
– Off: 温度は、x = -0.1xにしたがって下がる
– On: 温度は、x = 5-0.1xにしたがって上がる
• 初期状態：Off, x = 20
• ジャンプ条件：x<19
– 19度未満になれば、ヒータはオンになってよい（許可）
• 不変条件：x≧18
– 18度未満になったら、Ｏｆｆから出て行かなければならない（強制）
x = 20
init condition
flow condition
off
x = -0.1x
x ≧18
invariant condition
x ＞21
on
x = 5-0.1x
x ＜19
x ≦22
jump condition
5
Thermostat automaton
Definition1.2 : Safe Semantics
• 離散連続の合わさった動きは、完全に離散遷移
システムで抽象化されうる
• ラベルづけされた遷移システムSの定義
– 状態空間
» 状態の（できるかぎり無限の）セットQ
» Qの部分集合である初期状態のQ０
– 遷移関係
» ラベルのセットA
» ラベルセットの部分集合a∈Aで状態空間Q上でのbinary
a
relation （2項関係）を→と表す
a
» そして、q→q’を遷移とする
6
Labeled transition systems の続き
• 状態空間Qの部分集合Rをregion（領域）と
呼ぶ
• もし部分状態空間RとラベルAがあるなら
ばそれを用いて
– ラベルa変化後のR(region)を
a
» posta(R) = {q’ | ∃q ∈ R.q → q’}と表記する
– ラベルa変化前のR(region)を
a
» prea(R) = {q | ∃q’ ∈ R.q → q’}と表記する
7
２つのラベル付けされた遷移システム
• 両遷移システムは、遷移による離散jump
を表す
– Timed transition system(定期遷移システム)
• 各flowのソース、ターゲット、期間の情報だけを保持しつつ、
遷移による連続flowsを抽象化する
– Time-abstract transition system
• 他も抽象化して、flow期間も抽象化する
• ただ、保持はしない
8
Definition1.3 : Transition semantics of
Hybrid automata
•
•
•
•
Hybrid atutomaton：H
Labeled transition system：S
Timed transition system：StH
Time-abstract transition system： SaH
• 以下、 StHとSaHの定義が続く
9
Timed transition system：StH
• 下2項目を満たすQ, Q0 ⊆ V ×Rｎを定義する
– (v,x)∈Q ⇔閉じた（自由変数を含まない）述語inv(v)が真
– (v,x)∈Q0 ⇔init(v)∧inv(v)が真
• 集合QはハイブリッドオートマトンHの状態空間と呼ぶ
• Qの部分集合をH-regionsと呼ぶ
• ラベルA=イベントΣ∪R≧0
• 各イベントσ∈Σに対して
σ
– (v,x)→(v’,x’)⇔以下のような制御スイッチe∈Eが存在する
» eのソースはvで、eのターゲットはv’
» 自由変数を含まない述語jump(e)が真
» event(e)=σ
10
Timed transition system：StH続き
• 非負実数δ∈R≧０に対して
δ
– (v,x)→
(v’,x’)⇔v=v’∧微分可能な関数f:[0,δ]→Rｎ
» 上のｆは一回導関数ｆ：(0,δ)→Rｎをもつ
» そのときの関数fについてf(0)=x ∧ f(δ)=x’
» 全ての実数ε∈(0, δ)に対して
» inv(v) ∧ flow(v)が真
δ
– この関数fは遷移(v,x)→
(v’,x’)のwitnessと呼ばれ
る
11
Time-abstract transition system : SaH
• Q, Q0 関してはTimed transition systemと同じ
• いくつかのイベントτ∈Σに対して、
» ラベルB＝イベントΣ∨{τ}
• 各イベントσ∈ΣもTimed transition systemと同じ
τ
• (v,x)→ (v’,x’)⇔非負実数δ∈ R≧０存在する
δ
» (v,x)→ (v’,x’)
• Time-abstract transition system : SaHはTimed transition
system : StHのtime abstractionと呼ばれる
12
Live Semantics
• 時間の発散はliveness assumptionである
• Liveness assumptionだけを考えればよい
» 参照：理由：巻末[24],[33]の論文
• もし時間の発散を防ぐことができないならば、ハ
イブリッドオートマトンはnonzenoである
• Nonzenoとは単調な発散と比較して一貫している
仕様
• 実システムではnonzeno仕様だけならば実現しう
る
13
Difinition1.4
Live transition systems
• Labeled transition system : Sとその初期状態q0に
ついて考える
• Sのq0-rooted trajectory(軌道)は、有限または無
限のpair<ai,qi>i≧1の列である
ai
– ラベルai ∈A ∧ 状態qi ∈Q (i≧1の全てのiに対してqi-1 → qiとな
るようなqi)
• Sの初期状態をq0とすると、 <ai,qi>i≧1はSの
initialized trajectoryである。
• Live transition systemを(S, L)とすると、それは
labeled transition system：Sと、Sの無限の
initialized trajectoriesのセット：Lからなるペアー
14
Definition1.4
Live transition systems続き
• Sの有限のinitialized trajectoryが、Lのいくつか
のtrajectoryの前にあるモノであるならば、LはSに
とってmachine-closedである
• (S, L)がLive transition systemであり、かつ
<ai,qi>i≧1がSの有限initialized trajectoryである∨L
のtrajectoryである
↓
• 上の時、対応した連続のラベル<ai>i≧1は(S, L)の
traceと呼ばれる
15
Definition1.5 ： Trace semantics
of hybrid automata
• Timed transition systemの各遷移とR≧０での
期間を関連づけて考えていく
• イベントσ∈Σにおいて
σ
» q → q’にかかる時間は0
• 実数δ∈ R≧０において
δ
»q→
q’にかかる時間はδ
16
Definition1.5 ： Trace semantics
of hybrid automata続き
• δi (i≧1)の全ての和が発散するなら、Timed
transition system StHの無限軌道<ai,qi>i≧1も収束
しない（発散）
δ
» ここの各δはq → q’に対応する時間
• すべてのi≧1に対して、ai=bi ∨ ai,bi ∈∑であるよう
なStHの発散軌道<ai,qi>i≧1が存在するならば、
Time-abstract transition system SaHの無限軌道
<bi,qi>i≧1は収束しない（発散）
• StHの発散する初期軌道をLｔHとする
17
• SaHの発散する初期軌道をLaHとする
Definition1.5 ： Trace semantics
of hybrid automata続き
• SｔHに対してLｔHがmachine-closedである
⇔ SaHに対してLaHがmachine-closedである
↓
• Hybrid automaton Hはnonzenoである
• Live transition system(SｔH, LｔH)の各traceは
Hのtimed traceと呼ばれる
• Live transition system(SaH, LaH)の各traceは
Hのtime-abstract traceと呼ばれる
18
Compositon（合成）
• ２つのハイブリッドオートマトンH1とH2に対して、並
行合成（H1|| H2）のTimed semanticsとTimeabstract semanticsを定義する
• ２つのハイブリッドオートマトンは、共通のイベントによって相
互作用する
• a が共通のイベントなら、２つはaの遷移について同期しなけ
ればならない
• aがH1のみのイベントなら、 H2は０時間遷移で同期する
• 各実数δ> 0において、 H1とH2の時間遷移は同じδ時間で同期
しなければならない
19
Definition1.6 Product of
transition systems
• 2つのlabeled transition system S1とS2の整合性検査は、
S1からの遷移とS2からの遷移から成るpairsについての結
合則を満たす部分的関数×である
• 整合性検査についてのproduct S1×S2は、以下をもった
Labeled transition systemである
– 状態空間Q1×Q2
– 初期状態のセットQ10×Q20
– ラベルのセットrange(×)
– 遷移関係：各ラベルa∈range(×)について、
a
(q1,q2)→(q1’,q2’)
a1
a２
⇔二つの遷移q1→q1’とq2→q2’に×を適用した結果がaであるような
ラベルa1∈A1とラベルa2∈A2が存在すること
20
Definition1.7 Composition of
hybrid automata
• 2つのhybrid automata H１とH２について考える
•
a2
t
H1の遷移q1→q1’とS H2の遷移q2→q2’は、次の３つ
St
a1
の場合の一つが真なら無矛盾である
– a1=a2であり、遷移に適用された整合性検査×=がa1を生成する
– a1∈∑1 ∑2∧a2=0であり、整合性検査×=がa1を生成する
– a2∈∑2 ∑1∧a1=0であり、整合性検査×=がa2を生成する
• Timed transition system StH1 || H2は整合性検査×=について
のproduct StH1 × StH2であると定義される
• Time-abstract transition system SaH1 || H2はStH1 || H2の
21
time abstractionであると定義される
例1.2 Railroad gate control
– 列車のオートマトン
• 踏み切りのある環状線路上の
列車の制御をモデル化
• 列車の制御（右図）
– 変数ｘは踏み切りからの列車
の距離
– 線路の長さは2000－5000メー
トル
– 最初は４０－５０ｍ/秒で接近
(Far)、1000メートル以下にな
るとスピードを３０メートル/秒
まで落として良い（Near）
– 踏切をこえて（Past）１００メート
ルを過ぎると、Ｆａｒへ。ｘは再
初期化される
x=-100 ∧ 1900≦x’≦4900
x=0 ∧ x’=x
Train automaton
22
例1.2 Controller automaton
– 踏み切りの制御オートマトン
• uは定数
– 反応の遅延時間
• ｚはクロック
– 経過時間を計る
• approach イベント→u秒以内に
踏み切りを下げる
• exit イベント→u秒以内に踏切
を上げる
？
23
例1.2 Gate automaton
– 踏み切り
• 変数yは遮断機の
バーの角度
• 初期状態はopen
（y=90）
• lower event→9度/秒で
しまる.
• raise event→9度/秒で
あがる
24
On the Trace languages of Hybrid
Automata
• ハイブリッドオートマトンのtraceについてのどの
必要条件が検証されうるか、また検証され得な
いかを確認していく
• 検証
– 安全性必要条件の検証には到達可能性問題が重要
– Liveness必要条件の検証には空集合問題が重要
– 定時間trace包摂問題については、定時間の詳細に対
して(against)hybrid automatonのtraceを比較する
– Time-abstract trace包摂問題については、time-abstract
の詳細に対して、hybrid automatonのtraceを比較する
25
Definition2.1
Reachability、emptiness、trace inclusion
• ハイブリッドオートマトンのクラスHの到達可能性
問題
• HからのハイブリッドオートマトンをH
• Hの制御モデルをv として
– 型(v, x)の状態を通るStH（もしくはSaH）の初期軌道が
存在するかどうか
• HのEmptiness問題
• HからのハイブリッドオートマトンをHとして
– StH （もしくはSaH ）の発散する初期軌道が存在するか
どうか
26
Definition2.1 続き
Reachability、emptiness、trace inclusion
• クラスHの有限定時trace含有問題
• Hからの2つのハイブリッドオートマトンをH1,H2とし
て
– H1の有限定時traceの全てが、H2の定時trace
になっているかどうか
• Hの有限time-abstract trace含有問題
• 上と同じ前提で
– H1の有限time-abstract
traceの全てが、H2の
time-abstract traceになっているかどうか
27
2.2 Rectangular Automata
• Flow conditionが制御モードに独立しており、変数がペア
で独立しているならば、ハイブリッドオートマトンは
rectangularである
• Rectangular automatonの各制御モードでは、各変数の一
回微分係数は可能な値の幅で、その値の幅は制御ス
イッチでは不変
• Rectangular automatonの各制御スイッチで、各変数の値
は、不変のままであるか、もしくは与えられた可能性幅内
の新しい値に非決定的に変えられる
• 変数の振る舞いは分離されている
– なぜなら、１つの変数についての可能な値の幅と微分値は、他
28
の変数の値と微分値に依存できないから
Definition2.2
Rectangular automata
• n次元のrectangle I=Π1＜i＜nIiは実線のn区間
Ii⊆Rからのproduct生産物である
– 各区間は有理または無限の終点である
• もし各区間Ii(1<i<n)が単体であるなら
rectangle Iは一つずつ起こる
29
Definition2.2 続き
Rectangular automata
• もし、以下の３つの制限に適合するならハイブリッドオー
トマトンはrectangular automatonである
– Hの変数のセットをX={x1,…,xn}とする
• Hの各制御モードvとして、init(v)が束縛されたn次元rectangle
Iinit(v)のための型X∈Iinit(v)をもつ∧inv(v)が束縛されたn次元
rectangle Iinv(v)のための型X∈Iinv(v)を持つ
• Hの各制御モードvとして、flow condition inv(v)が型X∈Iflowを
もつような、束縛されたn次元rectangle Iflowが存在すること
• Hの各制御スイッチeにおいて、２つのn次元rectangles Ipre(e)と
Ipost(e)のために、変数のセットY⊆Xとして、 jump(v)は
X∈Ipre(e)∧Y’ = Y ∧X’∈Ipost(e)という型をもつ
– 制御スイッチeはXYの変数を再初期化する
– 変数xi（1<i<n）がeによって再初期化されるなら、区間 Iipost(e)は30
単体でなければならない
Definition2.3 Multirectangular
and triangular automaton
• 定義2.2の３つの制限に適合する（次のことは除いて）
• Hの異なる制御モードvとv’が、異なるflow rectangles
Iflow(v)とIflow(v’)をもってよい
↓
• 上の時、ハイブリッドオートマトンHはMultirectangular
automatonである
• xi≦xj(1<i,j<n)の不等式で定義されるRnの半空間の数を
もつ、n次元rectangleの相互作用をn次元triangleと呼ぶ
• 全てのrectangleがtriangleになってもよいことを除いて、定
義2.2の制限が適合するならば、その時のHはtriangle
automatonである
31
図例
train automaton
controller automaton
gate automaton
32
例2.1
• Train automatonは初期化された1次元multirectangular
automantonである
– 同じ定時traceを用いると2次元rectangular automaton
に転換できる
• Controller automatonは、clock zと定数uをもつ2次元
triangular automatonである
– 定数uの値がわかっていたら、controllerは1次元定時
オートマトンでモデル化できる
• Gate automatonは1次元multisingular automatonである
– 矢印の方向が両方向のものがなかったら、gateはsingular
automatonでモデル化できる
33
検証結果
• 定理2.1[time-abstract trace]
– 全てのrectangular automaton Hに対して、Hの有限
time-abstract traceのセットはregular
– Hの無限time-abstract traceのセットはω-regular
• 証明
• 結果2.1[Time-abstract trace inclusion]
– Rectangular automatonのTime-abstract trace含有問題
はEXPSPACEによって決定される
34
定理2.1[time-abstract trace]
の証明
• n次元rectangular automatonをTTとして、2n次元singular
automaton H’を作る
– HとH’は同じ定時トレースをもつような↑
• Hの各変数xiをH’の変数xilと変数xiuで置き換える
– xilはxiのできる限り最小の値の幅をもつ
– xiuはH’のできる限り最大の値の幅を持つ
• もしxiがflow区間[l,u]をもつなら、xilはflow区間[l,l]をもち、
xiuはflow区間[u,u]をもつ
• 全ての定時オートマトンH’に対して、トレースが正確にH’
のtime-abstract raceであるBuchi automatonを構成できる
ことが示されている
• これらの解釈は、singular automatonで一般化できる
35
定理2.2, 2.3
• 定理2.2 到達可能性
– Multisingular automataとtraiangular automataの到達可
能性問題は非決定的である
• 証明
– 2-counter machines での停止問題からのリダクション
• 定理2.3 定時トレース含有
– 定時automataの有限定時トレース含有問題は非決定
的である
36
3 On the State Space
of Hybrid Automata
• ハイブリッドオートマトンの状態空間は無限であ
るので、数え上げた状態によって探索することは
できない
• 無限領域内の有限な記号的代表を計算すること
によってハイブリッドオートマトンの状態空間を分
析する
• 例：
– xを実数変数として、実数の無限セットの有限な記号
的代表として1≦x≦5を分析する
37
遷移システムの記号分析
• 定義3.1 遷移システムの理論
– 状態空間Qのラベル付遷移システムSについ
て考える
– Sにおける理論Tは、Q内の状態による真値が
割り当てられた属性のセットである
– Tの属性をpとして、pを満たすQ内の状態セッ
トを[[p]]とする、つまり[[p]]⊆Q
– q=Φr⇔qとrがΦでの同属性を満たす
» Sの全ての状態qとrに対して
38
遷移システムの理論続き
• もし、Tの属性pに対して、[[p]]が空であるかどう
かが決定されるならば、理論Tは決定可能である
• Tの全ての属性をp1とp2として、
– 領域[[p1]]∨[[p2]]と定義されたTの属性Or(p1,p2)
– 領域Q/[[p1]]と定義される属性Not(p1)
– 上２つが構成できる理論Tは、boolean oprations下で
効率的に閉じられている
39
遷移システムの理論続き
• Tの各属性をp、Sの各ラベルをaとして、
– 領域posta([[p]])と定義されたTの属性Post(p,a)
– 領域prea([[p]])と定義される属性Pre(p,a)
– 上２つが構成できる理論Tは、transitions下で
効率的に閉じられている
• 理論Tはこの３つが成り立っていたら記号
分析を許可される
40
Definition3.2
Similarity,bisimilarity,trace equivalence
• 状態空間Qのラベル付遷移システムSにつ
いて考える
– Qについての同値関係をで表す
• Sの –simulation は、Qについてのbinary
関係
– q rはq
rであり、かつSの各ラベルaに対して
a
もしq→q’である時に、状態r’が存在するような
Q
a
• そのrはr→r’∧q’ r’である
41
Definition3.2続き
Similarity,bisimilarity,trace equivalence
• 対称の –simulationは –bisimilarityと呼
ばれる
• Sの2つの状態qとrが –similarityであると
は、
– q r∧r qであるような –simulation が存在す
ること
• qとrが –bisimilarityであるとは、
– q rであるような -bisimulation が存在するこ
と
42
Definition3.2続き
Similarity,bisimilarity,trace equivalence
• S[Q0:=q]∧S[Q0:=r]であるラベル付遷移シ
ステムが同じ有限トレースをもつならば、q
とrはtrace equivalent（トーレス同等）である
• もし、TがSのための理論、ΦがTからの属
性のセットであるならば、
– Sの Φ-(bi)similarity関係は
Φ-(bi)similarityと呼ばれる
43
Definition3.3 有限同値性
• 有限なたくさんの –equivalenceクラスが存
在するならば、同値関係はfinitaryとよば
れる
44
• 無限状態遷移システムSの有限bisimilarityもしくは
similarityの関係が計算されうるなら、Sのたくさんの検証
問題は有限状態問題にリダクションされる
• 検証作業がμ-calculusであると言われるならば、有限へ
のリダクションを計算せずに直接、無限状態空間を計算
してもよい
• μ-calculusは領域の単調演算子を定義し、この演算子の
繰り返し作業はSの記号的分析を許された理論で行われ
る
• 状態空間の適合した有限のリダクションが存在するなら
ば、その繰り返しは終わることが保証されている
45
Definition3.4 The μ-calculus
• 状態空間Qのラベル付遷移システムS、Sの理論Tを考え
る
• (S,T)に基づくμ-calculusの公式は、Tの属性p、Sのラベル
a、領域変数Rなどの文法から生成される
φ::=p|φ1∨φ2|￢φ|∃aφ|μR.φ|R
• もし、領域変数の各occurrence(発生？)はμ-quantifier（量
記号）によって束縛（有界？）であり、negations(負？虚
数？)の偶数によって量記号（数量子）と分離されている
なら、 (S,T)に基づくμ-calculusの公式はlegal（適法）であ
る
46
Definition3.4
The μ-calculus続き
• 各領域変数に割り当てられたmapをFとし
て、 (S,T)に基づくμ-calculusのlegal公式の全て
のsub公式は、領域[[φ]]F⊆Qを定義する
–
–
–
–
–
–
[[p]]F=[[p]]
[[φ1∨φ2]]F=[[φ1]]F∪[[φ2]]F
[[￢φ]]F=Q/[φ]]F
[[∃aφ]]F=prea([[φ]]F)
[[φ]]F=∩{Q’⊆Q|Q’=[[φ]]F[R:=Q’]}
[[R]]F=F(R)
47
Definition3.4
The μ-calculus続き
• 連結語∃ の出現が全てnegationsの偶数
内であるならば、
– 公式φはexistential(実存的)である
• 連結語∃ の出現が全てnegationsの奇数
内であるならば、
– 公式φはuniversal(全称的)である
48
3.2 Linear Hybrid Automata
• 実数の理論で記号的に分析されたhybrid
automataはlinearと呼ばれる
• Definition 3.5[Linear hybrid automata]
– x1,…,xmを実数変数、k0,…,kmを整数定数とし
て、線形項はk0+k1x1+・・・+kmxmという形で表
現される
– t1とt2が線形項ならば、t1≦t2は線形不等式で
ある
49
3.2 Linear Hybrid Automata続き
• 以下の２つの制約が適合するなら、ハイブ
リッドオートマトンTTが線形である
– Hのinitial,invariant,flow,jump conditionsが線
形不等式のboolean combinationsである
– XをTTの変数のセットとする時に、TTのflow
conditionsがXだけからなる自由変数を含む
50
Definition3.6
Theories of hybrid automata
• 変数のセットXと制御モードのセットVを用
いてハイブリッドオートマトンTTを考える
• TT-predicateは、自由変数がVからのブー
リアン値の変数とXからの実数値変数であ
るという属性である
• 閉じた属性p[v,V/{v},X:=true,false,x]がtrue
であるなら、TTの状態(v,x)はTT-predicate
pを満たす
51
Definition3.6続き
Theories of hybrid automata
• 次の場合であるならば、TT-predicate pは線形で
ある
– pがVからのブーリアン値変数のboolean combination
– pがXからの実数値変数での線形不等式のboolean
combination
• pの各線形不等式が、変数ｘ定数ｋとしてx≦kもし
くはx≧kの形で記述される場合
– TT-predicate pはrectangular TT-precicateである
• Rectangular μ-calculusのTT公式は(SaH,T)-based
μ-calculusであり
52
定理3.1 線形ハイブリッドオート
マトンの記号的分析
• 定理：線形ハイブリッドオートマトンをHとして、線形Hpredicateのセットはtime-abstract 遷移システムSaHの記号
的分析を許される
• 証明：線形TT-predicatesは、実数と和と比較演算子と整数
定数をもった一階理論（R,+,≦,0,1）の自由数量子公式で
ある
• 線形ハイブリッドオートマトンの各時間遷移は、有限の連
続直線に分解できるwitness（証拠）を持っている
• 上記の時、実数上の定量化を用いて、PostとPre演算子
は一階理論で表現されうる
• この証明の結論として一階理論は数量子除去を認める
53
3.3 Bisimilarity and Similarity
Relations
•
•
•
•
•
•
•
•
Definition3.7[timed and time-abstract (bi)similarity]
Theorem 3.2[time-abstract bisimilarity of singular automata]
Proof
Corollary3.1[symbolic μ-calculus model checking for singular
automata]
Teorem3.3[Time-abstract similarity of 2D rectangular automata]
Proof
Corollary3.2[symbolic μ-calculus model checking for 2D rectangular
automata]
Theorem3.4[time-abstract similarity of 3D rectangular automata]
54
3.4 Computation Tree Logics
• Timedとtime-abstract 遷移システムの構造について研究してきたが、
これらの遷移システムはハイブリッドオートマトンの振る舞いについ
ての断定を証明するために、直接的には役に立たないかもしれない
– なぜなら、StTTとSaTTの各軌跡は、ある離散点でTTの区分的に連続な軌跡
だけをサンプルするから
• SaHの各時間遷移は、 SaTTの軌跡のみを見ることによって、訪れた中
間の状態についての全ての情報を抽象化するので、TTの一致する
区分的に連続な軌跡がどの状態もしくは領域を訪れたかをチェック
するのが不可能になる
• この問題を解決するために、各時間遷移が領域にラベル付けされる
といったobservational遷移システムを定義する
55
3.4 Computation Tree Logics続き
• 時間遷移tは領域Rにラベル付けされる
⇔全ての中間状態とtのtargetの状態がRに存在す
る
• Observational遷移システムは、ハイブリッドオート
マトンの連続した観察（監視）からの結果である
– 領域のセットをRとして、連続した軌跡の断片がRから
の領域のどれかに入っているかどうかを監視する
56
Definition3.8
piecewise-continuous semantics of
hybrid automata
• ハイブリッドオートマトンをH、Hの領域のセットR、
TTのR-observational遷移システムSRH
–
–
–
–
Q、Q0はdefinition1.3と同じ
C=∑∪R
各イベントσ∈∑もdefinition1.3と同じ
各領域R∈Rとして、
R
• (v,x)→（v’,x’）
⇔非負実数δ∈R≧0が存在する
δ
∧全ての実数ε∈(0,δ, (v,f(ε))に対して、遷移(v,x)→(v’,x’)のため
のwitness fが存在する
R
– 実数δは遷移(v,x)→(v’,x’)の可能な期間（時間）
57
Definition3.9
computation tree logics
• 状態空間Qの線形ハイブリッドオートマトン
をTT
• 線形CTLのTT-formulasは次の文法から生
成される
φ:=p | φ1∨φ2 |￢φ|φ1∃μφ2|∃□φ
• 線形TT-predicates pに対して、線形CTLの
全てのTT-formulaはTT-region[[φ]]⊆Qを定
義する
58
Definition3.9続き
computation tree logics
– [[φ1∨φ2]]=[[φ1]]∪[[φ2]]
– [[￢φ]]=Q/[φ]]
– q∈[[φ1∃μφ2]]
[[φ ∨φ ]]
⇔observational遷移システムSH
は[[φ2]]の
状態を訪れるq-rootedの軌跡を持つ
– q∈[[∃□φ]]
[[φ]]
⇔observational遷移システムSH は収束しない
q-rooted軌跡をもつ
1
2
59
Definition3.9続き
computation tree logics
• φ内で出現する全ての属性がrectangular Hpredicatesであるなら、その時
– 線形CTLのTT-formulaはrectangular CTLのTTformulaである
• φ内の∃μ連結語の出現と∃□連結語がnegations
の偶数範囲内に存在するなら、
– Rectangular CTLのH-formula φはrectangular∃CTLの
TT-fomulaである
• 上で偶数を奇数に変えた条件が成立するなら、
– Rectangular CTLのH-formula φはrectangular∀CTLの
TT-fomulaである
60
Definition3.10 Model checking
• Hybrid automataのクラスHと木論理計算L
に対してのmodel-checking問題は、Hから
のハイブリッドオートマトンをH、LからのHformulaをφとして、[[φ]]がHの全ての初期
状態を含むかどうかを調べる
61
例3.1 Railroad gate control
• Railroad, gate controlのためのsafety必要条件
• 電車がgateの１０メートル以内にあるときは、gate
は完全に閉められていること
• この必要条件はrectangular ∀CTLの公式
(Far∧Idle∧Open)→∀□(-10≦x≦10→Closed)で表される
• HYTECHは完全自動的に、このCTLをu次元で
の投影が5u<49である線形属性に単純化する
• そうすると、制御の反応遅延時間uが9,8秒以下
ならsafety必要条件は適合する
62
記号集１
•
•
•
•
•
•
•
•
•
•
•
•
•
微分を表すxと離散変化後の変数を
表すx’
制御モード（v∈V）
制御スイッチ（e∈E）
イベントの有限セットΣ
ラベル付遷移システムS
状態のセットQ(q∈Q)
Qの部分集合である初期状態をQ０
•
•
•
•
•
•
•
遷移関係でのラベルa∈(A=イベント
Σ∪R≧0)
イベントτ∈Σに対して、ラベルB＝イベ
ントΣ∨{τ}
状態空間Qの部分集合R(region)
δは非負実数
n次元のrectangle I=Π1＜i＜nIi
経過時間zと定数u
•
•
•
•
有限有向マルチグラフ(V,E)
Hybrid atutomaton：H
Labeled transition system：S
Timed transition system：StH
Time-abstract transition system： SaH
Live transition system：(S, L)
LはSの無限のinitialized trajectoriesのセッ
ト
StHの発散する初期軌道をLｔHとする
SaHの発散する初期軌道をLaHとする
二つのハイブリッドオートマトン合成をH1||
H2で表す
labeled transition system S1とS2の整合性検
査は、 S1からの遷移とS2からの遷移から成
るpairsについての結合則を満たす部分的
関数を×
63
記号集２
•
•
•
遷移システムSの理論T
Tの述語をpとして、pを満たすQ内の状態
セットを[[p]]とする
q=Φr⇔qとrがΦでの同じ述語を満たす
64

Download Report