(57)【要約】【課題】多数のロボットの存在を考慮しつつも、計画計算に必要な計算時間や計算機の記憶容量を一台のロボットを扱うときと同様に少ないものに低減可能で、かつ、ロボット同士が接したまま状態を維持しつつ任意の矩形隊列から、他の任意の矩形隊列へ障害物のある環境にて変形動作を行うことを可能とする、ロボット協調隊列形成技術を提供する。【解決手段】行動制御システムは、価値関数が記憶される記憶部と、価値関数を用いて、１回の行動制御により、少なくとも１つの制御対象物が静止し、残りの制御対象物全てが同じ方向に移動するように制御する行動選択部とを含み、ある制御対象物の、第一〜第四位置の何れかに他の制御対象物が存在する状態を接続状態とし、行動選択部は、複数の制御対象物全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する。【選択図】図５
2016009354.tif 000002
【特許請求の範囲】
【請求項１】
複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う行動制御システムであって、
第一方向に対して平行でない方向を第二方向とし、第一方向に対して反対の方向を第三方向とし、第二方向に対して反対の方向を第四方向とし、前記目標位置の集合は第一方向に平行な二つの辺と第二方向に平行な二つの辺からなる平行四辺形を成し、前記制御対象物は、二次元平面上の第一〜第四方向において隣接する他の制御対象物と通信するための通信手段と、当該制御対象物の２次元平面上の第一方向において隣接する第一位置、第二方向において隣接する第二位置、第三方向において隣接する第三位置、及び、第四方向において隣接する第四位置に、障害物または他の制御対象物が存在するか否かを判定し、当該制御対象物の２次元平面上の、第一位置に第二方向において隣接する第五位置、第二位置に第三方向において隣接する第六位置、第三位置に第四方向において隣接する第七位置、及び、第四位置に第一方向において隣接する第八位置に他の制御対象物が存在するか否かを判定する隣接状態判定部とを備え、制御対象物がその制御対象物の現在の位置sにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて制御され、１回の行動制御により、静止するか、または、二次元平面上の第一〜第四位置に移動するように制御されるものとし、
前記価値関数が記憶される記憶部と、
前記価値関数を用いて、１回の行動制御により、少なくとも１つの制御対象物が静止し、残りの制御対象物全てが同じ方向に移動するように制御する行動選択部とを含み、
ある制御対象物の、第一〜第四位置の何れかに他の制御対象物が存在する状態を接続状態とし、前記行動選択部は、複数の前記制御対象物全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する、
行動制御システム。
【請求項２】
請求項１の行動制御システムであって、
前記行動選択部は、
ある制御対象物ｉが、ある方向の隣接する位置に移動するという行動aを実行した場合に得られる前記価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる前記価値関数の値Ｑ(s,0)よりも大きくなる場合に、前記制御対象物ｉから前記行動aにより移動する方向において連続して隣接する全ての他の制御対象物について、前記行動aを実行した場合に得られる前記価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる前記価値関数の値Ｑ(s,0)よりも小さいことを理由として、前記行動aが非可動と設定されている場合には、行動aが可動となるように制御する移動方向設定部を含む、
行動制御システム。
【請求項３】
請求項１または２の行動制御システムであって、
前記行動選択部は、
ある制御対象物ｉの２次元平面上の第一〜第四位置に、障害物が存在するときに、その制御対象物ｉが障害物が存在する方向に移動しないように制御し、さらに、その制御対象物ｉが障害物が存在する方向とは反対方向において連続して隣接する全ての他の制御対象物が障害物が存在する方向に移動しないように制御する可動判定部と、
前記隣接状態判定部による判定結果を用いて、仮にある制御対象物ｉが行動aによりある方向に移動したときに、前記行動aにより移動する方向と平行でない方向において隣接する制御対象物との接続状態を維持するか否かを判定し、維持しない場合、前記制御対象物ｉは前記行動aにより移動する方向と平行でない方向において隣接する制御対象物に対して相対移動不可能であると設定し、前記制御対象物ｉが前記行動aについて非可動である場合、前記制御対象物ｉに前記行動aにより移動する方向及びその反対方向において隣接する制御対象物が行動aについて非可動となるように制御し、前記制御対象物ｉが前記行動aについて非可動であって、かつ、前記行動aにより移動する方向と平行でない方向において前記制御対象物ｉに隣接する制御対象物が、前記行動aにより移動する方向に相対移動不可能である場合には、行動aにより移動する方向と平行でない方向において制御対象物ｉに隣接する制御対象物が行動aについて非可動となるように制御する接続判定部と、
静止するように制御された制御対象物の位置を基準として、前記隣接状態判定部による判定結果を用いて、実際に行動した後の制御対象物の位置である行動後位置を求め、その行動後位置が、選択された行動に基づいて行動した場合に想定される想定位置と一致するか否かを判定する位置判定部と、を含む、
行動制御システム。
【請求項４】
行動制御システムを用いて、複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う行動制御方法であって、
第一方向に対して平行でない方向を第二方向とし、第一方向に対して反対の方向を第三方向とし、第二方向に対して反対の方向を第四方向とし、前記目標位置の集合は第一方向に平行な二つの辺と第二方向に平行な二つの辺からなる平行四辺形を成し、前記制御対象物は、二次元平面上の第一〜第四方向において隣接する他の制御対象物と通信するための通信手段と、当該制御対象物の２次元平面上の第一方向において隣接する第一位置、第二方向において隣接する第二位置、第三方向において隣接する第三位置、及び、第四方向において隣接する第四位置に、障害物または他の制御対象物が存在するか否かを判定し、当該制御対象物の２次元平面上の、第一位置に第二方向において隣接する第五位置、第二位置に第三方向において隣接する第六位置、第三位置に第四方向において隣接する第七位置、及び、第四位置に第一方向において隣接する第八位置に他の制御対象物が存在するか否かを判定する隣接状態判定部とを備え、制御対象物がその制御対象物の現在の位置sにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて制御され、１回の行動制御により、静止するか、または、二次元平面上の第一〜第四位置に移動するように制御されるものとし、
予め計算された前記価値関数を用いて、１回の行動制御により、少なくとも１つの制御対象物が静止し、残りの制御対象物全てが同じ方向に移動するように制御する行動選択ステップとを含み、
ある制御対象物の、第一〜第四位置の何れかに他の制御対象物が存在する状態を接続状態とし、前記行動選択ステップにおいて、複数の前記制御対象物全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する、
行動制御方法。
【請求項５】
請求項４の行動制御方法であって、
前記行動選択ステップは、
ある制御対象物ｉが、ある方向の隣接する位置に移動するという行動aを実行した場合に得られる前記価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる前記価値関数の値Ｑ(s,0)よりも大きくなる場合に、前記制御対象物ｉから前記行動aにより移動する方向において連続して隣接する全ての他の制御対象物について、前記行動aを実行した場合に得られる前記価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる前記価値関数の値Ｑ(s,0)よりも小さいことを理由として、前記行動aが非可動と設定されている場合には、行動aが可動となるように制御する移動方向設定ステップを含む、
行動制御方法。
【請求項６】
請求項４または５の行動制御方法であって、
前記行動選択ステップは、
ある制御対象物ｉの２次元平面上の第一〜第四位置に、障害物が存在するときに、その制御対象物ｉが障害物が存在する方向に移動しないように制御し、さらに、その制御対象物ｉが障害物が存在する方向とは反対方向において連続して隣接する全ての他の制御対象物が障害物が存在する方向に移動しないように制御する可動判定ステップと、
前記隣接状態判定ステップによる判定結果を用いて、仮にある制御対象物ｉが行動aによりある方向に移動したときに、前記行動aにより移動する方向と平行でない方向において隣接する制御対象物との接続状態を維持するか否かを判定し、維持しない場合、前記制御対象物ｉは前記行動aにより移動する方向と平行でない方向において隣接する制御対象物に対して相対移動不可能であると設定し、前記制御対象物ｉが前記行動aについて非可動である場合、前記制御対象物ｉに前記行動aにより移動する方向及びその反対方向において隣接する制御対象物が行動aについて非可動となるように制御し、前記制御対象物ｉが前記行動aについて非可動であって、かつ、前記行動aにより移動する方向と平行でない方向において前記制御対象物ｉに隣接する制御対象物が、前記行動aにより移動する方向に相対移動不可能である場合には、行動aにより移動する方向と平行でない方向において制御対象物ｉに隣接する制御対象物が行動aについて非可動となるように制御する接続判定ステップと、
静止するように制御された制御対象物の位置を基準として、前記隣接状態判定ステップによる判定結果を用いて、実際に行動した後の制御対象物の位置である行動後位置を求め、その行動後位置が、選択された行動に基づいて行動した場合に想定される想定位置と一致するか否かを判定する位置判定ステップと、を含む、
行動制御方法。
【請求項７】
請求項１から３の何れかに記載の行動制御システムとしてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の制御対象物の行動を制御する技術に関する。例えば、複数のロボットを、開始位置における隊列形成状態から協調して移動させ、障害物を回避させ、目標位置で隊列形成をさせるための各ロボットの行動計画を求めるロボット協調制御技術に関する。
【背景技術】
【０００２】
近年、多数の自律移動ロボットを効率的に制御にするための研究が活発に行われている。その任務内容は、人の入れない箇所の監視、物品の搬送などさまざまであるが、多数のロボットの協調動作による隊列形成を効率的に行わせるための技術が求められており盛んに研究が行われている（例えば、非特許文献１参照）。多数のロボットによる効率的な隊列形成を実現するには、それぞれのロボットの配置、動作順序などを事前に計画することが重要である。このような計画においては、当然ながら、複数のロボットが動作する実環境における障害物の存在や経路の形状なども十分に考慮しなければならない。
【０００３】
このような計画計算を行うための効果的な手法の一つとして、マルコフ決定過程における動的計画法や強化学習の手法があり、さまざまな研究が行われている（例えば、非特許文献２参照）。
【０００４】
また、ロボットの隊列制御の中でも、ロボット同士が互いに接したままの状態で、アメーバのように全体で移動を行うという仮定の下でのロボット隊列制御においては、ロボット同士の相対的な位置関係から、各ロボットの絶対位値の決定が可能であるという利点と、付加的な位置計測用の装備を必要としないという利点があり、そのようなロボットの研究もおこなわれている。例えば、非特許文献３に示すものでは任意の矩形形状隊列から他の矩形形状隊列までの隊列制御が示されている。
【０００５】
また、非特許文献４に示す研究に至る一連の研究では、ある隊列から他の隊列に変化する隊列制御が示されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】M.Shimizu, A.Ishiguro, T.Kawakatsu, Y.Masubuchi, “Coherent Swarming from Local Interaction by Exploiting Molecular Dynamics and Stokesian Dynamics Methods”, Proceeaings of the 2003 IEE/RSJ International Conference on intelligent Robots and Systems, Las Veqas, pp.1614-1619, October 2003.
【非特許文献２】Y.Wang, C.W.de Silva, “Multi-Robot Box-pushing: Single-Agent Q-Learning vs. Team Q-Learning”, Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, pp.3694-3699, October 2006.
【非特許文献３】A.Becker, G.Habibi, J.Werfel, M.Rubenstein, and J.McLurkin, “Massive Uniform Manipulation: Controlling Large Populations of Simple Robots with a Common Input Signal”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Japan, pp.520-527, November, 2013.
【非特許文献４】Stanton Wong1 and Jennifer Walter ”Deterministic Distributed Algorithm for Self-Reconfiguration of Modular Robots from Arbitrary to Straight Chain Configurations”, Proceedings of the 2013 IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, pp.537-543, May 6-10, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１の手法では、流体力学的な特性をロボット動作に組み込む手法を用いて群ロボットの動作を制御しており、低い計算負荷での制御を可能にしている利点があるが、任意の形状の隊列形成をすることができるとは限らない。
【０００８】
また、非特許文献２の手法のように、マルコフ決定過程における動的計画法や強化学習を使用してこのような計画を行おうとすると、単体のロボットを使用する場合に比べて複数のロボットを使用する場合には、その計算に要する時間や計算機の記憶容量がロボットの数に対して指数関数的に増大してしまう。その主たる原因となるのが、探索計算のためのマルコフ状態空間内の状態数の莫大な増加である。非特許文献２では、検証された強化学習の手法では、ロボット数の増加に伴い、指数関数的に計算負荷が増加するという、マルコフ状態空間内の爆発問題への解決策は示されていない。
【０００９】
また、非特許文献１，２の手法ともに、付加的な位置計測用の装備を必要とする。
【００１０】
また、非特許文献３では、ロボットが接したままの状態を維持するという条件を考慮して、付加的な位置計測用の装備を必要としないが、その実現には障害物の存在を必要としており、動作計画に必要な計算量が、ロボットの台数の２乗に比例してしまい、ロボットの台数の増加とともに急激に上昇する。
【００１１】
非特許文献４の手法においては、一度、線形隊列への変換をしなければならず、可能な隊列形成動作そのものへの制約が大きい。
【００１２】
このような現状に鑑みて、本発明では、多数のロボットの存在を考慮しつつも、計画計算に必要な計算時間や計算機の記憶容量を一台のロボットを扱うときと同様に少ないものに低減可能で、かつ、ロボット同士が接したままの状態を維持しつつ任意の矩形隊列から、他の任意の矩形隊列へ障害物のある環境にて変形動作を行うことを可能とする、ロボット協調隊列形成技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明の一態様によれば、行動制御システムは、複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う。行動制御システムは、第一方向に対して平行でない方向を第二方向とし、第一方向に対して反対の方向を第三方向とし、第二方向に対して反対の方向を第四方向とし、目標位置の集合は第一方向に平行な二つの辺と第二方向に平行な二つの辺からなる平行四辺形を成し、制御対象物は、二次元平面上の第一〜第四方向において隣接する他の制御対象物と通信するための通信手段と、当該制御対象物の２次元平面上の第一方向において隣接する第一位置、第二方向において隣接する第二位置、第三方向において隣接する第三位置、及び、第四方向において隣接する第四位置に、障害物または他の制御対象物が存在するか否かを判定し、当該制御対象物の２次元平面上の、第一位置に第二方向において隣接する第五位置、第二位置に第三方向において隣接する第六位置、第三位置に第四方向において隣接する第七位置、及び、第四位置に第一方向において隣接する第八位置に他の制御対象物が存在するか否かを判定する隣接状態判定部とを備え、制御対象物がその制御対象物の現在の位置sにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて制御され、１回の行動制御により、静止するか、または、二次元平面上の第一〜第四位置に移動するように制御されるものとし、価値関数が記憶される記憶部と、価値関数を用いて、１回の行動制御により、少なくとも１つの制御対象物が静止し、残りの制御対象物全てが同じ方向に移動するように制御する行動選択部とを含み、ある制御対象物の、第一〜第四位置の何れかに他の制御対象物が存在する状態を接続状態とし、行動選択部は、複数の制御対象物全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する。
【００１４】
上記の課題を解決するために、本発明の他の態様によれば、行動制御方法は、行動制御システムを用いて、複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う。行動制御方法は、第一方向に対して平行でない方向を第二方向とし、第一方向に対して反対の方向を第三方向とし、第二方向に対して反対の方向を第四方向とし、目標位置の集合は第一方向に平行な二つの辺と第二方向に平行な二つの辺からなる平行四辺形を成し、制御対象物は、二次元平面上の第一〜第四方向において隣接する他の制御対象物と通信するための通信手段と、当該制御対象物の２次元平面上の第一方向において隣接する第一位置、第二方向において隣接する第二位置、第三方向において隣接する第三位置、及び、第四方向において隣接する第四位置に、障害物または他の制御対象物が存在するか否かを判定し、当該制御対象物の２次元平面上の、第一位置に第二方向において隣接する第五位置、第二位置に第三方向において隣接する第六位置、第三位置に第四方向において隣接する第七位置、及び、第四位置に第一方向において隣接する第八位置に他の制御対象物が存在するか否かを判定する隣接状態判定部とを備え、制御対象物がその制御対象物の現在の位置sにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて制御され、１回の行動制御により、静止するか、または、二次元平面上の第一〜第四位置に移動するように制御されるものとし、予め計算された価値関数を用いて、１回の行動制御により、少なくとも１つの制御対象物が静止し、残りの制御対象物全てが同じ方向に移動するように制御する行動選択ステップとを含み、ある制御対象物の、第一〜第四位置の何れかに他の制御対象物が存在する状態を接続状態とし、行動選択ステップにおいて、複数の制御対象物全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する。
【発明の効果】
【００１５】
本発明に拠れば、詳しくは後述するが、一台のロボットに必要な分だけのマルコフ状態空間を用意し、それを用いて動的計画法を利用して各位置でのロボットの行動方策を計算し、その行動方策を利用することで、ロボットに任意の矩形隊列形状と、任務環境内の任意の障害物形状に対応した、ロボット同士が接した状態を維持したうえでの多数ロボットのための隊列形成アルゴリズムを獲得することができる。すなわち、ロボット数に依存せずにロボット一台分の計画計算負荷での自己位置座標定義型隊列形成アルゴリズム獲得ができる。
【図面の簡単な説明】
【００１６】
【図１】多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務を説明するための図。
【図２】多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務を説明するための図。
【図３】多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務を説明するための図。
【図４】多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務を説明するための図。
【図５】第一実施形態に係る行動制御システムの機能ブロック図。
【図６】第一実施形態に係る行動制御システムの処理フローの例を示す図。
【図７】nとマス目との対応の例を示す図。
【図８】可動判定部の処理フローの例を示す図。
【図９】可動判定部の処理内容を説明するための図。
【図１０】移動方向設定部の処理フローの例を示す図。
【図１１】移動方向設定部の処理フローの例を示す図。
【図１２】接続判定部の処理フローの例を示す図。
【図１３】接続判定部の処理フローの例を示す図。
【図１４】図１４Ａは接続判定部の処理内容を説明するための図、図１４Ｂは接続判定部の処理内容を説明するための図。
【図１５】各格子が菱形での場合の例を示す図。
【図１６】図１６Ａはp個の目標位置(Xre[ｉ],Yre[i])の集合Gの中にp個の初期位置(Xr0[i],Xr0[i])の一部が含まれている場合を示す図、図１６Ｂは初期位置の個数をq、目標位置の個数をpとし、q>pの場合を示す図。
【図１７】可動判定部の処理内容を説明するための図。
【図１８】移動方向設定部の処理フローの例を示す図。
【図１９】接続判定部の処理フローの例を示す図。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００１８】
＜第一実施形態＞
［理論的背景］
まず、行動制御装置及び方法の理論的背景について説明する。以下、行動制御の対象である制御対象物が、ロボットである場合を例に挙げて説明するが、制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００１９】
多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務は、例えば図１に例示するような壁で区切られた部屋においての開始位置から目標位置まで複数のロボットの移動によって実現するものである。
【００２０】
任務を行うロボットは、p台（例えばp≧50）であり、各ロボットは、二次元平面におけるX軸方向及びY軸方向のそれぞれに移動可能とする。すなわち、この例では、各ロボットは、図１の紙面に対して上下左右の四方向に移動可能とする。図１の各格子にはロボットは一台しか存在することができない。それぞれのロボットは、移動しようとする方向に障害物か他のロボットがある場合には、静止をするものと仮定する。
【００２１】
図１において、Rが記載された格子はロボットが存在する位置を示し、Oが記載された格子は障害物が存在する位置を示す。また、太線の破線で囲まれた領域は開始位置を示し、太線の一点鎖線で囲まれた領域は目標隊列エリアGを示し、太線の実線で囲まれた領域は後述する目標隊列エリアGの入口位置Peを示す。このように、図１においては、ロボットの開始位置と目標位置での隊列形状は矩形である。
【００２２】
それぞれのロボットi（iはロボット番号を表し、i=0,1,2,…,p-1とする）の初期位置を（Xr0[i],Yr0[i]）とし、目標位置を（Xre[i],Yre[i]）とするとき、初期位置に配置されたロボットが、目標位置まで移動するための行動計画を求める問題を考える。
【００２３】
このような問題に対して単純にマルコフ状態遷移モデルを適用しようとする場合、マルコフ状態空間は、ロボットiの位置（Xr[i],Yr[i]）、ロボットiの行動a[i]によって構成される。各状態（ロボットの位置と行動）は離散値で表現される。部屋をX,Yの直交座標系からなる２次元平面で表すと、X軸、Y軸をそれぞれ離散化表現した値により各位置を表現する。つまり、図１のように部屋（２次元平面）は格子で区切られ、各格子が各位置に対応する。また、各格子において、障害物の「ある／なし」が予め設定されている。
【００２４】
また、この例では、制御対象物である行動主体は部屋に配置されている各ロボットとなる。ロボットiの行動a[i]∈D[i]は、静止、上下左右方向への１格子分の移動の計５種類のうちの何れかを取る。すなわち、D[ｉ]∈{0,1,2,3,4}として、各行動は例えば以下のように定義される。
0: 静止
1: 二次元平面上で右方向に１格子だけ移動する
2: 二次元平面上で上方向に１格子だけ移動する
3: 二次元平面上で左方向に１格子だけ移動する
4: 二次元平面上で下方向に１格子だけ移動する
【００２５】
このような任務環境におけるマルコフ状態空間は、ロボット数×２の次元数の状態を持ち、かつ選択可能な行動数は、ロボットの行動（＝５通り）のロボット数乗だけ存在する。例えば、ロボット数が５０で、部屋の縦横方向の格子数がそれぞれ２０であるとすれば状態数は２０の100乗個にもなり、探索計算に要する資源の量は膨大なものとなる。さらにロボット数が１台増えるごとに、その状態数は400倍増加していくことになり、複数ロボットを使用する場合の大きな問題となっている。
【００２６】
そこで、この実施形態では、このような状態空間の爆発をさけるために、学習に使用するマルコフ状態空間を、一台分のロボットの状態変数のみで構成することにする。すなわち、状態変数及び行動変数を以下のように定義する。
状態変数s=（Xr,Yr），行動変数a∈{0,1,2,3,4}
p台あるすべてのロボットは、この状態変数を引数とした１個の価値関数Q(s,a)を共有し、行動決定を行う。
【００２７】
なお、価値関数Q（s,ａ）の計算は、例えば、動的計画法を使用して、任務の事前に行うものとする。まず、各ロボットの目標位置をここに厳密に割り振ることをせず、目標位置全体の集合を、目標隊列エリアGと定義する。すなわち、
（Xre[i],Yre[i]）∈G  …(3)
として、各ロボットはG内の全ての全ての位置を自由に目標位置とすることができるものとする。つまり、Gをちょうど流体を注ぐ器のようなものとして扱う。すなわち、各ロボットは、Gの境界上にあるどの位置からもGに入ることが可能であるが、一度G内に入ったロボットは、Gを出る行動をとることができないものとする。また、強化学習時における報酬の設定については、Gの境界上に一点だけ入口の点Peを設定し、ロボットがPeからG内に入ったときのみ高報酬であるr=1を与え、それ以外の経験については、すべてr=0を与えるものとする。Peの位置を入口位置と呼ぶ。本実施形態では、Gで構成される矩形の４角のいずれかの１点を選んで入口位置Peとし、Peにロボットが移動した場合において、高報酬値１が与えられ、その他は０の報酬が与えられる。Peの位置はGの内部であって、Gで構成される矩形の４角のいずれかの１点であればどこでも構わないが、ロボットの開始位置から近い位置を選ぶのがロボットの動作をスムーズにするうえで効果的である。
【００２８】
このような報酬を設定する背景として、G内に入ったロボットは、本実施形態の制御を受けることで、G内のロボットが存在しない位置（空隙位置とよぶことにする。）を、次第にGを構成する矩形の４角の点いずれかに誘導していくことになる。これを利用して、Peの付近にてG内に入ろうとするロボットが常に待機するようにすれば、最後の一つのロボットも待ち時間を長くとることなしに、G内に入ることができるのである。
【００２９】
本実施形態において、ロボットは各々のロボット同士の相対位置関係から、各々の絶対位置を計測することができ、また隣の位置に他のロボットが存在しているか否か、障害物があるか否か、そして、自身が目標位置上にいるかどうかを知ることができるものとする。それを実現するためのロボット同士の位置関係と、移動に関する拘束条件は、
(1)各行動選択時に、必ず１つ以上の移動を行わないロボットがなければならない。
(2)各ロボットの隣り合う位置（上下左右）に必ず、他のロボットが存在していなければならない。
(3)隣り合うロボット同士がなす群れは、一つでなければならない。
である。この拘束条件を維持しつつ目標位置での隊列形成を行う動作の例を図１〜４に示す。以下、この条件を維持しながらの、価値関数Q(s,a)を利用した隊列移動の方法について述べる。
【００３０】
このような一つの価値関数Q(s,a)を使用して行動選択を行った場合に起こる問題について述べる（図１）。通例のMDP(Markov decision process)での強化学習や動的計画法で求められた価値関数を使用した行動選択では、それぞれの状態ｓにおいて、Q(s,a)の値を最大化する行動aを選択するのが通例である。本実施形態のように、各ロボットが単一の価値関数Qを参照して行動選択を行う場合、群れを構成する各ロボットにとってのQ(s,a)の値を最大化する行動aは、必ずしも一致しない。あるロボットはa=1の右への移動を選択し、別のロボットは、a=3の左への移動を選択することも起こりうることである。そのような状況では、ロボットが互いにそれぞれの選択した方向への移動をしようとして、衝突が起こり、群れ全体としての移動が滞ってしまうことが頻繁に起こりうる。また、目標位置における隊列形成において、各ロボットを目標位置での隊列内のどの位置に配置するかを割り振ることも重要である。これが適切に行われないと、目標位置近傍にて、ロボットが他のロボットの移動を邪魔してしまい、これも群れの移動の停滞を引き起こす。通例、これらを避けるためには、各ロボットが他のロボットの位置も把握したうえで行動選択を行う必要があり、そのためには、膨大な数の状態を含む状態空間を取り扱わなければならないのである。本実施形態では以上の、
(4)各ロボット同士の選択する行動の違いによる衝突に伴う、群れの移動の停滞を避ける。
(5)目標位置において、適切にロボットを隊列形成させる。
ための手法も備えている。
【００３１】
以下、ロボット移動の条件である(1)(2)(3)(4)(5)を実現するための処理について述べる。
【００３２】
＜第一実施形態に係る行動制御システム１００＞
図５は第一実施形態に係る行動制御システム１００の機能ブロック図を、図６はその処理フローの例を示す。行動制御システム１００は、図５に示すように、動作計画部１１０と、行動選択部１２０と、記憶部１４０と、通信部１５０と、入力部１６０とを含む。
【００３３】
行動選択部１２０は、隣接状態判定部１２１と、可動判定部１２２と、移動方向設定部１２３と、接続判定部１２４と、位置更新部１２５と、位置判定部１２６とを含む。
【００３４】
以下では、制御の対象となる制御対象物が、ロボットである場合を例に挙げて説明する。もちろん、制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００３５】
本実施形態では、行動制御システム１００は、p台のロボットの行動を制御し、p台のロボットの内の１つのロボット上に実装される。なお、行動制御システム１００が実装されていないp-１台のロボットについても、通信部１５０と、隣接状態判定部１２１とを含む。
【００３６】
＜動作計画部１１０＞
動作計画部１１０は、MDPにおける価値関数Q(s,a)の値を、動的計画法により、ロボットの任務行動開始前に事前に計算し（Ｓ１１０）、記憶部１４０に格納する。ここで、動作計画部１１０の計算は、一台のロボットを使用したQ学習に置き換えてもよい。なお、別装置で価値関数Q(s,a)を計算しておき、ロボットの任務行動開始前に事前に記憶部１４０に格納しておけば、行動制御システム１００は、動作計画部１１０を備えなくともよい。
【００３７】
＜入力部１６０＞
入力部１６０には、p台のロボットiのそれぞれの初期位置(Xr0[i],Xr0[i])及びp個の目標位置の集合G={(Xre[0],Yre[0]),(Xre[1],Yre[1]),…,(Xre[p-1],Yre[p-1])}が入力され、記憶部１４０に記憶される。
【００３８】
なお、目標位置は、所定の入口位置Peを含むとする。この入口位置Peについての情報も、入力部１６０から入力され、記憶部１４０に記憶されるとする。
【００３９】
＜記憶部１４０＞
記憶部１４０には、位置s及びa∈{0,1,2,3,4}の組み合わせのそれぞれについての価値関数Q(s,a)が記憶されているとする。sの取りうる範囲は、対象となる二次元平面上の領域内のロボットｉが存在しうる全ての座標である。
【００４０】
各位置sの報酬r(s)についても、記憶部１４０に記憶されているとする。各位置sの報酬r(s)についての情報は、例えば入力部１６０から入力される。
【００４１】
なお、記憶部１４０に、各ロボットiが、行動aについて可動であるか非可動であるかを示す変数move[a][i]を格納しておく。なお、aは行動である。ロボットiが、行動aについて可動の際は値１を、そうでない場合は１以外の値をとるものとする。move[a][i]の値が0のときは障害物によりさえぎられることで非可動であり、2のときは、ロボットiが価値関数Qの値の都合で非可動になったということを示す。さらに、記憶部１４０に、各ロボットiの周囲に他のロボットがいるかどうか、障害物があるかどうかを示す変数を格納しておく。ここでは、可動判定部１２２、移動方向設定部１２３で使用する変数としてnext[n][i](n=1,2,3,4)を、接続判定部１２４で使用する変数としてconnect[n][i](n=1,2,3,4,5,6,7,8)を格納しておく。next[n][i]は、ロボットiの周囲の4つのマスnに他のロボットが存在するか否か、障害物が存在するか否かを値として保持する。また、next[n][i]は、ロボットが目標隊列エリアG内に存在するときに、ロボットiの周囲の4つのマスnが、目標隊列エリアGに含まれるか否かを値として保持する。connect[n][i]は、ロボットiの周囲の8つのマスnに他のロボットが存在するか否かを値として保持する。なお、nはロボットiからみた方向を示すインデックスであり、図７はnとマス目との対応の例を示す。なお、図中の値「0」はロボットiの位置を表す。
【００４２】
＜通信部１５０＞
行動制御システム１００が実装されているロボットも含め、全てのロボットは、通信部１５０を介して、二次元平面上の上下左右の方向において隣接する他のロボットと通信することができる。
【００４３】
＜行動選択部１２０＞
行動選択部１２０は、記憶部１４０から価値関数Qを取り出す。以下に述べるのは、ロボット動作開始後の各時刻ステップにおける行動選択の際に行われる処理であり、行動選択部１２０で行われる。行動選択部１２０は、通信部１５０を介して、他のロボットから後述する隣接状態判定部１２１の判定結果を受け取る。行動選択部１２０は、価値関数Qを用いて、１回の行動制御により、少なくとも１つのロボットが静止し、残りのロボット全てが同じ方向に移動するように制御する（Ｓ１２０）。ただし、行動選択部１２０は、複数のロボット全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する。なお、接続状態とは、あるロボットの、２次元平面上の上下左右の何れかの隣接する位置に他のロボットが存在する状態をいう。例えば、行動選択部１２０は、各ロボットiに対して、行動aを実行するように制御信号を出力して、各ロボットiを制御する。
【００４４】
前述の通り、行動選択部１２０は、隣接状態判定部１２１と、可動判定部１２２と、移動方向設定部１２３と、接続判定部１２４と、位置更新部１２５と、位置判定部１２６とを含み、ここで述べた順に処理が行われる。
【００４５】
＜隣接状態判定部１２１＞
隣接状態判定部１２１は、ロボットの２次元平面上の上下左右の隣接する位置に、障害物または他のロボットが存在するか否かを判定し、ロボットの２次元平面上の右上、左上、左下、右下の隣接する位置に他のロボットが存在するか否かを判定し（Ｓ１２１−１），判定結果を記憶部１４０に格納する。また、隣接状態判定部１２１は、ロボットが目標隊列エリアG内に存在するときに、ロボットの２次元平面上の上下左右の隣接する位置のマスが、目標隊列エリアGに含まれるか否かを判定し（Ｓ１２１−１）、判定結果を記憶部１４０に格納する。
【００４６】
なお、上述の通り、行動制御システム１００が実装されていないp-１台のロボットについても、通信部１５０と、隣接状態判定部１２１とを含むため、各ロボットｉは隣接状態判定部１２１において、自身の周囲８方向に障害物があるかどうか、他のロボットがいるかどうかを検出し、以下の通りにnext[n][i],connect[n][i]の値を設定し、通信部１５０を介して行動制御システム１００に出力する。行動制御システム１００は、通信部１５０を介して各ロボットｉから判定結果next[n][i],connect[n][i]を受け取り、行動制御システム１００に含まれる隣接状態判定部１２１の判定結果next[n][i],connect[n][i]と一緒に記憶部１４０に格納する。なお、p台のロボットは、条件(2)各ロボットの隣り合う位置（上下左右）に必ず、他のロボットが存在し、条件(3)隣り合うロボット同士がなす群れは、一つなので、各ロボットｉは通信部１５０を介してp-1個の判定結果next[n][i],connect[n][i]を直接、または、他のロボットを介して、行動制御システム１００に送信することができる。また、行動制御システム１００は、通信部１５０を介して、直接、または、他のロボットを介して、各ロボットiに行動aを実行するように制御信号を送信することができる。また、他の情報もp台のロボット間で送受信可能となる。
【００４７】
(next[n][i]変数での上下左右方向の検出)
まず、すべてのnとiでnext[n][i]の値をpに初期化し、続いて、
i番目のロボットが、右（X軸正）方向でj番目のロボットと接しているとき、next[1][i]←j
i番目のロボットが、上（Y軸正）方向でj番目のロボットと接しているとき、next[2][i]←j
i番目のロボットが、左（X軸負）方向でj番目のロボットと接しているとき、next[3][i]←j
i番目のロボットが、下（Y軸負）方向でj番目のロボットと接しているとき、next[4][i]←j
とする。続いて、
i番目のロボットが、右（X軸正）方向で障害物と接しているか、i番目のロボットがG内にあって、右（X軸正）方向で隣接する格子がG外であるとき、next[1][i]←-1
i番目のロボットが、上（Y軸正）方向で障害物と接しているか、i番目のロボットがG内にあって、上（Y軸正）方向で隣接する格子がG外であるとき、next[2][i]←-1
i番目のロボットが、左（X軸負）方向で障害物と接しているか、i番目のロボットがG内にあって、左（X軸負）方向で隣接する格子がG外であるとき、next[3][i]←-1
i番目のロボットが、下（Y軸負）方向で障害物と接しているときか、i番目のロボットがG内にあって、下（Y軸負）方向で隣接する格子がG外であるとき、next[4][i]←-1
とする。結果、ロボットが、各方向にて、なにとも接しておらず、Gの境界上にもないときに、next[n][i]←pとなる。
【００４８】
(connect[n][i]変数での右上、左上、左下、右下の検出)
つづいて、8つ隣接方向において、他のロボットが存在するかどうかを検出し、以下のようにconnect変数の値を設定する。
i番目のロボットが、右（X軸正）方向でj番目のロボットと接しているとき、next[1][i]←j
i番目のロボットが、上（Y軸正）方向でj番目のロボットと接しているとき、next[2][i]←j
i番目のロボットが、左（X軸負）方向でj番目のロボットと接しているとき、next[3][i]←j
i番目のロボットが、下（Y軸負）方向でj番目のロボットと接しているとき、next[4][i]←j
i番目のロボットの右上（X軸正、Y軸正）隣の位置にロボットjがあるとき、next[5][i]←j
i番目のロボットの左上（X軸負、Y軸正）隣の位置にロボットjがあるとき、next[6][i]←j
i番目のロボットの左下（X軸負、Y軸負）隣の位置にロボットjがあるとき、next[7][i]←j
i番目のロボットの右下（X軸正、Y軸負）隣の位置にロボットjがあるとき、next[8][i]←j
上記以外の条件で、next[n][i]←p
【００４９】
例えば、センサにより隣接する位置に、障害物が存在するか否かを検知する。通信部１５０により通信することにより隣接する位置に、他のロボットが存在するか否かを検知すればよい。通信する際に互いにロボットの番号やID等を送信することで、隣接する位置に存在するロボットの番号jを知ることができる。
【００５０】
＜可動判定部１２２＞
可動判定部１２２は、あるロボットiの２次元平面上の上下左右の隣接する位置に、障害物が存在するときに、そのロボットiが障害物が存在する方向に移動しないように制御し、さらに、そのロボットiが障害物が存在する方向とは反対方向において連続して隣接する全ての他のロボットiが障害物が存在する方向に移動しないように制御する（Ｓ１２２）。また、可動判定部１２２は、行動aによりロボットｉがG内からG外へ移動しないように制御し、さらに、そのロボットiがGの境界線が存在する方向とは反対方向において連続して隣接する全ての他のロボットiが境界線が存在する方向に移動しないように制御する（Ｓ１２２）。例えば、ロボットiに対して、以下の通りにmove[a][i]を更新する。図８は可動判定部１２２の処理フローの例を示す。
【００５１】
まず、全てのa=1,2,3,4とi=0,1,…,p-1において、move[a][i]の値を１とする（Ｓ１２２ａ）。続いて、0からp-1までの間の整数でランダムに選んだ値をistopとし（Ｓ１２２ｂ）、全てのa=1,2,3,4の値について、move[a][istop]の値を0とする（Ｓ１２２ｃ）。なお、この処理は、「(1)各行動選択時に、必ず１つ以上の移動を行わないロボットがなければならない。」との条件を維持するためのものであり、少なくとも、ロボットistopが静止するように制御している。
【００５２】
続いて、以下の処理を、move[a][i]の値が一つも更新されなくなるまで繰り返す（Ｓ１２２ｔ）。
【００５３】
全てのa=1,2,3,4とi=0,1,…,p-1において（Ｓ１２２ｄ，Ｓ１２２ｅ，Ｓ１２２ｒ，Ｓ１２２ｓ）、
(i) move[a][i]=1、かつ、next[a][i]=-1のとき、move[a][i]を0に更新する（Ｓ１２２ｆ，Ｓ１２２ｇ、Ｓ１２２ｈ）。
(ii)また、move[a][i]＝０のとき、next[a][j]=iとなるjについて、move[a][j]を0に更新する（Ｓ１２２ｍ〜Ｓ１２２ｑ）。
【００５４】
以上の繰り返し更新は、ロボットiの行動aの進行方向において隣接する位置に障害物がある際に、ロボットiが行動aについて非可動であり（Ｓ１２２ｈ）、その進行方向の逆に接しているロボットjが行動aについて非可動であることを設定するものである（Ｓ１２２ｏ，Ｓ１２２ｐ）。move[a][i]の値が一つも更新されなくなるまで繰り返し更新（Ｓ１２２ｔ）を行うことにより、障害物に接しているロボットの背後に接している全てのロボットが行動a（障害物を押す方向に移動する）について非可動であることを設定する。
【００５５】
例えば、図９において、a=1の場合、まず、(X,Y)=(4,1)に位置するロボットは、行動aの進行方向において隣接する位置に障害物が存在するため、行動aについて非可動に設定する（Ｓ１２２ｈ）。さらに、(X,Y)=(4,1)に位置するロボットに、行動aの進行方向の逆に接している、(X,Y)=(3,1)に位置するロボットについても行動aについて非可動に設定する（Ｓ１２２ｐ）。更新処理が行われたため、処理Ｓ１２２ｄ〜Ｓ１２２ｓを繰り返す。一回目の繰り返し処理で、(X,Y)=(2,1)に位置するロボットについても行動aについて非可動に設定する（Ｓ１２２ｐ）。二回目の繰り返し処理ではmove[a][i]の値が一つも更新されないため、処理を終了する。
【００５６】
＜移動方向設定部１２３＞
移動方向設定部１２３は、あるロボットｉが、ある方向の隣接する位置に移動するという行動aを実行した場合の価値関数の値Q(s,a)が、静止するという行動を実行した場合の価値関数の値Q(s,0)よりも大きくなる場合に、ロボットｉから行動ａにより移動する方向において連続して隣接する全ての他のロボットについて、行動aを実行した場合に得られる価値関数の値Q(s,a)が、静止するという行動を実行した場合に得られる価値関数の値Q(s,0)よりも小さいことを理由として、行動aが非可動と設定されている場合には、行動aが可動となるように制御する（Ｓ１２３）。
【００５７】
例えば、以下の処理を行う。図１０及び図１１は移動方向設定部１２３の処理フローの例を示す。
【００５８】
全てのa=1,2,3,4とi=0,1,…,p-1において（Ｓ１２３ａ，Ｓ１２３ｂ，Ｓ１２３ｈ，Ｓ１２３ｉ）、s←（Xr[i],Yr[i]）とするとき、
(i)ロボットiの位置がG内にあるときは、Q(s,a)の値に関わらず、move[a][i]の値の更新は行わない（ｓ１２３ｃ）。
(ii)ロボットiの位置がG外にあり（Ｓ１２３ｃ）、Q(s,a)がQ(s,0)より小さくかつmove[a][i]=1のとき（Ｓ１２３ｆ）、move[a][i]を2に更新する（Ｓ１２３ｅ）。
【００５９】
以上の処理は、一度目標位置矩形集合のG内に入ったロボットiがGの外に出ることが許されないということは、next[a][i]の値の設定と可動判定部１２２にてすでに考慮されていることと、Gの外に位置するロボットは、静止している場合よりも価値関数Qの値が小さくなる行動の選択を許されない（Ｓ１２３ｆ、Ｓ１２３ｅ）という条件の設定をしている。ここで、静止している場合よりも価値関数Qの値が小さくなる行動とは、その行動をとることによって、現在位置よりも高報酬を得られる位置までの道のりが遠のくということを示している。例えば、図２のロボットR1は、G外にあり、右に移動すると、入口位置Peが遠のくため、Q(s,1)＜Q(s,0)であり、move[1][R1]←2と設定される。
【００６０】
さらに続いて、以下の処理を行う。
【００６１】
全てのa=1,2,3,4とi=0,1,…,p-1において（Ｓ１２３ｊ，Ｓ１２３ｋ，Ｓ１２３ｕ，Ｓ１２３ｖ）、s=（Xri,Yri）とするとき、
ロボットiの位置がG外にあり（Ｓ１２３ｌ）、Q(s,a)がQ(s,0)以上の値のときで、かつmove[a][i]=1のとき（Ｓ１２３ｎ）、
変数ipushedの初期値をiとして（Ｓ１２３ｏ）、以下の処理を、next[a][ipushed]の値がpでない間繰り返す（Ｓ１２３ｐ）。
ipushedの値にnext[a][ipushed]の値を設定する（Ｓ１２３ｑ）。
move[a][ipushed]=2ならば（Ｓ１２３ｒ）、move[a][ipushed]を1に更新する（Ｓ１２３ｓ）。
【００６２】
以上の処理は、行動aによって可動となっているロボットiが移動する際に、障害物にさえぎられる以外の理由で非可動となっているロボットipushedが（Ｓ１２３ｒ）、ロボットiに押される形で、行動aの方向に移動することを設定するものである（Ｓ１２３ｓ）。この処理は条件(4)「各ロボット同士の選択する行動の違いによる衝突に伴う、群れの移動の停滞を避ける。」を維持するためのものであり、ロボットipushedが、行動aによって高報酬を得るには不利な移動を強いられる場合でも、行動aによる移動が好都合なロボットiの移動を邪魔せずに受け入れることを示している。
【００６３】
例えば、a=1のとき、図２のロボットR2は、右に移動すると、入口位置Peが近づくため、Q(s,1)≧Q(s,0)であり、右方向で隣接するロボットR1は前述の通り、move[1][R1]←2と設定されていると考えられるため、move[1][R1]を1に更新する。
【００６４】
＜接続判定部１２４＞
接続判定部１２４は、隣接状態判定部１２１による判定結果,connect[n][i]を用いて、仮にあるロボットｉが行動aによりある方向に移動したときに、行動aにより移動する方向と直交する方向において隣接するロボットとの接続状態を維持するか否かを判定し、維持しない場合、ロボットｉは行動aにより移動する方向と直交する方向において隣接するロボットに対して相対移動不可能であると設定し、ロボットｉが行動aについて非可動である場合、ロボットｉに行動aにより移動する方向及びその反対方向において隣接するロボットが行動aについて非可動となるように制御し、ロボットｉが行動aについて非可動である場合であって、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットが、行動aにより移動する方向に相対移動不可能である場合には、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットが行動aについて非可動となるように制御する（Ｓ１２４）。
【００６５】
例えば、以下の処理を行う。図１２及び図１３は接続判定部１２４の処理フローの例を示す。
【００６６】
接続判定部１２４では、変数movable_plus[a][i],movable_minus[a][i]を使用し、非可動なロボットに接するロボットの可動性の判定を行う。
【００６７】
movable_plus[a][i]は、X軸Y軸のうち、行動aにより移動する方向に直交する軸の正の側でロボットiが接するロボットとの間の可動性を示す変数であり、１の場合は、接するロボットに対して行動aの方向の相対移動が可能であることを示す。０の場合は接するロボットに対して行動aの方向の相対移動が不可能であることを示す。
【００６８】
movable_minus[a][i]は、X軸Y軸のうち、行動ａにより移動する方向に直交する軸の負の側でロボットiが接するロボットとの間の可動性を示す変数であり、１の場合は、接するロボットに対して行動aの方向の相対移動が可能であることを示す。０の場合は接するロボットに対して行動aの方向の相対移動が不可能であることを示す。
【００６９】
一連の処理のはじめとして、まず、以下の処理によりあるロボットｉが行動aによりある方向に移動したときに、接続状態を維持するか否かを判定する。
【００７０】
全てのa=1,2,3,4とi=0,1,…,p-1において（Ｓ１２４ａ、Ｓ１２４ｂ、Ｓ１２４ｆ、Ｓ１２４ｇ）、接続状態を維持するか否かを判定し（Ｓ１２４ｃ）、維持する場合には、movable_plus[a][i]←1またはmovable_minus[a][i]←1とし（Ｓ１２４ｄ）、維持しない場合には、movable_plus[a][i]←0及びmovable_minus[a][i]←0とする（Ｓ１２４ｅ）。行動aにより移動する方向に直交する方向においてロボットiに隣接する他のロボットが仮に不可動であり、かつ、ロボットiが行動aにより移動する方向に移動したとして、接続状態を維持することができる場合にmovable_plus[a][i]←1またはmovable_minus[a][i]←1としている。なお、ロボットiに隣接する他のロボットが可動であれば、行動aにより同じ方向に移動するため、当然、移動前にロボットiと隣接する他のロボットは、移動後においてもロボットiと隣接し、接続状態を維持することができる。例えば、(i)行動aにより移動する方向に直交する方向に、行動aによる移動の前後において、ロボットiに隣接する他の不可動のロボットが存在する場合、または、(ii)行動aにより移動する方向に直交する方向に、行動aによる移動の前において、ロボットiに隣接する他の不可動のロボットが存在し、かつ、行動aにより移動する方向の反対方向に、行動aによる移動の前において、ロボットiに隣接する他の可動のロボットが存在する場合に、接続状態を維持することができる。例えば、図７において、「０」の位置のロボットiが右に移動しようとするとき、(i)「４」「８」の位置に不可動のロボットが存在する場合、または、(ii)「４」の位置に不可動のロボットが存在し、かつ、「３」の位置に可動のロボットが存在する場合、移動後においても接続状態を維持することができる。
【００７１】
よって、全てのa=1,2,3,4とi=0,1,…,p-1において、
(1-i)a=1かつ、move[a][i]=1かつ、-1<connect[8][i]<pかつ-1<connect[4][i]<pのとき、movable_minus[a][i]←１に設定する。
(1-ii)a=1かつ、move[a][i]=1かつ、-1<connect[3][i]<pかつ-1<connect[4][i]<pかつmove[a][connect[3][i]]=1のとき、movable_minus[a][i]←１に設定する。
(1-iii)a=1かつ、move[a][i]=1かつ、-1<connect[2][i]<pかつ、-1<connect[5][i]<pのとき、movable_plus[a][i]←１に設定する。
(1-iv)a=1かつ、move[a][i]=1かつ、-1<connect[3][i]<pかつ、-1<connect[2][i]<pかつ、move[a][connect[3][i]]=1のとき、movable_plus[a][i]←１に設定する。
(2-i)a=2かつ、move[a][i]=1かつ、-1<connect[6][i]<pかつ、-1<connect[3][i]<pのとき、movable_minus[a][i]←１に設定する。
(2-ii)a=2かつ、move[a][i]=1かつ、-1<connect[3][i]<pかつ、-1<connect[4][i]<pかつ、move[a][connect[4][i]]=1のとき、movable_minus[a][i]←1に設定する。
(2-iii)a=2かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[5][i]<pのとき、movable_plus[a][i]←1に設定する。
(2-iv)a=2かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[4][i]<pかつ、move[a][connect[4][i]]=1のとき、movable_plus[a][i]←1に設定する。
(3-i)a=3かつ、move[a][i]=1かつ、-1<connect[7][i]<pかつ、-1<connect[4][i]<pのとき、movable_minus[a][i]←1に設定する。
(3-ii)a=3かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[4][i]<pかつ、move[a][connect[1][i]]=1のとき、movable_minus[a][i]←1に設定する。
(3-iii)a=3かつ、move[a][i]=1かつ、-1<connect[2][i]<pかつ、-1<connect[6][i]<pのとき、movable_plus[a][i]←1に設定する。
(3-iv)a=3かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[2][i]<pかつ、move[a][connect[1][i]]=1のとき、movable_plus[a][i]←1に設定する。
(4-i)a=4かつ、move[a][i]=1かつ、-1<connect[3][i]<pかつ、-1<connect[7][i]<pのとき、movable_minus[a][i]←1に設定する。
(4-ii)a=4かつ、move[a][i]=1かつ、-1<connect[3][i]<pかつ、-1<connect[2][i]<pかつ、move[a][connect[2][i]]=1のとき、movable_minus[a][i]←1に設定する。
(4-iii)a=4かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[8][i]<pのとき、movable_plus[a][i]←1に設定する。
(4-iv)a=4かつ、move[a][i]=1かつ、-1<connect[1][i]<pかつ、-1<connect[2][i]<pかつ、move[a][connect[2][i]]=1のとき、movable_plus[a][i]←1に設定する。
(5)上記条件以外の場合、movable_plus[a][i]←0、movable_minus[a][i]←0に設定する。
【００７２】
以上の処理は、例えば、右方向への移動について、ロボットiの下方向と右下方向に隣接するロボットが存在する場合と、ロボットiの下方向と左方向に隣接するロボットが存在する場合において、ロボットiは、下方向のロボットに対して相対移動が可能であることを示す。これは、下方向のロボットがもし不可動であった場合でも、ロボットiは右方向に可動であることを示す。
【００７３】
続いて、以下の処理を、move[a][i]の値が一つも更新されなくなるまで繰り返す（Ｓ１２４ｐ）。
【００７４】
全てのa=1,2,3,4とi=0,1,…,p-1において（Ｓ１２４ｈ、Ｓ１２４ｉ、Ｓ１２４ｎ、Ｓ１２４ｏ）、ロボットｉが行動aについて非可動であるか否かを判定し（Ｓ１２４ｊ）、非可動である場合、ロボットｉが行動aにより移動する方向及びその反対方向においてロボットｉに隣接するロボット（=connect[a][i]、connect[a-1][i]）が行動aについて非可動となるように制御する（Ｓ１２４ｋ）。つまり、move[a][connect[a][i]]←0、move[a][connect[a-1][i]]←0とする。なお、a-1は行動aの逆方向に１格子だけ移動するという行動を表す。aとa-1の関係の一例は以下のようになる。
a=0のとき、a-1=0
a=1のとき、a-1=3
a=2のとき、a-1=4
a=3のとき、a-1=1
a=4のとき、a-1=2
【００７５】
例えば、図１４Ａにおいて、(X,Y)=(4,3)に位置するロボットがa=1（右方向に１格子分移動する）に対して非可動の場合、まず、行動aにより移動する方向及びその反対方向において(X,Y)=(4,3)に位置するロボットｉに隣接する、(X,Y)=(5,3)に位置するロボットと(X,Y)=(3,3)に位置するロボットをa=1に対して非可動に設定する。更新処理が行われたため、処理Ｓ１２４ｈ〜Ｓ１２４ｏを繰り返す。一回目の繰り返し処理で、(X,Y)=(3,3)に位置するロボットに隣接する(X,Y)=(2,3)に位置するロボットについても行動aについて非可動に設定する。二回目の繰り返し処理では、move[a][i]の値が一つも更新されないため、処理を終了する。
【００７６】
さらに、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットｊが、行動aにより移動する方向に相対移動不可能であるか否かを判定し（Ｓ１２４ｌ）、相対移動不可能である場合には、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットｊが行動aについて非可動となるように制御する（Ｓ１２４ｍ）。
【００７７】
例えば、図１４Ｂにおいて、(X,Y)=(3,2)に位置するロボットがa=1に対して非可動の場合、まず、行動aにより移動する方向と直交する方向において、(X,Y)=(3,2)に位置するロボットｉに隣接する、(X,Y)=(3,3)に位置するロボットが、行動aにより移動する方向（ここでは右）に相対移動不可能であるか否かを判定する。ここで、(X,Y)=(3,3)に位置するロボットは、(X,Y)=(3,2)に位置するロボットが仮に不可動であった場合、接続状態を維持できないため、相対移動不可能（movable_minus[a][i]=0）であると考えられる。この場合、(X,Y)=(3,3)に位置するロボットをa=1に対して非可動に設定する。更新処理が行われたため、処理Ｓ１２４ｈ〜Ｓ１２４ｏを繰り返す。一回目の繰り返し処理で、(X,Y)=(3,3)に位置するロボットに隣接する(X,Y)=(3,4)に位置するロボットについても行動aについて非可動に設定する。二回目の繰り返し処理では、move[a][i]の値が一つも更新されないため、処理を終了する。
【００７８】
例えば、全てのa=1,2,3,4とi=0,1,…,p-1において、move[a][i]=１でないロボットiについて（つまりmove[a][i]=0や、move[a][i]=2）、
(1-i)a=1かつ、-1<connect[2][i]<pかつ、movable_minus[a][connect[2][i]]=0かつmove[a][connect[2][i]]=1のとき、move[a][connect[2][i]]←0に更新する。
(1-ii)a=1かつ、-1<connect[4][i]<pかつ、movable_plus[a][connect[4][i]]=0かつmove[a][connect[4][i]]=1のとき、move[a][connect[4][i]]←0に更新する。
(1-iii)a=1かつ、-1<connect[3][i]<pかつ、move[a][connect[3][i]]=1のとき、move[a][connect[3][i]]←0に更新する。
(1-vi)a=1かつ、-1<connect[1][i]<pかつ、move[a][connect[1][i]]=1のとき、move[a][connect[1][i]]←0に更新する。
(2-i)a=2かつ、-1<connect[1][i]<pかつ、movable_minus[a][connect[1][i]]=0かつmove[a][connect[1][i]]=1のとき、move[a][connect[1][i]]←0に更新する。
(2-ii)a=2かつ、-1<connect[3][i]<pかつ、movable_plus[a][connect[3][i]]=0かつmove[a][connect[3][i]]=1のとき、move[a][connect[3][i]]←0に更新する。
(2-iii)a=2かつ、-1<connect[2][i]<pかつ、move[a][connect[2][i]]=1のとき、move[a][connect[2][i]]←0に更新する。
(2-vi)a=2かつ、-1<connect[4][i]<pかつ、move[a][connect[4][i]]=1のとき、move[a][connect[4][i]]←0に更新する。
(3-i)a=3かつ、-1<connect[2][i]<pかつ、movable_minus[a][connect[2][i]]=0かつmove[a][connect[2][i]]=1のとき、move[a][connect[2][i]]←0に更新する。
(3-ii)a=3かつ、-1<connect[4][i]<pかつ、movable_plus[a][connect[4][i]]=0かつmove[a][connect[4][i]]=1のとき、move[a][connect[4][i]]←0に更新する。
(3-iii)a=3かつ、-1<connect[3][i]<pかつ、move[a][connect[3][i]]=1のとき、move[a][connect[3][i]]←0に更新する。
(3-vi)a=3かつ、-1<connect[1][i]<pかつ、move[a][connect[1][i]]=1のとき、move[a][connect[1][i]]←0に更新する。
(4-i)a=4かつ、-1<connect[1][i]<pかつ、movable_minus[a][connect[1][i]]=0かつmove[a][connect[1][i]]=1のとき、move[a][connect[1][i]]←0に更新する。
(4-ii)a=4かつ、-1<connect[3][i]<pかつ、movable_plus[a][connect[3][i]]=0かつmove[a][connect[3][i]]=1のとき、move[a][connect[3][i]]←0に更新する。
(4-iii)a=4かつ、-1<connect[2][i]<pかつ、move[a][connect[2][i]]=1のとき、move[a][connect[2][i]]←0に更新する。
(4-vi)a=4かつ、-1<connect[4][i]<pかつ、move[a][connect[4][i]]=1のとき、move[a][connect[4][i]]←0に更新する。
【００７９】
以上の処理は、すでに非可動であると判定されたロボットに隣接するロボットの可動判定を、movable_minus変数と、movable_plus変数の値で示された相対的可動性に従って行っていることを示す。接続判定部１２４の処理は条件(2)「各ロボットの隣り合う位置（上下左右）に必ず、他のロボットが存在していなければならない。」、条件(3)「隣り合うロボット同士がなす群れは、一つでなければならない。」を維持するための処理である。
【００８０】
以上の行動選択部１２０に含まれる隣接状態判定部１２１、可動判定部１２２、移動方向設定部１２３、接続判定部１２４の処理が済んだあとで、各ロボットiのmove[a][i]変数が１の場合は、そのロボットが行動aによって移動可能であることを示す。
【００８１】
＜位置更新部１２５＞
位置更新部１２５は、まず、ロボット全体に指示される行動値a_allを決定する。決定の方法はランダムな方法か、もしくは、各行動aの値について、各ロボットiのQ（s,a）の値がQ(s,0)以上であるロボットの数の合計Sum(a)を計算し、Sum(a)の値に比例した確率でa_allの値を選択してもよい。また、縦方向の移動の行動(a=2,4)と横方向の移動（a=1,3）を交互にa_allの値として選択することとし、縦方向の行動を選ぶ際の上下のどちらの行動を選ぶか、もしくは横方向の行動を選ぶ際の右左どちらの行動を選ぶかについては、Sum(a)の値に比例した確率で、a_allの値を選択する方法でもよい。位置更新部１２５は、a_allの値が決定した後は、各ロボットiに対して、move[a_all][i]の値が１の場合だけ、行動a_allに従った移動をするように制御信号を出力する。位置更新部１２５は、move[a_all][i]の値が１以外の場合は、ロボットiに対して制御信号を出力しない、または、静止するように制御信号を出力する。
【００８２】
位置更新部１２５は、各i=0,1,…,p-1について、i番目のロボットの現在の位置（Xr[i],Yr[i]）において、行動値a_allに対応する行動、または静止するという行動を実行した場合のロボットの移動後（行動後）の位置（Xr'[i],Yr'[i]）を計算し、計算された（Xr'[i],Yr'[i]）で記憶部１４０に格納されたi番目のロボットの位置を更新する（Ｓ１２５）。言い換えれば、位置更新部１２５は、選択された行動a_allに基づいて、ロボットが行動した場合に想定される位置（以下、「想定位置」ともいう）を計算し、ロボットの位置を更新し記憶部１４０に格納する。
【００８３】
さらに、各ロボットｉにおいて、制御信号に従って行動を実行した後に、隣接状態判定部１２１が隣接状態を判定する（Ｓ１２１−２）。各ロボットｉは、判定結果を通信部１５０を介して行動制御システム１００に出力し、行動制御システム１００は判定結果を記憶部１４０に格納する。
【００８４】
なお、ロボットが移動するように制御信号を出力したとしても、何らかのトラブル（感知できなかった障害物の存在や、機器の故障等）により、制御信号通りに移動できるとは限らない。一方、静止するように制御されたロボットの位置は、制御信号を出力する前と変わらない。よって、静止するように制御されたロボットの位置を基準として、隣接状態判定部１２１による判定結果を用いて、移動するように制御されたロボットの、実際に行動した後の位置（以下「行動後位置」ともいう）（Xr"[i],Yr"[i]）を求めることができる。
【００８５】
＜位置判定部１２６＞
位置判定部１２６は、前述の通り、隣接状態判定部１２１による判定結果を用いて、行動後位置を求め、行動後位置（Xr"[i],Yr"[i]）と想定位置（Xr'[i],Yr'[i]）とが一致するか否かを判定する（Ｓ１２６）。なお、一致しない場合には、移動するように制御されたロボットが何らかのトラブルにより、制御信号通りに移動できなかったと考えられる。この場合、行動後位置（Xr"[i],Yr"[i]）と想定位置（Xr'[i],Yr'[i]）との少なくとも一方を補正すればよい。補正方法としては様々な手法が考えられる。例えば、全てのロボットに対して、制御前の位置に戻るように指示し、行動後位置（Xr"[i],Yr"[i]）を補正してもよいし、想定位置（Xr'[i],Yr'[i]）を行動後位置（Xr"[i],Yr"[i]）に合わせて補正してもよい。
【００８６】
以上に述べた処理を毎時刻ステップごとに行う。
【００８７】
各時刻ステップごとに、すべてのロボットがG内にあるかどうかを判定し（Ｓ１２７）、すべてのロットがG内にあるときは、任務を終了する。そうでないときは、任務を継続する。
【００８８】
例えば、図示しない目標位置到達判定部において、各i=0,1,…,p-1について、位置判定部１２６から出力された行動後位置（Xr"[i],Yr"[i]）∈Gであるか否かを判定し、全てのiについて（Xr"[i],Yr"[i]）∈Gである場合には、任務を終了する。少なくとも１つ以上のiについて（Xr"[i],Yr"[i]）∈Gを満たさない場合には、行動選択部１２０を再度実行するよう制御する。
【００８９】
＜効果＞
このような構成により、一台のロボットに必要な分だけのマルコフ状態空間を用意し、それを用いて動的計画法を利用して各位置でのロボットの行動方策を計算し、その行動方策を利用することで、ロボットに任意の矩形隊列形状と、任務環境内の任意の障害物形状に対応した、ロボット同士が接した状態を維持したうえでの多数ロボットのための隊列形成アルゴリズムを獲得することができる。すなわち、ロボット数に依存せずにロボット一台分の計画計算負荷での自己位置座標定義型隊列形成アルゴリズム獲得ができる。また、静止しているロボットに対する相対的な位置を判定することで、絶対的な位置を取得することができるため、付加的な位置計測用の装備を必要としない。
【００９０】
＜変形例＞
入力部１６０を介して入力される初期位置(Xr0[i],Yr0[i])が、実際にロボットが配置されている位置と一致するという前提の場合には、Ｓ１２１−１における隣接状態判定部１２１の処理を省略してもよい。その場合、行動制御システム１００は、各ロボットｉから判定結果next[n][i]を受信せずとも初期位置(Xr0[i],Yr0[i])から計算により隣接状態を取得することができる。
【００９１】
本実施形態では、各格子（マス）は、正方形であるが、他の形状であってもよい。格子は左右方向及び上下方向に連続して配置される。また、各格子は左右方向で他の二つの格子と隣接し、上下方向で他の二つの格子と隣接する。言い換えると、各格子は、ロボットの移動できる方向と同じ方向においてのみ、他の格子と隣接する。この条件を満たせば、各格子はどのような形状であってもよい。また、「直交」とは、厳密に「垂直に交わること」を意味しなくともよく、例えば、図１５のように、各格子は、菱形であってもよく、各格子が他の二つの格子と隣接する方向の一方を上下方向とし、他方を左右方向とすればよく、このとき、上下方向と左右方向とは直交するものとする。
【００９２】
別の言い方をすると、制御対象物は、二次元平面上の、第一方向（例えば右方向）、第一方向に対して平行でない方向である第二方向（例えば上方向）、第一方向に対して反対方向である第三方向（例えば左方向）、第二方向に対して反対方向である第四方向（例えば下方向）に移動可能であり、一回の行動制御により、現在いる領域（格子、マス）から、現在いる領域に対して、第一方向、第二方向、第三方向、第四方向において隣接する領域の何れかに移動するように制御される。この場合、目標位置の集合は、第一方向に平行な二つの辺と第二方向に平行な二つの辺からなる平行四辺形を成す。また、この場合、ロボットの２次元平面上の、第一方向において隣接する位置を第一位置、第二方向において隣接する位置を第二位置、第三方向において隣接する位置を第三位置、第四方向において隣接する位置を第四位置、第一位置に第二方向において隣接する位置を第五位置、第二位置に第三方向において隣接する位置を第六位置、第三位置に第四方向において隣接する位置を第七位置、第四位置に第一方向において隣接する位置を第八位置と呼んでもよい。例えば第一〜第八位置は、それぞれ図７の「１」〜「８」の位置に対応する。
【００９３】
可動判定部１２２では、図８のＳ１２２ｂ，Ｓ１２２ｃの処理を行わず、予め移動を行わないロボットを決めておいてもよい。例えば、図１６Ａのようにp個の初期位置(Xr0[i],Xr0[i])及びp個の目標位置(Xre[ｉ],Yre[i])の集合Gが設定されている場合、つまり、p個の目標位置(Xre[ｉ],Yre[i])の集合Gの中にp個の初期位置(Xr0[i],Xr0[i])の一部が含まれている場合には、その一部に位置するロボットを移動を行わないロボットとすることができる。また、初期位置の個数と目標位置の個数は同じでなくともよい。例えば、図１６Ｂのように初期位置の個数をq、目標位置の個数をpとし、q>pの場合、予め移動を行わないロボットを決めておいても（例えば図１６Ｂの初期位置の範囲の中で最も右下のロボット）、q個のロボットの内のp個のロボットを目標位置の集合Gに移動させ任務を終了することができる。
【００９４】
＜第二実施形態＞
第一実施形態と異なる部分を中心に説明する。
【００９５】
図６は第二実施形態に係る行動制御システムの処理フローの例を示す。
【００９６】
本実施形態では、行動制御システムは、p台のロボットi上に実装される。そして各ロボットｉは、図５に示すように、行動選択部１２０と、記憶部１４０と、通信部１５０と、入力部１６０とを含む。なお、価値関数Qは、p台のロボットiで同じものを用いればいいため、動作計画部１１０は必ずしも必要としない。
【００９７】
行動選択部１２０は、隣接状態判定部１２１と、可動判定部１２２と、移動方向設定部１２３と、接続判定部１２４と、位置更新部１２５と、位置判定部１２６と、制御対象物特定部２２８とを含む。
【００９８】
以下、あるロボットｉの処理について説明する。残りp-1台のロボットにおいて同様の処理が行われる。
【００９９】
記憶部１４０、通信部１５０及び入力部１６０の構成は第一実施形態と同様である。ただし、入力部１６０には、ロボットiの初期位置(Xr0[i],Xr0[i])及びp個の目標位置(Xre[ｉ],Yre[i])の集合G={(Xre[0],Yre[0]),(Xre[1],Yre[1]),…,(Xre[p-1],Yre[p-1])}が入力され、記憶部１４０に記憶される。
【０１００】
なお、記憶部１４０に、各ロボットiが、自身が可動であるか非可動であるかを示す変数move[a][i]を格納しておく。さらに、記憶部１４０に、各ロボットiの周囲に他のロボットがいるかどうか、障害物があるかどうかを示す変数next[n][i](n=1,2,3,4),connect[n][i](n=1,2,3,4,5,6,7,8)を格納しておく。
【０１０１】
なお、本実施形態では、初期位置としてp台のロボットの初期位置、変数move[a][i]及び変数connect[n][i]、next[n][i]を記憶するのではなく、ロボットｉ自身の初期位置、変数move[a][i]及び変数connect[n][i]、next[n][i]のみ（１台分）を記憶すればよい。
【０１０２】
＜行動選択部１２０＞
行動選択部１２０は、記憶部１４０から価値関数Qを取り出す。以下に述べるのは、ロボット動作開始後の各時刻ステップにおける行動選択の際に行われる処理であり、行動選択部１２０で行われる。
【０１０３】
行動選択部１２０は、価値関数Qを用いて、１回の行動制御により、少なくとも１つのロボットが静止し、残りのロボット全てが同じ方向に移動するように制御する（Ｓ１２０）。ただし、行動選択部１２０は、複数のロボット全てが常に接続状態を維持し、かつ、１つの群れを成すように制御する。
【０１０４】
＜隣接状態判定部１２１＞
隣接状態判定部１２１は、ロボットｉの２次元平面上の上下左右の隣接する位置に、障害物または他のロボットが存在するか否かを判定し、ロボットの２次元平面上の右上、左上、左下、右下の隣接する位置に他のロボットが存在するか否かを判定し（Ｓ１２１−１），判定結果connect[n][i]、next[n][i]を記憶部１４０に格納する。また、隣接状態判定部１２１は、ロボットが目標隊列エリアG内に存在するときに、ロボットの２次元平面上の上下左右の隣接する位置のマスが、目標隊列エリアGに含まれるか否かを判定し（Ｓ１２１−１）、判定結果を記憶部１４０に格納する。
【０１０５】
＜可動判定部１２２＞
可動判定部１２２は、あるロボットiの２次元平面上の上下左右の隣接する位置に、障害物が存在するときに、そのロボットiが障害物が存在する方向に移動しないように制御し、さらに、そのロボットiが障害物が存在する方向とは反対方向において連続して隣接する全ての他のロボットiが障害物が存在する方向に移動しないように制御する（Ｓ１２２）。また、可動判定部１２２は、行動aによりロボットｉがG内からG外へ移動しないように制御し、さらに、そのロボットiがGの境界線が存在する方向とは反対方向において連続して隣接する全ての他のロボットiが境界線が存在する方向に移動しないように制御する（Ｓ１２２）。例えば、ロボットiは、以下の通りにmove[a][i]を更新する。図１７は可動判定部１２２の処理フローの例を示す。
【０１０６】
まず、制御対象物特定部２２８は、p台のロボットの中から一つのロボットを特定する（図６のＳ２２８）。例えば、p台のロボットは、それぞれ乱数を取得し、その乱数が所定の値と一致するときに、その一致する乱数を取得したロボットが特定されたものとする。一致する乱数を取得したロボットは、通信部１５０を介して、他のp-1台のロボットに、自らが特定されたことを伝達する。なお、予めp台のロボットの中から一つのロボットを特定しておいた場合には、制御対象物特定部２２８における処理を省略してもよい。
【０１０７】
ロボットｉの可動判定部１２２は、ロボットｉが制御対象物特定部２２８で特定されたロボットの場合、全てのa=1,2,3,4において、move[a][i]の値を0とする（図１７のＳ１２２ａ、Ｓ１２２ｂ）。
【０１０８】
特定されたロボットではない場合、全てのa=1,2,3,4において、move[a][i]の値を1とする（図１７のＳ１２２ａ、Ｓ１２２ｃ）。
【０１０９】
特定されたロボットではない場合、さらに、全てのa=1,2,3,4において（Ｓ１２２ｄ，Ｓ１２２ｉ）、(i)move[a][i]=1、かつ、next[a][i]=-1のとき、move[a][i]を0に更新する（Ｓ１２２ｅ，Ｓ１２２ｆ，S１２２ｇ）。さらに、-1<next[a-1][i]<pのとき（行動aにより移動する方向と逆の方向の隣接する位置に他のロボットが存在するとき）、通信部１５０を介して自らがmove[a][i]を0に更新したことをロボットnext[a-1][i]に伝達する（Ｓ１２２ｈ）。
【０１１０】
特定されたロボットではない場合、さらに、全てのa=1,2,3,4において（Ｓ１２２ｊ，Ｓ１２２ｎ）、ロボットｉは、ロボットnext[a][i]からmove[a][next[a][i]]を0に更新したことを受け取ったとき、move[a][i]を0に更新する（Ｓ１２２ｋ，Ｓ１２２ｌ）。さらに、-1<next[a-1][i]<pのとき（行動aにより移動する方向と逆の方向の隣接する位置に他のロボットが存在するとき）、通信部１５０を介して自らがmove[a][i]を0に更新したことをロボットnext[a-1][i]に伝達する（Ｓ１２２ｍ）。所定の時間（障害物と隣接するロボットから、障害物が存在する方向とは反対方向において連続して隣接する最後尾のロボットに「move[a][i]を0に更新」したことを伝達するのに十分な時間）が経過するまで、Ｓ１２２ｊ〜Ｓ１２２ｎを繰り返す（Ｓ１２２ｏ）。
【０１１１】
このような構成により、各ロボットが障害物の存在を検知し、障害物発見の際に、対応する行動の方向と逆に接するロボットに、障害物の発見を伝達することができる。
【０１１２】
＜移動方向設定部１２３＞
移動方向設定部１２３は、あるロボットｉが、ある方向の隣接する位置に移動するという行動aを実行した場合に得られる価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる価値関数の値Ｑ(s,0)よりも大きくなる場合に、ロボットｉから行動ａにより移動する方向において連続して隣接する全ての他のロボットについて、行動aを実行した場合に得られる価値関数の値Ｑ(s,a)が、静止するという行動を実行した場合に得られる価値関数の値Ｑ(s,0)よりも小さいことを理由として、行動aが非可動と設定されている場合には、行動aが可動となるように制御する（Ｓ１２３）。
【０１１３】
まず、ロボットｉの移動方向設定部１２３は、図１０のＳ１２３ｂ〜Ｓ１２３ｈを行い、所定の条件を満たすときに、move[a][i]を２に更新する（Ｓ１２３ｅ）。
【０１１４】
さらに続いて、以下の処理を行う（図１８参照）。
【０１１５】
全てのa=1,2,3,4において（Ｓ１２３ｋ，Ｓ１２３ｕ）、s=（Xri,Yri）とするとき、
(i)ロボットiの位置がG内にあるときは、move[a][i]の値の更新の指示は送信しない。
(ii)ロボットiの位置がG外にあり（Ｓ１２３ｌ）、Q(s,a)がQ(s,0)以上値のときで、かつmove[a][i]=1のとき（Ｓ１２３ｎ）、
行動ａにより移動する方向において隣接するロボットnext[a][i]が存在する場合（-1<next[a][i]<pを満たす場合）、そのロボットnext[a][i]に対し、move[a][next[a][i]]=2ならば（Ｓ１２３ｑ）、move[a][next[a][i]]を1に更新するように指示を送信する（Ｓ１２３ｒ）。
【０１１６】
また、全てのa=1,2,3,4において（Ｓ１２３ｖ，Ｓ１２３ｙ）、行動ａにより移動する方向に対して反対方向において隣接するロボットnext[a-1][i]が存在する場合（-1<next[a-1][i]<pを満たす場合）、かつ、そのロボットnext[a-1][i]から「move[a][i]=2ならば、move[a][i]を1に更新するように」との指示を受け取り、move[a][i]=2の場合（ｓ１２３ｗ）、move[a][i]を1に更新する（ｓ１２３ｘ）。所定の時間が経過するまで、処理Ｓ１２３ｖ〜Ｓ１２３ｙを繰り返す（Ｓ１２３ｚ）。
【０１１７】
このような構成により、あるロボットが、行動aによって高報酬を得るには不利な移動を強いられる場合でも、行動aによる移動が好都合なロボットの移動を邪魔せずに受け入れることを示している。
【０１１８】
＜接続判定部１２４＞
接続判定部１２４は、隣接状態判定部１２１による判定結果connect[n][i]を用いて、仮にあるロボットｉが行動aによりある方向に移動したときに、行動aにより移動する方向と直交する方向において隣接するロボットに対して接続状態を維持するか否かを判定し、維持しない場合、ロボットｉは行動aにより移動する方向と直交する方向において隣接するロボットに対して相対移動不可能であると設定し、ロボットｉが行動aについて非可動である場合、ロボットｉに行動aにより移動する方向及びその反対方向において隣接するロボットが行動aについて非可動となるように制御し、ロボットｉが行動aについて非可動である場合であって、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットが、行動aにより移動する方向に相対移動不可能である場合には、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットが行動aについて非可動となるように制御する（Ｓ１２４）。
【０１１９】
まず、ロボットｉの接続判定部１２４は、図１２のＳ１２４ｂ〜Ｓ１２４ｆを行い、変数movable_plus[a][i],movable_minus[a][i]を設定する（Ｓ１２４ｄ、Ｓ１２４ｅ）。
【０１２０】
続いて、以下の処理を行う（図１９参照）。
【０１２１】
全てのa=1,2,3,4において（Ｓ１２４ｉ、Ｓ１２４ｎ）、ロボットｉが行動aについて非可動であるか否かを判定し（Ｓ１２４ｊ）、非可動である場合、ロボットｉが行動aにより移動する方向及びその反対方向においてロボットｉに隣接するロボット（=connect[a][i]、connect[a-1][i]）に対して、それぞれmove[a][connect[a][i]]及びmove[a][connect[a-1][i]]を0に更新するように指示を送信する（Ｓ１２４ｋ）。
【０１２２】
さらに、ロボットｉが非可動である場合、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットｊに対して、行動aにより移動する方向に相対移動不可能である場合には、move[a][j]を0に更新するように条件付きの指示を送信する（Ｓ１２４ｌ）。
【０１２３】
また、全てのa=1,2,3,4において（Ｓ１２４ｏ，Ｓ１２４ｓ）、ロボットconnect[a][i]またはロボットconnect[a-1][i]から「move[a][i]=1ならば、move[a][i]を0に更新するように」との指示を受け取った場合（Ｓ１２４ｐ）、move[a][i]を0に更新する（Ｓ１２４ｑ）。また、行動aにより移動する方向と直交する方向においてロボットｉに隣接するロボットｊから、「行動aにより移動する方向に相対移動不可能である場合には、move[a][i]を0に更新するように」との指示を受け取り、ロボットjが行動aにより移動する方向と直交する方向の軸の正側に位置するならば変数movable_plus[a][i],負側に位置するならばmovable_minus[a][i]が0の場合に、move[a][i]を0に更新する（Ｓ１２４ｒ）。
【０１２４】
所定の時間が経過するまで、処理Ｓ１２４ｏ〜Ｓ１２４ｓを繰り返す（Ｓ１２４ｔ）。
【０１２５】
このような構成により、周囲のロボットと連携して、接続状態を維持することができる。
【０１２６】
＜位置更新部１２５＞
位置更新部１２５は、まず、ロボット全体に指示される行動値a_allを決定する。決定の方法はランダムな方法か、もしくは、各行動aの値について、各ロボットiのQ（s,a）の値がQ(s,0)以上であるロボットの数の合計Sum(a)を計算し、Sum(a)の値に比例した確率でa_allの値を選択してもよい。例えば、制御対象物特定部２２８で特定されたロボット（図６のＳ２２８）の位置更新部１２５が、行動値a_allを決定する。その場合であって、Sum(a)を計算する場合、各ロボットからQ（s,a）の値がQ(s,0)以上であるか否かの判定結果を受信すればよい。
【０１２７】
特定されたロボットの位置更新部１２５は、行動値a_allを各ロボットiに送信する。行動値a_allを受け取った各ロボットの位置更新部１２５は、現在の位置（Xr[i],Yr[i]）において、行動値a_allに対応する行動、または静止するという行動を実行した場合のロボットiの移動後（行動後）の位置（Xr'[i],Yr'[i]）を計算し、計算された（Xr'[i],Yr'[i]）で記憶部１４０に格納された現在の位置を更新する（Ｓ１２５）。言い換えれば、位置更新部１２５は、選択された行動a_allに基づいて、ロボットiが行動した場合に想定される位置（以下、「想定位置」ともいう）を計算し、ロボットの位置を更新し記憶部１４０に格納する。
【０１２８】
さらに、各ロボットｉにおいて、制御信号に従って行動を実行した後に、隣接状態判定部１２１が隣接状態を判定し（Ｓ１２１−２）、判定結果next[n][i]を記憶部１４０に格納する。
【０１２９】
＜位置判定部１２６＞
各ロボットｉの位置判定部１２６は、隣接状態判定部１２１による判定結果を用いて、行動後位置を求め、行動後位置（Xr"[i],Yr"[i]）と想定位置（Xr'[i],Yr'[i]）とが一致するか否かを判定する（Ｓ１２６）。
【０１３０】
以上に述べた処理を毎時刻ステップ（行動制御）ごとに行う。
【０１３１】
各時刻ステップごとに、すべてのロボットがG内にあるかどうかを判定し（Ｓ１２７）、すべてのロットがG内にあるときは、任務を終了する。そうでないときは、任務を継続する。
【０１３２】
＜効果＞
このような構成により、第一実施形態と同様の効果を得ることができる。さらに、本実施形態では、各処理を各ロボットに分散することができる。例えば、一部のロボットにトラブルか生じ、動作しなくなったとしても、残りのロボットにおいて任務を終了することもできる。
【０１３３】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１３４】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１３５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１３６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１３７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３８】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2016009354.tif 000003
【図２】
2016009354.tif 000004
【図３】
2016009354.tif 000005
【図４】
2016009354.tif 000006
【図５】
2016009354.tif 000007
【図６】
2016009354.tif 000008
【図８】
2016009354.tif 000009
【図９】
2016009354.tif 000010
【図１０】
2016009354.tif 000011
【図１１】
2016009354.tif 000012
【図１２】
2016009354.tif 000013
【図１３】
2016009354.tif 000014
【図１４】
2016009354.tif 000015
【図１５】
2016009354.tif 000016
【図１６】
2016009354.tif 000017
【図１７】
2016009354.tif 000018
【図１８】
2016009354.tif 000019
【図１９】
2016009354.tif 000020
【図７】
2016009354.tif 000021