(57)【特許請求の範囲】
【請求項１】
対象装置の複数の加工位置の各々を複数の加工ヘッドのいずれかにより加工する際の該加工ヘッドの経路決定方法において、
前記対象装置の機種に応じて、前記加工位置と、前記加工ヘッドの各々の加工スタート位置とを備え、該加工位置の隣接する２つの間の前記加工ヘッドの移動時間を複数の位置決めパターンのいずれかで表わした加工マップデータをデータファイルからロードするステップと、
配列作成回数を初期化し、制限時間を初期値に設定するステップと、
前記複数の加工ヘッドの予め定めた優先順位の順番に、各々の加工ヘッドの加工スタート位置から開始して、前記制限時間内で前記加工位置の位置決めパターンの組み合わせを決定して経路配列を作成するステップと、
すべての加工位置がいずれかの経路配列に格納されたか否かを判定するステップと、
前記判定するステップで前記経路配列により前記加工位置のすべてが網羅されていると判定された場合に、前記配列作成回数を更新するとともに、前記制限時間から所定値を差し引いて、前記経路配列を作成するステップを繰り返すステップとを備え、
前記判定するステップで前記経路配列により前記加工位置のすべてが網羅されていないと判定された場合で、且つ前記配列作成回数が初期値でない場合に、直前で作成された経路配列を前記複数の加工ヘッドの経路として決定することを特徴とする加工ヘッドの経路決定方法。
【請求項２】
対象装置の複数の加工位置の各々を複数の加工ヘッドのいずれかにより加工する際の該加工ヘッドの経路決定装置において、
前記対象装置の機種に応じて、前記加工位置と、前記加工ヘッドの各々の加工スタート位置とを備え、該加工位置の隣接する２つの間の前記加工ヘッドの移動時間を複数の位置決めパターンのいずれかで表わした加工マップデータを格納するデータ登録部と、
前記複数の加工ヘッドの予め定めた優先順位の順番に、各々の加工ヘッドの加工スタート位置から開始して、前記制限時間内で前記加工マップデータにより規定されている位置決めパターンの組み合わせを決定して経路配列を作成する経路配列作成手段と、
前記経路配列により前記加工位置のすべてが網羅されているかを判別する判別手段と、
前記配列作成回数を計数する回数計数手段と、
前記回数計数手段による計数値が初期値かどうかを判定する計数値判定手段と、
前記制限時間から所定値を差し引くことにより前記制限時間を更新する制限時間更新手段とを備え、
前記経路配列により前記加工位置のすべてが網羅されている場合に、前記加算手段により前記配列作成回数を更新するとともに、前記更新手段により前記制限時間を更新してから前記経路配列作成により経路配列を作成し、
前記経路配列により前記加工位置のすべてが網羅されていない場合で、且つ前記回数計数手段による配列作成回数が初期値でない場合に、直前で作成された経路配列を前記複数の加工ヘッドの経路として決定することを特徴とする加工ヘッドの経路決定装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数の加工ヘッドの経路決定方法及び装置に関し、特に、多数の加工箇所を複数の加工ヘッドで加工する場合の移動時間を最短にする経路決定方法及び装置に関する。
【０００２】
【従来の技術】
例えば、ラジエータ等の自動車部品の製造において、それらの自動車部品には加工箇所が多数存在する。一例としてラジエータの場合は、アルミニューム製の多数のコアかしめ部を樹脂製の上下のプラスチックタンクにかしめにより結合する加工が必要である。この加工は、複数の加工ヘッドをロボット等を用いて加工箇所に移動させながら行う。このような場合、複数の加工ヘッドの移動時間を最短にすることが必要である。
【０００３】
複数の場所を１度だけ訪れて、その移動距離が最短となる経路を求める「巡回セールスマンの問題」の解法として、「ニューラルネットワーク」や「遺伝的アルゴリズム」を利用した方法が知られている。
また、人の試行錯誤により、加工ヘッドの経路を決定する場合もある。
【０００４】
【発明が解決しようとする課題】
しかし、従来の「ニューラルネットワーク」や「遺伝的アルゴリズム」を利用して複数の加工ヘッドの経路を決定する方法を開発する場合は、複数の加工ヘッドが同時に１つの加工箇所を加工することを避け、且つ、異なる時間であっても各々の加工ヘッドが同一の加工箇所を訪れないようにして、しかも移動時間が最短となる経路を求める、という条件が必要になる。このような条件を満たすためには、各加工ヘッドのための「ニューラルネットワーク」や「遺伝的アルゴリズム」のアルゴリズムが複雑になると予測される。したがって、そのためのプログラムの開発コストが高くなり、且つ開発期間が長くなるという問題がある。これは、最近の、低コストで短期間の設備開発に対する要求に反する。したがって、上記「ニューラルネットワーク」や「遺伝的アルゴリズム」を利用した方法を自動化設備に付加して複数の加工ヘッドの経路決定方法を実現することは現実的には困難である。
【０００５】
また、人の試行錯誤による加工ヘッドの経路決定方法によれば、人による作業負担が大きいという問題、及び経路決定に要する時間が長すぎるという問題の外に、決定された経路が人によって異なり、その結果、同一機種の対象装置であっても異なる加工経路を辿る事があり、加工経路を作成した人によって生産能力が左右されるという問題がある。
【０００６】
本発明の目的は、上記の従来技術における問題に鑑み、「ニューラルネットワーク」や「遺伝的アルゴリズム」などの複雑な理論を利用する必要性をなくして、開発コストが低く、開発期間を短くし、且つ、人手によらずに自動的に経路を決定することを可能にした、複数の加工ヘッドの経路決定方法及び装置を提供することにある。
【０００７】
【課題を解決するための手段】
上記の目的を達成するために、本発明により提供されるものは、複数の加工ヘッドの予め定めた優先順位の順番に、各々の加工ヘッドの加工スタート位置から開始して、制限時間内で加工位置のすべてを網羅する位置決めパターンの組み合わせを決定して経路配列を作成し、経路配列により加工位置のすべてが網羅されている場合に、配列作成回数を更新するとともに、制限時間から所定値を差し引いて、経路配列を作成するステップを繰り返し、経路配列により加工位置のすべてが網羅されていない場合で、且つ配列作成回数が初期値でない場合に、直前で作成された経路配列を複数の加工ヘッドの経路として決定することを特徴とする加工ヘッドの経路決定方法及び装置である。
【０００８】
加工スタート位置から開始して、制限時間内で加工マップデータにより規定されている位置決めパターンの組み合わせを決定し、制限時間を減少させながら上記位置決めパターンの組合せが所定の条件を満足する最短の移動合計時間を求めるようにしたので、「ニューラルネットワーク」や「遺伝的アルゴリズム」などの複雑な理論を利用する必要性がなくなり、開発コストが低く、開発期間を短くし、且つ、人手によらずに自動的に経路を決定することが可能になる。
【０００９】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。
図１は本発明による経路決定装置が用いられるシステムの一例を示すブロック図である。図において、１は本発明による経路決定装置、２は経路決定装置１を使用する設備（例えば加工ヘッド）を制御する設備制御装置、３は加工ヘッドを任意の位置に位置決め制御するサーボコントローラ、４は加工ヘッドである。以下の説明では経路決定装置１により経路が決定される設備として加工ヘッドを用いるが、本発明はこれに限定されるものではない。
【００１０】
経路決定装置１と設備制御装置２とはデータ通信バス５により接続されている。設備制御装置２からデータ通信バス５を介して経路決定装置１に加工する対象装置の機種及び／又は品番が通知され、それに応答して、後に詳述する各加工ヘッドの経路データが経路決定装置１からデータ通信経路５を介して設備制御装置２に通知される。
【００１１】
設備制御装置２と位置決めコントローラ３の各々とはデータ通信バス６により接続されている。
位置決めコントローラ３と加工ヘッド７の各々とはデータ通信バス７により接続されている。
図２は図１の装置における経路決定装置１の構成の概略を示すブロック図である。図において、経路決定装置１はキーボード、マウス等からなる入力部２１と、ＣＲＴ等からなる表示部２２と、制御部２３とからなっている。
【００１２】
制御部２３は、中央処理装置（ＣＰＵ）２３１と、メモリ２３２と、ハードディスク（ＨＤ）等からなるデータ登録部２３３と、ＲＳ２３２Ｃインテリジェントユニット等からなるインターフェースである通信制御部２３４と、インターフェースバス２３５とを備えている。
制御部２３は市販のパソコンに、本発明による複数の加工ヘッドの経路決定方法のプログラムをインストールすることにより実現可能である。
【００１３】
データ登録部２３３には、後に詳述する加工マップデータファイルと、時間層別データファイルと、演算定数データファイルとが格納される。
加工マップデータファイルは、対象装置の機種毎に「加工する位置（ポイント番号）」と、「各加工位置間の位置決めパターン」と、「各加工ヘッドの加工スタート位置（ポイント番号）」とを保存するファイルである。
【００１４】
時間層別データファイルは、「各加工位置間の位置決めパターン」に対する「位置決め時間」を保存するファイルである。
演算定数データファイルは、経路決定演算処理に必要な初期値、定数を保存するファイルである。
図３は図２に示した制御部２３内のＣＰＵ２３１を中心とした機能ブロック図である。同図において、データ登録部２３３は経路配列作成手段３１と、判別手段３２と、回数計数手段３３と、制限時間更新手段３４と、計数値判定手段３５とを備えている。
【００１５】
図４は図２及び図３に示した経路決定装置の動作を説明するフローチャートである。
図４により、本発明の実施の形態による対象装置の複数の加工位置の部分の各々を複数の加工ヘッドのいずれかにより加工する際の該加工ヘッドの経路決定方法を説明する。
【００１６】
まず、ステップＳ４１にて対象装置の機種に対応する加工マップデータをメモリ２３２にロードする。加工マップデータは前述のように、加工位置を示すポイント番号と、該加工位置の隣接する２つの間の前記加工ヘッドの移動時間を表す複数の位置決めパターンと、各加工ヘッドの移動開始ポイント番号とから構成されている。このステップＳ４１では、時間層別データファイルと演算データファイルもロードする。
【００１７】
図６は加工マップデータの例を示す図である。図６に示した例においては、加工位置を示すポイント番号は１、２、４、６、８、９、１０、１１、１２及び１３であり、位置決めパターンはＡとＢの２種類があって、パターンＡは加工ヘッドの移動時間がＴＡであり、パターンＢは加工ヘッドの移動時間がＴＢである。また、加工ヘッドは２個であり、第１の加工ヘッドの加工スタート位置はポイント番号１で、第２の加工ヘッドの加工スタート位置はポイント番号１３である。
【００１８】
加工マップデータに登録されているポイント番号の位置でのみ加工ヘッドによる対象装置の加工が行われ、加工マップデータに登録されていないポイント番号の位置では加工ヘッドによる加工は行われない。ＴＡ＜ＴＢである意味は、パターンＡの処理における加工ヘッドの移動に際しては例えば障害物が少ないので移動時間が短いのに対して、パターンＢの処理における加工ヘッドの移動に際しては障害物があるので移動時間が長くなっているということである。
【００１９】
再び図４に戻り、ステップＳ４２にて配列作成回数を０に初期化し、制限時間を初期値ｔ１に設定する。
次いでステップＳ４３にて、経路パターンテーブルをｔ１、ＴＡ、ＴＢと、各加工ヘッドの加工スタート位置と、制限時間とに基づいて、ＴＡとＴＢの回数の組合せによる移動時間が制限時間の範囲内になるときの、上記組合せとそれに対応する位置決め時間とからなる経路パターンテーブルを作成する。この経路パターンテーブルの作成方法の詳細は後に図７により説明する。
【００２０】
次いでステップＳ４４にて、優先順位が１位の加工ヘッドから順に経路配列を作成する。これはステップＳ４３にて作成した経路パターンテーブル内で加工ヘッドの移動時間が最短となる経路パターンの組合せを見出すことによりなされる。次にステップＳ４５にて、優先順位が２位の加工ヘッドの経路配列も上記と同様にして見出される。ステップＳ４６では優先順位が最下位の加工ヘッドの経路配列が見出される。このステップＳ４４〜Ｓ４６の詳細も後に図７により説明する。加工ヘッドの優先順位は予め定めてある。優先順位は任意でよいが、例えば加工のしやすさの順位であってもよい。
【００２１】
次いでステップＳ４７で、すべての加工ポイントがいずれかの経路配列に格納されたかを判定する。即ち、加工すべき位置のポイント番号のすべてが、いずれかの経路配列内のポイント番号に含まれるかを判定する。
この判定の結果、ＹＥＳであればステップＳ４８に進み、配列作成回数をインクリメントし、ステップＳ４９にて制限時間ｔ１から所定値を差し引くことにより制限時間を更新し、ステップＳ４３以降を繰り返す。
【００２２】
こうして、２回目以降の配列作成においても、短縮された制限時間内で加工ヘッドの移動時間が最短となる経路パターンの組合せが上記と同様にして見出される。
ステップＳ４３〜Ｓ４６を繰り返すと、いずれはステップＳ４７にて、加工すべき位置のポイント番号の少なくとも１つが経路配列内のポイント番号のいずれにも含まれない状態になる。
【００２３】
そのときはステップＳ５０に進み、配列作成回数が０ではないかを判定する。配列作成回数が０ではなければ、ステップＳ５１にて正常に終了し、前回のサイクルで見出された経路配列を、加工ヘッドのそれぞれが移動する際の経路配列として採用する。
ステップＳ５０の判定で配列作成回数が０と判定されると、ステップＳ５２にて異常終了となる。この場合は、制限時間の初期値が不適切であったと考えられるので、その初期値を変更して、再びステップＳ４１からの処理を行う。
【００２４】
以上の動作により、複数の加工ヘッドのそれぞれの移動時間の合計の中での最長時間を最短にするような、加工ヘッドの経路配列が決定される。
図５は図４におけるステップＳ４４〜Ｓ４６の動作の詳細を説明するフローチャートである。図において、ステップＳ５３で位置決めパターンカウンタのカウント値を０に初期化する。位置決めパターンカウンタはパターンの種類毎にパターンの回数をカウントするものであり、加工マップ上で例えばパターンＴＡとパターンＴＢの２つの移動パターンが存在する場合は、パターンＴＡの回数であるカウントＡとパターンＴＢの回数であるカウントＢとがある。これらの位置決めカウンタは図３の経路配列作成手段３１内に設けられている。以下では説明の簡単化のためにポイント番号間を加工ヘッドが移動する移動パターンはパターンＴＡとパターンＴＢの２種類とする。
【００２５】
次にステップＳ５４にて最短時間で行ける次のポイント番号を変数Ｐに代入するとともに、当該ポイント番号に移動する移動パターンはＴＡかＴＢかを記憶する。例えば図６の加工マップにおいて加工ヘッドスタート位置であるポイント番号１の位置においては次のポイント番号２を変数Ｐに代入し、パターンＴＡを記憶する。
【００２６】
ステップＳ５５では記憶された移動パターンに応じて、カウントＡ又はカウントＢに１を加算する。即ち、パターンＴＡで移動する場合はカウントＡに１を加算し、パターンＴＢで移動する場合はカウントＢに１を加算する。
次いでステップＳ５６にてカウントＡがパターンＴＡによる最大位置決め回数Ａｍａｘより小さいか、及びカウントＢがパターンＴＢによる最大位置決め回数Ｂｍａｘより小さいか、を判定する。この判定は図７により後に詳述する経路パターンテーブルにおける組合せの範囲内にあるかという判定である。ＹＥＳであればステップＳ５７にて経路配列にステップＳ５４にて代入したポイント番号Ｐの値を格納してステップＳ５３に戻る。ＮＯであれば、ステップＳ５８にてＡｍａｘ又はＢｍａｘの更新が可能かを判定する。Ａｍａｘ又はＢｍａｘが更新可能であるとは、制限時間内でカウントＡの最大値又はカウントＢの最大値を増大させることが可能である、ということである。ＹｅｓであればステップＳ５９にてＡｍａｘ及び／又はＢｍａｘを更新する。この更新の方法は次の通りである。
【００２７】
ＴＡ＞ＴＢの場合
Ａｍａｘに１を加算して新たなＡｍａｘとする。
ｔ１−ＴＡＸＡｍａｘの時間内のパターンＴＢによる最大位置決め回数を新たなＢｍａｘとする。
ＴＡ＜ＴＢの場合
Ｂｍａｘに１を加算して新たなＢｍａｘとする。
【００２８】
ｔ１−ＴＢＸＢｍａｘの時間内のパターンＴＡによる最大位置決め回数を新たなＡｍａｘとする。
ステップＳ５８の判定でＮＯであれば制限時間内での最大位置決め回数の更新はもはやできないので、加工ヘッドの経路配列の作成処理は終了し、この処理の直前で経路配列に格納されているポイント番号列を加工ヘッドの経路配列とする。
【００２９】
経路パターンテーブルの作成動作を図６及び図７〜図９に示した例により具体的に説明する。
図７に示した処理１においては、パターンＴＡによるポイント番号間の移動時間ＴＡは４秒であり、パターンＴＢによるポイント番号間の移動時間ＴＢは７秒であり、制限時間の初期値ｔ１は２５秒としてある。これらの値に基づいて経路パターンを図示のように作成する。即ち、制限時間２５秒以下でのパターンＴＡとＴＢの可能な組合せを列挙すると、まずＴＡ＜ＴＢなのでパターンＴＢによる最大位置決め回数を０から順にインクリメントする。パターンＴＢの回数の最大値Ｂｍａｘは３なので（７×３＝２１≦２５，７×４＝２８＞２５）、パターンＴＢによる最大位置決め回数Ｂｍａｘは０回の場合から３回まであり得る。
【００３０】
パターンＴＢによる最大位置決め回数Ｂｍａｘが０回の場合のパターンＴＡによる最大位置決め回数の最大値Ａｍａｘは６である（７×０＋４×６＝２４≦２５，７×０＋４×７＝２８＞２５）。したがって、最初の組合せはパターンＴＢが０回でパターンＴＡが６回であり、その時の合計の最大位置決め時間は２４秒である。
【００３１】
パターンＴＢが１回の場合のパターンＴＡの回数の最大値Ａｍａｘは４である（７×１＋４×４＝２３≦２５，７×１＋４×５＝２７＞２５）。したがって、次の組合せはＴＢが１回でＴＡが４回であり、その時の合計の最大位置決め時間は２３秒である。
ＴＢが２回の場合のＴＡの回数の最大値は２である（７×２＋４×２＝２２≦２５，７×２＋４×３＝２６＞２５）。したがって、３番目の組合せはＴＢが２回でＴＡが２回であり、その時の合計の最大位置決め時間は２２秒である。
【００３２】
ＴＢが３回の場合のＴＡの回数の最大値は１である（７×３＋４×１≦２５，７×３＋４×２＝２９＞２５）。したがって、４番目の組合せはＴＢが３回でＴＡが１回であり、その時の合計の最大位置決め時間は２５秒である。
上記の例ではパターンＴＢを０からインクリメントして、対応するパターンＴＡの回数の最大値を求めたが、パターンＴＡを０からインクリメントして、対応するパターンＴＢの回数の最大値を求めてもよい。この場合は組合せの数が上述の場合より多くなるので処理時間が長くなるという欠点がある。
【００３３】
再び図４に戻り、上記のようにして経路パターンテーブルを作成し終わると、ステップＳ４４〜Ｓ４６にて複数の加工ヘッドの優先順位の順番に、各々の加工ヘッドの加工スタート位置から開始して、制限時間内で加工マップデータにより規定されている位置決めパターンの組み合わせ中の各パターンの最大位置決め回数に対応するポイント番号を決定して経路配列を作成する。この経路配列の作成処理は図５のフローチャートにしたがって行われる。
【００３４】
図７の例では、第１の加工ヘッドの優先順位が最も高いので、その加工ヘッドの経路配列を最初に作成する。図５のステップＳ５３でカウントＡ及びＢを０に初期化する。制限時間２５秒内でのカウントＢの最大値Ｂｍａｘが０の場合、カウントＡの最大値Ａｍａｘは６である。カウントＢの最大値Ｂｍａｘが３の場合、カウントＡの最大値Ａｍａｘは１である。次にステップＳ５４にて最短時間で行けるポイント番号を変数Ｐに代入する。これは第１の加工ヘッドの優先順位が高い場合は、第１の加工ヘッドによる次の加工位置のポイント番号２を変数Ｐに格納することに相当する。次にステップＳ５５にて制限時間である２５秒以内での第１の加工ヘッドによるパターンＴＡの位置決め回数のカウントＡとパターンＴＢの位置決め回数のカウントＢを次の通りインクリメントする。
【００３５】
（１）ＴＡを１回とＴＢを０回でポイント番号２へ移動する場合（Ａ＝１，Ｂ＝０、加工ヘッドの移動時間は４×１＋７×０＝４≦２５）。
（２）ＴＡを１回とＴＢを１回でポイント番号２及び４へ移動する場合（Ａ＝１，Ｂ＝１、加工ヘッドの移動時間は４×１＋７×１＝１１≦２５）。
（３）ＴＡを１回とＴＢを２回でポイント番号２、４、６へ移動する場合（Ａ＝１，Ｂ＝２、加工ヘッドの移動時間は４×１＋７×２＝１８≦２５）。
【００３６】
（４）ＴＡを１回とＴＢを３回でポイント番号２、４、６、８へ移動する場合（Ａ＝１，Ｂ＝３、加工ヘッドの移動時間は４×１＋７×３＝２５≦２５）。
これ以外の組合せは、制限時間を越えるので採用できない。これにより、第１の加工ヘッドは、上記（４）で決定される。
したがって、ポイント番号９、１０、１１、１２は第２の加工ヘッドにより行う必要があるがその場合の第２の加工ヘッドの移動時間はＴＡが４回でＴＢが０回であり、移動時間の合計は４×４＋７×０＝１６≦２５なので、制限時間の範囲内でありやはり採用可能である。
【００３７】
この場合の加工ヘッドの移動時間は第１の加工ヘッドと第２の加工ヘッドの移動時間のうち長い方で決まる。即ち、図７の処理１においては移動時間は２５秒である。すべての加工ポイントが経路配列に格納されたので、図４のステップＳ４８で配列作成回数に１を加算し、制限時間ｔ１＝２５から所定値４を差し引いた値２１を新たな制限時間とする。そして、再びステップＳ４３以降を繰り返す。
【００３８】
図８に示した処理２は２回目の配列作成処理を示す。制限時間２１秒内での経路パターンテーブルにおける処理１と同様にパターンＴＢによる最大位置決め回数は０回の場合から３回まであり得る。
パターンＴＢによる最大位置決め回数が０回の場合のパターンＴＡによる最大位置決め回数の最大値は５である（７×０＋４×５＝２０≦２１，７×０＋４×６＝２４＞２１）。したがって、最初の組合せはパターンＴＢが０回でパターンＴＡが５回であり、その時の合計の最大位置決め時間は２０秒である。
【００３９】
パターンＴＢが１回の場合のパターンＴＡの回数の最大値は３である（７×１＋４×３＝１９≦２５，７×１＋４×４＝２３＞２１）。したがって、次の組合せはＴＢが１回でＴＡが３回であり、その時の合計の最大位置決め時間は１９秒である。
ＴＢが２回の場合のＴＡの回数の最大値は１である（７×２＋４×１＝１８≦２１，７×２＋４×２＝２２＞２１）。したがって、３番目の組合せはＴＢが２回でＴＡが１回であり、その時の合計の最大位置決め時間は１８秒である。
【００４０】
ＴＢが３回の場合のＴＡの回数の最大値は０である（７×３＋４×０≦２１，７×３＋４×１＝２５＞２１）。したがって、４番目の組合せはＴＢが３回でＴＡが０回であり、その時の合計の最大位置決め時間は２１秒である。
上記のようにして２回目の経路パターンテーブルを作成し終わると、再び図４のステップＳ４４〜Ｓ４６にて第１及び第２の加工ヘッドの経路配列が処理１と同様の手法で図５のフローチャート及び図６の加工マップにしたがって作成される。
【００４１】
更新後の制限時間である２１秒以内での第１の加工ヘッドによるパターンＴＡの位置決め回数のカウントＡとパターンＴＢの位置決め回数のカウントＢとの組合せの可能性は次の通りである。
（１）ＴＡを１回とＴＢを０回でポイント番号２に移動する場合（Ａ＝１，Ｂ＝０、加工ヘッドの移動時間は４×１＋７×０＝４≦２５）。
【００４２】
（２）ＴＡを１回とＴＢを１回でポイント番号２及び４へ移動する場合（Ａ＝１，Ｂ＝１、加工ヘッドの移動時間は４×１＋７×１＝１１≦２５）。
（３）ＴＡを１回とＴＢを２回でポイント番号２、４、６へ移動する場合（Ａ＝１，Ｂ＝２、加工ヘッドの移動時間は４×１＋７×２＝１８≦２５）。
これ以外の組合せは、制限時間を越えるので採用できない。これにより、図６の加工マップデータを考慮すると、第１の加工ヘッドの経路配列は、上記（３）で決定される。
【００４３】
したがって、ポイント番号８、９、１０、１１、１２は第２の加工ヘッドにより行う必要がある。その場合の第２の加工ヘッドの移動時間はＴＡが５回でＴＢが０回であり、移動時間の合計は４×５＋７×０＝２０≦２１なので、制限時間の範囲内であり採用可能である。
加工ヘッドの移動時間は第１の加工ヘッドと第２の加工ヘッドの移動時間のうち長い方できまる。即ち、図８の処理２においては移動時間は２０秒である。すべての加工ポイントが経路配列に格納されたので、図４のステップＳ４８で配列作成回数に１を加算し、制限時間ｔ１＝２１から所定値４を差し引いた値１７を新たな制限時間とする。そして、再びステップＳ４３以降を繰り返す。
【００４４】
図９に示した処理３は３回目の配列作成処理を示す。制限時間１７秒内での経路パターンテーブルにおいては、パターンＴＢによる最大位置決め回数は０回の場合から２回まであり得る。
パターンＴＢによる最大位置決め回数が０回の場合のパターンＴＡによる最大位置決め回数の最大値は４である（７×０＋４×４＝１６≦１７，７×０＋４×５＝２０＞１７）。したがって、最初の組合せはパターンＴＢが０回でパターンＴＡが４回であり、その時の合計の最大位置決め時間は１７秒である。
【００４５】
パターンＴＢが１回の場合のパターンＴＡの回数の最大値は２である（７×１＋４×２＝１５≦１７，７×１＋４×３＝１８＞１７）。したがって、次の組合せはＴＢが１回でＴＡが２回であり、その時の合計の最大位置決め時間は１５秒である。
ＴＢが２回の場合のＴＡの回数の最大値は０である（７×２＋４×０＝１４≦１７，７×２＋４×１＝１８＞１７）。したがって、３番目の組合せはＴＢが２回でＴＡが０回であり、その時の合計の最大位置決め時間は１４秒である。
【００４６】
上記のようにして３回目の経路パターンテーブルを作成し終わると、再び図４のステップＳ４４〜Ｓ４６にて第１及び第２の加工ヘッドの経路配列が処理１と同様の手法で図５のフローチャート及び図６の加工マップにしたがって作成される。
更新後の制限時間である１７秒以内での第１の加工ヘッドによるパターンＴＡとパターンＴＢの組合せの可能性は次の通りである。
【００４７】
（１）ＴＡを１回とＴＢを０回でポイント番号２へ移動する場合（加工ヘッドの移動時間は４×１＋７×０＝４≦１７）。
（２）ＴＡを１回とＴＢを１回でポイント番号２及び４へ移動する場合（加工ヘッドの移動時間は４×１＋７×１＝１１≦１７）。
これ以外の組合せは、制限時間を越えるので採用できない。これにより、第１の加工ヘッドの経路配列は、上記（２）で決定される。
【００４８】
したがって、ポイント番号６、８、９、１０、１１、１２は第２の加工ヘッドにより行う必要がある。その場合の第２の加工ヘッドの移動時間はＴＡが５回でＴＢが１回であり、移動時間の合計は４×５＋７×１＝２７＞１７なので、制限時間を越えるため採用できない。
結局、更新後の制限時間内で採用可能なパターンの組合せは存在しない。
【００４９】
処理３における配列作成回数は０ではないので、図４のステップＳ５１にて正常終了となり、処理２で作成した経路配列（第１の加工ヘッドはポイント番号２をパターンＴＡで移動し、ポイント番号４及び６をパターンＴＢで移動し、第２の加工ヘッドはポイント番号１２、１１、１０、９、８をパターンＴＡで移動する。）が加工ヘッドの最短時間の移動経路となる。
【図面の簡単な説明】
【図１】本発明による経路決定装置が用いられるシステムの一例を示すブロック図である。
【図２】図１の装置における経路決定装置１の構成の概略を示すブロック図である。
【図３】図２に示した制御部２３内のＣＰＵ２３１を中心とした機能ブロック図である。
【図４】図２及び図３に示した経路決定装置の動作を説明するフローチャートである。
【図５】図４におけるステップＳ４４〜Ｓ４６の動作の詳細を説明するフローチャートである。
【図６】加工マップデータの例を示す図である。
【図７】経路パターンテーブルの作成動作の例１を具体的に説明する図である。
【図８】経路パターンテーブルの作成動作の例２を具体的に説明する図である。
【図９】経路パターンテーブルの作成動作の例３を具体的に説明する図である。
【符号の説明】
１…経路決定装置
２３…制御部
３１…経路配列作成手段
３２…判別手段
３３…回数計数手段
３４…制限時間更新手段
３５…計数値判定手段
【図１】
0003624746.tif 000002
【図２】
0003624746.tif 000003
【図３】
0003624746.tif 000004
【図４】
0003624746.tif 000005
【図５】
0003624746.tif 000006
【図６】
0003624746.tif 000007
【図７】
0003624746.tif 000008
【図８】
0003624746.tif 000009
【図９】
0003624746.tif 000010