JP7707846B2 - 経路計画システム、経路計画方法、ロードマップ構築装置、モデル生成装置、及びモデル生成方法 - Google Patents

Description

本発明は、経路計画システム、経路計画方法、ロードマップ構築装置、モデル生成装置、及びモデル生成方法に関する。

複数のエージェントそれぞれが目的地に移動する経路を計画するマルチエージェントの経路計画問題が存在する。エージェントは、例えば、自律的に移動する移動体（例えば、搬送ロボット、清掃ロボット、自動運転車両、ドローン等）、人、人の操作する装置、マニピュレータ等である。従来、マルチエージェントの経路計画問題は、予め定められたグリッドマップ（グリッド空間）上で解かれていた。例えば、非特許文献１では、機械学習により訓練されたモデルを用いて、グリッドマップ上で各エージェントの経路計画を行う方法が提案されている。

このグリッドマップを用いる方法によれば、各エージェントの移動可能な位置が予め規定されるため、比較的に簡単に各エージェントの経路を見つけることができる。しかしながら、予め定められたグリッドにより各エージェントの移動が制限されてしまう。そのため、各エージェントについてより良い経路（例えば、実空間での最短経路）を得るには限界がある。

そこで、予め定められたグリッド空間ではなく、各エージェントが自由な位置に移動可能な連続空間上で、マルチエージェントの経路計画問題を解く方法が検討されている。連続空間上で経路計画問題を解く場合、ロードマップを構築し、構築されたロードマップ上で各エージェントの経路を探索するアプローチがしばしば採用される（例えば、非特許文献２）。

ロードマップは、ノード及びエッジにより構成され、各エージェントの経路を探索する範囲を特定する。ノードは、移動可能な位置を示し、エッジは、ノード同士を連結し、連結されるノード間が移動可能であることを示す。このロードマップを構築する際に、経路を探索する対象の連続空間に応じて任意の位置にノードを配置可能である。そのため、移動可能な位置が予め固定されるグリッドマップを用いる方法に比べて、この連続空間上で経路を探索する方法は、各エージェントについてより良い経路を得られる可能性がある。

Mehul Damani, Zhiyao Luo, Emerson Wenzel, Guillaume Sartoretti, "PRIMAL2 Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong", IEEE Robotics and Automation Letters, Volume 6, Issue 2, p.2666-2673, 2021 Felipe Felix Arias, Brian Andrew Ichter, Aleksandra Faust, Nancy M. Amato, "Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments", IEEE International Conference on Robotics and Automation, 2021

本件発明者らは、マルチエージェントの経路計画問題を連続空間上で解く上記従来の方法には、次のような問題点があることを見出した。すなわち、従来の方法では、連続空間全体にノードを配置することで、各エージェントに共通のロードマップが構築される。一例では、ノードは、連続空間全体にランダムに配置される。他の一例として、非特許文献２で提案される方法では、機械学習により訓練されたモデルを使用することで、障害物付近において他のエージェントを回避可能な位置にノードを配置する。いずれの方法でも、基本的には、ノードは、連続空間全体に配置される。

この際に、連続空間上にノードを密に配置することで、各エージェントに採用可能な経路の組み合わせが増える。そのため、そのロードマップにより各エージェントのより最適な経路を発見できる可能性が高くなる。しかしながら、ノードを密に配置すると、それだけノード数が増えるため、経路の探索にかかるコスト（計算的コスト及び時間的コスト）が増大する。そこで、ノードを疎に配置すると、探索にかかるコストを低減することができるが、最適な経路を発見できる可能性が低くなる。最悪のケースでは、障害物又は他のエージェントを迂回可能な経路が発見できなくなる事態も生じ得る。したがって、従来の方法では、より最適な経路を発見すること及び探索のコストを低減することの両立が困難であるという問題点があった。

なお、この問題点が生じるのは、マルチエージェントの移動経路を探索する場面に限られるものではない。各ノードは、位置以外の他の状態（例えば、速度、向き等）を示すように構成されてよい。この場合に、連続状態空間において各エージェントのスタート状態からゴール状態までの遷移経路を探索する場面でも同様に上記問題点は生じ得る。

本発明は、一側面では、このような事情を鑑みてなされたものであり、その目的は、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図る技術を提供することである。

本発明は、上述した課題を解決するために、以下の構成を採用する。

すなわち、本発明の一側面に係る経路計画システムは、情報取得部、マップ構築部、及び探索部を備える。情報取得部は、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するように構成される。マップ構築部は、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するように構成される。探索部は、前記エージェント毎に構築された前記ロードマップ上で、前記スタート状態から前記ゴール状態までの前記各エージェントの経路を探索するように構成される。

ロードマップ構築モデルは、第１処理モジュール、第２処理モジュール、及び推定モジュールを備える。第１処理モジュールは、対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される。第２処理モジュールは、前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される。推定モジュールは、生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される。訓練済みの前記ロードマップ構築モデルは、複数の学習用エージェントの正解経路から得られた学習データを使用した機械学習により生成される。

前記エージェント毎に前記ロードマップを構築することは、前記複数のエージェントのうちのいずれかのエージェントを前記対象エージェントとして取り扱い、前記複数のエージェントのうちの残りのエージェントの少なくとも一部を前記他のエージェントとして取り扱い、取得された前記対象情報により示される前記いずれかのエージェントのスタート状態を前記対象エージェントの最初の対象タイムステップにおける候補状態として指定して、訓練済みの前記ロードマップ構築モデルにより次のタイムステップにおける１つ以上の候補状態を推定し、かつ推定される次のタイムステップにおける１つ以上の候補状態に前記いずれかのエージェントの前記ゴール状態又はその近傍状態が含まれるまで、推定された次のタイムステップにおける１つ以上の候補状態それぞれを新たな対象タイムステップにおける候補状態に指定して、訓練済みの前記ロードマップ構築モデルによる次のタイムステップの候補状態の推定を繰り返す、処理を前記複数のエージェントそれぞれを前記対象エージェントに個々に指定して実行することにより構成される。

候補状態は、ロードマップを構成するノードに対応する。すなわち、推定モジュールは、対象エージェントに対して、対象タイムステップの各特徴情報から連続状態空間上で次のタイムステップに遷移可能な１つ以上のノードの配置を推定するように構成される。対象タイムステップにおける候補状態と推定により得られる次のタイムステップにおける候補状態とはエッジにより連結される。エッジは、ある候補状態（ノード）から別の候補状態（ノード）へ遷移可能であることを示す。

当該構成では、訓練済みのロードマップ構築モデルを使用して、エージェント毎のロードマップが構築される。使用される訓練済みのロードマップ構築モデルは、複数の学習用エージェントの正解経路から得られた学習データを用いた機械学習により生成される。この機械学習によれば、ロードマップ構築モデルは、エージェントのスタートからゴールまでの適切な経路に即してロードマップを構築する能力を獲得することができる。したがって、当該構成によれば、各エージェントのスタート状態からゴール状態までの適切な経路（すなわち、探索したい経路）及びその周辺範囲にノードが配置されたロードマップをエージェント毎に構築することができる。つまり、当該構成によれば、正解経路を学習した訓練済みのロードマップ構築モデルを使用することで、エージェント毎に適したロードマップを得ることができる。これに対して、上記従来の方法では、連続状態空間全体にノードを配置することで全エージェントに共通のロードマップを構築する。この従来の方法と比べて、当該構成により得られるロードマップでは、ノードを配置する範囲を各エージェントの適切な範囲に絞ることができる。つまり、各エージェントの探索経路にとって無駄な位置へのノードの配置を省くことができる。そのため、ロードマップ上にノードを密に配置しても、ノード数の増加を抑えることができる。よって、当該構成によれば、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

上記一側面に係る経路計画システムにおいて、前記ロードマップ構築モデルは、障害物に関する情報を含む環境情報から第３特徴情報を生成するように構成される第３処理モジュールを更に備えてよい。前記推定モジュールは、生成される前記第１特徴情報、前記第２特徴情報及び前記第３特徴情報から、前記次のタイムステップにおける１つ以上の候補状態を推定するように構成されてよい。取得される前記対象情報は、前記連続状態空間に存在する前記障害物に関する情報を更に含むように構成されてよい。訓練済みの前記ロードマップ構築モデルを使用することは、取得される前記対象情報に含まれる前記情報から前記環境情報を構成し、構成された前記環境情報を前記第３処理モジュールに与えることを含んでよい。当該構成では、障害物を含む環境の状況を考慮して、各エージェントのロードマップを構成するノードの配置を推定することができる。そのため、障害物の存在する環境下でも、各エージェントに対して適したロードマップを構築することができる。よって、当該構成によれば、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

上記一側面に係る経路計画システムにおいて、前記対象エージェント情報は、前記対象タイムステップよりも前のタイムステップにおける前記対象エージェントの候補状態を更に含むように構成されてよい。前記他エージェント情報は、前記対象タイムステップよりも前のタイムステップにおける前記他のエージェントの候補状態を更に含むように構成されてよい。当該構成では、各エージェントの状態遷移を時系列に考慮しながら、各エージェントのロードマップを構成するノードの配置を推定することができる。そのため、複数のタイムステップを経てスタートからゴールに到達するエージェントに対して適したロードマップを構築することができる。よって、当該構成によれば、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

上記一側面に係る経路計画システムにおいて、前記対象エージェント情報は、前記対象エージェントの属性を更に含むように構成されてよい。

従来の方法では、各エージェントに共通のロードマップを経路探索に使用するため、各エージェントの個体差を考慮する（すなわち、属性の異なるエージェントを取り扱う）ことが困難であった。一例として、細い通路が存在する連続空間上で、移動体である各エージェントの移動経路を探索する場面を想定する。この場面において、各エージェントのサイズが異なってもよい場合、一部のエージェントは当該通路を通過することができるが、残りのエージェントは当該通路を通過できないケースが生じ得る。当該ケースにおいて、従来の方法では、ロードマップを構成するノードを当該通路に配置すると、当該通路を通過不能なエージェントに対して実際には移動できない経路を探索してしまう可能性がある。一方、ロードマップを構成するノードを当該通路に配置しないようにすると、当該通路を通過可能なエージェントに対して最適な経路を探索できなくなる可能性が高くなってしまう。このように、従来の方法では、属性の異なるエージェントを取り扱うことが困難であった。

これに対して、当該構成では、各エージェントの属性を考慮しながら、ロードマップを構成するノードの配置をエージェント毎に推定する。これにより、属性の異なるエージェントが存在する場合でも、適したロードマップをエージェント毎に構築することができる。上記ケースでは、当該通路を通過可能なエージェントに対して（最適な経路上又はその周辺範囲に当該通路が存在する場合には）当該通路にノードを配置したロードマップを構築し、当該通路を通過不能なエージェントに対して当該通路にノードを配置していないロードマップを構築することができる。したがって、当該構成によれば、属性の異なるエージェントが混在する場合でも、連続状態空間上でのマルチエージェントの経路計画問題を適切に解くことができる。

上記一側面に係る経路計画システムにおいて、前記対象エージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。当該構成によれば、大きさ、形状、最大速度、及び重量の少なくともいずれかの異なるエージェントが混在する場合でも、連続状態空間上でのマルチエージェントの経路計画問題を適切に解くことができる。

上記一側面に係る経路計画システムにおいて、前記他エージェント情報は、前記他のエージェントの属性を更に含むように構成されてよい。当該構成では、他のエージェントの属性を考慮して、対象エージェントのロードマップを構成するノードの配置を推定することができる。そのため、様々な属性を備えるエージェントが存在する環境下でも、各エージェントに対して適したロードマップを構築することができる。よって、当該構成によれば、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

上記一側面に係る経路計画システムにおいて、前記他のエージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。当該構成によれば、大きさ、形状、最大速度、及び重量の少なくともいずれかが異なるエージェントが存在する環境下でも、各エージェントに対して適したロードマップを構築することができる。これにより、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

上記一側面に係る経路計画システムにおいて、前記対象エージェント情報は、前記連続状態空間において前記対象エージェントの遷移する方向を示す方向フラグを更に含むように構成されてよい。機械学習に使用した学習データを得た正解経路の遷移方向が偏っていた場合、訓練済みのロードマップ構築モデルは、各エージェントに対して偏った方向にのみノードを配置したロードマップを構築してしまう可能性がある。偏った方向にノードが配置されていると、状態遷移の選択幅が狭くなってしまうため、少なくともいずれかのエージェントに対して最適な経路を発見できなくなる可能性がある。これに対して、当該構成では、ロードマップ構築モデルに与える方向フラグにより、各エージェントのロードマップを構成するノードの配置方向を制御することができる。これによって、各エージェントのロードマップにおいて、偏った方向にノードが配置されることを抑制することができる。その結果、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めることができる。

上記一側面に係る経路計画システムにおいて、前記複数のエージェントそれぞれは、自律的に移動するように構成される移動体であってよい。当該構成によれば、複数の移動体の経路計画問題を解く場面で、各移動体に対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。なお、移動体は、機械制御により自律的に移動可能に構成された任意の装置であってよい。移動体は、例えば、移動ロボット、自動運転車両、ドローン等であってよい。

本発明の形態は、訓練済みのロードマップ構築モデルを使用して、エージェント毎のロードマップを構築し、各エージェントの経路を探索するように構成された経路計画システムに限られなくてよい。本発明の一側面は、上記いずれかの形態において各エージェントのロードマップを構築するように構成されたロードマップ構築装置、又は上記いずれかの形態において使用される訓練済みのロードマップ構築モデルを生成するように構成されたモデル生成装置であってもよい。

例えば、本発明の一側面に係るロードマップ構築装置は、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するように構成される情報取得部と、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するように構成されるマップ構築部と、を備える。当該構成によれば、正解経路を学習した訓練済みのロードマップ構築モデルを使用することで、エージェント毎に適したロードマップを得ることができる。これにより、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

例えば、本発明の一側面に係るモデル生成装置は、複数の学習用エージェントの正解経路から生成された学習データを取得するように構成されたデータ取得部と、取得された学習データを使用して、ロードマップ構築モデルの機械学習を実施するように構成される学習処理部と、を備える。前記学習データは、前記各学習用エージェントの前記正解経路におけるゴール状態及び複数のデータセットを含む。前記複数のデータセットそれぞれは、前記各学習用エージェントの第１タイムステップにおける状態及び第２タイムステップにおける状態の組み合わせにより構成される。前記第２タイムステップは、前記第１タイムステップの次のタイムステップである。前記ロードマップ構築モデルの機械学習は、前記複数の学習用エージェントのうちのいずれかの学習用エージェントを前記対象エージェントとして取り扱い、前記複数の学習用エージェントのうちの残りの学習用エージェントの少なくとも一部を前記他のエージェントとして取り扱い、及び前記各データセットについて、前記いずれかの学習用エージェントの前記第１タイムステップにおける状態を前記対象エージェントの前記対象タイムステップにおける候補状態として前記第１処理モジュールに与え、前記残りの学習用エージェントの少なくとも一部の前記第１タイムステップにおける状態を前記他のエージェントの前記対象タイムステップにおける候補状態として前記第２処理モジュールに与えることで、前記推定モジュールにより推定される前記対象エージェントの次のタイムステップにおける候補状態が、前記いずれかの学習用エージェントの前記第２タイムステップにおける状態に適合するように、前記ロードマップ構築モデルを訓練すること、により構成される。当該構成によれば、エージェント毎に適したロードマップを構築する能力を獲得した訓練済みのロードマップ構築モデルを生成することができる。この訓練済みのロードマップ構築モデルを使用することで、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

上記一側面に係るモデル生成装置において、前記対象エージェント情報は、前記連続状態空間において前記対象エージェントの遷移する方向を示す方向フラグを更に含むように構成されてよい。前記各データセットは、前記連続状態空間における前記第１タイムステップの状態から前記第２タイムステップの状態の方向を示す訓練フラグを更に含むように構成されてよい。前記ロードマップ構築モデルの機械学習は、前記各データセットについて、前記対象エージェントの次のタイムステップにおける候補状態を推定する際に、前記いずれかの学習用エージェントの前記訓練フラグを前記対象エージェントの方向フラグとして前記第１処理モジュールに与えることを含んでよい。

当該構成では、各データセットに含まれる訓練フラグに基づいて、機械学習に使用される各データセットの遷移方向を管理することができる。この訓練フラグにより、各方向の遷移を万遍なく訓練するように各データセットを機械学習に使用することで、ノードを配置する方向が偏り難い訓練済みのロードマップ構築モデルを生成することができる。また、対象エージェント情報に方向フラグの項目が含まれていることで、方向フラグによりノードを配置する方向を制御する能力を獲得した訓練済みのロードマップ構築モデルを生成することができる。この訓練済みのロードマップ構築モデルを使用することで、各エージェントのロードマップにおいてノードの配置される方向が偏らないようにし、これにより、状態遷移の選択幅が狭くならないようにすることができる。その結果、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めることができる。

上記各形態に係る経路計画システム、ロードマップ構築装置及びモデル生成装置の別の形態として、本発明の一側面は、以上の各構成の全部又はその一部を実現する情報処理方法であってもよいし、情報処理システムであってもよいし、プログラムであってもよいし、又はこのようなプログラムを記憶した、コンピュータその他装置、機械等が読み取り可能な記憶媒体であってもよい。ここで、コンピュータ等が読み取り可能な記憶媒体とは、プログラム等の情報を、電気的、磁気的、光学的、機械的、又は、化学的作用によって蓄積する媒体である。

例えば、本発明の一側面に係る経路計画方法は、コンピュータが、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するステップと、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するステップと、前記エージェント毎に構築された前記ロードマップ上で、前記スタート状態から前記ゴール状態までの前記各エージェントの経路を探索するステップと、を実行する情報処理方法である。

例えば、本発明の一側面に係る経路計画プログラムは、コンピュータに、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するステップと、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するステップと、前記エージェント毎に構築された前記ロードマップ上で、前記スタート状態から前記ゴール状態までの前記各エージェントの経路を探索するステップと、を実行させるためのプログラムである。

例えば、本発明の一側面に係るロードマップ構築方法は、コンピュータが、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するステップと、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するステップと、を実行する情報処理方法である。

例えば、本発明の一側面に係るロードマップ構築プログラムは、コンピュータに、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するステップと、訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するステップと、を実行させるためのプログラムである。

例えば、本発明の一側面に係るモデル生成方法は、コンピュータが、複数の学習用エージェントの正解経路から生成された学習データを取得するステップと、取得された学習データを使用して、ロードマップ構築モデルの機械学習を実施するステップと、を実行する情報処理方法である。

例えば、本発明の一側面に係るモデル生成プログラムは、コンピュータに、複数の学習用エージェントの正解経路から生成された学習データを取得するステップと、取得された学習データを使用して、ロードマップ構築モデルの機械学習を実施するステップと、を実行させるためのプログラムである。

本発明によれば、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

図１は、本発明が適用される場面の一例を模式的に示す。 図２Ａは、実施の形態に係るロードマップ構築モデルの構成の一例を模式的に示す。 図２Ｂは、実施の形態に係る第２処理モジュールの演算処理の一例を模式的に示す。 図３は、実施の形態に係るモデル生成装置のハードウェア構成の一例を模式的に示す。 図４は、実施の形態に係る経路計画システムのハードウェア構成の一例を模式的に示す。 図５は、実施の形態に係るモデル生成装置のソフトウェア構成の一例を模式的に示す。 図６は、実施の形態に係る学習データの獲得方法の一例を模式的に示す。 図７は、実施の形態に係るロードマップ構築モデルの機械学習方法の一例を模式的に示す。 図８は、実施の形態に係る経路計画システムのソフトウェア構成の一例を模式的に示す。 図９は、実施の形態に係る訓練済みのロードマップ構築モデルによりエージェント毎のロードマップを構築する過程の一例を模式的に示す。 図１０は、実施の形態に係るモデル生成装置の処理手順の一例を示すフローチャートである。 図１１は、実施の形態に係る経路計画システムの処理手順の一例を示すフローチャートである。 図１２は、実施の形態に係る訓練済みのロードマップ構築モデルにより構築されるエージェント毎のロードマップの一例を模式的に示す。 図１３は、実施の形態に係るエージェントの一例を模式的に示す。 図１４は、変形例に係る経路計画システムの構成の一例を模式的に示す。 図１５は、変形例に係るロードマップ構築モデルの機械学習方法の一例を模式的に示す。 図１６Ａは、実施例に係る手法によりあるエージェントに対して構築されたロードマップ及び経路探索の結果を示す。 図１６Ｂは、比較例に係る手法によりあるエージェントに対して構築されたロードマップ及び経路探索の結果を示す。 図１７は、実施例に係る手法により得られた各エージェントの経路計画結果を示す。

以下、本発明の一側面に係る実施の形態（以下、「本実施形態」とも表記する）を、図面に基づいて説明する。ただし、以下で説明する本実施形態は、あらゆる点において本発明の例示に過ぎない。本発明の範囲を逸脱することなく種々の改良及び変形を行うことができることは言うまでもない。つまり、本発明の実施にあたって、実施形態に応じた具体的構成が適宜採用されてもよい。なお、本実施形態において登場するデータを自然言語により説明しているが、より具体的には、コンピュータが認識可能な疑似言語、コマンド、パラメータ、マシン語等で指定される。

§１ 適用例
図１は、本発明を適用した場面の一例を模式的に示す。図１に示されるとおり、本実施形態に係る情報処理システムは、モデル生成装置１及び経路計画システム２を備える。

［モデル生成装置］
本実施形態に係るモデル生成装置１は、訓練済みのロードマップ構築モデル５を生成するように構成された少なくとも１台のコンピュータである。

モデル生成装置１は、複数の学習用エージェントの正解経路から生成された学習データ３を取得する。モデル生成装置１は、取得された学習データ３を使用して、ロードマップ構築モデル５の機械学習を実施する。

（ロードマップ構築モデル）
図２Ａは、本実施形態に係るロードマップ構築モデル５の構成の一例を模式的に例示する。本実施形態に係るロードマップ構築モデル５は、第１処理モジュール５１、第２処理モジュール５２、第３処理モジュール５３及び推定モジュール５５を備える。

第１処理モジュール５１は、対象エージェント情報４１から第１特徴情報を生成するように構成される。対象エージェント情報４１は、対象エージェントのロードマップの構築に有益な対象エージェントに関する情報を含む。対象エージェントは、複数のエージェントのうち、ロードマップ構築モデル５によりロードマップを構築する対象として着目するエージェントである。対象エージェント情報４１は、連続状態空間における対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含むように構成される。

第２処理モジュール５２は、他エージェント情報４３から第２特徴情報を生成するように構成される。他エージェント情報４３は、対象エージェントのロードマップの構築に有益な、対象エージェント以外の１つ以上の他のエージェントに関する情報を含む。他のエージェントは、複数のエージェントのうち、対象エージェントとして着目されているエージェント以外のエージェントである。他エージェント情報４３は、連続状態空間における１つ以上の他のエージェントのゴール状態及び対象タイムステップにおける候補状態を含むように構成される。

第３処理モジュール５３は、環境情報４５から第３特徴情報を生成するように構成される。環境情報４５は、障害物に関する情報を含むように構成される。障害物は、例えば、壁、荷物、動物（人間、人間以外の動物）、段差（階段）等のエージェントの状態遷移（例えば、移動）を妨げ得る物体である。障害物は、実際に存在する物体であってもよいし、仮想の物体であってもよい。障害物の数は、任意であってよい。障害物は、状態遷移し得る物体（例えば、移動し得る物体）であってもよいし、或いは状態遷移しない物体（例えば、停止した物体）であってもよい。障害物に関する情報は、例えば、障害物の有無、位置、大きさ、存在範囲、形状等の障害物の属性を示す情報を含んでよい。環境情報４５には、障害物に関する情報以外の他の情報であって、エージェントが状態遷移を行う環境に関する他の情報（例えば、エージェントの状態遷移に影響を及ぼし得る環境の状況、環境に設けられた規則等）が更に含まれてもよい。一例として、エージェントとして屋外（実空間）で移動する移動体を想定した場合、環境情報４５は、天候、路面状況等に関する情報を更に含んでよい。例えば、一般車両、自動運転車両等の道路を走行する移動体をエージェントとして想定した場合、環境情報４５は、混雑状況、交通規制、交通ルール（例えば、信号機の数、一方通行、追い越し禁止、法定の最高速度等）等に関する情報を更に含んでもよい。例えば、ドローン等の飛行する移動体をエージェントとして想定した場合、環境情報４５は、天候状況、航空規則等に関する情報を更に含んでもよい。

上記各処理モジュール５１－５３の演算結果として、入力データ（対象エージェント情報４１、他エージェント情報４３及び環境情報４５）から第１特徴情報、第２特徴情報、及び第３特徴情報が生成される。各特徴情報は、コンピュータで取り扱い可能な任意形式のデータ（例えば、固定長の数列）で表現されてよい。

推定モジュール５５は、生成される第１特徴情報、第２特徴情報、及び第３特徴情報から、対象タイムステップの次のタイムステップにおける対象エージェントの１つ以上の候補状態を推定するように構成される。１つ以上の候補状態を得るための推定モジュール５５の構成は、実施の形態に応じて適宜決定されてよい。一例として、推定モジュール５５は、試行の度に出力（推定結果）を変え得るように構成されてよい。図２Ａの一例では、推定モジュール５５は、各特徴情報に加えて、多次元の乱数ベクトルの入力を更に受け付けることで、推定結果を変え得るように構成されている。乱数ベクトルの値は、例えば、公知の方法等の任意の方法で得られてよい。この構成によれば、推定モジュール５５に与える乱数ベクトルの値を変えることで、推定モジュール５５から得られる推定結果が変わり得る。そのため、与える乱数ベクトルの値を変えて、各特徴情報から候補状態を推定する処理（推定モジュール５５の演算処理）の試行を複数回実行することで、複数の異なる候補状態を得ることができる。なお、乱数ベクトルは、例えば、ノイズ等の別の表現で称されてもよい。

本実施形態に係るロードマップ構築モデル５は、上記各モジュール（５１－５３、５５）を備えることで、対象タイムステップの情報から次のタイムステップにおける対象エージェントの１つ以上の候補状態を推定するように構成される。したがって、本実施形態に係るロードマップ構築モデル５によれば、スタート状態からゴール状態に到達するまで、対象タイムステップを置き換えながら、対象タイムステップの候補状態から次のタイムステップの候補状態を推定する処理を繰り返すことで、対象エージェントのロードマップを構築することができる。

対象タイムステップは、ロードマップを構築する処理の過程で、ノードの配置（候補状態）を推定する時に着目するタイムステップである。最初の対象タイムステップにおける候補状態には、各エージェントのスタート状態が指定される。２回目以降の対象タイムステップにおける候補状態には、直前の対象タイムステップの推定処理においてロードマップ構築モデル５により推定された候補状態が指定される。すなわち、ロードマップ構築モデル５の推定処理により得られる次のタイムステップにおける候補状態を新たな対象タイムステップにおける候補状態として指定して、ロードマップ構築モデル５の推定処理を繰り返す。これにより、スタート状態からゴール状態に到達するまでのロードマップを構築することができる。なお、便宜的に、対象タイムステップを「ｔ番目のタイムステップ」と表現した場合、次のタイムステップを「ｔ＋１番目のタイムステップ」と表現してもよい（ｔは、自然数）。最初の対象タイムステップを「１番目のタイムステップ」と表現してもよい。

ロードマップは、連続状態空間においてエージェントが取り得る状態遷移の範囲を規定する。構築されるロードマップは、ノード及びエッジにより構成される。ノードは、連続状態空間で対象エージェントが遷移可能な候補状態を示す。すなわち、候補状態は、ロードマップを構成するノードに対応する。ロードマップを構築する過程で、対象タイムステップにおける候補状態を示すノード及び推定された次のタイムステップにおける候補状態を示すノードがエッジにより連結される。エッジは、連続状態空間上で、連結されるノード（候補状態）間が１タイムステップで遷移可能であることを示す。タイムステップの時間間隔は、実施の形態に応じて適宜決定されてよい。

連続状態空間は、状態の値が連続値を取り得る空間である。状態（スタート状態、ゴール状態、候補状態）は、例えば、位置、速度、向き等の時間経過により変化し得るエージェントの動的な特性に関する。状態として採用する特性は、実施の形態に応じて適宜選択されてよい。状態は、複数種類の特性を含んでよい。一例として、状態は、位置、速度、及び向きの少なくともいずれかを含んでよい。状態として採用する特性に位置が含まれる場合、連続状態空間は、エージェントの存在する位置を示す空間に対応し、連続状態空間上の遷移は移動に対応し、マルチエージェントの経路計画問題は、各エージェントの移動経路を計画する問題に対応する。

スタート状態は、連続状態空間上で遷移を開始する状態（例えば、移動の開始地点、現在地）である。ゴール状態は、連続状態空間上で遷移の目標となる状態（例えば、移動の目的地）である。状態の値の取り得る範囲は、任意に定義されてよい。一例では、状態の値の取り得る範囲は、速度０から最大速度まで等のように、有限の範囲で定義されてよい。

（各種情報）
対象エージェント情報４１は、連続状態空間における対象エージェントのゴール状態及び対象タイムステップにおける候補状態を示す情報を含むように構成される。対象エージェント情報４１は、これらの情報に加えて、対象エージェントのロードマップの構築（具体的には、ノード配置の推定）に使用可能な他の情報を更に含んでよい。本実施形態では、対象エージェント情報４１は、対象タイムステップよりも前のタイムステップにおける対象エージェントの候補状態、対象エージェントの属性（属性情報）、方向フラグ、及びCost-to-go特徴を更に含むように構成されてよい。

前のタイムステップ（以下、「過去タイムステップ」とも称する）として取り扱い可能なタイムステップは、対象タイムステップとして着目しているタイムステップに依存する。ロードマップ構築モデル５による推定処理を繰り返す度に、過去タイムステップとして取り扱い可能なタイムステップの数は増える。過去タイムステップとして取り扱うタイムステップの数は、特に限定されなくてよく、実施の形態に応じて適宜決定されてよい。対象タイムステップよりも前に複数のタイムステップが存在する場合、当該複数のタイムステップのうちの少なくとも一部が、過去タイムステップとして取り扱われてよい。

一例では、対象タイムステップより前の全てのタイムステップが過去タイムステップとして取り扱われてよい。ただし、過去タイムステップの情報は、対象エージェントのノードの配置履歴から好適な次のノードの配置を推定するために参照される。ノードの配置履歴のうちの少なくとも一部の情報があれば、次のタイムステップにおけるノードの好適な配置を推定する手がかりにその情報を用いることができる。そのため、必ずしも対象タイムステップより前の全てのタイムステップが過去タイムステップとして取り扱われなければならない訳ではない。他の一例では、対象タイムステップより前の任意数のタイムステップが過去タイムステップとして取り扱われてもよい。典型的には、対象タイムステップの直前の任意数のタイムステップが過去タイムステップとして取り扱われてよい。

また、一例では、１つ以上の過去タイムステップは、対象タイムステップの直前のタイムステップを含んでよい。ただし、過去タイムステップは、必ずしも直前のタイムステップでなければならない訳ではない。過去タイムステップは、対象タイムステップの直前のタイムステップを含まないように構成されてもよい。対象タイムステップよりも前のタイムステップが存在しない場合には、過去タイムステップにおける候補状態を示す情報は省略されてよい。

なお、過去タイムステップにおける候補状態を示す情報を第１処理モジュール５１に与えることは、例えば、再帰型ニューラルネットワーク等のように再帰構造を有するモデルに対象タイムステップにおける候補状態を示す情報を時系列で与えることを含んでよい。この場合、過去タイムステップにおける候補状態を示す情報が対象エージェント情報４１に明示的に含まれていなくても、対象エージェント情報４１に当該情報が含まれていると取り扱ってよい。

属性は、例えば、大きさ、形状、最大速度、重量等の、基本的には時間が経過しても変化しないエージェントの静的な特性に関する。対象エージェント情報４１に含まれる属性情報は、対象エージェントの属性を示すように適宜構成される。属性として採用する特性は、実施の形態に応じて適宜選択されてよい。属性は、複数種類の特性を含んでよい。一例として、対象エージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。最大速度は、単位時間当たりの最大移動量を示す。最大速度は、任意の指標で決定されてよい。一例として、最大速度は、エージェントの能力上の限界値であってもよいし、規制上の値（例えば、法定速度）であってもよい。

方向フラグは、対象タイムステップから次のタイムステップにかけて連続状態空間において対象エージェントの遷移する（遷移を促す）方向を示すように構成される。Cost-to-go特徴は、連続状態空間において、対象タイムステップの候補状態（ノード）から任意の各遷移方向（例えば、２次元の場合、当該候補状態を中心としたＫ×Ｋの矩形領域の各地点）に対してゴール状態に近付くか否かを数値により表現する特徴ベクトルである。

他エージェント情報４３は、連続状態空間における１つ以上の他のエージェントのゴール状態及び対象タイムステップにおける候補状態を示す情報を含むように構成される。対象エージェント情報４１と同様に、他エージェント情報４３は、これらの情報に加えて、対象エージェントのロードマップの構築に使用可能な、他のエージェントに関する他の情報を更に含んでよい。本実施形態では、他エージェント情報４３は、対象タイムステップよりも前のタイムステップ（過去タイムステップ）における他のエージェントの候補状態、他のエージェントの属性（属性情報）、及びCost-to-go特徴を更に含むように構成されてよい。

他エージェント情報４３に含まれる過去タイムステップの候補状態を示す情報、属性情報、及びCost-to-go特徴は、他のエージェントに関する点を除き、対象エージェント情報４１と同様であってよい。すなわち、他のエージェントに関して、対象タイムステップよりも前に複数のタイムステップが存在する場合、当該複数のタイムステップのうちの少なくとも一部が、他のエージェントの過去タイムステップとして取り扱われてよい。対象タイムステップよりも前のタイムステップが存在しない場合には、他エージェント情報４３において、過去タイムステップの候補状態を示す情報は省略されてよい。過去タイムステップにおける候補状態を示す情報を第２処理モジュール５２に与えることは、例えば、再帰型ニューラルネットワーク等のように再帰構造を有するモデルに対象タイムステップにおける候補状態を示す情報を時系列で与えることを含んでよい。この場合、過去タイムステップにおける候補状態を示す情報が他エージェント情報４３に明示的に含まれていなくても、他エージェント情報４３に当該情報が含まれていると取り扱ってよい。他エージェント情報４３に含まれる属性情報は、他のエージェントの属性を示すように適宜構成される。属性として採用する特性は、実施の形態に応じて適宜選択されてよい。属性は、複数種類の特性を含んでよい。一例として、他のエージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。他エージェント情報４３に含まれるCost-to-go特徴は、他のエージェントに関して、連続状態空間において、対象タイムステップの候補状態から任意の各遷移方向に対してゴール状態に近付くか否かを数値により表現する特徴ベクトルである。

ロードマップ構築モデル５による推定処理を繰り返す過程で、対象エージェント情報４１、他エージェント情報４３及び環境情報４５に含まれる各種情報は、その推定処理において対象タイムステップとして着目しているタイムステップに適合するように適宜更新されてよい。例えば、対象エージェント情報４１及び他エージェント情報４３に含まれる対象エージェント及び他のエージェントの対象タイムステップにおける候補状態を示す情報は、直前のタイムステップについての推定処理で得られた候補状態の推定結果に基づいて更新されてよい。一方で、推定処理を繰り返す間に変化しない情報（例えば、各エージェントのゴール状態）は、そのまま継続的に使用されてよい。対象エージェント情報４１、他エージェント情報４３及び環境情報４５に含まれる各種情報のデータ形式は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。

図２Ａの一例では、ロードマップ構築モデル５は、各モジュール（５１－５３、５５）に分離可能な構造を有している。すなわち、ロードマップ構築モデル５において、各モジュール（５１－５３、５５）は、明確に区別可能に配置されている。しかしながら、ロードマップ構築モデル５の構造は、このような例に限定されなくてよい。ロードマップ構築モデル５は、対象タイムステップにおける各情報（４１、４３、４５）の入力を受け付け、次の対象タイムステップにおける対象エージェントの１つ以上の候補状態（ノード）の推定結果を出力可能に構成されていればよい。他の一例では、各モジュール（５１－５３、５５）は、少なくとも部分的に一体的に構成されてよく、これにより、明確には区別不能に配置されてもよい。各情報（４１、４３、４５）の入力に関わる凡その部分を各処理モジュール５１－５３として捉え、出力に関わる凡その部分を推定モジュール５５と捉えてよい。なお、対象タイムステップにおける候補状態を示す情報含むデータを各特徴情報に符号化するエンコーダとして各処理モジュール５１－５３を捉え、次のタイムステップにおける候補状態を各特徴情報から復元するデコーダとして推定モジュール５５を捉えてよい。

（第２処理モジュールの処理例）
対象エージェントのロードマップを構築する際に、第２処理モジュール５２の処理対象とする他のエージェントの数は、実施の形態に応じて適宜選択されてよい。一例では、存在する複数のエージェントのうち、対象エージェントを除いた全てのエージェントを他のエージェントとして取り扱ってよい。ただし、対象エージェントの遷移に対して影響の低い他のエージェントは、対象エージェントのロードマップの経路に影響を与える可能性が低い。そのため、他の一例では、このような影響の低い他のエージェントの取り扱いを省略することで、処理の効率化を図ってもよい。具体例として、対象エージェントの近傍に存在する任意数のエージェントを他のエージェントとして取り扱ってよい。第２処理モジュール５２の処理する他のエージェントの数は固定数であってもよいし、或いは可変数であってもよい。

図２Ｂは、本実施形態に係る第２処理モジュール５２の演算処理の一例を模式的に示す。図２Ｂの一例では、第２処理モジュール５２は、他のエージェントの他エージェント情報４３の入力を個別に受け取り、当該他のエージェントについての特徴情報（Ｆ_i）及び優先度（ｗ_i）を出力するように構成される。優先度は、対象エージェントのロードマップを構築する際に、対応する他のエージェントの情報を重視する程度を示す。優先度は、重み、重要度等と読み替えられてもよい。一例として、Ｍ－１個の他のエージェントが存在する場合、他のエージェントそれぞれの他エージェント情報４３を第２処理モジュール５２に入力し、第２処理モジュール５２の演算処理をＭ－１回繰り返すことで、Ｍ－１個の特徴情報（Ｆ_i）及び優先度（ｗ_i）を取得することができる（ｉは１～Ｍ－１までの整数、Ｍは２以上の自然数）。第２処理モジュール５２は、以下の式１により得られた推定結果（出力）を統合する処理を実行する演算モジュールを含むように構成される。

この第２処理モジュール５２によれば、当該統合処理の結果（Ｆ）を任意数の他のエージェントについての第２特徴情報として取得することができる。

なお、任意数の他のエージェントの情報を取り扱うための第２処理モジュール５２の構成は、このような例に限定されなくてよい。他の一例では、取り扱う他のエージェントの最大数が予め規定されてよい。第２処理モジュール５２は、最大数の他のエージェントの情報の入力を受け取り、それぞれの特徴情報を出力するように構成されてよい。

（機械学習の処理）
図１に戻り、学習データ３は、各学習用エージェントの正解経路におけるゴール状態及び複数のデータセットを含むように構成される。学習用エージェントは、正解経路を得るのに用いられたエージェントである。学習用エージェントは、推論対象のエージェント（すなわち、経路計画の対象となるエージェント）と同一であってもよいし、異なっていてもよい。正解経路は、学習用エージェントのスタート状態からゴール状態まで遷移する経路を示す。正解経路は、人手により得られてもよいし、任意のアルゴリズムによる演算結果から得られてもよい。また、正解経路は、任意の指標に基づいて得られてよい。一例として、状態として位置を取り扱う場合、正解経路は、距離の短い経路、早く到達可能な経路、コストの少ない経路等であってよい。

各データセットは、各学習用エージェントの第１タイムステップにおける状態及び第２タイムステップにおける状態の組み合わせにより構成される。第１タイムステップは、正解経路における任意のタイムステップであってよい。第１タイムステップとして最初のタイムステップが選択された場合、第１タイムステップにおける状態は、正解経路におけるスタート状態により構成されてよい。第２タイムステップは、第１タイムステップの次のタイムステップである。

ロードマップ構築モデル５の機械学習は、以下の処理により構成される。すなわち、ロードマップ構築モデル５の機械学習において、モデル生成装置１は、複数の学習用エージェントのうちのいずれかの学習用エージェントを対象エージェントとして取り扱い、複数の学習用エージェントのうちのいずれかの学習用エージェント以外の残りの学習用エージェントの少なくとも一部を他のエージェントとして取り扱う。そして、モデル生成装置１は、各データセットについて、いずれかの学習用エージェントの第１タイムステップにおける状態を対象エージェントの対象タイムステップにおける候補状態として第１処理モジュール５１に与え、残りの学習用エージェントの少なくとも一部の第１タイムステップにおける状態を他のエージェントの対象タイムステップにおける候補状態として第２処理モジュール５２に与えることで、推定モジュール５５により推定される対象エージェントの次のタイムステップにおける候補状態が、いずれかの学習用エージェントの第２タイムステップにおける状態に適合するように、ロードマップ構築モデル５を訓練する。この機械学習の結果、対象エージェント及び他のエージェントの対象タイムステップにおける候補状態から対象エージェントの次のタイムステップにおける適切な候補状態を推定する能力を獲得した訓練済みのロードマップ構築モデル５を生成することができる。

［経路計画システム］
一方、本実施形態に係る経路計画システム２は、上記機械学習により生成された訓練済みのロードマップ構築モデル５を使用して、連続状態空間におけるマルチエージェントの経路計画問題を解くように構成された少なくとも１台のコンピュータである。

経路計画システム２は、複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報２２１を取得する。経路計画システム２は、訓練済みのロードマップ構築モデル５を使用して、取得された対象情報２２１から、エージェント毎にロードマップ２２５を構築する。

エージェント毎にロードマップ２２５を構築する処理は、複数のエージェントそれぞれを対象エージェントに個々に指定して以下の処理を実行することにより構成される。すなわち、経路計画システム２は、複数のエージェントのうちのいずれかのエージェントを対象エージェントとして取り扱い、複数のエージェントのうちの残りのエージェントの少なくとも一部を他のエージェントとして取り扱う。経路計画システム２は、取得された対象情報２２１により示されるいずれかのエージェントのスタート状態を対象エージェントの最初の対象タイムステップにおける候補状態として指定し、訓練済みのロードマップ構築モデル５により次のタイムステップにおける１つ以上の候補状態を推定する。経路計画システム２は、推定される次のタイムステップにおける１つ以上の候補状態にいずれかのエージェントのゴール状態又はその近傍状態が含まれるまで、推定された次のタイムステップにおける１つ以上の候補状態それぞれを新たな対象タイムステップにおける候補状態に指定して、訓練済みのロードマップ構築モデル５による次のタイムステップの候補状態の推定を繰り返す。経路計画システム２は、複数のエージェントそれぞれを対象エージェントに個々に指定してこれらの処理を実行する。その結果、エージェント毎にロードマップ２２５を構築することができる。

経路計画システム２は、エージェント毎に構築されたロードマップ２２５上で、スタート状態からゴール状態までの各エージェントの経路を探索する。そして、経路計画システム２は、探索された経路を示す情報を出力する。

［作用効果］
以上のとおり、本実施形態に係るモデル生成装置１では、訓練済みのロードマップ構築モデル５は、複数の学習用エージェントの正解経路から得られた学習データ３を使用した機械学習により生成される。この機械学習によれば、ロードマップ構築モデル５は、エージェントのスタート状態からゴール状態までの適切な経路に即してロードマップを構築する能力を獲得することができる。したがって、経路計画システム２では、各エージェントのスタート状態からゴール状態までの適切な経路（すなわち、探索したい経路）及びその周辺範囲にノードが配置されたロードマップ２２５をエージェント毎に構築することができる。これにより、空間全体にノードを配置する従来のロードマップ構築方法に比べて、構築されたエージェント毎のロードマップ２２５では、各エージェントの経路探索に適した範囲にノードを配置する範囲を絞ることができる。つまり、各エージェントの探索経路にとって無駄な位置へのノードの配置を省くことができる。そのため、ロードマップ２２５上にノードを密に配置しても、ノード数の増加を抑えることができる。よって、本実施形態によれば、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

なお、一例では、図１に示されるとおり、モデル生成装置１及び経路計画システム２は、ネットワークを介して互いに接続されてよい。ネットワークの種類は、例えば、インターネット、無線通信網、移動通信網、電話網、専用網等から適宜選択されてよい。ただし、モデル生成装置１及び経路計画システム２の間でデータをやりとりする方法は、このような例に限定されなくてもよく、実施の形態に応じて適宜選択されてよい。他の一例では、モデル生成装置１及び経路計画システム２の間では、記憶媒体を利用して、データがやりとりされてよい。

また、図１の例では、モデル生成装置１及び経路計画システム２は、それぞれ別個のコンピュータである。しかしながら、本実施形態に係る情報処理システムの構成は、このような例に限定されなくてもよく、実施の形態に応じて適宜決定されてよい。他の一例では、モデル生成装置１及び経路計画システム２は一体のコンピュータであってよい。更に他の一例では、モデル生成装置１及び経路計画システム２の少なくとも一方は、複数台のコンピュータにより構成されてよい。

§２ 構成例
［ハードウェア構成］
＜モデル生成装置＞
図３は、本実施形態に係るモデル生成装置１のハードウェア構成の一例を模式的に示す。図３に示されるとおり、本実施形態に係るモデル生成装置１は、制御部１１、記憶部１２、通信インタフェース１３、入力装置１４、出力装置１５、及びドライブ１６が電気的に接続されたコンピュータである。なお、図３では、通信インタフェースを「通信Ｉ／Ｆ」と記載している。後述する図４でも同様の表記を用いる。

制御部１１は、ハードウェアプロセッサであるＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等を含み、プログラム及び各種データに基づいて情報処理を実行するように構成される。制御部１１（ＣＰＵ）は、プロセッサ・リソースの一例である。記憶部１２は、メモリ・リソースの一例であり、例えば、ハードディスクドライブ、ソリッドステートドライブ等で構成される。本実施形態では、記憶部１２は、モデル生成プログラム８１、学習データ３、学習結果データ１２５等の各種情報を記憶する。

モデル生成プログラム８１は、訓練済みのロードマップ構築モデル５を生成する後述の機械学習の情報処理（図１０）をモデル生成装置１に実行させるためのプログラムである。モデル生成プログラム８１は、当該情報処理の一連の命令を含む。学習データ３は、ロードマップ構築モデル５の機械学習に用いられる。学習結果データ１２５は、機械学習により生成された訓練済みのロードマップ構築モデル５に関する情報を示す。本実施形態では、学習結果データ１２５は、モデル生成プログラム８１を実行した結果として生成される。

通信インタフェース１３は、例えば、有線ＬＡＮ（Local Area Network）モジュール、無線ＬＡＮモジュール等であり、ネットワークを介した有線又は無線通信を行うためのインタフェースである。モデル生成装置１は、通信インタフェース１３を介して、他のコンピュータとの間でデータ通信を行うことができる。

入力装置１４は、例えば、マウス、キーボード等の入力を行うための装置である。出力装置１５は、例えば、ディスプレイ、スピーカ等の出力を行うための装置である。オペレータは、入力装置１４及び出力装置１５を利用することで、モデル生成装置１を操作することができる。入力装置１４及び出力装置１５は、例えば、タッチパネルディスプレイ等により一体的に構成されてもよい。

ドライブ１６は、例えば、ＣＤドライブ、ＤＶＤドライブ等であり、記憶媒体９１に記憶されたプログラム等の各種情報を読み込むためのドライブ装置である。上記モデル生成プログラム８１及び学習データ３の少なくともいずれかは、記憶媒体９１に記憶されていてもよい。

記憶媒体９１は、コンピュータその他装置、機械等が、記憶されたプログラム等の各種情報を読み取り可能なように、当該プログラム等の情報を、電気的、磁気的、光学的、機械的又は化学的作用によって蓄積する媒体である。モデル生成装置１は、この記憶媒体９１から、上記モデル生成プログラム８１及び学習データ３の少なくともいずれかを取得してよい。

ここで、図３では、記憶媒体９１の一例として、ＣＤ、ＤＶＤ等のディスク型の記憶媒体を例示している。しかしながら、記憶媒体９１の種類は、ディスク型に限定される訳ではなく、ディスク型以外であってもよい。ディスク型以外の記憶媒体として、例えば、フラッシュメモリ等の半導体メモリを挙げることができる。ドライブ１６の種類は、記憶媒体９１の種類に応じて適宜選択されてよい。

なお、モデル生成装置１の具体的なハードウェア構成に関して、実施形態に応じて、適宜、構成要素の省略、置換及び追加が可能である。例えば、制御部１１は、複数のハードウェアプロセッサを含んでもよい。ハードウェアプロセッサは、マイクロプロセッサ、ＦＰＧＡ（field-programmable gate array）、ＤＳＰ（digital signal processor）等で構成されてよい。記憶部１２は、制御部１１に含まれるＲＡＭ及びＲＯＭにより構成されてもよい。通信インタフェース１３、入力装置１４、出力装置１５及びドライブ１６の少なくともいずれかは省略されてもよい。モデル生成装置１は、複数台のコンピュータで構成されてもよい。この場合、各コンピュータのハードウェア構成は、一致していてもよいし、一致していなくてもよい。また、モデル生成装置１は、提供されるサービス専用に設計された情報処理装置の他、汎用のサーバ装置、汎用のＰＣ（Personal Computer）、産業用ＰＣ等であってもよい。

＜経路計画システム＞
図４は、本実施形態に係る経路計画システム２のハードウェア構成の一例を模式的に示す。図４に示されるとおり、本実施形態に係る経路計画システム２は、制御部２１、記憶部２２、通信インタフェース２３、入力装置２４、出力装置２５、及びドライブ２６が電気的に接続されたコンピュータである。

経路計画システム２の制御部２１～ドライブ２６及び記憶媒体９２はそれぞれ、上記モデル生成装置１の制御部１１～ドライブ１６及び記憶媒体９１それぞれと同様に構成されてよい。制御部２１は、ハードウェアプロセッサであるＣＰＵ、ＲＡＭ、ＲＯＭ等を含み、プログラム及びデータに基づいて各種情報処理を実行するように構成される。制御部２１（ＣＰＵ）は、プロセッサ・リソースの一例である。記憶部２２は、メモリ・リソースの一例であり、例えば、ハードディスクドライブ、ソリッドステートドライブ等で構成される。本実施形態では、記憶部２２は、経路計画プログラム８２、学習結果データ１２５等の各種情報を記憶する。

経路計画プログラム８２は、訓練済みのロードマップ構築モデル５を使用して、エージェント毎にロードマップ２２５を構築し、構築されたロードマップ２２５上で各エージェントの経路を探索する後述の情報処理（図１１）を経路計画システム２に実行させるためのプログラムである。経路計画プログラム８２は、当該情報処理の一連の命令を含む。経路計画プログラム８２及び学習結果データ１２５の少なくともいずれかは、記憶媒体９２に記憶されていてよい。経路計画システム２は、経路計画プログラム８２及び学習結果データ１２５の少なくともいずれかを記憶媒体９２から取得してよい。

経路計画システム２は、通信インタフェース２３を介して、他のコンピュータとの間でデータ通信を行うことができる。オペレータは、入力装置２４及び出力装置２５の利用により、経路計画システム２を操作することができる。

なお、経路計画システム２の具体的なハードウェア構成に関して、実施形態に応じて、適宜、構成要素の省略、置換及び追加が可能である。例えば、制御部２１は、複数のハードウェアプロセッサを含んでもよい。ハードウェアプロセッサは、マイクロプロセッサ、ＦＰＧＡ、ＤＳＰ等で構成されてよい。記憶部２２は、制御部２１に含まれるＲＡＭ及びＲＯＭにより構成されてもよい。通信インタフェース２３、入力装置２４、出力装置２５、及びドライブ２６の少なくともいずれかは省略されてもよい。経路計画システム２は、複数台のコンピュータで構成されてもよい。この場合、各コンピュータのハードウェア構成は、一致していてもよいし、一致していなくてもよい。また、経路計画システム２は、提供されるサービス専用に設計された情報処理装置の他、汎用のサーバ装置、汎用のＰＣ、産業用ＰＣ等であってもよい。

［ソフトウェア構成］
＜モデル生成装置＞
図５は、本実施形態に係るモデル生成装置１のソフトウェア構成の一例を模式的に示す。モデル生成装置１の制御部１１は、記憶部１２に記憶されたモデル生成プログラム８１をＲＡＭに展開する。そして、制御部１１は、ＲＡＭに展開されたモデル生成プログラム８１に含まれる命令をＣＰＵにより実行する。これにより、図５に示されるとおり、本実施形態に係るモデル生成装置１は、データ取得部１１１、学習処理部１１２、及び保存処理部１１３をソフトウェアモジュールとして備えるように構成される。すなわち、本実施形態では、モデル生成装置１の各ソフトウェアモジュールは、制御部１１（ＣＰＵ）により実現される。

データ取得部１１１は、複数の学習用エージェントの正解経路から生成された学習データ３を取得するように構成される。学習処理部１１２は、取得された学習データ３を使用して、ロードマップ構築モデル５の機械学習を実施するように構成される。保存処理部１１３は、機械学習により生成された訓練済みのロードマップ構築モデル５に関する情報を学習結果データ１２５として生成し、生成された学習結果データ１２５を所定の記憶領域に保存するように構成される。学習結果データ１２５は、訓練済みのロードマップ構築モデル５を再生するための情報を含むように適宜構成されてよい。

（学習データの獲得例）
図６は、本実施形態に係る学習データ３の獲得方法の一例を模式的に示す。図６の一例では、２個の学習用エージェント（Ａ、Ｂ）が、互いに異なるスタート状態から異なるゴール状態へ遷移する１つのシチュエーションから学習データ３を獲得する場面を想定している。このシチュエーションの一例では、学習用エージェントＡの正解経路は、左上のスタート状態から右下のゴール状態へ７タイムステップで遷移するものであり、学習用エージェントＢの正解経路は、左下のスタート状態から右上のゴール状態へ７タイムステップで遷移するものである。なお、図６に示される、学習用エージェントの数、各学習用エージェントのスタート状態、ゴール状態、正解経路を構成する各状態、スタート状態からゴール状態へ至るタイムステップ数等の各種情報は、あくまで説明の便宜上の一例である。学習データ３を得るシチュエーションがこのような例に限定される訳ではない。

学習データ３は、機械学習における訓練データ及び正解データ（教師信号、ラベル）の組み合わせを複数セット構成可能な情報を含むように各学習用エージェントの正解経路を示す情報から適宜生成されてよい。機械学習において、訓練データは、ロードマップ構築モデル５の各処理モジュール５１－５３に与えられる。正解データは、その訓練データを与えることで推定モジュール５５により推定される対象エージェントの次のタイムステップにおける候補状態の真値として使用される。

本実施形態では、第１処理モジュール５１に与えられる対象エージェント情報４１は、対象エージェントのゴール状態、対象タイムステップにおける候補状態、過去タイムステップにおける候補状態、属性、方向フラグ、及びCost-to-go特徴を含むように構成されてよい。第２処理モジュール５２に与えられる他エージェント情報４３は、他のエージェントのゴール状態、対象タイムステップにおける候補状態、過去タイムステップにおける候補状態、属性、及びCost-to-go特徴を含むように構成されてよい。第３処理モジュール５３に与えられる環境情報４５は、障害物に関する情報を含むように構成されてよい。

これに応じて、学習データ３は、各学習用エージェントの正解経路におけるゴール状態３１、複数のデータセット３２、各学習用エージェントの訓練用属性情報３３、及び訓練用環境情報３５を含むように構成されてよい。各データセット３２は、第１タイムステップの状態３２１、第２タイムステップの状態３２３、訓練フラグ３２５、及び訓練用のCost-to-go特徴（不図示）を含むように構成されてよい。訓練フラグ３２５は、連続状態空間における第１タイムステップの状態３２１から第２タイムステップの状態３２３の方向を示すように構成される。訓練フラグ３２５は、方向フラグの訓練データとして用いられる。

図６に示されるとおり、各学習用エージェント（Ａ、Ｂ）のゴール状態３１を示す情報は、各学習用エージェント（Ａ、Ｂ）の正解経路における最終状態（ゴール状態）の情報から得ることができる。

各学習用エージェント（Ａ、Ｂ）の各データセット３２は、各学習用エージェント（Ａ、Ｂ）の正解経路における、連続する２つのタイムステップ（第１タイムステップ、第２タイムステップ）の組み合わせの情報から得ることができる。第１タイムステップには、スタート状態からゴール状態直前の状態までの任意のタイムステップが選択されてよく、第２タイムステップは、第１タイムステップとして選択されたタイムステップの次のタイムステップであってよい。図６の一例では、各学習用エージェント（Ａ、Ｂ）の正解経路において、７組の第１タイムステップ及び第２タイムステップの組み合わせをそれぞれ形成することができる。

各データセット３２の獲得方法の一例として、各学習用エージェント（Ａ、Ｂ）の正解経路において、連続する２つのタイムステップの組み合わせを形成する。形成された組み合わせの連続する２つのタイムステップの状態を第１タイムステップの状態３２１及び第２タイムステップの状態３２３として得ることができる。続いて、第１タイムステップの状態３２１から第２タイムステップの状態３２３の方向を示す情報を生成することで、訓練フラグ３２５を得ることができる。第１タイムステップの状態３２１から任意の各遷移方向に対してゴール状態３１に近付くか否かを数値により表現する特徴ベクトルを生成することで、訓練用のCost-to-go特徴を得ることができる。そして、得られた第１タイムステップの状態３２１、第２タイムステップの状態３２３、訓練フラグ３２５、及び訓練用のCost-to-go特徴を関連付けることで、各学習用エージェント（Ａ、Ｂ）の各データセット３２を得ることができる。図６では、一例として、学習用エージェント（Ａ、Ｂ）それぞれについて２つのデータセット３２を得る場面を例示している。第１タイムステップの状態３２１、訓練フラグ３２５及び訓練用のCost-to-go特徴は、対象タイムステップの情報の訓練データを構成し、第２タイムステップの状態３２３は次のタイムステップの候補状態の正解データ（教師信号、ラベル）を構成する。

なお、訓練フラグ３２５及び訓練用のCost-to-go特徴の少なくとも一方は、機械学習に使用される前に予め生成されてもよいし、或いは機械学習に使用される時に生成されてもよい。また、一例では、各データセット３２は、第１タイムステップよりも前のタイムステップ（過去タイムステップ）における状態（不図示）を示す情報を更に含むように構成されてよい。ただし、正解経路の時系列を示す情報が保持されていれば、過去タイムステップにおける状態を示す情報は、目的のデータセット３２よりも前のタイムステップの組み合わせにより生成されたデータセット３２から得ることができる。そのため、他の一例では、各データセット３２は、過去タイムステップにおける状態を示す情報を含んでいなくてもよい。第１処理モジュール５１及び第２処理モジュール５２が再帰構造を有するモデルにより構成され、対象エージェント情報４１及び他エージェント情報４３を時系列で与えることで、過去タイムステップの情報が参照される場合も同様に、各データセット３２は、過去タイムステップにおける状態を示す情報を含んでいなくてよい。

各学習用エージェント（Ａ、Ｂ）の訓練用属性情報３３は、各学習用エージェント（Ａ、Ｂ）の情報から適宜得ることができる。一例では、訓練用属性情報３３は、学習用エージェントの大きさ、形状、最大速度、及び重量の少なくともいずれかを示すように構成されてよい。各学習用エージェント（Ａ、Ｂ）の訓練用属性情報３３は、各学習用エージェント（Ａ、Ｂ）から得られてもよいし、手入力により得られてもよいし、他のコンピュータ、外部記憶装置等から得られてもよい。訓練用属性情報３３を得る方法は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。

訓練用環境情報３５は、正解経路を得たシチュエーションの環境の情報から適宜得ることができる。訓練用環境情報３５は、障害物に関する情報を含んでよい。障害物は、例えば、壁、荷物、動物（人間、人間以外の動物）、段差（階段）等であってよい。障害物に関する情報は、例えば、障害物の有無、位置、大きさ、存在範囲、形状等の障害物の属性を示す情報を含んでよい。正解経路を得るシチュエーションの環境には、任意の障害物が存在していてもよいし、存在していなくてもよい。障害物に関する情報は、この環境における障害物の情報から適宜得ることができる。

以上により、学習データ３を構成する各種情報（各学習用エージェントの正解経路におけるゴール状態３１、複数のデータセット３２、各学習用エージェントの訓練用属性情報３３、及び訓練用環境情報３５）を得ることができる。これらの情報は、各学習用エージェントの正解経路を得るシチュエーション毎に獲得することができる。これらの情報を獲得するシチュエーションの数は、特に限定されなくてよく、実施の形態に応じて適宜決定されてよい。これらの情報を獲得するシチュエーションは、実空間で実現されてもよいし、仮想空間でシミュレートされてもよい。各シチュエーションからこれらの情報を収集することで、学習データ３を生成することができる。

なお、各学習用エージェントは、学習データ３の獲得に供したエージェントである。各学習用エージェントは、実空間に存在するエージェント（実エージェント）であってもよいし、仮想上のエージェント（仮想エージェント）であってもよい。各学習用エージェントの正解経路は、人手により得られてもよいし、任意のアルゴリズム（例えば、公知の探索アルゴリズム）による演算結果から得られてもよい。任意のエージェントが過去に状態遷移を行った結果から正解経路が得られてもよい。学習データ３を構成する上記各種情報のうちのデータセット３２は、得られた各学習用エージェントの正解経路の少なくとも一部から得られてよい。

（機械学習方法の一例）
ロードマップ構築モデル５は、タスクを解く演算（推定処理）を実行するための１つ以上の演算パラメータであって、機械学習により値が調整される１つ以上の演算パラメータを備える機械学習モデルにより構成される。次の対象タイムステップにおける候補状態を推定する演算処理を実行可能であれば、ロードマップ構築モデル５に採用する機械学習モデルの種類、構成及び構造は、特に限定されなくてよく、実施の形態に応じて適宜決定されてよい。各処理モジュール５１－５３及び推定モジュール５５は、ロードマップ構築モデル５に採用する機械学習モデルの一部として構成されてよい。

一例として、ロードマップ構築モデル５は、ニューラルネットワークにより構成されてよい。この場合、各ノード間の結合の重み、各ノードの閾値等が、演算パラメータの一例である。第１処理モジュール５１及び第２処理モジュール５２は、例えば、多層パーセプトロン、再帰型ニューラルネットワーク等により構成されてよい。第３処理モジュールは、例えば、多層パーセプトロン、畳み込みニューラルネットワーク等により構成されてよい。推定モジュール５５は、ニューラルネットワーク等により構成されてよい。ロードマップ構築モデル５（各処理モジュール５１－５３及び推定モジュール５５）の層の種類、層の数、各層のノードの数及びノードの接続関係は、実施の形態に応じて適宜決定されてよい。

ロードマップ構築モデル５の機械学習では、学習処理部１１２は、複数の学習用エージェントのうちのいずれかを対象エージェントとして取り扱い、残りの学習用エージェントの少なくとも一部を他のエージェントとして取り扱う。以下、説明の便宜上、対象エージェントとして選択された学習用エージェントを「学習用対象エージェント」とも記載し、他のエージェントとして選択された学習用エージェントを「学習用他エージェント」とも記載する。

学習処理部１１２は、学習データ３から訓練データ及び正解データ（教師信号、ラベル）の組み合わせを構成し、訓練データを与えることで得られる出力が正解データに適合するようにロードマップ構築モデル５を訓練する。本実施形態では、学習処理部１１２は、学習データ３に含まれる各種情報のうち、学習用対象エージェントのゴール状態３１、各データセット３２の第１タイムステップの状態３２１、訓練フラグ３２５及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３により第１処理モジュール５１に与える訓練データ（訓練用の対象エージェント情報）を構成する。学習処理部１１２は、学習データ３に含まれる各種情報のうち、学習用他エージェントのゴール状態３１、各データセット３２の第１タイムステップの状態３２１及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３により第２処理モジュール５２に与える訓練データ（訓練用の他エージェント情報）を構成する。学習処理部１１２は、学習データ３に含まれる各種情報のうちの訓練用環境情報３５により第３処理モジュール５３に与える訓練データを構成する。学習処理部１１２は、学習用対象エージェントの各データセット３２の第２タイムステップの状態３２３により正解データを構成する。１件のデータセット３２毎に訓練データ及び正解データの組み合わせを１サンプル分生成することができる。構成される訓練データを各処理モジュール５１－５３に与えることで、推定モジュール５５から対象エージェントの次のタイムステップにおける候補状態の推定結果を得ることができる。学習処理部１１２は、各データセット３２について、上記訓練データを各処理モジュール５１－５３に与えることで推定モジュール５５により推定される対象エージェントの次のタイムステップにおける候補状態が正解データ（対応する学習用対象エージェントの第２タイムステップの状態３２３）に適合するように、ロードマップ構築モデル５を訓練する。

ロードマップ構築モデル５を訓練することは、訓練データに対して得られる出力が正解データに適合するようにロードマップ構築モデル５の演算パラメータの値を調整（最適化）することにより構成される。最適化問題を解く方法は、ロードマップ構築モデル５に採用した機械学習モデルの種類、構成、構造等に応じて適宜選択されてよい。

ロードマップ構築モデル５がニューラルネットワークにより構成される場合の機械学習方法の一例として、学習処理部１１２は、学習データ３から構成される訓練データを各処理モジュール５１－５３に与えて、各処理モジュール５１－５３の順伝播の演算処理を実行する。この演算処理の結果、学習処理部１１２は、各処理モジュール５１－５３から特徴情報を取得する。学習処理部１１２は、得られた特徴情報及び乱数ベクトルを推定モジュール５５に与えて、推定モジュール５５の順伝播の演算処理を実行する。乱数ベクトルの値は適宜得られてよい。この演算処理の結果、学習処理部１１２は、対象エージェントの次のタイムステップにおける候補状態を推定した結果を得る。学習処理部１１２は、得られた推定結果と対応する正解データとの間の誤差を算出し、算出された誤差の勾配を更に算出する。学習処理部１１２は、誤差逆伝播法により、算出された誤差の勾配を逆伝播することで、ロードマップ構築モデル５（各処理モジュール５１－５３及び推定モジュール５５）の演算パラメータの値の誤差を算出する。そして、学習処理部１１２は、算出された誤差に基づいて、演算パラメータの値を更新する。学習処理部１１２は、この一連の更新処理により、訓練データを与えることで得られる推定結果と正解データとの間の誤差の和が小さくなるように、ロードマップ構築モデル５の演算パラメータの値を調整する。この演算パラメータの値の調整は、例えば、規定回数実行する、算出される誤差の和が閾値以下になる等の所定の条件を満たすまで繰り返されてよい。また、例えば、損失関数、学習率等の機械学習の条件は、実施の形態に応じて適宜設定されてよい。この機械学習の処理により、訓練済みのロードマップ構築モデル５を生成することができる。

図７は、本実施形態に係るロードマップ構築モデル５の機械学習方法の他の一例を模式的に示す。図７に示される機械学習方法の一例では、ロードマップ構築モデル５の機械学習のために、第１処理モジュール５１、第２処理モジュール５２、及び第３処理モジュール５３とそれぞれ同一の構成を有する第１処理モジュール５１Ｚ、第２処理モジュール５２Ｚ、及び第３処理モジュール５３Ｚが用意される。説明の便宜上、第１処理モジュール５１、第２処理モジュール５２、及び第３処理モジュール５３をまとめて第１エンコーダＥ１と称し、第１処理モジュール５１Ｚ、第２処理モジュール５２Ｚ、及び第３処理モジュール５３Ｚをまとめて第２エンコーダＥ２と称する。なお、図７では、「ＳＡ」は、対象エージェントとして取り扱われる学習用エージェントを示し、学習データ３における学習用対象エージェントＳＡの各種情報に「Ａ」を更に付した。同様に、「ＳＢ」は、他のエージェントとして取り扱われる学習用エージェントを示し、学習データ３における学習用他エージェントＳＢの各種情報に「Ｂ」を更に付した。

図７の一例では、学習処理部１１２は、学習用対象エージェントＳＡのゴール状態３１Ａ、各データセット３２Ａの第１タイムステップの状態３２１Ａ、訓練フラグ３２５Ａ及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３Ａにより第１処理モジュール５１に与える訓練データを構成する。学習処理部１１２は、学習用他エージェントＳＢのゴール状態３１Ｂ、各データセット３２Ｂの第１タイムステップの状態３２１Ｂ及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３Ｂにより第２処理モジュール５２に与える訓練データを構成する。学習処理部１１２は、訓練用環境情報３５により第３処理モジュール５３に与える訓練データを構成する。一方、学習処理部１１２は、学習用対象エージェントＳＡの各データセット３２Ａの第１タイムステップの状態３２１Ａを第２タイムステップの状態３２３Ａに置き換え、それ以外は上記第１処理モジュール５１に与える訓練データと同様の情報により第１処理モジュール５１Ｚに与える訓練データを構成する。第２処理モジュール５２Ｚ及び第３処理モジュール５３Ｚに与える訓練データは、第２処理モジュール５２及び第３処理モジュール５３と同様である。学習処理部１１２は、学習用対象エージェントＳＡの各データセット３２Ａの第２タイムステップの状態３２３Ａにより正解データを構成する。

学習処理部１１２は、学習データ３から構成される上記訓練データを第１エンコーダＥ１に与えて、第１エンコーダＥ１の順伝播の演算処理を実行する。この演算処理の結果、学習処理部１１２は、第１エンコーダＥ１から特徴情報を取得する。同様に、学習処理部１１２は、学習データ３から構成される上記訓練データを第２エンコーダＥ２に与えて、第２エンコーダＥ２の順伝播の演算処理を実行する。この演算処理の結果、学習処理部１１２は、第２エンコーダＥ２から特徴情報を取得する。

学習処理部１１２は、各エンコーダ（Ｅ１、Ｅ２）から得られた特徴情報の分布間誤差を算出し、算出された分布間誤差の勾配を更に算出する。学習処理部１１２は、誤差逆伝播法により、算出された誤差の勾配を第１エンコーダＥ１に逆伝播することで、第１エンコーダＥ１の演算パラメータの値の誤差を算出する。

また、学習処理部１１２は、第２エンコーダＥ２から得られた特徴情報及び乱数ベクトルを推定モジュール５５に与えて、推定モジュール５５の順伝播の演算処理を実行する。乱数ベクトルの値は適宜得られてよい。この演算処理の結果、学習処理部１１２は、対象エージェントの次のタイムステップにおける候補状態を推定した結果を推定モジュール５５から得る。学習処理部１１２は、得られた推定結果と対応する正解データ（第２タイムステップの状態３２３Ａ）との間の再構成誤差を算出し、算出された再構成誤差の勾配を更に算出する。学習処理部１１２は、誤差逆伝播法により、算出された誤差の勾配を各エンコーダ（Ｅ１、Ｅ２）及び推定モジュール５５に逆伝播することで、各エンコーダ（Ｅ１、Ｅ２）及び推定モジュール５５の演算パラメータの値の誤差を算出する。

そして、学習処理部１１２は、算出された誤差に基づいて、各エンコーダ（Ｅ１、Ｅ２）及び推定モジュール５５の演算パラメータの値を更新する。学習処理部１１２は、この一連の更新処理により、算出される分布間誤差及び再構成誤差の和が小さくなるように、ロードマップ構築モデル５の演算パラメータの値を調整する。この演算パラメータの値の調整は、例えば、規定回数実行する、算出される誤差の和が閾値以下になる等の所定の条件を満たすまで繰り返されてよい。また、例えば、損失関数、学習率等の機械学習の条件は、実施の形態に応じて適宜設定されてよい。この機械学習の処理により、訓練済みのロードマップ構築モデル５（第１エンコーダＥ１及び推定モジュール５５）を生成することができる。

なお、上述のとおり、過去タイムステップの状態を示す情報は適宜取得されてよく、第１処理モジュール５１及び第２処理モジュール５２に与える訓練データは、得られた過去タイムステップの状態を示す情報を更に含んでよい。或いは、訓練データを時系列に与えることで、過去タイムステップの状態を示す情報がロードマップ構築モデル５（第１処理モジュール５１及び第２処理モジュール５２）に適宜反映されてよい。図７で例示される方法を採用する場合、第２エンコーダＥ２に対しても同様である。また、学習用対象エージェントは、複数の学習用エージェントから任意に選択されてよい。最適化問題を解く過程において、例えば、一連の更新処理を繰り返す度等の任意のタイミングで、学習用対象エージェントは変更されてよい。

保存処理部１１３は、上記機械学習により生成された訓練済みのロードマップ構築モデル５を再生するための学習結果データ１２５を生成する。訓練済みのロードマップ構築モデル５を再生可能であれば、学習結果データ１２５の構成は、特に限定されなくてよく、実施の形態に応じて適宜決定されてよい。一例として、学習結果データ１２５は、上記機械学習の調整により得られた各演算パラメータの値を示す情報を含んでよい。場合によって、学習結果データ１２５は、ロードマップ構築モデル５の構造を示す情報を更に含んでもよい。構造は、例えば、入力層から出力層までの層の数、各層の種類、各層に含まれるニューロンの数、隣接する層のニューロン同士の結合関係等により特定されてよい。保存処理部１１３は、生成された学習結果データ１２５を所定の記憶領域に保存する。

＜経路計画システム＞
図８は、本実施形態に係る経路計画システム２のソフトウェア構成の一例を模式的に示す。経路計画システム２の制御部２１は、記憶部２２に記憶された経路計画プログラム８２をＲＡＭに展開する。そして、制御部２１は、ＲＡＭに展開された経路計画プログラム８２に含まれる命令をＣＰＵにより実行する。これにより、図８に示されるとおり、本実施形態に係る経路計画システム２は、情報取得部２１１、マップ構築部２１２、探索部２１３、及び出力部２１４をソフトウェアモジュールとして備えるように構成される。すなわち、本実施形態では、モデル生成装置１と同様に、経路計画システム２の各ソフトウェアモジュールも、制御部２１（ＣＰＵ）により実現される。

情報取得部２１１は、複数のエージェントそれぞれの連続状態空間における遷移のスタート状態及びゴール状態を含む対象情報２２１を取得するように構成される。マップ構築部２１２は、学習結果データ１２５を保持することで、訓練済みのロードマップ構築モデル５を備えている。マップ構築部２１２は、訓練済みのロードマップ構築モデル５を使用して、取得された対象情報２２１から、エージェント毎にロードマップ２２５を構築するように構成される。探索部２１３は、エージェント毎に構築されたロードマップ２２５上で、所定の経路探索法により、スタート状態からゴール状態までの各エージェントの経路を探索するように構成される。出力部２１４は、探索された経路を示す情報を出力するように構成される。

（ロードマップの構築過程の一例）
対象情報２２１は、各エージェントのロードマップ２２５を構築する際に、各処理モジュール５１－５３に与える対象エージェント情報４１、他エージェント情報４３及び環境情報４５を構成するのに使用される。本実施形態では、対象情報２２１は、各エージェントのスタート状態及びゴール状態を示す情報に加えて、連続状態空間に存在する障害物に関する情報、各エージェントの属性を示す情報（属性情報）、各エージェントの各対象タイムステップにおける遷移フラグを更に含むように構成されてよい。各エージェントの属性は、大きさ、形状、最大速度、及び重力の少なくともいずれかを含んでよい。遷移フラグは、各エージェントを対象エージェントとして取り扱う際に、対象タイムステップから次のタイムステップにかけて連続状態空間において遷移する（遷移を促す）方向を示すように構成される。遷移フラグは、次のタイムステップにおける候補状態を推定する処理の試行の度に得られてよい。

マップ構築部２１２は、複数のエージェントのうちのいずれかを対象エージェントとして取り扱い、対象エージェントとして取り扱うエージェント以外の残りのエージェントの少なくとも一部を他のエージェントとして取り扱う。以下、複数のエージェントのうちの対象エージェントとして取り扱うエージェントを「暫定対象エージェント」とも記載し、他のエージェントとして取り扱うエージェントを「暫定他エージェント」とも記載する。マップ構築部２１２は、訓練済みのロードマップ構築モデル５を使用することで、暫定対象エージェントの次のタイムステップにおける１つ以上の候補状態を推定する。各エージェントを個々に対象エージェントとして取り扱うことで、各エージェントの次のタイムステップにおける１つ以上の候補状態を得ることができる。マップ構築部２１２は、各エージェントのスタート状態からゴール状態までのロードマップが構築されるように、訓練済みのロードマップ構築モデル５の使用を繰り返す。これにより、エージェント毎のロードマップ２２５を構築することができる。

エージェント毎のロードマップ２２５を構築する過程で、ロードマップ構築モデル５を使用することは、対象情報２２１に含まれる暫定対象エージェントに関する情報により対象エージェント情報４１を構成し、構成された対象エージェント情報４１を第１処理モジュール５１に与えることを含む。ロードマップ構築モデル５を使用することは、対象情報２２１に含まれる暫定他エージェントに関する情報により他エージェント情報４３を構成し、構成された他エージェント情報４３を第２処理モジュール５２に与えることを含む。ロードマップ構築モデル５を使用することは、対象情報２２１に含まれる障害物に関する情報から環境情報４５を構成し、構成された環境情報４５を第３処理モジュール５３に与えることを含む。

具体的に、マップ構築部２１２は、各エージェントについて、対象情報２２１に含まれるスタート状態から任意の各遷移方向に対してゴール状態に近付くか否かを数値により表現する特徴ベクトルを生成することで、最初の対象タイムステップの情報として与えるCost-to-go特徴を得る。マップ構築部２１２は、対象情報２２１に含まれる暫定対象エージェントのスタート状態、ゴール状態、属性情報及び遷移フラグ、並びに得られたCost-to-go特徴により、最初の対象タイムステップ（１番目のタイムステップ）の情報として第１処理モジュール５１に与える対象エージェント情報４１を構成する。マップ構築部２１２は、対象情報２２１に含まれる暫定他エージェントのスタート状態、ゴール状態及び属性情報、並びに得られたCost-to-go特徴により、最初の対象タイムステップの情報として第２処理モジュール５２に与える他エージェント情報４３を構成する。すなわち、マップ構築部２１２は、暫定対象エージェントのスタート状態を対象エージェントの最初の対象タイムステップにおける候補状態として指定し、暫定他エージェントのスタート状態を他のエージェントの最初の対象タイムステップにおける候補状態として指定する。マップ構築部２１２は、対象情報２２１に含まれる障害物に関する情報より第３処理モジュール５３に与える環境情報４５を構成する。

マップ構築部２１２は、構成された対象エージェント情報４１、他エージェント情報４３及び環境情報４５を各処理モジュール５１－５３に与えて、訓練済みのロードマップ構築モデル５の演算処理を実行する。これにより、マップ構築部２１２は、推定モジュール５５より、暫定対象エージェントの次のタイムステップ（２番目のタイムステップ）における１つ以上の候補状態の推定結果を得る。本実施形態では、マップ構築部２１２は、この推定処理の際に、推定モジュール５５に与える乱数ベクトルの値を変えることで、暫定対象エージェントの次のタイムステップにおける候補状態について複数の異なる推定結果を得ることができる。マップ構築部２１２は、各エージェントを個々に対象エージェントとして取り扱い、上記演算処理を実行することで、各エージェントの次のタイムステップにおける１つ以上の候補状態を得ることができる。

マップ構築部２１２は、推定された各エージェントの次のタイムステップ（ｔ＋１番目のタイムステップ、ｔは１以上の自然数）における１つ以上の候補状態それぞれを各エージェントの新たな対象タイムステップにおける候補状態として指定して、訓練済みのロードマップ構築モデル５による次のタイムステップにおける候補状態の推定を繰り返す。具体的に、マップ構築部２１２は、各エージェントについて、推定された１つ以上の候補状態それぞれから任意の各遷移方向に対してゴール状態に近付くか否かを数値により表現する特徴ベクトルを生成することで、推定された１つ以上の候補状態それぞれに対して、新たな対象タイムステップの情報として与えるCost-to-go特徴を得る。マップ構築部２１２は、暫定対象エージェントの推定された１つ以上の候補状態それぞれ、ゴール状態、属性情報、遷移フラグ、及び得られたCost-to-go特徴により、新たな対象タイムステップの情報として第１処理モジュール５１に与える対象エージェント情報４１を構成する。マップ構築部２１２は、暫定他エージェントの推定された１つ以上の候補状態（暫定他エージェントを対象エージェントとして取り扱うことで得られた推定結果）それぞれ、ゴール状態、属性情報及び得られたCost-to-go特徴により、新たな対象タイムステップの情報として第２処理モジュール５２に与える他エージェント情報４３を構成する。マップ構築部２１２は、対象情報２２１に含まれる障害物に関する情報より第３処理モジュール５３に与える環境情報４５を構成する。マップ構築部２１２は、構成された対象エージェント情報４１、他エージェント情報４３及び環境情報４５（新たな対象タイムステップの情報）を各処理モジュール５１－５３に与えて、訓練済みのロードマップ構築モデル５の演算処理を実行する。これにより、マップ構築部２１２は、推定モジュール５５より、新たな対象タイムステップの次のタイムステップにおける暫定対象エージェントの１つ以上の候補状態の推定結果を得る。マップ構築部２１２は、各エージェントを個々に対象エージェントとして取り扱い、上記演算処理を実行することで、新たな対象タイムステップの次のタイムステップにおける各エージェントの１つ以上の候補状態を得ることができる。

すなわち、マップ構築部２１２は、各エージェントについて得られた次のタイムステップにおける１つ以上の候補状態の推定結果により、対象エージェント情報４１及び他エージェント情報４３として与える各エージェントの候補状態を示す情報及びCost-to-go特徴を更新して、訓練済みのロードマップ構築モデル５による次のタイムステップにおける候補状態の推定処理を再度実行する。マップ構築部２１２は、推定される次のタイムステップにおける１つ以上の候補状態に暫定対象エージェントのゴール状態又はその近傍状態が含まれるまで、当該訓練済みのロードマップ構築モデル５による暫定対象エージェントについての次のタイムステップの候補状態の推定処理を繰り返す。マップ構築部２１２は、各エージェントを対象エージェントに個々に指定して、上記一連の推定処理の繰り返しを実行する。これにより、エージェント毎のロードマップ２２５を構築することができる。

なお、遷移フラグは、各タイムステップにおいて、任意のタイミングで得られてよい。一例として、遷移フラグは、各タイムステップ及び各エージェントについて、乱数ベクトルの値を変えて候補状態の異なる推定結果を得る際に得られてよい。これにより、対象タイムステップのノード（候補状態）に対して、次のタイムステップのノード（候補状態）を配置する方向を制御することができる。また、遷移フラグは、任意の方法により得られてよい。遷移フラグは、例えば、オペレータによる指示、ランダム、任意の指標／所定の規則に基づく選択等の方法により得られてよい。任意の指標又は所定の規則に基づいて遷移フラグを得る方法の一例として、暫定対象エージェントの対象タイムステップにおける候補状態からゴール状態へ近付く方向を中心とする所定の範囲のうち、ノード（次の対象タイムステップにおける候補状態の推定結果）が存在しない又は少ない（例えば、密度が閾値以下）方向を遷移フラグの示す方向として選択してよい。これにより、構築されるロードマップ２２５においてノードの配置される方向が偏らないようにすることができる。

また、各タイムステップにおいて第１処理モジュール５１及び第２処理モジュール５２に与えられる対象エージェント情報４１及び他エージェント情報４３には、それぞれのエージェントの過去タイムステップにおける候補状態を示す情報が含まれてよい。すなわち、訓練済みのロードマップ構築モデル５を使用することは、次の対象タイムステップの候補状態を推定する処理を繰り返す際に、暫定対象エージェントの対象タイムステップ以前のタイムステップにおける候補状態を過去タイムステップにおける候補状態として第１処理モジュール５１に与え、暫定他エージェントの対象タイムステップ以前のタイムステップにおける候補状態を過去タイムステップにおける候補状態として第２処理モジュール５２に与えることを含んでよい。各エージェントの過去タイムステップにおける候補状態を示す情報は、以前の推定処理により得られた候補状態の推定結果及びスタート状態から適宜取得されてよい。或いは、第１処理モジュール５１及び第２処理モジュール５２が再帰構造を有していることにより、上記推定処理を時系列に実行することで、過去タイムステップの情報が反映されてよい。

図９は、本実施形態に係る訓練済みのロードマップ構築モデル５によりエージェント毎のロードマップ２２５を構築する過程の一例を模式的に示す。具体的に、図９は、Ｍ個のエージェントが存在し、いずれかのエージェントが対象エージェントとして取り扱われる際には、残りのＭ－１個のエージェント全てが他のエージェントとして取り扱われると想定して、上記推定処理を実行した過程の一部を示す。ただし、上述のとおり、エージェントの数及び他のエージェントの取り扱いは、このような例に限定されなくてよい。

図９の一例では、１番目のエージェントのロードマップ２２５を構築する過程において、１番目のエージェントが対象エージェントとして取り扱われ、２番目からＭ番目のエージェントが他のエージェントとして取り扱われる（図９の一番上のライン）。Ｔ番目のタイムステップが対象タイムステップである段階では、Ｔ番目のタイムステップにおける１番目のエージェントに関する情報から対象エージェント情報４１が構成され、Ｔ番目のタイムステップにおける２番目からＭ番目のエージェントそれぞれに関する情報から他エージェント情報４３が構成される。これにより、上述のとおり、Ｔ番目のタイムステップが対象タイムステップである段階において、１番目のエージェントを対象エージェントとして取り扱う際にロードマップ構築モデル５に与える入力情報が得られる。

２番目からＭ番目のエージェントそれぞれを対象エージェントとして取り扱う場合も同様である。Ｔ番目のタイムステップにおける暫定対象エージェントに関する情報から対象エージェント情報４１が構成され、Ｔ番目のタイムステップにおける暫定他エージェントに関する情報から他エージェント情報４３が構成される。Ｔ番目のタイムステップが最初の対象タイムステップである場合（Ｔ＝１）、対象エージェント情報４１及び他エージェント情報４３を構成する暫定対象エージェント及び暫定他エージェントの候補状態には、それぞれのスタート状態が指定される。それ以外の場合（Ｔが２以上）、対象エージェント情報４１及び他エージェント情報４３を構成する暫定対象エージェント及び暫定他エージェントの候補状態には、直前に推定された１つ以上の候補状態のいずれかが指定される。

そして、得られた入力情報をロードマップ構築モデル５に与えて、ロードマップ構築モデル５の演算処理を実行することで、暫定対象エージェントの次のタイムステップにおける１つ以上の候補状態の推定結果を得ることができる。Ｔ番目のタイムステップが対象タイムステップである段階で、１番目のエージェントを対象エージェントとして取り扱っている過程では、Ｔ＋１番目のタイムステップにおける１番目のエージェントの１つ以上の候補状態の推定結果を得ることができる。次の段階（すなわち、Ｔ＋１番目のタイムステップを新たな対象タイムステップとして取り扱う段階）でロードマップ構築モデル５に与える入力情報を得るため、この推定結果に基づいて、１番目のエージェントの対象タイムステップにおける候補状態を示す情報及びCost-to-go特徴を更新する。これにより、Ｔ＋１番目のタイムステップにおける１番目のエージェントに関する情報を得ることができる。２番目からＭ番目のエージェントについても同様である。各エージェントを対象エージェントとして取り扱う過程で、Ｔ＋１番目のタイムステップにおける各エージェントの１つ以上の候補状態の推定結果を得ることができる。得られた推定結果に基づいて、対象タイムステップにおける候補状態を示す情報及びCost-to-go特徴を更新することで、Ｔ＋１番目のタイムステップにおける各エージェントに関する情報を得ることができる。

得られたＴ＋１番目のタイムステップにおける各エージェントの情報を用いて、上記ロードマップ構築モデル５による暫定対象エージェントに対する推定処理をそれぞれ実行することで、Ｔ＋２番目のタイムステップにおける各エージェントの１つ以上の候補状態の推定結果を得ることができる。推定される次のタイムステップにおける１つ以上の候補状態にゴール状態又はその近傍状態が含まれるまで、当該訓練済みのロードマップ構築モデル５による推定処理を各エージェントに対して繰り返し実行する。これにより、エージェント毎のロードマップ２２５（図９の例では、Ｍ個のロードマップ）を構築することができる。

＜その他＞
本実施形態では、モデル生成装置１及び経路計画システム２の各ソフトウェアモジュールがいずれも汎用のＣＰＵによって実現される例について説明している。しかしながら、上記ソフトウェアモジュールの一部又は全部が、１又は複数の専用のプロセッサ（例えば、グラフィックスプロセッシングユニット）により実現されてもよい。上記各モジュールは、ハードウェアモジュールとして実現されてもよい。また、モデル生成装置１及び経路計画システム２それぞれのソフトウェア構成に関して、実施形態に応じて、適宜、ソフトウェアモジュールの省略、置換及び追加が行われてもよい。

§３ 動作例
［モデル生成装置］
図１０は、本実施形態に係るモデル生成装置１の処理手順の一例を示すフローチャートである。以下のモデル生成装置１の処理手順は、モデル生成方法の一例である。ただし、以下のモデル生成装置１の処理手順は、一例に過ぎず、各ステップは可能な限り変更されてよい。また、以下のモデル生成装置１の処理手順について、実施の形態に応じて、適宜、ステップの省略、置換、及び追加が可能である。

（ステップＳ１０１）
ステップＳ１０１では、制御部１１は、データ取得部１１１として動作し、複数の学習用エージェントの正解経路から生成された学習データ３を取得する。

学習データ３は、図６で例示される方法により学習用エージェントの正解経路から適宜生成されてよい。本実施形態では、学習データ３は、各学習用エージェントの正解経路におけるゴール状態３１、複数のデータセット３２、各学習用エージェントの訓練用属性情報３３、及び訓練用環境情報３５を含むように構成されてよい。各データセット３２は、第１タイムステップの状態３２１、第２タイムステップの状態３２３、訓練フラグ３２５、及び訓練用のCost-to-go特徴を含むように構成されてよい。

学習データ３は、コンピュータの動作により自動的に生成されてもよいし、或いは少なくとも部分的にオペレータの操作を含むことで手動的に生成されてもよい。また、学習データ３の生成は、モデル生成装置１により行われてもよいし、或いはモデル生成装置１以外の他のコンピュータにより行われてもよい。制御部１１は、自動的に又は入力装置１４を介したオペレータの操作により手動的に学習データ３を生成してよい。或いは、制御部１１は、例えば、ネットワーク、記憶媒体９１等を介して、他のコンピュータにより生成された学習データ３を取得してもよい。学習データ３の一部がモデル生成装置１により生成され、その他が１又は複数の他のコンピュータにより生成されてよい。

学習データ３として取得する各種情報の量は、特に限定されなくてよく、機械学習を実施可能なように適宜決定されてよい。学習データ３を取得すると、制御部１１は、次のステップＳ１０２に処理を進める。

（ステップＳ１０２）
ステップＳ１０２では、制御部１１は、学習処理部１１２として動作し、取得された学習データ３を使用して、ロードマップ構築モデル５の機械学習を実施する。

一例として、制御部１１は、ロードマップ構築モデル５を構成する機械学習モデルの初期設定を行う。機械学習モデルの構造及び演算パラメータの初期値は、テンプレートにより与えられてもよいし、或いはオペレータの入力により決定されてもよい。追加学習又は再学習を行う場合、制御部１１は、過去の機械学習により得られた学習結果データに基づいて、ロードマップ構築モデル５の初期設定を行ってよい。

次に、制御部１１は、複数の学習用エージェントのうちのいずれかを対象エージェントとして取り扱い、残りの学習用エージェントの少なくとも一部を他のエージェントとして取り扱って、学習データ３から訓練データ及び正解データの組み合わせを構成する。第１処理モジュール５１に与える訓練データは、学習用対象エージェントのゴール状態３１、各データセット３２の第１タイムステップの状態３２１、訓練フラグ３２５及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３により構成される。第２処理モジュール５２に与える訓練データは、学習用他エージェントのゴール状態３１、各データセット３２の第１タイムステップの状態３２１及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３により構成される。第３処理モジュール５３に与える訓練データは、訓練用環境情報３５により構成される。正解データは、学習用対象エージェントの各データセット３２の第２タイムステップの状態３２３により構成される。制御部１１は、各データセット３２について、上記訓練データを各処理モジュール５１－５３に与えることで推定モジュール５５により推定される対象エージェントの次のタイムステップにおける候補状態が正解データに適合するように、ロードマップ構築モデル５の演算パラメータの値を調整する。

図７で例示される機械学習方法を採用し、ロードマップ構築モデル５にニューラルネットワークを採用する場合、制御部１１は、上記初期設定において、第１エンコーダＥ１と同一の構成を有する第２エンコーダＥ２を更に用意する。各エンコーダ（Ｅ１、Ｅ２）に与える訓練データ及び正解データの構成は上述のとおりである。第２エンコーダＥ２の第１処理モジュール５１Ｚに与える訓練データは、第１エンコーダＥ１の第１処理モジュール５１Ｚに与える訓練データに含まれる情報のうち、各データセット３２Ａの第１タイムステップの状態３２１Ａを第２タイムステップの状態３２３Ａに置き換えることで構成される。この点を除き、第２エンコーダＥ２に与える訓練データは、第１エンコーダＥ１に与える訓練データと同様である。

制御部１１は、各エンコーダ（Ｅ１、Ｅ２）にそれぞれの訓練データを与え、順伝播の演算処理を実行することにより、各エンコーダ（Ｅ１、Ｅ２）から特徴情報を取得する。制御部１１は、各エンコーダ（Ｅ１、Ｅ２）から得られた特徴情報の間の誤差（分布間誤差）を算出する。制御部１１は、誤差逆伝播法により、算出される分布間誤差の和が小さくなるように、第１エンコーダＥ１（各処理モジュール５１－５３）の演算パラメータの値を調整する。これと共に、制御部１１は、第２エンコーダＥ２から得られた特徴情報及び乱数ベクトルを推定モジュール５５に与えて、推定モジュール５５の順伝播の演算処理を実行することにより、対象エージェントの次のタイムステップにおける候補状態の推定結果を推定モジュール５５から取得する。制御部１１は、得られた推定結果と対応する正解データ（第２タイムステップの状態３２３Ａ）との間の誤差（再構成誤差）を算出する。制御部１１は、誤差逆伝播法により、算出される再構成誤差の和が小さくなるように、第１エンコーダＥ１、第２エンコーダＥ２及び推定モジュール５５の演算パラメータの値を調整する。この機械学習の処理の結果として、対象エージェント及び他のエージェントの対象タイムステップにおける候補状態から対象エージェントの次のタイムステップにおける適切な候補状態を推定する能力を獲得した訓練済みのロードマップ構築モデル５を生成することができる。

なお、本実施形態では、訓練データの各サンプルには訓練フラグ３２５が含まれている。訓練フラグ３２５によれば、機械学習に使用されるサンプルの遷移方向を管理することができる。これにより、各方向の遷移を万遍なく訓練するように訓練データを機械学習に使用することができる。一例として、制御部１１は、訓練フラグ３２５を参照することで、各遷移方向のサンプル数をカウントしてもよい。そして、制御部１１は、上記機械学習において、得られたサンプル数の逆数の確率で各遷移方向のサンプルを抽出（サンプリング）するようにしてもよい。遷移方向は、例えば、上下左右等のように、ある程度の幅を有するように規定されてよい。他の一例として、制御部１１は、各遷移方向のサンプル数が均一（同一又は閾値以下の差）になるように、各遷移方向のサンプル数を調節してもよい。調節方法の一例として、他の遷移方向よりもサンプル数の少ない遷移方向について、制御部１１は、例えば、複製、データ拡張等の方法によりサンプル数を増やす処理を実行してもよい。訓練フラグ３２５により各方向の遷移を万遍なく訓練することで、ノードを配置する方向が偏り難い訓練済みのロードマップ構築モデル５を生成することができる。

以上により機械学習の処理が完了すると、制御部１１は、次のステップＳ１０３に処理を進める。

（ステップＳ１０３）
ステップＳ１０３では、制御部１１は、保存処理部１１３として動作し、機械学習により生成された訓練済みのロードマップ構築モデル５に関する情報を学習結果データ１２５として生成する。制御部１１は、生成された学習結果データ１２５を所定の記憶領域に保存する。

所定の記憶領域は、例えば、制御部１１内のＲＡＭ、記憶部１２、外部記憶装置、記憶メディア又はこれらの組み合わせであってよい。記憶メディアは、例えば、ＣＤ、ＤＶＤ等であってよく、制御部１１は、ドライブ１６を介して記憶メディアに学習結果データ１２５を格納してもよい。外部記憶装置は、例えば、ＮＡＳ（Network Attached Storage）等のデータサーバであってよい。この場合、制御部１１は、通信インタフェース１３を利用して、ネットワークを介してデータサーバに学習結果データ１２５を格納してもよい。また、外部記憶装置は、例えば、モデル生成装置１に接続された外付けの記憶装置であってもよい。

学習結果データ１２５の保存が完了すると、制御部１１は、本動作例に係るモデル生成装置１の処理手順を終了する。

なお、生成された学習結果データ１２５は、任意のタイミングで経路計画システム２に提供されてよい。例えば、制御部１１は、ステップＳ１０３の処理として又はステップＳ１０３の処理とは別に、学習結果データ１２５を経路計画システム２に転送してもよい。経路計画システム２は、この転送を受信することで、学習結果データ１２５を取得してもよい。また、例えば、経路計画システム２は、通信インタフェース２３を利用して、モデル生成装置１又はデータサーバにネットワークを介してアクセスすることで、学習結果データ１２５を取得してもよい。また、例えば、経路計画システム２は、記憶媒体９２を介して、学習結果データ１２５を取得してもよい。また、例えば、学習結果データ１２５は、経路計画システム２に予め組み込まれてもよい。

更に、制御部１１は、上記ステップＳ１０１～ステップＳ１０３の処理を定期又は不定期に繰り返すことで、学習結果データ１２５を更新又は新たに生成してもよい。この繰り返しの際に、機械学習に使用する学習データ３の少なくとも一部の変更、修正、追加、削除等が適宜実行されてよい。そして、制御部１１は、更新した又は新たに生成した学習結果データ１２５を任意の方法で経路計画システム２に提供することで、経路計画システム２の保持する学習結果データ１２５を更新してもよい。

［経路計画システム］
図１１は、本実施形態に係る経路計画システム２の処理手順の一例を示すフローチャートである。以下で説明する経路計画システム２の処理手順は、経路計画方法の一例である。ただし、以下で説明する処理手順は一例に過ぎず、各ステップは可能な限り変更されてよい。また、以下の処理手順について、実施の形態に応じて、適宜、ステップの省略、置換、及び追加が行われてよい。

（ステップＳ２０１）
ステップＳ２０１では、制御部２１は、情報取得部２１１として動作し、複数のエージェントそれぞれの連続状態空間における遷移のスタート状態及びゴール状態を含む対象情報２２１を取得する。

本実施形態では、制御部２１は、対象情報２２１として、各エージェントのスタート状態及びゴール状態を示す情報、連続状態空間に存在する障害物に関する情報、各エージェントの属性を示す情報（属性情報）、各エージェントの各対象タイムステップにおける遷移フラグを取得してよい。各種情報は、例えば、情報処理、オペレータの入力、記憶部２２から取得する、外部装置（例えば、他のコンピュータ、記憶媒体、外部記憶装置等）から取得する等の任意の方法により取得されてよい。各種情報の少なくとも一部は、経路計画システム２内に予め保持されてもよいし、使用する際に任意の方法で獲得されてもよい。対象情報２２１を取得すると、制御部２１は、次のステップＳ２０２に処理を進める。

（ステップＳ２０２）
ステップＳ２０２では、制御部２１は、マップ構築部２１２として動作し、学習結果データ１２５を参照することで、訓練済みのロードマップ構築モデル５の設定を行う。そして、制御部２１は、訓練済みのロードマップ構築モデル５を使用して、取得された対象情報２２１から、エージェント毎にロードマップ２２５を構築する。

上述のとおり、制御部２１は、複数のエージェントのうちのいずれかを対象エージェントとして取り扱い、対象エージェントとして取り扱うエージェント以外の残りのエージェントの少なくとも一部を他のエージェントとして取り扱う。制御部２１は、対象情報２２１に含まれる各エージェントの情報から対象エージェント情報４１及び他エージェント情報４３を構成する。制御部２１は、対象情報２２１に含まれる障害物に関する情報から環境情報４５を構成する。対象エージェント情報４１、他エージェント情報４３及び環境情報４５の構成は上述のとおりである。なお、環境情報４５が障害物に関する情報以外の情報を更に含むように構成される場合、制御部２１は、経路探索を行う対象の環境における当該情報を対象情報２２１として取得し、取得された当該情報を更に含む環境情報４５を構成してよい。当該情報及び障害物に関する情報を含め、経路探索を行う対象の環境に関する情報を「対象環境情報」と称してよい。制御部２１は、対象情報２２１として対象環境情報を取得し、取得された対象環境情報により第３処理モジュール５３に与える環境情報４５を構成してよい。

制御部２１は、構成された対象エージェント情報４１、他エージェント情報４３及び環境情報４５を各処理モジュール５１－５３に与えて、訓練済みのロードマップ構築モデル５の演算処理を実行する。これにより、制御部２１は、暫定対象エージェントの次のタイムステップにおける１つ以上の候補状態の推定結果を得る。図２Ａの構成例では、制御部２１は、推定処理の際に、推定モジュール５５に与える乱数ベクトルの値を変えることで、暫定対象エージェントの次のタイムステップにおける候補状態について複数の異なる推定結果を得ることができる。制御部２１は、各エージェントを個々に対象エージェントとして取り扱い、上記演算処理を実行することで、各エージェントの次のタイムステップにおける１つ以上の候補状態を得る。

得られた候補状態（ノード）が、例えば、障害物に衝突する等の何らかの理由により、対象タイムステップにおける候補状態（ノード）から到達不能である場合、制御部２１は、得られた候補状態（ノード）を破棄又は修正してよい。一例として、制御部２１は、得られた候補状態を破棄し、ランダムサンプリング等の別の方法により、次のタイムステップの新たな候補状態を得てもよい。他の一例として、制御部２１は、連続状態空間上で、得られた候補状態に対応するノードを近傍範囲に移動することで、得られた候補状態を修正してもよい。移動方向は、任意に決定されてよい。また、近傍範囲は閾値等により適宜決定されてよい。

また、制御部２１は、得られた候補状態（ノード）を採用するか否かを評価するために、直前までの推定処理により得られている候補状態（ノード）の中に、現段階の推定処理により得られた候補状態（ノード）と置き換え可能な候補状態（ノード）が存在するか否かを判定してよい。置き換え可能か否かを評価する指標は、実施の形態に応じて適宜設定されてよい。一例として、現段階で得られた候補状態（ノード）と同じように他の候補状態（ノード）と接続可能で、現段階で得られた候補状態（ノード）と連続状態空間上で近傍範囲に配置された候補状態（ノード）を置き換え可能な候補状態として評価してよい。当該評価における近傍範囲は閾値等により適宜決定されてよい。現段階で得られた候補状態と置き換え可能な候補状態が存在しない場合、制御部２１は、得られた候補状態をそのまま採用してもよい。一方、置き換え可能な候補状態が存在する場合、制御部２１は、得られた候補状態の採用を見送ってもよい。或いは、制御部２１は、置き換え可能な候補状態と得られた候補状態とを統合（例えば、平均化する）してもよい。制御部２１は、直前までに得られた候補状態（ノード）のうち現段階で得られた候補状態から到達可能な候補状態（ノード）と現段階で得られた候補状態とをエッジで連結する。

対象タイムステップにおける推定処理が完了すると、制御部２１は、推定された各エージェントの次のタイムステップにおける１つ以上の候補状態それぞれを各エージェントの新たな対象タイムステップにおける候補状態として使用する。すなわち、制御部２１は、各エージェントについて得られた次のタイムステップにおける１つ以上の候補状態の推定結果により、対象エージェント情報４１及び他エージェント情報４３として与える各エージェントの候補状態を示す情報及びCost-to-go特徴を更新する。そして、制御部２１は、訓練済みのロードマップ構築モデル５による推定処理を再度実行する。

制御部２１は、推定される次のタイムステップにおける１つ以上の候補状態に暫定対象エージェントのゴール状態又はその近傍状態が含まれるまで、当該訓練済みのロードマップ構築モデル５による推定処理を繰り返し実行する。推定された候補状態が近傍状態である（ゴール状態の近傍に配置されている）か否かは閾値等により適宜評価されてよい。なお、本実施形態では、推定処理を繰り返す過程において、対象エージェント情報４１及び他エージェント情報４３として各エージェントの過去タイムステップにおける候補状態を示す情報が訓練済みのロードマップ構築モデル５に与えられてよい。或いは、訓練済みのロードマップ構築モデル５（第１処理モジュール５１及び第２処理モジュール５２）が再帰構造を有することで、過去タイムステップの情報が推定処理に適宜反映されてよい。これにより、次のタイムステップにおける候補状態を推定するのに、対象タイムステップにおける候補状態の情報だけではなく、過去タイムステップにおける候補状態の情報が参照されてよい。また、各エージェントを対象エージェントとして取り扱い、候補状態の推定処理を実行する際、遷移フラグは、各タイムステップにおいて、候補状態を推定する処理を試行する度等の任意のタイミングで新たに得られてよい。遷移フラグは、例えば、オペレータによる指示、ランダム、任意の指標／所定の規則に基づく選択等の任意の方法により得られてよい。以上の処理により、制御部２１は、エージェント毎のロードマップ２２５を構築することができる。

なお、制御部２１は、各エージェントの各タイムステップにおける推定処理に関して、所定の確率で、上記ロードマップ構築モデル５を実行せず、他のアルゴリズム（例えば、ランダムに状態遷移）により、次のタイムステップにおける候補状態を生成してよい。所定の確率は、適宜設定されてよい。これにより、仮に、学習段階における学習データ３を獲得した経路計画問題と推論段階における経路計画問題との間で、エージェントの取り得る経路が大きくことなることで、訓練済みのロードマップ構築モデル５による適切な候補状態の推定が困難な場合であっても、他のアルゴリズムにより生成された候補状態（ノード）がロードマップに含まれていることで、経路計画を安定的に行うことができる。

図１２は、本実施形態に係る訓練済みのロードマップ構築モデル５により構築されるエージェント（Ｘ、Ｙ）毎のロードマップ（２２５Ｘ、２２５Ｙ）の一例を模式的に示す。図１２の一例では、２つのエージェント（Ｘ、Ｙ）が存在しており、エージェントＸは、連続状態空間の左上から右下への遷移を計画し、エージェントＹは、左下から右上への遷移を計画している。この場面において、ロードマップ２２５Ｘ（実線）は、エージェントＸに対して構築されたロードマップ２２５の一例を示し、ロードマップ２２５Ｙ（点線）は、エージェントＹに対して構築されたロードマップ２２５の一例を示す。

訓練済みのロードマップ構築モデル５は、複数の学習用エージェントの正解経路から得られた学習データ３を用いた機械学習により、エージェントのスタート状態からゴール状態までの適切な経路に即してロードマップ２２５を構築する能力を獲得している。したがって、図１２に例示されるとおり、構築されるエージェント（Ｘ、Ｙ）毎のロードマップ（２２５Ｘ、２２５Ｙ）において、各エージェント（Ｘ、Ｙ）のスタート状態からゴール状態までの最適な経路が存在する蓋然性の高い範囲にノードが配置されやすく、それ以外の範囲にノードが配置され難くすることができる。

エージェント毎のロードマップ２２５の構築が完了すると、制御部２１は、次のステップＳ２０３に処理を進める。

（ステップＳ２０３）
図１１に戻り、ステップＳ２０３では、制御部２１は、探索部２１３として動作し、エージェント毎に構築されたロードマップ２２５上で、所定の経路探索法により、スタート状態からゴール状態までの各エージェントの経路を探索する。経路探索法は、実施の形態に応じて適宜選択されてよい。一例では、ＣＢＳ（Conflict-based Search）、prioritized planning等の公知の経路探索法が、各エージェントの経路を探索するのに用いられてよい。各エージェントの経路の探索が完了すると、制御部２１は、次のステップＳ２０４に処理を進める。

（ステップＳ２０４）
ステップＳ２０４では、制御部２１は、出力部２１４として動作し、探索された経路を示す情報（以下、「探索結果情報」とも記載する）を出力する。

出力先及び出力する情報の内容は、実施の形態に応じて適宜決定されてよい。一例として、制御部２１は、各エージェントの探索された経路を示す情報をそのまま出力してよい。出力された情報は、各エージェントが状態遷移するために活用されてよい。例えば、エージェントが人間又は人間の操作する装置である場合、当該人間は、出力された情報に基づいて、自身の状態遷移又は当該装置の操作を行ってよい。他の一例として、各エージェントを直接的に又は制御装置を介して間接的に制御可能である場合、制御部２１は、経路の探索結果に応じて各エージェントの動作を指示する（すなわち、探索結果に従った状態遷移を各エージェントに促す）命令を探索結果情報として出力してよい。出力先は、例えば、ＲＡＭ、記憶部２２、出力装置２５、他のコンピュータ、エージェント等であってよい。

なお、経路計画の対象となるエージェントの数は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。経路計画を繰り返す場合、エージェントの数は変動してもよい。また、経路計画の対象となる各エージェントは、実空間に存在するエージェント（実エージェント）であってもよいし、仮想上のエージェント（仮想エージェント）であってもよい。各エージェントは、学習用エージェントと同一であってもよいし、異なっていてもよい。

各エージェントは、状態遷移可能であれば、その種類は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。各エージェントは、例えば、移動体、人間、人間の操作する装置、マニピュレータ等であってよい。人間の操作する装置は、例えば、一般車両等であってよい。エージェントがマニピュレータである場合、経路計画問題を解くことは、マニピュレータの動作計画問題を解くことに相当してよい。経路計画の対象となる全てのエージェントは同一種類であってもよいし、或いは少なくとも一部のエージェントは、他のエージェントと種類が異なっていてもよい。一例として、各エージェントは、自律的に移動するように構成される移動体であってよい。移動体は、例えば、移動ロボット、自動運転車両、ドローン等であってよい。移動ロボットは、例えば、物品の搬送、案内、見回り、清掃等の目的で移動するように構成されてよい。

図１３は、本実施形態に係るエージェントの一例を模式的に示す。図１３の場面では、２台の移動体（６Ｘ、６Ｙ）が存在している。左上に位置する移動体６Ｘは、右下のゴールＧＸへの移動を計画しており、左下に位置する移動体６Ｙは、右上のゴールＧＹへの移動を計画している。連続状態空間は、各移動体（６Ｘ、６Ｙ）の位置を示すものであると想定する。各移動体（６Ｘ、６Ｙ）が、エージェントの一例である。

この場面において、制御部２１は、各移動体（６Ｘ、６Ｙ）をエージェントとして取り扱い、上記ステップＳ２０１～ステップＳ２０３の処理を実行することで、各移動体（６Ｘ、６Ｙ）の各ゴール（ＧＸ、ＧＹ）までの移動経路を探索してよい。そして、本ステップＳ２０４の処理の一例として、制御部２１は、得られた探索結果情報を各移動体（６Ｘ、６Ｙ）に対して出力することで、各移動体（６Ｘ、６Ｙ）に探索結果に従った移動を指示してよい。

探索結果情報の出力が完了すると、制御部２１は、本動作例に係る経路計画システム２の処理手順を終了する。

なお、経路計画を行うシチュエーションは、実空間上で起きている若しくは起きたものであってもよいし、又は仮想空間上のシミュレーションで実現されているものであってもよい。これに応じて、制御部２１は、ステップＳ２０１～ステップＳ２０４の一連の情報処理を任意のタイミングで実行してよい。経路計画を行うタイミングは、オンラインであってもよいし、或いはオフラインであってもよい。

一例として、各エージェントが移動体であり、各移動体が移動経路の計画を行う場面（例えば、図１３）において、経路計画システム２は、リアルタイムでかつオンラインで各移動体の現在地及び目的地の情報を取得してもよい。経路計画システム２は、現在地をスタート状態、目的地をゴール状態として取り扱い、上記ステップＳ２０１～ステップＳ２０４の処理を実行してよい。これにより、経路計画システム２は、リアルタイムに各移動体の移動経路の計画を行ってよい。また、経路計画システム２は、定期的に又は不定期に各移動体の現在位置及び目的地の情報を取得し、上記ステップＳ２０１～ステップＳ２０４の一連の情報処理を再度実行することで、各移動体の移動経路の計画を更新してもよい。上記ステップＳ２０１～ステップＳ２０４の一連の情報処理を繰り返す際、移動体（エージェント）の数は変動してもよい。これにより、各移動体が目的地に到達するまで、各移動体に対して適切な経路情報を継続的に作成してよい。

［特徴］
以上のとおり、本実施形態では、上記ステップＳ１０２の処理において、訓練済みのロードマップ構築モデル５は、複数の学習用エージェントの正解経路から得られた学習データ３を使用した機械学習により生成される。この機械学習によれば、エージェントのスタート状態からゴール状態までの適切な経路に即してロードマップを構築する能力を獲得した訓練済みのロードマップ構築モデル５を生成することができる。ステップＳ２０２の処理において、この訓練済みのロードマップ構築モデル５を用いることで、図１２に例示されるとおり、最適な経路の存在する蓋然性の高い範囲に焦点を当ててノードが配置されたロードマップ２２５をエージェント毎に構築することができる。これにより、構築されたエージェント毎のロードマップ２２５では、各エージェントの経路探索に適した範囲にノードを配置する範囲を絞ることができる。したがって、ロードマップ２２５上にノードを密に配置しても、ノード数の増加を抑えることができる。よって、本実施形態によれば、ステップＳ２０３の処理において、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。

また、本実施形態では、ロードマップ構築モデル５は、障害物を含む環境の情報を処理する第３処理モジュール５３を備えている。これにより、訓練済みのロードマップ構築モデル５は、障害物を含む環境の状況を考慮して、各エージェントのロードマップ２２５を構成するノードの配置を推定することができる。したがって、ステップＳ２０２の処理において、各エージェントに対して環境に適したロードマップ２２５を構築することができる。その結果、ステップＳ２０３の処理において、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

また、本実施形態では、第１処理モジュール５１及び第２処理モジュール５２は、対象エージェント情報４１及び他エージェント情報４３として、過去タイムステップにおける候補状態を更に処理するように構成されてよい。これにより、訓練済みのロードマップ構築モデル５は、各エージェントの状態遷移を時系列に考慮しながら、各エージェントのロードマップ２２５を構成するノードの配置を推定することができる。したがって、ステップＳ２０２の処理において、複数のタイムステップを経てスタート状態からゴール状態に到達するエージェントに対して適したロードマップ２２５を構築することができる。その結果、ステップＳ２０３の処理において、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

また、本実施形態では、第１処理モジュール５１は、対象エージェント情報４１として、対象エージェントの属性情報を更に処理するように構成されてよい。これにより、訓練済みのロードマップ構築モデル５は、各エージェントの属性を考慮しながら、ロードマップ２２５を構成するノードの配置をエージェント毎に推定することができる。したがって、属性の異なるエージェントが存在する場合でも、ステップＳ２０２の処理において、適したロードマップ２２５をエージェント毎に構築することができる。その結果、属性の異なるエージェントが混在する場合でも、ステップＳ２０３の処理において、連続状態空間上でのマルチエージェントの経路計画問題を適切に解くことができる。なお、一例では、対象エージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。これにより、ステップＳ２０２の処理において、外形、速度、及び重量に関する制約に対して、適したロードマップ２２５をエージェント毎に構築することができる。

また、本実施形態では、第２処理モジュール５２は、他エージェント情報４３として、他エージェントの属性情報を更に処理するように構成されてよい。これにより、訓練済みのロードマップ構築モデル５は、他のエージェントの属性を考慮して、対象エージェントに適したノードの配置を推定することができる。したがって、様々な属性を備えるエージェントが存在する環境下でも、ステップＳ２０２の処理において、各エージェントに対して適したロードマップ２２５を構築することができる。その結果、ステップＳ２０３の処理において、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。なお、一例では、他のエージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含んでよい。これにより、外形、速度、及び重量の少なくともいずれかの異なるエージェントが混在しても、ステップＳ２０３の処理において、各エージェントに対して最適な経路を発見する可能性をより高めると共に、探索に係るコストの更なる低減を図ることができる。

また、本実施形態では、第１処理モジュール５１は、対象エージェント情報４１として、遷移方向を示す方向フラグの情報を更に処理するように構成されてよい。これにより、ステップＳ１０２の処理において、訓練フラグ３２５に基づいて、各方向の遷移を万遍なく訓練するように訓練データを機械学習に使用することができる。その結果、ノードを配置する方向が偏り難い訓練済みのロードマップ構築モデル５を生成することができる。更に、対象エージェント情報４１に方向フラグの項目が含まれていることで、方向フラグによりノードを配置する方向を制御する能力を獲得した訓練済みのロードマップ構築モデル５を生成することができる。

これに応じて、ステップＳ２０２の処理では、この訓練済みのロードマップ構築モデル５を使用することで、各エージェントのロードマップ２２５においてノードの配置される方向が偏らないようにすることができる。偏った方向にノードが配置される場合には、方向フラグとして与える遷移フラグにより、ノードを配置する方向を制御し、ノードを配置する方向を制御することができる。これにより、構築されるロードマップ２２５において、状態遷移の選択幅が狭くならないようにすることができる。その結果、ステップＳ２０３の処理において、連続状態空間上でエージェントに対して最適な経路を発見する可能性をより高めることができる。

§４ 変形例
以上、本発明の実施の形態を詳細に説明してきたが、前述までの説明はあらゆる点において本発明の例示に過ぎない。本発明の範囲を逸脱することなく種々の改良又は変形を行うことができることは言うまでもない。例えば、以下のような変更が可能である。なお、以下では、上記実施形態と同様の構成要素に関しては同様の符号を用い、上記実施形態と同様の点については、適宜説明を省略した。以下の変形例は適宜組み合わせ可能である。

＜４．１＞
上記実施形態では、経路計画システム２は、対象情報２２１を取得し、各エージェントのロードマップ２２５を構築し、各エージェントの経路計画問題を解く一連の処理を実行するように構成されている。しかしながら、各処理を実行するための装置構成は、このような例に限定されなくてよい。他の一例として、各エージェントのロードマップ２２５を構築する装置、及び得られたロードマップ２２５により連続状態空間上における各エージェントの経路を探索する装置は、別個独立の１又は複数台のコンピュータにより構成されてよい。

図１４は、本変形例に係る経路計画システムの構成の一例を模式的に示す。本変形例では、経路計画システムは、ロードマップ構築装置２０１及び経路探索装置２０２により構成される。ロードマップ構築装置２０１は、訓練済みのロードマップ構築モデル５を使用して、各エージェントのロードマップ２２５を構築するように構成された少なくとも１台のコンピュータである。経路探索装置２０２は、構築されたロードマップ２２５上で各エージェントの経路を探索するように構成された少なくとも１台のコンピュータである。

ロードマップ構築装置２０１及び経路探索装置２０２のハードウェア構成は、上記経路計画システム２のハードウェア構成と同様であってよい。ロードマップ構築装置２０１及び経路探索装置２０２は、直接的に接続されてもよいし、或いはネットワークを介して接続されてよい。一例では、ロードマップ構築装置２０１及び経路探索装置２０２は、これらの接続を介して、互いにデータ通信を行ってもよい。他の一例では、ロードマップ構築装置２０１及び経路探索装置２０２の間では、記憶媒体等を介してデータがやり取りされてよい。

ロードマップ構築プログラムは、経路計画プログラム８２に含まれる命令のうち、ロードマップ２２５を構築するまでの命令を含むように構成されてよい。ロードマップ構築プログラムは、構築されたロードマップ２２５を出力する命令を更に含んでよい。ロードマップ構築装置２０１は、このロードマップ構築プログラムを実行することで、情報取得部２１１、マップ構築部２１２、及び出力部２１６をソフトウェアモジュールとして備えるように構成されてよい。出力部２１６は、構築されたエージェント毎のロードマップ２２５を出力するように構成されてよい。

経路探索プログラムは、経路計画プログラム８２に含まれる命令のうち、経路探索を行い、探索結果を出力するまでの命令を含むように構成されてよい。経路探索プログラムは、エージェント毎に構築されたロードマップ２２５を取得する命令を更に含んでよい。経路探索装置２０２は、この経路探索プログラムを実行することで、マップ取得部２１８、探索部２１３、及び出力部２１４をソフトウェアモジュールとして備えるように構成されてよい。マップ取得部２１８は、エージェント毎に構築されたロードマップ２２５を取得するように構成されてよい。

なお、上記実施形態と同様に、ロードマップ構築装置２０１及び経路探索装置２０２のソフトウェアモジュールの一部又は全部が、１又は複数の専用のプロセッサにより実現されてもよい。ロードマップ構築装置２０１及び経路探索装置２０２の各モジュールは、ハードウェアモジュールとして実現されてもよい。また、ロードマップ構築装置２０１及び経路探索装置２０２それぞれのソフトウェア構成に関して、実施形態に応じて、適宜、ソフトウェアモジュールの省略、置換及び追加が行われてもよい。

本変形例に係るロードマップ構築装置２０１では、制御部は、情報取得部２１１として動作し、上記ステップＳ２０１の処理を実行する。次に、制御部は、マップ構築部２１２として動作し、上記ステップＳ２０２の処理を実行する。これにより、エージェント毎のロードマップ２２５が構築される。そして、制御部は、出力部２１６として動作し、構築されたエージェント毎のロードマップ２２５を出力する。出力先及び出力方法は、実施の形態に応じて適宜選択されてよい。出力先には、経路探索装置２０２が含まれてよい。構築されたエージェント毎のロードマップ２２５は、任意のタイミング及び任意の方法で経路探索装置２０２に提供されてよい。

本変形例に係る経路探索装置２０２では、制御部は、マップ取得部２１８として動作し、エージェント毎に構築されたロードマップ２２５を取得する。各エージェントのロードマップ２２５を取得する経路は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。次に、制御部は、探索部２１３として動作し、上記ステップＳ２０３の処理を実行する。そして、制御部は、出力部２１４として動作し、上記ステップＳ２０４の処理を実行する。

本変形例に係るロードマップ構築装置２０１によれば、訓練済みのロードマップ構築モデル５を用いることで、最適な経路の存在する蓋然性の高い範囲に焦点を当ててノードが配置されたロードマップ２２５をエージェント毎に構築することができる。したがって、ロードマップ２２５上にノードを密に配置しても、ノード数の増加を抑えることができる。よって、経路探索装置２０２において、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減を図ることができる。本変形例に係るロードマップ構築装置２０１は、そのような作用効果を経路探索装置２０２に対して享受させることができる。

＜４．２＞
ロードマップ構築モデル５の機械学習の方法は、上述の方法に限られなくてよい。対象タイムステップにおける各種情報から対象エージェントの次のタイムステップにおける候補状態を推定する能力を獲得可能であれば、ロードマップ構築モデル５の機械学習の方法は、特に限られなくてよく、実施の形態に応じて適宜選択されてよい。一例として、ロードマップ構築モデル５の機械学習の方法には敵対的学習が採用されてよい。

図１５は、本変形例に係る敵対的学習によるロードマップ構築モデル５の機械学習方法の一例を模式的に示す。図１５の一例では、敵対的学習を実行するために、ロードマップ構築モデル５に対して識別器５９が用意される。識別器５９には、演算パラメータを備える機械学習モデルが用いられる。識別器５９は、サンプルの入力を受け付け、入力されたサンプルの由来が正解データであるかロードマップ構築モデル５による推定結果であるかを識別する処理を実行するように構成される。この識別処理を実行可能であれば、識別器５９に用いられる機械学習モデルの種類は、特に限定されなくてよく、実施の形態に応じて適宜選択されてよい。一例では、識別器５９には、ニューラルネットワークが採用されてよい。識別器５９は、ロードマップ構築モデル５に与えられる各種情報の入力を更に受け付けるように構成されてもよい。すなわち、敵対的学習において、ロードマップ構築モデル５に与える情報（訓練データ）の少なくとも一部が、識別器５９にも入力されてよい。

敵対的学習は、第１訓練ステップ及び第２訓練ステップを含むように構成される。第１訓練ステップは、ロードマップ構築モデル５による次のタイムステップにおける候補状態の推定結果及び正解データを入力データとして使用し、入力データの由来を識別するように識別器５９を訓練することにより構成される。候補状態の推定結果は、各データセット３２の第１タイムステップにおける状態３２１を示す情報等により構成される訓練データをロードマップ構築モデル５に与えて、ロードマップ構築モデル５の演算処理を実行することで得られる。正解データは、各データセット３２の第２タイムステップにおける状態３２３を示す情報により構成される。第２訓練ステップは、ロードマップ構築モデル５による次のタイムステップにおける候補状態の推定結果を識別器５９に入力したときの識別器５９の識別性能が低下するようにロードマップ構築モデル５を訓練することにより構成される。なお、図１５では、正解データが由来であることを「真」と表現し、ロードマップ構築モデル５による推定結果が由来であることを「偽」と表現している。各サンプルの由来の表現方法は、適宜変更されてよい。

訓練処理の一例として、制御部１１は、初期設定の処理により、ロードマップ構築モデル５及び識別器５９を用意する。制御部１１は、学習データ３から訓練データ及び正解データを用意する。訓練データの構成は、上記第１エンコーダＥ１に与える訓練データと同様であってよい。すなわち、第１処理モジュール５１に与える訓練データは、学習用対象エージェントＳＡのゴール状態３１Ａ、各データセット３２Ａの第１タイムステップの状態３２１Ａ、訓練フラグ３２５Ａ及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３Ａにより構成されてよい。第２処理モジュール５２に与える訓練データは、学習用他エージェントＳＢのゴール状態３１Ｂ、各データセット３２Ｂの第１タイムステップの状態３２１Ｂ及び訓練用のCost-to-go特徴、並びに訓練用属性情報３３Ｂにより構成されてよい。第３処理モジュール５３に与える訓練データは、訓練用環境情報３５により構成されてよい。正解データは、学習用対象エージェントＳＡの各データセット３２Ａの第２タイムステップの状態３２３Ａにより構成されてよい。

制御部１１は、訓練データの各サンプルをロードマップ構築モデル５に入力し、ロードマップ構築モデル５の演算処理を実行する。すなわち、制御部１１は、訓練データの各サンプルを各処理モジュール５１－５３に与えて、各処理モジュール５１－５３の演算処理を実行することで、各処理モジュール５１－５３から特徴情報を取得する。制御部１１は、取得された特徴情報及び乱数ベクトルを推定モジュール５５に与えて、推定モジュール５５の演算処理を実行する。この演算処理により、制御部１１は、次のタイムステップにおける候補状態を推定した結果の各サンプルをロードマップ構築モデル５から取得する。

制御部１１は、推定結果及び正解データの各サンプルを識別器５９に入力し、識別器５９の演算処理を実行することにより、入力された各サンプルの由来を識別した結果を識別器５９から取得することができる。制御部１１は、この識別結果と識別の真値（真／偽）との間の誤差が小さくなるように、識別器５９の演算パラメータの値を調整する。演算パラメータの値を調整する方法は、機械学習モデルの種類に応じて適宜選択されてよい。一例として、ニューラルネットワークを識別器５９の構成に採用する場合、誤差逆伝播法により、識別器５９の演算パラメータの値は調整されてよい。識別器５９の演算パラメータの調整方法には、公知の最適化方法が採用されてよい。これにより、入力されるサンプルの由来を識別する能力を獲得するように識別器５９を訓練することができる。

また、制御部１１は、訓練データの各サンプルをロードマップ構築モデル５に入力し、ロードマップ構築モデル５の演算処理を実行する。この演算処理により、制御部１１は、次のタイムステップにおける候補状態を推定した結果の各サンプルをロードマップ構築モデル５から取得する。制御部１１は、推定結果の各サンプルを識別器５９に入力し、識別器５９の演算処理を実行することにより、入力された各サンプルの由来を識別した結果を識別器５９から取得することができる。制御部１１は、この識別結果が誤る（すなわち、入力されたサンプルの由来を正解データであると誤るほど誤差が小さくなる）ように誤差を算出し、算出される誤差が小さくなるように、ロードマップ構築モデル５の演算パラメータの値を調整する。ロードマップ構築モデル５の演算パラメータの値を調整する方法は、上記実施形態と同様であってよい。これにより、識別器５９の識別性能を低下させる（すなわち、正解データと誤らせる）ような推定結果を生成する能力を獲得するようにロードマップ構築モデル５を訓練することができる。

図１５の一例では、制御部１１は、識別器５９の訓練ステップにおいて、ロードマップ構築モデル５の演算パラメータの値を固定しながら、識別器５９の演算パラメータの値を調整する。一方、制御部１１は、ロードマップ構築モデル５の訓練ステップにおいて、識別器５９の演算パラメータの値を固定しながら、ロードマップ構築モデル５の演算パラメータの値を調整する。制御部１１は、この識別器５９及びロードマップ構築モデル５の訓練処理を交互に繰り返し実行する。これにより、識別器５９の識別性能が向上するのに対応して、ロードマップ構築モデル５は、この識別器５９による識別が失敗するような、すなわち、正解データ（各データセット３２Ａの第２タイムステップの状態３２３Ａ）に近似する推定結果を生成する能力を獲得する。よって、本変形例に係る機械学習方法によっても、上記実施形態と同様に、対象エージェント及び他のエージェントの対象タイムステップにおける候補状態から対象エージェントの次のタイムステップにおける適切な候補状態を推定する能力を獲得した訓練済みのロードマップ構築モデル５を生成することができる。

なお、敵対的学習の方法は、このような例に限定されなくてよい。他の一例では、勾配反転層が、ロードマップ構築モデル５及び識別器５９の間に配置されてよい。勾配反転層は、順伝播の演算の際は値をそのまま通過させ、逆伝播時には値を反転するように構成される。この勾配反転層により、制御部１１は、上記敵対的学習における識別器５９の訓練処理及びロードマップ構築モデル５の訓練処理を一度に実行してよい。

＜４．３＞
上記実施形態において、Cost-to-go特徴が、対象エージェント情報４１及び他エージェント情報４３から省略されてよい。これに応じて、Cost-to-go特徴を取得する処理が省略されてよい。Cost-to-go特徴に関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。訓練用のCost-to-go特徴が、学習データ３から省略されてよい。Cost-to-go特徴に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、方向フラグに関する情報が、対象エージェント情報４１から省略されてよい。これに応じて、遷移フラグを取得する処理が省略されてよい。方向フラグに関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。訓練フラグ３２５が、学習データ３から省略されてよい。訓練フラグ３２５に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、対象エージェントの属性情報が、対象エージェント情報４１から省略されてよい。これに応じて、対象エージェントの属性情報を取得する処理が省略されてよい。対象エージェントの属性情報に関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。学習用対象エージェントに関して、訓練用属性情報３３が、学習データ３から省略されてよい。学習用対象エージェントの訓練用属性情報３３に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、他のエージェントの属性情報が、他エージェント情報４３から省略されてよい。これに応じて、他のエージェントの属性情報を取得する処理が省略されてよい。他のエージェントの属性情報に関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。学習用他エージェントに関して、訓練用属性情報３３が、学習データ３から省略されてよい。学習用他エージェントの訓練用属性情報３３に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、過去タイムステップにおける候補状態に関する情報が、対象エージェント情報４１及び他エージェント情報４３から省略されてよい。これに応じて、過去タイムステップにおける候補状態の情報を取得する処理が省略されてよい。過去タイムステップにおける候補状態に関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。過去タイムステップにおける候補状態の情報が訓練データから省略されてよい。過去タイムステップにおける候補状態に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、第３処理モジュール５３が、ロードマップ構築モデル５から省略されてよい。これに応じて、環境情報４５を取得する処理が省略されてよい。第３処理モジュール５３に関する情報処理が、ロードマップ構築モデル５の情報処理から省略されてよい。訓練用環境情報３５が、学習データ３から省略されてよい。訓練用環境情報３５に関する訓練処理が、ロードマップ構築モデル５の機械学習の処理から省略されてよい。

上記実施形態において、ロードマップ構築モデル５の入出力の形態は適宜変更されてよい。ロードマップ構築モデル５は、対象エージェント情報４１、他エージェント情報４３、及び環境情報４５以外の他の情報の入力を更に受け付けるように構成されてよい。ロードマップ構築モデル５は、対象エージェントの次のタイムステップにおける候補状態の推定結果以外の他の情報を更に出力するように構成されてよい。

§５ 実施例
本発明の有効性を検証するために、以下の実施例及び比較例に係る手法を構成した。ただし、本発明は、以下の実施例に限定されるものではない。

（問題設定）
・問題：２１～３０個のエージェントのスタート位置からゴール位置までの最短の移動経路を探索する
・環境：２次元平面（［０，１］²）
・連続状態空間：位置を示す連続空間（状態＝位置）
・エージェント
－形状：円形
－大きさ（半径）：環境のサイズ×１／３２×倍率、倍率は｛１，１．２５，１．５｝からランダムに決定
－最大速度：環境のサイズ×１／６４×倍率、倍率は｛１，１．２５，１．５｝からランダムに決定
－数：２１～３０の間でランダムに決定
－スタート位置／ゴール位置：ランダムに決定
・障害物
－形状：円形
－大きさ（半径）：環境サイズ×倍率、倍率は０．０５～０．０８の間でランダムに決定
－位置：ランダムに決定

まず、以上の問題設定により、１１００種類の経路計画問題のインスタンスを作成した。そのうち１０００種類のインスタンスは、実施例に係るロードマップ構築モデルの学習データとして使用した。ランダムサンプリングによりロードマップを構築し、得られたロードマップを用いて、prioritized planning（参考文献：David Silver, "Cooperative Pathfinding", Proceedings of the Artificial Intelligence for Interactive Digital Entertainment Conference (AIIDE) (2005), 117－122.）を行うことで、１０００種類のインスタンスにおける各エージェントの正解経路を得た（すなわち、後述する比較例と同様の手法で、各インスタンスにおける各エージェントの正解経路を得た）。一方、残りの１００種類のインスタンスは、実施例及び比較例それぞれに対する評価データとして使用した。

＜実施例＞
実施例では、上記実施形態（図２Ａ）と同様の構成を有するロードマップ構築モデルを生成した。ロードマップ構築モデル及び入力情報（対象エージェント情報、他エージェント情報、環境情報）の条件は、以下に示す。上記１０００種類のインスタンスから学習データを得て、図７の方法により機械学習を実施することで、訓練済みのロードマップ構築モデルを生成した。機械学習の最適化アルゴリズムにはＡｄａｍ（学習率＝０．００１）を採用し、バッチサイズは５０、エポック数は１０００に設定した。評価データに対する損失が最小となる訓練済みモデルを評価に用いた。

（ロードマップ構築モデルの条件）
・エンコーダ（第１処理モジュール－第３処理モジュール）
－構成：全結合層->バッチ正規化->ＲｅＬＵ->全結合層->バッチ正規化->ＲｅＬＵ
－出力（特徴情報）の次元：６４次元
・推定モジュール
－構成：全結合層->バッチ正規化->ＲｅＬＵ->全結合層->バッチ正規化->ＲｅＬＵ
－出力（推定結果）の次元：３次元、対象タイムステップの候補位置から次のタイムステップの候補位置への距離（１次元）及び方向（単位ベクトルで表現、２次元）
（入力情報の条件）
・対象タイムステップにおける候補状態及びゴール状態：対象タイムステップにおける候補位置からゴール位置への距離及び方向を２次元の単位ベクトルで表現
・過去タイムステップにおける候補状態：１タイムステップ前の候補位置から対象タイムステップにおける候補位置への距離及び方向を２次元の単位ベクトルで表現
・障害物に関する情報：環境を１６０×１６０のグリッドで表現した上で、対象タイムステップにおける候補位置の周囲１９×１９マスにおける障害物の有無を０／１で表現したバイナリ特徴ベクトル
・Cost-to-go特徴：対象タイムステップの候補位置の周囲１９×１９マスの各地点についてゴール状態に近付くか否かを０／１で表現したバイナリ特徴ベクトル
・方向フラグ：次のタイムステップにおける候補位置への方向が「左（ゴール方向からみて３０度より左）」「正面（ゴール方向の左右３０度の範囲）」及び「右（ゴール方向からみて３０度より右）」のいずれであるかを、［１，０，０］，［０，１，０］及び［０，０，１］という３次元ベクトルで表現した
・属性情報は省略
・他のエージェント：対象タイムステップにおいて、対象エージェントの最も近傍に位置するエージェントから５番目に近傍に位置するエージェントまでの５つのエージェント
・第２処理モジュールの処理方法：図２Ｂに示す方法を採用して、各エージェントの情報を統合した

次に、上記１００種類のインスタンス（評価データ）それぞれについて、生成された訓練済みのロードマップ構築モデルを使用して、各エージェントに対するロードマップを構築した。ロードマップ構築の際には、タイムステップｔにおいて、以下の式２の確率で、訓練済みのロードマップ構築モデルを使用せず、対象タイムステップにおける候補位置からランダムに移動した位置にノード（次のタイムステップにおける候補位置）を配置した。

Ｔ_maxは、最大タイムステップ数（６４に設定）を示し、Ｔ_makespanは、今回の推定処理までのロードマップ構築の過程で得られた経路長の最大値を示す。

そして、各インスタンスについて、エージェント毎に得られたロードマップ上で、各エージェントの最短経路を探索した。経路探索法には、prioritized planningを採用した。

＜比較例＞
一方、比較例では、上記１００種類のインスタンス（評価データ）それぞれについて、エージェント毎に５０００個のノードをランダムに配置することで、エージェント毎のロードマップを構築した。そして、各インスタンスについて、得られたロードマップ上で、各エージェントの最短経路を探索した。経路探索法には、実施例と同様の方法（prioritized planning）を採用した。

＜結果＞
図１６Ａは、実施例に係る手法によりあるエージェントに対して構築されたロードマップ及び経路探索の結果を示す。図１６Ｂは、比較例に係る手法によりあるエージェントに対して構築されたロードマップ及び経路探索の結果を示す。図１７は、あるインスタンス（評価データ）について、実施例に係る手法により得られた各エージェントの経路計画結果を示す。以下の表１は、１００種類のインスタンス（評価データ）に対する実施例及び比較例に係る手法のパフォーマンス結果を示す。

なお、実施例及び比較例による経路計画には、ＣＰＵ(intel Core i7-7800)及びＲＡＭ（３２ＧＢ）を備える市販のＰＣ（ＧＰＵの利用はなし）を利用した。評価データに対する各部分の処理時間は、当該ＰＣを使用して各部分の処理を開始してから終了するまでにかかった時間を計測することにより得た。

図１７に一例を示すとおり、実施例に係る経路計画方法により、各エージェントの経路計画を適切に行うことができた。この得られた経路計画に関して、表１に示すとおり、実施例では、成功率及び得られる経路が最適か否かの点に関して、比較例とほぼ同等の性能であった。一方で、図１６Ａ及び図１６Ｂに一例を示すとおり、実施例では、比較例と比べて、ロードマップのノードを配置する範囲を適切な範囲に絞ることができた。その結果、実施例では、比較例と比べて、経路探索にかかる時間を大幅に削減することができた。これらの結果から、本発明によれば、連続状態空間上でマルチエージェントの経路計画問題を解く際に、エージェントに対してより最適な経路を発見できる可能性を高めると共に、探索にかかるコストの低減が可能であることを検証することができた。

１…モデル生成装置、
１１…制御部、１２…記憶部、１３…通信インタフェース、
１４…入力装置、１５…出力装置、１６…ドライブ、
８１…モデル生成プログラム、９１…記憶媒体、
１１１…データ取得部、１１２…学習処理部、
１１３…保存処理部、
１２５…学習結果データ、
２…経路計画システム、
２１…制御部、２２…記憶部、２３…通信インタフェース、
２４…入力装置、２５…出力装置、２６…ドライブ、
８２…経路計画プログラム、９２…記憶媒体、
２１１…情報取得部、２１２…マップ構築部、
２１３…探索部、２１４…出力部、
２２１…対象情報、２２５…ロードマップ、
３…学習データ、
３１…ゴール状態、
３２…データセット、
３２１…第１タイムステップの状態、
３２３…第２タイムステップの状態、
３２５…訓練フラグ、
３３…訓練用属性情報、３５…訓練用環境情報、
４１…対象エージェント情報、４３…他エージェント情報、
４５…環境情報、
５…ロードマップ構築モデル、
５１…第１処理モジュール、５２…第２処理モジュール、
５３…第３処理モジュール、５５…推定モジュール

Claims (14)

1. 複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するように構成される情報取得部と、
   訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するように構成されるマップ構築部と、
   前記エージェント毎に構築された前記ロードマップ上で、前記スタート状態から前記ゴール状態までの前記各エージェントの経路を探索するように構成される探索部と、
   を備える経路計画システムであって、
   前記ロードマップ構築モデルは、
   対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される第１処理モジュール、
   前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される第２処理モジュール、及び
   生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される推定モジュール、
   を備え、
   訓練済みの前記ロードマップ構築モデルは、複数の学習用エージェントの正解経路から得られた学習データを使用した機械学習により生成され、
   前記エージェント毎に前記ロードマップを構築することは、
   前記複数のエージェントのうちのいずれかのエージェントを前記対象エージェントとして取り扱い、
   前記複数のエージェントのうちの残りのエージェントの少なくとも一部を前記他のエージェントとして取り扱い、
   取得された前記対象情報により示される前記いずれかのエージェントのスタート状態を前記対象エージェントの最初の対象タイムステップにおける候補状態として指定して、訓練済みの前記ロードマップ構築モデルにより次のタイムステップにおける１つ以上の候補状態を推定し、かつ
   推定される次のタイムステップにおける１つ以上の候補状態に前記いずれかのエージェントの前記ゴール状態又はその近傍状態が含まれるまで、推定された次のタイムステップにおける１つ以上の候補状態それぞれを新たな対象タイムステップにおける候補状態に指定して、訓練済みの前記ロードマップ構築モデルによる次のタイムステップの候補状態の推定を繰り返す、
   処理を前記複数のエージェントそれぞれを前記対象エージェントに個々に指定して実行することにより構成される、
   経路計画システム。
2. 前記ロードマップ構築モデルは、障害物に関する情報を含む環境情報から第３特徴情報を生成するように構成される第３処理モジュールを更に備え、
   前記推定モジュールは、生成される前記第１特徴情報、前記第２特徴情報及び前記第３特徴情報から、前記次のタイムステップにおける１つ以上の候補状態を推定するように構成され、
   取得される前記対象情報は、前記連続状態空間に存在する前記障害物に関する情報を更に含むように構成され、
   訓練済みの前記ロードマップ構築モデルを使用することは、取得される前記対象情報に含まれる前記情報から前記環境情報を構成し、構成された前記環境情報を前記第３処理モジュールに与えることを含む、
   請求項１に記載の経路計画システム。
3. 前記対象エージェント情報は、前記対象タイムステップよりも前のタイムステップにおける前記対象エージェントの候補状態を更に含むように構成され、
   前記他エージェント情報は、前記対象タイムステップよりも前のタイムステップにおける前記他のエージェントの候補状態を更に含むように構成される、
   請求項１又は２に記載の経路計画システム。
4. 前記対象エージェント情報は、前記対象エージェントの属性を更に含むように構成される、
   請求項１から３のいずれか１項に記載の経路計画システム。
5. 前記対象エージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含む、
   請求項４に記載の経路計画システム。
6. 前記他エージェント情報は、前記他のエージェントの属性を更に含むように構成される、
   請求項１から５のいずれか１項に記載の経路計画システム。
7. 前記他のエージェントの属性は、大きさ、形状、最大速度、及び重量の少なくともいずれかを含む、
   請求項６に記載の経路計画システム。
8. 前記対象エージェント情報は、前記連続状態空間において前記対象エージェントの遷移する方向を示す方向フラグを更に含むように構成される、
   請求項１から７のいずれか１項に記載の経路計画システム。
9. 前記複数のエージェントそれぞれは、自律的に移動するように構成される移動体である、
   請求項１から８のいずれか１項に記載の経路計画システム。
10. コンピュータが、
    複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するステップと、
    訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するステップと、
    前記エージェント毎に構築された前記ロードマップ上で、前記スタート状態から前記ゴール状態までの前記各エージェントの経路を探索するステップと、
    を実行する経路計画方法であって、
    前記ロードマップ構築モデルは、
    対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される第１処理モジュール、
    前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される第２処理モジュール、及び
    生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される推定モジュール、
    を備え、
    訓練済みの前記ロードマップ構築モデルは、複数の学習用エージェントの正解経路から得られた学習データを使用した機械学習により生成され、
    前記エージェント毎に前記ロードマップを構築することは、
    前記複数のエージェントのうちのいずれかのエージェントを前記対象エージェントとして取り扱い、
    前記複数のエージェントのうちの残りのエージェントの少なくとも一部を前記他のエージェントとして取り扱い、
    取得された前記対象情報により示される前記いずれかのエージェントのスタート状態を前記対象エージェントの最初の対象タイムステップにおける候補状態として指定して、訓練済みの前記ロードマップ構築モデルにより次のタイムステップにおける１つ以上の候補状態を推定し、かつ
    推定される次のタイムステップにおける１つ以上の候補状態に前記いずれかのエージェントの前記ゴール状態又はその近傍状態が含まれるまで、推定された次のタイムステップにおける１つ以上の候補状態それぞれを新たな対象タイムステップにおける候補状態に指定して、訓練済みの前記ロードマップ構築モデルによる次のタイムステップの候補状態の推定を繰り返す、
    処理を前記複数のエージェントそれぞれを前記対象エージェントに個々に指定して実行することにより構成される、
    経路計画方法。
11. 複数のエージェントそれぞれの連続状態空間におけるスタート状態及びゴール状態を含む対象情報を取得するように構成される情報取得部と、
    訓練済みのロードマップ構築モデルを使用して、取得された前記対象情報から、前記エージェント毎にロードマップを構築するように構成されるマップ構築部と、
    を備えるロードマップ構築装置であって、
    前記ロードマップ構築モデルは、
    対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される第１処理モジュール、
    前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される第２処理モジュール、及び
    生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される推定モジュール、
    を備え、
    訓練済みの前記ロードマップ構築モデルは、複数の学習用エージェントの正解経路から得られた学習データを使用した機械学習により生成され、
    前記エージェント毎に前記ロードマップを構築することは、
    前記複数のエージェントのうちのいずれかのエージェントを前記対象エージェントとして取り扱い、
    前記複数のエージェントのうちの残りのエージェントの少なくとも一部を前記他のエージェントとして取り扱い、
    取得された前記対象情報により示される前記いずれかのエージェントのスタート状態を前記対象エージェントの最初の対象タイムステップにおける候補状態として指定して、訓練済みの前記ロードマップ構築モデルにより次のタイムステップにおける１つ以上の候補状態を推定し、かつ
    推定される次のタイムステップにおける１つ以上の候補状態に前記いずれかのエージェントの前記ゴール状態又はその近傍状態が含まれるまで、推定された次のタイムステップにおける１つ以上の候補状態それぞれを新たな対象タイムステップにおける候補状態に指定して、訓練済みの前記ロードマップ構築モデルによる次のタイムステップの候補状態の推定を繰り返す、
    処理を前記複数のエージェントそれぞれを前記対象エージェントに個々に指定して実行することにより構成される、
    ロードマップ構築装置。
12. 複数の学習用エージェントの正解経路から生成された学習データを取得するように構成されたデータ取得部と、
    取得された学習データを使用して、ロードマップ構築モデルの機械学習を実施するように構成される学習処理部と、
    を備えるモデル生成装置であって、
    前記ロードマップ構築モデルは、
    連続状態空間における対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される第１処理モジュール、
    前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される第２処理モジュール、及び
    生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される推定モジュール、
    を備え、
    前記学習データは、前記各学習用エージェントの前記正解経路におけるゴール状態及び複数のデータセットを含み、
    前記複数のデータセットそれぞれは、前記各学習用エージェントの第１タイムステップにおける状態及び第２タイムステップにおける状態の組み合わせにより構成され、
    前記第２タイムステップは、前記第１タイムステップの次のタイムステップであり、
    前記ロードマップ構築モデルの機械学習は、
    前記複数の学習用エージェントのうちのいずれかの学習用エージェントを前記対象エージェントとして取り扱い、
    前記複数の学習用エージェントのうちの残りの学習用エージェントの少なくとも一部を前記他のエージェントとして取り扱い、及び
    前記各データセットについて、前記いずれかの学習用エージェントの前記第１タイムステップにおける状態を前記対象エージェントの前記対象タイムステップにおける候補状態として前記第１処理モジュールに与え、前記残りの学習用エージェントの少なくとも一部の前記第１タイムステップにおける状態を前記他のエージェントの前記対象タイムステップにおける候補状態として前記第２処理モジュールに与えることで、前記推定モジュールにより推定される前記対象エージェントの次のタイムステップにおける候補状態が、前記いずれかの学習用エージェントの前記第２タイムステップにおける状態に適合するように、前記ロードマップ構築モデルを訓練すること、
    により構成される、
    モデル生成装置。
13. 前記対象エージェント情報は、前記連続状態空間において前記対象エージェントの遷移する方向を示す方向フラグを更に含むように構成され、
    前記各データセットは、前記連続状態空間における前記第１タイムステップの状態から前記第２タイムステップの状態の方向を示す訓練フラグを更に含むように構成され、
    前記ロードマップ構築モデルの機械学習は、前記各データセットについて、前記対象エージェントの次のタイムステップにおける候補状態を推定する際に、前記いずれかの学習用エージェントの前記訓練フラグを前記対象エージェントの方向フラグとして前記第１処理モジュールに与えることを含む、
    請求項１２に記載のモデル生成装置。
14. コンピュータが、
    複数の学習用エージェントの正解経路から生成された学習データを取得するステップと、
    取得された学習データを使用して、ロードマップ構築モデルの機械学習を実施するステップと、
    を実行するモデル生成方法であって、
    前記ロードマップ構築モデルは、
    連続状態空間における対象エージェントのゴール状態及び対象タイムステップにおける候補状態を含む対象エージェント情報から第１特徴情報を生成するように構成される第１処理モジュール、
    前記対象エージェント以外の他のエージェントのゴール状態及び前記対象タイムステップにおける候補状態を含む他エージェント情報から第２特徴情報を生成するように構成される第２処理モジュール、及び
    生成される前記第１特徴情報及び前記第２特徴情報から、前記対象エージェントの前記対象タイムステップの次のタイムステップにおける１つ以上の候補状態を推定するように構成される推定モジュール、
    を備え、
    前記学習データは、前記各学習用エージェントの前記正解経路におけるゴール状態及び複数のデータセットを含み、
    前記複数のデータセットそれぞれは、前記各学習用エージェントの第１タイムステップにおける状態及び第２タイムステップにおける状態の組み合わせにより構成され、
    前記第２タイムステップは、前記第１タイムステップの次のタイムステップであり、
    前記ロードマップ構築モデルの機械学習は、
    前記複数の学習用エージェントのうちのいずれかの学習用エージェントを前記対象エージェントとして取り扱い、
    前記複数の学習用エージェントのうちの残りの学習用エージェントの少なくとも一部を前記他のエージェントとして取り扱い、及び
    前記各データセットについて、前記いずれかの学習用エージェントの前記第１タイムステップにおける状態を前記対象エージェントの前記対象タイムステップにおける候補状態として前記第１処理モジュールに与え、前記残りの学習用エージェントの少なくとも一部の前記第１タイムステップにおける状態を前記他のエージェントの前記対象タイムステップにおける候補状態として前記第２処理モジュールに与えることで、前記推定モジュールにより推定される前記対象エージェントの次のタイムステップにおける候補状態が、前記いずれかの学習用エージェントの前記第２タイムステップにおける状態に適合するように、前記ロードマップ構築モデルを訓練すること、
    により構成される、
    モデル生成方法。