(57)【要約】【課題】隊列制御動作にかかる時間を短縮することができる制御技術を提供する。【解決手段】制御装置は、制御対象物単位は複数あり、各制御対象物単位は複数個の制御対象物から構成されており、各制御対象物単位の周囲には他の制御対象物単位を構成する制御対象物が移動可能な空隙が有り、各制御対象物単位には所定の目標位置が定められており、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、上記選択された目標位置に移動させる制御対象物単位を選択する制御対象物単位選択部１と、制御対象物構造の接続性を維持しながら、上記選択された制御対象物単位を上記目標位置に移動させる制御対象物単位移動制御部２と、を備えている。【選択図】図１
2019040580.tif 000002
【特許請求の範囲】
【請求項１】
制御対象物単位は複数あり、各制御対象物単位は複数個の制御対象物から構成されており、各制御対象物単位の周囲には他の制御対象物単位を構成する制御対象物が移動可能な空隙が有り、各制御対象物単位には所定の目標位置が定められており、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、
制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、上記選択された目標位置に移動させる制御対象物単位を選択する制御対象物単位選択部と、
制御対象物構造の接続性を維持しながら、上記選択された制御対象物単位を上記目標位置に移動させる制御対象物単位移動制御部と、
を含む制御装置。
【請求項２】
請求項１の制御装置であって、
上記制御対象物単位は三次元直交座標系で各軸方向に長さＭを有する立方体形状の空間内の部分構造であり、上記立方体形状の空間内の制御対象物単位に含まれる制御対象物の数と上記立方体形状の空間内の制御対象物単位以外の部分の数とが等しく、上記制御対象物単位は各軸方向にＭ個の制御対象物が隣接する構造を含む、
制御装置。
【請求項３】
請求項１又は２の制御装置であって、
上記制御対象物単位選択部は、上記選択された目標位置を目標位置とする制御対象物単位を選択し、
上記制御対象物単位移動制御部は、上記選択された制御対象物単位を上記目標位置に移動させるときに制御対象物構造の接続性が維持されるかどうか判定し、(1)制御対象物構造の接続性が維持されると判定された場合には、上記選択された制御対象物単位を上記目標位置に移動させ、(2)制御対象物構造の接続性が維持されないと判定された場合には、上記選択された制御対象物単位の位置に制御対象物構造の接続性を維持しながら移動することができる制御対象物である交換制御対象物単位を選択し、上記選択された交換制御対象物単位を上記選択された制御対象物単位の位置に移動させた後に上記選択された制御対象物単位を上記目標位置に移動させ、
制御対象物単位が到達していない目標位置がなくなるまで、上記制御対象物単位選択部及び上記制御対象物単位移動制御部の処理を繰り返す制御部、
を更に含む制御装置。
【請求項４】
請求項２又は３の制御装置であって、
各制御対象物単位には所定の初期位置が更に定められており、上記目標位置の集合及び上記初期位置の集合の積集合を共通位置の集合として、
上記制御対象物単位選択部は、上記選択された目標位置を目標位置とする制御対象物単位を仮に選択し、(a)上記仮に選択された制御対象物単位の位置が上記共通位置の集合に含まれない場合には、上記仮に選択された制御対象物単位を選択し、(b)上記仮に選択された制御対象物単位の位置が上記共通位置の集合に含まれる場合には、上記仮に選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択し、上記新たに選択された制御対象物単位の位置が上記共通位置の集合に含まれる場合には、上記新たに選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択するという処理を、上記新たに選択された制御対象物単位の位置が上記共通位置の集合に含まれないようになるまで繰り返すことにより、繰り返しの最後の新たに選択された制御対象物単位を選択し、
上記制御対象物単位移動制御部は、上記(a)の場合には、上記(1)又は(2)の処理を行い、上記(b)の場合には、上記(1)又は(2)の処理の後に、上記新たに選択された制御対象物を目標位置に移動させ、上記仮に選択された制御対象物単位を目標位置に移動させ、
上記制御部は、制御対象物単位が到達していない目標位置であって、上記目標位置の集合に含まれるが上記共通位置の集合に含まれない目標位置がなくなるまで、上記制御対象物単位選択部及び上記制御対象物単位移動制御部の処理を繰り返し、
制御対象物単位が到達していない目標位置であって、上記共通位置の集合に含まれる目標位置を選択し、上記選択された目標位置にある制御対象物単位を仮に選択し、上記仮に選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択し、上記新たに選択された制御対象物単位の位置が上記仮に選択された制御対象物単位の目標位置でない場合には、上記新たに選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択するという処理を、上記新たに選択された制御対象物単位の位置が上記仮に選択された制御対象物単位の目標位置になるまで繰り返し、最後に選択された制御対象物単位を選択する共通位置制御対象物単位選択部と、
上記選択された制御対象物単位を目標位置に移動させるときに制御対象物構造の接続性が維持されるかどうか判定し、(1)制御対象物構造の接続性が維持されると判定された場合には、上記選択された制御対象物単位を目標位置に移動させ、上記新たに選択された制御対象物単位を目標位置に移動させ、上記仮に選択された制御対象物単位を目標位置に移動させ、(2)制御対象物構造の接続性が維持されないと判定された場合には、上記選択された制御対象物単位の位置に制御対象物構造の接続性を維持しながら移動することができる制御対象物である交換制御対象物単位を選択し、上記選択された交換制御対象物単位を上記選択された制御対象物単位の位置に移動させた後に上記選択された制御対象物単位を目標位置に移動させ、上記新たに選択された制御対象物単位を目標位置に移動させ、上記仮に選択された制御対象物単位を目標位置に移動させ、上記交換制御対象物単位を目標位置に移動させる共通位置制御対象物単位移動制御部と、
制御対象物単位が到達していない目標位置であって、上記共通位置の集合に含まれる目標位置がなくなるまで、上記共通位置制御対象物単位選択部及び上記共通位置制御対象物単位移動制御部の処理を繰り返す共通位置制御部と、
を更に含む制御装置。
【請求項５】
請求項１又は２の制御装置であって、
上記制御対象物単位選択部は、上記選択された目標位置に移動するときに上記制御対象物構造の接続性が維持される制御対象物を選択し、
制御対象物単位が位置していない目標位置がなくなるまで、上記制御対象物単位選択部及び制御対象物単位移動制御部の処理を繰り返す制御部と、
各制御対象物単位が上記各制御対象物単位の目標位置に到達するように制御対象物単位の位置を入れ替える処理を制御対象物構造の接続性を維持しながら行う制御対象物単位入替部と、
を更に含む制御装置。
【請求項６】
請求項１又は２の制御装置であって、
上記制御対象物単位の初期位置の集合と上記目標位置の集合とは接しているとし、上記初期位置の集合に含まれる位置であって上記目標位置の集合に接している位置の１つを接続位置として、
各制御対象物単位が上記接続位置を通るように、かつ、各制御対象物単位が上記接続位置を通過した後は上記接続位置からの距離が近くならないように、各制御対象物単位が目標位置に到達するまでのパスを上記接続位置から遠い初期位置にある制御対象物単位のパスから順に決定するパス決定部と、
各制御対象物単位が衝突しないように、各制御対象物単位の待ち時間を決定する待ち時間調整部と、を更に含み、
上記制御対象物単位選択部は、上記パス決定部により決定されたパスに従って移動させる制御対象物単位を選択し、
上記制御対象物単位移動制御部は、上記パス決定部により決定されたパス及び上記待ち時間調整部により決定された待ち時間に従って、上記制御対象物単位選択部により選択された制御対象物単位を移動させる、
制御装置。
【請求項７】
制御対象物単位は複数あり、各制御対象物単位は複数個の制御対象物から構成されており、各制御対象物単位の周囲には他の制御対象物単位を構成する制御対象物が移動可能な空隙が有り、各制御対象物単位には所定の目標位置が定められており、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、
制御対象物単位選択部が、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、上記選択された目標位置に移動させる制御対象物単位を選択する制御対象物単位選択ステップと、
制御対象物単位移動制御部が、制御対象物構造の接続性を維持しながら、上記選択された制御対象物単位を上記目標位置に移動させる制御対象物単位移動制御ステップと、
を含む制御方法。
【請求項８】
請求項１から６の何れかの制御装置の各部としてコンピュータを機能させるためのコンピュータ読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の制御対象物の行動を制御する技術に関する。
【背景技術】
【０００２】
近年、多数の自律移動ロボットを効率的に制御にするための研究が活発に行われている。その任務内容は、人の入れない箇所の監視、物品の搬送などさまざまであるが、多数のロボットの協調動作による隊列形成を効率的に行わせるための技術が求められており盛んに研究が行われている。
【０００３】
特に、ロボットの隊列制御の中でも、ロボット同士が互いに接したままの状態で、アメーバのように全体で移動を行うという仮定の下でのロボット隊列制御においては、ロボット同士の相対的な位置関係から、各ロボットの絶対位置の決定が可能であるという利点と、付加的な位置計測用の装備を必要としないという利点があり、そのようなロボットの研究もおこなわれている（例えば、非特許文献１，２参照。）。
【０００４】
非特許文献１は、全てのロボットが同じ性質を持つ（ホモジニアス）という前提の下で、任意の初期隊列形成状態から目的隊列形成状態へ変形する隊列制御を実現する方法が開示されている。ここでは、８つのロボットを１つの単位として移動させることで、従来よりも効率的な隊列制御を実現している。
【０００５】
非特許文献２では、各矩形ロボットが異なる性質を持つ(ヘテロジニアス)という前提の下で、任意の形状隊列から他の形状隊列へ変形する隊列制御の方法が開示されている。
【０００６】
このような、多数のロボットによる効率的な隊列形成を実現するには、それぞれのロボットの配置、動作順序などを事前に計画することが重要である。このような計画においては、当然ながら、複数のロボットが動作する実環境における障害物の存在や経路の形状なども十分に考慮しなければならない。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Kawano, H., “Complete Reconfiguration Algorithm for Sliding Cube-shaped Modular Robots with only Sliding Motion Primitive”, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS 2015), pp.3276-3283, September 2015, Hamburg, Germany.
【非特許文献２】R. Fitch, Z. Butler, D. Rus, “Reconfiguration Planning for   Heterogeneous Self-Reconfiguring Robots”, in Proc.2003 IEEE/RSJ  Int. Conf. Intelligent Robots and Systems, pp. 2460-2467, Las Vegas, NV, Oct., 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献２では、各ロボットが接した状態での動作を想定し、各ロボットが異なる特性（ヘテロジニアス）である、つまり、各ロボットの目標位置が特定されている場合の隊列制御を実現している。このような隊列制御は、例えば、カメラを搭載したロボット、車輪を搭載したロボット等の個々に異なる役割がある各ロボットをロボット隊列内の適切な位置に配置させつつ、隊列の形状を制御するといった運用に適している。
【０００９】
非特許文献１はホモジニアスを前提としており、隊列変形後の各ロボットの位置が保証されないため、ヘテロジニアスを前提とするような隊列形成の問題に適用することができない。
【００１０】
非特許文献２は、ヘテロジニアスを前提とする隊列形成を行うことができるが、隊列全体の形状の変形動作と、変形後のロボット位置入れ替えを別個のプロセスとして行わなければならない。つまり、まずロボットの位置は問わずに形状（隊列）を目的隊列に変形する前に、各ロボットの位置が正しい目標位置となるように各ロボットの位置の入れ替えを行うための別の隊列形態をとり、ロボットの位置の入れ替えを行うのである。そのロボット位置入れ替えの処理に非常に時間を要するため、全体として隊列制御にかかる時間が長いという問題がある。
【００１１】
このような現状に鑑みて、本発明は、隊列制御動作にかかる時間を短縮することができる制御装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
この発明の一態様による制御装置は、制御対象物単位は複数あり、各制御対象物単位は複数個の制御対象物から構成されており、各制御対象物単位の周囲には他の制御対象物単位を構成する制御対象物が移動可能な空隙が有り、各制御対象物単位には所定の目標位置が定められており、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、上記選択された目標位置に移動させる制御対象物単位を選択する制御対象物単位選択部と、制御対象物構造の接続性を維持しながら、上記選択された制御対象物単位を上記目標位置に移動させる制御対象物単位移動制御部と、を備えている。
【発明の効果】
【００１３】
本発明に拠れば、隊列制御動作にかかる時間を短縮することができる。
【図面の簡単な説明】
【００１４】
【図１】ロボットの移動を説明するための図。
【図２】制御対象物の初期位置及び目標位置を説明するための図。
【図３】ボイドの移動の様子を説明するための図。
【図４】制御対象物単位を説明するための図。
【図５】制御対象物単位の移動を説明するための図。
【図６】制御対象物構造の非連続について説明するための図。
【図７】制御対象物構造の連続性を維持するための制御を説明するための図。
【図８】制御対象物単位の移動を説明するための図。
【図９】制御対象物単位の移動を説明するための図。
【図１０】制御対象物単位の移動を説明するための図。
【図１１】制御対象物単位の移動を説明するための図。
【図１２】制御対象物単位の移動を説明するための図。
【図１３】制御対象物単位の移動を説明するための図。
【図１４】制御対象物単位の移動を説明するための図。
【図１５】制御対象物単位の移動を説明するための図。
【図１６】制御対象物単位の移動を説明するための図。
【図１７】制御対象物単位の移動を説明するための図。
【図１８】第一実施形態の制御装置を説明するためのブロック図。
【図１９】第一実施形態の制御方法を説明するための流れ図。
【図２０】第二実施形態の制御装置を説明するためのブロック図。
【図２１】第二実施形態の制御方法を説明するための流れ図。
【図２２】第三実施形態の制御装置を説明するためのブロック図。
【図２３】第三実施形態の制御方法を説明するための流れ図。
【図２４】第四実施形態の制御装置を説明するためのブロック図。
【図２５】第四実施形態の制御方法を説明するための流れ図。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００１６】
＜理論的背景＞
まず、行動制御システム及び方法の理論的背景について説明する。以下の説明において、制御対象物は、ロボットである。制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００１７】
［問題設定］
任意の隊列形成を初期隊列形成状態として、制御対象物同士が接したままの状態を維持しつつ目的とする任意の隊列形成状態である目的隊列形成状態への隊列を移動させる隊列制御を、多数の制御対象物が協調して行う任務を、例えば図１に例示するような、互いに接する面同士をスライドさせて移動していくことが可能な立方体型の制御対象物の制御を想定して実現する。この隊列制御は、図２に示すように、壁で区切られた部屋（ただし図中、壁を省略する）において、初期位置における隊列から目標位置における隊列への変形を、複数の制御対象物の移動によって実現するものである。
【００１８】
制御対象物については、例えば図１に示すように、制御対象物の周囲縦横高さ方向（以下「上下左右前後方向」ともいう）６マスのうち１つに他の制御対象物が存在している（１つの面を他制御対象物と共有している）状態を維持しながら移動をするものとする。この手法では１つの制御対象物自身が、一個の制御対象物のサイズ分の距離を移動することで、一回の動作の移動量を正確に測ることができるというメリットがある。また、１つの面を共有する隣り合う制御対象物との相対的な位置を計測しあうことで、制御対象物の群れ全体の中での各制御対象物の位置も容易に知ることができる。このため、制御対象物の移動量の誤差によって、隊列が崩れるといった問題を起こしにくく、また、各制御対象物の位置を把握するために付加的な位置計測用の装備を備えずとも位置の把握が可能である。また、複数の制御対象物を連結したように、同時に複数の制御対象物を移動させていくことが可能である。なお、制御対象物は、隣の位置に他の制御対象物が存在しているか否か、障害物があるか否か、そして、自身が目標位置上にいるかどうかを知ることができるものとする。
【００１９】
任務を行う制御対象物は、p個（p≧12=4×3）であり、各制御対象物は、隣接する制御対象物と一面以上を共有しつつ、三次元空間におけるX-Y-Z軸方向に移動可能とする。本発明では、制御対象物は図４の右図に示すような４つの制御対象物で構成される制御対象物群を最小単位（制御対象物単位）として移動を実現するので、制御対象物の総数pは４の倍数とする。
【００２０】
図１の各立方体は、それぞれの制御対象物の位置を示すものである。各立方体には制御対象物は一個しか存在することができない。それぞれの制御対象物は、移動しようとする方向に障害物か他の制御対象物がある場合には、静止をするものと仮定する。なお、制御対象物が存在しうる立方体状の空間をマス、または、格子ともいう。図２において、色が塗りつぶされたマスは制御対象物が存在する位置を示す。図２Ａの制御対象物が存在する位置は制御対象物の初期位置の集合（初期隊列形成状態）を示し、図２Ｃの制御対象物が存在する位置は制御対象物の目標位置の集合（目的隊列形成状態）を示す。図２Ｂに示すように、目標位置の集合と初期位置の集合は接している。目標位置の集合で表される領域を目標隊列エリアともいう。このように、各初期位置及び各目標位置は、それぞれ縦横高さ方向の少なくとも何れかの方向において他の初期位置及び目標位置と隣接し、制御対象物の初期位置及び目標位置での隊列形状はそれぞれ一塊の任意の形状である。
【００２１】
なお、初期隊列形成状態と接しない位置を目的隊列形成状態としたい場合には、初期隊列形成状態と目的隊列形成状態との間にそれぞれ直前の隊列形成状態に隣接するような中間隊列形成状態を複数設定し、時間的に隣接する隊列形成状態をそれぞれ初期隊列形成状態と目的隊列形成状態として上述の隊列形成を行うことを繰り返すことで最終的に目的隊列形態に変形させることができる。
【００２２】
［制御対象物の座標設定］
それぞれの制御対象物i（iは制御対象物番号を表すi=0,1,2,3,…,p-1）の位置を（Xr[i],Yr[i],Zr[i]）とし、初期位置を（Xr0[i],Yr0[i],Zr0[i]）とし、目標位置を（Xre[i],Yre[i],Zre[i]）とするとき、本問題は、初期位置に配置された制御対象物が、目標位置まで移動するための行動計画を求めることと定義できる。制御対象物の初期位置（Xr0[i],Yr0[i],Zr0[i]）の集合をs、目標位置（Xre[i],Yre[i],Zre[i]）の集合をgとする。
【００２３】
［任務空間の定義］
iを制御対象物番号としたとき、制御対象物iの各状態（制御対象物の位置と行動）は離散値で表現される。部屋をX,Y,Zの直交座標系からなる３次元空間で表すと、X軸、Y軸、Z軸をそれぞれ離散化表現した値により各位置を表現する。つまり、部屋（３次元空間）は格子で区切られ、各格子が各位置に対応する。また、各格子において、障害物の「ある／なし」が予め設定されている。
【００２４】
［動作の定義］
例えば、制御対象物である行動主体は部屋に配置されている各制御対象物である。制御対象物i（iは制御対象物番号）の行動aは、静止、縦横高さ方向への１格子分の移動、の計７種類のうちのいずれかを取る。例えば、a∈{0,1,2,3,4,5,6}として、
0: 静止
1: 三次元空間内でX軸正方向に１格子だけ移動する
2: 三次元空間内でY軸正方向に１格子だけ移動する
3: 三次元空間内でX軸負方向に１格子だけ移動する
4: 三次元空間内でY軸負方向に１格子だけ移動する
5: 三次元空間内でZ軸正方向に１格子だけ移動する
6: 三次元空間内でZ軸負方向に１格子だけ移動する
とする。
【００２５】
［探索計算上の問題点］
このような任務環境における状態空間は、制御対象物数×３の次元数の状態を持ち、かつ選択可能な行動数は、制御対象物の行動（＝7通り）の制御対象物数乗だけ存在する。例えば、制御対象物数が50で、部屋の縦横高さ方向の格子数がそれぞれ20であるとすれば状態数は20の150乗個にもなり、探索計算に要する資源の量は膨大なものとなる。さらに制御対象物数が1個増えるごとに、その状態数は8000倍増加していくことになる。[問題設定]の項で説明したように、制御対象物同士が接しているという拘束条件を取り入れる場合、制御対象物のお互いの移動を考慮したうえで探索計算を行わなければならないために、根本的な計算量の削減は難しく、複数の制御対象物を使用する場合の大きな問題となっている。
【００２６】
[参考文献３におけるヘテロジニアス隊列制御における特徴]
参考文献３におけるヘテロジニアス隊列制御では、上述の計算負荷の問題を解決するための方策の１つとして、ボイド制御の考え方を導入している。また、［問題設定］で述べたような隊列変形の問題を克服するために８マス制御対象物単位の考え方も導入している。
【００２７】
まず、ボイド制御について説明する。ここでいうボイドとは、ある制御対象物が別の位置に移動した後に、元いた位置にできる空隙のことである。別の言い方をすると、ボイドとは、制御対象物の移動する方向と反対の方向に移動する仮想的な存在である。こうした群制御対象物の隊列形成問題においては、複数の制御対象物の動作に着目するがゆえに、その探索計算量が爆発してしまうが、視点を変えて、ボイドの動きに着目すれば、多数の制御対象物の動作計画の問題を単一のボイドの動作計画として考えることができ、探索計算負荷の軽減に適している。制御対象物の移動に伴ってボイドが移動していく様子を示す図を図３に示す。しかし、参考文献３では、フルに充填された８マス制御対象物の構造を採用しているために、制御対象物の移動のためにボイドを構造内に意図的に生成しなければならず、そのため、隣接していない制御対象物同士の行き来には不自由な点が多かった。そのため、隊列の全体形状変形の際に、同時に各制御対象物を目標位置まで到達させるための移動を同時に行いにくかった。
【００２８】
〔参考文献３〕Kawano, H., “Tunneling-Based Self-Reconfiguration of Heterogeneous Sliding Cube-Shaped Modular Robots in Environments with Obstacles”, 2017 IEEE International Conference on Robotics and Automation, pp.825-832, May 2017, Singapore.
［周囲に空隙を有する制御対象物単位の導入]
そこで本発明では、周囲に空隙を有する制御対象物単位を隊列の基本構成要素とし、隊列はこの制御対象物単位が複数接続することで構成され、制御対象物は、この制御対象物単位を維持しつつ移動を行うこととする。例えば、図４に示すように、４つの隣接した制御対象物を１つの単位（制御対象物単位）とし、制御対象物は、この制御対象物単位を維持しつつ移動を行う。言い換えると、４個毎に１つの制御対象物単位を構成し、１つの制御対象物単位を構成する４個の制御対象物は隣接した状態を維持しつつ移動を行う。制御対象物単位の集団は、互いに制御対象物単位ごとに少なくとも一面を共有し、接しながら移動をするように制御される。つまり、接続性を保ったまま隊列変形を行うこととする。また、同じ制御対象物単位に所属する４つの制御対象物は同一（ホモジニアス）であるとする。つまり、同じ制御対象物単位内では、どの制御対象物が単位内のどの位置にあるかは問わないものとする。
【００２９】
図４の例に限らず、制御対象物単位は以下の条件を満たすよう構成されていればよい。すなわち、制御対象物単位は、（１）三次元の直交座標系で各軸方向に長さＭ（Ｍ≧２、ただし、制御対象物１個の長さを長さ１とする）を有する立方体形状の空間（以降この空間をメタモジュールとする。）内の部分構造であり（言い換えれば、制御対象物単位はメタモジュールの一部を占め）、（２）当該メタモジュール内の制御対象物単位に含まれる制御対象物の数と、当該メタモジュール内の制御対象物単位以外の部分（すなわち空隙）の数とが等しく、（３）各軸方向にＭ個の制御対象物が隣接する構造を含む。例えば、図４に例示する制御対象物単位は、（１）各軸方向の長さＭ＝２とした計８マスの立方体からなるメタモジュールの部分構造であり、（２）制御対象物単位内の制御対象物の数が４個、メタモジュール内の空隙の数が４個と等しく、（３）各軸方向において２個の制御対象物が隣接する構造が含まれている。
【００３０】
このような制御対象物単位を１つの単位とした移動を行う理由は、各制御対象物単位の周囲（メタモジュールの内部）にある複数の空隙空間を、他の制御対象物単位に属する制御対象物が通過することができ、それにより、隣接していない制御対象物単位内に属する制御対象物同士が行き来することが容易である点である。また、各制御対象物単位の周囲（メタモジュールの内部）にある複数の空隙空間を、他の制御対象物単位に属する制御対象物が通過する際の接続性の維持も容易である。すなわちこれは、隊列形態の維持を考量しなければならない各制御対象物の動作の決定において、制御対象物同士の接続を考慮するための計算負荷を軽減することにつながるからである。このように、本発明は、制御対象物単位が周囲に空隙を有するような構成を基本単位とすることにより、計算負荷の削減を実現することを特徴とするものである。以後の説明では、制御対象物単位の一例として、図４に示す４個の制御対象物からなる構造を制御対象物単位とする場合について説明するが、Ｍ３個分の大きさのメタモジュール内で上述の（１）〜（３）の条件を満たすよう構成された制御対象物単位であれば同様の効果を得ることができる。
【００３１】
ここでは４個の制御対象物がなす制御対象物単位が１つのマスの単位（本実施形態では、以下、この単位を「マス単位」または「位置単位」ともいう）であるとし、１つのマス単位を一状態として取り得る制御対象物単位位置の集合からなる状態のうち、初期状態を集合S、目標状態を集合Gとする。なお、以下では、集合Sを、初期位置の集合S又は初期位置Sと呼ぶこともある。同様に、集合Gを、目標位置の集合G又は目標位置Gと呼ぶこともある。ある制御対象物単位jの位置を（Xr_u[j],Yr_u[j], Zr_u[j]）（j=0,1,2,…j_max-1）としたとき、その制御対象物単位j内の制御対象物をj1,j2,j3,j4とすれば、
Xr[j1] = 2 × Xr_u[j] 
Yr[j1] = 2 × Yr_u[j] + 1
Zr[j1] = 2 × Zr_u[j] 
Xr[j2] = 2 × Xr_u[j] + 1
Yr[j2] = 2 × Yr_u[j] 
Zr[j2] = 2 × Zr_u[j] 
Xr[j3] = 2 × Xr_u[j]
Yr[j3] = 2 × Yr_u[j]
Zr[j3] = 2 × Zr_u[j]
Xr[j4] = 2 × Xr_u[j]
Yr[j4] = 2 × Yr_u[j]
Zr[j4] = 2 × Zr_u[j] + 1
ここで、j_maxは制御対象物単位の総数、すなわちj_max=p/4であり、jは制御対象物単位を特定するIDに相当するものである。
【００３２】
なお、各制御対象物iが所属する制御対象物単位jは隊列制御のどの時刻においても不変である。また、各制御対象物単位jの初期位置を（Xr_u0[j],Yr_u0[j],Zr_u0[j]）とし、目標位置を（Xr_ue[j],Yr_ue[j],Zr_ue[j]）とする。
【００３３】
以下、制御対象物単位に属する制御対象物を移動させることを、制御対象物単位を移動させると略記することもある。
【００３４】
このように、４個の制御対象物により構成される制御対象物単位で移動の制御を行うことにより、８個の制御対象物により構成される制御対象物単位で移動の制御を行っていた従来よりも少ないステップ数で隊列の変形が可能となる。
【００３５】
［ヘテロジニアス制御対象物隊列制御］
初期位置（Xr_u0[j],Yr_u0[j],Zr_u0[j]）にある各制御対象物単位jの集合Sにより形成される初期位置における隊列から、目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）にある各制御対象物単位jの集合Gにより形成される目標位置における隊列へ各制御対象物単位を移動させるヘテロジニアス制御対象物隊列制御の方法について以下説明していく。
【００３６】
ある時刻において、制御対象物単位jの目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）が空隙のままであり、かつ目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）に隣接する制御対象物単位の位置内に制御対象物単位j'に属する制御対象物が４つ存在しているとする（図５Ａ）。この場合、p個の制御対象物からなる隊列内には非接続な箇所はなく、かつ各制御対象物単位内には、制御対象物が通過可能な空隙が４つ用意されているため、制御対象物構造内のある位置に存在する制御対象物単位jに属する制御対象物４つが、制御対象物構造内の空隙を伝って、制御対象物単位j'内の空隙に移動することは可能である(図５Ｂ、図５Ｃ)。そして、４つの空隙が制御対象物単位jに属する制御対象物によって埋められた状態の制御対象物位置j'から、隣接する位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）に制御対象物単位jに属する４つの制御対象物を排出して、目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）にて、制御対象物単位jの基本形状を形成させることも可能である（図５Ｄ）。
【００３７】
ここで、注意しなければならないのは、制御対象物単位jに属する制御対象物が制御対象物単位j'へ移動中には、制御対象物単位jの制御対象物があった場所が空隙になってしまうという事実である。すると、制御対象物単位jを移動させることで、残りの制御対象物からなる隊列の接続性が維持されず、非連続状態となってしまう場合がある（図６）。図６では、図６Ｂから図６Ｃの状態に移行するときに、制御対象物単位jがあった位置が空隙となり、非連続状態が発生している。
【００３８】
このため、制御対象物単位jの位置によっては、制御対象物構造の接続を維持しつつ制御対象物単位jを移動させるために工夫が必要である。ここで、制御対象物単位jが制御対象物構造から取り払われる（現在の制御対象物隊列における制御対象物単位jの位置から移動する）際に、制御対象物構造が接続を維持できるかどうかの条件として、以下の式を用いる。
【００３９】
δ(j)＞δ(j_n)…式(A)
ここで、δ(j)は、制御対象物単位jの制御対象物単位j'からのマンハッタン距離である。そして、j_nは、制御対象物単位jに隣接している制御対象物単位を一意に識別するための番号であり（nは正の整数）、δ(j_n)は制御対象物単位j_nの制御対象物単位j'からのマンハッタン距離である。全ての制御対象物単位j_nに対して式(A)が成立するならば、制御対象物単位jを制御対象物構造から取り払ったとしても制御対象物構造の接続性は維持できる。
【００４０】
そこで、制御対象物単位jの制御対象物単位j'の位置への移動を開始する前に、式(A)による判定を行い、その結果、δ（j）>δ（j_n）を満たさない制御対象物単位j_nが存在するならば、以下の方法をとる。
【００４１】
(1) δ(j_end)>δ(j)を満たす制御対象物単位j_endのうち、制御対象物単位j_endに隣接する全ての制御対象物単位j_end_n（ここでnはj_endに隣接する制御対象物単位のインデックスを表す整数とする）で式(A)が成立する制御対象物単位を１つ選択する(図７Ａ)。ここで、j_endは制御対象物構造中の端に位置する制御対象物単位である。
【００４２】
言い換えれば、この処理は、制御対象物構造中の端に位置する制御対象物単位（外側制御対象物単位）のうち、制御対象物単位jよりも制御対象物単位j'からみて離れた位置にある外側制御対象物単位であって、当該外側制御対象物単位を移動させても制御対象物構造の接続性が途切れない外側制御対象物単位を選択することといえる。
【００４３】
(2) 上記(1)で選択した制御対象物単位j_endに属する４つの制御対象物を、制御対象物単位jに隣接する制御対象物単位j_nのうちの１つである制御対象物単位j_k(k=1,…,n)の周囲の空隙位置に移動させ、制御対象物単位j_kと制御対象物単位j_endに属する制御対象物で8マスの立方体をなすようにする（図７Ｂ）。
【００４４】
(3) 制御対象物単位jに所属する制御対象物と上記(1)で選択した制御対象物単位j_endに所属する制御対象物の位置を入れ替える（図７Ｃ）。
【００４５】
(4) 制御対象物単位jに所属する制御対象物を制御対象物単位j'の中の制御対象物の周りにある空隙位置に移動させ、制御対象物単位jと制御対象物単位j'に属する制御対象物で8マスの立方体をなすようにする(図７Ｄ)。その後、制御対象物単位jの制御対象物を目標位置に移動させる。
【００４６】
以上に述べた制御を、全ての制御対象物単位が目標位置につくまで繰り返し行えば、ヘテロジニアス制御対象物隊列制御が完了する。この制御において、従来必要であった制御対象物同士の位置入れ替え作業は、上記の(3)において代替されている。以上の手法によれば、全ての制御対象物単位について、初期位置から目標位置に至るまでに必要な移動量は、入れ替えがなかった場合の移動量と同程度であり、かつそのほかの移動は必要としない。すなわち、本手法により、隊列の全体変形と制御対象物位置入れ替えが同時に行われている。
【００４７】
このように、全体の形状の変形動作と変形後の制御対象物位置入れ替えを別個のプロセスとせずに同時に行うことで、隊列制御動作にかかる時間を短縮することができる。
【００４８】
＜第一実施形態＞
以下、第一実施形態の制御装置及び方法について説明する。
【００４９】
制御装置は、図１８に示すように、制御対象物単位選択部１、制御対象物単位移動制御部２及び制御部３を例えば備えている。
【００５０】
制御方法は、制御装置が、図１９及び以下に説明するステップＳ１からステップＳ２の処理を行うことにより例えば実現される。
【００５１】
［制御対象物単位選択部１］
制御対象物単位選択部１は、移動対象とする制御対象物単位（標的制御対象物単位）を選択する。標的制御対象物単位は、制御対象物構造中の制御対象物単位であり、制御対象物構造に隣接する空隙位置を目標位置とする制御対象物単位（複数ある場合はその中の１つ）である。具体的には、以下のような処理で選択を行うことができる。選択された制御対象物単位についての情報は、制御対象物単位移動制御部２に出力される。以下、「選択された標的制御対象物単位」のことを、「選択された制御対象単位」と略記することもある。
【００５２】
(1) 制御対象物単位jが目標位置に到達しているかどうかを示す変数unfilled_g[j]が全ての制御対象物単位jについて定義されているものとする。例えば、0を目標位置に到達していないことを示す値、1を目標位置に到達していることを示す値とすれば、unfilled_g[j]=0ならば制御対象物単位jは目標位置に到達していないことを表す。
【００５３】
(2) unfilled_g[j]=0である目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）のうち、制御対象物構造に接している位置（つまり、制御対象物構造に隣接する目標位置）を１つ選び、それを目標位置とする制御対象物単位をj_fとする。ここでは、j_fが制御対象物単位の番号（制御対象物単位を特定するID）である。
【００５４】
このようにして、制御対象物単位選択部１は、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、選択された目標位置を目標位置とする制御対象物単位を選択する（ステップＳ１）。
【００５５】
［制御対象物単位移動制御部２］
制御対象物単位移動制御部２は、制御対象物単位選択部１で選択した制御対象物単位j_fを目標位置に移動させるよう制御する。
【００５６】
制御対象物単位移動制御部２は、図１８に示すように、接続性判定部２１、交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３、制御対象物単位入替制御部２４及び標的制御対象物単位移動制御部２５を例えば備えている。
【００５７】
［［接続性判定部２１］］
接続性判定部２１は、制御対象物単位j_fを移動させることで制御対象物構造の接続性が維持されるか否かを判定する。言い換えれば、接続性判定部２１は、制御対象物単位選択部１で選択された制御対象物単位を目標位置に移動させるときに制御対象物構造の接続性が維持されるかどうか判定する（ステップＳ２１）。
【００５８】
具体的には、接続性判定部２１は、式(A)においてjをj_fと読み替え、j'をj_fの目標位置に隣接する制御対象物単位としたときに、j_fに隣接する全ての制御対象物単位について式(A)を満たせば接続性は維持されると判定し、そうでない場合には接続性は維持されないと判定する。
【００５９】
接続性判定部２１は、接続性が維持される場合には標的制御対象物単位移動制御部２５の処理を実行させ、接続性が維持されない場合には交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３及び制御対象物単位入替制御部２４の処理を実行させる。
【００６０】
言い換えれば、制御対象物構造の接続性が維持されると接続性判定部２１で判定された場合には、制御対象物単位選択部１で選択された制御対象物単位を目標位置に移動さる処理が標的制御対象物単位移動制御部２５により行われる。
【００６１】
また、制御対象物構造の接続性が維持されないと接続性判定部２１で判定された場合には、制御対象物単位選択部１で選択された制御対象物単位の位置に制御対象物構造の接続性を維持しながら移動することができる制御対象物である交換制御対象物単位を選択し、選択された交換制御対象物単位を制御対象物単位選択部１で選択された制御対象物単位の位置に移動させる処理が、交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３及び制御対象物単位入替制御部２４により行われる。その後、制御対象物単位選択部１で選択された制御対象物単位を目標位置に移動させる処理が標的制御対象物単位移動制御部２５により行われる。
【００６２】
［［交換制御対象物単位選択部２２］］
交換制御対象物単位選択部２２は、制御対象物単位j_fを移動させても制御対象物構造の接続性が途切れないように他の制御対象物単位を制御対象物単位j_fの現在位置に移動させるため、移動対象とする「他の制御対象物単位」（以下、「交換制御対象物単位」という）を選択する。すなわち、交換制御対象物単位選択部２２は、制御対象物構造中で外側（端点）に位置する制御対象物単位である外側制御対象物単位のうち、制御対象物単位j_fの目標位置に隣接する制御対象物単位j'から見て制御対象物単位j_fよりも離れた位置にある外側制御対象物単位であって、移動させても制御対象物構造の接続性が途切れない外側制御対象物単位を１つ選択する。
【００６３】
具体的には、交換制御対象物単位選択部２２は、例えば以下の(1)の処理を行うことにより、交換制御対象物単位の選択を行う。
【００６４】
(1) 制御対象物単位j_fの位置から、δ値（制御対象物単位j'からみたマンハッタン距離）の大きな隣接する制御対象物単位をたどっていき、それ以上δ値の大きな制御対象物単位に到達できなくなる制御対象物単位を検出して、それを交換制御対象物単位j_endとする。
【００６５】
［［交換制御対象物単位移動制御部２３］］
交換制御対象物単位移動制御部２３は、交換制御対象物単位選択部２２で選択された交換制御対象物単位j_endに属する制御対象物を制御対象物単位j_fに隣接する制御対象物単位内にある空隙内に移動させるよう制御する。具体的には、交換制御対象物単位移動制御部２３は、例えば以下の(1)から(3)の処理を行う。
【００６６】
(1) 制御対象物単位j_fに隣接する制御対象物単位であって、かつ交換制御対象物単位j_endの位置と重ならない位置にある制御対象物単位のうち、制御対象物単位j_fから、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している制御対象物単位j_f_n（以下、「隣接空隙位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【００６７】
(2) 上記(1)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_fに隣接する制御対象物単位であって、かつ交換制御対象物単位j_endの位置と重ならない位置にある制御対象物単位のうち、制御対象物単位j_fから、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している制御対象物単位j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。必ず(1)→(2)の順に処理を行う。これは、（2）にて選択される制御対象物単位j_f_nを使用した後述の制御対象物単位入れ替え部の処理において、(1)にて選択される可能性のある制御対象物が存在しないことが、制御対象物構造の接続性を維持するうえで必須であるからである。
【００６８】
(3) 交換制御対象物単位j_endの位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応するS内の制御対象物単位各位置の列）を計算し、その道中の位置を
pass_j_f[nf](nf=0,1,2,…,nf_max)
として格納する。pass_j_f[0]=j_end,pass_j_f[nf_max]=j_f_nとなる。
【００６９】
(4) 交換制御対象物単位j_endを制御対象物単位pass_j_f[1]内の空隙に移動させる。例えば、X軸の正方向への移動であれば、図８に示すような手順で移動させ、X軸の負方向への移動であれば図９に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。この後は、制御対象物単位j_f_n内の空隙に至るまで、pass_j_fに格納済みの道中にある制御対象物単位をたどらせつつ制御対象物単位j_endを移動させ、制御対象物単位j_endと制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。その移動は、各移動ステップにおいて、X正方向への移動ならば例えば図１０に示す方法で、負方向への移動ならば、図１１に示す方法で移動させる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【００７０】
［［制御対象物単位入替制御部２４］］
制御対象物単位入替制御部２４は、制御対象物単位j_fとその周辺に移動させた交換制御対象物単位j_endの位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸やZ軸の正方向・負方向についても同様に交換を行えばよい。
【００７１】
［［標的制御対象物単位移動制御部２５］］
標的制御対象物単位移動制御部２５は、制御対象物単位j_fを目標位置へ移動させる。移動操作は、交換制御対象物単位移動制御部と同様の方法（例えば図１０、図１１に例示する手順の移動）で定義可能な方法で、制御対象物単位j_fを、制御対象物単位j_fの目標位置に隣接する制御対象物単位j'内の空隙に移動させ、制御対象物単位j_fと制御対象物単位j'に属する制御対象物で8マスの立方体をなすようにする。その後、例えば、図１４、図１５に示す手順等で定義可能な方法で、制御対象物単位j_fの目標位置への移動が完了したら、unfilled_g[j_f]の値を１に変更する。１は、目標位置に制御対象物単位が到達していることを示す値である。
【００７２】
［制御部３］
制御部３は、全ての制御対象物単位が目標位置に到達しているかを判定し、到達していなければ、制御対象物単位選択部１の処理に戻って移動を繰り返すよう制御する。例えば、制御部３は、制御対象物単位j=0から順にunfilled_g[j]の値を確認し、unfilled_g[j]=0なるjがあれば制御対象物単位選択部を実行させ、全てのjについてunfilled_g[j]=1ならば処理を終了する。
【００７３】
このようにして、制御部３は、制御対象物単位が到達していない目標位置がなくなるまで、制御対象物単位選択部１及び制御対象物単位移動制御部２の処理を繰り返すように制御を行う（ステップＳ３）。
【００７４】
＜第二実施形態＞
第一実施形態の制御装置及び方法は初期位置の集合と目標位置の集合に重なりがないことを前提とするが、第二実施形態の制御装置及びは初期位置の集合と目標位置の集合に重なりがあっても隊列変換可能である点を特徴とする。
【００７５】
目標位置の集合のうち、初期位置の集合と重なる部分、すなわち（Xr_u0[js],Yr_u0[js],Zr_u0[js]）=（Xr_ue[jg],Yr_ue[jg],Zr_ue[jg]）については、共通位置の集合Cと定義し、（Xr_uc[j],Yr_uc[j],Zr_uc[j]）とする。つまり、目標位置の集合及び初期位置の集合の積集合を共通位置の集合とする。同じ制御対象物単位番号jについて、（Xr_ue[j],Yr_ue[j],Zr_ue[j]）＝（Xr_uc[j],Yr_uc[j],Zr_uc[j]）である。初期状態において共通位置にある制御対象物単位jが、隊列変形後に共通位置の外の目標位置内に移動することもありうるし、隊列変形後に共通位置の内の目標位置内に移動することもありうる。初期状態において共通位置の外にある制御対象物単位jが、隊列変形後に共通位置の外の目標位置内に移動することもありうるし、隊列変形後に共通位置の内の目標位置内に移動することもありうる。なお、共通位置の集合Cはそれ自体に非接続箇所はないものと仮定する。
【００７６】
第一実施形態との主だった相異点は、共通位置の集合C内に、初期位置の集合Sの外へ移動する制御対象物単位jが存在していた場合の処理であるので、まずその概要を説明する。
【００７７】
まず、制御対象物単位jを制御対象物単位j_other[0]とし、その場合、制御対象物単位j_other[0]が現時点で存在している位置は、他の制御対象物単位j_other[1]が目標位置としている場所である。なぜならば、もし、その位置が他の制御対象物単位j_other[1]の目標位置でないならば、その位置は制御対象物単位j_other[0]の目標位置でなければならず、その場合、制御対象物単位j_other[0]は、共通位置の集合Cの外の目標位置G内に移動することはありえないからである。このように考えると、続いて、制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位j_other[1]の位置がもしC内であれば、当然、他の制御対象物単位j_other[2]が制御対象物単位j_other[1]の現在位置を目標位置とするはずである。という具合に制御対象物単位j_other[]を順次定義していくと、それは制御対象物単位j_other[]が共通位置の集合Cの外にある制御対象物単位になるまで続く。そのような制御対象物単位をj_other[j_c_out]とする。制御対象物単位j_other[j_c_out]を制御対象物構造から取り払ったときに、制御対象物構造に非接続が生じる場合には、制御対象物構造に非接続が生じさせない（jをj_other[j_c_out]と読み替えた場合の式(A)を満たす）制御対象物単位を共通位置の集合Cの外に探しだしj_other[j_c_out+1]として定義し、j_chain←j_c_out+1とする。もし制御対象物単位j_other[j_c_out]が式(A)を満たすならj_chain←j_c_outとすればよい。
【００７８】
この後、制御対象物単位j_other[j_chain]を、制御対象物単位j_other[j_chain‐1]の位置に移動させて制御対象物単位j_other[j_chain‐1]と入れ替える。制御対象物単位j_other[j_chain-1]を、制御対象物単位j_other[j_chain‐2]の位置に移動させて制御対象物単位j_other[j_chain‐2]と入れ替える。といった具合に制御対象物単位j_other[0]が制御対象物単位j_other[1]と入れ替えられるまで繰り返せば、制御対象物構造に非接続を発生させずに、制御対象物単位j_other[0]（＝j）をG内目標位置に送り出す準備が整う。すなわち、以下に述べる(1)から(5)の処理を行えば、共通位置の集合Cが存在する場合に適用可能な隊列制御が実現する。
【００７９】
(1) 制御対象物単位jを制御対象物単位j_other[0]とし、制御対象物単位j_other[0]の位置がC内ならば制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位j_other[1]を選択する。制御対象物単位j_other[1]の位置がC内であれば、制御対象物単位j_other[1]の現在位置を目標位置とする制御対象物単位j_other[2]を選択する。という形で順次制御対象物単位j_other[]がC外に位置する制御対象物単位になるまでを定義していく。そうして選択された最後の制御対象物単位をj_other[j_c_out]とする。j_other[j_c_out]の例は、図１６を参照のこと。
【００８０】
(2) 制御対象物単位j_other[j_c_out]が、jをj_other[j_c_out]と読み替えた場合の式(A)を満たさないならば、δ（j_end）>δ（j）である制御対象物単位j_endのうち、制御対象物単位j_endに隣接する全ての制御対象物単位j_end_nで式(A)が成立するものを選択し、j_other[j_c_out+1]とし、j_chain←j_c_out+1とする。図１７Ａでは、j_c_out=3であり、式(A)を成立させる制御対象物単位として制御対象物単位j_other[4]が選択されている。一方、制御対象物単位j_other[j_c_out]が、jをj_other[j_c_out]と読み替えた場合の式(A)を満たすならば、j_chain←j_c_outとする。
【００８１】
(3) j_c←j_chainとして、j_c=0になるまで以下の(4)から(5)を繰り返す（図１７Ｂから図１７Ｄ）。
【００８２】
(4) 制御対象物単位j_other[j_c]に属する４つの制御対象物を、制御対象物単位j_other[j_c-1]に隣接する位置にある制御対象物単位の１つj_f_nの中の４つの空隙位置に移動させ、制御対象物単位j_other[j_c]と制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。
【００８３】
(5) 制御対象物単位j_other[j_c]所属の制御対象物と制御対象物単位j_other[j_c-1]所属の制御対象物の位置を入れ替える。j_cをデクリメントする。
【００８４】
(6) 制御対象物単位j_other[0]所属の制御対象物を制御対象物単位j'の位置に移動させる（図１７Ｄ）。その後、制御対象物単位jの制御対象物を目標位置に展開する。
【００８５】
以下、第二実施形態の隊列制御装置の各部の処理について説明する。
【００８６】
図２０に示すように、制御装置は、制御対象物単位選択部１、制御対象物単位移動制御部２、制御部３、共通位置制御対象物単位選択部４、共通位置制御対象物単位移動制御部５及び共通位置制御部６を例えば備えている。
【００８７】
制御方法は、制御装置が、図２１及び以下に説明するステップＳ１からステップＳ６の処理を行うことにより例えば実現される。
【００８８】
以下、第一実施形態と異なる処理を中心に説明する。第一実施形態と同じ部分については説明を省略する。
【００８９】
［制御対象物単位選択部１］
制御対象物単位選択部１は、移動対象とする制御対象物単位（標的制御対象物単位）を選択する。標的制御対象物単位は、制御対象物構造中の制御対象物単位であり、制御対象物構造に隣接する位置を目標位置とする制御対象物単位（複数ある場合はその中の１つ）である。具体的には以下のような処理で選択を行うことができる。
【００９０】
(1) 制御対象物単位jが目標位置に到達しているかどうかを示す変数unfilled_g[j]が全ての制御対象物単位jについて定義されているものとする。例えば、0を目標位置に到達していないことを示す値、1を目標位置に到達していることを示す値とすれば、unfilled_g[j]=0ならば制御対象物単位jは目標位置に到達していないことを表す。
【００９１】
(2) unfilled_g[j]=0である目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）のうち、制御対象物構造に接している空隙位置（つまり、制御対象物構造に隣接する目標位置）を１つ選び、それを目標位置とする制御対象物単位をj_other[0]とする。ここでは、j_other[0]が標的制御対象物単位の番号（制御対象物単位を特定するID）である。
【００９２】
このようにして、制御対象物単位選択部１は、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、選択された目標位置を目標位置とする制御対象物単位j_other[0]を仮に選択する。
【００９３】
(3) 制御対象物単位j_other[0]の位置がC内ならば制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位j_other[1]を選択する。制御対象物単位j_other[1]の位置がC内であれば、制御対象物単位j_other[1]の現在位置を目標位置とする制御対象物単位j_other[2]を選択する。という形で順次制御対象物単位j_other[]がC外に位置する制御対象物単位になるまでを定義していく。そうして選択された最後の制御対象物単位をj_other[j_c_out]とする。
【００９４】
すなわち、制御対象物単位選択部１は、(b) 仮に選択された制御対象物単位j_other[0]の位置が共通位置の集合Cに含まれる場合には、仮に選択された制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位を新たに選択し、新たに選択された制御対象物単位の位置が共通位置の集合Cに含まれる場合には、新たに選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択するという処理を、新たに選択された制御対象物単位の位置が共通位置の集合Cに含まれないようになるまで繰り返し、繰り返しによって選択された全ての制御対象物単位についての情報を、制御対象物単位移動制御部２に出力する。
【００９５】
一方、(a) 仮に選択された制御対象物単位j_other[0]の位置が共通位置の集合Cに含まれない場合には、制御対象物単位選択部１は、仮に選択された制御対象物単位j_other[0]を選択し、選択された制御対象物単位についての情報を、制御対象物単位移動制御部２に出力する。
【００９６】
［制御対象物単位移動制御部２］
制御対象物単位移動制御部２は、制御対象物単位選択部１で選択した制御対象物単位を目標位置に移動させるよう制御する。
【００９７】
制御対象物単位移動制御部２は、図２０に示すように、接続性判定部２１、交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３、制御対象物単位入替制御部２４、標的制御対象物単位移動制御部２５及び共通部分制御対象物単位入替制御部２６を例えば備えている。
【００９８】
(a) 仮に選択された制御対象物単位j_other[0]の位置が共通位置の集合Cに含まれない場合には、制御対象物単位移動制御部２は、制御対象物単位選択部１により選択された制御対象物単位j_other[0]に対して、第一実施形態の制御対象物単位移動制御部２と同様の処理を行う。
【００９９】
一方、(b) 仮に選択された制御対象物単位j_other[0]の位置が共通位置の集合Cに含まれる場合には、制御対象物単位移動制御部２は、制御対象物単位選択部１により選択された制御対象物単位j_other[j_c_out]に対して、第一実施形態の制御対象物単位移動制御部２内の交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３、制御対象物単位入替制御部２４と同様の処理を行う。その後、制御対象物単位移動制御部２は、後述する共通部分制御対象物単位入替制御部２６の処理を行うことにより制御対象物単位選択部１で新たに選択された目標位置を共通位置内に持つ制御対象物を目標位置に移動させ、標的制御対象物単位移動制御部２５を行うことにより制御対象物単位選択部１で仮に選択された制御対象物単位j_other[0]を共通位置外の目標位置に移動させる。
【０１００】
以下、(b) 仮に選択された制御対象物単位j_other[0]の位置が共通位置の集合Cに含まれる場合に行われる、制御対象物単位移動制御部２の接続性判定部２１、交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３、制御対象物単位入替制御部２４、標的制御対象物単位移動制御部２５及び共通部分制御対象物単位入替制御部２６の処理について説明する。
【０１０１】
［［接続性判定部２１］］
接続性判定部２１は、制御対象物単位j_other[j_c_out]を移動させることで制御対象物構造の接続性が維持されるか否かを判定する。言い換えれば、接続性判定部２１は、制御対象物単位選択部１で選択された制御対象物単位を目標位置に移動させるときに制御対象物構造の接続性が維持されるかどうか判定する（ステップＳ２１）。
【０１０２】
具体的には、接続性判定部２１は、式(A)においてjをj_other[j_c_out]と読み替えたときに、隣接する全ての制御対象物単位について式(A)を満たせば接続性は維持されると判定し、そうでない場合には接続性は維持されないと判定する。
【０１０３】
接続性判定部２１は、j_chain←j_c_outとして、接続性が維持される場合には共通部分制御対象物単位入替制御部２６及び標的制御対象物単位移動制御部２５の処理を実行させ、接続性が維持されない場合には交換制御対象物単位選択部２２、交換制御対象物単位移動制御部２３、制御対象物単位入替制御部２４、共通部分制御対象物単位入替制御部２６及び標的制御対象物単位移動制御部２５の処理を実行させる。
【０１０４】
［［交換制御対象物単位選択部２２］］
交換制御対象物単位選択部２２は、交換制御対象物単位選択部２２は、制御対象物単位j_other[j_c_out]を移動させても制御対象物構造の接続性が途切れないように他の制御対象物単位を制御対象物単位j_other[j_c_out]の現在位置に移動させるため、移動対象とする「他の制御対象物単位」（以下、「交換制御対象物単位」という）を選択する。すなわち、交換制御対象物単位選択部２２は、制御対象物構造中で外側（端点）に位置する制御対象物単位である外側制御対象物単位のうち、制御対象物単位j'から見て制御対象物単位j_other[j_c_out]よりも離れた位置にある外側制御対象物単位であって、移動させても制御対象物構造の接続性が途切れない外側制御対象物単位を１つ選択する。
【０１０５】
具体的には、交換制御対象物単位選択部２２は、例えば以下の(1)の処理を行うことにより、交換制御対象物単位の選択を行う。
【０１０６】
(1) 制御対象物単位j_other[j_c_out]の位置から、δ値（制御対象物単位j'からみたマンハッタン距離）の大きな隣接する制御対象物単位をたどっていき、それ以上δ値の大きな制御対象物単位に到達できなくなる制御対象物単位を検出して、それを交換制御対象物単位j_other[j_c_out+1]とし、j_chain←j_c_out+1とする。
【０１０７】
［［交換制御対象物単位移動制御部２３］］
交換制御対象物単位移動制御部２３は、制御対象物単位j_other[j_chain]を制御対象物単位j_other[j_chain-1=j_c_out]に隣接する位置に移動させるよう制御する。具体的には、例えば、以下のような処理により実現される。
【０１０８】
(1) 制御対象物単位j_other[j_chain-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]の位置と重ならない位置のうち、制御対象物単位j_other[j_chain-1]から、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している位置j_f_n（以下、「隣接位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【０１０９】
(2) 上記(1)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_other[j_chain-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]の位置と重ならない位置のうち、制御対象物単位j_other[j_chain-1]から、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している位置j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。なお、(1)と(2)の処理は逆順ではいけない。
【０１１０】
(3) 制御対象物単位j_other[j_chain]の位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応する状態空間G内の各位置の列）を計算し、その道中の位置を
pass_j_f[nf](nf=0,1,2,…,nf_max)
として格納する。pass_j_f[0]= j_other[j_chain],pass_j_f[nf_max]=j_f_nとなる。
【０１１１】
(4) 制御対象物単位j_other[j_chain]を位置pass_j_f[１]に移動させる。例えば、X軸の正方向への移動であれば、図８に示すような手順で移動させ、X軸の負方向への移動であれば図９に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１１２】
(5) 制御対象物単位j_other[j_chain]を位置pass_j_f[1]〜位置pass_j_f[nf_max]に移動させ、制御対象物単位j_other[j_chain]と制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１１３】
［［制御対象物単位入替制御部２４］］
制御対象物単位入替制御部２４は、制御対象物単位j_other[j_chain-1]とその周辺に移動させた制御対象物単位j_other[j_chain]の位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸やZ軸の正方向・負方向についても同様に交換を行えばよい。
【０１１４】
［［共通部分制御対象物単位入替制御部２６］］
共通部分制御対象物単位入替制御部２６は、以下の(1)から(6)の処理を行う。
【０１１５】
(1) j_c←j_c_outとし、j_c=0になるまで以下を繰り返す。
【０１１６】
(2) 制御対象物単位j_other[j_c-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_c-1]から、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している位置j_f_n（以下、「隣接位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【０１１７】
(3)上記(2)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_other[j_c-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_c-1]から、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している位置j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。なお、(2)と(3)の処理は逆順ではいけない。
【０１１８】
(4) 制御対象物単位j_other[j_c]の位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応する状態空間G内の各位置の列）を計算し、その道中の位置を
pass_j_f[nf](nf=0,1,2,…,nf_max)
として格納する。pass_j_f[0]= j_other[j_c],pass_j_f[nf_max]=j_f_nとなる。
【０１１９】
(5) 制御対象物単位j_other[j_c]を位置pass_j_f[0]〜位置pass_j_f[nf_max]に移動させる。例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１２０】
(6)制御対象物単位j_other[j_c-1]とその周辺に移動させた制御対象物単位j_other[j_c]の位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸及びZ軸の正方向又は負方向についても同様に交換を行えばよい。j_cをデクリメントする。
【０１２１】
［［標的制御対象物単位移動制御部２５］］
標的制御対象物単位移動制御部２５は、制御対象物単位j_other[0]を目標位置へ移動させる。移動の初めの操作として、目標位置に接する位置にある制御対象物単位j'の中の空隙まで制御対象物単位j_other[0]を移動させ、制御対象物単位j_other[0]と制御対象物単位j'に属する制御対象物で8マスの立方体をなすようにする。具体的操作は、例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。続いての移動操作は、最後の空隙位置への展開である。具体的には、例えば図１４、図１５に例示する手順の移動で定義することができる。そして目標位置への移動が完了したら、unfilled_g[j_other[0]]の値を１に変更する。１は、目標位置に制御対象物単位が到達していることを示す値である。
【０１２２】
［制御部３］
制御部３は、C外G内の全ての位置についてunfilled_g[]=1であるか判定し、unfilled_g[]=0である位置がなくなるまで、制御対象物単位選択部１の処理に戻って移動を繰り返すよう制御する。例えば、制御部３は、制御対象物単位j=0から順にunfilled_g[j]の値を確認し、C外G内にてunfilled_g[j]=0なるjがあれば制御対象物単位選択部１を実行させ、全てのjについてunfilled_g[j]=1ならば処理を終了する。
【０１２３】
このようにして、制御部３は、制御対象物単位が到達していない目標位置であって、目標位置の集合に含まれるが共通位置の集合Cに含まれない目標位置がなくなるまで、制御対象物単位選択部１及び制御対象物単位移動制御部２の処理を繰り返すように制御を行う（ステップＳ３）。
【０１２４】
［共通位置制御対象物単位選択部４］
前述の制御対象物単位選択部１は、G内C外目標位置へ移動する制御対象物を含む制御対象物単位j_other[]に関する標的制御対象物選択処理であったが、C内目標位置へ移動する制御対象物のみを含む制御対象物単位j_other[]に関する標的制御対象物選択処理をここで行う。
【０１２５】
共通位置制御対象物単位選択部４は、移動対象とする制御対象物単位（標的制御対象物単位）を選択する。標的制御対象物単位は、C内のいまだ目標位置に到達していない制御対象物単位であり、C内の位置を目標位置とする制御対象物単位（複数ある場合はその中の１つ）である。具体的には、共通位置制御対象物単位選択部４は、以下の(1)及び(2)の処理で選択を行うことができる。
【０１２６】
(1) unfilled_g[j]=0であるC内の目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）を１つ選び、その位置にある制御対象物単位をj_other[0]とする。ここではj_other[0]が標的制御対象物単位の番号（制御対象物単位を特定するID）である。
【０１２７】
(2) 制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位j_other[1]を選択する。制御対象物単位j_other[1]の現在位置を目標位置とする制御対象物単位j_other[2]を選択する。という形で順次制御対象物単位j_other[]の位置が制御対象物単位j_other[0]の目標位置になるまでj_other[]を定義していく。そうして選択された最後の制御対象物単位をj_other[j_c_out]とする。
【０１２８】
このようにして、共通位置制御対象物単位選択部４は、制御対象物単位が到達していない目標位置であって、共通位置の集合Cに含まれる目標位置を選択し、選択された目標位置にある制御対象物単位j_other[0]を仮に選択し、仮に選択された制御対象物単位j_other[0]の位置を目標位置とする制御対象物単位を新たに選択し、新たに選択された制御対象物単位の位置が仮に選択された制御対象物単位の目標位置でない場合には、新たに選択された制御対象物単位の位置を目標位置とする制御対象物単位を新たに選択するという処理を、新たに選択された制御対象物単位の位置が仮に選択された制御対象物単位j_other[0]の目標位置になるまで繰り返し、最後に選択された制御対象物単位j_other[j_c_out]を選択する（ステップＳ４）。選択された制御対象物単位についての情報は、共通位置制御対象物単位移動制御部５に出力される。
【０１２９】
［共通位置制御対象物単位移動制御部５］
共通位置制御対象物単位移動制御部５は、共通位置制御対象物単位選択部４で選択した各制御対象物単位j_other[j_c_out],…,j_other[0]を目標位置に移動させるよう制御する。
【０１３０】
共通位置制御対象物単位移動制御部５は、図２０に示すように、共通位置接続性判定部５１、共通位置交換制御対象物単位選択部５２、共通位置交換制御対象物単位移動制御部５３、共通位置制御対象物単位入替制御部５４、共通位置標的制御対象物単位移動制御部５５及び共通位置共通部分制御対象物単位入替制御部５６を例えば備えいてる。
【０１３１】
［共通位置接続性判定部５１］
共通位置接続性判定部５１は、制御対象物単位j_other[j_c_out]を移動させることで制御対象物構造の接続性が維持されるか否かを判定する。言い換えれば、共通位置接続性判定部５１は、共通位置制御対象物単位選択部４で選択された制御対象物単位を目標位置に移動させるときに制御対象物構造の接続性が維持されるかどうか判定する（ステップＳ５１）。
【０１３２】
具体的には、共通位置接続性判定部５１は、式(A)においてjをj_other[j_c_out]と読み替えたときに、隣接する全ての制御対象物単位について式(A)を満たせば接続性は維持されると判定し、そうでない場合には接続性は維持されないと判定する。この場合のj'はGに接する制御対象物ならどれでもよい。
【０１３３】
共通位置接続性判定部５１は、j_chain←j_c_outとして、接続性が維持される場合には共通位置標的制御対象物単位移動制御部５５の処理を実行させ、接続性が維持されない場合には共通位置交換制御対象物単位選択部５２、共通位置交換制御対象物単位移動制御部５３、共通位置制御対象物単位入替制御部５４、共通位置共通部分制御対象物単位入替制御部５６及び共通位置標的制御対象物単位移動制御部５５の処理を実行させる。
【０１３４】
［［共通位置交換制御対象物単位選択部５２］］
共通位置交換制御対象物単位選択部５２は、制御対象物単位j_other[j_c_out]を移動させても制御対象物構造の接続性が途切れないように他の制御対象物単位を制御対象物単位j_other[j_c_out]の現在位置に移動させるため、移動対象とする「他の制御対象物単位」（以下、「交換制御対象物単位」という）を選択する。すなわち、制御対象物構造中で外側（端点）に位置する制御対象物単位である外側制御対象物単位のうち、制御対象物単位j'から見て制御対象物単位j_other[j_c_out]よりも離れた位置にある外側制御対象物単位であって、移動させても制御対象物構造の接続性が途切れない外側制御対象物単位を１つ選択する。
【０１３５】
具体的には、共通位置交換制御対象物単位選択部５２は、例えば以下の(1)の処理を行うことにより、交換制御対象物単位の選択を行う。
【０１３６】
(1) 制御対象物単位j_other[j_c_out]の位置から、δ値（制御対象物単位j'からみたマンハッタン距離）の大きな隣接する制御対象物単位をたどっていき、それ以上δ値の大きな制御対象物単位に到達できなくなる制御対象物単位を検出して、それを交換制御対象物単位j_other[j_c_out+1]とし、j_chain←j_c_out+1とする。
【０１３７】
このようにして、共通位置交換制御対象物単位選択部５２は、共通位置制御対象物単位選択部４で選択された制御対象物単位の位置に制御対象物構造の接続性を維持しながら移動することができる制御対象物である交換制御対象物単位を選択する（ステップＳ５３）。
【０１３８】
［［共通位置交換制御対象物単位移動制御部５３］］
共通位置交換制御対象物単位移動制御部５３は、制御対象物単位j_other[j_chain]を制御対象物単位j_other[j_chain-1=j_c_out]に隣接する位置に移動させるよう制御する。具体的には、例えば、以下のような処理により実現される。
【０１３９】
(1) 制御対象物単位j_other[j_chain-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]の位置と重ならない位置のうち、制御対象物単位j_other[j_chain-1]から、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している位置j_f_n（以下、「隣接位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【０１４０】
(2) 上記(1)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_other[j_chain-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]の位置と重ならない位置のうち、制御対象物単位j_other[j_chain-1]から、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している位置j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。なお、(1)と(2)の処理は逆順ではいけない。
【０１４１】
(3) 制御対象物単位j_other[j_chain]の位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応する状態空間G内の各位置の列）を計算し、その道中の位置を
pass_j_f[nf](nf=0,1,2,…,nf_max)
として格納する。pass_j_f[0]= j_other[j_chain],pass_j_f[nf_max]=j_f_nとなる。
【０１４２】
(4) 制御対象物単位j_other[j_chain]を位置pass_j_f[１]に移動させる。例えば、X軸の正方向への移動であれば、図８に示すような手順で移動させ、X軸の負方向への移動であれば図９に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１４３】
(5) 制御対象物単位j_other[j_chain]を位置pass_j_f[1]〜位置pass_j_f[nf_max]に移動させ、制御対象物単位j_other[j_chain]と制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１４４】
［［共通位置制御対象物単位入替制御部５４］］
共通位置制御対象物単位入替制御部５４は、制御対象物単位j_other[j_chain-1]とその周辺に移動させた制御対象物単位j_other[j_chain]の位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸やZ軸の正方向・負方向についても同様に交換を行えばよい。
【０１４５】
共通位置交換制御対象物単位移動制御部５３及び共通位置制御対象物単位入替制御部５４により、共通位置交換制御対象物単位選択部５２で選択された交換制御対象物単位を、共通位置制御対象物単位選択部４で選択された制御対象物単位j_other[j_c_out]の位置に移動させることができる（ステップＳ５３及びステップＳ５４）。
【０１４６】
［共通位置共通部分制御対象物単位入替制御部５６］
共通位置共通部分制御対象物単位入替制御部５６は、以下の(1)から(6)の処理を行う。これらの処理により、共通位置制御対象物単位選択部４で新たに選択された制御対象物単位を目標位置に移動させることができる（ステップＳ５６）。
【０１４７】
(1) j_c←j_c_outとし、j_c=0になるまで以下（(2)-(6)）を繰り返す。
【０１４８】
(2) 制御対象物単位j_other[j_c-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_c-1]から、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している位置j_f_n（以下、「隣接位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【０１４９】
(3)上記(2)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_other[j_c-1]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_c-1]から、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している位置j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。なお、(2)と(3)の処理は逆順ではいけない。
【０１５０】
(4) 制御対象物単位j_other[j_c]の位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応する状態空間G内の各位置の列）を計算し、その道中の位置を
pass_j_f[nf](nf=0,1,2,…,nf_max)
として格納する。pass_j_f[0]= j_other[j_c],pass_j_f[nf_max]=j_f_nとなる。
【０１５１】
(5) 制御対象物単位j_other[j_c]を位置pass_j_f[0]〜位置pass_j_f[nf_max]に移動させ、制御対象物単位j_other[j_c]と制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様に行うことができる。
【０１５２】
(6)制御対象物単位j_other[j_c-1]とその周辺に移動させた制御対象物単位j_other[j_c]の位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸及びZ軸の正方向又は負方向についても同様に交換を行えばよい。j_cをデクリメントする。
【０１５３】
［［共通位置標的制御対象物単位移動制御部５５］］
共通位置標的制御対象物単位移動制御部５５は、制御対象物単位j_other[0]を、目標位置まで移動させる（ステップＳ５５）。
【０１５４】
なお、共通位置接続性判定部５１で、j_other[j_c_out]を移動させた場合に制御対象物構造に非接続が生じると判定された場合とそうでない場合で、共通位置標的制御対象物単位移動制御部５５の処理の処理は分かれる。
【０１５５】
共通位置接続性判定部５１で非接続が生じると判定された場合には、共通位置標的制御対象物単位移動制御部５５は、以下の(1)から(6)の処理を行う。これらの処理により、共通位置標的制御対象物単位移動制御部５５は、仮に選択された制御対象物単位j_other[0]を目標位置に移動させ、交換制御対象物単位j_other[j_chain]を目標位置に移動させている。
【０１５６】
(1) 制御対象物単位j_other[j_chain]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]から、行動a=3,4,6の方向（つまり、x,y,z軸のいずれかの負方向）に隣接している位置j_f_n（以下、「隣接位置」という）を選択する。その際の隣接方向の逆方向をa_exに格納する。
【０１５７】
(2) 上記(1)にて、該当の隣接空隙位置j_f_nが見つからなかった場合、制御対象物単位j_other[j_chain]に隣接する制御対象物単位と同じサイズの位置であって、かつ制御対象物単位j_other[j_chain]から、行動a=1,2,5の方向（つまり、x,y,z軸の何れかの正方向）に隣接している位置j_f_nを選択する。その際の隣接方向の逆方向をa_exに格納する。なお、(1)と(2)の処理は逆順ではいけない。
【０１５８】
(3) 制御対象物単位j_other[0]の位置から、隣接空隙位置j_f_nに至るまでの制御対象物構造内をたどる道筋（経路に対応する状態空間G内の各位置の列）を計算し、その道中の位置をpass_j_f[nf](nf=0,1,2,…,nf_max)として格納する。pass_j_f[0]= j_other[0],pass_j_f[nf_max]=j_f_nとなる。
【０１５９】
(4) 制御対象物単位j_other[0]を位置pass_j_f[0]〜位置pass_j_f[nf_max]に移動させ、制御対象物単位j_other[0]と制御対象物単位j_f_nに属する制御対象物で8マスの立方体をなすようにする。例えば、道中の移動方向がX軸の正方向への移動であれば、図10 に示すような手順で移動させ、X軸の負方向への移動であれば図11に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様。
【０１６０】
(5)制御対象物単位j_other[j_chain]とその周辺に移動させた制御対象物単位j_other[0]の位置を入れ替える。このとき、隣接方向をa_exに基づいて入れ替え操作を行えばよい。例えば、a_ex=1（X軸の正方向）である場合は、図１２に示す制御対象物の移動により交換が実現できる。同様に、a_ex=3（X軸の負方向）である場合は、図１３に示す制御対象物の移動により交換が実現できる。Y軸及びZ軸の正方向又は負方向についても同様に交換を行えばよい。
【０１６１】
(6) 制御対象物単位j_other[j_chain]を、共通位置交換制御対象物単位選択部５２実行前のもとの位置へ移動させる。はじめの移動操作は、j_other[j_chain]を、前記もとの位置に隣接する位置にある制御対象物単位j'内の空隙内まで移動させて、制御対象物単位j_other[j_chain]と制御対象物単位j'に属する制御対象物で8マスの立方体をなすようにする操作である。具体的な操作は、例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様。続いての移動操作は、最後の空隙位置への展開であり、例えば図１４、図１５に例示する手順の移動で定義することができる。そして目標位置への移動が完了したら、unfilled_g[j_other[0]]の値を１に変更する。１は、目標位置に制御対象物単位が到達していることを示す値である。
【０１６２】
一方、共通位置接続性判定部５１で非接続が生じないと判定された場合には、共通位置標的制御対象物単位移動制御部５５は、以下の(1)の処理を行う。
【０１６３】
(1) 制御対象物単位j_other[0]を目標位置へ移動させる。はじめの移動操作は、j_other[0]を、目標位置に隣接する位置にある制御対象物単位j'内の空隙内まで移動させて、制御対象物単位j_other[0]と制御対象物単位j'に属する制御対象物で8マスの立方体をなすようにする操作である。具体的な操作は、例えば、道中の移動方向がX軸の正方向への移動であれば、図１０に示すような手順で移動させ、X軸の負方向への移動であれば図１１に示す手順で移動させることができる。Y軸及びZ軸の正方向又は負方向への移動も同様。続いての操作は、最後の空隙位置への展開であり、例えば図１４、図１５に例示する手順の移動で定義することができる。そして目標位置への移動が完了したら、unfilled_g[j_other[0]]の値を１に変更する。１は、目標位置に制御対象物単位が到達していることを示す値である。
【０１６４】
［共通位置制御部６］
共通位置制御部６は、C内の全ての位置についてunfilled_g[]=1であるか判定し、unfilled_g[]=0である位置がなくなるまで、共通位置制御対象物単位選択部４の処理に戻って移動を繰り返すよう制御する。
【０１６５】
すなわち、共通位置制御部６は、制御対象物単位が到達していない目標位置であって、共通位置の集合Cに含まれる目標位置がなくなるまで、共通位置制御対象物単位選択部４及び共通位置制御対象物単位移動制御部５の処理を繰り返すように制御を行う（ステップＳ６）
第二実施形態の隊列制御装置によれば、多数の制御対象物の存在を考慮しつつ、制御対象物同士が接したままの状態を維持しつつ任意の初期位置における隊列形成状態から、他の任意の目標位置における隊列形成状態へ障害物のある環境にてヘテロジニアス隊列制御を制御対象物の個数の２乗に比例した実行時間で従来手法より短い時間で配置させることができ、初期位置と目標位置の間に重なる部分がある場合であっても適用可能である。
【０１６６】
＜第三実施形態＞
第三実施形態の制御装置及び方法は、ヘテロジニアス隊列制御を２つの段階の制御、すなわち、初期位置状態にある制御対象物をホモジニアスな隊列変形制御により全体の隊列形状が目標位置の集合Gと同じ形状にするための制御と、その後の制御対象物位置の入れ替え制御からなる方法である。
【０１６７】
はじめのホモジニアスな隊列変形制御のある時刻において、目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）が空隙のままであり、かつ目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）に隣接する制御対象物単位の位置内に制御対象物単位j'に属する制御対象物４つが存在しているとする（図５Ａ）。この場合、p個の制御対象物からなる隊列（制御対象物構造）内には非接続な箇所はなく、かつ各制御対象物単位内には、制御対象物が通過可能な空隙が４つ用意されているため、制御対象物構造内のある位置に存在する制御対象物単位j''に属する制御対象物４つが、制御対象物構造内の空隙を伝って、制御対象物単位j'内の空隙に移動することは可能である(図５Ｂ、図５Ｃ)。そして、４つの空隙が制御対象物単位j''に属する制御対象物によって埋められた状態の制御対象物位置j'から、隣接する位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）に制御対象物単位j''に属する４つの制御対象物を排出して、目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）にて、制御対象物単位j''の基本形状を形成させることも可能である（図５Ｄ）。この動作を利用して、初期位置の集合S内の制御対象物をG内に１つずつ移動させればよい。この際、制御対象物単位j''を移動させることで、制御対象物構造に非接続が生じてはいけない。その判定のためには、式(A)と同様の式である式(B)を用いる。
【０１６８】
δ（j''）>δ（j_n）…式(B)
ここで、δ（j''）は、制御対象物単位j''の制御対象物単位j'からのマンハッタン距離である。そして、j_nは、制御対象物単位j''に隣接している制御対象物単位を一意に識別するための番号であり（nは正の整数）、δ（j_n）は制御対象物単位j_nの制御対象物単位j'からのマンハッタン距離である。全ての制御対象物単位j_nに対して式(B)が成立するならば、制御対象物単位j''を制御対象物構造から取り払ったとしても制御対象物構造の接続性は維持できる。
【０１６９】
そこで、式(B)による判定を行って、移動可能な制御対象物単位を選択すればよい。
【０１７０】
以上に述べた制御を、全てのS内制御対象物単位が目標位置の集合G内にたどりつくまで繰り返し行えば、ホモジニアス隊列変形が完了する。この後、目標位置の集合Gをなす制御対象物単位の各位置を入れ替える制御を行うことで、ヘテロジニアス隊列制御が完成する。
【０１７１】
制御対象物位置の入れ替え処理は、G内にある各制御対象物単位jが、それぞれの目標位置に制御対象物構造をたどって移動することで行われる。その移動は、例えば、制御対象物単位jの目標位置の隣に位置する制御対象物単位をj'としたとき、制御対象物単位jは、まず制御対象物単位j'の位置まで、図５Ａ、図５Ｂ、図５Ｃに示す方法で移動し、続いて図１２及び図１３に示す方法で、制御対象物単位jの目標位置に存在している制御対象物単位と位置を入れ替えることでなされる。この際、制御対象物単位jを移動させることで制御対象物単位jの位置に空隙が生じるが、その時に制御対象物構造に非接続が生じるかどうかの判定は同様に式(B)を使用すればよい。ここで、式(B)を制御対象物単位jが満たさない場合の処理として、他の式(B)を満たす制御対象物単位j_altをまず制御対象物単位jの位置まで移動させ、図１２，１３の動作を使用して制御対象物単位jと制御対象物単位j_altの位置を入れ替える。その後、制御対象物単位jを図５Ａ、図５Ｂ、図５Ｃ、図１２及び図１３の動作により、その目標位置まで移動させる。この後、制御対象物単位jの目標位置にあった制御対象物を、あらたに制御対象物単位jとし、新たな制御対象物単位jを制御対象物単位jの目標位置まで移動させることを、制御対象物単位j_altの現在位置を目標位置とする制御対象物単位jが目標位置に到達するまで実行し、最後の制御対象物単位jの移動が済んだら、制御対象物単位j_altを元あった位置に戻せばよい。
【０１７２】
以下、第三実施形態の制御装置及び方法の動作の詳細を述べる。
【０１７３】
制御装置は、図２２に示すように、制御対象物単位選択部１、制御対象物単位移動制御部２、制御部３及び制御対象物単位入替部７を例えば備えている。
【０１７４】
制御方法は、制御装置が、図２３及び以下に説明するステップＳ１からステップＳ７の処理を行うことにより例えば実現される。
【０１７５】
以下、第一実施形態と異なる処理を中心に説明する。第一実施形態と同じ部分については説明を省略する。
【０１７６】
［制御対象物単位選択部１］
制御対象物単位選択部１は、移動対象とする制御対象物単位（標的制御対象物単位）を選択する。標的制御対象物単位は、制御対象物構造中の制御対象物単位であり、制御対象物構造に隣接する空隙位置を目的位置とする制御対象物単位（複数ある場合はその中の１つ）である。具体的には、制御対象物単位選択部１は、以下の(1)及び(2)の処理で選択を行うことができる。
【０１７７】
(1) 目標位置jが空隙のままであるかどうかを示す変数unfilled_g[j]が全てjについて定義されているものとする。例えば、0を目標位置が空隙のままであることを示す値、1を目標位置jが制御対象物により占有されていることを示す値とすれば、unfilled_g[j]=0ならば目標位置jは、空隙のままであることを表す。
【０１７８】
(2) unfilled_g[j]=0である目標位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）のうち、制御対象物構造に接している位置（つまり、制御対象物構造に隣接する目的位置）を１つ選び、その位置に移動させる制御対象物単位として、式(B)においてj''をj_fと読み替え、式(B)を満たすものの１つをj_fとする。ここでは、j_fが標的制御対象物単位の番号（制御対象物単位を特定するID）である。
【０１７９】
このようにして、制御対象物単位選択部１は、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、選択された目標位置に移動するときに上記制御対象物構造の接続性が維持される制御対象物を選択する（ステップＳ１）。選択された制御対象物単位についての情報は、制御対象物単位移動制御部２に出力される。
【０１８０】
［制御対象物単位移動制御部２］
制御対象物単位移動制御部２は、制御対象物単位選択部１で選択した制御対象物単位j_fを目的位置へ移動させるように制御する。移動操作は、例えば図８、図９、図１０、図１１に例示する手順の移動で定義可能な方法で、目標位置jに隣接する制御対象物単位j'内の空隙に移動させ、その後、例えば、図１４及び図１５に示す手順の移動で定義可能な方法で目的位置jへ移動させる。それが完了したら、unfilled_g[j]の値を１に変更する。１は、目的位置jに制御対象物単位が存在していることを示す値である。
【０１８１】
このようにして、制御対象物単位移動制御部２は、制御対象物構造の接続性を維持しながら、制御対象物単位選択部１で選択された制御対象物単位を目標位置に移動させる（ステップＳ２）。
【０１８２】
［制御部３］
制御部３は、全ての目的位置jが制御対象物に占有されているかを判定し、到達していなければ制御対象物単位選択部１に戻って移動を繰り返すよう制御する。例えば、制御部３は、j=0から順にunfilled_g[j]の値を確認し、unfilled_g[j]=0なるjがあれば制御対象物単位選択部を実行させ、全てのjについてunfilled_g[j_f]=1ならば、制御対象物単位入替部７の処理に移行する。
【０１８３】
このようにして、制御部３は、制御対象物単位が位置していない目標位置がなくなるまで、制御対象物単位選択部１及び制御対象物単位移動制御部２の処理を繰り返すように制御を行う（ステップＳ３）。
【０１８４】
［制御対象物単位入替部７］
制御対象物単位入替部７は、以下の(1)から(4)の処理を行う。これらの処理により、制御対象物単位入替部７は、各制御対象物単位が各制御対象物単位の目標位置に到達するように制御対象物単位の位置を入れ替える処理を制御対象物構造の接続性を維持しながら行う（ステップＳ７）。
【０１８５】
(1) 各制御対象物単位jが目標位置jに到達しているかどうかを示す変数unpermutated_g[j]を定義し、制御対象物単位jの位置が目標位置jに一致しないもの全てについてunpermutated_g[j]←0とし、制御対象物単位jの位置が目標位置jに一致しているもの全てについてunpermutated_g[j]←１とする。
【０１８６】
(2) 式(B)を満たす制御対象物単位jを１つ選択する。制御対象物単位jがすでに目標位置にあるならば、j_alt←jとして（3)へ、そうでないならj0←jとし、以下により、制御対象物単位jを制御対象物単位jの目標位置jに移動させる。移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法で順次行う。その後、制御対象物単位jの目標位置jにあった制御対象物単位jでない制御対象物単位を、あらたに制御対象物単位jとし、新たな制御対象物単位jを新たな目標位置jまで移動させること（移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法）を、制御対象物単位jの目標位置jが制御対象物単位j0の入れ替え前の位置に一致するときの回まで実行し、最後の制御対象物単位jの移動（移動方法は、図８、図９、図１０、図１１、図１４、図1５に示す方法）が済んだら、最後の制御対象物単位jをj_altとする。この時点で、制御対象物単位jの位置が目標位置jに一致しているもの全てについてunpermutated_g[j]←１とする。
【０１８７】
(3) unpermutated_g[j]=0である制御対象物単位jがなくなるまで(4)を繰り返す。
【０１８８】
(4) unpermutated_g[j]=0である制御対象物単位jを１つ選択する。j0←jとする。制御対象物単位jが式(B)を満たすならば、制御対象物単位jを制御対象物単位jの目標位置jに移動させる。移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法で順次行う。その後、制御対象物単位jの目標位置jにあった制御対象物単位jでない制御対象物単位を、あらたに制御対象物単位jとし、新たな制御対象物単位jを新たな目標位置jまで移動させること（移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法）を、制御対象物単位jの目標位置jが制御対象物単位j0の入れ替え前の位置に一致するときの回まで実行する（最後の回の移動方法は、図８、図９、図１０、図１１、図１４、図1５に示す方法）。この時点で、制御対象物単位jの位置が目標位置jに一致しているもの全てについてunpermutated_g[j]←１とする。制御対象物単位jが式(B)を満たさないならば、制御対象物単位j_altを図８、図９、図１０、図１１の動作で制御対象物単位jの隣の位置まで移動させ、図１２，図１３の動作により制御対象物単位jの位置と入れ替える。その後制御対象物単位jを制御対象物単位jの目標位置jに移動させる。移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法で順次行う。その後、制御対象物単位jの目標位置jにあった制御対象物単位を、あらたに制御対象物単位jとし、新たな制御対象物単位jを新たな目標位置jまで移動させること（移動方法は、図８、図９、図１０、図１１、図１２、図１３に示す方法）を、制御対象物単位jの目標位置jが制御対象物単位j_altの現在の位置に一致するときの回まで実行する。その後、制御対象物単位j_altをもとの位置に戻す（移動方法は、図８、図９、図１０、図１１、図１４、図１５に示す方法）。この時点で、制御対象物単位jの位置が目標位置jに一致しているもの全てについてunpermutated_g[j]←１とする。
【０１８９】
＜第四実施形態＞
第一実施形態から第三実施形態では、初期位置にある各制御対象物単位を目標位置に移動を開始する時刻については、１つ前に目標位置に移動を開始した制御対象物単位が、目標位置にたどりついた時刻の後にする手法、すなわち制御対象物単位を１つずつ移動する手法を採用していた。
【０１９０】
これに対して、制御対象物構造内の空隙をフルに使用すれば、複数の制御対象物単位を同時に目標位置まで移動させることも可能である。ここで、移動を開始しようとしている制御対象物単位が、１つ前に移動を開始した制御対象物単位の開始時刻から、一定時間内に移動を開始することができれば、全体の変形に要する時間を、制御対象物単位数の一乗に比例するものにすることができる。以下、そのための手法を述べる。
【０１９１】
ここで、初期位置の集合Sと目標位置の集合Gは接しているものとし、目標位置の集合Gに接している初期位置の集合S内の制御対象物単位の位置の１つを接続位置Gate_S（X_Gate, Y_Gate, Z_Gate）とする。言い換えれば、初期位置の集合Sに含まれる位置であって目標位置の集合Gに接している位置の１つを接続位置とする。
【０１９２】
全ての制御対象物単位は、接続位置Gate_Sを経由して、目標位置G内に入っていくものとする。
【０１９３】
制御対象物単位が移動を開始する順番としては、接続位置Gate_Sからのマンハッタン距離δ(j)の大きいものから優先的に移動を開始させるものとする。
【０１９４】
また、移動を開始しようとしている制御対象物単位のδ値をδ(j)とし、１つ前に移動を開始した制御対象物単位の初期位置のδ値をδ(j-1)とし、αを２以上の正の整数とし、tw=δ(j-1)-δ(j)+αとして、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、tw時間ステップ後に移動を開始する。すなわち、移動を開始しようとしている制御対象物単位が、１つ前に移動を開始した制御対象物単位の初期位置とδ値が同じ場合は、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、α時間ステップ後に移動を開始する。移動を開始しようとしている制御対象物単位のδ値が、１つ前に移動を開始した制御対象物単位の初期位置のδ値よりも１だけ小さい場合は、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、α＋１時間ステップ後に移動を開始する。例えばα＝２とすることで、移動を行う各制御対象物単位は、互いにちょうど１つ分の制御対象物単位分の距離を開けつつ、同時に移動をすることになる。
【０１９５】
さらに、制御対象物単位が位置の入れ替えを行うときは、位置の入れ替えを行う制御対象物単位の後続の制御対象物単位はすべてβ時間ステップだけ、動作を停止する。βは２以上の正の整数であり、例えばβ＝２である。
【０１９６】
以下、第四実施形態の制御装置及び方法の動作の詳細を述べる。
【０１９７】
制御装置は、図２４に示すように、パス決定部８、待ち時間調整部９、制御対象物単位選択部１及び制御対象物単位移動制御部２を例えば備えている。
【０１９８】
制御方法は、制御装置が、図２５及び以下に説明するステップＳ８，Ｓ９、Ｓ１，Ｓ２の処理を行うことにより例えば実現される。
【０１９９】
以下、第一実施形態と異なる処理を中心に説明する。第一実施形態と同じ部分については説明を省略する。
【０２００】
［パス決定部８］
パス決定部８は、各制御対象物単位が接続位置を通るように、かつ、各制御対象物単位が接続位置を通過した後は接続位置からの距離が近くならないように、各制御対象物単位が目標位置に到達するまでのパスを接続位置から遠い初期位置にある制御対象物単位のパスから順に決定する（ステップＳ８）。
【０２０１】
決定されたパスについての情報は、待ち時間調整部９、制御対象物単位選択部１及び制御対象物単位移動制御部２に出力される。
【０２０２】
例えば、パス決定部８は、以下に説明する(1)から(3)の処理を行うことにより、各制御対象物単位jが、各々の初期位置から目標位置まで移動するためのパスを計算する。
【０２０３】
以下の処理により、パスの各位置は、pass[j][t](t=0,1,2,…,t_max[j])に格納される。また、制御対象物単位jが制御対象物単位j'と入れ替えを行う時刻は、exchange[j][t] (t=0,1,2,…,t_max[j])に格納される。
【０２０４】
(1) パス決定部８は、各制御対象物単位の仮想位置を、その各制御対象物単位の初期位置に設定する。ここで、パス決定部８の処理はパスを決定するだけであり、パス決定部８の処理においては制御対象物単位の実際の位置は変わらない。各制御対象物単位の実際の位置と区別するために、「仮想位置」という用語を用いる。なお、パス決定部８で決定されたパスに従った制御対象物単位の実際の移動は、制御対象物単位選択部１及び制御対象物単位移動制御部２で行われる。
【０２０５】
また、パス決定部８は、exchange[j][t]を全てのj,tで0に初期化する。
【０２０６】
そして、パス決定部８は、(2)-(3)の処理を制御対象物単位0から制御対象物単位j_maxまで実行する。ここで、ｊの番号は、δ値の大きい順に振ることとする。すなわち、δ(0)≧δ(1)≧δ(2)≧…とする。言い換えれば、接続位置Gate_Sから遠い初期位置にある制御対象物単位から順に、(2)-(3)の処理を行う。
【０２０７】
(2) パス決定部８は、制御対象物単位jの初期位置から接続位置Gate_Sに至る道筋を計算し、pass[j][t]に格納する。パス決定部８は、この時の接続位置Gate_Sが格納されているpass内のt番号を、time_at_gate[j]及びtime_at_end[j]のそれぞれに格納する。なお、パス決定部８は、例えば、制御対象物単位jの移動開始時間t_start[j]は、δ(j)=δ(j-1)のときは、t_start[j]=t_strat[j-1]+αに、δ(j)=δ(j-1)-1のときは、t_start[j]=t_strat[j-1]+α+1にする。パス決定部８は、t<t_start_tのpass値（すなわち、移動開始前のpass値）を、制御対象物単位jの初期位置とする。
【０２０８】
(3) パス決定部８は、t=time_at_end[j]+1からのpass内に、接続位置Gate_Sから、制御対象物単位jの目標位置までの道筋を計算して格納する。制御対象物単位jの目標位置が、他の制御対象物単位で埋められているかいないかで、処理が異なる。(3)の処理の例は、以下の(3-0)から(3-3)の処理である。
【０２０９】
(3-0) パス決定部８は、jm←jとする。
【０２１０】
(3-1) パス決定部８は、制御対象物単位jmの目標位置が他の制御対象物単位j'によって埋められている場合は、目標位置G内で制御対象物単位j'の隣にある制御対象物単位j_nまでの道筋を、t=time_at_end[j]+1からのpass[j][t]に追加する。パス決定部８は、j_nとしては、j_nからj'に至る方向a_exが1,2,5の場合を優先的に選び、そのようなj_nがない場合のみ、a_ex=3,4,6の場合のj_nを選ぶ。パス決定部８は、制御対象物単位jmがj_nに至る時刻をt_exとしたとき、exchange[j][t_ex]←a_exとする。ｊ'をpassの最後尾に追加し、その時のtをtime_at_end[j]とする。パス決定部８は、制御対象物単位jmの仮想位置の値に、制御対象物単位j'の仮想位置の値を代入し、(3-2)の処理を行う。パス決定部８は、制御対象物単位jmの目標位置が他の制御対象物単位j'によって埋められていない場合は、(3-3)の処理を行う。
【０２１１】
(3-2)制御対象物単位j'の目標位置が、他の制御対象物単位ｊ''によって占有されている場合は、jm←j', j'←j''とし(3-1)の処理を繰り返す。そうでない場合は(3-3)の処理を行う。
【０２１２】
(3-3) パス決定部８は、(3-2)の処理の実行がなかった場合は、制御対象物単位jmの目標位置から、目標位置G内の未充填位置内でもっとも近いマンハッタン距離にあり、目標位置G内の充填済み位置に接した位置を目標位置j_targetとし、j_targetに接する目標位置G内充填済み位置をj_target'として、接続位置Gate_Sからj_target'に至る目標位置G内の充填済み位置を経由した道筋をt=time_at_end[j]+1からのpass[j][t]に追加する。パス決定部８は、passの最後尾にj_targetを追加する。パス決定部８は、j_targetを格納したpass[j][t]のt値をtime_at_end[j]とする。
【０２１３】
パス決定部８は、(3-2)の処理の実行があった場合は、目標位置G内の未充填位置内で制御対象物単位j'の目標位置から、もっとも近いマンハッタン距離にあり、かつ、「制御対象物単位j'の現仮想位置から、接続位置Gate_Sからのδの値が制御対象物単位j'の現仮想位置でのδ値より小さくならないようにたどって行ける目標位置G内の充填済み位置に接している位置」を目標位置j_targetとし、j_targetに接する目標位置G内充填済み位置をj_target'として、ｊ'からj_target'に至る目標位置G内の充填済み位置を経由した道筋をt=time_at_end[j]+1からのpass[j][t]に追加する。passの最後尾にj_targetを追加する。j_targetを格納したpass[j][t]のt値をtime_at_end[j]とする。このように、パス決定部８は、後続の制御対象物単位に衝突しないようδの小さくなる道をたどらないようにパスを決定する。
【０２１４】
［待ち時間調整部９］
待ち時間調整部９は、各制御対象物単位が衝突しないように、各制御対象物単位の待ち時間を決定する（ステップＳ９）。
【０２１５】
決定された待ち時間についての情報は、制御対象物単位選択部１及び制御対象物単位移動制御部２に出力される。
【０２１６】
待ち時間調整部９は、制御対象物単位入れ替え時の、他の制御対象物単位の待ち時間を考慮して、pass値を修正する。待ち時間調整部９は、制御対象物単位jが時刻tで入れ替えを行う場合、制御対象物単位jの後続の全ての制御対象物単位の時刻ｔ以降のpass値をβ時間ステップ分ずらしていく。
【０２１７】
例えば、待ち時間調整部９は、以下に説明する(1)から(2)の処理を行うことにより、各制御対象物単位の待ち時間を決定する。
【０２１８】
(1) 待ち時間調整部９は、(2)の処理を制御対象物単位0から制御対象物単位j_maxまで実行する。
【０２１９】
(2) 待ち時間調整部９は、t=0からtime_at_end[j]まで以下の(2-1)の処理を実行する。
【０２２０】
(2-1) 待ち時間調整部９は、exchange[j][t]が0以外の値のとき、制御対象物単位jの後続の制御対象物単位j_sub (j_sub>j)すべてについて、pass[j_sub][t']←pass[j_sub][t'-β]、exchange[j_sub][t']← exchange[j_sub][t'-β]とし(t'≧t+β)、pass[j_sub][t+β-1]←pass[j_sub][t]、pass[j_sub][t+β-2]←pass[j_sub][t]、・・・、pass[j_sub][t+1]←pass[j_sub][t]、exchange[j_sub][t]←0, exchange[j_sub][t+1]←0、・・・、exchange[j_sub][t+β-2]←0、exchange[j_sub][t+β-1]←0 とする。待ち時間調整部９は、t<t_start[j_sub]のときは、t_start[j_sub]をβ回インクリメントする。待ち時間調整部９は、t<time_at_gate[j_sub]のときは、time_at_gate[j_sub]をβ回インクリメントする。また、待ち時間調整部９は、t<time_at_end[j_sub]のときは、time_at_end[j_sub]をβ回インクリメントする。
【０２２１】
［制御対象物単位選択部１及び制御対象物単位移動制御部２］
制御対象物単位選択部１は、パス決定部８により決定されたパスに従って移動させる制御対象物単位を選択する（ステップＳ１）。また、制御対象物単位移動制御部２は、パス決定部８により決定されたパス及び待ち時間調整部９により決定された待ち時間に従って、制御対象物単位選択部１により選択された制御対象物単位を移動させる（ステップＳ２）。
【０２２２】
例えば、制御対象物単位選択部１及び制御対象物単位移動制御部２は、以下に説明する(1)の処理を行うことにより、決定されたパス及び待ち時間に従って、制御対象物単位を移動させる。
【０２２３】
(1) 制御対象物単位選択部１及び制御対象物単位移動制御部２は、時刻t=0からtime_at_end[j_max]-1まで、以下の(1-1)の処理を繰り返す。
【０２２４】
(1-1) 制御対象物単位選択部１及び制御対象物単位移動制御部２は、全ての制御対象物単位jについて、exchange[j][t]が0以外の値のときは、pass[j][t]の位置にある制御対象物単位jとpass[j][t+1]の位置にある制御対象物単位との位置の入れ替えを行う。言い換えれば、全ての制御対象物単位jについて、exchange[j][t]が0以外の値のときは、制御対象物単位選択部１がpass[j][t]の位置にある制御対象物単位jを選択し、制御対象物単位移動制御部２がpass[j][t+1]の位置に移動させる。以降、pass[j][t+1]の位置にあった制御対象物単位を新たな制御対象物単位jとする。exchange[j][t]→a_exとし、a_ex=1,2,5のときは、図１２の動作で入れ替えが行われる。exchange[j][t]→a_exとし、a_ex=3,4,6のときは、図１３の動作で入れ替えが行われる。
【０２２５】
制御対象物単位選択部１及び制御対象物単位移動制御部２は、exchange[j][t]が0のときは、pass[j][t]の位置にある制御対象物単位jをpass[j][t+1]の位置に移動させる。言い換えれば、exchange[j][t]が0のときは、制御対象物単位選択部１がpass[j][t]の位置にある制御対象物単位jを選択し、制御対象物単位移動制御部２がpass[j][t+1]の位置に移動させる。この移動は、t=t_start[j]のときは、図８又は図９に示す動作で、t=time_at_end[j]-1のときは、図１４又は図１５に示す動作で行われる。それ以外のtの値のときは図１０，１１に示す動作で行われる。
【０２２６】
非特許文献２の技術は、ヘテロジニアスを前提とする隊列形成を行うことができるが、変形に要する時間が制御対象物単位数の二乗に比例する時間だけ、必要であった。変形に要する時間が制御対象物単位数の一乗に比例する時間であるような手法は、ヘテロジニアスな制御対象物単位の隊列変形においては実現されていなかった。
【０２２７】
以上の処理により、制御対象物単位数の一乗に比例する実行時間での隊列変形を実現することができる。
【０２２８】
［補足］
第一実施形態から第四実施形態の制御対象物単位選択部１は、制御対象物単位が位置していない目標位置であって、制御対象物構造に隣接している目標位置を選択し、選択された目標位置に移動させる制御対象物単位を選択していると言える。
【０２２９】
また、制御対象物単位移動制御部２は、制御対象物構造の接続性を維持しながら、選択された制御対象物単位を目標位置に移動させていると言える。
【０２３０】
［プログラム及び記録媒体］
制御装置の各部における処理をコンピュータによって実現する場合、これらの装置の各部がが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各部の処理がコンピュータ上で実現される。
【０２３１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２３２】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【０２３３】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2019040580.tif 000003
【図２】
2019040580.tif 000004
【図３】
2019040580.tif 000005
【図４】
2019040580.tif 000006
【図５】
2019040580.tif 000007
【図６】
2019040580.tif 000008
【図７】
2019040580.tif 000009
【図８】
2019040580.tif 000010
【図９】
2019040580.tif 000011
【図１０】
2019040580.tif 000012
【図１１】
2019040580.tif 000013
【図１２】
2019040580.tif 000014
【図１３】
2019040580.tif 000015
【図１４】
2019040580.tif 000016
【図１５】
2019040580.tif 000017
【図１６】
2019040580.tif 000018
【図１７】
2019040580.tif 000019
【図１８】
2019040580.tif 000020
【図１９】
2019040580.tif 000021
【図２０】
2019040580.tif 000022
【図２１】
2019040580.tif 000023
【図２２】
2019040580.tif 000024
【図２３】
2019040580.tif 000025
【図２４】
2019040580.tif 000026
【図２５】
2019040580.tif 000027