JP3943909B2 - Simulation device based on extended Petri net - Google Patents

Description

【０００８】
上記表１に示すメモリを確保して、シミュレーション時刻を初期時刻に設定し、トークン組み合わせのリストを空にし、作成されたペトリネットからプレースリストとトランジションリストとを作成する。
また、各プレースと各トランジションに対して、それぞれ表２、表３に示すようなメモリを確保し、作成されたペトリネットに基づき初期化する。
【０００９】
【表２】

【００１０】
【表３】

【００１１】
ただし、上記表２に示すメモリのトークンリストは空に初期化する。
初期マーキング処理４０２では、全プレースに対して設定されているトークンを生成し、上記表２に示すメモリのトークンリストに追加する。
【００１２】
発火可能トランジション検索処理４０３の処理を示すフローチャートを図５に示す。まず、入力アーク処理５０１において、トランジションの入力アークに設定されているカラー名（トークンの種別を表す名称）を持つトークンを対応する入力プレースから探し、対応する入力トークン変数とする。このトークンを発火可能トークンと呼ぶ。
【００１３】
全ての入力アークにおいて発火可能トークンが存在していれば（５０２）、発火ルール処理５０３において、出力アークに設定されているカラー名を持つトークンを作成して出力トークン変数とし、トランジション毎に設定されている発火ルールを実行する。この際、“０”以外の値が返された（returnされた）ときには（５０４）、発火可能と判断し、トークン組み合わせリスト登録処理５０５において、表４に示すトークン組み合わせデータを発火処理手段が管理する上記表１に示したメモリに登録する。この際、優先順位を示す変数priorityに値が設定されている時には、表４の優先順位にそのまま書き込み、値が設定されていないときには、乱数により適当な値を決めて、それを表４の優先順位に書き込む。
【００１４】
【表４】

【００１５】
そして、次組み合わせ作成処理５０６において、今までに処理していない入力トークンの組み合わせを求め、全ての入力トークンの組み合わせを処理していなかった場合には（５０７）、再度入力アーク処理５０１に戻り、全ての入力トークンの組み合わせが処理されるまで上記処理５０１〜５０６を繰り返す。
【００１６】
【発明が解決しようとする課題】
さて、図６に示すように１台の無人搬送台車（以下、「ＡＧＶ」と記載する。）により製品を搬送する物流システムを拡張ペトリネットで記述することを考える。図６において、スキッドskid１〜skid４は荷積み・荷降し場であり、ＡＧＶの走行路はゾーンzone１〜zone５に分割管理されている。特開平１０−３３４０７５号公報に記載の拡張ペトリネットで図６に示す物流システムを記述すると図７に示すようになる。
【００１７】
ここで、ステートプレースstateは、本来１つであるが、アークの重なりを防ぐために別々に４つ記載している。また、矢印が両側に付いているアークは、接続しているトランジションが発火しても、トークンが入力プレースから削除されないことを意味している（矢印が片側だけ付いているアークは、単純ペトリネットと同様に、トランジションが発火したら、トークンが入力プレースから削除される）。トークンは、ＡＧＶトークンとステートトークン（以下、「Ｓｔａｔｅトークン」と記載する。）との２種類が存在し、その属性を表５と表６にそれぞれ示す。
【００１８】
【表５】

【００１９】
【表６】

【００２０】
図７において、各ゾーンプレースzone１〜zone５とスキッドプレースskid１〜skid４にはＡＧＶトークンのみ入り、ステートプレースstateにはＳｔａｔｅトークンが入る。各トランジションの詳細な発火ルールは省略するが、例えば、トランジションmove３であれば、ＡＧＶの行先がスキッドプレースskid２のみ発火可能となるように発火ルールを設定する必要がある。
【００２１】
図７に示すトランジションload１の入力アークのみに発火可能なトークンが斜体で記載してある。すなわち、トランジションload１の発火には、スキッドプレースskid１に１つのＡＧＶトークンと、ステートプレースstateに１つのＳｔａｔｅトークンとを必要とする。トランジションload２、load３、load４の入力アークには発火可能なトークンを記載していないが、トランジションの発火には同様に、１つのＡＧＶトークンと１つのＳｔａｔｅトークンとを必要とする。
【００２２】
次に、特開平１０−３３４０７５号公報に記載の拡張ペトリネットにおける発火処理手段の問題点を説明する。当該発火処理手段では、図５に示した入力アーク処理５０１において、全てのトランジションの全ての入力プレースに発火可能なトークンが存在するか否かを調べている。すなわち、全てのトランジションに対して、発火可能性の判断を行う必要がある。例えば、図７に示す例では、トランジションload１〜load４、unload１〜unload４、move１〜move８の計１６個のトランジションに対して、発火可能性を判断する必要がある。図７は非常に単純なケースであるが、大規模なケースになると、かなりの計算時間を要するという欠点がある。
【００２３】
そこで、本発明は、上記の欠点を解消し、少ない計算時間でシミュレーション可能とする手段を提供することを目的としている。
【００２４】
【課題を解決するための手段】
本発明の拡張ペトリネットに基づくシミュレーション装置は、離散事象システムをシミュレーションするためのコンピュータシステムを用いた拡張ペトリネットに基づくシミュレーション装置であって、シミュレーションに必要な情報および命令を入力する入力手段と、上記入力手段に対するユーザの操作に基づいた上記入力手段からの入力に従って、プレース、トランジション、およびアークを入力して離散事象システムの拡張ペトリネットモデルを作成するモデル作成手段と、上記モデル作成手段により作成された拡張ペトリネットモデルを出力装置に表示する表示手段と、上記モデル作成手段により作成された拡張ペトリネットモデルを記録装置に記録する記録手段と、上記記録装置に記録された拡張ペトリネットモデルのシミュレーションを実行するシミュレーション計算手段と、上記シミュレーション計算手段により実行したシミュレーションの実行結果を上記出力装置および記録装置の少なくとも一方に出力する出力手段と、を備え、上記出力装置はディスプレイを含み、上記記録装置はメモリおよびディスクを含み、上記モデル作成手段は、さらに、トークン毎に上記入力手段を介してユーザからトークン変数名および属性名の指定を受け属性を定義するとともに、定義されたトークンの属性を用いてトランジションの発火ルールを設定し、かつ、トランジション発火時に、入力プレースに存在するトークンを削除するか否かを、当該入力プレースに接続するアークの種類に応じてプレース毎に設定する手段を有し、上記シミュレーション計算手段は、上記トークンを削除する設定を行っている入力プレースに接続するアークと、上記トークンを削除しない設定を行っている入力プレースに接続するアークとが共に入力アークとして１つのトランジションに接続されているとき、アークを介して当該トランジションに接続された上記トークンを削除する設定を行っている入力プレースの少なくとも１つに発火可能なトークンが存在しない場合には、当該トランジションと上記トークンを削除しない設定を行っている入力プレースとの関連を切断し、アークを介して当該トランジションに接続された上記トークンを削除する設定を行っているすべての入力プレースに発火可能なトークンが存在する場合には、当該トランジションと上記トークンを削除しない設定を行っている入力プレースとの関連を接続する自動切断接続手段を有し、シミュレーション進行時には、通常のトランジション発火処理に加えて、上記自動切断接続手段により上記トランジションと上記入力プレースとの関連を切断あるいは接続する切断・接続処理を実行し、発火可能なトランジションがなくなるまで当該発火処理と当該切断・接続処理とを繰り返してシミュレーションの実行結果を求めることを特徴とする。
【００２６】
【発明の実施の形態】
以下、本発明の一実施形態を図面に基づいて説明する。
本発明の実施形態の一例を図１に示す。なお、図１は、本発明を実施する際に必要となる装置、機能のみを記載しており、プリンターやテープドライブなどの周辺装置を付加しても、実施形態としての違いは無い。
【００２７】
図１において、コンピュータ本体１０１は、ＣＰＵ１０６とメモリ１０７等を有する汎用コンピュータであり、本実施形態では本発明はメモリ１０７上に記録されたソフトウェアとして実施される。本発明のシミュレーション装置は、キーボード１０３やポインティングデバイス１０４を用いて、拡張ペトリネット形式でシミュレーションモデルをモデル作成手段１１６に入力する。
【００２８】
モデル作成手段１１６は、ペトリネット図編集手段１１７によりプレース・トランジション・アークを入力してペトリネット図を作成し、初期マーキング設定手段１２１によりシミュレーション開始時のトークンの配置を設定する。さらに、モデル作成手段１１６は、発火ルール設定手段１１８によりトランジションの発火ルールを設定し、発火優先順位設定手段１１０により発火の優先順位を設定する。
【００２９】
作成された拡張ペトリネットは、モデル記録手段１２０によりメモリ１０７内に記録され、モデル表示手段１１９によりディスプレイ１０２に表示される。シミュレーション計算手段１１４は、メモリ１０７に記録された拡張ペトリネットに基づきシミュレーションを実行し、その実行結果をメモリ１０７やディスク１０５に記録するとともに、トークンの動き回る様子をディスプレイ１０２に表示する。
【００３０】
シミュレーション計算手段１１４において、図中の「●」は複数の関連があることを意味している。例えば、発火処理手段１１１とトランジション１０８との間におけるトランジションの「●」は、複数のトランジションが存在し、発火処理手段１１１は複数のトランジションと関連があることを示している。
【００３１】
アーク関連自動切断・接続手段１２２は、現在のトークン配置からトランジションと入力プレースとの関連を切断・接続する。具体的には、アーク関連自動切断・接続手段１２２は、全てのトークン１１３からトークンが存在する全てのプレース１０９を求め、さらに、それらのプレースを入力プレースとする全てのトランジション１０８を求める。それらの各トランジション１０８に対し、発火ルール設定手段１１８で設定された発火ルールと、発火優先順位設定手段１１０で設定された発火の優先順位とに基づいて所定の処理を行い、全ての発火可能トークンの組み合わせ１１２を作成する。発火処理手段１１１は、計算により得られた発火優先順位の高い順番にトランジションを発火させ、入力プレースからトークンを削除し、出力プレースにトークンを送る。上述した処理を繰り返し行うことにより、拡張ペトリネットのシミュレーションを行う。
【００３２】
以下、図面を参照して本発明の実施例について詳細に説明する。
なお、以下では、図６に示したＡＧＶを用いて製品を搬送する物流システムと、図６の物流システムを拡張ペトリネットで記述した図７とを一例として説明する。
【００３３】
本発明による拡張ペトリネットに基づくシミュレーション装置を実行（起動）すると、図８に示すようなウィンドウ８０１がディスプレイ１０２に表示される。ウィンドウ８０１は、ウィンドウ８０１の移動や拡大縮小を行うためのタイトルバー８０２と、さまざまな操作を行うためのメニューボタンを有するメニューバー８０３と、ペトリネットを作成したり表示したりするためのキャンバス８０４と、キャンバス８０４を上下左右にスクロールさせるためのスクロールバー８１４と、ペトリネット部品を選択するための部品リスト８０５とから構成される。
【００３４】
メニューバー８０３は、ファイルの入出力や印刷等を行うための「Ｆｉｌｅ」メニューボタン８０６と、ブロックやアークの移動およびカット＆ペースト（切り取って貼り付ける操作）等を行うための「Ｅｄｉｔ」メニューボタン８０７と、シミュレーションの実行開始や停止、再開等を行うための「Ｓｉｍｕｌａｔｉｏｎ」メニューボタン８０８と、トークンの属性定義を行うための「Ｃｏｌｏｒ」メニューボタン８０９とから構成されている。
【００３５】
部品リスト８０５は、ペトリネット部品として、プレース部品８１０と、トランジション部品８１１と、単方向アーク部品８１２と、双方向アーク部品８１３とから構成されている。ここで、あるトランジションが発火した際、単方向アーク部品８１２で接続されている入力プレースからはトークンが削除され、双方向アーク部品８１３で接続されている入力プレースからはトークンは削除されない。
【００３６】
ペトリネットを作成するときには、部品リスト８０５からペトリネット部品を選択し、選択した状態でキャンバス８０４に移動させる、つまりキャンバス８０４にドラッグ＆ドロップすることにより行う。部品の移動およびカット＆ペーストなどは、市販のドローツールのような操作方法で行うことができる。このような操作を行うことにより、図７に示すようなペトリネットをキャンバス８０４上に作成することができる。
【００３７】
次に、トークンの属性を定義（以下、「カラー定義」とも呼ぶ。）する方法について説明する。
図８に示す「Ｃｏｌｏｒ」メニューボタン８０９を選択すると、図９に示すような空の（まったく何も入力されていない）カラー定義ウィンドウが表示される。このカラー定義ウィンドウ内には、任意の文字を入力することができ、ユーザは次の書式でトークンの属性を定義する。
カラー名(属性１の型 属性１の名前，属性２の型 属性２の名前，．．．);
【００３８】
ここで、カラー名とは異なる種類のトークン同士を識別するための名前である（例えば、図７においては“ＡＧＶ”または“Ｓｔａｔｅ”）。図７に示すペトリネットの場合には、ＡＧＶトークンとＳｔａｔｅトークンとは、表５・表６の属性をそれぞれ持つので、カラー定義ウィンドウに
AGV(String to);
State(String cur[8], String next[8]);
のように設定する。
【００３９】
ここで、「String」は、文字列型（データ）を表す属性である。「to」は、ＡＧＶが行先（移動中）もしくは現在位置（停止中）を表す属性である。「cur[8]」は、各製品の搬送元（搬送前）もしくは搬送先（搬送中および搬送後）を表す属性、「next[8]」は、各製品の搬送先を表す属性である。製品は全部で８つあり、ｉ番目の製品の搬送元（搬送中および搬送後は搬送先）は、Ｓｔａｔｅトークンの「cur[i]」、搬送先はＳｔａｔｅトークンの「next[i]」で表される。
【００４０】
シミュレーションを実行する際には、初期マーキング（シミュレーション開始時のトークン配置）を設定する必要がある。初期マーキングは、プレース毎に行う。キャンバス８０４上に表示された各プレース部品をダブルクリックすると、図１０に示すような空のプレース定義ウィンドウが表示される。このプレース定義ウィンドウ内には、任意の文字を入力することができ、ユーザは次の書式でそのプレースの初期マーキングを指定することができる。
個数*カラー名(属性値１，属性値２，．．．．);
【００４１】
図７に示すペトリネットの場合には、初期マーキングは、スキッドプレースskid１にＡＧＶトークン、ステートプレースstateにＳｔａｔｅトークンであるため、スキッドプレースskid１のプレース定義ウィンドウには、以下の初期マーキングを設定するものとする。
1*AGV("skid1");
また、ステートプレースstate（図７に示すペトリネットにおいては、見掛け上４つあるが実体は１つである）のプレース定義ウィンドウには、以下の初期マーキングを設定するものとする。
1*State(["skid1", "skid1", "skid2", "skid2", "skid3", "skid3", "skid4", "skid4"],
["skid2", "skid3", "skid3", "skid4", "skid4", "skid1", "skid2", "skid3"]);
【００４２】
ここで、この例では、図６に示すように製品は８つあり、それぞれ搬送先が指定されている。例えば、製品１は搬送元がスキッドプレースskid１で、搬送先がスキッドプレースskid２である。
【００４３】
最後に、トランジションの発火ルールを設定する。各トランジションの発火ルールの設定は、アーク定義とトランジション定義とにより行う。
アーク定義とは、各トランジションの入力側に接続されているアークと出力側に接続されているアークとに、そのトランジションで発火する入出力トークンの個数およびカラー名と、トークンを参照するためのトークン変数名とを設定するものである。キャンバス８０４上に表示された設定したいアークをダブルクリックすると、図１１に示すような空のアーク定義ウィンドウが表示され、アーク定義ウィンドウ内に、以下のような書式で、接続されているトランジションで発火するトークンの個数、カラー名およびトークン変数名を指定する。
個数*カラー名 トークン変数名
【００４４】
ここで、トークン変数名とは、発火ルールを記述する際に複数のトークンを区別するための識別名である。特に、入力アークに設定されたトークン変数を「入力トークン変数」、出力アークに設定されたトークン変数を「出力トークン変数」と呼ぶこととする。
【００４５】
例えば、図７に示すトランジションload１が発火するには、スキッドプレースskid１にＡＧＶトークンが１つ存在し、ステートプレースstateにＳｔａｔｅトークンが１つ存在する必要があるので、トランジションload１とスキッドプレースskid１とを結ぶアークのアーク定義ウィンドウに、
1*AGV agv1
と設定する。同様に、トランジションload１とステートプレースstateとを結ぶアークのアーク定義ウィンドウに、
1*State state
と設定する。
【００４６】
また、トランジションload１が発火した際には、ゾーンプレースzone１にはＡＧＶトークンが発生する必要があるので、トランジションload１とゾーンプレースzone１とを結ぶアークのアーク定義ウィンドウに、
1*AGV agv2
と設定する。このように、ＡＧＶトークンは入力側と出力側とで異なるトークン変数名を付けて区別している。
【００４７】
トランジション定義により、トランジションの発火ルールの詳細を記述できる。また、トランジション定義は発火優先順位設定手段１１０も同時に兼ねている。キャンバス８０４上に表示された各トランジションをダブルクリックすると、図１２に示すようなトランジション定義ウィンドウが表示され、トランジション定義ウィンドウ内に、文字入力で任意のトランジションの発火ルールを記述することができる。
【００４８】
トランジション定義ではC++言語と同じ書式を利用することができ、例えば、戻り値として“０”が返される（“０”の値がreturnされる）と、発火条件が成立しないことを意味し、戻り値として“０”以外が返される（“０”以外の値がreturnされる）と、発火条件が成立したことを意味する。また、特別な変数として「priority」があり、「priority」に本発明に係わる発火優先順位を設定することができる。ただし、「priority」に優先順位を代入（設定）しなくても良く、この場合には暗黙的に乱数が代入されたとみなす。
【００４９】
図７に示すペトリネットの場合には、トランジションload１のトランジション定義ウィンドウには、

と記述する。このように、トークンの属性は
トークン変数名．属性名
の形式でアクセスすることができる。
【００５０】
完成したペトリネットを図１３に示す。ここでは、図７に示すような簡単なペトリネットに関して説明したが、複雑なペトリネットでも同様の操作を行うことにより作成することができる。
【００５１】
次に、発火処理手段１１１について説明する。
発火処理手段１１１は、作成されたペトリネットを基にシミュレーションを実行してトークンの生成および消滅を行う。発火処理手段１１１の動作を示すフローチャートを図１４に示す。
メモリ初期化処理４０１では、シミュレーションに必要なメモリの確保と初期化を行う。発火処理手段１１１が管理するメモリを表７に示す。
【００５２】
【表７】

【００５３】
上記表７に示すメモリは、上記表１に示した発火処理手段管理メモリと比べて、トークンのリスト（以下、「トークンリスト」と呼ぶ。）が追加されている。上記表７に示すメモリを確保して、シミュレーション時刻を初期時刻に設定し、トークン組み合わせリストとトークンリストとをそれぞれ空にし、作成されたペトリネットからプレースリストとトランジションリストとを作成する。
また、各プレースと各トランジションに対して、上記表２に示すプレース管理メモリ、上記表３に示すトランジション管理メモリ、および表８に示すトークン管理メモリをそれぞれ確保し、作成されたペトリネットに基づき初期化する。
【００５４】
【表８】

【００５５】
ただし、表２に示すプレース管理メモリ内のトークンリストは空に初期化する。また、表８に示すトークン管理メモリは、トークンが存在するプレースをトークン毎に記述している。
上記図７に示す例の場合には、発火処理手段１１１管理メモリは表９に示すようになり、プレース管理メモリは表１０に示すようになり、トランジション管理メモリは表１１に示すようになる。
【００５６】
【表９】

【００５７】
【表１０】

【００５８】
【表１１】

【００５９】
初期マーキング処理４０２では、全プレースに対してプレース定義ウィンドウに設定されたトークン個数、カラー名および属性に基づいてトークンを生成し、上記表７に示した発火処理手段１１１管理メモリ内のトークンリストと、上記表２に示したプレース管理メモリ内のトークンリストに追加する。また、各トークンが存在するプレースを表８に示したトークン管理メモリに追加する。
上記図７に示す例では、上記表２に示したプレース管理メモリは表１２に示すようになり、上記表８に示したトークン管理メモリは表１３に示すようになる。
【００６０】
【表１２】

【００６１】
【表１３】

【００６２】
このように、表１０に示すプレース管理メモリに比べて、表１２に示すプレース管理メモリでは、ステートプレースstateにＳｔａｔｅトークン、スキッドプレースskid１にＡＧＶトークンが追加されている。
【００６３】
アーク関連自動切断・接続処理１４０１では、トークンが存在するプレースを入力プレースとするトランジションが、双方向アーク部品８１３で接続されているときには、そのトランジションの他のアークを調べ、単方向アーク部品８１２でプレースと接続されているときには、そのプレースにトークンがなければ、双方向アーク部品８１３で接続されているプレースのプレース管理メモリ（表２）の出力トランジションリストから、そのトランジションを削除する。
例えば、図７に示す例の場合には、プレース管理メモリは表１２から表１４に示すように変化する。
【００６４】
【表１４】

【００６５】
このように、ステートプレースstateの出力トランジションから、トランジションload２、load３およびload４が削除されている。すなわち、ステートプレースstateとトランジションload２〜load４との関連が削除されている。
【００６６】
発火可能トランジション検索処理４０３は、図１５に示すフローチャートに従って実施される。
まず、処理１５０１では、トークンが存在するプレースを入力プレースとするトランジション（以下、「発火可能性を調べるトランジション」と記載する。）を１つ選択する。本実施例の場合、トークン管理メモリは表１３に示すようになっているため、トークンが存在するプレースは、スキッドプレースskid１とステートプレースstateとの２つであることがわかる。また、プレース管理メモリは表１４に示すようになっており、スキッドプレースskid１とステートプレースstateとの出力トランジションには共にトランジションload１が設定されているので、発火可能性を調べるトランジションはトランジションload１のみになる。
【００６７】
ここで、もし、アーク関連自動切断・接続処理１４０１を用いていない場合には、プレース管理メモリは表１２に示されるままである。したがって、ステートプレースstateに関連する出力トランジションは、トランジションload１、load２、load３、およびload４であり、スキッドプレースskid１に関連する出力トランジションはトランジションload１であるため、発火可能性を調べるトランジションはトランジションload１、load２、load３、およびload４の４つとなってしまう。
【００６８】
次に、処理１５０２では、処理１５０１にて選択された発火可能性を調べるトランジションに対して、トランジションの入力アークのアーク定義ウィンドウに記述されているカラー名を持つトークンを対応する入力プレースから探し、対応する入力トークン変数とする。このトークンを発火可能トークンと呼ぶ。
【００６９】
全ての入力アークにおいて発火可能トークンが存在していれば（１５０３）、発火ルール処理５０３において、出力アークのアーク定義ウィンドウに記述されているカラー名を持つトークンを作成して出力トークン変数とし、トランジション定義ウィンドウに記述されている発火ルールを実行する。この際、戻り値として“０”以外が返されたときには（５０４）、発火可能と判断し、トークン組み合わせリスト登録処理５０５において、表４に示すトークン組み合わせデータを発火処理手段１１１が管理する上記表７に示すトークン組み合わせリストに登録する。この際、優先順位を示す変数priorityに値が設定されているときには、表４の優先順位にそのまま書き込み、値が設定されていないときには、乱数により適当な値を決めて、それを表４の優先順位に書き込む。
【００７０】
複数のトークンが入力プレースに存在する場合には、別のトークンの組み合わせも存在するため、次組み合わせ作成処理５０６にて、次のトークンの組み合わせを求め、処理１５０２に戻り上述した処理と同様の処理を行う。
【００７１】
１つの発火可能性を調べるトランジションに対して、全てのトークンの組み合わせが得られた場合には（５０７）、発火可能性を調べるトランジションが残っているか否かを調べる。その結果、発火可能性を調べるトランジションがある場合には、処理１５０１に戻り、発火可能性を調べるトランジションがなくなるまで、上述した処理と同様の処理を繰り返す。
【００７２】
例えば、図７に示すペトリネットの場合には、トランジションload１が発火可能となり、表１５に示すようなトークン組み合わせが、表７に示す発火処理手段１１１管理メモリ内のトークン組み合わせリストに登録されることになる。
【００７３】
【表１５】

【００７４】
ここで、図７に示す例では、優先順位が指定されていないため、乱数で優先順位が選ばれる。したがって、乱数系列によっては、上記表１５に示すようになるとは限らない。
図１４に戻り、トークン組み合わせ並べ替え処理４０４では、上記表１５のトークン組み合わせリストを優先順位が高い順番（降順）に並べ替える。上記表１５を並べ替えると表１６に示すようになる。
【００７５】
【表１６】

【００７６】
マーキング変更処理４０５では、トークン組み合わせ並べ替え処理４０４により優先順位が高い順に並べ替えられたトークン組み合わせリストの先頭から順番に、リストに登録されているトランジションの入力プレースから入力トークンを削除して、出力プレースへ出力トークンを発生させる。入力プレースはトークンリストから削除すべきトークンを検索して、そのトークンをトークンリストから抜き出し、使用していたメモリを解放する。出力プレースでは新たに送られたトークンをトークンリストに登録する。
【００７７】
トークンを削除する際、トークン組み合わせリストを調べ、その結果、削除するトークンがそのリストに登録されているときには、その要素をリストからも削除する。さらに、表７に示す発火処理手段１１１管理メモリ内のトークンリストの更新も同時に行う。このような処理をトークン組み合わせリストが空になるまで繰り返すことにより、マーキングの変更を行う。
【００７８】
例えば、表１６に示すトークン組み合わせリストの最初の行を処理する。つまり、トランジションload１が発火して、ＡＧＶ（"skid1"）がスキッドプレースskid１から削除され、ＡＧＶ（"skid3"）がゾーンプレースzone１に出力される。また、Ｓｔａｔｅトークンの属性は、以下のように変化する。ＡＧＶが製品２を搬送してスキッドプレースskid３へと移動することになったため、cur[2]が、“skid1”から“skid3”に変わる。
State(["skid1", "skid3", "skid2", "skid2", "skid3", "skid3", "skid4", "skid4"],
["skid2", "skid3", "skid3", "skid4", "skid4", "skid1", "skid2", "skid3"]);
【００７９】
ＡＧＶトークンがスキッドプレースskid１からゾーンプレースzone１に移ったことにより、表１６に示すトークン組み合わせリストは空になる。また、表１４に示すプレース管理メモリは、表１７に示すようになる。表１４に示したプレース管理メモリと比較すると、ＡＧＶトークンがスキッドプレースskid１からゾーンプレースzone１に移っている。
【００８０】
【表１７】

【００８１】
また、表１３に示したトークン管理メモリは、表１８に示すようになる。
【００８２】
【表１８】

【００８３】
マスキング変更処理４０５を行った後、再度、アーク関連自動切断・接続処理１４０１に戻り、上述した処理と同じ処理を行う。上述した例では、トランジションload１の入力プレースであるスキッドプレースskid１にトークンがなくなったため、自動的にステートプレースstateとトランジションload１との関連が切断され、表１７に示すプレース管理メモリは表１９に示すようになる。このように、ステートプレースstateの出力トランジションは空となる。
【００８４】
【表１９】

【００８５】
以降、同様の処理を繰り返し、発火可能トランジションがなくなるまで繰り返す。
【００８６】
シミュレーションの途中で、ＡＧＶがスキッドプレースskid３に到着すると、アーク関連自動切断・接続処理１４０１により、トークンが存在するプレースを入力プレースとするトランジションが、双方向アーク部品８１３で接続されているときには、そのトランジションの他のアークを調べ、単方向アーク部品８１２でプレースと接続されているときには、そのプレースに発火可能トークンがあれば、双方向アーク部品８１３で接続されているプレースのプレース管理メモリ（表２）の出力トランジションリストに、そのトランジションを登録する。図７に示す例では、ＡＧＶがスキッドプレースskid３に到着した後のプレース管理メモリは表２０に示すようになる。
【００８７】
【表２０】

【００８８】
表２０においては、ステートプレースstateとトランジションload３との関連が接続されている。この場合、発火可能トランジション検索処理４０３で調べるトランジションは、トランジションload３のみとなる。
【００８９】
以上説明したペトリネットでは時間の概念は存在せず、新たに生成されたトークンはすぐに発火可能となる。なお、時間の概念を導入することも可能であり、トークンが生成されてからユーザが指定したある時間後に発火可能となるような、発火遅延時間を持つ拡張ペトリネットとすることも容易にできる。例えば、ある時刻で発火可能なトランジションがなくなると、発火不可となっているトークンが発火可能に変わる時刻の中で、最も小さい時刻までシミュレーション時刻を進め（シミュレーション時刻更新処理４０６）、上記処理を繰り返し行い、最終的に終了時刻まで行えば良い。
【００９０】
【発明の効果】
以上、説明したように、本発明によれば、シミュレーションにて発火可能性を判断する際、トークンがいずれの配置であったとしても、発火可能トランジションを適切に１つだけ選択し、１つのトランジションの発火可能性を判断するだけで済むので、少ない計算時間でシミュレーションを行うことができる。例えば、図７に示す実施例の場合には、従来においては、発火可能性を判断するために調べるトランジションは、トランジションload１〜load４、unload１〜unload４、move１〜move８の１６個となるが、本発明では、１つのトランジションで済むので、計算時間を短縮することができる。特に、大規模なペトリネットになるほど、従来と比較して高い効果を得ることができる。
【図面の簡単な説明】
【図１】本発明による拡張ペトリネットに基づくシミュレーション装置のシステム構成例を示すブロック図である。
【図２】単純ペトリネット（発火前）の一例を示す図である。
【図３】単純ペトリネット（発火後）の一例を示す図である。
【図４】従来の発火処理手段の動作を示すフローチャートである。
【図５】従来の発火可能トランジション検索処理を示すフローチャートである。
【図６】無人搬送台車による物流システムの一例を示す図である。
【図７】図６に示した物流システムの拡張ペトリネットを示す図である。
【図８】本発明による拡張ペトリネットに基づくシミュレーション装置実行直後に表示されるウィンドウを示す図である。
【図９】カラー定義ウィンドウを示す図である。
【図１０】プレース定義ウィンドウを示す図である。
【図１１】アーク定義ウィンドウを示す図である。
【図１２】トランジション定義ウィンドウを示す図である。
【図１３】本発明によるシミュレーション装置で作成した拡張ペトリネットを示す図である。
【図１４】図１に示した発火処理手段１１１の動作を示すフローチャートである。
【図１５】図１４に示す発火可能トランジション検索処理を示すフローチャートである。
【符号の説明】
１０１ コンピュータ本体
１０２ ディスプレイ
１０３ キーボード
１０４ ポインティングデバイス
１０５ ディスク
１０６ ＣＰＵ
１０７ メモリ
１０８ トランジション
１０９ プレース
１１０ 発火優先順位設定手段
１１１ 発火処理手段
１１２ 発火トークン組み合わせ
１１３ トークン
１１４ シミュレーション計算手段
１１５ トークン属性
１１６ モデル作成手段
１１７ ペトリネット図編集手段
１１８ 発火ルール設定手段
１１９ モデル表示手段
１２０ モデル記録手段
１２１ 初期マーキング設定手段
１２２ アーク関連自動切断・接続手段
４０１ メモリ初期化処理
４０２ 初期マーキング処理
４０３ 発火可能トランジション検索処理
４０４ トークン組み合わせ並べ替え処理
４０５ マーキング変更処理
４０６ シミュレーション時刻更新処理
５０１ 入力アーク処理
５０３ 発火ルール処理
５０５ トークン組み合わせリスト登録処理
５０６ 次組み合わせ作成処理
８０１ 拡張ペトリネットを作成・実行するウィンドウ
８０２ タイトルバー
８０３ メニューバー
８０４ キャンバス
８０５ 部品リスト
８０６ 「Ｆｉｌｅ」メニューボタン
８０７ 「Ｅｄｉｔ」メニューボタン
８０８ 「Ｓｉｍｕｌａｔｉｏｎ」メニューボタン
８０９ 「Ｃｏｌｏｒ」メニューボタン
８１０ プレース部品
８１１ トランジション部品
８１２ 単方向アーク部品
８１３ 双方向アーク部品
８１４ スクロールバー
１３０１ カラー定義ウィンドウ
１３０２ スキッドプレースskid１のプレース定義ウィンドウ
１３０３ ステートプレースstateのプレース定義ウィンドウ
１３０４ ステートプレースstateとトランジションload１とを結ぶアークのアーク定義ウィンドウ
１３０５ スキッドプレースskid１とトランジションload１とを結ぶアークのアーク定義ウィンドウ
１３０６ トランジションload１とゾーンプレースzone１とを結ぶアークのアーク定義ウィンドウ
１３０７ トランジションload１のトランジション定義ウィンドウ
１４０１ アーク関連自動切断・接続処理
１５０１ 発火可能性を調べるトランジション選択処理
１５０２ 入力アーク処理[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a simulation apparatus based on an extended Petri net for simulating discrete event systems such as truck delivery and product flow in factories.
[0002]
[Prior art]
Truck delivery and product flow in factories are generally represented as discrete event systems. Petri nets are known as a method for modeling discrete event systems.
Petri Net was founded in 1962 by German C.I. A. This is a technique for modeling and analyzing a discrete event system proposed by Petri and behaving asynchronously and in parallel. Petri nets are composed of four simple components called “tokens”, “places”, “transitions”, and “arcs”, and are considered to correspond to products, locations, machines, and routes, respectively. The event that a transition generates and extinguishes a token is called "ignition".
[0003]
The basic firing rule is to fire when more than the number of arcs is collected in the place connected to the input side (hereinafter referred to as “input place”) when viewed from the transition, and the number of arcs is determined from the input place. The token is extinguished and a token having the number of arcs is generated in a place connected to the output side (hereinafter referred to as “output place”). For example, in the Petri net shown in FIG. 2, since one or more tokens exist in the place P1 connected to the input side as viewed from the transition T1 and two or more tokens exist in the place P2, firing occurs, and FIG. As shown, one token from the place P1 and two tokens from the place P2 disappear, and three tokens are generated in the place P3 and one token in the place P4. Such a simple Petri net is particularly called a “simple Petri net” or a “basic Petri net”.
[0004]
In such a simple Petri net, it is difficult to describe a complicated physical distribution system such as a production line of a factory. Recently, Petri nets with various extensions have been proposed. Such Petri nets are collectively referred to as “extended Petri nets”.
[0005]
In the software called “Design / CPN” and the extended Petri net described in JP-A-4-13095, JP-A-6-149773, and JP-A-10-334075, the token has an attribute. The user can freely describe firing rules using token attributes. Furthermore, it is possible to define a delay time from when a token is generated until the next firing.
[0006]
In the extended Petri net described in Japanese Patent Application Laid-Open No. 10-334075, the ignition processing means executes a simulation based on the created Petri net, and generates and extinguishes tokens. A flowchart showing the operation of the ignition processing means is shown in FIG.
In the memory initialization process 401, the memory necessary for the simulation is secured and initialized. Table 1 shows the memory managed by the ignition processing means.
[0007]
[Table 1]

[0008]
The memory shown in Table 1 is secured, the simulation time is set to the initial time, the token combination list is emptied, and the place list and transition list are created from the created Petri net.
In addition, for each place and each transition, a memory as shown in Table 2 and Table 3 is secured and initialized based on the created Petri net.
[0009]
[Table 2]

[0010]
[Table 3]

[0011]
However, the token list of the memory shown in Table 2 is initialized to be empty.
In the initial marking process 402, tokens set for all the places are generated and added to the memory token list shown in Table 2 above.
[0012]
FIG. 5 is a flowchart showing the ignitable transition search processing 403. First, in the input arc processing 501, a token having a color name (name indicating the token type) set in the input arc of the transition is searched from the corresponding input place, and is set as the corresponding input token variable. This token is called a fireable token.
[0013]
If there are fireable tokens in all the input arcs (502), the firing rule processing 503 creates a token having the color name set in the output arc and sets it as an output token variable, which is set for each transition. Execute the firing rule. At this time, when a value other than “0” is returned (returned) (504), it is determined that firing is possible, and the token combination data shown in Table 4 is managed by the firing processing means in the token combination list registration processing 505. Register in the memory shown in Table 1 above. At this time, when a value is set in the priority variable indicating priority, the value is written as it is in the priority order shown in Table 4, and when no value is set, an appropriate value is determined by a random number, and the priority value shown in Table 4 is set. Write to rank.
[0014]
[Table 4]

[0015]
Then, in the next combination creation process 506, combinations of input tokens that have not been processed so far are obtained. If all combinations of input tokens have not been processed (507), the process returns to the input arc process 501 again. The above processes 501 to 506 are repeated until all combinations of input tokens are processed.
[0016]
[Problems to be solved by the invention]
Now, as shown in FIG. 6, let us consider that a physical distribution system that transports products by one automatic guided vehicle (hereinafter referred to as “AGV”) is described by an extended Petri net. In FIG. 6, skids skid 1 to skid 4 are loading / unloading places, and the traveling path of AGV is divided and managed in zones zone 1 to zone 5. When the physical distribution system shown in FIG. 6 is described by the extended Petri net described in JP-A-10-334075, it is as shown in FIG.
[0017]
Here, the number of state place states is originally one, but four are described separately in order to prevent arc overlap. Also, an arc with arrows on both sides means that the token is not deleted from the input place when the connected transition fires (an arc with only one side is a simple Petri net As well as the token is removed from the input place when the transition fires). There are two types of tokens, AGV tokens and state tokens (hereinafter referred to as “State tokens”), and their attributes are shown in Tables 5 and 6, respectively.
[0018]
[Table 5]

[0019]
[Table 6]

[0020]
In FIG. 7, only the AGV token is entered in each of the zone places zone1 to zone5 and the skid places skid1 to skid4, and the state token is entered in the state place state. Although detailed firing rules for each transition are omitted, for example, in the case of transition move3, it is necessary to set the firing rules so that only the AGV destination can fire the skid place skid2.
[0021]
The tokens that can be ignited only in the input arc of the transition load 1 shown in FIG. 7 are shown in italics. In other words, the firing of the transition load1 requires one AGV token for the skid place skid1 and one State token for the state place state. Although the tokens that can be ignited are not described in the input arcs of the transitions load2, load3, and load4, similarly, one AGV token and one State token are required to ignite the transition.
[0022]
Next, problems of the ignition processing means in the extended Petri net described in JP-A-10-334075 will be described. In the ignition processing means, in the input arc processing 501 shown in FIG. 5, it is checked whether or not there is a token that can be ignited in all the input places of all the transitions. That is, it is necessary to determine the possibility of ignition for all transitions. For example, in the example illustrated in FIG. 7, it is necessary to determine the possibility of firing for a total of 16 transitions of transitions load 1 to load 4, unload 1 to unload 4, and move 1 to move 8. Although FIG. 7 is a very simple case, there is a drawback that a considerable time is required for a large-scale case.
[0023]
Accordingly, an object of the present invention is to provide means for solving the above-described drawbacks and enabling simulation with a short calculation time.
[0024]
[Means for Solving the Problems]
The simulation device based on the extended Petri net of the present invention is a simulation device based on an extended Petri net using a computer system for simulating a discrete event system, an input means for inputting information and instructions necessary for the simulation, A model creation means for creating an extended Petri net model of a discrete event system by inputting places, transitions and arcs according to an input from the input means based on a user operation on the input means, and created by the model creation means Display means for displaying the extended Petri net model on the output device, recording means for recording the extended Petri net model created by the model creating means on the recording device, and an extended Petri net model recorded on the recording device. Simulation A simulation calculation means for executing a simulation, and an output means for outputting the execution result of the simulation executed by the simulation calculation means to at least one of the output device and the recording device, the output device including a display, The recording device includes a memory and a disk, and the model creation unit further defines an attribute by receiving a token variable name and attribute name designation from the user via the input unit for each token, and defines the attribute of the defined token. A means for setting a firing rule for a transition using, and at the time of firing a transition, whether to delete a token existing in the input place for each place according to the type of arc connected to the input place. The simulation calculation means has the token When an arc connected to an input place set to be deleted and an arc connected to an input place set not to delete the token are both connected to one transition as an input arc, If there is no ignitable token in at least one of the input places that are set to delete the token connected to the transition, the input place that is set not to delete the transition and the token If there is a token that can be fired in all input places that are set to delete the token connected to the transition via an arc, the transition and the token are deleted. The connection with the input place that is set to not When the simulation is in progress, in addition to the normal transition firing process, the automatic disconnection connection means disconnects / connects the connection between the transition and the input place by the automatic disconnection connection process. The ignition process and the disconnection / connection process are repeated until there are no possible transitions, and the simulation execution result is obtained.
[0026]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
An example of an embodiment of the present invention is shown in FIG. FIG. 1 shows only the devices and functions necessary for carrying out the present invention. Even if peripheral devices such as a printer and a tape drive are added, there is no difference as an embodiment.
[0027]
In FIG. 1, a computer main body 101 is a general-purpose computer having a CPU 106, a memory 107, and the like. In the present embodiment, the present invention is implemented as software recorded on the memory 107. The simulation apparatus according to the present invention inputs a simulation model in the extended Petri net format to the model creation means 116 using the keyboard 103 and the pointing device 104.
[0028]
The model creation means 116 inputs a place transition arc by the Petri net diagram editing means 117 to create a Petri net diagram, and the initial marking setting means 121 sets the token arrangement at the start of the simulation. Further, the model creating unit 116 sets the firing rule of the transition by the firing rule setting unit 118, and sets the firing priority by the firing priority setting unit 110.
[0029]
The created extended Petri net is recorded in the memory 107 by the model recording unit 120 and displayed on the display 102 by the model display unit 119. The simulation calculation means 114 executes a simulation based on the extended Petri net recorded in the memory 107, records the execution result in the memory 107 and the disk 105, and displays the state of the token moving around on the display 102.
[0030]
In the simulation calculation means 114, “●” in the figure means that there are a plurality of relationships. For example, a transition “●” between the ignition processing unit 111 and the transition 108 indicates that there are a plurality of transitions, and the ignition processing unit 111 is associated with a plurality of transitions.
[0031]
The arc-related automatic disconnection / connection means 122 disconnects / connects the association between the transition and the input place from the current token arrangement. Specifically, the arc-related automatic disconnection / connection unit 122 obtains all the places 109 where the tokens exist from all the tokens 113, and further obtains all the transitions 108 using these places as input places. Predetermined processing is performed on each of the transitions 108 based on the firing rules set by the firing rule setting means 118 and the firing priorities set by the firing priority setting means 110, and all the fireable tokens The combination 112 is created. The firing processing means 111 fires transitions in the order of the firing priority obtained by calculation, deletes the token from the input place, and sends the token to the output place. The extended Petri net is simulated by repeating the above-described processing.
[0032]
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
In the following, the distribution system for transporting products using the AGV shown in FIG. 6 and FIG. 7 in which the distribution system in FIG. 6 is described by an extended Petri net will be described as an example.
[0033]
When the simulation apparatus based on the extended Petri net according to the present invention is executed (activated), a window 801 as shown in FIG. The window 801 includes a title bar 802 for moving and enlarging / reducing the window 801, a menu bar 803 having menu buttons for performing various operations, and a canvas 804 for creating and displaying a Petri net. And a scroll bar 814 for scrolling the canvas 804 up and down, left and right, and a parts list 805 for selecting Petri net parts.
[0034]
A menu bar 803 includes a “File” menu button 806 for performing file input / output, printing, and the like, and an “Edit” menu button for performing block and arc movement and cutting and pasting (cutting and pasting operations). 807, a “Simulation” menu button 808 for starting, stopping, and restarting the simulation, and a “Color” menu button 809 for defining token attributes.
[0035]
The parts list 805 includes place parts 810, transition parts 811, unidirectional arc parts 812, and bidirectional arc parts 813 as Petri net parts. Here, when a transition is ignited, the token is deleted from the input place connected by the unidirectional arc component 812, and the token is not deleted from the input place connected by the bidirectional arc component 813.
[0036]
When creating a Petri net, a Petri net part is selected from the parts list 805 and moved to the canvas 804 in a selected state, that is, dragged and dropped onto the canvas 804. Parts can be moved, cut and pasted, and the like using a commercially available drawing tool. By performing such an operation, a Petri net as shown in FIG. 7 can be created on the canvas 804.
[0037]
Next, a method for defining the attributes of the token (hereinafter also referred to as “color definition”) will be described.
When the “Color” menu button 809 shown in FIG. 8 is selected, an empty color definition window (nothing is input at all) as shown in FIG. 9 is displayed. Any character can be entered in the color definition window, and the user defines the attributes of the token in the following format.
Color name (attribute 1 type attribute 1 name, attribute 2 type attribute 2 name, ...);
[0038]
Here, the color name is a name for identifying different types of tokens (for example, “AGV” or “State” in FIG. 7). In the case of the Petri net shown in FIG. 7, the AGV token and the State token have the attributes shown in Tables 5 and 6, respectively.
AGV (String to);
State (String cur [8], String next [8]);
Set as follows.
[0039]
Here, “String” is an attribute representing a character string type (data). “To” is an attribute indicating that the AGV indicates a destination (moving) or a current position (stopped). “Cur [8]” is an attribute indicating the transfer source (before transfer) or transfer destination (during transfer and after transfer) of each product, and “next [8]” is an attribute indicating the transfer destination of each product. There are 8 products in total, and the i-th product's transfer source (during and after transfer) is the State token “cur [i]”, and the transfer destination is the State token “next [i]” expressed.
[0040]
When executing the simulation, it is necessary to set initial marking (token arrangement at the start of simulation). Initial marking is performed for each place. When each place part displayed on the canvas 804 is double-clicked, an empty place definition window as shown in FIG. 10 is displayed. Any character can be entered in the place definition window, and the user can specify the initial marking of the place in the following format.
Number * color name (attribute value 1, attribute value 2, ...);
[0041]
In the case of the Petri net shown in FIG. 7, since the initial marking is an AGV token in the skid place skid1 and a state token in the state place state, the following initial marking is set in the place definition window of the skid place skid1. And
1 * AGV ("skid1");
In addition, the following initial markings are set in the place definition window of the state place state (the apparent number is four in the Petri net shown in FIG. 7 but there is only one entity).
1 * State (["skid1", "skid1", "skid2", "skid2", "skid3", "skid3", "skid4", "skid4"],
["skid2", "skid3", "skid3", "skid4", "skid4", "skid1", "skid2", "skid3"]);
[0042]
Here, in this example, as shown in FIG. 6, there are eight products, each of which is designated as a transport destination. For example, the transport source of the product 1 is the skid place skid1 and the transport destination is the skid place skid2.
[0043]
Finally, set the firing rules for the transition. The firing rule for each transition is set by the arc definition and transition definition.
The arc definition is the number of I / O tokens and color names that are ignited in the transition connected to the input side of each transition and the arc connected to the output side, and a token for referencing the token. Variable name. When you double-click the arc you want to set displayed on the canvas 804, an empty arc definition window as shown in Fig. 11 is displayed. In the arc definition window, the connected transition is ignited in the following format. Specify the number of tokens, color name, and token variable name.
Number * color name Token variable name
[0044]
Here, the token variable name is an identification name for distinguishing a plurality of tokens when describing the firing rule. In particular, the token variable set for the input arc is called “input token variable”, and the token variable set for the output arc is called “output token variable”.
[0045]
For example, in order for the transition load1 shown in FIG. 7 to fire, there must be one AGV token in the skid place skid1 and one State token in the state place state, so the transition load1 and skid place skid1 In the arc definition window of the connecting arc,
1 * AGV agv1
And set. Similarly, in the arc definition window of the arc connecting transition load1 and state place state,
1 * State state
And set.
[0046]
When transition load1 is ignited, it is necessary to generate an AGV token in zone place zone1, so in the arc definition window of the arc connecting transition load1 and zone place zone1,
1 * AGV agv2
And set. In this way, AGV tokens are distinguished by assigning different token variable names on the input side and output side.
[0047]
The transition definition can describe the details of the firing rules of the transition. The transition definition also serves as the firing priority setting means 110 at the same time. When each transition displayed on the canvas 804 is double-clicked, a transition definition window as shown in FIG. 12 is displayed. In the transition definition window, an ignition rule for an arbitrary transition can be described by inputting characters.
[0048]
The transition format can use the same format as the C ++ language. For example, if "0" is returned as the return value (the value of "0" is returned), it means that the firing condition is not met, and the return If a value other than “0” is returned (a value other than “0” is returned), it means that the firing condition is satisfied. Moreover, there is “priority” as a special variable, and the firing priority according to the present invention can be set in “priority”. However, it is not necessary to assign (set) the priority to “priority”. In this case, it is considered that a random number is implicitly substituted.
[0049]
In the case of the Petri net shown in FIG. 7, the transition definition window of transition load 1

Is described. Thus, the token attribute is
Token variable name. Attribute name
Can be accessed in the form of
[0050]
The completed Petri net is shown in FIG. Although a simple Petri net as shown in FIG. 7 has been described here, a complex Petri net can be created by performing the same operation.
[0051]
Next, the ignition processing unit 111 will be described.
The ignition processing unit 111 generates a token and extinguishes by executing a simulation based on the created Petri net. A flowchart showing the operation of the ignition processing means 111 is shown in FIG.
In the memory initialization process 401, the memory necessary for the simulation is secured and initialized. Table 7 shows the memory managed by the ignition processing unit 111.
[0052]
[Table 7]

[0053]
The memory shown in Table 7 has a list of tokens (hereinafter referred to as “token list”) added to the firing processing means management memory shown in Table 1 above. The memory shown in Table 7 is secured, the simulation time is set to the initial time, the token combination list and the token list are emptied, and a place list and a transition list are created from the created Petri net.
In addition, for each place and each transition, the place management memory shown in Table 2 above, the transition management memory shown in Table 3 above, and the token management memory shown in Table 8 are respectively secured, and the initial is based on the created Petri net. Turn into.
[0054]
[Table 8]

[0055]
However, the token list in the place management memory shown in Table 2 is initialized to be empty. The token management memory shown in Table 8 describes a place where a token exists for each token.
In the case of the example shown in FIG. 7, the ignition processing means 111 management memory is as shown in Table 9, the place management memory is as shown in Table 10, and the transition management memory is as shown in Table 11.
[0056]
[Table 9]

[0057]
[Table 10]

[0058]
[Table 11]

[0059]
In the initial marking process 402, tokens are generated based on the number of tokens, color names and attributes set in the place definition window for all places, and the token list in the ignition processing means 111 management memory shown in Table 7 above is displayed. And added to the token list in the place management memory shown in Table 2 above. Further, a place where each token exists is added to the token management memory shown in Table 8.
In the example shown in FIG. 7, the place management memory shown in Table 2 is shown in Table 12, and the token management memory shown in Table 8 is shown in Table 13.
[0060]
[Table 12]

[0061]
[Table 13]

[0062]
Thus, compared to the place management memory shown in Table 10, in the place management memory shown in Table 12, a State token is added to the state place state and an AGV token is added to the skid place skid1.
[0063]
In the arc-related automatic disconnection / connection processing 1401, when a transition having a place where a token exists as an input place is connected by the bidirectional arc component 813, another arc of the transition is examined, and the unidirectional arc component 812 When connected to a place, if there is no token in the place, the transition is deleted from the output transition list of the place management memory (Table 2) of the place connected by the bidirectional arc component 813.
For example, in the example shown in FIG. 7, the place management memory changes as shown in Table 12 to Table 14.
[0064]
[Table 14]

[0065]
Thus, the transitions load2, load3, and load4 are deleted from the output transition of the state place state. That is, the relationship between the state place state and the transitions load2 to load4 is deleted.
[0066]
The ignitable transition search process 403 is performed according to the flowchart shown in FIG.
First, in the process 1501, one transition (hereinafter referred to as “transition for checking the possibility of firing”) is selected which has a place where a token exists as an input place. In this embodiment, since the token management memory is as shown in Table 13, it can be seen that there are two places where a token exists, a skid place skid1 and a state place state. Further, the place management memory is as shown in Table 14, and since the transition load1 is set for both the output transitions of the skid place skid1 and the state place state, the transition for checking the possibility of firing is only the transition load1. Become.
[0067]
Here, if the arc-related automatic disconnection / connection process 1401 is not used, the place management memory remains as shown in Table 12. Therefore, since the output transitions related to the state place state are the transitions load1, load2, load3, and load4, and the output transition related to the skid place skid1 is the transition load1, the transitions for checking the possibility of firing are the transitions load1, load2 , Load3, and load4.
[0068]
Next, in process 1502, for the transition to be examined for the possibility of ignition selected in process 1501, a token having a color name described in the arc definition window of the input arc of the transition is searched from the corresponding input place, Let it be the corresponding input token variable. This token is called a fireable token.
[0069]
If there are fireable tokens in all the input arcs (1503), in the firing rule processing 503, a token having the color name described in the arc definition window of the output arc is created as an output token variable, and the transition is made. Execute the firing rules described in the definition window. At this time, when a return value other than “0” is returned (504), it is determined that firing is possible, and in the token combination list registration processing 505, the above-mentioned table managed by the firing processing means 111 in the token combination data shown in Table 4 7 is registered in the token combination list. At this time, when a value is set in the variable priority indicating the priority order, the value is written as it is in the priority order shown in Table 4, and when no value is set, an appropriate value is determined by a random number, and the priority value shown in Table 4 is set. Write to rank.
[0070]
If there are a plurality of tokens in the input place, there is another combination of tokens. Therefore, the next combination creation process 506 obtains the next token combination, and the process returns to the process 1502 to perform the same process as described above. I do.
[0071]
If all token combinations are obtained for one transition that examines the possibility of firing (507), it is examined whether or not there remains a transition that examines the possibility of firing. As a result, when there is a transition for checking the possibility of ignition, the process returns to the process 1501 and the same process as described above is repeated until there is no transition for checking the possibility of ignition.
[0072]
For example, in the case of the Petri net shown in FIG. 7, the transition load1 can be fired, and token combinations as shown in Table 15 are registered in the token combination list in the firing processing means 111 management memory shown in Table 7. become.
[0073]
[Table 15]

[0074]
Here, in the example shown in FIG. 7, since the priority order is not designated, the priority order is selected with a random number. Therefore, depending on the random number series, it is not always as shown in Table 15 above.
Returning to FIG. 14, in the token combination rearrangement process 404, the token combination list in Table 15 is rearranged in descending order of priority. When Table 15 is rearranged, Table 16 is obtained.
[0075]
[Table 16]

[0076]
In the marking change process 405, the input tokens are deleted from the input place of the transition registered in the list in order from the top of the token combination list sorted in the order of priority by the token combination sorting process 404, and output. Generate an output token to a place. The input place searches for a token to be deleted from the token list, extracts the token from the token list, and releases the used memory. In the output place, the newly sent token is registered in the token list.
[0077]
When deleting a token, the token combination list is examined. As a result, when the token to be deleted is registered in the list, the element is also deleted from the list. Furthermore, the token list in the firing processing means 111 management memory shown in Table 7 is also updated at the same time. The marking is changed by repeating such processing until the token combination list becomes empty.
[0078]
For example, the first line of the token combination list shown in Table 16 is processed. That is, the transition load1 is fired, AGV ("skid1") is deleted from the skid place skid1, and AGV ("skid3") is output to the zone place zone1. The attribute of the State token changes as follows. Since the AGV transports the product 2 and moves to the skid place skid3, cur [2] changes from “skid1” to “skid3”.
State (["skid1", "skid3", "skid2", "skid2", "skid3", "skid3", "skid4", "skid4"],
["skid2", "skid3", "skid3", "skid4", "skid4", "skid1", "skid2", "skid3"]);
[0079]
As the AGV token moves from the skid place skid1 to the zone place zone1, the token combination list shown in Table 16 becomes empty. The place management memory shown in Table 14 is as shown in Table 17. Compared with the place management memory shown in Table 14, the AGV token has moved from the skid place skid1 to the zone place zone1.
[0080]
[Table 17]

[0081]
Further, the token management memory shown in Table 13 is as shown in Table 18.
[0082]
[Table 18]

[0083]
After performing the masking change process 405, the process returns to the arc-related automatic disconnection / connection process 1401 again and performs the same process as described above. In the above-described example, since there is no token in the skid place skid1, which is the input place of the transition load1, the association between the state place state and the transition load1 is automatically disconnected, and the place management memory shown in Table 17 is as shown in Table 19 become. Thus, the output transition of the state place state is empty.
[0084]
[Table 19]

[0085]
Thereafter, the same processing is repeated until the transition that can be ignited disappears.
[0086]
When AGV arrives at skid place skid3 in the middle of the simulation, when a transition in which a place where a token exists is connected by bidirectional arc component 813 by arc-related automatic disconnection / connection processing 1401, When other arcs of the transition are examined and the place is connected to the place by the unidirectional arc part 812, if there is a fireable token in the place, the place management memory of the place connected by the bidirectional arc part 813 (Table 2). ) Is registered in the output transition list. In the example shown in FIG. 7, the place management memory after the AGV arrives at the skid place skid 3 is as shown in Table 20.
[0087]
[Table 20]

[0088]
In Table 20, the relationship between the state place state and the transition load3 is connected. In this case, the transition to be examined by the ignitable transition search processing 403 is only the transition load3.
[0089]
In the Petri net described above, there is no concept of time, and a newly generated token can be fired immediately. The concept of time can also be introduced, and an extended Petri net having a firing delay time that can be fired after a certain time specified by the user after the token is generated can be easily formed. For example, when there is no transition that can be fired at a certain time, the simulation time is advanced to the smallest time among the times when the token that cannot fire can be fired (simulation time update process 406), and the above process is repeated. This is done until the end time.
[0090]
【The invention's effect】
As described above, according to the present invention, when ignitability is judged by simulation, only one ignitable transition is selected appropriately regardless of the arrangement of tokens. Since it is only necessary to determine the possibility of ignition, simulation can be performed in a short calculation time. For example, in the case of the embodiment shown in FIG. 7, conventionally, the number of transitions to be examined to determine the possibility of ignition is 16 transitions load1 to load4, unload1 to unload4, and move1 to move8. Since only one transition is required, the calculation time can be shortened. In particular, the larger the Petri net, the higher the effect compared to the conventional one.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a system configuration example of a simulation apparatus based on an extended Petri net according to the present invention.
FIG. 2 is a diagram showing an example of a simple Petri net (before firing).
FIG. 3 is a diagram showing an example of a simple Petri net (after firing).
FIG. 4 is a flowchart showing the operation of a conventional ignition processing means.
FIG. 5 is a flowchart showing a conventional ignitable transition search process.
FIG. 6 is a diagram illustrating an example of a distribution system using an automatic guided vehicle.
7 is a diagram showing an extended Petri net of the physical distribution system shown in FIG. 6. FIG.
FIG. 8 is a diagram showing a window displayed immediately after execution of a simulation apparatus based on an extended Petri net according to the present invention.
FIG. 9 is a diagram illustrating a color definition window.
FIG. 10 is a diagram showing a place definition window.
FIG. 11 is a diagram showing an arc definition window.
FIG. 12 is a diagram showing a transition definition window.
FIG. 13 is a diagram showing an extended Petri net created by the simulation apparatus according to the present invention.
14 is a flowchart showing the operation of the ignition processing unit 111 shown in FIG. 1. FIG.
15 is a flowchart showing a ignitable transition search process shown in FIG. 14;
[Explanation of symbols]
101 Computer body
102 display
103 keyboard
104 pointing device
105 discs
106 CPU
107 memory
108 transition
109 places
110 Firing priority setting means
111 Ignition treatment means
112 firing token combination
113 tokens
114 Simulation calculation means
115 Token attribute
116 Model creation means
117 Editing means for Petri nets
118 firing rule setting means
119 Model display means
120 Model recording means
121 Initial marking setting means
122 Arc-related automatic disconnection and connection means
401 Memory initialization processing
402 Initial marking process
403 ignitable transition search process
404 Token combination sorting process
405 Marking change processing
406 Simulation time update processing
501 Input arc processing
503 firing rule processing
505 Token combination list registration process
506 Next combination creation process
801 Window for creating and executing extended Petri nets
802 Title bar
803 Menu bar
804 canvas
805 Parts list
806 “File” menu button
807 “Edit” menu button
808 "Simulation" menu button
809 “Color” menu button
810 Place parts
811 Transition parts
812 Unidirectional arc parts
813 Bidirectional arc parts
814 Scroll bar
1301 Color definition window
1302 Place definition window for skid place skid1
1303 Place definition window for state place state
1304 Arc definition window for arc connecting state place state and transition load1
1305 Arc definition window for arc connecting skid place skid1 and transition load1
1306 Arc definition window for arc connecting transition load1 and zone place zone1
1307 Transition definition window for transition load1
1401 Arc-related automatic disconnection and connection processing
1501 Transition selection process to check the possibility of ignition
1502 Input arc processing

Claims (1)

A simulation device based on an extended Petri net using a computer system for simulating a discrete event system,
An input means for inputting information and instructions necessary for the simulation;
Model creation means for creating an extended Petri net model of a discrete event system by inputting places, transitions, and arcs according to an input from the input means based on a user operation on the input means;
Display means for displaying the extended Petri net model created by the model creating means on an output device;
Recording means for recording the extended Petri net model created by the model creating means in a recording device;
Simulation calculation means for executing simulation of the extended Petri net model recorded in the recording device;
Output means for outputting the execution result of the simulation executed by the simulation calculation means to at least one of the output device and the recording device,
The output device includes a display,
The recording device includes a memory and a disk,
The model creation means further defines attributes by specifying the token variable name and attribute name from the user via the input means for each token, and sets a firing rule for the transition using the defined token attributes. And, at the time of transition firing, it has means for setting for each place whether or not to delete the token existing in the input place according to the type of arc connected to the input place,
The simulation calculation means is:
When an arc connected to an input place set to delete the token and an arc connected to an input place set not to delete the token are both connected to one transition as an input arc,
If there is no fireable token in at least one of the input places that are set to delete the token connected to the transition via the arc, set the transition and the token not to be deleted. Disconnect from the input place
Input that is set to not delete the transition and the token if there is a fireable token in all input places that are set to delete the token connected to the transition via the arc It has an automatic disconnection connection means to connect the association with the place,
When the simulation is in progress, in addition to the normal transition firing process, the automatic disconnection / connection means performs a disconnection / connection process for disconnecting or connecting the relation between the transition and the input place, and the ignition is performed until there are no more ignitable transitions. A simulation apparatus based on an extended Petri net characterized in that a simulation execution result is obtained by repeating the process and the disconnection / connection process.

Images