JP7616616B2 - 自律走行車用の車線レベルルートプランナ - Google Patents

Description

本開示は、一般にルートプランニングに関するものであり、より詳細には、自律走行車の車線レベルルートプランニングに関する。

ルートプランニングアプリケーション及びシステム（集合的に、ルートプランナ）は、車載車両システム又はハンドヘルドデバイスであり得る。ユーザ（例えば、運転者）は、目的地を提供し、ルーティングアプリケーションはユーザの現在位置から目的地へのルートを計算する。

ルートはマップ上にオーバレイされる場合があり、ユーザが目的地に到着するために従うことができる道路及び曲がり角を含む（例えば、示す）場合がある。つまり、ルートは、目的地への進路変更ごとの示を含み得る。通常、ルートは道路及び曲がり角を含んでおり、運転者が特定の道路のどの車線を走行するか、及び出口又は交差点での曲がり角等、いつ車線を切り替えるかを決定するのはユーザ（例えば、運転者）次第である。

従来のルートプランナは、所定の距離（例えば、２マイル）以内に曲がり角（例えば、出口）が近づいていることをユーザに警告又は通知する場合があり、現在の車線からどのように操縦して曲がるかを決定するのはユーザ次第である。このようなルートプランナは、ホスト車両がどの車線にいるかを知らず、単に所定の距離内でユーザに通知するだけで、ユーザは現在の車線から曲がり角の場所に移動するための安全でない操縦を余儀なくされる可能性がある。

このようなルートプランニングアプリケーションは、道路レベルで確定的に計画する場合があり、車線レベル情報／プランニングを考慮しない。ルートプランニングは、ルート時間を最小化しようとする古典的プランニング問題としてモデル化される場合がある。

少なくともこれらの理由から、このようなルートプランニングアプリケーションにおけるプランニングマップは、運転者がまったく関与しないか、せいぜい関与が最小限であり得る自律走行に必要なものを超えた抽象レベルにあるり得るため、車線レベルではなく道路レベルルートプランニングは、自律走行には適切ではない（例えば、十分ではない）場合がある。

第１の態様はルートプランニングのための方法である。この方法は、目的地を受信すること、マップを使用して目的地への車線レベルルートを取得すること、及び車線レベルルートを通行するように自律走行車（ＡＶ）を制御することを含む。車線レベルルートは、道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含む。

第２の態様は、ルートプランニングのための装置である。この装置は、目的地を受信すること、マップを使用して目的地への車線レベルルートを取得すること、車線レベルルートを通行するように車両を制御することを行うように構成されるプロセッサを含む。前記車線レベルルートは、前記ルートに沿った道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含む。

第３の態様は、プロセッサによって実行されると、動作の実行を容易にする実行可能命令を含む非一時的なコンピュータ可読記憶媒体である。この動作は、目的地を受信すること、マップを使用して目的地への車線レベルルートを取得すること、及び車線レベルルートを通行するように車両を制御することを含む。車線レベルルートは、道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含む。

以下では、本明細書に開示された方法、装置、プロシージャ及びアルゴリズムのこうした及び他の態様、特徴、要素、実装及び実施形態の変形がさらに詳細に記載される。

本明細書に開示された方法及び装置の様々な態様は、以下の記載及び図面において提供される例示を参照することでより明らかになるであろう。ここで同じ参照番号は同じ要素を指している。

本明細書に開示の態様、特徴及び要素が実装され得る車両の例を示す図である。

本明細書に開示の態様、特徴及び要素が実装され得る車両交通及び通信システムの一部の例示の図である。

本開示の実施形態によるルートプランニングのための技術の一例を示すフローチャート図である。

本開示の実装によるマップの一例を示す図である。

本開示の実装による目的の選好順位付けグラフの一例を示す図である。

本開示の実装によるナビゲーションマップの学習及び使用の概要を示す図である。

本開示の実施形態によるルートプランニングのためのナビゲーションマップを学習する技術の一例を示すフローチャート図である。

前述のように、ルートプランナは、通常、車線情報なしでルートを提供する。このようなルートは、全地球測位システム（ＧＰＳ）座標の連結グラフに基づいて計画される場合があり、あまりにも抽象的であるため、自律走行には使用できない。自律走行は、車線変更及び決定を行い、ルートに従うことができない障害が何らかの理由で発生した場合の偶発事象に備えて計画するために、車線固有の情報を必要とする。従来のルートプランナのマップでは、トポロジー、接続性、及び車線情報は通常利用できない。本明細書で使用される場合、自律走行は、文脈がそうでないことを示す場合を除き、人間の運転者又はテレオペレータ等による手動制御と比較すると、ホスト車両を自動的に実行するための車両走行制御を実行することを含む。

さらに、そのようなルートプランナは、典型的には、１つの目的、すなわち、時間のみについて解決し得る。つまり、目的地に到達するまでにかかる時間を最小限に抑えることで、古典的なルートプランニングを実行する。一部のルートプランナでは、ユーザが道路タイプの選好（例えば、地方道路の代わりに高速道路、有料道路の代わりに無料道路）を指定できる場合がある。しかしながら、自律走行では、異なる（例えば、より多くの）基準、制約、及び／又は目的を使用してルートプランニングを行う必要がある。

単純な例を使用して説明すると、従来のルートプランナの場合、運転者が予期した曲がり角で曲がらず、出口を出ない場合、ルートプランナは、通常、代替ルートを識別するために、完了までに少なくとも数秒かかる「再ルーティング」動作を実行する。自律走行の場合、混雑のために自律走行車（ＡＶ）が出口を出られなかったと仮定すると、ルーティングアプリケーションが代替ルートを識別する（すなわち、再ルーティングする）までＡＶがその場で停止し、再ルーティング動作を実行している間に偶発事象ルートを通行したりすることは受け入れられない。

むしろ、本開示に従ったルートプランナは、全ての偶発事象に対して事前に計画することができる。偶発事象は、後述するようにポリシーに組み込まれ得る。一例では、偶発事象は、以前の確率を考慮して計画され得る。確率は、車線セグメント通行の履歴データに基づき得る。確率は、車線変更に成功する確率、交通に基づいて車線変更に失敗する確率、交通履歴の確率、又はその他の確率を含み得る。車線レベルルートプランナは、異なる道路又は道路セグメントでの自律走行の能力レベルに基づいてルートを計画することもできる。能力については、以下にさらに説明する。ルートプランナは、自律走行、運転者、及び／又はテレオペレータ間の制御の移行を決定（例えば、計画）することもできる。車線レベルルートプランナは、確率を組み込んだナビゲーションマップを使用する。

繰り返しになるが、本開示によるルートプランナは、ＡＶが車線変更を行うために制御されるルートに沿った場所を含む目的地への車線レベルルートを決定する。つまり、ルートプランナによって、車線変更、及び、場合によってはルートに沿った障害が計画され得る。追加的に、ルートプランナは、成功及び失敗を想定し、コスト（例えば、目的地への時間）を最小限に抑える確定的な計画を取得するだけではなく、目標（例えば、目的地）までの全ての可能なルートの偶発事象プランを有し得る。

自律走行車の現実世界での展開には、複数の目的を同時に両立させる必要があり得る。いくつかの目的は、目的地への時間、所望のユーザの快適性（例えば、でこぼこした道路対平坦な道路）、所望のユーザの道路速度、道路ナビゲーション能力（例えば、車両が道路又は車線を通行する能力を有するかどうか）、ジオフェンスエリア間の移行ポイント、及び／又は他の目的を含んでもよい。電気又はハイブリッド電気自動車の場合、追加の目的は、バッテリ効率及び／又は再充電のための停止ポイントに関連し得る。本開示による車線レベルルートプランニングは、このような多目的プランニングを実行することができる。

本開示の態様では、車線レベル情報を含むナビゲーションマップが学習され得る。その後、ナビゲーションマップを使用して車線レベルルートが生成され得る。

従来の自律走行車ルートプランナは、複数の状態特徴又は目的に関して学習しない場合がある。対照的に、本開示の実装に従った車線レベルルートプランニングにおいて、ナビゲーションマップは、道路の車線の複数の車線セグメントに関して、及び学習を介して、本明細書にさらに記載されるように、少なくともいくつかの環境情報、車両情報、人的情報、より少ない、より多い若しくは他の情報、又はそれらの組み合わせを組み込むことができる。

本明細書に記載のリスク認識多目的車線レベルルートプランニングは、自律した接続された車両の多目的空間における考慮として、各車線の確率性及び特定の明確な目的報酬値に合わせて調整されたカスタマイズされた学習が必要であり、それらが本明細書に記載されている。

多目的での学習は、少なくとも、単一目的プランナよりも自動運転をより適応させることができる車線レベルルートプランナによってより多くの懸念を考慮することができるため、単一目的学習よりも有利であり得る。複数の目的が可能な場合、車線レベルルートプランナは、良好な（例えば、所望の、快適な）ルート、交通パターン、ユーザ選好、能力等について学習することができる（又はユーザによって教えられ得る）。例えば、ユーザは、正確に対応する目的で選好を直接エンコードすることができる。

車線レベルルートプランニングの詳細は、本明細書では、それが実装可能な環境を最初に参照して説明する。

図１は、本明細書に開示の態様、特徴及び要素が実装され得る車両の例を示す図である。図示の実施形態では、車両１００は様々な車両システムを含む。車両システムは、シャーシ１１０、パワートレイン１２０、コントローラ１３０、及び車輪１４０を含む。車両システムの追加の又は異なる組み合わせが使用されてもよい。簡潔のため、車両１００は４つの車輪１４０を含むように示されているが、プロペラ又はトレッド等の１つ以上の任意の他の推進装置が使用されてもよい。図１において、パワートレイン１２０、コントローラ１３０及び車輪１４０等の要素を相互接続する線は、データ又は制御信号等の情報、電力又はトルク等の力、又は情報及び電力の両方が各要素間で伝達され得ることを示している。例えば、コントローラ１３０は、パワートレイン１２０から電力を受信して、パワートレイン１２０、車輪１４０、又はその両方と通信して、車両１００を制御してもよく、これは、車両１００を加速、減速、操縦又は他のやり方で制御することを含み得る。

図１の例で示されるパワートレイン１２０は、電源１２１、トランスミッション１２２、ステアリング装置１２３、及びアクチュエータ１２４を含む。サスペンション、駆動シャフト、車軸、又は排気システム等のパワートレインの任意の他の要素又は要素の組み合わせが含まれてもよい。別々に示されているが、車輪１４０は、パワートレイン１２０に含まれてもよい。

電源１２１は、エンジン、バッテリ、又はこれらの組み合わせを含む。電源１２１は、電気エネルギー、熱エネルギー又は運動エネルギー等のエネルギーを提供するように動作する任意のデバイス又はデバイスの組み合わせであってもよい。一例では、電源１２１は、内燃エンジン、電気モータ又は内燃エンジン及び電気モータの組み合わせ等のエンジンを含み、車輪１４０の１つ以上に原動力としての運動エネルギーを提供するように動作する。代替的に又は追加的に、電源１２１は、ニッケルカドミウム（ＮｉＣｄ）、ニッケル亜鉛（ＮｉＺｎ）、ニッケル水素（ＮｉＭＨ）、リチウムイオン（Ｌｉ－ｉｏｎ）等の１つ以上の乾電池、太陽電池、燃料電池、又はエネルギーを提供することが可能な任意の他のデバイス等のポテンシャルエネルギー装置を含んでもよい。

トランスミッション１２２は、電源１２１から運動エネルギー等のエネルギーを受信し、原動力を提供するために車輪１４０にエネルギーを送る。トランスミッション１２２は、コントローラ１３０、アクチュエータ１２４又はその両方によって制御されてもよい。ステアリング装置１２３は、コントローラ１３０、アクチュエータ１２４又は両方によって制御され、車両を操縦するために車輪１４０を制御してもよい。アクチュエータ１２４は、コントローラ１３０から信号を受信してもよく、車両１００を動作させるために電源１２１、トランスミッション１２２、ステアリング装置１２３又はこれらの任意の組み合わせを作動又は制御してもよい。

例示の実施形態では、コントローラ１３０は、位置決め装置１３１、電子通信装置１３２、プロセッサ１３３、メモリ１３４、ユーザインターフェース１３５、センサ１３６、及び電子通信インターフェース１３７を含む。これらの要素のうち少数が、コントローラ１３０の一部として存在し得る。単一の装置として示されているが、コントローラ１３０の任意の１つ以上の要素が任意の数の分離した物理装置に組み込まれてもよい。例えば、ユーザインターフェース１３５及びプロセッサ１３３は、第１の物理装置に組み込まれてもよく、メモリ１３４は、第２の物理装置に組み込まれてもよい。図１には示されていないが、コントローラ１３０は、バッテリ等の電源１２１０を含んでもよい。個別の要素として示されているが、位置決め装置１３１、電子通信装置１３２、プロセッサ１３３、メモリ１３４、ユーザインターフェース１３５、センサ１３６、電子通信インターフェース１３７、又はこれらの任意の組み合わせは、１つ以上の電子装置、回路又はチップに組み込まれてもよい。

プロセッサ１３３は、光プロセッサ、量子プロセッサ、分子プロセッサ又はこれらの組み合わせを含む現存する又は今後開発される信号又は他の情報を操作又は処理することが可能な任意のデバイス又はデバイスの組み合わせを含んでもよい。例えば、プロセッサ１３３は、１つ以上の専用プロセッサ、１つ以上のデジタル信号プロセッサ、１つ以上のマイクロプロセッサ、１つ以上のコントローラ、１つ以上のマイクロコントローラ、１つ以上の集積回路、１つ以上の特定用途向け集積回路、１つ以上のフィールドプログラマブルゲートアレイ、１つ以上のプログラマブルロジックアレイ、１つ以上のプログラマブルロジックコントローラ、１つ以上の状態機械、又はこれらの任意の組み合わせを含んでもよい。プロセッサ１３３は、位置決め装置１３１、メモリ１３４、電子通信インターフェース１３７、電子通信装置１３２、ユーザインターフェース１３５、センサ１３６０、及びパワートレイン１３６の１つ以上と動作可能に結合されてもよい。例えば、プロセッサは、通信バス１３８を介してメモリ１３４と動作可能に結合されてもよい。

メモリ１３４は、プロセッサ１３３によって使用される又はそれと接続される、機械可読命令又はそれに関連付けられる任意の情報を、例えば、保持、記憶、伝達又は搬送することが可能な任意の有形の非一時的なコンピュータ使用可能又はコンピュータ可読媒体を含む。メモリ１３４は、例えば、１つ以上の半導体ドライブ、１つ以上のメモリカード、１つ以上のリムーバブル媒体、１つ以上の読み取り専用メモリ、１つ以上のランダムアクセスメモリ、ハードディスク、フロッピーディスク、光学ディスクを含む１つ以上のディスク、磁気若しくは光学カード、又は電子情報を記憶するのに適した任意のタイプの非一時的な媒体、又はこれらの任意の組み合わせであってもよい。例えば、メモリは、１つ以上の読み取り専用メモリ（ＲＯＭ）、１つ以上のランダムアクセスメモリ（ＲＡＭ）、１つ以上のレジスタ、低電力ＤＤＲ（ＬＰＤＤＲ）メモリ、１つ以上のキャッシュメモリ、１つ以上の半導体メモリデバイス、１つ以上の磁気媒体、１つ以上の光学媒体、１つ以上の磁気光学媒体、又はこれらの任意の組み合わせであってもよい。

通信インターフェース１３７は、図示のような無線アンテナ、有線通信ポート、光学通信ポート、又は有線若しくは無線電子通信媒体１５０とインターフェース接続することが可能な任意の他の有線若しくは無線装置であってもよい。図１は単一の通信リンクを介して通信を行う通信インターフェース１３７が示されているが、通信インターフェースは、複数の通信リンクを介して通信を行うように構成されてもよい。図１は単一の通信インターフェース１３７を示しているが、車両は、任意の数の通信インターフェースを含んでもよい。

通信装置１３２は、通信インターフェース１３７等を介して、有線又は無線電子通信媒体１５０を介して信号を送信又は受信するように構成される。図１に明示されていないが、通信装置１３２は、無線周波数（ＲＦ）、紫外線（ＵＶ）、可視光、光ファイバ、有線回線、又はこれらの組み合わせ等の任意の有線又は無線通信媒体を介して送信、受信又は両方を行うように構成されてもよい。図１は、単一の通信装置１３２及び単一の通信インターフェース１３７を示しているが、任意の数の通信装置及び任意の数の通信インターフェースが使用されてもよい。いくつかの実施形態では、通信装置１３２は、狭域通信（ＤＳＲＣ）装置、車載装置（ＯＢＵ）、又はこれらの組み合わせを含む。

位置決め装置１３１は、車両１００の経度、緯度、高度、進行方向又は速さ等の地理情報を決定してもよい。一例では、ＧＰＳは、広域補強システム（Ｗｉｄｅ Ａｒｅａ Ａｕｇｍｅｎｔａｔｉｏｎ Ｓｙｓｔｅｍ；ＷＡＡＳ）対応米国海洋電子機器協会（Ｎａｔｉｏｎａｌ ＭａｒｉｎｅＥｌｅｃｔｒｏｎｉｃｓ Ａｓｓｏｃｉａｔｉｏｎ；ＮＭＥＡ）装置、無線三角測量装置、又はこれらの組み合わせ等の全地球測位システム（ＧＰＳ）装置を含む。位置決め装置１３１は、例えば、車両１００の現在の向き、２次元又は３次元での車両１００の現在地、車両１００の現在の角度方向、又はこれらの組み合わせを表す情報を取得するために使用され得る。

ユーザインターフェース１３５は、仮想又は物理キーパッド、接触パッド、ディスプレイ、接触ディスプレイ、ヘッドアップディスプレイ、仮想ディスプレイ、拡張現実ディスプレイ、触覚ディスプレイ、視線追跡装置等の特徴追跡デバイス、スピーカ、マイクロホン、ビデオカメラ、センサ、プリンタ、又はこれらの任意の組み合わせ等、人物とインターフェース接続することが可能な任意の装置を含む。ユーザインターフェース１３５は、図示のようにプロセッサ１３３と、又はコントローラ１３０の任意の他の要素と動作可能に結合されてもよい。単一の装置として示されているが、ユーザインターフェース１３５は、１つ以上の物理装置を含んでもよい。例えば、ユーザインターフェース１３５は、人物との音声通信を行うためのオーディオインターフェース、及び人物との視覚及びタッチに基づく通信を行うためのタッチディスプレイの両方を含んでもよい。ユーザインターフェース１３５は、複数の物理的に分離した装置、単一の物理装置の中の複数の定義部分、又はこれらの組み合わせ等の複数のディスプレイを含んでもよい。

センサ１３６は、車両を制御するために使用され得る情報を提供するように動作可能である。センサ１３６は、センサのアレイであってもよい。センサ１３６は、車両動作情報を含む車両１００の現在の動作特徴に関する情報を提供してもよい。センサ１３６は、例えば、速度センサ、加速度センサ、ステアリング角センサ、トラクション関連センサ、ブレーキ関連センサ、ハンドル位置センサ、視線追跡センサ、着座位置センサ、又は任意のセンサ若しくはセンサの組み合わせを含んでもよく、これらは車両１００の現在の動的状況の何らかの態様に関する情報を報告するように動作可能である。

センサ１３６は、動作環境情報等の車両１００を取り囲む物理環境に関する情報を取得するように動作可能な１つ以上のセンサを含んでもよい。例えば、１つ以上のセンサが、車線等の道路の形状、及び固定障害物、車両及び歩行者等の障害物を検出してもよい。センサ１３６は、既知の又は後に開発される、１つ以上のビデオカメラ、レーザ感知システム、赤外線感知システム、音響感知システム、又は任意の他の適切なタイプの車載環境感知デバイス、又はデバイスの組み合わせであるか、又はこれらを含み得る。いくつかの実施形態では、センサ１３６及び位置決め装置１３１が結合される。

別に示されてはいないが、車両１００は、軌道コントローラを含んでもよい。例えば、コントローラ１３０が、軌道コントローラを含んでもよい。軌道コントローラは、車両１００の現在の状態及び車両１００に対して計画されたルートを記述する情報を取得し、この情報に基づいて、車両１００に対する軌道を決定及び最適化するように動作可能であってもよい。いくつかの実施形態では、軌道コントローラは、車両１００が軌道コントローラによって決定される軌道に従うように、車両１００を制御するように動作可能な信号を出力してもよい。例えば、軌道コントローラの出力は、パワートレイン１２０、車輪１４０又はその両方に供給され得る最適化された軌道であり得る。いくつかの実施形態において、最適化された軌道は、一組のステアリング角等の制御入力であってもよく、各ステアリング角は１つの時点又は位置に対応する。いくつかの実施形態において、最適化された軌道は、１つ以上の経路、線、曲線、又はこれらの組み合わせであり得る。

１つ以上の車輪１４０は、ステアリング装置１２３の制御下でステアリング角に枢動される操縦車輪、トランスミッション１２２の制御下で車両１００を推進するためのトルクを与えられる推進車輪、又は車両１００を操縦及び推進し得る操縦及び推進車輪であってもよい。

図１には示されていないが、車両は、エンクロージャ、ブルートゥース（登録商標）モジュール、周波数変調（ＦＭ）ラジオ装置、近距離無線通信（ＮＦＣ）モジュール、液晶表示（ＬＣＤ）ディスプレイ装置、有機発光ダイオード（ＯＬＥＤ）ディスプレイ装置、スピーカ、又はこれらの任意の組み合わせ等の図１に示されていない追加の装置又は要素を含んでもよい。

車両１００は、交通網の一部を移動するように、直接的な人間の介入なしで、自律的に制御される自律走行車であってもよい。図１に別に示されていないが、自律走行車は、自律走行車のルーティング、ナビゲーション及び制御を行う自律走行車制御装置を含んでもよい。自律走行車制御装置は、車両の別の装置と一体化されてもよい。例えば、コントローラ１３０は、自律走行車制御装置を含んでもよい。

存在する場合、自律走行車制御装置は、現在の車両動作パラメータに従って車両交通網の一部を移動するように車両１００を制御し又は動作させてもよい。自律走行車制御装置は、車両の駐車等の定義された動作又は操縦を行うように車両１００を制御し又は動作させてもよい。自律走行車制御装置は、車両情報、環境情報、車両交通ネットワークを表す車両交通ネットワーク情報、又はこれらの組み合わせに基づいて車両１００の現在地等の出発地から目的地への移動ルートを生成してもよく、ルートに従って車両交通ネットワークを移動するように車両１００を制御し又は動作させてもよい。例えば、自律走行車制御装置は、軌道コントローラに移動ルートを出力して、生成されたルートを使用して出発点から目的地に移動するように車両１００を動作させてもよい。

図２は、本明細書に開示の態様、特徴及び要素が実装され得る車両交通及び通信システムの一部の例示の図である。車両交通及び通信システム２００は、図１に示される車両１００等の１つ以上の車両２１０／２１１を含んでもよく、これは車両交通ネットワーク２２０の１つ以上の部分を介して移動してもよく、１つ以上の電子通信ネットワーク２３０を介して通信を行う。図２には明示されていないが、車両はオフロードエリアを通行してもよい。

電子通信ネットワーク２３０は、例えば、車両２１０／２１１と１つ以上の通信デバイス２４０との間の音声通信、データ通信、映像通信、メッセージング通信、又はこれらの組み合わせ等の通信を提供する多重アクセスシステムであってもよい。例えば、車両２１０／２１１は、ネットワーク２３０を介して通信デバイス２４０から車両交通ネットワーク２２０を表す情報等の情報を受信してもよい。

いくつかの実施形態では、車両２１０／２１１は、有線通信リンク（図示せず）、無線通信リンク２３１／２３２／２３７、又は任意の数の有線若しくは無線通信リンクの組み合わせを介して通信してもよい。図示のように、車両２１１／２１１は、陸上無線通信リンク２３１を介して、非陸上無線通信リンク２３２を介して、又はこれらの組み合わせを介して通信する。陸上無線通信リンク２３１は、イーサネット（登録商標）リンク、シリアルリンク、ブルートゥース（登録商標）リンク、赤外線（ＩＲ）リンク、紫外線（ＵＶ）リンク、又は電子通信を提供可能な任意のリンクを含んでもよい。

車両２１０／２１１は、別の車両２１０／２１１と通信してもよい。例えば、ホスト又は対象の車両２１０が、直接通信リンク２３７を介して又はネットワーク２３０を介して、遠隔又はターゲット車両（ＲＶ）２１１から基本安全メッセージ（ｂａｓｉｃ ｓａｆｅｔｙ ｍｅｓｓａｇｅ；ＢＳＭ）等の１つ以上の自律走行車間メッセージを受信してもよい。リモート車両２１１は、３００メートル等の定義されたブロードキャスト範囲内のホスト車両にメッセージをブロードキャストしてもよい。いくつかの実施形態では、ホスト車両２１０は、信号リピータ（図示せず）又は別のリモート車両（図示せず）等のサードパーティを介してメッセージを受信してもよい。車両２１０／２１１は、例えば、１００ミリ秒等の定義された間隔に基づいて周期的に１つ以上の自動車両間メッセージを送信してもよい。

自動車両間メッセージは、車両識別情報、経度、緯度若しくは高度情報等の地理空間状態情報、地理空間位置精度情報、車両加速度情報、ヨーレート情報、速度情報、車両方位情報、制動システム状態情報、スロットル情報、ハンドル角度情報若しくは車両ルーティング情報等の運動状態情報、又は送信車両状態に関連する車両サイズ情報、ヘッドライト状態情報、方向指示器情報、ワイパー状態情報、トランスミッション情報若しくは任意の他の情報若しくは情報の組み合わせ等の車両動作状態情報を含んでもよい。例えば、トランスミッション状態情報は、送信車両のトランスミッションがニュートラル状態、駐車状態、前進状態又は後退状態に有るかどうかを示してもよい。

車両２１０は、アクセスポイント２３３を介して通信ネットワーク２３０と通信してもよい。コンピュータ装置を含み得るアクセスポイント２３３は、無線又は有線通信リンク２３１／２３４を介して、車両２１０と、通信ネットワーク２３０と、１つ以上の通信デバイス２４０と、又はこれらの組み合わせと通信するように構成される。例えば、アクセスポイント２３３は、基地局、ＢＴＳ（ｂａｓｅ ｔｒａｎｓｃｅｉｖｅｒ ｓｔａｔｉｏｎ）、Ｎｏｄｅ－Ｂ、ｅＮｏｄｅ－Ｂ（ｅｎｈａｎｃｅｄ Ｎｏｄｅ－Ｂ）、ＨＮｏｄｅ－Ｂ（Ｈｏｍｅ Ｎｏｄｅ－Ｂ）、無線ルータ、有線ルータ、ハブ、リレー、スイッチ、又は任意の類似の有線若しくは無線デバイスであってもよい。ここでは単一の装置として示されているが、アクセスポイントは、任意の数の相互接続要素を含んでもよい。

車両２１０は、衛星２３５又は他の非陸上通信デバイスを介して通信ネットワーク２３０と通信してもよい。コンピュータデバイスを含み得る衛星２３５は、１つ以上の通信リンク２３２／２３６を介して、車両２１０と、通信ネットワーク２３０と、１つ以上の通信デバイス２４０と、又はこれらの組み合わせと通信するように構成される。ここでは単一の装置として示されているが、衛星は、任意の数の相互接続要素を含んでもよい。

電子通信ネットワーク２３０は、音声、データ、又は任意の他のタイプの電子通信を提供するように構成される任意のタイプのネットワークである。例えば、電子通信ネットワーク２３０は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）、モバイル若しくはセルラ電話ネットワーク、インターネット、又は任意の他の電子通信システムを含んでもよい。電子通信ネットワーク２３０は、トランスミッションコントロールプロトコル（ＴＣＰ）、ユーザデータグラムプロトコル（ＵＤＰ）、インターネットプロトコル（ＩＰ）、リアルタイムトランスポートプロトコル（ＲＴＰ）、ハイパーテキストトランスポートプロトコル（ＨＴＴＰ）、又はこれらの組み合わせ等の通信プロトコルを使用する。ここでは単一の装置として示されているが、電子通信ネットワークは、任意の数の相互接続要素を含んでもよい。

車両２１０は、車両交通網２２０の一部又は状態を識別してもよい。例えば、車両は、速度センサ、車輪速度センサ、カメラ、ジャイロスコープ、光学センサ、レーザセンサ、レーダセンサ、音響センサ、又は車両交通ネットワーク２２０の一部若しくは状態を決定若しくは識別することが可能な任意の他のセンサ若しくは装置又はこれらの組み合わせであってもよく又はそれを含み得る図１に示されたセンサ１３６等の少なくとも１つの車載センサ２０９を含む。

車両２１０は、交通ネットワーク２２０を表す情報、１つ以上の車載センサ２０９、又はこれらの組み合わせ等のネットワーク２３０を介して伝達される情報を使用して、車両交通ネットワーク２２０の一部又は複数の部分を通行してもよい。

簡潔のため、図２には１つの１つの車両交通ネットワーク２２０、１つの電子通信ネットワーク２３０及び１つの通信デバイス２４０が示されているが、任意の数のネットワーク又は通信デバイスが使用されてもよい。車両交通及び通信システム２００は、図２に示されていないデバイス、装置又は要素を含んでもよい。車両２１０は単一の装置として示されているが、車両は、任意の数の相互接続要素を含んでもよい。

ネットワーク２３０を介して通信デバイス２４０と通信する車両２１０が示されているが、車両２１０は、任意の数の直接又は間接通信リンクを介して通信デバイス２４０と通信してもよい。例えば、車両２１０は、ブルートゥース（登録商標）通信リンク等の直接通信リンクを介して通信デバイス２４０と通信してもよい。

図３は、本開示の実施形態によるルートプランニングのための技術の一例を示すフローチャート図である。技術３００は、図１に示された車両１００、図２に示された車両２１０／２１１のうちの１つ、半自律走行車、運転支援機能を含み得る任意の他の車両、又は運転者等によって手動で制御される車両であり得るホスト車両において部分的又は完全に実装され得る。技術３００は、図１のメモリ１３４等のメモリに記憶される命令（例えば、動作）として実装され得る。命令は、図１のプロセッサ１３３等のプロセッサによって実行され得る。技術３００は、専用のハードウェア又はファームウェアを使用して実装され得る。複数のプロセッサ、メモリ、又はその両方が使用されてもよい。

技術３００は、車線レベルルートプランナによって部分的又は完全に実装され得る。車線レベルプランナは、図１等に関して説明されたＣＰＵ（中央処理装置）、メモリ、及び入出力装置を含むプロセッサを使用して実装され得る。プロセッサを車線レベルルートプランナとして機能させるコンピュータプログラムは、プロセッサにインストールされ且つ実行され得る。これにより、プロセッサを車線レベルルートプランナとして機能させることが可能になる。なお、ここではソフトウェアによって車線レベルルートプランナが実装される例を説明するが、当然のことながら、ここで説明する各情報処理を実行するために用意された専用のハードウェアによっても車線レベルルートプランナは実装され得る。

ステップ３０２において、技術３００は目的地を受信する。一例では、ユーザ（例えば、運転者）は、ルーティングアプリケーションのユーザインターフェースを介して目的地を提供することができる。一例では、ユーザは、ユーザのポータブルデバイス上で実行され得るルーティングアプリケーションに目的地を提供することができる。別の例では、車両は、サービス（例えば、ロボタクシーサービス）を実行しており、目的地は、配車プロセスを介して技術３００に提供されてもよく、これにより、車両は、顧客又は荷物のピックアップ場所又は顧客又は荷物のドロップオフ場所であり得る目的地に移動する。技術３００に目的地を提供する他のやり方も可能である。目的地は、住所、ランドマーク、会場、又は他の目的地タイプであってもよい。技術３００は、受信した目的地をＧＰＳ座標の集合に変換することができる。

ステップ３０４において、技術３００は、マップ（すなわち、ナビゲーションマップ又は車線レベルナビゲーションマップ）を使用して目的地への車線レベルルートを取得する。車線レベルルートは、道路の第１の車線の第１のセグメントから道路の第２の車線の第２のセグメントへの遷移（すなわち、遷移のためのアクション）を含む。一例では、目的地は、車線レベルルートを計算する図２の通信デバイス２４０等のサーバ（例えば、クラウド型のサーバ）に（無線で）送信されて提供されてもよい。図４に関して、マップ及び車線レベルルートの一例を説明する。

図４は、本開示の実装によるマップの一例を示す図である。マップ４００は、目的地が道路セグメント４０１にあることを示す。マップ４００は、３つの車線、車線４０４Ａ～４０４Ｃを含む道路４０２を含む。マップ４００の車線は、車線セグメントに分割される。車線セグメントは、マップ４００の番号付きセグメントによって示される。例えば、車線４０４Ａは、車線セグメント４０６Ａ～４０６Ｃを含む。車両４０３は、現在、車線セグメント４０６Ａにあり、車線セグメント４０１の目的地に向かっている。車線セグメント４０６Ａは、車両４０３の出発点（図示せず）と目的地との間の中間車線セグメントであってもよい。

一例では、全ての道路セグメントは、同じ長さ（例えば、１００メートル、２００メートル、又はその他のセグメント長）を有し得る。一例では、車線セグメントの長さの少なくとも一部は、車線セグメントの道路に沿った速度に依存し得る。例えば、高速では、車線セグメントは、５００メートル等のより長い長さを有してもよい。一例では、一部の車線セグメントの長さは調整され得る。つまり、例えば、第１の車線レベルルートを生成する場合、第１の車線レベルルートは、第１の長さを有する車線セグメントの一部により生成されてもよく、第２の車線レベルルートを生成する場合、第２の車線レベルルートは、第２の長さを有する車線セグメントの一部により生成されてもよい。車線セグメントの長さは、道路における速度、時刻（例えば、ラッシュアワー対週末）、社会地理的領域（例えば、スクールゾーン、住宅街）、天候（例えば、晴れ対雪）、道路タイプ（例えば、高速道路対市街地道路）、より多い、より少ない、その他の基準、又はそれらの組み合わせに基づいて変更され得る。例えば、視覚的に示されているように、車線セグメント４０６Ｅは、車線セグメント４０６Ｃよりも短い。しかし、車線セグメント４０６Ｄは、車線セグメント４０６Ｃよりも長い。

マップ４００において、車線セグメントは、識別番号（ＩＤ）を有し得る。例えば、車線セグメント４０６Ａ～４０６Ｅは、それぞれＩＤ１、２、３、７、１３を有する。車線セグメントの少なくとも一部は、メタデータに関連付けられ得る。一例では、メタデータには、１つ以上の分類（例えば、指定）が含まれ得る。例えば、マップ４００は、（異なる陰影を使用して）ＩＤが１、２、及び３の車線セグメントが高速セグメントであることを示し、ＩＤが４、５、６、７、及び１１の車線セグメントが標準速度（例えば、速度制限）セグメントであることを示し、ＩＤが８、９、及び１０の車線セグメントが快適（例えば、低速）セグメントであることを示し、ＩＤが１２、１３、及び１５の車線セグメントが市街地車線セグメントであることを示し、ＩＤが１４、１６、及び１７の車線セグメントが手動運転の車線セグメントであることを示している。これらの分類は、必ずしも相互に排他的ではない。例えば、市街地車線セグメントは手動運転車線セグメントであり得る。

快適性車線セグメントとは、車線セグメントの道路上の制限速度の－１０マイル／時間（又はその他の閾値速度）以内の速度で交通が移動し得る車線セグメントであってもよい。手動運転車線セグメントとは、自律的に通行できない、又は十分な信頼度で自律的に通行できない車線セグメントである。このような車線セグメントは、運転者又はテレオペレータ等の手動運転制御の下で通行する必要がある。そのため、車線レベルルートプランナは、車線セグメントの一定時間前に、ユーザが車両の手動運転制御を引き継ぐ必要があることをユーザ（例えば、運転者）に通知するアクションを含んでもよい。

一例では、車線レベルルートを取得することは、起点位置から目的地まで車線セグメントを通行するためのポリシーを取得することを含んでもよい。ポリシーには、車線遷移が含まれる。より正確には、後述するように、ポリシーは、車両が現在の車線セグメント内にあることを考慮したアクションを提供する。一例では、ポリシーは確定的なポリシーであり得る。別の例では、ポリシーは確率モデルに基づき得る。

ルートプランニングでは、目的地への時間を最小化することがルートプランナの通常の目的であるが、本開示に従った車線レベルルートプランナは、以下にさらに説明するように、いくつかの目的のために最適化することによって車線レベルルートを取得することができる。

車線レベルルートは、１つのタイプのマルコフ決定過程（ＭＤＰ）モデルを使用して取得され得る。車線レベルルートプランニングは、トポロジカル部分観測マルコフ決定過程（ＴＰＯＭＤＰ）又はその完全に観測可能なサブクラスのトポロジカルマルコフ決定過程（ＴＭＤＰ）としてモデル化され得る。ＴＰＯＭＤＰ及びＴＭＤＰは、安全性、円滑性、及び／又は他の人の選好を最大化する等の追加的な目的尺度を、移動時間又は移動距離の最小化等、典型的な部分観測マルコフ決定過程モデル（ＰＯＭＤＰ）又はマルコフ決定過程（ＭＤＰ）の目的に組み込むことを可能にする。ＴＰＯＭＤＰモデルを解くことは、ＴＭＤＰモデルを解くことに似ている場合があるが、ＴＰＯＭＤＰが信念状態（すなわち、確率）に基づいており、それぞれの状態の確率を表し、それぞれの状態の観測値の生成に対応する観測確率に従うという点が異なる。他のモデルタイプも可能である。例えば、モデルはスカラー化された多目的マルコフ決定過程（ＭＯＭＤＰ）、スカラー化された部分観測多目的マルコフ決定過程（ＭＯＰＯＭＤＰ）、制約付きマルコフ決定過程（ＣＭＤＰ）、又は制約付き部分観測マルコフ決定過程（ＣＰＯＭＤＰ）のいずれかであり得る。

一般性を失わずに説明するために、ユーザは低速車線の選好を示してもよい。そのため、ルートプランナはどのように目的地に到達するかの計算に「快適性」の目的を組み込むことができる。別の例では、ユーザは、追加的に又は代替的に、エネルギー消費を最小限に抑える車線の選好を示し得る。例えば、一部の車線セグメントにおける交通がノロノロ運転であり、より多くのエネルギー消費を必要とする傾向がある場合、ルートプランナは他の道路セグメントを優先してもよい。別の例として、上り坂下り坂の多い道路はエネルギー消費が多くなる傾向があるため、ルートプランナによってそのような道路よりも円滑な道路が優先される。別の例として、充電ステーションが少ない別の道路よりも、充電ステーションが多い道路が優先されてもよい。

一般性を失わずに、モデル（例えば、ＴＭＤＰ又はＴＰＯＭＤＰ）を確率的最短経路（ＳＳＰ）構造用語（例えば、報酬の代わりにコスト、及び到着時に自己ループするターゲット状態としての目標）で記述され得る。

連結グラフ（Ｖ、Ｅ、Ｒ）は、タプル〈S，A，T，C，Ｅ，δ，s_０，s_g〉で表されるモデルに変換され得る。各頂点ｖ∈Ｖは、ルーティング決定が行われ得る点のＧＰＳ座標であり得る。そのため、頂点は、交差点、（例えば、ＩＤ９の車線セグメントからＩＤ１１の車線セグメントへの）車線変更位置、マージポイント等のＧＰＳ座標であり得る。説明するために、マップ４００では、頂点ｖは、車線セグメントの特定の点の座標であり得る。例えば、特定の点は、車線セグメントの中点であり得る。連結グラフの各エッジｅ∈Ｅは、長さ又は通行時間Ｒ（ｅ）の頂点の有向グラフを記述し得る。例えば、マップ４００の下にある連結グラフでは、ＩＤ９の車線セグメントに対応する頂点は、ＩＤ１０及び１１の車線セグメントに接続される。

次に、形式モデルＴＭＤＰの概要を示す。前述のように、このモデルは形式的にタプル〈S，A，T，C，Ｅ，δ，s_０，s_g〉として記述され得る。Sは、状態又は頂点ｖ∈Ｖの有限集合であり得る。Aは、後続車線セグメント（言い換えれば、後続の頂点）を選択するための各頂点におけるアクション空間である。一般性を損なわずに説明するために、アクション空間Aには、「左に移動する」、「右に移動する」、「真っすぐ移動する」、又は「斜めに移動する」というアクションを含み得る。しかしながら、より多い、より少ない、他のアクション、又はそれらの組み合わせも可能である。例えば、アクション空間Aは、手動制御を引き継ぐようにユーザに通知するアクション、手動制御に切り替えるアクション、制御が自動制御に切り替わることをユーザに通知するアクション、自動制御に切り替えるアクション等を含み得る。

s_０は初期状態であり、これはルートプランナが車線レベルルートを計算するときの車両の現在位置であり得る。s_gは目標状態であり、これは目的地であり得る。目標状態s_gに達すると、どのアクションが実行されても目標状態が維持され、目標状態s_gで実行される全てのアクションは０のコストを有する。

T（つまり、T：S×A×S→[０，１]）は、状態s∈Sでアクションa∈Aを実行した後に後続の状態s’∈Sが発生する確率を表す状態遷移関数であり得る。したがって、Tは、各アクションの確率的な成功／失敗を記述する状態遷移関数である。状態遷移関数T(s，a，s')＝Ｐｒ（s'｜s，a）は、アクションaが状態sで実行されたことを考慮した後続（車線セグメント又は頂点）の確率s'である。一例では、状態遷移関数は、頂点（例えば、車線セグメント）の隣接する頂点（例えば、車線セグメント）の少なくともいくつか（例えば、それぞれ）の各確率を含んでもよい。説明のため、ＩＤ１（すなわち、車線セグメント４０６Ａ）の車線セグメントに関して、状態遷移関数Tは、ＩＤ１の車線セグメントからＩＤ４の車線セグメントへの遷移、ＩＤ１の車線セグメントからＩＤ２の車線セグメントへの遷移、及び／又はＩＤ１の車線セグメントからＩＤ５の車線セグメントへの遷移のいくつかについて各遷移確率を含んでもよい。いくつかの例では、状態遷移関数は、より離れた近隣へ（例えば、ＩＤ１の車線セグメントからＩＤ３の車線セグメントへ）の遷移確率を含んでもよい。

そのため、マップを使用して目的地への車線レベルルートを取得することは、ＡＶがマップの第１の車線セグメント上にある場合に、第１の車線セグメントに隣接する第２の車線セグメントに移動するようにＡＶを制御するアクションを提供するポリシーを取得することを含んでもよい。

確率は、速度制限、エッジeの車線長、ＡＶの仕様、時刻及び場所、交通渋滞情報、より多くの基準、より少ない基準、他の基準、又はそれらの組み合わせを含む基準に基づいて導出され得る。一例では、これらの確率（及び／又は遷移確率を取得するために使用される基準）は、以下でさらに説明するように学習され得る。

は、状態s∈Sでアクションa∈Aを実行するために期待される即時コストを表すマルチコスト関数を表し得る。そのため、車線レベルルートは１つ以上の目的を使用して計算され得る。コストCは、１つ以上の期待される目的に対する最適化のコストベクトルとしてモデル化され得る。１つ以上の期待される目的は、時間目的C_T（すなわち、目的地への移動時間を最小化する時間に関する第１の目的）、快適性目的C_C（すなわち、快適性車線セグメントの選好を示す快適性に関する第２の目的）、自律目的C_A（すなわち、車両が手動で制御されるのとは対照的に自律的に制御され得る車線セグメントの選好を示す自律性に関する第３の目的）、市街地目的C_U（すなわち、例えば、地方車線セグメントとは対照的な市街地車線セグメントの選好に関する第４の目的）、より少ない目的、より多い目的、他の目的、又はそれらの組み合わせを含んでもよい。一例では、コスト目的は発電に関連し得る。したがって、一例では、コストベクトルCは、

によって与えられてもよく、ここで、各C_i (s，a)が状態sにあり、アクションaを実行するためのコスト目的ｉを示す。一例では、１つ以上の目的は、時間に関連する第１の目的、快適性に関連する第２の目的、自律性に関連する第３の目的、又は市街地車線セグメントに関連する第４の目的のうちの少なくとも２つを含んでもよい。

目的は、有向非巡回グラフ（ＤＡＧ）Ｅに続く選好順位付けで配置され得る。図５を用いて選好順位付けグラフの例を説明する。各目的は非負のスラックδ : e → R+を有してもよく、これはユーザが他の目的の価値を向上させるために、ある目的の価値にどれだけ「費やす」意思があるかを記述する。このように、１つ以上の目的は、スラック変数を含む選好順位付けで関連付けられる。

モデルの解は、ポリシーπ：S→Aであってもよい。ポリシーπの下では、アクションa（すなわち、π(s)）が状態sに対して選択される。つまり、ポリシーπは、状態sでアクションπ(s)∈Aを実行する必要があることを示し得る。ポリシーπは、ポリシーπに従って状態sから目的地（すなわち、目標状態s_g）に到達するために期待される累積コストV^π(s)を表し得る価値関数V^π：S→Cを含んでもよい。つまり、価値関数は、開始状態から目標状態に達するまでの各中間状態s_iの期待されるコスト（すなわち、価値）を提供し得る。

最適なポリシーπ^*は、期待される累積コストを最小化する。形式的には、初期状態s_０に対して、期待値は式（１）で与えられ得る。

式（１）において、S_t及びA_tは、時間ステップｔにおける状態及びアクションのランダム変数をそれぞれ表す。一般に、モデルを解くには、適切なポリシーが存在する必要がある。適切なポリシーπは、（１）確率１で目標に到達するポリシーが存在し、（２）確率１で目標に到達しない全ての状態は無限のコストをもたらす、という特性を有する。

図３のステップ３０６において、技術３００は、車線レベルルートを通行するようにＡＶを制御する。図４に戻り、図４の矢印は、決定されたポリシーπの下でのアクションを示す。矢印４０８Ａは、「状態がＩＤ１の車線セグメントと等しい場合に、右のアクションを実行し、その結果、車両はＩＤ４の車線セグメントと等しい状態で終了する」というアクションを示す。この場合の「アクションを実行する」とは、アクセルペダルの動作量、ブレーキペダルの動作量、ハンドルのステアリング角等の変更により、「車両が制御される」ことを意味する。

決定されたポリシーπには、偶発事象に備えたルートが組み込まれている（例えば、含まれる）。したがって、得られた車線レベルルートには偶発事象に備えたルートが含まれる。説明のため、車両がＩＤ９の車線セグメント内にある場合、ポリシーは車両がＩＤ１１の車線セグメントに移動するように制御されることを示す。しかしながら、車両がＩＤ１１の車線セグメントを取ることができず、ＩＤ１０の車線セグメントに入ってしまった場合、ポリシーは車両をＩＤ６の車線セグメントに移動させ、且つＩＤ７の車線セグメントに移動させる「左のアクションを実行する」を示す。したがって、車線レベルルートを通行するようにＡＶを制御することは、第１のセグメントから第２のセグメントに遷移できないことに応答して、偶発事象ルートに従ってＡＶを制御することを含んでもよい。

図５は、本開示の実装に従った目的の選好順位付けグラフの例５００を示す。上述したように、モデルの目的はトポロジカルに順序付けすることであってもよい。トポロジカルに順序付けされた制約は、先行目的に対して最初の信念又は全ての信念のスラックを満たさせ得る。車線レベルルートプランナは、トポロジカルに順序付けされた制約グラフで順序付けされたポリシーを計算するために、目的について推論することができる。３つの異なる選好順位が記述されているが、本開示はそれに限定されず、他の構成（すなわち、選好順位）も可能である。

例５００に示される目的は、速度の最適化（すなわち、目的５１２，５３８及び５５６等のＨとラベルされたバブル）、快適性の最適化（すなわち、目的５１４，５３４及び５５４等のＣとラベルされたバブル）、市街地運転の最適化（すなわち、目的５１６，５３２及び５５２等のＵとラベルされたバブル）、及び手動運転の最適化（すなわち、目的５１８，５３６及び５５８等のＭとラベルされたバブル）に関連する。例示された目的は例であり、他の目的も可能である。さらに、例示された選好順位付けグラフは非限定的な例であり、同じ又は異なる目的及びトポロジーを含む他の選好順位付けグラフも可能である。これらの目的のそれぞれは、人間にとって有意であり得るそれぞれの意味ラベルに関連付けられる。本明細書でさらに説明するように、ユーザは、意味ラベルを使用して、車線レベルルートプランナのためのルート選好を示すことができる。

例５１０は、連鎖選好順位付けグラフの例である。例５１０の選好順位付けグラフを使用する場合（すなわち、目的が連鎖的に関連している場合）、第１の高速目的が最大化され（すなわち、目的５１２）、次に、快適性目的（すなわち、目的５１４）は、それが高速目的のスラック５１３（例えば、３のスラック）内であれば最大化され、次に、市街地目的（すなわち、目的５１６）は、快適性目的のスラック５１５（例えば、１のスラック）内であれば最大化され、これはそれが最初の目的のスラック５１３内であることを保証するためにすでに制約されており、最後に、手動走行目的（すなわち、目的５１８）は、すでに制約されている市街地目的のスラック５１７（例えば、７のスラック）以内であれば最大化される。

例５１０は、車線レベルルートプランナが高速道路（すなわち、目的５１２）を好むが、ルートプランナがより快適な別の代替ルート（すなわち、目的５１４）を選択するために、３分の余分な時間（すなわち、スラック５１３）を許容すると解釈されてもよく（例えば、理解され得る）、この代替ルートも快適性目的を最大化する。そのため、ユーザは、「可能な限り最速の道路を与えてもらうが、より快適な車線を運転するために、最速よりも３分長いルートを許可する」を本質的に示す入力を提供（例えば、コマンドを発行）してもよい。また、例５１０の他の目的についても同様である。スラック変数の測定単位は、それが制約する目的の測定単位と同じであることに注意すべきである。

以下でさらに説明するように、ユーザは、ルートプランナがグラフィカルユーザインタフェース（例えば、ドラッグアンドドロップインターフェース、リスト等）を介して、又はユーザが選好を提供するための他のやり方を介して、選好順位付けグラフに変換し得る口頭コマンドを使用して、目的の選好を指定することができる。

例５３０は、扇形の選好順位付けグラフの一例である。例５３０の選好順位付けグラフが使用される場合（つまり、目的がこのような扇形のような関係を持っている場合）、最適ポリシーは、市街地目的（すなわち、目的５３２）、快適性目的（すなわち、目的５３４）、及び手動運転目的（すなわち、目的５３６）に対して同時に計算される。次に、３つの最初の目的のスラック５３３，５３５及び５３７（すなわち、それぞれスラック値５、９、及び２）を条件として、高速目的（すなわち、目的５３８）を最大化する最終ポリシーが決定される。これは、最初の３つの目的のポリシー集合の交点を取得し、最後の目的のためにその空間を検索することと等価である。

例５５０は、例５１０及び５３０を混合した有向グラフの一例である。

各目的（例えば、例５００のバブル）に対して、車線レベルルートプランナは、その目的を満たすルートの集合を取得する。例えば、目的５５２に関して、車線レベルルートプランナは、最適ルート（例えば、できるだけ多くの市街地車線で目的地に到達するための最小ルート）を識別する。目標に到達するために、１分間のスラック（すなわち、スラック５５３）が許容される。そのため、ルートプランナは、目標到達の周囲で可能性のエンベロープを提供すると考えることができる。つまり、ルートプランナは、最適な時間の１分以内にある全てのルート、及びそれらが市街地道路上にあるかどうかを識別することができる。したがって、スラック５５３内で目的５５２を満たすルートの最初の集合が返される。

ルートの第２の集合は、目的５５４（すなわち、快適とマークされた車線を走行すること）を満たし、最も快適なルートの６分（すなわち、スラック５５５）以内である。同様に、９分（すなわち、スラック５５７）以内に手動運転目的を満たす第３のルートの集合も得られ、以下同様である。取得されたルートの全ての集合は目的５５６に渡され、このシンク目的から取得されたルートは、取得されたルートの全ての集合に入っている必要がる。状況によっては、全ての制約及びスラックを満たすルートは不可能な場合がある。

例５００のバブルへの入力矢印は、その目的が与えられたルートの集合（又は、選好順位付けグラフの構成に応じて、複数の集合）内にあるようにその目的を制約すると考えることができることに留意されたい。したがって、親矢印がない（つまり、入力矢印がない）場合、任意のスラック（存在する場合）内で目的を満たす任意のルートがルートプランナによって選択され得る。一方、選択された（複数の）ルートは、親の目的によって提供されたルート内に入っている必要がある。そのため、下流の目的は、提供された（例えば、入力の）ルートの（複数の）集合のプルーニングと考えることができる。

一例では、選好順位付けグラフの代わりに、スカラー化関数を使用して、全ての報酬（例えば、コスト）を単一の値にマッピング（例えば、結合等）することができる。スカラー化関数を使用して、モデル／問題を最短経路最適化問題（ＳＳＰ）ＭＤＰ又はＰＯＭＤＰに変換することができる。スカラー化関数を使用して、次の即時アクションの長期的な有用性を示す単一の値が取得されてもよく、これは単一の値を取得するために期待されるコストを結合する。形式的には、スカラー化関数f：C→Rは、単一の値に関してf(V(s))＝V_f (s)であり、コスト関数に関してf(C(s))＝C_f (s)であるようなものであってもよい。一例では、スカラー化関数は、目的の加重和又は目的の非線形関数であってもよい。所望の最適化に応じて、異なる重みが使用されてもよい。一例では、車線レベルルートプランニングは、確率を除去することによって、古典的プランニング（ＣＰ）問題としてモデル化され得る。

使用するモデルに関係なく、車線レベルルートプランニングは階層的であってもよい。理解できるように、可能な車線の数が多いほど、仮にあった場合に、ポリシーの計算に時間がかかる可能性がある。車線レベルルートプランナが推論する車線セグメントの数を制限するために、車線レベルルートプランニングは階層的なやり方で実行され得る。例えば、フロリダ州マイアミの出発地及びアラスカ州フェアバンクスの目的地の場合、車線レベルルートプランナは、米国の道路をクラスタにグループ化し、クラスタ間の車線レベルルートを計画してから、ルートの各クラスタ内でルートレベルプランニングを実行してもよい。

一例では、前述のように、車線レベルルートプランニングは、トポロジカル部分観測ＭＤＰ（ＴＰＯＭＤＰ）としてモデル化され、例えば、（１）各州の交通レベル、（２）運転者及び／又は車両のうちの少なくとも１つの能力、及び／又は（３）様々な目的コストに対する信念を可能にしてもよい。

より形式的には、ＴＰＯＭＤＰはタプル〈S，A，Ω，T，O，R，Ｅ，δ〉として記述され得る。

Sは有限の状態集合である。Aは有限のアクション集合である。Ωは有限の観測集合である。Tは状態遷移関数であり、T(s，a，s')＝Ｐｒ（s'｜s，a）は、アクションaが状態sで実行されたことを考慮した後続状態s'の確率である。Oは観測関数であり、O(a，s'，ω)＝Ｐｒ（w｜a，s'）は、アクションaが実行された結果、後続状態s'になったことを考慮した観測確率ωである。

Ｒは報酬関数のベクトルであり、これは前述のコストベクトルCと等価であり得る。前述のように、Ｅはｋ個の報酬（例えば、コスト）に対するエッジの集合であり、一般性を失うことなく、報酬頂点ｋである１つのリーフ（すなわち、シンク）の報酬頂点を有する有向非巡回グラフを形成する。δは、エッジe＝〈i，j〉∈Eを非負のスラック制約δ（ｅ）≧０又は同等にδ（ｉ，ｊ）≧０にマッピングする関数である。

ＴＰＯＭＤＰは、世界の信念b∈B⊆Δ^｜S｜に対して動作し、ここで、Δ^｜S｜は状態Ｓに対する確率分布であり、且つ標準｜Ｓ｜－ｓｉｍｐｌｅｘとしてである。信念bは、状態に対する確率分布である。信念は、全ての時間ステップ、及び全ての前方、後方、後続、先行等の車線セグメントに存在する。信念bの場合、アクションaを実行して観察ωを行った後で、状態s’に対する次の信念b_baωは、

であり、ここで、∝は比例を意味する。

前述のように、ＴＭＤＰはΩ＝Ｓ及びO(a，s，s')＝１であるＴＰＯＭＤＰのサブクラスであり、到達可能な信念b∈Bは全てのs∈Sに対してb(s)＝１である。

無限区間ＴＰＯＭＤＰの目的は、割引係数γ∈［０，１）の初期信念ｂ_０から期待される割引報酬を最大化しようとすることである。ポリシーπの場合、期待される割引報酬は、

によって与えられてもよく、b^tは、遷移関数Ｔ及び観測関数Ｏに続いて生成された時間ｔの信念に対する確率変数を表し、これはアクションaが実行された結果として後続状態s’となったことを考慮した特定の観測の確率である。

は、信念bにおける期待される報酬であり、以下によって与えられ得る。

式（３）において、R(b，a)＝Σ_sb(s)R（s，a）及びb_bπ(b)ω'は式（２）の信念の更新に従う。

ここで述べたように、車線レベルルートプランナは、ナビゲーションマップを使用してポリシーを取得する。一例では、ナビゲーションマップは学習され得る。ここで使用される場合、学習されるとは、ナビゲーションマップが進化され得ることを含む。ナビゲーションマップは、事前に設定された車線情報を含んでもよく、車線レベル情報が１つ以上の車両から取得されると、事前に設定された車線情報は、取得された車線レベル情報を反映する（例えば、組み込む）ように進化させることができる。ナビゲーションマップは、最初に車線レベル情報を含まなくてもよく、車線レベル情報は、１つ以上の車両から受信した車線レベル情報に基づいて構築（例えば、投入）され得る。

車線レベル情報は、継続的に受信されてもよく、新たに受信した車線レベル情報を使用してナビゲーションマップが定期的に更新されてもよい。ナビゲーションマップは、（例えば、特定の車両に配備される）特定の車両のナビゲーションマップであってもよく、ナビゲーションマップは、車両自身からの車線レベル情報に基づいて更新され得る。

追加的に又は代替的に、ナビゲーションマップは、多くの車両から（サーバ等において）受信した車線レベル情報に基づいて学習され得る。車線レベル情報はサーバと共にあってもよく、これはクラウド型のサーバであり得る。そのため、複数の車両は、その後、（実際に道路を走行する前に）時間に関する正確な初期推定、（新しいエリアの）人気のあるルートに関する選好、及び（同じコード／ハードウェアを共有する車両の）車両軍が通行するルートを計画しているべき場所に関する能力情報を受信し得る。

車線レベル情報は、多くの車両から取得されてもよい。特定の顧客が所有する車両は、車線レベル情報を生成し得る。（タクシーサービス、デリバリーサービス、その他のサービス等を提供する）展開された車両群は、車線レベル情報を生成し得る。車両からの車線レベル情報は、車両のセンサから受信したデータを使用して生成され得る。一例では、生センサデータがサーバに送信され、サーバは、生センサデータを使用して車線レベル情報を生成し得る。

このように、ナビゲーションマップは、異なる車線及び異なる道路の異なる車線セグメントについて学習された過去の走行パターン及び特性を含み得る。過去の走行パターンは、特定の車両、特定の車両の特定の運転者、又は複数の車両の集約された学習された履歴走行パターンのいずれかであり得る。

１人以上の運転者の走行パターンが学習され、車線レベルルートプランニングに使用され得る。ナビゲーションマップは、道路状態に関する情報を含んでもよい。したがって、学習されたナビゲーションマップは、運転者の運転挙動の履歴及び／又は車線（より具体的には車線セグメント）の特性を活用／組み込むことができるものであり、車線レベルルートプランニングを可能にする。

（例えば、クラウド型のサーバに接続されている）複数の接続された車両からの車線レベル情報は、共有ナビゲーションマップに結合されてもよい。接続された各車両は、１つ以上の通信デバイス２４０等のサーバに車線レベル情報を送信してもよく、これは、取得した車線レベル情報の全てを集約してナビゲーションマップを取得することができる。多車両多目的学習（すなわち、複数の接続車両からの車線レベル情報）は、単一の車両の学習を大幅に高速化することができ、車両が道路自体を走行する前にルートの値（例えば、車線レベル情報）を学習することを可能にする。

経時的に、サーバは、特定の車両が走行した道路だけでなく、多くの運転者がエリア内で走行した多くの車線セグメントに関する情報を受信し得る。また、車線レベル情報は、車両プラットフォーム（例えば、日産リーフ、日産セントラ、日産ローグ等）の識別情報を含んでもよい。いくつかの例では、車線レベル情報は、車線レベル情報が生成された特定の運転者の情報（例えば、選好等）も含み得る。受信した車線レベル情報トレースを使用して、サーバは、その情報を車両（すなわち、車両仕様）、運転スタイル、道路（例えば、車線及び車線セグメント状態を含む）、及び／又はその他の基準に依存するものに分離して、それぞれが特定の車両、特定の車両プラットフォーム、特定の運転者、特定の運転スタイル等に固有の一意のナビゲーションマップを作成することができる。

上述したように、道路の車線の車線セグメントに関して、及び学習を介して、少なくともいくつかの環境情報、車両情報、人的情報、より少ない、より多い、その他の情報、又はそれらの組み合わせが学習され得る。学習された情報は、確率に変換され得る。確率は、本明細書に記載されるように、状態遷移関数に組み込まれてもよく、又は状態遷移関数によって使用され得る。確率は、計算されるルート（例えば、ポリシー）に関して目的を設定する際にも使用され得る。

環境情報は、交通パターン、歩行者パターン、車両（例えば、他のＡＶ）による車線セグメントの通行困難情報、気象情報、負担情報、より多い、より少ない、その他の環境情報の１つ以上、又はこれらの組み合わせを含み得る。車両情報は、車線セグメントごとの平均速度情報、エネルギー使用（例えば、電気自動車のバッテリ使用、ハイブリッド自動車のガソリン及びバッテリ使用、又は内燃機関自動車のガソリン使用）、より多い、より少ない、その他の車両情報のうちの１つ以上、又はこれらの組み合わせを含み得る。

人的情報は、好ましいルート、好ましい車線、制御移行の要求（自動運転から手動運転へ、又は手動運転から自動運転へ等）、運転者のオーバライドによる能力モデルの更新、より多い、より少ない、その他の人的情報、又はそれらの組み合わせのうちの１つ以上を含んでもよい。制御移行の要求は、制御の移行が要求された車線セグメントを含んでもよい。制御移行の要求は、計画された後続車線セグメント、及びどの後続車線セグメントを人間の運転者が取ったかを含んでもよい。

車両がルートを通行しているときに（ナビゲーションマップの現在の状態に基づいているか、又は車線レベルプランナを介してルートを設定していないかにかかわらず）、車両のセンサを使用して、車線レベル情報に変換される情報を収集することができる。つまり、車両はシャドウモードにあり、センサを介して環境を監視していると考えられ得る。

センサからのデータは、例えば、限定されないが、道路（したがって、車線及び車線セグメント）が市街地か高速道路か、車線セグメントが通行困難であるかどうか、交通が密集しているかどうか、密度のレベル等を識別するために使用されてもよい。通行の困難さは、運転者のオーバライド量に基づいて識別されてもよい。つまり、自動運転の決定が人間によってオーバライド又は修正された回数、又は人間が自動制御によって提案されたのとは異なるやり方で車両を制御するように自動制御に指示した回数である。

負荷情報は、選択された車線変更の決定を与えられたユーザ（例えば、車両の乗員）が受け得るストレスのレベルを示し得る。説明するために、特定のルートは、混雑した又は高速の交通エリアで、比較的短い時間又は短い距離内で、車両が３つの車線セグメントを左に移動することを必要とする場合がある。このような状況は、ユーザにストレスを与え得る。このような負荷情報は、混雑エリアよりも前のはるかに早い車線セグメント遷移点を選択し、又はストレスのかかる状況を完全に回避するルートを選択するために使用されてもよい。

車線レベル情報を使用して、カウントが確率に変換され得るように、カウントを実行し得る。例えば、一般性を失うことなく、交通密度のカウントは、道路の１つの車線セグメントを通行して次の車線セグメントに移動するのにかかる時間等、１つの車線セグメントから別の車線セグメントに移動する確率に変換されてもよく、車線セグメント上の交通量が少なかった場合と交通が密集していた場合の履歴の回数のカウントを使用して、交通密度の確率を決定してもよく、車線セグメント上の速度が速い回数のカウントを使用して、車線セグメントを高速であると分類してもよく、車線セグメント上の速度が制限速度の－１０マイル以内であった回数のカウントを使用して、車線セグメントが快適性車線セグメントである確率を決定してもよく、以下同様である。

ナビゲーションマップは確率から構築され得る。つまり、ナビゲーションマップに確率を組み込み得る。ナビゲーションマップは、図４に関して説明したような遷移グラフである。ポリシーを取得する際には、車線レベル情報（例えば、確率）に基づいて、次のアクション（例えば、次の車線セグメントに真っすぐ移動する、左隣の車線セグメントに移動する等）が決定され得る。一般性を失わずに説明するために、次のアクションは、例えば、現在の車線セグメントが渋滞しているかどうかに基づいて隣接する車線セグメントが渋滞している確率を含む、本明細書に記載されている隣接する車線セグメントの確率に基づいて確率的に（又は確定的に）決定され得る。

ナビゲーションマップの車線レベル情報の少なくとも一部は、車線レベルルートプランナの目的を設定するために使用され得る。説明のため、限定されないが、前述のように、環境は通行困難を含んでもよく、（例えば、ユーザによって設定された）目的が自動運転を最大化する場合、ルートプランナは通行困難のある車線（又は車線セグメント）を回避するであろう。つまり、ルートプランナポリシーは、通行困難のある車線セグメントを回避するように計算される。

目的地への時間（これには、制限速度、道路の長さ、停止信号、交通密度、車線セグメントが高速車線であるかどうか等が含まれるか又は組み込まれ得る）、選好（これには、快適性、高速道路とは対照的な市街地道路、エネルギー消費等の少なくともいくつかのユーザ選好が含まれ得る）、及び能力（これには、車線セグメントが有能に自動的に通行できるか、又は有能に手動で通行できるかが含まれ得る）についての目的を検討する。

説明のため、限定されないが、時間、優先度、及び能力目的の少なくとも一部を使用してルートを計画することができるように、車両がルートを走行するときはいつでも、特定の車線セグメントを自動的に通行するための時間は完全停止の有無にかかわらず記録され得る。同様に、特定の車線セグメントを手動で通行する時間（つまり、人間が運転しているとき）も記録され得る。したがって、４つの平均持続時間が記録され得る。平均時間を使用して、自己ループ（停止）のＴＭＤＰ状態遷移を定義し得る。平均時間を使用して、例えば、自動運転（例えば、制御）対手動運転の状態に基づいて、通行時間の報酬／コストを定義し得る。

追加的に、人間が車線セグメントを運転するときはいつでも、後続の車線セグメントが記録され得る。後続の車線セグメントを使用して、選好に関する報酬／コストを［０、１］の範囲で定義してもよく、これは、人間が道路又は車線セグメントを運転した時間の比率であり得る。

さらに、人間が自動制御をオーバライドするか、又は自動制御の下で車両が立ち往生する（すなわち、１分又はその他の時間の閾値等の第１の閾値を超えて前進しない）ときはいつでも、第１の値として－１が記録されてもよく、そうでなければ（例えば、自動制御がオーバライドされず、車両が立ち往生しない場合）、第２の値として０が記録され得る。記録された第１の値及び第２の値の平均は、能力の尺度として使用され得る。その逆は、人間の運転者の能力を学習するために使用され得る。例えば、手動制御の下では、車両が第２の時間の閾値（例えば、１分又はその他の時間閾値）を超えて移動しない場合、第３の値として－１が記録され得る。例えば、運転者車線レベルルートプランナによって識別された禁止された次のアクションに従わない場合、第４の値として－１が記録され得る。例えば、運転者がシームレスに隣接する車線セグメントに進む場合、第５の値として０が記録され得る。第３、第４、及び第５の値の平均は、車両が現在の車線セグメントにあるときに次のアクションを実行する人間の能力の尺度として記録され得る。

すでに述べたように、意味ラベルを使用して、車線レベルルートプランナによって計算されるルートの目的を定義し得る。意味ラベルの例は、「快適性」（及び／又は関連する意味概念）、「市街地」（及び／又は「高速道路」等の関連する意味概念）、「高速」（及び／また関連する意味概念）、「手動運転」（及び／又は「自動運転」等の関連する意味概念）等、図５に関して説明されたものを含む。より少ない、より多い、他の意味ラベル、又はそれらの組み合わせも可能である。説明するために、ユーザが快適な道路の選好を示す場合、車線レベルルートプランナは、「快適」とラベル付けされた車線セグメントを考慮してポリシーを計算する。

ここで、目的から意味ラベルへのマッピングは、１対１のマッピングである必要はないことに留意されたい。そのため、意味ラベルはいくつかの目的を組み合わせてもよく、又は１つの目的を使用して１つ以上の意味ラベルが定義されてもよい。

開示された実装の一態様において、多目的深層強化学習（ＭＯＤＲＬ）が使用され得る。強化学習又は深層強化学習において、深層ニューラルネットワーク（ＤＮＮ）を使用してポリシーを学習することができる。ＤＮＮは、代替的に又は追加的に、価値関数を学習するために使用され得る。そのため、強化学習技術がプランニング技術の代わりに使用され得る。強化学習では、目的はフィードバックからＤＮＮを介して学習され得る。フィードバックは、車線セグメントを通行する時間、能力に対する人間のオーバライド、又はその他のフィードバックの１つ以上を含み得る。強化学習では、確率を学習する代わりに、確率及びコストを組み合わせて、目標（すなわち、目的地）に到達するための期待値にする。

ある態様では、本明細書に記載のように、ＴＭＤＰはナビゲーションマップを使用してポリシーを取得し得る。別の態様では、ＴＰＯＭＤＰを使用してポリシーを取得し得る。ＴＰＯＭＤＰを使用すると、例えば、限定されないが、道路、車線、又は車線セグメント上の交通のレベル；新しい道路、車線、又は車線セグメントの能力の量；又は、本明細書に記載のその他の車線レベル情報に対する信念が有効になる。

図６は、本開示の実装によるナビゲーションマップの学習及び使用の概要６００を示す。車線レベルルートプランナは、車線レベル情報を取得する学習モジュールを含んでもよい。車線レベルルートプランナは車両で実行されてもよく、車線レベル情報は車両のナビゲーションマップに組み込まれ得る。車線レベル情報はサーバに送信されてもよく、サーバは複数の車両から車線レベル情報を受信してもよい。サーバは受信した車線レベル情報をナビゲーションマップに組み込み得る。その後、ナビゲーションマップは車線レベルルートプランナを使用してポリシー（例えば、ルート）を取得し得る。

概要６００は、起点６０８から目的地６１０まで（図示しない同一又は複数の車両によって）３つの異なるルート６０２，６０４及び６０６が取られたことを示す。走行中、車線セグメント６１２等の車線セグメントについて車線レベル情報が収集される。履歴６１４は学習された車線遷移を示し、履歴６１４における車線セグメントの陰影は車線セグメントの学習された特性を示す。履歴６１４は、本明細書に記載されるように学習された他の車線セグメント情報を含む。

ルートの少なくともいくつか（例えば、全て）に沿った車線セグメントの少なくともいくつか（例えば、全て）の履歴は、本明細書に記載されるように、ナビゲーションマップに結合（例えば、カウント）され得る。本明細書に記載されるように、複数の目的及び他の意味ラベルが、ボックス６１８によって示されるように、各車線セグメント履歴に記録され得る。

学習に基づいて、遷移グラフ６２０によって示される状態遷移グラフ構造（すなわち、上述の状態遷移関数T）が生成され得る。状態遷移グラフは、本明細書に記載されるように、ＳＳＰ ＭＤＰ又はＰＯＭＤＰモデルによって使用され得る。次に、車線レベル多目的車線レベルルートプランナのナビゲーションマップが出力される（例えば、生成される）。ナビゲーションマップの車線レベル情報は、車線セグメントの車両の全通行の平均を含む。例えば、車線レベル情報は、速度、停止、認識された交通の密度、バッテリ使用、車線変更成功率等の１つ以上の平均を含む。

学習に基づいて、ＳＳＰ ＭＤＰ又はＰＯＭＤＰモデルで使用されるコスト（報酬）関数も生成され得る。異なる目的の平均が、上記のように時間、制御の移行点、バッテリ使用、速度等を観察して報酬として記録され得る。報酬関数から、目的間においてスラックが可能かどうかを知ることができる。例えば、ルートの期待値が最適値より１０分長い場合、少なくとも１０のスラックが可能である。このような報酬関数及びスラックは、図５に関して説明され、選好順位付け６２２で示されるように、選好順位付けを設定するために使用され得る。

図７は、本開示の実施形態によるルートプランニングのためのナビゲーションマップを学習する技術の一例を示すフローチャート図である。ナビゲーションマップは、車線レベルルートプランナによって使用される。技術３００は、図１に示された車両１００等のホスト車両、図２に示された車両２１０／２１１のうちの１つ、半自律走行車、運転支援機能を含み得る他の車両、又は運転者等によって手動で制御される車両であり得る装置において部分的又は完全に実装され得る。装置は、図２の通信デバイス２４０であり得るサーバであり得る。

技術７００は、メモリに記憶される指示（例えば、命令）として実装され得る。メモリは、図１のメモリ１３４であり得る。メモリは、サーバのメモリであり得る。命令は、図１のプロセッサ１３３等のプロセッサによって実行され得る。技術７００は、専用のハードウェア又はファームウェアを使用して実装され得る。複数のプロセッサ、メモリ、又はその両方が使用されてもよい。

ステップ７０２において、技術７００は、道路の車線レベル情報を取得する。車線レベル情報は、道路の異なる車線の異なるセグメントの情報を含む。例えば、道路は第１の車線及び第２の車線を含み得る。車線レベル情報は、第１の車線に関連する第１の車線情報、及び第２の車線に関連する第２の車線情報を含む。

車線レベル情報は、ホスト車両で取得されてもよく、車線レベル情報を使用して、ホスト車両の（例えば、ホスト車両の中で使用される、ホスト車両が使用する、ホスト車両で利用可能な）ナビゲーションマップを進化させることができる。車線レベル情報は、複数の車両から車線レベル情報を取得するサーバで取得（例えば、受信）され得る。サーバは、それぞれの車線レベルルートプランナによって使用される進化したナビゲーションマップを車両に送信し得る。サーバは、進化したナビゲーションマップを使用してルート（例えば、ポリシー）を計算し得る。

上述したように、車線レベル情報は、環境情報、車両情報、又は人的情報の少なくとも１つを含んでもよい。環境情報は、車線セグメントの交通パターン、歩行者パターン、又は通行困難情報の少なくとも１つを含んでもよい。車両情報は、ユーザの選好ルート及びユーザによる制御の移行要求を含んでもよい。

一例では、道路の車線レベル情報を取得することは、道路上での停止を伴う道路の自動通行の第１の時間を記録すること、道路上での停止を伴わない道路の自動通行の第２の時間を記録すること、道路上での停止を伴う道路の手動通行の第３の時間を記録すること、及び道路上での停止を伴わない道路の手動通行の第４の時間を記録することを含んでもよい。一例では、道路の車線レベル情報を取得することは、手動通行中に後続車線セグメントを記録することを含んでもよい。一例では、道路の車線レベル情報を取得することは、自動走行制御の人間によるオーバライドを記録すること含んでもよい。道路の自動通行とは、車両が道路を通行するように自動的に制御されることを意味する。道路の手動通行とは、車両が道路を通行するように（人等によって）手動で制御されることを意味する。

ステップ７０４において、技術７００は、車線レベル情報を、目的地へのルートを取得するために使用され得る状態遷移関数に変換する。上述したように、状態遷移関数は、ＴＭＤＰ又はＴＰＯＭＤＰモデルのものであってもよい。目的地へのルートは、上述したように、ポリシーであってもよく、又はそれにカプセル化されてもよい。一例では、ポリシー、つまりルートは確率的である。

ステップ７０６において、技術７００は目的地を受信する。例えば、サーバ（より具体的には、サーバで実行される車線レベルルートプランナ）は、現在位置及び目的地を（例えば、ユーザ装置、車両のマッピングアプリケーション等から）受信して、ルートを取得し得る。例えば、装置で実行される車線レベルルートプランナは、ユーザ（運転者又は乗員等）から目的地を受信してもよく、車線レベルルートプランナはルートを取得し得る。例えば、車線レベルルートプランナは、装置の現在位置等に基づいて、ルートの起点位置を推測し得る。

ステップ７０８において、技術７００は、状態遷移関数を使用するモデルの解としてポリシーを取得する。

本明細書で使用される場合、「命令」という用語は、本明細書に開示の任意の方法を実行するための指示若しくは表現、又はその任意の部分若しくは複数の部分を含んでもよく、ハードウェア、ソフトウェア又はこれらの任意の組み合わせで実現されてもよい。例えば、命令は、本明細書に記載の各方法、アルゴリズム、態様又はこれらの組み合わせのいずれかを行うためにプロセッサによって実行され得るメモリに記憶されたコンピュータプログラム等の情報として実装されてもよい。命令又はその一部は、本明細書に記載の任意の方法、アルゴリズム、態様又はその組み合わせを行うための専用ハードウェアを含み得る専用プロセッサ又は回路として実装されてもよい。いくつかの実装では、命令の部分は、直接的に又はローカルエリアネットワーク、ワイドエリアネットワーク、インターネット又はこれらの組み合わせ等のネットワークを介して通信し得る複数の装置又は単一の装置上の複数のプロセッサに分散されてもよい。

本明細書で使用される場合、「例示」、「実施形態」、「実装」、「態様」、「特徴」又は「要素」という用語は、用例、例示又は実例としての役割を果たすことを示している。明示されない限り、任意の例示、実施形態、実装、態様、特徴又は要素が、互いの例示、実施形態、実装、態様、特徴又は要素から独立しており、任意の他の例示、実施形態、実装、態様、特徴又は要素と組み合わせて使用されてもよい。

本明細書で使用される場合、「決定」及び「識別」又はこれらの任意の変形の用語は、図示の及び本明細書に記載の１つ以上の装置を使用するいかなるやり方で選択、確認、計算、検索、受信、決定、確立、取得、又は他のやり方で識別又は決定することを含んでいる。

本明細書で使用される場合、「又は」という用語は、特に明記されていない限り、又は文脈から明らかな場合を除き、排他的な「又は」ではなく包含的な「又は」を意味することが意図されている。さらに、本願及び添付の請求項の中で使用される“ａ”及び“ａｎ”という冠詞は、一般に、単数形を指していることが文脈から明確であるか又は他に特段の定めがない限り、「１つ以上の」を意味すると解釈されるべきである。

さらに、説明の簡潔のため、本明細書の図面及び説明は一連のステップ又は段階又はシーケンスを含み得るが、本明細書に開示の方法の要素は、様々な順番で又は同時に起こってもよい。さらに、本明細書に開示の方法の要素は、本明細書に明示的に提示及び開示されていない他の要素と共に起こってもよい。さらに、本明細書に記載の方法の全ての要素が、本開示による方法を実装することを要求されるとは限らない。態様、特徴及び要素は特定の組み合わせで本明細書に記載されているが、各態様、特徴又は要素は、他の態様、特徴及び要素と共に又はそれらなしで独立して又は様々な組み合わせで使用されてもよい。

上記の態様、例示及び実装は、本開示の理解を容易にするために記載されており、限定するものではない。対照的に、本開示は、添付の特許請求の範囲内に含まれる様々な修正及び等価な構成を包含しており、特許請求の範囲は、法的に認められている全てのこのような修正及び均等構造を包含するように最も広く解釈されるべきである。

Claims (13)

1. ルートプランニングのための方法において、
   目的地を受信することと、
   マップを使用して前記目的地への車線レベルルートを取得することであって、前記車線レベルルートは、道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含み、前記車線レベルルートは、１つ以上の目的を使用して計算され、前記１つ以上の目的は、時間に関する第１の目的、快適性に関する第２の目的、自律性に関する第３の目的、又は市街地車線セグメントに関する第４の目的のうち少なくとも２つを含み、前記１つ以上の目的は、スラック変数を含む選好順位付けにおいて関連していることと、
   前記車線レベルルートを通行するようにＡＶ（自律走行車）を制御することと
   を含む、方法。
2. 前記車線レベルルートは、偶発事象ルートを含む、請求項１に記載の方法。
3. 前記車線レベルルートを通行するように前記ＡＶを制御することは、
   前記第１のセグメントから前記第２のセグメントへの遷移不能に応答して、前記偶発事象ルートに従って前記ＡＶを制御すること
   を含む、請求項２に記載の方法。
4. 前記第１の車線及び前記第２の車線は、前記道路の同一車線である、請求項１に記載の方法。
5. 前記選好順位付けは、有向非巡回グラフである、請求項１に記載の方法。
6. 前記選好順位付けは扇形選好順位付けグラフである、請求項５に記載の方法。
7. 前記マップを使用して前記目的地への前記車線レベルルートを取得することは、
   前記ＡＶが前記マップの第１の車線セグメント上にある場合に、前記第１の車線セグメントに隣接する第２の車線セグメントに移動するように前記ＡＶを制御するためのアクションを提供するポリシーを取得すること
   を含む、請求項１に記載の方法。
8. 前記車線レベルルートは、前記１つ以上の目的のスカラー化関数を使用して計算される、請求項１に記載の方法。
9. ルートプランニングのための装置において、
   プロセッサを備えており、前記プロセッサは、
   目的地を受信することと、
   マップを使用して前記目的地への車線レベルルートを取得することであって、前記車線レベルルートは、道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含み、前記車線レベルルートは、１つ以上の目的を使用して計算され、前記１つ以上の目的は、時間に関する第１の目的、快適性に関する第２の目的、自律性に関する第３の目的、又は市街地車線セグメントに関する第４の目的のうち少なくとも２つを含み、前記１つ以上の目的は、スラック変数を含む選好順位付けにおいて関連していることと、
   前記車線レベルルートを通行するように車両を制御することと
   を行うように構成される、装置。
10. 前記車線レベルルートは、偶発事象ルートを含む、請求項９に記載の装置。
11. 前記車線レベルルートを通行するように前記車両を制御することは、
    前記第１のセグメントから前記第２のセグメントへの遷移不能に応答して、前記偶発事象ルートに従って前記車両を制御すること
    を含む、請求項１０に記載の装置。
12. 前記偶発事象ルートに従って車両を制御することは、ポリシーに従って車両を制御することを含む、請求項１１に記載の装置。
13. 実行可能命令を含む非一時的なコンピュータ可読媒体において、前記実行可能命令は、プロセッサによって実行されると、
    目的地を受信することと、
    マップを使用して前記目的地への車線レベルルートを取得することであって、前記車線レベルルートは、道路の第１の車線の第１のセグメントから前記道路の第２の車線の第２のセグメントへの遷移を含むことと、
    前記車線レベルルートを通行するように車両を制御することと
    を含む動作の実行を促進し、
    前記車線レベルルートは、前記車両が現在の車線セグメントにあることを考慮して、次の車線セグメントに移動するように前記車両を制御するためのアクションを提供するポリシーを取得するために、１つのタイプのマルコフ決定過程を解くことによって取得される、非一時的なコンピュータ可読媒体。

Images