ペトリネットおよび
LCペトリネットについて


ペトリネットの考え方

ペトリネットはドイツ人のC.A.Petriによって1962年に提案された概念である.この概念を一言でいうなら,「協調して仕事をするべき作業者が複数いたとき、それらの仕事の前後関係と、各作業者が仕事をいつ開始できるかなどを表わした図」となる。作業者という言葉を使ったが仕事をしうるものであればコンピュータであってもロボットであっても単なるソフトであってもよい。全体は抽象的に記述されるのでその対象は広い.

今上述の「協調して仕事をする作業者...」の例をあげよう.おみやげのなすの漬け物を梱包している作業所を例にとる.一人の作業者(A)はポリの袋に商品名を印刷している.もう一人(B)は印刷の終わった袋に5個の漬け物のなすを入れている.3人目の作業者(C)はその袋の口をシールして閉じている.これで出来上がりである(下図).

各作業者の前後には材料あるいは半完成品(または完成品)を置く場所(仮に物置き場と呼ぼう)がある.それらをp,q,r,s,tとしよう.多くの作業者が協調して仕事をしているときは多かれ少なかれそのようなスペースはあるものである.

矢印の下の数字は一度に動く物の数を表わす.例えば物置き場rから作業者Bへは一度に5個ずつの物(なす)が動く.

作業者達は一般には作業のスピードが異なっている.そのため中間の物置き場には半完成品がたまってしまったりあるいは無くなってしまったりする.もし自分の上流にある物置き場(一つとは限らない)に物が無くなってしまえば(あるいは必要数に満たなければ)その作業者は手を休めなくてはならない.例えば作業者Bは物置き場qに物が無くなってしまえば手を休めざるを得ない.あるいは物置き場rにある物が5個未満になったらやはり手を休めることになる.そして次に作業を開始できるのは物置き場qにすくなくとも1個の物が置かれ,物置き場rには少なくとも5個の物が置かれたときである.

このような事情を抽象化して表わしたのがペトリネットである (下図).

容易に想像できるように丸が物置き場を表わし四角が作業者を表わす.矢印は同じように物の流れの方向を表わす.また黒い小丸は材料や半完成品または完成品などの物を表わす.

ここでペトリネットに関する用語を紹介しよう.

  物置き場としての[丸]は  プレース(place),
  作業者としての[四角]は  トランジション(transition),
  物の流れを表わす[矢印]は アーク(arc),
  物を表わす[黒小丸]は   マークまたはトークン(mark,token)
  一度に流れる量を表わす、
   矢印の下の数字は    ウェイト(weight)

などである.なおウェイトは1のとき記入を省略されることもある.

またトランジションが作業を開始し1単位の仕事をすることを

(トランジションが)発火する    fire

という.

ペトリネットのプレースの中に書かれたトークンはトランジションの発火後にその数を変化させる.例えば上のペトリネットではプレースsに1個、プレースtに2個のトークンが入っているが、トランジションCが発火すると(この状態では発火可能である)その後にはそれぞれトークンの数がプレースsには1個減って0個、プレースtには一つ増えて3個になる.このようにペトリネットの状態は時々刻々変わってゆく.

LCペトリネット

ペトリネットの中の1個のトークンは,ただあるかないかの情報をもたらすに過ぎないが、もしこのトークンの中に情報が書き込めるとすると,更にペトリネットの適用範囲は広くなる.例えば a×b+c の計算ができる回路は次のようなペトリネットで表わせる.

プレースAには数aが書き込まれたトークンが置かれる.プレースBには数bが書き込まれたトークンが,そしてプレースCには数cが書き込まれたトークンが置かれる.記号×のトランジションでは文字どおり掛け算が行われ,結果をトークンに書き込みプレースDに送る.同様に記号+の中のトークンのトランジションでは,プレースD中のトークンとプレースC中のトークンを一つずつとってそれらに書かれた数をもとに加算が行われ,結果を新しいトークンに書き込みプレースEに送られる.3つのプレースA,B,Cにまた異なる数が書き込まれた新しいトークンがそれぞれに入れられると、またつぎの計算が行われる.このようにトークンに数が書き込めるという仮定をすることで計算のような仕事もペトリネットで記述でき、このことはプログラムや演算回路までペトリネットで記述できる可能性を示している.

トークンに書き込む数を色の種類を表わすと解釈すると、トークン一つ一つはある特定の色に塗られていると考えることもできる.というわけで、トークンに数が書き込めるペトリネットをカラーペトリネット(Colored Petri net)という.

この場合下流のプレースに送るトークンの色はあらかじめある規則で決められるとしておく.例えば上の例のように数としての掛け算や足し算で決まるとしておいてもよいし、あるいは上流のプレース中のトークンの色や数の組み合わせにたいし,下流に送るトークンの色を与える表を用意してもよい.

またトランジションの発火の条件も上流のプレースの中のトークンの色の組み合わせで指定することができる.例えば「上流のプレースの全てに赤のトークンがあったら発火せよ」といった規則を与える.あるいは「上流の全てのプレースに赤または白のトークンがあって赤の個数のほうが多かったら発火せよ」といった複雑なものでもよい.これらは発火規則(firing rule)と呼ばれ論理式などで表わせる.

更にペトリネットの適用範囲を広げるために,あるトランジションが発火した後、上流のプレース中のトークンを取り去らなくてもよいとする.これは回路などでデータが記憶回路に入っているようなとき、そのデータを使って演算が行われても使われたデータが消えるわけではない,ということがあるためである.つまり物とちがって情報は、使われても無くならない,という性質がある.情報処理にペトリネットを適用するためにはこのように、場合によっては上流のトークンが無くならない,と考えたほうがよい.

またトークンを除くか除かないかは、上流のトークンの色の組み合わせにも依存するとする.もし上流のプレースが1,2,3と番号付けてられたとする.このとき

のような表が考えられる.この表を見ると,あるトークンの上流に3つのプレースがあり,それらの中のトークンが全て赤か,一つだけ白で後は赤という組み合わせになったときこのトランジションは発火し,そのとき上流の赤のトークンだけを取り除く,という規則がわかる.すなわちこの表は上流にあるトークンの色(=数)の各組み合わせにたいし,発火後上流の発火に使ったトークンを取り除くか否かを書いたものである.このような表をicp(input clear place)という.実際にはこの表全体を記述しなくても「赤のときだけ取り除く」のようなルールあるいはこのルールを表わす論理式を記述すればよい.

同様にして下流のプレースへトークンを送るとき,選択的に下流のあるプレースだけに限ることもできる.これは上流のトークンの処理結果に応じトークンの行き先を変えるようなとき使われる.具体的には小包の仕分け作業(宛て先によって送り先を変える)をペトリネットで記述するようなときである.これもicpと同じように表や規則や論理式で記述できる.それはosp(output set place)といい、下流のトークンの置かれるプレースを指定するものである.

このように発火規則、icp、ospなどの概念を付け加えることになり、それらはみな論理式で記述できる規則であるからlogicalのLをとり

LCペトリネット (Logical Colored Petri net)とこの拡張されたペトリネットを呼ぶことにする.

LCペトリネットの例

コンピュータソフトはみなLCペトリネットで記述することができる.例えば下図左のようなフローチャートを考えよう.これは1から100までの数を順に加えて1+2+3+...+100を求めるものである.

これをLCペトリネットで表わすと上の右の図になる.条件分岐の所ではospの式に従ってトークンは行き先を変えることになる.トークンはこの図ではスタートを表わすプレースの所にあるが時間とともに下に降りてきてループの所を何回か回った後に終了を表わす一番下のプレースに入る.これで計算終了である.

各トークンでの

  発火条件は「上流のプレースの一つにトークンがあったとき」であり
  処理は   図中に示したものでトークンの色を変えるのみ,
  icpは 「トークンのあるプレースからのみ除く」,
  ospは  分岐のトークンでのものは図中に示されておりその他はただ下流のプレースに置く,

である.フローチャートはただ一箇所でしか計算をしないため,それを表わすペトリネット上を動くトークンはただ一つである.

近年コンピュータが行う処理は多くの割り込みなどがあり,フローチャートでは表現しきれなくなっている.そのようなときはたくさんのトークンがネット上を動きまわる.ペトリネット(LC)はシステムの仕様記述からシステムのシミュレーションにも用いられ更にプログラムの自動生成までできるため,システムの開発において強力な道具になる.


PDS User's Guide Section Links