(57)【特許請求の範囲】
【請求項１】
ルート計算用の位置に使用し、複数のハイウエイデータが記憶されているデータベース媒体中の、ハイウエイアクセスランプを識別する方法において、
（ａ）ハイウエイに属し、且つそのハイウエイに連結された少なくとも１つのハイウエイアクセスランプを備え、前記ハイウエイに対応し、そのハイウエイ方向とハイウエイ上の位置によって特徴付られている第１の道路セグメントをデータベース媒体において識別し、
（ｂ）前記第１の道路セグメントが属するハイウエイに従って、前記第１の道路セグメントを分類し、
（ｃ）前記各第１の道路セグメントについてそのハイウエイ方向を決定し、
（ｄ）前記第１の道路セグメントが対応するハイウエイ方向に従って、前記ハイウエイの前記第１の道路セグメントの各々を分類し、
（ｅ）前記ハイウエイにおける各道路セグメントの位置に従って、前記ハイウエイ別及び各ハイウエイ方向別に、前記第１の道路セグメントを並べ換え、これによって、前記ハイウエイの各方向についてのハイウエイセグメントリストを形成し、
（ｆ）前記ハイウエイセグメントリスト中の前記第１の道路セグメント毎に連結する少なくとも１つのハイウエイアクセスランプを識別し、
（ｇ）前ステップ（ｆ）において識別された各ハイウエイアクセスランプについてのランプデータを補助的なデータベースとして、データベース媒体中に記憶し、それによって前記ハイウエイアクセスランプがルート計算のための位置として利用されるように操作可能となるようにし、
（ｈ）データベース媒体中の各ハイウエイについてステップ（ｄ）〜（ｇ）を反復することを特徴とする方法。
【請求項２】
前記第１の道路セグメントを識別するステップが、
（ｉ）データベース媒体中の複数の道路セグメントから１つの候補となる道路セグメントを選択し、
（ｊ）前記候補となる道路セグメントと関連する制限速度が制限速度閾値を超え、前記候補となる道路セグメントが、番号が付されたハイウエイの一部であり且つ前記候補となる道路セグメントがハイウエイアクセスランプではないときに、前記候補となる道路セグメントを前記第１の道路セグメントとして指定し、
（ｋ）データベース媒体中の各道路セグメントについてステップ（ｉ）及び（ｊ）を反復する請求項１に記載の方法。
【請求項３】
各第１の道路セグメントについてのハイウエイ方向を決定するステップが、データベース媒体中の第１の道路セグメントと関連するハイウエイの名称または記号の末尾部分を調べて決定することからなる請求項１に記載の方法。
【請求項４】
各第１の道路セグメントについてのハイウエイ方向を決定するステップが、データベース媒体中の第１の道路セグメントと関連するハイウエイ標識の表記を調べて決定することからなる請求項１に記載の方法。
【請求項５】
各第１の道路セグメントについてのハイウエイ方向を決定するステップが、データベース媒体中の第１の道路セグメントに連絡された前記第１の道路とは別の第２の道路セグメントと関連するハイウエイの名称または記号の末尾部分を調べて決定することからなる請求項１に記載の方法。
【請求項６】
各第１の道路セグメントについてのハイウエイ方向を決定するステップが、データベース媒体中の第１の道路セグメントに連絡された第２の道路セグメントと関連するハイウエイ標識の表記を調べて決定することからなる請求項１に記載の方法。
【請求項７】
各第１の道路セグメントについてのハイウエイ方向を決定するステップが、第１のハイウエイの方向に偶数番号を割り当て且つ第２のハイウエイの方向に奇数番号を割り当てることからなる請求項１に記載の方法。
【請求項８】
ハイウエイアクセスランプを識別するステップが、
（ｉ）ハイウエイセグメントリストから１つの道路セグメントを選択し、
（ｊ）前記１つの道路セグメントに連結されている１組のハイウエイアクセスランプを決定し、これによりランプリストを生成し、
（ｋ）前記ランプリストから第１のハイウエイアクセスランプを選択し、
（ｌ）前記第１のハイウエイアクセスランプが連結されている少なくとも１つの道路を識別し、
（ｍ）識別された少なくとも１つの道路に従って前記第１のハイウエイアクセスランプを指定し、
（ｎ）ランプリスト中の各ハイウエイアクセスランプについてステップ（ｋ）〜（ｍ）を反復することからなる請求項１に記載の方法。
【請求項９】
第１のハイウエイアクセスランプを、ランプ入口又はランプ出口として識別するステップを更に有する請求項８に記載の方法。
【請求項１０】
第１のハイウエイアクセスランプを識別するステップが、データベース媒体中の第１のハイウエイアクセスランプと関連するハイウエイ標識の表記を調べて決定することからなる請求項９に記載の方法。
【請求項１１】
ランプデータが各ハイウエイアクセスランプについての少なくとも１つの街路名からなり該少なくとも１つの街路名は、対応するハイウエイアクセスランプが連結される少なくとも１つの街路に一致する請求項１に記載の方法。
【請求項１２】
ランプデータが、各ハイウエイアクセスランプについての地理的地域名と、共通のハイウエイ上の連続するハイウエイアクセスランプ間の距離とを更に有している請求項１１に記載の方法。
【請求項１３】
特定のハイウエイアクセスランプについてのランプデータを記憶するステップは、特定のハイウエイアクセスランプが、第１の道路から第２のハイウエイへのアクセスを与える２つのハイウエイアクセスランプのうちの１つであるときに、特定のハイウエイアクセスランプの代わりに目的地として使用される特定のハイウエイアクセスランプに連結される別のハイウエイセグメントを記憶することからなる請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は車両ナビゲーションシステムに関し、より詳しくは、車両ナビゲーションシステムを用いてルート（道筋）の計算を行なうための位置として、ハイウェイアクセスランプを識別する方法を提供する。また、本発明は、車両ナビゲーションシステムを用いて、ハイウェイアクセスランプの位置に基づくルートを決定する方法及び装置を提供する。
【０００２】
【従来の技術】
今日の車両ナビゲーションシステムに用いられているマップデータベースでは、種々の形式の地理的領域に対してさまざまな詳しさで与えられている。一般に、都市地域及び郊外地域を有する大都会領域は、高レベルの明細を有し且つデータベースに記憶される大量の詳細マップ情報を保有する。これに対し、大都会間を結ぶ人口の少ない領域にある田園地域及び田舎町についてはほとんど詳しくは、示されていない。本願では、これらの領域をハイウェイ領域と呼ぶ。本願における「ハイウェイ」なる用語は、後述の幾つかの基準に合致する道路を含み、とりわけ、ハイウェイ、フリーウェイ及びエクスプレスウェイをいうのに使用される。
【０００３】
車両ナビゲーションシステムを使用するとき、一般にユーザは目的地を選択し、これによりナビゲーションシステムはルートを計算して目的地までのガイド情報を与える。例えば、ユーザが都市地域の特定交差点まで走行したい場合には、マップデータベースにより与えられる交差点を選択する。利用できるマップデータベースにより与えられる都市地域については、一般に、全てではないにせよ殆どの交差点情報をユーザが利用できる程度の詳しさである。しかしながら、マップデータベースはハイウェイ領域の細部をカバーするものではないので、これらの領域における多くの目的地はルート計算に利用されていない。
【０００４】
一般に、ハイウェイ領域についての利用できるマップデータベースにより与えられる詳しさは、ハイウェイ自体及び該ハイウェイに接続される主要道路を含んでいる。一般に、より詳細な街路情報は与えられない。かくして、ハイウェイ領域においてユーザが最も近づきたい目的地は、通常、ルート計算の目的に利用できない。従って、車両ナビゲーションシステムのユーザに、ハイウェイ領域での目的地オプションを提供する必要がある。ハイウェイアクセスポイント（すなわちランプ入口及びランプ出口）は可能性ある目的地オプションであるが、利用可能なマップデータベースは、このようなアクセスポイントをアクセスポイントとして識別し且つ目的地オプションとしてユーザに提供できるフォームで、このようなアクセスポイントに関する情報を与えるものではない。
【０００５】
ルート計算及びガイダンスにハイウェイアクセスポイントを利用できると、ユーザが、例えばハイウェイへの最短の入口を見出したい場合に有効であろう。この目的のためにハイウェイアクセスポイントを利用できることが有効な他の場合は、ユーザがハイウェイ領域の目的地及び／又は都市地域内でのユーザの現在位置に近い街路に精通している場合である。このような場合にユーザに必要とされることは、充分なルートガイダンスを受けるべくハイウェイ領域の目的地近くのハイウェイ出口を特定することだけである。
【０００６】
【発明が解決しようとする課題】
以上から、ナビゲーションシステムのユーザに、ルート計算及びガイダンスを目的とする目的地オプションとしてハイウェイアクセスポイントを提供する必要があることは明白であり、本発明はこの必要性を満たすものである。
【０００７】
【課題を解決するための手段】
本発明は、車両ナビゲーションシステムでのルート計算の目的のため、ハイウェイアクセスポイントの位置のリストが優先的にコンパイルされる方法を提供する。本発明は、慣用的なマップデータベースで開始する。本発明の方法は、関心のあるハイウェイ及び該ハイウェイに関連するアクセスポイント（例えば、ランプ入口、ランプ出口及び交差点等）を識別するものである。次に、アクセスランプは、ハイウェイへのアクセスが行なえる道路又はハイウェイからアクセスできる道路により識別される。次に、アクセスランプの位置が補助データベースに記憶され、ルート計算に使用される。車両ナビゲーションシステムのユーザは、例えば走行したいハイウェイのランプ入口を知ると、システムにより与えられるオプションから、目的地としてのランプ入口を選択できる。次にシステムは、このランプ入口についての補助データベースに記憶された位置に基づいて、ランプ入口までの少なくとも１つのルートを計算する。
【０００８】
本発明によれば、ルート計算用の位置設定に使用するデータベース媒体中のハイウエイアクセスランプを識別する方法が提供される。最初に、ハイウエイに属し且つ少なくとも１つのハイウエイアクセスランプに連結された第１の道路セグメントが識別される。第１の道路セグメントは、これらが属するハイウエイに従って分類される。各第１の道路セグメントについてハイウエイ方向が決定される。第１のハイウエイに属する道路セグメントがハイウエイ方向に従って分類される。位置に従って、第１のハイウエイに属する各ハイウエイ方向の第１の道路セグメントが分類され、これにより第１のハイウエイの各方向についてハイウエイセグメントリストが形成される。ハイウエイセグメントリスト中の各第１の道路セグメントについて、ハイウエイアクセスランプが識別される。ハイウエイアクセスランプの位置はデータベース媒体中に記憶される。ハイウエイアクセスランプは、このようにして、データベース媒体中の各ハイウエイについて識別される。
【０００９】
出発する車両の位置から目的地までのルートを、車両ナビゲーションシステムを用いて決定する方法及び装置も提供される。この装置は、複数のハイウエイアクセスランプの位置が記憶されたデータベース媒体を有する。ユーザは、ユーザインターフェースを用いて、第１のハイウエイ及び第１のハイウエイアクセスランプを目的地として選択できる。データベース媒体及びユーザインターフェースには、多数の機能を遂行できるプロセッサが接続されている。このプロセッサは、目的地としてユーザによる第１のアクセスランプの選択に応答して、データベース媒体からの第１の位置を識別する。次に、プロセッサは、出発する車両の位置と第１の位置とを連結するデータベース媒体中の連結された複数の道路セグメントを識別する。最後にプロセッサは、出発する車両の位置から目的地までの少なくとも１つのルートを識別する。識別されたルートは、前に識別された、複数の連結された道路セグメントの或る部分集合からなる。プロセッサには、複数のハイウエイアクセスランプの部分集合をユーザに与えて目的地を選択させるディスプレイが接続されている。また、ディスプレイは、識別されたルートをユーザに連絡する。
【００１０】
また本願は、上記特徴をもつ車両ナビゲーションシステムを開示する。
【００１１】
【実施例】
本発明の本質及び長所は、本願明細書の以下の記載及び図面を参照することにより一層理解できるであろう。
【００１２】
本発明は、全体として、一般譲渡された係属中の、「相対接近センサの較正方法」という名称の１９９２年５月１５日付米国特許出願第０７／８８３，８５９号、「ルートガイダンスオンオフルート状態フィルタ」という名称の１９９２年５月１５日付米国特許出願第０７／８８４，７４９号、「車両ナビゲーションシステムの位置矯正方法」という名称の１９９３年１月５日付米国特許出願第０８／０００，９５０号、及び「車両ナビゲーションシステムにおける目的地選択方法」という名称の１９９３年７月２９日付米国特許出願第０８／０９９，２０７号に関連している。尚、これらの全ての特許出願明細書は本願に援用する。
【００１３】
図１は、本発明に使用する車両ナビゲーションシステム１０の特定実施例のブロック図である。センサ１２、１４及びＧＰＳ受信器１８は、センサ／ＧＰＳインターフェース２２を介して計算手段２０に接続されている。典型的な実施例では、走行距離センサ１２はオドメータ（距離計）からなり、角速度センサ１４はジャイロスコープ、又は車両の車輪に連結された差動オドメータからなる。ＧＰＳ（地球投影位置決定システム）のデータ受信器１８は、例えば衛星によるナビゲーションシステムからの信号を受けるためのものである。センサ／ＧＰＳインターフェース２２からのデータは、較正機能、信号処理機能、推測航法機能、車両位置決め機能及びルートガイダンス機能を遂行するＣＰＵ２４に伝送される。マップ情報が入ったデータベースはデータベース媒体２６に記憶され、計算手段２０の作動を命令するソフトウェアが、ＣＰＵ２４を実行させる主メモリ２８に記憶されている。メモリ２８は、ＲＯＭ（リードオンリメモリ）、又はフラッシュメモリ又はＳＲＡＭのような再プログラミング可能な不揮発性メモリで構成できる。システムのＲＡＭ３０は、このようなソフトウェアプログラムの実行に必要な情報の読取り及び書込みが可能である。データベース媒体２６は、不揮発性メモリ、ハードディスクドライブ、ＣＤ−ＲＯＭ、又はデジタル化されたマップ情報が記憶されている集積回路で構成できる。出力コントローラ３２はグラフィックコントローラで構成でき、ＣＰＵ２４により処理されたデータを受け入れ且つ出力コミュニケータ３４（通常、ディスプレイスクリーンからなる）を含むディスプレイコンソールにデータを伝送する。ユーザは、ユーザインターフェース３６（一般に、キーボードからなる）を介して、所望の目的地等のデータを入力できる。
【００１４】
データベース媒体２６に記憶されるマップデータベースは、交差点、道路セグメント、陸標（ランドマーク）、関心のある場所、その他の地理的情報を記述するため、例えば緯度座標及び経度座標のような位置データで構成するのが好ましい。データベースは更に、道路名、地名等の特徴、分離帯、一方通行規制、路面、制限速度、形状、高架及び他の道路上の特徴をマップ上に表すデータを有する。マップデータベースに記憶されたデータを用いて、車両ナビゲーションシステムは、推測航法で求めた位置と、データベースに記憶された道路セグメント、交差点及び他の地理的位置とを比較するすることにより、１つ以上の可能性のある車両位置を生成する。次に、システムは、１組の位置可能性をふるい分けし、残余の位置可能性から車両の現在位置と思われる位置を選択する。
【００１５】
本発明の一実施例によれば、データベース媒体２６に記憶されたマップデータベース情報が、ハイウェイのアクセスランプの位置が記憶された付加アクセスランプデータベースを創出するのに使用される。アクセスランプデータベースには、各ハイウェイの入口名及び出口名、各出口間の距離、及び各方向のハイウェイ名（例えば、「ＵＳ−１０１南」）を含めることができる。本発明の幾つかの実施例では、サービスステーション、レストラン及び宿泊施設等のＰＯＩが、各出口の付加データベースに含まれている。
【００１６】
本発明の一実施例によるアクセスランプデータベースの創出が、図２のフローチャートに示されている。最初に、ハイウエーに属し且つ或る種のアクセスランプに接続された元のマップデータベースの全ての道路セグメントを含むハイウエイデータベースが創出される（ステップ５０）。これらの道路セグメントは、下記の基準に基づいて選択される。道路セグメントは次の場合すなわち、
１）道路セグメントの制限速度が所定の或る速度（例えば、時速５０マイル）を超える場合。
２）道路セグメントにハイウエイ番号（すなわち、ＵＳ−１０１、Ｉ−５等）が付されている場合。
３）道路セグメントがランプでない場合。（幾つかのランプは、比較的高い制限速度を有し且つハイウエイ番号が付されている）
４）道路セグメントがランプ又は分岐点である少なくとも１つの入口又は出口に連結されている場合。（すなわち、ランプを持たないハイウエイ又はエクスプレスウエイのセグメントはこのデータベースに含まれない）
には、ハイウエイデータベースに記憶すべきハイウエイセグメントであると見なされる。
【００１７】
ハイウェイデータベースに含まれる道路セグメントは、単一デジタル化及び二重デジタル化される。単一デジタル化とは、両移動方向が表される道路セグメントをいう。二重デジタル化とは、両移動方向のうちの一方の移動方向のみを表す道路セグメント（すなわち、両移動方向についての道路セグメントが存在する場合）をいう。道路セグメントが単一デジタル化される場合には、各移動方向について１つのセグメントが、ハイウェイデータベースに記憶される。
【００１８】
ハイウェイデータベースに記憶される特定の道路セグメントを適格化する入口及び出口は、下記の全ての基準を満たすものである。下記のセグメント形式は入口として適している。
【００１９】
１）一方の道路が他方の道路に対して高架になっている２つの道路を一緒に連結するセグメント。ＮａｖＴｅｃｈにより与えられるマップデータベースでは、これらのセグメントは、６のＳＩＦ（標準インターフェースフォーマット）リンククラス（例えばランプ）を備えたセグメントに相当する。後述のように、入口の名前はランプが設けられた道路セグメントの好ましい名前から付けられる。すなわち、ランプが連結された「無名」道路セグメントは無視され、次の連結道路セグメントの名前が使用される。ランプが道路セグメントからアプローチできるか否かを判断するには、旋回規制及び一方通行規制もチェックされる。
【００２０】
２）他のハイウェイに連結されるハイウェイセグメント又はエクスプレスウェイセグメント（例えば、１又は２のＳＩＦリンククラスを備えたセグメント）。入口の名前は流入ハイウェイの名前である。
【００２１】
３）同じ高さの２つの道路を連結するセグメント（例えば、８のＳＩＦリンククラス（例えば分岐点）を備えたセグメント速度）。
【００２２】
他のハイウェイへの入口を含める理由は、一貫性（すなわち、全ての入口を含めること）のため、及び外来ドライバがローカル地域には不慣れであってもハイウェイには精通していることがあるためである。従って、ドライバは、目的地として、知っているハイウェイを選択するだけでよい。
【００２３】
下記のセグメント形式は出口として適している。
【００２４】
１）一方の道路が他方の道路に対して高架になっている２つの道路を一緒に連結するセグメント（例えば、６のＳＩＦリンククラス（例えばランプ）を備えたセグメント）。この場合、ハイウェイを出るときにランプに取り付けられる標識特性は、出口の好ましい名前である。
【００２５】
２）他のハイウェイに連結されるハイウェイセグメント又はエクスプレスウェイセグメント（例えば、１又は２のＳＩＦリンククラスを備えたセグメント）。出口の名前は他のハイウェイの名前である。
【００２６】
３）同じ高さの２つの道路を連結するセグメント（例えば、８のＳＩＦリンククラス（例えば分岐点）を備えたセグメント速度）。
【００２７】
ランプからアクセスできる他の街路も、特定出口のランプデータベースに含まれる。他のハイウェイへの出口を含めたい理由は、一貫性（すなわち、全ての出口を含めること）のため、及びドライバが特定ハイウェイに精通していることがあるためである。この場合、ドライバが目的地を選択するとき、ドライバは、知っているハイウェイへの出口へのルートガイダンスを必要とするに過ぎない。
【００２８】
ハイウエイに属し且つアクセスランプに連結している全ての道路セグメントがひとたび決定され且つハイウエイデータベースに記憶されると、記憶されたセグメントは、これらが属するハイウエイに従って及びこれらの移動方向に従って分類される（ステップ５２）。例えば、南下するハイウエイ１０１（名称はハイウエイ１０１南）に属する全てのセグメントは一まとめにグループ化される。単一デジタル化されるハイウエイのハイウエイセグメントは複製され、これらのセグメントの入力値はこれらのハイウエイの両方向について記憶されるようにする。２重デジタル化されたハイウエイからの、方向接尾語（例えばハイウエイ１０１南において南が走行方向を示す語であるからこの最後尾の語を方向接尾語という。以下同じ）を持たないハイウエイセグメントも、それぞれのハイウエイのいずれの側にこれらのセグメントが属するかを決定する目的で最初に複製される。
【００２９】
関連する方向接尾語をもたない二重デジタル化されたハイウェイセグメントの移動方向を決定するため、元のマップデータベースに記憶された情報を用いて、ハイウェイに沿う探究が行なわれる。この探究は、セグメント７０の両端から出発して、ハイウェイ７６に沿って後方及び前方（矢印７２及び矢印７４）に進行する。ハイウェイセグメントが方向接尾語を有することがひとたび見出されると（例えば、セグメント７８）、この方向が問題としているハイウェイセグメントの方向であると推定される。ハイウェイの単一デジタル化されたセグメントに出合う前に、このような方向接尾語が見出されない場合には、更に別の二重デジタル化されたセグメントに出合うまで、単一デジタル化されたセグメントに沿って探究が続けられる。一実施例では、二重デジタル化されたハイウェイセグメントに入るランプに取り付けられた入口標識の表記が方向の決定に使用される。他の実施例では、ハイウェイセグメントの方向決定を補助するのに、ハイウェイ番号付け規約が使用される。このような規約の一例として、南北に走るハイウェイには奇数番号が付され、東西に走るハイウェイには偶数番号が付されるというものがある。
【００３０】
特定ハイウェイセグメントの方向を決定するのに上記方法ではうまくいかない場合がある。これらの場合の１つは、方向矛盾が存在する場合、すなわち異なる方向接尾語をもつ２つのセグメントが見出された場合である。これは、図４に示すような道路形状の結果として生じる。利用可能なマップデータベースは、二重デジタル化されたハイウェイ（セグメント８０、８２）が単一デジタル化されたハイウェイ８４に旋回する（例えば、このため、Ｕターンが禁止されている）場所に必ずしも旋回規制を置いていないため、同じハイウェイの反対方向へのＵターン探究（すなわち、セグメント８２からセグメント８０）が起こり得る。本発明の一実施例によれば、探究アルゴリズム（ｅｘｐｌｏｒａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）に角度閾値を導入することにより、このようなＵターン探究が防止される。かくして、セグメント８０とセグメント８２とにより形成される角度αが何らかの所定角度より小さければ、反対方向のハイウェイへのＵターンを防止する旋回規制が生成される。一実施例では、この角度閾値は４５°である。
【００３１】
特定ハイウェイセグメントと関連する接尾語がなく、且つハイウェイセグメントが、接尾語をもつ同じハイウェイ名を有する別のハイウェイセグメントに連結されない幾つかの場合がある。このような場合、ハイウェイセグメントの方向を決定する方法がないことがある。一実施例によれば、これらの各「不良」セグメントについての接尾語を何にすべきかを定めるファイルが手作業で創出される。他の実施例では、元のマップデータベースが、このハイウェイセグメントの接尾語をもつように手作業で修正される。
【００３２】
ひとたびハイウェイセグメントがハイウェイ及び方向に従って分類されると、ハイウェイセグメントは、次に、位置順序付けされたハイウェイセグメントリストに位置分類される（図２のステップ５４）。各ハイウェイの各側について、別の位置順序付けされたハイウェイセグメントリストが生成される。リストは移動方向に順序付けされる。例えば、南下するハイウェイ１０１について記憶された最北セグメントは、ＵＳ−１０１南についての位置順序付けされたハイウェイセグメントリストの最初のセグメントである。
【００３３】
位置順序付けされたハイウェイセグメントリストが、ひとたびマップデータベースの各ハイウェイについて生成されると、１つのハイウェイについての入口及び出口が一度に識別される（ステップ５６）。次に、このようにして識別された各入口／出口についてのデータが、このハイウェイについてのアクセスランプデータベースに記憶される（ステップ５８）。これは、マップデータベースの各ハイウェイについて行なわれる（ステップ６０〜６８）。
【００３４】
一実施例では、各ハイウェイについての入口及び出口が、図５及び図６のフローチャートに従って識別される。最初に、各ハイウェイ方向について完全なハイウェイセグメントリストを構成する目的で、各ハイウェイについて位置順序付けされたハイウェイセグメントリストが探究される（ステップ１００）。ハイウェイの始点での二重デジタル化されたハイウェイセグメントから開始し且つ元のマップデータベースのデータを使用して、ハイウェイに沿ってセグメントから前方及び後方の両方向に探究を遂行する。ハイウェイの全てのセグメントが、移動方向において出合う順序に記憶される。ハイウェイについての全ての道路セグメントを含むこのリストを、本願では、完全なハイウェイセグメントリストと呼ぶ。完全なハイウェイセグメントリストは、特定ハイウェイについての出口及び入口を正確に順序付けするのに必要である。なぜならば、位置順序付けされたハイウェイセグメントリストは、ハイウェイ上を実際に走行するときにハイウェイセグメントが出合う順序にハイウェイセグメントを必ず記憶させることに信頼性がないからである。ハイウェイセグメントが正しくない順序に記憶される状況は、例えば、ハイウェイが、図７に示すように、それ自体の上を折り返す場合に生じる。この場合、セグメント９０は、移動方向においてはハイウェイ１０１南に沿ってセグメント９２よりも更に進行しているにも係わらず、セグメント９２よりも一層北側にある。
【００３５】
ハイウェイについての完全なハイウェイセグメントリストがひとたび構成されると、位置順序付けされたハイウェイセグメントリストに記憶されたハイウェイセグメントに連結される入口及び出口を位置決めすべく、完全なハイウェイセグメントリストがその移動方向について試験される（図５のステップ１０４）。このようなランプが見出されると、特定ハイウェイセグメントについての入口及び出口が、下記のようにして構成される（ステップ１０６）。特定ハイウェイセグメントについての出口及び入口がひとたび生成されると、位置順序付けされたハイウェイセグメントリストからセグメントを取り出し（ステップ１０８）、リストが消尽するまで完全なハイウェイセグメントリストに沿う探究が続けられる（ステップ１１０〜１１６）。或る場合には、完全なハイウェイセグメントリストは、対応する位置順序付けされたハイウェイセグメントリストが消尽する前に、消尽することがある。これは、２つのリストが関連するハイウェイが論理的不連続性（例えば、名前をもたないセグメント又はセグメント群）を有する場合、又は実際の物理的不連続性（例えば、地震又は洪水による被害）が存在する場合に生じる。このような状況では、特定の位置順序付けされたハイウェイセグメントリストについて１つ以上の完全なハイウェイセグメントリストを構成する必要がある。このことが生じると（ステップ１１８）、位置順序付けされたハイウェイセグメントリスト中の次のハイウェイセグメントが見出され（ステップ１２０）、上記ステップが反復される。これにより、位置順序付けされたハイウェイセグメントリスト中の次のハイウェイセグメントで開始する当該ハイウェイについての新たな完全なハイウェイセグメントリストが構成される。このようして、位置順序付けされたハイウェイセグメントリストが消尽するまで探究が続けられ（ステップ１１８）、消尽したときに手順が終了する（ステップ１２４）。この手順は、位置順序付けされた各ハイウェイセグメントリストについて実行される。
【００３６】
上記手順で位置決めされるアクセスランプは、次のようにして、入口として識別される。位置順序付けされたハイウェイセグメントリスト中のハイウェイセグメントに連結されるアクセスランプは、当該ランプが連結される全ての街路を識別すべく後戻りして探究される。可能性ある連結入口街路の幾つかを除外するため、一方通行規制及び旋回規制が観察される。同じ番号をもつ街路が見出されると、これは入口として含められることはない。なぜならば、同じハイウェイからの出口の可能性が最も高いからである。或る実施例では、ハイウェイが或るハイウェイ番号から他のハイウェイ番号に変わる場合に、ハイウェイがそれ自体の入口として含められる。これは、一般に、ハイウェイが２つのハイウェイに分岐するときに生じる。
【００３７】
２方向街路がハイウェイに入る場所には幾つかの異なるシナリオが考えられる。例えば、２方向街路が、該２方向街路上での両移動方向についてハイウェイへの１つの入口を有する場合には、１つの入口名のみがデータベースに記憶される。しかしながら、２方向街路が２つ（すなわち、２方向街路の各方向に１つずつ）の入口ランプを有する場合で、入口が図８に示すようにハイウェイに沿って隣接している場合には、入口は１つに合流される。街路が２つの別々の遠隔の場所でハイウェイに入る場合には、ランプの入口間の距離に基づくヒューリスティックス（発見的方法）を用いて、両入口１３０、１３２を記憶すべきであるか、両入口を１つに統合すべきかを決定する。
【００３８】
２つの入口を１つの入口のみに減少すると、問題が生じることもある。このような問題の１つは、図９を参照することにより理解されよう。ここで、ルート計算のための目的セグメントは、ハイウェイ１４２Ｎに直接連結されたランプセグメント１４０であると仮定する。セグメント１４０が選択され且つドライバがＡ街路上を東方向に移動している場合で、彼らが実際に目的地として望んでいるものがセグメント１４４である場合には、彼らはＵターンをしてセグメント１４０に入らなくてはならないであろう。このような場合における１つのアプローチは、入口リスト中のＡ街路を二度（すなわち、一度はＡ街路（東方向）として、もう一度は、このような方向情報を利用できるＡ街路（西方向）として）作表することである。他のアプローチは、両入口が目的地として選択された場合に、目的地として両入口を越えたハイウェイセグメントを記憶することである。この方法でのルート計算により、Ａ街路に沿う移動方向に基づいて適当な入口が選択されるであろう。
【００３９】
入口ランプの識別に際し、他の問題に遭遇することがある。例えば、入口名を決定するためランプから後戻りする方向にサーチするとき、ドライバが通常入口を連想する主要道路ではない小さな道路に出合う場合である。このような場合、より高いクラスの道路セグメントが見出されるまで探究が続けられる。或る実施例では、１つ以上の道路セグメントの名前が特定の入口と関連付けられ且つアクセスランプデータベースに記憶される。
【００４０】
ハイウェイの入口ランプに旋回できる多くの街路を設けることもできる。本発明の一実施例は、これらを別の入口として処理する。
【００４１】
ハイウェイ領域では、しばしば、２つのハイウェイがランプではなく、例えば簡単な交差点で交差する。本発明の一実施例は旋回規制を考慮に入れ、且つ交差点に連結されたハイウェイセグメントを、旋回規制を受ける交差点に連結された他の各セグメントへの入口（及び該セグメントからの出口）として処理する。
【００４２】
ひとたび適正に識別され且つ付加データベースに記憶されると、入口ランプセグメントは、図１に関連して前述したように、ルートガイダンスのための目的地として使用される。
【００４３】
出口ランプの識別は、出口がアクセスを与える道路セグメントに関する付加情報が全体として利用可能である点を除き、上記入口ランプの識別と同様にして行なわれる。例えば、出口は「・・方面」及び「・・分岐」等の標識を有し、これらは、方向連結が行なわれる道路を識別すること、及びランプに直接連結されない付加主要道路があるか否かを決定することの両方に使用できる。また、このような標識により与えられる付加情報は、例えば、出口ランプセグメント１５０が出口としてハイウェイ１５２Ｎに再連結される場合（図１０（ａ））、出口ランプセグメント１６０が同じ道路１６２の両方向に分岐している場合（図１０（ｂ））、同じ道路１７４の異なる方向への出口ランプ１７０、１７２が互いに近接している場合（図１０（ｃ））、及び出口ランプセグメント１８０が、大きな道路１８４ではなく小さなアクセス道路１８２に連結される場合（図１０（ｄ））のような不明瞭な状況を一掃するのに使用できる。上記解決方法は、出口ランプを明瞭に識別するのに使用できるだけでなく、標識情報はこれらの問題の解決にも使用できる。
【００４４】
一般に、標識表記は、既存のマップデータベースに用いられている道路の略記とは異なり、道路のフルネームを使用している。かくして、一実施例によれば、道路標識の表記が上記方法で使用される場合には、略記名への変換すなわち標準化が行なわれる（すなわち、「Ｂｏｕｌｅｖａｒｄ」は「Ｂｌｖｄ」となる）。道路の接頭語又は接尾語情報もマップデータベースに採用されている略記フォーマットに標準化される（すなわち、「Ｎｏｒｔｈ」は「Ｎ」となる）。別の実施例では、ひとたび標識表記の標準化が完了すると、この標識が確認される。確認には、標準化された表記が既存道路を表しているか否かの決定が含まれる。これは、出口としてのＰＯＩすなわち都市名の誤記の機会を減少させる。
【００４５】
入口ランプと同様にして、所望の街路へのアクセスを与える出口ランプセグメントは、ルート計算を行なうための目的地として使用できる。いかなる街路も見出されない場合（例えば、街路を表示する標識のみの場合）には、ハイウェイを出て直ぐのランプセグメントが目的地として使用される。
【００４６】
ひとたびランプデータベースがコンパイルされると、車両ナビゲーションシステムのユーザは、下記の方法で、目的地としてハイウェイアクセスポイントを選択することができる。ユーザは、ディスプレイスクリーン上に表示されたハイウェイリストからハイウェイを選択する。番号が付されたハイウェイ名及びローカルハイウェイ名の両方が与えられる。例えば、ＵＳ−１０１は、ＲｅｄｗｏｏｄＨｉｇｈｗａｙ、Ｂａｙｓｈｏｒｅ  Ｆｒｅｅｗａｙ、Ｖｅｎｔｕｒａ  Ｆｒｅｅｗａｙ、及びＨｏｌｌｙｗｏｏｄ  Ｆｒｅｅｗａｙ等の種々の名前で知られている。一実施例によれば、各ハイウェイの方向は別々に識別される。例えば、ＵＳ−１０１北と、ＵＳ−１０１南とは別々の選択である。
【００４７】
ひとたびハイウェイ及び方向が選択されると、システムは、ユーザに、目的地として入口又は出口のいずれかを選択させる。入口及び出口は、ディスプレイスクリーン上に別々に表される。アクセスポイントのリストをディスプレイするとき、システムは、現在の車両位置に最も近いアクセスポイントを強調して、これをディスプレイスクリーンの中央に置く。ドライバは、アクセスポイントのリストをスクロールアップ又はスクロールダウンでき、現在の車両位置から各アクセスポイントまでの距離は、各アクセスポイントが強調されるときに与えられる。
【００４８】
別の実施例では、ユーザには、方向とは無関係にハイウェイのリストが与えられる。ひとたびハイウェイが選択されると、ユーザには、ハイウェイのアクセスポイントが入口であるか出口であるかとは無関係にアクセスポイントのリスト、又はアクセスポイントがアクセスを与えるハイウェイの方向が示される。ひとたびユーザがこのリストからアクセスポイントを選択すると、ユーザは、入口又は出口（及び、一実施例ではハイウェイ方向）のいずれかを選択させられる。次に、システムのルート計算アルゴリズムに、選択された基準に合致する全てのアクセスポイントが与えられ、最良のアクセスポイントが自動的に選択される。例えば、図９のセグメント１４０、１４４がルート計算アルゴリズムに与えられ、現在の車両位置に基づき最良の１つが選択される。アクセスポイントのリストを表示するディスプレイスクリーン上に、ハイウェイの名前（番号が付された名前及びローカル名の両方を含めることができる）が示され、ユーザに、これらのアクセスポイントが関連するハイウェイを想起させる。ユーザがアクセスポイントのリストをスクロールアップ及びスクロールダウンするとき、ローカルハイウェイ名の適当な変更が反映される。アクセスポイントが位置する市又は州も表示される。
【００４９】
図１１には、本発明の一実施例に従って設計された車両ナビゲーションシステムのユーザに提供される一連のディスプレイスクリーンが示されている。この例では、ユーザは、特定のフリーウェイ上に、Ｉｎｔｅｒｓｔａｔｅ２８０北を得ることを望んでいるに過ぎない。ディスプレイスクリーン２００（「Ｓｅｌｅｃｔ  Ｆｒｅｅｗａｙ」スクリーン）は、Ｉ−２８０Ｎが強調されていることを示している。ユーザが「Ｅｎｔｅｒ」ボタン２０２を押すと、システムはスクリーン２０４（「Ｓｅｌｅｃｔ  Ｅｎｔｒａｎｃｅ／Ｅｘｉｔ」スクリーン）に進む。ここで、入口を選択すると、システムは「Ｓｅｌｅｃｔ  Ｅｎｔｒａｎｃｅ」スクリーン２０６に進む。出口を選択すると、システムは「Ｓｅｌｅｃｔ  Ｅｘｉｔ」スクリーン２０８に進む。入口又は出口のいずれを選択しても、システムは「ルート計算基準選択メニュー」２１０に進み、選択された目的地までのルート計算を続ける。
【００５０】
以上、本発明を特定実施例に関連して図示し且つ説明したが、当業者ならば、本発明の精神及び範囲から逸脱することなく形態及び細部において前述の変更及びその他の変更を成し得るであろう。
【図面の簡単な説明】
【図１】本発明に使用する車両ナビゲーションシステムのブロック図である。
【図２】本発明の一実施例によるアクセスランプデータベースの生成を説明するフローチャートである。
【図３】ハイウェイのセグメントの決定方向に関するＵＳ−１０１南の一部を示す図面である。
【図４】単一デジタル化されたハイウェイに旋回する二重デジタル化されたハイウェイを示す図面である。
【図５】マップデータベースにおける各ハイウェイについての入口及び出口の識別を説明するフローチャートである。
【図６】図５に続くフローチャートである。
【図７】二重戻り部をもつＵＳ−１０１南の一部を示す図面である。
【図８】同一道路から１つのハイウェイ方向に入る２つの入口ランプを示す図面である。
【図９】同一道路から１つのハイウェイ方向に入る２つの入口ランプの別の構成を示す図面である。
【図１０】（ａ）、（ｂ）、（ｃ）及び（ｄ）は、不明瞭なランプ構成の例を示す図面である。
【図１１】目的地としてのハイウェイアクセスポイントの選択を示す一連のディスプレイスクリーンを示す図面である。
【符号の説明】
１０  車両ナビゲーションシステム
１２  走行距離センサ
１４  角速度センサ
１８  ＧＰＳ（地球投影位置決定システム）
２０  計算手段
２２  センサ／ＧＰＳインターフェース
２４  ＣＰＵ
２６  データベース媒体
２８  主メモリ
３０  ＲＡＭ
３２  出力コントローラ
３４  出力コミュニケータ
３６  ユーザインターフェース
４０  ディスプレイコンソール
７０  セグメント
７２  矢印
７４  矢印
７６  ハイウェイ
７８  セグメント
８０  二重デジタル化されたハイウェイのセグメント
８２  二重デジタル化されたハイウェイのセグメント
８４  単一デジタル化されたハイウェイ
９０  セグメント
９２  セグメント
１３０  入口
１３２  入口
１４０  セグメント
１４４  セグメント
１５０  出口ランプセグメント
１６０  出口ランプセグメント
１６２  道路
１７０  出口ランプ
１７２  出口ランプ
１７４  道路
１８０  出口ランプセグメント
１８２  小さなアクセス道路
１８４  大きな道路
２００  ディスプレイスクリーン
２０２  「Ｅｎｔｅｒ」ボタン
【図１】
0003675891.tif 000002
【図２】
0003675891.tif 000003
【図３】
0003675891.tif 000004
【図４】
0003675891.tif 000005
【図５】
0003675891.tif 000006
【図６】
0003675891.tif 000007
【図７】
0003675891.tif 000008
【図８】
0003675891.tif 000009
【図９】
0003675891.tif 000010
【図１０】
0003675891.tif 000011
【図１１】
0003675891.tif 000012