JP7394853B2 - 動的物体を有する環境における運動計画を促進する装置、方法及び物品 - Google Patents

Description

本開示は、概して、運動計画に関し、特にエージェント、例えば動的物体を有する環境における自律車両又は他のロボットエージェントの運動計画を促進するシステム及び方法に関する。

運動計画は、ロボット工学における基本的な問題である。運動計画は、自律車両の運動の制御又は他のタイプのロボット若しくはロボットの部分（例えば、付属物）の運動の制御に利用できる。例えば、運動計画は、自律車両又はロボット若しくはその部分が第１の構成状態（例えば、開始姿勢）からゴール状態（例えば、終了姿勢）まで、典型的には、動作環境中の障害物とも衝突することなく、又は、動作環境中の物体と衝突する確率が低い状態で辿ることができるパスを特定する。しかしながら、幾つかの場合、物体の検査、物体からの情報収集、物体との情報交換、又は、例えばゲーム等での物体との衝突等の、動作環境中の物体との相互作用が望まれ得る。通常、運動計画の作成に関わる４つの主成分がある。その４つの主成分は、知覚、ロードマップ（本明細書では運動計画グラフとも呼ばれる）構築、衝突検出、及び、経路検索（ｐａｔｈ ｓｅａｒｃｈ）である。それぞれは、静的物体及び特に環境内を移動する動的物体を含む、自律車両又はロボットを取り巻く環境内で解決すべき問題を呈する。動的障害物の将来の移動が未知又は不確かであることもあり得る。そのような動的物体は、自律車両又は他のタイプのロボットのゴールとは反対に移動中であり得る。したがって、自律車両又は他のタイプのロボットにとって、ゴール状態に到達するようこのような物体との衝突や妨害を回避するために、それらの変化にリアルタイムに追いつくよう運動計画を実行することは有利である。

運動計画システムは、一次エージェント（例えば、自律車両、他のタイプのロボット）が動作する環境を表す知覚情報を受信する。運動計画システムは、他のエージェントが、一次エージェントがとる行動に対して及び互いに対してどのように反応し得るかを含め、環境中の他のエージェントによる行動を考慮に入れて、運動計画の実行に先立ち、一次エージェントの計画グラフの衝突評価を実行する。

計画グラフの各エッジは、一次エージェントの構成空間におけるある状態から別の状態への一次エージェントの遷移を表し、それに関連付けられた固有の又は動作コストを有する。固有の又は動作コストは、例えば、燃料、エネルギー使用及び／又は時間等の一次エージェントとの種々の動作パラメータを反映し得る。各エッジは、それぞれの固有の又は動作コストに対応する初期重みを有する。

一次エージェントの状態遷移を表す計画グラフ上のエッジについて、システムは、衝突評価の少なくとも一部に基づいて、環境中の動的物体との衝突確率を特定し、次に動的物体との衝突確率に基づいてエッジの初期重みを変更又は調整する。例えば、システムは、コスト関数を各エッジに適用して、そのエッジの初期重み（すなわち固有のコストに対応する重み）に基づいて数学的演算を実行して、変更後重みを取得する。これは、確率衝突に基づいて割り当てられた初期重みに追加の重みを追加するか、衝突確率係数で割り当てられた初期重みを乗算するか、又は衝突確率及び固有のコストに対応する初期重みが関わる何らかの他の関数若しくは公式を適用することにより行われる。本明細書に記載されるように、衝突評価は、有利には、一次エージェントの行動に対する環境中の他のエージェントの反応及び互いに対する反応を考慮に入れる。衝突確率に加えて、システムは、物体の相対重要度を反映したコスト等、衝突確率から独立した物体固有のコストを割り当ててもよい。例えば、人間との衝突するコストには、木と衝突するコストよりもはるかに高い値を割り当ててもよい。

例えば、一次エージェントのゴールが環境中の動的物体との衝突回避である場合、システムは、エッジが１つ又は複数の動的物体との比較的高い衝突確率を有するとき、比較的大きい正の値を有する重みを計画グラフの当該エッジに割り当てる。システムは、エッジが環境中の１つ又は複数の動的物体との比較的低い衝突確率を有する場合、比較的小さい正の値を有する重みを計画グラフの当該エッジに割り当てる。システムは、次に、一次エージェントが動作する環境中の１つ又は複数の動的物体との衝突確率が比較的低い、結果として生成された計画グラフ中のパスを識別する最適化を実行する。システムは、次に、任意に、この最適化の少なくとも一部に基づいて、一次エージェントのアクチュエータシステムに、そのような動的物体との衝突確率が比較的低い運動計画を実施させる。

また、例えば、一次エージェントのゴールが環境中の動的物体との衝突である場合、システムは、エッジが１つ又は複数の動的物体との比較的高い衝突確率を有するとき、比較的低い正の値を有する重みを計画グラフの当該エッジに割り当てる一方、エッジが環境中の１つ又は複数の動的物体との比較的低い衝突確率を有するとき、比較的高い正の値を有する重みを計画グラフの当該エッジに割り当てる。システムは、次に、一次エージェントが動作する環境中の１つ又は複数の動的物体と衝突する可能性が比較的高い、結果として生成された計画グラフ中のパスを識別する最適化を実行する。システムは、次に、任意に、この最適化の少なくとも一部に基づいて、一次エージェントのアクチュエータシステムに、そのような動的物体と衝突する可能性が比較的高い運動計画を実施させる。

開示される実装形態では、格子中の各エッジが「衝突なし」と初期化される計算戦略がある。他のエージェント、例えば動的物体の意図がサンプリングされる。例えば、エージェントの意図を、単純な軌道ではなく、潜在ポリシー又はゴールのモデリングとして扱う各エージェントの挙動モデルを作成する。潜在ポリシー又はゴールは、エージェントが他のエージェントの軌道に対してどのように反応するかを決定するためにサンプリングすることができる形態であってもよい。各エージェントの意図は、軌道ｔを提供し、軌道の集合Ｓを生成する。Ｓ中の各サンプル特徴軌道ｔについて、ｔと衝突する格子中のエッジが特定され（これは、並列に行われてもよい）、エッジのコストは、衝突確率を反映するように増分される（例えば、軌道の１０％がエッジＥと衝突する場合、Ｅの衝突確率は、１０％である）。（確率的衝突のコスト項を含む１つ又は複数のコスト関数の適用後に）最小コスト経路検索が実行されて、計画を見つける。エッジのコストは、エッジの衝突確率の線形関数である必要はない。

一次エージェントのゴールが特定の動的物体との衝突回避である場合、運動プランナは、一次エージェントが動作する環境中のそのような動的物体と衝突する可能性が比較的低い一次エージェントの運動計画（例えば、移動ルート）を提供する、結果として生成された計画グラフ中のパスを識別する最適化を実行する。システムは、次に、この最適化の少なくとも一部に基づいて、一次エージェント（例えば、自律車両）のアクチュエータシステムに、１つ又は複数の物体と衝突する可能性が比較的低い運動計画を実施させる。

一次エージェントのゴールが動的物体との衝突である場合、運動プランナは、一次エージェントが動作する環境中のそのような動的物体と衝突する可能性が比較的高い一次エージェントの運動計画（例えば、移動ルート）を提供する、結果として生成された計画グラフ中のパスを識別する最適化を実行する。システムは、次に、この最適化の少なくとも一部に基づいて、一次エージェント（例えば、自律車両）のアクチュエータシステムに、１つ又は複数の物体と衝突する可能性が比較的低い運動計画を実施させる。

計画グラフを介して運動計画を実行するプロセッサベースのシステムにおける動作の運動計画方法が記載され、各計画グラフは、複数のノード及びエッジをそれぞれ含み、各ノードは、時間と、一次エージェントの状態を特徴付ける変数とを暗黙的又は明示的に表し、一次エージェントは、１つ又は複数の他のエージェントを含む環境中で動作し、各エッジは、ノード対間の遷移を表す。本方法は、第１の計画グラフ中の現在のノードについて、１つ又は複数の他のエージェントの少なくとも１つの実際の又は将来の軌道をそれぞれ表す軌道の集合中の各軌道について、エッジの何れかが軌道と衝突する場合、第１の計画グラフの何れのエッジ軌道と衝突するかを特定することと、コスト関数をエッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することと、第１の計画グラフ中の現在のノードに第１の計画グラフの単一のエッジにより直接結合される第１の計画グラフ中の任意のノードである幾つかの候補ノードのそれぞれについて、現在のノードから直接候補ノードを通過し、その後、第１の計画グラフ内のゴールノードに至る現在のノードから第１の計画グラフ中のゴールノードへの最小コストパスを、対応するパスに沿った候補ノードとゴールノードとの間の幾つかの介在ノードを有するか有しない状態で見つけることと、軌道の集合の軌道に関して、候補ノードのそれぞれの最小コストパスを見つけた後、候補ノードのそれぞれについて、全ての軌道にわたる候補ノードに対して各最小コストパスに関連付けられた最小コストの少なくとも一部に基づいて値を計算することと、計算された値の少なくとも一部に基づいて、候補ノードの１つを選択することと、を含むものとして要約できる。

コスト関数をエッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することは、少なくとも１つの軌道と衝突すると特定されたエッジについて、当該エッジのコストを比較的高い大きさに増大させて、特定された衝突を反映させることを含み、比較的高い大きさは、少なくとも１つの他のエッジについて衝突の不在を反映する比較的低い大きさよりも比較的高くできる。

コスト関数をエッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することは、少なくとも１つの軌道と衝突しないと特定されたエッジについて、当該エッジのコストを比較的高い大きさに増大させて、特定された衝突の不在を反映させることを含み、比較的高い大きさは、少なくとも１つの他のエッジについて衝突を反映する比較的低い大きさよりも比較的高くできる。

本方法は、環境中の他のエージェントの少なくとも１つについて、サンプリングして他のエージェントの将来の軌道を特定することと、他のエージェントの特定された実際の又は将来の軌道から軌道の集合を形成することと、を更に含むことができる。

本方法は、第１の計画グラフの単一のエッジにより第１の計画グラフ中の現在のノードに直接結合される第１の計画グラフ中の任意のノードである候補ノードに基づいて、第１の計画グラフの他のノードから第１の計画グラフ中の候補ノードを選択することを更に含み得る。

候補ノードのそれぞれについて、全ての軌道にわたる候補ノードに対して各最小コストパスに関連付けられたコストの少なくとも一部に基づいて値を計算することは、現在のノードから、候補ノードと、存在する場合には介在ノードの全てを経由して前記ゴールノードまで延びる各最小コストパスに関連づけられたコストの平均値を計算することを含むことができる。

計算された値の少なくとも一部に基づいて候補ノードの１つを選択することは、計算された値の全てのうちで最小の値を有する候補ノードの１つを選択することを含むことができる。

本方法は、選択された１つの候補ノードに基づいて、一次エージェントの軌道を更新することを更に含むことができる。

本方法は、コスト関数をエッジに適用して特定された衝突を反映する前に、第１の計画グラフを初期化することを更に含むことができる。第１の計画グラフを初期化することは、第１の計画グラフ中の各エッジについて、環境中の幾つかの静的物体のそれぞれに対するエッジの衝突評価を実行して、存在する場合に、エッジと静的物体との間の衝突を識別することを含むことができる。第１の計画グラフを初期化することは、静的物体の少なくとも１つと衝突すると評価される各エッジについて、コスト関数を当該エッジに適用して評価された衝突を反映するか、又は、第１の計画グラフから当該エッジを削除することを含むことができる。第１の計画グラフを初期化することは、第１の計画グラフ中の各ノードについて、ノードからゴールノードへのコストを計算することと、計算されたコストをそれぞれのノードに論理的に関連付けることと、を含むことができる。

本方法は、候補ノードの選択された１つを第１の計画グラフ中の新しい現在のノードとして割り当てることと、第１の計画グラフ中の新しい現在のノードについて、１つ又は複数の他のエージェントの少なくとも１つの実際の又は将来の軌道を表す軌道の集合中の各軌道について、エッジの何れかが軌道と衝突する場合、第１の計画グラフの何れのエッジが軌道と衝突するかを特定することと、コスト関数をエッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することと、第１の計画グラフ中の新しい現在のノードに第１の計画グラフの単一のエッジにより直接結合された第１の計画グラフ中の任意のノードである第１の計画グラフ中の幾つかの新しい候補ノードのそれぞれについて、第１の計画グラフ内の新しい現在のノードから直接新しい候補ノードを通過し、その後、第１の計画グラフ内のゴールノードに至る新しい現在のノードからゴールノードへの最小コストパスを、対応するパスに沿った新しい候補ノードとゴールノードとの間の幾つかの介在ノードを有するか有しない状態で見つけることと、軌道の集合の軌道に関して、新しい候補ノードのそれぞれの最小コストパスを見つけた後、新しい候補ノードのそれぞれについて、全ての軌道にわたる新しい候補ノードに対して各最小コストパスに関連付けられたコストの少なくとも一部に基づいて値を計算することと、計算された値の少なくとも一部に基づいて、新しい候補ノードの１つを選択することと、を含むことができる。

計画グラフを介して運動計画を実行するプロセッサベースのシステムが記載され、各計画グラフは、複数のノード及びエッジを含み、各ノードは、時間と、一次エージェントの状態を特徴付ける変数とを暗黙的又は明示的に表し、一次エージェントは、１つ又は複数の他のエージェントを含む環境中で動作し、各エッジは、ノードのそれぞれの対間の遷移を表す。本システムは、少なくとも１つのプロセッサと、プロセッサが実行可能な命令又はデータの少なくとも１つを記憶する少なくとも１つの非一時的プロセッサ可読媒体と、を含むものとして要約でき、プロセッサが実行可能な命令又はデータの少なくとも１つは、少なくとも１つのプロセッサによって実行されると、少なくとも１つのプロセッサに、先に要約された方法の何れかを実行させる。

状態を表すノードと、状態間の遷移を表すエッジと、を有するグラフを利用する運動計画システムにおける動作の方法が記載される。本方法は、少なくとも１つのプロセッサが、第１のグラフ中の現在のノードに対して利用可能な次のノードのそれぞれについて、現在のノードから次のノードを経由してゴールノードに到達するための代表コストを算出することと、少なくとも１つのプロセッサが、次のノードのそれぞれについて計算された代表コストに基づいて、次のノードを選択することと、少なくとも１つのプロセッサが、選択された次のノードの少なくとも一部に基づいて、移動の命令をすることと、を含み、代表コストが、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動に基づいて評価された環境中の１つ又は複数のエージェントとの衝突の確率に鑑みて、次のノードを経由した現在のノードからゴールノードまでの利用可能なパスのそれぞれに関連付けられた代表コストを反映しており、エージェントが、位置、速度、軌道、移動パス、又は形状のうちの１つ又は複数を経時変化させることができるものとして要約できる。

次のノードを経由して現在のノードからゴールノードに到達するための代表コストを計算することは、次のノードを経由した現在のノードとゴールノードとの間の将来のパスについて、将来のパスに沿った現在のノードとゴールノードとの間の各エッジについて、代表コストを特定することと、各エッジに対して特定した代表コストを、将来のパスに沿った現在のノードとゴールノードとの間の各エッジに割り当てることと、割り当てられ特定された代表コストの少なくとも一部に基づいて、次のノードを経由した現在のノードとゴールノードとの間の将来のパスからの次のノードのための最小コストパスを特定することと、特定された最小コストパスを表す値を次のノードに割り当てることと、を含むことができる。

割り当てられ特定された代表コストの一部に基づいて、次のノードを経由した現在のノードとゴールノードとの間の将来のパスからの次のノードの最小コストパスを特定することは、現在のノードから次のノードに移動するコストを含む最小コストパスを特定することを含むことができる。

将来のパスに沿った現在のノードとゴールノードとの間の各エッジについて代表コストを特定することは、将来のパスに沿った現在のノードとゴールノードとの間の各エッジについて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することを含むことができる。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、将来のパスに沿った次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す確率関数をサンプリングすることを含むことができる。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することは、現在のノードへの将来のパスに沿った次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す確率関数をサンプリングすることを含むことができ、現在のノードは、衝突のリスクの評価中に到達される将来のパスに沿った更なるノードである。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、エージェントのそれぞれについて、エージェントの非決定的挙動を表す確率関数を繰り返しサンプリングすることを含むことができる。それぞれのエージェントの非決定的挙動を表す確率関数を繰り返しサンプリングすることは、複数の繰り返しについて確率関数を繰り返しサンプリングすることを含むことができ、繰り返しの総数は、命令を発生させなくてはならなくなる前に利用可能な時間量の少なくとも一部に基づいている。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することは、エージェントのそれぞれについて、将来のパスに沿った次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す確率関数を繰り返しサンプリングすることを含むことができる。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することは、エージェントのそれぞれについて、現在のノードへの将来のパスに沿った次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す確率関数を繰り返しサンプリングすることを含むことができ、現在のノードは、衝突のリスクの評価中に到達される、将来のパスに沿った更なるノードである。衝突のリスクを評価することは、将来のパスの移動のシミュレーションを含むことができる。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することは、専用リスク評価ハードウェアが、少なくとも環境中の１つ又は複数のエージェントのそれぞれの確率的に特定された軌道に基づいて、衝突のリスクを評価することを含むことができ、代表コストは、評価された衝突のリスクの少なくとも一部に基づいている。

環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することは、環境中のエージェントの少なくとも二次エージェントの非決定的挙動を表す１つ又は複数の確率関数に基づいて、環境中の１つ又は複数のエージェントとの衝突のリスクを評価することを含むことができ、エージェントの一次エージェントは、運動計画が実行されているエージェントである。

本方法は、次のノードを経由して現在のノードからゴールノードに到達するための代表コストを計算する前に第１のグラフを初期化することを更に含むことができる。第１のグラフを初期化することは、静的衝突評価を実行して、環境中の１つ又は複数の静的物体との衝突を識別することと、第１のグラフ中の各ノードについて、各ノードからゴールノードに到達するためのコストを計算することと、第１のグラフ中の各ノードについて、ゴールノードに到達するための計算されたコストを各ノードに論理的に関連付けることと、を含むことができる。

状態を表すノードと状態間の遷移を表すエッジとを有するグラフを利用する運動計画を実行するプロセッサベースのシステムが記載される。本システムは、少なくとも１つのプロセッサと、プロセッサが実行可能な命令又はデータの少なくとも１つを記憶する少なくとも１つの非一時的プロセッサ可読媒体とを含むものとして要約でき、プロセッサが実行可能な命令又はデータの少なくとも１つは、少なくとも１つのプロセッサによって実行されると、少なくとも１つのプロセッサに、上記方法の何れかを実行させる。

状態を表すノードと、状態間の遷移を表すエッジとを有するグラフを利用して、一次エージェントの運動計画を生成する運動計画システムにおける動作の方法が記載される。本方法は、ステップカウンタＴを開始値に初期化する（Ｔ＝０）ことと、第１のグラフを初期化することと、シミュレーションを実行することとを含むものとして要約でき、シミュレーションは、第１のグラフ中の現在のノードＮにおいて開始して、且つ第１のグラフ中のゴールノードＧではない間、１つ又は複数のサンプリングの繰り返しについて、環境中の１つ又は複数の二次エージェントの各二次エージェントについて、ステップカウンタがインクリメントしたとき（Ｔ＋１、すなわち、次のステップ）に前記二次エージェントがとる行動を、前記ステップカウンタの開始値から現在値までに一次エージェント及び１つ又は複数の二次エージェントによってとられた行動を表す確率関数からサンプリングすることと、次の行動と衝突する第１のグラフのエッジを特定することと、次の行動と衝突するエッジについて、コスト関数をエッジに適用して、衝突条件の存在を反映することと、現在のノードに直接接続されるノードの集合のうちの第１のグラフ中の各ノードについて、現在のノードに直接接続されるノードを経由し、１つ又は複数の将来のパスを経由して現在のノードからゴールノードまで１つ又は複数のパスを移動するための最小コストパスを表す値を計算することと、別のサンプリングの繰り返しを実行するか否かを決定することと、別のサンプリングの繰り返しを実行しないと決定した場合、現在のノードに直接接続されるノードの集合から、最小コストを有する、ノードの集合のノードの１つを選択することと、ステップカウンタをインクリメントする（Ｔ＝Ｔ＋１）ことと、シミュレーションがゴールノードにおけるものであるか否かを決定することと、シミュレーションがゴールノードにおけるものではない場合、一次エージェントに命令することなく、選択されたノードを新しい現在のノードとして設定し、シミュレーションを継続することと、シミュレーションがゴールノードにおけるものである場合、現在のノードに直接接続されるノードの集合から、最小コストを有するノードを選択することと、最小コストを有する選択されたノードの識別情報を提供して、一次エージェントの移動を命令することとを含む。

前記ステップカウンタがインクリメントしたときに前記二次エージェントがとる行動を、前記ステップカウンタの前記開始値から現在値までに前記一次エージェント及び前記１つ又は複数の二次エージェントによってとられた行動を表す確率関数からサンプリングすることは、ゴールノードへのルートに沿った、現在のノードに直接接続されたノードと各後続ノードとの間の各エッジによって表される一次エージェントによってとられる一連の行動に鑑みて、環境中の１つ又は複数の二次エージェントのそれぞれの非決定的挙動を表す確率関数をサンプリングすることを含み得る。

各エッジによって表される一連の行動に鑑みて、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動を表す確率関数をサンプリングすることは、エージェントのそれぞれについて、エージェントの非決定的挙動を表す確率関数を繰り返しサンプリングすることを含むことができる。

一次エージェントは、一次自律車両とできる。本方法は、一次自律車両が動作する環境を表す知覚情報を受信することと、一次自律車両により生成された運動計画を実施することと、を更に含むことができる。知覚情報を受信することは、環境中の少なくとも１つの動的物体の位置及び軌道を表す知覚情報を受信することを含むことができる。知覚情報を受信することは、運動プランナにおいて知覚情報を受信することを含むことができ、知覚情報は、一次自律車両によって搬送される１つ又は複数のセンサを介して収集され、環境中の少なくとも１つの他の車両の位置又は軌道を表す。

本方法は、物体検出器により、１つ又は複数のセンサを介して収集された知覚情報から、少なくとも環境中の第１の動的物体を識別することを更に含むことができる。

状態を表すノードと、状態間の遷移を表すエッジとを有するグラフを利用して、一次エージェントの運動計画を生成する運動計画システムが記載される。本運動計画システムは、少なくとも１つのプロセッサと、プロセッサにより実行可能な命令を記憶する少なくとも１つの非一時的プロセッサ可読媒体とを含むものとして要約でき、プロセッサにより実行可能な命令は、少なくとも１つのプロセッサによって実行されると、少なくとも１つのプロセッサに、上記方法の何れかを実行させる。

図面中、同一の参照番号は、同様の要素又は動作を識別する。図面中の要素のサイズ及び相対位置は、必ずしも一定の縮尺で描かれているわけではない。例えば、種々の要素の形状及び角度は、一定の縮尺で描かれておらず、これらの要素の幾つかは、任意に拡大され、図面の見やすさを改善するように位置決めされる。更に、描かれる要素の特定の形状は、特定の要素の実際の形状に関するいかなる情報も伝達することを意図せず、単に図面にける認識のし易さのために選ばれている。

一実施形態により一次エージェント（例えば、自律車両、付属物あり又はなしのロボット等）が動作する環境の概略図である。 一実施形態による、図１の環境で動作する一次エージェント（例えば、自律車両、可動付属物あり又はなしのロボット等）に関連するコンピュータシステムの機能ブロック図である。 一実施形態による図２のコンピュータシステムにおける種々の構成要素間のデータフロー例を示すブロック図である。 一実施形態による、一次エージェントのゴールが、一次エージェントから逃れようとしている可能性がある図１の動的物体と衝突する場合の、図１の一次エージェントの運動計画グラフの一例である。 一実施形態による、一次エージェントのゴールが、一次エージェントから逃れようとしている可能性がある図１の動的物体と衝突する場合の、図１の一次エージェントの運動計画グラフの一例及び動的物体と衝突する、一次エージェントの計画グラフにおいて識別されたパスの一例である。 一実施形態による、一次エージェントのゴールが、一次エージェントに近づきつつある図１の動的物体との衝突回避である場合の、図１の一次エージェントの運動計画グラフの一例である。 一実施形態による、一次エージェントのゴールが、一次エージェントに近づきつつある図１の動的物体との衝突回避である場合の、図１の一次エージェントの運動計画グラフの一例及び動的物体との衝突を回避する、一次エージェントの計画グラフにおいて識別されたパスの一例である。 一次エージェント（例えば、自律車両、付属物あり又はなしのロボット等）が動作でき、他のエージェントが既知の軌道を有する環境の概略図である。 一実施形態による、他のエージェントの既知の軌道に基づいて特定されたコストを有する２つの候補ノードのそれぞれを通る最小コストパスの一例を示す、図６の一次エージェントの運動計画グラフの一例である。 一実施形態による、計画グラフを介して一次エージェントのパスを識別する方法を示す流れ図であり、パスは、他のエージェントの既知の軌道を考慮に入れた最小平均コストを有する候補ノードを通る。 一実施形態による、図８Ａの方法における既知の軌道の集合にわたる平均が計算された各候補ノードのコストを計算するのに有用な方法を示す流れ図である。 一実施形態による、一次エージェント（例えば、自律車両、付属物あり又はなしのロボット等）が動作でき、一次エージェント及び他のエージェントが独立した軌道を有する環境の概略図である。 一実施形態による、現在のノードから候補ノードへの第１の最小コストパスに沿った一次エージェントの計画された移動後の、確率的モデルから計算された他のエージェントの軌道に基づいて特定された第１の最小コストパス及び第２の最小コストパスの一例を示す、図９の一次エージェントの運動計画グラフの一例である。 示される一実施形態による、ゴールへの一次エージェントの計画パス及び確率的モデルを使用して特定された他のエージェントのパスを考慮に入れた最小平均コストを有する候補ノードを通る計画グラフを介した一次エージェントのパスを識別する方法を示す流れ図である。 一実施形態による、ゴールへの一次エージェントの計画パス及び確率的モデルを使用して特定された他のエージェントのパスに基づいて各候補ノードの値を計算する、図１１Ａの方法において有用な方法を示す流れ図である。 一実施形態による、確率的モデルに基づいて他のエージェントのサンプリングされた次のステップからのエッジ衝突コストに基づいて、次の時間ステップにおける各候補ノードの値を特定する、図１１Ｂの方法において有用な方法を示す流れ図である。

以下の説明では、種々の開示される実施形態の詳細な理解を提供するために、特定の具体的な詳細が記載される。しかしながら、１又は複数のこれらの具体的な詳細がなくとも、他の方法、構成要素、材料等を用いて実施形態が実施可能であることを当業者は認識するであろう。他の場合、コンピュータシステム、アクチュエータシステム及び／又は通信ネットワークに関連する周知の構造については、実施形態の説明を不必要に曖昧にしないように詳細に示されていないか又は説明されていない。他の場合、知覚データ及び１つ又は複数の物体の立体表現の生成並びに占有グリッドの構築等の周知のコンピュータビジョンの方法及び技法について、実施形態の説明を不必要に曖昧にしないように詳細に説明されていない。

文脈により別段のことが求められる場合を除き、本明細書及びそれに続く特許請求の範囲全体を通して、「含む（ｃｏｍｐｒｉｓｅ）」及び「含む（ｃｏｍｐｒｉｓｅｓ）」及び「含んでいる」等のその変形は、「含むが、限定されない」としてオープンで包含的な意味で解釈されるべきである。

本明細書全体を通した「一実装形態」、「実装形態」、「一実施形態」又は「実施形態」への言及は、その実施形態と併せて説明された特定の特徴、構造又は特性が少なくとも１つの実装形態又は少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書全体を通した種々の箇所における語句「一実装形態」、「実装形態」、「一実施形態において」又は「実施形態において」の出現は、必ずしも全て同じ実装形態又は同じ実施形態を指すわけではない。更に、特定の特徴、構造又は特性は、１つ又は複数の実装形態又は実施形態において任意の適した様式で組み合わせることができる。

本明細書及び添付の特許請求の範囲で使用される場合、単数形「１つの（ａ）」、「１つの（ａｎ）」及び「その」は、文脈により別段のことが明らかに示される場合を除き、複数形を含む。用語「又は」は、一般に、文脈により別段のことが明らかに示される場合を除き、「及び／又は」を含む意味で利用されることにも留意すべきである。

本明細書全体を通した「一次エージェント」又は「１つの一次エージェント」へ言及は、各運動計画が作成又は生成中であるエージェント（例えば、半又は全自律車両、可動付属物あり又はなしのロボット）を意味する。本明細書全体を通した「他のエージェント」、「別のエージェント」、「二次エージェント」又は「１つの二次エージェント」への言及は、各運動計画が作成又は生成中である一次エージェント以外のエージェント（例えば、半又は全自律車両、可動付属物あり又はなしのロボット）を意味する。幾つかの場合、運動計画の他のインスタンスがこれらの他の又は二次エージェントに対して実行されうるが、それらの運動計画は、一次エージェントのものではない。

本明細書に提供される本開示の見出し及び要約書は、便宜上のものに過ぎず、実施形態の範囲又は意味を説明するものではない。

図１は、一実施形態により一次エージェント（例えば、自律車両、可動付属物あり又はなしのロボット等）１０２が動作する動的動作環境１００を示す。簡潔にするために、動的動作環境１００は、本明細書では環境と呼ばれる。自律車両に関して一般に説明されるが、本明細書に記載される種々の実装形態は、ロボット又はその部分、例えば環境をナビゲートするように動作可能なロボット及び／又は１つ若しくは複数の可動付属物を有するロボットに適用可能である。

環境は、一次エージェント（例えば、自律車両）１０２が動作し移動する二次元又は三次元空間を表す。一次エージェント１０２は、自律的若しくは半自律的（すなわち少なくとも部分的に自律的）に動作し、環境１００により表される空間をルート若しくはパスに沿って移動することができる自動車、航空機、船、ドローン若しくは任意の他の車両であるか、又は、別のタイプのロボットである。環境１００は、車両が動作する二次元又は三次元空間であり、図４Ａ～図５Ｂの運動計画グラフに関して以下で参照され、「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願番号ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０（これらは、全体的に参照により本明細書に援用される）に記載されるような車両の「構成空間」（「Ｃ空間」と呼ばれることが多い）と異なる。構成空間は、通常、多次元（すなわち４次元以上）である。図１を参照すると、環境１００は、障害物衝突領域を含むことができる。これらの障害物衝突領域は、静的物体（例えば、建物、木々、石等）又は動的物体（例えば、他の航空若しくは地上ベースの車両、人々、動物、転がっている石、鳥等）に起因し、これらは、まとめて環境１００における「エージェント」又は「他のエージェント」と呼ばれる。例えば、静的物体Ｃ１０８は、環境１００において移動しない物体を表し、環境１００内の同じ空間を同時に占有しようとする場合、車両１０２が静的物体Ｃ１０８に衝突する可能性があるような衝突領域を環境１００にもたらす。種々の実施形態では、図１に示されるよりも少数又は追加の静的物体が存在しうる。

静的物体に加えて、既知／特定の軌道を移動する物体（例えば、落下するブロック、転がっている缶）、意識体（例えば、自転車運転者、歩行者、運転者、パイロット、鳥等）によりコントロールされるもの、及び、他の自律車両又はロボットの場合等の他の自律システムにより制御されるものを表すものなどの、動的物体が存在しうる。これらの動的物体に起因した運動計画についての課題は、非常に高速に運動計画を実行する能力、及び、動的物体がどのように移動するかについての不確さを分析する能力を伴う。車両１０２を取り巻く環境１００は、高速に変化する可能性があり、車両１０２がそれらの変化に追いつくように運動計画を実行することが有利である。例えば、図１に示されるように、エージェント、例えば動的物体Ａ１０４は、現在、車両１０２から離れて軌道１１０に沿って移動中である。しかしながら、車両１０２は、動的物体Ａ１０４の検査、動的物体Ａ１０４からの情報収集、動的物体Ａ１０４との情報交換又はゲームでの動的物体Ａ１０４との衝突等のために、動的物体Ａ１０４の後を辿るか又は妨害することが望ましい場合がある。

逆に、図１に示されるように、動的物体Ｂ１１２は、現在、車両１０２に向かって軌道１０６に沿って移動中である。車両１０２は、衝突することなくゴールに辿り着くか、そのような衝突による破損を回避するか、又は例えばゲームで動的物体Ｂ１１２との接触から逃れる等のために、動的物体Ｂ１１２との衝突を回避するか又は動的物体Ｂ１１２に近づくのを回避することが望ましい場合がある。一実施形態では、車両１０２のゴールは、例えば、動的物体Ｂ１１２が車両１０２と衝突する前に燃料切れになるように、動的物体Ｂ１１２と衝突しない時間を最大にすることである。一実施形態の例での車両１０２のゴールは、現在の時間と、所望の行き先に車両１０２が到達するか若しくは特定のゴールを達成する時間との間、又は、現在の時間と、動的物体Ｂ１１２が燃料切れになるまでの間に、動的物体Ｂ１１２と衝突する確率を最小にすることである。環境１００には、図１に示されるよりも少数又は追加の動的物体が存在しうる。また、環境は、幾つかの場合、車両１０２の範囲に対応する境界を有することがあり、境界は、少なくとも部分的に、現在の燃料又は車両１０２が利用可能なエネルギーに依存しうる。

図１は、代表的な環境１００を示すが、典型的な環境は、他の有人車両及び自律車両に対応する物体並びに種々の他の天然又は人工の静的及び動的物体及び障害物を含め、多くの追加のエージェントを含みうる。本明細書で教示される概念は、示されるよりもエージェントが多い環境でも同様に利用できる。

図２及び以下の記載は、種々の運動計画システム及び方法を実現しうるコンピュータシステム２００の形態の適したコントローラの概説を提供する。

必須ではないが、実施形態の多くは、コンピュータ又はプロセッサ可読媒体に記憶され、コンピュータ又はプロセッサによって実行されるプログラムアプリケーションモジュール、オブジェクト又はマクロ等のコンピュータにより実行可能な命令、並びに、衝突評価及び運動計画動作を実行できる専用車両運動計画ハードウェアに一般的に関連して説明される。そのような運動計画動作は、計画グラフのエッジに対して衝突評価を実行すること、衝突確率を特定し設定すること、最適化を実行して計画グラフ内の最小コストパスを見つけることにより、環境中の物体との衝突を回避又は衝突させる計画グラフ中のパスを識別し、そのような運動パスを実現することを含む。

運動プランナによる運動計画は、通常、衝突検出と最小コストパスの発見とを含む。衝突検出と最小コストパスの発見のいずれか又は両方は、例えば、１つ又は複数のフィールドプログラマブルゲートアレイ（ＦＰＧＡ）に実装することができ、有利には容易な再構成可能性を可能にする。衝突検出と最小コストパスの発見のいずれか又は両方は、例えば、１つ又は複数の特定用途向け集積回路（ＡＳＩＣ）に実装することができ、有利にはいくらかの再構成可能性を可能にしながら高速処理を可能にする。

車両（例えば、自動車両若しくはロボット）又は環境中の物体（例えば、静的若しくは動的障害物）の何れであれ、エージェントを表す場合、エージェントの表面は、ボクセル（３Ｄピクセル）又はポリゴン（多くの場合、三角形）のメッシュとして表すことができる。空間の各離散化領域は、３Ｄ（立体）ピクセルと同等の「ボクセル」と呼ばれる。幾つかの場合、物体を代わりにボックス（矩形プリズム）として表すことが有利である。物体はランダムな形状を有しないため、ボクセルがどのように編集されるかに相当量の構造があり、物体中の多くのボクセルは、３Ｄ空間において互いに直接隣にある。したがって、物体をボックスとして表すのに必要なのは、はるかに少数のビットのみとできる（すなわち、ボックスの２つの対向する隅のｘ、ｙ、ｚ座標のみとできる）。また、ボックスの交点テストを行うことは、ボクセルに対して交点テストを行うことと複雑性の点では同等である。物体の３Ｄ表面を表すために、種々の他のデータ構造、例えばユークリッド距離場、バイナリ空間パーテーションツリー等が使用可能である。

一実施形態では、衝突評価は、まず、動的物体ボクセル（又はボックス）の全てをプロセッサ（例えば、ＦＰＧＡ、ＡＳＩＣ）にストリーミングすることにより実行される。次に、車両１０２のロードマップの各エッジのエッジ情報がロードマップ専用のメモリからストリーミングされる。各エッジは、ある状態から、そのエッジによって表される別の状態へのロードマップにおける遷移を行う際、車両１０２により掃引される３Ｄ空間中の容積に対応する幾つかの数のボクセル（又はボックス）を有する。ある状態から、そのエッジによって表される別の状態へのロードマップにおける遷移を行う際、車両１０２により掃引されるボクセル又はボックスは、ロードマップの各エッジについてメモリに記憶される。各エッジボクセル（又はボックス）について、エッジの掃引容積からストリーミングされる場合、障害ボクセル（又はボックス）の何れかと衝突するとき、システム２００は、ロードマップにおいてそのエッジとの衝突を特定する。例えば、エッジボクセルがロードマップのエッジｘの掃引容積からストリーミングされる場合、障害ボクセル（又はボックス）の何れかと衝突するとき、システムは、エッジｘとの衝突を書き留める。この方法は、衝突評価が計画グラフの全てのエッジに対して並列で実行される他の設計と比較して、衝突評価にはるかに多数のロードマップを使用できるようにするため、衝突評価技術を改良する。特に、これは、チップ回路に記憶することができる限られた量のロードマップに関する他の設計の欠点を解消するのに役立つ。しかしながら、本明細書に記載される衝突評価法を使用する場合、オンチップ記憶は、多くの場合、全ての障害物ボックスを記憶するのに十分過ぎるほどである（しかし、ボクセルを使用する場合に十分さの程度が低くなりうる）。これは、大きいロードマップ及び／又は多数のロードマップをより安価なオフチップ記憶装置、例えばダイナミックランダムアクセスメモリ（ＤＲＡＭ）に記憶する能力を提供する。

種々の実装形態では、このような動作は、全体的に、ハードウェア回路で実行できるか、又はシステムメモリ２１４等のメモリ記憶装置に記憶され、１つ又は複数のマイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、グラフィックス処理ユニット（ＧＰＵ）プロセッサ、プログラムドロジックコントローラ（ＰＬＣ）、電気的に消去可能な読み取り専用メモリ（ＥＥＰＲＯＭ）又はハードウェア回路と、メモリ記憶装置に記憶されるソフトウェアとの組合せ等の１つ又は複数のハードウェアプロセッサ２１２ａにより実行されるソフトウェアとして実行できる。例えば、最適化を実行して、計画グラフ内の最小コストパスを見つけることにより、環境中の物体との衝突を回避するか又は衝突させる計画グラフ中のパスを識別することは、最適化部２９２により実行できる。一実施形態の例では、パス最適化部２９２がハードウェアを用いて実現される場合、計画グラフのトポロジは、ハードウェアユニットの再構成可能ファブリックにマッピングされて、最小コストパスを高速に特定することを可能にする。このマッピングは、論理近傍のアドレス及びエッジ重みを有する各物理ノードをプログラムすることを含む。これにより、アーキテクチャを異なる計画グラフトポロジに再構成可能とできる。他の実装形態は、ＦＰＧＡに実装されるミニプロセッサを使用できる。

代替の実施形態では、衝突評価は、再構成可能な衝突検出アーキテクチャ並びに「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０に記載される他の実施形態等の専用運動計画ハードウェアにより、車両１０２に生成された計画グラフの各エッジに対して並列で実行できる。例えば、そのような専用運動計画ハードウェアの全て又は部分は、運動プランナ２８０及び衝突評価器２８８に組み込むことができるか、又はそれらの一部を形成できる。また、知覚、計画グラフ構築、衝突検出及びパスサーチの種々の関連する態様の実現も、「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０に記載されている。図示の実施形態及び他の実装形態は、ロボット、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベース又はプログラマブルコンシューマ電子機器、パーソナルコンピュータ（ＰＣ）、ネットワーク化されたＰＣ、ミニコンピュータ、メインフレームコンピュータ等を含め、他のシステム構成及び／又は他の計算システム構成を用いて実現することも可能であることを当業者であれば理解するであろう。実装形態又はその一部（例えば、設計時、構成時、事前実行時）は、タスク又はモジュールが、通信ネットワークを通してリンクされたリモート処理デバイスにより実行される分散計算環境で実現することができる。分散計算環境では、プログラムモジュールは、ローカル及びリモートメモリ記憶装置の両方又は媒体に配置できる。しかしながら、車両１０２に効率的な計算能力を持たせることは、変化する環境に車両がリアルタイムに応答できるようにするために重要である。この問題に対して一般的に展開される解決策は、性能及び電力の点の両方で失敗している。この問題に対して一般的に展開される解決策は、高い自由度の車両及びロボットが環境にリアルタイムに応答できるようにするには遅すぎ、幾つかのＣＰＵ又はＧＰＵへの給電でシステムに負担を掛ける。この問題を解決するために、図２の実装形態の例に示されるコンピュータシステム２００は、ＦＰＧＡ２９０等の完全にゴール再設定可能な衝突検出マイクロアーキテクチャを使用する車両１０２に搭載された衝突評価器２８８を有する運動プランナ２８０を含む。しかしながら、種々の代替の実施形態では、ＡＳＩＣアーキテクチャ等のプログラマブル論理ブロックのアレイ及び再構成可能な相互接続の階層を含む他のプログラマブル衝突検出マイクロアーキテクチャを使用することもできる。プログラミングフェーズを通して、衝突検出マイクロアーキテクチャは、任意の車両計画問題に適用できる。衝突評価器２８８は、特定の物体との衝突回避を達成し、及び／又は、他の物体との衝突を探し求めるものであってもよい。衝突評価器２８８としての再構成可能プロセッサの使用は、効果的に、設計が１つの車両／ロードマップ対に専用であるという制限をなくす。最小コストパスモジュールは、例えば、分散ベルマン－フォードストラテジを使用して最小コストパスの高速計算を可能にする。

上述したように、幾つかの事前処理はランタイムの前に実行でき、したがって、幾つかの実施形態では、これらの動作は、通信ネットワークを通し、ネットワークインターフェース２６０を介して車両２００にリンクされるリモート処理デバイスにより実行できる。例えば、プログラミングフェーズでは、関心のある問題に向けてプロセッサを構成できるようにする。そのような実施形態では、広範な事前処理がランタイム計算を避けるために利用される。ロードマップ中のエッジにより表されるある状態から別の状態へのロードマップにおける遷移を行う際、車両１０２により掃引される３Ｄ空間中のボリュームに関する予め計算されたデータは、運動プランナ２８０の衝突評価器２８８に送信される。ロードマップのトポロジは、ＦＰＧＡ２９０等の計算ユニットの再構成可能ファブリックにマッピングされて、最小コストパスの高速な特定を可能にすることもできる。マッピングステップは、論理近傍のアドレス及びエッジ重みを有する計算ユニットの再構成可能ファブリックの各物理ノードをプログラムすることを含む。これにより、アーキテクチャを異なるロードマップトポロジに向けることができる。実行時フェーズ中、センサ２８２は、知覚データを運動プランナ２８０に送信する。知覚データは、現在の環境に存在するボクセル又はボックスのストリームである（より詳細に後述する）。衝突評価器２８８は、何れの運動が衝突を含む可能性が高く、何れの運動が衝突を含む可能性が低いかを計算し、完了すると、結果は、最小コストパスを特定するためにプラン最適化部２９２により使用される。これは、有利には、センサ２８２又は他の外部構成要素とそれ以上通信せずに行うことができる。運動プランナ２８０は、環境中の特定の物体との衝突回避又は衝突探求という車両１０２のゴールに応じて、ランタイム中、環境に基づいて環境に従ってロードマップに関連するコストを変更する。次に、運動プランナ２８０が実行され、生成されたパスをアクチュエータシステム２６６に返す。図２は、運動プランナ２８０と、システムメモリ２１４及びディスクドライブ２２４に関連するコンピュータ可読媒体２２６等の１つ又は複数の関連する非一時的機械可読記憶媒体とを含む、自動車両１０２向け等のコンピュータシステム２００を示す。関連する非一時的コンピュータ又はプロセッサ可読記憶媒体は、システムメモリ２１４及びディスクドライブ２２４に関連するコンピュータ可読媒体２２６を含み、システムバス２１６等の１つ又は複数の通信チャネルを介して運動プランナ２８０に通信可能に接続される。システムバス２１６は、メモリコントローラを有するメモリバス、周辺機器バス及び／又はローカルバスを含み、任意の既知のバス構造又はアーキテクチャを利用することができる。１つ又は複数のセンサ２８２、物体検出器２８４、物体挙動予測器、２８６及びアクチュエータシステム２６６もシステムバス２１６を介して運動プランナ２８０に通信可能に接続される。そのような構成要素の１つ又は複数は、追加又は代替として、１つ又は複数の他の通信チャネル、例えば１つ又は複数の並列ケーブル、直列ケーブル又は高速通信可能な無線ネットワークチャネル、例えばユニバーサルシリアルバス（「ＵＳＢ」）３．０、ＰＣＩエクスプレス（ＰＣＩｅ）又はＴｈｕｎｄｅｒｂｏｌｔ（登録商標）を介して互いに通信し得る。

コンピュータシステム２００は、ネットワークインターフェース２６０を介してコンピュータシステム２００の種々の構成要素に直接通信可能に接続されるか又間接的に通信可能に接続されるリモートシステム（図示せず）、例えばデスクトップコンピュータ、ラップトップコンピュータ、ウルトラポータブルコンピュータ、タブレットコンピュータ、スマートフォン、ウェアラブルコンピュータに通信可能に接続することもできる。実装形態では、コンピュータシステム２００自体又はその一部は、リモートであってもよい。そのようなリモートシステムは、コンピュータシステム２００及びコンピュータシステム２００内の種々の構成要素のプログラム、構成、制御又は他の方法でのインターフェース又はデータ入力を行うために使用できる。このような接続は、例えば１つ又は複数の広域ネットワーク（ＷＡＮ）（例えば、インターネット）といった、インターネットプロトコルを使用した１つ又は複数の通信チャネルを通じたものとできる。上述したように、事前ランタイム計算（例えば、初期ロードマップ生成）は、車両１０２とは別個のシステム又は他のタイプのロボットにより実行できる一方、変化する動作環境１００にリアルタイム又は準リアルタイム（マイクロ秒）に反応するようシステムが車両の速度を更新又は変更できることが重要であるため、ランタイム計算は、車両１０２で実行される。

図２に示される種々のブロックの構造及び動作の幾つかの態様は、「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０に記載されている。その結果、そのようなブロックは、本明細書に参照により援用される引用文献に鑑みて当業者により理解されるため、これ以上詳述する必要はない。

コンピュータシステム２００は、１つ又は複数の処理ユニット２１２ａ、２１２ｂ（まとめて２１２）、システムメモリ２１４及びシステムメモリ２１４を含む種々のシステム構成要素を処理ユニット２１２に結合するシステムバス２１６を含む。処理ユニット２１２は、１つ又は複数の中央演算処理装置（ＣＰＵ）２１２ａ、デジタル信号プロセッサ（ＤＳＰ）２１２ｂ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）等の任意の論理ユニットとできる。そのようなＡＳＩＣ及びＦＰＧＡは、衝突評価器２８８のＦＰＧＡ２９０への代替又は追加として、車両１０２の計画グラフのエッジに対して衝突評価を実行するために使用できる。システムメモリ２１４は、読み取り専用メモリ（「ＲＯＭ」）２１８、及び、ランダムアクセスメモリ（「ＲＡＭ」）２２０を含む。基本入出力システム（ＢＩＯＳ）２２２は、ＲＯＭ２１８の一部を形成でき、スタートアップ中などに、コンピュータシステム２００内の要素間での情報転送を補助する基本ルーチンを含む。

コンピュータシステム２００は、ディスクドライブ２２４を含み、ディスクドライブ２２４は、例えば、ハードディスクへの読み書きを行うハードディスクドライブ、フラッシュメモリデバイスへの読み書きを行うフラッシュメモリドライブ、リムーバブル光ディスクへの読み書きを行う光ディスクドライブ又は磁気ディスクへの読み書きを行う磁気ディスクドライブとできる。コンピュータシステム２００は、種々の異なる実施形態では、そのようなディスクドライブの任意の組合せを含むこともできる。ディスクドライブ２２４は、システムバス２１６を介して処理ユニット２１２と通信できる。ディスクドライブ２２４は、当業者に既知のように、そのようなドライブとシステムバス２１６との間に接続されるインターフェース又はコントローラ（図示せず）を含む。ディスクドライブ２２４及びそれに関連するコンピュータ可読媒体２２６は、コンピュータ可読命令、データ構造、プログラムモジュール及びコンピュータシステム２００の他のデータの不揮発性記憶を提供する。ＷＯＲＭドライブ、ＲＡＩＤドライブ、磁気カセット、デジタルビデオディスク（ＤＶＤ）、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭ、スマートカード等、コンピュータがアクセス可能なデータを記憶することができる他のタイプのコンピュータ可読媒体を利用することも可能であることを当業者であれば理解するであろう。

オペレーティングシステム２３６、１つ又は複数のアプリケーションプログラム２３８、他のプログラム又はモジュール２４０及びプログラムデータ２４２等のプログラムモジュールは、システムメモリ２１４に記憶できる。アプリケーションプログラム２３８は、プロセッサ２１２に、環境１００に対応する計画グラフのエッジに対する衝突評価を実行させ、計画グラフの各エッジの衝突確率を特定し設定させ、最適化を実行させて、環境１００中のエージェント（例えば、動的物体Ｂ１１２）との衝突を回避させるか又は衝突させる計画グラフ中のパスを識別させる命令を含む。計画グラフ中のパスを識別する最適化は、計画グラフ内の最小コストパスを見つけることを含む。アプリケーションプログラム２３８は、プロセッサ２１２に、本明細書に記載されるように運動計画に従って車両１０２を移動させる信号をアクチュエータシステム２６６に送信させる命令を含む。アプリケーションプログラム２３８は、プロセッサ２１２に、本明細書及び参照により本明細書に援用される引用文献に記載される知覚の他の動作（センサ２８２を介する）、計画グラフ構築、衝突検出及び経路検索を実行させる１つ又は複数の機械により可読な命令を更に含む。

アプリケーションプログラム２３８は、プロセッサ２１２に、車両１０２が動作する環境１００を表す知覚情報をセンサ２８２から受信させ、運動プランナ２８０に、衝突評価器２８８の再構成可能な衝突検出アーキテクチャハードウェアを使用させて、車両１０２の生成された計画グラフのエッジの２つ以上のそれぞれに対して衝突評価を実行させ、生成された計画グラフの２つ以上のエッジのそれぞれについて、衝突評価に少なくとも一部に基づいて衝突確率を設定させ、最適化を実行させて、車両１０２が動作する環境１００中の１つ又は複数の他のエージェント（例えば、動的物体Ａ１０４）と衝突する可能性が比較的高い、生成された計画グラフ中のパスを識別させ、アクチュエータシステム２６６に、最適化の少なくとも一部に基づいて、車両１０２が動作する環境１００中の１つ又は複数の他のエージェント（例えば、動的物体Ａ１０４）と衝突する可能性が比較的高い運動計画を実施させる１つ又は複数の機械により可読な命令を更に含む。再構成可能な衝突検出アーキテクチャハードウェアは、例えば、ＦＰＧＡ２９０である。しかしながら、種々の代替の実施形態では、ＡＳＩＣアーキテクチャ等のプログラマブル論理ブロックのアレイ及び再構成可能な相互接続の階層を含む他のプログラマブル衝突検出マイクロアーキテクチャを使用できる。

アプリケーションプログラム２３８は、プロセッサ２１２に、計画グラフについて、車両１０２が動作する環境１００中の１つ又は複数の動的物体（１０４、１１２）との衝突確率の評価の少なくとも一部に基づいて、各エッジが環境１００中の１つ又は複数の動的物体（１０４、１１２）との比較的低い衝突確率をそれぞれ有する場合、ゼロ以上の値を有する重みを計画グラフの各エッジに割り当てさせ、各エッジが環境１００中の１つ又は複数の動的物体（１０４、１１２）との比較的高い衝突確率をそれぞれ有する場合、ゼロ未満の値を有する重みを計画グラフの各エッジに割り当てさせ、最適化を実行させて、車両１０２が動作する環境１００中の１つ又は複数のエージェント、例えば動的物体（１０４、１１２）と衝突する可能性が比較的高い、生成された計画グラフ中のパスを識別させる１つ又は複数の機械により可読な命令を更に含む。

アプリケーションプログラム２３８は、プロセッサ２１２に、センサ２８２を介して、車両１０２が動作する環境１００を表す知覚情報を受信させ、運動プランナ２８０に、衝突評価器２８８の再構成可能な衝突検出アーキテクチャハードウェアを使用させて、計画グラフのエッジの１つ又は複数のそれぞれに対して衝突評価を実行させ、計画グラフの２つ以上のエッジのそれぞれについて、衝突評価の少なくとも一部に基づいて衝突確率を設定させ、最適化を実行させて、車両１０２が動作する環境１００中の１つ又は複数の動的物体（例えば、動的物体Ｂ１１２）と衝突する可能性が比較的低いパスにより指定される、二次元又は三次元空間中の車両１０２の走行の最長ルートを提供する、生成された計画グラフ中のパスを識別させ、最適化の少なくとも一部に基づいて、車両１０２が動作する環境１００中の１つ又は複数の動的物体（例えば、動的物体Ｂ１１２）と衝突する可能性が比較的低い運動計画を実施させる１つ又は複数の機械により可読な命令を更に含む。

アプリケーションプログラム２３８は、プロセッサ２１２に、限定ではなく、図６～図１３に示されるものを含め、本明細書に記載される種々の他の方法を実行させる１つ又は複数の機械により可読な命令を更に含む。

図２では、オペレーティングシステム２３６、アプリケーションプログラム２３８、他のプログラム／モジュール２４０及びプログラムデータ２４２は、システムメモリ２１４に記憶されているものとして示されているが、ディスクドライブ２２４の関連するコンピュータ可読媒体２２６に記憶することもできる。

プロセッサ２１２は、１つ又は複数の中央演算処理装置（ＣＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）等の任意の論理処理ユニットである。市販のコンピュータシステムの非限定的な例には、限定ではなく、米国Ｉｎｔｅｌ（登録商標）Ｃｏｒｐｏｒａｔｉｏｎにより提供されるＣｅｌｅｒｏｎ（登録商標）、Ｃｏｒｅ、Ｃｏｒｅ ２、Ｉｔａｎｉｕｍ（登録商標）及びＸｅｏｎファミリのマイクロプロセッサ；米国Ａｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓにより提供されるＫ８、Ｋ１０、Ｂｕｌｌｄｏｚｅｒ及びＢｏｂｃａｔシリーズのマイクロプロセッサ：米国Ａｐｐｌｅ Ｃｏｍｐｕｔｅｒ（登録商標）により提供されるＡ５、Ａ６及びＡ７シリーズのマイクロプロセッサ；米国Ｑｕａｌｃｏｍｍ（登録商標），Ｉｎｃ．により提供されるＳｎａｐｄｒａｇｏｎ（登録商標）シリーズのマイクロプロセッサ：並びに米国Ｏｒａｃｌｅ（登録商標） Ｃｏｒｐ．により提供されるＳＰＡＲＣ（登録商標）シリーズのマイクロプロセッサがある。別記されない限り、図２に示される種々のブロックの構築及び動作は、従来の設計のものである。その結果、そのようなブロックは、当業者により理解されるため、本明細書でこれ以上詳述する必要はない。運動プランナ２８０の衝突評価器２８８の再構成可能な衝突検出アーキテクチャハードウェアは、例えば、各エッジについて、記憶機構と、論理ゲートに並列接続されて、並列線の出力の「ＯＲ」演算を実行して、衝突結果を生成する比較器とを有する「エッジモジュール」のアレイを提供するアーキテクチャ等、ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０に記載されているようなアーキテクチャの１つであり得る。

図３は、一実施形態による、図２のコンピュータシステム中の種々の構成要素間の一例のデータフロー３００を示すブロック図である。一次エージェント１０２内に組み込まれるか、又は一次エージェント１０２と動作可能に通信する、カメラ、レーザセンサ機器、オーディオセンサ等の１つ又は複数のセンサ２８２は、知覚情報３０２を収集し、環境１００のモデルを生成する物体検出器２８４にこれを送信する。物体検出器２８４は、環境１００中の動的物体Ａ１０４及び動的物体Ｂ１１２等のエージェントの検出された移動に関する軌道情報を抽出し、当該軌道情報３０８を物体挙動予測器２８６に送信する。軌道情報３０８により示される環境１００中の動的物体（１０４、１１２）の現在の検出軌道に少なくとも一部に基づいて、物体挙動予測器２８６は、動的物体（１０４、１１２）の１つ又は複数の予測軌道を生成し、予測軌道情報３０６の一部としてこの情報を運動プランナ２８０に送信する。例えば、軌道情報３０８により、動的物体Ａ１０４が、現在、特定の方向に向かう軌道上にあることが示される場合、物体挙動予測器２８６は、動的物体Ａ１０４がその現在の軌道を続ける確率４０％、何らかの他のことを行う確率６０％と予測できる。

種々の要因が、物体挙動予測器２８６による環境１００中の動的物体（１０４、１１２）の予測軌道の特定に影響しうる。例えば、幾つかの実装形態では、動的物体（１０４、１１２）が環境１００内の将来の移動に影響するゴールを有すると示されるか又は決定される。一例として、現在、一次エージェント１０２から直接離れる軌道にあることが検出された動的物体Ａ１０４は、一次エージェント１０２から離れる（且つ離れたままである）というゴールを有すると示されるか又は決定される。したがって、物体挙動予測器２８６は、動的物体Ａ１０４の移動を予測する際、これを考慮に入れる。他方、現在、一次エージェント１０２に直接向かう軌道にあることが検出された動的物体Ｂ１１２は、一次エージェント１０２と衝突するというゴールを有すると示されるか又は決定される。したがって、物体挙動予測器２８６は、動的物体Ｂ１１２の移動を予測する際、これを考慮に入れる。

更に、他のエージェント、例えば動的物体（１０４、１１２）の移動は、一次エージェント１０２の軌道変更による影響を受ける。したがって、物体挙動予測器２８６は、動的物体（１０４、１１２）の予測軌道を特定する際、一次エージェント１０２の現在の軌道の、計画されたが、依然として実施又は実行されていない変更を考慮に入れ、運動プランナ２８０に提供される予測軌道情報３０６にそのような情報を含める。例えば、現在、一次エージェント１０２に直接向かう軌道にあることが検出された動的物体Ｂ１１２が、一次エージェント１０２と衝突するというゴールを有すると示されるか又は決定される場合、一次エージェント１０２が軌道を変更するとき、動的物体Ｂ１１２は、一次エージェント１０２を追いかけるような対応する変更を動的物体Ｂ１１２の軌道に行う可能性があることが予測される。したがって、一次エージェント１０２が、（一次エージェント１０２と衝突しようとしている）動的物体Ｂ１１２と衝突せずに環境１００内の行き先に到達するというゴールを有する場合、運動プランナ２８０は、一次エージェント１０２が行き先に到達するように軌道を変更した場合、動的物体Ｂ１１２が一次エージェント１０２を追いかけるような対応する変更をその軌道に行う可能性があることを考慮に入れて、動的物体Ｂ１１２との衝突を回避する行先へのパスを計画することが可能である。

全体的に、システムは、センサ２８２と、物体検出器２８４及び物体挙動予測器２８６により実行される処理との組合せを使用することにより、予測を実行して、環境１００のモデルを生成する。一実装形態では、センサ２８２は、占有グリッドを生成する。占有グリッドとは、環境１００等の環境の離散化ビューにおいて空間の何れの領域がいつ障害物を含むかを表すデータ構造である。空間の各離散化領域は、３Ｄ（立体）ピクセルと同等の「ボクセル」と呼ばれる。幾つかの場合、代わりに物体をボックス（矩形プリズム）として表すことが有利である。動的物体Ａ１０４、動的物体Ｂ１１２及び静的物体Ｃ１０８を含む環境中の物体により画定される空間の領域は、そのような立体表現により表される。１つ又は複数の動的物体（例えば、動的物体Ａ１０４及び動的物体Ｂ１１２）の立体表現及び関連する静的物体の立体表現は、物体検出器２８４から運動プランナ２８０に送信される。占有グリッドの構築については、入手可能な膨大な公開文献に記載されており、コンピュータビジョン及び検知の技術分野の当業者に既知である。

運動プランナ２８０は、動的物体及び静的物体の立体表現を含む知覚データを物体検出器２８４から受信し、予測軌道情報を物体挙動予測器から受信する。次に、運動プランナ２８０は、予測軌道を考慮して予測データにおいて障害物と衝突することになる計画グラフ中の各エッジに沿った衝突確率を調整し、コスト及び衝突確率を考慮してパスを決定し、そのパスを計算システムに出力する。

運動プランナは、運動プランナ２８０内の衝突評価器２８８の一部としてハードウェアプロセッサ及びメモリ記憶装置を含むことができる。例えば、ＦＰＧＡ２９０又はプログラマブル論理ブロックの他のアレイは、本明細書では「ロードマップ」とも呼ばれる計画グラフ（例えば、図４Ａ～図５Ｂを参照されたい）を記憶することができる。幾つかの実装形態では、運動プランナ２８０は、衝突検出を実行するＦＰＧＡ２９０等のハードウェア衝突検出回路を含む。幾つかの実装形態では、運動プランナ２８０は、再構成可能な衝突検出加速を含む。ロードマップ中のエッジにより表されるある状態から別の状態へのロードマップにおける遷移を行う際、一次エージェント１０２により掃引される２Ｄ又は３Ｄ空間における容積に関するデータは、運動プランナ２８０の衝突評価器２８８のメモリ記憶装置に記憶することができ、それにより、運動計画中、予測軌道情報を含む知覚データが受信されると、知覚データは、衝突評価器２８８のハードウェアプロセッサにより、衝突評価器２８８のメモリ記憶装置（又はコンピュータシステム２００のローカルシステムメモリ２１４）に記憶されたデータと比較されて、衝突を特定する。ランタイム動作中、計画グラフのエッジに、１つ又は複数の変数に基づいて情報を割り当てることができる。例えば、一次エージェント１０２のゴールが動的物体Ａ１０４との衝突である場合、予測軌道情報３０６による、動的物体Ａ１０４がどこに向かっているかの予測に基づいて、運動プランナ２８０は、動的物体Ａ１０４と衝突する一次エージェント１０２の運動計画を生成する。これを行うために、衝突評価器２８８は、動的物体Ａ１０４との衝突確率について計画グラフ中の全てのエッジを評価する。なお、環境１００は、一次エージェント１０２が動作する二次元又は三次元の空間であり、図４Ａ～図５Ｂに表される運動計画グラフに関して以下で参照する一次エージェントの「構成空間」と異なることに留意されたい。一次エージェントの構成空間は、一次エージェントの状態を特徴付ける一次エージェント１０２の全ての構成の空間であり、通常、例えば４つ以上の次元を有する多次元空間である。図４Ａ～図５Ｂに表される計画グラフ４００及び５００中のエッジは、一次エージェント１０２の構成間の遷移を表す。計画グラフ４００のエッジは、必ずしもデカルト座標における実際の移動を表す必要はないが、幾つかの実施形態では、デカルト座標における実際の移動を表すこともある。計画グラフ４００のエッジは、速度変更等を含むこともできる。

計画グラフ４００及び５００の各エッジは、ある状態から別の状態への一次エージェントの遷移を表し、関連する固有の又は動作のコストを有する。例えば、固有の又は動作のコストは、燃料使用、関連する行動を実行する時間、行動に関連する摩損及び／又は他の要因に関連する。各エッジには、固有の又は動作のコストに対応する初期重みが割り当てられる。

システムは、ランタイム中、衝突評価の少なくとも一部に基づいて、環境中の動的物体（１０４、１１２）との衝突確率を表すようにエッジのコストを調整する。システムは、衝突確率に基づいて各エッジの割り当てられた初期重みを変更することにより、コストの調整を実行できる。例えば、システムは、コスト関数を各エッジに適用して、そのエッジの初期重み（すなわち固有のコストに対応する重み）に基づいて数学的演算を実行して、変更された重みを取得できる。これは、衝突確率に基づいて、割り当てられた初期重みに追加の重みを追加することにより、衝突確率係数で、割り当てられた初期重みを乗算することにより、又は衝突確率及び固有のコストに対応する初期重みを含む何らかの他の関数若しくは公式を適用することにより行われる。

エッジに割り当てられた固有の又は動作のコストは、物体との衝突回避又は物体との衝突達成の相対的な重要度及び／又は深刻度を表す物体固有のコストを反映するようにランタイム中に調整することもできる。これらの物体特有のコストは、固有の又は動作のコストから独立しており、且つ衝突確率から独立している。例えば、人間との衝突に関連する物体特有のコストは、無生物物体との衝突に関連する物体特有のコストよりもはるかに高く設定される。

図４Ａ～図５Ｂにおける説明を簡潔にするために、各エッジの固有のコストに対応する全ての初期重みは、ゼロに設定されており、衝突確率を示す追加コストを追加することにより調整されている。したがって、一次エージェント１０２のゴールが、環境中の動的物体（動的物体Ａ１０４等）との衝突である一実装形態では、衝突確率ゼロと組み合わせた初期重み０は、エッジ重み０をもたらす一方、衝突確率が大きいほど、大きい負の値（すなわちより大きい絶対値を有する負の数）のエッジ重みになる。一次エージェント１０２のゴールが、環境中の動的物体（動的物体Ｂ１１２等）との衝突回避である別の実装形態では、衝突の確率が大きいほど、調整されたエッジ重みは、大きい正の値を有する。

計画グラフの全てのエッジ重みが調整されると、パス最適化部２９２は、計画グラフに示される一次エージェント１０２の現在の位置から、一次エージェント１０２が燃料／電力切れを起こす全ての可能な最終点まで最小コストパスアルゴリズムを実行する。次に、計画グラフ中の最小（最も負の）パスが運動プランナ２８０により選択される。

パス最適化部２９２が計画グラフ内のパスを識別すると、運動プランナは、この識別されたパス３１０を一次エージェント１０２のアクチュエータシステム２６６にリアルタイムに即座に送信して、一次エージェント１０２の種々のモータ又は移動システムへの、一次エージェント１０２の物理的移動を生じさせて運動計画を実施させる対応する信号を生成する。

図４Ａは、一実施形態による、一次エージェント１０２のゴールが、一次エージェント１０２を避けようとしている可能性がある図１の動的物体Ａ１０４と衝突することである場合の、図１の一次エージェント１０２の一例の運動計画グラフ４００である。計画グラフ４００は、エッジにより結ばれた複数のノードを含む。例えば、ノード４０８ｂ及び４０８ｃは、エッジ４１０ａにより結ばれている。各ノードは、暗黙的又は明示的に、一次エージェントの座標空間における一次エージェント１０２の状態を特徴付ける時間及び変数を表す。一次エージェントの構成空間（Ｃ空間と呼ばれることが多い）は、本例では、一次エージェントの状態を特徴付ける、計画グラフ４００において表される一次エージェントの構成の空間である。計画グラフ４００におけるエッジは、一次エージェント１０２のこれらの構成間の遷移を表す。計画グラフ４００のエッジは、デカルト座標における実際の移動を表さない。例えば、各ノードは、限定ではなく、一次エージェント１０２の現在の位置、姿勢、速度及び進行方向を含む一次エージェントの構成を表す。幾つかの実施形態では、一次エージェント１０２の加速度も計画グラフ４００中のノードによって表される。

計画グラフ４００中の各エッジは、各ノード対間の物体１０２の遷移を表す。例えば、エッジ４１０ａは、２つのノード間の一次エージェント１０２等の物体の遷移を表す。特に、エッジ４１０ａは、ノード４０８ｂに関連する特定の構成における一次エージェント１０２の状態と、ノード４０８ｃに関連する一次エージェント１０２の状態との間の遷移を表す。例えば、一次エージェント１０２は、現在、ノード４０８ａに関連する特定の構成とできる。ノードを互いから種々の距離を有するものとして示しているが、これは、単に例示のためであり、物理的距離に関連はなく、計画グラフ４００におけるノード数に制限はない。しかしながら、計画グラフ４００で使用されるノードが多くなるほど、最小コストパスを選択する際、多くのパス候補があるため、運動プランナ２８０は、より正確且つ精密に一次エージェント１０２のゴールに従って最適パスを決定することが可能である。

一次エージェント１０２は、動的物体Ａ１０４の検査、動的物体Ａ１０４からの情報収集、動的物体Ａ１０４との情報交換又はゲームでの動的物体Ａ１０４との衝突等のために、動的物体Ａ１０４の後を辿るか又は妨害することが望ましい場合がある。図４Ａは、一次エージェント１０２のゴールが動的物体Ａ１０４との衝突である場合、一次エージェント１０２のパスを識別するために、運動プランナ２８０により計画グラフがどのように使用されるかを示す。この時点で、運動プランナ２８０は、一次エージェント１０２が動作する環境１００を表す知覚情報を受信している。上述したように、衝突検出は、ボクセル又はボックスを使用して、一次エージェント１０２及び動的物体Ａ１０４を含む環境中の物体を運動プランナ２８０に対して表すことができる。しかしながら、他の物体表現を使用できることを理解されたい。

一実装形態では、環境は、ボクセル又はボックスの３Ｄ領域に離散化される。次に、環境１００中の一次エージェント１０２によるあらゆる運動の掃引体積と、離散化空間中のボクセル又はボックスとの間で起こりうる全ての衝突が予め計算される。そのような衝突評価の例は、「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０に記載されている。

動的物体Ａ１０４が環境１００中で移動していることに起因して、運動プランナ２８０は、動的物体Ａ１０４がどこに向かっているかの予測に基づいて、計画グラフ４００中の２つ以上のエッジについての動的物体Ａ１０４との一次エージェント１０２の衝突評価も決定する。計画グラフ４００のこれらのエッジのそれぞれについて、運動プランナ２８０は、衝突評価の少なくとも一部に基づいて、特定の将来の時間における動的物体Ａ１０４との一次エージェント１０２の衝突確率を設定する。例えば、知覚情報に従い、動的物体Ａ１０４は、環境１００中の特定の位置に存在することが検出される。動的物体Ａ１０４の現在の軌道１１０に基づいて、運動プランナ２８０は、動的物体Ａ１０４が、将来、環境１００中の特定の位置に存在するであろうと決定する。ノード間の直接移動が動的物体Ａ１０４との衝突を生じさせることになる確率がある計画グラフ４００中のノードについて、運動プランナは、動的物体Ａ１０４との衝突の確率を示す重みをそれらのノード間を遷移する計画グラフ４００のエッジ（エッジ４１０ｂ、４１０ｃ、４１０ｄ、４１０ｅ、４１０ｆ、４１０ｇ、４１０ｈ、４１０ｉ、４１０ｊ、４１０ｋ）に割り当てる。図４Ａに示される例では、これは、グラフ部分４１４として示されるが、物理的エリアに対応しない。

例えば、運動プランナ２８０は、定義された衝突確率閾値を下回る動的物体Ａ１０４との衝突確率をそれぞれ有する計画グラフ４００の幾つかのエッジのそれぞれに対して、ゼロ以上の値を有する重みを割り当てる。本例では、運動プランナ２８０は、動的物体Ａ１０４の現在の軌道によれば、動的物体Ａ１０４とのいかなる衝突確率もない（又はあったとしてもごく僅かである）計画グラフ４００中のエッジに重みゼロを割り当てた。例えば、計画グラフ４００に示されるように、運動プランナ２８０は、重みゼロをエッジ４１０ａに割り当てており、その理由は、動的物体Ａ１０４の現在の軌道１１０によれば、エッジ４１０ａにおいて動的物体Ａ１０４と衝突する確率がゼロ（又はあったとしてもごく僅か）であるためである。次に、運動プランナ２８０は、定義された衝突確率閾値を上回る環境１００中の動的物体Ａ１０４との衝突確率をそれぞれ有する計画グラフ４００の幾つかのエッジのそれぞれに対して、ゼロ未満の値を有する重みを割り当てる。本例では、運動プランナ２８０は、動的物体Ａ１０４の現在の軌道によれば、動的物体Ａ１０４との衝突確率がより高い計画グラフ４００中のエッジに対してゼロ未満の重みを割り当てた。衝突確率に使用される特定の閾値は、変更できる。例えば、閾値は、４０％、５０％、６０％又はより高い若しくはより低い衝突確率であってもよい。また、ゼロ未満の値を有する重みを割り当てる運動プランナ２８０は、各衝突確率と対応する大きさを有する負の重みを割り当てることを含む。例えば、計画グラフ４００に示されるように、運動プランナは、エッジ４１０ｂ、４１０ｃ、４１０ｄ及び４１０ｅに重み－３を割り当てているが、エッジ４１０ｆにより低い大きさ－２を有する負の重みを割り当てており、エッジ４１０ｇにより大きい大きさ－５を有する重みを割り当てている。割り当てられる重みは、整数である必要はない。

図４Ｂは、一実施形態による、一次エージェント１０２のゴールが、一次エージェント１０２を避けようとしている可能性がある図１の動的物体Ａ１０４と衝突することである場合の、図１の一次エージェント１０２の一例の運動計画グラフ４００及び動的物体Ａ１０４と衝突する一次エージェント１０２の計画グラフ４００において識別された一例のパス４１２（ノード４０８ａを４０８ｄに結ぶグラフ４００の太字エッジを含む）である。運動プランナ２８０は、衝突評価の少なくとも一部に基づいて動的物体Ａ１０４との一次エージェント１０２の衝突確率を設定した後、最適化を実行して、動的物体Ａ１０４と衝突する可能性が比較的高い、生成された計画グラフ４００中のパス４１２を識別する。

例えば、計画グラフ４００の全てのエッジ重みが図４Ａ及び図４Ｂに示されるように割り当てられると、運動プランナ２８０は、計画グラフ４００中の一次エージェント１０２の現在の状態から、一次エージェント１０２が燃料切れになる全ての可能な最終点までに最小コストパスアルゴリズムを実行する。次に、計画グラフ４００中の最小（最も負の）パスが運動プランナ２８０により選択される。本例では、計画グラフ中の一次エージェント１０２の現在の状態は、ノード４０８ａにあり、この最小（最も負のパス）は、計画グラフ４００におけるパス４１２として示されている。多くの急なターンを有するパスが計画グラフ４００に示されているが、そのようなターンは、ルートにおける対応する物理的ターンを表しておらず、一次エージェント１０２の状態間の論理的な遷移を表している。例えば、識別されたパス４１２中の各ノードは、環境１００における一次エージェント１０２の物理的構成に関する状態変更を表すが、必ずしも図４Ｂに示されるパス４１２の角度に対応する一次エージェント１０２の進行方向変更を表しているわけではない。

ベルマン－フォードアルゴリズムを実施するものを含め、最小コストパスを決定する種々のプロセスが使用可能であるが、それに限られず、構成エッジの重みの和が最小になるような最小コストパスが計画グラフ４００中の２つのノード間のパスとして決定される任意のプロセスを含む他のプロセスを使用できる。このプロセスは、計画グラフ及び衝突検出を使用して、所望の物体と衝突する最良のルートを見つけるための効率及び応答時間を改善することにより、動的物体（１０４、１１２）との衝突に向けた一次エージェント、例えば自律車両の運動計画の技術を改善する。更に、幾つかの実装形態は、一次エージェント１０２が動作する環境中の１つ又は複数の静的物体と衝突する可能性が比較的高い一次エージェント１０２のパスを識別するために同じプロセスを使用する。そのような静的物体との衝突が探求される場合、運動プランナ２８０は、環境１００中の静的物体との各衝突確率を有する計画グラフ４００のエッジに対して、大きい負の値を有する重みを割り当てる。このようにして、運動プランナが最適化中に最小コストパスを選択する場合、そのようなパスが選択される可能性がより高くなる。しかしながら、そのような実装形態では、考慮に入れる必要がある静的物体の速度、軌道又は加速度はない。

幾つかの実装形態では、一次エージェント１０２が動的物体Ａ１０４と衝突しようとしている間、衝突を回避すべき静的物体が環境に存在しうる。そのような場合、衝突評価に基づいて計画グラフ４００のエッジの衝突確率を設定することは、それに従ってそのような静的物体との衝突を回避するように（例えば、初期重みを変更／調整することにより）重みを割り当てることを含む。例えば、運動プランナ２８０は、環境１００における静的物体との各衝突確率を有する計画グラフ４００の幾つかのエッジのそれぞれに対して、無限大の値を有する重みを割り当てる。このようにして、運動プランナが最適化中に最小コストパスを選択する場合、無限大に設定されたエッジ重みを有するそのようなパスは、移動した場合、静的物体との衝突に繋がることになるため、回避されることになる。

運動プランナ２８０は、最適化を実行して、一次エージェント１０２のルート全体のうち、動的物体Ａ１０４と衝突する可能性が最も高い生成された計画グラフ４００中のパスを識別する。幾つかの実装形態では、ルートの長さは、少なくとも部分的に、一次エージェント１０２が燃料／電力切れになるときまで定義される。一次エージェント１０２の「残燃料」を示す変数がコンピュータシステム２００により記憶されてもよい。幾つかの実装形態では、運動プランナ２８０は、最適化を実行して、一次エージェント１０２が動作する環境中の１つ又は複数の物体と最短の相対時間量で衝突する可能性が比較的高い生成された計画グラフ４００中のパスを識別する。代替的には、幾つかの実装形態では、運動プランナ２８０は、最適化を実行して、最長の走行時間を有する生成された計画グラフ４００中のパスを、動的物体Ａ１０４と衝突する可能性が比較的高いパスにより特定されるものとして識別してもよい。

計画グラフ４００中のパスは、動的物体Ａの軌道１１０の変更又は予測される変更に基づいて識別することもできる。動的物体Ａ１０４の軌道１１０の各変更又は予測される変更時、衝突評価及び最適化プロセスを再びリアルタイム又は準リアルタイムで実行できる。また、生成された計画グラフ４００は、一次エージェント１０２及び／又は動的物体Ａ（１０４、１１２）の物理的制約又は性能制約、一次エージェント１０２及び幾つかの実装形態では動的物体Ａ１０４の加速度、ピッチ、ロール及びヨーを表す関連データを有するか又は記憶する。次に、そのような変数に基づいて、パスを識別する最適化を実行する。例えば、一次エージェント動的物体Ａ１０４のピッチ、ロール及び／又はヨーが変化する場合、これは、動的物体Ａ１０４の軌道の変更を示す（又は予測される変更に繋がる）。

図５Ａは、一実施形態による、一次エージェント１０２のゴールが、一次エージェント１０２に近づきつつある図１の動的物体Ｂ１１２との衝突回避である場合の、図１の一次エージェント１０２の一例の運動計画グラフ５００である。計画グラフ４００と同様に、計画グラフ５００は、それぞれエッジにより結ばれた複数のノードを含む。各ノードは、暗黙的又は明示的に、一次エージェント１０２の状態を特徴付ける時間及び変数を表す。例えば、各ノードは、一次エージェントの構成を表し、構成は、一次エージェント１０２の現在の位置、姿勢、速度及び進行方向を含むが、これに限定されない。幾つかの実施形態では、一次エージェント１０２の加速度も計画グラフ５００中のノードによって表される。

一次エージェント１０２は、動的物体Ｂ１１２との衝突回避等のために、動的物体Ｂ１１２を回避することが望ましい場合がある。図５Ａは、一次エージェント１０２のゴールが動的物体Ｂ１１２との衝突を回避すること又は動的物体Ｂ１１２から逃れることであり、動的物体Ｂ１１２がゲーム等において一次エージェント１０２と衝突しようとしている場合、一次エージェント１０２のパスを識別するために、運動プランナ２８０により計画グラフがどのように使用されるかを示す。この時点で、運動プランナ２８０は、一次エージェント１０２が動作する環境１００を表す知覚情報を受信している。上述したように、衝突検出は、ボクセル又はボックスを使用して、一次エージェント１０２及び動的物体Ｂ１１２を含む環境中の物体を表す。しかしながら、他の物体表現を使用できることを理解されたい。一実装形態では、環境は、ボクセル又はボックスの３Ｄ領域に離散化される。次に、環境１００中の一次エージェント１０２による計画グラフ５００におけるあらゆる運動の掃引容積と、離散化空間中のボクセル又はボックスとの間で起こり得る全ての衝突が予め計算される。

動的物体Ｂ１１２が環境１００中で移動していることに起因して、運動プランナ２８０は、動的物体Ｂ１１２が進行している場所の予測に基づいて、計画グラフ５００中の２つ以上のエッジについての動的物体Ｂ１１２との一次エージェント１０２の衝突評価も決定する。計画グラフ５０のこれらのエッジのそれぞれについて、運動プランナ２８０は、衝突評価の少なくとも一部に基づいて、特定の将来の時間における動的物体Ｂ１１２との一次エージェント１０２の衝突確率を設定する。例えば、知覚情報に従い、動的物体Ｂ１１２は、環境１００中の特定の位置にあることが検出される。動的物体Ｂ１１２の現在の軌道１０６に基づいて、運動プランナ２８０は、将来、動的物体Ｂ１１２が環境１００中の特定の位置に存在するであろうと決定する。ノード間の直接移動が動的物体Ｂ１１２との衝突を生じさせることになる確率がある計画グラフ５００中のノードについて、運動プランナは、動的物体Ｂ１１２との衝突の確率を示す重みをそれらのノード間を遷移する計画グラフ５００のエッジ（エッジ５１０ａ、５１０ｂ、５１０ｃ、５１０ｄ、５１０ｅ、５１０ｆ、５１０ｇ、５１０ｈ、５１０ｉ、５１０ｊ、５１０ｋ、５１０ｌ、５１０ｍ、５１０ｎ、５１０ｏ及び５１０ｐ）に割り当てる。図５Ａに示される例では、これは、グラフ部分５１４として示されるが、物理的エリアに対応しない。

例えば、運動プランナ２８０は、定義された衝突確率閾値を上回る動的物体Ｂ１１２との衝突確率を有する計画グラフ５００の幾つかのエッジのそれぞれに対して、ゼロを超える値を有する重みを割り当てる。本例では、運動プランナ２８０は、動的物体Ｂ１１２の現在の軌道によれば、動的物体Ｂ１１２とのいかなる衝突確率もない（又はあったとしてもごく僅かである）計画グラフ５００中のエッジに重みゼロを割り当てた。次に、運動プランナ２８０は、定義された衝突確率閾値を上回る環境１００中の動的物体Ｂ１１２との衝突確率を有する計画グラフ５００の幾つかのエッジのそれぞれに対して、ゼロを超える値を有する重みを割り当てる。本例では、運動プランナ２８０は、動的物体Ｂ１１２の現在の軌道によれば、動的物体Ｂ１１２との衝突確率がより高い計画グラフ５００中のエッジに対してゼロを超える重みを割り当てた。衝突確率に使用される特定の閾値は、変更さできる。例えば、閾値は、４０％、５０％、６０％又はより低い若しくはより高い衝突確率であってもよい。また、ゼロを超える値を有する重みを割り当てる運動プランナ２８０は、各衝突確率と対応する、ゼロを超える大きさを有する重みを割り当てることを含む。例えば、計画グラフ５００に示されるように、運動プランナは、より高い衝突確率を有するエッジ５１０ｆ及び５１０ｉに対して重み５を割り当てたが、運動プランナ２８０がはるかに低い衝突確率を有すると決定したエッジ５１０ｐ及び５１０ｇに対してはより低い大きさ１を有する重みを割り当てた。

図５Ｂは、一実施形態による、一次エージェント１０２のゴールが、一次エージェント１０２に近づきつつある図１の動的物体Ｂ１１２との衝突を回避することである場合の、図１の一次エージェント１０２の一例の運動計画グラフ５００及び動的物体Ｂ１１２との衝突を回避する一次エージェント１０２の計画グラフ５００において識別された一例のパス５１２（ノード５０８ａを５０８ｂに結ぶグラフ５００の太字エッジを含む）である。運動プランナ２８０は、衝突評価の少なくとも一部に基づいて動的物体Ｂ１１２との一次エージェント１０２の衝突確率を設定した後、最適化を実行して、動的物体Ｂ１１２と衝突する可能性が比較的低い、生成された計画グラフ５００中のパスにより指定される、一次エージェント１０２の走行の最長ルートを提供する、生成された計画グラフ５００中のパス５１２を識別する。

一実装形態では、計画グラフ５００の全てのエッジ重みが図５Ａ及び図５Ｂに示されるように割り当てられると、運動プランナ２８０は、計算を実行して、一次エージェント１０２と衝突する前に動的物体Ｂ１１２が燃料切れになるような走行の最長ルートを決定する。例えば、計画グラフ５００の全てのエッジ重みが図５Ａ及び図５Ｂに示されるように割り当てられると、運動プランナ２８０は、計画グラフ５００中の一次エージェント１０２の現在の状態から、一次エージェント１０２が燃料／電力切れになる全ての可能な最終点まで最小コストパスアルゴリズムを実行する。次に、計画グラフ５００中の最小コスト（ゼロに最も近い）パスを有する（例えば、時間又は距離において）最長となるルートが運動プランナ２８０により選択される。しかしながら、計画グラフ５００中の最長ルートであり、且つ、最小コスト（ゼロに最も近い）であるパスは、多くの場合、競合する。最長ルートが望ましい場合、計画グラフ５００において最小コストパスを見つけることは、最小の衝突確率を有するパスを選択することほど高い優先度を有さない。本例では、計画グラフ中の一次エージェント１０２の現在の状態は、ノード５０８ａにあり、このパスは、計画グラフ５００中のパス５１２として示される。

幾つかの実装形態では、（動的物体Ｂ１１２との衝突を回避しながら）特定の行先に辿り着く一次エージェント１０２の二次ゴールが存在しうる。この場合、最適化は、最小コストパスアルゴリズムを計画グラフ５００中の一次エージェント１０２の現在の状態から所望の行先まで実行することを含む。一実施形態では、一次エージェント１０２のゴールは、例えば、動的物体Ｂ１１２が一次エージェント１０２と衝突する前に燃料切れになるように、動的物体Ｂ１１２と衝突しない時間を最大にすることである。一実施形態例における一次エージェント１０２のゴールは、現在の時刻から所望の行先への一次エージェント１０２の到着時刻若しくは特定のゴールを達成するまでの間又は現在の時刻から動的物体Ｂ１１２が燃料切れになるまでの間、動的物体Ｂ１１２との衝突確率を最小にすることである。このプロセスは、計画グラフ及び衝突検出を使用して、自律一次エージェントとの衝突を探求している動的物体（１０４、１１２）との衝突を回避する最良のルートを見つけることの効率及び応答時間を改善することにより、動的物体（１０４、１１２）との衝突を回避することについて運動計画の技術を改善する。更に、幾つかの実装形態は、一次エージェント１０２が動作する環境中の１つ又は複数の静的物体と衝突する可能性がゼロである一次エージェント１０２のパスを識別するために同じプロセスを使用する。そのような静的物体との衝突を回避すべき場合、運動プランナ２８０は、環境１００中の静的物体との各衝突確率を有する計画グラフ５００の幾つかのエッジのそれぞれに対して、重みに無限大の値を割り当てる。このようにして、運動プランナが最適化中に最小コストパスを選択する場合、無限大に設定されたエッジ重みを有するそのようなパスは、エッジが横切られる場合、静的物体と衝突することになる不確かさがあるため、避けられる。そのような実装形態では、静的物体の速度又は軌道は、考慮に入れられない。

幾つかの実装形態では、複数の他のエージェント、例えば動的物体（１０４、１１２）が存在し、一次エージェント１０２は、そのうちの幾つかを回避し、他は妨害又は衝突するというゴールを有する。そのような実装形態では、一次エージェント１０２が動的物体（１０４、１１２）と衝突するための本明細書に記載されるプロセス、及び、一次エージェント１０２が動的物体（１０４、１１２）との衝突を回避するための本明細書に記載されるプロセスは、同時に、同じときに又は他の方法で互いと併せて実行できる。例えば、物体によっては、衝突するものとして識別されるものもあれば、衝突を回避する物体として識別されるものもある。次に、運動プランナ２８０は、それに従い、動的物体及び静的物体に対応する軌道及び知覚情報並びにそのような物体と衝突すべきか又は回避すべきかを考慮に入れて、本明細書に記載されるように最適化を実行する。そのような場合、衝突評価に基づいて計画グラフのエッジの衝突確率を設定することは、それに従って衝突又は衝突回避するための重みを割り当てる（例えば、初期重みを変更／調整することにより）ことを含む。

運動プランナ２８０は、最適化を実行して、一次エージェント１０２のルート全体に沿った動的物体Ｂ１１２との最小の衝突確率を有する、生成された計画グラフ５００中のパスを識別する。幾つかの実装形態では、ルートの長さは、少なくとも部分的に、一次エージェント１０２が燃料／電力切れになるときまで定義される。一次エージェント１０２の残燃料又は残電力を示す変数がコンピュータシステム２００により記憶されてもよい。幾つかの実装形態では、運動プランナ２８０は、最適化を実行して、動的物体Ｂ１１２と衝突する可能性が比較的低いパスにより指定される最長持続時間の走行を有する、生成された計画グラフ５００中のパスを識別する。パスを、動的物体Ｂ１１２の軌道１０６の変更又は予測される変更に基づいて識別することもできる。動的物体Ｂ１１２の軌道１０６の各変更又は予測される変更時、衝突評価及び最適化プロセスを再びリアルタイム又は準リアルタイムで実行できる。また、生成された計画グラフ５００は、一次エージェント及び／又は動的物体の物理的制約又は性能制約、一次エージェント１０２及び幾つかの実装形態では動的物体Ｂ１１２の加速度、ピッチ、ロール及びヨーを表す関連データを有してもよい。次に、そのような変数に基づいて、パスを識別する最適化を実行できる。例えば、動的物体Ｂ１１２のピッチ、ロール及び／又はヨーが変化する場合、これは、動的物体Ｂ１１２の軌道の変更を示す（又は予測される変更に繋がる）。

運動プランナ２８０は、多様な自律車両及びロボット（付属物あり又はなし）並びに予期されるタスクシナリオのためにプログラムすることができる。運動プランナ２８０は、異なる車両若しくはロボットのために再使用若しくは再プログラムすることができるか、又は運動プランナ２８０は、特定の車両若しくはロボットのために設計することができる。一つのタイプのロボットは、本明細書に記載される自律車両等の自律車両である。

図６は、一実施形態による、一次エージェント１０２（例えば、自律車両、付属物あり又はなしのロボット等）が動作でき、他のエージェント、例えば動的物体Ａ１０４及び動的物体Ｂ１１２が既知の軌道（例えば、それぞれｔ_Ａ１１０及びｔ_Ｂ１０６）を有する環境１００の概略図である。この状況では、一次エージェント１０２の軌道は、単に他のエージェントの現在の軌道を考慮に入れるだけではなく、環境１００における他のエージェントの意図、すなわち時間の関数としての他のエージェントの軌道を考慮に入れて計画することができる。また、これにより、他のエージェント、例えば動的物体Ａ１０４及び動的物体Ｂ１１２の変化する軌道に応答して、一次エージェント１０２の側での条件付きの行動が可能になる。例えば、人が一次エージェント１０２の環境１００において道路に走り込む場合、一次エージェント１０２の軌道に関してとるべき行動は、その人が走り続けるか、それとも止まるかに依存することになる。換言すれば、エージェント（例えば、この例では人）の軌道を知ることで、環境１００中の他のエージェントが行う可能性があることとは無関係に格子を通して完全なパスを計画するのではなく、変化する状況を考慮に入れた解決策が可能になる。加えて、この手法は、パスが計画される前に軌道の集合全体が運動グラフのエッジに適用される場合などに生じ得る衝突の二重カウントを回避する。

図７は、図６の一次エージェント１０２の一例の運動計画グラフ７００である。実施形態では、格子中の各ノード（例えば、ｎ_０、ｎ_１、ｎ_２、・・・）は、そのノードと一次エージェント１０２のゴール（すなわち最終状態）との間の格子のエッジ（例えば、ｃ_０，４、ｃ_０，５等）に関連するコストに基づく関連する値（すなわちコスト）を有する。

格子は、静的バックグラウンド衝突検出を実行して、静的物体（例えば、静的物体Ｃ１０８）と衝突するエッジを見つけることにより初期化される。そのような場合、コストは、静的物体と衝突することになり（例えば、ｎ_１４とｎ_１５との間のエッジ）、比較的高いコストになると特定されるエッジに割り当てられる（又はコスト関数を適用する）。例えば、コストは、無限大に設定され、それにより、効果的に、一次エージェント１０２の軌道が静的物体と衝突すると識別されたエッジを含まないようにする。格子の初期化の第２の態様では、例えば、対象のノードからゴールノード（例えば、ｎ_１５）への最小コストパスに基づいて、各ノードでのゴールへのコストが特定される。例えば、ノードｎ_１３のコストは、ｎ_１３とｎ_１６との間のエッジのコスト（ｃ_{１３，１６}）及びｎ_１６とｎ_１５との間のコスト（ｃ_{１６，１５}）によって決定される。

図７に示されるグラフ７００を使用した一次エージェント１０２の運動計画は、ｎと示されたノード（例えば、ｎ_０）において時間Ｔ＝ｉから始まって実行される。先に説明したように、運動計画は、一次エージェント１０２の環境１００中の他のエージェント、例えば動的物体（１０４、１１２）の意図を考慮に入れる。意図は、例えば、確率的関数に基づく挙動モデルを使用してサンプリングされて、各エージェントＡ_ｊの軌道ｔを生成し、結果として軌道の集合Ｓを生成する。以下に更に詳細に説明するように、各軌道ｔがグラフ７００に個々に適用されて最小コストパスが決定され、次にコストの平均計算が実行される。これは、最小コストパスが決定される前に軌道の集合全体が運動計画グラフに適用される手法とは対照的である。

Ｓ中の各軌道ｔについて、運動計画グラフ７００中のエッジが軌道と衝突する場合、何れのエッジが軌道と衝突するか、すなわち何れのエッジが一次エージェント１０２を軌道ｔに対応する別のエージェントと衝突させることになるかを決定する。これらのエッジのコスト値は、例えば、衝突するエッジに高い値が割り当てられることになる関数等の衝突に関連するコストを決定するコスト関数を適用することにより変更される。

グラフ７００のエッジのコストが軌道ｔに基づいて変更された後、候補ノードｎ’、すなわち現在のノードｎ（例えば、ｎ_０）から１つの時間ステップで（すなわち時間Ｔ＝ｉ＋１において）到達可能な各ノードのコストが計算される。候補ノードｎ’（例えば、ｎ_３、ｎ_４、ｎ_５及びｎ_１）のコストは、現在のノードｎ（例えば、ｎ_０）から候補ノードｎ’を通過してゴール（例えば、ｎ_１５）までの最小コストパスを見つけることにより計算される。図７は、ノードｎ_０からゴール（ノードｎ_１５）までの候補ノードｎ_４を通過する第１の最小コストパス７１０及びノードｎ_０からゴールまでの候補ノードｎ_５を通過する第２の最小コストパス７２０の一例を示す。これらの例では、軌道ｔでのノードｎ_４のコストは、第１のパスに沿ったエッジの和（例えば、ｃ_０，４、ｃ_４，９、ｃ_９，１３、ｃ_{１３，１６}、ｃ_{１６，１５}）であろう。

候補ノードｎ’のコストは、軌道の集合Ｓ中の各軌道（ｔ_１、ｔ_２，．．．、ｔ_ｍ）について上記のように計算され、各軌道は、エージェントＡ_ｊ（ｊ＝１～ｍ）に対応し、ここで、ｍは、他のエージェントの数である。コストは、軌道の集合Ｓにわたる平均が計算されて、各候補ノードｎ’の平均コストを提供する。最小平均コストを有する候補ノードｎ’が一次エージェントの次のノードとして選択される。したがって、時間Ｔ＝ｉ＋１において、最小平均コストを有する候補ノードｎ’は、次の時間ステップＴ＝ｉ＋２の現在のノードｎになる。これは、一次エージェント１０２がゴールノード（例えば、ｎ_１５）に到達するまで、すなわちゴールノードにより表される状態を達成するまで続けられる。

図８Ａは、示される一実施形態による、計画グラフを介して一次エージェントのパスを識別する方法８００を示す流れ図であり、パスは、他のエージェントの既知の軌道を考慮に入れて最小平均コストを有する候補ノードを通る。８０５において、システムは、静的バックグラウンド衝突検出を実行する。８１０において、各ノードのゴールまでのコストが計算される。図７に関して上述したように、格子中の各ノード（例えば、ｎ_０、ｎ_１、ｎ_２、・・・）は、そのノードと一次エージェント１０２のゴール（すなわち最終状態）との間の格子のエッジに関連するコスト（例えば、ｃ_０，４、ｃ_０，５等）に基づく関連する値（すなわちコスト）を有する。格子のエッジに関連するコストは、特に対象のエッジに沿った２つのノード間の移動に関連する固有のコスト（例えば、燃料及び／又はエネルギーコスト）に基づいて決定される。実装形態では、各ノードでのゴールまでのコストは、対象のノードからゴールノード（例えば、ｎ_１５）までの最小コストパスに基づいて決定される。８１５において、システムは、一次エージェントの環境１００中の他のエージェントＡ_ｊの軌道ｔを決定する。８２０において、現在のノードｎ、すなわち運動計画グラフ７００中の一次エージェントの現在の位置について、システムは、図８Ｂに更に詳細に説明され、その対応する説明が以下に説明されるように、軌道の集合Ｓにわたる各候補ノードｎ’の平均コストを計算する。８２５において、運動計画グラフ７００における一次エージェント１０２の状態（例えば、姿勢）は、ノードｎから、最小平均コストを有する候補ノードｎ’に移る。８３０において、時間がインクリメントされ、方法８００は、次の時間ステップに対して繰り返される。

図８Ｂは、示される一実施形態による、図８Ａの方法（ブロック８２０を参照されたい）における既知の軌道の集合にわたる平均が計算された各候補ノードのコストを計算するのに有用な方法８５０を示す流れ図である。８５５において、軌道の集合Ｓ中の各軌道ｔを考慮してループが開始され、ここで、ｔ＝１～ｍであり、ｍは、軌道の数である。８６０において、システムは、軌道ｔと衝突する運動計画グラフ７００のエッジがある場合、それが何れのエッジであるかを特定する。８６５において、システムは、軌道ｔと衝突すると特定されたエッジがある場合、そのエッジの値にコスト関数を適用する。８７０において、システムは、ノードｎからゴールまでの各候補ノードｎ’を通る最小コストパスに基づいて、各候補ノードｎ’のコストを決定する。８７５において、軌道を識別するインデックスｔは、インクリメントされ、方法８５０は、全ての軌道が処理されるまで繰り返される。

図９は、一実施形態による、一次エージェント１０２（例えば、自律車両、付属物あり又はなしのロボット等）が動作でき、一次エージェント１０２及び他のエージェント（例えば、動的物体Ａ１０４及び動的物体Ｂ１１２）が独立した軌道を有する環境１００の概略図である。動的物体（１０４、１１２）の軌道は、確率的にモデリングできる（例えば、Ｘ_Ａ及びＸ_Ｂ）。開示される実施形態では、動的物体Ａ１０４及び動的物体Ｂ１１２は、一次エージェント１０２及び環境中の他の全てのエージェント（互いを含む）の両方の移動に反応することができる。したがって、単純な軌道ではなく、潜在ポリシー又はゴールのモデリングとしてエージェントの意図を扱う各エージェントの挙動モデルが作成される。潜在ポリシー又はゴールは、エージェントが他のエージェントの軌道にどのように反応するかを決定するためにサンプリングできる形態を有する。一次エージェント１０２が現在の時間Ｔにおいてノードｎにある場合、システムは、他のエージェントが将来どこに存在するかを特定しようとする。他のエージェントのポリシーは、まず、開始ノードからノードｎまでの一次エージェントのパスに基づいて、一次エージェントの行動及び全ての二次エージェントの行動への二次エージェントの確率的反応を考慮に入れて、現在の時間Ｔまで順方向にシミュレートされる。したがって、所与の二次エージェントの確率的関数は、現在の時間までの一次エージェント及び二次エージェントの行動の少なくとも幾つかを表す。これは、現在の時間Ｔにおいて他のエージェントが占有する空間を示す結果を生成する。現在の時間Ｔにおける別のノードの場所は、現在の時間Ｔまで他の全てのエージェント及び一次エージェント１０２が辿った軌道に依存するため、これが該当する。

図１０は、第１の最小コストパス１０１０及び第２の最小コストパス１０２０の一例を示す、図９の一次エージェント１０２の一例の運動計画グラフ１０００である。第２の最小コストパス１０２０は、一実施形態により、現在のノード（例えば、ｎ_０）から候補ノード（例えば、ｎ_４）への第１の最小コストパス１０１０に沿った一次エージェント１０２の計画された移動後に計算される他のエージェントの確率的に特定された軌道に基づいて決定される。

実施形態では、格子中の各ノード（例えば、ｎ_０、ｎ_１、ｎ_２、・・・）は、そのノードと一次エージェント１０２のゴールとの間の格子のエッジに関連するコストに基づく関連する値（すなわちコスト）を有する。格子は、静的バックグラウンド衝突検出を実行して、静的物体（例えば、静的物体Ｃ１０８）と衝突するエッジを見つけることにより初期化される。そのような場合、コストは、静的物体と衝突することになり（例えば、ｎ_１４とｎ_１５との間のエッジ）、比較的高いコストになると決定されるエッジに割り当てられる（又はコスト関数を適用する）。例えば、コストは、無限大に設定され、それにより、効果的に、一次エージェント１０２の軌道が静的物体と衝突すると識別されたエッジを含まないようにする。格子の初期化の第２の態様では、例えば、対象のノードからゴールノード（例えば、ｎ_１５）への最小コストパスに基づいて、各ノードでのゴールへのコストが決定される。

実施形態では、他のエージェントＡ_ｊは、それぞれが自身の確率的挙動モデルを有するようにモデリングされる。あらゆるエージェントＡ_ｊについて、次の運動計画ステップは、他の全てのエージェント及び一次エージェント１０２により時間Ｔ＝０からとられた行動の確率関数Ｘ_ｊにより与えられる。確率関数Ｘ_ｊは、例えば、標準偏差、分散及び処理コスト／時間のような要因に基づいてｋ回サンプリングされる。

図１０に示されるグラフ１００を使用した一次エージェント１０２の運動計画は、ｎと示されたノード（例えば、ｎ_０）において時間Ｔ＝０から始まって実行される。各エージェントＡ_ｊについて、システムは、格子エッジが、一次エージェントが時間Ｔ＝１に存在することになるノードに移動するにあたり各エージェントと衝突する場合、何れの格子エッジがそうなるかを決定する。衝突エッジの値は、予測される実際の衝突のコストを測定し、衝突するエッジに高い値を割り当てるコスト関数を使用して変更される。変更されたエッジのコストに基づいて、各候補ノードｎ’（例えば、ｎ_３、ｎ_４、ｎ_５及びｎ_１）の値が計算される。現在のノード（例えば、ｎ_０）からゴール（例えば、ｎ_１５）までの最小コストパスは、各候補ノードｎ’を通して特定される。

計画のために、一次エージェント１０２が最小値の候補ノードｎ’に移動すると仮定され、これは、図１０に示される例ではノードｎ_４である。ノードｎ_４を通る最小コストパス１０１０は、例えば、ノードｎ_４、ｎ_８、ｎ_１２、ｎ_１６を通り、ノードｎ_１５（すなわちゴール）で終わるパスである。以下に更に詳細に説明するように、これは、運動計画グラフ１０００中の一次エージェント１０２の実際のパスではなく、単に計画されたパスである。換言すれば、この計画された移動により、運動計画システムにより運動命令が一次エージェント１０２に送信されることにはならない。

ノードｎ_４への一次エージェント１０２の計画された、すなわち仮説の移動は、確率的モデルにより決定される他のエージェントのパスに影響する。これは、一次エージェント１０２がノードｎ_０にある状態で時間Ｔ＝０において特定された最小コストパス１０１０が時間Ｔ＝１でもはや最小コストパスではないことがあることを意味する。上述した計算は、ノードｎ_４が一次エージェント１０２の現在のノードであり、ノードｎ_４からの新しい最小コストパス１０２０、例えばノードｎ_９、ｎ_１３、ｎ_１６を通り、ゴールであるノードｎ_１５で終わるパスが特定されるとの仮定下で繰り返される。計算は、一次エージェント１０２の計画ルートがゴール、例えばノードｎ_１５に到達するまで繰り返される。

一次エージェント１０２の計画された移動がこのようにマッピングされた後、運動計画グラフ１０００は、一次エージェントの環境中の他のエージェントのモデリングに使用された確率関数に基づく計画ルートに基づいてコストが計算されたエッジを有することになる。最小の値（すなわちコスト）を有する候補ノードｎ’が決定され、一次エージェント１０２は、現在のノードｎ_０から候補ノードｎ’（例えば、ｎ_３、ｎ_４、ｎ_５及びｎ_１）に移動する。運動計画グラフ１０００における一次エージェント１０２のこの実際の移動に続き、上述したプロセスは、次の時間ステップＴ＝Ｔ＋１における新しい現在のノードｎ（例えば、ｎ_３、ｎ_４、ｎ_５及びｎ_１）から繰り返される。

図１１Ａは、一実施形態による、計画グラフを介した一次エージェント１０２のパスを識別する方法１１００を示す流れ図であり、パスは、ゴールへの一次エージェント１０２の計画パス及び確率的モデルを使用して決定された他のエージェントのパスを考慮に入れた最小平均コストを有する候補ノードを通る。１１０５において、システムは、上述したように、静的バックグラウンド衝突検出を実行する。１１１０において、運動計画グラフ１０００の各ノードのゴールへのコストが計算される。１１１５において、システムは、各エージェントＡ_ｊの次のステップＸ_ｊの確率モデルを決定して、モデルの集合Ｓを生成する。１１２０において、システムは、図１１Ｂに更に説明され、対応する説明で以下に説明されるように、現在のノードｎからゴールまでの一次エージェント１０２の計画パス及び他のエージェントの確率的に決定されたパスに基づいて、各候補ノードｎ’の値を計算する。１１２５において、一次エージェント１０２は、現在のノードｎから、最小の値（すなわちコスト）を有する候補ノードｎ’に移動する。１１３０において、方法１１００は、次の時間ステップＴ＝Ｔ＋１に対して繰り返される。

図１１Ｂは、一実施形態による、ゴールへの一次エージェント１０２の計画パス及び確率モデルを使用して決定された他のエージェントのパスに基づいて各候補ノードの値を計算する、図１１Ａの方法１１００（ブロック１１２０）において有用な方法１１３５を示す流れ図である。１１４０において、システムは、図１１Ｃに更に説明され、対応する説明で以下に説明されるように、モデルの集合Ｓに基づいて他のエージェントＡ_ｊのサンプリングされた次のステップＸ_ｊに基づいて、各候補ノードｎ’の値を決定する。１１４２において、システムは、現在のノードｎ_０から、時間Ｔ＋１において最小値を有する候補ノードｎ’までの移動に基づいて、一次エージェント１０２の次の計画された位置を指定する。１１４４において、一次エージェント１０２が依然としてゴールノードにない場合、時間は、（１１４６において）インクリメントされ、方法１１３５は、次の時間ステップに対して繰り返される。一次エージェント１０２がゴールノードにある場合、処理は、方法１１００に戻る（ブロック１１２０に続く）。

図１１Ｃは、示される一実施形態による、確率モデルの集合Ｓに基づいて他のエージェントＡ_ｊのサンプリングされた次のステップＸ_ｊからのエッジ衝突コストに基づいて次の時間ステップＴ＋１における各候補ノードｎ’の値を決定する、図１１Ｂの方法１１３５（ブロック１１４０）において有用な方法１１５０を示す流れ図である。１１５５において、１エージェント当たりのサンプル数ｐに基づいて反復ループが開始される。１１６０において、反復ループが、他のエージェントの数ｊに基づいて開始される。１１６５において、システムは、モデルの集合Ｓに基づいてエージェントＡ_ｊの確率的な次のステップＸ_ｊの第ｋ番目のサンプルを決定する。１１７０において、システムは、時間Ｔ＋１においてエージェントＡ_ｊの決定された確率的な次のステップＸ_ｊと衝突する運動計画グラフ１０００のエッジがあれば、何れのエッジであるかを特定する。１１７５において、システムは、時間Ｔ＋１においてエージェントＡ_ｊの決定された確率的な次のステップＸ_ｊと衝突すると特定されたエッジがあれば、そのエッジの値にコスト関数を適用する。１１８０において、他のエージェントの反復ループは、他の全てのエージェントが処理されるまで繰り返される。１１８５において、他のエージェントの反復ループがｊ回完了した後、サンプルの反復ループは、全てのサンプルが完了するまで、すなわちｋ回完了するまで繰り返される。

先に説明したように、実装形態では、エージェントＡ_ｊの確率的挙動モデルは、各エージェントＡ_ｊの軌道が他の全てのエージェント及び一次エージェントの軌道に依存する点で相互依存する。したがって、全てのエージェントＡ_ｊ及び一次エージェントの現在及び過去の位置は、確率的挙動モデルに入力として提供されて、各エージェントＡ_ｊの予測される次のステップＸ_ｊを決定する。そうするにあたり、通常、窓、履歴又はルックバックに何らかの制限がある。したがって、（図１１Ｃに示される）プロセスの最も内側のループは、サンプリングが繰り返される前、全てのエージェントＡ_ｊの予測される次のステップＸ_ｊを特定するためのループである。このようにして、全てのサンプルは、全てのエージェントＡ_ｊ及び一次エージェントの同じ現在の位置に基づいて実行される。

上記の詳細な説明は、ブロック図、図式及び例を使用してデバイス及び／又はプロセスの種々の実施形態を記載した。そのようなブロック図、図式及び例が１つ又は複数の機能及び／又は動作を含む限り、そのようなブロック図、フローチャート又は例内の各機能及び／又は動作は、多様なハードウェア、ソフトウェア、ファームウェア又はそれらの実質的にあらゆる組合せにより、個々に及び／又は集合的に実施できることが当業者に理解されるであろう。一実施形態では、本趣旨は、特定用途向け集積回路（ＡＳＩＣ）及び／又はＦＰＧＡを介して実装さできる。しかしながら、本明細書に開示された実施形態は、全体的又は部分的に、１つ又は複数のコンピュータで実行される１つ又は複数のコンピュータプログラムとして（例えば、１つ又は複数のコンピュータシステムで実行される１つ又は複数のプログラムとして）、１つ又は複数のコントローラ（例えば、マイクロコントローラ）で実行される１つ又は複数のプログラムとして、１つ又は複数のプロセッサ（例えば、マイクロプロセッサ）で実行される１つ又は複数のプログラムとして、ファームウェアとして又はそれらの実質的にあらゆる組合せとして、標準集積回路において種々の異なる実装形態で実装することができ、回路を設計すること並びに／又はソフトウェア及び若しくはファームウェアのコードを記述することが十分に本開示に鑑みて当業者の技能内であることを当業者であれば認識するであろう。

本明細書に記載された方法又はアルゴリズムの多くが追加の動作を利用でき、幾つかの動作を省くことができ、及び／又は、指定されたものと異なる順序で動作を実行できることを当業者であれば認識するであろう。

加えて、本明細書に教示されるメカニズムは、様々な形態のプログラム製品として配布することが可能であり、例示的な実施形態は、配布を実際に実行するのに使用される信号記録媒体の特定のタイプに関係なく等しく適用されることを当業者であれば理解するであろう。信号記録媒体の例には、限定はされないが、ハードディスクドライブ等の記録可能なタイプの媒体、ＣＤ－ＲＯＭ及びコンピュータメモリがある。

上述した種々の実施形態は、組み合わされて更なる実施形態を提供することができる。「ＡＰＰＡＲＡＴＵＳ，ＭＥＴＨＯＤ，ＡＮＤ ＡＲＴＩＣＬＥ ＴＯ ＦＡＣＩＬＩＴＡＴＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＩＮ ＡＮ ＥＮＶＩＲＯＮＭＥＮＴ ＨＡＶＩＮＧ ＤＹＮＡＭＩＣ ＯＢＪＥＣＴＳ」という名称で２０１８年１２月４日付けにて出願された米国特許出願第６２／７７５，２５７、「ＡＰＰＡＲＡＴＵＳ，ＭＥＴＨＯＤ，ＡＮＤ ＡＲＴＩＣＬＥ ＴＯ ＦＡＣＩＬＩＴＡＴＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＯＦ ＡＮ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥ ＩＮ ＡＮ ＥＮＶＩＲＯＮＭＥＮＴ ＨＡＶＩＮＧ ＤＹＮＡＭＩＣ ＯＢＪＥＣＴＳ」という名称で２０１８年１月１２日付けにて出願された米国特許出願第６２／６１６，７８３、「ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＦＯＲ ＡＵＴＯＮＯＭＯＵＳ ＶＥＨＩＣＬＥＳ ＡＮＤ ＲＥＣＯＮＦＩＧＵＲＡＢＬＥ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＰＲＯＣＥＳＳＯＲＳ」という名称で２０１７年６月９日付けにて出願された国際特許出願ＰＣＴ／ＵＳ２０１７／０３６８８０、及び、「ＳＰＥＣＩＡＬＩＺＥＤ ＲＯＢＯＴ ＭＯＴＩＯＮ ＰＬＡＮＮＩＮＧ ＨＡＲＤＷＡＲＥ ＡＮＤ ＭＷＥＴＨＯＤＳ ＯＦ ＭＡＫＩＮＧ ＡＮＤ ＵＳＩＮＧ ＳＡＭＥ」という名称で２０１６年１月５日付けにて出願された国際特許出願公開ＷＯ２０１６／１２２８４０を含め、本明細書で引用され、及び／又は、出願データシートに列記される本願の譲受人に譲渡された米国出願公開、米国特許出願、外国特許及び外国特許出願の全ては、全体的に参照により本明細書に援用される。詳細に上述された説明に鑑みて、実施形態に対するこれら及び他の変更形態がなされうる。一般に、以下の特許請求の範囲では、使用される用語は、特許制球の範囲を、本明細書及び特許請求の範囲で開示される特定の実施形態に限定するものとして解釈されるべきではなく、そのような特許請求の範囲が権利を有する全範囲の均等物と共に可能な全ての実施形態を包含するものとして解釈されるべきである。

Claims (38)

1. 計画グラフを介して運動計画を実行するプロセッサベースのシステムにおける動作の運動計画方法であって、各計画グラフは、複数のノード及びエッジをそれぞれ含み、各ノードは、時間と、一次エージェントの状態を特徴付ける変数とを暗黙的又は明示的に表し、前記一次エージェントは、１つ又は複数の他のエージェントを含む環境中で動作し、各エッジは、前記ノードのそれぞれの対の間の遷移を表し、前記方法は、
   第１の計画グラフ中の現在のノードについて、
   前記１つ又は複数の他のエージェントの少なくとも１つの実際の又は将来の軌道をそれぞれ表す軌道の集合中の各軌道について、
   前記エッジの何れかが前記軌道と衝突する場合、前記第１の計画グラフの何れのエッジが前記軌道と衝突するかを特定することと、
   コスト関数を前記エッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することと、
   前記第１の計画グラフ中の現在のノードに前記第１の計画グラフの単一のエッジにより直接結合された前記第１の計画グラフ中の任意のノードである前記第１の計画グラフ中の複数の候補ノードのそれぞれについて、前記第１の計画グラフ内の現在のノードから直接候補ノードを通過し、その後前記第１の計画グラフ内のゴールノードに至る前記現在のノードから前記第１の計画グラフ中のゴールノードへの最小コストパスを、対応するパスに沿った前記候補ノードと前記ゴールノードとの間の複数の介在ノードを有するか有しない状態で、見つけることと、
   前記軌道の集合の前記軌道に関して、前記候補ノードのそれぞれの前記最小コストパスを見つけた後、
   前記候補ノードのそれぞれについて、全ての前記軌道にわたる前記候補ノードに対して各最小コストパスに関連付けられたコストの少なくとも一部に基づいて値を計算することと、
   計算された値の少なくとも一部に基づいて、前記候補ノードの１つを選択することと、
   を含む、運動計画方法。
2. コスト関数を前記エッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することは、
   少なくとも１つの軌道と衝突すると特定された前記エッジについて、当該エッジのコストを相対的に高い大きさに増大させて、特定された衝突を反映させることを含み、
   前記相対的に高い大きさは、少なくとも１つの他のエッジについて衝突の不在を反映する相対的に低い大きさよりも相対的に高い、請求項１に記載の運動計画方法。
3. コスト関数を前記エッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することは、
   少なくとも１つの軌道と衝突しないと特定された前記エッジについて、当該エッジのコストを相対的に高い大きさに増大させて、特定された衝突の不在を反映させることを含み、
   前記相対的に高い大きさは、少なくとも１つの他のエッジについて衝突を反映する相対的に低い大きさよりも相対的に高い、請求項１に記載の運動計画方法。
4. 前記環境中の他のエージェントの少なくとも１つについて、前記他のエージェントの将来の軌道を特定することと、
   前記他のエージェントの特定された実際の又は将来の軌道から前記軌道の集合を形成することと、
   を更に含む、請求項１に記載の運動計画方法。
5. 前記第１の計画グラフの単一のエッジにより前記第１の計画グラフ中の前記現在のノードに直接結合される前記第１の計画グラフ中の任意のノードである前記候補ノードに基づいて、前記第１の計画グラフの前記他のノードから前記第１の計画グラフ中の前記候補ノードを選択することを更に含む、請求項１に記載の運動計画方法。
6. 前記候補ノードのそれぞれについて、全ての前記軌道にわたる候補ノードに対して各最小コストパスに関連付けられたコストの少なくとも一部に基づいて値を計算することは、
   前記現在のノードから、前記候補ノードと、存在する場合には前記介在ノードの全てを経由して前記ゴールノードまで延びる各最小コストパスに関連づけられたコストの平均値を計算することを含む、請求項１に記載の運動計画方法。
7. 前記計算された値の少なくとも一部に基づいて、前記候補ノードの１つを選択することは、前記計算された値の全てのうちで最小の値を有する１つの候補ノードを選択することを含む、請求項１に記載の運動計画方法。
8. 選択された１つの前記候補ノードに基づいて、前記一次エージェントの軌道を更新することを更に含む、請求項１に記載の運動計画方法。
9. 前記コスト関数を前記エッジに適用して特定された衝突を反映する前に、前記第１の計画グラフを初期化することを更に含む、請求項１に記載の方法。
10. 前記第１の計画グラフを初期化することは、
    前記第１の計画グラフ中の各エッジについて、前記環境中の複数の静的物体のそれぞれに対する前記エッジの衝突評価を実行して、存在する場合に、前記エッジと前記静的物体との間の衝突を識別することを含む、請求項９に記載の方法。
11. 前記第１の計画グラフを初期化することは、
    前記静的物体の少なくとも１つと衝突すると評価される各エッジについて、コスト関数を当該エッジに適用して評価された衝突を反映するか、又は、前記第１の計画グラフから当該エッジを削除すること、
    を更に含む、請求項１０に記載の方法。
12. 前記第１の計画グラフを初期化することは、
    前記第１の計画グラフ中の各ノードについて、前記ノードから前記ゴールノードへのコストを計算することと、
    前記計算されたコストを当該ノードに論理的に関連付けることと、
    を更に含む、請求項９～１１の何れか一項に記載の方法。
13. 前記候補ノードの選択された１つを前記第１の計画グラフ中の新しい現在のノードとして割り当てることと、
    第１の計画グラフ中の前記新しい現在のノードについて、
    １つ又は複数の他のエージェントの少なくとも１つの実際の又は将来の軌道を表す軌道の集合中の各軌道について、
    前記エッジの何れかが前記軌道と衝突する場合、前記第１の計画グラフの何れのエッジが前記軌道と衝突するかを特定することと、
    コスト関数を前記エッジの１つ又は複数に適用して、特定された衝突又は衝突の不在の少なくとも一方を反映することと、
    前記第１の計画グラフ中の前記新しい現在のノードに前記第１の計画グラフの単一のエッジにより直接結合された前記第１の計画グラフ中の任意のノードである前記第１の計画グラフ中の複数の新しい候補ノードのそれぞれについて、前記第１の計画グラフ内の前記新しい現在のノードから直接前記新しい候補ノードを通過し、その後前記第１の計画グラフ内のゴールノードに至る前記新しい現在のノードから前記ゴールノードへの最小コストパスを、対応するパスに沿った前記新しい候補ノードと前記ゴールノードとの間の複数の介在ノードを有するか有しない状態で、見つけることと、
    前記軌道の集合の前記軌道に関して、前記新しい候補ノードのそれぞれの前記最小コストパスを見つけた後、
    前記新しい候補ノードのそれぞれについて、全ての前記軌道にわたる新しい候補ノードに対して各最小コストパスに関連付けられたコストの少なくとも一部に基づいて値を計算することと、
    前記計算された値の少なくとも一部に基づいて、前記新しい候補ノードの１つを選択することと、
    を更に含む、請求項１～１１の何れか一項に記載の方法。
14. 計画グラフを介して運動計画を実行するプロセッサベースのシステムであって、各計画グラフは、複数のノード及びエッジを含み、各ノードは、時間と、一次エージェントの状態を特徴付ける変数とを暗黙的又は明示的に表し、前記一次エージェントは、１つ又は複数の他のエージェントを含む環境中で動作し、各エッジは、前記ノードのそれぞれの対間の遷移を表し、前記システムは、
    少なくとも１つのプロセッサと、
    プロセッサが実行可能な命令又はデータの少なくとも１つを記憶する少なくとも１つの非一時的プロセッサ可読媒体と、
    を含み、前記プロセッサが実行可能な命令又はデータの少なくとも１つは、前記少なくとも１つのプロセッサによって実行されると、前記少なくとも１つのプロセッサに、請求項１～１３のいずれかに記載の方法を実行させる、
    プロセッサベースのシステム。
15. 状態を表すノードと、状態間の遷移を表すエッジと、を有するグラフを利用する運動計画システムにおける動作方法であって、
    少なくとも１つのプロセッサが、第１のグラフ中の現在のノードに対して利用可能な次のノードのそれぞれについて、前記現在のノードから前記次のノードを経由してゴールノードに到達するための代表コストを算出することと、
    少なくとも１つのプロセッサが、前記次のノードのそれぞれについて計算された代表コストに基づいて、次のノードを選択することと、
    少なくとも１つのプロセッサが、選択された次のノードの少なくとも一部に基づいて、移動の命令をすることと、を含み、
    前記代表コストは、環境中の１つ又は複数のエージェントのそれぞれの非決定的挙動に基づいて評価された前記環境中の前記１つ又は複数のエージェントとの衝突の確率に鑑みて、前記次のノードを経由した前記現在のノードから前記ゴールノードまでの利用可能なパスのそれぞれに関連付けられた代表コストを反映しており、
    前記エージェントは、位置、速度、軌道、又は形状のうちの１つ又は複数を経時変化させることができる、
    方法。
16. 前記次のノードを経由して前記現在のノードからゴールノードに到達するための代表コストを計算することは、
    前記次のノードを経由した前記現在のノードと前記ゴールノードとの間の将来のパスについて、
    前記将来のパスに沿った前記現在のノードと前記ゴールノードとの間の各エッジについて、
    代表コストを特定することと、
    各エッジに対して特定した代表コストを、前記将来のパスに沿った前記現在のノードと前記ゴールノードとの間の各エッジに割り当てることと、
    割り当てられ特定された代表コストの少なくとも一部に基づいて、前記次のノードを経由した前記現在のノードと前記ゴールノードとの間の前記将来のパスからの前記次のノードのための最小コストパスを特定することと、
    特定された最小コストパスを表す値を前記次のノードに割り当てることと
    を含む、請求項１５に記載の方法。
17. 割り当てられ特定された代表コストの一部に基づいて、前記次のノードを経由した前記現在のノードと前記ゴールノードとの間の前記将来のパスからの前記次のノードの最小コストパスを特定することは、
    前記現在のノードから前記次のノードに移動するコストを含む最小コストパスを特定することを含む、請求項１６に記載の方法。
18. 前記将来のパスに沿った前記現在のノードと前記ゴールノードとの間の各エッジについて代表コストを特定することは、
    前記将来のパスに沿った前記現在のノードと前記ゴールノードとの間の各エッジについて、
    前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することを含む、請求項１７に記載の方法。
19. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    前記将来のパスに沿った前記次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、前記環境中の前記１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す前記確率関数を取得することを含む、請求項１８に記載の方法。
20. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    現在のノードへの前記将来のパスに沿った前記次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、前記環境中の前記１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す前記確率関数を取得することを含み、
    前記現在のノードは、前記衝突のリスクの評価中に到達される前記将来のパスに沿った更なるノードである、請求項１８に記載の方法。
21. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    前記エージェントのそれぞれについて、前記エージェントの前記非決定的挙動を表す前記確率関数を繰り返し取得することを含む、請求項１８に記載の方法。
22. 前記それぞれのエージェントの前記非決定的挙動を表す前記確率関数を繰り返し取得することは、複数の繰り返しについて前記確率関数を繰り返し取得することを含み、
    前記繰り返しの総数は、前記命令を発生させなくてはならなくなる前に利用可能な時間量の少なくとも一部に基づいている、請求項２１に記載の方法。
23. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    前記エージェントのそれぞれについて、前記将来のパスに沿った前記次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、前記環境中の前記１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す前記確率関数を繰り返し取得することを含む、請求項１８に記載の方法。
24. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    前記エージェントのそれぞれについて、現在のノードへの前記将来のパスに沿った前記次のノードと各後続ノードとの間の各エッジによって表される一連の行動に鑑みて、前記環境中の前記１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す前記確率関数を繰り返し取得することを含み、
    前記現在のノードは、前記衝突のリスクの評価中に到達される、前記将来のパスに沿った更なるノードである、請求項１８に記載の方法。
25. 前記衝突のリスクを評価することは、前記将来のパスの移動のシミュレーションを含む、請求項１８に記載の方法。
26. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、
    専用リスク評価ハードウェアが、少なくとも前記環境中の前記１つ又は複数のエージェントのそれぞれの確率的に特定された軌道に基づいて、衝突のリスクを評価することを含み、
    前記代表コストは、評価された衝突のリスクの少なくとも一部に基づいている、請求項１８に記載の方法。
27. 前記環境中の１つ又は複数のエージェントのそれぞれの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することは、前記環境中のエージェントの少なくとも二次エージェントの前記非決定的挙動を表す１つ又は複数の確率関数に基づいて、前記環境中の前記１つ又は複数のエージェントとの衝突のリスクを評価することを含み、
    前記エージェントの一次エージェントは、運動計画が実行されているエージェントである、請求項１８に記載の方法。
28. 前記次のノードを経由して前記現在のノードからゴールノードに到達するための代表コストを計算する前に前記第１のグラフを初期化することを更に含む、請求項１５に記載の方法。
29. 前記第１のグラフを初期化することは、
    静的衝突評価を実行して、前記環境中の１つ又は複数の静的物体との衝突を識別することと、
    前記第１のグラフ中の各ノードについて、各ノードからゴールノードに到達するためのコストを計算することと、
    前記第１のグラフ中の各ノードについて、ゴールノードに到達するための計算されたコストを各ノードに論理的に関連付けることと、
    を含む、請求項２８に記載の方法。
30. 状態を表すノードと状態間の遷移を表すエッジとを有するグラフを利用する運動計画を実行するプロセッサベースのシステムであって、
    少なくとも１つのプロセッサと、
    プロセッサが実行可能な命令又はデータの少なくとも１つを記憶する少なくとも１つの非一時的プロセッサ可読媒体と、
    を含み、前記プロセッサが実行可能な命令又はデータの少なくとも１つは、前記少なくとも１つのプロセッサによって実行されると、前記少なくとも１つのプロセッサに、請求項１５～２９のいずれかに記載の方法を実行させる、
    プロセッサベースのシステム。
31. 状態を表すノードと、状態間の遷移を表すエッジとを有するグラフを利用して、一次エージェントの運動計画を生成する運動計画システムにおける動作の方法であって、
    ステップカウンタＴを開始値に初期化する（Ｔ＝０）ことと、
    第１のグラフを初期化することと、
    シミュレーションを実行することと、
    を含み、前記シミュレーションは、
    前記第１のグラフ中の現在のノードＮにおいて開始して、且つ前記第１のグラフ中のゴールノードではない間、
    １つ又は複数の取得の繰り返しについて、
    環境中の１つ又は複数の二次エージェントの各二次エージェントについて、前記ステップカウンタがインクリメントしたとき（Ｔ＋１、すなわち、次のステップ）に前記二次エージェントがとる行動を、前記ステップカウンタの前記開始値から現在値までに前記一次エージェント及び前記１つ又は複数の二次エージェントによってとられた行動を表す確率関数から取得することと、
    前記次の行動と衝突する前記第１のグラフのエッジを特定することと、
    前記次の行動と衝突するエッジについて、コスト関数を前記エッジに適用して、衝突条件の存在を反映することと、
    前記現在のノードに直接接続されるノードの集合のうちの前記第１のグラフ中の各ノードについて、前記現在のノードに直接接続される前記ノードを経由し、１つ又は複数の将来のパスを経由して前記現在のノードから前記ゴールノードまで１つ又は複数のパスを移動するための最小コストパスを表す値を計算することと、
    別の取得の繰り返しを実行するか否かを決定することと、
    別の取得の繰り返しを実行しないと決定した場合、
    前記現在のノードに直接接続される前記ノードの集合から、最小コストを有する、前記ノードの集合の前記ノードの１つを選択することと、
    前記ステップカウンタをインクリメントする（Ｔ＝Ｔ＋１）ことと、
    シミュレーションが前記ゴールノードにおけるものであるか否かを決定することと、
    前記シミュレーションが前記ゴールノードにおけるものではない場合、前記一次エージェントに命令することなく、選択されたノードを新しい現在のノードとして設定し、シミュレーションを継続することと、
    前記シミュレーションが前記ゴールノードにおけるものである場合、
    前記現在のノードに直接接続される前記ノードの集合から、最小コストを有するノードを選択することと、
    前記最小コストを有する選択されたノードの識別情報を提供して、前記一次エージェントの移動を命令することと、
    を含む、方法。
32. 前記ステップカウンタがインクリメントしたときに前記二次エージェントがとる行動を、前記ステップカウンタの前記開始値から現在値までに前記一次エージェント及び前記１つ又は複数の二次エージェントによってとられた行動を表す確率関数から取得することは、前記ゴールノードへのルートに沿った、前記現在のノードに直接接続された前記ノードと各後続ノードとの間の各エッジによって表される前記一次エージェントによってとられる一連の行動に鑑みて、前記環境中の前記１つ又は複数の二次エージェントのそれぞれの非決定的挙動を表す前記確率関数を取得することを含む、請求項３１に記載の方法。
33. 各エッジによって表される一連の行動に鑑みて、前記環境中の前記１つ又は複数のエージェントのそれぞれの非決定的挙動を表す前記確率関数を取得することは、前記エージェントのそれぞれについて、前記エージェントの非決定的挙動を表す前記確率関数を繰り返し取得することを含む、請求項３１に記載の方法。
34. 前記一次エージェントは、自律車両であり、
    前記方法は、
    前記自律車両が動作する前記環境を表す知覚情報を受信することと、
    前記自律車両により生成された運動計画を実施することと、
    を更に含む、請求項３１に記載の方法。
35. 知覚情報を受信することは、前記環境中の少なくとも１つの動的物体の位置及び軌道を表す知覚情報を受信することを含む、請求項３４に記載の方法。
36. 知覚情報を受信することは、運動プランナにおいて知覚情報を受信することを含み、前記知覚情報は、前記自律車両によって搬送される１つ又は複数のセンサを介して収集され、前記環境中の少なくとも１つの他の車両の位置又は軌道を表す、請求項３４に記載の方法。
37. 物体検出器により、前記１つ又は複数のセンサを介して収集された前記知覚情報から、少なくとも前記環境中の第１の動的物体を識別することを更に含む、請求項３６に記載の方法。
38. 状態を表すノードと、状態間の遷移を表すエッジとを有するグラフを利用して、一次エージェントの運動計画を生成する運動計画システムであって、
    少なくとも１つのプロセッサと、
    プロセッサにより実行可能な命令を記憶する少なくとも１つの非一時的プロセッサ可読媒体と、
    を含み、前記プロセッサにより実行可能な命令は、前記少なくとも１つのプロセッサによって実行されると、前記少なくとも１つのプロセッサに、請求項３１～３７のいずれかに記載の方法を実行させる、
    運動計画システム。

Images