(57)【要約】      （修正有）【課題】任意形状の隊列制御を可能にする手法であって、計算負荷が従来よりも低い行動制御技術を提供する。【解決手段】一台のロボットに必要な分だけのマルコフ状態空間を用意し、それを用いて強化学習手法を利用してロボットに学習を行わせる。これにより、任意の隊列形状と、任務環境内の任意の障害物形状に対応した、多数ロボットのための隊列形成アルゴリズムを獲得することができる。すなわち、ロボット数に依存せずにロボット一台分の学習計算負荷での隊列形成アルゴリズム獲得ができる。また、その際に、包摂構造を使用した行動選択、及び、目標位置におけるボイド制御を行う。【選択図】図２
2015201068.tif 000002
【特許請求の範囲】
【請求項１】
複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う行動制御装置であって、
上記制御対象物は、制御対象物がその制御対象物の現在の位置Lにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて行動制御が行われるとして、
(1)各上記制御対象物が上記目標位置に位置するか判定する位置判定部と、(2)上記各制御対象物が上記目標位置に位置しないと判定された場合には、制御対象物が上記入口位置に向かうことを理想的な状態として上記各制御対象物の現在の位置に基づいて上記価値関数を更新し、上記各制御対象物が移動可能な位置の中で上記更新後の価値関数の値が最も大きい位置に移動する行動を上記各制御対象物の行動として決定する目的領域外行動決定部と、(3)上記各制御対象物が上記目標位置に位置すると判定された場合には、制御対象物の移動に伴ってその制御対象物と位置が入れ替わる仮想的な存在であるボイドが上記入口位置に向かうことを理想的な状態としてボイドの現在の位置に基づいて上記価値関数を更新し、上記各制御対象物の現在の位置Lに移動可能な位置であるボイド位置の中で上記更新後の価値関数の値を最大にする行動が上記位置Lに移動する行動である位置を候補ボイド位置とし、その最大にする行動に対応する上記更新後の価値関数の値を候補ボイドQ関数値として、上記候補ボイド位置の中で上記各制御対象物が移動可能な位置であり候補ボイドQ関数値が最小である位置に移動する行動を上記各制御対象物の行動として決定する目的領域内行動決定部と、を含む行動割当部と、
上記決定された行動に基づいて上記各制御対象物の位置を更新する位置更新部と、
上記行動割当部と位置更新部との処理を繰り返し行うように制御する制御部と、
を含む行動制御装置。
【請求項２】
複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う行動制御方法であって、
上記制御対象物は、制御対象物がその制御対象物の現在の位置Lにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて行動制御が行われるとして、
(1)位置判定部が、各上記制御対象物が上記目標位置に位置するか判定する位置判定ステップと、(2) 目的領域外行動決定部が、上記各制御対象物が上記目標位置に位置しないと判定された場合には、制御対象物が上記入口位置に向かうことを理想的な状態として上記各制御対象物の現在の位置に基づいて上記価値関数を更新し、上記各制御対象物が移動可能な位置の中で上記更新後の価値関数の値が最も大きい位置に移動する行動を上記各制御対象物の行動として決定する目的領域外行動決定ステップと、(3)目的領域内行動決定部が、上記各制御対象物が上記目標位置に位置すると判定された場合には、制御対象物の移動に伴ってその制御対象物と位置が入れ替わる仮想的な存在であるボイドが上記入口位置に向かうことを理想的な状態としてボイドの現在の位置に基づいて上記価値関数を更新し、上記各制御対象物の現在の位置Lに移動可能な位置であるボイド位置の中で上記更新後の価値関数の値を最大にする行動が上記位置Lに移動する行動である位置を候補ボイド位置とし、その最大にする行動に対応する上記更新後の価値関数の値を候補ボイドQ関数値として、上記候補ボイド位置の中で上記各制御対象物が移動可能な位置であり候補ボイドQ関数値が最小である位置に移動する行動を上記各制御対象物の行動として決定する目的領域内行動決定ステップと、を含む行動割当ステップと、
位置更新部が、上記決定された行動に基づいて上記各制御対象物の位置を更新する位置更新ステップと、
制御部が、上記行動割当部と位置更新部との処理を繰り返し行うように制御する制御ステップと、
を含む行動制御方法。
【請求項３】
請求項１の行動制御装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の制御対象物の行動を制御する技術に関する。例えば、複数のロボットを、開始位置における隊列形成状態から協調して移動させ、障害物を回避させ、目標位置で隊列形成をさせるための各ロボットの行動計画を求めるロボット協調制御技術に関する。
【背景技術】
【０００２】
近年、多数の自律移動ロボットを効率的に制御にするための研究が活発に行われている。その任務内容は、人の入れない箇所の監視、物品の搬送などさまざまであるが、多数のロボットの協調動作による隊列形成を効率的に行わせるための技術が求められており盛んに研究が行われている（例えば、非特許文献１参照。）。多数のロボットによる効率的な隊列形成を実現するには、それぞれのロボットの配置、動作順序などを事前に計画することが重要である。このような計画においては、当然ながら、複数のロボットが動作する実環境における障害物の存在や経路の形状なども十分に考慮しなければならない。
【０００３】
このような計画計算を行うための効果的な手法の一つとして、マルコフ決定過程における動的計画法や強化学習の手法があり、さまざまな研究が行われている（例えば、非特許文献２参照。）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の手法では、流体力学的な特性をロボット動作に組み込む手法を用いて群ロボットの動作を制御しており、低い計算負荷での制御を可能にしている利点があるが、任意の形状の隊列形成をすることができるとは限らない。
【０００６】
また、非特許文献２の手法のように、マルコフ決定過程における動的計画法や強化学習を使用してこのような計画を行おうとすると、単体のロボットを使用する場合に比べて複数のロボットを使用する場合には、その計算に要する時間や計算機の記憶容量がロボットの数に対して指数関数的に増大してしまう。その主たる原因となるのが、探索計算のためのマルコフ状態空間内の状態数の莫大な増加である。非特許文献２では、検証された強化学習の手法では、ロボット数の増加に伴い、指数関数的に計算負荷が増加するという、マルコフ状態空間内の爆発問題への解決策は示されていない。
【０００７】
このように、任意形状の隊列制御を可能にする手法であって、計算負荷が低い手法は未だ実現できていない。
【０００８】
このような現状に鑑みて、この発明は、任意形状の隊列制御を可能にする手法であって、計算負荷が従来よりも低い行動制御装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
この発明の一態様による行動制御装置は、複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行う行動制御装置であって、制御対象物は、制御対象物がその制御対象物の現在の位置Lにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて行動制御が行われるとして、(1)各制御対象物が目標位置に位置するか判定する位置判定部と、(2)各制御対象物が目標位置に位置しないと判定された場合には、制御対象物が入口位置に向かうことを理想的な状態として各制御対象物の現在の位置に基づいて価値関数を更新し、各制御対象物が移動可能な位置の中で更新後の価値関数の値が最も大きい位置に移動する行動を各制御対象物の行動として決定する目的領域外行動決定部と、(3)各制御対象物が目標位置に位置すると判定された場合には、制御対象物の移動に伴ってその制御対象物と位置が入れ替わる仮想的な存在であるボイドが入口位置に向かうことを理想的な状態としてボイドの現在の位置に基づいて価値関数を更新し、各制御対象物の現在の位置Lに移動可能な位置であるボイド位置の中で更新後の価値関数の値を最大にする行動が位置Lに移動する行動である位置を候補ボイド位置とし、その最大にする行動に対応する更新後の価値関数の値を候補ボイドQ関数値として、候補ボイド位置の中で各制御対象物が移動可能な位置であり候補ボイドQ関数値が最小である位置に移動する行動を各制御対象物の行動として決定する目的領域内行動決定部と、を含む行動割当部と、決定された行動に基づいて各制御対象物の位置を更新する位置更新部と、行動割当部と位置更新部との処理を繰り返し行うように制御する制御部と、を含む。
【発明の効果】
【００１０】
任意形状の隊列制御が可能となり、計算負荷を従来よりも低くすることができる。
【図面の簡単な説明】
【００１１】
【図１】行動制御装置の例を説明するためのブロック図。
【図２】学習部の例を説明するためのブロック図。
【図３】第ｉ割当部の例を説明するためのブロック図。
【図４】目標領域外行動決定部の例を説明するためのブロック図。
【図５】目標領域内行動決定部の例を説明するためのブロック図。
【図６】スケジューリング部の例を説明するためのブロック図。
【図７】この発明の解決する問題を説明するための図。
【図８】包摂構造による行動選択を説明するための図。
【図９】行動制御方法の学習ステップの例を説明するためのフローチャート。
【図１０】行動制御方法の行動スケジュールステップの例を説明するためのフローチャート。
【発明を実施するための形態】
【００１２】
［理論的背景］
まず、行動制御装置及び方法の理論的背景について説明する。以下、行動制御の対象である制御対象物が、ロボットである場合を例に挙げて説明するが、制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００１３】
多数のロボットが協調して開始位置における隊列形成状態から移動を行い、目標位置での隊列形成を行う任務は、例えば図７に例示するような壁で区切られた部屋においての開始位置から目標位置まで複数のロボットの移動によって実現するものである。
【００１４】
任務を行うロボットは、N台（例えばN≧50）であり、各ロボットは、二次元平面におけるX軸方向及びY軸方向のそれぞれに移動可能とする。すなわち、この例では、各ロボットは、図７の紙面に対して上下左右の四方向に移動可能とする。図７の各格子は、それぞれのロボットの位置を示すものである。各格子にはロボットは一台しか存在することができない。それぞれのロボットは、移動しようとする方向に障害物か他のロボットがある場合には、静止をするものと仮定する。
【００１５】
図７において、Rが記載された格子はロボットが存在する位置を示し、Oが記載された格子は障害物が存在する位置を示し、Fが記載された格子は目標位置を示す。また、太線の破線で囲まれた領域は開始位置を示し、太線で囲まれた領域は後述する入口位置を示す。このように、図７においては、ロボットの開始位置での隊列形状は略長方形であり、目標位置での隊列形状は略星形である。
【００１６】
それぞれのロボットi（iはロボット番号を表す）の初期位置を（Xr0[i],Yr0[i]）とし、目標位置を（Xre[i],Yre[i]）とするとき、初期位置に配置されたロボットが、目標位置まで移動するための行動計画を求める問題を考える。
【００１７】
このような問題に対して単純にマルコフ状態遷移モデルを適用しようとする場合、マルコフ状態空間は、iをロボット番号としたとき、ロボットiの位置（Xr[i],Yr[i]）、ロボットiの行動a[i]によって構成される。各状態（ロボットの位置と行動）は離散値で表現される。部屋をX,Yの直交座標系からなる２次元平面で表すと、X軸、Y軸をそれぞれ離散化表現した値により各位置を表現する。つまり、図７のように部屋（２次元平面）は格子で区切られ、各格子が各位置に対応する。また、各格子において、障害物の「ある／なし」が予め設定されている。上述の通り、図７では、障害物のある格子をOで示している。
【００１８】
また、この例では、制御対象物である行動主体は部屋に配置されている各ロボットとなる。ロボットi（iはロボット番号）の行動a[i]∈D[i]は、静止、上下左右方向への１格子分の移動の計５種類のうちの何れかを取る。すなわち、D[ｉ]∈{0,1,2,3,4}として、各行動は例えば以下のように定義される。
0: 静止
1: 二次元平面上で右方向に１格子だけ移動する
2: 二次元平面上で上方向に１格子だけ移動する
3: 二次元平面上で左方向に１格子だけ移動する
4: 二次元平面上で下方向に１格子だけ移動する
このような任務環境におけるマルコフ状態空間は、ロボット数×２の次元数の状態を持ち、かつ選択可能な行動数は、ロボットの行動（＝５通り）のロボット数乗だけ存在する。例えば、ロボット数が５０で、部屋の縦横方向の格子数がそれぞれ２０であるとすれば状態数は２０の100乗個にもなり、探索計算に要する資源の量は膨大なものとなる。さらにロボット数が１台増えるごとに、その状態数は400倍増加していくことになり、複数ロボットを使用する場合の大きな問題となっている。
【００１９】
そこで、この発明では、このような状態空間の爆発をさけるために、学習に使用するマルコフ状態空間を、一台分のロボットの状態変数のみで構成することにする。すなわち、状態変数及び行動変数を以下のように定義する。
【００２０】
状態変数L=（Xr,Yr），行動変数a∈{0,1,2,3,4}
N台あるすべてのロボットは、この状態変数を引数とした１個の価値関数Q(L,a)を共有する。すなわち、各時刻ステップにおける価値関数Q(L,a)の更新は、N台の各ロボットが同じ価値関数を各々の経験によって更新する（すなわち、一時刻ステップでN回の更新を行う）。更新式は以下の通りである。
【００２１】
【数１】
2015201068.tif 000003
【００２２】
ここで、式(1)におけるαは学習率と呼ばれる予め定められた定数であり０＜α＜１である。また、式(1)における←は右辺の値で左辺の値を更新することを意味する。
【００２３】
i番目のロボットについて、式(1)及び式(2)の右辺のLにi番目のロボットの位置L[i]を代入し、式(1)及び式(2)のaにi番目のロボットの行動変数a[i]を代入して、式(1)及び式(2)を実行することで価値関数及び方策を更新する。これを、各i=1,2,…,Nについて繰り返す。
【００２４】
行動選択時にも、１個の価値関数Q(L,a)によって導かれる方策関数π(L)を使用して各ロボットが行動選択を行う。言い換えれば、例えばロボットである制御対象物は、制御対象物がその制御対象物の現在の位置Lにおいて各行動aを取ったときの適切さを表す１個の価値関数に基づいて行動制御が行われるとする。これにより、ロボットの数がどんなに増えても、学習に使用する状態空間の状態数がロボット一台分の状態空間の状態数と同じとなり、状態空間の大きさがロボット数に依存しないことになる。
【００２５】
なお、各ロボットは、それぞれの位置を計測することができ、また隣の位置に他のロボットが存在しているか否か、隣の位置に障害物があるか否かを知ることができるものとする。
【００２６】
このような１個の価値関数Q(L,a)を使用して学習を行った場合に起こる問題を以下に述べる。例えば学習において、各目標位置においてロボットに高い報酬を与えるものとする。まず、Q(L,a)においては、１個のロボットが開始位置からどのような行動を選択していくことで、最短時刻ステップ数で目標位置に到達できるかが記述されているのであるから、π(L)に従う各ロボットは、例えば目標位置へ向かう途中の障害物を回避するときに、障害物の角にあたる同じ位置を通ろうとする傾向がある。すなわち、同じ経路に多数のロボットが殺到し、文字通りの渋滞を引き起こしてしまう。また、目標位置に早めについたロボットがその位置に静止し、後から目標位置に到着しようとするロボットの道をふさいでしまうことも起こりうる。その結果、すべてのロボットが適切に目標位置に到達することが保証できない。それをさけるために、各ロボットの開始位置を考量して、早めに目標位置に到達するロボットには遠めの目標位置を割り振るなどの処理をする方法もあるが、そのためには、各ロボットの位置をロボットの台数分だけマルコフ状態空間に組み込むことが必要となってしまい、ロボット台数が多い場合には、状態空間の深刻な増加を引き起こす。
【００２７】
そこで、このようなことを引き起こさないために、主に２つの方法を提案する。１つ目は包摂構造を使用した行動選択手法であり、２つ目は目標位置におけるボイド制御である。
【００２８】
図８に、包摂構造を使用した行動選択手法の例の概念図を示す。図８の〇の中にｓが描かれたモジュール（以下、包摂モジュールとする）は、包摂構造における重要なキーパーツである。包摂モジュールは、上位のモジュールから入力された信号を、下位のモジュールからの信号入力がない限りはそのまま出力する下位のモジュールからの入力があった場合は、上位モジュールからの入力を無視し、下位モジュールの入力を出力する。
【００２９】
各層のモジュールは、Qxth(x=1,2,3,4)モジュールとStopperモジュールで構成される。最下層のQxthモジュールはQ1stモジュール、第二層はQ2ndモジュール、第三層はQ3rd、第四層はQ4thモジュールである。最上層はStayComモジュールで構成される。
【００３０】
Q1stモジュールは、現在のロボットの位置(xr[i],yr[i])を入力値として受け取り、L=(xr[i],yr[i])においてQ(L,a)の値を最大とするaの値をロボットiの行動a[i]の候補として出力する。同様に、Q2ndモジュールは、現在のロボットの位置(xri,yri)を入力値として受け取り、L=(xr[i],yr[i])においてQ(s,a)の値を2番目に大きな値とするaの値をロボットiの行動a[i]の候補として出力する。さらに、Q3rdモジュールは、現在のロボットの位置(xr[i],yr[i])を入力値として受け取り、L=(xr[i],yr[i])においてQ(L,a)の値を3番目に大きな値とするaの値をロボットiの行動a[i]の候補として出力する。同様に、Q4thモジュールは、現在のロボットの位置(xr[i],yr[i])を入力値として受け取り、L=(xr[i],yr[i])においてQ(L,a)の値を4番目に大きな値とするaの値をロボットiの行動a[i]の候補として出力する。
【００３１】
なお、各Qxthモジュールは、出力する行動の候補としてa[i]=0（静止）を含めないものとする。Stopperモジュールは、位置(xr[i],yr[i])に存在するロボットの隣の位置(xr[i]+1,yr[i])、(xr[i],yr[i]+1)、(xr[i]-1,yr[i])、(xr[i],yr[i]-1)に他のロボットが存在しているかどうかをチェックし、入力された値の行動によってロボットが移動する先の位置に、他のロボットが存在している場合には、何も行動値を出力しない。そうでない場合は入力された行動値をそのまま出力する。StayComモジュールは、常に静止行動a[i]=0を出力する。
【００３２】
ここで述べた行動選択方法は、例えば、位置ＬにおいてQ値を最大にする行動をロボットが選択した場合に、その行動によって移動する先の格子にすでに他のロボットが存在してしまっているときに、ロボットに動作をさせずに静止させるのではなく、最適ではないにしても、次に望ましい行動を選択して、他のロボットに占拠されていない格子に移動する行動をロボットに指示するものである。
【００３３】
これは、ちょうど流体が障害物にぶつかってもそこで静止せずに、障害物をよけつつも主流の方向から遠くずれない方向に流れていく性質を、ロボットに与えるものである。
【００３４】
なお、図８のモジュールが４層（第１〜第４）のレイヤで構成されているのは、この例では静止(a=0)以外でロボットの取りうる行動が４種類(a=1,2,3,4)であるとしているためである。一般には、行動の種類がM個（静止を含む）あれば、図８のモジュールはM-1個のレイヤになる。
【００３５】
次にボイド制御の原理について述べる。まず、各ロボットの目標位置をここに厳密に割り振ることをせず、目標位置全体の集合を、目標隊列エリアGと定義する。すなわち、
（Xre[i],Yre[i]）∈G  …(3)
として、各ロボットはG内の全ての全ての位置を自由に目標位置とすることができるものとする。つまり、Gをちょうど流体を注ぐ器のようなものとして扱う。すなわち、各ロボットは、Gの境界上にあるどの位置からもGに入ることが可能であるが、一度G内に入ったロボットは、Gを出る行動をとることができないものとする。また、強化学習時における報酬の設定については、Gの境界上に一点だけ入口の点Peを設定し、ロボットがPeからG内に入ったときのみ高報酬であるr=1を与え、それ以外の経験については、すべてr=0を与えるものとする。Peの位置はGの内部であって、Gの境界上であればどこでも構わないが、ロボットの開始位置から近い位置を選ぶのがロボットの動作をスムーズにするうえで効果的である。Peの位置を入口位置と呼ぶ。
【００３６】
G内においては、ロボットの経験をそのまま価値関数Q(L,a)の更新に用いるのではなく、ロボットの行動に伴って動く“ボイド”の動作として扱い、Q(L,a)の更新に用いることにする。ボイドとは、ロボットが位置Lから、L’に遷移したときに同時に、L’からLに遷移する空隙のことである。すなわち、一台のロボットがGの内部に入ったときは、同時に一つのボイドがGの外部に出ていくことになる。Gの入口点としてPeを設定したために、ロボットはPeからGに入る傾向を持つことになるが、同時にボイドは、Peを経由してGから出ていくことになる。すなわち、ボイドがPeからGの外に出ていくときに高報酬を与えられることになる。すると、そうしたボイドの動きを実現するためのロボットの動作は、必然的にPeからG内に入ったのちにPeから離れた点を目指して、G内に分散していく動作となる。以下、そのための、Q値計算と行動選択方法について述べる。G内において、ロボットが位置Lから、L’に遷移したときに、Q値は以下の式(4)により更新される。
【００３７】
【数２】
2015201068.tif 000004
【００３８】
Qmax(L)は位置Lにおいて式(1)で定義されるQ関数の最大値である。すなわち、Qmax(L)=maxaQ(L,a)また、γは、学習率と呼ばれるあらかじめ値の定められた定数であり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
式(4)は、ちょうど通常のQ学習におけるQ(L,a)の更新式である式(1)のLとL’を入れ替えて、時間の流れを逆に扱ったものに等しい。なお、Gの内と外でのQ値の不整合を避けるために、LがGの外部、L’がGの内部の場合には、Qmax(L)の値は０に設定することとする。このようにして更新されたQ値によって導かれる行動方策π（Q値を最大化する行動を返す関数）は、ボイドの最適な行動を返すものとなる。ロボットは、ボイドがそのような行動をとれるように移動を行う。
【００４０】
次にG内での行動選択について述べる。G内においてもGの外部と同様に、包摂構造による行動選択を行うが、Qxthモジュールの動作がGの内部では異なる。G内部では、Qxthモジュールは、まずロボット位置Lの隣の位置(xr[i]+1,yr[i])、(xr[i],yr[i]+1)、(xr[i]-1,yr[i])、(xr[i],yr[i]-1)にある各ボイドについてQ値を最大化する行動が、ボイドを現在のロボット位置に向かわせるようになっているボイドを、候補ボイドとして複数選択する。つづいて、それらの候補ボイドの中から、Qmaxの値をx番目に小さくするものをターゲットボイドとして一つ選択し、選択したターゲットボイドにロボットを向かわせる行動の値を出力する。このようにすることで、ロボットを動かして適切にボイドをPeの位置に誘導し、常に後からGに入ってこようとするロボットに入口を空いた状態に確保することができる。
【００４１】
なお、Qxthモジュールの設計についてはいくつかオプションがあり、例えば、候補ボイドの中からターゲットボイドを選択する手法としてとして、候補ボイドの中からQmaxの値をx番目に大きくするものをターゲットボイドとして一つ選択する手法や、候補ボイドにロボットを向かわせる行動の中から行動番号の小さいものをロボットの行動として出力するなどの色々な方法があり得る。
【００４２】
なお、Gの入口位置を一点に設定しているが、包摂構造による行動選択の効用で、もしPeがロボットによって占拠されている場合には、Pe以外のPe近傍の点からロボットがGに入るようにロボットの行動が制御されるので、Gに入ろうとするロボットがPeの一点に集中して渋滞を起こすことはない。
【００４３】
［行動制御装置及び方法］
図を参照して、行動制御装置及び方法の例について説明する。この行動制御装置及び方法は、複数の制御対象物を所定の入口位置を含む目標位置の集合に移動させるための行動制御を行うものである。
【００４４】
行動制御装置は、図１に示すように、学習部１、記憶部２及びスケジューリング部３を例えば備えている。
【００４５】
学習部１は、図２に示すように、入力部１１、行動割当部１２、位置更新部１３及び制御部１４を例えば備えている。
【００４６】
スケジューリング部３は、図６に示すように、初期状態入力部３１、行動割当部３２、位置更新部３３、目標位置到達判定部３４を例えば備えている。
【００４７】
以下では、制御の対象となる制御対象物が、ロボットである場合を例に挙げて説明する。もちろん、制御対象物は、制御の対象となり得るものであれば、ロボット以外であってもよい。
【００４８】
まず、行動制御装置の学習部１による学習ステップの処理について説明する。学習ステップの処理の流れの例を、図９に示す。
【００４９】
＜入力部１１＞
入力部１１には、N台のロボットのそれぞれの初期位置(xr0[i],yr0[i])及び目標位置(Xre[i],Yre[i])が入力される。ここで、i=1,2,…,Nとする。N個の目標位置の集合は、G={(Xre[1],Yre[1]),(Xre[2],Yre[2]),…,(Xre[N],Yre[N])}として記憶部２に記憶される。
【００５０】
N台のロボットのそれぞれについて、入力された初期位置の情報を用いて、i番目のロボットの初期位置L[i]=(xr0[i], yr0[i])を設定し、i番目のロボットの初期位置を記憶部２に記憶する。
【００５１】
なお、目標位置は、所定の入口位置を含むとする。この入口位置についての情報も、入力部１１から入力され、記憶部２に記憶されるとする。
【００５２】
＜記憶部２＞
記憶部２には、位置L及びa∈{0,1,2,3,4}の組み合わせのそれぞれについてのＱ関数Q(L,a)、各位置Lについての方策π(L)及びQmax(L)の初期値が記憶されているとする。Lの取りうる範囲は、対象となる二次元平面上の領域内の全ての座標である。これらの初期値はランダムな値を設定すればよい。ただし、Lが障害物位置と合致する場合は、Q(L,a)=0と設定してもよい。π(L)、Qmax(L)についても各Lに関するQ関数の初期値Q(L,a)のうちの最大値を設定すればよい。
【００５３】
各位置Lの報酬r(L)についても、記憶部２に記憶されているとする。各位置Lの報酬r(L)についての情報は、例えば入力部１１から入力される。
【００５４】
＜行動割当部１２＞
行動割当部１２による行動割当処理は、各ロボットについて順次実行される。行動割当部１２は、第１割当部１２−１，第i割当部１２−ｉ，…，第N割当部１２−Ｎを例えば備えている。
【００５５】
i=1,2,…,Nとして、i番目のロボットについての行動割当処理は、第i割当部１２−ｉが例えば行うとする。第i割当部１２−ｉの構成の例を図３に示す。
【００５６】
≪位置判定部１２−ｉ−１≫
位置判定部１２−ｉ−１は、記憶部２からi番目のロボットの位置(xr[i],yr[i])を読み込み、読み込んだ位置(xr[i],yr[i])が目的位置の集合G内に含まれるか否かを判定する。言い換えれば、位置判定部１２−ｉ−１は、ロボットが目標位置に位置するか判定する（ステップＡ１）。
【００５７】
位置判定部１２−ｉ−１は、位置(xr[i],yr[i])が目的位置の集合G内に含まれない場合は目的領域外行動決定部１２−ｉ−２が次の処理を実行し、(xr[i],yr[i])が目的位置の集合G内に含まれる場合は目的領域内行動決定部１２−ｉ−３が次の処理を実行するよう制御する。
【００５８】
また、位置判定部１２−ｉ−１は、位置(xr[i],yr[i])が目的位置の集合G内に含まれない場合は、目的領域外行動決定部１２−ｉ−２から出力される行動値が位置更新部１３に入力され、(xr[i],yr[i])が目的位置の集合G内に含まれる場合は、目的領域内行動決定部１２−ｉ−３から出力される行動値が位置更新部１３に入力されるよう制御する。
【００５９】
≪目的領域外行動決定部１２−ｉ−２≫
目的領域外行動決定部１２−ｉ−２の構成の例を図４に示す。
【００６０】
目的領域外行動決定部１２−ｉ−２は、図８の行動選択手法に基づいて行動を決定するものである。すなわち、目的領域外行動決定部１２−ｉ−２は、ロボットが目標位置に位置しないと判定された場合には、ロボットが入口位置に向かうことを理想的な状態としてロボットの現在の位置に基づいて価値関数を更新し、ロボットが移動可能な位置の中で更新後の価値関数の値が最も大きい位置に移動する行動をロボットの行動として決定する（ステップＡ２）。
【００６１】
〔領域外Ｑ関数更新部１２−ｉ−２１〕
領域外Ｑ関数更新部１２−ｉ−２１は、１時間ステップ前のｉ番目のロボットの位置をL=(xr[i],yr[i])とし、現在のｉ番目のロボットの位置をL’=(xr’[i],yr’[i])として、記憶部２に記憶されたQ(L,a)とQmax(L’)を参照して、１時間ステップ前のロボットの行動ａについて、式(1)によりQ(L,a)を求め、求めたQ(L,a)の値で記憶部２に記憶されたQ(L,a)の値を更新する。また、領域外Ｑ関数更新部１２−ｉ−２１は、更新前のQ(L,a)の値と更新後のQ(L,a)の値を制御部１４へ出力する。
【００６２】
また、領域外Ｑ関数更新部１２−ｉ−２１は、更新されたQ(L,a)の値を用いて、式(2)により方策π(L)を求め、求めたπ(L)の値で記憶部２に記憶された方策π(L)を更新する。
【００６３】
〔第１領域外行動候補決定部１２−ｉ−２２〕
第１領域外行動候補決定部は、L=(xr[i],yr[i])として、記憶部２に記憶されたQ(L,1),Q(L,2),Q(L,3),Q(L,4)のうちの最大値をとるaの値を第１領域外行動候補値として出力する。また、最大となるQ関数の値で記憶部２に記憶されたQmax(L)の値を更新する。
【００６４】
〔第１領域外包摂制御部１２−ｉ−２３〕
第１領域外包摂制御部１２−ｉ−２３は、第１領域外行動候補決定部１２−ｉ−２２で決定された第１領域外行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか否かを判定する。
【００６５】
第１領域外包摂制御部１２−ｉ−２３は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、障害物が存在する場合には、第２領域外行動候補決定部１２−ｉ−２４が次の処理を実行するよう制御する。
【００６６】
第１領域外包摂制御部１２−ｉ−２３は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在しない場合には、第１領域外行動候補値を「行動値」として出力する。
【００６７】
〔第２領域外行動候補決定部１２−ｉ−２４〕
第２領域外行動候補決定部１２−ｉ−２４は、L=(xr[i], yr[i])として、記憶部２に記憶されたQ(L,1),Q(L,2),Q(L,3),Q(L,4)のうちの２番目に大きな値をとるaの値を第２領域外行動候補値として出力する。
【００６８】
〔第２領域外包摂制御部１２−ｉ−２５〕
第２領域外包摂制御部１２−ｉ−２５は、第２領域外行動候補決定部１２−ｉ−２４で決定された第２領域外行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか否かを判定する。
【００６９】
第２領域外包摂制御部１２−ｉ−２５は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、障害物が存在する場合には、第３領域外行動候補決定部１２−ｉ−２６が次の処理を実行するよう制御する。
【００７０】
第２領域外包摂制御部１２−ｉ−２５は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在しない場合には、第２領域外行動候補値を「行動値」として出力する。
【００７１】
〔第３領域外行動候補決定部１２−ｉ−２６〕
第３領域外行動候補決定部１２−ｉ−２６は、L=(xr[i],yr[i])として、記憶部２に記憶されたQ(L,1),Q(L,2),Q(L,3),Q(L,4)のうちの３番目に大きな値をとるaの値を第３領域外行動候補値として出力する。
【００７２】
〔第３領域外包摂制御部１２−ｉ−２７〕
第３領域外包摂制御部１２−ｉ−２７は、第３領域外行動候補決定部１２−ｉ−２６で決定された第３領域外行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか否かを判定する。
【００７３】
第３領域外包摂制御部１２−ｉ−２７は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、障害物が存在する場合には、第４領域外行動候補決定部１２−ｉ−２８が次の処理を実行するよう制御する。
【００７４】
第３領域外包摂制御部１２−ｉ−２７は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在しない場合には、第３領域外行動候補値を「行動値」として出力する。
【００７５】
〔第４領域外行動候補決定部１２−ｉ−２８〕
第４領域外行動候補決定部１２−ｉ−２８は、L=(xr[i],yr[i])として、記憶部２に記憶されたQ(L,1),Q(L,2),Q(L,3),Q(L,4)のうちの４番目に大きな値をとる（つまり、最小値をとる）aの値を第４領域外行動候補値として出力する。
【００７６】
〔第４領域外包摂制御部１２−ｉ−２９〕
第４領域外包摂制御部１２−ｉ−２９は、第４領域外行動候補決定部１２−ｉ−２８で決定された第４領域外行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか否かを判定する。
【００７７】
第４領域外包摂制御部１２−ｉ−２９は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在するか、障害物が存在する場合には、a=0 (静止)を「行動値」として出力する。
【００７８】
第４領域外包摂制御部１２−ｉ−２９は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在しない場合には、第４領域外行動候補値を「行動値」として出力する。
【００７９】
≪目的領域内行動決定部１２−ｉ−３≫
目的領域内行動決定部１２−ｉ−３の詳細構成を図５に示す。
【００８０】
目的領域内行動決定部１２−ｉ−３は目的領域外行動決定部１２−ｉ−２と同様に図８の行動選択手法に基づいて行動を決定するものである。ただし、Q関数として式(1)の代わりに式(4)を用いる点が目的領域外行動決定部１２−ｉ−２と異なる。つまり、目的領域内行動決定部１２−ｉ−３ではボイド制御も組み込んだ処理が行われる。
【００８１】
すなわち、目的領域内行動決定部１２−ｉ−３は、ロボットが目標位置に位置すると判定された場合には、ロボットの移動に伴ってそのロボットと位置が入れ替わる仮想的な存在であるボイドが入口位置に向かうことを理想的な状態としてボイドの現在の位置に基づいて価値関数を更新し、ロボットの現在の位置Lに移動可能な位置であるボイド位置の中で更新後の価値関数の値を最大にする行動が位置Lに移動する行動である位置を候補ボイド位置とし、その最大にする行動に対応する更新後の価値関数の値を候補ボイドQ関数値として、候補ボイド位置の中でロボットが移動可能な位置であり候補ボイドQ関数値が最小である位置に移動する行動をロボットの行動として決定する（ステップＡ３）。
【００８２】
〔領域内Ｑ関数更新部１２−ｉ−３１〕
領域内Ｑ関数更新部１２−ｉ−３１は、1ステップ前のi番目のロボットの位置(xr[i],yr[i])をLとし、現在のi番目のロボット位置をボイド位置L’として、記憶部２に記憶されたQ(L’,a)とQmax(L)を参照して、１ステップ前のロボットの行動からa-1を求め、式(4)によりQ(L’,a-1)を求め、求めたQ(L’,a-1)の値で記憶部２に記憶されたQ(L’,a-1)の値を更新する。
【００８３】
ここで、L’は、1ステップ前の位置L=(xr[i], yr[i])において行動aを選択したときの移動後の位置である。aとL’の関係は、例えば以下のようになる。
【００８４】
a=1であれば、L’=(xr[i]+1, yr[i])
a=2であれば、L’=(xr[i], yr[i]+1)
a=3であれば、L’=(xr[i]-1, yr[i])
a=4であれば、L’=(xr[i], yr[i]-1)
領域内Ｑ関数更新部１２−ｉ−３１は、更新前のQ(L’,a-1)と更新後のQ(L’,a-1)を制御部１４に出力する。また、このときのQ関数の最大値で、記憶部２に記憶された方策π(L’)の値を更新する。
【００８５】
〔候補ボイド集合生成部１２−ｉ−３２〕
候補ボイド集合生成部１２−ｉ−３２は以下の（１）から（３）の処理を行う。
【００８６】
（１）i番目のロボットの位置(xr[i],yr[i])に隣接する位置(xr[i]+1,yr[i])、(xr[i],yr[i]+1)、(xr[i]-1,y[ri])、(xr[i],yr[i]-1)の各々をボイド位置L’として、各位置L’において、Q(L’,a-1) [a-1=0,1,2,3,4]のうち最大値をとるQ(L’,a-1)を「候補ボイドQ関数値」として決定する。またこのときのa-1の値を「L’における候補ボイド行動」として決定する。
【００８７】
（２）上記（１）で求めた各L’における候補ボイド行動のうち、候補ボイド行動に従ってL’からボイドが移動したと仮定したときの移動後の位置がi番目のロボットの位置(xr[i], yr[i])となるL’の集合を「候補ボイド位置集合」として求める。
【００８８】
（３）上記（２）で求めた「候補ボイド位置集合」に含まれる各候補ボイド位置L’と、L’における候補ボイドQ関数値と、L’における候補ボイド行動との組からなる集合を「候補ボイド集合」として、第１領域内行動候補決定部１２−ｉ−３３に出力する。
【００８９】
〔第１領域内行動候補決定部１２−ｉ−３３〕
第１領域内行動候補決定部１２−ｉ−３３は、「候補ボイド集合」から候補ボイドQ関数値が最小となる候補ボイドQ関数値に対応する候補ボイド位置L’を「第１ターゲット位置」として決定する。
【００９０】
i番目のロボットの位置(xr[i], yr[i])から、上記（２）で決定された第１ターゲット位置へ移動する行動を第１領域内行動候補値として出力する。
【００９１】
〔第１領域内包摂制御部１２−ｉ−３４〕
第１領域内包摂制御部１２−ｉ−３４は、第１領域内行動候補決定部１２−ｉ−３３で決定された第１領域内行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部であるか否かを判定する。
【００９２】
第１領域内包摂制御部１２−ｉ−３４は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部である場合には、第２領域内行動候補決定部が次の処理を実行するよう制御する。
【００９３】
第１領域内包摂制御部１２−ｉ−３４は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在せず、かつ、位置(xr’[i],yr’[i])がGの外部でない場合には、第１領域内行動候補値を「行動値」として出力する。
【００９４】
〔第２領域内行動候補決定部１２−ｉ−３５〕
第２領域内行動候補決定部１２−ｉ−３５は、「候補ボイド集合」から候補ボイドQ関数値が２番目に小さな値をとる候補ボイドQ関数値に対応する候補ボイド位置L’を「第２ターゲット位置」として決定する。
【００９５】
i番目のロボットの位置(xr[i], yr[i])から、上記（２）で決定された第２ターゲット位置へ移動する行動を第２領域内行動候補値として出力する。
【００９６】
〔第２領域内包摂制御部１２−ｉ−３６〕
第２領域内包摂制御部１２−ｉ−３６は、第２領域内行動候補決定部１２−ｉ−３５で決定された第２領域内行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部であるか否かを判定する。
【００９７】
第２領域内包摂制御部１２−ｉ−３６は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部である場合には、第３領域内行動候補決定部１２−ｉ−３７が次の処理を実行するよう制御する。
【００９８】
第２領域内包摂制御部１２−ｉ−３６は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在せず、かつ、位置(xr’[i],yr’[i])がGの外部でない場合には、第２領域内行動候補値を「行動値」として出力する。
【００９９】
〔第３領域内行動候補決定部１２−ｉ−３７〕
第１領域内行動候補決定部１２−ｉ−３７は、「候補ボイド集合」から候補ボイドQ関数値が３番目に小さな値をとる候補ボイドQ関数値に対応する候補ボイド位置L’を「第３ターゲット位置」として決定する。
【０１００】
i番目のロボットの位置(xr[i], yr[i])から、上記（２）で決定された第３ターゲット位置へ移動する行動を第３領域内行動候補値として出力する。
【０１０１】
〔第３領域内包摂制御部１２−ｉ−３８〕
第３領域内包摂制御部１２−ｉ−３８は、第３領域内行動候補決定部１２−ｉ−３７で決定された第３領域内行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部であるか否かを判定する。
【０１０２】
第３領域内包摂制御部１２−ｉ−３８は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部である場合には、第４領域内行動候補決定部１２−ｉ−３９が次の処理を実行するよう制御する。
【０１０３】
第３領域内包摂制御部１２−ｉ−３８は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在せず、かつ、位置(xr’[i],yr’[i])がGの外部でない場合には、第３領域内行動候補値を「行動値」として出力する。
【０１０４】
〔第４領域内行動候補決定部１２−ｉ−３９〕
第４領域内行動候補決定部１２−ｉ−３９は、「候補ボイド集合」から候補ボイドQ関数値が４番目に小さな値をとる候補ボイドQ関数値に対応する候補ボイド位置L’を「第４ターゲット位置」として決定する。
【０１０５】
i番目のロボットの位置(xr[i], yr[i])から、上記（２）で決定された第４ターゲット位置へ移動する行動を第４領域内行動候補値として出力する。
【０１０６】
〔第４領域内包摂制御部１２−ｉ−３１０〕
第４領域内包摂制御部１２−ｉ−３１０は、第４領域内行動候補決定部１２−ｉ−３９で決定された第４領域内行動候補値に従ってi番目のロボットが移動すると仮定したときの移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか否かを判定する。つまり、(xr’[i],yr’[i])=(xr[j],yr[j]) (i≠j)となるjが存在するか否かを判定する。さらに、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部であるか否かを判定する。
【０１０７】
第４領域内包摂制御部１２−ｉ−３１０は、移動後の位置(xr’[i],yr’[i])に他のロボットが存在するか、位置(xr’[i],yr’[i])に障害物が存在するか、位置(xr’[i],yr’[i])がGの外部である場合には、a=0(静止)を「行動値」として出力する。
【０１０８】
第４領域内包摂制御部１２−ｉ−３１０は、移動後の位置(xr’[i],yr’[i])に他のロボット及び障害物が存在せず、かつ、位置(xr’[i],yr’[i])がGの外部でない場合には、第４領域内行動候補値を「行動値a[i]」として出力する。
【０１０９】
以上の処理により、第i割当部１２−ｉ−３１０からは、i番目のロボットが現在の位置(xr[j],yr[j])において選択する行動に対応する値である行動値a[i]∈{0,1,2,3,4}が出力される。ゆえに、行動割当部１２からは、N個のロボットがそれぞれ現在の位置において選択する行動値a[i]が出力される。
【０１１０】
＜位置更新部１３＞
位置更新部１３は、各i=1,2,…,Nについて、i番目のロボットの現在の位置(xr[j],yr[j])において、行動割当部１２から出力された行動値a[i]に対応する行動をとった場合のロボットの移動後（行動後）の位置(xr’[i],yr’[i])を計算し、計算された(xr’[i],yr’[i])で記憶部２に格納されたi番目のロボットの位置を更新する。言い換えれば、位置更新部１３は、行動割当部１２によって決定された行動に基づいて例えばロボットである制御対象物のそれぞれの位置を更新する（ステップＡ４）。更新後の位置の系列｛(xr’[1],yr’[1]), (xr’[2],yr’[2]),…, (xr’[N],yr’[N])｝は、制御部１４に入力される。
【０１１１】
＜制御部１４＞
制御部１４は、行動割当部と位置更新部との処理を繰り返し行うように制御する（ステップＡ５）。
【０１１２】
制御部１４は、所定の終了条件を満たすまで、行動割当部と位置更新部との処理を繰り返し行うように制御する。例えば、制御部１４は、目的領域外行動決定部１２−ｉ−２又は目的領域内行動決定部１２−ｉ−３から出力されたすべての更新前のQ関数と更新後のQ関数とから構成される組について、更新前Q関数の値と更新後Q関数の値の差が所定の閾値以下となるまで、行動割当部１２及び位置更新部１３の処理を実行するよう制御する。この場合の終了条件は、更新前Q関数の値と更新後Q関数の値の差が所定の閾値以下となることである。
【０１１３】
すべての更新前のQ関数と更新後のQ関数とから構成される組について、更新前Q関数の値と更新後Q関数の値の差が所定の閾値以下となったら、行動制御装置の学習部１による学習ステップの処理は終了する。
【０１１４】
次に、行動制御装置のスケジューリング部３による行動スケジュールステップの処理について説明する。以下、学習部１と異なる部分を中心に説明し、学習部１と同様の部分については重複説明を省略する。
【０１１５】
行動スケジュールステップの処理の流れの例を、図１０に示す。
【０１１６】
＜スケジューリング部３＞
スケジューリング部３は、以上の学習部１の処理により得られたＱ関数と方策を用いて、N台の実ロボットが初期位置から目的の隊列を形成するための各ロボットの行動計画を決定する。スケジューリング部の詳細構成を図６に示す。
【０１１７】
≪初期状態入力部３１≫
初期状態入力部３１には、N台のロボットのそれぞれの初期位置(xr0[i], yr0[i])[i=1,2,…,N]が入力される。
【０１１８】
≪行動割当部３２≫
行動割当部３２の処理は学習部１の行動割当部１２と同様である。i=1,2,…,N1として、第i割当部３２−ｉは、学習部１の行動割当部１２の第i割当部１２−ｉと同様である。
【０１１９】
ただし、行動割当部３２は、ここでは各iについて決定された行動a[i]を現在の時刻tにおいてi番目のロボットが選択する行動at[i]として記憶部に格納する。これにより、記憶部２には時刻tまでの各時刻でi番目のロボットが選択する行動の系列（行動系列） A[i] ={a1[i],a2[i],…,at−１[i]}が格納されることになる。
【０１２０】
また、学習部１の行動割当部１２ではa[i]を決定するだけでなく、Q関数の値と方策の値の更新も行っているが、スケジューリング部３の行動割当部３２ではQ関数の値と方策の値の更新を行う必要はない。
【０１２１】
Q関数の値の更新を行わない場合には、行動割当部３２の位置判定部３２−ｉ−１は、ロボットが目標位置に位置するか判定し（ステップＢ１）、行動割当部３２の目的領域外行動決定部３２−ｉ−２は、ロボットが目標位置に位置しないと判定された場合には、ロボットが移動可能な位置の中で価値関数の値が最も大きい位置に移動する行動をロボットの行動として決定し（ステップＢ２）、目的領域内行動決定部３２−ｉ−３は、ロボットが目標位置に位置すると判定された場合には、ロボットの現在の位置Lに移動可能な位置であるボイド位置の中で価値関数の値を最大にする行動が位置Lに移動する行動である位置を候補ボイド位置とし、その最大にする行動に対応する価値関数の値を候補ボイドQ関数値として、候補ボイド位置の中でロボットが移動可能な位置であり候補ボイドQ関数値が最小である位置に移動する行動をロボットの行動として決定する（ステップＢ３）。
【０１２２】
≪位置更新部３３≫
位置更新部３３の処理は、学習部１の位置更新部１３と同様である。すなわち、位置更新部３３は、行動割当部３２によって決定された行動に基づいて例えばロボットである制御対象物のそれぞれの位置を更新する（ステップＢ４）。
【０１２３】
≪目標位置到達判定部３４≫
目標位置到達判定部３４は、各i=1,2,…,Nについて、位置更新部３３から出力された更新後の位置(xr’[i],yr’[i])∈Gであるか否かを判定し、全てのiについて(xr’[i],yr’[i])∈Gである場合には、現在記憶部２に記憶されている行動系列 A[i] ={a1[i],a2[i],…,at−１[i], at[i]}をスケジューリング結果として出力する。少なくとも１つ以上のiについて(xr’[i],yr’[i])∈Gを満たさない場合には、行動割当部３２及び位置更新部３３を再度実行するよう制御する（ステップＢ５）。
【０１２４】
［変形例等］
目的領域外行動決定部１２−ｉ−２が４層（第１〜第４）のレイヤで構成されているのは、上記の例では静止(a=0)以外でロボットの取りうる行動が４種類(a=1,2,3,4)であるとしているためである。一般には、行動の種類がM個（静止を含む）あれば、目的領域外行動決定部１２−ｉ−２はM-1個のレイヤになる。目的領域内行動決定部１２−ｉ−３、目的領域外行動決定部３２−ｉ−１及び目的領域内行動決定部３２−ｉ−３についても同様である。
【０１２５】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１２６】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１３１】
１      学習部
２      記憶部
３      スケジューリング部
１１    入力部
１２    行動割当部
１２−ｉ−１    位置判定部
１２−ｉ−２    目的領域外行動決定部
１２−ｉ−３    目的領域内行動決定部
１３    位置更新部
１４    制御部
３１    初期状態入力部
３２    行動割当部
３２    行動割当部
３２−ｉ−１    位置判定部
３２−ｉ−２    目的領域外行動決定部
３２−ｉ−３    目的領域内行動決定部
３３    位置更新部
３４    目標位置到達判定部
【図１】
2015201068.tif 000005
【図２】
2015201068.tif 000006
【図３】
2015201068.tif 000007
【図４】
2015201068.tif 000008
【図５】
2015201068.tif 000009
【図６】
2015201068.tif 000010
【図７】
2015201068.tif 000011
【図８】
2015201068.tif 000012
【図９】
2015201068.tif 000013
【図１０】
2015201068.tif 000014