ナビゲーションシステム、ナビゲーション装置、経路探索方法、および、プログラム
【課題】通信不可エリアにナビゲーション装置が移動した場合に、ナビゲーション装置によるスムーズな経路誘導を可能にするための技術を提供する。
【解決手段】情報センタ２００から提供された推奨経路を用いて経路誘導を行うナビゲーション装置１００であって、情報センタ２００から、推奨経路、仮想経由地を受信する受信手段と、移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を情報センタ２００に要求するリルート手段と、情報センタ２００から推奨経路を取得できない場合に、受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える。
【解決手段】情報センタ２００から提供された推奨経路を用いて経路誘導を行うナビゲーション装置１００であって、情報センタ２００から、推奨経路、仮想経由地を受信する受信手段と、移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を情報センタ２００に要求するリルート手段と、情報センタ２００から推奨経路を取得できない場合に、受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステム、ナビゲーション装置、経路探索方法、および、プログラムに関する。
【背景技術】
【０００２】
近年のナビゲーション装置は、無線通信によって通信可能な外部装置（以下では「情報センタ」とよぶ）を利用して、経路探索が可能になりつつある（例えば、特許文献１）。情報センタ側では、ナビゲーション装置からの要求に応じて推奨経路を探索し、これをナビゲーション装置に提供する。
【０００３】
このようなナビゲーションシステムでは、リアルタイムな交通情報を利用した経路探索が可能である。さらに、ナビゲーション装置側で経路探索を行わなくてよいため、ナビゲーション装置にかかる処理負荷を低減することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−５５６８２号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、上記のようなナビゲーションシステムでは、ナビゲーション装置と情報センタとの間で無線通信が必要となるため、ナビゲーション装置が通信できないエリア（以下では「通信不可エリア」とよぶ）に移動すると、情報センタの情報を利用できない。この場合、ナビゲーション装置側では経路探索できず、スムーズな経路誘導ができなくなる。
【０００６】
本発明は、通信不可エリアにナビゲーション装置が移動した場合に、ナビゲーション装置によるスムーズな経路誘導を可能にするための技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するための本願発明は、推奨経路の探索を行う外部装置と、当該外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置と、を備えるナビゲーションシステムであって、前記ナビゲーション装置は、前記外部装置に、推奨経路の探索を要求する要求手段を備え、前記外部装置は、前記ナビゲーション装置からの要求に基づいて、推奨経路を探索する経路探索手段と、前記ナビゲーション装置が当該外部装置と通信可能な地点である仮想経由地を設定する仮想経由地設定手段と、探索された前記推奨経路と、設定された前記仮想経由地と、を前記ナビゲーション装置に提供する提供手段と、を備え、前記ナビゲーション装置は、前記外部装置から、前記推奨経路、前記仮想経由地を受信する受信手段と、移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施形態が適用されたナビゲーションシステムの概略構成図である。
【図２】ナビゲーション装置の概略構成図である。
【図３】地図データの概略データ構造を示す図である。
【図４】情報センタの概略構成図である。
【図５】ナビゲーション装置の演算処理部、及び、情報センタの演算処理部の機能ブロック図である。
【図６】（Ａ）通信不可エリアについて説明するための図である。（Ｂ）仮想経由地の設定方法について説明するための図である。
【図７】ナビゲーション装置における経路誘導処理を示すフロー図である。
【図８】（Ａ）仮想経由地テーブルの概略データ構造の一例を示す図である。（Ｂ）仮想経由地テーブルの概略データ構造の別例を示す図である。
【図９】情報センタにおける経路探索処理を示すフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態の一例を図面を参照して説明する。
【００１０】
図１は、本発明の一実施形態が適用されたナビゲーションシステム５０の概略構成図である。図示するようにナビゲーションシステム５０は、ナビゲーション装置１００と、情報センタ２００と、を備える。なお、図には、１台のナビゲーション装置１００を示しているが、本発明のナビゲーションシステム５０に適用されるナビゲーション装置１００は複数台であってもよい。また、同様に、図には、１台の情報センタ２００を示しているが、情報センタ２００は複数台であってもよい。
【００１１】
ナビゲーション装置１００は、例えば、通信型の車載用ナビゲーション装置である。もちろん、ナビゲーション装置１００は、これに限られず、携帯電話やＰＤＡなどの携帯端末としてもよい。
【００１２】
情報センタ２００は、推奨経路や交通情報などをナビゲーション装置１００に提供するサーバ装置として機能する一般的な情報処理装置（コンピューター）である。
【００１３】
ナビゲーション装置１００と情報センタ２００は、ネットワークを介して接続され、無線通信により情報のやりとりを行える。
【００１４】
図２は、ナビゲーション装置１００の概略構成図である。図示するように、ナビゲーション装置１００は、演算処理部１０１と、ディスプレイ１０２と、記憶装置１０３と、音声入出力装置１０４（マイクロフォン１４１、スピーカ１４２）と、入力装置１０５（タッチパネル１５１、ダイヤルスイッチ１５２）と、車速センサ１０６と、ジャイロセンサ１０７と、ＧＰＳ受信装置１０８と、ＦＭ多重放送受信装置１０９と、ビーコン受信装置１１０と、通信装置１１２と、を備えている。
【００１５】
演算処理部１０１は、様々な処理を行う中心的ユニットである。例えば、演算処理部１０１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ（Central Processing Unit）１２１と、記憶装置１０３から読み出した地図データ、演算データなどを格納するＲＡＭ（Random Access Memory）１２２と、プログラムやデータを格納するＲＯＭ１２３と、各種ハードウェアを演算処理部１０１に接続するためのＩ／Ｆ（インタフェース）１２４と、を有する。そして、演算処理部１０１は、各デバイスをバス１２５で相互に接続した構成からなる。そして、後述する各機能部（４０１〜４０８）は、ＣＰＵ１２１がＲＡＭ１２２などのメモリに読み出したプログラムを実行することで実現される。
【００１６】
例えば、演算処理部１０１は、車速センサ１０６、ジャイロセンサ１０７、ＧＰＳ受信装置１０８から出力される情報を基にして現在地を検出する。また、得られた現在地情報に基づいて、表示に必要な地図データを記憶装置１０３から読み出す。また、読み出した地図データをグラフィック展開し、そこに現在地マーク（或いは、移動体の位置を示す移動体マーク）を重ねてディスプレイ１０２に表示する。また、情報センタ２００に出発地（現在地）と目的地を送信し、ユーザから指示された出発地と目的地を結ぶ最適な経路（以下では「推奨経路」とよぶ）の探索を、情報センタ２００に要求する。具体的には、演算処理部１０１は、出発地と目的地を含む情報を、通信装置１１１を介して情報センタ２００に送信する。また、演算処理部１０１は、情報センタ２００で探索された推奨経路に従って、音声入出力装置１０４のスピーカ１４２やディスプレイ１０２を用いてユーザを誘導する。
【００１７】
ディスプレイ１０２は、演算処理部１０１で生成されたグラフィック情報を表示するユニットである。ディスプレイ１０２は、液晶ディスプレイや有機ＥＬ（Electro-Luminescence）ディスプレイなどで構成される。
【００１８】
記憶装置１０３は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、例えば、地図データ３１０、音声データ、動画データ、等が記憶されている。また、記憶媒体は、電源供給が停止した場合でも必要なデータを保持可能なフラッシュメモリなどで構成されていてもよい。
【００１９】
図３は、地図データの概略データ構造を示す図である。図示するように、地図データ３１０は、地図上の区画された領域であるメッシュの識別コード（メッシュＩＤ）３１１ごとに、そのメッシュ領域に含まれている道路を構成する各リンクのリンクデータ３２０を含んでいる。
【００２０】
リンクデータ３２０は、リンクの識別コード（リンクＩＤ）３２１ごとに、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３２２、リンクを含む道路の種別情報を示す道路種別３２３、リンクの長さを示すリンク長情報３２４、リンク旅行時間３２５、２つのノードにそれぞれ接続するリンクの識別コード（接続リンクＩＤ）３２６、などを含んでいる。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードを区別することで、道路の上り方向と下り方向を、それぞれ別のリンクとして管理することができる。また、地図データ３１０には、地図表示における道路や施設を表示するための描画データが格納されている。
【００２１】
図２に戻り、音声入出力装置１０４は、音声入力装置としてマイクロフォン１４１と、音声出力装置としてスピーカ１４２と、を備える。マイクロフォン１４１は、運転手やその他の同乗者から発せられた音声などの、ナビゲーション装置１００の外部の音声を取得する。スピーカ１４２は、演算処理部１０１で生成された音声信号を出力する。これらのマイクロフォン１４１とスピーカ１４２は、車両の所定の部位に、別個に配置されている。
【００２２】
入力装置１０５は、ユーザからの指示を受け付けるユニットである。入力装置１０５は、タッチパネル１５１と、ダイヤルスイッチ１５２と、その他のハードスイッチ（図示せず）であるスクロールキー、縮尺変更キーなどで構成される。
【００２３】
タッチパネル１５１は、ディスプレイ１０２の表示面に貼られた透過性のある操作パネルである。タッチパネル１５１は、ディスプレイ１０２に表示された画像のＸＹ座標と対応したタッチ位置を特定し、タッチ位置を座標に変換して出力する。タッチパネル１５１は、感圧式または静電式の入力検出素子などにより構成される。
【００２４】
ダイヤルスイッチ１５２は、時計回り及び反時計回りに回転可能に構成され、所定の角度の回転ごとにパルス信号を発生し、演算処理部１０１に出力する。演算処理部１０１では、パルス信号の数から、ダイヤルスイッチ１５２の回転角度を求める。
【００２５】
車速センサ１０６、ジャイロセンサ１０７、及び、ＧＰＳ受信装置１０８は、移動体（ナビゲーション装置１００）の現在位置（自車位置）などを検出するために使用される。車速センサ１０６は、車速を算出するために用いる車速データを出力するセンサである。ジャイロセンサ１０７は、光ファイバジャイロや振動ジャイロ等で構成され、移動体の回転による角速度を検出するものである。ＧＰＳ受信装置１０８は、ＧＰＳ衛星からの信号を受信し、移動体とＧＰＳ衛星間の距離とその距離の変化率を３個以上の衛星に対して測定することで、移動体の現在位置や進行速度を測定する。
【００２６】
ＦＭ多重放送受信装置１０９は、ＦＭ多重放送局から送られてくるＦＭ多重放送信号を受信する。ＦＭ多重放送には、ＶＩＣＳ（Vehicle Infomation Communication System：登録商標）情報の概略現況交通情報、規制情報、ＳＡ／ＰＡ（サービスエリア／パーキングエリア）情報、駐車場情報、天気情報などのＦＭ多重一般情報としてラジオ局が提供する文字情報などがある。
【００２７】
ビーコン受信装置１１０は、ビーコンから送られてくる渋滞情報、規制情報、ＳＡ／ＰＡ情報、駐車場情報などを受信する。
【００２８】
通信装置１１１は、情報センタ２００と通信するための装置であり、情報センタ２００から提供された推奨経路、後述する仮想経由地（仮想経由地テーブル６００）などを受信する。
【００２９】
また、図４は、情報センタ２００の概略構成図である。図示するように、情報センタ２００は、演算処理部２０１と、記憶装置２０２と、通信装置２０３と、を備えている。
【００３０】
演算処理部２０１は、様々な処理を行う中心的ユニットである。例えば、演算処理部２０１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ２２１と、記憶装置２０２から読み出した地図データ、演算データなどを格納するＲＡＭ２２２と、プログラムやデータを格納するＲＯＭ２２３と、各種ハードウェアを演算処理部２０１に接続するためのＩ／Ｆ（インタフェース）２２４と、を有する。そして、演算処理部１０１は、各デバイスをバス１２５で相互に接続した構成からなる。そして、後述する各機能部（５０１〜５０４）は、ＣＰＵ２２１がＲＡＭ２２２などのメモリに読み出したプログラムを実行することで実現される。
【００３１】
例えば、演算処理部２０１は、ナビゲーション装置１００から経路探索の要求を受け付けると、記憶装置２０２に記憶されている地図データを用いて、ナビゲーション装置１００から受信した出発地と目的地を結ぶ推奨経路を探索する。また、演算処理部２０１は、ナビゲーション装置１００が情報センタ２００と通信可能な地点であって、目的地までの経由地として最適な地点を仮想経由地として設定する。仮想経由地の具体的な設定方法については後述する。
【００３２】
記憶装置２０２は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、図３に示す地図データ３１０と同様の地図データ、等が記憶されている。また、記憶媒体は、電源供給が停止した場合でも必要なデータを保持可能なフラッシュメモリなどで構成されていてもよい。
【００３３】
通信装置２０３は、ナビゲーション装置１００と通信するための装置であり、演算処理部２０１で探索された推奨経路、設定された仮想経由地（仮想経由地テーブル６００）などを送信する。
【００３４】
図５は、ナビゲーション装置１００の演算処理部１０１、及び、情報センタ２００の演算処理部２０１の機能ブロック図である。図示するように、ナビゲーション装置１００の演算処理部１０１は、主制御部４０１と、入力受付部４０２と、表示処理部４０３と、現在位置算出部４０４と、経路探索部４０５と、経路誘導部４０６と、リルート部４０７と、通信処理部４０８と、を有する。また、情報センタ２００の演算処理部２０１は、主制御部５０１と、経路探索部５０２と、経由地設定部５０３と、通信処理部５０４と、を有する。
【００３５】
ナビゲーション装置１００の主制御部４０１は、演算処理部１０１の各部を統括して制御する処理を行う。
【００３６】
入力受付部４０２は、入力装置１０５に入力されたユーザからの要求を受け付け、その要求内容を解析する。入力受付部４０２は、解析結果に応じたデータを主制御部４０１に通知する。例えば、入力受付部４０２は、ナビゲーション装置１００に、電源の投入、切断を指示する要求、推奨経路の探索（或いは、経路誘導の開始）を指示する要求、等を受け付け、主制御部４０１に通知する。
【００３７】
表示処理部４０３は、ディスプレイ１０２に、地図、推奨経路、ユーザに通知する各種メッセージ、等を表示させる。具体的には、表示処理部４０３は、ディスプレイ１０２に表示させるための描画コマンドを生成して通知する。なお、表示処理部４０３は、地図をディスプレイ１０２に表示させる際には、表示が要求された領域（例えば、推奨経路全体を表示するのに必要な領域）にある地図データを記憶装置１０３から抽出し、指定された描画方式で、道路、その他の地図構造物、現在位置、目的地、推奨経路、等を描画するように地図コマンドを生成する。また、表示処理部４０３は、ディスプレイ１０２に表示させた地図上に、車両の位置を示す車両マークや各種設定画面などを表示させる。
【００３８】
現在位置算出部４０４は、ナビゲーション装置１００の現在位置を算出する。具体的には、現在位置算出部４０４は、車速センサ１０６で出力された車速データに基づいて算出した移動体（ナビゲーション装置１００）の進行速度、および、ジャイロセンサ１０７で検出した角速度データを各々積分して結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から移動後（自車走行後）の位置（Ｘ’，Ｙ’）を定期的に演算する。また、演算結果を用いて、マップマッチ処理することにより、形状の相関が最も高い道路（リンク）上に現在位置を合わせ込む。また、定期的にＧＰＳ受信装置１０８の出力データを用いて現在位置を修正する。なお、移動体（ナビゲーション装置１００）が停止しているときには、ＧＰＳ受信装置１０８の出力データだけを用いて現在位置を求めてもよい。
【００３９】
ナビゲーション装置１００の経路探索部４０５は、移動体（ナビゲーション装置１００）が通信不可エリア内において推奨経路から逸れた場合に、情報センタ２００で設定された仮想経由地に向けた簡易的な経路探索を行う。具体的には、経路探索部４０５は、ダイクストラ法等を用いて、現在地と、情報センタ２００で設定された仮想経由地と、の２地点間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部４０５は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ１２２等のメモリに記憶しておく。そして、経路探索部４０５は、探索した推奨経路を、表示処理部４０３を介して、ディスプレイ１０２に表示（強調表示）する。このとき、経路探索部４０５は、例えば、推奨経路の現在置から仮想経路地までの全行程が１画面に収まる縮尺の地図に、推奨経路をディスプレイ１０２に表示する。
【００４０】
なお、経路探索部４０５が行う経路探索には、ＦＭ多重放送受信装置１０９やビーコン受信装置１１０から受信した交通情報を用いてもよいし、用いないようにしてもよい。
【００４１】
経路誘導部４０６は、情報センタ２００から取得（受信）した推奨経路、又は、経路探索部４０５で探索された推奨経路、を用いて経路誘導を行う。具体的には、経路誘導部４０６は、表示処理部４０３を介して、ディスプレイ１０２に表示された地図の範囲に含まれている推奨経路を表示（強調表示）する。このとき、経路誘導部４０６は、移動体（ナビゲーション装置１００）の現在位置を示す移動体マーク（車両マーク）を推奨経路上（例えば、画面中心）に表示する。また、経路誘導部４０６は、推奨経路の情報と現在位置とを比較して、主要な交差点等を通過する前に直進すべきか、右左折すべきかを、ディスプレイ１０２に表示させるとともに、音声入出力装置１０４のスピーカ１４２を用いて音声でユーザに知らせる。
【００４２】
リルート部４０７は、移動体（ナビゲーション装置１００）が推奨経路から逸れた場合に、現在地（例えば、推奨経路から逸れた地点）から目的地までの推奨経路を、情報センタ２００に要求する。具体的には、リルート部４０７は、現在地と目的地を含む情報を、通信装置１１１を介して情報センタ２００に送信する。
【００４３】
ただし、リルート部４０７は、移動体が通信不可エリア内において推奨経路から逸れた場合には、現在地（例えば、推奨経路から逸れた地点のリンク）から仮想経由地までの推奨経路を、自装置内の経路探索部４０５に探索させる。
【００４４】
ナビゲーション装置１００の通信処理部４０８は、情報センタ２００とのデータのやりとりを制御する。例えば、通信処理部４０８は、経路誘導部４０６或いはリルート部４０７からの指示に基づいて、情報センタ２００との通信を確立し、経路探索を要求するためのデータを出力する。また、通信処理部４０８は、情報センタ２００から出力された推奨経路や仮想経由地（仮想経由地テーブル６００）などを受信する。
【００４５】
また、情報センタ２００の主制御部５０１は、演算処理部２０１の各部を統括して制御する処理を行う。
【００４６】
情報センタ２００の経路探索部５０２は、ナビゲーション装置１００から受信した現在地（出発地や推奨経路から逸れた地点）と目的地の間の推奨経路を探索する。具体的には、経路探索部５０２は、ナビゲーション装置１００から受信した現在地と目的地の２地点間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部５０２は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ２２２等のメモリに記憶しておく。
【００４７】
なお、経路探索部５０２が行う経路探索には、ナビゲーション装置１００から収集した情報を基に生成された統計情報（例えば、渋滞などの交通情報）を用いてもよいし、用いないようにしてもよい。
【００４８】
経由地設定部５０３は、上述した仮想経由地を設定する。ただし、経由地設定部５０３は、経路探索部５０２で探索された推奨経路上の通信不可エリアが存在する場合に、仮想経由地を設定する。そのため、経由地設定部５０３は、経路探索部５０２で推奨経路が探索されると、まず、その推奨経路上の通信不可エリアを特定する。
【００４９】
図６（Ａ）は、通信不可エリアについて説明するための図である。図示するように、経由地設定部５０３は、推奨経路上に存在する全ての通信不可エリア（点線で囲まれたエリア）を特定する。なお、通信不可エリアは、記憶装置２０２に記憶されている地図データ３１０に予め格納しておく。
【００５０】
そして、経由地設定部５０３は、通信不可エリアを特定すると、通信不可エリアごとに、仮想経由地を設定する。
【００５１】
ここで、図６（Ｂ）は、仮想経由地の設定方法について説明するための図である。図示するように、経由地設定部５０３は、通信不可エリア内において、推奨経路上の分岐点を特定する。この分岐点は、移動体が推奨経路から逸れる可能性がある地点とする。そして、経由地設定部５０３は、分岐点で推奨経路から逸れているリンクの延長（点線で示す道路）上で、かつ、通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）を、仮想経由地として設定する。
【００５２】
具体的には、経由地設定部５０３は、分岐点で推奨経路から逸れているリンクを出発地として、目的地までのコスト（旅行時間など）が最小となる経路を探索し、探索したその経路上において、通信不可エリアから脱出する地点を、仮想経由地として設定する。
【００５３】
ただし、本発明の仮想経由地の設定方法はこれに限定されない。例えば、経由地設定部５０３は、通信不可エリア外で分岐点から一番近い地点を仮想経由地として設定してもよい。或いは、分岐点が存在する通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）で、目的地に一番近い地点を仮想経由地として設定してもよい。
【００５４】
なお、同一の通信不可エリア内に、分岐点が複数個存在する場合には、経由地設定部５０３は、分岐点ごとに仮想経由地を設定する（図示する例では同一エリア内に２箇所）。
【００５５】
また、１つの分岐点に対して複数の仮想経由地が設定されてしまう場合には、例えば、経由地設定部５０３は、通信不可エリア外で分岐点から一番近い地点や、分岐点が存在する通信不可エリアから脱出する地点で目的地に一番近い地点、などを仮想経由地として設定する。
【００５６】
そして、経由地設定部５０３は、仮想経由地を設定すると、少なくとも仮想経由地を含むテーブル（後述する仮想経由地テーブル６００）を生成し、ＲＡＭ２２２等のメモリに格納する。
【００５７】
なお、経由地設定部５０３による仮想経由地設定のための経路探索には、ナビゲーション装置１００から収集した情報を基に生成された統計情報（例えば、渋滞などの交通情報）を用いてもよいし、用いないようにしてもよい。
【００５８】
図５に戻り、情報センタ２００の通信処理部５０４は、ナビゲーション装置１００とのデータのやりとりを制御する。例えば、通信処理部５０４は、ナビゲーション装置１００から、経路探索の要求を受け付ける（受信する）。また、通信処理部５０４は、経路探索を要求してきたナビゲーション装置１００を特定して通信を確立し、経路探索部５０２で探索された推奨経路や、経由地設定部５０３で設定された仮想経由地（仮想経由地テーブル６００）などを送信する。
【００５９】
なお、上記した各構成要素は、ナビゲーションシステム５０の構成を理解容易にするために、主な処理内容に応じて分類したものである。構成要素の分類の仕方やその名称によって、本願発明が制限されることはない。ナビゲーションシステム５０の構成は、処理内容に応じて、さらに多くの構成要素に分類することもできる。また、１つの構成要素がさらに多くの処理を実行するように分類することもできる。
【００６０】
また、各機能部（４０１〜４０８、５０１〜５０４）は、ハードウエア（ＡＳＩＣなど）により構築されてもよい。また、各機能部の処理が一つのハードウエアで実行されてもよいし、複数のハードウエアで実行されてもよい。
【００６１】
次に、上記構成からなるナビゲーションシステム５０の特徴的な動作について説明する。
【００６２】
＜経路誘導処理＞
図７は、ナビゲーション装置１００で行われる経路誘導処理を示すフローチャートである。
【００６３】
ナビゲーション装置１００の主制御部４０１は、例えば、電源が投入されるタイミング、或いは、経路誘導開始の指示のタイミングで、本フローを開始する。
【００６４】
図示するように、本フローを開始すると、経路誘導部４０６は、まず、情報センタ２００に対して、経路探索を要求する（ステップＳ１０１）。具体的には、経路誘導部４０６は、出発地と目的地の指定を入力受付部４０２を介して受け付ける。ただし、出発地は、現在位置算出部４０４によって算出される移動体の現在位置としてもよい。出発地と目的地が指定されると、経路誘導部４０６は、通信処理部４０８を介して、出発地と目的地を情報センタ２００に送信し、経路探索の要求を行う。
【００６５】
このとき、情報センタ２００では、ステップＳ１０１の要求に応じて経路探索が行われ（後述する「経路探索処理」）、探索された推奨経路と、仮想経由地テーブル６００が情報センタ２００から出力される。
【００６６】
そして、経路誘導部４０６は、情報センタ２００から出力された推奨経路と、仮想経由地を受信する（ステップＳ１０２）。具体的には、経路誘導部４０６は、通信処理部４０８を介して、推奨経路を構成するリンクＩＤと、仮想経由地テーブル６００を受信する。
【００６７】
その後、経路誘導部４０６は、ステップＳ１０２で受信した推奨経路を用いて、経路誘導を開始する。
【００６８】
経路誘導を開始すると、経路誘導部４０６は、移動体（ナビゲーション装置１００）が目的地に到達したか否か判別する（ステップＳ１０３）。具体的には、経路誘導部４０６は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０１で指定された目的地から所定の距離内である場合には、移動体が目的地に到達したと判定する。一方、経路誘導部４０６は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０１で指定された目的地から所定の距離以上離れている場合には、移動体は目的地に到達していないと判定する。
【００６９】
ここで、経路誘導部４０６は、移動体が目的地に到達したと判定した場合には（ステップＳ１０３；Ｙｅｓ）、そのまま経路誘導を終了する（本フローを終了する）。
【００７０】
一方、経路誘導部４０６は、移動体が目的地に到達していないと判定した場合には（ステップＳ１０３；Ｎｏ）、処理をステップＳ１０４に移行する。
【００７１】
処理がステップＳ１０４に移行すると、リルート部４０７は、リルートの必要があるか否か判別する（ステップＳ１０４）。具体的には、リルート部４０７は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０２で情報センタ２００から受信した推奨経路上にない（推奨経路と現在位置の距離が所定閾値以上の）場合に、リルートの必要があると判定する。すなわち、リルート部４０７は、移動体が推奨経路から逸れた場合に、リルートの必要があると判定する。一方、リルート部４０７は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０２で情報センタ２００から受信した推奨経路上にある（推奨経路と現在位置の距離が所定閾値未満の）場合に、リルートの必要はないと判定する。すなわち、リルート部４０７は、移動体が推奨経路に従って移動（走行）している間、リルートの必要はないと判定する。
【００７２】
ここで、リルート部４０７は、リルートの必要がないと判定した場合には（ステップＳ１０４；Ｎｏ）、処理をステップＳ１０３に戻す。こうして、移動体が目的地に到達する、或いは、移動体が推奨経路から逸れる、までステップＳ１０３、Ｓ１０４の処理が繰り返し実行される。
【００７３】
一方、ステップＳ１０４において、リルート部４０７は、リルートの必要があると判定した場合には（ステップＳ１０４；Ｙｅｓ）、処理をステップＳ１０５に移行する。
【００７４】
処理がステップＳ１０５に移行すると、リルート部４０７は、情報センタ２００と通信可能（推奨経路を取得可能）か否か判別する（ステップＳ１０５）。例えば、リルート部４０７は、一般的な方法によって情報センタ２００と通信を確立できた場合に、情報センタ２００と通信可能と判定する。一方、リルート部４０７は、通信を確立できない場合には、情報センタ２００と通信不可能と判定する。
【００７５】
そして、リルート部４０７は、情報センタ２００と通信可能と判定した場合には（ステップＳ１０５；Ｙｅｓ）、処理をステップＳ１０１に戻す。ただし、ステップＳ１０５からステップＳ１０１に処理が戻された場合には、経路誘導部４０６は、現在位置算出部４０４によって算出される移動体の現在位置を出発地としてステップＳ１０１の処理を実行する。これにより、ナビゲーションシステム５０では、移動体が推奨経路から逸れた地点から目的地までの推奨経路を再探索することができる。
【００７６】
一方、リルート部４０７は、情報センタ２００と通信不可能と判定した場合には（ステップＳ１０５；Ｎｏ）、処理をステップＳ１０６に移行する。
【００７７】
情報センタ２００と通信不可能（推奨経路を取得不可能）である場合には、ナビゲーション装置１００は情報センタ２００から推奨経路を再探索させることができない。そこで、ナビゲーション装置１００は、移動体が推奨経路から逸れた地点から、設定されている仮想経由地までの推奨経路を自装置で探索する。
【００７８】
そのために、経路探索部４０５は、処理がステップＳ１０６に移行すると、まず、仮想経由地の選択（決定）を行う（ステップＳ１０６）。具体的には、経路探索部４０５は、ステップＳ１０２で情報センタ２００から取得した仮想経由地テーブル６００の中から１つの仮想経由地を選択する。
【００７９】
図８（Ａ）は、仮想経由地テーブル６００の概略データ構造の一例を示す図である。図示するように、仮想経由地テーブル６００は、情報センタ２００で設定された仮想経由地ごとのレコード６３０からなる。各レコード６３０には、分岐リンク６１０と、仮想経由地６２０と、が対応付けて格納される。分岐リンク６１０は、推奨経路上の通信不可エリア内における分岐点（例えば、トンネル内の分岐点）で、推奨経路から逸れる方向のリンク（リンクＩＤ）である。仮想経由地６２０は、その分岐点ごとに設定された仮想経由地の位置を示す座標データである。なお、仮想経由地テーブル６００に含まれるレコード６３０数は１つでもよい。
【００８０】
上記の仮想経由地テーブル６００から１つの仮想経由地を選択する際に、経路探索部４０５は、まず、移動体が位置しているリンクを特定する。そして、移動体が位置しているリンクに対応する分岐リンク６１０を、仮想経由地テーブル６００から検索する。それから、経路探索部４０５は、検索した分岐リンク６１０に対応付けられている仮想経由地６２０を、推奨経路を再探索（リルート）するための目的地（経由地）として選択する。
【００８１】
続いて、経路探索部４０５は、移動体が推奨経路から逸れた地点から、ステップＳ１０６で選択された仮想経由地までの推奨経路を探索する（ステップＳ１０７）。具体的には、経路探索部４０５は、ダイクストラ法等を用いて、現在位置算出部４０４で算出された現在位置と、ステップＳ１０６で選択された仮想経由地と、の２地点間を結ぶ経路のコストが最小となる経路を探索する。なお、ステップＳ１０７での経路探索は、移動体が推奨経路から逸れた地点から仮想経由地までの経路探索であるため、ナビゲーション装置１００にかかる処理負荷は非常に低いものとなる。
【００８２】
その後、経路誘導部４０６は、ステップＳ１０７で探索された推奨経路を用いて、経路誘導を再開する。
【００８３】
そして、経路誘導部４０６は、情報センタ２００と通信可能になる位置に移動体が到達するまで、仮想経由地に向けて経路誘導を行う。これに並行して、リルート部４０７は、ステップＳ１０５の処理と同様に、情報センタ２００と通信可能か否か判別する（ステップＳ１０８）。
【００８４】
そして、リルート部４０７は、情報センタ２００と通信可能になる位置に移動体が到達するまで（ステップＳ１０８；Ｎｏ）、ステップＳ１０８の処理を繰り返す。
【００８５】
一方、リルート部４０７は、情報センタ２００と通信可能と判定した場合には（ステップＳ１０８；Ｙｅｓ）、処理をステップＳ１０１に戻す。ただし、ステップＳ１０８からステップＳ１０１に処理が戻された場合には、経路誘導部４０６は、現在位置算出部４０４によって算出される移動体の現在位置を出発地としてステップＳ１０１の処理を実行する。これにより、ナビゲーション装置１００は、通信不可エリアを脱出するタイミング（地点）で、現在位置からステップＳ１０１で指定された目的地までの推奨経路を、情報センタ２００から取得できる。
【００８６】
以上の処理をナビゲーション装置１００が行うことにより、通信不可エリア内で移動体が推奨経路から逸れた場合にも、即座にリルートできるため、スムーズな経路誘導が可能になる。また、その場合のリルートは、仮想経由地までの経路探索としているため、ナビゲーション装置１００にかかる処理負荷を最低限に抑えることができる。さらには、ステップＳ１０８において、移動体が実際に仮想経由地に到達していなくても、情報センタ２００と通信可能であればすぐに推奨経路を再取得するため、効率的に情報センタ２００を利用することができる。
【００８７】
なお、上記したフローの各処理単位は、ナビゲーション装置１００の処理を理解容易にするために、主な処理内容に応じて分割したものである。処理ステップの分類の仕方やその名称によって、本願発明が制限されることはない。ナビゲーション装置１００が行う処理は、さらに多くの処理ステップに分割することもできる。また、１つの処理ステップが、さらに多くの処理を実行してもよい。
【００８８】
＜経路探索処理＞
図９は、情報センタ２００で行われる経路探索処理を示すフローチャートである。
【００８９】
情報センタ２００の主制御部５０１は、例えば、電源が投入されるタイミングで本フローを開始し、ナビゲーション装置１００からの情報を受信するまで待機する。
【００９０】
そして、情報センタ２００の経路探索部５０２は、ナビゲーション装置１００からの要求（経路探索の要求）を受け付けると（ステップＳ２０１）、処理をステップＳ２０２に移行する。具体的には、経路探索部５０２は、通信処理部５０４を介して、ナビゲーション装置１００から出発地と目的地を含むデータを受信して、経路探索の要求を受け付ける。
【００９１】
そして、経路探索部５０２は、ナビゲーション装置１００からの要求に応じた推奨経路を探索する（ステップＳ２０２）。具体的には、経路探索部５０２は、ダイクストラ法等を用いて、ステップＳ２０１で受信した出発地と目的地の２地点間を結ぶ経路のコストが最小となる経路を探索する。なお、経路探索部５０２は、リアルタイムな交通情報、統計情報などを利用して経路探索することができる。
【００９２】
続いて、経由地設定部５０３は、経路探索部５０２で推奨経路が探索されると、その推奨経路上に通信不可エリアが有るか否か判別する（ステップＳ２０３）。具体的には、経由地設定部５０３は、メモリなどに予め格納されている通信不可エリアと、ステップＳ２０２で探索された推奨経路と、を比較して、推奨経路が通過している通信不可エリアが少なくとも１つは存在する場合には、推奨経路上に通信不可エリアがあると判定する。一方、推奨経路が通過している通信不可エリアが１つも存在しない場合には、推奨経路上に通信不可エリアはないと判定する。
【００９３】
ここで、経由地設定部５０３は、探索された推奨経路上に通信不可エリアはないと判定した場合には（ステップＳ２０３；Ｎｏ）、仮想経由地の設定は行わず、処理をステップＳ２０６に移行する。
【００９４】
一方、経由地設定部５０３は、探索された推奨経路上に通信不可エリアがあると判定した場合には（ステップＳ２０３；Ｙｅｓ）、処理をステップＳ２０４に移行する。
【００９５】
処理がステップＳ２０４に移行すると、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点が有るか否か判別する（ステップＳ２０４）。具体的には、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリア内において、その推奨経路上に分岐点（交差点、リンクの分岐など）が少なくとも１つは存在する場合には、通信不可エリア内の推奨経路上に分岐点が有ると判定する。一方、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリア内において、その推奨経路上に分岐点が１つも存在しない場合には、通信不可エリア内の推奨経路上に分岐点はないと判定する。
【００９６】
ここで、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点はないと判定した場合には（ステップＳ２０４；Ｎｏ）、移動体が通信不可エリア内で推奨経路から逸れることはないため、仮想経由地の設定は行わず、処理をステップＳ２０６に移行する。
【００９７】
一方、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点が有ると判定した場合には（ステップＳ２０４；Ｙｅｓ）、処理をステップＳ２０５に移行する。
【００９８】
処理がステップＳ２０５に移行すると、経由地設定部５０３は、仮想経由地を設定する（ステップＳ２０５）。なお、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリアごとに、仮想経由地を設定する。
【００９９】
例えば、経由地設定部５０３は、ステップＳ２０４で特定した分岐点で推奨経路から逸れる方向に伸びているリンク（分岐リンク）の終端（終了ノード）を出発地として、ステップＳ２０１でナビゲーション装置１００から受信した目的地までのコストが最小となる経路を探索する。そして、探索された経路上であり、かつ、通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）を、仮想経由地として設定する。
【０１００】
なお、ステップＳ２０５の処理は、推奨経路上の全ての通信不可エリア内における全ての分岐点ごとに行われるため、複数の仮想経由地が設定され得る。
【０１０１】
そして、経由地設定部５０３は、仮想経由地を設定すると、ステップＳ２０４で特定した分岐点で推奨経路から逸れる方向に伸びている分岐リンク（リンクＩＤ）６１０と、その分岐リンクに基づいて設定された仮想経由地６２０と、を対応付けて、図８（Ａ）に示す仮想経由地テーブル６００を生成する。
【０１０２】
それから、通信処理部５０４は、ステップＳ２０２で探索された推奨経路と、ステップＳ２０５で設定された仮想経由地と、をナビゲーション装置１００に送信する（ステップＳ２０６）。具体的には、通信処理部５０４は、ステップＳ２０１で経路探索を要求してきたナビゲーション装置１００と通信を確立し、そのナビゲーション装置１００に対して、ステップＳ２０２で探索された推奨経路を構成するリンクＩＤと、ステップＳ２０６で生成した仮想経由地テーブル６００と、を送信する。
【０１０３】
送信後、主制御部５０１は、本フローを終了する。
【０１０４】
以上の処理を情報センタ２００が行うことにより、通信不可エリア内で移動体が推奨経路から逸れた場合でも、ナビゲーション装置１００で簡易にリルートするための目的地（仮想経由地）を提供できる。また、情報センタ２００で設定する仮想経由地は、移動体が推奨経路から逸れる地点（分岐点）ごとに最適な（目的地に最小旅行時間で到達できる）地点が設定されているため、通信不可エリア内で移動体が推奨経路から逸れた場合にも信頼性の高い経路誘導が可能となる。
【０１０５】
なお、上記したフローの各処理単位は、情報センタ２００の処理を理解容易にするために、主な処理内容に応じて分割したものである。処理ステップの分類の仕方やその名称によって、本願発明が制限されることはない。情報センタ２００が行う処理は、さらに多くの処理ステップに分割することもできる。また、１つの処理ステップが、さらに多くの処理を実行してもよい。
【０１０６】
また、上記の実施形態は、本発明の要旨を例示することを意図し、本発明を限定するものではない。多くの代替物、修正、変形例は当業者にとって明らかである。
【０１０７】
以下に、上記実施形態の変形例を挙げる。
【０１０８】
例えば、上記フローのステップ２０５では、経由地設定部５０３は、図８（Ａ）に示す仮想経由地テーブル６００を生成している。しかし、上述したように、本発明は、少なくとも仮想経由地を含む仮想経由地テーブル６００を生成すればよい。
【０１０９】
例えば、経由地設定部５０３は、変形例として、図８（Ｂ）に示す仮想経由地テーブル６００を生成してもよい。図８（Ｂ）の仮想経由地テーブル６００には、図示するように、分岐リンクが含まれず、仮想経由地６２０のみが含まれている。
【０１１０】
このような仮想経由地テーブル６００が情報センタ２００から提供される場合には、ナビゲーション装置１００の経路探索部４０５は、上記フローのステップＳ１０６において、仮想経由地テーブル６００から１つの仮想経由地を選択する際に、例えば、通信不可エリア外で現在位置（分岐点）から一番近い仮想経由地や、移動体が通信不可エリアから脱出する地点で目的地に一番近い仮想経由地、などを選択する。
【０１１１】
それから、経路探索部４０５は、続くステップＳ１０７において、選択された１つの仮想経由地に向かう推奨経路の探索を行えばよい。
【０１１２】
また、経路探索部４０５は、上記フローのステップＳ１０６において、仮想経由地テーブル６００から１つの仮想経由地を選択する際に、上述した分岐リンクを出発地として、目的地（ステップＳ１０１で指定された目的地）までのコスト（旅行時間など）が最小となる経路を探索し、探索したその経路上に存在する仮想経由地を選択するようにしてもよい。
【０１１３】
この場合には、経路探索部４０５は、再度、仮想経由地までの推奨経路を探索する必要はないため、続くステップＳ１０７の処理を省略する。そして、ステップＳ１０８では、経路誘導部４０６は、ステップＳ１０６で仮想経由地を選択するために探索された推奨経路を用いて、経路誘導を行えばよい。
【符号の説明】
【０１１４】
５０・・・ナビゲーションシステム、１００・・・ナビゲーション装置、１０１・・・演算処理部（ナビゲーション装置）、１０２・・・ディスプレイ、１０３・・・記憶装置（ナビゲーション装置）、１０４・・・音声入出力装置、１０５・・・入力装置、１０６・・・車速センサ、１０７・・・ジャイロセンサ、１０８・・・ＧＰＳ受信装置、１０９・・・ＦＭ多重放送受信装置、１１０・・・ビーコン受信装置、１１１・・・通信装置（ナビゲーション装置）、１２１・・・ＣＰＵ（ナビゲーション装置）、１２２・・・ＲＡＭ（ナビゲーション装置）、１２３・・・ＲＯＭ（ナビゲーション装置）、１２４・・・インターフェイス（ナビゲーション装置）、１４１・・・マイクロフォン、１４２・・・スピーカ、１５１・・・タッチパネル、１５２・・・ダイヤルスイッチ、２００・・・情報センタ、２０１・・・演算処理部（情報センタ）、２０２・・・記憶装置（情報センタ）、２０３・・・通信装置（情報センタ）、２２１・・・ＣＰＵ（情報センタ）、２２２・・・ＲＡＭ（情報センタ）、２２３・・・ＲＯＭ（情報センタ）、２２４・・・インターフェイス（情報センタ）、３１０・・・地図データ、３１１・・・メッシュＩＤ、３２０・・・リンクデータ、３２１・・・リンクＩＤ、３２２・・・開始ノード・終了ノード、３２３・・・道路種別、３２４・・・リンク長、３２５・・・リンク旅行時間、３２６・・・開始接続リンク・終了接続リンク、４０１・・・主制御部（ナビゲーション装置）、４０２・・・入力受付部、４０３・・・表示処理部、４０４・・・現在位置算出部、４０５・・・経路探索部（ナビゲーション装置）、４０６・・・経路誘導部、４０７・・・リルート部、４０８・・・通信処理部（ナビゲーション装置）、５０１・・・主制御部（情報センタ）、５０２・・・経路探索部（情報センタ）、５０３・・・経由地設定部、５０４・・・通信処理部（情報センタ）、６００・・・仮想経由地テーブル、６１０・・・分岐リンク、６２０・・・仮想経由地
【技術分野】
【０００１】
本発明は、ナビゲーションシステム、ナビゲーション装置、経路探索方法、および、プログラムに関する。
【背景技術】
【０００２】
近年のナビゲーション装置は、無線通信によって通信可能な外部装置（以下では「情報センタ」とよぶ）を利用して、経路探索が可能になりつつある（例えば、特許文献１）。情報センタ側では、ナビゲーション装置からの要求に応じて推奨経路を探索し、これをナビゲーション装置に提供する。
【０００３】
このようなナビゲーションシステムでは、リアルタイムな交通情報を利用した経路探索が可能である。さらに、ナビゲーション装置側で経路探索を行わなくてよいため、ナビゲーション装置にかかる処理負荷を低減することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−５５６８２号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、上記のようなナビゲーションシステムでは、ナビゲーション装置と情報センタとの間で無線通信が必要となるため、ナビゲーション装置が通信できないエリア（以下では「通信不可エリア」とよぶ）に移動すると、情報センタの情報を利用できない。この場合、ナビゲーション装置側では経路探索できず、スムーズな経路誘導ができなくなる。
【０００６】
本発明は、通信不可エリアにナビゲーション装置が移動した場合に、ナビゲーション装置によるスムーズな経路誘導を可能にするための技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するための本願発明は、推奨経路の探索を行う外部装置と、当該外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置と、を備えるナビゲーションシステムであって、前記ナビゲーション装置は、前記外部装置に、推奨経路の探索を要求する要求手段を備え、前記外部装置は、前記ナビゲーション装置からの要求に基づいて、推奨経路を探索する経路探索手段と、前記ナビゲーション装置が当該外部装置と通信可能な地点である仮想経由地を設定する仮想経由地設定手段と、探索された前記推奨経路と、設定された前記仮想経由地と、を前記ナビゲーション装置に提供する提供手段と、を備え、前記ナビゲーション装置は、前記外部装置から、前記推奨経路、前記仮想経由地を受信する受信手段と、移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施形態が適用されたナビゲーションシステムの概略構成図である。
【図２】ナビゲーション装置の概略構成図である。
【図３】地図データの概略データ構造を示す図である。
【図４】情報センタの概略構成図である。
【図５】ナビゲーション装置の演算処理部、及び、情報センタの演算処理部の機能ブロック図である。
【図６】（Ａ）通信不可エリアについて説明するための図である。（Ｂ）仮想経由地の設定方法について説明するための図である。
【図７】ナビゲーション装置における経路誘導処理を示すフロー図である。
【図８】（Ａ）仮想経由地テーブルの概略データ構造の一例を示す図である。（Ｂ）仮想経由地テーブルの概略データ構造の別例を示す図である。
【図９】情報センタにおける経路探索処理を示すフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態の一例を図面を参照して説明する。
【００１０】
図１は、本発明の一実施形態が適用されたナビゲーションシステム５０の概略構成図である。図示するようにナビゲーションシステム５０は、ナビゲーション装置１００と、情報センタ２００と、を備える。なお、図には、１台のナビゲーション装置１００を示しているが、本発明のナビゲーションシステム５０に適用されるナビゲーション装置１００は複数台であってもよい。また、同様に、図には、１台の情報センタ２００を示しているが、情報センタ２００は複数台であってもよい。
【００１１】
ナビゲーション装置１００は、例えば、通信型の車載用ナビゲーション装置である。もちろん、ナビゲーション装置１００は、これに限られず、携帯電話やＰＤＡなどの携帯端末としてもよい。
【００１２】
情報センタ２００は、推奨経路や交通情報などをナビゲーション装置１００に提供するサーバ装置として機能する一般的な情報処理装置（コンピューター）である。
【００１３】
ナビゲーション装置１００と情報センタ２００は、ネットワークを介して接続され、無線通信により情報のやりとりを行える。
【００１４】
図２は、ナビゲーション装置１００の概略構成図である。図示するように、ナビゲーション装置１００は、演算処理部１０１と、ディスプレイ１０２と、記憶装置１０３と、音声入出力装置１０４（マイクロフォン１４１、スピーカ１４２）と、入力装置１０５（タッチパネル１５１、ダイヤルスイッチ１５２）と、車速センサ１０６と、ジャイロセンサ１０７と、ＧＰＳ受信装置１０８と、ＦＭ多重放送受信装置１０９と、ビーコン受信装置１１０と、通信装置１１２と、を備えている。
【００１５】
演算処理部１０１は、様々な処理を行う中心的ユニットである。例えば、演算処理部１０１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ（Central Processing Unit）１２１と、記憶装置１０３から読み出した地図データ、演算データなどを格納するＲＡＭ（Random Access Memory）１２２と、プログラムやデータを格納するＲＯＭ１２３と、各種ハードウェアを演算処理部１０１に接続するためのＩ／Ｆ（インタフェース）１２４と、を有する。そして、演算処理部１０１は、各デバイスをバス１２５で相互に接続した構成からなる。そして、後述する各機能部（４０１〜４０８）は、ＣＰＵ１２１がＲＡＭ１２２などのメモリに読み出したプログラムを実行することで実現される。
【００１６】
例えば、演算処理部１０１は、車速センサ１０６、ジャイロセンサ１０７、ＧＰＳ受信装置１０８から出力される情報を基にして現在地を検出する。また、得られた現在地情報に基づいて、表示に必要な地図データを記憶装置１０３から読み出す。また、読み出した地図データをグラフィック展開し、そこに現在地マーク（或いは、移動体の位置を示す移動体マーク）を重ねてディスプレイ１０２に表示する。また、情報センタ２００に出発地（現在地）と目的地を送信し、ユーザから指示された出発地と目的地を結ぶ最適な経路（以下では「推奨経路」とよぶ）の探索を、情報センタ２００に要求する。具体的には、演算処理部１０１は、出発地と目的地を含む情報を、通信装置１１１を介して情報センタ２００に送信する。また、演算処理部１０１は、情報センタ２００で探索された推奨経路に従って、音声入出力装置１０４のスピーカ１４２やディスプレイ１０２を用いてユーザを誘導する。
【００１７】
ディスプレイ１０２は、演算処理部１０１で生成されたグラフィック情報を表示するユニットである。ディスプレイ１０２は、液晶ディスプレイや有機ＥＬ（Electro-Luminescence）ディスプレイなどで構成される。
【００１８】
記憶装置１０３は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、例えば、地図データ３１０、音声データ、動画データ、等が記憶されている。また、記憶媒体は、電源供給が停止した場合でも必要なデータを保持可能なフラッシュメモリなどで構成されていてもよい。
【００１９】
図３は、地図データの概略データ構造を示す図である。図示するように、地図データ３１０は、地図上の区画された領域であるメッシュの識別コード（メッシュＩＤ）３１１ごとに、そのメッシュ領域に含まれている道路を構成する各リンクのリンクデータ３２０を含んでいる。
【００２０】
リンクデータ３２０は、リンクの識別コード（リンクＩＤ）３２１ごとに、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３２２、リンクを含む道路の種別情報を示す道路種別３２３、リンクの長さを示すリンク長情報３２４、リンク旅行時間３２５、２つのノードにそれぞれ接続するリンクの識別コード（接続リンクＩＤ）３２６、などを含んでいる。なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードを区別することで、道路の上り方向と下り方向を、それぞれ別のリンクとして管理することができる。また、地図データ３１０には、地図表示における道路や施設を表示するための描画データが格納されている。
【００２１】
図２に戻り、音声入出力装置１０４は、音声入力装置としてマイクロフォン１４１と、音声出力装置としてスピーカ１４２と、を備える。マイクロフォン１４１は、運転手やその他の同乗者から発せられた音声などの、ナビゲーション装置１００の外部の音声を取得する。スピーカ１４２は、演算処理部１０１で生成された音声信号を出力する。これらのマイクロフォン１４１とスピーカ１４２は、車両の所定の部位に、別個に配置されている。
【００２２】
入力装置１０５は、ユーザからの指示を受け付けるユニットである。入力装置１０５は、タッチパネル１５１と、ダイヤルスイッチ１５２と、その他のハードスイッチ（図示せず）であるスクロールキー、縮尺変更キーなどで構成される。
【００２３】
タッチパネル１５１は、ディスプレイ１０２の表示面に貼られた透過性のある操作パネルである。タッチパネル１５１は、ディスプレイ１０２に表示された画像のＸＹ座標と対応したタッチ位置を特定し、タッチ位置を座標に変換して出力する。タッチパネル１５１は、感圧式または静電式の入力検出素子などにより構成される。
【００２４】
ダイヤルスイッチ１５２は、時計回り及び反時計回りに回転可能に構成され、所定の角度の回転ごとにパルス信号を発生し、演算処理部１０１に出力する。演算処理部１０１では、パルス信号の数から、ダイヤルスイッチ１５２の回転角度を求める。
【００２５】
車速センサ１０６、ジャイロセンサ１０７、及び、ＧＰＳ受信装置１０８は、移動体（ナビゲーション装置１００）の現在位置（自車位置）などを検出するために使用される。車速センサ１０６は、車速を算出するために用いる車速データを出力するセンサである。ジャイロセンサ１０７は、光ファイバジャイロや振動ジャイロ等で構成され、移動体の回転による角速度を検出するものである。ＧＰＳ受信装置１０８は、ＧＰＳ衛星からの信号を受信し、移動体とＧＰＳ衛星間の距離とその距離の変化率を３個以上の衛星に対して測定することで、移動体の現在位置や進行速度を測定する。
【００２６】
ＦＭ多重放送受信装置１０９は、ＦＭ多重放送局から送られてくるＦＭ多重放送信号を受信する。ＦＭ多重放送には、ＶＩＣＳ（Vehicle Infomation Communication System：登録商標）情報の概略現況交通情報、規制情報、ＳＡ／ＰＡ（サービスエリア／パーキングエリア）情報、駐車場情報、天気情報などのＦＭ多重一般情報としてラジオ局が提供する文字情報などがある。
【００２７】
ビーコン受信装置１１０は、ビーコンから送られてくる渋滞情報、規制情報、ＳＡ／ＰＡ情報、駐車場情報などを受信する。
【００２８】
通信装置１１１は、情報センタ２００と通信するための装置であり、情報センタ２００から提供された推奨経路、後述する仮想経由地（仮想経由地テーブル６００）などを受信する。
【００２９】
また、図４は、情報センタ２００の概略構成図である。図示するように、情報センタ２００は、演算処理部２０１と、記憶装置２０２と、通信装置２０３と、を備えている。
【００３０】
演算処理部２０１は、様々な処理を行う中心的ユニットである。例えば、演算処理部２０１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ２２１と、記憶装置２０２から読み出した地図データ、演算データなどを格納するＲＡＭ２２２と、プログラムやデータを格納するＲＯＭ２２３と、各種ハードウェアを演算処理部２０１に接続するためのＩ／Ｆ（インタフェース）２２４と、を有する。そして、演算処理部１０１は、各デバイスをバス１２５で相互に接続した構成からなる。そして、後述する各機能部（５０１〜５０４）は、ＣＰＵ２２１がＲＡＭ２２２などのメモリに読み出したプログラムを実行することで実現される。
【００３１】
例えば、演算処理部２０１は、ナビゲーション装置１００から経路探索の要求を受け付けると、記憶装置２０２に記憶されている地図データを用いて、ナビゲーション装置１００から受信した出発地と目的地を結ぶ推奨経路を探索する。また、演算処理部２０１は、ナビゲーション装置１００が情報センタ２００と通信可能な地点であって、目的地までの経由地として最適な地点を仮想経由地として設定する。仮想経由地の具体的な設定方法については後述する。
【００３２】
記憶装置２０２は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭやＨＤＤやＩＣカードといった記憶媒体で構成される。この記憶媒体には、図３に示す地図データ３１０と同様の地図データ、等が記憶されている。また、記憶媒体は、電源供給が停止した場合でも必要なデータを保持可能なフラッシュメモリなどで構成されていてもよい。
【００３３】
通信装置２０３は、ナビゲーション装置１００と通信するための装置であり、演算処理部２０１で探索された推奨経路、設定された仮想経由地（仮想経由地テーブル６００）などを送信する。
【００３４】
図５は、ナビゲーション装置１００の演算処理部１０１、及び、情報センタ２００の演算処理部２０１の機能ブロック図である。図示するように、ナビゲーション装置１００の演算処理部１０１は、主制御部４０１と、入力受付部４０２と、表示処理部４０３と、現在位置算出部４０４と、経路探索部４０５と、経路誘導部４０６と、リルート部４０７と、通信処理部４０８と、を有する。また、情報センタ２００の演算処理部２０１は、主制御部５０１と、経路探索部５０２と、経由地設定部５０３と、通信処理部５０４と、を有する。
【００３５】
ナビゲーション装置１００の主制御部４０１は、演算処理部１０１の各部を統括して制御する処理を行う。
【００３６】
入力受付部４０２は、入力装置１０５に入力されたユーザからの要求を受け付け、その要求内容を解析する。入力受付部４０２は、解析結果に応じたデータを主制御部４０１に通知する。例えば、入力受付部４０２は、ナビゲーション装置１００に、電源の投入、切断を指示する要求、推奨経路の探索（或いは、経路誘導の開始）を指示する要求、等を受け付け、主制御部４０１に通知する。
【００３７】
表示処理部４０３は、ディスプレイ１０２に、地図、推奨経路、ユーザに通知する各種メッセージ、等を表示させる。具体的には、表示処理部４０３は、ディスプレイ１０２に表示させるための描画コマンドを生成して通知する。なお、表示処理部４０３は、地図をディスプレイ１０２に表示させる際には、表示が要求された領域（例えば、推奨経路全体を表示するのに必要な領域）にある地図データを記憶装置１０３から抽出し、指定された描画方式で、道路、その他の地図構造物、現在位置、目的地、推奨経路、等を描画するように地図コマンドを生成する。また、表示処理部４０３は、ディスプレイ１０２に表示させた地図上に、車両の位置を示す車両マークや各種設定画面などを表示させる。
【００３８】
現在位置算出部４０４は、ナビゲーション装置１００の現在位置を算出する。具体的には、現在位置算出部４０４は、車速センサ１０６で出力された車速データに基づいて算出した移動体（ナビゲーション装置１００）の進行速度、および、ジャイロセンサ１０７で検出した角速度データを各々積分して結果得られる距離データおよび角度データを用い、そのデータを時間軸で積分していくことにより、初期位置（Ｘ，Ｙ）から移動後（自車走行後）の位置（Ｘ’，Ｙ’）を定期的に演算する。また、演算結果を用いて、マップマッチ処理することにより、形状の相関が最も高い道路（リンク）上に現在位置を合わせ込む。また、定期的にＧＰＳ受信装置１０８の出力データを用いて現在位置を修正する。なお、移動体（ナビゲーション装置１００）が停止しているときには、ＧＰＳ受信装置１０８の出力データだけを用いて現在位置を求めてもよい。
【００３９】
ナビゲーション装置１００の経路探索部４０５は、移動体（ナビゲーション装置１００）が通信不可エリア内において推奨経路から逸れた場合に、情報センタ２００で設定された仮想経由地に向けた簡易的な経路探索を行う。具体的には、経路探索部４０５は、ダイクストラ法等を用いて、現在地と、情報センタ２００で設定された仮想経由地と、の２地点間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部４０５は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ１２２等のメモリに記憶しておく。そして、経路探索部４０５は、探索した推奨経路を、表示処理部４０３を介して、ディスプレイ１０２に表示（強調表示）する。このとき、経路探索部４０５は、例えば、推奨経路の現在置から仮想経路地までの全行程が１画面に収まる縮尺の地図に、推奨経路をディスプレイ１０２に表示する。
【００４０】
なお、経路探索部４０５が行う経路探索には、ＦＭ多重放送受信装置１０９やビーコン受信装置１１０から受信した交通情報を用いてもよいし、用いないようにしてもよい。
【００４１】
経路誘導部４０６は、情報センタ２００から取得（受信）した推奨経路、又は、経路探索部４０５で探索された推奨経路、を用いて経路誘導を行う。具体的には、経路誘導部４０６は、表示処理部４０３を介して、ディスプレイ１０２に表示された地図の範囲に含まれている推奨経路を表示（強調表示）する。このとき、経路誘導部４０６は、移動体（ナビゲーション装置１００）の現在位置を示す移動体マーク（車両マーク）を推奨経路上（例えば、画面中心）に表示する。また、経路誘導部４０６は、推奨経路の情報と現在位置とを比較して、主要な交差点等を通過する前に直進すべきか、右左折すべきかを、ディスプレイ１０２に表示させるとともに、音声入出力装置１０４のスピーカ１４２を用いて音声でユーザに知らせる。
【００４２】
リルート部４０７は、移動体（ナビゲーション装置１００）が推奨経路から逸れた場合に、現在地（例えば、推奨経路から逸れた地点）から目的地までの推奨経路を、情報センタ２００に要求する。具体的には、リルート部４０７は、現在地と目的地を含む情報を、通信装置１１１を介して情報センタ２００に送信する。
【００４３】
ただし、リルート部４０７は、移動体が通信不可エリア内において推奨経路から逸れた場合には、現在地（例えば、推奨経路から逸れた地点のリンク）から仮想経由地までの推奨経路を、自装置内の経路探索部４０５に探索させる。
【００４４】
ナビゲーション装置１００の通信処理部４０８は、情報センタ２００とのデータのやりとりを制御する。例えば、通信処理部４０８は、経路誘導部４０６或いはリルート部４０７からの指示に基づいて、情報センタ２００との通信を確立し、経路探索を要求するためのデータを出力する。また、通信処理部４０８は、情報センタ２００から出力された推奨経路や仮想経由地（仮想経由地テーブル６００）などを受信する。
【００４５】
また、情報センタ２００の主制御部５０１は、演算処理部２０１の各部を統括して制御する処理を行う。
【００４６】
情報センタ２００の経路探索部５０２は、ナビゲーション装置１００から受信した現在地（出発地や推奨経路から逸れた地点）と目的地の間の推奨経路を探索する。具体的には、経路探索部５０２は、ナビゲーション装置１００から受信した現在地と目的地の２地点間を結ぶ経路のコスト（例えば、総距離や総旅行時間）が最小となる経路を探索する。このとき、経路探索部５０２は、探索した推奨経路を構成する各リンクの識別コード（リンクＩＤ）３２１を、それぞれ対応付けてＲＡＭ２２２等のメモリに記憶しておく。
【００４７】
なお、経路探索部５０２が行う経路探索には、ナビゲーション装置１００から収集した情報を基に生成された統計情報（例えば、渋滞などの交通情報）を用いてもよいし、用いないようにしてもよい。
【００４８】
経由地設定部５０３は、上述した仮想経由地を設定する。ただし、経由地設定部５０３は、経路探索部５０２で探索された推奨経路上の通信不可エリアが存在する場合に、仮想経由地を設定する。そのため、経由地設定部５０３は、経路探索部５０２で推奨経路が探索されると、まず、その推奨経路上の通信不可エリアを特定する。
【００４９】
図６（Ａ）は、通信不可エリアについて説明するための図である。図示するように、経由地設定部５０３は、推奨経路上に存在する全ての通信不可エリア（点線で囲まれたエリア）を特定する。なお、通信不可エリアは、記憶装置２０２に記憶されている地図データ３１０に予め格納しておく。
【００５０】
そして、経由地設定部５０３は、通信不可エリアを特定すると、通信不可エリアごとに、仮想経由地を設定する。
【００５１】
ここで、図６（Ｂ）は、仮想経由地の設定方法について説明するための図である。図示するように、経由地設定部５０３は、通信不可エリア内において、推奨経路上の分岐点を特定する。この分岐点は、移動体が推奨経路から逸れる可能性がある地点とする。そして、経由地設定部５０３は、分岐点で推奨経路から逸れているリンクの延長（点線で示す道路）上で、かつ、通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）を、仮想経由地として設定する。
【００５２】
具体的には、経由地設定部５０３は、分岐点で推奨経路から逸れているリンクを出発地として、目的地までのコスト（旅行時間など）が最小となる経路を探索し、探索したその経路上において、通信不可エリアから脱出する地点を、仮想経由地として設定する。
【００５３】
ただし、本発明の仮想経由地の設定方法はこれに限定されない。例えば、経由地設定部５０３は、通信不可エリア外で分岐点から一番近い地点を仮想経由地として設定してもよい。或いは、分岐点が存在する通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）で、目的地に一番近い地点を仮想経由地として設定してもよい。
【００５４】
なお、同一の通信不可エリア内に、分岐点が複数個存在する場合には、経由地設定部５０３は、分岐点ごとに仮想経由地を設定する（図示する例では同一エリア内に２箇所）。
【００５５】
また、１つの分岐点に対して複数の仮想経由地が設定されてしまう場合には、例えば、経由地設定部５０３は、通信不可エリア外で分岐点から一番近い地点や、分岐点が存在する通信不可エリアから脱出する地点で目的地に一番近い地点、などを仮想経由地として設定する。
【００５６】
そして、経由地設定部５０３は、仮想経由地を設定すると、少なくとも仮想経由地を含むテーブル（後述する仮想経由地テーブル６００）を生成し、ＲＡＭ２２２等のメモリに格納する。
【００５７】
なお、経由地設定部５０３による仮想経由地設定のための経路探索には、ナビゲーション装置１００から収集した情報を基に生成された統計情報（例えば、渋滞などの交通情報）を用いてもよいし、用いないようにしてもよい。
【００５８】
図５に戻り、情報センタ２００の通信処理部５０４は、ナビゲーション装置１００とのデータのやりとりを制御する。例えば、通信処理部５０４は、ナビゲーション装置１００から、経路探索の要求を受け付ける（受信する）。また、通信処理部５０４は、経路探索を要求してきたナビゲーション装置１００を特定して通信を確立し、経路探索部５０２で探索された推奨経路や、経由地設定部５０３で設定された仮想経由地（仮想経由地テーブル６００）などを送信する。
【００５９】
なお、上記した各構成要素は、ナビゲーションシステム５０の構成を理解容易にするために、主な処理内容に応じて分類したものである。構成要素の分類の仕方やその名称によって、本願発明が制限されることはない。ナビゲーションシステム５０の構成は、処理内容に応じて、さらに多くの構成要素に分類することもできる。また、１つの構成要素がさらに多くの処理を実行するように分類することもできる。
【００６０】
また、各機能部（４０１〜４０８、５０１〜５０４）は、ハードウエア（ＡＳＩＣなど）により構築されてもよい。また、各機能部の処理が一つのハードウエアで実行されてもよいし、複数のハードウエアで実行されてもよい。
【００６１】
次に、上記構成からなるナビゲーションシステム５０の特徴的な動作について説明する。
【００６２】
＜経路誘導処理＞
図７は、ナビゲーション装置１００で行われる経路誘導処理を示すフローチャートである。
【００６３】
ナビゲーション装置１００の主制御部４０１は、例えば、電源が投入されるタイミング、或いは、経路誘導開始の指示のタイミングで、本フローを開始する。
【００６４】
図示するように、本フローを開始すると、経路誘導部４０６は、まず、情報センタ２００に対して、経路探索を要求する（ステップＳ１０１）。具体的には、経路誘導部４０６は、出発地と目的地の指定を入力受付部４０２を介して受け付ける。ただし、出発地は、現在位置算出部４０４によって算出される移動体の現在位置としてもよい。出発地と目的地が指定されると、経路誘導部４０６は、通信処理部４０８を介して、出発地と目的地を情報センタ２００に送信し、経路探索の要求を行う。
【００６５】
このとき、情報センタ２００では、ステップＳ１０１の要求に応じて経路探索が行われ（後述する「経路探索処理」）、探索された推奨経路と、仮想経由地テーブル６００が情報センタ２００から出力される。
【００６６】
そして、経路誘導部４０６は、情報センタ２００から出力された推奨経路と、仮想経由地を受信する（ステップＳ１０２）。具体的には、経路誘導部４０６は、通信処理部４０８を介して、推奨経路を構成するリンクＩＤと、仮想経由地テーブル６００を受信する。
【００６７】
その後、経路誘導部４０６は、ステップＳ１０２で受信した推奨経路を用いて、経路誘導を開始する。
【００６８】
経路誘導を開始すると、経路誘導部４０６は、移動体（ナビゲーション装置１００）が目的地に到達したか否か判別する（ステップＳ１０３）。具体的には、経路誘導部４０６は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０１で指定された目的地から所定の距離内である場合には、移動体が目的地に到達したと判定する。一方、経路誘導部４０６は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０１で指定された目的地から所定の距離以上離れている場合には、移動体は目的地に到達していないと判定する。
【００６９】
ここで、経路誘導部４０６は、移動体が目的地に到達したと判定した場合には（ステップＳ１０３；Ｙｅｓ）、そのまま経路誘導を終了する（本フローを終了する）。
【００７０】
一方、経路誘導部４０６は、移動体が目的地に到達していないと判定した場合には（ステップＳ１０３；Ｎｏ）、処理をステップＳ１０４に移行する。
【００７１】
処理がステップＳ１０４に移行すると、リルート部４０７は、リルートの必要があるか否か判別する（ステップＳ１０４）。具体的には、リルート部４０７は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０２で情報センタ２００から受信した推奨経路上にない（推奨経路と現在位置の距離が所定閾値以上の）場合に、リルートの必要があると判定する。すなわち、リルート部４０７は、移動体が推奨経路から逸れた場合に、リルートの必要があると判定する。一方、リルート部４０７は、現在位置算出部４０４で算出された現在位置が、ステップＳ１０２で情報センタ２００から受信した推奨経路上にある（推奨経路と現在位置の距離が所定閾値未満の）場合に、リルートの必要はないと判定する。すなわち、リルート部４０７は、移動体が推奨経路に従って移動（走行）している間、リルートの必要はないと判定する。
【００７２】
ここで、リルート部４０７は、リルートの必要がないと判定した場合には（ステップＳ１０４；Ｎｏ）、処理をステップＳ１０３に戻す。こうして、移動体が目的地に到達する、或いは、移動体が推奨経路から逸れる、までステップＳ１０３、Ｓ１０４の処理が繰り返し実行される。
【００７３】
一方、ステップＳ１０４において、リルート部４０７は、リルートの必要があると判定した場合には（ステップＳ１０４；Ｙｅｓ）、処理をステップＳ１０５に移行する。
【００７４】
処理がステップＳ１０５に移行すると、リルート部４０７は、情報センタ２００と通信可能（推奨経路を取得可能）か否か判別する（ステップＳ１０５）。例えば、リルート部４０７は、一般的な方法によって情報センタ２００と通信を確立できた場合に、情報センタ２００と通信可能と判定する。一方、リルート部４０７は、通信を確立できない場合には、情報センタ２００と通信不可能と判定する。
【００７５】
そして、リルート部４０７は、情報センタ２００と通信可能と判定した場合には（ステップＳ１０５；Ｙｅｓ）、処理をステップＳ１０１に戻す。ただし、ステップＳ１０５からステップＳ１０１に処理が戻された場合には、経路誘導部４０６は、現在位置算出部４０４によって算出される移動体の現在位置を出発地としてステップＳ１０１の処理を実行する。これにより、ナビゲーションシステム５０では、移動体が推奨経路から逸れた地点から目的地までの推奨経路を再探索することができる。
【００７６】
一方、リルート部４０７は、情報センタ２００と通信不可能と判定した場合には（ステップＳ１０５；Ｎｏ）、処理をステップＳ１０６に移行する。
【００７７】
情報センタ２００と通信不可能（推奨経路を取得不可能）である場合には、ナビゲーション装置１００は情報センタ２００から推奨経路を再探索させることができない。そこで、ナビゲーション装置１００は、移動体が推奨経路から逸れた地点から、設定されている仮想経由地までの推奨経路を自装置で探索する。
【００７８】
そのために、経路探索部４０５は、処理がステップＳ１０６に移行すると、まず、仮想経由地の選択（決定）を行う（ステップＳ１０６）。具体的には、経路探索部４０５は、ステップＳ１０２で情報センタ２００から取得した仮想経由地テーブル６００の中から１つの仮想経由地を選択する。
【００７９】
図８（Ａ）は、仮想経由地テーブル６００の概略データ構造の一例を示す図である。図示するように、仮想経由地テーブル６００は、情報センタ２００で設定された仮想経由地ごとのレコード６３０からなる。各レコード６３０には、分岐リンク６１０と、仮想経由地６２０と、が対応付けて格納される。分岐リンク６１０は、推奨経路上の通信不可エリア内における分岐点（例えば、トンネル内の分岐点）で、推奨経路から逸れる方向のリンク（リンクＩＤ）である。仮想経由地６２０は、その分岐点ごとに設定された仮想経由地の位置を示す座標データである。なお、仮想経由地テーブル６００に含まれるレコード６３０数は１つでもよい。
【００８０】
上記の仮想経由地テーブル６００から１つの仮想経由地を選択する際に、経路探索部４０５は、まず、移動体が位置しているリンクを特定する。そして、移動体が位置しているリンクに対応する分岐リンク６１０を、仮想経由地テーブル６００から検索する。それから、経路探索部４０５は、検索した分岐リンク６１０に対応付けられている仮想経由地６２０を、推奨経路を再探索（リルート）するための目的地（経由地）として選択する。
【００８１】
続いて、経路探索部４０５は、移動体が推奨経路から逸れた地点から、ステップＳ１０６で選択された仮想経由地までの推奨経路を探索する（ステップＳ１０７）。具体的には、経路探索部４０５は、ダイクストラ法等を用いて、現在位置算出部４０４で算出された現在位置と、ステップＳ１０６で選択された仮想経由地と、の２地点間を結ぶ経路のコストが最小となる経路を探索する。なお、ステップＳ１０７での経路探索は、移動体が推奨経路から逸れた地点から仮想経由地までの経路探索であるため、ナビゲーション装置１００にかかる処理負荷は非常に低いものとなる。
【００８２】
その後、経路誘導部４０６は、ステップＳ１０７で探索された推奨経路を用いて、経路誘導を再開する。
【００８３】
そして、経路誘導部４０６は、情報センタ２００と通信可能になる位置に移動体が到達するまで、仮想経由地に向けて経路誘導を行う。これに並行して、リルート部４０７は、ステップＳ１０５の処理と同様に、情報センタ２００と通信可能か否か判別する（ステップＳ１０８）。
【００８４】
そして、リルート部４０７は、情報センタ２００と通信可能になる位置に移動体が到達するまで（ステップＳ１０８；Ｎｏ）、ステップＳ１０８の処理を繰り返す。
【００８５】
一方、リルート部４０７は、情報センタ２００と通信可能と判定した場合には（ステップＳ１０８；Ｙｅｓ）、処理をステップＳ１０１に戻す。ただし、ステップＳ１０８からステップＳ１０１に処理が戻された場合には、経路誘導部４０６は、現在位置算出部４０４によって算出される移動体の現在位置を出発地としてステップＳ１０１の処理を実行する。これにより、ナビゲーション装置１００は、通信不可エリアを脱出するタイミング（地点）で、現在位置からステップＳ１０１で指定された目的地までの推奨経路を、情報センタ２００から取得できる。
【００８６】
以上の処理をナビゲーション装置１００が行うことにより、通信不可エリア内で移動体が推奨経路から逸れた場合にも、即座にリルートできるため、スムーズな経路誘導が可能になる。また、その場合のリルートは、仮想経由地までの経路探索としているため、ナビゲーション装置１００にかかる処理負荷を最低限に抑えることができる。さらには、ステップＳ１０８において、移動体が実際に仮想経由地に到達していなくても、情報センタ２００と通信可能であればすぐに推奨経路を再取得するため、効率的に情報センタ２００を利用することができる。
【００８７】
なお、上記したフローの各処理単位は、ナビゲーション装置１００の処理を理解容易にするために、主な処理内容に応じて分割したものである。処理ステップの分類の仕方やその名称によって、本願発明が制限されることはない。ナビゲーション装置１００が行う処理は、さらに多くの処理ステップに分割することもできる。また、１つの処理ステップが、さらに多くの処理を実行してもよい。
【００８８】
＜経路探索処理＞
図９は、情報センタ２００で行われる経路探索処理を示すフローチャートである。
【００８９】
情報センタ２００の主制御部５０１は、例えば、電源が投入されるタイミングで本フローを開始し、ナビゲーション装置１００からの情報を受信するまで待機する。
【００９０】
そして、情報センタ２００の経路探索部５０２は、ナビゲーション装置１００からの要求（経路探索の要求）を受け付けると（ステップＳ２０１）、処理をステップＳ２０２に移行する。具体的には、経路探索部５０２は、通信処理部５０４を介して、ナビゲーション装置１００から出発地と目的地を含むデータを受信して、経路探索の要求を受け付ける。
【００９１】
そして、経路探索部５０２は、ナビゲーション装置１００からの要求に応じた推奨経路を探索する（ステップＳ２０２）。具体的には、経路探索部５０２は、ダイクストラ法等を用いて、ステップＳ２０１で受信した出発地と目的地の２地点間を結ぶ経路のコストが最小となる経路を探索する。なお、経路探索部５０２は、リアルタイムな交通情報、統計情報などを利用して経路探索することができる。
【００９２】
続いて、経由地設定部５０３は、経路探索部５０２で推奨経路が探索されると、その推奨経路上に通信不可エリアが有るか否か判別する（ステップＳ２０３）。具体的には、経由地設定部５０３は、メモリなどに予め格納されている通信不可エリアと、ステップＳ２０２で探索された推奨経路と、を比較して、推奨経路が通過している通信不可エリアが少なくとも１つは存在する場合には、推奨経路上に通信不可エリアがあると判定する。一方、推奨経路が通過している通信不可エリアが１つも存在しない場合には、推奨経路上に通信不可エリアはないと判定する。
【００９３】
ここで、経由地設定部５０３は、探索された推奨経路上に通信不可エリアはないと判定した場合には（ステップＳ２０３；Ｎｏ）、仮想経由地の設定は行わず、処理をステップＳ２０６に移行する。
【００９４】
一方、経由地設定部５０３は、探索された推奨経路上に通信不可エリアがあると判定した場合には（ステップＳ２０３；Ｙｅｓ）、処理をステップＳ２０４に移行する。
【００９５】
処理がステップＳ２０４に移行すると、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点が有るか否か判別する（ステップＳ２０４）。具体的には、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリア内において、その推奨経路上に分岐点（交差点、リンクの分岐など）が少なくとも１つは存在する場合には、通信不可エリア内の推奨経路上に分岐点が有ると判定する。一方、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリア内において、その推奨経路上に分岐点が１つも存在しない場合には、通信不可エリア内の推奨経路上に分岐点はないと判定する。
【００９６】
ここで、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点はないと判定した場合には（ステップＳ２０４；Ｎｏ）、移動体が通信不可エリア内で推奨経路から逸れることはないため、仮想経由地の設定は行わず、処理をステップＳ２０６に移行する。
【００９７】
一方、経由地設定部５０３は、通信不可エリア内の推奨経路上に分岐点が有ると判定した場合には（ステップＳ２０４；Ｙｅｓ）、処理をステップＳ２０５に移行する。
【００９８】
処理がステップＳ２０５に移行すると、経由地設定部５０３は、仮想経由地を設定する（ステップＳ２０５）。なお、経由地設定部５０３は、ステップＳ２０３で推奨経路が通過していると特定された通信不可エリアごとに、仮想経由地を設定する。
【００９９】
例えば、経由地設定部５０３は、ステップＳ２０４で特定した分岐点で推奨経路から逸れる方向に伸びているリンク（分岐リンク）の終端（終了ノード）を出発地として、ステップＳ２０１でナビゲーション装置１００から受信した目的地までのコストが最小となる経路を探索する。そして、探索された経路上であり、かつ、通信不可エリアから脱出する地点（情報センタ２００と通信可能となる地点）を、仮想経由地として設定する。
【０１００】
なお、ステップＳ２０５の処理は、推奨経路上の全ての通信不可エリア内における全ての分岐点ごとに行われるため、複数の仮想経由地が設定され得る。
【０１０１】
そして、経由地設定部５０３は、仮想経由地を設定すると、ステップＳ２０４で特定した分岐点で推奨経路から逸れる方向に伸びている分岐リンク（リンクＩＤ）６１０と、その分岐リンクに基づいて設定された仮想経由地６２０と、を対応付けて、図８（Ａ）に示す仮想経由地テーブル６００を生成する。
【０１０２】
それから、通信処理部５０４は、ステップＳ２０２で探索された推奨経路と、ステップＳ２０５で設定された仮想経由地と、をナビゲーション装置１００に送信する（ステップＳ２０６）。具体的には、通信処理部５０４は、ステップＳ２０１で経路探索を要求してきたナビゲーション装置１００と通信を確立し、そのナビゲーション装置１００に対して、ステップＳ２０２で探索された推奨経路を構成するリンクＩＤと、ステップＳ２０６で生成した仮想経由地テーブル６００と、を送信する。
【０１０３】
送信後、主制御部５０１は、本フローを終了する。
【０１０４】
以上の処理を情報センタ２００が行うことにより、通信不可エリア内で移動体が推奨経路から逸れた場合でも、ナビゲーション装置１００で簡易にリルートするための目的地（仮想経由地）を提供できる。また、情報センタ２００で設定する仮想経由地は、移動体が推奨経路から逸れる地点（分岐点）ごとに最適な（目的地に最小旅行時間で到達できる）地点が設定されているため、通信不可エリア内で移動体が推奨経路から逸れた場合にも信頼性の高い経路誘導が可能となる。
【０１０５】
なお、上記したフローの各処理単位は、情報センタ２００の処理を理解容易にするために、主な処理内容に応じて分割したものである。処理ステップの分類の仕方やその名称によって、本願発明が制限されることはない。情報センタ２００が行う処理は、さらに多くの処理ステップに分割することもできる。また、１つの処理ステップが、さらに多くの処理を実行してもよい。
【０１０６】
また、上記の実施形態は、本発明の要旨を例示することを意図し、本発明を限定するものではない。多くの代替物、修正、変形例は当業者にとって明らかである。
【０１０７】
以下に、上記実施形態の変形例を挙げる。
【０１０８】
例えば、上記フローのステップ２０５では、経由地設定部５０３は、図８（Ａ）に示す仮想経由地テーブル６００を生成している。しかし、上述したように、本発明は、少なくとも仮想経由地を含む仮想経由地テーブル６００を生成すればよい。
【０１０９】
例えば、経由地設定部５０３は、変形例として、図８（Ｂ）に示す仮想経由地テーブル６００を生成してもよい。図８（Ｂ）の仮想経由地テーブル６００には、図示するように、分岐リンクが含まれず、仮想経由地６２０のみが含まれている。
【０１１０】
このような仮想経由地テーブル６００が情報センタ２００から提供される場合には、ナビゲーション装置１００の経路探索部４０５は、上記フローのステップＳ１０６において、仮想経由地テーブル６００から１つの仮想経由地を選択する際に、例えば、通信不可エリア外で現在位置（分岐点）から一番近い仮想経由地や、移動体が通信不可エリアから脱出する地点で目的地に一番近い仮想経由地、などを選択する。
【０１１１】
それから、経路探索部４０５は、続くステップＳ１０７において、選択された１つの仮想経由地に向かう推奨経路の探索を行えばよい。
【０１１２】
また、経路探索部４０５は、上記フローのステップＳ１０６において、仮想経由地テーブル６００から１つの仮想経由地を選択する際に、上述した分岐リンクを出発地として、目的地（ステップＳ１０１で指定された目的地）までのコスト（旅行時間など）が最小となる経路を探索し、探索したその経路上に存在する仮想経由地を選択するようにしてもよい。
【０１１３】
この場合には、経路探索部４０５は、再度、仮想経由地までの推奨経路を探索する必要はないため、続くステップＳ１０７の処理を省略する。そして、ステップＳ１０８では、経路誘導部４０６は、ステップＳ１０６で仮想経由地を選択するために探索された推奨経路を用いて、経路誘導を行えばよい。
【符号の説明】
【０１１４】
５０・・・ナビゲーションシステム、１００・・・ナビゲーション装置、１０１・・・演算処理部（ナビゲーション装置）、１０２・・・ディスプレイ、１０３・・・記憶装置（ナビゲーション装置）、１０４・・・音声入出力装置、１０５・・・入力装置、１０６・・・車速センサ、１０７・・・ジャイロセンサ、１０８・・・ＧＰＳ受信装置、１０９・・・ＦＭ多重放送受信装置、１１０・・・ビーコン受信装置、１１１・・・通信装置（ナビゲーション装置）、１２１・・・ＣＰＵ（ナビゲーション装置）、１２２・・・ＲＡＭ（ナビゲーション装置）、１２３・・・ＲＯＭ（ナビゲーション装置）、１２４・・・インターフェイス（ナビゲーション装置）、１４１・・・マイクロフォン、１４２・・・スピーカ、１５１・・・タッチパネル、１５２・・・ダイヤルスイッチ、２００・・・情報センタ、２０１・・・演算処理部（情報センタ）、２０２・・・記憶装置（情報センタ）、２０３・・・通信装置（情報センタ）、２２１・・・ＣＰＵ（情報センタ）、２２２・・・ＲＡＭ（情報センタ）、２２３・・・ＲＯＭ（情報センタ）、２２４・・・インターフェイス（情報センタ）、３１０・・・地図データ、３１１・・・メッシュＩＤ、３２０・・・リンクデータ、３２１・・・リンクＩＤ、３２２・・・開始ノード・終了ノード、３２３・・・道路種別、３２４・・・リンク長、３２５・・・リンク旅行時間、３２６・・・開始接続リンク・終了接続リンク、４０１・・・主制御部（ナビゲーション装置）、４０２・・・入力受付部、４０３・・・表示処理部、４０４・・・現在位置算出部、４０５・・・経路探索部（ナビゲーション装置）、４０６・・・経路誘導部、４０７・・・リルート部、４０８・・・通信処理部（ナビゲーション装置）、５０１・・・主制御部（情報センタ）、５０２・・・経路探索部（情報センタ）、５０３・・・経由地設定部、５０４・・・通信処理部（情報センタ）、６００・・・仮想経由地テーブル、６１０・・・分岐リンク、６２０・・・仮想経由地
【特許請求の範囲】
【請求項１】
推奨経路の探索を行う外部装置と、当該外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置と、を備えるナビゲーションシステムであって、
前記ナビゲーション装置は、
前記外部装置に、推奨経路の探索を要求する要求手段を備え、
前記外部装置は、
前記ナビゲーション装置からの要求に基づいて、推奨経路を探索する経路探索手段と、
前記ナビゲーション装置が当該外部装置と通信可能な地点である仮想経由地を設定する仮想経由地設定手段と、
探索された前記推奨経路と、設定された前記仮想経由地と、を前記ナビゲーション装置に提供する提供手段と、を備え、
前記ナビゲーション装置は、
前記外部装置から、前記推奨経路、前記仮想経由地を受信する受信手段と、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、
前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える、
ことを特徴とするナビゲーションシステム。
【請求項２】
請求項１に記載のナビゲーションシステムであって、
前記ナビゲーション装置は、経路誘導手段をさらに備え、
前記経路誘導手段は、
前記外部装置から推奨経路を取得できる場合には、前記受信手段で受信された推奨経路に基づいて経路誘導を行い、
前記外部装置から推奨経路を取得できない場合には、前記経由経路探索手段で探索された経路に基づいて、前記外部装置から推奨経路を取得可能になる位置に移動体が到達するまで前記仮想経由地に向けた経路誘導を行う、
ことを特徴とするナビゲーションシステム。
【請求項３】
外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置であって、
前記外部装置から、推奨経路、仮想経由地を受信する受信手段と、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、
前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える、
ことを特徴とするナビゲーション装置。
【請求項４】
請求項３に記載のナビゲーション装置であって、
経路誘導手段をさらに備え、
前記経路誘導手段は、
前記外部装置から推奨経路を取得できる場合には、前記受信手段で受信された推奨経路に基づいて経路誘導を行い、
前記外部装置から推奨経路を取得できない場合には、前記経由経路探索手段で探索された経路に基づいて、前記外部装置から推奨経路を取得可能になる位置に移動体が到達するまで前記仮想経由地に向けた経路誘導を行う、
ことを特徴とするナビゲーション装置。
【請求項５】
請求項３又は４に記載のナビゲーション装置であって、
前記経由経路探索手段は、
前記受信手段で複数の仮想経由地が受信された場合には、所定の規則に従って１つの仮想経由地を選択し、選択された当該仮想経由地に至る経路を探索する、
ことを特徴とするナビゲーション装置。
【請求項６】
請求項３乃至４のいずれか１項に記載のナビゲーション装置であって、
前記経由経路探索手段は、
移動体が前記推奨経路から逸れた地点のリンクから、当該仮想経由地までの経路探索を行う、
ことを特徴とするナビゲーション装置。
【請求項７】
外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置における経路探索方法であって、
前記外部装置から、推奨経路、仮想経由地を受信する受信ステップと、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルートステップと、
前記外部装置から推奨経路を取得できない場合に、前記受信ステップで受信された仮想経由地に至る経路を探索する経由経路探索ステップと、を行う、
ことを特徴とする経路探索方法。
【請求項８】
コンピュータを、外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置として機能させるプログラムであって、
前記外部装置から、推奨経路、仮想経由地を受信する受信ステップと、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルートステップと、
前記外部装置から推奨経路を取得できない場合に、前記受信ステップで受信された仮想経由地に至る経路を探索する経由経路探索ステップと、を前記コンピュータに実行させる、
ことを特徴とするプログラム。
【請求項１】
推奨経路の探索を行う外部装置と、当該外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置と、を備えるナビゲーションシステムであって、
前記ナビゲーション装置は、
前記外部装置に、推奨経路の探索を要求する要求手段を備え、
前記外部装置は、
前記ナビゲーション装置からの要求に基づいて、推奨経路を探索する経路探索手段と、
前記ナビゲーション装置が当該外部装置と通信可能な地点である仮想経由地を設定する仮想経由地設定手段と、
探索された前記推奨経路と、設定された前記仮想経由地と、を前記ナビゲーション装置に提供する提供手段と、を備え、
前記ナビゲーション装置は、
前記外部装置から、前記推奨経路、前記仮想経由地を受信する受信手段と、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、
前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える、
ことを特徴とするナビゲーションシステム。
【請求項２】
請求項１に記載のナビゲーションシステムであって、
前記ナビゲーション装置は、経路誘導手段をさらに備え、
前記経路誘導手段は、
前記外部装置から推奨経路を取得できる場合には、前記受信手段で受信された推奨経路に基づいて経路誘導を行い、
前記外部装置から推奨経路を取得できない場合には、前記経由経路探索手段で探索された経路に基づいて、前記外部装置から推奨経路を取得可能になる位置に移動体が到達するまで前記仮想経由地に向けた経路誘導を行う、
ことを特徴とするナビゲーションシステム。
【請求項３】
外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置であって、
前記外部装置から、推奨経路、仮想経由地を受信する受信手段と、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルート手段と、
前記外部装置から推奨経路を取得できない場合に、前記受信手段で受信された仮想経由地に至る経路を探索する経由経路探索手段と、を備える、
ことを特徴とするナビゲーション装置。
【請求項４】
請求項３に記載のナビゲーション装置であって、
経路誘導手段をさらに備え、
前記経路誘導手段は、
前記外部装置から推奨経路を取得できる場合には、前記受信手段で受信された推奨経路に基づいて経路誘導を行い、
前記外部装置から推奨経路を取得できない場合には、前記経由経路探索手段で探索された経路に基づいて、前記外部装置から推奨経路を取得可能になる位置に移動体が到達するまで前記仮想経由地に向けた経路誘導を行う、
ことを特徴とするナビゲーション装置。
【請求項５】
請求項３又は４に記載のナビゲーション装置であって、
前記経由経路探索手段は、
前記受信手段で複数の仮想経由地が受信された場合には、所定の規則に従って１つの仮想経由地を選択し、選択された当該仮想経由地に至る経路を探索する、
ことを特徴とするナビゲーション装置。
【請求項６】
請求項３乃至４のいずれか１項に記載のナビゲーション装置であって、
前記経由経路探索手段は、
移動体が前記推奨経路から逸れた地点のリンクから、当該仮想経由地までの経路探索を行う、
ことを特徴とするナビゲーション装置。
【請求項７】
外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置における経路探索方法であって、
前記外部装置から、推奨経路、仮想経由地を受信する受信ステップと、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルートステップと、
前記外部装置から推奨経路を取得できない場合に、前記受信ステップで受信された仮想経由地に至る経路を探索する経由経路探索ステップと、を行う、
ことを特徴とする経路探索方法。
【請求項８】
コンピュータを、外部装置から提供された推奨経路を用いて経路誘導を行うナビゲーション装置として機能させるプログラムであって、
前記外部装置から、推奨経路、仮想経由地を受信する受信ステップと、
移動体が前記推奨経路から逸れた場合に、推奨経路の再探索を前記外部装置に要求するリルートステップと、
前記外部装置から推奨経路を取得できない場合に、前記受信ステップで受信された仮想経由地に至る経路を探索する経由経路探索ステップと、を前記コンピュータに実行させる、
ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−２２６９７３（Ｐ２０１１−２２６９７３Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１０−９８６３５（Ｐ２０１０−９８６３５）
【出願日】平成２２年４月２２日（２０１０．４．２２）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２２年４月２２日（２０１０．４．２２）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]