(57)【特許請求の範囲】
【請求項１】
利用者によって優先モードとして有料道路優先モードが設定された場合に有料道路を優先的に使用した目的地までの経路を探索し、利用者によって優先モードとして非有料道路優先モードが設定された場合に非有料道路を優先的に使用した目的地までの経路を探索する経路探索装置であって、
利用者の探索した経路からの逸脱を検知する監視手段と、
利用者の経路からの逸脱が検知された場合に、探索モードとして、現在位置から前記目的地までの経路を最初から探索する全探索モード、或いは、現在位置から元の経路に戻るための部分的な経路を探索し、該部分的な経路と元の経路とを連結するリルートモードのうち何れか一方を設定し、さらに、前記優先モードを更新するモード更新手段と、
更新された前記優先モード、及び、設定された前記探索モードで、現在位置から前記目的地までの経路を再探索する再探索手段と、を有し、
前記モード更新手段は、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、或いは、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合には、前記優先モードを有料道路優先とし、さらに、前記探索モードをリルートモードとし、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、前記優先モードを有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードをリルートモードとすること
を特徴とする経路探索装置。
【請求項２】
請求項１記載の経路探索装置であって、
前記モード更新手段は、
逸脱後に位置する道路がランプであり、逸脱前に位置したランプ以外の道路のうち最新のものが有料道路であり、かつ、前記優先モードが有料道路優先モードである場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードを全探索モードとし、
逸脱後に位置する道路がランプであり、逸脱前に位置したランプ以外の道路のうち最新のものが有料道路であり、かつ、前記優先モードが非有料道路優先モードである場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードをリルートモードとし、
逸脱後に位置する道路がランプであり、逸脱前に位置したランプ以外の道路のうち最新のものが非有料道路であり、かつ、前記優先モードが有料道路優先モードである場合、前記優先モードを有料道路優先とし、さらに、前記探索モードをリルートモードとし、
逸脱後に位置する道路がランプであり、逸脱前に位置したランプ以外の道路のうち最新のものが非有料道路であり、かつ、前記優先モードが非有料道路優先モードである場合、前記優先モードを有料道路優先とし、さらに、前記探索モードを全探索モードとすること
を特徴とする経路探索装置。
【請求項３】
経路を探索する方法であって、
利用者によって優先モードとして有料道路優先モードが設定された場合に有料道路を優先的に使用した目的地までの経路を探索し、利用者によって優先モードとして非有料道路優先モードが設定された場合に非有料道路を優先的に使用した目的地までの経路を探索するステップと、
利用者の探索した経路からの逸脱を検知するステップと、
利用者の経路からの逸脱が検知された場合に、探索モードとして、現在位置から前記目的地までの経路を最初から探索する全探索モード、或いは、現在位置から元の経路に戻るための部分的な経路を探索し、該部分的な経路と元の経路とを連結するリルートモードのうち何れか一方を設定し、さらに、前記優先モードを更新する更新ステップと、
更新された前記優先モード、及び、設定された前記探索モードで、現在位置から前記目的地までの経路を再探索する再探索ステップとを有し、
前記更新ステップは、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、或いは、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合には、前記優先モードを有料道路優先とし、さらに、前記探索モードをリルートモードとし、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、前記優先モードを有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードをリルートモードとすること
を特徴とする経路探索方法。
【請求項４】
電子計算機によって読み取られ実行されるプログラムを格納した記憶媒体であって、
前記プログラムは、
利用者によって優先モードとして有料道路優先モードが設定された場合に有料道路を優先的に使用した目的地までの経路を探索し、利用者によって優先モードとして非有料道路優先モードが設定された場合に非有料道路を優先的に使用した目的地までの経路を探索するステップと、
利用者の探索した経路からの逸脱を検知するステップと、
利用者の経路からの逸脱が検知された場合に、探索モードとして、現在位置から前記目的地までの経路を最初から探索する全探索モード、或いは、現在位置から元の経路に戻るための部分的な経路を探索し、該部分的な経路と元の経路とを連結するリルートモードのうち何れか一方を設定し、さらに、前記優先モードを更新する更新ステップと、
更新された前記優先モード、及び、設定された前記探索モードで、現在位置から前記目的地までの経路を再探索する再探索ステップと、を前記電子計算機に実行させ、
前記更新ステップは、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、或いは、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合には、前記優先モードを有料道路優先とし、さらに、前記探索モードをリルートモードとし、
前記優先モードが有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が有料道路である場合、前記優先モードを有料道路優先とし、さらに、前記探索モードを全探索モードとし、
前記優先モードが非有料道路優先モードである場合において、逸脱前に位置した道路が有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、又は、逸脱前に位置した道路が非有料道路であり、かつ、逸脱後に位置する道路が非有料道路である場合、前記優先モードを非有料道路優先とし、さらに、前記探索モードをリルートモードとすること
を前記電子計算機に実行させるプログラムであることを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自動車に搭載されるナビゲーション装置などにおいて設定された目的地までの経路を探索する技術に関するものである。
【０００２】
【従来の技術】
自動車に搭載されるナビゲーション装置では、道路地図データに基づいて、設定された出発地から目的地までの推奨される経路を探索し、利用者に提示する経路探索の技術が既に実用化されている。
【０００３】
また、このような推奨経路探索は、たとえば、ダイクストラ法と呼ばれる技術などによって、出発地から目的地までの間の取り得る経路のうち、コストが最小となるを経路を探索することにより行われている。ここで、このような経路のコストとしては、経路の総距離などを用いることが多い。
【０００４】
さらに、近年では、ナビゲーション装置において、利用者の希望する条件により適合する経路を探索する技術も実用化されている。たとえば、利用者の希望に応じて、有料道路を優先的に使用した経路や、逆に、有料道路以外の道路を優先的に使用した経路を探索するナビゲーション装置が実用化されている。ここで、このような条件付きの経路探索は、たとえば、ダイクストラ法において、有料道路のコストを、他の道路より小さくもしくは大きくなるように設定したり、有料道路を含む経路を探索の対象から除外することにより実現できる。
【０００５】
また、ナビゲーション装置において、自動車がナビゲーション装置を用いて探索した経路をはずれてしまった時に、その時点の現在位置から目的地までの経路を再探索する技術も実用化されている。ここで、このような技術には、自動車の現在位置が経路上をはずれた時に現在位置から目的地までの経路を初めから探索するものと、自動車の現在位置が経路上をはずれた時に現在位置から元の経路に戻る部分的な経路を探索し、この部分的な経路と、自動車がはずれてしまった元の経路の、探索した部分的な経路との連結点より目的地側の部分と結合して目的地までの経路とするものとが含まれる。
【０００６】
【発明が解決しようとする課題】
利用者の希望する条件により適合する経路を探索する技術と、前記自動車がナビゲーション装置を用いて探索した経路をはずれてしまった時に、その時点の現在位置から目的地までの経路を再探索する技術とを共に用いる場合には次のような不具合が生じてしまう。
【０００７】
たとえば、利用者が有料道路を優先的に使用した経路を希望して経路を探索した場合を考える。この場合、自動車が経路上の有料道路をはずれてしまった時に現在位置から目的地までの経路を初めから探索する技術では、再度、有料道路を優先的に使用した経路が探索され、現在位置から元の経路に戻る部分的な経路を探索する技術では、はずれてしまった元の経路を使用する経路が探索されることになる。
【０００８】
しかし、これでは、たとえば、経路中の有料道路が渋滞であったために利用者が意図的に有料道路をはずれた場合でも、また、渋滞中の有料道路を使用する経路が探索されてしまう可能性が高い。そして、この場合には、探索された経路は、利用者の意図に反するものとなることになる。
【０００９】
そこで、本発明は、利用者が希望した有料道路／非有料道路の優先的使用の条件に従って探索した経路を、自動車が逸脱した時に、その時点の現在位置から目的地までの経路を、利用者のその時点の意図により適合するように再探索することを課題とする。
【００１０】
【課題を解決するための手段】
前記課題達成のために本発明は、たとえば、利用者によって優先モードとして有料道路優先モードが設定された場合に有料道路を優先的に使用した目的地までの経路を探索し、利用者によって優先モードとして非有料道路優先モードが設定された場合に非有料道路を優先的に使用した目的地までの経路を探索する経路探索装置であって、
利用者の探索した経路からの逸脱を検知する監視手段と、
利用者の経路からの逸脱が検知された場合に、逸脱後に位置する道路が有料道路であったか否かと、逸脱前に位置した道路が有料道路であったか否かとに応じて、前記優先モードを有料道路優先モードもしくは非有料道路優先モードに更新するモード更新手段と、
更新された優先モードで、現在位置から目的地までの経路を再探索する再探索手段とを有することを特徴とする経路探索装置を提供する。
【００１１】
このような経路探索装置によれば、利用者が希望した有料道路／非有料道路の優先的使用の条件に従って探索した経路を、利用者が逸脱した時に、逸脱後に位置する道路が有料道路であったか否かと、逸脱前に位置した道路が有料道路であったか否かとより利用者の意図をくみ取って、利用者のその時点の意図により適合するように、その時点の現在位置から目的地までの経路を、再探索することができる。
【００１２】
【発明の実施の形態】
以下、本発明に係る経路探索装置の一実施形態を、車載用ナビゲーション装置への適用を例にとり説明する。
【００１３】
図１に、本実施形態に係るナビゲーション装置の構成を示す。
【００１４】
図中、１はマイクロプロセッサやメモリから構成される処理装置、２は表示装置、３は地図データが記憶されたCD-ROMなどの記憶媒体のアクセスを担うドライブ装置、４は利用者の指示の入力を受け付ける入力装置、５は車速センサや方位センサやＧＰＳ受信機などから構成されるセンサ装置である。
【００１５】
このような構成において、処理装置１は、センサ装置５の方位センサから入力する車両の進行方位や車速センサから入力する車速やＧＰＳ受信機から入力する測定現在位置などに基づいて車両の現在位置を算出したり、入力装置５を介して利用者より入力された目的地と、入力装置５を介して利用者より入力されたもしくはセンサ装置５からの入力より算出した現在位置に基づいて、目的地までの推奨経路の算出などを行う。
【００１６】
また、処理装置１は、算出した現在位置や、車両の進行方位や、入力装置５を介して利用者より指定された内容に基づき、ドライブ装置３を制御し地図データを読み出し、当該地図データの表す地図を表示装置２に表示する。地図の表示は、たとえば、算出した現在位置周辺の領域の地図を所定の縮尺で表示したり、利用者より指定された地区の地図を所定のもしくは指定された縮尺で表示したり、現在位置から目的地までの推奨経路を含む範囲の領域の地図を適当な縮尺で、推奨経路と共に表示することにより行う。また、この際、地図上に車両の現在位置と進行方位を表すマークを地図に重畳して表示したりする。
【００１７】
次に、ドライブ装置３に装着されるCD-ROMなどの記憶媒体に記録された地図データを図２に示す。
【００１８】
図示するように、地図データは、各道路毎に設けられた道路データより構成される。また、道路データは、道路情報と、リンク情報より構成される。
【００１９】
道路情報には、道路を一意に表す道路番号と、道路の名称を表す道路名称と、その道路の種別（有料道路、国道、県道、ランプ）などを表す道路種別と、その他の属性情報を表すその他道路属性が含まれる。
【００２０】
また、リンク情報には、道路を構成する各リンクについて設けられた、リンクの情報を表すリンクデータが含まれる。ここで、リンクは、道路の形状位置を集合として近似する直線の線分である。リンクデータは、その両端の点である２つのノードについて、それぞれ、ノードを一意に示すノード番号と、ノードの位置を表すノード座標と、そのノードとリンクを介して連結する全てのノードのノード番号のリストである隣接ノード番号リストを含む。ここで、リンク同士の連結は必ずノードにおいて行われる。たとえば、十字路では、その中心にノードが設けられ、この中心に設けられたノードに４つのリンクが連結する。そして、この場合、中心に設けられたノードの隣接ノード番号リストには、自ノードに連結する４つのリンクの他端の４つのノードのノード番号が記述される。
【００２１】
以下、このような地図データを用いて処理装置１が行う処理について説明する。
【００２２】
まず、処理装置１は、入力装置５を介して利用者より、有料道路優先モードと非有料道路優先モードのうちのいずれかの選択を受け付け優先モードとして記憶する。そして、入力装置５を介して利用者より、出発地と目的地と経路探索の指示を受け付けると、有料道路優先モードが優先モードとして記憶されている場合には、地図データを参照し、有料道路を優先的に使用した出発地から目的地までの経路を探索し探索した経路を記憶する。非有料道路優先モードが優先モード記憶されている場合には、地図データを参照し、非有料道路を優先的に使用した出発地から目的地までの経路を探索し探索した経路を記憶する。
【００２３】
その後、処理装置１は、図３に示す処理を行う。
【００２４】
すなわち、現在位置と記憶した経路とを照合し、自動車が記憶した経路から逸脱していないかを監視し（ステップ３１）、逸脱している場合には、記憶した優先モードを読み出し（ステップ３２）、道路データを参照して現在位置が位置するリンクが属する道路の道路種別を調べる（ステップ３３）。また、走行履歴と道路データを参照して経路から逸脱する前に走行したリンクが属する道路の道路種別とを調べる（ステップ３４）。なお、このために、処理装置１は、図３に示した処理とは別に走行の履歴を走行履歴として記憶する処理を行うようにする。
【００２５】
そして、これらより優先モードを決定すると共に、また、探索モードをリルートモードか全探索モードのいずれかに決定する（ステップ３５）。
【００２６】
この決定は、下表に従って行う。
【００２７】
【表１】
0004189054.tif 000002
【００２８】
ただし、現在位置が位置するリンクが属する道路の道路種別と経路から逸脱する前に走行したリンクの道路種別の双方がランプである場合には、最後に走行したランプ以外のリンクが属する道路の道路種別に応じ、表２に従って、現在位置が位置するリンクが属する道路の道路種別と、経路から逸脱する前に走行したリンクの道路種別を変更した後、表１に従って優先モードと探索モードを決定する。
【００２９】
【表２】
0004189054.tif 000003
【００３０】
そして、決定した優先モードを探索モードに従って、現在位置から目的地までの経路を再探索する（ステップ３６）。
【００３１】
この再探索では、決定した探索モードが全探索モードのときは、現在位置から目的地までの経路を初めから探索する。また、決定した探索モードがリルートモードのときは、現在位置から元の経路に戻る部分的な経路を探索し、この部分的な経路と、自動車がはずれてしまった元の経路の、探索した部分的な経路との連結点より目的地側の部分と結合して目的地までの経路とする。
【００３２】
また、いずれの探索モードの場合も、決定された優先モードが有料道路優先モードの場合には、有料道路を優先的に使用した経路を探索する。また、決定された優先モードが非有料道路優先モードの場合には、非有料道路を優先的に使用した経路を探索する。
【００３３】
そして、記憶している経路と優先モードを、探索した経路と、決定した優先モードに更新する（ステップ３７）。
【００３４】
結果、記憶された経路に合わせて表示装置上の経路の表示が更新される。
【００３５】
以上、本発明の実施形態について説明した。
【００３６】
本実施形態によれば、表１に示されるように、有料道路優先モードが設定されている場合でも、経路上の有料道路から経路外の非有料道路に利用者が自動車を進めたことにより経路を逸脱した場合には、利用者が有料道路を使用しない別の経路を進むことを意図しているものとして、非有料道路優先モードかつ全探索モードで経路を再探索する。したがって、経路を逸脱した時点で利用者の意図に沿って、優先的に非有料道路を使用する目的地までの新たな経路を探索することができる。また、これとは、逆に、経路上の非有料道路優先モードが設定されている場合でも、経路上の非有料道路から経路外の有料道路に利用者が自動車を進めたことにより経路を逸脱した場合には、利用者が有料道路を使用する別の経路を進むことを意図しているものとして、有料道路優先モードかつ全探索モードで経路を再探索する。したがって、経路を逸脱した時点で、利用者の意図に沿って、優先的に有料道路を使用する目的地までの新たな経路を探索することができる。
【００３７】
また、非有料道路優先モードが設定されている場合でも、経路上の有料道路から経路外の有料道路に利用者が自動車を進めたことにより経路を逸脱した場合には、利用者がそのまま経路外の有料道路を使用した経路を進むことを意図しているものとして、有料道路優先モードかつ全探索モードで優先的に有料道路を使用する目的地までの他の有料道路を使用した新たな経路を探索することができる。
【００３８】
また、これら以外の場合には、利用者が誤って経路を逸脱したものとして、リルートモードで元の経路に戻る経路を探索する。
【００３９】
したがって、本実施形態によれば、利用者の意図に沿って、優先的に有料道路を使用する経路を探索することができる。
【００４０】
また、さらに、表２に示されるように、本実施形態では、経路を逸脱した直後の道路の道路種別がランプである場合でも、最後に走行した経路上のランプ以外の道路の道路種別に応じて、ランプを非有料道路または有料道路と見なして、表１に従って優先モードと探索モードを決定する。したがって、有料道路から非有料道路もしくは非有料道路から有料道路に向かう形態で経路を逸脱する場合に、有料道路と非有料道路間に存在するランプに自動車進んだ時点で、早期に再探索を行うことができる。
【００４１】
なお、処理装置１は、CPUやメモリや適当なOSを備えた電子計算機であってよく、この場合、処理装置１が行う前記各処理は、CPUが、各処理の手順を記述したプログラムを実行することにより実現される。また、この場合、これらのプログラムはCD-ROMなどの記憶媒体を介して、処理装置１に供給するようにしてもよい。
【００４２】
また、本実施形態を簡易化して適用するする場合には、再探索時の優先モードを、その時点の優先モードを考慮せずに、経路からの逸脱後に位置するリンクが属する道路の道路種別と、経路からの逸脱前に走行したリンクが属する道路の道路種別とからのみ定めるようにしてもよい。この場合は、たとえば、経路からの逸脱後に位置するリンクが属する道路の道路種別が有料道路であって、経路からの逸脱前に走行したリンクが属する道路の道路種別が非有料道路である場合には、無条件に非有料道路優先モードとし、経路からの逸脱後に位置するリンクが属する道路の道路種別が非有料道路であって、経路からの逸脱前に走行したリンクが属する道路の道路種別が有料道路である場合には、無条件に有料道路優先モードとするようにし、他の場合は、優先モードを変更しないようにする。
【００４３】
【発明の効果】
以上のように本発明によれば、利用者が希望した有料道路／非有料道路の優先的使用の条件に従って探索した経路を、自動車が逸脱した時に、その時点の現在位置から目的地までの経路を、利用者のその時点の意図により適合するように再探索することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図である。
【図２】本発明の実施形態に係る地図データの構成を示す図である。
【図３】本発明の実施形態に係るナビゲーション装置の動作を示すフローチャートである。
【符号の説明】
１  処理装置
２  表示装置
３  ドライブ装置
４  入力装置
５  センサ装置
【図１】
0004189054.tif 000004
【図２】
0004189054.tif 000005
【図３】
0004189054.tif 000006