JP2004280213A - 分散型経路計画装置及び方法、分散型経路計画プログラム - Google Patents

Abstract

【課題】複数台のＡＧＶ等の搬送装置が、互いに衝突することなく総搬送時間を最短とする経路計画を短時間で作成すること。
【解決手段】分散型制御装置２は、各ＡＧＶ独自の評価指標に基づく経路計画最適化機能を備えた経路最適化部２１、全ＡＧＶの経路計画を無線を介して情報通信する通信部２２、他のＡＧＶとの協調をはかりながら、全ＡＧＶとして干渉やデッドロックを生じない経路計画を作成可能な分散協調部２３を有する。各ＡＧＶに設置された分散型経路計画装置２が、各ＡＧＶの経路計画の最適化と無線による非同期的なタイミングでの情報通信を繰り返すことにより、他のＡＧＶとの干渉に対するペナルティを徐々に増加させていくことと、確率的に経路の作成をスキップするという処理により、全体としてＡＧＶ間の干渉を生じることなく総搬送時間を最短とする経路計画を短い計算時間で作成する。
【選択図】 図２

Description

【０００１】
【発明の属する技術分野】
本発明は、分散型経路計画装置及び方法、分散型経路計画プログラムに係り、特に、複数台の移動ロボットや自動無人搬送車等の搬送装置の総搬送時間又は距離を最短とする経路計画を短時間で作成する分散型経路計画装置及び方法、分散型経路計画プログラムに関する。
【０００２】
【従来の技術】
半導体ウエハ製造プロセスは、複数の工程から構成され、ほこりの付着を避けるため、クリーンルーム内で処理が行われる。また、インターベイ搬送システムでは、人手による製品不良をなくすため、工程間の製品の搬送には自動無人搬送車（ＡＧＶ：Ａｕｔｏｍａｔｅｄ Ｇｕｉｄｅｄ Ｖｅｈｉｃｌｅ）が広く一般に利用される。また、近年、ウエハサイズの拡大と半導体需要の増加に伴い、クリーンルームの大規模化、ＡＧＶ搬送システムの高効率化、高密度化が進められている。
しかしながら、複数台ＡＧＶの経路計画を適切に行わなければ、ＡＧＶ間で衝突や干渉を起こし、工程間に製品が移送されなくなり、ものの停滞を引き起こす。そこで、ＡＧＶの稼働率を高めながら搬送時間を短縮し、ＡＧＶ間の衝突や干渉を回避した経路計画を迅速に得ることが求められている。
従来、搬送経路計画は、複数の目的地への巡回路の計画問題（最短路問題）に代表される巡回経路長の最小化問題として取り扱われてきた。
【０００３】
また、一般に用いられている経路計画手段は、クリーンルーム内に存在する全てのＡＧＶの位置を一つのホストコンピュータを用いて管理し、全てのＡＧＶを同時に考慮して経路計画を行おうとする集中型の経路計画システムを基本としている。例えば、特許文献１参照では、複数のＡＧＶに対して、現在地から目的地までの経路候補を木構造で表現し、ＡＧＶ間で衝突が生じないかどうかを逐次チェックしながら、探索木を登録、削除し、全てのＡＧＶの動作を一括して探索するという集中型経路計画法が採用されている。
また、経路計画法としては、一般にダイキストラ法と呼ばれるアルゴリズムが知られている。例えば、特許文献２参照には、ダイキストラ法を用いたＩＰネットワークにおけるＭＰＬＳ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ ｌａｂｅｌ ｓｗｉｔｃｈｉｎｇ）による経路設定方法が開示されている。
【０００４】
【特許文献１】
特開平１１−１７５１５３号公報
【特許文献２】
特開２００２−２４７０８４号公報
【０００５】
【発明が解決しようとする課題】
しかしながら、従来の巡回経路長の最小化問題として取り扱う経路計画は、一台のＡＧＶが複数の工程を巡回して搬送を行うものであり、実際のクリーンルーム等で行われている複数台のＡＧＶでの経路計画についてのものではない。
また、特許文献１のような従来の集中型経路計画システムでは、経路計画対象となるＡＧＶ台数が増加したとき、可能な経路の候補が膨大となるため、最適な経路を短時間で探索することは極めて難しい。また、従来の集中型経路計画システムは、全てのＡＧＶの位置や速度等に関する情報が必要となり、ＡＧＶの故障や計画からのずれが生じた際、全てのＡＧＶの計画を始めから作成しなおす必要が生じるため、設備で生じるさまざまな変化に対応することが難しい。
本発明は、以上の点に鑑み、搬送システムにおいて、複数台の自律移動ロボット、無線搬送車（ＡＧＶ）等の搬送装置が、互いに衝突することなく総搬送時間を最短とする経路計画を短時間で作成することを目的とする。また、本発明は、搬送要求が各ＡＧＶへ割当てられたとき、ＡＧＶの搬送時間は、初期位置から目的位置までの経路選択に大きく依存するため、複数のＡＧＶ間の干渉を生じないように、全ＡＧＶの総搬送時間を最短とすることを目的とする。
【０００６】
さらに、本発明は、無線を用いた各ＡＧＶ間の非同期的タイミングによる情報通信と各ＡＧＶの経路計画を繰り返すことにより、全てのＡＧＶの経路計画を短時間の計算時間で作成することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は、上記のような目的を達成するため、次のような手段により分散型経路計画を実現するものである。
本発明は、特に、所定の領域内で敷設された搬送路を移動する複数のＡＧＶを用いた搬送システムにおいて、搬送要求が発生し、中央制御装置から搬送要求発生地点の近傍に位置するＡＧＶに搬送初期位置と目的地が与えられたとき、各ＡＧＶはそれぞれに経路計画手段を有し、総搬送時間を最短とする経路計画を作成可能な分散型経路計画決定・制御装置である。
本発明に関する分散型経路計画装置は、例えば、各ＡＧＶ独自の評価指標に基づく経路計画最適化機能を備えた経路最適化部と、全てのＡＧＶの経路計画としてみた際に生じるＡＧＶ間の衝突や干渉をなくすため、全ＡＧＶの経路計画をＡＧＶに設置された無線又は有線を介して情報通信を行うことのできる通信部と、及び、他のＡＧＶとの協調をはかりながら、全ＡＧＶとして干渉やデッドロックを生じない経路計画を作成可能な分散協調部とを有する。
【０００８】
本発明に関する分散型経路計画装置において、ＡＧＶ独自の評価指標に他のＡＧＶとの衝突や干渉に関する不整合な経路計画に対するペナルティ関数を導入し、情報通信手段によって行われる情報の授受と各ＡＧＶでの再経路探索を複数回繰り返して実行することにより、そのペナルティ関数の重み係数を各ＡＧＶで次第に増加させ、生成される経路の最適性を保ちながら不整合な経路計画を分散協調的に解消することを可能とする。
本発明に関する分散型経路計画装置の実装において、ＡＧＶ間の情報通信と各ＡＧＶの経路計画システムを分散させた各々のＡＧＶにプロセッサに導入し、互いの状態に関する情報を非同期タイミングで通信することにより、各ＡＧＶが他のＡＧＶでの計算終了を待つことなく非同期並列的に計算を進めながら実行することを可能とする。
本発明に関する分散型経路計画装置において、各ＡＧＶで得られる経路計画が、実行可能な経路計画に収束するための方法として、例えば、ある段階において確率的に経路計画の作成を飛ばす、スキップという処理を行うことと、各ＡＧＶが同一の経路計画を導出するという条件、及び他のＡＧＶと干渉を生じないという条件を収束条件とすることにより、非同期最適化計算実行時においても、他のＡＧＶとの衝突や干渉を生じない経路計画に収束させることを可能とする分散協調手段を備えることができる。
【０００９】
本発明に関する分散型経路計画装置が他のＡＧＶの分散型経路計画装置との情報伝達を行う手段として、中央処理装置に共有リレーショナルデータベースを利用して、常時複数の分散経路計画装置からのアクセスを可能とする情報通信機能を備えた通信手段を備えることができる。
本発明に関する分散型経路計画装置は、ＡＧＶ自体の向きや大きさ、速度等を考慮して、ＡＧＶの回転に必要な時間、移動するタイミングを制御して、ＡＧＶ間のデッドロックや衝突を回避することを可能とする。
本発明に関する分散型経路計画装置は、搬送要求が時々刻々と複数で与えられたとき、あるいは経路変更の必要性が生じたとき、経路計画の不整合を判断し、整合のとれた経路計画であるＡＧＶの動作を固定し、不整合な経路計画を作成するＡＧＶのみが経路計画を再び行うことによって、全てのＡＧＶの経路計画を変更せず、局所的な変更のみで経路計画をやり直すことで計算時間の短縮をはかることを可能とする。
従って、各ＡＧＶに設置された情報通信のための装置と各ＡＧＶの経路計画のための装置を利用して各ＡＧＶからみたときに最短となる経路計画を作成しておき、情報通信と再経路計画を並列計算により繰り返すごとに、各ＡＧＶが他のＡＧＶとの衝突や干渉に対するペナルティを除々に増加させることで、全てのＡＧＶとして整合性のとれた経路計画を分散環境において短い計算時間で作成することができる。
【００１０】
本発明の第１の解決手段によると、
所定の領域内で敷設された搬送路を移動する複数の搬送装置を用いた搬送システムにおいて、前記搬送装置の各々に備えられた分散型経路計画装置であって、中央制御装置から、搬送元及び搬送先を含む搬送要求が、搬送元の近傍に位置する搬送装置に与えられたとき、全搬送装置による総搬送時間又は総搬送距離を最短とする各搬送装置の最短経路を各搬送装置独自の評価指標に基づき作成することにより、経路計画を最適化するための経路最適化部と、
各搬送装置の位置及び経路計画を含む状態情報を、他の搬送装置又は中央制御装置と通信するための通信部と、
前記通信部で通信した状態情報に基づき、前記経路最適化部により作成された全ての搬送装置の経路計画により生じる搬送装置間の干渉及び／又はデッドロックを判定し、経路計画の評価指標を変更し、前記経路最適化部で変更された評価指標に基づき再び経路計画を最適化するか否かを所定の条件で選択することにより、全搬送装置として干渉を生じないように経路計画を最適化して他の搬送装置と協調するための分散協調部と
を備えた分散型経路計画装置が提供される。
【００１１】
本発明の第２の解決手段によると、
各搬送装置独自の評価指標に基づく経路計画を最適化するための経路最適化部と、全ての搬送装置の経路計画において生じる搬送装置間の干渉及び／又はデッドロックをなくすために全搬送装置の経路計画に関する情報を通信するための通信部と、他の搬送装置との協調をはかりながら全搬送装置として干渉及び／又はデッドロックを生じない経路計画を作成するための分散協調部と備えた分散型経路計画装置における分散型経路計画方法であって、
通信部は、中央演算装置から送られる搬送元及び搬送先を含む搬送要求を得るステップと、
経路最適化部は、他の搬送装置との干渉を考慮せずに、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を各搬送装置独自の評価指標に基づき作成することで初期の経路計画を作成するステップと、
無線通信部は、他の全ての搬送装置の位置及び経路計画に関する情報を得るステップと、
分散協調部は、他の搬送装置との干渉及び／又はデッドロック、及び、最短経路の解の変更状態を判断し、その判断結果に基づき、経路計画の収束を判定するステップと、
分散協調部は、干渉及び／又はデッドロックを生じている場合、経路計画の作成に用いられる評価関数中の他の搬送装置との干渉に関するペナルティ関数の重み係数を増加させるステップと、
分散協調部は、次の再経路計画処理を予め定められた基準により確率的にスキップするステップと、
経路最適化部は、分散協調部により求められたペナルティ関数を用いた評価関数に従い、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を導出して再び経路計画するステップと、
経路最適化部は、経路計画が全ての搬送装置について収束した場合、得られた最短経路に基づき、搬送装置の制御部に搬送指示を与えるステップと
を含む分散型経路計画方法、及び、これら各ステップをコンピュータに実行させるための分散型経路計画プログラムが提供される。
【００１２】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
１．分散型経路計画装置
図１は、半導体画像デバイス工場における格子状の搬送システムを模式化した図である。
搬送システムは、ノードとアークを備え、ノードは、作業場やＡＧＶが方向転換可能な場所を表し、アークは、ノード間で移動可能な経路を表す。ＡＧＶは、各ＡＧＶの初期ノードと目的地ノードが与えられたとき、ＡＧＶ間の衝突や干渉のない経路を選択して、目的地ノードへ荷物を搬送する。ここで、一例として、搬送路は２方向走行が可能であるものとし、各ノードでは、１台のＡＧＶのみが待機できるものとする。また、各アーク上では２台のＡＧＶのすれ違いは不可能であるとする。
なお、本実施の形態では、一例として、半導体工場等の搬送システムにおけるＡＧＶを対象に説明するが、本発明の分散型経路計画装置及び方法、分散型経路計画プログラムは、半導体工場等の搬送システムに限定されるものではなく、適宜の搬送システムの経路計画に適用することができ、さらに、移動ロボットやＡＧＶに限定されず、適宜の搬送装置に適用することができる。
つぎに、図２に、分散型経路計画装置の構成図を示す。本実施の形態における分散型経路計画装置は、大きく分けて、中央演算装置１と、各ＡＧＶの分散型制御装置２と、経路計画結果を表示する表示装置３とを備える。
【００１３】
中央演算装置１は、搬送路のレイアウトや搬送要求を管理するデータベース機能と、搬送要求を各ＡＧＶへ割当てる機能とを有する。搬送要求が与えられたとき、中央演算装置１は、搬送要求地点近傍に位置するＡＧＶに搬送初期地点と搬送先地点を伝達する。中央演算装置１におけるデータベースは、搬送要求に関するデータとして、各ＡＧＶの初期地点、搬送先地点、各ＡＧＶの速度及びサイズ等のＡＧＶに関するデータ、及び、各ＡＧＶで計画された経路計画データ、動作・回転・向き等のＡＧＶの状態に関する状態データを蓄積する。
分散型制御装置２は、各ＡＧＶに設置され、各ＡＧＶの最適な経路計画を作成可能な経路最適化部２１と、共有データベースや他のＡＧＶとの無線又は有線による通信機能を有する通信部２２と、経路計画の収束処理機能を有する分散協調部２３と、計画された経路計画に従ってＡＧＶの走行を制御する制御部２４と、各種データを記憶する記憶部２５とを備える。
【００１４】
各ＡＧＶの経路最適化部２１は、複数の経路候補の中から各ＡＧＶの初期地から目的地までの搬送時間又は経路長を最短とする最適な経路計画を最適性の原理に基づくダイキストラ法等の数値計画法を用いて最適解を導出する。各ＡＧＶは、通信部２２により、中央演算装置１のデータベース及び他のＡＧＶから情報を得ることが可能である。通信部２２は、並列計算を実行する際の非同期での通信処理を行う。なお、通信部２２は、無線通信を行うものが好ましいが、優先通信を行うものでもよい。分散協調部２３は、他のＡＧＶにおける分散制型御装置で作成された経路計画との不整合をなくすための協調機構や、非同期タイミングによる最適化計算に対する収束判定機能等を備える。制御部２４は、作成された経路計画に従って、ＡＧＶの走行を制御する機能を備えている。記憶部２５は、後述するように、ＡＧＶ情報データベース、ＡＧＶ制御情報データベース等の各種データベースを含む。
表示装置３は、各ＡＧＶで得られた経路計画結果を表示する機能を有する。
【００１５】
２．分散型経路計画処理
２−１．中央演算装置
図３に、中央演算装置の処理についてのフローチャートを示す。
中央演算装置１及びＡＧＶは、複数個の搬送要求を格納可能なデータベースを有している。経路計画を行う場合は、まず搬送要求の発生を待つ（Ｓ１０１）。中央演算装置１は、搬送要求が発生した場合は、その搬送要求が発生した搬送元ノードと搬送先ノードを内部のデータベースに格納する。
つぎに、全てのＡＧＶに対して、次式により各ＡＧＶｋの搬送所要時間Ｅ_ｋを計算する（Ｓ１０２）。
【００１６】
【数１】

ここに、Ｔ^ｋ _ｆｒｅｅは、ＡＧＶｋがその時点で搬送要求が割り当てられていない場合０となり、それ以外は、その時点からすでに割り当てられた搬送要求を搬送し終える時間を表す。Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}は、搬送要求がＡＧＶｋに割り当てられたときに搬送元までの移動に必要となる最小搬送時間を表す。
【００１７】
ここで、図４に、Ｔ^ｋ _ｆｒｅｅ及びＴ^ｋ _{ｍｉｎ ｐａｔｈ}の計算に用いるデータベースの説明図を示す。
以下に、Ｔ^ｋ _ｆｒｅｅの求め方を説明する。まず、データ構造として、ＡＧＶの時刻Ｔのノード番号がＲｏｕｔｅ［Ｔ］として用意されているものとする。Ｔ_ｆｒｅｅは、Ｒｏｕｔｅ［Ｔ］をＲｏｕｔｅ［１］から順に、Ｒｏｕｔｅ［２］、Ｒｏｕｔｅ［３］・・・という順序に検索していき、Ｒｏｕｔｅ［Ｔ］が最後に割り付けられた搬送要求の目的値ノード番号となる時刻ＴをＴ^ｋ _ｆｒｅｅとする。
つぎに、Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}の求め方を説明する。ＡＧＶにその時点ですでに割り付けられている搬送要求の目的値から次に割り付けられた搬送要求の搬送元までの最短距離をダイキストラ法のアルゴリズムを利用して求める。その結果、データ構造として、ＡＧＶの時刻Ｔのノード番号がＲｏｕｔｅ［Ｔ］で得られるとする。Ｔ^ｋ _{ｍｉｎ ｐａｔｈ}は、Ｒｏｕｔｅ［Ｔ］をＲｏｕｔｅ［１］から順に、Ｒｏｕｔｅ［２］、Ｒｏｕｔｅ［３］・・・という順序に検索していき、Ｒｏｕｔｅ［Ｔ］が割り付けられた搬送要求先となる時刻Ｔとする。
つぎに、上述のフローに戻り、中央演算装置１は、搬送要求は、全てのＡＧＶを比較して、Ｅ_ｋが最も小さくなるＡＧＶに割り当てる（Ｓ１０３）。以上により、全てのＡＧＶの中から搬送時間が最短になると予想されるＡＧＶに搬送要求が割り当てられる。
【００１８】
２−２．ＡＧＶ
つぎに、各ＡＧＶの処理について説明する。
図５に、ＡＧＶの処理についてのフローチャートを示す。
ＡＧＶの分散型制御装置２は、中央演算装置１のデータベースにアクセスし、搬送要求が割り当てられたかどうか、又は、中央演算装置１から送信された搬送要求の割り当てを受信したかどうかを調べる（Ｓ２０１）。もし、割り当てられた搬送要求が存在すれば、分散型制御装置２は搬送要求（搬送指示）を受信し、記憶部２５に格納する（Ｓ２０２）。例えば、各分散型制御装置２の通信部２２は、中央演算装置１のデータベースにアクセスし、搬送要求（指示）データの有無を確認する。そして、搬送要求（指示）データが存在すれば、各分散型制御装置２は、データベースから搬送要求場所と搬送先、製品等の情報を読み込むことができる。そして、分散型制御装置２は、受信した搬送要求に従って、経路計画を実行する（Ｓ２０３）。経路計画が得られた時点で分散型制御装置２は表示装置３にその経路計画のデータを送り、経路計画結果を表示装置３で表示することができる（Ｓ２０４）。また、分散型制御装置２は、経路計画が終了すると同時に、ＡＧＶの制御部２４に動作指示を与える（Ｓ２０５）。
【００１９】
つぎに、図６に、経路計画作成処理のフローチャートを示す。この図は、上述のステップＳ２０３についての詳細フローチャートを示す。
本実施の形態における経路作成手段は、各ＡＧＶはまず、他のＡＧＶとの干渉を考慮せず、独自に経路を作成する。次に、全てのＡＧＶで得られた搬送経路は全ＡＧＶに情報交換される。しかしながら、ＡＧＶごとに作成された経路計画はほとんどの場合、ＡＧＶどうしが干渉し、実行不可能となる。そこで、各ＡＧＶはＡＧＶ間で干渉することに対するペナルティ関数を評価関数に組み込んで再経路計画を行う。このように、ＡＧＶ間の情報交換と各ＡＧＶでの再経路計画を最終的に実行可能な経路計画が得られるまで繰り返す。本アルゴリズムは、各ＡＧＶのアルゴリズムであるが、全てのＡＧＶで同一のアルゴリズムであるため、複数のＡＧＶに同一のアルゴリズムを用いることで全体の経路計画システムを構成することが可能である。
【００２０】
図７に、ＡＧＶのメモリフォーマットを示す。
分散型制御装置２は、搬送路のレイアウトを表すノード集合と、それらをつなぐアーク集合を予め記憶部２５内に格納している。なお、中央演算装置１のデータベースにも、全ＡＧＶに対してこれと同様のフォーマットの情報が記憶されている。このデータベースは、ＡＧＶのＩＤ（識別子）に対応して、初期値ノード、目的地ノード、初期方向、評価値、ＡＧＶｋとのペナルティ（Ｐｅｎａｌｔｙ［ｋ］）、経路更新情報、接触情報、収束情報、状態（搬送終了、待ち、経路計画中等）、経路（ノード番号、エリア情報、方向等）を含む。
【００２１】
分散型制御装置２は、以下の手順で経路計画を作成する。
（１）搬送要求入力（Ｓ１）
各分散型制御装置２は、中央演算装置１から送られる搬送指示を通信部２２又は記憶部２５により入力する（Ｓ１）。
（２）初期経路計画作成（Ｓ２）
各分散型制御装置２の経路最適化部２１は、他のＡＧＶとの衝突やすれ違い、又は、デッドロック等の干渉を考慮せず、各ＡＧＶで最適な経路、即ち搬送要求元から搬送先への最短経路を作成する（Ｓ２）。しかしながら、各ＡＧＶが他のＡＧＶを考慮せず経路を作成すれば、全体としてみた場合、不整合となる経路計画が得られる場合がある。なお、本実施の形態では、一例として、経路作成の処理に、ダイキストラ法を利用している。ここで、ダイキストラ法は、ノードとアーク（例、ノードとアーク間距離）の集合、及び評価関数が与えられたとき、初期ノードと目的地ノードを入力すれば、初期ノードから目的値ノードまでの最短経路を出力することができる処理方法である。なお、ダイキストラ法の処理アルゴリズムについては後述する。
【００２２】
（３）情報交換（Ｓ３）
分散型制御装置２の経路最適化部２１は、通信部２２による無線通信を利用して、他のＡＧＶの分散型制御装置２との間において、暫定的な経路計画を交換する（Ｓ３）。経路計画を交換すると、経路最適化部２１は情報交換回数ｉを１増加させる。次に、各ＡＧＶの通信部２２は、他の全てのＡＧＶからその時点での以下の情報を読み込み記憶部２５に記憶する。ただし、このとき、非同期通信を採用しているため、他のＡＧＶが経路計画途中であっても構わない。
・他のＡＧＶの暫定経路（時刻、ノード番号、ＡＧＶの方向）
・他のＡＧＶが経路計画の解を変更したかどうかを表すフラグ
・他のＡＧＶの経路計画が収束したかどうかを表すフラグ
・他のＡＧＶの情報交換回数
図８に、ＡＧＶのデータベースを示す。ＡＧＶの状態は、一例として、図８（ａ）に示すＡＧＶ状態データベースと、図８（ｂ）に示すＡＧＶ制御情報データベースの２つのデータベースで記述される。ＡＧＶ状態データベースは、ＡＧＶの識別子に対応して、時刻、ノード番号、向きを記憶したデータベースである。ＡＧＶ制御情報データベースは、ＡＧＶの識別子に対応して、情報交換回数、衝突判定フラグ、解変更フラグ、収束フラグを記憶したデータベースである。
なお、中央処理装置１は、経路計画処理を分散環境で実現するために他のＡＧＶの分散型経路制御装置２との情報伝達を行う手段として、他のＡＧＶの情報を記憶した共有リレーショナルデータベースを備え、この共有リレーショナルデータベースを利用して、常時複数の分散経路制御装置２から通信部２２によりアクセスを可能とすることで、情報交換を行うようにしてもよい。
【００２３】
（４）収束判定（Ｓ４）
分散協調部２３は、情報交換によって得られた情報を用いて収束判定を行い（Ｓ４）、収束していればステップＳ８に移る。収束していない場合は、ステップＳ５に移る。ここで、収束条件は、例えば、全ＡＧＶで再経路計画時に得られた経路が更新されず、かつＡＧＶどうしの干渉がないことである。分散協調部２３は、次の２つの条件のうち、いずれかの条件を満たした場合、収束と判定し、経路計画の計算を終了する。
（ｉ）他のＡＧＶと衝突やデッドロックを生じていない、かつ、他の全てのＡＧＶが解を変更していないこと
（ｉｉ）他の全てのＡＧＶの経路計画が収束していること
つぎに、図９に、衝突の判定の説明図を示す。ここで、分散協調部２３は、次のように衝突を判定する。まず、ＡＧＶをｋ、他のＡＧＶをｋ’、とする。時刻ＴにおけるＡＧＶｋの経路をノード番号Ｒ_ｋ［Ｔ］の集合、ＡＧＶｋ’の経路をノード番号Ｒ_ｋ’［Ｔ］の集合で表す。このとき、衝突しているかどうかは、Ｒ_ｋ［Ｔ］＝Ｒ_ｋ’［Ｔ］となるＴが存在するかどうかで判定する。
また、図１０に、すれちがいの判定の説明図を示す。分散協調部２３は、次のように、すれちがいを判定する。ＡＧＶをｋ、他のＡＧＶをｋ’とする。時刻ＴにおけるＡＧＶｋの経路をノード番号Ｒ_ｋ［Ｔ］の集合、ＡＧＶｋ’の経路をノード番号Ｒ_ｋ’［Ｔ］の集合で表す。このとき、すれちがいで衝突しているかどうかは、Ｒ_ｋ［Ｔ］＝Ｒ_ｋ’［Ｔ＋１］かつＲ_ｋ［Ｔ＋１］＝Ｒ_ｋ’［Ｔ］となるＴが存在するかどうかで判定する。
【００２４】
（５）ペナルティ関数の重み係数増加（Ｓ５）
ステップＳ２又は後述のステップＳ７で経路最適化部２１により得られた経路計画が実行不可能であれば、分散協調部２３は、干渉を生じているＡＧＶの分散型制御装置２のみ、経路計画の計算に用いられる評価関数Ｊ（後述の式（２）参照）中の他のＡＧＶとの干渉に対するペナルティ関数の重み係数であるαを所定値増加させ、更新する（Ｓ５）。この場合、衝突やデッドロック等の干渉が生じているＡＧＶの分散型制御装置２のみペナルティの重み係数を所定量増加させる。なお、ペナルティ関数は、例えば、一定値としてもよいし、他のＡＧＶと衝突していないとき０となり、衝突している場合は１となる関数を用いてもよい。また、ペナルティ関数は、他のＡＧＶとの間で生じた衝突ノード個数、他のＡＧＶとの間で生じたすれ違い回数、又はこれらの和とすることもできる。
【００２５】
（６）スキップ判定（Ｓ６）
各ＡＧＶの分散協調部２３は、次の再経路計画を確率的に飛ばし、ステップＳ３に進み（以後、この操作をスキップと呼ぶ）、一方、スキップしない場合はステップＳ７に移る（Ｓ６）。各分散協調部２３は、例えば、０から１の一様乱数を発生させ、ある予め定められた確率（以下、スキップ確率と呼ぶ）、スキップ確率と比較する。そして、乱数＜＝スキップ確率ならば、スキップ処理を実行する。
【００２６】
（７）再経路計画（Ｓ７）
ステップＳ６でスキップしないと判定されると、経路最適化部２１は、情報交換を行うことによって得られた情報を用いて、再経路計画を行う（Ｓ７）。再経路計画では、経路最適化部２１は、各ＡＧＶの搬送時間、及び他のＡＧＶとの衝突やデッドロック等の干渉に対するペナルティ関数の重みつき和を最小とする経路を作成する。例えば、経路最適化部２１は、情報交換（ステップＳ３）で得られた他のＡＧＶの経路情報から、他のＡＧＶが現在通っているノード間の距離の大きさをαだけ長く設定する。ノードｉからノードｊの距離をｄ_ｉｊとするとき、もし情報交換によって得られた他のＡＧＶがノードｉからノードｊを通っていたとき、ノード間距離をｄ_ｉｊ＋αとする。これによって、経路最適化部２１は、評価関数Ｊを最小とする最短経路をダイキストラ法を用いて導出することが可能となる。なお、評価関数Ｊは、次式により与えられる。
Ｊ＝（経路長）＋α（他のＡＧＶと干渉することに対するペナルティ） （２）（８）搬送指示（Ｓ８）
経路最適化部２１は、得られた搬送経路を基にして、ＡＧＶの制御部２５に移動指示を与える（Ｓ８）。
【００２７】
２−３．ダイキストラ法
図１１に、ダイキストラ法のアルゴリズムの説明図を示す。
ノード集合をＰ、計算回数をｋ、ｋ回目の探索途中ノードをｉ_ｋとする。初期値ノードを０とし、任意のノード間の距離｛ｄ_ｉｊ｝を与えたとき、ダイキストラ法のアルゴリズムは、図示のようになる。ここで、Ｇ（ｉ）は、初期値ノードからノードｉまでの最短距離を表す。このアルゴリズムで、初期値ノードから任意のノードｎまでの最短距離Ｇ（ｎ）と最短経路を計算することができ、最短経路は、Ｈ（ｎ）で与えられる。
【００２８】
２−４．分散型経路計画の例
つぎに、図１２に、簡単な例題を用いたＡＧＶの分散型経路計画の説明図を示す。
ここでは、図のような簡単な搬送システムにおいて、２台のＡＧＶに矢印が示す搬送要求が与えられているという問題を考える。この問題に対して、本アルゴリズムを適用した際に得られるＡＧＶの経路計画の例を示す。初期経路計画の段階では各ＡＧＶは他のＡＧＶとの干渉を考慮せずに各ＡＧＶにとって最短となる経路を作成する（図１２（ａ））。ここで得られた経路は情報交換され、この情報に基づいて再経路計画が行われる。しかし、どちらのＡＧＶも同様に、干渉に対するペナルティをより少なくするために、次の再経路計画では図１２（ａ）と同様に干渉のある図１２（ｂ）で示す経路を作成する可能性が高い。また、図１２（ｂ）の経路計画が得られた場合、次の反復でも再び同様に図１２（ａ）に示す経路計画が作成される場合もある。このように、同じ実行不可能な経路が周期的に作成され、収束しなくなる場合がある。
【００２９】
図１３に、各ＡＧＶが作成する経路計画の評価値の変化を表す図を示す。反復回数が５回から１０回の付近で評価値が振動していることがわかる。このような状況を回避するために、確率的に（約２０％の確率）再経路計画をスキップする。このような処理を追加することにより、一方のＡＧＶの経路が回避され、図をみてもわかるように、一方の評価値が大きくなるが、これにより全体の収束を早め、本実施の形態の経路計画手順の収束性を高めることができる。この結果、図１２（ｃ）で示す経路計画を作成することができる。
つぎに、図１４に、図１で示した搬送システムに７台のＡＧＶが走行する際の分散型経路計画法の例の説明図を示す。
これは、図１の搬送システムにおける７台のＡＧＶの経路計画を分散型経路計画装置を用いて作成したものである。各矢印は、各ＡＧＶの移動経路を表す。図示の結果から、全てのＡＧＶは遠回りや回避移動を行うことなく最短経路で目的値に到達していることがわかる。
【００３０】
３．ＡＧＶの大きさ等を考慮した分散型経路計画
以下に、ＡＧＶの大きさを考慮した経路計画結果の実施の形態を説明する。
図１５（ａ）に、３台の移動ロボットと１２個のノードから構成される模擬搬送システム構成図、図１５（ｂ）に、実施に利用した移動ロボットの構成図を示す。搬送路は、横方向のノード間距離が３６０ｍｍ、縦方向のノード間距離が５００ｍｍであり、白線により構成されている。移動ロボットは、一辺が３００ｍｍの正方形であり、前部に白線を認識するフォトセンサが搭載されている。三つのタイヤのうち、後部の二つが動輪、前部の一つが操縦輪となっている。ターン時の回転中心は、二つの動輪間の中心点である。実験において、回転中心がノード上に一致した場合をＡＧＶの到着とし、ターン及び停止は、回転中心をノード上に一致させて行う。
【００３１】
図１４の経路計画では、比較的大規模な搬送路を対象としていたため、各ＡＧＶを点として扱え、同一ノード上に進入する場合と、隣接するノード間ですれ違いをする場合のみを衝突とみなしていた。しかしながら、実際の工場では搬送路の大きさやレイアウト等の制限のため、搬送路の大きさに比べ、ロボットの大きさが無視できない場合も存在する。その場合には、ロボットの大きさを考慮し、経路計画を行わなければならないが、本発明による経路計画手法はＡＧＶ毎に経路計画手段が独立しているために、このような変更に対しても、各ＡＧＶの経路計画手段を多少改良するだけで、簡単に対応することが可能である。改良点を以下に示す。
【００３２】
（１）占有領域の計算
図１６に、占有領域の説明図を示す。図１６（ａ）に、ＡＧＶが非回転の場合を、図１６（ｂ）に、回転の場合をそれぞれ示す。
占有領域は、ＡＧＶの四隅の座標から定義される。ただし、回転中は、図１６（ｂ）のように、実際にＡＧＶが存在しているよりも大きめに領域を確保している。これは、接触が生じやすい回転時に余裕を与えるためである。回転中以外では、四隅の座標により求められる四角形が占有領域となる。分散型制御装置２の分散協調部２３は、ダイキストラ法により計画した移動経路から、各時刻においてＡＧＶが占有する領域を計算する。
占有領域の計算は、ＡＧＶの形状とＡＧＶの中心位置からＡＧＶの占有領域を計算する。収束判定時には、占有領域の端点（Ａ、Ｂ、Ｃ、Ｄ）が他のＡＧＶの占有領域に入るかどうかで判定する。また、計算に用いるメモリフォーマットは、図７で説明したフォーマットと同一である。なお、この実施の形態では、一例として、占有領域が四角形であるＡＧＶについて説明しているが、このような判定の計算方法は、ＡＧＶの形状や回転位置に依存するので、上述の計算法を限定する必要はなく、適宜の計算法を用いて判定を行うことができる。
【００３３】
移動中におけるＡＧＶの状態は、次の三種類に分類され、それぞれの状態に対して、四隅座標の計算を行う。なお、計算は、情報交換で得た三つの情報を用いて行う。
（１−１）ＡＧＶの回転中心がノード上に存在する場合
ノード上におけるＡＧＶの方向は分かっているため、ノードの座標とＡＧＶの大きさからＡＧＶの四隅の座標を計算する。
（１−２）ノード間を移動している場合
（１−２−ａ）前ノードに到着した時刻と次のノードに到着した時刻の差から、ノード間の移動時間を求める。
（１−２−ｂ）ＡＧＶの移動速度は一定であると仮定しているため、前ノードと次ノードの座標の差から、一時刻分の移動量を求める。
（１−２−ｃ）前ノード上におけるＡＧＶの四隅の座標をスタート地点とし、移動中の各時刻におけるＡＧＶの四隅の座標を計算する。
（１−３）ノード上で方向転換をしている場合
（１−３−ａ）方向転換前の時刻と方向転換後の時刻の差から、方向転換に要する時刻を求める。
（１−３−ｂ）ＡＧＶの回転速度は一定であると仮定しているため、一時刻分の回転角度を求める。
（１−３−ｃ）ノードの座標（ＡＧＶの回転中心）とＡＧＶの大きさから、回転中の各時刻におけるＡＧＶの四隅の座標を求める。
【００３４】
（２）交換する情報
以上の説明では、各ＡＧＶが計画した移動経路を交換していたが、ここではそれの代わりに、各時刻において各ＡＧＶが占有する領域の交換を行う。各ＡＧＶは、その情報を用いて経路計画を行う。
ＡＧＶが搬送先に到着するまでに経由する全てのノードに対して、ＡＧＶの回転中心がノード上に到着する時刻、そのノード番号及びＡＧＶの方向の三つの情報を交換する。ただし、ノード上で方向転換する場合も、新たにノード上に到着したものと見なし、方向転換終了時の時刻、ノード番号及びＡＧＶの方向を交換する。（方向転換は９０度毎に分解する。つまり、１８０度回転は９０度回転が二回と見なす。）
【００３５】
（３）衝突の定義
図１７に、衝突の説明図を示す。
他のＡＧＶの占有領域内に自分の領域が侵入する場合を衝突と定義し、その場合に接触ペナルティを加える。
つぎに、図１８に、経路計画の実験結果の図を示す。以下に、ＡＧＶの大きさを考慮した経路計画の例について説明する。
この図は、分散型制御装置２によって得られた経路計画結果に従って、ＡＧＶを動作させたときの軌道を表す。経路計画は、３台のＡＧＶ＃１〜＃３に対して、それぞれ、初期ノードＳ１〜Ｓ３、目的地ノードＧ１〜Ｇ３、及び初期方向を与えて行った。初期方向とは、ＡＧＶが最初に向いている方向である。ターンに必要な時間は、ＡＧＶが１０ｍｍ移動するのに必要とする時間を１とし、実際の移動ロボットから、実験的に求めた。図（ａ）は、初期状態である。図（ｂ）、（ｃ）、・・・、（ｆ）に、時間ｔを経るにつれて、各ＡＧＶ＃１〜＃３が回転及び移動し、各々の動作における占有領域が示される。図（ｇ）に最終状態として、各ＡＧＶ＃１〜＃３が目的ノードに到達したことが示される。この例では、分散型制御装置２により各ＡＧＶに経路計画を行うことによって得られた経路にしたがって、ＡＧＶを走行させた結果、ＡＧＶ間の衝突やデッドロックの生じない経路が得られることが確認できる。
【００３６】
４．非同期による分散型経路計画
図１９に、非同期通信による経路計画の説明図を示す。図１９（ａ）は、同期的タイミングによる情報通信による計算時間を、図１９（ｂ）は、非同期による計算時間を示す。この図は、３台のＡＧＶの分散型制御装置の計算時間を表す。ＤＳＳ（分散サブシステム）は、各ＡＧＶの分散型制御装置２を表し、図中の□は情報通信時間、■は経路計画時間を表す。同期通信によるデータ交換では、分散型制御装置２を用いて並列的計算を実行したとき、各ＡＧＶで得られる経路の実行可能性を判定する場合には、計算の実行を同期化させる必要があった。これに対して、非同期通信によるデータ交換を用いると、データベースに保存されている１ステップ前の経路情報を利用することにより、他のＡＧＶの計算が終了していなくても、次のステップの計算を実行する非同期通信による並列計算が可能となる。ここで、各ＡＧＶがいったん収束条件を満たしてしたとしても、他のＡＧＶのうち、一つでも収束条件を満たさないＡＧＶが存在すれば計算を続けるという処理を加えることにより、非同期通信の場合でも収束が可能となる。図示のように、非同期通信を利用することにより、通信時の待ち時間が短縮化され、同期通信に比べ約１２％の計算時間の短縮が確認できる。
【００３７】
５．その他
本発明の分散型経路計画方法又は分散型経路計画装置・システムは、その各手順をコンピュータに実行させるための分散型経路計画プログラム、分散型経路計画プログラムを記録したコンピュータ読み取り可能な記録媒体、分散型経路計画プログラムを含みコンピュータの内部メモリにロード可能なプログラム製品、そのプログラムを含むサーバ等のコンピュータ、等により提供されることができる。
【００３８】
【発明の効果】
以上述べたように、本発明によれば、複数台の移動ロボットから構成される搬送システムにおける、分散型経路計画装置を開発した。本発明で開発した経路計画装置は、各ＡＧＶが独自の評価による経路の最適化と、他のＡＧＶとの情報交換を繰り返すことにより、最適に近い経路を計画する。半導体工場をモデルとした搬送システムにおいて数値実験を行った結果、１５台のＡＧＶが存在する場合においても、最適に近い経路計画を、５秒以下の計算時間で導出することができることが可能となった。同様の経路計画を、全ＡＧＶの経路計画を同時に最適化するホストコンピュータを用いて、混合整数計画問題に対する分枝限定法、遺伝的アルゴリズム、シミュレーティッドアニーリング法を利用して同様のプロセッサを利用して計算時間の比較を行った結果、同等の搬送時間の評価を有する結果の導出に、約１００００秒、約８００秒、及び約１００秒の計算時間を必要とした。
【００３９】
経路計画装置で得られた結果の妥当性を確認するため、模擬搬送路を用いた搬送実験に提案法を適用した。模擬搬送路では、ＡＧＶの大きさを考慮した経路計画を行うことが必要であるが、占有領域の計算、情報交換の変更、接触の定義の変更を行い、得られた結果を実際の移動ロボットで実行した結果、接触の生じない経路が得られることを確認した。
分散型経路計画装置は、ＡＧＶに組み込まれた複数のＣＰＵと無線による情報通信を利用した非同期通信による並列最適化計算アルゴリズムへの適用することにより、計算時間の大幅な削減が可能となり、搬送要求が時事刻々に発生する搬送環境へ適用することも可能である。したがって、本発明はより実用的な経路計画問題に対しても経路計画を極めて迅速に行うことが可能であり、その効果は極めて大きい。
【図面の簡単な説明】
【図１】半導体画像デバイス工場における格子状の搬送システムを模式化した図。
【図２】分散型経路計画装置の構成図。
【図３】中央演算装置の処理についてのフローチャート。
【図４】Ｔ^ｋ _ｆｒｅｅ及びＴ^ｋ _{ｍｉｎ ｐａｔｈ}の計算に用いるデータベースの説明図。
【図５】ＡＧＶの処理についてのフローチャート。
【図６】分散型経路計画のフローチャート。
【図７】ＡＧＶのメモリフォーマット。
【図８】ＡＧＶのデータベース。
【図９】衝突の判定の説明図。
【図１０】すれちがいの判定の説明図。
【図１１】ダイキストラ法のアルゴリズムの説明。
【図１２】簡単な例題を用いたＡＧＶの分散型経路計画の説明図。
【図１３】各ＡＧＶが作成する経路計画の評価値の変化を表す図。
【図１４】図１で示した搬送システムに７台のＡＧＶが走行する際の分散型経路計画法の例の説明図。
【図１５】３台の移動ロボットと１２個のノードから構成される模擬搬送システム構成図。
【図１６】占有領域の説明図。
【図１７】衝突の説明図。
【図１８】経路計画の実験結果の図。
【図１９】非同期通信による経路計画の説明図。
【符号の説明】
１ 中央演算装置
２ 分散型制御装置
３ 表示装置
２１ 経路最適化部
２２ 通信部
２３ 分散協調部
２４ 制御部
２５ 記憶部

Claims (20)

1. 所定の領域内で敷設された搬送路を移動する複数の搬送装置を用いた搬送システムにおいて、前記搬送装置の各々に備えられた分散型経路計画装置であって、中央制御装置から、搬送元及び搬送先を含む搬送要求が、搬送元の近傍に位置する搬送装置に与えられたとき、全搬送装置による総搬送時間又は総搬送距離を最短とする各搬送装置の最短経路を各搬送装置独自の評価指標に基づき作成することにより、経路計画を最適化するための経路最適化部と、
   各搬送装置の位置及び経路計画を含む状態情報を、他の搬送装置又は中央制御装置と通信するための通信部と、
   前記通信部で通信した状態情報に基づき、前記経路最適化部により作成された全ての搬送装置の経路計画により生じる搬送装置間の干渉及び／又はデッドロックを判定し、経路計画の評価指標を変更し、前記経路最適化部で変更された評価指標に基づき再び経路計画を最適化するか否かを所定の条件で選択することにより、全搬送装置として干渉を生じないように経路計画を最適化して他の搬送装置と協調するための分散協調部と
   を備えた分散型経路計画装置。
2. 前記通信部が、全搬送装置の経路計画を搬送装置間で情報通信すること、及び、
   前記経路最適化部及び前記分散協調部が、各搬送装置における最適化計算を実行すること、
   を複数回繰り返すことにより、短時間で総搬送時間を最短とする最適な経路計画を得るようにした請求項１に記載の分散型経路計画装置。
3. 前記分散協調部は、搬送装置独自の評価指標に他の搬送装置との干渉及び／又はデッドロックに関する不整合な経路計画に対するペナルティ関数を導入し、前記通信手段によって受信される情報に基づき、干渉及び／又はデッドロックを生じている搬送装置のペナルティ関数の重み係数を各搬送装置で増加させて設定し、
   前記経路最適化部は、設定されたペナルティ関数に基づき、各搬送装置での再経路計画を実行することにより、
   生成される経路の最適性を保ちながら不整合な経路計画を分散協調的に解消する請求項１に記載の分散型経路計画装置。
4. 前記分散協調部は、各搬送装置で得られる経路計画が、実行可能な経路計画に収束するために、ある段階において確率的に再経路計画の作成を飛ばすスキップ処理を実行する請求項１に記載の分散型経路計画装置。
5. 前記情報通信部は、互いの状態に関する情報を非同期なタイミングで通信し、前記経路最適化部及び前記分散協調部は、各搬送装置における分散環境で非同期並列的に経路計画を実行する請求項１に記載の分散型経路計画装置。
6. 前記分散協調部は、
   各搬送装置で生成される不整合な経路計画を各搬送装置独自の評価指標に基づいて分散的に解消することを可能とし、経路計画の実現可能性を判定するための収束機能を備えた請求項１に記載の分散型経路計画装置。
7. 前記分散協調部は、
   （ｉ）他の搬送装置と干渉を生じていない、且つ、前回と各搬送装置が同一の経路計画を導出しているという条件、又は、
   （ｉｉ）他の搬送装置と干渉を生じていない、且つ、他の全ての搬送装置の経路計画が収束しているという条件、
   のうちいずれかの条件を満たしていることを収束条件として判定することにより、他の搬送装置との干渉及び／又はデッドロックを生じない経路計画に収束させる請求項１に記載の分散型経路計画装置。
8. 搬送装置自体の向き、大きさ、速度のいずれか又は複数を考慮して、搬送装置の回転に必要な時間又は移動するタイミングを制御して、搬送装置間のデッドロックや衝突を回避する請求項１に記載の分散型経路計画装置。
9. 前記経路計画に関する情報は、さらに、各時刻における搬送装置の占有領域に関する情報を含み、
   分散協調部は、さらに、
   搬送装置の四隅の座標情報から、ノード上に存在する場合、ノード間で移動する場合、及び／又は、ノード上で方向転換する場合の占有領域を計算するステップと、
   前記占有領域により、搬送装置間の干渉を判定するステップと、
   を含む請求項１０に記載の分散型経路計画方法。
10. 前記経路計画手段は、搬送要求が時々刻々と与えられたとき、あるいは経路変更が生じたとき、干渉を生じている搬送装置のみが再経路計画を行うことによって、局所的な経路変更のみで全体の経路計画をやり直すことなく短時間で可能な経路選択を可能とする請求項１に記載の分散型経路計画装置。
11. 前記経路最適化部は、搬送元及び搬送先、搬送路のノード及びノード間距離、評価指標が入力され、これら入力された情報に基づき、搬送元ノードから搬送先ノードまでの最短経路を導出するダイキストラ法を用いて最短経路を計算する請求項１に記載の分散型経路計画装置。
12. 前記中央処理装置は、経路計画手段を分散環境で実現するために他の搬送装置の分散型経路計画装置との情報伝達を行う手段として、他の搬送装置の情報を記憶した共有リレーショナルデータベースを備え、
    前記中央処理装置の前記共有リレーショナルデータベースを利用して、常時複数の分散経路計画装置から前記通信部によりアクセスする請求項１に記載の分散型経路計画装置。
13. 前記中央制御装置は、各搬送装置の識別子に対応して位置情報を含む状態情報を記憶したデータベースを有し、与えられた搬送指示に従い、搬送元の近傍に位置し、且つ必要となる最小搬送時間に従う値が最も小さくなる搬送装置を判定し、前記搬送装置に搬送要求を与える請求項１に記載の分散型経路計画装置。
14. 各搬送装置独自の評価指標に基づく経路計画を最適化するための経路最適化部と、全ての搬送装置の経路計画において生じる搬送装置間の干渉及び／又はデッドロックをなくすために全搬送装置の経路計画に関する情報を通信するための通信部と、他の搬送装置との協調をはかりながら全搬送装置として干渉及び／又はデッドロックを生じない経路計画を作成するための分散協調部と備えた分散型経路計画装置における分散型経路計画方法であって、
    通信部は、中央演算装置から送られる搬送元及び搬送先を含む搬送要求を得るステップと、
    経路最適化部は、他の搬送装置との干渉を考慮せずに、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を各搬送装置独自の評価指標に基づき作成することで初期の経路計画を作成するステップと、
    通信部は、他の全ての搬送装置の位置及び経路計画に関する情報を得るステップと、
    分散協調部は、他の搬送装置との干渉及び／又はデッドロック、及び、最短経路の解の変更状態を判断し、その判断結果に基づき、経路計画の収束を判定するステップと、
    分散協調部は、干渉及び／又はデッドロックを生じている場合、経路計画の作成に用いられる評価関数中の他の搬送装置との干渉に関するペナルティ関数の重み係数を増加させるステップと、
    分散協調部は、次の再経路計画処理を予め定められた基準により確率的にスキップするステップと、
    経路最適化部は、分散協調部により求められたペナルティ関数を用いた評価関数に従い、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を導出して再び経路計画するステップと、
    経路最適化部は、経路計画が全ての搬送装置について収束した場合、得られた最短経路に基づき、搬送装置の制御部に搬送指示を与えるステップと
    を含む分散型経路計画方法。
15. 経路計画に関する情報は、経路計画に関する情報暫定経路、解を変更したかどうかを表すフラグ、他の搬送装置が収束したかどうかを表すフラグ、他の搬送装置の情報交換回数を含む請求項１４に記載の分散型経路計画方法。
16. 分散協調部は、乱数を発生させ、予め定められたスキップ確率と比較することで、次の再経路計画処理をスキップする請求項１４に記載の分散型経路計画方法。
17. 前記経路計画に関する情報は、さらに、各時刻における搬送装置の占有領域に関する情報を含み、
    分散協調部は、さらに、
    搬送装置の四隅の座標情報から、ノード上に存在する場合、ノード間で移動する場合、及び／又は、ノード上で方向転換する場合の占有領域を計算するステップと、
    前記占有領域により、搬送装置間の干渉を判定するステップと、
    を含む請求項１４に記載の分散型経路計画方法。
18. 前記占有領域に関する情報は、搬送装置が搬送先に到着するまでに経由する全てのノードに対して、搬送装置の回転中心がノード上に到着する時刻、そのノード番号、及び、搬送装置の方向に関する情報、を含む請求項１７に記載の分散型経路計画方法。
19. 中央計算機は、搬送要求が発生した場合は、各搬送装置が搬送要求の発生時点からすでに割り当てられた搬送要求を搬送し終える時間と、その搬送要求が搬送装置に割り当てられたときに必要となる最小搬送時間に従う値が最も小さくなる搬送装置を求めるステップと、
    搬送要求を該当する搬送装置に割り当てるステップと
    を含む請求項１４に記載の分散型経路計画方法。
20. 各搬送装置独自の評価指標に基づく経路計画を最適化するための経路最適化部と、全ての搬送装置の経路計画において生じる搬送装置間の干渉及び／又はデッドロックをなくすために全搬送装置の経路計画に関する情報を通信するための通信部と、他の搬送装置との協調をはかりながら全搬送装置として干渉及び／又はデッドロックを生じない経路計画を作成するための分散協調部と備えた分散型経路計画装置における、コンピュータに次の各ステップを実行させるための分散型経路計画プログラムであって、
    通信部は、中央演算装置から送られる搬送元及び搬送先を含む搬送要求を得るステップと、
    経路最適化部は、他の搬送装置との干渉を考慮せずに、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を各搬送装置独自の評価指標に基づき作成することで初期の経路計画を作成するステップと、
    通信部は、他の全ての搬送装置の位置及び経路計画に関する情報を得るステップと、
    分散協調部は、他の搬送装置との干渉及び／又はデッドロック、及び、最短経路の解の変更状態を判断し、その判断結果に基づき、経路計画の収束を判定するステップと、
    分散協調部は、干渉及び／又はデッドロックを生じている場合、経路計画の作成に用いられる評価関数中の他の搬送装置との干渉に関するペナルティ関数の重み係数を増加させるステップと、
    分散協調部は、次の再経路計画処理を予め定められた基準により確率的にスキップするステップと、
    経路最適化部は、分散協調部により求められたペナルティ関数を用いた評価関数に従い、全搬送装置による総搬送時間又は総搬送距離を最短とするように、当該搬送装置の搬送元から搬送先への最短経路を導出して再び経路計画するステップと、
    経路最適化部は、経路計画が全ての搬送装置について収束した場合、得られた最短経路に基づき、搬送装置の制御部に搬送指示を与えるステップと
    をコンピュータに実行させるための分散型経路計画プログラム。

Images