JP2011018245A - 認識装置および方法、プログラム、並びに記録媒体 - Google Patents

Abstract

【課題】変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できるようにする。
【解決手段】変数Ｎの値を１にセットし、ステップＳ２０２において、長さＮの時系列情報が取得される。ステップＳ２０３において、認識器は、時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力し、ステップＳ２０４において、実際にあり得るノード列であるか否かを判定する。実際にあり得るノード列ではないと判定された場合、未知ノードであると認識される。一方、実際にあり得るノード列であると判定された場合、エントロピーが計算され、閾値以上であると判定された場合、変数Ｎの値がインクリメントされ、時系列情報が過去方向に延長される。閾値以上ではないと判定された場合、既知ノードであると認識される。
【選択図】図３３

Description

本発明は、認識装置および方法、プログラム、並びに記録媒体に関し、特に、変化する環境の中で自律的な学習を行う際に、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのかを適切に認識できるようにする認識装置および方法、プログラム、並びに記録媒体に関する。

対象となるシステムから観測されるセンサ信号を時系列データとして扱い、状態および状態遷移を合わせ持つ確率モデルとして学習する方法としてＨＭＭ（隠れマルコフモデル）の利用が提案されている。ＨＭＭは、音声認識に広く利用される技術の一つである。ＨＭＭは、状態遷移確率と、各状態における出力確率密度関数で定義される状態遷移モデルであり、そのパラメータは、尤度を最大化するように推定される。パラメータの推定方法としては、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の各時刻で取得した観測信号に対応する観測シンボルo_t， o_t+1， o_t+2， ・・・， o_Tが各時刻の観測シンボルとして観測バッファ３３に記憶されることになる。

行動出力部３２は、例えば、ロボットが実行すべきアクション（日本語で行動）を、ロボットに実行させるための制御信号を出力する機能ブロックである。行動出力部３２から出力された制御信号は、その制御信号に対応するアクションを特定する情報に変換され、その制御信号が出力された時刻と対応付けられて行動出力バッファ３９に記憶されるようになされている。

例えば、時刻t，t+1，t+2，・・・Tの各時刻で実行したアクションc_t， c_t+1， c_t+2， ・・・， c_Tが各時刻のアクションとして行動出力バッファ３９に記憶されることになる。

学習器３４は、観測バッファ３３および行動出力バッファ３９に記憶されている情報に基づいて、内部モデルデータを生成または更新し、内部モデルデータ記憶部３７に記憶させる。

内部モデルデータ記憶部３７に記憶されている内部モデルデータには、上述した、３次元の状態遷移確率テーブル、および２次元の観測確率テーブルが含まれる。さらに、内部モデルデータ記憶部３７に記憶されている内部モデルデータには、後述する、状態遷移確率の計算のための頻度変数および観測確率の計算のための頻度変数が含まれる。

認識器３５は、観測バッファ３３および行動出力バッファ３９に記憶されている情報、並びに内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいて、現在、ロボットが位置するノードを認識するようになされている。認識器３５から出力された認識結果は、その認識結果が出力された時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

行動生成器３６は、内部モデルデータ記憶部３７に記憶されている内部モデルデータ、行動出力バッファ３９に記憶されている情報、および認識器３５が出力する認識結果に基づいて、ロボットが実行すべきアクションを決定する。そして、行動生成器３６は、決定されたアクションに対応する制御信号を出力するように、行動出力部３２を制御する。

このように、自律行動学習装置１０は、例えば、ロボットを迷路上で移動させて、自動的に迷路の構造などを学習させることができるようになされている。

次に、図９の学習器３４におけるアクション拡張型ＨＭＭの学習アルゴリズムについて説明する。

通常のＨＭＭではノードs_iからs_jへの状態遷移確率を状態遷移確率テーブルa_ijでモデル化するが、アクション拡張型ＨＭＭではアクションパラメータcを用いてa_ij(c)としてモデル化する。

学習アルゴリズムとしては、Baum-Welchアルゴリズムを用いる。forward確率、backward確率の計算ができれば、Baum-Welchアルゴリズムに基づくパラメータ推定(期待値最大化法)が可能となるので、以下ではそれらの確率の計算について説明する。

ここで、アクション集合C = {c₁， c₂， ・・・， c_n}に属するアクションc_kによって、ノードs_i からs_j への遷移が起きる確率を、３次元の確率表現テーブルa_ij(k) ≡ a_ijkで表すこととする。なお、この例の場合、離散アクション集合を実行することになる。

まずforward確率の計算について説明する。

時刻1，2，・・・t-1の各時刻においてエージェントが取得したセンサ信号に対応する観測シンボルを、それぞれo₁，o₂，・・・，o_t？1で表すことにする。また、時刻1，2，・・・t-1の各時刻においてエージェントが実行したアクションを、それぞれc₁，c₂，・・・，c_t？1で表すことにする。この場合、時刻tにおいてエージェントが取得したセンサ信号に対応する観測シンボルがo_tであるとき、エージェントがノードs_jにいるforward確率α_t(j)は、式（１）の漸化式により表すことができる。

・・・（１）
ただし、b_j(o)は、ノードs_jの下で観測シンボルoが得られる観測確率である。

次に、backward確率の計算について説明する。

エージェントが時刻tにおいて状態iにいた場合、時刻t，t+1，t+2，・・・T-1の各時刻において、それぞれアクションc_t，c_t+1，・・・，c_T？1を実行し、各時刻で取得したセンサ信号に対応する観測シンボルが、それぞれo_t+1，o_t+2，・・・，o_Tであるbackward確率βt(i)は、式（２）の漸化式により表すことができる。

・・・（２）

このように計算されるforward確率と、backward確率とを用いて、状態遷移確率の推定と、観測確率の推定を行なうことができる。

離散アクション集合を実行する場合の状態遷移確率の推定と観測確率の推定は、次のようにして行なわれる。

状態遷移確率a_ij(k)の推定は、Baum-WelchアルゴリズムのＭ−ステップで行なう。ここで、状態遷移確率a_ij(k)は、エージェントが状態iにいるとき、アクションｋを実行することにより状態ｊに遷移する確率を意味する。すなわち、式（３）を演算することにより、状態遷移確率の推定値a´_ij(k)を得ることができる。

・・・（３）

観測確率b_j(o)の推定も、やはりBaum-WelchアルゴリズムのＭ-ステップで行なう。ここで、観測確率b_j(o)は、エージェントが状態ｊにいるとき、観測シンボルｏに対応するセンサ信号を取得する確立を意味する。すなわち、式（４）を演算することにより、観測確率の推定値b´_j(o)を得ることができる。

・・・（４）

式（４）は、離散観測信号を取得する場合の例であるが、連続観測信号を取得する場合は、時刻tにおいて取得された観測信号o_tを、式（５）に示されるγ_t(j）よって重み付けた信号分布を用いて、観測確率密度関数b_j(o)のパラメータを再推定すればよい。なお、γ_t(j）は、時刻tにおいてエージェントが状態jにいる場合の重み係数を表している。

・・・（５）

通常は、ガウス分布などの対数凹又は楕円型対称確率密度をモデルとして用い、観測確率密度関数b_j(o)のパラメータの再推定を行うことができる。

ガウス分布などの対数凹又は楕円型対称確率密度のモデルのパラメータとしては、状態jにおける観測信号の平均ベクトルμ´_jおよび共分散行列U´_jを用いることができる。平均ベクトルμ´_jおよび共分散行列U´_jは、それぞれ、式（６）および式（７）により求めることができる。

・・・（６）

・・・（７）

次に連続アクション集合を実行する場合の例について説明する。

連続アクションの場合、離散アクションの場合と異なり、離散アクションc_kより連続アクションcの出力される確率ρ_k(c)の学習が必要となる。確率ρ_k(c)を学習することにより、連続アクションｃを、あたかも離散アクションc_kであるようにラベリングする（離散アクションに対応付ける）ことができるからである。

連続アクションの場合のforward確率の計算は次のようにして行なわれる。

時刻1，2，・・・t-1の各時刻においてエージェントが取得したセンサ信号に対応する観測シンボルを、それぞれo₁，o₂，・・・，o_t？1で表すことにする。また、時刻1，2，・・・t-1の各時刻においてエージェントが実行した連続アクションから推定される離散アクションを、それぞれc₁，c₂，・・・，c_t？1で表すことにする。この場合、時刻tにおいてエージェントが取得したセンサ信号に対応する観測シンボルがo_tであるとき、エージェントがノードs_jにいるforward確率α_t(j)は、式（８）の漸化式により表すことができる。

・・・（８）
ただし、ρ_k(c)は、離散アクションc_kより連続アクションcの出力される確率を表す。
なお、ρ_k(c)をどのようにして求めるかについては、後述する。

エージェントが時刻tにおいて状態iにいた場合、時刻t，t+1，t+2，・・・T-1の各時刻において、エージェントが実行した連続アクションから推定される離散アクションを、それぞれアクションc_t，c_t+1，・・・，c_T？1とし、各時刻で取得したセンサ信号に対応する観測シンボルが、それぞれo_t+1，o_t+2，・・・，o_Tであるbackward確率βt(i)は、式（９）の漸化式により表すことができる。

・・・（９）

連続アクション集合を実行する場合の状態遷移確率の推定と観測確率の推定は、次のようにして行なわれる。

状態遷移確率a_ij(k)の推定は、離散アクションの場合と同様に、Baum-WelchアルゴリズムのＭ−ステップで行なう。ここで、状態遷移確率a_ij(k)は、エージェントが状態iにいるとき、アクションｋを実行することにより状態ｊに遷移する確率を意味する。すなわち、式（１０）を演算することにより、状態遷移確率の推定値a´_ij(k)を得ることができる。

・・・（１０）

観測確率b_j(o)の推定は、離散アクションの場合と全く同一なので、ここでは説明を省略する。

次に、離散アクションc_kより連続アクションcの出力される確率ρ_k(c)をどのようにして求めるかについて説明する。

確率ρ_k(c)もBaum-Welch アルゴリズムのＭ−ステップで行なうようにすることができる。すなわち、連続観測信号の場合における観測確率の推定と同様の方式で推定することができる。

時刻tにおいて実行されるアクションctを、式（１１）に示されるξ_t(i，j，k)よって重み付けた信号分布を用いて、確率ρ_k(c)を推定すればよい。

・・・（１１）

観測確率の場合と同様にガウス分布などをモデルとして用い、確率ρ_k(c)を推定することができる。

この場合、連続アクションｃをラベリングして得られる離散アクションc_kより生成されるアクション信号の平均ベクトルν_kおよび共分散行列Ｖ´_kを、それぞれ式（１２）および式（１３）により演算する。このようにして演算された、アクション信号の平均ベクトルν_kおよび共分散行列Ｖ´_kを、ガウス分布などのモデルのパラメータとして用いるようにすればよい。

・・・（１２）

・・・（１３）

このようにして、アクション拡張型ＨＭＭにおける３次元の状態遷移確率テーブルと、２次元の観測確率テーブルを学習により生成することができる。

ここまで説明したアクション拡張型ＨＭＭの学習アルゴリズムにより、通常のＨＭＭと同様に、状態遷移確率と観測確率を得ることができる。

しかし、状態の数（ノード数）をＮ、観測シンボル数をＭ、アクション数をＫとすると、３次元の状態遷移確率テーブルと、２次元の観測確率テーブルにおいて算出すべきパラメータ数は、Ｎ²Ｋ＋ＮＭとなる。このように、アクション拡張型ＨＭＭにおいては、Ｎ，Ｍ，Ｋの数が増大すると、学習処理の負荷も加速度的に増大することが明らかである。例えば、Ｎが２５０程度、Ｍが１５程度、Ｋが５程度の環境においては、３０万規模のパラメータを算出する必要がある。数少ないサンプルからこれほど多くのパラメータを適切に決定することは非常に困難である。

しかしながら、例えば、モデルに制約を加えることでパラメータの自由度を減らし、学習を安定化させることが可能である。次に、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うために必要となる技術について説明する。

本発明では、アクション拡張型ＨＭＭの学習において、一状態一観測制約およびアクション遷移制約を課すことにする。

最初に、一状態一観測制約について説明する。一状態一観測制約は、例えば、あるノードで観測される観測シンボルは、原則として１つに限るという制約である。なお、一状態一観測制約の下でも、同じ観測シンボルを別々のノードで観測することは許容される。

アクション拡張型ＨＭＭの学習において、一状態一観測制約を課すことにより事象の表現方式が限定され、結果として、状態遷移確率テーブルと観測確率テーブルの生成のために必要となるパラメータの自由度が減少する。

一状態一観測制約を実現する方式の１つとして、例えば、離散観測型ＨＭＭの学習においてなされているように、目的関数に観測確率をスパースにするような制約項を加えるという方式がある。

例えば、目的関数に観測確率をスパースにするような重みλを乗じた制約項Σ_jＨ(b_j)を加えるという方式が考えられる。ここで、Ｈ(b_j)は、ノードs_jで観測され得るすべて観測シンボルに対する観測確率ベクトルb_jに対して定義されるエントロピーとされる。これ以外にも、観測確率ベクトルb_jのＬ１ノルムとＬ２ノルムの差分Σ_j(||b_j||₁ ？ ||b_j||₂)などを、制約項とする方式も考えられる。

あるいはまた、上述の目的関数に観測確率をスパースにするような重みλを乗じた制約項Σ_jＨ(b_j)を加えるという方式以外の方式で一状態一観測制約を実現することも可能である。このような方式の例としてスプリットアルゴリズムを適用する例が考えられる。

図１０と図１１は、スプリットアルゴリズムを説明する図である。図１０と図１１では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。

図１０は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１０の例は、ノードＳ１０、ノードＳ２０、ノードＳ３０が存在する場合の例を示している。この例の場合、エージェントは、ノードＳ１０で十字路のパーツ（図２のパーツ１５）を１００％の確率で観測し、ノードＳ１０において右方向に移動するアクションを実行するとエージェントは１００％の確率でノードＳ２０に移動（遷移）する。

また、ノードＳ２０では、図２のパーツ７とパーツ１３が、それぞれ５０％の確率で観測される。ノードＳ２０において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、ノードＳ２０において左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。

さらに、ノードＳ３０では、図２のパーツ５が１００％の確率で観測され、ノードＳ３０において左方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。

なお、図１０（図１１も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１０に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにスプリットアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１１に示されるように変化する。

図１１は、図１０に対応する状態遷移確率テーブルと観測確率テーブルの内容にスプリットアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。

図１１の例では、ノードＳ１０、ノードＳ２１、ノードＳ２２、ノードＳ３０が存在する。すなわち、図１０のノードＳ２０が図１１においてノードＳ２１とノードＳ２２に分割（スプリット）されたのである。この例の場合、ノードＳ１０では図２のパーツ１５が１００％の確率で観測され、ノードＳ１０において右方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。

また、ノードＳ２１では図２のパーツ７が１００％の確率で観測され、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。

ノードＳ２２では図２のパーツ１３が１００％の確率で観測され、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、左方向に移動するアクションを実行すると１００％の確率でノードＳ１０に遷移する。

さらに、ノードＳ３０では、図２のパーツ５が１００％の確率で観測され、ノードＳ３０において左方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。

このように、スプリットアルゴリズムを適用することにより、一状態一観測制約を実現することが可能である。

すなわち、スプリットアルゴリズムの適用は、期待値最大化法で求められた局所最適解に対して一状態一観測制約を適用し、修正された解に対して再度期待値最大化法に基づく局所最適化を施す処理を繰り返すことで、最終的に一状態一観測制約を満たす局所最適解を求める処理になる。

なお、図１０と図１１を参照して上述した例では、各ノードで観測される観測シンボルの観測確率が１００％とされるように分割されると説明したが、実際には、観測シンボルの観測確率が１００％とされることは稀である。一状態一観測制約は、厳密な意味で１つのノードで観測される観測シンボルが常に１つに限られるようにするものではないからである。すなわち、一状態一観測制約は、１つのノードで観測される観測シンボルが複数ある場合でも、そのうち１つの観測シンボルの観測確率が閾値以上となるようにするものである。

図９の学習器３４により内部モデルデータに対してスプリットアルゴリズムが適用される場合の処理について、図１２のフローチャートを参照して説明する。

ステップＳ１０１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている観測確率テーブルを参照し、観測確率b_jの最大値が閾値th1以下のノードs_jを1つ探す。

ステップＳ１０２において、学習器３４は、ステップＳ１０１の処理の結果、最大値が閾値th1以下のノードs_jが見つかったか否かを判定し、見つかったと判定された場合、処理は、ステップＳ１０３に進む。

ステップＳ１０３において、学習器３４は、観測確率テーブルを参照し、ステップＳ１０２で見つかったと判定されたノードs_jにおける各観測シンボルの観測確率をチェックする。そして、学習器３４は、ノードs_jおいて、観測確率が閾値th2以上となる観測シンボルの数をカウントし、それらの観測シンボルをリストする。

例えば、Ｋ個の観測確率が閾値th2以上となる観測シンボルが存在する場合、観測シンボルo_k(k = 1， ・・・，K)がリストされる。

ステップＳ１０４において、学習器３４は、ノードs_jをＫ個に分割する。

このとき、ノードs_jが分割された後の観測確率テーブルにおける観測確率および状態遷移確率テーブルにおける状態遷移確率は、次のようにして設定される。

ノードs_jが分割された結果得られるＫ個のノードのうちの第ｋ番目のノードを、s_j ^kと表すこととし、ノードs_j ^kで観測される各観測シンボルの観測確率のそれぞれを要素とするベクトルをb_j ^kと表すことにする。

ステップＳ１０４において、学習器３４は、ベクトルb_j ^kを、観測シンボルo_kに対する観測確率だけが突出して大きく（１に極めて近く）、その他の観測シンボルに対する観測確率はきわめて微小な範囲の一様乱数となるように設定する。

また、ノードs_jが分割される前のノードs_iからノードs_jへの状態遷移確率をａ_ijで表すこととし、ノードs_jが分割された後のノードs_iからノードs_j ^kへの状態遷移確率をa^k _ijで表すことにする。

ステップＳ１０４において、学習器３４は、状態遷移確率をa^k _ijが、分割前の状態遷移確率a_ijを分割前の各観測シンボルの観測確率の比で案分されたものとなるように設定する。

さらに、ノードs_jが分割される前のノードs_jからノードs_iへの状態遷移確率をａ_jiで表すこととし、ノードs_jが分割された後のノードs_j ^kからノードs_iへの状態遷移確率をa^k _jiで表すことにする。

ステップＳ１０４において、Ｋ個の状態遷移確率a^k _jiのそれぞれに、状態遷移確率ａ_jiを設定する。

このようにして、スプリットアルゴリズムの適用の処理が実行される。

次に、アクション遷移制約について説明する。アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約である。

アクション遷移制約は、あるノードs_iから、同一のアクションc_kによって遷移可能な遷移先のノードs_j(j=1，・・・ ， J)、またはノードs_iへ同一のアクションc_kによって遷移可能な遷移元のノードs_j(j=1，・・・，J)では、それぞれ異なる観測シンボルo_j(j=1，・・・，J)が観測されるべきであるという制約である。前者をforward制約、後者をbackward制約と称する。すなわち、アクション遷移制約の下では、同一のアクションc_kによって遷移可能な複数の遷移先（または遷移元）のノードにおいて、同一の観測シンボルが観測されることは許容されないのである。なお、アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションc_kによって遷移可能な遷移先のノードが複数存在することは許容される。

アクション遷移制約を実現する方式の例としてフォワードマージアルゴリズムおよびバックワードマージアルゴリズムを適用する例が考えられる。

図１３と図１４は、フォワードマージアルゴリズムを説明する図である。

図１３と図１４では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。

図１３は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１３の例は、ノードＳ１０、ノードＳ２１、ノードＳ２２、ノードＳ３１、ノードＳ３２が存在する場合の例を示している。この例の場合、ノードＳ１０において右方向に移動するアクションを実行すると５０％の確率でノードＳ２１に遷移し、５０％の確率でノードＳ２２に遷移する。

ノードＳ２１では、図２のパーツ５が１００％の確率で観測され、ノードＳ２２でも図２のパーツ５が１００％の確率で観測される。

さらに、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３１に遷移し、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３２に遷移する。

なお、図１３（図１４も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１３に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにフォワードマージアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１４に示されるように変化する。

図１４は、図１３に対応する状態遷移確率テーブルと観測確率テーブルの内容にフォワードマージアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。

図１４の例では、ノードＳ１０、ノードＳ２０、ノードＳ３１、ノードＳ３２が存在する。すなわち、図１３のノードＳ２１とノードＳ２２が図１４のノードＳ２０に併合（マージ）されたのである。この例の場合、ノードＳ２０では図２のパーツ５が１００％の確率で観測され、ノードＳ１０において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。

また、ノードＳ２０において右方向に移動するアクションを実行すると５０％の確率でノードＳ３１に遷移し、５０％の確率でノードＳ３２に遷移する。

このように、フォワードマージアルゴリズムを適用することにより、アクション遷移制約のうちのforward制約を実現することが可能である。

つまり、アクション遷移制約の下では、同一のアクションc_kによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測されることは許容されないので、図１３のノードＳ２１とノードＳ２２が図１４のノードＳ２０にマージされたのである。なお、仮にノードＳ１０において右方向に移動するアクションを実行することにより遷移するノードＳ２３が存在した場合、ノードＳ２３でパーツ５以外のパーツが観測されるときは、ノード２３がマージの対象となることはない。アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションc_kによって遷移可能な遷移先のノードが複数存在することは許容されるからである。

すなわち、１つのノードにおいて所定のアクションを実行した場合に遷移し得る遷移先ノードのそれぞれでの観測確率分布が類似するノードを発見し、発見されたノードが併合（マージ）されるのである。

なお、図１３と図１４を参照して上述した例では、所定の観測シンボルが観測されるノードへの状態遷移確率が１００％とされるようにマージされると説明したが、実際には、状態遷移確率が１００％とされることは稀である。forward制約は、厳密な意味で同一のアクションc_kによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測されることは許容しないものではないからである。

図９の学習器３４により内部モデルデータに対してフォワードマージアルゴリズムが適用される場合の処理について、図１５のフローチャートを参照して説明する。

ステップＳ１２１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルを参照し、ある１つのアクションc_kの状態遷移確率テーブルをチェックする。

ステップＳ１２２において、学習器３４は、ステップＳ１２１の処理でチェックした状態遷移確率テーブルの中で、ある１つの遷移元ノードs_iを特定し、ノードs_iから各遷移先ノードへの状態遷移確率を要素とするベクトルa_ij(k)をチェックする。そして、学習器３４は、状態遷移確率の値が閾値以上となった遷移先ノードs_jをリストする。

ステップＳ１２３において、学習器３４は、ステップＳ１２２の処理でリストされた遷移先ノードを観測シンボル毎に分類する。

なお、上述したように、アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約だから、遷移先ノードで観測される観測シンボルは、ほぼ１つに特定することが可能である。

ステップＳ１２４において、学習器３４は、ステップＳ１２３の処理で分類された同一の観測シンボルのノードをマージする。

すなわち、ステップＳ１２３の処理でマージされた、観測シンボルmに対応するノード群を、s_j ^m，l(l = 1，・・・，L)で表すものとし、Ｌ個のノードs_j ^m，lを１つのノードs_j ^mにマージするのである。

このとき、Ｌ個のノードs_j ^m，lが１つのノードs_j ^mにマージされた後の状態遷移確率テーブルにおける状態遷移確率および観測確率テーブルにおける観測確率は、次のようにして設定される。

ノードs_iからノードs_j ^mへの状態遷移確率a_ij ^mは、式（１４）により求められて設定される。

・・・（１４）
ここで、a_ij ^m，lは、マージされる前のノードs_iから１個のノードs_j ^m，lへの状態遷移確率を表すものとする。

ノードs_j ^mからノードs_iへの状態遷移確率a_ji ^mは、a_ji ^m，lの単純平均、またはΣ_ka_kj ^m，lによる重み付き平均として求められて設定される。

Ｌ個のノードs_j ^m，lが１つのノードs_j ^mにマージされた後のノードs_j ^mにおける観測シンボルmの観測確率b_j ^mは、b_j ^m，lの単純平均、またはΣ_ka_kj ^m，lによる重み付き平均として求められて設定される。

ステップＳ１２４では、このように、状態遷移確率a_ij ^m、状態遷移確率a_ji ^m、観測確率b_j ^mが設定される。

このようにして、フォワードマージアルゴリズムの適用の処理が実行される。

図１６と図１７は、バックワードマージアルゴリズムを説明する図である。

図１６と図１７では、図中の円でノードが示されており、各ノードで観測されるシンボルとして図２を参照して上述したパーツの図形が表示されている。

図１６は、エージェントの学習の結果得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図１６の例は、ノードＳ１１、ノードＳ１２、ノードＳ２１、ノードＳ２２、ノードＳ３０が存在する場合の例を示している。この例の場合、ノードＳ１１において右方向に移動するアクションを実行すると１００％の確率でノードＳ２１に遷移する。ノードＳ１２において右方向に移動するアクションを実行すると１００％の確率でノードＳ２２に遷移する。

また、ノードＳ２１では、図２のパーツ７が１００％の確率で観測される。ノードＳ２２では、図２のパーツ７が１００％の確率で観測される。

さらに、ノードＳ２１において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移し、ノードＳ２２において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移する。

なお、図１６（図１７も同じ）は、状態遷移確率テーブルと観測確率テーブルの内容を可視化したものであり、実際には、図１６に対応する状態遷移確率テーブルと観測確率テーブルが内部モデルデータとして学習されている。このような内部モデルデータにバックワードマージアルゴリズムを適用すると、状態遷移確率テーブルと観測確率テーブルの内容は、図１７に示されるように変化する。

図１７は、図１６に対応する状態遷移確率テーブルと観測確率テーブルの内容にバックワードマージアルゴリズムを適用した場合に得られる状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。

図１７の例では、ノードＳ１１、ノードＳ１２、ノードＳ２０、ノードＳ３０が存在する。すなわち、図１６のノードＳ２１とノードＳ２２が図１７のノードＳ２０に併合（マージ）されたのである。この例の場合、ノードＳ２０では図２のパーツ７が１００％の確率で観測される。

また、ノードＳ１１において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移し、ノードＳ１２において右方向に移動するアクションを実行すると１００％の確率でノードＳ２０に遷移する。

さらに、ノードＳ２０において右方向に移動するアクションを実行すると１００％の確率でノードＳ３０に遷移する。

このように、バックワードマージアルゴリズムを適用することにより、アクション遷移制約のうちのbackward制約を実現することが可能である。

つまり、アクション遷移制約の下では、同一のアクションc_kによって遷移可能な複数の遷移元のノードにおいて、同一の観測シンボルが観測されることは許容されないので、図１６のノードＳ２１とノードＳ２２が図１７のノードＳ２０にマージされたのである。なお、仮に右方向に移動するアクションを実行することによりノードＳ３０に遷移するノードＳ２３が存在した場合、ノードＳ２３でパーツ７以外のパーツが観測されるときは、ノード２３がマージの対象となることはない。アクション遷移制約の下でも、異なる観測シンボルを観測するノードであれば、同一のアクションc_kによって遷移可能な遷移元のノードが複数存在することは許容されるからである。

すなわち、1つのノードに対して、共通のアクションによって遷移してくる遷移元ノードのそれぞれでの観測確率分布が類似するノードを発見し、発見されたノードが併合されるのである。

図９の学習器３４により内部モデルデータに対してバックワードマージアルゴリズムが適用される場合の処理について、図１８のフローチャートを参照して説明する。

ステップＳ１４１において、学習器３４は、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルを参照し、ある１つのアクションc_kの状態遷移確率テーブルをチェックする。

ステップＳ１４２において、学習器３４は、ステップＳ１４１の処理でチェックした状態遷移確率テーブルの中で、ある１つの遷移先ノードs_jを特定し、ノードs_jへの各遷移元ノードからの状態遷移確率を要素とするベクトルa_ij(k)をチェックする。そして、学習器３４は、状態遷移確率の値が閾値以上となった遷移元ノードs_iをリストする。

ステップＳ１４３において、学習器３４は、ステップＳ１４２の処理でリストされた遷移元ノードを観測シンボル毎に分類する。

なお、上述したように、アクション遷移制約は、一状態一観測制約が課されていることを前提とした制約だから、遷移元ノードで観測される観測シンボルは、ほぼ１つに特定することが可能である。

ステップＳ１４４において、学習器３４は、ステップＳ１４３の処理で分類された同一の観測シンボルのノードをマージする。

すなわち、ステップＳ１４３の処理でマージされた、観測シンボルmに対応するノード群を、s_i ^m，l(l=1，・・・，L)で表すものとし、Ｌ個のノードs_i ^m，lを１つのノードs_i ^mにマージするのである。

このとき、Ｌ個のノードs_i ^m，lが１つのノードs_i ^mにマージされた後の状態遷移確率テーブルにおける状態遷移確率および観測確率テーブルにおける観測確率は、次のようにして設定される。

ノードs_jへのノードs_i ^mからの状態遷移確率a_ij ^mは、a_ji ^m，lの単純平均、またはΣ_ka_ki ^m，lによる重み付き平均として求められて設定される。

ノードs_jからのノードs_i ^mへの状態遷移確率a_ji ^mは、Σ_la_ji ^m，lにより求められて設定される。

Ｌ個のノードs_i ^m，lが１つのノードs_i ^mにマージされた後のノードs_i ^mにおける観測シンボルmの観測確率b_i ^mは、b_i ^m，lの単純平均、またはΣ_ka_ki ^m，lによる重み付き平均として求められて設定される。

ステップＳ１２４では、このように、状態遷移確率a_ij ^m、状態遷移確率a_ji ^m、観測確率b_j ^mが設定される。

このようにして、バックワードマージアルゴリズムの適用の処理が実行される。

このように一状態一観測制約およびアクション遷移制約を課すことで、学習処理の負荷を軽減することが可能となる。

図１９は、アクション拡張型ＨＭＭにおける状態遷移確率テーブルと観測確率テーブルの尤度を比較する表である。同図の最も左側の列は、学習の回数（試行回数）を表している。試行回数の右側の列は、「最初の学習」の列とされており、それぞれの試行回数時に学習された状態遷移確率テーブルと観測確率テーブルの尤度の値が記述されている。「最初の学習」の右側の列は、「スプリット・マージ後」の列とされている。この列には、「最初の学習」によって得られた状態遷移確率テーブルと観測確率テーブルに対して、図１２、図１５、および図１８の処理を施すことにより得られた状態遷移確率テーブルと観測確率テーブルの尤度の値が記述されている。さらに、「スプリット・マージ後」の右側の列は、「増分」の列とされている。この列には、「スプリット・マージ後」の列に記述された尤度値と「最初の学習」の列に記述された尤度値との差分が記述されている。

図１９に示されるように、図１２、図１５、および図１８の処理を施すことにより尤度が向上することが分かる。また、図１２、図１５、および図１８の処理を施すことにより、尤度値は、「−６０」付近の値をとる回数が多くなることが分かる。つまり、尤度値は、「−６０」付近の値をとるような学習が行われた場合、与えられた環境を最も適切に学習したといえる。これに対して、「最初の学習」の列に記述された尤度は、学習の都度、値が大きく変化しており、学習を繰り返しても与えられた環境を最も適切に学習することは困難であることが判る。

すなわち、一状態一観測制約とアクション遷移制約を課すことで、アクション拡張型ＨＭＭの学習の精度を高めることができるのである。

図２０乃至図２６は、一状態一観測制約とアクション遷移制約を課すことによる学習結果の変化を説明する図である。

ここでは、図２０に示される迷路において、図中円で示される位置のパーツを変更し、図２１に示されるような構造に変化させた迷路を環境としてエージェントに学習させる場合を例として説明する。

図２２は、図２０と図２１に示される環境を学習したエージェントの状態遷移確率テーブルと観測確率テーブルの内容を可視化した図である。図２２の例では、図中の円でノードが示されており、図中の三角形で表現された方向のアクションにより遷移するノードが線により接続されている。また、図中の円の内部にしめされた番号が、その円で示されるノードのインデックスを表している。図２２の例は、一状態一観測制約とアクション遷移制約を課すことなく得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図とされる。

これに対して、図２３は、図２２に対応する状態遷移確率テーブルと観測確率テーブルに、一状態一観測制約とアクション遷移制約を課す処理を施すことにより得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化した図とされる。

図２３においては、図２２のノード２８がノード２８とノード３１に分割されている。また、図２３においては、図２２のノード１７とノード１９がノード７にマージされている。さらに、図２３においては、図２２のノード１２とノード２５がノード１２にマージされている。

なお、エージェントが学習のために迷路上を移動していた時間帯において、迷路が図２０に示される構造とされていた時間帯と、迷路が図２１に示される構造とされていた時間帯とが存在する。従って、図２３に示される各ノードの位置が完全に、図２０または図２１のパーツの位置と一致するものではない。例えば、図２３のノード２４、ノード３６、ノード２、ノード１８によって、迷路の構造が時間帯によって変化し得ることが適切に学習されていることが分かる。

実際には、迷路の規模はさらに大きいものとされる。例えば、図２４に示されるような迷路を環境としてエージェントに学習させる。この場合、一状態一観測制約とアクション遷移制約を課すことなく得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化すると図２５に示されるようになる。これに対して、一状態一観測制約とアクション遷移制約を課すことにより得られた状態遷移確率テーブルと観測確率テーブルの内容を可視化すると図２６に示されるようになる。

図２５と比較して、図２６は、現実の迷路（図２４）の構造に近いものとなっていることが分かる。

ここまで、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うために必要となる技術について説明した。

次に、ここまで説明してきた、図９の学習器３４によるアクション拡張型ＨＭＭの学習処理について、図２７のフローチャートを参照して説明する。

ステップＳ１６１において、学習器３４は、初期の内部モデルデータを取得する。ここで、初期の内部モデルデータは、例えば、ロボットが迷路上を移動することで生成された直後の状態遷移確率テーブルと観測確率テーブルとされる。状態遷移確率テーブルと観測確率テーブルに設定される状態遷移確率と観測確率は、例えば、各時刻においてロボットが実行したアクションと、そのアクションを実行した結果観測された観測シンボルとの組み合わせからなる情報に基づいて生成される。

ステップＳ１６２において、学習器３４は、ステップＳ１６１の処理で取得した内部モデルデータを最適化する。このとき、例えば、最尤推定法などにより、状態遷移確率テーブルの各値と観測確率テーブルの各値が最適化されるように変更される。

ステップＳ１６３において、学習器３４は、ステップＳ１６２の処理で最適化された内部モデルデータが、上述した一状態一観測制約、およびアクション遷移制約を満たすか否かを判定する。

例えば、１つのノードで観測される観測シンボルが複数ある場合でも、そのうち１つの観測シンボルの観測確率が閾値以上となる場合、一状態一観測制約を満たすことになる。また、例えば、同一のアクションによって遷移可能な複数の遷移先のノードにおいて、同一の観測シンボルが観測される確率が閾値以下となる場合、アクション遷移制約を満たすことになる。

ステップＳ１６３において、内部モデルデータが、上述した一状態一観測制約、およびアクション遷移制約を満たさないと判定された場合、処理は、ステップＳ１６４に進む。

ステップＳ１６４において、学習器３４は、一状態一観測制約、およびアクション遷移制約を満たすように、内部モデルデータを変更する。このとき、例えば、図１２、図１５、および図１８を参照して上述した処理が実行されることにより、状態遷移確率テーブルの各値と観測確率テーブルの各値が変更される。

ステップＳ１６４の処理の後、処理は、ステップＳ１６２に戻る。そして、ステップＳ１６３において、一状態一観測制約、およびアクション遷移制約を満たすと判定されるまで、ステップＳ１６２乃至ステップＳ１６４の処理が繰り返し実行される。

ステップＳ１６３において、一状態一観測制約、およびアクション遷移制約を満たすと判定された場合、処理は、ステップＳ１６５に進む。

ステップＳ１６５において、学習器３４は、内部モデルデータを、内部モデルデータ記憶部３７に保存する。

このようにして、アクション拡張型ＨＭＭの学習処理が実行される。

ところで、ＨＭＭの学習の方式として、バッチ学習方式と追加学習方式が存在する。ここで、バッチ学習方式は、例えば、１万ステップの遷移と観測のデータが得られる場合、１万ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存するものである。これに対して、追加学習方式は、例えば、最初に、１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルを生成して保存する。そして、その後の１千ステップの遷移と観測に基づいて状態遷移確率テーブルと観測確率テーブルの各値を変更して保存し、・・・というように、繰り返し学習を行って、内部モデルデータを更新（アップデート）していくものである。

例えば、迷路上を自走するロボットによるアクション拡張型ＨＭＭの学習などの場合、追加学習方式での学習を行うことが求められる。バッチ学習方式での学習では、迷路の構造の変化などを適応的に学ぶことが原理的に不可能であり、変化する環境の中でより良い性能を発揮するためには、動作結果をフィードバックする追加学習方式による学習が必須となるからである。

ところが、追加学習を行なう際に「学習済みの記憶構造」と「新しい経験」とをどのように統合するのかという問題は未解決である。一方では「新しい経験」を速やかに反映させてすばやい適応を実現したいという要請もあるが、他方、これまでに確立した記憶構造が破壊される危険性もある。

例えば、図２８に示されるような迷路の構造を学習するロボットが、１度学習して内部モデルデータを保存した後、図中の円１０１で示される範囲内を長時間移動し続けた場合、円１０２で示される範囲の位置に対応する内部モデルデータが破壊されることがある。すなわち、せっかく適切に学習されて記憶されていた円１０２で示される範囲の位置に対応する内部モデルデータが誤って更新されることがある。追加学習方式の学習では、新しく得られた遷移と観測に基づいてのみ、内部モデルデータが更新されるので、円１０１で示される範囲内の位置が誤って、円１０２で示される範囲の位置に対応するノードと認識されることがあるからである。

このような問題に対処するために、例えば、従来、追加学習方式での学習を行うために、内部モデルデータを迷路の各範囲に対応させて分離して保持するなどされていた。あるいはまた、過去の学習により得られた内部モデルデータを現在の記憶からリハースする等して、学習することが行われていた。

しかしながら、従来の方式を採用しても、例えば、分離された過去の内部モデルデータに、「新しい体験」が反映されなかったり、リハースされる過去の内部モデルデータが、「新しい体験」の影響を受けて生成されてしまうなどの問題があった。このように、従来の方式では、大規模なＨＭＭの学習において、追加学習を行って実用的なモデルとして機能させることは困難であった。例えば、過去の学習に用いられたデータと、新たな学習に用いられるデータとをまとめてバッチ学習するようにすれば、適切な学習結果を得ることができるが、これを実現するには、膨大な記憶容量と計算量が求められることになる。

次に、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにするための技術について説明する。

本発明においては、学習器３４が、次のような追加学習方式による学習を行い、変化する環境の中でより良い性能を発揮でき、かつ安定的な学習を行うことができるようにする。具体的には、後述する状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを算出して保存することにより、アクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにする。

バッチ学習方式による学習は、換言すれば、複数の時間帯において得られた遷移と観測に基づく学習を足し合わせたものということもできる。例えば、図２９に示されるように、バッチ学習方式の学習で用いられる遷移と観測の全体データＤＡが構成されていると考えられる。すなわち、全体データＤＡは、第１の時間帯において得られたデータセットＤ１と、第２の時間帯において得られたデータセットＤ２と、第３の時間帯において得られたデータセットＤ３と、・・・により構成されていると考えられる。

アクション拡張型ＨＭＭの学習における状態遷移確率の推定は、上述した式（３）により行なわれるが、ここでは、図２９に示されるように、複数のデータセットが存在している場合を考える。

第ｎ番目の学習データセットDnにおける状態遷移確率の推定値a´_ij(k)⁽ⁿ⁾は、式（１５）により求めることができる。

・・・（１５）

ここで、状態遷移確率の推定の説明において、t∈Dnは、特に言及がない場合、この表記により（t，t+1∈Dn）を表すものとする。また、学習データセットDnには、各時刻において実行したアクション、各時刻におけるノード、各時刻における観測シンボルを表す情報が含まれているものとする。

式（１５）における分子は、学習データセットDnの中で、アクションc_kを実行することにより、ノードiからノードjに遷移した頻度を表すものと言える。一方、式（１５）の分母は、学習データセットDnの中で、アクションc_kを実行することにより、ノードiから他のノードに遷移した頻度を表すものと言える。

いま、式（１５）における分子に対応する式を表す変数χ_ij(k)⁽ⁿ⁾を式（１６）で示されるものとして定義する。

・・・（１６）

式（１６）より式（１７）を得ることができる。

・・・（１７）

式（１７）と式（１５）より式（１８）が導出される。

・・・（１８）

このように、状態遷移確率の推定値は、変数χ_ij(k)⁽ⁿ⁾を用いて表すことができるのである。

ここで、変数χ_ij(k)⁽ⁿ⁾は、式（１５）における分子に相当し、学習データセットDnの中で、アクションc_kを実行することにより、ノードiからノードjに遷移した頻度を表すものと言えるから、状態遷移確率の推定のための頻度変数と称することにする。

本発明では、追加学習方式の学習を行う場合、安定的な学習を行うことができるようにするために、上述した頻度変数χ_ij(k)⁽ⁿ⁾を用いて状態遷移確率の推定値を求めることにする。すなわち、学習器３４が、１つの学習データセットに基づく学習を行う都度、頻度変数を更新して内部モデルデータの１つとして内部モデルデータ記憶部３７に記憶させて保存するようにする。

つまり、新たに学習を行う際に、過去の学習データセットに対応する頻度変数を読み出して、その頻度変数に新たな学習に基づいて得られた頻度変数を足しこむことにより頻度変数の値を更新する。さらに、更新された頻度変数に基づいて得られる状態遷移確率の推定値を求めることにより、追加学習方式の学習を行うのである。このようにすることで、学習データセットＤ１，Ｄ２，Ｄ３・・・をまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。

次に、複数回の学習により得られたそれぞれの内部モデルデータの統合について説明する。すなわち、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎ・・・に基づいて計算される状態遷移確率の推定値a´_ij(k)⁽¹⁾，a´_ij(k)⁽²⁾，・・・a´_ij(k)⁽ⁿ⁾，・・・の統合について説明する。

このような場合、例えば、重みw_n(Σw_n=1)を設定し、式（１９）に示されるように、状態遷移確率の推定値a´_ij(k)⁽¹⁾，a´_ij(k)⁽²⁾，・・・a´_ij(k)⁽ⁿ⁾，・・・を統合することも考えられる。

・・・（１９）

式（１９）は、上述した状態遷移確率の推定値のそれぞれに、各学習データセットに対応する重みw₁，w₂，・・・，w_n，・・・を乗じて足し合わせることを意味している。

しかしながら、上述したように本発明では、学習データセットに対応する頻度変数に基づいて得られる状態遷移確率の推定値を求めるようにしたので、式（１９）による統合は適さない。

本発明では、学習データセットに対応する頻度変数に基づいて得られる状態遷移確率の推定値を求めるようにしたので、それぞれの状態遷移確率の推定値の信頼性を考慮して統合を行う必要がある。すなわち、学習データセットのデータ量（シーケンス長）を考慮して重みを設定する必要がある。

また、学習データセットに対応する頻度変数は、過去の学習に基づいて既に設定されている状態遷移確率の値によって変化し得る。例えば、状態遷移確率の値が低い遷移が数多く発生した学習データセットから得られる頻度変数の値は必然的に小さい値となり易く、状態遷移確率の値が高い遷移が数多く発生した学習データセットから得られる頻度変数の値は必然的に大きい値となり易い。上述したように頻度変数は、式（１５）における分子に対応する式で表されるからである。従って、頻度変数の値の大きさも考慮して重みを設定する必要がある。

本発明では、統合後の状態遷移確率の推定値a´_ij(k)を式（２０）により求めるようにする。

・・・（２０）

このとき、上述したように重みw_nの考慮が必要となる。具体的には、シーケンス長Tnの学習データセットDnに対応する頻度変数χ_ij(k)⁽ⁿ⁾について、式（２１）に示される関係を満たすように重みw_nを設定する。

・・・（２１）

このように、学習データセットごとに、その学習データセットのシーケンス長に応じた重みの調整を行いながら、頻度変数χ_ij(k)⁽ⁿ⁾をすべてのデータセットに渡って累積すれば、全データをまとめてバッチ学習するのとほぼ同等の結果を得ることができる。すなわち、式（２２）により、頻度変数χ_ij(k)を求め、式（２０）を参照して上述したように、頻度変数χ_ij(k)を用いて統合後の状態遷移確率の推定値a´_ij(k)を求めるのである。

・・・（２２）

このようにすることで、例えば、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎ・・・のそれぞれに対応する状態遷移確率テーブルを保存するなどしなくても、全ての学習データセットをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。すなわち、既に記憶されている、学習データセットＤ_ｎ-1までを学習することにより得られた頻度変数に、学習データセットＤ_nを学習することにより得られた頻度変数を足しこんで状態遷移確率の推定値を求める。これにより、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。

一方、アクション拡張型ＨＭＭの学習における観測確率の推定は、上述した式（４）により行なわれるが、ここでは、図２９に示されるように、複数のデータセットが存在している場合を考える。

第ｎ番目の学習データセットDnにおける観測確率の推定値b´_j(o)⁽ⁿ⁾は、式（２３）により求めることができる。

・・・（２３）

なお、状態遷移確率の推定の説明の場合と異なり、ここでは、t∈Dnの表記により（t，t+1∈Dn）を表すものではない。

また、学習データセットDnには、各時刻において実行したアクション、各時刻におけるノード、各時刻における観測シンボルを表す情報が含まれているものとする。o_t=oは、時刻tにおける観測シンボルがoであることを表している。

式（２３）における分子は、学習データセットDnの中で、ノードjにおいて観測シンボルｏが観測された頻度を表すものと言える。一方、式（２３）の分母は、学習データセットDnの中で、ノードjにおいていずれかの観測シンボルが観測された頻度を表すものと言える。

いま、式（２３）における分子に対応する式を表す変数ω_j(o)⁽ⁿ⁾を式（２４）で示されるものとして定義する。

・・・（２４）

式（２４）より式（２５）を得ることができる。

・・・（２５）

式（２５）と式（２３）より式（２６）が導出される。

・・・（２６）

このように、観測確率の推定値は、変数ω_j(o)⁽ⁿ⁾を用いて表すことができるのである。

ここで、変数ω_j(o)⁽ⁿ⁾は、式（２３）における分子に相当し、学習データセットDnの中で、ノードjにおいて観測シンボルｏが観測された頻度を表すものと言えるから、観測確率の推定のための頻度変数と称することにする。

本発明では、状態遷移確率の場合と同様に、追加学習方式の学習を行う場合、安定的な学習を行うことができるようにするために、上述した変数ω_j(o)⁽ⁿ⁾を用いて観測確率の推定値を求めることにする。すなわち、学習器３４が、１つの学習データセットに基づく学習を行う都度、頻度変数更新して内部モデルデータの１つとして内部モデルデータ記憶部３７に記憶させて保存するようにする。

そして、新たに学習を行う際に、過去の学習データセットに対応する頻度変数を読み出して、その頻度変数に新たな学習に基づいて得られた頻度変数を足しこむことにより頻度変数の値を更新する。さらに、更新された頻度変数に基づいて得られる観測確率の推定値を求めることにより、追加学習方式の学習を行うのである。

次に、複数回の学習により得られたそれぞれの内部モデルデータの統合について説明する。すなわち、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎ・・・に基づいて計算される観測確率の推定値b´_j(o)⁽¹⁾，b´_j(o)⁽²⁾，・・・b´_j(o)⁽ⁿ⁾，・・・の統合について説明する。

統合にあたって、状態遷移確率の推定値の統合の場合と同様の理由で、重みw´_nの考慮が必要となる。

本発明では、統合後の状態遷移確率の推定値b´_j(o)を式（２７）により求めるようにする。

・・・（２７）

このとき、シーケンス長Tnの学習データセットDnに対応する頻度変数ω_j(o)⁽ⁿ⁾について、式（２８）に示される関係を満たすように重みw´_nを設定する。

・・・（２８）

このように、学習データセットごとに、その学習データセットのシーケンス長に応じた重みの調整を行いながら、頻度変数ω_j(o)⁽ⁿ⁾をすべてのデータセットに渡って累積すれば、全データをまとめてバッチ学習するのとほぼ同等の結果を得ることができる。すなわち、式（２９）により、頻度変数ω_j(o)を求め、式（２７）を参照して上述したように、頻度変数ω_j(o)を用いて統合後の観測確率の推定値b´_j(o)を求めるのである。

・・・（２９）

このようにすることで、例えば、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎ・・・のそれぞれに対応する観測確率テーブル、状態遷移確率テーブルを保存するなどしなくても、全ての学習データセットをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。すなわち、既に記憶されている、学習データセットＤ_ｎ-1までを学習することにより得られた頻度変数に、学習データセットＤ_nを学習することにより得られた頻度変数を足しこんで観測確率の推定値を求める。これにより、学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎをまとめてバッチ学習するのとほぼ同等の結果を得ることができるのである。

例えば、式（１５）または式（２３）の計算結果をそのまま保存して追加学習方式による学習を行っても学習データセットＤ_１，Ｄ_２，・・・Ｄ_ｎをまとめてバッチ学習するのとほぼ同等の結果を得ることはできない。式（１５）または式（２３）の計算結果は、確率の値として算出されるものであり、あり得る遷移の確率の合計値が１となるように正規化されているからである。仮に、式（１５）または式（２３）の計算結果をそのまま保存して、追加学習方式による学習を行っても、まとめてバッチ学習するのとほぼ同等の結果を得ることができるようにするためには、例えば、学習データセットのそれぞれに対応するテーブルを保存するなどの必要がある。このため、本発明では、式（１５）または式（２３）における分子に対応する式により得られる頻度変数を保存するようにしたのである。

このようにして、状態遷移確率と観測確率を求めるようにすれば、追加学習方式による学習を行って、変化する環境の中でより良い性能を発揮できるとともに、安定的な学習を行うことができるようになる。

また、そのようにするために、過去の学習のそれぞれに対応する内部モデルデータを全て保存するなどの必要がなく、例えば、内部モデルデータ記憶部３７の記憶容量を小さいものとすることができる。さらに、追加学習方式による学習の結果、内部モデルデータを更新する際の演算量を少なくすることができ、環境の変化をより迅速に認識させるようにすることが可能となる。

ここまでの追加学習方式に関する説明は、離散観測信号を取得する場合の例について説明した。連続観測信号を取得する場合は、時刻tにおいてエージェントが状態jにいる場合の重み係数γ_t(j）よって重み付けた信号分布を用いて、観測確率密度関数b_j(o)のパラメータを再推定すればよい。このとき、重み係数γ_t(j）が式（３０）を満たすように調整する必要がある。

・・・（３０）

いまの場合、γ′_t(j)が頻度相当の意味を有するものとなる。

そして、γ′_t(j) ≡ w′_nγ_t(j)を用いて観測信号の平均ベクトルおよび共分散行列を推定すればよい。

通常は、ガウス分布などの対数凹又は楕円型対称確率密度をモデルとして用い、観測確率密度関数b_j(o)のパラメータの再推定を行うことができる。

ガウス分布などの対数凹又は楕円型対称確率密度のモデルのパラメータとしては、状態jにおける観測信号の平均ベクトルμ´_jおよび共分散行列U´_jを用いることができる。平均ベクトルμ´_jおよび共分散行列U´_jは、それぞれ、式（３１）および式（３２）により求めることができる。

・・・（３１）

・・・（３２）

以上に説明した通り、追加学習方式による学習時の安定性を確保することができるが、追加学習方式の場合、直近の学習結果により大きな重みを与えて内部モデルデータを更新させることが多い。新しい経験は、環境の変化をより適切に学習するのに都合が良いと考えられるからである。

例えば、１０万サンプルからなる学習を終えた学習器に対して１００サンプルの新規データを与えて追加学習方式の学習をさせる場合を考える。既に学習したものの大きさ(１０万)に対して新たに学習するデータの量(１００)が小さいため、そのまま学習すると新たな学習の影響度は０.１％となる。このような場合、環境の変化を適切に学習しているとは言い難い。

そこで、例えば、新たな学習の影響度である学習率を指定することができれば便利である。例えば、上述の例において、学習率を０.１(１０％)と指定した場合、新たに学習するデータの量を変えることなく、影響度を１００倍にすることができる。

本発明では、上述した学習率の指定があった場合でも、学習の安定性を損なうことがないようにする。

上述したように、状態遷移確率の推定のための頻度変数χ_ij(k)は、式（３３）で示されるように更新される。なお式（３３）における⇒は、χ_ij(k)が右辺に示されるように更新されることを表している。

・・・（３３）

観測確率の推定のための頻度変数ω_j(o)は、式（３４）で示されるように更新される。なお式（３４）における⇒は、ω_j(o)が右辺に示されるように更新されることを表している。

・・・（３４）

いま、学習率ｒ(0≦r≦1)が指定された場合、本発明では、状態遷移確率の推定のための頻度変数を算出するために、式（３５）に示される重みW_nと、重みz_i(k)⁽ⁿ⁾を演算する。重みW_nと、重みz_i(k)⁽ⁿ⁾は、それぞれ新たな学習に基づいて得られた頻度変数に乗じるための重みと、既に保存されている頻度変数に乗じるための重みとして演算される。

・・・（３５）

そして、状態遷移確率の推定のための頻度変数は、式（３６）により演算される。

・・・（３６）

なお、式（３５）における重みz_i(k)⁽ⁿ⁾は、重みW_nが学習を繰り返すに従って一方的に大きくなることを考慮して設けられた重みであり、実際の演算では用いられないようにしてもよい。

また、学習率ｒ(0≦r≦1)が指定された場合、観測確率の推定のための頻度変数を算出するために、式（３７）に示される重みW´_nと、重みz_i ⁽ⁿ⁾を演算する。重みW´_nと、重みz_i ⁽ⁿ⁾は、それぞれ新たな学習に基づいて得られた頻度変数に乗じるための重みと、既に保存されている頻度変数に乗じるための重みとして演算される。

・・・（３７）

そして、状態遷移確率の推定のための頻度変数は、式（３８）により演算される。

・・・（３８）

なお、式（３７）における重みz_i ⁽ⁿ⁾は、重みW´_nが学習を繰り返すに従って一方的に大きくなることを考慮して設けられた重みであり、実際の演算では用いられないようにしてもよい。

ここまでの学習率の指定のある追加学習方式に関する説明は、離散観測信号を取得する場合の例について説明した。連続観測信号を取得する場合も同様に、対応する重み変換を行ってから分布パラメータの推定を行えばよい。

このようにすることで、学習率の指定があった場合でも、学習の安定性を損なうことがないようにすることができる。

ところで、頻度変数を用いた状態遷移確率の推定値a´ij(k)の算出については、上述したように式（２０）により求めることができるが、実際には、分母のΣ_jχ_ij(k)が小さい値となる場合、計算結果が擾乱することがある。上述した擾乱は、学習により得られる内部モデルデータの信頼性を損ねて、その後の環境の認識に影響し、エージェントが環境を誤って認識してしまう。さらに、その認識結果が、追加学習方式の学習の結果に対しても再帰的に悪影響を及ぼすため、この問題を解決する必要がある。

ここで、N_ik＝Σ_jχ_ij(k)とする。N_ikが小さい値となる場合、計算結果が擾乱するという問題を解決するためには、状態遷移確率に対するN_ikの小ささに応じたペナルティ係数を乗ずるようにすればよい。すなわち、ペナルティ係数をη(N_ik)とし、状態遷移確率の推定値a´ij(k)を、式（３９）により求めるようにすればよい。

・・・（３９）

ただし、関数η(x)は、定義域0≦xに対して値域0≦η(x)≦1を満たす単調増加関数であるものとする。

関数η(x)は、例えば、式（４０）により表される関数とされる。

・・・（４０）

式（４０）におけるα(>0)，βは、必要に応じて適切に調整されるパラメータであり、例えば、指定された学習率rに応じて調整されるようにしてもよい。

ところで、上述したように、本発明においては、内部モデルデータとして、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数とを記憶するようにした。そうすると、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対しても、上述した一状態一観測制約とアクション遷移制約を課す処理を施すことが必要となる。

状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するスプリットアルゴリズム適用の処理は、次のようにして行われる。

ここでは、ノードs_jをＫ個のノードに分割する場合の例について説明する。なお、ノードs_jが分割された結果得られるＫ個のノードのうちの第ｋ番目のノードを、s_j ^kと表すこととし、ノードs_jが分割された後のノードs_iからノードs_j ^kへの状態遷移確率をa^k _ijで表すことにする。また、ノードs_jが分割された後のノードs_j ^kからノードs_iへの状態遷移確率をa^k _jiで表すことにする。

学習器３４は、観測シンボルoについての観測確率b_j(o)に対応する観測確率の推定のための頻度変数ω_j(o)を、式（４１）により求める。

・・・（４１）

また、学習器３４は、状態遷移確率a^k _ijに対応する状態遷移確率の推定のための頻度変数χ^k _ijが、分割前の頻度変数χ_ijを分割前の各観測シンボルの観測確率に対応する観測確率の推定のための頻度変数ω_j(o_k)の比で案分されたものとなるように設定する。

さらに、学習器３４は、状態遷移確率a^k _jiに対応する状態遷移確率の推定のための頻度変数χ^k _jiが、分割前の頻度変数χ_jiを分割前の各観測シンボルの観測確率に対応する観測確率の推定のための頻度変数ω_j(o_k)の比で案分されたものとなるように設定する。

状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するフォワードマージアルゴリズム適用の処理は、次のようにして行われる。

ここでは、Ｌ個のノード群s_j ^m，l(l=1，・・・，L)を１つのノードs_j ^mにマージする場合の例について説明する。なお、マージされた後のノードs_iからノードs_j ^mへの状態遷移確率をa_ij ^mで表し、マージされた後のノードs_j ^mからノードs_iへの状態遷移確率をa_ji ^mで表すことにする。また、マージされた後の各観測シンボルの観測確率のそれぞれを要素とするベクトルを、b_j ^mで表すことにする。

学習器３４は、状態遷移確率a_ij ^mに対応する状態遷移確率の推定のための頻度変数χ_ij ^mをΣ_lχ_ij ^m，lにより求めて設定する。ここで、χ_ij ^m，lは、マージされる前のノードs_iからノードs_j ^m，lへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。

また、学習器３４は、状態遷移確率a_ji ^mに対応する状態遷移確率の推定のための頻度変数χ_ji ^mをΣ_lχ_ji ^m，lにより求めて設定する。ここで、χ_ji ^m，lは、マージされる前のノードs_j ^m，lからノードs_iへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。

さらに、学習器３４は、ベクトルb_j ^mの要素のそれぞれに対応する状態遷移確率の推定のための頻度変数のそれぞれを要素とするベクトルω_j ^mをΣ_lω_j ^m，lにより求めて設定する。

そして学習器３４は、すべてのマージが終了したら、修正された状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを用いて状態遷移確率と観測確率とを再計算する。

状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対するバックワードマージアルゴリズム適用の処理は、次のようにして行われる。

ここでは、Ｌ個のノード群s_j ^m，l(l=1，・・・，L)を１つのノードs_j ^mにマージする場合の例について説明する。なお、マージされた後のノードs_iからノードs_j ^mへの状態遷移確率をa_ij ^mで表し、マージされた後のノードs_j ^mからノードs_iへの状態遷移確率をa_ji ^mで表すことにする。また、マージされた後の各観測シンボルの観測確率のそれぞれを要素とするベクトルを、b_j ^mで表すことにする。

学習器３４は、状態遷移確率a_ij ^mに対応する状態遷移確率の推定のための頻度変数χ_ij ^mをΣ_lχ_ij ^m，lにより求めて設定する。ここで、χ_ij ^m，lは、マージされる前のノードs_iからノードs_j ^m，lへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。

また、学習器３４は、状態遷移確率a_ji ^mに対応する状態遷移確率の推定のための頻度変数χ_ji ^mをΣ_lχ_ji ^m，lにより求めて設定する。ここで、χ_ji ^m，lは、マージされる前のノードs_j ^m，lからノードs_iへの状態遷移確率に対応する状態遷移確率の推定のための頻度変数とされる。

さらに、学習器３４は、ベクトルb_i ^mの要素のそれぞれに対応する観測確率の推定のための頻度変数のそれぞれを要素とするベクトルω_i ^mをΣ_lω_i ^m，lにより求めて設定する。

そして学習器３４は、すべてのマージが終了したら、修正された状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを用いて状態遷移確率と観測確率とを再計算する。

このようにすることで、状態遷移確率の推定のための頻度変数と、観測確率の推定のための頻度変数に対しても、上述した一状態一観測制約とアクション遷移制約が課されることになる。

ここまで、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができるようにするための技術について説明した。

ところで以上においては、図８を参照して上述したような、３次元の状態遷移確率テーブルと、２次元の観測確率テーブルを有するアクション拡張型ＨＭＭの例について説明した。通常は、ノード数をＮ、観測シンボル数をＭ、アクション数をＫとすると、算出すべきパラメータ数は、Ｎ²Ｋ＋ＮＭとなり、Ｎ、Ｍ、およびＫの値が一定であることを前提に学習アルゴリズムが定められる。

しかしながら、学習を進めるうちにＮ、Ｍ、およびＫの値を変更する必要に迫られることがある。例えば、ロボットが移動する迷路に用いられるパーツが新たに加わった場合、観測シンボルの種類が増えることになるので、Ｍの値を大きくする必要がある。

次に、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更する必要に迫られた場合にとり得る処置について説明する。

図３０は、観測シンボルの種類が増えることによる影響を説明する図である。同図に示されるように、観測シンボルの種類が増えると、観測確率テーブルの行方向（図中水平方向）の拡張が生じることになる。すなわち、領域１２１に対応する観測確率の値を新たに設定する必要がある。なお、観測確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。

また、図３０に示されるように、観測確率テーブルの行方向（図中水平方向）の拡張が生じたことにより、観測確率の推定のための頻度変数のテーブルも拡張させる必要がある。すなわち、領域１２２に対応する頻度変数の値を新たに設定する必要がある。

本発明では、図３０に示されるように観測確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけ観測シンボルの種類が増えることを前提として、図３０に示されるように観測確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。

いま、新しい観測シンボルo_M+iに対応するインデックスをM+iとして、観測確率テーブルに第M+i列を追加するものとする。

学習器３４は、観測確率テーブルの第M+i列に設定すべき観測確率値を適切な大きさの非零要素とする。この非零要素の値は、次のように決定される。

式（４２）に示されるように、新しい観測シンボルを追加する前の観測シンボルの数をＭとし、第M+i列に設定すべき観測確率値は、全て１／Ｍとする。

・・・（４２）

あるいはまた、式（４３）に示されるように、観測確率テーブルの各行ごとに、観測確率bj(・)が閾値以上となる観測シンボルの数をカウントし、その数n_jを用いて第M+i列に設定すべき観測確率値を求める。なお、bj(・)は、閾値以上となった、それぞれの観測シンボルの観測確率を表している。

・・・（４３）

学習器３４は、式（４２）または式（４３）に示されるように、観測確率テーブルの第M+i列に適切な大きさの非零要素を設定した後、テーブルの１行あたり観測確率値の合計が１.０となるように調整する。すなわち、式（４４）に示されるように、観測確率テーブル内の非零の各観測確率bj(・)を更新する。これにより、観測確率テーブルの拡張は完了する。

・・・（４４）

さらに、学習器３４は、観測確率の推定のための頻度変数のテーブルの第M+i列に設定すべき観測確率値を全て０（零）とする。これにより、観測確率の推定のための頻度変数のテーブルの拡張は完了する。

そして学習器３４は、新しい観測シンボルを含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。

このようにすることで、追加学習方式での学習中に、新たな観測シンボルが観測された場合でも、内部モデルデータを適切に更新することができる。

また、例えば、学習中に所定の観測シンボルが不要となった場合、観測確率テーブルを列方向に縮小させることも可能である。

この場合、学習器３４は、不要となる観測シンボルに対応するインデックスをkとすると、観測確率テーブルから第k列を削除して、ノードs_jにおける観測確率b_j(k)が存在しないようにする。

学習器３４は、観測確率の推定のための頻度変数のテーブルについても同様に、第k列を削除して、ω_j(k)が存在しないようにする。

さらに、学習器３４は、観測確率の推定のための頻度変数を用いて縮小後の観測確率テーブル内の各値を再計算する。

そして学習器３４は、所定の観測シンボルが不要となった後の学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。

また、例えば、ロボットが移動する迷路が所定の方向に延長された場合、ノードの数が増えることになるので、ノード数Ｎの値を大きくする必要がある。

図３１は、ノードの数が増えることによる影響を説明する図である。同図に示されるように、ノードの数が増えると、状態遷移確率テーブルの行列方向の拡張が生じることになる。すなわち、図３１の第１枚目の状態遷移確率テーブルにおける逆Ｌ字型の領域１３１−１に対応する状態遷移確率の値を新たに設定する必要がある。同様に、各アクションに対応する状態遷移確率テーブルの逆Ｌ字型の領域１３１−２、領域１３１−３、・・・に対応する状態遷移確率の値を新たに設定する必要がある。すなわち、アクション数Ｋ枚の状態遷移確率テーブルを拡張させて状態遷移確率の値を新たに設定する必要がある。なお、状態遷移確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。

また、ノードの数が増えると、観測確率テーブルの列方向（図中垂直方向）の拡張が生じることになる。すなわち、領域１３４に対応する観測確率の値を新たに設定する必要がある。なお、観測確率テーブルにおいては、テーブルの１行あたり観測確率値の合計が１.０となるようにする制約がある。

さらに、同図には示されていないが、状態遷移確率の推定のための頻度変数のテーブルと、観測確率の推定のための頻度変数のテーブルも同様に拡張させて値を新たに設定する必要がある。

本発明では、図３１に示されるように状態遷移確率テーブルと観測確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけノードの数が増えることを前提として、図３１に示されるように状態遷移確率テーブルと観測確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。

いま、新しいノードs_N+iに対応するインデックスをN+iとして、状態遷移確率テーブルに第N+i行と第N+i列を追加するものとする。

学習器３４は、状態遷移確率テーブルの第N+i行と第N+i列に設定すべき状態遷移確率値を、それぞれ微小なランダム要素とする。

学習器３４は、状態遷移確率の推定のための頻度変数のテーブルについても同様に、第N+i行と第N+i列とを追加し、設定すべき状態遷移確率値を、それぞれ微小なランダム要素とする。

学習器３４は、ノードs_N+iにおいて実行したことのあるアクションc_kを特定する。そして学習器３４は、アクションc_kに対応する第ｋ枚目の状態遷移確率テーブルのノードs_N+iに対応する行の状態遷移確率値のそれぞれを一様の値とする。ただし、アクションc_k実行時の実際の遷移結果を考慮して、経験のある遷移先状態への遷移確率を多少引き上げるようにしてもよい。

また、アクションc_kを実行した結果、ノードs_N+iへの遷移したことのある遷移元のノードs_jを特定する。そして学習器３４は、アクションc_kに対応する第ｋ枚目の状態遷移確率テーブルのノードs_jに対応する行の状態遷移確率値のそれぞれを次のように設定する。

当該行において、状態遷移確率が閾値以上となる遷移先ノードs_lの数をカウントし、その数をＬとする。そして、第ｋ枚目の状態遷移確率テーブルのノードs_jからノードs_N+iへの状態遷移確率a_iN+i(k)を１/Ｌとする。

そして学習器３４は、テーブルの１行あたり状態遷移確率値の合計が１.０となるように調整する。すなわち、式（４５）に示されるように、状態遷移確率テーブル内の各状態遷移確率a_j(k)を更新する。これにより、状態遷移確率テーブルの拡張は完了する。

・・・（４５）

さらに、学習器３４は、状態遷移確率の推定のための頻度変数のテーブルの追加領域に設定すべき状態遷移確率値を全て０（零）とする。これにより、状態遷移確率の推定のための頻度変数のテーブルの拡張は完了する。

また、学習器３４は、観測確率テーブルの第N+i行と第N+i列に設定すべき観測確率値を、適切な大きさの非零要素とする。非零要素の値としては、例えば、１/Ｎのような一様の値とされるが、ノードs_N+iで実際に観測されたことのある観測シンボルの観測確率を引き上げるようにしてもよい。

さらに、学習器３４は、観測確率の推定のための頻度変数のテーブルにおいて追加されたノードs_N+iに対応する第N+i 行をすべて０（零）とする。これにより、観測確率の推定のための頻度変数のテーブルの拡張は完了する。

そして学習器３４は、新たなノードを含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。

あるいはまた、例えば、ロボットが迷路上における移動可能方向が拡張されるように改造された場合、アクションの数が増えることになるので、アクション数Ｋの値を大きくする必要がある。

図３２は、アクションの数が増えることによる影響を説明する図である。同図に示されるように、アクションの数が増えると、状態遷移確率テーブルの奥行方向の拡張が生じることになる。すなわち、例えば、新たに追加されたアクションに対応する状態遷移確率テーブルであって、図３２の第３枚目の状態遷移確率テーブル１４１の状態遷移確率の値を新たに設定する必要がある。

また、同図には示されていないが、状態遷移確率の推定のための頻度変数のテーブルも同様に拡張させて値を新たに設定する必要がある。

本発明では、図３２に示されるように状態遷移確率テーブルを拡張する必要がある場合、学習器３４が、次のような処理を行う。ここでは、例えば、ロボットに対して予め所定の数だけアクションが増えることを前提として、図３２に示されるように状態遷移確率テーブルを拡張するように指令する場合の学習器３４の処理について説明する。

いま、新しいアクションc_K+i に対応するインデックスをK+iとして、第K+i枚目の状態遷移確率テーブルを追加するものとする。

学習器３４は、追加された第K+i枚目の状態遷移確率テーブルの全ての状態遷移確率を０とする。

また、学習器３４は、状態遷移確率の推定のための頻度変数のテーブルも同様に、第K+i枚目のテーブルを追加し、追加された第K+i枚目の状態遷移確率テーブルの全ての状態遷移確率を０とする。これにより、状態遷移確率の推定のための頻度変数のテーブルの拡張は完了する。

さらに、学習器３４は、新しいアクションc_K+iを実行したことがあるノードs_jを特定する。そして学習器３４は、第K+i枚目の状態遷移確率テーブルのノードs_jに対応する行の状態遷移確率値を全て一様の値とする。ただし、実際のアクションc_K+i実行時の遷移結果を考慮して、経験のある遷移先ノードへの状態遷移確率を多少引き上げるようにしてもよい。これにより、状態遷移確率テーブルの拡張は完了する。

そして学習器３４は、新たなアクションの実行を含む学習データセットに対する追加学習方式での学習を、所定の学習率の指定の下に行い、内部モデルデータを更新する。これにより、状態遷移確率の推定のための頻度変数、観測確率の推定のための頻度変数、並びに観測確率テーブルおよび状態遷移確率テーブルの各値が更新される。

上述した処理により、学習を進めるうちにノード数、観測シンボル数、アクション数を追加する必要に迫られた場合であっても学習を継続させることが可能となる。上述した処理は、例えば、ロボットに対して予め所定の数だけ観測シンボルの種類が増えることを前提として、図３０乃至図３２に示されるように各テーブルを拡張する場合の例である。

しかしながら、例えば、所定の数だけ観測シンボル、ノード、またはアクションが増えることを予め知ることができない場合がある。つまり、エージェントの自律的な行動によって逐次環境の変化が認識されるような場合、例えば、ロボットの管理者などが事前にどれだけ観測シンボル、ノード、またはアクションが増えるのかを知ることができない。従って、例えば、ロボットが迷路を移動中に、任意に新たな迷路のパーツが出現したり、新たに迷路が拡張されたり、新たに移動方向が追加されたりする場合は、さらなる考慮が必要となる。

次に、例えば、ロボットが迷路を移動中に、新たな迷路のパーツが出現したり、新たに迷路が拡張されたりする場合の、状態遷移確率テーブル、観測確率テーブルの拡張について説明する。すなわち、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合の例について説明する。

エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合、そもそもエージェント自身が、新たに環境が拡張されたのか否かを認識する必要がある。つまり、エージェントが、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのか認識できるようにしなければならない。例えば、ロボットが迷路を移動中に、新たに迷路が拡張された場合、拡張された部分を移動しているとき、自分が新たに追加されるべきノードに位置していることを認識できるようにしなければ、自律的に環境の変化を認識することができない。

ここで、自律行動学習装置１０におけるノードの認識の方式について説明する。ノードの認識は、図９の認識器３５により行なわれる。詳細は後述するが、ここでは、時系列情報の長さ値に上限があること、および認識された現在の状態確率のエントロピーの値の変化を考慮して、最終的には４通りの方式を説明することにする。

上述したように、認識器３５は、観測バッファ３３および行動出力バッファ３９に記憶されている情報、並びに内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいて、現在、ロボットが位置するノードを認識するようになされている。

また、上述したように、時刻t，t+1，t+2，・・・Tの各時刻で取得した観測信号に対応する観測シンボルo_t， o_t+1， o_t+2， ・・・， o_Tが各時刻の観測シンボルとして観測バッファ３３に記憶されている。同様に、例えば、時刻t，t+1，t+2，・・・Tの各時刻で実行したアクションc_t， c_t+1， c_t+2， ・・・， c_Tが各時刻のアクションとして行動出力バッファ３９に記憶されている。

ここでは、認識器３５に入力される情報であって、観測バッファ３３および行動出力バッファ３９に記憶されている情報を時系列情報と称することにし、時系列情報の長さを変数Ｎで表すことにする。

また、認識器３５から出力された認識結果は、その認識結果が出力された時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

認識器３５は、まず、時系列情報の長さＮを設定し、観測バッファ３３および行動出力バッファ３９から長さＮの時系列情報を取得し、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づく認識を行なう。

認識器３５は、例えば、Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する。例えば、Ｎ＝３であった場合、認識器３５は、認識結果としてのノード列s₁，s₂，s₃を出力する。この場合、認識器３５は、時刻t₁，において、ロボットがノードs₁に位置し、時刻t₂において、ロボットがノードs₂に位置し、時刻t₃において、ロボットがノードs₃に位置していたと認識したことになる。

なお、Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する処理においては、内部モデルデータ記憶部３７に記憶されている状態遷移確率テーブルおよび観測確率テーブルに基づいてノード列が推測されて出力される。Viterbiアルゴリズムを用いて、長さＮに対応するノード列を出力する場合、最も確からしい確率を有するノード列を含んだ複数のノード列を出力することが可能である。ここでは、Viterbiアルゴリズムを用いて得られた最も確からしい確率を有するノード列が出力されるものとする。

認識器３５は、さらに、現在ロボットが位置するノードが新たに追加されるべきであるのか否かを判定するために、Viterbiアルゴリズムを用いて出力されたノード列が、実際にあり得るノード列であるか否かを判定する。

出力されたノード列が、実際にあり得るノード列であるか否かの判定は、例えば、次のようにして行なわれる。

いま、出力されたノード列（長さＴのノード列）をＸで表し、時系列情報に基づいて特定された観測シンボルの列（長さＴの観測シンボルの列）を、観測系列Ｏで表すことにする。また、内部モデルデータの状態遷移確率テーブルを、行列Ａで表すことにする。なお、行列Ａは、時系列情報に基づいて特定されたアクションのそれぞれに対応する状態遷移確率テーブルを意味することとする。

認識器３５は、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かを判定する。

・・・（４６）

・・・（４７）

ここで、P(O|X)は、ノード列Ｘを構成する各ノードにおける観測系列Ｏを構成する各観測シンボルの観測確率を意味するものとし、観測確率テーブルに基づいて特定することができる。また、Thres_trans、およびThres_obsは、それぞれ遷移があり得るかどうかの閾値と観測があり得るかどうかの閾値を表すものとする。

従って、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）のいずれか１つでも満たさないと判定された場合、認識器３５は、出力されたノード列が、実際にあり得るノード列ではないと判定する。これにより、現在ロボットが位置するノード（時系列情報の最後の時刻におけるノード）は、新たに追加されるべきノードであって、未知のノードであると認識されるようにすることができる。

ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすと判定された場合、認識器３５は、現在の状態遷移確率のエントロピーを計算する。

ここで、エントロピーをＥ、ノードＸiの事後確率をP(Xi|O)とし、現在の内部モデルデータ上に存在するノード数の合計をＭで表すことにする。なお、ノード（状態）の事後確率とは、Viterbiアルゴリズムにより出力された確率であって、時系列情報の最後の時刻におけるノードに対応する確率を意味する。この場合、エントロピーＥは、式（４８）により表すことができる。

・・・（４８）

例えば、式（４８）により演算されたエントロピーの値を所定の閾値と比較し、閾値未満である場合、認識器３５は、出力されたノード列が、実際にあり得るノード列であって一意に特定することができる状況であることを意味する。これにより、現在ロボットが位置するノード（時系列情報の最後の時刻におけるノード）は、内部モデルデータ上に既に存在するノードであって、既知のノード（学習済みの内部状態）であると認識されるようにすることができる。

さらに、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かが判定され、Thres以上である場合にのみ、時系列情報の最後の時刻におけるノードは、既知のノードであると認識されるようにしてもよい。すなわち、認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値を設けるのである。ここで、固有ノード数とは、インデックスが異なるノードのみをカウントした場合のノード数を意味する。

例えば、出力されたノード列のインデックスが「１０」、「１１」、「１０」、「１１」、「１２」、「１３」であった場合、ノード列の長さは６であるが、固有ノード数は４である。例えば、エージェントが同じノード間の遷移を繰り返した場合、同じ長さの時系列情報に基づいて認識を行なったとしても、認識結果の精度は低くなる。このため、認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値を設けるようにしてもよい。

一方、エントロピーの値が閾値以上である場合、出力されたノード列が、実際にあり得るノード列であるが、例えば、複数の候補が存在しており一意に特定することができない状況であることを意味する。このため、認識器３５は、出力されたノード列が、時系列情報の長さを増加させるべきと判定する。これにより、例えば、時系列情報の長さＮの値がインクリメントされて処理が繰り返し実行される。

次に、図３３のフローチャートを参照して、認識器３５によるノード認識処理について説明する。この処理は、認識器３５によるノード認識処理の第１の方式の例となる処理である。

ステップＳ２０１において、認識器３５は、変数Ｎの値を初期値である１にセットする。

ステップＳ２０２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。

ステップＳ２０３において、認識器３５は、ステップＳ２０２で出力された時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力する。

ステップＳ２０４において、認識器３５は、ステップＳ２０３の処理の結果、出力されたノード列が実際にあり得るノード列であるか否かを判定する。このとき、上述したように、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かが判定される。ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たす場合、ステップＳ２０４では、実際にあり得るノード列であると判定される。一方、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）の少なくとも一方を満たさない場合、ステップＳ２０４では、実際にあり得るノード列ではないと判定される。

ステップＳ２０４において、実際にあり得るノード列ではないと判定された場合、処理は、ステップＳ２０８に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、未知ノードであると認識する。ステップＳ２０８の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

一方、ステップＳ２０４において、実際にあり得るノード列であると判定された場合、処理は、ステップＳ２０５に進む。

ステップＳ２０５において、認識器３５は、エントロピーを計算する。このとき上述したように、式（４８）によりエントロピーが演算される。

ステップＳ２０６において、認識器３５は、ステップＳ２０５の処理で演算されたエントロピーの値を所定の閾値と比較し、エントロピーの値が閾値以上であるか否かを判定する。

ステップＳ２０６において、エントロピーの値が閾値以上であると判定された場合、処理は、ステップＳ２０９に進む。

ステップＳ２０９において、認識器３５は、変数Ｎの値を１だけインクリメントする。これにより、その後実行されるステップＳ２０２の処理において、長さがＮ＋１の時系列情報が取得されることになる。なお、ステップＳ２０９において変数Ｎの値をインクリメントする毎に、ステップＳ２０２で取得される時系列情報は、過去方向に延長されるものとする。

このように、ステップＳ２０４で実際にあり得るノード列ではないと判定されるか、または、ステップＳ２０６において、エントロピーの値が閾値以上ではないと判定されるまで、ステップＳ２０２乃至ステップＳ２０６、およびステップＳ２０９の処理が繰り返し実行される。

ステップＳ２０６において、エントロピーの値が閾値以上ではないと判定された場合、処理は、ステップＳ２０７に進む。

また、ステップＳ２０４において、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かがさらに判定され、Thres以上である場合にのみ、処理は、ステップＳ２０５またはステップＳ２０８に進むようにしてもよい。

あるいはまた、ステップＳ２０３で固有ノード数が閾値Thres以上となるノード列が出力された場合にのみ、処理がステップＳ２０４に進み、固有ノード数が閾値Thres未満である場合は、Ｎの値がインクリメントされて時系列情報が再度取得されるようにしてもよい。

ステップＳ２０７において、認識器３５は、時系列情報の最後の時刻におけるノードは、既知ノードであると認識する。このとき、時系列情報の最後の時刻におけるノードのインデックスが出力されるようにしてもよい。また、ステップＳ２０７の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

このようにしてノード認識処理が実行される。

ところで、図３３の処理において、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるものとすると説明したが、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することはできない。既知ノードから遷移した未知ノードを含むノード列に基づいて、正確な認識結果を得ることはできないからである。

従って、時系列情報に対応するノード列の中に、既知ノードから遷移した未知ノードが含まれるようにすることはできず、時系列情報の長さＮの値に上限があることになる。なお、当該ノードが既知ノードから遷移した未知ノードであるか否かは、認識結果バッファ３８に記憶された情報に基づいて判断することができる。

次に、図３４のフローチャートを参照して、時系列情報の長さＮの値に上限があることを考慮した場合のノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第２の方式の例となる処理である。

ステップＳ２２１乃至ステップＳ２２９の処理は、図３３のステップＳ２０１乃至ステップＳ２０９の処理と同様のものなので、詳細な説明は省略する。

図３４の例の場合、ステップＳ２２９の処理で変数Ｎの値が１だけインクリメントされると、ステップＳ２３０において、ノード列に既知ノードから遷移した未知ノードが含まれることになるか否かが判定される。すなわち、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるが、ノード列を過去方向に延長すると既知ノードから遷移した未知ノードが含まれることになるか否かが判定されるのである。つまり、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することができないようにされるのである。

ステップＳ２３０において、既知ノードから遷移した未知ノードが含まれることになると判定された場合、処理は、ステップＳ２３１に進む。ステップＳ２３０において、既知ノードから遷移した未知ノードが含まれることにはならないと判定された場合、処理は、ステップＳ２２２に戻る。

ステップＳ２３１において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行させるように制御情報を出力する。

すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積するように指令を出力するのである。

認識処理は、図３４に示されるように実行されるようにしてもよい。

ところで、図３３と図３４を参照して上述した処理においては、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすかによって、実際にあり得るノード列であるか否かが判定されると説明した。しかし、認識された現在の状態確率のエントロピーの値の変化に基づいて実際にあり得るノード列であるか否かが判定されるようにすることも可能である。

すなわち、長さＮの時系列情報に基づいて式（４８）により演算されるエントロピーをＥ_Nとし、長さＮ−１の時系列情報に基づいて式（４８）により演算されるエントロピーをＥ_N-1とし、△Ｅ＝Ｅ_N−Ｅ_N-1を演算する。そして、△Ｅを所定の閾値Thres_entと比較し、その比較処理の繰り返し回数を閾値Thres_stableと比較し、それらの比較結果に基づいてノードが認識されるようにしてもよい。

例えば、△Ｅ＜Thres_entを満たさない場合、時系列情報が過去方向に延長されるようにし、さらにエントロピーが計算されて△Ｅ＜Thres_entを満たすか否かが判定される。△Ｅ＜Thres_entを満たす場合、カウンタＮＣがカウントアップされ、ＮＣ＞Thres_stableを満たすとき、ノードの認識が行なわれることになる。

次に、図３５のフローチャートを参照して、状態確率のエントロピーの値の変化に基づく認識を行なう場合のノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第３の方式の例となる処理である。

ステップＳ２５１において、認識器３５は、変数Ｎの値を初期値である１にセットする。

ステップＳ２５２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。

ステップＳ２５３において、認識器３５は、ステップＳ２０２で出力された時系列情報に基づいて、Viterbiアルゴリズムを用いてノード列を出力する。

ステップＳ２５４において、認識器３５は、エントロピーの差分を演算する。このとき、上述したように、長さＮの時系列情報に基づいて式（４８）により演算されるエントロピーをＥ_Nとし、長さＮ−１の時系列情報に基づいて式（４８）により演算されるエントロピーをＥ_N-1とし、△Ｅ＝Ｅ_N−Ｅ_N-1を演算する。なお、ステップＳ２５４の演算は、Ｎの値が２以上となったときに実行されるものとする。

ステップＳ２５５において、認識器３５は、ステップＳ２５４で演算したエントロピーの差分は、閾値Thres_ent以上であるか否かを判定する。ステップＳ２５５において、ステップＳ２５４で演算したエントロピーの差分は、閾値以上ではないと判定された場合、処理は、ステップＳ２５６に進む。

ステップＳ２５６において、認識器３５は、カウンタＮＣの値を１だけインクリメントする。

ステップＳ２５７において、認識器３５は、カウンタＮＣの値が閾値Thres_stable以上であるか否かを判定する。ステップＳ２５７において、カウンタＮＣの値が閾値Thres_stable以上であると判定された場合、処理は、ステップＳ２５８に進む。

ステップＳ２５８において、認識器３５は、ステップＳ２５３の処理の結果、出力されたノード列が実際にあり得るノード列であるか否かを判定する。このとき、上述したように、ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たすか否かが判定される。ノード列Ｘと観測系列Ｏが式（４６）および式（４７）を満たす場合、ステップＳ２５８では、実際にあり得るノード列であると判定される。一方、ノード列Ｘと観測系列Ｏが式（４６）または式（４７）の少なくとも一方を満たさない場合、ステップＳ２５８では、実際にあり得るノード列ではないと判定される。

ステップＳ２５８において、出力されたノード列が実際にあり得るノード列ではないと判定された場合、処理は、ステップＳ２６２に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、未知ノードであると認識する。ステップＳ２６２の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

一方、ステップＳ２５８において、出力されたノード列が実際にあり得るノード列であると判定された場合、処理は、ステップＳ２５９に進む。

ステップＳ２５９において、認識器３５は、エントロピーを計算する。このとき上述したように、式（４８）によりエントロピーが演算される。

ステップＳ２６０において、認識器３５は、ステップＳ２５９の処理で演算されたエントロピーの値を所定の閾値と比較し、エントロピーの値が閾値以上であるか否かを判定する。

ステップＳ２６０において、エントロピーの値が閾値以上であると判定された場合、処理は、ステップＳ２６３に進む。

ステップＳ２６３において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行するように制御情報を出力する。

すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積するように指令を出力するのである。

一方、ステップＳ２６０において、エントロピーの値が閾値以上ではないと判定された場合、処理は、ステップＳ２６１に進み、認識器３５は、時系列情報の最後の時刻におけるノードは、既知ノードであると認識する。

ステップＳ２６１の認識結果は、時系列情報の最後の時刻と対応付けられて認識結果バッファ３８に記憶されるようになされている。

また、ステップＳ２５８において、出力されたノード列に含まれる固有ノード数が閾値Thres以上であるか否かがさらに判定され、Thres以上である場合にのみ、処理は、ステップＳ２５９またはステップＳ２６２に進むようにしてもよい。この場合、ステップＳ２５８において、出力されたノード列に含まれる固有ノード数が閾値Thres以上ではないと判定されたときは、処理は、ステップＳ２６５に進むようにすればよい。すなわち、変数Ｎの値が１だけインクリメントされるようにすればよい。

また、ステップＳ２５５で、ステップＳ２５４で演算したエントロピーの差分は、閾値Thres_ent以上であると判定された場合、処理は、ステップＳ２６４に進み、カウンタＮＣの値が０に設定される。

ステップＳ２６４の処理の後、または、ステップＳ２５７でカウンタＮＣの値が閾値Thres_stable以上ではないと判定された場合、処理は、ステップＳ２６５に進む。

ステップＳ２６５において、認識器３５は、変数Ｎの値を１だけインクリメントする。これにより、その後実行されるステップＳ２０２の処理において、長さがＮ＋１の時系列情報が取得されることになる。なお、ステップＳ２６５において変数Ｎの値をインクリメントする毎に、ステップＳ２５２で取得される時系列情報は、過去方向に延長されるものとする。

このように、ステップＳ２５５でエントロピーの差分は、閾値Thres_ent以上ではないと判定され、かつ、ステップＳ２５７でカウンタＮＣの値が閾値Thres_stable以上であると判定されるまで、ステップＳ２５２乃至ステップＳ２５７、およびステップＳ２６５の処理が繰り返し実行される。

このようにしてノード認識処理が実行される。図３５の例の場合、ステップＳ２５５とステップＳ２５７の処理により、エントロピーの値が収束したことが確認され、その後、出力されたノード列が実際にあり得るノード列であるかが判定されるようにした。従って、例えば、図３３を参照して上述した場合と比較して、より確実な認識を行なうことが可能となる。

また、図３５の処理の場合も、既知ノードから未知ノードへの遷移が生じた時刻より以前に時系列情報を延長することはできない。既知ノードから遷移した未知ノードを含むノード列に基づいて、正確な認識結果を得ることはできないからである。。

従って、時系列情報に対応するノード列の中に、既知ノードから遷移した未知ノードであると認識されたノードが含まれるようにすることはできず、時系列情報の長さＮの値に上限があることになる。なお、当該ノードが既知ノードから遷移した未知ノードであるか否かは、認識結果バッファ３８に記憶された情報に基づいて判断することができる。

次に、図３６のフローチャートを参照して、状態確率のエントロピーの値の変化に基づく認識を行なう場合、時系列情報の長さＮの値に上限があることを考慮するときのノード認識処理の例について説明する。この処理は、認識器３５によるノード認識処理の第４の方式の例となる処理である。

ステップＳ２８１乃至ステップＳ２９５の処理は、図３５のステップＳ２５１乃至ステップＳ２６５の処理と同様のものなので、詳細な説明は省略する。

図３６の例の場合、ステップＳ２９５の処理で変数Ｎの値が１だけインクリメントされると、ステップＳ２９６において、ノード列に既知ノードから遷移した未知ノードが含まれることになるか否かが判定される。すなわち、変数Ｎの値をインクリメントする毎に、取得される時系列情報は、過去方向に延長されるが、ノード列を過去方向に延長すると既知ノードから遷移した未知ノードが含まれることになるか否かが判定されるのである。

ステップＳ２９６において、既知ノードから遷移した未知ノードが含まれることになると判定された場合、処理は、ステップＳ２９３に進む。ステップＳ２９６において、既知ノードから遷移した未知ノードが含まれることにはならないと判定された場合、処理は、ステップＳ２８２に戻る。

ステップＳ２９３において、認識器３５は、認識結果を保留し、時系列情報を未来方向に延長するように指令する。つまり、さらにアクションを実行して時系列情報を蓄積することを指令するためのメッセージ等を出力するのである。このとき、認識器３５は、例えば、行動生成器３６に対して、さらに、アクションを実行するように制御情報を出力する。

すなわち、現時点でのノードの認識は不可能であるか、または、仮に可能であっても不確実な認識結果となるため、認識器３５は、認識結果を保留し、時系列情報をさらに蓄積されるように指令を出力するのである。

認識処理は、図３６に示されるように実行されるようにしてもよい。

図３３乃至図３６を参照して上述した４通りの方式により、ロボットは、自分が新たに追加された迷路のパーツ上（未知ノード）に位置しているのか、または以前から存在していたパーツ上（既知ノード）にいるのかを認識することができる。このようにして認識された未知ノードに関する状態遷移確率と観測確率を設定し、状態遷移確率テーブル、および観測確率テーブルを拡張する。

なお、ここでは、アクション拡張型ＨＭＭによる認識を行なう場合の例について説明したが、図３３乃至図３６の認識処理は、通常のＨＭＭの認識においても適用することができる。

ところで、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張する場合、どの時点でどれだけの未知ノードを、新たに状態遷移確率テーブル、および観測確率テーブルなどに含めるかが問題となる。次に、自律的に環境の変化を認識して、未知ノードを内部モデルデータに追加する場合における追加すべき未知ノードの個数および追加すべきタイミングについて説明する。

なお、ここでいう未知ノードの内部モデルデータへの追加とは、未知ノードとみなされたノードを表す新たなインデックスを生成し、例えば、そのインデックスに対応する行列を状態遷移確率テーブルなどに追加することを意味する。

図３３乃至図３６を参照して上述した方式により、自分が新たに追加されるべきノード（未知ノード）に位置していると認識した時刻から経過した時間をＮとする。この時間Ｎは、時系列情報の長さと言い換えることもできる。また、ここでは認識の精度を保証するための閾値であって、認識した結果のノード列における固有ノード数の閾値Thresを設けることにする。

まず、長さＮの時系列情報に含まれる固有ノード数がThresの値になるまで、エージェントは行動を繰り返す。すなわち、行動生成器３６と行動出力部３２とにより、Ｎ回のアクションが実行され、観測バッファ３３、および行動出力バッファ３９に、長さＮの時系列情報が蓄積されることになる。なお、ここでいう長さＮの時系列情報は、自分が未知ノードに位置していると認識した時刻後の時間的長さＮの時系列情報を意味する。また、以下において適宜、「長さＮの時系列情報に基づいて認識された長さＬｒのノード列に含まれる固有ノード数がThresの値になる」という意味で「ＬｒがThresの値になる」と表現することにする。

そして、ＬｒがThres以上になった場合、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この場合、時系列情報の長さの上限Ｎがあることになる。

ここで実行される認識処理における図３４のステップＳ２２３または図３６のステップＳ２８３で出力されるノード列をＳとし、そのノード列の長さをＬrとする。

そして、図３４のステップＳ２２８または図３６のステップＳ２９２で未知ノードであると認識された場合、そのノードが未知ノードとみなされて、学習器３４により内部モデルデータに追加するようにする。

実際に未知になってから足したノードの数をｍ_addとすると、追加する未知ノードの数をｍは、式（４９）により表すことができる。

・・・（４９）

なお、ｍ_addは、自分が未知ノードに位置していると最初に認識したときから、既に未知ノードの追加が行なわれた場合、それら追加されたノードの個数を表す数とされる。すなわち、式（４９）は、未知ノードに位置していると認識された後、未知ノードとみなして追加したノードの数はひいた上で、最初に認識した未知ノードに至るまでの間のノードを足すことを示している。

また、式（４９）の右辺において加算される「1」は、長さＬrのノード列の最も過去の時刻に対応するノードを、どのノードに接続するかが現時点では決められないため、保留するということを示す。

図３７を参照してさらに詳細に説明する。図３７は、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。

さらに、説明を簡単にするため、アクションを１回実行すると図中の円により示されたノードの数と時系列情報の長さが１だけ増加するものとし、それらのノードは、特に説明がない限り、全て固有ノードであると認識されたものとする。

同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２１１は、未知ノードであると認識されたものとする。

その後、さらに１のアクションが実行され、エージェントは、ノード２１２に遷移する。このとき、ノード２０２乃至ノード２１２に対応する長さＬｒの時系列情報に基づく認識処理が実行され、ノード２１２は未知ノードと認識されたものとする。この時点では、まだ未知ノードの追加は行なわれない。

その後、さらに１のアクションが実行され、エージェントがノード２１３に遷移する。このとき、ノード２０３乃至ノード２１３に対応する長さＬｒの時系列情報に基づく認識処理が実行され、ノード２１３は未知ノードと認識されたものとする。この時点でノード２０１の追加が行なわれる。

これにより、それ以後の認識処理においては、ノード２０１が既知ノードとして取り扱われることになる。

いまの場合、時系列情報の長さ（自分が未知ノードに位置していると認識した時刻後の時間的長さ）Ｎは、Thres＋２である。また、いまの場合、ノード２０３乃至ノード２１３がノード列Ｓに対応し、ノード列Ｓの長さＬrは、Thresである。よって、式（４９）より、追加すべきノードの個数ｍは、Thres＋２-（Thres＋０＋１）＝１と算出される。従って、未知ノードであった１個のノード２０１が新たに追加されたのである。

すなわち、内部モデルデータの状態遷移確率テーブルなどに、ノード２０１を表す新たなインデックスの行列が追加されるのである。

なお、上述した例において、ノード２１１乃至ノード２１３は、いずれも未知ノードであると認識されているが、ノード２０１が真の意味で未知ノードであったか否かは不明である。例えば、ノード２１１が未知ノードと判定されたのは、ノード２０１乃至ノード２１１のノード列が、実際にあり得るノード列ではないと判定された結果であり、必ずしもノード２１１が既存の内部モデルデータに存在しないノードであるとは限らないからである。つまり、ノード２０１乃至ノード２１１のノードのいずれかが既存の内部モデルデータに存在しないノードであれば、ノード２１１は、未知ノードと認識されるのである。

従って、現時点でノード２０１を未知ノードとみなして内部モデルデータの状態遷移確率テーブルなどに、ノード２０１を表す新たなインデックスの行列が追加しても、実際には既存のインデックスの行列と重複する結果にもなり得る。このように、ノード２０１が真の意味で未知ノードであったか否かは不明なのである。

なお、ここでは、図３７を参照して説明する都合上、ノード２０１が真の意味で未知ノードであったか否かは不明と説明しているが、図３７の例では、ノード２０１は真の意味で未知ノードであったことが前提とされる。従って、本来は、その後に追加される「ノード２０２、ノード２０３、・・・が真の意味で未知ノードであったか否かは不明なものとなる」という説明が適切である。

上述のように、ノード２０１が真の意味で未知ノードであったか否かは不明であるとしても、既存のインデックスの行列と重複する可能性を過度に懸念して、ノード２０１を表す新たなインデックスを内部モデルデータに追加しないとすると、問題がある。エージェントの状況によっては、永遠に学習が完了しないことになるからである。

例えば、環境である迷路が拡張され、新たな迷路の部屋ができ、エージェントであるロボットが、新たな迷路の部屋に閉じ込められた場合、追加するノードが真の意味で未知ノードであったと確信できなくても、やはり追加せざるを得ない。

このため、自分が未知ノードに位置していると最初に認識したときから、所定の時間経過後のタイミングで、所定の個数のノードを、内部モデルデータに追加する必要があるのである。

説明を図３７に戻す。ノード２０１が内部モデルデータに追加された後、さらにアクションが実行され、時系列情報に基づいて認識処理が実行されていく。ノード２１２乃至ノード２２１に対応する時系列情報に基づく認識処理が実行された結果、ノード２２１が既知ノードであると認識された場合、ノード２１２乃至ノード２２１は、全て既知ノードであったことになる。このとき、ノード２１１が追加されるとともに、ノード２１１からノード２１２へのアンカリングが行われる。アンカリングは、未知ノードから既知ノードへの遷移が認識された場合、未知ノードと既知ノードとの状態遷移確率などを設定する処理である。なお、アンカリングの詳細については後述する。

ところで、図３４、または図３６を参照して上述した認識処理においては、ステップＳ２３１またはステップＳ２９３において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力される場合がある。このような場合、時系列情報の長さThresでは適切な認識を行なうことができないので、時系列情報の長さを未来方向に延長する必要がある。

認識処理において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力された場合の例について、図３８を参照してさらに詳細に説明する。図３８では、図３７と同様に、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。

同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２０１乃至ノード２１１は、全て未知ノードであると認識されたものとする。また、この例では、ノード２０１乃至ノード２１１が内部モデルデータに追加されたものとする。

これにより、それ以後の認識処理においては、ノード２０１乃至ノード２１１が既知ノードとして取り扱われることになる。

エージェントがノード２２１に遷移したとき、長さＬｒの時系列情報に基づいて認識処理が実行され、この時点では、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたものとする。すなわち、この時点では、ノード列を一意に認識することができず、仮に認識したとしても複数の候補が存在する状態となっている。

このような場合、閾値Thresの値が１だけインクリメントされ、新たに１のアクションが実行され、認識処理の対象となる時系列情報の長さも１だけインクリメントされる。これにより、エージェントは、ノード２２２に遷移したものとする。この時点で、長さThres＋１の時系列情報に基づいて認識処理を実行し、長さＬｒ（＝Thres＋１）のノード列を得たが、この時点でも、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたものとする。

そして、閾値Thresの値がインクリメントされ、さらにアクションが実行されることにより、エージェントは、ノード２３１に遷移したものとする。この時点で、長さThres＋qの時系列情報に基づいて認識処理を実行することにより、ノード２３１が既知ノードであると認識されたものとする。

ノード２３１が既知ノードであると認識された場合、ノード２１３乃至ノード２３１は、全て既知ノードであったことになる。このとき、ノード２１２が追加されるとともに、ノード２１２からノード２１３へのアンカリングが行われる。

ただし、上述したように、未知ノードとみなされて追加されたノードの中に、実際には既知ノードであるノードが含まれることがある。また、例えば、エージェントが実際には同じノードに繰り返し遷移している場合（例えば、２つのノード間を往復している場合）でも、それらが異なる未知ノードと認識される場合がある。

このように、本来未知ノードとは言えないノードが未知ノードとみなされて、それらの未知ノードが内部モデルデータに追加されることを抑止するために、例えば、アンカリングする際にノードの追加または削除の要否のチェックが行なわれる。

アンカリングする際にノードの追加または削除の要否のチェックが行なわれる場合の例について、図３９を参照してさらに詳細に説明する。図３９では、図３７と同様に、図中垂直方向に時間軸ｔが設けられており、時間の経過に伴ってエージェントが遷移したノードが図中の円により示されている。また、同図において、図中垂直方向の点線は、自分が未知ノードに位置していると最初に認識したノードを示すためのものである。この例では、ノード２０１が、自分が未知ノードに位置していると最初に認識したノードとされる。

同図に示されるように、自分が未知ノードに位置していると最初に認識した後、１ずつアクションが実行されて時系列情報が蓄積されていく。そして、時系列情報の長さＮが閾値Thresと等しくなった（この場合、Ｌｒ＝Ｎ）後、認識器３５は、時系列情報に基づいて、図３４、または図３６を参照して上述した認識処理を実行する。この例の場合、ノード２０１、ノード２０２、・・・ノード２１１のノード列が出力され、ノード２０１乃至ノード２１１は、全て未知ノードであると認識されたものとする。

その後、さらに１のアクションが実行され、エージェントは、ノード２１２に遷移するが、この時点では、まだ未知ノードの追加は行なわれない。

その後、さらに１のアクションが実行され、エージェントがノード２１３に遷移すると、ノード２０１の追加が行なわれる。

このようにして、アクションが実行され、エージェントはノード２１５に遷移したものとする。また、このとき、ノード２０１乃至ノード２０３の追加が既に行なわれていたものとする。この時点で、ノード２０１乃至ノード２０３は、未知ノードとみなされて追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されているものとする。その後、ノード２０５乃至ノード２１５に対応する時系列情報に基づく認識処理が実行された結果、ノード２１５が既知ノードであると認識された場合、ノード２０５乃至ノード２１５は、全て既知ノードであったことになる。

このとき、ノードの削除の要否のチェックが行なわれる。すなわち、時系列情報の長さが過去方向に延長され、延長された時系列情報に基づく認識処理が実行される。その結果、例えば、ノード２０３乃至ノード２１５に対応する時系列情報に基づく認識処理が実行され、その結果、ノード２０３乃至ノード２１５が全て既知ノードであったと認識されたものとする。すなわち、ノード２０３は、未知ノードとみなされて追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されていたが、本来は、既知ノードであって、追加したインデックスのノードは、内部モデルデータから削除すべきである。

例えば、ノード２０３とノード２０５、実際には同じインデックスのノードであり、また、ノード２０４とノード２０６は、実際には同じインデックスのノードであった場合、上述のように認識されることになる。

例えば、ノード２０３のインデックスをｕとして状態遷移確率テーブルなどに新たな行列を追加したが、ノードの削除の要否のチェックが行なわれた結果、ノード２０３のインデックスは、ｆであることが判明したとする。インデックスｆに対応する行列は、エージェントがノード２０１に遷移する以前から状態遷移確率テーブルなどに存在していたものとする。この場合、インデックスｕに対応する行列とインデックスｆに対応する行列が重複して存在することになるので、インデックスｕに対応する行列は、状態遷移確率テーブルなどから削除しておく必要がある。

その結果、ノード２０３のインデックスとして新たに追加されたインデックスｕに対応する行列などが内部モデルデータから削除され、ノード２０２から既知ノードとして認識されたノード２０３へのアンカリングが行われる。

例えば、上述の例において、ノード２０２のインデックスをｔとして状態遷移確率テーブルなどに新たな行列を追加していた場合、インデックスｔのノードからインデックスｆのノードへの状態遷移確率などが、アンカリングによって設定されることになる。

なお、アンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようになされている。すなわち、アンカリングされた直後の内部モデルデータを初期値とし、図３９におけるノード２０１乃至ノード２１５、およびノード２０１の左側の１つのノードに対応する時系列情報に基づく学習が行われることになる。

上述したように、アンカリングは、未知ノードから既知ノードへの遷移が認識された場合、未知ノードと既知ノードとの状態遷移確率などを設定する処理である。本発明では、アンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようにする。

すなわち、未知ノードが追加された後の内部モデルデータに基づいて、追加学習方式の学習が行われる。仮に、実際には同じインデックスのノードが異なる未知ノードとして重複して追加されたとしても、この学習によって、上述したフォワードマージアルゴリズムおよびバックワードマージアルゴリズムが適用されて同一のノードとしてマージされる可能性が高くなる。

また、追加学習方式での学習を、アンカリングが行なわれるまで実行しないようにすることで、内部モデルデータにおいて更新すべきパラメータの数をできるだけ少なくすることができる。アンカリングの際にノードの削除の要否のチェックが行なわれるからである。従って、計算量を抑制しながら、適切に内部モデルデータを更新していくことが可能となるのである。

このように、アンカリングの際に、ノードの削除の要否のチェックが行なわれる場合、追加する未知ノードの数ｍは、式（４９）に替えて式（５０）より表すことができる。

・・・（５０）

いまの場合、時系列情報の長さ（自分が未知ノードに位置していると認識した時刻後の時間的長さ）Ｎは、１１である。また、いまの場合、ノード２０３乃至ノード２１５がノード列Ｓに対応し、ノード列Ｓの長さＬrは、Thres＋２である。よって、式（５０）より、追加すべきノードの個数ｍは、Thres＋４-（Thres＋２＋３）＝−１と算出される。従って、既に追加された３つのノードのうちの１個のノード２０３（のインデックスに対応する行列）が削除されるのである。

ここでは、ノードが削除される場合の例のみを説明したが、ｍ_addの値の如何によっては、ノードが追加される場合もあり得る。すなわち、式（５０）または後述する式（５１）により計算されたｍが正の値となれば、その分のノードが追加されることになる。従って、実際には、アンカリングの際に、ノードの追加または削除の要否のチェックが行なわれることになる。

なお、削除すべきノードが認識処理の結果、既知ノードと認識されてしまう場合、そのノードの削除は行なわれない。

仮に、既に未知ノードとみなして追加したノードのうちＫ個目のノードが、認識処理で出力されたノード列Ｓに含まれていた場合、削除するノードの数ｍは、式（５０）に替えて式（５１）より表すことができる。

・・・（５１）

式（５１）により算出された|ｍ|個のノードが削除するノードとなる。

また、この場合、アンカリングするノードは、ノード列Ｓの中の（（Ｌｒ＋Ｋ）−Ｎ）番目のノードとなる。

このようにアンカリングが行なわれた後、これまで蓄積された時系列情報に基づいて、追加学習方式の学習が行われるようになされている。また、アンカリングが行なわれるまでは、追加学習方式での学習を実行しないようになされている。従って、アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードは、それ以後の認識処理において既知ノードの１つとして認識されるものの、いわば仮の既知ノードとして認識されていることになる。アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードは、最終的には削除すべきものである可能性があるからである。また、アンカリングされる前に、未知ノードとみなされて内部モデルデータに追加されたノードと、他のノードとの状態遷移確率などの値は、追加学習方式での学習により変更される可能性があるからである。

ところで、追加するノードが真の意味で未知ノードであったと確信できなくても、自分が未知ノードに位置していると最初に認識したときから、所定の時間経過後のタイミングで、所定の個数のノードを、内部モデルデータに追加せざるを得ないことについては上述した。つまり、アンカリングする前の内部モデルデータには、単に未知ノードとみなされたノードを表すインデックスに対応する情報も追加されている可能性が極めて高いといえる。

しかし、真の意味で未知ノードであったと確信できない極めて多数のノードが、それぞれ一様に未知ノードとみなされて内部モデルデータに追加されていくと、認識処理における誤認識を招くことがある。未知ノードとみなされて追加されたノードも、それ以後の認識処理においては既知ノードとして取り扱われることになるからである。

その結果、例えば、以前から存在していた既知ノードが、未知ノードとみされて追加されたノードであると、誤って認識されてしまうことがある。認識処理は、内部モデルデータに基づいて行なわれるからである。

このような誤認識を抑制するために、アンカリングする前に、未知ノードとみなして追加してしまったノードを適宜削除するようにしてもよい。この場合、式（４９）に示したｍの値が０よりも小さくなったとき、|ｍ|個のノードを削除するようにすればよい。

例えば、固有ノード数の閾値Thresの値が７であった場合を考える。例えば、ノード２１６（図示せず）が、自分が未知ノードに位置していると最初に認識したノードであったものとし、いま、エージェントはノード２２６（図示せず）に遷移したものとする。ここで、ノード２１６は、既に内部モデルデータに追加されているものとする。

ノード２１９乃至ノード２２６に対応する時系列情報に基づいて認識処理を行った結果、ノード２２６は未知ノードであると認識されたものとする。このとき、ノード２１７が内部モデルデータに追加されることになる。

その後、アクションを実行することにより、エージェントはノード２２７（図示せず）に遷移し、この時点での認識処理の結果、ノード２２７は未知ノードであると認識されたものとする。このとき、ノード２１８が内部モデルデータに追加されることになる。しかし、ノード２１８が内部モデルデータに追加された結果、ノード２２０、ノード２２２、ノード２２４、およびノード２２６は、実際には、ノード２１８と同じインデックスのノードであることが認識されたこととする。

この場合、閾値Thres以上の固有ノード数を含むノード列を出力させるためには、時系列情報の長さを、ノード２１７乃至ノード２２７に対応する長さとしなければならない。

このような場合、時系列情報の長さ（ノード２１６乃至ノード２２７）Ｎは１２であり、既に追加したノード（ノード２１６乃至ノード２１８）の数ｍ_addは３である。また、いまの場合、ノード２１７乃至ノード２２７がノード列Ｓに対応し、ノード列Ｓの長さＬrは１１である。よって、式（４９）より、追加すべきノードの個数ｍは、１２−（１１＋３＋１）＝−３と算出される。従って、内部モデルデータに追加された３つノードであって、ノード２１６乃至ノード２１８が削除されるのである。

このようにして、アンカリングする前に、未知ノードとみなして追加してしまったノードを必要に応じて削除すれば、誤認識を抑制することが可能となる。

すなわち、アンカリングする前に、未知ノードを追加したり、未知ノードとみなして追加してしまったノードを必要に応じて削除したりする処理が行われる。この処理は、後述する図４０のステップＳ３１６に対応する。

また、アンカリングする際にも、未知ノードを追加したり、未知ノードとみなして追加してしまったノードを必要に応じて削除したりする処理が行われる。この処理は、後述する図４０のステップＳ３１８に対応する。

次に、図４０のフローチャートを参照して、未知ノード追加処理について説明する。この処理は、エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張する必要がある場合、自律行動学習装置１０により実行される。

ステップＳ３１１において、認識器３５は、変数Ｎの値を初期値である１にセットする。

ステップＳ３１２において、認識器３５は、長さＮの時系列情報を観測バッファ３３および行動出力バッファ３９から取得する。

ステップＳ３１３において、認識器３５は、Ｎが固有ノード数の閾値Thres以上となったか否かを判定し、まだ、閾値Thres以上となっていないと判定された場合、処理は、ステップＳ３２１に進む。

ステップ３２１において、変数Ｎの値が１だけインクリメントされ、処理は、ステップＳ３１２に戻る。

一方、ステップＳ３１３において、Ｎが閾値Thres以上となったと判定された場合、処理は、ステップＳ３１４に進む。

ステップＳ３１４において、認識器３５は、図３４、または図３６を参照して上述した認識処理を実行する。ただし、いまの場合、ステップＳ３１２の処理で時系列情報が取得されているので、その時系列情報に基づいて認識処理が実行される。

ステップＳ３１５において、学習器３４は、ステップＳ３１４における認識処理の結果、ノード列の最後のノードが未知ノードと認識されたか否かを判定する。ステップＳ３１５において、認識処理の結果、未知ノードと認識されたと判定された場合、処理は、ステップＳ３１６に進む。

ステップＳ３１６において、学習器３４は、未知ノードとみなされたノードを追加または削除する。

ステップＳ３１６では、例えば、図３７において未知ノードとみなされたノード２０１が内部モデルデータに追加されたように、ノードの追加が行なわれる。また、例えば、上述したように、誤認識を抑制するために、アンカリング前に、未知ノードとみなして追加してしまったノードの削除が行なわれる。

一方、ステップＳ３１５において、認識処理の結果、未知ノードと認識されていないと判定された場合、処理は、ステップＳ３１７に進む。

ステップＳ３１７において、学習器３４は、ステップＳ３１４における認識処理の結果、ノード列の最後のノードが既知ノードと認識されたか否かを判定する。ステップＳ３１７において、認識処理の結果、既知ノードと認識されたと判定された場合、処理は、ステップＳ３１８に進む。

ステップＳ３１８において、学習器３４および認識器３５は、図４１を参照して後述する追加または削除要否チェック処理を実行する。これにより、例えば、図３９を参照して上述したように、アンカリングの際のノードの削除要否がチェックされ、削除が必要であれば未知ノードとみなされて追加されたノードが削除される。

ステップＳ３１９において、学習器３４は、アンカリングを行なう。これにより、例えば、既知ノードから未知ノードへの状態遷移確率などが設定される。

一方、ステップＳ３１７において、認識処理の結果、既知ノードと認識されていないと判定された場合、処理は、ステップＳ３２０に進む。

ステップＳ３２０において、認識器３５は、閾値Thresの値を１だけインクリメントする。

すなわち、ステップＳ３１７において、認識処理の結果、既知ノードと認識されていないと判定された場合、認識処理において、認識結果を保留し、時系列情報を未来方向に延長する指令が出力されたことになる。例えば、図３４、または図３６を参照して上述したステップＳ２３１の処理またはステップＳ２９３の処理が行われる場合である。この場合、例えば、図３８を参照して上述したように、閾値Thresの値をインクリメントするとともに、時系列情報の長さを未来方向に延長する必要がある。

従って、ステップＳ３２０の処理の後、処理は、ステップＳ３２１に進むことになる。

このようにして、未知ノード追加処理が実行される。

次に、図４１のフローチャートを参照して、図４０のステップＳ３１８の追加または削除要否チェック処理の詳細な例について説明する。

ステップＳ３４１において、認識器３５は、長さＮの時系列情報を取得する。すなわち、自分が未知ノードに位置していると認識した時刻後の時間的長さＮの時系列情報が取得される。例えば、図３９の例の場合、ノード２０１乃至ノード２１５に対応する長さの時系列情報が取得されることになる。

ステップＳ３４２において、認識器３５は、長さＮの時系列情報に基づく認識処理を実行する。このとき、図３４、または図３６を参照して上述した認識処理を実行する。ただし、いまの場合、ステップＳ３４１の処理で時系列情報が取得されているので、その時系列情報に基づいて認識処理が実行される。

ステップＳ３４３において、学習器３４は、ステップＳ３４２における認識処理の結果、ノード列の最後のノード（時間的に最も後のノード）が既知ノードと認識されたか否かを判定する。ステップＳ３４３において、認識処理の結果、既知ノードと認識されていないと判定された場合、処理は、ステップＳ３４４に進む。

ステップＳ３４４において、認識器３５は、時系列情報の長さＮを１だけデクリメントする。この場合、時系列情報が過去側から短縮されることになる。例えば、例えば、図３９の例の場合、ノード２０１乃至ノード２１５に対応する長さの時系列情報が取得されていたものが、ノード２０２乃至ノード２１５に対応する長さの時系列情報とされることになる。

このように、ステップＳ３４３において、認識処理の結果、既知ノードと認識されたと判定されるまで、時系列情報が過去側から短縮され、繰り返し認識処理が実行されるのである。

ステップＳ３４３において、認識処理の結果、既知ノードと認識されたと判定された場合、処理は、ステップＳ３４５に進む。例えば、図３９の例の場合、ノード２０３乃至ノード２１５に対応する長さの時系列情報に基づく認識処理の結果、ノード２０３乃至ノード２１５が全て既知ノードであったと認識される。このとき、ノード２０３乃至ノード２１５のノード列におけるノード数が特定される。

ステップＳ３４５において、学習器３４は、ノード数を特定し、特定されたノード数をノード列Ｓの長さＬrとして、式（５０）を参照して上述した演算を行う。

ステップＳ３４６において、学習器３４は、追加（または削除）すべきノードがあるか否かを判定する。ステップＳ３４６において、追加（または削除）すべきノードがあると判定された場合、処理は、ステップＳ３４７に進む。一方、ステップＳ３４６において、追加（または削除）すべきノードがないと判定された場合、ステップＳ３４７の処理は、スキップされる。

ステップＳ３４７において、学習器３４は、ステップＳ３４６の処理で追加（または削除）すべきと判定されたノードを追加（または削除）する。例えば、図３９の例の場合、式（５０）より、追加すべきノードの個数ｍは、Thres＋４-（Thres＋２＋３）＝−１と算出されるので、既に追加された３つのノードのうちの１個のノード２０３が削除される。すなわち、ノード２０３は、未知ノードとして追加されており、例えば、新たなインデックスを有するノードが内部モデルデータに追加されていたが、本来は、既知ノードであって、追加したインデックスのノードは、内部モデルデータから削除されるのである。

このようにして、追加または削除要否チェック処理が実行される。

これまでに学習して得られた内部モデルデータでは表現できない、新しい状況に遭遇したときには、ノード数を増やして状況を表現し、事態を解決する必要がある。例えば、ロボットが移動する迷路が所定の方向に延長された場合、ノードの数が増えることになるので、ノード数Ｎの値を大きくする必要がある。

従来の技術では、新たなノードを検出すると、その場で直ちに内部モデルデータを拡張し、新たなノードを表すインデックスの追加が行なわれていた。

しかしながら、一般に新しい経験を取り込む際、その経験は既存の構造とどのような関係に位置づけられるのかが最重要な問題となり、例えば、新たなノードを検出した直後では既存構造との関係が十分明確でないことも多い。

従って、早急に新たなノードを表すインデックス内部モデルデータに追加することにより、今後の誤認識を招くおそれもある。例えば、新たなノードが連続して検出されるような状況では、新たなノードは直前の状態に対してしか関係性を定義できず、そのような連鎖が連続すればするほど、加速度的に既存構造に対する関係の不明瞭化が進むことになる。また、このような内部モデルデータに基づいて追加学習方式で学習を行ったとしても、学習時に調整すべきパラメータが膨大になってしまう。

そこで、本発明では、上述のように、所定のタイミングで所定の個数の未知ノードが追加されるようにするとともに、アンカリングされた直後の内部モデルデータに基づいて追加学習方式での学習が行われるようにしたのである。このようにすることで、例えば、既知ノードの中に散発的に新たなノードが発現するような場合はもちろんのこと、長期に渡って新たなノードが連続して検出されるような困難な環境においても、十分に有効な学習を行うことが可能となる。

上述のように、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張することが可能であるが、その際、それぞれのテーブルの拡張された領域に設定すべき状態遷移確率、観測確率などの値を特定する必要がある。

図３０乃至図３２において各テーブルを拡張する場合の例については説明したが、ここでは、既に記憶されている状態遷移確率から、拡張された領域のノードへの状態遷移確率などを推定して設定する方式について説明する。

例えば、図３１に示されるように状態遷移確率テーブルを拡張する必要がある場合、状態遷移確率テーブルの各行の確率の値の総和が１となるように正規化する必要があると説明した。換言すれば、図３１の例において上述した処理では、追加された領域に状態遷移確率を設定するにあたり、既に記憶されている既知ノードから既知ノードへの状態遷移確率は考慮されていなかった。しかしながら、内部モデルデータに追加された未知ノードに対して複数の既知ノードからの遷移が発生し得ることは予測可能である。

例えば、迷路におけるあるパーツＡが、別のパーツＢと置き換えられた場合、パーツＡに隣接していたパーツＣと、パーツＢとが接続されることになる。このような場合、ロボットがパーツＣからパーツＡに移動するためのアクションを実行すると、パーツＢに移動する可能性が高い。また、ロボットがパーツＡからパーツＣに移動するためのアクションを、パーツＢにおいて実行すると、パーツＣに移動する可能性が高い。この例では、パーツＢに対応するＨＭＭのノードを、未知ノードとして新たに追加する必要があるが、上記を考慮してパーツＣに対応する既知ノードとの状態遷移確率を設定すべきである。

従って、既に記憶されている既知ノードから既知ノードへの状態遷移確率に基づいて、未知ノードと既知ノードとの間の状態遷移確率などを設定することができれば、より適切に状態遷移確率を設定することができると考えられる。いわば、過去の経験に基づいて未知ノードと既知ノードとの間の状態遷移確率などを設定することができれば、より適切に状態遷移確率を設定することができるのである。

なお、ここで説明する既知ノードには、例えば、ロボットが迷路を移動中に、未知ノードとみなされて既に内部モデルデータに追加されているノードも含まれるものとする。

上述のように設定する状態遷移確率の値は、次のパターンを考慮して決める必要がある。

すなわち、現実に、ノードs_iからノードs_jへの遷移が生じた場合、ノードs_iとノードs_jが既知のノードであるのか、新たに追加された未知のノードであるのかを考慮する必要がある。

つまり、既知ノードから未知ノードへの遷移、未知ノードから未知ノードへの遷移、および未知ノードから既知ノードへの遷移の３つのパターンを考慮する必要がある。

例えば、状態遷移確率テーブルが拡張された場合、図４２に示される領域３０１−１乃至領域３０１−３に、既知ノードから未知ノードへの状態遷移確率を設定する必要がある。また、領域３０３−１乃至領域３０３−３に、未知ノードから未知ノードへの状態遷移確率を設定する必要がある。さらに、領域３０２−１乃至領域３０２−３に、未知ノードから既知ノードへの状態遷移確率を設定する必要がある。

また、上述したように、状態遷移確率テーブルの各行（例えば、ｎ行目）に記述された全ての数値を合計すると、１となるようになされているので、図４２において既存状態と記述された領域の確率もあらためて設定する必要がある。

例えば、図４３に示されるような場合を例として説明する。

すなわち、既知ノードである遷移元のノード３２１において、図中右方向への移動に対応するアクションを実行した結果、遷移する可能性の高い遷移先ノードは、状態遷移確率テーブルに基づいてノード３２２またはノード３２３と予想されていたものとする。しかしながら、実際に遷移元のノード３２１において、図中右方向への移動に対応するアクションを実行した結果、遷移した遷移先ノードはノード３２４であったとする。この場合、ノード３２４が未知ノードとなる。

図４３の例において、ノード３２１では、図２のパーツ５に対応する観測シンボルが観測され、ノード３２２では、図２のパーツ１２に対応する観測シンボルが観測され、ノード３２３では、図２のパーツ６に対応する観測シンボルが観測されている。

なお、図４３においては、迷路のパーツを表す矩形に対してノード３２１乃至ノード３２４の符号が付されているが、実際には、それらのパーツに対応する観測シンボルが観測されたノードに対して付される符号である。すなわち、エージェントは、ノード３２１乃至ノード３２３を、学習済の内部モデルデータに基づいて一意に認識することができたのであり、ノード３２４は、これまでに記憶されていない内部状態（ノード）として認識されたものとなる。

つまり、エージェントは、ノード３２１から図中右方向に移動すると、図中上向きの曲がり角（ノード３２２）または図中下向きの曲がり角（ノード３２３）に出るものと予想していた。

しかしながら、実際にノード３２１から図中右方向に移動してみると、十字路（ノード３２４）に出たのである。すなわち、ノード３２４では、図２のパーツ１５に対応する観測シンボルが観測されている。

例えば、迷路におけるノード３２１に対応する位置に配置されていたパーツが置き換えられた場合、このような状況となる。このような場合、ノード３２４は、それまでの内部モデルデータには存在しなかったノードと考えられるから、少なくともノード３２４を内部モデルデータに追加する必要がある。

このような場合、ノード３２４に対応する新たなインデックスが生成されて状態遷移確率テーブルの行列が追加される。従って、右方向のアクションに対応する状態遷移確率テーブルのノード３２１からノード３２４への状態遷移確率を設定する必要がある。ただし、実際に、新たなインデックスが生成されて状態遷移確率テーブルの行列が追加されるタイミングについては、図３７乃至図４１を参照して上述した通りである。

この状態遷移確率は、例えば、ノード３２１からノード３２２およびノード３２３への状態遷移確率の和を３で割った値を、設定する。このとき、ノード３２１からノード３２２およびノード３２３への状態遷移確率もそれぞれの状態遷移確率に応じた重みづけにより案分されて設定されるようにすればよい。

ノード３２１（例えば、ノードs_iとする）から右方向のアクション（例えば、アクションｋ´とする）により遷移し得るノードの候補s_j ^l（l=1，・・・L）は、例えば、状態遷移確率a_ij（k´）が閾値以上となる遷移先のノードs_jをリストすればよい。

図４３の例では、ノード３２１から右方向のアクションにより遷移し得るノード３２２およびノード３２３の２つのノードが候補ノードとしてリストされることになる。この場合、Ｌの値は２となる。

未知ノードであるノード３２４をノードs_newで表し、アクションk´に対応する各既知ノードs_iからs_newへの状態遷移確率a_inew(k´)は、1/Lとして設定する。

図４３の例では、ノード３２１からノード３２４への状態遷移確率が１／２として設定されることになる。

状態遷移確率a_inew(k´)は、図４２の例における領域３０１−１乃至領域３０１−３のいずれかの領域に設定されるものとなる。

そして、アクションk´に対応する状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する。すなわち、状態遷移確率a_inew(k´)として非零値が設定された行の各値をL/（L+1）倍すればよい。

ただし、状態遷移確率a_ij（k´）が閾値以上となる遷移先のノードが存在しなかった場合、状態遷移確率a_inew(k´)≒１として、上述のような正規化を行なう。

なお、ノード３２１においてアクションｋ´以外のアクションを実行することによりノード３２４に遷移する状態遷移確率は、０に近い微小な値を設定すればよいので、状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する必要はない。

また、図４４の図中の矢印で示されるに示されるように、十字路であるノード３２４においては、上下左右方向の４つアクションを実行して他のノードに遷移することが可能である。従って、上下左右方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率も設定する必要がある。これらの状態遷移確率は、図４２の例における領域３０２−１乃至領域３０２−３のいずれかに設定されるものとなる。なお、未知ノードから未知ノードへの遷移があり得る場合は、上記に加えて図４２の例における領域３０３−１乃至領域３０３−３のいずれかも含まれることになる。

例えば、上方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２２から既知の各ノードへの状態遷移確率をコピーする。ノード３２２は、上向きの曲がり角であり、ノード３２１から右方向のアクションによって遷移し得るノードのうち、上方向のアクションにより他の既知ノードへ遷移し得る唯一のノードだからである。なお、ノード３２２から既知の各ノードへの状態遷移確率については何も変更しない。

また、例えば、下方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２３から既知の各ノードへの状態遷移確率をコピーする。ノード３２３は、下向きの曲がり角であり、ノード３２１から右方向のアクションによって遷移し得るノードのうち、下方向のアクションにより他の既知ノードへ遷移し得る唯一のノードだからである。なお、ノード３２３から既知の各ノードへの状態遷移確率については何も変更しない。

さらに、左方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、ノード３２２から既知の各ノードへの状態遷移確率とノード３２３から既知の各ノードへの状態遷移確率を平均化した値とされる。ノード３２２とノード３２３は、ノード３２１から右方向のアクションによって遷移し得るノードのうち、左方向のアクションにより他の既知ノードへ遷移し得るノードだからである。すなわち、ノード３２２およびノード３２３の状態遷移確率の平均値をもって、左方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率とすればよい。なお、このとき、ノード３２２およびノード３２３から既知の各ノードへの状態遷移確率については何も変更されない。

また、右方向のアクションに対応する状態遷移確率テーブルのノード３２４から既知の各ノードへの状態遷移確率は、例えば、それぞれ一様の値を設定する。図４５に示されるように、右方向のアクションにより他の既知ノードへ遷移し得る候補のノードが他にないからである。

さらに、ノード３２１以外の各既知ノードからノード３２４への状態遷移確率も設定する必要がある。

ノード３２４は十字路だから、他のノードからノード３２４への遷移は、上下左右方向のいずれのアクションによっても起こりえる。すなわち、上方向のアクションによってノード３２４に遷移する遷移元のノードが存在し、下方向のアクションによってノード３２４に遷移する遷移元のノードが存在するはずである。また、左方向のアクションによってノード３２４に遷移する遷移元のノードが存在し、右方向のアクションによってノード３２４に遷移する遷移元のノードが存在するはずである。

この場合、遷移元のノードを特定するとともに、遷移元のノードのそれぞれにおいてどのアクションを実行することによりノード３２４へ遷移するのかを特定しなければならない。すなわち、未知ノードへの逆方向遷移アクションを特定する必要がある。

まず、遷移元のノードの推定の根拠となる情報を得るために、ノード３２４に類似するノードを抽出する。ノード３２４に類似するノードとは、例えば、仮にエージェントが現在ノード３２４以外のノードにいるとした場合、ある程度確からしいノードということもできる。

例えば、迷路の構造上似通った部分が複数存在する場合を考える。エージェントは、それらの部分の１つであって所定のパーツ上に存在しているものとする。このような場合、実際には、エージェントが認識した部分とはことなる部分の所定のパーツ上に存在している可能性もある。このように、エージェントが認識したノードに類似するノードを抽出することができるのである。

類似するノードは、過去ｎステップ分の時系列情報を用いたｎ-ステップ状態認識により特定することができる。

時刻tにおいて、過去ｎステップ分のアクションのシーケンスc_t？n，・・・，c_t？1および過去n+1ステップ分の観測シンボルのシーケンスo_t？n，・・・，o_tを用いて現在のノードを推定したり、現時刻tにおいてエージェントが各ノードに存在する確率を計算したりすることを「n-ステップ状態認識」と称する。

ｎ-ステップ状態認識では、最初に、インデックスｉ（i=1，・・・N）のノードに対応する事前確率π_iが、例えば、予め決められた方式で設定される。

その後、認識器３５が、時刻t-nにおいてエージェントが各ノードに存在する確率δ_t-n(i)を式（５２）により演算する。

・・・（５２）

そして、認識器３５は、時刻τ=t-n+1，・・・tの順に、エージェントが各ノードに存在する確率δτ(i)を式（５３）の漸化式により演算する。

・・・（５３）

あるいはまた、式（５３）に替えて式（５４）の演算が行われるようにしてもよい。

・・・（５４）

認識器３５は、さらに、式（５３）または式（５４）における最終時刻tにおいてエージェントが各ノードに存在する確率δ_t(i)を正規化することにより、時刻tにおける各ノードについての状態確率δ´_t(i)を式（５５）により演算する。

・・・（５５）

式（５５）により得られた状態確率が予め定められた閾値以上となるノードのそれぞれが、類似するノードとされる。

なお、ｎ-ステップ状態認識では、過去ｎステップ分のアクションのシーケンスおよび観測シンボルのシーケンスが用いられるが、ｎを０とすると、観測シンボルo_tが所定の閾値以上の確率で観測されるノードの全てが類似するノードとなる。また、ｎを大きくするほど、類似するノードの数も、通常少なくなっていく。ｎ-ステップ状態認識におけるｎの値は、例えば、本発明において行なわれる推定等に用いて好適となるような予め設定された値とされるものとする。

類似ノードが得られたら、それらのノードにおいて実行されることにより、他のノードに遷移し得るアクションを特定する。例えば、ノード３２４は十字路であるから、ノード３２４に類似するノードも十字路である可能性が高い。そうすると、類似するノードでは、上下左右方向の移動のアクションにより他のノードに遷移できることになる。

そしてそれらのアクションを実行して他のノードに遷移し得る既知ノードを特定する。例えば、ノード３２１から右方向のアクションによって遷移し得る既知ノードであるノード３２２でも、それぞれ左方向および上方向のアクションを実行することにより、他のノードに遷移し得る。同様に、ノード３２１から右方向のアクションによって遷移し得る既知ノードであるノード３２３でも、それぞれ左方向および下方向のアクションを実行することにより、他のノードに遷移し得る。

そうすると、未知ノード３２４には、ノード３２２において、それぞれ左方向および上方向のアクションを実行することで遷移する遷移先ノードのそれぞれから、左方向および上方向の逆方向となるアクションによって遷移し得ると仮定できる。この場合、右方向および下方向が逆方向となるアクション（逆方向遷移アクション）となる。

また、未知ノード３２４には、ノード３２３において、それぞれ左方向および下方向のアクションを実行することで遷移する遷移先ノードのそれぞれから、左方向および下方向の逆方向となるアクションによって遷移し得ると仮定できる。この場合、右方向および上方向が逆方向となるアクション（逆方向遷移アクション）となる。

逆方向遷移アクションは、例えば、次のようにして推定することができる。例えば、アクションc_zによってノードs_aからノードs_bへの遷移が起きる場合、逆方向遷移、すなわちノードs_bからノードs_aへの遷移を起こすためのアクションc_z′を推定する。

逆方向遷移アクションを推定するにあたり、認識器３５は、上述したように類似するノードであって既知ノードを特定する。ここで特定された既知ノードのそれぞれを、ノードs_j ^q（q=1，・・・Q）で表すことにする。

そして、認識器３５は、ノードs_j ^qのそれぞれについて、アクションc_zによってノードs_j ^qに遷移する遷移元ノードを抽出する。この場合、例えば、状態遷移確率a_ij ^q(z）が閾値以上となるノードs_iをリストすればよい。

そして、認識器３５は、(s_j ^q，s_i ^q，l)(q= 1，・・・，Q， l= 1，・・・，L_q)の全ての組み合わせについて、ノードs_j ^qからノードs_i ^q，lへの状態遷移確率の平均値a^*(k)を式（５６）により演算する。

・・・（５６）

このようにして得られた状態遷移確率の平均値a^*(k)のうち、閾値以上となるものを選択し、そのa^*(k)に対応するアクションc_kを特定すれば、逆方向遷移アクションc_z ^r´(r＝1，・・・，R)を特定することができる。

このようにして特定された遷移元のノードで、逆方向遷移が実行されることによりノード３２４へ遷移すると仮定すれば、上述したノード３２１からノード３２４への状態遷移確率を設定する場合と同様の操作により状態遷移確率を設定することができる。

このように考えると、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、図４２に示される領域の全ての状態遷移確率を再設定する必要がある。

すなわち、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、未知ノードにおいて実行し得るアクションと、そのアクションにより遷移し得る遷移先のノードとを特定する必要がある。このようにすれば、それら特定されたアクションと遷移先ノードとのペアから、状態遷移確率テーブルの所定の行列位置を特定することができ、それらの位置に設定すべき状態遷移確率の値を設定するとともに、その行の各値を正規化するなどすればよい。

また、未知ノードとみなされたノードのインデックスに対応する行列を状態遷移確率テーブルに追加するときには、未知ノードに遷移し得る遷移元ノードと、その遷移元ノードから未知ノードに遷移するためのアクションとを特定する必要がある。このようにすれば、それら特定されたアクションと遷移元ノードとのペアから、状態遷移確率テーブルの所定の行列位置を特定することができ、それらの位置に設定すべき状態遷移確率の値を設定するとともに、その行の各値を正規化するなどすればよい。

従って、上記に示したように、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルを拡張した場合、拡張された領域に設定すべき状態遷移確率の値を設定する処理は、最終的には、例えば、図４６に示される手順で実行されるようにすることができる。

図４６は、ノード追加時の状態遷移確率設定処理を説明するフローチャートである。この処理は、例えば、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルなどに未知ノードを追加するとき実行される。

なお、ここでは、未知ノードs_newが内部モデルデータに追加されるものとし、エージェントがノードs_newに遷移する直前のノードをノードs_i′とし、ノードs_i′においてアクションc_k′が実行されることによりエージェントはノードs_newに遷移したものとする。

ステップＳ４０１において、認識器３５は、図４７のフローチャートを参照して後述するノード逆アクションペアリスト生成処理を実行する。

これにより、未知ノードへの遷移元のノードが特定されるとともに、未知ノードへの逆方向遷移アクションが特定されることになる。

ステップＳ４０２において、学習器３４は、図４８のフローチャートを参照して後述する逆アクション状態遷移確率設定処理を実行する。

これにより、ステップＳ４０１の処理により特定された遷移元のノードにおいて逆方向遷移アクションを実行することにより未知ノードへ遷移する状態遷移確率が設定される。また、ここで新たに設定された状態遷移確率に応じて状態遷移確率テーブルの各行の値が正規化される。

ステップＳ４０３において、認識器３５は、図４９のフローチャートを参照して後述するノード順アクションペアリスト生成処理を実行する。

これにより、未知ノードからの遷移先のノードが特定されるとともに、未知ノードからそれらの遷移先ノードへ遷移するための順方向遷移アクションが特定されることになる。

ステップＳ４０４において、学習器３４は、図５０のフローチャートを参照して後述する順アクション状態遷移確率設定処理を実行する。

これにより、未知ノードにおいて、ステップＳ４０３の処理により特定された順方向遷移アクションを実行することにより遷移先のノードへ遷移する状態遷移確率が設定される。また、ここで新たに設定された状態遷移確率に応じて状態遷移確率テーブルの各行の値が正規化される。

次に、図４７のフローチャートを参照して、図４６のステップＳ４０１のノード逆アクションペアリスト生成処理の詳細について説明する。

ステップＳ４２１において、認識器３５は、ノードs_i′においてアクションc_k′が実行されることにより遷移し得る候補ノードs_j ^l（l=1，・・・L）を抽出する。候補ノードs_j ^lは、例えば、状態遷移確率a_i´j（k´）が閾値以上となる遷移先のノードs_j´をリストすればよい。

ステップＳ４２２において、認識器３５は、過去ｎステップ分の時系列情報を用いたｎ-ステップ状態認識を行なう。

ステップＳ４２３において、認識器３５は、ステップＳ４２２の処理結果に基づいて、ノードs_newに類似する類似ノードであって既知ノードを抽出する。ここで特定された既知ノードのそれぞれを、ノードs_j ^q（q=1，・・・Q）で表すことにする。このとき、上述した式（５２）乃至式（５５）の演算が行われることにより、ノードs_newに類似する類似ノードが抽出される。

ステップＳ４２４において、認識器３５は、ステップＳ４２３の処理で抽出された類似ノードの有効アクションを抽出する。

ここで、有効アクションは、上述した各類似ノードにおいて実行されることにより、他のノードに遷移し得るアクションを意味する。

ステップＳ４２４では、例えば、アクション毎の評価値E_kが、式（５７）により演算される。なお、この演算は、個々のアクションに対応してそれぞれ行われ、１のアクションに対して１の評価値が得られることになる。

・・・（５７）

ここでa_jx ^q(k)(q=1，・・・，Q， x=1，・・・，N)は、ノードs_j ^q(q=1，・・・，Q)においてアクションc_kを実行したとき、ノードs_xに遷移する状態遷移確率である。

そして、式（５７）により演算された評価値が閾値以上となったアクションｋが選択され、有効アクションの候補とされる。

さらに、その選択されたアクションｋのそれぞれについて、状態遷移確率a_jx ^q(k)がチェックされ、状態遷移確率a_jx ^q(k)が閾値以上となる(q，x)の組が少なくとも1つ存在するか否かが判定される。そのような(q，x)の組が1つも存在しない場合、そのアクションｋは、有効アクションの候補から除外される。

このようにして、ステップＳ４２４では、有効アクションc_k ^r(r=1，・・・，R)が抽出される。

ステップＳ４２５において、認識器３５は、ステップＳ４２１の処理で抽出された候補ノードs_j ^lのうち、ステップＳ４２４の処理で抽出されたアクションc_k ^rを有効アクションとして有するものを抽出する。すなわち、候補ノードのうち、類似ノードと同一の有効アクションを有するノードs_j ^ru (u=1，・・・，Ur)が抽出される。

ステップＳ４２５では、例えば、ノードs_j ^lのそれぞれについて評価値Elrが式（５８）により演算される。なお、この演算は、ノードs_j ^lのそれぞれにおいて、個々のアクションc_k ^rを実行する場合のそれぞれに対応してそれぞれ行われ、ノードとアクションの組み合わせ１つに対して１の評価値が得られることになる。

・・・（５８）

なお、式（５８）は、変数lにより特定されるインデックスjの候補ノードで、変数ｒで特定されるアクションc_kを実行する場合について算出される。また、式（５８）の右辺の状態遷移確率のアクションであるｋ（またはc_k）は、左辺の変数ｒにより特定されるものとする。

このように、ステップＳ４２５では、式（５８）により算出された評価値が閾値以上となったものが、ノードs_j ^ruとして抽出されるのである。

ステップＳ４２６において、認識器３５は、ステップＳ４２５で抽出されたノードとステップＳ４２４で抽出された有効アクションのペア(s_j ^ru，c_k ^r)を生成し、それぞれのペアから特定される遷移先ノードを特定する。

例えば、ノードs_j ^ruにおいて、アクションc_k ^rを実行した場合の状態遷移確率a_jl ^ru(k)（l=1，・・・，N）をチェックし、閾値を超える状態遷移確率に対応する遷移先ノードs_l ^q（q=1，・・・Q_ru）を特定する。

ステップＳ４２７において、認識器３５は、ノードs_j ^ruにおけるアクションc_k ^rの逆方向遷移アクションを推定する。すなわち、ノードs_l ^qからノードs_j ^ruへ遷移するためのアクションを推定する。このとき推定された逆方向遷移アクションを、c_ruq ^v（v=1，・・・V_ruq）とする。ただし、遷移先ノードがノードs_i′であった場合は、この推定は行なわない。

そして、認識器３５は、ステップＳ４２６で特定された遷移先ノードと、逆方向遷移アクションとのペア（s_l ^q，c_ruq ^v）(l=1，・・・，L， r=1，・・・，R， u=1，・・・，Ur， q=1，・・・，Qru， v=1，・・・，Vruq)を生成する。

ステップＳ４２８において、認識器３５は、ステップＳ４２７で生成したペア（s_l ^q，c_ruq ^v）に（s_i′，c_k′）を加えて重複を排除し、未知ノードへの遷移元ノードと逆方向遷移アクションのペア(s_i ^x，c_k ^x)(x=1，・・・，X)を生成する。そして、未知ノードへの遷移元ノードと逆方向遷移アクションのペアのそれぞれがリストされる。

このようにして、ノード逆アクションペアリスト生成処理が実行される。

図４７の処理により得られたペアに基づいて、ノードs_i ^xにおいてアクションc_k ^xを実行することによりノードs_newに遷移したと仮定され、図４６のステップＳ４０２の処理が実行される。

次に、図４８のフローチャートを参照して、図４６のステップＳ４０２の逆アクション状態遷移確率設定処理の詳細な例について説明する。

例えば、遷移元ノードs_iからアクションc_ｋによりノードs_newに遷移したと仮定されたものとする。

ステップＳ４４１において、学習器３４は、アクションc_ｋにより、ノードs_iから遷移し得るノードの候補を抽出する。ノードの候補s_j ^l（l=1，・・・L）は、例えば、状態遷移確率a_ij（k）が閾値以上となる遷移先のノードs_jをリストすればよい。

ステップＳ４４２において、学習器３４は、未知ノードへの状態遷移確率を設定し、正規化する。

例えば、アクションc_ｋに対応する各候補ノードs_iからs_newへの状態遷移確率a_inew(k)は、1/Lとして設定する。そして、アクションc_ｋに対応する状態遷移確率テーブルの各行の状態遷移確率の総和が１となるように正規化する。すなわち、状態遷移確率a_inew(k)として非零値が設定された行の各値をL/（L+1）倍する。

ただし、ステップＳ４１１の処理の結果、状態遷移確率a_ij（k）が閾値以上となる遷移先のノードが存在しなかった場合、状態遷移確率a_inew(k)≒１として、上述のような正規化を行なう。

このようにして、逆アクション状態遷移確率設定処理が実行される。

次に、図４９のフローチャートを参照して、図４６のステップＳ４０３のノード順アクションペアリスト生成処理の詳細な例について説明する。

ステップＳ４６１において、認識器３５は、図４７のステップＳ４２６の処理と同様に遷移先ノードs_l ^q（q=1，・・・Q_ru）を抽出する。すなわち、候補ノードと有効アクションのペアを生成し、各ペアに対応する遷移先ノードを特定する。

ステップＳ４６２において、認識器３５は、ステップＳ４６１の処理で得られた遷移先ノードs_l ^q（q=1，・・・Q_ru）と、その遷移先ノードに遷移するためのアクションc_k ^r（r=1，・・・R）をペアとして生成する。

ステップＳ４６３において、認識器３５は、ステップＳ４６２の処理で得られたペアの重複を排除し、ペア（s_j ^y，c_k ^y）(y=1，・・・，Y)を生成する。そして、遷移先ノードとその遷移先ノードへ遷移するためのアクションのペアのそれぞれがリストされる。

このようにして、ノード順アクションペアリスト生成処理が実行される。

図４９の処理により得られたペアに基づいて、ノードs_newにおいてアクションc_k ^yを実行することによりノードs_j ^yに遷移したと仮定され、図４６のステップＳ４０４の処理が実行される。

次に、図５０のフローチャートを参照して、図４６のステップＳ４０４の順アクション状態遷移確率設定処理の詳細な例について説明する。

ステップＳ４８１において、学習器３４は、状態遷移確率a_newj（k）(j=1，・・・，N， k=1，・・・，K)を、全て微小な値で初期化する。

ステップＳ４８２において、学習器３４は、図４８の処理により得られたペア（s_j ^y，c_k ^y）を用いて状態遷移確率を設定する。すなわち、ノードs_newにおいてアクションc_k ^yを実行することによりノードs_j ^yに遷移する状態遷移確率a_newj ^y(k)を１として設定する。

ステップＳ４８３において、学習器３４は、Σ_ja_newj(k)（k=1，・・・，K)を満たすように正規化する。

このようにして順アクション状態遷移確率設定処理が実行される。

上記した例においては、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブルに未知ノードを追加する場合の例について説明したが、これに伴って、観測確率テーブルにも未知ノードを追加する必要がある。この場合の、観測確率テーブルの更新については、例えば、図３１に示されるように観測確率テーブルを拡張する必要がある場合に、学習器３４が行う処理として上述した処理を行うようにすればよい。

また、勿論、状態遷移確率の推定のための頻度変数のテーブル、および観測確率の推定のための頻度変数のテーブルも図４６を参照して上述した処理に伴って更新されることになる。

次に、アンカリングする場合の状態遷移確率の設定について説明する。

上述したように、アンカリングは、既知ノードへの遷移が認識された場合、未知ノードとみなされたノードと既知ノードとの状態遷移確率などを設定する処理である。

換言すれば、未知ノードs_i´においてアクションc_k´を実行して、既知ノードs_j´に遷移した場合、内部モデルデータの状態遷移確率テーブルにおいて、状態遷移確率a _i´j(k´）(j=1，・・・，N)が閾値以上となるノードs_jが存在しないとき、アンカリングが行なわれる。すなわち、未知ノードとみなされたノードから、既知ノードへの遷移が確認され、かつ当該未知ノードから当該既知ノード以外のノードへの遷移が発生し難い場合、アンカリングが行われるのである。

アンカリングでは、アクションc_k´による未知ノードs_i´から既知ノードs_j´への状態遷移確率が設定される。例えば、図４６を参照して上述したように、未知ノードとみなされたノードが内部モデルデータに追加される都度、その未知ノードから既知ノードへの状態遷移確率が推定されて設定される。しかし、未知ノードから既知ノードへの遷移が実際に発生した場合は、アンカリングがなされることになる。

ここで、図５１のフローチャートを参照してアンカリング処理について説明する。この処理は、例えば、図４０のステップＳ３１９の処理として実行される処理である。

ステップＳ５０１において、学習器３４は、アンカリングの対象となる遷移に対応する状態遷移確率を１とする。上述の例では、状態遷移確率a _i´j´(k´）が１とされる。

ステップＳ５０２において、学習器３４は、Σ_ja _i´j(k´）が１となるように、状態遷移確率テーブルの各値を正規化する。

ステップＳ５０３において、認識器３５は、既知ノードs_j´から未知ノードs_i´に遷移する逆方向遷移アクションを推定する。このとき、例えば、図４７を参照して上述した場合と同様に逆方向遷移アクションの推定が行なわれる。これにより、逆方向遷移アクションc_z ^r(r=1，・・・，R)が推定される。

ステップＳ５０４において、学習器３４は、ステップＳ５０３の処理で推定された逆方向遷移アクションのそれぞれが実行されることにより、既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定して状態遷移確率を設定する。この処理は、例えば、図４８を参照して上述した場合と同様である。

このようにしてアンカリング処理が実行される。

なお、図５１を参照して説明した処理に替えて、既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定して図４６を参照して上述した処理が行われることにより状態遷移確率を設定することで、アンカリング処理がなされるようにしてもよい。

すなわち、実際には、未知ノードs_i´においてアクションc_k´を実行して、既知ノードs_j´に遷移したのだが、逆方向遷移アクションc_z ^r (r=1，・・・，R)によって既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定するのである。ここで、逆方向遷移アクションc_z ^r (r=1，・・・，R)は、例えば、ステップＳ５０３の処理と同様にして推定することができる。

つまり、アクションc_z ¹によって、既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定して図４６を参照して上述した処理を実行する。また、アクションc_z ²によって、やはり、既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定して図４６を参照して上述した処理を実行する。同様に、アクションc_z ³・・・アクションc_z ^Rによって、それぞれ既知ノードs_j´から未知ノードs_i´への遷移が発生したと仮定して図４６を参照して上述した処理を実行するのである。

アンカリングの際には、このように、アクションc_z ^r (r=1，・・・，R)によって直前のノードs_j′（実際には、アンカリングする既知ノード）から未知ノードs_i′へ遷移したものとみなして、図４６の処理がそれぞれ実行されるようにしてもよい。

このように、本発明によれば、エージェントが自律的に環境の変化を認識して、状態遷移確率テーブル、および観測確率テーブルを拡張することが可能である。また、その際に、それぞれのテーブルの拡張された領域に設定すべき状態遷移確率、観測確率などの値を適切に設定することも可能である。さらに、既に記憶されている既知ノードから既知ノードへの状態遷移確率に基づいて、未知ノードと既知ノードとの間の状態遷移確率などを設定することが可能である。

ここまで、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更する必要に迫られた場合にとり得る処置について説明した。

以上のように、本発明によれば、アクション拡張型ＨＭＭを用いた学習を行うことができる。これにより、エージェントがアクション信号を用いて環境に対してアクションを実行し、今後観測される観測シンボルに影響を与えることができるようにするという状況における学習が可能となる。

また、本発明によれば、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うことができる。すなわち、学習される内部モデルデータに対してスプリットアルゴリズムを適用するなどして一状態一観測制約を課し、フォワードマージアルゴリズムおよびバックワードマージアルゴリズムを適用するなどしてアクション遷移制約を課す。これにより、計算すべきパラメータの数の増大などを抑制し、必然的に大規模となるアクション拡張型ＨＭＭの学習を効率的かつ適切に行うことができる。

さらに、本発明によれば、必然的に大規模となるアクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができる。すなわち、状態遷移確率の推定のための頻度変数と観測確率の推定のための頻度変数とを算出して保存することにより、アクション拡張型ＨＭＭにおける追加学習方式での学習を安定的に行うことができる。

また、本発明によれば、学習を進める際に、ノード数、観測シンボル数、またはアクション数を変更することが可能である。

この際、例えば、エージェントに対して予め所定の数だけノードの数が増えることを前提として、内部モデルデータを拡張するように指令することも可能であるし、エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張することも可能である。

エージェントが自律的に環境の変化を認識して、内部モデルデータを拡張するために、エージェントが、現在自分が位置するノードは学習済の内部状態とされているノードなのか、新たに追加すべき内部状態とされるノードなのか認識できるようにした。

また、所定のタイミングで所定の個数の未知ノードが追加されるようにするとともに、アンカリングされた直後の内部モデルデータに基づいて追加学習方式での学習が行われるようにした。これにより、例えば、既知ノードの中に散発的に新たなノードが発現するような場合はもちろんのこと、長期に渡って新たなノードが連続して検出されるような困難な環境においても、十分に有効な学習を行うことが可能となった。

さらに、内部モデルデータを拡張するにあたり、過去の経験に基づいて未知ノードと既知ノードとの間の状態遷移確率などを設定することができるようにした。

このように、本発明によれば、変化する環境の中で自律的な学習を行う際に、効率的かつ安定的な学習を行うことができるのである。

以上においては、本発明の実施の形態を主に、ロボットが迷路を移動する場合の例に適用して説明したが、勿論、それ以外の実施の形態であっても構わない。例えば、アクションは、エージェントを移動させるものに限られず、環境に対して働きかける行為であればアクションとなり得る。また、例えば、観測シンボルは、迷路のパーツの形状などに対応するものに限られず、光や音の変化などに対応するものであってもよい。

なお、上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータにインストールされる。例えば、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、図５２に示されるような汎用のパーソナルコンピュータ７００などに、ネットワークや記録媒体から、そのソフトウェアを構成するプログラムがインストールされる。

図５２において、ＣＰＵ（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）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア７１１により構成されるものだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているＲＯＭ７０２や、記憶部７０８に含まれるハードディスクなどで構成されるものも含む。

なお、本明細書において上述した一連の処理は、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。

また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。

１０ 自律行動学習装置， ３１ センサ部， ３２ 行動出力部， ３３ 観測バッファ， ３４ 学習器， ３５ 認識器， ３６ 行動生成器， ３７ 内部モデルデータ記憶部， ３８ 認識結果バッファ， ３９ 行動出力バッファ

Claims (12)

1. 環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、
   時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、
   前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、
   前記認識手段は、可変長の前記時系列情報を読み出して認識する
   認識装置。
2. 前記認識手段は、
   前記時系列情報に基づいて、前記時系列情報の長さに対応するノード列を認識し、
   前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるまで、
   前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長する
   請求項１に記載の認識装置。
3. 前記認識手段は、
   前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、
   前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在しないと判定された場合、前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識して認識結果として出力し、
   前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定され、かつ前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満と判定された場合、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードであると認識して認識結果として出力する
   請求項２に記載の認識装置。
4. 前記認識結果を、認識された時刻と対応付けて記憶する認識結果記憶手段をさらに備える
   請求項３に記載の認識装置。
5. 前記認識手段は、
   前記認識結果記憶手段に記憶されている認識結果が、時間の経過に伴って既知ノードから未知ノードに変化した時刻を特定し、
   前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長することにより、前記特定された時刻より時間的に前の時系列情報が読み出される場合、
   認識結果の出力を保留する
   請求項４に記載の認識装置。
6. 前記認識手段は、
   長さＮの前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値と、長さＮ＋１の前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値との差分を算出し、
   前記算出された差分が第３の閾値未満となるまで、前記観測シンボル記憶手段から読み出す前記時系列情報の長さを過去方向に延長する
   請求項１に記載の認識装置。
7. 前記認識手段は、
   前記過去方向に延長された前記時系列情報に基づいて前記時系列情報の長さに対応するノード列を認識し、
   前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値未満の確率で存在すると判定された場合、
   前記時系列情報の最後の時刻における前記ノードが、新たに追加すべき内部状態の未知ノードであると認識する
   請求項６に記載の認識装置。
8. 前記認識手段は、
   前記環境において前記ノード列が、前記ＨＭＭの状態遷移確率および観測確率に基づいて、第１の閾値以上の確率で存在すると判定された場合、
   前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値未満となるとき、前記時系列情報の最後の時刻における前記ノードが、学習済の内部状態の既知ノードである認識し、
   前記時系列情報の最後の時刻における前記ノードの事後確率のエントロピーの値が第２の閾値以上となるとき、認識結果の出力を保留する
   請求項７に記載の認識装置。
9. 前記環境に対して自分が実行する行動を行動シンボルとし特定し、時間の経過に伴って得られる前記行動シンボルを、前記行動が実行された時刻と対応付けて記憶する行動シンボル記憶手段をさらに備え、
   前記観測シンボル記憶手段に記憶された情報と時間的に同じ長さの情報が前記行動シンボル記憶手段から読み出され、前記時系列情報とされる
   請求項１に記載の認識装置。
10. 時間の経過に伴って観測される環境から得られるセンサ信号に基づく前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段に記憶された情報を可変長の時系列情報として読み出し、
    前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する
    認識方法。
11. コンピュータを、
    環境から得られるセンサ信号に基づいて観測シンボルを観測する観測手段と、
    時間の経過に伴って観測される前記観測シンボルを、前記観測シンボルが観測された時刻と対応付けて記憶する観測シンボル記憶手段と、
    前記観測シンボル記憶手段に記憶された情報を時系列情報として読み出し、前記時系列情報の最後の時刻におけるＨＭＭのノードを認識する認識手段とを備え、
    前記認識手段は、可変長の前記時系列情報を読み出して認識する認識装置として機能させる
    プログラム。
12. 請求項１１に記載のプログラムが記録されている記録媒体。

Images