ナビゲーション装置及びナビゲーション用プログラム
【課題】地図画面上に表示された道路を意識せずにユーザの意思を反映したなぞり経路探索を可能にする。
【解決手段】ユーザが指やタッチペンを使用して、画面表示した地図上をなぞる（トレースする）ことにより走行経路を設定する。その際、画面への表示が省略されている道路が存在しない場合には、従来と同様にトレースされた軌跡による走行経路を設定する。一方、省略道路が存在し、マッチングもできなかった場合、ユーザによりなぞられた軌跡は表示された道路を意識しておらず、走行経路の概略指定（曖昧な指定）と考えられるため、概略なぞり探索（曖昧なぞり探索）を行う。概略なぞり探索では、ユーザによるなぞり軌跡に沿った一定の範囲に存在する交差点に対して、なぞり軌跡からの距離に基づく交差点コストを決定し、交差点コストの合計が少ない走行経路を所定数探索する。
【解決手段】ユーザが指やタッチペンを使用して、画面表示した地図上をなぞる（トレースする）ことにより走行経路を設定する。その際、画面への表示が省略されている道路が存在しない場合には、従来と同様にトレースされた軌跡による走行経路を設定する。一方、省略道路が存在し、マッチングもできなかった場合、ユーザによりなぞられた軌跡は表示された道路を意識しておらず、走行経路の概略指定（曖昧な指定）と考えられるため、概略なぞり探索（曖昧なぞり探索）を行う。概略なぞり探索では、ユーザによるなぞり軌跡に沿った一定の範囲に存在する交差点に対して、なぞり軌跡からの距離に基づく交差点コストを決定し、交差点コストの合計が少ない走行経路を所定数探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置及びナビゲーションプログラムに係り、詳細にはナビゲーションにおける経路の設定に関する。
【背景技術】
【０００２】
車両に搭載されて目的地までの走行経路を探索して車両を案内するナビゲーション装置が広く普及している。
このナビゲーション装置では、ユーザが意図したとおりの経路を設定するために、目的地までの通過地点をユーザが指定する機能がある。
また、地図画面上に表示されている道路をユーザが指などでトレースし、その軌跡から目的地までの走行経路を設定する、なぞり経路探索の技術が提案されている（例えば、特許文献１）。
【０００３】
【特許文献１】特開２００４−２８７０３
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、通過地点を指定する方法では、ユーザが指定した地点は確実に通過することができるが、目的地までの全経路を希望どおりの経路とするためには多くの地点を指定する必要があり、非常に手間がかかるという問題がある。
【０００５】
一方、従来のなぞり経路探索は、地図画面上に表示されている道路上を又は表示されている道路に沿ってなぞることをユーザに要求し、そのなぞられた座標から道路とマッチングさせて経路を決定することで、容易且つ的確にユーザの嗜好を経路に反映させるようにしている。
しかし、ユーザの嗜好が必ずしも、地図画面上に表示された道路を選択したいとは限らない。例えば、ユーザは、この辺りの景色を見ながら目的地までたどり着きたいといった、道路よりも周辺の施設や地域を指定したい場合がある。
従来のなぞり経路検索では、このような道路を意識しないユーザのファジイななぞりの軌跡から経路を決定することができなかった。特に、広域な縮尺の地図が表示されている場合のように、全ての道路が画面上に表示されていない場合に顕著になる。
【０００６】
そこで本発明は、地図画面上に表示された道路を意識せずにユーザの意思を反映したなぞり経路探索を可能にすることを目的とする。
【課題を解決するための手段】
【０００７】
（１）請求項１に記載の発明では、画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置であって、地図を画面表示する地図表示手段と、前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断手段と、ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得手段と、前記省略判断手段で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定手段と、を具備することを特徴とするナビゲーション装置を提供する。
（２）請求項２に記載の発明では、前記経路設定手段は、画面表示が省略されている道路を含めて経路を設定する、ことを特徴とする請求項１に記載のナビゲーション装置を提供する。
（３）請求項３に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記設定した範囲内に存在する各交差点に対し、前記なぞり軌跡からの距離に基づく交差点コストを設定する交差点コスト設定手段と、を備え、前記経路設定手段は、前記設定した交差点コストの合計から走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（４）請求項４に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記設定した範囲内に存在する道路のコストを、範囲外の道路コストに対して相対的に低下させるコスト変更手段と、を備え、前記経路設定手段は、前記変更した道路のコストを使用して走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（５）請求項５に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記経路設定手段は、前記設定した範囲内に存在する道路を対象として走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（６）請求項６に記載の発明では、前記設定した走行経路の、道路のコストに基づく総コストを算出する総コスト算出手段と、前記決定した走行経路と前記なぞり軌跡とで囲まれる面積を算出する面積算出手段と、を備え、前記経路設定手段は、候補となる走行経路が複数存在する場合、各走行経路に対して前記算出した総コストと、面積を用いて１の走行経路を選択する、ことを特徴とする請求項１から請求項５のうちのいずれか１の請求項に記載のナビゲーション装置を提供する。
（７）請求項７に記載の発明では、画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置を構成するコンピュータに、地図を画面表示する地図表示機能と、前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断機能と、ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得機能と、前記省略判断機能で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定機能と、を実現させることを特徴とするナビゲーション用プログラムを提供する。
【発明の効果】
【０００８】
本発明では、画面表示した地図において、当該画面内において一部の道路が省略表示されていると判断した場合に、なぞり軌跡から所定距離となる範囲を優先して経路を設定するので、地図画面上に表示された道路を意識せずにユーザの意思を反映したなぞり経路探索が可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、本発明のナビゲーション装置及びナビゲーション用プログラムにおける好適な実施の形態について、図１から図８を参照して詳細に説明する。
（１）実施形態の概要
本実施形態では、ユーザが指やタッチペンを使用して、画面表示した地図上をなぞる（トレースする）ことにより走行経路を設定する。
その際、例えば最も詳細な地図を表示している場合のように画面への表示が省略されている道路が存在しない場合、又は、省略された道路が存在する場合でもなぞられた軌跡と表示されている道路とのマッチングができた場合には、従来と同様にトレースされた軌跡による走行経路を設定する。
【００１０】
一方、省略道路が存在し、マッチングもできなかった場合、ユーザによりなぞられた軌跡は表示された道路を意識しておらず、走行経路の概略指定（曖昧な指定）と考えられるため、概略なぞり探索（曖昧なぞり探索）を行う。
概略なぞり探索では、ユーザによるなぞり軌跡に沿った一定の範囲に存在する交差点に対して、なぞり軌跡からの距離に基づく交差点コストを決定し、交差点コストの合計が少ない走行経路を所定数探索する。
【００１１】
また、範囲内に存在する道路のコスト（経路探索に使用するリンクコスト）を下げることで、なぞり軌跡に沿った走行経路を探索するようにしてもよい。
この探索の際には、画面表示されていない道路も探索対象としてコストを下げる。
コストを下げる場合、対象外（なぞり軌跡から所定範囲外）の道路についてのコストを挙げることで相対的に下げるようにしてもよい。
変更後のコストを使用して、ダイクストラ法等一般的な方法により目的地までの経路探索を行い、経路の候補を複数求める。
【００１２】
この求めた経路と、ユーザによるなぞり軌跡とによって囲まれる面積を各経路について求める。
そして、各経路に対する総コストと、面積とから走行経路を決定する。
例えば、２経路の一方を決定する場合、総コストの差が小さい場合には、面積が小さい経路を決定し、総コストの差が大きくて面積差も小さい場合には総コストが小さい経路を決定し、総コストの差も面積の差も大きい場合には面積が小さい経路を決定する。
【００１３】
このように、なぞり軌跡に近い経路という観点だけでなく、一般的な経路探索に基づく総コストという観点も加味して走行経路を決定するので、より適切な走行経路を決定することができる。
なお、決定した走行経路は１経路だけでなく、複数を決定し上位数経路をユーザに提示してユーザが最終決定をするようにしてもよい。
【００１４】
（２）実施形態の詳細
図１は本実施形態が適用されるナビゲーション装置のシステム構成図である。
このナビゲーション装置は、車両に搭載され、この図１に示すように、現在位置検出装置１０、情報処理制御装置２０、入出力装置４０及び情報記憶装置５０とを備えている。
まず、現在位置検出装置１０は、以下のような構成を有している。絶対方位センサ１１は、例えば、磁石に基づいてＮ方向の検出から、車両がいずれの方向に位置するかを検出する地磁気センサであり、絶対方位を検出する手段であればよい。
【００１５】
相対方位センサ１２は、例えば交差点を曲がったか否かを検出するものであり、ハンドルの回転部に取り付けた光学的な回転センサや回転型の抵抗ボリューム或いは車輪部に取り付ける角度センサでもよい。
また、角速度を利用して角度の変化を検出するジャイロセンサを用いてもよい。つまり、基準角度（絶対方位）に対して、相対的に変化した角度を検出することができる手段であればよい。
距離センサ１３は、例えば、車輪の回転を検出して計数するものや、加速度を検出して２回積分するものでもよい。つまり、車両の移動距離を計測できる手段であればよい。
【００１６】
ＧＰＳ（グローバル・ポジショニング・システム）受信装置１４は、人工衛星からの信号を受信する装置であり、信号の発信時刻、受信装置の位置情報、受信装置の移動速度、受信装置の進行方向など様々な情報を得ることができる。
ビーコン受信装置１５は、特定の地点に設置された送信装置より発信された信号を受信する装置である。特に、ＶＩＣＳ情報を入手することができ、渋滞情報、現在位置情報、駐車場情報等車両の走行に関する情報を入手することができる。
【００１７】
データ送受信装置１６は、電話回線や電波を利用して車両外部と通信をし、情報の交換を行うための装置である。
例えば、自動車電話、ＡＴＩＳ、ＶＩＣＳ、ＧＰＳ補正、車両間通信など様々な利用方法があり、走行に関する情報を入出力することが可能である。
【００１８】
次に、情報処理制御装置２０は、現在位置検出装置１０、入出力装置４０から入力される情報及び情報記憶装置５０に格納された情報に基づいて演算及び制御を行うとともに、演算結果をディスプレイ４２、プリンタ４３またはスピーカ４４等の出力手段に出力するように制御する手段である。
【００１９】
この情報処理制御装置２０は、以下のような構成を有している。
中央処理装置（ＣＰＵ）２１は、ナビゲーション装置全体の総括的な演算及び制御を行う。
第１ＲＯＭ２２はナビゲーションに関するプログラム、特に、現在位置の検出、本実施形態によるなぞり経路探索を含めた目的地までの経路の探索、表示案内などに関するナビゲーションプログラムを格納している。
入力インターフェイス２３は、現在位置検出装置１０からの情報を受け取る手段である。
【００２０】
ＲＡＭ２４は、後述する入力装置４１により入力された目的地の情報、通過地点の情報等の利用者が入力した情報を記憶すると共に、利用者の入力情報に基づいてＣＰＵ２１により演算された結果や、経路探索された結果、または情報記憶装置５０から読み込まれた地図情報を格納するための記憶手段である。ＲＡＭ２４には、本実施形態のなぞり経路探索においてユーザがなぞった軌跡（なぞり軌跡）のデータ（座標列）が一時保存される。
【００２１】
通信インタフェース２５は、現在位置検出装置１０からの情報、特に外部から得られる情報を入出力するための手段である。
【００２２】
第２ＲＯＭ２６は、ナビゲーションに関するプログラム、特に、本実施形態におけるなぞり経路探索処理を含め、音声案内に関するナビゲーションプログラムを格納している。なお、第１ＲＯＭ２２と第２ＲＯＭ２６を共通する１のＲＯＭで構成するようにしてもよい。
画像プロセッサ２７は、ＣＰＵ２１で処理されたベクトル情報を画像情報に処理するための処理手段である。
時計２８は、時刻を刻む。
画像メモリ２９は、画像プロセッサにより処理された画像情報を格納する手段である。
音声プロセッサ３０は、情報記憶装置５０から読み込まれた音声情報を処理し、スピーカ４４に出力する。
【００２３】
入出力装置４０は、利用者により目的地、通過地点、探索条件等のデータを入力する入力装置４１、画像を表示するディスプレイ４２、情報を印刷するプリンタ４３、音声を出力するスピーカ４４より構成される。入力装置４１は、例えば、タッチパネル、タッチスイッチ、ジョイスティック、キースイッチ等で構成される。
ディスプレイ４２には、現在地周辺の地図や、目的地までの走行経路が表示される。
本実施形態におけるなぞり経路探索では、ディスプレイ４２に指定された縮尺の地図が表示され、ユーザが表示された地図を見ながらディスプレイ４２の表面に配置されたタッチパネルをなぞることで、走行したい道路を指定したり、概略の通過コースを指定したりする。
なお、ディスプレイ４２に表示されている地図上に、ユーザがなぞった軌跡を順次表示するようにしてもよい。
【００２４】
情報記憶装置５０は、伝送路４５を介して情報処理制御装置２０に接続される。
情報記憶装置５０は、地図データファイル５１、交差点データファイル５２、ノードデータファイル５３、道路データファイル５４、写真データファイル５５、目的地データファイル５６、案内地点データファイル５７、詳細目的地データファイル５８、目的地読みデータファイル５９、その他のデータファイル６０を格納している。
この情報記憶装置５０は、一般的には、光学的記憶媒体であるＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭや磁気的記憶媒体であるハードディスクなどで構成されるが、光磁気ディスク、各種半導体メモリなどの各種情報記憶媒体で構成してもよい。
なお、書き換えが必要な情報については、書き換え可能なハードディスク、フラッシュメモリなどで構成し、その他の固定的な情報についてはＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのＲＯＭを使用するようにしてもよい。
【００２５】
地図データファイル５１には、全国道路地図、各地域の道路地図または住宅地図等の地図データが記憶されている。道路地図は、主要幹線道路、高速道路、細街路等の各道路と地上目標物（施設等）から構成される。住宅地図は、地上建造物等の外形を表す図形及び、道路名称等が表示される市街図である。細街路とは、例えば、国道、県道以下の道幅が所定値以下の比較的狭い道路である。
ディスプレイ４２に表示される地図の中では、住宅地図がもっとも縮尺が大きい地図で、この住宅地図がディスプレイに表示されている場合には、データとして保持している道路のうち、その表示領域に存在する全ての道路が表示されている。一方、表示地図の縮尺が小さくなるに従い、所定の基準に従って細い道路から順に表示対象外となる。
【００２６】
交差点データファイル５２には交差点の地理的位置座標や名称等の交差点に関するデータが、道路データファイル５４には道路の位置と種類及び車線数及び各道路間の接続関係等の道路に関するデータが、写真データファイル５５には各種施設や観光地、または主要な交差点等の視覚的表示が要求される場所を写した写真の画像データが、それぞれ記憶されている。
【００２７】
ノードデータファイル５３には地図上において経路探索に利用される各ノードの地理座標データ等を表したノードデータが記憶される。
例えば、交差点などの道路の接続点はノードにより表され、接続点の間の道路（即ち道路の内分岐しない領域）はリンクによって表される。このように、ノードデータ経路の接続関係を表した経路データとして機能している。
また、各リンクには、進入禁止や一方通行など、交通規制により走行が制限されるものに関しては、これを表す属性が付与されている。
【００２８】
目的地データファイル５６には、主要観光地や建物、電話帳に記載されている企業・事業所等の目的地になる可能性の高い場所や施設等の位置と名称等のデータが記憶されている。
案内地点データファイル５７には、道路に設置されている案内表示板の内容や分岐点の案内等、案内が必要とされる地点の案内データが記憶されている。
詳細目的地データファイル５８には、上記目的地データファイル５６に記憶されている目的地に関する詳細なデータが記憶されている。
【００２９】
このように構成されたナビゲーション装置では、次のようにして経路案内が行われる。
ナビゲーション装置は、現在位置検出装置１０で現在位置を検出し、情報記憶装置５０の地図データファイル５１から現在位置周辺の地図情報を読み込みディスプレイ４２に表示する。
そして、入力装置４１から目的地が入力されると、情報処理制御装置２０は、現在位置から目的地に至る走行経路の候補を複数探索（演算）し、ディスプレイ４２に表示した地図上に表示し、運転者がいずれかの走行経路を選択すると、選択した走行経路をＲＡＭ２４に格納することで、走行経路を取得する（走行経路取得手段）。
なお、本実施形態におけるなぞり経路探索による経路探索については後述する。
【００３０】
なお、情報処理制御装置２０は、情報処理センタに車両現在位置（又は入力された出発地）と目的地を送信し、情報処理センタで探索された目的地までの走行経路を受信することにより走行経路を取得するようにしてもよい。この場合、目的地や走行経路の通信は通信インターフェイス２５を介して、無線通信により行う。本実施形態におけるなぞり経路探索の場合には、地図上でユーザがなぞった軌跡（なぞり軌跡）のデータを情報センタに送信し、情報センタでなぞり経路探索を行う。
また、自宅等のパーソナルコンピュータ等の情報処理装置を使用して、出発地から目的地までの走行経路を探索し、ＵＳＢメモリ等の記憶媒体に格納し、該記憶媒体読取り装置を介して取得するようにしてもよい。この場合の記憶媒体読み取り装置は伝送路４５を介して情報処理制御装置２０に接続される。
【００３１】
車両が走行すると、現在位置検出装置１０によって検出された現在位置を追跡することにより、経路案内を行う。
経路案内は、探索した走行経路に対応する道路データと現在位置検出装置１０で検出される現在位置とのマップマッチングにより、地図上の車両位置を特定し、車両現在位置周辺の地図をディスプレイ４２に表示すると共に、探索した走行経路と現在位置とを地図上に表示する。
また、探索した走行経路と現在位置との関係から、案内の必要性、すなわち直進が所定距離以上続く場合、所定の進路変更地点等の走行経路の案内、及び方面案内が必要か否か等について判断し、必要である場合にはディスプレイ４２の表示及び音声による案内を実行する。
【００３２】
このように構成されたナビゲーション装置による、本実施形態のなぞり経路探索処理について次に説明する。
本実施形態によるなぞり経路探索処理は、目的地設定画面や経路設定画面における所定の選択メニューから、ユーザがなぞり経路探索を選択することで実行される。
なお、なぞり経路探索の選択は、所定縮尺の地図がディスプレイ４２に表示されていることが前提となる。このため、本実施形態では、なぞり経路探索が選択された際に既に地図が表示されている場合にはその縮尺の地図において実行され、表示されていない場合には、予め決められた所定縮尺（例えば、現在いる都道府県の全域が１画面に表示できる縮尺）の地図を表示する。いずれの場合でも地図画面の一部に縮尺を変更するための縮尺変更ボタンが表示され、ユーザはこの縮尺変更ボタンの操作することにより希望する縮尺の地図（自分がなぞり経路探索をしたい領域が表示される縮尺の地図）を表示する。
【００３３】
図２はなぞり経路探索処理の内容について表したフローチャートである。
なぞり経路探索を実行すると、情報処理制御装置２０は、ディスプレイ４２に表示している地図（ユーザがなぞった地図）に、表示領域の中で画面表示されていない道路（表示が省略されている道路）があるか否かを判断する（ステップ１１）。
【００３４】
ここで、画面表示されていない道路が存在するか否かの判断対象となる道路は、細街路を含めた全ての道路を含めるようにしてもよく、また、細街路は含めないようにしてもよい。また、通常の経路探索による探索対象とされる道路に限定し、細街路については通常経路探索の対象になっている範囲で判断対象とするようにしてもよい。
なお、表示されている地図の縮尺から、道路の省略表示があるか否かを判断するようにしてもよい。
【００３５】
全ての道路が省略されることなく表示されている場合（ステップ１１；Ｎ）、ユーザは表示されている道路上をなぞっている（トレースしている）と判断できるので、情報処理制御装置２０は、既存のなぞり検索を行う（ステップ１２）。
すなわち情報処理制御装置２０は、画面表示されている道路（リンク）となぞり軌跡とをマッチングさせ、経路をつなぐことで経路を決定し、処理を終了する。
なお、なぞり軌跡とのマッチング対象となる道路は、画面表示されている道路であるが、省略されている道路を含めてマッチングするようにしてもよい。
【００３６】
一方、ディスプレイ４２に表示されている地図が、一部の道路を省略して表示している場合（ステップ１１；Ｙ）、情報処理制御装置２０は、画面表示されている道路の本数が所定の閾値ｔ以上であるか否かを判断する（ステップ１３）。
情報処理制御装置２０は、表示道路数が所定閾値ｔより少なければ（ステップ１３；Ｎ）マッチングに使用するサンプル軌跡点数を少なくする（ステップ１４）。一方、閾値ｔ以上であれば（ステップ１３；Ｙ）、マッチングに使用するサンプル軌跡点数を多くする（ステップ１５）。すなわち、表示道路数が所定閾値ｔより少ない場合には、所定閾値ｔ以上である場合に比較してより少ないサンプル軌跡点数を使用してマッチングしている。
なお、この所定の閾値を１つ設けることでマッチングに使用するサンプル軌跡の点数を２段階に分けたが、２つ以上の閾値ｔ１、ｔ２、…を設けることで、サンプル軌跡の点数を３段階（少ない、中間、多い）とし、またそれ以上としてもよい。
【００３７】
ステップ１４又はステップ１５で決定したサンプル軌跡点数にしたがい、情報処理制御装置２０は、ユーザのなぞり操作開始から一定時間の軌跡（規定サンプル数での軌跡）とディスプレイ４２の地図上に表示されている道路をマッチングし、マッチングができたか否かを判断する（ステップ１６）。
【００３８】
ここでサンプル軌跡点と道路とのマッチングについては、サンプル軌跡点から所定距離内に表示されている道路が存在し、かつ前後のサンプル軌跡点で特定した道路と繋がっている場合に、マッチングできたと判断する。
【００３９】
表示されている道路とのマッチングができた場合（ステップ１６；Ｙ）、ユーザは画面表示された道路上をなぞっていると判断できるので、情報処理制御装置２０はステップ１２に移行して従来のなぞり検索を行い処理を終了する。
すなわち、機器制御部１０は、なぞり軌跡と表示されている道路（又はノード）をマッチングさせて走行経路を決定し、処理を終了する。
【００４０】
一方、マッチングできなかった場合（ステップ１６；Ｎ）、情報処理制御装置２０は、ディスプレイ４２に表示されている道路は意識せずになぞっていると判断し、概略なぞり検索（ステップ１７〜ステップ１９）を行う。この概略なぞり検索では、縮尺に基づいて表示が省略されている道路も経路探索の対象とする。
【００４１】
情報処理制御装置２０は、表示している地図の縮尺から、探索範囲（コスト変更範囲など）を決定する（ステップ１７）。
図３は、探索範囲の決定処理について表したフローチャートである。
情報処理制御装置２０は、まずディスプレイ４２に表示している地図の縮尺が所定の閾値Ｔ以上か否かを判断する（ステップ１７１）。
【００４２】
表示地図の縮尺が閾値Ｔ以上である場合、すなわち、詳細な地図が表示されている場合（ステップ１７１；Ｙ）、情報処理制御装置２０は、探索範囲を狭く設定する（ステップ１７２）。なぞり軌跡の点への重要度が高いと判断されるためである。
一方、縮尺が閾値Ｔ未満である場合、すなわち、広域な地図が表示されている場合（ステップ１７１；Ｎ）、探索範囲を広く設定する（ステップ１７３）。これは、広域地図を表示している場合、なぞり軌跡の点への重要度が薄れるためである。
【００４３】
図４は、なぞり軌跡と検索範囲の設定について表したものである。
図４（ａ)に示すように、ディスプレイ４２の表示地図上において、ユーザがなぞり経路探索開始地点Ｓから、なぞり軌跡Ａのようになぞり、なぞり経路探索終了地点Ｇまでなぞったものとする。
この場合、図４（ｂ)に示すように、地図表示の縮尺が閾値Ｔ以上であれば、なぞり軌跡の両側所定距離Ｓ１となる探索範囲１を設定し、閾値Ｔ未満であれば、なぞり軌跡の両側所定距離Ｓ２（＞Ｓ１）となる探索範囲２を設定する。
【００４４】
なお、探索範囲を設定する場合の所定の閾値Ｔを１つ設けることで探索範囲を２段階に分けたが、２つ以上の閾値Ｔ１、Ｔ２、…を設けることで、探索範囲を３段階（Ｓ１以内、Ｓ２以内、Ｓ３以内）とし、またそれ以上としてもよい。
【００４５】
探索範囲を決定すると情報処理制御装置２０は、決定した探索範囲に基づいて経路探索を行う（図２、ステップ１８）。
ここで行う経路探索は、経路探索Ｉ〜経路探索ＩＩＩの何れか１の方法による。以下各々の経路探索について説明する。
なお、ステップ１７（ステップ１７２又はステップ１７３）で設定する探索範囲については、以下の経路探索Ｉ〜ＩＩＩにより異なる値とすることができる。例えば、経路探索ＩＩＩを採用する場合の探索範囲は、経路探索ＩＩを採用する場合の探索範囲よりも広くすることができる。
【００４６】
（ａ)経路探索Ｉ
図５は、経路探索Ｉの方法を概念的に表したものである。
この図５では、点線がなぞり軌跡を、細線が画面に表示されている道路（リンク）を、太線が決定した経路を表している。また、各リンクの交差する点に表示された○が交差点（ノード）を表し、この○の中に表示した数字は、「交差点からなぞり軌跡までの最短距離」をコストとして設定したものである。
【００４７】
なお、この概略なぞり検索（ステップ１７〜１９）では、画面表示されていない道路も検索対象としている。
このため、図５（ａ)では、左上にコスト２と表示されている交差点にもコストが設定され、この交差点を通る道路（地図画面、及び図５（ａ)では表示されていない）も対象とされている。これは図５（ｂ)の場合も同様である。
【００４８】
そして情報処理制御装置２０は、設定した各交差点のコストに従って、なぞりの開始地点Ｓから終了地点Ｇまでのその総コスト（各ノードのコスト合計）が最小となる経路を、ステップ１７で設定した探査範囲内で探索する。
なお、一方通行などの通行付加道路やコストの極めて高いリンクは選択しない。
【００４９】
図５（ｂ)は、経路探索Ｉによる他の経路の決定について表したものである。
この図５（ｂ)に示すように、なぞり経路探索から一定距離の範囲内（図面中丸点線で表した範囲内）の交差点については、同一のコストを設定するようにしてもよい。
【００５０】
（ｂ)経路探索ＩＩ
この経路探索ＩＩでは、ステップ１７で設定した探索範囲内で、探索コストを下げたうえで（又は探索範囲外の探索コストを上げたうえで）、例えば、ダイクストラ法などの一般的な経路探索手法により、なぞり経路探索開始地点Ｓ（出発地点）からなぞり経路探索終了地点Ｇ（目的地）までの経路探索を行う。
このように、設定した探索範囲内の探索コストを下げることで、なぞり軌跡近傍の道路がより選択されやすくなる。
【００５１】
なお、探索コストは、一般的な経路探索で使用される探索コストであり、通常道路の距離や幅に応じて決められるコストである。コストを下げる場合、設定した探索範囲内の道路に対して所定値を一律下げ、又は一定の係数α１（＜１）を乗算する。また設定した範囲外の道路に対して所定値を一律上げ、又は一定の係数α２（＞１）を乗算する。
【００５２】
なお、なぞり軌跡に近い道路ほど下げ幅を大きくし、又は係数α１を小さくしてもよい。また、なぞり軌跡に遠いほど上げ幅を大きくし、又は係数α２を大きくするようにしてもよい。
【００５３】
（ｃ)経路探索ＩＩＩ
この経路探索ＩＩＩでは、ステップ１７で設定した探索範囲内の道路だけを探索対象として経路探索を行う。この経路探索は、例えば、ダイクストラ法などの一般的な経路探索手法により、なぞり経路探索開始地点Ｓ（出発地点）からなぞり経路探索終了地点Ｇ（目的地）までの経路探索を行う。
設定した探索範囲に含まれる道路か否かについては、少なくとも一部が含まれている道路を対象にする。また設定し探索範囲に含まれる交差点を端点に持つ道路を対象にしてもよい。
【００５４】
以上の経路探索Ｉ〜ＩＩＩの何れか１の方法により経路探索し、候補となる走行経路が複数探索されると、情報処理制御装置２０は、経路の選択を行う（ステップ１９）。
図６は、経路選択処理の内容を表したフローチャートである。
情報処理制御装置２０は、ステップ１８の探索経路で探索され候補となった全ての走行経路に対する総コストを算出する。
ここで算出する総コストは、経路探索開始地点Ｓを出発地とし、なぞり経路探索終了地点Ｇを目的地とし、通常のダイクストラ法等による経路探索の結果、当該各走行経路が探索された場合の総コストである。
このように、通常のダイクストラ法等による一般的な経路探索による総コストを算出するのは、走行経路としての一般的な妥当性を後で判断するためである。
【００５５】
従って、経路探索の方法として、上記経路探索Ｉを使用した場合には必ず総コストの算出が必要であるが、上記経路探索ＩＩとＩＩＩを使用した場合には、経路探索の際に総コストが算出済みなので、その値をＲＡＭ２４に記憶しておき、その記憶値を使用するようにしてもよい。
但し、経路探索ＩＩでは、ステップ１７で設定した探索範囲内で探索コストを変更した上で経路探索をしているので、変更後の探索コストに基づく総コストを使用してもよいが、変更前の探索コストに基づく総コストを再計算するようにしてもよい。
【００５６】
情報処理制御装置２０は、経路探索により候補となった走行経路となぞり軌跡とが成す面積を求める（ステップ１９２）。
このようになぞり軌跡との面積を求めるのは、各走行経路がなぞり軌跡にどれだけ沿った経路であるかを判断するためである。面積が小さいほど、なぞり軌跡に近い経路が選択されていることになる。
【００５７】
図７は、なぞり軌跡との面積を表したものである。
いま図７（ａ)に示すように、ユーザによるなぞり経路探索開始地点Ｓからなぞり経路探索終了地点Ｇまでなぞられ（なぞり軌跡Ａ）、このなぞり軌跡に基づいて概略なぞり探索により候補経路１と候補経路２が探索されたものとする。
この場合の各候補経路１と候補経路２がなぞり軌跡となす面積（囲まれる面積）は、それぞれ斜線で占める領域であり、情報処理制御装置２０は、この斜線で表した面積を算出する。
【００５８】
そして情報処理制御装置２０は、算出した各経路に対する総コストと面積を用いて複数の走行経路の候補から１の走行経路を選択する（ステップ１９３〜１９７）。
すなわち、情報処理制御装置２０は、総コストの差は一般的な経路の良し悪しの観点から経路の差を用い、また、なぞり軌跡に近いかどうかの観点から面積の差を用いて走行経路を選択する。
【００５９】
情報処理制御装置２０は、総コストの差が大きいか否かを判断する（ステップ１９３）。なお、総コストの差は、最大値と最小値との差であり、総コストの差の大小については、所定の閾値より大きいか否かにより判断する。
総コストの差が閾値より小さい場合（ステップ１９３；Ｎ）、いずれの候補も一般的な経路としての的確性があると判断できるので、情報処理制御装置２０は、最も面積が小さい走行経路に決定し（ステップ１９４）、メインルーチンにリターンする。
【００６０】
一方、総コストの差が閾値より大きい場合、情報処理制御装置２０は、面積の差が大きいか否かを判断する（ステップ１９５）。面積の差は最大値と最小値との差であり、面積の差の大小は閾値よりも大きいか否かによる。
経路コストの差が大きいが、面積の差は小さい場合（ステップ１９５；Ｎ）、全ての走行経路がなぞり軌跡の近傍に設定されているので、情報処理制御装置２０は、より一般的な的確性が高い走行経路である、最も総コストが小さい走行経路に決定し（ステップ１９６）、メインルーチンにリターンする。
【００６１】
また、総コストの差が大きく、更に面積の差も大きい場合（ステップ１９５；Ｙ）、情報処理制御装置２０は、ユーザの意志を尊重して、最も面積が小さい走行経路に決定し（ステップ１９７）、メインルーチンにリターンする。
【００６２】
説明した実施形態では、図６に示した経路選択処理において、総コストの差も面積の差も大きい場合（ステップ１９３；Ｙ、ステップ１９５；Ｙ）、最も面積が小さい経路に決定した（ステップ１９７）が、次のようにしてもよい。
図８は、経路選択処理における総コスト差、面積差の両者が大きい場合の走行経路決定方法についてのフローチャートである。
このフローチャートでは、経路１と経路２が走行経路の候補である場合について説明しているが、それ以上の場合も同様に処理するものとする。
【００６３】
情報処理制御装置２０は、コストの重要度合から係数αを決定し（ステップ２０１）、決定した係数αを経路１、経路２の総コストに積算し、換算総コストとする（ステップ２０２）。
また情報処理制御装置２０は、面積の重要度合により係数βを決定し（ステップ２０３）、決定した係数βを経路１、経路２の面積に積算して換算面積とする（ステップ２０４）。
【００６４】
ここで、コストの重要度、面積の重要度は、例えば、縮尺や地図画面上に表示される道路の数（密度）に応じて配分される係数によって決定する。また、ユーザが設定できるようにしてもよい。
【００６５】
そして情報処理制御装置２０は、各経路毎に換算総コストと換算面積の和を求め、経路１の和が小さいか否か判断し（ステップ２０５）、経路１の和が大きければ（ステップ２０５；Ｎ）経路２に決定し（ステップ２０６）、経路１の和が小さければ（ステップ２０５；Ｙ）、経路１に決定する（ステップ２０７）。
【００６６】
このように、総コストと面積を換算しその和の値が最も小さい経路を決定することで、両要素を考慮した最適な経路を選択することができる。
【００６７】
なお、係数α、βを積算するのではなく、各走行経路について算出した総コストと面積の乗算値を求め、乗算値が最小になる経路を選択するようにしてもよい。
【００６８】
以上説明したように本実施形態によるナビゲーション装置及びナビゲーション用プログラムによれば、ディスプレイ４２に表示されている地図の縮尺により表示されていない道路が存在している場合に、表示されている道路だけを対象としたマッチングを行うのではなく、表示が省略されている道路を含めて、なぞり軌跡に沿って設定した探索範囲を設定し、この探索範囲を使用して経路探索Ｉ、ＩＩ、又はＩＩＩを行うようにしている。
このため、本実施形態のなぞり経路探索によれば、ユーザは、画面表示されている道路を意識せずに自由に出発地から目的地までをなぞることができる。
【００６９】
以上、本発明のナビゲーション装置及びナビゲーション用プログラムにおける１実施形態について説明したが、本発明は説明した実施形態に限定されるものではなく、各請求項に記載した範囲において各種の変形を行うことが可能である。
例えば、説明した実施形態では、ステップ１４又はステップ１５で決定したサンプリング軌跡点数の全てが、表示されている道路とマッチングできなかった場合に、概略なぞり検索（ステップ１７〜１９）を行う場合について説明した。
これに対して、なぞり軌跡が表示道路と一定区間マッチングしている場合には、その区間はマッチングした表示道路を部分経路とし、マッチングしない他の区間に対して本実施形態の概略なぞり検索により部分経路を決定し、両部分経路を接続することで走行経路とするようにしてもよい。
【００７０】
また、説明した実施形態では、画面表示されている道路とサンプル軌跡点数のマッチングができるか否か（ステップ１６）により、概略なぞり検索を行うか否かを決定する場合について説明した。
これに対し、なぞる前又は後において、表示道路上のなぞりか、概略なぞり検索かをユーザ操作が選択するようにしてもよい。
【００７１】
また、説明した実施形態において、地図表示や探索に使用される情報を最詳細な情報を含めて探索しても、適切な走行経路を探索できない場合、「道路がありません」等の探索できない旨の表示を行うようにしてもよい。
【００７２】
また、高速道路などの有料道や、トンネル、高架橋などは、地図上に表示されても、入口が決まっていて、なぞったとしても、なぞり軌跡通りには走行できない場合がある。
この場合、広域な地図のため、間引かれた道路（表示が省略されている道路）も、なぞり操作のために表示させるようにしてもよい。
または、現在地なぞり位置から、入口が遠い場合は、該当の上記道路（高速道路やトンネル等）を薄く表示させるようにしてもよい。
【００７３】
ナビゲーション装置には、通常の経路探索を行う場合に、経路優先、時間優先等の異なる検索条件により走行経路を検索して各条件毎に走行経路の候補を地図上に表示し、その中からユーザが希望する走行経路を選択する複数経路探索機能がある。
本実施形態では、この複数経路探索で探索した各候補経路を地図上に表示した画面で、ユーザがなぞりを行うようにしてもよい。この場合、なぞり軌跡のマッチングを表示した候補経路に対して行うようにしてもよい。
【００７４】
この場合も、上記変形例とどうように、なぞり軌跡が候補経路と一定区間マッチングしている場合には、その区間はマッチングした候補経路を部分経路とし、マッチングしない他の区間に対して本実施形態の概略なぞり検索により部分経路を決定し、両部分経路を接続することで走行経路とするようにしてもよい。
【００７５】
また、説明した実施形態では、所定の選択メニューからユーザがなぞり検索を選択することでなぞり経路探索処理実行する場合について説明したが、ユーザが所定縮尺の地図を表示している画面をタッチしそのまま画面をなぞることでなぞり検索処理が実行されるようにしてもよい。
【００７６】
また、説明した実施形態及び上記各変形例では、最初にタッチした点を出発点とし、なぞり軌跡の最終点（タッチからの開放点）を目的地としてなぞり経路探索処理を実行する場合について説明したが、画面に表示されている走行経路を変更する場合になぞり経路探索処理を実行するようにしてもよい。
この場合の、画面に表示されている走行経路は、既に案内途中の走行経路を変更する場合、及び、目的地までの走行経路を探索して候補として表示した走行経路を変更する場合がある。
【００７７】
また説明した実施形態では、概略なぞり検索において、図６、７の方法により、複数の候補から１の走行経路を選択する場合（ステップ１９）について説明したが、上位所定数の候補についてユーザに提示し、ユーザが何れかを選択するようにしてもよい。
上位所定数の候補決定については、図６、図７の何れかの方法、その他の方法により決定してもよい。
ユーザの提示としては、例えば、図７（ａ)に示されるように、なぞり軌跡Ａと複数の候補経路を区別できるように地図上に表示する。なお、なぞり軌跡Ａの表示は省略してもよい。
【図面の簡単な説明】
【００７８】
【図１】本実施形態が適用されるナビゲーション装置のシステム構成図である。
【図２】なぞり経路探索処理の内容について表したフローチャートである。
【図３】探索範囲の決定処理について表したフローチャートである。
【図４】なぞり軌跡と検索範囲の設定について表した説明図である。
【図５】経路探索Ｉの方法を概念的に表した説明図である。
【図６】経路選択処理の内容を表したフローチャートである。
【図７】なぞり軌跡との面積を表した説明図である。
【図８】経路選択処理における総コスト差、面積差の両者が大きい場合の走行経路決定方法についてのフローチャートである。
【符号の説明】
【００７９】
１０ 現在位置検出装置
２０ 情報処理制御装置
２１ ＣＰＵ
４０ 入出力装置
５０ 情報記憶装置
【技術分野】
【０００１】
本発明は、ナビゲーション装置及びナビゲーションプログラムに係り、詳細にはナビゲーションにおける経路の設定に関する。
【背景技術】
【０００２】
車両に搭載されて目的地までの走行経路を探索して車両を案内するナビゲーション装置が広く普及している。
このナビゲーション装置では、ユーザが意図したとおりの経路を設定するために、目的地までの通過地点をユーザが指定する機能がある。
また、地図画面上に表示されている道路をユーザが指などでトレースし、その軌跡から目的地までの走行経路を設定する、なぞり経路探索の技術が提案されている（例えば、特許文献１）。
【０００３】
【特許文献１】特開２００４−２８７０３
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、通過地点を指定する方法では、ユーザが指定した地点は確実に通過することができるが、目的地までの全経路を希望どおりの経路とするためには多くの地点を指定する必要があり、非常に手間がかかるという問題がある。
【０００５】
一方、従来のなぞり経路探索は、地図画面上に表示されている道路上を又は表示されている道路に沿ってなぞることをユーザに要求し、そのなぞられた座標から道路とマッチングさせて経路を決定することで、容易且つ的確にユーザの嗜好を経路に反映させるようにしている。
しかし、ユーザの嗜好が必ずしも、地図画面上に表示された道路を選択したいとは限らない。例えば、ユーザは、この辺りの景色を見ながら目的地までたどり着きたいといった、道路よりも周辺の施設や地域を指定したい場合がある。
従来のなぞり経路検索では、このような道路を意識しないユーザのファジイななぞりの軌跡から経路を決定することができなかった。特に、広域な縮尺の地図が表示されている場合のように、全ての道路が画面上に表示されていない場合に顕著になる。
【０００６】
そこで本発明は、地図画面上に表示された道路を意識せずにユーザの意思を反映したなぞり経路探索を可能にすることを目的とする。
【課題を解決するための手段】
【０００７】
（１）請求項１に記載の発明では、画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置であって、地図を画面表示する地図表示手段と、前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断手段と、ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得手段と、前記省略判断手段で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定手段と、を具備することを特徴とするナビゲーション装置を提供する。
（２）請求項２に記載の発明では、前記経路設定手段は、画面表示が省略されている道路を含めて経路を設定する、ことを特徴とする請求項１に記載のナビゲーション装置を提供する。
（３）請求項３に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記設定した範囲内に存在する各交差点に対し、前記なぞり軌跡からの距離に基づく交差点コストを設定する交差点コスト設定手段と、を備え、前記経路設定手段は、前記設定した交差点コストの合計から走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（４）請求項４に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記設定した範囲内に存在する道路のコストを、範囲外の道路コストに対して相対的に低下させるコスト変更手段と、を備え、前記経路設定手段は、前記変更した道路のコストを使用して走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（５）請求項５に記載の発明では、前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、前記経路設定手段は、前記設定した範囲内に存在する道路を対象として走行経路を設定する、ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置を提供する。
（６）請求項６に記載の発明では、前記設定した走行経路の、道路のコストに基づく総コストを算出する総コスト算出手段と、前記決定した走行経路と前記なぞり軌跡とで囲まれる面積を算出する面積算出手段と、を備え、前記経路設定手段は、候補となる走行経路が複数存在する場合、各走行経路に対して前記算出した総コストと、面積を用いて１の走行経路を選択する、ことを特徴とする請求項１から請求項５のうちのいずれか１の請求項に記載のナビゲーション装置を提供する。
（７）請求項７に記載の発明では、画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置を構成するコンピュータに、地図を画面表示する地図表示機能と、前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断機能と、ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得機能と、前記省略判断機能で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定機能と、を実現させることを特徴とするナビゲーション用プログラムを提供する。
【発明の効果】
【０００８】
本発明では、画面表示した地図において、当該画面内において一部の道路が省略表示されていると判断した場合に、なぞり軌跡から所定距離となる範囲を優先して経路を設定するので、地図画面上に表示された道路を意識せずにユーザの意思を反映したなぞり経路探索が可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、本発明のナビゲーション装置及びナビゲーション用プログラムにおける好適な実施の形態について、図１から図８を参照して詳細に説明する。
（１）実施形態の概要
本実施形態では、ユーザが指やタッチペンを使用して、画面表示した地図上をなぞる（トレースする）ことにより走行経路を設定する。
その際、例えば最も詳細な地図を表示している場合のように画面への表示が省略されている道路が存在しない場合、又は、省略された道路が存在する場合でもなぞられた軌跡と表示されている道路とのマッチングができた場合には、従来と同様にトレースされた軌跡による走行経路を設定する。
【００１０】
一方、省略道路が存在し、マッチングもできなかった場合、ユーザによりなぞられた軌跡は表示された道路を意識しておらず、走行経路の概略指定（曖昧な指定）と考えられるため、概略なぞり探索（曖昧なぞり探索）を行う。
概略なぞり探索では、ユーザによるなぞり軌跡に沿った一定の範囲に存在する交差点に対して、なぞり軌跡からの距離に基づく交差点コストを決定し、交差点コストの合計が少ない走行経路を所定数探索する。
【００１１】
また、範囲内に存在する道路のコスト（経路探索に使用するリンクコスト）を下げることで、なぞり軌跡に沿った走行経路を探索するようにしてもよい。
この探索の際には、画面表示されていない道路も探索対象としてコストを下げる。
コストを下げる場合、対象外（なぞり軌跡から所定範囲外）の道路についてのコストを挙げることで相対的に下げるようにしてもよい。
変更後のコストを使用して、ダイクストラ法等一般的な方法により目的地までの経路探索を行い、経路の候補を複数求める。
【００１２】
この求めた経路と、ユーザによるなぞり軌跡とによって囲まれる面積を各経路について求める。
そして、各経路に対する総コストと、面積とから走行経路を決定する。
例えば、２経路の一方を決定する場合、総コストの差が小さい場合には、面積が小さい経路を決定し、総コストの差が大きくて面積差も小さい場合には総コストが小さい経路を決定し、総コストの差も面積の差も大きい場合には面積が小さい経路を決定する。
【００１３】
このように、なぞり軌跡に近い経路という観点だけでなく、一般的な経路探索に基づく総コストという観点も加味して走行経路を決定するので、より適切な走行経路を決定することができる。
なお、決定した走行経路は１経路だけでなく、複数を決定し上位数経路をユーザに提示してユーザが最終決定をするようにしてもよい。
【００１４】
（２）実施形態の詳細
図１は本実施形態が適用されるナビゲーション装置のシステム構成図である。
このナビゲーション装置は、車両に搭載され、この図１に示すように、現在位置検出装置１０、情報処理制御装置２０、入出力装置４０及び情報記憶装置５０とを備えている。
まず、現在位置検出装置１０は、以下のような構成を有している。絶対方位センサ１１は、例えば、磁石に基づいてＮ方向の検出から、車両がいずれの方向に位置するかを検出する地磁気センサであり、絶対方位を検出する手段であればよい。
【００１５】
相対方位センサ１２は、例えば交差点を曲がったか否かを検出するものであり、ハンドルの回転部に取り付けた光学的な回転センサや回転型の抵抗ボリューム或いは車輪部に取り付ける角度センサでもよい。
また、角速度を利用して角度の変化を検出するジャイロセンサを用いてもよい。つまり、基準角度（絶対方位）に対して、相対的に変化した角度を検出することができる手段であればよい。
距離センサ１３は、例えば、車輪の回転を検出して計数するものや、加速度を検出して２回積分するものでもよい。つまり、車両の移動距離を計測できる手段であればよい。
【００１６】
ＧＰＳ（グローバル・ポジショニング・システム）受信装置１４は、人工衛星からの信号を受信する装置であり、信号の発信時刻、受信装置の位置情報、受信装置の移動速度、受信装置の進行方向など様々な情報を得ることができる。
ビーコン受信装置１５は、特定の地点に設置された送信装置より発信された信号を受信する装置である。特に、ＶＩＣＳ情報を入手することができ、渋滞情報、現在位置情報、駐車場情報等車両の走行に関する情報を入手することができる。
【００１７】
データ送受信装置１６は、電話回線や電波を利用して車両外部と通信をし、情報の交換を行うための装置である。
例えば、自動車電話、ＡＴＩＳ、ＶＩＣＳ、ＧＰＳ補正、車両間通信など様々な利用方法があり、走行に関する情報を入出力することが可能である。
【００１８】
次に、情報処理制御装置２０は、現在位置検出装置１０、入出力装置４０から入力される情報及び情報記憶装置５０に格納された情報に基づいて演算及び制御を行うとともに、演算結果をディスプレイ４２、プリンタ４３またはスピーカ４４等の出力手段に出力するように制御する手段である。
【００１９】
この情報処理制御装置２０は、以下のような構成を有している。
中央処理装置（ＣＰＵ）２１は、ナビゲーション装置全体の総括的な演算及び制御を行う。
第１ＲＯＭ２２はナビゲーションに関するプログラム、特に、現在位置の検出、本実施形態によるなぞり経路探索を含めた目的地までの経路の探索、表示案内などに関するナビゲーションプログラムを格納している。
入力インターフェイス２３は、現在位置検出装置１０からの情報を受け取る手段である。
【００２０】
ＲＡＭ２４は、後述する入力装置４１により入力された目的地の情報、通過地点の情報等の利用者が入力した情報を記憶すると共に、利用者の入力情報に基づいてＣＰＵ２１により演算された結果や、経路探索された結果、または情報記憶装置５０から読み込まれた地図情報を格納するための記憶手段である。ＲＡＭ２４には、本実施形態のなぞり経路探索においてユーザがなぞった軌跡（なぞり軌跡）のデータ（座標列）が一時保存される。
【００２１】
通信インタフェース２５は、現在位置検出装置１０からの情報、特に外部から得られる情報を入出力するための手段である。
【００２２】
第２ＲＯＭ２６は、ナビゲーションに関するプログラム、特に、本実施形態におけるなぞり経路探索処理を含め、音声案内に関するナビゲーションプログラムを格納している。なお、第１ＲＯＭ２２と第２ＲＯＭ２６を共通する１のＲＯＭで構成するようにしてもよい。
画像プロセッサ２７は、ＣＰＵ２１で処理されたベクトル情報を画像情報に処理するための処理手段である。
時計２８は、時刻を刻む。
画像メモリ２９は、画像プロセッサにより処理された画像情報を格納する手段である。
音声プロセッサ３０は、情報記憶装置５０から読み込まれた音声情報を処理し、スピーカ４４に出力する。
【００２３】
入出力装置４０は、利用者により目的地、通過地点、探索条件等のデータを入力する入力装置４１、画像を表示するディスプレイ４２、情報を印刷するプリンタ４３、音声を出力するスピーカ４４より構成される。入力装置４１は、例えば、タッチパネル、タッチスイッチ、ジョイスティック、キースイッチ等で構成される。
ディスプレイ４２には、現在地周辺の地図や、目的地までの走行経路が表示される。
本実施形態におけるなぞり経路探索では、ディスプレイ４２に指定された縮尺の地図が表示され、ユーザが表示された地図を見ながらディスプレイ４２の表面に配置されたタッチパネルをなぞることで、走行したい道路を指定したり、概略の通過コースを指定したりする。
なお、ディスプレイ４２に表示されている地図上に、ユーザがなぞった軌跡を順次表示するようにしてもよい。
【００２４】
情報記憶装置５０は、伝送路４５を介して情報処理制御装置２０に接続される。
情報記憶装置５０は、地図データファイル５１、交差点データファイル５２、ノードデータファイル５３、道路データファイル５４、写真データファイル５５、目的地データファイル５６、案内地点データファイル５７、詳細目的地データファイル５８、目的地読みデータファイル５９、その他のデータファイル６０を格納している。
この情報記憶装置５０は、一般的には、光学的記憶媒体であるＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭや磁気的記憶媒体であるハードディスクなどで構成されるが、光磁気ディスク、各種半導体メモリなどの各種情報記憶媒体で構成してもよい。
なお、書き換えが必要な情報については、書き換え可能なハードディスク、フラッシュメモリなどで構成し、その他の固定的な情報についてはＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのＲＯＭを使用するようにしてもよい。
【００２５】
地図データファイル５１には、全国道路地図、各地域の道路地図または住宅地図等の地図データが記憶されている。道路地図は、主要幹線道路、高速道路、細街路等の各道路と地上目標物（施設等）から構成される。住宅地図は、地上建造物等の外形を表す図形及び、道路名称等が表示される市街図である。細街路とは、例えば、国道、県道以下の道幅が所定値以下の比較的狭い道路である。
ディスプレイ４２に表示される地図の中では、住宅地図がもっとも縮尺が大きい地図で、この住宅地図がディスプレイに表示されている場合には、データとして保持している道路のうち、その表示領域に存在する全ての道路が表示されている。一方、表示地図の縮尺が小さくなるに従い、所定の基準に従って細い道路から順に表示対象外となる。
【００２６】
交差点データファイル５２には交差点の地理的位置座標や名称等の交差点に関するデータが、道路データファイル５４には道路の位置と種類及び車線数及び各道路間の接続関係等の道路に関するデータが、写真データファイル５５には各種施設や観光地、または主要な交差点等の視覚的表示が要求される場所を写した写真の画像データが、それぞれ記憶されている。
【００２７】
ノードデータファイル５３には地図上において経路探索に利用される各ノードの地理座標データ等を表したノードデータが記憶される。
例えば、交差点などの道路の接続点はノードにより表され、接続点の間の道路（即ち道路の内分岐しない領域）はリンクによって表される。このように、ノードデータ経路の接続関係を表した経路データとして機能している。
また、各リンクには、進入禁止や一方通行など、交通規制により走行が制限されるものに関しては、これを表す属性が付与されている。
【００２８】
目的地データファイル５６には、主要観光地や建物、電話帳に記載されている企業・事業所等の目的地になる可能性の高い場所や施設等の位置と名称等のデータが記憶されている。
案内地点データファイル５７には、道路に設置されている案内表示板の内容や分岐点の案内等、案内が必要とされる地点の案内データが記憶されている。
詳細目的地データファイル５８には、上記目的地データファイル５６に記憶されている目的地に関する詳細なデータが記憶されている。
【００２９】
このように構成されたナビゲーション装置では、次のようにして経路案内が行われる。
ナビゲーション装置は、現在位置検出装置１０で現在位置を検出し、情報記憶装置５０の地図データファイル５１から現在位置周辺の地図情報を読み込みディスプレイ４２に表示する。
そして、入力装置４１から目的地が入力されると、情報処理制御装置２０は、現在位置から目的地に至る走行経路の候補を複数探索（演算）し、ディスプレイ４２に表示した地図上に表示し、運転者がいずれかの走行経路を選択すると、選択した走行経路をＲＡＭ２４に格納することで、走行経路を取得する（走行経路取得手段）。
なお、本実施形態におけるなぞり経路探索による経路探索については後述する。
【００３０】
なお、情報処理制御装置２０は、情報処理センタに車両現在位置（又は入力された出発地）と目的地を送信し、情報処理センタで探索された目的地までの走行経路を受信することにより走行経路を取得するようにしてもよい。この場合、目的地や走行経路の通信は通信インターフェイス２５を介して、無線通信により行う。本実施形態におけるなぞり経路探索の場合には、地図上でユーザがなぞった軌跡（なぞり軌跡）のデータを情報センタに送信し、情報センタでなぞり経路探索を行う。
また、自宅等のパーソナルコンピュータ等の情報処理装置を使用して、出発地から目的地までの走行経路を探索し、ＵＳＢメモリ等の記憶媒体に格納し、該記憶媒体読取り装置を介して取得するようにしてもよい。この場合の記憶媒体読み取り装置は伝送路４５を介して情報処理制御装置２０に接続される。
【００３１】
車両が走行すると、現在位置検出装置１０によって検出された現在位置を追跡することにより、経路案内を行う。
経路案内は、探索した走行経路に対応する道路データと現在位置検出装置１０で検出される現在位置とのマップマッチングにより、地図上の車両位置を特定し、車両現在位置周辺の地図をディスプレイ４２に表示すると共に、探索した走行経路と現在位置とを地図上に表示する。
また、探索した走行経路と現在位置との関係から、案内の必要性、すなわち直進が所定距離以上続く場合、所定の進路変更地点等の走行経路の案内、及び方面案内が必要か否か等について判断し、必要である場合にはディスプレイ４２の表示及び音声による案内を実行する。
【００３２】
このように構成されたナビゲーション装置による、本実施形態のなぞり経路探索処理について次に説明する。
本実施形態によるなぞり経路探索処理は、目的地設定画面や経路設定画面における所定の選択メニューから、ユーザがなぞり経路探索を選択することで実行される。
なお、なぞり経路探索の選択は、所定縮尺の地図がディスプレイ４２に表示されていることが前提となる。このため、本実施形態では、なぞり経路探索が選択された際に既に地図が表示されている場合にはその縮尺の地図において実行され、表示されていない場合には、予め決められた所定縮尺（例えば、現在いる都道府県の全域が１画面に表示できる縮尺）の地図を表示する。いずれの場合でも地図画面の一部に縮尺を変更するための縮尺変更ボタンが表示され、ユーザはこの縮尺変更ボタンの操作することにより希望する縮尺の地図（自分がなぞり経路探索をしたい領域が表示される縮尺の地図）を表示する。
【００３３】
図２はなぞり経路探索処理の内容について表したフローチャートである。
なぞり経路探索を実行すると、情報処理制御装置２０は、ディスプレイ４２に表示している地図（ユーザがなぞった地図）に、表示領域の中で画面表示されていない道路（表示が省略されている道路）があるか否かを判断する（ステップ１１）。
【００３４】
ここで、画面表示されていない道路が存在するか否かの判断対象となる道路は、細街路を含めた全ての道路を含めるようにしてもよく、また、細街路は含めないようにしてもよい。また、通常の経路探索による探索対象とされる道路に限定し、細街路については通常経路探索の対象になっている範囲で判断対象とするようにしてもよい。
なお、表示されている地図の縮尺から、道路の省略表示があるか否かを判断するようにしてもよい。
【００３５】
全ての道路が省略されることなく表示されている場合（ステップ１１；Ｎ）、ユーザは表示されている道路上をなぞっている（トレースしている）と判断できるので、情報処理制御装置２０は、既存のなぞり検索を行う（ステップ１２）。
すなわち情報処理制御装置２０は、画面表示されている道路（リンク）となぞり軌跡とをマッチングさせ、経路をつなぐことで経路を決定し、処理を終了する。
なお、なぞり軌跡とのマッチング対象となる道路は、画面表示されている道路であるが、省略されている道路を含めてマッチングするようにしてもよい。
【００３６】
一方、ディスプレイ４２に表示されている地図が、一部の道路を省略して表示している場合（ステップ１１；Ｙ）、情報処理制御装置２０は、画面表示されている道路の本数が所定の閾値ｔ以上であるか否かを判断する（ステップ１３）。
情報処理制御装置２０は、表示道路数が所定閾値ｔより少なければ（ステップ１３；Ｎ）マッチングに使用するサンプル軌跡点数を少なくする（ステップ１４）。一方、閾値ｔ以上であれば（ステップ１３；Ｙ）、マッチングに使用するサンプル軌跡点数を多くする（ステップ１５）。すなわち、表示道路数が所定閾値ｔより少ない場合には、所定閾値ｔ以上である場合に比較してより少ないサンプル軌跡点数を使用してマッチングしている。
なお、この所定の閾値を１つ設けることでマッチングに使用するサンプル軌跡の点数を２段階に分けたが、２つ以上の閾値ｔ１、ｔ２、…を設けることで、サンプル軌跡の点数を３段階（少ない、中間、多い）とし、またそれ以上としてもよい。
【００３７】
ステップ１４又はステップ１５で決定したサンプル軌跡点数にしたがい、情報処理制御装置２０は、ユーザのなぞり操作開始から一定時間の軌跡（規定サンプル数での軌跡）とディスプレイ４２の地図上に表示されている道路をマッチングし、マッチングができたか否かを判断する（ステップ１６）。
【００３８】
ここでサンプル軌跡点と道路とのマッチングについては、サンプル軌跡点から所定距離内に表示されている道路が存在し、かつ前後のサンプル軌跡点で特定した道路と繋がっている場合に、マッチングできたと判断する。
【００３９】
表示されている道路とのマッチングができた場合（ステップ１６；Ｙ）、ユーザは画面表示された道路上をなぞっていると判断できるので、情報処理制御装置２０はステップ１２に移行して従来のなぞり検索を行い処理を終了する。
すなわち、機器制御部１０は、なぞり軌跡と表示されている道路（又はノード）をマッチングさせて走行経路を決定し、処理を終了する。
【００４０】
一方、マッチングできなかった場合（ステップ１６；Ｎ）、情報処理制御装置２０は、ディスプレイ４２に表示されている道路は意識せずになぞっていると判断し、概略なぞり検索（ステップ１７〜ステップ１９）を行う。この概略なぞり検索では、縮尺に基づいて表示が省略されている道路も経路探索の対象とする。
【００４１】
情報処理制御装置２０は、表示している地図の縮尺から、探索範囲（コスト変更範囲など）を決定する（ステップ１７）。
図３は、探索範囲の決定処理について表したフローチャートである。
情報処理制御装置２０は、まずディスプレイ４２に表示している地図の縮尺が所定の閾値Ｔ以上か否かを判断する（ステップ１７１）。
【００４２】
表示地図の縮尺が閾値Ｔ以上である場合、すなわち、詳細な地図が表示されている場合（ステップ１７１；Ｙ）、情報処理制御装置２０は、探索範囲を狭く設定する（ステップ１７２）。なぞり軌跡の点への重要度が高いと判断されるためである。
一方、縮尺が閾値Ｔ未満である場合、すなわち、広域な地図が表示されている場合（ステップ１７１；Ｎ）、探索範囲を広く設定する（ステップ１７３）。これは、広域地図を表示している場合、なぞり軌跡の点への重要度が薄れるためである。
【００４３】
図４は、なぞり軌跡と検索範囲の設定について表したものである。
図４（ａ)に示すように、ディスプレイ４２の表示地図上において、ユーザがなぞり経路探索開始地点Ｓから、なぞり軌跡Ａのようになぞり、なぞり経路探索終了地点Ｇまでなぞったものとする。
この場合、図４（ｂ)に示すように、地図表示の縮尺が閾値Ｔ以上であれば、なぞり軌跡の両側所定距離Ｓ１となる探索範囲１を設定し、閾値Ｔ未満であれば、なぞり軌跡の両側所定距離Ｓ２（＞Ｓ１）となる探索範囲２を設定する。
【００４４】
なお、探索範囲を設定する場合の所定の閾値Ｔを１つ設けることで探索範囲を２段階に分けたが、２つ以上の閾値Ｔ１、Ｔ２、…を設けることで、探索範囲を３段階（Ｓ１以内、Ｓ２以内、Ｓ３以内）とし、またそれ以上としてもよい。
【００４５】
探索範囲を決定すると情報処理制御装置２０は、決定した探索範囲に基づいて経路探索を行う（図２、ステップ１８）。
ここで行う経路探索は、経路探索Ｉ〜経路探索ＩＩＩの何れか１の方法による。以下各々の経路探索について説明する。
なお、ステップ１７（ステップ１７２又はステップ１７３）で設定する探索範囲については、以下の経路探索Ｉ〜ＩＩＩにより異なる値とすることができる。例えば、経路探索ＩＩＩを採用する場合の探索範囲は、経路探索ＩＩを採用する場合の探索範囲よりも広くすることができる。
【００４６】
（ａ)経路探索Ｉ
図５は、経路探索Ｉの方法を概念的に表したものである。
この図５では、点線がなぞり軌跡を、細線が画面に表示されている道路（リンク）を、太線が決定した経路を表している。また、各リンクの交差する点に表示された○が交差点（ノード）を表し、この○の中に表示した数字は、「交差点からなぞり軌跡までの最短距離」をコストとして設定したものである。
【００４７】
なお、この概略なぞり検索（ステップ１７〜１９）では、画面表示されていない道路も検索対象としている。
このため、図５（ａ)では、左上にコスト２と表示されている交差点にもコストが設定され、この交差点を通る道路（地図画面、及び図５（ａ)では表示されていない）も対象とされている。これは図５（ｂ)の場合も同様である。
【００４８】
そして情報処理制御装置２０は、設定した各交差点のコストに従って、なぞりの開始地点Ｓから終了地点Ｇまでのその総コスト（各ノードのコスト合計）が最小となる経路を、ステップ１７で設定した探査範囲内で探索する。
なお、一方通行などの通行付加道路やコストの極めて高いリンクは選択しない。
【００４９】
図５（ｂ)は、経路探索Ｉによる他の経路の決定について表したものである。
この図５（ｂ)に示すように、なぞり経路探索から一定距離の範囲内（図面中丸点線で表した範囲内）の交差点については、同一のコストを設定するようにしてもよい。
【００５０】
（ｂ)経路探索ＩＩ
この経路探索ＩＩでは、ステップ１７で設定した探索範囲内で、探索コストを下げたうえで（又は探索範囲外の探索コストを上げたうえで）、例えば、ダイクストラ法などの一般的な経路探索手法により、なぞり経路探索開始地点Ｓ（出発地点）からなぞり経路探索終了地点Ｇ（目的地）までの経路探索を行う。
このように、設定した探索範囲内の探索コストを下げることで、なぞり軌跡近傍の道路がより選択されやすくなる。
【００５１】
なお、探索コストは、一般的な経路探索で使用される探索コストであり、通常道路の距離や幅に応じて決められるコストである。コストを下げる場合、設定した探索範囲内の道路に対して所定値を一律下げ、又は一定の係数α１（＜１）を乗算する。また設定した範囲外の道路に対して所定値を一律上げ、又は一定の係数α２（＞１）を乗算する。
【００５２】
なお、なぞり軌跡に近い道路ほど下げ幅を大きくし、又は係数α１を小さくしてもよい。また、なぞり軌跡に遠いほど上げ幅を大きくし、又は係数α２を大きくするようにしてもよい。
【００５３】
（ｃ)経路探索ＩＩＩ
この経路探索ＩＩＩでは、ステップ１７で設定した探索範囲内の道路だけを探索対象として経路探索を行う。この経路探索は、例えば、ダイクストラ法などの一般的な経路探索手法により、なぞり経路探索開始地点Ｓ（出発地点）からなぞり経路探索終了地点Ｇ（目的地）までの経路探索を行う。
設定した探索範囲に含まれる道路か否かについては、少なくとも一部が含まれている道路を対象にする。また設定し探索範囲に含まれる交差点を端点に持つ道路を対象にしてもよい。
【００５４】
以上の経路探索Ｉ〜ＩＩＩの何れか１の方法により経路探索し、候補となる走行経路が複数探索されると、情報処理制御装置２０は、経路の選択を行う（ステップ１９）。
図６は、経路選択処理の内容を表したフローチャートである。
情報処理制御装置２０は、ステップ１８の探索経路で探索され候補となった全ての走行経路に対する総コストを算出する。
ここで算出する総コストは、経路探索開始地点Ｓを出発地とし、なぞり経路探索終了地点Ｇを目的地とし、通常のダイクストラ法等による経路探索の結果、当該各走行経路が探索された場合の総コストである。
このように、通常のダイクストラ法等による一般的な経路探索による総コストを算出するのは、走行経路としての一般的な妥当性を後で判断するためである。
【００５５】
従って、経路探索の方法として、上記経路探索Ｉを使用した場合には必ず総コストの算出が必要であるが、上記経路探索ＩＩとＩＩＩを使用した場合には、経路探索の際に総コストが算出済みなので、その値をＲＡＭ２４に記憶しておき、その記憶値を使用するようにしてもよい。
但し、経路探索ＩＩでは、ステップ１７で設定した探索範囲内で探索コストを変更した上で経路探索をしているので、変更後の探索コストに基づく総コストを使用してもよいが、変更前の探索コストに基づく総コストを再計算するようにしてもよい。
【００５６】
情報処理制御装置２０は、経路探索により候補となった走行経路となぞり軌跡とが成す面積を求める（ステップ１９２）。
このようになぞり軌跡との面積を求めるのは、各走行経路がなぞり軌跡にどれだけ沿った経路であるかを判断するためである。面積が小さいほど、なぞり軌跡に近い経路が選択されていることになる。
【００５７】
図７は、なぞり軌跡との面積を表したものである。
いま図７（ａ)に示すように、ユーザによるなぞり経路探索開始地点Ｓからなぞり経路探索終了地点Ｇまでなぞられ（なぞり軌跡Ａ）、このなぞり軌跡に基づいて概略なぞり探索により候補経路１と候補経路２が探索されたものとする。
この場合の各候補経路１と候補経路２がなぞり軌跡となす面積（囲まれる面積）は、それぞれ斜線で占める領域であり、情報処理制御装置２０は、この斜線で表した面積を算出する。
【００５８】
そして情報処理制御装置２０は、算出した各経路に対する総コストと面積を用いて複数の走行経路の候補から１の走行経路を選択する（ステップ１９３〜１９７）。
すなわち、情報処理制御装置２０は、総コストの差は一般的な経路の良し悪しの観点から経路の差を用い、また、なぞり軌跡に近いかどうかの観点から面積の差を用いて走行経路を選択する。
【００５９】
情報処理制御装置２０は、総コストの差が大きいか否かを判断する（ステップ１９３）。なお、総コストの差は、最大値と最小値との差であり、総コストの差の大小については、所定の閾値より大きいか否かにより判断する。
総コストの差が閾値より小さい場合（ステップ１９３；Ｎ）、いずれの候補も一般的な経路としての的確性があると判断できるので、情報処理制御装置２０は、最も面積が小さい走行経路に決定し（ステップ１９４）、メインルーチンにリターンする。
【００６０】
一方、総コストの差が閾値より大きい場合、情報処理制御装置２０は、面積の差が大きいか否かを判断する（ステップ１９５）。面積の差は最大値と最小値との差であり、面積の差の大小は閾値よりも大きいか否かによる。
経路コストの差が大きいが、面積の差は小さい場合（ステップ１９５；Ｎ）、全ての走行経路がなぞり軌跡の近傍に設定されているので、情報処理制御装置２０は、より一般的な的確性が高い走行経路である、最も総コストが小さい走行経路に決定し（ステップ１９６）、メインルーチンにリターンする。
【００６１】
また、総コストの差が大きく、更に面積の差も大きい場合（ステップ１９５；Ｙ）、情報処理制御装置２０は、ユーザの意志を尊重して、最も面積が小さい走行経路に決定し（ステップ１９７）、メインルーチンにリターンする。
【００６２】
説明した実施形態では、図６に示した経路選択処理において、総コストの差も面積の差も大きい場合（ステップ１９３；Ｙ、ステップ１９５；Ｙ）、最も面積が小さい経路に決定した（ステップ１９７）が、次のようにしてもよい。
図８は、経路選択処理における総コスト差、面積差の両者が大きい場合の走行経路決定方法についてのフローチャートである。
このフローチャートでは、経路１と経路２が走行経路の候補である場合について説明しているが、それ以上の場合も同様に処理するものとする。
【００６３】
情報処理制御装置２０は、コストの重要度合から係数αを決定し（ステップ２０１）、決定した係数αを経路１、経路２の総コストに積算し、換算総コストとする（ステップ２０２）。
また情報処理制御装置２０は、面積の重要度合により係数βを決定し（ステップ２０３）、決定した係数βを経路１、経路２の面積に積算して換算面積とする（ステップ２０４）。
【００６４】
ここで、コストの重要度、面積の重要度は、例えば、縮尺や地図画面上に表示される道路の数（密度）に応じて配分される係数によって決定する。また、ユーザが設定できるようにしてもよい。
【００６５】
そして情報処理制御装置２０は、各経路毎に換算総コストと換算面積の和を求め、経路１の和が小さいか否か判断し（ステップ２０５）、経路１の和が大きければ（ステップ２０５；Ｎ）経路２に決定し（ステップ２０６）、経路１の和が小さければ（ステップ２０５；Ｙ）、経路１に決定する（ステップ２０７）。
【００６６】
このように、総コストと面積を換算しその和の値が最も小さい経路を決定することで、両要素を考慮した最適な経路を選択することができる。
【００６７】
なお、係数α、βを積算するのではなく、各走行経路について算出した総コストと面積の乗算値を求め、乗算値が最小になる経路を選択するようにしてもよい。
【００６８】
以上説明したように本実施形態によるナビゲーション装置及びナビゲーション用プログラムによれば、ディスプレイ４２に表示されている地図の縮尺により表示されていない道路が存在している場合に、表示されている道路だけを対象としたマッチングを行うのではなく、表示が省略されている道路を含めて、なぞり軌跡に沿って設定した探索範囲を設定し、この探索範囲を使用して経路探索Ｉ、ＩＩ、又はＩＩＩを行うようにしている。
このため、本実施形態のなぞり経路探索によれば、ユーザは、画面表示されている道路を意識せずに自由に出発地から目的地までをなぞることができる。
【００６９】
以上、本発明のナビゲーション装置及びナビゲーション用プログラムにおける１実施形態について説明したが、本発明は説明した実施形態に限定されるものではなく、各請求項に記載した範囲において各種の変形を行うことが可能である。
例えば、説明した実施形態では、ステップ１４又はステップ１５で決定したサンプリング軌跡点数の全てが、表示されている道路とマッチングできなかった場合に、概略なぞり検索（ステップ１７〜１９）を行う場合について説明した。
これに対して、なぞり軌跡が表示道路と一定区間マッチングしている場合には、その区間はマッチングした表示道路を部分経路とし、マッチングしない他の区間に対して本実施形態の概略なぞり検索により部分経路を決定し、両部分経路を接続することで走行経路とするようにしてもよい。
【００７０】
また、説明した実施形態では、画面表示されている道路とサンプル軌跡点数のマッチングができるか否か（ステップ１６）により、概略なぞり検索を行うか否かを決定する場合について説明した。
これに対し、なぞる前又は後において、表示道路上のなぞりか、概略なぞり検索かをユーザ操作が選択するようにしてもよい。
【００７１】
また、説明した実施形態において、地図表示や探索に使用される情報を最詳細な情報を含めて探索しても、適切な走行経路を探索できない場合、「道路がありません」等の探索できない旨の表示を行うようにしてもよい。
【００７２】
また、高速道路などの有料道や、トンネル、高架橋などは、地図上に表示されても、入口が決まっていて、なぞったとしても、なぞり軌跡通りには走行できない場合がある。
この場合、広域な地図のため、間引かれた道路（表示が省略されている道路）も、なぞり操作のために表示させるようにしてもよい。
または、現在地なぞり位置から、入口が遠い場合は、該当の上記道路（高速道路やトンネル等）を薄く表示させるようにしてもよい。
【００７３】
ナビゲーション装置には、通常の経路探索を行う場合に、経路優先、時間優先等の異なる検索条件により走行経路を検索して各条件毎に走行経路の候補を地図上に表示し、その中からユーザが希望する走行経路を選択する複数経路探索機能がある。
本実施形態では、この複数経路探索で探索した各候補経路を地図上に表示した画面で、ユーザがなぞりを行うようにしてもよい。この場合、なぞり軌跡のマッチングを表示した候補経路に対して行うようにしてもよい。
【００７４】
この場合も、上記変形例とどうように、なぞり軌跡が候補経路と一定区間マッチングしている場合には、その区間はマッチングした候補経路を部分経路とし、マッチングしない他の区間に対して本実施形態の概略なぞり検索により部分経路を決定し、両部分経路を接続することで走行経路とするようにしてもよい。
【００７５】
また、説明した実施形態では、所定の選択メニューからユーザがなぞり検索を選択することでなぞり経路探索処理実行する場合について説明したが、ユーザが所定縮尺の地図を表示している画面をタッチしそのまま画面をなぞることでなぞり検索処理が実行されるようにしてもよい。
【００７６】
また、説明した実施形態及び上記各変形例では、最初にタッチした点を出発点とし、なぞり軌跡の最終点（タッチからの開放点）を目的地としてなぞり経路探索処理を実行する場合について説明したが、画面に表示されている走行経路を変更する場合になぞり経路探索処理を実行するようにしてもよい。
この場合の、画面に表示されている走行経路は、既に案内途中の走行経路を変更する場合、及び、目的地までの走行経路を探索して候補として表示した走行経路を変更する場合がある。
【００７７】
また説明した実施形態では、概略なぞり検索において、図６、７の方法により、複数の候補から１の走行経路を選択する場合（ステップ１９）について説明したが、上位所定数の候補についてユーザに提示し、ユーザが何れかを選択するようにしてもよい。
上位所定数の候補決定については、図６、図７の何れかの方法、その他の方法により決定してもよい。
ユーザの提示としては、例えば、図７（ａ)に示されるように、なぞり軌跡Ａと複数の候補経路を区別できるように地図上に表示する。なお、なぞり軌跡Ａの表示は省略してもよい。
【図面の簡単な説明】
【００７８】
【図１】本実施形態が適用されるナビゲーション装置のシステム構成図である。
【図２】なぞり経路探索処理の内容について表したフローチャートである。
【図３】探索範囲の決定処理について表したフローチャートである。
【図４】なぞり軌跡と検索範囲の設定について表した説明図である。
【図５】経路探索Ｉの方法を概念的に表した説明図である。
【図６】経路選択処理の内容を表したフローチャートである。
【図７】なぞり軌跡との面積を表した説明図である。
【図８】経路選択処理における総コスト差、面積差の両者が大きい場合の走行経路決定方法についてのフローチャートである。
【符号の説明】
【００７９】
１０ 現在位置検出装置
２０ 情報処理制御装置
２１ ＣＰＵ
４０ 入出力装置
５０ 情報記憶装置
【特許請求の範囲】
【請求項１】
画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置であって、
地図を画面表示する地図表示手段と、
前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断手段と、
ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得手段と、
前記省略判断手段で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定手段と、
を具備することを特徴とするナビゲーション装置。
【請求項２】
前記経路設定手段は、画面表示が省略されている道路を含めて経路を設定する、
ことを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記設定した範囲内に存在する各交差点に対し、前記なぞり軌跡からの距離に基づく交差点コストを設定する交差点コスト設定手段と、を備え、
前記経路設定手段は、前記設定した交差点コストの合計から走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項４】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記設定した範囲内に存在する道路のコストを、範囲外の道路コストに対して相対的に低下させるコスト変更手段と、を備え、
前記経路設定手段は、前記変更した道路のコストを使用して走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項５】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記経路設定手段は、前記設定した範囲内に存在する道路を対象として走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項６】
前記設定した走行経路の、道路のコストに基づく総コストを算出する総コスト算出手段と、
前記決定した走行経路と前記なぞり軌跡とで囲まれる面積を算出する面積算出手段と、を備え、
前記経路設定手段は、候補となる走行経路が複数存在する場合、各走行経路に対して前記算出した総コストと、面積を用いて１の走行経路を選択する、
ことを特徴とする請求項１から請求項５のうちのいずれか１の請求項に記載のナビゲーション装置。
【請求項７】
画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置を構成するコンピュータに、
地図を画面表示する地図表示機能と、
前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断機能と、
ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得機能と、
前記省略判断機能で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定機能と、
を実現させることを特徴とするナビゲーション用プログラム。
【請求項１】
画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置であって、
地図を画面表示する地図表示手段と、
前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断手段と、
ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得手段と、
前記省略判断手段で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定手段と、
を具備することを特徴とするナビゲーション装置。
【請求項２】
前記経路設定手段は、画面表示が省略されている道路を含めて経路を設定する、
ことを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記設定した範囲内に存在する各交差点に対し、前記なぞり軌跡からの距離に基づく交差点コストを設定する交差点コスト設定手段と、を備え、
前記経路設定手段は、前記設定した交差点コストの合計から走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項４】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記設定した範囲内に存在する道路のコストを、範囲外の道路コストに対して相対的に低下させるコスト変更手段と、を備え、
前記経路設定手段は、前記変更した道路のコストを使用して走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項５】
前記なぞり軌跡から所定距離となる範囲を設定する範囲設定手段と、
前記経路設定手段は、前記設定した範囲内に存在する道路を対象として走行経路を設定する、
ことを特徴とする請求項１、又は請求項２に記載のナビゲーション装置。
【請求項６】
前記設定した走行経路の、道路のコストに基づく総コストを算出する総コスト算出手段と、
前記決定した走行経路と前記なぞり軌跡とで囲まれる面積を算出する面積算出手段と、を備え、
前記経路設定手段は、候補となる走行経路が複数存在する場合、各走行経路に対して前記算出した総コストと、面積を用いて１の走行経路を選択する、
ことを特徴とする請求項１から請求項５のうちのいずれか１の請求項に記載のナビゲーション装置。
【請求項７】
画面に表示された地図上をなぞられた軌跡に基づいて走行経路を探索するなぞり検索機能を備えたナビゲーション装置を構成するコンピュータに、
地図を画面表示する地図表示機能と、
前記画面表示した地図において、当該画面内において一部の道路が省略表示されているか否かを判断する省略判断機能と、
ユーザによる前記画面表示された地図上のなぞり軌跡を取得するなぞり軌跡取得機能と、
前記省略判断機能で一部の道路が省略されていると判断した場合、前記なぞり軌跡から所定距離となる範囲を優先して経路を設定する経路設定機能と、
を実現させることを特徴とするナビゲーション用プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−１５１５４６（Ｐ２０１０−１５１５４６Ａ）
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願番号】特願２００８−３２８６１９（Ｐ２００８−３２８６１９）
【出願日】平成２０年１２月２４日（２００８．１２．２４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願日】平成２０年１２月２４日（２００８．１２．２４）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]