(57)【要約】【課題】隊列制御動作にかかる時間を短縮することができる制御技術を提供する。【解決手段】移動ロボットは、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４、返信位置距離計算命令転送部５、動作時刻告知命令送信部６、動作時刻告知命令転送部７、第一移動部８、移動開始命令送信部９、移動開始命令転送部１０、第二移動部１１、第三移動部１２、判定部１３、第四移動部１４、第五移動部１５、待ち命令送信部１６及び待ち命令転送部１７を例えば備えている。【選択図】図１６
2020035123.tif 000002
【特許請求の範囲】
【請求項１】
移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、上記所定の初期位置の集合と上記所定の目標位置の集合とは接しているとし、上記所定の初期位置の集合に含まれる位置であって上記所定の目標位置の集合に接している位置の１つを接続位置とし、上記移動ロボットは上記所定の初期位置から上記接続位置を通って上記所定の目標位置に移動するとして、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記接続位置にあるロボット単位j_rootである場合に、それぞれ所定の初期値に設定された、上記接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信部と、
上記位置距離計算命令を受信した場合に、上記位置距離計算命令に含まれる送信転送回数をインクリメントし、上記位置距離計算命令を受信した方向に応じて上記位置距離計算命令に含まれる相対位置を更新し、上記インクリメントした送信転送回数及び上記更新した相対位置を含む位置距離計算命令を、上記位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送部と、
上記位置距離計算命令を最初に受信した場合に、上記位置距離計算命令を送信してきたロボット単位に、上記インクリメントした送信転送回数及び上記更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信部と、
上記位置距離計算命令を最初に受信した場合に、上記位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶部と、
上記返信位置距離計算命令を受信した場合に、上記方向記憶部から読み込んだroot方向に上記受信した返信位置距離計算命令を転送する返信位置距離計算命令転送部と、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記ロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合に、上記返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、上記移動開始時刻を含む動作時刻告知命令を隣接するロボット単位に送信する動作時刻告知命令送信部と、
上記動作時刻告知命令を受信した場合に、上記動作時刻告知命令を隣接するロボット単位に一度だけ転送する動作時刻告知命令転送部と、
最初に移動を開始するロボット単位であり上記動作時刻告知命令を受信した場合に、上記接続位置に向けてロボットを移動させる第一移動部と、
移動開始後所定の時間が経過した場合に、次に移動するロボット単位宛ての移動開始命令を隣接するロボット単位に送信する移動開始命令送信部と、
上記移動開始命令を受信した場合に、上記移動開始命令を隣接するロボット単位に一度だけ転送する移動開始命令転送部と、
上記移動開始命令を受信した場合に、上記接続位置に向けてロボットを移動させる第二移動部と、
上記接続位置に到達した場合に、上記ロボット単位j_rootから自身のロボット単位の目標位置と、上記自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三移動部と、
隣接し移動しようとする位置に他のロボット単位があるかどうかを判定する判定部と、
隣接し移動しようとする位置に他のロボット単位があり、上記隣接し移動しようとする位置が自身のロボット単位の目標位置である場合には、自身のロボット単位を上記隣接し移動しようとする位置に移動させる第四移動部と、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記他のロボット単位である場合に、上記自身のロボット単位が上記隣接し移動しようとする位置に移動した後に、上記他のロボット単位を上記他のロボット単位の目標位置及びパスに従って移動させる第五移動部と、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記他のロボット単位である場合に、所定の待ち時間を含む待ち命令を隣接するロボット単位に送信する待ち命令送信部と、
上記待ち命令を受信した場合に、上記待ち命令に含まれる待ち時間だけ自身のロボット単位の移動を停止すると共に、上記待ち命令を隣接するロボット単位に一度だけ転送する待ち命令転送部と、
を含む、
移動ロボット。
【請求項２】
移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、上記所定の初期位置の集合と上記所定の目標位置の集合とは接しているとし、上記所定の初期位置の集合に含まれる位置であって上記所定の目標位置の集合に接している位置の１つを接続位置とし、上記移動ロボットは上記所定の初期位置から上記接続位置を通って上記所定の目標位置に移動するとして、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記接続位置にあるロボット単位j_rootである場合に、それぞれ所定の初期値に設定された、上記接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信部と、
上記位置距離計算命令を受信した場合に、上記位置距離計算命令に含まれる送信転送回数をインクリメントし、上記位置距離計算命令を受信した方向に応じて上記位置距離計算命令に含まれる相対位置を更新し、上記インクリメントした送信転送回数及び上記更新した相対位置を含む位置距離計算命令を、上記位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送部と、
上記位置距離計算命令を最初に受信した場合に、上記位置距離計算命令を送信してきたロボット単位に、上記インクリメントした送信転送回数及び上記更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信部と、
上記位置距離計算命令を最初に受信した場合に、上記位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶部と、
上記返信位置距離計算命令を受信した場合に、上記方向記憶部から読み込んだroot方向に上記受信した返信位置距離計算命令を転送する返信位置距離計算命令転送部と、
上記複数のロボット単位のそれぞれについて、当該ロボット単位が上記ロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合には、上記返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、k=1,…,Kとして、ロボット単位j_kの移動開始時刻になった場合に、上記ロボット単位j_kと、上記ロボット単位j_kからたどっていける場所にあり上記接続位置からのマンハッタン距離が最も大きい位置にあるロボット単位j_moveと、上記ロボット単位j_moveの位置から上記ロボット単位j_kの位置への経路情報とを含む動作開始命令を隣接するロボット単位に送信する動作開始命令送信部と、
上記動作開始命令を受信した場合に、上記動作開始命令を隣接するロボット単位に一度だけ転送する動作開始命令転送部と、
上記ロボット単位j_moveについて、上記動作開始命令を受信した場合には、上記ロボット単位j_moveを上記ロボット単位j_kの位置に移動させる第一移動部と、
上記ロボット単位j_kについて、上記ロボット単位j_moveが上記ロボット単位j_kの位置に移動した後に、上記ロボット単位j_kを上記接続位置に向けて移動させる第二移動部と、
上記接続位置に到達した場合に、上記ロボット単位j_rootから自身のロボット単位の目標位置と、上記自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三移動部と、
を含む、
移動ロボット。
【請求項３】
請求項１又は２の移動ロボットであって、
上記ロボット単位は三次元直交座標系で各軸方向に長さＭを有する立方体形状の空間内の部分構造であり、上記立方体形状の空間内のロボット単位に含まれるロボットの数と上記立方体形状の空間内のロボット単位以外の部分の数とが等しく、上記ロボット単位は各軸方向にＭ個のロボットが隣接する構造を含む、
移動ロボット。
【請求項４】
移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、上記所定の初期位置の集合と上記所定の目標位置の集合とは接しているとし、上記所定の初期位置の集合に含まれる位置であって上記所定の目標位置の集合に接している位置の１つを接続位置とし、上記移動ロボットは上記所定の初期位置から上記接続位置を通って上記所定の目標位置に移動するとして、
上記接続位置にあるロボット単位j_rootの位置距離計算命令送信部が、それぞれ所定の初期値に設定された、上記接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信ステップと、
上記位置距離計算命令を受信したロボット単位の位置距離計算命令転送部が、上記位置距離計算命令に含まれる送信転送回数をインクリメントし、上記位置距離計算命令を受信した方向に応じて上記位置距離計算命令に含まれる相対位置を更新し、上記インクリメントした送信転送回数及び上記更新した相対位置を含む位置距離計算命令を、上記位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送ステップと、
上記位置距離計算命令を最初に受信したロボット単位の返信位置距離計算命令送信部が、場合に、上記位置距離計算命令を送信してきたロボット単位に、上記インクリメントした送信転送回数及び上記更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信ステップと、
上記位置距離計算命令を最初に受信したロボット単位の方向記憶部が、上記位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶ステップと、
上記返信位置距離計算命令を受信したロボット単位の返信位置距離計算命令転送部が、上記方向記憶部から読み込んだroot方向に上記受信した返信位置距離計算命令を転送する返信位置距離計算命令転送ステップと、
上記ロボット単位j_rootの動作時刻告知命令送信部が、全てのロボットが送信した返信位置距離計算命令を受信した場合には、上記返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、上記移動開始時刻を含む動作時刻告知命令を隣接するロボット単位に送信する動作時刻告知命令送信ステップと、
上記動作時刻告知命令を受信したロボット単位の動作時刻告知命令転送部が、上記動作時刻告知命令を隣接するロボット単位に一度だけ転送する動作時刻告知命令転送ステップと、
最初に移動を開始するロボット単位の第一移動部が、上記動作時刻告知命令を受信した場合に、上記接続位置に向けてロボットを移動させる第一移動ステップと、
移動開始後所定の時間が経過したロボット単位の移動開始命令送信部が、次に移動するロボット単位宛ての移動開始命令を隣接するロボット単位に送信する移動開始命令送信ステップと、
上記移動開始命令を受信したロボット単位の移動開始命令転送部が、上記移動開始命令を隣接するロボット単位に一度だけ転送する移動開始命令転送ステップと、
上記移動開始命令を受信したロボット単位の第二移動部が、上記接続位置に向けてロボットを移動させる第二移動ステップと、
上記接続位置に到達したロボット単位の第三移動部が、上記ロボット単位j_rootから自身のロボット単位の目標位置と、上記自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三移動ステップと、
ロボット単位の判定部が、隣接し移動しようとする位置に他のロボット単位があるかどうかを判定する判定ステップと、
ロボット単位の第四移動部が、隣接し移動しようとする位置に他のロボット単位があり、上記隣接し移動しようとする位置が自身のロボット単位の目標位置である場合には、自身のロボット単位を上記隣接し移動しようとする位置に移動させる第四移動ステップと、
上記他のロボット単位であるロボット単位の第五移動部が、上記自身のロボット単位が上記隣接し移動しようとする位置に移動した後に、上記他のロボット単位を上記他のロボット単位の目標位置及びパスに従って移動させる第五移動ステップと、
上記他のロボット単位であるロボット単位の待ち命令送信部が、所定の待ち時間を含む待ち命令を隣接するロボット単位に送信する待ち命令送信ステップと、
上記待ち命令を受信したロボット単位の待ち命令転送部が、上記待ち命令に含まれる待ち時間だけ自身のロボット単位の移動を停止すると共に、上記待ち命令を隣接するロボット単位に一度だけ転送する待ち命令転送ステップと、
を含む、
移動ロボットの制御方法。
【請求項５】
移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、上記所定の初期位置の集合と上記所定の目標位置の集合とは接しているとし、上記所定の初期位置の集合に含まれる位置であって上記所定の目標位置の集合に接している位置の１つを接続位置とし、上記移動ロボットは上記所定の初期位置から上記接続位置を通って上記所定の目標位置に移動するとして、
上記接続位置にあるロボット単位j_rootの位置距離計算命令送信部が、それぞれ所定の初期値に設定された、上記接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信ステップと、
上記位置距離計算命令を受信したロボット単位の位置距離計算命令転送部が、上記位置距離計算命令に含まれる送信転送回数をインクリメントし、上記位置距離計算命令を受信した方向に応じて上記位置距離計算命令に含まれる相対位置を更新し、上記インクリメントした送信転送回数及び上記更新した相対位置を含む位置距離計算命令を、上記位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送ステップと、
上記位置距離計算命令を最初に受信したロボット単位の返信位置距離計算命令送信部が、上記位置距離計算命令を送信してきたロボット単位に、上記インクリメントした送信転送回数及び上記更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信ステップと、
上記位置距離計算命令を最初に受信したロボット単位の方向記憶部が、上記位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶ステップと、
上記返信位置距離計算命令を受信したロボット単位の返信位置距離計算命令転送部が、上記方向記憶部から読み込んだroot方向に上記受信した返信位置距離計算命令を転送する返信位置距離計算命令転送ステップと、
上記ロボット単位j_rootの動作開始命令送信部が、全てのロボットが送信した返信位置距離計算命令を受信した場合には、上記返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、k=1,…,Kとして、ロボット単位j_kの移動開始時刻になった場合に、上記ロボット単位j_kと、上記ロボット単位j_kからたどっていける場所にあり上記接続位置からのマンハッタン距離が最も大きい位置にあるロボット単位j_moveと、上記ロボット単位j_moveの位置から上記ロボット単位j_kの位置への経路情報とを含む動作開始命令を隣接するロボット単位に送信する動作開始命令送信ステップと、
上記動作開始命令を受信したロボット単位の動作開始命令転送部が、上記動作開始命令を隣接するロボット単位に一度だけ転送する動作開始命令転送ステップと、
上記ロボット単位j_moveの第一移動部が、上記動作開始命令を受信した場合には、上記ロボット単位j_moveを上記ロボット単位j_kの位置に移動させる第一移動ステップと、
上記ロボット単位j_kの第二移動部が、上記ロボット単位j_moveが上記ロボット単位j_kの位置に移動した後に、上記ロボット単位j_kを上記接続位置に向けて移動させる第二移動ステップと、
上記接続位置に到達したロボット単位の第三移動部が、上記ロボット単位j_rootから自身のロボット単位の目標位置と、上記自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三移動ステップと、
を含む、
移動ロボットの制御方法。
【請求項６】
請求項１から３の何れかの移動ロボットの各部としてコンピュータを機能させるためのコンピュータ読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のロボットの行動を制御する技術に関する。例えば、複数のロボットを、初期位置における隊列形成状態から協調して移動させ、障害物を回避させ、目標位置で隊列形成をさせるための各ロボットの行動計画を求めるロボット協調制御技術に関する。
【背景技術】
【０００２】
近年、多数の自律移動ロボットを効率的に制御にするための研究が活発に行われている。その任務内容は、人の入れない箇所の監視、物品の搬送などさまざまであるが、多数のロボットの協調動作による隊列形成を効率的に行わせるための技術が求められており盛んに研究が行われている。
【０００３】
特に、ロボットの隊列制御の中でも、ロボット同士が互いに接したままの状態で、アメーバのように全体で移動を行うという仮定の下でのロボット隊列制御においては、ロボット同士の相対的な位置関係から、各ロボットの絶対位置の決定が可能であるという利点と、付加的な位置計測用の装備を必要としないという利点があり、そのようなロボットの研究も行われている（例えば、非特許文献１，２参照。）。
【０００４】
非特許文献１は、全てのロボットが同じ性質を持つ（ホモジニアス）という前提の下で、任意の初期隊列形成状態から目的隊列形成状態へ変形する隊列制御を実現する方法が開示されている。ここでは、８つのロボットを１つの単位として移動させることで、従来よりも効率的な隊列制御を実現している。
【０００５】
非特許文献２では、各矩形ロボットが異なる性質を持つ(ヘテロジニアス)という前提の下で、任意の形状隊列から他の形状隊列へ変形する隊列制御の方法が開示されている。
【０００６】
このような、多数のロボットによる効率的な隊列形成を実現するには、それぞれのロボットの配置、動作順序などを事前に計画することが重要である。このような計画においては、当然ながら、複数のロボットが動作する実環境における障害物の存在や経路の形状なども十分に考慮しなければならない。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献２では、各ロボットが接した状態での動作を想定し、各ロボットが異なる特性（ヘテロジニアス）である、つまり、各ロボットの目標位置が特定されている場合の隊列制御を実現している。このような隊列制御は、例えば、カメラを搭載したロボット、車輪を搭載したロボット等の個々に異なる役割がある各ロボットをロボット隊列内の適切な位置に配置させつつ、隊列の形状を制御するといった運用に適している。
【０００９】
非特許文献１はホモジニアスを前提としており、隊列変形後の各ロボットの位置が保証されないため、ヘテロジニアスを前提とするような隊列形成の問題に適用することができない。
【００１０】
非特許文献２は、ヘテロジニアスを前提とする隊列形成を行うことができるが、隊列全体の形状の変形動作と、変形後のロボット位置入れ替えを別個のプロセスとして行わなければならない。つまり、まずロボットの位置は問わずに形状（隊列）を目的隊列に変形する前に、各ロボットの位置が正しい目標位置となるように各ロボットの位置の入れ替えを行うための別の隊列形態をとり、ロボットの位置の入れ替えを行うのである。そのロボット位置入れ替えの処理に非常に時間を要するため、全体として隊列制御にかかる時間が長いという問題がある。
【００１１】
このような現状に鑑みて、本発明は、隊列制御動作にかかる時間を短縮することができる制御装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
この発明の一態様による移動ロボットは、移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、所定の初期位置の集合と所定の目標位置の集合とは接しているとし、所定の初期位置の集合に含まれる位置であって所定の目標位置の集合に接している位置の１つを接続位置とし、移動ロボットは所定の初期位置から接続位置を通って所定の目標位置に移動するとして、複数のロボット単位のそれぞれについて、当該ロボット単位が接続位置にあるロボット単位j_rootである場合に、それぞれ所定の初期値に設定された、接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信部と、位置距離計算命令を受信した場合に、位置距離計算命令に含まれる送信転送回数をインクリメントし、位置距離計算命令を受信した方向に応じて位置距離計算命令に含まれる相対位置を更新し、インクリメントした送信転送回数及び更新した相対位置を含む位置距離計算命令を、位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送部と、位置距離計算命令を最初に受信した場合に、位置距離計算命令を送信してきたロボット単位に、インクリメントした送信転送回数及び更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信部と、位置距離計算命令を最初に受信した場合に、位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶部と、返信位置距離計算命令を受信した場合に、方向記憶部から読み込んだroot方向に受信した返信位置距離計算命令を転送する返信位置距離計算命令転送部と、複数のロボット単位のそれぞれについて、当該ロボット単位がロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合に、返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、移動開始時刻を含む動作時刻告知命令を隣接するロボット単位に送信する動作時刻告知命令送信部と、動作時刻告知命令を受信した場合に、動作時刻告知命令を隣接するロボット単位に一度だけ転送する動作時刻告知命令転送部と、最初に移動を開始するロボット単位であり動作時刻告知命令を受信した場合に、接続位置に向けてロボットを移動させる第一移動部と、移動開始後所定の時間が経過した場合に、次に移動するロボット単位宛ての移動開始命令を隣接するロボット単位に送信する移動開始命令送信部と、移動開始命令を受信した場合に、移動開始命令を隣接するロボット単位に一度だけ転送する移動開始命令転送部と、移動開始命令を受信した場合に、接続位置に向けてロボットを移動させる第二移動部と、接続位置に到達した場合に、ロボット単位j_rootから自身のロボット単位の目標位置と、自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三移動部と、隣接し移動しようとする位置���他のロボット単位があるかどうかを判定する判定部と、隣接し移動しようとする位置に他のロボット単位があり、隣接し移動しようとする位置が自身のロボット単位の目標位置である場合には、自身のロボット単位を隣接し移動しようとする位置に移動させる第四移動部と、複数のロボット単位のそれぞれについて、当該ロボット単位が他のロボット単位である場合に、自身のロボット単位が隣接し移動しようとする位置に移動した後に、他のロボット単位を他のロボット単位の目標位置及びパスに従って移動させる第五移動部と、複数のロボット単位のそれぞれについて、当該ロボット単位が他のロボット単位である場合に、所定の待ち時間を含む待ち命令を隣接するロボット単位に送信する待ち命令送信部と、待ち命令を受信した場合に、待ち命令に含まれる待ち時間だけ自身のロボット単位の移動を停止すると共に、待ち命令を隣接するロボット単位に一度だけ転送する待ち命令転送部と、を含む。
【００１３】
この発明の一態様による移動ロボットは、移動ロボットは複数のロボット単位で構成されているとし、各ロボット単位の周囲には他のロボット単位を構成するロボットが移動可能な空隙があり、各ロボット単位には所定の初期位置及び所定の目標位置が定められており、所定の初期位置の集合と所定の目標位置の集合とは接しているとし、所定の初期位置の集合に含まれる位置であって所定の目標位置の集合に接している位置の１つを接続位置とし、移動ロボットは所定の初期位置から接続位置を通って所定の目標位置に移動するとして、複数のロボット単位のそれぞれについて、当該ロボット単位が接続位置にあるロボット単位j_rootである場合に、それぞれ所定の初期値に設定された、接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する位置距離計算命令送信部と、位置距離計算命令を受信した場合に、位置距離計算命令に含まれる送信転送回数をインクリメントし、位置距離計算命令を受信した方向に応じて位置距離計算命令に含まれる相対位置を更新し、インクリメントした送信転送回数及び更新した相対位置を含む位置距離計算命令を、位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する位置距離計算命令転送部と、位置距離計算命令を最初に受信した場合に、位置距離計算命令を送信してきたロボット単位に、インクリメントした送信転送回数及び更新した相対位置を含む返信位置距離計算命令を送信する返信位置距離計算命令送信部と、位置距離計算命令を最初に受信した場合に、位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する方向記憶部と、返信位置距離計算命令を受信した場合に、方向記憶部から読み込んだroot方向に受信した返信位置距離計算命令を転送する返信位置距離計算命令転送部と、複数のロボット単位のそれぞれについて、当該ロボット単位がロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合には、返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、k=1,…,Kとして、ロボット単位j_kの移動開始時刻になった場合に、ロボット単位j_kと、ロボット単位j_kからたどっていける場所にあり接続位置からのマンハッタン距離が最も大きい位置にあるロボット単位j_moveと、ロボット単位j_moveの位置からロボット単位j_kの位置への経路情報とを含む動作開始命令を隣接するロボット単位に送信する動作開始命令送信部と、動作開始命令を受信した場合に、動作開始命令を隣接するロボット単位に一度だけ転送する動作開始命令転送部と、ロボット単位j_moveについて、動作開始命令を受信した場合には、ロボット単位j_moveをロボット単位j_kの位置に移動させる第一移動部と、ロボット単位j_kについて、ロボット単位j_moveがロボット単位j_kの位置に移動した後に、ロボット単位j_kを接続位置に向けて移動させる第二移動部と、接続位置に到達した場合に、ロボット単位j_rootから自身のロボット単位の目標位置と、自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる第三���動部と、を含む。
【発明の効果】
【００１４】
本発明によれば、隊列制御動作にかかる時間を短縮することができる。
【図面の簡単な説明】
【００１５】
【図１】ロボットの移動を説明するための図。
【図２】ロボットの初期位置及び目標位置を説明するための図。
【図３】ボイドの移動の様子を説明するための図。
【図４】ロボット単位を説明するための図。
【図５】ロボット単位の移動を説明するための図。
【図６】ロボット構造の連続性を維持するための制御を説明するための図。
【図７】ロボット単位の移動を説明するための図。
【図８】ロボット単位の移動を説明するための図。
【図９】ロボット単位の移動を説明するための図。
【図１０】ロボット単位の移動を説明するための図。
【図１１】ロボット単位の移動を説明するための図。
【図１２】ロボット単位の移動を説明するための図。
【図１３】ロボット単位の移動を説明するための図。
【図１４】ロボット単位の移動を説明するための図。
【図１５】ロボット単位の例を説明するための図。
【図１６】第一実施形態の制御装置を説明するためのブロック図。
【図１７】第一実施形態の制御方法を説明するための流れ図。
【図１８】第二実施形態の制御装置を説明するためのブロック図。
【図１９】第二実施形態の制御方法を説明するための流れ図。
【図２０】第三実施形態の制御装置を説明するためのブロック図。
【図２１】第三実施形態の制御方法を説明するための流れ図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００１７】
＜理論的背景＞
まず、行動制御システム及び方法の理論的背景について説明する。
【００１８】
［問題設定］
任意の隊列形成を初期隊列形成状態として、ロボット同士が接したままの状態を維持しつつ目的とする任意の隊列形成状態である目的隊列形成状態への隊列を移動させる隊列制御を、多数のロボットが協調して行う任務を、例えば図１に例示するような、互いに接する面同士をスライドさせて移動していくことが可能な立方体型のロボットの制御を想定して実現する。この隊列制御は、図２に示すように、壁で区切られた部屋（ただし図中、壁を省略する）において、初期位置における隊列から目標位置における隊列への変形を、複数のロボットの移動によって実現するものである。
【００１９】
ロボットについては、例えば図１に示すように、ロボットの周囲縦横高さ方向（以下「上下左右前後方向」ともいう）６マスのうち１つに他のロボットが存在している（１つの面を他ロボットと共有している）状態を維持しながら移動をするものとする。この手法では１つのロボット自身が、一個のロボットのサイズ分の距離を移動することで、一回の動作の移動量を正確に測ることができるというメリットがある。また、１つの面を共有する隣り合うロボットとの相対的な位置を計測しあうことで、ロボットの群れ全体の中での各ロボットの位置も容易に知ることができる。このため、ロボットの移動量の誤差によって、隊列が崩れるといった問題を起こしにくく、また、各ロボットの位置を把握するために付加的な位置計測用の装備を備えずとも位置の把握が可能である。また、複数のロボットを連結したように、同時に複数のロボットを移動させていくことが可能である。なお、ロボットは、隣の位置に他のロボットが存在しているか否か、障害物があるか否か、そして、自身が目標位置上にいるかどうかを知ることができるものとする。
【００２０】
任務を行うロボットは、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が目標位置の集合G内へ入ろうとしている時点で、ロボット単位jの目標位置が、すでに別のロボット単位j’によって占有されている場合であり、ロボット単位j’の本来の目標位置が、空隙のままである場合である（図６（Ａ））。この場合、ロボット単位jをロボット単位j’の位置に移動させ、ロボット単位j’を追い出し、さらにロボット単位j’を本来の位置に移動させなければならないが、図６に示すように、ロボット単位jに属する４つのロボットを、ロボット単位j'に隣接するロボット単位j_nのうちの一つであるロボット単位j_k(k=1,…,n)の中の周囲に存在する４つの空隙位置に移動させ（図６（Ｂ））、続いて、ロボット単位j'に所属するロボットとロボット単位jに所属するロボットの位置を入れ替える（図６（Ｃ））。その後、ロボット単位j’に所属するロボットをロボット単位j''の周りにある空隙位置に移動させ(図６（Ｄ）)、その後、ロボット単位j'のロボットを目標位置に移動させる。
【００４２】
以上に述べた制御を、全てのロボット単位が目標位置につくまで繰り返し行えば、ヘテロ隊列制御が完了する。この制御において、従来必要であったロボット同士の位置入れ替え作業は、上記のロボット単位j'に所属するロボットとロボット単位jに所属するロボットの位置を入れ替える作業において代替されている。以上の手法によれば、全てのロボット単位について、初期位置から目標位置に至るまでに必要な移動量は、入れ替えがなかった場合の移動量と同程度であり、かつそのほかの移動は必要としない。すなわち、本手法により、隊列の全体変形とロボット位置入れ替えが同時に行われている。
【００４３】
このように、全体の形状の変形動作と変形後のロボット位置入れ替えを別個のプロセスとせずに同時に行うことで、隊列制御動作にかかる時間を短縮することができる。
【００４４】
ここで、従来手法では、初期位置Sにある各ロボット単位を目標位置への移動を開始する時刻については、１つ前に目標位置への移動を開始したロボット単位が、目標位置にたどり着いた時刻の後にする手法（ロボット単位が１つずつ移動する手法）を採用していたが、ロボット構造内の４マスロボット単位のもたらす空隙をフルに使用すれば、複数のロボット単位を同時に目標位置まで移動させることも可能である。ここで、移動を開始しようとしているロボット単位が、１つ前に移動を開始したロボット単位の開始時刻から、一定時間内に移動を開始することができれば、全体の変形に要する時間を、ロボット単位数の一乗に比例するものにすることができる。
【００４５】
そのための手法を述べる。ここで、初期位置Sと目標位置Gは接しているものとし、目標位置Gに接している初期位置S内のロボット単位の位置を接続位置Gate_S（X_Gate, Y_Gate, Z_Gate）とし、全てのロボット単位は、接続位置Gate_Sを経由して、目標位置G内に入っていくものとする。ロボット単位が移動を開始する順番としては、接続位置Gate_Sからのマンハッタン距離δ(j)の大きいものから優先的に移動を開始させるものとする。さらに、ロボット単位が位置の入れ替えを行うときは、位置の入れ替えを行うロボット単位の後続のロボット単位はすべて２時間ステップ以上だけ、動作を停止する。
【００４６】
また、移動を開始しようとしている制御対象物単位のδ値をδ(j)とし、１つ前に移動を開始した制御対象物単位の初期位置のδ値をδ(j-1)とし、αを２以上の正の整数とし、tw=δ(j-1)-δ(j)+αとして、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、tw時間ステップ後に移動を開始する。すなわち、移動を開始しようとしている制御対象物単位が、１つ前に移動を開始した制御対象物単位の初期位置とδ値が同じ場合は、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、α時間ステップ後に移動を開始する。移動を開始しようとしている制御対象物単位のδ値が、１つ前に移動を開始した制御対象物単位の初期位置のδ値よりも１だけ小さい場合は、移動を開始しようとしている制御対象物単位は、１つ前に移動を開始した制御対象物単位の移動開始時刻から、α＋１時間ステップ後に移動を開始する。例えばα＝２とすることで、移動を行う各制御対象物単位は、互いにちょうど１つ分の制御対象物単位分の距離を開けつつ、同時に移動をすることになる。
【００４７】
以上の方法を、分散制御方式でのアルゴリズムで実現する移動ロボット及び移動ロボットの制御方法の一実施形態について以下説明する。
【００４８】
＜第一実施形態＞
以下、第一実施形態の移動ロボット及び移動ロボットの制御方法について説明する。
【００４９】
移動ロボットは、図１６に示すように、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４、返信位置距離計算命令転送部５、動作時刻告知命令送信部６、動作時刻告知命令転送部７、第一移動部８、移動開始命令送信部９、移動開始命令転送部１０、第二移動部１１、第三移動部１２、判定部１３、第四移動部１４、第五移動部１５、待ち命令送信部１６及び待ち命令転送部１７を例えば備えている。
【００５０】
移動ロボットの制御方法は、移動ロボットの各部が、例えば図１７及び以下に説明するステップＳ１からステップＳ１７の処理を行うことにより実現される。
【００５１】
ステップＳ１からステップＳ５の処理は、初期位置Sの隊列構造を把握するための処理である。ステップＳ６からステップＳ１７の処理は、ロボット単位を移動するための処理である。
【００５２】
まず、接続位置Gate_Sにあるロボット単位j_rootにユーザーから変形開始命令が送信される。変形開始命令には、各ロボット単位の目標位置Gについての情報である隊列形態情報が含まれるとする。
【００５３】
［位置距離計算命令送信部１］
変形開始命令を受信したロボットが接続位置Gate_Sにあるロボット単位j_rootである場合には、位置距離計算命令送信部１は、それぞれ所定の初期値に設定された、接続位置からの相対位置と位置距離計算命令の送信転送回数とを含む位置距離計算命令を隣接するロボット単位に送信する（ステップＳ１）。
【００５４】
以下、位置距離計算命令を位置距離計算命令MANHATTAN_COM、相対位置を相対位置（Xr,Yr,Zr）、送信転送回数を送信転送回数N_manhattanと表記する場合もある。
【００５５】
例えば、相対位置（Xr,Yr,Zr）の初期値は(0,0,0)であり、送信転送回数N_manhattanの初期値は0である。
【００５６】
［位置距離計算命令転送部２］
ロボット単位が、位置距離計算命令を受信した場合に、位置距離計算命令転送部２は、位置距離計算命令に含まれる送信転送回数をインクリメントし、位置距離計算命令を受信した方向に応じて位置距離計算命令に含まれる相対位置を更新し、インクリメントした送信転送回数及び更新した相対位置を含む位置距離計算命令を、位置距離計算命令を送信してきたロボット単位以外の、隣接するロボット単位に一度だけ転送する（ステップＳ２）。
【００５７】
なお、位置距離計算命令転送部２は、位置距離計算命令MANHATTAN_COMを自分に送信してきたロボット単位には転送をしない。これにより、位置距離計算命令MANHATTAN_COMが、ロボット構造内で何度も無限に送受信されることを防ぐことができる。
【００５８】
［返信位置距離計算命令送信部３］
ロボット単位が、位置距離計算命令を最初に受信した場合に、返信位置距離計算命令送信部３は、位置距離計算命令を送信してきたロボット単位に、インクリメントした送信転送回数及び更新した相対位置を含む返信位置距離計算命令を送信する（ステップＳ３）。
【００５９】
以下、返信位置距離計算命令を返信位置距離計算命令RETURN_MANHATTAN_COMと表記する場合もある。
【００６０】
最初に位置距離計算命令MANHATTAN_COMを受信した際の送信転送回数N_manhattanの値が、このロボット単位のロボット単位j_rootからのマンハッタン距離となる。
【００６１】
［方向記憶部４］
ロボット単位が、位置距離計算命令を最初に受信した場合に、方向記憶部４は、位置距離計算命令を送信してきたロボット単位の方向をroot方向として記憶する（ステップＳ４）。
【００６２】
以後、各ロボットは、何か情報をロボット単位j_rootに対して送るときは、各自rootの方向に送信する。
【００６３】
［返信位置距離計算命令転送部５］
ロボット単位が、返信位置距離計算命令を受信した場合に、返信位置距離計算命令転送部５は、方向記憶部４から読み込んだroot方向に受信した返信位置距離計算命令を転送する（ステップＳ５）。
【００６４】
各返信位置距離計算命令を受信した各ロボットがステップＳ５の処理を行うことにより、各返信位置距離計算命令は最終的にロボット単位j_rootに到達する。
【００６５】
［動作時刻告知命令送信部６］
ロボット単位がロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合には、動作時刻告知命令送信部６は、返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定し、移動開始時刻を含む動作時刻告知命令を隣接するロボット単位に送信する（ステップＳ６）。
【００６６】
例えば、動作時刻告知命令送信部６は、各ロボット単位のマンハッタン距離を把握し、マンハッタン距離の大きい順に、各ロボット単位の目標位置Gへの移動動作開始の順番と、各ロボット単位間の移動開始予定時刻を決定する。
【００６７】
以下、動作時刻告知命令を動作時刻告知命令START_TIME_COMと表記する場合もある。
【００６８】
動作時刻告知命令START_TIME_COMは、各ロボット単位の移動開始時刻についての情報を含んでいる。
【００６９】
［動作時刻告知命令転送部７］
ロボット単位が、動作時刻告知命令を受信した場合に、動作時刻告知命令転送部７は、動作時刻告知命令を隣接するロボット単位に一度だけ転送する（ステップＳ７）。
【００７０】
以下、動作時刻告知命令を動作時刻告知命令START_TIME_COMと表記する場合もある。
【００７１】
動作時刻告知命令START_TIME_COMは、各ロボット単位の移動開始時刻についての情報を含んでいる。
【００７２】
このように、動作時刻告知命令START_TIME_COMは、位置距離計算命令MANHATTAN_COMと同様に各ロボット単位に伝播されていく。
【００７３】
［第一移動部８］
ロボット単位が、最初に移動を開始するロボット単位であり、動作時刻告知命令を受信した場合に、第一移動部８は、接続位置に向けてロボットを移動させる（ステップＳ８）。
【００７４】
このようにして、動作時刻告知命令START_TIME_COMを受信したロボット単位のうち、最初に移動開始するロボット単位は、動作時刻告知命令START_TIME_COMを受信後に接続位置Gate_Sを通る目標位置Gへの移動動作を開始する。この際、最初に移動を開始するロボット単位j_1は、全てのロボット単位の中で最後に命令START_TIME_COMを受信することになるため、この方法で他のロボット単位が命令START_TIME_COMを受信漏れすることはない。
【００７５】
なお、移動を開始したロボット単位j_1は、最初に図７及び図８に示す動作でroot方向に移動する。以後は、ロボット単位j_1は、自分とともに８マスロボット単位をなすロボット単位にrootの方向を尋ねる命令ASK_TO_ROOT_COMを送信し、それに対する返信命令RETURN_TO_ROOTによって、root方向を知る。そして、root方向に移動する。この際、図９及び図１０の動作が使用される。以後、ロボット単位j_1はロボット単位j_rootの位置（接続位置Gate_S）にたどり着くまでこれを繰り返す。
【００７６】
［移動開始命令送信部９］
ロボット単位の移動開始後所定の時間が経過した場合に、移動開始命令送信部９は、次に移動するロボット単位宛ての移動開始命令を隣接するロボット単位に送信する（ステップＳ９）。
【００７７】
以下、移動開始命令を移動開始命令MOVE_STRAT_COMと表記する場合もある。
【００７８】
例えば、ロボット単位j_1は、移動開始後所定の時間（次のロボット単位の移動開始時刻までの時間差）がたったら、次に接続位置Gate_Sを通る目標位置Gへの移動を開始する予定のロボット単位j_2に向けて、移動開始命令MOVE_STRAT_COMを送信する。
【００７９】
［移動開始命令転送部１０］
ロボット単位が、移動開始命令を受信した場合に、移動開始命令転送部１０は、移動開始命令を隣接するロボット単位に一度だけ転送する（ステップＳ１０）。
【００８０】
移動開始命令MOVE_START_COMは、移動開始命令MANHATTAN_COMと同様に各ロボット単位に伝播されていく。
【００８１】
［第二移動部１１］
ロボット単位が、移動開始命令を受信した場合に、第二移動部１１は、接続位置に向けてロボットを移動させる（ステップＳ１１）。
【００８２】
例えば、移動開始命令MOVE_START_COMを受信したロボット単位j_2は、接続位置Gate_Sを通る目標位置Gへの移動を開始する。以降、またロボット単位j_2は、移動開始後所定の時間（次のロボット単位の移動開始時刻までの時間差）がたったら、次に接続位置Gate_Sを通る目標位置Gへの移動を開始する予定のロボット単位j_3に向けて、移動開始命令MOVE_STRAT_COMを送信する。
【００８３】
初期位置Sにある全てのロボット単位が、接続位置Gate_Sを通る目標位置Gへの移動を開始するまで、ステップＳ９からステップＳ１２の処理が繰り返し行われる。
【００８４】
なお、移動を開始した各ロボット単位j_k(k=1,2,3,,,p/4)は、例えば、最初に図７及び図８に示す動作でroot方向に移動する。以後は、各ロボット単位は、例えば、自分とともに８マスロボット単位をなすロボット単位にrootの方向を尋ねる命令ASK_TO_ROOT_COMを送信し、それに対する返信命令RETURN_TO_ROOTによって、root方向を知る。そして、root方向に移動する。この際、図９及び図１０の動作が使用される。以後、ロボット単位j_kはロボット単位j_rootの位置（接続位置Gate_S）にたどり着くまでこれを繰り返す。
【００８５】
［第三移動部１２］
ロボット単位が、接続位置に到達した場合に、第三移動部１２は、ロボット単位j_rootから自身のロボット単位の目標位置と、自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる（ステップＳ１２）。
【００８６】
例えば、接続位置Gate_Sにたどり着いた各ロボット単位j_kの第三移動部１２は、ロボット単位j_rootに対し、自身のG内での目標位置とそれに至る最適パス（そこに至るG内のロボット単位位置が全て埋まっていて通過可能であるという前提の）の情報を要求する目標位置パス取得命令REQUEST_PATH_TO_GOAL_COMを送信し、それに対するロボット単位j_rootからの返信目標位置パス取得命令RETURN_PATH_TO_GOAL_COMを受信後、受信したパス情報に従い、自身のG内目標位置への移動を開始する。
【００８７】
［判定部１３］
判定部１３は、隣接し移動しようとする位置に他のロボット単位があるかどうかを判定する（ステップＳ１３）。
【００８８】
例えば、各自のG内目標位置への移動を開始したロボット単位j_kは、まず自身と８マスロボット単位をなすロボット単位j_k’に対し、今からロボット単位j_kが移動しようとする方向に、すでに他のロボット単位があるかどうかを尋ねる隣接ロボット単位確認命令ASK_TARGET_EXIST_COMを送信する。
【００８９】
この場合、ロボット単位j_k’は、ロボット単位j_kの移動しようとする方向での隣接ロボット単位の有無を返信隣接ロボット単位確認命令RETURN_TARGET_EXIST_COMにてロボット単位j_kに返信する。
【００９０】
これにより、ロボット単位j_kの判定部１３は、隣接し移動しようとする位置に他のロボット単位があるかどうかを判定することができる。
【００９１】
隣接ロボット単位確認命令RETURN_TARGET_EXIST_COMを受信したロボット単位j_kは、今からロボット単位j_kが移動しようとする方向に、すでに他のロボット単位がある場合で、これから移動しようとしている位置が自身の目標位置ではない場合は、例えば図９又は図１０の動作で移動を行う。
【００９２】
また、隣接ロボット単位確認命令RETURN_TARGET_EXIST_COMを受信したロボット単位j_kは、今からロボット単位j_kが移動しようとする方向に、すでに他のロボット単位がない場合は、図１３又は図１４に示す動作で移動を行う。
【００９３】
［第四移動部１４］
隣接し移動しようとする位置に他のロボット単位があり、隣接し移動しようとする位置が自身のロボット単位の目標位置である場合には、第四移動部１４は、自身のロボット単位を隣接し移動しようとする位置に移動させる（ステップＳ１４）。
【００９４】
例えば、今からロボット単位j_kが移動しようとする方向に、すでに他のロボット単位がある場合で、これから移動しようとしている位置が自身の目標位置である場合は、ロボット単位j_kの第四移動部１４は、自身と８マスロボット単位をなすロボット単位j_k’に対し、今からロボット単位j_kが移動しようとする方向にすでにあるロボット単位に隣接するロボット単位の有無についての情報を尋ねる隣接ロボット単位確認命令ASK_GOAL_NEIGHBOR_COMを送信する。ロボット単位j_k’は、ロボット単位j_kの目標位置にあるロボット単位に対し、隣接ロボット単位確認命令ASK_GOAL_NEIGHBOR_COMを転送し、それを受信したロボット単位j_kの目標位置にあるロボット単位は、自身に隣接するロボット単位の有無についての情報を返信する返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを送信する。返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMは、ロボット単位j_k’を経由し、ロボット単位j_kまで転送される。
【００９５】
返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを受信したロボット単位j_kの第四移動部１４は、自身の目標位置にa=3,4,6の方向で隣接するロボット単位がある場合は、その隣接するロボット単位の位置に移動し、移動先の位置から入れ替え動作（図１１又は図１２）を使用して、目標位置へ移動する。返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを受信したロボット単位j_kの第四移動部１４は、自身の目標位置にa=3,4,6の方向で隣接するロボット単位がなく、かつ自身の目標位置にa=1,2,5の方向で隣接するロボット単位がある場合は、その隣接するロボット単位の位置に移動し、移動先の位置から入れ替え動作（図１２）を使用して目標位置へ移動する。
【００９６】
例えば、このようにして、第四移動部１４は、自身のロボット単位を隣接し移動しようとする位置に移動させる。
【００９７】
［第五移動部１５］
ロボット単位が、ロボット単位j_kが移動しようとする位置にある他のロボット単位である場合には、第五移動部１５は、入れ替え動作によってロボット単位j_kが移動しようとする位置に移動した後に、他のロボット単位を他のロボット単位の目標位置及びパスに従って移動させる（ステップＳ１５）。
【００９８】
すなわち、ロボット単位j_kによって入れ替えられた他のロボット単位は、以降、自身の目標位置への移動を再開する。
【００９９】
［待ち命令送信部１６］
ロボット単位が、他のロボット単位である場合には、待ち命令送信部１６は、所定の待ち時間を含む待ち命令を隣接するロボット単位に送信する（ステップＳ１６）。
【０１００】
例えば、ロボット単位j_kは、隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを受信した後に、後続の移動中のロボット単位に対し、待ち命令WAIT_COMを発信する。
【０１０１】
以下、待ち命令を待ち命令WAIT_COMと表記する場合もある。
【０１０２】
所定の待ち時間は、例えば、ロボット単位j_kが、図１１又は図１２に示す動作により自身の目標位置に隣接する位置から自身の目標位置に移動するために必要な時間＋βである。βは０以上の所定の時間である。
【０１０３】
［待ち命令転送部１７］
ロボット単位が、待ち命令を受信した場合に、待ち命令転送部１７は、待ち命令に含まれる待ち時間だけ自身のロボット単位の移動を停止する共に、待ち命令を隣接するロボット単位に一度だけ転送する（ステップＳ１７）。
【０１０４】
すなわち、待ち命令WAIT_COMを受信した移動中の各ロボット単位は、以降、命令により指定された時間だけ動作を停止する。また、待ち命令WAIT_COMは、命令MANHATTAN_COMのときと同様に各ロボット単位に伝播されていく。
【０１０５】
このように、全体の形状の変形動作と変形後のロボット位置入れ替えを別個のプロセスとせずに同時に行うことで、隊列制御動作にかかる時間を短縮することができる。
【０１０６】
＜第二実施形態＞
以下、第二実施形態の移動ロボット及び移動ロボットの制御方法について説明する。
【０１０７】
第一実施形態においては、ロボット単位位置の入れ替え動作は、目標位置G内において行っていたが、初期位置S内において行うことも可能である。
【０１０８】
この場合は、移動中のロボット単位が、接続位置Gate_Sを通過して目標位置Gに入る順番が、接続位置Gate_Sからの各ロボット単位の目標位置のマンハッタン距離の小さい順になっていなければならない。しかし、ロボット単位jが移動を開始する際には、ロボット単位j_rootからのロボットjのマンハッタン距離が現時点でロボット単位jに隣接する初期位置S内ロボット単位のそれよりの大きいという条件を満たさなければならない。
【０１０９】
ここで、ある時点で、ロボット単位j_kが次に接続位置Gate_Sを通過すべきロボット単位であるとする。この際、ロボット単位j_kからマンハッタン距離が大きくなるように隣接するロボット単位をたどっていき、その時点でS内で最終的にたどり着く位置にあるロボット単位をj_moveとし、まずロボット単位j_moveをロボット単位j_kの位置に移動させる。その後、ロボット単位j_moveとロボット単位j_kを図１１又は図１２の動作によって入れ替えを行い、その後、ロボット単位j_kを接続位置Gate_Sまで移動させる。それ以降は、第一実施形態の場合と同様に目標位置G内でのロボット単位j_kの移動が行われる。各ロボット単位の移動開始時間の設定は第一実施形態の場合と同様である。
【０１１０】
以上の方法を、分散制御方式でのアルゴリズムで実現する移動ロボット及び移動ロボットの制御方法の第二実施形態について以下説明する。
以上のロボット動作を、各ロボット単位内に実装された計算機と、隣接している各ロボット同士での通信を利用して実現するための分散型アルゴリズムにより実現する。
【０１１１】
移動ロボットは、図１８に示すように、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４、返信位置距離計算命令転送部５、動作開始命令送信部１８、動作開始命令転送部１９、第一移動部２０、第二移動部２１及び第三移動部２２を例えば備えている。
【０１１２】
移動ロボットの制御方法は、移動ロボットの各部が、例えば図１９及び以下に説明するステップＳ１からステップＳ５及びステップＳ１８からステップＳ２２の処理を行うことにより実現される。
【０１１３】
ステップＳ１からステップＳ５の処理は、初期位置Sの隊列構造を把握するための処理である。ステップＳ１８からステップＳ２２処理は、ロボット単位を移動するための処理である。
【０１１４】
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
【０１１５】
まず、第一実施形態と同様にして、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４及び返信位置距離計算命令転送部５によるステップＳ１からステップＳ５の処理が行われる。
【０１１６】
［動作開始命令送信部１８］
ロボット単位が、ロボット単位j_rootであり、全てのロボットが送信した返信位置距離計算命令を受信した場合には、動作開始命令送信部１８は、返信位置距離計算命令に含まれる相対位置に基づく各ロボット単位の位置に基づいて、各ロボット単位の移動開始時刻を決定する。G内目標位置のGate_Sからのマンハッタン距離の小さいものからk=1,…,Kとして、ｋの小さい順番にG内に入っていくロボット単位j_kを決定する。ロボット単位j_kからたどっていける場所にあり接続位置からのマンハッタン距離が最も大きい位置にあるロボット単位j_moveを選択し、ロボット単位j_moveのGate_Sからのマンハッタン距離によってロボット単位j_moveの移動開始時刻を決定する、ロボット単位j_moveの位置と、ロボット単位j_moveの位置からロボット単位j_kの位置への経路情報とを含む動作開始命令を隣接するロボット単位に送信する（ステップＳ１８）。
【０１１７】
第一実施形態の動作時刻告知命令送信部６とは異なり、動作開始命令送信部１８は、先に述べた初期位置S内でのロボット位置入れ替えを考慮して、ロボット単位j_rootでのロボット移動開始時刻の設定を行う。
【０１１８】
例えば、最初の動作開始命令START_MOVE_COMは、最初にGate_Sを通過すべきロボット単位j_1と、ロボット単位j_1からマンハッタン距離を大きくする方向にたどっていける場所にあり最遠のロボット単位j_moveと、ロボット単位j_moveからロボット単位j_1への経路情報を含んでいる。
【０１１９】
ロボット単位j_rootの動作開始命令送信部１８は、最初の動作開始命令START_MOVE_COMの送信後、所定時間(ロボット単位j_moveのGate_Sからのマンハッタン距離δにより決まる移動開始時間間隔＋入れ替え用の待ち時間)がたった後、２回目の動作開始命令START_MOVE_COMを送信する。２回目の動作開始命令START_MOVE_COMは、２回目に接続位置Gate_Sを通過すべきロボット単位j_2と、ロボット単位j_2からマンハッタン距離を大きくする方向にたどっていける場所にあり最遠のロボット単位j_moveと、ロボット単位j_moveからロボット単位j_2への経路情報を含んでいる。
【０１２０】
このようにして、動作開始命令送信部１８は、各ロボット単位j_k(k=1,…,K)に対応する動作開始命令START_MOVE_COMを所定時間間隔で送信する。
【０１２１】
［動作開始命令転送部１９］
ロボット単位が、動作開始命令を受信した場合に、動作開始命令転送部１９は、動作開始命令を隣接するロボット単位に一度だけ転送する（ステップＳ１９）。
【０１２２】
これにより、動作開始命令START_MOVE_COMは、位置距離計算命令MANHATTAN_COMと同様に各ロボット単位に伝播されていく。
【０１２３】
［第一移動部２０］
ロボット単位が、ロボット単位j_moveであり、動作開始命令を受信した場合には、第一移動部２０は、ロボット単位j_moveをロボット単位j_kの位置に移動させる（ステップＳ２０）。
【０１２４】
例えば、最初の動作開始命令START_MOVE_COMを受信したロボット単位j_moveの第一移動部２０は、ロボット単位j_moveをロボット単位j_1の位置に移動させる。
【０１２５】
ロボット単位j_moveとロボット単位j_kの位置の入れ替え動作の例は、以下の通りである。ロボット単位j_moveが自身と入れ替えを行うロボット単位j_kとの８マスロボット単位をなす位置にたどり着いたら、ロボット単位j_moveの第一移動部２０は、ロボット単位j_kに対し、ロボット単位j_kに隣接するロボット単位の有無についての情報を尋ねる隣接ロボット単位確認命令ASK_GOAL_NEIGHBOR_COMを送信する。ロボット単位j_kは、自身に隣接するロボット単位の有無についての情報を返信する返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを返信する。
【０１２６】
返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを受信したロボット単位j_moveの第一移動部２０は、ロボット単位j_kにa=3,4,6の方向で隣接するロボット単位がある場合は、その隣接するロボット単位の位置移動し、移動先の位置から入れ替え動作（図１１）を使用して、ロボット単位j_kの位置へ移動する。返信隣接ロボット単位確認命令RETURN_GOAL_NEIGHBOR_COMを受信したロボット単位j_moveの第一移動部２０は、ロボット単位j_kにa=3,4,6の方向で隣接するロボット単位がなく、かつロボット単位j_kにa=1,2,5の方向で隣接するロボット単位がある場合は、その隣接するロボット単位の位置に移動し、移動先の位置から入れ替え動作（図１２）を使用して、ロボット単位j_kの位置へ移動する。
【０１２７】
［第二移動部２１］
ロボット単位が、ロボット単位j_kである場合に、第二移動部２１は、入れ替えによってロボット単位j_moveがロボット単位j_kの位置に移動した後に、ロボット単位j_kを接続位置に向けて移動させる（ステップＳ２１）。
【０１２８】
これにより、例えば、ロボット単位j_moveは、ロボット単位j_1の位置まで移動したら、ロボット単位j_1との入れ替えを行い、入れ替え後のロボット単位j_1は、接続位置Gate_Sへの移動を開始する。
【０１２９】
なお、移動を開始した各ロボット単位j_k(k=1,2,3,…,p/4)は、例えば、最初に図９又は図１０に示す動作でroot方向に移動する。以後は、各ロボット単位は、例えば、自分とともに８マスロボット単位をなすロボット単位にroot方向を尋ねる命令ASK_TO_ROOT_COMを送信し、それに対する返信命令RETURN_TO_ROOTによって、root方向を知る。そして、root方向に移動する(図９又は図１０の動作を使用する)。以後、ロボット単位j_kはロボット単位j_rootの位置（接続位置Gate_S）にたどり着くまでこれを繰り返す。
【０１３０】
［第三移動部２２］
ロボット単位が、接続位置に到達した場合に、第三移動部２２は、ロボット単位j_rootから自身のロボット単位の目標位置と、自身のロボット単位の目標位置に到達するためのパスとを取得し、取得した目標位置及びパスに従って自身のロボット単位を移動させる（ステップＳ２２）。
【０１３１】
例えば、接続位置Gate_Sにたどり着いた各ロボット単位j_kの第三移動部２２は、ロボット単位j_rootに対し、自身のG内での目標位置とそれに至る最適パス（そこに至るG内のロボット単位位置が全て埋まっているという前提の）の情報を要求する命令REQUEST_PATH_TO_GOAL_COMを送信し、それに対するロボット単位j_rootからの返信命令RETURN_PATH_TO_GOAL_COMを受信後、受信したパス情報に従い、自身の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] + 1
Xr[j2] = 2 × Xr_u[j] + 1
Yr[j2] = 2 × Yr_u[j] 
Zr[j2] = 2 × Zr_u[j] + 1
Xr[j3] = 2 × Xr_u[j] + 1
Yr[j3] = 2 × Yr_u[j] + 1
Zr[j3] = 2 × Zr_u[j]
Xr[j4] = 2 × Xr_u[j] + 1
Yr[j4] = 2 × Yr_u[j] + 1
Zr[j4] = 2 × Zr_u[j] + 1
【０１３６】
なお、各ロボットiが所属するロボット単位jは隊列制御のどの時刻においても不変である。また、各ロボット単位jの初期位置を（Xr_u0[j],Yr_u0[j],Zr_u0[j]）とし、目標位置を（Xr_ue[j],Yr_ue[j],Zr_ue[j]）とする。
【０１３７】
第一実施形態と第二実施形態を組み合わせて、８マスロボット単位で構成されたロボット隊列を任意の隊列に変形させることができる。図１５（Ｂ）のドットで示された４マスロボット単位をまず第一実施形態の方法で目標位置G内に移動させ、次に図１５（Ｂ）の白で示された４マスロボット単位形態で整列させる。続いて、白で示された４マスロボット単位を第二実施形態体の方法で目標位置G内に移動させる。
【０１３８】
ただし、最初のドットで示された４マスロボット単位の移動では、接続位置Gate_Sからのマンハッタン距離が近いものから優先的に目標位置Gへの移動を行っていく点と、続いての白で示された４マスロボット単位の移動では、目標位置G内の接続位置Gate_Sからのマンハッタン距離が大きいものから順に接続位置Gate_Sを通過する点だけが第一実施形態及び第二実施形態とは異なる。他の点については、第一実施形態及び第二実施形態と同様である。
【０１３９】
第三実施形態の移動ロボットは、図２０に示すように、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４、返信位置距離計算命令転送部５、動作時刻告知命令送信部６、動作時刻告知命令転送部７、第一移動部８、移動開始命令送信部９、移動開始命令転送部１０、第二移動部１１、第三移動部１２、判定部１３、第四移動部１４、第五移動部１５、待ち命令送信部１６、待ち命令転送部１７動作開始命令送信部１８、動作開始命令転送部１９、第一移動部２０、第二移動部２１及び第三移動部２２を例えば備えている。
【０１４０】
移動ロボットの制御方法は、移動ロボットの各部が、例えば図２１及び以下に説明するステップＳ１からステップＳ２２の処理を行うことにより実現される。
【０１４１】
以下では、第一実施形態及び第二実施形態と異なる部分を中心に説明する。第一実施形態及び第二実施形態と同様の部分については説明を省略する。
【０１４２】
まず、第一実施形態と同様にして、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４及び返信位置距離計算命令転送部５、動作時刻告知命令送信部６、動作時刻告知命令転送部７、第一移動部８、移動開始命令送信部９、移動開始命令転送部１０、第二移動部１１、第三移動部１２、判定部１３、第四移動部１４、第五移動部１５、待ち命令送信部１６、待ち命令転送部１７によるステップＳ１からステップＳ１７の処理が行われる。
【０１４３】
ただし、動作時刻告知命令送信部６は、各ロボット単位の移動開始時刻を、接続位置Gate_Sからのマンハッタン距離が近いロボット単位から優先的に目標位置Gへの移動を開始するように決定する（ステップＳ６）。
【０１４４】
また、図１５（Ｂ）のドットで示された４マスロボット単位は、目標位置Gにおいて、図１５（Ｂ）の白で示された４マスロボット単位の位置にポジションを取るとする。
【０１４５】
その後、第二実施形態と同様にして、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４、返信位置距離計算命令転送部５、動作開始命令送信部１８、動作開始命令転送部１９、第一移動部２０、第二移動部２１及び第三移動部２２によるステップＳ１からステップＳ５及びステップＳ１８からステップＳ２２の処理が行われる。
【０１４６】
ただし、動作開始命令送信部１８は、各ロボット単位の移動開始時刻を、目標位置G内の接続位置Gate_Sからのマンハッタン距離が大きいものから順に接続位置Gate_Sを通過するように決定する（ステップＳ１８）。
【０１４７】
なお、２回目の、位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４及び返信位置距離計算命令転送部５によるステップＳ１からステップＳ５の処理は行われなくてもよい。この場合、１回目の位置距離計算命令送信部１、位置距離計算命令転送部２、返信位置距離計算命令送信部３、方向記憶部４及び返信位置距離計算命令転送部５によるステップＳ１からステップＳ５の処理の結果を用いて、第二実施形態と同様の、動作開始命令送信部１８、動作開始命令転送部１９、第一移動部２０、第二移動部２１及び第三移動部２２によるステップＳ１８からステップＳ２２の処理が行われる。
【０１４８】
第三実施形態においても、全体の形状の変形動作と変形後のロボット位置入れ替えを別個のプロセスとせずに同時に行うことで、隊列制御動作にかかる時間を短縮することができる。
【０１４９】
＜プログラム及び記録媒体＞
移動ロボットの各部における処理をコンピュータによって実現する場合、これらの装置の各部がが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各部の処理がコンピュータ上で実現される。
【０１５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１５１】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１５２】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０１５３】
１      位置距離計算命令送信部
２      位置距離計算命令転送部
３      返信位置距離計算命令送信部
４      方向記憶部
５      返信位置距離計算命令転送部
６      動作時刻告知命令送信部
７      動作時刻告知命令転送部
８      第一移動部
９      移動開始命令送信部
１０    移動開始命令転送部
１１    第二移動部
１２    第三移動部
１３    判定部
１４    第四移動部
１５    第五移動部
１６    命令送信部
１７    命令転送部
１８    動作開始命令送信部
１９    動作開始命令転送部
２０    第一移動部
２１    第二移動部
２２    第三移動部
【図１】
2020035123.tif 000003
【図２】
2020035123.tif 000004
【図３】
2020035123.tif 000005
【図４】
2020035123.tif 000006
【図５】
2020035123.tif 000007
【図６】
2020035123.tif 000008
【図７】
2020035123.tif 000009
【図８】
2020035123.tif 000010
【図９】
2020035123.tif 000011
【図１０】
2020035123.tif 000012
【図１１】
2020035123.tif 000013
【図１２】
2020035123.tif 000014
【図１３】
2020035123.tif 000015
【図１４】
2020035123.tif 000016
【図１５】
2020035123.tif 000017
【図１６】
2020035123.tif 000018
【図１７】
2020035123.tif 000019
【図１８】
2020035123.tif 000020
【図１９】
2020035123.tif 000021
【図２０】
2020035123.tif 000022
【図２１】
2020035123.tif 000023