(57)【要約】【課題】エージェントがある環境内で動作する際に、その挙動を適切に変更することを可能にする。【解決手段】エージェントコントローラは、状態空間内の問合せ点を特定するモジュール１０２と、問合せ点に最も近いデータ点を選ぶモジュール１０４と、モジュール１０４によって選ばれたデータ点に基づき、エージェントが行なうべきプリミティブを選択するモジュール１０６と、選択されたデータ点のパラメータの組に基づき、選択されたプリミティブのためのパラメータを計算するモジュール１０８と、選択された行為をエージェントに実行させるモジュール１１０と、行為の結果を評価するモジュール１１２と、結果を反映するようにデータ点の値を更新するモジュール１１４とを含む。【選択図】        図１２
2004163992.tif 000002
【特許請求の範囲】
【請求項１】
所定の状態空間内のエージェントの位置および一組の予め定められたプリミティブに基づいてエージェントを制御するエージェントコントローラであって、
多数のエントリを有するプリミティブデータベースを記憶するための手段を含み、各エントリはプリミティブと、前記所定の状態空間内でそのエントリに対応するデータ点の位置と、プリミティブを実行するための一組のパラメータと、データ点に割り当てられたデータ点値とを含み、前記コントローラはさらに、
前記所定の状態空間内のエージェントの位置を問合せ点として特定するための手段と、
前記問合せ点と所定の関係を満足するデータ点を有する、プリミティブデータベース内の複数のエントリを選ぶための手段とを含み、前記所定の関係は前記所定の状態空間における前記問合せ点とデータ点との見かけ上の距離およびそのデータ点に割り当てられるデータ点値によって規定され、前記コントローラはさらに、
前記選ぶための手段によって選ばれた前記複数のエントリのプリミティブに基づいてエージェントによって実行されるプリミティブを選択し、前記複数のエントリのうち選択されたプリミティブと同じプリミティブを有するエントリを選択するための手段と、
前記選択されたプリミティブを有する前記選択されたエントリの一組のパラメータに基づき、前記選択されたプリミティブの一組のパラメータを計算するための手段と、
前記計算するための手段によって計算された一組のパラメータで、前記選択されたプリミティブに従った行為をエージェントに実行させるための手段と、
前記行為の結果を評価するための手段と、
前記選択されたエントリのデータ点に割り当てられたデータ点値を、前記評価するための手段による評価を反映するように更新して、前記行為の結果が肯定的であれば次に計算される見かけの距離が短くなり、前記行為の結果が否定的であれば長くなるようにするための手段とを含む、エージェントコントローラ。
【請求項２】
前記選ぶための手段は
前記所定の状態空間内の幾つかのデータ点の各々と前記問合せ点とのユークリッド距離を計算するための手段と、
前記ユークリッド距離を、幾つかのデータ点に割り当てられたそれぞれのデータ点値を用いて規定されたそれぞれのデータ点値により、乗算するための手段と、
乗算された距離が他のデータエントリのそれよりも小さい所定数のエントリを選ぶための手段とを含む、請求項１に記載のエージェントコントローラ。
【請求項３】
前記状態空間は各データ点付近において前記状態空間の小区域の周りのセルに量子化され、
各セルにはセル値が割り当てられ、
前記乗算するための手段は、
前記問合せ点を含む幾つかのデータ点の周囲のセルを選択するための手段と、選択されたセルに割り当てられたそれぞれのセル値を用いて規定される乗算係数でユークリッド距離を乗算するための手段とを含む、請求項２に記載のエージェントコントローラ。
【請求項４】
乗算係数はセルに割り当てられたセル値の関数であり、
関数の値はセル値が増加すると減少する、請求項３に記載のエージェントコントローラ。
【請求項５】
データ点値を更新するための手段は以下の関数に従ってデータ点値を更新し、
【数１】
2004163992.tif 000010
ここでＱｔ（ｑｔ，ｘｍ）は時間ｔで選択されたエントリのデータ点を表し、αはあるデータ点と問合せ点との距離の所定の関数として計算される学習率であり、ｒは行為が行なわれた後に観察される報酬であって、行為が好ましいものであれば正の値をとりそうでなければ負の値をとり、＾ｑおよび＾ｘは次の時間ステップでの新しい状態およびデータ点であり、Ｑｔ＋１（＾ｑ，＾ｘ）は以下の式で与えられ、
【数２】
2004163992.tif 000011
ここでＫ（ｄ（ａ，ｂ））はｄ（ａ，ｂ）＝０のとき最大値を有するカーネル関数であり、ｄ（ａｂ）が増加するにつれて単調にゼロに向かって減少し、ｄ（ａ ｂ）はデータ点ａと問合せ点ｂとの間のユークリッド距離である、請求項１に記載のエージェントコントローラ。
【請求項６】
αは以下の式で与えられ
【数３】
2004163992.tif 000012
ここでｄ（ｘｉ，ｑｔ）は時間ステップｔでのデータ点ｘｉと問合せ点ｑｔとの間のユークリッド距離である、請求項５に記載のエージェントコントローラ。
【請求項７】
コンピュータを、所定の状態空間内のエージェントの位置および一組の予め定められたプリミティブに基づいてエージェントを制御するエージェントコントローラとして動作させるための、コンピュータで実行可能なエージェント制御プログラムであって、前記エージェントコントローラは、
多数のエントリを有するプリミティブデータベースを記憶するための手段を含み、各エントリはプリミティブと、前記所定の状態空間内でそのエントリに対応するデータ点の位置と、プリミティブを実行するための一組のパラメータと、データ点に割り当てられたデータ点値とを含み、前記コントローラはさらに、
前記所定の状態空間内のエージェントの位置を問合せ点として特定するための手段と、
前記問合せ点と所定の関係を満足するデータ点を有する、プリミティブデータベース内の複数のエントリを選ぶための手段とを含み、前記所定の関係は前記所定の状態空間における前記問合せ点とデータ点との見かけ上の距離およびそのデータ点に割り当てられるデータ点値によって規定され、前記コントローラはさらに、
前記選ぶための手段によって選ばれた前記複数のエントリのプリミティブに基づいてエージェントによって実行されるプリミティブを選択し、前記複数のエントリのうち選択されたプリミティブと同じプリミティブを有するエントリを選択するための手段と、
前記選択されたプリミティブを有する前記選択されたエントリの一組のパラメータに基づき、前記選択されたプリミティブの一組のパラメータを計算するための手段と、
前記計算するための手段によって計算された一組のパラメータで、前記選択されたプリミティブに従った行為をエージェントに実行させるための手段と、
前記行為の結果を評価するための手段と、
前記選択されたエントリのデータ点に割り当てられたデータ点値を、前記評価するための手段による評価を反映するように更新して、前記行為の結果が肯定的であれば次に計算される見かけの距離が短くなり、前記行為の結果が否定的であれば長くなるようにするための手段とを含む、プログラム。
【請求項８】
前記選ぶための手段は
前記所定の状態空間内の幾つかのデータ点の各々と前記問合せ点とのユークリッド距離を計算するための手段と、
前記ユークリッド距離を、幾つかのデータ点に割り当てられたそれぞれのデータ点値を用いて規定されたそれぞれのデータ点値により、乗算するための手段と、
乗算された距離が他のデータエントリのそれよりも小さい所定数のエントリを選ぶための手段とを含む、請求項７に記載のプログラム。
【請求項９】
前記状態空間は各データ点付近において前記状態空間の小区域の周りのセルに量子化され、
各セルにはセル値が割り当てられ、
前記乗算するための手段は
前記問合せ点を含む幾つかのデータ点の周囲のセルを選択するための手段と、選択されたセルに割り当てられたそれぞれのセル値を用いて規定される乗算係数でユークリッド距離を乗算するための手段とを含む、請求項８に記載のプログラム。
【請求項１０】
乗算係数はセルに割り当てられたセル値の関数であり、
関数の値はセル値が増加すると減少する、請求項９に記載のプログラム。
【請求項１１】
データ点値を更新するための手段は以下の関数に従ってデータ点値を更新し、
【数４】
2004163992.tif 000013
ここでＱｔ（ｑｔ，ｘｍ）は時間ｔで選択されたエントリのデータ点を表し、αはあるデータ点と問合せ点との距離の所定の関数として計算される学習率であり、ｒは行為が行なわれた後に観察される報酬であって、行為が好ましいものであれば正の値をとりそうでなければ負の値をとり、＾ｑおよび＾ｘは次の時間ステップでの新しい状態およびデータ点であり、Ｑｔ＋１（＾ｑ，＾ｘ）は以下の式で与えられ、
【数５】
2004163992.tif 000014
ここでＫ（ｄ（ａ，ｂ））はｄ（ａ，ｂ）＝０のとき最大値を有するカーネル関数であり、ｄ（ａｂ）が増加するにつれて単調にゼロに向かって減少し、ｄ（ａ ｂ）はデータ点ａと問合せ点ｂとの間のユークリッド距離である、請求項７に記載のプログラム。
【請求項１２】
αは以下の式で与えられ
【数６】
2004163992.tif 000015
ここでｄ（ｘｉ，ｑｔ）は時間ステップｔでのデータ点ｘｉと問合せ点ｑｔとの間のユークリッド距離である、請求項１１に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、エージェントが環境中で動作する際にその挙動を変更することを可能にする方法およびプログラムに関し、特に、エージェントが動作するときにプリミティブを観察することで好適な解決策を学習することを可能にする方法およびプログラムに関する。
【０００２】
【従来の技術】
高性能コンピュータの発展に伴い、広範な分野で、コンピュータがごく短時間に大量の情報を取扱う能力が開発されつつある。典型的な例の一つは、リアルタイムで人と対話することのできるロボットである。別の例は、コンピュータまたはコンピュータネットワークに常駐して人と対話し、それ自身の判断で活動することのできるコンピュータプログラムである。この出願では、このようなロボットまたはプログラムを「エージェント」と呼ぶこととする。
【０００３】
人とエージェントとのこのようなリアルタイムの対話を実現するには、エージェントがカメラまたは一組のカメラを用いて人とその行為とを観察する能力が必要な前提条件である。人とその行為とを観察することができ、その観察にもとづいて、他者の行為にどのように反応すべきかを学習できるシステムには大いに利益がある筈である。
【０００４】
行為とパラメータとを選ぶことを学習する現在の方法は、ほとんどが強化学習を用い、以下のステップを含む。
【０００５】
ロボットが起立を学習する課題において、サブゴールを学習し、そのサブゴールを得るための行為を学習するステップ［１］［２］［３］、および
エージェントがある環境で動作する際に、シミュレーションブロックワールドにおいてゴールへと移動するようエージェントに学習させるステップ。
【０００６】
このような問題への解決策の一つは、「プリミティブを用いた観察からの学習」アプローチである。プリミティブとは、ある課題の小部分に対する解決策であって、それらを組合わせることによってその課題を完成することができるようなもののことをいう。ある課題の解決策は、多くのプリミティブから構成されることになる。たとえば、エアホッケーの環境では、パックを打つ、パックを捕らえる、ゴールを守る等のプリミティブがあるだろう。多くの場合、一つのプリミティブをさらにより小さいプリミティブに分けることができる。
【０００７】
現段階では、ある特定の課題に用いられるプリミティブの候補は人が設計できる。エージェントのための観察からの学習用フレームワークは、観察された挙動を選ばれたプリミティブに分離するためのプリミティブ認識モジュールと、観察された環境状態について行なうべきプリミティブの種類をエージェントに与えるためのプリミティブ選択モジュールと、その種類のプリミティブを行なうことにより望まれる結果、すなわちゴールを特定するサブゴール生成モジュールと、現在のゴールに対し選ばれた種類のプリミティブを実行するのに必要なアクチュエータコマンドを見出すための行為生成モジュールとを含むであろう。
【０００８】
プリミティブ認識モジュールは、観察された挙動を人が選んだプリミティブに分離する。この分離されたデータを用いて、プリミティブ選択、サブゴール生成、および行為生成のためのトレーニングデータを得る。プリミティブ選択モジュールは観察された環境状態について行なうべきプリミティブの種類をエージェントに与える。その種類のプリミティブを行なう際のゴールは、サブゴール生成モジュールによって決められる。最後に、所望の結果を得るため、アクチュエータを動作させなければならない。行為生成モジュールが、現在のゴールについて選ばれた種類のプリミティブを実行するのに必要なアクチュエータコマンドを探し出す。
【０００９】
［参考文献］
［１］  Ｊ．モリモトおよびＫ．ドウヤ著、「低い次元のサブゴールと高い次元の軌跡との階層的強化学習」、第５回神経情報処理会議予稿集、第２巻、１５８０−８５３頁、１９９８年（Ｊ．  Ｍｏｒｉｍｏｔｏ  ａｎｄ  Ｋ．  Ｄｏｙａ．  Ｈｉｅｒａｒｃｈｉｃａｌ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ  ｏｆ  ｌｏｗ−ｄｉｍｅｎｓｉｏｎａｌ  ｓｕｂｇｏａｌｓ  ａｎｄ  ｈｉｇｈ−ｄｉｍｅｎｓｉｏｎａｌ  ｔｒａｊｅｃｔｏｒｉｅｓ．  Ｉｎ  Ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ，  Ｖｏｌ．  ２，  ｐｐ．  １５８０−８５３，  １９９８．）
［２］  Ｊ．モリモトおよびＫ．ドウヤ著、［動的モータシーケンスにおける強化学習：起立の学習」、ＩＥＥＥ／ＲＳＪ知的ロボットおよびシステムに関する国際会議予稿集、第３巻、１７２１−１７２６頁、１９９８年（Ｊ．  Ｍｏｒｉｍｏｔｏ  ａｎｄ  Ｋ．  Ｄｏｙａ．  Ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ  ｏｆ  ｄｙｎａｍｉｃ  ｍｏｔｏｒ  ｓｅｑｕｅｎｃｅ：  Ｌｅａｒｎｉｎｇ  ｔｏ  ｓｔａｎｄ  ｕｐ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ／ＲＳＪ ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ ａｎｄ Ｓｙｓｔｅｍｓ，  Ｖｏｌ．  ３，  ｐｐ．  １７２１−１７２６，  １９９８．）
［３］  Ｊ．モリモトおよびＫ．ドウヤ著、「階層的な強化学習を用いた、実際のロボットによる起立動作の獲得」、ロボティックス・アンド・オートノマス・システムズ、第３６巻、３７−５１頁、２００２年（Ｊ．  Ｍｏｒｉｍｏｔｏ  ａｎｄ  Ｋ．  Ｄｏｙａ．    Ａｃｑｕｉｓｉｔｉｏｎ  ｏｆ  Ｓｔａｎｄ−ｕｐ  Ｂｅｈａｖｉｏｒ  ｂｙ  ａ  Ｒｅａｌ  Ｒｏｂｏｔ  ｕｓｉｎｇ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｒｅｉｎｆｏｒｃｅｍｅｎｔ  Ｌｅａｒｎｉｎｇ．  Ｉｎ  Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍｓ， Ｖｏｌ． ３６， ｐｐ． ３７−５１， ２００１．）
【発明が解決しようとする課題】
プリミティブと観察された情報とを用いるエージェントは、所与の課題と一組のプリミティブに対して、観察者と同様の動作をしようとする筈である。環境と感知情報とが大きく変わる可能性があり、さらにエージェントと観察された人との間に技量の差があるので、エージェントが課題に対して望まれるような結果を得ることはできないかもしれない。従って、エージェントはその環境で動作しながらその挙動を変化させる能力を有していなければならない。言い換えれば、エージェントが人の行動を観察して最初のトレーニングを得た後は、エージェントは行動を通してその課題に対する技量を高めていかなければならない。
【００１０】
従って、この発明の目的は、エージェントがある環境で動作する際に、その挙動を適切に変化させることを可能にするエージェントコントローラおよびプログラムを提供することである。
【００１１】
この発明の別の目的は、エージェントがある環境で動作する際に、その挙動を変化させてより良い結果を得ることを可能にするエージェントコントローラおよびプログラムを提供することである。
【００１２】
この発明のさらに別の目的は、エージェントがある環境でリアルタイムで動作する際に、その挙動を変化させてより良い結果を得ることを可能にするエージェントコントローラおよびプログラムを提供することである。
【００１３】
【課題を解決するための手段】
この発明の一局面に従えば、所定の状態空間内のエージェントの位置および一組の予め定められたプリミティブに基づいてエージェントを制御するエージェントコントローラは、多数のエントリを有するプリミティブデータベースを記憶するための手段を含む。各エントリはプリミティブと、所定の状態空間内でそのエントリに対応するデータ点の位置と、プリミティブを実行するための一組のパラメータと、データ点に割り当てられたデータ点値とを含む。コントローラはさらに、所定の状態空間内のエージェントの位置を問合せ点として特定するための手段と、問合せ点と所定の関係を満足するデータ点を有する、プリミティブデータベース内の複数のエントリを選ぶための手段とを含む。この所定の関係は所定の状態空間における問合せ点とデータ点との見かけ上の距離およびそのデータ点に割り当てられるデータ点値によって規定される。コントローラはさらに、選ぶための手段によって選ばれた複数のエントリのプリミティブに基づいてエージェントによって実行されるプリミティブを選択し、複数のエントリのうち選択されたプリミティブと同じプリミティブを有するエントリを選択するための手段と、選択されたプリミティブを有する選択されたエントリの一組のパラメータに基づき、選択されたプリミティブの一組のパラメータを計算するための手段と、計算するための手段によって計算された一組のパラメータで、選択されたプリミティブに従った行為をエージェントに実行させるための手段と、行為の結果を評価するための手段と、選択されたエントリのデータ点に割り当てられたデータ点値を、評価するための手段による評価を反映するように更新して、行為の結果が肯定的であれば次に計算される見かけの距離が短くなり、行為の結果が否定的であれば長くなるようにするための手段とを含む。
【００１４】
選ぶための手段は、所定の状態空間内の幾つかのデータ点の各々と問合せ点とのユークリッド距離を計算するための手段と、ユークリッド距離を、幾つかのデータ点に割り当てられたそれぞれのデータ点値を用いて規定されたそれぞれのデータ点値により、乗算するための手段と、乗算された距離が他のデータエントリのそれよりも小さい所定数のエントリを選ぶための手段とを含んでもよい。
【００１５】
プリミティブデータベースは所定の状態空間内の種々の場所からデータ点を選んだ結果をエンコードするような様態で更新される。コントローラはリアルタイムで動作して、プリミティブデータベースから先に検索された情報を用いて決定された行為を行なった結果に基づき、データベースに変更を加える。
【００１６】
状態空間は各データ点付近の状態空間の小区域の周りで、セルに量子化されてもよい。各セルにはセル値が割り当てられる。乗算するための手段は問合せ点を含む幾つかのデータ点の周囲のセルを選択するための手段と、選択されたセルに割り当てられたそれぞれのセル値を用いて規定される乗算係数でユークリッド距離を乗算するための手段とを含んでもよい。
【００１７】
データ点と問合せ点との見かけの距離は、データ点付近で、問合せ点に関連付けられたセルに割り当てられたセル値に基づいて計算される。あるデータ点の別々のセルは別々の問合せ点に関連付けられ、その結果見かけの距離が別々となるので、問合せ点に最も近いデータ点が正確に選択されるであろう。
【００１８】
乗算係数はセルに割り当てられたセル値の関数であってもよく、関数の値はセル値が増加すると減少する。
【００１９】
この発明の別の局面によれば、データ点値を更新するための手段は以下の関数に従ってデータ点値を更新し、
【００２０】
【数７】
2004163992.tif 000003
ここでＱｔ（ｑｔ，ｘｍ）は時間ｔで選択されたエントリのデータ点を表し、αはあるデータ点と問合せ点との距離の所定の関数として計算される学習率であり、ｒは行為が行なわれた後に観察される報酬であって、行為が好ましいものであれば正の値をとりそうでなければ負の値をとり、＾ｑおよび＾ｘは次の時間ステップでの新しい状態およびデータ点であり、Ｑｔ＋１（＾ｑ，＾ｘ）は以下の式で与えられ、
【００２１】
【数８】
2004163992.tif 000004
ここでＫ（ｄ（ａ，ｂ））はｄ（ａ，ｂ）＝０のとき最大値を有するカーネル関数であり、ｄ（ａｂ）が増加するにつれて単調にゼロに向かって減少し、ｄ（ａ ｂ）はデータ点ａと問合せ点ｂとの間のユークリッド距離である。
【００２２】
関数はカーネル回帰アルゴリズムをＱ学習アルゴリズムと組合わせたものである。エージェントが次に同じ状況になれば、それらのデータ点はより遠くに、またはより近くに現れることになる。なぜなら、上で規定した関数がデータ点値を適切に更新するからである。
【００２３】
αは以下の式で与えられ、
【００２４】
【数９】
2004163992.tif 000005
ここでｄ（ｘｉ，ｑｔ）は時間ステップｔでのデータ点ｘｉと問合せ点ｑｔとの間のユークリッド距離である。
【００２５】
用いられた各データ点について、この式で返される距離は０から１．０の間であり、用いられた全ての点の距離は合計で１．０となる。これは、プリミティブを選択するのに最も寄与した点が、最も高い学習率を有することになるという効果を有する。
【００２６】
この発明は、上述のようなエージェントとしてコンピュータを動作させる、コンピュータで実行可能なエージェント制御プログラムの形で実現されてもよい。
【００２７】
【発明の実施の形態】
［環境］
この発明の実施例では、現在の環境を見て現在の状況を問合せ点としてパラメータ化するアルゴリズムを用いる。アルゴリズムは環境の状態空間内の種々のデータ点のうちその状態空間の問合せ点に最も近いものを選択し、選ばれたデータ点に基づき行なうべきプリミティブを決定し、決定された行為を実行する。その後アルゴリズムはその行為の結果をエンコードするようなやり方でプリミティブデータベースを更新する。データ点は、学習プロセスで得られた特定されたプリミティブと関連のパラメータとを表し、データ点表の形で記憶されるが、これについては後述する。このアルゴリズムはリアルタイムで実行され、データベースから先に検索された情報を用いて決定された行為を実行した結果に基づき、データベースに対して変更を加える。
【００２８】
マーブル迷路の環境でプリミティブを選ぶ課題を用いて、このアルゴリズムを例示する。マーブル迷路においてプリミティブを行なった場合の結果は、先に進むこと、および穴に落ちることを含み、プリミティブが完了した時点で観察できる。選ばれたデータ点により決定される行為を実行して、たとえばボールが穴に落ちるという望ましくない結果に終わった場合、何らかの方法でこれを示さなければならない。将来も同じ状況で同じデータ点を選べば、同じ行為を実行し同じ望ましくない結果となってしまう筈である。将来、エージェント自身が、同じ状況になってとるべき行為を決定しなければならないとき、同じデータ点を選んではならないのである。
【００２９】
ここで説明する実施例はマーブル迷路を例にとったものであるが、ここで説明される方法とプログラムはヒューマノイドロボット等の他のシステムにも容易に適用可能である。
【００３０】
図１はマーブル迷路の環境を概略的に示す。この環境は、２個のノブ１４、１６を用いて傾けることのできるマーブルゲームボード１２を有するマーブル迷路ゲームボックス１０と、この発明の実施例を実現するコンピュータシステム２０と、ボックス１０上に置かれボード１２の方を向いて設けられボード１２のビデオ信号をコンピュータシステム２０に与えるためのカメラ３０と、コンピュータシステム２０からのアクチュエータコマンドによって制御され、ボード１２を傾けるためのアクチュエータ（モータ）３２、３４とを含む。図１には示さないが、ノブ１４および１６の軸には２個のエンコーダがそれぞれ設けられて、システムの学習段階でノブ１４および１６の角度を検知し、対応の信号をコンピュータシステム２０に与える。
【００３１】
図２はマーブルゲームボード１２を詳細に示す。ボード１２はノブ１４および１６を用いて傾けることができる。図２を参照して、ボード１２は、マーブルボール７０がボード１２上を転がってぶつかったり落ちたりする壁７２と穴７４という形で設けられた障害物を持つ迷路を有する。プレイヤーが行なうべきことは、２個のノブ１４、１６を用いてボード１２を傾けることで、ボール７０を所定のコース線７６に沿って転がすことである。
【００３２】
図１および２に示すマーブルゲームの環境は、仮想マーブルゲームとして、コンピュータで実現することもできる。仮想的なボード１２はコンピュータのマウスで制御され、ボード１２上を転がるボールの動きはシミュレートされる。仮想ゲームは、壁との衝突を、見た目上、多大なエネルギの損失を伴うものとして取り扱う。マーブルボールの動きは、ボード１２を傾ける動きに応答してシミュレートされ得る。
【００３３】
いずれの場合でも、人がゲームを行なっている間、時間と、ボードおよびマーブルの姿勢・位置とが記録される。システムはプレイヤーの動作を観察し、観察された動作中のプリミティブを特定し、プリミティブをボールの位置および速度、ボードの姿勢、ならびにノブ１４および１６の動作角度等の関連のパラメータとともに、データ点として記憶する。
【００３４】
人は、ハードウェア版のボードを操作する際には、エンコーダに接続されたノブ１４および１６を用いる。エンコーダシステムによって生成されたモータコマンドをコンピュータが読み、モータに送る。マーブルの位置は、ニュートンラボのコグナクローム（Ｎｅｗｔｏｎｌａｂｓ  Ｃｏｇｎａｃｒｏｍｅ）（登録商標）を用いて得られる。こうして、コンピュータシステム２０は人の動作を学習することができる。コンピュータシステム２０はまた、それ自身のコマンドを生成して、それ自身の判断でプレイするときにこれらをモータ３２および３４に送ることもできる。
【００３５】
［ハードウェア構成］
図３はこの実施例の方法を実現するコンピュータシステムを例示する。図４はシステムのブロック図である。仮想版のゲームが、図３および４に示すようなコンピュータによって実現できる。
【００３６】
図３を参照して、この実施例を実現するコンピュータシステム２０は、ＦＤ（フレキシブルディスク）ドライバ５２およびＣＤ−ＲＯＭ（コンパクトディスク読出専用メモリ）ドライブ５０を有するコンピュータ４０と、いずれもコンピュータ４０に接続された、キーボード４６と、マウス４８と、モニタ４２とを含む。
【００３７】
図４を参照して、コンピュータ２０は、ＦＤドライバ５２およびＣＤ−ＲＯＭドライブ５０に加えて、ＣＰＵ（中央処理装置）５６と、ＣＰＵ５６、ＦＤドライバ５２およびＣＤ−ＲＯＭドライブ５０に接続されたバス６６と、バス６６とカメラ３０とに接続されたビデオキャプチャボード６８と、ブートアッププログラム等を記憶する読出専用メモリ（ＲＯＭ）５８と、バス６６に接続され、アプリケーションプログラム命令、システムプログラム、データ点表およびプリミティブのためのデータベースを記憶するランダムアクセスメモリ（ＲＡＭ）６０とを含む。ＣＰＵ５６はさらにインターフェース（Ｉ／Ｏ）を介してエンコーダ３６および３８ならびにモータ３２および３４に接続される。
【００３８】
ここでは示さないが、コンピュータ４０はさらにローカルエリアネットワーク（ＬＡＮ）への接続を提供するネットワークアダプタボードを含んでもよい。
【００３９】
コンピュータシステム２０にこの実施例の方法を行なわせるプログラムは、ＣＤ−ＲＯＭドライブ５０またはＦＤドライブ５２に挿入されるＣＤ−ＲＯＭ６２またはＦＤ６４に記憶されさらにハードディスク５４に転送されてもよい。これに代えて、プログラムは図示しないネットワークを通じてコンピュータ４０に送信されハードディスク５４に記憶されてもよい。プログラムは実行の際にＲＡＭ６０にロードされる。プログラムはＣＤ−ＲＯＭ６２、ＦＤ６４、またはネットワークを介してＲＡＭ６０に直接ロードされてもよい。
【００４０】
以下に説明するプログラムは、コンピュータ４０にこの実施例の方法を行なわせる幾つかの命令を含む。この方法を行なわせるのに必要な基本的機能の幾つかはコンピュータ４０のオペレーティングシステム（ＯＳ）またはサードパーティのプログラム、もしくはコンピュータ４０にインストールされたモジュールにより提供されるので、このプログラムはこの実施例の方法を実現するのに必要な機能全てを必ずしも含まなくてよい。コンピュータシステム２０の動作は周知であるので、ここでは繰り返さない。
【００４１】
［プリミティブ］
マーブル迷路ゲームのプリミティブは、エージェントが課題を行なうのに必要とするであろう技量をエージェントに授けるように設計される。以下のプリミティブが現在研究されており、それらは図５から図９に示されている。
【００４２】
コーナへ進む（ＲＩＣ）：図５に示すように、ボール７０が壁に沿って転がり、別の壁７２に当たると停止する。
【００４３】
コーナ（ＣＯＲＮ）：図６に示すように、ボール７０はコーナにあり、ボード１２はボール７０をコーナから動かすような姿勢にされる。
【００４４】
自由前進（ＦＲ：Ｆｒｅｅ  Ｒｏｌｌｉｎｇ）：図７に示すように、ボール７０が壁に触れずに移動する。
【００４５】
壁から離れる（ＲＦＷ：Ｒｏｌｌ  Ｆｒｏｍ  Ｗａｌｌ）：図８に示すように、ボール７０が壁７２に接するか、当たってから、壁を離れて動く。
【００４６】
壁から落ちる（ＲＯＷ：Ｒｏｌｌ  Ｏｆｆ  Ｗａｌｌ）：図９に示すように、ボール７０が壁７２に沿って転がり、端から落ちる。
【００４７】
この実施例のエージェントは人がボード１２を操作するのを観察し、その操作のプリミティブを特定し、特定されたプリミティブ、ボードおよびボールの位置、ボールの速度、およびその関連のパラメータを、図１０に示すようにデータ点表８０の形で記憶する。表８０はＲＡＭ６０に保持されてもよい。観察された操作のプリミティブを特定する方法はこの発明を構成するものではなく、従ってここではその詳細は説明しない。
【００４８】
図１０を参照して、この実施例の表８０の各データ点エントリは、ボード１２上のＸ−Ｙ座標におけるボールの位置（ｘ，ｙ）と、ボールの速度（ｕ，ｖ）と、ボードの姿勢（Ｑｘ，Ｑｙ）と、プリミティブの種類ＴＹＰＥと、プリミティブの動作を行なうための必要とされるパラメータとを含む。ＴＹＰＥは、上にあげた５個のプリミティブのうちの一つである。ボールの位置、ボールの速度およびボードの姿勢はベクトルを形成し、このベクトルが以下で述べる距離の計算に用いられる。
【００４９】
表８０の構成は、この発明が別のものに応用される場合、たとえばエアホッケーゲームに適用される場合には、異なるものとなるであろう。
【００５０】
［距離の計算］
望ましい機能を得るために、カーネル回帰アルゴリズムをＱ学習アルゴリズムと組合わせ、各ステップで観察される状態に対して、使用するデータ点の値をエージェントに示すこととした。ボールとボードの位置・姿勢、およびそのステップで観察されるボールの速度が問合せ点を形成する。
【００５１】
アルゴリズムの基本は、カーネル回帰の式において、距離関数ｄ（ｘｉ，ｑ）への係数を加えることである。この係数は、データ点を問合せ点に対し相対的に移動させる効果を有する。１．０より大きい係数はデータ点を問合せ点から遠ざかるように移動させる効果を有し、１．０より小さい係数はデータ点を問合せ点に近付けるように移動させる効果を有する。たとえば、もしある組のデータ点に基づいて選択したプリミティブを行なった後ボールが穴に落ちた場合、そのデータ点の組に関連付けられた係数を増加させることができる。次にエージェントが同じ状態になった場合、これらのデータ点はより遠くに現れる筈であり、従って、選ばれる行為に対する影響は小さくなる筈である。
【００５２】
空間は、図１１に示すように、データ点付近の状態空間の小区域の周りで量子化され、図１１には、データ点９０の周りの「セル」９０Ａ−９０Ｄと呼ばれる分割された空間が概略的に示されている。各セルに対し、ある値が関連付けられ、データ点９０と関連付けて表に記憶される。表８０と、表８０におけるデータ点に関連した表とが、プリミティブデータベースを構成する。図１１および後続の図では、簡潔に示すことを目的に、多次元の状態空間を二次元の座標系で概略的に示す。
【００５３】
この実施例では、データ点は６次元を有し（ボール位置（ｘ，ｙ）、ボール速度（ｕ，ｖ）、ボード姿勢（Ｂｘ，Ｂｙ））、各次元は５個のセルで量子化される。従って、データベース内の各データ点は５６のサイズの表を有する。状態空間のどの問合せ点についても、このデータ点に対するその相対的な位置を用いて、その問合せ点に関連付けられるセルを見出す。ここでの目標は最適な解決策を見出すことではなく、観察された情報に対し良好な解決策を見出すことであるから、探索する必要があるのはセルのごく一部だけである。従って、表は疎なアレイとして記憶されるだけで、セルが実際に生成されるのはセルの値が初めて更新されるときになってである。それまでは、各セルは初期化ステップで与えられた一定の値を持つものとみなされる。
【００５４】
マーブル迷路の実現化例では、セル内の値は、問合せ点と関連してそのデータ点を用いる場合の値をエンコードする。データベースから、問合せ点に最も近いデータ点を選択するときには、以下の式により、データ点ｘｉ（文中下線の変数はベクトルを表す）と、問合せ点ｑとの距離が与えられる。
【００５５】
【数１０】
2004163992.tif 000006
関数ｆ（ｘｉ，ｑ）はこの問合せ点Ｑと関連付けられたデータ点ｘｉのセル内の値を見出し、この値を用いて係数を計算する。関数ｆ（ｘｉ，ｑ）から返された係数は、問合せ点に対するデータ点の見かけの距離に直接の影響を及ぼす。カーネル回帰において、ｄ（ｘｉ，ｑ）にかえて新たな距離Ｄを用いてパラメータを計算する。セルの値が増加するにつれてｆ（ｘｉ，ｑ）が減少し、データ点の見かけの距離は減少する。
【００５６】
セル値はある定数で初期化され、その後Ｑ学習関数を修正したものにより更新される。Ｎ個（たとえば５個）のデータ点が用いられるので、各時間ステップで、Ｎ個のＱ値を更新しなければならない。選ばれたデータ点、ｘｍ，ｍ＝１からＮ、の各々について、Ｑ値であるＱｔ（ｑｔ，
ｘｍ）は以下のように更新される。
【００５７】
【数１１】
2004163992.tif 000007
ここで、Ｑｔ（ｑｔ，  ｘｍ）は時間ｔにおいて選ばれたデータ点を表し、
αは学習率である。複数の点が用いられるので、学習率として、以下で与えられる距離を用いる。
【００５８】
【数１２】
2004163992.tif 000008
ここでｋ（）はカーネル関数であり、ｄ（ｘｉ，ｑｔ）＝０で最大値を有し、かつｄ（ｘｉ，ｑｔ）が増加するにつれて単調に減少する限りどのような形でもよい。用いられる各点についてこの式から返される距離は０から１．０の間であり、用いられる全ての点の距離の和は１．０となる。これは、プリミティブを選択するのに最も寄与した点が最も高い学習率を有することになるという効果を有する。
【００５９】
ｒは行為が行なわれた後に観察される報酬である。迷路内を進めば正の報酬が与えられる。時間がかかったり、穴に落ちたり、迷路内で負方向に進むかまたは全く進行しなかった場合には、負の報酬が与えられる。
Ｑｔ＋１（＾ｑ，＾ｘ）は新たな状態＾ｑ（＾のマークはこのマークのすぐあとに続く文字の上に置かれるべきものである。）で、次の時間ステップにおいてデータ点＾ｘを選択することにより期待される報酬である。この値は以下の式で与えられる。
【００６０】
【数１３】
2004163992.tif 000009
ソフトウェア構成
図１２はこの実施例の方法を実現するためにコンピュータシステム２０（図１）で実行されるメインプログラムの全体の制御構造を示す。図１２を参照して、メインプログラムは、以下のステップを含む。初期化１００、ここでデータ点のセルの値が定数で初期化される。環境状態を見るステップ１０２、ここではカメラ３０でキャプチャされた画像が評価され、環境状態が問合せ点として特定される。
【００６１】
次に、ステップ１０４で、問合せ点に最も近い２０個のデータ点が現在の問合せ点に対し選ばれる。図１３を参照して、問合せ点１３０とデータ点の各々との間のユークリッド距離が計算され、このステップで、最も短い距離を有する２０個のデータ点が選ばれる。図１３では、問合せ点１３０の周りの円１３２内の２０個のデータ点が選ばれている。
【００６２】
ステップ１０６で、特定された状態で行なわれるべきプリミティブの種類が、多数決で決定される。具体的には、ステップ１０４で選ばれたデータ点のプリミティブの種類が調べられ、最も数が多かったプリミティブの種類が、つぎに行なわれるべきプリミティブの種類であると決定される。
【００６３】
ステップ１０８で、図１４に示すように、選択されたものと同じプリミティブの種類を有するデータ点のうち問合せ点１３０に最も近い予め定められた数Ｎのデータ点、たとえば５個のデータ点１４０、１４２、１４４、１４６および１４８が選ばれ、選択されたプリミティブの種類を行なうためのパラメータが、これら５個のデータ点を用いて計算される。たとえば、選択されたデータ点のパラメータを、それぞれのデータ点から問合せ点までの距離で重み付けして平均をとることで、選択されたプリミティブの種類についてのパラメータを計算できる。
【００６４】
ステップ１１０で、決定された種類の行為（プリミティブ）が、ステップ１０８で計算されたパラメータを用いて行なわれる。ハードウェア版では、コンピュータシステム２０（図１）からモータ３２および３４に対してモータコマンドが出力され、仮想版ではボード１２の動きがシミュレートされる。
【００６５】
ステップ１１２で、ハードウェア版では、カメラ３０によってキャプチャされた画像が検討されて、報酬が決定され、ステップ１１０で実行された行為が評価される。仮想版では、ボールの動きがシミュレートされ、結果が評価される。
【００６６】
ステップ１１４で、ステップ１０８において選択されたデータ点に関連付けられたセルの値が上の式（１）により更新される。ここで、図１５に示すように、ステップ１０６で選択されたデータ点の各々について、問合せ点１３０を含むセルの値が更新される。たとえば、もし問合せ点がデータ点１４２のセル１４２Ｄにあれば、セル１４２Ｄの値が更新され、データ点１４２の他のセルは更新されない。
【００６７】
上で説明したように、この実施例の方法とプログラムは環境状態空間における種々の場所からデータ点を選んだ結果をエンコードするようなやり方で、プリミティブデータベースを更新する。プログラムはリアルタイムに実行され、行為を実行した結果によりデータベースを変更する。更新されたデータベースを用いることで、次にエージェントが同じ状況になった場合、エージェントの挙動は前回とは異なるものとなり、結果はより好ましいものとなる筈である。
【００６８】
この発明を具体的な実施例を参照して説明したが、この発明はこれに限られるものではない。発明の範囲は請求項によってのみ制限される。
【図面の簡単な説明】
【図１】ハードウェア版で実現されたこの発明の実施例の環境の概略図である。
【図２】マーブル迷路ボードの斜視図である。
【図３】この発明の実施例を実現するコンピュータシステムの斜視図である。
【図４】図３に示すコンピュータのブロック図である。
【図５】プリミティブＲＩＣ（コーナへ進む）を示す概略図である。
【図６】プリミティブＣＯＲＮ（コーナ）を示す概略図である。
【図７】プリミティブＦＲ（自由前進）を示す概略図である。
【図８】プリミティブＲＦＷ（壁から離れて進む）を示す概略図である。
【図９】プリミティブＲＯＷ（壁から落ちる）を示す概略図である。
【図１０】この発明の実施例のデータ点表を示す概略図である。
【図１１】データ点の周りのセルを示す概略図である。
【図１２】この発明の実施例の実施例によるプログラムのフローチャートである。
【図１３】問合せ点に最も近いデータ点の選択を示す概略図である。
【図１４】決定されたプリミティブ種類の、問合せ点に最も近い選択された５個のデータ点を示す概略図である。
【図１５】決定されたプリミティブ種類の、問合せ点に最も近い選択された５個のデータ点のセルがどのように更新されるかを示す概略図である。
【符号の説明】
１０  マーブル迷路ゲームボックス、１２  マーブル迷路ゲームボード、２０コンピュータシステム、１４，１６  ノブ、３２、３４  モータ、７０  ボール、７２  壁、７４  穴、７６  コース線、８０  データ点表、９０、１４０−１４８  データ点、９０Ａ−９０Ｄ、１４２Ｄ  セル、１３０  問合せ点
【図１】
2004163992.tif 000016
【図２】
2004163992.tif 000017
【図３】
2004163992.tif 000018
【図４】
2004163992.tif 000019
【図５】
2004163992.tif 000020
【図６】
2004163992.tif 000021
【図７】
2004163992.tif 000022
【図８】
2004163992.tif 000023
【図９】
2004163992.tif 000024
【図１０】
2004163992.tif 000025
【図１１】
2004163992.tif 000026
【図１２】
2004163992.tif 000027
【図１３】
2004163992.tif 000028
【図１４】
2004163992.tif 000029
【図１５】
2004163992.tif 000030
【外国語明細書】
2004163992.tif 000031
2004163992.tif 000032
2004163992.tif 000033
2004163992.tif 000034
2004163992.tif 000035
2004163992.tif 000036
2004163992.tif 000037
2004163992.tif 000038
2004163992.tif 000039
2004163992.tif 000040
2004163992.tif 000041
2004163992.tif 000042
2004163992.tif 000043
2004163992.tif 000044
2004163992.tif 000045
2004163992.tif 000046
2004163992.tif 000047
2004163992.tif 000048
2004163992.tif 000049
2004163992.tif 000050
2004163992.tif 000051
2004163992.tif 000052
2004163992.tif 000053
2004163992.tif 000054
2004163992.tif 000055
2004163992.tif 000056
2004163992.tif 000057
2004163992.tif 000058
2004163992.tif 000059
2004163992.tif 000060
2004163992.tif 000061
2004163992.tif 000062
2004163992.tif 000063
2004163992.tif 000064
2004163992.tif 000065
2004163992.tif 000066
2004163992.tif 000067
2004163992.tif 000068
2004163992.tif 000069
2004163992.tif 000070
2004163992.tif 000071
2004163992.tif 000072
2004163992.tif 000073
2004163992.tif 000074
2004163992.tif 000075
2004163992.tif 000076
2004163992.tif 000077
2004163992.tif 000078
2004163992.tif 000079
2004163992.tif 000080