(57)【特許請求の範囲】
【請求項１】
複数の通過点を含む経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定する方法であって、
当該方法は、複数のモジュールを含む少なくとも１つの処理装置を用いて行われ、
ａ）前経路モジュールによって、複数の通過点を含む前経路を受け取るステップと、
ｂ）前記前経路モジュールによって、前記前経路から前記経路を生成するステップであって、前記前経路の複数の通過点から精密なまたは細かい通過点のサンプリングを生成して前記経路の複数の通過点を作成するステップを含むステップと、
ｃ）許容可能速度モジュールによって、前記前経路モジュールから受け取った前記経路の許容可能速度プロフィールを決定するステップであって、前記許容可能速度プロフィールが前記複数の通過点の各々に関する許容可能な速度を有しており、前記複数の通過点の各々に関する前記許容可能な速度が前記経路における通過点の道路曲率の評価によって決定される進路横断加速度制約条件を満たすステップと、
ｄ）最適速度モジュールによって、前記経路の最適速度プロフィールを決定するステップであって、前記最適速度プロフィールが前記複数の通過点の各々に関する最適な速度を有しており、前記複数の通過点の各々に関する最適な速度が進路沿い加速度制約条件及び速度制約条件の両方を満たしており、前記速度制約条件が望ましい速度と前記許容可能な速度とのうちの最小値であるステップと、を含み、
前記最適速度プロフィールを決定するステップは、
前記複数の通過点を第１方向に掃引して進路沿い加速度プロフィールを決定するステップであって、前記進路沿い加速度プロフィールは、負の加速度制約条件を満たすステップと、
前記複数の通過点を第２方向に掃引して前記進路沿い加速度プロフィールを更新するステップであって、更新された進路沿い加速度プロフィールは、負の加速度制約条件及び正の加速度制約条件の両方を満たすステップと、を含む、方法。
【請求項２】
請求項１に記載の方法であって、前記経路は、空間索引付きである、方法。
【請求項３】
請求項１に記載の方法であって、前記複数の通過点の各々の望ましい速度は、運転制限速度である、方法。
【請求項４】
請求項１に記載の方法であって、前記許容可能速度プロフィールは、前記経路の近似的な経路曲率を用いて決定される、方法。
【請求項５】
請求項１に記載の方法であって、さらに、最適移動時間決定モジュールによって、前記最適速度プロフィールに基づいて、前記経路の最適移動時間を決定するステップを含む、方法。
【請求項６】
請求項１に記載の方法であって、さらに、快適性決定モジュールによって、前記経路の周波数応答に基づいて前記経路の快適性レベルを決定するステップを含む、方法。
【請求項７】
請求項６に記載の方法であって、前記経路の周波数応答は、前記最適速度プロフィールに基づいている、方法。
【請求項８】
請求項１に記載の方法であって、前記最適速度プロフィールは、前記経路と同時に決定される、方法。
【請求項９】
経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定するシステムであって、前記システムは、複数のモジュールを有し、請求項１に記載の方法を行う少なくとも１つの処理装置を含み、前記経路は、複数の通過点を含み、前記複数の通過点の各々は、望ましい速度を含む、システム。
【請求項１０】
複数の通過点を含む経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定する方法であって、
当該方法は、複数のモジュールを含む少なくとも１つの処理装置を用いて行われ、
ａ）許容可能速度モジュールによって、前記経路の許容可能速度プロフィールを決定するステップであって、前記許容可能速度プロフィールが前記複数の通過点の各々に関する許容可能な速度を有しており、前記複数の通過点の各々に関する前記許容可能な速度が前記経路における通過点の道路曲率の評価によって決定される進路横断加速度制約条件を満たすステップと、
ｂ）最適速度モジュールによって、前記経路の最適速度プロフィールを決定するステップであって、前記最適速度プロフィールが前記複数の通過点の各々に関する最適な速度を有しており、前記複数の通過点の各々に関する最適な速度が進路沿い加速度制約条件及び速度制約条件の両方を満たしており、前記速度制約条件が望ましい速度と前記許容可能な速度とのうちの最小値であるステップと、
ｃ）周波数応答決定モジュールによって、前記最適速度プロフィールの進路沿い加速度プロフィール及び前記最適速度プロフィールの進路横断加速度プロフィールの各々の周波数応答を決定するステップと、
ｄ）快適性判定モジュールによって、前記加速度プロフィールが、およそ０．１５ヘルツから０．２５ヘルツの間の周波数を含むかを判定して、前記最適速度プロフィールに従って前記経路を通過する快適性レベルを判定するステップと、
ｅ）経路生成モジュールによって、複数の潜在的な下位経路から前記経路を生成するステップであって、前記潜在的な下位経路の各々は、前記周波数応答に基づいて不利な評価に置かれ、前記周波数応答は、１）前記潜在的な下位経路の最適速度プロフィールの進路沿い加速度プロフィール、及び、２）前記潜在的な下位経路の最適速度プロフィールの進路横断加速度プロフィールのうち１つの周波数応答である、ステップと、を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は地上ベースのルート計画立案に関する。具体的には、本願は、地上ベースのルート計画立案システムにより決定される経路の移動時間及び快適性レベルに対する道路曲率の影響を評価するための方法及びシステムに関する。しかし、ここに開示される主題は他の同様の用途及び環境の一方または両方に対して同等に順応可能であることを理解されるべきである。
【背景技術】
【０００２】
マップクエスト（ＭａｐＱｕｅｓｔ）(商標)など従来の地上ベースのルート計画立案システム及び方法の一方または両方は一般に、２点間の最短または最速経路を与えようとするものである。その際、そのようなシステムは、２点を結ぶ道路の公示された速度制限に大きく依存しており、運転者は公示された速度制限近辺で経路を通過するものと仮定している。しかし、この仮定は誤りである。すなわち、曲がり角または湾曲した道に近づくと、一般に減速が必要なので、ある道路の公示された速度制限が時速８０．５ｋｍ／ｈ（５０ＭＰＨ）であっても、利用者が安全に移動できるのはせいぜい３２．２ｋｍ／ｈ（２０ＭＰＨ）である。結果として、減速して曲がり角またはカーブを通過した後は、速度制限まで再加速する必要があり、余分な時間がかかる。したがって、道路の曲率を考慮しないと経路通過に必要な時間の概算が不正確となることがあり、そのため経路通過のための見積時間の計算に経路の曲率を入れるシステム及び方法の一方または両方があると有利である。公示された速度制限の仮定に影響を及ぼすもう１つの要因は、速度制約条件または予想速度制約条件を付与することがある停止標識及び停止信号の存在であることに言及すべきである。
【０００３】
地上ベースのルート計画立案システム及び方法の一方または両方には、職業的運転者から記録されたデータを用いて経路に沿った予想通過時間の精度を向上させるものがある。しかし、そのような精度向上は、運転者の好みに特有のものであり、また交通条件に依存している。さらに、そのような精度向上は、運転者が経路に沿ったあらゆる道路を通過する必要がある点で労働集中的であり、費用もかさむ。したがって、運転者の好み及び特定の交通条件に対して独断的でなく、かつ運転者がある経路で利用可能なすべての道路を通過する必要がないシステム及び方法の一方または両方があると有利である。
【０００４】
通過の速度にかかわらず、従来の地上ベースのルート計画立案システム及び方法の一方または両方は一般的に、地上ベースのルート計画立案システムの利用者が経路通過中に経験する快適性レベルに関係する考慮を行なうことができない。その代わり、そのようなシステムは２点間の最短または最速経路に焦点を合わせている。しかし、多くの利用者が経路通過中に快適性及び安全性レベル向上のため、数分の付加的な移動時間または数キロ（数マイル）の余分な移動を費やそうとすることは自明であろう。よって、利用者が経路通過中に経験する快適性レベル及び安全性の考慮を行なう地上ベースのルート計画立案システム及び方法の一方または両方があれば有利である。
【０００５】
幹線道路の利用の奨励の利点により、運転者の快適性を考慮可能な地上ベースのルート計画立案システムもあるが、それらは経路通過中における利用者の快適性レベルに直接影響するある特定の考慮、すなわち経路の曲率の考慮を行なうことができない。すなわち、ＮＡＳＡの研究により、特定の周波数での加速により車酔いのリスクが増大することが分かっている。一般に、これらの周波数はおよそ０．２ヘルツである。道路の曲率の変化は進路横断及び進路沿いの両方で車両の加速度に直接影響を与えるので、道路の曲率が個人の快適性レベルに影響を与えることがある。その上、カーブの多い道路はそのような道路の通過に必要な注意が増大することにより、運転に関する課題を高めるので、道路の曲率は乗り物酔いにかかわらず個人の快適性レベルに影響を与える場合がある。反面、個人によっては、カーブの多い道路を通過することによる運転者の意識及び娯楽の増大により、直線道路よりカーブの多い道路の方が快適であると感じることがある。したがって、少なくとも上記の理由により、道路の曲率は利用者の快適性レベルに影響を与えるので、経路を決定しながら道路の曲率を考慮することと、発生可能性がある潜在的な不快を利用者に知らせることとの一方または両方を行うシステム及び方法の一方または両方があると有利である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本願は上記問題などを克服する新規かつ改良されたシステム及び方法の一方または両方を考えたものである。
【課題を解決するための手段】
【０００７】
本発明に係る道路曲率評価方法は、複数の通過点を含む経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定する方法であって、当該方法は、複数のモジュールを含む少なくとも１つの処理装置を用いて行われ、
ａ）前経路モジュールによって、複数の通過点を含む前経路を受け取るステップと、
ｂ）前記前経路モジュールによって、前記前経路から前記経路を生成するステップであって、前記前経路の複数の通過点から精密なまたは細かい通過点のサンプリングを生成して前記経路の複数の通過点を作成するステップを含むステップと、
ｃ）許容可能速度モジュールによって、前記前経路モジュールから受け取った前記経路の許容可能速度プロフィールを決定するステップであって、前記許容可能速度プロフィールが前記複数の通過点の各々に関する許容可能な速度を有しており、前記複数の通過点の各々に関する前記許容可能な速度が前記経路における通過点の道路曲率の評価によって決定される進路横断加速度制約条件を満たすステップと、
ｄ）最適速度モジュールによって、前記経路の最適速度プロフィールを決定するステップであって、前記最適速度プロフィールが前記複数の通過点の各々に関する最適な速度を有しており、前記複数の通過点の各々に関する最適な速度が進路沿い加速度制約条件及び速度制約条件の両方を満たしており、前記速度制約条件が望ましい速度と前記許容可能な速度とのうちの最小値であるステップと、を含み、
前記最適速度プロフィールを決定するステップは、
前記複数の通過点を第１方向に掃引して進路沿い加速度プロフィールを決定するステップであって、前記進路沿い加速度プロフィールは、負の加速度制約条件を満たすステップと、
前記複数の通過点を第２方向に掃引して前記進路沿い加速度プロフィールを更新するステップであって、更新された進路沿い加速度プロフィールは、負の加速度制約条件及び正の加速度制約条件の両方を満たすステップと、を含む、方法である。
【０００８】
本発明に係る道路曲率評価システムは、経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定するシステムであって、前記システムは、複数のモジュールを有し、本発明に係る道路曲率評価方法を行う少なくとも１つの処理装置を含み、前記経路は、複数の通過点を含み、前記複数の通過点の各々は、望ましい速度を含む、システムである。
本発明に係る別の道路曲率評価方法は、複数の通過点を含む経路の道路曲率の評価を用いて経路の最適速度プロフィールを決定する方法であって、当該方法は、複数のモジュールを含む少なくとも１つの処理装置を用いて行われ、
ａ）許容可能速度モジュールによって、前記経路の許容可能速度プロフィールを決定するステップであって、前記許容可能速度プロフィールが前記複数の通過点の各々に関する許容可能な速度を有しており、前記複数の通過点の各々に関する前記許容可能な速度が前記経路における通過点の道路曲率の評価によって決定される進路横断加速度制約条件を満たすステップと、
ｂ）最適速度モジュールによって、前記経路の最適速度プロフィールを決定するステップであって、前記最適速度プロフィールが前記複数の通過点の各々に関する最適な速度を有しており、前記複数の通過点の各々に関する最適な速度が進路沿い加速度制約条件及び速度制約条件の両方を満たしており、前記速度制約条件が望ましい速度と前記許容可能な速度とのうちの最小値であるステップと、
ｃ）周波数応答決定モジュールによって、前記最適速度プロフィールの進路沿い加速度プロフィール及び前記最適速度プロフィールの進路横断加速度プロフィールの各々の周波数応答を決定するステップと、
ｄ）快適性判定モジュールによって、前記加速度プロフィールが、およそ０．１５ヘルツから０．２５ヘルツの間の周波数を含むかを判定して、前記最適速度プロフィールに従って前記経路を通過する快適性レベルを判定するステップと、
ｅ）経路生成モジュールによって、複数の潜在的な下位経路から前記経路を生成するステップであって、前記潜在的な下位経路の各々は、前記周波数応答に基づいて不利な評価に置かれ、前記周波数応答は、１）前記潜在的な下位経路の最適速度プロフィールの進路沿い加速度プロフィール、及び、２）前記潜在的な下位経路の最適速度プロフィールの進路横断加速度プロフィールのうち１つの周波数応答である、ステップと、を含む、方法である。
【図面の簡単な説明】
【００１０】
【図１】経路の道路曲率を評価するための例示的方法である。
【図２】ある経路の図式的な説明である。
【図３】ある通過点の曲率半径の決定を示す、図２の経路の一部分の図式的な説明である。
【図４】図２における経路通過に際して与えられる速度制約条件の図式的説明である。
【図５】図２のグラフの最適速度プロフィールの図式的説明である。
【図６】経路の曲率を評価するための例示的システムである。
【図７】経路の道路曲率を評価するための例示的方法を用いた例示的な道路曲率評価部である。
【図８】２点間の最短経路を発見するための２つの例示的アルゴリズムに従って生成された経路の図式的な説明である。
【図９】２点間の最短経路を発見するための２つの例示的アルゴリズムに従って生成された経路の図式的な説明である。
【図１０】図８に示す第１の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１１】図８に示す第１の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１２】図８に示す第１の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１３】図８に示す第１の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１４】図９に示す第２の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１５】図９に示す第２の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１６】図９に示す第２の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【図１７】図９に示す第２の例示的アルゴリズムに従って生成された経路に対し本願の例示的方法を実行した結果の図式的な説明である。
【発明を実施するための形態】
【００１１】
本願のある態様によれば、経路の道路曲率を評価するための方法及びシステムが開示される。この経路は複数の通過点を含む。経路の許容可能速度プロフィールが決定される。許容可能速度プロフィールは複数の通過点の各々に関する許容可能な速度を含んでいる。複数の通過点の各々に関する許容可能な速度は進路横断加速度制約条件を満たす。経路の最適速度プロフィールも決定される。最適速度プロフィールは複数の通過点の各々に関する最適な速度を含んでいる。複数の通過点の各々に関する最適な速度は進路沿い加速度制約条件及び速度制約条件の両方を満たす。速度制約条件は望ましい速度及び許容可能な速度のうちの最小値である。
【００１２】
経路の道路曲率を評価する例示的方法は、地上ベースのルート計画立案システムにより生成される経路を前提としている。地上ベースのルート計画立案システムとは、マップクエスト（商標）、トムトム（ＴｏｍＴｏｍ）（商標）及び他の同様のサービスなどの電子的サービスを指すものである。さらに、地上ベースのルート計画立案システムとは、ウェブサイト（例えばマップクエスト（商標））、携帯ＧＰＳ装置（例えばトムトム（商標））、または他の同様の変形例を指すこともある。
【００１３】
一般に、地上ベースのルート計画立案システムは、地上ベースのルート計画立案システムの利用者により入力される開始アドレスと終点アドレスとの間の経路を生成する。当然、そのような用途では通常、生成された経路を用いて運転方向及び運転時間の一方または両方が生成され、生成された経路が道路、幹線道路、高速道路、及び他の同様の地上ベースの経路をたどるようになっている。よって、生成される経路は個々の道路、幹線道路等に対応する複数の経路（または下位経路）からなってもよい。しかし理解されるように、本願は、地上ベースのルート計画立案システムの利用者が例えば開始座標及び終点座標を入力する「オフロード」の経路生成またはその変形例に対しても同等に対応可能である。
【００１４】
地上ベースのルート計画立案システムの用途にかかわらず、一般に経路は２点間の最速かつ最短、または最速もしくは最短の経路を指すものである。当業者が理解するように、経路の前述の種類に対する変形例も本願にとって同等に対応可能である。この経路は、可視グラフを伴うＡ＊、勾配降下法による高速前進（ｆａｓｔ  ｍａｒｃｈｉｎｇ）、または２点間の経路を生成するように動作する他のいかなるアルゴリズムを用いて生成してもよい。しかし、本願のある実施形態では、低時間計算量アルゴリズムが用いられる。経路はさらに複数の通過点を含んでおり、それら通過点は、地上ベースのルート計画立案システムにより生成された経路に沿った点に相当している。
【００１５】
これを考慮し、図１に示すような例示的方法を説明する。この例示的方法は、例えばマップクエスト(商標)により生成された経路の曲率を評価して、この経路の移動時間及び経路の快適性レベルの一方または両方を決定しようとするものである。この例示的方法の説明では、図１のステップを適宜、図２〜５と併せて説明する。より明白となるように、図２〜５の各点はある通過点に対応している。図２はある経路の図式的な説明である。図３は、ある通過点の曲率半径の決定を示す、図２の経路の一部分の図式的な説明である。図４は、図２における経路通過に際して与えられる速度制約条件の図式的説明である。図５は、図２のグラフの最適速度プロフィールの図式的説明である。
【００１６】
図１を参照すると、経路の道路曲率を評価する例示的方法が開示されている。この方法は、前経路から経路を生成するステップ（選択的ステップ１０２）と、許容可能速度プロフィールを決定するステップ（ステップ１０４）と、最適速度プロフィールを決定するステップ（ステップ１０６）とを含む。この方法はさらに、最適速度プロフィールの最適移動時間を決定するステップ（ステップ１０８）と、快適性レベルを決定するステップ（ステップ１１０）とを含む。最適速度プロフィールを決定するステップ（ステップ１０６）は、速度制約条件を決定するステップ（ステップ１１２）と、負の加速度制約条件を満たす速度プロフィールを決定するステップ（ステップ１１４）と、正の加速度制約条件を満たすよう速度プロフィールを更新するステップ（ステップ１１６）とを含む。快適性レベルを決定するステップ（ステップ１１０）は、経路の周波数応答を決定するステップ（ステップ１１８）を含む。
【００１７】
選択的であろうとも、第１のステップは、前経路から経路を生成する（ステップ１０２）。前経路は地上ベースのルート計画立案システムにより与えられる経路である。このステップは、前経路よりも精密なまたは細かい通過点のサンプリングを生成することを必要としており、より精密なまたは細かい通過点のサンプリングは、数値的に推定可能な曲率を有する空間索引付き経路ｗ∈ＲNx2を定義するようになっている。Ｎは通過点の数である。上記のように、前経路は時間索引付きまたは空間索引付きのいずれかであってよい。前経路が時間索引付きの場合、空間索引付き経路に変換される。さらに、理解されるように、通過点のサンプルが精密なまたは細かいほど、例示的方法により、道路曲率をより正確に評価できるようになる。しかし、より精密なまたは細かい通過点のサンプリングは一般により好ましいが、計算時間の増大という代償が生じてしまう。したがって、前経路の離散化の量は、計算時間と正確さとの競合する利害を考慮して選択しなければならない。
【００１８】
通過点の空間索引付き経路を仮定すると、次のステップは、その経路に関する許容可能速度プロフィールを決定することである（ステップ１０４）。このステップは、近似的な経路曲率を用いて、進路横断加速度制約条件ａmaxを満たす通過点ｗi＝（ｘi，ｙi）ごとの最大許容速度ｖi,allowを計算することを課する。理解されるように、進路横断加速度制約条件ａmaxは、快適性、車両の性能、道路条件、及び他の同様の考慮事項の１以上を含むがそれらに限定されない多数の考慮事項に依存している。通過点ｗiにおける進路横断加速度ａct,iは、速度ｖi及び曲率半径ｒiの関数である。
【数１】
0005476252.tif 000002
進路横断加速度の大きさをａmaxより小さく制約する場合、ｗiにおける最大許容速度はｖi,allowである。
【数２】
0005476252.tif 000003
【００１９】
曲率半径ｒiを決定するため、通過点ｗi-1、ｗi及びｗi+1を用いて、それら通過点を通る円が定義される。この円は曲率半径ｒｉを有すると仮定されるが、理解されるように、これは通過点がそれらの曲率に対して精密なまたは細かい間隔を有する場合に有効な仮定だからである。通過点ｗi-1及びｗiは第１ラインを定義し、通過点ｗi及びｗi+1は第２ラインを定義する。第１ライン及び第２ラインの中点を通る垂線の交点が円の中心である。交点を解くと中心点ｃi＝（ｘic，ｙic）が得られる。
【数３】
0005476252.tif 000004
【数４】
0005476252.tif 000005
【数５】
0005476252.tif 000006
曲率半径が無限大の場合、分母ｄiの値はいかなる直線線分に対してもゼロとなるので、分母ｄiを事前に計算すべきである。そうでない場合、中心点は上記の式を用いて計算可能である。曲率半径ｒiは、ｗiと中心ｃiとを結ぶベクトルのノルムである。カーブの方向は、有限の曲率半径ｒiに対して第１及び第２の線分のクロス乗積の符号を用いて計算可能である。
【００２０】
図２及び３を参照すると、通過点ｗiに関して曲率半径ｒiをどのように決定するかの一例が図式的に示されている。図２を参照すると、ある経路のグラフが示されており、この経路は複数の通過点を含んでいる。このグラフはｘ軸とｙ軸とを含んでおり、グラフ上の各点はある通過点に対応している。このグラフは３つの通過点ｗi-1、ｗi及びｗi+1を囲む破線のボックスをさらに示している。これら３つの通過点を用いて、通過点ｗiの曲率半径ｒiがどのように決定されるかを説明する。
【００２１】
図３を参照すると、図２内で囲まれている３つの通過点ｗi-1、ｗi及びｗi+1が示されている。第１のステップは、図２に示すように、通過点ｗi-1及びｗiの間の第１ライン３０２と、通過点ｗi及びｗi+1の間の第２ライン３０４とを決定することである。その後、第１垂線３０６と第２垂線３０８との交点を決定する。この交点は、通過点ｗi-1、ｗi及びｗi+1を通る円の中心ｃiに相当している。第１垂線３０６は第１ライン３０２に対し垂直であり、第１ライン３０２の中点を通っている。第２垂線３０８は第２ライン３０４に対し垂直であり、第２ライン３０４の中点を通っている。曲率半径ｒiは、単純に円の中心ｃiと通過点ｗiとの間に延びる線の長さ（またはノルム）である。
【００２２】
ある通過点ｗiの曲率半径ｒiが決定されると、通過点ｗiにおいて進路横断加速度制約条件ａmaxにより与えられる最大許容速度ｖi,allowの決定が可能になる。理解されるように、このステップは、各通過点ｗiごとに許容可能速度プロフィールを決定するように繰り返される。
【００２３】
図１に戻ると、ある経路の許容可能速度プロフィールが決定（ステップ１０４）された後、その経路の最適速度プロフィールが決定される（ステップ１０６）。このステップは、以前のステップからの望ましい速度及び許容可能速度のうちの最小値とともに、それぞれの部分での線形の進路沿い加速度制約条件を満たす最適速度プロフィールを決定することを課する。このステップは、速度制約条件を決定するサブステップ（ステップ１１２）と、負の進路沿い加速度制約条件を満たす速度プロフィールを決定するサブステップ（ステップ１１４）と、正の進路沿い加速度制約条件を満たすよう速度プロフィールを更新するサブステップ（ステップ１１６）とを含む。
【００２４】
速度制約条件の決定（ステップ１１２）に関し、通過点ごとの速度は、望ましい速度ｖi,maxと進路横断加速度制約条件ｖi,allowに関して与えられる制約条件との両方により制約される。前経路は好ましくは望ましい速度を定義するものである。ある特定の通過点に関する望ましい速度は、例えばその通過点に対応する道路に沿った速度制限であってもよい。代替的に、望ましい速度は車両の最高速度など、経路を通過する車両の性能に依存していてもよい。望ましい速度がどのように選択されるかにかかわらず、これら２つの制約条件の最小値は満たされなければならず、各通過点において許容される最高速度
【数６】
0005476252.tif 000007
は以下に示すように定義される。
【数７】
0005476252.tif 000008
【００２５】
図４を参照すると、上述の様々な速度プロフィールが示されており、各通過点は図２の経路に沿った速度及び位置に応じて図示されている。グラフに示すように、許容速度は、進路横断加速度制約条件に応じた許容速度（すなわちステップ１０４）に対応している。望ましい速度は上述のような望ましい速度に対応している。この場合、各通過点ごとの望ましい速度は説明に役立つ目的のため任意に選択した。最後に、最大速度（すなわち速度制約条件）は望ましい速度及び許容速度のうちの最小値に相当している。
【００２６】
図１に戻ると、速度制約条件が決定（ステップ１１２）された後、負の進路沿い加速度制約条件を満たす速度プロフィールがまず決定される（ステップ１１４）。その後、ステップ１１４からの速度プロフィールは正の進路沿い加速度制約条件を満たすように更新される（ステップ１１６）。しかし、明らかなように、これらのステップは３つの式、すなわち複数の通過点間の時間Δｔ、次の通過点における速度ｖi+1、及び進路沿い加速度ａat,iに依存している。さらに、これらのステップはアルゴリズム１に依存している。よって、アルゴリズム１及びこれらの式を以下に示す。
【００２７】
上記参照の式に関して、通過点ｗi及びｗi+1の間の区分的線形進路沿い加速度ａat,iを考慮する。現在速度ｖi及び複数の通過点間の時間Δｔが与えられると、次の通過点における速度ｖi+1は以下の通りである。
【数８】
0005476252.tif 000009
通過点ｗiの進路沿い位置を経路、すなわち、
【数９】
0005476252.tif 000010
の始点から計測したｓiとする。
【数１０】
0005476252.tif 000011
である。
通過点間の時間Δｔを決定するため、通過点間の時間Δｔに対して次の通過点における速度ｖi+1に関する前の式を積分することにより、以下の式が得られる。
【数１１】
0005476252.tif 000012
通過点間の時間Δｔを解くと、以下の式が得られる。速度は正でなければならないので、通過点間の時間Δｔに関する上記式において正の平方根のみが物理的解釈を有することに留意すべきである。
【数１２】
0005476252.tif 000013
次の通過点における速度ｖi+1に対応する上記式に、通過点間の時間Δｔに関する式を代入すると、次の通過点における速度ｖi+1に関する以下の式が得られる。
【数１３】
0005476252.tif 000014
与えられた距離に対する与えられた速度変化を実現するため加速度に関して解くと、以下が得られる。
【数１４】
0005476252.tif 000015
【００２８】
アルゴリズム１、掃引アルゴリズム、に関して、アルゴリズム１は通過点を通ってインクリメントすることにより動作する。通過点ｗiにおいて、ｗi及びｗi+1の間で加速することが可能かどうかをまず決定する。加速可能な場合、必要な限り速くに加速し、ａmaxで飽和する。加速できない場合、
【数１５】
0005476252.tif 000016
を満たすように減速する必要があるかどうかを次に確認する。それが必要な場合、たとえａat、i＜−ａmaxを用いることが必要であっても、必要な加速度を用いてその速度まで減速する。減速はａmaxに反するのみであることに留意すべきである。減速が必要でない場合、現在の速度が保持される。最後に、計算された速度プロフィールｖ、加速度プロフィールａ、及び時間プロフィールΔｔを返す。アルゴリズムは空間索引付きなのでΔｔを計算しなければならないことに留意すべきである。理解されるように、このアルゴリズムはＯ（Ｎ）時間（Ｎは通過点の数）で動作する。
［アルゴリズム１］(速度−計画−掃引（ｖ0、ｓ、ｖ、ａmax））
【数１６】
0005476252.tif 000017
【００２９】
上記の背景を考慮して、次のステップは、負の進路沿い加速度制約条件を満たす加速度プロフィールを決定するものである（ステップ１１４）。このステップは、上記に示したアルゴリズム１を用いて通過点の逆掃引を行なうことにより達成される。初めに、すべての進路沿い位置をｓに記憶し、すべての最大速度を
【数１７】
0005476252.tif 000018
に記憶する。理解されるように、最大速度はステップ１１２で決定される（すなわち速度制約条件）。その後、終点から始点までの点を通る掃引を準備するため、これらの配列ｓ及び
【数１８】
0005476252.tif 000019
を時間的に反転させ、ｓを否定する。アルゴリズム１への入力が準備されると、
【数１９】
0005476252.tif 000020
の反転したデータに対してアルゴリズム１を走らせ、速度プロフィール及び、ａi＞−ａmax∀ｉを満たす対応する進路沿い加速度プロフィールａを生成する。理解されるように、その結果、速度プロフィールは負の進路沿い加速度制約条件−ａmaxを満たす。
【００３０】
負の進路沿い加速度制約条件を満たす速度プロフィールが決定された（ステップ１１４）後に、アルゴリズム１を用いて、さらに正の進路沿い加速度制約条件を満たすよう速度プロフィールが更新される（ステップ１１６）。これは、通過点の順方向掃引を用いて達成される。最初に、速度制約条件
【数２０】
0005476252.tif 000021
を、ステップ１１４（すなわち逆掃引）の結果としてのｖに設定する。その後、始点から終点までの点を通る掃引を準備するため、配列ｓ及び
【数２１】
0005476252.tif 000022
を時間的に再び反転させ、ｓを再び否定する。アルゴリズム１への入力が準備されると、
【数２２】
0005476252.tif 000023
の順方向データに対してアルゴリズム１を走らせ、以前のステップからの速度プロフィール及び対応する進路沿い加速度プロフィールを更新し、ａi＜ａmax∀ｉとなる。さらに、この掃引においては、上記の逆掃引によって与えられる速度制限により、ａi＜−ａmax∀ｉは不可能である。
【００３１】
これら逆方向及び順方向の掃引が完了すると、その結果、速度プロフィールはステップ１１２からの速度制約条件とともに、負の進路沿い加速度制約条件及び正の進路沿い加速度制約条件の両方を満たすことになる。言い換えれば、最適速度プロフィールが生成されている。さらに、理解されるように、速度プロフィールの生成プロセスにおいては、対応する加速度プロフィール及び対応する時間プロフィールが生成される。さらに、負の進路沿い加速度制約条件−ａmaxは正の進路沿い加速度制約条件ａmaxの否定として示されているが、それらは対称的である必要はないことを理解されるべきである。
【００３２】
図５を参照すると、図２のグラフの掃引２の後の速度プロフィール（すなわち最適速度プロフィール）の図式的説明が示されている。図５はさらに、掃引１の後の速度プロフィールとステップ１１２からの速度制約条件とを含んでいる。速度制約条件は第１の掃引に関する速度の上限を課すものであり、第１掃引の速度プロフィール内の速度が、望ましい速度及び進路横断加速度制約条件を超えないようになっている。第１の掃引後の速度プロフィールは、第２の掃引に関する速度の上限を課すものであり、第２掃引の速度プロフィール内の速度が、望ましい速度、進路横断加速度制約条件及び負の進路沿い加速度制約条件を超えないようになっている。これにより、理解されるように、掃引１の速度プロフィール内の速度は、速度制約プロフィール内の速度を超えることがなく、掃引２の速度プロフィール内の速度は、掃引１の速度プロフィール内の速度を超えることがない。掃引１の後の速度プロフィールは、速度が速度制約条件を満たすまでの右から左への加速を示している。掃引２の後の速度プロフィールは、速度が第１掃引からの速度プロフィールを満たすまで左から右へ加速する。
【００３３】
最適速度プロフィールが決定（ステップ１０４）された後、本方法は２つの選択的ステップの一方または両方に従って進行してもよい。第１の選択は、経路の通過に関する最適移動時間ｔを決定することである（ステップ１０８）。理解されるように、これは通過点間の時間Δｔを合計するのと同等に単純である。
【数２３】
0005476252.tif 000024
従来の近似は道路の曲率と、対応するカーブ及び曲がり角の一方または両方での減速の必要とを考慮していないので、最適移動時間ｔを用いると、従来の近似よりも経路通過に必要な時間のはるかに良好な近似が得られる。
【００３４】
本願の別の態様に移ると、経路の快適性レベルの決定（ステップ１１０）を可能にする選択肢が開示される。このステップは、経路の周波数応答を決定するサブステップ（ステップ１１８）を含んでいる。経路の周波数応答を決定するため、２つの方法のうち一方を採用してもよい。その第１は、ある経路に関する実時間運転データを収集することである。明らかなように、このような方法では、経路を物理的または物質的に通過して経路の周波数応答に関するデータを収集することが必要である。代替的に、かつ好ましくは、周波数応答は最適速度プロフィールと、対応する進路横断加速度プロフィール及び進路沿い加速度プロフィールの一方または両方とから決定される。この方式を用いて、加速度プロフィールは、空間索引付きとは対照的な時間索引付きとなるように変換される。その後、周波数応答を得るため、有限インパルス応答、フーリエ変換などのデジタルフィルタリング法が、関連する加速度プロフィールに対し実行される。
【００３５】
周波数応答により、周波数応答が乗り物酔いを起こしやすい周波数を含んでいるかどうかを判定してもよい。上記のように、ＮＡＳＡの研究により、乗り物酔いを起こしやすいそれらの周波数の詳細を記載した表（以下の表１を参照）が発表されている。特に、表１には加速度（重力単位）に対する周波数（ヘルツ単位）がプロットされている。生成された曲線（２５パーセント、５０パーセント、７５パーセント）は、垂直の正弦波運動にさらされた５００人の男性被験者について２時間以内に嘔吐を生じた割合にもとづく乗り物酔いの等高線を表わしている。明らかなように、乗り物酔いの顕著な増加は、およそ０．２０ヘルツをピークとしておよそ０．１５ヘルツから０．２５ヘルツの間で生じている。この判定にもとづき、経路通過者が経験する快適性レベルの近似を導くことができる。その上、または代替例において、周波数応答がより高い周波数を含んでいるかどうかにもとづいて快適性レベルを導くことができる。当然、現われる周波数が高いほど、ある経路に沿った道路のカーブ及び曲がり角の一方または両方が多く、それら道路を通過するにはより多くの努力が必要となる。したがって、快適性レベルは、より高い周波数にもとづくものとすることができる。表１のデータは模範的に引用される乗り物酔いの例である。しかし、他の研究は様々なレベルを定義しているかもしれない。よって、上記は単なる一例であり、本概念は他のそのような研究からのデータを用いて実現してよいものと理解すべきである。自動車タイヤは代表的に、大多数の利用者の快適性レベルの範囲内で０．３ｇまで対処可能であることにも言及しておく。
【００３６】
決定された快適性レベルに応じて、快適性レベルが所定のしきい値を下回っているかどうかを利用者に知らせてもよい。ある実施形態では、このしきい値は利用者により設定されるが、他の実施形態では、しきい値はすべての利用者に対して包括的に設定される。代替的に、ある利用者が経路を観察した後に経路の快適性レベルを要求してもよい。さらに別の代替例では、経路の快適性レベルが所定のしきい値を下回った場合に新規の経路が自動的に生成される。さらに別の代替例では、経路を生成する間に、下位経路（例えば道路）の周波数応答及び移動時間を用いてこの下位経路を不利に評価してもよい。例えば、地上ベースのルート計画立案システムは、カーブの多い道路の２分延伸は移動時間の３０分節約のために許容可能であるが、カーブの多い道路の３０分延伸は移動時間の３０分節約のために許容不可能であることを見出してもよい。このようにして、経路の周波数応答を有利に用いて、経路を通過する利用者の快適性が改善される。
【表１】
0005476252.tif 000025
【００３７】
別の例示的実施形態によれば、上記で論じた例示的方法は、地上ベースのルート計画立案システムのデータベースを解析及び増強するように変形される。ある実施形態によれば、上記で論じた例示的方法を用いて、地上ベースのルート計画立案システムのデータベースを構成する経路（例えば道路）の速度プロフィール、加速度プロフィール、時間プロフィール、周波数応答及び運転者の快適性の１以上を事前に計算してもよい。その後、地上ベースのルート計画立案システムは、増強されたデータベースを用いて２点（例えば開始アドレスと終点アドレス）間の経路を決定し、事前計算されたデータ、例えば周波数応答により下位経路（例えば道路）を不利な評価に置くことができる。これにより、地上ベースのルート計画立案システムが、２点間の経路を例えば、より正確な移動時間、下位経路（例えば道路）の周波数応答、及び運転者の快適性にもとづくように生成しながら、道路の曲率を有利に考慮することができる。さらに、理解されるように、前述のデータを事前計算することにより、地上ベースのルート計画立案システムにより用いられる経路生成アルゴリズムの時間及び領域計算量に対する影響を無視しうるものとすべきである。ある代替的実施形態では、２点間の経路を生成しながら（すなわち実行時に）地上ベースのルート計画立案システムのデータベースが増強される。さらに別の代替的実施形態では、２点間の経路を生成しながら（すなわち実行時に）２点間の経路の中間かつそれに関連する下位経路（例えば道路）に関する速度プロフィール、加速度プロフィール、時間プロフィール、周波数応答及び運転者の快適性の１以上が生成される。
【００３８】
図６を参照すると、上記の開示したような経路の曲率を評価するための例示的システム６００が示されている。このシステムは１人以上の利用者６０２と、地上ベースのルート計画立案システム６０４と、自動車６１４とを含んでいる。地上ベースのルート計画立案システムはインタフェース６０６と、経路生成部６０８と、制御部６１０と、道路曲率評価部６１２とを備えている。
【００３９】
インタフェース６０６は１人以上の利用者６０２とインタフェース接続され、１人以上の利用者６０２からの要求を受け取る。インタフェース６０６はマップクエスト（商標）などのウェブインタフェースであってもよい。代替的に、インタフェース６０６は、トムトム（商標）のような携帯ＧＰＳ装置のコンピュータインタフェースなどのコンピュータインタフェースであってもよい。要求は、運転方向、ある経路の快適性レベル、ある経路の移動時間に関する要求、及び他の同様の要求の１以上であってもよい。ある要求が運転方向に関するものである場合、その要求は始点と終点とを含んでいてもよい。その要求が、ある経路の快適性レベル及び移動時間の一方または両方に関するものである場合、その要求は経路または経路の位置を含んでいてもよい。経路生成部６０８は、経路要求、例えば運転方向に関する要求に応答して経路を生成する。経路生成部６０８は、可視グラフを伴うＡ＊、勾配降下法による高速前進、または２点間の経路を生成するように動作する他のいかなるアルゴリズムを用いて経路を生成してもよい。道路曲率評価部６１２は、評価要求に応答して以下図７で説明するように経路の曲率を評価する。
【００４０】
制御部６１０は、地上ベースのルート計画立案システム６０４の構成要素間の通信をブリッジ及びリレーの一方または両方を行うように作用する。制御部６１０は、インタフェース６０６を介して１人以上の利用者から要求を受け取る。その後、制御部６１０は、要求にどのように応答するかを決定し、要求を適切にリレーする。制御部６１０が運転方向に関する要求（すなわち経路要求）を受け取ると、制御部６１０は、要求を経路生成部６０８へリレーし、生成された経路をインタフェース６０６を介して適切な利用者に返す。制御部６１０が、ある経路の移動時間またはある経路の快適性レベルに関する要求（すなわち評価要求）を受け取ると、次のステップは、要求で受け取った情報に依存したものになる。要求がある経路を含む場合、制御部６１０は、要求を道路曲率評価部６１２へ単純にリレーし、インタフェース６０６を介して、道路曲率評価部６１２の評価により要求に応答する。しかし、要求が、運転方向に関する要求（すなわち経路要求）も含む場合、制御部６１０は、まず要求を経路生成のため経路生成部６０８へ送信する。その後、制御部は、その経路を経路生成部６０８から道路曲率評価部６１２へリレーし、その経路及び道路曲率評価部６１２の評価により要求に応答する。
【００４１】
地上ベースのルート計画立案システム６０４はさらに自動車６１４を伴っていてもよい。自動車６１４は現在位置表示器６１６及び速度調整器６１８の一方または両方を備えている。現在位置表示器６１６は、地上ベースのルート計画立案システム６０４の制御部６１０に、地上ベースのルート計画立案システムにより生成された経路に沿った自動車６１４の現在位置を与えてもよい。現在位置表示器６１６はＧＰＳ装置及び地上ベースのナビゲーションのための他のいかなるシステムの一方または両方であってもよい。経路に沿った自動車６１４の現在位置により、制御部６１０はその経路の最適速度プロフィールを用いて自動車６１４の速度調整器６１８を制御することができる。速度調整器６１８は例えばクルーズコントロールを備えていてもよい。これにより自動車６１４は、クルーズコントロールなどの速度調整器６１８を用いる際に、曲がり角に関して有利に減速することができる。代替的に、制御部６１０は、利用者が与えるパラメータまたは事前にプログラムされたパラメータにもとづき制御部６１０が運転者に速度制限を課す「一方的クルーズコントロール」を備えてもよい。例えば、そのようなパラメータは、運転者の、道路状態に対してあまりに高速でカーブに進入する能力を制限するものでもよい。理解されるように、これにより安全性が有利に向上する。別の実施形態によれば、制御部６１０は減速のための聴覚的な及び視覚的な一方または両方の警告を運転者に与えることができる。これによっても安全性が有利に向上する。前述の論議は前述の特徴を調和させた制御部を考慮しているが、制御部は単にある経路に関する速度プロフィールを自動車６１４に与えるものであってもよく、それにより自動車６１４は速度調整器６１８の制御など前述の特徴のうち１以上を実行してもよい。
【００４２】
図７を参照すると、経路の曲率を評価するための代替的実施形態のシステム７００が示されている。システム７００はコンピュータ７１０、またはマイクロプロセッサ、マイクロコントローラ、図形処理装置（ＧＰＵ）等のデジタルプロセッサと記憶装置とを含む他のデジタル処理装置に適切に組み込まれている。他の実施形態では、道路曲率を評価するためのシステム７００は、デジタルプロセッサを備えるとともにデジタルデータ記憶装置にアクセスするサーバにより実現してもよく、そのようなサーバはインターネットまたはローカルエリアネットワークを経由して適切にアクセスされるものであり、もしくはデジタルプロセッサ及びデジタルデータ記憶装置などを備える携帯情報端末（ＰＤＡ）により実現してもよい。コンピュータまたは他のデジタル処理装置は、利用者の入力を受け取って道路曲率評価部を制御するための図示されたキーボード７１４等の１以上のユーザ入力装置を適切に備えるか、またはこれに動作可能に接続されており、さらに、道路曲率評価システム７００の出力にもとづいて生成された出力を表示するための図示されたディスプレイ７１２などの１以上の表示装置を備えるか、またはこれに動作可能に接続されている。他の実施形態では、道路曲率評価システム７００を制御するための入力は、コンピュータ７１０上の道路曲率評価システム７００より以前またはそれと同時に走る別のプログラム、またはネットワーク接続などから受信される。同様に、他の実施形態では、上記出力がコンピュータ上のシステム７００の後またはそれと同時に走る別のプログラムに対する入力として作用してもよく、または上記出力をネットワーク接続を介して伝送するなどしてもよい。
【００４３】
道路曲率評価システム７００は、選択的な前経路モジュール７０２と、許容可能速度モジュール７０４と、最適速度モジュール７０６と、利用者モジュール７０８とを備える。使用時、選択的前経路モジュール７０２は、外部供給源（例えばインターネット）から道路曲率評価システム７００への前経路を受け取り、図１のステップ１０２に関連して説明したような前経路から経路を生成する。その後、許容可能速度モジュール７０４が前経路モジュール７０２から経路を受け取る。選択的前経路モジュール７０２が用いられない場合、許容可能速度モジュール７０４は外部供給源（例えばインターネット）から道路曲率評価システム７００への経路を受け取り、許容可能速度プロフィールを生成する。許容可能速度プロフィールは、好ましくは図１のステップ１０４に関連して説明したように生成される。最適速度モジュール７０６は、許容可能速度モジュール７０４から経路及び許容可能速度プロフィールを受け取る。その後、最適速度モジュール７０６は、受け取った経路及び許容可能速度プロフィールを用いて、加速度制約条件及び速度制約条件を満たす最適速度プロフィールを生成する。最適速度モジュールは、図１のステップ１０６に関連して説明したように最適速度プロフィールを生成する。その後、最適速度プロフィールは表示、プリントアウト、及びプランナなどの付加的決定機構へのインプリメンテーションの１以上のため出力される。代替的に、最適速度プロフィールが生成された後、利用者モジュール７０８は最適速度モジュールから最適速度プロフィール及び対応する加速度プロフィールを受け取る。加えて、利用者モジュール７０８は最適移動時間、快適性レベル、または他の同様の要求のうち１以上に関する外部の要求を受け取る。要求に応じて、利用者モジュール７０８は図１のステップ１０８及び１１０に関連して論じたように速度プロフィール及び加速度プロフィールの一方または両方を解析する。その後、要求に対する応答が表示、プリントアウト、及びプランナなどの付加的決定機構へのインプリメンテーションの１以上のため出力される。
【００４４】
実施形態によっては、本願の上述した例示的方法、これを用いた道路曲率評価部などは、例示的方法及び道路曲率評価部の一方または両方を実現するため（例えばデジタルプロセッサにより）実行可能な命令を記憶する記憶媒体により実現される。この記憶媒体は、例えば磁気ディスクまたは他の磁気的記憶媒体、光学ディスクまたは他の光学的記憶媒体、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、または他の電子的メモリ装置またはチップもしくは動作可能に相互接続されたチップの組、記憶された命令をインターネットまたはローカルエリアネットワークを経由して検索可能なインターネットサーバなどを含んでもよい。
【００４５】
図８から１７を参照すると、上述の時間最適掃引アルゴリズムの実験による試験結果が示されている。時間最適掃引アルゴリズムを２つの例示的経路探索アルゴリズム、Ａ＊アルゴリズム及び高速前進アルゴリズムに適用した。さらに、すべての実験は３．４ＧＨｚペンティアム（登録商標）（Ｐｅｎｔｉｕｍ（登録商標））ＩＶコンピュータを用いて実施した。以下より詳細に論じるように、時間最適掃引アルゴリズムを実行するための時間は、そのＯ（ｎ）時間計算量から予想されるように、このアルゴリズムが計算上無視しうることを示している。
【００４６】
図８に示す可視グラフによる最短経路発見のためＡ＊を用いて生成された経路を考慮すると、最短経路の生成にはＭａｔｌａｂを用いて２０ｍｓ未満が必要であった。しかし、この方法は、急な曲がり角において自動車の減速停止が必要となる動的制約条件を無視するものであった。最適時間掃引アルゴリズムを実行するため、最短経路を０．２ｍのインクリメントで離散化した結果、最適時間掃引を実行するための計算時間は１ｍｓ未満であった。これらの結果を図１０から１３に示す。加速度及び速度の制約条件の下で経路を通過するための最小時間は１３．６秒であった。
【００４７】
本方式の１つの欠点は、離散化の精密さまたは細かさによっては曲がり角が省略される可能性があるという、多くの経路探索アルゴリズムに共通する問題である。しかし、掃引アルゴリズムの実行時間が短いと仮定した場合、十分に精密なまたは細かい離散化を選択するための計算上の費用は低く、任意の正確さを用いて障害を回避してもよい。空間離散化の精度を向上させる影響は、基礎的な望ましい経路内の曲がり角ごとに速度がゼロまで低下するので、コースを完了するための合計時間が増大するということである。問題の定式化によっては、当初の計画の生成において用いられる障害の定義に十分な余裕がある場合、曲がり角を省略することが望ましい。これにより、経路内の急な曲がり角を停止せずに通過することができるが、これは可視グラフの場合のように経路内に急な曲がり角がある場合にのみ有利である。
【００４８】
図９に示す平面波近似による高速前進を用いて生成された経路を考慮すると、離散格子を用いたこの方法は、距離とともに増大する目標から外側への目標到達費用を増大させる。障害への近接はこの費用を増大させ、その結果、表面周囲における波面の屈折が生じる。この結果としての費用マップを用いると、勾配降下法を用いて目的までの最良経路が費用マップに従って見出される。図示の例では、完全な経路発見アルゴリズムが再び２０ｍｓ未満で動作する。障害に対する嫌忌により、障害に近接していることにより自動車がペナルティを与えられるので、この費用マップは目標までの正確な時間とならない。最適時間掃引アルゴリズムを実行するため、高速前進経路を再び０．２ｍのインクリメントで離散化した結果、計算時間は１ｍｓ未満であった。
【００４９】
これらの結果を図１４から１７に示す。加速度及び速度の制約条件の下で経路を通過するための最小時間は１３．８秒であった。高速前進の結果は、可視グラフのものとは異なる。障害に対する嫌忌の結果、経路はより円滑となるが、常に可視グラフより長くなる。その結果、可視グラフの方が高速となることもあり、高速前進経路の方が高速となることもある。障害に対する嫌忌により、高速前進は可能な場合、小さな間隙の通過を回避しようとするが、これは、くねった曲がり角がある場合に有利であるものの、単純な間隙が存する場合には性能が低下する。その結果としての高速前進経路に関する最小時間加速度指令は、曲がり角の欠如により可視グラフよりはるかに円滑に変化した。進路横断加速度による最大速度制約条件は可視グラフ経路より長い時間有効であったが、最小値は平均速度が上記２つの例に関して同等に近づくほど低くはならなかった。
【００５０】
両方の例において、動的制約条件は経路発見のため最初無視され、次に最適時間掃引アルゴリズムに内包されたので、上記環境により経路を発見するための計算時間は短時間であった。自動車の動力学と経路計画とを別個に考慮することにより、全体の経路は最適とならなかった。しかしすでに良好な経路を仮定すれば、最適時間掃引アルゴリズムは制御入力と、経路を最小時間で通過する速度計画とを生成する。
【符号の説明】
【００５１】
６００  システム、６０２  利用者、６０４  地上ベースのルート計画立案システム、６０６  インタフェース、６０８  経路生成部、６１０  制御部、６１２  道路曲率評価部、６１４  自動車、６１６  現在位置表示器、６１８  速度調整器、７００  システム、７０２  前経路モジュール、７０４  許容可能速度モジュール、７０６  最適速度モジュール、７０８  利用者モジュール、７１０  コンピュータ、７１２  ディスプレイ、７１４  キーボード。
【図１】
0005476252.tif 000026
【図２】
0005476252.tif 000027
【図３】
0005476252.tif 000028
【図４】
0005476252.tif 000029
【図５】
0005476252.tif 000030
【図６】
0005476252.tif 000031
【図７】
0005476252.tif 000032
【図８】
0005476252.tif 000033
【図９】
0005476252.tif 000034
【図１０】
0005476252.tif 000035
【図１１】
0005476252.tif 000036
【図１２】
0005476252.tif 000037
【図１３】
0005476252.tif 000038
【図１４】
0005476252.tif 000039
【図１５】
0005476252.tif 000040
【図１６】
0005476252.tif 000041
【図１７】
0005476252.tif 000042