JP6987150B2 - 自動運転車両の３ポイントターンの最適プランナー切り替え方法 - Google Patents

Description

本願の実施形態は、総体的に自動運転車両の操作に関し、具体的には、自動運転車両の３ポイントターンを計画することに関する。

自動運転モード（例えば、無人運転）で運行する車両は、乗員を、特に運転手を、幾つかの運転関連の責務から解放することができる。自動運転モードで運行する時、車両は、車載センサを使用して各位置にナビゲートされることができ、故に車両を最小のマン・マシン・インタラショションの状況で、または乗客がまったくいない状況で運行させることができる。

３ポイントターン（即ち、地図においてＵターンの位置として指定されていないところにおける車両の進行方向の方向逆転）は、自動運転車両の複雑な運動である。３ポイントターンの計画及びルーティングは、自動運転車両の通常操作の計画及びルーティングと遥かに異なる可能性がある。２つの計画及びルーティングのモードの間で切り替えをするか否かを決めることは、１つの挑戦的な任務であると言える。

本願の側面においては、自動運転車両（ＡＤＶ：autonomous driving vehicle）の操作において３ポイントターンを計画するためのコンピュータ実施の方法を提供する。当該方法は、第一の進行方向に関する第一の車線内にある起点から、第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、少なくとも部分的に第一のセグメント及び第二のセグメントに基づいて候補ルートに関する総コストを推定することと、総コストが閾値コストより低いことに応答して、候補ルートに基づいて３ポイントターンを計画して、ＡＤＶを３ポイントターンを行うように運転することとを備える。

本願のもう１つの側面においては、命令が記憶されている非一時性機器可読メディアを提供することによって、自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画する操作を実行する。当該操作は、第一の進行方向に関する第一の車線内にある起点から、第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、少なくとも部分的に第一のセグメント及び第二のセグメントに基づいて候補ルートに関する総コストを推定することと、総コストが閾値コストより低いことに応答して、候補ルートに基づいて３ポイントターンを計画して、ＡＤＶを３ポイントターンを行うように運転することとを備える。

本願の他の側面においては、データ処理システムを提供する。当該システムは、プロセッサと、命令を記憶するためにプロセッサに接続されているメモリとを備える。当該命令がプロセッサにより実行されると、プロセッサに自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画する操作を実行させる。前記操作は、第一の進行方向に関する第一の車線内にある起点から、第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、少なくとも部分的に第一のセグメント及び第二のセグメントに基づいて候補ルートに関する総コストを推定することと、総コストが閾値コストより低いことに応答して、候補ルートに基づいて３ポイントターンを計画して、ＡＤＶを３ポイントターンを行うように運転することとを備える。

本願の実施形態は、図面の各図の中で限定の方式ではなく、例をあげる方式で示されている。図面の中の同じ参照表記は、似ている構成要素を示す。

図１は、一つの実施形態によるネットワーク化システムを示すブロック図である。 図２は、一つの実施形態による自動運転車両の例示を示すブロック図である。 図３Ａは、一つの実施形態による自動運転車両の感知及び計画システムの例示を示すブロック図である。 図３Ｂは、一つの実施形態による自動運転車両の感知及び計画システムの例示を示すブロック図である。 図４は、典型的な３ポイントターンの運転シーンを示す図である。 図５は、一つの実施形態による様々なモジュールを示すブロック図である。 図６は、一つの実施形態による、計画された３ポイントターンルートを示す図である。 図７は、一つの実施形態による、自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画する例示する方法を示すフローチャート図である。 図８は、一つの実施形態によるデータ処理システムを示すブロック図である。

以下、討論の細部を参考しながら、本願の各実施形態と各側面について説明し、図面は、各実施形態を示す。以下の説明と図面は、本願に対する解釈であり、本願に対する限定ではないことが理解される。本願の各実施形態に対する全面的な理解をさせるために、多数の特定な細部を説明するが、場合によっては、本願の実施形態に対する簡潔な討論を行わせるために、周知の細部または通常の細部については、説明を省く時もある。

本明細書における“一つの実施形態”または“実施形態”の言及は、当該実施形態に関連して説明する特定の特徴、構造または特性が、本願の少なくとも一つの実施形態に含まれることを意味する。本明細書の各箇所に現れる短句“一つの実施形態において”は、必ずしも全部同一の実施形態を指すものではない。

幾つかの実施形態により、自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画して実行する。起点から終点を通り抜ける候補ルートを決定し、起点は、第一の進行方向に関する第一の車線内にあり、終点は、第二の進行方向に関する第二の車線内にあり、第一の進行方向と第二の進行方向が逆である。候補ルートは、部分的に重なる第一のセグメント、第二のセグメント及び第三のセグメントに分類され、第一のセグメントは、第一の進行方向に関し、第二のセグメントは、３ポイントターン領域に関し、第三のセグメントは、第二の進行方向に関する。所定コスト関数を用いて、少なくとも部分的に第一のセグメント及び第二のセグメントに基づいて候補ルートに関する総コストを推定する。総コストが閾値コストより低いか否かを判定する。総コストが閾値コストより低いと判定されたことに応答して、候補ルートに基づいて３ポイントターンを計画する。また、少なくとも部分的に計画された３ポイントターンに基づいて、ＡＤＶの操作を制御する運転信号を生成する。

１つの実施形態においては、候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索のような探索アルゴリズムを実行することを含む。なお、第一の進行方向及び第二の進行方向のそれぞれに関する第一の車線及び第二の車線の両方は、何れも探索可能及び接続可能であると見なされている。

１つの実施形態においては、総コストは、少なくとも障害物コスト及び残り車線長さコストを含む。障害物コストは、少なくとも部分的にＡＤＶと候補ルートの付近の１つ又は複数の障害物の中の各障害物との間の距離に基づいて推定する。残り車線長さコストは、少なくとも部分的に第一のセグメントの長さに基づいて推定する。残り車線の長さとは、目下の車線セグメント又はルートセグメントにおける残り車線の長さを指す。つまり、残り車線の長さは、車両の目下の位置と目下の車線セグメントの終点との間の距離である。

１つの実施形態においては、ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい場合、計画された３ポイントターンを完成させる。３ポイントターンを完成させると、ＡＤＶの操作が通常操作のモードに切り替えられる。

図１は、本願の一つの実施形態による自動運転車両のネットワーク配置を示すブロック図である。図１に示すように、ネットワーク配置１００は、ネットワーク１０２を通じて一つまたは複数のサーバ１０３〜１０４に通信可能に接続する自動運転車両１０１を含む。一台の自動運転車両しか示されていないが、複数台の自動運転車両がネットワーク１０２を通じて互いに接続し、及び／またはサーバ１０３〜１０４に接続しても良い。ネットワーク１０２は、任意のタイプのネットワークであっても良く、例えば、有線または無線のローカルエリアネットワーク（ＬＡＮ）、インターネットのようなワイドエリアネットワーク（ＷＡＮ）、移動体通信ネットワーク、衛星ネットワークまたはその組み合わせであっても良い。サーバ１０３〜１０４は、任意のタイプのサーバまたはサーバクラスタであっても良く、例えば、ネットワークまたはクラウドサーバ、アプリケーションサーバ、バックエンドサーバまたはその組み合わせであっても良い。サーバ１０３〜１０４は、データ分析サーバ、コンテンツサーバ、交通情報サーバ、地図と関心地点（ＭＰＯＩ：map and point of interest）サーバまたは位置サーバ等であっても良い。

自動運転車両は、自動運転モードで配置できる車両を指し、前記自動運転モードにおいて、運転手からの入力が非常に少ない状況、または運転手からの入力がない状況において車両が環境を通過するようにナビゲートされる。このような自動運転車両は、センサシステムを含むことができ、前記センサシステムは、車両の運行環境と関係のある情報を検出するように配置される一つまたは複数のセンサを有する。前記車両と関連するコントローラは、検出した情報を使用して車両が前記環境を通過するようにナビゲートを行う。自動運転車両１０１は、手動モード、全自動運転モードまたは部分自動運転モードで走行することができる。

一つの実施形態において、自動運転車両１０１は、感知・計画システム１１０と、車両制御システム１１１と、無線通信システム１１２と、ユーザインターフェースシステム１１３と、センサシステム１１５とを含むが、これらに限定されない。自動運転車両１０１は、さらに普通の車両に含まれる通常の構成要素、例えば、エンジン、ホイール、ステアリングホイール、トランスミッション等を含むことができ、前記構成要素は、複数の種類の通信信号及び／または命令を使って車両制御システム１１１及び／または感知・計画システム１１０によってコントロールされることができる。当該複数の種類の通信信号及び／または命令は、例えば、加速信号または命令、減速信号または命令、方向転換信号または命令、ブレーキ信号または命令等である。

構成要素１１０〜１１５は、インターコネクト、バス、ネットワークまたはその組み合わせを通じて互いに通信可能に接続することができる。例えば、構成要素１１０〜１１５は、コントローラエリアネットワーク（ＣＡＮ）バスを通じて互いに通信可能に接続することができる。ＣＡＮバスは、ホストコンピュータがない応用においてマイクロコントローラーと装置が互いに通信できるように設計された車両バス規格である。ＣＡＮバスは、最初は自動車内部の多重化電気配線用に設計されたメッセージベースのプロトコルであるが、多数のその他の環境においても使用される。

図２に示すように、一つの実施形態において、センサシステム１１５は、一つまたは複数のカメラ２１１と、グローバル・ポジショニング・システム（ＧＰＳ）ユニット２１２と、慣性検出装置（ＩＭＵ）２１３と、レーダユニット２１４と、光検出と測距（ＬＩＤＡＲ）ユニット２１５とを含むが、これらに限定されない。ＧＰＳユニット２１２は、自動運転車両の位置に関する情報を提供するように操作可能なトランシーバを含んでも良い。ＩＭＵユニット２１３は、慣性加速度に基づいて自動運転車両の位置と向く方向の変化をセンシングすることができる。レーダユニット２１４は、無線信号を使って自動運転車両のローカル環境内のオブジェクトをセンシングするシステムを表すことができる。幾つかの実施形態において、オブジェクトをセンシングする以外に、レーダユニット２１４は、さらにオブジェクトの速度及び／または進行方向をセンシングすることができる。ＬＩＤＡＲユニット２１５は、レーザーを使って自動運転車両を取り巻く環境の中のオブジェクトをセンシングすることができる。その他のシステム構成要素以外に、ＬＩＤＡＲユニット２１５は、一つまたは複数のレーザー光源、レーザースキャンナー及び一つまたは複数の検出器を更に含むことができる。カメラ２１１は、自動運転車両の周辺環境の画像を採集するために使う一つまたは複数の装置を含むことができる。カメラ２１１は、スチールカメラ及び／またはビデオカメラであっても良い。カメラは、機械的に移動できるものであっても良く、例えば、カメラを回転及び／または傾斜するプラットフォームに取り付けても良い。

センサシステム１１５は、ソナーセンサ、赤外センサ、ステアリングセンサ、スロットルセンサ、ブレーキセンサ、及びオーディオセンサ（例えば、マイクロホン）のようなその他のセンサを更に含むことができる。オーディオセンサは、自動運転車両の周辺環境から音声を採集するように配置されても良い。ステアリングセンサは、ステアリングホイール、車両のホイールまたはその組み合わせの方向転換角度をセンシングするように配置されても良い。スロットル／ブレーキセンサは、それぞれ車両のスロットル位置とブレーキ位置をセンシングする。幾つかの状況において、スロットル／ブレーキセンサは、集積式スロットル／ブレーキセンサとして集積されても良い。

一つの実施形態において、車両制御システム１１１は、ステアリングユニット２０１と、スロットルユニット２０２（加速ユニットとも呼ばれる）と、ブレーキユニット２０３とを含むが、これらに限定されない。ステアリングユニット２０１は、車両の方向または進行方向を調整するために使用される。スロットルユニット２０２は、モーターまたはエンジンの速度をコントロールするために使用され、モーターまたはエンジンの速度は、車両の速度と加速度を更にコントロールする。ブレーキユニット２０３は、摩擦を提供することによって車両のホイールまたはタイヤを減速させ、ひいては車両を減速させる。図２に示す構成要素は、ハードウェア、ソフトウェアまたはその組み合わせとして実装できることに注意すべきである。

図１の参照に戻り、無線通信システム１１２は、自動運転車両１０１が例えば装置、センサ、その他の車両等の外部システムとの間で通信できるように許可する。例えば、無線通信システム１１２は、一つまたは複数の装置と直接的に無線通信することができ、または通信ネットワークを通じて無線通信することができ、例えば、ネットワーク１０２を通じてサーバ１０３〜１０４と通信することができる。無線通信システム１１２は、任意の移動体通信ネットワークまたは無線ローカルエリアネットワーク（ＷＬＡＮ）を使用することができ、例えば、ＷＩＦＩを使って他の構成要素またはシステムと通信する。無線通信システム１１２は、例えば、赤外線リンク、ブルートゥース等を使って装置（例えば、乗客のモバイル装置、ディスプレイ装置、車両１０１の内部のスピーカー）と直接通信することができる。ユーザインターフェースシステム１１３は、車両１０１の内部で実装された周辺装置の部分であっても良く、例えば、キーボード、タッチパネルディスプレイ装置、マイクロホンとスピーカー等である。

特に自動運転モードで操作するとき、自動運転車両１０１の機能の幾つかまたは全部は、感知・計画システム１１０によってコントロールまたは管理されることができる。感知・計画システム１１０は、センサシステム１１５、制御システム１１１、無線通信システム１１２及び／またはユーザインターフェースシステム１１３から情報を受信し、受信した情報を処理し、起点から目的地点までのルートまたは経路を計画し、そして計画と制御情報に基づいて車両１０１を運転するように、必要なハードウェア（例えば、プロセッサ、メモリ、記憶装置）とソフトウェア（例えば、オペレーティングシステム、計画とルーティングプログラム）を含む。代替できるように、感知・計画システム１１０は、車両制御システム１１１と一体に集積されても良い。

例えば、乗客としてのユーザは、例えば、ユーザインターフェースを通じて行程のスタート位置と目的地を指定することができる。感知・計画システム１１０は、行程に関するデータを獲得する。例えば、感知・計画システム１１０は、ＭＰＯＩサーバから位置とルートの情報を獲得することができ、前記ＭＰＯＩサーバは、サーバ１０３〜１０４の一部分であっても良い。位置サーバは、位置サービスを提供し、ＭＰＯＩサーバは、地図サービスと幾つかの位置のＰＯＩを提供する。代替できるように、この種類の位置とＭＰＯＩ情報は、感知・計画システム１１０の永続的記憶装置にローカル的にキャッシュされても良い。

自動運転車両１０１がルートに沿って移動する時、感知・計画システム１１０は、交通情報システムまたはサーバ（ＴＩＳ）からリアルタイムの交通情報を更に獲得することができる。サーバ１０３〜１０４は、サードパーティーによって操作されることができることに注意すべきである。代替できるように、サーバ１０３〜１０４の機能は、感知・計画システム１１０と一体に集積されても良い。安全でかつ効率よく指定の目的地に到達するように、リアルタイムの交通情報、ＭＰＯＩ情報、位置情報及びセンサシステム１１５によって検出またはセンシングされたリアルタイムのローカル環境データ（例えば、障害物、オブジェクト、付近車両）に基づいて、感知・計画システム１１０は、最適なルートを計画し、そして計画されたルートに基づき、例えば制御システム１１１を通じて車両１０１を運転する。

サーバ１０３は、各種の顧客のためにデータ分析サービスを実装するデータ分析システムであっても良い。一つの実施形態において、データ分析システム１０３は、データ収集器１２１と機械学習エンジン１２２を含む。データ収集器１２１は、各種車両（自動運転車両または人間の運転手によって運転される通常の車両）から運転統計データ１２３を収集する。運転統計データ１２３は、出された運転命令（例えば、スロットル、ブレーキ、ステアリング命令）及び車両のセンサが異なる時刻で捕捉した車両の反応（例えば、速度、加速、減速、方向）を表す情報を含む。運転統計データ１２３は、異なる時刻における運転環境を表す情報、例えば、ルート（スタート位置と目的地位置を含む）、ＭＰＯＩ、道路状況、気候状況等を更に含むことができる。

運転統計データ１２３に基づき、各種の目的のために、機械学習エンジン１２２は、ワンセットのルール、アルゴリズム及び／又は予測モジュール１２４を生成する又はトレーニングする。一つの実施形態においては、本願の実施形態により３ポイントターンをするコストを計算するために、アルゴリズム１２４は、３ポイントターンプランナーアルゴリズム及び／又はコスト関数を含んでも良い。そのあと、アルゴリズム１２４を、自動運転の期間でリアルタイムに使用されるように、ＡＤＶにアップロードすることができる。

図３Ａ及び図３Ｂは、一つの実施形態による自動運転車両の感知・計画システムの例示を示すブロック図である。当該システム３００は、図１の自動運転車両１０１の一部分として実装することができ、感知・計画システム１１０と、制御システム１１１と、センサシステム１１５とを含むが、これらに限定されない。図３Ａ及び図３Ｂに示すように、感知・計画システム１１０は、測位モジュール３０１と、感知モジュール３０２と、予測モジュール３０３と、決定モジュール３０４と、計画モジュール３０５と、制御モジュール３０６と、ルーティングモジュール３０７と、３ポイントターン計画モジュール３０８とを含むが、これらに限定されない。

モジュール３０１〜３０８の中の幾つかまたは全部は、ソフトウェア、ハードウェアまたはその組み合わせとして実装することができる。例えば、これらのモジュールは、永続的記憶装置３５２にインストールされ、メモリ３５１にロードされ、一つまたは複数のプロセッサ（図示せず）によって実装されても良い。これらのモジュールの中の幾つかまたは全部は、図２の車両制御システム１１１の幾つかまたは全部のモジュールと通信可能的に接続され、または一体に集積されることができることに注意すべきである。モジュール３０１〜３０８の中の幾つかは、一体に集積モジュールとして集積されても良い。例えば、３ポイントターン計画モジュール３０８は、計画モジュール３０５の一部として実現する又は集積されても良い。

測位モジュール３０１は、自動運転車両３００の目下位置（例えば、ＧＰＳユニット２１２を使って）を決め、ユーザの行程またはルートに関する任意のデータを管理する。測位モジュール３０１（地図・ルートモジュールとも呼ばれる）は、ユーザの行程またはルートに関する任意のデータを管理する。ユーザは、例えば、ユーザインターフェースを通じてログインし、行程のスタート位置と目的地を指定することができる。測位モジュール３０１は、行程に関するデータを獲得するために、地図・ルート情報３１１のような、自動運転車両３００のその他の構成要素と通信する。例えば、測位モジュール３０１は、位置サーバと、地図とＰＯＩ（ＭＰＯＩ）サーバから位置とルートの情報を獲得できる。位置サーバは、位置サービスを提供し、ＭＰＯＩサーバは、地図サービスと幾つかの位置のＰＯＩを提供し、よって地図・ルート情報３１１の一部分としてキャッシュできる。自動運転車両３００がルートに沿って移動する時、測位モジュール３０１は、交通情報システムまたはサーバからリアルタイムの交通情報を獲得することができる。

センサシステム１１５から提供されたセンサデータと測位モジュール３０１から獲得した定位情報に基づき、感知モジュール３０２は、周囲環境に対する感知を決める。感知情報は、普通の運転手が運転している車両の周辺から感知する情報を表すことができる。感知は、オブジェクトの形で、例えば、車線配置、交通信号、もう一つの車両の相対位置、通行人、建築物、横断歩道またはその他の交通関連標識（例えば、停止標識、譲れ標識）等を含むことができる。車線配置は、１つ又は複数の車線を記述する情報を含み、例えば、車線の形状（例えば、直線又は湾曲）、車線の幅、道路における車線の数、一方通行の車線又は双方向車線、合併車線又は分離車線、出口車線等である。

感知モジュール３０２は、一つまたは複数のカメラから採集した画像を処理分析し、自動運転車両の環境の中のオブジェクト及び／または特徴を識別するように、コンピュータビジョンシステムまたはコンピュータビジョンシステムの機能を含むことができる。前記オブジェクトは、交通信号、道路の境界、他の車両、通行人及び／または障害物等を含むことができる。コンピュータビジョンシステムは、オブジェクト識別アルゴリズム、ビデオトラッキング及びその他のコンピュータビジョン技術を使うことができる。幾つかの実施形態においては、コンピュータビジョンシステムは、環境地図を描き、オブジェクトを追跡し、オブジェクトの速度を見積もることができる。感知モジュール３０２は、さらに、例えば、レーダ及び／またはＬＩＤＡＲのようなその他のセンサから提供されたその他のセンターデータに基づき、オブジェクトを検出することができる。

各々のオブジェクトに対して、予測モジュール３０３は、オブジェクトがこの状況においてどう振舞うかを予測する。予測は、地図／ルート情報３１１と交通ルール３１２を考慮した、運転環境をその時刻で感知した感知データに基づいて実装される。例えば、オブジェクトは、反対方向の車両であり、かつ目下の運転環境は、交差点を含むなら、予測モジュール３０３は、車両が真っすぐに前へ移動するか、または曲がるかを予測する。感知データは、交差点に交通信号がないと表しているなら、予測モジュール３０３は、車両は交差点に進入する前に完全停車する必要があるかもしれないと予測する。感知データは、車両が左折専用車線または右折専用車線にあると表しているなら、予測モジュール３０３は、車両が左折または右折する可能性がより大きいと予測する。

各々のオブジェクトに対して、決定モジュール３０４は、オブジェクトをどう処置するかを決定する。例えば、特定のオブジェクト（例えば、交差するルートの中のもう一つの車両）及びオブジェクトを記述する元データ（例えば、速度、方向、曲がる角度）に対して、決定モジュール３０４は、オブジェクトと遭遇する時如何にするか（例えば、追い越し、譲り、停止、通過）を決定する。決定モジュール３０４は、永続的記憶装置３５２に記憶されている、例えば交通ルールまたは運転ルール３１２のようなルール集に従ってこれらを決定することができる。

ルーティングモジュール３０７は、起点から目的地までの１つ又は複数のルート又は経路を提供するように配置されている。スタート位置から目的地の位置までの所与の行程、例えば、ユーザから受け取った行程に対して、ルーティングモジュール３０７は、ルートと地図情報３１１を獲得し、スタート位置から目的地の位置に到達するまでの全ての可能なルートまたは経路を決定する。ルーティングモジュール３０７は、地形図の形式で決まった、スタート位置から目的地の位置に到達するまでの各ルートに対して、参考線を生成することができる。参考線は、例えば、その他の車両、障害物または交通状況の如何なる邪魔も受けない理想なルートまたは経路を指す。すなわち、道路にその他の車両、歩行者または障害物がないなら、ＡＤＶは、精確でまたはぴったりと参考線に従うべきである。そして、地形図は、決定モジュール３０４及び／または計画モジュール３０５に提供される。決定モジュール３０４及び／または計画モジュール３０５は、他のモジュールから提供される他のデータに基づいて最適なルートの中から一つのルートを選択して修正するように、全ての可能なルートを検査する。その他のデータは、例えば、測位モジュール３０１からの交通状況、感知モジュール３０２によって感知された運転環境、及び予測モジュール３０３によって予測された交通状況である。その時刻における特定の運転環境に従って、ＡＤＶをコントロールするための実際ルートまたは経路は、ルーティングモジュール３０７によって提供された参考線と接近することも、異なることもできる。

感知されたオブジェクトの中の各々に対する決定に基づき、計画モジュール３０５は、ルーティングモジュール３０７の提供した参考線をベースに、自動運転車両のためにルートまたは経路及び運転パラメータ（例えば、距離、速度及び／または曲がる角度）を計画する。言い換えれば、所与のオブジェクトに対して、決定モジュール３０４は、当該オブジェクトに対して何をするかを決定し、計画モジュール３０５は、どうやってそれをするかを決める。例えば、所与のオブジェクトに対して、決定モジュール３０４は、前記オブジェクトを通過すると決定し、計画モジュール３０５は、前記オブジェクトの左側から通過するか、または右側から通過するかを決める。車両３００が次の移動サイクル（例えば、次のルート／経路セグメント）でどのように移動するかに関する情報を含む計画と制御データは、計画モジュール３０５によって生成される。例えば、計画と制御データは、車両３００が１時間３０マイル（ｍｐｈ）の速度で１０メートルを移動してから、２５ｍｐｈの速度で右側車線に変更すると指示する。

計画と制御データに基づき、制御モジュール３０６は、計画と制御データによって限定されたルートまたは経路に従って、適切な命令または信号を車両制御システム１１１に送信することを通じて、自動運転車両を制御し運転する。経路またはルートに沿って異なる時刻において適切な車両設置または運転パラメータ（例えば、スロットル、ブレーキとステアリング命令）を使用し、車両をルートまたは経路の第１の地点から第２の地点まで運転できるように、前記計画と制御データは、十分の情報を含む。

一つの実施形態において、計画段階は、多数の計画周期（命令周期とも呼ばれる）の中で実装され、例えば、各時間間隔が１００ミリ秒（ｍｓ）の周期の中で実装される。計画周期または命令周期の中の各々に対して、計画と制御データに基づいて一つまたは複数の制御命令を発行する。即ち、各々の１００ｍｓに対して、計画モジュール３０５は、次のルートセグメントまたは経路セグメントを計画し、例えば、目標位置及びＡＤＶが目標位置に到達するまでの時間を含む。代替できるように、計画モジュール３０５は、具体的な速度、方向及び／または曲がる角度等を規定できる。一つの実施形態において、計画モジュール３０５は、次の予定時間間隔（例えば、５秒）のためにルートセグメントまたは経路セグメントを計画する。各計画周期に対して、計画モジュール３０５は、前の周期で計画した目標位置に基づき、目下の周期（例えば、次の５秒）に使用される目標位置を計画する。そして、制御モジュール３０６は、目下の周期の計画と制御データに基づき、一つまたは複数の制御命令（例えば、スロットル、ブレーキ、ステアリング制御命令）を生成する。

決定モジュール３０４と計画モジュール３０５は、集積モジュールとして集積されることができることに注意すべきである。自動運転車両の運転経路を決めるように、決定モジュール３０４／計画モジュール３０５は、ナビゲーションシステムまたはナビゲーションシステムの機能を含むことができる。例えば、自動運転車両がしっかりと感知した障害物を避けながら、大体最終目的地に到達するような、車線に基づく経路に沿って進むように、ナビゲーションシステムは、一連の速度と進行方向を決めることができる。目的地は、ユーザインターフェースシステム１１３を経由して行われたユーザの入力に従って設定することができる。ナビゲーションシステムは、自動運転車両が運行していると同時に、動的に運転経路を更新できる。自動運転車両の運転経路を決めるために、ナビゲーションシステムは、ＧＰＳシステムからのデータと、一つまたは複数の地図のデータとを合併することができる。

一つの実施形態において、３ポイントターン（ＴＰＴ）計画モジュール３０８は、３ポイントターンの決定又は推薦を決定して計画モジュール３０５に提供する責任を負う。上述したように、ＴＰＴ計画モジュール３０８は、計画モジュール３０５の一部として実現しても良い。決定モジュール３０４は、３ポイントターンをするように決定すると、ＴＰＴ計画モジュール３０８は、当該時刻における３ポイントターンを実行することができるかどうかを決定するように配置され、実行できれば、１つ又は複数のＴＰＴアルゴリズム３１３を用いてどのように３ポイントターンを実行するかを決定する。

図４に示すように、３ポイントターンを実行するかどうかを決定する際、様々な要素を考える必要がある。ＡＤＶ３３０が３ポイントターンを実行するように決定した場合、経路３４１に沿って相対の車線または交通の遠いほうの車線カーブに向かって第１の前進曲がりを行う必要がある。そして、ＡＤＶは、経路３４２に沿って目下の車線の近いほうの車線カーブに向かって後ろへ移動する必要がある。その後、ＡＤＶは、経路３４３に沿ってもう１つの前進曲がりを行って３ポイントターンを完成させる必要がある。他の障害物が存在する可能性があり、例えば、反対車線におけるＡＤＶ３３０に向かう他の一台の車両３３５である。二台の車両３３０及び３３５の間の距離が近すぎると、３ポイントターンを行うことは、安全ではない可能性がある。類似的に、残り車線の長さが十分じゃないと、３ポイントターンを行うための十分なスペースがない可能性がある。３ポイントターンを行うかどうか、及び、どのように３ポイントターンを行うかを決定する際、これらの状況を要素として考慮する必要がある。残り車線の長さとは、目下の車線セグメント又はルートセグメントの中の残り車線の長さを指す。つまり、残り車線の長さは、車両の目下の位置と目下の車線セグメントの終点との間の距離である。

図５は、一つの実施形態による３ポイントターンモジュールの各種モジュールを示すブロック図４００である。起点から終点を通り抜ける候補ルートを決定する。起点は、第一の進行方向（例えば、目下の進行方向）に関する第一の車線内にある。終点は、第二の進行方向（例えば、目下の方向に対する反対方向）に関する第二の車線内にある。第二の進行方向と第一の進行方向は、逆である。起点及び終点は、ルートポイント４１０と総称しても良い。候補ルートを決定する際、ＴＰＴ計画モジュール３０８の探索モジュールは、地図データに対してＡ−Ｓｔａｒ（Ａ^＊）探索４２０を実行し、なお、第一の進行方向及び第二の進行方向のそれぞれに関する第一の車線及び第二の車線は、探索可能及び接続可能であると見なされている。

Ａ−Ｓｔａｒ（Ａ^＊）探索は、経路探し及びグラフ走査のために幅広く用いられているコンピュータアルゴリズムであり、多数の点（「ノード」と称する）の間において経路を探すプロセスである。その性能及び正確性によって幅広く使用されている。Ａ^＊は、一種のインフォームド探索アルゴリズム又は最良優先探索であり、重み付きグラフに基づいて作られたことを意味する。グラフの特定の開始ノードから、最もコストの少ない、所与の目標ノードに到達する経路（最小の進行距離、最短の時間等）を探すことを目的としている。次の方法により上記の目的を実現する：開始ノードを起点とする経路のツリーを維持し、終了基準が満たされるまで一度に１エッジずつそれらの経路を拡張する。そのメインループの毎回の繰り返しにおいて、Ａ^＊は、その経路の中のどの経路を拡張するかを決定する必要がある。これは、経路のコスト及び経路を目標まで拡張するのに必要とするコストの見積もりに基づいて実現されるものである。選択された、拡張する経路は、起点から目標までの経路であり又は拡張される経路がない場合、Ａ^＊は、終了する。

一つの実施形態においては、ＴＰＴ計画モジュール３０８は、所定のセグメントアルゴリズム又は基準に基づいてルート候補をルートセグメントに分割し、ルートセグメントに対して分類を行うために、ルートセグメンタ又はセグメントモジュール３２１を備える。候補ルートが部分的に重なる第一のセグメント４３０、第二のセグメント４３２及び第三のセグメント４３４に分類され、第一のセグメント４３０は、第一の進行方向に関し、第二のセグメント４３２は、３ポイントターン領域に関し、第三のセグメント４３４は、第二の進行方向に関する。

ＴＰＴ計画モジュール３０８は、所定コスト関数を用いて３ポイントターンを行うコストを計算するために、コスト計算器３２２を更に備え、当該所定コスト関数は、ＴＰＴアルゴリズム３１３の一部であっても良い。具体的には、候補ルートに関する総コストは、少なくとも部分的に第一のセグメント４３０及び第二のセグメント４３２に基づき、コスト評価モジュール４４０において推定される。総コストが所定の閾値コストより低いか否かを判定する。閾値コストは、経験により決定できる調整可能なパラメータである。総コストが閾値コストより低いと判定されたことに応答して、候補ルートに基づいて３ポイントターンプランナー４４２において３ポイントターンを計画し、なお、ＴＰＴプランナー４４２は、計画モジュール３０５の一部として実現することができる。また、少なくとも部分的に計画された３ポイントターンに基づいて、ＡＤＶの操作を制御する運転信号を生成する。

一つの実施形態においては、総コストは、少なくとも障害物コスト及び残り車線長さコストを含む。障害物コストは、少なくとも部分的にＡＤＶと候補ルートの付近の１つ又は複数の障害物（例えば、候補ルートとの距離が閾値より短い障害物）の中のそれぞれの障害物との間の距離に基づいて推定される。残り車線長さコストは、少なくとも部分的に第一のセグメントの長さに基づいて推定される。具体的には、総コストは、コスト関数に基づいて推定することができる：

なお、

は、障害物コストを表し、即ち、所定の接近度内の全ての障害物の各々の障害物コストを加えることによって得られた総障害物コストである。

は、残り車線長さコストを表す。パラメータｄｉｓは、車両と障害物と間の距離を表す。デルタｓ（Δｓ）は、残り車線の長さを表す。パラメータα、λ、β及びδは、経験により決定することができる調整可能なパラメータである。

前記コスト関数に示すように、車両と障害物との間の距離が比較的短い時、相応する障害物コストがより高くなり、これは、３ポイントターンを行うことが安全ではない可能性があることを意味する。なぜならば、付近に障害物が存在しているからである。類似的には、残り車線の長さが比較的短い時、コストがより高くなり、なぜならば、３ポイントターンを行うための十分なスペースがない可能性があるからである。

一つの実施形態においては、データ分析システム（例えば、図１のサーバ１０３）により類似する走行環境又は状況において走行する大量の車両から収集された大量の運転統計に基づいて前記コスト関数及び関連パラメータを決定することができる。総コストが所定の閾値より低い時、ＴＰＴプランナー４４２を呼び出して計画と車両制御を行うことによって、３ポイントターンを行わせる。

一つの実施形態においては、完成条件検査モジュール４５０は、ＡＤＶの進行方向と参考進行方向との間の差が進行方向差の閾値より小さいと判定された時、計画された３ポイントターンを完成させる。進行方向差の閾値は、経験により決定することができる調整可能なパラメータである。３ポイントターンを完成させると、ＡＤＶの操作が通常操作のモード（通常プランナー４６０）に切り換えられる。

図６は、一つの実施形態による計画された３ポイントターンルート５００を示す図である。ルート５００は、起点５１０からスタートし、かつ終点５１２を通り抜け、起点は、第一の進行方向に関する第一の車線５２０内にあり、終点は、第一の進行方向と逆の第二の進行方向に関する第二の車線５２２内にある。第一の車線５２０は、サブセグメント１〜４を含み、第二の車線５２２は、サブセグメント５〜７を含む。ルート５００は、部分的に重なる第一のセグメント、第二のセグメント及び第三のセグメントに分類され、第一のセグメントは、第一の進行方向に関し、第二のセグメントは、３ポイントターン領域に関し、第三のセグメントは、第二の進行方向に関する。よって、ここでは、第一のセグメントは、サブセグメント１〜４を含み、第二のセグメントは、サブセグメント４及び５を含み、第三のセグメントは、サブセグメント５〜７を含む。

図７は、一つの実施形態による、自動運転車両（ＡＤＶ）の操作時に３ポイントターンを計画するための例示する方法６００を示すフローチャート図である。方法６００は、ハードウェア、ソフトウェア又はその組み合わせにより実現することができる。ブロック６１０においては、起点から終点を通り抜ける候補ルートを決定し、起点は、第一の進行方向に関する第一の車線内にあり、終点は、第二の進行方向に関する第二の車線内にあり、第二の進行方向と第一の進行方向は、逆である。ブロック６２０においては、候補ルートが部分的に重なる第一のセグメント、第二のセグメント及び第三のセグメントに分類され、第一のセグメントは、第一の進行方向に関し、第二のセグメントは、３ポイントターン領域に関し、第三のセグメントは、第二の進行方向に関する。ブロック６３０においては、少なくとも部分的に第一のセグメント及び第二のセグメントに基づいて候補ルートに関する総コストを推定する。ブロック６４０においては、総コストが閾値コストより低いか否かを判定する。ブロック６５０においては、総コストが閾値コストより低いと判定されたことに応答して、候補ルートに基づいて３ポイントターンを計画する。また、ブロック６６０においては、少なくとも部分的に計画された３ポイントターンに基づいてＡＤＶの操作を制御する運転信号を生成する。

前記文章で示され、説明された構成要素の中の幾つかまたは全部は、ソフトウェア、ハードウェアまたはその組み合わせとして実装することができる。例えば、この種類の構成要素は、永続的な記憶装置にインストールされ、かつ記憶されるソフトウェアとして実装することができる。当該ソフトウェアは、プロセッサ（図示せず）を通じてメモリにロードし、メモリの中で本願を貫いて説明したプロセスまたは操作を実行する。代替できるように、この種類の構成要素は、専用ハードウェア（例えば、集積回路（例えば、専用集積回路またはＡＳＩＣ）、デジタルシグナルプロセッサ（ＤＳＰ）または現場でプログラム可能なゲートアレイ（ＦＰＧＡ））にプログラムされたまたは埋め込まれた実行可能なコードとして実装することができる。当該実行可能なコードは、アプリケーションからの対応する駆動プログラム及び／またはオペレーティングシステムを通じてアクセスすることができる。さらに、この種類の構成要素は、ソフトウェアが一つまたは複数の特定の命令でアクセスできる命令集の一部分となるように、プロセッサまたはプロセッサのコアの中の特定のハードウェアロジックとして実装することができる。

図８は、本願の一つの実施形態と共に使用されるデータ処理システムの例示を示すブロック図である。例えば、システム１５００は、図１の感知・計画システム１１０またはサーバ１０３〜１０４の中の任意の一つのような、前記プロセスまたは方法を実装する任意の一つの任意のデータ処理システムを表すことができる。システム１５００は、多数の異なる構成要素を含むことができる。これらの構成要素は、集積回路（ＩＣ）、集積回路の一部分、独立な電子装置、または回路基板（例えば、コンピュータシステムのマザーボードまたはアドインカード）に用いられるその他のモジュールとして実装することができ、またはその他の方式でコンピュータシステムのシャーシに組み入れられる構成要素として実装することができる。

システム１５００の趣旨は、コンピュータシステムの複数の構成要素の高レベルの様子を示すことにあることに注意すべきである。幾つかの実施形態においては、付加的構成要素を有することができ、また、他の実施形態においては、図示する構成要素の異なる配置を有することができる。システム１５００は、デスクトップコンピュータ、ラップトップコンピューター、タブレットコンピュータ、サーバ、携帯電話、メディアプレーヤー、パーソナルデジタルアシスタント（ＰＤＡ）、スマートウォッチ、パーソナルコミュニケータ、ゲーム装置、ネットワークルーターまたはハブ、ワイヤレスアクセスポイント（ＡＰ）またはリピーター、セットトップボックスまたはこれらの組み合わせを表すことができる。さらに、シングルの機器またはシステムしか示されていないが、用語“機器”または“システム”は、本願で検討した任意の一つまたは複数の方法を実装するように、単独的にまたは共同的に一つ（または複数の）の命令集を実装する機器またはシステムの任意の集まりであると理解されるべきである。

一つの実施形態において、システム１５００は、バスまたはインターコネクト１５１０により連結されるプロセッサ１５０１、メモリ１５０３及び装置１５０５〜１５０８を含む。プロセッサ１５０１は、シングルのプロセッサコアまたは複数のプロセッサコアを含むシングルのプロセッサまたは複数のプロセッサを表すことができる。プロセッサ１５０１は、マイクロプロセッサ、中央処理装置（ＣＰＵ）等のような、一つまたは複数の汎用プロセッサを表すことができる。より具体的に、プロセッサ１５０１は、複合命令セットコンピューティング（ＣＩＳＣ）マイクロプロセッサ、縮小命令セットコンピューティング（ＲＩＳＣ）マイクロプロセッサ、超長命令語（ＶＬＩＷ）マイクロプロセッサ、またはその他の命令集を実装するプロセッサ、または命令集の組み合わせを実装するプロセッサであっても良い。プロセッサ１５０１は、専用集積回路（ＡＳＩＣ）、移動体またはベースバンドプロセッサ、現場でプログラム可能なゲートアレイ（ＦＰＧＡ））、デジタルシグナルプロセッサ（ＤＳＰ）、ネットワークプロセッサ、グラフィックスプロセッサ、通信プロセッサ、暗号化プロセッサ、コプロセッサ、組み込みプロセッサ、または命令を処理できる任意のその他のタイプのロジックのような、一つまたは複数の専用プロセッサであっても良い。

プロセッサ１５０１（低電力マルチコアプロセッサソケットであっても良く、例えば、超低電圧プロセッサ）は、前記システムの各種構成要素と通信する主プロセッサユニットと中央ハブとして振舞うことができる。この種類のプロセッサは、システムオンチップ（ＳｏＣ）として実装することができる。プロセッサ１５０１は、本願で議論した操作とプロセスを実装するための命令を実装するように配置される。システム１５００は、ディスプレイコントローラ、図形プロセッサ及び／またはディスプレイ装置を含む、候補の図形サブシステム１５０４と通信する図形インターフェースを更に含むことができる。

プロセッサ１５０１は、メモリ１５０３と通信することができる。一つの実施形態において、メモリ１５０３は、複数のメモリ装置によって規定の量のシステムメモリを提供するように実装されることができる。メモリ１５０３は、ランダムアクセスメモリ（ＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、スタティックＲＡＭ（ＳＲＡＭ）、またはその他のタイプのメモリ装置のような、一つまたは複数の揮発性ストレージ（またはメモリ）装置を含むことができる。メモリ１５０３は、プロセッサ１５０１またはその他の任意の装置によって実装する命令シーケンスを含む情報を記憶することができる。例えば、各種のオペレーティングシステム、デバイスドライバプログラム、ファームウェア（例えば、入出力基本システムまたはＢＩＯＳ）、および／またはアプリケーションの実装可能なコード及び／またはデータは、メモリ１５０３にロードされ、プロセッサ１５０１により実装されることができる。オペレーティングシステムは、任意のタイプのオペレーティングシステムであっても良く、例えば、ロボットオペレーティングシステム（ＲＯＳ）、Ｍｉｃｒｏｓｏｆｔ（登録商標）のＷｉｎｄｏｗｓ（登録商標）オペレーティングシステム、ＡｐｐｌｅのＭａｃＯＳ（登録商標）／ｉＯＳ（登録商標）、Ｇｏｏｇｌｅ（登録商標）のＡｎｄｒｏｉｄ（登録商標）、ＬＩＮＵＸ、ＵＮＩＸ、その他のリアルタイムまたは組み込みオペレーティングシステムであっても良い。

システム１５００は、ネットワークインターフェース装置１５０５、候補の入力装置１５０６、及びその他の候補のＩＯ装置１５０７を含む装置１５０５〜１５０８のようなＩＯ装置を更に含むことができる。ネットワークインターフェース装置１５０５は、無線トランシーバ及び／またはネットワークインターフェースカード（ＮＩＣ）を含むことができる。前記無線トランシーバは、ＷＩＦＩトランシーバ、赤外トランシーバ、ブルートゥーストランシーバ、ＷｉＭａｘトランシーバ、無線移動体電話トランシーバ、衛星トランシーバ（例えば、グローバル・ポジショニング・システム（ＧＰＳ）トランシーバ）、またはその他の無線周波数（ＲＦ）トランシーバまたはそれらの組み合わせであっても良い。ＮＩＣは、イーサネットカードであっても良い。

入力装置１５０６は、マウス、タッチパッド、タッチセンシティブ画面（表示装置１５０４と一体に集積されて）、ポインター装置（例えば、スタイラスペン）、および／またはキーボード（例えば、物理的キーボード、またはタッチセンシティブ画面の一部分として表示される仮想キーボード）を含むことができる。例えば、入力装置１５０６は、タッチパネルに接続するタッチパネルコントローラを含むことができる。タッチパネルとタッチパネルコントローラは、例えば、複数の種類のタッチセンシティブ技術（キャパシタンス、抵抗、赤外線および表面音波技術を含むが、これらに限定されない）を使用することができ、及び、その他の類似するセンサアレイまたはタッチパネルと接触する一つまたは複数の点を決めるために用いられるその他のデバイスを使用し、接触、移動または中断を検出することができる。

ＩＯ装置１５０７は、オーディオ装置を含むことができる。オーディオ装置は、音声識別、音声複製、デジタル記録及び／または電話機能等の音の機能のサポートを促進するために、スピーカー及び／またはマイクロホンを含むことができる。その他のＩＯ装置１５０７は、ユニバーサル・シリアル・バス（ＵＳＢ）ポート、パラレルポート、シリアルポート、プリンタ、ネットワークインターフェース、バスブリッジ（例えば、ＰＣＩ−ＰＣＩブリッジ）、センサ（例えば、加速度計運動センサ、ジャイロ、磁力計、光センサ、コンパス、近接センサ等）またはその組み合わせを更に含むことができる。装置１５０７は、画像処理サブシステム（例えば、カメラ）を更に含むことができる。当該画像処理サブシステムは、電荷結合素子（ＣＣＤ）または相補型金属酸化物半導体（ＣＭＯＳ）光センサのような、カメラ機能（例えば、写真やビデオクリップを記録する）を促進するために使用される光センサを含むことができる。幾つかのセンサは、センサハブ（図示せず）を経由してインターコネクト１５１０に接続しても良く、例えば、キーボードまたは熱センサのようなその他の装置は、システム１５００の具体的な配置または設計に従って埋め込み式コントローラ（図示せず）によってコントロールされても良い。

データ、アプリケーション、一つまたは複数のオペレーティングシステム等の情報に対する永続的な保存を提供するために、大容量記憶装置（図示せず）は、プロセッサ１５０１に接続しても良い。各種の実施形態において、より薄くより軽いシステム設計を実現し、システム応答性を改善するために、この種の大容量記憶装置は、ソリッドステートドライブ（ＳＳＤ）によって実装しても良い。しかし、その他の実施形態において、大容量記憶装置は、主にハードディスクドライブ（ＨＤＤ）を使用して実装し、それに加えて容量の比較的小さいＳＳＤ記憶装置をＳＳＤキャッシとして使用し、これによって電源が切られたイベントにおいて文脈状態及びその他のこの種類の情報の非揮発性保存を実現し、システムの活動が再び起動する時に素早い電源投入を実現する。なお、フラッシュメモリ装置は、例えば、シリアル・ペリフェラル・インタフェース（ＳＰＩ）を経由してプロセッサ１５０１に接続しても良い。この種類のフラッシュメモリ装置は、前記システムのＢＩＯＳ及びその他のファームウェアを含むシステムソフトウェアの非揮発性保存を提供することができる。

記憶装置１５０８は、本願で記述した一つまたは複数の方法または機能を具体的に表現する一つまたは複数の命令集またはソフトウェア（例えば、モジュール、ユニットまたはロジック１５２８）を記憶する、コンピュータのアクセス可能な記憶メディア１５０９（機器可読メディア又はコンピュータ可読メディアとも呼ばれる）を含むことができる。処理モジュール／ユニット／ロジック１５２８は、計画モジュール３０５、制御モジュール３０６及び／又は３ポイントターン計画モジュール３０８等のような、前記構成要素の中の任意の一つを表すことができる。処理モジュール／ユニット／ロジック１５２８は、データ処理システム１５００、メモリ１５０３とプロセッサ１５０１によって実装されている期間において、完全にまたは少なくとも部分的にメモリ１５０３及び／またはプロセッサ１５０１の中に駐留することができ、データ処理システム１５００、メモリ１５０３とプロセッサ１５０１もコンピュータのアクセス可能な記憶メディアを構成する。処理モジュール／ユニット／ロジック１５２８は、ネットワークを通じて、ネットワークインターフェース装置１５０５を経由して送信と受信を行うことができる。

コンピュータ可読メディア１５０９は、前記で説明した幾つかのソフトウェア機能を永続的に記憶するためにも使用される。コンピュータ可読メディア１５０９は、例示的な実施形態において、シングルのメディアとして示されているが、用語“コンピュータ可読メディア”は、前記一つまたは複数の命令集を記憶するシングルのメディアまたは複数のメディア（例えば、集中式または分布式データベース及び／または関連するキャッシュとサーバ）を含むと理解すべきである。用語“コンピュータ可読メディア”は、機器によって実装され、かつ本願の任意の一つまたは複数の方法を当該機器に実装させる命令集を、記憶するまたはエンコードすることができる任意のメディアを含むと理解すべきである。故に、用語“コンピュータ可読メディア”は、ソリッド・ステート・メモリ、光メディアと磁気メディア、または任意のその他の非一時的な機器可読メディアを含むが、これらに限定されないと理解すべきである。

本願で説明する処理モジュール／ユニット／ロジック１５２８、構成要素及びその他の特徴は、独立なハードウェア構成要素として実装しても良く、ハードウェア構成要素（例えば、ＡＳＩＣＳ、ＦＰＧＡ、ＤＳＰまたは類似の装置）の機能の中に集積しても良い。さらに、処理モジュール／ユニット／ロジック１５２８は、ハードウェア装置の中のファームウェアまたは機能回路として実装しても良い。なお、処理モジュール／ユニット／ロジック１５２８は、ハードウェア装置とソフトウェア構成要素との任意の組み合わせとして実装しても良い。

システム１５００は、データ処理システムの各種の構成要素を有するように示されているが、構成要素が互いに接続する任意の特定のアーキテクチャまたは方式を表すことではない。これは、この種類の細部は、本願の実施形態と密接な関係がないからである。より少ない構成要素又はより多い構成要素を有するネットワークコンピュータ、ハンドヘルドコンピュータ、携帯電話、サーバ、および／または他のデータ処理システムは、本願の実施形態と一緒に使用しても良いと認識すべきである。

前述の詳細な説明の中の一部分は、コンピュータメモリ内のデータビットに対する演算のアルゴリズムおよび記号表現に従って提示した。これらのアルゴリズム記述および表現は、データ処理領域の当業者が、仕事の本質を最も有効的に同じ領域の当業者に伝えるように、使用する方式である。本願において、アルゴリズムは、予期の結果をもたらす、自己矛盾のない操作のシーケンスであると一般的に認識される。これらの操作は、物理量に対して物理操縦を行う必要がある操作であることを指す。

これらのすべての用語と類似の用語は、適切な物理量と関連し、これらの量に応用されるのみの便宜上の標識であることをしっかりと覚えるべきである。以上の議論においてその他の方式で明確的に表明している時以外に、本願全体において、用語（例えば、付属の特許請求の範囲の中で説明する用語）を利用して行った討論は、コンピュータシステムまたは類似の電子計算装置の動作と処理を指す。前記コンピュータシステムまたは類似の電子計算装置は、コンピュータシステムのレジスターとメモリの中の、物理（電子）量として表されているデータを操縦し、前記データを、コンピュータシステムのメモリまたはレジスターまたはその他のこの種類の情報の記憶装置、転送またはディスプレイ装置の中の、類似的に物理量として表されているその他のデータへ変換する。

本願の実施形態は、本願文章の中の操作を実装するために用いられる設備にも関わる。この種のコンピュータプログラムは、非一時的なコンピュータ可読メディアの中に記憶される。機器可読メディアは、機器（例えば、コンピュータ）可読形式で情報を記憶する任意の機構を含む。例えば、機器可読（例えば、コンピュータ可読）メディアは、機器（例えば、コンピュータ）可読記憶メディア（例えば、リードオンリーメモリ（“ＲＯＭ”）、ランダムアクセスメモリ（“ＲＡＭ”）、磁気ディスク記憶メディア、光記憶メティア、フラッシュメモリ装置）を含む。

前記図面の中で説明されたプロセスまたは方法は、ハードウェア（例えば、回路、専用ロジックなど）、ソフトウェア（例えば、非一時性コンピュータ読み取りメディアに具現して）またはその組み合わせを含む処理ロジックによって実装しても良い。前記プロセスまたは方法は、上記の文章において幾つかの順序操作によって説明されているが、前記操作の中の幾つかは、異なる順序で実装しても良いと理解すべきである。さらに、幾つかの操作は、順序で実装されるのではなく、並列的に実装されても良い。

本願の実施形態は、何らかの特定のプログラミング言語を参考にして説明されているのではない。説明した本願の実施形態の教えは、複数のプログラミング言語を使って実装することができると認識すべきである。

以上の明細書において、本願の具体的で例示性のある実施形態を参考にして、本願の実施形態に対して説明を行った。添付する特許の請求範囲の中で論述した本願のより広範な精神と範囲を逸脱しない限り、本発明に対して各種の修正をすることができる。故に、制限性の意味ではなく、説明性の意味で本明細書と図面を理解すべきである。
なお、出願当初の特許請求の範囲の記載は以下の通りである。
請求項１：
自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画するコンピュータ実施の方法であって、
第一の進行方向に関する第一の車線内にある起点から、前記第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
前記候補ルートを、前記第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び前記第二の進行方向に関する第三のセグメントに分類することと、
少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて前記候補ルートに関する総コストを推定することと、
前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、前記ＡＤＶを前記３ポイントターンを行うように運転することと
を備える、コンピュータ実施の方法。
請求項２：
前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを含み、
前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項１に記載の方法。
請求項３：
前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項１に記載の方法。
請求項４：
前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項３に記載の方法。
請求項５：
前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項３に記載の方法。
請求項６：
前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時、計画された３ポイントターンを完成させることを更に備える、請求項１に記載の方法。
請求項７：
計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項６に記載の方法。
請求項８：
命令を記憶している非一時性機器可読メディアであって、
前記命令がプロセッサにより実行されると、前記プロセッサに、自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画する操作を実行させ、
前記操作は、
第一の進行方向に関する第一の車線内にある起点から、第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
前記候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、
少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて候補ルートに関する総コストを推定することと、
前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、ＡＤＶを３ポイントターンを行うように運転することと
を備える、非一時性機器可読メディア。
請求項９：
前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを含み、
前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項８に記載の機器可読メディア。
請求項１０：
前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項８に記載の機器可読メディア。
請求項１１：
前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項１０に記載の機器可読メディア。
請求項１２：
前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項１０に記載の機器可読メディア。
請求項１３：
前記操作は、前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時は、計画された３ポイントターンを完成させることを更に備える、請求項８に記載の機器可読メディア。
請求項１４：
前記操作は、計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項１３に記載の機器可読メディア。
請求項１５：
プロセッサと、前記プロセッサに接続され、命令を記憶するメモリとを含むデータ処理システムであって、
前記命令がプロセッサによって実行されると、前記プロセッサに、自動運転車両ＡＤＶの操作において３ポイントターンを計画する操作を実行させ、
前記操作は、
第一の進行方向に関する第一の車線内にある起点から、前記第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
前記候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、
少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて候補ルートに関する総コストを推定することと、
前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、ＡＤＶを３ポイントターンを行うように運転することと
を備える、データ処理システム。
請求項１６：
前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを備え、前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項１５に記載のデータ処理システム。
請求項１７：
前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項１５に記載のデータ処理システム。
請求項１８：
前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項１７に記載のデータ処理システム。
請求項１９：
前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項１７に記載のデータ処理システム。
請求項２０：
前記操作は、前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時は、計画された３ポイントターンを完成させることを更に備える、請求項１５に記載のデータ処理システム。
請求項２１：
前記操作は、計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項２０に記載のデータ処理システム。

Claims (22)

1. 自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画するコンピュータ実施の方法であって、
   第一の進行方向に関する第一の車線内にある起点から、前記第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
   前記候補ルートを、前記第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び前記第二の進行方向に関する第三のセグメントに分類することと、
   少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて前記候補ルートに関する総コストを推定することと、
   前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、前記ＡＤＶが前記３ポイントターンを行うように運転することと
   を備え、
   前記閾値コストは、前記総コストが前記閾値コストより低い場合、３ポイントターンを行うための十分なスペースがあり、且つ障害物と衝突することはないコストである、コンピュータ実施の方法。
2. 前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを含み、
   前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項１に記載の方法。
3. 前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項１に記載の方法。
4. 前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項３に記載の方法。
5. 前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項３に記載の方法。
6. 前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時、計画された３ポイントターンを完成させることを更に備える、請求項１に記載の方法。
7. 計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項６に記載の方法。
8. 命令を記憶している非一時性機器可読メディアであって、
   前記命令がプロセッサにより実行されると、前記プロセッサに、自動運転車両（ＡＤＶ）の操作において３ポイントターンを計画する操作を実行させ、
   前記操作は、
   第一の進行方向に関する第一の車線内にある起点から、第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
   前記候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、
   少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて候補ルートに関する総コストを推定することと、
   前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、ＡＤＶが３ポイントターンを行うように運転することと
   を備え、
   前記閾値コストは、前記総コストが前記閾値コストより低い場合、３ポイントターンを行うための十分なスペースがあり、且つ障害物と衝突することはないコストである、非一時性機器可読メディア。
9. 前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを含み、
   前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項８に記載の機器可読メディア。
10. 前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項８に記載の機器可読メディア。
11. 前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項１０に記載の機器可読メディア。
12. 前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項１０に記載の機器可読メディア。
13. 前記操作は、前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時は、計画された３ポイントターンを完成させることを更に備える、請求項８に記載の機器可読メディア。
14. 前記操作は、計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項１３に記載の機器可読メディア。
15. プロセッサと、前記プロセッサに接続され、命令を記憶するメモリとを含むデータ処理システムであって、
    前記命令がプロセッサによって実行されると、前記プロセッサに、自動運転車両ＡＤＶの操作において３ポイントターンを計画する操作を実行させ、
    前記操作は、
    第一の進行方向に関する第一の車線内にある起点から、前記第一の進行方向と逆である第二の進行方向に関する第二の車線内にある終点までの候補ルートを決定することと、
    前記候補ルートを、第一の進行方向に関する第一のセグメント、３ポイントターン領域に関する第二のセグメント及び第二の進行方向に関する第三のセグメントに分類することと、
    少なくとも部分的に前記第一のセグメント及び前記第二のセグメントに基づいて候補ルートに関する総コストを推定することと、
    前記総コストが閾値コストより低いと判定されたことに応答して、前記候補ルートに基づいて前記３ポイントターンを計画して、ＡＤＶが３ポイントターンを行うように運転することと
    を備え、
    前記閾値コストは、前記総コストが前記閾値コストより低い場合、３ポイントターンを行うための十分なスペースがあり、且つ障害物と衝突することはないコストである、データ処理システム。
16. 前記候補ルートを決定することは、地図データに対してＡ−Ｓｔａｒ探索を行うことを備え、前記第一の進行方向及び前記第二の進行方向のそれぞれに関する前記第一の車線及び前記第二の車線の双方は、何れも探索可能及び接続可能であると見なされる、請求項１５に記載のデータ処理システム。
17. 前記総コストは、少なくとも障害物コスト及び残り車線長さコストを含む、請求項１５に記載のデータ処理システム。
18. 前記障害物コストは、少なくとも部分的に前記ＡＤＶと前記候補ルートの付近の１つ又は複数の障害物の中のそれぞれの障害物との間の距離に基づいて推定される、請求項１７に記載のデータ処理システム。
19. 前記残り車線長さコストは、少なくとも部分的に前記第一のセグメントの長さに基づいて推定される、請求項１７に記載のデータ処理システム。
20. 前記操作は、前記ＡＤＶの進行方向と参考進行方向との差が進行方向差の閾値より小さい時は、計画された３ポイントターンを完成させることを更に備える、請求項１５に記載のデータ処理システム。
21. 前記操作は、計画された３ポイントターンを完成させた後、前記ＡＤＶの操作を通常操作のモードに切り替えることを更に備える、請求項２０に記載のデータ処理システム。
22. プロセッサにより実行されると、請求項１〜７のいずれか一項に記載の方法を実現させるコンピュータプログラム。

Images