JP2001249961A

JP2001249961A - アセンブリワークセルをレイアウトするための最適化ツール

Info

Publication number: JP2001249961A
Application number: JP2000358545A
Authority: JP
Inventors: David Barral; バラールダビッド
Original assignee: Dassault Systemes SE
Current assignee: Dassault Systemes SE
Priority date: 1999-11-24
Filing date: 2000-11-24
Publication date: 2001-09-14
Anticipated expiration: 2020-11-24
Also published as: EP1107082A3; CA2325005A1; EP1107082A2; JP3604005B2; US6470301B1

Abstract

(57)【要約】【課題】産業用ロボットのＣＡＤ／ＣＡＭ／ＣＡＥソ
フトウェア製品のコンテキストにおいて、アセンブリワ
ークセルレイアウトを最適化するための方法およびシス
テムを提供する。【解決手段】最小化される基準は、所与の作業シーケ
ンス（５２）を完了するサイクル時間であり、これはワ
ークセルフロア上の周辺機器の相対的位置を決定するこ
とで達成される。この方法は構成的なものであって、修
正された模擬アニーリング方法を用いて、各機械がロボ
ットの近隣に１回に１つずつ配置される。この方法は、
１つの機械についていくつかの可能な位置および最適な
位置を導き出すため、実行の終わり（６５）にはいくつ
かのレイアウトが得られる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、コンピュータソフ
トウェアユーティリティプログラムに関する。さらに詳
細には、コンピュータ援用設計（ＣＡＤ）、コンピュー
タ援用製造（ＣＡＭ）、およびコンピュータ援用エンジ
ニアリング（ＣＡＥ）の分野におけるプログラムに関
し、具体的に言えば、製造設備内でロボットおよび機械
の適切な物理的位置を決定するためにこのようなシステ
ムを使用することに関する。

【０００２】

【従来の技術】従来、ロボットは、自動化された製造プ
ロセスで広く使用されている。ロボットを使用すると、
精密で時間効率の高い方法で反復性のタスクを実行する
ことができる。たとえばロボットを、自動車の骨組をス
ポット溶接するための自動車製造ライン内で使用する
と、手作業を利用して達成するよりも、時間効率の高い
方法で、溶接部分を精密に配置することができる。他の
例では、ワークセル内に配置され、その周囲を他の機械
で囲まれたロボットは、ワークセル環境内の様々な周辺
機械から部品を取得し、作業端末でその様々な部品を組
み立てることによって製品を作成する。典型的な製造プ
ロセスでは、ロボットは２地点間を移動する反復性のシ
ーケンスを実行し、各地点で停止する。たとえば、ロボ
ットは、プログラムされたそれぞれの停止位置でアセン
ブリにスポット溶接を行う。他の例では、ロボットは組
立作業において、実行される組立タスクによって指示さ
れる作業シーケンスで、１つの周辺機械から次の機械ま
で移動する。

【０００３】ロボットの生産性は、１つの作業シーケン
スを完了するためのサイクル時間を最小限にすることに
よって、かなり向上させることができる。所与のロボッ
トの場合、サイクル時間は、タスクに関するロボットの
マニピュレータ（ｍａｎｉｐｕｌａｔｏｒ）ツールの位
置、ポイントへの移動シーケンス、アクチュエータの最
高速度および加速度、ポイントの相対的位置、ならびに
ロボットアームの構成など、多くのパラメータによって
決まる。また、ロボットがアクセスするポイントの相対
的位置によって、すなわちワークセルレイアウトによっ
ても決まる。作業端末で誤って配置されたロボットは、
十分な作業効率が得られず、障害を起こす危険性さえあ
る。したがって、指定の作業シーケンスに対するサイク
ル時間を最小限にできるように、システム用のロボット
および周辺機械の位置を選択する必要がある。

【０００４】既存のＣＡＤシステムを使用して、ロボッ
トを含む製造設備をモデリングすることができる。この
ようなＣＡＤシステムが、ロボットの構成およびワーク
セル内の周辺機器の構成を詳述したデータを備えている
場合、ワークプレースをモデリングするのに使用され
る。各アイテムは設備をモデリングするためにワークセ
ル内部に配置し、次いで周辺機械はタスクの実行可能性
および有効性を調べるために移動することができる。た
だし、これまで業界でロボットワークセルの設計用に使
用された設計プロセスには、ユーザが実行しなければな
らない何らかの対話式チェックおよび変更ループが含ま
れている。このようなプロセスは時間がかかり、レイア
ウトの品質は人間の設計者に大幅に依存するものであ
る。

【０００５】ワークセル用に一体化された設計プロセス
を実現させるためには、ＣＡＤ／ＣＡＭ／ＣＡＥシステ
ムでサイクル時間を短くするようにロボットおよび周辺
機械の位置を最適化するための、自動レイアウトプラン
ニングツールが必要である。

【０００６】

【発明が解決しようとする課題】従来のシステムには上
述したような種々の問題があり、さらなる改善が望まれ
ている。

【０００７】本発明は、このような問題に鑑みてなされ
たもので、その目的とするところは、ロボットおよび周
辺機械からなるロボットアセンブリワークセルのレイア
ウトを効率的な方法で見つけるためのシステム、方法、
および装置を提供することにある。

【０００８】

【課題を解決するための手段】したがって、本発明は、
ロボットおよび周辺機械からなるロボットアセンブリワ
ークセルに最適またはほぼ最適なレイアウトを効率的な
方法で見つけるためのシステム、方法、および装置を提
供する。最適なレイアウトは、作業シーケンスを最低時
間内で処理できるようにする、ワークセル（ワークスペ
ース）内のロボットおよび周辺機械の配置として定義さ
れる。

【０００９】本発明は、完全な解が得られるまで、変数
のステップごとのサブセットをセットアップすることで
構成される、「構成アルゴリズム」技法を使用する。も
ちろん、ワークセル内に配置されるアイテムは、作業に
関与するロボットおよび各周辺機械である。本発明の一
態様によれば、ワークセルをレイアウトする問題は、第
１に、ロボットおよび第１の周辺機械をワークセル内に
配置することから着手される。その後、ワークセル内に
配置する第２の周辺機械が選択される。本発明の一態様
によれば、修正された「模擬アニーリング」方法を使用
して、ワークセルのフロア上に、第２の周辺機械を配置
することができるロケーションセットを見つける。修正
された模擬アニーリング方法は、ワークセル内でロボッ
トと周辺機械とが対話する時間（サイクル時間）を最小
限にするようなロケーションを見つける。

【００１０】本発明の修正された模擬アニーリング方法
は、最適に近い第２の周辺機械用の配置セットを導き出
す。すなわち、検索で見つけられたロケーションの中に
絶対的に最適なものがなくてもよい（ただし、解の１つ
は絶対的に最適である可能性がある）。それにもかかわ
らず、この方法によって見つけられたロケーションは、
周辺機械を配置するのに最適に近いロケーションを表
す。本発明によれば、修正された模擬アニーリング方法
は多くの配置問題を生み出す可能性はあるが、（サイク
ル時間に関して）最高のロケーションのみが維持されて
引き続き評価される。模擬アニーリング方法によって生
成されたロケーションの残りは、考慮の対象から外され
る。本発明の好適実施形態によれば、最良のロケーショ
ンが５つだけ選択される。したがって、引き続き評価す
るための部分レイアウトセットは、５つの部分レイアウ
トからなり、それぞれがそのオリジナルロケーション内
にロボットおよび第１の機械を有し、さらにワークセル
フロア上の特有ロケーションに第２の周辺機械を有する
ことになる。

【００１１】修正された模擬アニーリング方法は、新し
い機械が追加されたときに、維持されたそれぞれの部分
レイアウトに対して実行される。したがって、本発明の
一態様によれば、第３の周辺機械が配置用に選択され
る。その後、第３の周辺機械に可能な配置セットを見つ
けるために、本発明の修正された模擬アニーリング方法
を使用して、部分レイアウトセット内の各部分レイアウ
トが検索される。この検索プロセスが、５つの維持され
た部分レイアウトそれぞれに対して、ロボット、第１の
２つの周辺機械、および第３の機械を含む、新しい部分
レイアウトのセットを導き出す。この検索は、５つの維
持された部分レイアウトそれぞれに対して行われるの
で、第３の周辺機械を含むレイアウトが多数生成され
る。ただし、本発明の一態様によれば、ここで再度、最
高の部分レイアウトだけが引き続き評価するために選択
され、残りは考慮の対象から外される。本発明の好適実
施形態にしたがって、部分レイアウトはいくつでも選択
できると考えられるが、ユーザが望むかまたはＣＰＵ時
間の実行可能性によって指示されるように、最高の部分
レイアウトが５つだけ選択される。

【００１２】前述のプロセスは、すべての周辺機械がワ
ークセル環境内に配置されるまで繰り返される。

【００１３】本発明の他の態様によれば、第１の周辺機
械は「受け入れ可能ベースロケーション領域」の中央に
配置される。ロボットのアームおよびリストジョイント
部の運動上の制限により、ロボットのマニピュレータツ
ールは、任意の単一ロボットベースロケーションについ
て、その環境内で制限された分散ロケーション数までし
か可能ではない。同様に、ロボットのマニピュレータツ
ールが１つのロケーションに固定されており、そのロボ
ットベースが移動可能である場合、その作業範囲を介し
てロボットのアームおよびリストを動かすと、ワークセ
ルのフロア中をロボットのベースが移動することにな
る。ロボットがその作業範囲全体を移動するときにロボ
ットベースが移動するワークセルフロア上の範囲が、特
定のワークポイントに対して許容可能なロボットのベー
スロケーション領域を確定する。ロボットを許容可能な
ベースロケーション領域の外に配置すると、ロボットは
作業ポイントに届くことができなくなる。

【００１４】本発明の他の態様によれば、周辺機械が評
価される順序は、ほとんどの作業シーケンスでアクセス
される機械を第１の基準として優先し、小型機械を第２
の基準として優先する、機械の選択規則を使用して決定
される。その結果、サイクル時間の最適化が改善され
る。

【００１５】本発明の他の態様によれば、周辺機械の形
状は、模擬アニーリング方法を適用する前に簡略化され
る。その結果、検索の処理時間が高速化される。

【００１６】前述のように、修正された「模擬アニーリ
ング」方法は、サイクル時間を最短化するように周辺機
械を配置するために最適なポジションセットを見つける
のに使用される。この従来の模擬アニーリングアルゴリ
ズムは、当分野の技術者にはよく知られており、たとえ
ば、参照により本明細書に組み込まれている、Ｓ．Ｋｉ
ｒｋｐａｔｒｉｃｋのＣ．Ｄ．Ｇｅｌａｔｔ，Ｊｒ．お
よびＭ．Ｐ．Ｖｅｃｃｈｉによる、「Ｏｐｔｉｍｉｚａ
ｔｉｏｎｂｙＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉ
ｎｇ」，Ｓｃｉｅｎｃｅ，２２０（４５９８），ｐｐ．
６７１−６８０，１９８３年５月、に記載されている。
従来の模擬アニーリングアルゴリズムは、問題に対して
１つの独立した最適な解を導き出すだけであり、産業用
ＣＡＤシステムのコンテキストで使用するには不満足な
ものである。さらに模擬アニーリングには、局所極小
（ｌｏｃａｌｍｉｎｉｍｕｍ）の最下位までたどり着
かない限り、通常の解と局所極小とを区別することがで
きないため、長い計算時間が必要となる場合がある。本
発明によれば、従来の模擬アニーリング方法には、この
方法に何らかの「便宜主義（ｏｐｐｏｒｔｕｎｉｓ
ｍ）」を構築するために、２つの機能が追加された。

【００１７】第１の機能は、ローカル検索手順の規則的
な適用に対応する、「フリーズヒート（ｆｒｅｅｚｅ−
ｈｅａｔ）」サイクルと呼ばれるサイクルを使用するこ
とである。この機能の目的は、できる限り迅速に最小の
谷（ｖａｌｌｅｙ）を探索することであり、検索スペー
ス内で最も近い局所極小を導き出す。第２の機能は、局
所極小およびその「誘引領域」を記憶することである。
この方法では、いったん探索した最小の谷には二度と訪
れることがなく、他の最小を得ることができる。このよ
うに修正すると、実行の終わりに、最適に近い解のセッ
トとそれぞれの近隣に関する知識とが一緒に導き出され
る。この修正を使用すると、ロボットベースの単一の絶
対的に最適なロケーションが見つけ出されるという保証
はない。その代わりに、従来の模擬アニーリング方法で
は必要であった計算リソースをほとんど使用せずに、最
適に近い解セットが得られる。

【００１８】

【発明の実施の形態】以下、図面を参照して本発明の実
施形態を詳細に説明する。なお、各図面において同様の
機能を有する箇所には同一の符号を付し、説明の重複は
省略する。

【００１９】図１は、本実施形態に使用可能なコンピュ
ータシステム１００の物理的なリソースを示す。コンピ
ュータ１００は、データ、アドレス、および制御信号を
提供するプロセッサホストバス１０２に接続されたＣＰ
Ｕ１０１を備える。プロセッサ１０１は、Ｐｅｎｔｉｕ
ｍ（登録商標）シリーズのプロセッサ、Ｋ６（商標）プ
ロセッサ、ＭＩＰＳ（登録商標）プロセッサ、Ｐｏｗｅ
ｒＰＣ（登録商標）プロセッサ、またはＡＬＰＨＡ
（登録商標）プロセッサなどの、どんな従来型汎用シン
グルチップまたはマルチチップのマイクロプロセッサで
もよい。さらにプロセッサ１０１は、デジタル信号プロ
セッサまたはグラフィックスプロセッサなどの、どんな
従来型専用マイクロプロセッサでもよい。マイクロプロ
セッサ１０１は、従来のアドレス、データ、およびこれ
をプロセッサホストバス１０２に結合する制御ラインを
有することができる。

【００２０】コンピュータ１００は、一体型ＲＡＭメモ
リ制御装置１０４を備えるシステム制御装置１０３を含
むことができる。システム制御装置１０３はホストバス
１０２に接続し、ランダムアクセスメモリ１０５へのイ
ンタフェースを提供することができる。システム制御装
置１０３は、ホストバスから周辺バスへのブリッジング
機能を提供することもできる。これによって制御装置１
０３は、プロセッサホストバス１０２上の信号と１次周
辺バス１１０上の信号とを、整合性を持たせて交換する
ことができる。たとえば周辺バス１１０は、ＰＣＩ（pe
ripheral component interconnect）バス、ＩＳＡ（ind
ustrial standard architecture）バス、またはマイク
ロチャネルバスであってもよい。さらに制御装置１０３
は、ホストバス１０２と周辺バス１１０との間で一致し
た、データバッファリングおよびデータ転送速度を提供
することができる。これによって制御装置１０３は、た
とえば、インタフェースが６４ビット６６ＭＨｚでデー
タ転送速度が５３３Ｍバイト／秒のプロセッサ１０１
を、データパスのビット幅、クロック速度、またはデー
タ転送速度が異なるデータパスを有するＰＣＩバス１１
０にインタフェースさせることができる。

【００２１】たとえばハードディスクドライブ１１３に
結合されたハードディスクドライブ制御インタフェース
１１１、ビデオディスプレイ１１５に結合されたビデオ
ディスプレイ制御装置１１２、ならびにキーボードおよ
びマウス制御装置１２１を含むアクセサリデバイスを、
バス１２０に結合し、プロセッサ１０１によって制御す
ることができる。コンピュータシステムは、コンピュー
タシステムネットワーク、イントラネット、またはイン
ターネットへの接続を含むことができる。こうした接続
を介して、データおよび情報を送受信することができ
る。

【００２２】コンピュータ１００は、基本的なコンピュ
ータソフトウェアルーチンを格納するために、不揮発性
ＲＯＭメモリ１２２を含むこともできる。ＲＯＭ１２２
は、構成データを格納するために、ＥＥＰＲＯＭ（elec
trically erasable read-only memory）などの変更可能
メモリを含むことができる。ＲＯＭ１２２にＢＩＯＳル
ーチン１２３を含めて、基本的なコンピュータの初期設
定、システムテスト、および入力／出力（Ｉ／Ｏ）サー
ビスを提供することができる。ＢＩＯＳ１２３は、オペ
レーティングシステムをディスク１１３から「ブート」
できるようにするルーチンを含むこともできる。高水準
オペレーティングシステムの例には、Ｍｉｃｒｏｓｏｆ
ｔＷｉｎｄｏｗｓ９８（商標）、Ｗｉｎｄｏｗｓ
ＮＴ（商標）、ＵＮＩＸ（登録商標）、ＬＩＮＵＸ、Ａ
ｐｐｌｅＭａｃＯＳ（商標）オペレーティングシステ
ム、または他のオペレーティングシステムがある。

【００２３】オペレーティングシステムは、ＲＡＭメモ
リ１０５内に完全にロードするか、またはＲＡＭメモリ
１０５、ディスクドライブ格納装置１１３、またはネッ
トワークロケーションにある格納装置に部分的に含める
ことができる。オペレーティングシステムは、ソフトウ
ェアアプリケーション、ソフトウェアシステム、および
ソフトウェアシステムのツールを実行する機能を提供す
ることができる。ソフトウェア機能は、ビデオディスプ
レイ制御装置１１２およびコンピュータシステム１００
の他のリソースにアクセスして、設計のモデル、ロボッ
ト構成、ワークスペース、およびワークプレース環境を
ビデオコンピュータディスプレイ１１５上に提供するこ
とができる。

【００２４】アセンブリワークセルレイアウトの問題お
よび仮定アセンブリワークセルレイアウトの問題は、ロボットの
近隣にあり、ロボットが対話する周辺機械の相対的位置
を決定することに関係する。その目的は、１つまたは複
数のワークセルの有効性基準を最適化することである。
本実施形態によれば、最適化のために満たさなければな
らない１つの基準、すなわちアセンブリタスクに対応す
るサイクル時間が考慮された。工業用ＣＡＤ／ＣＡＭ／
ＣＡＥシステムでは、このような基準を算出するのに必
要な努力がかなりの量にのぼる。実際、制御装置の製造
業者がそのロボットに関して独自のシミュレーションモ
ジュールを提供しているように、各評価はロボットの動
きのシミュレーションを意味する。

【００２５】以下の要素の場合、考慮する必要がある。

【００２６】１．機械の形状が不揃いの可能性がある。
この場合、ロボットを基準にした機械の向きで可能な数
を制限する表現方法を見つける問題、および機械の重な
りを効率的に検出する問題が発生する。

【００２７】２．各機械が、少なくとも１つのアクセス
／送達ポイントを有し、ロボットは機械に関連付けられ
たタスクを実行するためにこのポイントに届かなければ
ならない。

【００２８】３．機械は、機械間で保守、修理、および
オペレータの動作が行えるだけの十分なスペースをとら
なければならない。このゆとりは機械によって異なる場
合がある。

【００２９】４．アセンブリタスクには、２つ以上のロ
ボットが必要となる場合がある。

【００３０】５．機械のアクセス／送達ポイントをロボ
ットのワークスペース内に配置し、ロボットはこれに届
かなければならない。

【００３１】６．ロボットのベースは移動可能であって
もよい。移動ロボットの場合は、機械の間に動き回る余
分なスペースが必要である。

【００３２】一般的なアセンブリワークセルのレイアウ
ト問題は非常に複雑で組み合わされたものである。した
がって、以下のような道理にかなった実践的な、何らか
の簡略化および仮定が実行される。

【００３３】１．ワークセルは、ベースが固定された１
つのロボットおよび周辺機械のセットからなる。

【００３４】２．アセンブリタスクに関連付けられた作
業シーケンスが決定される。

【００３５】３．考慮の対象となる機械のタイプおよび
形状は限定されていない。

【００３６】４．機械にはアクセス／送達ポイントが１
つだけある。ほとんどの機械にこのようなポイントが１
つしかない場合、この仮定は道理にかなっている。機械
上でのアクセスポイントの位置は、機械の「中央」に限
定されていない。

【００３７】５．機械の間にあるスペースのゆとりは、
ユーザによって与えられるものである。機械の内部表現
は、スペースのゆとりを考慮に入れて決められる。

【００３８】６．レイアウトに使用できるフロアスペー
スは、制限されないものと仮定される。使用可能なフロ
アスペースに合わせて機械をわずかに移動させても、結
果にはほとんど影響を与えない。さらにレイアウトは、
所与のフロア領域に適合させるために、全体として表示
することができる。

【００３９】実用的および工業的なケースに対して信頼
できる解を提供するために、以下の制約を考慮に入れな
ければならない。

【００４０】１．機械のアクセスポイントのアクセス可
能度。

【００４１】２．作業が実行されるポイントにロボット
ツールが届く場合、ロボットとその環境との間の衝突回
避。

【００４２】３．ロボットアームがアクセスポイント間
を移動する場合、ロボットとその環境との間の衝突回
避。

【００４３】最終的に、ユーザによって、アセンブリロ
ボットモデル、これと対話する機械、および実行される
アセンブリタスクに対応する作業／対話シーケンスとい
う、初期データが提供される。

【００４４】ワークセルレイアウト解法ロボットが所与のアセンブリタスクを実行するための全
サイクル時間は、周辺機械など、その環境内でのオブジ
ェクトに対する位置によって決まる。ワークスペースの
配置が良くないと、作業効率が悪くなる。これが、特定
のタスクが実施される間にマニピュレータの性能が最適
化されるような方法で、レイアウトを選択する際の問題
につながる。

【００４５】既存のロボットＣＡＤシステムでは、サイ
クル時間を最適化するためのプロセスは非常に時間がか
かる作業である。本実施形態によれば、このタスクは、
周辺機械がワークスペースに１つずつ加えられる構成ア
ルゴリズム方法を使用することによって、より効率的に
なっている。周辺機械が追加されるごとに、修正された
模擬アニーリング方法を使用して、新しい周辺機械を含
む可能なレイアウトセッが決定される。最高のレイアウ
トだけが引き続き評価するために受け入れられる。この
方法は、ＣＰＵ時間を削減するためにロボットおよび周
辺機械の幾何形状を簡略化することによって能率的にな
る。さらにこの方法は、アセンブリプロセスでしばしば
アクセスされる周辺機械を優先すること、および小型の
機械を優先することによって決定される特有の順序で周
辺機械を追加することによって能率的になり、その結
果、しばしばアクセスされる機械がロボットの近くに配
置され、小型の機械はロボットの周囲に、その周辺に大
型の機械が集められることになる。

【００４６】図２を参照すると、本実施形態の方法の概
略図が示されている。システムは、特有のロボットモデ
ルの幾何形状５０、各周辺機械の幾何形状５１、および
アセンブリ作業シーケンス５２に関して、システム内部
またはシステム外部のいずれかに格納されたデータを使
用する。ステップ５３では、本明細書で詳細に記述され
る「ランク表」が計算される。このランク表の情報を使
用して、サイクル時間が計算される。これは、ロボット
が特定の機械にアクセスする回数、および機械間での移
動回数を記録する。ステップ５４では、周辺機械がワー
クセル内に配置される順序が決定される。好適実施形態
では、機械の配置シーケンスは、ランク表からの情報な
らびに周辺デバイスの構成に関する情報を使用して、下
記のように決定される。

【００４７】ステップ５５では、ロボットがワークスペ
ース内に配置され、第１の周辺機械は、ロボットがアク
セスしやすいようにロボットの近くに配置される。この
構成は、「ａ₀」と明示された第１のレイアウトとして
明示される。ステップ５６では、カウンタであるパラメ
ータ「ｉ」および「ｊ」が値１に初期設定される。下記
のように、値「ｉ_max」は加えられる機械の合計数に対
応し、値「ｊ_max」は下記のように機械が追加されると
きに評価されるレイアウト数に対応する。パラメータ
「ａ」は個々のレイアウトを明示し、パラメータ「Ａ」
は機械「ｉ」の全レイアウトセットである。

【００４８】したがって、プロセスを続行していくと、
次にサイクル時間が最小になるような方法で、第２の周
辺機械をワークセル内に配置することが望まれる。本実
施形態によれば、下記に記載する修正された模擬アニー
リング方法を使用して、第２の周辺機械について可能な
配置セットが生成される。修正された模擬アニーリング
方法が生成する可能性のある可能なロケーション数は、
任意に制限されるものではない。この方法は、ワークス
ペースの構成およびワークスペース内にある他のオブジ
ェクトに応じて、２、３の配置だけを生成するか、また
は多数の配置を生成することができる。例示の目的で１
５の可能な配置が生成されると仮定すると、それぞれの
配置が１５の部分レイアウトのうちの１つを定義し、ロ
ボットおよび第１の機械は同じ場所にあるが、第２の機
械は異なる場所にある。１５の部分レイアウトは、第２
の機械に対応する部分レイアウトセット「Ａ」内に配置
される（ステップ５８）。プロセスはステップ５９へ進
み、ここではパラメータ「ｊ」が「ｊ_max」に等しいか
どうかに関する照会が実行される。パラメータ「ｊ」は
ステップ５６で値１に初期設定されたカウンタであり、
パラメータ「ｊ_max」は評価の基準として使用されてい
る現在の部分レイアウト数であることを想起されたい。
この段階で、現在の部分レイアウトは１つしかない、す
なわちロボットおよび第１の機械を備えた１つのレイア
ウトしかないので、「ｊ_max」は値１を有する。したが
って、ステップ５９の照会の答えは「はい」となり、ス
テップ６１に進む。ステップ６１では、修正された模擬
アニーリング方法で生成された１５の部分レイアウトの
サイクル時間が相互に比較され、最高のものだけが選択
される。使用可能なＣＰＵ時間に応じて部分レイアウト
をいくつ選択するかは、ユーザの責任で定義される。好
適実施形態では、最高のレイアウトが５つだけ維持さ
れ、残りは考慮の対象から外される。これで、評価を続
ける部分レイアウトセットには５つの部分レイアウトが
含まれるので、「ｊ_max」の値は５に設定される。機械
番号２の部分レイアウトセットを決定すると、その機械
番号に対応するカウンタ、すなわち「ｉ」は値１だけ進
む（ステップ６２）ので、プロセスを残りの機械にも繰
り返すことができる。

【００４９】ステップ６３に進むと、追加する機械が他
にもあるかどうか（ｉ＝ｉ_maxであるか）に関する照会
が実行される。追加する機械が他にもある場合（ステッ
プ６３で「いいえ」）は、ステップ６４に進み、カウン
タ「ｊ」は値１にリセットされる。次いで、現在の５つ
の部分レイアウトそれぞれに対して、模擬アニーリング
プログラムが実行される。したがって、ステップ５７に
戻り、修正された模擬アニーリング方法が現在の５つの
部分レイアウトのうちの第１を開始し、第３の周辺機械
を含む可能なレイアウトセットを生成する。これらのレ
イアウトはセット「Ａ」に格納され（ステップ５８）、
「ｊ」の値は１、「ｊ_max」の値は５となるので、ステ
ップ５９の照会の答えは「いいえ」となる。「ｊ」の値
はステップ６０で１だけ増え、修正された模擬アニーリ
ング方法が再度実行されて、開始ポイントとして現在の
５つの部分レイアウトのうちの２番目を使用して、第３
の周辺機械を含む可能なレイアウトセットが導き出され
る。このプロセスは、第３の機械の部分レイアウトを生
成するための開始ポイントとして、現在の部分レイアウ
ト５つが全部使用されるまで続行される。この時点で、
値「ｊ」は「ｊ_max」に等しくなり、前述のように好適
実施形態では値５を有し、ステップ５９の照会の答えは
「はい」となる。

【００５０】この段階で機械番号３を含む部分レイアウ
トセットは潜在的に非常に大きくなる可能性がある。た
とえば、現在の５つの部分レイアウトそれぞれについ
て、１５の新しいレイアウトが生成された場合、機械番
号３の部分レイアウトセットには７５の部分レイアウト
が含まれることになる。再度、ステップ６１では、すべ
てのレイアウトが比較され、最高のものだけが維持され
る。残りを消去することによって、処理時間は道理にか
なった限界値に制限される。プロセスは、すべての機械
がレイアウト（ｉ＝ｉ_max）（ステップ６３）内に配置
されるまで繰り返され、この時点でプロセスは終了す
る。プロセスの最後には、ユーザが「ｊ_max」に値５を
選択したと仮定し、ユーザには５つの完全なレイアウト
が提示される。

【００５１】解析の際に考慮の対象とならない要素があ
るために、実際には１つまたは複数のレイアウトが実行
可能であることが証明できないので、複数の解を有する
ことは有利である。さらに、作業環境またはシーケンス
に何らかの変更が加えられ、１つまたは複数の解が発展
不可能となった場合でも、ユーザにはまだ選択する他の
解がある。

【００５２】以上、本実施形態の方法全体について述べ
てきた。次に、本発明の好適実施形態に従った、本実施
形態の修正された模擬アニーリング方法ならびにプロセ
スを最適化するための方法について述べる。

【００５３】作業シーケンスの定義アセンブリタスクに関連付けられた作業シーケンスを記
述するための標準的なＣＡＤ／ＣＡＭ／ＣＡＥツールが
このタスクに適さないため、好適実施形態でユーザが必
要とする対話回数を最小限に抑える、新しいユーザイン
タフェースが設計された。

【００５４】ユーザはこのインタフェースを使用する
と、ロボットのワークスペース内にある作業ポイント間
ではなく、機械間でのロボットの動きを定義することが
できる。具体的に言えば、ユーザが何を「機械間対話」
と呼んでいるかを定義することができる。このような対
話は、ロボットがある要素（ピースまたはツール）を１
つの所与の機械から第２の機械へ運ぶときに発生する。
この点について、ロボットが何も持たずに機械間を移動
する場合の対話は、機械間対話ではないことに留意され
たい。実際、このような対話は以前の対話から推断でき
るので、明示的に指定する必要はない。

【００５５】これは例示的なものとして図示されてい
る。ワークセルは、１つのロボットおよび３つの周辺機
械（機械１、機械２、および機械３）で構成される。実
行されるタスクは、機械１から所与のピースを連続して
２回把持してこのピースを機械２上に配置すること、機
械３にある所与のツールを把持して機械２にあるピース
を組み立てること、およびツールを機械３に戻すことで
ある。

【００５６】ユーザは提案されたインタフェースを使用
して、単に最初および目標の機械名を連続してクリック
し、対話の反復回数を入力することによって、機械間対
話を記述することができる。これらのステップは、機械
１と機械２との間の対話に関して、図３に示されてい
る。図４に示すように、ユーザは対話シーケンスを記述
しながら、これまでに定義した対話をチェックすること
ができる。すべての対話がここに表示される。

【００５７】その後、機械シーケンス（すなわちロボッ
トが機械の場所へ移動しなければならない順序）が対話
シーケンスから直接推断される。これまでに使用した例
では、次のようなシーケンスになる。

【００５８】機械１−機械２−機械１−機械２−機械３
−機械２−機械３次に、サイクル時間を計算するのに使用するランク表が
生成される（図５）。表のｉ，ｉ要素は、ロボットが機
械ｉにアクセスする回数である。表のｉ，ｊ要素および
ｊ，ｉ要素は、順序に関係なく、機械ｉと機械ｊとの間
の移動回数（対話ではない）に対応する。

【００５９】３次元機械表示の簡略化ここで示される２次元の機械内部表示は、最適化中に発
生する非常に多くの衝突計算を簡略化することを目的と
する。これは、任意の直線で囲まれた形状の機械、すな
わち、矩形、Ｌ型、またはＴ型の機械など、いくつかの
低レベル矩形要素（略して矩形）で構成される機械を正
確に記述するものである。円形または多角形などの形状
は、境界を示す矩形で表されるだけである。ほとんどの
機械の形状は直線で囲まれているので、このような近似
も道理にかなっている。

【００６０】第１に、フロアスペース上にある機械の２
次元近似輪郭が以下のように計算され、

【００６１】

【数１】Ｂ＝｛ｂ_i／１≦ｉ≦ｍ｝上式で、ｂ_iは機械ｉの境界を示す矩形であり、ｍは機
械の数である。

【００６２】次に、機械ｉの３次元初期表示からｂ_iを
構成する矩形のセットが以下のように推断され、

【００６３】

【数２】Ｂ_i＝｛ｂ_ij／１≦ｊ≦ｍ_i｝上式で、ｂ_ijは機械ｉの分解された矩形ｊであり、ｍ_i
は機械ｉの分解された矩形数である。

【００６４】区分された各矩形ｂ_ij、ｘ_ij、およびｙ_ij
は、矩形ｂ_ijの中心のｘおよびｙ座標である。矩形ｂ_ij
の幅および長さはｗ_ijおよびｌ_ijである。直線で囲まれ
た機械内にある別々の構成矩形は、ソリッド接続（ｓｏ
ｌｉｄ−ｃｏｎｎｅｃｔｅｄ）されていると想定する
が、これはこれら矩形間のオフセットが一定に維持され
ているという意味である。したがって、配置プロセス中
に、セットＢ_i内にあるすべての矩形ｂ_ij間のオフセッ
トを維持しなければならない。表示を簡単にする目的
で、ｂ_iの中心からｂ_ijの中心までのオフセットｘおよ
びｙを表すために、２つの定数としてｘｏ_ijおよびｙｏ
_ijを与えている。機械ｉの境界を示す矩形ｂ _iの場合、
ｘ_iおよびｙ_iはｂ_iの中心のｘおよびｙ座標である。ｂ_i
の幅および長さはｗ_iおよびｌ_iである。次いで、直線で
囲まれた機械ｉの中心を、それに関係する境界を示す矩
形ｂ_iの中心として定義すること、およびｂ_iからｂ_ijま
でのｘオフセットおよびｙオフセットを、それぞれｘｏ
_ij＝ｘｂ_ij−ｘ_iおよびｙｏ_ij＝ｙｂ_ij−ｙ_iとして定義
することができる。図６は、直線で囲まれた機械とその
区分された矩形セルとの関係を実証するための簡単な例
である。この例で使用されるすべての変数および定数
は、これら表記の関係を例示するためにラベル表示され
たものである。

【００６５】重なり合った機械の検出以前の表示は、重なり合った機械を２次元で検出する、
単純かつ迅速な機能を提供している。実際に、ロボット
のワークセルレイアウト問題に関して探求された解は、
機械の重なりＣ_moがゼロであるという基準の下で、事前
定義されたタスクを達成するのに必要なサイクル時間を
最小限にするためのものである。Ｃ_moは以下のように定
義することができる。

【００６６】

【数３】

【００６７】数式（１）では、重なり距離ｏｄ_ij,klは
ｂ_klとｂ_ijとの間の機械の重なりを符号で表したもので
ある。これは以下のように定義することが可能であり、

【００６８】

【数４】

【００６９】

【数５】

【００７０】上式でｉｄ_ij,klは、機械の重なりを最小
限にするｂ_klとｂ_ijとの間の理想的な最短距離であっ
て、数式（２）で使用される関数ｆ_h（．）は、０〜１
ハードリミットしきい値関数であり、ｘ＞０の場合はｆ
_h（ｘ）＝１、そうでない場合はｆ_h（ｘ）＝０である。

【００７１】ｂ_klとｂ_ijとの間のユークリッド距離ｄ
_ij,klは、以下のように定義され、

【００７２】

【数６】

【００７３】上式で、ｄｘ_ij,kl＝ｘｂ_kl−ｘｂ_ijおよ
びｄｙ_ij,kl＝ｙｂ_kl−ｙｂ_ijはそれぞれ、ｂ_klの中心
からｂ_ijの中心までのｘおよびｙ座標変位として定義さ
れる。図７は、この表示方法を実証するために、単純な
Ｌ型機械および矩形機械を使用した一例である。

【００７４】ワークセルフロアの定義好適実施形態で使用されるワークセルレイアウトの最適
化方法では、各機械の初期配置を計算する必要がある。
この配置では、特に機械の重なりを避けなければならな
い。

【００７５】このような配置を決定するために、Ｂ．
Ｋ．Ａ．ＮｇｏｉａｎｄＫ．Ｗｈｙｂｒｅｗ，「Ａ
ＦａｓｔＳｐａｔｉａｌＲｅｐｒｅｓｅｎｔａｔ
ｉｏｎＭｅｔｈｏｄ」，ＴｈｅＩｎｔｅｒｎａｔｉｏ
ｎａｌＪｏｕｒｎａｌｏｆＡｄｖａｎｃｅｄＭ
ａｎｕｆａｃｔｕｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，８
（２），ｐｐ．７１〜７７、１９９３年で示された「空
間表示方法」から導出されたワークセルフロア表示が使
用された。２次元マトリックスは機械が配置されるごと
に更新され、フロアスペース上での機械の現在のレイア
ウトを表す。マトリックスの第１行および第１列は、レ
イアウトのｘおよびｙ座標に対応する。残りのマトリッ
クスセルには、機械の占有に応じて「０」または「１」
が含まれる（「０」は空きスペースを表す）。

【００７６】図８は、初期フロアスペースの表示方法を
示す図である。初期の２次元マトリックスが、理解しや
すいように概略的な方法で表示されている。前述のよう
に、使用可能なスペースは無限であると仮定されてい
る。

【００７７】例示のために、「機械１」と名付けられ、
寸法がｌ₁＝４０およびｗ₁＝５０の矩形型の機械が、ｘ
₁＝５２０およびｙ₁＝５２０でフロア上に配置されると
仮定する。次いでこの２次元マトリックスは４×４マト
リックスに拡張され、フロアスペースはフロア領域上に
点線で示された９セクションに分割される（図９）。

【００７８】次いで、図１０に示すように、「機械２」
と名付けられ、寸法がｌ₂₁＝３０、ｗ₂₁＝６０、ｌ₂₂＝
４０、およびｗ₂₂＝３０のＬ型機械が、ｘ₂＝３００お
よびｙ₂＝７００で配置された場合、取得されるマトリ
ックスは７×７である。

【００７９】より多くの周辺機械がフロアスペース上に
配置されるに従って、追加情報を収容するために２次元
マトリックスがステップごとに拡張される。機械がフロ
ア上に配置されるときには、空きセルだけが選択され
る。したがってこのフロア表示は、最適化方法が適用さ
れるときに、機械にとって可能な初期位置を決定する迅
速な方法を提供することになる。

【００８０】連続的な機械配置規則前述のように、本実施形態の方法に従って、ワークセル
のレイアウトに周辺機械が１つずつ追加され、各ステッ
プで本実施形態の修正された模擬アニーリング方法を使
用し、追加される機械に最適な配置が見つけられる。機
械はどのような順序でも追加することができる。ただ
し、好適実施形態により、ロボットが最もよくアクセス
する小型の機械が第１にワークセルに追加されると、良
い結果が得られる。ワークセル内に配置される機械を連
続的に選択するために、非常に効率的であることが証明
された、Ｍ．Ｌ．ＴａｙａｎｄＢ．Ｋ．Ａ．Ｎｇｏ
ｉ，「ＯｐｔｉｍｉｓｉｎｇＲｏｂｏｔＷｏｒｋｃ
ｅｌｌＬａｙｏｕｔ」，ＴｈｅＩｎｔｅｒｎａｔｉ
ｏｎａｌＪｏｕｒｎａｌｏｆＡｄｖａｎｃｅｄＭ
ａｎｕｆａｃｔｕｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，１
２（５），ｐｐ．３７７〜３８５、１９９６年で提案さ
れた既存の規則が使用された。

【００８１】配置される第１の機械を選択することは、
後続の機械を選択することとは幾分か異なる。これは機
械の需要、すなわちロボットが機械にアクセスしなけれ
ばならない回数に基づいている。最高需要値を基準とし
て使用する理由は、最も需要の高い機械が、他の機械と
最も多く対話するからである。したがって、これが第１
に配置され、対話の際に使用する他の機械がその周囲に
配置されなければならない。同じ最高需要値を有する機
械が複数存在する場合は、ベース領域が最も小さい機械
が選択されることになる。

【００８２】後続の機械は、以下の基準に従って選択さ
れ、

【００８３】

【数７】

【００８４】上式で、Ｉ_ijは、機械ｉがすでに配置され
た機械ｊと対話する回数（ｉ≠ｊ）、Ｉ_maxjは、機械ｊ
に関連付けられた最大対話値、Ｓ_iは、機械ｉの規準化
されたベース領域、ｎは機械の合計数、ｋはサイズに割
り当てられた重み付け値で０．５に等しい。

【００８５】規準化されたベース領域Ｓ_iは、以下のよ
うに定義され、

【００８６】

【数８】

【００８７】上式で、Ａ_minは、機械間で最小のベース
領域、Ａ_iは機械ｉの領域である。

【００８８】数式（５）および（６）は領域の小さな機
械を好むため、大型機械はワークセルの周囲に配置され
る。

【００８９】機械の配置これまで論じたように、ロボットが第１にワークセル内
に配置される。次いで第１の周辺機械がワークセル内に
配置される。この段階では、ワークスペース内に、第１
の機械に関してロボットの動きに対する障害物となる他
の機械がないため、最適化は実行されない。したがっ
て、第１の機械は単に、ロボットと機械の幾何学的配置
によって決定されるような、ロボットに容易にアクセス
できるロケーションに配置されるだけである。本発明の
好適実施形態に従い、第１の機械は、図１１の項目６０
に示した「許容ベースロケーション領域」の中心に配置
される。Ｄａｓｓａｕｌｔ−Ｓｙｓｔｅｍｅｓ，Ｓｕｒ
ｅｓｎｅｓ，Ｆｒａｎｃｅによって販売されている「Ｃ
ＡＴＩＡ設計およびロボットプログラミング解法（ＣＡ
ＴＩＡＤｅｓｉｇｎａｎｄＲｏｂｏｔＰｒｏｇ
ｒａｍｍｉｎｇＳｏｌｕｔｉｏｎ）」システムの「衝
突テスト」機能など、既存のＣＡＤシステムの標準機能
を使用して、図１１に示すように、許容ロボットベース
ロケーション領域が計算される。

【００９０】ａ）許容ベースロケーション領域図１１および１２を参照すると、許容ベースロケーショ
ン領域を決定する方法が詳細に記載されている。許容ベ
ースロケーション領域とは、その中にロボットベースが
配置されると、ロボットのマニピュレータが所与の作業
ポイントに届く、平面部分のことである。この領域を決
定するには、ロボットの物理的な幾何学および運動学を
考慮しなければならない。この方法は、ワークスペース
内の６次元基準フレーム（ｓｉｘ−ｄｉｍｅｎｓｉｏｎ
ａｌｒｅｆｅｒｅｎｃｅｆｒａｍｅ）に届く所与の
ロボットマニピュレータを物理的に観察することに基づ
いている。現在の（リストに３つの直交交差軸を備えた
６軸の）産業用ロボットでは、主アーム（位置を確定す
る最初の３つの軸、図１２の項目４１、４２、および４
３）とリスト（向きを確定する後の３つの軸）とを別個
のものとして考えることができる。

【００９１】図１２を参照すると、ロボットのベース用
基準フレームとしてＲ_o、ロボットのリスト中心用基準
フレームとしてＲ_p、エフェクタ終端用基準フレームま
たはツール基準としてＲ_e、ならびに届くことのできる
溶接ポイントにリンクされた基準フレームとしてＲ_aを
定義している。Ｒ_oは、Ｒ_eとＲ_aが一致するときに、円
柱座標系（ｒ、θ、ｚ）を使用して、Ｒ_pに関して便利
に参照することができる。

【００９２】この座標系では、３軸の主アームについ
て、以下の数式システムが得られ、

【００９３】

【数９】

【００９４】上式で、ｌ_iはアームのセグメントｉの長
さ、ｑ_iは結合部位ｉの値である。

【００９５】この数式システムを使用して、水平面内
（ｚが定数）でのｒの値を、ｑ₂、ｑ₃、またはｑ₂＋ｑ₃
に応じて解析的に計算することができる。

【００９６】この方法は、第１に次の２つの段階で進行
する。

【００９７】１．制限範囲内（すなわちｑ_2min＜ｑ₂＜
ｑ_2max；ｑ_3min＜ｑ₃＜ｑ_3max）で主アームのジョイン
ト部を走査する（ｓｗｅｅｐ）ことによる、ロボットベ
ースのワークスペースの解析。この解析によって１組の
円が導き出される。

【００９８】２．エルボー構成（すなわち０＜ｑ₃＜
π）および閉じた運動連鎖（すなわちｑ_pmin＜ｑ₂＋ｑ₃
＜ｑ_pmax）に従った制限値の解析。この解析によって
も、１組の円が導き出される。

【００９９】次いで、リストジョイント部制限の制限値
を考慮に入れる必要がある。３つの共点軸を有し、その
１つがスポット溶接ロボットで最も一般的に使用される
リストの場合、リストの動作範囲の制限は、ジョイント
ｑ₅の変位が実際に小さい（すなわちｑ_5min＜ｑ₅＜ｑ
_5max）という事実に従う。図１３の表記を使用すると、

【０１００】

【数１０】が軸４の方位ベクトルであり、

【０１０１】

【数１１】が軸６の方位ベクトルであって、リストの制約は、以下
の形式を取る。

【０１０２】

【数１２】

【０１０３】α＝ｑ₂＋ｑ₃−３π／２であるとすれば
（図１３を参照）、リストがその限界にあるロボットベ
ースロケーションを解析的に計算することができる。

【０１０４】１組の作業ポイント内にある各ポイントに
ついて解析を実行し、その共通部分が許容ベースロケー
ション領域の範囲を定めている、１組の平面領域または
表面を導き出す。作業ポイントが１つしか存在しない場
合は、平面が１つだけ生成される。これらのセクション
は、１組の曲線または直線の投影によって境界が定めら
れる平面の部分である、表面によって表される。例に示
したように、図１１は１作業ポイントおよび「エルボー
アップ位置」について、これらセクション６０のうちの
１つを示す。ロボットのベースがこの表面内のどこかに
あれば、ロボットはこの作業ポイントに届くことができ
る。作業ポイントの所与の組の場合、許容ベースロケー
ション領域は、すべての作業ポイント表面に共通の平面
内の領域となる。

【０１０５】ｂ）模擬アニーリングロボットおよび第１の周辺機械がワークスペース内に配
置されると、次いで、図２を参照しながら上記で述べた
ように、残りのすべての機械について最適または最適に
近い配置を見つけるために、本実施形態の修正された模
擬アニーリング技法が使用される。次に、模擬アニーリ
ング方法を簡単に説明した後、模擬アニーリング方法の
修正について説明する。

【０１０６】模擬アニーリング方法の概念は、たとえ
ば、Ｓ．Ｋｉｒｋｐａｔｒｉｃｋ．Ｃ．Ｄ．Ｇｅｌａｔ
ｔ，Ｊｒ．およびＭ．Ｐ．Ｖｅｃｃｈｉによる「Ｏｐｔ
ｉｍｉｚａｔｉｏｎｂｙＳｉｍｕｌａｔｅｄＡｎ
ｎｅａｌｉｎｇ」，Ｓｃｉｅｎｃｅ，２２０（４５９
８），ｐｐ．６７１〜６８０、１９８３年５月に記載さ
れている。模擬アニーリングとは、多くの変数の関数を
最小限にするような、最適化問題を解決するための方法
を指す言葉である。典型的には、本明細書ではコストと
呼ぶ、たとえばサイクル時間などの関数を最小限にする
何らかのパラメータ構成を見つけることが含まれる。

【０１０７】模擬アニーリングは、反復的な改善に基づ
いており、何らかの既存の２次最適構成または解を開始
することおよびこれを小規模に摂動することが含まれ
る。新しい構成または解が古いものよりも良い場合は、
新しい解が受け入れられ、プロセスが再度開始される。
この単純な反復方法は、古い構成の改善である場合は新
しい構成だけが受け入れられるといった、幾分粗野な方
法である。したがって、図１４を参照すると、初期の構
成から開始される。これを摂動してよい解だけを受け入
れ、すなわち下り坂だけを移動する。したがって、最終
的にポイントＡに到達すると、上り坂は移動できないの
で、それ以上どこにも動くことはできない。そこで、大
域極小がポイントＢにあっても、局部極小Ａにはまりこ
んでしまう。

【０１０８】模擬アニーリングは、次のような方法で発
生する。第１に最小化の開始ポイントが選択され、現在
ポイントとしてラベル表示される。次に、そのポイント
の隣りに新しいポイントが選択される。新しいポイント
が現在のポイントよりも低い関数値を有する場合は、単
純な反復方法の場合と同様に、自動的に次のステップの
「現在」ポイントとして適合される。そうでなければ、
次いでランダムな数が引き出される。このランダム数
が、新しいポイントが現在ポイントとして適合されるか
どうかを決定する。これによって、模擬アニーリング
に、局所極小から飛び出す能力が与えられる。

【０１０９】模擬アニーリングの実施には、新しいポイ
ントが受け入れられる確率、いわゆる温度降下関数、お
よび温度降下数という、３つのパラメータを規定するこ
とが含まれる。これらは次のように記述される。

【０１１０】１．新しいポイントが受け入れられる確
率。

【０１１１】新しいポイントｊと現在のポイントｉとの
差異がゼロよりも小さい場合、受け入れの確率は１であ
る。この差異がゼロよりも大きい場合、受け入れの確率
は、

【０１１２】

【数１３】ｐ（Δｃ_i,j、Ｔ）＝exp（−Δｃ_i,j／Ｔ）

【０１１３】となり、上式では、

【０１１４】

【数１４】Δｃ_i,j＝ｃ（ｊ）−ｃ（i）

【０１１５】となる。

【０１１６】Ｔは、コスト関数と同じユニットの、「温
度」と呼ばれる単なる制御パラメータある。

【０１１７】この値Ｔは、最初は比較的大きいので、多
くのコスト上昇移動が受け入れられる。最適化プロセス
中に温度は徐々に降下するので、よりコストの少ない移
動が受け入れられていく。

【０１１８】２．温度降下関数。Ｋｉｒｋｐａｔｒｉｃｋ（Ｓ．Ｋｉｒｋｐａｔｒｉｃ
ｋ，Ｃ．Ｄ．ＧｅｌａｔｔＪｒ．およびＭ．Ｐ．Ｖｅ
ｃｃｈｉの「ＯｐｔｉｍｉｚａｔｉｏｎｂｙＳｉｍｕ
ｌａｔｅｄＡｎｎｅａｌｉｎｇ」，Ｓｃｉｅｎｃｅ，
２２０（４５９８），ｐｐ．６７１〜６８０、１９８３
年５月）は、０．９５の温度降下率を提唱した。Ｓｅｃ
ｈｅｎ（Ｃ．Ｓｅｃｈｅｎの「ＶＬＳＩＰｌａｃｅｍ
ｅｎｔａｎｄＧｌｏｂａｌＲｏｕｔｉｎｇＵｓｉ
ｎｇＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ」，Ｋ
ｌｕｗｅｒＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒ
ｓ，Ｂｏｓｔｏｎ，１９８８年）は、高温または低温で
は、システムがわずかな状態変化しか要求しないことを
指摘した。ただし中温では、状態変化は極めて重要であ
る。したがって温度降下率を以下のように、最高および
最低温度では０．８に設定し、中温では０．９５に設定
することができる。

【０１１９】

【数１５】Ｔ_n＝α（Ｔ）Ｔ_n-1 （０＜α（Ｔ）＜１）ここでα（Ｔ）は温度降下率を示す。

【０１２０】初期温度は、計算の始めに遭遇した最初の
１０のレイアウトを受け入れるように選択される。

【０１２１】３．温度降下数。この目標は、温度を初期値の５％まで降下させることで
ある。したがって、温度降下数は、温度降下関数から直
接導出することができる。

【０１２２】模擬アニーリングは、一般に図１５の流れ
図を参照して示される。始めに、ステップ２００で第１
のポイントが選択され、ステップ２０１で現在の解とし
て設定される。さらにステップ２０２で、模擬アニーリ
ング方法の初期パラメータＴおよびｋが設定される。次
いで、ステップ２０３で、現在のポイントの隣にあるポ
イントに関して、サイクル時間コスト解が計算され、そ
の後ステップ２０４で、これと現在の解とが比較され
る。ステップ２０５で、新しい解が現在の解よりも低い
場合（はい）、ステップ２０６で、現在の解の値が自動
的に新しい解の値に置き換えられ、このプロセスが繰り
返される。ただし、ステップ２０５で新しい解が現在の
解よりも高い場合（いいえ）、０から１の間の数がラン
ダムに選択され（ステップ２０７）、次いでステップ２
０８に示すように、前述の確率関数によって決定された
確率値と比較される。ランダム数の生成および前述の確
率関数が、新しいポイントが現在のポイントとして適合
されるかどうかを決定し、模擬アニーリングに局所極小
から飛び出す能力を与える。ステップ２０８で確率関数
が新しい値が受け入れられることを示す場合（はい）、
次いで、実際のところ現在の解としては良い解ではない
が、新しいポイントが現在のポイントとして設定される
（ステップ２０６）。他方、ステップ２０８で新しいポ
イントが拒否された場合（いいえ）、その後次の反復セ
ットで温度を降下させるべきであるかどうかを決定する
（ステップ２０９）。これは、所定数の近隣解が評価さ
れたかどうかによって決定される。ステップ２０９で降
下させない場合（いいえ）、同じ温度値を使用してプロ
セスが繰り返される。ステップ２０９で十分な解数が評
価された場合（はい）、その後ステップ２１０で、前述
の温度降下関数に従ってＴの値が降下される。ステップ
２１１で、温度の最小値が達成されるまでこのプロセス
全体が繰り返され、ここでプロセスは終了する。温度を
変える前に評価される近隣解の数は、初期には経験に基
づいて推測することによって設定され、その後は実験に
基づいた知識によって設定される。

【０１２３】ｃ）修正された模擬アニーリング本実施形態は、周辺機械の最適な配置を見つける確率を
増加させること、およびＣＰＵ時間を削減することによ
って、模擬アニーリング方法を改善するように、この方
法を変更および拡張することに関するものである。これ
らの変更は、いくつかの理由によって実行された。従来
の模擬アニーリングを使用すると得られる、単一の独立
した最適な解を取得することは、産業用ＣＡＤシステム
のコンテキストでは満足できるものではない。修正され
た模擬アニーリングを使用すると、機械の配置に関して
複数の選択を実行することができる。

【０１２４】さらに、模擬アニーリング方法には長い計
算時間が必要である。大量の計算が必要な理由の１つ
は、模擬アニーリングが、局所極小の最下位にまで達し
ない限り、局所極小と通常の解とを区別できないことで
ある。初期段階で、模擬アニーリングは温度が高いとき
に広域の探索スペースをサンプリングするが、局所極小
の深いところまで達するのは、かなり後の、温度が下が
ったときだけである。すなわち、初期の時点で検索が大
域極小の誘引領域（ａｔｔｒａｃｔｉｏｎｄｏｍａｉ
ｎ）に入ったとしても、模擬アニーリング方法はローカ
ル検索を実行せず、領域全体の検索を続行する。これは
かなり望ましくない。従来の模擬アニーリング方法に何
らかの「便宜主義」を構築することが有利であるので、
検索の初期段階でローカル探査を行うことを約束してい
る。本実施形態によれば、修正された模擬アニーリング
アルゴリズムは、以下の２つの新しい機能を使用して、
この目的を達成するように設計された。

【０１２５】フリーズヒートサイクルローカル探査問題の解を見つけ出すためには、２つの要
素が重要である。その第１は、ローカル検索の約束が、
実際には傾斜降下の実行を意味することである。第２
は、温度がゼロに近づいたときに、模擬アニーリングが
傾斜降下と同等であることである。したがって、模擬ア
ニーリングアルゴリズムに便宜主義を加えるためには、
局所極小の最下位に達するのに必要な長さだけ、温度を
ほぼゼロまで下げれば十分である。その後、温度は初期
の減衰スケジュールを再開することができる。この方法
が「フリーズヒートサイクル」と呼ばれる。

【０１２６】局所極小の記憶できる限り速く最小の谷を探索し（フリーズ）、できる
限り速くそこから抜け出して（ヒート）、二度とそこへ
は戻らないことが、理想的に有利である。同じ局所極小
を再訪しないために、本実施形態に従って、これまでに
見つけたすべての局所極小のリストと、その誘引領域の
推定とが一緒に格納される。このため、そこからの傾斜
降下がこの局所極小で終了すると思われる局所極小の誘
引領域が、すべてのポイントのセットとして定義され
る。実際にはこのようなセットを解析的に記述すること
は不可能であり、誘引領域は、傾斜降下の初期ロケーシ
ョンを通過する局所極小を中心とした円に対応すること
になる。これは図１６にグラフィック表示されており、
円９０内部の領域が誘引領域である。直径ｄ（９３）
は、局所極小９１から解、すなわちロケーション９２ま
での距離によって確立され、ここから降下アルゴリズム
が適用されて局所極小９１が発見された。図１７に示し
たように、その後いつでも、誘引領域９０の外部にある
他のロケーション９５からの傾斜降下が９０内部の構成
内で終わることを検索中に、誘引領域９０のサイズがロ
ケーション９５を含むように更新され、その結果、円９
６によって境界が示された拡張済みの誘引領域が生じ
る。このような誘引領域は、実際の局所極小誘引領域の
サイズを過大評価する場合がある。ただし、修正された
方法は、良い結果を与えながら、模擬アニーリング方法
の収束特性に影響を与えないように公式化される。傾斜
降下は、実際には任意の既存誘引領域の外部にある構成
からのみ開始されるが、構成が誘引領域内部にあると、
模擬アニーリングはランダムステップの実行を続けて新
しい極小を導き出すことができる。

【０１２７】図１８を参照すると、本実施形態の修正さ
れた模擬アニーリングアルゴリズムの方法が示されてい
る。このように、ワークスペースから最初の周辺機械配
置が選択され（ステップ６００）、このロケーションが
現在の解として設定され（ステップ６０１）、温度関数
が初期設定される（ステップ６０２）。その後、現在の
解が誘引領域内部にあるかどうかが判定される（ステッ
プ６０３）。内部にある場合は、標準の模擬アニーリン
グが適用されて、領域内で大域最適を探す。図１８に示
すように、これにはステップ６０４からステップ６１５
が含まれ、ステップ６０７、６１３、および６１５で呼
び出された照会「Ｔ＝０」への答えは、否定で応答され
る。この場合、温度降下関数に従って、温度が下げられ
る。

【０１２８】ただし、現在の解が誘引領域内にない場合
は、その後、Ｔの値がゼロに設定されることでフリーズ
ヒートサイクルが適用され（ステップ６１９）、その結
果降下アルゴリズムが生成されて、局所極小から飛び出
す、すなわち「上り坂」を進んでいく可能性のない極小
方向へと即時に働く。評価される解が誘引領域内にない
場合、２つの結果のどちらかが発生する。降下アルゴリ
ズム中に、解が既存の誘引領域内に降下していくと、そ
の後既存の誘引領域は、降下アルゴリズムの起源である
解を含むように更新され、この場合、図１７に示したよ
うに、その誘引領域のサイズが増加される。これは、図
１８のステップ６１６に示されている。このステップで
は、ステップ６１３の照会が肯定応答（Ｔ＝０）である
ので、ステップ６０６で判定された初期解よりも良い解
が、ステップ６１６に到達する。ステップ６１６では、
新しい解が既存の誘引領域内にあるかどうかが判定さ
れ、その後、降下の起源である解を含むように誘引領域
が更新されて（ステップ６１７）、その結果誘引領域が
拡張される。

【０１２９】他方で、降下アルゴリズム中に、解が既存
の誘引領域内に入らずに極小まで降下した場合は、その
後局所極小が新しい誘引領域の中心で見つかったかどう
かが判定される。この場合は、対応する誘引領域が作成
および格納される（図１８のステップ６２１および６２
２）。

【０１３０】コスト関数前述の模擬アニーリング方法への修正を介して、莫大な
ＣＰＵ時間を必要としない、最適および最適に近い解を
見つけ出す方法が得られる。

【０１３１】修正された模擬アニーリングを使用して、
選択された機械に可能な配置セットを見つける。計算さ
れた位置は、仮定を記述したセクションで言及された制
約のみで制限される検索スペース内において、コスト関
数の局所極小である。

【０１３２】コスト関数は、以下に定義した数式（９）
から計算され、

【０１３３】

【数１６】

【０１３４】上式で、ｔ_ijは、ロボットが機械ｉから機
械ｊまで移動するのに必要な時間、Ｉ_ijは、機械ｉがす
でに配置された機械ｊと対話する回数（ｉ≠ｊ）、ｎは
すでに配置された機械数である。

【０１３５】値ｔ_ijは、ＣＡＤ／ＣＡＭ／ＣＡＥシステ
ムで使用可能な標準機能を使用して得られることに留意
されたい。

【０１３６】選択された機械の所与の配置についてＦ_i
を評価する前に、アクセスポイントのアクセス可能性お
よび重なりがないことが確認される。配置された機械の
間でロボットが移動することの実行可能性も保証されて
おり、ロボットの移動が不可能な場合は、移動時間を計
算するのに使用される標準機能がエラーメッセージを戻
す。

【０１３７】修正された模擬方法が初期解として使用す
る初期の機械の位置および向きは、前述のワークセルフ
ロア表示を使用して決定される。配置する機械の境界の
１つがすでに配置された機械と一致するように、十分な
数の空きマトリックスセルが選択される。このようなロ
ケーションが良好な関数値を保証しない場合であって
も、初めは、機械間のスペースを最小にする特権が与え
られている。

【０１３８】部分レイアウト選択規則前述のように、本実施形態の方法の「構成アルゴリズ
ム」部分では、各ステップで機械が選択され、修正され
た模擬アニーリング方法を使用して、選択された機械の
いくつかの可能な配置が決定される。したがって、すで
に配置されたｎ個の機械を含む部分的に構成されたレイ
アウトは、ｎ＋１個の機械を含むｍ個のレイアウトセッ
トを導き出し、ｍは配置する機械に可能なロケーション
数に対応する。

【０１３９】発見されたすべての機械配置のレイアウト
を構成するには、爆発的に多くの計算が必要となる。し
たがって、部分レイアウトの選択規則が必要である。こ
の規則は、標準的な構成方法に比べて、追加的な機能で
ある。

【０１４０】使用される方式は、構成ステップの後で生
成されたすべての部分レイアウトの中で、最良のｋを維
持する。最も有効なｋの値は、経験に基づいて、５であ
ることが証明されている。この値が、最高の「サイクル
時間／ＣＰＵ時間」の比を導き出す。

【０１４１】したがって実行の最後には、５つの最適な
ワークセルレイアウトがユーザに提供される。このよう
な結果は、いくつかの理由で有用である。たとえば、ワ
ークセルの幾何学的モデリングは、実際の世界では十分
な精度を示さない。修正された模擬アニーリング方法か
ら得られた配置が、性能の低下を導き出すような位置で
囲まれており、この機械配置が最終的な最適レイアウト
の１つにあると思われる場合、この結果を実際の現場に
転送することはできない。

【０１４２】例ここで、本実施形態の方法を適用する例を、１台のロボ
ットおよび１０台の機械を使用するワークセルに関して
記述する。最適化前の３次元表示を図１９に示す。

【０１４３】この例の作業シーケンスは、以下のとおり
である。

【０１４４】１．ロボットは、機械６からドライブシャ
フトを連続して６回把持し、これらを円形の割出し台
（機械１）上にある６つのアセンブリ取付け具に配置す
る。

【０１４５】２．機械７からベアリングとスラスト座金
の組み合わせを取得し、これを機械１の取付け具に連続
して６回取り付ける。

【０１４６】３．その後ロボットはグリース計量ユニッ
トである機械２を把持し、機械１にある６つの取付け具
すべてのハウジング内歯にグリースを塗布する。

【０１４７】４．機械８で段付きシャフトが６回把持さ
れ、機械１のハウジングに取り付けられる。

【０１４８】５．機械４で３つの円筒ピンが次々と把持
され、機械１の段付きシャフト内に取り付けられる。こ
の手順が次々と６回繰り返される。

【０１４９】６．機械３から３つのギアホイールが連続
して６回把持され、ピン上に配置される。

【０１５０】７．機械９でファンホイールが６回把持さ
れ、機械１のドライブシャフトに取り付けられる。

【０１５１】８．機械５から取得したスプリングナット
が、機械１の各ドライブシャフトに取り付けられる。

【０１５２】９．最後に、組み立てられたユニットが割
出し台から取り外され、１つずつコンベヤベルト（機械
１０）上に配置される。

【０１５３】図２０および２１はそれぞれ、上記の作業
シーケンスから生成されたサイズ表およびランク表であ
る。

【０１５４】前の表から、プログラムの各ステップで値
Ｃ_i（数式（５）を参照）が計算された。機械が配置さ
れた順序は、次のとおりである。

【０１５５】機械１−機械７−機械４−機械５−機械９
−機械６−機械８−機械３−機械１０−機械２

【０１５６】結果の比較本実施形態の修正された模擬アニーリング方法は、確率
論的な方法である。したがって、この方法の結果は、実
行するごとに異なる場合がある。このセクションで示し
レイアウトは、結果を例示するために、どちらも単一の
応用例から得られたものである。図２２は最適なレイア
ウトを示し、図２３は最適に近い、他の計算された５つ
の解を示す。どちらのレイアウトも機械の間にスペース
があることに留意されたい。

【０１５７】前の方法と比較するために、Ｍ．Ｌ．Ｔａ
ｙａｎｄＢ．Ｋ．Ａ．Ｎｇｏｉ，「Ｏｐｔｉｍｉｓ
ｉｎｇＲｏｂｏｔＷｏｒｋｃｅｌｌＬａｙｏｕ
ｔ」，ＴｈｅＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒ
ｎａｌｏｆＡｄｖａｎｃｅｄＭａｎｕｆａｃｔｕ
ｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，１２（５），ｐｐ．
３７７〜３８５、１９９６年によって提案された方法
が、Ｄａｓｓａｕｌｔ−Ｓｙｓｔｅｍｅｓ，Ｓｕｒｅｓ
ｎｅｓ，Ｆｒａｎｃｅによって販売されている市販のＣ
ＡＤプログラムである「ＩＧＲＩＰ」で修正および実施
されているので、比較が可能であった。使用されたロボ
ットは、デカルト座標ロボットではなく、Ｒｅｎａｕｌ
ｔＡｕｔｏｍａｔｉｏｎ，ｒｕｅＪｕｌｅｓＧｕ
ｅｓｄｅｓ，９１１３０Ｒｉｓ−Ｏｒａｎｇｉｓ，Ｆ
ｒａｎｃｅが構築したＡＣＭＡＸ５８である。「Ｔ＆
Ｎレイアウト」と名付けられた取得レイアウトが、図２
４に示されている。

【０１５８】表１は、図２２、２３、および２４に示さ
れたレイアウトのサイクル時間を示す表である。表２
は、両方の方法がワークセルレイアウトを最適化するた
めに必要な計算時間を示す表である。

【０１５９】

【表１】

【０１６０】

【表２】

【０１６１】したがって、最適なレイアウトは、従来技
術のＴ＆Ｎレイアウトに比べて、サイクル時間を２４．
６５秒減らし、１０．２％の改善となっている。さら
に、最適に近いレイアウトは、この研究の追加の制約を
考慮しなければ、非常に良い解であると言える。

【０１６２】本実施形態の方法に対応する計算時間は、
Ｔ＆Ｎ方法の計算時間よりも長い。にもかかわらず、
（１）本方法は、産業用ＣＡＤ／ＣＡＭ／ＣＡＥシステ
ムのコンテキストに適合しており、（２）いくつかのレ
イアウトが得られ、（３）Ｔ＆Ｎ方法とは異なり、問題
に関連付けられた調査スペース、すなわちすべての可能
なレイアウトを含む調査スペースが広範囲に渡って検索
される。

【０１６３】統計結果以前に述べたように、この方法は確率論的である。した
がって、その性能を研究するには統計結果が重要であ
る。このプログラムは連続して５０回実行された。表３
は、サイクル時間の平均および標準偏差を示した表であ
る。「最適なレイアウト」とは、実際には「取得された
５つの中で最高のレイアウト」を意味し、「最悪な最適
に近いレイアウト」とは、「取得された５つの中で最悪
のレイアウト」を意味する。表４は計算時間に対応す
る。

【０１６４】

【表３】

【０１６５】

【表４】

【０１６６】したがって、前のセクションで得られた結
果が確認される。本実施形態の方法が、Ｔ＆Ｎ方法に比
べて平均１１．２％の改善を導き出していること、およ
びこれまでに得られた最高のレイアウトはサイクル時間
２０９．６５秒という結果を出したことに留意された
い。

【０１６７】前述の方法は、ＣＡＤ／ＣＡＭシステムに
よって定義されることが可能な任意のワークプレース構
成に適用できることに留意されたい。本実施形態は、デ
ジタル電子回路、すなわちコンピュータのハードウェ
ア、ファームウェア、ソフトウェア、またはこれらの組
み合わせで実施することができる。本実施形態の装置
は、プログラム可能プロセッサが実行するために、機械
読取り可能記憶デバイス内で具体的に実施されるコンピ
ュータプログラム製品で実施することが可能であり、本
実施形態の方法のステップは、入力データで作業して出
力を生成することによって本実施形態の機能を実行する
ために、命令プログラムを実行するプログラム可能プロ
セッサによって実行することができる。

【０１６８】本実施形態は、データ格納システム、少な
くとも１つの入力デバイス、および少なくとも１つの出
力デバイスから、データおよび命令を受信し、これらに
データおよび命令を送信するために結合された、少なく
とも１つのプログラム可能プロセッサを含むプログラム
可能システム上で実行可能な、１つまたは複数のコンピ
ュータプログラム内で実施できるので有利である。アプ
リケーションプログラムは、高水準の手続き型プログラ
ミング言語またはオブジェクト指向プログラミング言語
で実施するか、または所望であればアセンブリ言語また
は機械言語で実施してもよく、いずれの場合も、この言
語はコンパイルまたは翻訳処理された言語であってよ
い。

【０１６９】一般にプロセッサは、読取り専用メモリお
よび／またはランダムアクセスメモリから、命令および
データを受け取る。コンピュータプログラム命令および
データを具体的に実施するのに好適な格納デバイスは、
たとえばＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュ
メモリデバイスなどの半導体メモリデバイス、内部ハー
ドディスクおよび取外し可能ディスクなどの磁気ディス
ク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスクな
どを含む、すべての形式の不揮発性メモリを含む。前述
のいずれも、特別設計のＡＳＩＣ（特定用途向け集積回
路）を補足するか、またはこれに組み込むことができ
る。

【０１７０】以上、本発明のいくつかの実施形態につい
て述べてきた。本発明の精神および範囲を逸脱すること
なく、様々な修正が実行できることが理解されよう。た
だし、その他の実施は、添付の特許請求の範囲内である
ものとする。

【図面の簡単な説明】

【図１】本発明実施形態の使用可能なコンピュータシス
テムを示す構成図である。

【図２】本発明実施形態のシステムを表す概略図であ
る。

【図３】本発明実施形態の機械間の対話を定義するため
のグラフィックツールの一例を示す図である。

【図４】本発明実施形態の機械の対話シーケンスを搬送
するグラフィック表示の一例を示す図である。

【図５】本発明実施形態の特定の機械にロボットがアク
セスする回数、ならびに所与の作業シーケンスに関する
機械間の対話回数を、編成および格納するためのランク
表の一例を示す図である。

【図６】本発明実施形態のワークセル内に配置される機
械の形状を簡略化するための、機械の境界矩形とその対
応する構成矩形との間の関係を示す図である。

【図７】本発明実施形態のワークセル内での機械間の重
なり距離および理想距離を示す図である。

【図８】本発明実施形態のオブジェクトがワークセル内
に配置される前の、ワークセルフロアスペースの２次元
表現を示す図である。

【図９】本発明実施形態の１つのオブジェクトがその上
に配置されたワークセルフロアスペースの２次元表示を
示す図である。

【図１０】本発明実施形態の３つのオブジェクトがその
上に配置されたワークセルフロアスペースの２次元表示
を示す図である。

【図１１】本発明実施形態の水平面内の許容可能ベース
ロケーション領域内にそのベースが位置付けされたロボ
ットをグラフィック表示した図である。

【図１２】移動軸を示す座標系内に配置されたロボット
をグラフィック表示した図である。

【図１３】許容可能なベースロケーション領域を決定す
るための解析フレームワークを提供する、ロボットのリ
ストジョイント座標系をグラフィック表示した図であ
る。

【図１４】局部極小が存在するときに、単一の反復方法
を使用して大域極小を決定する問題を示す図である。

【図１５】模擬アニーリング方法を示す概略図である。

【図１６】本発明実施形態の「誘引領域」をグラフィッ
ク表示した図である。

【図１７】本発明実施形態の初期データポイントから誘
引領域への傾斜降下によって生じる、誘引領域の拡大を
グラフィック表示した図である。

【図１８】本発明実施形態の修正された模擬アニーリン
グ方法を示す概略図である。

【図１９】本発明実施形態の最適化を実行する前の、例
のワークセルレイアウトをグラフィック表示した図であ
る。

【図２０】本発明実施形態のワークセルの例について、
生成されるマシンのサイズ表を示す図である。

【図２１】本発明実施形態の例について、生成されるラ
ンク表を示す図である。

【図２２】本発明実施形態の例について、生成される最
適なワークセルレイアウトをグラフィック表示した図で
ある。

【図２３】本発明実施形態の例について、生成される他
のワークセルレイアウトをグラフィック表示した図であ
る。

【図２４】本発明実施形態の例について、従来技術の方
法によって生成されるワークセルレイアウトをグラフィ
ック表示した図である。

【符号の説明】

６０許容ベースロケーション領域６１主アーム６２主アーム６３主アーム９０前の誘引領域９１局所極小９２ロケーション９５降下アルゴリズムの適用元である解９６更新された誘引領域１００コンピュータ１０１ＣＰＵ１０２ＣＰＵバス１０３システム制御装置１０４ＤＲＡＭ制御装置１０５ＲＡＭ１０６キャッシュＳＲＡＭ１１０周辺バス１１１ブリッジ制御装置１１２ビデオ制御装置１１４ネットワークアダプタ１１５ビデオディスプレイ１２０ＩＳＡバス１２１キーボード制御装置、ＲＴＣ、シリアルおよび
パラレルポート１２２ＲＯＭ１２３ＢＩＯＳ１２４オーディオ

───────────────────────────────────────────────────── フロントページの続き (71)出願人 500102435 ９，ｑｕａｉＭａｒｃｅｌＤａｓｓａｕｌｔ，ＢＰ 310 92156 ＳｕｒｅｓｎｅｓＣｅｄｅｘ，ＦＲＡＮＣＥ

Claims

【特許請求の範囲】

【請求項１】所与の作業シーケンスを完了するための
サイクル時間を最小限にするように、ワークセル内で１
つのロボットおよび周辺機械セットの配置を最適化する
ための、ＣＡＤ／ＣＡＭシステムで使用するコンピュー
タシステム操作方法において、ａ）ワークセルを表すデータセットを定義するステップ
と、ｂ）ロボットと、前記周辺機械セットからの第１の周辺
機械とを、前記ワークセル内に配置し、前記配置を現在
のレイアウトセットとして指定するステップと、ｃ）前記ワークセル内に配置するために、前記周辺機械
セットから他の周辺機械を選択するステップと、ｄ）前記現在のレイアウトセット内の各レイアウトにつ
いて、最小サイクル時間のために選択される最適な方法
を使用して、ステップｃ）で選択された周辺機械を前記
ワークセル内に配置するのに可能なロケーションセット
を計算するステップと、ｅ）ステップｄ）で計算された可能なロケーションセッ
トから、計算された最小のサイクル時間に対応するロケ
ーションを表すレイアウトサブセットを選択し、各選択
されたロケーションがワークセル内のオブジェクトレイ
アウトに対応したものであり、前記レイアウトサブセッ
トを現在のレイアウトセットとして指定するステップ
と、ｆ）前記周辺機械セット内の前記周辺機械すべてが、前
記ワークセル内に配置されるまで、ステップｃ）から
ｅ）を反復するステップとを含むことを特徴とするコン
ピュータシステム操作方法。
【請求項２】請求項１に記載のコンピュータシステム
操作方法において、ワークセル内に配置するための順序
で、前記周辺機械セット内に周辺機械を配置するステッ
プをさらに備えたことを特徴とするコンピュータシステ
ム操作方法。
【請求項３】請求項２に記載のコンピュータシステム
操作方法において、前記周辺機械は、ロボットが最もよ
くアクセスする機械を優先する順序で配置されることを
特徴とするコンピュータシステム操作方法。
【請求項４】請求項２に記載のコンピュータシステム
操作方法において、前記周辺機械は、大型の機械に対し
て小型の機械を優先する順序で配置されることを特徴と
するコンピュータシステム操作方法。
【請求項５】請求項２に記載のコンピュータシステム
操作方法において、前記周辺機械は、第１の基準として
ロボットが最もよくアクセスする機械を優先する順序
で、および第２の基準として大型の機械に対して小型の
機械を優先する順序で配置されることを特徴とするコン
ピュータシステム操作方法。
【請求項６】請求項１に記載のコンピュータシステム
操作方法において、最小サイクル時間を選択するための
前記最適化方法は、修正された従来の模擬アニーリング
方法を備え、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引（attraction）領域を
確立するステップと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が
誘引領域内にあるデータポイントを生成するときに、誘
引領域が傾斜降下の開始されるデータポイントを含むように、誘引
領域を再定義するステップとを含むことを特徴とするコ
ンピュータシステム操作方法。
【請求項７】請求項２に記載のコンピュータシステム
操作方法において、最小サイクル時間を選択するための
前記最適化方法は、修正された従来の模擬アニーリング
方法を備え、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を確立するステッ
プと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを含
むことを特徴とするコンピュータシステム操作方法。
【請求項８】最小サイクル時間を選択するための前記
最適化方法は、修正された従来の模擬アニーリング方法
を備え、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を確立するステッ
プと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを含
むことを特徴とするコンピュータシステム操作方法。
【請求項９】ワークセルを表すデータと、ワークセル
内に配置されたロボットの物理的構成を表すデータと、
ワークセル内に配置された周辺機械セット内の各機械の
物理的構成を表すデータと、ロボットおよび各周辺機械
のワークセル内でのロケーションを表すデータとを備
え、前記ロケーションは、所与の作業シーケンスについ
て、前記ロボットが前記それぞれの周辺機械にアクセス
するためのサイクル時間を結果的に最小化するワークセ
ル内のオブジェクト構成を表す、デジタルデータストリ
ームで実施されるコンピュータデータ信号であって、ａ）ワークセルを表すデータセットを定義するステップ
と、ｂ）ロボットと、前記周辺機械セットからの第１の周辺
機械とを、前記ワークセル内に配置し、前記配置を現在
のレイアウトセットとして指定するステップと、ｃ）前記ワークセル内に配置するために、前記周辺機械
セットから他の周辺機械を選択するステップと、ｄ）前記現在のレイアウトセット内の各レイアウトにつ
いて、最小サイクル時間のために選択される最適な方法
を使用して、ステップｃ）で選択された周辺機械を前記
ワークセル内に配置するために可能なロケーションセッ
トを計算するステップと、ｅ）ステップｄ）で計算された可能なロケーションセッ
トから、計算された最小のサイクル時間に対応するロケ
ーションを表すロケーションサブセットを選択し、各選
択されたロケーションはワークセル内のオブジェクトレ
イアウトに対応したものであり、前記レイアウトサブセ
ットを現在のレイアウトセットとして指定するステップ
と、ｆ）前記周辺機械セット内の前記周辺機械すべてが、前
記ワークセル内に配置されるまで、ステップｃ）から
ｅ）を反復するステップとを備えた方法によって生成さ
れることを特徴とするデジタルデータストリームで実施
されるコンピュータデータ信号。
【請求項１０】請求項９に記載のデジタルデータスト
リームで実施されるコンピュータデータ信号において、
データストリームを生成する方法は、ワークセル内に配
置するための順序で前記周辺機械セット内に周辺機械を
配置するステップをさらに備えたことを特徴とするデジ
タルデータストリームで実施されるコンピュータデータ
信号。
【請求項１１】請求項１０に記載のデジタルデータス
トリームで実施されるコンピュータデータ信号におい
て、前記周辺機械は、ロボットが最もよくアクセスする
機械を優先する順序で配置されることを特徴とするデジ
タルデータストリームで実施されるコンピュータデータ
信号。
【請求項１２】請求項１０に記載のデジタルデータス
トリームで実施されるコンピュータデータ信号におい
て、前記周辺機械は、大型の機械に対して小型の機械を
優先する順序で配置されることを特徴とするデジタルデ
ータストリームで実施されるコンピュータデータ信号。
【請求項１３】請求項９に記載のデジタルデータスト
リームで実施されるコンピュータデータ信号において、
前記データ信号を生成する方法は、修正された従来の模
擬アニーリング方法からなる最小サイクル時間を選択す
るための最適化方法をさらに備え、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む前記局所
極小のそれぞれに対応する誘引領域を確立するステップ
と、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを含
むことを特徴とするデジタルデータストリームで実施さ
れるコンピュータデータ信号。
【請求項１４】入力デバイスと、中央処理ユニットと、データを格納するためのメモリデバイスとを備え、中央処理ユニットは、所与の作業シーケンスを完了する
サイクル時間を最小化するように、ワークセル内でのロ
ボットおよび周辺機械セットの配置を最適化するための
コードを含むアプリケーションプログラムを実行し、前
記コードが装置に実行させる方法は、ａ）ワークセルを表すデータセットを定義するステップ
と、ｂ）ロボットと、前記周辺機械セットからの第１の周辺
機械とを、前記ワークセル内に配置し、前記配置を現在
のレイアウトセットとして指定するステップと、ｃ）前記ワークセル内に配置するために、前記周辺機械
セットから他の周辺機械を選択するステップと、ｄ）前記現在のレイアウトセット内の各レイアウトにつ
いて、最小サイクル時間のために選択される最適な方法
を使用して、ステップｃ）で選択された周辺機械を前記
ワークセル内に配置するために可能なロケーションセッ
トを計算するステップと、ｅ）ステップｄ）で計算された可能なロケーションセッ
トから、計算された最小のサイクル時間に対応するロケ
ーションを表すロケーションサブセットを選択し、各選
択されたロケーションがワークセル内のオブジェクトレ
イアウトに対応したものであり、前記レイアウトサブセ
ットを現在のレイアウトセットとして指定するステップ
と、ｆ）前記周辺機械セット内の前記周辺機械すべてが前記
ワークセル内に配置されるまで、ステップｃ）からｅ）
を反復するステップとを含むことを特徴とするＣＡＤ／
ＣＡＭ装置。
【請求項１５】請求項１４に記載のＣＡＤ／ＣＡＭ装
置において、前記方法は、ワークセル内に配置するため
の順序で前記周辺機械セット内に周辺機械を配置するス
テップをさらに備えたことを特徴とするＣＡＤ／ＣＡＭ
装置。
【請求項１６】請求項１５に記載のＣＡＤ／ＣＡＭ装
置において、前記周辺機械は、ロボットが最もよくアク
セスする機械を優先する順序で配置されることを特徴と
するＣＡＤ／ＣＡＭ装置。
【請求項１７】請求項１５に記載のＣＡＤ／ＣＡＭ装
置において、前記周辺機械は、大型の機械に対して小型
の機械を優先する順序で配置されることを特徴とするＣ
ＡＤ／ＣＡＭ装置。
【請求項１８】機械セットをワークセル内に配置する
ためのロケーションを含むデータセットを検索するため
の方法であって、前記ロケーションは、定義済みの作業
シーケンスで前記機械のそれぞれにロボットのエンドエ
フェクタが届くようにできるロケーションであり、前記
方法は、ロボットのエンドエフェクタが作業シーケンス
を介して移動するための時間を最小限にするようなデー
タセットから、別々のロケーションセットを選択し、前
記方法は、従来の模擬アニーリング方法の修正を使用して前記デー
タセットを検索するステップを含み、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を確立するステッ
プと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを含
むことを特徴とするデータセットを検索するための方
法。
【請求項１９】第１の機械をワークセル内に配置する
ためのロケーションセットを表すデータを含む、デジタ
ルデータストリームで実施されるコンピュータデータ信
号であって、前記ロケーションは、最小時間内にワーク
セル内のロボットのエンドエフェクタが、第１の機械な
らびにワークセル内の他の機械に届くようにするロケー
ションであって、前記データ信号は、修正された模擬アニーリング方法を使用してワークセル
フロアスペースを表すデータセットを検索するステップ
を備えた方法によって取得され、前記修正は、標準的な模擬アニーリングプロセス中に遭遇する局所極
小を格納するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を確立するステッ
プと、誘引領域内にないデータセットからのデータポイントに
遭遇したときに、模擬アニーリング方法の温度関数を値
ゼロに設定することによって、傾斜降下を実行するステ
ップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを含
むことを特徴とするデジタルデータストリームで実施さ
れるコンピュータデータ信号。
【請求項２０】入力デバイスと、中央処理ユニットと、データを格納するためのメモリデバイスと、ディスプレイデバイスとを備え、中央処理ユニットは、別々の最適なデータポイントセッ
トを見つけるためにデータ検索を実行するためのコード
を含むアプリケーションプログラムを実行し、前記検索
が修正された模擬アニーリング方法を含み、前記模擬ア
ニーリング方法の前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を格納するステッ
プと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義し格納するステップ
とを含むことを特徴とする、ＣＡＤ／ＣＡＭ装置。
【請求項２１】コンピュータ読取り可能媒体上に格納
されたコンピュータ実行可能コードであって、該コード
は所与の作業シーケンスを完了させるサイクル時間を最
小にするために、コンピュータにワークセル内でのロボ
ットおよび周辺機械セットの配置を最適化させるための
手段を含み、前記コードは、ａ）ワークセルを表すデータセットを定義するステップ
と、ｂ）ロボットと、前記周辺機械セットからの第１の周辺
機械とを、前記ワークセル内に配置し、前記配置を現在
のレイアウトセットとして指定するステップと、ｃ）前記ワークセル内に配置するために、前記周辺機械
セットから他の周辺機械を選択するステップと、ｄ）前記現在のレイアウトセット内の各レイアウトにつ
いて、最小サイクル時間のために選択される最適な方法
を使用して、ステップｃ）で選択された周辺機械を前記
ワークセル内に配置するために可能なロケーションセッ
トを計算するステップと、ｅ）ステップｄ）で計算された可能なロケーションセッ
トから、計算された最小のサイクル時間に対応するロケ
ーションを表すロケーションサブセットを選択し、各選
択されたロケーションはワークセル内のオブジェクトレ
イアウトに対応しており、前記レイアウトサブセットを
現在のレイアウトセットとして指定するステップと、ｆ）前記周辺機械セット内の前記周辺機械すべてが前記
ワークセル内に配置されるまで、ステップｃ）からｅ）
を反復するステップとをさらに備えたことを特徴とする
コンピュータ実行可能コード。
【請求項２２】請求項２１に記載のコンピュータ実行
可能コードにおいて、前記コードは、ワークセル内に配
置するための順序で前記周辺機械セット内に周辺機械を
配置するステップをさらに備えたことを特徴とするコン
ピュータ実行可能コード。
【請求項２３】請求項２２に記載のコンピュータ実行
可能コードにおいて、前記コードは、ロボットが最もよ
くアクセスする機械を優先する順序で前記周辺機械を配
置するステップをさらに備えたことを特徴とするコンピ
ュータ実行可能コード。
【請求項２４】請求項２２に記載のコンピュータ実行
可能コードにおいて、前記コードは、大型の機械に対し
て小型の機械を優先する順序で前記周辺機械を配置する
ことをステップをさらに備えたことを特徴とするコンピ
ュータ実行可能コード。
【請求項２５】請求項２１に記載のコンピュータ実行
可能コードにおいて、最小サイクル時間を選択する前記
最適化方法は、修正された従来の模擬アニーリング方法
を含み、前記修正は、模擬アニーリングプロセス中に遭遇する局所極小を格納
するステップと、局所極小データポイントを取り囲む領域を含む、前記局
所極小のそれぞれに対応する誘引領域を確立するステッ
プと、誘引領域内にないデータポイントに遭遇したときに、模
擬アニーリング方法の温度関数を値ゼロに設定すること
によって、傾斜降下を実行するステップと、傾斜降下が誘引領域内にあるデータポイントを生成する
ときに、誘引領域が傾斜降下の開始されるデータポイン
トを含むように、誘引領域を再定義するステップとを備
えたことを特徴とするコンピュータ実行可能コード。