ナビゲーション装置及びルート探索方法
【課題】階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供する。
【解決手段】出発地点を含むセルＡにおいては、セルＡを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートをセルＡにおけるルートに設定する。その退出地点を進入地点とするセルＢにおいては、進入地点が代表ルートの入口に位置しているため、その代表ルートの出口を退出地点に設定し、その代表ルートをセルＢにおけるルートに設定する。そして、セルＢと同様の処理をセルＣ〜Ｆにおいても行う。目的地点を含むセルＧにおいては、進入地点から目的地点までのルートを探索して、探索したルートをセルＧにおけるルートに設定する。
【解決手段】出発地点を含むセルＡにおいては、セルＡを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートをセルＡにおけるルートに設定する。その退出地点を進入地点とするセルＢにおいては、進入地点が代表ルートの入口に位置しているため、その代表ルートの出口を退出地点に設定し、その代表ルートをセルＢにおけるルートに設定する。そして、セルＢと同様の処理をセルＣ〜Ｆにおいても行う。目的地点を含むセルＧにおいては、進入地点から目的地点までのルートを探索して、探索したルートをセルＧにおけるルートに設定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地点から目的地点までのルートを探索するための技術に関する。
【背景技術】
【０００２】
従来、ナビゲーション装置では、地図データを用いて出発地点から目的地点までのルート（経路）を探索する技術が利用されている。ルート探索の基本的な手法は、出発地点から目的地点までのルートとして設定し得るすべてのルートの中から、最も適切な（例えば走行距離が最短となる）ルートを選択するという総当たりの手法である。ただし、この手法では、ルート探索のための計算量が膨大となり、処理時間が長くなってしまう。そこで、ルート探索に要する時間を短縮するための手法が提案されている。
【０００３】
例えば特許文献１には、上位レベルほどリンク数が少なくなるように階層化された構造の地図データを用いて、ルート探索に要する時間を短縮する構成のナビゲーション装置について記載されている。具体的には、このナビゲーション装置が用いる地図データは、基準レベルの道路リンク情報、基準レベルの道路リンク情報を用いてレベル格上げ処理を行って得られた第１上位レベルのリンク情報、第１上位レベルのリンク情報を用いてレベル格上げ処理を行って得られた複数の第２上位レベルのリンク情報といった形の階層構造を有する。なお、ここでいうレベル格上げ処理とは、探索枝数が規定数以上のリンクを上位レベルのリンクとして格上げすることにより、上位レベルのリンクを決定する処理のことである。
【０００４】
そして、特許文献１に記載のナビゲーション装置は、出発地点と目的地点との間の直線距離を算出し、算出した直線距離に基づいて、ルート探索に使用するリンクが属する第１レベル以外の上位レベルを決定する。その後、ナビゲーション装置は、基準レベルにおいて第１上位レベルに移行可能なリンクまでのルートを探索し、第１上位レベルにおいて、先に決定した更に上位のレベルに移行可能なリンクまでのルートを探索して、その上位レベルのリンク情報を用いてルート探索を行う。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２９２９８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述した特許文献１に記載のルート探索の手法は、階層構造に整備された地図データを必要とするものであり、地図データが階層構造に整備されていない場合には適用することができなかった。
【０００７】
本発明は、こうした問題にかんがみてなされたものであり、階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供することを目的としている。
【課題を解決するための手段】
【０００８】
請求項１に記載のナビゲーション装置は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する区画ルート探索手段を備える。具体的には、この区画ルート探索手段は、出発ルート探索手段、中間ルート探索手段及び目的ルート探索手段を備える。
【０００９】
出発ルート探索手段は、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索手段は、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索手段は、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【００１０】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索手段は、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【００１１】
このような構成によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【００１２】
ここで、代表ルートの出口が複数存在する場合には、請求項２に記載のように、目的地点の位置に応じて選択した出口を退出地点に設定するようにしてもよい。このようにすれば、目的地点に応じた適切なルートを設定することが可能となる。
【００１３】
具体的には、請求項３に記載のように、代表ルートの出口は、区画の外縁を形成する複数の辺のいずれかに位置し、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点の方角に応じた適切なルートを設定することが可能となる。
【００１４】
また、請求項４に記載のように、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点へ向かった適切なルートを設定することができる。
【００１５】
また、請求項５に記載のように、出発ルート探索手段は、出発区画が代表設定区画である場合には、代表ルートの出口を退出地点に設定するようにしてもよい。つまり、出発地点から代表ルートの出口までのルートを探索するのである。このようにすれば、出口があらかじめ設定されているため、総当たりの手法でルートを探索するとしても探索の手間や時間を大幅に短縮することができる。しかも、出発区画の退出地点を進入地点とする中間区画において、進入地点を代表ルートの入口に位置させることができるため、以降の区画における探索の処理負荷を抑えることができる。
【００１６】
また、請求項６に記載のように、代替ルート探索手段及び差替手段を更に備え、代替ルート探索手段が、出発地点から目的地点までのルートを区画ルート探索手段とは異なる方法で探索し、差替手段が、区画ルート探索手段により探索された第１のルートを、代替ルート探索手段により探索された第２のルートに差し替えるようにしてもよい。このようにすれば、第２のルートと比較して短時間で探索可能な第１のルートを最初に提示し、その後に第１のルートと比較して信頼性の高い第２のルートに差し替えるといったことが可能となる。
【００１７】
ただし、第１のルートが第２のルートに差し替えられることをユーザが望まない場合も考えられる。そこで、請求項７に記載のように、差替手段は、第１のルートを第２のルートに差し替えるか否かをユーザに選択させるようにしてもよい。このようにすれば、ユーザの意に反して第１のルートが第２のルートに差し替えられてしまうことを防ぐことができる。
【００１８】
また、代表ルートに代えて第２のルートが走行される場合には、その第２のルートを代表ルートとした方がユーザにとって好ましい場合もある。そこで、請求項８に記載のように、登録手段を更に備え、この登録手段が、代表ルートと異なる第２のルートが走行されたことを条件として、第２のルートを代表ルートとして登録するようにしてもよい。このようにすれば、代表ルートをユーザに応じた適切なルートに更新することができる。
【００１９】
次に、請求項９に記載のルート探索方法は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する方法であって、出発ルート探索ステップ、中間ルート探索ステップ及び目的ルート探索ステップを備える。
【００２０】
出発ルート探索ステップでは、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索ステップでは、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索ステップでは、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【００２１】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索ステップでは、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【００２２】
このような方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【図面の簡単な説明】
【００２３】
【図１】実施形態のナビゲーション装置の概略構成を示すブロック図である。
【図２】複数のセルに分割された地図を示す図である。
【図３】（Ａ）はセルの一例を示す図、（Ｂ）はセルにおける代表ルートの入口と出口との対応関係を示す図である。
【図４】ルート探索処理のフローチャートである。
【図５】ルート設定処理のフローチャートである。
【図６】（Ａ）は対象セルへの進入地点が代表ルートの入口に位置している状態を示す図、（Ｂ）は対象セルへの進入地点が代表ルートの入口に位置していない状態を示す図である。
【図７】ルート差替処理のフローチャートである。
【図８】代表ルート更新処理のフローチャートである。
【発明を実施するための形態】
【００２４】
以下、本発明が適用された実施形態について、図面を用いて説明する。
図１は、実施形態のナビゲーション装置の概略構成を示すブロック図である。
このナビゲーション装置は、車両に搭載されて用いられるものであり、位置検出部１１、地図データ記憶部１５、操作部１６、表示部１７、音声出力部１８、制御部１９などを備える。
【００２５】
位置検出部１１は、ＧＰＳ（Global Positioning System）用の人工衛星からの送信信号を受信し、車両の位置座標や高度を検出するＧＰＳ受信機１２と、車両に加えられる回転運動の角速度に応じた検出信号を出力するジャイロスコープ１３と、車両の走行距離を出力する距離センサ１４とを備える。そして、これらの各センサ１２〜１４の出力信号に基づいて制御部１９が、現在位置、方位、速度等を算出する。
【００２６】
地図データ記憶部１５は、地図データを記憶し、その各種データを制御部１９に入力する。地図データ記憶部１５に格納されるデータは、交差点等の特定地点に対応するノード及びノード間を接続するリンクによって道路の接続状況を示す道路データや、地図上の施設に関する施設データ、ルート案内を行うための案内データなどを含む各種データである。
【００２７】
操作部１６は、ユーザからの各種指示（各種の設定や機能実行の指示）を入力するためのものであり、表示部１７の表示画面上に配置されたタッチパネルや、メカニカルなキースイッチ等が用いられる。
【００２８】
表示部１７は、液晶ディスプレイ等の表示画面を有するものであり、制御部１９からの映像信号の入力に応じて各種画像を表示画面に表示する。この表示部１７は、地図画像の表示や、出発地点から目的地点までの誘導ルート、車両の現在位置を示すマーク、その他の案内情報等の表示に用いられる。
【００２９】
音声出力部１８は、各種情報を音声にてユーザに報知する。これによって、表示部１７による表示と音声出力部１８による音声出力との両方でユーザに対して各種ルート案内を行うことができる。
【００３０】
制御部１９は、ＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスライン等からなる周知のマイクロコンピュータを中心に構成されている。そして、ＣＰＵは、ＲＯＭに記憶されているプログラムに従い、位置検出部１１、地図データ記憶部１５、操作部１６から入力された各種情報に基づき、各種処理を実行する。
【００３１】
具体的には、制御部１９は、地図データ記憶部１５に記憶されている地図データを用いて、現在位置（出発地点）から目的地点までのルートを探索するルート探索処理を実行する。本実施形態で用いられる地図データは、図２に示すように、複数のセル（一定サイズの正方形の区画）に分割されており、制御部１９は、出発地点から目的地点までのルートを、次の（１）〜（３）の手順でセルごとに探索する。
【００３２】
（１）出発地点を含むセル（以下「出発セル」ともいう。）において、その出発セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その出発地点から、設定した退出地点までのルートを探索し、探索したルートをその出発セルにおけるルートに設定する。
【００３３】
（２）出発地点及び目的地点を含まないセルであって、他のセルで設定された退出地点を進入地点とするセル（以下「中間セル」ともいう。）において、その中間セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その進入地点から、設定した退出地点までのルートを探索し、探索したルートをその中間セルにおけるルートに設定する。
【００３４】
（３）目的地点を含むセルであって他のセルで設定された退出地点を進入地点とするセル（以下「目的セル」ともいう。）において、その進入地点から目的地点までのルートを探索し、探索したルートをその目的セルにおけるルートに設定する。
【００３５】
このように制御部１９は、１セル分の地図データを順に読み込み、セルごとにルートを探索することで、出発地点から目的地点までのルートを探索する。ただし、セル内において総当たりの手法でルートを探索すると、ルート探索に要する時間が長くなる。特に、すべてのセルにおいて総当たりの手法でルートを探索すると、セル数に比例して探索時間が増大してしまう。
【００３６】
そこで、本実施形態では、図２に示すように、各セルにおいて、例えば幹線道路などのように、走行案内するルートに適した一部の道路が、代表ルート（セルの拡大図において太線で示されたルート）としてあらかじめ設定されている。各セルにおける代表ルートの入口及び出口は、セルの外縁を形成する４つの辺（北側、西側、南側及び東側の各方角に対応する辺）のいずれかに位置し、あるセルにおける代表ルートの出口は、その出口が位置する辺で隣接する他のセルにおける代表ルートの入口となる。
【００３７】
また、代表ルートの設定されたセル（以下「代表設定セル」ともいう。）には、図３（Ａ），（Ｂ）に示すように、セルにおける各方角の辺を基準とした代表ルートの入口と出口との対応関係が記憶されている。例えば、図３（Ａ）に示すセルの場合、代表ルートの入口又は出口となり得る箇所が、東側、南側及び北側の３箇所に存在する。そして、このセルでは、図３（Ｂ）に示すように、東側を入口とした場合の出口が南側の１箇所、南側を入口とした場合の出口が東側及び北側の２箇所、北側を入口とした場合の出口が南側の１箇所に設定され、かつそれら出口に至るためのルート(代表ルート)がそれぞれ一意に定義されている。なお、東側を入口とした場合の出口を北側及び南側の２箇所に設定してもよく、同様に、北側を入口とした場合の出口を東側及び南側の２箇所に設定してもよい。
【００３８】
このように、代表設定セルでは、代表ルートの入口と出口との対応関係が設定されているため、代表ルートの入口に対応する出口を選択するだけで、入口から出口へ至るルートを考慮することなく（最短ルートであるか否かは問わず）、ルートを設定することが可能となる。そして、セルにおける代表ルートの出口を、隣接するセルにおける代表ルートの入口として、代表ルートを順につないでいくことにより、短時間でルートを設定することができる。
【００３９】
ここで、このような処理を実現するために制御部１９が実行する具体的処理内容について説明する。図４は、制御部１９が実行するルート探索処理のフローチャートである。このルート探索処理は、ルート探索を開始する操作がユーザにより操作部１６で行われることにより開始される。
【００４０】
制御部１９は、ルート探索処理を開始すると、まずＳ１０１で、目的地点をユーザに設定させる。続いてＳ１０２で、階層構造の地図データが使用可能であるか否かを判定する。すなわち、地図データ記憶部１５に記憶される地図データが、階層構造に整備されたものであるか否かを判定する。例えば、ナビゲーション装置が複数の国で使用されるものであり、国によって地図データの構造が異なるような場合に、このような判定が有効となる。なお、階層構造に整備されていない地図データを用いることが決まっている場合には、Ｓ１０２の判定処理を行うことなくＳ１０４へ移行するようにしてもよい。
【００４１】
そして、Ｓ１０２で、階層構造の地図データが使用可能であると判定した場合には、Ｓ１０３へ移行して、階層構造の地図データを使用してルートを設定した後、Ｓ１１１へ移行する。この場合のルート設定は、従来技術をそのまま適用すればよいため、具体的な説明は省略する。
【００４２】
一方、Ｓ１０２で、階層構造の地図データが使用可能でないと判定した場合には、前述したＳ１０３の処理に代えて、Ｓ１０４〜Ｓ１１０の処理を実行する。すなわち、まずＳ１０４で、出発地点（通常は現在位置）を含むセルを処理対象のセル（以下「対象セル」という。）に設定する。続いてＳ１０５では、対象セルのルート設定に代表ルートを使用可能である（対象セルに代表ルートが設定されている）か否かを判定する。このＳ１０５で、対象セルのルート設定に代表ルートを使用可能であると判定した場合には、Ｓ１０６へ移行して、代表ルートを使用してルートを設定するためのルート設定処理を実行した後、Ｓ１０８へ移行する。
【００４３】
ここで、図４のＳ１０６で実行されるルート設定処理の詳細について図５のフローチャートを用いて説明する。制御部１９は、ルート設定処理を開始すると、まずＳ２０１で、対象セルへの進入地点が、その対象セルに設定されている代表ルートの入口に位置しているか否かを判定する。なお、対象セルへの進入地点とは、前回の対象セルの退出地点（後述）のことである。ただし、対象セルに出発地点が含まれる場合には、その出発地点を進入地点として処理を行う。
【００４４】
そして、図６（Ａ）に例示するように、Ｓ２０１で、対象セルへの進入地点が代表ルートの入口に位置していると判定した場合には、Ｓ２０２へ移行し、対象セルを基準とした目的地点の方角を判定する。本実施形態では、対象セルの中心位置を基準とした目的地点の方角が、北東〜北西（北東含む）、北西〜南西（北西含む）、南西〜南東（南西含む）、南東〜北東（南東含む）の４つの範囲のいずれに分類されるかを判定する。
【００４５】
そして、Ｓ２０２で目的地点の方角が北東〜北西（北東含む）に分類されると判定した場合には、Ｓ２０３へ移行し、進入地点を入口とする代表ルートの出口のうち、対象セルにおける北側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４６】
また、Ｓ２０２で目的地点の方角が北西〜南西（北西含む）に分類されると判定した場合には、Ｓ２０４へ移行し、代表ルートの出口のうち、対象セルにおける西側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４７】
また、Ｓ２０２で目的地点の方角が南西〜南東（南西含む）に分類されると判定した場合には、Ｓ２０５へ移行し、代表ルートの出口のうち、対象セルにおける南側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４８】
また、Ｓ２０２で目的地点の方角が南東〜北東（南東含む）に分類されると判定した場合には、Ｓ２０６へ移行し、代表ルートの出口のうち、対象セルにおける東側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４９】
Ｓ２０７では、進入地点から退出地点までの代表ルートを、対象セルのルートに設定し、図５のルート設定処理を終了する。このように、進入地点が代表ルートの入口に位置する場合には、ルート計算を行うことなく、目的地点の方角に応じた出口を選択するだけでルートが設定される。
【００５０】
なお、目的地点の方角に代表ルートの出口が存在しない場合には、他の方角の出口の中から、目的地点の方角に近い方角の出口を選択するようにしてもよい。また、対象セルへの進入地点の方角から遠い方角の出口を選択するようにしてもよい。例えば、対象セルへの進入地点が西側、目的地点が南の方角であって、対象セルにおける南側の辺に出口が設定されていない場合には、東側の辺に設定された出口（目的地点の方角に近い方角であって、進入地点の方角から遠い方角）を優先的に選択する。
【００５１】
また、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、代表ルートの出口の数が同じ方角に２つ以上存在するような場合にも、目的地点の位置に応じた１つの出口として選択することができるため、目的地点へ向かった適切なルートを設定することができる。
【００５２】
一方、図６（Ｂ）に例示するように、Ｓ２０１で、対象セルへの進入地点が代表ルートの入口に位置していないと判定した場合には、Ｓ２０８へ移行し、総当たりの手法でルート探索を行い、対象セルのルートを設定した後、図５のルート設定処理を終了する。なお、この場合の退出地点も、目的地点の位置に応じて（例えば目的地点との距離が最も近い出口などに）設定される。特に、この退出地点を代表ルートの出口から選択するようにすれば、次回の対象セルの進入地点を代表ルートの入口に位置させることができる。つまり、進入地点から対象セルの代表ルートの出口までのルート探索を行うのである。こうすれば、出口があらかじめ設定されているため、総当たりの手法でルート探索するとしても探索の手間、時間を大幅に短縮することができる。とりわけ対象セルが出発セルである場合、すなわち進入地点が出発地点（通常は現在位置）である場合、この方法をとれば、それ以後の探索の手間、時間を容易に節約できる。
【００５３】
図４に戻り、Ｓ１０５で対象セルのルート設定に代表ルートを使用可能でないと判定した場合には、Ｓ１０７へ移行し、前述したＳ２０８と同様、総当たりの探索処理を実施して対象セルのルートを設定した後、Ｓ１０８へ移行する。
【００５４】
Ｓ１０８では、設定したルートの出口（退出地点）が位置する辺で現在の対象セルに隣接するセルを、次の対象セルに設定する。続いてＳ１０９では、設定した対象セルに目的地点が含まれているか否かを判定し、含まれていない（中間セルである）と判定した場合には、Ｓ１０５へ戻り、前述した処理（Ｓ１０５〜Ｓ１０８）を行う。
【００５５】
一方、Ｓ１０９で対象セルに目的地点が含まれている（目的セルである）と判定した場合には、Ｓ１１０へ移行し、総当たりの探索処理を実施して対象セルのルート（進入地点から目的地点までのルート）を設定する。これにより、出発地点から目的地点までのルートが設定される。
【００５６】
続いて、Ｓ１１１では、こうして設定したルートを必要に応じて別のルートに差し替えるルート差替処理を実行し、図４のルート探索処理を終了する。ここで、図４のＳ１１１で実行されるルート差替処理の詳細について図７のフローチャートを用いて説明する。制御部１９は、ルート差替処理を開始すると、まずＳ３０１で、代表ルートを使用したルート設定処理（Ｓ１０６）を行ったか否かを判定し、ルート設定処理を行っていないと判定した場合には、図７のルート差替処理を終了する。
【００５７】
一方、Ｓ３０１で、代表ルートを使用したルート設定処理を行ったと判定した場合には、Ｓ３０２へ移行し、総当たりの手法での出発地点から目的地点までのルート探索を、バックグラウンドで実行する。
【００５８】
続いて、Ｓ３０３では、設定済みのルート（代表ルートを使用して設定したルート）を、バックグラウンドで探索したルート（総当たりの手法で探索したルート）に差し替えるか否かをユーザに確認する。そして、ルートを差し替えるための操作がユーザにより行われた場合には、Ｓ３０４へ移行し、設定済みのルートをバックグラウンドで探索したルートに差し替えた後、Ｓ３０５へ移行する。一方、ルートを差し替えないための操作がユーザにより行われた場合には、そのままＳ３０５へ移行する。Ｓ３０５では、地図データにおいて設定されている代表ルートを必要に応じて更新するための代表ルート更新処理を実行し、ルート差替処理を終了する。
【００５９】
ここで、図７のＳ３０５で実行される代表ルート更新処理の詳細について図８のフローチャートを用いて説明する。制御部１９は、代表ルート更新処理を開始すると、まずＳ４０１で、出発地点を含むセルを対象セルに設定する。
【００６０】
続いてＳ４０２では、対象セルの代表ルートとバックグラウンドで探索したルートとが同じであるか否かを判定し、同じでないと判定した場合には、Ｓ４０３へ移行して、バックグラウンドで探索したルートを車両が実際に走行したか否かを判定する。
【００６１】
そして、Ｓ４０３でバックグラウンドで探索したルートを走行したと判定した場合には、Ｓ４０４へ移行し、対象セルの代表ルートをバックグラウンドで探索したルートに更新する。一方、Ｓ４０２で対象セルの代表ルートとバックグラウンドで探索したルートとが同じであると判定した場合や、Ｓ４０３でバックグラウンドで探索したルートを走行していないと判定した場合には、代表ルートを更新せずにＳ４０５へ移行する。
【００６２】
Ｓ４０５では、次のセルを対象セルに設定する。続いてＳ４０６では、対象セルに目的地点が含まれているか否かを判定し、含まれていないと判定した場合には、Ｓ４０２へ戻り、前述した処理（Ｓ４０２〜Ｓ４０５）を行う。一方、Ｓ４０６で対象セルに目的地点が含まれていると判定した場合には、図８の代表ルート更新処理を終了する。
【００６３】
次に、ルート探索の具体例について、図２を用いて説明する。
（１）セルＡ
セルＡ（出発セル）においては、出発地点が代表ルートの入口に位置していないため（Ｓ２０１：ＮＯ）、総当たりの手法でルート探索が行われる（Ｓ２０８）。具体的には、代表ルートの出口（この例では北側１箇所及び南側１箇所の合計２箇所）のうち、目的地点との距離が最も近い出口（北側の出口）が、セルＡを退出する退出地点として設定される。そして、出発地点から退出地点までのルートが探索され、探索されたルートがセルＡにおけるルートとして設定される。
【００６４】
（２）セルＢ
セルＡの退出地点を進入地点とするセルＢ（中間セル）においては、進入地点が代表ルートの入口に位置しているため（Ｓ２０１：ＹＥＳ）、この代表ルートがセルＢにおけるルートとして設定される（Ｓ２０２〜Ｓ２０７）。具体的には、代表ルートの出口（この例では北側１箇所及び西側１箇所の合計２箇所）のうち、目的地点に近い方角に存在する出口（北側の出口）が、セルＢを退出する退出地点として設定される。
【００６５】
（３）セルＣ
セルＢの退出地点を進入地点とするセルＣ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＣにおけるルートとして設定される。具体的には、代表ルートの出口（この例では北側１箇所、西側１箇所及び東側１箇所の合計３箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＣを退出する退出地点として設定される。
【００６６】
（４）セルＤ
セルＣの退出地点を進入地点とするセルＤ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＤにおけるルートとして設定される。具体的には、代表ルートの出口（この例では東側１箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＤを退出する退出地点として設定される。
【００６７】
（５）セルＥ
セルＤの退出地点を進入地点とするセルＥ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＥにおけるルートとして設定される。具体的には、代表ルートの出口（この例では北側１箇所、南側１箇所及び東側１箇所の合計３箇所）のうち、目的地点の方角に存在する出口（北側の出口）が、セルＥを退出する退出地点として設定される。
【００６８】
（６）セルＦ
セルＥの退出地点を進入地点とするセルＦ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＦにおけるルートとして設定される。具体的には、代表ルートの出口（この例では東側１箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＦを退出する退出地点として設定される。
【００６９】
（７）セルＧ
セルＦの退出地点を進入地点とするセルＧ（目的セル）においては、進入地点から目的地点までのルート探索が、総当たりの手法で行われ、探索されたルートがセルＧにおけるルートとして設定される（Ｓ１１０）。このようにして、出発地点から目的地点までのルートが設定される。
【００７０】
以上説明したように、本実施形態のナビゲーション装置は、複数のセルに分割された地図を表す地図データを用いて、出発地点から目的地点までのルートをセルごとに探索する（Ｓ１０４〜Ｓ１１０）。
【００７１】
具体的には、出発地点を含むセルである出発セルにおいて、出発セルを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発セルにおけるルートに設定する（Ｓ１０４〜Ｓ１０９）。そして、出発地点及び目的地点を含まないセルであって他のセルで設定された退出地点を進入地点とする中間セルにおいて、中間セルを退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間セルにおけるルートに設定する（Ｓ１０４〜Ｓ１０９）。さらに、目的地点を含むセルであって他のセルで設定された退出地点を進入地点とする目的セルにおいて、進入地点から目的地点までのルートを探索して、探索したルートを目的セルにおけるルートに設定する（Ｓ１１０）。
【００７２】
また、複数のセルには、セルを通過するルートとして１つ以上の代表ルートが設定された代表設定セルが含まれる。そして、中間セルが代表設定セルであって（Ｓ１０５：ＹＥＳ）、進入地点が代表ルートの入口である場合には（Ｓ２０１：ＹＥＳ）、その代表ルートの出口を退出地点に設定し、その代表ルートを中間セルにおけるルートに設定する（Ｓ２０２〜Ｓ２０７）。
【００７３】
このようなルート探索方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、総当たりでルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【００７４】
また、目的地点の位置に応じて選択した出口をセルの退出地点に設定するようにしているため（Ｓ２０２〜Ｓ２０６）、代表ルートの出口が複数存在する場合にも、目的地点に応じた適切なルートを設定することが可能となる。具体的には、代表ルートの出口は、正方形のセルの４つの辺のいずれかに位置し、代表ルートの出口が複数存在する場合には、中間セルにおける基準位置（本実施形態では中心位置）に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択する（Ｓ２０２〜Ｓ２０６）。このため、目的地点の方角に応じた適切なルートを設定することが可能となる。
【００７５】
また、代表ルートを使用して設定した第１のルートとは別に、出発地点から目的地点までの第２のルートを総当たりの探索処理で探索し（Ｓ３０２）、第１のルートを第２のルートに差し替える（Ｓ３０４）。このため、第２のルートと比較して短時間で探索可能な第１のルートを最初に提示し、その後に第１のルートと比較して信頼性の高い第２のルートに差し替えるといったことが可能となる。特に、第１のルートを第２のルートに差し替えるか否かをユーザに選択させるようにしているため（Ｓ３０３）、ユーザの意に反して第１のルートが第２のルートに差し替えられてしまうことを防ぐことができる。加えて、代表ルートと異なる第２のルートが走行された場合に（Ｓ４０２：ＮＯ，Ｓ４０３：ＹＥＳ）、第２のルートを代表ルートとして登録するようにしているため（Ｓ４０４）、代表ルートをユーザに応じた適切なルートに更新することができる。
【００７６】
なお、本実施形態では、Ｓ１０４〜Ｓ１１０が、区画ルート探索手段としての処理の一例に相当し、特に、Ｓ１０４〜Ｓ１０９が、出発ルート探索手段及び中間ルート探索手段としての処理（出発ルート探索ステップ及び中間ルート探索ステップ）の一例に相当し、Ｓ１１０が、目的ルート探索手段としての処理（目的ルート探索ステップ）の一例に相当する。また、Ｓ３０２が、代替ルート探索手段としての処理の一例に相当し、Ｓ３０４が、差替手段の一例に相当し、Ｓ３０５が、登録手段の一例に相当する。また、出発セル、中間セル、目的セル及び代表設定セルが、出発区画、中間区画、目的区画及び代表設定区画の一例にそれぞれ相当する。
【００７７】
以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。
（１）上記実施形態では、バックグラウンドで探索したルート（代表ルートとは異なるルート）が走行された場合に、代表ルートを更新するようにしているが、これに限定されるものではない。例えば、バックグラウンドで探索したルートのセルにおける入口及び出口の各方角が、代表ルートの入口及び出口の各方角と同じであることを条件に加えてもよい。このようにすれば、セルにおける代表ルートの入口及び出口の数（各方角における数）を一定に保ちつつ代表ルートを更新することができる。また、代表ルートを更新する（既存の代表ルートを削除して新規の代表ルートを記憶する）ことに代えて、代表ルートを追加する（既存の代表ルートを削除せずに新規の代表ルートを記憶する）ようにしてもよい。
【００７８】
（２）上記実施形態では、セルの中心位置を基準として目的地点の方角を判定するようにしているが、これに限定されるものではなく、例えば、セルへの進入地点を基準として目的地点の方角を判定するようにしてもよい。
【符号の説明】
【００７９】
１１…位置検出部、１２…ＧＰＳ受信機、１３…ジャイロスコープ、１４…距離センサ、１５…地図データ記憶部、１６…操作部、１７…表示部、１８…音声出力部、１９…制御部
【技術分野】
【０００１】
本発明は、出発地点から目的地点までのルートを探索するための技術に関する。
【背景技術】
【０００２】
従来、ナビゲーション装置では、地図データを用いて出発地点から目的地点までのルート（経路）を探索する技術が利用されている。ルート探索の基本的な手法は、出発地点から目的地点までのルートとして設定し得るすべてのルートの中から、最も適切な（例えば走行距離が最短となる）ルートを選択するという総当たりの手法である。ただし、この手法では、ルート探索のための計算量が膨大となり、処理時間が長くなってしまう。そこで、ルート探索に要する時間を短縮するための手法が提案されている。
【０００３】
例えば特許文献１には、上位レベルほどリンク数が少なくなるように階層化された構造の地図データを用いて、ルート探索に要する時間を短縮する構成のナビゲーション装置について記載されている。具体的には、このナビゲーション装置が用いる地図データは、基準レベルの道路リンク情報、基準レベルの道路リンク情報を用いてレベル格上げ処理を行って得られた第１上位レベルのリンク情報、第１上位レベルのリンク情報を用いてレベル格上げ処理を行って得られた複数の第２上位レベルのリンク情報といった形の階層構造を有する。なお、ここでいうレベル格上げ処理とは、探索枝数が規定数以上のリンクを上位レベルのリンクとして格上げすることにより、上位レベルのリンクを決定する処理のことである。
【０００４】
そして、特許文献１に記載のナビゲーション装置は、出発地点と目的地点との間の直線距離を算出し、算出した直線距離に基づいて、ルート探索に使用するリンクが属する第１レベル以外の上位レベルを決定する。その後、ナビゲーション装置は、基準レベルにおいて第１上位レベルに移行可能なリンクまでのルートを探索し、第１上位レベルにおいて、先に決定した更に上位のレベルに移行可能なリンクまでのルートを探索して、その上位レベルのリンク情報を用いてルート探索を行う。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２９２９８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述した特許文献１に記載のルート探索の手法は、階層構造に整備された地図データを必要とするものであり、地図データが階層構造に整備されていない場合には適用することができなかった。
【０００７】
本発明は、こうした問題にかんがみてなされたものであり、階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供することを目的としている。
【課題を解決するための手段】
【０００８】
請求項１に記載のナビゲーション装置は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する区画ルート探索手段を備える。具体的には、この区画ルート探索手段は、出発ルート探索手段、中間ルート探索手段及び目的ルート探索手段を備える。
【０００９】
出発ルート探索手段は、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索手段は、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索手段は、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【００１０】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索手段は、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【００１１】
このような構成によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【００１２】
ここで、代表ルートの出口が複数存在する場合には、請求項２に記載のように、目的地点の位置に応じて選択した出口を退出地点に設定するようにしてもよい。このようにすれば、目的地点に応じた適切なルートを設定することが可能となる。
【００１３】
具体的には、請求項３に記載のように、代表ルートの出口は、区画の外縁を形成する複数の辺のいずれかに位置し、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点の方角に応じた適切なルートを設定することが可能となる。
【００１４】
また、請求項４に記載のように、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点へ向かった適切なルートを設定することができる。
【００１５】
また、請求項５に記載のように、出発ルート探索手段は、出発区画が代表設定区画である場合には、代表ルートの出口を退出地点に設定するようにしてもよい。つまり、出発地点から代表ルートの出口までのルートを探索するのである。このようにすれば、出口があらかじめ設定されているため、総当たりの手法でルートを探索するとしても探索の手間や時間を大幅に短縮することができる。しかも、出発区画の退出地点を進入地点とする中間区画において、進入地点を代表ルートの入口に位置させることができるため、以降の区画における探索の処理負荷を抑えることができる。
【００１６】
また、請求項６に記載のように、代替ルート探索手段及び差替手段を更に備え、代替ルート探索手段が、出発地点から目的地点までのルートを区画ルート探索手段とは異なる方法で探索し、差替手段が、区画ルート探索手段により探索された第１のルートを、代替ルート探索手段により探索された第２のルートに差し替えるようにしてもよい。このようにすれば、第２のルートと比較して短時間で探索可能な第１のルートを最初に提示し、その後に第１のルートと比較して信頼性の高い第２のルートに差し替えるといったことが可能となる。
【００１７】
ただし、第１のルートが第２のルートに差し替えられることをユーザが望まない場合も考えられる。そこで、請求項７に記載のように、差替手段は、第１のルートを第２のルートに差し替えるか否かをユーザに選択させるようにしてもよい。このようにすれば、ユーザの意に反して第１のルートが第２のルートに差し替えられてしまうことを防ぐことができる。
【００１８】
また、代表ルートに代えて第２のルートが走行される場合には、その第２のルートを代表ルートとした方がユーザにとって好ましい場合もある。そこで、請求項８に記載のように、登録手段を更に備え、この登録手段が、代表ルートと異なる第２のルートが走行されたことを条件として、第２のルートを代表ルートとして登録するようにしてもよい。このようにすれば、代表ルートをユーザに応じた適切なルートに更新することができる。
【００１９】
次に、請求項９に記載のルート探索方法は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する方法であって、出発ルート探索ステップ、中間ルート探索ステップ及び目的ルート探索ステップを備える。
【００２０】
出発ルート探索ステップでは、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索ステップでは、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索ステップでは、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【００２１】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索ステップでは、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【００２２】
このような方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【図面の簡単な説明】
【００２３】
【図１】実施形態のナビゲーション装置の概略構成を示すブロック図である。
【図２】複数のセルに分割された地図を示す図である。
【図３】（Ａ）はセルの一例を示す図、（Ｂ）はセルにおける代表ルートの入口と出口との対応関係を示す図である。
【図４】ルート探索処理のフローチャートである。
【図５】ルート設定処理のフローチャートである。
【図６】（Ａ）は対象セルへの進入地点が代表ルートの入口に位置している状態を示す図、（Ｂ）は対象セルへの進入地点が代表ルートの入口に位置していない状態を示す図である。
【図７】ルート差替処理のフローチャートである。
【図８】代表ルート更新処理のフローチャートである。
【発明を実施するための形態】
【００２４】
以下、本発明が適用された実施形態について、図面を用いて説明する。
図１は、実施形態のナビゲーション装置の概略構成を示すブロック図である。
このナビゲーション装置は、車両に搭載されて用いられるものであり、位置検出部１１、地図データ記憶部１５、操作部１６、表示部１７、音声出力部１８、制御部１９などを備える。
【００２５】
位置検出部１１は、ＧＰＳ（Global Positioning System）用の人工衛星からの送信信号を受信し、車両の位置座標や高度を検出するＧＰＳ受信機１２と、車両に加えられる回転運動の角速度に応じた検出信号を出力するジャイロスコープ１３と、車両の走行距離を出力する距離センサ１４とを備える。そして、これらの各センサ１２〜１４の出力信号に基づいて制御部１９が、現在位置、方位、速度等を算出する。
【００２６】
地図データ記憶部１５は、地図データを記憶し、その各種データを制御部１９に入力する。地図データ記憶部１５に格納されるデータは、交差点等の特定地点に対応するノード及びノード間を接続するリンクによって道路の接続状況を示す道路データや、地図上の施設に関する施設データ、ルート案内を行うための案内データなどを含む各種データである。
【００２７】
操作部１６は、ユーザからの各種指示（各種の設定や機能実行の指示）を入力するためのものであり、表示部１７の表示画面上に配置されたタッチパネルや、メカニカルなキースイッチ等が用いられる。
【００２８】
表示部１７は、液晶ディスプレイ等の表示画面を有するものであり、制御部１９からの映像信号の入力に応じて各種画像を表示画面に表示する。この表示部１７は、地図画像の表示や、出発地点から目的地点までの誘導ルート、車両の現在位置を示すマーク、その他の案内情報等の表示に用いられる。
【００２９】
音声出力部１８は、各種情報を音声にてユーザに報知する。これによって、表示部１７による表示と音声出力部１８による音声出力との両方でユーザに対して各種ルート案内を行うことができる。
【００３０】
制御部１９は、ＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスライン等からなる周知のマイクロコンピュータを中心に構成されている。そして、ＣＰＵは、ＲＯＭに記憶されているプログラムに従い、位置検出部１１、地図データ記憶部１５、操作部１６から入力された各種情報に基づき、各種処理を実行する。
【００３１】
具体的には、制御部１９は、地図データ記憶部１５に記憶されている地図データを用いて、現在位置（出発地点）から目的地点までのルートを探索するルート探索処理を実行する。本実施形態で用いられる地図データは、図２に示すように、複数のセル（一定サイズの正方形の区画）に分割されており、制御部１９は、出発地点から目的地点までのルートを、次の（１）〜（３）の手順でセルごとに探索する。
【００３２】
（１）出発地点を含むセル（以下「出発セル」ともいう。）において、その出発セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その出発地点から、設定した退出地点までのルートを探索し、探索したルートをその出発セルにおけるルートに設定する。
【００３３】
（２）出発地点及び目的地点を含まないセルであって、他のセルで設定された退出地点を進入地点とするセル（以下「中間セル」ともいう。）において、その中間セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その進入地点から、設定した退出地点までのルートを探索し、探索したルートをその中間セルにおけるルートに設定する。
【００３４】
（３）目的地点を含むセルであって他のセルで設定された退出地点を進入地点とするセル（以下「目的セル」ともいう。）において、その進入地点から目的地点までのルートを探索し、探索したルートをその目的セルにおけるルートに設定する。
【００３５】
このように制御部１９は、１セル分の地図データを順に読み込み、セルごとにルートを探索することで、出発地点から目的地点までのルートを探索する。ただし、セル内において総当たりの手法でルートを探索すると、ルート探索に要する時間が長くなる。特に、すべてのセルにおいて総当たりの手法でルートを探索すると、セル数に比例して探索時間が増大してしまう。
【００３６】
そこで、本実施形態では、図２に示すように、各セルにおいて、例えば幹線道路などのように、走行案内するルートに適した一部の道路が、代表ルート（セルの拡大図において太線で示されたルート）としてあらかじめ設定されている。各セルにおける代表ルートの入口及び出口は、セルの外縁を形成する４つの辺（北側、西側、南側及び東側の各方角に対応する辺）のいずれかに位置し、あるセルにおける代表ルートの出口は、その出口が位置する辺で隣接する他のセルにおける代表ルートの入口となる。
【００３７】
また、代表ルートの設定されたセル（以下「代表設定セル」ともいう。）には、図３（Ａ），（Ｂ）に示すように、セルにおける各方角の辺を基準とした代表ルートの入口と出口との対応関係が記憶されている。例えば、図３（Ａ）に示すセルの場合、代表ルートの入口又は出口となり得る箇所が、東側、南側及び北側の３箇所に存在する。そして、このセルでは、図３（Ｂ）に示すように、東側を入口とした場合の出口が南側の１箇所、南側を入口とした場合の出口が東側及び北側の２箇所、北側を入口とした場合の出口が南側の１箇所に設定され、かつそれら出口に至るためのルート(代表ルート)がそれぞれ一意に定義されている。なお、東側を入口とした場合の出口を北側及び南側の２箇所に設定してもよく、同様に、北側を入口とした場合の出口を東側及び南側の２箇所に設定してもよい。
【００３８】
このように、代表設定セルでは、代表ルートの入口と出口との対応関係が設定されているため、代表ルートの入口に対応する出口を選択するだけで、入口から出口へ至るルートを考慮することなく（最短ルートであるか否かは問わず）、ルートを設定することが可能となる。そして、セルにおける代表ルートの出口を、隣接するセルにおける代表ルートの入口として、代表ルートを順につないでいくことにより、短時間でルートを設定することができる。
【００３９】
ここで、このような処理を実現するために制御部１９が実行する具体的処理内容について説明する。図４は、制御部１９が実行するルート探索処理のフローチャートである。このルート探索処理は、ルート探索を開始する操作がユーザにより操作部１６で行われることにより開始される。
【００４０】
制御部１９は、ルート探索処理を開始すると、まずＳ１０１で、目的地点をユーザに設定させる。続いてＳ１０２で、階層構造の地図データが使用可能であるか否かを判定する。すなわち、地図データ記憶部１５に記憶される地図データが、階層構造に整備されたものであるか否かを判定する。例えば、ナビゲーション装置が複数の国で使用されるものであり、国によって地図データの構造が異なるような場合に、このような判定が有効となる。なお、階層構造に整備されていない地図データを用いることが決まっている場合には、Ｓ１０２の判定処理を行うことなくＳ１０４へ移行するようにしてもよい。
【００４１】
そして、Ｓ１０２で、階層構造の地図データが使用可能であると判定した場合には、Ｓ１０３へ移行して、階層構造の地図データを使用してルートを設定した後、Ｓ１１１へ移行する。この場合のルート設定は、従来技術をそのまま適用すればよいため、具体的な説明は省略する。
【００４２】
一方、Ｓ１０２で、階層構造の地図データが使用可能でないと判定した場合には、前述したＳ１０３の処理に代えて、Ｓ１０４〜Ｓ１１０の処理を実行する。すなわち、まずＳ１０４で、出発地点（通常は現在位置）を含むセルを処理対象のセル（以下「対象セル」という。）に設定する。続いてＳ１０５では、対象セルのルート設定に代表ルートを使用可能である（対象セルに代表ルートが設定されている）か否かを判定する。このＳ１０５で、対象セルのルート設定に代表ルートを使用可能であると判定した場合には、Ｓ１０６へ移行して、代表ルートを使用してルートを設定するためのルート設定処理を実行した後、Ｓ１０８へ移行する。
【００４３】
ここで、図４のＳ１０６で実行されるルート設定処理の詳細について図５のフローチャートを用いて説明する。制御部１９は、ルート設定処理を開始すると、まずＳ２０１で、対象セルへの進入地点が、その対象セルに設定されている代表ルートの入口に位置しているか否かを判定する。なお、対象セルへの進入地点とは、前回の対象セルの退出地点（後述）のことである。ただし、対象セルに出発地点が含まれる場合には、その出発地点を進入地点として処理を行う。
【００４４】
そして、図６（Ａ）に例示するように、Ｓ２０１で、対象セルへの進入地点が代表ルートの入口に位置していると判定した場合には、Ｓ２０２へ移行し、対象セルを基準とした目的地点の方角を判定する。本実施形態では、対象セルの中心位置を基準とした目的地点の方角が、北東〜北西（北東含む）、北西〜南西（北西含む）、南西〜南東（南西含む）、南東〜北東（南東含む）の４つの範囲のいずれに分類されるかを判定する。
【００４５】
そして、Ｓ２０２で目的地点の方角が北東〜北西（北東含む）に分類されると判定した場合には、Ｓ２０３へ移行し、進入地点を入口とする代表ルートの出口のうち、対象セルにおける北側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４６】
また、Ｓ２０２で目的地点の方角が北西〜南西（北西含む）に分類されると判定した場合には、Ｓ２０４へ移行し、代表ルートの出口のうち、対象セルにおける西側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４７】
また、Ｓ２０２で目的地点の方角が南西〜南東（南西含む）に分類されると判定した場合には、Ｓ２０５へ移行し、代表ルートの出口のうち、対象セルにおける南側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４８】
また、Ｓ２０２で目的地点の方角が南東〜北東（南東含む）に分類されると判定した場合には、Ｓ２０６へ移行し、代表ルートの出口のうち、対象セルにおける東側の辺に設定された出口を退出地点に設定する。その後、Ｓ２０７へ移行する。
【００４９】
Ｓ２０７では、進入地点から退出地点までの代表ルートを、対象セルのルートに設定し、図５のルート設定処理を終了する。このように、進入地点が代表ルートの入口に位置する場合には、ルート計算を行うことなく、目的地点の方角に応じた出口を選択するだけでルートが設定される。
【００５０】
なお、目的地点の方角に代表ルートの出口が存在しない場合には、他の方角の出口の中から、目的地点の方角に近い方角の出口を選択するようにしてもよい。また、対象セルへの進入地点の方角から遠い方角の出口を選択するようにしてもよい。例えば、対象セルへの進入地点が西側、目的地点が南の方角であって、対象セルにおける南側の辺に出口が設定されていない場合には、東側の辺に設定された出口（目的地点の方角に近い方角であって、進入地点の方角から遠い方角）を優先的に選択する。
【００５１】
また、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、代表ルートの出口の数が同じ方角に２つ以上存在するような場合にも、目的地点の位置に応じた１つの出口として選択することができるため、目的地点へ向かった適切なルートを設定することができる。
【００５２】
一方、図６（Ｂ）に例示するように、Ｓ２０１で、対象セルへの進入地点が代表ルートの入口に位置していないと判定した場合には、Ｓ２０８へ移行し、総当たりの手法でルート探索を行い、対象セルのルートを設定した後、図５のルート設定処理を終了する。なお、この場合の退出地点も、目的地点の位置に応じて（例えば目的地点との距離が最も近い出口などに）設定される。特に、この退出地点を代表ルートの出口から選択するようにすれば、次回の対象セルの進入地点を代表ルートの入口に位置させることができる。つまり、進入地点から対象セルの代表ルートの出口までのルート探索を行うのである。こうすれば、出口があらかじめ設定されているため、総当たりの手法でルート探索するとしても探索の手間、時間を大幅に短縮することができる。とりわけ対象セルが出発セルである場合、すなわち進入地点が出発地点（通常は現在位置）である場合、この方法をとれば、それ以後の探索の手間、時間を容易に節約できる。
【００５３】
図４に戻り、Ｓ１０５で対象セルのルート設定に代表ルートを使用可能でないと判定した場合には、Ｓ１０７へ移行し、前述したＳ２０８と同様、総当たりの探索処理を実施して対象セルのルートを設定した後、Ｓ１０８へ移行する。
【００５４】
Ｓ１０８では、設定したルートの出口（退出地点）が位置する辺で現在の対象セルに隣接するセルを、次の対象セルに設定する。続いてＳ１０９では、設定した対象セルに目的地点が含まれているか否かを判定し、含まれていない（中間セルである）と判定した場合には、Ｓ１０５へ戻り、前述した処理（Ｓ１０５〜Ｓ１０８）を行う。
【００５５】
一方、Ｓ１０９で対象セルに目的地点が含まれている（目的セルである）と判定した場合には、Ｓ１１０へ移行し、総当たりの探索処理を実施して対象セルのルート（進入地点から目的地点までのルート）を設定する。これにより、出発地点から目的地点までのルートが設定される。
【００５６】
続いて、Ｓ１１１では、こうして設定したルートを必要に応じて別のルートに差し替えるルート差替処理を実行し、図４のルート探索処理を終了する。ここで、図４のＳ１１１で実行されるルート差替処理の詳細について図７のフローチャートを用いて説明する。制御部１９は、ルート差替処理を開始すると、まずＳ３０１で、代表ルートを使用したルート設定処理（Ｓ１０６）を行ったか否かを判定し、ルート設定処理を行っていないと判定した場合には、図７のルート差替処理を終了する。
【００５７】
一方、Ｓ３０１で、代表ルートを使用したルート設定処理を行ったと判定した場合には、Ｓ３０２へ移行し、総当たりの手法での出発地点から目的地点までのルート探索を、バックグラウンドで実行する。
【００５８】
続いて、Ｓ３０３では、設定済みのルート（代表ルートを使用して設定したルート）を、バックグラウンドで探索したルート（総当たりの手法で探索したルート）に差し替えるか否かをユーザに確認する。そして、ルートを差し替えるための操作がユーザにより行われた場合には、Ｓ３０４へ移行し、設定済みのルートをバックグラウンドで探索したルートに差し替えた後、Ｓ３０５へ移行する。一方、ルートを差し替えないための操作がユーザにより行われた場合には、そのままＳ３０５へ移行する。Ｓ３０５では、地図データにおいて設定されている代表ルートを必要に応じて更新するための代表ルート更新処理を実行し、ルート差替処理を終了する。
【００５９】
ここで、図７のＳ３０５で実行される代表ルート更新処理の詳細について図８のフローチャートを用いて説明する。制御部１９は、代表ルート更新処理を開始すると、まずＳ４０１で、出発地点を含むセルを対象セルに設定する。
【００６０】
続いてＳ４０２では、対象セルの代表ルートとバックグラウンドで探索したルートとが同じであるか否かを判定し、同じでないと判定した場合には、Ｓ４０３へ移行して、バックグラウンドで探索したルートを車両が実際に走行したか否かを判定する。
【００６１】
そして、Ｓ４０３でバックグラウンドで探索したルートを走行したと判定した場合には、Ｓ４０４へ移行し、対象セルの代表ルートをバックグラウンドで探索したルートに更新する。一方、Ｓ４０２で対象セルの代表ルートとバックグラウンドで探索したルートとが同じであると判定した場合や、Ｓ４０３でバックグラウンドで探索したルートを走行していないと判定した場合には、代表ルートを更新せずにＳ４０５へ移行する。
【００６２】
Ｓ４０５では、次のセルを対象セルに設定する。続いてＳ４０６では、対象セルに目的地点が含まれているか否かを判定し、含まれていないと判定した場合には、Ｓ４０２へ戻り、前述した処理（Ｓ４０２〜Ｓ４０５）を行う。一方、Ｓ４０６で対象セルに目的地点が含まれていると判定した場合には、図８の代表ルート更新処理を終了する。
【００６３】
次に、ルート探索の具体例について、図２を用いて説明する。
（１）セルＡ
セルＡ（出発セル）においては、出発地点が代表ルートの入口に位置していないため（Ｓ２０１：ＮＯ）、総当たりの手法でルート探索が行われる（Ｓ２０８）。具体的には、代表ルートの出口（この例では北側１箇所及び南側１箇所の合計２箇所）のうち、目的地点との距離が最も近い出口（北側の出口）が、セルＡを退出する退出地点として設定される。そして、出発地点から退出地点までのルートが探索され、探索されたルートがセルＡにおけるルートとして設定される。
【００６４】
（２）セルＢ
セルＡの退出地点を進入地点とするセルＢ（中間セル）においては、進入地点が代表ルートの入口に位置しているため（Ｓ２０１：ＹＥＳ）、この代表ルートがセルＢにおけるルートとして設定される（Ｓ２０２〜Ｓ２０７）。具体的には、代表ルートの出口（この例では北側１箇所及び西側１箇所の合計２箇所）のうち、目的地点に近い方角に存在する出口（北側の出口）が、セルＢを退出する退出地点として設定される。
【００６５】
（３）セルＣ
セルＢの退出地点を進入地点とするセルＣ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＣにおけるルートとして設定される。具体的には、代表ルートの出口（この例では北側１箇所、西側１箇所及び東側１箇所の合計３箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＣを退出する退出地点として設定される。
【００６６】
（４）セルＤ
セルＣの退出地点を進入地点とするセルＤ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＤにおけるルートとして設定される。具体的には、代表ルートの出口（この例では東側１箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＤを退出する退出地点として設定される。
【００６７】
（５）セルＥ
セルＤの退出地点を進入地点とするセルＥ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＥにおけるルートとして設定される。具体的には、代表ルートの出口（この例では北側１箇所、南側１箇所及び東側１箇所の合計３箇所）のうち、目的地点の方角に存在する出口（北側の出口）が、セルＥを退出する退出地点として設定される。
【００６８】
（６）セルＦ
セルＥの退出地点を進入地点とするセルＦ（中間セル）においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルＦにおけるルートとして設定される。具体的には、代表ルートの出口（この例では東側１箇所）のうち、目的地点の方角に存在する出口（東側の出口）が、セルＦを退出する退出地点として設定される。
【００６９】
（７）セルＧ
セルＦの退出地点を進入地点とするセルＧ（目的セル）においては、進入地点から目的地点までのルート探索が、総当たりの手法で行われ、探索されたルートがセルＧにおけるルートとして設定される（Ｓ１１０）。このようにして、出発地点から目的地点までのルートが設定される。
【００７０】
以上説明したように、本実施形態のナビゲーション装置は、複数のセルに分割された地図を表す地図データを用いて、出発地点から目的地点までのルートをセルごとに探索する（Ｓ１０４〜Ｓ１１０）。
【００７１】
具体的には、出発地点を含むセルである出発セルにおいて、出発セルを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発セルにおけるルートに設定する（Ｓ１０４〜Ｓ１０９）。そして、出発地点及び目的地点を含まないセルであって他のセルで設定された退出地点を進入地点とする中間セルにおいて、中間セルを退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間セルにおけるルートに設定する（Ｓ１０４〜Ｓ１０９）。さらに、目的地点を含むセルであって他のセルで設定された退出地点を進入地点とする目的セルにおいて、進入地点から目的地点までのルートを探索して、探索したルートを目的セルにおけるルートに設定する（Ｓ１１０）。
【００７２】
また、複数のセルには、セルを通過するルートとして１つ以上の代表ルートが設定された代表設定セルが含まれる。そして、中間セルが代表設定セルであって（Ｓ１０５：ＹＥＳ）、進入地点が代表ルートの入口である場合には（Ｓ２０１：ＹＥＳ）、その代表ルートの出口を退出地点に設定し、その代表ルートを中間セルにおけるルートに設定する（Ｓ２０２〜Ｓ２０７）。
【００７３】
このようなルート探索方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、総当たりでルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【００７４】
また、目的地点の位置に応じて選択した出口をセルの退出地点に設定するようにしているため（Ｓ２０２〜Ｓ２０６）、代表ルートの出口が複数存在する場合にも、目的地点に応じた適切なルートを設定することが可能となる。具体的には、代表ルートの出口は、正方形のセルの４つの辺のいずれかに位置し、代表ルートの出口が複数存在する場合には、中間セルにおける基準位置（本実施形態では中心位置）に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択する（Ｓ２０２〜Ｓ２０６）。このため、目的地点の方角に応じた適切なルートを設定することが可能となる。
【００７５】
また、代表ルートを使用して設定した第１のルートとは別に、出発地点から目的地点までの第２のルートを総当たりの探索処理で探索し（Ｓ３０２）、第１のルートを第２のルートに差し替える（Ｓ３０４）。このため、第２のルートと比較して短時間で探索可能な第１のルートを最初に提示し、その後に第１のルートと比較して信頼性の高い第２のルートに差し替えるといったことが可能となる。特に、第１のルートを第２のルートに差し替えるか否かをユーザに選択させるようにしているため（Ｓ３０３）、ユーザの意に反して第１のルートが第２のルートに差し替えられてしまうことを防ぐことができる。加えて、代表ルートと異なる第２のルートが走行された場合に（Ｓ４０２：ＮＯ，Ｓ４０３：ＹＥＳ）、第２のルートを代表ルートとして登録するようにしているため（Ｓ４０４）、代表ルートをユーザに応じた適切なルートに更新することができる。
【００７６】
なお、本実施形態では、Ｓ１０４〜Ｓ１１０が、区画ルート探索手段としての処理の一例に相当し、特に、Ｓ１０４〜Ｓ１０９が、出発ルート探索手段及び中間ルート探索手段としての処理（出発ルート探索ステップ及び中間ルート探索ステップ）の一例に相当し、Ｓ１１０が、目的ルート探索手段としての処理（目的ルート探索ステップ）の一例に相当する。また、Ｓ３０２が、代替ルート探索手段としての処理の一例に相当し、Ｓ３０４が、差替手段の一例に相当し、Ｓ３０５が、登録手段の一例に相当する。また、出発セル、中間セル、目的セル及び代表設定セルが、出発区画、中間区画、目的区画及び代表設定区画の一例にそれぞれ相当する。
【００７７】
以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。
（１）上記実施形態では、バックグラウンドで探索したルート（代表ルートとは異なるルート）が走行された場合に、代表ルートを更新するようにしているが、これに限定されるものではない。例えば、バックグラウンドで探索したルートのセルにおける入口及び出口の各方角が、代表ルートの入口及び出口の各方角と同じであることを条件に加えてもよい。このようにすれば、セルにおける代表ルートの入口及び出口の数（各方角における数）を一定に保ちつつ代表ルートを更新することができる。また、代表ルートを更新する（既存の代表ルートを削除して新規の代表ルートを記憶する）ことに代えて、代表ルートを追加する（既存の代表ルートを削除せずに新規の代表ルートを記憶する）ようにしてもよい。
【００７８】
（２）上記実施形態では、セルの中心位置を基準として目的地点の方角を判定するようにしているが、これに限定されるものではなく、例えば、セルへの進入地点を基準として目的地点の方角を判定するようにしてもよい。
【符号の説明】
【００７９】
１１…位置検出部、１２…ＧＰＳ受信機、１３…ジャイロスコープ、１４…距離センサ、１５…地図データ記憶部、１６…操作部、１７…表示部、１８…音声出力部、１９…制御部
【特許請求の範囲】
【請求項１】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索する区画ルート探索手段を備え、
前記区画ルート探索手段は、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索手段と、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索手段と、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索手段と、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索手段は、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点の位置に応じて選択した出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置であって、
前記代表ルートの出口は、前記区画の外縁を形成する複数の辺のいずれかに位置し、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、前記中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項４】
請求項２又は請求項３に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項５】
請求項１から請求項４までのいずれか１項に記載のナビゲーション装置であって、
前記出発ルート探索手段は、前記出発区画が前記代表設定区画である場合には、代表ルートの出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項６】
請求項１から請求項５までのいずれか１項に記載のナビゲーション装置であって、
出発地点から目的地点までのルートを前記区画ルート探索手段とは異なる方法で探索する代替ルート探索手段と、
前記区画ルート探索手段により探索された第１のルートを、前記代替ルート探索手段により探索された第２のルートに差し替える差替手段と、
を更に備えることを特徴とするナビゲーション装置。
【請求項７】
請求項６に記載のナビゲーション装置であって、
前記差替手段は、前記第１のルートを前記第２のルートに差し替えるか否かをユーザに選択させる
ことを特徴とするナビゲーション装置。
【請求項８】
請求項６又は請求項７に記載のナビゲーション装置であって、
前記代表ルートと異なる前記第２のルートが走行されたことを条件として、前記第２のルートを前記代表ルートとして登録する登録手段を更に備える
ことを特徴とするナビゲーション装置。
【請求項９】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索するルート探索方法であって、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索ステップと、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索ステップと、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索ステップと、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索ステップでは、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするルート探索方法。
【請求項１】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索する区画ルート探索手段を備え、
前記区画ルート探索手段は、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索手段と、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索手段と、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索手段と、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索手段は、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点の位置に応じて選択した出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項３】
請求項２に記載のナビゲーション装置であって、
前記代表ルートの出口は、前記区画の外縁を形成する複数の辺のいずれかに位置し、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、前記中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項４】
請求項２又は請求項３に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項５】
請求項１から請求項４までのいずれか１項に記載のナビゲーション装置であって、
前記出発ルート探索手段は、前記出発区画が前記代表設定区画である場合には、代表ルートの出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項６】
請求項１から請求項５までのいずれか１項に記載のナビゲーション装置であって、
出発地点から目的地点までのルートを前記区画ルート探索手段とは異なる方法で探索する代替ルート探索手段と、
前記区画ルート探索手段により探索された第１のルートを、前記代替ルート探索手段により探索された第２のルートに差し替える差替手段と、
を更に備えることを特徴とするナビゲーション装置。
【請求項７】
請求項６に記載のナビゲーション装置であって、
前記差替手段は、前記第１のルートを前記第２のルートに差し替えるか否かをユーザに選択させる
ことを特徴とするナビゲーション装置。
【請求項８】
請求項６又は請求項７に記載のナビゲーション装置であって、
前記代表ルートと異なる前記第２のルートが走行されたことを条件として、前記第２のルートを前記代表ルートとして登録する登録手段を更に備える
ことを特徴とするナビゲーション装置。
【請求項９】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索するルート探索方法であって、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索ステップと、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索ステップと、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索ステップと、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索ステップでは、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするルート探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−１１３６０９（Ｐ２０１３−１１３６０９Ａ）
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１１−２５７６６５（Ｐ２０１１−２５７６６５）
【出願日】平成２３年１１月２５日（２０１１．１１．２５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１１月２５日（２０１１．１１．２５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【Ｆターム（参考）】
[ Back to top ]