(57)【要約】【課題】ユーザに不要なリスクや手間を強いることなく、かつ地図データの作成コストを上昇させることなく、適切な目的道路への経路を提示・案内する。【解決手段】目的地指定受付手段２３で目的地の指定を受け付けると、目的リンク選択手段２５が、指定された目的地近傍の各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択し、この選択された前記目的リンクへの経路を、経路探索手段２７が、道路データに基いて計算により探索する。【選択図】図１
2008190913.tif 000002
【特許請求の範囲】
【請求項１】
道路区間を表す各道路リンクをノードで接続した道路データを予め記憶した記憶手段を有するナビゲーション装置において、
目的地の指定を受け付ける目的地指定受付手段と、
指定された前記目的地近傍の前記各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択する目的リンク選択手段と、
選択された前記目的リンクへの経路を前記道路データに基いて計算により探索する経路探索手段と、
をコンピュータの演算制御部により実現することを特徴とするナビゲーション装置。
【請求項２】
前記目的リンク選択手段は、
目的地の位置から所定範囲内の各道路リンクを対象リンクとして順次選択のうえ、対象リンクにおける前記目的地からの最近傍点を求め、その最近傍点とその目的地との距離が目的リンクの現候補より近ければ、
現在の対象リンクから両方向にそれぞれ辿り、複数の他のリンクが接続されている最初のノード又は行止りのノードを、二つ、両端ノードとして特定し、
両端ノード間のいずれかのリンクと、２次元的に交差するがノードで接続されていない他の各リンクの数と各交点を求め、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間に無い場合、及び、前記他のリンクの数が一までの場合は、現在の対象リンクを目的リンクの現候補とし、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間にある場合は、現在の対象リンクに関する判断を終了する
ことを特徴とする請求項１記載のナビゲーション装置。
【請求項３】
道路区間を表す各道路リンクをノードで接続した道路データを予め記憶した記憶手段を有するナビゲーション装置の制御方法において、
コンピュータの演算制御部により、目的地の指定を受け付ける目的地指定受付手段と、経路探索用の目的リンクを選択する目的リンク選択手段と、経路を探索する経路探索手段と、を実現するとともに、
前記目的リンク選択手段に、指定された前記目的地近傍の前記各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択する目的リンク選択処理を実行させ、
前記経路探索手段に、選択された前記目的リンクへの経路を前記道路データに基いて計算により探索させる経路探索処理を実行させる
ことを特徴とするナビゲーション装置の制御方法。
【請求項４】
前記目的リンク選択手段に、前記経路探索処理において、
目的地の位置から所定範囲内の各道路リンクを対象リンクとして順次選択させたうえ、対象リンクにおける前記目的地からの最近傍点を求めさせ、その最近傍点とその目的地との距離が目的リンクの現候補より近ければ、
現在の対象リンクから両方向にそれぞれ辿り、複数の他のリンクが接続されている最初のノード又は行止りのノードを、二つ、両端ノードとして特定させ、
両端ノード間のいずれかのリンクと、２次元的に交差するがノードで接続されていない他の各リンクの数と各交点を求めさせ、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間に無い場合、及び、前記他のリンクの数が一までの場合は、現在の対象リンクを目的リンクの現候補とさせ、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間にある場合は、現在の対象リンクに関する判断を終了させる
ことを特徴とする請求項３記載のナビゲーション装置の制御方法。
【請求項５】
道路区間を表す各道路リンクをノードで接続した道路データを予め記憶した記憶手段を有するナビゲーション装置の制御プログラムにおいて、
そのプログラムはコンピュータの演算制御部を制御することにより、目的地の指定を受け付ける目的地指定受付手段と、経路探索用の目的リンクを選択する目的リンク選択手段と、経路を探索する経路探索手段と、を実現するとともに、
前記目的リンク選択手段に、指定された前記目的地近傍の前記各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択する目的リンク選択処理を実行させ、
前記経路探索手段に、選択された前記目的リンクへの経路を前記道路データに基いて計算により探索させる経路探索処理を実行させる
ことを特徴とするナビゲーション装置の制御プログラム。
【請求項６】
前記目的リンク選択手段を制御することにより、前記経路探索処理において、
目的地の位置から所定範囲内の各道路リンクを対象リンクとして順次選択させたうえ、対象リンクにおける前記目的地からの最近傍点を求めさせ、その最近傍点とその目的地との距離が目的リンクの現候補より近ければ、
現在の対象リンクから両方向にそれぞれ辿り、複数の他のリンクが接続されている最初のノード又は行止りのノードを、二つ、両端ノードとして特定させ、
両端ノード間のいずれかのリンクと、２次元的に交差するがノードで接続されていない他の各リンクの数と各交点を求めさせ、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間に無い場合、及び、前記他のリンクの数が一までの場合は、現在の対象リンクを目的リンクの現候補とさせ、
前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間にある場合は、現在の対象リンクに関する判断を終了させる
ことを特徴とする請求項５記載のナビゲーション装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション技術の改良に関する。
【背景技術】
【０００２】
近年、自動車の分野で急速に普及したナビゲーション装置は、予め記憶した道路データを用い、ＧＰＳなどで検出する自車位置を地図上に表示したり、施設検索や地図スクロールなどで指定される目的地への経路を探索計算し、その経路にそって画面表示や音声出力などで分岐点の進行方向などを誘導案内するものである。
【０００３】
このようなナビゲーション装置で用いる道路データは、地図データとも呼ぶが、道路区間ごとの両端位置を表すリンク（「道路リンク」とも呼ぶ）を、道路の屈曲点や交差点などの分岐点を表すノードで接続することで、道路のネットワーク構成を表している。
【０００４】
また、このようなナビゲーション装置における経路探索で一般に用いられる、いわゆるダイクストラ法では、まず、ユーザが指定した目的地の位置情報などを基に、道路データの各リンクのうち、探索経路の終端とする目的リンクを選定するが、その選定基準としては、第一に、目的地の位置と道路リンクとの２次元的な距離の短さを用いる。
【０００５】
それに加えて例えば、道路の種別（都市間高速道路、都市高速道路、一般国道、市道など）を表す情報や、または周囲との往来が制限されているか否かの情報を地図データに格納しておき、それらの情報を用いて、特定の条件を満たす道路、例えば高速道路を目的リンクの候補から除外する提案も存在する（特許文献１参照）。
【０００６】
たしかに、高速道路など、道路の種別については、現地の確認をせずとも、公的な資料などから容易に割り出せるため、比較的低廉なコストで情報を収集し地図データに採録可能である。
【特許文献１】特開２００５−１０６７４２
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、高速道路以外のいわゆる一般道路の類に関し、各部分で例えば高架やトンネルの区間で周囲と往来できないかどうかの情報（説明の便宜上「往来可否情報」と呼ぶこととする）については、多くの場合に現地確認を要し、往来可否情報を収集し地図データに盛り込むには非常な大きなコストと時間がかかる。
【０００８】
そのような往来可否情報を地図データに収録しない場合、従来の経路探索処理では、高架道路か否かといった往来可否の判別を行っていなかったので、探索された経路通りにユーザが目的地近くまで行ってみると、例えば目的地の建物の斜め上を横切る高架道路上に案内されるなど、実際には目的地に到着できないリスクが生じていた。
【０００９】
これを避けるため、ユーザ自身がナビゲーション装置以外の例えば紙の地図などで目的リンクに適した道路を調べ、そこを目的地として指定する対応も考えられるが、実際的には煩雑で、技術的な解決が希求されていた。
【００１０】
本発明は、上記のような従来技術の課題を解決するもので、その目的は、ユーザに不要なリスクや手間を強いることなく、かつ地図データの作成コストを上昇させることなく、適切な目的道路への経路を提示・案内することである。
【課題を解決するための手段】
【００１１】
上記の目的をふまえ、本発明の一態様は、道路区間を表す各道路リンクをノードで接続した道路データを予め記憶した記憶手段を有するナビゲーション装置において、目的地の指定を受け付ける目的地指定受付手段と、指定された前記目的地近傍の前記各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択する目的リンク選択手段と、選択された前記目的リンクへの経路を前記道路データに基いて計算により探索する経路探索手段と、をコンピュータの演算制御部により実現することを特徴とする。
【００１２】
このように、立体交差といった高架やトンネルなど、目的地と往来できない道路区間について、実地調査による情報やユーザが調べる負担がなくとも、道路データに本来含まれる道路リンクとノードを活用した幾何学的な計算を行うことにより、不適切な道路区間を目的リンクから除外し適切な経路の探索や案内が可能となる。
【００１３】
本発明の他の態様は、さらに、前記目的リンク選択手段は、目的地の位置から所定範囲内の各道路リンクを対象リンクとして順次選択のうえ、対象リンクにおける前記目的地からの最近傍点を求め、その最近傍点とその目的地との距離が目的リンクの現候補より近ければ、現在の対象リンクから両方向にそれぞれ辿り、複数の他のリンクが接続されている最初のノード又は行止りのノードを、二つ、両端ノードとして特定し、両端ノード間のいずれかのリンクと、２次元的に交差するがノードで接続されていない他の各リンクの数と各交点を求め、前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間に無い場合、及び、前記他のリンクの数が一までの場合は、現在の対象リンクを目的リンクの現候補とし、前記他のリンクの数が二以上かつ前記最近傍点が前記交点同士の間にある場合は、現在の対象リンクに関する判断を終了することを特徴とする。
【００１４】
このように、候補の道路リンクを含む連続したリンク列について、他のリンクと２次元的には交差しているが、それらのリンクと実際には接続していない交点間の場合に目的リンクから除外することにより、明快な基準による少ない演算負荷かつ高い精度で、高架やトンネルなど不適切な場所への誘導案内を回避可能となる。
【００１５】
なお、方法及びプログラムについても上記各態様に準ずる。
【発明の効果】
【００１６】
以上のように、本発明によれば、ユーザに不要なリスクや手間を強いることなく、かつ地図データの作成コストを上昇させることなく、適切な目的道路への経路を提示・案内することが可能となる。
【発明を実施するための最良の形態】
【００１７】
次に、本発明を実施するための最良の実施形態について、図に沿って説明する。なお、背景技術や課題での説明と共通の前提事項については適宜省略する。
【００１８】
〔１．構成〕
本実施形態におけるナビゲーション装置（以下「本装置」と呼ぶ）は、車両に搭載し、逐次検出する自車位置と目的地への経路に基づき誘導案内を出力するもので、図１の構成図に示す以下の各要素を備える。
【００１９】
まず、ディスク装置２は、道路区間を表す各道路リンクをノードで接続した道路データを予め記憶した、ＨＤＤ等の記憶手段である。また、ＧＰＳレシーバ３、ジャイロ４、車速パルスセンサ５、バック信号センサ６は、自車の位置や方位を逐次検出するための航法センサ群である。また、本装置は、ユーザからの目的地指定や経路探索要求等の操作を受け付けるための入力装置として、リモコン受光器７およびリモコン８、その他の図示しない操作スイッチ類を有する。
【００２０】
また、本装置は、地図や経路、その他必要な情報をユーザに視覚的に提示するため、液晶ディスプレイ９等の表示装置を有するが、液晶ディスプレイ９をタッチパネル式とすることにより入力装置を兼ねさせることも可能である。
【００２１】
また、本装置の情報処理機能を実現する制御プログラムは、本装置内のＲＯＭ１０に格納しておき、本装置の起動時に必要に応じてＲＡＭ１１に展開する。ユーザからの経路探索要求等により経路探索を実行する場合、ディスク装置２に予め格納した道路データの必要な部分をＲＡＭに読み込み、読み込んだ道路データをＣＰＵ１２で適宜利用することにより、適切と考えられる経路を求め、また、液晶ディスプレイ９などの表示装置に自車周辺地図とともに表示する。
【００２２】
すなわち、ＣＰＵ１２はコンピュータの演算制御部であり、前記制御プログラムが制御することにより、各手段２３，２５，２７を実現する。これら各手段は、以下のような本発明及び本実施形態の機能作用を実現実行する処理手段である。なお、誘導案内出力など従来同様のナビゲーション処理やその手段については、本発明の主要な特徴ではないため省略する。
【００２３】
〔２．作用の概要〕
以上のように構成した本実施形態では、目的地指定受付手段２３で目的地の指定を受け付けると、目的リンク選択手段２５が、指定された目的地近傍の各道路リンクを候補として、その道路リンク又はその道路リンクと連なる道路リンクと、それら以外の他の道路リンクと、の交差箇所におけるノードの有無に基く適不適の判断により、経路探索用の目的リンクを選択し、この選択された目的リンクへの経路を、経路探索手段２７が、道路データに基いて計算により探索する。
【００２４】
〔３．具体的処理内容〕
より具体的には、本装置では、ユーザからの要求等のイベント発生により、経路探索処理を開始するが、図２は、その際における処理手順のフローチャートであり、図３は、説明用に道路データの一例を示すもので、リンクを直線で、ノードを黒丸で表す。
【００２５】
そして、図２の処理手順では、まず、ＧＰＳレシーバ、ジャイロ、車速パルス、バック信号センサ等の信号データから計算した車両位置と、ユーザにより指定された目的地Ｄ（図３）を求め（ステップＳ１）、目的地周辺を含む区域の道路データをディスク装置２からＲＡＭ１１に読み込む（ステップＳ２）。そして、目的リンク選択手段２５は、読み込んだ道路データに含まれ、目的地の位置から所定範囲内の各道路リンクを対象リンクとして順次選択のうえ、各対象リンクＬｍ（ｍ＝１，２，３，…）について以下の処理を行うことで目的リンクを選択する。
【００２６】
まず、対象リンクＬｍにおける目的地Ｄからの最近傍点Ｐｍ（図３の例ではＰ１）と、その最近傍点Ｐｍと目的地Ｄとの間の距離Ｄｍ（図３の例ではＤ１）を求める（ステップＳ３）。この距離Ｄｍが、すでに記憶されている目的リンクの現候補（Ｌｘとする）の距離Ｄｘより遠ければ（ステップＳ４）、この時点で目的リンク候補から除外する（Ｓ５）。
【００２７】
一方、Ｌｘより近ければ（ステップＳ４）、まず、現在の対象リンクから両方向にそれぞれ辿り、複数の他のリンクが接続されている最初のノード又は行止りのノードを、二つ、両端ノードとして特定する。すなわち、まず、リンクＬｍ（図３の例ではリンクＬ１）の一方の端点ノードからリンクをたどっていき、２以上の目的地が接続されているか行き止まりとなるノードＡｍ（図３の例ではノードＡ１）を求める（ステップＳ６）。また、Ｌｍの他方の端点ノードから同様にリンクをたどっていき、２以上の目的地が接続されているか行き止まりとなるノードＢｍ（図３の例ではノードＢ１）を求める（ステップＳ７）。
【００２８】
次に、両端ノード間のいずれかのリンクと、２次元的に交差するがノードで接続されていない他の各リンクの数と各交点を求める。すなわち、１以上の連続したリンク列であるＡｍからＢｍ（図３の例ではＡ１〜Ｂ１）を構成しているいずれかのリンクと、２次元的に交差している道路の本数Ｎｍ（＝ｔ）と、各交点Ｃｍ−１，Ｃｍ−２，…，Ｃｍ−ｔを求める（ステップＳ８）。
【００２９】
そして、ここで求められた他のリンクの数が二以上かつ最近傍点Ｐｍが交点同士の間に無い場合と、他のリンクの数が一までの場合は、現在の対象リンクＬｍを目的リンクの現候補とし、他のリンクの数が二以上かつ最近傍点Ｐｍが交点同士の間にある場合は、現在の対象リンクに関する判断を終了する。
【００３０】
すなわち、本数Ｎｍの値をチェックし（ステップＳ９）、Ｎｍ＝０か１であった場合は、両端ノードＡｍとＢｍ間は立体交差道路でないとみなし、すでに目的リンク候補としていた道路リンクＬｘと置き換えて、対象リンクＬｍを新たな目的リンク候補とする（ステップ１３）。
【００３１】
また、Ｎｍ＞１であった場合は、交点Ｃｍ−１〜Ｃｍ−ｔの間は立体交差道路であるとみなし、最近傍点Ｐｍが交点Ｃｍ−１〜Ｃｍ−ｔの間にあるかどうかをチェックする（ステップＳ１１）。例えば、図３の例では、交差点である両端ノードＡ１とＢ１間は立体交差区間であり、４のリンク４本と立体交差している。
【００３２】
そして、最近傍点が交点間の場合は対象リンクＬｍを目的リンク候補としないと判断する（ステップＳ１２）。Ｃｍ＞１だが（ステップＳ９）、最近傍点Ｐｍが交点Ｃｍ−１〜Ｃｍ−ｔの間に無い場合は（ステップＳ１１）、目的リンク候補としていた道路リンクＬｘと置き換えて、対象リンクＬｍを新たな目的リンク候補とする（ステップＳ１３）。
【００３３】
そして、上記により選定された目的リンクを用いて経路探索処理を行い（ステップＳ１４）、その結果をディスプレイ装置により視覚的に表示するとともに、表示や音声によりユーザへの経路誘導案内を行う。
【００３４】
〔４．効果〕
以上のように、本実施形態では、目的リンク選択手段により、立体交差といった高架やトンネルなど、目的地と往来できない道路区間について、実地調査による情報やユーザが調べる負担がなくとも、道路データに本来含まれる道路リンクとノードを活用した幾何学的な計算を行うことにより、不適切な道路区間を目的リンクから除外し適切な経路の探索や案内が可能となる。
【００３５】
また、本実施形態では、図２に示した処理手順により、候補の道路リンクを含む連続したリンク列について、他のリンクと２次元的には交差しているが、それらのリンクと実際には接続していない交点間の場合に目的リンクから除外することにより、明快な基準による少ない演算負荷かつ高い精度で、高架やトンネルなど不適切な場所への誘導案内を回避可能となる。
【００３６】
〔５．他の実施形態〕
なお、本発明は、上記実施形態に限定されるものではなく、以下に例示するものやそれ以外の他の実施形態も含むものである。例えば、図１の構成、図２のフローチャート、図３の道路データや、それらに関する説明についても、適宜変更実施可能であることは言うまでもなく、例えば、目的リンク選択の基準として、２以上の交点以外にも、交点は一つだがその位置から最近傍点が所定距離内の場合に、土地の落差があるものと推定し回避するなども考えられる。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施形態の構成を示す図。
【図２】本発明の実施形態における処理手順を例示するフローチャート。
【図３】本発明の実施形態における道路データを例示する図。
【符号の説明】
【００３８】
１…本装置
２…ディスク装置
３…レシーバ
４…ジャイロ
５…車速パルスセンサ
６…バック信号センサ
７…リモコン受光器
８…リモコン
９…タッチパネル式液晶ディスプレイ
１０…ＲＯＭ
１１…ＲＡＭ
１２…ＣＰＵ
２３…目的地指定受付手段
２５…目的リンク選択手段
２７…経路探索手段
【図１】
2008190913.tif 000003
【図２】
2008190913.tif 000004
【図３】
2008190913.tif 000005