経路誘導装置及び経路誘導方法
【課題】移動体が誘導経路から逸脱した場合に、再探索を極力行うことなく、誘導経路を迅速に変更すると共に、大きく迂回又は後戻りしないように誘導経路を変更する経路誘導装置を提供する。
【解決手段】本発明の経路誘導装置は、出発地から目的地に至る複数の経路を生成して、複数の経路上の交点を記憶し、複数の経路の中の第１経路を当初の誘導経路として設定し、移動体が誘導経路から逸脱した場合に、移動体が、前記複数の経路の１つであって、第１経路と異なる第２経路上に位置していると、前記第１経路を除く複数の経路の中の１又は２以上の経路を利用して、移動体が第１経路に復帰可能か否かを判断し、移動体が第１経路に復帰可能な場合、上記の１又は２以上の経路を利用して第１経路に復帰する経路を誘導経路として設定し、移動体が第１経路に復帰不可能な場合、上記の１又は２以上の経路を利用して目的地に至る経路を誘導経路として設定する。
【解決手段】本発明の経路誘導装置は、出発地から目的地に至る複数の経路を生成して、複数の経路上の交点を記憶し、複数の経路の中の第１経路を当初の誘導経路として設定し、移動体が誘導経路から逸脱した場合に、移動体が、前記複数の経路の１つであって、第１経路と異なる第２経路上に位置していると、前記第１経路を除く複数の経路の中の１又は２以上の経路を利用して、移動体が第１経路に復帰可能か否かを判断し、移動体が第１経路に復帰可能な場合、上記の１又は２以上の経路を利用して第１経路に復帰する経路を誘導経路として設定し、移動体が第１経路に復帰不可能な場合、上記の１又は２以上の経路を利用して目的地に至る経路を誘導経路として設定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索をして生成された誘導経路に沿って、自動車等の移動体を目的地に誘導する経路誘導装置及び経路誘導方法に関する。
【背景技術】
【０００２】
周知のように、カーナビゲーション装置に代表される経路誘導装置は、地図情報を参照して、出発地から目的地に至る経路を探索し、その結果得られた誘導経路に沿って、移動体を目的地に誘導する装置である。移動体の移動中に、移動体の現在位置及び誘導経路と共に地図が表示手段に表示されて、ユーザは、その地図を参照しながら、誘導経路に沿って移動体を進める。工事による通行止めや渋滞などの道路事情等によって、移動体が誘導経路を逸脱する事態が往々にしてあり得ることから、一般的な経路誘導装置は、所謂リルート機能を具えている。リルート機能とは、誘導経路からの移動体の逸脱を検知又は判断し、現在位置から目的地に至る経路を再探索して(通常、当初の誘導経路に移動体を戻すような経路を再探索して)誘導経路を変更又は更新する機能である。
【０００３】
経路の再探索を行うためには、地図情報を再度読み出す必要があることから、移動体が誘導経路を逸脱してから再探索が完了するまでに、ある程度の時間を要する。これでは、移動体の逸脱後に、新たな誘導経路に沿って移動体の誘導を行うことは困難である。この問題を解決するために、幾つかの経路誘導装置が提供されており、例えば、特開２０００−３０４５６２公報に開示されたナビゲーションシステムは、誘導経路上のある分岐点を移動体が通過する前に、その分岐点を始点として目的地に至る予備経路を求めておいて、移動体がその分岐点から誘導経路を逸脱すると、予備経路の中から適切な予備経路を選択して、新たな誘導経路として採用する。これによって、移動体が誘導経路から逸脱すると、誘導経路が直ちに更新されることになる。
【０００４】
【特許文献１】特開２０００−３０４５６２公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特開２０００−３０４５６２公報に開示されたナビゲーションシステムでは、分岐点間を移動体が移動する際に、経路探索が必ず行われることから、例えば、大都市の道路を移動体が移動する場合には、経路探索が頻繁に行われる事態が起こり得る。一般的な経路誘導装置では、ダイクストラ法又はその改良方法に基づいたアルゴリズムが用いられていることから、経路探索にかなりの演算処理が必要とされる。従って、上記公報に開示されたナビゲーションシステムのような構成を採用すると、経路誘導装置のその他の機能に負担が及んでしまう。さらに、分岐点間の間隔や移動体の移動速度は様々であるから、移動体が分岐点に到着するまでに予備経路の探索が終わっていない事態も起こり得る。また、従来の経路誘導装置では、経路の再探索が行われると、逸脱した誘導経路に移動体を戻すために大きく迂回したり、又は出発地に向かって大きく後戻りするような経路が、かなりの頻度で生成される問題がある。
【０００６】
本発明は、上記の問題を解決するものであり、移動体が誘導経路から逸脱した場合に、再探索を極力行うことなく誘導経路を迅速に変更すると共に、大きく迂回又は後戻りしないように誘導経路を変更する経路誘導装置及び経路誘導方法を提供する。
【課題を解決するための手段】
【０００７】
本発明の経路誘導装置は、誘導経路に沿って目的地まで移動体を誘導する経路誘導装置において、出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶し、前記複数の経路の中の第１経路を当初の誘導経路として設定し、前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記移動体が、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記第１経路に復帰可能か否かを判断し、前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定し、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定することを特徴とする。
【０００８】
さらに、本発明の経路誘導装置は、前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出し、前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する。
【０００９】
さらに、本発明の経路誘導装置は、前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断し、前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定し、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する。
【００１０】
本発明の経路誘導方法は、誘導経路に沿って目的地まで移動体を誘導する経路誘導方法において、出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶する工程と、前記複数の経路の中の第１経路を当初の誘導経路として設定する工程と、前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定する工程と、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定する工程とを含むことを特徴とする。
【００１１】
さらに、本発明の経路誘導方法は、前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出する工程と、前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する工程とを含む。
【００１２】
さらに、本発明の経路誘導方法は、前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定する工程と、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する工程とを含む。
【発明の効果】
【００１３】
本発明では、当初の誘導経路として設定される経路を含めて、出発地から目的地に至る複数の経路を予め生成しておき、移動体が誘導経路から逸脱した場合に、移動体が複数の経路の何れかの経路上にあると、それら複数の経路を利用して誘導経路を新たに設定する。予め得られた経路を利用して誘導経路を設定することから、地図情報を記録媒体から読み出して再探索を行うことなく、誘導経路が迅速に変更される。また、本発明によれば、出発地から目的地に至る複数の経路を利用して、より具体的には部分的に組み合わせて、移動体の現在位置から目的地に至る誘導経路を設定することから、大きく迂回又は後戻りするような誘導経路が設定される可能性は非常に少ない。
【００１４】
また、本発明では、移動体が誘導経路から逸脱した場合に、移動体が複数の経路の何れかの経路上にないと、移動体の現在位置とそれに最も近い交点間の距離と、移動体の現在位置と目的地間の距離とを比較する。そして、前者が後者よりも短い場合、移動体の現在位置から最も近い交点に至る経路が生成されると共に、その経路と、予め生成された複数の経路を利用した経路であって、最も近い交点から目的地に至る経路とで誘導経路が構成される。これによって、必要以上に再探索を行うことなく誘導経路が変更されて、さらに、大きく迂回又は後戻りするような誘導経路が生成される可能性が低減される。
【発明を実施するための最良の形態】
【００１５】
以下、自動車用の車載式ナビゲーション装置(以下、「ナビゲーション装置」と称する)に本発明を適用した実施例について、図を用いて説明する。図１は、ナビゲーション装置(1)のブロック図である。本ナビゲーション装置(1)は、該装置(1)が搭載されている車両の現在位置や方位等を決定する位置検出手段と、地図情報等を記録する記録手段と、記録手段に記録された情報を用いた経路探索、誘導経路に沿って車両を誘導するために必要な処理(例えば、誘導用の画像データや音声データの作成)、及び装置(1)の統括的な制御等を行う制御手段と、車両の現在位置とその周囲の地図等が示された誘導用画面や各種設定画面等を表示する表示手段と、誘導用音声を発生する音声出力手段と、ユーザが装置(1)に各種指示を行うための操作手段とを具えている。
【００１６】
位置検出手段は、ＧＰＳ(Global Positioning System)衛星から送信されるＧＰＳ信号をＧＰＳアンテナ(3)を介して受信して、受信したＧＰＳ信号から車両の現在位置(例えば、緯度及び経度)を特定するＧＰＳ受信部(5)を含んでいる。また、位置検出手段は、ジャイロスコープ(7)及び車速センサ(9)と、これらから送られた信号を処理して車両の方位及び速度を特定するジャイロマイクロコンピュータ(以下、マイクロコンピュータを「マイコン」と称する)(11)を含んでいる。ナビゲーション装置(1)が車両の経路誘導動作を行っている際、ＧＰＳ受信部(5)及びジャイロマイコン(11)は、車両の位置、方位及び速度を決定し、それらの情報を制御手段に送ることを周期的又は定期的に行う。
【００１７】
記録手段は、地図情報等を記録した記録媒体(13)と、制御手段からの指示に基づいて、記録媒体(13)から情報を読み出すドライバ(15)とを含んでいる。記録媒体(13)には、ＣＤ−ＲＯＭ、ＤＶＤ、ＨＤ、又はＩＣメモリ等が用いられる。地図情報は、地理的領域が所定の大きさのブロックに区分けされた形態で記録媒体(13)に記録されている。各ブロックに係るデータには、そのブロックに含まれる道路のノード及びリンクに関するデータ、コンビニエンスストアやガソリンスタンド等の施設の位置データ及び種別データ等、及びそのブロックの地図を表示手段に表示するために用いるデータ等が含まれている。
【００１８】
ノードは、道路の交差点、分岐点、合流点、終点、及びブロックにおける道路の端点に対応して設けられる。各ブロックに係るデータは、そのブロックに含まれる各ノードについて、そのノードのＩＤ番号と、そのノードの位置(例えば、緯度及び経度)と、そのノードの属性(例えば、有料道路の入口又は出口)と、そのノードに接続するリンクのＩＤと、そのノードに隣接するノードのＩＤ番号とを含んでいる。
【００１９】
また、リンクは、ノード間を繋ぐ道路の一区間に対応しており、通常、向きを持っている。各ブロックに係るデータは、そのブロックに含まれる各リンクについて、そのリングのＩＤ番号と、そのリンクの始端ノード及び終端ノードのＩＤ番号と、そのリンクの道路の種別(例えば、有料道路や国道)と、そのリンクの距離(長さ)、そのリンクに接続するリンクのＩＤと、経路探索処理で参照されるリンクコストとを含んでいる。
【００２０】
制御手段には、ＣＰＵ(17)、ＲＡＭ(19)、ＲＯＭ(21)、フラッシュメモリ(23)や図示を省略したローカルバス等を含む制御マイコン(25)が用いられている。ＲＯＭ(21)には、カーナビゲーション装置(1)の各種制御及び処理を実行するためのプログラム及びパラメータ等が記憶されている。経路探索動作や経路誘導動作を行うためのプログラムなど、更新される可能性があるプログラム及びパラメータ等は、フラッシュメモリ(23)に記憶される。これらのプログラムはＣＰＵ(17)により実行される。また、ＲＡＭ(19)は、経路探索動作や経路誘導動作にて読み出された地図情報や演算結果などの一時的なデータの記憶に用いられる。
【００２１】
表示手段は、描画ＩＣ(27)と、液晶表示装置(以下、「ＬＣＤ」と称する)(29)と、ＬＣＤＩ/Ｆ(31)とを含んでいる。経路探索結果の表示画面、経路誘導動作中に表示される誘導用画面や各種設定画面等を表示する指示が制御マイコン(25)から送られると、描画ＩＣ(27)は、その指示に基づいて画像データを作成して、それら画面を、ＬＣＤＩ/Ｆ(31)を介してＬＣＤ(29)に表示する。
【００２２】
音声出力手段は、デジタルアナログコンバータ(以下、「ＤＡＣ」と称する)(33)と、アンプ(35)と、スピーカ(37)とを含んでいる。制御手段は、ユーザを誘導経路に沿って案内する案内音声に係るデジタル音声信号を、経路誘導動作中に適宜作成して、ＤＡＣ(33)に送る。デジタル音声信号は、ＤＡＣ(33)にてアナログ音声信号に変換されてアンプ(35)に送られる。そして、アナログ音声信号はアンプ(35)にて増幅されて、スピーカ(37)から案内音声が出力される。
【００２３】
操作手段は、ナビゲーション装置(1)の筐体(図示せず)に設けられた各種操作キー(39)と、ＬＣＤ(29)上に配置されるタッチパネル(41)と、図示を省略したリモートコントローラ(以下、「リモコン」と称する)と、リモコンから送られる赤外線信号を受信するリモコン受光部(43)と、キーマイコン(45)とを含んでいる。操作キー(39)が押されると、キーマイコン(45)は、押された操作キー(39)を判別して、それに応じた動作コマンドを制御マイコン(25)に送る。また、キーマイコン(45)は、ＬＣＤ(29)に設定画面等が表示されている状態にて、タッチパネル(41)が押された領域を判別して、操作に対応した動作コマンドを制御マイコン(25)に送る。リモコン受光部(43)は、受光した赤外線信号を電気信号に変換及び復調してキーマイコン(45)に送り、キーマイコン(45)は、送られた信号から特定した動作コマンドを制御マイコン(25)に送る。
【００２４】
次に、本実施例のナビゲーション装置(1)が行う経路探索動作について説明する。図２は、経路探索動作の概要を示すフローチャートである。経路探索動作が開始されると、まず、制御マイコン(25)は、目的地設定画面をＬＣＤ(29)に表示させる(Ｓ１)。ユーザが、操作キー(39)やリモコン等を操作して目的地を入力すると、制御マイコン(25)は、それらの位置を特定して、ＲＡＭ(19)に記憶する。ナビゲーション装置(1)では、種々の手順で、目的地を設定することが可能になっている。例えば、記録媒体(13)には、住所や名称等の目的地に関する情報と、目的地の位置とが対応づけられた検索用データベースが記録されており、ユーザが目的地に関する情報を入力すると、検索用データベースが参照されて、目的地の位置が特定される。また、目的地設定画面が表示されると、ＧＰＳ受信部(5)から得られた車両の現在位置が特定されて、制御マイコン(25)は、その位置を出発地の位置としてＲＡＭ(19)に記憶する。なお、ナビゲーション装置(1)では、目的地を設定するように出発地を設定することも可能である。
【００２５】
制御マイコン(25)(のＣＰＵ(17))は、出発地及び目的地の設定が完了したか否かを、例えば、操作手段にて設定完了を指示する操作が行われたが否かを判別し(Ｓ２)、設定が完了すると、設定された出発地及び目的地を含む所定の範囲のノードデータ及びリンクデータが記録媒体(13)から読み出されて、制御マイコン(25)のＲＡＭ(19)に記憶される(Ｓ３)。本実施例のナビゲーション装置(1)は、複数の探索条件の各々に基づいて経路探索を行って複数の経路を生成する。ステップＳ３の後、ある探索条件が選択されて、その探索条件に基づいて経路探索が行われる(Ｓ４)。
【００２６】
ステップＳ４の経路探索処理では、ダイクストラ法又はその改良法に基づいたアルゴリズムに基づいて、出発地に最も近いノード又は出発地のノード(以下、「出発地ノード」と称す)から、目的地に最も近いノード又は目的地のノード(以下、「目的地ノード」と称す)までの経路が探索される。制御マイコン(25)は、ステップＳ３にて設定された条件に基づいて、読み出されたリンクデータのリンクコストを参照して、評価コストが最も低い経路を生成する。生成された経路は、リンク列で表現されて、そのデータはＲＡＭ(19)に記憶される。
【００２７】
本実施例のナビゲーション装置(1)では、例えば、有料道路優先、一般道路優先及び距離優先の３つの探索条件の各々に基づいて経路が探索される。ステップＳ４の後、全ての探索条件について経路探索処理が行われたか否かが判断されて(Ｓ５)。残りの探索条件がある場合は、探索条件を変えて再度ステップＳ４が行われる。このように探索条件を変えてステップＳ４が繰り返されて、全ての探索条件について経路探索処理が行われた後、ＲＡＭ(19)に記憶されている経路データが参照されて、生成された複数の経路上にある交点、つまり交点ノードが求められる(Ｓ６)。そして、ステップＳ６では、交点ノードに該当するノードについて、その旨が、ＲＡＭ(19)に記憶されているノードデータに登録される(交点ノードに該当する全ノードＩＤが、ノードデータとは別個に記憶されてもよい)。ここで、交点とは、生成された複数の経路に含まれる２以上の経路が交差する交差点、又は、複数の経路に含まれる２以上の経路が重なった共通区間の端点(道路の合流点又は分岐点に相当する)である。
【００２８】
ステップＳ６の後、ステップＳ４を繰り返して得られた複数の経路がＬＣＤ(29)に表示される(Ｓ７)。ユーザは、ステップＳ７にて表示された画面を見て、(当初の)誘導経路として採用する経路を選択する(Ｓ８)。ステップＳ８にてある１つの経路が選択されると、制御マイコン(25)は、その経路を誘導経路として設定する(Ｓ９)。
【００２９】
図２に示す経路探索動作が完了すると、ユーザが操作キー(39)等の操作手段を用いて指示することで、ナビゲーション装置(1)は、誘導経路に沿って車両を目的地に誘導する経路誘導動作を開始する。図３及び図４は、この動作を示すフローチャートである。まず、図３を参照する。経路誘導動作が開始されると、制御マイコン(25)は、ＧＰＳ受信部(5)等を含む位置検出手段を用いて車両の現在位置及び方位等を取得し、得られた位置情報等に基づいて誘導用画面をＬＣＤ(29)に表示し、スピーカ(37)から誘導用音声を出力するなどの誘導処理を行う(Ｓ２１)。誘導用画面では、車両の周囲の地図が車両の現在位置を示す記号と共に示されており、誘導経路を構成する道路がその他の道路と区別されるように描画される。なお、経路誘導動作が開始された際の誘導経路は、図２に示すステップＳ９にて設定された経路である。
【００３０】
誘導処理では、車両の現在位置が定期的又は周期的に取得されて、誘導用画面の更新等が行われる。車両の現在位置が取得されると、制御マイコン(25)によって、車両が誘導経路を逸脱しているか否かが判断される(Ｓ２２)。例えば、車両が、誘導経路から所定の距離以上離れている場合に、制御マイコン(25)は、車両が誘導経路から逸脱していると判断する。ステップＳ２２にて、車両が誘導経路から逸脱していないと判断されると、車両が目的地に到達したか否かが判断される(Ｓ２３)。車両が目的地に到達した場合、経路誘導動作は終了する。また、車両が目的地に到達していない場合、ステップＳ２１が再度行われて、誘導用画面の更新等が行われる。
【００３１】
ステップＳ２２にて、車両が誘導経路から逸脱していると判断された場合、まず、制御マイコン(25)は、取得した車両の現在位置と、ＲＡＭ(19)に記憶されている経路データ等とを参照して、図２に示すステップＳ９にて設定された当初の誘導経路上に車両があるか否かを判断する(Ｓ２４)。当初の誘導経路上に車両がある場合、当初の誘導経路に誘導経路が変更されて(Ｓ２５)、ステップＳ２１の誘導処理が行われる。なお、ステップＳ２５は、誘導経路が当初の誘導経路から変更された場合において機能する。ステップＳ２４にて、車両が当初の誘導経路上にないと判断された場合、制御マイコン(25)は、図２に示す経路探索動作にて生成された複数の経路の中で、車両が、誘導経路として採用されなかった経路の何れかの上に位置するか否かを判断する(Ｓ２６)。
【００３２】
ステップＳ２６にて、車両が誘導経路として採用されなかったある経路上に位置すると判断された場合、図２のステップＳ６で得られた交点ノードに関する情報や経路データ等が参照されて、車両の現在位置と目的地間において、その経路上に交点があるか否かが判断される(Ｓ２７)。交点がない場合、即ち、車両の現在位置から目的地に至る途中で、その経路が他の経路と交わることがない場合、その経路が(又は、車両が位置するリンクの始点ノードから目的地ノードに至る区間が)誘導経路に設定される(Ｓ２８)。そして、ステップＳ２１にて、変更された誘導経路に基づいて誘導処理が行われる。
【００３３】
ステップＳ２７にて、車両が位置する経路について、車両の現在位置と目的地の間に交点があると判断された場合、当初の誘導経路以外の(図２の経路探索動作で得られた)経路の交点間区間(始点及び終点が交点である区間)を利用して、車両の現在位置から当初の誘導経路に復帰できるか否かが判断される(Ｓ２９)。ステップＳ２９にて、当初の誘導経路に復帰できると判断された場合、当初の誘導経路以外のその他の経路の交点間区間を利用して当初の誘導経路に復帰し、車両の現在位置から目的地に至る経路(より具体的には、車両が位置するリンクの始点から目的地ノードに至る経路。以下同様)の中で、評価コストの最も低い経路が選択されて、誘導経路として設定される(Ｓ３０)。
【００３４】
ステップＳ３０では、ＲＡＭ(19)に記憶された経路データやリンクデータ等が参照されて、当初の誘導経路以外のその他の経路の交点間区間と当初の誘導経路の一部との組み合わせにより可能な経路の各々について評価コストが算出されて、誘導経路が選択及び設定される。なお、交点間区間を利用して当初の誘導経路に復帰して、車両の現在位置から目的地に至る経路が１つしかない場合には、評価コストを算出することなく、誘導経路の設定が行われる。評価コストは、図２に示す経路誘導動作において当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ３０の後、変更された誘導経路に基づいて誘導処理が行われる。
【００３５】
ステップＳ２９にて、当初の誘導経路以外の経路の交点間区間を利用して、当初の誘導経路に復帰できないと判断された場合、当初の誘導経路以外の経路の交点間区間を利用して車両の現在位置から目的地に至る経路であって、評価コストが最も低い経路が選択されて、誘導経路として設定される(Ｓ３１)。ステップＳ３１では、当初の誘導経路以外のその他の経路の交点間区間の組み合わせにより可能な経路の各々について評価コストが算出されて、誘導経路が選択及び設定される。車両の現在位置から目的地に至る経路が１つしかない場合には、評価コストを算出することなく、誘導経路の設定が行われる。評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ３１の後、変更された誘導経路に基づいてステップＳ２１の誘導処理が行われる。
【００３６】
ステップＳ２６にて、車両が、当初の誘導経路以外の経路上に位置していないと判断された場合、図４に示す処理が行われる。まず、車両の現在位置やノードデータ等が参照されて、車両の現在位置と車両に最も近い交点間の直線距離が、車両の現在位置と目的地間の直線距離よりも短いか否かが判断される(Ｓ４１)。前者が後者以上である場合、車両の現在位置から目的地に至る経路が探索されて、その結果得られた経路が誘導経路として設定される(Ｓ４２)。その後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。なお、ステップＳ４２における評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。
【００３７】
ステップＳ４１にて、車両の現在位置と車両に最も近い交点間の直線距離が、車両の現在位置と目的地間の直線距離よりも短いと判断された場合、車両の現在位置(のノード又は車両に最も近いノード)から、車両に最も近い交点(ノード)に至る経路が探索される(Ｓ４３)。ステップＳ４３における評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ４３の後、車両に最も近い交点が当初の誘導経路上にあるか否かが判断される(Ｓ４４)。車両に最も近い交点が当初の誘導経路上にある場合、ステップＳ４３で生成された経路と、当初の誘導経路におけるその交点から目的地に至る区間とで構成された経路が、誘導経路として設定される(Ｓ４５)。その後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００３８】
ステップＳ４４にて、車両に最も近い交点が当初の誘導経路上にないと判断された場合、当初の誘導経路以外の(図２の経路探索動作で得られた)経路の交点間区間を利用して、車両に最も近い交点から当初の誘導経路に復帰できるか否かが判断される(Ｓ４６)。ステップＳ４６にて、当初の誘導経路に復帰できると判断された場合、ステップＳ３０とほぼ同様にして、当初の誘導経路以外の経路の交点間区間を利用して当初の誘導経路に復帰し、車両に最も近い交点から目的地に至る経路の中で、評価コストが最も低い経路が選択される。そして、選択された経路とステップＳ４３で生成された経路とを組み合わせた経路が、誘導経路として設定される(Ｓ４７)。ここで、評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。また、ステップＳ４７では、車両に最も近い交点から目的地に至る経路が１つしか存在しない場合、評価コストを算出することなく、その経路が誘導経路として設定される。ステップＳ４７の後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００３９】
ステップＳ４６にて、当初の誘導経路に復帰できないと判断された場合、ステップＳ３１とほぼ同様にして、当初の誘導経路以外の経路の交点間区間を利用して最も近い交点から目的地に至る経路の中で、評価コストが最も低い経路が選択されて、その経路とステップＳ４３で生成された経路とを組み合わせた経路が、誘導経路として設定される(Ｓ４８)。ここで、評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。また、ステップＳ４８では、車両に最も近い交点から目的地に至る経路が１つしか存在しない場合、評価コストを算出することなく、その経路が誘導経路として設定される。ステップＳ４８の後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００４０】
図５(a)乃至図５(e)は、本発明のナビゲーション装置(1)にて経路誘導動作が行われて、出発地から目的地に車両が誘導される一例を示す説明図である。図２に示す経路探索動作にて、探索条件を変えてステップＳ４が繰り返されることによって、出発地ノードＮ1から目的地ノードＮ9に至る３つの経路、即ち経路Ａ、経路Ｂ及び経路Ｃが得られている。経路Ａは、リンク列｛Ｌ1，Ｌ2，Ｌ4．Ｌ7，Ｌ9｝で構成されており、これらの図中にて実線で表されている。経路Ｂは、リンク列｛Ｌ1，Ｌ2，Ｌ6．Ｌ8，Ｌ10，Ｌ11｝で構成されており、これらの図中にて一点鎖線で表されている。経路Ｃは、リンク列｛Ｌ1，Ｌ3，Ｌ5．Ｌ7，Ｌ10，Ｌ11｝で構成されており、これらの図中にて破線で表されている。
【００４１】
図２に示すステップＳ６にて、経路Ａと経路Ｂの共通区間であるリンクＬ2の端点であるノードＮ2及びＮ3と、経路Ａと経路Ｃの共通区間であるリンクＬ7の端点であるノードＮ5と、同じくリンクＬ7の端点であって、経路Ａ、経路Ｂ及び経路Ｃの交差点でもあるノードＮ7と、出発地ノードＮ1及び目的地ノードＮ9とが、交点ノードとして登録されている。また、ステップＳ９では、経路Ａが誘導経路として設定されている。
【００４２】
図３に示す経路誘導動作が開始すると、当初の誘導経路である経路Ａに沿って車両Ｐを誘導するように、ステップＳ２１が行われる。図５(a)は、経路Ａ及び経路Ｂに含まれており、リンクＬ2に対応した区間上を車両Ｐが移動している模様を示している。図５(b)は、交点ノードであるノードＮ3を経由して、誘導経路である経路Ａから車両Ｐが逸脱した模様を示している。図５(b)に示すケースでは、経路Ｂ上に、車両Ｐが位置していることから、図３に示すステップＳ２２、Ｓ２４及びＳ２６の後、ステップＳ２７が行われる。経路Ｂには、車両Ｐの現在位置と目的地の間にて、経路Ａと交わる交点ノードＮ7が存在することから、ステップＳ２７の後、ステップＳ２９が行われる。
【００４３】
ステップＳ２９が行われると、交点ノードＮ7は、当初の誘導経路である経路Ａと交わる交点ノードであるから、経路Ｂを利用して、車両Ｐの現在位置から当初の誘導経路に復帰可能と判断される。ステップＳ２９の後、ステップＳ３０が行われるが、車両Ｐの現在位置から経路Ａに復帰して目的地に至る経路は、経路｛Ｌ6，Ｌ8，Ｌ9｝の１つのみであるので、経路探索が行われることなく、この経路が誘導経路として設定される。そして、経路｛Ｌ6，Ｌ8，Ｌ9｝に沿って車両Ｐを誘導するように、ステップＳ２１の誘導処理が行われる。
【００４４】
図５(c)は、上述のように誘導経路の変更が行われた後、ノードＮ6を通って、誘導経路である経路｛Ｌ6，Ｌ8，Ｌ9｝から車両Ｐが逸脱した模様を示している。このケースでは、ステップＳ２２、Ｓ２４及びＳ２６が行われた後、図４に示すステップＳ４１が行われる。ステップＳ４１では、車両Ｐの現在位置と、この位置に最も近い交点ノードであるノードＮ7との間の直線距離が計算され、さらに、車両Ｐの現在位置と目的地ノードＮ9間の直線距離が計算される。このケースでは、前者が後者よりも短いことから、ステップＳ４１の後、ステップＳ４３が行われる。図５(d)にて、ステップＳ４３が行われて生成された経路｛Ｌ12，Ｌ13｝を点線で示す。
【００４５】
ステップＳ４３が行われた後、ステップＳ４４が行われる。車両Ｐの現在位置に最も近い交点ノードであるノードＮ7は、当初の誘導経路Ａ上にある交点ノードであるので、ステップＳ４４の後ステップＳ４５が行われて、経路｛Ｌ12，Ｌ13，Ｌ9｝が新たな誘導経路として設定される。そして、図５(e)に示すように、この経路に沿って車両Ｐを移動させることで、車両Ｐを目的地に到達させることが可能となる。
【００４６】
図６(a)は、図５(b)と似たケースを示しているが、当初の誘導経路である経路Ａが、リンク列｛Ｌ1，Ｌ2，Ｌ4，Ｌ14｝で構成されており、経路Ｃが、リンク列｛Ｌ1，Ｌ3，Ｌ5，Ｌ7，Ｌ9｝で構成されている点が異なる。ここで、リンクＬ14は、交点ノードＮ5から目的地ノードＮ9に至る区間に対応している。図６(a)に示すケースでは、ステップＳ２２、Ｓ２４、Ｓ２６及びＳ２７が行われた後、車両Ｐが位置している経路Ｂ上に交点ノードＮ7があることから、ステップＳ２９が行われる。さらに、経路Ｂと、交点ノードＮ7にて経路Ｂと交差する経路Ｃとは、交点ノードＮ7以降にて経路Ａと交わることはないので、ステップＳ２９にて、経路Ｂを、又は経路Ｂ及び経路Ｃを利用して、車両Ｐの現在位置から当初の誘導経路に復帰することはできないという判断がなされる。そして、ステップＳ３１にて、経路Ｂを、さらには経路Ｃをも利用して車両Ｐの現在位置から目的地に至る経路の中で、評価コストが最も低い経路が誘導経路として設定される。このケースでは、経路｛Ｌ6，Ｌ8，Ｌ9｝の評価コストと、経路｛Ｌ6，Ｌ8，Ｌ10，Ｌ11｝の評価コストとが比較されて、評価コストが低い経路が誘導経路として設定される。
【００４７】
図６(b)は、上述のように誘導経路が変更された後にノードＮ6を通って車両Ｐが誘導経路から逸脱した模様を示している。このケースでは、図５(c)及び図５(d)について説明したように、ステップＳ４３にて、車両Ｐの現在位置から交点ノードＮ7に至る経路｛Ｌ12，Ｌ13｝が生成される。図６(b)では、交点ノードＮ7は、当初の誘導経路である経路Ａ上にないので、ステップＳ４３及びＳ４４の後、ステップＳ４６が行われる。交点ノードＮ7からは、経路Ｂ及び/又は経路Ｃを利用して経路Ａに復帰することはできないので、ステップＳ４６の後、ステップＳ４８が行われる。ステップＳ４８では、リンクＬ9からなる経路の評価コストと、経路｛Ｌ10，Ｌ11｝の評価コストとが比較されて、これらの中で評価コストが低い方の経路と、経路｛Ｌ12，Ｌ13｝とで構成される経路が誘導経路に設定される。
【００４８】
図７(a)は、図５(b)と似たケースを示しているが、当初の誘導経路である経路Ａが｛Ｌ1，Ｌ2，Ｌ4，Ｌ7，Ｌ10，Ｌ11｝、経路Ｂが｛Ｌ1，Ｌ2，Ｌ6，Ｌ15，Ｌ16，Ｌ11｝、経路Ｃが｛Ｌ1，Ｌ3，Ｌ5，Ｌ17，Ｌ18，Ｌ9｝で構成されている点が異なる。図７(a)にて、ノードＮ7は、経路Ａと経路Ｃの交点ノードであり、ノードＮ8は、経路Ａと経路Ｂの交点ノードであり、ノードＮ11は、経路Ｂと経路Ｃの交点ノードである。
【００４９】
図７(a)に示すケースでは、車両Ｐが交点ノードＮ3を通って、誘導経路である経路Ａから逸脱すると、ステップＳ２２、Ｓ２４、Ｓ２６及びＳ２７が行われた後、ステップＳ２９、さらにはステップＳ３０が行われる。このケースでは、ステップＳ３０にて、経路Ｂの交点間区間である区間｛Ｌ6，Ｌ15｝及びリンクＬ16を利用して経路Ａに戻って目的地に至る経路｛Ｌ6，Ｌ15，Ｌ16，Ｌ11｝の評価コストと、経路Ｂの交点間区間である区間｛Ｌ6，Ｌ15｝と経路Ｃの交点間区間であるリンクＬ18を利用して経路Ａに戻って目的地に至る経路｛Ｌ6，Ｌ15，Ｌ18，Ｌ10，Ｌ11｝の評価コストとが比較されて、評価コストの低い経路が誘導経路として選択される。
【００５０】
図７(b)は、上述のように誘導経路が変更された後にノードＮ6を通って車両誘導経路から逸脱した模様を示している。このケースでは、ステップＳ４３にて、車両Ｐの現在位置から交点ノードＮ11に至る経路(図中に点線で示す)が生成される。交点ノードＮ11は、経路Ａ上にないことから、ステップＳ４３及びＳ４４の後、ステップＳ４６が行われる。交点ノードＮ11以降にて、経路Ｂ及び経路Ｃは、経路Ａと交わっていることから、ステップＳ４６の後、ステップＳ４７が行われる。ステップＳ４７では、経路Ｃの交点間区間であるリンクＬ18を利用して交点ノードＮ11から経路Ａに戻って、目的地に至る経路｛Ｌ18，Ｌ10，Ｌ11｝の評価コストと、経路Ｂの交点間区間であるリンクＬ16を利用して交点ノードＮ11から経路Ａに戻って、目的地に至る経路｛Ｌ16，Ｌ11｝の評価コストとが比較されて、これら経路の中で評価コストの低い方の経路と、ステップＳ４３で生成された経路とで構成される経路が誘導経路として選択される。
【００５１】
本実施例のナビゲーション装置(1)では、図２に示すように探索条件を変えて経路探索を繰り返すことで、出発地から目的地に至る複数の経路を生成しているが、本発明の特徴とする経路誘導動作は、経路誘導動作を行う前に、出発地から目的地に至る複数の経路が予め生成されていれば実行可能であって、これら経路の特性は基本的に問われない。例えば、経路探索動作にて、単一の探索条件で経路探索を行った結果から複数の経路(例えば、誘導経路として設定される評価コストの最も低い最適経路と、最適経路よりも評価コストが低い幾つかの経路)を選んでもよい。この場合だと、図２に示す経路探索動作と、図３及び図４に示す経路誘導動作とにおいて、同一種類の評価コストが用いられる点が好ましい。また、図２に示す経路探索動作において、有料道路優先等の探索条件下で、付加的な条件を変化させることで複数の経路が生成されてもよい。
【００５２】
また、ナビゲーション装置(1)は、必ずしも車載式である必要はなく、その具体的形態は特に限定されない。例えば、上記実施例の機能の一部、例えば経路探索機能が、別個に設けられたサーバ装置で行われて、通信手段を用いて探索結果がサーバ装置からナビゲーション装置に送られてもよい。さらに、本発明は、自動車用のナビゲーション装置に限定されることはなく、移動体用の経路誘導装置に広く適用可能である。
【００５３】
上記実施例の説明は、本発明を説明するためのものであって、特許請求の範囲に記載の発明を限定し、或は範囲を減縮する様に解すべきではない。本発明の各部構成は上記実施例に限らず、特許請求の範囲に記載の技術的範囲内で種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施例であるナビゲーション装置のブロック図である。
【図２】本発明の実施例であるナビゲーション装置の経路探索動作を示すフローチャートである。
【図３】本発明の実施例であるナビゲーション装置の経路誘導動作を示すフローチャートである。
【図４】本発明の実施例であるナビゲーション装置の経路誘導動作を示すフローチャートである。
【図５（ａ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｂ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｃ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｄ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｅ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図６】図６(a)及び図６(b)は、本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図７】図７(a)及び図７(b)は、本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【符号の説明】
【００５５】
(1) カーナビゲーション装置
(5) ＧＰＳ受信部
(13) 記録媒体
(19) ＲＡＭ
(25) 制御マイクロコンピュータ
(29) 液晶表示装置
(41) タッチパネル
【技術分野】
【０００１】
本発明は、経路探索をして生成された誘導経路に沿って、自動車等の移動体を目的地に誘導する経路誘導装置及び経路誘導方法に関する。
【背景技術】
【０００２】
周知のように、カーナビゲーション装置に代表される経路誘導装置は、地図情報を参照して、出発地から目的地に至る経路を探索し、その結果得られた誘導経路に沿って、移動体を目的地に誘導する装置である。移動体の移動中に、移動体の現在位置及び誘導経路と共に地図が表示手段に表示されて、ユーザは、その地図を参照しながら、誘導経路に沿って移動体を進める。工事による通行止めや渋滞などの道路事情等によって、移動体が誘導経路を逸脱する事態が往々にしてあり得ることから、一般的な経路誘導装置は、所謂リルート機能を具えている。リルート機能とは、誘導経路からの移動体の逸脱を検知又は判断し、現在位置から目的地に至る経路を再探索して(通常、当初の誘導経路に移動体を戻すような経路を再探索して)誘導経路を変更又は更新する機能である。
【０００３】
経路の再探索を行うためには、地図情報を再度読み出す必要があることから、移動体が誘導経路を逸脱してから再探索が完了するまでに、ある程度の時間を要する。これでは、移動体の逸脱後に、新たな誘導経路に沿って移動体の誘導を行うことは困難である。この問題を解決するために、幾つかの経路誘導装置が提供されており、例えば、特開２０００−３０４５６２公報に開示されたナビゲーションシステムは、誘導経路上のある分岐点を移動体が通過する前に、その分岐点を始点として目的地に至る予備経路を求めておいて、移動体がその分岐点から誘導経路を逸脱すると、予備経路の中から適切な予備経路を選択して、新たな誘導経路として採用する。これによって、移動体が誘導経路から逸脱すると、誘導経路が直ちに更新されることになる。
【０００４】
【特許文献１】特開２０００−３０４５６２公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特開２０００−３０４５６２公報に開示されたナビゲーションシステムでは、分岐点間を移動体が移動する際に、経路探索が必ず行われることから、例えば、大都市の道路を移動体が移動する場合には、経路探索が頻繁に行われる事態が起こり得る。一般的な経路誘導装置では、ダイクストラ法又はその改良方法に基づいたアルゴリズムが用いられていることから、経路探索にかなりの演算処理が必要とされる。従って、上記公報に開示されたナビゲーションシステムのような構成を採用すると、経路誘導装置のその他の機能に負担が及んでしまう。さらに、分岐点間の間隔や移動体の移動速度は様々であるから、移動体が分岐点に到着するまでに予備経路の探索が終わっていない事態も起こり得る。また、従来の経路誘導装置では、経路の再探索が行われると、逸脱した誘導経路に移動体を戻すために大きく迂回したり、又は出発地に向かって大きく後戻りするような経路が、かなりの頻度で生成される問題がある。
【０００６】
本発明は、上記の問題を解決するものであり、移動体が誘導経路から逸脱した場合に、再探索を極力行うことなく誘導経路を迅速に変更すると共に、大きく迂回又は後戻りしないように誘導経路を変更する経路誘導装置及び経路誘導方法を提供する。
【課題を解決するための手段】
【０００７】
本発明の経路誘導装置は、誘導経路に沿って目的地まで移動体を誘導する経路誘導装置において、出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶し、前記複数の経路の中の第１経路を当初の誘導経路として設定し、前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記移動体が、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記第１経路に復帰可能か否かを判断し、前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定し、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定することを特徴とする。
【０００８】
さらに、本発明の経路誘導装置は、前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出し、前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する。
【０００９】
さらに、本発明の経路誘導装置は、前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断し、前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定し、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する。
【００１０】
本発明の経路誘導方法は、誘導経路に沿って目的地まで移動体を誘導する経路誘導方法において、出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶する工程と、前記複数の経路の中の第１経路を当初の誘導経路として設定する工程と、前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定する工程と、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定する工程とを含むことを特徴とする。
【００１１】
さらに、本発明の経路誘導方法は、前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出する工程と、前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する工程とを含む。
【００１２】
さらに、本発明の経路誘導方法は、前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定する工程と、前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する工程とを含む。
【発明の効果】
【００１３】
本発明では、当初の誘導経路として設定される経路を含めて、出発地から目的地に至る複数の経路を予め生成しておき、移動体が誘導経路から逸脱した場合に、移動体が複数の経路の何れかの経路上にあると、それら複数の経路を利用して誘導経路を新たに設定する。予め得られた経路を利用して誘導経路を設定することから、地図情報を記録媒体から読み出して再探索を行うことなく、誘導経路が迅速に変更される。また、本発明によれば、出発地から目的地に至る複数の経路を利用して、より具体的には部分的に組み合わせて、移動体の現在位置から目的地に至る誘導経路を設定することから、大きく迂回又は後戻りするような誘導経路が設定される可能性は非常に少ない。
【００１４】
また、本発明では、移動体が誘導経路から逸脱した場合に、移動体が複数の経路の何れかの経路上にないと、移動体の現在位置とそれに最も近い交点間の距離と、移動体の現在位置と目的地間の距離とを比較する。そして、前者が後者よりも短い場合、移動体の現在位置から最も近い交点に至る経路が生成されると共に、その経路と、予め生成された複数の経路を利用した経路であって、最も近い交点から目的地に至る経路とで誘導経路が構成される。これによって、必要以上に再探索を行うことなく誘導経路が変更されて、さらに、大きく迂回又は後戻りするような誘導経路が生成される可能性が低減される。
【発明を実施するための最良の形態】
【００１５】
以下、自動車用の車載式ナビゲーション装置(以下、「ナビゲーション装置」と称する)に本発明を適用した実施例について、図を用いて説明する。図１は、ナビゲーション装置(1)のブロック図である。本ナビゲーション装置(1)は、該装置(1)が搭載されている車両の現在位置や方位等を決定する位置検出手段と、地図情報等を記録する記録手段と、記録手段に記録された情報を用いた経路探索、誘導経路に沿って車両を誘導するために必要な処理(例えば、誘導用の画像データや音声データの作成)、及び装置(1)の統括的な制御等を行う制御手段と、車両の現在位置とその周囲の地図等が示された誘導用画面や各種設定画面等を表示する表示手段と、誘導用音声を発生する音声出力手段と、ユーザが装置(1)に各種指示を行うための操作手段とを具えている。
【００１６】
位置検出手段は、ＧＰＳ(Global Positioning System)衛星から送信されるＧＰＳ信号をＧＰＳアンテナ(3)を介して受信して、受信したＧＰＳ信号から車両の現在位置(例えば、緯度及び経度)を特定するＧＰＳ受信部(5)を含んでいる。また、位置検出手段は、ジャイロスコープ(7)及び車速センサ(9)と、これらから送られた信号を処理して車両の方位及び速度を特定するジャイロマイクロコンピュータ(以下、マイクロコンピュータを「マイコン」と称する)(11)を含んでいる。ナビゲーション装置(1)が車両の経路誘導動作を行っている際、ＧＰＳ受信部(5)及びジャイロマイコン(11)は、車両の位置、方位及び速度を決定し、それらの情報を制御手段に送ることを周期的又は定期的に行う。
【００１７】
記録手段は、地図情報等を記録した記録媒体(13)と、制御手段からの指示に基づいて、記録媒体(13)から情報を読み出すドライバ(15)とを含んでいる。記録媒体(13)には、ＣＤ−ＲＯＭ、ＤＶＤ、ＨＤ、又はＩＣメモリ等が用いられる。地図情報は、地理的領域が所定の大きさのブロックに区分けされた形態で記録媒体(13)に記録されている。各ブロックに係るデータには、そのブロックに含まれる道路のノード及びリンクに関するデータ、コンビニエンスストアやガソリンスタンド等の施設の位置データ及び種別データ等、及びそのブロックの地図を表示手段に表示するために用いるデータ等が含まれている。
【００１８】
ノードは、道路の交差点、分岐点、合流点、終点、及びブロックにおける道路の端点に対応して設けられる。各ブロックに係るデータは、そのブロックに含まれる各ノードについて、そのノードのＩＤ番号と、そのノードの位置(例えば、緯度及び経度)と、そのノードの属性(例えば、有料道路の入口又は出口)と、そのノードに接続するリンクのＩＤと、そのノードに隣接するノードのＩＤ番号とを含んでいる。
【００１９】
また、リンクは、ノード間を繋ぐ道路の一区間に対応しており、通常、向きを持っている。各ブロックに係るデータは、そのブロックに含まれる各リンクについて、そのリングのＩＤ番号と、そのリンクの始端ノード及び終端ノードのＩＤ番号と、そのリンクの道路の種別(例えば、有料道路や国道)と、そのリンクの距離(長さ)、そのリンクに接続するリンクのＩＤと、経路探索処理で参照されるリンクコストとを含んでいる。
【００２０】
制御手段には、ＣＰＵ(17)、ＲＡＭ(19)、ＲＯＭ(21)、フラッシュメモリ(23)や図示を省略したローカルバス等を含む制御マイコン(25)が用いられている。ＲＯＭ(21)には、カーナビゲーション装置(1)の各種制御及び処理を実行するためのプログラム及びパラメータ等が記憶されている。経路探索動作や経路誘導動作を行うためのプログラムなど、更新される可能性があるプログラム及びパラメータ等は、フラッシュメモリ(23)に記憶される。これらのプログラムはＣＰＵ(17)により実行される。また、ＲＡＭ(19)は、経路探索動作や経路誘導動作にて読み出された地図情報や演算結果などの一時的なデータの記憶に用いられる。
【００２１】
表示手段は、描画ＩＣ(27)と、液晶表示装置(以下、「ＬＣＤ」と称する)(29)と、ＬＣＤＩ/Ｆ(31)とを含んでいる。経路探索結果の表示画面、経路誘導動作中に表示される誘導用画面や各種設定画面等を表示する指示が制御マイコン(25)から送られると、描画ＩＣ(27)は、その指示に基づいて画像データを作成して、それら画面を、ＬＣＤＩ/Ｆ(31)を介してＬＣＤ(29)に表示する。
【００２２】
音声出力手段は、デジタルアナログコンバータ(以下、「ＤＡＣ」と称する)(33)と、アンプ(35)と、スピーカ(37)とを含んでいる。制御手段は、ユーザを誘導経路に沿って案内する案内音声に係るデジタル音声信号を、経路誘導動作中に適宜作成して、ＤＡＣ(33)に送る。デジタル音声信号は、ＤＡＣ(33)にてアナログ音声信号に変換されてアンプ(35)に送られる。そして、アナログ音声信号はアンプ(35)にて増幅されて、スピーカ(37)から案内音声が出力される。
【００２３】
操作手段は、ナビゲーション装置(1)の筐体(図示せず)に設けられた各種操作キー(39)と、ＬＣＤ(29)上に配置されるタッチパネル(41)と、図示を省略したリモートコントローラ(以下、「リモコン」と称する)と、リモコンから送られる赤外線信号を受信するリモコン受光部(43)と、キーマイコン(45)とを含んでいる。操作キー(39)が押されると、キーマイコン(45)は、押された操作キー(39)を判別して、それに応じた動作コマンドを制御マイコン(25)に送る。また、キーマイコン(45)は、ＬＣＤ(29)に設定画面等が表示されている状態にて、タッチパネル(41)が押された領域を判別して、操作に対応した動作コマンドを制御マイコン(25)に送る。リモコン受光部(43)は、受光した赤外線信号を電気信号に変換及び復調してキーマイコン(45)に送り、キーマイコン(45)は、送られた信号から特定した動作コマンドを制御マイコン(25)に送る。
【００２４】
次に、本実施例のナビゲーション装置(1)が行う経路探索動作について説明する。図２は、経路探索動作の概要を示すフローチャートである。経路探索動作が開始されると、まず、制御マイコン(25)は、目的地設定画面をＬＣＤ(29)に表示させる(Ｓ１)。ユーザが、操作キー(39)やリモコン等を操作して目的地を入力すると、制御マイコン(25)は、それらの位置を特定して、ＲＡＭ(19)に記憶する。ナビゲーション装置(1)では、種々の手順で、目的地を設定することが可能になっている。例えば、記録媒体(13)には、住所や名称等の目的地に関する情報と、目的地の位置とが対応づけられた検索用データベースが記録されており、ユーザが目的地に関する情報を入力すると、検索用データベースが参照されて、目的地の位置が特定される。また、目的地設定画面が表示されると、ＧＰＳ受信部(5)から得られた車両の現在位置が特定されて、制御マイコン(25)は、その位置を出発地の位置としてＲＡＭ(19)に記憶する。なお、ナビゲーション装置(1)では、目的地を設定するように出発地を設定することも可能である。
【００２５】
制御マイコン(25)(のＣＰＵ(17))は、出発地及び目的地の設定が完了したか否かを、例えば、操作手段にて設定完了を指示する操作が行われたが否かを判別し(Ｓ２)、設定が完了すると、設定された出発地及び目的地を含む所定の範囲のノードデータ及びリンクデータが記録媒体(13)から読み出されて、制御マイコン(25)のＲＡＭ(19)に記憶される(Ｓ３)。本実施例のナビゲーション装置(1)は、複数の探索条件の各々に基づいて経路探索を行って複数の経路を生成する。ステップＳ３の後、ある探索条件が選択されて、その探索条件に基づいて経路探索が行われる(Ｓ４)。
【００２６】
ステップＳ４の経路探索処理では、ダイクストラ法又はその改良法に基づいたアルゴリズムに基づいて、出発地に最も近いノード又は出発地のノード(以下、「出発地ノード」と称す)から、目的地に最も近いノード又は目的地のノード(以下、「目的地ノード」と称す)までの経路が探索される。制御マイコン(25)は、ステップＳ３にて設定された条件に基づいて、読み出されたリンクデータのリンクコストを参照して、評価コストが最も低い経路を生成する。生成された経路は、リンク列で表現されて、そのデータはＲＡＭ(19)に記憶される。
【００２７】
本実施例のナビゲーション装置(1)では、例えば、有料道路優先、一般道路優先及び距離優先の３つの探索条件の各々に基づいて経路が探索される。ステップＳ４の後、全ての探索条件について経路探索処理が行われたか否かが判断されて(Ｓ５)。残りの探索条件がある場合は、探索条件を変えて再度ステップＳ４が行われる。このように探索条件を変えてステップＳ４が繰り返されて、全ての探索条件について経路探索処理が行われた後、ＲＡＭ(19)に記憶されている経路データが参照されて、生成された複数の経路上にある交点、つまり交点ノードが求められる(Ｓ６)。そして、ステップＳ６では、交点ノードに該当するノードについて、その旨が、ＲＡＭ(19)に記憶されているノードデータに登録される(交点ノードに該当する全ノードＩＤが、ノードデータとは別個に記憶されてもよい)。ここで、交点とは、生成された複数の経路に含まれる２以上の経路が交差する交差点、又は、複数の経路に含まれる２以上の経路が重なった共通区間の端点(道路の合流点又は分岐点に相当する)である。
【００２８】
ステップＳ６の後、ステップＳ４を繰り返して得られた複数の経路がＬＣＤ(29)に表示される(Ｓ７)。ユーザは、ステップＳ７にて表示された画面を見て、(当初の)誘導経路として採用する経路を選択する(Ｓ８)。ステップＳ８にてある１つの経路が選択されると、制御マイコン(25)は、その経路を誘導経路として設定する(Ｓ９)。
【００２９】
図２に示す経路探索動作が完了すると、ユーザが操作キー(39)等の操作手段を用いて指示することで、ナビゲーション装置(1)は、誘導経路に沿って車両を目的地に誘導する経路誘導動作を開始する。図３及び図４は、この動作を示すフローチャートである。まず、図３を参照する。経路誘導動作が開始されると、制御マイコン(25)は、ＧＰＳ受信部(5)等を含む位置検出手段を用いて車両の現在位置及び方位等を取得し、得られた位置情報等に基づいて誘導用画面をＬＣＤ(29)に表示し、スピーカ(37)から誘導用音声を出力するなどの誘導処理を行う(Ｓ２１)。誘導用画面では、車両の周囲の地図が車両の現在位置を示す記号と共に示されており、誘導経路を構成する道路がその他の道路と区別されるように描画される。なお、経路誘導動作が開始された際の誘導経路は、図２に示すステップＳ９にて設定された経路である。
【００３０】
誘導処理では、車両の現在位置が定期的又は周期的に取得されて、誘導用画面の更新等が行われる。車両の現在位置が取得されると、制御マイコン(25)によって、車両が誘導経路を逸脱しているか否かが判断される(Ｓ２２)。例えば、車両が、誘導経路から所定の距離以上離れている場合に、制御マイコン(25)は、車両が誘導経路から逸脱していると判断する。ステップＳ２２にて、車両が誘導経路から逸脱していないと判断されると、車両が目的地に到達したか否かが判断される(Ｓ２３)。車両が目的地に到達した場合、経路誘導動作は終了する。また、車両が目的地に到達していない場合、ステップＳ２１が再度行われて、誘導用画面の更新等が行われる。
【００３１】
ステップＳ２２にて、車両が誘導経路から逸脱していると判断された場合、まず、制御マイコン(25)は、取得した車両の現在位置と、ＲＡＭ(19)に記憶されている経路データ等とを参照して、図２に示すステップＳ９にて設定された当初の誘導経路上に車両があるか否かを判断する(Ｓ２４)。当初の誘導経路上に車両がある場合、当初の誘導経路に誘導経路が変更されて(Ｓ２５)、ステップＳ２１の誘導処理が行われる。なお、ステップＳ２５は、誘導経路が当初の誘導経路から変更された場合において機能する。ステップＳ２４にて、車両が当初の誘導経路上にないと判断された場合、制御マイコン(25)は、図２に示す経路探索動作にて生成された複数の経路の中で、車両が、誘導経路として採用されなかった経路の何れかの上に位置するか否かを判断する(Ｓ２６)。
【００３２】
ステップＳ２６にて、車両が誘導経路として採用されなかったある経路上に位置すると判断された場合、図２のステップＳ６で得られた交点ノードに関する情報や経路データ等が参照されて、車両の現在位置と目的地間において、その経路上に交点があるか否かが判断される(Ｓ２７)。交点がない場合、即ち、車両の現在位置から目的地に至る途中で、その経路が他の経路と交わることがない場合、その経路が(又は、車両が位置するリンクの始点ノードから目的地ノードに至る区間が)誘導経路に設定される(Ｓ２８)。そして、ステップＳ２１にて、変更された誘導経路に基づいて誘導処理が行われる。
【００３３】
ステップＳ２７にて、車両が位置する経路について、車両の現在位置と目的地の間に交点があると判断された場合、当初の誘導経路以外の(図２の経路探索動作で得られた)経路の交点間区間(始点及び終点が交点である区間)を利用して、車両の現在位置から当初の誘導経路に復帰できるか否かが判断される(Ｓ２９)。ステップＳ２９にて、当初の誘導経路に復帰できると判断された場合、当初の誘導経路以外のその他の経路の交点間区間を利用して当初の誘導経路に復帰し、車両の現在位置から目的地に至る経路(より具体的には、車両が位置するリンクの始点から目的地ノードに至る経路。以下同様)の中で、評価コストの最も低い経路が選択されて、誘導経路として設定される(Ｓ３０)。
【００３４】
ステップＳ３０では、ＲＡＭ(19)に記憶された経路データやリンクデータ等が参照されて、当初の誘導経路以外のその他の経路の交点間区間と当初の誘導経路の一部との組み合わせにより可能な経路の各々について評価コストが算出されて、誘導経路が選択及び設定される。なお、交点間区間を利用して当初の誘導経路に復帰して、車両の現在位置から目的地に至る経路が１つしかない場合には、評価コストを算出することなく、誘導経路の設定が行われる。評価コストは、図２に示す経路誘導動作において当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ３０の後、変更された誘導経路に基づいて誘導処理が行われる。
【００３５】
ステップＳ２９にて、当初の誘導経路以外の経路の交点間区間を利用して、当初の誘導経路に復帰できないと判断された場合、当初の誘導経路以外の経路の交点間区間を利用して車両の現在位置から目的地に至る経路であって、評価コストが最も低い経路が選択されて、誘導経路として設定される(Ｓ３１)。ステップＳ３１では、当初の誘導経路以外のその他の経路の交点間区間の組み合わせにより可能な経路の各々について評価コストが算出されて、誘導経路が選択及び設定される。車両の現在位置から目的地に至る経路が１つしかない場合には、評価コストを算出することなく、誘導経路の設定が行われる。評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ３１の後、変更された誘導経路に基づいてステップＳ２１の誘導処理が行われる。
【００３６】
ステップＳ２６にて、車両が、当初の誘導経路以外の経路上に位置していないと判断された場合、図４に示す処理が行われる。まず、車両の現在位置やノードデータ等が参照されて、車両の現在位置と車両に最も近い交点間の直線距離が、車両の現在位置と目的地間の直線距離よりも短いか否かが判断される(Ｓ４１)。前者が後者以上である場合、車両の現在位置から目的地に至る経路が探索されて、その結果得られた経路が誘導経路として設定される(Ｓ４２)。その後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。なお、ステップＳ４２における評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。
【００３７】
ステップＳ４１にて、車両の現在位置と車両に最も近い交点間の直線距離が、車両の現在位置と目的地間の直線距離よりも短いと判断された場合、車両の現在位置(のノード又は車両に最も近いノード)から、車両に最も近い交点(ノード)に至る経路が探索される(Ｓ４３)。ステップＳ４３における評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。ステップＳ４３の後、車両に最も近い交点が当初の誘導経路上にあるか否かが判断される(Ｓ４４)。車両に最も近い交点が当初の誘導経路上にある場合、ステップＳ４３で生成された経路と、当初の誘導経路におけるその交点から目的地に至る区間とで構成された経路が、誘導経路として設定される(Ｓ４５)。その後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００３８】
ステップＳ４４にて、車両に最も近い交点が当初の誘導経路上にないと判断された場合、当初の誘導経路以外の(図２の経路探索動作で得られた)経路の交点間区間を利用して、車両に最も近い交点から当初の誘導経路に復帰できるか否かが判断される(Ｓ４６)。ステップＳ４６にて、当初の誘導経路に復帰できると判断された場合、ステップＳ３０とほぼ同様にして、当初の誘導経路以外の経路の交点間区間を利用して当初の誘導経路に復帰し、車両に最も近い交点から目的地に至る経路の中で、評価コストが最も低い経路が選択される。そして、選択された経路とステップＳ４３で生成された経路とを組み合わせた経路が、誘導経路として設定される(Ｓ４７)。ここで、評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。また、ステップＳ４７では、車両に最も近い交点から目的地に至る経路が１つしか存在しない場合、評価コストを算出することなく、その経路が誘導経路として設定される。ステップＳ４７の後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００３９】
ステップＳ４６にて、当初の誘導経路に復帰できないと判断された場合、ステップＳ３１とほぼ同様にして、当初の誘導経路以外の経路の交点間区間を利用して最も近い交点から目的地に至る経路の中で、評価コストが最も低い経路が選択されて、その経路とステップＳ４３で生成された経路とを組み合わせた経路が、誘導経路として設定される(Ｓ４８)。ここで、評価コストは、当初の誘導経路を生成する際に行われた経路探索の評価コストと同じにされることが好ましい。また、ステップＳ４８では、車両に最も近い交点から目的地に至る経路が１つしか存在しない場合、評価コストを算出することなく、その経路が誘導経路として設定される。ステップＳ４８の後、変更された誘導経路に基づいて、ステップＳ２１の誘導処理が行われる。
【００４０】
図５(a)乃至図５(e)は、本発明のナビゲーション装置(1)にて経路誘導動作が行われて、出発地から目的地に車両が誘導される一例を示す説明図である。図２に示す経路探索動作にて、探索条件を変えてステップＳ４が繰り返されることによって、出発地ノードＮ1から目的地ノードＮ9に至る３つの経路、即ち経路Ａ、経路Ｂ及び経路Ｃが得られている。経路Ａは、リンク列｛Ｌ1，Ｌ2，Ｌ4．Ｌ7，Ｌ9｝で構成されており、これらの図中にて実線で表されている。経路Ｂは、リンク列｛Ｌ1，Ｌ2，Ｌ6．Ｌ8，Ｌ10，Ｌ11｝で構成されており、これらの図中にて一点鎖線で表されている。経路Ｃは、リンク列｛Ｌ1，Ｌ3，Ｌ5．Ｌ7，Ｌ10，Ｌ11｝で構成されており、これらの図中にて破線で表されている。
【００４１】
図２に示すステップＳ６にて、経路Ａと経路Ｂの共通区間であるリンクＬ2の端点であるノードＮ2及びＮ3と、経路Ａと経路Ｃの共通区間であるリンクＬ7の端点であるノードＮ5と、同じくリンクＬ7の端点であって、経路Ａ、経路Ｂ及び経路Ｃの交差点でもあるノードＮ7と、出発地ノードＮ1及び目的地ノードＮ9とが、交点ノードとして登録されている。また、ステップＳ９では、経路Ａが誘導経路として設定されている。
【００４２】
図３に示す経路誘導動作が開始すると、当初の誘導経路である経路Ａに沿って車両Ｐを誘導するように、ステップＳ２１が行われる。図５(a)は、経路Ａ及び経路Ｂに含まれており、リンクＬ2に対応した区間上を車両Ｐが移動している模様を示している。図５(b)は、交点ノードであるノードＮ3を経由して、誘導経路である経路Ａから車両Ｐが逸脱した模様を示している。図５(b)に示すケースでは、経路Ｂ上に、車両Ｐが位置していることから、図３に示すステップＳ２２、Ｓ２４及びＳ２６の後、ステップＳ２７が行われる。経路Ｂには、車両Ｐの現在位置と目的地の間にて、経路Ａと交わる交点ノードＮ7が存在することから、ステップＳ２７の後、ステップＳ２９が行われる。
【００４３】
ステップＳ２９が行われると、交点ノードＮ7は、当初の誘導経路である経路Ａと交わる交点ノードであるから、経路Ｂを利用して、車両Ｐの現在位置から当初の誘導経路に復帰可能と判断される。ステップＳ２９の後、ステップＳ３０が行われるが、車両Ｐの現在位置から経路Ａに復帰して目的地に至る経路は、経路｛Ｌ6，Ｌ8，Ｌ9｝の１つのみであるので、経路探索が行われることなく、この経路が誘導経路として設定される。そして、経路｛Ｌ6，Ｌ8，Ｌ9｝に沿って車両Ｐを誘導するように、ステップＳ２１の誘導処理が行われる。
【００４４】
図５(c)は、上述のように誘導経路の変更が行われた後、ノードＮ6を通って、誘導経路である経路｛Ｌ6，Ｌ8，Ｌ9｝から車両Ｐが逸脱した模様を示している。このケースでは、ステップＳ２２、Ｓ２４及びＳ２６が行われた後、図４に示すステップＳ４１が行われる。ステップＳ４１では、車両Ｐの現在位置と、この位置に最も近い交点ノードであるノードＮ7との間の直線距離が計算され、さらに、車両Ｐの現在位置と目的地ノードＮ9間の直線距離が計算される。このケースでは、前者が後者よりも短いことから、ステップＳ４１の後、ステップＳ４３が行われる。図５(d)にて、ステップＳ４３が行われて生成された経路｛Ｌ12，Ｌ13｝を点線で示す。
【００４５】
ステップＳ４３が行われた後、ステップＳ４４が行われる。車両Ｐの現在位置に最も近い交点ノードであるノードＮ7は、当初の誘導経路Ａ上にある交点ノードであるので、ステップＳ４４の後ステップＳ４５が行われて、経路｛Ｌ12，Ｌ13，Ｌ9｝が新たな誘導経路として設定される。そして、図５(e)に示すように、この経路に沿って車両Ｐを移動させることで、車両Ｐを目的地に到達させることが可能となる。
【００４６】
図６(a)は、図５(b)と似たケースを示しているが、当初の誘導経路である経路Ａが、リンク列｛Ｌ1，Ｌ2，Ｌ4，Ｌ14｝で構成されており、経路Ｃが、リンク列｛Ｌ1，Ｌ3，Ｌ5，Ｌ7，Ｌ9｝で構成されている点が異なる。ここで、リンクＬ14は、交点ノードＮ5から目的地ノードＮ9に至る区間に対応している。図６(a)に示すケースでは、ステップＳ２２、Ｓ２４、Ｓ２６及びＳ２７が行われた後、車両Ｐが位置している経路Ｂ上に交点ノードＮ7があることから、ステップＳ２９が行われる。さらに、経路Ｂと、交点ノードＮ7にて経路Ｂと交差する経路Ｃとは、交点ノードＮ7以降にて経路Ａと交わることはないので、ステップＳ２９にて、経路Ｂを、又は経路Ｂ及び経路Ｃを利用して、車両Ｐの現在位置から当初の誘導経路に復帰することはできないという判断がなされる。そして、ステップＳ３１にて、経路Ｂを、さらには経路Ｃをも利用して車両Ｐの現在位置から目的地に至る経路の中で、評価コストが最も低い経路が誘導経路として設定される。このケースでは、経路｛Ｌ6，Ｌ8，Ｌ9｝の評価コストと、経路｛Ｌ6，Ｌ8，Ｌ10，Ｌ11｝の評価コストとが比較されて、評価コストが低い経路が誘導経路として設定される。
【００４７】
図６(b)は、上述のように誘導経路が変更された後にノードＮ6を通って車両Ｐが誘導経路から逸脱した模様を示している。このケースでは、図５(c)及び図５(d)について説明したように、ステップＳ４３にて、車両Ｐの現在位置から交点ノードＮ7に至る経路｛Ｌ12，Ｌ13｝が生成される。図６(b)では、交点ノードＮ7は、当初の誘導経路である経路Ａ上にないので、ステップＳ４３及びＳ４４の後、ステップＳ４６が行われる。交点ノードＮ7からは、経路Ｂ及び/又は経路Ｃを利用して経路Ａに復帰することはできないので、ステップＳ４６の後、ステップＳ４８が行われる。ステップＳ４８では、リンクＬ9からなる経路の評価コストと、経路｛Ｌ10，Ｌ11｝の評価コストとが比較されて、これらの中で評価コストが低い方の経路と、経路｛Ｌ12，Ｌ13｝とで構成される経路が誘導経路に設定される。
【００４８】
図７(a)は、図５(b)と似たケースを示しているが、当初の誘導経路である経路Ａが｛Ｌ1，Ｌ2，Ｌ4，Ｌ7，Ｌ10，Ｌ11｝、経路Ｂが｛Ｌ1，Ｌ2，Ｌ6，Ｌ15，Ｌ16，Ｌ11｝、経路Ｃが｛Ｌ1，Ｌ3，Ｌ5，Ｌ17，Ｌ18，Ｌ9｝で構成されている点が異なる。図７(a)にて、ノードＮ7は、経路Ａと経路Ｃの交点ノードであり、ノードＮ8は、経路Ａと経路Ｂの交点ノードであり、ノードＮ11は、経路Ｂと経路Ｃの交点ノードである。
【００４９】
図７(a)に示すケースでは、車両Ｐが交点ノードＮ3を通って、誘導経路である経路Ａから逸脱すると、ステップＳ２２、Ｓ２４、Ｓ２６及びＳ２７が行われた後、ステップＳ２９、さらにはステップＳ３０が行われる。このケースでは、ステップＳ３０にて、経路Ｂの交点間区間である区間｛Ｌ6，Ｌ15｝及びリンクＬ16を利用して経路Ａに戻って目的地に至る経路｛Ｌ6，Ｌ15，Ｌ16，Ｌ11｝の評価コストと、経路Ｂの交点間区間である区間｛Ｌ6，Ｌ15｝と経路Ｃの交点間区間であるリンクＬ18を利用して経路Ａに戻って目的地に至る経路｛Ｌ6，Ｌ15，Ｌ18，Ｌ10，Ｌ11｝の評価コストとが比較されて、評価コストの低い経路が誘導経路として選択される。
【００５０】
図７(b)は、上述のように誘導経路が変更された後にノードＮ6を通って車両誘導経路から逸脱した模様を示している。このケースでは、ステップＳ４３にて、車両Ｐの現在位置から交点ノードＮ11に至る経路(図中に点線で示す)が生成される。交点ノードＮ11は、経路Ａ上にないことから、ステップＳ４３及びＳ４４の後、ステップＳ４６が行われる。交点ノードＮ11以降にて、経路Ｂ及び経路Ｃは、経路Ａと交わっていることから、ステップＳ４６の後、ステップＳ４７が行われる。ステップＳ４７では、経路Ｃの交点間区間であるリンクＬ18を利用して交点ノードＮ11から経路Ａに戻って、目的地に至る経路｛Ｌ18，Ｌ10，Ｌ11｝の評価コストと、経路Ｂの交点間区間であるリンクＬ16を利用して交点ノードＮ11から経路Ａに戻って、目的地に至る経路｛Ｌ16，Ｌ11｝の評価コストとが比較されて、これら経路の中で評価コストの低い方の経路と、ステップＳ４３で生成された経路とで構成される経路が誘導経路として選択される。
【００５１】
本実施例のナビゲーション装置(1)では、図２に示すように探索条件を変えて経路探索を繰り返すことで、出発地から目的地に至る複数の経路を生成しているが、本発明の特徴とする経路誘導動作は、経路誘導動作を行う前に、出発地から目的地に至る複数の経路が予め生成されていれば実行可能であって、これら経路の特性は基本的に問われない。例えば、経路探索動作にて、単一の探索条件で経路探索を行った結果から複数の経路(例えば、誘導経路として設定される評価コストの最も低い最適経路と、最適経路よりも評価コストが低い幾つかの経路)を選んでもよい。この場合だと、図２に示す経路探索動作と、図３及び図４に示す経路誘導動作とにおいて、同一種類の評価コストが用いられる点が好ましい。また、図２に示す経路探索動作において、有料道路優先等の探索条件下で、付加的な条件を変化させることで複数の経路が生成されてもよい。
【００５２】
また、ナビゲーション装置(1)は、必ずしも車載式である必要はなく、その具体的形態は特に限定されない。例えば、上記実施例の機能の一部、例えば経路探索機能が、別個に設けられたサーバ装置で行われて、通信手段を用いて探索結果がサーバ装置からナビゲーション装置に送られてもよい。さらに、本発明は、自動車用のナビゲーション装置に限定されることはなく、移動体用の経路誘導装置に広く適用可能である。
【００５３】
上記実施例の説明は、本発明を説明するためのものであって、特許請求の範囲に記載の発明を限定し、或は範囲を減縮する様に解すべきではない。本発明の各部構成は上記実施例に限らず、特許請求の範囲に記載の技術的範囲内で種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施例であるナビゲーション装置のブロック図である。
【図２】本発明の実施例であるナビゲーション装置の経路探索動作を示すフローチャートである。
【図３】本発明の実施例であるナビゲーション装置の経路誘導動作を示すフローチャートである。
【図４】本発明の実施例であるナビゲーション装置の経路誘導動作を示すフローチャートである。
【図５（ａ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｂ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｃ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｄ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図５（ｅ）】本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図６】図６(a)及び図６(b)は、本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【図７】図７(a)及び図７(b)は、本発明の実施例であるナビゲーション装置を用いて車両が誘導される例を示す説明図である。
【符号の説明】
【００５５】
(1) カーナビゲーション装置
(5) ＧＰＳ受信部
(13) 記録媒体
(19) ＲＡＭ
(25) 制御マイクロコンピュータ
(29) 液晶表示装置
(41) タッチパネル
【特許請求の範囲】
【請求項１】
誘導経路に沿って目的地まで移動体を誘導する経路誘導装置において、
出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶し、
前記複数の経路の中の第１経路を当初の誘導経路として設定し、
前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断し、
前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定し、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定することを特徴とする経路誘導装置。
【請求項２】
前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出し、
前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する、請求項１に記載の経路誘導装置。
【請求項３】
前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断し、
前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定し、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する、請求項２に記載の経路誘導装置。
【請求項４】
誘導経路に沿って目的地まで移動体を誘導する経路誘導方法において、
出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶する工程と、
前記複数の経路の中の第１経路を当初の誘導経路として設定する工程と、
前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、
前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定する工程と、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定する工程とを含むことを特徴とする経路誘導方法。
【請求項５】
前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出する工程と、
前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する工程とを含む、請求項４に記載の経路誘導方法。
【請求項６】
前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、
前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定する工程と、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する工程とを含む、請求項５に記載の経路誘導方法。
【請求項１】
誘導経路に沿って目的地まで移動体を誘導する経路誘導装置において、
出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶し、
前記複数の経路の中の第１経路を当初の誘導経路として設定し、
前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断し、
前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定し、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定することを特徴とする経路誘導装置。
【請求項２】
前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出し、
前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する、請求項１に記載の経路誘導装置。
【請求項３】
前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断し、
前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定し、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する、請求項２に記載の経路誘導装置。
【請求項４】
誘導経路に沿って目的地まで移動体を誘導する経路誘導方法において、
出発地から前記目的地に至る複数の経路を生成して、前記複数の経路上の交点を記憶する工程と、
前記複数の経路の中の第１経路を当初の誘導経路として設定する工程と、
前記移動体が誘導経路から逸脱した場合に、前記移動体が、前記複数の経路の１つであって、前記第１経路と異なる第２経路上に位置していると、前記第１経路を除く前記複数の経路の中の１又は２以上の経路を利用して、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、
前記移動体が前記第１経路に復帰可能な場合、前記移動体の現在位置から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路を誘導経路として設定する工程と、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して、前記移動体の現在位置から前記目的地に至る経路を誘導経路として設定する工程とを含むことを特徴とする経路誘導方法。
【請求項５】
前記移動体が誘導経路から逸脱した場合に、前記移動体が前記第２経路上に位置していないと、前記移動体の現在位置と前記移動体に最も近い交点との間の第１距離と、前記移動体の現在位置と前記目的地との間の第２距離とを算出する工程と、
前記第１距離が前記第２距離よりも短い場合、前記移動体の現在位置から前記最も近い交点に至る第３経路を生成する工程とを含む、請求項４に記載の経路誘導方法。
【請求項６】
前記第１距離が前記第２距離よりも短く、前記最も近い交点が前記第１経路上にない場合、前記１又は２以上の経路を利用して、前記最も近い交点を通って、前記移動体が前記第１経路に復帰可能か否かを判断する工程と、
前記移動体が前記第１経路に復帰可能な場合、前記最も近い交点から前記目的地に至る経路であって、前記１又は２以上の経路を利用して前記第１経路に復帰する経路と、前記第３経路とで構成される経路を誘導経路として設定する工程と、
前記移動体が前記第１経路に復帰不可能な場合、前記１又は２以上の経路を利用して前記最も近い交点から前記目的地に至る経路と、前記第３経路とで構成される経路を誘導経路として設定する工程とを含む、請求項５に記載の経路誘導方法。
【図１】
【図２】
【図３】
【図４】
【図５（ａ）】
【図５（ｂ）】
【図５（ｃ）】
【図５（ｄ）】
【図５（ｅ）】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５（ａ）】
【図５（ｂ）】
【図５（ｃ）】
【図５（ｄ）】
【図５（ｅ）】
【図６】
【図７】
【公開番号】特開２００６−２６６９６３（Ｐ２００６−２６６９６３Ａ）
【公開日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【出願番号】特願２００５−８７５４７（Ｐ２００５−８７５４７）
【出願日】平成１７年３月２５日（２００５．３．２５）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
【公開日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【出願日】平成１７年３月２５日（２００５．３．２５）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
[ Back to top ]