(57)【要約】【課題】２点間の移動コストを、メモリを節約しつつ高速に計算する。【解決手段】経路計画装置における２点間の移動コストを複数のパラメータに基づいて計算する際に、複数のパラメータが、それぞれの所定範囲内にあるときは、該パラメータによる演算結果を索引とする複数の表を参照して移動コストを求め、前記所定範囲を外れるときは、移動コストを計算する。【選択図】　　　図７
2004139532.tif 000002
【特許請求の範囲】
【請求項１】
２点間の移動コストを複数のパラメータに基づいて計算するに際して、
前記複数のパラメータが、それぞれ所定範囲内にあるときは、該パラメータによる演算結果を索引とする複数の表を参照して移動コストを求め、
前記複数のパラメータの少なくともいずれか一つが、前記所定範囲を外れるときは、移動コストを計算することを特徴とする経路計画装置の移動コスト計算方法。
【請求項２】
前記表の索引に対応データが存在しない場合には、移動コストを計算して、表の索引の内容を更新することを特徴とする請求項１に記載の経路計画装置の移動コスト計算方法。
【請求項３】
前記パラメータを正規化して用いることを特徴とする請求項１又は２に記載の経路計画装置の移動コスト計算方法。
【請求項４】
前記パラメータを離散化した後、整数化して用いることを特徴とする請求項１乃至３のいずれかに記載の経路計画装置の移動コスト計算方法。
【請求項５】
前記表のサイズが、前記複数のパラメータの全組合わせ数より十分小さいことを特徴とする請求項１に記載の経路計画装置の移動コスト計算方法。
【請求項６】
前記表のサイズが、正規化されたパラメータの最大値のうちの最大値に対し、２の累乗でその値より大きい最小の数以上であることを特徴とする請求項５に記載の経路計画装置の移動コスト計算方法。
【請求項７】
前記演算として、パラメータをｐ、ｑとしたとき、２進記数法で表されたｐとｑの桁毎の排他的論理和演算、ｐとｑの加算、又は、ｐとｑの減算と非負化パラメータを加える演算の組合せ演算を用いることを特徴とする請求項１乃至６のいずれかに記載の経路計画装置の移動コスト計算方法。
【請求項８】
請求項１乃至７のいずれかに記載の移動コスト計算方法を用いて、加工点間の移動時間を計算することを特徴とする加工計画方法。
【請求項９】
請求項１乃至７のいずれかに記載の移動コスト計算方法又は請求項７に記載の加工計画方法を実施するためのコンピュータプログラム。
【請求項１０】
２点間の移動コストを複数のパラメータに基づいて計算するための経路計画装置の移動コスト計算装置であって、
前記複数のパラメータが、それぞれ所定範囲内にあることを判定する手段と、前記複数のパラメータが、共に、前記所定範囲内にあるときは、該パラメータによる演算結果を索引とする複数の表を参照して移動コストを求める手段と、
前記複数のパラメータの少なくともいずれか一つが、前記所定範囲を外れるときは移動コストを計算する手段と、
を備えたことを特徴とする経路計画装置の移動コスト計算装置。
【請求項１１】
前記表の索引に対応データが存在しない場合には、移動コストを計算して、表の索引の内容を更新するようにされていることを特徴とする請求項１０に記載の経路計画装置の移動コスト計算装置。
【請求項１２】
前記パラメータを正規化して用いるようにされていることを特徴とする請求項１０又は１１に記載の経路計画装置の移動コスト計算装置。
【請求項１３】
前記パラメータを離散化した後、整数化して用いるようにされていることを特徴とする請求項１０乃至１２のいずれかに記載の経路計画装置の移動コスト計算装置。
【請求項１４】
前記表のサイズが、前記複数のパラメータの全組合わせ数より十分小さいことを特徴とする請求項１０に記載の経路計画装置の移動コスト計算装置。
【請求項１５】
前記表のサイズが、正規化されたパラメータの最大値のうちの最大値に対し、２の累乗でその値より大きい最小の数以上であることを特徴とする請求項１４に記載の経路計画装置の移動コスト計算装置。
【請求項１６】
前記演算として、パラメータをｐ、ｑとしたとき、２進記数法で表されたｐとｑの桁毎の排他的論理和演算、ｐとｑの加算、又は、ｐとｑの減算と非負化パラメータを加える演算の組合せ演算を用いることを特徴とする請求項１０乃至１５のいずれかに記載の経路計画装置の移動コスト計算装置。
【請求項１７】
請求項１０乃至１６のいずれかに記載の移動コスト計算装置を用いて、加工点間の移動時間を計算するようにされていることを特徴とする加工計画装置。
【請求項１８】
請求項１０乃至１６のいずれかに記載の移動コスト計算装置又は請求項１７に記載の加工計画装置を実現するためのコンピュータプログラム。
【請求項１９】
請求項９又は１８に記載のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２点間の移動コストを複数のパラメータに基づいて計算する経路計画装置の移動コスト計算方法及び装置に係り、特に、レーザビームを照射してプリント配線基板等に複数の穴開け加工を行なうレーザ穴開け機に用いるのに好適な、２点間の移動コストを、メモリを節約しつつ高速に計算することが可能な経路計画装置の移動コスト計算方法、該移動コスト計算方法を用いた加工計画方法、同様な移動コスト計算装置、該移動コスト計算装置を含む加工計画装置、前記移動コスト計算方法や加工計画方法を実施したり、前記移動コスト計算装置や加工計画装置を実現するためのコンピュータプログラム、及び、該コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体に関する。
【０００２】
【従来の技術】
レーザビームを用いてプリント配線基板等に穴をあけるレーザ穴開け機の市場価値の一つとして、加工速度が上げられる。この加工速度を上げるための手法の１つに、例えば穿孔順序の効率化等といった、数学的最適化による方法が挙げられ、出願人は、既に、特願２００１−３３１５５０や特願２００２−２６１８９を提案している。
【０００３】
このような最適化問題には、例えば巡回セールスマン問題（Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ：以下単にＴＳＰと略す）、最短路問題等といった、最適な（多くの場合、最短な）経路を求める問題が存在する。例えばＴＳＰは、「全ての都市（ＴＳＰでは、点のことを都市と呼ぶ）を一度ずつ通り、元の位置に戻る巡回路の中で、最短の経路（コストの総和が最小となる経路）を求める問題」である。このＴＳＰを解く際には、２点間の移動を行なう際のコスト（以下では移動コストと呼ぶ。例えば２点間の移動距離、移動時間、移動費用などが該当する）が定義されている必要がある。移動コストは、平面上のユークリッド距離のように、各点の幾何的な位置などの複数のパラメータに基づいて、計算できることが多い。
【０００４】
このような移動コストの計算を行なう方法には、（１）計算の必要がある毎に毎回計算を実行する方法、及び（２）メモリに計算結果を全て蓄えておく方法が考えられる。
【０００５】
しかしながら、前者の（１）の方法では、例え１回の計算時間は小さくても、計算回数が増えれば、無視できない時間となってしまう。実際に、移動コストの計算は、ＴＳＰにおいて何度も必要となるものである。又、後者の（２）の方法では、都市数をｎとおくと、記憶しておかなければならない都市対の組合わせが、例え都市Ａ→Ｂへの移動と逆向きのＢ→Ａへの移動のコストが同一な対称的な問題の場合であっても、ｎ（ｎ−１）／２個存在する。これを全て記憶しておくのはメモリの浪費であり、又、そのための計算も、無駄である。例えばｎ＝１００００の場合、５×１０７個程度必要であり、１個を４バイトで記憶する場合でも２００Ｍバイト必要となる。
【０００６】
これらの問題に対処すべく、ベントリー（Ｊ．Ｌ．Ｂｅｎｔｌｅｙ）は、１９９０年の論文（“Ｋ−ｄ　Ｔｒｅｅｓ　ｆｏｒ　Ｓｅｍｉｄｙｎａｍｉｃ　Ｐｏｉｎｔ　Ｓｅｔｓ”，Ｐｒｏｃｅｅｄｉｎｇｓｏｆ　ｔｈｅ　Ｓｉｘｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｇｅｏｍｅｔｒｙ，ＡＣＭ，Ｎｅｗ　Ｙｏｒｋ，１８７−１９７，１９９０）のＡｐｐｅｎｄｉｘにおいて、対称ＴＳＰにおける、高速且つメモリを節約できるような移動コストの計算方法（関数及びデータ構造）について言及している。この方法は、彼が“Ｃａｃｈｉｎｇ”とタイトルを付けたとおり、キャッシュメモリの用い方に類似するものである。
【０００７】
ベントリーの提案に従った移動コスト計算方法の手順を図１に、同じく計算例を図２に示す。
【０００８】
以下、ベントリーの方法について簡単に説明する。
【０００９】
都市数をｎとし、各都市に、それぞれ番号を割り振る（以下、「ｉ番の都市」を、簡単に「都市ｉ」と称する）。ベントリーの方法は、都市ｉから都市ｊへの移動コストを、「必要があれば」計算する方法である。ここで、「必要があれば」としたのは、実際に計算する場合と、単にメモリに蓄えているデータを読むだけの場合があるからである。用意する配列は、図３に示す如く、２つあり、共にサイズがｍである。ここで、ｍは、２の累乗でｎ−１よりも大きい最小の数とする（例えばｎ＝５００とすると、ｍ＝２９＝５１２）。配列の１つ（図３の左側）ｃａｃｈｅｓｉｇ［］は整数（ｉｎｔ）型で、都市番号を記憶する。もう１つ（図３の右側）ｃａｃｈｅｖａｌ［］は、移動コストを、例えば浮動小数点（ｆｌｏａｔ）型で記憶する。配列のサイズが、このようなｍである理由は、配列内データへのアクセスに用いる（ハッシュ）インデックス（索引）ｉｎｄを計算するための（ハッシュ）関数として、排他的論理和（ＸＯＲ：以下では“＾”で表現する。ビット毎の計算で、０＾０＝１＾１＝０、０＾１＝１＾０＝１である）を用いているからである。０＾０＝０なので、ｎ未満の２つの数のＸＯＲの結果は、必ずｍ未満である。
【００１０】
まず図１のステップ１００で、移動コストが対称である場合、２つの番号が、小さい方がｉで大きい方がｊとなるようにする。ステップ１０２はインデックスの計算であり、ｉとｊのＸＯＲ演算を行ない、ｉｎｄに格納する（ｉｎｄが等しいｉとｊの組合わせは多数あることに注意する）。ステップ１０４は、ｃａｃｈｅｓｉｇ［ｉｎｄ］とｉとの比較である。即ち、もし前回のｉｎｄの計算が、同じｉとｊの組合わせであった場合には、ｃａｃｈｅｓｉｇ［ｉｎｄ］にｉが格納されており、その移動コストはｃａｃｈｅｖａｌ［ｉｎｄ］に既に格納されているので、単に取り出せばよい（ステップ１０８で関数の戻り値として返す）。そうでなければ、ｃａｃｈｅｓｉｇ［ｉｎｄ］には別の値が格納されているので、ステップ１０６で実際のコスト計算ｃｏｍｐｕｔｅｄｉｓｔ（）を実行し、結果をｃａｃｈｅｖａｌ［ｉｎｄ］に格納すると共に、ｃａｃｈｅｓｉｇ［ｉｎｄ］にｉを格納する。
【００１１】
ベントリーによると、ＴＳＰのある解法を用いた場合、移動コスト計算をしなくてもよい確率（ヒット率）は７５％であり、移動コスト計算時間の合計は、半分まで削減できる。又、使用するメモリは、配列２つで済む（例えばｎ＝５００に対しｍ＝５１２であるので、ｉｎｔ型、ｆｌｏａｔ型（各４バイト）の配列なら、約４Ｋバイトで済む。
【００１２】
【発明が解決しようとする課題】
しかしながら、この方法は、単に都市番号の対による計算であり、例えば既に挙げた特願２００２−２６１８９に関しては、そのままの方法では扱えない。何故ならば、２点間の移動コストを計算するためには、２点の幾何学的情報（Ｘ座標値の差等）だけではなく、ＸＹステージの移動速度が必要なためである。即ち、移動速度が別の値になれば、都市番号の対が同一でも別の値となる。従来は、この状況に対処できず、メモリを浪費するか、コスト計算が必要となる毎に実際に計算を行なうしか方法がなかった。
【００１３】
本発明は、前記従来の問題点を解消するべくなされたもので、２点間の移動コストを複数のパラメータに基づいて計算する場合であっても、メモリを節約しつつ高速に計算できるようにすることを課題とする。
【００１４】
【課題を解決するための手段】
本発明は、２点間の移動コストを複数のパラメータに基づいて計算するに際して、前記複数のパラメータが、それぞれ所定範囲内にあるときは、該パラメータによる演算結果を索引とする複数の表を参照して移動コストを求め、前記複数のパラメータの少なくともいずれか一つが、前記所定範囲を外れるときは、移動コストを計算するようにして、前記課題を解決したものである。
【００１５】
又、前記表の索引に対応データが存在しない場合には、移動コストを計算して、表の索引の内容を更新するようにしたものである。
【００１６】
又、前記パラメータを正規化して用いるようにしたものである。
【００１７】
又、前記パラメータを離散化した後、整数化（望ましくは０又は自然数化）して用いるようにしたものである。
【００１８】
又、前記表のサイズを、前記複数のパラメータの全組合わせ数より十分小さくしたものである。
【００１９】
又、前記表のサイズが、正規化されたパラメータの最大値のうちの最大値に対し、２の累乗でその値より大きい最小の数以上であるようにしたものである。
【００２０】
又、前記演算として、パラメータをｐ、ｑとしたとき、２進記数法で表されたｐとｑの桁毎の排他的論理和演算、ｐとｑの加算、又は、ｐとｑの減算と非負化パラメータを加える演算の組合せ演算を用いるようにしたものである。
【００２１】
本発明は、又、前記の移動コスト計算方法を用いて、加工点間の移動時間を計算する加工計画方法を提供するものである。
【００２２】
又、前記の移動コスト計算方法又は加工計画方法を実施するためのコンピュータプログラムを提供するものである。
【００２３】
本発明は、又、２点間の移動コストを複数のパラメータに基づいて計算するための経路計画装置の移動コスト計算装置であって、前記複数のパラメータが、それぞれ所定範囲内にあることを判定する手段と、前記複数のパラメータが、共に、前記所定範囲内にあるときは、該パラメータによる演算結果を索引とする複数の表を参照して移動コストを求める手段と、前記複数のパラメータの少なくともいずれか一つが、前記所定範囲を外れるときは移動コストを計算する手段とを備えることにより、前記課題を解決したものである。
【００２４】
又、前記の移動コスト計算装置を用いて、加工点間の移動時間を計算するようにされた加工計画装置を提供するものである。
【００２５】
又、前記の移動コスト計算装置又は加工計画装置を実現するためのコンピュータプログラムを提供するものである。
【００２６】
又、前記のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体を提供するものである。
【００２７】
【発明の実施の形態】
以下図面を参照して、ＸＹステージとガルバノスキャナを備えたレーザ穴開け機の加工計画に適用した本発明の実施形態を詳細に説明する。
【００２８】
オンライン形態の本実施形態は、図４に示す如く、レーザ穴開け機３０と、例えばハードディスクやフレキシブルディスク等の外部メモリに記憶された、前記レーザ穴開け機３０が加工を行なうための加工データファイル群４２、該加工データファイル群４２を変換する加工データ変換プログラム（Ｐｒｇ）４４、例えば内部メモリに記憶された加工データ４６、例えば外部メモリに記録された動作モデルファイル４８、該動作モデルファイル４８を読み込むための動作モデルファイル読込みプログラム（Ｐｒｇ）５０、例えば内部メモリに記憶された動作モデルデータ５２、本発明に係る加工計画プログラム（Ｐｒｇ）５４、前記レーザ穴開け機３０を制御する加工制御プログラム（Ｐｒｇ）５６を含む、前記レーザ穴開け機３０と通信可能なパソコン（ＰＣ）４０とを備えている。
【００２９】
なお、図４では、加工を制御する加工制御プログラム５６と、加工を計画する加工計画プログラム５４が、同じＰＣ４０内に収まっており、加工計画がオンラインで処理されるが、これらは別個でもよい。即ち、加工計画プログラム５４は、オフラインで実行可能である。
【００３０】
オフライン形態の実施形態は、図５に示す如く、オンライン形態の実施形態と同様の加工データファイル群４２、加工データ変換プログラム４４、加工データ４６、加工制御プログラム５６を含む、レーザ穴開け機３０と通信可能なオンラインＰＣ６０と、同じくオンライン形態の実施形態と同様の加工データファイル群４２、加工データ変換プログラム４４、加工データ４６、動作モデルファイル４８、動作モデルファイル読込みプログラム５０、動作モデル５２、加工計画プログラム５４を含むオフラインＰＣ６２とを備えている。
【００３１】
次に、オンライン形態のレーザ穴開け機の実施形態を例にとって、本発明の作用を説明する。
【００３２】
本実施形態において、ＰＣ４０と通信可能なレーザ穴開け機３０は、加工データ４６に従って、加工制御プログラム５６により制御され、加工を行なう。加工データ４６は、通常、ハードディスクやフレキシブルディスク等の外部メモリにある加工データファイル群４２を、加工データ変換プログラム４４で変換することにより得られる。加工データ４６は、レーザ穴開け機３０を効率良く動かすために、加工計画プログラム５４により更新される。この加工計画プログラム５４は、内部機器（ガルバノスキャナ及びＸＹステージ）の動作をモデル化した動作モデル５２を用いる。この動作モデル５２は、通常、内部メモリに常駐していないので、外部メモリにある動作モデルファイル４８を、動作モデルファイル読込みプログラム５０を用いて読み込むことにより得る。
【００３３】
前記レーザ穴開け機３０は、前記加工データファイル群４２の内容に従って動作する。加工開始命令の後、レーザ穴開け機３０の動作を制御するのは。前記加工制御プログラム５６である。即ち、当事者は、加工に際して加工データファイル群４２を用意し、加工制御プログラム５６に加工開始命令を与えて、レーザ穴開け機３０を動作させる。
【００３４】
本発明は、前記加工計画プログラム５４における、２点間の移動コストの計算方法及びメモリ利用方法に関する。
【００３５】
本発明の適用対象はレーザ穴開け機に限定されず、図６に示す如く、入力データ７２と移動コストデータ７４に基づいて経路計画を立てる計画プログラム（Ｐｒｇ）７６と、該計画プログラム７６によって設定された経路に従って実施対象８０を制御する制御プログラム（Ｐｒｇ）７８を含む、実施対象８０と通信可能なＰＣ７０（複数も可であり、１つのＰＣが７２、７４、７６、７８全てを含まなくてもよい）を有するもので、移動コスト計算の全部又は一部が、複数のパラメータから一意に計算できるもの一般に適用できる。例えば、カーナビゲーションシステムにおける最短路の探索、物流支援ソフトにおける配送路の計画、移動ロボットの軌道の計画等に適用できる。更には、出願人が提案した特願２００２−１０４６０又は特願２００２−２６１８９においては、実世界の移動ではなく架空のネットワークモデルを導入し、モデル上で最短路問題又は最長路問題として定式化し、問題を解いたが、そのような場合のネットワーク上のノード間の移動にも本発明は適用される。
【００３６】
なお、入力データ７２や移動コストデータ７４は、必ずしもファイル形式である必要はない。
【００３７】
複数のパラメータの例としては、まず、ｘｙ平面上の２点（ｘ１，ｙ１）、（ｘ２，ｙ２）の距離Ｌｋが次式
Ｌｋ（（ｘ１，ｙ１），（ｘ２，ｙ２））＝｛｜ｘ１−ｘ２｜ｋ＋｜ｙ１−ｙ２｜ｋ｝１／ｋ　　　　…（１）
で与えられる距離（ｋ＝２であるとユークリッド距離）における、ｘ方向の移動量｜ｘ１−ｘ２｜とｙ方向の移動量｜ｙ１−ｙ２｜が挙げられる。又、（１）式でｋ＝∞としたＬ∞距離に類似するが、特願２００１−３３１５５０に記載した、ガルバノスキャナの動作時間（ｌの移動にかかる時間がｃｏｓｔｘ（ｌ）、ｃｏｓｔｙ（ｌ））をモデル化したデータ（動作モデル）を直接反映した移動コスト
Ｌ＝ｍａｘ｛ｃｏｓｔｘ｜ｘ１−ｘ２｜，ｃｏｓｔｙ｜ｙ１−ｙ２｜｝　　　…（２）
におけるｘ方向の移動量｜ｘ１−ｘ２｜とｙ方向の移動量｜ｙ１−ｙ２｜も挙げられる。ここで、ｍａｘ｛ａ，ｂ｝は、ａとｂの大きい方を表わす。
【００３８】
又、特願２００２−２６１８９の移動コストは、
Ｌ＝ｍａｘ｛ｃｏｓｔｘ（ｘ２−ｘ１，Ｖｘ），ｃｏｓｔｙ（ｙ２−ｙ１，Ｖｙ）｝
であったが、この場合でも、ｘ方向の移動時間を求める部分のｘ方向の移動量ｘ２−ｘ１とｘ方向の速度Ｖｘ，ｙ方向の移動時間を求める部分のｙ方向の移動量ｙ２−ｙ１とｙ方向の速度Ｖｙも、２つのパラメータの例である。このような例は、傾斜のある移動、納期までの日数を考慮する移動、物体の進行方向を考慮する移動のコスト等、幾らでも考え得る。
【００３９】
以下、本発明による移動コストの計算方法について、詳細に説明する。ここでは、一般的に、パラメータをｐ、ｑとし、移動コストがＬ＝ｃｏｓｔ（ｐ，ｑ）で算出されるものとする。従来の技術においては、都市番号の対のＸＯＲでインデックスを求めていたが、それを改良し、次のようにする。
【００４０】
（１）関数の第１引数ｐ、第２引数ｑを決める。ｐとｑの並びは交換しない。
【００４１】
（２）ｐとｑそれぞれに限界値（下限、上限）が無い場合には、限界値を適切に決める。限界値に収まらないものは、（ハッシュ）表を用いないで、実際の計算を行なう。
【００４２】
（３）ｐとｑそれぞれが連続的な数であれば、例えば最も近い離散的な値に変える。
【００４３】
（４）ｐとｑそれぞれの下限が０で１毎に離散化している場合を除き、乗算、加減算により、０から始まる配列のインデックスとなるよう、正規化する。
【００４４】
（５）ハッシュ関数は、それぞれ正規化されたｐとｑのＸＯＲとし、ハッシュ表の大きさｍは、ｐの最大値ｐｍａｘとｑの最大値ｑｍａｘの大きい方をｐｑｍａｘとすると、２の累乗でｐｑｍａｘより大きい最小の数とする。
【００４５】
これにより、従来の技術とほぼ同様に、移動コスト計算が可能になる。
【００４６】
以下、特願２００２−２６１８９で提案した、ＸＹステージとガルバノスキャナを共に動かしながら加工を行うステージ非停止加工の場合を例にとって、本発明を詳細に説明する。ここで移動コストは、前出（３）式で表わされる。そのうち、ｘ方向の移動時間を求める部分ｃｏｓｔｘ（ｘ２−ｘ１，Ｖｘ）に関して説明する。
【００４７】
（１）関数の第１引数ｐをｘ２−ｘ１（ｘ方向の都市間距離）、第２引数ｑをＶｘ（ｘ方向のステージ移動速度。ここで、基板上での相対移動を考慮しているため、０より大きい正値となるが、実機では、負の方向に動作することに注意する）とする。
【００４８】
（２）ｘ２−ｘ１に上下限はない。しかし、距離計算を行うのは、大多数が０を挟んで数ｍｍ〜数十ｍｍ程度であるので、その間に入るものに限定する。又、ステージ速度Ｖｘの最小値は０である。最大値は、システムで規定された限界や実験や理論を通して精度良く加工できると判断できる限界値で決める。例えば、数百ｍｍ／秒とする。
【００４９】
（３）ｘ２−ｘ１は穴座標の位置差なので、離散値である。一方、Ｖｘは連続値であるが、例えば１ｍｍ／秒や０．１ｍｍ／秒毎に離散化する。
【００５０】
（４）（２）で決めたｘ２−ｘ１の最小値をａ（＜０）とすると、０以上となるよう｜ａ｜を加える。Ｖｘが０．１ｍｍ／秒毎の離散値とすると、整数となるよう１０倍する。すると、ｐ、ｑは、下限が０で、１毎に離散化される。
【００５１】
（５）（１）〜（４）から、ハッシュ表のサイズｍは容易に算出される。
【００５２】
具体的な処理手順を図７に示す。まずステップ２００でパラメータ（引数）が上下限の範囲内か否かを判定する。判定結果が正である場合には、ステップ２０２に進み、引数を正規化する。次いでステップ２０４に進み、引数のＸＯＲ演算を行ない、結果を変数ｉｎｄに格納する。次いでステップ２０６に進み、その計算結果が蓄えられているか否かを判定する。判定結果が否である場合には、ステップ２０８で実際の計算を実行し、結果をｃａｃｈｅｖａｌ［ｉｎｄ］に格納すると共に、ｃａｃｈｅｓｉｇ［ｉｎｄ］を更新する。次いでステップ２１０に進み、ｃａｃｈｅｖａｌ［ｉｎｄ］の値を返す。
【００５３】
一方、ステップ２００の判定結果が否であり、パラメータが上下限の範囲内に無いときには、ステップ２１２で実際の計算を実行し、結果を返す。
【００５４】
例えば移動量ｐの上限を＋５０００μｍ、下限を−５０００μｍに設定し、５０００を加えて正規化するとｐｍａｘは１００００となる。又、ステージ速度ｑの上限を５００．０ｍｍ／秒、下限を０ｍｍ／秒に設定し、１０倍して小数点以下を切り捨てて正規化するとｐｍａｘ＝５０００となる。すると、配列サイズは、１００００を超える最小の２の累乗として、１６３８４となる。この場合のハッシュ表の例を図８に示す。
【００５５】
例えば移動量が＋１０００μｍ、ステージ速度が１２３．４５６ｍｍ／秒の場合、移動時間は、次のようにして求める。即ち、図７のステップ２００における上下限のチェックに際しては、引数が共に上下限を超えていないので、ステップ２０２に進む。正規化した値はｐ＝６０００、ｑ＝１２３４となるので、ステップ２０４でそのＸＯＲを演算すると、ｐ＾ｑ＝５０２６となる。ステップ２０６で、ｃａｃｈｅｓｉｇ［５０２６］が６０００であるかどうかをチェックする。そうであればステップ２１０でそのまま取り出し、そうでなければステップ２０８で実計算を実行する。
【００５６】
一方、移動量が−１５０００μｍ、ステージ速度が５３．４２３１ｍｍ／秒の場合、ステップ２００におけるチェックで、引数が上下限を超えている（移動量が−５０００以下）と判定されるので、ステップ２１２に進み、実計算を実行する。
【００５７】
本実施形態においては、演算としてＸＯＲを用いていたので、配列のサイズが小さく、演算ルールが単純である。しかし、この関数は、ＸＯＲで無くとも構わない。例えば、パラメータｐ、ｑに対して、パラメータ同士の加算（ｐ＋ｑ）や、減算及び最小値の非負化のための加算（ｐ−ｑ＋ｑｍａｘ）等を用いてもかまわない。
【００５８】
又、本実施形態においては、パラメータの数が２の場合のみを説明したが、パラメータの数は２に限定されず、３以上であってもよい。図９に示す如く、３つのパラメータｐ、ｑ、ｒをもつ移動コストの計算において、配列を２つ（ｃａｃｈｅｓｉｇ１［］、ｃａｃｈｅｖａｌ２［］）用意し、ｃａｃｈｅｓｉｇ１［］にはｐ＾ｑの結果を、ｃａｃｈｅｓｉｇ２［］には（ｐ＾ｑ）＾ｒの結果を格納するようにして、共に一致する場合のみｃａｃｈｅｖａｌ［］を参照するようにすればよい。ここで、全ての配列のサイズｍは、ｐ、ｑ、ｒの最大値の中の最大値に対し、２つの累乗でその値より大きい最小の数となることに注意する。同様にして、一般のパラメータ数ｎの場合にも適用出来ることは明らかである。
【００５９】
なお、前記実施形態においては、本発明がオンライン形態のレーザ穴開け機における移動コストの計算に適用されていたが、本発明の適用対象はこれに限定されず、オンライン形態、オフライン形態を問わず、マーキング装置や加工装置等のレーザビーム以外の加工手段を用いた加工機一般、更には、カーナビゲーションシステムにおける最短路の探索、物流支援ソフトにおける配送路の計画、移動ロボットの軌道の計画等の複数のパラメータを用いて計算される移動コストを持つ計画全てに対して同様に適用できる。
【００６０】
【発明の効果】
本発明によれば、プログラム全体の中でボトルネックとなっている２点間の移動コスト計算時間を大幅に削減できる。又、大きなメモリサイズを必要とせず、メモリを節約することができる。
【図面の簡単な説明】
【図１】ベントリーが提案した従来の移動コスト計算手順を示す流れ図
【図２】同じく計算例を示す線図
【図３】同じく表を示す線図
【図４】本発明が適用されるオンライン構成のレーザ穴開け機の例を示すブロック図
【図５】同じくオフライン構成のレーザ穴開け機の例を示すブロック図
【図６】本発明の一般的な適用対象の構成例を示すブロック図
【図７】本発明の実施形態の処理手順を示す流れ図
【図８】本発明の実施形態で用いられる表の例を示す線図
【図９】パラメータが３つの場合への適用例を示す線図
【符号の説明】
１０…加工対象物（ワーク）
１２…ＸＹステージ
２０…レーザ光線
２２、２４…ガルバノスキャナ
２３、２５…回転ミラー
２６…ｆ−θレンズ
３０…レーザ穴開け機
４０、６０、６２、７０…ＰＣ（パソコン）
４２…加工データファイル群
４４…加工データ変換プログラム
４６…加工データ
４８…動作モデルファイル
５０…動作モデル読込みプログラム
５２…動作モデルデータ
５４…加工計画プログラム
５６…加工制御プログラム
７２…入力データ
７４…移動コストデータ
７６…計画プログラム
７８…制御プログラム
８０…実施対象
【図１】
2004139532.tif 000003
【図２】
2004139532.tif 000004
【図３】
2004139532.tif 000005
【図４】
2004139532.tif 000006
【図５】
2004139532.tif 000007
【図６】
2004139532.tif 000008
【図７】
2004139532.tif 000009
【図８】
2004139532.tif 000010
【図９】
2004139532.tif 000011