(57)【要約】【課題】下位の階層での経路探索をより適切に行なうことのできるナビゲーション装置を提供する。【解決手段】経路探索部４３は、上位のレイヤＨｎで探索した中間経路Ｒｍｎと最短直線Ｌとで囲まれる領域である再探索要否判断用領域の面積Ｓｎを算出し、再探索要否判断用領域の面積Ｓｎが所定の基準値Ｓｔｈｎ以上である場合に、下位のレイヤＨｎ＋１にて中間経路Ｒｍｎ＋１を再探索する。また、所定の基準値Ｓｔｈｎとして、交点Ｃ１０及びＣ２０間の距離交点間の距離を直径とする半円の面積を採用する。【選択図】図１
2011191065.tif 000002
【特許請求の範囲】
【請求項１】
出発地を設定する出発地設定部と、
目的地を設定する目的地設定部と、
地図情報が道路の詳細度に応じた階層にて記憶されている地図情報記憶部と、
前記出発地から前記目的地までの経路を、前記地図情報記憶部に記憶されている地図情報を用いて探索する経路探索部とを備えるナビゲーション装置において、
前記経路探索部は、
出発地近傍の経路である出発地近傍経路と、目的地近傍の経路である目的地近傍経路とを結ぶ経路である中間経路については、これら出発地近傍経路及び目的地近傍経路を探索する階層よりも道路の詳細度が低い上位の階層にて探索し、
その探索した中間経路と現在地及び目的地を結ぶ最短直線とで囲まれる領域である再探索要否判断用領域の面積を算出し、
再探索要否判断用領域の面積が所定の基準値以上である場合に、前回中間経路を探索した階層よりも道路の詳細度が高い下位の階層にて中間経路を再探索することを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、
前記中間経路は、複数のリンクから構成されており、
前記経路探索部は、それら複数のリンクの個々に対し、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を前記再探索要否判断用領域の面積として算出することを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置において、
前記経路探索部は、リンクの終点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項４】
請求項２に記載のナビゲーション装置において、
前記経路探索部は、リンクの始点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項５】
請求項２に記載のナビゲーション装置において、
前記経路探索部は、リンクの終点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項６】
請求項２に記載のナビゲーション装置において、
前記経路探索部は、リンクの始点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項７】
請求項１に記載のナビゲーション装置において、
前記中間経路は、複数のリンクから構成されており、
前記経路探索部は、それら複数のリンクの個々に対し、最短直線に平行な辺及び直交直線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を前記再探索要否判断用領域の面積として算出することを特徴とするナビゲーション装置。
【請求項８】
請求項７に記載のナビゲーション装置において、
前記経路探索部は、リンクの終点側の端点を通り前記最短直線に直交する直交直線と前記最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項９】
請求項７に記載のナビゲーション装置において、
前記経路探索部は、リンクの始点側の端点を通り前記最短直線に直交する直交直線と前記最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定することを特徴とするナビゲーション装置。
【請求項１０】
請求項１〜９のいずれか一項に記載のナビゲーション装置において、
前記経路探索部は、前記所定の基準値として、上位の階層にて探索した中間経路と最短直線との交点間の距離に基づいて定められる値を用いることを特徴とするナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を案内するナビゲーション装置に関する。
【背景技術】
【０００２】
一般に、ナビゲーション装置では、出発地から目的地までの経路を探索するために必要な地図情報は、道路の詳細度に応じた階層（レイヤ）にて記憶されている。上位の階層には、高速道、首都高速道路、有料道路、及び国道等の主要な道路の道路情報が記憶されており、下位の階層には、これら主要道路に加えて一般道路を含む全ての道路情報が記憶されている。ナビゲーション装置は、出発地から目的地までの経路探索を行なう際に、出発地近傍及び目的地近傍については、下位の階層にて詳細な経路探索を行なうとともに、出発地近傍と目的地近傍との間の中間地点については、上位の階層にて大雑把な経路探索を行なう。
【０００３】
このような一般的な技術では、中間地点において上位の階層で主要道路を通る経路を探索することから、出発地から目的地までの遠回りの経路を探索してしまい、その結果、遠回りの経路を案内してしまうことがある。
【０００４】
そこで、特許文献１に記載の技術では、ナビゲーション装置を搭載する車両の現在地を検出し、所定時間ごとに、あるいは、所定距離ごとに、現在地から目的地までの経路を探索することで、中間地点で遠回りの経路が探索されることを低減している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−１０７１６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１に記載の技術では、上位の階層にて探索した現在の経路（中間経路）よりも経路コストがより小さい経路が存在する可能性を判断することなく、所定時間ごとに、あるいは、所定距離ごとに下位の階層にて中間経路を探索する。そのため、より近い経路が存在する可能性がない場合には、上位の階層にて探索した中間経路と同一の中間経路が下位の階層にて探索されることになり、下位の階層にて経路探索を無駄に行なってしまったこととになる。
【０００７】
本発明は、上記実情に鑑みてなされたものであって、その目的は、下位の階層での経路の再探索をより適切に行なうことのできるナビゲーション装置を提供することにある。
【課題を解決するための手段】
【０００８】
こうした目的を達成するため、請求項１に記載の発明では、出発地を設定する出発地設定部と、目的地を設定する目的地設定部と、地図情報が道路の詳細度に応じた階層にて記憶されている地図情報記憶部と、出発地から目的地までの経路を、地図情報記憶部に記憶されている地図情報を用いて探索する経路探索部とを備えるナビゲーション装置において、経路探索部は、出発地近傍の経路である出発地近傍経路と、目的地近傍の経路である目的地近傍経路とを結ぶ経路である中間経路については、これら出発地近傍経路及び目的地近傍経路を探索する階層よりも道路の詳細度が低い上位の階層にて探索し、その探索した中間経路と現在地及び目的地を結ぶ最短直線とで囲まれる領域である再探索要否判断用領域の面積を算出し、再探索要否判断用領域の面積が所定の基準値以上である場合に、前回中間経路を探索した階層よりも道路の詳細度が高い下位の階層にて中間経路を再探索することを特徴とする。
【０００９】
最短直線と中間経路とで囲まれる領域である再探索要否判断用領域の面積が大きければ、上位の階層にて探索された中間経路よりもより経路コストが小さい中間経路の存在を期待することができる。ナビゲーション装置としての上記請求項１に記載の発明では、経路探索部は、再探索要否判断用領域の面積を算出し、再探索要否判断用領域の面積が所定の基準値以上である場合に、前回中間経路を探索した階層よりも道路の詳細度が高い下位の階層にて中間経路を再探索することから、上位の階層にて探索した中間経路よりもより経路コストの小さい近い経路が存在する可能性が高い場合に下位の階層にて中間経路を再探索することができるようなる。そして、ひいては、上位の階層にて探索した中間経路と同一の中間経路が下位の階層にて再探索されることが低減し、下位の階層での経路の再探索をより適切に行なうことができるようになる。
【００１０】
なお、上記請求項１に記載の構成では、再探索要否判断領域の面積を算出するにあたり、中間経路を近似する近似曲線を求め、この近似曲線及び最短直線によって囲まれる面積を積分にて算出してもよい。あるいは、請求項２に記載の発明のように、中間経路は、複数のリンクから構成されており、経路探索部は、それら複数のリンクの個々に対し、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積として算出してもよい。またあるいは、請求項７に記載の発明のように、中間経路は、複数のリンクから構成されており、経路探索部は、それら複数のリンクの個々に対し、最短直線に平行な辺及び直交直線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積として算出してもよい。近似曲線による算出方法によれば、近似曲線を求めるのに必要な演算負荷及び積分するのに必要な演算負荷が多いものの、請求項２あるいは請求項７に記載の算出方法によれば、リンクの個々に対して矩形を設定するため、演算負荷を軽減することができるようになる。
【００１１】
より具体的には、請求項２に記載の構成において、請求項３に記載の発明のように、経路探索部は、リンクの終点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定したり、請求項２に記載の構成において、請求項４に記載の発明のように、経路探索部は、リンクの始点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定するとよい。
【００１２】
あるいは、請求項２に記載の構成において、請求項５に記載の発明のように、経路探索部は、リンクの終点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定したり、請求項２に記載の構成において、請求項６に記載の発明のように、経路探索部は、リンクの始点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定するとよい。
【００１３】
またあるいは、請求項７に記載の構成において、請求項８に記載の発明のように、経路探索部は、リンクの終点側の端点を通り最短直線に直交する直交直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とする矩形を設定したり、請求項７に記載の構成において、請求項９に記載の発明のように、経路探索部は、リンクの始点側の端点を通り最短直線に直交する直交直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とする矩形を設定するとよい。
【００１４】
なお、上記請求項１〜９のいずれか一項に記載の構成において、請求項１０に記載の発明のように、経路探索部は、所定の基準値として、上位の階層で探索した中間経路と最短直線との交点間の距離に基づいて定められる値を用いるとよい。こうした所定の基準値としては、例えば、交点間の距離を一辺とする正方形の面積、交点間の距離を直径とする半円の面積、及び交点間の距離を一辺とする正三角形の面積等のように、交点間の距離を用いて定められる図形の面積を採用するとよい。
【図面の簡単な説明】
【００１５】
【図１】本発明に係るナビゲーション装置の一実施の形態について、その全体構成を示すブロック図である。
【図２】本実施の形態のナビゲーション装置において、上位のレイヤにて探索された中間経路と下位のレイヤにて再探索された中間経路とを併せて示す模式図である。
【図３】再探索要否判断用領域の面積を算出する算出方法を説明するための図である。
【図４】本実施の形態のナビゲーション装置によって実行される経路探索処理について、その処理手順の一例を示すフローチャートである。
【図５】再探索要否判断用領域の面積を算出する算出方法についてその変形例を説明するための図である。
【発明を実施するための形態】
【００１６】
以下、本発明に係るナビゲーション装置の一実施の形態について、図１〜図４を参照して説明する。
【００１７】
図１に示されるように、ナビゲーション装置１は、地図情報記憶部１０、ＧＰＳ受信部２０、操作入力部３０、制御部４０、表示部５０、及び音声出力部６０を備えて構成されている。制御部４０は、公知のＣＰＵ及び内蔵メモリを有して構成されるコンピュータであり、そのＣＰＵが内蔵メモリに記憶されているプログラムを実行することによって各種機能を実現している。以下の説明では、便宜上、制御部４０は、現在地検出部４１、目的地設定部４２、経路算出部４３、及び経路案内部４４を有するものとして説明する。なお、このナビゲーション装置１は、図示しない車両に搭載されている。
【００１８】
地図情報記憶部１０は、例えばハードディスクドライブ装置、ＤＶＤ（digital versatile disc）装置、ＣＤ(compact disc)装置、フラッシュメモリ等によって構成されており、地図情報が記憶されている。詳しくは、図２に示されるように、地図情報記憶部１０には、高速道、首都高速道路、有料道路、及び国道等の主要な道路の道路情報を含む上位のレイヤＨ０と、これら主要道路に加えて一般道路を含む全ての道路情報を含む下位のレイヤＨ１との２階層にて、地図情報が記憶されている。また、道路情報には、所要時間、距離、通行料金等のリンクコストが含まれており、現在地Ｐから目的地Ｔまでの経路Ｒの経路コストは経路Ｒを構成するリンクのリンクコストの総和である。そして、地図情報記憶部１０は、制御部４０に接続されており、この制御部４０によって地図情報等が適宜読み出される。なお、説明の便宜上、地図情報記憶部１０にはレイヤＨ０及びレイヤＨ１の２階層にて地図情報が記憶されているものとする。
【００１９】
ＧＰＳ受信部２０は、例えば図示しないＧＰＳアンテナを有して構成されており、これも図示しない複数のＧＰＳ衛星から発せられるＧＰＳ信号を受信する。また、ＧＰＳ受信部２０は、制御部４０に接続されており、この受信したＧＰＳ信号を制御部４０に出力する。
【００２０】
操作入力部３０は、例えばタッチパネルや音声入力装置等の適宜の入力装置にて構成されており、制御部４０に接続されている。当該ナビゲーション装置１のユーザはこの操作入力部３０を操作することで目的地を制御部４０へ入力することができる。
【００２１】
現在地検出部４１は、地図情報記憶部１０及びＧＰＳ受信部２０に接続されており、ＧＰＳ受信部２０によって受信されるＧＰＳ信号を取得するとともに、地図情報記憶部１０に記憶されている地図情報を読み出す。また、現在地検出部４１は、経路探索部４３に接続されており、これらＧＰＳ信号及び地図情報を利用して車両の現在地を検出する。また、車両の現在地の検出においては、当該ナビゲーション装置１を搭載する車両の走行軌跡と地図情報に基づいて周知のマップマッチングを実行することで、ＧＰＳ信号に基づいて決定する現在地の誤差を補正する。そして、このようにして検出した車両の現在地Ｓの情報である現在地情報を経路探索部４３に出力する。
【００２２】
目的地設定部４２は、操作入力部３０から入力された目的地に基づいて経路案内上の目的地を設定する。なお、操作入力部３０から入力される目的地に限らず、現在地と目的地の履歴から今回の目的地を推定して、その推定した目的地を経路案内上の目的地に設定してもよい。
【００２３】
経路探索部４３は、地図情報記憶部１０、目的地設定部４２、及び現在地検出部４１に接続されており、目的地設定部４２から目的地情報を取得すると、この取得した目的地情報、現在地検出部４１から入力された現在地情報、及び地図情報記憶部１０から取得した地図情報を利用して、車両の現在地Ｐから目的地Ｔまでの経路Ｒを算出する。また、経路探索部４３は経路案内部４４に接続されており、車両の現在地Ｐから目的地Ｔまでの経路Ｒを探索すると、その探索した経路Ｒの情報である経路情報を経路案内部４４に出力する。
【００２４】
なお、本実施の形態では、経路探索部４３は、車両の現在地Ｐを経路Ｒの出発地として設定し、車両の現在地Ｐから目的地Ｔまでの経路Ｒを探索していた。そのため、経路探索部４３は、特許請求の範囲に記載の経路探索部に相当することはもちろんのこと、出発地設定部にも相当する。車両の現在地Ｐを経路Ｒの出発地に設定するに限らず、上記操作入力部３０によって入力された地点を経路Ｒの出発地に設定してもよい。
【００２５】
経路案内部４４は、地図情報記憶部１０、経路探索部４３、例えばＬＣＤ等によって構成されている表示部５０、及び例えばスピーカ等によって構成される音声出力部６０に接続されている。経路案内部４４は、経路探索部４３から経路情報が入力されると、この入力された経路情報に基づいて地図画像を描画し、その描画した地図画像を表示部５０に表示させる。また、経路案内部４４は、音声出力部６０から音声案内あるいは警告音を出力してユーザに経路を案内する。
【００２６】
以下、図２及び図３を参照して、経路探索部４３及び経路案内部４４についてさらに説明する。
【００２７】
経路探索部４３は、現在地Ｐから目的地Ｔまでの経路Ｒのうち、現在地Ｐ近傍の経路である現在地近傍経路Ｒｐ及び目的地Ｔ近傍の経路である目的地近傍経路Ｒｔについては、レイヤＨ０よりも下位のレイヤ（図２では図示略）にて探索し、これら現在地近傍経路Ｒｐと目的地近傍経路Ｒｔとを結ぶ経路である中間経路Ｒｍ０については、上位のレイヤＨ０にて探索する。
【００２８】
ただし、現在地Ｐ及び目的地Ｔを結ぶ直線である最短直線Ｌと中間経路Ｒｍ０とで囲まれる領域である再探索要否判断用領域の面積Ｓ０が大きければ、上位のレイヤＨ０で探索された中間経路Ｒｍ０よりも経路コストのより小さい中間経路の存在を期待することができる。
【００２９】
そこで、経路探索部４３は、再探索要否判断用領域の面積Ｓ０が所定の基準値Ｓｔｈ０以上である場合には、中間経路Ｒｍ０を探索したレイヤＨ０よりも道路の詳細度が高い下位のレイヤＨ１にて中間経路Ｒｍ１を再探索する一方、再探索要否判断用領域の面積Ｓ０が所定の基準値Ｓｔｈ０に満たない場合には、中間経路Ｒｍ０を探索したレイヤＨ０よりも道路の詳細度が高い下位のレイヤＨ１にて中間経路Ｒｍ１を再探索しないこととした。
【００３０】
また、経路案内部４４は、下位のレイヤＨ１にて再探索された中間経路Ｒｍ１の経路コストが上位のレイヤＨ０にて探索された中間経路Ｒｍ０の経路コストよりも小さい場合には、下位のレイヤＨ１にて再探索された中間経路Ｒｍ１を表示部５０及び音声出力部６０にて案内することとし、下位のレイヤＨ１にて再探索された中間経路Ｒｍ１の経路コストが上位のレイヤＨ０にて探索された中間経路Ｒｍ０の経路コスト以上である場合には、上位のレイヤＨ０にて探索された中間経路Ｒｍ０を表示部５０及び音声出力部６０にて案内することとした。
【００３１】
なお、経路案内部４４は、所定の基準値Ｓｔｈ０として、中間経路Ｒｍ０と最短直線Ｌとの交点Ｃ１０及びＣ２０間の距離に基づいて定められる値を用いる。具体的には、経路探索部４３は、こうした所定の基準値Ｓｔｈ０として、例えば、交点Ｃ１０及びＣ２０間の距離交点間の距離を直径とする半円の面積を採用する。ただし、半円に限らず、交点Ｃ１０及びＣ２０間の距離を一辺とする正方形の面積、交点Ｃ１０及びＣ２０間の距離を一辺とする正三角形の面積等のように、交点Ｃ１０及びＣ２０間の距離を用いて定められる図形の面積を採用してもよい。
【００３２】
また、現在地近傍経路Ｒｐ及び目的地近傍経路Ｒｔを探索する領域を狭くすると、中間経路Ｒｍ０を探索する領域が広くなり、現在地Ｐから目的地Ｔまでの経路Ｒを探索するに必要な演算量が少なくなる。一方、現在地近傍経路Ｒｐ及び目的地近傍経路Ｒｔを探索する領域を広くすると、中間経路Ｒｍ０を探索する領域が狭くなり、現在地Ｐから目的地Ｔまでの経路Ｒを探索するに必要な演算量が多くなる。そのため、現在地近傍及び目的地近傍の範囲については、制御部４０を構成するＣＰＵの演算能力に応じて予め定められている。ちなみに、本実施の形態では、現在地近傍、すなわち出発地近傍として、現在地（すなわち出発地）を中心として所定距離（例えば「１０ｋｍ」等）までの領域を採用しており、目的地近傍として、目的地を中心として所定距離（例えば「１０ｋｍ」等）までの領域を採用している。これに限らず、他に例えば、現在地近傍、すなわち出発地近傍として、現在地を中心として現在地から目的地までの直線距離の所定分の１（例えば「１／１０」等）までの領域を採用してもよく、目的地近傍として、目的地を中心として現在地から目的地までの直線距離の所定分の１（例えば「１／１０」等）までの領域を採用してもよい。
【００３３】
図３では、中間経路Ｒｍ０と最短直線Ｌとの交点Ｃ１０を原点とし、緯度及び経度をそれぞれＸ軸及びＹ軸とする直交座標系において、レイヤＨ０にて探索された中間経路Ｒｍ０は、リンクｌ１〜ｌ１２の計「１２個」のリンクで構成されている。この場合における経路探索部４３による再探索要否判断用領域の面積Ｓ０の算出方法について詳述する。
【００３４】
まず、経路探索部４３は、中間経路Ｒｍ０と最短直線Ｌとの交点Ｃ１０及びＣ２０を算出する。ここで、交点Ｃ１０及びＣ２０は、最短直線Ｌを跨ぐリンクの端点とする。
【００３５】
次に、経路探索部４３は、交点Ｃ１０及びＣ２０間を結ぶ線分Ｃ１０−Ｃ２０と中間経路Ｒｍ０とで囲まれる再探索要否判断用領域の面積Ｓ０を算出する。具体的には、経路探索部４３は、レイヤＨ０にて探索された中間経路Ｒｍ０を構成するリンクｌ１〜ｌ１２の個々に対して矩形Ａ１〜Ａ１２を設定し、それら設定した矩形Ａ１〜Ａ１２の面積の総和を再探索要否判断用領域の面積Ｓ０として算出する。
【００３６】
説明の便宜上、リンクｌ５に対して矩形Ａ５を設定する場合を説明すると、経路探索部４３は、リンクｌ５の終点側の端点ｅ５ｔから経線に平行な平行直線を引いて最短直線Ｌとの交点ｉ５ｔを算出し、この交点ｉ５ｔとリンクｌ５の始点側の端点ｅ５ｐとを結ぶ直線を対角線とする矩形Ａ５を設定する。なお、図３では、リンクｌ８〜ｌ１２が経線と平行になることから、経路探索部４３は、リンクｌ８〜ｌ１２に対し矩形Ａ８〜Ａ１２を設定せず、リンクｌ１〜ｌ４，ｌ６〜ｌ７に対して、リンクｌ５と同様に矩形Ａ１〜Ａ４，Ａ６〜Ａ７を設定する。そして、経路探索部４３は、矩形Ａ１〜Ａ７を設定すると、それら設定した矩形Ａ１〜Ａ７の面積の総和を再探索要否判断用領域の面積Ｓ０として算出する。
【００３７】
なお、本実施の形態では、経路探索部４３は、リンクｌ５の終点側の端点ｅ５ｔから経線に平行な平行直線を引いて最短直線Ｌとの交点ｉ５ｔを算出し、この交点ｉ５ｔとリンクｌ５の始点側の端点ｅ５ｐとを結ぶ直線を対角線とする矩形Ａ５を設定していたが、これに限らない。経路探索部４３は、リンクｌ５の始点側の端点ｅ５ｐから経線に平行な平行直線を引いて最短直線Ｌとの交点ｉ５ｐを算出し、この交点ｉ５ｐとリンクｌ５の終点側の端点ｅ５ｔとを結ぶ直線を対角線とする矩形Ａ５を設定してもよい。
【００３８】
また、経路探索部４３は、リンクｌ５の始点側の端点ｅ５ｐと、上記交点ｉ５ｐを通る緯線に平行な直線とリンクｌ５の終点側の端点ｅ５ｔを通る経線に平行な平行直線との図示しない交点とを対角線とする矩形Ａ５を設定してもよい。また、経路探索部４３は、リンクｌ５の終点側の端点ｅ５ｔと、上記交点ｉ５ｔを通る緯線に平行な直線とリンクｌ５の始点側の端点ｅ５ｐを通る経線に平行な平行直線との交点（図示せず）とを対角線とする矩形Ａ５を設定してもよい。
【００３９】
以上のように構成されたナビゲーション装置１は図４に示す経路探索処理Ｓ１を実行する。なお、ここまで、説明の便宜上、地図情報記憶部１０にはレイヤＨ０及びレイヤＨ１の２階層にて地図情報が記憶されているものとしたが、以下では、２階層に限らず複数の階層にて地図情報が記憶されているものとする。中間経路Ｒｍｎ、交点Ｃ１ｎ、交点Ｃ２ｎ、面積Ｓｎ、基準値Ｓｔｈｎに付した添え字ｎは、レイヤＨｎにて算出されたことを意味する。
【００４０】
制御部４０は、現在地Ｐを検出し、目的地Ｔが設定されると、この経路探索処理Ｓ１を実行開始する。経路探索処理Ｓ１を実行開始すると、ステップＳ１１の処理として、現在地情報、目的地情報、及び地図情報を利用して、車両の現在地Ｐから目的地Ｔまでの経路Ｒを算出する。このとき、経路探索部４３は、現在地Ｐから目的地Ｔまでの経路Ｒのうち、現在地近傍の経路である現在地近傍経路Ｒｐ及び目的地近傍の経路である目的地近傍経路Ｒｔについては、レイヤＨ０よりも下位のレイヤにて探索し、これら現在地近傍経路Ｒｐと目的地近傍経路Ｒｔとを結ぶ経路である中間経路Ｒｍ０については、上位のレイヤＨ０にて探索する。
【００４１】
現在地Ｐから目的地Ｔまでの経路Ｒを算出すると、制御部４０は、続くステップＳ１２の処理として、現在地Ｐと目的地Ｔとを結ぶ直線である最短直線Ｌを算出する。
【００４２】
ステップＳ１２の処理を終えると、制御部４０は、続くステップＳ１３の処理として、中間経路Ｒｍｎと最短直線Ｌとの交点Ｃ１ｎ及びＣ２ｎを算出し、続くステップＳ１４の処理として、線分Ｃ１ｎ−Ｃ２ｎと中間経路Ｒｍｎとで囲まれる面積Ｓｎを算出する。具体的には、制御部４０は、レイヤＨｎにて探索された中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの終点側の端点から経線に平行な平行直線を引いて最短直線Ｌとの交点を算出し、この交点とリンクの始点側の端点とを対角線とする矩形を設定する。そして、経路探索部４３は、それら設定した矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出する。
【００４３】
ステップＳ１４の処理を終えると、制御部４０は、続くステップＳ１５の判断処理に移行し、ステップＳ１４の処理で算出した面積Ｓｎが所定の基準値Ｓｔｈｎ以上であるか否かを判断する。なお、本実施の形態では、所定の基準値Ｓｔｈｎは、交点Ｃ１ｎ及びＣ２ｎ間の距離交点間の距離を直径とする半円の面積である。
【００４４】
ここで、面積Ｓｎが所定の基準値Ｓｔｈｎ以上であると判断しなかった場合（ステップＳ１５の判断処理で「Ｎｏ」）、前回上位のレイヤＨｎで探索した中間経路Ｒｍｎよりも経路コストの小さい中間経路Ｒｍｎ＋１が下位のレイヤＨｎ＋１に存在する可能性は低い。そのため、制御部４０は、この経路探索処理Ｓ１を終了する。
【００４５】
一方、ステップＳ１４の処理で算出した面積Ｓｎが所定の基準値Ｓｔｈｎ以上であると判断した場合（ステップＳ１５の判断処理で「Ｙｅｓ」）、前回上位のレイヤＨｎで探索した中間経路Ｒｍｎよりも経路コストの小さい中間経路Ｒｍｎ＋１が下位のレイヤＨｎ＋１に存在する可能性がある。そのため、制御部４０は、続くステップＳ１６の判断処理に移行する。
【００４６】
ステップＳ１６の判断処理に移行すると、制御部４０は、前回中間経路Ｒｍｎを探索したレイヤＨｎよりも下位のレイヤＨｎ＋１が地図情報記憶部１０に記憶されているか否かを判断する。ここで、下位のレイヤＨｎ＋１が記憶されていないと判断した場合（ステップＳ１６の判断処理で「Ｎｏ」）、下位のレイヤＨｎ＋１で中間経路Ｒｍｎ＋１を探索することができないことから、制御部４０は、この経路探索処理Ｓ１を終了する。
【００４７】
一方、下位のレイヤＨｎ＋１が記憶されていると判断した場合（ステップＳ１６の判断処理で「Ｙｅｓ」）、制御部４０は、続くステップＳ１７の処理に移行し、下位のレイヤＨｎ＋１で中間経路Ｒｍｎ＋１を再探索する。
【００４８】
ステップＳ１７の処理を終えると、続くステップＳ１８の判断処理に移行し、制御部４０は、今回下位のレイヤＨｎ＋１で再探索した中間経路Ｒｍｎ＋１の経路コストが前回上位のレイヤＨｎで探索した中間経路Ｒｍｎの経路コストよりも小さいか否かを判断する。ここで、今回下位のレイヤＨｎ＋１で再探索した中間経路Ｒｍｎ＋１の経路コストが前回上位のレイヤＨｎで探索した中間経路Ｒｍｎの経路コストよりも小さいと判断しなかった場合（ステップＳ１８の判断処理で「Ｎｏ」）、今回下位のレイヤＨｎ＋１で再探索した中間経路Ｒｍｎ＋１の経路コストが前回上位のレイヤＨｎで探索した中間経路Ｒｍｎの経路コスト以上であることから、制御部４０は、この経路探索処理Ｓ１を終了する。
【００４９】
一方、今回下位のレイヤＨｎ＋１で再探索した中間経路Ｒｍｎ＋１の経路コストが前回上位のレイヤＨｎで探索した中間経路Ｒｎの経路コストよりも小さいと判断した場合（ステップＳ１８の判断処理で「Ｙｅｓ」）、制御部４０は、続くステップＳ１９の処理に移行して、前回上位のレイヤＨｎで探索した中間経路Ｒｍｎを、今回下位のレイヤＨｎ＋１で再探索した中間経路Ｒｍｎ＋１に替える。そして、制御部４０は、先のステップＳ１３の判断処理に移行し、ステップＳ１３〜Ｓ１９の一連の処理を再度実行する。このように、経路探索部４３は、中間経路Ｒｍｎを逐次探索する。
【００５０】
以上説明した本実施の形態では、経路探索部４３は、上位のレイヤＨｎで探索した中間経路Ｒｍｎと最短直線Ｌとで囲まれる領域である再探索要否判断用領域の面積Ｓｎを算出し、再探索要否判断用領域の面積Ｓｎが所定の基準値Ｓｔｈｎ以上である場合に、下位のレイヤＨｎ＋１にて中間経路Ｒｍｎ＋１を再探索することとした。また、経路案内部４４は、下位のレイヤＨｎ＋１にて再探索された中間経路Ｒｍｎ＋１の経路コストの方が上位のレイヤＨｎにて探索された中間経路Ｒｍｎよりも経路コストが小さい場合に、下位のレイヤＨｎ＋１にて再探索された中間経路Ｒｍｎ＋１を案内することとした。上位のレイヤＨｎで探索した中間経路Ｒｍｎよりもより経路コストの小さい近い中間経路が存在する可能性が高い場合に下位のレイヤＨｎ＋１にて中間経路Ｒｍｎ＋１を再探索することができるようなる。そして、ひいては、上位のレイヤＨｎで探索した中間経路Ｒｍｎと同一の中間経路Ｒｍｎ＋１が下位のレイヤＨｎ＋１で再探索されることが低減し、下位のレイヤＨｎ＋１での経路の再探索をより適切に行なうことができるようになる。
【００５１】
また、本実施の形態では、経路探索部４３は、中間経路Ｒｍｎを構成する複数のリンクの個々に対して矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出した。この算出方法によれば、中間経路Ｒｍｎを近似する近似曲線を求め、この近似曲線及び最短直線Ｌによって囲まれる面積を積分にて算出する算出方法よりも、演算負荷を低減することができるようになる。
【００５２】
なお、本発明に係るナビゲーション装置は、上記実施の形態にて例示した構成に限定されるものではなく、本発明の趣旨を逸脱しない範囲において、種々に変形して実施することが可能である。すなわち、上記実施の形態を適宜変更した例えば次の形態として実施することもできる。
【００５３】
上記実施の形態では、経路探索部４３は、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの終点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とするとともに、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出していたが、これに限らない。
【００５４】
他に例えば、経路探索部４３は、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの始点側の端点を通り経線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とするとともに、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出してもよい。
【００５５】
あるいは、経路探索部３１は、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの終点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの始点側の端点とを結ぶ線を対角線とするとともに、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出してもよい。
【００５６】
またあるいは、経路探索部３１は、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの始点側の端点を通り緯線に平行な平行直線と最短直線との交点と、リンクの終点側の端点とを結ぶ線を対角線とするとともに、経線に平行な辺及び緯線に平行な辺を有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出してもよい。
【００５７】
また、他に例えば、経路探索部４３は、中間経路Ｒｍと最短直線Ｌとの交点Ｃ１ｎを原点とし、緯線及び経線をそれぞれＸ軸及びＹ軸とする直交座標系を、経線と最短直線Ｌとがなす角θだけ回転させた直交座標系において、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの始点側の端点を通り最短直線Ｌに直交する直交直線と最短直線Ｌとの交点と、リンクの終点側の端点とを結ぶ直線を対角線とするとともに、最短直線Ｌに平行な辺と直交直線に平行な辺とを有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出してもよい。
【００５８】
図２に対応する図として示す図５を参照して詳しく説明する。この図５に示されるように、経路探索部４３は、レイヤＨ０にて探索された中間経路Ｒｍ０を構成するリンクｌ１〜ｌ１２の個々に対して矩形Ａ１〜Ａ１２を設定し、それら設定した矩形Ａ１〜Ａ１２の面積の総和を再探索要否判断用領域の面積Ｓ０として算出する。
【００５９】
リンクｌ５に対して矩形Ａ５を設定する場合を説明すると、経路探索部４３は、リンクｌ５の始点側の端点ｅ５ｐから最短直線Ｌに直交する直交直線を引いて最短直線Ｌとの交点ｉ５ｐを算出し、この交点ｉ５ｐとリンクｌ５の終点側の端点ｅ５ｔとを結ぶ直線を対角線とし、最短直線Ｌに平行な辺と最短直線Ｌｎｉ直交する辺とを有する矩形Ａ５を設定する。なお、リンクｌ５の始点側の端点ｅ５ｐの座標が（ａ、ｂ）であり、終点側の端点ｅ５ｔの座標が（ａ’，ｂ’）である場合、矩形Ａ５の面積は「（ａ’−ａ）×ｂ’」という簡単な式で算出することができる。経路探索部４３は、リンクｌ１〜ｌ４，ｌ６〜ｌ１２に対して、リンクｌ５と同様に矩形Ａ１〜Ａ４，Ａ６〜Ａ１２を設定すると、それら設定した矩形Ａ１〜Ａ１２の面積の総和を再探索要否判断用領域の面積Ｓ０として算出する。
【００６０】
また、経路探索部４３は、中間経路Ｒｍと最短直線Ｌとの交点Ｃ１ｎを原点とし、緯線及び経線をそれぞれＸ軸及びＹ軸とする直交座標系を、経線と最短直線Ｌとがなす角θだけ回転させた直交座標系において、中間経路Ｒｍｎを構成する複数のリンクの個々に対し、リンクの始点側の端点を通り最短直線Ｌに直交する直交直線と最短直線Ｌとの交点と、リンクの終点側の端点とを結ぶ直線を対角線とするとともに、最短直線Ｌに平行な辺と直交直線に平行な辺とを有する矩形を設定し、それら設定された矩形の面積の総和を再探索要否判断用領域の面積Ｓｎとして算出してもよい。
【符号の説明】
【００６１】
１…ナビゲーション装置、１０…地図情報記憶部、２０…ＧＰＳ受信部、３０…操作入力部、４０…制御部、４１…現在地検出部、４２…目的地設定部、４３…経路探索部、４４…経路案内部、５０…表示部、６０…音声出力部
【図１】
2011191065.tif 000003
【図２】
2011191065.tif 000004
【図３】
2011191065.tif 000005
【図４】
2011191065.tif 000006
【図５】
2011191065.tif 000007