(57)【要約】【課題】道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、利用者の嗜好に合致した経路決定を行うことができる経路探索装置を提供する。【解決手段】ディスプレイ２ａに表示した地図表示画面２Ａに対して指示された操作軌跡５ａを検出する入出力処理部１ａと、当該入出力処理部１ａが検出した操作軌跡５ａを地図表示画面２Ａ上の複数の座標点で表した経由地点５ｂ群に変換する経路設定部１ｄと、経由地点５ｂ群及び地図表示画面２Ａ上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路データを用いて、所望の経路に応じた誘導経路を算出する経路計算処理部１ｅとを備える。【選択図】　　　　図１
2004028703.tif 000002
【特許請求の範囲】
【請求項１】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、
当該軌跡検出部が検出した軌跡を上記地図画像上の複数の座標点で表した経由地点群に変換する経路設定部と、
上記経由地点群及び上記地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、上記所望の経路に応じた誘導経路を算出する経路計算処理部と
を備えた経路探索装置。
【請求項２】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、
当該軌跡検出部が検出した軌跡を複数の線分に分割し、各線分の節点を上記地図画像上の座標点で表した経由地点群に変換する経路設定部と、
上記経由地点群及び上記地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、上記所望の経路に応じた誘導経路を算出する経路計算処理部と
を備えた経路探索装置。
【請求項３】
経路設定部は、経路計算処理部が誘導経路を算出すると、上記誘導経路内の各経由地点近傍に共通の属性を有する道路リンクの交差節点が存在するか否かを判定し、上記交差節点が存在する場合、当該交差節点を新たな経由地点として設定することを特徴とする請求項１又は請求項２記載の経路探索装置。
【請求項４】
経路設定部は、交差節点が所定の領域内に存在するか否かを判定し、上記領域内に存在すると、当該交差節点を新たな経由地点として設定することを特徴とする請求項３記載の経路探索装置。
【請求項５】
経路設定部は、経由地点の近傍で複数回の通過を要する道路リンクである重複使用リンクが存在するか否かを判定し、上記重複使用リンクが存在する場合、当該重複使用リンクの節点を１回通過する経路となるように経由地点を再設定することを特徴とする請求項１又は請求項２記載の経路探索装置。
【請求項６】
経路設定部は、経由地点近傍に予め定めた属性の道路リンクが存在する場合、当該道路リンク上に新たな経由地点を設定し、
経路計算処理部は、上記経路設定部によって新たに設定された経由地点を用いて、所望の経路に応じた誘導経路を算出することを特徴とする請求項１又は請求項２記載の経路探索装置。
【請求項７】
経路設定部は、所望の経路に応じた軌跡から求めた経由地点と、当該経由地点に代わって新たに設定された経由地点とを、異なる記号で地図画像上に表示させることを特徴とする請求項６記載の経路探索装置。
【請求項８】
経路設定部は、所望の経路に応じた軌跡から求めた経由地点及び当該経由地点に代わって新たに設定された経由地点のいずれか及び／又は一方の記号の表示可否を適宜設定可能であることを特徴とする請求項７記載の経路探索装置。
【請求項９】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、
上記地図画像上の道路のうち経路計算に使用すべき道路を決定する経路計算領域を上記軌跡検出部が検出した軌跡に沿って設定する経路設定部と、
上記地図画像上の道路網のうち上記経路計算領域内に含まれる各道路を、節点間を接続する道路リンクとして表現した道路情報を用いて、上記所望の経路に応じた誘導経路を算出する経路計算処理部と
を備えた経路探索装置。
【請求項１０】
経路設定部は、軌跡検出部が検出した軌跡を複数の線分に分割すると共に、各線分に応じて経路計算領域を設定し、
経路計算処理部は、上記各経路計算領域内の道路に関する道路情報を用いて、所望の経路に応じた誘導経路を算出することを特徴とする請求項９記載の経路探索装置。
【請求項１１】
経路計算処理部は、地図画像上の道路網が表示装置に地図の縮尺に応じたレイアウトで表示される場合、所望の経路に応じた軌跡が入力された際に表示されていた道路網に関する道路情報を用いて、上記所望の経路に応じた誘導経路を算出することを特徴とする請求項１から請求項１０のうちのいずれか１項記載の経路探索装置。
【請求項１２】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、
当該軌跡検出部が検出した軌跡を上記地図画像上の複数の座標点で表した経由地点群に変換する経路設定部、
上記経由地点群及び上記地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、上記所望の経路に応じた誘導経路を算出する経路計算処理部
としてコンピュータを機能させるプログラム。
【請求項１３】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、
当該軌跡検出部が検出した軌跡を複数の線分に分割し、各線分の節点を上記地図画像上の座標点で表した経由地点群に変換する経路設定部、
上記経由地点群及び上記地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、上記所望の経路に応じた誘導経路を算出する経路計算処理部
としてコンピュータを機能させるプログラム。
【請求項１４】
表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、
上記地図画像上の道路のうち経路計算に使用すべき道路を決定する経路計算領域を上記軌跡検出部が検出した軌跡に沿って設定する経路設定部、
上記地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、上記経路計算領域内に含まれる上記所望の経路に応じた誘導経路を算出する経路計算処理部
としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は車両が進むべき誘導経路を探索するナビゲーション装置として機能する経路探索装置に係り、特にディスプレイに表示した地図画像に対して指示された軌跡から所望する誘導経路を算出する経路探索装置及びプログラムに関するものである。
【０００２】
【従来の技術】
従来の経路探索装置は、利用者によって指定された目的地点と自車位置（出発地点）を結ぶ複数の経路候補を算出する。このあと、これら経路候補に含まれる道路の名称、若しくはこれらを道路種別（例えば、高架道路、地下道、高速道路、国道、一般道、有料道路など）に分類したデータをリスト形式で画面上に表示する。ここで、利用者は、画面上に表示された経路候補に係る情報のうち、所望の経路に合致した道路やその道路種別を選択し、これを基にして所望の経路を最終的に決定する。このような経路探索装置としては、例えば特開平１１−２３３０７号公報に開示されるものがある。
【０００３】
【発明が解決しようとする課題】
従来の経路探索装置は以上のように構成されているので、利用者に提示される経路候補に係る情報と実際の道路との対応関係が明確でなく、利用者の嗜好に合致した経路決定を行うことが困難であるという課題があった。
【０００４】
上記課題を具体的に説明する。
一般的に、利用者は、道路若しくは道路種別についての知識がない場合が多い。また、訪問したことのない地域では、選択した経路情報に対応する道路によって実際にどのような経路が導かれるのかなどの判定が困難である。このため、利用者が自己の嗜好に合致した経路を決定する場合、経路探索装置から提示された経路候補に係る情報のみで所望の経路であるか否かを判断することができない。結局、地図画面上に表示された経路によって所望の経路か否かを判定せざるを得ないのが現状である。
【０００５】
この発明は上記のような課題を解決するためになされたもので、ディスプレイに表示した地図画像に対して指示された軌跡から所望する誘導経路を算出することで、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、利用者の嗜好に合致した経路決定を行うことができる経路探索装置及びプログラムを得ることを目的とする。
【０００６】
【課題を解決するための手段】
この発明に係る経路探索装置は、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、当該軌跡検出部が検出した軌跡を地図画像上の複数の座標点で表した経由地点群に変換する経路設定部と、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるものである。
【０００７】
この発明に係る経路探索装置は、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、当該軌跡検出部が検出した軌跡を複数の線分に分割し、各線分の節点を地図画像上の座標点で表した経由地点群に変換する経路設定部と、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるものである。
【０００８】
この発明に係る経路探索装置は、経路計算処理部が誘導経路を算出すると、誘導経路内の各経由地点近傍に共通の属性を有する道路リンクの交差節点が存在するか否かを経路設定部が判定し、交差節点が存在する場合、当該交差節点を新たな経由地点として設定するものである。
【０００９】
この発明に係る経路探索装置は、交差節点が所定の領域内に存在するか否かを経路設定部が判定し、上記領域内に存在すると当該交差節点を新たな経由地点として設定するものである。
【００１０】
この発明に係る経路探索装置は、経由地点の近傍で複数回の通過を要する道路リンクである重複使用リンクが存在するか否かを経路設定部が判定し、重複使用リンクが存在する場合、当該重複使用リンクの節点を１回通過する経路となるように経由地点を再設定するものである。
【００１１】
この発明に係る経路探索装置は、経路設定部が、経由地点近傍に予め定めた属性の道路リンクが存在する場合、当該道路リンク上に新たな経由地点を設定し、経路計算処理部が、経路設定部によって新たに設定された経由地点を用いて、所望の経路に応じた誘導経路を算出するものである。
【００１２】
この発明に係る経路探索装置は、経路設定部が、所望の経路に応じた軌跡から求めた経由地点と、当該経由地点に代わって新たに設定された経由地点とを、異なる記号で地図画像上に表示させるものである。
【００１３】
この発明に係る経路探索装置は、経路設定部が、所望の経路に応じた軌跡から求めた経由地点及び当該経由地点に代わって新たに設定された経由地点のいずれか及び／又は一方の記号の表示可否を適宜設定可能であるものである。
【００１４】
この発明に係る経路探索装置は、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、地図画像上の道路のうち経路計算に使用すべき道路を決定する経路計算領域を軌跡検出部が検出した軌跡に沿って設定する経路設定部と、地図画像上の道路網のうち経路計算領域内に含まれる各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるものである。
【００１５】
この発明に係る経路探索装置は、経路設定部が、軌跡検出部が検出した軌跡を複数の線分に分割すると共に、各線分に応じて経路計算領域を設定し、経路計算処理部が、各経路計算領域内の道路に関する道路情報を用いて、所望の経路に応じた誘導経路を算出するものである。
【００１６】
この発明に係る経路探索装置は、経路計算処理部が、地図画像上の道路網が表示装置に地図の縮尺に応じたレイアウトで表示される場合、所望の経路に応じた軌跡が入力された際に表示されていた道路網に関する道路情報を用いて、所望の経路に応じた誘導経路を算出するものである。
【００１７】
この発明に係るプログラムは、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、当該軌跡検出部が検出した軌跡を地図画像上の複数の座標点で表した経由地点群に変換する経路設定部、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部としてコンピュータを機能させるものである。
【００１８】
この発明に係るプログラムは、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、当該軌跡検出部が検出した軌跡を複数の線分に分割し、各線分の節点を地図画像上の座標点で表した経由地点群に変換する経路設定部、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて所望の経路に応じた誘導経路を算出する経路計算処理部としてコンピュータを機能させるものである。
【００１９】
この発明に係るプログラムは、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部、地図画像上の道路のうち経路計算に使用すべき道路を決定する経路計算領域を軌跡検出部が検出した軌跡に沿って設定する経路設定部、地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、経路計算領域内に含まれる所望の経路に応じた誘導経路を算出する経路計算処理部としてコンピュータを機能させるものである。
【００２０】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１による経路探索装置の構成を示す図である。図において、１は中央処理装置であって、本発明の経路探索装置として機能するコンピュータ装置のＣＰＵ及びその周辺回路などから具現化される。１ａは入出力装置２との間でやり取りされる情報を処理する入出力処理部（軌跡検出部）で、例えばタッチパネル２ｂやリモートコントローラ２ｃを用いて利用者が入力した情報を地図表示部１ｃと協動してディスプレイ２ａに表示したりＲＡＭ１ｇへの一時的な記憶を実行する。
【００２１】
１ｂは現在位置検出装置３と協動して測位処理を実行する測位処理部であって、ＧＰＳ受信機３ａ、速度センサ３ｂや相対方位センサ３ｃからの情報に基づいて自車位置を決定し、経路計算処理部１ｅなどに送出する。１ｃはディスプレイ２ａの表示画面を管理する地図表示部で、例えば表示画面上の地図を実際と対応付けるための緯度経度座標や正規化座標などを管理する。
【００２２】
１ｄは経路設定部であって、地図表示画面に対して入出力装置２を介して利用者が入力した座標情報や地図情報記憶装置４に記憶された数値化地図情報から経路設定に必要とする情報を求める。１ｅは経路計算処理部で、測位処理部１ｂや経路設定部１ｄからの情報を元に利用者の設定内容に合致した経路を算出する。１ｆは経路計算処理部１ｅが算出した経路に沿った案内情報（例えば、交差点・分岐等での右左折指示など）を生成する経路誘導部であって、地図上の案内表示や音声による誘導情報からなる案内情報をディスプレイ２ａやスピーカ２ｄなどを介して利用者に提示する。また、入出力処理部１ａ、測位処理部１ｂ、地図表示部１ｃ、経路設定部１ｄ、経路計算処理部１ｅ及び経路誘導部１ｆは、それぞれの処理を実行させるプログラムによって具現化される。
【００２３】
１ｇは中央処理装置１内に内蔵されたＲＡＭであって、地図情報記憶装置４に格納された数値化された地図データや利用者によって設定された座標値などを一時的に記憶する書き換え可能なメモリである。１ｈは中央処理装置１内に内蔵されたフラッシュメモリで、上述したプログラムなどを半恒久的に記憶する書き換え可能な不揮発性のメモリである。２は利用者と中央処理装置１との間における情報のやり取りを中継する入出力装置であって、地図画面を表示するためのディスプレイ２ａ、利用者が地図画面上の座標情報を入力するためのタッチパネル２ｂ、利用者の設定情報を入力するリモートコントローラ２ｃ、及び案内情報を音声で出力するスピーカ２ｄなどから構成される。
【００２４】
３は利用者が運転する車両の現在位置に関する情報を検出する現在位置検出装置で、衛星航法システムを利用したＧＰＳ受信機３ａ、速度センサ３ｂ、やジャイロからなり車両の方位を算出する相対方位センサ３ｃなどが用いられる。４はディスプレイ２ａに表示すべき地図情報を記憶する地図情報記憶装置であって、本発明の経路探索装置として機能するコンピュータ装置に標準的に搭載されるハードディスク装置やＣＤ−ＲＯＭやＤＶＤなどの記憶媒体を用いるドライブ装置などで具現化される。
【００２５】
図２は図１中のディスプレイに表示した地図表示画面を示す図であり、（ａ）は利用者が入力した操作軌跡を示し、（ｂ）は（ａ）中の操作軌跡から求められた経由地点群を示している。図において、２Ａは図１中のディスプレイ２ａに表示された地図表示画面である。５はディスプレイ２ａに表示された地図画面に対して利用者が入力する操作点であって、例えばタッチパネル２ｂによって希望する経路に沿った情報として入力される。（ａ）に示す例では、タッチパネル２ｂによる入力を表す指さしマークで示されている。
【００２６】
また、操作点の入力は、ディスプレイ２ａに重ねて設置されたタッチパネル２ｂを利用する方法の他に、リモートコントローラ２ｃを用いることも可能である。５ａは利用者が希望する経路に対応する操作軌跡で、タッチパネル２ｂを使って操作点５を連続的に入力することで形成される。５ｂは経由地点であって、操作軌跡５ａを構成する操作点５を所定間隔ごとに抽出し地図上の座標値に変換したものに相当する。
【００２７】
図３は図１中の経路探索装置のディスプレイに表示される画面を示す図である。図において、２ｅ−１は地図表示画面２Ａ上で自車が位置する領域を表示する現在地の表示ボタンであって、タッチパネル２ｂやリモートコントローラ２ｃを用いて選択（押下）することで測位処理部１ｂからの自車位置情報を地図表示画面２Ａ上に反映させるプログラムから構成される。２ｅ−２は経路探索に必要な情報を設定するための設定画面と地図表示画面２Ａとを適宜切り替えるメニューボタンで、上記設定画面を表示する動作モードを経路設定モードとし、地図を表示する動作モードを地図表示モードとする。２ｅ−３は地図表示画面２Ａの縮尺を変更する拡大・縮小ボタンであって、選択（押下）することで地図表示部１ｃが起動し地図を拡大したり縮小したりする。
【００２８】
２ｆ−１は設定画面を構成する目的地設定（施設）ボタンで、任意の施設を目的地に設定する際に用いられる。２ｆ−２は実施の形態１の経路探索装置の動作モードを選択する目的地設定（画面）ボタンで、選択（押下）することで利用者が希望する経路の探索に必要な目的地の設定処理に移行する。２ｆ−３は実施の形態１の経路探索装置の動作モードを選択する経路設定（画面）ボタンで、選択（押下）することで利用者が希望する経路の探索に必要な操作点５（操作軌跡５ａ）の設定処理に移行する。なお、図１と同一構成要素には同一符号を付して重複する説明を省略する。
【００２９】
次に動作について説明する。
図４は図１中の経路探索装置の動作を示すフロー図であり、この図に沿って経路探索処理を詳細に説明する。
実施の形態１による経路探索装置では、図３に示すように、タッチパネル２ｂやリモートコントローラ２ｃを用いて選択可能な操作ボタンを設けている。例えば、現在地の表示ボタン２ｅ−１を選択すると、当該ボタン２ｅ−１が選択された旨が入出力処理部１ａから測位処理部１ｂに伝えられる。このあと、測位処理部１ｂは、現在位置検出装置３と協働して自車位置に関する情報を取得し、地図表示部１ｃに出力する。
【００３０】
地図表示部１ｃでは、測位処理部１ｂから得た自車位置に関する情報を地図表示画面２Ａ上の座標値に変換し、入出力処理部１ａを介して図３の左図のようにディスプレイ２ａに表示させる。このとき、拡大・縮小ボタン２ｅ−３を選択することで、地図表示部１ｃによって地図表示画面２Ａ上の自車が位置する領域を拡大したり、縮小して地図全体との関係を表示することができる。
【００３１】
ここで、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いてメニューボタン２ｅ−２を選択すると、入出力処理部１ａは、図３の右図のような経路設定用のメニュー画面をディスプレイ２ａに表示させる。利用者は、このメニュー画面に従って希望する経路の探索に必要な情報の設定を行う。例えば、目的地設定（施設）ボタン２ｆ−１を選択すると、入出力処理部１ａは、地図情報記憶装置４に格納された代表的な施設に関する情報を読み出し、これら施設の名称をリスト形式に表示する画面をディスプレイ２ａに表示させる。利用者は、このリスト中にあげられた施設を適宜選択することで、目的地を容易に設定することができる。
【００３２】
また、目的地設定（画面）ボタン２ｆ−２が選択されると、入出力処理部１ａは、利用者によって地図表示画面２Ａ上の任意の点が目的地として選択されるのを待つ状態に移行する。ここで、利用者によって地図表示画面２Ａ上の任意の点が目的地として選択されると、当該目的地に関する情報（例えば、地図表示画面２Ａ上の座標値など）は、入出力処理部１ａからＲＡＭ１ｇに一時記憶される。当該情報は、経路設定モードにおける経路探索に用いられる。
【００３３】
次に、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いてメニュー画面中の経路設定（画面）ボタン２ｆ−３を選択した場合について説明する。先ず、利用者がメニュー画面中の経路設定（画面）ボタン２ｆ−３を選択すると、当該ボタン２ｆ−３が選択された旨が入出力処理部１ａに伝えられる。これにより、経路探索装置では、経路設定モードが起動する（ステップＳＴ１）。具体的には、経路設定モードになると、入出力処理部１ａは、地図表示部１ｃにディスプレイ２ａに自車位置を示す地図表示画面２Ａを表示させる。このとき、入出力処理部１ａは、地図表示画面２Ａに対して操作点５が入力されること（具体的には、操作点５の座標の連続入力）の待ち状態に移行する。
【００３４】
なお、経路設定モードに移行する操作として、メニューボタン２ｅ−２からメニュー画面を導き、経路設定操作を行うための経路設定（画面）ボタン２ｆ−３を選択する操作のみに限られない。例えば、音声認識機能による発話指示や画面上での操作を起点とするなど、他の明示的に経路探索装置に指示する手法を用いて経路設定モードを起動するようにしても良い。
【００３５】
ここで、入出力処理部１ａは、利用者による操作点５入力の待ち状態に、即ち操作入力の検出待ちの状態に移行する（ステップＳＴ２）。このあと、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いた操作点５の連続入力によって地図表示画面２Ａ上に希望する経路に対応する操作軌跡５ａを入力する。
【００３６】
入出力処理部１ａは、利用者によって操作点５の入力が行われると、当該操作点５のディスプレイ２ａ画面上の位置を検出する（ステップＳＴ３）。続いて、入出力処理部１ａは、検出した操作点５の位置をディスプレイ２ａ画面上の２次元座標系における座標値に変換し、当該座標値をＲＡＭ１ｇに一時記憶する（ステップＳＴ４）。
【００３７】
次に、利用者の操作軌跡５ａを操作点５の上記座標値の点列（表示座標列）として入力するため、入出力処理部１ａは、所定間隔ごとに操作位置の取得を実行するように時間待ちを行う。つまり、入出力処理部１ａは、前回の座標値をＲＡＭ１ｇに一時記憶した後、所定時間を経過するまで時間計測を行う。一方、所定時間が経過していれば、ステップＳＴ６の処理に移行する。
【００３８】
ステップＳＴ６において、入出力処理部１ａは、利用者の操作が完了したか否かを判定する。このとき、利用者の操作が終了していなければ、ステップＳＴ３の処理に戻って、利用者によって入力された操作点５のディスプレイ２ａ画面上の位置を検出する。このあとの処理は、上述した通りである。なお、利用者の操作入力の終了判定は、例えば前回の入力座標値との距離、タッチパネル２ｂ押下の解除（指を離す）、音声による指示、終了ボタンの押下などの種々の方式が考えられる。
【００３９】
ここで、所定間隔ごとに操作位置の取得を実行するために、ステップＳＴ５では、予め定めておいた時間を経過するごとに上記座標値を取得する方法（定時間間隔入力）を示したが、後述するような方法を利用しても良い。
【００４０】
図５は図１中の入出力処理部による操作位置の取得方法を説明する説明図であり、（ａ）は所定領域ごとに分割した地図表示画面を示し、（ｂ）は操作軌跡と地図表示画面を示し、（ｃ）は操作軌跡に対応する折れ線軌跡を示している。図５は、定位置間隔入力を説明する図である。この定位置間隔入力では、例えば（ａ）に示すように地図表示画面２Ａを同一サイズの所定領域２Ｂごとに分割する。また、各所定領域２Ｂには、代表地点（一般的には、その中心位置）２Ｃが設定されている。
【００４１】
当該地図表示画面２Ａに対して、利用者が操作軌跡５ａを入力すると、（ｂ）に示すように操作軌跡５ａを含む領域２Ｄがそれぞれ選択される。入出力処理部１ａでは、操作軌跡５ａを含む領域２Ｄが選択されると、ステップＳＴ３において、（ｃ）に示すように、その代表点２Ｃを経由地点５ｂ群とすべき操作点５として取得する。つまり、入出力処理部１ａは、操作軌跡５ａを代表点２Ｃを線分で接続した折れ線軌跡５ｃとして近似する。
【００４２】
図６は図１中の入出力処理部による操作位置の他の取得方法を説明する説明図であり、（ａ）は所定領域ごとに操作点を決定した操作軌跡を示し、（ｂ）は操作軌跡に対応する折れ線軌跡を示している。図６は、定操作間隔入力を説明する図である。この定操作間隔入力では、予め定められた操作位置範囲以上に変動したとき、操作点を取得するものである。（ａ）では、操作軌跡５ａに対して、操作開始点Ｓを中心とする半径Ｒの円２Ｅを所定の操作位置範囲とし、当該円２Ｅが交わる操作軌跡５ａ上の点を中心として半径Ｒの円２Ｅを求める。以降、同様に円２Ｅが交わる操作軌跡５ａ上の点を中心として半径Ｒの円２Ｅを操作終了点Ｇまで求めていく。
【００４３】
このようにすることで、入出力処理部１ａは、ステップＳＴ３において、（ｂ）に示すように、所定の操作位置範囲を越えるごとに操作点５を取得することができる。つまり、入出力処理部１ａは、操作軌跡５ａを操作点５を線分で接続した折れ線軌跡５ｃとして近似する。また、図５、図６に示したいずれの場合も、所定値は、平均的な操作入力の速度、経路計算精度、計算量、装置の他の動作への影響などの諸要因を考慮しながら、実験的或いは試行錯誤的に決定される。
【００４４】
図７は図１中の入出力処理部による操作位置のさらに別の取得方法を説明する説明図であり、（ａ）は接線から所定角度ごとに操作点を決定した操作軌跡を示し、（ｂ）は操作軌跡に対応する折れ線軌跡を示している。図７は、定角度間隔入力を説明する図である。この定角度間隔入力では、操作軌跡５ａに対する接線から所定角度θとなる位置を操作点として取得するものである。（ａ）では、操作軌跡５ａに対して、操作開始点Ｓから接線を求め、当該接線から所定角度θとなる直線と操作軌跡５ａとの交点を操作点５とし、当該操作点５から操作軌跡５ａに対して接線を求め、当該接線から所定角度θとなる直線と操作軌跡５ａとの交点を操作点５とする。
【００４５】
以降、接線から所定角度θとなる直線と操作軌跡５ａとの交点を操作点５として操作終了点Ｇまで逐次求めていく。このようにすることで、入出力処理部１ａは、ステップＳＴ３において、（ｂ）に示すように、各接線ごとに操作点５を取得することができる。つまり、入出力処理部１ａは、操作軌跡５ａを操作点５を線分で接続した折れ線軌跡５ｃとして近似する。この方法では、操作点５を選択する角度θは一定であるが、地点の設定タイミング及び位置間隔は可変となる。なお、図５、６、７に示した折れ線軌跡５ｃを求めるための操作点５間の線分化処理は、後述する実施の形態２において詳細に説明する。
【００４６】
ここで、図４のフローの説明に戻ると、ステップＳＴ６において、利用者の操作入力が終了していれば、ステップＳＴ７の処理に移行する。このとき、利用者による操作軌跡５ａに対応する表示座標列（ディスプレイ２ａ画面の２次元座標系における操作点５の座標値群）がＲＡＭ１ｇに一時記憶されている。
【００４７】
ステップＳＴ７において、経路設定部１ｄは、表示座標列を構成する座標値群を地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して、ディスプレイ２ａ画面の座標系から地図表示部１ｃが管理している位置座標系の座標値に変換して位置座標列とする。これにより、経路設定部１ｄは、当該位置座標列を構成する座標値群の最終データ（操作軌跡の終端）を目的地として抽出し、残りを経由地点５ｂ群として設定する。
【００４８】
続いて、経路計算処理部１ｅは、ステップＳＴ７で設定済みの経由地点５ｂ群と目的地、現在位置検出装置３及び測位処理部１ｂから得た自車位置、及び、地図情報記憶装置４が記憶・管理する数値化された地図情報を用いて、自車位置から経由地点５ｂ群を通過し目的地に至るまでの経路（誘導経路）を計算（探索）する（ステップＳＴ８）。これにより、経路探索に係る処理は、終了する。
【００４９】
最後に、利用者が経路探索装置に対して経路を設定した後、自車の走行を開始すると、上述のようにして計算された経路情報と自車位置を元に、経路誘導部１ｆが適切な案内情報（交差点・分岐での右左折指示など）を生成する。当該案内情報は、入出力処理部１ａを介してディスプレイ２ａに表示される。これにより、利用者は、安全・快適に所望の経路を使用して目的地まで誘導される。
【００５０】
以上のように、この実施の形態１によれば、利用者がディスプレイ２ａの画面上で指定した任意の経路に沿って探索経路を生成するので、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、所望の経路を利用者に提示することができる。
【００５１】
実施の形態２．
この実施の形態２による経路設定部１ｄでは、操作軌跡５ａから所定間隔ごとに取得した操作点５からなる表示座標列を線分群からなる折れ線軌跡５ｃに変換し、各線分の端点を地図の座標系に変換して経由地点５ｂ群とするものである。
【００５２】
図８はこの発明の実施の形態２による経路探索装置のディスプレイに表示した地図表示画面を示す図であり、（ａ）は利用者が入力した操作軌跡を示し、（ｂ）は（ａ）中の操作軌跡から求められた折れ線軌跡を示している。上記実施の形態１と同様にして、（ａ）に示すように、タッチパネル２ｂにより操作点５を入力することで、利用者が希望する経路に対応する操作軌跡５ａが得られる。（ｂ）に示す折れ線軌跡５ｃは、入出力処理部１ａが操作軌跡５ａから所定間隔ごとに取得した操作点５の位置座標値からなる表示座標列に対して、後述する線分化処理を施して得られる。なお、図２と同一構成要素には同一符号を付して重複する説明を省略する。
【００５３】
次に動作について説明する。
図９は実施の形態２による経路探索装置の動作を示すフロー図である。
実施の形態２による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、上述したように経路設定部１ｄの動作が異なる。そこで、図９に沿って経路設定部１ｄの動作について主に説明する。
【００５４】
先ず、ステップＳＴ１からステップＳＴ６までの処理は、上記実施の形態１と同様であるので重複する説明を省略する。ここで、ステップＳＴ１からステップＳＴ６までの一連の処理において、利用者による操作軌跡５ａは、所定間隔ごとに入出力処理部１ａによって処理され、表示座標列としてＲＡＭ１ｇに記憶されている。
【００５５】
このあと、経路設定部１ｄは、ＲＡＭ１ｇに記憶されている操作位置（操作点）の座標値群から座標点間の距離や角度などを基準として、座標点群を統合して直線化処理を実行し近似直線を得る。さらに、座標点群との位置誤差が所定範囲内に収まるように線分化を実行する。なお、上記位置誤差の所定範囲に係るデータは、例えばフラッシュメモリ１ｈ内に本発明の経路探索装置の機能を実現するプログラムと共に格納しておく。
【００５６】
上述した処理の具体例を説明する。
図１０は実施の形態２による経路設定部の線分化処理を説明する説明図である。図に示す例では、多数の座標点群から線分を決定する方法として、最小二乗法を用いている。具体的な動作としては、経路設定部１ｄが、最初に操作軌跡５ａの全ての座標点（操作点５）に対して最小二乗法による直線近似を施す。このあと、経路設定部１ｄは、近似した直線と各操作点５とのずれの二乗和を誤差として扱い、予め設定しておいた誤差範囲にあるか否かを判定する。
【００５７】
このとき、所定の誤差範囲内に二乗和がないと、経路設定部１ｄは、操作軌跡５ａを適当な線分ごとに分割し、上記と同様に最小二乗法による直線近似をそれぞれの線分に施す。図示の例では、最初に全ての操作点５に対して求めた直線５ｄが所定の誤差範囲内になく、適当な操作点５ｂａ間の線分ごとに分割されている。
【００５８】
これにより、各線分の操作点５に対する二乗和が、上述した誤差範囲内に入るまで、経路設定部１ｄは、操作軌跡５ａを線分ごとに分割する処理、最小二乗法による各線分の直線近似、及び各線分の操作点５に対する二乗和が所定誤差範囲内にあるか否かの判定を繰り返す。このようにすることで、所定の誤差範囲内の線分からなる折れ線軌跡５ｃを得ることができる。
【００５９】
上述のようにして、操作軌跡５ａに対応する折れ線軌跡５ｃが求まると、経路設定部１ｄは、折れ線軌跡５ｃの各線分の端点を抽出（節点抽出）して、これらの座標値を新たにＲＡＭ１ｇに記憶する。ここまでの処理がステップＳＴ６−１に相当する。
【００６０】
続いて、経路設定部１ｄは、ステップＳＴ６−１にて記憶した各線分の端点の座標点群を、地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して地図の座標系に変換する。さらに、経路設定部１ｄは、座標点群の最終データを目的地として抽出し、残りを経由地点５ｂ群として設定する（ステップＳＴ７）。以降のステップＳＴ８からの処理は、上記実施の形態１と同様である。
【００６１】
以上のように、この実施の形態２によれば、利用者がディスプレイ２ａ画面上で指定した任意の経路に沿って探索経路を生成するので、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択等の煩雑な操作を経ることなく、所望の経路を利用者に提示することができる。さらに、操作軌跡５ａを複数の線分に分割し各線分の節点を経由地点５ｂとするので、経由地点５ｂ群として設定する地点数を減少させることができる。このため、経路探索の高速化を期待することができる。
【００６２】
実施の形態３．
上記実施の形態１、２では、利用者が設定した任意経路に対して経由地点５ｂ群を設定し経路探索を行うにあたり、経由地点５ｂ群が主要道路（幹線道路）上に設定される保証が無い。そこで、この実施の形態３では、経由地点５ｂ群が設定されている道路の近傍に主要道路（共通属性を有する道路リンク）の共通ノード（交差節点）を通過するように経由地点を再設定するものである。
【００６３】
実施の形態３による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、経路設定部１ｄによる上述した動作が異なる。そこで、経路設定部１ｄによる経由地点の再設定処理について説明する。
【００６４】
図１１はこの発明の実施の形態３による経路探索装置の経路探索を説明する図であり、（ａ）は探索した経路を表示した地図表示画面を示し、（ｂ）は経由地点と道路リンクを示す図である。図中の星印を付した地点は、上記実施の形態１や２で示した方法で求めた経由地点５ｂ群のうちの１つである。つまり、当該地点を操作軌跡５ａが通り、入出力処理部１ａによってさらに所定間隔ごとに抽出された場合が考えられる。
【００６５】
また、操作軌跡５ａを線分ごとに分割するにあたり、当該地点が上記線分の端点に位置する場合が考えられる。このような経由地点５ｂが選択されている場合、経路計算処理部１ｅは、当該経由地点５ｂに最近傍の道路リンクから経路５ｅを算出する（経路探索）ので、以下のような不具合が生じる場合がある。
【００６６】
例えば、（ａ）に示す経路５ｅでは、星印を付した経由地点５ｂを通った道路リンクから構成されるため、地点５ｈから図中一点破線を付した幹線道路をわざわざおりて細街路に入り、星印を付した経由地点５ｂを通って幹線道路に戻るという不効率な経路となっている。つまり、幹線道路をショートカットした経路となっている。
【００６７】
一般的に、利用者は、走行しやすい幹線道路を使用できれば、道幅が狭く、幹線道路と比較して走行しにくい細街路を含む経路を意図して指定することは考え難い。また、地点５ｈでは、利用者に対して幹線道路をおりる旨の不要な案内情報が生じ、利用者を困惑させる要因となり、ひいては交通事故を発生させる可能性もある。
【００６８】
そこで、実施の形態３の経路探索装置は、上述したような不効率な経路に対して、（ａ）中で一点破線を付した２つの幹線道路の交差点、即ち（ｂ）中の共通ノード５ｆに相当する点で自車の進路を変更することで効率よい経路を再設定させるものである。
【００６９】
具体的な動作を説明する。
先ず、実施の形態３の経路設定部１ｄは、経路計算処理部１ｅが経路５ｅを算出すると、当該経路５ｅを構成する数値化された道路リンクを照査する。例えば、各経由地点５ｂの近傍に共通の属性を有する道路の交差ノードである共通ノード５ｆが存在するか否かを検査する。
【００７０】
このとき、共通ノード５ｆが存在すれば、経路設定部１ｄは、当該共通ノード５ｆの近傍の経由地点５ｂを不使用とし、代わりに当該共通ノード５ｆを新たな経由地点５ｂとして設定し直す。なお、上記道路の属性に係るデータは、例えばフラッシュメモリ１ｈ内に本発明の経路探索装置の機能を実現するプログラムと共に格納しておく。
【００７１】
この新たな経由地点５ｂを用いて、経路計算処理部１ｅが再び経路計算を行うことで、効率よい経路が再設定される。図示の例では、（ａ）中で一点破線を付した２つの幹線道路が同一属性の道路に相当し、これらの共通ノード５ｆを経由する（ｂ）中の実線を付した経路５ｇが、新たに求められる。
【００７２】
以上のように、この実施の形態３によれば、経路計算処理部１ｅが算出した経路内の各経由地点５ｂ近傍に共通の属性を有する道路の共通ノード５ｆが存在するか否かを判定し、共通ノード５ｆが存在する場合、これを新たな経由地点５ｂとして設定するので、利用者が地図中の幹線道路を意図したのにも関わらず、誤った操作点の入力、近似化の誤差などによって意図しない細街路に経由地が設定されることによる不具合を解消することができる。
【００７３】
実施の形態４．
上記実施の形態３では、同一属性の道路による共通ノードを通過させるため経由地点を設定し直す処理を示したが、この実施の形態４は共通ノードに至る道路リンクの経路探索コストを通常より下げることで共通ノードを通過させるようにしたものである。
【００７４】
実施の形態４による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、経路設定部１ｄによる上述した動作が異なる。そこで、経路設定部１ｄによる経由地点の再設定処理について説明する。
【００７５】
図１２はこの発明の実施の形態４による経路探索装置の経路探索を説明する図であり、（ａ）は各道路リンクにおける探索コストと経由地点との関係を示し、（ｂ）は経由地点を基準とした道路リンクの探索コスト変更有無を示す図である。図において、５ｉは同一属性の道路の探索に対して同一の値が設定される探索コストである。上記実施の形態では、当該探索コスト５ｉのみを用いて経路計算処理部１ｅによる経路計算が行われる。
【００７６】
これに対して、この実施の形態４では、共通ノード５ｆにおいて最も低い探索コスト５ｊを設定している。また、共通ノード５ｆの近傍における道路リンクには、共通ノード５ｆに近づくにつれて一律に低下する探索コスト５ｋが設定されている。なお、上記道路リンクと探索コストに係るデータは、例えばフラッシュメモリ１ｈ内に本発明の経路探索装置の機能を実現するプログラムと共に格納しても良いし、ＲＡＭ１ｇ上に一時的に作成・格納してもよい。
【００７７】
ここで、本発明における経路探索の方法としては、例えば出発地から目的地までに至る複数の経路候補について、それぞれの経路を構成する道路リンクの探索コストの総和を求め、これが最小となる経路を最適経路として選定する。このため、探索コストを低下させると、経路計算処理部１ｅによる経路計算の際に、当該道路リンクを利用し易くなる。このため、共通ノード５ｆを通過する経路が算出されやすくなる。
【００７８】
また、経路計算処理部１ｅによる経路計算の前に、探索コストを変更させておく対象の道路としては、（ｂ）に示すように、共通ノード５ｆに接続する道路リンクを基本とする。また、さらに拡張して探索コストを変更させる場合、共通ノード５ｆに接続している道路リンクと同一属性を有する道路のみを対象とする。
【００７９】
さらに、探索コスト低下のパターンとしては、共通ノード５ｆ近傍の道路リンク全体の探索コストを下げるように構成しても良いし、図１２中の変更探索コスト５ｋの様に予め定められたパターンに従って滑らかに変化させても良い。また、共通ノード５ｆ近傍の道路リンクの長さ、経由地点５ｂと共通ノード５ｆとの距離などに応じて探索コストのパターンを変化させるようにしても良い。
【００８０】
なお、道路リンクの探索コストを低下させることにより、所望の道路リンクを通過する経路を探索させ易くする方法を示したが、共通ノード５ｆ近傍の道路リンクの長さが短い場合、経路探索における探索コストの総和に対する影響度が少なくなる。このため、当該道路リンクを通過する経路が探索されない可能性もある。さらに、極端に探索コストを変化させると、当該道路リンクを無理矢理通過する経路が探索され、異常な経路が生成される可能性もある。
【００８１】
そこで、探索コストの変更対象となる道路リンクの長さ（共通ノード５ｆ近傍のリンク長）が短い場合には、当該道路リンクに接続する他の道路リンクも含めて探索コストの変更対象とすることなどが考えられる。また、急激な探索コストの変更による不具合を避けるために、共通ノード５ｆの探索コストを最小値とし、これから離れるに従って探索コストの低下量を低減させることが考えられる。
【００８２】
以上のように、この実施の形態４によれば、経路計算処理部１ｅが算出した経路内の各経由地点５ｂ近傍に共通属性を有する道路の交差ノードである共通ノード５ｆが存在するか否かを判定し、共通ノード５ｆが存在する場合、これの探索コストを下げることで新たな経由地点５ｂとして使用するので、利用者が地図中の幹線道路を意図したのにも関わらず、誤った操作点の入力、近似化の誤差などによって意図しない細街路に経由地点が設定されることによる不具合を解消することができる。
【００８３】
実施の形態５．
この実施の形態５では、上記実施の形態３での処理において経路設定部１ｄが設定した経由地点５ｂと共通ノード５ｆとが離れている場合、共通ノード５ｆを経由せず経由地点５ｂをそのまま利用した経路とするものである。
【００８４】
実施の形態５による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、経路設定部１ｄによる上述した動作が異なる。そこで、経路設定部１ｄによる処理について説明する。
【００８５】
図１３はこの発明の実施の形態５による経路探索装置の経路探索を説明する図である。図に示すように、この実施の形態５による経路設定部１ｄは、経由地点５ｂを中心とした所定半径ｒの円５ｌを設定し、当該円５ｌ内に共通ノード５ｆが含まれるか否かを判定する。これにより、経路設定部１ｄが設定した経由地点５ｂと共通ノード５ｆとが離れているか否かを判定するものである。なお、上記円５ｌの半径ｒの値などのデータは、例えばフラッシュメモリ１ｈ内に本発明の経路探索装置の機能を実現するプログラムと共に格納しておく。
【００８６】
次に動作について説明する。
先ず、実施の形態５による経路設定部１ｄは、経路計算処理部１ｅが経路５ｅを算出すると、当該経路５ｅを構成する数値化された道路リンクを照査する。例えば、各経由地点５ｂの近傍に位置する同一属性の道路の延長線上に共通ノード５ｆが存在するか否かを検査する。このとき、共通ノード５ｆが存在すれば、経路設定部１ｄは、図に示すように、経由地点５ｂを中心とした所定半径ｒの円５ｌを設定し、当該円５ｌ内に共通ノード５ｆが含まれるか否かを判定する。一方、共通ノード５ｆが存在しなければ、経路５ｅをそのまま設定する。
【００８７】
共通ノード５ｆが存在し、これが円５ｌ内に含まれる場合、経路設定部１ｄは、上記実施の形態３又は上記実施の形態４で説明した処理を実行して、経由地点５ｂの代わりに共通ノード５ｆを新たな経由地点５ｂとして設定する。また、共通ノード５ｆが存在し、円５ｌに含まれてない場合、経路設定部１ｄは、経由地点５ｂの変更を行わず、経路計算処理部１ｅが算出した経路５ｅをそのまま利用する。
【００８８】
図示の例では、共通ノード５ｆが存在するが、円５ｌ内には含まれていない。従って、経路設定部１ｄは、共通ノード５ｆを新たな経由地点５ｂに変更せず、経路計算処理部１ｅが算出した経路５ｅがそのまま利用される。
【００８９】
以上のように、この実施の形態５によれば、経路設定部１ｄが設定した経由地点５ｂと共通ノード５ｆとが離れている場合、共通ノード５ｆを経由せず経由地点５ｂをそのまま利用した経路とするので、不必要に遠方の経路を利用することが避けられ、省エネルギー化や環境保全に貢献することができる。
【００９０】
また、共通ノード５ｆが円５ｌ内に含まれない場合の処理として、経由地点５ｂをそのまま使う代わりに、上記実施の形態４で説明した共通ノード５ｆに至る道路の探索コストを上昇させるようにしても同様の効果を得ることができる。
【００９１】
さらに、判定用の円５ｌの半径ｒは、固定でも良いし、共通ノード５ｆに至る道路の探索コストや道路幅員などの属性値（例えば、大通りの場合は、共通ノード５ｆが離れていても利用できるよう円５ｌを大きくするなど）に応じて可変としても良い。
【００９２】
実施の形態６．
上記実施の形態１や上記実施の形態２では、利用者が設定した任意の経路に対して経由地点５ｂ群を設定し経路探索を行う。このとき、経由地点５ｂが幹線道路上に設定されている保証が無く、経由地点５ｂの位置によっては不要な経路を含む場合がある。そこで、この実施の形態６は、経由地点５ｂが幹線道路上に設定されていないために、不要な循環経路が発生しているか否かを判定し、これを含む場合に適切な経路に再設定するものである。
【００９３】
実施の形態６による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、経路設定部１ｄによる上述した動作が異なる。そこで、経路設定部１ｄによる経由地点の再設定処理について説明する。
【００９４】
図１４はこの発明の実施の形態６による経路探索装置の経路探索を説明する図であり、（ａ）は経由地点と循環経路に係る道路リンクを示し、（ｂ）は循環を排除した経路に係る道路リンクを示す図である。（ａ）に示す例では、中央に位置する幹線道路から図中右側に離れた位置にある、星印を付した経由地点５ｂが設定されている。このため、経路計算処理部１ｅが、破線を付した経路５ｅに示すように、中央の幹線道路から一旦離れて星印の経由地点５ｂを通過し、幹線道路に再び戻るという循環を含む経路を算出している。
【００９５】
そこで、実施の形態６による経路設定部１ｄは、経路計算処理部１ｅが経路５ｅを算出すると、当該経路５ｅに含まれる道路リンクを照査し、複数回使用されている道路リンク５ｍ（重複使用リンク）を抽出する（以下、リンク５ｍを重複リンクと称する）。（ａ）に示す例では、自己を通過したあとその終点から経由地点５ｂへ向かい、再びその始点に戻って重複して走行される道路リンク５ｍが中央に存在する。
【００９６】
このとき、経路設定部１ｄは、（ｂ）に示すように、重複リンク５ｍのリンク始点ノード５ｎに至るまでの経路５ｐ、重複リンク５ｍを使用する経路５ｑ、及び、重複リンク５ｍのリンク終点ノード５ｏを始点として次の経由地点に至るまでの経路５ｒを、それぞれ計算する。つまり、重複リンク５ｍの始点ノード５ｎ及び終点ノード５ｏを１回通過する経路を求める。このあと、経路設定部１ｄは、（ｂ）中に矢印を付したように、経路５ｐ、５ｑ、５ｒを統合して新規な経路として設定する。このようにすることで、循環経路を排除した経路を得ることができる。
【００９７】
以上のように、この実施の形態６によれば、経由地点５ｂ近傍で複数回の通過を要する重複リンク５ｍが存在するか否かを判定し、重複リンク５ｍの始終点ノード５ｎ，５ｏを１回通過するように経路を再設定するので、利用者が地図中の幹線道路を意図したのにも関わらず、誤った操作点の入力、近似化の誤差などによって意図しない細街路に経由地点５ｂが設定されたため、不要な循環を含む経路が生成されることを防ぐことができる。これにより、利用者に不要な困惑を与えることの無い経路を設定することが可能となる。
【００９８】
なお、上記実施の形態６において、上記実施の形態４と同様に、重複リンク５ｍの探索コストを当初の探索コストより低下させて、再計算する手法を用いても良い。また、逆に重複リンク５ｍの終点ノード５ｏから重複リンク５ｍの始点ノード５ｎに至る循環経路の探索コストを当初の探索コストより上昇させ、再計算させても同様の効果が期待できる。
【００９９】
実施の形態７．
遠距離の経路を指定する際には、広域の地図を表示させた状態で行う必要がある。この広域の地図表示では、画面の煩雑さを避けるために、一般的に主要道路のみを表示するよう構成されている。このような状態で、画面上の経路を指定する場合、利用者は、表示されている主要道路を想定した操作を行うものと考えられる。
【０１００】
そこで、この実施の形態７では、操作時に表示されていた地図の縮尺及び表示領域を地図表示部１ｃから取得し、さらに地図情報記憶装置４に記憶されている数値化地図データから当該表示領域内に含まれ、且つ当該縮尺において表示対象とされている探索道路リンクを抽出して経路計算処理部１ｅで利用するものである。
【０１０１】
なお、実施の形態７による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、経路設定部１ｄや経路計算処理部１ｅによる上述した動作やこれに用いるデータが異なる。そこで、上記実施の形態１と異なる経路探索処理について説明する。
【０１０２】
図１５はこの発明の実施の形態７による経路探索装置の経路探索を説明する図であり、（ａ）は道路リンクを示し、（ｂ）は道路リンクの構成情報ファイルの内容を示している。この図に沿って表示データと探索への使用の有無を判断する手法の１つの具体例を説明する。図において、６ａは個々の道路を線分化して表した要素の始終端を表すノード（Ｎで表記）であり、６ｂはノード間の接続を表すリンク（Ｌで表記）である。
【０１０３】
また、（ｂ）に示す表は、（ａ）で示した道路リンクについての構成情報ファイル（以下、リンクテーブルと称する）の一部を記載したものである。例えば、道路リンクＬｎは、始点ノードがＮｎ、終点ノードがＮｎ＋１であり、道路の属性値として幅員レベルが２、有料／一般の区別が０（１：有料、０：一般とする）である。幅員レベルは、広いほど数値が大きく、例えば５．５ｍ以下を０として定義する。なお、各ノードＮについての位置情報や属性値は、別の構成情報ファイル（以下、ノードテーブルと称する）で管理されているものとする。
【０１０４】
また、リンクテーブルには、（ｂ）に示すように、どの表示レベルで表示されるかについての情報も記述しておく。具体的には、表示属性として各表示レベル（例えば、レベル０を広域表示とする）に対応するフラグ（０：非表示、１：表示）が記録されている。
【０１０５】
例えば、表示レベル５では、Ｌｎ，Ｌｎ＋１，Ｌｎ＋２，・・・，Ｌｍ，Ｌｍ＋１，・・・，Ｌｏの全ての表示フラグが１であるので、これら全てが表示される。一方、表示レベル３ではＬｏが非表示となり、表示レベル１ではＬｍ，Ｌｍ＋１，・・・，Ｌｏが非表示となる。つまり、表示した地図の縮尺に応じて表示レベルを設定しておくことで、当該縮尺において表示対象とされている道路リンクのみを表示することができる。
【０１０６】
ここで、本発明の地図情報記憶装置４に記憶されている数値化地図情報は、（ａ）に示すような道路リンク及びそのノードを位置座標で表現した道路データ、及び、（ｂ）に示すような道路リンク及びそのノードに関するリンクテーブル及びノードテーブルから構成される。なお、これらのデータは、地図情報記憶装置４に格納され、必要に応じてＲＡＭ１ｇに展開され利用される。
【０１０７】
次に動作について説明する。
先ず、上記実施の形態１と同様に、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いて地図表示画面２Ａ上に操作点５を連続して入力し、希望する経路を操作軌跡５ａとして入力する。入出力処理部１ａでは、ディスプレイ２ａの画面上の操作軌跡５ａに係る座標値を取り込む。
【０１０８】
次に、入出力処理部１ａは、ディスプレイ２ａの画面上の操作軌跡５ａに係る座標値を、表示座標列の構成座標値として取得する。続いて、入出力処理部１ａは、当該座標値をＲＡＭ１ｇに一時記憶する。このあと、利用者の操作軌跡５ａを点列（表示座標列）として入力するため、入出力処理部１ａは、所定間隔ごとに操作位置の取得を実行する。
【０１０９】
利用者による操作入力が終了すると、操作軌跡５ａに対応する表示座標列（ディスプレイ２ａ画面の２次元座標系における操作点５の座標値群）がＲＡＭ１ｇに一時記憶されることとなる。このあと、経路設定部１ｄは、表示座標列を構成する座標値群を、地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して、ディスプレイ２ａ画面の座標系から地図表示部１ｃが管理している位置座標系の座標値に変換して位置座標列とする。
【０１１０】
これにより、経路設定部１ｄは、位置座標列を構成する座標値群の最終データ（操作軌跡５ａの終端）を目的地として抽出し、残りを経由地点５ｂ群として設定する。ここまでの処理は、上記実施の形態１と同様である。
【０１１１】
ここで、この実施の形態７の経路設定部１ｄでは、上述のようにして設定された経由地点５ｂ群、出発地や目的地を用いて経路を探索するにあたり、地図表示部１ｃが管理している表示状態（地図縮尺）を取得して、その地図表示レベルをＲＡＭ１ｇに記憶する。
【０１１２】
次に、経路計算処理部１ｅは、経路設定部１ｄがＲＡＭ１ｇに一時記憶させた地図表示レベルを取得して経路計算を実行する。このとき、経路計算処理部１ｅは、地図情報記憶装置４が記憶するリンクテーブルから当該地図表示レベルに対応するフラグを調査する。
【０１１３】
これにより、利用者が操作入力した地図の縮尺において、当該地図上に表示されている道路リンクやノードは使用し、非表示となっている道路リンクやノードは不使用として、上記経由地点５ｂ群、出発地や目的地を用いて経路計算を行う。以降の処理は、上記実施の形態１と同様であるので重複する説明を省略する。
【０１１４】
また、上述したものとは別の経路探索処理の具体例を説明する。
図１６は実施の形態７による経路探索装置の経路探索を説明する図であり、（ａ）は縮尺ごとに階層化した表示用及び／又は経路探索用の地図データを示し、（ｂ）は各階層における地図の表示データと経路探索データとの関係を概念的に示している。（ａ）において、縮尺ごとに階層化した各地図の数値化データを、例えば矩形領域で管理し、当該矩形領域を細分化する。
【０１１５】
そして、各矩形領域が細分化されるにつれて、より詳しい情報を含めたデータを用意する。（ａ）では、最も広域に表示される地図２Ａ−１が碁盤のように矩形領域ごとに分割して管理されており、地図２Ａ−１中のいくつかの矩形領域を合わせた領域からなる地図２Ａ−２を地図２Ａ−１の下層の地図データとして表示した例を示している。
【０１１６】
また、上述した階層化した表示用及び／又は経路探索用の地図データ２Ａ−１〜２Ａ−３は、（ｂ）に示すように、各階層ごとに図１５で示した表示レベルと対応付けて、地図情報記憶装置４に格納される。さらに、上記各階層ごとの地図データに関連付けて、経路計算処理部１ｅが使用すべき道路リンクやノードをまとめた経路探索用データも地図情報記憶装置４に格納される。
【０１１７】
（ｂ）では、経路探索用データ５Ａ−１が最も長距離の経路探索に使用され、地図２Ａ−１に関連付けて地図情報記憶装置４に格納される。続いて、経路探索用データ５Ａ−２と地図２Ａ−２が関連付けられ、近距離探索に使用される経路探索用データ５Ａ−３が地図２Ａ−３が関連付けられて地図情報記憶装置４に格納される。
【０１１８】
次に動作について説明する。
先ず、利用者が地図表示画面２Ａ上に操作点５を入力するにあたり、所望の地図の縮尺を設定する。これにより、地図表示部１ｃは、利用者が設定した縮尺に対応する表示用地図データを地図情報記憶装置４から読み出してディスプレイ２ａに表示する。このあと、上記実施の形態１と同様にして、利用者が希望する経路を操作軌跡５ａとして入力する。
【０１１９】
次に、入出力処理部１ａは、ディスプレイ２ａの画面上の操作軌跡５ａを構成する操作点５の位置を検出し、ディスプレイ２ａ画面の２次元座標系の座標値に変換してＲＡＭ１ｇに一時記憶する。このあと、入出力処理部１ａは、利用者の操作軌跡５ａを、操作点５の座標値からなる点列（表示座標列）として入力するため、所定間隔ごとに操作位置の取得を実行する。
【０１２０】
続いて、経路設定部１ｄは、上記表示座標列を構成する座標値群を地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して、ディスプレイ２ａの画面における座標系から地図表示部１ｃが管理している地図座標系に変換する。これにより、経路設定部１ｄは、座標値群の最終データ（操作軌跡の終端）を目的地として抽出し、残りを経由地点５ｂ群として設定する。
【０１２１】
このあと、経路計算処理部１ｅは、利用者が設定した縮尺に対応する表示用地図データに関連付けられた経路探索用データを地図情報記憶装置４から読み出して経路計算を実行する。これにより、経路計算処理部１ｅでは、上記経由地点５ｂ群、出発地や目的地を用いて表現できる道路リンクやノードとして、利用者が設定した縮尺に対応する経路探索用データを使って経路計算を行う。以降の処理は、上記実施の形態１と同様であるので重複する説明を省略する。
【０１２２】
上述したような階層化した地図データを使用する場合、通常は、現在地と目的地との間の距離に応じて、探索用地図の階層として下層と上層を組み合わせて用いる。しかしながら、本実施の形態７では、利用者が操作したときに用いられていた表示レベルのデータセットに応じて、経路探索に用いる経路探索データセットを切り替える、若しくは、下層レベルを制限する。
【０１２３】
以上のように、この実施の形態７によれば、操作時に表示されていた地図の縮尺及び表示領域を地図表示部１ｃから取得し、地図情報記憶装置４に記憶されている数値化地図データから当該表示領域内に含まれ、且つ当該縮尺において表示対象とされている探索道路リンクを抽出して経路計算に利用するので、地図の表示に対応した道路データを用いて探索を行うことが可能となる。
なお、この実施の形態７の構成は、本発明の全ての実施の形態に適用できる。
【０１２４】
実施の形態８．
図１７はこの発明の実施の形態８による経路探索装置の経路探索を説明する図であり、（ａ）は利用者が入力した操作軌跡を示し、（ｂ）は検査領域を設けて新たな経由地点を設定する処理を概略的に示している。図において、７ａは経由地点５ｂに基づいて近隣の主要道路上に対して設定された経由地点である。なお、図２と同一構成要素には同一符号を付して重複する説明を省略する。
【０１２５】
次に動作について説明する。
ここで、実施の形態８による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、上記実施の形態１と経路探索処理が異なる。そこで、この異なる箇所について詳細に説明する。
【０１２６】
先ず、実施の形態８の経路設定部１ｄは、利用者の操作に従って設定された各経由地点５ｂ（例えば、上記実施の形態１や２に示す所定時間ごとの操作点５群、若しくは、線分化された操作軌跡５ａの節点群）について、地図情報記憶装置４に記憶されている数値化地図及び地図表示部１ｃが管理している表示領域情報を基にして、各地点５ｂ近傍の主要道路（幹線道路）に対応する道路リンクを参照する。このようにして抽出された主要道路リンク上に各地点５ｂに対応する新たな経由地点７ａを設定する。
【０１２７】
具体的に説明すると、経路設定部１ｄは、（ｂ）に示すように、星印を付した地点５ｂを中心とした所定半径の円からなる検査領域７ｃを設定し、当該検査領域７ｃに道路リンクの両端ノードが含まれる道路リンクを抽出する。続いて、経路設定部１ｄは、地図情報記憶装置４に記憶されている地図情報を用いて、検査領域７ｃに含まれる道路リンクの属性を判別する。
【０１２８】
このあと、検査領域７ｃに含まれるとして抽出した道路リンクの属性が、予め定めた属性の道路リンクであれば、経路設定部１ｄは、当該道路リンクを選択して、これと星印を付した経由地点５ｂとの距離を判定する。そして、当該距離が最小となる道路リンク上の位置を新たな経由地点７ａとして設定する。
【０１２９】
（ｂ）の例において、検査領域７ｃに含まれる上記道路リンクと星印を付した経由地点５ｂとの距離が最小となるのは、上記経由地点５ｂから上記道路リンクに対して下ろした垂線の上記道路リンク上の交点の位置である。即ち、この点が経由地点７ａに相当する。
【０１３０】
続いて、経路計算処理部１ｅは、経路設定部１ｄが設定した経由地点７ａ群を利用して、現在地から経由地点７ａ群を経由し目的地に至る経路７ｂを算出する。このあと、自車の走行を開始すると、上述のようにして計算された経路７ｂに関する情報と自車位置を元に、経路誘導部１ｆが適切な案内情報（交差点・分岐での右左折指示など）を生成する。当該案内情報は、入出力処理部１ａを介してディスプレイ２ａに表示される。これにより、利用者は、安全・快適に所望の経路を使用して目的地まで誘導される。
【０１３１】
以上のように、この実施の形態８によれば、経由地点５ｂ近傍に予め定めた属性の道路リンクが存在する場合、当該道路リンク上に新たな経由地点７ａを設定し、これを用いて経路を算出するので、利用者が地図中の幹線道路を意図したにも関わらず、誤った操作点の入力、近似化の誤差などによって意図しない細街路に経由地点が設定されることによる不具合を解消することができる。
【０１３２】
また、上述のように自動的に主要道路上に新たに経由地点７ａが設定されることから、上記実施の形態３や上記実施の形態６に示したような経路計算後の重複リンクやショートカットなどの判定が不要となり、経路探索を高速化することができるという利点がある。
【０１３３】
なお、上記実施の形態８では、検査領域７ｃによる検査対象として道路リンクやノードを用いる例を示したが、上記実施の形態７と同様に利用者の操作時点で表示されていた道路リンクやノードを対象としてもよい。このようにすることで、上述した効果に加え、利用者の操作時点で表示されていた道路を優先して経路設定がなされるようになり、より利用者の希望に合致した経路を提示することが可能となる。
【０１３４】
実施の形態９．
上記実施の形態１から上記実施の形態８までの経路探索装置では、利用者が入力した操作軌跡５ａを経由地点５ｂ群に変換した例を示した。この場合、利用者が入力した操作軌跡５ａを経由地点５ｂ群と共に表示して、希望する経路に沿った経由地点５ｂ群が表示されているかどうかを確認できることが望ましい。
【０１３５】
また、上記実施の形態３から上記実施の形態８までの経路探索装置のように、利用者が入力した操作点５に対応する経由地点５ｂを不使用とし、経路探索装置側で新たに経由地点（例えば、共通ノード５ｆや経由地点７ａ）を設定する場合、設定語の経由地点群のみ表示すると見かけ上は、利用者が設定した地点を通過しないこととなり、無用な混乱を招く恐れがある。
【０１３６】
そこで、この実施の形態９による経路探索装置では、利用者が設定した経由地点５ｂ以外の地点を新たに設定した場合、当該地点と共に利用者が設定した経由地点５ｂ群を表示し、さらに新たに設定した経由地点とこれに取って代わられる経由地点に対して異なる記号を付し、希望する経路に沿った経由地点５ｂ群が設定されているかどうかを確認できるようにしたものである。
【０１３７】
図１８はこの発明の実施の形態９による経路探索装置のディスプレイに表示される画面を示す図である。図中の経由地点５ｂは、上記実施の形態１と同様にして利用者が設定したものであり、丸形の吹き出し記号が付されている。また、経由地点７ａは、上記実施の形態８と同様にして経路探索装置が設定したものであり、矩形の吹き出し記号が付されている。
【０１３８】
ここで、吹き出し内部のＷ１やＷ２は、それぞれ互いに対応する経由地点であることを示すために記載したものである。このようにすることで、経路探索装置側の自動設定機能によって設定された経由地点が、希望する経路に沿っているかどうかを容易に確認することができる。
【０１３９】
なお、それぞれの地点マークは両者が弁別可能であれば良く、ここに挙げた形状以外でも機能を満たすことは言うまでもない。
【０１４０】
以上のように、この実施の形態９によれば、利用者が入力した操作軌跡５ａから求めた経由地点５ｂと、当該経由地点５ｂに代わって新たに設定した経由地点７ａとを、異なる記号で表示するので、利用者の操作内容と経路探索装置側の動作内容（経路の根拠）を同時に利用者にフィードバックすることが可能となり、不要な混乱が避けられ、装置に対する信頼感を向上させることができる。
【０１４１】
なお、上記実施の形態９では、経由地点５ｂ，７ａの両方を表示するよう構成した。しかしながら、両者を表示することは、車載機器のような面積の小さなディスプレイの場合や、経路長が長く屈曲が大きいような場合には、多数の吹き出し記号が表示され画面が煩雑となる。そこで、経由地点５ｂ，７ａのいずれかを表示しないように構成してもよい。
【０１４２】
この場合、例えば縮尺の大小や画面中に含まれる経由地点の数などに応じて、経由地点５ｂ，７ａのいずれかを表示しないようにする設定を自動的に可変とする。具体的に説明すると、利用者が操作入力した地図の縮尺が小さい（詳細地図）場合、１つの画面に表示可能な地点数は、自ずと少なくなり、また、経由地点５ｂ，７ａの位置の特定も容易である。
【０１４３】
このため、縮尺が小さい地図（詳細地図）上に経由地点５ｂ，７ａを同時に表示することによって、利用者自身の操作内容と経路探索装置の動作内容（経由地点を自動的に移動させるなど）や、その操作結果と経路探索装置が決定した経路に差異が発生したか否かなどを容易に確認することができる。
【０１４４】
これに対して、利用者の操作によって地図の縮尺が大きくなる方向に変更されると、画面に表示される地点数も多くなり、経由地点５ｂ，７ａ間の位置差が小さくなりこれらの特定も困難となる。さらに、縮尺が最も大きくなる（広域の地図表示）場合、地図情報の全体像（経路、地域など）が必要であり、詳細な経由地点５ｂなどの情報は不要である。
【０１４５】
このような場合、経由地点５ｂ，７ａのいずれか、若しくは、両方を表示しないようにすることで、利用者の意図にも応えることができ、画面上の情報の整理が容易となる。
【０１４６】
また、利用者に事前に若しくは表示時に、経由地点５ｂ，７ａのいずれか、若しくは、両方を表示しないように選択させる構成にしても良い。
【０１４７】
さらに、経路設定のシーケンスに応じて経由地点５ｂ，７ａのいずれか、若しくは、両方の表示の有無を可変としても良い。例えば、利用者の操作による経路設定の直後では、正しく操作ができたかどうかをチェックするために経由地点５ｂを表示する。このあと、経路探索装置によって経由地点５ｂが適否判定、移動操作を実行した結果として経由地点７ａを表示する場合、経由地点５ｂも同時に表示する。
【０１４８】
これにより、利用者は、自己が入力した経由地点５ｂが移動して経由地点７ａとなったことを確認することができる。最後に、利用者が自車の走行を開始すると経由地点７ａのみを表示する。
【０１４９】
このようにすることで、利用者の操作内容と経路探索装置の動作内容を適切なタイミング・表示条件に応じて利用者に提示することが可能となり、経由地点を表示する上での煩雑さを避けることができ、ひいては安全運転に寄与することが可能となる。
【０１５０】
実施の形態１０．
図１９はこの発明の実施の形態１０による経路探索装置のディスプレイに表示した地図表示画面を示す図であり、（ａ）は利用者が入力した操作軌跡を示し、（ｂ）は（ａ）中の操作軌跡に基づいて求めた経路計算領域を示している。図において、８は操作軌跡５ａに基づいて求めた経路計算領域であって、例えば操作軌跡５ａから求めた表示座標列の近似曲線に沿って所定半径の包絡円を移動させることで設定する。なお、図２と同一構成要素には同一符号を付して重複する説明を省略する。
【０１５１】
図２０は実施の形態１０の経路探索装置による経路計算領域の設定処理を説明する図である。図において、８ａは操作軌跡５ａから求めた表示座標列の近似曲線、８ｂは近似曲線８ａに沿った経路計算領域８を求めるために用いる包絡円である。
【０１５２】
次に動作について説明する。
図２１は実施の形態１０による経路探索装置の動作を示すフロー図である。この実施の形態１０による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、後述する経路探索処理が上記実施の形態１と異なる。そこで、図２１のフローに沿って主に上記実施の形態１と異なる処理について詳細に説明する。
【０１５３】
先ず、上記実施の形態１と同様にして、利用者が経路探索装置の経路設定モードを起動する（ステップＳＴ１）。これにより、入出力処理部１ａは、利用者による操作点５入力の待ち状態に、即ち操作入力の検出待ちの状態に移行する（ステップＳＴ２）。このあと、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いた操作点５の連続入力によって地図表示画面２Ａ上に希望する経路に対応する操作軌跡５ａを入力する。
【０１５４】
入出力処理部１ａは、利用者によって操作点５の入力が行われると、当該操作点５のディスプレイ２ａ画面上の位置を検出する（ステップＳＴ３）。続いて、入出力処理部１ａは、検出した操作点５の位置をディスプレイ２ａ画面上の２次元座標系における座標値に変換し、当該座標値をＲＡＭ１ｇに一時記憶する（ステップＳＴ４）。
【０１５５】
次に、利用者の操作軌跡５ａを操作点５の上記座標値の点列（表示座標列）として入力するため、入出力処理部１ａは、所定間隔ごとに操作位置の取得を実行するように時間待ちを行う。つまり、入出力処理部１ａは、前回の座標値をＲＡＭ１ｇに一時記憶した後、所定時間を経過するまで時間計測を行う。一方、所定時間が経過していれば、ステップＳＴ６の処理に移行する。
【０１５６】
ステップＳＴ６において、入出力処理部１ａは、利用者の操作が完了したか否かを判定する。このとき、利用者の操作が終了していなければ、ステップＳＴ３の処理に戻って、利用者によって入力された操作点５のディスプレイ２ａ画面上の位置を検出する。このあとの処理は、上述した通りである。なお、利用者の操作入力の終了判定は、例えば前回の入力座標値との距離、タッチパネル２ｂ押下の解除（指を離す）、音声による指示、終了ボタンの押下などの種々の方式が考えられる。ここまでの処理は、上記実施の形態１と同様である。
【０１５７】
一方、ステップＳＴ６において、利用者の操作が終了していれば、ステップＳＴ７ａの処理に移行する。このとき、利用者による操作軌跡５ａに対応する表示座標列（ディスプレイ２ａの画面上の座標値群）がＲＡＭ１ｇに一時記憶されている。
【０１５８】
ステップＳＴ７ａにおいて、経路設定部１ｄは、ステップＳＴ４にて記憶した表示座標列を構成する座標値群を、地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して、ディスプレイ２ａの画面上の座標系から地図表示部１ｃが管理している位置座標系の座標値に変換して位置座標列とする。
【０１５９】
このあと、経路設定部１ｄは、位置座標列を構成する座標値群の最終データ（操作軌跡５ａの終端）を目的地として抽出すると共に、上記位置座標列を所定の自由曲線関数に変換して近似曲線８ａを求める。
【０１６０】
続いて、経路設定部１ｄは、上記近似曲線８ａを基準として所定幅の経路計算領域８を設定する（ステップＳＴ８ａ）。この自由曲線関数への変換は、例えば公知のベジェ曲線、ｎ次スプライン曲線などの変換公式を用いる方法がある。また、所定幅の経路計算領域の設定法としては、例えば図２０に示すような自由曲線関数を用いて変換された近似曲線８ａに対して、所定半径ｒの包絡円８ｂを設定し、且つ近似曲線８ａに沿って包絡円８ｂを移動することで設定する。
【０１６１】
上述のようにして目的地及び経路計算領域が設定されると、経路計算処理部１ｅは、地図情報記憶装置４に記憶・管理されている数値化地図を参照し、自車位置から目的地に至る経路が経路計算領域８内に包含されるように経路計算を実行する（ステップＳＴ９ａ）。
【０１６２】
ステップＳＴ９ａにおける処理を具体的に説明する。
図２２は経路計算領域と道路リンクとの関係を説明する図である。図において、８ｃは図１９（ｂ）中の経路計算領域の一部であって、図２１のステップＳＴ８ａにて地図表示画面上に設定したものに相当する。図示の例では、経路計算領域８ｃの機能を明確に説明するため、地図情報記憶装置４に記憶した数値化地図情報に含まれる、図１９中の表示地図内の道路に対応する道路データ（道路リンクやそのノードなど）を表示している。８ｄは経路探索の対象外の道路リンクであり、８ｅは経路探索の対象となる道路リンクである。
【０１６３】
経路計算処理部１ｅは、経路を算出するにあたり、上述した経路計算領域８ｃと数値化地図情報中の道路リンクのノードデータを比較し、道路リンクの両端のノードのそれぞれの座標値が経路計算領域８ｃに含まれているか否かを判定する。このとき、道路リンクの両端のノードが経路計算領域８ｃに含まれていれば、探索対象リンク８ｅとしてＲＡＭ１ｇに一時記憶し、両端のノードのいずれかが含まれていなければ、図２２中に破線で示したように経路探索の対象外の道路リンク８ｄとして経路探索処理に使用しない。
【０１６４】
このあと、自車の走行を開始すると、上述のようにして探索された経路に関する情報と自車位置を元に、経路誘導部１ｆが適切な案内情報（交差点・分岐での右左折指示など）を生成する。当該案内情報は、入出力処理部１ａを介してディスプレイ２ａに表示される。これにより、利用者は、安全・快適に所望の経路を使用して目的地まで誘導される。
【０１６５】
以上のように、この実施の形態１０によれば、ディスプレイ２ａに表示した地図画像に対して指示された操作軌跡５ａに沿って経路計算領域８を設定し、当該経路計算領域８内に含まれる道路データを用いて所望の経路に応じた誘導経路を算出するので、利用者がディスプレイ２ａ画面上で指定した任意の経路に沿って探索経路を生成することができることから、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、所望の経路を利用者に提示することができる。
【０１６６】
実施の形態１１．
上記実施の形態１０では、利用者の操作軌跡５ａに対して近似曲線化を行った後に経路計算領域８を設定するものであったが、この実施の形態１１は、利用者による操作軌跡５ａの入力時に経路計算領域８を設定するものである。
【０１６７】
この実施の形態１１による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、後述する経路探索処理が上記実施の形態１と異なる。
【０１６８】
図２３はこの発明の実施の形態１１による経路探索装置の経路計算領域の設定過程を説明する図である。図において、５ａ−１は利用者によってこれから操作されるべき操作軌跡であって、実線で表した操作済みの操作軌跡５ａと区別するために破線で表している。なお、図２０と同一構成要素には同一符号を付して重複する説明を省略する。
【０１６９】
次に動作について説明する。
図２４は実施の形態１１による経路探索装置の動作を示すフロー図であり、この図に沿って経路計算領域の設定処理について詳細に説明する。
先ず、上記実施の形態１と同様にして、利用者が経路探索装置の経路設定モードを起動する（ステップＳＴ１）。これにより、入出力処理部１ａは、利用者による操作点５入力の待ち状態に、即ち操作入力の検出待ちの状態に移行する（ステップＳＴ２）。このあと、利用者がタッチパネル２ｂやリモートコントローラ２ｃを用いた操作点５の連続入力によって地図表示画面２Ａ上に希望する経路に対応する操作軌跡５ａを入力する。
【０１７０】
入出力処理部１ａは、利用者によって操作点５の入力が行われると、当該操作点５のディスプレイ２ａ画面上の位置を検出する（ステップＳＴ３）。続いて、入出力処理部１ａは、検出した操作点５の位置をディスプレイ２ａ画面上の２次元座標系における座標値に変換し、当該座標値をＲＡＭ１ｇに一時記憶する（ステップＳＴ４）。ここまでの処理は、上記実施の形態１と同様である。
【０１７１】
次に、経路設定部１ｄは、ステップＳＴ４にてＲＡＭ１ｇに記憶した操作点５の座標値を読み出して、当該操作点５を中心とした所定半径の包絡円８ｂを設定する（ステップＳＴ５ｂ）。ここで、上記包絡円８ｂは、ディスプレイ２ａ画面の２次元座標系で表現したものである。
【０１７２】
続いて、経路設定部１ｄは、前回取り込んだ操作点５に係る包絡円８ｂに今回設定した包絡円８ｂを追記した領域を求めてＲＡＭ１ｇに一時記憶する（ステップＳＴ６ｂ）。つまり、前回取り込んだ操作点５に係る包絡円８ｂと今回設定した包絡円８ｂとの和からなる領域を経路計算領域８として逐次記憶する。このとき、経路設定部１ｄは、経路計算領域８を位置座標系に変換した後、ＲＡＭ１ｇに記憶する。
【０１７３】
また、上述したステップＳＴ５ｂの包絡円８ｂの設定処理、若しくは、ステップＳＴ６ｂの経路計算領域８の追記・記憶処理において、経路設定部１ｄは、地図情報記憶装置４に記録した数値化地図情報に含まれる道路データ（道路リンクやそのノードなど）を参照して、経路計算領域８に含まれる道路データを求める。この道路データは、地図表示部１ｃが管理している位置座標系で表されていることから、ＲＡＭ１ｇに記憶した経路計算領域８とそのまま比較することができる。
【０１７４】
続いて、利用者の操作軌跡５ａを操作点５の上記座標値の点列（表示座標列）として入力するため、入出力処理部１ａは、所定間隔ごとに操作位置の取得を実行するように時間待ちを行う（ステップＳＴ７ｂ）。つまり、入出力処理部１ａは、前回の座標値をＲＡＭ１ｇに一時記憶した後、所定時間を経過するまで時間計測を行う。一方、所定時間が経過していれば、ステップＳＴ８ｂの処理に移行する。
【０１７５】
ステップＳＴ８ｂにおいて、入出力処理部１ａは、利用者の操作が完了したか否かを判定する。このとき、利用者の操作が終了していなければ、ステップＳＴ３の処理に戻って、利用者によって入力された操作点５のディスプレイ２ａ画面上の位置を検出する。このあとの処理は、上述した通りである。なお、利用者の操作入力の終了判定は、例えば前回の入力座標値との距離、タッチパネル２ｂ押下の解除（指を離す）、音声による指示、終了ボタンの押下などの種々の方式が考えられる。
【０１７６】
一方、ステップＳＴ８ｂにおいて、利用者の操作入力が終了していれば、ステップＳＴ９ｂの処理に移行する。このとき、利用者による操作軌跡５ａに対応する表示座標列（ディスプレイ２ａ画面の２次元座標系における操作点５の座標値群）と、経路計算領域８内に存在する道路データがＲＡＭ１ｇに一時記憶されている。
【０１７７】
ステップＳＴ９ｂにおいて、経路設定部１ｄは、ステップＳＴ４にて記憶した表示座標列を構成する座標値群を、地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して、ディスプレイ２ａの画面上の座標系から地図表示部１ｃが管理している位置座標系の座標値に変換して位置座標列とする。これにより、経路設定部１ｄは、位置座標列を構成する座標値群の最終データ（操作軌跡５ａの終端）を目的地として抽出し、残りを経由地点５ｂ群として設定する。
【０１７８】
続いて、経路計算処理部１ｅは、経由地点５ｂ群と目的地、経路計算領域８内に存在する道路データ、及び、現在位置検出装置３及び測位処理部１ｂから得た自車位置を用いて、自車位置から経由地点５ｂ群を通過し目的地に至るまでの経路を計算（探索）する。これにより、経路探索に係る処理は、終了する。
【０１７９】
なお、上述した説明では、利用者の操作入力の途中過程で逐次設定した経路計算領域８を位置座標系に変換してＲＡＭ１ｇに格納する旨を示したが、経路設定部１ｄがディスプレイ２ａ画面の２次元座標系で経路計算領域８を記憶し、ステップＳＴ９ｂにおける経路探索の際に、位置座標系に変換して地図情報との参照を行うようにしても良い。
【０１８０】
最後に、利用者が経路探索装置に対して経路を設定した後、自車の走行を開始すると、上述のようにして計算された経路情報と自車位置を元に、経路誘導部１ｆが適切な案内情報（交差点・分岐での右左折指示など）を生成する。当該案内情報は、入出力処理部１ａを介してディスプレイ２ａに表示される。これにより、利用者は、安全・快適に所望の経路を使用して目的地まで誘導される。
【０１８１】
以上のように、この実施の形態１１によれば、ディスプレイ２ａに表示した地図画像に対して操作軌跡５ａを指示する際に経路計算領域８を設定し、当該経路計算領域８内に含まれる道路データを用いて所望の経路に応じた誘導経路を算出するので、利用者が画面上で任意の経路を指定中に、経路計算領域８を設定できることから、近似曲線の生成、近似曲線から領域の生成などの処理を省略することができ、経路探索動作を簡略化、高速化することが可能となる。
【０１８２】
実施の形態１２．
この実施の形態１２は、利用者が設定した操作軌跡５ａを線分化し、各線分に対して経路計算領域を設定するものである。
【０１８３】
図２５はこの発明の実施の形態１２による経路探索装置の経路計算領域の設定処理を説明する図であり、（ａ）は折れ線軌跡と各線分に対応する経路計算領域を表示した地図表示画面を示し、（ｂ）から（ｅ）までは折れ線軌跡の各線分に対応して設定する種々の形状の経路計算領域を示している。図において、５ｃａは折れ線軌跡５ｃを構成する線分であり、８ｆは折れ線軌跡５ｃの各線分５ｃａに対応して設定される経路計算領域である。
【０１８４】
次に動作について説明する。
この実施の形態１２による経路探索装置は、上記実施の形態１による構成と基本的に同一であるので、上記実施の形態１と異なる経路計算領域の設定処理について詳細に説明する。
先ず、上記実施の形態１で示した図４中のステップＳＴ１からステップＳＴ６までと同様の処理を実行して、利用者による操作軌跡５ａを所定間隔ごとに取得した操作点５の座標値群としてＲＡＭ１ｇに記憶する。
【０１８５】
次に、経路設定部１ｄは、上記実施の形態２と同様にして、ＲＡＭ１ｇに記憶されている操作位置（操作点）の座標値群から座標点間の距離や角度などを基準として、座標点群を統合して直線化処理を実行し近似直線を得る。さらに、座標点群との位置誤差が所定範囲内に収まるように線分化を実行する。
【０１８６】
上述の処理を施すことによって、（ａ）に示すような、操作軌跡５ａに対応する折れ線軌跡５ｃが求まると、経路設定部１ｄは、折れ線軌跡５ｃの各線分５ｃａの端点を抽出（節点抽出）して、これらの座標値を新たにＲＡＭ１ｇに記憶する。
【０１８７】
続いて、経路設定部１ｄは、記憶した各線分５ｃａの端点の座標点群を、地図表示部１ｃが管理している地図の表示領域情報（緯度経度座標、正規化座標など）と参照して地図の座標系に変換する。さらに、経路設定部１ｄは、上記線分５ｃａを基準として所定の経路計算領域８ｆを設定する。
【０１８８】
上述のようにして経路計算領域が設定されると、経路計算処理部１ｅは、地図情報記憶装置４に記憶・管理されている数値化地図を参照し、自車位置から目的地に至る経路が各線分５ｃａに対応した経路計算領域８ｆ内に包含されるように経路計算を実行する。
以降の処理は、上記実施の形態１と同様であるので説明を省略する。
【０１８９】
次に、（ｂ）から（ｅ）までに示した経路計算領域８ｆについて説明する。
（ｂ）に示した経路計算領域８ｆは、折れ線軌跡５ｃの線分５ｃａの端点が短辺の中心位置に一致し、当該線分５ｃａから長辺までが所定幅ｄとなる矩形形状を有している。この経路計算領域８ｆは、線分５ｃａによってその形状が規定される。これにより、経路設定部１ｄによる経路計算領域８ｆの設定を容易に実行することができる。
【０１９０】
また、線分５ｃａから所定幅ｄだけ離れた長辺までに含まれるか否かで、経路計算に使用すべき道路データを容易に判定することができる。これらの利点を考慮すると、（ｂ）に示すような矩形の経路計算領域８ｆを採用することで、経路計算の高速化を期待することができる。
【０１９１】
（ｃ）に示した経路計算領域８ｆは、折れ線軌跡５ｃの線分５ｃａを内部に含む矩形形状を有している。この形状は、（ｂ）に示した経路計算領域８ｆにおける不具合を解消するためのものである。つまり、折れ線軌跡５ｃの各線分５ｃａに、（ｂ）に示した経路計算領域８ｆを設定すると、（ａ）に示すように、線分５ｃａ間の接続点近傍で、それぞれに対応する経路計算領域８ｆ同士が重ならない部分が生じることがある。
【０１９２】
このような重なりのない部分に、例えば経路計算に使用すべき道路リンクのノードの一方が含まれた場合、当該道路リンクは経路計算に使用できなくなる。そこで、（ｃ）に示した経路計算領域８ｆのように、線分５ｃａを内部に含む矩形とすることで、線分５ｃａ間の接続点近傍で、それぞれに対応する経路計算領域８ｆ同士を確実に重ならせることができる。従って、上述したような経路計算に使用すべき道路リンクが不使用となることがない。
【０１９３】
（ｄ）に示した経路計算領域８ｆは、折れ線軌跡５ｃの線分５ｃａを内部に含む楕円形状を有している。楕円形状では、線分５ｃａの中央付近に対応する部分の幅が拡がる。これにより、操作軌跡５ａの入力時、操作軌跡５ａの線分化処理時における弊害を抑制することができる。以下に具体的に説明する。
【０１９４】
図２６は経路計算領域の矩形と楕円の違いによる効果を説明する説明図であり、（ａ）は楕円形状の経路計算領域の短辺が矩形形状の経路計算領域の幅より大きい場合を示し、（ｂ）は楕円形状の経路計算領域と矩形形状の経路計算領域の長辺及び短辺が等しい場合を示している。（ａ）に示す場合において、矩形形状の経路計算領域８ｆでは、線分５ｃａの中央付近に対応する部分の幅が拡がることがない。
【０１９５】
このため、破線を付した折れ線軌跡５ｃは内部に含まれるが、道路リンク８Ａ，８Ｂは領域外に出てしまい、経路計算の対象とはならない。一方、楕円形状の経路計算領域８ｆでは、線分５ｃａの中央付近に対応する部分の幅が拡がるため、道路リンク８Ａ，８Ｂも領域内に含めることができる。このため、破線を付した折れ線軌跡５ｃと共に、道路リンク８Ａ，８Ｂも経路計算の対象とすることができる。
【０１９６】
また、（ｂ）に示す場合において、楕円形状の経路計算領域８ｆでは、線分５ｃａ間の接続点近傍で、矩形形状のものと比較して領域８Ｃだけ計算量を削減することができる。つまり、（ｂ）に示すように、経路計算に使用すべきデータとして折れ線軌跡５ｃ、及び道路リンク８Ａ，８Ｂがある場合、これらを楕円及び矩形形状のいずれもが含んでいる。
【０１９７】
これにも関わらず、矩形形状の経路計算領域８ｆでは、楕円形状のものと比較して、道路データ内包の有無を判定する計算を、領域８Ｃの分だけ余計に実行しなければならない。このように、楕円形状の経路計算領域８ｆでは、短辺及び長辺が同一長さの矩形のものと比較して、計算量を削減することができる。
【０１９８】
最後に、図２５（ｅ）に示す経路計算領域８ｆは、線分５ｃａを直径とする円形を有している。この経路計算領域８ｆは、線分５ｃａによってその形状が規定される。これにより、経路設定部１ｄによる経路計算領域８ｆの設定を容易に実行することができる。また、円内に含まれるか否かで、経路計算に使用すべき道路データを容易に判定することができる。これらの利点を考慮すると、（ｅ）に示すような矩形の経路計算領域８ｆを採用することで、経路計算の高速化を期待することができる。
【０１９９】
以上のように、この実施の形態１２によれば、操作軌跡５ａを複数の線分に分割すると共に、各線分に応じて経路計算領域８ｃを設定し、各経路計算領域８ｃ内の道路に関する道路データを用いて、所望の経路に応じた誘導経路を算出するので、利用者の操作軌跡を線分化することにより経路計算領域が複数の幾何的領域に分割・管理することができることから、経路探索に係る処理負荷を軽減することができる。これにより、経路探索の高速化や軽快な操作反応を利用者に提供することが可能となる。
【０２００】
実施の形態１３．
上記実施の形態１０から上記実施の形態１２までに示した経路探索装置では、経路計算領域８内において、経路探索の出発点に対応する座標値から数値化地図情報中の道路リンクを順次追跡する。このとき、目的地まで到達できた座標列からなる経路のうち、時間や距離に対応する通過コストが最小となるものを最適な経路とする。具体的には、例えば最短路を求めるダイクストラ法やＡ＊法などのリンク探索アルゴリズムなどを用いる。
【０２０１】
この実施の形態１３では、上述した探索アルゴリズムに沿って経路探索を行うにあたり、探索した道路リンク列の終端が予め設定しておいた経路計算領域内から逸脱した時点で、当該道路リンク列を用いた探索を打ち切るようにしたものである。
【０２０２】
なお、この実施の形態１３による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、上述したように経路探索処理に係るアルゴリズムが上記実施の形態１０から上記実施の形態１２までと異なる。そこで、実施の形態１３の特徴的な経路探索処理について詳細に説明する。
【０２０３】
図２７はこの発明の実施の形態１３による経路探索装置の経路探索処理を説明する図であり、（ａ）は経路探索の概念図を示し、（ｂ）は探索打ち切りを決定する際の経路計算領域と道路リンクとの関係を示している。（ａ）に示すように、経路計算処理部１ｅは、ダイクストラ法などに従って、出発点Ｓを起点に順次接続する経由地点（ノード）の選択を実行してゆく。
【０２０４】
（ａ）に示す例で具体的に説明すると、出発点Ｓに道路リンクを介して接続するノードａ１，ｂ１のうち、距離や走行時間が最短となるノードｂ１が選択される。次に、ノードｂ１に道路リンクを介して接続するノードｃ１，ｂ２のうち、距離や走行時間が最短となるノードｂ２が選択される。これにより、出発地点Ｓ→ノードｂ１→ノードｂ２を経由する道路リンク列が求められる。続いて、ノードｂ３，ｂ４，・・・と選択されて、目的地Ｇまでの最短経路に対応する道路リンク列が求められる。
【０２０５】
上述した経路探索処理において、この実施の形態１３による経路計算処理部１ｅでは、予め設定しておいた経路計算領域８ｃから道路リンクやそのノードがはずれた場合、当該道路リンクを含む道路リンク列を経路探索処理の対象から外すようにする。
【０２０６】
具体的には、（ｂ）に示すように、下方より継続してきた道路リンク列の終端ノード８ｈから、さらに次の道路リンクを探索するにあたり、経路計算処理部１ｅが、終端ノード８ｈに接続している他の道路リンクの終端ノードの座標を参照する。
【０２０７】
このとき、道路リンク８ｇのように、終端ノードの座標が経路検索領域８ｃの外部にあれば、当該道路リンク８ｇの探索への使用を打ち切る。一方、経路検索領域８ｃの内部にあれば、当該道路リンクを使用した探索を継続する。このような動作を繰り返し行うことにより、経路検索領域８ｃに含まれる経路を計算することが可能となる。
【０２０８】
以上のように、この実施の形態１３によれば、探索した道路リンク列の終端が予め設定しておいた経路計算領域８ｃ内から逸脱した時点で、当該道路リンク列を用いた探索を打ち切るようにしたので、経路検索領域８ｃに含まれる道路リンクを再構成しＲＡＭ１ｇに蓄えておく必要が無く、使用するリソースを少なく抑えることができる。これにより、本発明を導入するために必要なコストを削減することができる。
【０２０９】
実施の形態１４．
通常の経路探索では、探索の始点から数値化地図情報中の道路リンクを順次追跡し、目的地まで到達した道路リンク列から経路全体の通過コストが最小となるものが最適な経路として利用される。つまり、経路探索は、選択された経路全体の通過コストによって制御される。
【０２１０】
この実施の形態１４では、数値化地図情報において経路計算領域内に存在する道路リンクの通過コストを周囲に比べて低下させておくか、若しくは、経路計算領域外に存在する道路リンクの通過コストを上昇させておく。これによって、結果的に経路計算領域内に存在する道路リンクを用いて出発地から目的地に至る経路を算出するものである。
【０２１１】
なお、この実施の形態１４による経路探索装置は、上記実施の形態１による構成と基本的に同一であるが、上述したように経路探索処理に係るアルゴリズムが上記実施の形態１０から上記実施の形態１２までと異なる。そこで、実施の形態１４の特徴的な経路探索処理について詳細に説明する。
【０２１２】
図２８はこの発明の実施の形態１４による経路探索装置の経路探索処理を説明する図であり、（ａ）は各経路と経路計算領域の位置関係を示す上面図、（ｂ）及び（ｃ）は経路計算領域内外に位置する経路の通過コストを立体的に表した概念図である。図において、８ｃは利用者の操作の結果として上記実施の形態と同様な処理にて設定された経路計算領域であり、８ｉは経路の出発地、８ｊは経路の目的地、８ｋは経路計算領域８ｃ内に存在する経路、８ｌは経路計算領域８ｃ外に存在する経路である。
【０２１３】
また、経路計算領域８ｃ内に存在する経路８ｋで使用されている道路リンクをＬｋ０〜Ｌｋｎとし、それぞれの通過コストをＣｋ０〜Ｃｋｎとする。さらに、経路計算領域８ｃ外に存在する経路８ｌで使用されている道路リンクをＬｌ０〜Ｌｌｍとし、それぞれの通過コストをＣｌ０〜Ｃｌｍとする。これにより、経路の総コストＣｋ及びＣｌは、それぞれ下記式（１）で表現することができる。但し、Ｃｋについて、ｉ＝０〜ｎで、ｎは正の整数である。また、Ｃｌについて、ｉ＝０〜ｍで、ｍは正の整数である。
【数１】
2004028703.tif 000003
【０２１４】
ここで、経路計算領域８ｃ内に存在する道路リンクＬｋ０〜Ｌｋｎの各通過コストを、領域８ｃ外のものと比較して低く設定しておくことで、上記（１）式の関係からＣｋ＜Ｃｌとなる。これにより、経路探索において、経路計算領域８ｃ内に存在する経路が優先して使用される。
【０２１５】
反対に、経路計算領域８ｃ外に存在する道路リンクＬｌ０〜Ｌｌｍの各通過コストを、領域８ｃ内のものと比較して高く設定しておくことで、上記（１）式の関係からＣｋ＜Ｃｌとなる。これによっても経路計算領域８ｃ内に存在する経路を優先して使用することができる。
【０２１６】
（ｂ）及び（ｃ）では、上述したような経路計算領域内外に位置する経路の通過コストを立体的に表現している。具体的に説明すると、（ｂ）に示す例では、平面の位置の高低が通過コストに対応している。つまり、経路計算領域８ｃ内の道路リンクの通過コストは、領域８ｃ外のものより低いので、経路計算領域８ｃに対応する部分の平面が下方に位置している。また、経路計算領域８ｃ外の道路リンクの通過コストは、領域８ｃ内のものより高いので、経路計算領域８ｃ外に対応する部分の平面が上方に位置している。
【０２１７】
これにより、（ａ）中の出発地８ｉを含むＡ−Ａ線で切った断面では、経路の通過コストが（ｂ）に見るような凹形状のパターンとなる。
【０２１８】
（ｃ）に示す例では、経路計算領域８ｃ外において経路計算領域８ｃから離れるにつれて、領域８ｃ外の道路リンクの通過コストを徐々に高くしている。このため、経路計算領域８ｃの周囲では、通過コストに対応するスロープが形成される。
【０２１９】
これにより、（ａ）中の出発地８ｉを含むＡ−Ａ線で切った断面では、経路の通過コストが（ｃ）に見るような台形のパターンとなる。
【０２２０】
以上のように、この実施の形態１４によれば、経路計算領域８ｃ内に存在する道路リンクの通過コストを周囲に比べて低下させておくか、若しくは、経路計算領域８ｃ外に存在する道路リンクの通過コストを上昇させておくので、最終的な通過コストの大小で経路設定が行われ、確実に現在地と目的地を結ぶ経路を計算することができる。
【０２２１】
従って、上記実施の形態１０から１３までのように、経路計算に用いる道路リンクを限定したり、探索を打ち切ったりすることによっても、目的地に到達する道路リンクが発見できず、探索不可能となるようなことがない。
【０２２２】
なお、上記実施の形態１０から１４までにおいて、上記実施の形態７と同様に、経路計算領域８ｃ内に存在し、且つ、利用者の操作入力時に表示されていた表示レベルの道路に経路探索の対象を限定する用に構成しても良い。これにより、利用者のイメージに合致した経路を提示することができる。
【０２２３】
これは、例えば実施の形態１０から１４までの構成に、上記実施の形態７に示した表示の際の道路選択処理を適用することによって実現することができる。また、上記実施の形態１４に、利用者の操作入力時に表示されていた道路の通過コストを一定比率で上昇／下降させる処理を加えることによっても、同様の動作が実現可能である。
【０２２４】
また、上記実施の形態１から１４までの処理では、経路計算の始点を自車位置とし、利用者による操作軌跡５ａの終端を経路計算の終点である目的地として、経路計算する例を主に説明したが、利用者による操作軌跡５ａ及び自車位置とは無関係に経路計算の始点と終点を定めるよう構成しても良い。
【０２２５】
例えば、上記実施の形態１で示したように、経路探索装置の操作初期画面において目的地設定（施設）ボタン２ｆ−１を設けておく。そして、このボタン２ｆ−１を選択すると、入出力処理部１ａは、地図情報記憶装置４に格納された代表的な施設に関する情報を読み出し、これら施設の名称をリスト形式に表示する画面をディスプレイ２ａに表示させる。このリスト中にあげられた施設を適宜選択することで、目的地を容易に設定できるようにする。
【０２２６】
このとき、利用者がディスプレイ２ａ画面上で操作した軌跡は、始点と終点を結ぶ経路の一部を変更しようとする動作として解釈することができる。また、上記施設の名称リストを任意に定めておくことで、任意地点間の経路計算にも利用することができる。
【０２２７】
また、上述したようなメニュー操作によって、既に設定された経路の一部を変更するモード（具体的には、迂回経路の計算処理）に切り替えられるように構成する。当該モードにおいて、経路計算の終点は予め設定しておいた目的地となり、利用者によって指定された軌跡による経路は、新たに設定した経路の一部（通過経路）として使用される。
【０２２８】
【発明の効果】
以上のように、この発明によれば、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、当該軌跡検出部が検出した軌跡を地図画像上の複数の座標点で表した経由地点群に変換する経路設定部と、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるので、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、所望の経路を利用者に提示することができるという効果がある。
【０２２９】
この発明によれば、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、当該軌跡検出部が検出した軌跡を複数の線分に分割し、各線分の節点を地図画像上の座標点で表した経由地点群に変換する経路設定部と、経由地点群及び地図画像上の道路網内の各道路を節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるので、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択等の煩雑な操作を経ることなく、所望の経路を利用者に提示することができるという効果がある。また、軌跡を複数の線分に分割し各線分の節点を経由地点とするので、経由地点群として設定する地点数を減少させることができ、経路探索の高速化を期待することができるという効果がある。
【０２３０】
この発明によれば、表示装置に表示した地図画像に対して指示された所望の経路に応じた軌跡を検出する軌跡検出部と、地図画像上の道路のうち経路計算に使用すべき道路を決定する経路計算領域を軌跡検出部が検出した軌跡に沿って設定する経路設定部と、地図画像上の道路網のうち経路計算領域内に含まれる各道路を、節点間を接続する道路リンクとして表現した道路情報を用いて、所望の経路に応じた誘導経路を算出する経路計算処理部とを備えるので、道路属性の指定／選択、道路名称の指定／選択、検索条件の指定／選択などの煩雑な操作を経ることなく、所望の経路を利用者に提示することができるという効果がある。
【図面の簡単な説明】
【図１】この発明の実施の形態１による経路探索装置の構成を示す図である。
【図２】図１中のディスプレイに表示した地図表示画面を示す図である。
【図３】図１中の経路探索装置のディスプレイに表示される画面を示す図である。
【図４】図１中の経路探索装置の動作を示すフロー図である。
【図５】図１中の入出力処理部による操作位置の取得方法を説明する説明図である。
【図６】図１中の入出力処理部による操作位置の他の取得方法を説明する説明図である。
【図７】図１中の入出力処理部による操作位置のさらに別の取得方法を説明する説明図である。
【図８】この発明の実施の形態２による経路探索装置のディスプレイに表示した地図表示画面を示す図である。
【図９】実施の形態２による経路探索装置の動作を示すフロー図である。
【図１０】実施の形態２による経路設定部の線分化処理を説明する説明図である。
【図１１】この発明の実施の形態３による経路探索装置の経路探索を説明する図である。
【図１２】この発明の実施の形態４による経路探索装置の経路探索を説明する図である。
【図１３】この発明の実施の形態５による経路探索装置の経路探索を説明する図である。
【図１４】この発明の実施の形態６による経路探索装置の経路探索を説明する図である。
【図１５】この発明の実施の形態７による経路探索装置の経路探索を説明する図である。
【図１６】実施の形態７による経路探索装置の経路探索を説明する図である。
【図１７】この発明の実施の形態８による経路探索装置の経路探索を説明する図である。
【図１８】この発明の実施の形態９による経路探索装置のディスプレイに表示される画面を示す図である。
【図１９】この発明の実施の形態１０による経路探索装置のディスプレイに表示した地図表示画面を示す図である。
【図２０】実施の形態１０の経路探索装置による経路計算領域の設定処理を説明する図である。
【図２１】実施の形態１０による経路探索装置の動作を示すフロー図である。
【図２２】経路計算領域と道路リンクとの関係を説明する図である。
【図２３】この発明の実施の形態１１による経路探索装置の経路計算領域の設定過程を説明する図である。
【図２４】実施の形態１１による経路探索装置の動作を示すフロー図である。
【図２５】この発明の実施の形態１２による経路探索装置の経路計算領域の設定処理を説明する図である。
【図２６】経路計算領域の矩形と楕円の違いによる効果を説明する説明図である。
【図２７】この発明の実施の形態１３による経路探索装置の経路探索処理を説明する図である。
【図２８】この発明の実施の形態１４による経路探索装置の経路探索処理を説明する図である。
【符号の説明】
１　中央処理装置、１ａ　入出力処理部（軌跡検出部）、１ｂ　測位処理部、１ｃ　地図表示部、１ｄ　経路設定部、１ｅ　経路計算処理部、１ｆ　経路誘導部、１ｇ　ＲＡＭ、１ｈ　フラッシュメモリ、２　入出力装置、２ａ　ディスプレイ、２ｂ　タッチパネル、２ｃ　リモートコントローラ、２ｄ　スピーカ、２ｅ−１　現在地の表示ボタン、２ｅ−２　メニューボタン、２ｅ−３　拡大・縮小ボタン、２ｆ−１　目的地設定（施設）ボタン、２ｆ−２　目的地設定（画面）ボタン、２ｆ−３　経路設定（画面）ボタン、２Ａ　地図表示画面、２Ａ−１〜２Ａ−３　地図、２Ｂ　所定領域、２Ｃ　代表地点、２Ｄ　領域、２Ｅ　円、３　現在位置検出装置、３ａ　ＧＰＳ受信機、３ｂ　速度センサ、３ｃ　相対方位センサ、４　地図情報記憶装置、５　操作点、５ａ，５ａ−１　操作軌跡、５ｂ　経由地点、５ｂａ　操作点、５ｃ　折れ線軌跡、５ｃａ　線分、５ｄ　直線、５ｅ　経路、５ｆ　共通ノード、５ｇ　経路、５ｈ　地点、５ｉ，５ｊ，５ｋ探索コスト、５ｌ　円、５ｍ，５ｐ，５ｑ，５ｒ　経路、５ｎ，５ｏ　ノード（節点）、５Ａ−１〜５Ａ−３　経路探索用データ、６ａ　ノード、６ｂ　リンク、７ａ　経由地点、７ｂ　経路、７ｃ　検査領域、８，８ｃ，８ｆ　経路計算領域、８ｂ　包絡円、８ｄ　経路探索の対象外の道路リンク、８ｅ　経路探索の対象となる道路リンク、８ｇ　道路リンク、８ｉ　経路の出発地、８ｊ　経路の目的地、８ｋ，８ｌ　経路、ａ１，ｂ１，ｂ２，ｂ３，ｂ４，ｃ１　ノード。
【図１】
2004028703.tif 000004
【図２】
2004028703.tif 000005
【図３】
2004028703.tif 000006
【図４】
2004028703.tif 000007
【図５】
2004028703.tif 000008
【図６】
2004028703.tif 000009
【図７】
2004028703.tif 000010
【図８】
2004028703.tif 000011
【図９】
2004028703.tif 000012
【図１０】
2004028703.tif 000013
【図１１】
2004028703.tif 000014
【図１２】
2004028703.tif 000015
【図１３】
2004028703.tif 000016
【図１４】
2004028703.tif 000017
【図１５】
2004028703.tif 000018
【図１６】
2004028703.tif 000019
【図１７】
2004028703.tif 000020
【図１８】
2004028703.tif 000021
【図１９】
2004028703.tif 000022
【図２０】
2004028703.tif 000023
【図２１】
2004028703.tif 000024
【図２２】
2004028703.tif 000025
【図２３】
2004028703.tif 000026
【図２４】
2004028703.tif 000027
【図２５】
2004028703.tif 000028
【図２６】
2004028703.tif 000029
【図２７】
2004028703.tif 000030
【図２８】
2004028703.tif 000031