JP2022030664A - 情報処理装置、情報処理方法、プログラム、情報処理システム、および、車両制御システム - Google Patents

Abstract

【課題】軌道の生成に要する時間を低減する。
【解決手段】実施形態の情報処理装置は、生成部と探索部と選択部とを備える。生成部は、対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために回避パターンが示す動作に対応する位置に複数のノードを生成する。探索部は、回避パターンごとに、複数のノードを接続する複数の軌道候補のうち移動コストが他の軌道候補より小さい軌道候補を探索する。選択部は、回避パターンごとに探索された１以上の軌道候補のうち、移動コストが他の軌道候補より小さい軌道候補を選択する。
【選択図】図２

Description

本発明の実施形態は、情報処理装置、情報処理方法、プログラム、情報処理システム、および、車両制御システムに関する。

自動車の操舵を自動で行う、自動運転技術が注目されている。例えば、障害物などの対象との衝突を回避する軌道を生成する技術が開示されている。また、走行可能領域内にノードを配置し、現在地から目的地まで複数のノードを順に経由する複数の軌道のうち、走行コストの低い軌道を探索する技術が開示されている。例えば、障害物の回避性能を上げるために、走行可能領域内に存在する障害物の周囲にノードを密にサンプリングする技術が提案されている。

特開２０１９－００６１４３号公報

しかしながら、従来技術では、障害物の周囲に一様に密にノードを配置する。このため、軌道の生成に要する時間が増大する場合があった。

実施形態の情報処理装置は、生成部と探索部と選択部とを備える。生成部は、対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために回避パターンが示す動作に対応する位置に複数のノードを生成する。探索部は、回避パターンごとに、複数のノードを接続する複数の軌道候補のうち移動コストが他の軌道候補より小さい軌道候補を探索する。選択部は、回避パターンごとに探索された１以上の軌道候補のうち、移動コストが他の軌道候補より小さい軌道候補を選択する。

移動体の一例を示す図。 移動体の一例を示すブロック図。 参照軌道の一例を示す模式図。 探索空間を示す模式図。 探索空間の説明図。 探索空間の説明図。 回避パターンを構成する動作の例を示す図。 回避パターンを構成する動作の例を示す図。 回避パターンを構成する動作の例を示す図。 回避パターンを構成する動作の例を示す図。 逸脱開始ノードに相当するＷＰ（Ｗａｙ Ｐｏｉｎｔ）の生成方法の一例を示す図。 逸脱終了ノードに相当するＷＰの生成方法の一例を示す図。 ＷＰの周囲に配置されるＷＰの一例を示す図。 新しい参照軌道の例を示す図。 追従完了ノードの生成方法の一例を示す図。 ＷＰの周囲に配置されるＷＰの一例を示す図。 再帰的な軌道候補の探索の様子を示す概念図。 回避パターンの出力例を示す図。 軌道生成処理のフローチャート。 障害物回避のための軌道生成処理のフローチャート。 障害物回避ルートの探索処理のフローチャート。 変形例の情報処理システムのブロック図。 実施形態の装置のハードウェア構成図。

以下に添付図面を参照して、情報処理装置、情報処理方法、プログラム、情報処理システム、および、車両制御システムを詳細に説明する。

図１は、本実施形態の移動体１０の一例を示す図である。

移動体１０（車両制御システムの一例）は、情報処理装置２０と、出力部１０Ａと、センサ１０Ｂと、入力装置１０Ｃと、動力制御部１０Ｇ（動力制御装置の一例）と、動力部１０Ｈと、を備える。

情報処理装置２０は、移動体１０の軌道を探索する（詳細後述）。情報処理装置２０は、例えば、専用または汎用コンピュータである。本実施形態では、情報処理装置２０が、移動体１０に搭載されている場合を一例として説明する。

移動体１０は、移動可能な物体である。移動体１０は、例えば、車両（自動二輪車、自動四輪車、自転車）、台車、ロボット、船舶、および、飛翔体（飛行機、無人航空機（ＵＡＶ：Ｕｎｍａｎｎｅｄ Ａｅｒｉａｌ Ｖｅｈｉｃｌｅ）など）である。移動体１０は、例えば、人による運転操作を介して走行する移動体、および、人による運転操作を介さずに自動的に走行（自律走行）可能な移動体である。自律走行可能な移動体は、例えば、自動運転車両である。本実施形態の移動体１０は、自律走行可能な車両である場合を一例として説明する。

なお、情報処理装置２０は、移動体１０に搭載された形態に限定されない。情報処理装置２０は、静止物に搭載されていてもよい。静止物は、移動不可能な物、および、地面に対して静止した状態の物である。静止物は、例えば、ガードレール、ポール、駐車車両、および、道路標識、などである。また、情報処理装置２０は、クラウド上で処理を実行するクラウドサーバに搭載されていてもよい。

出力部１０Ａは、各種情報を出力する。本実施形態では、出力部１０Ａは、出力情報を出力する。

出力部１０Ａは、例えば、出力情報を送信する通信機能、出力情報を表示する表示機能、および、出力情報を示す音を出力する音出力機能、などを備える。例えば、出力部１０Ａは、通信部１０Ｄと、ディスプレイ１０Ｅと、スピーカ１０Ｆと、を含む。

通信部１０Ｄは、外部装置と通信する。通信部１０Ｄは、ＶＩＣＳ（登録商標）通信回路およびダイナミックマップ通信回路などである。通信部１０Ｄは、出力情報を外部装置へ送信する。また、通信部１０Ｄは、道路情報などを外部装置から受信する。道路情報は、信号、標識、周囲の建物、各車線の道幅、および、レーン中心線などである。道路情報は、記憶部２０Ｂに記憶されていてもよい。

ディスプレイ１０Ｅは、出力情報を表示する。ディスプレイ１０Ｅは、例えば、公知のＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）、投影装置、および、ライトなどである。スピーカ１０Ｆは、出力情報を示す音を出力する。

センサ１０Ｂは、移動体１０の走行環境を取得するセンサである。走行環境は、例えば、移動体１０の観測情報、および、移動体１０の周辺情報である。センサ１０Ｂは、例えば、外界センサおよび内界センサである。

内界センサは、移動体１０の観測情報を観測するセンサである。観測情報は、移動体１０の加速度、移動体１０の速度、および、移動体１０の角速度、の少なくとも１つを含む。

内界センサは、例えば、慣性計測装置（ＩＭＵ：Ｉｎｅｒｔｉａｌ Ｍｅａｓｕｒｅｍｅｎｔ Ｕｎｉｔ）、加速度センサ、速度センサ、および、ロータリエンコーダ、などである。ＩＭＵは、移動体１０の三軸加速度および三軸角速度を含む観測情報を観測する。

外界センサは、移動体１０の周辺情報を観測する。外界センサは、移動体１０に搭載されていてもよいし、該移動体１０の外部（例えば、他の移動体および外部装置など）に搭載されていてもよい。

周辺情報は、移動体１０の周辺の状況を示す情報である。移動体１０の周辺とは、該移動体１０から予め定めた範囲内の領域である。この範囲は、外界センサの観測可能な範囲である。この範囲は、予め設定すればよい。

周辺情報は、例えば、移動体１０の周辺の撮影画像および距離情報の少なくとも一方である。なお、周辺情報は、移動体１０の位置情報を含んでいてもよい。撮影画像は、撮影によって得られる撮影画像データである（以下、単に、撮影画像と称する場合がある）。距離情報は、移動体１０から対象までの距離を示す情報である。対象は、外界における、外界センサによって観測可能な箇所である。位置情報は、相対位置であってもよいし、絶対位置であってもよい。

外界センサは、例えば、撮影によって撮影画像を得る撮影装置、距離センサ（ミリ波レーダ、レーザセンサ、距離画像センサ）、および、位置センサ（ＧＮＳＳ（Ｇｌｏｂａｌ Ｎａｖｉｇａｔｉｏｎ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）、無線通信装置）などである。

撮影画像は、画素ごとに画素値を規定したデジタル画像データ、および、画素ごとにセンサ１０Ｂからの距離を規定したデプスマップなどである。レーザセンサは、例えば、水平面に対して平行に設置された二次元ＬＩＤＡＲ（Ｌａｓｅｒ Ｉｍａｇｉｎｇ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｒａｎｇｉｎｇ）センサ、および、三次元ＬＩＤＡＲセンサである。

入力装置１０Ｃは、ユーザからの各種指示および情報入力を受け付ける。入力装置１０Ｃは、例えば、マウスおよびトラックボール等のポインティングデバイス、または、キーボード等の入力デバイスである。また、入力装置１０Ｃは、ディスプレイ１０Ｅと一体的に設けられたタッチパネルにおける入力機能であってもよい。

動力制御部１０Ｇは、動力部１０Ｈを制御する。動力部１０Ｈは、移動体１０に搭載された、駆動するデバイスである。動力部１０Ｈは、例えば、エンジン、モータ、車輪、などである。

動力部１０Ｈは、動力制御部１０Ｇの制御によって駆動する。例えば、動力制御部１０Ｇは、情報処理装置２０で生成された出力情報、および、センサ１０Ｂから得られた情報などに基づいて、周辺の状況を判断し、アクセル量、ブレーキ量、操舵角などの制御を行う。例えば、動力制御部１０Ｇは、情報処理装置２０で生成されたルートに従って移動体１０が移動するように、移動体１０の動力部１０Ｈを制御する。

次に、移動体１０の電気的構成について詳細に説明する。図２は、移動体１０の構成の一例を示すブロック図である。

移動体１０は、情報処理装置２０と、出力部１０Ａと、センサ１０Ｂと、入力装置１０Ｃと、動力制御部１０Ｇと、動力部１０Ｈと、を備える。出力部１０Ａは、上述したように、通信部１０Ｄと、ディスプレイ１０Ｅと、スピーカ１０Ｆと、を含む。

情報処理装置２０、出力部１０Ａ、センサ１０Ｂ、入力装置１０Ｃ、および動力制御部１０Ｇは、バス１０Ｊを介して接続されている。動力部１０Ｈは、動力制御部１０Ｇに接続されている。

情報処理装置２０は、記憶部２０Ｂと、処理部２０Ａと、を有する。すなわち、出力部１０Ａ、センサ１０Ｂ、入力装置１０Ｃ、動力制御部１０Ｇ、処理部２０Ａ、および記憶部２０Ｂは、バス１０Ｊを介して処理部２０Ａに接続されている。

なお、記憶部２０Ｂ、出力部１０Ａ（通信部１０Ｄ、ディスプレイ１０Ｅ、スピーカ１０Ｆ）、センサ１０Ｂ、入力装置１０Ｃ、および動力制御部１０Ｇ、の少なくとも１つは、有線または無線で処理部２０Ａに接続すればよい。また、記憶部２０Ｂ、出力部１０Ａ（通信部１０Ｄ、ディスプレイ１０Ｅ、スピーカ１０Ｆ）、センサ１０Ｂ、入力装置１０Ｃ、および動力制御部１０Ｇの少なくとも１つと、処理部２０Ａと、をネットワークを介して接続してもよい。

記憶部２０Ｂは、各種データを記憶する。記憶部２０Ｂは、例えば、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、フラッシュメモリ等の半導体メモリ素子、ハードディスク、および、光ディスク等である。なお、記憶部２０Ｂは、情報処理装置２０の外部に設けてもよい。また、記憶部２０Ｂは、移動体１０の外部に設けてもよい。例えば、記憶部２０Ｂを、クラウド上に設置されたサーバ装置に配置してもよい。

また、記憶部２０Ｂは、記憶媒体であってもよい。具体的には、記憶媒体は、プログラムおよび各種情報を、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）およびインターネットなどを介してダウンロードして記憶または一時記憶したものであってもよい。また、記憶部２０Ｂを、複数の記憶媒体から構成してもよい。

処理部２０Ａは、取得部２０Ｃと、生成部２０Ｄと、算出部２０Ｅと、追加部２０Ｆと、探索部２０Ｇと、選択部２０Ｈと、出力制御部２０Ｉと、を有する。

処理部２０Ａにおける各処理機能は、コンピュータによって実行可能なプログラムの形態で記憶部２０Ｂへ記憶されている。処理部２０Ａは、プログラムを記憶部２０Ｂから読出、実行することで、各プログラムに対応する機能部を実現するプロセッサである。

各プログラムを読み出した状態の処理部２０Ａは、図２の処理部２０Ａ内に示された各機能部を有することになる。図２においては単一の処理部２０Ａによって、取得部２０Ｃ、生成部２０Ｄ、算出部２０Ｅ、追加部２０Ｆ、探索部２０Ｇ、選択部２０Ｈ、および出力制御部２０Ｉが実現されるものとして説明する。

なお、各機能の各々を実現するための独立した複数のプロセッサを組み合わせて処理部２０Ａを構成してもよい。この場合、各プロセッサがプログラムを実行することにより各機能を実現する。また、各処理機能がプログラムとして構成され、１つの処理回路が各プログラムを実行する場合であってもよいし、特定の機能が専用の独立したプログラム実行回路に実装される場合であってもよい。

なお、本実施形態において用いる「プロセッサ」との文言は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＧＰＵ（Ｇｒａｐｈｉｃａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ：ＡＳＩＣ）、または、プログラマブル論理デバイス（例えば、単純プログラマブル論理デバイス（Ｓｉｍｐｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ：ＳＰＬＤ）、
複合プログラマブル論理デバイス（Ｃｏｍｐｌｅｘ Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ：ＣＰＬＤ）、および、フィールドプログラマブルゲートアレイ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ：ＦＰＧＡ））の回路を意味する。

プロセッサは、記憶部２０Ｂに保存されたプログラムを読み出し実行することで機能を実現する。なお、記憶部２０Ｂにプログラムを保存する代わりに、プロセッサの回路内にプログラムを直接組み込むよう構成しても構わない。この場合、プロセッサは回路内に組み込まれたプログラムを読み出し実行することで機能を実現する。

処理部２０Ａは、移動体１０の軌道が障害物などの対象と干渉する場合に、対象を回避する軌道を生成する。対象と干渉するとは、軌道に沿って移動体１０が走行したと仮定した場合に、対象に接触する、または、対象上を走行することを意味する。なお、処理部２０Ａが、対象がない場合の軌道を生成してもよい。

取得部２０Ｃは、情報処理装置２０で用いられる各種情報を取得する。例えば取得部２０Ｃは、参照軌道（ＲＴ：Reference Trajectory）、および、対象についての情報を取得する。対象についての情報は、例えば、対象の軌道の予測値を示す予測軌道である。参照軌道は、例えば上記のように処理部２０Ａにより生成された移動体１０の軌道である。

参照軌道は、移動体１０が移動するルートを表す位置情報と、移動する速度または時間を表す時間情報とにより表される。位置情報は、例えば、走行予定ルートである。また、時間情報は、例えば、走行予定ルート上の各位置で推奨される速度（推奨速度）、または、走行予定ルート上の各位置を通過する時間である。このように、参照軌道は、例えば、移動体１０が推奨速度を守って走行予定ルート上を走行する際の軌道に相当する。

走行予定ルートとは、移動体１０がある地点からある地点へ移動する際に通過する予定のルートである。例えば、走行予定ルートは、移動体１０が現在地から目的地へ移動する際に通過する予定のルートである。

具体的には、走行予定ルートは、ある地点（例えば、移動体１０の現在地）から他の地点（例えば、目的地）へ移動する際に通過する道路上を通る線と、によって構成される。道路上を通る線は、例えば、通過する道路の中央（移動方向に沿った車線の中央）を通る線である。

なお、走行予定ルートは、通過する道路の識別情報（以下、道路ＩＤと称する場合がある）を含んでもよい。

推奨速度は、移動体１０が移動するときに推奨される速度である。例えば、推奨速度は、法定速度、および、他のシステムが周囲の道路状況から判断される速度である。推奨速度は地点によって異なってもよいし、地点によらず一定でもよい。

図３は、参照軌道３０の一例を示す模式図である。参照軌道３０は、道路Ｒにおける走行可能領域Ｅの中央を通る線によって表される。走行可能領域Ｅは、移動体１０が走行可能な領域である。走行可能領域Ｅは、例えば、移動体１０が走行する車線に沿った領域である。

本実施形態では、参照軌道３０は、複数の参照ポイント３２（以下、ＷＰ（Ｗａｙ Ｐｏｉｎｔ）３２と称する）の群によって表される場合を説明する。ＷＰ３２は、位置（位置情報に相当）と、移動体１０の通過予定時間および通過予定速度の少なくとも一方（時間情報に相当）と、を規定した点である。ＷＰ３２は、さらに移動体１０の姿勢を含んでもよい。なお、ＷＰ３２は、点に代えてベクトルで表してもよい。

ＷＰ３２に規定される位置は、地図上の位置を示す。位置は、例えば、世界座標で表される。なお、位置は、移動体１０の現在位置に対する相対位置で表されてもよい。

ＷＰ３２に規定される通過予定時間は、移動体１０がＷＰ３２の位置を通過する予定の時刻を表す。通過予定時間は、特定の時間に対する相対時間であってもよいし、標準電波に応じた時刻であってもよい。

ＷＰ３２に規定される通過予定速度は、移動体１０がＷＰ３２の位置を通過する時の予定速度を表す。通過予定速度は、特定の速度に対する相対速度であってもよいし、絶対速度であってもよい。

図２に戻り説明を続ける。生成部２０Ｄは、移動体１０の軌道を探索するために用いるポイントを表すノードを生成する。本実施形態では、生成部２０Ｄは、１以上の回避パターンを用いてノードを生成する。回避パターンは、干渉する対象を回避するための移動体の１以上の動作を示すパターンである。例えば、生成部２０Ｄは、１以上の回避パターンに基づいて、参照軌道（第１軌道）上の対象（第１対象）を回避するために回避パターンが示す動作に対応する位置に複数のノードを生成する。回避パターンの詳細については後述する。

以下、生成部２０Ｄの機能についてさらに説明する。生成部２０Ｄは、探索空間に配置する参照軌道３０および対象の情報を取得部２０Ｃから受け取る。

対象は、移動体１０の走行を阻害する可能性のある物である。対象は、例えば、障害物である。障害物は、他の移動体、人および木などの生物、並びに、地面に設置された非生物（例えば、標識、信号、ガードレール等の各種の物体）などである。なお、対象は、障害物に限定されない。例えば、対象は、非障害物であってもよい。非障害物は、走行可能領域Ｅにおける、路面の悪化した領域などである。路面の悪化した領域は、例えば、水たまり、および、陥没した領域などである。また、非障害物は、走行禁止領域であってもよい。走行禁止領域とは、道路規則によって表される、走行の禁止された領域である。走行禁止領域は、例えば、追い越し禁止標識で規定される領域である。

図４は、探索空間４０を示す模式図である。探索空間４０は、二次元座標空間（ｓｄ座標空間）と、該二次元座標空間に直交する通過予定時間軸（ｔ）または通過予定速度軸（ｖ）と、で表される空間である。図４には、二次元座標空間に直交する座標軸として、通過予定時間軸（ｔ）が一例として示されている。

二次元座標空間は、参照軌道３０を移動する移動体１０の走行可能領域Ｅ（図３参照）に沿った、二次元平面の空間である。この二次元座標空間は、移動体１０の移動方向（参照軌道上に沿った方向、道なり方向）に沿ったｓ軸と、移動体１０の幅方向に沿ったｄ軸と、によって規定される。ｓ軸とｄ軸とは、直交配置されている。なお、ｓ軸は、参照軌道３０の延伸方向に一致する。また、幅方向は、ｓ軸に直交する方向である。

この二次元座標空間（ｓｄ座標空間）に直交する通過予定時間軸（ｔ）は、移動体１０の通過予定時間を示す座標軸である。

なお、上述したように、探索空間４０は、通過予定時間軸（ｔ）に代えて、通過予定速度軸（ｖ）を座標軸として表したものであってもよい。

生成部２０Ｄは、参照軌道３０を構成するＷＰ３２の規定内容に応じて、探索空間４０を生成すればよい。

例えば、参照軌道３０を構成するＷＰ３２が、位置と通過予定時間とを規定したものであると仮定する。この場合、生成部２０Ｄは、二次元座標空間（ｓｄ座標空間）と、通過予定時間軸（ｔ）と、を座標軸とする探索空間４０を生成すればよい。また、例えば、参照軌道３０を構成するＷＰ３２が、位置と通過予定速度とを規定したものであると仮定する。この場合、生成部２０Ｄは、二次元座標空間（ｓｄ座標空間）と、通過予定速度軸（ｖ）と、を座標軸とする探索空間４０を生成すればよい。

なお、生成部２０Ｄは、ｓｄ座標空間に代えて、世界座標のｘｙ座標空間またはｘｙｚ座標空間で探索空間４０を表してもよい。この場合、ｘｙ座標空間は、鉛直方向（標高）を示すｚ軸方向に直交する二次元平面である。

図５Ａおよび図５Ｂは、探索空間４０の二次元座標空間をｘｙ座標空間、および、ｓｄ座標空間でそれぞれ表した説明図である。図５Ａは、探索空間４０の二次元座標空間をｘｙ座標空間で表し、参照軌道３０を配置した一例である。図５Ｂは、探索空間４０の二次元座標空間をｓｄ座標空間で表し、参照軌道３０を配置した一例である。

移動体１０は、走行予定ルート上を推奨速度で走行しているとは限らない。移動体１０を走行予定ルート上に追従させるため、例えば処理部２０Ａは、走行予定ルートに追従し、追従後に推奨速度で走行予定ルート上を走行する軌道（以下、追従軌道という）を生成する。処理部２０Ａは、公知の方法（例えば“M. Werling et al.， “Optimal trajectories for timecritical street scenarios using discretized terminal manifolds”， The International Journal of Robotics Research、 vol．31、 No．3， pp．346-359， March 2012．”、以下参考文献１）を用いて追従軌道を算出すればよい。

なお、車線変更を実現する場合は、処理部２０Ａは、変更先の車線に移動された走行予定ルートに追従する追従軌道を生成する。

そして、処理部２０Ａは、参照軌道または追従軌道と、対象とが干渉するかを判定する。干渉する場合、処理部２０Ａは、対象を回避する軌道を生成する。対象を回避する軌道が生成されなかった場合、処理部２０Ａは、非常停止軌道を算出する。非常停止軌道は、制動距離で停止する軌道である。処理部２０Ａは、公知の方法（例えば参考文献１）を用いて非常停止軌道を生成することができる。

図２に戻り説明を続ける。生成部２０Ｄは、参照軌道または追従軌道が対象と干渉する位置（干渉位置）を算出する。次に、生成部２０Ｄは、参照軌道または追従軌道上のＷＰで、干渉位置との距離が最も近いＷＰを取得する。このＷＰは、図７等で後述するＷＰ３３に相当する。

ＷＰ３３は便宜的に参照軌道または追従軌道上のＷＰと一致させているだけなので、干渉位置をＷＰ３３に設定してもかまわない。

追従軌道が生成され、かつ、ＷＰ３３が走行予定ルート上にある場合（移動体１０が走行予定ルートに追従し、走行予定ルートに沿って走行中の場合）、追従軌道を参照軌道３０に設定する。

追従軌道が生成され、かつ、ＷＰ３３が走行予定ルートから逸脱している場合に（移動体１０が走行予定ルートに追従している最中に）対象と干渉する場合、走行予定ルートへの追従をキャンセルし、現在の移動体１０の位置から対象を回避する軌道を生成する。このため、参照軌道３０は変更されない。生成部２０Ｄは、変更しない参照軌道３０からＷＰ３３を選択する。

ＷＰ３３をもとに、生成部２０Ｄは、ノードの配置位置（サンプリング位置）を決定する。本実施形態では、ノードの数をより減少させるために、対象に対する移動体１０に特有の回避パターンに着目する。そして、その回避パターンに必要な領域のみにノードを配置（生成）する。

上記のように、回避パターンは、干渉する対象を回避するための移動体１０の１以上の動作を示すパターンであれば、どのようなパターンであってもよい。以下では、回避パターンとして、右追い越し、左追い越し、対象との干渉回避のための加減速、および、対象への追従、の４個を用いる例を説明する。

回避パターンは１～３個、５個以上であってもよい。例えば右追い越しおよび左追い越しは、対象の追い越しを示すパターンの一例であり、いずれか一方のみを用いてもよい。また、移動体１０が飛翔体である場合のように、左右以外から対象を追い越せる場合は、左右以外の方向からの追い越し（例えば、上からの追い越し、下からの追い越し）の回避パターンをさらに用いてもよい。

対象への追従とは、走行予定ルート上を対象と一定距離を保ちながら走行する回避パターンである。車線幅の右寄りを走行するなど、対象が走行予定ルートから逸脱する場合があるが、移動体１０は走行予定ルート上を走行する。

なお、追従（広義の追従）には、このような対象への追従の他、軌道（ルート）への追従が含まれる。軌道への追従は、ある軌道から逸脱している場合に、この軌道に合流し、その後この軌道に従って移動することを意味する。上記の追従軌道は、軌道への追従のために生成される軌道の例である。

干渉回避のための加減速とは、例えば交差点の右折、および、車線合流などで他の移動体（他の車両など）との干渉を回避するために、移動体１０が加速および減速の少なくとも一方を実行する回避パターンである。この回避パターンも対象への追従と同様に、移動体１０は走行予定ルート上を走行する。

一方、車線合流の回避パターンは定義しない。車線合流の場合、参照軌道が変更先の車線に移っている。その参照軌道に対して上記の４個の回避パターンを適用することにより、車線合流の軌道を生成できる。

次に、回避パターンを実現するための動作を定義する。回避パターンは、以下の４個の動作の少なくとも一部の組み合わせで表現することができる。
（Ａ１）参照軌道上の走行（ＲＴ走行）
（Ａ２）参照軌道からの逸脱（ＲＴ逸脱）
（Ａ３）新しい参照軌道への追従（新ＲＴ追従）
（Ａ４）新しい参照軌道上の走行（新ＲＴ走行）

新しい参照軌道とは、参照軌道を時間軸方向（ｔ軸方向）にオフセットした（ずらした）軌道をいう。新しい参照軌道が必要な理由は、参照軌道から逸脱すると、逸脱後のあるＷＰ３２の位置に到達する時刻がＷＰ３２より遅れたり早まったりするからである。

図６Ａ～図６Ｄを用いて、各回避パターンを構成する動作を説明する。図６Ａは、右追い越しを構成する動作の例を示す図である。図６Ｂは、左追い越しを構成する動作の例を示す図である。図６Ａおよび図６Ｂでは、車両である移動体１０が、他の車両である対象１２を追い越し、ゴール６０１に到達する例が示されている。ゴール６０１は、例えば、探索開始時から一定時間が経過後に到達する位置を示す。このように、軌道の探索は、一定時間を単位として実行することができる。

図６Ａおよび図６Ｂに示すように、右追い越しおよび左追い越しは、以下の順序で実行される動作を含む。
（Ａ１）対象の手前までは参照軌道上を走行（ＲＴ走行）
（Ａ２）対象の手前で追い越しのために参照軌道をｄ軸方向および時間軸方向（ｔ軸方向）に逸脱し、対象の真横で逸脱を完了し、対象を追い抜くまで参照軌道の延伸方向の軸と並行に移動（ＲＴ逸脱）
（Ａ３）対象を追い抜いた後に新しい参照軌道上に追従（新ＲＴ追従）
（Ａ４）新しい参照軌道上を走行（新ＲＴ走行）

このように、右追い越しおよび左追い越しを構成する動作は共通であり、対象の右側および左側のいずれから追い越すかが異なる。なお、対象を追い抜くとは、例えば、移動体１０の移動方向で対象より前方に到達することを意味する。

図６Ｃに示すように、対象への追従は、以下の順序で実行される動作を含む。新しい参照軌道は、対象の軌道を延伸方向に一定距離オフセットした軌道とする。
（Ａ１）対象の手前までは参照軌道上を走行（ＲＴ走行）
（Ａ３）新しい参照軌道への追従（新ＲＴ追従）
（Ａ４）新しい参照軌道上を走行（新ＲＴ走行）

図６Ｄに示すように、干渉回避のための加減速は、以下の順序で実行される動作を含む。
（Ａ１）対象の手前までは参照軌道を走行（ＲＴ走行）
（Ａ２）対象の手前で参照軌道の時間軸方向に逸脱（ＲＴ逸脱）
（Ａ３）逸脱後に新しい参照軌道に追従（新ＲＴ追従）
（Ａ４）新しい参照軌道上を走行（新ＲＴ走行）

生成部２０Ｄは、回避パターンに含まれる動作ごとに、各動作に対応するノードの位置を算出する。生成部２０Ｄは、例えば対象１２の位置を基点にしてノードの位置を算出する。

以下、各動作において、ノードの位置を算出する方法を説明する。なお、上記のＡ１（参照軌道上の走行）については、既に求められている参照軌道３０上を走行すればよいため、生成部２０Ｄは、新たにノードを生成する必要はない。

上記のＡ２（参照軌道からの逸脱）のためのノードの位置を算出する方法を説明する。この説明の前提条件として、移動体１０が参照軌道３０上を走行していることとする。逸脱のためのノードは、逸脱開始ノード、逸脱終了ノード、および、並走完了ノードを含む。

このように、１つの動作に対して、複数の種類のノードが生成される場合がある。生成部２０Ｄは、複数の種類のノードを、予め定められた順序で生成する。例えば生成部２０Ｄは、逸脱開始ノード、逸脱終了ノード、および、並走完了ノードの順にノードを生成する。

図７は、逸脱開始ノードに相当するＷＰ（ＷＰ３１）の生成方法の一例を示す図である。逸脱開始ノードは、参照軌道３０からの逸脱を開始するノードである。矢印７０１は、走行可能領域の幅を表す。図７では、対象１２は静止体である。静止しているため、対象１２は、時刻ｔによらずｓｄ座標空間内での位置が一定である。

一方、対象１２が移動体（移動体１０とは異なる移動体）である場合、ｓｄ座標空間内での移動体の位置は、時刻ｔによって離散的に変化する。具体的には、移動体は、ｔからｔ＋Δｔまではｔの位置で停止し、ｔ＋Δｔにｔ＋Δｔの位置へ瞬間移動し、ｔ＋Δｔからｔ＋２Δｔまでｔ＋Δｔの位置で停止する。Δｔは、干渉を判定するときに移動体１０が対象１２の間をすり抜けないような間隔に設定する。対象１２が移動体の場合であっても、逸脱開始ノードの生成方法は静止体と同じである。このため、移動体用の説明は省略する。

逸脱開始ノードは、ＷＰ３３よりＳ_ｏｐｔ１離れた位置に生成する。上記のように、ＷＰ３３は参照軌道３０上のＷＰのうち、干渉位置との距離が最も近いＷＰである。Ｓ_ｏｐｔ１は、例えば、ユーザによる入力装置１０Ｃの操作などによって、予め記憶部２０Ｂに記憶すればよい。

例えば、記憶部２０Ｂは、移動体１０の速度と、Ｓ_ｏｐｔ１の値と、を対応付けたルックアップテーブルを記憶する。生成部２０Ｄは、このようなルックアップテーブルにより、現在の移動体１０の速度に対応するＳ_ｏｐｔ１を求め、求めたＳ_ｏｐｔ１の値とＷＰ３３の位置とから、逸脱開始ノード（ＷＰ３１）を生成する。

回避パターンごとに異なるＳ_ｏｐｔ１の値を用いる場合は、回避パターンを特定する情報をさらに対応づけたルックアップテーブルを用いてもよい。また、後述する追従完了ノード（ＷＰ３７）の決定に用いるＳ_ｏｐｔ２の値を求めるルックアップテーブルと共通化する場合は、逸脱開始ノードおよび逸脱終了ノードのいずれを対象とするかを特定するための特定情報をさらに対応づけたルックアップテーブルを用いてもよい。特定情報は、例えば、参照軌道３０と対象１２（車両など）とが干渉する位置との距離が最も近いＷＰが、移動方向の手前側のＷＰであるＷＰ３３であるか、移動方向の奥側のＷＰであるＷＰ３４（図８参照）であるか、を示す情報である。

また、移動体１０の速度に代えて、回避方法（ゆったり回避、早急に回避）をルックアップテーブルに記憶してもよい。この場合、生成部２０Ｄは、例えば、ユーザによって入力された回避方法に対応するＳ_ｏｐｔ１を求め、求めたＳ_ｏｐｔ１の値とＷＰ３３の位置とから、逸脱開始ノード（ＷＰ３１）を生成する。

次に、逸脱終了ノードの生成方法の例を説明する。逸脱終了ノードは、逸脱を終了するノードである。逸脱終了ノードの生成方法は、回避パターンにより異なる。図８は、追い越しにおける逸脱終了ノードに相当するＷＰ（ＷＰ３５）の生成方法の一例を示す図である。

ＷＰ３５、および、後述するＷＰ３６（並走完了ノード）の生成のための中間情報として、対象１２を外接する直方体８０１が設定される。直方体８０１を設定する理由は、ｓ軸と並行に進む（道なりに進む）軌道を算出させ、移動体１０が交通の流れを乱さないようにするためである。

直方体８０１の頂点のｄ軸方向位置は、対象１２に外接する位置とする。直方体８０１の頂点のｓ軸方向位置は、ＷＰ３３およびＷＰ３４とする。直方体８０１の頂点のｔ軸方向位置は、対象１２のｔ軸方向位置と同じとする。ここで、ＷＰ３４は、参照軌道３０上のＷＰであって、対象１２と干渉しなくなった位置との距離が最も近いＷＰである。

ＷＰを、二次元座標空間（ｓｄ座標空間）と、時間軸（ｔ）と、を座標軸とする探索空間４０の座標（ｓ，ｄ，ｔ）で表す。また、ＷＰ３３およびＷＰ３４は、以下の（１）式および（２）式で表す。
ＷＰ３３＝（ｓ_ＷＰ３３，ｄ_ＷＰ３３，ｔ_ＷＰ３３） ・・・（１）
ＷＰ３４＝（ｓ_ＷＰ３４，ｄ_ＷＰ３４，ｔ_ＷＰ３４） ・・・（２）

追い越しにおける逸脱終了ノードＷＰ３５の位置は、ｓ軸およびｔ軸ではＷＰ３３と同じに設定し、ｄ軸では直方体８０１の端と走行可能領域の端との中点ｄ_ＷＰ３５に設定する。すなわち、ＷＰ３５は、以下の（３）式で表される。
ＷＰ３５＝（ｓ_ＷＰ３３、ｄ_ＷＰ３５、ｔ_ＷＰ３３） ・・・（３）

次に、干渉回避のための加減速における、逸脱終了ノードの生成方法について説明する。干渉回避のための加減速では、移動体１０はｄ軸方向には逸脱しない。そこで、逸脱終了ノードの位置は、ＷＰ３３と同じに設定する。加減速するためには、ＷＰ３３をさらにｔ軸方向にオフセットさせる必要がある。このオフセットについては後述する。

次に、並走完了ノードの生成方法について説明する。並走完了ノードとは、並走が完了する位置に配置されたノードである。並走とは、回避パターンが追い越しの際、移動体１０が、ＷＰ３５から対象１２を追い抜くまで道なりにかつ参照軌道３０と同じ速度（例えばＷＰ３５での速度）で走行することである。移動体１０の走行を道なりと等速に制限することで、ノード数を削減することができる。

並走完了ノードに相当するＷＰを以下ではＷＰ３６という。図８にＷＰ３６の例が示されている。並走完了ノードＷＰ３６の座標は、以下の（４）式で表される。
ＷＰ３６＝（ｓ_ＷＰ３４、ｄ_ＷＰ３５、ｔ_ＷＰ３４） ・・・（４）

ＷＰ３１、ＷＰ３５、および、ＷＰ３６は、ヒューリスティックに定義されるため、これらのＷＰに相当するノードよりふさわしいノードが存在する可能性がある。そこで、生成部２０Ｄは、これらのＷＰ（ノード）の周囲に新たなノードを配置する。

図９は、ＷＰ３１、ＷＰ３５、および、ＷＰ３６の周囲に配置されるＷＰの一例を示す図である。ＷＰ３１、ＷＰ３５、および、ＷＰ３６の周囲に配置されるＷＰを、それぞれＷＰ３１_ｏｆｆ、ＷＰ３５_ｏｆｆ、ＷＰ３６_ｏｆｆと表す。新たなＷＰを配置する方向は、回避パターンに含まれる動作の種類（Ａ１～Ａ４）によって異なる。

ＷＰ３１を以下の（５）式で表す。
ＷＰ３１＝（ｓ_ＷＰ３１，ｄ_ＷＰ３１，ｔ_ＷＰ３１） ・・・（５）

参照軌道からの逸脱（Ａ２）の開始までは参照軌道３０上を走行（Ａ１）するため、ＷＰ３１_ｏｆｆは、ＷＰ３１をｓ軸方向にオフセットした位置、および、ｔ軸方向にオフセットした位置に配置される。参照軌道３０からｔ軸方向にオフセットしたＷＰは、加速または減速を意味する。ＷＰ３１_ｏｆｆは、以下の（６）式により表される。
ＷＰ３１_ｏｆｆ＝（ｓ_ＷＰ３１＋ｎ_ｓ３１×ｐｓ_{ｗｐ３１ｏｆｆ}、ｄ_ＷＰ３１、ｔ_ＷＰ３１＋ｎ_ｔ３１×ｐｔ_{ｗｐ３１ｏｆｆ}） ・・・（６）

ｐｓ_{ｗｐ３１ｏｆｆ}、ｐｔ_{ｗｐ３１ｏｆｆ}は、ｓ軸方向、ｔ軸方向のオフセット間隔である。ｎ_ｓ３１、ｎ_ｔ３１は、オフセット個数に応じて決定される整数である。オフセット間隔およびオフセット個数は、例えばルックアップテーブルから取得するように構成することができる。ＷＰ３１の位置を中心としてｓ軸方向の前後１個ずつ、および、ｔ軸方向の前後１個ずつＷＰ３１_ｏｆｆを生成する場合、ｎ_ｓ３１、ｎ_ｔ３１は、例えば以下の組み合わせに示す値を取る。図９では、これらの値に従い生成された８個のＷＰ３１_ｏｆｆの例が示されている。
（ｎ_ｓ３１，ｎ_ｔ３１）＝（－１，－１）、（－１，０）、（－１，１）、（０，－１）、（０，１）、（１，－１）、（１，０）、（１，１）

参照軌道からの逸脱（Ａ２）した後のＷ３５およびＷ３６については、以下のようにして、新たに配置するＷＰを決定する。

ＷＰ３５_ｏｆｆは、ＷＰ３５をｄ軸方向にオフセットした位置、および、ｔ軸方向にオフセットした位置に配置される。ｄ軸方向に配置する理由は、対象１２と並走する際のｄ軸方向のオフセット量を調節するためである。ｔ軸方向に配置する理由は、移動体１０を加減速するためである。ｓ軸方向に配置しない理由は、ノード数の節約のためである。
ＷＰ３５_ｏｆｆは、以下の（７）式により表される。
ＷＰ３５_ｏｆｆ＝（ｓ_ＷＰ３３、ｄ_{ＷＰ３５ｏｆｆ}、ｔ_{ＷＰ３５ｏｆｆ}）、
ｄ_{ＷＰ３５ｏｆｆ}＝ｄ_ＷＰ３５＋ｎ_ｄ３５×ｐｄ_{ＷＰ３５ｏｆｆ}、
ｔ_{ＷＰ３５ｏｆｆ}＝ｔ_ＷＰ３３＋ｎ_ｔ３５×ｐｔ_{ＷＰ３５ｏｆｆ} ・・・（７）

ｐｄ_{ＷＰ３５ｏｆｆ}、ｐｔ_{ＷＰ３５ｏｆｆ}は、ｄ軸方向、ｔ軸方向のオフセット間隔である。ｎ_ｄ３５、ｎ_ｔ３５は、オフセット個数に応じて決定される整数である。ＷＰ３５の位置を中心としてｄ軸方向の前後１個ずつ、および、ｔ軸方向の前後に１個ずつＷＰ３５_ｏｆｆを生成する場合、ｎ_ｄ３５、ｎ_ｔ３５は、例えば以下の組み合わせに示す値を取る。
（ｎ_ｄ３５，ｎ_ｔ３５）＝（－１，－１）、（－１，０）、（－１，１）、（０，－１）、（０，１）、（１，－１）、（１，０）、（１，１）

ＷＰ３６_ｏｆｆは、ＷＰ３５_ｏｆｆと同じｄ座標を有し、ＷＰ３６と同じｓ座標を有する。ＷＰ３６_ｏｆｆは、以下の（８）式により表される。ｎ_ｔ３６は、オフセット個数に応じて決定される整数である。
ＷＰ３６_ｏｆｆ＝
（ｓ_ＷＰ３４、ｄ_{ＷＰ３５ｏｆｆ}、ｔ_ＷＰ３４＋ｎ_ｔ３６×ｐｔ_{ＷＰ３５ｏｆｆ}） ・・・（８）

次に、上記のＡ３（新しい参照軌道への追従）のためのノードの位置を算出する方法を説明する。Ａ３のためのノードは、追従完了ノードを含む。追従完了ノードは、新しい参照軌道への追従が完了するノードである。

追従完了ノードの算出に先立ち、新しい参照軌道の設定方法を説明する。新しい参照軌道は、参照軌道からの逸脱により生じた時刻方向のずれを解消するように設定される。

新しい参照軌道を算出するための基点は回避パターンにより異なる。追い越しの場合は、並走完了ノードＷＰ３６とＷＰ３６_ｏｆｆの中から選んだ１つのノードが基点となる。対象への追従の場合は、逸脱開始ノードＷＰ３１とＷＰ３１_ｏｆｆの中から選んだ１つのノードが基点となる。干渉回避のための加減速の場合は、逸脱終了ノードＷＰ３５とＷＰ３５_ｏｆｆの中から選んだ１つのノードが基点となる。

新しい参照軌道の算出方法は、追い越し、および、干渉回避のための加減速、の回避パターンで共通となる。以下では、追い越しの場合を例として説明する。図１０は、この場合の新しい参照軌道の例を示す図である。

参照軌道３０に含まれるＷＰ３２の座標を以下の（９）式で表す。
ＷＰ３２＝（ｓ_ＷＰ３２、ｄ_ＷＰ３２、ｔ_ＷＰ３２） ・・・（９）

ＷＰ３６_ｏｆｆを基点にして新しい参照軌道を設定する場合、新しい参照軌道のＷＰ３２_ｎの座標は以下の（１０）式で表される。
ＷＰ３２_ｎ＝（ｓ_ＷＰ３２、ｄ_ＷＰ３２、ｔ_ＷＰ３２＋ｎ_ｔ３６×ｐｔ_{ＷＰ３５ｏｆｆ}） ・・・（１０）

（１０）式に示すように、ＷＰ３２_ｎのｄ座標は参照軌道と同じであり、ＷＰ３６_ｏｆｆと同じではない。なお、ＷＰ３６を基点にする場合、時刻方向にオフセットしていないため、参照軌道と新しい参照軌道は同じになる。

対象への追従における新しい参照軌道は、対象の軌道から延伸方向に一定距離オフセットした軌道である。生成部２０Ｄは、対象への追従における新しい参照軌道の時刻ｔにおけるｓ座標ｓ_{ＷＰ３２ｎｆ}（ｔ）を、公知の方法（例えば“M. Werling et al.， “Optimal Trajectory Generation for Dynamic Street Scenarios in a Frenet Frame”， Proceedings - IEEE International Conference on Robotics and Automation ・ June 2010．”）に従い、例えば以下の（１１）式のように算出する。
ｓ_{ＷＰ３２ｎｆ}（ｔ）＝ｓ_ｌｖ（ｔ）－（Ｄ_０＋τ×ｖｓ_ｌｖ（ｔ）） ・・・（１１）

ｓ_ｌｖ（ｔ）は対象１２の位置であり、ｖｓ_ｌｖ（ｔ）は対象１２の速度であり、Ｄ_０およびτは定数である。なお、対象への追従における新しい参照軌道のｄ座標は、元の参照軌道と同じとする。

生成部２０Ｄは、この新しい参照軌道に追従するノードである追従完了ノードＷＰ３７を生成する。ＷＰ３７の生成方法は、逸脱開始ノードＷＰ３１の生成方法と同様とすることができる。例えば生成部２０Ｄは、ＷＰ３４よりＳ_ｏｐｔ２離れた位置に追従完了ノードを生成する。Ｓ_ｏｐｔ２は、Ｓ_ｏｐｔ１と同様に例えばルックアップテーブルにより求めることができる。図１１は、追従完了ノードＷＰ３７の生成方法の一例を示す図である。

そして、生成部２０Ｄは、追従完了ノードＷＰ３７の周囲にノードＷＰ３７_ｏｆｆを配置する。ＷＰ３７_ｏｆｆの配置方向は、逸脱開始ノードＷＰ３１の周囲に配置したノードＷＰ３１_ｏｆｆと同様に、ｓ軸方向とｔ軸方向とする。図１２は、ＷＰ３７の周囲に配置されるＷＰ３７_ｏｆｆの一例を示す図である。

上記のＡ４（新しい参照軌道上の走行）については、新しい参照軌道上を走行すればよいため、生成部２０Ｄは、新たにノードを生成する必要はない。

図２に戻り、算出部２０Ｅ、追加部２０Ｆ、探索部２０Ｇ、選択部２０Ｈ、および、出力制御部２０Ｉについて以下に説明する。

算出部２０Ｅは、生成されたノードそれぞれに対してコスト（エッジコスト）を算出する。例えば算出部２０Ｅは、生成されたノードごとに、１つ前のノードから当該ノードまでの軌道のコストを算出する。以下では、２つのノードを接続する軌道をエッジという場合がある。１つ前のノードとは、以下の順序に従い１つ前に生成されるノードである。
・動作の順序
・ある動作に対して複数の種類のノードが生成される場合、動作内でのノードの生成順序

最初の動作の場合は、１つ前のノードは、例えば移動体１０の現在の位置を示すルートノードである。２番目以降の動作の場合は、１つ前のノードは、例えば前の動作のノードである。ルートコストの詳細は後述する。ある動作に対して複数の種類のノードが生成される場合、１つ前のノードは、この動作内で定められた１つ前の生成順序で生成されるノードである。

まず算出部２０Ｅは、１つ前のノードと現在のノードとを接続する。例えば算出部２０Ｅは、逸脱開始ノードＷＰ３１とＷＰ３１_ｏｆｆとを含む複数のノードのうち１つのノードと、逸脱終了ノードＷＰ３５とＷＰ３５_ｏｆｆとを含む複数のノードのうち１つのノードと、接続する。算出部２０Ｅは、原則として、２つのノードのすべての組み合わせについて接続を行う。ただし、算出部２０Ｅは、逸脱終了ノードＷＰ３５とＷＰ３５_ｏｆｆとを含む複数のノードのうち１つのノードと、並走完了ノードＷＰ３６とＷＰ３６_ｏｆｆとを含む複数のノードのうち１つのノードと、を接続する場合は、ｄ座標が同じであり、かつ、ｔ座標のオフセット量が同じである２つのノードのみを接続する。移動体１０を道なりに参照軌道と同じ速度で走行させるためである。

次に、算出部２０Ｅは、ノードのコスト（エッジコスト）を算出する。ノードのコストとは、１つ前のノードと現在のノードとを結ぶエッジを、制御的な観点、運転規則的な観点、および、対象との干渉の観点から評価した値である。

制御的な観点のコストは、例えば、速度、加速度、および、躍度に基づくコストである。算出部２０Ｅは、例えば以下のような場合に評価が低くなるようにエッジコストを算出する。
・軌道を走行する移動体１０の加速度が上限値を超えている。
・軌道を走行する移動体１０の躍度が上限値を超えている。
・軌道長が０（すなわち、速度が０）である。

運転規則的な観点のコストは、例えば、参照軌道からの逸脱量に基づくコストである。算出部２０Ｅは、例えば以下のような場合に評価が低くなるようにエッジコストを算出する。
・移動体１０が、参照軌道で定められる走行方向とは逆の方向に走行する（バック走行）。
・走行可能領域の外部に軌道が存在する。

対象との干渉の観点からのコストは、移動体１０の軌道と対象１２の軌道との間の距離に基づくコストである。算出部２０Ｅは、例えば以下のような場合に評価が低くなるようにエッジコストを算出する。
・移動体１０の軌道と対象１２の軌道とが干渉する。

追加部２０Ｆは、算出されたエッジコストを参照して、探索空間にノードを追加する。例えば追加部２０Ｆは、算出されたエッジコストが予め定められた条件（第１条件）を満たすノードを探索空間に追加する。予め定められた条件は、例えば、評価が低いこと示す条件である。評価が低いこと示す条件は、例えば、エッジコストが閾値より大きい（評価が低い）ことを示す条件である。

探索部２０Ｇは、ノードが追加された探索空間を用いて、移動体が対象を回避する軌道を探索する。例えば探索部２０Ｇは、回避パターンごとに、探索空間に追加された複数のノードを接続する複数の軌道候補のうち、ルートコストが他の軌道候補より小さい軌道候補を探索する。コストが他の軌道候補より小さい軌道候補は、例えば、コストが最小の軌道候補である。

まず探索部２０Ｇは、移動体１０の現在の位置にルートノードを設定する。探索部２０Ｇは、回避パターンごとに、回避パターンを実現するための動作のうち、最初に実行する動作を決定する。決定された動作について、生成部２０Ｄによりノードが生成され、追加部２０Ｆにより生成されたノードのうち条件を満たすノードが探索空間に追加される。

探索部２０Ｇは、追加されたノードのルートコストを算出する。ルートコストとは、ルートノードから追加されたノードまでのエッジコストの合計である。ルートノードから追加されたノードまでのルートは、ルートコストが最小となるルートとする。探索部２０Ｇは、ルートコストが最小のルートを記憶する。そして、回避パターンの最後の動作であるＡ４（新しい参照軌道上の走行）までの処理が終了した場合に、その回避パターンに対する探索を終了する。最初の動作で用いたルートノードから、最後の動作についての最後のノードまでの軌道が、この回避パターンを実行するための軌道候補となる。

探索部２０Ｇは、残りの回避パターンについても同様に探索を実行する。各回避パターンについて、それぞれ軌道候補が選択される。

ある回避パターンの軌道候補（第２軌道）を探索している最中に、その軌道候補が新たな対象（第２対象）に干渉する場合がある。この場合、その対象のための新たな回避パターンを実行すれば干渉を回避できる可能性がある。そこで探索部２０Ｇは、すべての軌道のエッジコストが条件を満たさない場合、その回避パターンの探索を中止する。そして、第２対象に干渉した軌道が１つ以上ある場合、干渉する軌道の起点となるノードから、回避パターンの軌道候補を再帰的に探索する。

図１３は、再帰的な軌道候補の探索の様子を示す概念図である。例えば、障害物Ｏ１の左追い越しについての軌道候補を探索しているときに、障害物Ｏ２が干渉することが検知される。この場合、探索部２０Ｇは、障害物Ｏ２の干渉を回避するための軌道候補を再帰的に探索する。この探索時にさらに障害物Ｏ３またはＯ４が干渉することが検知されると、探索部２０Ｇは、さらに障害物Ｏ３またはＯ４の干渉を回避するための軌道候補を再帰的に探索する。

探索部２０Ｇは、干渉以外の理由で探索を中止してもよい。例えば、探索部２０Ｇは、探索空間に含まれるすべてのノードのエッジコストが予め定められた条件（第２条件）を満たす場合に、探索を中止すると判定する。予め定められた条件は、例えば、エッジコストが閾値より大きい（評価が低い）ことを示す条件である。

探索が中止された場合、生成部２０Ｄは、それ以降のノードの生成を中止する。すなわち生成部２０Ｄは、ノードを生成していない動作に対するノードの生成を中止する。不要なノードの生成を回避できるため、軌道の生成に要する時間を減少させることができる。

なお、取得部２０Ｃ、生成部２０Ｄ、算出部２０Ｅおよび追加部２０Ｆの機能のうち一部または全部は、探索部２０Ｇ内に備えられてもよい。

図２に戻り説明を続ける。選択部２０Ｈは、回避パターンごとに探索された１以上の軌道候補のうち、ルートコストが他の軌道候補より小さい軌道候補を選択する。また、選択部２０Ｈは、選択した軌道候補を用いて、曲線ルートを生成する。

例えば選択部２０Ｈは、各回避パターンに対して探索された軌道候補のルートコストを比較し、ルートコストが最小となる軌道候補を選択する。選択部２０Ｈは、選択した軌道候補の最後のノードからルートノードまで逆に辿り、ノード列（ルート）を得る。選択部２０Ｈは、ノード列に含まれる各ノードを結ぶ軌道を取得して接続することで、曲線ルートを生成する。

また選択部２０Ｈは、選択された軌道候補に対応する回避パターンも併せて取得する。

なお、静止物である対象１２に対して追従する軌道候補のルートコストが最小になる場合がある。移動体１０が静止物に追従すると、本来のゴールに到達する前に停止する。停止する理由は、新しい参照軌道が静止物からのオフセットで算出され、新しい参照軌道のゴールが本来のゴールより手前に設定されるからである。

静止物である対象１２に追従する軌道候補のルートコストが最小となった場合であっても、この軌道候補を選択部２０Ｈが選択しないように構成することが望ましい。そこで、選択部２０Ｈは、対象１２の速度を取得し、その速度がゼロの場合、本来のゴールに到達した軌道候補のうち、ルートコストが最小となる軌道候補を選択する。

図２に戻り説明を続ける。出力制御部２０Ｉは、選択部２０Ｈで生成された曲線ルートを示す出力情報を出力する。

出力制御部２０Ｉは、さらに、回避パターンを出力する。例えば出力制御部２０Ｉは、回避パターンをディスプレイ１０Ｅに表示する。図１４は、ディスプレイ１０Ｅに表示される回避パターンの出力例を示す図である。

図１４では、想定される移動体１０の移動状況１４０１と、この移動状況１４０１に対して表示される回避パターン１４１０の例が示されている。回避パターン１４１０内の破線は、移動体１２Ａを右から追い越して走行予定ルートに戻った後で移動体１２Ｃに追従する際の曲線ルートを示す。矩形１４１２Ａ、矩形１４１２Ｂ、および、矩形１４１２Ｃは、それぞれ移動体１２Ａ、移動体１２Ｂ、および、移動体１２Ｃの予想軌跡を示す。さらに、回避パターン名を曲線ルート上に合わせて表示してもよい。

また、出力制御部２０Ｉは、回避パターンを示す音を出力するようにスピーカ１０Ｆを制御してもよい。また、出力制御部２０Ｉは、回避パターンを、通信部１０Ｄを介して外部装置へ出力してもよい。また、出力制御部２０Ｉは、出力情報を、記憶部２０Ｂへ記憶してもよい。

出力制御部２０Ｉは、曲線ルートを示す出力情報を、移動体１０の動力部１０Ｈを制御する動力制御部１０Ｇへ出力する。

詳細には、出力制御部２０Ｉは、曲線ルートを、動力制御部１０Ｇおよび出力部１０Ａの少なくとも一方へ出力する。

まず、出力制御部２０Ｉが、曲線ルートを出力部１０Ａへ出力する場合を説明する。例えば、出力制御部２０Ｉは、回避パターン名と曲線ルートの１つ以上を含む出力情報を、ディスプレイ１０Ｅに表示する。また、出力制御部２０Ｉは、曲線ルートを示す音を出力するようにスピーカ１０Ｆを制御してもよい。また、出力制御部２０Ｉは、回避パターン名と曲線ルートの１つ以上を示す出力情報を、通信部１０Ｄを介して外部装置へ出力してもよい。また、出力制御部２０Ｉは、出力情報を、記憶部２０Ｂへ記憶してもよい。

次に、出力制御部２０Ｉが、曲線ルートを示す出力情報を動力制御部１０Ｇへ出力する場合を説明する。この場合、動力制御部１０Ｇは、出力制御部２０Ｉから受付けた曲線ルートに応じて、動力部１０Ｈを制御する。

例えば、動力制御部１０Ｇは、曲線ルートを用いて、動力部１０Ｈを制御するための動力制御信号を生成し、動力部１０Ｈを制御する。動力制御信号は、動力部１０Ｈにおける、移動体１０の走行に関する駆動を行う駆動部を制御するための制御信号である。動力制御信号は、操舵角およびアクセル量、などを調整するための制御信号を含む。

具体的には、動力制御部１０Ｇは、移動体１０の現在位置、姿勢、および速度を、センサ１０Ｂから取得する。

そして、動力制御部１０Ｇは、センサ１０Ｂから取得したこれらの情報と、曲線ルートと、を用いて、曲線ルートと移動体１０の現在位置との偏差がゼロとなるように、動力制御信号を生成し、動力部１０Ｈへ出力する。

これによって、動力制御部１０Ｇは、曲線ルートに沿った走行を行うように、動力部１０Ｈ（移動体１０の操舵、エンジンなど）を制御する。このため、移動体１０は、曲線ルートに応じたルートに沿って走行する。

なお、曲線ルートから動力制御信号を生成する処理の少なくとも一部を、出力制御部２０Ｉ側で行ってもよい。

次に、処理部２０Ａが実行する情報処理の手順を説明する。図１５は、軌道生成処理の一例を示すフローチャートである。以下では、対象１２が障害物である場合を例に説明する。軌道生成処理は、参照軌道に従って移動体１０の軌道を生成する処理である。参照軌道が障害物と干渉する場合は、障害物を回避するような軌道が生成される。周囲の状況の変化に対応するため、軌道生成処理は、例えば一定時間が経過するごとに実行される。

例えば処理部２０Ａは、取得部２０Ｃにより取得された参照軌道に追従する軌道を生成する（ステップＳ１０１）。処理部２０Ａは、参照軌道が障害物と干渉するか否かを判定する（ステップＳ１０２）。参照軌道が障害物と干渉しない場合（ステップＳ１０２：Ｎｏ）、処理部２０Ａは処理を終了する。

なお移動体１０は、ステップＳ１０１で生成された軌道に従い走行するように制御される。また、上記のように、一定時間が経過するごとに軌道生成処理が実行され、生成された軌道に従い移動体１０が走行する。

参照軌道が障害物と干渉する場合（ステップＳ１０２：Ｙｅｓ）、障害物回避のための軌道生成処理が実行される（ステップＳ１０３）。障害物回避のための軌道生成処理の詳細は後述する。

処理部２０Ａは、障害物回避のための軌道生成処理により軌道が生成されたか否かを判定する（ステップＳ１０４）。軌道が生成されなかった場合（ステップＳ１０４：Ｎｏ）、処理部２０Ａは、非常停止軌道を生成する（ステップＳ１０５）。非常停止軌道は、障害物との衝突などを回避するために移動体１０を停止させるための軌道である。移動体１０は、非常停止軌道に従い非常停止するように制御される。

軌道が生成された場合（ステップＳ１０４；Ｙｅｓ）、処理部２０Ａは軌道生成処理を終了する。移動体１０は、ステップＳ１０３で生成された軌道に従い走行するように制御される。

次に、ステップＳ１０３の障害物回避のための軌道生成処理について説明する。図１６は、障害物回避のための軌道生成処理の一例を示すフローチャートである。

取得部２０Ｃは、参照軌道３０を取得する（ステップＳ２０１）。取得部２０Ｃは、１以上の障害物を含む障害物群である対象１２の情報を取得する（ステップＳ２０２）。生成部２０Ｄは、探索空間４０に、参照軌道３０および対象１２を配置する（ステップＳ２０３）。

処理部２０Ａは、回避する障害物を決定する（ステップＳ２０４）。例えば処理部２０Ａは、障害物群に含まれる障害物のうち、参照軌道３０と干渉する障害物を、回避する障害物と決定する。複数の障害物が参照軌道３０と干渉しうる場合は、処理部２０Ａは、移動体１０により近い障害物を回避する障害物として決定する。

処理部２０Ａは、決定した障害物の回避ルートの探索処理を実行する（ステップＳ２０５）。障害物回避ルートの探索処理の詳細は後述する。

選択部２０Ｈは、障害物回避ルートの探索処理で探索された１以上の軌道候補のうち、ルートコストが最小となる軌道候補を選択する。そして選択部２０Ｈは、選択した軌道候補の最後のノードからルートノードまで逆に辿り、ノード列（ルート）を得る（ステップＳ２０６）。選択部２０Ｈは、ノード列に含まれる各ノードを結ぶ軌道を取得して接続し、曲線ルートを生成する（ステップＳ２０７）。

次に、ステップＳ２０５の障害物回避ルートの探索処理の詳細について説明する。図１７は、障害物回避ルートの探索処理の一例を示すフローチャートである。

生成部２０Ｄは、探索の対象とする回避パターンを決定する（ステップＳ３０１）。上記のような４個の回避パターンを用いる場合、生成部２０Ｄは、４個の回避パターンから１つを決定する。

生成部２０Ｄは、決定した回避パターンに含まれる動作のうち、探索の対象とする動作を決定する（ステップＳ３０２）。上記のように、各回避パターンには、複数の動作が、処理の順序とともに定められている。生成部２０Ｄは、処理の順序に従って対象とする動作を決定する。

生成部２０Ｄは、決定した動作に対応するノードの位置を算出し、算出した位置にノードを生成する（ステップＳ３０３）。

探索部２０Ｇは、基点ノードとノード群の各ノードとを接続する軌道（エッジ）を生成する（ステップＳ３０４）。基点ノードは、例えば、前の動作のノード群のうちの１つである。最初の動作の場合は、基点ノードは、移動体１０の現在の位置を示すルートノードである。

算出部２０Ｅは、生成された各ノードに対するコストとして、生成されたエッジのコスト（エッジコスト）を算出する（ステップＳ３０５）。

追加部２０Ｆは、生成した軌道（エッジ）が、エッジコストが条件（条件は、障害物と干渉しないことを示す条件を含む）を満たすノードが１つ以上存在するかを判定する（ステップＳ３０６）。１つ以上存在する場合（ステップＳ３０６：Ｙｅｓ）、追加部２０Ｆは、算出されたエッジコストが予め定められた条件を満たすノードを探索空間に追加する（ステップＳ３０７）。探索部２０Ｇは、追加されたノードのルートコストを算出する（ステップＳ３０８）。

探索部２０Ｇは、現在の回避パターンに含まれるすべての動作を処理したか否かを判定する（ステップＳ３０９）。すべての動作を処理していない場合（ステップＳ３０９：Ｎｏ）、ステップＳ３０２に戻り、次の順序の動作に対して処理が繰り返される。

ステップＳ３０６で、エッジコストが条件を満たすノードが１つも存在しないと判定された場合（ステップＳ３０６：Ｎｏ）、探索部２０Ｇは、生成した軌道の１つ以上が他の障害物と干渉するか否かを判定する（ステップＳ３１０）。生成した軌道の１つ以上が他の障害物と干渉すると判定された場合（ステップＳ３１０：Ｙｅｓ）、この障害物を回避するための障害物回避ルートの探索処理が再帰的に実行される。すなわち、処理部２０Ａは、干渉すると判定された他の障害物を、回避する障害物として決定する（ステップＳ３１１）。処理部２０Ａは、決定した障害物の回避ルートの探索処理を実行する（ステップＳ３１２）。

ステップＳ３０４で生成した軌道（エッジ）の始点のノード（群）の中からルートコストが最小となるノードが、再帰的な探索処理の基点ノードとなる。

すべての動作を処理した場合（ステップＳ３０９：Ｙｅｓ）、および、他の障害物と干渉しないと判定された場合（ステップＳ３１０：Ｎｏ）、探索部２０Ｇは、すべての回避パターンを処理したか否かを判定する（ステップＳ３１３）。すべての回避パターンを処理していない場合（ステップＳ３１３：Ｎｏ）、ステップＳ３０１に戻り、次の回避パターンに対して処理が繰り返される。

すべての回避パターンを処理した場合（ステップＳ３１３：Ｙｅｓ）、障害物回避ルートの探索処理を終了する。

以上のように、本実施形態の情報処理装置２０は、回避パターンに必要な領域のみにノードを生成する。このため、対象の周囲の特定の領域にノードを配置する従来の方式に比べて、処理時間の短縮および処理負荷の軽減を図ることができる。

（変形例）
ノードの位置を決定するための各種情報（例えば、Ｓ_ｏｐｔ１、Ｓ_ｏｐｔ２、オフセット間隔、および、オフセット個数）は、事前の学習処理により値が決定されてもよい。図１８は、学習処理を実行するように構成された、変形例の情報処理システムの機能構成例を示すブロック図である。図１８に示すように、情報処理システムは、学習装置１００と、移動体１０と、がネットワーク２００を介して接続された構成となっている。

ネットワーク２００は、インターネット、および、ＬＡＮ（ローカルエリアネットワーク）などの、どのような形態のネットワークであってもよい。またネットワークは、無線ネットワークおよび有線ネットワークのいずれでもよいし、両者が混在したネットワークであってもよい。

移動体１０は、上記実施形態の移動体１０と同じであるため同一の符号を付し説明を省略する。

学習装置１００は、学習部１０１と、通信制御部１０２と、記憶部１２１と、を備えている。

学習部１０１は、移動体１０（生成部２０Ｄ）がノードを生成するための用いる情報を学習により求める。ノードを生成するための用いる情報は、例えば、Ｓ_ｏｐｔ１、Ｓ_ｏｐｔ２、オフセット間隔、および、オフセット個数の一部または全部である。学習部１０１は、学習により求められた値を対応づけたルックアップテーブルを作成してもよい。

以下では、移動体１０の速度に応じたＳ_ｏｐｔ１を学習により求める場合を例に説明する。例えば学習部１０１は、速度を入力してＳ_ｏｐｔ１の値を出力する機械学習モデルを学習する。機械学習モデルは、例えばニューラルネットワークモデルであるが、その他のどのような構造のモデルであってもよい。

学習方法は、機械学習モデルに応じたどのような方法であってもよい。例えば、学習データを用いた教師あり学習、および、強化学習などを適用することができる。学習データは、例えば熟練した運転者による運転時のログ情報に基づき生成される。

通信制御部１０２は、移動体１０などの外部装置との間の通信を制御する。例えば通信制御部１０２は、学習部１０１により求められた情報（例えばルックアップテーブル）を、移動体１０に送信する。移動体１０では、例えば通信部１０Ｄが、送信されたルックアップテーブルなどの情報を受信する。生成部２０Ｄは、受信されたルックアップテーブルを用いてノードを生成する。

記憶部１２１は、学習装置１００で実行される各種処理で用いられる各種情報を記憶する。例えば記憶部１２１は、機械学習モデルを表す情報、学習に用いられる学習データ、および、学習により得られた情報などを記憶する。

上記各部（学習部１０１、および、通信制御部１０２）は、例えば、１または複数のプロセッサにより実現される。例えば上記各部は、ＣＰＵなどのプロセッサにプログラムを実行させること、すなわちソフトウェアにより実現してもよい。上記各部は、専用のＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などのプロセッサ、すなわちハードウェアにより実現してもよい。上記各部は、ソフトウェアおよびハードウェアを併用して実現してもよい。複数のプロセッサを用いる場合、各プロセッサは、各部のうち１つを実現してもよいし、各部のうち２以上を実現してもよい。

記憶部１２１は、フラッシュメモリ、メモリカード、ＲＡＭ、ＨＤＤ（ハードディスクドライブ）、および、光ディスクなどの一般的に利用されているあらゆる記憶媒体により構成することができる。

次に、上記実施形態の各装置（情報処理装置、学習装置）の、ハードウェア構成の一例を説明する。図１９は、上記実施形態の装置のハードウェア構成図の一例である。

上記実施形態の装置は、ＣＰＵ８６などの制御装置と、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）８８やＲＡＭ９０やＨＤＤ９２などの記憶装置と、各種機器とのインターフェースであるＩ／Ｆ部８２と、出力情報などの各種情報を出力する出力部８０と、ユーザによる操作を受付ける入力部９４と、各部を接続するバス９６とを備えており、通常のコンピュータを利用したハードウェア構成となっている。

上記実施形態の装置では、ＣＰＵ８６が、ＲＯＭ８８からプログラムをＲＡＭ９０上に読み出して実行することにより、上記各機能がコンピュータ上で実現される。

なお、上記実施形態の装置で実行される上記各処理を実行するためのプログラムは、ＨＤＤ９２に記憶されていてもよい。また、上記実施形態の装置で実行される上記各処理を実行するためのプログラムは、ＲＯＭ８８に予め組み込まれて提供されていてもよい。

また、上記実施形態の装置で実行される上記処理を実行するためのプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ－ＲＯＭ、ＣＤ－Ｒ、メモリカード、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、フレキシブルディスク（ＦＤ）等のコンピュータで読み取り可能な記憶媒体に記憶されてコンピュータプログラムプロダクトとして提供されるようにしてもよい。また、上記実施形態の装置で実行される上記処理を実行するためのプログラムを、インターネットなどのネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するようにしてもよい。また、上記実施形態の装置で実行される上記処理を実行するためのプログラムを、インターネットなどのネットワーク経由で提供または配布するようにしてもよい。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１０ 移動体
１０Ｇ 動力制御部
１０Ｈ 動力部
２０ 情報処理装置
２０Ａ 処理部
２０Ｂ 記憶部
２０Ｃ 取得部
２０Ｄ 生成部
２０Ｅ 算出部
２０Ｆ 追加部
２０Ｇ 探索部
２０Ｈ 選択部
２０Ｉ 出力制御部
３０ 参照軌道
１００ 学習装置
１０１ 学習部
１０２ 通信制御部
１２１ 記憶部
２００ ネットワーク

Claims (14)

1. 対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成する生成部と、
   前記回避パターンごとに、複数の前記ノードを接続する複数の軌道候補のうち移動コストが他の前記軌道候補より小さい前記軌道候補を探索する探索部と、
   前記回避パターンごとに探索された１以上の前記軌道候補のうち、前記移動コストが他の前記軌道候補より小さい前記軌道候補を選択する選択部と、
   を備える情報処理装置。
2. 前記生成部は、前記探索部が探索する前記軌道候補である第２軌道上に第２対象が存在する場合に、前記第２軌道上の前記第２対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成し、
   前記探索部は、前記第２軌道に対して生成された複数の前記ノードを接続する複数の軌道候補のうち前記移動コストが他の前記軌道候補より小さい前記軌道候補を探索する、
   請求項１に記載の情報処理装置。
3. 前記ノードごとに、接続される他のノードから前記ノードまでの軌道のコストを算出する算出部と、
   前記コストが予め定められた第１条件を満たす前記ノードを、前記探索部が前記軌道候補を探索空間に追加する追加部と、をさらに備え、
   前記探索部は、前記探索空間に含まれる複数の前記ノードを接続する複数の前記軌道候補のうち前記移動コストが他の前記軌道候補より小さい前記軌道候補を探索する、
   請求項１に記載の情報処理装置。
4. 前記動作は、
   走行予定ルートを表す位置情報と、走行予定ルート上の各位置での速度または走行予定ルート上の各位置を通過する時間である時間情報と、により表される参照軌道上の走行、
   前記参照軌道からの逸脱と、新しい参照軌道への追従と、の少なくとも一方、および、
   新しい参照軌道上の走行、を含む、
   請求項１に記載の情報処理装置。
5. 前記回避パターンは、
   前記対象の追い越し、
   前記対象との干渉回避のための加減速、および、
   前記対象への追従、を含む、
   請求項１に記載の情報処理装置。
6. 前記動作は、
   走行予定ルートを表す位置情報と、走行予定ルート上の各位置での速度または走行予定ルート上の各位置を通過する時間である時間情報と、により表される参照軌道上の走行、
   前記参照軌道からの逸脱と、新しい参照軌道への追従と、の少なくとも一方、および、
   新しい参照軌道上の走行、を含み、
   前記対象の追い越しは、
   前記対象の手前までの前記参照軌道上の走行、
   前記対象の手前での前記参照軌道からの逸脱、
   移動方向で前記対象より前方に到達した後の新しい参照軌道への追従、および、
   新しい参照軌道上の走行、を含む、
   請求項１に記載の情報処理装置。
7. 前記動作は、
   走行予定ルートを表す位置情報と、走行予定ルート上の各位置での速度または走行予定ルート上の各位置を通過する時間である時間情報と、により表される参照軌道上の走行、
   前記参照軌道からの逸脱と、新しい参照軌道への追従と、の少なくとも一方、および、
   新しい参照軌道上の走行、を含み、
   前記対象への追従は、
   前記対象の手前までの前記参照軌道上の走行、
   前記対象の軌道を前記移動体の移動方向に沿った延伸方向にずらした軌道である新しい参照軌道への追従、および、
   新しい参照軌道上の走行、を含む、
   請求項１に記載の情報処理装置。
8. 前記動作は、
   走行予定ルートを表す位置情報と、走行予定ルート上の各位置での速度または走行予定ルート上の各位置を通過する時間である時間情報と、により表される参照軌道上の走行、
   前記参照軌道からの逸脱と、新しい参照軌道への追従と、の少なくとも一方、および、
   新しい参照軌道上の走行、を含み、
   前記対象との干渉回避のための加減速は、
   前記対象の手前までの前記参照軌道上の走行、
   前記対象の手前での時間軸方向での前記参照軌道からの逸脱、
   新しい参照軌道への追従、および、
   新しい参照軌道上の走行、を含む、
   請求項１に記載の情報処理装置。
9. 前記生成部は、前記回避パターンに含まれる前記動作ごとに複数の前記ノードを生成し、生成した前記ノードが予め定められた第２条件を満たす場合に、前記ノードを生成していない前記動作に対する前記ノードの生成を中止する、
   請求項１に記載の情報処理装置。
10. 選択された前記軌道候補に基づく情報を出力する出力制御部をさらに備える、
    請求項１に記載の情報処理装置。
11. 対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成する生成ステップと、
    前記回避パターンごとに、複数の前記ノードを接続する複数の軌道候補のうち移動コストが他の前記軌道候補より小さい前記軌道候補を探索する探索ステップと、
    前記回避パターンごとに探索された１以上の前記軌道候補のうち、前記移動コストが他の前記軌道候補より小さい前記軌道候補を選択する選択ステップと、
    を含む情報処理方法。
12. コンピュータに、
    対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成する生成ステップと、
    前記回避パターンごとに、複数の前記ノードを接続する複数の軌道候補のうち移動コストが他の前記軌道候補より小さい前記軌道候補を探索する探索ステップと、
    前記回避パターンごとに探索された１以上の前記軌道候補のうち、前記移動コストが他の前記軌道候補より小さい前記軌道候補を選択する選択ステップと、
    を実行させるためのプログラム。
13. 学習装置と情報処理装置とを備える情報処理システムであって、
    前記情報処理装置は、
    対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成する生成部と、
    前記回避パターンごとに、複数の前記ノードを接続する複数の軌道候補のうち移動コストが他の前記軌道候補より小さい前記軌道候補を探索する探索部と、
    前記回避パターンごとに探索された１以上の前記軌道候補のうち、前記移動コストが他の前記軌道候補より小さい前記軌道候補を選択する選択部と、
    前記学習装置は、
    前記生成部が前記ノードを生成するための用いる情報を学習により求める学習部を備える、
    情報処理システム。
14. 車両を制御する車両制御システムであって、
    前記車両の軌道を生成する情報処理装置と、
    前記軌道に基づき車両を駆動するための動力部を制御する動力制御装置と、
    を備え、
    前記情報処理装置は、
    対象を回避するための移動体の１以上の動作をそれぞれ示す１以上の回避パターンに基づいて、第１軌道上の第１対象を回避するために前記回避パターンが示す前記動作に対応する位置に複数のノードを生成する生成部と、
    前記回避パターンごとに、複数の前記ノードを接続する複数の軌道候補のうち移動コストが他の前記軌道候補より小さい前記軌道候補を探索する探索部と、
    前記回避パターンごとに探索された１以上の前記軌道候補のうち、前記移動コストが他の前記軌道候補より小さい前記軌道候補を選択する選択部と、を備える、
    車両制御システム。

Images