(57)【特許請求の範囲】
【請求項１】
探索開始点から順次探索枝を延ばして目的点までの経路を探索する経路探索方法において、
リンクが計画道路リンクであるか否か及び計画道路リンクであれば開通予定日を地図情報に含ませておき、
経路探索に際して、着目リンクが計画道路リンクであれば、開通予定日を経過しているか判断し、
開通予定日を経過してなければ該リンクを経路探索対象リンクから除外し、
開通予定日を経過していれば該リンクを経路探索対象リンクとして経路探索処理を行い、
目的地までの経路探索が完了し、該探索した経路を主経路とするとき、該主経路に計画道路リンクが含まれているかチェックし、
含まれていれば、該計画道路リンクを含まない目的地までの予備の経路を探索し、
経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する、
ことを特徴とする経路探索方法。
【請求項２】
経路誘導に際して、主経路と予備経路を識別可能に共に表示し、
経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する、
ことを特徴とする請求項１記載の経路探索方法。
【請求項３】
探索開始点から順次探索枝を延ばして目的点までの経路を探索するナビゲーション装置において、
リンクが計画道路リンクであるか否か及び計画道路リンクであれば開通予定日を含む地図情報を記憶する地図情報記憶部、
経路探索を要求する経路探索要求部、
経路探索に際して、着目リンクが計画道路リンクであれば、開通予定日を経過しているか判断し、開通予定日を経過してなければ該リンクを経路探索対象リンクから除外し、開通予定日を経過していれば該リンクを経路探索対象リンクとして経路探索処理を行う経路探索部、
探索された経路情報を保存する経路情報保存部、
探索された経路を表示するための描画制御を行う経路描画制御部、
を備え、
前記経路探索部は、目的地までの経路探索が完了し、該探索した経路を主経路とするとき、該主経路に計画道路リンクが含まれているかチェックし、含まれていれば、該計画道路リンクを含まない目的地までの予備の経路を探索して前記経路情報保存部に保存し、
前記経路描画制御部は、経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する、
ことを特徴とするナビゲーション装置。
【請求項４】
前記経路描画制御部は、経路誘導に際して、主経路と予備経路を識別可能に共に表示し、経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する、
ことを特徴とする請求項３記載のナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は探索開始点から順次探索枝を延ばして目的点までの経路を探索する経路探索方法及びナビゲーション装置に係わり、特に、計画道路リンクを経路探索の対象リンクとして使用する経路探索方法及びナビゲーション装置に関する。
【０００２】
【従来の技術】
車載用ナビゲーション装置は、出発地点から目的地点までのコスト最小の経路を辿るような経路を探索し、画面に該経路を表示して運転者の走行案内をする（経路誘導機能）。この経路誘導機能によれば、実際の運転に際して、誘導経路を特定の色で太く表示するなど他の道路と識別可能に表示して、運転者が目的地まで容易に到着できるようになっている。車両が走行する最適経路を道路地図データから検索する方法として、Ａ*アルゴリズムやダイクストラ法などが知られており、探索の各段階で枝を伸ばして探索を進め、最終的にコスト最小の最適経路を探索する。
【０００３】
【発明が解決しようとする課題】
現在のナビゲーションデータベースにはこれから造られる予定の道路(計画道路)情報も含んでいる。これらの計画道路情報は、地図表示などの機能で利用されている。すなわち、計画道路であっても地図上に表示されるようになっている。しかし、計画道路は開通していない可能性であるため、経路探索の対象としていない。このように計画道路を経路探索の対象から除外すると、実際に開通している場合には経路探索に際して開通道路を利用できず不都合であり、又、ユーザに悪印象を与える。例えば、ユーザに「目の前にあるバイパスを降りて、わざわざ街中を誘導するナビゲーション装置」という悪い印象を与えてしまう。
【０００４】
以上から本発明の目的は、計画道路であっても開通している道路は経路探索の対象とすることができるようにすることである。
本発明の別の目的は、開通予定日を経過しているため経路探索の対象とした計画道路が実際に未だ開通していない場合であっても、計画道路を通らない予備経路を直ちにドライバに提供できるようにすることである。
【０００５】
【課題を解決するための手段】
本発明の経路探索方法では、(1) リンクが計画道路リンクであるか否か及び計画道路リンクであれば開通予定日を地図情報に含ませておき、(2) 経路探索に際して、着目リンクが計画道路リンクであれば、開通予定日を経過しているか判断し、(3) 開通予定日を経過してなければ該リンクを経路探索対象リンクから除外し、(4) 開通予定日を経過していれば該リンクを経路探索対象リンクとして経路探索処理を行う。このように開通予定日を経過しているかにより計画道路を経路探索対象とするか決定するため、開通している計画道路を確実に経路探索の対象にでき、利便性を向上することがきる。
【０００６】
又、本発明では、(1) 目的地までの経路探索が完了したとき、該探索経路（主経路）に計画道路リンクが含まれているかチェックし、(2) 含まれていれば、該計画道路リンクを含まない目的地までの予備の経路を探索し、(3) 経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する。あるいは、(1) 目的地までの経路探索が完了したとき、該探索経路（主経路）に計画道路リンクが含まれているかチェックし、(2) 含まれていれば、該計画道路リンクを含まない目的地までの予備の経路を探索し、(3) 経路誘導に際して、主経路と予備経路を識別可能に共に表示し、(4) 経路誘導による走行においてオフルートした時、自動車が予備経路上に存在すれば該予備経路を主経路として表示する。以上のようにすれば、開通予定日を経過しているため経路探索の対象とした計画道路が実際に未だ開通していない場合であっても、計画道路を通らない予備経路を直ちにドライバに提供することができる。
【０００７】
【発明の実施の形態】
（Ａ）ナビゲーション装置の構成
図１は本発明を実現するナビゲーション装置の構成図であり、１１は道路地図を記憶するDVD（地図データ記憶部）である。地図データは、(1) 図２に示す道路レイヤと、(2) 地図上のオブジェクトを表示するための背景レイヤと、(3) 市町村名や国道名などを表示するための文字レイヤなどから構成されている。道路レイヤは、図２に示すように、ノ−ドテーブルNDTB、道路リストRDLT、交差点構成ノ−ドリストCRLT等を有している。道路リストRDLTは該当道路リンクのリンク属性情報、リンクを構成する各ノ−ド位置情報を含んでいる。リンク属性には、▲１▼探索対象フラグ、▲２▼リンク種別コード、▲３▼道路種別、▲４▼有料道路フラグ、・・・▲５▼計画道路か否かを示すフラグ（計画道路フラグ）、▲６▼計画道路開通日等が含まれている。本発明では、経路探索を行っている日が計画道路開通日以降であれば該計画道路を経路探索対象リンクとして使用し、計画道路開通日前であれば経路探索対象リンクとして使用しない。
【０００８】
交差点ノ−ド構成リストCRLTは地図上の各交差点毎に、該交差点に連結する各リンクの他端ノ−ド（交差点構成ノ−ドという）の集合を示すものである。ノ−ドテ−ブルNDTBは地図上の全ノ−ドのリストであり、ノ−ド毎に▲１▼位置情報（経度、緯度）、▲２▼該ノ−ドが交差点であるか否かの交差点識別フラグ、▲３▼交差点であれば交差点データを指し、交差点でなければ該ノ−ドが属する道路リンクを指すポインタ等で構成されている。
【０００９】
図１に戻って、１２は自動車の現在地に応じた地図や自動車位置マ−ク、誘導経路等を描画するディスプレイ装置（CRT）、１３は走行中の自動車の走行距離と方位に基づいて現在地を算出する現在地検出部である。現在地検出部１３は、図示しないが、自動車の進行方位を検出する方位センサや走行距離を検出する車速センサ、方位や走行距離に基づいて自動車の現在地（経度、緯度）を算出する位置計算用CPUを有している。尚、実際にはこれらセンサとGPS受信機を併用して現在地検出を行うのが一般的になっている。
１４は地図検索キー、地図スクロ−ルキー、経路探索キー、メニューキー等を備えたリモコンなどの操作部、１５はナビゲーション制御装置であり、地図データに基づき車両現在地周辺の地図画像を発生すると共に、誘導経路を探索し、誘導経路画像や自動車位置マ−クを発生する。
ナビゲーション制御装置１５において、１５ａは現在地データに基づき、現在地周辺で画面表示範囲より広い範囲の地図データ（例えば９画面分の地図データ）をDVD １１から読出し、該地図データに基づいてドットイメ−ジの地図画像を発生する地図画像描画部である。
【００１０】
１５ｂは誘導経路探索処理により得られた出発地から目的地までの誘導経路データに基づいて誘導経路画像を発生する誘導経路描画部、１５ｃは地図画像及び誘導経路画像を記憶するビデオRAMである。地図画像描画部１５ａはディスプレイ画面の表示範囲がビデオRAM １５ｃの画像範囲を越えないように、自動車の走行に従って、随時、ビデオRAM １５ｃを書き替え、また誘導経路描画部１５ｂも自動車の走行に応じて誘導経路画像を発生してビデオRAM １５ｃに記憶するようになっている。
【００１１】
１５ｄは車両現在地がディスプレイ画面の固定点に位置するようにビデオRAM １５ｃから１画面分の地図画像を読み出す読出制御部であり、読出し位置は地図画像描画部１５ａから指示される。１５ｅはディスプレイ画面の固定点に自動車位置マ−クを表示するための自動車位置マ−ク発生部、１５ｆは経路探索部であり、経路探索時に出発地と目的地が入力されると地図データに含まれる道路レイヤ情報に基づいて、出発地から目的地迄の最適経路を誘導経路として算出する。又、経路探索部１５ｆはオフルート時、自動車現在位置から目的地までの誘導経路を探索する機能を有している。１５ｇは誘導経路を構成するノ−ドを順次記憶する誘導経路記憶部である。１５ｈは合成部であり、ビデオＲＡＭ１５ｃ、自動車位置マ−ク発生部１５ｅからそれぞれ読出された地図画像及び誘導経路画像、自動車位置マ−ク画像、その他メニュー画像を適宜合成してＣＲＴ１２に出力して表示する。１５ｉは案内部であり、操作部１４より入力した経路探索要求を受信し、経路探索部１５ｆにその要求を通知するものである。
【００１２】
（Ｃ）第１の経路探索処理
図３は本発明の第１の経路探索処理のフローである。
ユーザが操作部１４を操作して経路探索のための要求を入力すれば、案内部 １５ｉは該経路探索要求を経路探索部１５ｆに通知し（Driver's Guidance)、経路探索部１５ｆは該要求を受け付ける（ステップ１０１〜１０２）。例えば、操作部より目的地の設定、計画道路使用可否の設定、経路属性の設定等を行えば、これらは案内部１５ｉを介して経路探索部１５ｆに通知される。計画道路使用可否の設定とは、計画道路属性のリンクを探索枝拡張の際に使用するか否かの設定であり、経路属性の設定とは現オーダーが主経路作成要求か予備経路作成要求かの設定である。
この状態で、経路探索の開始が指示されると経路探索部１５ｆは地図情報を用いた経路作成処理ルーチン（図４）を実行する（ステップ１０３）。経路作成処理ルーチンにより経路が探索されると該経路をディスプレイ画面に表示して経路誘導をする（ステップ１０４）。
【００１３】
経路作成処理ルーチンにおいて、経路探索部１５ｆはダイクストラ法などにより探索枝拡張処理を実行し、該処理により接続リンクを取得する（ステップ１０３ａ）。ついで、該接続リンクが計画道路リンクであるか否かを道路レイヤ情報を参照して調べ（ステップ１０３ｂ）、計画道路リンクでなければ、経路探索対象リンクとみなし（ステップ１０３ｃ）、経路探索処理を実行し（ステップ１０３ｄ）、ついで、目的地までの経路が探索されたかチェックし（ステップ１０３ｅ）、探索されてなければステップ１０３ａ以降の処理を繰り返す。
【００１４】
ステップ１０３ｂにおいて、計画道路リンクであれば、当該計画道路リンクの開通日を求め、現在の日時が道路開通日以降の日時であるかチェックし（ステップ１０３ｆ）、道路開通日以降であれば計画道路リンクを経路探索対象リンクとみなし（ステップ１０３ｃ）、経路探索処理を実行し（ステップ１０３ｄ）、ついで、目的地までの経路が探索されたかチェックし（ステップ１０３ｅ）、探索されてなければステップ１０３ａ以降の処理を繰り返す。
又、ステップ１０３ｆにおいて、現在の日時が道路開通日に至っていないければ計画道路リンクを経路探索の対象から除外し（ステップ１０３ｇ）、ついで、目的地までの経路が探索されたかチェックし（ステップ１０３ｅ）、探索されてなければステップ１０３ａ以降の処理を繰り返す。
一方、ステップ１０３ｅにおいて、目的地までの経路探索が完了すれば、図３のステップ１０４の処理を実行する。尚、探索された経路は誘導経路記憶部１５ｇに保存される。
【００１５】
（Ｄ）第２の経路探索処理
図５は本発明の第２の経路探索処理のフローである。
ユーザが操作部１４を操作して経路探索のための要求を入力すれば、案内部 １５ｉは該経路探索要求を経路探索部１５ｆに通知し（Driver's Guidance)、経路探索部１５ｆは該要求を受け付ける（ステップ２０１〜２０２）。例えば、操作部より目的地の設定、計画道路使用可否の設定、経路属性の設定等を行う。
この状態で、経路探索の開始が指示されると経路探索部１５ｆは地図情報を用いた経路作成処理ルーチン（図４）を実行する（ステップ２０３）。経路作成処理ルーチンにより経路が探索されると探索した経路の中に計画道路属性のリンクが含まれているか否かを判別する（ステップ２０４）。
探索経路に計画道路リンクが含まれていなければ、ステップ２０２の要求受付処理で設定された経路属性を参照して当該探索経路が主経路であるか予備経路であるかを判定する（ステップ２０５）。主経路であれば、該主経路を用いて図６の経路誘導ルーチンを実行する。
【００１６】
一方、ステップ２０４において、探索経路に計画道路リンクが含まれていれば、計画道路始点から出発地寄りの最初の交差点を予備経路始点として求める（ステップ２０７）。ついで、出発地から予備経路始点までを結ぶ経路を基本予備経路としてコピーし（ステップ２０８）、以後、ステップ２０２以降の処理により予備経路始点から目的地までの経路（従属予備経路という）を探索する。従属予備経路の探索が完了し、該経路の中に計画道路リンクがなければ、ステップ２０４，２０５を介して予備経路編集処理を行う（ステップ２０９）。すなわち、ステップ２０８でコピーしてある基本予備経路と今回の経路作成処理でつくられた従属予備経路を接続して予備経路を作成し、誘導経路記憶部１５ｇに記憶する。以後、図６の経路誘導ルーチンを実行する（ステップ２０６）。
【００１７】
図６の経路誘導処理ルーチンでは、主経路をディスプレイ画面に表示して経路誘導する（ステップ３０１）。ついで、目的地に到達したかチェックし（ステップ３０２）、到達すれば経路誘導処理ルーチン処理を終了する。
目的地に到達してなければ、オフルートしたか、すなわち、探索経路から自動車が外れたかチェックし（ステップ３０３）、オフルートしなければステップ３０１以降の主経路による経路誘導処理を継続する。
【００１８】
しかし、自動車が計画道路を走行せずオフルートし、予備経路上に存在すれば、計画道路が道路開通日以降の現日時になっても未開通であると判定し、主経路を消し、代わって予備経路を主経路にして表示し（ステップ３０４）、以後、新主経路による経路誘導を継続し（ステップ３０５）、目的地に到達するまで該新主経路による誘導経路表示を行う（ステップ３０６）。
以上のように経路誘導を行えば、計画道路が未開通であってオフルートすると直ちに予備経路に基づいて経路誘導を続行することができる。
【００１９】
図６の経路誘導処理ルーチンでは計画道路が未開通のためオフルートするまで主経路のみ表示するが、最初から主経路と予備経路を表示し、オフルートしたら主経路を消し、予備経路を主経路として表示することもできる。図７はかかる経路誘導処理ルーチンの別の処理フローである。
最初に計画道路未開通時の予備経路と開通時の主経路を表示することをユーザに通知する（ステップ４０１）。ついで、主経路と予備経路を識別可能に表示して経路誘導を行う（ステップ４０２）。例えば、予備経路は薄い線又は点線などで表示する。しかる後、目的地に到達したかチェックし（ステップ４０３）、到達すれば経路誘導処理ルーチン処理を終了する。
目的地に到達してなければ、オフルートしたか、すなわち、探索経路から自動車が外れたかチェックし（ステップ４０４）、オフルートしなければステップ４０２以降の経路誘導処理を継続する。
【００２０】
しかし、自動車が計画道路を走行せずオフルートし、予備経路上に存在すれば、計画道路が道路開通日以降の現日時になっても未開通であると判定し、主経路を消し、代わって予備経路を主経路にして表示し（ステップ４０５）、以後、新主経路による経路誘導を継続し（ステップ４０６）、目的地に到達するまで該新主経路による誘導経路表示を行う（ステップ４０７）。
以上のように経路誘導を行えば、計画道路が未開通であってオフルートすると直ちに予備経路に基づいて経路誘導を続行することができる。
以上、本発明を実施例により説明したが、本発明は請求の範囲に記載した本発明の主旨に従い種々の変形が可能であり、本発明はこれらを排除するものではない。
【００２１】
【発明の効果】
本発明によれば、道路開通予定日を経過しているかにより計画道路を経路探索対象とするか決定するため、開通している計画道路を確実に経路探索の対象にでき、利便性を向上することがきる。
又、本発明によれば、開通予定日を経過しているため経路探索の対象とした計画道路が実際に未開通の場合であっても、計画道路を通らない予備経路をドライバに瞬時に提供することができる。
【図面の簡単な説明】
【図１】本発明を実現するナビゲーション装置の構成図である。
【図２】道路レイヤ説明図である。
【図３】本発明の第１の経路探索処理のフローである。
【図４】経路作成処理ルーチンである。
【図５】本発明の第２の経路探索処理のフローである。
【図６】経路誘導処理ルーチンである。
【図７】経路誘導処理ルーチンの別の例である。
【符号の説明】
１１・・DVD（地図データ記憶部）
１２・・ディスプレイ装置（CRT）
１３・・現在地検出部
１４・・操作部
１５・・ナビゲーション制御装置
１５ａ・・地図画像描画部
１５ｂ・・誘導経路描画部
１５ｃ・・ビデオRAM
１５ｄ・・読出制御部
１５ｅ・・自動車位置マ−ク発生部
１５ｆ・・経路探索部
１５ｇ・・誘導経路記憶部
【図１】
0004454162.tif 000002
【図２】
0004454162.tif 000003
【図３】
0004454162.tif 000004
【図４】
0004454162.tif 000005
【図５】
0004454162.tif 000006
【図６】
0004454162.tif 000007
【図７】
0004454162.tif 000008