車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法
【課題】レーンを考慮して短時間で目的地に到着できる経路を探索すること。
【解決手段】自車位置を特定する特定手段（ＣＰＵ１１）と、目的地の入力を受け付ける受付手段（タッチパネル式液晶ディスプレイ）と、記憶装置（ＨＤＤ１４）に記憶された道路情報を参照し、自車位置から目的地までの経路を探索する探索手段（ＣＰＵ１１）を有し、探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する。
【解決手段】自車位置を特定する特定手段（ＣＰＵ１１）と、目的地の入力を受け付ける受付手段（タッチパネル式液晶ディスプレイ）と、記憶装置（ＨＤＤ１４）に記憶された道路情報を参照し、自車位置から目的地までの経路を探索する探索手段（ＣＰＵ１１）を有し、探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法に関する。
【背景技術】
【０００２】
特許文献１には、道路の通りやすさの指標である車線数を考慮して、経路探索を行う車載型ナビゲーション装置に関する技術が開示されている。また、車線数に加えて、交差点での進行方向に応じた追加コストを付与（例えば、直進よりも左折に対して、左折よりも右折に対して大きな追加コストを付与）することで、できるだけ右左折の回数が少ない経路をユーザに呈示することも行われている。
【特許文献１】特開２００２−６２１５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、例えば、同じ道路から右折する場合でもどの交差点で右折するかによって実際の所要時間（右折待ち時間）が異なるケースがしばしば存在するが、上述した技術では、このようなケースを考慮することは困難である。また、大半の車両が右左折し、直進する車両は僅少であるため、レーン設定等の運用により、右左折はしやすく、直進はしづらい交通制御がなされる場合も存在するが、上述した技術ではこのような交通制御に対しては対応することができない。
【０００４】
そこで、本発明の目的は、レーンを考慮して短時間で目的地に到着できる経路を探索することが可能な車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法を提供することにある。
【課題を解決するための手段】
【０００５】
上述課題を解決するため、本発明は、記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置において、自車位置を特定する特定手段と、目的地の入力を受け付ける受付手段と、前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索手段を有し、前記探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、ことを特徴とする。
この構成によれば、レーンを考慮して短時間で目的地に到着できるとともに、他の車両の走行も阻害しない車載型ナビゲーション装置を提供することができる。
【０００６】
他の発明は、上記発明に加えて、進入リンクから脱出リンクへ通じるレーンの数が多い場合には、当該脱出リンクに対するコストを低く計算し、レーンの数が少ない場合には、当該脱出リンクに対するコストを高く計算することを特徴とする。
これにより、レーンが複数存在する脱出リンクが存在する場合には、当該脱出リンクのコストを低く計算することにより、より通行しやすいリンクが選択される可能性を高くすることができる。
【０００７】
また、本発明は、記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置の制御方法において、自車位置を特定する特定ステップと、目的地の入力を受け付ける受付ステップと、前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索ステップを有し、前記探索ステップは、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、ことを特徴とする。
この方法によれば、レーンを考慮して短時間で目的地に到着できるとともに、他の車両の走行も阻害しない車載型ナビゲーション装置の制御方法を提供することができる。
【発明の効果】
【０００８】
本発明によれば、レーンを考慮して短時間で目的地に到着できる経路を探索することが可能な車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法を提供することができる。
【発明を実施するための最良の形態】
【０００９】
（Ａ）発明の実施形態の説明
つぎに図面を参照して本発明の好適な実施の形態について説明する。図１は、本発明の実施形態である車載型ナビゲーション装置１０の構成例を示す図である。この図１に示すように、車載型ナビゲーション装置１０は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１１、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１２、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１３、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）１４、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）レシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、バック信号センサ１８、リモコン受信部１９、タッチパネル式液晶ディスプレイ２０、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｅｄ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）２１、バス２２、および、リモコン（リモートコントローラ）２５を有している。
【００１０】
ここで、ＣＰＵ１１は、ＲＯＭ１２またはＨＤＤ１４に記憶されているプログラムに基づいて装置の各部を制御する中央制御装置である。ＲＯＭ１２は、ＣＰＵ１１が実行する基本的なプログラムやデータを格納している半導体記憶装置である。ＲＡＭ１３は、ＣＰＵ１１がプログラムを実行する際にワーキングエリアとして機能する半導体記憶装置である。ＨＤＤ１４は、基本的なプログラムとしてのオペレーティングシステムや、後述する経路探索や経路案内を実行するためのアプリケーションプログラムや、経路探索や経路案内を実行するために必要なデータ（地図情報等）を有している。ＧＰＳレシーバ１５は、複数のＧＰＳ衛星から送信される信号を受信し、これらの信号に含まれているタイムスタンプに基づいて、自己の位置を示す情報（緯度、経度、高度等）を生成して出力する。ジャイロセンサ１６は、例えば、車両の３軸（ヨー軸、ロール軸、ピッチ軸）方向の加速度を検出して出力する。車速パルスセンサ１７は、車両の走行速度を示す車速パルスを検出して出力する。バック信号センサ１８は、車両がバックしていることを示すバック信号を検出して出力する。リモコン受信部１９は、リモコン２５から送信された赤外線信号を受信し、ユーザの操作に応じた情報を出力する。タッチパネル式液晶ディスプレイ２０は、表示装置としての液晶ディスプレイに、入力装置としてのタッチパネルが重畳するように配置されて構成されている。ユーザは、液晶ディスプレイに表示された情報を参照しながら、タッチパネルを操作することにより、装置に対して指示を行うことができる。ＡＳＩＣ２１は、ＧＰＳレシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、バック信号センサ１８、および、リモコン受信部１９から出力される信号を入力し、車載型ナビゲーション装置１０に適合する形式にデータを変換して出力する。
【００１１】
図２および図３は、ＨＤＤ１４に格納されているノード情報およびリンク情報の一例を示す図である。なお、本実施形態では、道路情報は、道路の分岐点（例えば、交差点）を示すノードと、ノード同士を接続するリンクとによって構成される。図２は、ノードが格納されたノードテーブルの一例を示している。図２の例では、図の左側に示すように、ｎ個のノードに関する情報が格納されており、図の右側に拡大して示すように、ノード＃０に関する情報は、リンク情報とレーン情報とから構成される。リンク情報としては、この例では、ノード＃０に接続されているリンクの数（この例ではｍ個）と、それぞれのリンクに関する情報とが格納されている。レーン情報としては、この例では、ノード＃０が有するレーン情報の定義数（この例ではｐ個）と、それぞれのレーンに関する情報とが記憶されている。なお、「レーン」とは、交差点等の分岐点に設けられた車線を示し、例えば、右折する車両が通行する右折レーン、左折する車両が通行する左折レーン、直進する車両が通行する直進レーン等が存在する。なお、直進する車両と左折する車両が通行する直進／左折レーン、および、直進する車両と右折する車両が通行する直進／右折レーンを含めてもよい。
【００１２】
図３は、図２に示すレーン情報（レーンデータ）の一例を示す図である。図３の例では、レーンデータは、当該ノードに進入するリンクを特定するための進入リンク番号と、当該リンクのレーン数と、進入リンクに接続される脱出リンク（経路）の定義数（この例ではｒ個）と、各経路に脱出する脱出リンクと、それぞれの脱出リンクに適用されるレーンの種類を示す情報を有している。例えば、図４に示すようなリンクおよびノードが存在する場合において、ノードＮ３のレーンデータとしては、例えば、図５に示す情報が格納されている。すなわち、図５の例は、ノードＮ３に進入リンクＬ２から進入する場合に対応する情報であり、この例では、「レーン数」は「４」であることからレーンが４つ存在することが示され、脱出リンクとしては「Ｌ３」および「Ｌ８」の２種類が存在することから、「経路数」は「２」とされている。また、「経路＃０脱出先リンク」としての「Ｌ３」の適用レーン（リンクＬ３に脱出可能なレーン）は「第１レーン」および「第２レーン」であり、「経路＃１脱出先リンク」としての「Ｌ８」の適用レーン（リンクＬ８に脱出可能なレーン）は「第３レーン」および「第４レーン」であることが示されている。つまり、リンクＬ２からノードＮ３へ進入する場合、リンクＬ３へ通ずるレーンは第１および第２の２レーンであり、リンクＬ８へ通ずるレーンは第３および第４の２レーンであり、合計４つのレーンが存在している。
【００１３】
（Ｂ）発明の概略動作の説明
つぎに、図４〜図６を参照して、本実施形態の概略動作について説明する。図４についてさらに詳細に説明すると、丸印はノードを示し、ノード同士を結ぶ線分はリンクを示している。この例では、ノードＮ１〜Ｎ６と、リンクＬ１〜Ｌ６とが存在している。ここで、リンクＬ１〜Ｌ６は全て同一種類（例えば、国道）であり、リンクＬ１およびリンクＬ３〜Ｌ６は全て２００ｍの長さを有し、リンクＬ２は２５０ｍの長さを有している。また、リンクＬ１およびリンクＬ３〜Ｌ６の基本コスト（リンク自体のコスト）値は全て１００００であり、リンクＬ２の基本コスト値は１２５００である。また、ノードＮ３には、図５に示すようなレーンデータが設定されており、その他のノードＮ１，Ｎ２およびノードＮ４〜Ｎ６には、レーンデータは設定されていないとする。また、図６は、レーンデータに応じてコスト計算に適用される追加コストの一例を示す図である。この図６では、該当するレーンが存在しない場合の追加コストは「８０００」であり、該当するレーンが１レーン存在する場合の追加コストは「４０００」であり、該当するレーンが２レーン以上存在する場合の追加コストは「０」とされている。
【００１４】
以上のような場合において、リンクＬ１からリンクＬ６（ノードＮ２からノードＮ６）への最適経路を求める場合の本実施形態の概略動作について説明する。
【００１５】
まず、リンクＬ１にノードＮ２を介して接続されるリンクは、リンクＬ２とリンクＬ７の２本である。ノードＮ２にはレーンデータが存在しないので、リンクＬ２のコスト値は基本値である１２５００に対して、図６の「該当レーン無し」に対応する追加コスト値「８０００」が加算された「２０５００」となる。また、リンクＬ７のコスト値は基本値である１００００に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１６】
リンクＬ７からリンクＬ５への経路では、ノードＮ４にはレーンデータが存在しないことから、リンクＬ５のコスト値は、基本値である「１００００」に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１７】
リンクＬ２からリンクＬ８への経路では、図５に示すように、ノードＮ３にはレーンデータが存在し、かつ、該当する適用レーンが２レーン存在する（第３レーンおよび第４レーンが存在する）ので、リンクＬ８のコスト値は、基本値である「１００００」に対して、「該当レーン有り（２レーン以上）」に対応する追加コスト値「０」が加算された「１００００」となる。
【００１８】
リンクＬ８からリンクＬ６への経路およびリンクＬ５からリンクＬ６への経路では、ノードＮ５にはレーンデータが存在しないことから、リンクＬ６のコスト値は、基本値である「１００００」に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１９】
以上のコスト計算の結果、リンクＬ２〜リンクＬ８〜リンクＬ６と経由する場合のトータルのコストは２０５００＋１００００＋１８０００＝４８５００となり、また、リンクＬ７〜リンクＬ５〜リンクＬ６と経由する場合のトータルのコストは１８０００＋１８０００＋１８０００＝５４０００となる。このため、走行距離は長いにも拘わらず、右折レーンが整備されて走行しやすいと考えられるリンクＬ２〜リンクＬ８〜リンクＬ６が経路として選択される。
【００２０】
（Ｃ）発明の詳細な動作の説明
つぎに、図７〜図９のフローチャートを参照して、本発明において実行される処理の詳細について説明する。図７は、車両の現在位置から目的値までの経路を探索する処理の概要を説明するための図である。例えば、ユーザがタッチパネル式液晶ディスプレイ２０を操作することにより、経路探索の要求を行ったとすると、ステップＳ１０において、ＣＰＵ１１は、ＧＰＳレシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、および、バック信号センサ１８から得られた情報に基づいて、自車の現在位置を算出するとともに、タッチパネル式液晶ディスプレイ２０から入力された情報（例えば、目的地の住所、名称、電話番号、緯度・経度情報）に基づいて目的地を求める。
【００２１】
つぎに、ステップＳ１１では、ＣＰＵ１１は、車両の現在位置と目的地の間に存在する道路データをＨＤＤ１４から読み出し、ＲＡＭ１３に格納する。つづいて、ステップＳ１２では、ＣＰＵ１１は、ステップＳ１１において読み込んだ道路データから、車両位置に最も近い道路および目的地に最も近い道路を抽出する。そして、ステップＳ１３において、ＣＰＵ１１は、ステップＳ１２で抽出した道路を、甲種経路としてＲＡＭ１３に記憶する。
【００２２】
ステップＳ１４では、ＣＰＵ１１は、甲種経路候補のうち、最も有力と判断できる道路を選択し、乙種経路候補として記憶する。ステップＳ１５では、ＣＰＵ１１は、ステップＳ１４において選択された道路に接続し、通行可能な道路を全て求める。そしてステップＳ１６では、ＣＰＵ１１は、ステップＳ１５で求めた道路の各々について、コストを計算する。なお、この処理の詳細については、図８および図９を参照して後述する。
【００２３】
ステップＳ１７では、ＣＰＵ１１は、ステップＳ１６で求めた全ての道路を、甲種経路候補として記憶する。ステップＳ１８では、ＣＰＵ１１は、車両位置から連続した乙種経路候補と目的地から連続した乙種経路候補とが適切に接続したか否かを判定し、接続したと判定した場合（ステップＳ１８；Ｙｅｓ）にはステップＳ１９に進み、それ以外の場合（ステップＳ１８；Ｎｏ）にはステップＳ１４に戻って前述の場合と同様の処理を繰り返す。
【００２４】
ステップＳ１９では、ＣＰＵ１１は、接続した一連の乙種経路候補群を経路として確定し、これ以降、当該確定された経路に基づいて、経路表示を行うとともに、ユーザへの案内を行う。
【００２５】
つぎに、図８および図９を参照して、経路のコスト計算処理の詳細について説明する。ここで、図８は、自車位置の近傍に存在するスタートノードから、目的地の近傍に存在するゴールノードまでの間の各ノードのコストを計算する処理を説明するフローチャートであり、図９は図８に示すステップＳ５５の処理の詳細を説明するフローチャートである。なお、図８の処理は、いわゆる「ダイクストラ法」に基づいて各ノードのコスト値を計算する。この図８に示すフローチャートの処理が実行されると、ステップＳ３０において、ＣＰＵ１１は、車両位置の近傍に存在するスタートノードのコスト値を「０」に設定するとともに、他のノードのコスト値を「∞」に設定する。図４の例では、現在、リンクＬ１を走行中であるとすると、スタートノードとしてのノードＮ２のコストが「０」に設定されるとともに、スタートノードからゴールノード（ノードＮ６）までの間のノードＮ３〜Ｎ６のコスト値が「∞」に設定される。図１０（Ａ）は、ステップＳ３０の処理の結果を示す図である。この図では、ノードＮ２のコスト値は「０」とされ、それ以外のノードのコスト値は「∞」とされている。
【００２６】
ステップＳ３１では、ＣＰＵ１１は、未確定ノードの中から、最小のコスト値を有するノードを特定する。ここで、「未確定ノード」とは、ノードのコスト値が確定していないノードをいい、後述する「確定ノード」とは、ノードのコスト値が確定したノードをいう。図４の例では、未確定ノードの中で最小のコスト値を有するのは、ノードＮ２であるので（他のノードのコスト値は無限大であるので）、ノードＮ２のコストが最小値のノードとして特定される。ステップＳ３２では、ＣＰＵ１１は、ステップＳ３１において特定したノードを確定ノードに設定する。なお、図１０において、確定ノードにはハッチングが施されており、未確定ノードにはハッチングが施されていない。
【００２７】
ステップＳ３３では、ＣＰＵ１１は、ステップＳ３２で設定した確定ノードに接続する未確定ノードのコストを計算する。いまの例では、ステップＳ３２において、ノードＮ２が確定ノードに設定されているので、ノードＮ２に接続される未確定ノードとしてのノードＮ３およびノードＮ４のコストが計算される。なお、この処理の詳細は、図９を参照して後述するが、簡単に説明すると、確定ノードがレーンデータを有している場合には、レーンデータと、リンクのコスト値に基づいて、対象となるノードのコスト値が計算され、レーンデータを有しない場合には、レーンデータが存在しない場合の追加コストと、リンクのコスト値に基づいて、対象となるノードのコスト値が算定される。図１０の例では、ノードＮ２は、レーンデータを有しないことから、レーンデータを有しない場合の追加コストとしての「８０００」が、リンクＬ２のコスト値「１２５００」と、リンクＬ７のコスト値「１００００」とにそれぞれ加算され、得られた値「２０５００」と「１８０００」とがノードＮ３およびノードＮ４のそれぞれのコスト値として算出される。
【００２８】
ステップＳ３４では、ＣＰＵ１１は、ステップＳ３３において算出したノードのコスト値が、現在設定されているコスト値よりも小さい場合には、新たに算出した値によって更新する。図１０の例では、ノードＮ３およびノードＮ４に現在設定されているコスト値はともに「∞」であり、ステップＳ３３において算出されたコスト値は「２０５００」および「１８０００」であるので、更新がなされて、「２０５００」および「１８０００」がノードＮ３およびノードＮ４のそれぞれのコスト値として設定される（図１０（Ｂ）参照）。
【００２９】
ステップＳ３５では、ＣＰＵ１１は、未確定ノードが存在するか否かが判定され、未確定ノードが存在すると判定した場合（ステップＳ３５；Ｙｅｓ）にはステップＳ３１に戻って同様の処理を繰り返し、それ以外の場合（ステップＳ３５；Ｎｏ）にはステップＳ３６に進む。図１０の例では、その時点では、図１０（Ｂ）に示すように、ノードＮ２のみが確定ノードの状態であるので、ステップＳ３１に戻って前述の場合と同様の処理を繰り返す。
【００３０】
ステップＳ３１〜ステップＳ３５の処理が繰り返されることにより、図１０および図１１に示すように、各ノードのコスト値が計算されて確定されていく。詳細に説明すると、ステップＳ３１〜ステップＳ３５の１回目のループでは、図１０（Ｂ）に示すように、ノードＮ２が確定ノードとされるとともに、ノードＮ３およびノードＮ４のコスト値が算出された状態となる。２回目のループでは、ステップＳ３１においてノードＮ４が最小のコスト値（＝１８０００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ４が確定ノードに設定される。そしてステップＳ３３では、ノードＮ４に接続される未確定ノードであるノードＮ５のコスト値が計算される。ここで、ノードＮ４はレーンデータを有しないことから、ノードＮ５のコスト値としては、レーンデータが存在しない場合の追加コスト「８０００」と、リンクＬ５のコスト「１００００」と、ノードＮ４のコスト値「１８０００」を加算して得られた値「３６０００」がノードＮ５のコスト値として算出される。ステップＳ３４では、その時点でのノードＮ５のコスト値は「∞」であることから、新たに計算されたコスト値の「３６０００」がノードＮ５のコスト値として設定される（図１０（Ｃ）参照）。
【００３１】
３回目のループでは、ステップＳ３１において、ノードＮ３が最小値（＝２０５００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ３が確定ノードに設定される（図１１（Ａ）参照）。ステップＳ３３では、ノードＮ３に接続するノードＮ５のコスト値が計算される。ここで、ノードＮ３は、図５に示すレーンデータを有する。図５に示すように、リンクＬ２からノードＮ３を経由してリンクＬ８へ通じるレーンは、第３および第４レーンの２種類である。図６に示すように、レーンが２つ以上存在する場合の追加コストは「０」であることから、ノードＮ５のコスト値としては、ノードＮ３のコスト値「２０５００」と、リンクＬ８のコストとを加算した「３０５００」が算出される。新たに算出されたコスト値「３０５００」は、既存のコスト値「３６０００」よりも小さいので、ステップＳ３４ではノードＮ５のコスト値は「３０５００」に更新される（図１１（Ｂ）参照）。
【００３２】
４回目のループでは、ステップＳ３１において、ノードＮ５が最小値（＝３０５００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ５が確定ノードに設定される。ステップＳ３３では、ノードＮ５に接続するノードＮ６のコスト値が計算される。ここで、ノードＮ５はレーンデータを有しないので、ノードＮ６のコスト値としては、ノードＮ５のコスト値「３０５００」と、レーンデータが存在しない場合の追加コスト「８０００」と、リンクＬ６のコスト「１００００」とを加算した「４８５００」が算出される。ノードＮ６の既存のコスト値は「∞」であるので、ステップＳ３４ではノードＮ６のコスト値が「４８５００」に更新される。５回目のループでは、ノードＮ６が確定ノードに設定されるとともに（図１１（Ｃ）参照）、ノードＮ６はゴールノードであることから接続されるノードが存在しないとして、コスト値の更新は行われない。このため、ステップＳ３５ではＮｏと判定され、ステップＳ３６に進む。ステップＳ３６では、最小のコストを有するリンクＬ２〜リンクＬ８〜リンクＬ６が最小コストの経路として選択される。
【００３３】
つぎに、図９を参照して、図８に示すステップＳ３３の処理の詳細について説明する。図９のフローチャートの処理が開始されると、ステップＳ５０において、ＣＰＵ１１は、対象となる確定ノードのレーンデータをＨＤＤ１４から検索する。ステップＳ５１では、ステップＳ５０の検索により、レーンデータが存在するか否かを判定し、存在すると判定した場合（ステップＳ５１；Ｙｅｓ）にはステップＳ５３に進み、それ以外の場合（ステップＳ５１；Ｎｏ）にはステップＳ５２に進む。例えば、対象となる確定ノードがノードＮ２である場合には、レーンデータが存在しないのでステップＳ５２に進み、対象となる確定ノードがノードＮ３である場合には、レーンデータが存在するのでステップＳ５３に進む。
【００３４】
ステップＳ５２では、ＣＰＵ１１は、リンクの基本コストに追加コストを加算して、リンクのコストを算出する。例えば、対象となる確定ノードがノードＮ２である場合には、レーンデータが存在しない場合の追加コスト「８０００」が、リンクＬ２の基本コスト「１２５００」およびリンクＬ７の基本コスト「１００００」にそれぞれ加算されて、これらのリンクのコストとして「２０５００」および「１８０００」がそれぞれ計算される。そして、ステップＳ６０に進み、ノードＮ３およびノードＮ４のコストが算出される。具体的には、対象となる確定ノードがノードＮ２である場合には、ノードＮ２のコスト値「０」に、ステップＳ５２で算出したリンクＬ２のコスト「２０５００」およびリンクＬ７のコスト「１８０００」が加算され、ノードＮ３のコスト値として「２０５００」が、また、ノードＮ４のコスト値として「１８０００」がそれぞれ算出される。
【００３５】
ステップＳ５３では、ＣＰＵ１１は、該当するレーンデータをＨＤＤ１４から取得する。例えば、対象となる確定ノードがノードＮ３である場合には、図５に示すようなレーンデータが取得される。
【００３６】
ステップＳ５４では、ＣＰＵ１１は、対象となる確定ノードに接続される未確定ノードを１つ特定する。例えば、対象となる確定ノードがノードＮ３である場合には、これに接続される未確定ノードはノードＮ５だけであるので、ノードＮ５が特定される。ステップＳ５５では、ＣＰＵ１１は、リンクデータを参照し、ステップＳ５４で特定した未確定ノードに対応する進入リンクと脱出リンクが存在するか否かを判定し、存在する場合（ステップＳ５５；Ｙｅｓ）にはステップＳ５６に進み、それ以外の場合（ステップＳ５５；Ｎｏ）にはステップＳ５７に進む。ここで、進入リンクとは当該ノードに進入するリンクであり、脱出リンクとは当該ノードから脱出するリンクである。例えば、ステップＳ５４において、ノードＮ５が特定された場合、図５に示すように、リンクＬ２からノードＮ３を経由してリンクＬ８に進むレーンは存在することからステップＳ５６に進む。なお、該当するレーンが存在しない場合には、ステップＳ５７に進み、ステップＳ５２の場合と同様に、リンクのコストにレーンが存在しない場合と同様の追加コスト「８０００」が基本コストに加算され、ステップＳ５９に進む。
【００３７】
ステップＳ５６では、ＣＰＵ１１は、該当するレーンの数を特定する。ノードＮ５の場合では、リンクＬ２からノードＮ３を経由してリンクＬ８に進むレーンは第３および第４レーンの２つ存在することから、レーン数として「２」が特定される。ステップＳ５８では、リンクのコストにレーン数に応じた追加コストが基本コストに加算されてリンクのコストが算出される。例えば、ノードＮ５の場合では、レーン数は「２」であり、図５に示すようにレーン数が２以上の場合の追加コストは「０」であることから、リンクＬ８のコストは基本コスト「１００００」に追加コスト「０」を加算した「１００００」とされる。なお、レーン数が「１」である場合には、図５に示すように追加コストとして「４０００」が基本コストに加算される。
【００３８】
ステップＳ５９では、確定ノードに接続される未確定ノードがまだ存在するか否かを判定し、存在すると判定した場合（ステップＳ５９；Ｙｅｓ）にはステップＳ５４に戻って前述の場合と同様の処理を繰り返し、それ以外の場合（ステップＳ５９；Ｎｏ）にはステップＳ６０に進む。例えば、対象となる確定ノードがノードＮ３である場合には、これに接続される未確定のノードはノードＮ５だけであるので、ステップＳ６０に進む。
【００３９】
ステップＳ６０では、ＣＰＵ１１は、以上の処理によって求めたリンクのコストに基づいて、未確定ノードのコストを計算する。例えば、確定ノードがノードＮ２である場合には、ステップＳ５２において求めた、リンクＬ２およびリンクＬ７のコスト「１８０００」および「２０５００」と、ノードＮ２のコスト値である「０」とを加算して得られた値「１８０００」および「２０５００」がノードＮ４およびノードＮ３のコスト値とされる。そして、元の処理に復帰（リターン）する。
【００４０】
以上に説明したように、本発明の実施形態によれば、レーンデータを考慮してコスト計算を行うようにしたので、進入リンクから脱出リンクに通じるレーンの有無に応じて経路が選択されるため、実際の道路状況に応じた最適な経路を選択することができる。
【００４１】
また、本実施形態によれば、該当するレーンの本数が多いほど、追加コストが小さくなるように設定したので、レーンの本数が多い経路が選択される可能性が高くなる。これによって、通行に時間を要しないで、通行が容易な経路が選択される可能性が高くなることから、運転者の負担を軽減することが可能となる。
【００４２】
（Ｄ）変形実施形態の説明
以上の説明においては、レーンとしては、直進、左折、および、右折等の専用のレーンを想定するようにしたが、例えば、直進または左折が可能な「直進／左折レーン」、または、直進または右折が可能な「直進／右折レーン」を設け、これらのレーンについてもコスト計算の対象としてもよい。
【００４３】
また、以上の実施形態では、レーンの種類は考慮せずに追加コストを計算するようにしたが、例えば、右折レーン＞左折レーン＞直進レーンの大小関係を有するように追加コストを設定し、このようにして設定されたコスト値に基づいてコスト計算を行うようにしてもよい。さらに、前述した直進／左折レーンおよび直進／右折レーンも考慮し、例えば、直進／右折レーン＞右折レーン＞直進／左折レーン＞左折レーン＞直進レーンの大小関係を有するように追加コストを設定するようにしてもよい。
【００４４】
また、追加コストを固定値とするのではなく、例えば、学習によって追加コストの値を調整するようにしてもよい。具体的には、例えば、各種レーンの走行に要した時間等を考慮して、追加コストの値を調整するようにすることができる。
【００４５】
また、図６に示すように、全体として１つの追加コストを用いるのではなく、ノード毎に追加コストの値を設定しておき、当該追加コスト値を参照して、コスト計算を行うようにしてもよい。具体的には、同じ右折レーンであっても、例えば、信号機の右折を示す矢印の表示時間の長短によって走行に要する時間が変化したり、あるいは、交通量の多少によって走行に要する時間が変化したりするためである。なお、このように、ノード毎に追加コストを設定する方法としては、信号機の矢印信号の表示時間や交通量等を示すデータから計算によって求めたり、あるいは、他の車両が通行するの要した時間を、例えば、車車間通信等によって取得し、当該時間に基づいて求めたりしてもよい。
【００４６】
また、以上の実施形態では、交通状況については考慮しないようにしたが、例えば、ＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）（登録商標）からの情報を参照して、コスト計算を行うようにしてもよいことは言うまでもない。
【図面の簡単な説明】
【００４７】
【図１】本実施の形態に係る車載型ナビゲーション装置の構成を示すブロック図である。
【図２】ノードデータの一例を示す図である。
【図３】レーンデータの一例を示す図である。
【図４】処理対象となる道路の一例を示す図である。
【図５】レーンデータの一例を示す図である。
【図６】追加コストの一例を示す図である。
【図７】現在地から目的地までの経路探索処理の一例を示すフローチャートである。
【図８】ノードのコスト計算の処理の一例を示すフローチャートである。
【図９】図８のステップＳ３３の処理の詳細を説明するフローチャートである。
【図１０】図８，９の処理の詳細を説明するための図である。
【図１１】図８，９の処理の詳細を説明するための図である。
【符号の説明】
【００４８】
１０ 車載型ナビゲーション装置
１１ ＣＰＵ
１２ ＲＯＭ
１３ ＲＡＭ
１４ ＨＤＤ
１５ ＧＰＳレシーバ
１６ ジャイロセンサ
１７ 車速パルスセンサ
１８ バック信号センサ
１９ リモコン受信部
２０ タッチパネル式液晶ディスプレイ
２１ ＡＳＩＣ
２２ バス
【技術分野】
【０００１】
本発明は、車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法に関する。
【背景技術】
【０００２】
特許文献１には、道路の通りやすさの指標である車線数を考慮して、経路探索を行う車載型ナビゲーション装置に関する技術が開示されている。また、車線数に加えて、交差点での進行方向に応じた追加コストを付与（例えば、直進よりも左折に対して、左折よりも右折に対して大きな追加コストを付与）することで、できるだけ右左折の回数が少ない経路をユーザに呈示することも行われている。
【特許文献１】特開２００２−６２１５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、例えば、同じ道路から右折する場合でもどの交差点で右折するかによって実際の所要時間（右折待ち時間）が異なるケースがしばしば存在するが、上述した技術では、このようなケースを考慮することは困難である。また、大半の車両が右左折し、直進する車両は僅少であるため、レーン設定等の運用により、右左折はしやすく、直進はしづらい交通制御がなされる場合も存在するが、上述した技術ではこのような交通制御に対しては対応することができない。
【０００４】
そこで、本発明の目的は、レーンを考慮して短時間で目的地に到着できる経路を探索することが可能な車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法を提供することにある。
【課題を解決するための手段】
【０００５】
上述課題を解決するため、本発明は、記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置において、自車位置を特定する特定手段と、目的地の入力を受け付ける受付手段と、前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索手段を有し、前記探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、ことを特徴とする。
この構成によれば、レーンを考慮して短時間で目的地に到着できるとともに、他の車両の走行も阻害しない車載型ナビゲーション装置を提供することができる。
【０００６】
他の発明は、上記発明に加えて、進入リンクから脱出リンクへ通じるレーンの数が多い場合には、当該脱出リンクに対するコストを低く計算し、レーンの数が少ない場合には、当該脱出リンクに対するコストを高く計算することを特徴とする。
これにより、レーンが複数存在する脱出リンクが存在する場合には、当該脱出リンクのコストを低く計算することにより、より通行しやすいリンクが選択される可能性を高くすることができる。
【０００７】
また、本発明は、記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置の制御方法において、自車位置を特定する特定ステップと、目的地の入力を受け付ける受付ステップと、前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索ステップを有し、前記探索ステップは、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、ことを特徴とする。
この方法によれば、レーンを考慮して短時間で目的地に到着できるとともに、他の車両の走行も阻害しない車載型ナビゲーション装置の制御方法を提供することができる。
【発明の効果】
【０００８】
本発明によれば、レーンを考慮して短時間で目的地に到着できる経路を探索することが可能な車載型ナビゲーション装置および車載型ナビゲーション装置の制御方法を提供することができる。
【発明を実施するための最良の形態】
【０００９】
（Ａ）発明の実施形態の説明
つぎに図面を参照して本発明の好適な実施の形態について説明する。図１は、本発明の実施形態である車載型ナビゲーション装置１０の構成例を示す図である。この図１に示すように、車載型ナビゲーション装置１０は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１１、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１２、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１３、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）１４、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）レシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、バック信号センサ１８、リモコン受信部１９、タッチパネル式液晶ディスプレイ２０、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｅｄ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）２１、バス２２、および、リモコン（リモートコントローラ）２５を有している。
【００１０】
ここで、ＣＰＵ１１は、ＲＯＭ１２またはＨＤＤ１４に記憶されているプログラムに基づいて装置の各部を制御する中央制御装置である。ＲＯＭ１２は、ＣＰＵ１１が実行する基本的なプログラムやデータを格納している半導体記憶装置である。ＲＡＭ１３は、ＣＰＵ１１がプログラムを実行する際にワーキングエリアとして機能する半導体記憶装置である。ＨＤＤ１４は、基本的なプログラムとしてのオペレーティングシステムや、後述する経路探索や経路案内を実行するためのアプリケーションプログラムや、経路探索や経路案内を実行するために必要なデータ（地図情報等）を有している。ＧＰＳレシーバ１５は、複数のＧＰＳ衛星から送信される信号を受信し、これらの信号に含まれているタイムスタンプに基づいて、自己の位置を示す情報（緯度、経度、高度等）を生成して出力する。ジャイロセンサ１６は、例えば、車両の３軸（ヨー軸、ロール軸、ピッチ軸）方向の加速度を検出して出力する。車速パルスセンサ１７は、車両の走行速度を示す車速パルスを検出して出力する。バック信号センサ１８は、車両がバックしていることを示すバック信号を検出して出力する。リモコン受信部１９は、リモコン２５から送信された赤外線信号を受信し、ユーザの操作に応じた情報を出力する。タッチパネル式液晶ディスプレイ２０は、表示装置としての液晶ディスプレイに、入力装置としてのタッチパネルが重畳するように配置されて構成されている。ユーザは、液晶ディスプレイに表示された情報を参照しながら、タッチパネルを操作することにより、装置に対して指示を行うことができる。ＡＳＩＣ２１は、ＧＰＳレシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、バック信号センサ１８、および、リモコン受信部１９から出力される信号を入力し、車載型ナビゲーション装置１０に適合する形式にデータを変換して出力する。
【００１１】
図２および図３は、ＨＤＤ１４に格納されているノード情報およびリンク情報の一例を示す図である。なお、本実施形態では、道路情報は、道路の分岐点（例えば、交差点）を示すノードと、ノード同士を接続するリンクとによって構成される。図２は、ノードが格納されたノードテーブルの一例を示している。図２の例では、図の左側に示すように、ｎ個のノードに関する情報が格納されており、図の右側に拡大して示すように、ノード＃０に関する情報は、リンク情報とレーン情報とから構成される。リンク情報としては、この例では、ノード＃０に接続されているリンクの数（この例ではｍ個）と、それぞれのリンクに関する情報とが格納されている。レーン情報としては、この例では、ノード＃０が有するレーン情報の定義数（この例ではｐ個）と、それぞれのレーンに関する情報とが記憶されている。なお、「レーン」とは、交差点等の分岐点に設けられた車線を示し、例えば、右折する車両が通行する右折レーン、左折する車両が通行する左折レーン、直進する車両が通行する直進レーン等が存在する。なお、直進する車両と左折する車両が通行する直進／左折レーン、および、直進する車両と右折する車両が通行する直進／右折レーンを含めてもよい。
【００１２】
図３は、図２に示すレーン情報（レーンデータ）の一例を示す図である。図３の例では、レーンデータは、当該ノードに進入するリンクを特定するための進入リンク番号と、当該リンクのレーン数と、進入リンクに接続される脱出リンク（経路）の定義数（この例ではｒ個）と、各経路に脱出する脱出リンクと、それぞれの脱出リンクに適用されるレーンの種類を示す情報を有している。例えば、図４に示すようなリンクおよびノードが存在する場合において、ノードＮ３のレーンデータとしては、例えば、図５に示す情報が格納されている。すなわち、図５の例は、ノードＮ３に進入リンクＬ２から進入する場合に対応する情報であり、この例では、「レーン数」は「４」であることからレーンが４つ存在することが示され、脱出リンクとしては「Ｌ３」および「Ｌ８」の２種類が存在することから、「経路数」は「２」とされている。また、「経路＃０脱出先リンク」としての「Ｌ３」の適用レーン（リンクＬ３に脱出可能なレーン）は「第１レーン」および「第２レーン」であり、「経路＃１脱出先リンク」としての「Ｌ８」の適用レーン（リンクＬ８に脱出可能なレーン）は「第３レーン」および「第４レーン」であることが示されている。つまり、リンクＬ２からノードＮ３へ進入する場合、リンクＬ３へ通ずるレーンは第１および第２の２レーンであり、リンクＬ８へ通ずるレーンは第３および第４の２レーンであり、合計４つのレーンが存在している。
【００１３】
（Ｂ）発明の概略動作の説明
つぎに、図４〜図６を参照して、本実施形態の概略動作について説明する。図４についてさらに詳細に説明すると、丸印はノードを示し、ノード同士を結ぶ線分はリンクを示している。この例では、ノードＮ１〜Ｎ６と、リンクＬ１〜Ｌ６とが存在している。ここで、リンクＬ１〜Ｌ６は全て同一種類（例えば、国道）であり、リンクＬ１およびリンクＬ３〜Ｌ６は全て２００ｍの長さを有し、リンクＬ２は２５０ｍの長さを有している。また、リンクＬ１およびリンクＬ３〜Ｌ６の基本コスト（リンク自体のコスト）値は全て１００００であり、リンクＬ２の基本コスト値は１２５００である。また、ノードＮ３には、図５に示すようなレーンデータが設定されており、その他のノードＮ１，Ｎ２およびノードＮ４〜Ｎ６には、レーンデータは設定されていないとする。また、図６は、レーンデータに応じてコスト計算に適用される追加コストの一例を示す図である。この図６では、該当するレーンが存在しない場合の追加コストは「８０００」であり、該当するレーンが１レーン存在する場合の追加コストは「４０００」であり、該当するレーンが２レーン以上存在する場合の追加コストは「０」とされている。
【００１４】
以上のような場合において、リンクＬ１からリンクＬ６（ノードＮ２からノードＮ６）への最適経路を求める場合の本実施形態の概略動作について説明する。
【００１５】
まず、リンクＬ１にノードＮ２を介して接続されるリンクは、リンクＬ２とリンクＬ７の２本である。ノードＮ２にはレーンデータが存在しないので、リンクＬ２のコスト値は基本値である１２５００に対して、図６の「該当レーン無し」に対応する追加コスト値「８０００」が加算された「２０５００」となる。また、リンクＬ７のコスト値は基本値である１００００に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１６】
リンクＬ７からリンクＬ５への経路では、ノードＮ４にはレーンデータが存在しないことから、リンクＬ５のコスト値は、基本値である「１００００」に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１７】
リンクＬ２からリンクＬ８への経路では、図５に示すように、ノードＮ３にはレーンデータが存在し、かつ、該当する適用レーンが２レーン存在する（第３レーンおよび第４レーンが存在する）ので、リンクＬ８のコスト値は、基本値である「１００００」に対して、「該当レーン有り（２レーン以上）」に対応する追加コスト値「０」が加算された「１００００」となる。
【００１８】
リンクＬ８からリンクＬ６への経路およびリンクＬ５からリンクＬ６への経路では、ノードＮ５にはレーンデータが存在しないことから、リンクＬ６のコスト値は、基本値である「１００００」に対して、「該当レーン無し」に対応する追加コスト値「８０００」が加算された「１８０００」となる。
【００１９】
以上のコスト計算の結果、リンクＬ２〜リンクＬ８〜リンクＬ６と経由する場合のトータルのコストは２０５００＋１００００＋１８０００＝４８５００となり、また、リンクＬ７〜リンクＬ５〜リンクＬ６と経由する場合のトータルのコストは１８０００＋１８０００＋１８０００＝５４０００となる。このため、走行距離は長いにも拘わらず、右折レーンが整備されて走行しやすいと考えられるリンクＬ２〜リンクＬ８〜リンクＬ６が経路として選択される。
【００２０】
（Ｃ）発明の詳細な動作の説明
つぎに、図７〜図９のフローチャートを参照して、本発明において実行される処理の詳細について説明する。図７は、車両の現在位置から目的値までの経路を探索する処理の概要を説明するための図である。例えば、ユーザがタッチパネル式液晶ディスプレイ２０を操作することにより、経路探索の要求を行ったとすると、ステップＳ１０において、ＣＰＵ１１は、ＧＰＳレシーバ１５、ジャイロセンサ１６、車速パルスセンサ１７、および、バック信号センサ１８から得られた情報に基づいて、自車の現在位置を算出するとともに、タッチパネル式液晶ディスプレイ２０から入力された情報（例えば、目的地の住所、名称、電話番号、緯度・経度情報）に基づいて目的地を求める。
【００２１】
つぎに、ステップＳ１１では、ＣＰＵ１１は、車両の現在位置と目的地の間に存在する道路データをＨＤＤ１４から読み出し、ＲＡＭ１３に格納する。つづいて、ステップＳ１２では、ＣＰＵ１１は、ステップＳ１１において読み込んだ道路データから、車両位置に最も近い道路および目的地に最も近い道路を抽出する。そして、ステップＳ１３において、ＣＰＵ１１は、ステップＳ１２で抽出した道路を、甲種経路としてＲＡＭ１３に記憶する。
【００２２】
ステップＳ１４では、ＣＰＵ１１は、甲種経路候補のうち、最も有力と判断できる道路を選択し、乙種経路候補として記憶する。ステップＳ１５では、ＣＰＵ１１は、ステップＳ１４において選択された道路に接続し、通行可能な道路を全て求める。そしてステップＳ１６では、ＣＰＵ１１は、ステップＳ１５で求めた道路の各々について、コストを計算する。なお、この処理の詳細については、図８および図９を参照して後述する。
【００２３】
ステップＳ１７では、ＣＰＵ１１は、ステップＳ１６で求めた全ての道路を、甲種経路候補として記憶する。ステップＳ１８では、ＣＰＵ１１は、車両位置から連続した乙種経路候補と目的地から連続した乙種経路候補とが適切に接続したか否かを判定し、接続したと判定した場合（ステップＳ１８；Ｙｅｓ）にはステップＳ１９に進み、それ以外の場合（ステップＳ１８；Ｎｏ）にはステップＳ１４に戻って前述の場合と同様の処理を繰り返す。
【００２４】
ステップＳ１９では、ＣＰＵ１１は、接続した一連の乙種経路候補群を経路として確定し、これ以降、当該確定された経路に基づいて、経路表示を行うとともに、ユーザへの案内を行う。
【００２５】
つぎに、図８および図９を参照して、経路のコスト計算処理の詳細について説明する。ここで、図８は、自車位置の近傍に存在するスタートノードから、目的地の近傍に存在するゴールノードまでの間の各ノードのコストを計算する処理を説明するフローチャートであり、図９は図８に示すステップＳ５５の処理の詳細を説明するフローチャートである。なお、図８の処理は、いわゆる「ダイクストラ法」に基づいて各ノードのコスト値を計算する。この図８に示すフローチャートの処理が実行されると、ステップＳ３０において、ＣＰＵ１１は、車両位置の近傍に存在するスタートノードのコスト値を「０」に設定するとともに、他のノードのコスト値を「∞」に設定する。図４の例では、現在、リンクＬ１を走行中であるとすると、スタートノードとしてのノードＮ２のコストが「０」に設定されるとともに、スタートノードからゴールノード（ノードＮ６）までの間のノードＮ３〜Ｎ６のコスト値が「∞」に設定される。図１０（Ａ）は、ステップＳ３０の処理の結果を示す図である。この図では、ノードＮ２のコスト値は「０」とされ、それ以外のノードのコスト値は「∞」とされている。
【００２６】
ステップＳ３１では、ＣＰＵ１１は、未確定ノードの中から、最小のコスト値を有するノードを特定する。ここで、「未確定ノード」とは、ノードのコスト値が確定していないノードをいい、後述する「確定ノード」とは、ノードのコスト値が確定したノードをいう。図４の例では、未確定ノードの中で最小のコスト値を有するのは、ノードＮ２であるので（他のノードのコスト値は無限大であるので）、ノードＮ２のコストが最小値のノードとして特定される。ステップＳ３２では、ＣＰＵ１１は、ステップＳ３１において特定したノードを確定ノードに設定する。なお、図１０において、確定ノードにはハッチングが施されており、未確定ノードにはハッチングが施されていない。
【００２７】
ステップＳ３３では、ＣＰＵ１１は、ステップＳ３２で設定した確定ノードに接続する未確定ノードのコストを計算する。いまの例では、ステップＳ３２において、ノードＮ２が確定ノードに設定されているので、ノードＮ２に接続される未確定ノードとしてのノードＮ３およびノードＮ４のコストが計算される。なお、この処理の詳細は、図９を参照して後述するが、簡単に説明すると、確定ノードがレーンデータを有している場合には、レーンデータと、リンクのコスト値に基づいて、対象となるノードのコスト値が計算され、レーンデータを有しない場合には、レーンデータが存在しない場合の追加コストと、リンクのコスト値に基づいて、対象となるノードのコスト値が算定される。図１０の例では、ノードＮ２は、レーンデータを有しないことから、レーンデータを有しない場合の追加コストとしての「８０００」が、リンクＬ２のコスト値「１２５００」と、リンクＬ７のコスト値「１００００」とにそれぞれ加算され、得られた値「２０５００」と「１８０００」とがノードＮ３およびノードＮ４のそれぞれのコスト値として算出される。
【００２８】
ステップＳ３４では、ＣＰＵ１１は、ステップＳ３３において算出したノードのコスト値が、現在設定されているコスト値よりも小さい場合には、新たに算出した値によって更新する。図１０の例では、ノードＮ３およびノードＮ４に現在設定されているコスト値はともに「∞」であり、ステップＳ３３において算出されたコスト値は「２０５００」および「１８０００」であるので、更新がなされて、「２０５００」および「１８０００」がノードＮ３およびノードＮ４のそれぞれのコスト値として設定される（図１０（Ｂ）参照）。
【００２９】
ステップＳ３５では、ＣＰＵ１１は、未確定ノードが存在するか否かが判定され、未確定ノードが存在すると判定した場合（ステップＳ３５；Ｙｅｓ）にはステップＳ３１に戻って同様の処理を繰り返し、それ以外の場合（ステップＳ３５；Ｎｏ）にはステップＳ３６に進む。図１０の例では、その時点では、図１０（Ｂ）に示すように、ノードＮ２のみが確定ノードの状態であるので、ステップＳ３１に戻って前述の場合と同様の処理を繰り返す。
【００３０】
ステップＳ３１〜ステップＳ３５の処理が繰り返されることにより、図１０および図１１に示すように、各ノードのコスト値が計算されて確定されていく。詳細に説明すると、ステップＳ３１〜ステップＳ３５の１回目のループでは、図１０（Ｂ）に示すように、ノードＮ２が確定ノードとされるとともに、ノードＮ３およびノードＮ４のコスト値が算出された状態となる。２回目のループでは、ステップＳ３１においてノードＮ４が最小のコスト値（＝１８０００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ４が確定ノードに設定される。そしてステップＳ３３では、ノードＮ４に接続される未確定ノードであるノードＮ５のコスト値が計算される。ここで、ノードＮ４はレーンデータを有しないことから、ノードＮ５のコスト値としては、レーンデータが存在しない場合の追加コスト「８０００」と、リンクＬ５のコスト「１００００」と、ノードＮ４のコスト値「１８０００」を加算して得られた値「３６０００」がノードＮ５のコスト値として算出される。ステップＳ３４では、その時点でのノードＮ５のコスト値は「∞」であることから、新たに計算されたコスト値の「３６０００」がノードＮ５のコスト値として設定される（図１０（Ｃ）参照）。
【００３１】
３回目のループでは、ステップＳ３１において、ノードＮ３が最小値（＝２０５００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ３が確定ノードに設定される（図１１（Ａ）参照）。ステップＳ３３では、ノードＮ３に接続するノードＮ５のコスト値が計算される。ここで、ノードＮ３は、図５に示すレーンデータを有する。図５に示すように、リンクＬ２からノードＮ３を経由してリンクＬ８へ通じるレーンは、第３および第４レーンの２種類である。図６に示すように、レーンが２つ以上存在する場合の追加コストは「０」であることから、ノードＮ５のコスト値としては、ノードＮ３のコスト値「２０５００」と、リンクＬ８のコストとを加算した「３０５００」が算出される。新たに算出されたコスト値「３０５００」は、既存のコスト値「３６０００」よりも小さいので、ステップＳ３４ではノードＮ５のコスト値は「３０５００」に更新される（図１１（Ｂ）参照）。
【００３２】
４回目のループでは、ステップＳ３１において、ノードＮ５が最小値（＝３０５００）の未確定ノードとして特定され、ステップＳ３２においてノードＮ５が確定ノードに設定される。ステップＳ３３では、ノードＮ５に接続するノードＮ６のコスト値が計算される。ここで、ノードＮ５はレーンデータを有しないので、ノードＮ６のコスト値としては、ノードＮ５のコスト値「３０５００」と、レーンデータが存在しない場合の追加コスト「８０００」と、リンクＬ６のコスト「１００００」とを加算した「４８５００」が算出される。ノードＮ６の既存のコスト値は「∞」であるので、ステップＳ３４ではノードＮ６のコスト値が「４８５００」に更新される。５回目のループでは、ノードＮ６が確定ノードに設定されるとともに（図１１（Ｃ）参照）、ノードＮ６はゴールノードであることから接続されるノードが存在しないとして、コスト値の更新は行われない。このため、ステップＳ３５ではＮｏと判定され、ステップＳ３６に進む。ステップＳ３６では、最小のコストを有するリンクＬ２〜リンクＬ８〜リンクＬ６が最小コストの経路として選択される。
【００３３】
つぎに、図９を参照して、図８に示すステップＳ３３の処理の詳細について説明する。図９のフローチャートの処理が開始されると、ステップＳ５０において、ＣＰＵ１１は、対象となる確定ノードのレーンデータをＨＤＤ１４から検索する。ステップＳ５１では、ステップＳ５０の検索により、レーンデータが存在するか否かを判定し、存在すると判定した場合（ステップＳ５１；Ｙｅｓ）にはステップＳ５３に進み、それ以外の場合（ステップＳ５１；Ｎｏ）にはステップＳ５２に進む。例えば、対象となる確定ノードがノードＮ２である場合には、レーンデータが存在しないのでステップＳ５２に進み、対象となる確定ノードがノードＮ３である場合には、レーンデータが存在するのでステップＳ５３に進む。
【００３４】
ステップＳ５２では、ＣＰＵ１１は、リンクの基本コストに追加コストを加算して、リンクのコストを算出する。例えば、対象となる確定ノードがノードＮ２である場合には、レーンデータが存在しない場合の追加コスト「８０００」が、リンクＬ２の基本コスト「１２５００」およびリンクＬ７の基本コスト「１００００」にそれぞれ加算されて、これらのリンクのコストとして「２０５００」および「１８０００」がそれぞれ計算される。そして、ステップＳ６０に進み、ノードＮ３およびノードＮ４のコストが算出される。具体的には、対象となる確定ノードがノードＮ２である場合には、ノードＮ２のコスト値「０」に、ステップＳ５２で算出したリンクＬ２のコスト「２０５００」およびリンクＬ７のコスト「１８０００」が加算され、ノードＮ３のコスト値として「２０５００」が、また、ノードＮ４のコスト値として「１８０００」がそれぞれ算出される。
【００３５】
ステップＳ５３では、ＣＰＵ１１は、該当するレーンデータをＨＤＤ１４から取得する。例えば、対象となる確定ノードがノードＮ３である場合には、図５に示すようなレーンデータが取得される。
【００３６】
ステップＳ５４では、ＣＰＵ１１は、対象となる確定ノードに接続される未確定ノードを１つ特定する。例えば、対象となる確定ノードがノードＮ３である場合には、これに接続される未確定ノードはノードＮ５だけであるので、ノードＮ５が特定される。ステップＳ５５では、ＣＰＵ１１は、リンクデータを参照し、ステップＳ５４で特定した未確定ノードに対応する進入リンクと脱出リンクが存在するか否かを判定し、存在する場合（ステップＳ５５；Ｙｅｓ）にはステップＳ５６に進み、それ以外の場合（ステップＳ５５；Ｎｏ）にはステップＳ５７に進む。ここで、進入リンクとは当該ノードに進入するリンクであり、脱出リンクとは当該ノードから脱出するリンクである。例えば、ステップＳ５４において、ノードＮ５が特定された場合、図５に示すように、リンクＬ２からノードＮ３を経由してリンクＬ８に進むレーンは存在することからステップＳ５６に進む。なお、該当するレーンが存在しない場合には、ステップＳ５７に進み、ステップＳ５２の場合と同様に、リンクのコストにレーンが存在しない場合と同様の追加コスト「８０００」が基本コストに加算され、ステップＳ５９に進む。
【００３７】
ステップＳ５６では、ＣＰＵ１１は、該当するレーンの数を特定する。ノードＮ５の場合では、リンクＬ２からノードＮ３を経由してリンクＬ８に進むレーンは第３および第４レーンの２つ存在することから、レーン数として「２」が特定される。ステップＳ５８では、リンクのコストにレーン数に応じた追加コストが基本コストに加算されてリンクのコストが算出される。例えば、ノードＮ５の場合では、レーン数は「２」であり、図５に示すようにレーン数が２以上の場合の追加コストは「０」であることから、リンクＬ８のコストは基本コスト「１００００」に追加コスト「０」を加算した「１００００」とされる。なお、レーン数が「１」である場合には、図５に示すように追加コストとして「４０００」が基本コストに加算される。
【００３８】
ステップＳ５９では、確定ノードに接続される未確定ノードがまだ存在するか否かを判定し、存在すると判定した場合（ステップＳ５９；Ｙｅｓ）にはステップＳ５４に戻って前述の場合と同様の処理を繰り返し、それ以外の場合（ステップＳ５９；Ｎｏ）にはステップＳ６０に進む。例えば、対象となる確定ノードがノードＮ３である場合には、これに接続される未確定のノードはノードＮ５だけであるので、ステップＳ６０に進む。
【００３９】
ステップＳ６０では、ＣＰＵ１１は、以上の処理によって求めたリンクのコストに基づいて、未確定ノードのコストを計算する。例えば、確定ノードがノードＮ２である場合には、ステップＳ５２において求めた、リンクＬ２およびリンクＬ７のコスト「１８０００」および「２０５００」と、ノードＮ２のコスト値である「０」とを加算して得られた値「１８０００」および「２０５００」がノードＮ４およびノードＮ３のコスト値とされる。そして、元の処理に復帰（リターン）する。
【００４０】
以上に説明したように、本発明の実施形態によれば、レーンデータを考慮してコスト計算を行うようにしたので、進入リンクから脱出リンクに通じるレーンの有無に応じて経路が選択されるため、実際の道路状況に応じた最適な経路を選択することができる。
【００４１】
また、本実施形態によれば、該当するレーンの本数が多いほど、追加コストが小さくなるように設定したので、レーンの本数が多い経路が選択される可能性が高くなる。これによって、通行に時間を要しないで、通行が容易な経路が選択される可能性が高くなることから、運転者の負担を軽減することが可能となる。
【００４２】
（Ｄ）変形実施形態の説明
以上の説明においては、レーンとしては、直進、左折、および、右折等の専用のレーンを想定するようにしたが、例えば、直進または左折が可能な「直進／左折レーン」、または、直進または右折が可能な「直進／右折レーン」を設け、これらのレーンについてもコスト計算の対象としてもよい。
【００４３】
また、以上の実施形態では、レーンの種類は考慮せずに追加コストを計算するようにしたが、例えば、右折レーン＞左折レーン＞直進レーンの大小関係を有するように追加コストを設定し、このようにして設定されたコスト値に基づいてコスト計算を行うようにしてもよい。さらに、前述した直進／左折レーンおよび直進／右折レーンも考慮し、例えば、直進／右折レーン＞右折レーン＞直進／左折レーン＞左折レーン＞直進レーンの大小関係を有するように追加コストを設定するようにしてもよい。
【００４４】
また、追加コストを固定値とするのではなく、例えば、学習によって追加コストの値を調整するようにしてもよい。具体的には、例えば、各種レーンの走行に要した時間等を考慮して、追加コストの値を調整するようにすることができる。
【００４５】
また、図６に示すように、全体として１つの追加コストを用いるのではなく、ノード毎に追加コストの値を設定しておき、当該追加コスト値を参照して、コスト計算を行うようにしてもよい。具体的には、同じ右折レーンであっても、例えば、信号機の右折を示す矢印の表示時間の長短によって走行に要する時間が変化したり、あるいは、交通量の多少によって走行に要する時間が変化したりするためである。なお、このように、ノード毎に追加コストを設定する方法としては、信号機の矢印信号の表示時間や交通量等を示すデータから計算によって求めたり、あるいは、他の車両が通行するの要した時間を、例えば、車車間通信等によって取得し、当該時間に基づいて求めたりしてもよい。
【００４６】
また、以上の実施形態では、交通状況については考慮しないようにしたが、例えば、ＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）（登録商標）からの情報を参照して、コスト計算を行うようにしてもよいことは言うまでもない。
【図面の簡単な説明】
【００４７】
【図１】本実施の形態に係る車載型ナビゲーション装置の構成を示すブロック図である。
【図２】ノードデータの一例を示す図である。
【図３】レーンデータの一例を示す図である。
【図４】処理対象となる道路の一例を示す図である。
【図５】レーンデータの一例を示す図である。
【図６】追加コストの一例を示す図である。
【図７】現在地から目的地までの経路探索処理の一例を示すフローチャートである。
【図８】ノードのコスト計算の処理の一例を示すフローチャートである。
【図９】図８のステップＳ３３の処理の詳細を説明するフローチャートである。
【図１０】図８，９の処理の詳細を説明するための図である。
【図１１】図８，９の処理の詳細を説明するための図である。
【符号の説明】
【００４８】
１０ 車載型ナビゲーション装置
１１ ＣＰＵ
１２ ＲＯＭ
１３ ＲＡＭ
１４ ＨＤＤ
１５ ＧＰＳレシーバ
１６ ジャイロセンサ
１７ 車速パルスセンサ
１８ バック信号センサ
１９ リモコン受信部
２０ タッチパネル式液晶ディスプレイ
２１ ＡＳＩＣ
２２ バス
【特許請求の範囲】
【請求項１】
記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置において、
自車位置を特定する特定手段と、
目的地の入力を受け付ける受付手段と、
前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索手段を有し、
前記探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、
ことを特徴とする車載型ナビゲーション装置。
【請求項２】
請求項１記載の車載型ナビゲーション装置において、
進入リンクから脱出リンクへ通じるレーンの数が多い場合には、当該脱出リンクに対するコストを低く計算し、レーンの数が少ない場合には、当該脱出リンクに対するコストを高く計算する、
ことを特徴とする車載型ナビゲーション装置。
【請求項３】
記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置の制御方法において、
自車位置を特定する特定ステップと、
目的地の入力を受け付ける受付ステップと、
前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索ステップを有し、
前記探索ステップは、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、
ことを特徴とする車載型ナビゲーション装置の制御方法。
【請求項１】
記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置において、
自車位置を特定する特定手段と、
目的地の入力を受け付ける受付手段と、
前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索手段を有し、
前記探索手段は、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、
ことを特徴とする車載型ナビゲーション装置。
【請求項２】
請求項１記載の車載型ナビゲーション装置において、
進入リンクから脱出リンクへ通じるレーンの数が多い場合には、当該脱出リンクに対するコストを低く計算し、レーンの数が少ない場合には、当該脱出リンクに対するコストを高く計算する、
ことを特徴とする車載型ナビゲーション装置。
【請求項３】
記憶装置に記憶されたノードおよびリンクを有する道路情報を参照して経路案内を行う車載型ナビゲーション装置の制御方法において、
自車位置を特定する特定ステップと、
目的地の入力を受け付ける受付ステップと、
前記記憶装置に記憶された前記道路情報を参照し、前記自車位置から前記目的地までの経路を探索する探索ステップを有し、
前記探索ステップは、ノードに進入するリンクを進入リンクとし、ノードから脱出するリンクを脱出リンクとした場合に、進入リンクから脱出リンクへ通じるレーンの有無を考慮してコスト計算を実行する、
ことを特徴とする車載型ナビゲーション装置の制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１０−１１２９３２（Ｐ２０１０−１１２９３２Ａ）
【公開日】平成２２年５月２０日（２０１０．５．２０）
【国際特許分類】
【出願番号】特願２００８−２８７９８９（Ｐ２００８−２８７９８９）
【出願日】平成２０年１１月１０日（２００８．１１．１０）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２２年５月２０日（２０１０．５．２０）
【国際特許分類】
【出願日】平成２０年１１月１０日（２００８．１１．１０）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]