(57)【特許請求の範囲】
【請求項１】
離散事象システムをシミュレーションするためのコンピュータシステムを用いた拡張ペトリネットに基づくシミュレーション装置であって、
シミュレーションに必要な情報および命令を入力する入力手段と、
上記入力手段に対するユーザの操作に基づいた上記入力手段からの入力に従って、プレース、トランジション、およびアークを入力して離散事象システムの拡張ペトリネットモデルを作成するモデル作成手段と、
上記モデル作成手段により作成された拡張ペトリネットモデルを出力装置に表示する表示手段と、
上記モデル作成手段により作成された拡張ペトリネットモデルを記録装置に記録する記録手段と、
上記記録装置に記録された拡張ペトリネットモデルのシミュレーションを実行するシミュレーション計算手段と、
上記シミュレーション計算手段により実行したシミュレーションの実行結果を上記出力装置および記録装置の少なくとも一方に出力する出力手段と、を備え、
上記出力装置はディスプレイを含み、
上記記録装置はメモリおよびディスクを含み、
上記モデル作成手段は、さらに、トークン毎に上記入力手段を介してユーザからトークン変数名および属性名の指定を受け属性を定義するとともに、定義されたトークンの属性を用いてトランジションの発火ルールを設定し、かつ、トランジション発火時に、入力プレースに存在するトークンを削除するか否かを、当該入力プレースに接続するアークの種類に応じてプレース毎に設定する手段を有し、
上記シミュレーション計算手段は、
上記トークンを削除する設定を行っている入力プレースに接続するアークと、上記トークンを削除しない設定を行っている入力プレースに接続するアークとが共に入力アークとして１つのトランジションに接続されているとき、
アークを介して当該トランジションに接続された上記トークンを削除する設定を行っている入力プレースの少なくとも１つに発火可能なトークンが存在しない場合には、当該トランジションと上記トークンを削除しない設定を行っている入力プレースとの関連を切断し、
アークを介して当該トランジションに接続された上記トークンを削除する設定を行っているすべての入力プレースに発火可能なトークンが存在する場合には、当該トランジションと上記トークンを削除しない設定を行っている入力プレースとの関連を接続する自動切断接続手段を有し、
シミュレーション進行時には、通常のトランジション発火処理に加えて、上記自動切断接続手段により上記トランジションと上記入力プレースとの関連を切断あるいは接続する切断・接続処理を実行し、発火可能なトランジションがなくなるまで当該発火処理と当該切断・接続処理とを繰り返してシミュレーションの実行結果を求めることを特徴とする拡張ペトリネットに基づくシミュレーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、トラックの配送や工場における製品の流れのような離散事象システムをシミュレーションするための拡張ペトリネットに基づくシミュレーション装置に関するものである。
【０００２】
【従来の技術】
トラックの配送や工場における製品の流れは、一般に離散事象システムとして表わされる。離散事象システムをモデル化する手法としてペトリネットが知られている。
ペトリネット（Petri Net）は、１９６２年ドイツのＣ．Ａ．Ｐｅｔｒｉによって提案され、非同期的かつ並列的に振舞う離散事象システムをグラフィカルにモデル化・解析する手法である。ペトリネットは、「トークン」、「プレース」、「トランジション」、および「アーク」と呼ばれる簡単な４つの構成要素からなり、製品、置場、機械、およびルートにそれぞれ対応していると考えられる。トランジションがトークンを生成・消滅させる事象は「発火」と呼ばれている。
【０００３】
基本的な発火ルールは、トランジションから見て入力側に接続されているプレース（以下、「入力プレース」と記載する。）にアーク本数以上のトークンが揃った時に発火し、入力プレースからアーク本数のトークンが消滅して、出力側に接続されているプレース（以下、「出力プレース」と記載する。）にアーク本数のトークンが生成される、というものである。例えば、図２に示すペトリネットでは、トランジションＴ１から見て入力側に接続されているプレースＰ１に１個以上、プレースＰ２に２個以上のトークンが存在しているため発火が起こり、図３に示すように、プレースＰ１から１個、プレースＰ２から２個のトークンが消滅して、プレースＰ３に３個、プレースＰ４に１個のトークンが生成される。このような単純なペトリネットは、特に、「単純ペトリネット」あるいは「基本ペトリネット」と呼ばれている。
【０００４】
このような単純ペトリネットでは、工場の生産ラインのような複雑な物流システムを記述することは困難であるため、最近では、さまざまな拡張がなされたペトリネットが提案されている。このようなペトリネットを、総称して「拡張ペトリネット」と呼ぶ。
【０００５】
「Ｄｅｓｉｇｎ／ＣＰＮ」と呼ばれるソフトウェアや特開平４−１３０９５号公報、特開平６−１４９７７３号公報、および特開平１０−３３４０７５号公報に記載されている拡張ペトリネットでは、トークンに属性を持たせることができ、トークン属性を用いて発火ルールをユーザが自由に記述することができる。さらに、トークンが生成されてから、次に発火するまでの遅延時間を定義することもできる。
【０００６】
特開平１０−３３４０７５号公報に記載の拡張ペトリネットでは、発火処理手段において、作成されたペトリネットを基にシミュレーションを実行し、トークンの生成・消滅を行っている。上記発火処理手段の動作を示すフローチャートを図４に示す。
メモリ初期化処理４０１で、シミュレーションに必要なメモリの確保と初期化を行う。発火処理手段が管理するメモリを表１に示す。
【０００７】
【表１】
0003943909.tif 000002
【０００８】
上記表１に示すメモリを確保して、シミュレーション時刻を初期時刻に設定し、トークン組み合わせのリストを空にし、作成されたペトリネットからプレースリストとトランジションリストとを作成する。
また、各プレースと各トランジションに対して、それぞれ表２、表３に示すようなメモリを確保し、作成されたペトリネットに基づき初期化する。
【０００９】
【表２】
0003943909.tif 000003
【００１０】
【表３】
0003943909.tif 000004
【００１１】
ただし、上記表２に示すメモリのトークンリストは空に初期化する。
初期マーキング処理４０２では、全プレースに対して設定されているトークンを生成し、上記表２に示すメモリのトークンリストに追加する。
【００１２】
発火可能トランジション検索処理４０３の処理を示すフローチャートを図５に示す。まず、入力アーク処理５０１において、トランジションの入力アークに設定されているカラー名（トークンの種別を表す名称）を持つトークンを対応する入力プレースから探し、対応する入力トークン変数とする。このトークンを発火可能トークンと呼ぶ。
【００１３】
全ての入力アークにおいて発火可能トークンが存在していれば（５０２）、発火ルール処理５０３において、出力アークに設定されているカラー名を持つトークンを作成して出力トークン変数とし、トランジション毎に設定されている発火ルールを実行する。この際、“０”以外の値が返された（returnされた）ときには（５０４）、発火可能と判断し、トークン組み合わせリスト登録処理５０５において、表４に示すトークン組み合わせデータを発火処理手段が管理する上記表１に示したメモリに登録する。この際、優先順位を示す変数priorityに値が設定されている時には、表４の優先順位にそのまま書き込み、値が設定されていないときには、乱数により適当な値を決めて、それを表４の優先順位に書き込む。
【００１４】
【表４】
0003943909.tif 000005
【００１５】
そして、次組み合わせ作成処理５０６において、今までに処理していない入力トークンの組み合わせを求め、全ての入力トークンの組み合わせを処理していなかった場合には（５０７）、再度入力アーク処理５０１に戻り、全ての入力トークンの組み合わせが処理されるまで上記処理５０１〜５０６を繰り返す。
【００１６】
【発明が解決しようとする課題】
さて、図６に示すように１台の無人搬送台車（以下、「ＡＧＶ」と記載する。）により製品を搬送する物流システムを拡張ペトリネットで記述することを考える。図６において、スキッドskid１〜skid４は荷積み・荷降し場であり、ＡＧＶの走行路はゾーンzone１〜zone５に分割管理されている。特開平１０−３３４０７５号公報に記載の拡張ペトリネットで図６に示す物流システムを記述すると図７に示すようになる。
【００１７】
ここで、ステートプレースstateは、本来１つであるが、アークの重なりを防ぐために別々に４つ記載している。また、矢印が両側に付いているアークは、接続しているトランジションが発火しても、トークンが入力プレースから削除されないことを意味している（矢印が片側だけ付いているアークは、単純ペトリネットと同様に、トランジションが発火したら、トークンが入力プレースから削除される）。トークンは、ＡＧＶトークンとステートトークン（以下、「Ｓｔａｔｅトークン」と記載する。）との２種類が存在し、その属性を表５と表６にそれぞれ示す。
【００１８】
【表５】
0003943909.tif 000006
【００１９】
【表６】
0003943909.tif 000007
【００２０】
図７において、各ゾーンプレース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１のトランジション定義ウィンドウには、
0003943909.tif 000008
と記述する。このように、トークンの属性は
トークン変数名．属性名
の形式でアクセスすることができる。
【００５０】
完成したペトリネットを図１３に示す。ここでは、図７に示すような簡単なペトリネットに関して説明したが、複雑なペトリネットでも同様の操作を行うことにより作成することができる。
【００５１】
次に、発火処理手段１１１について説明する。
発火処理手段１１１は、作成されたペトリネットを基にシミュレーションを実行してトークンの生成および消滅を行う。発火処理手段１１１の動作を示すフローチャートを図１４に示す。
メモリ初期化処理４０１では、シミュレーションに必要なメモリの確保と初期化を行う。発火処理手段１１１が管理するメモリを表７に示す。
【００５２】
【表７】
0003943909.tif 000009
【００５３】
上記表７に示すメモリは、上記表１に示した発火処理手段管理メモリと比べて、トークンのリスト（以下、「トークンリスト」と呼ぶ。）が追加されている。上記表７に示すメモリを確保して、シミュレーション時刻を初期時刻に設定し、トークン組み合わせリストとトークンリストとをそれぞれ空にし、作成されたペトリネットからプレースリストとトランジションリストとを作成する。
また、各プレースと各トランジションに対して、上記表２に示すプレース管理メモリ、上記表３に示すトランジション管理メモリ、および表８に示すトークン管理メモリをそれぞれ確保し、作成されたペトリネットに基づき初期化する。
【００５４】
【表８】
0003943909.tif 000010
【００５５】
ただし、表２に示すプレース管理メモリ内のトークンリストは空に初期化する。また、表８に示すトークン管理メモリは、トークンが存在するプレースをトークン毎に記述している。
上記図７に示す例の場合には、発火処理手段１１１管理メモリは表９に示すようになり、プレース管理メモリは表１０に示すようになり、トランジション管理メモリは表１１に示すようになる。
【００５６】
【表９】
0003943909.tif 000011
【００５７】
【表１０】
0003943909.tif 000012
【００５８】
【表１１】
0003943909.tif 000013
【００５９】
初期マーキング処理４０２では、全プレースに対してプレース定義ウィンドウに設定されたトークン個数、カラー名および属性に基づいてトークンを生成し、上記表７に示した発火処理手段１１１管理メモリ内のトークンリストと、上記表２に示したプレース管理メモリ内のトークンリストに追加する。また、各トークンが存在するプレースを表８に示したトークン管理メモリに追加する。
上記図７に示す例では、上記表２に示したプレース管理メモリは表１２に示すようになり、上記表８に示したトークン管理メモリは表１３に示すようになる。
【００６０】
【表１２】
0003943909.tif 000014
【００６１】
【表１３】
0003943909.tif 000015
【００６２】
このように、表１０に示すプレース管理メモリに比べて、表１２に示すプレース管理メモリでは、ステートプレースstateにＳｔａｔｅトークン、スキッドプレースskid１にＡＧＶトークンが追加されている。
【００６３】
アーク関連自動切断・接続処理１４０１では、トークンが存在するプレースを入力プレースとするトランジションが、双方向アーク部品８１３で接続されているときには、そのトランジションの他のアークを調べ、単方向アーク部品８１２でプレースと接続されているときには、そのプレースにトークンがなければ、双方向アーク部品８１３で接続されているプレースのプレース管理メモリ（表２）の出力トランジションリストから、そのトランジションを削除する。
例えば、図７に示す例の場合には、プレース管理メモリは表１２から表１４に示すように変化する。
【００６４】
【表１４】
0003943909.tif 000016
【００６５】
このように、ステートプレース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１が発火可能となり、表１５に示すようなトークン組み合わせが、表７に示す発火処理手段１１１管理メモリ内のトークン組み合わせリストに登録されることになる。
【００７３】
【表１５】
0003943909.tif 000017
【００７４】
ここで、図７に示す例では、優先順位が指定されていないため、乱数で優先順位が選ばれる。したがって、乱数系列によっては、上記表１５に示すようになるとは限らない。
図１４に戻り、トークン組み合わせ並べ替え処理４０４では、上記表１５のトークン組み合わせリストを優先順位が高い順番（降順）に並べ替える。上記表１５を並べ替えると表１６に示すようになる。
【００７５】
【表１６】
0003943909.tif 000018
【００７６】
マーキング変更処理４０５では、トークン組み合わせ並べ替え処理４０４により優先順位が高い順に並べ替えられたトークン組み合わせリストの先頭から順番に、リストに登録されているトランジションの入力プレースから入力トークンを削除して、出力プレースへ出力トークンを発生させる。入力プレースはトークンリストから削除すべきトークンを検索して、そのトークンをトークンリストから抜き出し、使用していたメモリを解放する。出力プレースでは新たに送られたトークンをトークンリストに登録する。
【００７７】
トークンを削除する際、トークン組み合わせリストを調べ、その結果、削除するトークンがそのリストに登録されているときには、その要素をリストからも削除する。さらに、表７に示す発火処理手段１１１管理メモリ内のトークンリストの更新も同時に行う。このような処理をトークン組み合わせリストが空になるまで繰り返すことにより、マーキングの変更を行う。
【００７８】
例えば、表１６に示すトークン組み合わせリストの最初の行を処理する。つまり、トランジション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１に移っている。
【００８０】
【表１７】
0003943909.tif 000019
【００８１】
また、表１３に示したトークン管理メモリは、表１８に示すようになる。
【００８２】
【表１８】
0003943909.tif 000020
【００８３】
マスキング変更処理４０５を行った後、再度、アーク関連自動切断・接続処理１４０１に戻り、上述した処理と同じ処理を行う。上述した例では、トランジションload１の入力プレースであるスキッドプレースskid１にトークンがなくなったため、自動的にステートプレースstateとトランジションload１との関連が切断され、表１７に示すプレース管理メモリは表１９に示すようになる。このように、ステートプレースstateの出力トランジションは空となる。
【００８４】
【表１９】
0003943909.tif 000021
【００８５】
以降、同様の処理を繰り返し、発火可能トランジションがなくなるまで繰り返す。
【００８６】
シミュレーションの途中で、ＡＧＶがスキッドプレースskid３に到着すると、アーク関連自動切断・接続処理１４０１により、トークンが存在するプレースを入力プレースとするトランジションが、双方向アーク部品８１３で接続されているときには、そのトランジションの他のアークを調べ、単方向アーク部品８１２でプレースと接続されているときには、そのプレースに発火可能トークンがあれば、双方向アーク部品８１３で接続されているプレースのプレース管理メモリ（表２）の出力トランジションリストに、そのトランジションを登録する。図７に示す例では、ＡＧＶがスキッドプレースskid３に到着した後のプレース管理メモリは表２０に示すようになる。
【００８７】
【表２０】
0003943909.tif 000022
【００８８】
表２０においては、ステートプレースstateとトランジションload３との関連が接続されている。この場合、発火可能トランジション検索処理４０３で調べるトランジションは、トランジションload３のみとなる。
【００８９】
以上説明したペトリネットでは時間の概念は存在せず、新たに生成されたトークンはすぐに発火可能となる。なお、時間の概念を導入することも可能であり、トークンが生成されてからユーザが指定したある時間後に発火可能となるような、発火遅延時間を持つ拡張ペトリネットとすることも容易にできる。例えば、ある時刻で発火可能なトランジションがなくなると、発火不可となっているトークンが発火可能に変わる時刻の中で、最も小さい時刻までシミュレーション時刻を進め（シミュレーション時刻更新処理４０６）、上記処理を繰り返し行い、最終的に終了時刻まで行えば良い。
【００９０】
【発明の効果】
以上、説明したように、本発明によれば、シミュレーションにて発火可能性を判断する際、トークンがいずれの配置であったとしても、発火可能トランジションを適切に１つだけ選択し、１つのトランジションの発火可能性を判断するだけで済むので、少ない計算時間でシミュレーションを行うことができる。例えば、図７に示す実施例の場合には、従来においては、発火可能性を判断するために調べるトランジションは、トランジションload１〜load４、unload１〜unload４、move１〜move８の１６個となるが、本発明では、１つのトランジションで済むので、計算時間を短縮することができる。特に、大規模なペトリネットになるほど、従来と比較して高い効果を得ることができる。
【図面の簡単な説明】
【図１】本発明による拡張ペトリネットに基づくシミュレーション装置のシステム構成例を示すブロック図である。
【図２】単純ペトリネット（発火前）の一例を示す図である。
【図３】単純ペトリネット（発火後）の一例を示す図である。
【図４】従来の発火処理手段の動作を示すフローチャートである。
【図５】従来の発火可能トランジション検索処理を示すフローチャートである。
【図６】無人搬送台車による物流システムの一例を示す図である。
【図７】図６に示した物流システムの拡張ペトリネットを示す図である。
【図８】本発明による拡張ペトリネットに基づくシミュレーション装置実行直後に表示されるウィンドウを示す図である。
【図９】カラー定義ウィンドウを示す図である。
【図１０】プレース定義ウィンドウを示す図である。
【図１１】アーク定義ウィンドウを示す図である。
【図１２】トランジション定義ウィンドウを示す図である。
【図１３】本発明によるシミュレーション装置で作成した拡張ペトリネットを示す図である。
【図１４】図１に示した発火処理手段１１１の動作を示すフローチャートである。
【図１５】図１４に示す発火可能トランジション検索処理を示すフローチャートである。
【符号の説明】
１０１  コンピュータ本体
１０２  ディスプレイ
１０３  キーボード
１０４  ポインティングデバイス
１０５  ディスク
１０６  ＣＰＵ
１０７  メモリ
１０８  トランジション
１０９  プレース
１１０  発火優先順位設定手段
１１１  発火処理手段
１１２  発火トークン組み合わせ
１１３  トークン
１１４  シミュレーション計算手段
１１５  トークン属性
１１６  モデル作成手段
１１７  ペトリネット図編集手段
１１８  発火ルール設定手段
１１９  モデル表示手段
１２０  モデル記録手段
１２１  初期マーキング設定手段
１２２  アーク関連自動切断・接続手段
４０１  メモリ初期化処理
４０２  初期マーキング処理
４０３  発火可能トランジション検索処理
４０４  トークン組み合わせ並べ替え処理
４０５  マーキング変更処理
４０６  シミュレーション時刻更新処理
５０１  入力アーク処理
５０３  発火ルール処理
５０５  トークン組み合わせリスト登録処理
５０６  次組み合わせ作成処理
８０１  拡張ペトリネットを作成・実行するウィンドウ
８０２  タイトルバー
８０３  メニューバー
８０４  キャンバス
８０５  部品リスト
８０６  「Ｆｉｌｅ」メニューボタン
８０７  「Ｅｄｉｔ」メニューボタン
８０８  「Ｓｉｍｕｌａｔｉｏｎ」メニューボタン
８０９  「Ｃｏｌｏｒ」メニューボタン
８１０  プレース部品
８１１  トランジション部品
８１２  単方向アーク部品
８１３  双方向アーク部品
８１４  スクロールバー
１３０１  カラー定義ウィンドウ
１３０２  スキッドプレースskid１のプレース定義ウィンドウ
１３０３  ステートプレースstateのプレース定義ウィンドウ
１３０４  ステートプレースstateとトランジションload１とを結ぶアークのアーク定義ウィンドウ
１３０５  スキッドプレースskid１とトランジションload１とを結ぶアークのアーク定義ウィンドウ
１３０６  トランジションload１とゾーンプレースzone１とを結ぶアークのアーク定義ウィンドウ
１３０７  トランジションload１のトランジション定義ウィンドウ
１４０１  アーク関連自動切断・接続処理
１５０１  発火可能性を調べるトランジション選択処理
１５０２  入力アーク処理
【図１】
0003943909.tif 000023
【図２】
0003943909.tif 000024
【図３】
0003943909.tif 000025
【図４】
0003943909.tif 000026
【図５】
0003943909.tif 000027
【図６】
0003943909.tif 000028
【図７】
0003943909.tif 000029
【図８】
0003943909.tif 000030
【図９】
0003943909.tif 000031
【図１０】
0003943909.tif 000032
【図１１】
0003943909.tif 000033
【図１２】
0003943909.tif 000034
【図１３】
0003943909.tif 000035
【図１４】
0003943909.tif 000036
【図１５】
0003943909.tif 000037