ペトリネットの解析

挙動的解析

発火系列

ペトリネットのあるマーキング $m$ と トランジションの列 $w=t_{i_1}t_{i_2}\cdots t_{i_r}$ に対して、 $m$ から $w$ の各トランジションが順次発火可能であるとき、 すなわち、 $m[t_{i_1}\rangle m_1$, $m_1[t_{i_2}\rangle m_2$, $\ldots$, $m_{r-1}[t_{i_r}\rangle$ が成り立つとき、 $w$ は $m$ から可能な発火系列(legal firing sequence)であるという。 これを、$m[w\rangle$ と表す。その結果のマーキングが $m'$ であるとき、 $m[w\rangle m'$ と書く。 空列 $\varepsilon$ (トランジションを1つも含まない「列」)に対して、 $m[\varepsilon\rangle m$ であるものとする。

可達集合

ペトリネット $N$ の初期マーキング $m_0$ から遷移可能な マーキング全体の集合を可達集合(reachability set)といい、$R(N,\,m_0)$ と書く。 形式的には、 $R(N,\,m_0)=\{m\mid \exists w \in T^*;\ m_0[w\rangle m\}$. ただし、$T^*$ を空列も含むトランジションの列全体の集合とする。

例 7   図2のペトリネットの可達集合は、 $R(N,\,m_0)=\{[k+3\,2\,1\,1]^T$, $[k\,1\,2\,2]^T$, $[k\,0\,3\,3]^T$, $[k\,2\,0\,1]^T$, $[k\,1\,1\,2]^T$, $[k\,0\,2\,3]^T$, $[k\,1\,0\,2]^T$, $[k\,0\,1\,3]^T$ $\mid k=0,1,2,\ldots\}$ である(確かめてみよ)。

可達問題

ペトリネット $N$ と目的マーキング $m_f$ を与えたとき、 $m_0[w\rangle m_f$ となる発火系列 $w$ が存在するかどうかを 可達問題(reachability problem)という。 ペトリネットの制御としては、 「発火可能なトランジションの発火を許可または禁止する」 方法が一般的である。 可達問題はこの制御方法による可制御性と解釈することができる。

活性

マーキング $m$ から可達な任意のマーキング $m'$ に対して、 トランジション $t$ が発火可能なマーキング $m''$ が $m'$ から可達であるとき、 $t$ は $m$ で活性(live)であるという。 すべてのトランジションが初期マーキング $m_0$ で活性であるとき、 ペトリネット $N$ は活性であるという。 活性は定常動作の可能性に関係が深い。

有界性

自然数 $k$ に対して、 初期マーキングから可達な任意のマーキング $m$ で $m(p)\leq k$ が成り立つとき、 プレース $p$ は $k$-有界($k$-bounded)であるという。 1-有界であることを特に安全(safe)であるという。 任意の自然数 $G$ に対して $m(p)>G$ なるマーキング $m$ が可達であるとき、 プレース $p$ は非有界であるという。

すべてのプレースが $k$-有界であるとき、 ペトリネット $N$ が $k$-有界であるという。

実システムのモデルは有界でなければならないし、 とくに(2値)論理のモデルは安全でなければならない。

問題 4   図2のペトリネットについて、以下の問いに答えよ。

1. 初期マーキング $m_0$ から、 $m_f=[0\,0\,3\,3]^T$ は可達であるか。 もし、可達であれば、 $m_0[w\rangle m_f$ となる発火系列 $w$ の1つを求めよ。

2. 各トランジションの活性を判定せよ。

3. 各プレースの有界性を判定せよ。

構造的解析

接続行列

ペトリネット $N$ の入出力接続行列(input/output incidence matrix) $A^-=\{a^-_{ij}\}$、 $A^+=\{a^+_{ij}\}$ は 以下に定義される $\vert P\vert\times\vert T\vert$ 行列である。

$$a^-_{ij}=\left\{ \begin{array}{ll} W((p_i,t_j)) & \mbox{if }... ...if }(t_j,p_i)\in F \\ 0 & \mbox{otherwise} \end{array}\right.$$

また、$A=A^+-A^-$ を接続行列という。

例 8   図2のペトリネットの接続行列は以下のとおりである。

$$A^-= \left[ \begin{array}{rrr} 3 & 0 & 0 \\ 1 & 0 & 0 \\ ... ...& 1 & 0 \\ 1 & -2 & 0 \\ 1 & -1 & 0 \\ \end{array}\right]$$

$A$ には $p_4$ と $t_3$ の間の往復アーク(セルフループ, self-loop)が 表現されていないことに注意する。

$u_j=[0\,\cdots\,0\,\stackrel{(j)}{1}\,0\,\cdots\,0]^T$ を $t_j$ に対する 発火ベクトルという。 マーキング $m$ で $t_j$ が発火可能であることは、$A^-u_j\leq m$ と表される。 $m[t_j\rangle m'$ であるとき、$m'=m+Au_j$ である。 マーキング $m$ から発火可能な 発火系列 $w=t_{i_1}t_{i_2}\cdots t_{i_r}$ に対して、 $x=\displaystyle\mathop{\textstyle\sum}_{j=1}^{r} u_{i_j}$ とする。 $w$ の発火の結果のマーキングを $m'$ とすれば、 $m'=m+Ax$ である。$x$ を $w$ の発火回数ベクトル(firing count vector)という。

問題 5   方程式 $m_f=m_0+Ax$ を用いれば、 可達問題は容易に解くことができそうであるが、実際にはそうではない。 その理由として、どんなことが考えられるか。

問題 6   図8のペトリネットの 入出力接続行列 $A^-$, $A^+$、および、接続行列 $A$ を求めよ。 また、(入出力)接続行列を用いて マーキング $m_0=[0\,0\,1\,1]^T$ から、 トランジション $t_1$ が発火可能であることを示し、 $w=t_1t_4$ の発火の結果のマーキングを求めよ。

図 8: ペトリネット

Tインバリアント

あるマーキング $m$ から発火可能な 空列でない発火系列 $w$ の発火の結果のマーキングがふたたび $m$ であるとする。 $w$ の発火回数ベクトルを $x$ とすれば、 $m=m+Ax$ より、$Ax=0$ が成り立つ。 方程式 $Ax=0$ の非負整数解 $x$ をTインバリアント(T-invariant)という。

Sインバリアント

各プレース $p_j$ に非負整数の重み $y_j$ を考える。 $y^Tm$ はトークンの重み付き和である。 もし、$y^TA=0$ が成り立つならば、 $m_0$ から可達な任意のマーキング $m$ に対して、 $y^Tm=y^T(m_0+Ax)=y^Tm_0+(y^TA)x=y^Tm_0$ より、 重み付き和は不変である。 方程式 $A^Ty=0$ の非負整数解 $y$ をSインバリアント(S-invariant)あるいは、 Pインバリアントという。

問題 7   図8のペトリネットのTインバリアント、Sインバリアントを求めよ。