(57)【特許請求の範囲】
【請求項１】
エア・ジェット・モジュールを制御するための、分散されたアクチュエーション割り当てシステムであって、
複数の実行ユニット(150)、又は、複数の実行ユニット・サブ・モジュール(170,180)、の少なくとも１つを備える複数のモジュールにグループ化された、複数の実行ユニット(150)であって、当該実行ユニット(150)が、紙片に対して作動して、当該紙を１つの位置から他の位置に移動させるエア・ジェットであり、当該実行ユニット・サブ・モジュール(170,180)が、複数のエア・ジェットを含むものであるものと、
システム・ゴールを生成する制御器(135)であって、当該システム・ゴールが、実行ユニット（150）が達成すべき、フォースの割当てであるものと、そして、
システム・ゴールを受信し、以下の（式１）に基づき、割り当てパラメータに基づいて、システム・ゴールを、複数のモジュールの各々に対して１つの、複数のサブ・ゴールに分割する、少なくとも１つの割当て器(110)であって、当該サブ・ゴールが、フォースであり、当該サブ・ゴールが、以下の（式１）で表され、
ｕi＝（ｆxi ｆyi tzi）T      （式１）
ここで、
ｆxiは、エア・ジェットｉ（ｉ＝１・・・Ｎの整数。Ｎはエア・ジェットの数。）についてのｘフォースであって、
【数１】
0004215995.tif 000025
で表され、
ｆyiは、エア・ジェットｉについてのｙフォースであって、
【数２】
0004215995.tif 000026
で表され、
tzi は、（xi, yi）位置におけるトルクであって、
【数３】
0004215995.tif 000027
で表され、
ここで、wx及びwyは、それぞれ、ｘフォース及びｙフォースへの各モジュールの貢献のための重み付けファクターであり、
【数４】
0004215995.tif 000028
割当て器(110)に対応するモジュールが、複数の実行ユニット・サブ・モジュール(170,180)を含む場合には、上記（式１）に基づいて、前記少なくとも１つの割当て器(110)が、少なくとも１つのサブ・ゴールを、複数の実行ユニット・サブ・モジュール(170,180)の少なくとも１つに割り当てる、
分散されたアクチュエーション割り当てシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、実行ユニットのグループのアクチュエーション割当ての装置及び方法に関する。
【０００２】
【従来の技術】
スマート・マター・システム（smart matter system）は、多数の要素（センサ,アクチュエータ,及び／又はアロケータ（allocator）のような）を持つシステムである。そのようなシステムでの主要な問題は、全スマート・マター・システムのための、所望の結果を得るため、あるいはゴールを達成するために、多くの要素の動作を調整することである。所望の結果は、全てのアクチュエータを通じての累積的なアクチュエーションを得るために、特定の動作を各個々のアクチュエータに対して制御すること、あるいは、割当てすることによって達成される。各アクチュエータの所望の個々の動作は、多くのやり方によって達成され得る。しかし、アクチュエーションは、多くの制約を満足させつつ、いくつかの最適なあるいは最適に近いやり方によって達成されねばならない。
【０００３】
比較的小さい数のアクチュエータを持つシステムのためには、例えば、消耗的な探索法を用いて、全体的なシステムアクチュエーションを得るために、所望の個々のアクチュエーションを決定することは比較的容易である。不幸なことに、所望の全体的結果を得るための方法の数は、制御されるべきアクチュエータの数に伴って指数関数的に増加する。従って、多くのアクチュエータ間のアクチュエーション割当ての問題は、スマート・マター・方式においてアクチュエータ数が増加するに従って、かなり、より困難になる。更に、アクチュエータ数が増加するにつれて、割当てを計算するために利用可能な時間は、普通、減少する。なぜなら、割当て決定を、増加した数のアクチュエータに通信する必要があるからである。
【０００４】
アクチュエータ割当てについての関連技術による方法としては、消耗的サーチ方法が含まれる。これによれば、所望の結果を達成することができる、全ての可能なアクチュエーション割当てを通じて、システム的なサーチが実行される。
【０００５】
アクチュエータ割当てについての他の関連技術による方法には、混合整数非線型プログラミング問題（mixed integer nonlinear programming problem）の解決が含まれる。割当て問題は、各アクチュエータのアクチュエーションを選択するための、連続的な、及び、整数の変数の組についての、混合整数非線型プログラミング問題としての特徴を持つ。分岐と連結,ベンダーの分解,及び外挿、のような種々の方法が、混合整数非線型プログラミング問題を解決するために用いられる。これらの方法は、整数的制約無しに、最適化問題を解決し、その後、増加的に整数的制約を強制する。その結果は、可能な、全ての指数関数的な数の組合わせを計算するのではなく、その木の各枝における非線型最適化問題を解決するという労力をかけることによって、探索木の可能性の高い（promising）枝だけが計算される。
【０００６】
アクチュエータ割当てのための制約された最適化を解決するための、他の関連技術による方法は、内部点（interior point）あるいはアクティブセット法のような標準最適化方法を用いる。
【０００７】
しかし、これらの関連技術による方法は、多くの不利な点を持つ。
【０００８】
消耗的サーチ技術によるアクチュエーション割当ての関連技術による方法は、比較的小さい数のアクチュエータだけの制御が必要とされる、スマート・マター・システムのための、一定の受け入れ可能なパラメータ内で動作し得る。なぜなら、全ての解が、比較的短時間で計算され得るからである。しかし、消耗的サーチための計算の努力は、アクチュエータの数及びアクチュエータ状態の数に伴って、指数関数的に増加するので、もしアクチュエータ数が一定限度（プロセッサ速度及び必要な制御帯域によって、一般的に10より小さい）を越えて増加するならば、実行が難しい。
【０００９】
アクチュエータを割当てするための、混合整数非線型プログラミングを用いた、関連技術による方法もまた、不利な点を持つ。各枝での計算は、より複雑である。なぜなら、この計算には、各ステップでの、制約された非線型プログラミング問題の解決が含まれるからである。更に、この方法のためのアルゴリズムには、中央の位置における、システムの完全な知識が要求されるし、割当ては、多くのプロセッサ間で分配することが困難である。従って、もしシステムのハードウェアの性質が元来モジュラーであれば、非線型プログラミング技術を採用する方法にとって、所望の情報を持つ集中的割当て器を提供するためには、大量の通信が必要とされる。
【００１０】
標準最適化技術を用いる、アクチュエータ割り当てについての、関連技術による方法もまた、不利な点を持つ。このタイプの方法は、結果として最適値からの大きな偏差をもたらすような解を必要とする。なぜなら、その解は、バイナリ値に限定され、アクチュエータ数が100以下に限定されるからである。これらの技術はまた、システムに関する広い知識を必要とし、そのため、通信を大量に使用することになり、それによって、分散システムにおいて高コストをもたらす。
【００１１】
上述の関連技術による方法がこのような不利な点を持つ結果、スマート・マター・システムのための、アクチュエーションを割当てるための新しい方法及び装置が必要とされる。
【００１２】
【発明の概要】
本発明は、階層的にアクチュエーション割当てを分解し、最適化と、迅速な計算の必要性を均衡させる方法及び装置を提供する。
【００１３】
本発明は、少しの実行ユニット（例えば10個）から、多数の実行ユニット（10000より多い）までの、異なる数の実行ユニットを持つシステムのための、アクチュエーションの割当てを可能とする方法及び装置を別々に提供する。
【００１４】
本発明は、システムコントローラとの通信のための必要性を最小化する、実行ユニットの制御を割り当てるための方法及び装置を別々に提供する。
【００１５】
本発明は、アクチュエータ割当ての問題を、最適なやり方で解決できる、より小さな問題に細分するための、あるいは、その、“より小さな問題”を更に小さな問題に細分するための、連続型の高レベルソリューションを使用する方法及び装置を別々に提供する。
【００１６】
本発明は、複数のアクチュエータをグループのアクチュエータに分解し、更にそのグループを、グループが、ローカルの最適なサーチが実行できるだけの数のアクチュエータを含むまで、（モジュールやサブモジュールのような）より小さなグループに分解する方法及び装置を別々に提供する。ここで、アクチュエータの分解のために、アクチュエータの位置は知られている必要は無いし、サブモジュールの詳細は、サブモジュールを含むモジュールによって知られる必要は無い。
【００１７】
本発明は、複数のアクチュエータをグループのアクチュエータに分解する方法及び装置を別々に提供する。ここで、アクチュエータのグルーピングは任意のグルーピングであり得る。
【００１８】
本発明は、最適に近いアクチュエータ割当てを計算するための時間が、アクチュエータの数とスケール（scale）するような、方法及び装置を別々に提供する。
【００１９】
本発明は、元々階層的なために、アクチュエータ割当ての計算がスマート・マター・システム及びスマート・マター・通信システムの構造に可適応な、アクチュエーションを割り当てるための方法及び装置を別々に提供する。
【００２０】
本発明は、タイル化されたアクチュエーションに適したアクチュエータ割当てための、方法及び装置を別々に提供する。
【００２１】
本発明は、マルチプロセッサによって実行させることができるアクチュエータの割当てのための方法を別々に提供する。
【００２２】
本発明の、これらの，及び他の特徴及び利点が、発明の詳細な説明中の種々の、本発明の方法及び装置に係る実施例に記述されるか、あるいは、その記述から明白である。
【００２３】
本発明に係るシステム及び方法の種々の実施例が、図面を参照して詳細に記述される。
【００２４】
【発明の実施の形態】
全システムの全体的なゴールが求められるが、上述の問題によって、その全体的なゴールを達成するために命令を実行ユニットに割当てることが困難である場合における、実行ユニットを含む、多くのタイプの多数要素システムが存在する。本発明は、その全体的なゴールの、実行ユニットのグループ（即ち、サブドメイン，あるいは実行モジュール，そして個々の実行ユニット）への割当てを提供する。このようにして、本発明によれば、実行ユニットのアレイ（array）は、要求されるゴールがサブドメインに分割されるような、サブドメインに分割される。更に、本発明によって、そのサブドメインは更に分割され得、最後のサブドメインがローカル最適サーチを実行するために十分に小さい数の実行ユニットを持つまで、その工程は継続され得る。サブドメインは、いかなる実行ユニｔットとも厳密に位置合わせする必要は無く、むしろ、サブドメインは、任意の実行ユニットのグルーピングを表し得る。更に、実行ユニットの位置あるいは配置は、全体的ゴールの分解の目的のために知られる必要がなく、より低いレベルのサブドメインの詳細は、より上位のサブドメインから隠され得る。
【００２５】
図１は、本発明による、分散されたアクチュエーション割当てを持つ、多数要素システム100の一つの模範的実施例を示す概略図である。システム100は、いかなる数の異なるタイプのアプリケーション（エア-ジェット紙輸送システム，ロボットシステム等のような、しかし、これに限定されない）でも用いられる、いかなるタイプのシステムでも有り得る。システム100は、システム割当て器110，複数の実行ユニット120，入力装置130，制御器135，及び，少なくとも一つのセンサ140を含む。
【００２６】
複数の実行ユニット120は、個々の実行ユニット150を含む。割当て器110の制御の下で、実行ユニット150は、必要な結果あるいはアクション（action）を生成するように動作する。様々な模範的実施例で、複数の実行ユニット120は、実行ユニットのアレイである。種々の模範的実施例で、実行ユニット150はアクチュエータである。他の種々の模範的実施例で、実行ユニット150は、一枚の紙の上に対して動作して、一つの位置他の位置から紙を移動させるエアジェットである。
【００２７】
入力装置130は、制御器135と、通信リンク132を介して通信する。入力装置130は、制御器135に全体的ゴールを提供する。様々な模範的実施例で、入力装置130は、システム100の全体的ゴールを生成するように構成された、コンピュータあるいはソフトウェアプログラムである。他の種々の模範的実施例では、入力ソース130は、そこでシステム100のゴールが、グラフィカル入力ソースの出力と関連付けられる、ジョイスティック，マウス，あるいは、コンピュータによって読み取り可能な他のグラフィカル入力ソースであるが、これに限定されない。他の種々の模範的実施例では、入力ソース130は、システム100を含む、より高位レベルの要素、あるいはシステムの要素である。より高位レベルの制御要素の例は、紙ハンドラに対して紙の動作ゴール（必要な軌跡）を送る、プリンタシステムのジョブスケジューラである（システム100の例）。
【００２８】
種々の模範的実施例において、全体的なゴールは、目的物の軌跡であり得るがこれに限定されないことが理解されなければならない。あるいは、他の種々の模範的実施例では、全体的なゴールは、実行ユニットの必要な状態であり得るがこれに限定されないことが理解されなければならない。
【００２９】
少なくとも一つのセンサ140は、通信リンク142を介して制御器135と通信する。少なくとも一つのセンサ140は、複数の実行ユニット150のアクチュエーションの現在の状態をモニタするか、あるいは、検知し、通信リンク142を介して状態情報を制御器135に提供する。他の種々の模範的実施で、少なくとも一つのセンサ140は、目標物の状態を検知し、その検知に応じて複数の実行ユニットが動作する。
【００３０】
制御器135は、入力ソース130から全体的ゴールを受信する。制御器135は、全体的ゴールに基づいて、システムのゴールを計算する。少なくとも一つのセンサ140を含む種々の模範的実施例で、制御器135は、少なくとも一つのセンサ140から、現在の状態情報を受信し、全体的ゴール及び現在の状態情報に基づいて命令を計算する。種々の模範的実施例で、制御器135は、比例微分制御器（proportional derivative controller）である。いかなる既知の、あるいは、後に開発された制御器も、制御器として使用され得ることが理解されなければならない。
【００３１】
種々の模範的実施例では、システムのゴールは、実行ユニット150が達成すべき、フォース（force）の割当て、命令あるいはゴールである。種々の模範的実施例では、システムのゴールは連続的な値である。他の種々の模範的実施例では、システムのゴールは離散値である。
【００３２】
割当て器110は、制御器135から命令を受信する。割当て器110は、割当てアルゴリズムを実行して、システム100のための、全体的なゴールを達成するために、どの実行ユニットがアクチュエートされるべきかを決定する。割当て器110は、少なくとも一つの通信リンクを介して、複数の実行ユニット120と通信する。
【００３３】
種々の模範的実施例では、複数の実行ユニット120は、実行ユニットのグループに分割される。実行ユニットのグループは、グループ中の実行ユニットの数が、割当て器110がローカル最適割当てサーチを実行することが許されるように、十分に小さくなるまで、更に分割され得る。
【００３４】
複数の実行ユニットは、複数の実行ユニットモジュール170及び180に分割される。種々の模範的実施例で、実行ユニットモジュール170は、個々の実行ユニット150を含む。種々の模範的実施例で、実行ユニットモジュール180は、サブモジュールとして、少なくとも一つの他の実行ユニットモジュール170を含む。種々の模範的実施例において、一つより多い実行ユニットモジュール170は、を同じ個々の実行ユニット150含む（この配置が図１に示される）。種々の模範的実施例で、一つ以上の実行ユニットモジュール180は、同じ実行ユニットモジュール170を含む（この配置が図１に示される）。複数の実行ユニット150が、更に分割され得、多くのバリエーションを持つアレイにグループ化され得ることが理解される。
【００３５】
種々の模範的実施例で、割当て器110は、全体的目標を、各モジュール170及び180に対する、解，モジュール割当て，サブ-ゴール，サブ-目標，あるいはサブ命令によって表現することによって、全体的目標を、複数の実行ユニット120割り当てる。各モジュール170及び180の解は、全体的ゴール割当てに対する解のための制約として働く。各モジュール170に対する解は、次に、更に、サブモジュールに対するサブ解に分解され得、これによって、階層的分解を提供する。階層的分解は、サブモジュールが十分に小さい数の個々の実行ユニット150を含み、そのサブモジュールに対する割当て解が、（消耗的サーチ技術のような、しかしこれに限定されない）従来の技術を用いて、迅速に実行され得るまで、割当て器110によって継続され得る。
【００３６】
種々の模範的実施例で、割当て器110は、複数の割当てレベルを含む。図１に示される模範的実施例では、割当て器110はトップレベル116，中間レベル117及びボトムレベル118を持つ。種々の模範的実施例で、割当て器110は、割当てが所望の時間的制約内で実行されるような形で、全実行ユニット通信するために、一つの割当てレベルと同じ位少ない割当てレベルから、必要なだけの多くの割当てレベルまでを含む。
【００３７】
トップレベル116は、モジュール割当て器191を含む。中間レベル117は、モジュール割当て器192及び193を含む。ボトムレベル118は、モジュール割当て器194，195，196，及び197を含む。割当てレベル116，117，及び118は、階層的配置の中で配置される。ここで、トップレベル116のモジュール割当て器191は、中間レベル117のモジュール割当て器192及び193を制御する。中間割当て器レベル117のモジュール割当て器192は、ボトム割当てレベルのモジュール割当て器194及び195を制御する。中間割当てレベル117のモジュール割当て器193は、ボトム割当てレベル118のモジュール割当て器196及び197を制御する。ボトムレベル118のモジュール割当て器194，195，196，及び197は、対応する実行グループユニット170あるいは個々の実行ユニット150を制御する。
【００３８】
図１の制御器135及びシステム制御器110は、適切なシステム，マネジャーあるいはプログラムされた一般用途のコンピュータの一部分として実行され得ることが理解されるべきである。一方、制御器135及びシステム制御器110は、ASIC,FPGA,PLA,PALを用いて、あるいは、ディスクリート・ロジック要素あるいはディスクリート回路要素のような、物理的にディティンクト（distinct）なハードウェア回路を用いて実行され得る。図１の制御器135及びシステム制御器110が取り得る特定の形式は、設計上の選択である。
【００３９】
リンク112，132，137，及び142は、いかなる、実行ユニット120，ゴール生成装置130，及び少なくとも一つのセンサ140、のそれぞれののアレイを、割当て器110に接続するための、既知のあるいは後に開発される装置あるいはシステム（ワイヤ（wire），直接ケーブル接続，ワイド・エリア・ネットワークあるいはローカル・エリア・ネットワーク上の接続，イントラネット上の接続，ワイヤレス接続，インターネット上の接続，あるいはいかなる他の分散された処理ネットワークあるいはシステム上の接続を含む。）でも有り得る。一般に、リンク112，132，137，及び142は、それぞれの装置を接続するために使用できる、いかなる既知のあるいは後に開発される通信システムあるいは構造であり得る。
【００４０】
複数の実行ユニット120，入力装置130，制御器135及び割当て器110は、物理的に一緒に位置される必要があるものではないことが理解されるべきである。更に、割当て器110及び制御器135は一つの装置内に統合され得ることが理解されるべきである。入力ソース130，制御器135，及び割当て器110は、一つの装置内に統合され得ることもまた理解されるべきである。
【００４１】
図２は、多くの実行ユニットシステム100の一つの模範的実施例である、エアジェット紙輸送システム200を示す。システム200は、割当て器と統合された制御器を含む装置の模範的実施例である、制御器/割当て器210を含む。種々の模範的実施例で、制御器/割当て器210は、割当て器110に類似する階層的割当てレベルを含む。
【００４２】
システム200はまた、エアジェットのアレイ220，及び入力ソース230，複数のセンサ240を含む。これらの装置はアレイ120，入力装置130及び少なくとも一つのセンサ140のそれぞれの模範的実施例である。
【００４３】
更に、制御器/割当て器210は、通信リンク232を介して、入力ソース230との通信状態にあり、通信リンク242を介してセンサ240と通信状態にあり、通信リンク222を介してエアジェットと通信状態にある。リンク222，232，及び242はリンク122，132及び142の模範的実施例である。
【００４４】
リンク222に沿って配置されたものは、リンク222を介して、割当て器から受信された命令に基づいて、個々のエアジェットバルブ250の開閉を制御する、少なくとも一つのバルブドライバ装置224である。少なくとも一つのバルブドライバ装置224は、いかなる既知のあるいは後に開発されるバルブドライバ装置でもあり得る。
【００４５】
リンク242に沿って配置されるものは、従来型の技術及び／又は装置を介してセンサ240から信号を受信して、リンク242を介してセンサ信号を制御器210に提供する、少なくとも一つのセンサ読出し部244である。センサ読出し部244はいかなる既知の、あるいは後に開発される装置でもあり得る。
【００４６】
オブジェクト260は、エアジェット250のアレイの上に配置される。この模範的実施例では、オブジェクト260は一片の紙である。このエアジェット250は、制御器/割当て器210の制御下で、オブジェクトを特定の位置に動かすか、あるいは、オブジェクト260を特定の方向に方向付けさせる。
【００４７】
センサ240はアレイ220中に散在する。種々の模範的な実施例で、センサ240は、アクチュエーション表面に位置するCMOSイメージセンサバーである。センサは、オブジェクト260のエッジ位置を検知するために配線されている。センサ240間の間隔は、典型的なシートサイズの紙においては、紙のエッジがセンサ240に交差する、常に少なくとも４つの点が存在するようになっている。このようにして、オブジェクト200がアレイ220上を動くにつれて、オブジェクトのｘ，ｙ，及び角度位置が決定され得る。種々の模範的な実施例で、センサ240の読出し及び位置計算は１ms以下しかかからない。
【００４８】
種々の模範的実施例では、エアジェットのアレイ220は、576個の角度付けされたエアジェットを含む。角度付けされたエアジェットは、４つの異なる方向（左，右，上，及び，下）の一つに向けられ、アレイ220中に均等に分配される。この模範的実施例では、エアジェットのアレイ220は、３６（あるいは6×6）個のエアジェトの“タイル”/アクチュエータ・モジュール270からなると考えられ得る。種々の模範的実施例で、各タイル/アクチュエータ・モジュール270は、１６個（あるいは4×4）のエアジェットを含む。アクチュエータモジュール270は、より大きなアクチュエーションモジュール280を形成するために、一緒にグループ化され得る。大きなアクチュエータモジュール280を含む実施例では、アクチュエータモジュール270は、より大きなモジュールアクチュエータ280のサブモジュールアクチュエータとして考えられ得る。本発明に従って、更に大きいアクチュエータモジュールを形成するために、より大きなアクチュエータモジュール280がグループ化され得ること、及び、アクチュエータモジュール270が更に、アクチュエーション・サブモジュールに、更に分解され得ることが理解されなければならない。
【００４９】
種々の模範的実施例で、個々のコンピュータによるアドレス可能な静電的フラップバルブ（flap valves）が、各エアジェット250を通したエアの流れを制御する。エアのソース（source）が図示されていないことにご注意頂きたい。ジェットからのエアはオブジェクト260に衝突する。オブジェクト260が一枚の紙であるような、模範的な実施例では、エアジェット250からやって来るエアは、紙をアレイ220上に浮遊させる。種々の模範的実施例で、紙は、エアジェット出口250の上に大体２ｍｍ浮遊する。紙に対する空気の粘性抵抗によって、紙上のエアの衝突点の周りの小さな円形の領域に主に閉じ込められた紙、にフォースがかかる。供給圧力１ｋＰａに対して、ジェット当り10-4Ｎｔのオーダーのフォースが、典型的である。ここに、この出願に取りこまれる、ビーゲルセン，デイビッド  Ｋ；パニデス，エイリアス；シュワルツ，ラース  Ｅ；ジャクソン，ウォレン  Ｂ；バーリン，アンドリュー  Ａ．による、“斜めに衝突するエアジェットによって誘起される、せん(剪)断応力場の特性”ＭＥＭＳ-ボリューム１，マイクロエレクトロメカニカルシステム（ＭＥＭＳ）（ＡＳＭＥ  1999），ｐｐ．385-389を見よ。
【００５０】
各エアジェット250のフォースが、線形重ね合わせとして加算される。各エアジェット250のバルブは、開閉のいずれかなので、各エアジェット250は実質的にバイナリフォースアクチュエータである。全体のアレイ220は、バイナリフォースアクチュエータの分配されたアレイとして観察され得る。種々の模範的実施例において、エアジェット250の応答時間、即ちエアジェット250がコマンド（command）に応答するために必要な時間、は、エアジェット250のフラップバルブへの印加電圧、及びエア供給圧力に依存する。種々の模範的実施例で、エアジェット250の応答時間は、典型的には、1-2ｍｓのオーダーである。
【００５１】
オブジェクト260の状態は、６個の値によって記述され得る。特に、オブジェクト260は、ｘ位置，ｙ位置，角度位置，ｘ方法の速度，ｙ方向の速度，エアジェットの平面に垂直の軸（ｚ軸）周りの角速度、を持ち得る。
【００５２】
制御器/割当て器210は、オブジェクト260を所望の全目的に向かって動かすために必要なフォースを加えるために、これらの多数のエアジェット250から選択しなければならない。このやり方は、アクチュエータへのフォース割当ての問題は、所望のマクロ-レベルアクチュエーションを、高度に分配されたマイクロ-レベルアクチュエータへ割り当る一般的な問題の場合であることを示す。この模範的実施例では、アクチュエータは、整数プログラミング問題を発生するバイナリ・エアジェットである。制御器/割当て器210は、以上の問題を解決する、本発明による、割当て方法を採用する。
【００５３】
オブジェクト260がアレイを横切って移動するに従って、シートの端部の位置は、センサ240によって検知される。これらのセンサの読みは、制御器/割当て器210によって用いられ、オブジェクト260のｘ位置，ｙ位置及び角度位置が計算される。時間に対するこの位置情報もまた、オブジェクト260のｘ速度，ｙ速度，及び角速度を計算するために用いられる。オブジェクト260の位置及び速度は、オブジェクト状態である。制御器/割当て器210は、オブジェクト状態を計算し、それを、予め定められた軌道あるいはダイナミックなき軌道、によって与えられた所望の状態（これは、元々入力ソース230からの全体的ゴールに基づく）と比較する。
【００５４】
種々の模範的実施例で、制御器/割当て器210は、複数の割当てレベルを含む。この割当てレベルのそれぞれは、階層的に配置された、少なくとも一つのモジュール割当て器（図２に図示せず）を持つ。複数のモジュール割当て器は、より大きな各モジュール・アクチュエータ280に対する、そして、各モジュール・アクチュエータ270（サブモジュール）に対する、所望のｘフォース及びｙフォース，及びｚ軸周り（オブジェクト260に垂直）のトルクを計算するために用いられる。これらのフォースは、その後、個々のエアジェト250に割り当てられ、複数のエアジェットは一緒に所望のアクチュエーションフォースを、オブジェクト260に加える。種々の模範的実施例で、この制御サイクルが、ミリセカンド（millisecond）毎に一回実行される。多の種々の模範的実施例では、制御器/割当て器210は、全体的ゴールの割当てを手助けするために、モジュール割当て器を持つ、付加的な、及び／又は、別々の割当て装置を含み得ることが理解されなければならない。
【００５５】
模範的な紙輸送システムが、以下に開示される：
（１）バーリン，アンドリュー；ビーゲルセン，デイビッド；チュング，パトリック；フロムハーツ，マルカス；ゴルドバーグ，デイビッド；ジャクソン，ウォーレン；パニデス，エイリアス；プリース，ブライアン；レイチ，ジェームス；及びシュワルツ，ラースによる、“変調されたエアジェットアレイを用いた紙輸送”，ＩＳ＆ＴｓＮＩＰ15：1999デジタル印刷技術についての国際会議，オーランド，フロリダ，10月，1999年，ｐｐ．285-288；及び（２）ビーゲルセン，デイビッド；バーリン，アンドリュー；チュング，パトリック；フロムハーツ，マルカス；ゴルドバーグ，デイビッド；ジャクソン，ウォーレン；プリース，ブライアン；レイチ，ジェームス；及びシュワルツ，ラース，“エアジェット紙移動器：メソ-スケール（Meso-Scale）ＭＥＭＳの例，”ＳＰＩＥ，マイクロマシン化された素子及び構成要素  VI，サンタクララ，カリフォルニア  ボリューム4176、９月、2000，ｐｐ.122-129”
図３は、アクチュエータのアレイ120の模範的実施例である、エアジェット320のアレイの一つの模範的実施例を示す。
【００５６】
アレイ320は、複数のエアジェット350を含む。アレイ320は、２−ｄグリッド上のＮジェットの組として変調されている。エアジェットｉ（ｉ＝1，・・・，Ｎ）は、その、
位置（ｘxi，ｙxi）；
フォースドメインｄxi及びｄyyi；及び
フォースｆxi及びｆyi（ｆxi∈ｄxi，ｆyi∈ｄyi）
によって表される。
【００５７】
位置（ｘiは352として表され、ｙiは354として表される）は、オブジェクト360の質量中心362に対して、相対的に与えられる。種々の模範的実施例で、質量中心362は近似される。しかし、他の種々の模範的実施例では、質量中心362は、制御器に提供され、あるいは、システムは質量中心362を学習するために校正される。種々の模範的実施例で、オブジェクト360の下のアクチュエータだけが、所望の時刻に変調される。
【００５８】
個々のエアジェット350のフォースドメインは、連続的間隔ｄi＝[ｆmin，ｆmax]、あるいは、いくらかの増分値ｆincに対する、可能な値の離散的な組ｄi＝｛ｆmin，ｆmin＋ｆinc，ｆmin＋２ｆinc，・・・，ｆmax｝、であり得る。種々の模範的実施例で、エアジェット350は、正負いずれかの方向に、ｘ-フォース390，あるいはｙ-フォース395だけのフォースを加え得る。種々の模範的実施例で、エアジェット350を通じたエアフローを制御するバイナリバルブのために、エアジェット350だけが、ｏｎあるいはｏｆｆとなり得る。従って、ｘ方向のエアジェットにとって、フォースドメインは、
【００５９】
【数１】
0004215995.tif 000002
0004215995.tif 000003
である。
【００６０】
同様なことがｙ方向エアジェットに当てはまる。種々の模範的実施例で、ジェットバルブが状態を変化させる時間は、一般的に、制御周期，即ち1-2ミリセカンド（milliseconds）のオーダーであり、従って、オブジェクト360の動作と比較して無視できる。従って、以下の議論において、ジェットバルブは瞬時に状態を変化（開閉）できる、ということが仮定される。
【００６１】
種々の模範的実施例で、エアジェット350は一緒にグループ化され、タイルを形成し得る。各アクチュエータ・モジュール370が、いかなる数の個々のエアジェット350をも含み得ることが理解されなければならない。エアジェット・モジュール370は、ｘ方向及びｙ方向のエアジェットの双方を含み得、これによって、ｘ-フォース要素372とｙ方向要素374の双方を持ち得る。例えば、ｎ個のｘ−ジェットとｎ個のｙ−ジェットを持ち、等しい数のジェットが正負方向を持つ、モジュール・エアジェット370のための最大フォースは、いずれかの方向のｆMAX＝ｎ/2ｆmaxである。従って、そのようなモジュール・エアジェット370のためのドメインは：
【００６２】
【数２】
0004215995.tif 000004
である。
【００６３】
アクチュエータ・モジュール370は、囲みボックスの重心として与えられ得る、あるいはその囲み内のエアジェット350の平均位置として与えられ得る、位置（376として表されるｘxi，378として表されるｙxi）を持つ。
【００６４】
種々の模範的実施例で、エアジェットモジュールは、個々のアクチュエータ350ではなくむしろ、アクチュエータ・モジュール370のグループを含む。そのようなエアジェット・モジュールの例が、380として示される。エアジェット・モジュール380は、ｘフォース要素とｙフォース要素，位置及びフォースドメイン、の双方を持つことができると言う点で、エアジェット・モジュール370と類似する。
【００６５】
一緒になって、エアジェット・モジュール370中のエアジェット350、あるいは全システム、あるいはアレイ・アクチュエータ320は、オブジェクト360に対して、ｘ−フォースＦx，ｙ−フォースＦy，及び，ｚ-トルクＴzを与える。
【００６６】
種々の模範的実施例で、アクチュエータ・モジュールｉの、フォースｆxi及びｆyiが、それぞれ、システムのｘ-フォース，ｙ-フォースに付加的に寄与する。更に、フォースｆxiが、-ｙiｆxiの形でｚ-トルク（オブジェクト360の質量中心362の周りの）に寄与し、フォースｆyiが、ｘiｆyiの形で、寄与する。言いかえれば、アクチュエータ・モジュールｉによって与えられるｚ-トルクは、ｔzi＝ｘiｆyi-ｙiｆxiである。種々の模範的実施例で、各エアジェット350が、ｘ-フォースあるいはｙ-フォースのいずれかだけを与えることを除外すれば、個々のエアジェット350についても同様のことが言える。オブジェクト360に働く、合計したｘ-フォースＦx，ｙ-フォースＦｙ，及び、ｚ-トルクＴzが、以下の線形合計モデルに従って決定される：
【００６７】
【数３】
0004215995.tif 000005
0004215995.tif 000006
図４は、本発明に従った、多くのアクチュエータシステムに対する、階層的フォース割当ての方法の１つの模範的実施例を示す。種々の模範的実施例で、多くのアクチュエータを持つシステム中の割当て器によって、この方法が採用される。種々の模範的実施例で、多くのアクチュエータを持つシステム中の、複数のレベル・アクチュエータによって、この方法が採用される。
【００６８】
アクチュエータの数が、制御コマンド（所望のゴール）Ｕ＝（ＦxＦyＦz）の次元を大きく越えるので、アクチュエータのアクチュエーションを割り当てる、多くの方法が存在する。一般的に、他の所望のゴールを得て、多くの可能なアクチュエータの配置構成の中から、最も所望される割当てを選択するために、付加的な自由度を使用することが望ましい。言いかえれば、フォース割当て問題は、制約された最適化問題として見ることができる。ここでの制約は、アクチュエータのドメイン制約と，個々のアクチュエータと全体の印加されたフォース（方程式（２）及び（３））との間の関係、の双方である。この最適化問題は、どのアクチュエータを作動さえるかを決定するための、各制御時間ステップにおいて解決される。動作は離散的なので、所望の動作の正確な生成は、必ずしも常に可能ではない。一般的に、そのような離散的最適化問題は、ＮＰ困難である。即ち、作動割当て計算スケールは、アクチュエータの数に応じて指数関数的に増加する。他方、多数のアクチュエータを持つアクチュエータのアレイにとって、作動は連続体限界（continuum limit）に近づき、問題を解決することは、ほぼ容易になる。それゆえ、フォース割当て法にとっての所望の特性は、本発明によって達成されるように、少ない数のジェットについて離散最適化問題を最適に解決し、中間的な数のジェットに対する近似最適解決を提供し、多数のジェットについての連続体（continuum）にアプローチすることである。
【００６９】
本発明による、フォースを割り当てる方法についての、種々の模範的実施例で、アクチュエーションの最適割当ては、消耗的サーチ，離散的最適化救解器（solver）、あるいは、小数のアクチュエータ（例えば、通常のデジタル信号プロセッサ上でループ時間1ｍｓで走るエアジェットの例について、１０と等しいあるいは、１０より少ない）用の、事前計算された解のルックアップテーブルによって達成され得る。本発明に従ってフォースを割り当てる方法についての、種々の模範的実施例で、多数のアクチュエータについて（例えば、典型的なデジタル信号プロセッサ上で1ｍｓのループ時間で走らせるエアジェットの例で、10個と等しいか、あるいは、10個より多い）、割当て問題は、近似的最適方法において、近似としての連続解を用いて、より小さなサブ-問題に分解される。他の種々の模範的実施例で、各サブ-問題は、更に、もっと小さなサブ−問題に分解され得るか、あるいは、もし十分に小さければ、サブ-問題は、ルックアップテーブルのような、しかし、それに限定されない、従来の方法を用いて最適に解決される。
【００７０】
本発明によってフォースを割り当てるための方法の種々の模範的実施例で、サブ-問題への分解には、アクチュエータをモジュール（アクチュエータのグループ）に分割し、その後、所望のフォースを生成する責任を、各モジュールに割り当てることが含まれる。
【００７１】
図４に示される模範的方法は、ステップＳ400から開始し、割り当てられる必要のあるゴールが受信されるステップＳ405に進む。種々の模範的実施例で、ゴールはフォースである。システム割当て器か、モジュール割当て器か、のいずれかによって制御された特定のレベルが受信される。種々の模範的実施例で、受信されたゴールが、ゴール生成装置130から割当て器110によって受信される全体的ゴールである。他の種々の模範的実施例で、受信されたゴールは、中間レベル117内に位置する割当て器114によって受信された、トップレベル116内の割当て器114からのフォース割当てである。
【００７２】
種々の模範的実施例で、トップレベル割当ては、アロケート（Ｕ，Ｉ，ｎ）（Allocate(U,I,n)）として表現される。ここで、Ｕはアクチュエータの全アレイのための全体的タスク（task）を示し、Ｕ＝（Ｆｘ，Ｆｙ，Ｆｚ）Tで表される。Ｉはアイデンティファイヤ・ストリング（identifier string）、即ち数のリスト（list of numbers）である。このＩは、システムのレベル（トップレベルは1で、“1.2”のＩは、トップレベル1内のレベル2のモジュール2を示す。）を示す。ｎは、モジュ−ルの数（number）あるいは、レベル内のジェット（トップレベルについては，ｎは1）を示す。
【００７３】
ステップＳ410では、第１のモジュールが選択される。即ち、レベル内のモジュールを表すインデックスであるｉが、1と等しい、と設定される。図１の模範的トップレベル116について、１つの割当て器だけ、従って、１つのモジュールだけが存在する。よって、そのモジュールが選択される。図１の、模範的中間レベル117では、各々が割当て器114に対応する、２つのモジュールが存在する。図１の模範的ボトムレベル118では、各々が割当て器114に対応する、４つのモジュールが存在する。
【００７４】
本方法は、ステップＳ415に進む。ここで、現在のモジュールｉが分解される。モジュールを分解するために、その分解が、全システム、即ちトップレベルに対するものか、あるいは、中間レベルのようなサブレベルに対するものか、について、分解関数が使用される。種々の模範的実施例で、分解関数は：
【００７５】
【数４】
[ni,ri,wi]=Decompose(I,i)              式（１）
のように表される。
【００７６】
分解工程は、レベルＩ内のモジュールｉを選択し、アクチュエータあるいはサブモジュールの数ｎi，サブモジュール位置ｒi＝（xi,yi），及び、以下に説明される、割当て関数のための重みｗiを戻す。この分解関数は、更に以下で説明する、モジュールの階層的分解のためのヒューリスティック（heuristic）選択を行う。もし、１つも（更なる）階層的分解が所望でなければ、即ち、現在のモジュールを、いわゆるサブモジュール即ちサブドメインに分割することが望まれなければ、その後この関数は、例えば、図１のボトムレベル118内のモジュールでなされ得るように、モジュールｉをそのｎiの実際のジェットに分解する。複数のアクチュエータの、アクチュエータモジュールへのグループ化は、予め決定され得るか、あるいは、例えば負荷バランシング基準（load-balancing criterion）に基づいて、ダイナミックに計算され得る。
【００７７】
複数のアクチュエータは、種々の方法によって、アクチュエータモジュールにグループ化され得る。種々の模範的実施例で、複数のアクチュエータの物理的レイアウトがそれに続く。例えば、複数のセンサ間の、アクチュエータの各クラスタ（cluster）が、モジュールになる。アクチュエータアレイの物理的ヒューリスティック分解の模範的実施例が、図５に示される（即ち“タイル”）。物理的ヒューリスティックの利点は、システムのモジュラ構造が、割当てアルゴリズムの、対応するモジュラ構造につながることである。種々の模範的実施例で、約360のジェットを覆う８1/2×11インチの紙について、物理的ヒューリスティックは、シートの下のエリアを、各モジュールに最大約16の実際のジェットを持つ約４０のモジュールに分解する。モジュールは、全体として、各方向に４つジェットを持つ１６の実際のジェットを含むシートによって覆われる。
【００７８】
離散的バルブとｆMAXの１つのジェットフォースであっても、そのようなモジュールは、ｆxiとｆyiのための近似連続的フォースドメインを提供する:
【００７９】
【数５】
dxi=dyi={-4fmax,-3fmax,-2fmax,-fmax,0,fmax,2fmax,3fmax,4fmax}  式（２）
他の模範的グルーピング・ヒューリスティックは、“制約に従う”あるいは論理的ヒューリスティックである。複数のアククエータの論理的ヒューリスティックグルーピングの模範的実施例が、図６に示される。例えば、以下に説明するように、同じｙ位置を持つ全てのｘジェットが、方程式（４）の制約に関して交換可能である。
【００８０】
同じｙ位置を持つｘジェットの列、及び、同じｘ位置を持つｙジェットの行は、特に、列あるいは行内の、単純な割当て関数につながる。模範的実施例で、ジェットの分解が図４に示される。ここで、Ｎ個のモジュールが、その各々が共通のｙ位置ｙiを持つｘ方向を向いたジェットだけであるＮｘ個の“ｘモジュール”と、その各々が共通のｘ位置ｘiを持つｙ方向を向いたジェットだけであるＮｙ個の“ｙモジュール”に分割される。そのようなやり方では、重み付けは、ｎxi個のジェットを持つxモジュールに対する(wxi wyi)=(nxi 0)、と、ｎyi個のジェットを含むｙモジュールに対する(0 nyi)、を特徴とする。
【００８１】
１つのレベルでのグルーピング/分解は、他の下位のレベルでのフォース割当てを非常に簡易化できる。種々の模範的実施例で、８1/2×11インチの紙について、論理的ヒューリスティクは、シートの下のエリアを、各々が最大約12の自己ジェットを持つ、約50のモジュールにグループ化する。
【００８２】
再度図４を参照すると、ステップＳ420で、現在のモジュールのためのサブ-ゴールが決定される。種々の模範的実施例で、サブ-ゴールはフォースである。サブ−ゴールあるいはフォースは：
【００８３】
【数６】
ｕi＝Solve(U,ni,ri,wi,n)    式（3）
のように表される。ここで、Ｕ＝（ＦｘＦｙＦｚ）Tは、現在のレベルでの、全モジュールに対する、所望のトータルフォース（total force）であり、ｎは現在のレベルのモジュールの数（number）であり、他の全ての入力は分解によって決定されるものであり、そして、出力ｕi＝（ｆxiｆyiｆzi）T  は、モジュールｉのための計算された割当てである。種々の模範的実施例で、Ｕは、例えばゴール生成装置130によって生成された全体的フォースである。種々の模範的実施例で、Ｕは、現在のモジュールのレベルより、更に高位のレベルからのモジュールからのフォース割当命令である。階層のレベル、あるいは、モジュール内のサブモジュールの数（number）に従って、ステップＳ420は、以下に説明する、方程式（5）及び（6）のインスタンシエーション（instantiation）を使用する。
【００８４】
ステップＳ425で、現在のモジュールが存在するレベルが、全アクチュエータアレイのボトムレベルか否かが判断される。もし、モジュールが更にサブモジュールに分解されないならば、レベルはボトムレベルである。言い替えれば、現在のモジュールは、いかなるフォースもより低位のモジュールに割当てず、むしろ、モジュールはアクチュエータに命令を与える。もし現在のモジュールレベルがボトムレベルでなければ、その後、本方法は、ステップＳ430に進む。ここで、サブ-ゴールは、次に低いレベルのモジュールに割り当てられる。この割当ては、Allocate(ui,I.i,ni)として表される。他方、もしステップＳ425で、現在のモジュールが存在するレベルがボトムレベルであると判断されれば、その後、本方法はステップＳ435に進む。ここで、サブ-ゴールは、個々のアクチュエータに割り当てられる。割当て関数は、以下のように表される：
【００８５】
【数７】
uIi=Assign(ui,I.i)     式（４）
割当て関数は、所望のアクチュエーションuIiを、モジュールI.i内のアクチュエータに割り当てる。言いかえれば、所望のアクチュエーションｕi＝（fxifyitzi）T及び１つのアクチュエータが与えられると、割当て関数は、ｘジェットに対してｆxiを、そしてｙジェットに対してｆyiを選択し得る。離散的ドメインでは、割当てはまた、ドメインから要素を選択するために、スレッシュホールディング関数を適用し得る。例えば、ドメイン{0,fmax}を持つｘジェットについては、もし、fxiがｆmax/2より大きければ、Assignは、fmaxを返し得るし、さもなければ、0を返し得る。複数のジェットを持つモジュールについては、割当て工程は、最適サーチを実行し得る。割当てはモジュールにとってはローカル（local）なので、最適割当てを事前に計算して、フォース割当てをルックアップオペレーション（lookup operation）に還元することもまた可能である。
【００８６】
モジュールの数（アクチュエータのグループあるいは１つのアクチュエータから成る）が与えられた場合の、最適割当てを生成する以下の方法、及び、所望のフォースＵの割当て、が、ステップＳ430及びＳ435のために用いられる。種々の模範的実施例で、ｘ及びｙ方向のエアジェットを持つＮ個のモジュールが存在する。各モジュールは、オブジェクトの質量中心に対する位置（xi,yi）(i=1,・・・,N)に位置する。即ち、モジュールは、位置（xi,yi）においてそのフォースを加える。種々の模範的実施例で、Ｕを生成する際に、ジェットは、互いに対抗し合って動作すべきでない（即ち、アクチュエーションは最小になるべきである。）。したがって、そのような所望の振るまいを捕捉する、可能な制約された最適化の問題は、
【００８７】
【数８】
0004215995.tif 000007
0004215995.tif 000008
である。
【００８８】
ここで、ｆi＝（ｆxi，ｆyi）は、モジュール・ジェットｉについての、割り当てられたｘ及びｙフォースであり、ｗi＝（ｗxi  ｗyi）は、ｘフォース及びｙフォースへの各モジュールの貢献のための重み付けファクター（factor）である。大きな重み付けファクターは、フォース及びトルクについての拘束を満たすに際して、モジュールのより大きな役割を想定する事態をもたらし、目標関数（objective function）を最小化するに際して、より小さな役割を想定する事態をもたらす。小さいファクターは、目標関数を強調する。この目標関数は、各モジュールがそのアクチュエーションを最小化する事態をもたらす一方、依然として、制御によって必要とされるフォースを提供する。もし、アクチベーションレベルが連続的なら、この最適化問題の解は以下で与えられる：
【００８９】
【数９】
ｉ＝１，・・・，Ｎについて、
0004215995.tif 000009
0004215995.tif 000010
【００９０】
ここで、
【数１０】
0004215995.tif 000011
0004215995.tif 000012
である。
0004215995.tif 000013
この平均を中心とした、全てのｘ及びｙのサブモジュールジェット位置の重み付けされた標準偏差である。トルクｔｚｉは、（ｘｉ，ｙｉ）に対してゼロである。
【００９１】
これらの方程式は、最適化問題に対して、連続的な解を与える。ジェットのドメインが連続的であるような、種々の模範的実施例で、これらの方程式は、最適解を与える。離散的アクチュエータで実行されるときには、各モジュールのジェットの数が多くなる（そして、ほとんど連続的なドメインを持つようになる）につれて、最適解は階層的分解で近似される。離散的アクチュエータによる実行は、以下に説明される。
【００９２】
方程式（5）及び（6）によって必要とされる全体的フォースは、大きな領域についての全体的タスクＵ＝（ＦｘＦｙＴｚ）T  の、そのサブ領域あるいはモジュールについてのタスクｕi＝（ｆxiｆyi0）Tへの分割（partitioning）を表す。
【００９３】
制約された最適化に対する方程式（5）及び（6）の解は、特定のシステムで必要とされるようにインスタンシエイト（instantiate）され得る。例えば、Ｎｘ個のｘジェット及びＮｙ個のｙジェットへの非階層的割当てについては、各ジェット“モジュール”が1つのジェットを含み、ｘジェットに対して（ｗxiｗyi）＝（1  0），ｙジェットに対して（ｗxiｗyi）＝（0  1）によって等しく重み付けされる。方程式（5）及び（6）のインスタンシエーションは、容易に導かれる。
【００９４】
システムが、個々のジェットからなるモジュールに分解されるような、２つのレベルの階層的割当てでは、モジュールサイズに基づいてアクチュエーションの割当てをシフトするために、トップレベルでの重みが使用され得る。例えば、ｎxi個のｘジェットとｎyi個のｙジェットを持つｉ番目のモジュールのために、重みは、（ｗxiｗyi）＝（ｎxiｎyi）となるように選択され得る。再度、方程式（５）及び（６）のインスタンシエーションが導出される。各モジュール内の割当ては、同じ方程式を用いた、モジュール内でのジェットへの非階層的割当てに類似している。
【００９５】
論理的に分解されたモジュールに対しては、方程式（5）及び（6）をインスタンシエートするモジュールへの割当ては、ｘ及びｙモジュールに対して、それぞれｆxiあるいはｆyiのためのみに計算される必要がある。そして、モジュール内の割当ては、ｘモジュール及びその等価物であるｙモジュールについて、方程式（７）に従う。種々の模範的実施例で、もし、論理的ヒューリスティックによって分解されたエアジェットのアレイが、同じｙ位置を持つＮｘ個のジェットだけから成るのなら、モジュールに対する割当て関数のインスタンシエーション、即ち、方程式（５）は、
【００９６】
【数１１】
0004215995.tif 000014
0004215995.tif 000015
となるであろう。
【００９７】
ステップＳ430とＳ435の後に、本方法はステップＳ440に進む。ここで、全モジュールが評価済みか否か、即ち、モジュールのためのフォースが、更に割り当てられるか、あるいは、個々のアクチュエータに割り当てられるか否かが判断される。言いかえれば、ｉがｎ（ｎはレベルのモジュル数である）と等しいか、否かが判断される。もし、ｉがｎに等しくなければ（即ち、全モジュールが評価済みでないとき）、本方法は、ステップＳ445に進む。
【００９８】
ステップＳ445では、次のモジュールが選択される。言いかえれば、ｉがｉ＋１に増加される。本方法は、その後、ｉがｎ（レベル内のモジュールあるいはアクチュエータの数）と等しくなるまで、ステップＳ415からＳ440まで戻る。言いかえれば、レベル内の各モジュールは分解され、各モジュールのためのフォースが決定され、そして、各モジュールのためのフォースが、サブモジュールに割り当てられるか、あるいは、個々のアクチュエータに割当てられる。もし、選択すべき更なるモジュールが存在しなければ、その後、次のモジュールは選択され得ず、ステップＳ440で全モジュールが評価済みかが判断される。
【００９９】
もしステップＳ440で、全モジュールが評価済み、即ち、ｉがｎと等しいと判断されれば、その後、本方法は、ステップＳ450に進む。ここで、本方法は終了する。
【０１００】
以上の模範的実施例は、1つのモジュール内の割当てが、同じレベルのいかなる他のモジュール内の割当てに依存しない、という特徴を持つ。言い替えれば、いかなる与えられたレベルでの、モジュール内の割当ては、お互いに完全に分断されており、したがって、並列動作可能で、マルチプルプロセッサに分配され得る。
【０１０１】
更に、計算の分配は、アクチュエーションと同じスケールで行われる。この特徴は、非常に多くの数のアクチュエータを持つ、多くのアクチュエータシステムにとって明白な利点である。
【０１０２】
以上の模範的実施例で、モジュールについてフォースを割り当てるための各コール（call）が、アクチュエーションを、与えられたモジュールのサブモジュールに分割する。この模範的実施例が、連続的ドメインを持つジェットに対して最適である。
【０１０３】
以上の模範的実施例は、再帰的に、アクチュエーションを、モジュールのサブモジュールに分解及び割当てる。他の種々の模範的実施例で、モジュール内に、あるいはボトムレベル内に残る、最も多いｎmaxのジェットが達成されたときに、再帰は終了する。
【０１０４】
以上の模範的実施例は、再帰的方法である。他の種々の模範的実施例で、本方法は、当業者によって明白なように、その代わりに繰り返し方法によって実行される。
【０１０５】
他の種々の模範的実施例で、以上の模範的割当て方法は、ステップS430で更にエラーを割り当てる。このエラーは、以前のモジュールのステップS430のフォース割当て中に生成される。エラーは、与えられたモジュールのための所望のゴールアクチュエーションと実際に生成されたアクチュエーションとの間の差異である。
【０１０６】
1つの模範的実施例で、エラーを割り当てる本方法は、次のモジュール割当て方法によって完成される。次のモジュール割当て方法は、ｕi-1＝（Fi-1n，Ti-1n）の、割り当てられるべき次のモジュールｉへの割当てに際して発生したフォース、及び、トルクエラーを加算する。特に：
【０１０７】
【数１２】
0004215995.tif 000016
0004215995.tif 000017
0004215995.tif 000018
は、それぞれ、（ｉ−１）番目のサブドメインの割当て中に発生した、トルク及びフォースエラーであり、Ｗは、フォースエラーに対するトルクの相対的重要度を反映する、エラー重み付けファクターである。もしＷ＝１なら、フォースエラーのみが考慮されるべきである。一方、Ｗ＝０であれば、フォースエラーを無視できて、トルクエラーのみを考慮する。ｉ番目のモジュールは、より初期の割当て中に発生したエラーの訂正を試みる。同様に、全ての子モジュール/サブモジュールが割当て済みのときには、結果としての親モジュールのエラーは、エラーをその子モジュール（即ちサブモジュ−ル）に手渡す、次の親モジュールに割当てられる。モジュールの考慮の度合いは、この実施例で、及び、他の実施例で重要で有り得る。例えば、エラー割当ては、シーケンシャル（sequential）あるいは、最も近傍の位置に対するものであり得る。種々の模範的実施例で、オブジェクト（シート）の縁部からその中央部への割当て（外から中へ）が望ましい。外から中への割当て、では、最も外側のモジュールが最初に割り当てられる。この割当てから発生したエラーは、その後、通常オブジェクトの反対側の、次に最も外側のモジュールに割当てられる。中央のモジュールが最後に割り当てられるまで、このプロセスが繰り返される。外側のモジュールは、オブジェクトに対する、最も大きいトルクを与える。外側のモジュールによって生まれる、いかなるエラーも、互いにキャンセルして帳消しにし、中央部のモジュールによって対応されるべき小さいエラー（より小さなトルクをもたらすことになる）を残す傾向がある。
【０１０８】
他の模範的実施例で、エラー割当て方法は、ユニバーサルエラー割当て（universal error allocation）である。ユニバーサルエラー割当て方法では、発生したエラーは、現在のレベル内の、全ての残りのモジュールに割り当てられる。このエラー割当ては、現在のモジュールの割当てによって発生したエラーによって、Ｔ(n-1)及びＦ(n-1)を調整することによって達成される。次のサブドメインの割当ては、新しいゴールを用いる。図７は、ドット-ダッシュされた（一点鎖線の）曲線710によって表される連続的フォースを近似するために、システムを、モジュール1，2，及び3に対して、それぞれ、モジュール701，702，及び703に分解する様子を表す図を示す。各モジュールは、その境界内で、平均的な連続的フォース密度を表すように試みる。モジュール１については、このフォースは712である。このモジュールでデリバー（deliver）される実際のフォースは、破線で示される706である。それゆえ、エラーは、斜線の四角部708によって与えられる。エラー708は、次の所望のフォース718（モジュール２の太線）を提供するために、平均の連続的フォース714から減算される。モジュール１でデリバーされたフォースが所望のフォース712より大きすぎるので、エラー708は、714から減算される。モジュール２でデリバーされたフォースは、716（破線）によって与えられる。これは、モジュール2についてのエラー（728で示される）を与える太線によって示される総計の所望のフォース718と比較して小さすぎる。このエラー728は、所望の平均連続的フォース722に付加され、所望のモジュール3フォース720（太線）を与える。モジュール3で実際にデリバーされたフォースは、破線で示される724である。それゆえ、全ての３つのモジュールの組合わせに対するエラーは726である。図７に示されるこのエラースキーム（scheme）は、多くのスキームの１つに過ぎない。他の可能なスキームには、各モジュールのエラーの等しい部分を、他に割当てることが含まれる。
【０１０９】
本発明によるエラー割当て方法のために、フォースのローカル割当ては、完全に最適である必要がない。つまり、グローバル（global）な割当てが重要なのである。
【０１１０】
実験結果
種々の代替的フォース割当てアルゴリズムを、それらの効率及び有効性について評価するために、実験結果を説明する。多数のアクチュエータを持つシステムについて特に重要なことは、それらの実行時間のスケーリング（scaling）と、アクチュエータ数に伴うフォース割当てエラーである。異なるフォース割当てアルゴリズムに対する、実行時間とエラーとの間にトレードオフが存在することが予想されるかもしれない。
【０１１１】
以下の評価について、エアジェットの簡易化されたシステムが、アクチュエータとして用いられた。このシステムは、一緒になってｙ-フォースとｚ−トルク、Ｕ＝[ＦyＴz]Tをデリバーするだけの、ｙジェットからなる。シート下の、正負ジェットの数Ｎは1-100の範囲を持ち，階層的アルゴリズムでのモジュール当りのジェットの数は５であり、トータルの結合された最大フォースは常にＦmax＝1であった（即ち、各ジェットは、1/Nのフォースをデリバーした。）。ジェットは、ドメイン｛-1/N，0，1/N｝（即ち、可能なアクチュエーション状態）を持つ離散的ジェットを生成した。
【０１１２】
子の模範的実験システム階層を分解する２つの方法が存在する。つまり、互いに隣接するジェットをモジュールにグルーピングするか、モジュ−ルを、同じｘ位置を持つ複数のジェットの列として規定するかである。いずれの場合でも、この簡易化されたシステムは、ジェットの列を用いて、シートの角度及びｙ-位置を制御することと等価である。
【０１１３】
各アルゴリズムは、実行時間及び平均割当てエラーを決定するために、ゴールフォース及びトルク値の２次元のグリッド上で評価された。グリッド評価点は、ステップサイズ0.25（対称キャンセレーションを避けるために、これに小さい擬似ランダム値が付加される）での-1から1に亘る。時間はＣＰＵ経過時間（elapsed time）である。全てのアルゴリズムは、Matlab.5.3で実行され、同一レベルにおけるモジュールに対する計算が並列運転でシミュレートされた。所望のゴールＵ＝（ＦyiＴzi）に対する結合されたｒｍｓエラーσ、及び割り当てられたアクチュエーションＵa,i＝（Ｆya,i  Ｔza,i）が、
【０１１４】
【数１３】
0004215995.tif 000019
0004215995.tif 000020
として計算された。
【０１１５】
ここで、ｗ1＝ｗ2＝0.5，及びσF及びσTは、グリッド上で、あるいはグリッドの一部上で計算されたフォースエラーとトルクエラーの標準偏差である。図８及び図９は、擬似ランダム変動を持つ、ＦyとＴzグリッドのタスク空間を示す。図８は、最適アルゴリズムに対する、グリッド上の、サンプルｒｍｓ結合エラーの描画された表現を示す。これは、大きなフォースとトルク値は、領域805に示されるように、一緒にはデリバーされ得ないことを示す。これらの大きな、不可避的エラーがをｒｍｓエラーを支配するので、ｒｍｓエラーはグリッドの密閉領域上、即ちＦmaxの90％の範囲を持つ円形部905（図９に示すように、ここでアルゴリズムが、小さなエラーで割当てることができるはずである）、で計算される。ここで図９は、評価されたフォース/トルク点の（円中の）グリッドである。
【０１１６】
この評価で、表１に示される４つのアルゴリズムが比較された。４つのアルゴリズムは：（１）グローバルサーチ（global search）を用いた最適割当て；（２）Assignの結果のSolve及び単純スレッシュホールディングでの、方程式(5)及び(6)を用いたフラットな（非階層的）割当て；（３）両レベルでのSolveで、方程式(5)及び(6)を用いた２レベルの階層的割当て；及び（４）トップレベルで、方程式(5)及び(6)を用い、より下位のレベルで最適割当てを用いた、２レベルの階層的割当て、である。最適割当てには、ｒｍｓエラーを最小化する割当て、に対する全ての可能性を通じた、総当り（brute-force）サーチが含まれる。
【０１１７】
0004215995.tif 000021
0004215995.tif 000022
【０１１８】
最適割当ては、平均割当てエラーのためのベースライン（baseline）を提供する。最適アルゴリズムの実行時間が、ジェットの数について余りにも貧弱にスケール（scale）されるので、最適アルゴリズムは、1から10のジェットの範囲でのみ評価された。結果は図１０に示される。ｒｍｓエラーは、0.4/Ｎで与えられ、補償時間は、0.04 10Nとしてスケールされる。各々1/ＮのフォースのＮ個のジェットに対するトランケーションエラーは均一な分配（uniform distribution）の±1/2Ｎなので、スケーリング（scaling）結果は、すぐに理解できる。このエラーが、フォース及びトルクグリッド上で平均されると、結果は、おおよそ1/2N√２である。これは観測値とうまく符合する。最適割当てにとって、このエラーが小さい一方、計算時間に対する指数関数的なスケーリングは、多数の数のアクチュエータを持つシステムにとっては受け入れられない。
【０１１９】
図１１は、表１の４つのアルゴリズムのエラーの（N=10ジェットでの）比較を示す。図示されるように、アルゴリズム４（モジュール内の最適割当てを伴う階層的割当て）は、サブオプチマル（suboptimal）アルゴリズム中で最良の結果をもたらす。フラットな割当てが次に良好である一方、モジュール最適化無しの階層的割当てが最も多いエラーを持つ。最適割当てを持つ階層的アルゴリズムと、最適割当てを持たない階層的アルゴリズムとを比較すると、エラーのほとんどが、モジュール内で割り当てる際のトランケーションによって発生することが示される。従って、（例えば10より少ない）小数のジェットについてさえも、最適割当ては、エラーについて、近似最適割当てスキーム以上の計算速度で、1から10のオーダーの大きさのコストで、約２のファクターだけの（factor of 2）改善をもたらす。100-1000ジェットの、より興味深い範囲においては、近似最適割当てが必要とされることが明白である。
【０１２０】
ジェットの数が10から100の範囲での、エラー及び計算時間のスケールングが、これから検討される。最適割当てが計算できない一方、種々の模範的実施例で近似最適割当てアルゴリズムのスケーリング特性は比較され得、最適割当てについてのスケーリングの法則が使用できる。ジェットの数の関数としての、評価されたアルゴリズムについての計算時間が、図１２に示される。階層的割当てアルゴリズムは、最適及びフラットアルゴリズムで、ジェットの数に従って、非常に遅い増加を示し、階層的割当てが良いスケーリング特性を示すであろうという期待が確認できた。（サブオプティマル（sub optimal）の）フラットな割当て（Alg.2）の時間は、Nに従って増加し、これは、階層的割当てと比較すると、明白に不利である。アルゴリズム３と比較した、アルゴリズム４についての、一定の損失ファクター（constant penalty factor）は、小数のジェットのために、最適割当てを計算するために必要な時間を反映したものである。実際、N=10で、比較時間は、最適割当てによって完全に支配される。この計算損失ファクターは、モジュールレベルで割り当てるために、事前に計算されたルックアップテーブルを用いることによって除去され得るし、あるいは、モジュール内の最適割当てが小さくなるような形でシステムを分解することによって除去され得る。評価されたシステムでは、後者は、上述のように、同じｘ位置のｙジェットの列からモジュールを集合することによって達成され得る。
【０１２１】
ジェットの数の関数としての、評価されたアルゴリズムのためのｒｍｓエラーが、図１３に示される。これから明白なように、最適モジュール割当て（アルゴリズム４）によっても、ジェットの数が増加するにつれて、エラーは大きくは減少しない。この振るまいは、個々のモジュール及びジェット割当てによるエラーが、他の割当てによっては補償されない、という事実の結果である。より詳細には、1/Ｎのジェットフォースで、最適モジュール割当てでは、各モジュールは、最大1/2Ｎのエラーを作る。モジュール当り５つのジェットでは、モジュール数Ｍ＝Ｎ/5で、よって、トータルのフォースエラーは、ジェットの数から独立であって、Ｍ 1/2Ｎ＝Ｎ/5 1/2Ｎ＝0.1までの大きさであり得る。最大エラーがｒｍｓ平均を支配する傾向を持つので、全てのアルゴリズムはこの値の周りに集まる。最適モジュール割当てによっても、モジュール内のジェットだけが、各々の他者のエラーを補償できる。しかし、最大エラーの式 Ｍ 1/2N から、もし、モジュールＭの数がジェットの数Ｎの増加（即ち、モジュール当りのジェットの数が増加）に対して一定に保たれれば、エラーは大まかには、Ｍ×1/2Nとしてスケール（scale）されることが明白である。
【０１２２】
上述の実験結果は、以下のようにまとめられる。多数のアクチュエータに対する割当て問題についての、エラーと計算時間との間にトレードオフが存在する。グローバリー（globally）な最適割当て（アルゴリズム１）は、最良のエラー（状態）をもたらすが、ジェット数の増加に対して不充分にスケールする。実際、（行/列分解におけるように）最適割当てが事前に計算され得ない限り、あるいは容易に計算されない限り、計算時間は、Ｎ個のジェットに対して２Nのようにスケールされる。他方、フラット割当て（アルゴリズム２）、あるいは、単純に、問題を最適に割当てられていないモジュールに分割する（アルゴリズム３）ことによって、比較的大きな割当てエラーという結果がもたらされる。実際、上述のように、支配的ｒｍｓエラーは、最大合計フォースの1/2のオーダーである。
【０１２３】
最良の妥協は、モジュール内の最適割当てによる、モジュールへの階層的分解（アルゴリズム４）である。上述のようなＭ/Ｎであるエラーのスケーリングを前提とすると、モジュ−ルのために実時間で最適割当てが計算できる、あるいは事前計算され記憶される、そのモジュールがより大きくて、それによってモジュールの数Ｍが小さくなれば、より良い結果が得られる。同時に、Ｎ／Ｍのモジュール当りのジェットを前提とすれば、モジュール当りの最適割当て時間は、２N/Mによってスケールされる。このことは、計算時間を受容可能な範囲内に維持しつつ、エラーを減少させるための、特定のＮに対する、モジュールサイズとモジュール数の間のトレードオフを示唆する。全てのアルゴリズム（最適，フラット，及び、階層的）についての、エラーと計算時間の間の関係は、
【０１２４】
【数１４】
ｌｏｇ（Ｔ）×Ｅ∝１                                  式（８）
なる関係によって説明される。ここで、Ｔは計算時間で、Ｅは分別エラー（fractional error）（フルレンジ（full range）の部分としてのエラー）である。この関係は、ローカルの最小値（local minimum）を前提とした際に、より低い最小値（lower minimum）がほとんど、どこにでも発見でき、先の最小値（previous minimum）との関係でのみ弱い（weak）場合の問題に当てはまり、及び／又は、アルゴリズムが、１つのローカルの最小値（local minimum ）から次を発見することができる確率より、少ししか、ためになることしかしない場合に当てはまる。これは、離散的ジェットからのフォース及びトルクの、結合された最適化のような場合であるように思える。
【０１２５】
しかし、もしアルゴリズムが、一定時間で決定される（即ち、事前計算された、あるいは、行/列分解におけるようにトリビアルに（trivially）計算された）、より良い近似最適（near-optimal）解を発見できれば、そしてもし、モジュール割当てが分配され得れば、計算時間が、トップレベルでのＭ個のモジュールへの割当てによって支配されるので、超線形スケーリングでさえも達成され得る。
【０１２６】
これらの結果が表２に要約される。階層的アルゴリズムにとって、計算時間はトップレベル及びモジュールレベルでの計算時間の合計であることにご注意頂きたい。Ｐ個のプロセッサが、モジュール割当てに利用可能と仮定すると、後者は更にＰによって分割され得る（特に、Ｐ＝Ｍ、即ち、モジュール当り１つのプロセッサが存在するようなケースを考えてみて欲しい）。参考のために、レベル間及びアクチュエータへのコール数（number of calls）によってスケールされる通信負荷が含まれる。
0004215995.tif 000023
0004215995.tif 000024
【０１２７】
表２は、評価されたアルゴリズム及び一定時間モジュール最適化（cto：constant-time module optimization）アルゴリズム４に対する、エラー，計算時間，及び通信時間のスケーリング法則を示す。通信負荷は、計算ノード（computational node）間を通過、及び、計算ノードからアクチュエータを通過したメッセージ数である。
【０１２８】
ハイブリッド階層-最適アルゴリズムは、全ての範囲のアクチュエータ数について良好な動作を示した。小数のアクチュエータにとって、アッパーレベル継続的割当て（continuous allocation）が、小数のモジュールに対して、あるいは１つのモジュールに対してさえ、トリビアルに（trivially）割当て可能である。モジュール内のジェットは最適に割り当てられる。非常に多数のアクチュエータに対しては（例えば＞1000）、モジュール内のジェット数は多くなり得るので、（連続体（continuum）リミット内で最適である）連続的割当てが、非常に良く動作する。より低位のレベルの最適割当てが、モジュールのより低位に対して、再帰的に、あるいは−多数存在するために−クルード（crude）だが迅速な割当てによってなされ得る。このアルゴリズムは、10＜Ｎ＜1000の中間レンジでも良く動作する。その後最適法（optimum method）を用いて解決される、近似最適の（near-optimal）より小さな問題に、最適化をガイド（guide）するために、連続体の解の漸近の（asymptotic）最適性（optimality）が使用される。従って、他のアルゴリズムと異なり、このハイブリッド階層的最適割当ては、全てのレジーム（regime）で良く動作し、異なるアプリケーションに対してアクチュエータ数が変動するにつれて、システムは再設計される必要がない。
【０１２９】
本発明のハイブリッド階層的割当ては、に実際のマイクロ電子機械システム（ＭＥＭＳ：micro-electrical-mechanical system）に適用されてきており、良く動作することがわかっている。本発明の模範的実施例は、１つのアナログ素子SHARC 40MHzDSP上での行／列割当てに対して、より下位のレベルで、一定時間最適割当て（constant time optimal allocation）により、アルゴリズム４を用いて、割当てを0.4ｍｓ以内で実行する。本発明での、模範的実施例での、８1/2×11インチのシートは、約Ｎ＝360のジェットをカバーし、行/列分解は、モジュール当り平均7から9のジェット、及び、モジュール当り最大約12のジェット（シート位置に依存する）を持つ、Ｍ＝約40から50のモジュール、なる結果をもたらす。利用可能なジェットフォースｆmaxは、ジェット当り約0.1ｍＮｔである。平均エラーは Ｍ/２ ｆmax＝20から25×ｆmaxで、時間は、データ構造を維持することによって支配される、モジュール割当ての計算の40から50倍である。結果としての位置エラーは30μｍrmsであり、10-5ラジアンのｒｍｓ角度エラーである。
【０１３０】
これは、アクチュエータ割当て方法についての、エラーと計算時間の間のトレードオフである。基本的に、計算時間のｌｏｇ（対数）×エラーは、階層的，最適割当て，及びハイブリッド-最適・階層的アルゴリズム、について一定である。従って、エラーについての小さい減少をもたらすためには、大きな計算時間の増加が必要である。しかし、割当て計算は、繰り返し実行されるので、この計算努力（computational effort）は、一回で事前計算され得る。従って、ハイブリッド階層的最適割当てスキームが、エラーと計算時間との間の最良のトレードオフを持つ。
【０１３１】
本発明のハイブリッド階層的最適アルゴリズムは、小規模の伝統的システムから、数千のアクチュエータを持つ多数のアクチュエータシステムまでの、全ての数のアクチュエータに対して良く動作する。これらの、ハイブリッド・アルゴリズムは、高次元問題への一般的なアプローチを示す。言い替えれば、本発明の模範的実施例は、問題を多くの、より小さな自己相似問題（このサイズが更に小さくされたり、あるいは、最適解を用いて解決され得る）に分割するために、連続的な解を用いる。この本発明を、ロボッティックシステムのような、そして、温度感知マイクロロボット（即ち、“スマート・ダスト（smart dust）”）、及び大規模向上、のような、しかしこれに限定されない、他の多くの自由度システムで一般的に応用すること、もまた可能である。
【図面の簡単な説明】
【図１】本発明による、多くの要素を持つシステムの模範的実施例の概略図。
【図２】本発明による、エアジェット紙輸送システムの模範的実施例の概略図。
【図３】本発明による、アクチュエータのアレイの模範的実施例の概略図。
【図４】本発明による、スマート・マッター・システムのための全体的な目的物を割当てるための方法の模範的実施例を説明するフローチャート。
【図５】本発明による、アクチュエータのアレイの物理的でヒューリスティックなグルーピングの模範的実施例の概略図。
【図６】本発明による、アクチュエータのアレイの論理的にヒューリスティックなグルーピングの模範的実施例の概略図。
【図７】本発明の一つの模範的実施例による、複数のサブドメインを通したエラー割当ての方法を表す図。
【図８】最適割当てアルゴリズムのために、グリッド上でｒｍｓ結合されたエラーのサンプルの画像表現を表す図。
【図９】隆起したフォース/トルク点のグリッド（円形の内部）を表す図。
【図１０】最適フラット割当てアルゴリズムのための、ｒｍｓエラー及び計算時間のスケーリングを表す図。
【図１１】４つの異なった割当てアルゴリズムのためのフォース/トルクグリッドの中央領域のための、ｒｍｓ，最大，及び個々のエラーを表す棒グラフ。
【図１２】４つの異なった割当てアルゴリズムの計算時間のスケーリングを示す図。
【図１３】３つの異なった割当てアルゴリズムのエラーのスケーリングを示す図。
【図１】
0004215995.tif 000029
【図２】
0004215995.tif 000030
【図３】
0004215995.tif 000031
【図４】
0004215995.tif 000032
【図５】
0004215995.tif 000033
【図６】
0004215995.tif 000034
【図７】
0004215995.tif 000035
【図８】
0004215995.tif 000036
【図９】
0004215995.tif 000037
【図１０】
0004215995.tif 000038
【図１１】
0004215995.tif 000039
【図１２】
0004215995.tif 000040
【図１３】
0004215995.tif 000041