《ペトリネット》
【ぺとりねっと (Petri net) 】
ペトリネットは, 1962年C.A.Petriによって, 非同期的でかつ並列的にふるまうシステムに対して, その中の情報の流れや制御を記述し解析するために考えだされたものである. ペトリネットはいくつかの事象が並列的に発生する中で, それらの発生の順序, 頻度などにある制約が与えられているようなシステムをモデル化するために用いられてきた. 離散事象システムの特徴は, 事象生起の並行性, 非同期性, および非決定性にあり, ペトリネットはこのような特徴持ったシステムを条件(condition)と事象(event)を基本としてモデル化し, 数学的解析を可能にする. ペトリネットでは条件をプレースと呼ばれる丸印"○"で表し, 事象をトランジションと呼ばれる棒"｜"で表す. したがって, ペトリネットは有向枝をもつ2部グラフ(bipartite graph)の構造を有している.
ペトリネットの実行はプレースに置かれたマーク(これをトークンと呼ぶ)の位置とその動きによって制御される. トークンは黒丸()で表し, プレースの中に置く. プレースにトークンを割り当てることをマーキングという. 一般にペトリネットでは, システムの初期の状態を表すのに初期マーキングが割り当てられている. トークンの動きは発火規則に従っている. 図1にはペトリネットの要素と発火規則の適用例を示す. トークンがペトリネット内を動き回る様子, すなわち状態遷移はボードを使うゲームに似ていて, それは次のような規則に従っている.
(1) トークンはペトリネットのトランジションを発火(firing)させることによりネット内を移動する.
(2) トランジションを発火させるためにはトランジションが発火可能(enable)でなければならない. トランジションのすべての入力プレースにトークンがあるとき, そのトランジションは発火可能である(図1(b)).
(3) トランジションが発火すると, その入力プレースからトークンを取り除き, 新しいトークンを生成してそれを出力プレースに置く(図1(c)).
 |
| 図１ |
ところで, 条件が成立しているということは, すべての入力プレース内にトークンがあり, そのトランジションは発火可能の状態, すなわち事象が生起する状態になっていることを意味する. このように, トークンがペトリネット内を発火規則に従って動き回る様子は, ペトリネットの動的な性質を表している.
さらに複雑な発火規則を定めることによっていろいろな動的な動作をモデル化することができる.
ペトリネットによってシステムをモデル化し, そのモデルに基づいてシステムを解析しようとするとき, 一般的には, システムが支障なく所定の動作を行うために必要な基本的要件として, 次の3つが考えられる.
(1) モデル化したペトリネットは発散しないか. すなわち, おのおののプレースのトークン数はトランジションの発火によってつねに有界であるか.
(2) ある初期状態から目標状態へ移行する発火系列が存在するか. すなわち, マーキングのある初期状態からスタートして発火可能なトランジションを発火させ, 目標マーキングに到達できるか.
(3) モデルがデッドロックに陥ることはないか. すなわち, トランジションが発火できないようなマーキングがあるか.
これら3つの性質をペトリネットが有しているか否かを判定する問題は, ペトリネットの基本問題として知られている. そして, これらはそれぞれ"有界性問題", "可到達問題", "活性問題"と呼ばれている.
ペトリネットはいろいろな分野で応用されている. トランジションが発火可能であっても一定時間その発火を遅らせることで, 発火規則に時間遅れの概念を導入することができる. このようなペトリネットは時間ペトリネット(timed Petri net)と呼ばれている. さらに, 時間ペトリネットはシステムの確率的な事象の表現と解析を行うために拡張され, トランジションが発火可能になってから発火を開始するまでの時間を連続の確率分布をもつような確率変数で定義する確率ペトリネット(stochastic Petri net)も提案されている.
ペトリネットを線形代数的な観点から考察する方法として, ネットインバリアント(net invariant)の概念がある [1] . ペトリネットモデルを用いてシステムの性質を調べようとするとき, そのモデルの規模が大きくなった場合は, そのペトリネットモデルを数学的な手段で解析することが困難になる場合がある. そのような場合はコンピュータを用いたシミュレーションによる解析が適している [1].
参考文献
[1] 椎塚久雄, 『実例ペトリネット』, コロナ社, 1992.