ナビゲーション装置、および経路探索方法
【課題】ナビゲーション装置において、探索される経路の中に未舗装の道路が含まれる可能性を減少させると共に、舗装路から未舗装路に入る経路が探索される可能性を減少させる。
【解決手段】出発地から目的地までの推奨経路を探索するナビゲーション装置にリンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれているリンク情報を記憶する記憶装置３と、リンク情報を用いて、出発地と目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する演算処理部１とを設ける。演算処理部１は、経路探索を行なう際、道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないようにする。
【解決手段】出発地から目的地までの推奨経路を探索するナビゲーション装置にリンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれているリンク情報を記憶する記憶装置３と、リンク情報を用いて、出発地と目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する演算処理部１とを設ける。演算処理部１は、経路探索を行なう際、道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
従来のナビゲーション装置には、舗装路と未舗装路とを識別可能に構成された道路データを保持し、未舗装路のコスト（例えば旅行時間）を高くした上で経路探索を行うものがある（例えば特許文献１）。特許文献１では、このように構成することで、探索される経路の中に未舗装の道路が含まれる可能性を低減させるようにしている。
【０００３】
【特許文献１】特開２０００−７４６８２号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献１の未舗装路にコストをかける方法は、以下の問題を有している。具体的には、特許文献１では、目的地までの経路を構成するリンクのコストを算出し、コストが有利なリンクを選択するようにしている。そのため、例えば、未舗装路にコストをかけても、未舗装路が舗装路よりもコストが有利なこともある。このような場合、未舗装路を含む経路が探索されてしまう。すなわち、特許文献１では、利用者が未舗装の道路を通行したくない場合であっても、利用者を未舗装の道路に誘導してしまうことがある。
【０００５】
また、利用者は、未舗装路から舗装路に抜けた場合、再度、未舗装路に進入したくないと考えることがある。しかしながら、特許文献１では、リンクのコストを利用して経路を選択する方法を採用しているため、舗装路に抜けた場合、再度、未舗装路を含む経路が選択されることがある。なお、未舗装路を初めから経路を構成する道路として選択しないことも考えられる。しかしながら、この方法では、出発地の周辺が未舗装路に囲まれている場合に経路探索をすることができない。
【０００６】
本発明は、上記事情に鑑みてなされたものであり、本発明の目的は、ナビゲーション装置において、探索される経路の中に未舗装路が含まれる可能性を減少させると共に、舗装路から未舗装路に入る経路が探索される可能性を減少させることにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明では、ナビゲーション装置において、経路探索の際、一度、舗装された道路のリンクを選択した場合、それ以降の経路を構成する道路として未舗装のリンクを選択しないようにする。
【０００８】
例えば、本発明の一態様は、地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置に適用される。
【０００９】
そして、前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、前記ナビゲーション装置は、前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する経路探索手段と、を有し、前記経路探索手段は、前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索する。
【発明の効果】
【００１０】
このように本発明によれば、ナビゲーション装置は、経路探索の際に舗装された道路を示すリンクを選択した場合、該舗装された道路を示すリンクに接続するリンクとして、未舗装の道路を示すリンクを選択しないで目的地までの推奨経路を構成するリンクを探索するようにしている。
【００１１】
そのため、本発明によれば、コストが有利な未舗装路がある場合であっても、一度、舗装された道路に入った後には未舗装路を含んだ経路が探索されることがない。
【００１２】
また、本発明は、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないようにしているだけで、未舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択することについて制限を設けていない。すなわち、本発明では、舗装路のリンクが選択されるまでは、未舗装路のリンクが選択されることを制限していない。そのため、現在位置の周辺が未舗装の道路に囲まれている場合であっても、目的地までの経路探索を行うことが可能になる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態について図面を用いて説明する。
【００１４】
最初に本発明の第１実施形態が適用された車載用ナビゲーション装置の概略構成について図１を用いて説明する。
【００１５】
図１は、本発明の第１実施形態が適用された車載用ナビゲーション装置（以下において単に「ナビゲーション装置」という）の概略構成図である。
【００１６】
図示するように、ナビゲーション装置は、演算処理部１と、ディスプレイ２と、地図データ等が記憶された記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロ８と、ＧＰＳ（Global Positioning System）受信装置９とを有する。
【００１７】
演算処理部１は、ナビゲーション装置が利用者に提供する各種情報を処理するための中心的ユニットである。例えば、各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在位置を検出する。演算処理部１は、検出した現在位置の周辺の地図データを記憶装置３から読み出して、その読み出した地図データをグラフィックス展開し、そこに現在位置を示すマークを重ねてディスプレイ２に表示する。また、演算処理部１は、現在位置と利用者から指示された目的地とを結ぶ推奨経路を探索し、音声入出力装置４やディスプレイ２を用いて利用者を誘導する。なお、後述するが本実施形態の演算処理部１は、推奨経路を探索する際に舗装された道路を示すリンクを選択した後は、未舗装の道路を示すリンクを選択しないで目的地までの推奨経路を探索する。
【００１８】
ディスプレイ２は、演算処理部１で生成された画像データを表示するユニットで、ＣＲＴや液晶ディスプレイ等により構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National TV Standards Committee）信号で接続するのが一般的である。
【００１９】
記憶装置３は、日本列島の全体図から全国各市町村の詳細図まで多段階の縮尺図に対応した地図データ等のデータを記憶するユニットである。なお、記憶装置３には、例えば、ＤＶＤ装置やハードディスク装置を用いることができる。
【００２０】
ここで地図データの構成を説明する。
【００２１】
図２は、本発明の実施形態の記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【００２２】
図示するように、地図データ３１０は、地図を複数に分割することで得られるメッシュ領域毎に分類されている。地図データ３１０は、メッシュ領域を識別するためのメッシュＩＤ３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。
【００２３】
リンクデータ３１２は、リンクを識別するためのリンクＩＤ３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクが属する道路が「有料道路」であるか「一般道路」であるかを示す道路種別３１２３、リンクが示す道路が「舗装された道路（舗装路という）」であるか、或いは「未舗装の道路（未舗装路という）」であるかを示すリンク種別３１２４、リンクの長さを示すリンク長情報３１２５、リンクの旅行時間（或いは移動時間）情報３１２６、および２つのノード（開始ノード、終了ノード）にそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２７などを有する。
【００２４】
なお、記憶装置３には、上述の地図データの他に、座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定するためのテーブル（変換テーブルと呼ぶこととする）が記憶されている。
【００２５】
図１に戻り、説明を続ける。音声入出力装置４は、演算処理部１で生成した利用者へのメッセージを音声信号に変換して出力すると共に、利用者が発した声を認識し、認識した内容を演算処理部１に転送する。
【００２６】
入力装置５は、ナビゲーション装置の各種機能選択、目的地設定等の利用者からの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイステック、ディスプレイ２上に貼られたタッチパネルなどで構成される。
【００２７】
センサ６〜８およびＧＰＳ受信装置９は、ナビゲーション装置が現在位置を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数から距離を測定し、さらに対となる車輪の回転数から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁気を検知し、移動体が向かっている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロで構成され、移動体が回転した角度を検出する。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＳＰ衛星間の距離および距離の変化率を３個以上の衛星に対して測定することで移動体の現在位置、進行方向および進行方位を測定する。
【００２８】
続いて、上述したナビゲーション装置の演算処理部１が有する機能について図３を用いて説明する。
【００２９】
図３は、本発明の第１実施形態の演算処理部１の機能構成を説明するための図である。
【００３０】
図示するように、演算処理部１は、設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７を有する。
【００３１】
設定部１０は、入力装置５或いは音声入出力装置４に入力された利用者からの要求を受け付け、その要求された内容に対応する処理が実行されるように演算処理部１を制御する。例えば、利用者が、入力装置５を介して目的地に向うための推奨経路の探索を要求した場合、現在位置から目的地までの推奨経路を探索する処理を経路探索部１４に要求する。
【００３２】
現在位置検出部１１は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロセンサ８で計測される角速度データＳ７を各々積分した結果得られる距離データおよび角度データを用いて、そのデータを時間軸で積分していくことにより、初期値（Ｘ,Ｙ）から自車走行後の位置である現在位置（Ｘ´,Ｙ´）を定期的に演算する。現在位置検出部１１は、上記算出した現在位置を地図表示処理部１６に出力すると共に、上記算出した現在位置を所定の算出回数毎にマップマッチ処理部１３に出力する。また、現在位置検出部１１は、後述するマップマッチ処理部１３から現在位置の補正データを取得した場合、その現在位置の補正データを地図表示処理部１６に出力する。さらに、現在位置検出部１１は、経路誘導部１５からの現在位置を要求された場合、経路誘導部１５に現在位置（或いは現在位置の補正データ）を出力する。
【００３３】
ここで、現在位置検出部１１は、自車の回転した角度と進む方向との関係を一致させるため、地磁気センサ７から得られた方位データＳ６と、ジャイロ８から得られ角速度データＳ７を積分した角度データを参照して、自車が進行している方向の絶対方位を推定する。現在位置検出部１１は、車輪速センサ６のデータＳ５およびジャイロ８のデータＳ７を各々積分していくと、誤差が蓄積するため、ある時間でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルする処理を施し、現在位置のデータを求める。
【００３４】
データ読込部１２は、ディスプレイ２に表示が要求される領域や、経路探索のために要求される領域（現在位置および目的地を含む）にある地図データ３１を記憶装置３から読み込む。
【００３５】
マップマッチ処理部１３は、データ読込部１２が読み込んだ現在位置周辺の地図データと、現在位置検出部１１が定期的に検出する現在位置を合わせ込むマップマッチ処理を行う。マップマッチ処理部１３は、定期的に現在位置を補正し、補正した現在位置を示すデータを現在位置検出部１１に出力する。
【００３６】
経路探索部１４は、ダイクストラ法等を用いて、指定された２地点（現在位置、目的地）を結ぶ最適なコストで目的地に到達する経路をリンクデータ３１２（図２参照）を用いて探索する。本実施形態の経路探索部１４は、後述するが経路探索を行う際、道路が舗装されているか否かを考慮する。そして、経路探索部１４は、舗装されている道路から未舗装の道路に入る経路が探索されないようにする。なお、経路探索部１４が行う処理については、後段で詳細に説明する。
【００３７】
経路探索部１４は、探索の結果得られた経路を推奨経路として、ディスプレイ２に表示させるために地図表示処理部１６に推奨経路を示すデータを出力する。また、経路探索部１４は、探索された推奨経路を示すデータを経路誘導部１５に出力する。
【００３８】
経路誘導部１５は、探索された推奨経路を通って目的地に到達するように利用者を誘導する。具体的には、経路誘導部１５は、自車位置検出部１１から定期的に現在位置を取得する。そして、経路誘導部１５は、取得した現在位置と、経路探索部１４から取得した推奨経路を示すデータと、データ読込部１２を介して記憶装置３から読込んだ地図データとを用いて利用者を目的地まで誘導する。
【００３９】
地図表示処理部１６は、ディスプレイ２に表示が要求される領域にある地図データ３１０を記憶装置３からデータ読込部１２を介して受け取る。地図表示処理部１６は、経路探索部１４から探索した推奨経路を受け取り、現在位置検出部１１から現在位置の情報を受け取る。そして、地図表示処理部１６は、道路、その他の地図構成物、現在位置、目的地、および経路誘導のための矢印といったマーク等をディスプレイ２の画面に描画させるための地図描画コマンドを生成し、グラフィックス処理部１７に出力する。
【００４０】
グラフィックス処理部１７は、地図表示処理部１６で生成された地図描画コマンドを用いてディスプレイ２の画面上に画像データを表示させる。
【００４１】
続いて、本実施形態の演算処理部１のハードウェア構成を説明する。
【００４２】
図４は、演算処理部１のハードウェア構成を示す図である。
【００４３】
図示するように、演算処理部１は、ＣＰＵ（中央演算処理装置）２１と、ＣＰＵ２１が実行するプログラムやデータを一時的に記憶するＲＡＭ（Random Access Memory）２２と、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７）が有する機能を実行するためのプログラムが予め記憶されているＲＯＭ（Read Only Memory）２３と、メモリ間およびメモリと各デバイスとの間のデータを転送するＤＭＡ（Direct Memory Access）２４と、グラフィック描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ（Video Random Access Memory）２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣI(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上に載せるＰＩＯ（Parallel Input/Output）３０と、パルス信号を積分するカウンタ３１と、を有する。そして、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７）の機能は、ＣＰＵ２１が、ＲＯＭ２３に記憶されている上記各部が有する機能を実行するためのプログラをＲＡＭ２２にロードし、実行することにより実現される。
【００４４】
続いて、本実施形態のナビゲーション装置の経路探索部１４が行う経路探索処理を説明する。
【００４５】
最初に経路探索処理の概略を図５を用いて説明する。
【００４６】
図５は、本実施形態のナビゲーション装置が行なう経路探索の処理のフローを説明するための図である。
【００４７】
先ず、経路探索部１４は、設定部１０を介して利用者からの目的地の入力を受付ける（Ｓ１００）。また、本ステップでは、経路探索部１４は、現在位置検出部１１を介して車両の現在位置を取得する。なお、以下の説明では、車両の現在位置を出発地とする場合を例にするが、特にこれに限定しない。経路探索部１４は、設定部１０を介して利用者からの出発地の入力を受付けるようにしてもよい。
【００４８】
続いて、経路探索部１４は、データ読込部１２を介して、推奨経路の探索に必要なリンクデータ３１２を記憶装置３から読み込み（Ｓ１０１）、Ｓ１０２の処理に進む。具体的には、経路探索部１４は、記憶装置３から変換テーブルを読出し、現在位置および目的地を示す座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定する。次に、経路探索部１４は、データ読込部１２を介して記憶装置３より、特定したメッシュＩＤを持つ地図データ各々に登録されている各リンクデータ３１２を入手する。
【００４９】
Ｓ１０２では、Ｓ１０１で読み込んだリンクデータ３１２を用いて、後述するＳ１０６でヒープテーブルから抽出されたリンク（進入リンクという）の終了ノードを開始ノードとするリンクを、推奨経路を構成するリンクの候補のリンク（脱出リンクとよぶ）として選出する。なお、進入リンクの終了ノードを開始ノードとするリンクが複数ある場合には、複数の脱出リンクが選出されることとなる。なお、Ｓ１０６での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出された進入リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、現在位置（または出発地）が存在あるいは現在位置に近接する少なくとも１つのリンクを、脱出リンクとして選出する。
【００５０】
ここで、ヒープテーブルとは、候補のリンクのリンクデータを、出発地から当該候補のリンクの終了ノードまでの総コスト（例えば旅行時間）と共に登録するためのテーブルであり、メモリ等の記憶装置に記憶される。
【００５１】
続いて、経路探索部１４は、選出した脱出リンクの舗装・未舗装判定処理を行い（Ｓ１０３）、Ｓ１０４の処理に進む。舗装・未舗装判定処理とは、Ｓ１０２で選出した脱出リンクを採用するか否かを判定する処理のことをいう。なお、舗装・未舗装判定処理は、後述する図６および図７で説明する。
【００５２】
Ｓ１０４では、経路探索部１４は、Ｓ１０３で採用された脱出リンク各々の総コスト（出発地から脱出リンクの終了ノードまでの総コスト）を算出する。具体的には、Ｓ１０１で読み出した各リンクデータ３１２を用いて、ヒープテーブルに登録されているリンクの総コストに、Ｓ１０３で採用された脱出リンクのコストを加算し、その加算結果を当該脱出リンクの総コストとする。ただし、ヒープテーブルにリンクが登録されていない初期段階では、Ｓ１０３で採用され脱出リンクのコストを当該脱出リンクの総コストとする。それから、経路探索部１４は、候補リンク各々のリンクデータおよび総コストをヒープテーブルに追加する。
【００５３】
次に、経路探索部１４は、直前に行ったＳ１０４にてヒープテーブルに新たに追加されたリンクの中に、目的地が存在あるいは目的地に近接するリンク（目的地リンクと呼ぶ）があるか否かを調べる（Ｓ１０５）。経路探索部１４は、Ｓ１０５において目的地リンクがないと判断したならば、Ｓ１０６の処理に進み、目的地リンクがあると判断した場合には、Ｓ１０７の処理に進む。
【００５４】
Ｓ１０６では、経路探索部４３は、ヒープテーブルに登録されているリンクの情報を総コストの小さい順にソートし、最初に位置するリンクを抽出するなどして、ヒープテーブルから総コストが最小のリンクを抽出する。それから、Ｓ１００２に戻る。
【００５５】
続いて、Ｓ１０５において目的地リンクがあると判断した場合に進むＳ１０７の処理について説明する。Ｓ１０７では、経路探索部１４は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクを発生させたリンク（目的地リンクの開始ノードを終了ノードとするリンクと呼ぶ）を検索し、検出したリンクを推奨経路を構成するリンク（構成リンクと呼ぶ）に決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接するリンク（出発地リンクと呼ぶ）であるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンクを検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。経路探索部１４は、推奨経路を決定したら処理を終了する。
【００５６】
続いて、上記の図５のＳ１０３の舗装・未舗装判定処理について図６および図７を用いて説明する。
【００５７】
図６は、本実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。図７は、進入リンクと脱出リンクとの関係を説明するための図である。なお、以下の説明では、図７に示すように、上述のＳ１０３で進入リンク５２に対し脱出リンク５３および５４が抽出されている場合を例に説明する。
【００５８】
先ず、経路探索部１４は、図５のＳ１０２で抽出した脱出リンクの中から一の脱出リンクを特定し（Ｓ２００）、Ｓ２０１の処理に進む。なお、ここでは、経路探索部１４が脱出リンク５３を特定したこととする。
【００５９】
Ｓ２０１では、経路探索部１４は、リンクデータ３１２から脱出リンクのリンク種別３１２４を取得し、Ｓ２０２の処理に進む。
【００６０】
Ｓ２０２では、経路探索部１４は、取得したリンク種別３１２４を用いて特定した脱出リンクが舗装路であるか否かの判定を行う。そして、経路判定部１４は、脱出リンクが舗装路であると判定した場合にはＳ２０３の処理に進み、脱出リンクが未舗装路であると判定した場合にはＳ２１０の処理に進む。
【００６１】
Ｓ２１０では、経路探索部１４は、進入リンク５２のリンク種別３１２４を取得し、Ｓ２１１の処理に進む。
【００６２】
Ｓ２１１では、経路探索部１４は、取得したリンク種別３１２４を用いて進入リンクが未舗装路であるか否かの判定を行う。そして、経路判定部１４は、進入リンクが未舗装路であると判定した場合にはＳ２０３の処理に進み、進入リンクが未舗装路ではないと判定した場合にはＳ２１２の処理に進む。
【００６３】
Ｓ２１２では、Ｓ２００で特定した脱出リンクを推奨経路を構成するリンクとして採用しないこととし、Ｓ２１３の処理に進む。
【００６４】
続いて、Ｓ２０２において特定した脱出リンクが舗装路であると判定した場合、および、Ｓ２１１において進入リンクが未舗装であると判定した場合に進むＳ２０３の処理を説明する。Ｓ２０３では、経路探索部１４は、Ｓ２００で特定した脱出リンクを、推奨経路を構成するリンクとして採用する。
【００６５】
その後、経路探索部１４は、図５のＳ１０２で抽出した全ての脱出リンクについて上述の判定処理（Ｓ２００〜Ｓ２１２）を行なったか否かを判定し、全ての脱出リンクを判定した場合に処理を終了する。一方、経路探索部１４は、Ｓ１０２で抽出した全ての脱出リンクについての判定を行なっていない場合、Ｓ２００の処理に戻る（Ｓ２１３）。図７の例では、脱出リンク５３および脱出リンク５４の両者について、推奨経路を構成するリンクとして採用するか否かを判定した場合に処理を終了する。
【００６６】
ここで、図６の処理を具体例を挙げて説明する。例えば、図７に示す例において、脱出リンク５３が未舗装路で、進入リンク５２が未舗装路であったとする。この場合、経路探索部１４は、Ｓ２０２、Ｓ２１０、およびＳ２１１の処理を実行した後、Ｓ２０３の処理に進み、脱出リンク５３を、推奨経路を構成するリンクとして採用する。また、例えば、脱出リンク５３が未舗装路で、進入リンク５２が舗装路であったとする。この場合、経路探索部１４は、Ｓ２０２、Ｓ２１０、およびＳ２１１の処理を実行した後、Ｓ２１２の処理に進み、脱出リンク５３を、推奨経路を構成するリンクとして採用しない。
【００６７】
このように、本実施形態の経路探索部１４は、経路探索処理において、推奨経路を構成するリンクとして舗装路を採用した場合、その舗装路に接続するリンクに未舗装路を採用しない。そのため、一度、舗装路のリンクが選択された場合、そのリンクに続く経路として、未舗装路が探索されることがない。また、本実施形態では、経路探索において、舗装路のリンクが選択されるまでは、未舗装のリンクの選択を認めるようにしている。これは、未舗装路のリンクを全て選択できないようにした場合に経路探索ができなくなることを考慮したためである。
【００６８】
続いて、本発明の第２実施形態について説明する。
【００６９】
第２実施形態は、上記第１実施形態のナビゲーション装置が有する経路探索部１４を変形したものである。具体的には、第２実施形態の経路探索部１４は、第１実施形態の経路探索部１４の機能に加え、さらに所定要件下において舗装路から未舗装路に入る経路を選択する機能を付加したものである。なお、第２実施形態は、第１実施形態と経路探索部１４の機能が異なる以外は同様の構成を有している。第２実施形態の説明において、第１実施形態と同じ構成については同じ符号を用いることとする。また、第２実施形態の説明では、第１実施形態と異なる
部分を中心に説明する。
【００７０】
第２実施形態の経路探索処理を、上述した図５を用いて説明する。
【００７１】
さて、第２実施形態の経路探索部１４は、図５に示す各処理ステップを行い、目的地までの推奨経路を探索する。具体的には、第２実施形態の経路探索部１４は、第１実施形態と同様の手順にしたがい、Ｓ１００〜１０３の処理を行なう。そして、Ｓ１０３で脱出リンクを１以上採用できた場合、Ｓ１０４では上述した第１実施形態と同様の処理を行なう。一方、Ｓ１０３で脱出リンクを１つも採用できない場合、経路探索部１４は、Ｓ１０４において、脱出リンクを採用できない進入リンクを特定するデータを保持する。例えば、経路探索部１４は、ヒープテーブルに登録されている、脱出リンクを採用できない「進入リンク」にフラグを対応付けて登録する。なお、以下では、フラグを対応付けて登録する場合を例にする。続いて、経路探索部１４は、上述したＳ１０５の処理を行なう。
【００７２】
Ｓ１０５の処理によりＳ１０６に進んだ場合、経路探索部１４は、ヒープテーブルからリンクを抽出する際、フラグに対応付けられているリンク以外のリンクを抽出し、Ｓ１０２の処理に戻る。なお、Ｓ１０６において、フラグに対応付けられているリンク以外のリンクを抽出した場合に行なうＳ１０２〜１０５は、上記と同様である。
【００７３】
ここで、Ｓ１０６において、抽出できるリンクがない場合（すなわち、目的地までの経路探索ができない場合）がある。この場合、経路探索部１４は、ヒープテーブルに登録されたフラグを消去した上で、リンクの抽出を行い、Ｓ１０２〜Ｓ１０３の処理に進む。なお、Ｓ１０６において、ヒープテーブルに登録されたフラグを消去した上でリンクの抽出を行なった場合、経路探索部１４は、Ｓ１０３で行う舗装・未舗装判定処理を、図６に示す処理から図８に示す処理に変更する。
【００７４】
ここで、目的地までの経路探索ができない場合の例を図９に示す。図９は、目的地が未舗装路のリンクにだけ接続している場合を例示した図である。図９では、目的地７０に到達するために未舗装路のリンク６３および未舗装路のリンク６４のいずれかを通過する必要がある場合を示している。また、未舗装路のリンク６３および未舗装路のリンク６４には、それぞれ、舗装路のリンク６２および舗装路のリンク６５が接続されている。図示する例において、経路探索部１４が図６に示す舗装・未舗装判定処理を行なったとする。この場合、リンク６２を経由する場合に脱出リンクとしてリンク６３は採用されない。同様に、リンク６５を経由する場合に脱出リンクとしてリンク６４は採用されない。図６の舗装・未舗装判定処理では、舗装路のリンクから未舗装路のリンクに入る経路は選択されないためである。その結果、目的地までの経路が探索できないこととなる。そのため、第２実施形態では、目的地までの経路を探索できない場合において、舗装路のリンクから未舗装のリンクを選択する処理を行なうようにしている。以下、目的地までの経路を探索できない場合に行なう経路探索のリトライ処理を説明する。
【００７５】
図８は、第２実施形態のナビゲーション装置が行なう舗装・未舗装判定処理のフローチャートである。
【００７６】
先ず、経路探索部１４は、図５のＳ１０２で抽出された脱出リンクを特定する処理を行なう。具体的には、図６のＳ２００と同様の手順により脱出リンクを特定する（Ｓ３００）。
【００７７】
次に、経路探索部１４は、リンクデータ３１２を用いて進入リンクの種別を特定し、進入リンクが舗装路であるか否かの判定を行う（Ｓ３０１〜３０２）。判定の結果、進入リンクが舗装路である場合にＳ３０３に進み、進入リンクが舗装路でない場合にＳ３１０に進む。
【００７８】
Ｓ３１０では、経路探索部１４は、リンクデータ３１２を用いて脱出リンクの種別を取得する。経路探索部１４は、脱出リンクが舗装路であるか否かの判定を行い、脱出リンクが舗装路であると判定した場合にＳ３１２に進み、脱出リンクが舗装路ではないと判定した場合にＳ３０３に進む。Ｓ３１２では、経路探索部１４は、脱出リンクを、推奨経路を構成するリンクとして採用しないことに決定して、Ｓ３１３の処理に進む（Ｓ３１２）。
【００７９】
続いて、Ｓ３０２において進入リンクが舗装路であると判定した場合、および、Ｓ３１１において脱出リンクが舗装路ではないと判定した場合に進むＳ３０３の処理を説明する。Ｓ３０３では、経路探索部１４は、Ｓ３００で特定した脱出リンクを、推奨経路を構成するリンクとして採用する。
【００８０】
その後、経路探索部１４は、図５のＳ１０２で抽出した全ての脱出リンクについて上述の判定処理（Ｓ３００〜Ｓ３１２）を行なったか否かを判定し、全ての脱出リンクを判定した場合に処理を終了する。一方、経路探索部１４は、Ｓ１０２で抽出した全ての脱出リンクについての判定を行なっていな場合、Ｓ３００の処理に戻る（Ｓ３１３）。
【００８１】
このように第２実施形態によれば、第１実施形態と同様に目的地までの経路に未舗装路が含まれる可能性を低下させることができる。また、第２実施形態によれば、目的地に未舗装路を経由しないと到達しない場合に舗装路から未舗装路に入るリンクを採用するようにしている。そのため、第１実施形態と同様の手順に従い経路探索を行った結果、目的地までの経路を探索できない場合であっても、上述した図８の処理を行なうことにより経路を探索することが可能となる。
【００８２】
なお、本発明は以上で説明した実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形が可能である。例えば、第１実施形態のナビゲーション装置が未舗装路を経由しないと到達しない目的地への経路探索を行った場合、探索できたリンクまでの経路を保持する。そして、経路探索部１４は、探索できた経路から以降については、舗装路・未舗装路に関係なく目的地に至るまでの経路を探索するようにしてもよい。
【図面の簡単な説明】
【００８３】
【図１】本発明の実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【図２】本発明の実施形態の記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【図３】本発明の実施形態の演算処理部１の機能構成を説明するための図である。
【図４】本発明の実施形態の演算処理部１のハードウェア構成を示す図である。
【図５】本発明の実施形態のナビゲーション装置が行なう経路探索の処理のフローを説明するための図である。
【図６】本発明の実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。
【図７】進入リンクと脱出リンクとの関係を説明するための図である。
【図８】第２実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。
【図９】目的地が未舗装路のリンクにだけ接続している場合を例示した図である。
【符号の説明】
【００８４】
１…演算処理部、２…ディスプレイ、３…記憶装置、４…音声入出力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信装置、１０…設定部、１１…現在位置検出部、１２…データ読込部、１３…マップマッチ処理部、１４…経路探索部、１５…経路誘導部、１６…地図表示処理部、１７…グラフィックス処理部、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ
【技術分野】
【０００１】
本発明は、ナビゲーション装置に関し、特に車載用ナビゲーション装置の経路探索技術に関する。
【背景技術】
【０００２】
従来のナビゲーション装置には、舗装路と未舗装路とを識別可能に構成された道路データを保持し、未舗装路のコスト（例えば旅行時間）を高くした上で経路探索を行うものがある（例えば特許文献１）。特許文献１では、このように構成することで、探索される経路の中に未舗装の道路が含まれる可能性を低減させるようにしている。
【０００３】
【特許文献１】特開２０００−７４６８２号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献１の未舗装路にコストをかける方法は、以下の問題を有している。具体的には、特許文献１では、目的地までの経路を構成するリンクのコストを算出し、コストが有利なリンクを選択するようにしている。そのため、例えば、未舗装路にコストをかけても、未舗装路が舗装路よりもコストが有利なこともある。このような場合、未舗装路を含む経路が探索されてしまう。すなわち、特許文献１では、利用者が未舗装の道路を通行したくない場合であっても、利用者を未舗装の道路に誘導してしまうことがある。
【０００５】
また、利用者は、未舗装路から舗装路に抜けた場合、再度、未舗装路に進入したくないと考えることがある。しかしながら、特許文献１では、リンクのコストを利用して経路を選択する方法を採用しているため、舗装路に抜けた場合、再度、未舗装路を含む経路が選択されることがある。なお、未舗装路を初めから経路を構成する道路として選択しないことも考えられる。しかしながら、この方法では、出発地の周辺が未舗装路に囲まれている場合に経路探索をすることができない。
【０００６】
本発明は、上記事情に鑑みてなされたものであり、本発明の目的は、ナビゲーション装置において、探索される経路の中に未舗装路が含まれる可能性を減少させると共に、舗装路から未舗装路に入る経路が探索される可能性を減少させることにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明では、ナビゲーション装置において、経路探索の際、一度、舗装された道路のリンクを選択した場合、それ以降の経路を構成する道路として未舗装のリンクを選択しないようにする。
【０００８】
例えば、本発明の一態様は、地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置に適用される。
【０００９】
そして、前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、前記ナビゲーション装置は、前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する経路探索手段と、を有し、前記経路探索手段は、前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索する。
【発明の効果】
【００１０】
このように本発明によれば、ナビゲーション装置は、経路探索の際に舗装された道路を示すリンクを選択した場合、該舗装された道路を示すリンクに接続するリンクとして、未舗装の道路を示すリンクを選択しないで目的地までの推奨経路を構成するリンクを探索するようにしている。
【００１１】
そのため、本発明によれば、コストが有利な未舗装路がある場合であっても、一度、舗装された道路に入った後には未舗装路を含んだ経路が探索されることがない。
【００１２】
また、本発明は、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないようにしているだけで、未舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択することについて制限を設けていない。すなわち、本発明では、舗装路のリンクが選択されるまでは、未舗装路のリンクが選択されることを制限していない。そのため、現在位置の周辺が未舗装の道路に囲まれている場合であっても、目的地までの経路探索を行うことが可能になる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態について図面を用いて説明する。
【００１４】
最初に本発明の第１実施形態が適用された車載用ナビゲーション装置の概略構成について図１を用いて説明する。
【００１５】
図１は、本発明の第１実施形態が適用された車載用ナビゲーション装置（以下において単に「ナビゲーション装置」という）の概略構成図である。
【００１６】
図示するように、ナビゲーション装置は、演算処理部１と、ディスプレイ２と、地図データ等が記憶された記憶装置３と、音声入出力装置４と、入力装置５と、車輪速センサ６と、地磁気センサ７と、ジャイロ８と、ＧＰＳ（Global Positioning System）受信装置９とを有する。
【００１７】
演算処理部１は、ナビゲーション装置が利用者に提供する各種情報を処理するための中心的ユニットである。例えば、各種センサ６〜８やＧＰＳ受信装置９から出力される情報を基にして現在位置を検出する。演算処理部１は、検出した現在位置の周辺の地図データを記憶装置３から読み出して、その読み出した地図データをグラフィックス展開し、そこに現在位置を示すマークを重ねてディスプレイ２に表示する。また、演算処理部１は、現在位置と利用者から指示された目的地とを結ぶ推奨経路を探索し、音声入出力装置４やディスプレイ２を用いて利用者を誘導する。なお、後述するが本実施形態の演算処理部１は、推奨経路を探索する際に舗装された道路を示すリンクを選択した後は、未舗装の道路を示すリンクを選択しないで目的地までの推奨経路を探索する。
【００１８】
ディスプレイ２は、演算処理部１で生成された画像データを表示するユニットで、ＣＲＴや液晶ディスプレイ等により構成される。また、演算処理部１とディスプレイ２との間の信号Ｓ１は、ＲＧＢ信号やＮＴＳＣ（National TV Standards Committee）信号で接続するのが一般的である。
【００１９】
記憶装置３は、日本列島の全体図から全国各市町村の詳細図まで多段階の縮尺図に対応した地図データ等のデータを記憶するユニットである。なお、記憶装置３には、例えば、ＤＶＤ装置やハードディスク装置を用いることができる。
【００２０】
ここで地図データの構成を説明する。
【００２１】
図２は、本発明の実施形態の記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【００２２】
図示するように、地図データ３１０は、地図を複数に分割することで得られるメッシュ領域毎に分類されている。地図データ３１０は、メッシュ領域を識別するためのメッシュＩＤ３１１、および、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ３１２を有する。
【００２３】
リンクデータ３１２は、リンクを識別するためのリンクＩＤ３１２１、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報３１２２、リンクが属する道路が「有料道路」であるか「一般道路」であるかを示す道路種別３１２３、リンクが示す道路が「舗装された道路（舗装路という）」であるか、或いは「未舗装の道路（未舗装路という）」であるかを示すリンク種別３１２４、リンクの長さを示すリンク長情報３１２５、リンクの旅行時間（或いは移動時間）情報３１２６、および２つのノード（開始ノード、終了ノード）にそれぞれ接続するリンクのリンクＩＤ（接続リンクＩＤ）３１２７などを有する。
【００２４】
なお、記憶装置３には、上述の地図データの他に、座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定するためのテーブル（変換テーブルと呼ぶこととする）が記憶されている。
【００２５】
図１に戻り、説明を続ける。音声入出力装置４は、演算処理部１で生成した利用者へのメッセージを音声信号に変換して出力すると共に、利用者が発した声を認識し、認識した内容を演算処理部１に転送する。
【００２６】
入力装置５は、ナビゲーション装置の各種機能選択、目的地設定等の利用者からの指示を受け付けるユニットで、スクロールキー、縮尺変更キーなどのハードスイッチ、ジョイステック、ディスプレイ２上に貼られたタッチパネルなどで構成される。
【００２７】
センサ６〜８およびＧＰＳ受信装置９は、ナビゲーション装置が現在位置を検出するために使用するものである。車輪速センサ６は、車輪の円周と計測される車輪の回転数から距離を測定し、さらに対となる車輪の回転数から移動体が曲がった角度を計測する。地磁気センサ７は、地球が保持している磁気を検知し、移動体が向かっている方角を検出する。ジャイロ８は、光ファイバジャイロや振動ジャイロで構成され、移動体が回転した角度を検出する。ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＳＰ衛星間の距離および距離の変化率を３個以上の衛星に対して測定することで移動体の現在位置、進行方向および進行方位を測定する。
【００２８】
続いて、上述したナビゲーション装置の演算処理部１が有する機能について図３を用いて説明する。
【００２９】
図３は、本発明の第１実施形態の演算処理部１の機能構成を説明するための図である。
【００３０】
図示するように、演算処理部１は、設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７を有する。
【００３１】
設定部１０は、入力装置５或いは音声入出力装置４に入力された利用者からの要求を受け付け、その要求された内容に対応する処理が実行されるように演算処理部１を制御する。例えば、利用者が、入力装置５を介して目的地に向うための推奨経路の探索を要求した場合、現在位置から目的地までの推奨経路を探索する処理を経路探索部１４に要求する。
【００３２】
現在位置検出部１１は、車輪速センサ６で計測される距離パルスデータＳ５およびジャイロセンサ８で計測される角速度データＳ７を各々積分した結果得られる距離データおよび角度データを用いて、そのデータを時間軸で積分していくことにより、初期値（Ｘ,Ｙ）から自車走行後の位置である現在位置（Ｘ´,Ｙ´）を定期的に演算する。現在位置検出部１１は、上記算出した現在位置を地図表示処理部１６に出力すると共に、上記算出した現在位置を所定の算出回数毎にマップマッチ処理部１３に出力する。また、現在位置検出部１１は、後述するマップマッチ処理部１３から現在位置の補正データを取得した場合、その現在位置の補正データを地図表示処理部１６に出力する。さらに、現在位置検出部１１は、経路誘導部１５からの現在位置を要求された場合、経路誘導部１５に現在位置（或いは現在位置の補正データ）を出力する。
【００３３】
ここで、現在位置検出部１１は、自車の回転した角度と進む方向との関係を一致させるため、地磁気センサ７から得られた方位データＳ６と、ジャイロ８から得られ角速度データＳ７を積分した角度データを参照して、自車が進行している方向の絶対方位を推定する。現在位置検出部１１は、車輪速センサ６のデータＳ５およびジャイロ８のデータＳ７を各々積分していくと、誤差が蓄積するため、ある時間でＧＰＳ受信装置９から得られた位置データＳ８をもとに蓄積した誤差をキャンセルする処理を施し、現在位置のデータを求める。
【００３４】
データ読込部１２は、ディスプレイ２に表示が要求される領域や、経路探索のために要求される領域（現在位置および目的地を含む）にある地図データ３１を記憶装置３から読み込む。
【００３５】
マップマッチ処理部１３は、データ読込部１２が読み込んだ現在位置周辺の地図データと、現在位置検出部１１が定期的に検出する現在位置を合わせ込むマップマッチ処理を行う。マップマッチ処理部１３は、定期的に現在位置を補正し、補正した現在位置を示すデータを現在位置検出部１１に出力する。
【００３６】
経路探索部１４は、ダイクストラ法等を用いて、指定された２地点（現在位置、目的地）を結ぶ最適なコストで目的地に到達する経路をリンクデータ３１２（図２参照）を用いて探索する。本実施形態の経路探索部１４は、後述するが経路探索を行う際、道路が舗装されているか否かを考慮する。そして、経路探索部１４は、舗装されている道路から未舗装の道路に入る経路が探索されないようにする。なお、経路探索部１４が行う処理については、後段で詳細に説明する。
【００３７】
経路探索部１４は、探索の結果得られた経路を推奨経路として、ディスプレイ２に表示させるために地図表示処理部１６に推奨経路を示すデータを出力する。また、経路探索部１４は、探索された推奨経路を示すデータを経路誘導部１５に出力する。
【００３８】
経路誘導部１５は、探索された推奨経路を通って目的地に到達するように利用者を誘導する。具体的には、経路誘導部１５は、自車位置検出部１１から定期的に現在位置を取得する。そして、経路誘導部１５は、取得した現在位置と、経路探索部１４から取得した推奨経路を示すデータと、データ読込部１２を介して記憶装置３から読込んだ地図データとを用いて利用者を目的地まで誘導する。
【００３９】
地図表示処理部１６は、ディスプレイ２に表示が要求される領域にある地図データ３１０を記憶装置３からデータ読込部１２を介して受け取る。地図表示処理部１６は、経路探索部１４から探索した推奨経路を受け取り、現在位置検出部１１から現在位置の情報を受け取る。そして、地図表示処理部１６は、道路、その他の地図構成物、現在位置、目的地、および経路誘導のための矢印といったマーク等をディスプレイ２の画面に描画させるための地図描画コマンドを生成し、グラフィックス処理部１７に出力する。
【００４０】
グラフィックス処理部１７は、地図表示処理部１６で生成された地図描画コマンドを用いてディスプレイ２の画面上に画像データを表示させる。
【００４１】
続いて、本実施形態の演算処理部１のハードウェア構成を説明する。
【００４２】
図４は、演算処理部１のハードウェア構成を示す図である。
【００４３】
図示するように、演算処理部１は、ＣＰＵ（中央演算処理装置）２１と、ＣＰＵ２１が実行するプログラムやデータを一時的に記憶するＲＡＭ（Random Access Memory）２２と、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７）が有する機能を実行するためのプログラムが予め記憶されているＲＯＭ（Read Only Memory）２３と、メモリ間およびメモリと各デバイスとの間のデータを転送するＤＭＡ（Direct Memory Access）２４と、グラフィック描画を実行し且つ表示制御を行う描画コントローラ２５と、グラフィックスイメージデータを蓄えるＶＲＡＭ（Video Random Access Memory）２６と、イメージデータをＲＧＢ信号に変換するカラーパレット２７と、アナログ信号をデジタル信号に変換するＡ/Ｄ変換器２８と、シリアル信号をバスに同期したパラレル信号に変換するＳＣI(Serial Communication Interface)２９と、パラレル信号をバスに同期させてバス上に載せるＰＩＯ（Parallel Input/Output）３０と、パルス信号を積分するカウンタ３１と、を有する。そして、上記各部（設定部１０、現在位置検出部１１、データ読込部１２、マップマッチ処理部１３、経路探索部１４、経路誘導部１５、地図表示処理部１６、およびグラフィックス処理部１７）の機能は、ＣＰＵ２１が、ＲＯＭ２３に記憶されている上記各部が有する機能を実行するためのプログラをＲＡＭ２２にロードし、実行することにより実現される。
【００４４】
続いて、本実施形態のナビゲーション装置の経路探索部１４が行う経路探索処理を説明する。
【００４５】
最初に経路探索処理の概略を図５を用いて説明する。
【００４６】
図５は、本実施形態のナビゲーション装置が行なう経路探索の処理のフローを説明するための図である。
【００４７】
先ず、経路探索部１４は、設定部１０を介して利用者からの目的地の入力を受付ける（Ｓ１００）。また、本ステップでは、経路探索部１４は、現在位置検出部１１を介して車両の現在位置を取得する。なお、以下の説明では、車両の現在位置を出発地とする場合を例にするが、特にこれに限定しない。経路探索部１４は、設定部１０を介して利用者からの出発地の入力を受付けるようにしてもよい。
【００４８】
続いて、経路探索部１４は、データ読込部１２を介して、推奨経路の探索に必要なリンクデータ３１２を記憶装置３から読み込み（Ｓ１０１）、Ｓ１０２の処理に進む。具体的には、経路探索部１４は、記憶装置３から変換テーブルを読出し、現在位置および目的地を示す座標情報からその座標情報により特定される地点を含むメッシュ領域のメッシュＩＤを特定する。次に、経路探索部１４は、データ読込部１２を介して記憶装置３より、特定したメッシュＩＤを持つ地図データ各々に登録されている各リンクデータ３１２を入手する。
【００４９】
Ｓ１０２では、Ｓ１０１で読み込んだリンクデータ３１２を用いて、後述するＳ１０６でヒープテーブルから抽出されたリンク（進入リンクという）の終了ノードを開始ノードとするリンクを、推奨経路を構成するリンクの候補のリンク（脱出リンクとよぶ）として選出する。なお、進入リンクの終了ノードを開始ノードとするリンクが複数ある場合には、複数の脱出リンクが選出されることとなる。なお、Ｓ１０６での処理が行われていない場合、つまり、ヒープテーブルにリンクが登録されていない初期段階では、抽出された進入リンクの終了ノードを開始ノードとするリンクを候補リンクとして選出する代わりに、現在位置（または出発地）が存在あるいは現在位置に近接する少なくとも１つのリンクを、脱出リンクとして選出する。
【００５０】
ここで、ヒープテーブルとは、候補のリンクのリンクデータを、出発地から当該候補のリンクの終了ノードまでの総コスト（例えば旅行時間）と共に登録するためのテーブルであり、メモリ等の記憶装置に記憶される。
【００５１】
続いて、経路探索部１４は、選出した脱出リンクの舗装・未舗装判定処理を行い（Ｓ１０３）、Ｓ１０４の処理に進む。舗装・未舗装判定処理とは、Ｓ１０２で選出した脱出リンクを採用するか否かを判定する処理のことをいう。なお、舗装・未舗装判定処理は、後述する図６および図７で説明する。
【００５２】
Ｓ１０４では、経路探索部１４は、Ｓ１０３で採用された脱出リンク各々の総コスト（出発地から脱出リンクの終了ノードまでの総コスト）を算出する。具体的には、Ｓ１０１で読み出した各リンクデータ３１２を用いて、ヒープテーブルに登録されているリンクの総コストに、Ｓ１０３で採用された脱出リンクのコストを加算し、その加算結果を当該脱出リンクの総コストとする。ただし、ヒープテーブルにリンクが登録されていない初期段階では、Ｓ１０３で採用され脱出リンクのコストを当該脱出リンクの総コストとする。それから、経路探索部１４は、候補リンク各々のリンクデータおよび総コストをヒープテーブルに追加する。
【００５３】
次に、経路探索部１４は、直前に行ったＳ１０４にてヒープテーブルに新たに追加されたリンクの中に、目的地が存在あるいは目的地に近接するリンク（目的地リンクと呼ぶ）があるか否かを調べる（Ｓ１０５）。経路探索部１４は、Ｓ１０５において目的地リンクがないと判断したならば、Ｓ１０６の処理に進み、目的地リンクがあると判断した場合には、Ｓ１０７の処理に進む。
【００５４】
Ｓ１０６では、経路探索部４３は、ヒープテーブルに登録されているリンクの情報を総コストの小さい順にソートし、最初に位置するリンクを抽出するなどして、ヒープテーブルから総コストが最小のリンクを抽出する。それから、Ｓ１００２に戻る。
【００５５】
続いて、Ｓ１０５において目的地リンクがあると判断した場合に進むＳ１０７の処理について説明する。Ｓ１０７では、経路探索部１４は、推奨経路決定処理を行う。具体的には、ヒープテーブルから、目的地リンクを発生させたリンク（目的地リンクの開始ノードを終了ノードとするリンクと呼ぶ）を検索し、検出したリンクを推奨経路を構成するリンク（構成リンクと呼ぶ）に決定する。次に、構成リンクが、出発地が存在あるいは出発地に近接するリンク（出発地リンクと呼ぶ）であるか否かを調べ、出発地リンクでないならば、この構成リンクを発生させたリンクを検索し、検出したリンクを構成リンクに決定して、それが出発リンクであるか否かをさらに調べる。この処理を、構成リンクが出発リンクであると判断されるまで繰り返すことで、推奨経路を構成する各構成リンクを決定する。経路探索部１４は、推奨経路を決定したら処理を終了する。
【００５６】
続いて、上記の図５のＳ１０３の舗装・未舗装判定処理について図６および図７を用いて説明する。
【００５７】
図６は、本実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。図７は、進入リンクと脱出リンクとの関係を説明するための図である。なお、以下の説明では、図７に示すように、上述のＳ１０３で進入リンク５２に対し脱出リンク５３および５４が抽出されている場合を例に説明する。
【００５８】
先ず、経路探索部１４は、図５のＳ１０２で抽出した脱出リンクの中から一の脱出リンクを特定し（Ｓ２００）、Ｓ２０１の処理に進む。なお、ここでは、経路探索部１４が脱出リンク５３を特定したこととする。
【００５９】
Ｓ２０１では、経路探索部１４は、リンクデータ３１２から脱出リンクのリンク種別３１２４を取得し、Ｓ２０２の処理に進む。
【００６０】
Ｓ２０２では、経路探索部１４は、取得したリンク種別３１２４を用いて特定した脱出リンクが舗装路であるか否かの判定を行う。そして、経路判定部１４は、脱出リンクが舗装路であると判定した場合にはＳ２０３の処理に進み、脱出リンクが未舗装路であると判定した場合にはＳ２１０の処理に進む。
【００６１】
Ｓ２１０では、経路探索部１４は、進入リンク５２のリンク種別３１２４を取得し、Ｓ２１１の処理に進む。
【００６２】
Ｓ２１１では、経路探索部１４は、取得したリンク種別３１２４を用いて進入リンクが未舗装路であるか否かの判定を行う。そして、経路判定部１４は、進入リンクが未舗装路であると判定した場合にはＳ２０３の処理に進み、進入リンクが未舗装路ではないと判定した場合にはＳ２１２の処理に進む。
【００６３】
Ｓ２１２では、Ｓ２００で特定した脱出リンクを推奨経路を構成するリンクとして採用しないこととし、Ｓ２１３の処理に進む。
【００６４】
続いて、Ｓ２０２において特定した脱出リンクが舗装路であると判定した場合、および、Ｓ２１１において進入リンクが未舗装であると判定した場合に進むＳ２０３の処理を説明する。Ｓ２０３では、経路探索部１４は、Ｓ２００で特定した脱出リンクを、推奨経路を構成するリンクとして採用する。
【００６５】
その後、経路探索部１４は、図５のＳ１０２で抽出した全ての脱出リンクについて上述の判定処理（Ｓ２００〜Ｓ２１２）を行なったか否かを判定し、全ての脱出リンクを判定した場合に処理を終了する。一方、経路探索部１４は、Ｓ１０２で抽出した全ての脱出リンクについての判定を行なっていない場合、Ｓ２００の処理に戻る（Ｓ２１３）。図７の例では、脱出リンク５３および脱出リンク５４の両者について、推奨経路を構成するリンクとして採用するか否かを判定した場合に処理を終了する。
【００６６】
ここで、図６の処理を具体例を挙げて説明する。例えば、図７に示す例において、脱出リンク５３が未舗装路で、進入リンク５２が未舗装路であったとする。この場合、経路探索部１４は、Ｓ２０２、Ｓ２１０、およびＳ２１１の処理を実行した後、Ｓ２０３の処理に進み、脱出リンク５３を、推奨経路を構成するリンクとして採用する。また、例えば、脱出リンク５３が未舗装路で、進入リンク５２が舗装路であったとする。この場合、経路探索部１４は、Ｓ２０２、Ｓ２１０、およびＳ２１１の処理を実行した後、Ｓ２１２の処理に進み、脱出リンク５３を、推奨経路を構成するリンクとして採用しない。
【００６７】
このように、本実施形態の経路探索部１４は、経路探索処理において、推奨経路を構成するリンクとして舗装路を採用した場合、その舗装路に接続するリンクに未舗装路を採用しない。そのため、一度、舗装路のリンクが選択された場合、そのリンクに続く経路として、未舗装路が探索されることがない。また、本実施形態では、経路探索において、舗装路のリンクが選択されるまでは、未舗装のリンクの選択を認めるようにしている。これは、未舗装路のリンクを全て選択できないようにした場合に経路探索ができなくなることを考慮したためである。
【００６８】
続いて、本発明の第２実施形態について説明する。
【００６９】
第２実施形態は、上記第１実施形態のナビゲーション装置が有する経路探索部１４を変形したものである。具体的には、第２実施形態の経路探索部１４は、第１実施形態の経路探索部１４の機能に加え、さらに所定要件下において舗装路から未舗装路に入る経路を選択する機能を付加したものである。なお、第２実施形態は、第１実施形態と経路探索部１４の機能が異なる以外は同様の構成を有している。第２実施形態の説明において、第１実施形態と同じ構成については同じ符号を用いることとする。また、第２実施形態の説明では、第１実施形態と異なる
部分を中心に説明する。
【００７０】
第２実施形態の経路探索処理を、上述した図５を用いて説明する。
【００７１】
さて、第２実施形態の経路探索部１４は、図５に示す各処理ステップを行い、目的地までの推奨経路を探索する。具体的には、第２実施形態の経路探索部１４は、第１実施形態と同様の手順にしたがい、Ｓ１００〜１０３の処理を行なう。そして、Ｓ１０３で脱出リンクを１以上採用できた場合、Ｓ１０４では上述した第１実施形態と同様の処理を行なう。一方、Ｓ１０３で脱出リンクを１つも採用できない場合、経路探索部１４は、Ｓ１０４において、脱出リンクを採用できない進入リンクを特定するデータを保持する。例えば、経路探索部１４は、ヒープテーブルに登録されている、脱出リンクを採用できない「進入リンク」にフラグを対応付けて登録する。なお、以下では、フラグを対応付けて登録する場合を例にする。続いて、経路探索部１４は、上述したＳ１０５の処理を行なう。
【００７２】
Ｓ１０５の処理によりＳ１０６に進んだ場合、経路探索部１４は、ヒープテーブルからリンクを抽出する際、フラグに対応付けられているリンク以外のリンクを抽出し、Ｓ１０２の処理に戻る。なお、Ｓ１０６において、フラグに対応付けられているリンク以外のリンクを抽出した場合に行なうＳ１０２〜１０５は、上記と同様である。
【００７３】
ここで、Ｓ１０６において、抽出できるリンクがない場合（すなわち、目的地までの経路探索ができない場合）がある。この場合、経路探索部１４は、ヒープテーブルに登録されたフラグを消去した上で、リンクの抽出を行い、Ｓ１０２〜Ｓ１０３の処理に進む。なお、Ｓ１０６において、ヒープテーブルに登録されたフラグを消去した上でリンクの抽出を行なった場合、経路探索部１４は、Ｓ１０３で行う舗装・未舗装判定処理を、図６に示す処理から図８に示す処理に変更する。
【００７４】
ここで、目的地までの経路探索ができない場合の例を図９に示す。図９は、目的地が未舗装路のリンクにだけ接続している場合を例示した図である。図９では、目的地７０に到達するために未舗装路のリンク６３および未舗装路のリンク６４のいずれかを通過する必要がある場合を示している。また、未舗装路のリンク６３および未舗装路のリンク６４には、それぞれ、舗装路のリンク６２および舗装路のリンク６５が接続されている。図示する例において、経路探索部１４が図６に示す舗装・未舗装判定処理を行なったとする。この場合、リンク６２を経由する場合に脱出リンクとしてリンク６３は採用されない。同様に、リンク６５を経由する場合に脱出リンクとしてリンク６４は採用されない。図６の舗装・未舗装判定処理では、舗装路のリンクから未舗装路のリンクに入る経路は選択されないためである。その結果、目的地までの経路が探索できないこととなる。そのため、第２実施形態では、目的地までの経路を探索できない場合において、舗装路のリンクから未舗装のリンクを選択する処理を行なうようにしている。以下、目的地までの経路を探索できない場合に行なう経路探索のリトライ処理を説明する。
【００７５】
図８は、第２実施形態のナビゲーション装置が行なう舗装・未舗装判定処理のフローチャートである。
【００７６】
先ず、経路探索部１４は、図５のＳ１０２で抽出された脱出リンクを特定する処理を行なう。具体的には、図６のＳ２００と同様の手順により脱出リンクを特定する（Ｓ３００）。
【００７７】
次に、経路探索部１４は、リンクデータ３１２を用いて進入リンクの種別を特定し、進入リンクが舗装路であるか否かの判定を行う（Ｓ３０１〜３０２）。判定の結果、進入リンクが舗装路である場合にＳ３０３に進み、進入リンクが舗装路でない場合にＳ３１０に進む。
【００７８】
Ｓ３１０では、経路探索部１４は、リンクデータ３１２を用いて脱出リンクの種別を取得する。経路探索部１４は、脱出リンクが舗装路であるか否かの判定を行い、脱出リンクが舗装路であると判定した場合にＳ３１２に進み、脱出リンクが舗装路ではないと判定した場合にＳ３０３に進む。Ｓ３１２では、経路探索部１４は、脱出リンクを、推奨経路を構成するリンクとして採用しないことに決定して、Ｓ３１３の処理に進む（Ｓ３１２）。
【００７９】
続いて、Ｓ３０２において進入リンクが舗装路であると判定した場合、および、Ｓ３１１において脱出リンクが舗装路ではないと判定した場合に進むＳ３０３の処理を説明する。Ｓ３０３では、経路探索部１４は、Ｓ３００で特定した脱出リンクを、推奨経路を構成するリンクとして採用する。
【００８０】
その後、経路探索部１４は、図５のＳ１０２で抽出した全ての脱出リンクについて上述の判定処理（Ｓ３００〜Ｓ３１２）を行なったか否かを判定し、全ての脱出リンクを判定した場合に処理を終了する。一方、経路探索部１４は、Ｓ１０２で抽出した全ての脱出リンクについての判定を行なっていな場合、Ｓ３００の処理に戻る（Ｓ３１３）。
【００８１】
このように第２実施形態によれば、第１実施形態と同様に目的地までの経路に未舗装路が含まれる可能性を低下させることができる。また、第２実施形態によれば、目的地に未舗装路を経由しないと到達しない場合に舗装路から未舗装路に入るリンクを採用するようにしている。そのため、第１実施形態と同様の手順に従い経路探索を行った結果、目的地までの経路を探索できない場合であっても、上述した図８の処理を行なうことにより経路を探索することが可能となる。
【００８２】
なお、本発明は以上で説明した実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形が可能である。例えば、第１実施形態のナビゲーション装置が未舗装路を経由しないと到達しない目的地への経路探索を行った場合、探索できたリンクまでの経路を保持する。そして、経路探索部１４は、探索できた経路から以降については、舗装路・未舗装路に関係なく目的地に至るまでの経路を探索するようにしてもよい。
【図面の簡単な説明】
【００８３】
【図１】本発明の実施形態が適用された車載用ナビゲーション装置の概略構成図である。
【図２】本発明の実施形態の記憶装置３に記憶されている地図データのデータ構造を模擬的に示す図である。
【図３】本発明の実施形態の演算処理部１の機能構成を説明するための図である。
【図４】本発明の実施形態の演算処理部１のハードウェア構成を示す図である。
【図５】本発明の実施形態のナビゲーション装置が行なう経路探索の処理のフローを説明するための図である。
【図６】本発明の実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。
【図７】進入リンクと脱出リンクとの関係を説明するための図である。
【図８】第２実施形態のナビゲーション装置が行なう経路探索の処理の中の舗装・未舗装判定処理のフローチャートである。
【図９】目的地が未舗装路のリンクにだけ接続している場合を例示した図である。
【符号の説明】
【００８４】
１…演算処理部、２…ディスプレイ、３…記憶装置、４…音声入出力装置、５…入力装置、６…車輪速センサ、７…地磁気センサ、８…ジャイロ、９…ＧＰＳ受信装置、１０…設定部、１１…現在位置検出部、１２…データ読込部、１３…マップマッチ処理部、１４…経路探索部、１５…経路誘導部、１６…地図表示処理部、１７…グラフィックス処理部、２１…ＣＰＵ、２２…ＲＡＭ、２３…ＲＯＭ、２４…ＤＭＡ、２５…描画コントローラ、２６…ＶＲＡＭ、２７…カラーパレット、２８…Ａ/Ｄ変換器、２９…ＳＣＩ、３０…ＰＩＯ、３１…カウンタ
【特許請求の範囲】
【請求項１】
地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置であって、
前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、
前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する経路探索手段と、を有し、
前記経路探索手段は、
前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索すること
を特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
前記経路探索手段は、
前記推奨経路を探索する際、
既に探索されたリンク（進入リンク）の出口に接続できるリンクの中から一の候補リンクを特定し、
前記道路情報を用いて、前記候補リンクが舗装路であるか否かを判定し、
前記候補リンクが舗装路の場合に該候補リンクを前記推奨経路を構成するリンクとして選択し、
前記候補リンクが未舗装路の場合、さらに前記道路情報を用いて、前記進入リンクが舗装路であるか否かを判定し、該進入リンクが未舗装路の場合に前記候補リンクを前記推奨経路を構成するリンクとして選択し、該進入リンクが舗装路の場合に前記候補リンクを前記推奨経路を構成するリンクとして選択しないこと
を特徴とするナビゲーション装置。
【請求項３】
請求項１または２に記載のナビゲーション装置であって、
前記経路探索手段は、
前記出発地から前記目的地までの推奨経路を探索できない場合に、舗装路のリンクの出口に接続するリンクとして前記未舗装路のリンクを選択すること
を特徴とするナビゲーション装置。
【請求項４】
地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置が行なう経路探索方法であって、
前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、
前記ナビゲーション装置は、
前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索するステップを行い、
前記推奨経路を探索するステップは、
前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索すること
を特徴とする経路探索方法。
【請求項１】
地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置であって、
前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、
前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索する経路探索手段と、を有し、
前記経路探索手段は、
前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索すること
を特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置であって、
前記経路探索手段は、
前記推奨経路を探索する際、
既に探索されたリンク（進入リンク）の出口に接続できるリンクの中から一の候補リンクを特定し、
前記道路情報を用いて、前記候補リンクが舗装路であるか否かを判定し、
前記候補リンクが舗装路の場合に該候補リンクを前記推奨経路を構成するリンクとして選択し、
前記候補リンクが未舗装路の場合、さらに前記道路情報を用いて、前記進入リンクが舗装路であるか否かを判定し、該進入リンクが未舗装路の場合に前記候補リンクを前記推奨経路を構成するリンクとして選択し、該進入リンクが舗装路の場合に前記候補リンクを前記推奨経路を構成するリンクとして選択しないこと
を特徴とするナビゲーション装置。
【請求項３】
請求項１または２に記載のナビゲーション装置であって、
前記経路探索手段は、
前記出発地から前記目的地までの推奨経路を探索できない場合に、舗装路のリンクの出口に接続するリンクとして前記未舗装路のリンクを選択すること
を特徴とするナビゲーション装置。
【請求項４】
地図データに含まれているリンク情報を用いて出発地から目的地までの推奨経路を探索するナビゲーション装置が行なう経路探索方法であって、
前記リンク情報には、リンク毎に該リンクが舗装路であるか否かを示す道路情報が含まれていて、
前記ナビゲーション装置は、
前記リンク情報を用いて、前記出発地と前記目的地とを結ぶ複数のリンクにより構成される推奨経路を探索するステップを行い、
前記推奨経路を探索するステップは、
前記道路情報を用いて、舗装路のリンクの出口に接続するリンクとして未舗装路のリンクを選択しないで前記推奨経路を探索すること
を特徴とする経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−１４５２２１（Ｐ２００６−１４５２２１Ａ）
【公開日】平成１８年６月８日（２００６．６．８）
【国際特許分類】
【出願番号】特願２００４−３３１７３２（Ｐ２００４−３３１７３２）
【出願日】平成１６年１１月１６日（２００４．１１．１６）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
【公開日】平成１８年６月８日（２００６．６．８）
【国際特許分類】
【出願日】平成１６年１１月１６日（２００４．１１．１６）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
[ Back to top ]