(57)【特許請求の範囲】
【請求項１】
ネットワークを介してサーバと通信することができる経路探索装置であって、
少なくとも出発地の周囲を含む第１の経路ネットワーク情報と、前記第１の経路ネットワーク情報よりも経路ネットワークの詳細度が低い第２の経路ネットワーク情報であって、少なくとも出発地から目的地までの範囲を含む第２の経路ネットワーク情報を記憶した記憶手段と、
前記サーバと通信する通信手段と、
前記通信手段が前記サーバと通信できない場合、前記記憶手段に記憶された前記第１の経路ネットワーク情報で少なくとも出発地の周囲の第１の経路を探索し、前記第１の経路ネットワーク情報がない範囲の第２の経路を前記第２の経路ネットワーク情報で探索する経路探索手段と、を有し、
前記経路探索手段は、
出発地から目的地への経路が、前記第１の経路と前記第２の経路とを跨ぐ場合には、前記第１の経路と前記第２の経路とを接続すること、を特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、
前記第２の経路ネットワーク情報の中から、前記第１の経路の一端部と位置が一致するノード又はリンク補間点を探索し、該ノード又はリンク補間点を中継して、前記第１の経路と前記第２の経路とを接続すること、を特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路探索手段は、
前記第２の経路ネットワーク情報の中から、前記第１の経路の一端部と位置が一致するノード又はリンク補間点を探索できない場合には、前記第１の経路の一端部と所定距離内に位置するノード又はリンク補間点を探索し、該ノード又はリンク補間点を中継して、前記第１の経路と前記第２の経路とを接続すること、を特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記第２の経路を有する前記第１の経路ネットワーク情報を取得する取得手段を有し、
前記経路探索手段は、
前記取得手段により前記第２の経路を有する前記第１の経路ネットワーク情報が取得されると、該第１の経路ネットワーク情報を用いて、前記第２の経路ネットワーク情報を用いて探索した前記第２の経路よりも詳細度の高い第２の経路を再探索すること、
を特徴とする請求項１ないし３の何れか一項に記載の経路探索装置。
【請求項５】
ネットワークを介してサーバと通信することができるコンピュータを、
少なくとも出発地の周囲を含む第１の経路ネットワーク情報と、前記第１の経路ネットワーク情報よりも経路ネットワークの詳細度が低い第２の経路ネットワーク情報であって、少なくとも出発地から目的地までの範囲を含む第２の経路ネットワーク情報とを記憶した記憶手段と、
前記サーバと通信する通信手段と、
前記通信手段が前記サーバと通信できない場合、前記記憶手段に記憶された前記第１の経路ネットワーク情報で少なくとも出発地の周囲の第１の経路を探索し、前記第１の経路ネットワーク情報がない範囲の第２の経路を前記第２の経路ネットワーク情報で探索する経路探索手段として機能させ、
前記経路探索手段は、
出発地から目的地への経路が、前記第１の経路と前記第２の経路とを跨ぐ場合には、前記第１の経路と前記第２の経路とを接続すること、を特徴とする経路探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置及び経路探索プログラムに関する。
【背景技術】
【０００２】
近年、スマートフォンなどの携帯端末で実現されるナビゲーションシステムが広く利用されている。ナビゲーションシステムのサーバ側は、地図データを生成したり、経路探索を実行し、生成した地図データや探索した探索経路を携帯端末に送信する。携帯端末は、サーバ側から受信した地図データや探索経路を、Ｗｅｂブラウザやアプリケーションを介して表示する。
【０００３】
昨今、携帯端末（例えば、スマートフォン）の数が増大するにつれて、サーバ負担が増加している。一方、携帯端末の機能性能も著しく向上している。このような背景から、経路探索の機能を持つ携帯端末も提案されてきている。但し、地図データは、データの最新性を保つため、サーバ側で保持する。この場合、携帯端末は、サーバから必要な地図データや、経路探索に用いる道路ＮＷデータを都度取得し、取得した地図データや道路ＮＷデータを用いて、地図を表示更新したり、経路探索を実行する。
【０００４】
しかしながら、このような携帯端末の場合、携帯端末側が通信できない状態になると（圏外等）、地図データや道路ＮＷデータを取得できないので、経路案内を中断せざるを得ないことがある。
【０００５】
これに関する技術として、例えば、特許文献１には、サーバが出発地から目的地までを含む全領域地図データを予め端末に配信し、端末が通信不能領域に移動した場合、端末は全領域地図データを用いて経路案内を行う発明が記載されている。
【０００６】
ここで、上述の地図データ及び道路ＮＷデータには、レベルがある。地図データの場合、例えば、レベル３は最も上位の広域地図（いわば最も粗い地図）であり、レベル１は最も下位の詳細地図（いわば最も細かい地図）である。また、道路ＮＷデータの場合、例えば、レベル３は幹線道路だけの道路ＮＷデータであり、レベル１は細い道路までも含む詳細な道路ＮＷデータである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−３２８５９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１記載の発明では、通信不能領域では急に全領域地図（例えば、レベル３）を用いた経路案内がなされるため、広域地図上では、詳細地図だと利用できる各種施設や細い道路を使った案内ができないなど、ユーザの利便性が低下するという問題がある。
【０００９】
本発明は上記の点に鑑みて提案されたものであり、その目的とするところは、通信できない状態になった場合でも、携帯端末側で保持するキャッシュデータの範囲内で、適切な経路探索を実行することにある。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明にかかる経路探索装置は、  ネットワークを介してサーバと通信することができる経路探索装置であって、少なくとも出発地の周囲を含む第１の経路ネットワーク情報と、前記第１の経路ネットワーク情報よりも経路ネットワークの詳細度が低い第２の経路ネットワーク情報であって、少なくとも出発地から目的地までの範囲を含む第２の経路ネットワーク情報を記憶した記憶手段と、前記サーバと通信する通信手段と、前記通信手段が前記サーバと通信できない場合、前記記憶手段に記憶された前記第１の経路ネットワーク情報で少なくとも出発地の周囲の第１の経路を探索し、前記第１の経路ネットワーク情報がない範囲の第２の経路を前記第２の経路ネットワーク情報で探索する経路探索手段と、を有し、前記経路探索手段は、出発地から目的地への経路が、前記第１の経路と前記第２の経路とを跨ぐ場合には、前記第１の経路と前記第２の経路とを接続すること、を特徴とする。
【発明の効果】
【００１１】
本発明の実施の形態によれば、携通信できない状態になった場合でも、携帯端末側で保持するキャッシュデータの範囲内で、適切な経路探索を実行することができる。
【図面の簡単な説明】
【００１２】
【図１】経路探索システム１００の一例を示す図である。
【図２】経路探索システム１００のハードウェア構成例を示す図である。
【図３】経路探索システム１００のソフトウェア構成例を示す図である。
【図４】地図データ及び道路ＮＷデータのレベルを示す模式図である。
【図５】地図データ及び道路ＮＷデータのキャッシュ状態を示す模式図（その１）である。
【図６】地図データ及び道路ＮＷデータのキャッシュ状態を示す模式図（その２）である。
【図７】経路探索の探索例を示す模式図（その１）である。
【図８】経路探索の探索例を示す模式図（その２）である。
【図９】経路同士の接続例を示す模式図（その１）である。
【図１０】経路同士の接続例を示す模式図（その２）である。
【図１１】探索結果を表示した画面例を示す図である。
【図１２】経路探索の再探索例を示す模式図である。
【図１３】携帯端末２の経路探索処理を示すフローチャート図である。
【発明を実施するための形態】
【００１３】
以下、本発明の好適な実施形態につき説明する。
【００１４】
[システム構成]
（ネットワーク構成）
図１は、本実施形態にかかる経路探索システム１００の一例を示す図である。経路探索システム１００は、サーバ１及び携帯端末２が、ネットワーク３を介して接続される。
【００１５】
サーバ１は、全ての地図データ及び道路ＮＷデータを保持する。地図データ及び道路ＮＷデータは、最新のデータが保たれており、変更が生じる度、最新の情報に更新される。また、サーバ１は、携帯端末２から地図データ及び道路ＮＷデータの取得要求を受信すると、要求のあったエリアの地図データ及び道路ＮＷデータを携帯端末２に送信する。
【００１６】
携帯端末２は、汎用のＷｅｂブラウザやナビゲーション用のアプリケーションを予め有し、スマートフォンやタブレット端末などに代表される携帯型の情報端末である。利用者（ユーザ）が所持する。携帯端末２は、地図を表示する場合、サーバ１に対して必要な地図データを要求し、受信した地図データを、Ｗｅｂブラウザやアプリケーションを介して表示する。また、携帯端末２は、利用者が出発地及び目的地の入力を行うと、サーバ１に対して必要な道路ＮＷデータを要求し、受信した道路ＮＷデータを用いて、地図上の経路探索を実行する。検索結果は、地図上、探索経路として表示される。
【００１７】
ネットワーク３は、無線の通信ネットワークである。例えば、電話回線網、ＷｉＦｉ（登録商標）、及びインターネットなどを含む。
【００１８】
このように、本実施形態にかかる経路探索システム１００において、最新のデータを保つため、地図データ及び道路ＮＷデータは、サーバ１側で保持される。携帯端末２は、必要に応じて、サーバ１に対して地図データや道路ＮＷデータを要求し、受信した地図データや道路ＮＷデータを用いて、地図表示や経路探索を実行する。
【００１９】
（ハードウェア構成）
図２は、本実施形態にかかる経路探索システム１００のハードウェア構成例を示す図である。図２に示されるように、サーバ１は、ハードウェア構成として、ＣＰＵ（Central Processing Unit）１１、ＲＯＭ（Read Only Memory）１２、ＲＡＭ（Random Access Memory）１３、ＨＤＤ（Hard Disk Drive）１４、入力装置１５、表示装置１６、通信装置１７を有する。
【００２０】
ＣＰＵ１１は、各種プログラムの実行や演算処理を行う。ＲＯＭ１２は、起動時に必要なプログラムなどが記憶されている。ＲＡＭ１３は、ＣＰＵ１１での処理を一時的に記憶したり、データを記憶したりする作業エリアである。ＨＤＤ１４は、各種データ及びプログラムを格納する。入力装置１５は、例えばキーボードやマウスである。表示装置１６は、ディスプレイであり、例えば、ナビゲーションの経路等が表示される。通信装置１７は、ネットワーク３を介し、他装置との通信を行う。
【００２１】
携帯端末２は、サーバ１の有する構成に加え、さらに音声入出力装置１８、ＧＰＳ受信装置１９を有する。
【００２２】
音声入出力装置１８は、音声の入出力を行う装置であり、例えば、利用者をナビするための音声データなどが出力される。ＧＰＳ受信装置１９は、現在位置をＧＰＳ衛星より受信する。
【００２３】
なお、携帯端末２の入力装置１５は、キーボードやマウスに代え、画面上のタップ座標（タッチ座標）を検知可能なタッチパネルにより実現されうる。またこの場合、入力操作は、画面上のタッチパネルと、プログラムにより制御されるソフトウェアキー等とにより実現される。
【００２４】
（ソフトウェア構成）
図３は、本実施形態にかかる経路探索システム１００のソフトウェア構成例を示す図である。まず、サーバ１は、主な機能部として、データ提供部１０１、記憶部１０２を有する。
【００２５】
データ提供部１０１は、携帯端末２から地図データ及び道路ＮＷデータの取得要求を受信すると、要求のあったエリアの地図データ及び道路ＮＷデータを携帯端末２に送信（提供）する。
【００２６】
記憶部１０２は、全ての地図データ及び道路ＮＷデータを記憶している。地図データ及び道路ＮＷデータは、最新のデータが保たれており、変更が生じる度、最新の情報に更新される。
【００２７】
ここで、地図データ（地図背景データ）は、いわゆるマップ画像である。地図を表示する際に用いられる。これに対し、道路ＮＷデータは、経路探索に用いられる道路情報である。つまり、道路ＮＷデータは、例えば、道路の種類、長さ、幅、交通標識など、道路の「情報」である。なお、探索結果は、マップ上に（マップ上の道路画像上に）、ルートが表示される。このため、経路探索時点では道路ＮＷデータが用いられるが、探索結果表示時には、地図データも用いられる。
【００２８】
また、地図データ及び道路ＮＷデータには、レベル（詳細度）がある。地図データの場合、例えば、レベル３は最も上位の広域地図（いわば最も粗い地図）であり、一方、レベル１は最も下位の詳細地図（いわば最も細かい地図）である。また、道路ＮＷデータの場合、例えば、レベル３は幹線道路だけの道路ＮＷデータであり、一方、レベル１は細い道路までも含む詳細な道路ＮＷデータである。
【００２９】
次に、携帯端末２は、主な機能部として、データ取得部２０１、経路探索部２０２、表示部２０３、記憶部２０４を有する。
【００３０】
データ取得部２０１は、必要な地図データ及び道路ＮＷデータが発生すると、サーバ１に対して、必要分の地図データ及び道路ＮＷデータの取得要求を送信することで、必要な地図データ及び道路ＮＷデータを受信（取得）する。受信した地図データ及び道路ＮＷデータは、記憶部２０４においてキャッシュデータとして記憶される。
【００３１】
ここで例えば、利用者が携帯端末２の画面上で現在位置を表示しようとする際、必要な地図データは、現在位置を含むエリアの地図データである。また、現在位置を出発地として経路探索が実行される場合、必要な道路ＮＷデータは、現在位置を含むエリア〜目的地を含むエリアの道路ＮＷデータである。
【００３２】
但し、必要な地図データ及び道路ＮＷデータが発生した場合でも、携帯端末２が通信圏外等で通信できない状態にあると、言うまでもなく、データ取得部２０１は、必要分の地図データ及び道路ＮＷデータを取得することはできない。
【００３３】
経路探索部２０２は、記憶部２０４に記憶された道路ＮＷデータを用いて、出発地から目的地への経路を探索する。
【００３４】
経路探索には道路ＮＷデータが用いられるが、経路探索部２０２は、記憶部２０４に必要な道路ＮＷデータが記憶されている場合（キャッシュされている場合）、効率性や合理性等の観点からサーバ１に対して道路ＮＷデータを要求せず、記憶部２０４に記憶されている道路ＮＷデータを用いて、経路探索を実行する。
【００３５】
一方、記憶部２０４に必要な道路ＮＷデータが記憶されていない場合（キャッシュされていない場合）、携帯端末２が通信圏内等で通信できる状態にあれば、サーバ１に対して道路ＮＷデータを要求し、受信した道路ＮＷデータ（受信して記憶部２０４に記憶された道路ＮＷデータ）を用いて、地図上の経路探索を実行する。
【００３６】
表示部２０３は、地図上に探索経路が引かれるなどして、探索経路を画面上に表示する。
【００３７】
記憶部２０４は、データ取得部２０１により取得された地図データ及び道路ＮＷデータを記憶する。つまり、既に取得済みの地図データ及び道路ＮＷデータが、携帯端末２のキャッシュデータとして記憶される。
【００３８】
なお、上記各機能部は、サーバ１又は携帯端末２を構成するコンピュータのＣＰＵ１１、ＲＯＭ１２、ＲＡＭ１３等のハードウェア資源上で実行されるコンピュータプログラムによって実現される。これらの機能部は、「手段」、「モジュール」、「ユニット」、又は「回路」に読替えてもよい。
【００３９】
（地図データ及び道路ＮＷデータ）
図４は、本実施形態にかかる地図データ及び道路ＮＷデータのレベルを示す模式図である。図４に示されるように、地図データ及び道路ＮＷデータには、同一エリアであっても、レベル（詳細度）の異なる複数のデータがある。
【００４０】
レベル３の地図データは、最も上位の広域地図（いわば最も粗い地図）である。これに対し、レベル１の地図データは、最も下位の詳細地図（いわば最も細かい地図）である。詳しい地図を詳細に表示したい場合は、レベル１の地図データの表示が適切である。
【００４１】
また、例えば、レベル３の道路ＮＷデータは、幹線道路だけの道路ＮＷデータである。これに対し、レベル１の道路ＮＷデータは、細い道路までも含む詳細な道路ＮＷデータである。詳しい経路を詳細に探索したい場合は、レベル１の道路ＮＷデータを用いた経路が適切である。
【００４２】
なお、図４に示される道路ＮＷデータは、道路図の如く描かれているが、あくまで概念的に図示したものである。即ち、道路ＮＷデータの実体は、例えば、道路の種類、長さ、幅、交通標識など、道路の「情報」である。
【００４３】
[経路探索例]
次いで、本実施形態にかかる経路探索システム１００の経路探索について、図面を参照しながら説明する。
【００４４】
（キャッシュデータ）
図５は、本実施形態にかかる地図データ及び道路ＮＷデータのキャッシュ状態を示す模式図（その１）である。地図データ及び道路ＮＷデータ中、空白はデータがないことを示す。これに対し、斜線は、データがキャッシュされていることを示す。
【００４５】
本実施形態において、図５に示されるように、携帯端末２の記憶部２０４には、既にレベル３の地図データ及び道路ＮＷデータがキャッシュされているものとする（前提）。これは例えば、ナビ利用開始のセットアップ時などで、最も上位の地図データ及び道路ＮＷデータが、データ取得部２０１により取得され記憶部２０４にキャッシュされうる。
【００４６】
図６は、本実施形態にかかる地図データ及び道路ＮＷデータのキャッシュ状態を示す模式図（その２）である。
【００４７】
例えば、携帯端末２の画面上、現在地Ａを含むエリアにおけるレベル１の地図が表示要求された場合、データ取得部２０１は、サーバ１に対して、表示に用いられる少なくともレベル１の地図データの取得要求を送信することで、レベル１の地図データを受信（取得）する。勿論、携帯端末２（データ取得部２０１）が圏内等で通信できる状態にある。
【００４８】
また、データ取得部２０１は、携帯端末２が位置する現在地Ａを含むエリアの広域地図の表示要求に備え、サーバ１に対して、現在地Ａを含むエリアに対応するレベル２及びレベル３の地図データの取得要求を送信することで、そのレベル２及びレベル３の地図データを受信（取得）する。
【００４９】
また、データ取得部２０１は、携帯端末２が位置する現在地Ａからの経路探索要求に備え、サーバ１に対して、現在地Ａを含むエリアに対応するレベル１、レベル２及びレベル３の道路ＮＷデータの取得要求を送信することで、そのレベル１、レベル２及びレベル３の道路ＮＷデータを受信（取得）する。
【００５０】
この結果、図６に示されるように、現在地Ａを含むエリアに対応するレベル１、レベル２及びレベル３の地図データ、並びに、レベル１、レベル２及びレベル３の道路ＮＷデータが記憶部２０４にキャッシュされる。
【００５１】
このように、データ取得部２０１は、全エリアの地図データ及び道路ＮＷデータを予め取得せず、必要となったエリアの地図データ及び道路ＮＷデータを取得する。また、一旦取得した地図データ及び道路ＮＷデータは、記憶部２０４にキャッシュされる。
【００５２】
（経路探索）
図７は、本実施形態にかかる経路探索の探索例を示す模式図（その１）である。利用者が出発地Ａ（＝現在地Ａ）及び目的地Ｂの入力を行うと、経路探索部２０２は、まずは記憶部２０４に記憶された道路ＮＷデータを用いて、出発地から目的地への経路を探索しようとする。
【００５３】
経路探索部２０２は、記憶部２０４に必要な道路ＮＷデータが記憶されている場合（キャッシュされている場合）、記憶部２０４に記憶されている道路ＮＷデータを用いて、経路探索を実行する。
【００５４】
ここで、本実施形態においては、図７に示されるように、出発地Ａを含むエリアのレベル１の道路ＮＷデータがキャッシュされているものの、目的地Ｂを含むエリアのレベル１の道路ＮＷデータがキャッシュされていない。レベル１の道路ＮＷデータは、細い道路までも含む詳細な道路ＮＷデータであるので、目的地Ｂへの詳しい経路を詳細に探索しナビするには、出発地Ａから目的地Ｂへの全経路を含むエリアのレベル１の道路ＮＷデータが必要となる。
【００５５】
よって、記憶部２０４に必要な道路ＮＷデータが記憶されていない場合（キャッシュされていない場合）、携帯端末２（データ取得部２０１）が圏内等で通信できる状態にあれば、サーバ１に対して出発地Ａから目的地Ｂへの全経路を含むエリアのレベル１の道路ＮＷデータを要求する。そして、経路探索部２０２は、受信した道路ＮＷデータ（受信して記憶部２０４に記憶された道路ＮＷデータ）を用いて、出発地Ａから目的地Ｂへの詳細な経路探索を実行する。
【００５６】
しかしながら、本実施形態においては、このタイミングで、携帯端末２が通信圏外等で通信できない状態を想定する（前提とする）。言うまでもなく、データ取得部２０１は、必要分の地図データ及び道路ＮＷデータの取得することはできない。とはいうものの、地図データや道路ＮＷデータを取得できないことを理由として、経路探索や経路案内を中断するとなると、利用者の利便性が低下することになる。
【００５７】
従って、経路探索部２０２は、記憶部２０４のキャッシュの範囲内の道路ＮＷデータを用いて経路探索を行うようにする。即ち、本実施形態においては、レベル１の道路ＮＷデータがキャッシュされている範囲内では、レベル１の道路ＮＷデータを用いて詳細な経路探索を行う。レベル１の道路ＮＷデータがキャッシュされていないものの、いずれか上位レベルの道路ＮＷデータがキャッシュされているのであれば、その道路ＮＷデータを用いて、レベル１と同等の詳細度とはいえないものの、その上位レベルの道路ＮＷデータの範囲内で経路探索を行う。
【００５８】
図８は、本実施形態にかかる経路探索の探索例を示す模式図（その２）である。
【００５９】
図８に示されるように、経路探索部２０２は、出発地Ａから目的地Ｂへの経路をする場合、出発地Ａからはまずレベル１の道路ＮＷデータを用いて経路１０を探索する。レベル１の道路ＮＷデータがない場合、それよりも上位であってなるべくレベルの低い道路ＮＷデータがキャッシュにあれば、レベル１の道路ＮＷデータの範囲を超えた範囲については、上位レベル３の道路ＮＷデータを用いて経路３０を探索する。つまり、経路探索部２０２は、レベル１の道路ＮＷデータとレベル３の道路ＮＷデータという異なるレベルの道路ＮＷデータを跨いで、経路を探索する。
【００６０】
ここで、レベル１の道路ＮＷデータには、例えば、県道や私道など詳細な道路のデータを含んでいる。これに対し、レベル３の道路ＮＷデータには、例えば、幹線道路など主要道路のみのデータしか含まれていない。
【００６１】
例えば、レベル１の道路ＮＷデータ内の経路１０が幹線道路である場合、レベル３の道路ＮＷデータ内の経路３０と一致するので、経路１０の接続点Ｃ１と経路３０の接続点Ｃ３とを接続することで、探索経路を生成することが可能である。
【００６２】
しかし、レベル１の道路ＮＷデータ内の経路１０が県道である場合、レベル３の道路ＮＷデータ内には情報として県道は含まれておらず、レベル３の道路ＮＷデータ内の経路３０と一致しない。よって、経路１０の接続点Ｃ１と経路３０の接続点Ｃ３とは完全に一致しないという問題がある。
【００６３】
図９は、本実施形態にかかる経路同士の接続例を示す模式図（その１）である。
【００６４】
経路探索部２０２は、レベル３の道路ＮＷデータの中から、経路１０の端部に位置する接続点Ｃ１の位置と一致するノードＣ３又は補間点Ｃ３を探索し、一致するノードＣ３又は補間点Ｃ３が存在する場合、接続点Ｃ１と、ノードＣ３又は補間点Ｃ３とを接続することで、接続点Ｃ１−Ｃ３を中継する探索経路を生成する。
【００６５】
なお、道路ＮＷは、大きく、交差点その他道路網表現上の結節点である「ノード」と、ノードとノードの間の道路区間である「リンク」の組み合わせによって構成される。また、ノード間のリンク上、カーブを表現したりノード同士の接続を滑らかにするための「補間点」が存在する。道路ＮＷデータは、ノードの情報（例えば、位置、交差点、交差角度、信号、車幅・車線、交通標識など）、補間点の情報（例えば、位置、カーブ角度）、及びリンクの情報（例えば、位置、信号、車幅・車線、交通標識など）を有する。このため、ノード、リンク及び補間点は、これら情報に基づいて、経路同士の接続点となりうる。
【００６６】
図１０は、本実施形態にかかる経路同士の接続例を示す模式図（その２）である。
【００６７】
経路探索部２０２は、レベル３の道路ＮＷデータの中から、経路１０の端部に位置する接続点Ｃ１の位置と一致するノードＣ３又は補間点Ｃ３を探索するものの、一致するノードＣ３又は補間点Ｃ３が存在しない場合、経路１０の端部に位置する接続点Ｃ１の位置と所定距離Ｌ内に位置するノードＣ３又は補間点Ｃ３を探索する。レベル３の道路ＮＷデータの中に、所定距離Ｌ内に位置するノードＣ３又は補間点Ｃ３が存在する場合、接続点Ｃ１と補間点Ｃ３とを接続することで、接続点Ｃ１−Ｃ３を中継する探索経路を生成する。
【００６８】
なお、表示画面中、Ｃ１−Ｃ３の経路は、空白の経路となるが、表示上は便宜的に、例えば実線や点線で補間したりすればよい。
【００６９】
なお、探索経路は、様々な複数の経路を組み合わせ、総コスト計算を行うことで、最終的な１の経路を探索する。例えば、レベル１の道路ＮＷデータとレベル３の道路ＮＷデータとを同時に用いて、両道路ＮＷデータ上から導出される複数の経路を取得し、それぞれの経路毎の総コスト計算を行うことで、最もコストの小さい１の経路を探索しうる。
【００７０】
（探索結果の表示画面例）
図１１は、本実施形態にかかる探索結果を表示した画面例を示す図である。
【００７１】
探索結果は、表示部２０３により、マップ上に（マップ上の道路上に）、探索経路が表示される。なお、地図データについても、レベル３の地図データのみがキャッシュされている場合、レベル３の地図データのマップ上に（マップ上の道路上に）、探索経路が表示される。
【００７２】
（経路再探索）
図１２は、本実施形態にかかる経路探索の再探索例を示す模式図である。
【００７３】
データ取得部２０１は、携帯端末２が圏内等で通信できる状態になると、探索経路上、レベル３の道路ＮＷデータしかキャッシュされていなかったエリアに対応するレベル１の道路ＮＷデータを取得する。取得したレベル１の道路ＮＷデータは、記憶部２０４にキャッシュされる。
【００７４】
経路探索部２０２は、レベル３の道路ＮＷデータしかキャッシュされていなかったエリアに対応するレベル１の道路ＮＷデータがキャッシュされると、当該レベル１の道路ＮＷデータを用いて、再度の経路探索を行うことで、例えば、経路３０'を探索する。
【００７５】
これにより、例えば、一旦は圏外のため、探索経路がレベル３の道路ＮＷデータを用いて探索された経路を含んでいる場合であっても、探索経路上レベル３の道路ＮＷデータを用いて探索された経路部分について、レベル１の道路ＮＷデータを用いて再探索されるので、利用者は最終的には詳細な探索経路を得ることが可能である。
【００７６】
[情報処理]
図１３は、本実施形態にかかる携帯端末２の経路探索処理を示すフローチャート図である。
【００７７】
Ｓ１：まず、経路探索部２０２は、出発地及び目的地の情報と共に、経路探索要求を受けたか否かを判定する。
【００７８】
Ｓ２：次に、経路探索部２０２は、記憶部２０４のキャッシュから、出発地、目的地及び中継エリアまでの全道路ＮＷデータを取得する。なお、中継エリアの道路ＮＷデータは、出発地と目的地とを直線で結んだ場合、直線を含むエリア（中継エリア）の道路ＮＷデータとする。また、場合によっては、直線を含むエリアに隣接する周辺エリアを含めてもよい。
【００７９】
Ｓ３：経路探索部２０２は、記憶部２０４のキャッシュから、出発地、目的地及び中継エリアまでの全道路ＮＷデータを取得できたか否かを判定する。全道路ＮＷデータを取得できず、一部の道路ＮＷデータが欠けている場合、経路探索は不可である。
【００８０】
Ｓ４：データ取得部２０１は、通信可能な状態か否かを判定する。例えば、圏外の場合、通信可能な状態でないと判定しうる。
【００８１】
Ｓ５：データ取得部２０１は、通信可能な状態である場合、サーバ１から、全道路ＮＷデータの最も詳細なレベル（例えば、レベル１が相当）のデータを取得する。なお、エリアによっては、既に最も詳細なレベルの道路ＮＷデータがキャッシュされている場合、その分は取得する必要はなく、不足エリアにおける最も詳細なレベルの道路ＮＷデータのみ取得すればよい。全道路ＮＷデータの最も詳細なレベル（例えば、レベル１が相当）のデータを取得すると、Ｓ６へ進む。
【００８２】
Ｓ６：経路探索部２０２は、最も詳細なレベル（例えば、レベル１が相当）の道路ＮＷデータを用いて、経路探索を実行する。これにより、利用者は出発地から目的地への詳細な全探索経路を得ることが可能である。
【００８３】
Ｓ７：一方、Ｓ４で通信可能な状態でない場合、全道路ＮＷデータを取得できず、一部道路ＮＷデータが欠けている場合、経路探索は不可である。よって、経路探索部２０２は、経路探索を中止する。この場合、例えば、携帯端末２の画面上にはエラー等を表示することができる。
【００８４】
Ｓ８：一方、Ｓ３で全道路ＮＷデータを取得できた場合、経路探索部２０２は、取得した全道路ＮＷデータのレベルは、全て最も詳細なレベル（例えば、レベル１が相当）か否かを判定する。取得した全道路ＮＷデータのレベルが、全て最も詳細なレベル（例えば、レベル１が相当）の場合、Ｓ６へ進む。
【００８５】
Ｓ９：データ取得部２０１は、通信可能な状態か否かを判定する。例えば、圏外の場合、通信可能な状態でないと判定しうる。
【００８６】
Ｓ１０：データ取得部２０１は、通信可能な状態である場合、サーバ１から、全道路ＮＷデータの最も詳細なレベル（例えば、レベル１が相当）のデータを取得する。なお、エリアによっては、既に最も詳細なレベルの道路ＮＷデータがキャッシュされている場合、その分は取得する必要はなく、不足エリアにおける最も詳細なレベルの道路ＮＷデータのみ取得すればよい。全道路ＮＷデータの最も詳細なレベル（例えば、レベル１が相当）のデータを取得すると、Ｓ６へ進む。
【００８７】
Ｓ１１：一方、Ｓ９で通信可能な状態でない場合、記憶部２０４のキャッシュから、出発地、目的地及び中継エリアまでの全道路ＮＷデータを取得できたものの、レベルに関し、取得できた全道路ＮＷデータのうち一部の道路ＮＷデータは、最も詳細なレベルのもの（例えば、レベル２、３が相当）ではない。経路探索部２０２は、キャッシュから取得できた範囲内の道路ＮＷデータを用いて、経路探索を実行する。即ち、経路探索部２０２は、レベルの異なる道路ＮＷデータを跨いで、経路探索を実行する（図７〜１１参照）。
【００８８】
なお、Ｓ１１の後、再びＳ９へ進み、通信が回復を待機するとよい。通信が回復した場合、Ｓ１０及びＳ６へ進むことで、経路探索部２０２は、最も詳細なレベル（例えば、レベル１が相当）の道路ＮＷデータを用いて、再経路探索を実行する（図１２参照）。これにより、利用者は最終的に出発地から目的地への詳細な全探索経路を得ることが可能である。
【００８９】
[総括]
以上、本実施形態にかかる携帯端末２では、携帯端末２が通信圏外等で通信できない状態にあると、キャッシュの範囲内の道路ＮＷデータを用いて経路探索を行うようにする。ここで、道路ＮＷデータは、同一エリアでも詳細度の異なる複数の道路ＮＷデータがある。本実施形態においては、詳細度の異なる複数の道路ＮＷデータがキャッシュされている場合、レベルの異なる道路ＮＷデータを用いて、経路探索を実行する。つまり、レベルの異なる道路ＮＷデータからそれぞれの経路を跨ぐように接続することで、経路探索を実行する。
【００９０】
これにより、圏外等で携帯端末２が通信できない状態になった場合でも、携帯端末側で保持するキャッシュデータの範囲内で、適切な経路探索を実行することで、利用者の利便性を向上させることができる。
【００９１】
なお、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【符号の説明】
【００９２】
１        経路案内サーバ
２        携帯端末
３        ネットワーク
１１        ＣＰＵ
１２        ＲＯＭ
１３        ＲＡＭ
１４        ＨＤＤ
１５        入力装置
１６        表示装置
１７        通信装置
１８        音声入出力装置
１９        ＧＰＳ受信装置
１００    経路案内システム
１０１    データ提供部
１０２    記憶部
２０１    データ取得部
２０２    経路探索部
２０３    表示部
２０４    記憶部
【図１】
0006293016.tif 000002
【図２】
0006293016.tif 000003
【図３】
0006293016.tif 000004
【図４】
0006293016.tif 000005
【図５】
0006293016.tif 000006
【図６】
0006293016.tif 000007
【図７】
0006293016.tif 000008
【図８】
0006293016.tif 000009
【図９】
0006293016.tif 000010
【図１０】
0006293016.tif 000011
【図１１】
0006293016.tif 000012
【図１２】
0006293016.tif 000013
【図１３】
0006293016.tif 000014