(57)【要約】【課題】複数のロボットを協調動作させて効率的に物品を搬送する任務を小さい計算負荷で計画する。【解決手段】物品移動内容計画部１０は、物品が初期位置から目標位置まで移動する最短経路点列と最短経路点列を区分する切り替え位置と物品の移動を停止させる待機位置とを求める。ロボット行動学習部４００は、物品の位置と１台の仮想ロボットの位置とを状態変数とするマルコフ状態空間において、切り替え位置と待機位置とに反しない行動をシミュレーションした結果を状態変数に代入することで押し方策と押し方策価値関数と移動方策と移動方策価値関数とを学習する。スケジューリング部５００は、移動方策価値関数と移動方策と押し方策と押し方策価値関数を用いて物品協調搬送計画を求める。【選択図】図５
2014211667.tif 000002
【特許請求の範囲】
【請求項１】
複数のロボットが協調して物品を初期位置から目標位置まで移動させるための物品協調搬送計画を求めるロボット協調搬送計画装置であって、
上記物品の位置を状態変数とするマルコフ状態空間において、上記初期位置から上記目標位置までの上記物品の移動経路を示す最短経路点列と、上記最短経路点列を１台のロボットが上記物品を移動させることのできる区間に区分する切り替え位置と、上記切り替え位置それぞれについて、当該切り替え位置へ上記物品を移動させるロボット以外のロボットが当該切り替え位置に対応するレディ位置へ到達するまで上記物品の移動を停止させる待機位置とを求める物品移動内容計画部と、
上記物品の位置と１台の仮想ロボットの位置とを状態変数とするマルコフ状態空間において、上記複数のロボットそれぞれについて、上記切り替え位置と上記待機位置とに反しない行動を割り当てた際の状態の変化をシミュレーションした結果を状態変数に代入することで、当該ロボットが上記物品を移動させるための方策である押し方策と、上記押し方策に対応する価値関数である押し方策価値関数と、当該ロボットが上記レディ位置へ移動するための方策である移動方策と、上記移動方策に対応する価値関数である移動方策価値関数とを学習するロボット行動学習部と、
時刻ごとに、上記移動方策価値関数を最大にするロボットに上記移動方策が示す行動を割り当て、上記押し方策価値関数を最大にするロボットに上記押し方策が示す行動を割り当てることで、上記物品協調搬送計画を求めるスケジューリング部と、
を含むロボット協調搬送計画装置。
【請求項２】
請求項１に記載のロボット協調搬送計画装置であって、
上記物品移動内容計画部は、
上記物品の位置を状態変数とし、上記物品の移動方向を行動変数とするマルコフ状態空間において、上記最短経路点列を求める物品起動計算部と、
上記最短経路点列に含まれる位置を定義域とする上記物品の位置と１台の仮想ロボットの位置とを状態変数とし、当該仮想ロボットの移動方向を行動変数とするマルコフ状態空間において、上記切り替え位置を求める切り替え位置計算部と、
上記最短経路点列に含まれる位置を定義域とする上記物品の位置と１台の仮想ロボットの位置とを状態変数とし、当該仮想ロボットの移動方向を行動変数とするマルコフ状態空間において、上記待機位置を求める待機位置決定部と、
を含むロボット協調搬送計画装置。
【請求項３】
請求項１または２に記載のロボット協調搬送計画装置であって、
上記ロボット行動学習部は、上記最短経路点列と上記切り替え位置と上記待機位置とに反しない行動を割り当てた際の状態の変化をシミュレーションした結果を状態変数に代入することで、上記押し方策と上記押し方策価値関数と上記移動方策と上記移動方策価値関数とを学習する
ロボット協調搬送計画装置。
【請求項４】
複数のロボットが協調して物品を初期位置から目標位置まで移動させるための物品協調搬送計画を求めるロボット協調搬送計画方法であって、
物品移動内容計画部が、上記物品の位置を状態変数とするマルコフ状態空間において、上記初期位置から上記目標位置までの上記物品の移動経路を示す最短経路点列と、上記最短経路点列を１台のロボットが上記物品を移動させることのできる区間に区分する切り替え位置と、上記切り替え位置それぞれについて、当該切り替え位置へ上記物品を移動させるロボット以外のロボットが当該切り替え位置に対応するレディ位置へ到達するまで上記物品の移動を停止させる待機位置とを求める物品移動内容計画ステップと、
ロボット行動学習部が、上記物品の位置と１台の仮想ロボットの位置とを状態変数とするマルコフ状態空間において、上記複数のロボットそれぞれについて、上記切り替え位置と上記待機位置とに反しない行動を割り当てた際の状態の変化をシミュレーションした結果を状態変数に代入することで、当該ロボットが上記物品を移動させるための方策である押し方策と、上記押し方策に対応する価値関数である押し方策価値関数と、当該ロボットが上記レディ位置へ移動するための方策である移動方策と、上記移動方策に対応する価値関数である移動方策価値関数とを学習するロボット行動学習ステップと、
スケジューリング部が、時刻ごとに、上記移動方策価値関数を最大にするロボットに上記移動方策が示す行動を割り当て、上記押し方策価値関数を最大にするロボットに上記押し方策が示す行動を割り当てることで、上記物品協調搬送計画を求めるスケジューリングステップと、
を含むロボット協調搬送計画方法。
【請求項５】
請求項１から３のいずれかに記載のロボット協調搬送計画装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数のロボットを協調動作させて物品の搬送を行うロボット協調搬送計画技術に関する。
【背景技術】
【０００２】
近年、自律移動ロボットによる物品搬送の研究が活発に行われている。搬送の対象となる物品や搬送を行うロボットの種類も様々な中、複数のロボットを協調動作させて効率的な物品搬送を行う技術が求められており盛んに研究が行われている。協調動作する複数のロボットによる効率的な物品の搬送を実現するには、複数ロボットの配置、動作順序などを事前に計画することが必須である。そのような計画においては、当然ながら、ロボットが動作する環境における障害物や経路の形状と配置などの存在も十分に考慮しなければならない。
【０００３】
そのような計画計算を行うための効果的な手法の１つとして、マルコフ決定過程における動的計画法や強化学習の手法があり、さまざまな研究が行われている。その中でも協調学習と呼ばれている手法は、任務に参加するすべてのロボットの状態や行動の変数を含む状態空間を設定し、その状態空間を使用して一度に強化学習を行うものである。必ず正解に到達することが数学的に証明されているが、その計算に要する時間や計算機の記憶容量がロボットの数に対して指数関数的に増大してしまうという問題がある。その主たる原因となる状態空間内の状態数の莫大な増加を解決する方法の１つに、例えば、動的計画法や強化学習を使用した探索計算を行うための状態空間を、階層的な構造を使用して構成する方法が考えられている（非特許文献１、非特許文献２）。
【０００４】
また、その一方で、各ロボットについて、自身のロボットの状態と行動を含むが、すべてのロボットの状態や行動の変数を必ずしも含まない状態空間を設定し、それぞれの状態空間で独立して学習を行うといった、いわば分散された状態空間を使用する分散学習の方法も提案されている（非特許文献３）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Rajbara Makar, Sridhar Mahadevan, Mohammad Ghavamzaden, “Hierarchical Multi-Agent Reinforcement Learning”, Autonomous Agents and Multi-Agent Systems, Volume 13, Issue 2, pp.197-229, September 2006.
【非特許文献２】Bernhard Hengst, “Discovering Hierarchy in Reinforcement Learning with HEXQ”, 19th International Conference on Machine Learning, pp.243-250, 2002.
【非特許文献３】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, pp.3694-3699, October 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１や非特許文献２などに記載された従来の手法は、単体のロボットを使用する場合について考慮されたものがほとんどであり、複数ロボットの使用を考慮した効果的な階層モデルの構築方法は提案されていない。つまり、複数のロボットを協調動作させて効率的な物品搬送を行うような任務に対する効果的な階層モデルの構築方法は提案されていない。また、階層的状態空間を使用しているとはいえ、問題が複雑になるほど考慮すべき状態数や階層数が増えるので、計算負荷は大きくなってしまう。
【０００７】
また、非特許文献３のような分散学習は、計算負荷は小さくて済むが、学習を適用可能な任務の内容が限られるという問題がある。例えば、複数のロボットを協調動作させて効率的な物品搬送を行うような任務では、ロボット同士の待ち合わせ動作などを必要とするが、自身以外のロボットの状態を学習時に考慮しないで学習を行う分散学習では、適切な解が得られないのは明白である。
【０００８】
このような現状を鑑みて、この発明では、複数のロボットを協調動作させて効率的な物品搬送を行うような任務に対しても適用可能であり、かつ、計算負荷の小さいロボット協調搬送計画技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、この発明のロボット協調搬送計画装置は、複数のロボットが協調して物品を初期位置から目標位置まで移動させるための物品協調搬送計画を求める。この発明のロボット協調搬送計画装置は、物品の位置を状態変数とするマルコフ状態空間において、初期位置から目標位置までの物品の移動経路を示す最短経路点列と、最短経路点列を１台のロボットが物品を移動させることのできる区間に区分する切り替え位置と、切り替え位置それぞれについて、当該切り替え位置へ物品を移動させるロボット以外のロボットが当該切り替え位置に対応するレディ位置へ到達するまで物品の移動を停止させる待機位置とを求める物品移動内容計画部と、物品の位置と１台の仮想ロボットの位置とを状態変数とするマルコフ状態空間において、複数のロボットそれぞれについて、切り替え位置と待機位置とに反しない行動を割り当てた際の状態の変化をシミュレーションした結果を状態変数に代入することで、当該ロボットが物品を移動させるための方策である押し方策と、押し方策に対応する価値関数である押し方策価値関数と、当該ロボットがレディ位置へ移動するための方策である移動方策と、移動方策に対応する価値関数である移動方策価値関数とを学習するロボット行動学習部と、時刻ごとに、移動方策価値関数を最大にするロボットに移動方策が示す行動を割り当て、押し方策価値関数を最大にするロボットに押し方策が示す行動を割り当てることで、物品協調搬送計画を求めるスケジューリング部とを含む。
【発明の効果】
【００１０】
この発明のロボット協調搬送計画技術によれば、複数ロボットによる物品搬送計画において、莫大な計算機の記憶容量と計算時間を要する協調学習の手法を使用することなく、また、分散学習の計算の不安定性も回避しながら、ロボット同士の待ち合わせ行動を含む物品搬送計画の計算を適切に行うことが可能となる。
【図面の簡単な説明】
【００１１】
【図１】複数のロボットによる物品搬送任務の環境を例示する図。
【図２】ロボットの移動方向と物品搬送可能方向を説明するための図。
【図３】搬送される物品の形状例と、物品を移動方向に移動させるための必要条件となるロボットの位置を説明するための図。
【図４】物品の移動が不可能な位置関係を例示する図。
【図５】ロボット協調搬送計画装置の機能構成を例示する図。
【図６】物品軌道計算部の機能構成を例示する図。
【図７】切り替え位置決定部の機能構成を例示する図。
【図８】待機位置決定部の機能構成を例示する図。
【図９】ロボット行動学習部の機能構成を例示する図。
【図１０】Ｑ関数・方策更新部の処理フローを例示する図。
【図１１】スケジューリング部の機能構成を例示する図。
【発明を実施するための形態】
【００１２】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１３】
［対象とする問題］
この発明が対象とする問題は、複数のロボットが協調して移動対象物である物品を初期位置から目標位置まで搬送する任務である。この問題は、例えば図１に示すような壁で区切られた部屋にある物品を、初期位置から目標位置まで複数のロボットの協調行動によって搬送するものである。任務を行うロボットは、p台（p≧２）であり、各々のロボットは、図２に示すように、物品を二次元平面におけるX-Y軸方向（この例では、図面の紙面上下左右の四方向）に押して動かすことのできるロボットであるとする。なお、各ロボットは、二次元平面におけるX-Y軸方向（この例では、図面の紙面上下左右の四方向）に移動可能とする。
【００１４】
また、図３に示すように、物品は複数の正方形のブロックが組み合わさった形状をしているものと仮定する。物品の位置は、物品を構成するブロックのうちのいずれか１つの格子位置（物品位置基準点）によって定義される。この実施形態では、図３に示すように、物品を構成するブロックのうち左下端のブロックを物品位置基準点とする。
【００１５】
このような問題設定において、物品を目標位置に適切に移動させるには、ロボット同士の協調による動作が不可欠である。また、障害物が存在しているため、どのようなタイミングで、どのロボットを「物品を押すことが可能な位置」に予め移動させておくかを正確に計画しなければならない。
【００１６】
それぞれのロボットは、移動しようとする方向に障害物や他のロボットがある場合、もしくは物品を押そうとする方向に障害物がある場合において、その方向に移動しようとした場合、もしくは物品をその方向に押そうとした場合には、静止をするものと仮定する。複数のロボットは、同一の位置に同時に存在することができないものと仮定する。つまり、学習においてはロボット同士の衝突を考慮する。
【００１７】
図１に示すように、それぞれのロボットi（iはロボット番号を表す）の初期位置を（Xr[i]0,Yr[i]0）、物品の初期位置を（Xb0,Yb0）、物品の搬送先の目標位置を（Xbe,Ybe）とするとき、この問題は、初期位置に配置されたロボットが、物品を初期位置から目標位置まで移動させるための行動計画を求めることと定義できる。
【００１８】
このような問題に対して単純にマルコフ状態遷移モデルを適用しようとする場合、マルコフ状態空間は、iをロボット番号としたとき、ロボットiの位置（Xr[i],Yr[i]）、ロボットiの行動d[i]、物品の位置（Xb,Yb）によって構成される。各状態（ロボットの位置と行動、物品の位置）は離散値で表現される。部屋をX,Yの直交座標系からなる二次元平面で表すと、X軸、Y軸をそれぞれ離散化表現した値により各位置を表現する。つまり、図１に示すように部屋（二次元平面）は格子で区切られ、各格子が各位置に対応する。また、各格子において、障害物の「あり／なし」が予め設定されている。
【００１９】
また、行動主体は部屋に配置されている各ロボットとなる。ロボットi（iはロボット番号）の行動h[i]は、静止、上下左右方向への１格子分の移動、の計５種類のうちのいずれかを取る。例えば、h[i]∈{0,1,2,3,4}として、
0: 静止
1: 二次元平面上で右方向に１格子だけ移動する
2: 二次元平面上で上方向に１格子だけ移動する
3: 二次元平面上で左方向に１格子だけ移動する
4: 二次元平面上で下方向に１格子だけ移動する
とする。
【００２０】
このような任務環境におけるマルコフ状態空間は、物品数×2＋ロボット数×2の次元数の状態を持ち、かつ選択可能な行動数は、ロボットの行動（＝５通り）のロボット数乗だけ存在する。例えば、物品数が１、ロボット数が２で、部屋の縦横方向の格子数がそれぞれ10であるとすれば状態数は10×10×10×10×10×10=1,000,000にもなり、探索計算に要する資源の量は膨大なものとなる。さらにロボット数が１台増えるごとに、その状態数は100倍増加していくことになる。つまり、このような任務環境におけるマルコフ状態空間は、ロボット数が増大するにつれて大幅に増加してしまう。
【００２１】
［実施形態の概要］
この発明では、階層的な学習と分散学習とを組み合わせることにより、分散学習法の計算負荷の低さを生かしつつも、複数のロボットの協調動作を考慮して適切な物品搬送計画を学習できるようにする。
【００２２】
この実施形態のロボット協調搬送計画装置Ａの構成を図５に示す。この発明のロボット協調搬送計画装置Ａは、物品移動内容計画部１０、ロボット行動学習部４００、スケジューリング部５００を含む。物品移動内容計画部１０は、物品軌道計算部１００、切り替え位置決定部２００、待機位置決定部３００を含む。
【００２３】
物品移動内容計画部１０では、階層的な学習を用いて、障害物を避けて初期位置から目標位置まで物品が到達するための物品の経路（以下、最短経路点列とも言う）、最短経路点列上でロボット同士の待ち合わせを必要とする位置（以下、切り替え位置とも言う）、最短経路点列上で物品を待機させる（先に次区間の物品移動を担当するロボットを通すために待機させる）位置（以下、待機位置とも言う）、を決定する。ここでは、物品の位置もしくは単機のロボット位置のみで状態空間を構成し、任務環境の地形（障害物位置、物品形状）についての知識のみから学習を行う。
【００２４】
上述の通り、物品移動内容計画部１０は、物品軌道計画部１００（第１階層）、切り替え位置決定部２００（第２階層）、待機位置決定部３００（第３階層）から構成される。
【００２５】
第１階層（物品軌道計算部１００）では、障害物を避けて初期位置から目標位置まで物品が到達するための物品の経路（最短経路点列）を決定する。ここでは、仮想的に物品を行動主体（つまり、自分で移動するもの）として扱い、物品の位置のみで状態空間を構成し、任務環境の地形（障害物位置、物品形状）についての知識のみから最短経路点列の計算を行う。ただし、任務環境の地形（障害物位置、物品形状）に基づいて、物品の移動方向にロボットが物品を押せる空間があるか否かを考慮して計算する。このように、第１階層では実ロボットの状態に依存しない状態空間に基づいて学習を行うことで、状態数を削減し、効率よく学習を行うことができる。
【００２６】
第２階層（切り替え位置決定部２００）では、第１階層で求めた最短経路点列上でロボット同士の待ち合わせを必要とする位置（切り替え位置）の特定を行う。ここでは、実ロボットではなく１台の仮想的なロボットを行動主体とし、物品位置と仮想的なロボットの位置からなる状態変数を用いて学習を行う。ここでの物品位置は、第１階層で求めた最短経路点列上の物品位置のみを定義域とすることで、状態数を削減することができ、効率よく学習を行うことができる。切り替え位置とは、ロボット同士の待ち合わせ動作を必要とする場所である。例えば、これまで右方向に物品を押してきたロボットが、下方向に物品を押さなければならない場合、押す方向の変化に伴ってロボットが下方向に物品を押すための位置へ移動する必要がある。このとき、ロボットの移動が障害物によって阻まれる場合は、そのロボットは下に物品を押すことはできない。つまり、他のロボットに物品の移動を引き継がざるを得ない。最短経路点列内におけるこのような物品位置を、切り替え位置と呼ぶことにする。
【００２７】
第３階層（待機位置決定部３００）では、第２階層で求めた切り替え位置ごとに、当該切り替え位置から始まる区間の物品移動を担当するロボットが、物品に邪魔されて物品を押すための位置（レディ位置）に到達できなくなることがないように、第１階層で求めた最短経路点列上で物品を待機させる（先に次の区間の物品移動を担当するロボットを通すために待機させる）位置を決定する。ここでも、行動主体は実ロボットではなく１台の仮想的なロボットとし、物品位置と仮想的なロボットの位置からなる状態変数を用いて学習を行う。なお、ここでの物品位置は、第１階層で求めた最短経路点列上の物品位置のみを定義域とすることで、状態数を削減することができる。
【００２８】
ロボット行動学習部４００では、分散学習を用いて、各実ロボットの行動を決定するための価値関数と方策を学習する。ここでは、実ロボットごとに、物品移動内容計画部１０で得た最短経路点列、切り替え位置、待機位置の情報に基づいて、当該実ロボットを動作させたときの状態の変化をシミュレーション（分散学習）し、この結果に基づいて価値関数と方策を更新していく。ただし、価値関数と方策を構成する状態空間は、物品位置と仮想的なロボットの位置（実ロボットの内のいずれかの位置が代入される変数）により構成することで、ロボットごとの状態変数を含む膨大な空間を考慮することなく学習を可能とする。
【００２９】
実ロボットの動作のシミュレーションは、各ロボットで独立して行うことができる。シミュレーションにおいては、それぞれのロボットiは自分の位置（Xr[i],Yr[i]）と物品位置（Xb,Yb）、及び自分の行動d[i]のみを状態変数として用いる。そして、物品移動内容計画部１０で計画した最短経路点列、切り替え位置、待機位置に従わないような実ロボットの行動は許容しない、つまり、実ロボットの行動が物品移動内容計画部１０で計画した結果に反する場合には、行動後の状態を変化させない（物品を動かさない）ように制御しながらシミュレーションを行う。シミュレーションで考慮する状態変数に含まれる物品位置の定義域は、物品移動内容計画部１０で求められた最短経路点列に含まれる物品位置のみである。これにより、状態空間内の状態数は、協調学習時に比べて大幅に少ないものとなる。ロボット数の増加に対しても、状態数はロボット数に比例する形でしか増大しない。
【００３０】
また、シミュレーション結果に基づく行動方策の学習では、実ロボットの役割を「物品を押すこと」と「レディ位置への移動」の２つに分け、任務環境内にあるすべてのロボットの行動を、それぞれ「物品を押すこと」と「レディ位置への移動」のための価値関数と行動方策の学習に使用する。また、学習に用いる状態変数は、実ロボットごとの位置情報の代わりに、１台の仮想ロボットの位置情報を用いる。つまり、価値関数と方策を構成する状態空間は、物品位置と仮想的なロボットの位置（実ロボットの内のいずれかの位置が代入される変数）により構成する。ロボットの行動選択においては、それぞれの役割のための価値関数値が最も高い実ロボットにその役割を割り振り、その実ロボットの状態を価値関数や方策の引数に代入することでその実ロボットがとるべき行動を得る。この場合、必要とする状態空間の数は役割の数と同じであり、ロボットの数には影響を受けないため、特に多数のロボットを使用する場合には適切である。
【００３１】
スケジューリング部５００は、ロボット行動学習部４００で得た価値関数と方策に基づいて、初期位置から目標位置まで物品を搬送するための、各実ロボットの行動計画結果を求める。
【００３２】
［実施形態の具体例］
以下、各部での具体的な処理内容を詳述する。
【００３３】
〔物品軌道計算処理〕
物品軌道計算部１００では、行動主体を物品とし、任務環境に関する情報（障害物の位置や部屋の形状、物品の形状）を利用して、物品が初期位置から目標位置に移動するための最適な移動経路（最短経路点列）s1_trj=(s1_trj[0],s1_trj[1],…,s1_trj[e])を求める。つまり、あたかも物品が自分で移動するかのように扱って、物品が初期位置から目標位置に移動するための最短経路点列を求める。最短経路点列の探索に使用するマルコフ状態空間を構成する変数を、
状態変数s1=(Xb,Yb)、行動変数a1∈{0,1,2,3,4}
のように取る。
【００３４】
各状態（ロボットの行動や物品の位置）は離散値で表現される。部屋をX,Yの直交座標系からなる二次元平面で表すと、X軸、Y軸をそれぞれ離散化表現した値により、各位置を表現する。つまり、図１のように部屋（二次元平面）は格子で区切られ、各格子が各位置に対応する。また、各格子において、障害物の「あり／なし」が予め設定されている。
【００３５】
物品の移動方向を表す行動変数a1は、以下の５種類のいずれかを取れるものとする。
0: 静止
1: 二次元平面上で右方向に物品が移動
2: 二次元平面上で上方向に物品が移動
3: 二次元平面上で左方向に物品が移動
4: 二次元平面上で下方向に物品が移動
また、行動変数a1の取りうる値の集合をA1={0,1,2,3,4}とする。
【００３６】
以下、物品軌道計算部１００が最短経路点列s1_trj=(s1_trj[0],s1_trj[1],…,s1_trj[e])を求める具体的な手順を説明する。
【００３７】
物品軌道計算部１００では、どの状態（物品位置）s1=(Xb,Yb)がどれだけゴール位置に到達し易い位置であるかを表す価値関数Vπ1(s1)を以下のマルコフ状態遷移モデルを利用して動的計画法により求め、初期位置から目標位置までの物品移動の最短経路を示す最短経路点列を出力する。
【００３８】
ここでは、マルコフ状態遷移モデルにおける「環境のとりうる離散的な状態の集合」を物品位置s1i=(Xbi,Ybi)の集合S1={s10,s11,…,s1n-1}とする。例えば、対象とする部屋をX軸方向にM個の区間に区切り、各離散区間のインデックスを0,1,…,M-1とする。同様に、Y軸方向にN個の区間に区切り、各離散区間のインデックスを0,1,…,N-1で表す。そして、各格子の位置をX軸とY軸のインデックス(Xbi,Ybj)で表す（0≦Xbi≦M-1、0≦Ybj≦N-1）。
【００３９】
物品軌道計算部１００のマルコフ状態空間では、実環境におけるどのロボットが（例えばロボットが２台あるとすれば、ロボット１とロボット２のどちらが）物品を押すのかは考慮しない。また、ロボットが物品を押せる位置まで移動するというプロセスも考慮しない。ただし、ロボットが物品を押すことが可能な物品の周りの位置に障害物がある場合にはロボットが物品を移動させることは不可能なので、その点のみを考慮する。例えば、図４の位置にある物品を図面の紙面右方向に移動させようとしても、物品の右側は障害物に接していてロボットが入るスペースがないので右方向に移動させることはできない。このようなときに、右方向に物品の位置を移動させるという選択は行わないように、物品の周辺のスペースを考慮した上で最短経路点列の計算を行う。
【００４０】
状態s1∈S1において行動a1∈A1を実行すると、状態（物品位置）は確率的に状態s1’∈S1へ遷移するものとする。その状態遷移確率P1を、
P1(s1’|s1,a1)=Pr(s1t+1=s1’|s1t=s1,a1t=a1)
とする。ここで、tは時刻を表す。各s1,a1,s1’に対する状態遷移確率P(s1’|s1,a1)を次式(1)のように設定する。
【００４１】
【数１】
2014211667.tif 000003
【００４２】
ただし、＜条件Ａ＞は以下の(1)〜(5)のいずれかの条件を満たす場合である。
(1)  a1=1 & Xb’=Xb+1 & Yb’=Yb   & Judge(s1,a1)=YES
(2)  a1=2 & Xb’=Xb   & Yb’=Yb+1 & Judge(s1,a1)=YES
(3)  a1=3 & Xb’=Xb-1 & Yb’=Yb   & Judge(s1,a1)=YES
(4)  a1=4 & Xb’=Xb   & Yb’=Yb-1 & Judge(s1,a1)=YES
(5)  a1=0 & Xb’=Xb   & Yb’=Yb   & Judge(s1,a1)=YES
ここで、「&」はAND条件を示す。また、Judge(s1,a1)を次式で与える。
【００４３】
【数２】
2014211667.tif 000004
【００４４】
Judge(s1,a1)は、位置s1にある物品が行動a1に従った方向に移動できる場合にはYES、移動できない場合にはNOを返す関数である。実際には、物品が移動するためには、ロボットが物品をその方向に押さなければならないので、物品を押すことが可能な位置にロボットが入るスペースが空いている（障害物がない）ことが必要条件となる。Judge(s1,a1)は、この必要条件を満たすか否かをチェックする関数である。Ready_Pos_k(s1,a1)は、図２に示すように、物品位置s1にある物品を行動a1の示す方向に移動させるための、物品に接するロボットの位置のk個の候補の集合を表す。このうち、障害物に重ならないロボット位置がある（障害物の位置に一致しないReady_Pos_k(s1,a1)の要素がある）場合には、位置s1にある物品をロボットが行動a1の示す方向に移動させることができる。そうでない場合には、移動させることができない。
【００４５】
なお、Ready_Pos_k(s1,a1)の候補位置を計算するためには、例えば、物品位置基準点((Xb,Yb)=(0,0))において、行動a1の示す方向に物品を移動させるためのロボットの位置の候補Pos_1(a1),Pos_2(a1),…,Pos_k(a1)を予め記憶しておき、各位置Pos_j(a1)（j=1,2,…,k）と位置s1の座標を足し合わせることで計算できる。Pos_j(a1)=(XPos_j(a1),YPos_j(a1))、s1=(Xb,Yb)であれば、(XPos_j(a1)+Xb,YPos_j(a1)+Yb)をすべてのjについて計算すればよい。
【００４６】
上記条件Ａの前半３つの条件(1)〜(3)は、現在の物品位置s1と物品の移動方向a1の組み合わせと、状態遷移後の物品位置s1’とが整合しているか否かを判定するための条件である。例えば、条件Ａの(1)の場合、a1=1（右方向に物品が移動）かつs1=(Xb,Yb)の場合、状態遷移後の物品位置はs1’=(Xb+1,Yb)となる。それ以外の位置に物品が移動することは有り得ない。上記式(1)は、現在の物品位置s1と物品の移動方向a1の組み合わせと、状態遷移後の物品位置s1’とが整合していて、かつ、物品を押すことが可能な位置にロボットが入るスペースが空いている（障害物がない）場合には、状態遷移確率を１とする。また、この条件を満たさない状態に遷移することはできないため、状態遷移確率を０とすることを意味している。
【００４７】
また、状態s1∈S1において行動a1∈A1を実行し、状態（物品位置）がs1’∈S1へ遷移したとき、環境から行動主体へ与えられる報酬R1を、
【００４８】
【数３】
2014211667.tif 000005
【００４９】
と設定する。
【００５０】
物品軌道計算部１００は、上記のマルコフ状態空間を用いて、最適な価値関数Vπ1(s1)及び方策π1をダイナミックプログラミング（Dynamic Programming）法により計算する。ダイナミックプログラミング法の詳細は、例えば、「三上貞芳、皆川雅章（共訳）、R. S. Sutton、A. G. Barto（原著）、「強化学習」、森北出版、1998、pp. 94-118」を参照されたい。
【００５１】
物品軌道計算部１００の詳細構成を図６に示す。物品軌道計算部１００は、物品軌道計算用状態遷移モデル設定部１０１、物品軌道計算用価値関数初期化部１０２、物品軌道計算用方策更新部１０３、物品軌道計算用価値関数更新部１０４、物品軌道計算用価値関数収束判定部１０５、最短経路点列計算部１０６を含む。
【００５２】
物品軌道計算用状態遷移モデル設定部１０１は、各物品位置s1と物品の移動方向a1と、状態遷移後の物品位置s1’とのすべての組み合わせについて、上記式(1)の状態遷移確率P1と、式(2)の報酬R1とを設定する。
【００５３】
物品軌道計算用価値関数初期化部１０２において、各s1∈S1についての価値関数Vπ1(s1)の初期値を設定する。これは適当な値を設定すればよいが、この発明では、初期値はすべてのs1についてVπ1(s1)=0と設定する。
【００５４】
物品軌道計算用方策更新部１０３は、各s1∈S1及びa1∈A1の組み合わせについて、
【００５５】
【数４】
2014211667.tif 000006
【００５６】
を計算し、価値関数Vπ1(s1,a1)の値が最大となる行動a1を、方策π1(s1)の値に設定する。ここで、Σは取りうるすべてのs1’についての総和を表し、γ1は予め定めた0<γ1<1.0の定数である。また、式(3)におけるVπ1(s1’)の値は、物品軌道計算用方策更新部１０３の最初の実行時は物品軌道計算用価値関数初期化部１０２で設定された初期値が利用され、２回目以降の実行では、以下の物品軌道計算用価値関数更新部１０４で更新された価値関数の値が用いられる。
【００５７】
物品軌道計算用価値関数更新部１０４は、各s1∈S1について、
【００５８】
【数５】
2014211667.tif 000007
【００５９】
により価値関数Vπ1(s1)を更新する。
【００６０】
物品軌道計算用価値関数収束判定部１０５は、物品軌道計算用価値関数更新部１０４における更新後の価値関数Vπ1(s1)の値と更新前の価値関数Vπ1(s1)の値との誤差が所定の閾値以下となるまで、上記の物品軌道計算用方策更新部１０３に戻り、方策と価値関数の更新処理を繰り返す。所定の閾値以下となった場合には、価値関数Vπ1(s1)が収束したと判定し、価値関数Vπ1(s1)と方策π1(s1)を最短経路点列計算部１０６に出力する。
【００６１】
こうして求まった価値関数Vπ1(s1)は、物品位置s1が、どれだけゴール位置に到達し易い位置であるかを表す指標である。これにより、部屋内の任意の位置から目標地点までの物品移動の最短経路を示す物品位置の系列を求めることができるようになる。
【００６２】
最短経路点列計算部１０６は、物品軌道計算用価値関数収束判定部１０５から出力された価値関数Vπ1(s1)と方策π1(s1)を用いて、初期位置から目標位置までの最短経路となる物品位置の系列（最短経路点列）を算出する。例えば、初期位置をs1_trj[0]∈S1とした場合、方策π1(s1_trj[0])の値が示す物品の移動を行い、位置s1_trj[1]∈S1に移動する。続いて位置s1_trj[1]にて方策π1(s1_trj[1])の値が示す物品の移動を行い、位置s1_trj[2]∈S1に移動する。これを目標位置s1_trj[e]∈S1に到達するまで繰り返すことで、初期位置から目標位置に至る物品の最短経路に含まれる途中点の点列（最短経路点列）：s1_trj=(s1_trj[0],s1_trj[1],…,s1_trj[e])を求める。また、このときの物品の移動方向を示す配列a1_trj=(a1_trj[0],a1_trj[1],…,a1_trj[e])=(π1(a1_trj[0]),π1(a1_trj[1]),…,π1(a1_trj[e])を求める。そして、最短経路点列計算部１０６は、最短経路点列s1_trjと移動方向の系列a1_trjを出力する。
【００６３】
〔切り替え位置決定処理〕
切り替え位置決定部２００では、最短経路点列s1_trjの各位置の中で、仮想ロボットvが継続して物品を移動させることのできる最大範囲を計算する。言い換えれば、１つのロボットが最短経路点列上の各位置をたどるように物品を押し続けたとき、これ以上継続して押せない位置（他のロボットに引き継がざるを得ない位置）を切り替え位置として計算する。
【００６４】
例えば、１台のロボットが継続してs1_trj[0]からs1_trj[4]までの各位置を経由して物品を移動させることが可能であれば、s1_trj[0],s1_trj[1],s1_trj[2],s1_trj[3],s1_trj[4]の位置については１台のロボットに担当させた方が得策である。逆に、例えばs1_trj[3]からs1_trj[4]に物品を移動させたロボットが、次のs1_trj[5]に物品を移動させるための方向に物品を押せる位置に移動することが障害物によって阻まれている場合、他の位置にいる別のロボットに物品移動を引き継いだ方が得策である。すなわち、切り替え位置決定部２００は、最短経路点列s1_trj=(s1_trj[0],s1_trj[1],…,s1_trj[e])の各位置での移動の中で、担当ロボットを切り替える位置（他のロボットに移動を引き継がざるを得ない位置）を計算する。
【００６５】
切り替え位置の探索では、１台の仮想ロボットv（物品を押して移動させるロボット）を行動主体とし、マルコフ状態遷移モデルにおけるマルコフ状態空間を最短経路点列s1_trjに含まれる各物品位置(Xb,Yb)と仮想ロボットvの位置(Xrv,Yrv)の組の取りうる値の集合として、切り替え位置の学習を行う。つまり、
状態変数s2=(Xb,Yb,Xrv,Yrv)、行動変数a2∈{0,1,2,3,4}
とする。仮想ロボットvの移動方向を表す行動変数a2は、以下の５種類のいずれかを取れるものとする。
0: 静止
1: 二次元平面上で右方向にロボットが移動
2: 二次元平面上で上方向にロボットが移動
3: 二次元平面上で左方向にロボットが移動
4: 二次元平面上で下方向にロボットが移動
【００６６】
また、行動変数a2の取りうる値の集合をA2={0,1,2,3,4}とする。
【００６７】
切り替え位置の探索では、物品軌道計算部１００で求めた最短経路点列s1_trjに含まれる位置すべてが、状態変数s2に含まれる物品位置座標(Xb,Yb)の取りうる範囲となり、それ以外の物品位置は考慮されない。つまり、(Xb,Yb)∈s1_trjとし、s1_trj以外の物品位置の値は探索にて考慮されない。
【００６８】
状態s2∈S2において行動a2∈A2を実行したとき、状態s2’∈S2へ遷移する状態遷移確率P21を、
P21(s2’|s2,a2)=Pr(s2t+1=s2’|s2t=s2,a2t=a2)
とし、各s2,a2,s2’に対する状態遷移確率P21(s2’|s2,a2)を次式(5)のように設定する。
【００６９】
【数６】
2014211667.tif 000008
【００７０】
ただし、＜条件Ｂ１＞は以下の(1)〜(6)のいずれかの条件を満たす場合である。
(1)  Xb=Xb’ & Yb=Yb’ & a2=1 & Xrv’=Xrv+1 & Yrv’=Yrv
(2)  Xb=Xb’ & Yb=Yb’ & a2=2 & Xrv’=Xrv   & Yrv’=Yrv+1
(3)  Xb=Xb’ & Yb=Yb’ & a2=3 & Xrv’=Xrv-1 & Yrv’=Yrv
(4)  Xb=Xb’ & Yb=Yb’ & a2=4 & Xrv’=Xrv   & Yrv’=Yrv-1
(5)  Xb=Xb’ & Yb=Yb’ & a2=0 & Xrv’=Xrv   & Yrv’=Yrv
(6)  (Xb,Yb)=s1_trj[L+1] & (Xb’,Yb’)=s1_trj[L+2] & a2=a1_trj[L+1] & (Xrv,Yrv)=Ready_Pos_k(s1_trj[L+1],a1_trj[L+1]) & (Xrv’,Yrv’)=a1_trj[L+1]により移動した後の位置
【００７１】
また、状態s2∈S2において行動a2∈A2を実行し、状態がs2’∈S2へ遷移したとき、環境から行動主体へ与えられる報酬R21を、
【００７２】
【数７】
2014211667.tif 000009
【００７３】
と設定する。
【００７４】
以上のように定義された状態遷移確率P21(s2’|s2,a2)と報酬R21(s2’,s2,a2)を使用して動的計画法にて方策π21(s2)を求めると、得られる方策π21(s2)は、物品が位置s1_trj[L+1]にあるときに、物品を位置s1_trj[L+1]から位置s1_trj[L+2]に移動させるための行動a1_trj[L+1]を取れる位置の集合(Ready_Pos_k(s1_trj[L+1],a1_trj[L+1]))のうちの少なくとも一箇所に、仮想ロボットvが到達するための行動方策（移動のための方策）となる。すなわち、状態s2=(Xb_trj[L+1],Yb_trj[L+1],Xrv,Yrv)における価値関数Vπ21(s2)の値が0より大きい場合、状態s2が示す位置(Xrv,Yrv)にある仮想ロボットvは状態s2が示す物品位置s1_trjL+1=(Xb_trj[L+1],Yb_trj[L+1])にある物品を次の位置に押すことが可能な位置（Ready_Pos_k(s1_trj[L+1],a1_trj[L+1])のいずれかの位置）に移動することが可能であることを示す。また、その時の移動は、方策π21(s2)が示す行動変数の値に従えばよい。
【００７５】
ここで、位置Ready_Pos_k(s1_trj[L],a1_trj[L])にあったロボットが位置s1_trj[L]にある物品を行動a1_trj[L]の示す方向に押してロボット自身も移動したときに到達するはずの位置は最大K個存在し、それらのうち障害物に重ならない位置は、Ready_Pos_k(s1_trj[L+1],a1_trj[L])=(XrL[k],YrL[k])（k=0,1,…,K-1）と表現できる。すると、位置s1_trj[L+1]の物品位置において、k個の点s2[k]=(Xb_trj[L+1],Yb_trj[L+1],XrL[k],YrL[k])（ただし、k=0,1,…,K-1、(XrL[k],YrL[k])∈Ready_Pos_k(s1_trj[L+1],a1_trj[L])、s2[k]∈S2）における価値関数値Vπ21(s2[k])=Vπ2(Xb_trj[L+1],Yb_trj[L+1],XrvL[k],YrvL[k])のうちいずれかの値が0より大きければ、同じロボットが続けて物品をs1_trj[L+2]に移動させることが可能であり、そうでない場合には物品をs1_trj[L+1]に移動させたロボットは障害物に阻まれてこれ以上物品を動かすことができないので、別のロボットに切り替える必要があることがわかる。
【００７６】
切り替え位置決定部２００の詳細構成を図７に示す。切り替え位置決定部２００は、切り替え位置決定用状態遷移モデル設定部２０１、切り替え位置決定用価値関数初期化部２０２、切り替え位置決定用方策更新部２０３、切り替え位置決定用価値関数更新部２０４、切り替え位置決定用価値関数収束判定部２０５、切り替え位置判定部２０６を含む。
【００７７】
切り替え位置決定用状態遷移モデル設定部２０１は、上記式(5)の状態遷移確率P21と、式(6)の報酬R21とを設定する。
【００７８】
切り替え位置決定用価値関数初期化部２０２、切り替え位置決定用方策更新部２０３、切り替え位置決定用価値関数更新部２０４、切り替え位置決定用価値関数収束判定部２０５の処理は、状態遷移確率と報酬がそれぞれ式(5)(6)に置き換わる点を除いては、物品軌道計算部１００で説明した処理と同様である。
【００７９】
切り替え位置決定用価値関数初期化部２０２は、各s2∈S2についての価値関数Vπ21（s2)の初期値を0に設定する。
【００８０】
切り替え位置決定用方策更新部２０３は、各s2∈S2及びa2∈A2の組み合わせについて、
【００８１】
【数８】
2014211667.tif 000010
【００８２】
を計算し、価値関数Vπ21(s2,a2)の値が最大となる行動a2を、方策π21(s2)の値に設定する。ここで、Σは取りうるすべてのs2’についての総和を表し、γは予め定めた0<γ<1.0の定数である。また、式(7)におけるVπ21(s2’)の値は、切り替え位置決定用方策更新部２０３の最初の実行時は切り替え位置決定用価値関数初期化部２０２で設定された初期値が利用され、２回目以降の実行では、以下の切り替え位置決定用価値関数更新部２０４で更新された価値関数の値が用いられる。
【００８３】
切り替え位置決定用価値関数更新部２０４は、各s2∈S2について、
【００８４】
【数９】
2014211667.tif 000011
【００８５】
により価値関数Vπ21(s2)を更新する。
【００８６】
切り替え位置決定用価値関数収束判定部２０５は、切り替え位置決定用価値関数更新部２０４における更新後の価値関数Vπ21(s2)の値と更新前の価値関数Vπ21(s2)の値との誤差が所定の閾値以下となるまで、上記の切り替え位置決定用方策更新部２０３に戻り、方策と価値関数の更新処理を繰り返す。所定の閾値以下となった場合には、価値関数Vπ21(s2)が収束したと判定し、価値関数Vπ21(s2)と方策π21(s2)を切り替え位置判定部２０６に出力する。
【００８７】
切り替え位置判定部２０６は、切り替え位置決定用方策更新部２０３で計算した価値関数を用いて、各L=0,1,…,eについて、
【００８８】
【数１０】
2014211667.tif 000012
【００８９】
を計算する。ここで、Lは、最短経路点列s1_trjのインデックスである。Partition[L]の値が0のとき、s1_trj[L]にある物品をs1_trj[L+1]に移動したのち、担当ロボットを変更しなければならないことを示す。
【００９０】
こうして求められたPartition[L]の値は、１台のロボットが継続して押すことのできる区間を示す。つまり、Partition[L]=0で区切られた区間が１台のロボットが継続して押すことのできる区間である。以下では、各区間の開始点のインデックスの値をp0,p1,p2,…,pfとする。なお、区間の開始点とは、L=0、及び、Partition[L]=0となるLの値である。
【００９１】
例えば、
Partition[0]=1,
Partition[1]=1,
Partition[2]=0,
Partition[3]=2,
Partition[4]=2,
Partition[5]=3,
Partition[6]=0,
Partition[7]=4,
Partition[8]=5, …
の場合、区間の端点はp0=0,p1=2,p2=6であり、p1=2及びp2=6が切り替え位置となる。
【００９２】
〔待機位置決定処理〕
待機位置決定部３００では、切り替え位置決定部２００で求められた切り替え位置p1,p2,…,pfの各レディ位置（切り替え位置pjから始まる物品の移動を可能な位置）にロボットが到達可能にするための物品の待機位置を、マルコフ状態遷移モデルを利用して動的計画法により計算する。ここで、待機位置とは、最短経路点列上の切り替え位置より前の物品位置であって、レディ位置にロボットが到達するための経路が障害物や物品で塞がれておらず、かつ、最もそれぞれの切り替え位置に近い物品位置である。
【００９３】
待機位置決定部３００は、切り替え位置決定部２００と同じく状態変数s2と行動変数a2を用いて、待機位置の学習を行う。ここでも、物品軌道計算部１００で求めた最短経路点列s1_trjに含まれる位置すべてが、状態変数s2に含まれる物品位置座標(Xb,Yb)の取りうる範囲となり、それ以外の物品位置は考慮されない。
【００９４】
以下、切り替え位置pjにおける物品の待機位置を求める場合を例に、具体的な処理を説明する。ここで、切り替え位置pjにおける物品の待機位置とは、切り替え位置pjから先の物品の移動を担当するロボットがレディ位置に到達するための経路を妨げないための物品の待機位置である。
【００９５】
状態s2∈S2において行動a2∈A2を実行したとき、状態s2’∈S2へ遷移する状態遷移確率P22を、
P22(s2’|s2,a2)=Pr(s2t+1=s2’|s2t=s2,a2t=a2)
とし、各s2,a2,s2’に対する状態遷移確率P22(s2’|s2,a2)を次式(9)のように設定する。
【００９６】
【数１１】
2014211667.tif 000013
【００９７】
ただし、＜条件Ｂ２＞は以下の(1)〜(5)のいずれかを満たす場合である。
(1)  Xb=Xb’ & Yb=Yb’ & a2=1 & Xrv’=Xrv+1 & Yrv’=Yrv
(2)  Xb=Xb’ & Yb=Yb’ & a2=2 & Xrv’=Xrv   & Yrv’=Yrv+1
(3)  Xb=Xb’ & Yb=Yb’ & a2=3 & Xrv’=Xrv-1 & Yrv’=Yrv
(4)  Xb=Xb’ & Yb=Yb’ & a2=4 & Xrv’=Xrv   & Yrv’=Yrv-1
(5)  Xb=Xb’ & Yb=Yb’ & a2=0 & Xrv’=Xrv   & Yrv’=Yrv
【００９８】
また、状態s2∈S2において行動a2∈A2を実行し、状態がs2’∈S2へ遷移したとき、環境から行動主体へ与えられる報酬R22を、
【００９９】
【数１２】
2014211667.tif 000014
【０１００】
と設定する。
【０１０１】
以上のように定義された状態遷移確率P22(s2’|s2,a2)と報酬R22(s2’,s2,a2)を使用して動的計画法にて価値関数Vπ22(s2)を求めると、得られる価値関数Vπ22(s2)は、物品が位置(Xb,Yb)にあるときに、切り替え位置pjに対するレディ位置にロボットがどの位置から到達可能であるかを示す値となる。すなわち、s2=(Xb_trj[L+1],Yb_trj[L+1],Xrv,Yrv)における価値関数Vπ22(s2)の値が0より大きい場合、状態s2が示す位置(Xrv,Yrv)にある仮想ロボットvは切り替え位置pjのレディ位置に移動することが可能であることを示す。また、その時の移動は、方策π22(s2)が示す行動変数の値に従えばよい。
【０１０２】
つまり、物品位置が（Xb_trj[L+1],Yb_trj[L+1]）であり、ロボットの位置(Xrv,Yrv)が障害物位置に一致しておらず、かつ、物品と重なっていないすべての状態s2において、価値関数Vπ22(s2)の値が0以下になる状態が存在しない場合、その物品位置(Xb_trj[L+1],Yb_trj[L+1])が、切り替え位置pjのための待機位置の候補となりうる。（ただし、任務環境内に、障害物で囲まれてロボットの出入り不可な領域はないものと仮定する。）そうした候補物品位置(Xb_trj[L+1],Yb_trj[L+1])の中で、pj≧L+1であり、かつ最もpjに近い位置を、切り替え位置pjのための待機位置とすればよい。そのようにして求められた切り替え位置pjのための待機位置を（Xb_wait(j),Yb_wait(j)）と定義する。これを、すべての切り替え位置p1,p2,…,pfについて行う。
【０１０３】
待機位置決定部３００の詳細構成を図８に示す。待機位置決定部３００は、切り替え位置選択部３０１、待機位置決定用状態遷移モデル設定部３０２と、待機位置決定用価値関数初期化部３０３、待機位置決定用方策更新部３０４、待機位置決定用価値関数更新部３０５、待機位置決定用価値関数収束判定部３０６、待機位置判定部３０７、終了判定部３０８を含む。
【０１０４】
切り替え位置選択部３０１は、切り替え位置決定部２００で求めた切り替え位置p1,p2,…,pfの中から、まだ選択していない（待機位置を計算していない）切り替え位置pjを１つ選択する。
【０１０５】
待機位置決定用状態遷移モデル設定部３０２は、上記式(9)の状態遷移確率P22と、式(10)の報酬R22とを設定する。
【０１０６】
待機位置決定用価値関数初期化部３０３、待機位置決定用方策更新部３０４、待機位置決定用価値関数更新部３０５、待機位置決定用価値関数収束判定部３０６の処理は、状態遷移確率と報酬がそれぞれ式(9)(10)に置き換わる点を除いては、物品軌道計算部１００で説明した処理と同様である。
【０１０７】
待機位置決定用価値関数初期化部３０３は、各s2∈S2についての価値関数Vπ22(s2)の初期値を0に設定する。
【０１０８】
待機位置決定用方策更新部３０４は、各s2∈S2及びa2∈A2の組み合わせについて、
【０１０９】
【数１３】
2014211667.tif 000015
【０１１０】
を計算し、価値関数Vπ22(s2,a2)の値が最大となる行動a2を、方策π22(s2)の値に設定する。ここで、Σは取りうるすべてのs2’についての総和を表し、γは予め定めた0<γ<1.0の定数である。また、式(11)におけるVπ22(s2’)の値は、待機位置決定用方策更新部３０４の最初の実行時は待機位置決定用価値関数初期化部３０３で設定された初期値が利用され、２回目以降の実行では、以下の待機位置決定用価値関数更新部３０５で更新された価値関数の値が用いられる。
【０１１１】
待機位置決定用価値関数更新部３０５は、各s2∈S2について、
【０１１２】
【数１４】
2014211667.tif 000016
【０１１３】
により価値関数Vπ22(s2)を更新する。
【０１１４】
待機位置決定用価値関数収束判定部３０６は、待機位置決定用価値関数更新部３０５における更新後の価値関数Vπ22(s2)の値と更新前の価値関数Vπ22(s2)との誤差が所定の閾値以下となるまで、上記の待機位置決定用方策更新部３０４に戻り、方策と価値関数の更新処理を繰り返す。所定の閾値以下となった場合には、価値関数Vπ22(s2)が収束したと判定し、価値関数Vπ22(s2)と方策π22(s2)を待機位置判定部３０７に出力する。
【０１１５】
待機位置判定部３０７は、待機位置決定用価値関数収束判定部３０６から出力された価値関数Vπ22(s2)と方策π22(s2)を用いて、切り替え位置pjにおける物品の待機位置を決定する。具体的には、状態s2において、物品位置を(Xb_trj[L+1],Yb_trj[L+1])としたときに、障害物位置及び物品に一致していないすべてのロボット位置(Xrv,Yrv)において価値関数Vπ22(s2)の値が0より大きくなる場合、その物品位置(Xb_trj[L+1],Yb_trj[L+1])を、切り替え位置pjにおける物品の待機位置候補とし、すべての待機位置候補のうち、pj≧L+1を満たす最大のL+1の値を持つ待機位置候補を切り替え位置pjのための待機位置として決定する。
【０１１６】
終了判定部３０８は、切り替え位置決定部２００で求めたすべての切り替え位置について待機位置を決定したか否かを判定し、まだ待機位置を決定していない切り替え位置がある場合には切り替え位置選択部３０１へ処理を移行する。すべての切り替え位置について待機位置を決定した場合には、切り替え位置ごとの待機位置を出力する。
【０１１７】
〔ロボット行動学習処理〕
ロボット行動学習部４００は、実ロボットごとに動作のシミュレーション（分散学習）を行い、その結果に基づいて、実ロボットの各々の時刻ごとの行動を決定するための行動方策を、マルコフ状態遷移モデルを利用したＱ学習により学習する。ここで、行動方策は、物品押し行動のための行動方策（押し方策）π31及びレディ位置への移動行動のための行動方策（移動方策）π32の２種類を用いる。
【０１１８】
マルコフ状態遷移モデルの状態変数s3は、物品位置(Xb,Yb)と１台の仮想ロボットwの位置(Xrw,Yrw)からなる状態変数s3=(Xb,Yb,Xrw,Yrw)であり、行動変数a3∈{0,1,2,3,4}は仮想ロボットwの取りうる行動を表すものとする。行動a3の取りうる各値は、行動変数a2と同様である。物品位置(Xb,Yb)の取りうる値は、物品軌道計算部１００で求めた最短経路点列に含まれる点(Xb,Yb)∈{s1_trj[0],s1_trj[1],…,s1_trj[e]}とする。また、状態s3に含まれる仮想ロボットwの位置(Xrw,Yrw)は、部屋全体を定義域とする。
【０１１９】
ロボット行動学習部４００の学習が第１階層から第３階層までの学習と大きく異なる点は、第１階層から第３階層まではマルコフ状態遷移モデルにおける行動主体が１台の仮想ロボットvとしているのに対して、ロボット行動学習部４００ではN台の実ロボットを動作させた結果を基に押し方策と移動方策を求める点である。つまり、押し方策と移動方策を決定するための価値関数（Ｑ関数）を求める際に、状態変数s3における仮想ロボットwの位置情報(Xrw,Yrw)や行動変数a3に、各実ロボットの位置や行動を代入することにより、押し方策と移動方策の各々に対応するＱ関数を更新していく。つまり、１台の仮想ロボットwの状態変数と行動変数をN台の実ロボットで共有して学習するようなものである。これにより、ロボットごとの状態変数を考慮するよりも状態変数の数を少なくすることができ、かつ、ロボットの台数が増えるほど学習を加速させられる効果が得られる。
【０１２０】
実ロボットの動作のシミュレーションは、各ロボットで独立して行うことができる。シミュレーションでは、第１階層から第３階層までで計画した最短経路点列、切り替え位置、待機位置に従わないような実ロボットの行動は許容しない。つまり、実ロボットの行動が第１階層から第３階層までで計画した結果に反する場合には、行動後の状態を変化させない（物品を動かさない）ように制御することを特徴とする。
【０１２１】
また、上述のように状態変数s3及び行動変数a3をすべての実ロボットで共有し、学習対象（方策の種類）をロボットの役割に応じた数（「押し方策」と「移動方策」の２種類）にして学習を行うことで、ロボット数が増えても状態数や学習対象の数が変わらないため、計算量を抑えることができる。
【０１２２】
ロボット行動学習部４００の詳細構成を図９に示す。ロボット行動学習部４００は、Ｑ関数・方策初期化部４０１、初期状態設定部４０２、行動割り当て部４０３、Ｑ関数・方策更新部４０４、目標位置到達判定部４０５を含み、この例ではさらに、物品位置判定部４０６を含む。このうちＱ関数・方策更新部４０４が上述のシミュレーションを行う部分である。Ｑ関数・方策更新部４０４は、ロボットごとに独立して実行させる構成としてもよく、例えばロボットがN台ある場合であれば、図９に示すように、N個のＱ関数・方策更新部４０４1,４０４2,…,４０４Nを含むように構成すればよい。
【０１２３】
＜Ｑ関数・方策初期化処理＞
Ｑ関数・方策初期化部４０１は、取りうるすべての状態s3と行動a3の組合せについて、押し方策を決定するための指標となるＱ関数Qπ31(s3,a3)と、移動方策を決定するための指標となるＱ関数Qπ32(s3,a3)と、押し方策π31(s3)と移動方策π32(s3)の初期値を設定する。これらはランダムな値を設定すればよい。また、それぞれの状態s3におけるＱ関数の最大値Qmaxπ31(s3)とQmaxπ32(s3)の初期値を、それぞれQπ31(s3,a3)とQπ32(s3,a3)の初期値から求める。
【０１２４】
押し方策π31(s3)の初期値は、状態s3においてQπ31(s3,a3)の値が最大となる行動a3の値とする。同様に、移動方策π32(s3)の初期値は、状態s3においてQπ32(s3,a3)の値が最大となる行動a3の値とする。
【０１２５】
＜初期状態設定処理＞
初期状態設定部４０２は、N台の実ロボットの位置と物品の位置を初期位置に設定する。
【０１２６】
＜行動割り当て処理＞
行動割り当て部４０３は、実ロボットと物品の動きをシミュレーションするにあたっての、各実ロボットの行動を決定する。具体的には、現在のステップ（時刻）をtとし、時刻tにおける各実ロボットに対応する状態変数s3のうち、Qmaxπ31(s3)を最大にする実ロボットに、時刻tで押し方策π31(s3)が示す行動を割り当て、Qmaxπ32(s3)を最大にする実ロボットに、時刻tで移動方策π32(s3)が示す行動を割り当てる。その他の実ロボットには、a3∈{0,1,2,3,4}の中からランダムな行動を割り当てる。ただし、押し方策と移動方策とでは、移動方策の選択を優先させることとする。つまり、Qmaxπ31(s3)を最大にする実ロボットがQmaxπ32(s3)も最大にする場合は、この実ロボットには移動方策π32(s3)に沿った行動を割り当てる。なお、学習の初期には押し方策もしくは移動方策を割り当てたロボットの場合でも、一定の確率でランダムな行動選択をさせ、ランダムな行動選択の確率を学習時間の経過とともに０に近づけていく方法を採用してもよい。
【０１２７】
＜Ｑ関数・方策更新処理＞
Ｑ関数・方策更新部４０４は、実ロボットごとに、行動割り当て部４０３で割り当てられた行動に従って行動したときの次のステップ（時刻t+1）における状態s3'を計算し、この結果に基づいて押し方策を決定するための価値関数であるＱ関数Qπ31(s3,a3)と、移動方策を決定するための価値関数であるＱ関数Qπ32(s3,a3)の値を更新する。この処理は、実ロボットごとに独立（並列）に行ってもよいし、１つのＱ関数・方策更新部４０４で順番にすべての実ロボットに対応したシミュレーションに基づくＱ関数の更新を行ってもよい。
【０１２８】
Ｑ関数・方策更新部４０４の行うシミュレーションの流れを図１０に示す。まず、状態変数s3における物品位置(Xb,Yb)が待機位置かどうかを確認する（ステップＳ１）。物品が待機位置にある場合には、すべての実ロボットのうち、少なくとも１つが待機位置(Xb,Yb)に対応する切り替え位置pjにおけるレディ位置に到達しているかどうかを確認する（ステップＳ２）。ステップＳ１において物品が待機位置にない場合、もしくはステップＳ２においていずれかの実ロボットがレディ位置にすでに到達している場合には、各実ロボットの行動に従って、各実ロボットの位置及び物品位置を移動させ、状態s3’を計算する（ステップＳ３−１）。ステップ２においてレディ位置に到達している実ロボットがない場合、押し行動を選択した実ロボットについては、時刻t+1における状態s3’を変化させず、残りの実ロボットについては、選択した行動に従って実ロボットの位置及び物品位置を移動させ、状態s3’を計算する（ステップＳ３−２）。
【０１２９】
このように、シミュレーションでは、第２階層と第３階層で計画した切り替え位置と待機位置に沿った実ロボットの行動しか許容しないような制御を行う。つまり、物品が待機位置決定部３００で決定した待機位置にあり、当該待機位置に対応する切り替え位置における次の区間の移動を担当するロボットのレディ位置にまだ１台もロボットが到達していない場合には、押し行動を選択した実ロボットが物品の軌道に沿った向きに物品を押せる位置にあり、かつ物品を押す行動を選択したとしても、時刻tにおける状態s3から時刻t+1における状態s3'へ変化させないこととする。これが、Ｑ関数・方策更新部４０４の処理における重要なポイントの１つである。いわば、実ロボットが物品を押して移動させようとしても、物品が意識的にブレーキをかけて動こうとしないような状態を仮想的に作り出している。これにより、環境にいるすべての実ロボットの状態が状態変数の中に含まれていなくとも、他ロボットの状態を考慮して、切り替え位置から先の区間の移動が行えない状態に陥らないような計画を行うことができる。
【０１３０】
なお、さらに、物品が第１階層で求めた最短経路点列に沿った実ロボットの行動しか許容しないような制御を加えてもよい。つまり、押し行動を選択したロボットの行動が、最短経路点列に沿った物品の移動以外の方向に物品を押す行動であった場合にも、押し行動を選択した実ロボットについては、時刻t+1における状態s3'を時刻tにおける状態s3から変化させないこととしてもよい。
【０１３１】
これにより、第１階層から第３階層までで計画した最短経路点列の物品移動に沿わない行動を実ロボットが選択した場合には、行動前の状態s3と行動後の状態s3'が変化しないため、結果として下記式(13)や(14)で計算される押し方策のための報酬が0となる。一方、物品が（移動中のロボットの軌道を妨げないように）待機している状態ではなく、ロボットが物品を押す行動を選択し、物品を押して移動させることができた場合に、報酬が正の値となる。これにより、ロボットが押す行動を学習する。
【０１３２】
Ｑ関数・方策更新部４０４は、各実ロボットの時刻tにおける状態s3と時刻t+1における状態s3'に対応するＱ関数Qπ31(s3,a3)及びＱ関数Qπ32(s3,a3)を更新する。具体的には、押し方策π31と移動方策π32の初期値は、押し方策のための報酬R31を次式(13)のように設定し、移動方策のための報酬R32を次式(14)のように設定する。
【０１３３】
【数１５】
2014211667.tif 000017
【０１３４】
ただし、＜条件Ｃ１＞は以下の(1)〜(3)のすべてを満たす場合である。
(1)  (Xb,Yb)=s1_trj[L+1] & (Xb’,Yb’)=s1_trj[L+2]
(2)  a3=a1_trj[L+1]
(3)  (Xrw,Yrw)=Ready_Pos_k(s1_trj[L+1],a1_trj[L+1]) & (Xrw’,Yrw’)=a1_trj[L+1]により移動した後の位置
【０１３５】
また、＜条件Ｃ２＞は以下の条件を満たす場合である。（現在物品が切り替え位置pjに向けて移動中とすると）
(Xrw’,Yrw’)=Ready_Pos_k(s1_trj[pj],a1_trj[pj])
【０１３６】
Ｑ関数・方策更新部４０４は、押し方策のための報酬R31(s3’,s3,a3)と時刻tにおけるＱ関数Qπ31(s3,a3)及びQπ32(s3,a3)を用いて、
【０１３７】
【数１６】
2014211667.tif 000018
【０１３８】
により、Ｑ関数Qπ31(s3,a3)及びQπ32(s3,a3)の値を更新する。次に、更新後のＱ関数Qπ31(s3,a3)を使用して、最大値Qmaxπ31(s3’)の値を設定する。同様に、更新後のＱ関数Qπ32(s3,a3)を使用して、最大値Qmaxπ32(s3’)の値を設定する。そして、押し方策π31(s3)を状態s3において最大値Qmaxπ31(s3)の値をもたらす行動a3の値で更新し、移動方策π32(s3)を状態s3において、最大値Qmaxπ32(s3)の値をもたらす行動a3の値で更新する。
【０１３９】
＜目標位置到達判定処理＞
目標位置到達判定部４０５は、上記Ｑ関数・方策更新部４０４でシミュレーションしたときに、行動割り当て部４０３において押し方策π31(s3)を割り当てた実ロボットの次ステップ（時刻t+1）における状態s3'に含まれる物品位置(Xb,Yb)が目標位置(Xbe,Ybe)に到達しているかを判定し、到達していれば初期状態設定部４０２に戻る。到達していなければ、行動割り当て部４０３に戻り、シミュレーションに基づくＱ関数の更新処理を繰り返す。
【０１４０】
さらに、目標位置到達判定部４０５では、Ｑ関数・方策更新部４０４における更新前のＱ関数の値と更新後のＱ関数の値との差、ΔQπ31(s3,a3)とΔQπ32(s3,a3)の過去のある時間ステップの間での平均を計算し、これらが所定の閾値以下であるならば処理を終了し、閾値以上である場合には、初期状態設定部４０２に処理を移行し、シミュレーションに基づくＱ関数の更新処理を繰り返させてもよい。Ｑ関数が収束するまで（つまり、ΔQπ31(s3,a3)とΔQπ32(s3,a3)が所定の閾値以下となるまで）、Ｑ関数の更新処理を繰り返すことで、Ｑ関数の精度を上げることができ、より効率の良い解（行動計画結果）が得られる可能性が高くなる。なお、学習の終了の条件として、ロボットが所定の行動ステップ数内で物品を目標位置まで押すことができたかどうかという条件や、学習開始時に予め学習を継続するステップの回数を決めておき、Ｑ関数の更新回数がそれを超えたかどうかを判定する条件を使用してもよい。
【０１４１】
＜物品位置判定処理＞
物品の位置がロボットにより移動不可能な位置にあるまま、長時間学習処理が継続してしまうことを避けるために、物品位置判定部４０６を更に設けてもよい。物品位置判定部４０６は、Ｑ関数・方策更新部４０４のシミュレーションにおいて、物品位置が最後に変化した時刻から現在の時刻までの差が所定の閾値を超えた場合に、初期状態設定部４０２へ移行するよう制御する。物品位置が最後に変化した時刻から現在の時刻までの差が所定の閾値未満であれば、Ｑ関数・方策更新部４０４に処理を移行し、シミュレーションに基づくＱ関数の更新処理を繰り返す。長時間物品位置が変わらないということは、物品が実ロボットの動きを妨げる位置にあったり、障害物に接していたりして、これ以上動かせない（解に到達できない）状態になっている可能性が高い。物品位置判定部４０６を含むように構成することで、このような場合に初期状態に戻して再度計算し直すことできるようになる。
【０１４２】
〔スケジューリング処理〕
スケジューリング部５００は、ロボット行動学習部４００により得られた押し方策を決定するための指標となるＱ関数Qπ31(s3,a3)と、移動方策を決定するための指標となるＱ関数Qπ32(s3,a3)と、押し方策π31(s3)と、移動方策π32(s3)とを使用し、実ロボットが協調して物品を初期位置から目標位置まで搬送するための各ロボットの行動計画を行う。
【０１４３】
スケジューリング部５００の詳細構成を図１１に示す。スケジューリング部５００は、初期状態設定部５０１、行動割り当て部５０２、次状態計算部５０３、目標位置到達判定部５０４を含む。
【０１４４】
初期状態設定部５０１は、ロボット行動学習部４００の初期状態設定部４０２と同じく、各実ロボットと物品の位置をそれぞれ初期位置に設定する。
【０１４５】
行動割り当て部５０２は、ロボット行動学習部４００の行動割り当て部４０３と同様の処理を行う。
【０１４６】
次状態計算部５０３は、実ロボットごとに、行動割り当て部５０２で割り当てた行動を選択したときの、次ステップ（次時刻）における状態（各実ロボット及び物品の状態）s3'を計算する。このとき、ロボット行動学習部４００のＱ関数・方策更新部４０４と同様に、第２階層と第３階層で計画した切り替え位置と待機位置に沿った実ロボットの行動しか許容しないような制御（物品のブレーキング）を考慮するものとする。
【０１４７】
目標位置到達判定部５０４は、ロボット行動学習部４００の目標位置到達判定部４０５と同様の処理を行う。目標位置に到達したら、ステップの実行ごと（時刻ごと）に各実ロボットに割り当てた行動の系列（搬送計画結果）を出力する。
【０１４８】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１４９】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１５１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１５３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１５４】
Ａ  ロボット協調搬送計画装置
１０  物品移動内容計画部
１００  物品軌道計算部
２００  切り替え位置決定部
３００  待機位置決定部
４００  ロボット行動学習部
５００  スケジューリング部
【図２】
2014211667.tif 000019
【図５】
2014211667.tif 000020
【図６】
2014211667.tif 000021
【図７】
2014211667.tif 000022
【図８】
2014211667.tif 000023
【図９】
2014211667.tif 000024
【図１０】
2014211667.tif 000025
【図１１】
2014211667.tif 000026
【図１】
2014211667.tif 000027
【図３】
2014211667.tif 000028
【図４】
2014211667.tif 000029