JP4138541B2 - Distributed path planning apparatus and method, and distributed path planning program - Google Patents

Description

ここに、Ｔ^ｋ _ｆｒｅｅは、ＡＧＶｋがその時点で搬送要求が割り当てられていない場合０となり、それ以外は、その時点からすでに割り当てられた搬送要求を搬送し終える時間を表す。Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}は、搬送要求がＡＧＶｋに割り当てられたときに搬送元までの移動に必要となる最小搬送時間を表す。
【００１７】
ここで、図４に、Ｔ^ｋ _ｆｒｅｅ及びＴ^ｋ _{ｍｉｎ ｐａｔｈ}の計算に用いるデータベースの説明図を示す。
以下に、Ｔ^ｋ _ｆｒｅｅの求め方を説明する。まず、データ構造として、ＡＧＶの時刻Ｔのノード番号がＲｏｕｔｅ［Ｔ］として用意されているものとする。Ｔ_ｆｒｅｅは、Ｒｏｕｔｅ［Ｔ］をＲｏｕｔｅ［１］から順に、Ｒｏｕｔｅ［２］、Ｒｏｕｔｅ［３］・・・という順序に検索していき、Ｒｏｕｔｅ［Ｔ］が最後に割り付けられた搬送要求の目的値ノード番号となる時刻ＴをＴ^ｋ _ｆｒｅｅとする。
つぎに、Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}の求め方を説明する。ＡＧＶにその時点ですでに割り付けられている搬送要求の目的値から次に割り付けられた搬送要求の搬送元までの最短距離をダイキストラ法のアルゴリズムを利用して求める。その結果、データ構造として、ＡＧＶの時刻Ｔのノード番号がＲｏｕｔｅ［Ｔ］で得られるとする。Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}は、Ｒｏｕｔｅ［Ｔ］をＲｏｕｔｅ［１］から順に、Ｒｏｕｔｅ［２］、Ｒｏｕｔｅ［３］・・・という順序に検索していき、Ｒｏｕｔｅ［Ｔ］が割り付けられた搬送要求先となる時刻Ｔとする。
つぎに、上述のフローに戻り、中央演算装置１は、搬送要求は、全てのＡＧＶを比較して、Ｅ_ｋが最も小さくなるＡＧＶに割り当てる（Ｓ１０３）。以上により、全てのＡＧＶの中から搬送時間が最短になると予想されるＡＧＶに搬送要求が割り当てられる。
【００１８】
２−２．ＡＧＶ
つぎに、各ＡＧＶの処理について説明する。
図５に、ＡＧＶの処理についてのフローチャートを示す。
ＡＧＶの分散型制御装置２は、中央演算装置１のデータベースにアクセスし、搬送要求が割り当てられたかどうか、又は、中央演算装置１から送信された搬送要求の割り当てを受信したかどうかを調べる（Ｓ２０１）。もし、割り当てられた搬送要求が存在すれば、分散型制御装置２は搬送要求（搬送指示）を受信し、記憶部２５に格納する（Ｓ２０２）。例えば、各分散型制御装置２の通信部２２は、中央演算装置１のデータベースにアクセスし、搬送要求（指示）データの有無を確認する。そして、搬送要求（指示）データが存在すれば、各分散型制御装置２は、データベースから搬送要求場所と搬送先、製品等の情報を読み込むことができる。そして、分散型制御装置２は、受信した搬送要求に従って、経路計画を実行する（Ｓ２０３）。経路計画が得られた時点で分散型制御装置２は表示装置３にその経路計画のデータを送り、経路計画結果を表示装置３で表示することができる（Ｓ２０４）。また、分散型制御装置２は、経路計画が終了すると同時に、ＡＧＶの制御部２４に動作指示を与える（Ｓ２０５）。
【００１９】
つぎに、図６に、経路計画作成処理のフローチャートを示す。この図は、上述のステップＳ２０３についての詳細フローチャートを示す。
本実施の形態における経路作成手段は、各ＡＧＶはまず、他のＡＧＶとの干渉を考慮せず、独自に経路を作成する。次に、全てのＡＧＶで得られた搬送経路は全ＡＧＶに情報交換される。しかしながら、ＡＧＶごとに作成された経路計画はほとんどの場合、ＡＧＶどうしが干渉し、実行不可能となる。そこで、各ＡＧＶはＡＧＶ間で干渉することに対するペナルティ関数を評価関数に組み込んで再経路計画を行う。このように、ＡＧＶ間の情報交換と各ＡＧＶでの再経路計画を最終的に実行可能な経路計画が得られるまで繰り返す。本アルゴリズムは、各ＡＧＶのアルゴリズムであるが、全てのＡＧＶで同一のアルゴリズムであるため、複数のＡＧＶに同一のアルゴリズムを用いることで全体の経路計画システムを構成することが可能である。
【００２０】
図７に、ＡＧＶのメモリフォーマットを示す。
分散型制御装置２は、搬送路のレイアウトを表すノード集合と、それらをつなぐアーク集合を予め記憶部２５内に格納している。なお、中央演算装置１のデータベースにも、全ＡＧＶに対してこれと同様のフォーマットの情報が記憶されている。このデータベースは、ＡＧＶのＩＤ(識別子)に対応して、初期値ノード、目的地ノード、初期方向、評価値、ＡＧＶｋとのペナルティ（Ｐｅｎａｌｔｙ［ｋ］）、経路更新情報、接触情報、収束情報、状態（搬送終了、待ち、経路計画中等）、経路（ノード番号、エリア情報、方向等）を含む。
【００２１】
分散型制御装置２は、以下の手順で経路計画を作成する。
（１）搬送要求入力（Ｓ１）
各分散型制御装置２は、中央演算装置１から送られる搬送指示を通信部２２又は記憶部２５により入力する（Ｓ１）。
（２）初期経路計画作成（Ｓ２）
各分散型制御装置２の経路最適化部２１は、他のＡＧＶとの衝突やすれ違い、又は、デッドロック等の干渉を考慮せず、各ＡＧＶで最適な経路、即ち搬送要求元から搬送先への最短経路を作成する（Ｓ２）。すなわち、経路最適化部２１は、他のＡＧＶとの干渉を考慮せずに、全ＡＧＶによる総搬送時間又は総搬送距離を最短とするように、当該ＡＧＶの搬送元から搬送先への最短経路を各ＡＧＶ独自の評価指標に基づき作成することで初期の経路計画を作成する。しかしながら、各ＡＧＶが他のＡＧＶを考慮せず経路を作成すれば、全体としてみた場合、不整合となる経路計画が得られる場合がある。なお、本実施の形態では、一例として、経路作成の処理に、ダイキストラ法を利用している。ここで、ダイキストラ法は、ノードとアーク（例、ノードとアーク間距離）の集合、及び評価関数が与えられたとき、初期ノードと目的地ノードを入力すれば、初期ノードから目的値ノードまでの最短経路を出力することができる処理方法である。なお、ダイキストラ法の処理アルゴリズムについては後述する。
【００２２】
（３）情報交換（Ｓ３）
分散型制御装置２の経路最適化部２１は、通信部２２による無線通信を利用して、他のＡＧＶの分散型制御装置２との間において、暫定的な経路計画を交換する（Ｓ３）。経路計画を交換すると、経路最適化部２１は情報交換回数ｉを１増加させる。次に、各ＡＧＶの通信部２２は、他の全てのＡＧＶからその時点での以下の情報を読み込み記憶部２５に記憶する。ただし、このとき、非同期通信を採用しているため、他のＡＧＶが経路計画途中であっても構わない。
・他のＡＧＶの暫定経路（時刻、ノード番号、ＡＧＶの方向）
・他のＡＧＶが経路計画の解を変更したかどうかを表すフラグ
・他のＡＧＶの経路計画が収束したかどうかを表すフラグ
・他のＡＧＶの情報交換回数
図８に、ＡＧＶのデータベースを示す。ＡＧＶの状態は、一例として、図８（ａ）に示すＡＧＶ状態データベースと、図８（ｂ）に示すＡＧＶ制御情報データベースの２つのデータベースで記述される。ＡＧＶ状態データベースは、ＡＧＶの識別子に対応して、時刻、ノード番号、向きを記憶したデータベースである。ＡＧＶ制御情報データベースは、ＡＧＶの識別子に対応して、情報交換回数、衝突判定フラグ、解変更フラグ、収束フラグを記憶したデータベースである。
なお、中央演算装置１は、経路計画処理を分散環境で実現するために他のＡＧＶの分散型経路制御装置２との情報伝達を行う手段として、他のＡＧＶの情報を記憶した共有リレーショナルデータベースを備え、この共有リレーショナルデータベースを利用して、常時複数の分散経路制御装置２から通信部２２によりアクセスを可能とすることで、情報交換を行うようにしてもよい。
【００２３】
（４）収束判定（Ｓ４）
分散協調部２３は、情報交換によって得られた情報を用いて収束判定を行い（Ｓ４）、収束していればステップＳ８に移る。収束していない場合は、ステップＳ５に移る。ここで、収束条件は、例えば、全ＡＧＶで再経路計画時に得られた経路が更新されず、かつＡＧＶどうしの干渉がないことである。分散協調部２３は、次の２つの条件のうち、いずれかの条件を満たした場合、収束と判定し、経路計画の計算を終了する。
（ｉ）他のＡＧＶと衝突やデッドロックを生じていない、かつ、他の全てのＡＧＶが解を変更していないこと
（ｉｉ）他の全てのＡＧＶの経路計画が収束していること
つぎに、図９に、衝突の判定の説明図を示す。ここで、分散協調部２３は、次のように衝突を判定する。まず、ＡＧＶをｋ、他のＡＧＶをｋ’、とする。時刻ＴにおけるＡＧＶｋの経路をノード番号Ｒ_ｋ［Ｔ］の集合、ＡＧＶｋ’の経路をノード番号Ｒ_ｋ’［Ｔ］の集合で表す。このとき、衝突しているかどうかは、Ｒ_ｋ［Ｔ］＝Ｒ_ｋ’［Ｔ］となるＴが存在するかどうかで判定する。
また、図１０に、すれちがいの判定の説明図を示す。分散協調部２３は、次のように、すれちがいを判定する。ＡＧＶをｋ、他のＡＧＶをｋ’とする。時刻ＴにおけるＡＧＶｋの経路をノード番号Ｒ_ｋ［Ｔ］の集合、ＡＧＶｋ’の経路をノード番号Ｒ_ｋ’［Ｔ］の集合で表す。このとき、すれちがいで衝突しているかどうかは、Ｒ_ｋ［Ｔ］＝Ｒ_ｋ’［Ｔ＋１］かつＲ_ｋ［Ｔ＋１］＝Ｒ_ｋ’［Ｔ］となるＴが存在するかどうかで判定する。
【００２４】
（５）ペナルティ関数の重み係数増加（Ｓ５）
ステップＳ２又は後述のステップＳ７で経路最適化部２１により得られた経路計画が実行不可能であれば、分散協調部２３は、干渉を生じているＡＧＶの分散型制御装置２のみ、経路計画の計算に用いられる評価関数Ｊ（後述の式（２）参照）中の他のＡＧＶとの干渉に対するペナルティ関数の重み係数であるαを所定値増加させ、更新する（Ｓ５）。この場合、衝突やデッドロック等の干渉が生じているＡＧＶの分散型制御装置２のみペナルティの重み係数を所定量増加させる。なお、ペナルティ関数は、例えば、一定値としてもよいし、他のＡＧＶと衝突していないとき０となり、衝突している場合は１となる関数を用いてもよい。また、ペナルティ関数は、他のＡＧＶとの間で生じた衝突ノード個数、他のＡＧＶとの間で生じたすれ違い回数、又はこれらの和とすることもできる。
【００２５】
（６）スキップ判定（Ｓ６）
各ＡＧＶの分散協調部２３は、次の再経路計画を確率的に飛ばし、ステップＳ３に進み（以後、この操作をスキップと呼ぶ）、一方、スキップしない場合はステップＳ７に移る（Ｓ６）。各分散協調部２３は、例えば、０から１の一様乱数を発生させ、ある予め定められた確率（以下、スキップ確率と呼ぶ）、スキップ確率と比較する。そして、乱数＜＝スキップ確率ならば、スキップ処理を実行する。
【００２６】
（７）再経路計画（Ｓ７）
ステップＳ６でスキップしないと判定されると、経路最適化部２１は、情報交換を行うことによって得られた情報を用いて、再経路計画を行う（Ｓ７）。再経路計画では、経路最適化部２１は、各ＡＧＶの搬送時間、及び他のＡＧＶとの衝突やデッドロック等の干渉に対するペナルティ関数の重みつき和を最小とする経路を作成する。すなわち、経路最適化部は、各ＡＧＶの搬送時間又は搬送距離と、分散協調部２３により求められたペナルティ関数を用いた評価関数に従い、全ＡＧＶによる総搬送時間又は総搬送距離を最短とするように、当該ＡＧＶの搬送元から搬送先への最短経路を導出して再び経路計画を作成する。例えば、経路最適化部２１は、情報交換（ステップＳ３）で得られた他のＡＧＶの経路情報から、他のＡＧＶが現在通っているノード間の距離の大きさをαだけ長く設定する。ノードｉからノードｊの距離をｄｉｊとするとき、もし情報交換によって得られた他のＡＧＶがノードｉからノードｊを通っていたとき、ノード間距離をｄｉｊ＋αとする。これによって、経路最適化部２１は、評価関数Ｊを最小とする最短経路をダイキストラ法を用いて導出することが可能となる。なお、評価関数Ｊは、次式により与えられる。
Ｊ＝（経路長）＋α（他のＡＧＶと干渉することに対するペナルティ） （２）

（８）搬送指示（Ｓ８）
経路最適化部２１は、得られた搬送経路を基にして、ＡＧＶの制御部２５に移動指示を与える（Ｓ８）。
【００２７】
２−３．ダイキストラ法
図１１に、ダイキストラ法のアルゴリズムの説明図を示す。
ノード集合をＰ、計算回数をｋ、ｋ回目の探索途中ノードをｉ_ｋとする。初期値ノードを０とし、任意のノード間の距離｛ｄ_ｉｊ｝を与えたとき、ダイキストラ法のアルゴリズムは、図示のようになる。ここで、Ｇ（ｉ）は、初期値ノードからノードｉまでの最短距離を表す。このアルゴリズムで、初期値ノードから任意のノードｎまでの最短距離Ｇ（ｎ）と最短経路を計算することができ、最短経路は、Ｈ（ｎ）で与えられる。
【００２８】
２−４．分散型経路計画の例
つぎに、図１２に、簡単な例題を用いたＡＧＶの分散型経路計画の説明図を示す。
ここでは、図のような簡単な搬送システムにおいて、２台のＡＧＶに矢印が示す搬送要求が与えられているという問題を考える。この問題に対して、本アルゴリズムを適用した際に得られるＡＧＶの経路計画の例を示す。初期経路計画の段階では各ＡＧＶは他のＡＧＶとの干渉を考慮せずに各ＡＧＶにとって最短となる経路を作成する（図１２（ａ））。ここで得られた経路は情報交換され、この情報に基づいて再経路計画が行われる。しかし、どちらのＡＧＶも同様に、干渉に対するペナルティをより少なくするために、次の再経路計画では図１２（ａ）と同様に干渉のある図１２（ｂ）で示す経路を作成する可能性が高い。また、図１２（ｂ）の経路計画が得られた場合、次の反復でも再び同様に図１２（ａ）に示す経路計画が作成される場合もある。このように、同じ実行不可能な経路が周期的に作成され、収束しなくなる場合がある。
【００２９】
図１３に、各ＡＧＶが作成する経路計画の評価値の変化を表す図を示す。反復回数が５回から１０回の付近で評価値が振動していることがわかる。このような状況を回避するために、確率的に（約２０％の確率）再経路計画をスキップする。このような処理を追加することにより、一方のＡＧＶの経路が回避され、図をみてもわかるように、一方の評価値が大きくなるが、これにより全体の収束を早め、本実施の形態の経路計画手順の収束性を高めることができる。この結果、図１２（ｃ）で示す経路計画を作成することができる。
つぎに、図１４に、図１で示した搬送システムに７台のＡＧＶが走行する際の分散型経路計画法の例の説明図を示す。
これは、図１の搬送システムにおける７台のＡＧＶの経路計画を分散型経路計画装置を用いて作成したものである。各矢印は、各ＡＧＶの移動経路を表す。図示の結果から、全てのＡＧＶは遠回りや回避移動を行うことなく最短経路で目的値に到達していることがわかる。
【００３０】
３．ＡＧＶの大きさ等を考慮した分散型経路計画
以下に、ＡＧＶの大きさを考慮した経路計画結果の実施の形態を説明する。
図１５（ａ）に、３台の移動ロボットと１２個のノードから構成される模擬搬送システム構成図、図１５（ｂ）に、実施に利用した移動ロボットの構成図を示す。搬送路は、横方向のノード間距離が３６０ｍｍ、縦方向のノード間距離が５００ｍｍであり、白線により構成されている。移動ロボットは、一辺が３００ｍｍの正方形であり、前部に白線を認識するフォトセンサが搭載されている。三つのタイヤのうち、後部の二つが動輪、前部の一つが操縦輪となっている。ターン時の回転中心は、二つの動輪間の中心点である。実験において、回転中心がノード上に一致した場合をＡＧＶの到着とし、ターン及び停止は、回転中心をノード上に一致させて行う。
【００３１】
図１４の経路計画では、比較的大規模な搬送路を対象としていたため、各ＡＧＶを点として扱え、同一ノード上に進入する場合と、隣接するノード間ですれ違いをする場合のみを衝突とみなしていた。しかしながら、実際の工場では搬送路の大きさやレイアウト等の制限のため、搬送路の大きさに比べ、ロボットの大きさが無視できない場合も存在する。その場合には、ロボットの大きさを考慮し、経路計画を行わなければならないが、本発明による経路計画手法はＡＧＶ毎に経路計画手段が独立しているために、このような変更に対しても、各ＡＧＶの経路計画手段を多少改良するだけで、簡単に対応することが可能である。改良点を以下に示す。
【００３２】
（１）占有領域の計算
図１６に、占有領域の説明図を示す。図１６（ａ）に、ＡＧＶが非回転の場合を、図１６（ｂ）に、回転の場合をそれぞれ示す。
占有領域は、ＡＧＶの四隅の座標から定義される。ただし、回転中は、図１６（ｂ）のように、実際にＡＧＶが存在しているよりも大きめに領域を確保している。これは、接触が生じやすい回転時に余裕を与えるためである。回転中以外では、四隅の座標により求められる四角形が占有領域となる。分散型制御装置２の分散協調部２３は、ダイキストラ法により計画した移動経路から、各時刻においてＡＧＶが占有する領域を計算する。
占有領域の計算は、ＡＧＶの形状とＡＧＶの中心位置からＡＧＶの占有領域を計算する。収束判定時には、占有領域の端点（Ａ、Ｂ、Ｃ、Ｄ）が他のＡＧＶの占有領域に入るかどうかで判定する。また、計算に用いるメモリフォーマットは、図７で説明したフォーマットと同一である。なお、この実施の形態では、一例として、占有領域が四角形であるＡＧＶについて説明しているが、このような判定の計算方法は、ＡＧＶの形状や回転位置に依存するので、上述の計算法を限定する必要はなく、適宜の計算法を用いて判定を行うことができる。
【００３３】
移動中におけるＡＧＶの状態は、次の三種類に分類され、それぞれの状態に対して、四隅座標の計算を行う。なお、計算は、情報交換で得た三つの情報を用いて行う。
（１−１）ＡＧＶの回転中心がノード上に存在する場合
ノード上におけるＡＧＶの方向は分かっているため、ノードの座標とＡＧＶの大きさからＡＧＶの四隅の座標を計算する。
（１−２）ノード間を移動している場合
（１−２−ａ）前ノードに到着した時刻と次のノードに到着した時刻の差から、ノード間の移動時間を求める。
（１−２−ｂ）ＡＧＶの移動速度は一定であると仮定しているため、前ノードと次ノードの座標の差から、一時刻分の移動量を求める。
（１−２−ｃ）前ノード上におけるＡＧＶの四隅の座標をスタート地点とし、移動中の各時刻におけるＡＧＶの四隅の座標を計算する。
（１−３）ノード上で方向転換をしている場合
（１−３−ａ）方向転換前の時刻と方向転換後の時刻の差から、方向転換に要する時刻を求める。
（１−３−ｂ）ＡＧＶの回転速度は一定であると仮定しているため、一時刻分の回転角度を求める。
（１−３−ｃ）ノードの座標（ＡＧＶの回転中心）とＡＧＶの大きさから、回転中の各時刻におけるＡＧＶの四隅の座標を求める。
【００３４】
（２）交換する情報
以上の説明では、各ＡＧＶが計画した移動経路を交換していたが、ここではそれの代わりに、各時刻において各ＡＧＶが占有する領域の交換を行う。各ＡＧＶは、その情報を用いて経路計画を行う。
ＡＧＶが搬送先に到着するまでに経由する全てのノードに対して、ＡＧＶの回転中心がノード上に到着する時刻、そのノード番号及びＡＧＶの方向の三つの情報を交換する。ただし、ノード上で方向転換する場合も、新たにノード上に到着したものと見なし、方向転換終了時の時刻、ノード番号及びＡＧＶの方向を交換する。（方向転換は９０度毎に分解する。つまり、１８０度回転は９０度回転が二回と見なす。）
【００３５】
（３）衝突の定義
図１７に、衝突の説明図を示す。
他のＡＧＶの占有領域内に自分の領域が侵入する場合を衝突と定義し、その場合に接触ペナルティを加える。
つぎに、図１８に、経路計画の実験結果の図を示す。以下に、ＡＧＶの大きさを考慮した経路計画の例について説明する。
この図は、分散型制御装置２によって得られた経路計画結果に従って、ＡＧＶを動作させたときの軌道を表す。経路計画は、３台のＡＧＶ＃１〜＃３に対して、それぞれ、初期ノードＳ１〜Ｓ３、目的地ノードＧ１〜Ｇ３、及び初期方向を与えて行った。初期方向とは、ＡＧＶが最初に向いている方向である。ターンに必要な時間は、ＡＧＶが１０ｍｍ移動するのに必要とする時間を１とし、実際の移動ロボットから、実験的に求めた。図（ａ）は、初期状態である。図（ｂ）、（ｃ）、・・・、（ｆ）に、時間ｔを経るにつれて、各ＡＧＶ＃１〜＃３が回転及び移動し、各々の動作における占有領域が示される。図（ｇ）に最終状態として、各ＡＧＶ＃１〜＃３が目的ノードに到達したことが示される。この例では、分散型制御装置２により各ＡＧＶに経路計画を行うことによって得られた経路にしたがって、ＡＧＶを走行させた結果、ＡＧＶ間の衝突やデッドロックの生じない経路が得られることが確認できる。
【００３６】
４．非同期による分散型経路計画
図１９に、非同期通信による経路計画の説明図を示す。図１９（ａ）は、同期的タイミングによる情報通信による計算時間を、図１９（ｂ）は、非同期による計算時間を示す。この図は、３台のＡＧＶの分散型制御装置の計算時間を表す。ＤＳＳ（分散サブシステム）は、各ＡＧＶの分散型制御装置２を表し、図中の□は情報通信時間、■は経路計画時間を表す。同期通信によるデータ交換では、分散型制御装置２を用いて並列的計算を実行したとき、各ＡＧＶで得られる経路の実行可能性を判定する場合には、計算の実行を同期化させる必要があった。これに対して、非同期通信によるデータ交換を用いると、データベースに保存されている１ステップ前の経路情報を利用することにより、他のＡＧＶの計算が終了していなくても、次のステップの計算を実行する非同期通信による並列計算が可能となる。ここで、各ＡＧＶがいったん収束条件を満たしてしたとしても、他のＡＧＶのうち、一つでも収束条件を満たさないＡＧＶが存在すれば計算を続けるという処理を加えることにより、非同期通信の場合でも収束が可能となる。図示のように、非同期通信を利用することにより、通信時の待ち時間が短縮化され、同期通信に比べ約１２％の計算時間の短縮が確認できる。
【００３７】
５．その他
本発明の分散型経路計画方法又は分散型経路計画装置・システムは、その各手順をコンピュータに実行させるための分散型経路計画プログラム、分散型経路計画プログラムを記録したコンピュータ読み取り可能な記録媒体、分散型経路計画プログラムを含みコンピュータの内部メモリにロード可能なプログラム製品、そのプログラムを含むサーバ等のコンピュータ、等により提供されることができる。
【００３８】
【発明の効果】
以上述べたように、本発明によれば、複数台の移動ロボットから構成される搬送システムにおける、分散型経路計画装置を開発した。本発明で開発した経路計画装置は、各ＡＧＶが独自の評価による経路の最適化と、他のＡＧＶとの情報交換を繰り返すことにより、最適に近い経路を計画する。半導体工場をモデルとした搬送システムにおいて数値実験を行った結果、１５台のＡＧＶが存在する場合においても、最適に近い経路計画を、５秒以下の計算時間で導出することができることが可能となった。同様の経路計画を、全ＡＧＶの経路計画を同時に最適化するホストコンピュータを用いて、混合整数計画問題に対する分枝限定法、遺伝的アルゴリズム、シミュレーティッドアニーリング法を利用して同様のプロセッサを利用して計算時間の比較を行った結果、同等の搬送時間の評価を有する結果の導出に、約１００００秒、約８００秒、及び約１００秒の計算時間を必要とした。
【００３９】
経路計画装置で得られた結果の妥当性を確認するため、模擬搬送路を用いた搬送実験に提案法を適用した。模擬搬送路では、ＡＧＶの大きさを考慮した経路計画を行うことが必要であるが、占有領域の計算、情報交換の変更、接触の定義の変更を行い、得られた結果を実際の移動ロボットで実行した結果、接触の生じない経路が得られることを確認した。
分散型経路計画装置は、ＡＧＶに組み込まれた複数のＣＰＵと無線による情報通信を利用した非同期通信による並列最適化計算アルゴリズムへの適用することにより、計算時間の大幅な削減が可能となり、搬送要求が時事刻々に発生する搬送環境へ適用することも可能である。したがって、本発明はより実用的な経路計画問題に対しても経路計画を極めて迅速に行うことが可能であり、その効果は極めて大きい。
【図面の簡単な説明】
【図１】半導体画像デバイス工場における格子状の搬送システムを模式化した図。
【図２】分散型経路計画装置の構成図。
【図３】中央演算装置の処理についてのフローチャート。
【図４】Ｔ^ｋ _ｆｒｅｅ及びＴ^ｋ _{ｍｉｎ ｐａｔｈ}の計算に用いるデータベースの説明図。
【図５】ＡＧＶの処理についてのフローチャート。
【図６】分散型経路計画のフローチャート。
【図７】ＡＧＶのメモリフォーマット。
【図８】ＡＧＶのデータベース。
【図９】衝突の判定の説明図。
【図１０】すれちがいの判定の説明図。
【図１１】ダイキストラ法のアルゴリズムの説明。
【図１２】簡単な例題を用いたＡＧＶの分散型経路計画の説明図。
【図１３】各ＡＧＶが作成する経路計画の評価値の変化を表す図。
【図１４】図１で示した搬送システムに７台のＡＧＶが走行する際の分散型経路計画法の例の説明図。
【図１５】３台の移動ロボットと１２個のノードから構成される模擬搬送システム構成図。
【図１６】占有領域の説明図。
【図１７】衝突の説明図。
【図１８】経路計画の実験結果の図。
【図１９】非同期通信による経路計画の説明図。
【符号の説明】
１ 中央演算装置
２ 分散型制御装置
３ 表示装置
２１ 経路最適化部
２２ 通信部
２３ 分散協調部
２４ 制御部
２５ 記憶部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a distributed route planning apparatus and method, and a distributed route planning program, and in particular, shortens a route plan that minimizes the total transport time or distance of a plurality of mobile robots, automatic guided vehicles, and other transport devices. The present invention relates to a distributed path planning apparatus and method, and a distributed path planning program that are created in time.
[0002]
[Prior art]
The semiconductor wafer manufacturing process is composed of a plurality of processes, and processing is performed in a clean room in order to avoid adhesion of dust. Further, in the interbay transport system, an automated guided vehicle (AGV) is widely used for transporting products between processes in order to eliminate product defects due to manual labor. In recent years, with the increase in wafer size and the increase in semiconductor demand, the enlargement of a clean room, the higher efficiency and higher density of an AGV transfer system are being promoted.
However, if the route planning of a plurality of AGVs is not performed properly, collisions and interferences will occur between AGVs, and products will not be transferred between processes, causing stagnation. Therefore, it is required to quickly obtain a route plan that shortens the conveyance time while avoiding the collision and interference between the AGVs while increasing the availability of the AGV.
Conventionally, the transport route planning has been treated as a minimization problem of the traveling route length represented by a planning problem (shortest route problem) of a traveling route to a plurality of destinations.
[0003]
The route planning means generally used is a centralized type that manages the positions of all AGVs in a clean room using a single host computer and performs route planning considering all AGVs simultaneously. It is based on a route planning system. For example, in Patent Document 1, for a plurality of AGVs, a candidate from a current position to a destination is expressed by a tree structure, and a search tree is registered while sequentially checking whether or not a collision occurs between AGVs. A centralized route planning method is adopted in which all AGV operations are deleted and searched collectively.
As a path planning method, an algorithm generally called a Dijkstra method is known. For example, Patent Document 2 discloses a route setting method by MPLS (Multiprotocol label switching) in an IP network using the Dijkstra method.
[0004]
[Patent Document 1]
JP-A-11-175153
[Patent Document 2]
JP 2002-247084 A
[0005]
[Problems to be solved by the invention]
However, the conventional route plan handled as a problem of minimizing the length of the traveling route is one in which one AGV circulates a plurality of processes and transports it, and in a plurality of AGVs that are performed in an actual clean room or the like. It is not about route planning.
Further, in the conventional centralized route planning system such as Patent Document 1, when the number of AGVs subject to route planning increases, the number of possible route candidates becomes enormous, and therefore an optimum route can be searched in a short time. Is extremely difficult. In addition, the conventional centralized route planning system requires information on the position and speed of all AGVs, and when an AGV failure or deviation from the plan occurs, it is necessary to re-create all the AGV plans from the beginning. Therefore, it is difficult to cope with various changes that occur in equipment.
In view of the above points, the present invention provides a transport system in which a plurality of autonomous mobile robots, radio transport vehicles (AGVs), and the like have a short route plan that minimizes the total transport time without colliding with each other. The purpose is to create. Further, according to the present invention, when a transport request is assigned to each AGV, the transport time of the AGV largely depends on the route selection from the initial position to the target position, so that interference between a plurality of AGVs does not occur. The purpose is to minimize the total transport time of all AGVs.
[0006]
It is another object of the present invention to create a route plan for all AGVs in a short calculation time by repeating information communication between each AGV using radio and asynchronous route plans and a route plan for each AGV. To do.
[0007]
[Means for Solving the Problems]
In order to achieve the above object, the present invention realizes a distributed path plan by the following means.
In the present invention, in particular, in a transport system using a plurality of AGVs that move on a transport path laid within a predetermined area, a transport request is generated, and the AGV located near the transport request generation point from the central controller. Each AGV is a distributed route plan determination / control device which can create a route plan having the shortest total transportation time when each of the AGVs has a route initializing position and a destination.
The distributed route planning apparatus according to the present invention includes, for example, a collision between a route optimization unit having a route plan optimization function based on an evaluation index unique to each AGV, and AGVs that occur when all AGVs are considered as route plans. In order to eliminate interference, all AGV's route plan is coordinated with other AGVs and the communication unit capable of performing information communication via radio or wire installed in AGV, and all AGV's And a distributed coordination unit capable of creating a route plan that does not cause deadlock.
[0008]
In the distributed route planning apparatus according to the present invention, a penalty function for an inconsistent route plan related to collision or interference with another AGV is introduced into an evaluation index unique to AGV, information exchange performed by information communication means, and each AGV By repeatedly executing the re-route search of multiple times, the weighting coefficient of the penalty function is gradually increased at each AGV, and the inconsistent route plan is resolved in a distributed cooperative manner while maintaining the optimality of the generated route. Make it possible.
In the implementation of the distributed route planning apparatus according to the present invention, the information communication between the AGVs and the route planning system of each AGV is introduced into each AGV in the processor, and information on the state of each other is communicated at asynchronous timing. Each AGV can be executed while advancing the calculation asynchronously and parallelly without waiting for the completion of the calculation in the other AGV.
In the distributed route planning apparatus according to the present invention, as a method for the route plan obtained by each AGV to converge to an executable route plan, for example, a process of skipping the creation of a route plan stochastically at a certain stage And a condition that each AGV derives the same route plan and a condition that interference does not occur with other AGVs are used as convergence conditions, so that even when executing asynchronous optimization calculation, It is possible to provide distributed coordination means that enables convergence to a path plan that does not cause any collision or interference.
[0009]
As a means for the distributed path planning apparatus according to the present invention to communicate information with other AGV distributed path planning apparatuses, the central processing unit uses a shared relational database to constantly access from a plurality of distributed path planning apparatuses. The communication means provided with the information communication function which enables is provided.
The distributed path planning apparatus according to the present invention controls the time required for rotation of the AGV and the timing of movement in consideration of the direction, size, speed, etc. of the AGV itself to avoid deadlock and collision between the AGVs. It is possible to do.
The distributed route planning apparatus according to the present invention determines the inconsistency of the route plan when a plurality of transport requests are given from moment to moment or when the route needs to be changed, and the route plan is consistent. By fixing the operation of a certain AGV and only the AGV that creates an inconsistent route plan performs the route plan again, it is possible to re-do the route plan with only local changes without changing the route plan of all AGVs. It is possible to shorten the calculation time.
Therefore, a route plan that is the shortest when viewed from each AGV is created using a device for information communication installed in each AGV and a device for route planning of each AGV, and information communication and reroute are performed. Each time the plan is repeated by parallel calculation, each AGV gradually increases the penalty for collision and interference with other AGVs, thereby creating a consistent route plan for all AGVs in a short time in a distributed environment. can do.
[0010]
  According to the first solution of the present invention,
In a transport system using a plurality of transport devices that move along a transport path laid within a predetermined area, a distributed path planning device provided in each of the transport devices,
When a transport request including a transport source and a transport destination is given from the central processing unit to a transport device located in the vicinity of the transport source, the total transport time or total transport distance of all the transport devices is set to the shortest. A route optimization unit for optimizing the route plan by creating the shortest route based on an evaluation index unique to each transport device;
A communication unit for communicating status information including the position and route plan of each transport device with other transport devices or a central processing unit;
Based on the status information communicated by the communication unit, it determines the interference and / or deadlock between transfer devices caused by the route plan of all transfer devices created by the route optimization unit, and changes the evaluation index of the route plan Then, by selecting, under a predetermined condition, whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit, so that interference and / or deadlock does not occur in the entire transport device A decentralized coordination unit for optimizing route planning and cooperating with other transport devices;
With

The communication unit obtains a transport request including a transport source and a transport destination sent from the central processing unit,
The route optimization unit minimizes the total transport time or total transport distance of all transport devices from the transport source to the transport destination without considering interference with other transport devices. Create an initial route plan by creating a route based on each transport device's unique evaluation index,
The communication unit obtains information on the route plan including the position and route of all other transport devices and the presence or absence of changes in the route plan of all other transport devices,
The distributed coordination unit increases the weighting factor of the penalty function related to the interference with the other transport device in the evaluation function used for creating the route plan when the interference with the other transport device and / or the deadlock occurs. Let
The distributed coordination unit probabilistically skips the next process of creating a route plan again according to a predetermined criterion,
The route optimization unit creates a route that minimizes the transport function or transport distance of each transport device and the evaluation function using the penalty function obtained by the distributed coordination unit, and the total transport time or total transport time of all transport devices. Deriving the shortest route from the transfer source to the transfer destination of the transfer device so as to make the transfer distance the shortest, create a route plan again,
The distributed coordinating unit determines whether there is interference and / or deadlock with other transport devices and whether there is a change in the route plan of all other transport devices, and determines the convergence of the route plan based on the determination result. And
The route optimization unit gives a conveyance instruction to the control unit of the conveyance device based on the obtained shortest route when the route plan has converged for all the conveyance devices.
A distributed path planning device is provided.
[0011]
  According to the second solution of the present invention,
In a transport system using a plurality of transport devices that move along a transport path laid within a predetermined area, a distributed path planning device provided in each of the transport devices,
When a transport request including a transport source and a transport destination is given from the central processing unit to a transport device located in the vicinity of the transport source, the total transport time or total transport distance of all the transport devices is set to the shortest. A route optimization unit for optimizing the route plan by creating the shortest route based on an evaluation index unique to each transport device;
A communication unit for communicating status information including the position and route plan of each transport device with other transport devices or a central processing unit;
Based on the status information communicated by the communication unit, it determines the interference and / or deadlock between transfer devices caused by the route plan of all transfer devices created by the route optimization unit, and changes the evaluation index of the route plan Then, by selecting, under a predetermined condition, whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit, so that interference and / or deadlock does not occur in the entire transport device A decentralized coordination unit for optimizing route planning and cooperating with other transport devices;
A distributed path planning method in a distributed path planning apparatus comprising: a distributed path planning program for causing a computer to execute the following steps:

The communication unit obtains a transport request including a transport source and a transport destination sent from the central processing unit;
The route optimization unit minimizes the total transport time or total transport distance of all the transport devices from the transport source to the transport destination without considering interference with other transport devices. Creating an initial route plan by creating a route based on an evaluation index unique to each transport device; and
The communication unit obtains information on a route plan including the positions and routes of all other transport devices and whether or not the route plan of all other transport devices has been changed, and
The dispersion coordination unit increases the weighting factor of the penalty function related to the interference with the other transport device in the evaluation function used for creating the route plan when the interference and / or deadlock with the other transport device occurs. Step to
The distributed coordination unit skips probabilistically skipping the next process of creating a route plan again according to a predetermined criterion;
The route optimization unit creates a route that minimizes the transport function or transport distance of each transport device and the evaluation function using the penalty function obtained by the distributed coordination unit, and the total transport time or total transport time of all transport devices. Deriving the shortest route from the transfer source of the transfer device to the transfer destination so as to make the transfer distance the shortest, and creating a route plan again;
The distributed coordinating unit determines whether there is interference and / or deadlock with other transport devices and whether there is a change in the route plan of all other transport devices, and determines the convergence of the route plan based on the determination result. And steps to
The route optimization unit, when the route plan has converged for all the transport device, based on the obtained shortest route, giving a transport instruction to the control unit of the transport device;
Including a distributed path planning method and a distributed path planning program for causing a computer to execute these steps.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
1. Distributed path planning device
FIG. 1 is a diagram schematically showing a lattice-shaped transport system in a semiconductor image device factory.
The transport system includes a node and an arc, the node represents a place where the work place or the AGV can change direction, and the arc represents a path that can move between the nodes. When the initial node and destination node of each AGV are given, the AGV selects a route that does not cause a collision or interference between the AGVs and transports the package to the destination node. Here, as an example, it is assumed that the conveyance path can travel in two directions, and only one AGV can stand by at each node. In addition, it is assumed that two AGVs cannot pass on each arc.
In the present embodiment, an AGV in a transport system such as a semiconductor factory will be described as an example. However, the distributed path planning apparatus and method of the present invention and the distributed path planning program are used in a transport system such as a semiconductor factory. However, the present invention can be applied to route planning of an appropriate transport system, and is not limited to a mobile robot or AGV, and can be applied to an appropriate transport device.
Next, FIG. 2 shows a configuration diagram of the distributed path planning apparatus. The distributed route planning apparatus according to the present embodiment is roughly divided into a central processing unit 1, a distributed control device 2 for each AGV, and a display device 3 for displaying a route plan result.
[0013]
The central processing unit 1 has a database function for managing the layout of the conveyance path and the conveyance request, and a function for assigning the conveyance request to each AGV. When the transport request is given, the central processing unit 1 transmits the transport initial point and the transport destination point to the AGV located near the transport request point. The database in the central processing unit 1 includes, as data related to the transport request, data related to AGV such as initial points of each AGV, transport destination points, speed and size of each AGV, route planning data planned for each AGV, operation / Accumulate state data relating to AGV state such as rotation and orientation.
The distributed control device 2 is installed in each AGV, and a route optimization unit 21 capable of creating an optimum route plan for each AGV, and a communication unit 22 having a wireless or wired communication function with a shared database or another AGV. And a distributed cooperation unit 23 having a route plan convergence processing function, a control unit 24 that controls the travel of the AGV according to the planned route plan, and a storage unit 25 that stores various data.
[0014]
  The route optimization unit 21 of each AGV generates an optimum route plan that minimizes the transport time or route length from the initial location of each AGV to the destination from among a plurality of route candidates, such as the Dijkstra method based on the principle of optimality, etc. The optimal solution is derived using the numerical programming method.When the transport request including the transport source and the transport destination is given from the central processing unit 1 to the AGV located near the transport source, the route optimization unit 21 shortens the total transport time or the total transport distance by all the AGVs. The route plan is optimized by creating the shortest route of each AGV based on the evaluation index unique to each AGV. The communication unit 22 communicates status information including the position and route plan of each AGV with other AGVs or the central processing unit 1.Each AGV can obtain information from the database of the central processing unit 1 and other AGVs by the communication unit 22. The communication unit 22 performs asynchronous communication processing when executing parallel computation. The communication unit 22 preferably performs wireless communication, but may perform priority communication. The distributed cooperation unit 23 includes a cooperation mechanism for eliminating inconsistencies with a route plan created by the distributed control device 2 in another AGV, a convergence determination function for optimization calculation based on asynchronous timing, and the like.Based on the state information communicated by the communication unit 22, the distributed coordination unit 23 determines interference and / or deadlock between AGVs caused by the route plan of all AGVs created by the route optimization unit 21. By changing the evaluation index of the plan and selecting whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit 21, interference is not caused as all AGVs. Optimize path planning and collaborate with other AGVs.The control unit 24 has a function of controlling traveling of the AGV according to the created route plan. As will be described later, the storage unit 25 includes various databases such as an AGV information database and an AGV control information database.
  The display device 3 has a function of displaying a route plan result obtained by each AGV.
[0015]
2. Distributed route planning process
2-1. Central processing unit
FIG. 3 shows a flowchart of processing of the central processing unit.
The central processing unit 1 and the AGV have a database capable of storing a plurality of transport requests. When performing a route plan, first, the generation of a transport request is waited (S101). When a transport request occurs, the central processing unit 1 stores a transport source node and a transport destination node where the transport request has occurred in an internal database.
Next, for all AGVs, the transport time E of each AGVk is given by the following equation:_kIs calculated (S102).
[0016]
[Expression 1]

Where T^k _freeIndicates 0 when AGVk has not been assigned a transfer request at that time, and otherwise indicates the time to finish transferring the already assigned transfer request from that time. T^k _{min path}Represents the minimum transport time required for movement to the transport source when the transport request is assigned to AGVk.
[0017]
Here, in FIG.^k _freeAnd T^k _{min path}The explanatory view of the database used for calculation of is shown.
T^k _freeExplain how to find out. First, it is assumed that a node number at time T of AGV is prepared as Route [T] as a data structure. T_freeSearches for Route [T] in order of Route [1], Route [2], Route [3]..., And Route [T] is the target value node of the transport request assigned last. Time T to be number is T^k _freeAnd
Next, T^k _{min path}Explain how to find out. The shortest distance from the target value of the transport request already allocated to the AGV at that time to the transport source of the next allocated transport request is obtained using the Dijkstra algorithm. As a result, it is assumed that the node number at time T of AGV is obtained as Route [T] as the data structure. T^k _{min path}Search for Route [T] in order of Route [1], Route [2], Route [3]..., And the time T that is the transport request destination to which Route [T] is assigned. To do.
Next, returning to the above-described flow, the central processing unit 1 compares all AGVs with the transfer request,_kIs assigned to the AGV having the smallest value (S103). As described above, a transport request is assigned to an AGV that is expected to have the shortest transport time among all AGVs.
[0018]
2-2. AGV
Next, processing of each AGV will be described.
FIG. 5 shows a flowchart of AGV processing.
The distributed control device 2 of the AGV accesses the database of the central processing unit 1 and checks whether or not a transport request has been assigned, or whether or not the transport request assignment transmitted from the central processing device 1 has been received (S201). ). If there is an assigned transfer request, the distributed control device 2 receives the transfer request (transfer instruction) and stores it in the storage unit 25 (S202). For example, the communication unit 22 of each distributed control device 2 accesses the database of the central processing unit 1 and confirms the presence / absence of transfer request (instruction) data. If there is transfer request (instruction) data, each distributed control device 2 can read information such as the transfer request location, transfer destination, and product from the database. Then, the distributed control device 2 executes route planning according to the received transport request (S203). When the route plan is obtained, the distributed control device 2 can send the route plan data to the display device 3 and display the route plan result on the display device 3 (S204). Further, the distributed control device 2 gives an operation instruction to the AGV control unit 24 at the same time as the route planning is completed (S205).
[0019]
Next, FIG. 6 shows a flowchart of the route plan creation process. This figure shows the detailed flowchart about the above-mentioned step S203.
In the route creation means in the present embodiment, each AGV first creates a route independently without considering interference with other AGVs. Next, the transport routes obtained by all AGVs are exchanged with all AGVs. However, in most cases, the route plan created for each AGV becomes infeasible because the AGVs interfere with each other. Therefore, each AGV incorporates a penalty function for interference between the AGVs into the evaluation function and performs reroute planning. As described above, the information exchange between the AGVs and the reroute plan in each AGV are repeated until a path plan that can be finally executed is obtained. Although this algorithm is an algorithm of each AGV, since it is the same algorithm for all AGVs, it is possible to configure the entire route planning system by using the same algorithm for a plurality of AGVs.
[0020]
FIG. 7 shows an AGV memory format.
The distributed control device 2 stores in advance in the storage unit 25 a node set that represents the layout of the transport path and an arc set that connects them. The database of the central processing unit 1 also stores information in the same format for all AGVs. This database corresponds to an AGV ID (identifier), an initial value node, a destination node, an initial direction, an evaluation value, a penalty with AGVk (Penalty [k]), route update information, contact information, convergence information, The status (conveyance end, waiting, route planning, etc.) and route (node number, area information, direction, etc.) are included.
[0021]
  The distributed control device 2 creates a route plan according to the following procedure.
(1) Transport request input (S1)
Each distributed control device 2 inputs a conveyance instruction sent from the central processing unit 1 through the communication unit 22 or the storage unit 25 (S1).
(2) Preparation of initial route plan (S2)
  The route optimizing unit 21 of each distributed control device 2 does not take into account collisions with other AGVs or interference such as deadlock, and the optimum route in each AGV, that is, from the transfer request source to the transfer destination. The shortest path is created (S2).That is, the route optimization unit 21 does not consider interference with other AGVs, and the shortest route from the transport source of the AGV to the transport destination so as to minimize the total transport time or the total transport distance of all AGVs. Is created based on an evaluation index unique to each AGV to create an initial route plan.However, if each AGV creates a route without considering other AGVs, a route plan that is inconsistent when viewed as a whole may be obtained. In this embodiment, as an example, the Dijkstra method is used for the route creation process. Here, in the Dijkstra method, given a set of nodes and arcs (for example, distance between nodes and arcs) and an evaluation function, if an initial node and a destination node are input, the initial node to the target value node are input. This is a processing method capable of outputting the shortest path. The processing algorithm of the Dijkstra method will be described later.
[0022]
(3) Information exchange (S3)
  The route optimization unit 21 of the distributed control device 2 exchanges a temporary route plan with the distributed control device 2 of another AGV using the wireless communication by the communication unit 22 (S3). When the route plans are exchanged, the route optimization unit 21 increases the information exchange number i by one. Next, the communication unit 22 of each AGV reads the following information at that time from all the other AGVs and stores it in the storage unit 25. However, since asynchronous communication is adopted at this time, other AGVs may be in the middle of route planning.
・ Provisional route of other AGV (time, node number, direction of AGV)
A flag indicating whether another AGV has changed the route plan solution
-Flag indicating whether the path plan of other AGV has converged
・ Information exchange times of other AGVs
  FIG. 8 shows an AGV database. As an example, the AGV state is described in two databases, an AGV state database shown in FIG. 8A and an AGV control information database shown in FIG. 8B. The AGV state database is a database that stores time, node number, and direction corresponding to the identifier of AGV. The AGV control information database is a database that stores information exchange times, collision determination flags, solution change flags, and convergence flags in correspondence with the identifiers of AGVs.
  The centerCalculationThe apparatus 1 includes a shared relational database that stores information on other AGVs as means for transmitting information with the distributed path control apparatus 2 of other AGVs in order to realize path planning processing in a distributed environment. Information may be exchanged by using the relational database to always allow access from the plurality of distributed path control devices 2 by the communication unit 22.
[0023]
(4) Convergence determination (S4)
The distribution coordinating unit 23 performs convergence determination using information obtained by information exchange (S4), and if converged, proceeds to step S8. If not converged, the process proceeds to step S5. Here, the convergence condition is, for example, that the route obtained at the time of reroute planning is not updated for all AGVs and that there is no interference between AGVs. If any of the following two conditions is satisfied, the distribution coordination unit 23 determines that the convergence has occurred, and ends the calculation of the route plan.
(I) There is no collision or deadlock with other AGVs, and all other AGVs have not changed the solution.
(Ii) All other AGV path plans have converged
Next, FIG. 9 shows an explanatory diagram of collision determination. Here, the distributed coordination unit 23 determines a collision as follows. First, AGV is k, and the other AGV is k ′. The route of AGVk at time T is the node number R_kThe set of [T], the route of AGVk ′, the node number R_{k '}[T] represents a set. At this time, it is R_k[T] = R_{k '}Judgment is made based on whether or not T which is [T] exists.
FIG. 10 is an explanatory diagram for determining passing. The distributed cooperation unit 23 determines passing as follows. Let AGV be k and other AGV be k '. The route of AGVk at time T is the node number R_kThe set of [T], the route of AGVk ′, the node number R_{k '}[T] represents a set. At this time, it is R_k[T] = R_{k '}[T + 1] and R_k[T + 1] = R_{k '}Judgment is made based on whether or not T which is [T] exists.
[0024]
(5) Penalty function weight coefficient increase (S5)
If the route plan obtained by the route optimization unit 21 in step S2 or step S7, which will be described later, cannot be executed, the distributed coordination unit 23 determines that only the AGV distributed control device 2 causing the interference Α, which is a weighting factor of the penalty function for interference with other AGVs in the evaluation function J (see formula (2) described later) used in the calculation, is updated by a predetermined value (S5). In this case, the penalty weighting factor is increased by a predetermined amount only in the AGV distributed control device 2 in which interference such as collision or deadlock occurs. The penalty function may be a constant value, for example, or may be a function that becomes 0 when there is no collision with another AGV and becomes 1 when there is a collision. Also, the penalty function may be the number of collision nodes generated with other AGVs, the number of times of passing between other AGVs, or the sum thereof.
[0025]
(6) Skip determination (S6)
The distributed coordination unit 23 of each AGV skips the next reroute plan stochastically and proceeds to step S3 (hereinafter, this operation is referred to as skip). On the other hand, if not skipped, the process proceeds to step S7 (S6). Each distributed coordination unit 23 generates, for example, a uniform random number from 0 to 1, and compares it with a predetermined probability (hereinafter referred to as skip probability) and skip probability. If random number <= skip probability, skip processing is executed.
[0026]
(7) Reroute plan (S7)
  If it is determined not to skip in step S6, the route optimization unit 21 performs re-route planning using information obtained by exchanging information (S7). In the reroute plan, the route optimization unit 21 creates a route that minimizes the weighted sum of the penalty function for the transport time of each AGV and interference such as collision with other AGVs and deadlock.That is, the route optimizing unit makes the total transport time or total transport distance by all AGVs the shortest according to the transport function or transport distance of each AGV and the evaluation function using the penalty function obtained by the distribution coordination unit 23. Then, the shortest route from the transportation source of the AGV to the transportation destination is derived and a route plan is created again.For example, the route optimization unit 21 sets the length of the distance between the nodes through which the other AGV currently passes from the route information of the other AGV obtained by the information exchange (step S3) longer by α. When the distance from the node i to the node j is dij, if another AGV obtained by the information exchange passes from the node i to the node j, the distance between the nodes is dij + α. Accordingly, the route optimization unit 21 can derive the shortest route that minimizes the evaluation function J using the Dijkstra method. The evaluation function J is given by the following equation.
J = (path length) + α (penalty for interference with other AGV) (2)

(8) Transport instruction (S8)
  The route optimization unit 21 gives a movement instruction to the control unit 25 of the AGV based on the obtained transport route (S8).
[0027]
2-3. Daikistra method
FIG. 11 is an explanatory diagram of the algorithm of the Dijkstra method.
P is the node set, k is the number of calculations, and i is the k-th searching node_kAnd The initial value node is 0, and the distance between any nodes {d_ij}, The algorithm of the Dijkstra method is as shown in the figure. Here, G (i) represents the shortest distance from the initial value node to node i. With this algorithm, the shortest distance G (n) and the shortest path from the initial value node to an arbitrary node n can be calculated, and the shortest path is given by H (n).
[0028]
2-4. Example of distributed path planning
Next, FIG. 12 shows an explanatory diagram of AGV's distributed path planning using a simple example.
Here, consider the problem that a transport request indicated by an arrow is given to two AGVs in a simple transport system as shown in the figure. An example of an AGV route plan obtained when this algorithm is applied to this problem will be described. At the initial route planning stage, each AGV creates the shortest route for each AGV without considering interference with other AGVs (FIG. 12A). Information obtained here is exchanged, and reroute planning is performed based on this information. However, both AGVs may create the path shown in FIG. 12B having interference as in FIG. 12A in the next reroute plan in order to reduce the penalty for interference. high. When the route plan of FIG. 12B is obtained, the route plan shown in FIG. 12A may be created again in the next iteration. In this way, the same infeasible route is periodically created and may not converge.
[0029]
FIG. 13 is a diagram showing a change in the evaluation value of the route plan created by each AGV. It can be seen that the evaluation value oscillates when the number of iterations is around 5 to 10. To avoid this situation, reroute planning is skipped stochastically (approximately 20% probability). By adding such processing, the path of one AGV is avoided and, as can be seen from the figure, the evaluation value of one increases, but this speeds up the overall convergence, and the path of the present embodiment The convergence of the planning procedure can be improved. As a result, the route plan shown in FIG. 12C can be created.
Next, FIG. 14 shows an explanatory diagram of an example of a distributed route planning method when seven AGVs travel in the transport system shown in FIG.
This is a route plan for seven AGVs in the transport system of FIG. 1 created using a distributed route planner. Each arrow represents a movement route of each AGV. From the results shown in the figure, it can be seen that all the AGVs have reached the target value through the shortest route without making a detour or avoiding movement.
[0030]
3. Distributed route planning considering the size of AGV
In the following, an embodiment of a route plan result in consideration of the size of AGV will be described.
FIG. 15A shows a block diagram of a simulated transfer system composed of three mobile robots and 12 nodes, and FIG. 15B shows a block diagram of the mobile robot used for implementation. The transport path has a distance between nodes of 360 mm in the horizontal direction and a distance between nodes of 500 mm in the vertical direction, and is configured by white lines. The mobile robot is a square with a side of 300 mm, and a photosensor that recognizes a white line is mounted on the front. Of the three tires, the rear two are the driving wheels and the front one is the control wheel. The center of rotation at the turn is the center point between the two driving wheels. In the experiment, when the rotation center coincides with the node, it is determined that the AGV has arrived, and the turn and stop are performed with the rotation center coincident with the node.
[0031]
Since the route plan in FIG. 14 is intended for a relatively large transport route, each AGV can be treated as a point, and only a case of entering on the same node and a case of passing between adjacent nodes is regarded as a collision. It was. However, in actual factories, there are cases where the size of the robot cannot be ignored compared to the size of the transfer path due to restrictions on the size and layout of the transfer path. In that case, the route planning must be performed in consideration of the size of the robot. However, the route planning method according to the present invention has independent route planning means for each AGV. However, it is possible to easily cope with the problem by slightly improving the route planning means of each AGV. The improvements are shown below.
[0032]
(1) Calculation of occupied area
FIG. 16 is an explanatory diagram of the occupied area. FIG. 16A shows a case where the AGV is not rotated, and FIG. 16B shows a case where it is rotated.
The occupied area is defined from the coordinates of the four corners of the AGV. However, during rotation, as shown in FIG. 16B, an area larger than the actual AGV is secured. This is because a margin is given at the time of rotation where contact is likely to occur. When not rotating, a quadrangle obtained from the coordinates of the four corners is the occupied area. The distributed cooperation unit 23 of the distributed control device 2 calculates the area occupied by the AGV at each time from the movement route planned by the Dijkstra method.
In the calculation of the occupied area, the occupied area of the AGV is calculated from the shape of the AGV and the center position of the AGV. At the time of convergence determination, the determination is made based on whether the end points (A, B, C, D) of the occupied area enter the occupied areas of other AGVs. The memory format used for the calculation is the same as the format described in FIG. In this embodiment, an AGV whose occupation area is a quadrangle is described as an example. However, since the calculation method for such determination depends on the shape and rotation position of the AGV, the above calculation method is used. It is not necessary to limit, and determination can be performed using an appropriate calculation method.
[0033]
The state of the AGV during movement is classified into the following three types, and four corner coordinates are calculated for each state. The calculation is performed using three pieces of information obtained by information exchange.
(1-1) When the rotation center of AGV exists on the node
Since the direction of the AGV on the node is known, the coordinates of the four corners of the AGV are calculated from the coordinates of the node and the size of the AGV.
(1-2) When moving between nodes
(1-2-a) The movement time between nodes is obtained from the difference between the time of arrival at the previous node and the time of arrival at the next node.
(1-2b) Since the movement speed of the AGV is assumed to be constant, the movement amount for one time is obtained from the difference between the coordinates of the previous node and the next node.
(1-2c) Using the coordinates of the four corners of the AGV on the previous node as the start point, calculate the coordinates of the four corners of the AGV at each moving time.
(1-3) When changing direction on a node
(1-3-a) The time required for the direction change is obtained from the difference between the time before the direction change and the time after the direction change.
(1-3-b) Since it is assumed that the rotational speed of the AGV is constant, the rotational angle for one time is obtained.
(1-3-c) The coordinates of the four corners of the AGV at each time during rotation are obtained from the coordinates of the node (the center of rotation of the AGV) and the size of the AGV.
[0034]
(2) Information to be exchanged
In the above description, the movement route planned by each AGV is exchanged, but here, instead, the area occupied by each AGV is exchanged at each time. Each AGV performs route planning using the information.
For all nodes through which the AGV arrives at the transport destination, three pieces of information of the time when the rotation center of the AGV arrives on the node, its node number, and the direction of the AGV are exchanged. However, when the direction is changed on the node, it is assumed that the node has newly arrived on the node, and the time at the end of the direction change, the node number, and the AGV direction are exchanged. (The direction change is disassembled every 90 degrees. That is, 180 degree rotation is regarded as 90 degree rotation twice.)
[0035]
(3) Definition of collision
FIG. 17 shows an explanatory diagram of the collision.
A collision is defined as a case where one's own area enters another AGV's occupied area, and in that case, a contact penalty is added.
Next, FIG. 18 shows a diagram of a route planning experiment result. Hereinafter, an example of a route plan in consideration of the size of AGV will be described.
This figure shows the trajectory when the AGV is operated according to the path planning result obtained by the distributed control device 2. The route planning was performed by giving initial nodes S1 to S3, destination nodes G1 to G3, and an initial direction to the three AGVs # 1 to # 3, respectively. The initial direction is the direction in which the AGV first faces. The time required for the turn was determined experimentally from an actual mobile robot, with the time required for the AGV to move 10 mm as 1. FIG. 1A shows an initial state. (B), (c),..., (F), the AGVs # 1 to # 3 rotate and move with time t, and the occupied area in each operation is shown. FIG. 5 (g) shows that each AGV # 1 to # 3 has reached the target node as the final state. In this example, it is confirmed that, as a result of running the AGV according to the route obtained by performing the route planning to each AGV by the distributed control device 2, a route that does not cause a collision or deadlock between the AGVs is obtained. it can.
[0036]
4). Asynchronous distributed path planning
FIG. 19 is an explanatory diagram of route planning by asynchronous communication. FIG. 19 (a) shows the calculation time for information communication at the synchronous timing, and FIG. 19 (b) shows the calculation time for asynchronous. This figure represents the calculation time of three AGV distributed controllers. DSS (Distributed Subsystem) represents the distributed control device 2 of each AGV, □ in the figure represents information communication time, and ■ represents path planning time. In data exchange by synchronous communication, when executing parallel computation using the distributed control device 2, it is necessary to synchronize the execution of the computation when determining the feasibility of the path obtained by each AGV. It was. On the other hand, when data exchange by asynchronous communication is used, the calculation of the next step is performed even if the calculation of another AGV is not completed by using the route information of the previous step stored in the database. Parallel computation by asynchronous communication that executes is possible. Here, even if each AGV once satisfies the convergence condition, even if there is an AGV that does not satisfy the convergence condition among other AGVs, the calculation is continued, so even in the case of asynchronous communication. Convergence is possible. As shown in the figure, by using asynchronous communication, the waiting time at the time of communication is shortened, and it can be confirmed that the calculation time is reduced by about 12% compared to the synchronous communication.
[0037]
5. Other
A distributed path planning method or distributed path planning apparatus / system according to the present invention includes a distributed path planning program for causing a computer to execute each procedure, a computer-readable recording medium on which the distributed path planning program is recorded, distributed It can be provided by a program product that includes the type path planning program and can be loaded into the internal memory of the computer, a computer such as a server that includes the program, and the like.
[0038]
【The invention's effect】
As described above, according to the present invention, a distributed path planning apparatus has been developed in a transfer system including a plurality of mobile robots. The route planning apparatus developed in the present invention plans a route close to the optimum by each AGV repeatedly optimizing the route based on its own evaluation and exchanging information with other AGVs. As a result of a numerical experiment in a transport system modeled on a semiconductor factory, even when 15 AGVs exist, it is possible to derive a route plan close to the optimum with a calculation time of 5 seconds or less. It was. Using a similar processor using a branch and bound method, a genetic algorithm, and a simulated annealing method for a mixed integer programming problem, using a host computer that simultaneously optimizes the path plan of all AGVs. As a result of the comparison of the calculation times, the calculation times of about 10,000 seconds, about 800 seconds, and about 100 seconds were required to derive the results having the same conveyance time evaluation.
[0039]
In order to confirm the validity of the results obtained by the route planning device, the proposed method was applied to a transport experiment using a simulated transport path. In the simulated transport path, it is necessary to perform a route plan considering the size of the AGV. However, the occupied area is calculated, the information exchange is changed, the contact definition is changed, and the obtained result is used as an actual mobile robot. As a result of executing the above, it was confirmed that a route without contact was obtained.
The distributed path planning device can greatly reduce the calculation time by applying it to the parallel optimization calculation algorithm by asynchronous communication using multiple CPUs built into AGV and wireless information communication. It is also possible to apply it to a transport environment where time is generated. Therefore, the present invention can perform route planning very quickly even for more practical route planning problems, and the effect is extremely large.
[Brief description of the drawings]
FIG. 1 is a schematic view of a lattice-shaped transport system in a semiconductor image device factory.
FIG. 2 is a configuration diagram of a distributed path planning apparatus.
FIG. 3 is a flowchart for processing of the central processing unit.
FIG. 4 T^k _freeAnd T^k _{min path}Explanatory drawing of the database used for calculation.
FIG. 5 is a flowchart for AGV processing;
FIG. 6 is a flowchart of distributed path planning.
FIG. 7 shows an AGV memory format.
FIG. 8 is a database of AGV.
FIG. 9 is an explanatory diagram of collision determination.
FIG. 10 is an explanatory diagram of determination of passing.
FIG. 11 explains an algorithm of the Dijkstra method.
FIG. 12 is an explanatory diagram of AGV's distributed path planning using a simple example.
FIG. 13 is a diagram illustrating a change in an evaluation value of a route plan created by each AGV.
14 is an explanatory diagram of an example of a distributed route planning method when seven AGVs travel on the transport system shown in FIG. 1. FIG.
FIG. 15 is a configuration diagram of a simulated transport system including three mobile robots and 12 nodes.
FIG. 16 is an explanatory diagram of an occupied area.
FIG. 17 is an explanatory diagram of a collision.
FIG. 18 is a diagram of a route planning experiment result.
FIG. 19 is an explanatory diagram of route planning by asynchronous communication.
[Explanation of symbols]
1 Central processing unit
2 Distributed controller
3 display devices
21 Route Optimization Department
22 Communication Department
23 Distributed Cooperation Department
24 Control unit
25 storage unit

Claims (20)

In a transport system using a plurality of transport devices that move along a transport path laid within a predetermined area, a distributed path planning device provided in each of the transport devices,
When a transport request including a transport source and a transport destination is given from the central processing unit to a transport device located in the vicinity of the transport source, the total transport time or total transport distance of all the transport devices is set to the shortest. A route optimization unit for optimizing the route plan by creating the shortest route based on an evaluation index unique to each transport device;
A communication unit for communicating status information including the position and route plan of each transport device with other transport devices or a central processing unit;
Based on the status information communicated by the communication unit, it determines the interference and / or deadlock between transfer devices caused by the route plan of all transfer devices created by the route optimization unit, and changes the evaluation index of the route plan Then, by selecting, under a predetermined condition, whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit, so that interference and / or deadlock does not occur in the entire transport device With a distributed coordination unit for optimizing the route plan and cooperating with other transport devices,

The communication unit obtains a transport request including a transport source and a transport destination sent from the central processing unit,
The route optimization unit minimizes the total transport time or total transport distance of all transport devices from the transport source to the transport destination without considering interference with other transport devices. Create an initial route plan by creating a route based on each transport device's unique evaluation index,
The communication unit obtains information on the route plan including the position and route of all other transport devices and the presence or absence of changes in the route plan of all other transport devices ,
The distributed coordination unit increases the weighting factor of the penalty function related to the interference with the other transport device in the evaluation function used for creating the route plan when the interference with the other transport device and / or the deadlock occurs. Let
The distributed coordination unit probabilistically skips the next process of creating a route plan again according to a predetermined criterion,
The route optimization unit creates a route that minimizes the transport function or transport distance of each transport device and the evaluation function using the penalty function obtained by the distributed coordination unit, and the total transport time or total transport time of all transport devices. Deriving the shortest route from the transfer source to the transfer destination of the transfer device so as to minimize the transfer distance, create a route plan again,
The distributed coordinating unit determines whether there is interference and / or deadlock with other transport devices and whether there is a change in the route plan of all other transport devices, and determines the convergence of the route plan based on the determination result. And
The route optimization unit gives a conveyance instruction to the control unit of the conveyance device based on the obtained shortest route when the route plan has converged for all the conveyance devices.
Distributed path planning device. The communication unit communicates information about the route plan of all transport devices between the transport devices; and
The route optimization unit and the distributed coordination unit execute optimization calculation in each transport device;
The distributed route planning apparatus according to claim 1, wherein an optimum route plan that minimizes the total transport time in a short time is obtained by repeating the above. The distributed coordination unit introduces a penalty function for an inconsistent route plan related to interference with other transport devices and / or deadlocks into an evaluation index unique to the transport device, and based on information received by the communication unit, interference And / or increasing the weighting factor of the penalty function of the transfer device causing the deadlock in each transfer device,
The route optimization unit executes a reroute plan in each transfer device based on the set penalty function,
The distributed path planning apparatus according to claim 1, wherein inconsistent path plans are resolved in a distributed cooperative manner while maintaining the optimality of the generated paths. The distribution coordinating unit executes skip processing that probabilistically skips the creation of a reroute plan at a certain stage so that the route plan obtained by each transport device converges to an executable route plan. Distributed path planning device. The information communication unit communicates information about each state at asynchronous timing, and the route optimization unit and the distributed coordination unit execute route planning asynchronously and parallelly in a distributed environment in each transport device. A distributed path planning apparatus according to claim 1. The distributed coordination unit
Claims with a convergence function that enables the inconsistent route plan generated by each transport device to be resolved in a distributed manner based on the evaluation index unique to each transport device and to determine the feasibility of the route plan Item 2. The distributed path planning apparatus according to Item 1. The distributed coordination unit
(I) a condition that there is no interference with other transport devices, and that each transport device derives the same route plan from the previous time, or
(Ii) a condition that no interference occurs with other transport apparatuses and that the route plans of all other transport apparatuses are converged;
2. The distributed path plan according to claim 1, wherein it is converged to a path plan that does not cause interference and / or deadlock with other transport apparatuses by determining that one of the conditions is satisfied as a convergence condition. apparatus. Claims for avoiding deadlock or collision between transfer devices by controlling the time required for rotation of the transfer device or the timing of movement in consideration of one or more of the direction, size, speed of the transfer device itself The distributed path planning apparatus according to 1. The information on the route plan further includes information on the occupation area of the transfer device at each time,
The distributed coordination department
From the coordinate information of the four corners of the transport device, calculate the occupation area when it exists on the node, when moving between nodes, and / or when turning around on the node,
The interference between the transfer devices is determined by the occupied area.
The distributed path planning apparatus according to claim 1. The route planning means performs only a local route change only when a transfer request is given from moment to moment, or when a route change occurs, only the transfer device causing the interference performs a reroute plan. The distributed path planning apparatus according to claim 1, which enables a path selection that can be performed in a short time without redoing the path planning. The route optimization unit receives a transport source and transport destination, a transport path node and distance between nodes, and an evaluation index, and derives the shortest path from the transport source node to the transport destination node based on the input information. The distributed path planning apparatus according to claim 1, wherein the shortest path is calculated using a Dijkstra method. The central processing unit includes a shared relational database that stores information on other transport devices as means for communicating information with a distributed route plan device of another transport device in order to realize the route plan means in a distributed environment. ,
The distributed path planning apparatus according to claim 1, wherein the communication unit is always accessed from a plurality of distributed path planning apparatuses using the shared relational database of the central processing unit. The central processing unit has a database that stores state information including position information corresponding to the identifier of each transport device, and is located near the transport source and transported from the transport source in accordance with a given transport instruction. The distributed path planning device according to claim 1, wherein a transport device having a minimum value according to the minimum transport time required for previous transport is determined and a transport request is given to the transport device. In a transport system using a plurality of transport devices that move along a transport path laid within a predetermined area, a distributed path planning device provided in each of the transport devices,
When a transport request including a transport source and a transport destination is given from the central processing unit to a transport device located in the vicinity of the transport source, the total transport time or total transport distance of all the transport devices is set to the shortest. A route optimization unit for optimizing the route plan by creating the shortest route based on an evaluation index unique to each transport device;
A communication unit for communicating status information including the position and route plan of each transport device with other transport devices or a central processing unit;
Based on the status information communicated by the communication unit, it determines the interference and / or deadlock between transfer devices caused by the route plan of all transfer devices created by the route optimization unit, and changes the evaluation index of the route plan Then, by selecting, under a predetermined condition, whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit, so that interference and / or deadlock does not occur in the entire transport device A distributed route planning method in a distributed route planning device comprising a distributed coordination unit for optimizing a route plan and cooperating with other transport devices,

The communication unit obtains a transport request including a transport source and a transport destination sent from the central processing unit;
The route optimization unit minimizes the total transport time or total transport distance of all transport devices from the transport source to the transport destination without considering interference with other transport devices. Creating an initial route plan by creating a route based on an evaluation index unique to each transport device; and
The communication unit obtains information on a route plan including the positions and routes of all other transport devices and whether or not the route plan of all other transport devices has been changed , and
The distributed coordination unit increases the weighting factor of the penalty function related to the interference with the other transport device in the evaluation function used for creating the route plan when the interference with the other transport device and / or the deadlock occurs. Step to
The distributed coordination unit skips probabilistically skipping the next process of creating a route plan again according to a predetermined criterion;
The route optimization unit creates a route that minimizes the transport function or transport distance of each transport device and the evaluation function using the penalty function obtained by the distributed coordination unit, and the total transport time or total transport time of all transport devices. Deriving the shortest route from the transfer source of the transfer device to the transfer destination so as to make the transfer distance the shortest, and creating a route plan again;
The distributed coordinating unit determines whether there is interference and / or deadlock with other transport devices and whether there is a change in the route plan of all other transport devices, and determines the convergence of the route plan based on the determination result. And steps to
The route optimization unit, when the route plan has converged for all the transport device, based on the obtained shortest route, giving a transport instruction to the control unit of the transport device;
A distributed path planning method including: Information related to the route plan includes a provisional route related to the route plan , a flag indicating whether or not the route plan of all other transport devices has been changed, a flag indicating whether or not the other transport devices have converged, and information on other transport devices The distributed path planning method according to claim 14, comprising the number of exchanges. 15. The distributed path planning method according to claim 14, wherein the distributed coordination unit skips the next reroute planning process by generating a random number and comparing it with a predetermined skip probability. The information on the route plan further includes information on the occupation area of the transfer device at each time,
The distributed coordination department
From the coordinate information of the four corners of the transport device, calculating the occupied area when it exists on the node, when moving between nodes, and / or when turning around on the node;
Determining the interference between the conveying devices by the occupied area;
The distributed path planning method according to claim 14, comprising: The information about the occupied area relates to the time when the rotation center of the transfer device arrives on the node, the node number, and the direction of the transfer device for all the nodes through which the transfer device arrives at the transfer destination. The distributed path planning method according to claim 17, comprising information. When a transport request occurs, the central computer determines when each transport device finishes transporting the transport request that has already been assigned since the transport request occurs, and when the transport request is assigned to the transport device, Determining a transport device having a minimum value according to the minimum transport time required for transport from the transport destination to the transport destination;
The distributed route planning method according to claim 14, further comprising a step of assigning a transport request to a corresponding transport device. In a transport system using a plurality of transport devices that move along a transport path laid within a predetermined area, a distributed path planning device provided in each of the transport devices,
When a transport request including a transport source and a transport destination is given from the central processing unit to a transport device located in the vicinity of the transport source, the total transport time or total transport distance of all the transport devices is set to the shortest. A route optimization unit for optimizing the route plan by creating the shortest route based on an evaluation index unique to each transport device;
A communication unit for communicating status information including the position and route plan of each transport device with other transport devices or a central processing unit;
Based on the status information communicated by the communication unit, it determines the interference and / or deadlock between transfer devices caused by the route plan of all transfer devices created by the route optimization unit, and changes the evaluation index of the route plan Then, by selecting, under a predetermined condition, whether or not to optimize the route plan again based on the evaluation index changed by the route optimization unit, so that interference and / or deadlock does not occur in the entire transport device A distributed route planning program for causing a computer to execute each of the following steps in a distributed route planning device including a distributed coordination unit for optimizing a route plan and cooperating with other transport devices,

The communication unit obtains a transport request including a transport source and a transport destination sent from the central processing unit;
The route optimization unit minimizes the total transport time or total transport distance of all transport devices from the transport source to the transport destination without considering interference with other transport devices. Creating an initial route plan by creating a route based on an evaluation index unique to each transport device; and
The communication unit obtains information on a route plan including the positions and routes of all other transport devices and whether or not the route plan of all other transport devices has been changed , and
The distributed coordination unit increases the weighting factor of the penalty function related to the interference with the other transport device in the evaluation function used for creating the route plan when the interference with the other transport device and / or the deadlock occurs. Step to
The distributed coordination unit skips probabilistically skipping the next process of creating a route plan again according to a predetermined criterion;
The route optimization unit creates a route that minimizes the transport function or transport distance of each transport device and the evaluation function using the penalty function obtained by the distributed coordination unit, and the total transport time or total transport time of all transport devices. Deriving the shortest route from the transfer source of the transfer device to the transfer destination so as to make the transfer distance the shortest, and creating a route plan again;
The distributed coordinating unit determines whether there is interference and / or deadlock with other transport devices and whether there is a change in the route plan of all other transport devices, and determines the convergence of the route plan based on the determination result. And steps to
The route optimization unit, when the route plan has converged for all the transport device, based on the obtained shortest route, giving a transport instruction to the control unit of the transport device;
Distributed path planning program that causes a computer to execute.

Images