(57)【要約】【課題】表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することを可能とした経路探索システム、経路探索方法及びコンピュータプログラムを提供する。【解決手段】ナビゲーション装置１に表示された地図画像上をユーザがなぞる操作を受け付けた場合に、ユーザのなぞり操作によって描かれた軌跡が曲線形状である場合には、描かれた軌跡の形状に基づいて地図画像上に経路除外エリアを設定し、設定された経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索するように構成する。【選択図】図１９
2016048227.tif 000002
【特許請求の範囲】
【請求項１】
地図画像を表示装置に表示する地図画像表示手段と、
前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、
前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリアを設定する除外エリア設定手段と、
前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する経路探索手段と、を有することを特徴とする経路探索システム。
【請求項２】
前記ユーザによって描かれる軌跡の始点と終点との中点を軌跡中点として算出する軌跡中点算出手段と、
前記軌跡中点を通り前記始点と前記終点とを結ぶ直線に交差する線と、前記ユーザによって描かれる軌跡との交点を軌跡交点として算出する軌跡交点算出手段と、
前記始点から前記軌跡中点までの距離と、前記軌跡中点から前記軌跡交点までの距離の内、短い方の距離をエリア設定距離として算出する距離算出手段と、を有し、
前記除外エリア設定手段は、前記軌跡中点を中心とし、前記エリア設定距離を半径とする円を前記経路除外エリアに設定することを特徴とする請求項１に記載の経路探索システム。
【請求項３】
前記軌跡の始点と終点とを結ぶ直線と前記軌跡とが少なくとも１箇所以上で交わる場合に、各交点を中間交点として算出する中間交点算出手段を有し、
前記除外エリア設定手段は、前記ユーザによって描かれる軌跡を前記中間交点で分割した複数の分割軌跡を対象として、分割軌跡毎に前記経路除外エリアを設定することを特徴とする請求項１又は請求項２に記載の経路探索システム。
【請求項４】
前記経路探索手段は、前記中間交点を経由地とした案内経路を探索することを特徴とする請求項３に記載の経路探索システム。
【請求項５】
地図画像を表示装置に表示する地図画像表示手段と、
前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、
前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリアに設定する終点エリア設定手段と、
前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索する推奨経路探索手段と、
前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する経路選択手段と、
前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する案内経路探索手段と、を有することを特徴とする経路探索システム。
【請求項６】
前記操作受付手段は、前記表示装置の前面に配置されたタッチパネルによって前記ユーザの操作を受け付け、
前記所定距離は、前記タッチパネルに対して前記ユーザの接触した面積に基づいて設定されることを特徴とする請求項５に記載の経路探索システム。
【請求項７】
前記ユーザによって描かれる軌跡は直線形状であって、
前記経路選択手段は、前記推奨経路探索手段によって探索された推奨経路の内、最も直線性の高い形状を有する推奨経路を選択することを特徴とする請求項５又は請求項６に記載の経路探索システム。
【請求項８】
前記経路探索手段は、
前記ユーザによって描かれる軌跡の始点に基づいて前記出発地を設定し、
前記ユーザによって描かれる軌跡の終点に基づいて前記目的地を設定することを特徴とする請求項１乃至請求項７のいずれかに記載の経路探索システム。
【請求項９】
前記地図画像表示手段は、前記地図画像に重畳して前記ユーザの現在位置を示すマークを表示し、
前記経路探索手段は、
前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記軌跡の始点が道路上に位置する場合には、前記ユーザの現在位置を前記出発地に設定し、
前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記マークが道路上に位置しない場合には、前記ユーザの現在位置の周辺にある道路上の地点を前記出発地に設定し、
前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置する場合には、該始点の位置を前記出発地に設定し、
前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置しない場合には、該始点の位置の周辺にある道路上の地点を前記出発地に設定することを特徴とする請求項８に記載の経路探索システム。
【請求項１０】
前記経路探索手段は、
前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記マークが道路上に位置しない場合において、前記ユーザの現在位置の周辺に複数の道路がある場合には、前記ユーザによって描かれる軌跡に沿った方向に形成された道路上の地点を前記出発地に設定し、
前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置しない場合において、前記始点の位置の周辺に複数の道路がある場合には、前記ユーザによって描かれる軌跡に沿った方向に形成された道路上の地点を前記出発地に設定することを特徴とする請求項９に記載の経路探索システム。
【請求項１１】
地図画像表示手段が、地図画像を表示装置に表示するステップと、
操作受付手段が、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付けるステップと、
除外エリア設定手段が、前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリアを設定するステップと、
経路探索手段が、前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索するステップと、を有することを特徴とする経路探索方法。
【請求項１２】
地図画像表示手段が、地図画像を表示装置に表示するステップと、
操作受付手段が、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付けるステップと、
終点エリア設定手段が、前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリアに設定するステップと、
推奨経路探索手段が、前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索するステップと、
経路選択手段が、前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択するステップと、
案内経路探索手段が、前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索するステップと、を有することを特徴とする経路探索方法。
【請求項１３】
コンピュータを、
地図画像を表示装置に表示する地図画像表示手段と、
前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、
前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリアを設定する除外エリア設定手段と、
前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する経路探索手段と、
して機能させる為のコンピュータプログラム。
【請求項１４】
コンピュータを、
地図画像を表示装置に表示する地図画像表示手段と、
前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、
前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリアに設定する終点エリア設定手段と、
前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索する推奨経路探索手段と、
前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する経路選択手段と、
前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する案内経路探索手段と、
して機能させる為のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地へと至る案内経路の探索を行う経路探索システム、経路探索方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、探索された最適経路を案内経路として設定し、ディスプレイ画面に案内経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、ユーザを所望の目的地まで確実に案内するようになっている。また、近年は携帯電話機、スマートフォン、タブレット型端末、パーソナルコンピュータ等においても上記ナビゲーション装置と同様の機能を有するものがある。
【０００３】
また、上記ナビゲーション装置等では、できる限りユーザの意図に沿った経路を案内経路に設定する為の様々な技術が提案されている。例えば、特開２０１０−１５１５４６号公報には、ユーザにディスプレイに表示された地図画像をなぞらせるとともに、ユーザのなぞった軌跡にできる限り近い形状となる経路を案内経路に設定するように探索コストの調整を行う技術について提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１５１５４６号公報（第１０−１１頁、図５）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記特許文献１の技術では、ユーザのなぞった軌跡に近い形状の経路を案内経路として設定することは可能であるが、ユーザがなぞった軌跡が目的地への経路として妥当でない場合であっても、それに近い経路が設定されてしまう問題があった。例えば、図２３に示すように出発地と目的地の間にユーザが走行したくないエリア１０１がある場合には、ユーザはエリア１０１を上側に避けるような軌跡を描くか、下側に避ける軌跡を描くかを選択できる。そして、仮にユーザがエリア１０１を上側に避ける軌跡を描くと、設定される案内経路はエリア１０１を上側に避ける経路１０２となり、エリア１０１を下側に避ける経路１０３が設定されることは基本的にない。しかしながら、実際にはエリア１０１を上側に避ける経路１０２よりもエリア１０１を下側に避ける経路１０３のほうが適切な経路である場合もある。
【０００６】
上記特許文献１では基本的にユーザのなぞった軌跡にできる限り近い形状となるように案内経路を設定するので上記問題が生じていた。特にユーザが周辺の地理に詳しくない場合においては、上記問題が生じる場合が多くなると考えられる。
【０００７】
本発明は前記従来における問題点を解消するためになされたものであり、表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することを可能とした経路探索システム、経路探索方法及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記目的を達成するため本発明に係る第１の経路探索システム（１）は、地図画像（５１）を表示装置（１５）に表示する地図画像表示手段（４１）と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段（４１）と、前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリア（７６）を設定する除外エリア設定手段（４１）と、前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する経路探索手段（４１）と、を有することを特徴とする。
【０００９】
また、本発明に係る第２の経路探索システム（１）は、地図画像（５１）を表示装置（１５）に表示する地図画像表示手段（４１）と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段（４１）と、前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリア（６６）に設定する終点エリア設定手段（４１）と、前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索する推奨経路探索手段（４１）と、前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する経路選択手段（４１）と、前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する案内経路探索手段（４１）と、を有することを特徴とする。
【００１０】
また、本発明に係る第１の経路探索方法は、地図画像表示手段（４１）が、地図画像（５１）を表示装置（１５）に表示するステップと、操作受付手段（４１）が、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付けるステップと、除外エリア設定手段（４１）が、前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリア（７６）を設定するステップと、経路探索手段（４１）が、前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索するステップと、を有することを特徴とする。
【００１１】
また、本発明に係る第２の経路探索方法（１）は、地図画像表示手段（４１）が、地図画像（５１）を表示装置（１５）に表示するステップと、操作受付手段（４１）が、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付けるステップと、終点エリア設定手段（４１）が、前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリア（６６）に設定するステップと、推奨経路探索手段（４１）が、前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索するステップと、経路選択手段（４１）が、前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択するステップと、案内経路探索手段（４１）が、前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索するステップと、を有することを特徴とする。
【００１２】
また、本発明に係る第１のコンピュータプログラムは、コンピュータを、地図画像（５１）を表示装置（１５）に表示する地図画像表示手段（４１）と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段（４１）と、前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリア（７６）を設定する除外エリア設定手段（４１）と、前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する経路探索手段（４１）と、して機能させることを特徴とする。
【００１３】
また、本発明に係る第２のコンピュータプログラムは、コンピュータを、地図画像（５１）を表示装置（１５）に表示する地図画像表示手段（４１）と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段（４１）と、前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリア（６６）に設定する終点エリア設定手段（４１）と、前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索する推奨経路探索手段（４１）と、前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する経路選択手段（４１）と、前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する案内経路探索手段（４１）と、して機能させることを特徴とする。
【発明の効果】
【００１４】
前記構成を有する本発明に係る第１の経路探索システム、経路探索方法及びコンピュータプログラムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡に基づいて経路除外エリアを設定し、経路除外エリアを通過しないように案内経路の探索を行うので、ユーザが走行したくないエリアについては通過させることなく、その上で最適な経路を案内経路として探索することが可能である。従って、表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
【００１５】
また、本発明に係る第２の経路探索システム、経路探索方法及びコンピュータプログラムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡の終点に一定の幅を持たせて案内経路の探索を行うので、従来に比べて軌跡による探索の束縛を小さくしつつ、ユーザの描いた軌跡からは大きく相違しない最適な経路を案内経路として探索することが可能である。従って、表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本実施形態に係るナビゲーション装置の構成を示したブロック図である。
【図２】本実施形態に係る経路探索処理プログラムのフローチャートである。
【図３】液晶ディスプレイに表示された地図画像上をユーザがなぞる操作について説明した図である。
【図４】液晶ディスプレイに表示された地図画像上をユーザがなぞる操作について説明した図である。
【図５】本実施形態に係る出発地特定処理のサブ処理プログラムのフローチャートである。
【図６】ユーザのなぞり操作によって地図画像上に描かれた軌跡に基づく出発地の特定方法について説明した図である。
【図７】ユーザのなぞり操作によって地図画像上に描かれた軌跡に基づく出発地の特定方法について説明した図である。
【図８】ユーザのなぞり操作によって地図画像上に描かれた軌跡に基づく出発地の特定方法について説明した図である。
【図９】本実施形態に係る軌跡形状解析処理のサブ処理プログラムのフローチャートである。
【図１０】ユーザのなぞり操作によって地図画像上に描かれた軌跡が直線形状を有するか否かの判定方法について説明した図である。
【図１１】タッチパネルに対するユーザの指の設置面半径について説明した図である。
【図１２】２次曲線形状に分類される軌跡について示した図である。
【図１３】ｎ次曲線形状に分類される軌跡について示した図である。
【図１４】本実施形態に係る経路探索処理（直線）のサブ処理プログラムのフローチャートである。
【図１５】ユーザのなぞり操作によって地図画像上に描かれた軌跡が直線形状を有する場合における案内経路の探索方法について説明した図である。
【図１６】ユーザのなぞり操作によって地図画像上に描かれた軌跡が直線形状を有する場合における案内経路の探索方法について説明した図である。
【図１７】本実施形態に係る経路探索処理（２次曲線）のサブ処理プログラムのフローチャートである。
【図１８】ユーザのなぞり操作によって地図画像上に描かれた軌跡が２次曲線形状を有する場合における案内経路の探索方法について説明した図である。
【図１９】ユーザのなぞり操作によって地図画像上に描かれた軌跡が２次曲線形状を有する場合における案内経路の探索方法について説明した図である。
【図２０】本実施形態に係る経路探索処理（ｎ次曲線）のサブ処理プログラムのフローチャートである。
【図２１】ユーザのなぞり操作によって地図画像上に描かれた軌跡が３次曲線形状を有する場合における案内経路の探索方法について説明した図である。
【図２２】ユーザのなぞり操作によって地図画像上に描かれた軌跡が３次曲線形状を有する場合における案内経路の探索方法について説明した図である。
【図２３】従来技術の問題点について説明した図である。
【発明を実施するための形態】
【００１７】
以下、本発明に係る経路探索システムをナビゲーション装置に具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。先ず、本実施形態に係るナビゲーション装置１の概略構成について図１を用いて説明する。図１は本実施形態に係るナビゲーション装置１を示したブロック図である。
【００１８】
図１に示すように本実施形態に係るナビゲーション装置１は、ナビゲーション装置１が搭載された車両の現在位置を検出する現在位置検出部１１と、各種のデータが記録されたデータ記録部１２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ１３と、ユーザからの操作を受け付けるタッチパネル１４と、ユーザに対して車両周辺の地図や後述の経路探索処理によって探索された経路に関する経路情報等を表示する液晶ディスプレイ１５と、経路案内に関する音声ガイダンスを出力するスピーカ１６と、記憶媒体であるＤＶＤを読み取るＤＶＤドライブ１７と、プローブセンタやＶＩＣＳ（登録商標：Vehicle Information and Communication System）センタ等の情報センタとの間で通信を行う通信モジュール１８と、から構成されている。
【００１９】
以下に、ナビゲーション装置１を構成する各構成要素について順に説明する。
現在位置検出部１１は、ＧＰＳ２１、車速センサ２２、ステアリングセンサ２３、ジャイロセンサ２４等からなり、現在の車両の位置、方位、車両の走行速度、現在時刻等を検出することが可能となっている。ここで、特に車速センサ２２は、車両の移動距離や車速を検出する為のセンサであり、車両の駆動輪の回転に応じてパルスを発生させ、パルス信号をナビゲーションＥＣＵ１３に出力する。そして、ナビゲーションＥＣＵ１３は発生するパルスを計数することにより駆動輪の回転速度や移動距離を算出する。尚、上記４種類のセンサをナビゲーション装置１が全て備える必要はなく、これらの内の１又は複数種類のセンサのみをナビゲーション装置１が備える構成としても良い。
【００２０】
また、データ記録部１２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ３１や所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、データ記録部１２をハードディスクの代わりにフラッシュメモリやメモリーカードやＣＤやＤＶＤ等の光ディスクにより構成しても良い。また、地図情報ＤＢ３１は外部のサーバに格納させ、ナビゲーション装置１が通信により取得する構成としても良い。
【００２１】
ここで、地図情報ＤＢ３１は、例えば、道路（リンク）に関するリンクデータ３３、ノード点に関するノードデータ３４、経路の探索に係る処理に用いられる探索データ３５、施設に関する施設データ、地図を表示するための地図表示データ、各交差点に関する交差点データ、地点を検索するための検索データ等が記憶された記憶手段である。
【００２２】
また、リンクデータ３３としては、道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。
【００２３】
また、ノードデータ３４としては、実際の道路の分岐点（交差点、Ｔ字路等も含む）や各道路に曲率半径等に応じて所定の距離毎に設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。
【００２４】
また、探索データ３５としては、後述のように出発地（例えば車両の現在位置）から設定された目的地までの経路を探索する経路探索処理に使用される各種データについて記録されている。具体的には、交差点に対する経路として適正の程度を数値化したコスト（以下、交差点コストという）や道路を構成するリンクに対する経路として適正の程度を数値化したコスト（以下、リンクコストという）等の探索コストを算出する為に使用するコスト算出データが記憶されている。
【００２５】
ここで、交差点コストは、探索コストの算出対象となる経路に含まれる交差点に対応するノード毎に設定され、信号機の有無、交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）等によってその値が算出される。
また、リンクコストは、探索コストの算出対象となる経路に含まれるリンク毎に設定され、リンク長を基本にして、該リンクの道路属性や道路種別、道路幅、車線数、交通状況等を考慮して算出される。
【００２６】
一方、ナビゲーションＥＣＵ（エレクトロニック・コントロール・ユニット）１３は、ナビゲーション装置１の全体の制御を行う電子制御ユニットであり、演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うにあたってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、後述の経路探索処理プログラム（図２参照）等が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記憶するフラッシュメモリ４４等の内部記憶装置を備えている。尚、ナビゲーションＥＣＵ１３は、処理アルゴリズムとしての各種手段を構成する。例えば、地図画像表示手段は、地図画像を液晶ディスプレイ１５に表示する。操作受付手段は、液晶ディスプレイ１５に表示された地図画像上でユーザが軌跡を描く操作を受け付ける。除外エリア設定手段は、ユーザによって描かれた軌跡に基づいて、地図画像上に経路除外エリアを設定する。経路探索手段は、経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する。終点エリア設定手段は、ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリアに設定する。推奨経路探索手段は、終点エリア内に含まれる交差点毎に、出発地から交差点までの推奨経路を探索する。経路選択手段は、推奨経路探索手段によって探索された推奨経路の内、ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する。案内経路探索手段は、経路選択手段により選択された推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する。
【００２７】
タッチパネル１４は、液晶ディスプレイ１５の表示領域の前面に配置され、地図画像のスクロール表示を行う場合や表示領域に配置されたボタンを選択する場合や後述のように案内経路の探索を行う際に地図画像上に軌跡を描く場合等に操作される。そして、ナビゲーションＥＣＵ１３は、タッチパネル１４の操作によりタッチパネル１４から出力される検出信号に基づき、タッチパネル１４にユーザがタッチしていない状態からタッチした状態へと移行する“タッチオン”や、タッチパネル１４にユーザがタッチした状態からタッチしていない状態へと移行する“タッチオフ”を検出する。また、ユーザがタッチした地点（タッチ地点）の座標であるタッチ座標や、地図画像やボタン等の選択対象物の選択を行っている状態でタッチ地点を移動させる操作（即ちドラッグ操作やフリック操作）を受け付けた場合のタッチ座標の変位についても検出する。更に、ユーザが地図画像上でタッチオンした状態でタッチ地点を移動させた場合にはタッチ座標の軌跡についても検出する。そして、ナビゲーションＥＣＵ１３は、検出したタッチ操作やタッチ座標等に対応する各種の動作を実行すべく制御を行う。
尚、ユーザのタッチ操作を受け付ける操作手段としては、タッチパネル１４の代わりにタブレット等の操作手段を用いても良い。
【００２８】
また、液晶ディスプレイ１５には、道路を含む地図画像、交通情報、操作案内、操作メニュー、キーの案内、出発地から目的地までの案内経路、案内経路に沿った案内情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。尚、液晶ディスプレイ１５の代わりに、ＨＵＤやＨＭＤを用いても良い。
【００２９】
また、スピーカ１６は、ナビゲーションＥＣＵ１３からの指示に基づいて案内経路に沿った走行を案内する音声ガイダンスや、交通情報の案内を出力する。
【００３０】
また、ＤＶＤドライブ１７は、ＤＶＤやＣＤ等の記録媒体に記録されたデータを読み取り可能なドライブである。そして、読み取ったデータに基づいて音楽や映像の再生、地図情報ＤＢ３１の更新等が行われる。尚、ＤＶＤドライブ１７に替えてメモリーカードを読み書きする為のカードスロットを設けても良い。
【００３１】
また、通信モジュール１８は、交通情報センタ、例えば、ＶＩＣＳセンタやプローブセンタ等から送信された交通情報、プローブ情報、天候情報等を受信する為の通信装置であり、例えば携帯電話機やＤＣＭが該当する。
【００３２】
続いて、上記構成を有する本実施形態に係るナビゲーション装置１においてＣＰＵ４１が実行する経路探索処理プログラムについて図２に基づき説明する。図２は本実施形態に係る経路探索処理プログラムのフローチャートである。ここで、経路探索処理プログラムはナビゲーション装置１において経路探索を実施する為の所定の操作を受け付けた場合に実行され、出発地から目的地へと到る案内経路を探索するプログラムである。尚、以下の図２、図５、図９、図１４、図１７、図２０にフローチャートで示されるプログラムは、ナビゲーション装置１が備えているＲＡＭ４２やＲＯＭ４３に記憶されており、ＣＰＵ４１により実行される。
【００３３】
先ず、経路探索処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ４１は、液晶ディスプレイ１５に対して車両の現在位置周辺の地図画像を表示する。尚、表示される地図の縮尺はユーザが任意に変更することが可能である。また、ユーザはタッチパネル１４を用いて表示された地図画像上でフリック操作やドラッグ操作を行うことにより、表示された地図画像を任意の方向にスクロールさせ、表示対象とするエリアを変更することが可能である。また、地図画像上には車両の現在位置を示す現在位置マークについても表示される。
【００３４】
次に、Ｓ２においてＣＰＵ４１は、タッチパネル１４から送信される信号に基づいて、液晶ディスプレイ１５に表示された地図画像上をユーザがなぞる（即ち軌跡を描く）操作を受け付けたか否かを判定する。
【００３５】
例えば、図３に示すように液晶ディスプレイ１５に地図画像５１が表示された場合において、ユーザが液晶ディスプレイ１５に表示された地図画像上の地点Ｘでタッチオンし、タッチオンした状態でタッチ地点を例えば上方に移動させると、ＣＰＵ４１は地図画像上をユーザがなぞる操作を受け付けたと判定する。
【００３６】
そして、地図画像上をユーザがなぞる操作を受け付けたと判定された場合（Ｓ２：ＹＥＳ）には、Ｓ３へと移行する。それに対して、地図画像上をユーザがなぞる操作を受け付けていないと判定された場合（Ｓ２：ＮＯ）には、当該経路探索処理プログラムを終了する。
【００３７】
Ｓ３においてＣＰＵ４１は、後述の出発地特定処理（図５）を実行する。尚、出発地特定処理は、ユーザのなぞり操作によって地図画像上に描かれた軌跡の始点から経路探索において出発地とする地点を特定する処理である。
【００３８】
続いて、Ｓ４においてＣＰＵ４１は、タッチパネル１４から送信される信号に基づいて、液晶ディスプレイ１５に表示された地図画像上をユーザがなぞる（即ち軌跡を描く）操作の受け付けを終了したか否かを判定する。
【００３９】
例えば、図４に示すように液晶ディスプレイ１５に地図画像５１が表示された場合において、ユーザが液晶ディスプレイ１５に表示された地図画像上の地点Ｘでタッチオンし、タッチオンした状態でタッチ地点を移動させ、地点Ｙでタッチオフしたとすると、ＣＰＵ４１は地図画像上をユーザがなぞる操作の受け付けを終了したと判定する。
【００４０】
そして、地図画像上をユーザがなぞる操作の受け付けを終了したと判定された場合（Ｓ４：ＹＥＳ）には、Ｓ５へと移行する。それに対して、地図画像上をユーザがなぞる操作の受け付けが継続して行われていると判定された場合（Ｓ４：ＮＯ）には、受け付けを終了するまで待機する。
【００４１】
Ｓ５においてＣＰＵ４１は、ユーザのなぞり操作によって地図画像上に描かれた軌跡の終点から経路探索において目的地とする地点を特定する。具体的には、軌跡の終点（図４では地点Ｙ）を目的地に特定する。尚、軌跡ではなく事前に受け付けたユーザの操作（例えば施設の検索や選択操作）に基づいて目的地を特定する構成としても良い。その場合には、軌跡の終点は経由地として設定されることとなる。
【００４２】
次に、Ｓ６においてＣＰＵ４１は、後述の軌跡形状解析処理（図９）を実行する。尚、軌跡形状解析処理は、受け付けたユーザのなぞり操作によって地図画像上に描かれた軌跡の形状を、“直線形状”、“２次曲線（円弧）形状”、“ｎ（≧３）次曲線形状”のいずれかに分類する処理である。
【００４３】
その後、Ｓ７においてＣＰＵ４１は、前記Ｓ６の軌跡形状解析処理の結果、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“直線形状”に分類されたか否かを判定する。
【００４４】
そして、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“直線形状”に分類されたと判定された場合（Ｓ７：ＹＥＳ）には、Ｓ８へと移行する。それに対して、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“直線形状”以外に分類されたと判定された場合（Ｓ７：ＮＯ）には、Ｓ９へと移行する。
【００４５】
Ｓ９においてＣＰＵ４１は、後述の経路探索処理（直線）（図１４）を実行する。尚、経路探索処理（直線）では、受け付けたユーザのなぞり操作によって地図画像上に描かれた直線状の軌跡に基づいて、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する処理である。その後、Ｓ１２へと移行する。
【００４６】
一方、Ｓ９においてＣＰＵ４１は、前記Ｓ６の軌跡形状解析処理の結果、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“２次曲線（円弧）形状”に分類されたか否かを判定する。
【００４７】
そして、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“２次曲線（円弧）形状”に分類されたと判定された場合（Ｓ９：ＹＥＳ）には、Ｓ１０へと移行する。それに対して、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状が“ｎ（≧３）次曲線形状”に分類されたと判定された場合（Ｓ９：ＮＯ）には、Ｓ１１へと移行する。
【００４８】
Ｓ１０においてＣＰＵ４１は、後述の経路探索処理（２次曲線）（図１７）を実行する。尚、経路探索処理（２次曲線）では、受け付けたユーザのなぞり操作によって地図画像上に描かれた２次曲線の軌跡に基づいて、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する処理である。その後、Ｓ１２へと移行する。
【００４９】
一方、Ｓ１１においてＣＰＵ４１は、後述の経路探索処理（ｎ次曲線）（図２０）を実行する。尚、経路探索処理（ｎ次曲線）では、受け付けたユーザのなぞり操作によって地図画像上に描かれたｎ次曲線の軌跡に基づいて、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する処理である。その後、Ｓ１２へと移行する。
【００５０】
Ｓ１２においてＣＰＵ４１は、前記Ｓ８、Ｓ１０、Ｓ１１で探索された推奨経路を、液晶ディスプレイ１５等を介してユーザに案内する。尚、案内される経路は必ずしも１本である必要はなく、推奨経路以外に探索条件（例えば、有料優先、一般優先、距離優先）を変えて探索された複数の経路候補についても案内する構成としても良い。
【００５１】
その後、Ｓ１３においてＣＰＵ４１は、最終的なユーザの決定操作に基づいて前記Ｓ１２で案内した推奨経路をナビゲーション装置１の案内経路として設定する。その後、ナビゲーション装置１では設定された案内経路に基づく走行案内が行われる。
【００５２】
次に、前記Ｓ３において実行される出発地特定処理のサブ処理について図５に基づき説明する。図５は出発地特定処理のサブ処理プログラムのフローチャートである。
【００５３】
先ず、Ｓ２１においてＣＰＵ４１は、タッチパネル１４の検出結果に基づいて、ユーザがなぞる操作を開始した地点（即ちユーザが地図画像上に描く軌跡の始点であり、以下では軌跡始点という）の座標を取得する。例えば、図３に示す例ではユーザがタッチオンした地点Ｘの座標が取得される。尚、前記Ｓ２１で取得される座標は、地図上の座標（緯度、経度）ではなく、液晶ディスプレイ１５の画面上での位置を特定する座標系での座標である。
【００５４】
次に、Ｓ２２においてＣＰＵ４１は、液晶ディスプレイ１５に表示される車両の現在位置マーク５２の中心座標を取得する。尚、前記Ｓ２２で取得される座標は、Ｓ２１と同様に地図上の座標（緯度、経度）ではなく、液晶ディスプレイ１５の画面上での位置を特定する座標系での座標である。尚、現在位置マーク５２が液晶ディスプレイ１５に表示されていない場合には、以降の処理を行うことなくＳ２８へと移行する。
【００５５】
続いて、Ｓ２３においてＣＰＵ４１は、前記Ｓ２１で取得した軌跡始点の座標から前記Ｓ２２で取得した現在位置マーク５２の中心座標までの直線距離Ｄを算出する。
【００５６】
その後、Ｓ２４においてＣＰＵ４１は、軌跡始点が地図画像上で車両の現在位置を示す現在位置マーク５２上にあるか否かを判定する。ここで、図６に示すように地図画像上に重畳して表示され車両の現在位置を示す現在位置マーク５２は、中心座標Ｃを中心にした半径ｒ（例えば５ｍｍ）の円形状を有する。従って、前記Ｓ２３で算出された直線距離Ｄがｒ以下であれば、軌跡始点が現在位置マーク５２上にあることとなる。
【００５７】
そして、軌跡始点が地図画像上で車両の現在位置を示す現在位置マーク５２上にあると判定された場合（Ｓ２４：ＹＥＳ）、即ち直線距離Ｄがｒ以下であると判定された場合には、Ｓ２５へと移行する。それに対して、軌跡始点が地図画像上で車両の現在位置を示す現在位置マーク５２上にないと判定された場合（Ｓ２４：ＮＯ）、即ち直線距離Ｄがｒより大きいと判定された場合には、Ｓ２８へと移行する。
【００５８】
Ｓ２５においてＣＰＵ４１は、現在位置マーク５２が地図画像上に描かれたいずれかの道路上にあるか否か判定する。尚、車両が実際に道路上に位置しなくても、マップマッチング処理が行われることによって現在位置マーク５２が道路上に位置する場合がある。
【００５９】
そして、現在位置マーク５２が地図画像上に描かれたいずれかの道路上にあると判定された場合（Ｓ２５：ＹＥＳ）には、Ｓ２６へと移行する。それに対して、現在位置マーク５２が地図画像上に描かれたいずれの道路上にも位置しないと判定された場合（Ｓ２５：ＮＯ）には、Ｓ２７へと移行する。
【００６０】
Ｓ２６においてＣＰＵ４１は、現在位置マーク５２の位置、即ちＳ２２で取得した現在位置マーク５２の中心座標に対応する地図上の地点を出発地として特定する。その後、Ｓ４へと移行する。
【００６１】
一方、Ｓ２７においてＣＰＵ４１は、現在位置マーク５２の周辺にある道路上の地点を出発地として特定する。具体的には、図７に示すように現在位置マーク５２の中心座標Ｃから最も近い位置にある道路上の地点（図７に示す例では道路５３上の地点Ｍ）を出発地として特定する。尚、図８に示すようにユーザの現在位置の周辺に複数の道路があって、現在位置マーク５２の中心座標Ｃからほぼ同距離に複数の道路上の地点（図８に示す例では道路５３上の地点Ｍと道路５４上の地点Ｎ）がある場合、即ち、出発地の候補が複数ある場合には、ユーザによって描かれる軌跡に沿った方向に形成された道路上の地点を出発地に設定する。例えば、図８に示す例ではユーザによって描かれる軌跡５５は道路５４に沿った上方向へ描かれるので、道路５４上の地点Ｎが出発地として特定されることとなる。その後、Ｓ４へと移行する。
【００６２】
また、Ｓ２８においてＣＰＵ４１は、軌跡始点が地図画像上に描かれたいずれかの道路上にあるか否か判定する。尚、軌跡始点が道路と完全に一致しなくても、道路から所定距離以内（例えば３ｍｍ）以内にあれば、道路上にあるとみなすのが望ましい。
【００６３】
そして、軌跡始点が地図画像上に描かれたいずれかの道路上にあると判定された場合（Ｓ２８：ＹＥＳ）には、Ｓ２９へと移行する。それに対して、軌跡始点が地図画像上に描かれたいずれの道路上にも位置しないと判定された場合（Ｓ２８：ＮＯ）には、Ｓ３０へと移行する。
【００６４】
Ｓ２９においてＣＰＵ４１は、軌跡始点の位置、即ちＳ２１で取得した軌跡始点の座標に対応する地図上の地点を出発地として特定する。その後、Ｓ４へと移行する。
【００６５】
一方、Ｓ３０においてＣＰＵ４１は、軌跡始点の周辺にある道路上の地点を出発地として特定する。尚、具体的な処理の内容については、前記Ｓ２７において現在位置マーク５２の中心座標を軌跡始点の座標に置き換えた処理と同様であるので、詳細は省略する。その後、Ｓ４へと移行する。
【００６６】
次に、前記Ｓ６において実行される軌跡形状解析処理のサブ処理について図９に基づき説明する。図９は軌跡形状解析処理のサブ処理プログラムのフローチャートである。
【００６７】
先ず、Ｓ３１においてＣＰＵ４１は、ユーザのなぞり操作によって地図画像上に描かれた軌跡の幅Ｗを算出する。具体的には、先ず図１０に示すように軌跡６０の始点Ｓと終点Ｇとを結んだ直線６１を描く。次に、直線６１に対して平行で且つ軌跡６０と少なくとも一点で重複するという条件を満たす直線について、直線６１の左右両側に直線６１から最も離れた位置にそれぞれ描く。図１０に示す例では直線６２と直線６３が描かれることとなる。そして、直線６２と直線６３の間隔を軌跡の幅Ｗとして算出する。尚、軌跡６０が直線である場合には軌跡の幅は“０”とする。
【００６８】
次に、Ｓ３２においてＣＰＵ４１は、前記Ｓ３１で算出された軌跡の幅Ｗが、ユーザの指の設置面半径ｒの２倍以下か否か判定する。尚、ユーザの指の設置面とは、図１１に示すように、なぞり操作によって軌跡を描く際にタッチパネル１４に対してユーザの指６４が接触したエリア６５である。尚、エリア６５はタッチパネル１４から送信される信号に基づいて特定する。そして、エリア６５を円形に近似し、半径ｒを算出する。尚、半径ｒは固定値（例えば５ｍｍ）としても良い。
【００６９】
そして、前記Ｓ３１で算出された軌跡の幅Ｗが、ユーザの指の設置面半径ｒの２倍以下と判定された場合（Ｓ３２：ＹＥＳ）には、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状を“直線形状”に分類する（Ｓ３３）。その後、Ｓ７へと移行する。
【００７０】
それに対して、前記Ｓ３１で算出された軌跡の幅Ｗが、ユーザの指の設置面半径ｒの２倍より大きいと判定された場合（Ｓ３２：ＮＯ）には、Ｓ３４へと移行する。
【００７１】
Ｓ３４においてＣＰＵ４１は、ユーザのなぞり操作によって地図画像上に描かれた軌跡を解析し、軌跡の変曲点の数を算出する。
【００７２】
次に、Ｓ３５においてＣＰＵ４１は、ユーザのなぞり操作によって地図画像上に描かれた軌跡の変曲点の数が２以上か否かを判定する。
【００７３】
そして、軌跡の変曲点の数が１のみであると判定された場合（Ｓ３５：ＮＯ）には、図１２に示すように軌跡６０の形状は２次曲線（円弧）形状であると推定できる。従って、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状を“２次曲線（円弧）形状”に分類する（Ｓ３６）。その後、Ｓ７へと移行する。尚、変曲点の数ではなく軌跡６０と、軌跡６０の始点Ｓと終点Ｇとを結んだ直線６１との交点があるか否かを判定し、交点が無い場合に“２次曲線（円弧）形状”に分類する構成としても良い
【００７４】
一方、軌跡の変曲点の数が２以上あると判定された場合（Ｓ３５：ＹＥＳ）には、図１３に示すように軌跡６０の形状は３次以上のｎ次曲線（波形）形状であると推定できる。従って、ユーザのなぞり操作によって地図画像上に描かれた軌跡の形状を“ｎ（≧３）次曲線形状”に分類する（Ｓ３６）。その後、Ｓ７へと移行する。尚、変曲点の数ではなく軌跡６０と、軌跡６０の始点Ｓと終点Ｇとを結んだ直線６１との交点があるか否かを判定し、交点がある場合に“ｎ（≧３）次曲線形状”に分類する構成としても良い
【００７５】
次に、前記Ｓ８において実行される経路探索処理（直線）のサブ処理について図１４に基づき説明する。図１４は経路探索処理（直線）のサブ処理プログラムのフローチャートである。
【００７６】
先ず、Ｓ４１においてＣＰＵ４１は、図１５に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０の終点Ｇから所定距離以内を終点エリア６６に設定し、地図情報に基づいて終点エリア６６内にある交差点を抽出する。尚、所定距離は前記Ｓ３２で用いたユーザの指の設置面半径ｒに対応する地図上の距離（即ち、１万分の１の縮尺ではユーザの指の設置面半径ｒが５ｍｍであれば５０ｍとなる）の４倍とする。
【００７７】
以降のＳ４２及びＳ４３の処理は、前記Ｓ４１で抽出された全ての交差点を対象として行い、全ての交差点を対象としてＳ４２及びＳ４３の処理が行われた後にＳ４４へと移行する。
【００７８】
Ｓ４２においてＣＰＵ４１は、前記Ｓ３で特定された出発地を出発し、処理対象となる交差点を目的地とした推奨経路の探索を行う。具体的には、公知のダイクストラ法を用い、コスト値の合計が最小となる経路を推奨経路とする。例えば、図５に示すように終点エリア６６内に３つの交差点Ａ〜Ｃが存在する場合には、最終的に各交差点Ａ〜Ｃを目的地とした３本の推奨経路が探索されることとなる。
【００７９】
次に、Ｓ４３においてＣＰＵ４１は、前記Ｓ４２で探索された推奨経路の形状を解析し、直線性を算出する。
【００８０】
その後、Ｓ４４においてＣＰＵ４１は、前記Ｓ４２及びＳ４３の処理によって算出された交差点毎の推奨経路の直線性を比較し、最も推奨経路の直線性の高い交差点を選択する。そして、選択された交差点を経由地に設定する。例えば、図１６に示す例では、交差点Ａを目的地とした推奨経路７０と、交差点Ｂを目的地とした推奨経路７１と、交差点Ｃを目的地とした推奨経路７２の内、推奨経路７１が最も直線性が高いので、交差点Ｂが経由地として選択されることとなる。ここで、ユーザのなぞり操作によって地図画像上に描かれた軌跡は直線形状を有するので、前記Ｓ４４で選択される交差点を目的地として前記Ｓ４２で探索された推奨経路は、前記Ｓ４２で探索された複数の推奨経路の内、ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路となる。
【００８１】
次に、Ｓ４５においてＣＰＵ４１は、前記Ｓ４４で設定された経由地を経由することを条件とし、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する。具体的には、公知のダイクストラ法を用い、コスト値の合計が最小となる経路を推奨経路とする。その結果、前記Ｓ４４で直線性が最も高いと判定された推奨経路（図１６に示す例では推奨経路７１）を含み、経由地に選択された交差点（図１６に示す例では交差点Ｂ）から目的地へと到る経路が探索される。
【００８２】
続いて、前記Ｓ１０において実行される経路探索処理（２次曲線）のサブ処理について図１７に基づき説明する。図１７は経路探索処理（２次曲線）のサブ処理プログラムのフローチャートである。
【００８３】
先ず、Ｓ５１においてＣＰＵ４１は、図１８に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０の始点Ｓから終点Ｇまでの直線距離Ｄを算出する。
【００８４】
次に、Ｓ５２においてＣＰＵ４１は、先ず図１８に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０の始点Ｓと終点Ｇとの中点を軌跡中点Ｈとして算出する。更に、軌跡中点Ｈを通り始点Ｓと終点Ｇとを結ぶ直線６１に直交する線７５と、軌跡６０との交点を軌跡交点Ｋとして算出する。そして、軌跡中点Ｈから軌跡交点Ｋまでの距離Ｒを算出する。
【００８５】
続いて、Ｓ５３においてＣＰＵ４１は、前記Ｓ５２において算出された軌跡中点Ｈから軌跡交点Ｋまでの距離Ｒと、始点Ｓから軌跡中点Ｈまでの距離Ｄ／２とを比較し、距離Ｒの方が短いか否か判定する。
【００８６】
そして、前記Ｓ５２において算出された軌跡中点Ｈから軌跡交点Ｋまでの距離Ｒの方が短いと判定された場合（Ｓ５３：ＹＥＳ）には、Ｓ５４へと移行する。それに対して、始点Ｓから軌跡中点Ｈまでの距離Ｄ／２の方が短いと判定された場合（Ｓ５３：ＮＯ）には、Ｓ５５へと移行する。
【００８７】
Ｓ５４においてＣＰＵ４１は、前記Ｓ５２において算出された軌跡中点Ｈから軌跡交点Ｋまでの距離Ｒをエリア設定距離として設定し、軌跡中点Ｈを中心とし、エリア設定距離を半径とする円を経路除外エリアとして設定する。例えば、図１８に示す例では、始点Ｓから軌跡中点Ｈまでの距離Ｄ／２よりも軌跡中点Ｈから軌跡交点Ｋまでの距離Ｒの方が短いので、軌跡中点Ｈを中心とした半径Ｒの円が経路除外エリア７６として設定される。
【００８８】
一方、Ｓ５５においてＣＰＵ４１は、始点Ｓから軌跡中点Ｈまでの距離Ｄ／２をエリア設定距離として設定し、軌跡中点Ｈを中心とし、エリア設定距離を半径とする円を経路除外エリアとして設定する。
【００８９】
次に、Ｓ５６においてＣＰＵ４１は、前記Ｓ５４又はＳ５５で設定された経路除外エリアを通過しないことを条件とし、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する。具体的には、公知のダイクストラ法を用い、コスト値の合計が最小となる経路を推奨経路とする。Ｓ５６では、図１９に示すように軌跡６０の形状に近い経路除外エリア７６を上側に避ける経路７７以外に、経路除外エリア７６を下側に避ける経路７８についても検索対象となり、全長、交通状況、道路種別等を考慮してより適切な経路が推奨経路として選択されることとなる。
【００９０】
続いて、前記Ｓ１１において実行される経路探索処理（ｎ次曲線）のサブ処理について図２０に基づき説明する。図２０は経路探索処理（ｎ次曲線）のサブ処理プログラムのフローチャートである。
【００９１】
以降のＳ６１〜Ｓ６５の処理は、軌跡の描くｎ次曲線を複数に分割し、分割後の全ての軌跡（分割軌跡）を対象として実施される。具体的には、図２１に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０の始点Ｓと終点Ｇを結ぶ直線６１と、軌跡６０との交点を中間交点Ｑとして算出し、中間交点Ｑで軌跡６０を分割する。尚、分割軌跡は２次曲線形状を有することとなる。そして、分割された全ての分割軌跡を対象として、軌跡の始点に近い分割軌跡から順にＳ６１〜Ｓ６５の処理が実施される。例えば、図２１に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０が３次曲線である場合には、先ず始点Ｓ側の２次曲線形状を有する分割軌跡８１を対象にしてＳ６１〜Ｓ６５の処理が実行され、その後に終点Ｇ側の同じく２次曲線形状を有する分割軌跡８２を対象にしてＳ６１〜Ｓ６５の処理が実行される。そして、全ての分割軌跡を対象としてＳ６１〜Ｓ６５の処理が行われた後にＳ６６へと移行する。
【００９２】
尚、各分割軌跡を対象にして行われるＳ６１〜Ｓ６５の処理は、前記Ｓ５１〜Ｓ５５の処理と同様であるので説明は省略する。
【００９３】
次に、Ｓ６６においてＣＰＵ４１は、図２１に示すようにユーザのなぞり操作によって地図画像上に描かれた軌跡６０の始点Ｓと終点Ｇを結ぶ直線６１と、軌跡６０との交点を中間交点Ｑとして算出する。尚、中間交点Ｑの数は軌跡６０の形状によって異なり、３次曲線であれば１個、４次曲線であれば２個となる。
【００９４】
次に、Ｓ６７においてＣＰＵ４１は、前記Ｓ６６で算出された全ての中間交点Ｑを経由地とし、分割軌跡毎に前記Ｓ６４又はＳ６５で設定された全ての経路除外エリアを通過しないことを条件とし、前記Ｓ３で特定された出発地から前記Ｓ５で特定された目的地までの推奨経路を探索する。具体的には、公知のダイクストラ法を用い、コスト値の合計が最小となる経路を推奨経路とする。Ｓ６７では、図２２に示すように軌跡６０の形状に近い形で経路除外エリア７６を避ける経路８５以外に、軌跡６０と異なる方向から経路除外エリア７６を避ける経路８６についても検索対象となり、全長、交通状況、道路種別等を考慮してより適切な経路が推奨経路として選択されることとなる。
【００９５】
以上詳細に説明した通り、本実施形態に係るナビゲーション装置１、ナビゲーション装置１による経路探索方法及びナビゲーション装置１で実行されるコンピュータプログラムでは、ナビゲーション装置１に表示された地図画像上をユーザがなぞる操作を受け付けた場合に、ユーザのなぞり操作によって描かれた軌跡が曲線形状である場合には、描かれた軌跡の形状に基づいて地図画像上に経路除外エリアを設定し（Ｓ５４、Ｓ５５、Ｓ６４、Ｓ６５）、設定された経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する（Ｓ５６、Ｓ６７）ので、ユーザが走行したくないエリアについては通過させることなく、その上で最適な経路を案内経路として探索することが可能である。従って、液晶ディスプレイ１５に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
また、ユーザのなぞり操作によって描かれた軌跡が特に直線形状である場合には、描かれた軌跡の終点から所定距離以内の範囲を終点エリアに設定し（Ｓ４１）、終点エリア内に含まれる交差点毎に、出発地から交差点までの推奨経路を探索し（Ｓ４２）、探索された推奨経路の内、ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択し（Ｓ４４）、選択された推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する（Ｓ４５）ので、従来に比べて軌跡による探索の束縛を小さくしつつ、ユーザの描いた軌跡からは大きく相違しない最適な経路を案内経路として探索することが可能である。従って、液晶ディスプレイ１５に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
【００９６】
尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、液晶ディスプレイ１５に配置されたタッチパネル１４によりユーザによる軌跡を描く操作を受け付けることとしているが、タッチパネル以外の操作手段を用いてユーザの操作を受け付ける構成としても良い。例えば、マウスやタッチパッド等が該当する。また、マウスを用いる場合にはマウスによって操作されるポインタによって描かれる軌跡に基づいて経路探索を行う。
【００９７】
また、本実施形態では、ユーザのなぞり操作によって描かれた軌跡が特に直線形状である場合と、ｎ（≧２）次曲線である場合における経路探索処理についてそれぞれ説明したが、ユーザのなぞり操作によって描かれた軌跡が直線形状とｎ次曲線形状の組み合わせである場合についても適用可能である。その場合には、直線形状とｎ次曲線形状の境界を経由地として設定し、直線形状部分についてはＳ８、ｎ次曲線形状部分についてはＳ１０又はＳ１１により推奨経路をそれぞれ探索し、それらを組み合わせることによって最終的な案内経路として出力するように構成する。
【００９８】
また、本発明はナビゲーション装置以外に、経路探索機能を有する装置に対して適用することが可能である。例えば、携帯電話機、スマートフォン、タブレット端末、パーソナルコンピュータ等（以下、携帯端末等という）に適用することも可能である。また、サーバと携帯端末等から構成されるシステムに対しても適用することが可能となる。その場合には、上述した経路探索処理プログラム（図２）の各ステップは、サーバと携帯端末等のいずれが実施する構成としても良い。また、本発明を携帯端末等に適用する場合には、車両以外の移動体、例えば、携帯端末等のユーザや２輪車等に対する経路の変更にも本願発明を適用することが可能である。
【００９９】
また、本発明に係る経路探索システムを具体化した実施例について上記に説明したが、経路探索システムは以下の構成を有することも可能であり、その場合には以下の効果を奏する。
【０１００】
例えば、第１の構成は以下のとおりである。
地図画像を表示装置に表示する地図画像表示手段と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、前記ユーザによって描かれた軌跡に基づいて、前記地図画像上に経路除外エリアを設定する除外エリア設定手段と、前記経路除外エリアを通過しないことを条件とした出発地から目的地までの案内経路を探索する経路探索手段と、を有することを特徴とする。
上記構成を有する経路探索システムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡に基づいて経路除外エリアを設定し、経路除外エリアを通過しないように案内経路の探索を行うので、ユーザが走行したくないエリアについては通過させることなく、その上で最適な経路を案内経路として探索することが可能である。従って、表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
【０１０１】
また、第２の構成は以下のとおりである。
前記ユーザによって描かれる軌跡の始点と終点との中点を軌跡中点として算出する軌跡中点算出手段と、前記軌跡中点を通り前記始点と前記終点とを結ぶ直線に交差する線と、前記ユーザによって描かれる軌跡との交点を軌跡交点として算出する軌跡交点算出手段と、前記始点から前記軌跡中点までの距離と、前記軌跡中点から前記軌跡交点までの距離の内、短い方の距離をエリア設定距離として算出する距離算出手段と、を有し、前記除外エリア設定手段は、前記軌跡中点を中心とし、前記エリア設定距離を半径とする円を前記経路除外エリアに設定することを特徴とする。
上記構成を有する経路探索システムによれば、地図画像上でユーザによって描かれた軌跡の形状に基づいて、ユーザが走行を避けたいと意図しているエリアを経路除外エリアとして正確に特定することが可能である。
【０１０２】
また、第３の構成は以下のとおりである。
前記軌跡の始点と終点とを結ぶ直線と前記軌跡とが少なくとも１箇所以上で交わる場合に、各交点を中間交点として算出する中間交点算出手段を有し、前記除外エリア設定手段は、前記ユーザによって描かれる軌跡を前記中間交点で分割した複数の分割軌跡を対象として、分割軌跡毎に前記経路除外エリアを設定することを特徴とする。
上記構成を有する経路探索システムによれば、地図画像上でユーザによって描かれた軌跡の形状が複雑な形状であっても、ユーザが走行を避けたいと意図しているエリアを経路除外エリアとして正確に特定することが可能である。
【０１０３】
また、第４の構成は以下のとおりである。
前記経路探索手段は、前記中間交点を経由地とした案内経路を探索することを特徴とする。
上記構成を有する経路探索システムによれば、地図画像上でユーザによって描かれた軌跡の形状に基づいて経由地を設定することによって、ユーザの描いた軌跡から大きく相違しない最適な経路を案内経路として探索することが可能である。
【０１０４】
また、第５の構成は以下のとおりである。
地図画像を表示装置に表示する地図画像表示手段と、前記表示装置に表示された前記地図画像上でユーザが軌跡を描く操作を受け付ける操作受付手段と、前記ユーザによって描かれる軌跡の終点から所定距離以内の範囲を終点エリアに設定する終点エリア設定手段と、前記終点エリア内に含まれる交差点毎に、前記出発地から前記交差点までの推奨経路を探索する推奨経路探索手段と、前記推奨経路探索手段によって探索された推奨経路の内、前記ユーザによって描かれる軌跡の形状と最も近い形状を有する推奨経路を選択する経路選択手段と、前記経路選択手段により選択された前記推奨経路を含むことを条件とした出発地から目的地までの案内経路を探索する案内経路探索手段と、を有することを特徴とする。
上記構成を有する経路探索システムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡の終点に一定の幅を持たせて案内経路の探索を行うので、従来に比べて軌跡による探索の束縛を小さくしつつ、ユーザの描いた軌跡からは大きく相違しない最適な経路を案内経路として探索することが可能である。従って、表示装置に表示された地図画像上でユーザによって描かれた軌跡の意図を考慮しつつ、ユーザに対してより適切な案内経路を提供することが可能となる。
【０１０５】
また、第６の構成は以下のとおりである。
前記操作受付手段は、前記表示装置の前面に配置されたタッチパネルによって前記ユーザの操作を受け付け、前記所定距離は、前記タッチパネルに対して前記ユーザの接触した面積に基づいて設定されることを特徴とする。
上記構成を有する経路探索システムによれば、ユーザのタッチパネルに対するタッチ操作に基づいて、終点エリアの形状を適切に設定することが可能となる。
【０１０６】
また、第７の構成は以下のとおりである。
前記ユーザによって描かれる軌跡は直線形状であって、前記経路選択手段は、前記推奨経路探索手段によって探索された推奨経路の内、最も直線性の高い形状を有する推奨経路を選択することを特徴とする。
上記構成を有する経路探索システムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡が直線形状である場合において、ユーザの描いた軌跡から大きく相違しない直線形状を有する経路を案内経路として探索することが可能である。
【０１０７】
また、第８の構成は以下のとおりである。
前記経路探索手段は、前記ユーザによって描かれる軌跡の始点に基づいて前記出発地を設定し、前記ユーザによって描かれる軌跡の終点に基づいて前記目的地を設定することを特徴とする。
上記構成を有する経路探索システムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡に基づいて、案内経路の出発地及び目的地とする地点をユーザの意図に沿って適切に特定することが可能となる。
【０１０８】
また、第９の構成は以下のとおりである。
前記地図画像表示手段は、前記地図画像に重畳して前記ユーザの現在位置を示すマークを表示し、前記経路探索手段は、前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記軌跡の始点が道路上に位置する場合には、前記ユーザの現在位置を前記出発地に設定し、前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記マークが道路上に位置しない場合には、前記ユーザの現在位置の周辺にある道路上の地点を前記出発地に設定し、前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置する場合には、該始点の位置を前記出発地に設定し、前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置しない場合には、該始点の位置の周辺にある道路上の地点を前記出発地に設定することを特徴とする。
上記構成を有する経路探索システムによれば、表示装置に表示された地図画像上でユーザによって描かれた軌跡の始点と、ユーザの現在位置を示すマークと、地図画像上に描かれる道路との位置関係に基づいて、案内経路の出発地とする地点をユーザの意図に沿って適切に特定することが可能となる。
【０１０９】
また、第１０の構成は以下のとおりである。
前記経路探索手段は、前記ユーザによって描かれる軌跡の始点が前記マーク上にあって、且つ前記マークが道路上に位置しない場合において、前記ユーザの現在位置の周辺に複数の道路がある場合には、前記ユーザによって描かれる軌跡に沿った方向に形成された道路上の地点を前記出発地に設定し、前記ユーザによって描かれる軌跡の始点が前記マーク上になく、且つ該始点が道路上に位置しない場合において、前記始点の位置の周辺に複数の道路がある場合には、前記ユーザによって描かれる軌跡に沿った方向に形成された道路上の地点を前記出発地に設定することを特徴とする。
上記構成を有する経路探索システムによれば、案内経路の出発地となる地点の候補が複数ある場合において、表示装置に表示された地図画像上でユーザによって描かれた軌跡の形状を参照することにより、よりユーザの意図に沿った地点を出発地に特定することが可能となる。
【符号の説明】
【０１１０】
１              ナビゲーション装置
１３            ナビゲーションＥＣＵ
１４            タッチパネル
１５            液晶ディスプレイ
３２            道路状況情報ＤＢ
４１            ＣＰＵ
４２            ＲＡＭ
４３            ＲＯＭ
５１            地図画像
５２            現在位置マーク
６０            軌跡
６６            終点エリア
７６            経路除外エリア
【図１】
2016048227.tif 000003
【図２】
2016048227.tif 000004
【図３】
2016048227.tif 000005
【図４】
2016048227.tif 000006
【図５】
2016048227.tif 000007
【図６】
2016048227.tif 000008
【図７】
2016048227.tif 000009
【図８】
2016048227.tif 000010
【図９】
2016048227.tif 000011
【図１０】
2016048227.tif 000012
【図１１】
2016048227.tif 000013
【図１２】
2016048227.tif 000014
【図１３】
2016048227.tif 000015
【図１４】
2016048227.tif 000016
【図１５】
2016048227.tif 000017
【図１６】
2016048227.tif 000018
【図１７】
2016048227.tif 000019
【図１８】
2016048227.tif 000020
【図１９】
2016048227.tif 000021
【図２０】
2016048227.tif 000022
【図２１】
2016048227.tif 000023
【図２２】
2016048227.tif 000024
【図２３】
2016048227.tif 000025