(57)【要約】【課題】右左折信号のある交差点を経路とするか否かを運転者が選択でき、運転者の技量に応じて右左折信号のある交差点を経路とすることができる経路案内装置、経路案内方法及び道路地図データを提供すること。【解決手段】交差点を通過する際のコストを格納したノードデータと、交差点間の道路を通過する際のコストを格納したリンクデータとに基づき目的地までの経路のコストが小さくなるように該経路を探索する経路案内装置１０であって、右折信号又は左折信号を付随する信号機のある前記交差点の右左折を優先的に経路として選択する経路探索手段４と、経路探索手段による経路探索をするか否かを選択する経路探索手法選択手段４と、探索された経路を表示する表示装置５と、を有することを特徴とする。【選択図】図１１
2007255919.tif 000002
【特許請求の範囲】
【請求項１】
交差点を通過する際のコストを格納したノードデータと、前記交差点間の道路を通過する際のコストを格納したリンクデータとに基づき目的地までの経路のコストが小さくなるように該経路を探索する経路案内装置であって、
右折信号又は左折信号を付随する信号機のある前記交差点の右左折を優先的に経路として選択する経路探索手段と、
前記経路探索手段による経路探索をするか否かを選択する経路探索手法選択手段と、
探索された経路を表示する表示装置と、
を有することを特徴とする経路案内装置。
【請求項２】
前記リンクデータには、右折信号又は左折信号を介して接続するリンクのリンク番号が設定されている、
ことを特徴とする請求項１記載の経路案内装置。
【請求項３】
交差点を通過する際のコストを格納したノードデータと、前記交差点間の道路を通過する際のコストを格納したリンクデータに基づき目的地までの経路のコストが小さくなるように該経路を探索する経路探索装置の経路案内方法であって、
右折信号又は左折信号を付随する信号機のある前記交差点を右左折する経路を探索するように入力されるステップと、
前記リンクデータから、右折信号又は左折信号を介して接続するリンクのリンク番号を抽出するステップと、
右折信号又は左折信号を介して接続する前記リンクから経路のコストが小さくなる経路を探索するステップと、
探索された経路を表示するステップと、
を有することを特徴とする経路案内方法。
【請求項４】
交差点を通過する際のコストを格納したノードデータと、前記交差点間の道路を通過する際のコストを格納したリンクデータとを有する道路地図データにおいて、
第１のリンクから第２のリンクに右折信号又は左折信号を介して接続する場合、前記第２のリンクのリンクデータに前記第１のリンクのリンク番号が設定されている、
ことを特徴とする道路地図データ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの経路を案内する経路案内装置、経路案内方法及び道路地図データに関する。
【背景技術】
【０００２】
車両には、自車両の位置を検出する位置検出装置及び道路地図が格納されたナビーゲーションシステムが搭載され、自車両周辺の道路地図や目的地が入力された場合には目的地までの経路を道路地図に表示して運転者を案内する。
【０００３】
自車両の位置と目的地とを結ぶ経路の探索方法は種々提案されているが、ダイクストラ法を用いた場合、設定された条件下で通過コストが小さくなる経路が探索される。このため、道路地図には、通過コストを算出するため、道路を通過する際のコストを示すリンクコスト及び交差点における右左折のコストを示すノードコストとが格納されている。そして、いくつかの経路候補について各道路区間の通過コストを算出し、適当な処理回数を経た後又は所定の条件を満たした場合に、通過コストが小さい経路候補を、最適経路として探索する。
【０００４】
したがって、道路のリンクコストや交差点のノードコストを調整すれば目的地は同じでも異なる経路を探索することができる。例えば、左側通行の日本では右折する場合に対向車の状況を確認する必要があるため、ノードコストに置ける右折コストを高く設定することで、右折の少ない経路を探索することが可能となる（例えば、特許文献１参照。）。
【０００５】
また、このような探索では本来右折すべき交差点において左折又は直進するように経路を探索する可能性が高まるため経路が長くなる虞がある。そこで、ノードコストにおいて、右折するために表示される矢印などの右折信号の有無に基づきノードコストを増減する探索方法が提案されている（例えば、特許文献２参照。）。このような探索方法であれば、右折する交差点でも右折信号がある交差点の右折が優先的に探索されることとなり、運転のしやすさと走行距離とを両立しやすくなる。
【特許文献１】特開２００４−３５４０８６号公報
【特許文献２】特開２００５−３２１３６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献２の探索方法では、右折コストを左折コストと同程度に低減するのみであり必ずしも右折信号のある交差点を右折する経路が探索されるとは限らない。  また、特許文献２に記載された探索方法には運転者のスキルについて考慮されていない。交差点の右折を含む経路の是非は運転者の運転スキルに依存するものであり、例えば、熟練した運転者であれば交差点の右折が多くても距離が短い経路を所望することが多いと考えられる。
【０００７】
本発明は、上記課題に鑑み、右左折信号のある交差点を経路とするか否かを運転者が選択でき、運転者の技量に応じて右左折信号のある交差点を経路とすることができる経路案内装置、経路案内方法及び道路地図データを提供すること目的とする。
【課題を解決するための手段】
【０００８】
上記課題に鑑み、本発明は、交差点を通過する際のコストを格納したノードデータと、交差点間の道路を通過する際のコストを格納したリンクデータとに基づき目的地までの経路のコストが小さくなるように該経路を探索する経路案内装置であって、右折信号又は左折信号を付随する信号機のある交差点の右左折を優先的に経路として選択する経路探索手段と、経路探索手段による経路探索をするか否かを選択する経路探索手法選択手段と、探索された経路を表示する表示装置と、を有することを特徴とする。
【０００９】
本発明によれば、右左折信号のある交差点を経路とするか否かを運転者が選択でき、運転者の技量に応じて右左折信号のある交差点を経路とすることができる。
【発明の効果】
【００１０】
右左折信号のある交差点を経路とするか否かを運転者が選択でき、運転者の技量に応じて右左折信号のある交差点を経路とすることができる経路案内装置を提供できる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明を実施するための最良の形態について図面を参照しながら説明する。図１は、経路案内装置１０のシステム構成図を示す。経路案内装置１０は、道路地図のデータを記憶する記録装置１、自車両の位置を検出する位置検出装置２、運転者や乗員の入力を受け付ける入力装置３、現在地から目的地までの経路を探索する経路探索装置４、及び、道路地図や自車両の位置、経路を表示する表示装置５を有するように構成される。
【００１２】
経路案内装置１０は、主に車両に搭載されナビゲーション装置として利用されるが、携帯電話機、ＰＨＳ（Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−Ｐｈｏｎｅ  Ｓｙｓｔｅｍ）、携帯情報端末、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、ゲーム機、デジタルテレビ受信機等、およそコンピュータを搭載したデバイスに適用できる。
【００１３】
入力装置３は、押下式のキーボード、ボタン、リモコン、十字キー、タッチパネル等により構成され、運転者や乗員からの操作を受け付けるためのものである。また、マイクを備え運転者の発する音声を音声認識回路で認識することで操作を入力してもよい。後述するように、本実施の形態の経路案内装置１０は目的地を入力すると、現在位置から目的地までの経路探索を行う。目的地は、住所、地名、ランドマーク名、郵便番号、電話番号等で入力することができる。
【００１４】
また、入力装置３から右折又は左折信号がある交差点の右左折を優先的に選択して経路を探索する設定を行う右左折信号優先設定が入力できる。右左折信号優先設定の情報は、経路探索装置４に送出される。なお、右左折信号優先設定について詳細は後述する。
【００１５】
位置検出装置２は、ＧＰＳ（Ｇｒｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの電波に基づき自車両の位置を測位して、さらに自律航法等により自車両の位置を推定する。位置検出装置２は、所定の軌道を周回する複数のＧＰＳ衛星のうち現在の車両の位置から所定の仰角に入るＧＰＳ衛星を好ましくは４つ以上選択し、それらのＧＰＳ衛星から発信される電波を受信する。なお、位置を測位するための電波を衛星からでなく、位置の知られた地上の基地局が受信してもよい。
【００１６】
ＧＰＳ衛星が発信する電波は、搬送波を衛星毎に固定の疑似ランダム符号により変調されているので、位置検出装置２は、選択したＧＰＳ衛星の疑似ランダム符号を生成して、受信される電波の復調を試みる。そして、ＧＰＳ電波が復調できる疑似ランダム符号の位相を決定する。
【００１７】
ＧＰＳ衛星の時計とＧＰＳ受信部１１が保持する時計が完全に一致しているとすれば、ＧＰＳ衛星で生成され搬送波を変調した疑似ランダム符号の位相と、受信した電波を復調した疑似ランダム符号の位相とは、電波の到達時間の分だけシフトしている。位置検出装置２は、そのシフト分に基づき電波の到達時間を計算し、到達時間と光速ｃから捕捉したＧＰＳ衛星までの距離を算出する。
【００１８】
自車両の位置は、緯度・経度・標高で特定される３次元上の１点であると考えられる。このため、位座標置検出装置２は、３つのＧＰＳ衛星と自車両の距離を算出し、各ＧＰＳ衛星との距離を半径とする球面が交差する２点のうち一方をＧＰＳ衛星からの電波に基づく自車両の位置として測位する。また、より好適には４つめのＧＰＳ衛星を捕捉して、ＧＰＳ衛星の時計とＧＰＳ受信部１１が保持する時計の誤差を補正し、より正確に自車両の位置を測位する。測位された位置はＷＧＳ（Ｗｏｒｌｄ  Ｇｅｏｄｅｔｉｃ  Ｓｙｓｔｅｍ）基準座標系による位置座標であるため、位置検出装置２はこれを地球固定直交座標系に変換する。
【００１９】
ついで、位置検出装置２は、車速センサ及びジャイロセンサを用いて自律航法によりさらに自車両の位置を高精度に推定する。車速センサは、例えば、各輪に備えられたロータの円周上に定間隔で設置された凸部が通過する際の磁束の変化をパルスとして計測して、単位時間あたりのパルス数に基づき各輪毎に車速を計測する。また、ジャイロセンサは、光ファイバージャイロ、震動片型ジャイロ等のヨーレートセンサであり、自車両が回転する時の角速度を検知して検知結果を積分することで角度、すなわち進行方向に変換できる。
【００２０】
位置検出装置２は、ＧＰＳ衛星からの電波により測位された位置に、車速センサによる走行距離及びジャイロセンサによる走行方向を累積しながら自律航法により車両の現在位置を精度よく推定する。さらに、道路地図に、推定した自車両の位置を対応づけるマップマッチング法により、地図上に表示する自車両の位置を高精度に決定する。
【００２１】
記録装置１は、ＣＤ−ＲＯＭ、ＤＶＤ（Digital Versatile Disk）、ハードディスク、フラッシュメモリ等の記録媒体により構成される。記録装置１に格納された道路地図には、道路網や交差点などの道路地図情報が、緯度・経度に対応づけて格納されている。道路地図は、実際の道路網をノード(道路と道路が交差する点、すなわち交差点)及びリンク(ノードとノードを接続する道路)に対応づけて、テーブル状のデータベースとして構成される。
【００２２】
図２は道路地図が格納されたデータベースの一例を示す。図２（ａ）は、リンクデータを図２（ｂ）はノードデータのそれぞれ一例を示す。図２（ａ）に示すように、道路地図データのうちリンクについては、道路を細分化して各リンク毎に情報を格納した複数のリンクデータとして表現される。
【００２３】
各リンクデータは、始点ノードＮｕｍｂｅｒ（以下、単にＮｏ.とする）、終点ノードＮｏ.、リンク方位、リンクの実際の長さ、属性、の情報が格納されている。そして、属性情報には、さらに、一方通行、道路種別（国道、高速道路、主要地方道路等）、幅員、車線数、速度規制、信号情報等の情報が格納されている。また、さらに信号情報は、信号数、始点リンクＮｏ.及び終点リンクＮｏ.の情報を有する。
【００２４】
始点リンクＮｏ.は、当該リンクへの接続が、その経路においていずれのリンクからなさているかを表す。始点リンクＮｏ.が設定されている場合、その始点リンクＮｏ.から対象とするノードを通して当該リンクへ向かう場合、通常（右左折信号に限らず）の信号又は右折若しくは左折信号のいずれかが存在すること表す。例えば、リンクＮｏ.１のリンクからリンクＮｏ.２のリンクへ接続する経路であって、リンクＮｏ.２のリンクに右折するための右折信号がある場合、リンクＮｏ.２のリンクデータには「始点リンクＮｏ.」としてリンクＮｏ.１が設定される。
【００２５】
また、図２（ｂ）に示すように、道路地図データのうちノードについては、各ノードに接続する複数のリンクを表す接続リンクＮｏ.が格納されている。
【００２６】
この他にも、道路地図のデータには、出発地、目的地、通過点等となる地点を検索するための施設データ、タウンページデータ等を有する。施設データとは、レストラン、食堂等の飲食店に関する情報（営業日、営業時間、駐車場の有無、電話番号、メニュー、値段等）である。また、タウンページデータは、例えば、コンビニエンスストア、百貨店、ホームセンタ、スーパーマーケット、テーマパーク、ゲームセンタ、映画館、劇場等である。
【００２７】
図３は、リンクデータ及びノードデータにより表される道路地図の一例を示す。図３では、「◎」が特定ノード、「○」が未探索ノードを示す。これらの意味及び探索方法については後述するが、特定ノードは通過するノードとして確定したもの、未探索ノードは通過するノードの候補である。また、各ノード間において、リンクは「→」で表されている。このうち、黒塗りされている矢印「→」については、矢印の示す方向から矢印の終端のノードに対しリンクしていることを表す。
【００２８】
したがって、図３では、リンクＮｏ.１１のリンクがノードＮｏ.１の特定ノードにリンクしており、該特定ノードからノードＮｏ.２、ノードＮｏ.３及びノードＮｏ.４のノード、３つのノードが未探索ノードとして示されている。特定ノードからノードＮｏ.２のノードにはリンクＮｏ.１２のリンクによりリンクされ、特定ノードからノードＮｏ.３のノードにはリンクＮｏ.１３のリンクによりリンクされ、特定ノードからノードＮｏ.４のノードにはリンクＮｏ.１４のリンクによりリンクされている。
【００２９】
図２のリンクデータと図３の道路地図とにより本実施の形態の道路地図を表すことができる。図４は、リンクＮｏ.１２〜１４のリンクデータ及びその道路地図の一例を示す。なお、図４において図３と同一部分には同一の符号を付しその説明は省略する。図４の道路地図に示すように、リンクＮｏ.１１のリンクから特定ノードに対し接続され、信号は、リンクＮｏ.１１の方向からリンクＮｏ.１３の方向に存在し、かつ、右折信号が付随している。
【００３０】
また、リンクデータによれば、リンクＮｏ.１２のリンクは、ノードＮｏ.１のノードを始点とし、ノードＮｏ.２のノードを終点とする。また、リンク方位は「西」であり、リンク実長は５００〔ｍ〕、また、このリンクに接続する信号は存在しない。リンクＮｏ.１３のリンクは、ノードＮｏ.１のノードを始点とし、ノードＮｏ.３のノードを終点とする。また、リンク方位は「北」であり、リンク実長は１０００〔ｍ〕、このリンクに接続する信号が１つ存在し、その始点リンクＮｏ.は１１である。リンクＮｏ.１４のリンクは、ノードＮｏ.１のノードを始点とし、ノードＮｏ.４のノードを終点とする。また、リンク方位は「東」であり、リンク実長は２０００〔ｍ〕、このリンクに接続する信号が１つ存在し、その始点リンクＮｏ.は１１である。
【００３１】
このように、本実施の形態の道路地図データでは、リンクＮｏ.１１のリンクから見た前方の通常の信号は、リンクＮｏ.１３に属性（信号）情報として設定され、右折信号は、リンクＮｏ.１４に属性（信号）情報として設定される。これは、リンクＮｏ.１１のリンクから、リンクＮｏ.１３のリンクへ向かう場合に信号があることを表し、また、リンクＮｏ.１１のリンクからリンクＮｏ.１４のリンクへ向かう場合に右折信号があることを表す。このとき、道路地図に示すように左折信号がないため、リンクＮｏ.１１からリンクＮｏ.１２へ向かう場合には、属性として信号のあることを意味する「始点リンクＮｏ.」は設定されない。
【００３２】
図５は、リンクＮｏ.１２〜１４のリンクデータ及びその道路地図の別の一例を示す。なお、図５において図３と同一部分には同一の符号を付しその説明は省略する。図５の道路地図に示すように、リンクＮｏ.１１のリンクから特定ノードに対し接続され、信号は、リンクＮｏ.１１の方向からリンクＮｏ.１３の方向及びリンクＮｏ.１３の方向からリンクＮｏ.１１の方向に２つ存在する。また、前者の信号には右折信号が設けられており、後者の信号には左折信号が設けられている。
【００３３】
したがって、リンクＮｏ.１２及び１３のリンクについては図４と同様のリンクデータとなるが、リンクＮｏ.１４のリンクからリンクＮｏ.１１のリンクの方向に、左折信号が付随した信号があるため、リンクＮｏ.１４のリンクデータには、属性情報として新号数が２つとなり、その始点リンクＮｏ.が１１と１２が記録されている。
【００３４】
本実施の形態の経路探索装置は、右折信号及び左折信号の有無がリンクデータに格納されていることから、経路探索時に通常の信号に加え右左折信号の有無に基づき目的地までの経路を探索できる。
【００３５】
図１に戻り、表示装置５は、液晶や有機ＥＬ、ＨＵＤ（Head  Up  Display）等により構成され、道路地図や自車両の位置、目的地及び目的地までの経路等を表示する。また、表示装置５はスピーカを備え、スピーカにより右左折する交差点など経路に沿った進行方向を音声により案内する。
【００３６】
また、経路案内装置１０は、ネットワークを介して外部のサーバと通信する通信装置を備えていてもよい。ネットワークは、例えば、有線又は無線の公衆通信回線網、携帯電話回線網、インターネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（ＷｉｄｅＡｒｅａ  Ｎｅｔｗｏｒｋ）、衛星通信回線網等やこれらを適宜組み合わせたものである。
【００３７】
また、地上波デジタルテレビ放送、ＦＭ多重放送、道路脇（わき）や道路上等に設置されている光ビーコン、電波ビーコン、準天頂衛星等から電波の受信装置を備え、これらを利用して通信してもよい。
【００３８】
経路探索装置４の探索方法について説明する。まず、ダイクストラ法について簡単に説明する。図６はダイクストラ法を説明するための図である。ダイクストラ法では、あるノード（例えば出発地）に接続するすべてのリンクのコストを計算しながら計算を行い、一段階分（１ノード分）の展開が終了するとコストの順に並べ替えを行い、未完成経路を展開するものとしないものに分け、展開するものをさらに順に展開していく。
【００３９】
図６（ａ）に示す経路図において、ノードＳからノードＧまでの経路が最も短い経路を探索する。経路長はリンクに記載したように、例えばＳＡ２、ＳＢ３、ＳＣ２である。これを順に展開していく。図６（ｂ）は展開結果を、それを短い順に並べ替えた結果を図６（ｃ）に示す。
ＳＡ２を展開すると、ＳＡＢ４．５となる。
ＳＢ３を展開するとＳＢＧ６、ＳＢＣ４．５、ＳＢＤ７、ＳＢＡ５．５となる。
ＳＣ２を展開するとＳＣＢ３．５、ＳＣＤ４となる。
【００４０】
また、ノードＧを含む四角で囲んだ経路は完成経路であるのでそれ以上は展開しない。完成経路ＳＢＧ６よりも短い経路があるのでこれらを展開していき、完成経路ＳＢＧ６よりも長い経路はここで展開を打ち切る。また、スタートしたノードに戻る経路は展開しないこととする。
【００４１】
ＳＣＢ３．５を展開すると、ＳＣＢＧ６．５、ＳＣＢＤ７．５となる。
ＳＣＤ４を展開すると、ＳＣＤＢ８、ＳＣＤＧ５となる。
ＳＡＢ４．５を展開すると、ＳＡＢＣ６．０、ＳＡＢＧ７．５、ＳＡＢＤ８．５となる。
ＳＢＣ４．５を展開すると、ＳＢＣＤ６．５となる。
【００４２】
図６（ｄ）は展開結果を示す。完成経路の中で最も距離が短いのは、ＳＣＤＧ５となる。また、これより短い未完成経路はないのでＳＣＤＧ５が最短の経路として探索される。実際には、距離（リンク実長）をリンクコストに置き換え、さらにリンクコストは距離だけでなく、リンクデータに格納されている道路種別（有料道路、高速道路）、幅員、車線数等がパラメータとなって決定されている。
【００４３】
また、目的地に向かわない方向の展開を排除するため、目的までの経路の残りの推定距離が所定以上の経路は展開を打ち切る。これにより、目的地と遠ざかる方向の経路探索を省き経路探索を短時間にできる。
【００４４】
また、ノードコストについては、左折コスト、直進コスト及び右折コストのように分けられ、一般的には、直進コストが最も低く、ついで、左折コスト、右折コストの順にコストが高くなる。これは、左折の場合は歩行者の通過待ちが、右折の場合、対向車の通過待ちが必要なるためである。したがって、１つのリンクのみからなる経路と１つのノードを介して接続された２つのリンクからなる経路の距離が同じ場合、ノードを含む経路の方がコストが大きくなる。以下、リンクコスト及びノードコストを単に総コストと称す。
【００４５】
本実施の形態では、ユーザが入力装置３から右左折信号優先設定を選択した場合には、右折信号又は左折信号がある交差点を右折又は左折する経路として選択しておき（右折信号又は左折信号がない交差点は経路としない）、その後、総コストに基づき最終的な経路を決定する。これにより、右左折に苦手な運転者に適切な経路を案内できる。なお、ユーザが選択しない場合は、総コストに基づき経路が選択される。
【００４６】
図７は経路を探索する手順の概念を示す図である。まず、経路探索におけるノードの種類について説明する。本実施の形態の場合には、「■」により示される確定ノード、「●」により示される未確定ノード、「◎」により示される特定ノード、「○」により示される未探索ノードの4種類がノードの種類である。
【００４７】
確定ノードは、既に検索されているノードで、かつ、コストが確定しているノードを示す。未確定ノードは、既に検索されているノードであるが、まだコストが確定されていないノードを示す。特定ノードは、未確定ノードの中からコストが最小とであるとして1つ選ばれたノードである。この特定ノードを基準に特定ノードに接続する未だ探索されていない未探索ノードを探索する。
【００４８】
次に、未確定ノードから確定ノードへの移行、及び、未探索ノードから未確定ノードへの移行について説明する。
【００４９】
図７（ｂ）では、確定ノード（■）に接続する未確定ノード（●）が５つある。この５つの中で、右左折信号優先設定、又は、総コストが最小となるノードが特定ノード（◎）
とされる。
【００５０】
図７（ｂ）では、Ｉで示した未確定ノードが特定ノードとされた。特定ノードが選択されるとその特定ノード（◎）に接続する３つの末探索ノード（○）が、経路の検索対象のノードとなる。図７（ｃ）はノードＩが特定ノードとなり、該特定ノードに接続された３つの探索対象のノードを示す。
【００５１】
そして、３つの探索対象のノードを探索することによって、図７（ｄ）に示すように、ノードＩは確定ノードに移行し、３つの探索ノードは未確定ノード（●）に移行する。なお、探索するとは、道路地図データからリンクデータ及びノードデータを参照し、リンクコスト及びノードコストを抽出することをいう。
【００５２】
以降は、総コストが最小になる未確定ノードを特定ノードに選択する処理を繰り返すことによって探索始点ノード（現在地）から探索終点ノード（目的地）までの経路が設定される。
【００５３】
図１に戻り、経路探索装置４及び位置検出装置２は、ＣＰＵ、ＲＯＭ、ＲＡＭ、ＮＶ−ＲＡＭ（Non-Volatile  ＲＡＭ）、ハードディスクドライブ及び通信部等がバスにより接続されたマイコンとして構成される。図１に示したように、経路探索装置４は、右折信号又は左折信号を付随する信号機のある前記交差点の右左折を優先的に経路として選択する経路探索手段と、経路探索手段による経路探索をするか否かを選択する経路探索手法選択手段とを有する。経路探索手法選択手段は、表示装置に選択のための画面を表示し、入力装置からユーザの選択を受け付ける。
【００５４】
ＣＰＵがＲＯＭに格納されたプログラムを実行することで、経路探索手段や経路探索手法選択手段を実現する。また、経路案内装置１０が車両に搭載された場合、車載された他のＥＣＵ（Ｅｌｅｃｔｏｒｉｃａｌ  Ｃｏｎｔｒｏｌｌ  Ｕｎｉｔ）とＣＡＮ（Ｃｏｎｔｒｏｌｌｅｒ Ａｒｅａ Ｎｅｔｗｏｒｋ）プロトコルによりバスを介して相互に通信を行う。
【００５５】
続いて、経路探索の探索手順についてより詳細に説明する。図８は、探索手順の全体を示すフローチャート図である。
【００５６】
まず、ユーザにより入力装置３から、右左折信号優先設定又は総コストを優先するかの設定が入力される（Ｓ１０）。図９は、経路探索手法選択手段が表示する右左折信号優先設定の設定画面の一例を示す。ユーザは表示装置５に表示された設定画面をタッチパネルや選択キーにより選択できる。また、音声により所望の設定を入力してもよい。また、前回の設定がデフォルトとして残っているので、そのまま何も入力しない場合もある。本実施の形態では、右左折信号優先設定の設定がなされたものとするが、総コストを優先した場合の経路探索についても簡単に説明する。
【００５７】
ついで、ユーザにより入力装置３から、目的地が設定され（Ｓ２０）、また、自車両の現在地が位置検出装置２により推定される（Ｓ３０）。
【００５８】
経路探索装置４は、目的地と現在地とに基づき初期経路計算を行う（Ｓ４０）。初期経路計算について詳細は後述する。
【００５９】
経路探索装置４は、経路が探索されると案内を開始する（Ｓ５０）。案内は、表示装置５に道路地図及び現在の車両の位置を表示すると共に、「道なり」「右折」「左折」等の音声をスピーカから出力して行う。
【００６０】
ついで、経路探索装置４は再計算するか否かを判定する（Ｓ６０）。再計算の実行判定について詳細は後述する。
【００６１】
再計算する場合（Ｓ７０のＹｅｓ）、経路の再計算を行い（Ｓ８０）、再計算しない場合（Ｓ７０のＮｏ）、案内が終了するか否かを判定する（Ｓ９０）。案内が終了するか否かは、例えば、目的地に到達したか否かにより判定される。案内が終了するまで、再計算するか否か（Ｓ６０）以降の処理を繰り返す。
【００６２】
続いて、ステップＳ４０の初期経路計算について図１０〜１２のフローチャート図に基づき説明する。説明のため、図４及び図７の道路地図を使用する。
【００６３】
まず、経路探索装置４は、探索始点ノードを確定する（Ｓ１１０）。探索始点ノードは、探索開始時であれば自車両の現在位置又は最寄りのノードであり、探索の途中であれば未確定ノードである。
【００６４】
経路探索装置４は、探索終点ノードを確定する（Ｓ１２０）。探索終点ノードは、目的地に最寄りのノードである。
【００６５】
ついで、経路探索装置４は、始点ノードを未確認ノードとして登録する（Ｓ１３０）。そして、通常、複数ある未確定ノードから総コストが最小となるノードを特定する（Ｓ１４０）。コストの算出には周知のダイクストラ法又はそれを修正したアルゴリズムを用いる。
【００６６】
図７（ｂ）を例に取れば、未確定ノードはＣ、Ｆ、I、Ｇ，Ｈであるので、ノードＳから各未確定ノード、ＳＡＣ、ＳＢＤＦ、ＳＢＤＧ、ＳＢＥＦ、ＳＢＤＩまでのコストを算出する。なお、より詳細には、これらの各経路と残りの経路を考慮して残りの総コストが大きい経路は排除し、各経路から総コストが最小の経路を決定する。本実施例では、目的地の方向が例えばノードＫの方向であるとして、ＳＢＤＩ、ＳＢＤＦ、ＳＢＤＧを選択対象とし、さらに、ノードコストに右左折コストが必要となるＳＢＤＦ、ＳＢＤＧの展開が終了される。これにより、ＳＢＤＩのコストが最小となり、ノードＩが特定ノードとして選択される。
【００６７】
ついで、特定ノードが終点ノードと一致したか否かを判定する（Ｓ１５０）。総コストが最小なノードを経由して特定ノードが終点ノードと一致すれば、経路の探索は終了する（Ｓ１５０のＹｅｓ）。
【００６８】
特定ノードが終点ノードと一致しない場合（Ｓ１５０のＮｏ）、ステップＳ２００に進む。
【００６９】
ステップＳ２００において、経路探索手段は、まず信号フラグにＯＦＦを設定する（Ｓ２００）。信号フラグは、後述するように特定ノードに接続するリンクに右左折信号があるか否かを判定するためのフラグである。フラグをＯＦＦにするとは、信号がないこと（初期化）に相当する。信号フラグの状態はＮＶ−ＲＡＭに格納されている。
【００７０】
ついで、経路探索手段は、特定ノードに接続する全てのリンクを探索する（Ｓ２１０）。すなわち、特定ノードに接続する全てのリンクのリンクデータを参照する。リンクデータには右左折信号の有無として、始点リンクＮｏ.が記録されている。
【００７１】
ついで、経路探索手段は、ユーザにより右左折信号優先設定がなされているか否かを判定する（Ｓ２３０）。かかる判定により、右左折信号のある交差点を優先的に通過したいユーザには右左折信号のある交差点を経由する経路が探索され、目的地までの総コストを優先したいユーザには距離や到達時間の短い経路の探索が可能となる。
【００７２】
右左折信号優先設定がある場合（Ｓ２２０のＹｅｓ）、経路探索手段はいずかのリンクに右左折信号の付随した信号機があるか否かを判定する（Ｓ２３０）。例えば、図４に示すように、ノードＮｏ.１のノードが特定ノードである場合、リンクＮｏ.１２〜１４のリンクデータから信号機の有無を判定する。図４ではリンクＮｏ.１３と１４に信号機がある。
【００７３】
右左折信号の信号機がある場合（Ｓ２３０のＹｅｓ）、信号フラグをＯＮに設定する（Ｓ２４０）。また、右左折信号の信号機がない場合（Ｓ２３０のＮｏ）、信号フラグをＯＮにせず、ステップＳ２５０に進む。
【００７４】
ついで、経路探索装置４は、特定ノードに接続するリンクＮｏ.１２〜１４のリンクについて、順番にコストを計算する。
〔右左折信号機の優先設定がある場合〕
まず、信号フラグがＯＮか否かを判定する（Ｓ２５０）。信号フラグがＯＮの場合（Ｓ２５０のＹｅｓ）、リンクに信号があるか否かをリンク毎に順に判定する（Ｓ２６０）。
【００７５】
リンクＮｏ.１２のリンクの場合、信号機はないのでステップＳ２９０に進む。ステップＳ２９０では、特定ノードに接続するすべての接続リンクが終了したか否かが判定される（Ｓ２９０）。
【００７６】
まだ、リンクＮｏ.１３と１４のリンクが残っているので、経路探索手段は４はステップＳ２５０以下の処理を繰り返す。
【００７７】
リンクＮｏ.１３のリンクについては、信号機があるので（Ｓ２６０のＹｅｓ）、経路探索装置４は接続するリンクＮｏ.１３のリンクを経由してノードＮｏ.３のノードまでのコストを計算する（Ｓ２７０）。また、ノードＮｏ３．のノードを未確定ノードとして登録する（Ｓ２８０）。
【００７８】
同様に、リンクＮｏ.１４のリンクについては、信号機があるので（Ｓ２６０のＹｅｓ）、経路探索装置４は接続するリンクＮｏ.１４のリンクを経由してノードＮｏ.４のノードまでのコストを計算する。また、ノードＮｏ４．のノードを未確定ノードとして登録する。
【００７９】
特定ノードに接続する全てのリンクについて処理が終了したので（Ｓ２９０のＹｅｓ）、ステップＳ１４０に戻る。
【００８０】
〔右左折信号優先設定がない場合〕
右左折信号機の優先設定がない場合、ステップＳ２２０及びステップＳ２５０の判定はＮｏであるため、リンクＮｏ.１２〜１４のリンクデータについて、それぞれコスト計算（Ｓ２７０）され、ノードＮｏ２〜４の各ノードが未確定ノードとして登録される（Ｓ２８０）。
【００８１】
特定ノードに接続する全てのリンクについて処理が終了したら（Ｓ２９０のＹｅｓ）、ステップＳ１４０に戻る。
【００８２】
以上の処理結果を整理する。
（ａ１）右左折信号機の優先設定がある場合、ノードＮｏ.２のノードへのリンクは信号機がないため、コスト計算もされず、未確定ノードとして登録もされないため、経路として選択されることがない。
（ａ２）右左折信号機の優先設定がある場合、ノードＮｏ.３のノードへのリンクは信号機があるため、コスト計算され、未確定ノードとして登録される。
（ａ３）右左折信号機の優先設定がある場合、ノードＮｏ.４のノードへのリンクは信号機があるため、コスト計算され、未確定ノードとして登録される。
（ａ４）右左折信号機の優先設定がない場合、ノードＮｏ.２〜４のノードへの全てのリンクについて、コスト計算され、未確定ノードとして登録される。
【００８３】
ステップＳ１４０では、上述したように、未確定ノードを含む全ての経路のコストを比較して、総コストが最小となる特定ノードを決定する。
【００８４】
経路探索装置４は、特定ノードと終点ノードが一致したら（Ｓ１５０のＹｅｓ）、ステップＳ３００へ進む。
【００８５】
すなわち、経路リンクをＲＡＭやハードディスクドライブなどの記憶領域に格納する（Ｓ３００）。経路リンクとは、ノードＳから終点ノードに至る、すなわち、現在位置から目的地までの経路を示す全てのリンクである。
【００８６】
経路探索装置４は、経路リンクに基づき経路表示用データを作成する（Ｓ３１０）。経路表示用データは、表示装置５の道路地図に経路リンクを表示するためのデータである。例えば、経路は道路地図の道路部分とは異なる視認性の高い色で表示される。
【００８７】
また、経路探索装置４は、経路リンクに基づき経路案内用データを作成する（Ｓ３２０）。経路案内用データは、スピーカから音声により経路を案内するためのデータである。
【００８８】
そして、経路探索装置４は、経路表示用データにより経路を表示し（Ｓ３３０）、また、所定のタイミングで経路案内データによる案内を行う。
【００８９】
以上のような処理により、ユーザが右左折信号を優先的に経路とする設定をすれば、右左折信号のある交差点のうち総コストが最小となる経路を探索することができるので、右折や左折の苦手な運転者であっても、運転が容易で総コストも比較的小さい経路を探索できる。また、右折や左折が得意な運転者であれば、総コストが最小となる経路を探索することができるので煩わしさを感じることがない。
【００９０】
〔再計算実行判定〕
続いて、ステップＳ６０の再計算実行判定について説明する。本実施の形態では、右左折信号優先設定があるか否かにより経路が変わるので、右左折信号優先設定に変化がある場合に再計算を実行する。
【００９１】
図１３は、再計算実行判定の処理手順を示すフローチャート図である。まず、経路探索装置４は車両が停車したか否かを判定する（Ｓ４１０）。車両が停車した場合、自車両の位置が固定されるので経路探索が容易になる。車両が停車したか否かは例えば車速センサの検出値により判定される。
【００９２】
車両が停車した場合（Ｓ４１０のＹｅｓ）、右左折信号優先設定に変化があるか否かを判定する（Ｓ４２０）。そして、右左折信号を優先的に経路とする設定に変化がある場合（Ｓ４２０のＹｅｓ）、経路の再計算を実行する（Ｓ４３０）。経路の再計算を実行する場合、ステップＳ４０の処理が実行される。
【００９３】
以上のように、本実施の形態の経路案内装置１０は、右左折信号優先設定がある場合は右左折信号のない交差点を右左折する経路が選択されることがないので、初心者やペーパードライバのように右折や左折の苦手な運転者でも安心して走行することができる。また、右左折信号優先設定がない場合は、総コストが最小となる経路を探索することができるので熟練したドライバもとっても都合がよい。
【図面の簡単な説明】
【００９４】
【図１】経路案内装置のシステム構成図である。
【図２】道路地図が格納されたデータベースの一例を示す図である。
【図３】リンクデータ及びノードデータにより表される道路地図の一例である。
【図４】リンクＮｏ.１２〜１４のリンクデータ及びその道路地図の一例である。
【図５】リンクＮｏ.１２〜１４のリンクデータ及びその道路地図の一例である。
【図６】ダイクストラ法を説明するための図である。
【図７】経路を探索する手順の概念を示す図である
【図８】探索手順の全体を示すフローチャート図である。
【図９】右左折信号優先設定の設定画面の一例である。
【図１０】初期経路計算の処理手順を示すフローチャート図である。
【図１１】初期経路計算の処理手順を示すフローチャート図である。
【図１２】初期経路計算の処理手順を示すフローチャート図である。
【図１３】再計算実行判定の処理手順を示すフローチャート図である
【符号の説明】
【００９５】
１    記録装置
２    位置検出装置
３    入力装置
４    経路探索装置
５    表示装置
６    右左折信号優先設定
１０  経路案内装置
【図１】
2007255919.tif 000003
【図２】
2007255919.tif 000004
【図３】
2007255919.tif 000005
【図４】
2007255919.tif 000006
【図５】
2007255919.tif 000007
【図６】
2007255919.tif 000008
【図７】
2007255919.tif 000009
【図８】
2007255919.tif 000010
【図９】
2007255919.tif 000011
【図１０】
2007255919.tif 000012
【図１１】
2007255919.tif 000013
【図１２】
2007255919.tif 000014
【図１３】
2007255919.tif 000015