経路探索システム及び方法、搬送システム、並びにコンピュータプログラム
【課題】経路探索システムにおいて、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索する。
【解決手段】経路探索システム（１００）は、被搬送物を搬送するための搬送車（２）を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する。経路探索システムは、複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、搬送車の移動コストを格納する格納手段（９）と、格納された移動コストに基づいて、最適経路の少なくとも一部を、複数の集合を結ぶ単位で探索する経路探索手段（６）と、探索された少なくとも一部と、複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、最適経路を特定する経路特定手段（７）とを備える。
【解決手段】経路探索システム（１００）は、被搬送物を搬送するための搬送車（２）を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する。経路探索システムは、複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、搬送車の移動コストを格納する格納手段（９）と、格納された移動コストに基づいて、最適経路の少なくとも一部を、複数の集合を結ぶ単位で探索する経路探索手段（６）と、探索された少なくとも一部と、複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、最適経路を特定する経路特定手段（７）とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、半導体装置製造用の各種基板などの被搬送物を、工場内に敷設された軌道上を移動するビークル等の搬送車で搬送する搬送システムにおいて、最適経路を探索する経路探索システム及び方法の技術分野に関する。本発明は更に、かかる搬送システム及びコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムの技術分野に関する。
【背景技術】
【０００２】
この種の経路探索システムとして、例えば特許文献１には、複数の分岐や合流を含んで張り巡らされた軌道上で出発地点から目的地点までの最適な経路を探索するのに、所謂“ダイクストラ法”を利用した技術が開示されている。この技術では、全経路の各々が、最適経路の候補とされる。該各々の候補を構成するリンクにおける移動コスト（即ち、分岐点や合流点に相当するノード間を走行するのにかかる時間或いは時間に対応する評価値）が、出発地点から目標地点までについて積算される。その後、候補のうち出発地点から目的地点までの移動コストが最小となるものが、最適経路として決定される。
【０００３】
【特許文献１】特開平１０−３２００４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述の背景技術によれば、作業装置を夫々ノードとし且つ作業装置間に位置する経路部分を夫々リンクとして、移動コストが設定されている。このため、経路探索において取り扱うデータ数が膨大となり、特に近時における経路の複雑高度化或いは作業装置数の増大に伴って、コンピュータにかかる負荷は膨大となるという技術的問題点がある。
【０００５】
本発明は、例えば、上述した問題点に鑑みなされたものであり、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索可能である経路探索システム及び方法、これを備えた搬送システム、並びにコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明の経路探索システムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムであって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段とを備える。
【０００７】
本発明の経路探索システムによれば、実際の経路探索の動作に先立って、例えばデータベース、メモリ等の格納手段に、経路上における搬送車の移動コストが格納される。ここに「経路」とは、例えばレールなど、被搬送物が搭載された又はされない状態で搬送車が移動可能である、経路を意味する。「搬送車」とは、例えばビークル等の経路上を移動すると共に被搬送物を積載可能に構成された台車等の車を意味する。
【０００８】
本発明では特に、移動コストは、複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される。ここに「作業装置」とは、例えば半導体基板などの被搬送物に対して、成膜、加熱、配線、エッチング等を行う製造装置や、被搬送物の一時的な格納を行うストッカを含む、被搬送物に対して各種処理を施す装置を意味する。作業装置は、経路の脇に並んでいるか、又は経路の一部をなすように並んでいる。経路の一部をなす場合としては、例えば、単一の作業装置における搬入口と搬出口との経路における位置が相互に異なることで、経路の一部をなすように並ぶ場合がある。本発明に係る「集合」は、このような作業装置を複数含んで構成される集合を含む。但し、作業装置の一つから構成される集合を含んでもよい。集合の間には、搬送車が移動される経路（以下適宜「集合間経路」と呼ぶ）が存在し、集合の内部にも、搬送車が移動される経路（以下適宜「集合内経路」）が存在する。例えば、個々の集合は、個々の製造ラインに対応してもよいし、複数の集合が単一の製造ラインの中に存在していてもよい。
【０００９】
本発明に係る「移動コスト」は、このように複数の作業装置を含んでなる集合の相互間の経路部分が夫々リンクとされると共に集合が夫々ノードとされた上で、規定されている。「リンク」は、経路において、分岐点、合流点、交差点などの間を直接結んでおり、移動の仕方について単純に進むことしか選択枝がない、一本の直線又は曲線状若しくは屈曲状の経路部分に対応する。「ノード」は、経路において、リンクの端に位置しており、典型的には、分岐点、合流点、交差点、行き止り点、更にはストッカの搬出搬入箇所など、搬送経路における移動の仕方についての選択枝が複数存在する点或いは箇所に対応する。「移動コスト」とは、このような集合をノードとし且つ集合間をリンクとする経路探索を行う際に、一つのノードからこれに隣接するノードまで一つのリンクを介して移動するのにかかる時間若しくは時間に比例する指標であるコストを意味する。例えば、同一の距離でも、混雑等により移動時間が長ければ、移動コストの値は大きくなる。このような移動コストを用いれば、次に説明するように、典型的には、上述の如く集合に対応した移動コストを用いてのダイクストラ法によって、複数の集合を結ぶ単位での経路探索を行える。
【００１０】
特に、このように複数の作業装置を含んでなる集合をノードとして、移動コストが規定されるので、作業装置をノードとする場合と比較して、複数の作業装置を集合にまとめた分だけ、経路探索に供される移動コストの総数は、削減される。即ち、格納手段に格納される移動コストのデータ量は、先ず低減される。また、作業装置等の設備が新規に設置される場合に、その新規設備は何れかのノードに設置される。この何れかのノードを含んでなる経路における移動コストの修正では、その新規設備が設置されたノードのみにおいて、移動コストが算出されればよく、既に使用されている規定済みの移動コストは、該経路において流用可能である。このため、新規設備を立ち上げる時間を短縮することができる。
【００１１】
尚、以上のような移動コストは、例えば過去における各集合に関しての平均移動時間から予め特定して、格納手段に格納してもよい。或いは、実際の経路探索の動作を行う際に先ず、経路における混雑状況等を考慮して、かかる移動コストを検出或いは算出し、格納手段に新たに格納したり、その格納内容を更新してもよい。或いは、搬送作業の際に、搬送車が各集合を移動するのに要した移動時間が実測され、搬送作業が終了されると直ちに、その経路についてのコスト計算が実行或いは再実行されることで、格納手段の格納内容が新設或いは更新されてもよい。この場合に、移動コストは、最新の経路の混雑状況を反映させたものとなる。
【００１２】
その後、実際の経路探索の動作時には、例えばプロセッサ、メモリ等を備えてなる経路探索手段によって、上述の如く格納手段に格納された移動コストに基づいて、最適経路の少なくとも一部が、複数の集合を結ぶ単位で探索される。例えば、複数の集合のうち出発地点を含む出発集合から、複数の集合のうち目的地点を含む目標集合までの経路が、出発集合から目標集合まで複数の集合を結ぶ形で探索される。言い換えれば、先ずは、少なくとも最適経路の一部について、経路探索手段によって、例えば製造ライン単位など、集合を結ぶ単位での大まかな経路探索が行われる。
【００１３】
このように経路探索手段による経路探索では、少なくとも最適経路の一部について、集合の内部において個々の作業装置間を結ぶ経路部分が、夫々リンクとして扱われるのではなく、集合の相互間を結ぶ経路部分が夫々リンクとして扱われる。これと共に、個々の作業装置が夫々ノードとして扱われるのではなく、集合が夫々ノードとして扱われる。従って、個々の作業装置間を結ぶ経路部分が夫々リンクとして扱われ、個々の作業装置が夫々ノードとして扱われる場合における、経路探索と比べて、データ量及び演算量が飛躍的に低減される。特に、格納手段に格納される移動コストの総数の削減に対して、移動コストに基づく経路探索におけるデータ量及び演算量の削減は、極めて顕著となる。経路探索で用いる移動コストの総数の小規模な削減であっても、経路探索においては大規模なデータ量及び演算量の削減に繋がる。
【００１４】
このような経路探索手段による探索と相前後して又は並列に、例えばプロセッサ、メモリ等を備えてなる経路特定手段によって、探索された最適経路の少なくとも一部と、この少なくとも一部に含まれる一又は複数の集合の内部に存在する経路の部分とが統合されることで、最適経路の全体が特定される。ここに「統合する」とは、探索された集合を結ぶ集合間経路と、探索された集合の各々の内部に存在する集合内経路とを、一本の道筋に結び合わせて最適経路とすることを意味する。例えば、経路探索手段による探索の後に、探索された集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われる。或いは、経路探索手段による探索の以前に、任意の集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われて、探索された集合内経路が集合に対応付けられて格納手段等に格納され、その後、経路探索手段により探索された集合に対応する集合内経路が格納手段等から呼び出されてもよい。
【００１５】
ここで特に、本願発明者の研究によれば、全体として複雑高度化された経路であっても、一つの集合についてみれば、その内部における経路及び経路を介しての移動は、相対的に単純であり、移動にかかる時間は、短時間であることが判明している。言い換えれば、同一集合内であれば、目標地点がどの作業装置であったとしても、時間的に或いはコスト的に大差がないことが判明している。よって、上述の経路特定手段による集合内経路の探索或いは決定は、例えば同一製造ライン内における経路の探索であれば、複数の製造ラインに跨る経路の探索或いは決定と比べて、飛躍的に単純なもので足りる。例えば、ダイクストラ法を用いても、個々の集合についてみれば、リンク及びノードの構成は単純なものであり、経路探索にかかるデータ量及び演算処理も、飛躍的に低減されることになる。従って、先ず集合を結ぶ単位で大まかな経路探索を行って、最適経路をなす集合及び集合間経路を決定した上で、各集合内における集合内経路を特定し、これらを結んで得られる最適経路は、初めから経路を最大限に細かく見てダイクストラ法により経路探索を行った場合に得られる最適経路と比べて、実践上は殆ど又は全く遜色のないものとなる。
【００１６】
そこで本発明において、経路探索手段により、集合を結ぶ単位で大まかな経路探索を行うと共に、経路特定手段により、集合内での経路探索或いは経路の決定を行えば、決定される最適経路は、実践上は、理論上における真の最適経路と殆ど又は全く同じ経路となる。或いは、少なくとも、真の最適経路に相当に近いものとなる。他方で、このような適切な経路を求める際に、集合単位で経路探索するのに必要なデータ量及び演算量と集合内で経路探索或いは決定を行うのに必要なデータ量及び演算量との合算は、一段階で真の最適経路を探索する場合と比べて飛躍的に低減されている。
【００１７】
以上の結果、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。従って、リアルタイム或いはそれに近い形で経路探索を行うことも容易となり、搬送システムにおいて迅速な搬送が可能となる。更に、これらを実践するために、経済性に見合わないような高性能のコンピュータを用いることも効果的に回避できる。
【００１８】
尚、本発明で探索される最適経路の精度を高める観点からは、一集合にまとめられる複数の作業装置は、経路探索上で同一ノードとして扱っても、最終的に探索される経路に差がでないような関係にある、典型的に近くに横並びになっているような複数の作業装置とするのがよい。例えば、小規模な製造ラインであって、その製造ライン内における移動が短時間で行われ得るような製造ラインであれば、一つの集合と一つの製造ラインとを対応させるのがよい。他方、大規模な製造ラインであって、その製造ライン内における移動が長時間で行われ得るような製造ラインであれば、複数の集合と一つの製造ラインとを対応させるのがよい。
【００１９】
他方で、複数の作業装置を集合にまとめる箇所が多い程、移動コストの総数は低減され、よって経路探索時におけるデータ量及び演算量の削減の効果は、より顕著に得られる。但し、集合にまとめる箇所が一箇所だけであっても、経路探索時におけるデータ量及び演算量の削減の効果は、相応に得られる。
【００２０】
加えて、集合間の経路と集合との接続点、即ち、各集合の搬出口及び搬入口は、一つの集合に対して複数個所存在してもよい。一つの集合を一つのノードとして扱えば、上述の如き移動時間又は移動コストを用いた経路探索は、極めて単純化できる。或いは、搬出口及び搬入口の少なくとも一方が複数ある場合、搬出口又は搬入口別に複数の集合として扱って、即ち複数のノードであるものとして扱っても（従って、リンクもそれに応じて増えても）、移動時間又は移動コストを用いた経路探索は、全ての作業装置の各々をノードとして扱う場合と比べれば、なお顕著に単純化できる。
【００２１】
本発明の経路探索システムの一態様では、前記経路特定手段は、前記複数の作業装置間を夫々結ぶ前記経路の部分を夫々リンクとすると共に前記複数の作業装置を夫々ノードとする前記搬送車の移動コストに基づいて、前記経路の部分を探索し、前記探索された少なくとも一部と前記探索された経路の部分とを統合することで、最適経路を特定する。
【００２２】
この態様によれば、各集合内における経路探索は、作業装置をノードとし且つ作業装置間をリンクとする移動コストを用いて、典型的にはダイクストラ法によって行われるが、例えば同一製造ラインなど、同一集合の内部での経路の探索である。このため、経路特定手段による経路探索に必要なデータ量及び演算負荷が、過度に増大することはない。
【００２３】
或いは本発明の経路探索システムの他の態様では、前記格納手段は、前記ノード及び前記リンクに対応付けて、前記集合の内部における前記経路の部分を示す集合内経路情報を更に格納しており、前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、最適経路を特定する。
【００２４】
この態様によれば、各集合内における経路の決定は、格納手段に格納された集合内経路情報を参照することで行われるが、例えば同一製造ラインなど、同一集合の内部での経路の決定である。このため、経路特定手段による経路の決定に必要なデータ量及び演算負荷が、過度に増大することはない。
【００２５】
本発明の経路探索システムの他の態様では、前記搬送車が移動する際の移動状況を検出する状態検出手段を更に備え、前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する。
【００２６】
この態様によれば、例えばプロセッサ、センサ等を有する状態検出手段によって、例えば各集合内を移動する際の平均移動速度、混雑状態や、集合間を移動する際の平均移動速度、混雑状態などの、搬送車が移動する際の移動状況が検出される。すると、経路探索手段によって、検出された移動状況に対応して、経路が再探索される。従って、特定の集合で或いは特定の集合間で平均移動速度が変化したり、故障や搬送量の過多に起因して混雑やデッドロックが発生したり、回復や搬送量の低下に起因して混雑やデッドロックが解消した場合に、最適経路が探索され直される。従って、リアルタイム的に各時点に見合った最適経路が探索されることとなり、実践上極めて便利である。特に、演算負荷が低減されているので、このように再探索を行う場合に特に有利である。仮に頻繁に再探索を行っても特に問題は生じない。
【００２７】
尚、このような経路探索手段による再探索に加えて又は代えて、経路特定手段による最適経路による再特定が、状態検出手段により検出された移動状況に対応して、行われてもよい。
【００２８】
本発明の経路探索システムの他の態様では、前記経路の一部を、前記経路探索手段により前記最適経路を探索する上で、使用不可能に設定する設定手段を更に備え、前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索する。
【００２９】
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって、経路探索手段により最適経路を探索する上で、使用不可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、経路探索手段により最適経路を探索する上で、使用不可能に設定される。例えば、前述の状況検出手段の検出結果により、移動状況の異常が検出された場合に、これに対応する経路に使用不可能フラグを立てることで、実質的に使用不可能に設定されてもよい。すると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部がこのように実質的に使用不可能に設定されると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が再探索される。従って、経路探索におけるデータ量及び演算負荷は、経路の一部を除外して計算する分だけ、飛躍的に低減されると共に、使用不可能な一部を含む最適経路が決定されるのを未然防止できる。
【００３０】
尚、このような経路探索手段による、使用不可能に設定された一部を除外しての経路探索に加えて又は代えて、経路特定手段による、使用不可能に設定された一部を除外しての最適経路の特定が、行われてもよい。
【００３１】
或いは本発明の経路探索システムの他の態様では、前記経路の一部を使用可能に設定する又は前記経路に対して使用可能な一部を追加する設定手段を更に備え、前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索する。
【００３２】
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって使用可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、使用可能に設定される。例えば、前述の状況検出手段の検出結果に応じて、使用可能に設定されてもよい。すると、経路探索手段によって、このように使用可能に設定された又は追加された一部が入れられた上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部が使用可能に設定される又は追加されると、経路探索手段によって、使用可能に設定された又は追加された一部が入れられた上で、経路が再探索される。従って、使用可能な一部を除外するが故に、不適切な経路（即ち、コストが最小でない経路）が、最適経路として決定されるのを未然防止できる。
【００３３】
尚、このような経路探索手段による、使用可能に設定された一部を入れての経路探索に加えて又は代えて、経路特定手段による、使用可能に設定された一部を入れての最適経路の特定が、行われてもよい。
【００３４】
本発明の経路探索システムの他の態様では、前記移動コストを前記リンク毎に算出するコスト算出手段を更に備え、前記格納手段は、前記算出された移動コストを格納する。
【００３５】
この態様によれば、経路探索手段による経路探索に先立って、例えばプロセッサ、メモリ等を備えてなるコスト算出手段によって、移動コストが、算出され、例えばデータベース等の格納手段に格納される。
【００３６】
この態様では、前記コスト算出手段は、前記搬送車が実際の搬送作業に要した実績時間データから前記搬送車が実際に搬送した前記経路について前記移動コストを算出し、前記格納手段は、前記算出された移動コストで格納内容を更新するように構成してもよい。
【００３７】
このように構成すれば、コスト算出手段によって、例えば搬送車が経路上の目標地点に到達すると直ちに、搬送車が実際の搬送作業に要した実績時間データから搬送車が実際に搬送した経路について移動コストが算出される。更に、この算出された移動コストで、格納手段の格納内容が更新される。このため、経路における混雑の状況等が変化した場合に、経路探索に必要な移動コストを最新のものに更新でき、よりリアルタイム的に実際の経路状況に合致した最適経路を探索可能となる。
【００３８】
本発明の搬送システムは上述の課題を解決するために、上述した本発明に係る経路探索システム（但し、その各種態様を含む）と、前記経路と、前記搬送車と、前記搬送車を前記経路上で移動させる移動手段とを備える。
【００３９】
本発明の搬送システムによれば、上述した本発明に係る経路探索システムを含むので、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。これにより、例えばビークルの推進装置、レールなどを含んでなる移動手段によって、搬送車が、例えば同一の製造ライン内で或いは異なる製造ライン間で、迅速に移動可能となる。例えば、複数の作業装置から一つの製造ラインが構成されており、複数の製造ラインに対応して複数の搬送ラインが設けられ、更に複数の搬送ラインの相互間にも、搬送ラインが設けられている搬送システムにおいて、最適な経路を経由して移動可能にできる。
【００４０】
尚、本発明の搬送システムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４１】
本発明の経路探索方法は上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索方法であって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程とを備える。
【００４２】
本発明の経路探索方法によれば、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。
【００４３】
尚、本発明の経路探索方法においても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４４】
本発明のコンピュータプログラムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムに備えられるコンピュータを、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段として機能させる。
【００４５】
本実施形態のコンピュータプログラムによれば、当該コンピュータプログラムを格納するＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の記録媒体から、当該コンピュータプログラムを、経路探索システムに備えられたコンピュータに読み込んで実行させれば、或いは、当該コンピュータプログラムを通信手段を介してダウンロードさせた後に実行させれば、上述した本発明に係る経路探索システムを比較的簡単に構築できる。これにより、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。
【００４６】
尚、本発明のコンピュータプログラムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４７】
本発明の作用及び他の利得は次に説明する実施するための最良の形態から明らかにされる。
【発明を実施するための最良の形態】
【００４８】
以下、本発明の実施形態について図を参照しつつ説明する。
【００４９】
先ず、本実施形態に係る経路探索システムを含む製造システムの構成について説明する。ここに図１は、本実施形態に係る経路探索システムを含む製造システムのブロック図であり、図２は、図１の経路探索システムの搬送路を製造装置と共に示す概略平面図である。
【００５０】
図１及び図２において、製造システム２００は、主に、製造指示部１、ビークル２、ＣＰＵ１０、及び移動装置１１を備えている。本実施形態に係る経路探索システム１００は、ＣＰＵ１０として、製造システム２００に組み込まれている。ＣＰＵ１０は、経路設定部３、走行検出部４、コスト算出部５、第１経路探索部６、経路特定部７、搬送コントローラ８、及びメモリ９を含む。移動装置１１は、ビークル２を所望の製造装置２１及びストッカ２１ｂへと搬送可能に構成されている。
【００５１】
図２において、移動装置１１は、本発明に係る「移動手段」の一例であって、搬送路１２の他、例えばリニアモータの制御ライン及び電源装置などの、ビークル２をリニアモータ方式で移動させるための機械的及び電気的な機構一式を有する。より具体的には、搬送路１２は、搬送方向に延びると共にビークル２の車輪が転動する転動面を夫々有する一対のレールを有し、更に該一対のレールの間に搬送方向に複数配列された永久磁石を有する。搬送路１２は、ビークル２側に設けられたリニアモータが、その上を走行するための走行路でもあり、ビークル２が走行するための電源信号やその走行を制御するための各種信号がやりとりされる有線の制御線としての機能も有する。
【００５２】
移動装置１１は、モジュールＭ１からＭ４を搬送路１２によって接続している。ここに「モジュール」とは、一つ又は複数のベイによって構成されたＯＨＴ（工程内搬送機器）システムが搬送制御管理するための単位を意味し、「ベイ」とは、ＯＨＴシステムで搬送可能な一又は複数の製造装置の集まりである。モジュールＭ１からＭ４は、大規模ＯＨＴを構成している。大規模ＯＨＴでは、大規模ＯＨＴを構成する移動装置１１の部分によって、モジュールＭ１からＭ４の各々の内部で、ビークル２が走行可能である。更に、移動装置１１は、搬送路１２によって、四方に配置されるモジュールＭ１からＭ４を、ストッカＳＴＫ１からＳＴＫ４を介して、相互に接続している。このモジュールＭ１からＭ４の間の搬送制御が、ＯＨＳ（工程間搬送機器）システムによって管理される。ＯＨＳでは、ＯＨＳを構成する移動装置１１の部分によって、モジュールＭ１からＭ４の間で、ビークル２が走行可能である。
【００５３】
ビークル２は、本発明に係る「搬送車」の一例として、リニアモータにより搬送路１２に沿って走行し、半導体装置製造における各種基板等の被搬送物が格納されたキャリアを搬送する。ビークル２には、図示しない、個々のビークルを独立制御するためのコントローラ、及び位置情報を発信するための位置情報発信部が内蔵されている。
【００５４】
製造装置２１は、本発明に係る「作業装置」の一例として、製造装置コントローラ２２による制御下で、ビークル２により搬送された被搬送物に対して、製品に至る各種処理を行う。
【００５５】
ストッカ２１ｂは、本発明に係る「作業装置」の一例として、ストッカコントローラ２３による制御下で、ビークル２により搬送されたキャリア（例えば、搬送用の容器）或いは被搬送物に対して一部処理が実施されたキャリアを、内部の収容庫へ搬入する又は外部へ搬出するように構成されている。ストッカ２１ｂは、搬送路１２の一部から搬入すると共に搬送路１２の他部へ搬出することで、移動装置１１と共に搬送手段の一部を構成してもよい。
【００５６】
ストッカ２１ｂの各々には、キャリアの搬入又は搬出を行うために、ＯＨＴに対する搬入出口ＳＴＫ−１、及びＯＨＳに対する搬入出口ＳＴＫ−２が夫々備えられている。これらの２つの搬入出口ＳＴＫ−１及びＳＴＫ−２は、ＯＨＴからＯＨＳに、或いはその逆にＯＨＳからＯＨＴに移動手段を切り替えるために備えられている。ストッカ２１ｂには、図示しない、ストッカロボットも備えられている。ストッカロボットは、ストッカ２１ｂの内部で、キャリアを移動させ、所望の搬入出口ＳＴＫ−１又はＳＴＫ−２からキャリアを搬出することで、ＯＨＴ及びＯＨＳの移動手段を切り替える。具体的に、ＯＨＴによって移動されるビークル２がグループＧ３のストッカ２１ｂ（ＳＴＫ１）に差し掛かると、ビークル２によって搬送されるキャリアが、ストッカロボットによって、ストッカＳＴＫ１の内部に、搬入出口ＳＴＫ−１から搬入された後、搬入出口ＳＴＫ−２から搬出される。これにより、ビークル２の移動手段がＯＨＴからＯＨＳに切り替えられ、ビークル２は、ＯＨＳによって移動されることになる。
【００５７】
図２に示すように、搬送路１２には、複数の製造装置２１やストッカ２１ｂからなるグループＧ１からＧ１０が設定されている。モジュールＭ１からＭ４の各々は、グループＧ３及びＧ４、グループＧ５及びＧ６、グループＧ７及びＧ８、グループＧ９及びＧ１０に夫々対応している。モジュールＭ１のストッカＳＴＫ1及びモジュールＭ２のストッカＳＴＫ２は、グループＧ１に対応し、モジュールＭ３のストッカＳＴＫ３及びモジュールＭ４のストッカＳＴＫ４は、グループＧ２に対応している。このようなグループＧ１からＧ１０の各々が、本発明に係る「集合」の一例とされた場合、グループＧ１からＧ１０の各々が「ノード」として扱われ、グループＧ１からＧ１０の相互間が「リンク」として扱われて、リンク毎にコストが算出される。コストは、本発明に係る「移動コスト」の一例として、各グループＧ１からＧ１０において、例えば過去に測定された移動時間の平均値から算出される。或いは、この平均値に対して、経路の現状に応じた修正が施されることで設定される。
【００５８】
各グループＧ１からＧ１０は、グループを結ぶ単位での大まかな最適経路を、探索する際の区分けとなる。更に、そのように大まかな最適経路が決定された後のグループ内部における最適経路を決定する際の範囲となる。即ち、各グループＧ１からＧ１０は、２段階で経路探索を行う際に、段階を隔てる基本的な区分けである。
【００５９】
再び図１において、製造指示部１は、製造工程のスケジュールに従って、製造を指示する旨の製造指示データを、ＣＰＵ１０、製造装置コントローラ２２及びストッカコントローラ２３に入力することで、半導体装置製造の指示を行う。
【００６０】
ＣＰＵ１０は、製造指示部１によって入力される製造指示データに対応して、半導体装置製造の処理を実行しつつ、ビークル２を、例えば後に詳述する最適経路を介して目標地点に到達させるように、各部を制御する。
【００６１】
経路設定部３は、本発明に係る「設定手段」の一例であって、半導体装置製造が開始されるよりも前に、製造指示部１及び走行検出部４の指示により、搬送路１２の部分、即ち部分経路のいずれかを使用可能又は使用不可能に設定する。具体的に、経路設定部３は、該設定を行う部分経路に対して、予め設定されているフラグを、使用可能及び使用不可能のどちらかに変更する。この部分経路の設定変更のデータは、コスト算出部５に入力される。
【００６２】
走行検出部４は、本発明に係る「状態検出手段」の一例として、経路設定部３と同様に、半導体装置製造が開始されるよりも前に、製造指示部１の指示により、搬送路１２を走行する複数のビークル２から発信される位置情報に基づいて、ビークル２の走行状況を検出する。具体的に、走行検出部４は、該位置情報に基づいて、例えばビークル２の走行が異常に遅いことや、走行すべき搬送路１２で走行が止まっていることを検出する。この検出のデータは、経路設定部３及びコスト算出部５に入力される。
【００６３】
コスト算出部５は、本発明に係る「コスト算出手段」の一例として、基本的に、半導体装置製造が開始されるよりも前に、製造指示部１の指示により、グループＧ１からＧ１０の相互間の経路、即ちリンク毎のコストを算出する。
【００６４】
図２に示すように、グループＧ１は、ストッカＳＴＫ１及びストッカＳＴＫ２、グループＧ２は、ストッカＳＴＫ３及びストッカＳＴＫ４から夫々構成される。グループＧ３は、ビークル２が走行する順に、製造装置ＥＱ１１，ＥＱ１２、ストッカＳＴＫ１、グループＧ４は、製造装置ＥＱ１４，ＥＱ１３、グループＧ５は、製造装置ＥＱ２１，ＥＱ２２、ストッカＳＴＫ２、グループＧ６は、製造装置ＥＱ２４，ＥＱ２３、グループＧ７は、ストッカＳＴＫ３、製造装置ＥＱ３１，ＥＱ３２、グループＧ８は、製造装置ＥＱ３４，ＥＱ３３、グループＧ９は、ストッカＳＴＫ４、製造装置ＥＱ４１，ＥＱ４２、グループＧ１０は、製造装置ＥＱ４４，ＥＱ４３から夫々構成される。
【００６５】
具体的には、コスト算出部５は、移動装置１１によって、コスト算出用の所定のビークル２を、グループＧ１からＧ１０の相互間において所定回数移動させる。この移動に要した時間の平均値が、コストとして算出され、予めメモリ９に格納される。或いは、過去に搬送作業を行った一又は複数のビークル２がグループＧ１からＧ１０の相互間の夫々で移動する際に要した移動時間の平均値が、コストとして算出されて、予めメモリ９に格納される。或いは、経験的な又は理論計算に基づくデフォールトの値が、コストとして、予めメモリ９に格納される。
【００６６】
コスト算出部５は、半導体装置製造が開始されてからも、経路設定部３から入力される部分経路の設定変更、及び走行検出部４から入力される走行状況の検出結果に応じて、リンク毎のコストを再度算出し、メモリ９に格納されているコストのデータを更新する。
【００６７】
最適経路の探索方法について、本実施形態では、第１経路探索部６及び第２経路探索部７ａによる２段階の探索が行われる。
【００６８】
第１経路探索部６は、半導体装置製造が開始されると、製造指示部１の指示により、ビークル２が出発地点から目標地点までキャリアを搬送するための、グループを結ぶ単位での最適経路を探索する。ここでは先ず、かかるグループを結ぶ単位での最適経路の複数の候補として、搬送元を含むグループから搬送先を含むグループに至るものが複数特定される。更に、第１経路探索部６は、これら複数の候補のうち、合計コスト（即ち、総コスト）が小さいものを、グループを結ぶ単位での最適経路として決定する。このため、第１経路探索部６は、メモリ９から、各候補に相当するグループ単位のコストを読み出し、読み出した複数のコストを合計して、各候補の合計コストを算出する。経路特定部７は、算出された合計コストのうち最小のものを有する候補を選択する。ここでの合計コストは、図２に示した各候補を構成する一連のグループのコストを合計或いは積算したものであり、各候補を経路として採用した場合における、搬送元を含むグループから搬送先を含むグループまで移動するのにかかる時間の概ねの指標となる。
【００６９】
本実施形態では特に、第１経路探索部６は、コスト算出部５によるコストデータの更新に応答して、グループを結ぶ単位での最適経路を再度探索する。具体的には、第１経路探索部６は、経路設定部３によって部分経路のいずれかが使用不可能に設定された場合に、その使用不可能に設定された経路を除いて、グループを結ぶ単位での最適経路を再度探索する。また、経路設定部３によって部分経路のいずれかが使用可能に設定されたり、使用可能な部分経路が追加された場合に、その使用可能に設定された、又は追加された部分経路を含めて、グループを結ぶ単位での最適経路を再度探索する。更に、走行検出部４によって検出される走行状況に応じて、グループを結ぶ単位での最適経路を再度探索する。
【００７０】
次に、経路特定部７は、第１経路探索部６から入力されたグループを結ぶ単位での最適経路における各グループの内部を通過する経路を特定する。このため、経路特定部７は、第２経路探索部７ａを備える。第２経路探索部７ａは、グループ内を結ぶ単位の最適経路を構成するグループＧ１からＧ１０のうちいずれか複数のグループの各々の内部を、短時間で通過する経路（即ち、グループ内最適経路）を、第１経路探索部６と同様のダイクストラ法を、グループ内部の移動に係るコスト（即ち、グループ内部に存在する製造装置やストッカをノードとし且つこれらの間をリンクとして定義されるコスト）を用いて行うことで、探索される。この結果、個々のグループの内部に存在する複数の製造装置２１又はストッカ２１ｂを結ぶグループ内最適経路が特定される。
【００７１】
尚、グループ内の経路は、単純な場合もある。よって、このようなグループ内最適経路は、コスト計算による探索を行わなくても、例えば、予め設定された製造装置間やポート間を素直に連絡する順路として特定されてもよい。或いはコストに代えて単純に経路長や、右回り又は左回りなどの単純なルールに従って、特定されてもよい。
【００７２】
経路特定部７は、このように第２経路探索部７ａによって探索された個々のグループの内部にあるグループ内最適経路と、第１経路探索部６から入力されたグループを結ぶ単位での最適経路とを統合することで得られる一筋の経路を、最終的に最適経路として特定し、これを示す最適経路データを、搬送コントローラ８に入力する。
【００７３】
搬送コントローラ８は、経路特定部７から入力された最適経路データに基づいて、ビークル２を制御する。この制御により、ビークル２に搬送されるキャリアが、最短時間で目標地点に到達する。
【００７４】
メモリ９は、本発明に係る「格納手段」の一例として、グループ別のコスト及びグループ内経路情報を格納している。コストは、コスト算出部５によって、グループを結ぶリンク毎に予め算出されると共に、経路設定部３による設定変更、及び走行検出部４により検出される走行状況に応じて、更新される。グループ内経路情報は、グループＧ１からＧ１０の各々の内部におけるグループ内経路を示し、第２経路探索部７ａにより適宜参照される。
【００７５】
次に、最適経路を特定する動作処理について説明する。ここに図３は、本実施形態に係る経路探索システムを含む製造システムのグループ別のコスト表の一具体例であり、図４は、図３の経路探索システムにおける最適経路の合計コストの対比表の一具体例である。
【００７６】
図３において、グループ別のコストが示されている。各コストは、１つの製造装置２１、ストッカ２１ｂ、ＯＨＴ、及びＯＨＳ別に設定される、搬送元（即ち、搬送当初の出発地点又は搬送途中の中継地点）及び搬送先（即ち、搬送途中の中継地点又は最終的な目標地点）の組み合わせに対応している。即ち、搬送元及び搬送先を夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。具体的には、作業装置がストッカＳＴＫ１である場合に、搬送元として、搬送されるキャリアがストッカＳＴＫ１の内部にあることを示す「ＳＨＥＬＦ」、キャリアがＯＨＳの搬入出口ＳＴＫ−２にあることを示す「ＯＨＳｉｎ」、及びキャリアがＯＨＴの搬入出口ＳＴＫ−１にあることを示す「ＯＨＴｉｎ」が示されている。この搬送元に対する搬送先として、搬送されるキャリアがＯＨＳに向かうことを示す「ＯＨＳｏｕｔ」、キャリアがＯＨＴに向かうことを示す「ＯＨＴｏｕｔ」、及びキャリアがストッカＳＴＫ１の内部に向かうことを示す「ＳＨＥＬＦ」が示されている。例えば、ストッカＳＴＫ１の内部にあるキャリアがＯＨＴに向かう場合に、搬送元として「ＳＨＥＬＦ」、搬送先として「ＯＨＴｏｕｔ」が選択され、図３に示すように、コストが「１０」となる。
【００７７】
更に、作業装置が移動手段であるＯＨＴ及びＯＨＳである場合に、搬送元及び搬送先として、グループＧ１からＧ１０のいずれかが示されている。即ち、ＯＨＴ及びＯＨＳの場合には特に、グループを夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。例えば、ＯＨＳに対するグループＧ１とグループＧ２との間を、キャリアが搬送される場合に、搬送元として「Ｇ１」、搬送先として「Ｇ２」が選択され、コストが「４０」となる。経路網上における移動時間に大差がないような隣接した又は近接した複数の作業装置は、同一グループに属するように、ここでのグループ分けは行われる。
【００７８】
再び図２において、製造指示部１によって、ストッカ２１ｂ（ＳＴＫ１）内部に収容されているキャリアを、製造装置２１（ＥＱ４４）に搬送する指示がなされると、第１経路探索部６は、ストッカＳＴＫ１から製造装置ＥＱ４４までの最適経路の探索を行う。この探索では、グループを結ぶ単位での最適経路の候補として４つの候補ＴＲである、第１候補（図４における搬送経路Ｎｏ．１）〜第４候補（図４における搬送経路Ｎｏ．４）についての、コスト比較が行われる。図３では、第４の最適経路の候補ＴＲ４を構成するグループのコストが示される。
【００７９】
第１候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−１を出発し、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第１候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ３からグループＧ１０のグループ間のグループ間経路（ＳＴＫ１：ＯＨＴｏｕｔ → ＥＱ４４）の２つのグループ間経路から構成されている。
【００８０】
第２候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１を介して、ストッカＳＴＫ２の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ２の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第２候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ２：ＯＨＳｉｎ）、グループＧ５に対応するグループ間経路（ＳＴＫ２：ＯＨＳｉｎ → ＳＴＫ２：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ５からグループＧ１０のグループ間のグループ間経路（ＳＴＫ２：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８１】
第３候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１及びＧ２を介して、ストッカＳＴＫ３の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ３の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ７を経て、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第３候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１及びＧ２に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ３：ＯＨＳｉｎ）、グループＧ７に対応するグループ間経路（ＳＴＫ３：ＯＨＳｉｎ → ＳＴＫ３：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ７からＧ１０のグループ間のグループ間経路（ＳＴＫ３：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８２】
第４候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１及びＧ２を介して、ストッカＳＴＫ４の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ４の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第４候補は、グループＧ３のグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１及びＧ２に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ４：ＯＨＳｉｎ）、グループＧ９に対応するグループ間経路（ＳＴＫ４：ＯＨＳｉｎ → ＳＴＫ４：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ９からＧ１０のグループ間のグループ間経路（ＳＴＫ４：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８３】
こうして、４つの候補についてのグループを結ぶ単位での合計コストは、メモリ９から読み取られたグループ別のコストが積算されることで算出される。第１候補から第４候補の合計コストは夫々、図４に「合計コスト」として示したように、「１２５」、「２０５」、「１８５」、「９５」となる。これにより、合計コストが、最小値「９５」となる第４候補が、最適経路ＴＲ４として選択される。
【００８４】
このようにグループを結ぶ単位での最適経路ＴＲ４が特定されると、これを構成するグループの各々の内部に存在するグループ内経路とが結び合わされて、一本の道筋になることで、最終的に、最適経路が特定される。
【００８５】
次に、本実施形態に係る経路探索システムの動作処理である経路特定処理について、図５を参照して説明する。
（経路特定処理）
図５は、本実施形態に係る経路探索システムの経路特定処理を示すフローチャートである。
【００８６】
具体的には、図５において、先ず、第１経路探索部６によって、グループを結ぶ単位で、最適経路の複数の候補が探索される（ステップＳ１１）。続いて、探索された複数の候補を構成する、部分経路のいずれかについて、経路設定部３によって使用可能又は使用不可能とする経路変更、或いは走行検出部５によってビークル２の故障等の走行異常があったか否かが判定される（ステップＳ１２）。
【００８７】
ここで、経路変更及び走行異常のいずれかがあったと判定された場合には（ステップＳ１２：ＹＥＳ）、経路変更の対象となる部分経路、及び走行異常とされるビークル２が存在するために通過できないと想定される部分経路が、使用不可能に設定される（ステップＳ１３）。具体的には、この実質的に使用不可能な部分経路を含む候補については、次に行われる候補毎のコスト算出の対象から除外される。或いは、この使用不可能な部分経路に対する移動コストについては、非常に高い値に設定される。これにより、次に行われる候補毎のコスト算出における合計コストが大きくなるが故に、早期に候補から除外される。
【００８８】
他方で、経路変更及び走行異常のいずれもないと判定された場合には（ステップＳ１２：ＮＯ）、ステップS１３における部分経路を使用不可能とする設定が行われることなく、次の処理へ進む。
【００８９】
続いて、コスト算出部５によって、グループ単位でのコストが算出され、メモリ９に格納されているコストデータが更新される（ステップＳ１４）。続いて、第１経路探索部６によって、更新後における合計コストが最小となる候補が、選択される。即ち、グループ単位での最適経路が、この段階で完了する。
【００９０】
続いて、この特定されたグループ単位での最適経路を構成するグループの各々の内部のグループ内経路情報がメモリ９から読み出され、読み出されたグループ内経路情報に基づくグループ内経路が特定される。更に、これらの特定されたグループ内経路とグループを結ぶ単位での最適経路とが統合されることで、最終的に最適経路が特定される（ステップＳ１５）。
【００９１】
その後、搬送コントローラ８によって、特定された最適経路に沿って、ビークル２が制御され、ビークル２に搬送されるキャリアが目標地点に到達される（ステップＳ１６）。これにより、一連の経路特定処理が終了される。
【００９２】
尚、ステップＳ１６で実際にビークル２が目標地点に到達すると直ちに、走行した最適経路を構成するリンクを搬送するのにかかった時間から、これら各リンクについての移動コストが、算出される。更に、この算出された移動コストで、メモリ９内の格納内容が更新されて、その後における最適経路探索に利用される。
【００９３】
このように、実施形態の経路特定システムによれば、グループを結ぶ単位でコストが算出されるので、コストを用いての経路探索に必要とされるデータ数が極端に少なくなる。これにより、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。
【００９４】
また、搬送経路の変更や、ビークル２の走行異常に対応して、再度、リンク毎にコストを算出するので、常に最新のコストに基づいて最適経路が選択される。このため、搬送車の故障や、搬送経路の混雑を要因とする搬送時間のロスを無くすことができ、パフォーマンスを更に向上させることができる。
【００９５】
本発明は、上述した実施形態に限られるものではなく、請求の範囲及び明細書全体から読み取れる発明の要旨或いは思想に反しない範囲で適宜変更可能であり、そのような変更を伴う経路探索システム及び方法、搬送システム、並びにコンピュータプログラムもまた本発明の技術的範囲に含まれるものである。
【図面の簡単な説明】
【００９６】
【図１】実施形態に係る経路探索システムの構成を示すブロック図である。
【図２】実施形態に係る経路探索システムの搬送路を示す平面図である。
【図３】実施形態に係る経路探索システムのグループ別のコストを示すコスト表である。
【図４】実施形態に係る経路探索システムの最適経路の合計コストを示す合計コスト対比表である。
【図５】実施形態に係る経路探索システムの経路特定処理を示すフローチャートである。
【符号の説明】
【００９７】
１…搬送路、２…ビークル、３…経路設定部、４…走行検出部、５…コスト算出部、６…第１経路特定部、７…経路特定部、７ａ…第２経路探索部、８…搬送コントローラ、１１…移動装置、２１…製造装置、２１ｂ…ストッカ、１００…経路探索システム、２００…製造システム
【技術分野】
【０００１】
本発明は、例えば、半導体装置製造用の各種基板などの被搬送物を、工場内に敷設された軌道上を移動するビークル等の搬送車で搬送する搬送システムにおいて、最適経路を探索する経路探索システム及び方法の技術分野に関する。本発明は更に、かかる搬送システム及びコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムの技術分野に関する。
【背景技術】
【０００２】
この種の経路探索システムとして、例えば特許文献１には、複数の分岐や合流を含んで張り巡らされた軌道上で出発地点から目的地点までの最適な経路を探索するのに、所謂“ダイクストラ法”を利用した技術が開示されている。この技術では、全経路の各々が、最適経路の候補とされる。該各々の候補を構成するリンクにおける移動コスト（即ち、分岐点や合流点に相当するノード間を走行するのにかかる時間或いは時間に対応する評価値）が、出発地点から目標地点までについて積算される。その後、候補のうち出発地点から目的地点までの移動コストが最小となるものが、最適経路として決定される。
【０００３】
【特許文献１】特開平１０−３２００４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述の背景技術によれば、作業装置を夫々ノードとし且つ作業装置間に位置する経路部分を夫々リンクとして、移動コストが設定されている。このため、経路探索において取り扱うデータ数が膨大となり、特に近時における経路の複雑高度化或いは作業装置数の増大に伴って、コンピュータにかかる負荷は膨大となるという技術的問題点がある。
【０００５】
本発明は、例えば、上述した問題点に鑑みなされたものであり、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索可能である経路探索システム及び方法、これを備えた搬送システム、並びにコンピュータをこのような経路探索システムとして機能させるコンピュータプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明の経路探索システムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムであって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段とを備える。
【０００７】
本発明の経路探索システムによれば、実際の経路探索の動作に先立って、例えばデータベース、メモリ等の格納手段に、経路上における搬送車の移動コストが格納される。ここに「経路」とは、例えばレールなど、被搬送物が搭載された又はされない状態で搬送車が移動可能である、経路を意味する。「搬送車」とは、例えばビークル等の経路上を移動すると共に被搬送物を積載可能に構成された台車等の車を意味する。
【０００８】
本発明では特に、移動コストは、複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される。ここに「作業装置」とは、例えば半導体基板などの被搬送物に対して、成膜、加熱、配線、エッチング等を行う製造装置や、被搬送物の一時的な格納を行うストッカを含む、被搬送物に対して各種処理を施す装置を意味する。作業装置は、経路の脇に並んでいるか、又は経路の一部をなすように並んでいる。経路の一部をなす場合としては、例えば、単一の作業装置における搬入口と搬出口との経路における位置が相互に異なることで、経路の一部をなすように並ぶ場合がある。本発明に係る「集合」は、このような作業装置を複数含んで構成される集合を含む。但し、作業装置の一つから構成される集合を含んでもよい。集合の間には、搬送車が移動される経路（以下適宜「集合間経路」と呼ぶ）が存在し、集合の内部にも、搬送車が移動される経路（以下適宜「集合内経路」）が存在する。例えば、個々の集合は、個々の製造ラインに対応してもよいし、複数の集合が単一の製造ラインの中に存在していてもよい。
【０００９】
本発明に係る「移動コスト」は、このように複数の作業装置を含んでなる集合の相互間の経路部分が夫々リンクとされると共に集合が夫々ノードとされた上で、規定されている。「リンク」は、経路において、分岐点、合流点、交差点などの間を直接結んでおり、移動の仕方について単純に進むことしか選択枝がない、一本の直線又は曲線状若しくは屈曲状の経路部分に対応する。「ノード」は、経路において、リンクの端に位置しており、典型的には、分岐点、合流点、交差点、行き止り点、更にはストッカの搬出搬入箇所など、搬送経路における移動の仕方についての選択枝が複数存在する点或いは箇所に対応する。「移動コスト」とは、このような集合をノードとし且つ集合間をリンクとする経路探索を行う際に、一つのノードからこれに隣接するノードまで一つのリンクを介して移動するのにかかる時間若しくは時間に比例する指標であるコストを意味する。例えば、同一の距離でも、混雑等により移動時間が長ければ、移動コストの値は大きくなる。このような移動コストを用いれば、次に説明するように、典型的には、上述の如く集合に対応した移動コストを用いてのダイクストラ法によって、複数の集合を結ぶ単位での経路探索を行える。
【００１０】
特に、このように複数の作業装置を含んでなる集合をノードとして、移動コストが規定されるので、作業装置をノードとする場合と比較して、複数の作業装置を集合にまとめた分だけ、経路探索に供される移動コストの総数は、削減される。即ち、格納手段に格納される移動コストのデータ量は、先ず低減される。また、作業装置等の設備が新規に設置される場合に、その新規設備は何れかのノードに設置される。この何れかのノードを含んでなる経路における移動コストの修正では、その新規設備が設置されたノードのみにおいて、移動コストが算出されればよく、既に使用されている規定済みの移動コストは、該経路において流用可能である。このため、新規設備を立ち上げる時間を短縮することができる。
【００１１】
尚、以上のような移動コストは、例えば過去における各集合に関しての平均移動時間から予め特定して、格納手段に格納してもよい。或いは、実際の経路探索の動作を行う際に先ず、経路における混雑状況等を考慮して、かかる移動コストを検出或いは算出し、格納手段に新たに格納したり、その格納内容を更新してもよい。或いは、搬送作業の際に、搬送車が各集合を移動するのに要した移動時間が実測され、搬送作業が終了されると直ちに、その経路についてのコスト計算が実行或いは再実行されることで、格納手段の格納内容が新設或いは更新されてもよい。この場合に、移動コストは、最新の経路の混雑状況を反映させたものとなる。
【００１２】
その後、実際の経路探索の動作時には、例えばプロセッサ、メモリ等を備えてなる経路探索手段によって、上述の如く格納手段に格納された移動コストに基づいて、最適経路の少なくとも一部が、複数の集合を結ぶ単位で探索される。例えば、複数の集合のうち出発地点を含む出発集合から、複数の集合のうち目的地点を含む目標集合までの経路が、出発集合から目標集合まで複数の集合を結ぶ形で探索される。言い換えれば、先ずは、少なくとも最適経路の一部について、経路探索手段によって、例えば製造ライン単位など、集合を結ぶ単位での大まかな経路探索が行われる。
【００１３】
このように経路探索手段による経路探索では、少なくとも最適経路の一部について、集合の内部において個々の作業装置間を結ぶ経路部分が、夫々リンクとして扱われるのではなく、集合の相互間を結ぶ経路部分が夫々リンクとして扱われる。これと共に、個々の作業装置が夫々ノードとして扱われるのではなく、集合が夫々ノードとして扱われる。従って、個々の作業装置間を結ぶ経路部分が夫々リンクとして扱われ、個々の作業装置が夫々ノードとして扱われる場合における、経路探索と比べて、データ量及び演算量が飛躍的に低減される。特に、格納手段に格納される移動コストの総数の削減に対して、移動コストに基づく経路探索におけるデータ量及び演算量の削減は、極めて顕著となる。経路探索で用いる移動コストの総数の小規模な削減であっても、経路探索においては大規模なデータ量及び演算量の削減に繋がる。
【００１４】
このような経路探索手段による探索と相前後して又は並列に、例えばプロセッサ、メモリ等を備えてなる経路特定手段によって、探索された最適経路の少なくとも一部と、この少なくとも一部に含まれる一又は複数の集合の内部に存在する経路の部分とが統合されることで、最適経路の全体が特定される。ここに「統合する」とは、探索された集合を結ぶ集合間経路と、探索された集合の各々の内部に存在する集合内経路とを、一本の道筋に結び合わせて最適経路とすることを意味する。例えば、経路探索手段による探索の後に、探索された集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われる。或いは、経路探索手段による探索の以前に、任意の集合の内部の夫々について、経路特定手段によってダイクストラ法による集合内経路の探索が行われて、探索された集合内経路が集合に対応付けられて格納手段等に格納され、その後、経路探索手段により探索された集合に対応する集合内経路が格納手段等から呼び出されてもよい。
【００１５】
ここで特に、本願発明者の研究によれば、全体として複雑高度化された経路であっても、一つの集合についてみれば、その内部における経路及び経路を介しての移動は、相対的に単純であり、移動にかかる時間は、短時間であることが判明している。言い換えれば、同一集合内であれば、目標地点がどの作業装置であったとしても、時間的に或いはコスト的に大差がないことが判明している。よって、上述の経路特定手段による集合内経路の探索或いは決定は、例えば同一製造ライン内における経路の探索であれば、複数の製造ラインに跨る経路の探索或いは決定と比べて、飛躍的に単純なもので足りる。例えば、ダイクストラ法を用いても、個々の集合についてみれば、リンク及びノードの構成は単純なものであり、経路探索にかかるデータ量及び演算処理も、飛躍的に低減されることになる。従って、先ず集合を結ぶ単位で大まかな経路探索を行って、最適経路をなす集合及び集合間経路を決定した上で、各集合内における集合内経路を特定し、これらを結んで得られる最適経路は、初めから経路を最大限に細かく見てダイクストラ法により経路探索を行った場合に得られる最適経路と比べて、実践上は殆ど又は全く遜色のないものとなる。
【００１６】
そこで本発明において、経路探索手段により、集合を結ぶ単位で大まかな経路探索を行うと共に、経路特定手段により、集合内での経路探索或いは経路の決定を行えば、決定される最適経路は、実践上は、理論上における真の最適経路と殆ど又は全く同じ経路となる。或いは、少なくとも、真の最適経路に相当に近いものとなる。他方で、このような適切な経路を求める際に、集合単位で経路探索するのに必要なデータ量及び演算量と集合内で経路探索或いは決定を行うのに必要なデータ量及び演算量との合算は、一段階で真の最適経路を探索する場合と比べて飛躍的に低減されている。
【００１７】
以上の結果、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。従って、リアルタイム或いはそれに近い形で経路探索を行うことも容易となり、搬送システムにおいて迅速な搬送が可能となる。更に、これらを実践するために、経済性に見合わないような高性能のコンピュータを用いることも効果的に回避できる。
【００１８】
尚、本発明で探索される最適経路の精度を高める観点からは、一集合にまとめられる複数の作業装置は、経路探索上で同一ノードとして扱っても、最終的に探索される経路に差がでないような関係にある、典型的に近くに横並びになっているような複数の作業装置とするのがよい。例えば、小規模な製造ラインであって、その製造ライン内における移動が短時間で行われ得るような製造ラインであれば、一つの集合と一つの製造ラインとを対応させるのがよい。他方、大規模な製造ラインであって、その製造ライン内における移動が長時間で行われ得るような製造ラインであれば、複数の集合と一つの製造ラインとを対応させるのがよい。
【００１９】
他方で、複数の作業装置を集合にまとめる箇所が多い程、移動コストの総数は低減され、よって経路探索時におけるデータ量及び演算量の削減の効果は、より顕著に得られる。但し、集合にまとめる箇所が一箇所だけであっても、経路探索時におけるデータ量及び演算量の削減の効果は、相応に得られる。
【００２０】
加えて、集合間の経路と集合との接続点、即ち、各集合の搬出口及び搬入口は、一つの集合に対して複数個所存在してもよい。一つの集合を一つのノードとして扱えば、上述の如き移動時間又は移動コストを用いた経路探索は、極めて単純化できる。或いは、搬出口及び搬入口の少なくとも一方が複数ある場合、搬出口又は搬入口別に複数の集合として扱って、即ち複数のノードであるものとして扱っても（従って、リンクもそれに応じて増えても）、移動時間又は移動コストを用いた経路探索は、全ての作業装置の各々をノードとして扱う場合と比べれば、なお顕著に単純化できる。
【００２１】
本発明の経路探索システムの一態様では、前記経路特定手段は、前記複数の作業装置間を夫々結ぶ前記経路の部分を夫々リンクとすると共に前記複数の作業装置を夫々ノードとする前記搬送車の移動コストに基づいて、前記経路の部分を探索し、前記探索された少なくとも一部と前記探索された経路の部分とを統合することで、最適経路を特定する。
【００２２】
この態様によれば、各集合内における経路探索は、作業装置をノードとし且つ作業装置間をリンクとする移動コストを用いて、典型的にはダイクストラ法によって行われるが、例えば同一製造ラインなど、同一集合の内部での経路の探索である。このため、経路特定手段による経路探索に必要なデータ量及び演算負荷が、過度に増大することはない。
【００２３】
或いは本発明の経路探索システムの他の態様では、前記格納手段は、前記ノード及び前記リンクに対応付けて、前記集合の内部における前記経路の部分を示す集合内経路情報を更に格納しており、前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、最適経路を特定する。
【００２４】
この態様によれば、各集合内における経路の決定は、格納手段に格納された集合内経路情報を参照することで行われるが、例えば同一製造ラインなど、同一集合の内部での経路の決定である。このため、経路特定手段による経路の決定に必要なデータ量及び演算負荷が、過度に増大することはない。
【００２５】
本発明の経路探索システムの他の態様では、前記搬送車が移動する際の移動状況を検出する状態検出手段を更に備え、前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する。
【００２６】
この態様によれば、例えばプロセッサ、センサ等を有する状態検出手段によって、例えば各集合内を移動する際の平均移動速度、混雑状態や、集合間を移動する際の平均移動速度、混雑状態などの、搬送車が移動する際の移動状況が検出される。すると、経路探索手段によって、検出された移動状況に対応して、経路が再探索される。従って、特定の集合で或いは特定の集合間で平均移動速度が変化したり、故障や搬送量の過多に起因して混雑やデッドロックが発生したり、回復や搬送量の低下に起因して混雑やデッドロックが解消した場合に、最適経路が探索され直される。従って、リアルタイム的に各時点に見合った最適経路が探索されることとなり、実践上極めて便利である。特に、演算負荷が低減されているので、このように再探索を行う場合に特に有利である。仮に頻繁に再探索を行っても特に問題は生じない。
【００２７】
尚、このような経路探索手段による再探索に加えて又は代えて、経路特定手段による最適経路による再特定が、状態検出手段により検出された移動状況に対応して、行われてもよい。
【００２８】
本発明の経路探索システムの他の態様では、前記経路の一部を、前記経路探索手段により前記最適経路を探索する上で、使用不可能に設定する設定手段を更に備え、前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索する。
【００２９】
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって、経路探索手段により最適経路を探索する上で、使用不可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、経路探索手段により最適経路を探索する上で、使用不可能に設定される。例えば、前述の状況検出手段の検出結果により、移動状況の異常が検出された場合に、これに対応する経路に使用不可能フラグを立てることで、実質的に使用不可能に設定されてもよい。すると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部がこのように実質的に使用不可能に設定されると、経路探索手段によって、このように実質的に使用不可能に設定された一部が除外された上で、経路が再探索される。従って、経路探索におけるデータ量及び演算負荷は、経路の一部を除外して計算する分だけ、飛躍的に低減されると共に、使用不可能な一部を含む最適経路が決定されるのを未然防止できる。
【００３０】
尚、このような経路探索手段による、使用不可能に設定された一部を除外しての経路探索に加えて又は代えて、経路特定手段による、使用不可能に設定された一部を除外しての最適経路の特定が、行われてもよい。
【００３１】
或いは本発明の経路探索システムの他の態様では、前記経路の一部を使用可能に設定する又は前記経路に対して使用可能な一部を追加する設定手段を更に備え、前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索する。
【００３２】
この態様によれば、例えばキーボード、マウス、プロセッサ等を備えてなる設定手段によって、経路の一部が、ユーザによって使用可能に設定される。或いは、経路の一部が、故障診断を行う手段若しくは混雑診断を行う手段による診断結果に応じて、又はメンテナンスが行われている箇所を特定する手段による特定結果に応じて、使用可能に設定される。例えば、前述の状況検出手段の検出結果に応じて、使用可能に設定されてもよい。すると、経路探索手段によって、このように使用可能に設定された又は追加された一部が入れられた上で、経路が探索される。或いは、既に経路が設定されていた場合に、設定手段によって、経路の一部が使用可能に設定される又は追加されると、経路探索手段によって、使用可能に設定された又は追加された一部が入れられた上で、経路が再探索される。従って、使用可能な一部を除外するが故に、不適切な経路（即ち、コストが最小でない経路）が、最適経路として決定されるのを未然防止できる。
【００３３】
尚、このような経路探索手段による、使用可能に設定された一部を入れての経路探索に加えて又は代えて、経路特定手段による、使用可能に設定された一部を入れての最適経路の特定が、行われてもよい。
【００３４】
本発明の経路探索システムの他の態様では、前記移動コストを前記リンク毎に算出するコスト算出手段を更に備え、前記格納手段は、前記算出された移動コストを格納する。
【００３５】
この態様によれば、経路探索手段による経路探索に先立って、例えばプロセッサ、メモリ等を備えてなるコスト算出手段によって、移動コストが、算出され、例えばデータベース等の格納手段に格納される。
【００３６】
この態様では、前記コスト算出手段は、前記搬送車が実際の搬送作業に要した実績時間データから前記搬送車が実際に搬送した前記経路について前記移動コストを算出し、前記格納手段は、前記算出された移動コストで格納内容を更新するように構成してもよい。
【００３７】
このように構成すれば、コスト算出手段によって、例えば搬送車が経路上の目標地点に到達すると直ちに、搬送車が実際の搬送作業に要した実績時間データから搬送車が実際に搬送した経路について移動コストが算出される。更に、この算出された移動コストで、格納手段の格納内容が更新される。このため、経路における混雑の状況等が変化した場合に、経路探索に必要な移動コストを最新のものに更新でき、よりリアルタイム的に実際の経路状況に合致した最適経路を探索可能となる。
【００３８】
本発明の搬送システムは上述の課題を解決するために、上述した本発明に係る経路探索システム（但し、その各種態様を含む）と、前記経路と、前記搬送車と、前記搬送車を前記経路上で移動させる移動手段とを備える。
【００３９】
本発明の搬送システムによれば、上述した本発明に係る経路探索システムを含むので、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。これにより、例えばビークルの推進装置、レールなどを含んでなる移動手段によって、搬送車が、例えば同一の製造ライン内で或いは異なる製造ライン間で、迅速に移動可能となる。例えば、複数の作業装置から一つの製造ラインが構成されており、複数の製造ラインに対応して複数の搬送ラインが設けられ、更に複数の搬送ラインの相互間にも、搬送ラインが設けられている搬送システムにおいて、最適な経路を経由して移動可能にできる。
【００４０】
尚、本発明の搬送システムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４１】
本発明の経路探索方法は上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索方法であって、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程とを備える。
【００４２】
本発明の経路探索方法によれば、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。
【００４３】
尚、本発明の経路探索方法においても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４４】
本発明のコンピュータプログラムは上記課題を解決するために、被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムに備えられるコンピュータを、前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段として機能させる。
【００４５】
本実施形態のコンピュータプログラムによれば、当該コンピュータプログラムを格納するＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の記録媒体から、当該コンピュータプログラムを、経路探索システムに備えられたコンピュータに読み込んで実行させれば、或いは、当該コンピュータプログラムを通信手段を介してダウンロードさせた後に実行させれば、上述した本発明に係る経路探索システムを比較的簡単に構築できる。これにより、上述した本発明に係る経路探索システムの場合と同様に、取り扱うデータ数及び演算負荷を低減しつつ、最適経路を探索でき、リアルタイム或いはそれに近い形で経路探索を行うことも容易となる。
【００４６】
尚、本発明のコンピュータプログラムにおいても、上述した本発明の経路探索システムにおける各種態様と同様の各種態様を採ることが可能である。
【００４７】
本発明の作用及び他の利得は次に説明する実施するための最良の形態から明らかにされる。
【発明を実施するための最良の形態】
【００４８】
以下、本発明の実施形態について図を参照しつつ説明する。
【００４９】
先ず、本実施形態に係る経路探索システムを含む製造システムの構成について説明する。ここに図１は、本実施形態に係る経路探索システムを含む製造システムのブロック図であり、図２は、図１の経路探索システムの搬送路を製造装置と共に示す概略平面図である。
【００５０】
図１及び図２において、製造システム２００は、主に、製造指示部１、ビークル２、ＣＰＵ１０、及び移動装置１１を備えている。本実施形態に係る経路探索システム１００は、ＣＰＵ１０として、製造システム２００に組み込まれている。ＣＰＵ１０は、経路設定部３、走行検出部４、コスト算出部５、第１経路探索部６、経路特定部７、搬送コントローラ８、及びメモリ９を含む。移動装置１１は、ビークル２を所望の製造装置２１及びストッカ２１ｂへと搬送可能に構成されている。
【００５１】
図２において、移動装置１１は、本発明に係る「移動手段」の一例であって、搬送路１２の他、例えばリニアモータの制御ライン及び電源装置などの、ビークル２をリニアモータ方式で移動させるための機械的及び電気的な機構一式を有する。より具体的には、搬送路１２は、搬送方向に延びると共にビークル２の車輪が転動する転動面を夫々有する一対のレールを有し、更に該一対のレールの間に搬送方向に複数配列された永久磁石を有する。搬送路１２は、ビークル２側に設けられたリニアモータが、その上を走行するための走行路でもあり、ビークル２が走行するための電源信号やその走行を制御するための各種信号がやりとりされる有線の制御線としての機能も有する。
【００５２】
移動装置１１は、モジュールＭ１からＭ４を搬送路１２によって接続している。ここに「モジュール」とは、一つ又は複数のベイによって構成されたＯＨＴ（工程内搬送機器）システムが搬送制御管理するための単位を意味し、「ベイ」とは、ＯＨＴシステムで搬送可能な一又は複数の製造装置の集まりである。モジュールＭ１からＭ４は、大規模ＯＨＴを構成している。大規模ＯＨＴでは、大規模ＯＨＴを構成する移動装置１１の部分によって、モジュールＭ１からＭ４の各々の内部で、ビークル２が走行可能である。更に、移動装置１１は、搬送路１２によって、四方に配置されるモジュールＭ１からＭ４を、ストッカＳＴＫ１からＳＴＫ４を介して、相互に接続している。このモジュールＭ１からＭ４の間の搬送制御が、ＯＨＳ（工程間搬送機器）システムによって管理される。ＯＨＳでは、ＯＨＳを構成する移動装置１１の部分によって、モジュールＭ１からＭ４の間で、ビークル２が走行可能である。
【００５３】
ビークル２は、本発明に係る「搬送車」の一例として、リニアモータにより搬送路１２に沿って走行し、半導体装置製造における各種基板等の被搬送物が格納されたキャリアを搬送する。ビークル２には、図示しない、個々のビークルを独立制御するためのコントローラ、及び位置情報を発信するための位置情報発信部が内蔵されている。
【００５４】
製造装置２１は、本発明に係る「作業装置」の一例として、製造装置コントローラ２２による制御下で、ビークル２により搬送された被搬送物に対して、製品に至る各種処理を行う。
【００５５】
ストッカ２１ｂは、本発明に係る「作業装置」の一例として、ストッカコントローラ２３による制御下で、ビークル２により搬送されたキャリア（例えば、搬送用の容器）或いは被搬送物に対して一部処理が実施されたキャリアを、内部の収容庫へ搬入する又は外部へ搬出するように構成されている。ストッカ２１ｂは、搬送路１２の一部から搬入すると共に搬送路１２の他部へ搬出することで、移動装置１１と共に搬送手段の一部を構成してもよい。
【００５６】
ストッカ２１ｂの各々には、キャリアの搬入又は搬出を行うために、ＯＨＴに対する搬入出口ＳＴＫ−１、及びＯＨＳに対する搬入出口ＳＴＫ−２が夫々備えられている。これらの２つの搬入出口ＳＴＫ−１及びＳＴＫ−２は、ＯＨＴからＯＨＳに、或いはその逆にＯＨＳからＯＨＴに移動手段を切り替えるために備えられている。ストッカ２１ｂには、図示しない、ストッカロボットも備えられている。ストッカロボットは、ストッカ２１ｂの内部で、キャリアを移動させ、所望の搬入出口ＳＴＫ−１又はＳＴＫ−２からキャリアを搬出することで、ＯＨＴ及びＯＨＳの移動手段を切り替える。具体的に、ＯＨＴによって移動されるビークル２がグループＧ３のストッカ２１ｂ（ＳＴＫ１）に差し掛かると、ビークル２によって搬送されるキャリアが、ストッカロボットによって、ストッカＳＴＫ１の内部に、搬入出口ＳＴＫ−１から搬入された後、搬入出口ＳＴＫ−２から搬出される。これにより、ビークル２の移動手段がＯＨＴからＯＨＳに切り替えられ、ビークル２は、ＯＨＳによって移動されることになる。
【００５７】
図２に示すように、搬送路１２には、複数の製造装置２１やストッカ２１ｂからなるグループＧ１からＧ１０が設定されている。モジュールＭ１からＭ４の各々は、グループＧ３及びＧ４、グループＧ５及びＧ６、グループＧ７及びＧ８、グループＧ９及びＧ１０に夫々対応している。モジュールＭ１のストッカＳＴＫ1及びモジュールＭ２のストッカＳＴＫ２は、グループＧ１に対応し、モジュールＭ３のストッカＳＴＫ３及びモジュールＭ４のストッカＳＴＫ４は、グループＧ２に対応している。このようなグループＧ１からＧ１０の各々が、本発明に係る「集合」の一例とされた場合、グループＧ１からＧ１０の各々が「ノード」として扱われ、グループＧ１からＧ１０の相互間が「リンク」として扱われて、リンク毎にコストが算出される。コストは、本発明に係る「移動コスト」の一例として、各グループＧ１からＧ１０において、例えば過去に測定された移動時間の平均値から算出される。或いは、この平均値に対して、経路の現状に応じた修正が施されることで設定される。
【００５８】
各グループＧ１からＧ１０は、グループを結ぶ単位での大まかな最適経路を、探索する際の区分けとなる。更に、そのように大まかな最適経路が決定された後のグループ内部における最適経路を決定する際の範囲となる。即ち、各グループＧ１からＧ１０は、２段階で経路探索を行う際に、段階を隔てる基本的な区分けである。
【００５９】
再び図１において、製造指示部１は、製造工程のスケジュールに従って、製造を指示する旨の製造指示データを、ＣＰＵ１０、製造装置コントローラ２２及びストッカコントローラ２３に入力することで、半導体装置製造の指示を行う。
【００６０】
ＣＰＵ１０は、製造指示部１によって入力される製造指示データに対応して、半導体装置製造の処理を実行しつつ、ビークル２を、例えば後に詳述する最適経路を介して目標地点に到達させるように、各部を制御する。
【００６１】
経路設定部３は、本発明に係る「設定手段」の一例であって、半導体装置製造が開始されるよりも前に、製造指示部１及び走行検出部４の指示により、搬送路１２の部分、即ち部分経路のいずれかを使用可能又は使用不可能に設定する。具体的に、経路設定部３は、該設定を行う部分経路に対して、予め設定されているフラグを、使用可能及び使用不可能のどちらかに変更する。この部分経路の設定変更のデータは、コスト算出部５に入力される。
【００６２】
走行検出部４は、本発明に係る「状態検出手段」の一例として、経路設定部３と同様に、半導体装置製造が開始されるよりも前に、製造指示部１の指示により、搬送路１２を走行する複数のビークル２から発信される位置情報に基づいて、ビークル２の走行状況を検出する。具体的に、走行検出部４は、該位置情報に基づいて、例えばビークル２の走行が異常に遅いことや、走行すべき搬送路１２で走行が止まっていることを検出する。この検出のデータは、経路設定部３及びコスト算出部５に入力される。
【００６３】
コスト算出部５は、本発明に係る「コスト算出手段」の一例として、基本的に、半導体装置製造が開始されるよりも前に、製造指示部１の指示により、グループＧ１からＧ１０の相互間の経路、即ちリンク毎のコストを算出する。
【００６４】
図２に示すように、グループＧ１は、ストッカＳＴＫ１及びストッカＳＴＫ２、グループＧ２は、ストッカＳＴＫ３及びストッカＳＴＫ４から夫々構成される。グループＧ３は、ビークル２が走行する順に、製造装置ＥＱ１１，ＥＱ１２、ストッカＳＴＫ１、グループＧ４は、製造装置ＥＱ１４，ＥＱ１３、グループＧ５は、製造装置ＥＱ２１，ＥＱ２２、ストッカＳＴＫ２、グループＧ６は、製造装置ＥＱ２４，ＥＱ２３、グループＧ７は、ストッカＳＴＫ３、製造装置ＥＱ３１，ＥＱ３２、グループＧ８は、製造装置ＥＱ３４，ＥＱ３３、グループＧ９は、ストッカＳＴＫ４、製造装置ＥＱ４１，ＥＱ４２、グループＧ１０は、製造装置ＥＱ４４，ＥＱ４３から夫々構成される。
【００６５】
具体的には、コスト算出部５は、移動装置１１によって、コスト算出用の所定のビークル２を、グループＧ１からＧ１０の相互間において所定回数移動させる。この移動に要した時間の平均値が、コストとして算出され、予めメモリ９に格納される。或いは、過去に搬送作業を行った一又は複数のビークル２がグループＧ１からＧ１０の相互間の夫々で移動する際に要した移動時間の平均値が、コストとして算出されて、予めメモリ９に格納される。或いは、経験的な又は理論計算に基づくデフォールトの値が、コストとして、予めメモリ９に格納される。
【００６６】
コスト算出部５は、半導体装置製造が開始されてからも、経路設定部３から入力される部分経路の設定変更、及び走行検出部４から入力される走行状況の検出結果に応じて、リンク毎のコストを再度算出し、メモリ９に格納されているコストのデータを更新する。
【００６７】
最適経路の探索方法について、本実施形態では、第１経路探索部６及び第２経路探索部７ａによる２段階の探索が行われる。
【００６８】
第１経路探索部６は、半導体装置製造が開始されると、製造指示部１の指示により、ビークル２が出発地点から目標地点までキャリアを搬送するための、グループを結ぶ単位での最適経路を探索する。ここでは先ず、かかるグループを結ぶ単位での最適経路の複数の候補として、搬送元を含むグループから搬送先を含むグループに至るものが複数特定される。更に、第１経路探索部６は、これら複数の候補のうち、合計コスト（即ち、総コスト）が小さいものを、グループを結ぶ単位での最適経路として決定する。このため、第１経路探索部６は、メモリ９から、各候補に相当するグループ単位のコストを読み出し、読み出した複数のコストを合計して、各候補の合計コストを算出する。経路特定部７は、算出された合計コストのうち最小のものを有する候補を選択する。ここでの合計コストは、図２に示した各候補を構成する一連のグループのコストを合計或いは積算したものであり、各候補を経路として採用した場合における、搬送元を含むグループから搬送先を含むグループまで移動するのにかかる時間の概ねの指標となる。
【００６９】
本実施形態では特に、第１経路探索部６は、コスト算出部５によるコストデータの更新に応答して、グループを結ぶ単位での最適経路を再度探索する。具体的には、第１経路探索部６は、経路設定部３によって部分経路のいずれかが使用不可能に設定された場合に、その使用不可能に設定された経路を除いて、グループを結ぶ単位での最適経路を再度探索する。また、経路設定部３によって部分経路のいずれかが使用可能に設定されたり、使用可能な部分経路が追加された場合に、その使用可能に設定された、又は追加された部分経路を含めて、グループを結ぶ単位での最適経路を再度探索する。更に、走行検出部４によって検出される走行状況に応じて、グループを結ぶ単位での最適経路を再度探索する。
【００７０】
次に、経路特定部７は、第１経路探索部６から入力されたグループを結ぶ単位での最適経路における各グループの内部を通過する経路を特定する。このため、経路特定部７は、第２経路探索部７ａを備える。第２経路探索部７ａは、グループ内を結ぶ単位の最適経路を構成するグループＧ１からＧ１０のうちいずれか複数のグループの各々の内部を、短時間で通過する経路（即ち、グループ内最適経路）を、第１経路探索部６と同様のダイクストラ法を、グループ内部の移動に係るコスト（即ち、グループ内部に存在する製造装置やストッカをノードとし且つこれらの間をリンクとして定義されるコスト）を用いて行うことで、探索される。この結果、個々のグループの内部に存在する複数の製造装置２１又はストッカ２１ｂを結ぶグループ内最適経路が特定される。
【００７１】
尚、グループ内の経路は、単純な場合もある。よって、このようなグループ内最適経路は、コスト計算による探索を行わなくても、例えば、予め設定された製造装置間やポート間を素直に連絡する順路として特定されてもよい。或いはコストに代えて単純に経路長や、右回り又は左回りなどの単純なルールに従って、特定されてもよい。
【００７２】
経路特定部７は、このように第２経路探索部７ａによって探索された個々のグループの内部にあるグループ内最適経路と、第１経路探索部６から入力されたグループを結ぶ単位での最適経路とを統合することで得られる一筋の経路を、最終的に最適経路として特定し、これを示す最適経路データを、搬送コントローラ８に入力する。
【００７３】
搬送コントローラ８は、経路特定部７から入力された最適経路データに基づいて、ビークル２を制御する。この制御により、ビークル２に搬送されるキャリアが、最短時間で目標地点に到達する。
【００７４】
メモリ９は、本発明に係る「格納手段」の一例として、グループ別のコスト及びグループ内経路情報を格納している。コストは、コスト算出部５によって、グループを結ぶリンク毎に予め算出されると共に、経路設定部３による設定変更、及び走行検出部４により検出される走行状況に応じて、更新される。グループ内経路情報は、グループＧ１からＧ１０の各々の内部におけるグループ内経路を示し、第２経路探索部７ａにより適宜参照される。
【００７５】
次に、最適経路を特定する動作処理について説明する。ここに図３は、本実施形態に係る経路探索システムを含む製造システムのグループ別のコスト表の一具体例であり、図４は、図３の経路探索システムにおける最適経路の合計コストの対比表の一具体例である。
【００７６】
図３において、グループ別のコストが示されている。各コストは、１つの製造装置２１、ストッカ２１ｂ、ＯＨＴ、及びＯＨＳ別に設定される、搬送元（即ち、搬送当初の出発地点又は搬送途中の中継地点）及び搬送先（即ち、搬送途中の中継地点又は最終的な目標地点）の組み合わせに対応している。即ち、搬送元及び搬送先を夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。具体的には、作業装置がストッカＳＴＫ１である場合に、搬送元として、搬送されるキャリアがストッカＳＴＫ１の内部にあることを示す「ＳＨＥＬＦ」、キャリアがＯＨＳの搬入出口ＳＴＫ−２にあることを示す「ＯＨＳｉｎ」、及びキャリアがＯＨＴの搬入出口ＳＴＫ−１にあることを示す「ＯＨＴｉｎ」が示されている。この搬送元に対する搬送先として、搬送されるキャリアがＯＨＳに向かうことを示す「ＯＨＳｏｕｔ」、キャリアがＯＨＴに向かうことを示す「ＯＨＴｏｕｔ」、及びキャリアがストッカＳＴＫ１の内部に向かうことを示す「ＳＨＥＬＦ」が示されている。例えば、ストッカＳＴＫ１の内部にあるキャリアがＯＨＴに向かう場合に、搬送元として「ＳＨＥＬＦ」、搬送先として「ＯＨＴｏｕｔ」が選択され、図３に示すように、コストが「１０」となる。
【００７７】
更に、作業装置が移動手段であるＯＨＴ及びＯＨＳである場合に、搬送元及び搬送先として、グループＧ１からＧ１０のいずれかが示されている。即ち、ＯＨＴ及びＯＨＳの場合には特に、グループを夫々ノードとして、これらにより結ばれるリンクに対応する形で、各コストは定義されている。例えば、ＯＨＳに対するグループＧ１とグループＧ２との間を、キャリアが搬送される場合に、搬送元として「Ｇ１」、搬送先として「Ｇ２」が選択され、コストが「４０」となる。経路網上における移動時間に大差がないような隣接した又は近接した複数の作業装置は、同一グループに属するように、ここでのグループ分けは行われる。
【００７８】
再び図２において、製造指示部１によって、ストッカ２１ｂ（ＳＴＫ１）内部に収容されているキャリアを、製造装置２１（ＥＱ４４）に搬送する指示がなされると、第１経路探索部６は、ストッカＳＴＫ１から製造装置ＥＱ４４までの最適経路の探索を行う。この探索では、グループを結ぶ単位での最適経路の候補として４つの候補ＴＲである、第１候補（図４における搬送経路Ｎｏ．１）〜第４候補（図４における搬送経路Ｎｏ．４）についての、コスト比較が行われる。図３では、第４の最適経路の候補ＴＲ４を構成するグループのコストが示される。
【００７９】
第１候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−１を出発し、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第１候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ３からグループＧ１０のグループ間のグループ間経路（ＳＴＫ１：ＯＨＴｏｕｔ → ＥＱ４４）の２つのグループ間経路から構成されている。
【００８０】
第２候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１を介して、ストッカＳＴＫ２の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ２の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第２候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ２：ＯＨＳｉｎ）、グループＧ５に対応するグループ間経路（ＳＴＫ２：ＯＨＳｉｎ → ＳＴＫ２：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ５からグループＧ１０のグループ間のグループ間経路（ＳＴＫ２：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８１】
第３候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１及びＧ２を介して、ストッカＳＴＫ３の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ３の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ７を経て、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第３候補は、グループＧ３に対応するグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１及びＧ２に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ３：ＯＨＳｉｎ）、グループＧ７に対応するグループ間経路（ＳＴＫ３：ＯＨＳｉｎ → ＳＴＫ３：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ７からＧ１０のグループ間のグループ間経路（ＳＴＫ３：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８２】
第４候補は、先ず、ストッカＳＴＫ１の搬入出口ＳＴＫ−２を出発し、ＯＨＳにおけるグループＧ１及びＧ２を介して、ストッカＳＴＫ４の搬入出口ＳＴＫ−２に達した後、その内部を経て、ストッカＳＴＫ４の搬入出口ＳＴＫ−１から、ＯＨＴを介して、グループＧ１０の製造装置ＥＱ４４に到達する経路を示す。この第４候補は、グループＧ３のグループ間経路（ＳＴＫ１：ＳＨＥＬＦ → ＳＴＫ１：ＯＨＳｏｕｔ）、ＯＨＳにおけるグループＧ１及びＧ２に対応するグループ間経路（ＳＴＫ１：ＯＨＳｏｕｔ → ＳＴＫ４：ＯＨＳｉｎ）、グループＧ９に対応するグループ間経路（ＳＴＫ４：ＯＨＳｉｎ → ＳＴＫ４：ＯＨＴｏｕｔ）、及びＯＨＴにおけるグループＧ９からＧ１０のグループ間のグループ間経路（ＳＴＫ４：ＯＨＴｏｕｔ → ＥＱ４４）の４つのグループ間経路から構成されている。
【００８３】
こうして、４つの候補についてのグループを結ぶ単位での合計コストは、メモリ９から読み取られたグループ別のコストが積算されることで算出される。第１候補から第４候補の合計コストは夫々、図４に「合計コスト」として示したように、「１２５」、「２０５」、「１８５」、「９５」となる。これにより、合計コストが、最小値「９５」となる第４候補が、最適経路ＴＲ４として選択される。
【００８４】
このようにグループを結ぶ単位での最適経路ＴＲ４が特定されると、これを構成するグループの各々の内部に存在するグループ内経路とが結び合わされて、一本の道筋になることで、最終的に、最適経路が特定される。
【００８５】
次に、本実施形態に係る経路探索システムの動作処理である経路特定処理について、図５を参照して説明する。
（経路特定処理）
図５は、本実施形態に係る経路探索システムの経路特定処理を示すフローチャートである。
【００８６】
具体的には、図５において、先ず、第１経路探索部６によって、グループを結ぶ単位で、最適経路の複数の候補が探索される（ステップＳ１１）。続いて、探索された複数の候補を構成する、部分経路のいずれかについて、経路設定部３によって使用可能又は使用不可能とする経路変更、或いは走行検出部５によってビークル２の故障等の走行異常があったか否かが判定される（ステップＳ１２）。
【００８７】
ここで、経路変更及び走行異常のいずれかがあったと判定された場合には（ステップＳ１２：ＹＥＳ）、経路変更の対象となる部分経路、及び走行異常とされるビークル２が存在するために通過できないと想定される部分経路が、使用不可能に設定される（ステップＳ１３）。具体的には、この実質的に使用不可能な部分経路を含む候補については、次に行われる候補毎のコスト算出の対象から除外される。或いは、この使用不可能な部分経路に対する移動コストについては、非常に高い値に設定される。これにより、次に行われる候補毎のコスト算出における合計コストが大きくなるが故に、早期に候補から除外される。
【００８８】
他方で、経路変更及び走行異常のいずれもないと判定された場合には（ステップＳ１２：ＮＯ）、ステップS１３における部分経路を使用不可能とする設定が行われることなく、次の処理へ進む。
【００８９】
続いて、コスト算出部５によって、グループ単位でのコストが算出され、メモリ９に格納されているコストデータが更新される（ステップＳ１４）。続いて、第１経路探索部６によって、更新後における合計コストが最小となる候補が、選択される。即ち、グループ単位での最適経路が、この段階で完了する。
【００９０】
続いて、この特定されたグループ単位での最適経路を構成するグループの各々の内部のグループ内経路情報がメモリ９から読み出され、読み出されたグループ内経路情報に基づくグループ内経路が特定される。更に、これらの特定されたグループ内経路とグループを結ぶ単位での最適経路とが統合されることで、最終的に最適経路が特定される（ステップＳ１５）。
【００９１】
その後、搬送コントローラ８によって、特定された最適経路に沿って、ビークル２が制御され、ビークル２に搬送されるキャリアが目標地点に到達される（ステップＳ１６）。これにより、一連の経路特定処理が終了される。
【００９２】
尚、ステップＳ１６で実際にビークル２が目標地点に到達すると直ちに、走行した最適経路を構成するリンクを搬送するのにかかった時間から、これら各リンクについての移動コストが、算出される。更に、この算出された移動コストで、メモリ９内の格納内容が更新されて、その後における最適経路探索に利用される。
【００９３】
このように、実施形態の経路特定システムによれば、グループを結ぶ単位でコストが算出されるので、コストを用いての経路探索に必要とされるデータ数が極端に少なくなる。これにより、取り扱うデータ数及び演算負荷を低減しつつ、最適経路或いは実践的な意味での最適経路を探索できる。
【００９４】
また、搬送経路の変更や、ビークル２の走行異常に対応して、再度、リンク毎にコストを算出するので、常に最新のコストに基づいて最適経路が選択される。このため、搬送車の故障や、搬送経路の混雑を要因とする搬送時間のロスを無くすことができ、パフォーマンスを更に向上させることができる。
【００９５】
本発明は、上述した実施形態に限られるものではなく、請求の範囲及び明細書全体から読み取れる発明の要旨或いは思想に反しない範囲で適宜変更可能であり、そのような変更を伴う経路探索システム及び方法、搬送システム、並びにコンピュータプログラムもまた本発明の技術的範囲に含まれるものである。
【図面の簡単な説明】
【００９６】
【図１】実施形態に係る経路探索システムの構成を示すブロック図である。
【図２】実施形態に係る経路探索システムの搬送路を示す平面図である。
【図３】実施形態に係る経路探索システムのグループ別のコストを示すコスト表である。
【図４】実施形態に係る経路探索システムの最適経路の合計コストを示す合計コスト対比表である。
【図５】実施形態に係る経路探索システムの経路特定処理を示すフローチャートである。
【符号の説明】
【００９７】
１…搬送路、２…ビークル、３…経路設定部、４…走行検出部、５…コスト算出部、６…第１経路特定部、７…経路特定部、７ａ…第２経路探索部、８…搬送コントローラ、１１…移動装置、２１…製造装置、２１ｂ…ストッカ、１００…経路探索システム、２００…製造システム
【特許請求の範囲】
【請求項１】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムであって、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
を備えることを特徴とする経路探索システム。
【請求項２】
前記経路特定手段は、前記複数の作業装置間を夫々結ぶ前記経路の部分を夫々リンクとすると共に前記複数の作業装置を夫々ノードとする前記搬送車の移動コストに基づいて、前記経路の部分を探索し、前記探索された少なくとも一部と前記探索された経路の部分とを統合することで、前記最適経路を特定することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記格納手段は、前記ノード及び前記リンクに対応付けて、前記集合の内部における前記経路の部分を示す集合内経路情報を更に格納しており、
前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、前記最適経路を特定することを特徴とする請求項１に記載の経路探索システム。
【請求項４】
前記搬送車が移動する際の移動状況を検出する状態検出手段を更に備え、
前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する
ことを特徴とする請求項１から３のいずれか一項に記載の経路探索システム。
【請求項５】
前記経路の一部を、前記経路探索手段により前記最適経路を探索する上で、使用不可能に設定する設定手段を更に備え、
前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索することを特徴とする請求項１から４のいずれか一項に記載の経路探索システム。
【請求項６】
前記経路の一部を使用可能に設定する又は前記経路に対して使用可能な一部を追加する設定手段を更に備え、
前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索することを特徴とする請求項１から４のいずれか一項に記載の経路探索システム。
【請求項７】
前記移動コストを前記リンク毎に算出するコスト算出手段を更に備え、
前記格納手段は、前記算出された移動コストを格納することを特徴とする請求項１から６のいずれか一項に記載の経路探索システム。
【請求項８】
前記コスト算出手段は、前記搬送車が実際の搬送作業に要した実績時間データから前記搬送車が実際に搬送した前記経路について前記移動コストを算出し、
前記格納手段は、前記算出された移動コストで格納内容を更新する
ことを特徴とする請求項７に記載の経路探索システム。
【請求項９】
請求項１から８のいずれか一項に記載の経路探索システムと、
前記経路と、
前記搬送車と、
前記搬送車を前記経路上で移動させる移動手段と
を備えることを特徴とする搬送システム。
【請求項１０】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索方法であって、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程と
を備えることを特徴とする経路探索方法。
【請求項１１】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムに備えられるコンピュータを、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
として機能させることを特徴とするコンピュータプログラム。
【請求項１】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムであって、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
を備えることを特徴とする経路探索システム。
【請求項２】
前記経路特定手段は、前記複数の作業装置間を夫々結ぶ前記経路の部分を夫々リンクとすると共に前記複数の作業装置を夫々ノードとする前記搬送車の移動コストに基づいて、前記経路の部分を探索し、前記探索された少なくとも一部と前記探索された経路の部分とを統合することで、前記最適経路を特定することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記格納手段は、前記ノード及び前記リンクに対応付けて、前記集合の内部における前記経路の部分を示す集合内経路情報を更に格納しており、
前記経路特定手段は、前記格納された集合内経路情報を参照することで、前記探索された少なくとも一部に接続される経路の部分を決定し、前記探索された少なくとも一部と前記決定された経路の部分とを統合することで、前記最適経路を特定することを特徴とする請求項１に記載の経路探索システム。
【請求項４】
前記搬送車が移動する際の移動状況を検出する状態検出手段を更に備え、
前記経路探索手段は、前記検出された移動状況に対応して、前記経路を再探索する
ことを特徴とする請求項１から３のいずれか一項に記載の経路探索システム。
【請求項５】
前記経路の一部を、前記経路探索手段により前記最適経路を探索する上で、使用不可能に設定する設定手段を更に備え、
前記経路探索手段は、前記使用不可能に設定された一部を除外して、前記経路を探索することを特徴とする請求項１から４のいずれか一項に記載の経路探索システム。
【請求項６】
前記経路の一部を使用可能に設定する又は前記経路に対して使用可能な一部を追加する設定手段を更に備え、
前記経路探索手段は、前記使用可能に設定された又は追加された一部を入れて、前記経路を探索することを特徴とする請求項１から４のいずれか一項に記載の経路探索システム。
【請求項７】
前記移動コストを前記リンク毎に算出するコスト算出手段を更に備え、
前記格納手段は、前記算出された移動コストを格納することを特徴とする請求項１から６のいずれか一項に記載の経路探索システム。
【請求項８】
前記コスト算出手段は、前記搬送車が実際の搬送作業に要した実績時間データから前記搬送車が実際に搬送した前記経路について前記移動コストを算出し、
前記格納手段は、前記算出された移動コストで格納内容を更新する
ことを特徴とする請求項７に記載の経路探索システム。
【請求項９】
請求項１から８のいずれか一項に記載の経路探索システムと、
前記経路と、
前記搬送車と、
前記搬送車を前記経路上で移動させる移動手段と
を備えることを特徴とする搬送システム。
【請求項１０】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索方法であって、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段に格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する探索工程と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定工程と
を備えることを特徴とする経路探索方法。
【請求項１１】
被搬送物を搬送するための搬送車を該搬送車の経路上で出発地点から目標地点まで移動させる際の最適経路を探索する経路探索システムに備えられるコンピュータを、
前記被搬送物に対して各種処理を施すと共に前記経路に沿って並ぶ複数の作業装置を含んで構成される集合を少なくとも一つ含む複数の集合の各々をノードとし且つ該複数の集合の相互間をリンクとして規定される、前記搬送車の移動コストを格納する格納手段と、
前記格納された移動コストに基づいて、前記最適経路の少なくとも一部を、前記複数の集合を結ぶ単位で探索する経路探索手段と、
前記探索された少なくとも一部と、前記複数の集合のうち前記探索された少なくとも一部に含まれる一又は複数の集合の内部に存在する前記経路の部分とを統合することで、前記最適経路を特定する経路特定手段と
として機能させることを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２０７７３（Ｐ２００９−２０７７３Ａ）
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願番号】特願２００７−１８３９０３（Ｐ２００７−１８３９０３）
【出願日】平成１９年７月１３日（２００７．７．１３）
【出願人】（３０２０５９２７４）アシスト テクノロジーズ ジャパン株式会社 (146)
【Ｆターム（参考）】
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願日】平成１９年７月１３日（２００７．７．１３）
【出願人】（３０２０５９２７４）アシスト テクノロジーズ ジャパン株式会社 (146)
【Ｆターム（参考）】
[ Back to top ]