(57)【特許請求の範囲】
【請求項１】
連続していない輪郭のパターンに従って機械を制御するための方法であって、
前記パターンの前記輪郭上の一組の出口点および入口点を求めることと、
前記一組の出口点および入口点の各点について少なくとも１つの速度ベクトルを求め、複数の速度ベクトルを生成することであって、各速度ベクトルの大きさは、前記機械の動力学を用いて求められる、生成することと、
前記機械の動力学を用いて、前記一組の出口点および入口点の点を接続する一組の軌道を求めることであって、各軌道は、前記出口点における前記速度ベクトルの出口速度を有する出口点から、前記入口点における前記速度ベクトルの入口速度を有する入口点へ進む前記機械の動作を表し、前記一組の軌道は、対応する出口点および対応する入口点において非ゼロ速度を有する、輪郭に沿った前記動作を表す少なくとも１つの軌道と、前記対応する出口点および前記対応する入口点において非ゼロ速度を有する、異なる輪郭間の前記動作を表す少なくとも１つの軌道とを含む、一組の軌道を求めることと、
各軌跡に沿った前記機械の前記動作を表す一組のコストに基づいて、前記パターンを追跡する前記機械の総動作コストを最適化する前記軌道のシーケンスを求めることと、
前記シーケンスに従って、前記機械を制御するための一組の命令を求めることと、
を含み、該方法のステップは、プロセッサによって実行され、前記速度ベクトルを考慮することで前記軌道のシーケンスの最適化を行う、連続していない輪郭のパターンに従って機械を制御するための方法。
【請求項２】
点に対する前記速度ベクトルの方向は、前記点のロケーションにおける前記輪郭の形状の接線の方向である請求項１に記載の方法。
【請求項３】
前記点の前記ロケーションに接続された前記輪郭のセグメントを機械加工するのに適した、前記機械の最大速度に最適に一致する前記速度ベクトルの大きさを求めることと、
前記対応する出口点および前記対応する入口点の速度ベクトルに基づいて前記一組のコストのそれぞれを求めることと
をさらに含む、請求項１に記載の方法。
【請求項４】
前記出口速度および前記入口速度を、前記出口点および前記入口点を接続する輪郭のセグメントを機械加工するのに適した最大速度として求めること
をさらに含む、請求項１に記載の方法。
【請求項５】
前記軌道を動的最適軌道として求めること
をさらに含む、請求項１に記載の方法。
【請求項６】
前記一組の命令を求めることは、
運動プリミティブの過剰完全集合を前記軌道の前記シーケンスにあてはめることと、
動的計画法を用いて、前記総動作コストを最適化する一組の運動から前記運動プリミティブの部分集合を選択することと
を含む、請求項１に記載の方法。
【請求項７】
グラフを構築することであって、該グラフのノードは、前記入口点および前記出口点を表し、切断エッジは、対応する隣接ノード間の前記輪郭に沿った前記軌道を表し、トラバースエッジは、異なる輪郭上のノード間の前記軌道を表すことと、
前記ノードと、前記切断エッジと、前記グラフの少なくとも幾つかのトラバースエッジとを通るツアーを、該ツアーが前記総動作コストを最適化するように求めることと、
前記ツアーに基づいて前記軌道の前記シーケンスを求めることと
をさらに含む、請求項１に記載の方法。
【請求項８】
各コストは、前記軌道に沿った動作時間を表し、前記ツアーは、該動作時間を最小にする、請求項７に記載の方法。
【請求項９】
隣接ノードによって形成された前記切断エッジを機械加工するのに適した最大速度に基づいて前記ノードの速度ベクトルを求めることと、
前記異なる輪郭上の前記ノードを接続する前記トラバースエッジを、対応するノードを接続する前記トラバースエッジが、該対応するノードにおいて対応する速度ベクトルを達成する前記機械の前記動力学を表すように求めることと
をさらに含む、請求項７に記載の方法。
【請求項１０】
請求項１に記載の方法であって、
前記一組の軌道は、同一の出口ノードおよび入口ノードを接続する少なくとも２つの軌道を含み、該少なくとも２つの軌道は、異なる形状を有し、該方法は、
前記一組のコストを同時に最適化することであって、各軌道に従って、前記シーケンスの前記軌道の形状と、前記シーケンス内の前記軌道の順序と、動作時間とを求めること
をさらに含む、請求項１に記載の方法。
【請求項１１】
前記ツアー内の各軌道について一組の代替の軌道を選択することと、
動的計画法を用いて、各軌道の前記コストに基づいて、元の軌道と代替の軌道との結合集合の部分集合を用いて前記ツアーを更新することと
をさらに含む、請求項１に記載の方法。
【請求項１２】
輪郭のパターンに従ってレーザー切断機を制御するための方法であって、
前記パターンの前記輪郭上の一組の出口点および入口点を求めることと、
前記一組の出口点および入口点の各点について少なくとも１つの速度ベクトルを求め、複数の速度ベクトルを生成することであって、各速度ベクトルの大きさは、前記レーザー切断機の動力学を用いて求められる、生成することと、
グラフを構築することであって、該グラフのノードは、前記輪郭上の前記入口点および前記出口点を表し、切断エッジは、隣接ノード間の前記輪郭に沿った切断を表し、トラバースエッジは、異なる切断輪郭上のノード間の動的に最適な軌道を表すことと、
前記ノードと、前記切断エッジと、前記グラフの少なくとも幾つかのトラバースエッジとを通るツアーを、該ツアーが総実行コストを最適化するように求めることと、
前記ツアーを、前記機械を制御するための一組の命令に変換することと
を含み、該方法のステップは、プロセッサによって実行され、前記速度ベクトルを考慮することで前記軌道の最適化を行う、輪郭のパターンに従ってレーザー切断機を制御するための方法。
【請求項１３】
点に対する前記速度ベクトルの方向は、前記点のロケーションにおける前記輪郭の形状の接線の方向である請求項１２に記載の方法。
【請求項１４】
前記動的最適トラバース軌道は、非フライゾーンを迂回したルートを取るように制約される、請求項１２に記載の方法。
【請求項１５】
前記変換することは、
運動プリミティブの過剰完全集合を前記ツアーにあてはめることと、
動的計画法を用いて、各運動プリミティブの機械加工のコストに基づいて、前記運動プリミティブの前記集合から前記運動プリミティブの部分集合を選択することと
を含む、請求項１２に記載の方法。
【請求項１６】
前記グラフは、巡回セールスマン問題（ＴＳＰ）グラフであり、該方法は、
前記ノードおよび前記切断エッジを強制的に解に入れながら、ＴＳＰソルバを前記グラフに適用することであって、前記ツアーを生成すること
をさらに含む、請求項１２に記載の方法。
【請求項１７】
前記構築することは、
前記パターンの前記輪郭を一組の切断エッジに分割することであって、該切断エッジの端点は、前記グラフの前記ノードを形成することと、
ノードに対応する切断エッジのプロファイルと、該切断エッジを切断するのに適した最大速度とに基づいて、各ノードについて速度ベクトルを求めることと、
前記異なる輪郭上の前記ノードを接続する前記トラバースエッジを、２つのノードを接続するトラバースエッジが前記２つのノードの前記速度ベクトルを達成する前記機械の動力学を表すように求めることと
を含む、請求項１２に記載の方法。
【請求項１８】
近傍ノードの前記トラバースエッジを求めること
をさらに含む、請求項１２に記載の方法。
【請求項１９】
前記切断エッジおよび前記トラバースエッジに沿った実行コストを求めることであって、一組のコストを生成することと、
一組の優先度に従って前記一組のコストを変更することと、
前記一組のコストを同時に最適化することであって、前記総実行コストを最適化する前記ツアーを求めることと
をさらに含む、請求項１２に記載の方法。
【請求項２０】
レーザー切断機であって、
パターンに従って工作物を切断するためのレーザーカッターと、
一組の命令に従って前記レーザーカッターをナビゲートするための制御モジュールであって、前記レーザーカッターが停止することなく切断エッジおよびトラバースエッジを追跡するようにする、制御モジュールと、
前記パターンを追跡する前記レーザーカッターの総動作コストを最適化するツアーに基づいて前記一組の命令を生成するための運動計画モジュールであって、該運動計画モジュールは、一組の切断エッジと一組のトラバースエッジとを求め、該一組のトラバースエッジ内の軌道は、輪郭上の点の速度ベクトルと異なる輪郭上の点の速度ベクトルとの対を接続する動的に最適な軌道であり、前記点の前記速度ベクトルの大きさは、前記点の前記ロケーションに接続された前記輪郭のセグメントを機械加工するのに適した、前記レーザー切断機の最大速度に最適に一致し、該運動計画モジュールは、巡回セールスマン問題（ＴＳＰ）ソルバを適用して前記ツアーを生成する、運動計画モジュールと
を備え、前記速度ベクトルを考慮することで前記軌道の最適化を行う、レーザー切断機。
【請求項２１】
前記トラバースエッジは、非フライゾーンを迂回したルートをとるように制約される、請求項２０に記載のレーザー切断機。
【請求項２２】
前記一組の命令は、運動プリミティブを前記ツアーにあてはめることに基づいて求められる、請求項２０に記載のレーザー切断機。
【請求項２３】
連続していない輪郭のパターンに従って機械を制御するための一組の命令を求めるための方法であって、
前記連続していない輪郭のパターンと、前記機械の動力学のうちの少なくとも１つとを取得することと、
前記パターンの前記輪郭上の一組の点を求めることと、
前記一組の点の各点について少なくとも１つの速度ベクトルを求め、複数の速度ベクトルを生成することであって、各速度ベクトルの大きさは、前記機械の前記動力学を用いて求められる、生成することと、
前記パターンを追跡する前記機械の総動作コストを最適化する軌道のシーケンスに従って前記機械を制御するための一組の命令を生成することであって、前記軌道のシーケンスは、対応する出口点および対応する入口点において非ゼロ速度を有する、輪郭に沿った前記動作を表す少なくとも１つの軌道と、前記対応する出口点および前記対応する入口点において非ゼロ速度を有する、異なる輪郭間の前記動作を表す少なくとも１つの軌道とを含む、生成することと
を含み、該方法のステップは、プロセッサによって実行され、前記速度ベクトルを考慮することで前記軌道のシーケンスの最適化を行う、連続していない輪郭のパターンに従って機械を制御するための一組の命令を求めるための方法。
【請求項２４】
点に対する前記速度ベクトルの方向は、前記点のロケーションにおける前記輪郭の形状の接線の方向である請求項２３に記載の方法。
【請求項２５】
前記機械の前記動力学は、最大加速度を含む、請求項２３に記載の方法。
【請求項２６】
前記一組の命令は、前記パターンに従った工作物の機械加工の位置、速度、およびオン／オフ信号を制御する、請求項２３に記載の方法。
【請求項２７】
前記機械は、異なる輪郭間の前記動作を表す軌道を追跡するために停止しない、請求項２３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、機械の運動計画を生成するためのシステムおよび方法に関し、より詳細には、輪郭のパターンに従って機械を制御するための一組の命令を求めることに関する。
【背景技術】
【０００２】
コンピューター数値制御（ＣＮＣ：computer numerical controlled）による機械加工では、所定のパターンに従って工作物に対しツールヘッドを動かし、工作物の機械加工を実行する。機械加工は、工作物の切断またはドリル加工等の、工作物の様々なタイプの処理を含むことができる。説明を簡単にするために、一般性を損なうことなく、本開示において、機械加工は、レーザー切断機を用いて工作物を切断する工程として例示される。
【０００３】
パターンに従ってシート材料から特徴を切り取ることは、一般的な製造工程である。通常、レーザー切断機の切断ヘッドは、直交軸に沿って有限平面内を平行移動される。このタイプのレーザーカッターは、多くの場合に、材料、例えば様々な厚さのプラスティックシートおよび金属シートから、個別的な特徴を切り取るのに用いられる。レーザーカッターの制御は、通常、「ＮＣコード」または「Ｇコード」として実施される場合もある所定の一組の命令に従って、コンピューター数値制御装置（ＣＮＣ：computer numerical controller）によって実行される。
【０００４】
切り取られるパターンが連続していない輪郭を含む場合、機械加工は、再位置決めと交互に行われ、例えば、切断後に機械がカッターをオフにし、新たなロケーションまでトラバースし、カッターをオンに戻して機械加工を継続する。機械の運動は、パターン、例えば、切り取られることになる輪郭の全ての曲線の図に基づいて計画される。通常、曲線のうちの幾つかは、材料から切り出される形状を表すように閉じている。計画問題は、全ての切断の最小時間または最小エネルギーのツアー（巡路）を求めることを含むことができる。このツアーは、切断の順序を指定する。
【０００５】
最近まで、全ての機械加工は、停止・開始運動によって特徴付けられていた。機械加工中、切断ヘッドは、パターンの輪郭の計画された切断曲線の入口点に接近し、停止し、カッターをオンにし、次いで、次の切断運動に進む。したがって、「ラピッド（rapids）」としても知られる最速の切断間トラバースは、直線であった。「停止−開始」機械加工の計画問題は、切断順序、および切断間の最も短い直線のトラバースを同時に見つけることを含むことができる。そのような計画問題の１つの従来の解決策は、巡回セールスマン問題（ＴＳＰ）の一変形を用いる。例えば、非特許文献１を参照されたい。
【０００６】
しかしながら、これらの運動計画によって仮定されるレーザーカッターの「停止−開始」挙動によって、機械の生産速度が制限される。高速機械加工の場合、多数の加速および減速によって高いエネルギーコストが課され、機械が消耗する可能性がある。
【０００７】
切断技術の進歩によって、今や、「オンザフライ」で、すなわち、カッターをオンまたはオフにするために停止することなく切断することが可能になっている。これによって、より高速なツアーが可能になるが、オンザフライ機械加工における直線のトラバースは、完全に準最適となる可能性があるので、はるかにより複雑な計画問題も課される。しかしながら、直線のトラバースを他のタイプのトラバースと置き換えることは、準最適である。なぜなら、この解決法は、機械の動的特性を十分考慮しないためである。例えば、特許文献１を参照されたい。他の解決法は、手書きのツアーを含むが、これは、明らかに大きな計画問題には実際的な方法でない。
【０００８】
したがって、連続していない輪郭のパターンに従って機械を制御するための、効率的で、動的に最適化された運動計画を自動的に生成する必要がある。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第６，６０９，０４４号
【非特許文献】
【００１０】
【非特許文献１】HoeftおよびPalekar「Heuristics for the Plate-Cutting TSP」（IIE Transactions vol. 29, 1997）
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の様々な実施の形態の目的は、輪郭のパターン、例えば、連続していない輪郭のパターンに従って、機械を制御するための一組の命令を求めるためのシステムおよび方法を提供することである。幾つかの実施の形態は、切断または切断なしのトラバース等の処理運動の順序付け、これらの運動の輪郭上の入口点および出口点、これらの出口点および入口点間の動的に最適なトラバース軌道、並びに運動計画に沿った様々な点における運動の速度プロファイルのうちの１つまたはそれらの組合せを含むオンザフライ機械加工の運動計画を生成するための方法を提供する。
【課題を解決するための手段】
【００１２】
幾つかの実施の形態は、機械加工の速度を最適化するために、機械のツールヘッドが、セグメントの最大切断速度を、その曲率および機械の動力学に基づいて最適に整合させながら、接線上での各セグメント輪郭の入口点および出口点に進むべきであるという認識に基づいている。この認識によって、例えば、切断軌道およびトラバース軌道を含むツアー、すなわち、軌道のシーケンスを求めることが可能になり、動的に最適な方式で、パターンを追跡することが可能になる。トラバース軌道の例は、実際の機械加工なしで機械のツールヘッドを再位置決めすることである。
【００１３】
トラバース軌道の各端における速度ベクトルは、出入りされる切断輪郭のセグメントの形状によって求めることができる。これらのベクトル間の最適な軌道は、機械の動力学、例えば、機械の運動量、速度制限、または加速度制限に基づいて求めることができる。幾つかの実施の形態は、大きな加速を可能にするレーザー切断機を用いて、工作物を切断するプロセスにおいて用いられる。他の実施の形態は、他のタイプの機械加工、例えば、スクライビング、彫刻、およびプロッティングによって用いられる。
【００１４】
多くの場合に、最適なトラバース軌道は、湾曲している。機械の動力学に起因して、湾曲したトラバース軌道は、直線のトラバースよりも高速にし、エネルギー効率を良くすることができる。さらなる複雑な点は、幾つかのカッターは、切断ヘッドがトラバース中に回避しなくてはならない「非フライゾーン（no-fly zone：通過禁止ゾーン）」を有する場合があることである。例えば、熱いヘッドは、薄い材料を歪ませる可能性があり、このため、全てのトラバースは、廃材の上のみを通過すべきである。
【００１５】
さらに、幾つかの実施の形態は、速度ベクトルを、パターンの輪郭上の様々な可能な出口点および入口点に割り当てることができ、任意のツアーにおける１つの出口点から１つの入口点へ進むコストは、出口速度を有する出口点から入口速度を有する入口点へ機械の動作を移す動的最適軌道のコストを示し、例えば、このコストに等しいという特定の認識に基づいている。そのような認識によって、一組の候補トラバース軌道を求め、様々な最適化技法を用いてツアーを選択することが可能になる。
【００１６】
したがって、１つの実施の形態は、連続していない輪郭のパターンに従って、機械を制御するための方法を開示する。本方法は、パターンの輪郭上の一組の出口点および入口点を接続する一組の軌道に沿った機械の動作を表す一組のコストを求める。ここで、各軌道は、機械の動力学に従って、出口速度を有する出口点から入口速度を有する入口点に進む機械の動作を表す。一組の軌道は、対応する出口点および対応する入口点において非ゼロ速度を有する、輪郭に沿った動作を表す少なくとも１つの軌道と、対応する出口点および対応する入口点において非ゼロ速度を有する、異なる輪郭間の動作を表す少なくとも１つの軌道とを含むことができる。次に、本方法は、コストに基づいて、パターンを追跡する機械の総動作コストを最適化する軌道のシーケンスを求め、シーケンスに従って機械を制御するための一組の命令を求める。
【００１７】
別の実施の形態は、連続していない輪郭のパターンに従ってレーザー切断機を制御するための方法を開示する。本方法は、ノードおよびエッジを含むグラフを構築するステップであって、グラフのノードは、輪郭上の入口点および出口点を表し、切断エッジは、隣接ノード間の輪郭に沿った切断を表し、トラバースエッジは、異なる切断輪郭上の入口点と出口点との間の動的に最適な軌道を表す、構築するステップと、ノードと、切断エッジと、グラフの少なくとも幾つかのトラバースエッジとを通るツアーを、そのツアーが総実行コストを最適化するように求めるステップと、ツアーを、機械を制御するための一組の命令に変換するステップと、を含む。本方法のステップは、プロセッサによって実行される。
【００１８】
さらに、別の実施の形態は、レーザー切断機であって、連続していない切断輪郭のパターンに従って工作物を切断するためのレーザーカッターと、一組の命令に従ってレーザーカッターをナビゲートするための制御モジュールであって、レーザーカッターが停止することなく、切断エッジおよびトラバースエッジを追跡するようにする、制御モジュールと、パターンに基づいて一組の命令を生成するための運動計画モジュールであって、一組の命令は、パターンを追跡するレーザーカッターの総動作コストを最適化するツアーに基づいて生成され、運動計画モジュールは、一組の切断エッジと一組のトラバースエッジとを求め、一組のトラバースエッジ内の軌道は、動的に最適な軌道であり、運動計画モジュールは、巡回セールスマン問題（ＴＳＰ）ソルバ（解法）を適用してツアーを生成する、運動計画モジュールと、を備える、レーザー切断機を開示する。
【００１９】
さらに、別の実施の形態は、連続していない輪郭のパターンに従って機械を制御するための一組の命令を求めるための方法を開示する。本方法は、連続していない輪郭のパターンと、機械の動力学のうちの少なくとも１つとを取得するステップと、パターンを追跡する機械の総動作コストを最適化する軌道のシーケンスに従って機械を制御するための一組の命令を生成するステップであって、軌道のシーケンスは、対応する出口点および対応する入口点において非ゼロ速度を有する、輪郭に沿った動作を表す少なくとも１つの軌道と、対応する出口点および対応する入口点において非ゼロ速度を有する、異なる輪郭間の動作を表す少なくとも１つの軌道とを含む、生成するステップと、を含む。
【図面の簡単な説明】
【００２０】
【図１Ａ】本発明の幾つかの実施の形態によるレーザー切断機の概略図である。
【図１Ｂ】本発明の幾つかの実施の形態によるレーザー切断機の概略図である。
【図２】連続していない輪郭の例示的なパターンを示す図である。
【図３】本発明の幾つかの実施の形態による、連続していない輪郭のパターンに従って機械を制御するための方法のブロック図である。
【図４Ａ】幾つかの実施の形態による、巡回セールスマン（ＴＳＰ）問題を求めて解くための方法の変形形態のフローチャートである。
【図４Ｂ】幾つかの実施の形態による、巡回セールスマン（ＴＳＰ）問題を求めて解くための方法の変形形態のフローチャートである。
【図５】幾つかの実施の形態による例示的なＴＳＰグラフの一部の図である。
【図６】本発明の幾つかの実施の形態による、図２のパターンの一部について求められたツアーの例を示す図である。
【図７】本発明の様々な実施の形態による迂回戦略の例を示す図である。
【発明を実施するための形態】
【００２１】
図１Ａは、本発明の幾つかの実施の形態によって制御するのに適したレーザー切断機１０の一例を示している。説明を簡単にするために、一般性を損なうことなく、機械加工は、レーザー切断機を用いて工作物を切断する工程として例示される。
【００２２】
機械１０は、特定の形状に切断されるシート材料の表面に平行な任意の方向にレーザーヘッド２０を動かすように構成される。レーザーヘッド２０は、通常、レーザーヘッドの先端から、切断されるシート材料の上面までの、「下」位置にあるときの距離を維持する非接触デバイスである。「接触」型ヘッドを含む他のタイプのレーザーヘッドも可能である。
【００２３】
レーザーヘッド２０は、レーザー切断機のメインテーブルの長手寸法に垂直な線方向に前後に動くことができるように、往復台に取り付けられる。レーザーヘッド２０がこの垂直方向にトラバースすると、指定されたアコーディオン状のカーテン２２は、それに従って伸び縮みすることができる。レーザーヘッド往復台構造２４は、機械１０の主軸に沿って長手方向に動くことも可能であり、レーザーヘッド構造のいずれかの側のアコーディオン状のカーテン２６、２８は、それに従って伸び縮みすることができる。レーザーヘッド２０の動きは、通常、コンピューター数値制御装置１５によって制御される。
【００２４】
例えば、シート材料で作製された平面状部品３０は、特殊なベッド状の構造部３２の上に配置される。ベッド状の構造部３２は、比較的薄い金属シート材料のＸ−Ｙグリッド構造で作製され、このＸ−Ｙグリッド構造は、シート材料３０の底面を支持する複数の「点」３４を作成するように構築される。
【００２５】
通常、レーザーヘッド２０の先端と、シート材料３０の上面との間に小さな空隙が維持される。シート材料３０が切り出されたが、ベッド３２の底まで落下することに失敗したとき、場合によっては、切り出された小片がベッド３２の上部に「引っかかっている」可能性がある。
【００２６】
図１Ｂは、幾つかの実施の形態によって、レーザー１１０によって生成されたビーム１１５を工作物１１１上に位置決めするように制御するのに適したレーザー切断機１００の別の例のブロック図である。説明を簡単にするために、一般性を損なうことなく、機械加工は、機械１０または１００等のレーザー切断機を用いて工作物を切断する工程として例示される。しかしながら、本発明の実施の形態を利用するのに適した機械の他の変形形態、レーザー切断機の他の変形形態、およびレーザー切断機１０または１００の設計の他の変形形態が可能であり、本発明の範囲内にある。
【００２７】
レーザー切断機１００は、少なくとも第１の方向１２０に沿って動くように構成されたプラットフォーム１１２を備えることができる。このプラットフォームは、このプラットフォームを工作物に平行な面において動かすための運動システム１２２によって動かされる。１つの実施の形態では、運動システム１２２は、第１の方向１２０に沿ったプラットフォームの第１の運動を容易にする第１の直動ジョイントを備える。
【００２８】
付加的にまたは代替的に、レーザー切断機は、第１の方向１２０に沿ったプラットフォームの運動によって、第１の方向に沿ったガルバノヘッドの運動が生じるように、例えば、プラットフォーム１１２上に配置されたガルバノヘッド１１３を備えることができる。例えば、ガルバノヘッドは、可逆ＤＣモーターを備えることができ、この可逆ＤＣモーターは、出力シャフト上にミラーを備え、通常、内蔵のバンプストップを備え、ミラーの回転を小さい角度に、通常、中心の回りに＋／−２０度〜３０度に制限する。ガルバノヘッドは、多くの場合に単一の統合ユニットとして構成される。
【００２９】
例えば、位置１１２’へのプラットフォームの運動によって、ガルバノヘッドは、位置１１３’に動かされる。また、ガルバノヘッドの動作によって、レーザービームは、少なくとも第２の方向１３０に沿って工作物に方向付けられる。ガルバノヘッドは、第２の方向１３０が第１の方向１２０に対して固定されるように、プラットフォーム上に配置することができる。これによって、レーザービームを、同時に第１の方向および第２の方向に沿って方向付けることが可能になる。機械１００の様々な実施態様では、工作物に対するレーザービームの位置は、第１の運動と第２の運動とのベクトル和１４０である。
【００３０】
プラットフォームの運動およびガルバノヘッドの動作は、制御モジュール１５０によって制御することができる。制御モジュール１５０は、プロセッサ１５１を用いて実装することができる。幾つかの実施の形態では、制御モジュールは、コンピューター数値制御装置（ＣＮＣ：computer numerical control）１９５を備える。制御モジュールは、レーザービームの位置の軌道を定義するＧコード１９０に従って、運動システムおよびガルバノヘッドを制御する。例えば、Ｇコード１９０は、Ｇコード軸Ｘ上の運動としてＸ軸プラットフォームの位置を符号化し、Ｇコード軸Ｙ上の運動としてＹ軸ガントリーの位置を符号化し、Ｇコード軸Ａ上の運動としてＸ運動ガルバノおよびミラーの位置を符号化し、Ｇコード軸Ｂ上の運動としてＹ運動ガルバノおよびミラーの位置を符号化する。この４軸Ｇコードは、レーザー切断機の動作中に制御装置によって解釈される。また、機械は、例えば、Ｇコード１９０の形態の、パターンに従って機械を制御するための一組の命令を求めるための運動制御モジュール１８０を備えることができる。
【００３１】
レーザー切断機１０および１００は、「オンザフライ」の、すなわち、カッターをオンまたはオフにするために停止することのない切断または他のタイプの機械加工を可能にする技術の例である。これによって、より高速なツアーが可能になるが、そのような機械にとって直線のトラバースは、準最適である可能性があるので、はるかに、より複雑な計画問題も課される。
【００３２】
図２は、輪郭２１０、２１２、２１４、２１６、および２１８等の、工作物の材料を切断するのに用いることができる連続していない輪郭のパターン２００の例を示している。パターン２００は、連続していない輪郭を含むので、パターンに従った工作物の機械加工は、再位置決めと交互に行われ、例えば、切断後に機械がカッターをオフにし、新たなロケーションにトラバースし、カッターをオンに戻し、機械加工を継続する。様々な実施の形態では、レーザー切断機等の機械は、異なる輪郭間の動作を表す軌道の追跡開始前または追跡中に停止しない。
【００３３】
したがって、切断軌道、すなわち、軌道２２６等の、輪郭に沿った切断の軌道は、トラバース軌道、すなわち、軌道２２５等の、切断を行うことなくカッターを新たな位置に再位置決めする軌道と交互になることができる。各軌道の端点は、輪郭からの軌道を開始する出口点と、輪郭への軌道に入る入口点とを含む。端点は、パターンの輪郭のうちの１つの上に位置する。通常、切断軌道の端点、例えば、軌道２２６の点２２２および２２４は、同じ輪郭上にある。一方、トラバース軌道の端点、例えば、軌道２２５の点２２２および２２８は、通常、異なる輪郭上にある。各端点は、出口点、入口点、または双方とすることができる。
【００３４】
切断順序および入口点／出口点は、所与ではなく、本発明の幾つかの実施の形態によって求められる。加えて、幾つかの実施の形態は、軌道の形状を求め、軌道に沿って進むタイミングを求め、そして、機械のトラバース運動および切断運動の双方の形状およびタイミングを制御する。また、幾つかの実施の形態では、入口点／出口点の順序、軌道の形状、およびタイミングは、同時に最適化される。この同時最適化は、他の方法よりも有利である可能性がある。他の方法は、順序を求め、かつ場合によっては入口点を求めるが、形状およびタイミングは、運動制御装置によって後に求めるように残しておくので、準最適である。
【００３５】
図３は、本発明の幾つかの実施の形態による、連続していない輪郭のパターンに従って機械を制御する方法のブロック図を示している。特に、１つの実施の形態は、ツアー、例えば、パターンを追跡する機械３６０の総動作コストを最適化する軌道３４０のうちの少なくとも幾つかのシーケンス３２５を求め、このツアーに従って機械を制御する（３５０）ための一組の命令３３５を求める。幾つかの実施の形態では、この一組の命令は、パターンに従った工作物の機械加工の位置、速度、およびオン／オフコマンド信号を含む。
【００３６】
本方法のステップは、プロセッサ３０１によって実行することができる。例えば、本方法のステップは、制御モジュール１５０によって、かつ／または、例えば、制御装置１９５の一部として実装することができる運動計画モジュール１８０によって実施することができる。運動計画モジュールは、例えば、Ｇコード１９０の形態で、命令３３５を生成することができる。
【００３７】
幾つかの実施の形態は、高い速度を維持するために、機械のツールヘッドは、接線上で輪郭の各セグメントを出入りすべきであり、セグメントの形状および機械の動力学が許す、そのセグメントの最大切断速度に一致するのが最適であるという一般的な認識に基づいている。特に、トラバースの各端点における速度ベクトルは、出入りされている輪郭のセグメントの形状によって求めることができる。これらのベクトル間の最適な軌道は、機械の動力学、例えば、機械の運動量、速度制限、および加速制限によって求めることができる。
【００３８】
さらに、幾つかの実施の形態は、パターンの輪郭上の様々な可能な出口点および入口点に、速度ベクトルを割り当てることができ、任意のツアーにおける１つの出口点から１つの入口点に進むコストは、出口速度を有する出口点から入口速度を有する入口点に機械の動作を移す動的最適軌道のコストを示し、例えば、そのコストに等しいという特定の認識に基づいている。そのような認識によって、一組の候補トラバース軌道を求め、様々な最適化技法を用いてツアーを選択することが可能になる。
【００３９】
さらに、幾つかの実施の形態は、パターンを追跡する機械の総動作コストを最適化する軌道のシーケンスを含む一組の命令に従って機械を制御することが有利であるという別の認識に基づいている。一組の軌道は、対応する出口点および対応する入口点において、非ゼロ速度を有する、輪郭に沿った動作を表す少なくとも１つの軌道と、対応する出口点および対応する入口点において非ゼロ速度を有する、異なる輪郭間の動作を表す少なくとも１つの軌道とを含む。
【００４０】
したがって、本発明の１つの実施の形態は、パターンの輪郭上の一組の出口点および入口点を接続する一組の軌道３４０に沿った機械３６０の動作を表す一組のコスト３１５を求める（３１０）。各軌道、例えば、軌道３４５は、機械の動力学３６５に従って、出口速度３７５を有する出口点から入口速度３７３を有する入口点に進む機械の動作を表す（３７０）。機械の動力学３６５は、機械の最大加速度を含むことができる。通常、一組の軌道は、対応する出口点および対応する入口点において非ゼロ速度を有する、輪郭に沿った動作を表す少なくとも１つの軌道、例えば、図２の軌道２２６と、対応する出口点および対応する入口点において非ゼロ速度を有する、異なる輪郭間の動作を表す少なくとも１つの軌道、例えば、図２の軌道２２５とを含む。
【００４１】
幾つかの変形形態では、軌道３４０は、対応する出口点および対応する入口点と関連付けられた最適な切断速度ベクトルに基づいて求められた動的最適軌道である。各速度ベクトルは、機械の動作の速度値と速度方向とを含む。例えば、出口点および入口点ごとの速度ベクトルは、点のロケーションにおける輪郭の形状３６３と、機械の動力学３６５とに基づいて求めることができる。例えば、出口速度および入口速度は、出口点と入口点とを接続する輪郭のセグメントを機械加工するのに適した最大速度に基づいて求めることができる。別の実施の形態では、スプラインを用いて、セグメント端点を接続する動的に最適な軌道が求められる。
【００４２】
コスト３１５は、対応する軌道に従って機械の動作のコストを表す。より一般的には、軌道のコストは、軌道の時間、距離、エネルギー等の任意の関数とすることができる。例えば、コストは、追跡時間、軌道を追跡するのに必要なエネルギー、または他の消耗物に基づくことができる。次に、コスト３１５に基づいて、パターンを追跡する機械の総動作コストを最適化する軌道のシーケンス３２５が求められる（３２０）。様々な実施の形態は、様々な最適化技法を用い、それらのうちの幾つかを、以下で説明する。
【００４３】
シーケンス３２５は、パターンを追跡するツアーを形成する。このツアーは、所定の順序の軌道３４０の部分集合を含む。さらに、軌道３４０は、最適化前に、機械の動力学３６５に基づいて求められるので、この求めること３２０によって最適な部分集合も選択され、このため軌道の形状およびそのトラバース時間も求められる。次に、シーケンスに従って機械３６０を制御する（３５０）ための一組の命令３３５を求め（３３０）、例えば、メモリに格納するか、コントローラに送信することができる。
【００４４】
幾つかの実施の形態は、ツアーを求めるためのコスト最適化問題は、巡回セールスマン問題（ＴＳＰ）、例えば、非メトリックＴＳＰとして提起することができるという別の認識に基づいている。ここで、ＴＳＰの解は、一組の軌道にわたる所望のツアーである。幾つかの実施の形態では、コストは、軌道を明確に計算することなく計算されるので、ＴＳＰにおいて多数の可能なトラバースを検討することができる。
【００４５】
有利には、ＴＳＰは、リアルタイムで構築することができ、妥当な時間量で近最適解も得ることができ、様々な実施の形態によって様々な第三者またはカスタムＴＳＰソルバを用いることができる。ＴＳＰソルバは、分枝限定アルゴリズムと、切除平面法と、リン−カーニハン法と、アニーリング法と、遺伝的アルゴリズムと、タブー探索法と、ボルツマンマシンと、他のソルバとを含む。
【００４６】
例えば、幾つかの実施の形態は、一組の切断エッジおよび一組のトラバースエッジを含むＴＳＰグラフを構築し、切断エッジの端点は、グラフのノードを形成し、一組のトラバースエッジ内の軌道は、異なる輪郭からのノード対を接続する動的に最適な軌道である。このため、グラフに適用されたＴＳＰソルバは、動的に最適なツアーを生成することができる。
【００４７】
ＴＳＰグラフは、ノード・エッジグラフであり、ノード・エッジグラフでは、各ノードは、可能な切断入口点または切断出口点を表し、各エッジは、任意選択のトラバース軌道、または切断等の必要とされる処理運動のいずれかを表す。本開示では、これらの運動は、切断と呼ばれるが、本発明の幾つかの実施の形態では、他のプロセスを工作物に適用することもできる。グラフ内の全てのエッジは、コストを割り当てられ、通常、時間、エネルギー、または何らかの他の消耗物の使用を反映する。幾つかの実施の形態は、切断を表す全てのノードおよび全てのエッジを通過するこのグラフの最小コストツアーを求める。最小コストツアーは、切断の入口、出口、およびトラバースの最適なシーケンスを与える。幾つかの実施の形態では、ツアーは、機械の運動を完全に指定する。他の実施の形態では、ツアーは、動的に平滑化され、最小エネルギーまたは最小コストの運動計画が得られる。
【００４８】
ＴＳＰグラフは、切断端点を表すノードと、切断を表すエッジ、すなわち、切断エッジ、または切断間のトラバースを表すエッジ、すなわち、トラバースエッジとを含む。様々な実施の形態において、切断エッジは、強制的にＴＳＰ解に入れられる。次に、それに加えて、ＴＳＰソルバは、完全なツアーを作成するためのトラバースエッジの部分集合を選択する。完全なツアーは、動的に最適なトラバース軌道によって接続された切断の最小コストの順序付けを含む。幾つかの実施の形態は、汎用ＴＳＰソルバを用いるか、または全ての切断エッジの集合から開始するツアーを求めるためのカスタムソルバを考案する。
【００４９】
このため、幾つかの実施の形態では、運動計画問題は、ＴＳＰグラフにおける非メトリックＴＳＰに縮小され、ここで、（１）ＴＳＰグラフを構築すること、（２）ＴＳＰグラフのエッジのコストを求めること、（３）ＴＳＰグラフを解いてツアーを求めること、および（４）ツアーシーケンスを変換して動的に最適な物理軌道にすること、のうちの１つまたは組合せによって、幾つかのエッジが強制的にツアーに入れられる。
【００５０】
ＴＳＰグラフの決定
図４Ａは、幾つかの実施の形態による、ＴＳＰグラフを求め、このＴＳＰグラフを解いて動的に最適なツアー４７０を求めるための方法４００のフローチャートを示している。図４Ｂは、代替的な実施の形態による方法４００のフローチャートを示している。切断する一組の輪郭４１０が与えられると、全ての輪郭が一組のセグメントに分割される（４１５）。各セグメントの２つの端点は、それぞれノードをＴＳＰグラフに提供する。セグメントは、端点ノードを接続するエッジをＴＳＰグラフに提供する。このエッジは、切断を表す。端点ノードのそれぞれについて、セグメントの形状、およびそのセグメントのための機械の最大切断速度に従って、入口速度ベクトルまたは出口速度ベクトルが求められる（４２５）。通常の実施の形態では、ベクトルは、切断に接しており、ベクトルの大きさは、入口点または出口点における切断の曲率に反比例する。代替的な実施の形態では、端点における最適な速度を表す様々な関数を用いることができる。例えば、図４Ｂの実施の形態では、各端点における速度を表す一組のスプラインが求められる（４２５’）。
【００５１】
幾つかの実施の形態では、機械加工の開始位置および終了位置を表す１つまたは２つの付加的なノードが、ＴＳＰグラフに加えられる（４２０）。開始位置および終了位置は、異なる位置または同じ位置、例えば、機械のホーム位置とすることができる。これらのノードのそれぞれは、ゼロ速度ベクトルを有し、ＴＳＰ解は、これらのノードが切断の端点であるかのように、シーケンスにおいて、これらのノードを通過するように強制される。
【００５２】
トラバースエッジが出口点および入口点の各対について、ＴＳＰグラフに加えられる。幾つかの実施の形態では、グラフ内のノードごとに、連続していない輪郭上に位置する入口点または出口点の物理的に近い一組のノードが、例えば、ノード間のユークリッド距離に基づいて求められる（４３０）。これらの実施の形態では、トラバース軌道は、近いノードの対についてのみ求められ、このため、計算量が低減される。加えて、１つの実施の形態は、近いノードの対を、一切「非フライゾーン」にわたってトラバースすることなく到達することができる対に限定する。幾つかの実施態様は、全てのノードロケーションをｋ−Ｄツリーに入力し、各ノードの空間的な近傍において範囲クエリまたはボールクエリを実行することによって、これらの近いノードを求める。
【００５３】
一対の近いノードを表す端点の対ごとに、幾つかの実施の形態は、例えば、関連付けられた速度ベクトルから開始する一方の端点から、関連付けられた速度ベクトルで終了する他方の端点へのトラバースの時間またはエネルギーに基づいて、動的に最適なトラバース軌道を求める。軌道は、速度ベクトルに基づいて求めることができる。図４Ａに示すように、例えば、端点の対ごとに、速度ベクトルを接続する動的に最適な軌道が求められる（４３５）。代替的に、図４Ｂに示すように、トラバース軌道は、例えば、スプラインを用いて、速度を表す他の関数に基づいて求める（４３５’）ことができる。
【００５４】
トラバース軌道は、最大速度、最大加速度、ジャーク、および機械の運動範囲等の、機械動力学または運動制約４８０によって制限される。機械の動力学は、例えば、機械の仕様によって規定することができる。幾つかの実施の形態では、運動制約に違反するか、または非フライゾーンに交差する軌道は、グラフから除去される（４４０）。
【００５５】
例えば、１つの実施の形態では、動的に最適な軌道ｘ（ｔ）、０＜ｔ＜Ｔｍａｘは、以下に対する解である。
【００５６】
【数１】
0005897151.tif 000002
【００５７】
最適な軌道は、ＣＮＣ制御の変形形態に基づいて求めることができる。例えば、トラバース軌道は、目標位置のみでなく、目標速度および目標進行方向に達しなくてはならないという点で、ＣＮＣ制御によって求められる軌道と異なる。これに関して、運動計画問題は、宇宙船制御により近い。
【００５８】
ほとんどの機械において、Ｘ軸運動およびＹ軸運動は、独立して制御することができ、したがって、最適なトラバース軌道を、方向ＸおよびＹにおいて、独立して計算することができる。例えば、速度制限および加速度制限のみを適用する場合、各次元における運動プロファイルは、１つ〜４つの二次曲線の連結である。例えば、水平方向の運動のみを検討する。候補トラバースが、左方向に向かって切断を出るが、次いで右方向に切断に入ることを含む場合、トラバースコストは、完全に減速し、次いで、次の切断に向けて右方向に最大限に加速する（場合によっては切断速度に一致するように減速する）ための時間である。このように、水平運動の最小総時間は、二次方程式を解くことによって得られる。一般的に、２Ｄ軌道は、８度未満の曲線である。
【００５９】
軌道を表すトラバースエッジが、その対応するコストとともに、ＴＳＰグラフに加えられる。軌道のコストは、その時間、距離、エネルギー等の任意の関数として求めることができる（４４５）。入口ノードおよび出口ノードの対を接続する複数のトラバースエッジが存在することができる。
【００６０】
軌道および軌道の対応するコストが求められた後、全ての入口ノードおよび出口ノード、切断エッジ、並びにトラバースエッジによって形成されたグラフにＴＳＰソルバが適用される（４５０）。切断エッジは、強制的に解に入れられ（４５５）、ＴＳＰソルバは、ツアーを完結させるトラバースエッジの部分集合を求める（４６０）。幾つかの実施の形態では、完全なツアーは、精緻化され、動的に最適なツアー４７０を求める機械命令に変換される（４６５）。
【００６１】
図５は、例示的なＴＳＰグラフの一部の図を示している。ここで、グラフのノードは、輪郭上の入口点および出口点を表し、切断エッジは、隣接ノード間の輪郭に沿った切断を表し、トラバースエッジは、異なるカット輪郭上のノード間の動的に最適な軌道を表す。線５１０および５２０等の太線は、必須の切断を表すエッジである。これらの切断は、セグメントに分割される。小さな白丸、例えば、５３０および５３５は、セグメントを形成する入口点または出口点を表す。輪郭がどこで分割されようと、同じロケーションに位置する入口ノードおよび出口ノードを表す２つの白丸が存在する。破線の矢印５４０および５４５は、２つの出口速度ベクトルを表す。各速度ベクトルは、速度の大きさおよび方向を含む。全ての入口点または出口点は、そのようなベクトルを有するが、図において、混乱を減らすために、２つのみが示される。点線、例えば、線５５０および５５５は、正方形の右下側の角における単一の出口点からの候補トラバース軌道の例である。
【００６２】
図６は、図２のパターン２００の一部について求められたツアー６００の例を示している。ツアーは、本発明の様々な実施の形態によって求めることができ、機械の速度制限および加速度制限等の、機械の動力学の影響を受けやすい。セグメント６１０は、対応する出口点６２０および入口点６３０において、非ゼロ速度を有する異なる輪郭間の動作を表す軌道の例である。
【００６３】
非フライゾーン
幾つかの状況では、最適なトラバース軌道は、「非フライゾーン」、すなわち、パターンに従って交差の影響を受けやすい工作物の部分に交差する。場合によっては、そのような交差は、除去部分とツールヘッドとの衝突につながる可能性があるので望ましくない。例えば、図７（Ａ）に示すように、以前に切断された特徴７００が、ロケーション７０１から、切断される別の輪郭７１１のロケーション７０９までの単一の軌道７１０によって交差される可能性がある。幾つかの実施の形態では、そのような軌道は、排除または修復される。
【００６４】
例えば、図７（Ｂ）に示すように、軌道は、単一の軌道７１０から、特徴の外形を辿る一連のセグメント７０１〜７０９に変換される。この軌道は、
（１）元の急速な横方向の動き７１０について、特定の特徴の入口ロケーション７０２および出口ロケーション７０８をマーキングすることと、
（２）入口ロケーションと出口ロケーションとの間で特徴を迂回して進む最も短い方向を求めることと、
（３）特徴の辿られた外形を含む切断の動きを模倣する一連の短いセグメントによって元の高速な横方向の動き７１０を置き換えることと、
（４）これらのセグメントを特徴境界から離れるように拡張し、カッターヘッドと以前に切断された特徴との間に衝突が生じ得ないことを確保することと、
によって構築することができる。
【００６５】
しかしながら、上記の戦略によって生成された軌道は、複数の唐突な動きを含む可能性があるので、以前に切断された特徴に交差することを回避する最適な動きではない場合があり、動的に最適でない場合がある。
【００６６】
図７（Ｃ）に示すように、別の戦略は、ロケーション７０１、７０４、７０６、および７０９のみを用いるようにして、一連の短いセグメントを取り除く。特徴を回避するのに必要なロケーションのみが保持される。
【００６７】
これは、出口点７０１の観点から開始し、非フライゾーンの境界上の最も左の可視点７０４を選択し、次いで、その点７０４の観点から、非フライゾーンの境界上の最も左の可視点７０６を再び選択し、このプロセスを、入口点７０９の遮るものがないビューを有する点に達するまで繰り返し、これらの全ての点７０１、７０４、７０６、７０９をトラバースのテンプレートとしてとることによって、達成することができる。次いで、テンプレートは、非フライゾーンから離れるように拡張され、次いで、７０４から７０６までの拡張された経路の左側に留まりながら、正しい端点速度で７０１を７０９と接続する動的に最適な軌道７１２が解かれる。代替的に、同じ手順によって、非フライゾーンの右側のルートをとることができる。
【００６８】
別の実施の形態は、ＴＳＰグラフを用いて軌道を修復する。例えば、１つの実施の形態は、軌道が、非フライゾーンの境界の外側の点、例えば、点７０４を通過するという追加の制約を用いて最適運動問題を解き直すことによって、軌道を修復する。修復された軌道も、非フライゾーンを通過する場合、さらなるそのような制約点が加えられ、再び問題が解き直される。
【００６９】
非ローカルトラバースを表すトラバースエッジ、例えば、各内部ノードから最も外側の切断におけるノードへのトラバース、または、さらにはランダムに選択されたノード間の少数のトラバースも、グラフに加えることができる。これらのエッジは、ＴＳＰ問題に対する自由度を付加し、これによって、さらなる計算が必要となることと引き換えに、より効率的な計画を見つけることが可能になる。
【００７０】
ＴＳＰソルバは、グラフを通る最低コスト、またはほぼ最低コストのツアーを求める。このツアーのエッジによって表される切断およびトラバースは、切断ヘッドの動的に最適な大域軌道を含む。
【００７１】
調整
トラバース軌道のコストに様々な優先度を符号化することができる。例えば、閉じた輪郭内の全てのセグメントが単一の運動において切断されることが好ましい場合、これらのセグメントに出入りするトラバースを表すトラバースエッジと関連付けられた全てのコストに、正の値が加えられ、これによって、複数の入口および出口が阻止される。カッターが、他の切断を行うように離れるのではなく、角を回る切断輪郭を辿ることが好ましい場合、トラバースエッジを付加することができ、このトラバースエッジのコストは、２つの隣接する切断を低速化して、角を正確に回る時間コストまたはエネルギーコストを反映する。
【００７２】
一組の入れ子構造の切断が与えられるとき、多くの場合に、内側の切断が外側の切断の前に行われることが好ましい。幾つかのＴＳＰソルバは、ノードがツアー内に現れる順序に対する制約に適応することができる。代替的に、幾つかの実施の形態は、包囲する切断が、その内部に入れ子になった切断の前に完了する場合のＴＳＰ解を調べる。ＴＳＰ解が見つかった場合、入れ子になった切断が包囲する切断上を最後にフライオーバーしたときについて、ツアーを調べ、この時点において、前の包囲する切断は、材料のタブがこの最後のフライオーバー中に切断されるように残されるよう変更される。閉じた曲線が１つの運動で切断されるという要件を有する実施の形態では、ＴＳＰグラフは、それぞれ独立して解かれる入れ子構造のグラフに分割され、次いで、内側から外側の順に切断される。
【００７３】
幾つかの実施の形態は、ツアー内の軌道のシーケンスを求めた後、様々な方法で解を精緻化する。例えば、入口点および出口点ごとに、（同じ切断輪郭上の）一組の近傍の代替点が検討される。ＴＳＰによって求められた切断のシーケンスを用いて、動的計画法により、ここでもトラバース軌道コストをエッジ重みとして用いて、代替点の大域的に最適なツアーを効率的に特定することができる。
【００７４】
ＴＳＰ解によって切断ヘッドの動的に最適なツアーが求められた後、実施の形態は、切断機械の制御装置への一組の命令を求める。幾つかの制御装置は、線分および場合によっては円弧のシーケンスを処理するのみでよく、したがって、１つの実施の形態では、ＴＳＰ解によって選択された軌道は、これらの幾何プリミティブのシーケンスによって近似される。これらのプリミティブを曲線にあてはめる際、曲線を過度に粗くサンプリングすること（これによって、運動誤差が生じる）と、曲線を過度に精密にサンプリングすること（これによって、制御装置に過負荷がかかり、機械全体が低速化する）との間のトレードオフが存在する。１つの実施の形態は、制御装置に過負荷をかけない最も細かいサンプリングレートでプリミティブを貪欲に求めるが、この実施の形態は、準最適である可能性がある。代替的な実施の形態は、プリミティブの過剰完全な集合を軌道の曲線にあてはめ、曲線の全ての部分が複数の重複するプリミティブによってカバーされるようにする。次いで、動的計画法または他の解決法を用いて、制御装置に過負荷をかけることなく曲線を最良に近似する、あてはめられたプリミティブの部分集合を求める。
【００７５】
本発明の上述した実施の形態は、数多くの方法のいずれにおいても実施することができる。例えば、実施の形態は、ハードウェア、ソフトウェアまたはそれらの組合せを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピューターに設けられるのか、または複数のコンピューター間に分散されるのかにかかわらず、任意の適したプロセッサまたはプロセッサの集合体において実行することができる。そのようなプロセッサは、１つまたは複数のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。
【００７６】
さらに、コンピューターは、ラックマウント型コンピューター、デスクトップコンピューター、ラップトップコンピューター、ミニコンピューターまたはタブレットコンピューター等の複数の形態のいずれにおいても具現化できることが理解されるべきである。また、コンピューターは、１つまたは複数の入力デバイスおよび出力デバイスを有することもできる。これらのデバイスは、中でも、ユーザーインターフェースを提示するのに用いることができる。ユーザーインターフェースを提供するのに用いることができる出力デバイスの例には、出力を視覚提示するためのプリンターまたは表示スクリーン、および出力を可聴提示するためのスピーカーまたは他の音発生デバイスが含まれる。ユーザーインターフェースに用いることができる入力デバイスの例には、キーボード、並びにマウス、タッチパッドおよびデジタイジングタブレット等のポインティングデバイスが含まれる。別の例として、コンピューターは、音声認識を通じて、または他の可聴フォーマットで入力情報を受け取ることもできる。
【００７７】
そのようなコンピューターは、ローカルエリアネットワークまたはワイドエリアネットワークとしてエンタープライズネットワークまたはインターネット等を含む１つまたは複数のネットワークによって、任意の適した形態で相互接続することができる。そのようなネットワークは、任意の適した技術に基づくことができ、任意の適したプロトコルに従って動作することができ、無線ネットワーク、有線ネットワークまたは光ファイバーネットワークを含むことができる。
【００７８】
また、本明細書において概説される様々な方法またはプロセスは、様々なオペレーティングシステムまたはプラットフォームのうちの任意のものを用いる１つまたは複数のプロセッサに対して実行可能なソフトウェアとして符号化することができる。加えて、そのようなソフトウェアは、複数の適切なプログラミング言語および／またはプログラミングツール若しくはスクリプティングツールのうちの任意のものを用いて書くことができ、フレームワークまたは仮想マシン上で実行される実行可能な機械語コードまたは中間コードとしてコンパイルすることもできる。これに関して、本発明は、単数のコンピューター可読記憶媒体または複数のコンピューター可読媒体、例えば、コンピューターメモリ、コンパクトディスク（ＣＤ）、光ディスク、デジタルビデオディスク（ＤＶＤ）、磁気テープ、およびフラッシュメモリとして実現することができる。代替的にまたは付加的に、本発明は、伝播信号等の、コンピューター可読記憶媒体以外のコンピューター可読媒体として実施することもできる。
【００７９】
コンピューター実行可能命令は、１つもしくは複数のコンピューターまたは他のデバイスによって実行される、プログラムモジュール等の多くの形式をとることができる。一般に、プログラムモジュールは、特定のタスクを実行するか、または特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造を含む。通常、プログラムモジュールの機能は、様々な実施の形態において所望に応じて組み合わせることも分散することもできる。
【００８０】
また、本発明の実施の形態は、例が提供された方法として実施することができる。方法の一部として実行される動作は、任意の適切な方法で順序付けすることができる。したがって、動作が示したものと異なる順序で実行される実施の形態を構築することができ、これには、例示の実施の形態では一連の動作として示されたにも関わらず、幾つかの動作を同時に実行することを含めることもできる。
【図１Ａ】
0005897151.tif 000003
【図１Ｂ】
0005897151.tif 000004
【図２】
0005897151.tif 000005
【図３】
0005897151.tif 000006
【図４Ａ】
0005897151.tif 000007
【図４Ｂ】
0005897151.tif 000008
【図５】
0005897151.tif 000009
【図６】
0005897151.tif 000010
【図７】
0005897151.tif 000011