(57)【要約】【課題】問題に関して状態と行動との複数の組み合わせについての評価値が算出された後に当該問題が変化した場合に、状態と行動との複数の組み合わせについての評価値の再学習処理をより効率的に行う。【解決手段】学習部２４は、格子世界１８において、車両を現在位置から目的位置へ向かわせる問題Ｍに関して、状態ｓと行動ａとの複数の組み合わせそれぞれについての評価値Ｑ（ｓ，ａ）を学習する。状態集合識別部２８は、問題Ｍが問題Ｍ’に変化した場合に、問題Ｍ’において取り得る複数の状態を、学習不要状態集合６０と再学習状態集合６２とに識別する。重み設定部３０は、学習不要状態集合６０と再学習状態集合６２との境界状態であるフロンティアへ到達するまでの行動回数が少ない状態程、大きい重みを設定する。学習部２４は、再学習状態集合６２に含まれる状態のうち、重みが大きい状態程、より多く初期状態として選択した上で再学習を行う。【選択図】図１
2019175058.tif 000002
【特許請求の範囲】
【請求項１】
報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習する強化学習装置であって、
前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別部と、
前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定部と、
前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習部と、
を備えることを特徴とする強化学習装置。
【請求項２】
前記強化学習装置は、道路ネットワークが格子で表現された格子世界において、前記行動主体としての車両が目的地に到達することで報酬が得られる問題に関して、前記状態としての前記格子世界における車両の現在位置と、前記行動としての前記車両の前記格子世界におけるいずれかの方向への移動との組み合わせについての前記評価値を学習するものであり、
前記状態集合識別部は、前記格子世界が変化した場合に、前記格子世界の変化前と変化後との間において、前記目的地までの最短距離が変化しなかった状態の集合を前記学習不要状態集合と識別し、前記目的地までの最短距離が変化した状態の集合を前記再学習状態集合と識別する、
ことを特徴とする請求項１に記載の強化学習装置。
【請求項３】
前記格子世界において、格子のマス目間に移動コストが定義されており、
前記強化学習装置は、前記移動コストをさらに考慮して前記評価値を学習する、
ことを特徴とする請求項２に記載の強化学習装置。
【請求項４】
前記道路ネットワークを示す道路情報に基づいて、前記格子世界を生成する格子世界生成部と、
をさらに備えることを特徴とする請求項２または３に記載の強化学習装置。
【請求項５】
報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習するコンピュータを、
前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別部と、
前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定部と、
前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習部と、
として機能させることを特徴とする強化学習プログラム。
【請求項６】
報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習する強化学習方法であって、
前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別ステップと、
前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定ステップと、
前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習ステップと、
を備えることを特徴とする強化学習方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、強化学習装置、強化学習プログラム、及び強化学習方法に関する。
【背景技術】
【０００２】
従来、機械学習に関する研究が行われている。特に、機械学習の手法の１つである強化学習に関する研究が行われている。強化学習とは、報酬が存在する問題に関して、意思決定を行う行動主体が、現在の状態において取るべき行動を決定する機械学習である。具体的には、行動主体は、行動を選択することで環境から報酬を得、強化学習では、一連の行動を通じて報酬が最も多く得られるように学習を行う。
【０００３】
例えば、非特許文献１には、強化学習の１つの手法であるＱ学習が開示されている。また、非特許文献２には、Ｑ学習の改良法であり、様々な強化学習タスクについてより良い性能を実験的に示すｎ−Ｑ学習が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Watkins, Christopher JCH and Peter Dayan, “Q-Learning”, Machine Learning vol.8(3-4), pp.279-292, 1992
【非特許文献２】Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, Koray Kavukcuoglu, Asynchronous Methods for Deep Reinforcement Learning, Proc. of ICML2016, PMLR 48:1928-1937, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
強化学習においては，与えられた問題Ｍにおける状態ｓと，各状態ｓにおいて行動主体が取り得る行動ａとの複数の組み合わせについての評価値Ｑ（ｓ，ａ）を学習するのが一般的である。例えば、問題Ｍが道路ネットワークにおける経路選択である場合、状態ｓとしての道路ネットワークにおける行動主体（例えば車両）の位置と，行動ａとしての行動主体の進行方向との複数の組み合わせについての評価値Ｑ（ｓ，ａ）を学習する。
【０００６】
しかし、強化学習は、問題Ｍが変化しないことが前提となっており、学習する問題Ｍと学習結果は一対一で対応している。したがって、仮に、問題Ｍが、問題Ｍと一部が異なる問題Ｍ’に変化した場合（上述の道路ネットワークの例では、例えば工事や渋滞などによる局所的な変化が発生した場合）、状態ｓと行動ａとの複数の組み合わせに関する評価値Ｑ（ｓ，ａ）を学習し直す必要がある。
【０００７】
本発明の目的は、問題に関して状態と行動との複数の組み合わせについての評価値が算出された後に当該問題が変化した場合に、状態と行動との複数の組み合わせについての評価値の再学習処理をより効率的に行うことにある。
【課題を解決するための手段】
【０００８】
本発明は、報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習する強化学習装置であって、前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別部と、前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定部と、前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習部と、を備えることを特徴とする強化学習装置である。
【０００９】
望ましくは、前記強化学習装置は、道路ネットワークが格子で表現された格子世界において、前記行動主体としての車両が目的地に到達することで報酬が得られる問題に関して、前記状態としての前記格子世界における車両の現在位置と、前記行動としての前記車両の前記格子世界におけるいずれかの方向への移動との組み合わせについての前記評価値を学習するものであり、前記状態集合識別部は、前記格子世界が変化した場合に、前記格子世界の変化前と変化後との間において、前記目的地までの最短距離が変化しなかった状態の集合を前記学習不要状態集合と識別し、前記目的地までの最短距離が変化した状態の集合を前記再学習状態集合と識別する、ことを特徴とする。
【００１０】
望ましくは、前記格子世界において、格子のマス目間に移動コストが定義されており、前記強化学習装置は、前記移動コストをさらに考慮して前記評価値を学習する、ことを特徴とする。
【００１１】
望ましくは、前記道路ネットワークを示す道路情報に基づいて、前記格子世界を生成する格子世界生成部と、をさらに備えることを特徴とする。
【００１２】
また、本発明は、報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習するコンピュータを、前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別部と、前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定部と、前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習部と、として機能させることを特徴とする強化学習プログラムである。
【００１３】
また、本発明は、報酬が存在する問題に関して、前記問題において取り得る状態と、各状態において行動主体が取り得る行動との複数の組み合わせについての評価値を学習する強化学習方法であって、前記問題が変化した場合に、変化後の問題において取り得る複数の状態を、変化前の前記問題に関して学習済みの前記評価値を利用可能な状態の集合である学習不要状態集合と、前記変化後の問題に関して前記評価値の再学習が必要となった状態の集合である再学習状態集合とに識別する状態集合識別ステップと、前記再学習状態集合と前記学習不要状態集合との境界状態を定義した上で、前記再学習状態集合に含まれる各状態について、前記境界状態へ到達するまでの行動回数が少ない状態程大きい重みを設定する重み設定ステップと、前記再学習状態集合に含まれる各状態における前記評価値の再学習を行う再学習部であって、前記重みが大きい状態程、より多く前記再学習の初期状態として選択する再学習ステップと、を備えることを特徴とする強化学習方法である。
【発明の効果】
【００１４】
本発明によれば、問題に関して状態と行動との複数の組み合わせについての評価値が算出された後に当該問題が変化した場合に、状態と行動との複数の組み合わせについての評価値の再学習処理をより効率的に行うことができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係る強化学習装置の構成概略図である。
【図２】格子世界が生成される様子を示す図である。
【図３】十分に学習された学習器によって出力される現在位置から目的地までの最短経路を示す図である。
【図４】問題Ｍから問題Ｍ’に変化した様子を示す図である。
【図５】変化前の問題Ｍ及び変化後の問題Ｍ’における、各状態から目的地までの最短距離を示す図である。
【図６】再学習状態集合と学習不要状態集合を示す図である。
【図７】重み設定アルゴリズムを示す図である。
【図８】再学習状態集合に含まれる各状態の重みを示すヒートマップが生成される様子を示す第１の図である。
【図９】再学習状態集合に含まれる各状態の重みを示すヒートマップが生成される様子を示す第２の図である。
【図１０】再学習状態集合に含まれる各状態の重みを示すヒートマップが生成される様子を示す第３の図である。
【図１１】本実施形態に係る強化学習装置の処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について説明する。
【００１７】
図１には、本実施形態に係る強化学習装置１０の構成概略図が示されている。強化学習装置１０としては、以下に説明する機能を発揮可能な限りにおいてどのようなコンピュータであってもよい。例えば、強化学習装置１０は、一般的なコンピュータであってよく、あるいはサーバコンピュータであってもよい。
【００１８】
詳細は後述するが、強化学習装置１０は、報酬が存在する問題Ｍに関して、当該問題Ｍにおいて取り得る状態ｓと、各状態ｓにおいて行動主体が取り得る行動ａとの複数の組み合わせについての評価値Ｑ（ｓ，ａ）を学習する。その上で、強化学習装置１０は、十分に学習された評価値Ｑ（ｓ，ａ）に基づいて、行動主体の現在の状態から目的状態までの最適状態遷移経路を出力する。
【００１９】
本明細書においては、行動主体が車両であり、目的状態が車両の目的地であり、状態ｓが道路ネットワークにおける車両の現在位置であって、行動ａが現在位置からの車両のいずれかの方向への移動であり、問題Ｍが、車両を現在位置から目的位置へ向かわせる問題であって、車両が目的地に到着したときに報酬が得られる問題である例について本実施形態を説明する。
【００２０】
通信部１２は、例えばネットワークアダプタなどを含んで構成される。通信部１２は、ＬＡＮ（Local Area Network）やインターネットなどの通信回線を介して他の装置と通信する機能を発揮する。強化学習装置１０がサーバコンピュータである場合には、通信部１２は、強化学習装置１０における処理結果を示す結果情報を他の装置に送信する。また、通信部１２は、強化学習装置１０の利用者（ユーザ）からの指示を示す指示情報をユーザ端末から受信する。
【００２１】
記憶部１４は、例えばハードディスク、ＲＯＭ（Read Only Memory）、あるいはＲＡＭ（Random Access Memory）などを含んで構成される。記憶部１４には、強化学習装置１０の各部を機能させるための強化学習プログラムが記憶される。
【００２２】
また、図１に示すように、記憶部１４には、強化学習に用いられる学習器１６が記憶される。学習器１６の実体は、強化学習に関する各情報（状態ｓ及び各状態ｓにおいて行動主体が取り得る行動ａを含む問題Ｍに関する情報、並びに、状態ｓと行動ａとの複数の組み合わせに関する評価値Ｑ（ｓ，ａ）、評価値Ｑ（ｓ，ａ）の算出に用いる各種パラメータなど）、及び、入力データに対して処理を行うための処理実行プログラムである。したがって、記憶部１４に学習器１６が格納されるとは、上記各情報及び処理実行プログラムが記憶部１４に格納されることを意味する。
【００２３】
さらに、記憶部１４には、格子世界１８が記憶される。格子世界１８とは、現実の道路ネットワークが２次元の格子で表現されたものである。格子世界１８の詳細については後述する。
【００２４】
制御部２０は、例えばＣＰＵ（Central Processing Unit）などを含んで構成される。制御部２０は、記憶部１４に記憶された強化学習プログラムに従って、強化学習装置１０の各部を制御する。図１に示される通り、制御部２０は、格子世界生成部２２、学習部２４、外乱情報取得部２６、状態集合識別部２８、及び、重み設定部３０としても機能する。
【００２５】
本実施形態に係る強化学習装置１０の構成概要は以上の通りである。強化学習装置１０は、上述の構成要素の他、例えば液晶表示部を含んで構成され、強化学習装置１０の処理結果を表示するための表示部、例えばマウス、キーボード、あるいはタッチパネルなどから構成され、ユーザの指示を入力するための入力部などを含んでいてもよい。
【００２６】
以下、制御部２０が発揮する各機能の詳細と共に、強化学習装置１０における処理の詳細について説明する。
【００２７】
格子世界生成部２２は、現実の道路ネットワークを示す道路情報に基づいて格子世界１８を生成する。道路情報は、通信部１２を介して他の装置から取得することができる。図２に、格子世界１８が生成される様子が示されている。
【００２８】
図２（ａ）は道路ネットワークの一例を示す図であり、図２（ｂ）は図２（ａ）に示される道路ネットワークの一部拡大図である。図２（ｂ）に示される通り、道路情報は、複数の頂点４０（例えば交差点）と、各頂点間を結ぶリンク４２（例えば道路）を含む情報である。図２（ｂ）において、頂点４０ａに隣接する頂点４０ｂ、すなわち、頂点４０ａから１つのリンク４２を通って到達できる頂点４０ｂが斜線で示されている。
【００２９】
格子世界生成部２２は、図２（ａ）及び（ｂ）に示す情報を有する道路情報に基づいて、複数の頂点４０をＸ方向及びＹ方向の２次元方向に並べて格子世界１８を生成する。図２（ｃ）に格子世界１８の一部が示されている。格子世界１８においては、１つのマス目５０が道路ネットワークの１つの頂点４０に対応したものとなっており、道路ネットワークにおいて隣接する２つの頂点４０に対応する２つのマス目５０が隣接して配置される。例えば、図２（ｃ）に示されたマス目５０ａは図２（ｂ）における頂点４０ａに対応し、マス目５０ａに隣接するマス目５０ｂは、頂点４０ｂに対応したものとなっている。
【００３０】
また、本明細書における格子世界１８においては、車両が進入可能な進入可能マス目５２が白で示され、車両が侵入不可能な進入不可マス目５４が着色して示されている。
【００３１】
学習部２４は、学習器１６を学習させる処理を実行する。具体的には、格子世界１８において、車両を現在位置から目的位置へ向かわせる問題であって、車両が目的地に到着したときに報酬が得られる問題である問題Ｍに関して、状態ｓと行動ａとの複数の組み合わせそれぞれについての評価値Ｑ（ｓ，ａ）（以下、単に評価値Ｑ（ｓ，ａ）と記載する）を学習する。このように、学習部２４は、強化学習、特にＱ学習を実行する。
【００３２】
本実施形態では、学習部２４は、以下の式１に基づいて評価値Ｑ（ｓ，ａ）を算出する。
【数１】
2019175058.tif 000003
【００３３】
式１において、ｔは現時刻を表し、ｔ＋１は次時刻（車両が１回行動した後の時刻）を表す。本実施形態では、ｓｔは格子世界１８における車両の現在位置を示し、次状態ｓｔ＋１は、状態ｓｔから行動ａｔによって車両が格子世界１８のマス目５０を１つ移動した後の、格子世界１８における車両の位置を示す。また、式１において、αは学習率であり、０＜α≦１の値が設定される。一般的に学習率αは０．１程度の値が設定される。γは割引率であり、同じく０＜γ≦１の値が設定される。一般的に、割引率γは１に近い値が設定される。
【００３４】
ｒｔ+１は、状態ｓｔから行動ａｔを行ったときに得られる即時報酬である。なお、即時報酬とは、行動主体（本実施形態では車両）が目的状態（本実施形態では目的地）に達したときに得られる報酬とは区別される概念である。本実施形態では、格子世界１８のマス目間に移動コストが定義されている。移動コストは、格子世界１８の各マス目５０に対応する頂点４０を移動するために必要なコストであり、例えば道路の長さなどに応じた値である。本実施形態では、ｒｔ＋１は移動コストに応じて設定される。具体的には、移動コストが低いほど即時報酬ｒｔ＋１が大きくなるように設定される。このようにすることで、学習部２４は、移動コストを考慮して学習を行うことができる。
【００３５】
式１のうち、
【数２】
2019175058.tif 000004
は、次状態ｓｔ＋１と、次状態ｓｔ＋１において車両が取り得る全ての行動ａ（本例では次状態ｓｔ＋１において車両が進み得る全ての方向それぞれへの移動）それぞれとの複数の組み合わせについての複数の評価値Ｑ（ｓｔ＋１，ａ）のうち、現在の学習状態において、最も大きい値を示す評価値Ｑ（ｓｔ＋１，ａ）（以下「次状態最大評価値」と記載する）を意味する。
【００３６】
したがって、式１は、即時報酬ｒｔ＋１と、次状態最大評価値に割引率γを乗じた値との和よりも、現在状態ｓｔで車両が取った行動ａｔの評価値Ｑ（ｓｔ，ａｔ）が小さければ、学習率αに応じて評価値Ｑ（ｓｔ，ａｔ）を大きくし、即時報酬ｒｔ＋１と、次状態最大評価値に割引率γを乗じた値との和よりも、現在状態ｓｔで車両が取った行動ａｔの評価値Ｑ（ｓｔ，ａｔ）が大きければ、学習率αに応じて評価値Ｑ（ｓｔ，ａｔ）を小さくする処理を意味する。
【００３７】
評価値Ｑ（ｓｔ，ａｔ）が十分に学習されると、式１において学習率αに係る項がほぼ０となり、すなわち評価値Ｑ（ｓｔ，ａｔ）の値にほぼ変化が無くなる。
【００３８】
式１が示す通り、本実施形態では、学習部２４は、現状態ｓｔと次状態ｓｔ＋１とに基づいて、評価値Ｑ（ｓｔ，ａｔ）を算出する。したがって、学習部２４は、まず、各状態ｓと各行動ａとの複数の組み合わせについての初期評価値を予め設定し、任意の初期状態ｓ０（本例では格子世界１８における任意の初期マス目５０）から上述の学習を開始する。
【００３９】
十分に学習された学習器１６に車両の現在位置と目的地を入力すると、学習器１６は、格子世界１８において、車両の現在位置から目的地までの経路を出力できるようになる。特に、移動コストに応じた即時報酬ｒｔ＋１を考慮して学習するので、学習器１６は、車両の現在位置から目的までの移動コストが最小となる経路、つまり最短経路を出力できるようになる。図３には、十分に学習された学習器１６によって出力された、格子世界１８における車両の現在位置「Ｓ」から目的地「Ｇ」までの最短経路５６が示されている。
【００４０】
外乱情報取得部２６は、学習部２４が評価値Ｑ（ｓ，ａ）を学習した問題Ｍを変化させる外乱に関する外乱情報を取得する。本明細書では、外乱により変化した問題を問題Ｍ’と記載する。本実施形態では、上述の通り、問題Ｍは、車両を現在位置から目的位置へ向かわせる問題であるから、外乱の一例としては、道路ネットワークの状況を変化させる要因である。例えば、工事や渋滞などにより特定の道路が通行できなくなることが外乱となる。
【００４１】
外乱情報取得部２６は、例えば、路上に設置されたカメラの映像、車両に搭載されたカメラの映像、交通システムからの情報、あるいは道路状況を管理する機関が発信する道路状況データを受信することなどによって外乱情報を取得する。以下、外乱として、図４に示すように、格子世界１８のＸ＝４、Ｙ＝２のマス目５０ｃで工事が発生し、車両が当該マス目５０ｃを通行できなくなった例について説明する。
【００４２】
学習部２４が学習した評価値Ｑ（ｓ，ａ）は、問題Ｍが前提となっているものである。本実施形態では、格子世界１８が図３に示す状態であることが前提となっている。したがって、外乱によって問題Ｍが問題Ｍ’（本実施形態では図４に示す格子世界１８の状態）に変化すると、問題Ｍを前提として学習した評価値Ｑ（ｓ，ａ）の少なくとも一部が適切でないものとなる。すなわち、評価値Ｑ（ｓ，ａ）の再学習が必要となる。以下、強化学習装置１０における問題Ｍから問題Ｍ’に変化したときの評価値Ｑ（ｓ，ａ）の再学習処理について説明する。
【００４３】
状態集合識別部２８は、学習部２４が評価値Ｑ（ｓ，ａ）を学習した問題Ｍが問題Ｍ’に変化した場合に、問題Ｍ’において取り得る複数の状態を、変化前の問題Ｍに関して学習済みの評価値Ｑ（ｓ，ａ）を利用可能な状態の集合である学習不要状態集合と、変化後の問題Ｍ’に関して評価値Ｑ（ｓ，ａ）の再学習が必要となった状態の集合である再学習状態集合とに識別する。
【００４４】
学習不要状態集合とは、変化前の問題Ｍに関して学習した評価値Ｑ（ｓ，ａ）が、変化後の問題Ｍ’においても、さらに学習する必要なく、そのまま十分学習済みの評価値Ｑ（ｓ，ａ）となる状態の集合であるといえる。一方、再学習状態集合とは、変化前の問題Ｍに関して学習した評価値Ｑ（ｓ，ａ）が、変化後の問題Ｍ’においては、十分学習された評価値Ｑ（ｓ，ａ）でなくなる状態の集合であるといえる。
【００４５】
本実施形態では、状態集合識別部２８は、変化前の問題Ｍと変化後の問題Ｍ’との間の、格子世界１８における目的地までの最短距離に基づいて、学習不要状態集合と再学習状態集合を識別する。具体的には、状態集合識別部２８は、変化前の問題Ｍと変化後の問題Ｍ’との間において、格子世界１８における目的地までの最短距離が変化しなかった状態の集合を学習不要状態集合と識別し、目的地までの最短距離が変化した状態の集合を再学習状態集合と識別する。
【００４６】
図５（ａ）には、変化前の問題Ｍの格子世界１８における各マス目５０の目的地「Ｇ」までの最短距離が示され、図５（ｂ）には、変化後の問題Ｍ’の格子世界１８’における各マス目５０の目的地「Ｇ」までの最短距離が示されている。図５（ａ）と図５（ｂ）を比較してわかるように、変化前の問題Ｍの格子世界１８と、変化後の問題Ｍ’の格子世界１８’との間において、一部のマス目５０（状態には車両の現在位置が含まれるから、一部の状態と言い換えることができる）は目的地「Ｇ」までの最短距離が変わらないが、その他のマス目５０は目的地「Ｇ」までの最短距離が変わっている。
【００４７】
図６には、格子世界１８と格子世界１８’との間において、目的地「Ｇ」までの最短距離が変わらない学習不要状態集合６０が斜線で示され、目的地「Ｇ」までの最短距離が変わった再学習状態集合６２が太枠線で示されている。
【００４８】
重み設定部３０は、状態集合識別部２８が識別した再学習状態集合６２に含まれる各状態について、再学習処理のための重みを設定する。
【００４９】
まず、重み設定部３０は、変化後の問題Ｍ’において境界状態（以下「フロンティア」と記載する）を定義する。フロンティアとは、再学習状態集合６２に含まれる状態であって、学習不要状態集合６０と再学習状態集合６２との境界に位置する状態である。図６の例では、目的地「Ｇ」までの最短距離が「１０」であるマス目５０ｄがフロンティアとなる。
【００５０】
重み設定部３０は、フロンティアを定義した後、図７に示す重み設定アルゴリズムに従って、再学習状態集合６２に含まれる各状態の重みを設定する。以下、図８〜１０を参照しながら、重み設定アルゴリズムを説明する。なお、重み設定アルゴリズムの前提として、格子世界１８は、ｎ×ｍサイズであるとする。
【００５１】
重み設定アルゴリズムの１行目に示されるＷ（ｉ，ｊ）は、格子世界１８におけるＸ＝ｉ、Ｙ＝ｊの状態（マス目５０）の重みを意味している。したがって、１行目に示される処理は、格子世界１８の全ての状態の重みを０に初期化する処理である。
【００５２】
２行目に示されるＦは、重み設定処理の対象となる対象状態集合を意味している。また、Ｆ０はフロンティアを意味している。したがって、２行目に示される処理は、対象状態集合ＦをフロンティアＦ０とする処理である。
【００５３】
以下、３行目から８行目までの処理がｈ回繰り返される。ここで、ｈはホップ数であり、後述の対象状態集合Ｆの拡張処理を行う回数である。ホップ数ｈは予め設定されている。
【００５４】
４行目及び５行目に示される処理は、対象状態集合Ｆに含まれる全ての状態の重みそれぞれに対して、加算値ρを加える処理である。ｋ＝１の状態においては、対象状態集合ＦにはフロンティアＦ０のみが含まれているため、この時点では、格子世界１８に含まれる状態のうち、フロンティアＦ０のみ重みρを有している状態となる。
【００５５】
本実施形態においては、加算値ρは１に設定されているが、加算値ρとしてはその他の値であってもよい。例えば、フロンティアＦ０からより離れた（フロンティアＦ０に到達するための行動回数がより多い）状態に対する加算値ρを、フロンティアＦ０により近い（フロンティアＦ０に到達するための行動回数がより少ない）状態に対する加算値ρよりも小さくするようにしてもよい。例えば、加算値ρは以下の式２で与えられてもよい。
【数３】
2019175058.tif 000005
式２において、ｎは、加算値ρが加算される状態のフロンティアＦ０からの距離（行動回数）である。
【００５６】
図８（ａ）に、ｋ＝１における５行目までの処理が終了した時点の格子世界１８における対象状態集合Ｆが示され、図８（ｂ）に、ｋ＝１における５行目までの処理が終了した時点の格子世界１８の各状態の重みを示すヒートマップ７０が示されている。図８（ａ）においては、対象状態集合Ｆは、格子世界１８上の黒いマス目によって表されている。上述の通り、ｋ＝１の時点では、フロンティアＦ０であるマス目５０ｄのみが対象状態集合Ｆに含まれている。また、図８（ｂ）のヒートマップ７０が示す通り、マス目５０ｄに対応するヒートマップ７０のマス目７２ａの重みが「１」となっている。
【００５７】
重み設定アルゴリズムの７行目に示されるＨ（Ｆ）という関数は、対象状態集合Ｆと、対象状態集合Ｆに隣接する（１回の行動で遷移可能な）状態とを含む状態集合を出力する関数である。ここで、対象状態集合Ｆに隣接する状態とは、対象状態集合Ｆに含まれるいずれかの状態に隣接する状態のうち、未だ対象状態集合Ｆに含まれていない状態を意味する。７行目の処理によって、対象状態集合ＦがＨ（Ｆ）に更新される。つまり、対象状態集合Ｆが隣接する状態を含むように拡張される。
【００５８】
図９（ａ）に、ｋ＝１における７行目の処理が終了した時点の格子世界１８における対象状態集合Ｆが示されている。７行目の処理により、対象状態集合Ｆが、フロンティアＦ０であるマス目５０ｄに加え、マス目５０ｄに隣接する２つのマス目５０ｅを含むものとなっている。なお、車両が移動できないマス目５４は対象状態集合Ｆに含められない。
【００５９】
ｋ＝２における４行目及び５行目の処理によって、拡張された対象状態集合Ｆに含まれる全ての状態の重みそれぞれに対して加算値ρが加えられる。これにより、図９（ｂ）に示すように、ヒートマップ７０において、フロンティアＦ０であるマス目５０ｄに対応するマス目７２ａの重みが「２」となり、新たに対象状態集合Ｆに追加された格子世界１８の２つのマス目５０ｅに対応する２つのマス目７２ｂの重みが「１」となる。なお、図９（ｂ）に示すヒートマップ７０においては、再学習状態集合６２に対応するマス目（太枠線）以外のマス目、つまり学習不要状態集合６０に対応するマス目にまで重みが設定されているが、再学習状態集合６２に対応するマス目のみに重みを設定するようにしてもよい。
【００６０】
ｋ＝２における７行目の処理により、再度、対象状態集合Ｆが拡張される。図１０（ａ）に、２つのマス目５０ｅに隣接する３つのマス目５０ｆが対象状態集合Ｆに加えられた対象状態集合Ｆが示されている。
【００６１】
そして、ｋ＝３における４行目及び５行目の処理によって、再度拡張された対象状態集合Ｆに含まれる全ての状態の重みそれぞれに対して加算値ρが加えられる。これにより、図１０（ｂ）に示すように、ヒートマップ７０において、フロンティアＦ０であるマス目５０ｄに対応するマス目７２ａの重みが「３」となり、マス目ｄに隣接する格子世界１８の２つのマス目５０ｅに対応する２つのマス目７２ｂの重みが「２」となり、新たに対象状態集合Ｆに追加された格子世界１８の３つのマス目５０ｆに対応する３つのマス目７２ｃの重みが「１」となる。
【００６２】
以後、変数ｋが予め設定されたホップ数ｈに達するまで、４行目から７行目までの処理を繰り返す。そのようにして得られたＷ（ｘ，ｙ）が格子世界１８に含まれる各状態についての重みであり、再学習状態集合６２に含まれる各状態についての重みを含むものである。
【００６３】
重み設定アルゴリズムにより、フロンティアまでの距離が小さい状態程、すなわち、フロンティアへ到達するまでの行動回数が少ない状態程、大きい重みが設定される。
【００６４】
再学習部としての学習部２４は、重み設定部３０が設定した再学習状態集合６２に含まれる各状態の重みに基づいて、再学習状態集合６２に含まれる各状態に関する評価値Ｑ（ｓ，ａ）の再学習を行う。具体的には、学習部２４は、再学習状態集合６２に含まれる状態のうち、重みが大きい状態程、より多く再学習の初期状態として選択した上で、再学習を行う。
【００６５】
学習部２４は、上述の式１により評価値Ｑ（ｓ，ａ）を学習する。上述の通り、式１は、行動ａｔにより遷移する次状態ｓｔ＋１における行動ａの最大評価値に基づいて、現状態ｓｔと行動ａとの組み合わせについての評価値Ｑ（ｓｔ，ａｔ）を学習する。つまり、次状態ｓｔ＋１と行動ａとの組み合わせの評価値Ｑ（ｓｔ＋１，ａ）がより適切である（より学習されている）方が、評価値Ｑ（ｓｔ，ａｔ）を効率よく学習できるといえる。
【００６６】
ここで、図６を参照すると、例えばフロンティアであるマス目（状態）５０ｄを初期状態とすれば、次状態として、学習不要状態集合６０に含まれるマス目５０ｇを取り得る。次状態であるマス目５０ｇに関する評価値Ｑ（ｓ，ａ）は、変化前の問題Ｍに関する学習により十分学習されているから、初期状態をマス目５０ｄとすれば、比較的効率よく再学習ができるといえる。
【００６７】
一方、再学習状態集合６２に含まれる状態であって、フロンティアから離れた状態（例えばマス目５０ｈ）を初期状態とした場合、次状態としては、マス目５０ｈに隣接する２つのマス目５０ｉを取り得る。しかしながら、２つのマス目５０ｉは、再学習状態集合６２に含まれているわけだから、次状態としての２つのマス目５０ｉに関する評価値Ｑ（ｓ，ａ）は、十分に学習されていないことになる。つまり、初期状態をフロンティアから離れた状態とすると、再学習の効率が比較的下がることになる。
【００６８】
したがって、学習部２４は、再学習状態集合６２に含まれる状態のうち、重みが大きい状態程、より多く初期状態として選択して再学習を行うことで、再学習をより効率良く行うことができる。本実施形態では、工事や渋滞などの外乱により特定の道路が通行できなくなった場合に、通行不可能な道路を迂回した目的地への経路が効率よく学習される。
【００６９】
以下、図１１に示すフローチャートに従って、強化学習装置１０の処理の流れを説明する。
【００７０】
ステップＳ１０において、格子世界生成部２２は、取得した道路情報に基づいて格子世界１８を生成する。
【００７１】
ステップＳ１２において、学習部２４は、格子世界１８において車両を現在位置から目的位置へ向かわせる問題Ｍに関して、評価値Ｑ（ｓ，ａ）を学習する。ステップＳ１２では、問題Ｍに関して評価値Ｑ（ｓ，ａ）が十分に学習される。
【００７２】
ステップＳ１４において、外乱情報取得部２６は、問題Ｍを変化させる外乱（本例では道路ネットワークの状況の変化）に関する外乱情報を取得したか否かを判定する。外乱情報を取得した場合はステップＳ１６に進み、外乱情報を取得しない場合は処理を終了する。
【００７３】
ステップＳ１６において、状態集合識別部２８は、外乱による変化後の問題Ｍ’において取り得る複数の状態を、学習不要状態集合６０と再学習状態集合６２に識別する。ステップＳ１６が状態集合識別ステップに相当する。
【００７４】
ステップＳ１８において、重み設定部３０は、ステップＳ１６で識別された再学習状態集合６２に含まれる各状態に重みを設定する。重み設定部３０は、学習不要状態集合６０と再学習状態集合６２の境界状態であるフロンティアへ到達するまでの行動回数が少ない状態程大きい重みを設定する。ステップＳ１８が重み設定ステップに相当する。
【００７５】
ステップＳ２０において、学習部２４は、ステップＳ１８で設定された重みに従って、再学習状態集合６２に含まれる各状態についての評価値Ｑ（ｓ，ａ）を再学習する。学習部２４は、重みが大きい状態程、より多く初期状態として選択した上で再学習を行う。ステップＳ２０が再学習ステップに相当する。
【００７６】
以上、本発明に係る実施形態を説明したが、本発明は上記実施形態に限られるものではなく、本発明の趣旨を逸脱しない限りにおいて種々の変更が可能である。
【００７７】
例えば、上記実施形態では、問題Ｍが車両を現在位置から目的位置へ向かわせる問題であったが、本発明はその他の問題Ｍについて強化学習を行う場合においても好適に適用することができる。
【符号の説明】
【００７８】
１０  強化学習装置、１２  通信部、１４  記憶部、１６  学習器、１８  格子世界、２０  制御部、２２  格子世界生成部、２４  学習部、２６  外乱情報取得部、２８  状態集合識別部、３０  重み設定部。
【図１】
2019175058.tif 000006
【図２】
2019175058.tif 000007
【図３】
2019175058.tif 000008
【図４】
2019175058.tif 000009
【図５】
2019175058.tif 000010
【図６】
2019175058.tif 000011
【図７】
2019175058.tif 000012
【図８】
2019175058.tif 000013
【図９】
2019175058.tif 000014
【図１０】
2019175058.tif 000015
【図１１】
2019175058.tif 000016