(57)【特許請求の範囲】
【請求項１】
地図配信サーバから通信回線を介して差分地図データを取得して更新を行うナビゲーション装置であって、
目的地を設定するための設定部と、
前記ナビゲーション装置の現在位置から前記目的地までの誘導経路を表示する表示部と、
前記誘導経路を計算するための地図データを記憶する地図データベースと、
前記地図配信サーバから取得した前記差分地図データを記憶する差分地図データ記憶部と、
前記ナビゲーション装置近傍の地図データであるキャッシュ地図データを記憶するメモリ部と、
衛星からの電波を用いて、前記ナビゲーション装置の現在位置の情報を受信する衛星電波受信部と、
前記現在位置と前記目的地と前記ナビゲーション装置が備える地図データのバージョン情報とを含んだ分岐候補要求情報を前記地図配信サーバに送信し、前記地図配信サーバから、前記誘導経路上の新たな分岐地点の候補である分岐候補情報を取得する分岐候補情報取得部と、
前記分岐地点が含まれる差分地図データを前記地図配信サーバから取得し、前記差分地図データ記憶部に記憶する差分地図データ取得部と、
前記ナビゲーション装置の現在位置から前記分岐地点までの到達時間と、前記差分地図データ記憶部に記憶された前記差分地図データを更新する時間とを比較し、前記差分地図データ記憶部に記憶された差分地図データのうち、更新が間に合う前記差分地図データを選択する更新地図データ選択部と、
前記更新地図データ選択部により選択された１つ以上の前記差分地図データについて、前記分岐地点までの到達時間が短い順に当該差分地図データの更新順序を決定する更新順序決定部と、
前記更新順序決定部によって決定された更新順序にしたがい、前記更新地図データ選択部により選択された差分地図データごとに、前記地図データベースを更新し、さらに前記更新された地図データベースの当該差分地図データを用いて、前記メモリ部に記憶された前記キャッシュ地図データを更新する地図データ更新処理部と、
を備えることを特徴とするナビゲーション装置。
【請求項２】
前記更新地図データ選択部は、
前記ナビゲーション装置の現在位置および移動速度から、前記分岐地点の候補ごとの到達時間を計算し、前記差分地図データの更新にかかる所定の閾値よりも、前記到達時間が長い場合に、前記差分地図データを更新可能と判断する地図更新可否判断部を
備えることを特徴とする請求の範囲第１項に記載のナビゲーション装置。
【請求項３】
前記所定の閾値は、前記ナビゲーション装置の現在位置と前記目的地との間の経路探索の処理時間を示す経路探索最悪時間、前記表示部の画面更新時間、前記地図データベースの更新時間、および、前記キャッシュ地図データの更新時間、を含んで算出されること
を特徴とする請求の範囲第２項に記載のナビゲーション装置。
【請求項４】
前記更新地図データ選択部は、
前記地図更新可否判断部により更新可能と判断された前記差分地図データについて、当該差分地図データにより示されるリンク列の両端のポイントが前記誘導経路と連結するか否かを判定する整合性判定部を
備えることを特徴とする請求の範囲第２項または請求の範囲第３項に記載のナビゲーション装置。
【請求項５】
前記分岐候補情報取得部が、前記地図配信サーバから前記分岐候補情報を取得すると、前記表示部に前記分岐地点の候補を表示させる誘導案内部を
さらに備えることを特徴とする請求の範囲第１項に記載のナビゲーション装置。
【請求項６】
地図配信サーバから通信回線を介して差分地図データを取得して更新を行うナビゲーション装置を用いたナビゲーション方法であって、
前記ナビゲーション装置は、
目的地を設定するための設定部と、前記ナビゲーション装置の現在位置から前記目的地までの誘導経路を表示する表示部と、前記誘導経路を計算するための地図データを記憶する地図データベースと、前記地図配信サーバから取得した前記差分地図データを記憶する差分地図データ記憶部と、前記ナビゲーション装置近傍の地図データであるキャッシュ地図データを記憶するメモリ部と、衛星からの電波を用いて、前記ナビゲーション装置の現在位置の情報を受信する衛星電波受信部とを備え、
前記現在位置と前記目的地と前記ナビゲーション装置が備える地図データのバージョン情報とを含んだ分岐候補要求情報を前記地図配信サーバに送信し、前記地図配信サーバから、前記誘導経路上の新たな分岐地点の候補である分岐候補情報を取得し、
前記分岐地点が含まれる差分地図データを、前記地図配信サーバから取得して、前記差分地図データ記憶部に記憶し、
前記ナビゲーション装置の現在位置から前記分岐地点までの到達時間と、前記差分地図データ記憶部に記憶された前記差分地図データを更新する時間とを比較し、前記差分地図データ記憶部に記憶された差分地図データのうち、更新が間に合う前記差分地図データを選択し、
前記選択された１つ以上の前記差分地図データについて、前記分岐地点までの到達時間が短い順に当該差分地図データの更新順序を決定し、
前記決定された更新順序にしたがい、前記選択された差分地図データごとに、前記地図データベースを更新し、さらに前記更新された地図データベースの当該差分地図データを用いて、前記メモリ部に記憶された前記キャッシュ地図データを更新すること
を特徴とするナビゲーション方法。
【請求項７】
ナビゲーション装置が地図データの更新に必要とする差分地図データを、通信回線を介して地図配信サーバから取得して誘導案内を行うナビゲーションシステムであって、
前記ナビゲーション装置は、
目的地を設定するための設定部と、
前記ナビゲーション装置の現在位置から前記目的地までの誘導経路を表示する表示部と、
前記誘導経路を計算するための地図データを記憶する地図データベースと、
前記地図配信サーバから取得した前記差分地図データを記憶する差分地図データ記憶部と、
前記ナビゲーション装置近傍の地図データであるキャッシュ地図データを記憶するメモリ部と、
衛星からの電波を用いて、前記ナビゲーション装置の現在位置の情報を受信する衛星電波受信部と、
前記現在位置と前記目的地と前記ナビゲーション装置が備える地図データのバージョン情報とを含んだ分岐候補要求情報を前記地図配信サーバに送信し、前記地図配信サーバから、前記誘導経路上の新たな分岐地点の候補である分岐候補情報を取得する分岐候補情報取得部と、
前記分岐地点が含まれる差分地図データを前記地図配信サーバから取得し、前記差分地図データ記憶部に記憶する差分地図データ取得部と、
前記ナビゲーション装置の現在位置から前記分岐地点までの到達時間と、前記差分地図データ記憶部に記憶された前記差分地図データを更新する時間とを比較し、前記差分地図データ記憶部に記憶された差分地図データのうち、更新が間に合う前記差分地図データを選択する更新地図データ選択部と、
前記更新地図データ選択部により選択された１つ以上の前記差分地図データについて、前記分岐地点までの到達時間が短い順に当該差分地図データの更新順序を決定する更新順序決定部と、
前記更新順序決定部によって決定された更新順序にしたがい、前記更新地図データ選択部により選択された差分地図データごとに、前記地図データベースを更新し、さらに前記更新された地図データベースの当該差分地図データを用いて、前記メモリ部に記憶された前記キャッシュ地図データを更新する地図データ更新処理部と、を備え、
前記地図配信サーバは、
地図バージョンごとの地図データを格納する地図データベースが記憶される地図データ記憶部と、
前記ナビゲーション装置から取得した前記分岐候補要求情報を用いて、前記地図データ記憶部を参照し、前記誘導経路上の新たな分岐地点の候補である分岐候補情報を生成する分岐候補情報生成部と、
生成された分岐候補情報をナビゲーション装置に送信する分岐候補情報送信部と、
前記分岐候補が含まれる前記差分地図データをナビゲーション装置に送信する差分地図データ送信部と、
を備えることを特徴とするナビゲーションシステム。
【請求項８】
前記地図配信サーバは、
前記ナビゲーション装置から送信された前記地図データのバーション情報と、前記地図配信サーバが備える前記地図データの最新のバージョン情報とが異なる場合に、
前記ナビゲーション装置の、現在位置と、前記目的地と、前記地図データのバージョン情報とを参照して、前記誘導経路を計算する誘導経路確認部と、
前記地図データ記憶部に記憶された前記地図データの最新のバージョン情報と、前記ナビゲーション装置が備える前記地図データのバージョン情報とを比較することにより、前記地図データの差分を検出して前記差分地図データを生成し、当該生成された差分地図データから、前記誘導経路確認部が計算した誘導経路上にある新たな分岐地点の候補を抽出する差分抽出部と、
をさらに備えることを特徴とする請求の範囲第７項に記載のナビゲーションシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置、ナビゲーション方法およびナビゲーションシステムの技術に関する。
【背景技術】
【０００２】
近年、車両の現在位置を地図上に表示したり、目的地までの経路情報を探索して運転者に案内するナビゲーション装置が普及してきている。このような現在位置の表示や経路探索、誘導案内を行うために、ナビゲーション装置は地図が示す領域の広さに応じて区分分けされた地図データを備えている。この地図データの区分（レベル）は、例えば１０ｋｍ×１０ｋｍ四方の「概要レベル」の区分に分けられた地図データから、例えば２．５ｋｍ×２．５ｋｍ四方の「詳細レベル」の区分に分けられた地図データ、あるいはさらに詳細な区分に分けられた地図データというように階層的に構成されている。【０００３】
こうした地図データは、ＤＶＤ（Digital Versatile Disc）やハードディスク（ＨＤＤ：Hard Disk Drive）等の記録媒体、記録装置により入手されるほか、最近では通信回線を介してハードディスクにダウンロードする形でも入手される。しかし、実際の道路網は新たな道路の開通、閉鎖等により絶えず変化している。したがって、一旦入手した地図データもそのような最新の道路事情を反映させるために頻繁に更新を行う必要がある。【０００４】
このような地図データの更新は、地図データを通信回線を介して取得できるハードディスクを備えたナビゲーション装置の場合、更新を必要とする差分地図データのみを地図配信サーバから取得して更新する方法が開示されている（例えば、特許文献１参照）。これは、地図データの変更部分が、実際には約数パーセントにしか過ぎず、地図の更新時間や通信コストを節約するためである。
また、ハードディスク上の地図データの更新と、誘導案内（ナビゲーション処理）を両立させるため、キャッシュメモリを設け、キャッシュメモリ上に地図データを持つことで、地図データの更新と誘導案内動作を独立させて、両者を同時に行う技術が開示されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−１９８８４１号公報
【特許文献２】特開２００５−２５８３４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に記載された技術を用いて、配信された差分地図データをもとにナビゲーション装置内の地図データを更新しようとすると、更新時間は東京でも３０分近くかかる場合がある。その理由は、ナビゲーション装置という組み込み機器のＣＰＵの性能、メモリ容量といったシステムのリソース上の制約によるところが大きい。このため、もし差分地図データをもとに再経路探索（リルート）させようとすると、走行中であった場合には、その間誘導案内をすることができず、さらに、自車位置が３０分走行しているため、新しくできた道路の分岐地点を通過してしまい、最新の道路状況を考慮した誘導案内が実現できない結果となる。このため、地図更新のメリットを即座に享受できるものではない。【０００７】
また、特許文献２に記載された技術では、ナビゲーション装置のハードディスク上の地図データは更新されたとしても、キャッシュメモリ上の地図データが更新されず、したがって更新前の地図データを用いて誘導経路の案内がされることとなり、更新後の新しい道路状況を考慮した再経路探索および誘導案内が実現できないことになる。【０００８】
このような背景に鑑みて本発明がなされたのであり、本発明は、差分地図データの更新順序を決定することで、差分地図データの更新と最新の地図データによる誘導案内を同時に行うことを可能にするナビゲーション装置、ナビゲーション方法およびナビゲーションシステムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記課題を解決するため、本発明のナビゲーション装置、ナビゲーション方法およびナビゲーションシステムは、新たな分岐地点までの到達時間と、差分地図データの更新時間とを比較し、差分地図データの更新が間に合う分岐地点を選択した上で、その分岐地点までの到達時間が短い順に差分地図データを更新していくことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、差分地図データの更新順序を決定することで、差分地図データの更新と最新の地図データによる誘導案内を同時に行うことを可能にするナビゲーション装置、ナビゲーション方法およびナビゲーションシステムを提供することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係るナビゲーションシステムの構成を示す機能ブロック図である。
【図２】本発明の実施形態に係る地図配信サーバの構成を示す機能ブロック図である。
【図３】地図データベースに記録された地図データの例を示す図である。
【図４】道路データを説明するための図である。
【図５】本発明の実施形態に係る分岐候補要求情報のデータ構成の一例を示す図である。
【図６】本発明の実施形態に係るナビ状態管理情報の一例を示す図である。
【図７】本発明の実施形態に係る分岐候補情報の一例を示す図である。
【図８】本発明の実施形態に係る差分地図データの一例を示した図である。
【図９】本発明の実施形態に係るナビゲーション装置の動作を示すフローチャートである。
【図１０】本発明の実施形態に係るナビゲーションシステムの動作を説明するための図である。
【図１１】本発明の実施形態に係る分岐地点を画面表示した図である。
【図１２】本発明の実施形態に係る地図配信サーバの分岐候補情報生成処理を示すフローチャートである。
【図１３】本発明の実施形態に係るハードディスク地図データベースの更新処理を示すフローチャートである。
【図１４】本発明の実施形態に係る更新候補選択処理を示すフローチャートである。
【図１５】本発明の実施形態に係る地図更新可否判定を示すフローチャートである。
【図１６】本発明の実施形態に係る閾値ｍの算出方法を示すフローチャートである。
【図１７】本発明の実施形態に係る整合性判定処理を示すフローチャートである。
【図１８】整合性判定処理を概念的に説明するための図である。
【図１９】本発明の実施形態に係る更新順序決定処理を示すフローチャートである。
【図２０】本発明のナビゲーションシステムの変形例の構成を示す機能ブロック図である。
【図２１】本発明の地図配信サーバの変形例の構成を示す機能ブロック図である。
【図２２】本発明の変形例の実施形態に係るナビゲーション装置の動作を示すフローチャートである。
【図２３】本発明の変形例の実施形態に係るナビゲーションシステムの動作を説明するための図である。
【発明を実施するための形態】
【００１２】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１３】
図１は、本発明の実施形態に係るナビゲーションシステム１の構成例を示した図である。また、図１において、ナビゲーション装置２の構成例を機能ブロック図として示している。
【００１４】
ナビゲーションシステム１は、ナビゲーション装置２と地図配信サーバ３とを備えて構成される。また、ナビゲーション装置２と地図配信サーバ３とは、通信回線４を介して無線で通信可能に接続されている。
【００１５】
ナビゲーション装置２は、表示部２１、入出力部２２、通信部２３、記憶部２４、メモリ部２５、衛星電波受信部２６、および制御部２０を備えて構成される。なお、この表示部２１、入出力部２２、通信部２３および制御部２０の機能は、例えばナビゲーション装置２のハードディスクに格納されたプログラムをＣＰＵ（Central Processing Unit）がＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００１６】
表示部２１は、液晶ディスプレイ等で構成されており、制御部２０の制御のもとに、ナビゲーション処理に応じて、道路状況あるいは誘導案内等を表示する。また、入出力部２２を介して外部からの指示を入力するための画面を表示する機能を有する。
【００１７】
入出力部２２は、例えば、リモコン、あるいはタッチパネル等を含んで構成され、外部からのナビゲーション装置２への指示を受け付ける。また、制御部２０の制御のもと、ナビゲーション装置２の各種処理に応じて、音声案内等を図示されていないスピーカを通じて出力する機能を有する。
【００１８】
通信部２３は、通信回線４を介して、少なくともナビゲーション装置２の現在位置と、目的地と、ナビゲーション装置２が備える地図データの地図バージョンと、を含んだ分岐候補要求情報を、制御部２０の制御により地図配信サーバ３に送信する機能を有する。また、通信部２３は、ナビゲーション装置２の誘導経路上に抽出された新たな分岐地点の候補である分岐候補情報と差分地図データとを、制御部２０の制御により、地図配信サーバ３から取得する機能を有する。
【００１９】
記憶部２４は、ハードディスクやフラッシュメモリ等の補助記憶装置からなり、差分地図データ記憶部２４１と、ハードディスク地図データベース２４２とを備えて構成される。
【００２０】
差分地図データ記憶部２４１は、制御部２０が通信部２３を介して地図配信サーバ３から受信した差分地図データを記録する機能を有する。ここで、差分地図データとは、更新前後の地図データ間で相互に異なるデータ部分をいう。本実施形態においては、地図バージョンが異なる地図データの差異部分を抽出することにより差分地図データを生成することができる（詳細は後記する）。
【００２１】
また、ハードディスク地図データベース２４２は、概要レベル（例えば１０ｋｍ×１０ｋｍ四方）から詳細レベル（例えば２．５ｋｍ×２．５ｋｍ四方）までの数段階の階層に分けて地域を区分しデータ化された地図データ（以下、単に「地図データ」という。）を、例えばリレーショナルデータベースとして記憶する。
【００２２】
図３は、ハードディスク地図データベース２４２に記憶された地図データのデータ構造の例を示した図である。図３（ａ）は、「概要レベル」の地図データを示し、図３（ｂ）は「詳細レベル」の地図データを示している。この地図データは、地図バージョン、地域コード、および道路データから構成される。さらに、道路データは、「概要レベル」や「詳細レベル」を示すレベル情報と、ナビゲーション装置２の現在位置（自車位置）を中心とする所定の範囲を描画するための描画用道路データと、目的地までの最適経路を探索するための経路計算用道路データと、車両と誘導するための進行方向のマーク等の誘導用テキストデータとを含んで構成される。
【００２３】
また、図４は、経路計算用道路データに含まれる道路データの位置と距離との関連を説明するための図である。図４に示すように、道路データは、緯度と経度によって表される２地点のポイント（ポイントＩＤ）と、その２点間を結ぶリンク（リンクＩＤ）とからなる。また、誘導経路は、複数のリンクが繋がったリンク列で構成される。これらの情報が、地図データとして、ハードディスク地図データベース２４２に記憶されている。
【００２４】
図１に戻り、メモリ部２５は、記憶部２４内のハードディスク地図データベース２４２から読み出され、ナビゲーション装置２の現在位置（自車位置）の所定の範囲（近傍）における地図データであるキャッシュ地図データ２５１を一時的に記憶するための記憶手段であり、ＲＡＭ（Random Access Memory）やキャッシュメモリ等により構成される。
また、衛星電波受信部２６は、衛星からの電波を用いて、ナビゲーション装置２の現在位置（自車位置）に関する情報を受信する機能を有する。
【００２５】
制御部２０は、ナビゲーション装置２全体を制御する機能を有し、ナビゲーション制御部２６０と地図データ更新部２００とを備えて構成される。
【００２６】
ナビゲーション制御部２６０は、自車位置決定部２６１と、目的地設定部（設定部）２６２と、経路探索部２６３と、自車速度検知部２６４と、誘導案内部２６５とを備えて構成され、誘導案内（ナビゲーション処理）の操作全般を制御する機能を有する。
【００２７】
自車位置決定部２６１は、衛星電波受信部２６が受信した情報に基づいて、ナビゲーション装置２の現在位置（自車位置）を算出する機能を有する。また、目的地設定部（設定部）２６２は、入出力部２２を介してユーザが目的地として入力した位置情報を設定する機能を有する。経路探索部２６３は、自車位置決定部２６１によって算出されたナビゲーション装置２の現在位置と、目的地設定部２６２により設定された目的地との間の最適な経路を探索する機能を有する。自車速度検知部２６４は、図示されていない速度センサにより、ナビゲーション装置２が移動する速度（自車速度）を検出する機能を有する。
そして、誘導案内部２６５は、経路探索部２６３が探索した経路に基づいて、表示部２１に目的地までの誘導経路等を表示する。さらに、誘導案内部２６５は、地図配信サーバ３から分岐候補情報取得部２１０が分岐候補情報７００（図７参照）を取得すると、表示部２１に分岐地点の候補を表示させる機能を有する。
【００２８】
地図データ更新部２００は、通信部２３を介して地図配信サーバ３から差分地図データを受信し、ハードディスク地図データベース２４２を更新する機能等を制御する。
地図データ更新部２００は、分岐候補情報取得部２１０と、差分地図データ取得部２２０と、更新地図データ選択部２３０と、更新順序決定部２４０と、地図データ更新処理部２５０とを含んで構成される。
【００２９】
分岐候補情報取得部２１０は、経路探索部２６３が探索した誘導経路上の新たな分岐地点の情報である分岐候補情報７００を要求するための分岐候補要求情報５００を、通信部２３を介して地図配信サーバ３に送信する機能を有する。
【００３０】
図５は、本実施形態に係る分岐候補要求情報５００のデータ構造を示す図である。図５に示すように、分岐候補要求情報５００は、少なくともナビゲーション装置２の現在位置に関する情報である自車位置５０１と、目的地５０２と、ナビゲーション装置２が備える地図データの地図バージョン５０３とを含み、さらに、ナビゲーション装置２の設定状態の情報であるナビ状態管理情報５０４と、経路探索するときに高速道路優先かまたは一般道優先かを示す情報である経路探索モード５０５とを含めることができる。
【００３１】
また、図６は、ナビ状態管理情報５０４の具体的なデータ構造の一例を示している。図６に示すように、ナビ状態管理情報５０４は、ナビ状態属性として、「目的地設定」と「経路探索」とからなり、それぞれナビ状態属性値としてその操作が行われていなければ「未」、操作の最中であれば「操作中」、操作が終了していれば「済」というナビゲーション装置２の情報を示すものである。
【００３２】
分岐候補情報取得部２１０は、さらに、地図配信サーバ３が生成した、誘導経路上に新たに設定される分岐地点の候補である分岐候補情報７００を取得する機能を有する。なお、分岐候補情報７００の具体的なデータ構成については、後記する（図７参照）。
【００３３】
図１に戻り、差分地図データ取得部２２０は、地図配信サーバ３によって生成された分岐候補情報７００の分岐地点が含まれる差分地図データ８００（図８参照）を、地図配信サーバ３から取得し、差分地図データ記憶部２４１に記憶させる機能を有する。
【００３４】
更新地図データ選択部２３０は、ナビゲーション装置２の現在位置（自車位置）から分岐地点までの到達時間と、差分地図データ取得部２２０が取得した差分地図データ８００をナビゲーション装置２が更新するのに要する時間とを比較し、差分地図データ記憶部２４１に記憶された差分地図データ８００のうち、分岐地点の到達時間に更新が間に合う差分地図データ８００を選択する機能を有する。ここで、差分地図データ８００のうち、更新地図データ選択部２３０により、分岐地点の到達時間に更新が間に合うとして選択された差分地図データ８００を更新地図データとする。
【００３５】
また、更新地図データ選択部２３０は、地図更新可否判断部２３１と、整合性判定部２３２とを備えて構成される。
【００３６】
地図更新可否判断部２３１は、自車位置決定部２６１で計算したナビゲーション装置２の現在位置（自車位置）と、自車速度検知部２６４が検知した移動速度とから、分岐地点の候補それぞれまでの到達時間を計算し、差分地図データ８００の更新にかかる所定の時間として設定される閾値よりも、到達時間が長い場合に、地図データ更新部２００による更新が間に合うとして、該当する差分地図データ８００を更新すると判断する機能を有する。このようにすることで、予め更新の必要のない差分地図データ８００は更新対象から除外することができるため、地図更新可否判断部２３１の処理以降の処理、例えば整合性判定部２３２の処理においてはＩ／Ｏボトルネックとなりやすいハードディスクへのアクセスを少なくすることができるばかりでなく、更新順序決定部２４０においては更新順序決定を行うための差分地図データ８００ごとの分岐地点到達時間の算出時間を抑えることになり、ナビゲーション装置２の限られたシステムリソースの中で必要な地図データだけを更新対象をすることができる。
【００３７】
整合性判定部２３２は、地図更新可否判断部２３１において、差分地図データ８００を更新すると判断された更新地図データについて、更新地図データに含まれるリンク列の両端のポイントＩＤが誘導経路上のリンクと連結するか否かについて判定する機能を有する。更新地図データの両端のポイントＩＤが誘導経路上のリンクと連結していない場合には、その道路は、一方通行の道路であり、その分岐にしたがって経路を変更しても、目的地に到達できないため、経路探索部２６３において、誘導経路として探索されないものである。したがって、この整合性判定部２３２の判定により、経路探索および誘導案内を実行する際にユーザに対して混乱のもととなる不整合な差分地図データ８００の更新処理の実施を予め防ぐことができる。
【００３８】
更新順序決定部２４０は、更新地図データ選択部２３０が選択した１つ以上の更新地図データについて、分岐地点までの到達時間が短い順に更新地図データの更新順序を決定する機能を有する。
このようにすることで、更新するための時間の余裕が少ない更新地図データから優先して地図データの更新をすることができる。
【００３９】
地図データ更新処理部２５０は、更新順序決定部２４０によって決定された更新順序にしたがい、更新地図データを用いて、ハードディスク地図データベース２４２を更新する。さらに、更新地図データごとのハードディスク地図データベース２４２の更新を契機として、メモリ部２５に記憶されたキャッシュ地図データ２５１を更新する機能を有する。
また、この地図データ更新処理部２５０の処理は、地図データの区分（レベル）ごとに行われ、まず、最も広い区分である例えば「概要レベル」の更新地図データの更新処理を行ってから、順次狭い区分である「詳細レベル」の更新地図データの更新を行う。このようにすることで、目的値までの到達時間に影響を及ぼす、広い範囲における地図データの更新を優先して経路探索を行うことができる。
【００４０】
次に、地図配信サーバ３について図２を用いて説明する。図２は、地図配信サーバ３の構成例を機能ブロック図として示している。
【００４１】
地図配信サーバ３は、通信回線４を介してナビゲーション装置２と接続され、ナビゲーション装置２から分岐候補要求情報５００を受信し、また、ナビゲーション装置２に対して、分岐候補情報７００（図７参照）や差分地図データ８００（図８参照）等を送信する機能を有する。この地図配信サーバ３は、地図データ記憶部３０と、地図配信制御部３１と、地図配信通信部３２とを備えて構成される。なお、この地図配信制御部３１および地図配信通信部３２の機能は、例えば地図配信サーバ３のハードディスクに格納されたプログラムをＣＰＵがＲＡＭに展開し実行することで実現される。
【００４２】
地図データ記憶部３０は、地図バージョンごとの地図データが、地図データベース３３０Ａ，３３０Ｂ，３３０Ｃに記憶されている記憶装置であり、ハードディスク等により構成される。
【００４３】
地図配信制御部３１は、地図配信サーバ３全体の制御を司り、分岐候補情報生成部３１０と、分岐候補情報送信部３１３と、差分地図データ送信部３１４とを備えて構成される。
【００４４】
分岐候補情報生成部３１０は、ナビゲーション装置２から取得した分岐候補要求情報５００をもとに、地図データ記憶部３０を参照し、誘導経路上の分岐地点の候補のリストを生成する機能を有する。この分岐候補情報生成部３１０は、誘導経路確認部３１１と、差分抽出部３１２とを備えている。
【００４５】
誘導経路確認部３１１は、ナビゲーション装置２から送信された分岐候補要求情報５００に含まれる自車位置５０１と、目的地５０２の情報から最適な誘導経路を再探索する機能を有する。
差分抽出部３１２は、ナビゲーション装置２から送信された分岐候補要求情報５００に含まれる地図バージョン５０３と、地図配信サーバ３が備える地図データの最新の地図バージョンとが異なる場合に、地図配信サーバ３の地図データ記憶部３０に記憶された最新の地図バージョンと、ナビゲーション装置２が備える地図データの地図バージョンとから、変更箇所である差分地図データ８００を生成し、さらに、生成した差分地図データ８００のうち、誘導経路確認部３１１が探索した誘導経路上にポイントＩＤがある分岐地点を抽出する機能を有する。
【００４６】
図７は、分岐候補情報生成部３１０によって生成された分岐候補情報７００の具体的なデータ構造の一例を示す図である。図７に示すように、分岐候補情報７００は、緯度および経度で示される分岐地点と、誘導経路上にポイントＩＤのあるリンクＩＤにより構成される。この分岐候補情報７００によって、誘導経路上に新たに分岐地点が存在することが示される。
【００４７】
図２に戻り、分岐候補情報送信部３１３は、分岐候補情報生成部３１０が生成した分岐候補情報７００を、地図配信通信部３２を介してナビゲーション装置２に送信する機能を有する。
【００４８】
差分地図データ送信部３１４は、差分抽出部３１２により生成された差分地図データ８００を、地図配信通信部３２を介してナビゲーション装置２に送信する機能を有する。
【００４９】
図８は、差分抽出部３１２により生成された差分地図データ８００のデータ構造の一例を示す図である。図８に示すように、差分地図データ８００は、「リンク列名称」と、ナビゲーション装置２の処理によって決定される「更新順序」と、地図データの区分（レベル）情報を含んだ「リンク列ＩＤ」と、「リンク列」とを含んで構成される。また、この「リンク列」は１つ以上のリンクからなり、それぞれ「リンクＩＤ」と、リンクＩＤの両端の地点である「ポイントＩＤ」と、その位置を示す「緯度経度」と、を含んで構成される。
【００５０】
図２に戻り、地図配信通信部３２は、ナビゲーション装置２から送信された分岐候補要求情報５００を受信する機能を有する。また、地図配信制御部３１が生成した分岐候補情報７００および差分地図データ８００をナビゲーション装置２に送信する機能を有する。
【００５１】
次に、図１および図２を参照しつつ、図９〜図１９に沿って、本実施形態に係るナビゲーションシステム１の動作について説明する。
図９は、本実施形態に係るナビゲーション装置２の動作を示すフローチャートである。
【００５２】
まず、ナビゲーション装置２の電源がＯＮにされ、ナビゲーション装置２の初期化処理が行われる（ステップＳ９０１）。
ナビゲーション装置２が起動すると、図１の自車位置決定部２６１が、衛星電波受信部２６からの情報を取得し、ナビゲーション装置２の現在位置（自車位置）を算出する（ステップＳ９０２）。そして、誘導案内部２６５の制御により、表示部２１に自車位置の表示が行われる（ステップＳ９０３）。次に、入出力部２２を介して、ユーザにより目的地の入力が行われ、目的地設定部２６２により、目的地の設定が行われる（ステップＳ９０４）。そして、経路探索部２６３の処理により、自車位置決定部２６１が算出した自車位置と、目的地設定部２６２により設定された目的地との間の経路探索処理が行われる（ステップＳ９０５）。
【００５３】
経路探索処理の後、差分地図データ取得部２２０は、ナビゲーション装置２にユーザにより予め設定されている「地図更新有無確認モード」を確認する。ここで、「地図更新有無確認モード」は、ナビゲーション装置２の地図データの更新処理を行ってよいか、予めユーザに確認するためのモードである。ここで、「Ｙｅｓ」に設定されている場合には、最新の地図データの更新を行うモードであると判断する。一方、「Ｎｏ」と設定されていれば、地図データの更新を行わずにナビゲーション装置２内に備えた地図データを用いてナビゲーション処理を行うことを意味する。
この「地図更新有無確認モード」が「Ｙｅｓ」に設定されている場合は（ステップＳ９０６→Ｙｅｓ）、ステップＳ９０７の差分地図データ取得処理に進む。一方、「Ｎｏ」の場合は（ステップＳ９０６→Ｎｏ）、地図データの更新処理を終了する。
【００５４】
次に、ステップＳ９０６において「Ｙｅｓ」の場合、ナビゲーション装置２における差分地図データ取得処理が行われる（ステップＳ９０７）。この差分地図データ取得処理において、ナビゲーション装置２は、地図配信サーバ３から分岐候補情報７００（図７参照）と、差分地図データ８００（図８参照）とを取得する。なお、この差分地図データ取得処理については、後記し詳細に説明する（図１０参照）。
【００５５】
続いて、ステップＳ９０７において、分岐候補情報７００と差分地図データ８００とを取得すると、次に、ナビゲーション装置２は、ハードディスク地図データベース２４２（図１参照）の更新処理を行う（ステップＳ９０８）。このハードディスク地図データベース２４２の更新処理において、差分地図データ記憶部２４１（図１参照）に記憶された差分地図データ８００のうち、ユーザが指定した経路上に位置し、ナビゲーション装置２内の更新が間に合う分岐地点を含んだ更新地図データを選択する。そして、その選択された更新地図データのうち、分岐地点までの到達時間が短い順に更新地図データについてハードディスク地図データベース２４２を更新する。なお、具体的な処理の流れについては、後記する図１３〜図１９を用いて詳細に説明する。
【００５６】
次に、ハードディスク地図データベース２４２の更新が完了すると、誘導案内（ナビゲーション処理）を行うため、図１の地図データ更新処理部２５０の制御により、ハードディスク地図データベース２４２に新しく記憶された更新地図データを参照して（ステップＳ９０９）、その参照した更新地図データをもとに、図１のメモリ部２５内のキャッシュ地図データ２５１を更新する（ステップＳ９１０）。そして、更新されたキャッシュ地図データ２５１を用いて、誘導案内部２６５が、キャッシュ地図データ２５１をもとに誘導案内処理を行う（ステップＳ９１１）。
【００５７】
続いて、図１の地図データ更新処理部２５０は、ハードディスク地図データベース２４２を更新していない差分地図データ８００があるか否かを判断する（ステップＳ９１２）。そして、更新していない差分地図データ８００がある場合には（ステップＳ９１２→Ｙｅｓ）、ステップＳ９０８に戻り、更新していない差分地図データ８００についてのハードディスク地図データベース２４２の更新処理を行う。
一方、更新していない差分地図データ８００がない場合には（ステップＳ９１２→Ｎｏ）、ナビゲーション装置２の地図データ更新処理を終了する。
【００５８】
次に、図９のステップＳ９０７の差分地図データ取得処理について詳細に説明する。
図１０は、本実施形態に係るナビゲーションシステム１における差分地図データ取得処理の流れを示したフローチャートである。
【００５９】
まず、ナビゲーション装置２の分岐候補情報取得部２１０は、分岐候補要求情報５００を地図配信サーバ３に送信する（ステップＳ１００１）。
次に、地図配信サーバ３は、分岐候補要求情報５００（図５参照）の中から地図バージョン５０３を特定し（ステップＳ１００２）、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンであるか否かを判断する（ステップＳ１００３）。ここで、ナビゲーション装置２の地図バージョンが５０３が、地図配信サーバ３が備える最新の地図バージョンであれば（ステップＳ１００３→Ｙｅｓ）、差分地図データ８００の取得処理を終了する（ステップＳ１０１１）。
一方、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンでなければ（ステップＳ１００３→Ｎｏ）、地図配信サーバ３の誘導経路確認部３１１（図２参照）は、受信した分岐候補要求情報５００に含まれる自車位置５０１と目的地５０２と、経路探索モード５０５を用いて、誘導経路を計算する（ステップＳ１００４）。
【００６０】
次に、地図配信サーバ３は、ナビゲーション装置２の誘導経路上に、少なくともリンクの一端が連結する分岐地点を検索するために分岐候補情報生成処理を行う（ステップＳ１００５）。なお、この分岐候補情報生成処理の詳細については、後記する（図１２参照）。
【００６１】
続いて、分岐候補情報生成処理の結果、分岐地点がない場合には（ステップＳ１００６→Ｎｏ）、差分地図データ８００の取得処理を終了する（ステップＳ１０１１）。一方、分岐地点がある場合には（ステップＳ１００６→Ｙｅｓ）、分岐候補情報７００（図７参照）をナビゲーション装置２へ送信する（ステップＳ１００７）。
【００６２】
そして、ナビゲーション装置２の分岐候補情報取得部２１０（図１参照）は、地図配信サーバ３から分岐候補情報７００を取得すると、誘導案内部２６５の制御により、ナビゲーション装置２の表示部２１（図１参照）に示された誘導経路の画面上に、分岐候補情報７００に基づき分岐地点を表示する（ステップＳ１００８）。
【００６３】
図１１は、地図配信サーバ３から受信した分岐地点を、ナビゲーション装置２の表示部２１に表示させた一例を示した図である。
ナビゲーション装置２が経路探索部２６３（図１参照）で探索した経路上に、誘導案内部２６５の処理により、地図データを更新することにより新たな分岐地点が発生することをユーザに示す。このとき、図１１に示すように、分岐地点を×印等で示したり、あるいは吹き出しによって、例えば「この地点が更新されます」といった表示をすることにより、ユーザにこれから更新される誘導経路があることを示すことができる。
【００６４】
図１０に戻り、ステップＳ１００７において、分岐候補情報７００をナビゲーション装置２に送信した地図配信サーバ３は、その分岐候補情報７００の分岐地点のポイントＩＤが含まれる差分地図データ８００のすべてを、ナビゲーション装置２に送信する（ステップＳ１００９）。そして、差分地図データ８００を受信したナビゲーション装置２は、差分地図データ取得部２２０（図１参照）の制御により、受信した差分地図データ８００を記憶部２４内の差分地図データ記憶部２４１に保存し（ステップＳ１０１０）、差分地図データ取得処理を終了する（ステップＳ１０１１）。
【００６５】
次に、図１０のステップＳ１００５における分岐候補情報生成処理について説明する。
図１２は、分岐候補情報７００を生成する処理の流れを示すフローチャートである。
【００６６】
まず、地図配信サーバ３の差分抽出部３１２（図２参照）は、ナビゲーション装置２の誘導経路を構成するリンク列を抽出する（ステップＳ１２０１）。次に、地図配信サーバ３の地図データ記憶部３０に記憶された最新の地図バージョンの地図データと比較して、ナビゲーション装置２の誘導経路と異なる差分地図データ８００のリンクを抽出する（ステップＳ１２０２）。そして、差分抽出部３１２（図２参照）は、抽出した差分地図データ８００のリンクの両端のポイントＩＤのいずれかが誘導経路を構成するリンク列のポイントＩＤに含まれるか否かを判断する（ステップＳ１２０３）。
【００６７】
次に、ステップＳ１２０３において、差分抽出部３１２は、差分地図データ８００のリンクのポイントＩＤが、ナビゲーション装置２の誘導経路に含まれると判断した場合は（ステップＳ１２０３→Ｙｅｓ）、分岐地点であると判断し、分岐候補情報７００を生成する（ステップＳ１２０４）。一方、ステップＳ１２０３において、差分地図データ８００のリンクのポイントＩＤが、ナビゲーション装置２の誘導経路に含まれないと判断した場合には（ステップＳ１２０３→Ｎｏ）、差分地図データ８００のリンクの両端のポイントＩＤの緯度経度が示す地点と誘導経路との距離が５ｍ以下か否かを判断する（ステップＳ１２０５）。ここで、５ｍ以下であった場合には（ステップＳ１２０５→Ｙｅｓ）、分岐地点であると判断し、分岐候補情報７００を生成する（ステップＳ１２０４）。一方、５ｍよりも長かった場合には（ステップＳ１２０５→Ｎｏ）、次のリンクを判断するため、ステップＳ１２０３に戻る。
ここで、差分地図データ８００のリンクのポイントＩＤの緯度経度が示す地点と誘導経路との距離が５ｍ以下か否かを判断するのは、ポイントＩＤの緯度経度の誤差を考慮したものであり、５ｍ以下であれば、道路は繋がっているものと判断するからである。
【００６８】
そして、ステップＳ１２０４において、分岐候補情報７００を生成した後、ステップＳ１２０６において、すべての差分地図データ８００のリンクについて判断したか否かを判定する（ステップＳ１２０６）。ここで、まだ判断していない差分地図データ８００のリンクがある場合には（ステップＳ１２０６→Ｎｏ）、ステップＳ１２０３に戻り、分岐候補情報生成処理を続ける。一方、すべての差分地図データ８００のリンクについて判断した場合には（ステップＳ１２０６→Ｙｅｓ）、分岐候補情報生成処理を終了する。
この分岐候補情報生成処理により、図７に示すように、ナビゲーション装置２の誘導経路上にある「分岐地点」とその「リンクＩＤ」を示す分岐候補情報７００が生成される。
【００６９】
次に、図９のステップＳ９０８における、ハードディスク地図データベース２４２（図１参照）の更新処理について説明する。図１３は、ナビゲーション装置２の差分地図データ記憶部２４１に記憶された差分地図データ８００を用いて、ハードディスク地図データベース２４２を更新する処理の流れを示すフローチャートである。
【００７０】
まず、ナビゲーション装置２の地図データ更新処理部２５０（図１参照）は、差分地図データ取得部２２０による差分地図データ８００（図８参照）の受信が完了し、さらに、差分地図データ記憶部２４１（図１参照）への差分地図データ８００の保存処理を行う（ステップＳ１３０１）。
【００７１】
ステップＳ１３０１において、地図データ更新処理部２５０は、差分地図データ８００の保存が完了したと判断した場合には、差分地図データ記憶部２４１に記憶した差分地図データ８００の中から、ナビゲーション装置２による更新が間に合う差分地図データ８００である更新地図データを選択する更新候補選択処理を行う（ステップＳ１３０２）。なお、更新候補選択処理の具体的な処理の流れについては、後記する（図１４参照）。
【００７２】
次にステップＳ１３０２において選択された更新地図データの中で、分岐地点とナビゲーション装置２との距離が最も近いため、到達時間が最も短くなるものから順に更新順序を決定する更新順序決定処理を行う（ステップＳ１３０３）。なお、更新順序決定処理の具体的な処理の流れについては、後記する（図１９参照）。
【００７３】
続いて、ステップＳ１３０３において決定された更新順序のうち、最初に更新すべきと判断された更新地図データについて、地図データ更新処理部２５０の制御により、ハードディスク地図データベース２４２の更新処理を行う（ステップＳ１３０４）。
【００７４】
また、ステップＳ１３０４において、地図データ更新処理部２５０が、ハードディスク地図データベース２４２の更新が完了した場合は、ハードディスク地図データベース２４２の更新処理を終了する。
【００７５】
次に、図１３のステップＳ１３０２における更新候補選択処理について説明する。図１４は、ナビゲーション装置２の更新地図データ選択部２３０（図１参照）による更新候補選択処理の流れを示すフローチャートである。
【００７６】
まず、差分地図データ記憶部２４１に記憶された差分地図データ８００の中から１つを選択する（ステップＳ１４０１）。次に、差分地図データ８００を更新しても、ナビゲーション装置２の誘導処理が間に合うか否かを判定する地図更新可否判定処理を行う（ステップＳ１４０２）。具体的には、自車の移動に伴って、差分地図データ８００の更新が間に合わず、更新を終えたときには分岐地点を通過してしまう差分地図データ８００については、地図更新可否判断部２３１（図１参照）は、更新を行う必要がないと判断する。一方、差分地図データ８００の更新が間に合うものについては、地図更新可否判断部２３１が、更新を行う更新地図データとして選択する処理を行う（後記する図１５参照）。
【００７７】
次に、ステップＳ１４０３の整合性判定処理に進み、整合性判定部２３２（図１参照）が、差分地図データ８００の両端のポイントＩＤが探索経路上のリンクと連結するか否かを判定する（後記する図１７参照）。つまり、新たな分岐による道路であっても、途中で行き止まりである場合等には、経路を誘導する必要はない。そのため、その分岐地点における新たな差分地図データ８００による道路が、ナビゲーション装置２が経路探索したもとの道路の繋がった道路であるかの整合性を判定する（ステップＳ１４０３）。
【００７８】
続いて、ステップＳ１４０４に進みすべての差分地図データ８００を処理したか判断する（ステップＳ１４０４）。そして、処理していない差分地図データ８００がある場合には（ステップＳ１４０４→Ｎｏ）、ステップＳ１４０１に戻り、差分地図データ８００の更新候補選択処理を続ける。一方、すべての差分地図データ８００が処理された場合には（ステップＳ１４０４→Ｙｅｓ）、図１３のステップＳ１３０３の更新順序決定処理へと進む。
このようにすることで、図１３に示すハードディスク地図データベース２４２の更新処理の前に、ナビゲーション装置２が地図配信サーバ３から取得した差分地図データ８００の中から更新対象を絞り込むことが可能となるため、ハードディスク地図データベース２４２の更新処理の処理負荷を低減できることになる。このため差分地図データ８００の更新処理が速くなり、最新の地図データによる経路探索と誘導案内の処理にすぐに移ることができるようになる。
【００７９】
次に、図１４のステップＳ１４０２の地図更新可否判定について具体的に説明する。
図１５は、ナビゲーション装置２の地図更新可否判断部２３１による地図更新可否判定の処理の流れを示すフローチャートである。
【００８０】
先ず、地図更新可否判断部２３１（図１参照）は、自車速度検知部２６４（図１参照）から自車の速度を取得する（ステップＳ１５０１）。次に、自車速度と、ナビゲーション装置２の現在位置（自車位置）から更新地図データの分岐地点までの到達時間を計算する（ステップＳ１５０２）。次に、ハードディスク地図データベース２４２を更新するための時間等を考慮して、閾値ｍを算出する（ステップＳ１５０３）。続いて、算出された分岐地点までの到達時間と、閾値ｍとを比較し、閾値ｍよりも分岐地点までの到達時間が長いか否かを判断する（ステップＳ１５０４）。
そして、算出した分岐地点までの到達時間が、閾値ｍよりも長い場合には（ステップＳ１５０４→Ｙｅｓ）、図１４のステップＳ１４０３の整合性判定処理へと進む。一方、算出した分岐地点までの到達時間が、閾値ｍ以下の場合は（ステップＳ１５０４→Ｎｏ）、差分地図データ８００の更新が間に合わないとして、差分地図データ８００の更新を行わず、図１４のステップＳ１４０１に戻り、次の差分地図データ８００の判定処理を行う。
【００８１】
次に、図１５のステップＳ１５０３における閾値ｍの算出方法について説明する。
この閾値ｍは、閾値ｍ＝（経路探索最悪時間ｍ１）＋（画面更新時間ｍ２）＋（ハードディスク地図データベース更新時間ｍ３）＋（キャッシュ地図データ更新時間ｍ４）からなる値である。
図１６は、本実施形態における閾値ｍの算出方法を示した図である。まず、地図更新可否判断部２３１（図１参照）は、経路探索部２６３の設定において、経路探索モードが高速道路優先に設定されているか否かを判断する（ステップＳ１６０１）。ここで、高速道路優先に設定されている場合には（ステップＳ１６０１→Ｙｅｓ）、高速道路であることを考慮した経路探索最悪時間の算出を行う（ステップＳ１６０２）。一方、高速道路優先以外の場合、例えば一般道が優先されている場合には（ステップＳ１６０１→Ｎｏ）、一般道は高速道路よりも経路が複雑であることを考慮して、経路探索最悪時間の算出を行う（ステップＳ１６０３）。
【００８２】
ここで、ステップＳ１６０２とステップＳ１６０３における（経路探索最悪時間ｍ１）は、自車位置と目的地間の２点間の距離にそれぞれの所定値（α，β）を掛けた値である。高速道路優先の場合、所定値αは経路探索時間の実測値から例えば０．０１２５秒／ｋｍとされ、一般道の場合の所定値βは、例えば、０．０２１４秒／ｋｍとされる。
【００８３】
次に、ステップＳ１６０４において、（画面更新時間ｍ２）を計算する。画面更新時間ｍ２は、画面レイヤ数と、画面ごとの画素数と、１画面の転送速度を掛けたものである。
【００８４】
次に、ステップＳ１６０５において、（ハードディスク地図データベース更新時間ｍ３）を計算する。ハードディスク地図データベース更新時間は、ハードディスク地図データベース２４２へのＳＱＬ命令数に、ハードディスクアクセス単位時間（例えば０．０７秒／１ＳＱＬ命令）を掛けた値となる。
【００８５】
次に、ステップＳ１６０６において、（キャッシュ地図データ更新時間ｍ４）を計算する。キャッシュ地図データ更新時間ｍ４は、ハードディスク地図データベース２４２へのＳＱＬ命令数に、ハードディスクアクセス単位時間（例えば０．０７秒／１ＳＱＬ命令）を掛けた値となる。
【００８６】
そして、各ステップにおいて算出したｍ１，ｍ２，ｍ３，ｍ４の値を合計することで、地図更新可否判断部２３１は閾値ｍを算出する。このようにすることで、更新順序を決定する際に、自車位置と自車速度に加えてナビゲーション装置２が備えもつ処理性能やユーザのカーナビ設定情報の種類を用いることによって、より精度の高い更新順序を決定することができるため、ユーザに対してより的確なタイミングで地図更新を行うことが可能となる。
【００８７】
次に、図１４のステップＳ１４０３における整合性判定処理について、図１７および図１８を参照して具体的に説明する。
図１７は、ナビゲーション装置２の整合性判定部２３２の処理の流れを説明するための図である。また、図１８は、本実施形態における整合性判定を概念的に説明するための図である。
【００８８】
図１７において、まず、整合性判定部２３２（図１参照）は、差分地図データ８００に含まれるリンク列の両端のポイントＩＤが、他のリンクと連結しているかどうかについて、ハードディスク地図データベース２４２を検索する（ステップＳ１７０１）。
次に、整合性判定部２３２は、ステップＳ１７０１の結果、ポイントＩＤが他のリンクと連結しているか否かを判定する（ステップＳ１７０２）。ここで、他のリンクと連結されていなければ（ステップＳ１７０２→Ｎｏ）、その差分地図データ８００は、更新する必要がないため、図１４のステップＳ１４０１に戻り、次の差分地図データ８００の判定処理を行う。
一方、他のリンクと連結されていれば（ステップＳ１７０２→Ｙｅｓ）、次のステップＳ１７０３に進む。
【００８９】
ステップＳ１７０３において、整合性判定部２３２は、探索経路上のリンク列について差分地図データ８００の両端のポイントＩＤをキーにしてハードディスク地図上を検索する。
そして、両端のポイントＩＤが探索経路上のリンクと連結するか否かを判断する（ステップＳ１７０４）。ここで、両端のポイントＩＤが探索経路上のリンクと連結しない場合には（ステップＳ１７０４→Ｎｏ）、そのリンク列は、ナビゲーション装置２が探索した探索経路と両端において繋がってないことを意味するため、地図データの更新処理を行わないと判断し、図１４のステップＳ１４０１に戻り、次の差分地図データ８００の判定処理を行う。一方、両端のポイントＩＤが経路探索上のリンクと連結している場合には（ステップＳ１７０４→Ｙｅｓ）、図１４のステップＳ１４０４へと進む。
【００９０】
図１８は、差分地図データ８００がナビゲーション装置２の誘導経路とリンク列の両端において繋がっていることを説明するための図である。図１８に示すように、分岐地点から別経路をたどる差分地図データ８００の両端のポイントＩＤが誘導経路と繋がっているため、探索経路のリンクと差分地図データ８００のリンク列とが連結していると判断される。一方、分岐地点では繋がっていても、差分地図データ８００の片端のポイントＩＤが誘導経路と繋がっていなければ、目的地まで繋がっていないこととなる。したがって、差分地図データ８００のポイントＩＤの両端が、もとの誘導経路と繋がっている必要がある。
このように、整合性判定処理を行うことによって、不必要な差分地図データ８００の更新を避け、更新する必要がある差分地図データ８００か否かの判定をした上で、差分地図データ８００の更新処理を行うことができる。
【００９１】
次に、図１３のステップＳ１３０３における更新順序決定処理について図１９を参照して説明する。図１９は、更新順序決定部２４０（図１参照）が、差分地図データ８００のうち、更新を行う更新地図データと判断されたデータについて、その更新順序を決定する処理の流れを示すフローチャートである。
【００９２】
まず、地図の拡大・縮小の度合いに応じた地図データの内容を管理する単位である区分（レベル）の中から未選択の区分（レベル）を選択する（ステップＳ１９０１）。選択する順序としては、更新地図データのうち、リンク列ＩＤによって識別される最も広い区分（例えば、概要レベル）から詳細レベルに選択することとなる。
次に、ステップＳ１９０１により選択した区分（レベル）の差分地図データ８００を選択する（ステップＳ１９０２）。
次に、選択された差分地図データ８００ごとの分岐地点到達時間を計算する（ステップＳ１９０３）。なお、このステップは、地図更新可否判定（図１５参照）において計算され、メモリ部２５（図１参照）に記憶された計算結果をそのまま利用することもできる。
【００９３】
続いて、更新順序決定部２４０は、計算した分岐地点到達時間が短い順（早い順）に更新処理を実行するように更新地図データの順序を決定する（ステップＳ１９０４）。
【００９４】
次に、更新順序を判断していない区分（レベル）の差分地図データ８００があるか否かを判断する（ステップＳ１９０５）。ここで、更新順序を判断していない区分（レベル）の差分地図データ８００がある場合には（ステップＳ１９０５→Ｙｅｓ）、ステップＳ１９０１に戻り、次に広い区分（レベル）の差分地図データ８００を選択し、ステップＳ１９０２以降の更新順序決定処理を行う。
一方、更新順序を判断していない区分（レベル）の差分地図データ８００がない場合には（ステップＳ１９０５→Ｎｏ）、差分地図データ８００の更新順序決定処理を終了し、図１３のステップＳ１３０４の処理を行う。
なお、地図データ更新処理部２５０は、１つの差分地図データ８００によりハードディスク地図データベース２４２が更新されたことを契機として、キャッシュ地図データ２５１の更新を順次行う（図９のステップＳ９０９〜Ｓ９１０）。
このようにすることで、整合性を担保した上で、経路探索に最も早く必要な差分地図データ８００の順に更新し、更新された差分地図データ８００を考慮して誘導案内をすることができる。
【００９５】
次に、本実施形態の変形例について説明する。
図２０は、本発明の変形例の実施形態に係るナビゲーションシステム１ａの構成例を示した図である。図２０に示すように、この変形例においては、図１のナビゲーション装置２の構成と比較して、分岐候補情報生成部２７０が地図データ更新部２００の新たな機能として加わっている。その他の構成については、図１のナビゲーションシステム１と同一の符号を付し、同様の機能を有するものとして説明を省略する。
【００９６】
この分岐候補情報生成部２７０は、差分地図データ取得部２２０が取得した差分地図データ８００と、経路探索部２６３が探索した誘導経路とに基づいて、誘導経路上にある分岐地点を抽出する機能を有する。これによって、本発明の実施形態のように地図配信サーバ３ａ側で分岐地点を抽出するのではなく、ナビゲーション装置２ａ側で分岐地点を抽出することができる。
【００９７】
次に、本発明の変形例の実施形態に係る地図配信サーバ３ａについて説明する。図２１は、本発明の地図配信サーバ３の変形例を機能ブロック図として示した図である。図２の地図配信サーバ３との違いは、地図配信サーバ３ａにおいては、分岐候補情報７００を生成しないため、地図配信サーバ３が有する分岐候補情報生成部３１０、および分岐候補情報送信部３１３を備えていない。一方で、差分地図データ生成部３１５を備える構成となっている。
【００９８】
差分地図データ生成部３１５は、ナビゲーション装置２ａから取得した分岐候補要求情報５００から、ナビゲーション装置２ａの地図バージョン５０３を特定する。また、受信した自車位置５０１と目的地５０２とから所定の円領域を設定し、その領域内における地図データを参照することで、差分地図データ８００を抽出する機能を有する。
【００９９】
図２２は、本発明の変形例の実施形態に係るナビゲーション装置２ａの動作を示すフローチャートである。図９のナビゲーション装置２の動作と同じ処理を行うステップは同一のステップ名を付し、説明は省略するものとする（ステップＳ９０１〜Ｓ９０４，ステップＳ９０８〜Ｓ９１２の説明は省略）。
図２２の変形例と図９の処理の流れとの違いは、図９においては、経路探索処理（ステップＳ９０５）を終えてから、地図配信サーバ３に対して、差分地図データ取得処理をしているのに対し、図２２の変形例の実施形態においては、目的設定を終えた後に、経路探索処理を行わず、地図配信サーバ３ａに対して、差分地図データ取得処理をしている点が異なる。また、ナビゲーション装置２ａ側で分岐候補情報７００を生成する。
【０１００】
図２２において、まず、差分地図データ取得部２２０は、目的地設定後に「地図更新有無確認モード」が「Ｙｅｓ」に設定されているか否かを確認する（ステップＳ２２０１）。ここで、「Ｎｏ」と設定されていれば（ステップＳ２２０１→Ｎｏ）、地図データの更新処理を行わずにナビゲーション装置２ａ内に備えられた地図データを用いてナビゲーション処理を行う。一方、この「地図更新有無確認モード」が「Ｙｅｓ」の場合は（ステップＳ２２０１→Ｙｅｓ）、差分地図データ取得処理を行って（ステップＳ２２０２）、差分地図データ８００を地図配信サーバ３ａから取得した後、経路探索部２６３により経路探索処理を行い、分岐候補情報生成部２７０が分岐候補情報７００を生成する（ステップＳ２２０３）。その後は、本発明の実施形態と同様の処理を行い、ハードディスク地図データベース２４２とキャッシュ地図データ２５１を更新してナビゲーション処理を行う。
【０１０１】
次に、本発明の変形例の実施形態における差分地図データ取得処理について説明する。図２３は、本発明の変形例の実施形態に係るナビゲーションシステム１ａの差分地図データ取得処理の流れを示したフローチャートである。
【０１０２】
まず、ナビゲーション装置２ａの分岐候補情報取得部２１０は、分岐候補要求情報５００を地図配信サーバ３ａに送信する（ステップＳ１００１）。そして、地図配信サーバ３ａは、図１０の処理と同様に、分岐候補要求情報５００からナビゲーション装置２ａの地図バージョン５０３を特定し（ステップＳ１００２）、ナビゲーション装置２ａの地図バージョン５０３が最新の地図バージョンであるか否かを判断する（ステップＳ１００３）。
そして、ナビゲーション装置２ａの地図バージョン５０３が最新の地図バージョンでなかった場合（ステップＳ１００３→Ｎｏ）、差分地図データ生成部３１５の制御により、受信した自車位置５０１と目的地５０２から決定する所定の円領域を設定する（ステップＳ２３０１）。続いて、設定した円領域に含まれる地図データをＳＱＬの検索処理を用いて空間検索する（ステップＳ２３０２）。なお、本変形例における空間検索の命令文の一例を、図２３においてステップＳ２３０２とともに示す。また、本変形例においては、円領域の空間検索としたが、円領域以外の楕円領域や矩形領域に設定してもよい。このようにすることで、地図配信サーバ３ａからナビゲーション装置２ａが差分地図データ８００を自車位置５０１と目的地５０２で指定される地図上の領域内の必要な分だけ取得することになり、無駄な通信コストを削減できるばかりでなく、取得した差分地図データ８００のハードディスク地図データベース２４２の更新処理の処理時間が軽減できる。
【０１０３】
次に、差分地図データ生成部３１５は、ナビゲーション装置２ａの地図バージョン５０３と最新の地図バージョンの地図データベース３３０を用いて、空間検索された地図データについて、最新バージョンと異なる部分である差分地図データ８００を生成する（ステップＳ２３０３）。
続いて、差分地図データ生成部３１５は、１つ以上の差分地図データ８００が生成されたか否かを判断する（ステップＳ２３０４）。差分地図データ８００が生成されなかった場合には（ステップＳ２３０４→Ｎｏ）、差分地図データ取得処理を終了する。一方、差分地図データ８００が生成された場合には（ステップＳ２３０４→Ｙｅｓ）、生成された差分地図データ８００をナビゲーション装置２ａへ送信する（ステップＳ２３０５）。
ナビゲーション装置２ａは、差分地図データ取得部２２０により、差分地図データ８００を取得すると、記憶部２４内の差分地図データ記憶部２４１に差分地図データ８００を保存する（ステップＳ１０１０）。
次に、ナビゲーション装置２は、経路探索部２６３により経路計算を行い、分岐候補情報生成部２７０が、図１２に示した分岐候補情報生成処理と同様の処理を行って、分岐候補情報７００の生成を行う（ステップＳ２３０６）。
【０１０４】
このようにすることで、本発明の実施形態に係るナビゲーション装置、ナビゲーション方法およびナビゲーションシステムは、更新が間に合う差分地図データ８００について、分岐地点までの到達時間が短い順に差分地図データ８００の更新を行うことができる。そして、更新した差分地図データ８００をもとに、誘導案内を行うことが可能となる。
【０１０５】
本発明のさらなる変形例の実施形態における差分地図データ取得処理について、図１０を用いて説明する。
まず、ナビゲーション装置２の分岐候補情報取得部２１０は、分岐候補要求情報５００（図５参照）を地図配信サーバ３に送信する（ステップＳ１００１）。
次に、地図配信サーバ３は、ナビゲーション装置２から受信した分岐候補要求情報５００の中から経路探索モード５０５内にて保持される経路探索部識別子５０５５および地図バージョン５０３を特定し（ステップＳ１００２）、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンであるか否かを判断すると同時にナビゲーション装置２において用いられている経路探索アプリを特定する（ステップＳ１００３）。ここで経路探索部識別子５０５５は、少なくとも地図配信サーバ３とナビゲーション装置２との間で、経路探索部の一意性を保障するための取り決めがなされているのが前提である。そして、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンであれば（ステップＳ１００３→Ｙｅｓ）、差分地図データ８００の取得処理を終了する（ステップＳ１０１１）。
一方、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンでなければ（ステップＳ１００３→Ｎｏ）、地図配信サーバ３の誘導経路確認部３１１（図２参照）は、受信した分岐候補要求情報５００に含まれる自車位置５０１と、目的地５０２と、経路探索モード５０５とを用いて、地図配信サーバ３が予め各種ナビゲーション装置２のそれぞれのメーカから調達し備え持つ差分地図データ取得用経路探索部群３１１３の中から、経路探索部識別子５０５５により特定された最適な差分地図データ取得用経路探索部３１１５を選択し、誘導経路を計算する（ステップＳ１００４）。この処理により、地図配信サーバ３は、ナビゲーション装置２の機種の違いに伴う各機種の誘導経路の違いを考慮した差分地図の的確な選択と無駄のない差分地図配信が可能となる。
【０１０６】
本発明のさらなる変形例の実施形態における差分地図データ取得処理について、図１０を用いて説明する。
まず、ナビゲーション装置２の分岐候補情報取得部２１０は、分岐候補要求情報５００（図５参照）を地図配信サーバ３に送信する（ステップＳ１００１）。
次に、地図配信サーバ３は、分岐候補要求情報５００の中から経路探索モード５０５内にて保持される誘導経路データ（図４参照）および地図バージョン５０３を特定し（ステップＳ１００２）、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンであるか否かを判断する（ステップＳ１００３）。ここで、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンであれば（ステップＳ１００３→Ｙｅｓ）、差分地図データ８００の取得処理を終了する（ステップＳ１０１１）。
一方、ナビゲーション装置２の地図バージョン５０３が、地図配信サーバ３が備える最新の地図バージョンでなければ（ステップＳ１００３→Ｎｏ）、地図配信サーバ３の誘導経路確認部３１１（図２参照）は、受信した分岐候補要求情報５００に含まれる自車位置５０１と、目的地５０２と、経路探索モード５０５と、誘導経路データ（図４参照）とを選択し、誘導経路として採用する（ステップＳ１００４）。この処理により、ナビゲーション装置２の機種の違いに伴う各機種ごとの誘導経路の違いの影響を受けることなく、地図配信サーバ３ではナビゲーション装置２において計算された誘導経路を加味した差分地図の効率的な選択と無駄のない配信が可能となる。
【符号の説明】
【０１０７】
１      ナビゲーションシステム
２      ナビゲーション装置
３      地図配信サーバ
４      通信回線
２０    制御部
２１    表示部
２２    入出力部
２３    通信部
２４    記憶部
２５    メモリ部
２６    衛星電波受信部
３０    地図データ記憶部
３１    地図配信制御部
３２    地図配信通信部
２００  地図データ更新部
２１０  分岐候補情報取得部
２２０  差分地図データ取得部
２３０  更新地図データ選択部
２３１  地図更新可否判断部
２３２  整合性判定部
２４０  更新順序決定部
２４１  差分地図データ記憶部
２４２  ハードディスク地図データベース
２５０  地図データ更新処理部
２５１  キャッシュ地図データ
２６０  ナビゲーション制御部
２６１  自車位置決定部
２６２  目的地設定部（設定部）
２６３  経路探索部
２６４  自車速度検知部
２６５  誘導案内部
２７０，３１０  分岐候補情報生成部
３１１  誘導経路確認部
３１２  差分抽出部
３１３  分岐候補情報送信部
３１４  差分地図データ送信部
３３０  地図データベース
５００  分岐候補要求情報
７００  分岐候補情報
８００  差分地図データ
【図１】
0005400771.tif 000002
【図２】
0005400771.tif 000003
【図３】
0005400771.tif 000004
【図４】
0005400771.tif 000005
【図５】
0005400771.tif 000006
【図６】
0005400771.tif 000007
【図７】
0005400771.tif 000008
【図８】
0005400771.tif 000009
【図９】
0005400771.tif 000010
【図１０】
0005400771.tif 000011
【図１１】
0005400771.tif 000012
【図１２】
0005400771.tif 000013
【図１３】
0005400771.tif 000014
【図１４】
0005400771.tif 000015
【図１５】
0005400771.tif 000016
【図１６】
0005400771.tif 000017
【図１７】
0005400771.tif 000018
【図１８】
0005400771.tif 000019
【図１９】
0005400771.tif 000020
【図２０】
0005400771.tif 000021
【図２１】
0005400771.tif 000022
【図２２】
0005400771.tif 000023
【図２３】
0005400771.tif 000024