メインコンテンツまでスキップ

付録H. 確率モデル拡張(stochastic 0.1)

本付録は,CADLの確率モデル拡張を規定する。この拡張は, 付録A.2の生成規則 sos_body に 1つのキー model: を追加する。これにより,ファイルに,制度パラメータα,β,λが現れる 明示的な確率モデルを書き,そのモデルの性質を述べ,パラメータ空間のどの領域でどのモードが 最良かというモードマップの問いを書くことができる。

コア言語は,このブロックを必須としない。本拡張を実装していないCADL準拠の処理系は, 新しいキーを理由にファイルを拒否してはならない。新しいキーを構文上は受理し, 情報レベルの診断を出すことが望ましい。本拡張のバージョンは,コア言語とは独立に管理する。 拡張の名前は stochastic であり,本付録はバージョン 0.1 を記述する。本拡張を用いるファイルは, extensions: の下の項目 - stochastic: 0.1 でそのことを宣言しなければならない (宣言せずに用いた場合に処理系がどう扱うかはH.15で述べる)。

本拡張は,コア言語や他の拡張のどの構成要素の意味も変えない。特に, 付録A.8の verification: ブロックは 変わらない。

H.1 動機と範囲​

5.4.2節は,モードマップを制度パラメータを用いて構築すると述べるが, コア言語にはパラメータを振る舞いに結び付けるものがなく,cadl regime-map コマンドが報告するのは モード名のグラフであり,パラメータ空間のどの領域でどのモードが最良かは示さない。9.1節のRD-1.3は, この結び付きを求めている。パラメトリックなマルコフモデルのパラメータ合成は,パラメータ空間を, 性質を満たすことが認証された領域と破ることが認証された領域に分割する [Junges+, FMSD 2024]。Stormはこれを実装しており, PRISMモデリング言語を読む [Hensel+, STTT 2022] [Kwiatkowska+, CAV 2011]。しかし,CADLにはそのようなツールに 渡すモデルがない。stochastic 0.1は,そのモデルを書くための最小限の手段を,次の方針で定める。

  • モデルは記述者が書く。 状態変数と,パラメータを参照する確率コマンドを書く。契約,プロトコル, 規範からは何も導出しない。本拡張が定めるのは,契約とモデルの対応付けだけである。パラメータを契約の alpha,beta, lambda に束縛でき,それによって契約とモデルが同じ数を用いる。
  • 意味論は変換である。 モデルとモードは,パラメトリックな離散時間マルコフ連鎖を定める(H.7)。 処理系はこれを,固定の規則によってPRISMモデリング言語へエクスポートする(H.11)。
  • モードマップの問いは定義するが,解かない。 H.9は,問い合わせが何を問い,何が正しい答えであるかを 定義する。それをどう計算するかは定義しない。リファレンス実装の方法はH.14に述べる。

バージョン0.1の範囲。

  • 時間は離散である。1ステップは1回の遷移であり,duration_lit とは関係しない。連続時間のモデルや 時間付きのモデルは扱わない。状態は有限である。
  • どのモードモデルもマルコフ連鎖である。非決定性はなく(S-9),コマンドの同期もない。
  • モード間の切替(A.7)はモデルの一部ではない。各モードは,それぞれ独立したモデルとして解析する。
  • 単調性の主張(「αを上げても成功確率は下がらない」)は見送る。パラメトリックなマルコフ連鎖には 単調性検査が存在するが [Spel+, ATVA 2019],その研究が扱うのは到達確率である。
  • 本付録にはゲーム意味論はない。モデルをアクター間のゲームとして読み,遵守が均衡であるかを問うこと (9.7節のRD-7.1とRD-7.2。合理的検証 [Gutierrez+, AI 2020],並行確率ゲームの相関均衡 [Kwiatkowska+, TACAS 2022])は,戦略モデル拡張 (付録I,games 0.1)が扱う。そのために 次のものを予約し,別の意味では用いない。キー owner:(変数またはコマンドの)と sync: (コマンドの), model: の players:,payoffs:,equilibria:,kind: の値 mdp,およびパラメータの出所 motivation.rho と motivation.kappa である。games: 0.1 を宣言するファイルでは,付録Iが, players:,payoffs:,equilibria:,およびコマンドの owner: を定義し,kind: の値 smg を 追加し,その種類のモデルについてS-9を置き換える。sync:,変数の owner:,mdp,および 2つのパラメータの出所は,そこでも予約されたままである。games: 0.1 を宣言しないファイルでは, これらはすべて予約されたままである。

H.2 構文(A.2へのEBNFの追加)​

文法は付録Aの記法に従う。identifier,int_literal, bool_literal,string,number,scalar,comp_op は付録Aで定義している。 sos_body に1つの省略可能なキーを追加する。

sos_body = ... ,
[ "model:" , model_block ] ;

model_block = [ "kind:" , "dtmc" ] ,
[ "parameters:" , { "-" , param_def } ] ,
"variables:" , { "-" , var_def } ,
"commands:" , { "-" , command_def } ,
[ "labels:" , { identifier , ":" , state_pred } ] ,
[ "regimes:" , { identifier , ":" , regime_def } ] ,
[ "rewards:" , { "-" , reward_def } ] ,
[ "properties:" , { "-" , property_def } ] ,
[ "regime_maps:" , { "-" , regime_map_def } ] ;

param_def = "id:" , identifier ,
( "from:" , param_source , [ "range:" , interval ]
| "range:" , interval , [ "value:" , number ] ) ;
param_source = identifier , "." , ( "alpha" | "beta" | "lambda" )
| "environment" , "." , identifier ; (* string *)
interval = "-" , number , "-" , number ; (* a sequence of exactly two numbers: [lo, hi] *)

var_def = "id:" , identifier ,
"type:" , var_type ,
"init:" , scalar ;
var_type = "bool" | int_range | enum_type ; (* string *)
int_range = "[" , int_const , ".." , int_const , "]" ;
enum_type = "{" , identifier , { "," , identifier } , "}" ;
int_const = [ "-" ] , int_literal ;

command_def = [ "action:" , identifier ] ,
[ "when:" , { "-" , identifier } ] ,
[ "guard:" , state_pred ] , (* string *)
"updates:" , { "-" , update_def } ;
update_def = [ "prob:" , ( param_expr | "rest" ) ] , (* string or number *)
[ "set:" , { identifier , ":" , state_pred } ] ;

regime_def = [ "parameters:" , { identifier , ":" , number } ] ;

reward_def = "id:" , identifier ,
"items:" , { "-" , reward_item } ;
reward_item = [ "action:" , identifier ] ,
[ "guard:" , state_pred ] , (* string *)
"value:" , param_expr ; (* string or number *)

property_def = "id:" , identifier ,
[ "regimes:" , { "-" , identifier } ] ,
"expr:" , property ; (* string *)

regime_map_def = "id:" , identifier ,
"over:" , { identifier , ":" , interval } ,
[ "regimes:" , { "-" , identifier } ] ,
"objective:" , objective ,
[ "constraint:" , threshold_prop ] , (* string *)
[ "resolution:" , number ] ;
objective = "maximize:" , query_prop (* string *)
| "minimize:" , query_prop ; (* string *)

3つの小さな式言語を,文字列スカラーの中に書く。state_pred と param_expr は, 付録AのA.10節の predicate と arith_expr の 部分集合であり,優先順位と結合性は同じである。property は本付録で新たに定義する(H.8)。

state_pred = s_and , { "OR" , s_and } ;
s_and = s_not , { "AND" , s_not } ;
s_not = "NOT" , s_not | s_cmp ;
s_cmp = s_sum , [ comp_op , s_sum ] ;
s_sum = s_term , { ( "+" | "-" ) , s_term } ;
s_term = s_factor , { "*" , s_factor } ;
s_factor = "(" , state_pred , ")" | "-" , s_factor
| int_literal | bool_literal | identifier ;

param_expr = p_term , { ( "+" | "-" ) , p_term } ;
p_term = p_factor , { "*" , p_factor } ;
p_factor = "(" , param_expr , ")" | "-" , p_factor
| decimal | identifier ;
decimal = int_literal , [ "." , int_literal ] ;

property = query_prop | threshold_prop ;
query_prop = quantity , "=?" , "[" , path , "]" ;
threshold_prop = quantity , threshold_op , decimal ,
"[" , path , "]" ;
quantity = "P" | "R" , "{" , string , "}" ;
threshold_op = ">=" | ">" | "<=" | "<" ;
path = "F" , [ step_bound ] , state_pred
| state_pred , "U" , [ step_bound ] , state_pred ;
step_bound = "<=" , int_literal ;

R{"…"} では,経路はステップ上限のない F φ でなければならない(S-13)。state_pred には, 量化子,関数呼び出し,メンバーアクセス,添字付き参照,文字列,時間長,浮動小数点リテラル,除算がない。 param_expr は多項式であり,除算,比較,関数呼び出しがない。3つの部分言語の数は,数字の並びに 省略可能な小数部が付いたもの(decimal)であり,指数形式はない。

YAMLでの値の書き方。 bool 以外の var_type,from:,expr:,および maximize:, minimize:,constraint: の値は,引用符で囲んだ文字列でなければならない。報酬の名前を含む性質は, 一重引用符のスカラーの中に書く('R{"delay"}<=1.5 [ F done ]')。prob:,報酬の value:, init:,および set: の項目の右辺は,文字列の代わりにYAMLの数または真偽値でもよく (prob: 0.5,init: false),guard: はYAMLの真偽値 true または false でもよい。 YAML 1.1のローダーでは,引用符のないスカラー ON,No,Off,Yes,null,~ は 名前ではなく真偽値またはnullになる。そのような名前は,マッピングのキー (model.regimes:,over:,set:)または init: の値である位置では,引用符で囲まなければならない (A.12を参照)。 そのようなローダーは 1e-3 も文字列として読む。数は指数なしで書くことが望ましい (range: [0, 0.001])。

数は実数であり,厳密に扱う。文字列の中の数値リテラルは,書かれたとおりの10進小数である。 YAMLの数値スカラーは,ローダーが生成した浮動小数点値に往復変換で戻る最短の10進小数として読む。 この10進小数が書かれたものと一致するように,記述者は有効数字を15桁より多く書いてはならない。

既定値。 kind: は dtmc である。guard: は "true" である。省略した prob: は rest であり, 省略した set: はどの変数も変えず,省略した when: はすべての設計を意味する。制度パラメータの range: は [0, 1] である。性質の regimes: はすべての設計,モードマップの regimes: は ファイルのすべてのモードである。resolution: は 0.05 である。

H.3 パラメータ​

model.parameters: はパラメータを宣言する。from: を持たないパラメータは自由である。 from: を持つパラメータは束縛されている。

from:束縛先宣言値
"C.alpha"id: C を持つ契約の information.alphaそこに書かれた数(あれば)
"C.beta"契約 C の authority.betaそこに書かれた数(あれば)
"C.lambda"契約 C の incentives.lambdaそこに書かれた数(あれば)
"environment.X"context.environment の項目 Xその項目。YAMLの数でなければならない

ドットの前の語 environment は,常に context.environment を指す。それ以外の名前は,契約の id で なければならない。契約に束縛されたパラメータを制度パラメータという。束縛されたパラメータは value: を持たない。自由なパラメータの宣言値は,その value:(あれば)である。

range: [lo, hi] は,有限の数 lo ≤ hi による閉区間 lo ≤ x ≤ hi であり,これを宣言範囲という。 制度パラメータでは既定値が [0, 1] であり,指定する場合は [0, 1] の中に収まらなければならない。 それ以外のパラメータでは必須である。ファイルのどこであれパラメータに与えられる値は,それが束縛されている 契約の数も含めて,すべて宣言範囲に入らなければならない(S-4)。

設計 D(H.6)のもとでのパラメータの固定値は,D のモードがそのパラメータに値を割り当てていれば その値であり,そうでなければ宣言値である。どのパラメータも,どの設計のもとでも固定値を 持たなければならない(S-11)。モードマップ問い合わせが over: に挙げるパラメータは,その問い合わせで 開いている(open)という。そこではパラメータは区間の上を動き,固定値は用いない。 それ以外のすべての場所,特に model.properties: のどの性質でも,どのパラメータも固定値を取る。

H.4 変数,ラベル,状態式​

model.variables: は,少なくとも1つの状態変数を宣言する。

type:定義域値の書き方
boolfalse,truetrue,false
"[lo..hi]"整数 lo,…,hi。ただし lo ≤ hi整数リテラル
"{A, B, C}"列挙した列挙リテラル。少なくとも1つで,すべて異なるリテラルの名前

init: は必須であり,定義域の値でなければならない。ただ1つの初期状態は,どの変数にも その init: の値を与える。列挙には順序がない。2つの列挙型は,同じリテラルを同じ順に挙げているとき 同じである。1つのリテラルが複数の型に現れてよい。

state_pred は状態の上で評価する。その中の識別子は,変数,列挙リテラル,または property の中に限り ラベルである。パラメータはその中に現れてはならない。state_pred は,整数(整数リテラルと変数, および +,-,*),真偽値(true,false,真偽値の変数,ラベル,比較,および AND,OR, NOT),または列挙型(リテラルまたは変数)のいずれかである。<,<=,>,>= は2つの整数を 比較する。== と != は,2つの整数,2つの真偽値,または同じ列挙型の2つの値を比較し,列挙型の場合は 少なくとも一方が変数である(2つのリテラルどうしは比較しない)。ガード,ラベル,報酬のガード, および property の各 state_pred は,真偽値でなければならない。整数の算術は厳密であり, 変数の範囲に制限されない。定義域に入らなければならないのは,更新が代入する値だけである(H.5)。

model.labels: は,真偽値の状態述語に名前を付ける(delivered: "task == Delivered")。ラベルは, property の state_pred の中で,真偽値の変数が書ける位置に書くことができ,それ以外の場所には 書けない。ラベル自身の述語は変数だけを参照する。

H.5 コマンド​

model.commands: は,ガード付き確率コマンドのリストである。例はH.12にある。

有効性。 コマンドは,when: を持たないか,その when: が設計のモードを挙げているとき, その設計に存在する。コマンドは,設計に存在し,かつ状態でそのガードが真であるとき, その状態で有効である。どの状態でも,有効になりうるコマンドは高々1つである(S-9)。

更新。 状態 s で更新を取ると,set: に挙げた各変数が,s で評価した右辺の値を持ち (すべての右辺を,どの代入よりも前に評価する),それ以外の変数はすべて値を保つ状態になる。 その値は,コマンドが有効であるときは常に定義域に入らなければならない(S-7)。値を折り返したり, 範囲に切り詰めたりすることはない。

確率。 prob: は,数値リテラルとパラメータの上の param_expr である。コマンドの更新のうち 高々1つが確率 rest を持つ。これは明示しても省略によってもよく,1からそのコマンドの他の確率の和を 引いたものである。rest のないコマンドは,パラメータを含まない確率だけを持たなければならず, それらの和はちょうど1でなければならない(S-8)。したがって,パラメータが現れるコマンドは常に ちょうど1つの rest を持ち,その確率の和は構成上1になる。

良定義性。 設計は,すべてのパラメータへの数の割当てにおいて,その設計に存在するすべてのコマンドの すべての確率が,rest の値も含めて [0, 1] に入り,すべての報酬の値(H.8)が負でないとき, その割当てにおいて良定義である。H.7からH.9は,そこでのみ定義される。S-11は固定値でそれを要求し, S-14はモードマップの領域の上でそれを要求する。

グラフ保存。 領域は,設計のコマンドのどの確率も,その領域のすべての付値で0である場合を除いて, 領域のどの付値でも0にならないとき,その設計についてグラフ保存である。確率が0になるところでは, 解関数(H.7)は連続であるとは限らない。ある状態に到達する確率が0になることがあり,期待報酬が +∞ になることがある。処理系は,グラフ保存でないセルの認証を見送ってよい。そのときセルは undecided になる(H.9)。そのようなセルを認証する処理系は,この仮定がなくても健全な方法を 用いなければならない。グラフ保存を仮定する方法を,そのようなセルに適用してはならない。

アクションラベル。 action: はコマンドに名前を付ける。複数のコマンドが1つの名前を共有してよい。 コマンドはその名前で同期しない。遷移報酬がこれを参照し(H.8),エクスポートしたモデルに現れる(H.11)。

デッドロック。 どのコマンドも有効でない状態は,確率1でその状態にとどまる。これは誤りではない。 「配送済み」のような吸収状態は,何も有効にしないことで書く。

H.6 モードと設計​

A.7は,モードを transitions: を通じてのみ導入する。 ファイルのモードとは,そこで from: と to: に用いる名前である。したがって,設計を比較するには transitions: ブロックが必要である。model.regimes: はモードごとにパラメータの値を割り当て, コマンドの when:(H.5)は,そのコマンドがどのモードに存在するかを述べる。

regimes:
CENTRALIZED: { parameters: { beta: 0.9 } }
DISTRIBUTED: { parameters: { beta: 0.1 } }

割り当てた値は,そのモードのもとで宣言値に代わり,宣言範囲に入らなければならない。束縛された パラメータについては,契約が宣言どおりの設計の値を与え,それに値を割り当てるモードは, それが別の値を取る運用モードを記述する。項目のないモードは何も割り当てない。

cadl 0.3.32から,コア言語のブロック regimes:(A.7.1) も,モードごとに,ソース C.alpha,C.beta,C.lambda,environment.X に値を束縛する。 regimes: がそのモードで,束縛されたパラメータのソースに値を束縛しているとき,その値は,model.regimes: が 割り当てた場合と同じく,そのモードの設計でのパラメータの値である。model.regimes: はそのモードで 同じ値を書いてもよいが,別の値を与えてはならない(R-7)。その値は宣言範囲に入らなければならず (S-4),そのパラメータはS-14とI-9では割り当てられたものとして扱うので,モードマップと均衡マップは それを開けない。regimes: がそのモードで束縛しないパラメータ,特に自由なパラメータには, これまでどおり model.regimes: が値を割り当てる。その値は確率モデルの中でだけ使われ,IR, シミュレータの設定,生成されるコードは,regimes: の値または宣言された値を使う。

設計とは,モードと,そのパラメータの割当て,およびそこに存在するコマンドの集合を合わせたものである。 「モード R のもとでのモデル」,「設計 R」,「制度 R」は,いずれもこれを意味する。モードを持つ ファイルは,モードごとに1つの設計を持ち,設計にはモードの名前を付ける。設計を列挙またはエクスポートする ところでは,その順序は transitions: に最初に現れる順である(項目の from: がその to: より先)。 transitions: のないファイルは,base という名前の設計をちょうど1つ持ち,それは割当てを持たず, すべてのコマンドを含む。そのようなファイルには,model.regimes:,when:,model.regime_maps: が 現れてはならない(S-10)。transition_def の condition: は,切替の運用上の規則である。 本付録は,それをモードマップと比較しない。

H.7 意味論:誘導されるパラメトリックなマルコフ連鎖​

k 個の更新を持つコマンド c について,その j 番目の更新の確率の式を f(c, j) と書き(rest の場合は, 1から他の和を引いたもの),j 番目の更新が状態 s で与える状態を u(c, j)(s) と書く。設計 D を固定し, θ を,すべてのパラメータに数を割り当て,D が θ において良定義である(H.5)ものとする。f[θ] は, θ のもとでの f の値である。θ における D のモードモデルは,離散時間マルコフ連鎖 M(D, θ) = (S, s₀, P) である。

  • 状態。 S は,すべての変数に定義域の値を割り当てる割当て全体の集合である。S は有限であり, θ にも D にも依存しない。
  • 初期状態。 s₀ は,init: の値が与える状態である。
  • 遷移関数。 D のもとで s においてコマンド c が有効であれば(S-9により一意である),P(s, s′) は, u(c, j)(s) = s′ となる更新 j にわたる f(c, j)[θ] の和である。s で有効なコマンドがなければ, P(s, s) = 1 であり,他のすべての s′ について P(s, s′) = 0 である。

P(s, ·) は,どの s についても確率分布である。経路とは,状態の無限列 s₀ s₁ s₂ … であって, どの P(sᵢ, sᵢ₊₁) も正であるものをいう。各遷移が1ステップである。M(D, θ) は,標準的な方法で 経路の上の確率測度を誘導する。

性質(H.8)については,θ はどのパラメータにも D のもとでの固定値を与える。領域 B を持つ モードマップ問い合わせ(H.9)については,各付値 v ∈ B が,開いているパラメータでは v と一致し, それ以外では固定値を持つ θ を与える。このとき問い合わせの値は v の関数 J_D であり,B から, +∞ を加えて拡張した実数への関数である。これを設計の解関数という。

H.8 報酬と性質​

報酬。 model.rewards: は,名前付きの報酬構造を宣言する。各項目は value: を持ち,これは param_expr である(パラメータに依存してよいが,状態には依存しない)。action: のない項目は 状態報酬であり,そのガードが真である状態から取る各ステップで得られる。デッドロック状態の自己ループも 含む。action: のある項目は遷移報酬であり,そのガードが真である状態から,そのアクションラベルを 持つコマンドを取る各ステップで得られる。1ステップの報酬は,その構造の項目のうち,そのステップに 当てはまるすべての項目の値の和である。

性質言語。 property(H.2)は,PRISMの性質言語 [Kwiatkowska+, CAV 2011]と同じように書く。これは,確率時相論理PCTL [Hansson & Jonsson, 1994]に期待報酬の演算子を加えたものの小さな断片であり, 標準的な意味を持つ。演算子は入れ子にできない。s₀ s₁ s₂ … を経路とし,φ,φ₁,φ₂ を状態述語とする。

経路式経路がそれを満たす条件
F φある i ≥ 0 について sᵢ で φ が成り立つ
F<=k φある 0 ≤ i ≤ k について sᵢ で φ が成り立つ
φ₁ U φ₂ある i ≥ 0 について sᵢ で φ₂ が成り立ち,j < i であるすべての sⱼ で φ₁ が成り立つ
φ₁ U<=k φ₂同じ。ただし 0 ≤ i ≤ k

ステップ上限は,初期状態からのステップを数える。次のトークンが <= である F または U は, 間の空白がどうであれ,ステップ上限を持つ(F x <= 3 は,述語 x <= 3 の上限のない F である)。

性質M(D, θ) での意味
P=? [ ψ ]ψ を満たす経路の確率
P⋈b [ ψ ]その確率 ⋈ b。⋈ は >=,>,<=,< のいずれか
R{"r"}=? [ F φ ]φ が初めて成り立つまでに累積する,構造 r の期待報酬
R{"r"}⋈c [ F φ ]その期待値 ⋈ c

R については,経路の上で φ が成り立つ最初の位置を i とする。経路の累積報酬は,ステップ 0,…,i − 1 の報酬の和である。期待報酬は,φ に確率1で到達するときはこの和の期待値であり, そうでないときは +∞ である。+∞ はどの数よりも大きい。=? を持つ性質を問い合わせといい, 閾値を持つ性質を閾値性質という。

model.properties:。 各項目は,regimes: に挙げた設計(既定値はすべての設計)の性質を, すべてのパラメータの固定値において述べる。結果は,設計ごとに,問い合わせの値,または閾値性質に対する satisfied か violated である。結果を報告する処理系は,それを厳密な算術で,または健全な誤差限界を持つ 数値計算で計算するか,結果を近似値として示さなければならない。誤差限界によって決まらない閾値は inconclusive である。

演算子 F と U は,付録Fの within,throughout,until ではない。 後者は,動作中のシステムの1つの時刻付きトレースの上で評価して判定を与え,前者は,モデルのすべての 経路の上で,ステップを単位として評価して確率または期待値を与える。両者を混ぜることはできず, バージョン0.1は,規範とモデルの性質の間の変換を定義しない。

H.9 モードマップ問い合わせ​

model.regime_maps: は,モードマップ問い合わせを列挙する(例はH.12にある)。問い合わせのキーは 次のとおりである。

  • over: は,開いているパラメータを与える。少なくとも1つ,多くとも4つであり,それぞれに 宣言範囲の中の閉区間 [lo, hi],lo < hi を与える。領域 B は,これらの区間がなす直方体である。 over: のパラメータには,model.regimes: のどのモードも値を割り当ててはならない。 制度パラメータも他のパラメータと同じように開くことができ,αやλについてのモードマップはそのようにして求める。
  • regimes: は,比較するモードを列挙する。少なくとも2つであり,それぞれ1回だけ挙げる。
  • objective: は,maximize: または minimize: のちょうど1つのキーを持ち,その値は問い合わせである。 J_R(v) は,モード R の設計での,付値 v における問い合わせの値である(H.7)。「x は y と同等以上に 良い」を x ⪰ y と書く。maximize: では x ≥ y,minimize: では x ≤ y である。
  • constraint: は,省略可能な閾値性質である。R の設計が v において制約を満たし(制約がなければ真), かつ minimize: では J_R(v) が有限であることを,sat_R(v) と書く。maximize: では,値 +∞ を 認め,それはどの値とも同等以上に良い。
  • resolution: は,0 < r < 1 である数 r であり,B の体積のうち未決定のまま残ってよい割合である。

比較するどの設計も,B のすべての付値において良定義でなければならない(S-14)。

何を問うか。 付値 v において,モードは,制約を満たし,かつ制約を満たすどのモードとも同等以上に 良いとき,最適である。

R ∈ opt(v) iff sat_R(v), and J_R(v) ⪰ J_R'(v)
for every compared regime R' with sat_R'(v)

opt(v) が空になるのは,v においてどのモードも制約を満たさないとき(minimize: では,どのモードも値が +∞ であるときも)に限られ,モードが並ぶときには複数の要素を持つ。セルとは,B に含まれる 閉じた直方体である。モード R は,すべての v ∈ C について R ∈ opt(v) であるとき, セル C の上で最適である。C は,すべての v ∈ C について opt(v) が空であるとき, 実行不能である。あるモードがセルの上で最適であると決定することが,RD-1.3の 比較型の領域検証の問題である。パラメータ合成における領域検証は,1つのモデルがある領域で閾値を 満たすかを問う [Junges+, FMSD 2024]。ここでは,複数のモデルの解関数を 互いに比較する。

結果。 答えであるモードマップは,B を覆い,内部が互いに交わらない有限個のセルの集合であり, 各セルは status と集合 best を持つ。これに,未決定の割合(undecided のセルの体積を B の体積で 割ったもの)と,それが resolution: 以下であるかどうかを添える。

status主張best
decidedbest のどのモードも,セルの上で最適である空でないモードの集合
infeasibleセルは実行不能である空
undecidedなし。最良のモードがセルの中で変わるか,処理系が決定できなかった空

best は,セルの上で最適であるすべてのモードを含まなくてもよい。モードがセル全体で並ぶところでは, それらをすべて挙げることが望ましい。⪰ は狭義でないため,best の集合が異なる隣り合うセルは 矛盾しない。共通の境界の上では,両方のセルのモードが最適である。最適なモードが変わる点はセルの内部を 通るため,分割をどれほど細かくしても,一部のセルは undecided のままになる。resolution: が 0より大きいのはこのためである。

認証付き。 decided と infeasible は,セルのすべての付値についての主張である。処理系は, セル全体について健全な方法により,厳密な算術または健全な誤差限界を持つ数値計算で確立した場合を除いて, これらの主張をしてはならない。これは,ただ1点についての主張にも当てはまる。パラメータリフティングによる 領域検証と,解関数の上の厳密な推論は,そのような方法である。標本点での評価は,どれほど多くても そうではない。resolution: に算入するのは,そのような認証付きのセルだけである。要求された 分解能に達することができない処理系も,マップを報告し,達しなかったことを述べる。処理系は, マップとともに方法の名前を示すことが望ましい。

これらの主張は,セルの上でH.7が定義されていることを前提とする。処理系は,比較するどの設計も セルのすべての付値において良定義(H.5)である場合を除いて,セルについて decided または infeasible を主張してはならない。確率が開いているパラメータについて多重アフィンである設計では, S-14の頂点の検査がこれを確立する。それ以外の設計では,処理系は,セルについてこれを確立するか, セルを undecided のままにしなければならない。

上下界によるセルの決定。 ある方法が,比較する各モード R について,セル C のすべての付値で 成り立つ J_R の下界 l_R と上界 u_R を与え(界は +∞ であってよい),制約の量についても同様に 上下界を与えるとする。上下界が,すべての v ∈ C について sat_R(v) を示すとき,R は C の上で 内であるといい,すべての v ∈ C について sat_R(v) が成り立たないことを示すとき,C の上で 外であるという。このとき,次が成り立つ。

  • 比較するどのモードも C の上で外であるとき,C は実行不能である。
  • R が C の上で内であり,かつ,比較する他のどのモード R′ についても,R′ が C の上で外であるか, maximize: では l_R ≥ u_R′(minimize: では u_R ≤ l_R′)であるとき,R は C の上で最適である。

これらの条件は十分条件であり,必要条件ではない。条件は,ある解関数の界を別の解関数の界と比べる ものであり,2つの関数を同じ付値で比べるものではない。したがって,2つのモードが並ぶ点の近くのセルは, 一方のモードがその上で最適であっても,undecided のまま残ることがある。また,セル全体で並ぶ モードの両方が見つかるのは,それらの上下界が一致するとき,または2つの解関数が同じであることを 処理系が判定できるときに限られる。

推定。 処理系は,これに加えて,たとえばシミュレーションによる,標本点での目的の推定を, その信頼度とともに報告してよい。推定はセルとは分けて報告する。推定はそれらの点だけについての 主張であり,セルの状態を変えることはなく,resolution: に算入することもない。

H.10 静的意味論​

本拡張を実装する処理系は,stochastic: 0.1 を宣言しているファイルにおいて,既存の検査に加えて, 次の検査をしなければならない。

  • S-1. model: は,少なくとも1つの変数を持つ variables: と,commands: を持たなければならない。 commands: は空のリストでもよい。kind: は,あれば dtmc でなければならない。ただし,次の場合は, この規則の誤りではない。拡張 games(付録I)を,そのバージョンを問わず宣言するファイルでは, その拡張を実装していない処理系は,kind: があって dtmc でないモデルを解釈しない。処理系は, 1つの情報レベルの診断を出し,そのブロックにはS-2からS-15のどれも適用せず,そのブロックを マルコフ連鎖として評価も,IRへの変換も,エクスポートもしてはならない(H.15)。games を 宣言しないファイルでは,そのような kind: は誤りである。
  • S-2. パラメータ,変数,報酬構造,性質,モードマップの id,すべてのラベル名,すべての 列挙リテラル,すべてのアクションラベルは,識別子でなければならず, A.11の式の部分言語のキーワード(AND,OR, NOT,true,false,in,exists),IN,または本付録の部分言語のキーワード(rest,F, U,P,R)であってはならない。A.11の構造キー(alpha,beta,…)は,ここでは予約されていない。 パラメータ,変数,ラベル,列挙リテラルは1つの名前空間を共有し,その中ではどの名前も1回だけ宣言する。 ただし,1つのリテラルが複数の列挙型に現れてよい。リテラル L を持つ列挙変数 x について, 生成される名前 x_L(H.11)は,その名前空間で宣言されたどの名前とも,他のどの生成される名前とも 異ならなければならない。ラベルに init または deadlock という名前を付けてはならない。これらは PRISMの組み込みラベルである。報酬構造,性質とモードマップ,アクションラベルは,それぞれ独自の 名前空間を持つ。1つのアクションラベルを複数のコマンドが用いてよい。
  • S-3. from: は,C.alpha,C.beta,C.lambda,または environment.X の形の文字列で なければならない。ここで C は宣言済みの契約の id であり,X は値がYAMLの数である context.environment のキーである。from: を持つパラメータは value: を持ってはならない。 2つのパラメータが同じ出所を持つとき,処理系は警告することが望ましい。
  • S-4. range: は,lo ≤ hi である2つの有限の数の列 [lo, hi] でなければならない。 制度パラメータを除いて必須であり,制度パラメータでは [0, 1] の中に収まらなければならない。 value:,出所が与える数,およびモードが割り当てるすべての値は,宣言範囲に入らなければならない。
  • S-5. type: は,bool,lo ≤ hi である int_range,または少なくとも1つのリテラルを持ち, 同じリテラルを2回含まない enum_type でなければならない。init: は定義域の値でなければならない。
  • S-6. どの state_pred も,H.2の文法に適合し,型が正しくなければならない(H.4)。その識別子は, 宣言済みの変数,正しい型の列挙リテラル,または property の中に限りラベルであり,パラメータで あることはない。適合しない文字列は誤りである。不透明な述語として保持することはしない。 set: の項目の右辺については,構文の誤りはこの規則に,型または定義域の誤りはS-7に該当する。
  • S-7. set: のどのキーも宣言済みの変数でなければならず,その右辺は変数の型を持たなければならない。 コマンドが存在するすべての設計と,そのガードが真である S のすべての状態について,右辺の値は 定義域に入らなければならない(これは,S-9と同じく,S を列挙して判定する)。
  • S-8. prob: は,rest,数,または識別子が宣言済みのパラメータである param_expr で なければならない。コマンドは,少なくとも1つの更新を持ち,rest を持つ更新(明示または省略による)を 高々1つ持たなければならない。rest のないコマンドでは,どの確率もパラメータを含むことはできず, 確率の和はちょうど1でなければならない。パラメータを含まない確率は [0, 1] に入らなければならない。
  • S-9. すべての設計と S のすべての状態(到達可能かどうかを問わない)について,その設計に存在する コマンドのうち,ガードが真になりうるものは高々1つである。
  • S-10. model.regimes: のどのキーも,when: のどの名前も,ファイルのモードでなければならない。 モードの parameters: のどのキーも宣言済みのパラメータでなければならず,その値は数でなければならない。 transitions: のないファイルには,model.regimes:,when:,model.regime_maps: が現れてはならない。 model.regimes: ブロックがあるとき,その中に項目のないモードについて,処理系は警告することが望ましい。
  • S-11. どのパラメータも,どの設計のもとでも固定値を持たなければならず,どの設計も,その固定値に おいて良定義でなければならない(H.5)。
  • S-12. 報酬構造は,少なくとも1つの項目を持たなければならない。項目の action: は,少なくとも 1つのコマンドのアクションラベルでなければならず,value: は,数,または宣言済みのパラメータの上の param_expr でなければならない。value: は,モードマップの over: に現れるパラメータに 言及してはならない。PRISMでは,パラメトリックモデル検査のパラメータは確率にしか用いることが できないからである [Kwiatkowska+, CAV 2011]。
  • S-13. どの property も,H.2の文法に適合しなければならない。R では,名前は宣言済みの 報酬構造でなければならず,経路はステップ上限のない F φ でなければならない。確率の閾値は [0, 1] に入らなければならない。性質の regimes: は,ファイルの設計を,それぞれ1回だけ 名指さなければならない。
  • S-14. モードマップでは,次のとおりである。over: は,1つから4つの宣言済みのパラメータを 持たなければならず,それぞれは宣言範囲の中で lo < hi であり,model.regimes: のどのモードも それに値を割り当てていてはならない。regimes: は,ファイルのモードを少なくとも2つ,それぞれ1回だけ 名指さなければならない(したがって,モードが2つより少ないファイルでは,既定値であるすべてのモードは 誤りである)。objective: は,maximize: と minimize: のちょうど一方を,問い合わせとともに 持たなければならない。constraint: は閾値性質でなければならない。resolution: は 0 < r < 1 を満たさなければならない。比較するどの設計も,領域全体で良定義でなければならない。 処理系は,これを少なくとも領域の頂点で検査しなければならない。開いているパラメータが1より高い べきで現れないとき(このとき式は開いているパラメータについて多重アフィンである),頂点が 直方体全体を決める。
  • S-15. 処理系は,H.1で予約したキーまたは値について情報レベルの診断を出すことが望ましく, それに意味を与えてはならない。予約した値(kind: mdp,motivation. の出所)には,S-1または S-3の誤りに加えて,この診断を出す。

6.3節の検査は model: を読まない。alpha,beta,lambda が [0, 1] に 入るというA.4の規則は変わらない。

本付録は5.4.2節を変えない。α,β,λが振る舞いに影響するのは,記述者が書く式を 通じてだけである。保証されるのは,モデルが束縛されたパラメータに用いる数が契約の数であることである。 ただし,モードが model.regimes: で別の数を割り当てる場合は除く。その場合,違いはファイルに明示される。

H.11 PRISMモデリング言語へのエクスポート​

本節は,エクスポートを行う処理系に対して規範的である。処理系は,モデル検査,領域検証, パラメータ合成を行うツールのために,設計ごとに,PRISMモデリング言語のモデルファイル1つと, それに付随する性質ファイル1つをエクスポートする。ファイルの名前は <name>_<design>.prism と <name>_<design>.props であり,<name> は,SoSの name のうち [A-Za-z0-9_.-] の外にある文字を すべて _ で置き換えたものである。H.12のリストは,正準の体裁(インデント,部分の間の1行の空行, 二項演算子の前後の1つの空白,ソースの括弧の保持)を示す。空白と空行だけが異なる2つのエクスポートは 等しい。以下の tr(e) は式の変換である。AND,OR,NOT,== は &,|,!,= になる。 変数 x と比較される,または変数 x に代入される列挙リテラル L は x_L になる。それ以外は, 括弧も含めて,書かれたとおりに保つ。

モデルファイルは,次の順である。

  1. 行 dtmc。
  2. パラメータごとに1つの定数。宣言の順に書く。ファイルの少なくとも1つのモードマップの over: に 現れるパラメータは開いており,値なしで const double p; と書く。それ以外のパラメータは, 設計のもとでの固定値とともに const double p = 0.9; と書く(over: のパラメータには どのモードも値を割り当てないため(S-14),2つの場合は衝突しない)。
  3. 各列挙変数 x について宣言の順に,その型の位置 i(0から数える)にある各リテラル L について, const int x_L = i;。
  4. module main,続いて宣言の順に変数。 x : bool init true; または x : bool init false;, x : [lo..hi] init v;,および k 個のリテラルを持つ列挙では x : [0..k-1] init i;。ここで i は init: のリテラルの位置である。
  5. 設計に存在するコマンド。宣言の順に,それぞれ [a] tr(guard) -> (p1) : upd1 + (p2) : upd2 + … ; と書く。ここで a はアクションラベルである (なければ空)。各確率の式は括弧の中に書く。rest は,コマンドの他の確率の上で,その順に (1 - ((p1) + (p2) + …)) と書く。rest を持つただ1つの更新の確率は (1) である。 更新は,set: の各項目についての (x'=tr(e)) を,変数の宣言の順に & でつないだものである。 set: のない更新は true である。
  6. 1つのデッドロックコマンド [] !((g1) | (g2) | …) -> true;。ここで g1,g2,… は,手順5の コマンドの変換したガードであり,その順に書く(設計がコマンドを持たないときは [] true -> true;)。モデルが,ツールによるデッドロック状態の扱いに依存しないように, これは常に書く。続いて endmodule。
  7. 各ラベルについて,宣言の順に, label "name" = (tr(pred));。
  8. 各報酬構造について,rewards "id",続いてその項目を順に書く。状態報酬は tr(guard) : (value);,遷移報酬は [a] tr(guard) : (value); と書く。続いて endrewards。 設計のどのコマンドも持たないアクションラベルの遷移報酬は書かない。その設計では決して得られず, PRISMとStormは,モデルにないアクションを挙げる項目を受け付けないからである。ある構造の項目を 1つも書かないときは,代わりにただ1つの項目 true : (0); を書く。Stormが空の報酬構造を 受け付けないからである。

数は,往復変換で戻る最短の10進小数として,指数なしで書く(0.9,1,0.001)。

識別子。 パラメータ,変数,アクションの名前,および生成される名前 x_L は,そのまま書く。 ただし,PRISM言語のキーワード,またはその組み込み関数名 floor,ceil,round,pow,mod, log のいずれかと等しい名前には,末尾に下線を1つ付ける。その結果が別の名前と衝突するとき, エクスポートする処理系は誤りを報告しなければならない。ラベルと報酬の名前は引用符で囲んで書き, 同じ規則で名前を変える。PRISMとStormは,引用符の中にも,キーワードでない識別子だけを受け付ける (label "max" はどちらでも構文誤りになる)。Stormは,組み込み関数名も受け付けない。 PRISMでは,ラベルと報酬構造はそれぞれ独自の名前空間を持つので,衝突は,2つのラベルの間, または2つの報酬構造の間でだけ報告する。予約されているキーワードは,PRISMのマニュアル [Kwiatkowska+, CAV 2011]のものであり,大文字と小文字を区別する。 A, bool, clock, const, ctmc, C, double, dtmc, E, endinit, endinvariant, endmodule, endobservables, endrewards, endsystem, false, formula, filter, func, F, global, G, init, invariant, I, int, label, max, mdp, min, module, X, nondeterministic, observable, observables, of, Pmax, Pmin, P, pomdp, popta, probabilistic, prob, pta, rate, rewards, Rmax, Rmin, R, S, stochastic, system, true, U, W。

性質ファイルは,次の順である。開いている各パラメータについて,その宣言値を持つコメント行 // const p = v。次に,model.properties: の性質のうち設計に関係する各性質。その前にコメント行 // id を置く。次に,設計を比較する各モードマップについて,その目的と制約。その前に // id objective と // id constraint を置く。性質はファイルに書かれたとおりに書くが, どの state_pred も tr で変換し,どのラベルも引用符で囲み,F または U の被演算子は, ただ1つの識別子,引用符付きのラベル,またはすでに括弧で囲まれた1つの式である場合を除いて, 括弧で囲む。 P=? [ F<=3 "delivered" ]。

領域,比較するモード,および resolution: は解析の引数であり,エクスポートしない。 古典的な形のパラメータリフティング [Quatmann+, ATVA 2016]は,パラメータについて多重アフィンである確率と, グラフ保存(H.5)である領域を仮定する [Heck+, ATVA 2025]。既存のツールは,モードマップを求める機能を持たない。 処理系は,複数のモードモデルの複数の解析からそれを組み立てる。

H.12 例​

配車係とロボットが荷物を配送する。集中モードでは,配送の決定のほとんどを配車係が下す。配車係の計画は, 情報が共有されていれば(α)良いが,配車係が稼働しており,かつメッセージが失われない場合にしか ロボットに届かない。分散モードでは,決定のほとんどをロボットが局所情報から下し,その質は一定である。 βは,決定が集中的に下される確率である。ロボットは多くとも3回試行する。

sos:
name: "RobotDeliveryStochastic"
type: Acknowledged
extensions:
- stochastic: 0.1

actors:
- { id: DISPATCHER, role: "Assigns and replans routes" }
- { id: "ROBOT[1..N]", role: "Delivers parcels" }

contracts:
- id: DELIVERY
parties: [DISPATCHER, "ROBOT[*]"]
information: { alpha: 0.9 }
authority: { decision_holder: DISPATCHER, beta: 0.9 }

transitions:
- { from: CENTRALIZED, to: DISTRIBUTED, condition: "loss_rate > 0.3" }
- { from: DISTRIBUTED, to: CENTRALIZED, condition: "loss_rate <= 0.2" }

model:
kind: dtmc
parameters:
- { id: p_fail, range: [0, 0.5], value: 0.05 } # 試行の間,配車係が停止している
- { id: p_loss, range: [0, 0.5], value: 0.1 } # 配車係からのメッセージが失われる
- { id: alpha, from: "DELIVERY.alpha" } # 0.9,範囲 [0, 1]
- { id: beta, from: "DELIVERY.beta" } # モードが割り当てる
- { id: q_local, range: [0, 1], value: 0.6 } # 局所的な決定の成功
variables:
- { id: task, type: "{Pending, Delivered}", init: Pending }
- { id: attempts, type: "[0..3]", init: 0 }
labels:
delivered: "task == Delivered"
given_up: "task == Pending AND attempts == 3"
commands:
- action: attempt
guard: "task == Pending AND attempts < 3"
updates:
- prob: "beta * alpha * (1 - p_fail) * (1 - p_loss) + (1 - beta) * q_local"
set: { task: Delivered, attempts: "attempts + 1" }
- prob: rest
set: { attempts: "attempts + 1" }
regimes:
CENTRALIZED: { parameters: { beta: 0.9 } }
DISTRIBUTED: { parameters: { beta: 0.1 } }
rewards:
- { id: delay, items: [ { action: attempt, value: 1 } ] }
properties:
- { id: P_DELIVERY, expr: "P>=0.95 [ F<=3 delivered ]" }
- { id: P_EVENTUAL, expr: "P=? [ F delivered ]" }
- { id: P_DELAY, regimes: [CENTRALIZED], expr: 'R{"delay"}<=1.5 [ F delivered OR given_up ]' }
regime_maps:
- id: best_for_delivery
over: { p_fail: [0, 0.5], p_loss: [0, 0.5] }
regimes: [CENTRALIZED, DISTRIBUTED]
objective: { maximize: "P=? [ F<=3 delivered ]" }
constraint: "P>=0.9 [ F<=3 delivered ]"
resolution: 0.05

2つの遷移の condition:(loss_rate の閾値)は運用上の切替規則であり,以下で計算する 認証付きの境界とは独立である。モデルは8つの状態を持ち,そのうち7つが到達可能である。 ただ1つのコマンドはS-9を満たし,ガードが attempts < 3 を要求するため,その更新 attempts + 1 は [0..3] にとどまる(S-7)。task == Delivered である状態と状態 given_up は, 何も有効にせず,自分自身へループする。2つの設計は β だけが異なる。

x = (1 − p_fail)(1 − p_loss) と書き,1回の試行が成功する確率を s と書く。α = 0.9 および q_local = 0.6 のとき,次のとおりである。

モードβs = β·α·x + (1 − β)·q_local
CENTRALIZED0.9s_C = 0.81·x + 0.06
DISTRIBUTED0.1s_D = 0.09·x + 0.54

問い合わせの領域では 0.25 ≤ x ≤ 1 であるから,0.2625 ≤ s_C ≤ 0.87 および 0.5625 ≤ s_D ≤ 0.63 である。すなわち,どちらの設計も領域の上で良定義であり,領域は グラフ保存であり,確率は p_fail と p_loss について多重アフィンである。各試行は独立に成功するため, どちらのモードについても次が成り立つ。

  • P=? [ F<=3 delivered ] の値は 1 − (1 − s)³ であり,P=? [ F delivered ] も同じ値を持つ。 モデルが非巡回であり,どの経路も3ステップ以内に吸収されるからである。
  • R{"delay"}=? [ F delivered OR given_up ] の値は 1 + (1 − s) + (1 − s)² であり, これは試行回数の期待値である。

R{"delay"}=? [ F delivered ] の値は +∞ である。delivered に確率1で到達するわけではない からである。

性質。 固定値 p_fail = 0.05 と p_loss = 0.1 では,x = 0.855,s_C = 0.75255, s_D = 0.61695 である。本節の計算値は,小数第6位までに丸めている。

性質設計値結果
P_DELIVERYCENTRALIZED1 − 0.24745³ = 0.984848satisfied
P_DELIVERYDISTRIBUTED1 − 0.38305³ = 0.943796violated
P_EVENTUALCENTRALIZED / DISTRIBUTED0.984848 / 0.943796(問い合わせ)
P_DELAYCENTRALIZED1 + 0.24745 + 0.24745² = 1.308682satisfied

P_DELAY は CENTRALIZED に限定している。DISTRIBUTED では値が 1.529777 になり,上限の 1.5 を 超える。

モードマップ。 1 − (1 − s)³ は s とともに増加するため,CENTRALIZED が DISTRIBUTED と 同等以上に良いのは,ちょうど s_C ≥ s_D のとき,すなわち 0.72·x ≥ 0.48 のときである。

  • (1 − p_fail)(1 − p_loss) ≥ 2/3 であるところでは,CENTRALIZED が最適である。
  • (1 − p_fail)(1 − p_loss) ≤ 2/3 であるところでは,DISTRIBUTED が最適である。
  • (p_fail, p_loss) = (0, 1/3) から (1/3, 0) に至る曲線 p_loss = 1 − 2 / (3·(1 − p_fail)) の上では, 両方が最適であり,s = 0.6,確率は 1 − 0.4³ = 0.936 である。

制約は,s ≥ 1 − 0.1^(1/3) = 0.535841 であるところで成り立つ。DISTRIBUTED は領域全体でこれを満たす (s_D ≥ 0.5625)。CENTRALIZED は,x ≥ 0.587458 であるところでこれを満たし,それより下では違反する。 違反する部分は DISTRIBUTED が最適である部分の中にあるため,制約はそこで CENTRALIZED を候補から外すが, best を変えない。故障が少なく損失が少ないと集中モードが有利になり,故障が多いか損失が多いと 分散モードが有利になる。

実装を確かめるための,いくつかの点での値を示す。

p_failp_lossxP, CENTRALIZEDP, DISTRIBUTEDbest
0010.9978030.949347CENTRALIZED
0.10.10.810.9771180.941994CENTRALIZED
0.21/62/30.9360.936両方
0.30.30.490.8398090.928061DISTRIBUTED(CENTRALIZED は制約に違反する)
0.50.50.250.5988690.916260DISTRIBUTED(CENTRALIZED は制約に違反する)

x はどちらのパラメータについても減少するため,セル [f₁, f₂] × [l₁, l₂] はその頂点によって認証される。(1 − f₂)(1 − l₂) ≥ 2/3 のとき,その上で CENTRALIZED が最適であり,(1 − f₁)(1 − l₁) ≤ 2/3 のとき DISTRIBUTED が最適であり, それ以外のときは曲線がセルを横切り,セルは undecided である。

2つの設計の上下界からセルを決定する方法(H.9)が決定するセルは,これより少ない。セルの上での x の最小値と最大値を,x_min = (1 − f₂)(1 − l₂),x_max = (1 − f₁)(1 − l₁) と書く。 どちらの設計についても,セルの上での値の範囲は,x が x_min から x_max までを動くときの 1 − (1 − s)³ の範囲にちょうど一致する。これらの範囲を比べると,x_min における s_C が x_max における s_D 以上であるとき,すなわち 0.81·x_min − 0.09·x_max ≥ 0.48 のとき CENTRALIZED に決定し,0.81·x_max − 0.09·x_min ≤ 0.48 のとき DISTRIBUTED に決定する。 どちらも満たさないセルは,曲線がセルを横切らないときも,undecided である。

エクスポート。 H.11により,設計 CENTRALIZED のモデルファイルは次のとおりである。 p_fail と p_loss は,モードマップが over: に挙げているため,開いている。DISTRIBUTED のファイルは, const double beta = 0.1; だけが異なる。

dtmc

const double p_fail;
const double p_loss;
const double alpha = 0.9;
const double beta = 0.9;
const double q_local = 0.6;
const int task_Pending = 0;
const int task_Delivered = 1;

module main
task : [0..1] init 0;
attempts : [0..3] init 0;
[attempt] task = task_Pending & attempts < 3 -> (beta * alpha * (1 - p_fail) * (1 - p_loss) + (1 - beta) * q_local) : (task'=task_Delivered) & (attempts'=attempts + 1) + (1 - ((beta * alpha * (1 - p_fail) * (1 - p_loss) + (1 - beta) * q_local))) : (attempts'=attempts + 1);
[] !((task = task_Pending & attempts < 3)) -> true;
endmodule

label "delivered" = (task = task_Delivered);
label "given_up" = (task = task_Pending & attempts = 3);

rewards "delay"
[attempt] true : (1);
endrewards

その性質ファイルは次のとおりである。

// const p_fail = 0.05
// const p_loss = 0.1
// P_DELIVERY
P>=0.95 [ F<=3 "delivered" ]
// P_EVENTUAL
P=? [ F "delivered" ]
// P_DELAY
R{"delay"}<=1.5 [ F ("delivered" | "given_up") ]
// best_for_delivery objective
P=? [ F<=3 "delivered" ]
// best_for_delivery constraint
P>=0.9 [ F<=3 "delivered" ]

H.13 中間表現(IR)への追加​

IRに,3つの層と並ぶトップレベルのフィールド stochastic_model を1つ追加する。本拡張が 宣言されていないとき,model: がないとき,またはブロックに検査の誤りがあるとき,これは null である。 付録EのE.7節と同じく,式はテキストのまま保持する。次の例は, 印を付けた箇所を省略している。

{
"stochastic_model": {
"kind": "dtmc",
"parameters": [
{ "id": "p_fail", "source": null, "range": [0, 0.5], "value": 0.05, "open": true },
{ "id": "alpha", "source": "DELIVERY.alpha", "range": [0, 1], "value": 0.9, "open": false }
// ... p_loss, beta, q_local
],
"designs": [ { "name": "CENTRALIZED", "parameters": { "beta": 0.9 } } ], // ... DISTRIBUTED
"properties": [ // ... P_EVENTUAL, P_DELAY
{ "id": "P_DELIVERY", "regimes": ["CENTRALIZED", "DISTRIBUTED"], "expr": "P>=0.95 [ F<=3 delivered ]" }
],
// ... "variables", "labels", "commands", "rewards": the fields of H.2 under the same names;
// a variable has "kind" (bool | int | enum), "lo", "hi", "literals", "init";
// a command has "index", "action", "when", "guard", "updates" (each with "prob", "set")
"regime_maps": [
{ "id": "best_for_delivery", "over": { "p_fail": [0, 0.5], "p_loss": [0, 0.5] },
"regimes": ["CENTRALIZED", "DISTRIBUTED"], "direction": "maximize",
"objective": "P=? [ F<=3 delivered ]", "constraint": "P>=0.9 [ F<=3 delivered ]", "resolution": 0.05 }
]
}
}

キーの順序は,kind,parameters,designs,properties,variables,labels,commands, rewards,regime_maps である。labels は各名前をそのテキストに対応付ける。prob はテキストである ("rest",または式か10進小数のテキスト)。set は各変数をテキストに対応付ける。報酬の項目は {action, guard, value} であり,value はテキストである。使わない lo または hi は null, 使わない literals は [] である。H.2の既定値は補ってある(when: [] はすべての設計を意味する)。 value はH.3の宣言値,または null である。open は,いずれかのモードマップが over: に挙げる パラメータで真である。designs は,すべての設計を,そのモードが割り当てる値とともに列挙する (transitions: のないファイルでは,ただ1つの項目 base)。index は,model.commands: の中での コマンドの位置であり,1から数える。解析の結果はIRに含まれない。

H.14 リファレンス実装の状況​

リファレンス実装は,cadl 0.3.20からstochastic 0.1を次のように実装する。

  • cadl は model: を構文解析し,cadl check で規則S-1からS-15を適用し(「望ましい」は警告とする。 S-7とS-9は状態空間を列挙して検査し,200 000状態を超える場合は列挙を拒否する),ブロックを H.13のIRへ変換する。
  • cadl model-export は,H.11のファイルを書き出す。
  • cadl model-check は,固定したパラメータの値における1つの設計を対象とする,厳密な有理数算術による 小さな参照評価器である。H.8の性質を,2 000個の未知数まで評価する。--regime-map ID を付けると, モードマップの目的を格子の点で評価する。これらは標本点での推定として報告し(H.9),決定済みの セルとしては報告しない。
  • cadl model-check --regime-map ID --certify は,cadl 0.3.22から,H.9の モードマップを計算する。外部のモデル検査器は実行しない。方法は,厳密な有理数算術による パラメータリフティング [Quatmann+, ATVA 2016]である。セルの上で, 設計をマルコフ決定過程に緩和する。この過程では,各状態が,他の状態とは独立に,その状態から出る 確率に現れる開いているパラメータについて,セルの頂点の1つを選ぶ。それらの確率が多重アフィンで あるとき,セルのどの付値における連鎖も,ある1つの確率的な方策のもとでのこの過程であるので, 過程の最小値と最大値は,セル全体で解関数の下界と上界になる。ステップ上限のある性質は 後ろ向き帰納法で解き,上限のない性質は,連立一次方程式を厳密に解く方策反復で解く。セルは, これらの上下界から,H.9の条件によって決定する。未決定のセルは,領域に対する区間の幅の比が 最も大きいパラメータに沿って二分する。未決定のセルのうち最も大きいものから二分し,未決定の割合が resolution: 以下になるか,予算が尽きるまで続ける(--max-depth,既定では1つのセルを 24回まで二分する。--max-cells,既定では20 000セルまで)。後者の場合,分解能に達しなかった ことを述べてマップを報告し,終了ステータスは1である。同じ主張を持つ2つの半分は,1つのセルとして 報告する。コマンドは,方法,セル,状態ごとのセルの数,および厳密な数としての未決定の割合を 報告する。推定(--grid)と認証付きのマップ(--certify)は別の出力であり,同時には指定できない。
  • 認証付きのマップの限界は,次のとおりである。
    • 2つの設計の上下界を比べるのであり,それらの差を比べるのではない。そのため,境界に隣り合うセルは undecided のまま残る(H.9,H.12)。セルの上で並ぶモードをともに挙げるのは,それらの上下界が 一致するとき,またはそれらの設計が同じモデルを持つときに限られる。
    • 開いているパラメータについて多重アフィンでない確率は,その単項式の上の厳密な区間演算で囲み, 状態は,これらの区間に入る分布の集合の頂点の1つを選ぶ。これは健全であるが,より粗い。 そのような設計は,区間が [0, 1] に入るときにだけ,セルの上で良定義であるとみなす。 そうでないとき,セルは undecided であり,報告はこの理由を示す。区間演算は過大に見積もるので, そのような確率が0または1になる付値の近くでは,セルをどれほど小さくしても,これを確立できない ことがある。
    • グラフ保存でないセルは,見送らずに解析する。確率の上下界は,決定過程の上下界である。 期待報酬が有限の上界を持つのは,過程のどの方策も確率1で目標に到達するときに限られる。 どの方策もそうでないとき,期待報酬はセル全体で +∞ である。その下界は,方策が蓄積する 期待報酬のうち最小のものである。
    • 計算量は,セルの数と状態の数とともに増える。セルの数は,開いているパラメータの数とともに増える。 どの方策も,2 000個までの未知数を持つ厳密な連立一次方程式で評価する。
    • S-14は,cadl check が領域の角で検査する。多重アフィンでない確率は,領域の内側でだけ [0, 1] を外れうる。認証付きのモードは,セルの中心または角でそれが分かるとき,誤りとして 報告する(終了状態2)。分からないときは,そのセルを undecided のままにする。
    • 有効数字が15桁を超えるYAMLの数は,H.2が禁じているが,ファイルの読み込み時に丸められ, 報告されない。そのとき,主張は丸めた後のモデルについてのものになる。
  • H.12の例(resolution: 0.05)では,認証付きのマップは95個のセルを持ち,60個が decided, 35個が undecided である。これは121個のセルの分割をまとめた結果である。解析したセルは241個で, 1つのセルの二分は多くとも10回である。CENTRALIZED は領域の 235/1024 で認証され(最適であるのは 領域の 0.2521 である),DISTRIBUTED は 738/1024 で認証され(最適であるのは 0.7479), 未決定の割合は 51/1024 = 0.0498 である。曲線は,未決定の35個のセルのうち31個を横切り, 残りの4個は曲線に隣り合う。計算はノートPCで約0.1秒である。resolution: 0.01 では0.8秒 (まとめる前のセルは726個),resolution: 0.002 では3.8秒(3 632個)である。
  • 認証付きのマップは,2つの方法で確認した。リファレンス実装のテストは両方を繰り返す。2つ目には stormpy が必要である。対象の8つのマップは,H.12のマップと,第2のモデルの7つのマップである。 第2のモデルは,3つのモード,サイクル,minimize: と期待報酬(1つのモードではどこでも +∞ であり, 他のモードでは領域の1つの面で +∞ である),領域の一部を実行不能にする制約,多重アフィンでない確率, グラフ保存でないセル,セル全体での並び,および3つの開いているパラメータを含む。
    • 8つのマップの decided と infeasible のセルすべて,212個を,その頂点,中心,および6個の 無作為な有理数の点で,厳密な参照評価器によって評価した。点での評価は2 512回である。そのどの点でも, 主張のとおり,best のどのモードも最適であるか,どのモードも制約を満たさない。
    • エクスポートしたファイルの上で,上下界をStorm(stormpy 2.0.0,厳密なパラメータリフティングの エンジン)と比較した。対象は,設計と,その設計についてグラフ保存であるセルとの134個の組である。 確率が多重アフィンである設計では,cadl の下界と上界は,Stormのものと有理数として等しい (159組の上下界)。Stormが細分によってセルの上で見つける極値は,cadl の上下界の中にある (213組)。セルについての制約に対するStormの判定(すべての付値が満たす,すべてが違反する, どちらでもない)は,79件のうち79件で cadl の主張と一致する。
    • Stormのパラメータリフティングは,グラフ保存である領域を仮定する。stormpyの verify は, そうでない領域を拒否する。また,各ステップで確率 p で done に到達する設計について, 0 ≤ p ≤ 1/2 の上で,その極値の計算は P=? [ F done ] の最小値として1を返した。 p = 0 での値は0である。そのため,グラフ保存でないセルは,参照評価器だけで確認した。
  • 独立したレビューで,認証付きのモードに誤った主張をさせることを試みたが,誤った主張は見つからなかった。乱数で生成した 3 290個のモデルについて,56 782個の decided または infeasible のセルを,1 731 349個の厳密な点で 検査した。グラフを保存しないセルと,多重アフィンでない設計を含む。決定過程の解法は,60 000個の 乱数で生成した過程について,すべての無記憶方策の総当たりと一致した。コードに注入した4つの 健全性の誤りは,いずれも検査の仕組みが検出した。
  • cadl regime-map は,これまでどおりモード名と遷移のグラフを報告する。
  • 逸脱:cadl 0.3.22は,拡張 games(付録I)に対応していない。games: 0.1 を 宣言するファイルの kind: smg を持つモデルについて,S-1とH.15が1つの情報レベルの診断だけを求め, それ以上の検査を求めないところで,S-1の誤りを報告し,1人のプレイヤーの2つのコマンドが同じ状態で 有効であるところでは,S-9の誤りも報告する。モデルの評価とエクスポートはしない。
  • エクスポートしたファイルは,PRISM 4.11とStorm(stormpy 2.0.0)で実行して確認した。対象は, H.12の例,when:,3分岐の更新,ガード付きの状態報酬と遷移報酬,U,U<=k,キーワードと 同じ名前を使う第2のモデル,および上の認証付きのマップのモデルであり,7つの設計の39個の性質である。 状態数は一致し,すべての値は,Stormと,PRISMの厳密エンジンのもとで,cadl model-check と 有理数として一致する。PRISMの厳密エンジンはステップ上限(F<=k,U<=k)を扱えないので, それらの性質は,PRISMとは浮動小数点で比較した。リファレンス実装のテストは,prism または stormpy がインストールされているときに,この比較を繰り返す。これらの実行で,エクスポートの 2つの不具合が分かった。cadl 0.3.20は,キーワードと同じ名前のラベルや報酬構造をそのまま 書き出しており,どちらのツールもそれを読み込めなかった。0.3.21は,H.11が現在述べるとおりに 名前を変える。cadl 0.3.21までは,設計のどのコマンドも持たないアクションの遷移報酬を 書き出しており,どちらのツールもそれを読み込めなかった。0.3.22は,H.11が 現在述べるとおりに,それを書かない。

H.15 後方互換性​

本拡張を用いないCADL v0.3のファイルは引き続き有効であり,同じように読まれる。本拡張は 1つのキーを追加するだけであり,既存のものの意味を何も変えない。

stochastic: 0.1 を宣言せずに model: を用いるファイルは,本付録に適合しない。本拡張を実装する 処理系は,そのようなファイルの model: ブロックを解釈せず(検査も,IRへの変換も,エクスポートも しない),宣言されていない拡張のキーとして報告することが望ましい。本拡張を実装していない処理系は, model: を理由にファイルを拒否してはならない。ファイルごとに1つの情報レベルの診断を出すことが 望ましい。

ファイルは,拡張 games(付録I)を,そのバージョンを問わず宣言し,kind: smg を持つモデルを 持つことがある。それはゲームであり,マルコフ連鎖ではない。本付録を実装し,付録Iを実装していない 処理系は,そのようなモデルを読み飛ばす(S-1)。処理系は,1つの情報レベルの診断でそれを報告し, stochastic_model は null であり,本付録の規則によってそのモデルを検査も,評価も,エクスポートも してはならない。H.7が,そのモデルが持たない意味を与えてしまうからである。そのようなファイルの中の, kind: dtmc を持つか kind: を持たないモデルは,本付録のモデルであり,これまでどおりに読む。