ナビゲーション装置及びルート探索方法

【課題】階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供する。
【解決手段】出発地点を含むセルAにおいては、セルAを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートをセルAにおけるルートに設定する。その退出地点を進入地点とするセルBにおいては、進入地点が代表ルートの入口に位置しているため、その代表ルートの出口を退出地点に設定し、その代表ルートをセルBにおけるルートに設定する。そして、セルBと同様の処理をセルC〜Fにおいても行う。目的地点を含むセルGにおいては、進入地点から目的地点までのルートを探索して、探索したルートをセルGにおけるルートに設定する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、出発地点から目的地点までのルートを探索するための技術に関する。
【背景技術】
【0002】
従来、ナビゲーション装置では、地図データを用いて出発地点から目的地点までのルート(経路)を探索する技術が利用されている。ルート探索の基本的な手法は、出発地点から目的地点までのルートとして設定し得るすべてのルートの中から、最も適切な(例えば走行距離が最短となる)ルートを選択するという総当たりの手法である。ただし、この手法では、ルート探索のための計算量が膨大となり、処理時間が長くなってしまう。そこで、ルート探索に要する時間を短縮するための手法が提案されている。
【0003】
例えば特許文献1には、上位レベルほどリンク数が少なくなるように階層化された構造の地図データを用いて、ルート探索に要する時間を短縮する構成のナビゲーション装置について記載されている。具体的には、このナビゲーション装置が用いる地図データは、基準レベルの道路リンク情報、基準レベルの道路リンク情報を用いてレベル格上げ処理を行って得られた第1上位レベルのリンク情報、第1上位レベルのリンク情報を用いてレベル格上げ処理を行って得られた複数の第2上位レベルのリンク情報といった形の階層構造を有する。なお、ここでいうレベル格上げ処理とは、探索枝数が規定数以上のリンクを上位レベルのリンクとして格上げすることにより、上位レベルのリンクを決定する処理のことである。
【0004】
そして、特許文献1に記載のナビゲーション装置は、出発地点と目的地点との間の直線距離を算出し、算出した直線距離に基づいて、ルート探索に使用するリンクが属する第1レベル以外の上位レベルを決定する。その後、ナビゲーション装置は、基準レベルにおいて第1上位レベルに移行可能なリンクまでのルートを探索し、第1上位レベルにおいて、先に決定した更に上位のレベルに移行可能なリンクまでのルートを探索して、その上位レベルのリンク情報を用いてルート探索を行う。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2007−292988号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
前述した特許文献1に記載のルート探索の手法は、階層構造に整備された地図データを必要とするものであり、地図データが階層構造に整備されていない場合には適用することができなかった。
【0007】
本発明は、こうした問題にかんがみてなされたものであり、階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供することを目的としている。
【課題を解決するための手段】
【0008】
請求項1に記載のナビゲーション装置は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する区画ルート探索手段を備える。具体的には、この区画ルート探索手段は、出発ルート探索手段、中間ルート探索手段及び目的ルート探索手段を備える。
【0009】
出発ルート探索手段は、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索手段は、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索手段は、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【0010】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索手段は、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【0011】
このような構成によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【0012】
ここで、代表ルートの出口が複数存在する場合には、請求項2に記載のように、目的地点の位置に応じて選択した出口を退出地点に設定するようにしてもよい。このようにすれば、目的地点に応じた適切なルートを設定することが可能となる。
【0013】
具体的には、請求項3に記載のように、代表ルートの出口は、区画の外縁を形成する複数の辺のいずれかに位置し、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点の方角に応じた適切なルートを設定することが可能となる。
【0014】
また、請求項4に記載のように、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点へ向かった適切なルートを設定することができる。
【0015】
また、請求項5に記載のように、出発ルート探索手段は、出発区画が代表設定区画である場合には、代表ルートの出口を退出地点に設定するようにしてもよい。つまり、出発地点から代表ルートの出口までのルートを探索するのである。このようにすれば、出口があらかじめ設定されているため、総当たりの手法でルートを探索するとしても探索の手間や時間を大幅に短縮することができる。しかも、出発区画の退出地点を進入地点とする中間区画において、進入地点を代表ルートの入口に位置させることができるため、以降の区画における探索の処理負荷を抑えることができる。
【0016】
また、請求項6に記載のように、代替ルート探索手段及び差替手段を更に備え、代替ルート探索手段が、出発地点から目的地点までのルートを区画ルート探索手段とは異なる方法で探索し、差替手段が、区画ルート探索手段により探索された第1のルートを、代替ルート探索手段により探索された第2のルートに差し替えるようにしてもよい。このようにすれば、第2のルートと比較して短時間で探索可能な第1のルートを最初に提示し、その後に第1のルートと比較して信頼性の高い第2のルートに差し替えるといったことが可能となる。
【0017】
ただし、第1のルートが第2のルートに差し替えられることをユーザが望まない場合も考えられる。そこで、請求項7に記載のように、差替手段は、第1のルートを第2のルートに差し替えるか否かをユーザに選択させるようにしてもよい。このようにすれば、ユーザの意に反して第1のルートが第2のルートに差し替えられてしまうことを防ぐことができる。
【0018】
また、代表ルートに代えて第2のルートが走行される場合には、その第2のルートを代表ルートとした方がユーザにとって好ましい場合もある。そこで、請求項8に記載のように、登録手段を更に備え、この登録手段が、代表ルートと異なる第2のルートが走行されたことを条件として、第2のルートを代表ルートとして登録するようにしてもよい。このようにすれば、代表ルートをユーザに応じた適切なルートに更新することができる。
【0019】
次に、請求項9に記載のルート探索方法は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する方法であって、出発ルート探索ステップ、中間ルート探索ステップ及び目的ルート探索ステップを備える。
【0020】
出発ルート探索ステップでは、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索ステップでは、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索ステップでは、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。
【0021】
また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索ステップでは、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。
【0022】
このような方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【図面の簡単な説明】
【0023】
【図1】実施形態のナビゲーション装置の概略構成を示すブロック図である。
【図2】複数のセルに分割された地図を示す図である。
【図3】(A)はセルの一例を示す図、(B)はセルにおける代表ルートの入口と出口との対応関係を示す図である。
【図4】ルート探索処理のフローチャートである。
【図5】ルート設定処理のフローチャートである。
【図6】(A)は対象セルへの進入地点が代表ルートの入口に位置している状態を示す図、(B)は対象セルへの進入地点が代表ルートの入口に位置していない状態を示す図である。
【図7】ルート差替処理のフローチャートである。
【図8】代表ルート更新処理のフローチャートである。
【発明を実施するための形態】
【0024】
以下、本発明が適用された実施形態について、図面を用いて説明する。
図1は、実施形態のナビゲーション装置の概略構成を示すブロック図である。
このナビゲーション装置は、車両に搭載されて用いられるものであり、位置検出部11、地図データ記憶部15、操作部16、表示部17、音声出力部18、制御部19などを備える。
【0025】
位置検出部11は、GPS(Global Positioning System)用の人工衛星からの送信信号を受信し、車両の位置座標や高度を検出するGPS受信機12と、車両に加えられる回転運動の角速度に応じた検出信号を出力するジャイロスコープ13と、車両の走行距離を出力する距離センサ14とを備える。そして、これらの各センサ12〜14の出力信号に基づいて制御部19が、現在位置、方位、速度等を算出する。
【0026】
地図データ記憶部15は、地図データを記憶し、その各種データを制御部19に入力する。地図データ記憶部15に格納されるデータは、交差点等の特定地点に対応するノード及びノード間を接続するリンクによって道路の接続状況を示す道路データや、地図上の施設に関する施設データ、ルート案内を行うための案内データなどを含む各種データである。
【0027】
操作部16は、ユーザからの各種指示(各種の設定や機能実行の指示)を入力するためのものであり、表示部17の表示画面上に配置されたタッチパネルや、メカニカルなキースイッチ等が用いられる。
【0028】
表示部17は、液晶ディスプレイ等の表示画面を有するものであり、制御部19からの映像信号の入力に応じて各種画像を表示画面に表示する。この表示部17は、地図画像の表示や、出発地点から目的地点までの誘導ルート、車両の現在位置を示すマーク、その他の案内情報等の表示に用いられる。
【0029】
音声出力部18は、各種情報を音声にてユーザに報知する。これによって、表示部17による表示と音声出力部18による音声出力との両方でユーザに対して各種ルート案内を行うことができる。
【0030】
制御部19は、CPU、ROM、RAM、I/O及びこれらの構成を接続するバスライン等からなる周知のマイクロコンピュータを中心に構成されている。そして、CPUは、ROMに記憶されているプログラムに従い、位置検出部11、地図データ記憶部15、操作部16から入力された各種情報に基づき、各種処理を実行する。
【0031】
具体的には、制御部19は、地図データ記憶部15に記憶されている地図データを用いて、現在位置(出発地点)から目的地点までのルートを探索するルート探索処理を実行する。本実施形態で用いられる地図データは、図2に示すように、複数のセル(一定サイズの正方形の区画)に分割されており、制御部19は、出発地点から目的地点までのルートを、次の(1)〜(3)の手順でセルごとに探索する。
【0032】
(1)出発地点を含むセル(以下「出発セル」ともいう。)において、その出発セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その出発地点から、設定した退出地点までのルートを探索し、探索したルートをその出発セルにおけるルートに設定する。
【0033】
(2)出発地点及び目的地点を含まないセルであって、他のセルで設定された退出地点を進入地点とするセル(以下「中間セル」ともいう。)において、その中間セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その進入地点から、設定した退出地点までのルートを探索し、探索したルートをその中間セルにおけるルートに設定する。
【0034】
(3)目的地点を含むセルであって他のセルで設定された退出地点を進入地点とするセル(以下「目的セル」ともいう。)において、その進入地点から目的地点までのルートを探索し、探索したルートをその目的セルにおけるルートに設定する。
【0035】
このように制御部19は、1セル分の地図データを順に読み込み、セルごとにルートを探索することで、出発地点から目的地点までのルートを探索する。ただし、セル内において総当たりの手法でルートを探索すると、ルート探索に要する時間が長くなる。特に、すべてのセルにおいて総当たりの手法でルートを探索すると、セル数に比例して探索時間が増大してしまう。
【0036】
そこで、本実施形態では、図2に示すように、各セルにおいて、例えば幹線道路などのように、走行案内するルートに適した一部の道路が、代表ルート(セルの拡大図において太線で示されたルート)としてあらかじめ設定されている。各セルにおける代表ルートの入口及び出口は、セルの外縁を形成する4つの辺(北側、西側、南側及び東側の各方角に対応する辺)のいずれかに位置し、あるセルにおける代表ルートの出口は、その出口が位置する辺で隣接する他のセルにおける代表ルートの入口となる。
【0037】
また、代表ルートの設定されたセル(以下「代表設定セル」ともいう。)には、図3(A),(B)に示すように、セルにおける各方角の辺を基準とした代表ルートの入口と出口との対応関係が記憶されている。例えば、図3(A)に示すセルの場合、代表ルートの入口又は出口となり得る箇所が、東側、南側及び北側の3箇所に存在する。そして、このセルでは、図3(B)に示すように、東側を入口とした場合の出口が南側の1箇所、南側を入口とした場合の出口が東側及び北側の2箇所、北側を入口とした場合の出口が南側の1箇所に設定され、かつそれら出口に至るためのルート(代表ルート)がそれぞれ一意に定義されている。なお、東側を入口とした場合の出口を北側及び南側の2箇所に設定してもよく、同様に、北側を入口とした場合の出口を東側及び南側の2箇所に設定してもよい。
【0038】
このように、代表設定セルでは、代表ルートの入口と出口との対応関係が設定されているため、代表ルートの入口に対応する出口を選択するだけで、入口から出口へ至るルートを考慮することなく(最短ルートであるか否かは問わず)、ルートを設定することが可能となる。そして、セルにおける代表ルートの出口を、隣接するセルにおける代表ルートの入口として、代表ルートを順につないでいくことにより、短時間でルートを設定することができる。
【0039】
ここで、このような処理を実現するために制御部19が実行する具体的処理内容について説明する。図4は、制御部19が実行するルート探索処理のフローチャートである。このルート探索処理は、ルート探索を開始する操作がユーザにより操作部16で行われることにより開始される。
【0040】
制御部19は、ルート探索処理を開始すると、まずS101で、目的地点をユーザに設定させる。続いてS102で、階層構造の地図データが使用可能であるか否かを判定する。すなわち、地図データ記憶部15に記憶される地図データが、階層構造に整備されたものであるか否かを判定する。例えば、ナビゲーション装置が複数の国で使用されるものであり、国によって地図データの構造が異なるような場合に、このような判定が有効となる。なお、階層構造に整備されていない地図データを用いることが決まっている場合には、S102の判定処理を行うことなくS104へ移行するようにしてもよい。
【0041】
そして、S102で、階層構造の地図データが使用可能であると判定した場合には、S103へ移行して、階層構造の地図データを使用してルートを設定した後、S111へ移行する。この場合のルート設定は、従来技術をそのまま適用すればよいため、具体的な説明は省略する。
【0042】
一方、S102で、階層構造の地図データが使用可能でないと判定した場合には、前述したS103の処理に代えて、S104〜S110の処理を実行する。すなわち、まずS104で、出発地点(通常は現在位置)を含むセルを処理対象のセル(以下「対象セル」という。)に設定する。続いてS105では、対象セルのルート設定に代表ルートを使用可能である(対象セルに代表ルートが設定されている)か否かを判定する。このS105で、対象セルのルート設定に代表ルートを使用可能であると判定した場合には、S106へ移行して、代表ルートを使用してルートを設定するためのルート設定処理を実行した後、S108へ移行する。
【0043】
ここで、図4のS106で実行されるルート設定処理の詳細について図5のフローチャートを用いて説明する。制御部19は、ルート設定処理を開始すると、まずS201で、対象セルへの進入地点が、その対象セルに設定されている代表ルートの入口に位置しているか否かを判定する。なお、対象セルへの進入地点とは、前回の対象セルの退出地点(後述)のことである。ただし、対象セルに出発地点が含まれる場合には、その出発地点を進入地点として処理を行う。
【0044】
そして、図6(A)に例示するように、S201で、対象セルへの進入地点が代表ルートの入口に位置していると判定した場合には、S202へ移行し、対象セルを基準とした目的地点の方角を判定する。本実施形態では、対象セルの中心位置を基準とした目的地点の方角が、北東〜北西(北東含む)、北西〜南西(北西含む)、南西〜南東(南西含む)、南東〜北東(南東含む)の4つの範囲のいずれに分類されるかを判定する。
【0045】
そして、S202で目的地点の方角が北東〜北西(北東含む)に分類されると判定した場合には、S203へ移行し、進入地点を入口とする代表ルートの出口のうち、対象セルにおける北側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。
【0046】
また、S202で目的地点の方角が北西〜南西(北西含む)に分類されると判定した場合には、S204へ移行し、代表ルートの出口のうち、対象セルにおける西側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。
【0047】
また、S202で目的地点の方角が南西〜南東(南西含む)に分類されると判定した場合には、S205へ移行し、代表ルートの出口のうち、対象セルにおける南側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。
【0048】
また、S202で目的地点の方角が南東〜北東(南東含む)に分類されると判定した場合には、S206へ移行し、代表ルートの出口のうち、対象セルにおける東側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。
【0049】
S207では、進入地点から退出地点までの代表ルートを、対象セルのルートに設定し、図5のルート設定処理を終了する。このように、進入地点が代表ルートの入口に位置する場合には、ルート計算を行うことなく、目的地点の方角に応じた出口を選択するだけでルートが設定される。
【0050】
なお、目的地点の方角に代表ルートの出口が存在しない場合には、他の方角の出口の中から、目的地点の方角に近い方角の出口を選択するようにしてもよい。また、対象セルへの進入地点の方角から遠い方角の出口を選択するようにしてもよい。例えば、対象セルへの進入地点が西側、目的地点が南の方角であって、対象セルにおける南側の辺に出口が設定されていない場合には、東側の辺に設定された出口(目的地点の方角に近い方角であって、進入地点の方角から遠い方角)を優先的に選択する。
【0051】
また、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、代表ルートの出口の数が同じ方角に2つ以上存在するような場合にも、目的地点の位置に応じた1つの出口として選択することができるため、目的地点へ向かった適切なルートを設定することができる。
【0052】
一方、図6(B)に例示するように、S201で、対象セルへの進入地点が代表ルートの入口に位置していないと判定した場合には、S208へ移行し、総当たりの手法でルート探索を行い、対象セルのルートを設定した後、図5のルート設定処理を終了する。なお、この場合の退出地点も、目的地点の位置に応じて(例えば目的地点との距離が最も近い出口などに)設定される。特に、この退出地点を代表ルートの出口から選択するようにすれば、次回の対象セルの進入地点を代表ルートの入口に位置させることができる。つまり、進入地点から対象セルの代表ルートの出口までのルート探索を行うのである。こうすれば、出口があらかじめ設定されているため、総当たりの手法でルート探索するとしても探索の手間、時間を大幅に短縮することができる。とりわけ対象セルが出発セルである場合、すなわち進入地点が出発地点(通常は現在位置)である場合、この方法をとれば、それ以後の探索の手間、時間を容易に節約できる。
【0053】
図4に戻り、S105で対象セルのルート設定に代表ルートを使用可能でないと判定した場合には、S107へ移行し、前述したS208と同様、総当たりの探索処理を実施して対象セルのルートを設定した後、S108へ移行する。
【0054】
S108では、設定したルートの出口(退出地点)が位置する辺で現在の対象セルに隣接するセルを、次の対象セルに設定する。続いてS109では、設定した対象セルに目的地点が含まれているか否かを判定し、含まれていない(中間セルである)と判定した場合には、S105へ戻り、前述した処理(S105〜S108)を行う。
【0055】
一方、S109で対象セルに目的地点が含まれている(目的セルである)と判定した場合には、S110へ移行し、総当たりの探索処理を実施して対象セルのルート(進入地点から目的地点までのルート)を設定する。これにより、出発地点から目的地点までのルートが設定される。
【0056】
続いて、S111では、こうして設定したルートを必要に応じて別のルートに差し替えるルート差替処理を実行し、図4のルート探索処理を終了する。ここで、図4のS111で実行されるルート差替処理の詳細について図7のフローチャートを用いて説明する。制御部19は、ルート差替処理を開始すると、まずS301で、代表ルートを使用したルート設定処理(S106)を行ったか否かを判定し、ルート設定処理を行っていないと判定した場合には、図7のルート差替処理を終了する。
【0057】
一方、S301で、代表ルートを使用したルート設定処理を行ったと判定した場合には、S302へ移行し、総当たりの手法での出発地点から目的地点までのルート探索を、バックグラウンドで実行する。
【0058】
続いて、S303では、設定済みのルート(代表ルートを使用して設定したルート)を、バックグラウンドで探索したルート(総当たりの手法で探索したルート)に差し替えるか否かをユーザに確認する。そして、ルートを差し替えるための操作がユーザにより行われた場合には、S304へ移行し、設定済みのルートをバックグラウンドで探索したルートに差し替えた後、S305へ移行する。一方、ルートを差し替えないための操作がユーザにより行われた場合には、そのままS305へ移行する。S305では、地図データにおいて設定されている代表ルートを必要に応じて更新するための代表ルート更新処理を実行し、ルート差替処理を終了する。
【0059】
ここで、図7のS305で実行される代表ルート更新処理の詳細について図8のフローチャートを用いて説明する。制御部19は、代表ルート更新処理を開始すると、まずS401で、出発地点を含むセルを対象セルに設定する。
【0060】
続いてS402では、対象セルの代表ルートとバックグラウンドで探索したルートとが同じであるか否かを判定し、同じでないと判定した場合には、S403へ移行して、バックグラウンドで探索したルートを車両が実際に走行したか否かを判定する。
【0061】
そして、S403でバックグラウンドで探索したルートを走行したと判定した場合には、S404へ移行し、対象セルの代表ルートをバックグラウンドで探索したルートに更新する。一方、S402で対象セルの代表ルートとバックグラウンドで探索したルートとが同じであると判定した場合や、S403でバックグラウンドで探索したルートを走行していないと判定した場合には、代表ルートを更新せずにS405へ移行する。
【0062】
S405では、次のセルを対象セルに設定する。続いてS406では、対象セルに目的地点が含まれているか否かを判定し、含まれていないと判定した場合には、S402へ戻り、前述した処理(S402〜S405)を行う。一方、S406で対象セルに目的地点が含まれていると判定した場合には、図8の代表ルート更新処理を終了する。
【0063】
次に、ルート探索の具体例について、図2を用いて説明する。
(1)セルA
セルA(出発セル)においては、出発地点が代表ルートの入口に位置していないため(S201:NO)、総当たりの手法でルート探索が行われる(S208)。具体的には、代表ルートの出口(この例では北側1箇所及び南側1箇所の合計2箇所)のうち、目的地点との距離が最も近い出口(北側の出口)が、セルAを退出する退出地点として設定される。そして、出発地点から退出地点までのルートが探索され、探索されたルートがセルAにおけるルートとして設定される。
【0064】
(2)セルB
セルAの退出地点を進入地点とするセルB(中間セル)においては、進入地点が代表ルートの入口に位置しているため(S201:YES)、この代表ルートがセルBにおけるルートとして設定される(S202〜S207)。具体的には、代表ルートの出口(この例では北側1箇所及び西側1箇所の合計2箇所)のうち、目的地点に近い方角に存在する出口(北側の出口)が、セルBを退出する退出地点として設定される。
【0065】
(3)セルC
セルBの退出地点を進入地点とするセルC(中間セル)においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルCにおけるルートとして設定される。具体的には、代表ルートの出口(この例では北側1箇所、西側1箇所及び東側1箇所の合計3箇所)のうち、目的地点の方角に存在する出口(東側の出口)が、セルCを退出する退出地点として設定される。
【0066】
(4)セルD
セルCの退出地点を進入地点とするセルD(中間セル)においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルDにおけるルートとして設定される。具体的には、代表ルートの出口(この例では東側1箇所)のうち、目的地点の方角に存在する出口(東側の出口)が、セルDを退出する退出地点として設定される。
【0067】
(5)セルE
セルDの退出地点を進入地点とするセルE(中間セル)においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルEにおけるルートとして設定される。具体的には、代表ルートの出口(この例では北側1箇所、南側1箇所及び東側1箇所の合計3箇所)のうち、目的地点の方角に存在する出口(北側の出口)が、セルEを退出する退出地点として設定される。
【0068】
(6)セルF
セルEの退出地点を進入地点とするセルF(中間セル)においても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルFにおけるルートとして設定される。具体的には、代表ルートの出口(この例では東側1箇所)のうち、目的地点の方角に存在する出口(東側の出口)が、セルFを退出する退出地点として設定される。
【0069】
(7)セルG
セルFの退出地点を進入地点とするセルG(目的セル)においては、進入地点から目的地点までのルート探索が、総当たりの手法で行われ、探索されたルートがセルGにおけるルートとして設定される(S110)。このようにして、出発地点から目的地点までのルートが設定される。
【0070】
以上説明したように、本実施形態のナビゲーション装置は、複数のセルに分割された地図を表す地図データを用いて、出発地点から目的地点までのルートをセルごとに探索する(S104〜S110)。
【0071】
具体的には、出発地点を含むセルである出発セルにおいて、出発セルを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発セルにおけるルートに設定する(S104〜S109)。そして、出発地点及び目的地点を含まないセルであって他のセルで設定された退出地点を進入地点とする中間セルにおいて、中間セルを退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間セルにおけるルートに設定する(S104〜S109)。さらに、目的地点を含むセルであって他のセルで設定された退出地点を進入地点とする目的セルにおいて、進入地点から目的地点までのルートを探索して、探索したルートを目的セルにおけるルートに設定する(S110)。
【0072】
また、複数のセルには、セルを通過するルートとして1つ以上の代表ルートが設定された代表設定セルが含まれる。そして、中間セルが代表設定セルであって(S105:YES)、進入地点が代表ルートの入口である場合には(S201:YES)、その代表ルートの出口を退出地点に設定し、その代表ルートを中間セルにおけるルートに設定する(S202〜S207)。
【0073】
このようなルート探索方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、総当たりでルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。
【0074】
また、目的地点の位置に応じて選択した出口をセルの退出地点に設定するようにしているため(S202〜S206)、代表ルートの出口が複数存在する場合にも、目的地点に応じた適切なルートを設定することが可能となる。具体的には、代表ルートの出口は、正方形のセルの4つの辺のいずれかに位置し、代表ルートの出口が複数存在する場合には、中間セルにおける基準位置(本実施形態では中心位置)に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択する(S202〜S206)。このため、目的地点の方角に応じた適切なルートを設定することが可能となる。
【0075】
また、代表ルートを使用して設定した第1のルートとは別に、出発地点から目的地点までの第2のルートを総当たりの探索処理で探索し(S302)、第1のルートを第2のルートに差し替える(S304)。このため、第2のルートと比較して短時間で探索可能な第1のルートを最初に提示し、その後に第1のルートと比較して信頼性の高い第2のルートに差し替えるといったことが可能となる。特に、第1のルートを第2のルートに差し替えるか否かをユーザに選択させるようにしているため(S303)、ユーザの意に反して第1のルートが第2のルートに差し替えられてしまうことを防ぐことができる。加えて、代表ルートと異なる第2のルートが走行された場合に(S402:NO,S403:YES)、第2のルートを代表ルートとして登録するようにしているため(S404)、代表ルートをユーザに応じた適切なルートに更新することができる。
【0076】
なお、本実施形態では、S104〜S110が、区画ルート探索手段としての処理の一例に相当し、特に、S104〜S109が、出発ルート探索手段及び中間ルート探索手段としての処理(出発ルート探索ステップ及び中間ルート探索ステップ)の一例に相当し、S110が、目的ルート探索手段としての処理(目的ルート探索ステップ)の一例に相当する。また、S302が、代替ルート探索手段としての処理の一例に相当し、S304が、差替手段の一例に相当し、S305が、登録手段の一例に相当する。また、出発セル、中間セル、目的セル及び代表設定セルが、出発区画、中間区画、目的区画及び代表設定区画の一例にそれぞれ相当する。
【0077】
以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。
(1)上記実施形態では、バックグラウンドで探索したルート(代表ルートとは異なるルート)が走行された場合に、代表ルートを更新するようにしているが、これに限定されるものではない。例えば、バックグラウンドで探索したルートのセルにおける入口及び出口の各方角が、代表ルートの入口及び出口の各方角と同じであることを条件に加えてもよい。このようにすれば、セルにおける代表ルートの入口及び出口の数(各方角における数)を一定に保ちつつ代表ルートを更新することができる。また、代表ルートを更新する(既存の代表ルートを削除して新規の代表ルートを記憶する)ことに代えて、代表ルートを追加する(既存の代表ルートを削除せずに新規の代表ルートを記憶する)ようにしてもよい。
【0078】
(2)上記実施形態では、セルの中心位置を基準として目的地点の方角を判定するようにしているが、これに限定されるものではなく、例えば、セルへの進入地点を基準として目的地点の方角を判定するようにしてもよい。
【符号の説明】
【0079】
11…位置検出部、12…GPS受信機、13…ジャイロスコープ、14…距離センサ、15…地図データ記憶部、16…操作部、17…表示部、18…音声出力部、19…制御部

【特許請求の範囲】
【請求項1】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索する区画ルート探索手段を備え、
前記区画ルート探索手段は、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索手段と、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索手段と、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索手段と、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索手段は、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするナビゲーション装置。
【請求項2】
請求項1に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点の位置に応じて選択した出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項3】
請求項2に記載のナビゲーション装置であって、
前記代表ルートの出口は、前記区画の外縁を形成する複数の辺のいずれかに位置し、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、前記中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項4】
請求項2又は請求項3に記載のナビゲーション装置であって、
前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、前記目的地点の位置に応じた出口として選択する
ことを特徴とするナビゲーション装置。
【請求項5】
請求項1から請求項4までのいずれか1項に記載のナビゲーション装置であって、
前記出発ルート探索手段は、前記出発区画が前記代表設定区画である場合には、代表ルートの出口を退出地点に設定する
ことを特徴とするナビゲーション装置。
【請求項6】
請求項1から請求項5までのいずれか1項に記載のナビゲーション装置であって、
出発地点から目的地点までのルートを前記区画ルート探索手段とは異なる方法で探索する代替ルート探索手段と、
前記区画ルート探索手段により探索された第1のルートを、前記代替ルート探索手段により探索された第2のルートに差し替える差替手段と、
を更に備えることを特徴とするナビゲーション装置。
【請求項7】
請求項6に記載のナビゲーション装置であって、
前記差替手段は、前記第1のルートを前記第2のルートに差し替えるか否かをユーザに選択させる
ことを特徴とするナビゲーション装置。
【請求項8】
請求項6又は請求項7に記載のナビゲーション装置であって、
前記代表ルートと異なる前記第2のルートが走行されたことを条件として、前記第2のルートを前記代表ルートとして登録する登録手段を更に備える
ことを特徴とするナビゲーション装置。
【請求項9】
複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索するルート探索方法であって、
出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索ステップと、
出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索ステップと、
目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索ステップと、
を備え、
前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、
前記中間ルート探索ステップでは、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定する
ことを特徴とするルート探索方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate


【公開番号】特開2013−113609(P2013−113609A)
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願番号】特願2011−257665(P2011−257665)
【出願日】平成23年11月25日(2011.11.25)
【出願人】(000004260)株式会社デンソー (27,639)
【Fターム(参考)】