(57)【要約】【課題】変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できるようにする。【解決手段】変数Ｎの値を１にセットし、ステップＳ２０２において、長さＮの時系列情報が取得される。ステップＳ２０３において、認識器は、時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力し、ステップＳ２０４において、実際にあり得るノード列であるか否かを判定する。実際にあり得るノード列ではないと判定された場合、未知ノードであると認識される。一方、実際にあり得るノード列であると判定された場合、エントロピーが計算され、閾値以上であると判定された場合、変数Ｎの値がインクリメントされ、時系列情報が過去方向に延長される。閾値以上ではないと判定された場合、既知ノードであると認識される。【選択図】図３３
2011018245.tif 000002
【特許請求の範囲】
【請求項１】
環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、
時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、
前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、
前記認識手段は、可変長の前記時系列情報を読み出して認識する
認識装置。
【請求項２】
前記認識手段は、
前記時系列情報に基づいて、前記時系列情報の長さに対応するノード列を認識し、
前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるまで、
前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長する
請求項１に記載の認識装置。
【請求項３】
前記認識手段は、
前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、
前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在しないと判定された場合、前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識して認識結果として出力し、
前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満と判定された場合、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードであると認識して認識結果として出力する
請求項２に記載の認識装置。
【請求項４】
前記認識結果を、認識された時刻と対応付けて記憶する認識結果記憶手段をさらに備える
請求項３に記載の認識装置。
【請求項５】
前記認識手段は、
前記認識結果記憶手段に記憶されている認識結果が、時間の経過に伴って既知ノードから未知ノードに変化した時刻を特定し、
前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長することにより、前記特定された時刻より時間的に前の時系列情報が読み出される場合、
認識結果の出力を保留する
請求項４に記載の認識装置。
【請求項６】
前記認識手段は、
長さＮの前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値と、長さＮ＋１の前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値との差分を算出し、
前記算出された差分が第３の閾値未満となるまで、前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長する
請求項１に記載の認識装置。
【請求項７】
前記認識手段は、
前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、
前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値未満の確率で存在すると判定された場合、
前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識する
請求項６に記載の認識装置。
【請求項８】
前記認識手段は、
前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定された場合、
前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるとき、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードである認識し、
前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値以上となるとき、認識結果の出力を保留する
請求項７に記載の認識装置。
【請求項９】
前記環境に対して自分が実行する行動を行動シンボルとし特定し、時間の経過に伴って得られる前記行動シンボルを、前記行動が実行された時刻と対応付けて記憶する行動シンボル記憶手段をさらに備え、
前記観測シンボル記憶手段に記憶された情報と時間的に同じ長さの情報が前記行動シンボル記憶手段から読み出され、前記時系列情報とされる
請求項１に記載の認識装置。
【請求項１０】
時間の経過に伴って観測される環境から得られるセンサ信号に基づく前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段に記憶された情報を可変長の時系列情報として読み出し、
前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する
認識方法。
【請求項１１】
コンピュータを、
環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、
時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、
前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、
前記認識手段は、可変長の前記時系列情報を読み出して認識する認識装置として機能させる
プログラム。
【請求項１２】
請求項１１に記載のプログラムが記録されている記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認識装置および方法、プログラム、並びに記録媒体に関し、特に、変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できるようにする認識装置および方法、プログラム、並びに記録媒体に関する。
【背景技術】
【０００２】
対象となるシステムから観測されるセンサ信号を時系列データとして扱い、状態および状態遷移を合わせ持つ確率モデルとして学習する方法としてＨＭＭ（隠れマルコフモデル）の利用が提案されている。ＨＭＭは、音声認識に広く利用される技術の一つである。ＨＭＭは、状態遷移確率と、各状態における出力確率密度関数で定義される状態遷移モデルであり、そのパラメータは、尤度を最大化するように推定される。パラメータの推定方法としては、Baum-Welch algorithmが広く利用されている。
【０００３】
ＨＭＭでは、各状態から状態遷移確率を介して別の状態へ遷移することができるモデルとなっており、状態が遷移する過程としてモデル化が行われる。ただし、ＨＭＭでは、通常、観測されるセンサ信号がどの状態に対応するのかについては、確率的にしか決定されない。
【０００４】
そこで、観測されるセンサ信号に基づいて、最も尤度が高くなるような状態遷移過程を決定する方法として、Viterbi Algorithmが広く利用されている。これにより、各時刻のセンサ信号に応じた状態を一意に確定することが可能となる。また、システムから観測されるセンサ信号が異なる状況で同じになったとしても、それぞれの時刻の前後におけるセンサ信号の時間変化の過程の違いに応じて、異なる状態遷移過程として扱うことが可能となる。perceptual aliasingの問題が完全に解決できるわけではないが、同じセンサ信号に対して異なる状態を割り当てることが可能であり、ＳＯＭなどに比べると、システムの状態をより詳細にモデル化することが可能である（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Lawrence R. Rabiner (February 1989)."A tutorial on Hidden Markov Models and selected applications in speech recognition".Proceedings of the IEEE 77 (2): 257-286.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、ＨＭＭの学習において、状態の数および状態遷移の数が多くなると、正しくパラメータを推定するのが困難となる。特に、Baum-Welch algorithmは、必ずしも最適なパラメータを決定できることを保証する方法ではないため、パラメータの数が多くなると適切なパラメータを推定するのが極めて困難となる。また、学習すべき対象となるシステムが未知の場合、状態遷移モデルの構造やパラメータの初期値を適切に設定することは難しく、これもパラメータの推定を困難にする原因となる。
【０００７】
音声認識においてＨＭＭが有効に利用されているのは、扱う対象が音声信号に限定されており、音声に関する数多くの知見が利用可能であることが要因となっている。さらに、音声認識においてＨＭＭの構造に関しては left-to-right型の構造が有効であることなどが長年に渡る膨大な研究成果の結果として得られていることなどが大きな要因である。従って、未知のシステムを対象とし、ＨＭＭの構造や初期値をあらかじめ決定するための情報が与えられない場合に、大規模なＨＭＭを実用的なモデルとして機能させることは非常に難しい問題であると言える。
【０００８】
さて、ＨＭＭが対象とする問題は上記の通り、センサ信号を構造化するというものであり、アクション信号に関する考慮はない。ＨＭＭを拡張し、エージェントがアクション信号を用いて環境に対し働きかけ、将来のセンサ信号に影響を与えることができる、という枠組みに置き換えたものは部分観測マルコフ決定過程(Partially observable Markov decision process， 以下、ＰＯＭＤＰ)と呼ばれる。
【０００９】
この問題のモデル学習は非常に困難な課題であり、これまで主に研究されてきたものは、事前知識によってスケルトンが与えられたモデル内の比較的少数のパラメータ推定のみであったり、あるいは強化学習的な枠組みで学習を駆動するようなものであった。さらに、学習の速度や収束性・安定性に課題のあるものも多く、実用性は必ずしも高くないと言える。
【００１０】
また、ＨＭＭの学習の方式として、バッチ学習方式と追加学習方式が存在する。ここで、バッチ学習方式は、例えば、１万ステップの遷移と観測のデータが得られる場合、１万ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存するものである。これに対して、追加学習方式は、例えば、最初に、１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存する。そして、その後の１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルの各値を変更して保存し、・・・というように、繰り返し学習を行って、内部モデルデータを更新（アップデート）していくものである。
【００１１】
従来のＨＭＭの学習では、追加学習方式の学習の際に問題が発生する。ＨＭＭの学習では、事前に全てのデータを予め準備しておき、バッチ学習方式での学習を行なうという方法がよく採られているが、このような学習では環境に適応して経験から学ぶことが原理的に不可能である。言い換えれば、多様な実世界の中でより良い性能を発揮するためには、実環境での動作結果をフィードバックして追加学習を行なうという機能が必須である。ところが、追加学習を行なう際に「学習済みの記憶構造」と「新しい経験」とをどのように調停するのかという問題は未解決である。一方では「新しい経験」を速やかに反映させてすばやい適応を実現したいが、他方、これまでに確立した記憶構造が破壊される危険性もある。
【００１２】
また、従来、追加学習を行うために、過去の学習データを分離して保持するか、または、過去の学習データを現在の記憶からリハースする等して、新たに得られたデータとを組み合わせて学習することが行われていた。しかしながら、そのようにしても、分離された過去の学習データに、「新しい体験」が反映されなかったり、リハースされる過去の学習データが、「新しい体験」の影響を受けて生成されてしまうなどの問題があった。このように、大規模なＨＭＭの学習において、追加学習を行って実用的なモデルとして機能させることは困難であった。
【００１３】
さらに、例えば、学習すべき環境が変化した場合、観測シンボルの種類、ノード数が増えることになり、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更する必要に迫られこともある。このような場合、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する必要がある。
【００１４】
エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合、そもそもエージェント自身が、新たに環境が拡張されたのか否かを認識する必要がある。つまり、エージェントが、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのか認識できるようにしなければならない。
【００１５】
本発明はこのような状況に鑑みてなされたものであり、変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できるようにするものである。
【課題を解決するための手段】
【００１６】
本発明の一側面は、環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、前記認識手段は、可変長の前記時系列情報を読み出して認識する認識装置である。
【００１７】
前記認識手段は、前記時系列情報に基づいて、前記時系列情報の長さに対応するノード列を認識し、前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるまで、前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長するようにすることができる。
【００１８】
前記認識手段は、前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在しないと判定された場合、前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識して認識結果として出力し、前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満と判定された場合、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードであると認識して認識結果として出力するようにすることができる。
【００１９】
前記認識結果を、認識された時刻と対応付けて記憶する認識結果記憶手段をさらに備えるようにすることができる。
【００２０】
前記認識手段は、前記認識結果記憶手段に記憶されている認識結果が、時間の経過に伴って既知ノードから未知ノードに変化した時刻を特定し、前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長することにより、前記特定された時刻より時間的に前の時系列情報が読み出される場合、認識結果の出力を保留するようにすることができる。
【００２１】
前記認識手段は、長さＮの前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値と、長さＮ＋１の前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値との差分を算出し、前記算出された差分が第３の閾値未満となるまで、前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長するようにすることができる。
【００２２】
前記認識手段は、前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値未満の確率で存在すると判定された場合、前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識するようにすることができる。
【００２３】
前記認識手段は、前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定された場合、前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるとき、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードである認識し、前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値以上となるとき、認識結果の出力を保留するようにすることができる。
【００２４】
前記環境に対して自分が実行する行動を行動シンボルとし特定し、時間の経過に伴って得られる前記行動シンボルを、前記行動が実行された時刻と対応付けて記憶する行動シンボル記憶手段をさらに備え、前記観測シンボル記憶手段に記憶された情報と時間的に同じ長さの情報が前記行動シンボル記憶手段から読み出され、前記時系列情報とされるようにすることができる。
【００２５】
本発明の一側面は、時間の経過に伴って観測される環境から得られるセンサ信号に基づく前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段に記憶された情報を可変長の時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識方法である。
【００２６】
本発明の一側面は、コンピュータを、環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、前記認識手段は、可変長の前記時系列情報を読み出して認識する認識装置として機能させるプログラムである。
【００２７】
本発明の一側面においては、環境から得られるセンサ信号に基づいて観測シンボルが観測され、時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けられて記憶され、記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードが認識され、可変長の前記時系列情報が読み出されて認識される。
【発明の効果】
【００２８】
本発明によれば、変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できる。
【図面の簡単な説明】
【００２９】
【図１】迷路の例を示す図である。
【図２】図１の迷路を構成するパーツの例を示す図である。
【図３】迷路の構造の変化を説明する図である。
【図４】迷路の構造の変化を説明する図である。
【図５】迷路の構造の変化を説明する図である。
【図６】ロボットの移動方向を説明する図である。
【図７】通常のＨＭＭを説明する図である。
【図８】アクション拡張型ＨＭＭを説明する図である。
【図９】本発明の一実施の形態に係る自律行動学習装置の構成例を示すブロック図である。
【図１０】スプリットアルゴリズムの適用を説明する図である。
【図１１】スプリットアルゴリズムの適用を説明する図である。
【図１２】スプリットアルゴリズム適用処理の例を説明するフローチャートである。
【図１３】フォワードマージアルゴリズムの適用を説明する図である。
【図１４】フォワードマージアルゴリズムの適用を説明する図である。
【図１５】フォワードマージアルゴリズム適用処理の例を説明するフローチャートである。
【図１６】バックワードマージアルゴリズムの適用を説明する図である。
【図１７】バックワードマージアルゴリズムの適用を説明する図である。
【図１８】バックワードマージアルゴリズムの適用処理の例を説明するフローチャートである。
【図１９】アクション拡張型ＨＭＭにおける状態遷移確率テーブルと観測確率テーブルの尤度を比較する表である。
【図２０】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２１】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２２】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２３】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２４】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２５】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２６】一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【図２７】アクション拡張型ＨＭＭ学習処理の例を説明するフローチャートである。
【図２８】従来の方式により追加学習を行なう際の問題を説明する図である。
【図２９】本発明における追加学習方式について説明する図である。
【図３０】観測シンボルの種類が増えることによる影響を説明する図である。
【図３１】ノードの数が増えることによる影響を説明する図である。
【図３２】アクションの数が増えることによる影響を説明する図である。
【図３３】ノード認識処理の例を説明するフローチャートである。
【図３４】ノード認識処理の別の例を説明するフローチャートである。
【図３５】ノード認識処理のさらに別の例を説明するフローチャートである。
【図３６】ノード認識処理のさらに別の例を説明するフローチャートである。
【図３７】未知ノードが追加される場合の例を説明する図である。
【図３８】未知ノードが追加される場合の別の例を説明する図である。
【図３９】アンカリングする際にノードの追加または削除の要否のチェックが行なわれる場合の例について説明する図である。
【図４０】未知ノード追加処理の例を説明するフローチャートである。
【図４１】追加または削除要否チェック処理の例を説明するフローチャートである。
【図４２】未知ノードが追加される場合、状態遷移確率テーブルにおいて拡張される領域を説明する図である。
【図４３】追加される未知ノードの例を説明する図である。
【図４４】追加される未知ノードとアクションの例を示す図である。
【図４５】追加される未知ノード、候補ノードおよびアクションの例を示す図である。
【図４６】ノード追加時の状態遷移確率設定処理の例を説明するフローチャートである。
【図４７】ノード逆アクションペアリスト生成処理の例を説明するフローチャートである。
【図４８】逆アクション状態遷移確率設定処理の例を説明するフローチャートである。
【図４９】ノード順アクションペアリスト生成処理の例を説明するフローチャートである。
【図５０】順アクション状態遷移確率設定処理の例を説明するフローチャートである。
【図５１】アンカリング処理の例を説明するフローチャートである。
【図５２】パーソナルコンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００３０】
以下、図面を参照して、本発明の実施の形態について説明する。
【００３１】
最初に、アクション拡張型ＨＭＭについて説明する。
【００３２】
後述する本発明の自律行動学習装置は、例えば、迷路を自走して自分の位置を認識し、目的地へのルートを学習するロボットなどに適用される。
【００３３】
図１は、迷路の例を示す図である。同図に示されるように、この迷路は、図２に示されるような複数の種類のパーツを組み合わせることにより構成されている。図２に示されるように、パーツのそれぞれは、同一の大きさの矩形として構成されており、１５の異なる種類が用意されている。例えば、パーツ５は、横方向の通路を構成するためのものであり、パーツ１０は、縦方向の通路を構成するためのものである。また、パーツ７、パーツ１１、パーツ１３は、それぞれＴ字路を構成するためのものであり、パーツ１５は、十字路を構成するためのものである。
【００３４】
また、この迷路は、その構造を変化させることもできるようになされている。例えば、図３において、図中点線の円により示される部分の２つのパーツを変更することにより、迷路の構造は、図４に示されるように変化する。すなわち、図３において、通り抜けできなかったものが、図４においては通り抜けできるように、迷路の構造を変化させることができる。
【００３５】
さらに、図４において、図中点線の円により示される部分の２つのパーツを変更することにより、迷路の構造は、図５に示されるように変化する。すなわち、図４において、通り抜けできたものが、図５においては通り抜けできないように、迷路の構造を変化させることができる。
【００３６】
このような迷路をロボットが自走する。この例では、迷路は２次元であり、通路の方向も水平または垂直方向のみなので、ロボットも上下左右の４方向に移動できるように設定するものとする。
【００３７】
図６は、ロボットの移動方向を説明する図である。同図における垂直方向、水平方向は、図１に対応しており、図中上下左右のいずれかの方向に、図中中央に示されるロボットが移動することが分かる。
【００３８】
ここで、ロボットの所定の方向への移動をアクションと称することにする。例えば、図６の例では、図中の４つの矢印に対応する４通りのアクションが存在することになる。
【００３９】
また、ロボットには、例えば、物体を検知するセンサが設けられており、センサから出力される信号を解析することにより、迷路上においてロボットが位置するパーツの種類を特定することが可能となるようになされている。すなわち、ロボットは、迷路上の各位置において、図２を参照して上述した１５種類のパーツのいずれかに対応するセンサ信号を取得するのである。
【００４０】
本発明では、例えば、ロボットが自走した迷路上の各位置におけるセンサ信号に基づいて迷路の構造に対応する内部モデルデータを生成する。ここで、迷路を環境と称し、１５種類のパーツのいずれかに対応するセンサ信号を観測シンボルと称することにする。本発明では、ＨＭＭを利用して、迷路の構造を学習し、上述した内部モデルデータを生成する。
【００４１】
ＨＭＭの学習においては、環境から得られる観測に基づいて状態が認識される。上述したように、環境は、例えば迷路であり、観測は、例えば１５種類のパーツのいずれかに対応するセンサ信号から特定される観測シンボルに対応する。なお、ロボットは、適宜、エージェントと称することにする。
【００４２】
ＨＭＭの学習では、エージェントが、環境から得られる観測に基づいて自分がいる状態を認識する。ここでいう状態は、いわばエージェントが主観的に認識した状態であり、実際にエージェントが置かれた状態を外部から客観的に観察した場合、両者が異なることがある。例えば、２次元の迷路上においてロボットがいる位置を客観的に観察すれば、その位置は座標（ｘ１，ｙ１）であるのに対して、ロボット自身は、自分は座標（ｘ２，ｙ２）にいると認識する場合がある。このように、いわばエージェントが主観的に認識した状態がＨＭＭでは、隠れ状態、内部状態、state、ノードなどと表現される。
【００４３】
本実施例では、主に、迷路上の各位置、すなわち、迷路に配置された各パーツの位置のそれぞれを、ＨＭＭにおけるノード（状態、隠れ状態、内部状態、state）に対応付けて、それらのノードに観測シンボルを対応づけた例について説明する。
【００４４】
ところで、通常のＨＭＭは、センサ信号を構造化するというものであり、アクション信号に関する考慮はない。エージェントがアクション信号を用いて環境に対してアクションを実行し、今後観測される観測シンボルに影響を与えることができるようにするという状況における学習は、ＨＭＭでは想定されていない。このような問題の解決は、部分観測マルコフ決定過程(Partially observable Markov decision process， 以下、ＰＯＭＤＰ)と呼ばれる。
【００４５】
そこで、本発明では、ＨＭＭを拡張して上記の問題を解決する。すなわち、本発明では、ＨＭＭを、アクション信号を考慮したものとなるように拡張する。このように拡張したＨＭＭをアクション拡張型ＨＭＭと称することにする。
【００４６】
図７は、通常のＨＭＭを説明する図である。同図に示されるように、ＨＭＭは、ある１つのノードから他の１つのノードへ遷移（状態遷移）する確率を、起こりえる遷移の数だけ学習する。すなわち、ノード数×ノード数のテーブルの各行列位置に、状態遷移確率の値を設定し、状態遷移確率テーブルという２次元のテーブルを生成する。また、ＨＭＭは、ある１つのノードにおいて、それぞれの観測シンボルが観測される確率を学習する。すなわち、ノード数×観測シンボル数のテーブルの各行列位置に、観測確率の値を設定し、観測確率テーブルという２次元のテーブルを生成する。
【００４７】
例えば、図７の状態遷移確率テーブルにおいて、図中垂直方向に記述されたノードのそれぞれは、遷移元のノードを表し、図中水平方向に記述されたノードのそれぞれが遷移先のノードを表す。従って、例えば、状態遷移確率テーブルのｎ行ｍ列に記述された数値は、インデックスｎのノード（第ｎ番目のノード）からインデックスｍのノード（第ｍ番目のノード）へ遷移する確率を表している。そして、状態遷移確率テーブルの各行（例えば、ｎ行目）に記述された全ての数値を合計すると、１となるようになされている。
【００４８】
また、例えば、図７の観測確率テーブルのｎ行p列に記述された数値は、インデックスｎのノード（第ｎ番目のノード）において、インデックスpの観測シンボル（第ｐ番目の観測シンボル）が観測される確率を表している。そして、観測確率テーブルの各行（例えば、ｎ行目）に記述された全ての数値を合計すると、１となるようになされている。
【００４９】
図８は、アクション拡張型ＨＭＭを説明する図である。同図に示されるように、アクション拡張型ＨＭＭでは、状態遷移確率テーブルを、アクション毎に生成する。例えば、上方向への移動というアクションの結果、ある１つのノードから他の１つのノードへ遷移する確率を、上方向移動アクションの状態遷移確率テーブルとして生成する。また、下方向への移動というアクションの結果、ある１つのノードから他の１つのノードへ遷移する確率を、下方向移動アクションの状態遷移確率テーブルとして生成する。同様に、左方向移動アクションの状態遷移確率テーブルと、右方向移動アクションの状態遷移確率テーブルも生成される。
【００５０】
例えば、図８の状態遷移確率テーブルを、複数枚の２次元のテーブルとしてみると、図中垂直方向に記述されたノードのそれぞれは、それぞれのアクションにおける遷移元のノードを表し、図中水平方向に記述されたノードのそれぞれが遷移先のノードを表す。従って、例えば、ｋ枚目の状態遷移確率テーブルのｎ行ｍ列に記述された数値は、インデックスｋのアクション（第ｋ番目のアクション）を実行することにより、インデックスｎのノードからインデックスｍのノードへ遷移する確率を表している。そして、状態遷移確率テーブルの各行（例えば、ｋ枚目のテーブルのｎ行目）に記述された全ての数値を合計すると、１となるようになされている。
【００５１】
このように、アクション拡張型ＨＭＭでは、２次元の状態遷移確率テーブルがアクション毎に生成され、いわば３次元の状態遷移確率テーブルが生成されることになる。
【００５２】
なお、アクション拡張型ＨＭＭにおいても、通常のＨＭＭの場合と同様に、ノード数×観測シンボル数のテーブルの各行列位置に、観測確率の値を設定し、２次元の観測確率テーブルが生成される。
【００５３】
例えば、図８の観測確率テーブルのｎ行p列に記述された数値は、図７の場合と同様に、インデックスｎのノードにおいて、インデックスpの観測シンボルが観測される確率を表している。そして、観測確率テーブルの各行（例えば、ｎ行目）に記述された全ての数値を合計すると、１となるようになされている。
【００５４】
ここでは、センサ信号に基づいて１５通りの観測シンボルが得られる場合であって、離散観測信号を取得する場合の例について説明した。しかし、例えば、少しずつ変化するセンサ信号に基づいてほぼ無限の観測シンボルが得られるような、連続観測信号を取得する場合にもアクション拡張型ＨＭＭを用いることができる。
【００５５】
また、ここでは、エージェントが４通りのアクションのいずれかを実行する場合であって、離散アクション集合を実行する場合の例について説明した。しかし、例えば、エージェントが、少しずつ移動方向を変え、ほぼ無限のアクションの中から１つのアクションを実行するような、連続アクション集合を実行する場合にもアクション拡張型ＨＭＭを用いることができる。
【００５６】
ここまで、アクション拡張型ＨＭＭについて説明した。
【００５７】
図９は、本発明を適用した自律行動学習装置１０の構成例を示すブロック図である。同図の自律行動学習装置１０は、例えば、図１に示されるような迷路上を移動するロボットの制御装置などとして構成される。この例では、自律行動学習装置１０に、センサ部３１、行動出力部３２、観測バッファ３３、学習器３４、認識器３５、行動生成器３６、内部モデルデータ記憶部３７、認識結果バッファ３８、および行動出力バッファ３９が設けられている。
【００５８】
センサ部３１は、例えば、迷路などの環境において、上述した観測シンボルを観測するためのセンサ信号（または観測信号）を出力する。センサ部３１から出力された観測信号は、その観測信号が出力された時刻と対応付けられて観測バッファ３３に記憶されるようになされている。
【００５９】
例えば、時刻t，t+1，t+2，・・・Tの各時刻で取得した観測信号に対応する観測シンボルot， ot+1， ot+2， ・・・， oTが各時刻の観測シンボルとして観測バッファ３３に記憶されることになる。
【００６０】
行動出力部３２は、例えば、ロボットが実行すべきアクション（日本語で行動）を、ロボットに実行させるための制御信号を出力する機能ブロックである。行動出力部３２から出力された制御信号は、その制御信号に対応するアクションを特定する情報に変換され、その制御信号が出力された時刻と対応付けられて行動出力バッファ３９に記憶されるようになされている。
【００６１】
例えば、時刻t，t+1，t+2，・・・Tの各時刻で実行したアクションct， ct+1， ct+2， ・・・， cTが各時刻のアクションとして行動出力バッファ３９に記憶されることになる。
【００６２】
学習器３４は、観測バッファ３３および行動出力バッファ３９に記憶されている情報に基づいて、内部モデルデータを生成または更新し、内部モデルデータ記憶部３７に記憶させる。
【００６３】
内部モデルデータ記憶部３７に記憶されている内部モデルデータには、上述した、３次元の状態遷移確率テーブル、および２次元の観測確率テーブルが含まれる。さらに、内部モデルデータ記憶部３７に記憶されている内部モデルデータには、後述する、状態遷移確率の計算のための頻度変数および観測確率の計算のための頻度変数が含まれる。
【００６４】
認識器３５は、観測バッファ３３および行動出力バッファ３９に記憶されている情報、並びに内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいて、現在、ロボットが位置するノードを認識するようになされている。認識器３５から出力された認識結果は、その認識結果が出力された時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【００６５】
行動生成器３６は、内部モデルデータ記憶部３７に記憶されている内部モデルデータ、行動出力バッファ３９に記憶されている情報、および認識器３５が出力する認識結果に基づいて、ロボットが実行すべきアクションを決定する。そして、行動生成器３６は、決定されたアクションに対応する制御信号を出力するように、行動出力部３２を制御する。
【００６６】
このように、自律行動学習装置１０は、例えば、ロボットを迷路上で移動させて、自動的に迷路の構造などを学習させることができるようになされている。
【００６７】
次に、図９の学習器３４におけるアクション拡張型ＨＭＭの学習アルゴリズムについて説明する。
【００６８】
通常のＨＭＭではノードsiからsjへの状態遷移確率を状態遷移確率テーブルaijでモデル化するが、アクション拡張型ＨＭＭではアクションパラメータcを用いてaij(c)としてモデル化する。
【００６９】
学習アルゴリズムとしては、Baum-Welchアルゴリズムを用いる。forward確率、backward確率の計算ができれば、Baum-Welchアルゴリズムに基づくパラメータ推定(期待値最大化法)が可能となるので、以下ではそれらの確率の計算について説明する。
【００７０】
ここで、アクション集合C = {c1， c2， ・・・， cn}に属するアクションckによって、ノードsi からsj への遷移が起きる確率を、３次元の確率表現テーブルaij(k) ≡ aijkで表すこととする。なお、この例の場合、離散アクション集合を実行することになる。
【００７１】
まずforward確率の計算について説明する。
【００７２】
時刻1，2，・・・t-1の各時刻においてエージェントが取得したセンサ信号に対応する観測シンボルを、それぞれo1，o2，・・・，ot？1で表すことにする。また、時刻1，2，・・・t-1の各時刻においてエージェントが実行したアクションを、それぞれc1，c2，・・・，ct？1で表すことにする。この場合、時刻tにおいてエージェントが取得したセンサ信号に対応する観測シンボルがotであるとき、エージェントがノードsjにいるforward確率αt(j)は、式（１）の漸化式により表すことができる。
【００７３】
【数１】
2011018245.tif 000003
・・・（１）
ただし、bj(o)は、ノードsjの下で観測シンボルoが得られる観測確率である。
【００７４】
次に、backward確率の計算について説明する。
【００７５】
エージェントが時刻tにおいて状態iにいた場合、時刻t，t+1，t+2，・・・T-1の各時刻において、それぞれアクションct，ct+1，・・・，cT？1を実行し、各時刻で取得したセンサ信号に対応する観測シンボルが、それぞれot+1，ot+2，・・・，oTであるbackward確率βt(i)は、式（２）の漸化式により表すことができる。
【００７６】
【数２】
2011018245.tif 000004
・・・（２）
【００７７】
このように計算されるforward確率と、backward確率とを用いて、状態遷移確率の推定と、観測確率の推定を行なうことができる。
【００７８】
離散アクション集合を実行する場合の状態遷移確率の推定と観測確率の推定は、次のようにして行なわれる。
【００７９】
状態遷移確率aij(k)の推定は、Baum-WelchアルゴリズムのＭ−ステップで行なう。ここで、状態遷移確率aij(k)は、エージェントが状態iにいるとき、アクションｋを実行することにより状態ｊに遷移する確率を意味する。すなわち、式（３）を演算することにより、状態遷移確率の推定値a´ij(k)を得ることができる。
【００８０】
【数３】
2011018245.tif 000005
・・・（３）
【００８１】
観測確率bj(o)の推定も、やはりBaum-WelchアルゴリズムのＭ-ステップで行なう。ここで、観測確率bj(o)は、エージェントが状態ｊにいるとき、観測シンボルｏに対応するセンサ信号を取得する確立を意味する。すなわち、式（４）を演算することにより、観測確率の推定値b´j(o)を得ることができる。
【００８２】
【数４】
2011018245.tif 000006
・・・（４）
【００８３】
式（４）は、離散観測信号を取得する場合の例であるが、連続観測信号を取得する場合は、時刻tにおいて取得された観測信号otを、式（５）に示されるγt(j）よって重み付けた信号分布を用いて、観測確率密度関数bj(o)のパラメータを再推定すればよい。なお、γt(j）は、時刻tにおいてエージェントが状態jにいる場合の重み係数を表している。
【００８４】
【数５】
2011018245.tif 000007
・・・（５）
【００８５】
通常は、ガウス分布などの対数凹又は楕円型対称確率密度をモデルとして用い、観測確率密度関数bj(o)のパラメータの再推定を行うことができる。
【００８６】
ガウス分布などの対数凹又は楕円型対称確率密度のモデルのパラメータとしては、状態jにおける観測信号の平均ベクトルμ´jおよび共分散行列U´jを用いることができる。平均ベクトルμ´jおよび共分散行列U´jは、それぞれ、式（６）および式（７）により求めることができる。
【００８７】
【数６】
2011018245.tif 000008
・・・（６）
【００８８】
【数７】
2011018245.tif 000009
・・・（７）
【００８９】
次に連続アクション集合を実行する場合の例について説明する。
【００９０】
連続アクションの場合、離散アクションの場合と異なり、離散アクションckより連続アクションcの出力される確率ρk(c)の学習が必要となる。確率ρk(c)を学習することにより、連続アクションｃを、あたかも離散アクションckであるようにラベリングする（離散アクションに対応付ける）ことができるからである。
【００９１】
連続アクションの場合のforward確率の計算は次のようにして行なわれる。
【００９２】
時刻1，2，・・・t-1の各時刻においてエージェントが取得したセンサ信号に対応する観測シンボルを、それぞれo1，o2，・・・，ot？1で表すことにする。また、時刻1，2，・・・t-1の各時刻においてエージェントが実行した連続アクションから推定される離散アクションを、それぞれc1，c2，・・・，ct？1で表すことにする。この場合、時刻tにおいてエージェントが取得したセンサ信号に対応する観測シンボルがotであるとき、エージェントがノードsjにいるforward確率αt(j)は、式（８）の漸化式により表すことができる。
【００９３】
【数８】
2011018245.tif 000010
・・・（８）
ただし、ρk(c)は、離散アクションckより連続アクションcの出力される確率を表す。
なお、ρk(c)をどのようにして求めるかについては、後述する。
【００９４】
エージェントが時刻tにおいて状態iにいた場合、時刻t，t+1，t+2，・・・T-1の各時刻において、エージェントが実行した連続アクションから推定される離散アクションを、それぞれアクションct，ct+1，・・・，cT？1とし、各時刻で取得したセンサ信号に対応する観測シンボルが、それぞれot+1，ot+2，・・・，oTであるbackward確率βt(i)は、式（９）の漸化式により表すことができる。
【００９５】
【数９】
2011018245.tif 000011
・・・（９）
【００９６】
連続アクション集合を実行する場合の状態遷移確率の推定と観測確率の推定は、次のようにして行なわれる。
【００９７】
状態遷移確率aij(k)の推定は、離散アクションの場合と同様に、Baum-WelchアルゴリズムのＭ−ステップで行なう。ここで、状態遷移確率aij(k)は、エージェントが状態iにいるとき、アクションｋを実行することにより状態ｊに遷移する確率を意味する。すなわち、式（１０）を演算することにより、状態遷移確率の推定値a´ij(k)を得ることができる。
【００９８】
【数１０】
2011018245.tif 000012
・・・（１０）
【００９９】
観測確率bj(o)の推定は、離散アクションの場合と全く同一なので、ここでは説明を省略する。
【０１００】
次に、離散アクションckより連続アクションcの出力される確率ρk(c)をどのようにして求めるかについて説明する。
【０１０１】
確率ρk(c)もBaum-Welch アルゴリズムのＭ−ステップで行なうようにすることができる。すなわち、連続観測信号の場合における観測確率の推定と同様の方式で推定することができる。
【０１０２】
時刻tにおいて実行されるアクションctを、式（１１）に示されるξt(i，j，k)よって重み付けた信号分布を用いて、確率ρk(c)を推定すればよい。
【０１０３】
【数１１】
2011018245.tif 000013
・・・（１１）
【０１０４】
観測確率の場合と同様にガウス分布などをモデルとして用い、確率ρk(c)を推定することができる。
【０１０５】
この場合、連続アクションｃをラベリングして得られる離散アクションckより生成されるアクション信号の平均ベクトルνkおよび共分散行列Ｖ´kを、それぞれ式（１２）および式（１３）により演算する。このようにして演算された、アクション信号の平均ベクトルνkおよび共分散行列Ｖ´kを、ガウス分布などのモデルのパラメータとして用いるようにすればよい。
【０１０６】
【数１２】
2011018245.tif 000014
・・・（１２）
【０１０７】
【数１３】
2011018245.tif 000015
・・・（１３）
【０１０８】
このようにして、アクション拡張型ＨＭＭにおける３次元の状態遷移確率テーブルと、２次元の観測確率テーブルを学習により生成することができる。
【０１０９】
ここまで説明したアクション拡張型ＨＭＭの学習アルゴリズムにより、通常のＨＭＭと同様に、状態遷移確率と観測確率を得ることができる。
【０１１０】
しかし、状態の数（ノード数）をＮ、観測シンボル数をＭ、アクション数をＫとすると、３次元の状態遷移確率テーブルと、２次元の観測確率テーブルにおいて算出すべきパラメータ数は、Ｎ2Ｋ＋ＮＭとなる。このように、アクション拡張型ＨＭＭにおいては、Ｎ，Ｍ，Ｋの数が増大すると、学習処理の負荷も加速度的に増大することが明らかである。例えば、Ｎが２５０程度、Ｍが１５程度、Ｋが５程度の環境においては、３０万規模のパラメータを算出する必要がある。数少ないサンプルからこれほど多くのパラメータを適切に決定することは非常に困難である。
【０１１１】
しかしながら、例えば、モデルに制約を加えることでパラメータの自由度を減らし、学習を安定化させることが可能である。次に、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うために必要となる技術について説明する。
【０１１２】
本発明では、アクション拡張型ＨＭＭの学習において、一状態一観測制約およびアクション遷移制約を課すことにする。
【０１１３】
最初に、一状態一観測制約について説明する。一状態一観測制約は、例えば、あるノードで観測される観測シンボルは、原則として１つに限るという制約である。なお、一状態一観測制約の下でも、同じ観測シンボルを別々のノードで観測することは許容される。
【０１１４】
アクション拡張型ＨＭＭの学習において、一状態一観測制約を課すことにより事象の表現方式が限定され、結果として、状態遷移確率テーブルと観測確率テーブルの生成のために必要となるパラメータの自由度が減少する。
【０１１５】
一状態一観測制約を実現する方式の１つとして、例えば、離散観測型ＨＭＭの学習においてなされているように、目的関数に観測確率をスパースにするような制約項を加えるという方式がある。
【０１１６】
例えば、目的関数に観測確率をスパースにするような重みλを乗じた制約項ΣjＨ(bj)を加えるという方式が考えられる。ここで、Ｈ(bj)は、ノードsjで観測され得るすべて観測シンボルに対する観測確率ベクトルbjに対して定義されるエントロピーとされる。これ以外にも、観測確率ベクトルbjのＬ１ノルムとＬ２ノルムの差分Σj(||bj||1 ？ ||bj||2)などを、制約項とする方式も考えられる。
【０１１７】
あるいはまた、上述の目的関数に観測確率をスパースにするような重みλを乗じた制約項ΣjＨ(bj)を加えるという方式以外の方式で一状態一観測制約を実現することも可能である。このような方式の例としてスプリットアルゴリズムを適用する例が考えられる。
【０１１８】
図１０と図１１は、スプリットアルゴリズムを説明する図である。図１０と図１１では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。
【０１１９】
図１０は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１０の例は、ノードＳ１０、ノードＳ２０、ノードＳ３０が存在する場合の例を示している。この例の場合、エージェントは、ノードＳ１０で十字路のパーツ（図２のパーツ１５）を１００％の確率で観測し、ノードＳ１０において右方向に移動するアクションを実行するとエージェントは１００％の確率でノードＳ２０に移動（遷移）する。
【０１２０】
また、ノードＳ２０では、図２のパーツ７とパーツ１３が、それぞれ５０％の確率で観測される。ノードＳ２０において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、ノードＳ２０において左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。
【０１２１】
さらに、ノードＳ３０では、図２のパーツ５が１００％の確率で観測され、ノードＳ３０において左方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。
【０１２２】
なお、図１０（図１１も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１０に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにスプリットアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１１に示されるように変化する。
【０１２３】
図１１は、図１０に対応する状態遷移確率テーブルと観測確率テーブルの内容にスプリットアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。
【０１２４】
図１１の例では、ノードＳ１０、ノードＳ２１、ノードＳ２２、ノードＳ３０が存在する。すなわち、図１０のノードＳ２０が図１１においてノードＳ２１とノードＳ２２に分割（スプリット）されたのである。この例の場合、ノードＳ１０では図２のパーツ１５が１００％の確率で観測され、ノードＳ１０において右方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。
【０１２５】
また、ノードＳ２１では図２のパーツ７が１００％の確率で観測され、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。
【０１２６】
ノードＳ２２では図２のパーツ１３が１００％の確率で観測され、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。
【０１２７】
さらに、ノードＳ３０では、図２のパーツ５が１００％の確率で観測され、ノードＳ３０において左方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。
【０１２８】
このように、スプリットアルゴリズムを適用することにより、一状態一観測制約を実現することが可能である。
【０１２９】
すなわち、スプリットアルゴリズムの適用は、期待値最大化法で求められた局所最適解に対して一状態一観測制約を適用し、修正された解に対して再度期待値最大化法に基づく局所最適化を施す処理を繰り返すことで、最終的に一状態一観測制約を満たす局所最適解を求める処理になる。
【０１３０】
なお、図１０と図１１を参照して上述した例では、各ノードで観測される観測シンボルの観測確率が１００％とされるように分割されると説明したが、実際には、観測シンボルの観測確率が１００％とされることは稀である。一状態一観測制約は、厳密な意味で１つのノードで観測される観測シンボルが常に１つに限られるようにするものではないからである。すなわち、一状態一観測制約は、１つのノードで観測される観測シンボルが複数ある場合でも、そのうち１つの観測シンボルの観測確率が閾値以上となるようにするものである。
【０１３１】
図９の学習器３４により内部モデルデータに対してスプリットアルゴリズムが適用される場合の処理について、図１２のフローチャートを参照して説明する。
【０１３２】
ステップＳ１０１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている観測確率テーブルを参照し、観測確率bjの最大値が閾値th1以下のノードsjを1つ探す。
【０１３３】
ステップＳ１０２において、学習器３４は、ステップＳ１０１の処理の結果、最大値が閾値th1以下のノードsjが見つかったか否かを判定し、見つかったと判定された場合、処理は、ステップＳ１０３に進む。
【０１３４】
ステップＳ１０３において、学習器３４は、観測確率テーブルを参照し、ステップＳ１０２で見つかったと判定されたノードsjにおける各観測シンボルの観測確率をチェックする。そして、学習器３４は、ノードsjおいて、観測確率が閾値th2以上となる観測シンボルの数をカウントし、それらの観測シンボルをリストする。
【０１３５】
例えば、Ｋ個の観測確率が閾値th2以上となる観測シンボルが存在する場合、観測シンボルok(k = 1， ・・・，K)がリストされる。
【０１３６】
ステップＳ１０４において、学習器３４は、ノードsjをＫ個に分割する。
【０１３７】
このとき、ノードsjが分割された後の観測確率テーブルにおける観測確率および状態遷移確率テーブルにおける状態遷移確率は、次のようにして設定される。
【０１３８】
ノードsjが分割された結果得られるＫ個のノードのうちの第ｋ番目のノードを、sjkと表すこととし、ノードsjkで観測される各観測シンボルの観測確率のそれぞれを要素とするベクトルをbjkと表すことにする。
【０１３９】
ステップＳ１０４において、学習器３４は、ベクトルbjkを、観測シンボルokに対する観測確率だけが突出して大きく（１に極めて近く）、その他の観測シンボルに対する観測確率はきわめて微小な範囲の一様乱数となるように設定する。
【０１４０】
また、ノードsjが分割される前のノードsiからノードsjへの状態遷移確率をａijで表すこととし、ノードsjが分割された後のノードsiからノードsjkへの状態遷移確率をakijで表すことにする。
【０１４１】
ステップＳ１０４において、学習器３４は、状態遷移確率をakijが、分割前の状態遷移確率aijを分割前の各観測シンボルの観測確率の比で案分されたものとなるように設定する。
【０１４２】
さらに、ノードsjが分割される前のノードsjからノードsiへの状態遷移確率をａjiで表すこととし、ノードsjが分割された後のノードsjkからノードsiへの状態遷移確率をakjiで表すことにする。
【０１４３】
ステップＳ１０４において、Ｋ個の状態遷移確率akjiのそれぞれに、状態遷移確率ａjiを設定する。
【０１４４】
このようにして、スプリットアルゴリズムの適用の処理が実行される。
【０１４５】
次に、アクション遷移制約について説明する。アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約である。
【０１４６】
アクション遷移制約は、あるノードsiから、同一のアクションckによって遷移可能な遷移先のノードsj(j=1，・・・ ， J)、またはノードsiへ同一のアクションckによって遷移可能な遷移元のノードsj(j=1，・・・，J)では、それぞれ異なる観測シンボルoj(j=1，・・・，J)が観測されるべきであるという制約である。前者をforward制約、後者をbackward制約と称する。すなわち、アクション遷移制約の下では、同一のアクションckによって遷移可能な複数の遷移先（または遷移元）のノードにおいて、同一の観測シンボルが観測されることは許容されないのである。なお、アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションckによって遷移可能な遷移先のノードが複数存在することは許容される。
【０１４７】
アクション遷移制約を実現する方式の例としてフォワードマージアルゴリズムおよびバックワードマージアルゴリズムを適用する例が考えられる。
【０１４８】
図１３と図１４は、フォワードマージアルゴリズムを説明する図である。
【０１４９】
図１３と図１４では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。
【０１５０】
図１３は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１３の例は、ノードＳ１０、ノードＳ２１、ノードＳ２２、ノードＳ３１、ノードＳ３２が存在する場合の例を示している。この例の場合、ノードＳ１０において右方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。
【０１５１】
ノードＳ２１では、図２のパーツ５が１００％の確率で観測され、ノードＳ２２でも図２のパーツ５が１００％の確率で観測される。
【０１５２】
さらに、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３１に遷移し、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３２に遷移する。
【０１５３】
なお、図１３（図１４も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１３に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにフォワードマージアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１４に示されるように変化する。
【０１５４】
図１４は、図１３に対応する状態遷移確率テーブルと観測確率テーブルの内容にフォワードマージアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。
【０１５５】
図１４の例では、ノードＳ１０、ノードＳ２０、ノードＳ３１、ノードＳ３２が存在する。すなわち、図１３のノードＳ２１とノードＳ２２が図１４のノードＳ２０に併合（マージ）されたのである。この例の場合、ノードＳ２０では図２のパーツ５が１００％の確率で観測され、ノードＳ１０において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。
【０１５６】
また、ノードＳ２０において右方向に移動するアクションを実行すると５０％の確率でノードＳ３１に遷移し、５０％の確率でノードＳ３２に遷移する。
【０１５７】
このように、フォワードマージアルゴリズムを適用することにより、アクション遷移制約のうちのforward制約を実現することが可能である。
【０１５８】
つまり、アクション遷移制約の下では、同一のアクションckによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測されることは許容されないので、図１３のノードＳ２１とノードＳ２２が図１４のノードＳ２０にマージされたのである。なお、仮にノードＳ１０において右方向に移動するアクションを実行することにより遷移するノードＳ２３が存在した場合、ノードＳ２３でパーツ５以外のパーツが観測されるときは、ノード２３がマージの対象となることはない。アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションckによって遷移可能な遷移先のノードが複数存在することは許容されるからである。
【０１５９】
すなわち、１つのノードにおいて所定のアクションを実行した場合に遷移し得る遷移先ノードのそれぞれでの観測確率分布が類似するノードを発見し、発見されたノードが併合（マージ）されるのである。
【０１６０】
なお、図１３と図１４を参照して上述した例では、所定の観測シンボルが観測されるノードへの状態遷移確率が１００％とされるようにマージされると説明したが、実際には、状態遷移確率が１００％とされることは稀である。forward制約は、厳密な意味で同一のアクションckによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測されることは許容しないものではないからである。
【０１６１】
図９の学習器３４により内部モデルデータに対してフォワードマージアルゴリズムが適用される場合の処理について、図１５のフローチャートを参照して説明する。
【０１６２】
ステップＳ１２１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルを参照し、ある１つのアクションckの状態遷移確率テーブルをチェックする。
【０１６３】
ステップＳ１２２において、学習器３４は、ステップＳ１２１の処理でチェックした状態遷移確率テーブルの中で、ある１つの遷移元ノードsiを特定し、ノードsiから各遷移先ノードへの状態遷移確率を要素とするベクトルaij(k)をチェックする。そして、学習器３４は、状態遷移確率の値が閾値以上となった遷移先ノードsjをリストする。
【０１６４】
ステップＳ１２３において、学習器３４は、ステップＳ１２２の処理でリストされた遷移先ノードを観測シンボル毎に分類する。
【０１６５】
なお、上述したように、アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約だから、遷移先ノードで観測される観測シンボルは、ほぼ１つに特定することが可能である。
【０１６６】
ステップＳ１２４において、学習器３４は、ステップＳ１２３の処理で分類された同一の観測シンボルのノードをマージする。
【０１６７】
すなわち、ステップＳ１２３の処理でマージされた、観測シンボルmに対応するノード群を、sjm，l(l = 1，・・・，L)で表すものとし、Ｌ個のノードsjm，lを１つのノードsjmにマージするのである。
【０１６８】
このとき、Ｌ個のノードsjm，lが１つのノードsjmにマージされた後の状態遷移確率テーブルにおける状態遷移確率および観測確率テーブルにおける観測確率は、次のようにして設定される。
【０１６９】
ノードsiからノードsjmへの状態遷移確率aijmは、式（１４）により求められて設定される。
【０１７０】
【数１４】
2011018245.tif 000016
・・・（１４）
ここで、aijm，lは、マージされる前のノードsiから１個のノードsjm，lへの状態遷移確率を表すものとする。
【０１７１】
ノードsjmからノードsiへの状態遷移確率ajimは、ajim，lの単純平均、またはΣkakjm，lによる重み付き平均として求められて設定される。
【０１７２】
Ｌ個のノードsjm，lが１つのノードsjmにマージされた後のノードsjmにおける観測シンボルmの観測確率bjmは、bjm，lの単純平均、またはΣkakjm，lによる重み付き平均として求められて設定される。
【０１７３】
ステップＳ１２４では、このように、状態遷移確率aijm、状態遷移確率ajim、観測確率bjmが設定される。
【０１７４】
このようにして、フォワードマージアルゴリズムの適用の処理が実行される。
【０１７５】
図１６と図１７は、バックワードマージアルゴリズムを説明する図である。
【０１７６】
図１６と図１７では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。
【０１７７】
図１６は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１６の例は、ノードＳ１１、ノードＳ１２、ノードＳ２１、ノードＳ２２、ノードＳ３０が存在する場合の例を示している。この例の場合、ノードＳ１１において右方向に移動するアクションを実行すると１００％の確率でノードＳ２１に遷移する。ノードＳ１２において右方向に移動するアクションを実行すると１００％の確率でノードＳ２２に遷移する。
【０１７８】
また、ノードＳ２１では、図２のパーツ７が１００％の確率で観測される。ノードＳ２２では、図２のパーツ７が１００％の確率で観測される。
【０１７９】
さらに、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移する。
【０１８０】
なお、図１６（図１７も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１６に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにバックワードマージアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１７に示されるように変化する。
【０１８１】
図１７は、図１６に対応する状態遷移確率テーブルと観測確率テーブルの内容にバックワードマージアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。
【０１８２】
図１７の例では、ノードＳ１１、ノードＳ１２、ノードＳ２０、ノードＳ３０が存在する。すなわち、図１６のノードＳ２１とノードＳ２２が図１７のノードＳ２０に併合（マージ）されたのである。この例の場合、ノードＳ２０では図２のパーツ７が１００％の確率で観測される。
【０１８３】
また、ノードＳ１１において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移し、ノードＳ１２において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。
【０１８４】
さらに、ノードＳ２０において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移する。
【０１８５】
このように、バックワードマージアルゴリズムを適用することにより、アクション遷移制約のうちのbackward制約を実現することが可能である。
【０１８６】
つまり、アクション遷移制約の下では、同一のアクションckによって遷移可能な複数の遷移元のノードにおいて、同一の観測シンボルが観測されることは許容されないので、図１６のノードＳ２１とノードＳ２２が図１７のノードＳ２０にマージされたのである。なお、仮に右方向に移動するアクションを実行することによりノードＳ３０に遷移するノードＳ２３が存在した場合、ノードＳ２３でパーツ７以外のパーツが観測されるときは、ノード２３がマージの対象となることはない。アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションckによって遷移可能な遷移元のノードが複数存在することは許容されるからである。
【０１８７】
すなわち、1つのノードに対して、共通のアクションによって遷移してくる遷移元ノードのそれぞれでの観測確率分布が類似するノードを発見し、発見されたノードが併合されるのである。
【０１８８】
図９の学習器３４により内部モデルデータに対してバックワードマージアルゴリズムが適用される場合の処理について、図１８のフローチャートを参照して説明する。
【０１８９】
ステップＳ１４１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルを参照し、ある１つのアクションckの状態遷移確率テーブルをチェックする。
【０１９０】
ステップＳ１４２において、学習器３４は、ステップＳ１４１の処理でチェックした状態遷移確率テーブルの中で、ある１つの遷移先ノードsjを特定し、ノードsjへの各遷移元ノードからの状態遷移確率を要素とするベクトルaij(k)をチェックする。そして、学習器３４は、状態遷移確率の値が閾値以上となった遷移元ノードsiをリストする。
【０１９１】
ステップＳ１４３において、学習器３４は、ステップＳ１４２の処理でリストされた遷移元ノードを観測シンボル毎に分類する。
【０１９２】
なお、上述したように、アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約だから、遷移元ノードで観測される観測シンボルは、ほぼ１つに特定することが可能である。
【０１９３】
ステップＳ１４４において、学習器３４は、ステップＳ１４３の処理で分類された同一の観測シンボルのノードをマージする。
【０１９４】
すなわち、ステップＳ１４３の処理でマージされた、観測シンボルmに対応するノード群を、sim，l(l=1，・・・，L)で表すものとし、Ｌ個のノードsim，lを１つのノードsimにマージするのである。
【０１９５】
このとき、Ｌ個のノードsim，lが１つのノードsimにマージされた後の状態遷移確率テーブルにおける状態遷移確率および観測確率テーブルにおける観測確率は、次のようにして設定される。
【０１９６】
ノードsjへのノードsimからの状態遷移確率aijmは、ajim，lの単純平均、またはΣkakim，lによる重み付き平均として求められて設定される。
【０１９７】
ノードsjからのノードsimへの状態遷移確率ajimは、Σlajim，lにより求められて設定される。
【０１９８】
Ｌ個のノードsim，lが１つのノードsimにマージされた後のノードsimにおける観測シンボルmの観測確率bimは、bim，lの単純平均、またはΣkakim，lによる重み付き平均として求められて設定される。
【０１９９】
ステップＳ１２４では、このように、状態遷移確率aijm、状態遷移確率ajim、観測確率bjmが設定される。
【０２００】
このようにして、バックワードマージアルゴリズムの適用の処理が実行される。
【０２０１】
このように一状態一観測制約およびアクション遷移制約を課すことで、学習処理の負荷を軽減することが可能となる。
【０２０２】
図１９は、アクション拡張型ＨＭＭにおける状態遷移確率テーブルと観測確率テーブルの尤度を比較する表である。同図の最も左側の列は、学習の回数（試行回数）を表している。試行回数の右側の列は、「最初の学習」の列とされており、それぞれの試行回数時に学習された状態遷移確率テーブルと観測確率テーブルの尤度の値が記述されている。「最初の学習」の右側の列は、「スプリット・マージ後」の列とされている。この列には、「最初の学習」によって得られた状態遷移確率テーブルと観測確率テーブルに対して、図１２、図１５、および図１８の処理を施すことにより得られた状態遷移確率テーブルと観測確率テーブルの尤度の値が記述されている。さらに、「スプリット・マージ後」の右側の列は、「増分」の列とされている。この列には、「スプリット・マージ後」の列に記述された尤度値と「最初の学習」の列に記述された尤度値との差分が記述されている。
【０２０３】
図１９に示されるように、図１２、図１５、および図１８の処理を施すことにより尤度が向上することが分かる。また、図１２、図１５、および図１８の処理を施すことにより、尤度値は、「−６０」付近の値をとる回数が多くなることが分かる。つまり、尤度値は、「−６０」付近の値をとるような学習が行われた場合、与えられた環境を最も適切に学習したといえる。これに対して、「最初の学習」の列に記述された尤度は、学習の都度、値が大きく変化しており、学習を繰り返しても与えられた環境を最も適切に学習することは困難であることが判る。
【０２０４】
すなわち、一状態一観測制約とアクション遷移制約を課すことで、アクション拡張型ＨＭＭの学習の精度を高めることができるのである。
【０２０５】
図２０乃至図２６は、一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。
【０２０６】
ここでは、図２０に示される迷路において、図中円で示される位置のパーツを変更し、図２１に示されるような構造に変化させた迷路を環境としてエージェントに学習させる場合を例として説明する。
【０２０７】
図２２は、図２０と図２１に示される環境を学習したエージェントの状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図２２の例では、図中の円でノードが示されており、図中の三角形で表現された方向のアクションにより遷移するノードが線により接続されている。また、図中の円の内部にしめされた番号が、その円で示されるノードのインデックスを表している。図２２の例は、一状態一観測制約とアクション遷移制約を課すことなく得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図とされる。
【０２０８】
これに対して、図２３は、図２２に対応する状態遷移確率テーブルと観測確率テーブルに、一状態一観測制約とアクション遷移制約を課す処理を施すことにより得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図とされる。
【０２０９】
図２３においては、図２２のノード２８がノード２８とノード３１に分割されている。また、図２３においては、図２２のノード１７とノード１９がノード７にマージされている。さらに、図２３においては、図２２のノード１２とノード２５がノード１２にマージされている。
【０２１０】
なお、エージェントが学習のために迷路上を移動していた時間帯において、迷路が図２０に示される構造とされていた時間帯と、迷路が図２１に示される構造とされていた時間帯とが存在する。従って、図２３に示される各ノードの位置が完全に、図２０または図２１のパーツの位置と一致するものではない。例えば、図２３のノード２４、ノード３６、ノード２、ノード１８によって、迷路の構造が時間帯によって変化し得ることが適切に学習されていることが分かる。
【０２１１】
実際には、迷路の規模はさらに大きいものとされる。例えば、図２４に示されるような迷路を環境としてエージェントに学習させる。この場合、一状態一観測制約とアクション遷移制約を課すことなく得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化すると図２５に示されるようになる。これに対して、一状態一観測制約とアクション遷移制約を課すことにより得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化すると図２６に示されるようになる。
【０２１２】
図２５と比較して、図２６は、現実の迷路（図２４）の構造に近いものとなっていることが分かる。
【０２１３】
ここまで、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うために必要となる技術について説明した。
【０２１４】
次に、ここまで説明してきた、図９の学習器３４によるアクション拡張型ＨＭＭの学習処理について、図２７のフローチャートを参照して説明する。
【０２１５】
ステップＳ１６１において、学習器３４は、初期の内部モデルデータを取得する。ここで、初期の内部モデルデータは、例えば、ロボットが迷路上を移動することで生成された直後の状態遷移確率テーブルと観測確率テーブルとされる。状態遷移確率テーブルと観測確率テーブルに設定される状態遷移確率と観測確率は、例えば、各時刻においてロボットが実行したアクションと、そのアクションを実行した結果観測された観測シンボルとの組み合わせからなる情報に基づいて生成される。
【０２１６】
ステップＳ１６２において、学習器３４は、ステップＳ１６１の処理で取得した内部モデルデータを最適化する。このとき、例えば、最尤推定法などにより、状態遷移確率テーブルの各値と観測確率テーブルの各値が最適化されるように変更される。
【０２１７】
ステップＳ１６３において、学習器３４は、ステップＳ１６２の処理で最適化された内部モデルデータが、上述した一状態一観測制約、およびアクション遷移制約を満たすか否かを判定する。
【０２１８】
例えば、１つのノードで観測される観測シンボルが複数ある場合でも、そのうち１つの観測シンボルの観測確率が閾値以上となる場合、一状態一観測制約を満たすことになる。また、例えば、同一のアクションによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測される確率が閾値以下となる場合、アクション遷移制約を満たすことになる。
【０２１９】
ステップＳ１６３において、内部モデルデータが、上述した一状態一観測制約、およびアクション遷移制約を満たさないと判定された場合、処理は、ステップＳ１６４に進む。
【０２２０】
ステップＳ１６４において、学習器３４は、一状態一観測制約、およびアクション遷移制約を満たすように、内部モデルデータを変更する。このとき、例えば、図１２、図１５、および図１８を参照して上述した処理が実行されることにより、状態遷移確率テーブルの各値と観測確率テーブルの各値が変更される。
【０２２１】
ステップＳ１６４の処理の後、処理は、ステップＳ１６２に戻る。そして、ステップＳ１６３において、一状態一観測制約、およびアクション遷移制約を満たすと判定されるまで、ステップＳ１６２乃至ステップＳ１６４の処理が繰り返し実行される。
【０２２２】
ステップＳ１６３において、一状態一観測制約、およびアクション遷移制約を満たすと判定された場合、処理は、ステップＳ１６５に進む。
【０２２３】
ステップＳ１６５において、学習器３４は、内部モデルデータを、内部モデルデータ記憶部３７に保存する。
【０２２４】
このようにして、アクション拡張型ＨＭＭの学習処理が実行される。
【０２２５】
ところで、ＨＭＭの学習の方式として、バッチ学習方式と追加学習方式が存在する。ここで、バッチ学習方式は、例えば、１万ステップの遷移と観測のデータが得られる場合、１万ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存するものである。これに対して、追加学習方式は、例えば、最初に、１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存する。そして、その後の１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルの各値を変更して保存し、・・・というように、繰り返し学習を行って、内部モデルデータを更新（アップデート）していくものである。
【０２２６】
例えば、迷路上を自走するロボットによるアクション拡張型ＨＭＭの学習などの場合、追加学習方式での学習を行うことが求められる。バッチ学習方式での学習では、迷路の構造の変化などを適応的に学ぶことが原理的に不可能であり、変化する環境の中でより良い性能を発揮するためには、動作結果をフィードバックする追加学習方式による学習が必須となるからである。
【０２２７】
ところが、追加学習を行なう際に「学習済みの記憶構造」と「新しい経験」とをどのように統合するのかという問題は未解決である。一方では「新しい経験」を速やかに反映させてすばやい適応を実現したいという要請もあるが、他方、これまでに確立した記憶構造が破壊される危険性もある。
【０２２８】
例えば、図２８に示されるような迷路の構造を学習するロボットが、１度学習して内部モデルデータを保存した後、図中の円１０１で示される範囲内を長時間移動し続けた場合、円１０２で示される範囲の位置に対応する内部モデルデータが破壊されることがある。すなわち、せっかく適切に学習されて記憶されていた円１０２で示される範囲の位置に対応する内部モデルデータが誤って更新されることがある。追加学習方式の学習では、新しく得られた遷移と観測に基づいてのみ、内部モデルデータが更新されるので、円１０１で示される範囲内の位置が誤って、円１０２で示される範囲の位置に対応するノードと認識されることがあるからである。
【０２２９】
このような問題に対処するために、例えば、従来、追加学習方式での学習を行うために、内部モデルデータを迷路の各範囲に対応させて分離して保持するなどされていた。あるいはまた、過去の学習により得られた内部モデルデータを現在の記憶からリハースする等して、学習することが行われていた。
【０２３０】
しかしながら、従来の方式を採用しても、例えば、分離された過去の内部モデルデータに、「新しい体験」が反映されなかったり、リハースされる過去の内部モデルデータが、「新しい体験」の影響を受けて生成されてしまうなどの問題があった。このように、従来の方式では、大規模なＨＭＭの学習において、追加学習を行って実用的なモデルとして機能させることは困難であった。例えば、過去の学習に用いられたデータと、新たな学習に用いられるデータとをまとめてバッチ学習するようにすれば、適切な学習結果を得ることができるが、これを実現するには、膨大な記憶容量と計算量が求められることになる。
【０２３１】
次に、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにするための技術について説明する。
【０２３２】
本発明においては、学習器３４が、次のような追加学習方式による学習を行い、変化する環境の中でより良い性能を発揮でき、かつ安定的な学習を行うことができるようにする。具体的には、後述する状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを算出して保存することにより、アクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにする。
【０２３３】
バッチ学習方式による学習は、換言すれば、複数の時間帯において得られた遷移と観測に基づく学習を足し合わせたものということもできる。例えば、図２９に示されるように、バッチ学習方式の学習で用いられる遷移と観測の全体データＤＡが構成されていると考えられる。すなわち、全体データＤＡは、第１の時間帯において得られたデータセットＤ１と、第２の時間帯において得られたデータセットＤ２と、第３の時間帯において得られたデータセットＤ３と、・・・により構成されていると考えられる。
【０２３４】
アクション拡張型ＨＭＭの学習における状態遷移確率の推定は、上述した式（３）により行なわれるが、ここでは、図２９に示されるように、複数のデータセットが存在している場合を考える。
【０２３５】
第ｎ番目の学習データセットDnにおける状態遷移確率の推定値a´ij(k)(n)は、式（１５）により求めることができる。
【０２３６】
【数１５】
2011018245.tif 000017
・・・（１５）
【０２３７】
ここで、状態遷移確率の推定の説明において、t∈Dnは、特に言及がない場合、この表記により（t，t+1∈Dn）を表すものとする。また、学習データセットDnには、各時刻において実行したアクション、各時刻におけるノード、各時刻における観測シンボルを表す情報が含まれているものとする。
【０２３８】
式（１５）における分子は、学習データセットDnの中で、アクションckを実行することにより、ノードiからノードjに遷移した頻度を表すものと言える。一方、式（１５）の分母は、学習データセットDnの中で、アクションckを実行することにより、ノードiから他のノードに遷移した頻度を表すものと言える。
【０２３９】
いま、式（１５）における分子に対応する式を表す変数χij(k)(n)を式（１６）で示されるものとして定義する。
【０２４０】
【数１６】
2011018245.tif 000018
・・・（１６）
【０２４１】
式（１６）より式（１７）を得ることができる。
【０２４２】
【数１７】
2011018245.tif 000019
・・・（１７）
【０２４３】
式（１７）と式（１５）より式（１８）が導出される。
【０２４４】
【数１８】
2011018245.tif 000020
・・・（１８）
【０２４５】
このように、状態遷移確率の推定値は、変数χij(k)(n)を用いて表すことができるのである。
【０２４６】
ここで、変数χij(k)(n)は、式（１５）における分子に相当し、学習データセットDnの中で、アクションckを実行することにより、ノードiからノードjに遷移した頻度を表すものと言えるから、状態遷移確率の推定のための頻度変数と称することにする。
【０２４７】
本発明では、追加学習方式の学習を行う場合、安定的な学習を行うことができるようにするために、上述した頻度変数χij(k)(n)を用いて状態遷移確率の推定値を求めることにする。すなわち、学習器３４が、１つの学習データセットに基づく学習を行う都度、頻度変数を更新して内部モデルデータの１つとして内部モデルデータ記憶部３７に記憶させて保存するようにする。
【０２４８】
つまり、新たに学習を行う際に、過去の学習データセットに対応する頻度変数を読み出して、その頻度変数に新たな学習に基づいて得られた頻度変数を足しこむことにより頻度変数の値を更新する。さらに、更新された頻度変数に基づいて得られる状態遷移確率の推定値を求めることにより、追加学習方式の学習を行うのである。このようにすることで、学習データセットＤ１，Ｄ２，Ｄ３・・・をまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。
【０２４９】
次に、複数回の学習により得られたそれぞれの内部モデルデータの統合について説明する。すなわち、学習データセットＤ１，Ｄ２，・・・Ｄｎ・・・に基づいて計算される状態遷移確率の推定値a´ij(k)(1)，a´ij(k)(2)，・・・a´ij(k)(n)，・・・の統合について説明する。
【０２５０】
このような場合、例えば、重みwn(Σwn=1)を設定し、式（１９）に示されるように、状態遷移確率の推定値a´ij(k)(1)，a´ij(k)(2)，・・・a´ij(k)(n)，・・・を統合することも考えられる。
【０２５１】
【数１９】
2011018245.tif 000021
・・・（１９）
【０２５２】
式（１９）は、上述した状態遷移確率の推定値のそれぞれに、各学習データセットに対応する重みw1，w2，・・・，wn，・・・を乗じて足し合わせることを意味している。
【０２５３】
しかしながら、上述したように本発明では、学習データセットに対応する頻度変数に基づいて得られる状態遷移確率の推定値を求めるようにしたので、式（１９）による統合は適さない。
【０２５４】
本発明では、学習データセットに対応する頻度変数に基づいて得られる状態遷移確率の推定値を求めるようにしたので、それぞれの状態遷移確率の推定値の信頼性を考慮して統合を行う必要がある。すなわち、学習データセットのデータ量（シーケンス長）を考慮して重みを設定する必要がある。
【０２５５】
また、学習データセットに対応する頻度変数は、過去の学習に基づいて既に設定されている状態遷移確率の値によって変化し得る。例えば、状態遷移確率の値が低い遷移が数多く発生した学習データセットから得られる頻度変数の値は必然的に小さい値となり易く、状態遷移確率の値が高い遷移が数多く発生した学習データセットから得られる頻度変数の値は必然的に大きい値となり易い。上述したように頻度変数は、式（１５）における分子に対応する式で表されるからである。従って、頻度変数の値の大きさも考慮して重みを設定する必要がある。
【０２５６】
本発明では、統合後の状態遷移確率の推定値a´ij(k)を式（２０）により求めるようにする。
【０２５７】
【数２０】
2011018245.tif 000022
・・・（２０）
【０２５８】
このとき、上述したように重みwnの考慮が必要となる。具体的には、シーケンス長Tnの学習データセットDnに対応する頻度変数χij(k)(n)について、式（２１）に示される関係を満たすように重みwnを設定する。
【０２５９】
【数２１】
2011018245.tif 000023
・・・（２１）
【０２６０】
このように、学習データセットごとに、その学習データセットのシーケンス長に応じた重みの調整を行いながら、頻度変数χij(k)(n)をすべてのデータセットに渡って累積すれば、全データをまとめてバッチ学習するのとほぼ同等の結果を得ることができる。すなわち、式（２２）により、頻度変数χij(k)を求め、式（２０）を参照して上述したように、頻度変数χij(k)を用いて統合後の状態遷移確率の推定値a´ij(k)を求めるのである。
【０２６１】
【数２２】
2011018245.tif 000024
・・・（２２）
【０２６２】
このようにすることで、例えば、学習データセットＤ１，Ｄ２，・・・Ｄｎ・・・のそれぞれに対応する状態遷移確率テーブルを保存するなどしなくても、全ての学習データセットをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。すなわち、既に記憶されている、学習データセットＤｎ-1までを学習することにより得られた頻度変数に、学習データセットＤnを学習することにより得られた頻度変数を足しこんで状態遷移確率の推定値を求める。これにより、学習データセットＤ１，Ｄ２，・・・Ｄｎをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。
【０２６３】
一方、アクション拡張型ＨＭＭの学習における観測確率の推定は、上述した式（４）により行なわれるが、ここでは、図２９に示されるように、複数のデータセットが存在している場合を考える。
【０２６４】
第ｎ番目の学習データセットDnにおける観測確率の推定値b´j(o)(n)は、式（２３）により求めることができる。
【０２６５】
【数２３】
2011018245.tif 000025
・・・（２３）
【０２６６】
なお、状態遷移確率の推定の説明の場合と異なり、ここでは、t∈Dnの表記により（t，t+1∈Dn）を表すものではない。
【０２６７】
また、学習データセットDnには、各時刻において実行したアクション、各時刻におけるノード、各時刻における観測シンボルを表す情報が含まれているものとする。ot=oは、時刻tにおける観測シンボルがoであることを表している。
【０２６８】
式（２３）における分子は、学習データセットDnの中で、ノードjにおいて観測シンボルｏが観測された頻度を表すものと言える。一方、式（２３）の分母は、学習データセットDnの中で、ノードjにおいていずれかの観測シンボルが観測された頻度を表すものと言える。
【０２６９】
いま、式（２３）における分子に対応する式を表す変数ωj(o)(n)を式（２４）で示されるものとして定義する。
【０２７０】
【数２４】
2011018245.tif 000026
・・・（２４）
【０２７１】
式（２４）より式（２５）を得ることができる。
【０２７２】
【数２５】
2011018245.tif 000027
・・・（２５）
【０２７３】
式（２５）と式（２３）より式（２６）が導出される。
【０２７４】
【数２６】
2011018245.tif 000028
・・・（２６）
【０２７５】
このように、観測確率の推定値は、変数ωj(o)(n)を用いて表すことができるのである。
【０２７６】
ここで、変数ωj(o)(n)は、式（２３）における分子に相当し、学習データセットDnの中で、ノードjにおいて観測シンボルｏが観測された頻度を表すものと言えるから、観測確率の推定のための頻度変数と称することにする。
【０２７７】
本発明では、状態遷移確率の場合と同様に、追加学習方式の学習を行う場合、安定的な学習を行うことができるようにするために、上述した変数ωj(o)(n)を用いて観測確率の推定値を求めることにする。すなわち、学習器３４が、１つの学習データセットに基づく学習を行う都度、頻度変数更新して内部モデルデータの１つとして内部モデルデータ記憶部３７に記憶させて保存するようにする。
【０２７８】
そして、新たに学習を行う際に、過去の学習データセットに対応する頻度変数を読み出して、その頻度変数に新たな学習に基づいて得られた頻度変数を足しこむことにより頻度変数の値を更新する。さらに、更新された頻度変数に基づいて得られる観測確率の推定値を求めることにより、追加学習方式の学習を行うのである。
【０２７９】
次に、複数回の学習により得られたそれぞれの内部モデルデータの統合について説明する。すなわち、学習データセットＤ１，Ｄ２，・・・Ｄｎ・・・に基づいて計算される観測確率の推定値b´j(o)(1)，b´j(o)(2)，・・・b´j(o)(n)，・・・の統合について説明する。
【０２８０】
統合にあたって、状態遷移確率の推定値の統合の場合と同様の理由で、重みw´nの考慮が必要となる。
【０２８１】
本発明では、統合後の状態遷移確率の推定値b´j(o)を式（２７）により求めるようにする。
【０２８２】
【数２７】
2011018245.tif 000029
・・・（２７）
【０２８３】
このとき、シーケンス長Tnの学習データセットDnに対応する頻度変数ωj(o)(n)について、式（２８）に示される関係を満たすように重みw´nを設定する。
【０２８４】
【数２８】
2011018245.tif 000030
・・・（２８）
【０２８５】
このように、学習データセットごとに、その学習データセットのシーケンス長に応じた重みの調整を行いながら、頻度変数ωj(o)(n)をすべてのデータセットに渡って累積すれば、全データをまとめてバッチ学習するのとほぼ同等の結果を得ることができる。すなわち、式（２９）により、頻度変数ωj(o)を求め、式（２７）を参照して上述したように、頻度変数ωj(o)を用いて統合後の観測確率の推定値b´j(o)を求めるのである。
【０２８６】
【数２９】
2011018245.tif 000031
・・・（２９）
【０２８７】
このようにすることで、例えば、学習データセットＤ１，Ｄ２，・・・Ｄｎ・・・のそれぞれに対応する観測確率テーブル、状態遷移確率テーブルを保存するなどしなくても、全ての学習データセットをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。すなわち、既に記憶されている、学習データセットＤｎ-1までを学習することにより得られた頻度変数に、学習データセットＤnを学習することにより得られた頻度変数を足しこんで観測確率の推定値を求める。これにより、学習データセットＤ１，Ｄ２，・・・Ｄｎをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。
【０２８８】
例えば、式（１５）または式（２３）の計算結果をそのまま保存して追加学習方式による学習を行っても学習データセットＤ１，Ｄ２，・・・Ｄｎをまとめてバッチ学習するのとほぼ同等の結果を得ることはできない。式（１５）または式（２３）の計算結果は、確率の値として算出されるものであり、あり得る遷移の確率の合計値が１となるように正規化されているからである。仮に、式（１５）または式（２３）の計算結果をそのまま保存して、追加学習方式による学習を行っても、まとめてバッチ学習するのとほぼ同等の結果を得ることができるようにするためには、例えば、学習データセットのそれぞれに対応するテーブルを保存するなどの必要がある。このため、本発明では、式（１５）または式（２３）における分子に対応する式により得られる頻度変数を保存するようにしたのである。
【０２８９】
このようにして、状態遷移確率と観測確率を求めるようにすれば、追加学習方式による学習を行って、変化する環境の中でより良い性能を発揮できるとともに、安定的な学習を行うことができるようになる。
【０２９０】
また、そのようにするために、過去の学習のそれぞれに対応する内部モデルデータを全て保存するなどの必要がなく、例えば、内部モデルデータ記憶部３７の記憶容量を小さいものとすることができる。さらに、追加学習方式による学習の結果、内部モデルデータを更新する際の演算量を少なくすることができ、環境の変化をより迅速に認識させるようにすることが可能となる。
【０２９１】
ここまでの追加学習方式に関する説明は、離散観測信号を取得する場合の例について説明した。連続観測信号を取得する場合は、時刻tにおいてエージェントが状態jにいる場合の重み係数γt(j）よって重み付けた信号分布を用いて、観測確率密度関数bj(o)のパラメータを再推定すればよい。このとき、重み係数γt(j）が式（３０）を満たすように調整する必要がある。
【０２９２】
【数３０】
2011018245.tif 000032
・・・（３０）
【０２９３】
いまの場合、γ′t(j)が頻度相当の意味を有するものとなる。
【０２９４】
そして、γ′t(j) ≡ w′nγt(j)を用いて観測信号の平均ベクトルおよび共分散行列を推定すればよい。
【０２９５】
通常は、ガウス分布などの対数凹又は楕円型対称確率密度をモデルとして用い、観測確率密度関数bj(o)のパラメータの再推定を行うことができる。
【０２９６】
ガウス分布などの対数凹又は楕円型対称確率密度のモデルのパラメータとしては、状態jにおける観測信号の平均ベクトルμ´jおよび共分散行列U´jを用いることができる。平均ベクトルμ´jおよび共分散行列U´jは、それぞれ、式（３１）および式（３２）により求めることができる。
【０２９７】
【数３１】
2011018245.tif 000033
・・・（３１）
【０２９８】
【数３２】
2011018245.tif 000034
・・・（３２）
【０２９９】
以上に説明した通り、追加学習方式による学習時の安定性を確保することができるが、追加学習方式の場合、直近の学習結果により大きな重みを与えて内部モデルデータを更新させることが多い。新しい経験は、環境の変化をより適切に学習するのに都合が良いと考えられるからである。
【０３００】
例えば、１０万サンプルからなる学習を終えた学習器に対して１００サンプルの新規データを与えて追加学習方式の学習をさせる場合を考える。既に学習したものの大きさ(１０万)に対して新たに学習するデータの量(１００)が小さいため、そのまま学習すると新たな学習の影響度は０.１％となる。このような場合、環境の変化を適切に学習しているとは言い難い。
【０３０１】
そこで、例えば、新たな学習の影響度である学習率を指定することができれば便利である。例えば、上述の例において、学習率を０.１(１０％)と指定した場合、新たに学習するデータの量を変えることなく、影響度を１００倍にすることができる。
【０３０２】
本発明では、上述した学習率の指定があった場合でも、学習の安定性を損なうことがないようにする。
【０３０３】
上述したように、状態遷移確率の推定のための頻度変数χij(k)は、式（３３）で示されるように更新される。なお式（３３）における⇒は、χij(k)が右辺に示されるように更新されることを表している。
【０３０４】
【数３３】
2011018245.tif 000035
・・・（３３）
【０３０５】
観測確率の推定のための頻度変数ωj(o)は、式（３４）で示されるように更新される。なお式（３４）における⇒は、ωj(o)が右辺に示されるように更新されることを表している。
【０３０６】
【数３４】
2011018245.tif 000036
・・・（３４）
【０３０７】
いま、学習率ｒ(0≦r≦1)が指定された場合、本発明では、状態遷移確率の推定のための頻度変数を算出するために、式（３５）に示される重みWnと、重みzi(k)(n)を演算する。重みWnと、重みzi(k)(n)は、それぞれ新たな学習に基づいて得られた頻度変数に乗じるための重みと、既に保存されている頻度変数に乗じるための重みとして演算される。
【０３０８】
【数３５】
2011018245.tif 000037
・・・（３５）
【０３０９】
そして、状態遷移確率の推定のための頻度変数は、式（３６）により演算される。
【０３１０】
【数３６】
2011018245.tif 000038
・・・（３６）
【０３１１】
なお、式（３５）における重みzi(k)(n)は、重みWnが学習を繰り返すに従って一方的に大きくなることを考慮して設けられた重みであり、実際の演算では用いられないようにしてもよい。
【０３１２】
また、学習率ｒ(0≦r≦1)が指定された場合、観測確率の推定のための頻度変数を算出するために、式（３７）に示される重みW´nと、重みzi(n)を演算する。重みW´nと、重みzi (n)は、それぞれ新たな学習に基づいて得られた頻度変数に乗じるための重みと、既に保存されている頻度変数に乗じるための重みとして演算される。
【０３１３】
【数３７】
2011018245.tif 000039
・・・（３７）
【０３１４】
そして、状態遷移確率の推定のための頻度変数は、式（３８）により演算される。
【０３１５】
【数３８】
2011018245.tif 000040
・・・（３８）
【０３１６】
なお、式（３７）における重みzi(n)は、重みW´nが学習を繰り返すに従って一方的に大きくなることを考慮して設けられた重みであり、実際の演算では用いられないようにしてもよい。
【０３１７】
ここまでの学習率の指定のある追加学習方式に関する説明は、離散観測信号を取得する場合の例について説明した。連続観測信号を取得する場合も同様に、対応する重み変換を行ってから分布パラメータの推定を行えばよい。
【０３１８】
このようにすることで、学習率の指定があった場合でも、学習の安定性を損なうことがないようにすることができる。
【０３１９】
ところで、頻度変数を用いた状態遷移確率の推定値a´ij(k)の算出については、上述したように式（２０）により求めることができるが、実際には、分母のΣjχij(k)が小さい値となる場合、計算結果が擾乱することがある。上述した擾乱は、学習により得られる内部モデルデータの信頼性を損ねて、その後の環境の認識に影響し、エージェントが環境を誤って認識してしまう。さらに、その認識結果が、追加学習方式の学習の結果に対しても再帰的に悪影響を及ぼすため、この問題を解決する必要がある。
【０３２０】
ここで、Nik＝Σjχij(k)とする。Nikが小さい値となる場合、計算結果が擾乱するという問題を解決するためには、状態遷移確率に対するNikの小ささに応じたペナルティ係数を乗ずるようにすればよい。すなわち、ペナルティ係数をη(Nik)とし、状態遷移確率の推定値a´ij(k)を、式（３９）により求めるようにすればよい。
【０３２１】
【数３９】
2011018245.tif 000041
・・・（３９）
【０３２２】
ただし、関数η(x)は、定義域0≦xに対して値域0≦η(x)≦1を満たす単調増加関数であるものとする。
【０３２３】
関数η(x)は、例えば、式（４０）により表される関数とされる。
【０３２４】
【数４０】
2011018245.tif 000042
・・・（４０）
【０３２５】
式（４０）におけるα(>0)，βは、必要に応じて適切に調整されるパラメータであり、例えば、指定された学習率rに応じて調整されるようにしてもよい。
【０３２６】
ところで、上述したように、本発明においては、内部モデルデータとして、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数とを記憶するようにした。そうすると、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対しても、上述した一状態一観測制約とアクション遷移制約を課す処理を施すことが必要となる。
【０３２７】
状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するスプリットアルゴリズム適用の処理は、次のようにして行われる。
【０３２８】
ここでは、ノードsjをＫ個のノードに分割する場合の例について説明する。なお、ノードsjが分割された結果得られるＫ個のノードのうちの第ｋ番目のノードを、sjkと表すこととし、ノードsjが分割された後のノードsiからノードsjkへの状態遷移確率をakijで表すことにする。また、ノードsjが分割された後のノードsjkからノードsiへの状態遷移確率をakjiで表すことにする。
【０３２９】
学習器３４は、観測シンボルoについての観測確率bj(o)に対応する観測確率の推定のための頻度変数ωj(o)を、式（４１）により求める。
【０３３０】
【数４１】
2011018245.tif 000043
・・・（４１）
【０３３１】
また、学習器３４は、状態遷移確率akijに対応する状態遷移確率の推定のための頻度変数χkijが、分割前の頻度変数χijを分割前の各観測シンボルの観測確率に対応する観測確率の推定のための頻度変数ωj(ok)の比で案分されたものとなるように設定する。
【０３３２】
さらに、学習器３４は、状態遷移確率akjiに対応する状態遷移確率の推定のための頻度変数χkjiが、分割前の頻度変数χjiを分割前の各観測シンボルの観測確率に対応する観測確率の推定のための頻度変数ωj(ok)の比で案分されたものとなるように設定する。
【０３３３】
状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するフォワードマージアルゴリズム適用の処理は、次のようにして行われる。
【０３３４】
ここでは、Ｌ個のノード群sjm，l(l=1，・・・，L)を１つのノードsjmにマージする場合の例について説明する。なお、マージされた後のノードsiからノードsjmへの状態遷移確率をaijmで表し、マージされた後のノードsjmからノードsiへの状態遷移確率をajimで表すことにする。また、マージされた後の各観測シンボルの観測確率のそれぞれを要素とするベクトルを、bjmで表すことにする。
【０３３５】
学習器３４は、状態遷移確率aijmに対応する状態遷移確率の推定のための頻度変数χijmをΣlχijm，lにより求めて設定する。ここで、χijm，lは、マージされる前のノードsiからノードsjm，lへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。
【０３３６】
また、学習器３４は、状態遷移確率ajimに対応する状態遷移確率の推定のための頻度変数χjimをΣlχjim，lにより求めて設定する。ここで、χjim，lは、マージされる前のノードsjm，lからノードsiへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。
【０３３７】
さらに、学習器３４は、ベクトルbjmの要素のそれぞれに対応する状態遷移確率の推定のための頻度変数のそれぞれを要素とするベクトルωjmをΣlωjm，lにより求めて設定する。
【０３３８】
そして学習器３４は、すべてのマージが終了したら、修正された状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを用いて状態遷移確率と観測確率とを再計算する。
【０３３９】
状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するバックワードマージアルゴリズム適用の処理は、次のようにして行われる。
【０３４０】
ここでは、Ｌ個のノード群sjm，l(l=1，・・・，L)を１つのノードsjmにマージする場合の例について説明する。なお、マージされた後のノードsiからノードsjmへの状態遷移確率をaijmで表し、マージされた後のノードsjmからノードsiへの状態遷移確率をajimで表すことにする。また、マージされた後の各観測シンボルの観測確率のそれぞれを要素とするベクトルを、bjmで表すことにする。
【０３４１】
学習器３４は、状態遷移確率aijmに対応する状態遷移確率の推定のための頻度変数χijmをΣlχijm，lにより求めて設定する。ここで、χijm，lは、マージされる前のノードsiからノードsjm，lへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。
【０３４２】
また、学習器３４は、状態遷移確率ajimに対応する状態遷移確率の推定のための頻度変数χjimをΣlχjim，lにより求めて設定する。ここで、χjim，lは、マージされる前のノードsjm，lからノードsiへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。
【０３４３】
さらに、学習器３４は、ベクトルbimの要素のそれぞれに対応する観測確率の推定のための頻度変数のそれぞれを要素とするベクトルωimをΣlωim，lにより求めて設定する。
【０３４４】
そして学習器３４は、すべてのマージが終了したら、修正された状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを用いて状態遷移確率と観測確率とを再計算する。
【０３４５】
このようにすることで、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対しても、上述した一状態一観測制約とアクション遷移制約が課されることになる。
【０３４６】
ここまで、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにするための技術について説明した。
【０３４７】
ところで以上においては、図８を参照して上述したような、３次元の状態遷移確率テーブルと、２次元の観測確率テーブルを有するアクション拡張型ＨＭＭの例について説明した。通常は、ノード数をＮ、観測シンボル数をＭ、アクション数をＫとすると、算出すべきパラメータ数は、Ｎ2Ｋ＋ＮＭとなり、Ｎ、Ｍ、およびＫの値が一定であることを前提に学習アルゴリズムが定められる。
【０３４８】
しかしながら、学習を進めるうちにＮ、Ｍ、およびＫの値を変更する必要に迫られることがある。例えば、ロボットが移動する迷路に用いられるパーツが新たに加わった場合、観測シンボルの種類が増えることになるので、Ｍの値を大きくする必要がある。
【０３４９】
次に、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更する必要に迫られた場合にとり得る処置について説明する。
【０３５０】
図３０は、観測シンボルの種類が増えることによる影響を説明する図である。同図に示されるように、観測シンボルの種類が増えると、観測確率テーブルの行方向（図中水平方向）の拡張が生じることになる。すなわち、領域１２１に対応する観測確率の値を新たに設定する必要がある。なお、観測確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。
【０３５１】
また、図３０に示されるように、観測確率テーブルの行方向（図中水平方向）の拡張が生じたことにより、観測確率の推定のための頻度変数のテーブルも拡張させる必要がある。すなわち、領域１２２に対応する頻度変数の値を新たに設定する必要がある。
【０３５２】
本発明では、図３０に示されるように観測確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけ観測シンボルの種類が増えることを前提として、図３０に示されるように観測確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。
【０３５３】
いま、新しい観測シンボルoM+iに対応するインデックスをM+iとして、観測確率テーブルに第M+i列を追加するものとする。
【０３５４】
学習器３４は、観測確率テーブルの第M+i列に設定すべき観測確率値を適切な大きさの非零要素とする。この非零要素の値は、次のように決定される。
【０３５５】
式（４２）に示されるように、新しい観測シンボルを追加する前の観測シンボルの数をＭとし、第M+i列に設定すべき観測確率値は、全て１／Ｍとする。
【０３５６】
【数４２】
2011018245.tif 000044
・・・（４２）
【０３５７】
あるいはまた、式（４３）に示されるように、観測確率テーブルの各行ごとに、観測確率bj(・)が閾値以上となる観測シンボルの数をカウントし、その数njを用いて第M+i列に設定すべき観測確率値を求める。なお、bj(・)は、閾値以上となった、それぞれの観測シンボルの観測確率を表している。
【０３５８】
【数４３】
2011018245.tif 000045
・・・（４３）
【０３５９】
学習器３４は、式（４２）または式（４３）に示されるように、観測確率テーブルの第M+i列に適切な大きさの非零要素を設定した後、テーブルの１行あたり観測確率値の合計が１.０となるように調整する。すなわち、式（４４）に示されるように、観測確率テーブル内の非零の各観測確率bj(・)を更新する。これにより、観測確率テーブルの拡張は完了する。
【０３６０】
【数４４】
2011018245.tif 000046
・・・（４４）
【０３６１】
さらに、学習器３４は、観測確率の推定のための頻度変数のテーブルの第M+i列に設定すべき観測確率値を全て０（零）とする。これにより、観測確率の推定のための頻度変数のテーブルの拡張は完了する。
【０３６２】
そして学習器３４は、新しい観測シンボルを含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。
【０３６３】
このようにすることで、追加学習方式での学習中に、新たな観測シンボルが観測された場合でも、内部モデルデータを適切に更新することができる。
【０３６４】
また、例えば、学習中に所定の観測シンボルが不要となった場合、観測確率テーブルを列方向に縮小させることも可能である。
【０３６５】
この場合、学習器３４は、不要となる観測シンボルに対応するインデックスをkとすると、観測確率テーブルから第k列を削除して、ノードsjにおける観測確率bj(k)が存在しないようにする。
【０３６６】
学習器３４は、観測確率の推定のための頻度変数のテーブルについても同様に、第k列を削除して、ωj(k)が存在しないようにする。
【０３６７】
さらに、学習器３４は、観測確率の推定のための頻度変数を用いて縮小後の観測確率テーブル内の各値を再計算する。
【０３６８】
そして学習器３４は、所定の観測シンボルが不要となった後の学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。
【０３６９】
また、例えば、ロボットが移動する迷路が所定の方向に延長された場合、ノードの数が増えることになるので、ノード数Ｎの値を大きくする必要がある。
【０３７０】
図３１は、ノードの数が増えることによる影響を説明する図である。同図に示されるように、ノードの数が増えると、状態遷移確率テーブルの行列方向の拡張が生じることになる。すなわち、図３１の第１枚目の状態遷移確率テーブルにおける逆Ｌ字型の領域１３１−１に対応する状態遷移確率の値を新たに設定する必要がある。同様に、各アクションに対応する状態遷移確率テーブルの逆Ｌ字型の領域１３１−２、領域１３１−３、・・・に対応する状態遷移確率の値を新たに設定する必要がある。すなわち、アクション数Ｋ枚の状態遷移確率テーブルを拡張させて状態遷移確率の値を新たに設定する必要がある。なお、状態遷移確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。
【０３７１】
また、ノードの数が増えると、観測確率テーブルの列方向（図中垂直方向）の拡張が生じることになる。すなわち、領域１３４に対応する観測確率の値を新たに設定する必要がある。なお、観測確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。
【０３７２】
さらに、同図には示されていないが、状態遷移確率の推定のための頻度変数のテーブルと、観測確率の推定のための頻度変数のテーブルも同様に拡張させて値を新たに設定する必要がある。
【０３７３】
本発明では、図３１に示されるように状態遷移確率テーブルと観測確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけノードの数が増えることを前提として、図３１に示されるように状態遷移確率テーブルと観測確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。
【０３７４】
いま、新しいノードsN+iに対応するインデックスをN+iとして、状態遷移確率テーブルに第N+i行と第N+i列を追加するものとする。
【０３７５】
学習器３４は、状態遷移確率テーブルの第N+i行と第N+i列に設定すべき状態遷移確率値を、それぞれ微小なランダム要素とする。
【０３７６】
学習器３４は、状態遷移確率の推定のための頻度変数のテーブルについても同様に、第N+i行と第N+i列とを追加し、設定すべき状態遷移確率値を、それぞれ微小なランダム要素とする。
【０３７７】
学習器３４は、ノードsN+iにおいて実行したことのあるアクションckを特定する。そして学習器３４は、アクションckに対応する第ｋ枚目の状態遷移確率テーブルのノードsN+iに対応する行の状態遷移確率値のそれぞれを一様の値とする。ただし、アクションck実行時の実際の遷移結果を考慮して、経験のある遷移先状態への遷移確率を多少引き上げるようにしてもよい。
【０３７８】
また、アクションckを実行した結果、ノードsN+iへの遷移したことのある遷移元のノードsjを特定する。そして学習器３４は、アクションckに対応する第ｋ枚目の状態遷移確率テーブルのノードsjに対応する行の状態遷移確率値のそれぞれを次のように設定する。
【０３７９】
当該行において、状態遷移確率が閾値以上となる遷移先ノードslの数をカウントし、その数をＬとする。そして、第ｋ枚目の状態遷移確率テーブルのノードsjからノードsN+iへの状態遷移確率aiN+i(k)を１/Ｌとする。
【０３８０】
そして学習器３４は、テーブルの１行あたり状態遷移確率値の合計が１.０となるように調整する。すなわち、式（４５）に示されるように、状態遷移確率テーブル内の各状態遷移確率aj(k)を更新する。これにより、状態遷移確率テーブルの拡張は完了する。
【０３８１】
【数４５】
2011018245.tif 000047
・・・（４５）
【０３８２】
さらに、学習器３４は、状態遷移確率の推定のための頻度変数のテーブルの追加領域に設定すべき状態遷移確率値を全て０（零）とする。これにより、状態遷移確率の推定のための頻度変数のテーブルの拡張は完了する。
【０３８３】
また、学習器３４は、観測確率テーブルの第N+i行と第N+i列に設定すべき観測確率値を、適切な大きさの非零要素とする。非零要素の値としては、例えば、１/Ｎのような一様の値とされるが、ノードsN+iで実際に観測されたことのある観測シンボルの観測確率を引き上げるようにしてもよい。
【０３８４】
さらに、学習器３４は、観測確率の推定のための頻度変数のテーブルにおいて追加されたノードsN+iに対応する第N+i 行をすべて０（零）とする。これにより、観測確率の推定のための頻度変数のテーブルの拡張は完了する。
【０３８５】
そして学習器３４は、新たなノードを含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。
【０３８６】
あるいはまた、例えば、ロボットが迷路上における移動可能方向が拡張されるように改造された場合、アクションの数が増えることになるので、アクション数Ｋの値を大きくする必要がある。
【０３８７】
図３２は、アクションの数が増えることによる影響を説明する図である。同図に示されるように、アクションの数が増えると、状態遷移確率テーブルの奥行方向の拡張が生じることになる。すなわち、例えば、新たに追加されたアクションに対応する状態遷移確率テーブルであって、図３２の第３枚目の状態遷移確率テーブル１４１の状態遷移確率の値を新たに設定する必要がある。
【０３８８】
また、同図には示されていないが、状態遷移確率の推定のための頻度変数のテーブルも同様に拡張させて値を新たに設定する必要がある。
【０３８９】
本発明では、図３２に示されるように状態遷移確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけアクションが増えることを前提として、図３２に示されるように状態遷移確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。
【０３９０】
いま、新しいアクションcK+i に対応するインデックスをK+iとして、第K+i枚目の状態遷移確率テーブルを追加するものとする。
【０３９１】
学習器３４は、追加された第K+i枚目の状態遷移確率テーブルの全ての状態遷移確率を０とする。
【０３９２】
また、学習器３４は、状態遷移確率の推定のための頻度変数のテーブルも同様に、第K+i枚目のテーブルを追加し、追加された第K+i枚目の状態遷移確率テーブルの全ての状態遷移確率を０とする。これにより、状態遷移確率の推定のための頻度変数のテーブルの拡張は完了する。
【０３９３】
さらに、学習器３４は、新しいアクションcK+iを実行したことがあるノードsjを特定する。そして学習器３４は、第K+i枚目の状態遷移確率テーブルのノードsjに対応する行の状態遷移確率値を全て一様の値とする。ただし、実際のアクションcK+i実行時の遷移結果を考慮して、経験のある遷移先ノードへの状態遷移確率を多少引き上げるようにしてもよい。これにより、状態遷移確率テーブルの拡張は完了する。
【０３９４】
そして学習器３４は、新たなアクションの実行を含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。
【０３９５】
上述した処理により、学習を進めるうちにノード数、観測シンボル数、アクション数を追加する必要に迫られた場合であっても学習を継続させることが可能となる。上述した処理は、例えば、ロボットに対して予め所定の数だけ観測シンボルの種類が増えることを前提として、図３０乃至図３２に示されるように各テーブルを拡張する場合の例である。
【０３９６】
しかしながら、例えば、所定の数だけ観測シンボル、ノード、またはアクションが増えることを予め知ることができない場合がある。つまり、エージェントの自律的な行動によって逐次環境の変化が認識されるような場合、例えば、ロボットの管理者などが事前にどれだけ観測シンボル、ノード、またはアクションが増えるのかを知ることができない。従って、例えば、ロボットが迷路を移動中に、任意に新たな迷路のパーツが出現したり、新たに迷路が拡張されたり、新たに移動方向が追加されたりする場合は、さらなる考慮が必要となる。
【０３９７】
次に、例えば、ロボットが迷路を移動中に、新たな迷路のパーツが出現したり、新たに迷路が拡張されたりする場合の、状態遷移確率テーブル、観測確率テーブルの拡張について説明する。すなわち、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合の例について説明する。
【０３９８】
エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合、そもそもエージェント自身が、新たに環境が拡張されたのか否かを認識する必要がある。つまり、エージェントが、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのか認識できるようにしなければならない。例えば、ロボットが迷路を移動中に、新たに迷路が拡張された場合、拡張された部分を移動しているとき、自分が新たに追加されるべきノードに位置していることを認識できるようにしなければ、自律的に環境の変化を認識することができない。
【０３９９】
ここで、自律行動学習装置１０におけるノードの認識の方式について説明する。ノードの認識は、図９の認識器３５により行なわれる。詳細は後述するが、ここでは、時系列情報の長さ値に上限があること、および認識された現在の状態確率のエントロピーの値の変化を考慮して、最終的には４通りの方式を説明することにする。
【０４００】
上述したように、認識器３５は、観測バッファ３３および行動出力バッファ３９に記憶されている情報、並びに内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいて、現在、ロボットが位置するノードを認識するようになされている。
【０４０１】
また、上述したように、時刻t，t+1，t+2，・・・Tの各時刻で取得した観測信号に対応する観測シンボルot， ot+1， ot+2， ・・・， oTが各時刻の観測シンボルとして観測バッファ３３に記憶されている。同様に、例えば、時刻t，t+1，t+2，・・・Tの各時刻で実行したアクションct， ct+1， ct+2， ・・・， cTが各時刻のアクションとして行動出力バッファ３９に記憶されている。
【０４０２】
ここでは、認識器３５に入力される情報であって、観測バッファ３３および行動出力バッファ３９に記憶されている情報を時系列情報と称することにし、時系列情報の長さを変数Ｎで表すことにする。
【０４０３】
また、認識器３５から出力された認識結果は、その認識結果が出力された時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【０４０４】
認識器３５は、まず、時系列情報の長さＮを設定し、観測バッファ３３および行動出力バッファ３９から長さＮの時系列情報を取得し、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づく認識を行なう。
【０４０５】
認識器３５は、例えば、Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する。例えば、Ｎ＝３であった場合、認識器３５は、認識結果としてのノード列s1，s2，s3を出力する。この場合、認識器３５は、時刻t1，において、ロボットがノードs1に位置し、時刻t2において、ロボットがノードs2に位置し、時刻t3において、ロボットがノードs3に位置していたと認識したことになる。
【０４０６】
なお、Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する処理においては、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいてノード列が推測されて出力される。Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する場合、最も確からしい確率を有するノード列を含んだ複数のノード列を出力することが可能である。ここでは、Viterbiアルゴリズムを用いて得られた最も確からしい確率を有するノード列が出力されるものとする。
【０４０７】
認識器３５は、さらに、現在ロボットが位置するノードが新たに追加されるべきであるのか否かを判定するために、Viterbiアルゴリズムを用いて出力されたノード列が、実際にあり得るノード列であるか否かを判定する。
【０４０８】
出力されたノード列が、実際にあり得るノード列であるか否かの判定は、例えば、次のようにして行なわれる。
【０４０９】
いま、出力されたノード列（長さＴのノード列）をＸで表し、時系列情報に基づいて特定された観測シンボルの列（長さＴの観測シンボルの列）を、観測系列Ｏで表すことにする。また、内部モデルデータの状態遷移確率テーブルを、行列Ａで表すことにする。なお、行列Ａは、時系列情報に基づいて特定されたアクションのそれぞれに対応する状態遷移確率テーブルを意味することとする。
【０４１０】
認識器３５は、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かを判定する。
【０４１１】
【数４６】
2011018245.tif 000048
・・・（４６）
【０４１２】
【数４７】
2011018245.tif 000049
・・・（４７）
【０４１３】
ここで、P(O|X)は、ノード列Ｘを構成する各ノードにおける観測系列Ｏを構成する各観測シンボルの観測確率を意味するものとし、観測確率テーブルに基づいて特定することができる。また、Threstrans、およびThresobsは、それぞれ遷移があり得るかどうかの閾値と観測があり得るかどうかの閾値を表すものとする。
【０４１４】
従って、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）のいずれか１つでも満たさないと判定された場合、認識器３５は、出力されたノード列が、実際にあり得るノード列ではないと判定する。これにより、現在ロボットが位置するノード（時系列情報の最後の時刻におけるノード）は、新たに追加されるべきノードであって、未知のノードであると認識されるようにすることができる。
【０４１５】
ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすと判定された場合、認識器３５は、現在の状態遷移確率のエントロピーを計算する。
【０４１６】
ここで、エントロピーをＥ、ノードＸiの事後確率をP(Xi|O)とし、現在の内部モデルデータ上に存在するノード数の合計をＭで表すことにする。なお、ノード（状態）の事後確率とは、Viterbiアルゴリズムにより出力された確率であって、時系列情報の最後の時刻におけるノードに対応する確率を意味する。この場合、エントロピーＥは、式（４８）により表すことができる。
【０４１７】
【数４８】
2011018245.tif 000050
・・・（４８）
【０４１８】
例えば、式（４８）により演算されたエントロピーの値を所定の閾値と比較し、閾値未満である場合、認識器３５は、出力されたノード列が、実際にあり得るノード列であって一意に特定することができる状況であることを意味する。これにより、現在ロボットが位置するノード（時系列情報の最後の時刻におけるノード）は、内部モデルデータ上に既に存在するノードであって、既知のノード（学習済みの内部状態）であると認識されるようにすることができる。
【０４１９】
さらに、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かが判定され、Thres以上である場合にのみ、時系列情報の最後の時刻におけるノードは、既知のノードであると認識されるようにしてもよい。すなわち、認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値を設けるのである。ここで、固有ノード数とは、インデックスが異なるノードのみをカウントした場合のノード数を意味する。
【０４２０】
例えば、出力されたノード列のインデックスが「１０」、「１１」、「１０」、「１１」、「１２」、「１３」であった場合、ノード列の長さは６であるが、固有ノード数は４である。例えば、エージェントが同じノード間の遷移を繰り返した場合、同じ長さの時系列情報に基づいて認識を行なったとしても、認識結果の精度は低くなる。このため、認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値を設けるようにしてもよい。
【０４２１】
一方、エントロピーの値が閾値以上である場合、出力されたノード列が、実際にあり得るノード列であるが、例えば、複数の候補が存在しており一意に特定することができない状況であることを意味する。このため、認識器３５は、出力されたノード列が、時系列情報の長さを増加させるべきと判定する。これにより、例えば、時系列情報の長さＮの値がインクリメントされて処理が繰り返し実行される。
【０４２２】
次に、図３３のフローチャートを参照して、認識器３５によるノード認識処理について説明する。この処理は、認識器３５によるノード認識処理の第１の方式の例となる処理である。
【０４２３】
ステップＳ２０１において、認識器３５は、変数Ｎの値を初期値である１にセットする。
【０４２４】
ステップＳ２０２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。
【０４２５】
ステップＳ２０３において、認識器３５は、ステップＳ２０２で出力された時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力する。
【０４２６】
ステップＳ２０４において、認識器３５は、ステップＳ２０３の処理の結果、出力されたノード列が実際にあり得るノード列であるか否かを判定する。このとき、上述したように、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かが判定される。ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たす場合、ステップＳ２０４では、実際にあり得るノード列であると判定される。一方、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）の少なくとも一方を満たさない場合、ステップＳ２０４では、実際にあり得るノード列ではないと判定される。
【０４２７】
ステップＳ２０４において、実際にあり得るノード列ではないと判定された場合、処理は、ステップＳ２０８に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、未知ノードであると認識する。ステップＳ２０８の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【０４２８】
一方、ステップＳ２０４において、実際にあり得るノード列であると判定された場合、処理は、ステップＳ２０５に進む。
【０４２９】
ステップＳ２０５において、認識器３５は、エントロピーを計算する。このとき上述したように、式（４８）によりエントロピーが演算される。
【０４３０】
ステップＳ２０６において、認識器３５は、ステップＳ２０５の処理で演算されたエントロピーの値を所定の閾値と比較し、エントロピーの値が閾値以上であるか否かを判定する。
【０４３１】
ステップＳ２０６において、エントロピーの値が閾値以上であると判定された場合、処理は、ステップＳ２０９に進む。
【０４３２】
ステップＳ２０９において、認識器３５は、変数Ｎの値を１だけインクリメントする。これにより、その後実行されるステップＳ２０２の処理において、長さがＮ＋１の時系列情報が取得されることになる。なお、ステップＳ２０９において変数Ｎの値をインクリメントする毎に、ステップＳ２０２で取得される時系列情報は、過去方向に延長されるものとする。
【０４３３】
このように、ステップＳ２０４で実際にあり得るノード列ではないと判定されるか、または、ステップＳ２０６において、エントロピーの値が閾値以上ではないと判定されるまで、ステップＳ２０２乃至ステップＳ２０６、およびステップＳ２０９の処理が繰り返し実行される。
【０４３４】
ステップＳ２０６において、エントロピーの値が閾値以上ではないと判定された場合、処理は、ステップＳ２０７に進む。
【０４３５】
また、ステップＳ２０４において、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かがさらに判定され、Thres以上である場合にのみ、処理は、ステップＳ２０５またはステップＳ２０８に進むようにしてもよい。
【０４３６】
あるいはまた、ステップＳ２０３で固有ノード数が閾値Thres以上となるノード列が出力された場合にのみ、処理がステップＳ２０４に進み、固有ノード数が閾値Thres未満である場合は、Ｎの値がインクリメントされて時系列情報が再度取得されるようにしてもよい。
【０４３７】
ステップＳ２０７において、認識器３５は、時系列情報の最後の時刻におけるノードは、既知ノードであると認識する。このとき、時系列情報の最後の時刻におけるノードのインデックスが出力されるようにしてもよい。また、ステップＳ２０７の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【０４３８】
このようにしてノード認識処理が実行される。
【０４３９】
ところで、図３３の処理において、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるものとすると説明したが、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することはできない。既知ノードから遷移した未知ノードを含むノード列に基づいて、正確な認識結果を得ることはできないからである。
【０４４０】
従って、時系列情報に対応するノード列の中に、既知ノードから遷移した未知ノードが含まれるようにすることはできず、時系列情報の長さＮの値に上限があることになる。なお、当該ノードが既知ノードから遷移した未知ノードであるか否かは、認識結果バッファ３８に記憶された情報に基づいて判断することができる。
【０４４１】
次に、図３４のフローチャートを参照して、時系列情報の長さＮの値に上限があることを考慮した場合のノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第２の方式の例となる処理である。
【０４４２】
ステップＳ２２１乃至ステップＳ２２９の処理は、図３３のステップＳ２０１乃至ステップＳ２０９の処理と同様のものなので、詳細な説明は省略する。
【０４４３】
図３４の例の場合、ステップＳ２２９の処理で変数Ｎの値が１だけインクリメントされると、ステップＳ２３０において、ノード列に既知ノードから遷移した未知ノードが含まれることになるか否かが判定される。すなわち、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるが、ノード列を過去方向に延長すると既知ノードから遷移した未知ノードが含まれることになるか否かが判定されるのである。つまり、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することができないようにされるのである。
【０４４４】
ステップＳ２３０において、既知ノードから遷移した未知ノードが含まれることになると判定された場合、処理は、ステップＳ２３１に進む。ステップＳ２３０において、既知ノードから遷移した未知ノードが含まれることにはならないと判定された場合、処理は、ステップＳ２２２に戻る。
【０４４５】
ステップＳ２３１において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行させるように制御情報を出力する。
【０４４６】
すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積するように指令を出力するのである。
【０４４７】
認識処理は、図３４に示されるように実行されるようにしてもよい。
【０４４８】
ところで、図３３と図３４を参照して上述した処理においては、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすかによって、実際にあり得るノード列であるか否かが判定されると説明した。しかし、認識された現在の状態確率のエントロピーの値の変化に基づいて実際にあり得るノード列であるか否かが判定されるようにすることも可能である。
【０４４９】
すなわち、長さＮの時系列情報に基づいて式（４８）により演算されるエントロピーをＥNとし、長さＮ−１の時系列情報に基づいて式（４８）により演算されるエントロピーをＥN-1とし、△Ｅ＝ＥN−ＥN-1を演算する。そして、△Ｅを所定の閾値Thresentと比較し、その比較処理の繰り返し回数を閾値Thresstableと比較し、それらの比較結果に基づいてノードが認識されるようにしてもよい。
【０４５０】
例えば、△Ｅ＜Thresentを満たさない場合、時系列情報が過去方向に延長されるようにし、さらにエントロピーが計算されて△Ｅ＜Thresentを満たすか否かが判定される。△Ｅ＜Thresentを満たす場合、カウンタＮＣがカウントアップされ、ＮＣ＞Thresstableを満たすとき、ノードの認識が行なわれることになる。
【０４５１】
次に、図３５のフローチャートを参照して、状態確率のエントロピーの値の変化に基づく認識を行なう場合のノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第３の方式の例となる処理である。
【０４５２】
ステップＳ２５１において、認識器３５は、変数Ｎの値を初期値である１にセットする。
【０４５３】
ステップＳ２５２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。
【０４５４】
ステップＳ２５３において、認識器３５は、ステップＳ２０２で出力された時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力する。
【０４５５】
ステップＳ２５４において、認識器３５は、エントロピーの差分を演算する。このとき、上述したように、長さＮの時系列情報に基づいて式（４８）により演算されるエントロピーをＥNとし、長さＮ−１の時系列情報に基づいて式（４８）により演算されるエントロピーをＥN-1とし、△Ｅ＝ＥN−ＥN-1を演算する。なお、ステップＳ２５４の演算は、Ｎの値が２以上となったときに実行されるものとする。
【０４５６】
ステップＳ２５５において、認識器３５は、ステップＳ２５４で演算したエントロピーの差分は、閾値Thresent以上であるか否かを判定する。ステップＳ２５５において、ステップＳ２５４で演算したエントロピーの差分は、閾値以上ではないと判定された場合、処理は、ステップＳ２５６に進む。
【０４５７】
ステップＳ２５６において、認識器３５は、カウンタＮＣの値を１だけインクリメントする。
【０４５８】
ステップＳ２５７において、認識器３５は、カウンタＮＣの値が閾値Thresstable以上であるか否かを判定する。ステップＳ２５７において、カウンタＮＣの値が閾値Thresstable以上であると判定された場合、処理は、ステップＳ２５８に進む。
【０４５９】
ステップＳ２５８において、認識器３５は、ステップＳ２５３の処理の結果、出力されたノード列が実際にあり得るノード列であるか否かを判定する。このとき、上述したように、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かが判定される。ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たす場合、ステップＳ２５８では、実際にあり得るノード列であると判定される。一方、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）の少なくとも一方を満たさない場合、ステップＳ２５８では、実際にあり得るノード列ではないと判定される。
【０４６０】
ステップＳ２５８において、出力されたノード列が実際にあり得るノード列ではないと判定された場合、処理は、ステップＳ２６２に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、未知ノードであると認識する。ステップＳ２６２の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【０４６１】
一方、ステップＳ２５８において、出力されたノード列が実際にあり得るノード列であると判定された場合、処理は、ステップＳ２５９に進む。
【０４６２】
ステップＳ２５９において、認識器３５は、エントロピーを計算する。このとき上述したように、式（４８）によりエントロピーが演算される。
【０４６３】
ステップＳ２６０において、認識器３５は、ステップＳ２５９の処理で演算されたエントロピーの値を所定の閾値と比較し、エントロピーの値が閾値以上であるか否かを判定する。
【０４６４】
ステップＳ２６０において、エントロピーの値が閾値以上であると判定された場合、処理は、ステップＳ２６３に進む。
【０４６５】
ステップＳ２６３において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行するように制御情報を出力する。
【０４６６】
すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積するように指令を出力するのである。
【０４６７】
一方、ステップＳ２６０において、エントロピーの値が閾値以上ではないと判定された場合、処理は、ステップＳ２６１に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、既知ノードであると認識する。
【０４６８】
ステップＳ２６１の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。
【０４６９】
また、ステップＳ２５８において、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かがさらに判定され、Thres以上である場合にのみ、処理は、ステップＳ２５９またはステップＳ２６２に進むようにしてもよい。この場合、ステップＳ２５８において、出力されたノード列に含まれる固有ノード数が閾値Thres以上ではないと判定されたときは、処理は、ステップＳ２６５に進むようにすればよい。すなわち、変数Ｎの値が１だけインクリメントされるようにすればよい。
【０４７０】
また、ステップＳ２５５で、ステップＳ２５４で演算したエントロピーの差分は、閾値Thresent以上であると判定された場合、処理は、ステップＳ２６４に進み、カウンタＮＣの値が０に設定される。
【０４７１】
ステップＳ２６４の処理の後、または、ステップＳ２５７でカウンタＮＣの値が閾値Thresstable以上ではないと判定された場合、処理は、ステップＳ２６５に進む。
【０４７２】
ステップＳ２６５において、認識器３５は、変数Ｎの値を１だけインクリメントする。これにより、その後実行されるステップＳ２０２の処理において、長さがＮ＋１の時系列情報が取得されることになる。なお、ステップＳ２６５において変数Ｎの値をインクリメントする毎に、ステップＳ２５２で取得される時系列情報は、過去方向に延長されるものとする。
【０４７３】
このように、ステップＳ２５５でエントロピーの差分は、閾値Thresent以上ではないと判定され、かつ、ステップＳ２５７でカウンタＮＣの値が閾値Thresstable以上であると判定されるまで、ステップＳ２５２乃至ステップＳ２５７、およびステップＳ２６５の処理が繰り返し実行される。
【０４７４】
このようにしてノード認識処理が実行される。図３５の例の場合、ステップＳ２５５とステップＳ２５７の処理により、エントロピーの値が収束したことが確認され、その後、出力されたノード列が実際にあり得るノード列であるかが判定されるようにした。従って、例えば、図３３を参照して上述した場合と比較して、より確実な認識を行なうことが可能となる。
【０４７５】
また、図３５の処理の場合も、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することはできない。既知ノードから遷移した未知ノードを含むノード列に基づいて、正確な認識結果を得ることはできないからである。。
【０４７６】
従って、時系列情報に対応するノード列の中に、既知ノードから遷移した未知ノードであると認識されたノードが含まれるようにすることはできず、時系列情報の長さＮの値に上限があることになる。なお、当該ノードが既知ノードから遷移した未知ノードであるか否かは、認識結果バッファ３８に記憶された情報に基づいて判断することができる。
【０４７７】
次に、図３６のフローチャートを参照して、状態確率のエントロピーの値の変化に基づく認識を行なう場合、時系列情報の長さＮの値に上限があることを考慮するときのノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第４の方式の例となる処理である。
【０４７８】
ステップＳ２８１乃至ステップＳ２９５の処理は、図３５のステップＳ２５１乃至ステップＳ２６５の処理と同様のものなので、詳細な説明は省略する。
【０４７９】
図３６の例の場合、ステップＳ２９５の処理で変数Ｎの値が１だけインクリメントされると、ステップＳ２９６において、ノード列に既知ノードから遷移した未知ノードが含まれることになるか否かが判定される。すなわち、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるが、ノード列を過去方向に延長すると既知ノードから遷移した未知ノードが含まれることになるか否かが判定されるのである。
【０４８０】
ステップＳ２９６において、既知ノードから遷移した未知ノードが含まれることになると判定された場合、処理は、ステップＳ２９３に進む。ステップＳ２９６において、既知ノードから遷移した未知ノードが含まれることにはならないと判定された場合、処理は、ステップＳ２８２に戻る。
【０４８１】
ステップＳ２９３において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行するように制御情報を出力する。
【０４８２】
すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積されるように指令を出力するのである。
【０４８３】
認識処理は、図３６に示されるように実行されるようにしてもよい。
【０４８４】
図３３乃至図３６を参照して上述した４通りの方式により、ロボットは、自分が新たに追加された迷路のパーツ上（未知ノード）に位置しているのか、または以前から存在していたパーツ上（既知ノード）にいるのかを認識することができる。このようにして認識された未知ノードに関する状態遷移確率と観測確率を設定し、状態遷移確率テーブル、および観測確率テーブルを拡張する。
【０４８５】
なお、ここでは、アクション拡張型ＨＭＭによる認識を行なう場合の例について説明したが、図３３乃至図３６の認識処理は、通常のＨＭＭの認識においても適用することができる。
【０４８６】
ところで、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合、どの時点でどれだけの未知ノードを、新たに状態遷移確率テーブル、および観測確率テーブルなどに含めるかが問題となる。次に、自律的に環境の変化を認識して、未知ノードを内部モデルデータに追加する場合における追加すべき未知ノードの個数および追加すべきタイミングについて説明する。
【０４８７】
なお、ここでいう未知ノードの内部モデルデータへの追加とは、未知ノードとみなされたノードを表す新たなインデックスを生成し、例えば、そのインデックスに対応する行列を状態遷移確率テーブルなどに追加することを意味する。
【０４８８】
図３３乃至図３６を参照して上述した方式により、自分が新たに追加されるべきノード（未知ノード）に位置していると認識した時刻から経過した時間をＮとする。この時間Ｎは、時系列情報の長さと言い換えることもできる。また、ここでは認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値Thresを設けることにする。
【０４８９】
まず、長さＮの時系列情報に含まれる固有ノード数がThresの値になるまで、エージェントは行動を繰り返す。すなわち、行動生成器３６と行動出力部３２とにより、Ｎ回のアクションが実行され、観測バッファ３３、および行動出力バッファ３９に、長さＮの時系列情報が蓄積されることになる。なお、ここでいう長さＮの時系列情報は、自分が未知ノードに位置していると認識した時刻後の時間的長さＮの時系列情報を意味する。また、以下において適宜、「長さＮの時系列情報に基づいて認識された長さＬｒのノード列に含まれる固有ノード数がThresの値になる」という意味で「ＬｒがThresの値になる」と表現することにする。
【０４９０】
そして、ＬｒがThres以上になった場合、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この場合、時系列情報の長さの上限Ｎがあることになる。
【０４９１】
ここで実行される認識処理における図３４のステップＳ２２３または図３６のステップＳ２８３で出力されるノード列をＳとし、そのノード列の長さをＬrとする。
【０４９２】
そして、図３４のステップＳ２２８または図３６のステップＳ２９２で未知ノードであると認識された場合、そのノードが未知ノードとみなされて、学習器３４により内部モデルデータに追加するようにする。
【０４９３】
実際に未知になってから足したノードの数をｍ_addとすると、追加する未知ノードの数をｍは、式（４９）により表すことができる。
【０４９４】
【数４９】
2011018245.tif 000051
・・・（４９）
【０４９５】
なお、ｍ_addは、自分が未知ノードに位置していると最初に認識したときから、既に未知ノードの追加が行なわれた場合、それら追加されたノードの個数を表す数とされる。すなわち、式（４９）は、未知ノードに位置していると認識された後、未知ノードとみなして追加したノードの数はひいた上で、最初に認識した未知ノードに至るまでの間のノードを足すことを示している。
【０４９６】
また、式（４９）の右辺において加算される「1」は、長さＬrのノード列の最も過去の時刻に対応するノードを、どのノードに接続するかが現時点では決められないため、保留するということを示す。
【０４９７】
図３７を参照してさらに詳細に説明する。図３７は、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。
【０４９８】
さらに、説明を簡単にするため、アクションを１回実行すると図中の円により示されたノードの数と時系列情報の長さが１だけ増加するものとし、それらのノードは、特に説明がない限り、全て固有ノードであると認識されたものとする。
【０４９９】
同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２１１は、未知ノードであると認識されたものとする。
【０５００】
その後、さらに１のアクションが実行され、エージェントは、ノード２１２に遷移する。このとき、ノード２０２乃至ノード２１２に対応する長さＬｒの時系列情報に基づく認識処理が実行され、ノード２１２は未知ノードと認識されたものとする。この時点では、まだ未知ノードの追加は行なわれない。
【０５０１】
その後、さらに１のアクションが実行され、エージェントがノード２１３に遷移する。このとき、ノード２０３乃至ノード２１３に対応する長さＬｒの時系列情報に基づく認識処理が実行され、ノード２１３は未知ノードと認識されたものとする。この時点でノード２０１の追加が行なわれる。
【０５０２】
これにより、それ以後の認識処理においては、ノード２０１が既知ノードとして取り扱われることになる。
【０５０３】
いまの場合、時系列情報の長さ（自分が未知ノードに位置していると認識した時刻後の時間的長さ）Ｎは、Thres＋２である。また、いまの場合、ノード２０３乃至ノード２１３がノード列Ｓに対応し、ノード列Ｓの長さＬrは、Thresである。よって、式（４９）より、追加すべきノードの個数ｍは、Thres＋２-（Thres＋０＋１）＝１と算出される。従って、未知ノードであった１個のノード２０１が新たに追加されたのである。
【０５０４】
すなわち、内部モデルデータの状態遷移確率テーブルなどに、ノード２０１を表す新たなインデックスの行列が追加されるのである。
【０５０５】
なお、上述した例において、ノード２１１乃至ノード２１３は、いずれも未知ノードであると認識されているが、ノード２０１が真の意味で未知ノードであったか否かは不明である。例えば、ノード２１１が未知ノードと判定されたのは、ノード２０１乃至ノード２１１のノード列が、実際にあり得るノード列ではないと判定された結果であり、必ずしもノード２１１が既存の内部モデルデータに存在しないノードであるとは限らないからである。つまり、ノード２０１乃至ノード２１１のノードのいずれかが既存の内部モデルデータに存在しないノードであれば、ノード２１１は、未知ノードと認識されるのである。
【０５０６】
従って、現時点でノード２０１を未知ノードとみなして内部モデルデータの状態遷移確率テーブルなどに、ノード２０１を表す新たなインデックスの行列が追加しても、実際には既存のインデックスの行列と重複する結果にもなり得る。このように、ノード２０１が真の意味で未知ノードであったか否かは不明なのである。
【０５０７】
なお、ここでは、図３７を参照して説明する都合上、ノード２０１が真の意味で未知ノードであったか否かは不明と説明しているが、図３７の例では、ノード２０１は真の意味で未知ノードであったことが前提とされる。従って、本来は、その後に追加される「ノード２０２、ノード２０３、・・・が真の意味で未知ノードであったか否かは不明なものとなる」という説明が適切である。
【０５０８】
上述のように、ノード２０１が真の意味で未知ノードであったか否かは不明であるとしても、既存のインデックスの行列と重複する可能性を過度に懸念して、ノード２０１を表す新たなインデックスを内部モデルデータに追加しないとすると、問題がある。エージェントの状況によっては、永遠に学習が完了しないことになるからである。
【０５０９】
例えば、環境である迷路が拡張され、新たな迷路の部屋ができ、エージェントであるロボットが、新たな迷路の部屋に閉じ込められた場合、追加するノードが真の意味で未知ノードであったと確信できなくても、やはり追加せざるを得ない。
【０５１０】
このため、自分が未知ノードに位置していると最初に認識したときから、所定の時間経過後のタイミングで、所定の個数のノードを、内部モデルデータに追加する必要があるのである。
【０５１１】
説明を図３７に戻す。ノード２０１が内部モデルデータに追加された後、さらにアクションが実行され、時系列情報に基づいて認識処理が実行されていく。ノード２１２乃至ノード２２１に対応する時系列情報に基づく認識処理が実行された結果、ノード２２１が既知ノードであると認識された場合、ノード２１２乃至ノード２２１は、全て既知ノードであったことになる。このとき、ノード２１１が追加されるとともに、ノード２１１からノード２１２へのアンカリングが行われる。アンカリングは、未知ノードから既知ノードへの遷移が認識された場合、未知ノードと既知ノードとの状態遷移確率などを設定する処理である。なお、アンカリングの詳細については後述する。
【０５１２】
ところで、図３４、または図３６を参照して上述した認識処理においては、ステップＳ２３１またはステップＳ２９３において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力される場合がある。このような場合、時系列情報の長さThresでは適切な認識を行なうことができないので、時系列情報の長さを未来方向に延長する必要がある。
【０５１３】
認識処理において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力された場合の例について、図３８を参照してさらに詳細に説明する。図３８では、図３７と同様に、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。
【０５１４】
同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２０１乃至ノード２１１は、全て未知ノードであると認識されたものとする。また、この例では、ノード２０１乃至ノード２１１が内部モデルデータに追加されたものとする。
【０５１５】
これにより、それ以後の認識処理においては、ノード２０１乃至ノード２１１が既知ノードとして取り扱われることになる。
【０５１６】
エージェントがノード２２１に遷移したとき、長さＬｒの時系列情報に基づいて認識処理が実行され、この時点では、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたものとする。すなわち、この時点では、ノード列を一意に認識することができず、仮に認識したとしても複数の候補が存在する状態となっている。
【０５１７】
このような場合、閾値Thresの値が１だけインクリメントされ、新たに１のアクションが実行され、認識処理の対象となる時系列情報の長さも１だけインクリメントされる。これにより、エージェントは、ノード２２２に遷移したものとする。この時点で、長さThres＋１の時系列情報に基づいて認識処理を実行し、長さＬｒ（＝Thres＋１）のノード列を得たが、この時点でも、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたものとする。
【０５１８】
そして、閾値Thresの値がインクリメントされ、さらにアクションが実行されることにより、エージェントは、ノード２３１に遷移したものとする。この時点で、長さThres＋qの時系列情報に基づいて認識処理を実行することにより、ノード２３１が既知ノードであると認識されたものとする。
【０５１９】
ノード２３１が既知ノードであると認識された場合、ノード２１３乃至ノード２３１は、全て既知ノードであったことになる。このとき、ノード２１２が追加されるとともに、ノード２１２からノード２１３へのアンカリングが行われる。
【０５２０】
ただし、上述したように、未知ノードとみなされて追加されたノードの中に、実際には既知ノードであるノードが含まれることがある。また、例えば、エージェントが実際には同じノードに繰り返し遷移している場合（例えば、２つのノード間を往復している場合）でも、それらが異なる未知ノードと認識される場合がある。
【０５２１】
このように、本来未知ノードとは言えないノードが未知ノードとみなされて、それらの未知ノードが内部モデルデータに追加されることを抑止するために、例えば、アンカリングする際にノードの追加または削除の要否のチェックが行なわれる。
【０５２２】
アンカリングする際にノードの追加または削除の要否のチェックが行なわれる場合の例について、図３９を参照してさらに詳細に説明する。図３９では、図３７と同様に、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。
【０５２３】
同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２０１乃至ノード２１１は、全て未知ノードであると認識されたものとする。
【０５２４】
その後、さらに１のアクションが実行され、エージェントは、ノード２１２に遷移するが、この時点では、まだ未知ノードの追加は行なわれない。
【０５２５】
その後、さらに１のアクションが実行され、エージェントがノード２１３に遷移すると、ノード２０１の追加が行なわれる。
【０５２６】
このようにして、アクションが実行され、エージェントはノード２１５に遷移したものとする。また、このとき、ノード２０１乃至ノード２０３の追加が既に行なわれていたものとする。この時点で、ノード２０１乃至ノード２０３は、未知ノードとみなされて追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されているものとする。その後、ノード２０５乃至ノード２１５に対応する時系列情報に基づく認識処理が実行された結果、ノード２１５が既知ノードであると認識された場合、ノード２０５乃至ノード２１５は、全て既知ノードであったことになる。
【０５２７】
このとき、ノードの削除の要否のチェックが行なわれる。すなわち、時系列情報の長さが過去方向に延長され、延長された時系列情報に基づく認識処理が実行される。その結果、例えば、ノード２０３乃至ノード２１５に対応する時系列情報に基づく認識処理が実行され、その結果、ノード２０３乃至ノード２１５が全て既知ノードであったと認識されたものとする。すなわち、ノード２０３は、未知ノードとみなされて追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されていたが、本来は、既知ノードであって、追加したインデックスのノードは、内部モデルデータから削除すべきである。
【０５２８】
例えば、ノード２０３とノード２０５、実際には同じインデックスのノードであり、また、ノード２０４とノード２０６は、実際には同じインデックスのノードであった場合、上述のように認識されることになる。
【０５２９】
例えば、ノード２０３のインデックスをｕとして状態遷移確率テーブルなどに新たな行列を追加したが、ノードの削除の要否のチェックが行なわれた結果、ノード２０３のインデックスは、ｆであることが判明したとする。インデックスｆに対応する行列は、エージェントがノード２０１に遷移する以前から状態遷移確率テーブルなどに存在していたものとする。この場合、インデックスｕに対応する行列とインデックスｆに対応する行列が重複して存在することになるので、インデックスｕに対応する行列は、状態遷移確率テーブルなどから削除しておく必要がある。
【０５３０】
その結果、ノード２０３のインデックスとして新たに追加されたインデックスｕに対応する行列などが内部モデルデータから削除され、ノード２０２から既知ノードとして認識されたノード２０３へのアンカリングが行われる。
【０５３１】
例えば、上述の例において、ノード２０２のインデックスをｔとして状態遷移確率テーブルなどに新たな行列を追加していた場合、インデックスｔのノードからインデックスｆのノードへの状態遷移確率などが、アンカリングによって設定されることになる。
【０５３２】
なお、アンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようになされている。すなわち、アンカリングされた直後の内部モデルデータを初期値とし、図３９におけるノード２０１乃至ノード２１５、およびノード２０１の左側の１つのノードに対応する時系列情報に基づく学習が行われることになる。
【０５３３】
上述したように、アンカリングは、未知ノードから既知ノードへの遷移が認識された場合、未知ノードと既知ノードとの状態遷移確率などを設定する処理である。本発明では、アンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようにする。
【０５３４】
すなわち、未知ノードが追加された後の内部モデルデータに基づいて、追加学習方式の学習が行われる。仮に、実際には同じインデックスのノードが異なる未知ノードとして重複して追加されたとしても、この学習によって、上述したフォワードマージアルゴリズムおよびバックワードマージアルゴリズムが適用されて同一のノードとしてマージされる可能性が高くなる。
【０５３５】
また、追加学習方式での学習を、アンカリングが行なわれるまで実行しないようにすることで、内部モデルデータにおいて更新すべきパラメータの数をできるだけ少なくすることができる。アンカリングの際にノードの削除の要否のチェックが行なわれるからである。従って、計算量を抑制しながら、適切に内部モデルデータを更新していくことが可能となるのである。
【０５３６】
このように、アンカリングの際に、ノードの削除の要否のチェックが行なわれる場合、追加する未知ノードの数ｍは、式（４９）に替えて式（５０）より表すことができる。
【０５３７】
【数５０】
2011018245.tif 000052
・・・（５０）
【０５３８】
いまの場合、時系列情報の長さ（自分が未知ノードに位置していると認識した時刻後の時間的長さ）Ｎは、１１である。また、いまの場合、ノード２０３乃至ノード２１５がノード列Ｓに対応し、ノード列Ｓの長さＬrは、Thres＋２である。よって、式（５０）より、追加すべきノードの個数ｍは、Thres＋４-（Thres＋２＋３）＝−１と算出される。従って、既に追加された３つのノードのうちの１個のノード２０３（のインデックスに対応する行列）が削除されるのである。
【０５３９】
ここでは、ノードが削除される場合の例のみを説明したが、ｍ_addの値の如何によっては、ノードが追加される場合もあり得る。すなわち、式（５０）または後述する式（５１）により計算されたｍが正の値となれば、その分のノードが追加されることになる。従って、実際には、アンカリングの際に、ノードの追加または削除の要否のチェックが行なわれることになる。
【０５４０】
なお、削除すべきノードが認識処理の結果、既知ノードと認識されてしまう場合、そのノードの削除は行なわれない。
【０５４１】
仮に、既に未知ノードとみなして追加したノードのうちＫ個目のノードが、認識処理で出力されたノード列Ｓに含まれていた場合、削除するノードの数ｍは、式（５０）に替えて式（５１）より表すことができる。
【０５４２】
【数５１】
2011018245.tif 000053
・・・（５１）
【０５４３】
式（５１）により算出された|ｍ|個のノードが削除するノードとなる。
【０５４４】
また、この場合、アンカリングするノードは、ノード列Ｓの中の（（Ｌｒ＋Ｋ）−Ｎ）番目のノードとなる。
【０５４５】
このようにアンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようになされている。また、アンカリングが行なわれるまでは、追加学習方式での学習を実行しないようになされている。従って、アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードは、それ以後の認識処理において既知ノードの１つとして認識されるものの、いわば仮の既知ノードとして認識されていることになる。アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードは、最終的には削除すべきものである可能性があるからである。また、アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードと、他のノードとの状態遷移確率などの値は、追加学習方式での学習により変更される可能性があるからである。
【０５４６】
ところで、追加するノードが真の意味で未知ノードであったと確信できなくても、自分が未知ノードに位置していると最初に認識したときから、所定の時間経過後のタイミングで、所定の個数のノードを、内部モデルデータに追加せざるを得ないことについては上述した。つまり、アンカリングする前の内部モデルデータには、単に未知ノードとみなされたノードを表すインデックスに対応する情報も追加されている可能性が極めて高いといえる。
【０５４７】
しかし、真の意味で未知ノードであったと確信できない極めて多数のノードが、それぞれ一様に未知ノードとみなされて内部モデルデータに追加されていくと、認識処理における誤認識を招くことがある。未知ノードとみなされて追加されたノードも、それ以後の認識処理においては既知ノードとして取り扱われることになるからである。
【０５４８】
その結果、例えば、以前から存在していた既知ノードが、未知ノードとみされて追加されたノードであると、誤って認識されてしまうことがある。認識処理は、内部モデルデータに基づいて行なわれるからである。
【０５４９】
このような誤認識を抑制するために、アンカリングする前に、未知ノードとみなして追加してしまったノードを適宜削除するようにしてもよい。この場合、式（４９）に示したｍの値が０よりも小さくなったとき、|ｍ|個のノードを削除するようにすればよい。
【０５５０】
例えば、固有ノード数の閾値Thresの値が７であった場合を考える。例えば、ノード２１６（図示せず）が、自分が未知ノードに位置していると最初に認識したノードであったものとし、いま、エージェントはノード２２６（図示せず）に遷移したものとする。ここで、ノード２１６は、既に内部モデルデータに追加されているものとする。
【０５５１】
ノード２１９乃至ノード２２６に対応する時系列情報に基づいて認識処理を行った結果、ノード２２６は未知ノードであると認識されたものとする。このとき、ノード２１７が内部モデルデータに追加されることになる。
【０５５２】
その後、アクションを実行することにより、エージェントはノード２２７（図示せず）に遷移し、この時点での認識処理の結果、ノード２２７は未知ノードであると認識されたものとする。このとき、ノード２１８が内部モデルデータに追加されることになる。しかし、ノード２１８が内部モデルデータに追加された結果、ノード２２０、ノード２２２、ノード２２４、およびノード２２６は、実際には、ノード２１８と同じインデックスのノードであることが認識されたこととする。
【０５５３】
この場合、閾値Thres以上の固有ノード数を含むノード列を出力させるためには、時系列情報の長さを、ノード２１７乃至ノード２２７に対応する長さとしなければならない。
【０５５４】
このような場合、時系列情報の長さ（ノード２１６乃至ノード２２７）Ｎは１２であり、既に追加したノード（ノード２１６乃至ノード２１８）の数ｍ_addは３である。また、いまの場合、ノード２１７乃至ノード２２７がノード列Ｓに対応し、ノード列Ｓの長さＬrは１１である。よって、式（４９）より、追加すべきノードの個数ｍは、１２−（１１＋３＋１）＝−３と算出される。従って、内部モデルデータに追加された３つノードであって、ノード２１６乃至ノード２１８が削除されるのである。
【０５５５】
このようにして、アンカリングする前に、未知ノードとみなして追加してしまったノードを必要に応じて削除すれば、誤認識を抑制することが可能となる。
【０５５６】
すなわち、アンカリングする前に、未知ノードを追加したり、未知ノードとみなして追加してしまったノードを必要に応じて削除したりする処理が行われる。この処理は、後述する図４０のステップＳ３１６に対応する。
【０５５７】
また、アンカリングする際にも、未知ノードを追加したり、未知ノードとみなして追加してしまったノードを必要に応じて削除したりする処理が行われる。この処理は、後述する図４０のステップＳ３１８に対応する。
【０５５８】
次に、図４０のフローチャートを参照して、未知ノード追加処理について説明する。この処理は、エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張する必要がある場合、自律行動学習装置１０により実行される。
【０５５９】
ステップＳ３１１において、認識器３５は、変数Ｎの値を初期値である１にセットする。
【０５６０】
ステップＳ３１２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。
【０５６１】
ステップＳ３１３において、認識器３５は、Ｎが固有ノード数の閾値Thres以上となったか否かを判定し、まだ、閾値Thres以上となっていないと判定された場合、処理は、ステップＳ３２１に進む。
【０５６２】
ステップ３２１において、変数Ｎの値が１だけインクリメントされ、処理は、ステップＳ３１２に戻る。
【０５６３】
一方、ステップＳ３１３において、Ｎが閾値Thres以上となったと判定された場合、処理は、ステップＳ３１４に進む。
【０５６４】
ステップＳ３１４において、認識器３５は、図３４、または図３６を参照して上述した認識処理を実行する。ただし、いまの場合、ステップＳ３１２の処理で時系列情報が取得されているので、その時系列情報に基づいて認識処理が実行される。
【０５６５】
ステップＳ３１５において、学習器３４は、ステップＳ３１４における認識処理の結果、ノード列の最後のノードが未知ノードと認識されたか否かを判定する。ステップＳ３１５において、認識処理の結果、未知ノードと認識されたと判定された場合、処理は、ステップＳ３１６に進む。
【０５６６】
ステップＳ３１６において、学習器３４は、未知ノードとみなされたノードを追加または削除する。
【０５６７】
ステップＳ３１６では、例えば、図３７において未知ノードとみなされたノード２０１が内部モデルデータに追加されたように、ノードの追加が行なわれる。また、例えば、上述したように、誤認識を抑制するために、アンカリング前に、未知ノードとみなして追加してしまったノードの削除が行なわれる。
【０５６８】
一方、ステップＳ３１５において、認識処理の結果、未知ノードと認識されていないと判定された場合、処理は、ステップＳ３１７に進む。
【０５６９】
ステップＳ３１７において、学習器３４は、ステップＳ３１４における認識処理の結果、ノード列の最後のノードが既知ノードと認識されたか否かを判定する。ステップＳ３１７において、認識処理の結果、既知ノードと認識されたと判定された場合、処理は、ステップＳ３１８に進む。
【０５７０】
ステップＳ３１８において、学習器３４および認識器３５は、図４１を参照して後述する追加または削除要否チェック処理を実行する。これにより、例えば、図３９を参照して上述したように、アンカリングの際のノードの削除要否がチェックされ、削除が必要であれば未知ノードとみなされて追加されたノードが削除される。
【０５７１】
ステップＳ３１９において、学習器３４は、アンカリングを行なう。これにより、例えば、既知ノードから未知ノードへの状態遷移確率などが設定される。
【０５７２】
一方、ステップＳ３１７において、認識処理の結果、既知ノードと認識されていないと判定された場合、処理は、ステップＳ３２０に進む。
【０５７３】
ステップＳ３２０において、認識器３５は、閾値Thresの値を１だけインクリメントする。
【０５７４】
すなわち、ステップＳ３１７において、認識処理の結果、既知ノードと認識されていないと判定された場合、認識処理において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたことになる。例えば、図３４、または図３６を参照して上述したステップＳ２３１の処理またはステップＳ２９３の処理が行われる場合である。この場合、例えば、図３８を参照して上述したように、閾値Thresの値をインクリメントするとともに、時系列情報の長さを未来方向に延長する必要がある。
【０５７５】
従って、ステップＳ３２０の処理の後、処理は、ステップＳ３２１に進むことになる。
【０５７６】
このようにして、未知ノード追加処理が実行される。
【０５７７】
次に、図４１のフローチャートを参照して、図４０のステップＳ３１８の追加または削除要否チェック処理の詳細な例について説明する。
【０５７８】
ステップＳ３４１において、認識器３５は、長さＮの時系列情報を取得する。すなわち、自分が未知ノードに位置していると認識した時刻後の時間的長さＮの時系列情報が取得される。例えば、図３９の例の場合、ノード２０１乃至ノード２１５に対応する長さの時系列情報が取得されることになる。
【０５７９】
ステップＳ３４２において、認識器３５は、長さＮの時系列情報に基づく認識処理を実行する。このとき、図３４、または図３６を参照して上述した認識処理を実行する。ただし、いまの場合、ステップＳ３４１の処理で時系列情報が取得されているので、その時系列情報に基づいて認識処理が実行される。
【０５８０】
ステップＳ３４３において、学習器３４は、ステップＳ３４２における認識処理の結果、ノード列の最後のノード（時間的に最も後のノード）が既知ノードと認識されたか否かを判定する。ステップＳ３４３において、認識処理の結果、既知ノードと認識されていないと判定された場合、処理は、ステップＳ３４４に進む。
【０５８１】
ステップＳ３４４において、認識器３５は、時系列情報の長さＮを１だけデクリメントする。この場合、時系列情報が過去側から短縮されることになる。例えば、例えば、図３９の例の場合、ノード２０１乃至ノード２１５に対応する長さの時系列情報が取得されていたものが、ノード２０２乃至ノード２１５に対応する長さの時系列情報とされることになる。
【０５８２】
このように、ステップＳ３４３において、認識処理の結果、既知ノードと認識されたと判定されるまで、時系列情報が過去側から短縮され、繰り返し認識処理が実行されるのである。
【０５８３】
ステップＳ３４３において、認識処理の結果、既知ノードと認識されたと判定された場合、処理は、ステップＳ３４５に進む。例えば、図３９の例の場合、ノード２０３乃至ノード２１５に対応する長さの時系列情報に基づく認識処理の結果、ノード２０３乃至ノード２１５が全て既知ノードであったと認識される。このとき、ノード２０３乃至ノード２１５のノード列におけるノード数が特定される。
【０５８４】
ステップＳ３４５において、学習器３４は、ノード数を特定し、特定されたノード数をノード列Ｓの長さＬrとして、式（５０）を参照して上述した演算を行う。
【０５８５】
ステップＳ３４６において、学習器３４は、追加（または削除）すべきノードがあるか否かを判定する。ステップＳ３４６において、追加（または削除）すべきノードがあると判定された場合、処理は、ステップＳ３４７に進む。一方、ステップＳ３４６において、追加（または削除）すべきノードがないと判定された場合、ステップＳ３４７の処理は、スキップされる。
【０５８６】
ステップＳ３４７において、学習器３４は、ステップＳ３４６の処理で追加（または削除）すべきと判定されたノードを追加（または削除）する。例えば、図３９の例の場合、式（５０）より、追加すべきノードの個数ｍは、Thres＋４-（Thres＋２＋３）＝−１と算出されるので、既に追加された３つのノードのうちの１個のノード２０３が削除される。すなわち、ノード２０３は、未知ノードとして追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されていたが、本来は、既知ノードであって、追加したインデックスのノードは、内部モデルデータから削除されるのである。
【０５８７】
このようにして、追加または削除要否チェック処理が実行される。
【０５８８】
これまでに学習して得られた内部モデルデータでは表現できない、新しい状況に遭遇したときには、ノード数を増やして状況を表現し、事態を解決する必要がある。例えば、ロボットが移動する迷路が所定の方向に延長された場合、ノードの数が増えることになるので、ノード数Ｎの値を大きくする必要がある。
【０５８９】
従来の技術では、新たなノードを検出すると、その場で直ちに内部モデルデータを拡張し、新たなノードを表すインデックスの追加が行なわれていた。
【０５９０】
しかしながら、一般に新しい経験を取り込む際、その経験は既存の構造とどのような関係に位置づけられるのかが最重要な問題となり、例えば、新たなノードを検出した直後では既存構造との関係が十分明確でないことも多い。
【０５９１】
従って、早急に新たなノードを表すインデックス内部モデルデータに追加することにより、今後の誤認識を招くおそれもある。例えば、新たなノードが連続して検出されるような状況では、新たなノードは直前の状態に対してしか関係性を定義できず、そのような連鎖が連続すればするほど、加速度的に既存構造に対する関係の不明瞭化が進むことになる。また、このような内部モデルデータに基づいて追加学習方式で学習を行ったとしても、学習時に調整すべきパラメータが膨大になってしまう。
【０５９２】
そこで、本発明では、上述のように、所定のタイミングで所定の個数の未知ノードが追加されるようにするとともに、アンカリングされた直後の内部モデルデータに基づいて追加学習方式での学習が行われるようにしたのである。このようにすることで、例えば、既知ノードの中に散発的に新たなノードが発現するような場合はもちろんのこと、長期に渡って新たなノードが連続して検出されるような困難な環境においても、十分に有効な学習を行うことが可能となる。
【０５９３】
上述のように、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張することが可能であるが、その際、それぞれのテーブルの拡張された領域に設定すべき状態遷移確率、観測確率などの値を特定する必要がある。
【０５９４】
図３０乃至図３２において各テーブルを拡張する場合の例については説明したが、ここでは、既に記憶されている状態遷移確率から、拡張された領域のノードへの状態遷移確率などを推定して設定する方式について説明する。
【０５９５】
例えば、図３１に示されるように状態遷移確率テーブルを拡張する必要がある場合、状態遷移確率テーブルの各行の確率の値の総和が１となるように正規化する必要があると説明した。換言すれば、図３１の例において上述した処理では、追加された領域に状態遷移確率を設定するにあたり、既に記憶されている既知ノードから既知ノードへの状態遷移確率は考慮されていなかった。しかしながら、内部モデルデータに追加された未知ノードに対して複数の既知ノードからの遷移が発生し得ることは予測可能である。
【０５９６】
例えば、迷路におけるあるパーツＡが、別のパーツＢと置き換えられた場合、パーツＡに隣接していたパーツＣと、パーツＢとが接続されることになる。このような場合、ロボットがパーツＣからパーツＡに移動するためのアクションを実行すると、パーツＢに移動する可能性が高い。また、ロボットがパーツＡからパーツＣに移動するためのアクションを、パーツＢにおいて実行すると、パーツＣに移動する可能性が高い。この例では、パーツＢに対応するＨＭＭのノードを、未知ノードとして新たに追加する必要があるが、上記を考慮してパーツＣに対応する既知ノードとの状態遷移確率を設定すべきである。
【０５９７】
従って、既に記憶されている既知ノードから既知ノードへの状態遷移確率に基づいて、未知ノードと既知ノードとの間の状態遷移確率などを設定することができれば、より適切に状態遷移確率を設定することができると考えられる。いわば、過去の経験に基づいて未知ノードと既知ノードとの間の状態遷移確率などを設定することができれば、より適切に状態遷移確率を設定することができるのである。
【０５９８】
なお、ここで説明する既知ノードには、例えば、ロボットが迷路を移動中に、未知ノードとみなされて既に内部モデルデータに追加されているノードも含まれるものとする。
【０５９９】
上述のように設定する状態遷移確率の値は、次のパターンを考慮して決める必要がある。
【０６００】
すなわち、現実に、ノードsiからノードsjへの遷移が生じた場合、ノードsiとノードsjが既知のノードであるのか、新たに追加された未知のノードであるのかを考慮する必要がある。
【０６０１】
つまり、既知ノードから未知ノードへの遷移、未知ノードから未知ノードへの遷移、および未知ノードから既知ノードへの遷移の３つのパターンを考慮する必要がある。
【０６０２】
例えば、状態遷移確率テーブルが拡張された場合、図４２に示される領域３０１−１乃至領域３０１−３に、既知ノードから未知ノードへの状態遷移確率を設定する必要がある。また、領域３０３−１乃至領域３０３−３に、未知ノードから未知ノードへの状態遷移確率を設定する必要がある。さらに、領域３０２−１乃至領域３０２−３に、未知ノードから既知ノードへの状態遷移確率を設定する必要がある。
【０６０３】
また、上述したように、状態遷移確率テーブルの各行（例えば、ｎ行目）に記述された全ての数値を合計すると、１となるようになされているので、図４２において既存状態と記述された領域の確率もあらためて設定する必要がある。
【０６０４】
例えば、図４３に示されるような場合を例として説明する。
【０６０５】
すなわち、既知ノードである遷移元のノード３２１において、図中右方向への移動に対応するアクションを実行した結果、遷移する可能性の高い遷移先ノードは、状態遷移確率テーブルに基づいてノード３２２またはノード３２３と予想されていたものとする。しかしながら、実際に遷移元のノード３２１において、図中右方向への移動に対応するアクションを実行した結果、遷移した遷移先ノードはノード３２４であったとする。この場合、ノード３２４が未知ノードとなる。
【０６０６】
図４３の例において、ノード３２１では、図２のパーツ５に対応する観測シンボルが観測され、ノード３２２では、図２のパーツ１２に対応する観測シンボルが観測され、ノード３２３では、図２のパーツ６に対応する観測シンボルが観測されている。
【０６０７】
なお、図４３においては、迷路のパーツを表す矩形に対してノード３２１乃至ノード３２４の符号が付されているが、実際には、それらのパーツに対応する観測シンボルが観測されたノードに対して付される符号である。すなわち、エージェントは、ノード３２１乃至ノード３２３を、学習済の内部モデルデータに基づいて一意に認識することができたのであり、ノード３２４は、これまでに記憶されていない内部状態（ノード）として認識されたものとなる。
【０６０８】
つまり、エージェントは、ノード３２１から図中右方向に移動すると、図中上向きの曲がり角（ノード３２２）または図中下向きの曲がり角（ノード３２３）に出るものと予想していた。
【０６０９】
しかしながら、実際にノード３２１から図中右方向に移動してみると、十字路（ノード３２４）に出たのである。すなわち、ノード３２４では、図２のパーツ１５に対応する観測シンボルが観測されている。
【０６１０】
例えば、迷路におけるノード３２１に対応する位置に配置されていたパーツが置き換えられた場合、このような状況となる。このような場合、ノード３２４は、それまでの内部モデルデータには存在しなかったノードと考えられるから、少なくともノード３２４を内部モデルデータに追加する必要がある。
【０６１１】
このような場合、ノード３２４に対応する新たなインデックスが生成されて状態遷移確率テーブルの行列が追加される。従って、右方向のアクションに対応する状態遷移確率テーブルのノード３２１からノード３２４への状態遷移確率を設定する必要がある。ただし、実際に、新たなインデックスが生成されて状態遷移確率テーブルの行列が追加されるタイミングについては、図３７乃至図４１を参照して上述した通りである。
【０６１２】
この状態遷移確率は、例えば、ノード３２１からノード３２２およびノード３２３への状態遷移確率の和を３で割った値を、設定する。このとき、ノード３２１からノード３２２およびノード３２３への状態遷移確率もそれぞれの状態遷移確率に応じた重みづけにより案分されて設定されるようにすればよい。
【０６１３】
ノード３２１（例えば、ノードsiとする）から右方向のアクション（例えば、アクションｋ´とする）により遷移し得るノードの候補sjl（l=1，・・・L）は、例えば、状態遷移確率aij（k´）が閾値以上となる遷移先のノードsjをリストすればよい。
【０６１４】
図４３の例では、ノード３２１から右方向のアクションにより遷移し得るノード３２２およびノード３２３の２つのノードが候補ノードとしてリストされることになる。この場合、Ｌの値は２となる。
【０６１５】
未知ノードであるノード３２４をノードsnewで表し、アクションk´に対応する各既知ノードsiからsnewへの状態遷移確率ainew(k´)は、1/Lとして設定する。
【０６１６】
図４３の例では、ノード３２１からノード３２４への状態遷移確率が１／２として設定されることになる。
【０６１７】
状態遷移確率ainew(k´)は、図４２の例における領域３０１−１乃至領域３０１−３のいずれかの領域に設定されるものとなる。
【０６１８】
そして、アクションk´に対応する状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する。すなわち、状態遷移確率ainew(k´)として非零値が設定された行の各値をL/（L+1）倍すればよい。
【０６１９】
ただし、状態遷移確率aij（k´）が閾値以上となる遷移先のノードが存在しなかった場合、状態遷移確率ainew(k´)≒１として、上述のような正規化を行なう。
【０６２０】
なお、ノード３２１においてアクションｋ´以外のアクションを実行することによりノード３２４に遷移する状態遷移確率は、０に近い微小な値を設定すればよいので、状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する必要はない。
【０６２１】
また、図４４の図中の矢印で示されるに示されるように、十字路であるノード３２４においては、上下左右方向の４つアクションを実行して他のノードに遷移することが可能である。従って、上下左右方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率も設定する必要がある。これらの状態遷移確率は、図４２の例における領域３０２−１乃至領域３０２−３のいずれかに設定されるものとなる。なお、未知ノードから未知ノードへの遷移があり得る場合は、上記に加えて図４２の例における領域３０３−１乃至領域３０３−３のいずれかも含まれることになる。
【０６２２】
例えば、上方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２２から既知の各ノードへの状態遷移確率をコピーする。ノード３２２は、上向きの曲がり角であり、ノード３２１から右方向のアクションによって遷移し得るノードのうち、上方向のアクションにより他の既知ノードへ遷移し得る唯一のノードだからである。なお、ノード３２２から既知の各ノードへの状態遷移確率については何も変更しない。
【０６２３】
また、例えば、下方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２３から既知の各ノードへの状態遷移確率をコピーする。ノード３２３は、下向きの曲がり角であり、ノード３２１から右方向のアクションによって遷移し得るノードのうち、下方向のアクションにより他の既知ノードへ遷移し得る唯一のノードだからである。なお、ノード３２３から既知の各ノードへの状態遷移確率については何も変更しない。
【０６２４】
さらに、左方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２２から既知の各ノードへの状態遷移確率とノード３２３から既知の各ノードへの状態遷移確率を平均化した値とされる。ノード３２２とノード３２３は、ノード３２１から右方向のアクションによって遷移し得るノードのうち、左方向のアクションにより他の既知ノードへ遷移し得るノードだからである。すなわち、ノード３２２およびノード３２３の状態遷移確率の平均値をもって、左方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率とすればよい。なお、このとき、ノード３２２およびノード３２３から既知の各ノードへの状態遷移確率については何も変更されない。
【０６２５】
また、右方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、例えば、それぞれ一様の値を設定する。図４５に示されるように、右方向のアクションにより他の既知ノードへ遷移し得る候補のノードが他にないからである。
【０６２６】
さらに、ノード３２１以外の各既知ノードからノード３２４への状態遷移確率も設定する必要がある。
【０６２７】
ノード３２４は十字路だから、他のノードからノード３２４への遷移は、上下左右方向のいずれのアクションによっても起こりえる。すなわち、上方向のアクションによってノード３２４に遷移する遷移元のノードが存在し、下方向のアクションによってノード３２４に遷移する遷移元のノードが存在するはずである。また、左方向のアクションによってノード３２４に遷移する遷移元のノードが存在し、右方向のアクションによってノード３２４に遷移する遷移元のノードが存在するはずである。
【０６２８】
この場合、遷移元のノードを特定するとともに、遷移元のノードのそれぞれにおいてどのアクションを実行することによりノード３２４へ遷移するのかを特定しなければならない。すなわち、未知ノードへの逆方向遷移アクションを特定する必要がある。
【０６２９】
まず、遷移元のノードの推定の根拠となる情報を得るために、ノード３２４に類似するノードを抽出する。ノード３２４に類似するノードとは、例えば、仮にエージェントが現在ノード３２４以外のノードにいるとした場合、ある程度確からしいノードということもできる。
【０６３０】
例えば、迷路の構造上似通った部分が複数存在する場合を考える。エージェントは、それらの部分の１つであって所定のパーツ上に存在しているものとする。このような場合、実際には、エージェントが認識した部分とはことなる部分の所定のパーツ上に存在している可能性もある。このように、エージェントが認識したノードに類似するノードを抽出することができるのである。
【０６３１】
類似するノードは、過去ｎステップ分の時系列情報を用いたｎ-ステップ状態認識により特定することができる。
【０６３２】
時刻tにおいて、過去ｎステップ分のアクションのシーケンスct？n，・・・，ct？1および過去n+1ステップ分の観測シンボルのシーケンスot？n，・・・，otを用いて現在のノードを推定したり、現時刻tにおいてエージェントが各ノードに存在する確率を計算したりすることを「n-ステップ状態認識」と称する。
【０６３３】
ｎ-ステップ状態認識では、最初に、インデックスｉ（i=1，・・・N）のノードに対応する事前確率πiが、例えば、予め決められた方式で設定される。
【０６３４】
その後、認識器３５が、時刻t-nにおいてエージェントが各ノードに存在する確率δt-n(i)を式（５２）により演算する。
【０６３５】
【数５２】
2011018245.tif 000054
・・・（５２）
【０６３６】
そして、認識器３５は、時刻τ=t-n+1，・・・tの順に、エージェントが各ノードに存在する確率δτ(i)を式（５３）の漸化式により演算する。
【０６３７】
【数５３】
2011018245.tif 000055
・・・（５３）
【０６３８】
あるいはまた、式（５３）に替えて式（５４）の演算が行われるようにしてもよい。
【０６３９】
【数５４】
2011018245.tif 000056
・・・（５４）
【０６４０】
認識器３５は、さらに、式（５３）または式（５４）における最終時刻tにおいてエージェントが各ノードに存在する確率δt(i)を正規化することにより、時刻tにおける各ノードについての状態確率δ´t(i)を式（５５）により演算する。
【０６４１】
【数５５】
2011018245.tif 000057
・・・（５５）
【０６４２】
式（５５）により得られた状態確率が予め定められた閾値以上となるノードのそれぞれが、類似するノードとされる。
【０６４３】
なお、ｎ-ステップ状態認識では、過去ｎステップ分のアクションのシーケンスおよび観測シンボルのシーケンスが用いられるが、ｎを０とすると、観測シンボルotが所定の閾値以上の確率で観測されるノードの全てが類似するノードとなる。また、ｎを大きくするほど、類似するノードの数も、通常少なくなっていく。ｎ-ステップ状態認識におけるｎの値は、例えば、本発明において行なわれる推定等に用いて好適となるような予め設定された値とされるものとする。
【０６４４】
類似ノードが得られたら、それらのノードにおいて実行されることにより、他のノードに遷移し得るアクションを特定する。例えば、ノード３２４は十字路であるから、ノード３２４に類似するノードも十字路である可能性が高い。そうすると、類似するノードでは、上下左右方向の移動のアクションにより他のノードに遷移できることになる。
【０６４５】
そしてそれらのアクションを実行して他のノードに遷移し得る既知ノードを特定する。例えば、ノード３２１から右方向のアクションによって遷移し得る既知ノードであるノード３２２でも、それぞれ左方向および上方向のアクションを実行することにより、他のノードに遷移し得る。同様に、ノード３２１から右方向のアクションによって遷移し得る既知ノードであるノード３２３でも、それぞれ左方向および下方向のアクションを実行することにより、他のノードに遷移し得る。
【０６４６】
そうすると、未知ノード３２４には、ノード３２２において、それぞれ左方向および上方向のアクションを実行することで遷移する遷移先ノードのそれぞれから、左方向および上方向の逆方向となるアクションによって遷移し得ると仮定できる。この場合、右方向および下方向が逆方向となるアクション（逆方向遷移アクション）となる。
【０６４７】
また、未知ノード３２４には、ノード３２３において、それぞれ左方向および下方向のアクションを実行することで遷移する遷移先ノードのそれぞれから、左方向および下方向の逆方向となるアクションによって遷移し得ると仮定できる。この場合、右方向および上方向が逆方向となるアクション（逆方向遷移アクション）となる。
【０６４８】
逆方向遷移アクションは、例えば、次のようにして推定することができる。例えば、アクションczによってノードsaからノードsbへの遷移が起きる場合、逆方向遷移、すなわちノードsbからノードsaへの遷移を起こすためのアクションcz′を推定する。
【０６４９】
逆方向遷移アクションを推定するにあたり、認識器３５は、上述したように類似するノードであって既知ノードを特定する。ここで特定された既知ノードのそれぞれを、ノードsjq（q=1，・・・Q）で表すことにする。
【０６５０】
そして、認識器３５は、ノードsjqのそれぞれについて、アクションczによってノードsjqに遷移する遷移元ノードを抽出する。この場合、例えば、状態遷移確率aijq(z）が閾値以上となるノードsiをリストすればよい。
【０６５１】
そして、認識器３５は、(sjq，siq，l)(q= 1，・・・，Q， l= 1，・・・，Lq)の全ての組み合わせについて、ノードsjqからノードsiq，lへの状態遷移確率の平均値a*(k)を式（５６）により演算する。
【０６５２】
【数５６】
2011018245.tif 000058
・・・（５６）
【０６５３】
このようにして得られた状態遷移確率の平均値a*(k)のうち、閾値以上となるものを選択し、そのa*(k)に対応するアクションckを特定すれば、逆方向遷移アクションczr´(r＝1，・・・，R)を特定することができる。
【０６５４】
このようにして特定された遷移元のノードで、逆方向遷移が実行されることによりノード３２４へ遷移すると仮定すれば、上述したノード３２１からノード３２４への状態遷移確率を設定する場合と同様の操作により状態遷移確率を設定することができる。
【０６５５】
このように考えると、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、図４２に示される領域の全ての状態遷移確率を再設定する必要がある。
【０６５６】
すなわち、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、未知ノードにおいて実行し得るアクションと、そのアクションにより遷移し得る遷移先のノードとを特定する必要がある。このようにすれば、それら特定されたアクションと遷移先ノードとのペアから、状態遷移確率テーブルの所定の行列位置を特定することができ、それらの位置に設定すべき状態遷移確率の値を設定するとともに、その行の各値を正規化するなどすればよい。
【０６５７】
また、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、未知ノードに遷移し得る遷移元ノードと、その遷移元ノードから未知ノードに遷移するためのアクションとを特定する必要がある。このようにすれば、それら特定されたアクションと遷移元ノードとのペアから、状態遷移確率テーブルの所定の行列位置を特定することができ、それらの位置に設定すべき状態遷移確率の値を設定するとともに、その行の各値を正規化するなどすればよい。
【０６５８】
従って、上記に示したように、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルを拡張した場合、拡張された領域に設定すべき状態遷移確率の値を設定する処理は、最終的には、例えば、図４６に示される手順で実行されるようにすることができる。
【０６５９】
図４６は、ノード追加時の状態遷移確率設定処理を説明するフローチャートである。この処理は、例えば、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルなどに未知ノードを追加するとき実行される。
【０６６０】
なお、ここでは、未知ノードsnewが内部モデルデータに追加されるものとし、エージェントがノードsnewに遷移する直前のノードをノードsi′とし、ノードsi′においてアクションck′が実行されることによりエージェントはノードsnewに遷移したものとする。
【０６６１】
ステップＳ４０１において、認識器３５は、図４７のフローチャートを参照して後述するノード逆アクションペアリスト生成処理を実行する。
【０６６２】
これにより、未知ノードへの遷移元のノードが特定されるとともに、未知ノードへの逆方向遷移アクションが特定されることになる。
【０６６３】
ステップＳ４０２において、学習器３４は、図４８のフローチャートを参照して後述する逆アクション状態遷移確率設定処理を実行する。
【０６６４】
これにより、ステップＳ４０１の処理により特定された遷移元のノードにおいて逆方向遷移アクションを実行することにより未知ノードへ遷移する状態遷移確率が設定される。また、ここで新たに設定された状態遷移確率に応じて状態遷移確率テーブルの各行の値が正規化される。
【０６６５】
ステップＳ４０３において、認識器３５は、図４９のフローチャートを参照して後述するノード順アクションペアリスト生成処理を実行する。
【０６６６】
これにより、未知ノードからの遷移先のノードが特定されるとともに、未知ノードからそれらの遷移先ノードへ遷移するための順方向遷移アクションが特定されることになる。
【０６６７】
ステップＳ４０４において、学習器３４は、図５０のフローチャートを参照して後述する順アクション状態遷移確率設定処理を実行する。
【０６６８】
これにより、未知ノードにおいて、ステップＳ４０３の処理により特定された順方向遷移アクションを実行することにより遷移先のノードへ遷移する状態遷移確率が設定される。また、ここで新たに設定された状態遷移確率に応じて状態遷移確率テーブルの各行の値が正規化される。
【０６６９】
次に、図４７のフローチャートを参照して、図４６のステップＳ４０１のノード逆アクションペアリスト生成処理の詳細について説明する。
【０６７０】
ステップＳ４２１において、認識器３５は、ノードsi′においてアクションck′が実行されることにより遷移し得る候補ノードsjl（l=1，・・・L）を抽出する。候補ノードsjlは、例えば、状態遷移確率ai´j（k´）が閾値以上となる遷移先のノードsj´をリストすればよい。
【０６７１】
ステップＳ４２２において、認識器３５は、過去ｎステップ分の時系列情報を用いたｎ-ステップ状態認識を行なう。
【０６７２】
ステップＳ４２３において、認識器３５は、ステップＳ４２２の処理結果に基づいて、ノードsnewに類似する類似ノードであって既知ノードを抽出する。ここで特定された既知ノードのそれぞれを、ノードsjq（q=1，・・・Q）で表すことにする。このとき、上述した式（５２）乃至式（５５）の演算が行われることにより、ノードsnewに類似する類似ノードが抽出される。
【０６７３】
ステップＳ４２４において、認識器３５は、ステップＳ４２３の処理で抽出された類似ノードの有効アクションを抽出する。
【０６７４】
ここで、有効アクションは、上述した各類似ノードにおいて実行されることにより、他のノードに遷移し得るアクションを意味する。
【０６７５】
ステップＳ４２４では、例えば、アクション毎の評価値Ekが、式（５７）により演算される。なお、この演算は、個々のアクションに対応してそれぞれ行われ、１のアクションに対して１の評価値が得られることになる。
【０６７６】
【数５７】
2011018245.tif 000059
・・・（５７）
【０６７７】
ここでajxq(k)(q=1，・・・，Q， x=1，・・・，N)は、ノードsjq(q=1，・・・，Q)においてアクションckを実行したとき、ノードsxに遷移する状態遷移確率である。
【０６７８】
そして、式（５７）により演算された評価値が閾値以上となったアクションｋが選択され、有効アクションの候補とされる。
【０６７９】
さらに、その選択されたアクションｋのそれぞれについて、状態遷移確率ajxq(k)がチェックされ、状態遷移確率ajxq(k)が閾値以上となる(q，x)の組が少なくとも1つ存在するか否かが判定される。そのような(q，x)の組が1つも存在しない場合、そのアクションｋは、有効アクションの候補から除外される。
【０６８０】
このようにして、ステップＳ４２４では、有効アクションckr(r=1，・・・，R)が抽出される。
【０６８１】
ステップＳ４２５において、認識器３５は、ステップＳ４２１の処理で抽出された候補ノードsjlのうち、ステップＳ４２４の処理で抽出されたアクションckrを有効アクションとして有するものを抽出する。すなわち、候補ノードのうち、類似ノードと同一の有効アクションを有するノードsjru (u=1，・・・，Ur)が抽出される。
【０６８２】
ステップＳ４２５では、例えば、ノードsjlのそれぞれについて評価値Elrが式（５８）により演算される。なお、この演算は、ノードsjlのそれぞれにおいて、個々のアクションckrを実行する場合のそれぞれに対応してそれぞれ行われ、ノードとアクションの組み合わせ１つに対して１の評価値が得られることになる。
【０６８３】
【数５８】
2011018245.tif 000060
・・・（５８）
【０６８４】
なお、式（５８）は、変数lにより特定されるインデックスjの候補ノードで、変数ｒで特定されるアクションckを実行する場合について算出される。また、式（５８）の右辺の状態遷移確率のアクションであるｋ（またはck）は、左辺の変数ｒにより特定されるものとする。
【０６８５】
このように、ステップＳ４２５では、式（５８）により算出された評価値が閾値以上となったものが、ノードsjruとして抽出されるのである。
【０６８６】
ステップＳ４２６において、認識器３５は、ステップＳ４２５で抽出されたノードとステップＳ４２４で抽出された有効アクションのペア(sjru，ckr)を生成し、それぞれのペアから特定される遷移先ノードを特定する。
【０６８７】
例えば、ノードsjruにおいて、アクションckrを実行した場合の状態遷移確率ajlru(k)（l=1，・・・，N）をチェックし、閾値を超える状態遷移確率に対応する遷移先ノードslq（q=1，・・・Qru）を特定する。
【０６８８】
ステップＳ４２７において、認識器３５は、ノードsjruにおけるアクションckrの逆方向遷移アクションを推定する。すなわち、ノードslqからノードsjruへ遷移するためのアクションを推定する。このとき推定された逆方向遷移アクションを、cruqv（v=1，・・・Vruq）とする。ただし、遷移先ノードがノードsi′であった場合は、この推定は行なわない。
【０６８９】
そして、認識器３５は、ステップＳ４２６で特定された遷移先ノードと、逆方向遷移アクションとのペア（slq，cruqv）(l=1，・・・，L， r=1，・・・，R， u=1，・・・，Ur， q=1，・・・，Qru， v=1，・・・，Vruq)を生成する。
【０６９０】
ステップＳ４２８において、認識器３５は、ステップＳ４２７で生成したペア（slq，cruqv）に（si′，ck′）を加えて重複を排除し、未知ノードへの遷移元ノードと逆方向遷移アクションのペア(six，ckx)(x=1，・・・，X)を生成する。そして、未知ノードへの遷移元ノードと逆方向遷移アクションのペアのそれぞれがリストされる。
【０６９１】
このようにして、ノード逆アクションペアリスト生成処理が実行される。
【０６９２】
図４７の処理により得られたペアに基づいて、ノードsixにおいてアクションckxを実行することによりノードsnewに遷移したと仮定され、図４６のステップＳ４０２の処理が実行される。
【０６９３】
次に、図４８のフローチャートを参照して、図４６のステップＳ４０２の逆アクション状態遷移確率設定処理の詳細な例について説明する。
【０６９４】
例えば、遷移元ノードsiからアクションcｋによりノードsnewに遷移したと仮定されたものとする。
【０６９５】
ステップＳ４４１において、学習器３４は、アクションcｋにより、ノードsiから遷移し得るノードの候補を抽出する。ノードの候補sjl（l=1，・・・L）は、例えば、状態遷移確率aij（k）が閾値以上となる遷移先のノードsjをリストすればよい。
【０６９６】
ステップＳ４４２において、学習器３４は、未知ノードへの状態遷移確率を設定し、正規化する。
【０６９７】
例えば、アクションcｋに対応する各候補ノードsiからsnewへの状態遷移確率ainew(k)は、1/Lとして設定する。そして、アクションcｋに対応する状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する。すなわち、状態遷移確率ainew(k)として非零値が設定された行の各値をL/（L+1）倍する。
【０６９８】
ただし、ステップＳ４１１の処理の結果、状態遷移確率aij（k）が閾値以上となる遷移先のノードが存在しなかった場合、状態遷移確率ainew(k)≒１として、上述のような正規化を行なう。
【０６９９】
このようにして、逆アクション状態遷移確率設定処理が実行される。
【０７００】
次に、図４９のフローチャートを参照して、図４６のステップＳ４０３のノード順アクションペアリスト生成処理の詳細な例について説明する。
【０７０１】
ステップＳ４６１において、認識器３５は、図４７のステップＳ４２６の処理と同様に遷移先ノードslq（q=1，・・・Qru）を抽出する。すなわち、候補ノードと有効アクションのペアを生成し、各ペアに対応する遷移先ノードを特定する。
【０７０２】
ステップＳ４６２において、認識器３５は、ステップＳ４６１の処理で得られた遷移先ノードslq（q=1，・・・Qru）と、その遷移先ノードに遷移するためのアクションckr（r=1，・・・R）をペアとして生成する。
【０７０３】
ステップＳ４６３において、認識器３５は、ステップＳ４６２の処理で得られたペアの重複を排除し、ペア（sjy，cky）(y=1，・・・，Y)を生成する。そして、遷移先ノードとその遷移先ノードへ遷移するためのアクションのペアのそれぞれがリストされる。
【０７０４】
このようにして、ノード順アクションペアリスト生成処理が実行される。
【０７０５】
図４９の処理により得られたペアに基づいて、ノードsnewにおいてアクションckyを実行することによりノードsjyに遷移したと仮定され、図４６のステップＳ４０４の処理が実行される。
【０７０６】
次に、図５０のフローチャートを参照して、図４６のステップＳ４０４の順アクション状態遷移確率設定処理の詳細な例について説明する。
【０７０７】
ステップＳ４８１において、学習器３４は、状態遷移確率anewj（k）(j=1，・・・，N， k=1，・・・，K)を、全て微小な値で初期化する。
【０７０８】
ステップＳ４８２において、学習器３４は、図４８の処理により得られたペア（sjy，cky）を用いて状態遷移確率を設定する。すなわち、ノードsnewにおいてアクションckyを実行することによりノードsjyに遷移する状態遷移確率anewjy(k)を１として設定する。
【０７０９】
ステップＳ４８３において、学習器３４は、Σjanewj(k)（k=1，・・・，K)を満たすように正規化する。
【０７１０】
このようにして順アクション状態遷移確率設定処理が実行される。
【０７１１】
上記した例においては、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルに未知ノードを追加する場合の例について説明したが、これに伴って、観測確率テーブルにも未知ノードを追加する必要がある。この場合の、観測確率テーブルの更新については、例えば、図３１に示されるように観測確率テーブルを拡張する必要がある場合に、学習器３４が行う処理として上述した処理を行うようにすればよい。
【０７１２】
また、勿論、状態遷移確率の推定のための頻度変数のテーブル、および観測確率の推定のための頻度変数のテーブルも図４６を参照して上述した処理に伴って更新されることになる。
【０７１３】
次に、アンカリングする場合の状態遷移確率の設定について説明する。
【０７１４】
上述したように、アンカリングは、既知ノードへの遷移が認識された場合、未知ノードとみなされたノードと既知ノードとの状態遷移確率などを設定する処理である。
【０７１５】
換言すれば、未知ノードsi´においてアクションck´を実行して、既知ノードsj´に遷移した場合、内部モデルデータの状態遷移確率テーブルにおいて、状態遷移確率a i´j(k´）(j=1，・・・，N)が閾値以上となるノードsjが存在しないとき、アンカリングが行なわれる。すなわち、未知ノードとみなされたノードから、既知ノードへの遷移が確認され、かつ当該未知ノードから当該既知ノード以外のノードへの遷移が発生し難い場合、アンカリングが行われるのである。
【０７１６】
アンカリングでは、アクションck´による未知ノードsi´から既知ノードsj´への状態遷移確率が設定される。例えば、図４６を参照して上述したように、未知ノードとみなされたノードが内部モデルデータに追加される都度、その未知ノードから既知ノードへの状態遷移確率が推定されて設定される。しかし、未知ノードから既知ノードへの遷移が実際に発生した場合は、アンカリングがなされることになる。
【０７１７】
ここで、図５１のフローチャートを参照してアンカリング処理について説明する。この処理は、例えば、図４０のステップＳ３１９の処理として実行される処理である。
【０７１８】
ステップＳ５０１において、学習器３４は、アンカリングの対象となる遷移に対応する状態遷移確率を１とする。上述の例では、状態遷移確率a i´j´(k´）が１とされる。
【０７１９】
ステップＳ５０２において、学習器３４は、Σja i´j(k´）が１となるように、状態遷移確率テーブルの各値を正規化する。
【０７２０】
ステップＳ５０３において、認識器３５は、既知ノードsj´から未知ノードsi´に遷移する逆方向遷移アクションを推定する。このとき、例えば、図４７を参照して上述した場合と同様に逆方向遷移アクションの推定が行なわれる。これにより、逆方向遷移アクションczr(r=1，・・・，R)が推定される。
【０７２１】
ステップＳ５０４において、学習器３４は、ステップＳ５０３の処理で推定された逆方向遷移アクションのそれぞれが実行されることにより、既知ノードsj´から未知ノードsi´への遷移が発生したと仮定して状態遷移確率を設定する。この処理は、例えば、図４８を参照して上述した場合と同様である。
【０７２２】
このようにしてアンカリング処理が実行される。
【０７２３】
なお、図５１を参照して説明した処理に替えて、既知ノードsj´から未知ノードsi´への遷移が発生したと仮定して図４６を参照して上述した処理が行われることにより状態遷移確率を設定することで、アンカリング処理がなされるようにしてもよい。
【０７２４】
すなわち、実際には、未知ノードsi´においてアクションck´を実行して、既知ノードsj´に遷移したのだが、逆方向遷移アクションczr (r=1，・・・，R)によって既知ノードsj´から未知ノードsi´への遷移が発生したと仮定するのである。ここで、逆方向遷移アクションczr (r=1，・・・，R)は、例えば、ステップＳ５０３の処理と同様にして推定することができる。
【０７２５】
つまり、アクションcz1によって、既知ノードsj´から未知ノードsi´への遷移が発生したと仮定して図４６を参照して上述した処理を実行する。また、アクションcz2によって、やはり、既知ノードsj´から未知ノードsi´への遷移が発生したと仮定して図４６を参照して上述した処理を実行する。同様に、アクションcz3・・・アクションczRによって、それぞれ既知ノードsj´から未知ノードsi´への遷移が発生したと仮定して図４６を参照して上述した処理を実行するのである。
【０７２６】
アンカリングの際には、このように、アクションczr (r=1，・・・，R)によって直前のノードsj′（実際には、アンカリングする既知ノード）から未知ノードsi′へ遷移したものとみなして、図４６の処理がそれぞれ実行されるようにしてもよい。
【０７２７】
このように、本発明によれば、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張することが可能である。また、その際に、それぞれのテーブルの拡張された領域に設定すべき状態遷移確率、観測確率などの値を適切に設定することも可能である。さらに、既に記憶されている既知ノードから既知ノードへの状態遷移確率に基づいて、未知ノードと既知ノードとの間の状態遷移確率などを設定することが可能である。
【０７２８】
ここまで、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更する必要に迫られた場合にとり得る処置について説明した。
【０７２９】
以上のように、本発明によれば、アクション拡張型ＨＭＭを用いた学習を行うことができる。これにより、エージェントがアクション信号を用いて環境に対してアクションを実行し、今後観測される観測シンボルに影響を与えることができるようにするという状況における学習が可能となる。
【０７３０】
また、本発明によれば、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うことができる。すなわち、学習される内部モデルデータに対してスプリットアルゴリズムを適用するなどして一状態一観測制約を課し、フォワードマージアルゴリズムおよびバックワードマージアルゴリズムを適用するなどしてアクション遷移制約を課す。これにより、計算すべきパラメータの数の増大などを抑制し、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うことができる。
【０７３１】
さらに、本発明によれば、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができる。すなわち、状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを算出して保存することにより、アクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができる。
【０７３２】
また、本発明によれば、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更することが可能である。
【０７３３】
この際、例えば、エージェントに対して予め所定の数だけノードの数が増えることを前提として、内部モデルデータを拡張するように指令することも可能であるし、エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張することも可能である。
【０７３４】
エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張するために、エージェントが、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのか認識できるようにした。
【０７３５】
また、所定のタイミングで所定の個数の未知ノードが追加されるようにするとともに、アンカリングされた直後の内部モデルデータに基づいて追加学習方式での学習が行われるようにした。これにより、例えば、既知ノードの中に散発的に新たなノードが発現するような場合はもちろんのこと、長期に渡って新たなノードが連続して検出されるような困難な環境においても、十分に有効な学習を行うことが可能となった。
【０７３６】
さらに、内部モデルデータを拡張するにあたり、過去の経験に基づいて未知ノードと既知ノードとの間の状態遷移確率などを設定することができるようにした。
【０７３７】
このように、本発明によれば、変化する環境の中で自律的な学習を行う際に、効率的かつ安定的な学習を行うことができるのである。
【０７３８】
以上においては、本発明の実施の形態を主に、ロボットが迷路を移動する場合の例に適用して説明したが、勿論、それ以外の実施の形態であっても構わない。例えば、アクションは、エージェントを移動させるものに限られず、環境に対して働きかける行為であればアクションとなり得る。また、例えば、観測シンボルは、迷路のパーツの形状などに対応するものに限られず、光や音の変化などに対応するものであってもよい。
【０７３９】
なお、上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータにインストールされる。例えば、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、図５２に示されるような汎用のパーソナルコンピュータ７００などに、ネットワークや記録媒体から、そのソフトウェアを構成するプログラムがインストールされる。
【０７４０】
図５２において、ＣＰＵ（Central Processing Unit）７０１は、ＲＯＭ（Read Only Memory）７０２に記憶されているプログラム、または記憶部７０８からＲＡＭ（Random Access Memory）７０３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ７０３にはまた、ＣＰＵ７０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０７４１】
ＣＰＵ７０１、ＲＯＭ７０２、およびＲＡＭ７０３は、バス７０４を介して相互に接続されている。このバス７０４にはまた、入出力インタフェース７０５も接続されている。
【０７４２】
入出力インタフェース７０５には、キーボード、マウスなどよりなる入力部７０６、ＬＣＤ(Liquid Crystal display)などよりなるディスプレイ、並びにスピーカなどよりなる出力部７０７、ハードディスクなどより構成される記憶部７０８が接続されている。また、入出力インタフェース７０５には、モデム、LANカードなどのネットワークインタフェースカードなどより構成される通信部７０９が接続されている。通信部７０９は、インターネットを含むネットワークを介しての通信処理を行う。
【０７４３】
入出力インタフェース７０５にはまた、必要に応じてドライブ７１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア７１１が適宜装着される。そして、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部７０８にインストールされる。
【０７４４】
上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、インターネットなどのネットワークや、リムーバブルメディア７１１などからなる記録媒体からインストールされる。
【０７４５】
なお、この記録媒体は、図５２に示される、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フロッピディスク（登録商標）を含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory)，ＤＶＤ (Digital Versatile Disk)を含む）、光磁気ディスク（MD（Mini-Disk）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア７１１により構成されるものだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているＲＯＭ７０２や、記憶部７０８に含まれるハードディスクなどで構成されるものも含む。
【０７４６】
なお、本明細書において上述した一連の処理は、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０７４７】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０７４８】
１０  自律行動学習装置，  ３１  センサ部，  ３２  行動出力部，  ３３  観測バッファ，  ３４  学習器，  ３５  認識器，  ３６  行動生成器，  ３７  内部モデルデータ記憶部，  ３８  認識結果バッファ，  ３９  行動出力バッファ
【図１】
2011018245.tif 000061
【図２】
2011018245.tif 000062
【図３】
2011018245.tif 000063
【図４】
2011018245.tif 000064
【図５】
2011018245.tif 000065
【図６】
2011018245.tif 000066
【図７】
2011018245.tif 000067
【図８】
2011018245.tif 000068
【図９】
2011018245.tif 000069
【図１０】
2011018245.tif 000070
【図１１】
2011018245.tif 000071
【図１２】
2011018245.tif 000072
【図１３】
2011018245.tif 000073
【図１４】
2011018245.tif 000074
【図１５】
2011018245.tif 000075
【図１６】
2011018245.tif 000076
【図１７】
2011018245.tif 000077
【図１８】
2011018245.tif 000078
【図１９】
2011018245.tif 000079
【図２０】
2011018245.tif 000080
【図２１】
2011018245.tif 000081
【図２２】
2011018245.tif 000082
【図２３】
2011018245.tif 000083
【図２４】
2011018245.tif 000084
【図２５】
2011018245.tif 000085
【図２６】
2011018245.tif 000086
【図２７】
2011018245.tif 000087
【図２８】
2011018245.tif 000088
【図２９】
2011018245.tif 000089
【図３０】
2011018245.tif 000090
【図３１】
2011018245.tif 000091
【図３２】
2011018245.tif 000092
【図３３】
2011018245.tif 000093
【図３４】
2011018245.tif 000094
【図３５】
2011018245.tif 000095
【図３６】
2011018245.tif 000096
【図３７】
2011018245.tif 000097
【図３８】
2011018245.tif 000098
【図３９】
2011018245.tif 000099
【図４０】
2011018245.tif 000100
【図４１】
2011018245.tif 000101
【図４２】
2011018245.tif 000102
【図４３】
2011018245.tif 000103
【図４４】
2011018245.tif 000104
【図４５】
2011018245.tif 000105
【図４６】
2011018245.tif 000106
【図４７】
2011018245.tif 000107
【図４８】
2011018245.tif 000108
【図４９】
2011018245.tif 000109
【図５０】
2011018245.tif 000110
【図５１】
2011018245.tif 000111
【図５２】
2011018245.tif 000112