ペトリネット

ペトリネットの定義

ペトリネットは、プレース(place)、トランジション(transition)という 二種類のノード(node)をもつ二部有向グラフ(bipartite digraph)である。 プレースは円で表されるノードであり、条件を表す。 トランジションは棒または箱で表されるノードであり、事象を表す。 これらを結ぶアーク(arc)は条件、事象の間の関係を表す。 プレース、トランジション、アークがシステムの構造を表現する。 アークには正整数の重みがつけられる場合がある。 重みはアークの本数で表すか、アークに重みを併記して表す。 重みがつけられないアークは重みが1であるとみなす。 プレースの上には、非負整数個のトークン(token)が置かれる。 トークンは点で表され、条件の成立を表す。 プレース上のトークンの配置をマーキング(marking)といい、システムの状態を表す。

形式的には、ペトリネットは $N=(P,\,T,\,F,\,W,\,m_0)$ で表される。

$$\left\{\mbox{%\begin{tabular}{ll} $P=\{p_1,\,p_2,\,\ldots,\... ...,\,1,\,2,\,\ldots\,\}$\ & 初期マーキング \end{tabular}} \right.$$

マーキングはベクトルの形で、 $m_0=[m_0(p_1)\,m_0(p_2)\,\cdots\,m_0(p_{\vert P\vert})]^T$ のように表すこともできる。

トランジション $t$ に向かうアークを $t$ の入力アーク、 $t$ の入力アークが出て行くもとのプレースを $t$ の入力プレースという。 $t$ から出て行くアークを出力アーク、 $t$ の出力アークが入って行く先のプレースを $t$ の出力プレースという。 プレース $p$ の入出力アーク、入出力トランジションもまた同様に定義する。

例 1   図2のペトリネットは、
　 $P=\{ p_1,\,p_2,\,p_3,\,p_4 \}$
　 $T=\{ t_1,\,t_2,\,t_3 \}$
　 $F=\{(p_1,t_1),\,(p_2,t_1),\,(p_3,t_2),\,(p_4,t_2),\,(p_4,t_3),\, (t_1,p_3),\,(t_1,p_4),\,(t_2,p_2),\,(t_3,p_1),\,(t_3,p_4)\}$
　 $W((p_1,t_1))=3,\,W((p_3,t_2))=2,\, W((p_2,t_1))=\cdots=W((t_3,p_4))=1$
　 $m_0(p_1)=3,\,m_0(p_2)=2,\,m_0(p_3)=1,\,m_0(p_4)=1$
と表される。

図 2: ペトリネット

マーキングをベクトルの形で表すと、 $m_0=[3\,2\,1\,1]^T$ となる。 $t_1$ の入力プレースは $\{p_1\,p_2\}$、出力プレースは $\{p_3,\,p_4\}$ である。 $p_1$ の入力トランジションは $\{t_3\}$、出力トランジションは $\{t_1\}$ である。

トランジションの発火

ペトリネットのマーキングはトランジションの発火(firing)によって遷移する。 トランジション $t$ がマーキング $m$ で発火可能(fireable, enabled)であるとは、 $t$ のすべての入力プレースが入力アークの重み以上の個数のトークンを持つこと であり、$m[t\rangle$ で表す。 発火可能なトランジションは発火してもしなくてもよい。 発火可能なトランジション $t$ が発火すると、 各入力プレースから入力アークの重みの数だけのトークンを取り去り、 各出力プレースに出力アークの重みの数だけのトークンを与える。 この結果のマーキングを $m'$ とすれば、$m[t\rangle m'$ と表される。

例 2   図2のペトリネットで、$t_1$ と $t_3$ は発火可能である。 $t_2$ は $p_3$ に入力アークの重み2以上のトークンがないので、発火可能ではない。 $t_1$ が発火した結果のマーキングを $m_1$ とすれば、 $m_1=[0\,1\,2\,2]^T$ である。

同時進行と競合

マーキング $m$ で 2つのトランジション $t$、$t'$ が発火可能であるものとする。 これらのトランジションが $m$ から $t$、$t'$ の順にも、$t'$、$t$ の順にも 順次発火できるとき、 $t$ と $t'$ は同時発火可能(simultaneously enabled)であるという。 そうでないとき、 $t$ と $t'$ は競合(conflict)の状態にあるという。

例 3   図3のペトリネットで、 $t_1$、$t_2$、$t_3$ はともに発火可能である。 $t_1$ と $t_3$ は同時発火可能であるが、 $t_1$ と $t_2$、$t_2$ と $t_3$ は競合の関係にある。

図 3: 同時進行と競合

問題 2   図4のペトリネットで、
　1. 図のマーキング $m_0$ から発火可能なトランジションはどれか。
　2. $m_0$ から発火可能なトランジションをそれぞれ発火させた結果のマーキングを示せ。
　3. $m_0$ で競合関係にあるトランジションはどれとどれか。

図 4: ペトリネット

ペトリネットとモデル化

以下に、3つのモデル化の例を挙げる。 ペトリネットのモデルとしての特徴にもふれる。

例 4   図5に簡単なジュースの自動販売機のモデルを示す。 客は110円または200円を投入し、ボタンを押す。 その結果、ジュースと釣り銭が出てくる。

図 5: 自動販売機のモデル

`=Y10'、`=Y100'、`button' とラベルづけされたトランジションが それぞれ、10円硬貨を投入する、100円硬貨を投入する、ボタンを押す動作を表す。 $p_1$、$p_2$ はそれぞれ、投入された10円硬貨、100円硬貨をトークンとしてもつ。 $t_1$、$t_2$、$t_3$ はそれぞれ、10円が11枚、10円が1枚と100円が1枚、100円が2枚 投入されると発火可能となる。 $p_3$ は十分な金額が投入されていて、 ボタンを押せばジュースが出てくることを表している。 このときボタンが押されると、$p_4$ にトークンが投入され、 投入金額が110円か200円かによって、$t_4$ または $t_5$ が発火する。 $t_4$ が発火すればジュースのみが、 $t_5$ が発火すればジュースと釣り銭90円が、 `juice'、`=Y10'のプレースに投入される。

例 5   図6(a)は生産システムのモデルである。 2種類の製品1、2がそれぞれ機械A、Bに加工されて完成する。 $p_a$、$p_b$ はそれぞれ、機械A、Bが加工中でなく、使用可能であることを表す。 $p_{is}$ $(i=1,2)$ は製品 $i$ の加工準備ができていることを示す。 $p_{ia}$、$p_{ib}$ $(i=1,2)$ はそれぞれ、 製品 $i$ が機械A、Bで加工中がであることを示す。 $p_{it}$ $(i=1,2)$ は製品 $i$ が機械Aのある場所から 機械Bのある場所へ運ばれていることを示す。 $p_{if}$ $(i=1,2)$ は製品 $i$ の加工が終了したことを示す。 $t_{ias}$、$t_{ibs}$ $(i=1,2)$ はそれぞれ、 製品 $i$ の機械A、Bによる加工を開始することを表し、 $t_{iaf}$、$t_{ibf}$ $(i=1,2)$ は加工の終了を表す。

図 6: 生産システムのモデル

ここで、機械Aと機械Bが離れた場所にあって、 搬送車で運ばなければならないものとする。 搬送車のモデルを(b)に示す。 $t_{its}$、$t_{itf}$ $(i=1,2)$ はそれぞれ、 製品 $i$ の搬送開始、終了を表す。 $p_{va}$、$p_{vb}$ はそれぞれ、搬送車が機械A、Bの場所にあることを表す。 $t_{mv}$ は搬送車が機械Bの場所からAの場所へ移動することを表す。

2つのプレース $p_{1t}$、$p_{2t}$ を搬送車のモデル(b)で置き換えることによって、 機械間の搬送を考慮したモデル(c)を得る。 このように、あるペトリネットモデルの1つあるいは複数のプレースやトランジションを 別のネットで置き換えることによって、より詳細なモデルを作ることができる。 逆に、あるペトリネットの一部をより簡単なネットで置き換えることで、 より抽象化されたモデルを得ることができる。

例 6   図7にプリンタへの文字列の出力のモデルを示す。 (a)はコンピュータのプリンタ制御プログラム、(b)はプリンタを表す。 コンピュータはプリンタのBUSY信号が偽(0)になるのを待って、データを送信する。 そして、データが有効であることを示すために、STROBE信号を送る。 STROBE信号は負論理なので、まず、信号を立ち下げ($1\rightarrow0$)、 所定の時間が経過した後、信号を立ち上げる($0\rightarrow1$)。

図 7: プリンタのモデル

プリンタはSTROBE信号の立ち下がりでデータを取り込み、BUSY信号を真(1)にする。 そして、印字処理を行い、その終了後、BUSY信号を偽にする。

(a)と(b)のネットに共通のプレース $\overline{\mbox{BUSY}}$、DATA と トランジション STROBE$\downarrow$ を それぞれ重ね合わせることによって、 コンピュータで制御されたプリンタのモデルを得る。 このように、複数のペトリネットのプレースやトランジションを重ね合わせて、 結合システムのモデルを作ることができる。

問題 3   図5のモデルを、50円硬貨も受け付けるように修正せよ。