(57)【要約】【課題】制御対象物単位の初期位置の集合と制御対象物単位の目標位置の集合との共通部分に非接続箇所がある場合でも適用可能な隊列制御を実現する制御技術を提供する。【解決手段】制御装置は、共通位置の集合に属する位置の中で、Head_firstからの距離が近い位置をHead_lastとして選択し、Head_firstからHead_lastに至る目標位置内の経路上の位置からなる系列を目的位置系列とする目的位置系列出力部１と、目的位置系列の位置の中の制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第一移動部２と、目標位置の集合に属する位置の中に制御対象物単位が位置していない位置がある場合には、その制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第二移動部３と、を備えている。【選択図】図１
2019074997.tif 000002
【特許請求の範囲】
【請求項１】
初期位置にある複数の制御対象物単位を目標位置に移動させる制御装置であって、
各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、
目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、共通位置の集合に属する位置をHead_firstとして選択し、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、Head_firstと異なる共通位置の集合に属する位置の中で、Head_firstからの距離が近い位置をHead_lastとして選択し、Head_firstからHead_lastに至る目標位置内の経路上の位置からなる系列を目的位置系列とする目的位置系列出力部と、
上記目的位置系列の位置の中の制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第一移動部と、
目標位置の集合に属する位置の中に制御対象物単位が位置していない位置がある場合には、その制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第二移動部と、を含み、
上記第一移動部及び上記第二移動部は、制御対象物単位を移動させるときには、先頭の制御対象物単位及び尾部の制御対象物単位を選択し、上記先頭の制御対象物単位から上記尾部の制御対象物単位までの一連の制御対象物単位を先頭の制御対象物単位の動作を追従するように移動させる、
制御装置。
【請求項２】
請求項１の制御装置であって、
上記制御対象物単位は、二つの制御対象物単位の組み合わせでできており、
上記第一移動部及び上記第二移動部は、上記制御対象物単位を構成する二つの制御対象物単位のうち、一つずつを制御対象物単位の大きさ分の距離だけ交互に移動させることによって上記制御対象物単位を移動させる、
制御装置。
【請求項３】
初期位置にある複数の制御対象物単位を目標位置に移動させる制御方法であって、
各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、
目的位置系列出力部が、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、共通位置の集合に属する位置をHead_firstとして選択し、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、Head_firstと異なる共通位置の集合に属する位置の中で、Head_firstからの距離が近い位置をHead_lastとして選択し、Head_firstからHead_lastに至る目標位置内の経路上の位置からなる系列を目的位置系列とする目的位置系列出力ステップと、
第一移動部が、上記目的位置系列の位置の中の制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第一移動ステップと、
第二移動部が、目標位置の集合に属する位置の中に制御対象物単位が位置していない位置がある場合には、その制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第二移動ステップと、を含み、
上記第一移動ステップ及び上記第二移動ステップは、制御対象物単位を移動させるときには、先頭の制御対象物単位及び尾部の制御対象物単位を選択し、上記先頭の制御対象物単位から上記尾部の制御対象物単位までの一連の制御対象物単位を先頭の制御対象物単位の動作を追従するように移動させる、
を含む制御方法。
【請求項４】
請求項１又は２の制御装置の各部としてコンピュータを機能させるためのコンピュータ読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の制御対象物単位の行動を制御する技術に関する。
【背景技術】
【０００２】
近年、多数の自律移動ロボットを効率的に制御にするための研究が活発に行われている。その任務内容は、人の入れない箇所の監視、物品の搬送などさまざまであるが、多数のロボットの協調動作による隊列形成を効率的に行わせるための技術が求められており盛んに研究が行われている。
【０００３】
特に、ロボットの隊列制御の中でも、ロボット同士が互いに接したままの状態で、アメーバのように全体で移動を行うという仮定の下でのロボット隊列制御においては、ロボット同士の相対的な位置関係から、各ロボットの絶対位置の決定が可能であるという利点と、付加的な位置計測用の装備を必要としないという利点があり、そのようなロボットの研究もおこなわれている。例えば、非特許文献１に示す研究に至る一連の研究では、ある隊列から他の隊列に変化する隊列制御が示されている（例えば、非特許文献１参照。）。
【０００４】
このような、多数のロボットによる効率的な隊列形成を実現するには、それぞれのロボットの配置、動作順序などを事前に計画することが重要である。このような計画においては、当然ながら、複数のロボットが動作する実環境における障害物の存在や経路の形状なども十分に考慮しなければならない。
【０００５】
非特許文献１に示す研究に示されている手法では、複数の立方体形状のロボット同士での面せん断動作(あるロボットが、他のロボットと接した状態で、接する面上をスライド移動する動作)と回り込み動作によるロボットの隊列変形が扱われている。
【０００６】
非特許文献２に示す研究に示されている手法では、複数の立方体形状のロボット同士での伸長収縮面動作(あるロボットが、他のロボットと接した状態で、伸び縮みしつつ移動する動作)によるロボットの隊列変形が扱われている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】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.
【非特許文献２】S. Vassilvitskii, M. Yim, J. Suh, “A Complete, Local and Parallel Reconfiguration Algorithm for Cube Style Modular Robots”, in Proc.2002 IEEE Int. Conf. Robotics and Automation, pp. 117-122, Washington DC, May, 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１では、各ロボットが接した状態での動作を想定し、各ロボットが同じ特性（ホモジニアス）である。つまり、目標形態内部での各ロボットの目標位置が定まってない場合の隊列制御を実現しているが、ロボットが初期状態でとる隊列位置の集合とロボットの目標位置の集合の共通部分内に非接続箇所がない条件でのみの適用に限られている。
【０００９】
そこで、本発明は、制御対象物単位の初期位置の集合と制御対象物単位の目標位置の集合との共通部分に非接続箇所がある場合でも適用可能な隊列制御を実現する制御装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
この発明の一態様による制御装置は、初期位置にある複数の制御対象物単位を目標位置に移動させる制御装置であって、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとして、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、共通位置の集合に属する位置をHead_firstとして選択し、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、Head_firstと異なる共通位置の集合に属する位置の中で、Head_firstからの距離が近い位置をHead_lastとして選択し、Head_firstからHead_lastに至る目標位置内の経路上の位置からなる系列を目的位置系列とする目的位置系列出力部と、目的位置系列の位置の中の制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第一移動部と、目標位置の集合に属する位置の中に制御対象物単位が位置していない位置がある場合には、その制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる第二移動部と、を備えており、第一移動部及び第二移動部は、制御対象物単位を移動させるときには、先頭の制御対象物単位及び尾部の制御対象物単位を選択し、先頭の制御対象物単位から尾部の制御対象物単位までの一連の制御対象物単位を先頭の制御対象物単位の動作を追従するように移動させる。
【発明の効果】
【００１１】
本発明によれば、制御対象物単位の初期位置の集合と制御対象物単位の目標位置の集合との共通部分に非接続箇所がある場合でも適用可能な隊列制御を実現することができる。
【図面の簡単な説明】
【００１２】
【図１】ロボットの移動を説明するための図。
【図２】制御対象物単位の初期位置及び目標位置を説明するための図。
【図３】ボイドの移動の様子を説明するための図。
【図４】制御対象物単位の例を説明するための図。
【図５】タネリングを説明するための図。
【図６】タネリングを説明するための図。
【図７】タネリングを説明するための図。
【図８】制御対象物単位の移動を説明するための図。
【図９】制御対象物単位の移動を説明するための図。
【図１０】制御対象物単位の移動を説明するための図。
【図１１】制御対象物単位の移動を説明するための図。
【図１２】制御対象物単位の移動を説明するための図。
【図１３】制御対象物単位の移動を説明するための図。
【図１４】制御対象物単位の移動を説明するための図。
【図１５】制御対象物単位の移動を説明するための図。
【図１６】制御装置の例を説明するためのブロック図。
【図１７】第一移動部２の例を説明するためのブロック図。
【図１８】第二実施形態の制御方法を説明するための流れ図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００１４】
＜理論的背景＞
まず、制御装置及び方法の理論的背景について説明する。以下、行動制御の対象である制御対象物が、ロボットである場合を例に挙げて説明するが、制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００１５】
［問題設定］
多数の制御対象物が協調して、各制御対象物が接した状態を維持しつつ移動を行い、開始位置における隊列形成状態から目標位置への隊列変形を行う任務は、例えば図１に例示するような、互いに接する面同士をスライドさせて移動していくことが可能な立方体型の制御対象物の使用を想定する。図２に示すように、壁で区切られた部屋（ただし図中、壁を省略する）においての開始位置から目標位置まで複数の制御対象物の移動によって実現するものである。
【００１６】
制御対象物については、例えば図１に示すように、制御対象物の周囲縦横高さ方向（以下「上下左右前後方向」ともいう）６マスのうち一つに他の制御対象物が存在している状態を維持しながら移動をするものとする。この手法では１つの制御対象物自身が、一台の制御対象物のサイズ分の距離を移動することで、一回の動作の移動量を正確に測ることができるというメリットがある。また、一つの面を共有する隣り合う制御対象物との相対的な位置を計測しあうことで、制御対象物の群れ全体の中での各制御対象物の位置も容易に知ることができる。このため、制御対象物の移動量の誤差によって、隊列が崩れるといった問題を起こしにくい。また、複数の制御対象物を連結したように、同時に複数の制御対象物を移動させていくことが可能である。なお、制御対象物は、隣の位置に他の制御対象物が存在しているか否か、障害物があるか否か、そして、自身が目標位置上にいるかどうかを知ることができるものとする。
【００１７】
任務を行う制御対象物は、p台（p≧16=8×2）であり、各制御対象物は、隣接する制御対象物と一面以上を共有しつつ、三次元空間におけるX-Y-Z軸方向に移動可能とする。図１の各立方体は、それぞれの制御対象物の位置を示すものである。各立方体には制御対象物は一台しか存在することができない。それぞれの制御対象物は、移動しようとする方向に障害物か他の制御対象物がある場合には、静止をするものと仮定する。なお、制御対象物が存在しうる立方体状の空間をマス、または、格子ともいう。図２において、濃い灰色のマスは制御対象物が存在する位置を示す。図２Ａの制御対象物が存在する位置は制御対象物の開始位置の集合を示し、図２Ｃの制御対象物が存在する位置は制御対象物の目標位置の集合を示す。図２Ｂに示すように、目標位置の集合と開始位置の集合は接している。目標位置の集合で表される領域を目標隊列エリアともいう。このように、各開始位置及び各目標位置は、それぞれ縦横高さ方向の少なくとも何れかの方向において他の開始位置及び目標位置と隣接し、制御対象物の開始位置及び目標位置での隊列形状はそれぞれ一塊の任意の形状である。
【００１８】
［制御対象物の座標設定］
それぞれの制御対象物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]）とするとき、本問題は、初期位置に配置された制御対象物が、目標位置まで移動するための行動計画を求めることと定義できる。制御対象物の開始位置の集合をs、目標位置（Xre[i],Yre[i],Zre[i]）の集合をgとする。
【００１９】
［任務空間の定義］
iを制御対象物番号としたとき、制御対象物iの各状態（制御対象物の位置と行動）は離散値で表現される。部屋をX,Y,Zの直交座標系からなる3次元空間で表すと、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軸負方向に１格子だけ移動する
とする。
【００２１】
［探索計算上の問題点］
このような任務環境における状態空間は、制御対象物数×３の次元数の状態を持ち、かつ選択可能な行動数は、制御対象物の行動（＝７通り）の制御対象物数乗だけ存在する。例えば、制御対象物数が50で、部屋の縦横高さ方向の格子数がそれぞれ20であるとすれば状態数は20の150乗個にもなり、探索計算に要する資源の量は膨大なものとなる。さらに制御対象物数が１台増えるごとに、その状態数は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.
【００２５】
［４マス制御対象物単位の導入］
そこで、図４Ａに示すように、４つの隣接した制御対象物を一つの単位とし（制御対象物単位）、制御対象物は、この制御対象物単位を維持しつつ移動を行うこととする。言い換えると、４台毎に１つの制御対象物単位を構成し、１つの制御対象物単位を構成する４台の制御対象物はそれぞれ３つの方向において１つの制御対象物単位を構成する他の制御対象物と隣接した状態を維持しつつ移動を行う。この制御対象物単位の集団は、互いに制御対象物単位ごとに一面を共有し、接しながら移動をするように制御される。同じ制御対象物単位に所属する４つの制御対象物は同一でホモジニアスであるとし、同じ制御対象物単位内では、どの制御対象物が単位内のどの位置にあるかは問わないものとする。
【００２６】
このような４つの制御対象物を一つの単位とした移動を行う理由は、各制御対象物単位の内部にある４つの空隙空間を、他の制御対象物単位に属する制御対象物が通過することが出来、それにより、異なる制御対象物単位内に属する制御対象物同士の行き来がすることが容易である点である。また、各制御対象物単位の内部にある４つの空隙空間を、他の制御対象物単位に属する制御対象物が通過する際の接続性の維持も容易である。すなわちこれは、隊列形態の維持を考量しなければならない各制御対象物の動作の決定において、制御対象物同士の接続を考慮するための計算負荷を軽減することにつながるからである。
【００２７】
ここでは４台の制御対象物がなす制御対象物単位が一つのマスの単位（本実施形態では、以下、この単位を「マス単位」または「位置単位」ともいう）であるとし、一つのマス単位を一状態として状態空間を組む。制御対象物単位の位置を（Xr_u[j],Yr_u[j], Zr_u[j]）（j=0,1,2,…j_max-1）としたとき、その制御対象物単位j内の制御対象物をi1,i2,i3,i4とすれば、
Xr[i1] = 2 × Xr_u[j] 
Yr[i1] = 2 × Yr_u[j] + 1
Zr[i1] = 2 × Zr_u[j] 
Xr[i2] = 2 × Xr_u[j] + 1
Yr[i2] = 2 × Yr_u[j] 
Zr[i2] = 2 × Zr_u[j] 
Xr[i3] = 2 × Xr_u[j]
Yr[i3] = 2 × Yr_u[j]
Zr[i3] = 2 × Zr_u[j]
Xr[i4] = 2 × Xr_u[j]
Yr[i4] = 2 × Yr_u[j]
Zr[i4] = 2 × Zr_u[j] + 1
【００２８】
なお、各制御対象物iが所属する制御対象物単位jを表す変数をRr[i]=jとし、これは隊列制御のどの時刻においても不変である。また、制御対象物が上記i1,i2,i3,i4のどの位置にあるかを指す変数をIr[i]=(1,2,3,4)とする。各制御対象物単位の初期位置を（Xr_u0[j],Yr_u0[j],Zr_u0[j]）とし、目標位置を（Xr_ue[j],Yr_ue[j],Zr_ue[j]）とする。以下、制御対象物の全体数pを4の倍数とする。
【００２９】
なお、図４Ｂのように、二つの制御対象物単位を合わせることで、８マスの制御対象物単位を構成することも可能であり、８マスの制御対象物単位で構成された制御対象物群の隊列制御も、４マス制御対象物単位の制御を行うことで可能となる。
【００３０】
また、図４の例に限らず、制御対象物単位は以下の条件を満たすよう構成されていればよい。すなわち、制御対象物単位は、（１）三次元の直交座標系で各軸方向に長さＭ（Ｍ≧２、ただし、制御対象物１個の長さを長さ１とする）を有する立方体形状の空間（以降この空間をメタモジュールとする。）内の部分構造であり（言い換えれば、制御対象物単位はメタモジュールの一部を占め）、（２）当該メタモジュール内の制御対象物単位に含まれる制御対象物の数と、当該メタモジュール内の制御対象物単位以外の部分（すなわち空隙）の数とが等しく、（３）各軸方向にＭ個の制御対象物が隣接する構造を含む。例えば、図４に例示する制御対象物単位は、（１）各軸方向の長さＭ＝２とした計８マスの立方体からなるメタモジュールの部分構造であり、（２）制御対象物単位内の制御対象物の数が４個、メタモジュール内の空隙の数が４個と等しく、（３）各軸方向において２個の制御対象物が隣接する構造が含まれている。
【００３１】
以後の説明では、制御対象物単位の一例として、図４に示す４個の制御対象物からなる構造を制御対象物単位とする場合について説明するが、例えば、Ｍ３個分の大きさのメタモジュール内で上述の（１）〜（３）の条件を満たすよう構成された制御対象物単位であれば同様の効果を得ることができる。
【００３２】
［ホモジニアス隊列制御］
各制御対象物単位jが開始位置の集合S内にて、任意の位置に存在する状態から、各制御対象物単位jをそれぞれ目標位置の集合のうちのいずれかの位置（Xr_ue[j],Yr_ue[j],Zr_ue[j]）に配置させるホモジニアス制御対象物隊列制御の方法について以下説明していく。
【００３３】
ここで、集合S、Gは、４マスの制御対象物単位２つが合わさってできる８マスの制御対象物単位で構成されているものとする。４マス制御対象物単位数j_maxは偶数であり、一つの８マス制御対象物単位を構成する二つの４マス制御対象物単位j1,j2の番号の間には、j1+ j_max/2 = j2の関係がある（j_max=8の場合、0,1,2,3がj1、4,5,6,7がj2であり、(j1,j2)=(0,4)（1,5）（2,6）（3,7）の組が８マス単位を構成する。）。j2は図４Ｂでいうところのドットで表された４マス制御対象物単位である。
【００３４】
図５に示す通り、集合Sの状態にある制御対象物構造を集合Gの状態に変形させるには、タネリングと呼ばれる方法をとる。図５に示す動作においては、先頭の制御対象物単位Headと尾部の制御対象物単位Tailを結ぶ一連の制御対象物単位がいわば蛇のような形で、先頭制御対象物単位Headの動作を追従する方式で動作する。なお、他のタネリングを行う制御対象物単位、例えば非特許文献２に示すような伸長収縮制御対象物単位を使用した２×２×２の制御対象物単位を使用した制御対象物構造においてもこのタネリング動作は同様であり、本発明で示すタネリングのHeadとTailの選択方法は、同様に適用可能である。タネリングを使用した隊列変形は障害物のある環境においても、隊列変形動作を初期位置の集合と目標位置の集合以外の位置を使用せずに実行可能である。
【００３５】
図６に、本発明で使用する２つの４マス制御対象物単位を使用した８マス制御対象物単位のタネリング動作の１ステップを示す。図６の動作１の制御対象物単位０の動作の詳細は図１２に示すとおりである。図６の動作２の制御対象物単位１の動作の詳細は図１０に示すとおりである。図６の動作３の制御対象物単位0、１の動作の詳細は図１４に示すとおりである。図６の動作４の制御対象物単位0の動作の詳細は図１１に示すとおりである。図６の動作５の制御対象物単位１の動作の詳細は図１４に示すとおりである。図６の一連の動作により、「１」の８マス制御対象物単位が伸びて、先頭制御対象物単位である「０」の８マス制御対象物単位が１つだけ位置を進める。なお、ここでは、図６に示すように、同じＩＤの制御対象物単位（ここで「ＩＤ」とは図６の「０」「１」等の数字である）の占有する空間の大きさが大きくなることを「制御対象物単位が伸びる」と表現している。 
【００３６】
図６の動作を繰り返す様子を図７に示す。図７の矢印「２」の動作により、伸びていた「１」の８マス制御対象物単位が縮み、また、「２」の８マス制御対象物単位が伸びて、「１」の８マス制御対象物単位が１つだけ位置を進める。図７の矢印「３」の動作により、伸びていた「２」の８マス制御対象物単位が縮み、また、尾部制御対象物単位である「３」の８マス制御対象物単位が伸びて、「２」の８マス制御対象物単位が１つだけ位置を進める。図７の矢印「４」の動作により、伸びていた「３」の８マス制御対象物単位が縮み、「３」の８マス制御対象物単位が１つだけ位置を進める。これにより、尾部制御対象物単位（Tail）の動作が完了する。図７の最終動作における尾部制御対象物単位の動作の詳細は、図８に示すとおりである。
【００３７】
つづいて、先頭制御対象物単位Headと尾部制御対象物単位Tailの選び方について述べる。制御対象物の変形動作中に、初期位置の集合Sと目的位置の集合Gの共通部分CがNcommon個の部分に分かれているとし、それぞれの部分を共通部分C[１]，C[２]，C[３],…,C[Ncommon]とする。
【００３８】
まず先頭制御対象物単位Headの選択について注意すべきことは、変形動作中に全体の制御対象物構造からこれらのNcommon個のうちのいずれも、制御対象物構造から非接続にならないようにすることである。例えば、S内の制御対象物単位を徐々にG内に移動させたとするとその分S内に残る制御対象物単位数は少なくなる。この過程で注意を怠ると、共通部分が制御対象物構造から非接続とならないようにするために使用できる制御対象物がS内にもG内にも存在しないという事態が起こりうる。それを避けるために、S内の制御対象物単位を移動させてG内に移す際に、G内の領域でNcommon個の共通部分が制御対象物構造中で接続された状態にできる最小限の数の制御対象物単位を使って、G内側だけでNcommon個の共通部分が接続された状態にできる構造に優先的に配置させるようにする。
【００３９】
＜実施形態＞
以下、制御装置及び方法の一実施形態について説明する。
【００４０】
制御装置は、図１６に示すように、目的位置系列出力部１、第一移動部２、第一判定部３、第二判定部４及び第二移動部５を例えば備えている。
【００４１】
制御方法は、制御装置の各部が、図１８及び以下に説明するステップＳ１からステップＳ５の処理を行うことにより例えば実現される。
【００４２】
変数common_prevの初期値は１に設定しておくものとし、各共通部分iが制御対象物構造中で接続を維持しているか否かを示す変数Connected[i]の初期値はConnected[1]=1, Connected[i]=0 (ただしi≠1)とする。
【００４３】
［目的位置系列出力部１］
目的位置系列出力部１は、以下の手順により先頭の制御対象物単位の移動先の位置の系列を求める。
【００４４】
(1) 共通部分C[common_prev]に所属し、G内の共通部分以外の領域に接する制御対象物単位位置をHead_firstとして選択する。すなわち、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、共通位置の集合に属する位置をHead_firstとして選択する。
【００４５】
(2) Head_firstに接するG内の共通部分以外の領域内の位置を制御対象物単位位置Head_nextとして選択する。すなわち、Head_firstの位置に隣接する位置であって、目標位置の集合に属し共通位置の集合に属しない位置をHead_nextとして選択する。
【００４６】
そして、G内の各位置のHead_firstからのG内でのマンハッタン距離δHを計算する。
【００４７】
(3) Connected[i]=0である共通部分C[i]に所属する制御対象物単位で、G内の共通部分以外の領域に接する制御対象物単位のうち、(2)で計算したマンハッタン距離δHが最小のものを制御対象物単位Head_lastとして選び、制御対象物単位Head_firstから制御対象物単位Head_lastに至るG内の最短パスを計算する。そのパスの経路位置をHead[]の値に格納する。すなわち、Head内の最終点位置をHead[n_last]として、Head[0]=Head_first, Head[1]=Head_next,…,Head[n_last]=Head_lastである。
【００４８】
こうして求めたHead[]の系列を先頭制御対象物単位の移動先の位置の系列を、目的位置系列として出力する。
【００４９】
このようにして、目的位置系列出力部１は、目標位置の集合に属するが共通位置の集合に属しない位置に隣接する位置であって、Head_firstと異なる共通位置の集合に属する位置の中で、Head_firstからの距離が近い位置をHead_lastとして選択し、Head_firstからHead_lastに至る目標位置内の経路上の位置からなる系列を目的位置系列とする（ステップＳ１）。
【００５０】
目的位置系列は、第一移動部２及び第一判定部３に出力される。
【００５１】
図１５に、Head_first,Head_next,Head_last,目的位置系列の例を示す。図１５（Ａ）（Ｂ）において、白のマスは初期位置の集合Sを表し、ドットのマスは目標位置の集合Gを表し、斜線部分のマスは初期位置の集合と目標位置の集合の共通部分Cを表す。図１５（Ａ）において、Head_first, Head_next,Head_lastは図１５（Ａ）に示したように選択されたとする。このとき、目的位置系列は、図１５（Ａ）において太線で示した位置の系列とする。
【００５２】
［第一移動部２］
第一移動部２は、目的位置系列に従って、順次タネリング動作を行うことで、初期位置の集合S内にある制御対象物単位を目標位置の集合G内に移動させる。
【００５３】
第一移動部２は、図１７に例示するように、先頭位置設定部２１、尾部選択部２２、移動部２３及び判定部２４から構成される。
【００５４】
以下、先頭位置設定部２１、尾部選択部２２、移動部２３及び判定部２４の各処理について説明する。
【００５５】
［［先頭位置設定部２１］］
先頭位置設定部２１は、目的位置系列の先頭から順番にまだ設定していない位置を１つ読み出して、先頭位置に設定する（ステップＳ２１）。ここで設定された先頭位置をHead[k]と呼ぶこととする。ここで、kは、k=0からn_last-1までの整数である。
【００５６】
この際、先頭位置設定部２１は、先頭位置Head[k]の目的位置であるHead[k+1]に制御対象物単位が存在しない先頭位置のうちkが最小の位置を選択する。言い換えれば、先頭位置設定部２１は、先頭位置Head[k]の目的位置であるHead[k+1]に制御対象物単位が存在する場合には、その先頭位置Head[k]を選択しない。
【００５７】
［［尾部選択部２２］］
尾部選択部２２は、Head[k]を先頭制御対象物単位とし、S内の制御対象物単位のうち移動させても接続性が維持できる制御対象物単位のうちの１つをTailとして選択する（ステップＳ２２）。
【００５８】
具体的には、下記式（１）を満たすS内の制御対象物単位jをTailとして選択する。
【００５９】
δ（j）>δ（j_n）…(1)
ここで、δ（ｊ）は、制御対象物単位ｊの先頭制御対象物単位Headからの制御対象物構造内でのマンハッタン距離である。そして、j_nは、制御対象物単位jに隣接している制御対象物単位の番号である。全ての制御対象物単位j_nに対して不等式（１）が成立するならば、制御対象物単位ｊを制御対象物構造から取り払ったとしても制御対象物構造の接続性は維持できる。
【００６０】
［［移動部２３］］
移動部２３は、Head[k+1]をHead[k]の目的位置として、Head[k]からTailまでの制御対象物隊列をタネリング動作により移動させる（ステップＳ２３）。タネリング動作は、図７に示すものである。
【００６１】
［［判定部２４］］
判定部２４は、ｋが最後のインデックスであれば（Head[0]からHead[n_last]の全ての位置に制御対象物単位が存在している状態であれば）、第一判定部３を実行させ、そうでなければ先頭位置設定部２１に戻り、処理を繰り返す（ステップＳ２４）。つまり、目的位置系列中の全ての位置について移動部２３による移動処理を終えるまで先頭位置設定部２１から移動部２３までの処理を繰り返し、全て終了したら第一判定部３の処理に移行する。
【００６２】
このようにして、第一移動部２は、ステップＳ２１からステップＳ２４の処理により、目的位置系列の位置の中の制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる（ステップＳ２）。その際、第一移動部２は、制御対象物単位を移動させるときには、先頭の制御対象物単位及び尾部の制御対象物単位を選択し、先頭の制御対象物単位から尾部の制御対象物単位までの一連の制御対象物単位を先頭の制御対象物単位の動作を追従するように移動させる。
【００６３】
なお、各制御対象物単位が他の制御対象物単位と隣接することにより制御対象物単位が一塊の制御対象物構造を形成していることを制御対象物構造の接続性と言うとする。
【００６４】
目的位置系列として、図１５（Ａ）において太線で示した位置の系列が選択された場合には、移動部２３及び判定部２４の処理により、図１５（Ｃ）から（Ｅ）に示すように、制御対象物単位が移動される。
【００６５】
［第一判定部３］
第一判定部３は、common_prevを位置Head_lastの所属する共通部分番号とし、当該共通部分番号に対する変数Connected[common_prev]=1として、全ての共通部分が接続された状態（全てのiについてConnected[i]=1）となったか否かを判定する（ステップＳ３）。
【００６６】
まだ、接続された状態でない共通部分（Connected[i]=0なるi）があれば目的位置系列出力部１へ戻り、処理を繰り返す。全て接続された状態になっていれば（全てのiについてConnected[i]=1を満たすならば）、第二判定部４へ処理を移行する。
【００６７】
例えば、図１５（Ｅ）に示すように制御対象物単位が移動した状態において、第一判定部３の判定処理により、目的位置系列出力部１に戻り、目的位置系列出力部１において、図１５（Ｅ）のように、Head_first, Head_next,Head_lastが選択されたとする。このとき、目的位置系列は、図１５（Ｅ）において太線で示した位置の系列となる。その後、移動部２３及び判定部２４の処理により、図１５（Ｆ）から（Ｉ）に示すように、制御対象物単位が移動される。このようにして、目的位置系列出力部１、移動部２３及び判定部２４の処理が、接続された状態でない共通部分がなくなるまで繰り返し行われる。
【００６８】
［第二判定部４］
第二判定部４は、G内のまだ制御対象物単位が存在しない位置があるか否かを判定する（ステップＳ４）。G内のまだ制御対象物単位が存在しない位置があれば第二移動部５を実行させ、そうでなければ処理を終了する。
【００６９】
［第二移動部５］
第二移動部５は、G内のまだ制御対象物単位が存在せず、かつ制御対象物単位に接した位置を位置Dとして選択し、Dに接する制御対象物単位を先頭制御対象物単位Headとして、式（１）を使用してS内にある尾部制御対象物単位Tailを選択して、制御対象物単位Headの目標位置をDとしたタネリングを行う。その後、第二判定部４の処理に戻り、判定処理を行う。
【００７０】
このようにして、第二移動部５は、目標位置の集合に属する位置の中に制御対象物単位が位置していない位置がある場合には、その制御対象物単位が位置していない位置に、初期位置にある制御対象物単位を、制御対象物構造の接続性を維持しながら移動させる（ステップＳ５）。その際、第二移動部５は、制御対象物単位を移動させるときには、先頭の制御対象物単位及び尾部の制御対象物単位を選択し、先頭の制御対象物単位から尾部の制御対象物単位までの一連の制御対象物単位を先頭の制御対象物単位の動作を追従するように移動させる。
【００７１】
このような構成により、多数の制御対象物単位の存在を考慮しつつ、制御対象物単位同士が接したままの状態を維持しつつ任意の開始位置における隊列形成状態から、他の任意の目標位置における隊列形成状態へ、初期位置の集合と目標位置の集合の共通部分に非接続がある場合でも障害物のある環境にてホモジニアス隊列制御を行うことができる。
【００７２】
「制御対象物単位同士が接したままの状態を維持しつつ」とは、言い換えれば、
「制御対象物単位を構成する複数の制御対象物の中の制御対象物が、制御対象物単位を構成する複数の制御対象物の中の他の制御対象物に隣接するようにして」ということである。更に言い換えれば、「制御対象物単位を構成する二つの制御対象物単位のうち、一つずつを制御対象物単位の大きさ分の距離だけ交互に移動させることによって」ということである。
【００７３】
＜変形例等＞
上記の実施形態では、制御対象物単位としていわゆる８マスライディングキューブを用いたが、タネリングが可能であれば、８マスコンプレッシングタイプ、４マスライディングキューブ等の制御対象物単位を用いてもよい。また、タネリングが可能であれば、いわゆるせん断ロボット、伸縮ロボット以外のロボットを制御対象物単位として用いてもよい。
【００７４】
＜プログラム及び記録媒体＞
制御装置の各部における処理をコンピュータによって実現する場合、これらの装置の各部がが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各部の処理がコンピュータ上で実現される。
【００７５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７６】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【００７７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2019074997.tif 000003
【図２】
2019074997.tif 000004
【図３】
2019074997.tif 000005
【図４】
2019074997.tif 000006
【図５】
2019074997.tif 000007
【図６】
2019074997.tif 000008
【図７】
2019074997.tif 000009
【図８】
2019074997.tif 000010
【図９】
2019074997.tif 000011
【図１０】
2019074997.tif 000012
【図１１】
2019074997.tif 000013
【図１２】
2019074997.tif 000014
【図１３】
2019074997.tif 000015
【図１４】
2019074997.tif 000016
【図１５】
2019074997.tif 000017
【図１６】
2019074997.tif 000018
【図１７】
2019074997.tif 000019
【図１８】
2019074997.tif 000020