(57)【要約】【課題】環境が変わっても行動を適切に変更できるエージェントコントローラを提供する。【解決手段】エージェントコントローラは、データ点の形で経験を記憶する行動要素DB194を含む。データ点の各々は行動要素の種類と、ローカルパラメータと、引数と、行動要素実行の終了時のローカルパラメータの値とを含む。コントローラはさらに、エージェントの環境を観察し、ローカルパラメータの値を計算するローカル表現生成モジュール186と、ローカルパラメータ及び行動要素DB194に記憶された経験に基づいて行うべき行動要素の種類を決定する比較選択モジュール192と、決定された行動要素に関連する引数を、同じ行動要素を有するデータ点間のカーネル回帰で計算するサブゴール生成モジュール196と、行動要素の実行結果を評価し、強化学習を用いてカーネル回帰でのデータ点の重みを更新する更新モジュール190とを含む。【選択図】図１１
2008090606.tif 000002
【特許請求の範囲】
【請求項１】
課題を遂行する間に、ある環境において観察されうる一組のパラメータによって規定される状態空間内のエージェントの現在位置と、エージェントを制御するための予め定められた一組の行動要素とに基づいて、エージェントに課題を遂行させるよう制御するためのエージェントコントローラであって、前記一組のパラメータは環境において場所ごとに異なる一組のグローバルパラメータと、環境において場所に関わらず同じであり得る一組のローカルパラメータとに分割されており、前記エージェントコントローラは、
課題に関連する経験をデータ点の形で記憶するための手段を含み、前記データ点の各々は、実行される行動要素の種類と、行動要素が実行される際のローカルパラメータの組の値と、行動要素に関連する引数の値と、行動要素の実行終了の際のローカルパラメータの組の値とを含み、前記エージェントコントローラはさらに、
課題におけるエージェントの環境を観察するための手段を含み、前記観察するための手段は、観察された環境に基づいてローカルパラメータの組の値を計算し、
前記観察するための手段によって計算されたローカルパラメータの組と、前記記憶するための手段に記憶された経験とに基づいて、実行すべき行動要素の種類を決定するための手段と、
前記決定するための手段によって決定された行動要素の種類に関連する引数の値を、前記決定するための手段によって決定された行動要素と同じ種類の行動要素を有する、前記記憶するための手段に記憶されたデータ点の引数値からの所定のカーネル回帰によって計算するための手段と、
前記計算するための手段によって計算された引数値を用いて、前記決定するための手段によって決定された種類の、エージェントを制御するための行動要素を実行するための手段と、
前記行動要素を実行するための手段によって実行された種類の行動要素の実行の結果を評価して、前記課題において期待される報酬が最大に近づくように、強化学習を用いて前記カーネル回帰における前記データ点に割当てられる重みを更新するための手段とを含み、前記重みは、前記経験、前記ローカルパラメータの組、及び前記グローバルパラメータの組を用いて計算される、エージェントコントローラ。
【請求項２】
前記計算するための手段は、
状態空間におけるエージェントの現在位置と、前記状態空間内の、前記決定するための手段によって決定されたのと同じ種類の行動要素を有するデータ点の各々との距離を計算するための手段と、
前記状態空間において、他のデータ点よりもエージェントの現在位置に近い予め定められた数のデータ点を選ぶための手段と、
前記選ぶための手段によって選ばれたデータ点の引数値から所定のカーネル回帰により、前記決定するための手段によって決定された行動要素の種類に関連する引数値を計算するための手段と、を含む、請求項１に記載のエージェントコントローラ。
【請求項３】
コンピュータ上で実行されると、請求項１または請求項２に記載の全ての手段としてコンピュータを動作させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、エージェントコントローラと、エージェントがある環境で動作しながらその行動を変更できるようにするプログラムとに関し、特に、エージェントが動作する際に、行動要素を用いて観察と実践とから新たな環境に対する好適な解決策を学習できるようにする、エージェントコントローラ及びプログラムに関する。
【背景技術】
【０００２】
高性能コンピュータの発展に伴い、広範な分野で、コンピュータがごく短時間に大量の情報を取扱う能力が開発されつつある。典型的な例の一つは、リアルタイムで人と対話することのできるヒューマノイドロボットである。別の例は、コンピュータ又はコンピュータネットワークに常駐してそれ自身の判断で活動することのできるコンピュータプログラムである。この出願では、このようなロボット又はプログラムを「エージェント」と呼ぶこととする。
【０００３】
人とエージェントとのこのようなリアルタイムの対話を実現するには、エージェントがカメラ又は一組のカメラを用いて人とその行為とを観察する能力が必要な前提条件である。エージェントが人の行為に対して好適な反応をどのように見出すべきかを学習することも必要である。人とその行為とを観察することができ、その観察に基づいて、他者の行為にどのように反応すべきかを学習できるシステムには大いに利益がある筈である。
【０００４】
このような状況において、エージェント又はロボットにとって、学習は大変に費用がかかるものとなりうる。従って、学習済みの情報をできるだけ多く利用することが必要になる。これを行なうひとつの方法は、さまざまな同様の課題において学習された情報や技能を用いる能力を備えることである。
【０００５】
学習速度を速め、一般化を向上させる方法の一つとして行動要素が提案されており、これらは、ある課題の小部分に対する解決策であって、それらを組合せることによってその課題を完成することができるようなものである、と定義されている。ロボットやエージェントシミュレータをプログラミングし、操作、ナビゲーション、運動、ダンス等において同様の課題に一般化できる行動要素を教示することについて、広範な研究がなされている。操作課題のための行動要素実行シーケンスを学習したエージェント又はロボットは、作業空間の初期構成がわずかに異なってもこれを一般化する能力を有する。エージェント又はロボットに、身振り、又は言語によるフィードバックを与えることによって、一般化を支援し、行動要素のシーケンスをガイドするような他のシステムも作られている。行動要素の実行が時に失敗し、また他のエージェントが干渉するようなダイナミックな課題においては、何らかの状況でどのような行動をとるべきかをエージェントに指示するためにより完全な方策が必要であることがわかった。
【０００６】
発明者らの研究が主に焦点をあてているのは、学習済みの情報をできるだけ再利用することが可能になる方法を探求することである。発明者らは、行動要素を用いて、観察と実践とから学習する枠組を作成した。この枠組によれば、エージェントやロボットはどのようにマーブル迷路の課題を行なったり、エアホッケーをしたりするかを学習することができる。この枠組は、行為生成モジュールと、行動要素選択モジュールと、サブゴール生成モジュールと、観察学習モジュールと、実践学習モジュールと、を含む。このシステムの詳細は、特許文献１に示される。
【０００７】
「行為生成モジュール」はある環境内の複数の場所で用いられるように設計され、また同様の環境においても用いることができる。「行動要素選択モジュール」及び「サブゴール生成モジュール」は、いつ、どの行動要素を、どの引数と用いるべきかを学習するために、メモリベースのアプローチを利用する。「観察学習モジュール」は他者がある課題を行なうのを見て学習するのを支援する。これは、観察された行動を、選ばれた行動要素に分離する行動要素認識モジュールと、観察された環境状態で行なうべき行動要素の種類をエージェントに提供する行動要素選択モジュールとを含みうる。
【０００８】
観察された情報のみを用いる場合、エージェント又はロボットはその観察された情報に基づく固定された方策のみを有する。「実践学習モジュール」は課題を実行する間のロボットの性能を評価し、さまざまなアルゴリズムを用いてロボットの技量を向上させる。
【０００９】
行動要素とは、ある課題の小部分に対する解決策であって、それらを組合わせることによってその課題を完成することができるようなものである。ある課題の解決策は、多くの行動要素から構成されうる。例えば、エアホッケーの環境では、パックを打つ、パックを捕らえる、ゴールを守る等の行動要素があるだろう。多くの場合、一つの行動要素をさらにより小さい行動要素に分けることができる。現段階では、ある特定の課題に用いられる行動要素の候補は人が設計できる。
【特許文献１】特開２００４−１６３９９２
【発明の開示】
【発明が解決しようとする課題】
【００１０】
行動要素と、観察された情報とを用いるエージェント又はロボットは、与えられた課題と一組の行動要素とに対して、観察者と同様の動作をしようとする筈である。マーブル迷路ゲームを行なうための行動要素を選択する場合、エージェント又はロボットは環境を観察して「マーブルがこのボードのこの場所にあり、観察された速度でボードが観察された角度にあったとき、教師はどの行動要素を選択したか？」と問いかける。回答は、これらが観察された状態に最も近かったときに教師が行なった行動要素である。ここでは、「グローバル表現」という用語を、ボードの場所を含む状態について用いるが、これは、この状態がグローバルなボードの座標情報を含むからである。この種のグローバル表現は暗黙のうちにボードレイアウトと一般的な状況とを符号化する。この内容の暗黙の符号化のために、学習された行動要素の選択とサブゴール生成の方策とを、異なるレイアウトのボードで用いることはできない。特許文献１に開示された、グローバル表現に基づいて動作するエージェントは、固定された課題については観察と実践からうまく高速に学習することができると分かったが、類似の課題に対する一般化はうまくいかなかった。
【００１１】
従って、エージェント又はロボットは異なる環境で動作する際にその行動を変更する能力を備えていなければならない。言換えれば、始めに人が実行するのをエージェントが観察して初期トレーニングを得た後は、エージェントはトレーニング環境と異なる環境においても実行することを通して課題に対する技量を増大させるべきである。
【００１２】
従って、この発明の目的は、たとえ環境が変わっても動作する際にエージェントがその行動を適切に変更することを可能にするエージェントコントローラ及びプログラムを提供することである。
【００１３】
この発明の別の目的は、たとえ環境が変わっても動作する際にエージェントがその行動を変更してよりよい結果を得ることを可能にするエージェントコントローラ及びプログラムを提供することである。
【課題を解決するための手段】
【００１４】
この発明の第一の局面に従えば、エージェントコントローラは、課題を遂行する間に、ある環境において観察されうる一組のパラメータによって規定される状態空間内のエージェントの現在位置と、エージェントを制御するための予め定められた一組の行動要素とに基づいて、エージェントに課題を遂行させるよう制御する。一組のパラメータは環境において場所ごとに異なる一組のグローバルパラメータと、環境において場所に関わらず同じであり得る一組のローカルパラメータとに分割されている。エージェントコントローラは、課題に関連する経験をデータ点の形で記憶するための手段を含む。データ点の各々は、実行される行動要素の種類と、行動要素が実行される際のローカルパラメータの組の値と、行動要素に関連する引数の値と、行動要素の実行終了の際のローカルパラメータの組の値とを含む。エージェントコントローラはさらに、課題におけるエージェントの環境を観察するための手段を含む。観察するための手段は、観察された環境に基づいてローカルパラメータの組の値を計算する。エージェントコントローラはさらに、観察するための手段によって計算されたローカルパラメータの組と、記憶するための手段に記憶された経験とに基づいて、実行すべき行動要素の種類を決定するための手段と、決定するための手段によって決定された行動要素の種類に関連する引数の値を、決定するための手段によって決定された行動要素と同じ種類の行動要素を有する、記憶するための手段に記憶されたデータ点の引数値からの所定のカーネル回帰によって計算するための手段と、計算するための手段によって計算された引数値を用いて、決定するための手段によって決定された種類の、エージェントを制御するための行動要素を実行するための手段と、行動要素を実行するための手段によって実行された種類の行動要素の実行の結果を評価して、課題において期待される報酬が最大に近づくように、強化学習を用いてカーネル回帰におけるデータ点に割当てられる重みを更新するための手段とを含む。重みは、経験、ローカルパラメータの組、及びグローバルパラメータの組を用いて計算される。
【００１５】
計算するための手段は、状態空間におけるエージェントの現在位置と、状態空間内の、決定するための手段によって決定されたのと同じ種類の行動要素を有するデータ点の各々との距離を計算するための手段と、状態空間において、他のデータ点よりもエージェントの現在位置に近い予め定められた数のデータ点を選ぶための手段と、選ぶための手段によって選ばれたデータ点の引数値から所定のカーネル回帰により、決定するための手段によって決定された行動要素の種類に関連する引数値を計算するための手段と、を含んでもよい。
【００１６】
この発明の第二の局面に従ったコンピュータプログラムは、コンピュータ上で実行されると、上記エージェントコントローラのいずれかのすべての手段としてそのコンピュータを機能させる。
【発明を実施するための最良の形態】
【００１７】
先行技術のロボットは、環境を観察して、「マーブルがこのボードのこの場所にあり、観察された速度でボードが観察された角度にあったとき、教師はどの行動要素を選択したか？」と問いかける。情報をより一般的な方法で用いることをゴールとするロボットは、「左手に壁があり、前方にコーナがあり、右手に穴があり、マーブルが所望の運動方向においてある速度を有し、ボードが、所望の方向へのマーブルの速度を増大させるように回転されているという状況にマーブルがあるとき、教師は何をしたか？」と問いかけるであろう。もしロボットが以前にこの状況で教師を観察し記録しており、その情報を適切に記憶していれば、この問合せに回答することが可能であろう。この種の表現を「ローカル表現」と呼ぶことにする。なぜなら、これらの表現は、典型的には、何かの対象物又はイベント、ここではマーブルにとって、空間的に局所的な特徴を表したものだからである。
【００１８】
グローバルな表現は、課題の状態空間内でも、場所ごとに異なる。ローカル表現は、異なる場所でも同じであろう。
【００１９】
この実施の形態はまた、マーブル迷路ゲームコントローラにも関連するものであって、特許文献１に開示された直接的な方策による学習において、ローカルな特徴を用いることに焦点を当てる。この実施の形態は、グローバル表現とローカル表現とをともに用いてどのようにより有効な一般化を行なうかを探索するものである。ローカル表現は新たなボードに技量を移転する助けとなり、グローバル表現は同じボードでの実践で技量を向上させる助けとなる。
【００２０】
[環境]
この発明の実施の形態は、現在の環境を視認して現在の状況を問合せ点としてパラメータ化するアルゴリズムを用いる。アルゴリズムは、環境の状態空間内の異なる場所のデータ点の内で、その状態空間の問合せ点に最も近いものを選択し、選ばれたデータ点に基づき実行すべき行動要素を決定し、決定された行為を実行する。その後アルゴリズムはその行為の結果を符号化するようなやり方で行動要素データベースを更新する。データ点は、学習過程で得られた特定された行動要素と関連のパラメータとを表し、データ点テーブルの形で記憶されるが、これについては後述する。このアルゴリズムはリアルタイムで実行され、データベースから検索された情報を用いて決定された行為を実行し、その結果に基づき、データベースに対して変更を加える。
【００２１】
マーブル迷路の環境で行動要素を選ぶ課題を例としてこのアルゴリズムを説明する。マーブル迷路において行動要素を実行した場合の結果は、先に進むこと、及び穴に落ちることを含み、行動要素が完了した時点で観察できる。選ばれたデータ点により決定される行為を実行して、たとえばボールが穴に落ちるという望ましくない結果に終わった場合、何らかの方法でこれを示さなければならない。将来も同じ状況で同じデータ点を選べば、同じ行為を実行し同じ望ましくない結果となってしまう筈である。将来、エージェント自身が、同じ状況になってとるべき行為を決定しなければならないとき、同じデータ点を選んではならないのである。
【００２２】
ここで説明する実施の形態は、マーブル迷路を例にとったものであるが、ここで説明される方法とプログラムとはヒューマノイドロボット等の他のシステムにも容易に適用可能である。
【００２３】
この課題では、プレイヤーはプラットフォームを傾けて、穴などの障害物を避けつつマーブルをゴールに向けて転がす。ゴールへの経路はボード上に印刷されているので、目的はゴールへの経路を見出すことではなく、マーブルをゴール位置まで経路に沿って迅速に移動させる行為を行なうことである。エージェント(ロボット）は、人がボードを制御し、迷路のレイアウトを通してマーブルを動かす様子を観察する。その後エージェントは、ボードを制御して、異なるレイアウトで、マーブルを開始点からゴール場所まで動かす。
【００２４】
テストベッドとして、マーブル迷路の課題のハードウェア版とソフトウェア版とを作成した（図２）。さまざまなプレイヤーの成果を比較できるように、経過時間を測定した性能評価基準を作成した。マーブルが穴に落ちるか、１０秒にわたって進まない場合は、マーブルは迷路中で先に進められ、プレイヤーにはさらに１０秒のペナルティが課される。ここでは、人手で定義した行動要素のライブラリを用いて、課題を観察し、類似の課題を実践することから行動要素を選択しサブゴールを生成する学習に焦点をあてることができるようにした。
【００２５】
図１は、ハードウェアで実現されたマーブル迷路環境を概略的に示す。この環境は、２個のノブ１４、１６を用いて傾けることのできるマーブルゲームボード１２を有するマーブル迷路ゲームボックス１０と、この発明の実施の形態を実現するコンピュータシステム２０と、ボックス１０上に置かれボード１２の方を向いて設けられ、ボード１２のビデオ信号をコンピュータシステム２０に与えるためのカメラ３０と、コンピュータシステム２０からのアクチュエータコマンドによって制御され、ボード１２を傾けるためのアクチュエータ（モータ）３２、３４とを含む。図１には示さないが、ノブ１４及び１６の軸には２個のエンコーダがそれぞれ設けられて、システムの学習段階及び評価段階でノブ１４及び１６の角度を検知し、対応の信号をコンピュータシステム２０に与える。
【００２６】
図２はソフトウェアのマーブルゲームボードとハードウェアのマーブルゲームボード１２とを示す。図２を参照して、ボード１２はマーブルボール７０がボード１２上を転がってぶつかったり落ちたりする壁７２と穴７４という形で設けられた障害物を持つ迷路を有する。ハードウェアのゲームのプレイヤーが行なうべきことは、２個のノブ１４、１６を用いてボード１２を傾けることによって、ボール７０を所定のコース線７６に沿って転がすことである。ソフトウェアゲームの場合、仮想的なボード１２はコンピュータのマウスで制御され、ボード１２上を転がるボールの動きはシミュレートされる。仮想ゲームは、壁との衝突を、見た目上、多大なエネルギの損失を伴うものとして取り扱う。マーブルボールの動きは、ボード１２を傾ける動き（又は傾き制御信号）に応答してシミュレートされ得る。
【００２７】
どちらの場合も、人がゲームを行なう際に、時間、ボード及びマーブルの位置が記録される。このシステムは、プレイヤーの動作を観察し、観察された動作中の行動要素を特定し、マーブルの位置及び速度、ノブ１４及び１６の動作角度等としてのボード１２の位置、マーブル７０の周囲のローカルな特徴、並びに関連のパラメータとともに、行動要素をデータ点として記憶する。ローカルな特徴とその表現の詳細は後述する。
【００２８】
人は、エンコーダに接続されたノブ１４及び１６を用いてハードウェア版のボードを制御する。エンコーダシステムによって生成されたモータコマンドをコンピュータが読み、モータに送る。マーブルの位置は、ニュートンラボのコグナクローム(Newtonlabs  Cognacrome)（登録商標）を用いて得られる。こうして、コンピュータシステム２０は人の動作を学習することができる。コンピュータシステム２０はまた、それ自身の判断でプレイするときには、それ自身のコマンドを生成してモータ３２及び３４に送ることもできる。
【００２９】
[ハードウェア構成]
図３はこの実施の形態に係る方法のハードウェア版を実現するコンピュータシステムを例示する。図４はシステムのブロック図である。仮想版のゲームが、図３及び図４に示すようなコンピュータによって実現できる。
【００３０】
図３を参照して、この実施の形態を実現するコンピュータシステム２０は、メモリポート５２及びＤＶＤ（デジタル多用途ディスク）ドライブ５０を有するコンピュータ４０と、いずれもコンピュータ４０に接続された、キーボード４６と、マウス４８と、モニタ４２とを含む。
【００３１】
図４を参照して、コンピュータ４０は、メモリポート５２及びＤＶＤドライブ５０に加えて、ＣＰＵ（中央処理装置）５６と、ＣＰＵ５６、ＤＶＤドライブ５０及びメモリポート５２に接続されたバス６６と、バス６６とカメラ３０とに接続されたビデオキャプチャボード６８と、ブートアッププログラム等を記憶する読出専用メモリ（ＲＯＭ）５８と、ＣＰＵ５６に接続され、アプリケーションプログラム命令、システムプログラム、データ点テーブル及び行動要素のためのデータベースを記憶するランダムアクセスメモリ（ＲＡＭ）６０とを含む。ＣＰＵ５６はさらにインターフェース（Ｉ／Ｆ）を介してエンコーダ３６及び３８並びにモータ３２及び３４に接続される。
【００３２】
ここでは示さないが、コンピュータ４０はさらに、ローカルエリアネットワーク（ＬＡＮ）への接続を提供するネットワークアダプタボードを含んでもよい。
【００３３】
コンピュータシステム２０をこの実施の形態のエージェントコントローラとして動作させるプログラムは、ＤＶＤドライブ５０又はメモリポート５２に挿入されるＤＶＤ６２又はメモリ６４に記憶されさらにハードディスク５４に転送されてもよい。これに代えて、プログラムは、図示しないネットワークを通じてコンピュータ４０に送信され、ハードディスク５４に記憶されてもよい。プログラムは実行の際にＲＡＭ６０にロードされる。プログラムはＤＶＤ６２、メモリ６４、又はネットワークを介してＲＡＭ６０に直接ロードされてもよい。
【００３４】
以下に説明するプログラムは、コンピュータ４０をこの実施の形態のエージェントコントローラとして機能させるための幾つかの命令を含む。この方法を行なわせるのに必要な基本的機能の幾つかはコンピュータ４０のオペレーティングシステム（ＯＳ）又はサードパーティのプログラム、若しくはコンピュータ４０にインストールされたモジュールにより提供されるので、このプログラムはこの実施の形態の方法を実現するのに必要な機能全てを必ずしも含まなくてよい。コンピュータシステム２０の動作は周知であるので、ここでは繰り返さない。
【００３５】
[基本的枠組]
図５はこの実施の形態に従ったシステム全体の枠組を示す。図５に示す通り、このシステムは、行動要素選択モジュール１５０と、サブゴール生成モジュール１５２と、行為生成モジュール１５４と、観察学習モジュール１５６と、実践学習モジュール１５８と、を含む。これらモジュールの組合せは特許文献１で用いたものと同様である。相違点は、これらのモジュールが環境のグローバル表現のみならずローカル表現も用いる点である。
【００３６】
[行動要素]
マーブル迷路ゲームの行動要素は、エージェントが課題を遂行するのに必要とするであろう技量をエージェントに授けるように設計される。以下の行動要素がこの実施の形態で用いられており、それらは図６から図１０に示されている。
【００３７】
コーナへ進む：図６に示すように、マーブル７０が壁に沿って転がり、別の壁７２に当たると停止する。
【００３８】
コーナ：図７に示すように、マーブル７０はコーナにあり、ボード１２はマーブル７０をコーナから動かすような位置に置かれる。
【００３９】
ガイド：図８に示すように、マーブル７０は壁に触れずに移動する。
【００４０】
壁から離れる：図９に示すように、マーブル７０が壁７２に接するか、当たってから、壁を離れて動く。
【００４１】
壁から落ちる：図１０に示すように、マーブル７０が壁７２に沿って転がり、端から落ちる。
【００４２】
[ローカル表現]
多くの可能な選択肢の中から、もしマーブルの場所にいてあたりを見回したとすれば見えるであろう特徴を記録した、マーブル迷路のローカル表現を設計した。マーブルがとるべきおおよその経路がボード上に印刷されており、これを利用して、マーブルがとり得る全ての場所の２Ｄ表を初期化し、各セルにゴールまでの距離を記録した。所望される移動方向を、近接するセルの値を観察することによって迷路のいずれかの点から計算した。
【００４３】
マーブルの移動方向は迷路の壁に対し平行と直交の４つの方向に離散化されている。すなわち、前進（所望の移動方向）、後退、左、右である。この実施の形態では、４方向の特徴とともに、所望の移動方向に対するマーブルの速度とボードの位置（ボードの傾き角度）とを用いた。図１２は迷路内の様々な特徴の場所（穴、壁、コーナ、壁の端、及び壁の縁）を示す。
【００４４】
この実施の形態のエージェントは人によるボードの操作を観察し、その操作のための行動要素を特定し、特定した行動要素と、グローバル表現の形のボード及びマーブルの位置並びにマーブルの速度と、グローバル表現から計算されたローカルな特徴と、その関連の引数とを、データ点テーブルとして記憶する。この表はＲＡＭ６０に維持されてもよい。観察された操作から行動要素を特定する方法はこの発明の一部を構成するものではないので、ここでは詳細に説明しない。
【００４５】
[システム構成]
図１１はこの実施の形態に従ったマーブル迷路制御システム１７０の全体のシステム構成を示す図であって、これは図１に示したコンピュータシステム２０で実現される。図１１を参照して、マーブル迷路制御システム１７０は、マーブル迷路の構成を記述した情報を記憶するための迷路構成記憶部１８０と、ボード１２に設置されたカメラ３０及びエンコーダ３６並びに３８の出力を受けるように接続され、カメラ３０及びエンコーダ３６並びに３８からの映像信号とエンコーダ信号とを受けてボード１２上のマーブルの位置及びボード１２の角度を出力するマーブル位置キャプチャモジュール１８２と、マーブル位置キャプチャモジュール１８２の出力を受けるように接続され、マーブル位置キャプチャモジュール１８２の出力を記憶部１８０に記憶された迷路構成と組合せてマーブル迷路ゲームの状態のグローバルな表現を出力するための組合せモジュール１８４とを含む。
【００４６】
マーブル迷路制御システム１７０はさらに、組合せモジュール１８４の出力を受けるように接続され組合せモジュール１８４から出力されるグローバル表現と記憶部１８０に記憶された迷路構成情報とに基づいてマーブル迷路ゲームの状態のローカル表現を生成するためのローカル表現生成モジュール１８６と、組合せモジュール１８４の出力を受けるように接続され、選択された行動要素の性能を観察しかつ評価するとともに、観察された性能を出力する観察モジュール１８８と、マーブル位置キャプチャモジュール１８２からのローカル表現と観察モジュール１８８からの選択された行動要素の観察された性能とを受けるように接続され、「強化学習」方法に従って、後述する行動要素データベースを更新するための更新モジュール１９０と、行動要素データベースを記憶するための行動要素データベース記憶部１９４とを含む。
【００４７】
行動要素データベースは、後述するデータ点テーブルを含む。
【００４８】
マーブル迷路制御システム１７０はさらに、マーブル迷路ゲームの現在の状態のローカル表現を受けるように接続され、これを行動要素データベース１９４に記憶されたデータ点と比較し、マーブル迷路ゲームの現在の状態に対し好適な種類の行動要素を選択する比較選択モジュール１９２と、比較選択モジュール１９２によって選択された種類の行動要素を受けるように接続され、選択された種類の行動要素に対する引数を生成してマーブルの好適な動きを達成するためのサブゴール生成モジュール１９６と、サブゴール生成モジュール１９６によって生成された引数とその種類の行動要素とを受けるように接続され、モータ３２及び３４を駆動するための駆動出力信号を生成するボードコントローラ１９８とを含む。
【００４９】
図１３を参照して、迷路構成記憶部１８０に記憶された迷路構成情報２００は、図１２に示されたようなボード１２の各穴の場所と直径とを特定する穴データ２１０と、ボード１２の壁の各々の厚さと、中心線の開始場所及び終端場所とを特定する壁データ２１２と、迷路のスタート位置２１４及びゴール位置２１６、さらにスタート位置からゴール位置までの経路を特定する「ゴールへの経路」データ２１８とを含む。
【００５０】
図１４及び図１５は迷路の様々な場所での符号化を示す。迷路構成の各々は開始場所から終端場所への経路を含んでいる。この経路を用いて、前進方向を決定する所望の移動方向を計算する。符号化の際に、横方向、すなわち左右は、前進後退方向とは異なって扱われる。壁終端という特徴は、横方向のみについて計算される。もし２×マーブルの半径の距離以内で横方向に壁が見えた場合には、所望の運動方向におけるその壁に沿った特徴（コーナ、穴、又は壁終端）もまた記録される。ローカル表現は、所望の移動方向に関連したボード位置とボールの速度とともに、４方向での特徴を含む。
【００５１】
このローカル表現は、プレイヤーが課題を遂行するのを観察する間に、経験を記憶し、とられた行為を符号化するために用いられる。観察された行動要素の性能の各々について、ローカル状態情報が、実行された行動要素の種類、マーブルの動き、マーブルの速度及び行動要素終了時のボードの位置とともに記録される。
【００５２】
図１６を参照して、この実施の形態のテーブル８０の各データ点のエントリは、所望される移動方向を基準としたローカル座標フレームでのボード位置（Ｂｘ，Ｂｙ）及びマーブル速度（ｕ，ｖ）と、行動要素種類ＴＹＰＥと、行動要素の動作を行なうのに必要とされる引数と、行動要素の開始からのマーブルの位置変化と、ローカル特徴Ｆ，Ｌ，Ｂ及びＲと、を含む。マーブル速度とボード位置とは、行動要素の開始と行動要素の終了の各々について記憶される。これらのローカル特徴は、それぞれ前進（所望の移動方向）、左、後退及び右方向の特徴を示す。これらのローカル特徴は、後述するローカル表現中のローカル状態間の距離を計算するのに用いられる。
【００５３】
データ点はまた、グローバル状態によって指示することができる値を含むデータ構造：すなわち、マーブル位置（ｘ,ｙ）と、マーブル速度（ｕＧ，ｖＧ）と、ボード位置（ＢＸＧ，ＢＹＧ）とを含み、これらは全てボード１２上のＸ−Ｙ座標で表される。マーブル位置、マーブル速度及びボード位置は、後述するグローバル表現の距離の計算で用いられるベクトルを形成する。ＴＹＰＥは上に挙げた５個の行動要素のうちの一つである。
【００５４】
テーブル８０の構造はマーブル迷路ゲームでの単なる一例であって、この発明の方法を他の応用、例えばエアホッケーゲーム等に適用する場合には、これと異なっていても良い。
【００５５】
[計算上の振舞]
エージェントは、計算上の振舞にメモリベースの手法を用い、過去の経験を参照しその情報を用いて決定の指針とする。行動要素の種類は、最も近い隣接するものを用いて選択され、行動要素の引数はカーネル回帰を用いて生成される。エージェントの行動は、データ点がどのように選択され重み付けされるかによって定められる。
【００５６】
この実施の形態では、データ点は８個の入力次元を有する（マーブル速度（ｕ，ｖ）、ボード位置（Ｂｘ，Ｂｙ）、及び４個のローカル特徴Ｆ，Ｌ，Ｂ及びＲ）。各データ点はまた、グローバル環境状態によって指示された数を記憶するデータ構造（表）を含む。ここで目標とするところは、最適な解を見出すことではなく、観察された情報に対して良好な解を見出すことであるから、探訪すべきセルはごく一部である。従って、表は疎な配列として記憶されるだけで、セルが実際に生成されるのはセルの値が初めて更新されるときになってである。それまでは、各セルは初期化ステップで与えられた一定の値を持つものとみなされる。この表に記憶された値は次のセクションで説明する。
【００５７】
特許文献１で用いられるグローバル表現では、各データ点ｘｊの問合せ点ｑからのユークリッド距離ｄは以下のように計算され、ここでベクトルｘ＝(ｘ１ｘ２…ｘｋ）及びｑ（ｑ１ｑ２…ｑｋ）はそれぞれ状態空間におけるデータ点及び問合せ点の場所であり、重みベクトルｗ＝（ｗ１ｗ２…ｗｋ）は各次元の重み付けを可能にする。
【００５８】
【数１】
2008090606.tif 000003
グローバル表現でのデータベースへの問合せは環境の現在の状態の表現である。すなわちマーブル位置（ｘＧ，ｙＧ）、速度（ｕＧ，ｖＧ）、及びボード位置（ＢｘＧ，ＢｙＧ）である。先の調査では、グローバル表現で用いられる典型的な重みは、位置、速度及びボード位置についてそれぞれ１００．０、１．０及び１．０であった。
【００５９】
この実施の形態では、ローカル表現スキームについて距離も同様に計算された。従って、同じメモリベースのアルゴリズムを使用することができる。マーブル速度（ｕ，ｖ）、ボード位置（Ｂｘ，Ｂｙ）、及び４方向の特徴Ｆ，Ｌ，Ｂ及びＲを用いて、距離の値が計算される。
【００６０】
この実施の形態では、２つの状況間での特徴の相違を表す値が、一致する特徴の数を比較することによって計算される。一致する特徴の数を可能な一致の数で割る。この実施の形態で用いられる表現では、合計４個の特徴がある。従って、特徴空間での相違は０．０、０．２５、０．５、０．７５又は１．０であり得る。ここで０．０は一致がないことを意味し、１．０は全ての方向の特徴が一致することを意味する。
【００６１】
問合せベクトルｑを計算するために、エージェントは現在の所望の移動方向を計算し、全ての方向の特徴の位置を特定し、マーブルの速度（ｕＧ，ｖＧ）、及びボード位置（ＢｘＧ，ＢｙＧ）をローカルな基準に変換する。考慮されるデータ点の数は、データ点によって特定される行動要素の種類が、現在マーブルの置かれている状況に適用可能か否かを確認することで減じられる。例えば、もしデータ点が「コーナへ進む」行動要素を特定しており、現在の状況で該当するコーナがない場合は、このデータ点は考慮されない。
【００６２】
最も近いデータ点によって特定される行動要素が、現在の状況でどの種の行動要素を用いるべきかを決定する。その後エージェントは、ボールがどこに転がっていくか、また行動要素の完了時にその速度はどれくらいであるか、といったサブゴール情報を計算する。壁の終端及びコーナといった現在利用可能なローカル特徴の場所は、「壁から落ちる」行動要素及び「コーナへ進む」行動要素の終端場所を特定するのに用いられる。同じ種類の行動要素のうち、最も近いデータ点が、所望されるマーブル速度（ｕ，ｖ）及びボード位置角度（Ｂｘ，Ｂｙ）を含む他のサブゴール引数を計算するのに用いられる。多数のデータ点の結果が、以下のカーネル回帰によって組合される。
【００６３】
【数２】
2008090606.tif 000004
ここでＫ（ｄ）はカーネル関数であって、典型的には以下の通りである。
【００６４】
【数３】
2008090606.tif 000005
ここでｄは問合せ点と現在の点との差を表し、パラメータδは近接するデータ点の影響を決定し、Ｎは回帰に用いられるデータ点の数を表す。＾ｙ（式中では＾はｙの上に付される。）の推定値は問合せ点ｑの場所に依存する。
【００６５】
[実践による性能の向上]
この課題を実践しつつ学習するために、行動要素の選択とサブゴールの生成の両者でなされる最も近い隣接するものの参照で用いられる距離関数を変更するメカニズムを付加した。
【００６６】
値の関数、実際にはＱ関数の推定値を用いて、現在の課題の状態である特定の行動要素を選んだ場合の帰結を表す。Ｑ関数は、引数として現在の課題の状態ｓと行為とをとる。この場合、行為とは、記憶された点ｘｉからの情報を用いると選択することである。グローバル状態ｓでデータ点ｘｉを選ぶことは、この状態でとられる行為と直接関係しており、従って、Ｑ（ｓ，ｘｉ）はＱの値を符号化する。この場合、報酬を最大化していることになり、この値Ｑを用いて距離のスケールファクタを計算する。
【００６７】
【数４】
2008090606.tif 000006
ここでＣはＱの初期値であり、βは乗数に対するＱの影響を制御する。ｑはローカル表現の問合せ状態であり、ｓはグローバル表現の状態である。データ点ｘｉはローカル表現を用いて符号化される。式（１）のｄ（ｘｉ,ｑ）を＾ｄ（ｘｉ,ｑ,ｓ）（式中＾はｄの上に付される。）と置換することにより、スケールファクタは、記憶された経験を問合せ点に対して移動させる効果を有することになる。１．０より大きいスケールファクタは、データ点を問合せ点から遠くへ移動させる効果を有し、１．０より小さいスケールファクタは、データ点を問合せ点の近くへ移動させる効果を有する。例えば、もしある組のデータ点で選択された行動要素を実行したあとマーブルが穴に落ちれば、その組のデータ点に関連する乗数を増加させることができる。次にエージェントが同じ状態にあることを発見した場合、これらのデータ点はより遠くに現れ、従って選ばれた行為に対する効果はより少なくなるはずである。この式は、エージェントに、行為を選ぶ際にローカル情報とグローバル情報との両者を用いる能力を与える。
【００６８】
Ｑ学習では、将来とりうる行為の結果を考慮に入れることによって、その値が更新される。Ｑの値は定数によって初期化され、その後、Ｑ学習の修正版を用いて更新される。この詳細は、Ｒ．サットン及びＡ．バルト、強化学習：序論、ＭＩＴプレス、１９９８年（R.Sutton  and  A.  Barto,  Reinforcement  Learning:  An  Introduction.  MIT  Press,  1998）に記載されている。状態ｓで選ばれたデータ点ｘｍの各々について、Ｑの値は各行動要素の実行の完了時に以下のように更新される。
【００６９】
【数５】
2008090606.tif 000007
ここで、αは学習率である。多数の点が用いられるため、以下で与えられる重みを学習率として用いる。
【００７０】
【数６】
2008090606.tif 000008
この重み付けは、最も高い学習率を有する行動要素を選択することに最も貢献する点を持つ、という効果を有する。
【００７１】
ｒは行動要素が実行された後に観察される報酬である。
【００７２】
γはディスカウント率である。
【００７３】
ｍａｘＱ（＾ｓ，＾ｘ）は新しい状態＾ｓと、次のステップでデータ点＾ｘを選択することから予想されうる将来の報酬である。（式中＾はそれぞれ後続する文字の上に付される。）この値は以下で与えられる。
【００７４】
【数７】
2008090606.tif 000009
[ソフトウェア構成]
図１７はこの実施の形態の方法を実現するためにコンピュータシステム２０（図１）のＣＰＵ５６によって実行されるメインプログラムの全体の制御構造を示す。図１７を参照して、メインプログラムは、データポイントのセルの数が定数で初期化される初期化ステップ１００と、カメラ３０によってキャプチャされた像とエンコーダ３６及び３８からの信号出力とが評価され、環境状態が問合せ点として特定される環境状態視認ステップ１０２とを含む。
【００７５】
ステップ１０４では、問合せ点とデータ点との間の特徴の相違を現す値が、各データ点について整合する特徴の数を比較することによって計算され、整合する特徴の数が最大であると特定されたデータ点が特定される。その後ステップ１０６で、ステップ１０４で選択されたデータ点の行動要素の種類が、次に行なわれるべき行動要素として選ばれる。
【００７６】
次に、ステップ１０８で、問合せ点に最も近く選択された行動要素と同じ種類の行動要素を有する、予め定められた数のデータ点が現在の問合せ点に対して選ばれる。図１８を参照して、問合せ点１３０と同じ種類の行動要素（濃い黒で示す）を有するデータ点の各々とのユークリッド距離が、４次元（マーブル速度（ｕ，ｖ）及びボード位置（Ｂｘ，Ｂｙ））を用いて計算され、このステップで、最も短い距離を有する予め定められた数のデータ点が選ばれる。図１８では、問合せ点１３０の周囲の５個の点１４０、１４２、１４４、１４６及び１４８が選ばれる。図１８は簡潔のため、多次元の状態空間を２次元の座標システムで簡略に表したものであることに注意されたい。
【００７７】
ステップ１１０で、ステップ１０８で選ばれた５個のデータ点１４０、１４２、１４４、１４６及び１４８が、選択された種類の行動要素を実行するための引数を計算するのに用いられる。この実施の形態では、選択された行動要素の種類のための引数はカーネル回帰によって計算される。
【００７８】
ステップ１１２で、ステップ１１０で計算された引数を用い、引数をそれぞれモータ３２及び３４のドライバソフトウェアに出力することにより、決定された種類の行為（行動要素）が行なわれる。ハードウェア版ではモータコマンドがコンピュータシステム２０（図１）からモータ３２及び３４に出力され、仮想版ではボード１２の動きがシミュレートされる。
【００７９】
ステップ１１４で、ハードウェア版ではカメラ３０によってキャプチャされた像が視認され、エンコーダ信号がキャプチャされるので、報酬が決定され、ステップ１１２で行なわれた行為が評価される。仮想版では、マーブルの動きがシミュレートされ、結果が評価される。
【００８０】
ステップ１１６で、ステップ１０８で選ばれたデータ点のセルに関連した数が上述の式（１）により更新される。
【００８１】
上述の通り、この実施の形態の方法とプログラムは、環境状態空間において異なる場所からデータ点を選んだ結果が符号化されるようなやり方で行動要素データベースを更新する。プログラムはリアルタイムで実行され、行為を行なった結果に基づいてデータベースを変更する。更新されたデータベースを用いると、次にエージェントが同じ状況にあることを見出した場合には、その行動は前回とは異なったものとなり、その結果はより好ましいものとなるはずである。
【００８２】
行なわれるべき行動要素の種類及びそれに関連する引数が、システムの状態のローカル表現を用いて選択され計算されるため、この実施の形態に従ったエージェントは他の環境に対し一般化を行なうことができる。例えば、マーブル迷路ゲームでは、ボードの構成が変更された場合でも、観察と実践により迅速に学習することができる。
【００８３】
上で説明した通り、この発明に従ったエージェント又はロボットは異なる環境で動作する際にその行動を変更する能力を有する。言換えれば、エージェントが人の行為を観察して初期トレーニングを受けた後では、たとえトレーニング環境と異なる環境にあっても、エージェントは課題を遂行することによってその技量を向上させることができるはずである。
【００８４】
今回開示された実施の形態は単に例示であって、本発明が上記した実施の形態のみに制限されるわけではない。本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味及び範囲内でのすべての変更を含む。
【図面の簡単な説明】
【００８５】
【図１】ハードウェア版で実現されたこの発明の実施の形態の環境の概略図である。
【図２】ソフトウェア版及びハードウェア版でのマーブル迷路ボードの斜視図である。
【図３】この発明の一実施の形態を実現するコンピュータシステムの正面図である。
【図４】図３に示すコンピュータシステムのブロック図である。
【図５】この発明の実施の形態に従ったシステム全体の枠組を示す図である。
【図６】「コーナへ進む」行動要素を示す概略図である。
【図７】「コーナ」行動要素を示す概略図である。
【図８】「ガイド」行動要素を示す概略図である。
【図９】「壁から離れる」行動要素を示す概略図である。
【図１０】「壁から落ちる」行動要素を示す概略図である。
【図１１】この発明の一実施の形態に従ったマーブル迷路制御システム１７０の機能的構造を示すブロック図である。
【図１２】実施の形態に従った迷路内の特徴（穴、壁、コーナ、壁の終端、壁の縁）の様々な場所を示す図である。
【図１３】迷路構成情報の構造を示す図である。
【図１４】ローカル特徴の符号化を例示するための、迷路の様々な場所を示す図である。
【図１５】図１４に示された場所の各々について特徴を列挙した図である。
【図１６】データ点のローカル特徴とグローバル特徴とを符号化したデータ点テーブル８０の構造を示す図である。
【図１７】この発明の実施の形態のプログラムのフローチャートである。
【図１８】問合せ点に最も近い決定された種類の行動要素の選択されたデータ点を示す概略図である。
【符号の説明】
【００８６】
１０     マーブル迷路ゲームボックス
１２     マーブルゲームボード
１４及び１６      ノブ
２０     コンピュータシステム
３０     カメラ
４０     コンピュータ
３２及び３４      モータ
７０     マーブル
７２     壁
７４     穴
７６     コース線
８０     データ点テーブル
１３０   問合せ点
１４０−１４８    データ点
１７０   マーブル迷路制御システム
【図１】
2008090606.tif 000010
【図２】
2008090606.tif 000011
【図３】
2008090606.tif 000012
【図４】
2008090606.tif 000013
【図５】
2008090606.tif 000014
【図６】
2008090606.tif 000015
【図７】
2008090606.tif 000016
【図８】
2008090606.tif 000017
【図９】
2008090606.tif 000018
【図１０】
2008090606.tif 000019
【図１１】
2008090606.tif 000020
【図１２】
2008090606.tif 000021
【図１３】
2008090606.tif 000022
【図１４】
2008090606.tif 000023
【図１５】
2008090606.tif 000024
【図１６】
2008090606.tif 000025
【図１７】
2008090606.tif 000026
【図１８】
2008090606.tif 000027
【外国語明細書】
2008090606000001.pdf
2008090606000002.pdf
2008090606000003.pdf
2008090606000004.pdf