(57)【要約】【課題】娯楽性のあるエージェントを提供する。【解決手段】学習部は、アクション可能なエージェントがアクションを行ったときにエージェントにおいて観測される観測値を用いて、エージェントがアクションを行う環境のモデルの学習を行う。ユーザ指示出力部は、ユーザからの指示に応じて、そのユーザからの指示を表す指示情報を出力する。アクション決定部は、モデルに基づいて、エージェントが行うアクションを決定するが、ユーザから指示があった場合には、指示情報に従って、エージェントが行うアクションを決定する。本技術は、例えば、ゲームのキャラクタ等に適用できる。【選択図】図３
2013058059.tif 000002
【特許請求の範囲】
【請求項１】
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
を備え、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定する
情報処理装置。
【請求項２】
前記モデルは、
前記エージェントが行うアクションによって、状態が状態遷移する、前記アクションごとの状態遷移確率と、
前記状態から、前記観測値が観測される観測確率と
で規定され、
前記学習部は、前記モデルの学習を、前記エージェントが行うアクションと、前記エージェントがアクションを行ったときに前記エージェントにおいて観測される観測値とを用いて行う
請求項１に記載の情報処理装置。
【請求項３】
前記モデルは、HMM(Hidden Marcov Model)の状態遷移確率を、前記エージェントが行うアクションごとの状態遷移確率に拡張した拡張HMMであり、
前記学習部は、Baum-Welchの再推定法に従い、各アクションについての前記状態遷移確率と、前記観測確率とを推定する、前記拡張HMMの学習を行う
請求項２に記載の情報処理装置。
【請求項４】
前記拡張HMMに基づき、前記エージェントが行ったアクションと、そのアクションが行われたときに前記エージェントにおいて観測された観測値とを用いて、前記拡張HMMにおいて、現在いる状態である現在状態を認識する状態認識部と、
前記拡張HMMの状態の１つを、目標とする目標状態に決定する目標決定部と
をさらに備え、
前記アクション決定部は、前記拡張HMMに基づき、前記現在状態から前記目標状態までの状態遷移の尤度を最も高くするアクションの系列であるアクションプランを算出し、そのアクションプランに従い、前記エージェントが次に行うべきアクションを決定する
請求項３に記載の情報処理装置。
【請求項５】
前記目標決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記目標状態を決定し、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って決定された前記目標状態までのアクションプランを算出し、そのアクションプランに従い、前記エージェントが次に行うべきアクションを決定する
請求項４に記載の情報処理装置。
【請求項６】
所定の観測値が観測される状態を遷移元として行うことが可能な状態遷移の中で、行われたことがない状態遷移がある、前記所定の観測値と同一の観測値が観測される他の状態であるオープン端を検出するオープン端検出部をさらに備え、
前記目標決定部は、前記オープン端を、前記目標状態に決定する
請求項４に記載の情報処理装置。
【請求項７】
前記オープン端検出部は、
前記状態遷移確率と、前記観測確率とを用いて、各観測値が観測されるときに、前記エージェントが各アクションを行う確率であるアクション確率を求め、
前記アクション確率と、前記観測確率との乗算により、各観測値が観測される各状態において、前記エージェントが各アクションを行う確率である、観測確率に基づくアクション確率を算出し、
各状態について、その状態を遷移元とする状態遷移の前記状態遷移確率を、アクションごとに加算することにより、各状態において、前記エージェントが各アクションを行う確率である、状態遷移確率に基づくアクション確率を算出し、
前記観測確率に基づくアクション確率と、前記状態遷移確率に基づくアクション確率との差分が所定の閾値以上となる状態を、前記オープン端として検出する
請求項６に記載の情報処理装置。
【請求項８】
前記エージェントが、前記オープン端を前記目標状態とするアクションプラン、又は、前記指示情報に従って決定される前記目標状態までのアクションプランに従って、景品が置かれた迷路を移動するアクションを行うことにより観測される観測値と、前記エージェントが行うアクションとを用いて、前記拡張HMMにおいて、前記迷路の構造を獲得する学習を行う事前準備処理と、
前記エージェントが、前記迷路において景品が置かれた場所に対応する状態を目標状態とするアクションプランに従って、前記迷路を移動するアクションを行うことにより、前記景品を収集する収集処理と
を制御する請求項６に記載の情報処理装置。
【請求項９】
前記アクション決定部は、前記拡張HMMにおいて獲得していない未知の情報を増加させるストラテジに従って、アクションを決定する
請求項３に記載の情報処理装置。
【請求項１０】
前記アクション決定部は、前記エージェントがアクションを行ったときに各観測値が観測される確率によって発生確率が表される情報のエントロピーを最大にするアクションを、前記エージェントが次に行うべきアクションに決定する
請求項９に記載の情報処理装置。
【請求項１１】
前記エージェントが、前記エントロピーを最大にするアクション、又は、前記指示情報に従って決定されるアクションを行って、景品が置かれた迷路を移動することにより観測される観測値と、前記エージェントが行うアクションとを用いて、前記拡張HMMにおいて、前記迷路の構造を獲得する学習を行う事前準備処理と、
前記エージェントが、前記迷路において景品が置かれた場所に対応する状態を目標状態とするアクションプランに従って、前記迷路を移動するアクションを行うことにより、前記景品を収集する収集処理と
を制御する請求項１０に記載の情報処理装置。
【請求項１２】
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
を備える情報処理装置の前記アクション決定部が、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定するステップを含む
情報処理方法。
【請求項１３】
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
して、コンピュータを機能させるためのプログラムであり、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定する
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、情報処理装置、情報処理方法、及び、プログラムに関し、特に、例えば、ゲームのキャラクタ等に適用可能な娯楽性のあるエージェントを提供することができるようにする情報処理装置、情報処理方法、及び、プログラムに関する。
【背景技術】
【０００２】
ゲーム（ビデオゲーム）については、基本的に、設計者が、ゲームの内容を、事前に作り込み、プログラムとして実装する（特許文献１，２，３，４，及び、５）。
【０００３】
例えば、アドベンチャゲームでは、ゲームの舞台となる世界や、シナリオ、キャラクタの振る舞い等のすべてが、事前に設計され、実装される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2007-319560号公報
【特許文献２】特開2007-312848号公報
【特許文献３】特開2007-75467号公報
【特許文献４】特開2006-288951号公報
【特許文献５】特開2000-271347号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、ゲームについては、ユーザが飽きないように、事前に作り込まれたキャラクタではなく、実際の人のように、自律的に成長し、かつ、ユーザの育成によって性能（能力）に差がつくキャラクタの登場が要請されている。
【０００６】
本技術は、このような状況に鑑みてなされたものであり、例えば、ユーザに飽きさせないキャラクタとなるような、娯楽性のあるエージェントを提供することができるようにするものである。
【課題を解決するための手段】
【０００７】
本技術の一側面の情報処理装置、又は、プログラムは、アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部とを備え、前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定する情報処理装置、又は、情報処理装置としてコンピュータを機能させるためのプログラムである。
【０００８】
本技術の一側面の情報処理方法は、アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部とを備える情報処理装置の前記アクション決定部が、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定するステップを含む情報処理方法である。
【０００９】
以上のような一側面においては、アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習が行われる一方、前記モデルに基づいて、前記エージェントが行うアクションが決定される。但し、ユーザから指示があった場合、その指示に応じて、前記ユーザからの指示を表す指示情報が出力され、前記指示情報に従って、前記エージェントが行うアクションが決定される。
【００１０】
なお、情報処理装置は、独立した装置であっても良いし、１つの装置を構成している内部ブロックであっても良い。
【００１１】
また、プログラムは、伝送媒体を介して伝送することにより、又は、記録媒体に記録して、提供することができる。
【発明の効果】
【００１２】
本技術の一側面によれば、娯楽性のあるエージェントを提供することができる。
【図面の簡単な説明】
【００１３】
【図１】アクション環境を示す図である。
【図２】エージェントが行うアクション、及び、エージェントが観測する観測値を示す図である。
【図３】本技術の情報処理装置を適用したエージェントの一実施の形態の構成例を示すブロック図である。
【図４】反射アクションモードの処理を説明するフローチャートである。
【図５】拡張HMMの状態遷移確率を説明する図である。
【図６】拡張HMMの学習の処理を説明するフローチャートである。
【図７】認識アクションモードの処理を説明するフローチャートである。
【図８】目標決定部１６が行う目標状態の決定の処理を説明するフローチャートである。
【図９】オープン端検出部３７が検出するオープン端である拡張HMMの状態を説明する図である。
【図１０】オープン端検出部３７が、観測値Okが閾値以上の確率で観測される状態Siをリストアップする処理を説明する図である。
【図１１】観測値Okに対してリストアップされた状態Siを用いて、アクションテンプレートCを生成する方法を説明する図である。
【図１２】観測確率に基づくアクション確率Dを算出する方法を説明する図である。
【図１３】状態遷移確率に基づくアクション確率Eを算出する方法を説明する図である。
【図１４】差分アクション確率Fを模式的に示す図である。
【図１５】オープン端の検出の処理を説明するフローチャートである。
【図１６】本技術を適用したゲーム機の一実施の形態の構成例を示すブロック図である。
【図１７】コイン収集ゲームのゲーム環境の例を示す図である。
【図１８】エージェントが迷路のマスにおいて観測することができる範囲の例を示す図である。
【図１９】コイン収集ゲームについて、ゲーム機が行う処理（ゲーム制御）を説明するフローチャートである。
【図２０】本技術を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１４】
［エージェントがアクションを行う環境］
【００１５】
図１は、本技術の情報処理装置を適用したエージェントがアクションを行う環境であるアクション環境の例を示す図である。
【００１６】
エージェントは、移動等のアクション（行動）を自律的に行うことが可能（アクション可能）な、例えば、ロボット（実世界で行動するロボットでも良いし、仮想世界で行動する仮想的なロボットでも良い）等の装置である。
【００１７】
エージェントは、アクションを行うことによって、エージェントの状態を変化させること、及び、外部から観測可能な情報を観測し、その観測結果である観測値を用いて、エージェントの状態を認識することができる。
【００１８】
また、エージェントは、状態の認識や、各状態において行うべきアクションの決定（選択）のために、エージェントがアクションを行うアクション環境のモデル（環境モデル）を構築する。
【００１９】
図１では、アクション環境は、２次元平面の迷路になっており、エージェントは、図中、白抜きの部分を、通路として移動することができる。
【００２０】
［エージェントが行うアクションと、エージェントが観測する観測値］
【００２１】
図２は、アクション環境において、エージェントが行うアクション、及び、エージェントが観測する観測値の例を示している。
【００２２】
エージェントは、図１に示したようなアクション環境の、図中、点線で正方形状に区切ったエリアを、観測値を観測する単位（観測単位）とし、その観測単位で移動するアクションを行う。
【００２３】
図２Ａは、エージェントが行うアクションの種類を示している。
【００２４】
図２Ａでは、エージェントは、図中、上方向に観測単位だけ移動するアクションU1、右方向に観測単位だけ移動するアクションU2、下方向に観測単位だけ移動するアクションU3、左方向に観測単位だけ移動するアクションU4、及び、移動しない（何もしない）アクションU5の、合計で、５つのアクションU1ないしU5を行うことが可能になっている。
【００２５】
図２Ｂは、エージェントが観測単位で観測する観測値の種類を、模式的に示している。
【００２６】
本実施の形態では、エージェントは、観測単位において、１５種類の観測値（シンボル）O1ないしO15のうちのいずれかを観測する。
【００２７】
観測値O1は、上と、下と、左とが壁で、右が通路になっている観測単位で観測され、観測値O2は、上と、左と、右とが壁で、下が通路になっている観測単位で観測される。
【００２８】
観測値O3は、上と、左とが壁で、下と、右とが通路になっている観測単位で観測され、観測値O4は、上と、下と、右とが壁で、左が通路になっている観測単位で観測される。
【００２９】
観測値O5は、上と、下とが壁で、左と、右とが通路になっている観測単位で観測され、観測値O6は、上と、右とが壁で、下と、左とが通路になっている観測単位で観測される。
【００３０】
観測値O7は、上が壁で、下と、左と、右とが通路になっている観測単位で観測され、観測値O8は、下と、左と、右とが壁で、上が通路になっている観測単位で観測される。
【００３１】
観測値O9は、下と、左とが壁で、上と、右とが通路になっている観測単位で観測され、観測値O10は、左と、右とが壁で、上と、下とが通路になっている観測単位で観測される。
【００３２】
観測値O11は、左が壁で、上と、下と、右とが通路になっている観測単位で観測され、観測値O12は、下と、右とが壁で、上と、左とが通路になっている観測単位で観測される。
【００３３】
観測値O13は、下が壁で、上と、左と、右とが通路になっている観測単位で観測され、観測値O14は、右が壁で、上と、下と、左とが通路になっている観測単位で観測される。
【００３４】
観測値O15は、上下左右すべてが通路になっている観測単位で観測される。
【００３５】
なお、アクションUm（m=1,2,・・・,M（Mはアクションの（種類の）総数））、及び、観測値Ok（k=1,2,・・・,K（Kは観測値の総数））は、いずれも離散値である。
【００３６】
［エージェントの一実施の形態］
【００３７】
図３は、本技術の情報処理装置を適用したエージェントの一実施の形態の構成例を示すブロック図である。
【００３８】
エージェントは、アクション環境をモデル化した環境モデルを、学習により獲得する。
【００３９】
また、エージェントは、観測値の系列（観測値系列）を用いて、エージェントの現在の状態（状況）の認識を行う。
【００４０】
さらに、エージェントは、現在地（現在の状態）から、ある目標に向かうのに行うべきアクションのプラン（アクションプラン）をプランニング（生成）し、そのアクションプランに従って、次に行うべきアクションを決定する。
【００４１】
なお、エージェントが行う学習、状態の認識、アクションプランのプランニング（アクションの決定）は、エージェントが観測単位で上、下、左、又は右に移動する問題（タスク）の他、一般的に強化学習の課題として取り上げられる、マルコフ決定過程(MDP(Markov decision process))の枠組みで定式化が可能な問題に適用することができる。
【００４２】
図３において、エージェントは、アクション環境において、図２Ａに示したアクションUmを行うことによって、観測単位で移動し、移動後の観測単位で観測される観測値Okを取得する。
【００４３】
そして、エージェントは、現在までに行ったアクションUm（を表すシンボル）の系列であるアクション系列、及び、現在までに観測された観測値（を示すシンボル）Okの系列である観測値系列を用いて、アクション環境（の構造（をモデル化した環境モデル））の学習や、次に行うべきアクションの決定を行う。
【００４４】
エージェントがアクションを行うモードとしては、反射アクションモード（反射行動モード）と、認識アクションモード（認識行動モード）との２つのモードがある。
【００４５】
反射アクションモードでは、過去に得られた観測値系列とアクション系列とから、次に行うべきアクションを決定するルールを、生得的なルールとして設計しておき、その生得的なルールに従って、アクションが決定される。
【００４６】
ここで、生得的なルールとしては、例えば、壁にぶつからないように、アクションを決定する（通路中での往復運動を許す）ルール、又は、壁にぶつからないように、かつ、行き止まるまでは、来た道を戻らないように、アクションを決定するルール等を採用することができる。
【００４７】
エージェントでは、生得的なルールに従い、エージェントにおいて観測される観測値に対して、次に行うべきアクションを決定し、そのアクションを行った後の観測単位で観測値を観測することを繰り返す。
【００４８】
これにより、エージェントは、アクション環境を移動したときのアクション系列と観測値系列とを獲得する。このようにして反射アクションモードで獲得されたアクション系列と観測値系列は、アクション環境の学習に用いられる。
【００４９】
認識アクションモードでは、エージェントは、目標を決定し、現在の状態を認識して、その現在の状態から目標を達成するためのアクションプランを決定する。そして、エージェントは、アクションプランに従って、次に行うべきアクションを決定する。なお、反射アクションモードでも、アクション系列と観測値系列を獲得することができ、アクション環境の学習に用いることができる。
【００５０】
図３において、エージェントは、ユーザ指示出力部１０、反射アクション決定部１１、アクチュエータ１２、センサ１３、履歴記憶部１４、アクション制御部１５、及び、目標決定部１６から構成される。
【００５１】
ユーザ指示出力部１０は、ユーザが、例えば、リモートコマンダ等の操作部を操作することによって、エージェントに対する指示を入力した場合に、そのユーザからの指示に応じて、その指示を表す指示情報を出力する。
【００５２】
ユーザ指示出力部１０が出力する指示情報は、反射アクション決定部１１、及び、目標決定部１６に供給される。
【００５３】
反射アクション決定部１１には、ユーザ指示出力部１０からの指示情報の他、センサ１３が出力する、アクション環境において観測された観測値が供給される。
【００５４】
反射アクション決定部１１は、反射アクションモードにおいて、生得的なルールに従い、センサ１３から供給される観測値に対して、次に行うべきアクションを決定し、アクチュエータ１２を制御する。
【００５５】
なお、反射アクション決定部１１は、ユーザ指示出力部１０から指示情報が供給された場合には、優先的に、その指示情報に従って、次に行うべきアクションを決定する。
【００５６】
アクチュエータ１２は、反射アクション決定部１１や、後述するアクション決定部２４の制御に従って駆動する。アクチュエータが駆動することにより、アクション環境において、エージェントは、反射アクション決定部１１やアクション決定部２４で決定されたアクション、すなわち、例えば、アクション環境としての迷路内の移動を行う。
【００５７】
センサ１３は、外部から観測可能な情報をセンシングし、そのセンシング結果としての観測値を出力する。
【００５８】
すなわち、センサ１３は、アクション環境の、エージェントが存在する観測単位を観測し、その観測単位を表すシンボルを、観測値として出力する。
【００５９】
なお、図３では、センサ１３は、アクチュエータ１２をも観測し、これにより、エージェントが行ったアクション（を表すシンボル）も出力する。
【００６０】
センサ１３が出力する観測値は、反射アクション決定部１１と、履歴記憶部１４とに供給される。
【００６１】
履歴記憶部１４は、センサ１３が出力する観測値とアクションを順次記憶する。これにより、履歴記憶部１４には、観測値の系列（観測値系列）とアクションの系列（アクション系列）とが記憶される。
【００６２】
なお、ここでは、外部から観測可能な観測値として、エージェントが存在する観測単位を表すシンボルを採用するが、観測値としては、エージェントが存在する観測単位を表すシンボルと、エージェントが行ったアクションを表すシンボルとのセットを採用することが可能である。
【００６３】
アクション制御部１５は、履歴記憶部１４に記憶された観測値系列、及び、アクション系列を用いて、アクション環境の構造を記憶（獲得）させる環境モデルとしての状態遷移確率モデルの学習を行う。
【００６４】
また、アクション制御部１５は、学習後の状態遷移確率モデルに基づき、アクションプランを算出する。さらに、アクション制御部１５は、アクションプランに従って、エージェントが次に行うべきアクションを決定し、そのアクションに従って、アクチュエータ１２を制御することで、エージェントにアクションを行わせる。
【００６５】
すなわち、アクション制御部１５は、学習部２１、モデル記憶部２２、状態認識部２３、及び、アクション決定部２４から構成される。
【００６６】
学習部２１は、履歴記憶部１４に記憶されたアクション系列、及び、観測値系列を用いて、モデル記憶部２２に記憶された状態遷移確率モデルの学習を行う。
【００６７】
ここで、学習部２１が学習の対象とする状態遷移確率モデルは、エージェントが行うアクションによって、状態が状態遷移する、アクションごとの状態遷移確率と、状態から、所定の観測値が観測される観測確率とで規定される状態遷移確率モデルである。
【００６８】
状態遷移確率モデルとしては、例えば、HMM(Hidden Marcov Model)があるが、一般のHMMの状態遷移確率は、アクションごとに存在しない。そこで、本実施の形態では、HMM(Hidden Marcov Model)の状態遷移確率を、エージェントが行うアクションごとの状態遷移確率に拡張し、そのように状態遷移確率が拡張されたHMM（以下、拡張HMMともいう）を、学習部２１による学習の対象として採用する。
【００６９】
なお、状態遷移確率モデルとしては、一般のHMM（状態遷移確率がアクションごとに存在しないHMM）を採用することができる。但し、状態遷移確率モデルとして、一般のHMMを採用する場合、HMMの状態遷移と、エージェントが行うべきアクションとを対応付ける学習（状態遷移を入力として、その状態遷移を生じさせるために行うアクションを出力する関数等のコントローラの学習）を行う必要がある。HMMの状態遷移と、エージェントが行うアクションとを対応付ける学習の方法については、例えば、本件出願人が先に提案した特許第4596024号に記載されている。
【００７０】
モデル記憶部２２は、拡張HMM（を規定するモデルパラメータである状態遷移確率や、観測確率等）を記憶する。
【００７１】
状態認識部２３は、認識アクションモードにおいて、モデル記憶部２２に記憶された拡張HMMに基づき、履歴記憶部１４に記憶されたアクション系列、及び、観測値系列を用いて、エージェントの現在の状態、すなわち、拡張HMMの、いまいる状態である現在状態を求める（認識する）。
【００７２】
そして、状態認識部２３は、現在状態を、アクション決定部２４に供給する。
【００７３】
アクション決定部２４は、認識アクションモードにおいて、エージェントが行うべきアクションをプランニングするプランナとして機能する。
【００７４】
すなわち、アクション決定部２４には、状態認識部２３から現在状態が供給される他、目標決定部１６から、モデル記憶部２２に記憶された拡張HMMの状態のうちの１つの状態が、目標とする目標状態として供給される。
【００７５】
アクション決定部２４は、モデル記憶部２２に記憶された拡張HMMに基づき、状態認識部２３からの現在状態から、目標決定部１６からの目標状態までの状態遷移の尤度を最も高くするアクションの系列であるアクションプランを算出（決定）する。
【００７６】
さらに、アクション決定部２４は、アクションプランに従い、エージェントが次に行うべきアクションを決定し、その決定したアクションに従って、アクチュエータ１２を制御する。
【００７７】
目標決定部１６は、認識アクションモードにおいて、目標状態を決定し、アクション決定部２４に供給する。
【００７８】
すなわち、目標決定部１６は、目標選択部３１、外部目標設定部３３、及び、内部目標生成部３４から構成される。
【００７９】
目標選択部３１には、外部目標設定部３３からの外部目標と、内部目標生成部３４からの内部目標とが供給される。
【００８０】
目標選択部３１は、外部目標設定部３３からの外部目標としての状態、又は、内部目標生成部３４からの内部目標としての状態を選択し、その選択した状態を、目標状態に決定して、アクション決定部２４に供給する。
【００８１】
なお、目標選択部３１は、外部目標設定部３３から外部目標としての状態が供給されるとともに、内部目標生成部３４から内部目標としての状態が供給される場合には、外部目標設定部３３から外部目標としての状態を、内部目標生成部３４から内部目標としての状態よりも優先的に、目標状態に選択する。
【００８２】
外部目標設定部３３には、ユーザ指示出力部１０からの指示情報が供給される。
【００８３】
外部目標設定部３３は、ユーザ指示出力部１０からの指示情報に従った拡張HMMの状態を、外部からの指示に従って決定される外部目標に設定して、目標選択部３１に供給する。
【００８４】
内部目標生成部３４は、（エージェントの）内部で求められる内部目標となる拡張HMMの状態を取得し、目標選択部３１に供給する。
【００８５】
すなわち、内部目標生成部３４は、ランダム目標生成部３５、特定状態検出部３６、及び、オープン端検出部３７から構成される。
【００８６】
ランダム目標生成部３５は、モデル記憶部２２に記憶された拡張HMMの状態の中から、ランダムに、１つの状態を、ランダム目標として選択し、そのランダム目標を、内部目標（の１つ）として、目標選択部３１に供給する。
【００８７】
特定状態検出部３６は、モデル記憶部２２に記憶された拡張HMMの状態から、所定の状態を、特定状態として検出し、内部目標（の１つ）として、目標選択部３１に供給する。
【００８８】
オープン端検出部３７は、モデル記憶部２２に記憶された拡張HMMにおいて、所定の観測値が観測される状態を遷移元として行うことが可能な状態遷移の中で、行われたことがない状態遷移がある、所定の観測値と同一の観測値が観測される他の状態を、オープン端として検出する。そして、オープン端検出部３７は、オープン端を、内部目標（の１つ）として、目標選択部３１に供給する。
【００８９】
［反射アクションモードの処理］
【００９０】
図４は、図３のエージェントが行う、反射アクションモードの処理を説明するフローチャートである。
【００９１】
ステップＳ１１において、反射アクション決定部１１は、時刻をカウントする変数tを、初期値としての、例えば、1に設定し、処理は、ステップＳ１２に進む。
【００９２】
ステップＳ１２では、センサ１３が、アクション環境から、現在の観測値（時刻tの観測値）otを取得して出力し、処理は、ステップＳ１３に進む。
【００９３】
ここで、時刻tの観測値otは、本実施の形態では、図２Ｂに示した１５個の観測値O1ないしO15のうちのいずれかである。
【００９４】
ステップＳ１３では、ユーザ指示出力部１０が、ユーザからの指示があったかどうかを判定する。
【００９５】
ステップＳ１３において、ユーザからの指示がなかったと判定された場合、処理は、ステップＳ１４に進み、エージェントは、センサ１３が出力した観測値otを、反射アクション決定部１１に供給して、処理は、ステップＳ１５に進む。
【００９６】
ステップＳ１５では、反射アクション決定部１１が、生得的なルールに従い、センサ１３からの観測値otに対して、時刻tに行うべきアクションutを決定し、そのアクションutに従って、アクチュエータ１２を制御して、処理は、ステップＳ１６に進む。
【００９７】
ここで、時刻tのアクションutは、本実施の形態では、図２Ａに示した５個のアクションU1ないしU5のうちのいずれかである。
【００９８】
また、以下、エージェントが次に行うべきアクションとして決定されたアクションutを、決定アクションutともいう。
【００９９】
ステップＳ１６では、アクチュエータ１２は、反射アクション決定部１１の制御に従って駆動し、これにより、エージェントは、決定アクションutを行う。
【０１００】
このとき、センサ１３は、アクチュエータ１２を観測しており、エージェントが行ったアクションut（を表すシンボル）を出力する。
【０１０１】
そして、処理は、ステップＳ１６からステップＳ１７に進み、履歴記憶部１４は、センサ１３が出力した観測値otとアクションutとを、観測値及びアクションの履歴として、既に記憶している観測値及びアクションの系列に追加する形で記憶し、処理は、ステップＳ１８に進む。
【０１０２】
ステップＳ１８では、反射アクション決定部１１は、反射アクションモードで行うアクションの回数として、あらかじめ指定（設定）された回数だけ、エージェントがアクションを行ったかどうかを判定する。
【０１０３】
ステップＳ１８において、エージェントが、あらかじめ指定された回数だけのアクションを、まだ、行っていないと判定された場合、処理は、ステップＳ１９に進み、反射アクション決定部１１は、時刻tを1だけインクリメントする。そして、処理は、ステップＳ１９からステップＳ１２に戻り、以下、同様の処理が繰り返される。
【０１０４】
また、ステップＳ１８において、エージェントが、あらかじめ指定された回数だけのアクションを行ったと判定された場合、すなわち、時刻tが、あらかじめ指定された回数に等しい場合、反射アクションモードの処理は終了し、認識アクションモードの処理が開始される。認識アクションモードの処理については、後述する。
【０１０５】
一方、ステップＳ１３において、ユーザからの指示があったと判定された場合、すなわち、ユーザが、エージェントの移動先の位置を指定する指示や、移動方向を指定する指示等を行った場合、処理は、ステップＳ２０に進み、ユーザ指示出力部１０は、ユーザの指示を表す指示情報を、反射アクション決定部１１に供給して、処理は、ステップＳ２１に進む。
【０１０６】
ステップＳ２１では、反射アクション決定部１１は、ユーザ指示出力部１０からの指示情報に従い、その指示情報が表すエージェントの移動先の位置の方向に移動するアクションや、指示情報が表す移動方向に移動するアクションを、次に行うべきアクション（決定アクション）utに決定し、その決定アクションutに従って、アクチュエータ１２を制御して、処理は、ステップＳ１６に進む。
【０１０７】
ステップＳ１６では、アクチュエータ１２は、反射アクション決定部１１の制御に従って駆動し、これにより、エージェントは、決定アクションutを行う。
【０１０８】
このとき、センサ１３は、アクチュエータ１２を観測しており、エージェントが行ったアクションut（を表すシンボル）を出力する。
【０１０９】
そして、処理は、ステップＳ１６からステップＳ１７に進み、履歴記憶部１４は、センサ１３が出力した観測値otとアクションutとを、観測値及びアクションの履歴として、既に記憶している観測値及びアクションの系列に追加する形で記憶する。その後、処理は、ステップＳ１８に進み、以下、上述した場合と同様の処理が行われる。
【０１１０】
以上のように、反射アクションモードでは、ユーザの指示がない限り、エージェントは、生得的なルールに従って、次に行うべきアクションを決定し、そのアクションを行うが、ユーザの指示があった場合には、優先的に、ユーザの指示に従って、次に行うべきアクションを決定し、そのアクションを行う。
【０１１１】
生得的なルール、又は、ユーザの指示に従ってアクションを行うエージェントにおいて観測される観測値otの系列（観測値系列）と、観測値otが観測されるときにエージェントが行ったアクションutの系列（アクション系列）とは（アクションutの系列と、アクションutが行われたときにエージェントにおいて観測される値ot+1の系列とは）、履歴記憶部１４に記憶されていく。
【０１１２】
そして、エージェントでは、学習部２１が、履歴記憶部１４に記憶された観測値系列とアクション系列とを、学習データとして用いて、拡張HMMの学習を行う。
【０１１３】
拡張HMMでは、一般（従来）のHMMの状態遷移確率が、エージェントが行うアクションごとの状態遷移確率に拡張されている。
【０１１４】
［拡張HMM］
【０１１５】
図５は、拡張HMMの状態遷移確率を説明する図である。
【０１１６】
すなわち、図５Ａは、一般のHMMの状態遷移確率を模式的に示している。
【０１１７】
いま、拡張HMMを含むHMMとして、ある状態から任意の状態に状態遷移が可能なエルゴディックなHMMを採用することとする。また、HMMの状態の数がN個であるとする。
【０１１８】
この場合、一般のHMMは、N個の各状態Siから、N個の状態Sjのそれぞれへの、N×N個の状態遷移の状態遷移確率aijを、モデルパラメータとして有する。
【０１１９】
一般のHMMのすべての状態遷移確率は、状態Siから状態Sjへの状態遷移の状態遷移確率aijを、上からi番目で、左からj番目に配置した２次元のテーブルで表現することができる。
【０１２０】
ここで、HMMの状態遷移確率のテーブルを、状態遷移確率Aとも記載する。
【０１２１】
図５Ｂは、拡張HMMの状態遷移確率Aを示している。
【０１２２】
拡張HMMでは、状態遷移確率が、エージェントが行うアクションUmごとに存在する。
【０１２３】
ここで、あるアクションUmについての、状態Siから状態Sjへの状態遷移の状態遷移確率を、aij(Um)とも記載する。
【０１２４】
状態遷移確率aij(Um)は、エージェントがアクションUmを行ったときに、状態Siから状態Sjへの状態遷移が生じる確率を表す。
【０１２５】
拡張HMMのすべての状態遷移確率は、アクションUmについての、状態Siから状態Sjへの状態遷移の状態遷移確率aij(Um)を、上からi番目で、左からj番目の、奥行き方向に手前側からm番目に配置した３次元のテーブルで表現することができる。
【０１２６】
ここで、状態遷移確率Aの３次元のテーブルにおいて、垂直方向の軸を、i軸と、水平方向の軸を、j軸と、奥行き方向の軸を、m軸、又は、アクション軸と、それぞれいうこととする。
【０１２７】
また、状態遷移確率Aの３次元のテーブルを、アクション軸のある位置mで、アクション軸に垂直な平面で切断して得られる、状態遷移確率aIj(Um)で構成される平面を、アクションUmについての状態遷移確率平面ともいう。
【０１２８】
さらに、状態遷移確率Aの３次元のテーブルを、i軸のある位置Iで、i軸に垂直な平面で切断して得られる、状態遷移確率aIj(Um)で構成される平面を、状態SIについてのアクション平面ともいう。
【０１２９】
状態SIについてのアクション平面を構成する状態遷移確率aIj(Um)は、状態SIを遷移元とする状態遷移が生じるときに各アクションUmが行われる確率を表す。
【０１３０】
なお、拡張HMMは、その拡張HMMのモデルパラメータとして、アクションごとの状態遷移確率aij(Um)の他、一般のHMMと同様に、最初の時刻t=1に、状態Siにいる初期状態確率πiと、状態Siにおいて、観測値Okを観測する観測確率bi(Ok)とを有する。
【０１３１】
［拡張HMMの学習］
【０１３２】
図６は、図３の学習部２１が、履歴記憶部１４に記憶された学習データとしての観測値系列及びアクション系列を用いて行う、拡張HMMの学習の処理を説明するフローチャートである。
【０１３３】
エージェントでは、反射アクションモードや認識アクションモードの処理において、履歴記憶部１４に、観測値及びアクションの履歴として、観測値及びアクションの系列が記憶される。
【０１３４】
学習部２１は、履歴記憶部１４に、観測値及びアクションの系列が新たに記憶されると、その新たな観測値系列及びアクション系列を学習データとして用いて、拡張HMMの学習を行う。
【０１３５】
すなわち、ステップＳ３１において、学習部２１は、拡張HMMを初期化する。
【０１３６】
具体的には、学習部２１は、モデル記憶部２２に記憶された拡張HMMのモデルパラメータである初期状態確率πi、（アクションごとの）状態遷移確率aij(Um)、及び、観測確率bi(Ok)を初期化する。
【０１３７】
なお、拡張HMMの状態の数（総数）がN個であるとすると、初期状態確率πiは、例えば、1/Nに初期化される。ここで、２次元平面の迷路であるアクション環境が、横×縦がa×b個の観測単位で構成されることとすると、拡張HMMの状態の数Nとしては、マージンとする整数を△として、（a＋△）×（b＋△）個を採用することができる。
【０１３８】
また、状態遷移確率aij(Um)、及び、観測確率bi(Ok)は、例えば、確率の値としてとり得るランダムな値に初期化される。
【０１３９】
ここで、状態遷移確率aij(Um)の初期化は、各アクションUmについての状態遷移確率平面の各行について、その行の状態遷移確率aij(Um)の総和（ai,1(Um)+ai,2(Um)+・・・+ai,N(Um)）が1.0になるように行われる。
【０１４０】
同様に、観測確率bi(Ok)の初期化は、各状態Siについて、その状態Siから観測値O1，O2，・・・，OKが観測される観測確率の総和（bi(O1)+bi(O2)+・・・+bi(OK)）が1.0になるように行われる。
【０１４１】
なお、いわゆる追加学習が行われる場合には、モデル記憶部２２に記憶されている拡張HMMの初期状態確率πi、状態遷移確率aij(Um)、及び、観測確率bi(Ok)が、そのまま初期値として用いられ、ステップＳ３１の初期化は、行われない（スキップされる）。
【０１４２】
ステップＳ３１の後、処理は、ステップＳ３２に進み、以下、ステップＳ３２以降において、Baum-Welchの再推定法（をアクションについて拡張した方法）に従い、履歴記憶部１４に記憶された学習データとしてのアクション系列、及び、観測値系列を用いて、初期状態確率πi、各アクションについての状態遷移確率aij(Um)、及び、観測確率bi(Ok)を推定する、拡張HMMの学習が行われる。
【０１４３】
すなわち、ステップＳ３２では、学習部２２は、前向き確率(Forward probability)αt+1(j)と、後ろ向き確率(Backward probability)βt(i)とを算出する。
【０１４４】
ここで、拡張HMMにおいては、時刻tにおいて、アクションutが行われると、現在の状態Siから状態Sjに状態遷移し、次の時刻t+1において、状態遷移後の状態Sjで、観測値ot+1が観測される。
【０１４５】
かかる拡張HMMでは、前向き確率αt+1(j)は、現在の拡張HMM（モデル記憶部２２に現に記憶されている初期状態確率πi、状態遷移確率aij(Um)、及び、観測確率bi(Ok)で規定される拡張HMM）であるモデルΛにおいて、学習データのアクション系列u1,u2,・・・,utが観測されるとともに、観測値系列o1,o2,・・・,ot+1が観測され、時刻t+1に、状態Sjにいる確率P(o1,o2,・・・,ot+1,u1,u2,・・・,ut,st+1=j|Λ)であり、式（１）で表される。
【０１４６】
【数１】
2013058059.tif 000003
・・・（１）
【０１４７】
なお、状態stは、時刻tにいる状態を表し、拡張HMMの状態の数がN個である場合には、状態S1ないしSNのうちのいずれかである。また、式st+1=jは、時刻t+1にいる状態st+1が、状態Sjであることを表す。
【０１４８】
式（１）の前向き確率αt+1(j)は、学習データのアクション系列u1,u2,・・・,ut-1、及び、観測値系列o1,o2,・・・,otを観測して、時刻tに、状態stにいる場合に、アクションutが行われることにより（観測され）、状態遷移が生じ、時刻t+1に、状態Sjにいて、観測値ot+1を観測する確率を表す。
【０１４９】
なお、前向き確率αt+1(j)の初期値α1(j)は、式（２）で表される。
【０１５０】
【数２】
2013058059.tif 000004
・・・（２）
【０１５１】
式（２）の初期値α1(j)は、最初（時刻t=0）に、状態Sjにいて、観測値o1を観測する確率を表す。
【０１５２】
また、拡張HMMでは、後ろ向き確率βt(i)は、現在の拡張HMMであるモデルΛにおいて、時刻tに、状態Siにいて、その後、学習データのアクション系列ut+1,ut+2,・・・,uT-1が観測されるとともに、観測値系列ot+1,ot+2,・・・,oTが観測される確率P(ot+1,ot+2,・・・,oT,ut+1,ut+2,・・・,uT-1,st=i|Λ)であり、式（３）で表される。
【０１５３】
【数３】
2013058059.tif 000005
・・・（３）
【０１５４】
なお、Tは、学習データの観測値系列の観測値の個数を表す。
【０１５５】
式（３）の後ろ向き確率βt(i)は、時刻t+1に、状態Sjにいて、その後に、学習データのアクション系列ut+1,ut+2,・・・,uT-1が観測されるとともに、観測値系列ot+2,ot+3,・・・,oTが観測される場合において、時刻tに、状態Siにいて、アクションutが行われることにより（観測され）、状態遷移が生じ、時刻t+1の状態st+1が、状態Sjとなって、観測値ot+1が観測されるときに、時刻tの状態stが、状態Siである確率を表す。
【０１５６】
なお、後ろ向き確率βt(i)の初期値βT(i)は、式（４）で表される。
【０１５７】
【数４】
2013058059.tif 000006
・・・（４）
【０１５８】
式（４）の初期値βT(i)は、最後（時刻t=T）に、状態Siにいる確率が、1.0であること、つまり、最後に、必ず、状態Siにいることを表す。
【０１５９】
拡張HMMでは、式（１）及び式（３）に示したように、ある状態Siからある状態Sjへの状態遷移の状態遷移確率として、アクションごとの状態遷移確率aij(ut)を用いる点が、一般のHMMと異なる。
【０１６０】
ステップＳ３２において、前向き確率αt+1(j)と、後ろ向き確率βt(i)とを算出した後、処理は、ステップＳ３３に進み、学習部２１は、前向き確率αt+1(j)と、後ろ向き確率βt(i)とを用いて、拡張HMMのモデルパラメータΛである初期状態確率πi、アクションUmごとの状態遷移確率aij(Um)、及び、観測確率bi(Ok)を再推定する。
【０１６１】
ここで、モデルパラメータの再推定は、状態遷移確率が、アクションUmごとの状態遷移確率aij(Um)に拡張されていることに伴い、Baum-Welchの再推定法を拡張して、以下のように行われる。
【０１６２】
すなわち、現在の拡張HMMであるモデルΛにおいて、アクション系列U=u1,u2,・・・,uT-1と、観測値系列O=o1,o2,・・・,oTとが観測される場合に、時刻tで、状態Siにいて、アクションUmが行われることにより、時刻t+1に、状態Sjに状態遷移している確率ξt+1(i,j,Um)は、前向き確率αt(i)と、後ろ向き確率βt+1(j)とを用いて、式（５）で表される。
【０１６３】
【数５】
2013058059.tif 000007
・・・（５）
【０１６４】
さらに、時刻tに、状態Siにいて、アクションut＝Umが行われる確率γt(i,Um)は、確率ξt+1(i,j,Um)について、時刻t+1にいる状態Sjに関して周辺化した確率として計算することができ、式（６）で表される。
【０１６５】
【数６】
2013058059.tif 000008
・・・（６）
【０１６６】
学習部２１は、式（５）の確率ξt+1(i,j,Um)、及び、式（６）の確率γt(i,Um)を用い、拡張HMMのモデルパラメータΛの再推定を行う。
【０１６７】
ここで、モデルパラメータΛの再推定を行って得られる推定値を、ダッシュ(')を用いて、モデルパラメータΛ'と表すこととすると、モデルパラメータΛ'である初期状態確率の推定値π'iは、式（７）に従って求められる。
【０１６８】
【数７】
2013058059.tif 000009
・・・（７）
【０１６９】
また、モデルパラメータΛ'であるアクションごとの状態遷移確率の推定値a'ij(Um)は、式（８）に従って求められる。
【０１７０】
【数８】
2013058059.tif 000010
・・・（８）
【０１７１】
ここで、式（８）の状態遷移確率の推定値a'ij(Um)の分子は、状態Siにいて、アクションut=Umを行って、状態Sjに状態遷移する回数の期待値を表し、分母は、状態Siにいて、アクションut=Umを行って、状態遷移する回数の期待値を表す。
【０１７２】
モデルパラメータΛ'である観測確率の推定値b'j(Ok)は、式（９）に従って求められる。
【０１７３】
【数９】
2013058059.tif 000011
・・・（９）
【０１７４】
ここで、式（９）の観測確率の推定値b'j(Ok)の分子は、状態Sjへの状態遷移が行われ、その状態Sjで、観測値Okが観測される回数の期待値を表し、分母は、状態Sjへの状態遷移が行われる回数の期待値を表す。
【０１７５】
ステップＳ３３において、モデルパラメータΛ'である初期状態確率、状態遷移確率、及び、観測確率の推定値π'i，a'ij(Um)、及び、b'j(Ok)を再推定した後、学習部２１は、推定値π'iを、新たな初期状態確率πiとして、推定値a'ij(Um)を、新たな状態遷移確率aij(Um)として、推定値b'j(Ok)を、新たな観測確率bj(Ok)として、それぞれ、モデル記憶部２２に、上書きの形で記憶させ、処理は、ステップＳ３４に進む。
【０１７６】
ステップＳ３４では、拡張HMMのモデルパラメータ、すなわち、モデル記憶部２２に記憶された（新たな）初期状態確率πi、状態遷移確率aij(Um)、及び、観測確率bj(Ok)が、収束したかどうかを判定する。
【０１７７】
ステップＳ３４において、拡張HMMのモデルパラメータが、まだ収束していないと判定された場合、処理は、ステップＳ３２に戻り、モデル記憶部２２に記憶された新たな初期状態確率πi、状態遷移確率aij(Um)、及び、観測確率bj(Ok)を用いて、同様の処理が繰り返される。
【０１７８】
また、ステップＳ３４において、拡張HMMのモデルパラメータが収束したと判定された場合、すなわち、例えば、ステップＳ３３の再推定の前と後とで、拡張HMMのモデルパラメータが、ほとんど変化しなくなった場合や、拡張HMMにおいて、学習データが観測される尤度が、ほとんど変化しなくなった場合、拡張HMMの学習の処理は終了する。
【０１７９】
以上のように、アクションごとの状態遷移確率aij(Um)で規定される拡張HMMの学習を、エージェントが行うアクションのアクション系列と、エージェントがアクションを行ったときにエージェントにおいて観測される観測値の観測値系列とを用いて行うことにより、拡張HMMにおいて、観測値系列を通して、アクション環境の構造が獲得されるとともに、各観測値と、その観測値が観測されるときに行われたアクションとの関係（エージェントが行うアクションと、そのアクションが行われたときに観測される観測値（アクション後に観測される観測値）との関係）が獲得される。
【０１８０】
その結果、かかる学習後の拡張HMMを用いることにより、認識アクションモードにおいて、後述するように、アクション環境内のエージェントが行うべきアクションとして、適切なアクションを決定することができる。
【０１８１】
なお、拡張HMMの状態Siの観測確率bi(Ok)は、その状態Siにおいて、各観測値Okが観測される確率であるから、状態Siは、その状態Siの観測確率bi(Ok)で各観測値Okが観測されるアクション環境（本実施の形態では、迷路）上の位置に対応させることができる（対応すると考えることができる）。
【０１８２】
［認識アクションモードの処理］
【０１８３】
図７は、図３のエージェントが行う、認識アクションモードの処理を説明するフローチャートである。
【０１８４】
認識アクションモードでは、エージェントは、上述したように、目標の決定、及び、現在状態の認識を行い、現在状態から目標を達成するためのアクションプランを算出する。さらに、エージェントは、アクションプランに従って、次に行うべきアクションを決定し、そのアクションを行う。そして、エージェントは、以上の処理を繰り返す。
【０１８５】
すなわち、ステップＳ４１において、状態認識部２３は、時刻をカウントする変数tを、初期値としての、例えば、1に設定し、処理は、ステップＳ４２に進む。
【０１８６】
ステップＳ４２では、センサ１３が、アクション環境から、現在の観測値（時刻tの観測値）otを取得して出力し、処理は、ステップＳ４３に進む。
【０１８７】
ステップＳ４３では、履歴記憶部１４は、センサ１３が取得した時刻tの観測値otと、その観測値otが観測されるときに（センサ１３において観測値otが取得される直前に）、センサ１３が出力したアクションut-1（直前の時刻t-1にエージェントが行ったアクションut-1）とを、観測値及びアクションの履歴として、既に記憶している観測値及びアクションの系列に追加する形で記憶し、処理は、ステップＳ４４に進む。
【０１８８】
ステップＳ４４では、状態認識部２３は、拡張HMMに基づき、エージェントが行ったアクションと、そのアクションが行われたときにエージェントにおいて観測された観測値とを用いて、エージェントの現在の状態、つまり、拡張HMMにおいて、いまいる状態である現在状態を求める。
【０１８９】
すなわち、状態認識部２３は、履歴記憶部１４から、最新の０個以上のアクションのアクション系列と、最新の１個以上の観測値の観測値系列とを、エージェントの現在状態を認識するのに用いる認識用のアクション系列、及び、観測値系列として読み出す。
【０１９０】
さらに、状態認識部２３は、モデル記憶部２２に記憶された拡張HMM（学習済みの拡張HMM）において、認識用のアクション系列、及び、観測値系列を観測して、時刻（現在時刻）tに、状態Sjにいる状態確率の最大値である最適状態確率δt(j)と、その最適状態確率δt(j)が得られる状態系列である最適経路（パス）ψt(j)とを、例えば、Viterbiアルゴリズム（をアクションに拡張したアルゴリズム）に従って求める。
【０１９１】
ここで、Viterbiアルゴリズムによれば、一般のHMMにおいて、ある観測値系列が観測されるときに辿る状態の系列（状態系列）のうちの、その観測値系列が観測される尤度を最大にする状態系列（最尤状態系列）を推定することができる。
【０１９２】
但し、拡張HMMでは、状態遷移確率が、アクションについて拡張されているため、Viterbiアルゴリズムを拡張HMMに適用するには、Viterbiアルゴリズムを、アクションについて拡張する必要がある。
【０１９３】
このため、状態認識部２３では、式（１０）及び式（１１）に従って、それぞれ、最適状態確率δt(j)、及び、最適経路ψt(j)が求められる。
【０１９４】
【数１０】
2013058059.tif 000012
・・・（１０）
【０１９５】
【数１１】
2013058059.tif 000013
・・・（１１）
【０１９６】
ここで、式（１０）のmax［X］は、状態Siを表すサフィックスiを、1から、状態の数Nまでの範囲の整数に変えて得られるXのうちの最大値を表す。また、式（１１）のargmax{X}は、サフィックスiを、1からNまでの範囲の整数に変えて得られるXを最大にするサフィックスiを表す。
【０１９７】
状態認識部２３は、認識用のアクション系列、及び、観測値系列を観測して、時刻tに、式（１０）の最適状態確率δt(j)を最大にする状態Sjに辿り着く状態系列である最尤状態系列を、式（１１）の最適経路ψt(j)から求める。
【０１９８】
さらに、状態認識部２３は、最尤状態系列の最後の状態を、現在状態stとして求める（認識する）。
【０１９９】
状態認識部２３は、現在状態stを求めると、さらに、ステップＳ４４において、その現在状態stが、既知の状態（既知状態）であるか、又は、未知の状態（未知状態）であるかを判定する。
【０２００】
ここで、認識用の観測値系列（、又は、認識用の観測値系列、及び、アクション系列）を、Oと表すとともに、認識用の観測値系列O、及び、アクション系列が観測される最尤状態系列を、Xと表す。なお、最尤状態系列Xを構成する状態の数は、認識用の観測値系列Oの系列長qに等しい。
【０２０１】
また、認識用の観測値系列Oの最初の観測値が観測される時刻tを、例えば、1として、最尤状態系列Xの、時刻tの状態（先頭からt番目の状態）を、Xtと表すとともに、時刻tの状態Xtから、時刻t+1の状態Xt+1への状態遷移の状態遷移確率を、A(Xt,Xt+1)と表すこととする。
【０２０２】
さらに、最尤状態系列Xにおいて、認識用の観測値系列Oが観測される尤度を、P(O|X)と表すこととする。
【０２０３】
ステップＳ４４において、状態認識部２３は、現在状態stが既知状態であるか、又は、未知状態であるかを判定するにあたり、例えば、式A(Xt,Xt+1)＞Threstrans（但し、t＝1,2,・・・,q-1）、及び、式P(O|X)＞Thresobsが満たされるかどうかを判定する。
【０２０４】
ここで、式A(Xt,Xt+1)＞Threstransの閾値Threstransは、状態Xtから状態Xt+1への状態遷移があり得るのかどうかを切り分けるための閾値である。
【０２０５】
また、式P(O|X)＞Thresobsの閾値Thresobsは、最尤状態系列Xにおいて、認識用の観測値系列Oが観測されることがあり得るのかどうかを切り分けるための閾値である。
【０２０６】
閾値Threstrans及びThresobsとしては、例えば、シミュレーション等によって、上述の切り分けを適切に行うことができる値が設定される。
【０２０７】
式A(Xt,Xt+1)＞Threstrans、及び、式P(O|X)＞Thresobsのうちの少なくとも一方が満たされない場合、状態認識部２３は、ステップＳ４４において、エージェントの現在状態が、未知状態であると判定する。
【０２０８】
また、式A(Xt,Xt+1)＞Threstrans、及び、式P(O|X)＞Thresobsの両方が満たされる場合、状態認識部２３は、ステップＳ４４において、エージェントの現在状態が、既知状態であると判定する。
【０２０９】
ここで、上述したように、拡張HMMの状態Siは、その状態Siの観測確率bi(Ok)で各観測値Okが観測されるアクション環境（本実施の形態では、迷路）上の位置に対応させることができる。
【０２１０】
拡張HMMにおいて、状態Siに対応するアクション環境上の位置付近の構造がある程度獲得されている場合、状態Siは既知状態であり、そうでない場合、状態Siは未知状態である。
【０２１１】
したがって、拡張HMMの学習が、状態Siに対応するアクション環境上の位置付近で観測される観測値系列、及び、アクション系列を用いて、ある程度（十分に）行われている場合、状態Siは、既知状態である。一方、拡張HMMの学習が、状態Siに対応するアクション環境上の位置付近で観測される観測値系列、及び、アクション系列を用いて、まったく（ほとんど）行われていない場合、状態Siは、未知状態である。
【０２１２】
ステップＳ４４において、現在状態が、未知状態であると判定された場合、エージェントは、認識アクションモードの処理を終了し、未知状態に対応するアクション環境上の位置付近（で観測される観測値を用いて、拡張HMM）を学習するために、反射アクションモードの処理（図４）を開始する。
【０２１３】
また、ステップＳ４４において、現在状態が、既知状態であると判定された場合、状態認識部２３は、現在状態を、アクション決定部２４に供給して、処理は、ステップＳ４５に進む。
【０２１４】
ステップＳ４５では、目標決定部１６が、拡張HMMの状態の中から、目標状態を決定する目標状態決定処理を行い、その目標状態決定処理で決定された目標状態を、アクション決定部２４に供給して、処理は、ステップＳ４６に進む。
【０２１５】
ステップＳ４６では、アクション決定部２４は、モデル記憶部２２に記憶された拡張HMMに基づき、状態認識部２３からの現在状態から、目標決定部１６からの目標状態までの状態遷移の尤度を最も高くするアクションの系列であるアクションプランを、例えば、Viterbiアルゴリズム（をアクションに拡張したアルゴリズム）に従って算出する。
【０２１６】
ここで、Viterbiアルゴリズムによれば、一般のHMMにおいて、２つの状態のうちの一方から他方に到達する状態系列、すなわち、例えば、現在状態から目標状態に到達する状態系列のうちの、ある観測値系列が観測される尤度を最も高くする最尤状態系列を推定することができる。
【０２１７】
但し、上述したように、拡張HMMでは、状態遷移確率が、アクションについて拡張されているため、Viterbiアルゴリズムを拡張HMMに適用するには、Viterbiアルゴリズムを、アクションについて拡張する必要がある。
【０２１８】
このため、アクション決定部２４では、式（１２）に従って、状態確率δ't(j)が求められる。
【０２１９】
【数１２】
2013058059.tif 000014
・・・（１２）
【０２２０】
ここで、式（１２）のmax［X］は、状態Siを表すサフィックスiを、1から、状態の数Nまでの範囲の整数に変え、かつ、アクションUmを表すサフィックスmを、1から、アクションの数Mまでの範囲の整数に変えて得られるXのうちの最大値を表す。
【０２２１】
式（１２）は、最適状態確率δt(j)を求める式（１０）から、観測確率bj(ot)を削除した式になっている。また、式（１２）では、アクションUmを考慮して、状態確率δ't(j)が求められるが、その点が、Viterbiアルゴリズムの、アクションについての拡張に相当する。
【０２２２】
アクション決定部２４は、式（１２）の計算を、前向き方向に実行し、時刻ごとに、最大の状態確率δ't(j)をとるサフィックスiと、そのサフィックスiが表す状態Siに至る状態遷移が生じるときに行われるアクションUmを表すサフィックスmを一時保存する。
【０２２３】
アクション決定部２４は、現在状態stを最初の状態として、式（１２）の状態確率δ't(j)を計算していき、目標状態Sgoalの状態確率δ't(Sgoal)が、式（１３）に示すように、所定の閾値δ'th以上となったときに、式（１２）の状態確率δ't(j)の計算を終了する。
【０２２４】
【数１３】
2013058059.tif 000015
・・・（１３）
【０２２５】
なお、式（１３）の閾値δ'thは、例えば、式（１４）に従って設定される。
【０２２６】
【数１４】
2013058059.tif 000016
・・・（１４）
【０２２７】
ここで、式（１４）において、T'は、式（１２）の計算回数（式（１２）から求められる最尤状態系列の系列長）を表す。
【０２２８】
式（１４）によれば、尤もらしい状態遷移が１回生じた場合の状態確率として、0.9を採用して、閾値δ'thが設定される。
【０２２９】
したがって、式（１３）によれば、尤もらしい状態遷移がT'回だけ連続した場合に、式（１２）の状態確率δ't(j)の計算が終了する。
【０２３０】
アクション決定部２４は、式（１２）の状態確率δ't(j)の計算を終了すると、その終了時にいる状態、つまり、目標状態Sgoalから、状態Si及びアクションUmについて保存しておいたサフィックスi及びmを、逆方向に、現在状態stに至るまで辿ることで、現在状態stから目標状態Sgoalに到達する最尤状態系列（多くの場合、最短経路）と、その最尤状態系列が得られる状態遷移が生じるときに行われるアクションUmの系列とを求める。
【０２３１】
すなわち、アクション決定部２４は、上述したように、式（１２）の状態確率δ't(j)の計算を、前向き方向に実行するときに、最大の状態確率δ't(j)をとるサフィックスiと、そのサフィックスiが表す状態Siに至る状態遷移が生じるときに行われるアクションUmを表すサフィックスmとを、時刻ごとに保存する。
【０２３２】
時刻ごとのサフィックスiは、時間を遡る方向に、状態Sjから、どの状態Siに戻る場合が、最大の状態確率が得られるかを表し、時刻ごとのサフィックスmは、その最大の状態確率が得られる状態遷移が生じるアクションUmを表す。
【０２３３】
したがって、時刻ごとのサフィックスi及びmを、式（１２）の状態確率δ't(j)の計算を終了した時刻から１時刻ずつ遡っていき、式（１２）の状態確率δ't(j)の計算を開始した時刻まで到達すると、現在状態stから目標状態Sgoalに至るまでの状態系列の状態のサフィックスの系列と、その状態系列の状態遷移が生じるときに行われるアクション系列のアクションのサフィックスの系列とのそれぞれを、時間を遡る順に並べた系列を得ることができる。
【０２３４】
アクション決定部２４は、この時間を遡る順に並べた系列を、時間順に並べ替えることで、現在状態stから目標状態Sgoalに至るまでの状態系列（最尤状態系列）と、その状態系列の状態遷移が生じるときに行われるアクション系列とを求める。
【０２３５】
以上のようにして、アクション決定部２４で求められる、現在状態stから目標状態Sgoalに至るまでの最尤状態系列の状態遷移が生じるときに行われるアクション系列が、アクションプランである。
【０２３６】
ここで、アクション決定部２４において、アクションプランとともに求められる最尤状態系列は、エージェントが、アクションプラン通りにアクションを行った場合に生じる（はずの）状態遷移の状態系列である。したがって、エージェントが、アクションプラン通りにアクションを行った場合に、最尤状態系列である状態の並びの通りでない状態遷移が生じたときには、エージェントが、アクションプラン通りにアクションを行っても、目標状態に到達しない可能性がある。
【０２３７】
ステップＳ４６において、アクション決定部２４が、上述したようにして、アクションプランを求めると、処理は、ステップＳ４７に進み、アクション決定部２４は、アクションプランに従い、エージェントが次に行うべきアクションutを決定し、処理は、ステップＳ４８に進む。
【０２３８】
すなわち、アクション決定部２４は、アクションプランとしてのアクション系列のうちの最初のアクションを、エージェントが次に行うべき決定アクションutとする。
【０２３９】
ステップＳ４８では、アクション決定部２４は、直前のステップＳ４７で決定したアクション（決定アクション）utに従って、アクチュエータ１２を制御し、これにより、エージェントは、アクションutを行う。
【０２４０】
その後、処理は、ステップＳ４８からステップＳ４９に進み、状態認識部２３は、時刻tを1だけインクリメントして、処理は、ステップＳ４２に戻り、以下、同様の処理が繰り返される。
【０２４１】
以上のように、状態認識部２３において、拡張HMMに基づき、エージェントが行ったアクションと、そのアクションが行われたときにエージェントにおいて観測された観測値とを用いて、エージェントの現在状態を認識する一方、目標決定部１６において、目標状態を決定し、アクション決定部２４において、拡張HMMに基づき、現在状態から目標状態までの状態遷移の尤度（状態確率）を最も高くするアクションの系列であるアクションプランを算出し、そのアクションプランに従い、エージェントが次に行うべきアクションを決定するので、エージェントが目標状態に到達するために、エージェントが行うべきアクションとして、適切なアクションを決定することができる。
【０２４２】
なお、認識アクションモードでは、現在状態が既知状態である場合には、上述したように、現在状態から目標状態に到達するアクションが行われるが、現在状態が未知状態である場合には、ステップＳ４４で説明したように、エージェントは、認識アクションモードを終了し、未知状態に対応するアクション環境上の位置付近（で観測される観測値を用いて、拡張HMM）を学習するために、反射アクションモードの処理（図４）を開始する。
【０２４３】
ここで、図３で説明したように、モデル記憶部２２に記憶させる状態遷移確率モデルとしては、拡張HMMの他、一般のHMMを採用することができる。
【０２４４】
但し、状態遷移確率モデルとして、一般のHMMを採用する場合には、観測値系列を学習するHMMと、そのHMMの状態遷移を実現するアクションを出力する関数等であるアクションのコントローラとを、別個に用意して、学習を行う必要がある。
【０２４５】
これに対して、拡張HMMでは、その拡張HMMにおいて、観測値系列とアクション系列とを関連づけて学習するので、少ない計算コストと記憶リソースで、学習を行うことができる。
【０２４６】
また、状態遷移確率モデルとして、一般のHMMを採用する場合には、HMMを用いて、目標状態までの状態系列を算出し、その状態系列を得るためのアクションの算出を、アクションのコントローラを用いて行う必要がある。
【０２４７】
これに対して、拡張HMMによれば、現在状態から目標状態までの最尤状態系列と、その最尤状態系列を得るためのアクション系列とを同時に求めることができるので、少ない計算コストで、エージェントが次に行うべきアクションを決定することができる。
【０２４８】
［目標状態の決定］
【０２４９】
図８は、図７のステップＳ４５で、図３の目標決定部１６が行う目標状態決定処理を説明するフローチャートである。
【０２５０】
目標決定部１６では、ステップＳ５１において、外部目標設定部３３が、ユーザからの指示があったかどうかを判定する。
【０２５１】
ステップＳ５１において、ユーザからの指示があったと判定された場合、すなわち、例えば、ユーザが、アクション環境上の所定の位置を指定する指示を行い、その指示を表す指示情報が、ユーザ指示出力部１０から外部目標設定部３３に供給された場合、処理は、ステップＳ５２に進み、外部目標設定部３３は、ユーザ指示出力部１０からの指示情報に従い、例えば、その指示情報によって指示されているアクション環境上の位置に対応する拡張HMMの状態を、外部目標に設定し、目標選択部３１に供給して、処理は、ステップＳ５３に進む。
【０２５２】
ステップＳ５３では、目標選択部３１は、外部目標設定部３３からの外部目標を、優先的に、目標状態に選択して、アクション決定部２４に供給し、処理はリターンする。
【０２５３】
一方、ステップＳ５１において、ユーザからの指示がなかったと判定された場合、処理は、ステップＳ５４に進み、特定状態検出部３６は、モデル記憶部２２に記憶された拡張HMMの状態の中から、特定状態（となっている状態）を検出することができたかどうかを判定する。
【０２５４】
ステップＳ５４において、特定状態を検出することができたと判定された場合、特定状態検出部３６は、その特定状態を、内部目標として、目標選択部３１に供給し、処理は、ステップＳ５５に進む。
【０２５５】
ステップＳ５５では、目標選択部３１は、特定状態検出部３６からの特定状態を、目標状態に選択して、アクション決定部２４に供給し、処理はリターンする。
【０２５６】
ステップＳ５４において、特定状態が検出されなかったと判定された場合、処理は、ステップＳ５６に進み、オープン端検出部３７が、モデル記憶部２２に記憶された拡張HMMの状態の中から、オープン端を検出することができたかどうかを判定する。
【０２５７】
ステップＳ５６において、オープン端を検出することができたと判定された場合、オープン端検出部３７は、そのオープン端を、内部目標として、目標選択部３１に供給し、処理は、ステップＳ５７に進む。
【０２５８】
ステップＳ５７では、目標選択部３１は、特定状態検出部３６からのオープン端である拡張HMMの状態を、目標状態に選択して、アクション決定部２４に供給し、処理はリターンする。
【０２５９】
また、ステップＳ５６において、オープン端を検出することができなかったと判定された場合、処理は、ステップＳ５８に進み、目標選択部３１は、ランダム目標生成部３５がモデル記憶部２２に記憶された拡張HMMから、ランダムに選択した状態（ランダム目標）を、目標状態に選択して、アクション決定部２４に供給し、処理はリターンする。
【０２６０】
すなわち、ランダム目標生成部３５は、拡張HMMの状態の１つをランダムに選択しており、ステップＳ５８では、そのランダムに選択された状態が、目標状態に選択される。
【０２６１】
なお、ランダム目標生成部３５による状態のランダムな選択、特定状態検出部３６による特定状態の検出、及び、オープン端検出部３７によるオープン端の検出は、例えば、エージェントがアクションを行うアクション環境を提供するアプリケーションや、ユーザ等の外部からの指示に従って行うことができる。
【０２６２】
さらに、特定状態検出部３６において検出する特定状態としては、拡張HMMの任意の状態を採用することができる。拡張HMMの、どの状態を、特定状態とするかは、例えば、アプリケーションやユーザ等の外部から指示することができる。
【０２６３】
［オープン端の検出］
【０２６４】
図９は、図３のオープン端検出部３７が検出するオープン端である拡張HMMの状態を説明する図である。
【０２６５】
オープン端とは、大雑把には、拡張HMMにおいて、ある状態を遷移元として、エージェントが未経験の状態遷移が起こり得ることがあらかじめ分かっている、その遷移元の状態である。
【０２６６】
具体的には、ある状態の状態遷移確率と、その状態と同一の観測値を観測する観測確率が割り当てられた（0.0（とみなされる値）でない値になっている）他の状態の状態遷移確率とを比較した場合に、あるアクションを行ったときに次の状態に状態遷移することが可能なことが分かるにも関わらず、まだ、その状態で、そのアクションを行ったことがないため、状態遷移確率が割り当てられておらず（0.0（とみなされる値）になっており）、状態遷移ができないことになっている状態が、オープン端に該当する。
【０２６７】
したがって、拡張HMMにおいて、所定の観測値が観測される状態を遷移元として行うことが可能な状態遷移の中で、行われたことがない状態遷移がある、所定の観測値と同一の観測値が観測される他の状態を検出すれば、その、他の状態が、オープン端である。
【０２６８】
オープン端は、概念的には、図９に示すように、例えば、エージェントが部屋に置かれ、その部屋のある範囲を対象とした学習が行われることによって、拡張HMMが獲得する構造の端部（部屋の中の学習済みの範囲の端部）や、エージェントが置かれた部屋の全範囲を対象とした学習が行われた後、その部屋に隣接して、エージェントが移動可能な新しい部屋を追加することによって現れる、新しい部屋への入り口等に対応する状態である。
【０２６９】
オープン端が検出されると、拡張HMMが獲得している構造のどの部分の先に、エージェントが未知の領域（未知状態）が広がっているかを知ることができる。したがって、オープン端を目標状態として、アクションプランを算出することにより、エージェントは、積極的に未知の領域に踏み込むアクションを行うことが可能となる。その結果、エージェントは、より広くアクション環境の構造を学習し（アクション環境の構造の学習のための学習データとなる観測系列及びアクション系列を獲得し）、拡張HMMにおいて、構造を獲得していない曖昧な部分（アクション環境の、オープン端となっている状態に対応する観測単位付近の構造）を補強するために必要な経験を効率的に得ることが可能になる。
【０２７０】
オープン端検出部３７は、オープン端を検出するのに、まず、アクションテンプレートを生成する。
【０２７１】
オープン端検出部３７は、アクションテンプレートの生成にあたり、拡張HMMの観測確率B={bi(Ok)}を閾値処理し、各観測値Okに対して、その観測値Okが閾値以上の確率で観測される状態Siをリストアップする。
【０２７２】
図１０は、オープン端検出部３７が、観測値Okが閾値以上の確率で観測される状態Siをリストアップする処理を説明する図である。
【０２７３】
図１０Ａは、拡張HMMの観測確率Bの例を示している。
【０２７４】
すなわち、図１０Ａは、状態Siの数Nが5個で、観測値Okの数Mが3個の拡張HMMの観測確率Bの例を示している。
【０２７５】
オープン端検出部３７は、閾値を、例えば、0.5等として、閾値以上の観測確率Bを検出する閾値処理を行う。
【０２７６】
この場合、図１０Ａでは、状態S1については、観測値O3が観測される観測確率b1(O3)=0.7が、状態S2については、観測値O2が観測される観測確率b2(O2)=0.8が、状態S3については、観測値O3が観測される観測確率b3(O3)=0.8が、状態S4については、観測値O2が観測される観測確率b4(O2)=0.7が、状態S5については、観測値O1が観測される観測確率b5(O1)=0.9が、それぞれ、閾値処理によって検出される。
【０２７７】
その後、オープン端検出部３７は、各観測値O1,O2,O3に対して、その観測値Okが閾値以上の確率で観測される状態Siをリストアップ検出する。
【０２７８】
図１０Ｂは、観測値O1,O2,O3それぞれに対してリストアップされる状態Siを示している。
【０２７９】
観測値O1に対しては、その観測値O1が閾値以上の確率で観測される状態として、状態S5がリストアップされ、観測値O2に対しては、その観測値O2が閾値以上の確率で観測される状態として、状態S2及びS4がリストアップされる。また、観測値O3に対して、その観測値O3が閾値以上の確率で観測される状態として、状態S1及びS3がリストアップされる。
【０２８０】
その後、オープン端検出部３７は、拡張HMMの状態遷移確率A={aij(Um)}を用い、各観測値Okについて、その観測値Okに対してリストアップされた状態Siからの状態遷移のうちの、状態遷移確率aij(Um)が最大の状態遷移の状態遷移確率aij(Um)に対応する値である遷移確率対応値を、アクションUmごとに算出し、各観測値Okについて、アクションUmごとに算出された遷移確率対応値を、観測値Okが観測されたときにアクションUmが行われるアクション確率として、アクション確率を要素とする行列であるアクションテンプレートCを生成する。
【０２８１】
すなわち、図１１は、観測値Okに対してリストアップされた状態Siを用いて、アクションテンプレートCを生成する方法を説明する図である。
【０２８２】
オープン端検出部３７は、３次元の状態遷移確率テーブルにおいて、観測値Okに対してリストアップされた状態Siからの状態遷移の、列（横）方向（j軸方向）に並ぶ状態遷移確率から、最大の状態遷移確率を検出する。
【０２８３】
すなわち、例えば、いま、観測値O2に注目し、観測値O2に対して、状態S2及びS4がリストアップされていることとする。
【０２８４】
この場合、オープン端検出部３７は、３次元の状態遷移確率テーブルを、i軸のi=2の位置で、i軸に垂直な平面で切断して得られる、状態S2についてのアクション平面に注目し、その状態S2についてのアクション平面の、アクションU1を行ったときに生じる状態S2からの状態遷移の状態遷移確率a2,j(U1)の最大値を検出する。
【０２８５】
すなわち、オープン端検出部３７は、状態S2についてのアクション平面の、アクション軸の、m=1の位置に、j軸方向に並ぶ状態遷移確率a2,1(U1),a2,2(U1),・・・,a2,N(U1)の中の最大値を検出する。
【０２８６】
同様に、オープン端検出部３７は、状態S2についてのアクション平面から、他のアクションUmを行ったときに生じる状態S2からの状態遷移の状態遷移確率の最大値を検出する。
【０２８７】
さらに、オープン端検出部３７は、観測値O2に対してリストアップされている、他の状態である状態S4についても、同様に、状態S4についてのアクション平面から、各アクションUmを行ったときに生じる状態S4からの状態遷移の状態遷移確率の最大値を検出する。
【０２８８】
以上のように、オープン端検出部３７は、観測値O2に対してリストアップされた状態S2及びS4のそれぞれについて、各アクションUmが行われたときに生じる状態遷移の状態遷移確率の最大値を検出する。
【０２８９】
その後、オープン端検出部３７は、上述したようにして検出された状態遷移確率の最大値を、アクションUmごとに、観測値O2に対してリストアップされた状態S2及びS4について、平均化し、その平均化によって得られる平均値を、観測値O2についての、状態遷移確率の最大値に対応する遷移確率対応値とする。
【０２９０】
観測値O2についての、遷移確率対応値は、アクションUmごとに求められるが、この、観測値O2について得られる、アクションUmごとの遷移確率対応値は、観測値O2が観測されたときに、アクションUmが行われる確率（アクション確率）を表す。
【０２９１】
オープン端検出部３７は、他の観測値Okについても、同様にして、アクションUmごとのアクション確率としての遷移確率対応値を求める。
【０２９２】
そして、オープン端検出部３７は、観測値Okが観測されたときに、アクションUmが行われるアクション確率を、上からk番目で、左からm番目の要素とした行列を、アクションテンプレートCとして生成する。
【０２９３】
したがって、アクションテンプレートCは、行数が、観測値Okの数Kに等しく、列数が、アクションUmの数Mに等しいK行M列の行列となる。
【０２９４】
オープン端検出部３７は、アクションテンプレートCの生成後、そのアクションテンプレートCを用いて、観測確率に基づくアクション確率Dを算出する。
【０２９５】
図１２は、観測確率に基づくアクション確率Dを算出する方法を説明する図である。
【０２９６】
いま、状態Siにおいて、観測値Okを観測する観測確率bi(Ok)を、第i行第k列の要素とする行列を、観測確率行列Bということとすると、観測確率行列Bは、行数が、状態Siの数Nに等しく、列数が観測値Okの数Kに等しいN行K列の行列となる。
【０２９７】
オープン端検出部３７は、式（１５）に従い、N行K列の観測確率行列Bに、K行M列の行列であるアクションテンプレートCを乗算することにより、観測値Okが観測される状態Siにおいて、アクションUmが行われる確率を、第i行第m列の要素とする行列である、観測確率に基づくアクション確率Dを算出する。
【０２９８】
【数１５】
2013058059.tif 000017
・・・（１５）
【０２９９】
オープン端検出部３７は、以上のようにして、観測確率に基づくアクション確率Dを算出する他、状態遷移確率に基づくアクション確率Eを算出する。
【０３００】
図１３は、状態遷移確率に基づくアクション確率Eを算出する方法を説明する図である。
【０３０１】
オープン端検出部３７は、i軸、j軸、及び、アクション軸からなる３次元の状態遷移確率テーブルAの、i軸方向の各状態Siについて、状態遷移確率aij(Um)を、アクションUmごとに加算することで、状態Siにおいて、アクションUmが行われる確率を、第i行第m列の要素とする行列である、状態遷移確率に基づくアクション確率Eを算出する。
【０３０２】
すなわち、オープン端検出部３７は、i軸、j軸、及び、アクション軸からなる状態遷移確率テーブルAの、水平方向（列方向）に並ぶ状態遷移確率aij(Um)の総和、つまり、i軸のある位置iと、アクション軸のある位置mに注目した場合に、点(i,m)を通るj軸に平行な直線上に並ぶ状態遷移確率aij(Um)の総和を求め、その総和を、行列の第i行第m列の要素とすることで、N行M列の行列である、状態遷移確率に基づくアクション確率Eを算出する。
【０３０３】
オープン端検出部３７は、以上のようにして、観測確率に基づくアクション確率Dと、状態遷移確率に基づくアクション確率Eとを算出すると、観測確率に基づくアクション確率Dと、状態遷移確率に基づくアクション確率Eとの差分である差分アクション確率Fを、式（１６）に従って算出する。
【０３０４】
【数１６】
2013058059.tif 000018
・・・（１６）
【０３０５】
差分アクション確率Fは、観測確率に基づくアクション確率Dや、状態遷移確率に基づくアクション確率Eと同様に、N行M列の行列となる。
【０３０６】
図１４は、差分アクション確率Fを模式的に示す図である。
【０３０７】
図１４において、小さな正方形は、行列の要素を表している。また、模様を付していない正方形は、0.0（とみなせる値）になっている要素を表し、黒で塗りつぶしてある正方形は、0.0（とみなせる値）でない値になっている要素を表している。
【０３０８】
差分アクション確率Fによれば、観測値Okが観測される状態として、複数の状態が存在する場合に、その複数の状態の一部の状態（エージェントがアクションUmを行ったことがある状態）からは、アクションUmを行うことができることが分かっているが、そのアクションUmが行われたときに生じる状態遷移が、状態遷移確率aij(Um)に反映されていない、残りの状態（エージェントがアクションUmを行ったことがない状態）、つまり、オープン端を検出することができる。
【０３０９】
すなわち、状態Siの状態遷移確率aij(Um)に、アクションUmが行われたときに生じる状態遷移が反映されている場合、観測確率に基づくアクション確率Dの第i行第m列の要素と、状態遷移確率に基づくアクション確率Eの第i行第m列の要素とは、同じような値となる。
【０３１０】
一方、状態Siの状態遷移確率aij(Um)に、アクションUmが行われたときに生じる状態遷移が反映されていない場合、観測確率に基づくアクション確率Dの第i行第m列の要素は、状態Siと同一の観測値が観測される、アクションUmが行われたことがある状態の状態遷移確率の影響によって、0.0とはみなせない、ある程度の値となるが、状態遷移確率に基づくアクション確率Eの第i行第m列の要素は、0.0（0.0とみなせる小さい値を含む）となる。
【０３１１】
したがって、状態Siの状態遷移確率aij(Um)に、アクションUmが行われたときに生じる状態遷移が反映されていない場合、差分アクション確率Fの第i行第m列の要素は、値（絶対値）が、0.0とみなせない値となるので、差分アクション確率Fにおいて、0.0とみなせない値になっている要素を検出することで、オープン端、及び、オープン端で行ったことがないアクションを検出することができる。
【０３１２】
すなわち、差分アクション確率Fにおいて、第i行第m列の要素の値が、0.0とみなせない値となっている場合、オープン端検出部３７は、状態Siを、オープン端として検出するとともに、アクションUmを、オープン端である状態Siで行ったことがないアクションとして検出する。
【０３１３】
図１５は、図３のオープン端検出部３７が行うオープン端の検出の処理を説明するフローチャートである。
【０３１４】
ステップＳ８１において、オープン端検出部３７は、モデル記憶部２２（図３）に記憶された拡張HMMの観測確率B={bi(Ok)}を閾値処理し、これにより、図１０で説明したように、各観測値Okに対して、その観測値Okが閾値以上の確率で観測される状態Siをリストアップする。
【０３１５】
ステップＳ８１の後、処理は、ステップＳ８２に進み、オープン端検出部３７は、図１１で説明したように、モデル記憶部２２に記憶された拡張HMMの状態遷移確率A={aij(Um)}を用い、各観測値Okについて、その観測値Okに対してリストアップされた状態Siからの状態遷移のうちの、状態遷移確率aij(Um)が最大の状態遷移の状態遷移確率aij(Um)に対応する値である遷移確率対応値を、アクションUmごとに算出し、各観測値Okについて、アクションUmごとに算出された遷移確率対応値を、観測値Okが観測されたときにアクションUmが行われるアクション確率として、アクション確率を要素とする行列であるアクションテンプレートCを生成する。
【０３１６】
その後、処理は、ステップＳ８２からステップＳ８３に進み、オープン端検出部３７は、式（１５）に従い、観測確率行列Bに、アクションテンプレートCを乗算することにより、観測確率に基づくアクション確率Dを算出し、処理は、ステップＳ８４に進む。
【０３１７】
ステップＳ８４では、オープン端検出部３７は、図１３で説明したようにして、状態遷移確率テーブルAの、i軸方向の各状態Siについて、状態遷移確率aij(Um)を、アクションUmごとに加算することで、状態Siにおいて、アクションUmが行われる確率を、第i行第m列の要素とする行列である、状態遷移確率に基づくアクション確率Eを算出する。
【０３１８】
そして、処理は、ステップＳ８４からステップＳ８５に進み、オープン端検出部３７は、観測確率に基づくアクション確率Dと、状態遷移確率に基づくアクション確率Eとの差分である差分アクション確率Fを、式（１６）に従って算出し、処理は、ステップＳ８６に進む。
【０３１９】
ステップＳ８６では、オープン端検出部３７は、差分アクション確率Fを閾値処理することで、その差分アクション確率Fにおいて、値が所定の閾値以上の要素を、検出の対象の検出対象要素として検出する。
【０３２０】
さらに、オープン端検出部３７は、検出対象要素の行iと列mとを検出し、状態Siをオープン端として検出するとともに、アクションUmを、オープン端Siにおいて行ったことがない未経験アクションとして検出して、リターンする。
【０３２１】
エージェントは、オープン端において、未経験アクションを行うことにより、オープン端の先に続く未知の領域を開拓することができる。
【０３２２】
ここで、従来の行動決定手法では、エージェントの目標は、エージェントの経験を考慮せずに、既知の領域（学習済みの領域）と、未知の領域（未学習の領域）とを対等に（区別なく）扱って決定される。このため、未知の領域の経験を積むのに、多くのアクションを行う必要があり、その結果、アクション環境の構造を広く学習するのに、多くの試行と多大な時間を要していた。
【０３２３】
これに対して、図３のエージェントでは、オープン端を検出し、そのオープン端を目標状態として、アクションを決定するので、アクション環境の構造を、効率的に学習することができる。
【０３２４】
すなわち、オープン端は、その先に、エージェントが経験していない未知の領域が広がっている状態であるから、オープン端を検出し、そのオープン端を目標状態としてアクションを決定することにより、エージェントは、積極的に未知の領域に踏み込むことができる。これにより、エージェントは、アクション環境の構造を、より広く学習するための経験を効率的に積むことができる。
【０３２５】
以上のように、図３のエージェントは、アクションを行ったときに観測される観測値を用いて、拡張HMMの学習を行う一方、生得的なルールや拡張HMMに基づいて、エージェントが行うアクションを決定するが、ユーザからの指示があった場合には、その指示を表す指示情報に従って、エージェントが行うアクションを決定するので、例えば、ユーザに飽きさせないゲームのキャラクタとなるような、娯楽性のあるエージェントを提供することができる。
【０３２６】
［ゲーム機の一実施の形態］
【０３２７】
図１６は、本技術の情報処理装置を適用したゲーム機の一実施の形態の構成例を示すブロック図である。
【０３２８】
図１６のゲーム機では、図３のエージェントと同様に構成される仮想的なエージェントが、ゲームのキャラクタに適用されている。
【０３２９】
図１６において、ゲーム機は、操作部５１、ゲーム制御部５２、及び、表示制御部５３を有する。
【０３３０】
操作部５１は、ユーザによって操作され、ユーザの操作に対応する操作信号を、ゲーム制御部５２に供給する。
【０３３１】
ゲーム制御部５２は、ゲーム環境制御部６１、及び、エージェント制御部６２を有し、操作部５１からの操作信号等に従って、ゲームのキャラクタや、ゲームのキャラクタが登場する環境（ゲーム環境）等を制御する。
【０３３２】
すなわち、ゲーム環境制御部６１は、操作部５１からの操作信号等に従って、ゲーム環境（の画像）を生成する。
【０３３３】
エージェント制御部６２は、操作部５１からの操作信号等に従って、図３のエージェントと同様に構成される仮想的なエージェント（の画像）（例えば、エージェントのインスタンス）を、ゲームのキャラクタとして生成する。
【０３３４】
ゲーム制御部５２は、ゲーム環境制御部６１で生成されたゲーム環境（の画像）に、エージェント制御部６２で生成されたエージェントを重畳することにより、ゲームの画面（の画像）を生成し、表示制御部５３に供給する。
【０３３５】
表示制御部５３は、ゲーム制御部５２からのゲームの画面を、図示せぬ表示装置に表示させる。
【０３３６】
ここで、図３のエージェントは、上述したように、迷路等のアクション環境を自律的に移動し、その移動によって観測される観測値を用いて、拡張HMMの学習を行うことにより、アクション環境（迷路）の構造を獲得し、目標状態に選択された状態に対応する迷路上の位置に移動することが可能となる。
【０３３７】
また、エージェントは、自律的に移動する他、ユーザの指示があった場合には、そのユーザの指示に従って移動する。
【０３３８】
したがって、エージェントにおいて、拡張HMMの学習（アクション環境の構造の獲得）は、ユーザの指示によって加速し、その加速の程度、つまり、拡張HMMの学習の進捗は、ユーザの指示の質によって異なる。このように、エージェントによる拡張HMMの学習の進捗が、ユーザの指示の質によって異なるので、エージェントには、ユーザの教示の仕方（ユーザの指示の質）によって、成長の仕方（拡張HMMの進捗）が変化するといった娯楽性が認められる。
【０３３９】
このような娯楽性のあるエージェントを、ゲームのキャラクタに適用することにより、ユーザに新たな感覚を享受させることができる新たなゲームを提供することができる。
【０３４０】
すなわち、新たなゲームでは、エージェントに、ゲームのための学習（知識を獲得するための学習）（以下、ゲーム学習ともいう）を行わせ、その学習後のエージェントを用いたゲームを行う。ゲーム学習では、ユーザは、エージェントに、各種の教示を行うことができ、エージェントの性能は、ユーザが行う教示に大きく依存する。
【０３４１】
そして、新たなゲームでは、例えば、ユーザは、ユーザ自身が教示、つまり、育成を行ったエージェントと対戦することや、ユーザ自身が育成を行ったエージェントと、他のユーザが育成を行ったエージェントとを対戦させることができる。
【０３４２】
また、新たなゲームでは、例えば、ユーザは、ユーザ自身が育成を行ったエージェントとチームを組み、他のユーザ及び他のユーザが育成を行ったエージェントのチームとの対戦を行うことができる。
【０３４３】
ユーザは、ゲーム学習において、適切な教示を行うことによって、エージェントの性能を変化させることができる。したがって、ユーザは、エージェントの性能を、例えば、エージェントのパラメータやプログラムの変更等によって、直接的に変化させることはできないが、適切な教示によって、間接的に変化させることができる。そして、エージェントの性能は、ユーザの教示によって、必ずしも、ユーザの思い通りに変化するとは限らず、ユーザは、その思い通りにならない感覚を享受することができる。
【０３４４】
なお、あるユーザＡが育成を行ったエージェントと、他のユーザＢが育成を行ったエージェントとの対戦は、図１６の１台のゲーム機上で行うこともできるし、２台のゲーム機をネットワークを介して接続して行うこともできる。
【０３４５】
エージェントをゲームのキャラクタに適用した新たなゲームとしては、例えば、プレイヤが、コイン等の景品が置かれた迷路内を移動しながら、コインを収集し、合計金額がより多いコインを収集したプレイヤを勝者とするコイン収集ゲームがある。
【０３４６】
コイン収集ゲームでは、例えば、プレイヤであるエージェントやユーザが、迷路の構造や、コインが置いてある場所（コイン位置）等の知識を獲得する等の、コインの収集のための事前準備を行う事前準備期間と、事前準備で獲得した知識を用いて、迷路に置かれたコインを収集する収集期間とがあり、収集期間において、合計金額がより多いコインを収集したプレイヤが勝者となる。
【０３４７】
プレイヤは、事前準備の後、コインの収集（コイン位置への移動）を開始するが、コイン収集ゲームでは、ゲームのスタート時、つまり、事前準備の開始時に、迷路の構造と、コインを置く位置とがリセットされる（新たに設定される）とともに、プレイヤは、迷路上の任意の位置に配置される。
【０３４８】
このため、ゲームのスタート直後の、プレイヤであるエージェントは、反射アクションモード（図４）により、生得的なルールに従って、迷路上を移動するアクションを行い、そのアクション時に観測される観測値（及びアクション）を用いて、拡張HMMの学習（図６）を行うことにより、迷路の構造を獲得するとともに、その観測値から、コイン位置（に対応する拡張HMMの状態）を獲得する。
【０３４９】
反射アクションモードにおいて、ある程度の観測値（及びアクション）が観測され、その結果、その観測値を用いた学習によって、拡張HMMにおいて、迷路の構造が多少なりとも獲得されると、エージェントがアクションを行うモードは、反射アクションモードから、認識アクションモード（図７）となる。
【０３５０】
認識アクションモードでは、例えば、オープン端を、目標状態に選択すると、エージェントは、図７及び図８で説明したように、オープン端、つまり、迷路上の未知の領域に移動するアクションを行う。
【０３５１】
したがって、オープン端を目標状態に選択することにより、エージェントは、既に移動した場所に何度も移動することがなくなり、迷路の構造、及び、コイン位置を効率的に獲得することができる。
【０３５２】
また、認識アクションモードにおいて、迷路上のコイン位置に対応する拡張HMMの状態を、特定状態として、その特定状態を、目標状態に選択すると、エージェントは、図７及び図８で説明したように、特定状態、つまり、コイン位置に移動するアクションを行う。
【０３５３】
したがって、コイン位置に対応する拡張HMMの状態を、特定状態として、その特定状態を、目標状態に選択することにより、エージェントは、コイン位置に移動し、そのコイン位置のコインを収集することができる。
【０３５４】
さらに、反射アクションモード、及び、認識アクションモードでは、迷路上の所定の位置を指定するように、ユーザが指示を行うと、エージェントは、図４、並びに、図７及び図８で説明したように、ユーザの指示を表す指示情報に従い、所定の位置に移動するアクションを行う。
【０３５５】
したがって、例えば、事前準備において、エージェントが、高額なコインが置いてあるコイン位置に移動していかない場合に、ユーザが、そのコイン位置を指示してあげることによって、エージェントは、高価なコインが置いてあるコイン位置（及び、現在地からそのコイン位置までの迷路の構造）を獲得することができる。
【０３５６】
エージェントをゲームのキャラクタに適用したコイン収集ゲームでは、例えば、以下のような、第１ないし第３のルールで、ゲームを行うことができる。
【０３５７】
すなわち、第１のルールでは、ユーザ（ユーザが操作する、ユーザを模したキャラクタ）と、エージェント（図３のエージェントと同様に構成される仮想的なエージェント）とが対戦し、どれだけのコインを収集することができるかを競う。
【０３５８】
ここで、エージェントの実体としてのプロセッサ（コンピュータ）と、人間であるユーザとでは、処理の実行サイクルが異なり、エージェント（プロセッサ）の方が、ユーザよりも、処理の実行サイクルがはるかに速い。このため、エージェントにおいては、ユーザがエージェントと競い合うことができるように、実行サイクルが調整される。
【０３５９】
エージェントの実行サイクルを遅くしすぎると、例えば、ユーザは、事前準備時に、コイン位置のメモをとる等して、コイン位置を正確に把握し、コインの収集時に、大量のコインを収集することが可能となるため、実行サイクルの調整は、そのようなことがないように行われる。
【０３６０】
例えば、エージェントは、アクションを行う実行サイクルを、3秒に調整して、その3秒の実行サイクル単位で、１つのアクションを行うが、3秒の実行サイクルにおいて、ユーザが、迷路内を移動する操作を行ったときには、その動作に同期して、１つのアクションを行う。このように、実行サイクルを調整することにより、ユーザは、エージェントと競い合って、コインを収集することができる。
【０３６１】
なお、ユーザが対戦を行う場合、ゲームの画面には、ユーザが操作する、ユーザを模したキャラクタが表示されるが、ユーザを模したキャラクタは、例えば、ゲーム環境制御部６１において生成される。
【０３６２】
第２のルールでは、ユーザは、事前準備において、コイン位置等を指示することによって、エージェントが、コイン位置、及び、迷路の構造を獲得する育成を行い、ユーザが育成を行ったエージェントと、ユーザ、又は、他のユーザが育成を行ったエージェントとが対戦して、どれだけのコインを収集することができるかを競う。
【０３６３】
ユーザは、事前準備において、エージェントを観察し、高額なコインが置いてあるコイン位置や、近傍に多くのコインが置いてある位置に移動していかない場合に、そのコイン位置を指示し、エージェントを、そのようなコイン位置に誘導して、半強制的に、高価なコインが置いてあるコイン位置や多数のコインが置いてある位置を獲得させる。
【０３６４】
また、事前準備において、エージェントが移動していかない迷路上の位置がある場合に、ユーザは、その位置を指示し、エージェントを、そのような位置に誘導して、半強制的に、エージェントが移動していかなかった位置付近の迷路の構造を獲得させる。
【０３６５】
以上のように、ユーザが指示を与えることによって、エージェントは、多くのコイン位置や、迷路内の広範囲の構造を、迅速に獲得することができ、性能の良いエージェントに育成される。
【０３６６】
ユーザは、育成後のエージェントと対戦し、ユーザ自身の育成（指示）の仕方の良さを楽しむことができる。
【０３６７】
また、ユーザは、ユーザ自身が育成を行ったエージェントと、他のユーザが育成を行ったエージェントとを対戦させることができる。
【０３６８】
ユーザが育成を行ったエージェントＡと、他のユーザが育成を行ったエージェントＢとの対戦では、同一の迷路を使用した事前準備の後、エージェントＡとＢとが、迷路上の同一の位置に置かれ、コインの収集が開始される。コインの収集では、エージェントＡ及びＢは、同一のタイミングでアクションを行い、例えば、100回のアクションで収集することができたコインの金額（総額）を競う。
【０３６９】
エージェントＡ及びＢのユーザは、事前準備では、それぞれのエージェントに対して指示を行うが（エージェントの育成を行うが）、コインの収集では、観戦を行うだけとなる。
【０３７０】
なお、エージェントＡ及びＢの対戦は、例えば、ネットワーク経由で行うことができる。
【０３７１】
第３のルールでは、ユーザは、エージェントとチームを組んで、コインを収集する。
【０３７２】
この場合、ユーザとエージェントとは、分担（共同）して作業を行う。
【０３７３】
すなわち、事前準備において、ユーザが、迷路の一部の範囲について、迷路の構造、及び、コイン位置を記憶し、エージェントに、迷路の残りの範囲について、迷路の構造、及び、コイン位置を獲得させる。
【０３７４】
そして、コインの収集では、ユーザは、迷路の一部の範囲を対象に、コインの収集を行い、エージェントは、迷路の残りの範囲を対象に、コインの収集を行う。
【０３７５】
この場合、ユーザが収集したコインとエージェントが収集したコインとの合計のコインの金額が、ユーザとエージェントとのチームの得点とされ、ユーザは、チームの得点として、高い得点をとることを目標として、ゲームを行う。
【０３７６】
また、第３のルールでは、ユーザのチームと、他のユーザのチームとの対戦を行うことができる。ユーザのチームと、他のユーザのチームとの対戦は、ネットワーク経由で行うことができる。
【０３７７】
なお、チームには、１つのエージェントの他、複数のエージェントを含めることができる。但し、チームどうしの対戦では、チームに含めるエージェントの数は、一致させることが望ましい。
【０３７８】
以上のように、図３のエージェントと同様に構成される仮想的なエージェントを、ゲームのキャラクタに適用した（新たな）ゲームによれば、ユーザは、ゲームのキャラクタとしてのエージェントを育成し、その育成後のエージェントと対戦することや、ユーザが育成を行ったエージェントと、他のユーザが育成を行ったエージェントとを対戦させること等ができる。
【０３７９】
なお、図３のエージェントと同様に構成される仮想的なエージェントは、コイン収集ゲーム以外の、例えば、アドベンチャゲームやボードゲーム等のキャラクタに適用することができる。
【０３８０】
図１７は、コイン収集ゲームのゲーム環境の例を示す図である。
【０３８１】
図１７のゲーム環境では、迷路に、コインが置かれている。迷路内に置かれているコインとしては、金額（価値）が異なる複数種類（図１７では、２種類）のコインが採用されている。
【０３８２】
ゲームのキャラクタに適用されたエージェント（図３のエージェントと同様に構成される仮想的なエージェント）は、ゲーム環境の迷路内を、上下左右の４方向に、１マス単位で移動することができる。
【０３８３】
エージェントは、迷路の各マスにおいて、そのマスを基準とする一定の範囲だけを観測することができるが、迷路全体を観察することはできない。
【０３８４】
図１８は、エージェントが迷路のマスにおいて観測することができる範囲の例を示す図である。
【０３８５】
図１８Ａでは、エージェントは、迷路の各マスにおいて、エージェントがいるマスだけ、すなわち、エージェントがいるマスの壁と、そのマスから移動することができる方向だけを観測することができる。
【０３８６】
図１８Ｂでは、エージェントは、迷路の各マスにおいて、エージェントがいるマスと、そのマスの８方向それぞれに隣接する８個のマスとの、合計で９マスを観測することができる。
【０３８７】
図１９は、コイン収集ゲームについて、図１６のゲーム機が行う処理（ゲーム制御）を説明するフローチャートである。
【０３８８】
ステップＳ９１において、ゲーム環境制御部６１は、コインが置かれた迷路（の画像）を、ゲーム環境（の画像）として生成する。さらに、ステップＳ９１において、エージェント制御部６２は、図３のエージェントと同様に構成される仮想的なエージェント（の画像）を、ゲームのキャラクタとして生成する。
【０３８９】
そして、ゲーム制御部５２は、ゲーム環境制御部６１で生成されたゲーム環境（の画像）に、エージェント制御部６２で生成されたエージェントを重畳することにより、ゲームの画面（の画像）を生成し、表示制御部５３に供給する。
【０３９０】
表示制御部５３は、ゲーム制御部５２からのゲームの画面の表示を開始し、処理は、ステップＳ９１からステップＳ９２に進む。
【０３９１】
ステップＳ９２では、エージェント制御部６２は、エージェントに事前準備を行わせる事前準備制御を行う。
【０３９２】
すなわち、エージェント制御部６２は、エージェント（図３）を、反射アクションモードにする。
【０３９３】
反射アクションモード（図４）では、エージェントは、生得的なルールに従って、迷路上を移動するアクションを行い、そのアクション時に観測される観測値（及びアクション）を用いて、拡張HMMの学習（図６）を行うことにより、迷路の構造を獲得するとともに、その観測値から、コイン位置を獲得する。
【０３９４】
反射アクションモードにおいて、ある程度の観測値（及びアクション）が観測されると、その観測値を用いた学習によって、拡張HMMにおいて、迷路の構造が多少なりとも獲得される。そして、反射アクションモードにおいて、エージェントが、あらかじめ指定された回数だけアクションを行うと（図４のステップＳ１８）、エージェントは、反射アクションモードから、認識アクションモード（図７）となる。
【０３９５】
事前準備制御では、エージェント制御部６２は、エージェント（図３）の外部目標設定部３３、ランダム目標生成部３５、特定状態検出部３６、及び、オープン端検出部３７のうちの、外部目標設定部３３、ランダム目標生成部３５、及び、オープン端検出部３７を有効にし（動作させ）、特定状態検出部３６を無効にする（停止させる）。
【０３９６】
その結果、事前準備制御において、エージェントがアクションを行うモードが、認識アクションモードである場合の目標状態は、ユーザからの指示に従った状態、オープン端、及び、拡張HMMの状態の中からランダムに選択された状態のうちのいずれかに制限される。
【０３９７】
そして、ユーザからの指示があった場合には、図８で説明したように、目標設定部３３において、そのユーザからの指示を表す指示情報に従って、外部目標が設定され、目標選択部３１において、目標状態に選択される。
【０３９８】
この場合、エージェントは、迷路上を、指示情報に従って設定された外部目標を目標状態とするアクションプランに従って移動し、すなわち、ユーザからの指示に従って移動し、迷路の構造、及び、コイン位置を獲得する。
【０３９９】
また、ユーザからの指示がなく、オープン端検出部３７において、オープン端が検出された場合には、図８で説明したように、目標選択部３１において、オープン端が、目標状態に選択される。
【０４００】
この場合、エージェントは、オープン端を目標状態とするアクションプランに従い、迷路上を、オープン端である拡張HMMの状態に対応する位置に向かって、未知の領域を開拓するかのごとく移動し、迷路の構造、及び、コイン位置を獲得する。
【０４０１】
ユーザからの指示がなく、また、オープン端検出部３７において、オープン端が検出されない場合には、図８で説明したように、ランダム目標生成部３５において、拡張HMMの状態の中から、１つの状態がランダムに選択され、目標選択部３１において、その状態が、目標状態に選択される。
【０４０２】
ここで、オープン端検出部３７において、オープン端が検出されない場合というのは、エージェントが、ゲーム環境（迷路）の構造のすべてを獲得している場合である。迷路の規模や、事前準備期間は、オープン端が検出されなくなることがないように設定される。
【０４０３】
以上のように、事前準備では、エージェントは、未知の領域を開拓するかのごとく移動することによって、また、ユーザからの指示があった場合には、優先的に、そのユーザからの指示を表す指示情報に従って移動することによって、迷路の構造、及び、コイン位置を獲得する。
【０４０４】
事前準備が開始されてから、あらかじめ設定された事前準備期間が経過すると、処理は、ステップＳ９２からステップＳ９３に進み、エージェント制御部６２は、エージェントにコインを収集させるコイン収集制御を行う。
【０４０５】
コイン収集制御では、エージェント制御部６２は、エージェント（図３）の外部目標設定部３３、ランダム目標生成部３５、特定状態検出部３６、及び、オープン端検出部３７のうちの、特定状態検出部３６を有効にし、外部目標設定部３３、ランダム目標生成部３５、及び、オープン端検出部３７を無効にする。
【０４０６】
その結果、コイン収集制御では、エージェントがアクションを行うモードが、認識アクションモードである場合の目標状態は、特定状態に制限される。
【０４０７】
さらに、コイン収集制御では、エージェント制御部６２は、事前準備で獲得したコイン位置の中で、コイン収集制御が開始されてから、エージェントが到着したことがないコイン位置（以下、未到着位置ともいう）に対応する拡張HMMの状態を、特定状態として検出するように、エージェント（図３）の特定状態検出部３６を制御する。
【０４０８】
特定状態検出部３６では、エージェント制御部６２の制御に従い、拡張HMMの状態の中から、未到着位置の１つに対応する状態が、特定状態として検出され、目標選択部３１において、特定状態が、目標状態に選択される。
【０４０９】
この場合、エージェントは、特定状態を目標状態とするアクションプランに従い、迷路上を、特定状態に対応する位置、すなわち、コイン位置に向かって移動し、そのコイン位置に置いてあるコインを収集する。
【０４１０】
なお、特定状態検出部３６では、未到着位置について、エージェントの現在地から未到着位置までの距離に反比例する値や、未到着位置に置いてあるコインの金額に比例する値、エージェントの現在地から未到着位置までの距離に反比例し、かつ、未到着位置に置いてあるコインの金額に比例する値等が、未到着位置に移動することの価値を表す評価値として求められ、評価値が最大の未到着位置に対応する拡張HMMの状態が、特定状態として優先的に検出される。
【０４１１】
また、エージェントは、未到着位置であるコイン位置に到着した場合、そのコイン位置を、未到着位置から除外する。
【０４１２】
コインの収集の時間として、あらかじめ設定された時間が経過すると、ステップＳ９３のコイン収集制御は終了し、コイン収集ゲームが終了する。
【０４１３】
ここで、上述の場合には、コインの収集において、エージェントが、コイン位置に対応する状態（特定状態）を目標状態とするアクションプランに従って移動し、目標状態に対応するコイン位置においてあるコインを収集することとしたが、エージェントにおいては、アクションプランに従って移動したときに収集することができるコインの金額の総和を最大にする最短の経路（拡張HMMの状態の系列）を、アクションプランとして求め、そのアクションプランに従って移動することにより、コインを収集することができる。
【０４１４】
また、上述の場合には、事前準備において、エージェントが、オープン端を、目標状態に選択し、その目標状態であるオープン端に向かって移動することで、迷路の構造、及び、コイン位置を獲得することとしたが、事前準備では、その他、例えば、エージェントにおいて、信頼度の低い拡張HMMの状態（その状態に対応する位置付近の迷路の構造を十分に獲得することができていない状態）に対応する位置に向かって移動することで、迷路の構造、及び、コイン位置を獲得することができる。
【０４１５】
エージェントが信頼度の低い（拡張HMMの）状態に向かう移動は、アクション決定部２４において、例えば、拡張HMMにおいて獲得していない迷路の構造の情報（観測値）を増加させるストラテジ(strategy)（以下、未獲得情報増加ストラテジともいう）に従ってアクションを決定することにより行うことができる。
【０４１６】
アクション決定部２４において、未獲得情報増加ストラテジに従ったアクションの決定は、例えば、以下のようにして行うことができる。
【０４１７】
すなわち、ある時刻tにおいて、エージェントがアクションUmを行った場合に、観測値Oが観測される確率Pm(O)は、式（１７）で表すことができる。
【０４１８】
【数１７】
2013058059.tif 000019
・・・（１７）
【０４１９】
式（１７）において、ρiは、時刻tに、状態Siにいる状態確率を表す。
【０４２０】
いま、発生確率が、確率Pm(O)で表される情報の量を、I(Pm(O))と表すこととすると、何らかの情報を増加させるストラテジに従って、アクションを決定する場合の、そのアクションUm'のサフィックスm'は、式（１８）で表される。
【０４２１】
【数１８】
2013058059.tif 000020
・・・（１８）
【０４２２】
ここで、式（１８）のargmax{I(Pm(O))}は、アクションUmのサフィックスmのうちの、かっこ内の情報の量I(Pm(O))を最大にするサフィックスm'を表す。
【０４２３】
いま、情報として、拡張HMMにおいて獲得していない情報（以下、未知状態情報ともいう）を採用することとすると、式（１８）に従って、アクションUm'を決定することは、拡張HMMにおいて獲得していない迷路の構造の情報を増加させる未獲得情報増加ストラテジに従って、アクションを決定することになる。
【０４２４】
ここで、発生確率が、確率Pm(O)で表される情報のエントロピーを、Ho(Pm)と表すこととすると、式（１８）は、等価的に、以下の式で表すことができる。
【０４２５】
すなわち、エントロピーHo(Pm)は、式（１９）で表すことができる。
【０４２６】
【数１９】
2013058059.tif 000021
・・・（１９）
【０４２７】
式（１９）のエントロピーHo(Pm)が、大きい場合には、観測値Oが観測される確率Pm(O)が、各観測値で均等になるので、どのような観測値が観測されるかが分からない、ひいては、エージェントが、どこにいるか分からないというような曖昧性が増加し、エージェントが知らない、いわば未知の世界の情報を獲得する可能性が高くなる。
【０４２８】
したがって、エントロピーHo(Pm)を大きくすることで、未知状態情報は増加するから、未獲得情報増加ストラテジに従って、アクションを決定する場合の式（１８）は、等価的に、エントロピーHo(Pm)を最大化する式（２０）で表すことができる。
【０４２９】
【数２０】
2013058059.tif 000022
・・・（２０）
【０４３０】
ここで、式（２０）のargmax{ Ho(Pm)}は、アクションUmのサフィックスmのうちの、かっこ内のエントロピーHo(Pm)を最大にするサフィックスm'を表す。
【０４３１】
エージェントが、式（２０）に従って決定されるアクションUm'を行うことによっても、オープン端を目標状態としてアクションを行う場合と同様に、迷路の構造、及び、コイン位置を効率的に獲得することができる。
【０４３２】
ここで、特許文献１には、相手の移動を考慮して、相手が移動する場所が少なくなるように弾を撃つ、アルゴリズムが固定的な対戦型シューティングゲームが記載されている。なお、特許文献１では、人工知能技術が探索問題として使われているだけで、学習や、育成を行ったキャラクタを使った対戦については、記載されていない。
【０４３３】
特許文献２には、ユーザがコマンドを入力して対話や指示をして、ペットを育てるゲームが記載されている。特許文献２に記載のゲームでは、ユーザの話し方の特徴や言葉から得られる特徴でペットの性格やアクションが変化し、これにより、ユーザがゲームに飽きることを抑制する。なお、特許文献２のゲームでは、自律で環境を探索することはなく、常に人間の関与が必要とされる。また、特許文献２には、対話以外のアクションを指示して育成を行うことや、キャラクタどうしの対戦については、記載されていない。
【０４３４】
特許文献３には、キャラクタが板の上に乗っている状況で、その板の角度をユーザが変えたときに、キャラクタが各種の振る舞いを行うゲームが記載されている。なお、特許文献３には、人工知能という言葉が記載されているが、その言葉は、板の傾きが少ないときにキャラクタが板の上で行う知的な振る舞いを意味しており、また、学習については、記載されていない。
【０４３５】
特許文献４には、対戦型のゲーム等において、味方のキャラクタと、敵のキャラクタや各種のオブジェクトとの位置関係を把握しやすくする工夫に関する技術が記載されている。なお、特許文献４には、人工知能という言葉が記載されているが、その言葉は、敵のキャラクタの動きや戦略を決める、各種の条件で複雑な判断を行うモジュールを意味しており、学習や育成については、記載されていない。
【０４３６】
特許文献５には、RPG(Role-Playing Game)において、キャラクタの性格の変更や、キャラクタの追加によって、ゲームを面白くする技術が記載されている。なお、特許文献５には、人工知能という言葉が記載されているが、その言葉は、キャラクタの動作を決めるモジュールを意味している。特許文献５には、そのモジュールを交換することや流通させることが記載されているが、人工知能で学習することや、キャラクタどうしの対戦については、記載されていない。
【０４３７】
［本技術を適用したコンピュータの説明］
【０４３８】
次に、上述した一連の処理は、ハードウェアにより行うこともできるし、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。
【０４３９】
そこで、図２０は、上述した一連の処理を実行するプログラムがインストールされるコンピュータの一実施の形態の構成例を示している。
【０４４０】
プログラムは、コンピュータに内蔵されている記録媒体としてのハードディスク１０５やROM１０３に予め記録しておくことができる。
【０４４１】
あるいはまた、プログラムは、リムーバブル記録媒体１１１に格納（記録）しておくことができる。このようなリムーバブル記録媒体１１１は、いわゆるパッケージソフトウエアとして提供することができる。ここで、リムーバブル記録媒体１１１としては、例えば、フレキシブルディスク、CD-ROM(Compact Disc Read Only Memory)，MO(Magneto Optical)ディスク，DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリ等がある。
【０４４２】
なお、プログラムは、上述したようなリムーバブル記録媒体１１１からコンピュータにインストールする他、通信網や放送網を介して、コンピュータにダウンロードし、内蔵するハードディスク１０５にインストールすることができる。すなわち、プログラムは、例えば、ダウンロードサイトから、ディジタル衛星放送用の人工衛星を介して、コンピュータに無線で転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送することができる。
【０４４３】
コンピュータは、CPU(Central Processing Unit)１０２を内蔵しており、CPU１０２には、バス１０１を介して、入出力インタフェース１１０が接続されている。
【０４４４】
CPU１０２は、入出力インタフェース１１０を介して、ユーザによって、入力部１０７が操作等されることにより指令が入力されると、それに従って、ROM(Read Only Memory)１０３に格納されているプログラムを実行する。あるいは、CPU１０２は、ハードディスク１０５に格納されたプログラムを、RAM(Random Access Memory)１０４にロードして実行する。
【０４４５】
これにより、CPU１０２は、上述したフローチャートにしたがった処理、あるいは上述したブロック図の構成により行われる処理を行う。そして、CPU１０２は、その処理結果を、必要に応じて、例えば、入出力インタフェース１１０を介して、出力部１０６から出力、あるいは、通信部１０８から送信、さらには、ハードディスク１０５に記録等させる。
【０４４６】
なお、入力部１０７は、キーボードや、マウス、マイク等で構成される。また、出力部１０６は、LCD(Liquid Crystal Display)やスピーカ等で構成される。
【０４４７】
ここで、本明細書において、コンピュータがプログラムに従って行う処理は、必ずしもフローチャートとして記載された順序に沿って時系列に行われる必要はない。すなわち、コンピュータがプログラムに従って行う処理は、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含む。
【０４４８】
また、プログラムは、１のコンピュータ（プロセッサ）により処理されるものであっても良いし、複数のコンピュータによって分散処理されるものであっても良い。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであっても良い。
【０４４９】
なお、本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【０４５０】
例えば、本技術は、１つの機能をネットワークを介して複数の装置で分担、共同して処理するクラウドコンピューティングの構成をとることができる。
【０４５１】
また、上述のフローチャートで説明した各ステップは、１つの装置で実行する他、複数の装置で分担して実行することができる。
【０４５２】
さらに、１つのステップに複数の処理が含まれる場合には、その１つのステップに含まれる複数の処理は、１つの装置で実行する他、複数の装置で分担して実行することができる。
【０４５３】
なお、本技術は、以下のような構成をとることができる。
【０４５４】
［１］
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
を備え、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定する
情報処理装置。
［２］
前記モデルは、
前記エージェントが行うアクションによって、状態が状態遷移する、前記アクションごとの状態遷移確率と、
前記状態から、前記観測値が観測される観測確率と
で規定され、
前記学習部は、前記モデルの学習を、前記エージェントが行うアクションと、前記エージェントがアクションを行ったときに前記エージェントにおいて観測される観測値とを用いて行う
［１］に記載の情報処理装置。
［３］
前記モデルは、HMM(Hidden Marcov Model)の状態遷移確率を、前記エージェントが行うアクションごとの状態遷移確率に拡張した拡張HMMであり、
前記学習部は、Baum-Welchの再推定法に従い、各アクションについての前記状態遷移確率と、前記観測確率とを推定する、前記拡張HMMの学習を行う
［２］に記載の情報処理装置。
［４］
前記拡張HMMに基づき、前記エージェントが行ったアクションと、そのアクションが行われたときに前記エージェントにおいて観測された観測値とを用いて、前記拡張HMMにおいて、現在いる状態である現在状態を認識する状態認識部と、
前記拡張HMMの状態の１つを、目標とする目標状態に決定する目標決定部と
をさらに備え、
前記アクション決定部は、前記拡張HMMに基づき、前記現在状態から前記目標状態までの状態遷移の尤度を最も高くするアクションの系列であるアクションプランを算出し、そのアクションプランに従い、前記エージェントが次に行うべきアクションを決定する
［３］に記載の情報処理装置。
［５］
前記目標決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記目標状態を決定し、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って決定された前記目標状態までのアクションプランを算出し、そのアクションプランに従い、前記エージェントが次に行うべきアクションを決定する
［４］に記載の情報処理装置。
［６］
所定の観測値が観測される状態を遷移元として行うことが可能な状態遷移の中で、行われたことがない状態遷移がある、前記所定の観測値と同一の観測値が観測される他の状態であるオープン端を検出するオープン端検出部をさらに備え、
前記目標決定部は、前記オープン端を、前記目標状態に決定する
［４］又は［５］に記載の情報処理装置。
［７］
前記オープン端検出部は、
前記状態遷移確率と、前記観測確率とを用いて、各観測値が観測されるときに、前記エージェントが各アクションを行う確率であるアクション確率を求め、
前記アクション確率と、前記観測確率との乗算により、各観測値が観測される各状態において、前記エージェントが各アクションを行う確率である、観測確率に基づくアクション確率を算出し、
各状態について、その状態を遷移元とする状態遷移の前記状態遷移確率を、アクションごとに加算することにより、各状態において、前記エージェントが各アクションを行う確率である、状態遷移確率に基づくアクション確率を算出し、
前記観測確率に基づくアクション確率と、前記状態遷移確率に基づくアクション確率との差分が所定の閾値以上となる状態を、前記オープン端として検出する
［６］に記載の情報処理装置。
［８］
前記エージェントが、前記オープン端を前記目標状態とするアクションプラン、又は、前記指示情報に従って決定される前記目標状態までのアクションプランに従って、景品が置かれた迷路を移動するアクションを行うことにより観測される観測値と、前記エージェントが行うアクションとを用いて、前記拡張HMMにおいて、前記迷路の構造を獲得する学習を行う事前準備処理と、
前記エージェントが、前記迷路において景品が置かれた場所に対応する状態を目標状態とするアクションプランに従って、前記迷路を移動するアクションを行うことにより、前記景品を収集する収集処理と
を制御する［６］又は［７］に記載の情報処理装置。
［９］
前記アクション決定部は、前記拡張HMMにおいて獲得していない未知の情報を増加させるストラテジに従って、アクションを決定する
［３］に記載の情報処理装置。
［１０］
前記アクション決定部は、前記エージェントがアクションを行ったときに各観測値が観測される確率によって発生確率が表される情報のエントロピーを最大にするアクションを、前記エージェントが次に行うべきアクションに決定する
［９］に記載の情報処理装置。
［１１］
前記エージェントが、前記エントロピーを最大にするアクション、又は、前記指示情報に従って決定されるアクションを行って、景品が置かれた迷路を移動することにより観測される観測値と、前記エージェントが行うアクションとを用いて、前記拡張HMMにおいて、前記迷路の構造を獲得する学習を行う事前準備処理と、
前記エージェントが、前記迷路において景品が置かれた場所に対応する状態を目標状態とするアクションプランに従って、前記迷路を移動するアクションを行うことにより、前記景品を収集する収集処理と
を制御する［１０］に記載の情報処理装置。
［１２］
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
を備える情報処理装置の前記アクション決定部が、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定するステップを含む
情報処理方法。
［１３］
アクション可能なエージェントがアクションを行ったときに前記エージェントにおいて観測される観測値を用いて、前記エージェントがアクションを行う環境のモデルの学習を行う学習部と、
前記モデルに基づいて、前記エージェントが行うアクションを決定するアクション決定部と、
ユーザからの指示に応じて、前記ユーザからの指示を表す指示情報を出力するユーザ指示出力部と
して、コンピュータを機能させるためのプログラムであり、
前記アクション決定部は、前記ユーザから指示があった場合、前記指示情報に従って、前記エージェントが行うアクションを決定する
プログラム。
【符号の説明】
【０４５５】
１０  ユーザ指示出力部，  １１  反射アクション決定部，  １２  アクチュエータ，  １３  センサ，  １４  履歴記憶部，  １５  アクション制御部，  １６  目標決定部，  ２１  学習部，  ２２  モデル記憶部，  ２３  状態認識部，  ２４  アクション決定部，  ３１  目標選択部，  ３３  外部目標設定部，  ３４  内部目標生成部，  ３５  ランダム目標生成部，  ３６  特定状態検出部，  ３７  オープン端検出部，  ５１  操作部，  ５２  ゲーム制御部，  ５３  表示制御部，  ６１  ゲーム環境制御部，  ６２  エージェント制御部，  １０１  バス，  １０２  CPU，  １０３  ROM，  １０４  RAM，  １０５  ハードディスク，  １０６  出力部，  １０７  入力部，  １０８  通信部，  １０９  ドライブ，  １１０  入出力インタフェース，  １１１  リムーバブル記録媒体
【図１】
2013058059.tif 000023
【図２】
2013058059.tif 000024
【図３】
2013058059.tif 000025
【図４】
2013058059.tif 000026
【図５】
2013058059.tif 000027
【図６】
2013058059.tif 000028
【図７】
2013058059.tif 000029
【図８】
2013058059.tif 000030
【図９】
2013058059.tif 000031
【図１０】
2013058059.tif 000032
【図１１】
2013058059.tif 000033
【図１２】
2013058059.tif 000034
【図１３】
2013058059.tif 000035
【図１４】
2013058059.tif 000036
【図１５】
2013058059.tif 000037
【図１６】
2013058059.tif 000038
【図１７】
2013058059.tif 000039
【図１８】
2013058059.tif 000040
【図１９】
2013058059.tif 000041
【図２０】
2013058059.tif 000042