(57)【特許請求の範囲】
【請求項１】
道路地図を記憶する道路地図記憶手段と、
車両の現在地を検出する現在地検出手段と、
目的地を設定する目的地設定手段と、
車両の停車状態を検出する停車検出手段と、
前記停車検出手段により停車状態が検出されている時に、前記道路地図記憶手段の道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する現在地周辺探索手段と、
前記目的地設定手段による目的地の設定後に、前記現在地周辺探索手段による探索結果に基づいて目的地から現在地への最適経路を探索する複数の経路探索手段であって、目的地から現在地への指向性の強さがそれぞれ異なる複数の経路探索手段と、
前記複数の経路探索手段の中から前記目的地設定手段による目的地設定後から出発までの待ち時間に応じた経路探索手段を選択する選択手段と、
前記道路地図記憶手段から道路地図を読み出して表示するとともに、その道路地図上に前記選択手段により選択された経路探索手段の探索結果の最適経路を表示する表示手段とを備えることを特徴とする車両用経路誘導装置。
【請求項２】
請求項１に記載の車両用経路誘導装置において、
前記選択手段は、前記複数の経路探索手段の中から前記待ち時間に応じた経路探索手段を手動で選択するための手段であることを特徴とする車両用経路誘導装置。
【請求項３】
請求項１に記載の車両用経路誘導装置において、
前記選択手段は、前記複数の経路探索手段の中から前記待ち時間に応じて自動的に経路探索手段を選択することを特徴とする車両用経路誘導装置。
【請求項４】
請求項３に記載の車両用経路誘導装置において、
前記選択手段は、前記複数の経路探索手段の中から目的地から現在地への指向性の強い順に経路探索手段を選択することを特徴とする車両用経路誘導装置。
【請求項５】
請求項１〜４のいずれかの項に記載の車両用経路誘導装置において、
目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記複数の経路選択手段はそれぞれ（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索することを特徴とする車両用経路誘導装置。
【請求項６】
請求項５に記載の車両用経路誘導装置において、
前記複数の経路探索手段には指向性の強さＫが１以下の経路探索手段と指向性の強さＫが１よりも大きい経路探索手段とが含まれることを特徴とする車両用経路誘導装置。
【請求項７】
道路地図を記憶する道路地図記憶手段と、
車両の現在地を検出する現在地検出手段と、
目的地を設定する目的地設定手段と、
車両の停車状態を検出する停車検出手段と、
前記停車検出手段により停車状態が検出されている時に、前記道路地図記憶手段の道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する第１の経路探索手段と、
前記目的地設定手段により目的地が設定されると、前記第１の経路探索手段により探索された交差点の中から目的地に最も近い交差点を抽出する交差点抽出手段と、
前記第１の経路探索手段による探索結果に基づいて、現在地から前記交差点抽出手段により抽出された交差点までの最適経路を探索する第２の経路探索手段と、
前記道路地図記憶手段から道路地図を読み出して表示するとともに、その道路地図上に前記第２の経路探索手段により探索された最適経路を表示する表示手段とを備えることを特徴とする車両用経路誘導装置。
【請求項８】
請求項７に記載の車両用経路誘導装置において、
目的地から前記交差点抽出手段により抽出された交差点までの最適経路を探索する第３の経路探索手段を備え、
前記表示手段は、道路地図上に前記第２の経路探索手段により探索された最適経路と前記第３の経路探索手段により探索された最適経路とを表示することを特徴とする車両用経路誘導装置。
【請求項９】
請求項７に記載の車両用経路誘導装置において、
前記表示手段に前記第２の経路探索手段により探索された最適経路が表示された時点に前記停車検出手段により停車状態が検出されると、前記第１の経路探索手段による探索結果に基づいて目的地から現在地までの最適経路を探索する第３の経路探索手段を備え、
前記表示手段は、前記停車検出手段により停車状態が検出されている間に前記第３の経路探索手段による探索が終了したら、前記第３の経路探索手段による探索結果の最適経路を道路地図上に表示することを特徴とする車両用経路誘導装置。
【請求項１０】
請求項９に記載の車両用経路誘導装置において、
前記第３の経路探索手段は、目的地から現在地への指向性の強い探索を行なうことを特徴とする車両用経路誘導装置。
【請求項１１】
請求項１０に記載の車両用経路誘導装置において、
目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第３の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索することを特徴とする車両用経路誘導装置。
【請求項１２】
請求項１１に記載の車両用経路誘導装置において、
前記第３の経路探索手段は、指向性の強さＫを１よりも大きな値とすることを特徴とする車両用経路誘導装置。
【請求項１３】
請求項１０〜１２のいずれかの項に記載の車両用経路誘導装置において、
前記表示手段に前記第３の経路探索手段により探索された最適経路が表示された時点に前記停車検出手段により停車状態が検出されると、前記第１の経路探索手段による探索結果に基づいて前記第３の経路探索手段よりも弱い指向性で目的地から現在地までの最適経路を探索する第４の経路探索手段を備え、
前記表示手段は、前記停車検出手段により停車状態が検出されている間に前記第４の経路探索手段による探索が終了したら、前記第４の経路探索手段による探索結果の最適経路を道路地図上に表示することを特徴とする車両用経路誘導装置。
【請求項１４】
請求項１３に記載の車両用経路誘導装置において、
目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第４の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索することを特徴とする車両用経路誘導装置。
【請求項１５】
請求項１４に記載の車両用経路誘導装置において、
前記第４の経路探索手段は、指向性の強さＫを１以下とすることを特徴とする車両用経路誘導装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、目的地までの最適経路を探索して乗員を誘導する車両用経路誘導装置に関する。
【０００２】
【従来の技術とその問題点】
目的地を設定すると現在地から目的地までの最適な経路を探索し、その最適経路と車両の現在地を道路地図上に表示して乗員を目的地まで誘導する車両用経路誘導装置が知られている。
この目的地までの最適経路の探索は、膨大な交差点ネットワークデータを検索して形成される目的地までの無数の経路の中から、例えば道程が最小の経路や所要走行時間が最小の経路を最適経路に選定している。
【０００３】
しかしながら、従来の車両用経路誘導装置では、乗員が目的地を設定してから最適経路の探索を開始しているので、探索を終了するまで経路誘導が行なわれず、乗員が待たされるという問題がある。
【０００４】
この問題を解決するために、本出願人らは特願平５−２２５９４８号で次のような車両用経路誘導装置を提案している。すなわち、車両が停車状態にある時に道路地図データを検索して現在地からその周辺の各交差点へ至る最適経路を探索し、目的地が設定されると現在地周辺の経路探索結果と道路地図データとを検索して目的地から現在地へ至る最適経路を探索するものである。これにより、目的地が設定された後の目的地から現在地への経路探索において、すでに最適経路が探索されている現在地周辺の交差点までの経路探索を改めて行なう必要がなく、その分だけ経路探索時間が短縮され、目的地の設定後に速やかに最適経路を探索して乗員の誘導を開始できる。
【０００５】
本発明の目的は、目的地を設定したら速やかに最適経路を探索して乗員の誘導を開始する車両用経路誘導装置を提供することにあり、上述した車両用経路誘導装置に改良を加えて乗員の待ち時間をさらに低減するものである。
【０００６】
【課題を解決するための手段】
上記目的を達成するために、請求項１の発明は、道路地図を記憶する道路地図記憶手段と、車両の現在地を検出する現在地検出手段と、目的地を設定する目的地設定手段と、車両の停車状態を検出する停車検出手段と、前記停車検出手段により停車状態が検出されている時に、前記道路地図記憶手段の道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する現在地周辺探索手段と、前記目的地設定手段による目的地の設定後に、前記現在地周辺探索手段による探索結果に基づいて目的地から現在地への最適経路を探索する複数の経路探索手段であって、目的地から現在地への指向性の強さがそれぞれ異なる複数の経路探索手段と、前記複数の経路探索手段の中から前記目的地設定手段による目的地設定後から出発までの待ち時間に応じた経路探索手段を選択する選択手段と、前記道路地図記憶手段から道路地図を読み出して表示するとともに、その道路地図上に前記選択手段により選択された経路探索手段の探索結果の最適経路を表示する表示手段とを備える。
請求項２の車両用経路誘導装置は、前記選択手段を、前記複数の経路探索手段の中から前記待ち時間に応じた経路探索手段を手動で選択するための手段としたものである。
請求項３の車両用経路誘導装置は、前記選択手段によって、前記複数の経路探索手段の中から前記待ち時間に応じて自動的に経路探索手段を選択するようにしたものである。
請求項４の車両用経路誘導装置は、前記選択手段によって、前記複数の経路探索手段の中から目的地から現在地への指向性の強い順に経路探索手段を選択するようにしたものである。
請求項５の車両用経路誘導装置は、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記複数の経路選択手段はそれぞれ（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたものである。
請求項６の車両用経路誘導装置は、前記複数の経路探索手段に、指向性の強さＫが１以下の経路探索手段と指向性の強さＫが１よりも大きい経路探索手段とが含まれるようにしたものである。
請求項７の発明は、道路地図を記憶する道路地図記憶手段と、車両の現在地を検出する現在地検出手段と、目的地を設定する目的地設定手段と、車両の停車状態を検出する停車検出手段と、前記停車検出手段により停車状態が検出されている時に、前記道路地図記憶手段の道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する第１の経路探索手段と、前記目的地設定手段により目的地が設定されると、前記第１の経路探索手段により探索された交差点の中から目的地に最も近い交差点を抽出する交差点抽出手段と、前記第１の経路探索手段による探索結果に基づいて、現在地から前記交差点抽出手段により抽出された交差点までの最適経路を探索する第２の経路探索手段と、前記道路地図記憶手段から道路地図を読み出して表示するとともに、その道路地図上に前記第２の経路探索手段により探索された最適経路を表示する表示手段とを備える。
請求項８の車両用経路誘導装置は、目的地から前記交差点抽出手段により抽出された交差点までの最適経路を探索する第３の経路探索手段を備え、前記表示手段に、道路地図上に前記第２の経路探索手段により探索された最適経路と前記第３の経路探索手段により探索された最適経路とを表示するようにしたものである。
請求項９の車両用経路誘導装置は、前記表示手段に前記第２の経路探索手段により探索された最適経路が表示された時点に前記停車検出手段により停車状態が検出されると、前記第１の経路探索手段による探索結果に基づいて目的地から現在地までの最適経路を探索する第３の経路探索手段を備え、前記表示手段に、前記停車検出手段により停車状態が検出されている間に前記第３の経路探索手段による探索が終了したら、前記第３の経路探索手段による探索結果の最適経路を道路地図上に表示するようにしたものである。
請求項１０の車両用経路誘導装置は、前記第３の経路探索手段によって、目的地から現在地への指向性の強い探索を行なうようにしたものである。
請求項１１の車両用経路誘導装置は、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第３の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたものである。
請求項１２の車両用経路誘導装置は、前記第３の経路探索手段の指向性の強さＫを１よりも大きな値としたものである。
請求項１３の車両用経路誘導装置は、前記表示手段に前記第３の経路探索手段により探索された最適経路が表示された時点に前記停車検出手段により停車状態が検出されると、前記第１の経路探索手段による探索結果に基づいて前記第３の経路探索手段よりも弱い指向性で目的地から現在地までの最適経路を探索する第４の経路探索手段を備え、前記表示手段に、前記停車検出手段により停車状態が検出されている間に前記第４の経路探索手段による探索が終了したら、前記第４の経路探索手段による探索結果の最適経路を道路地図上に表示するようにしたものである。
請求項１４の車両用経路誘導装置は、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第４の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたものである。
請求項１５の車両用経路誘導装置は、前記第４の経路探索手段の指向性の強さＫを１以下としたものである。
【０００７】
【作用】
請求項１の車両用経路誘導装置では、車両の停車状態が検出されている時に道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索するとともに、目的地の設定後に出発までの待ち時間に応じた経路探索手段を選択し、その経路探索手段によって現在地周辺の探索結果に基づいて目的地から現在地への最適経路を探索する。そして、道路地図を読み出して表示するとともに、その道路地図上に選択された経路探索手段の探索結果の最適経路を表示する。
請求項２の車両用経路誘導装置では、複数の経路探索手段の中から目的地設定後から出発までの待ち時間に応じた経路探索手段を手動で選択する。
請求項３の車両用経路誘導装置では、複数の経路探索手段の中から目的地設定後から出発までの待ち時間に応じて自動的に経路探索手段を選択する。
請求項４の車両用経路誘導装置では、複数の経路探索手段の中から目的地から現在地への指向性の強い順に経路探索手段を選択する。
請求項５の車両用経路誘導装置では、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索する。
請求項７の車両用経路誘導装置では、まず、車両の停車状態が検出されている時に、道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する。次に目的地が設定されると、現在地からの最適経路が探索された交差点の中から目的地に最も近い交差点を抽出し、現在地周辺の最適経路の探索結果に基づいて現在地から抽出された交差点までの最適経路を探索する。そして、道路地図を表示するとともに、その道路地図上に探索された現在地から抽出交差点までの最適経路を表示する。
請求項８の車両用経路誘導装置では、目的地から抽出された交差点までの最適経路を探索し、道路地図上に探索された現在地から抽出交差点までの最適経路と目的地から抽出交差点までの最適経路とを表示する。
請求項９の車両用経路誘導装置では、前記第２の経路探索手段により探索された最適経路が表示された時点に車両の停車状態が検出されると、現在地周辺の最適経路の探索結果に基づいて目的地から現在地までの最適経路を探索し、その最適経路の探索が車両の停車状態が検出されている間に終了したら、探索結果の最適経路を道路地図上に表示する。
請求項１０の車両用経路誘導装置では、前記第３の経路探索手段は目的地から現在地への指向性の強い探索を行なう。
請求項１１の車両用経路誘導装置では、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第３の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索する。
請求項１３の車両用経路誘導装置では、前記第３の経路探索手段により探索された最適経路が道路地図上に表示された時点に車両の停車状態が検出されると、現在地周辺の最適経路の探索結果に基づいて前記第３の経路探索手段よりも弱い指向性で目的地から現在地までの最適経路を探索し、その最適経路の探索が車両の停車状態が検出されている間に終了したら、探索結果の最適経路を道路地図上に表示する。
請求項１４の車両用経路誘導装置では、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、第４の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索する。
【０００８】
【実施例】
図１、図２は一実施例の構成を示すブロック図である。
この車両用経路誘導装置１００は、図に示すようにＣＰＵ１とその周辺部品から成るマイクロコンピューターを中心に構成される。ＣＰＵ１は、システムバス２を介して各種機器とデータの授受を行ない、後述する制御プログラムを実行して車両の現在地を演算し、現在地から目的地まで最適経路を探索する。方位センサ３は車両の進行方位を検出するセンサであり、増幅器４、Ａ／Ｄ変換器５およびＩ／Ｏコントローラー６を介してシステムバス２へ接続される。また、車速センサ７は例えばトランスミッションに取り付けられ、スピードメーターピニオン１回転当り所定数のパルス信号を発生する。この車速センサ７はＩ／Ｏコントローラー６を介してシステムバス２へ接続される。ＣＰＵ１は、車速センサ７から出力される単位時間当りのパルス数またはパルス周期を検出することにより車両の走行速度を検出するとともに、パルス数をカウントすることにより車両の走行距離を検出する。キー８は、装置へ種々の指令や目的地などのデータを入力するための操作部材であり、Ｉ／Ｏコントローラー９を介してシステムバス２へ接続される。音声出力用スピーカー１０はサウンドジェネレーター１１およびＩ／Ｏコントローラー９を介してシステムバス２へ接続される。ＧＰＳレシーバー１２は、衛星から送信されるＧＰＳ信号を受信し、ＧＰＳ測位演算を行なって車両の現在地や進行方位を検出する。
【０００９】
また、図２において、ＣＤ−ＲＯＭ１６は交差点ネットワークデータを含む道路地図データを記憶する記憶装置であり、インタフェース用ＳＣＳＩコントローラー１７を介してシステムバス２へ接続される。ＣＲＴ１８はＶＤＴ（Visual  Display Terminal）として機能するディスプレイであり、グラフィックコントローラー１９を介してシステムバス２へ接続される。このＣＲＴ１８に車両の現在地周辺の道路地図を表示するとともに、その道路地図上に車両の現在地と目的地までの最適経路を表示する。なお、システムバス２には、ＣＲＴ１８の画像記憶用Ｖ−ＲＡＭ２０、後述する制御プログラムなどを格納するＲＯＭ２１、目的地から現在地への経路探索結果を記憶するＤ−ＲＡＭ２２、漢字ＲＯＭ２３、イグニッションオフ時に現在地と現在地周辺の経路探索結果を記憶するＳ−ＲＡＭ２４が接続される。
【００１０】
図３は、図１と図２に示す経路誘導装置１００の電源系統図である。
この実施例の経路誘導装置１００には、キースイッチ１０２を介してバッテリー１０１から電源が供給される。キースイッチ１０２は、不図示のイグニッションキーがＡＣＣ，ＯＮ，ＳＴＡＲＴのいずれかの位置にあるときに閉路し、ＯＦＦ位置にあるときに開路する。したがって、イグニッションキーがＯＦＦ位置に設定されない限り、経路誘導装置１００にはバッテリー１０１から電源が供給されている。なお、Ｓ−ＲＡＭ２４は２つの電源系統を備えており、通常はＣＰＵ１，ＲＯＭ２１，Ｄ−ＲＯＭ２２などの機器と同様にバッテリー１０１から電源が供給されるが、その通常電源の供給が停止されても補助電池２７から電源が供給され、記憶内容を保持する。補助電池２７は、バッテリー１０１に接続されて常時充電可能とされる。
【００１１】
タイマー２６は、キースイッチ１０２により経路誘導装置１００に電源が供給されるとその接点を閉路し、電源の供給が停止されると予め設定された時間だけその接点の閉路状態を保持した後、開路する。したがって、イグニッションキーがＯＦＦ位置に設定されてキースイッチ１０２がオフしても、タイマー２６を介して設定時間だけ経路誘導装置１００にバッテリー１０１から電源が供給され続ける。設定時間が経過するとタイマー２６が開路し、経路誘導装置１００への電源の供給が停止される。このタイマー２６には、車両が停止した後、現在地周辺の経路探索を行なうのに充分な時間を設定する。つまり、乗員が車両を停車させてイグニッションキーをＯＦＦ位置にしても、タイマー２６の設定時間だけは経路誘導装置１００に電源が供給され続け、ＣＰＵ１は現在地と、現在地周辺の各交差点へ至る最適経路を探索することができる。
【００１２】
図４はこの実施例の基本的な経路探索方法を説明する図である。なお、以下の図では車両の現在地および目的地を×印で表わし、交差点を○印で表わす。
この実施例では２通りの基本的な経路探索方法により、現在地から目的地までの最適経路を探索する。第１の経路探索は、乗員が目的地を設定する前の停車中に行なわれる、現在地を中心とした無指向性の経路探索である。第２の経路探索は、目的地の設定後に第１の経路探索結果を用いて行なわれる、目的地から現在地への指向性の経路探索である。
【００１３】
（１）現在地を中心とする無指向性の経路探索
この経路探索では、停車中に車両の現在地を演算するとともに、現在地から任意の交差点へ至る複数の経路の中でその交差点までの道程ｈが最小の経路を探索する。ここで、停車中とは、例えば、イグニッションオフ後のタイマー２６によりバッテリー電源が供給されている間、シフトレバーがパーキンング位置またはニュートラル位置にある間、パーキングブレーキがセットされている間、車速センサ７により検出される車速パルス信号が所定値以下の時である。
またこの経路探索では、探索結果をイグニッションオフ後はＳ−ＲＡＭ２４へ記憶し、イグニッションオン後はＤ−ＲＡＭ２２へ記憶する。この探索結果の記憶メモリには、各交差点ごとに、出発交差点Ｄからの道程ｈと、出発交差点Ｄから各交差点へ至る最適経路上の、各交差点の手前にある直前交差点Ａとを記憶する。出発交差点Ｄとは、現在地近くの交差点の中から所定の条件を満たす交差点を出発交差点Ｄとして特定したものである。なお以下では、経路演算を行なうために検索する交差点を中心交差点Ｃと呼び、その中心交差点Ｃに隣接する交差点を隣接交差点Ｒと呼ぶ。
【００１４】
まず、出発交差点Ｄの道程ｈに０を設定し、他の交差点の道程ｈに無限大相当の定数を設定するとともに、出発交差点Ｄを中心交差点Ｃに設定して経路探索を開始する。中心交差点Ｃの道程に記憶された出発交差点Ｄからの道程ｈ０と、中心交差点Ｃから隣接交差点Ｒまでの道程ｈとを加算して出発交差点Ｄからその隣接交差点Ｒまでの道程ｈ１を求め、すでにその隣接交差点Ｒの道程に記憶されている出発交差点Ｄからの道程ｈ２と比較する。今回算出された道程ｈ１がｈ２よりも小さい場合は、その隣接交差点Ｒの道程ｈ２をｈ１に変更するとともに、その隣接交差点Ｒの直前交差点Ａに中心交差点Ｃを設定する。中心交差点Ｃに隣接するすべての隣接交差点Ｒに対して上記処理を終了したら、すでに中心交差点Ｃとして選択された交差点を除くすべての交差点の中から、出発交差点Ｄからの道程が最小の交差点を次の新しい中心交差点Ｃに設定する。以下、この新しい中心交差点Ｃの隣接交差点Ｒに対して上述した処理を行なう。
このように、出発交差点Ｄから道程の小さい順に新しい中心交差点Ｃを設定して経路探索を行なう。経路探索が終了した交差点において、その交差点の直前交差点Ａを順にたどっていくと出発交差点Ｄに到達する。その経路が出発交差点Ｄからその交差点までの最小道程の最適経路である。
【００１５】
ここで、現在地を中心とする無指向性の経路探索により探索された領域を第１領域と呼ぶ。この経路探索では、池に石を投げた時に波紋が広がっていくように、ほぼ円形の第１領域が時間ととも大きくなっていく。無指向性の経路探索による第１領域は大きければ大きいほど、目的地が設定された時の現在地から目的地までの経路探索時間が短くなる。例えば目的地が第１領域内にあれば瞬時にして目的地までの最適経路が得られるから、第１領域が大きければ目的地が第１領域内にある確率が高くなり、それだけ経路探索時間を短縮できることになる。
ところが、イグニッションオフ後にこの現在地を中心とする無指向性の経路探索を行なう場合は、際限なく行なうとバッテリー１０１の電力を必要以上に消費することになるから、上述したようにタイマー２６により所定時間が経過したら第１の経路探索を強制的に終了させ、電力消費の抑制を優先させる。
一方、イグニッションオン時はエンジンが始動されており、経路探索に必要な電力は十分に発電されていると考えられるから、車両が停車中である限り無指向性の経路探索を継続し、目的地設定後の経路探索時間の短縮を優先させる。
【００１６】
（２）目的地から現在地への指向性の経路探索
乗員が目的地を設定すると、上述した現在地を中心とする無指向性の経路探索結果を用いて、目的地から現在地へ向う指向性の経路探索を行なう。ここで、目的地から現在地までの最適経路は道程が最小の経路とする。この目的地から現在地までの最適経路の探索は、目的地近くの交差点の中から所定の条件を満たす交差点を目的交差点Ｓとして特定し、その目的交差点Ｓの周辺の交差点から探索を開始する。また、探索結果の記憶メモリ２２に、各交差点ごとに目的交差点Ｓからの道程ｇと、目的交差点Ｓから各交差点へ至る最適経路上の各交差点の手前にある直前交差点Ｂと、各交差点から出発交差点Ｄまでの推測道程ｈ’とを記憶する。なお、この実施例では、各交差点から現在地までの直線距離を道路地図データに基づいて算出し、それを推測道程ｈ’とする。
【００１７】
まず、目的交差点Ｓの道程ｇに０を設定し、他の交差点の道程ｇに無限大相当の定数を設定するとともに、目的交差点Ｓを中心交差点Ｃに設定して目的地からの経路探索を開始する。中心交差点Ｃの道程に記憶された目的交差点Ｓからの道程ｇ０と、中心交差点Ｃから隣接交差点Ｒまでの道程ｇとを加算して目的交差点Ｓからその隣接交差点Ｒまでの道程ｇ１を求め、すでにその隣接交差点Ｒの道程に記憶されている目的交差点Ｓからの道程ｇ２と比較する。今回算出された道程ｇ１がｇ２よりも小さい場合は、その隣接交差点Ｒの道程ｇ２をｇ１に変更するとともに、その隣接交差点Ｒの直前交差点Ｂに中心交差点Ｃを設定する。さらに、その隣接交差点Ｒから出発交差点までの推測道程ｈ’を算出して記憶する。
中心交差点Ｃに隣接するすべての隣接交差点Ｒに対して上記処理が終了したら、すでに中心交差点Ｃとして選択された交差点を除くすべての交差点の中から、目的交差点Ｓからの道程ｇと出発交差点Ｄまでの推測道程ｈ’との和（ｇ＋ｈ’）が最小の交差点を次の新しい中心交差点Ｃに設定する。以下、この新しい中心交差点Ｃの隣接交差点Ｒに対して上述した処理を行なう。
【００１８】
このように、目的交差点Ｓからの道程ｇと出発交差点Ｄまでの推測道程ｈ’との和（ｇ＋ｈ’）が小さい順に新しい中心交差点Ｃを設定して、目的地からの経路探索を行なう。探索中に、隣接交差点Ｒが、上述した現在地を中心とする無指向性の経路探索が終了している交差点、すなわち出発交差点Ｄからの最適経路が探索されている交差点に到達した場合は、その隣接交差点Ｒの目的交差点Ｓからの道程ｇと出発交差点Ｄからの道程ｈとの和（ｇ＋ｈ）、すなわちその隣接交差点Ｒを経由する経路の出発交差点Ｄから目的交差点Ｓまでの道程（ｇ＋ｈ）を求め、出発交差点Ｄの道程に記憶されているｇ３と比較する。ここで、出発交差点Ｄの道程ｇ３は出発交差点Ｄから目的交差点Ｓまでの道程である。比較の結果、隣接交差点Ｒの道程（ｇ＋ｈ）がｇ３よりも小さい場合は、出発交差点Ｄの道程ｇ３を（ｇ＋ｈ）に変更するとともに、出発交差点Ｄの直前交差点Ｂにその隣接交差点Ｒを設定する。ここで、出発交差点Ｄの直前交差点Ｂは、図４に示すように、目的地からの経路探索中に最初に到達する第１領域内の交差点であり、以下ではこのような交差点を接点交差点と呼ぶ。
【００１９】
ここで、目的地から現在地への指向性の経路探索を行なった時の探索領域を第２領域と呼ぶ。上述した方法で目的地から現在地への指向性の経路探索を行なうと、図４に示すように第２領域は現在地に近くなるほど狭くなる。道程（ｇ＋ｈ’）が小さい順に中心交差点Ｃを設定して目的地からの経路探索を進めていくと、ついには出発交差点Ｄが中心交差点Ｃになる。その時点で目的地からの経路探索を終了する。最終的に出発交差点Ｄの直前交差点Ｂに格納されている接点交差点を経由する経路が、目的交差点Ｓから出発交差点Ｄまでの最小道程の最適経路であり、その経路の道程は出発交差点Ｄの最終的な道程ｇで示される。
【００２０】
現在地を中心とする無指向性の経路探索と目的地から現在地への指向性の経路探索とを比較すると、前者は出発交差点Ｄからそれぞれの交差点までの道程ｈが小さい順に交差点を検索していくが、後者は目的交差点Ｓからそれぞれの交差点までの道程ｇと、それらの交差点から出発交差点Ｄまでの推測道程ｈ’との和（ｇ＋ｈ’）が小さい順に交差点を検索する。したがって、同一条件において両者の経路探索に要する時間を比較すると、指向性のある経路探索を行なう後者の場合は、演算量が少ないので前者の場合の約１／５の時間で探索を行なうことができる。
そこで、イグニッションオフ後にも、バッテリー電源が供給されている間に現在地を中心とする無指向性の経路探索をできる限り行ない、探索結果をＳ−ＲＡＭ２４に記憶する。イグニションオン後に目的地が設定されると、Ｓ−ＲＡＭ２４から現在地周辺の経路探索結果を読み出し、目的地から現在地に向って指向性のある経路探索を行なう。そして、後者の経路探索が前者の探索済みの第１領域に達したら、前者の探索結果を用いて現在地から目的地までの最適経路を選定する。
図４に示すように、後者の第２領域内の斜線部の領域の交差点に対してはすでに最適経路が探索されているので、この領域に対する探索は不要となり、その分だけ全体の経路探索時間を短縮することができる。現在地周辺の第１領域が広く、目的地をその第１領域内に設定した場合は、ほどんど瞬時に現在地から目的地までの経路探索が終了する。
【００２１】
ここで、目的地から現在地への指向性の経路探索について考察する。
上述した指向性探索では、目的交差点Ｓからある中心交差点Ｃまでの道程ｇと、その中心交差点Ｃから出発交差点Ｄまでの推測道程ｈ’との和（ｇ＋ｈ’）の小さい順に、中心交差点Ｃを設定して経路探索を行なった。この和（ｇ＋ｈ’）に指向性係数Ｋを導入し、（ｇ＋Ｋ・ｈ’）とする。この指向性係数Ｋは、経路探索における指向性の度合いを表わすものである。指向性係数Ｋが１の場合は経路の最短性が保証される限界の指向性探索であり、指向性係数Ｋが１よりも大きい場合は経路の最短性は保証されないが、Ｋが大きくなるほど短い時間で経路を探索でき、以下ではＫ＞１の指向性の強い経路探索を超指向性探索と呼ぶ。また、指向性係数Ｋが０の場合は上述した無指向性の経路探索となる。
【００２２】
図５は出発交差点Ｄから目的交差点Ｓまでの種々の指向性係数Ｋに対する経路探索領域を示す図であり、（ａ）はＫ＝０の無指向性探索の場合を示し、（ｂ）はＫ＝１の指向性探索の場合を示し、（ｃ）はＫ＞１の超指向性検索の場合を示す。
上述したように無指向性検索では、（ａ）に示すように出発交差点Ｄを中心にほぼ円形の探索領域が広がっていく。これに対し指向性探索では、（ｂ）に示すように出発交差点Ｄを中心とする楕円状の探索領域が目的交差点Ｓに引っ張られるように広がっていく。さらに超指向性探索では、（ｃ）に示すように探索領域が細長くなる。
これらの図から明らかなように、指向性係数Ｋが小さいと探索領域は大きく、探索時間がかかるが最短経路が探索される。指向性係数Ｋが大きくなるにしたがって探索領域は狭くなり、探索時間は短くなるが、経路の最短性は保証されなくなる。
【００２３】
図６、図７は現在地を中心とする無指向性の経路探索プログラムを示すフローチャート、図８〜図１１はＳ−ＲＡＭ２４に記憶される経路探索結果を示す図、図１２は交差点ネットワーク例を示す図である。これらの図により、現在地を中心とする無指向性の経路探索を説明する。
図８〜図１１において、（ａ）は最適経路情報を示すリストＡであり、このリストＡには現在地周辺の各交差点、それらの交差点までの道程ｈ、中心交差点Ｃに設定されたことを示すフラグ、現在地周辺の各交差点へ至る経路上の直前交差点Ａ、目的地から目的地周辺の各交差点へ至る道程ｇ、目的地から目的地周辺の各交差点へ至る経路上の直前交差点Ｂが含まれる。また、（ｂ）は中心交差点候補の交差点を示すリストＢである。なお、中心交差点Ｃに選択された交差点は出発交差点Ｄからの最適経路と道程ｈが算出される。
【００２４】
ステップ１００において出発交差点を特定する。この出発交差点は、例えば特開昭６２−８６４９９号公報に開示されているように、現在地周辺の交差点の中から、現在地を中心とする所定半径の円外に存在し、且つ最も現在地に近い交差点を出発交差点として選択する。今、図１２に示すように、交差点１が出発交差点として選択されたとする。なお、図１２では交差点を円で表し、円内の番号が交差点番号を示す。さらに、交差点と交差点を結ぶ線が道路を示し、各道路上の数字は交差点から交差点までの道程を示す。
次にステップ１０２へ進み、出発交差点を中心交差点とする。図１２の例では、出発交差点１を中心交差点とする。続くステップ１０４では、Ｓ−ＲＡＭ２４のリストＡの各種データを初期設定する。すなわち、図８（ａ）に示すように、全交差点のフラグに０を設定するとともに、出発交差点の道程ｈに０を設定し、他の全ての交差点の道程ｈに非常に大きい値＋∞を設定する。
【００２５】
ステップ１０６で、中心交差点に隣接する交差点の中からいずれかを選択する。続くステップ１０８において、中心交差点の道程ｈに中心交差点から選択された隣接交差点までの道程を加えた値と、隣接交差点の道程ｈとを比較し、前者が小さい場合はステップ１１０へ進み、そうでなければステップ１２０へ進む。ステップ１１０では、中心交差点の道程ｈに中心交差点から選択された隣接交差点までの道程を加えた値を、隣接交差点の道程ｈに設定する。
ステップ１０６〜１１０の処理過程を図１２の例で説明すると、中心交差点１には交差点２〜５が隣接しており、これらの隣接交差点の中からまず交差点２を選択する。そして、図８（ａ）に示すように、中心交差点１の道程ｈ＝０に中心交差点１から隣接交差点２までの道程３を加算した値３と、隣接交差点２の道程ｈ＝∞とを比較し、前者の方が小さいので、隣接交差点２の道程ｈ＝∞を計算値３に変更する。
【００２６】
ステップ１１２へ進み、中心交差点候補リストＢに現在選択されている隣接交差点が存在するか否かを判別し、存在しなければステップ１１６へ進み、存在すればステップ１１６をスキップする。ステップ１１６では、現在選択されている隣接交差点を中心交差点候補リストＢに追加する。さらにステップ１１８で、この時の中心交差点を現在選択されている隣接交差点の直前交差点Ａとして記録する。
図１２の例では、現在選択されている隣接交差点２はまだ中心交差点候補リストＢに存在しないので、図８（ｂ）に示すリストＢに隣接交差点２の番号を登録し、中心交差点１を現在選択されている隣接交差点２の直前交差点Ａとして、図８（ａ）に示すリストＡの直前交差点Ａの欄に中心交差点１の交差点番号を記録する。
【００２７】
ステップ１２０で、中心交差点に隣接するすべての交差点について上記の検討を行なったか否かを判別し、検討が完了していればステップ１２２へ進み、そうでなければステップ１０６へ戻って上記処理を繰り返す。図８（ａ），（ｂ）は、中心交差点１の隣接交差点２〜５に対して上述した処理が完了した時点のＳ−ＲＡＭ２４の記憶内容を示す。リストＡには各隣接交差点２〜５の道程ｈと直前交差点１が設定され、リストＢには中心交差点候補の交差点２〜５が記録されている。
ステップ１２２では、中心交差点候補リストＢが空か否かを判別し、リストＢに中心交差点候補の交差点が登録されていなければ、ＣＤ−ＲＯＭ１６に記憶されている道路地図の全範囲に対して経路探索が終了したと判断してプログラムの実行を終了し、そうでなければステップ１２４へ進む。なお、通常、予め用意した道路地図の全範囲に対して現在地からの経路探索が終了する前に、目的地が設定されて後述する目的地からの経路探索が開始される。
【００２８】
中心交差点候補リストＢが空でないときは、ステップ１２４でリストＢに登録されている交差点の中から、最小の道程ｈの交差点を新しい中心交差点に決定し、ステップ１２６へ進む。ステップ１２６では、新しく中心交差点に選ばれた交差点をリストＢから消去し、続くステップ１２８で、リストＡのそれまでの中心交差点のフラグに１を設定する。
図１２の例では、図８（ｂ）のリストＢに登録されている隣接交差点２〜５の中で隣接交差点２の道程ｈが最小であり、隣接交差点２を新しい中心交差点に決定し、リストＢの中から交差点２を消去するとともに、リストＡのそれまでの中心交差点１のフラグに１を設定する。その状態におけるＳ−ＲＡＭ２４の記憶内容を図９に示す。
【００２９】
次にステップ１０６へ戻り、新たに選択された中心交差点に対して上記処理を行なう。
図１２の例では、新たに選択された中心交差点２の隣接交差点は交差点１だけであり、ステップ１０８の演算を行なうと、中心交差点２の道程３に中心交差点２から隣接交差点１までの道程３を加算した値６は、隣接交差点１の道程ｈ＝０より大きいので、ステップ１０８が否定されてステップ１２０へ進み、ステップ１１０以下の処理、すなわち隣接交差点１の道程ｈの変更を行なわない。さらにこの場合はステップ１２２〜１２８へと進み、図９（ｂ）に示すリストＢに記録されている交差点３〜５の中から最小の道程ｈを有する交差点４を新しい中心交差点に決定し、リストＢから交差点４を消去するとともに、リストＡのそれまでの中心交差点２のフラグに１を設定する。
【００３０】
次に、新たに選択された中心交差点４に対する経路探索を行ない、中心交差点４に隣接する交差点１，５，６に対して上述した探索処理を行なう。この処理過程におけるＳ−ＲＡＭ２４の記録内容の変化を図１０に示す。
隣接交差点１に対しては、中心交差点４の道程４に中心交差点４から隣接交差点１までの道程４を加算した値８が隣接交差点１の道程０よりも大きいので、道程ｈの変更を行なわない。
隣接交差点５に対しては、中心交差点４の道程４に中心交差点４から隣接交差点５までの道程１を加算した値５が隣接交差点５の道程６よりも小さいので、隣接交差点５の道程ｈを６から５に変更する。なお、この隣接交差点５はすでにリストＢに存在しているのでリストＢへの記録を行なわない。また、隣接交差点５の直前交差点Ａは交差点１から交差点４に変更する。
隣接交差点６に対しては、中心交差点４の道程４に中心交差点４から隣接交差点６までの道程５を加算した値９が隣接交差点６の道程∞よりも小さいので、隣接交差点６の道程を∞から９に変更する。さらに、この隣接交差点６は、リストＢに存在しないのでリストＢに記録するとともに、リストＡの隣接交差点６の直前交差点Ａに交差点４を設定する。
【００３１】
次に、中心交差点候補リストＢに記録されている交差点３，５，６の中から、最小の道程ｈを有する交差点を新しい中心交差点に決定する。このとき、交差点３と交差点５がともに最小の道程３を有しているので、この場合は任意のいずれか一方、ここでは交差点５を中心交差点に選択する。
さらに探索を続けていくと、中心交差点は交差点１→２→４→３→５→６→７と変化してゆく。交差点７を中心交差点として経路探索が終了した時点のＳ−ＲＡＭ２４の記憶内容を図１１に示す。
この実施例では、交差点７を中心交差点として経路探索が終了した時点で、タイマー２６の設定時間が経過して現在地を中心とする無指向性の経路探索が終了したものとする。
【００３２】
図１３〜図１５は目的地から現在地への指向性の経路探索プログラムを示すフローチャート、図１６〜図１９はＳ−ＲＡＭ２２に記憶される経路探索結果を示す図である。これらの図により、図１２に示す交差点ネットワークを例に上げて目的地から現在地への指向性の経路探索を説明する。なお、この目的地から現在地への指向性の経路探索は、Ｓ−ＲＡＭ２４に記憶されている現在地周辺の探索結果を用いる。探索開始に先だってＳ−ＲＡＭ２４に記憶されている探索結果をＤ−ＲＡＭ２２へ転送するとともに、以後、転送された探索結果に目的地から現在地への指向性の探索結果を付加する。図１６〜図１９において、（ａ）および（ｂ）はそれぞれ上述した最適経路リストＡおよび中心交差点候補リストＢである。（ｃ）は目的地周辺の中心交差点候補の交差点を示すリストＣである。
ステップ２００において目的交差点を特定する。この目的交差点は、例えば上述した出発交差点と同様に、目的地周辺の交差点の中から、目的地を中心とする所定半径の円外に存在し、且つ最も目的地に近い交差点を目的交差点として選定する。図１２の例では、交差点１０が目的交差点として選定されたとする。次にステップ２０２へ進み、選定された目的交差点に対するリストＡのフラグが１になっているか、すなわち上述した現在地からの経路探索によってすでに経路探索が終了している交差点か否かを判別し、経路探索が終了している交差点であればステップ２０４へ進み、そうでなければステップ２０６へ進む。
【００３３】
選定された目的交差点がすでに経路探索が終了している交差点の場合は、ステップ２０４で、Ｄ−ＲＡＭ２２に記憶されている最適経路リストＡの目的交差点から直前交差点Ａを順にたどることによって、出発交差点までの最適経路が得られる。
図１２の例で、仮に目的交差点を経路探索が終了している交差点７とすると、図１６に示すように目的交差点７の直前交差点Ａは交差点５であり、交差点５の直前交差点Ａは交差点４であり、交差点４の直前交差点Ａは出発交差点１である。したがって、出発交差点１から目的交差点７までの最適経路は、目的交差点７から直前交差点Ａをたどって得られる交差点５→交差点４→出発交差点１の経路である。
なお、上述した現在地周辺からの経路探索によって道路地図のすべての範囲の探索が終了していれば、どの交差点が目的交差点に設定されても、最適経路リストＡの目的交差点から直前交差点Ａを順にたどることによって、すぐに出発交差点から目的交差点までの最適経路が得られる。
【００３４】
今、目的交差点は経路探索が終了していない交差点１０であるから、ステップ２０２が否定されてステップ２０６へ進む。ステップ２０６で目的交差点を中心交差点に設定してステップ２０８へ進み、図１６に示すように、Ｄ−ＲＡＭ２２に記憶されているリストＡの目的交差点１０の道程ｇに０を設定するとともに、他の交差点の道程ｇに非常に大きな値＋∞を設定する。ここで、道程ｇは目的交差点から任意の交差点までの道程であり、上述した出発交差点から現在地周辺の任意の交差点までの道程ｈに相当する。
ステップ２１０で、中心交差点に隣接する交差点の中からいずれかを選択してステップ２１２へ進み、中心交差点の道程ｇに中心交差点から選択された隣接交差点までの道程を加えた値と、隣接交差点の道程ｇとを比較し、前者が小さい場合はステップ２１４へ進み、そうでなければステップ２３４へ進む。ステップ２１４では、中心交差点の道程ｇに中心交差点から選択された隣接交差点までの道程を加えた値を、隣接交差点の道程ｇに設定する。続くステップ２１６で、現在選択されている隣接交差点の直前交差点Ｂに中心交差点を設定する。
【００３５】
ステップ２０６〜２１６の処理過程を図１２の例で説明すると、中心交差点１０には交差点８，９，１１，１２が隣接しており、これらの隣接交差点の中からまず交差点８を選択する。そして、図１６（ａ）に示すように、中心交差点１０の道程ｇ＝０に中心交差点１０から選択された隣接交差点８までの道程４を加算した値４と、隣接交差点８の道程ｇ＝∞とを比較し、前者の方が小さいので、隣接交差点８の道程ｇを∞から加算値４に変更するとともに、隣接交差点８の直前交差点Ｂに中心交差点１０を設定する。
【００３６】
ステップ２１８において、現在選択されている隣接交差点のリストＡのフラグに１が設定されているか否かを判別する。この隣接交差点のフラグに１が設定されているということは、この隣接交差点に対して現在地周辺からの経路探索が終了し、出発交差点からこの隣接交差点までの最適経路が選定されていることを示す。すなわち、この隣接交差点は上述した接点交差点であり、この時点で目的地からの経路探索が現在地周辺からの経路探索済みの範囲に到達したことを示す。現在選択されている隣接交差点のフラグに１が設定されていればステップ２２２へ進み、フラグが０のままであればステップ２５０へ進む。図１２の例では、中心交差点１０に隣接する交差点８，９，１１，１２のフラグはすべて０であり、ステップ２５０へ進む。
【００３７】
目的地からの経路探索で検索中の隣接交差点が現在地周辺からの経路探索済みの接点交差点でないときは、ステップ２５０で現在選択されている隣接交差点がＤ−ＲＡＭ２２の中心交差点候補リストＣに存在するか否かを判別する。このリストＣは、目的地からの最適経路探索において中心交差点になり得る交差点を登録するリストである。隣接交差点が中心交差点候補リストＣにないときはステップ２５２へ進み、すでに中心交差点候補リストＣにあるときはステップ２５２をスキップする。ステップ２５２で、隣接交差点を中心交差点候補リストＣに追加登録するとともに、出発交差点からその隣接交差点までの直線距離を算出して推測道程ｈ’として記録する。さらに、中心交差点から隣接交差点までの道程ｇを記録する。
図１２の例では、中心交差点１０の隣接交差点８，９，１１，１２は、当初いずれも中心交差点候補リストＣに存在しないので、図１６に示すようにこれらの隣接交差点８，９，１１，１２を中心交差点候補リストＣに記録するとともに、出発交差点から各隣接交差点８，９，１１，１２までの直線距離を算出して推測道程ｈ’として記録する。なお、推測道程ｈ’は出発交差点から検索中の交差点までの直線距離であるから、出発交差点から検索中の交差点までの道程ｈよりも短い。さらにリストＣには、中心交差点１０から各隣接交差点までの道程ｇを記録する。
【００３８】
次にステップ２３４へ進み、中心交差点に隣接するすべての交差点について検討が終了したか否かを判別し、全ての隣接交差点について検討が終了したらステップ２３６へ進む。ステップ２３６では、中心交差点候補リストＣの中から最小の（ｇ＋ｈ’）を有する交差点を新しい中心交差点に選定し、続くステップ２３８で、新たに中心交差点に選定された交差点をリストＣから消去する。
図１２の例では、中心交差点１０に隣接する交差点８，９，１１，１２に対して上記処理が終了したら、図１６（ｃ）に示すように最小の（ｇ＋ｈ’）を有する隣接交差点９を新しい中心交差点に選定し、この交差点９をリストＣから消去する。
【００３９】
一方、ステップ２１８において現在検索中の隣接交差点のフラグに１が設定されている場合、すなわち目的地からの経路探索で検索中の隣接交差点が現在地周辺の経路探索済みの接点交差点である場合は、ステップ２２２へ進む。現在選択されている隣接交差点は接点交差点であるから、出発交差点からの最小道程ｈの最適経路が探索されており、ステップ２２２で、この隣接交差点の道程ｇと道程ｈの和（ｇ＋ｈ）が出発交差点の道程ｇよりも小さいか否かを判別し、小さければステップ２２４へ進み、そうでなければステップ２３４へ進む。ステップ２２４では、出発交差点の道程ｇを隣接交差点の道程ｇとｈの和（ｇ＋ｈ）に変更する。上述したように、出発交差点の道程ｇは出発交差点から目的交差点までの道程を示す。続くステップ２２６で、リストＡの出発交差点の直前交差点Ｂに現在検索中の隣接交差点を設定する。出発交差点と現在検索中の隣接交差点との間には他の交差点が存在するが、現在検索中の隣接交差点は接点交差点であり、出発交差点からの最適経路が確定しているので、経路途中に存在する他の交差点を省略して出発交差点の直前交差点として現在検索中の隣接交差点を設定する。
【００４０】
図１２の例では、新しい中心交差点９の隣接交差点７，８，１０，１２に対してステップ２１０，２１２を実行すると、隣接交差点７以外はステップ２１２が否定される。中心交差点９の隣接交差点７の場合は、ステップ２１４へ進み、図１７に示すように隣接交差点７のリストＡの道程ｇが、∞から中心交差点９のｇ＝２と中心交差点９から隣接交差点７までの道程４との和６に変更される。また、隣接交差点７の直前交差点Ｂとして中心交差点９が設定される。さらに、隣接交差点７のフラグに１が設定されているので隣接交差点７は接点交差点となり、ステップ２１８が肯定されてステップ２２２へ進む。そして、隣接交差点７の道程ｇと道程ｈとの和（ｇ＋ｈ）が出発交差点１の道程ｇと比較され、前者が小さいので、図１７に示すように出発交差点１のｇ＝∞が隣接交差点７のｇ＝６とｈ＝１０との和１６に変更される。そして、出発交差点１の直前交差点Ｂに隣接交差点７が設定される。
【００４１】
ステップ２２８で、出発交差点が中心交差点候補リストＣに存在するか否かを判別し、すでにリストＣに出発交差点が存在すればステップ２３０をスキップし、なければステップ２３０を実行する。ステップ２３０で、リストＣに出発交差点とその道程ｇおよび（ｇ＋Ｋ・ｈ’）を記録する。
図１２の例では、図１７（ｃ）に示すようにリストＣに出発交差点１とその道程ｇ＝１６が記録されるとともに、出発交差点の道程ｈ’は０であるから（ｇ＋Ｋ・ｈ’）に１６（Ｋ＝１）が記録される。
【００４２】
その後、ステップ２３４〜２３８を実行し、上記の処理を行なう。図１２に例では、図１７（ｃ）に示すリストＣの中心交差点候補の中から最小の（ｇ＋Ｋ・ｈ’）の交差点８が次の中心交差点として選定され、リストＣから中心交差点に選定された交差点８が消去される。
ステップ２４０では、新しく選定された中心交差点が出発交差点であるか否かを判別し、新しい中心交差点が出発交差点であれば目的地からの経路探索が終了したと判断してステップ２４２へ進み、そうでなければステップ２１０へ戻り、新しい中心交差点に対する上記処理を続ける。図１２の例では、新しい中心交差点８の隣接交差点６，９，１０に対して上記処理が行なわれる。
【００４３】
中心交差点８の隣接交差点６，９，１０の内の交差点９，１０に対しては、ステップ２１２が否定されて道程ｇは変更されない。しかし、隣接交差点６の道程ｇ＝∞は、中心交差点８の道程ｇ＝４と中心交差点８から隣接交差点６までの道程２との和６よりも大きいので、図１８（ａ）に示すように、隣接交差点６の道程ｇは∞から６に変更され、また、隣接交差点６の直前交差点Ｂに中心交差点８が設定される。さらに、隣接交差点６のリストＡのフラグは１に設定されているので、ステップ２２２〜２３０の処理が実行される。まず、隣接交差点６のｇ＝６と、現在地周辺の経路探索において算出された道程ｈ＝９との和１５は出発交差点１のｇ＝１６より小さいので、図１８（ａ）に示すように、出発交差点のｇ＝１６を１５に変更するとともに、現在設定されている出発交差点１の直前交差点Ｂを検索中の隣接交差点６に変更する。
【００４４】
ここで、出発交差点における道程ｇと直前交差点Ｂの変更は、目的交差点から出発交差点に至る最適経路が新たに発見されたことを意味する。図１２に示す例では、当初、設定された出発交差点１の道程ｇ＝１６と直前交差点Ｂ＝７は、目的交差点１０から交差点７を経由して出発交差点１へ至る経路とその経路の道程ｇが１６であることを示しており、道程ｇが１５へ直前交差点Ｂが６へそれぞれ変更されたということは、当初の設定経路よりも道程ｇが小さい、より最適な経路、すなわち目的交差点１０から交差点６を経由して出発交差点１へ至る経路が発見されたことを意味する。図１８はこの時のＤ−ＲＡＭ２２の記憶状態を示す。
【００４５】
図１２の例では、図１８に示す探索段階で新しい中心交差点に交差点１２が選定される。この新しい中心交差点１２は出発交差点ではないので、ふたたびステップ２１０以降が実行され、図１９に示すようにリストＣに中心交差点候補の交差点１３が登録され、リストＡの隣接交差点１３の道程ｇおよび直前交差点Ｂが設定される。
【００４６】
ステップ２４０において、新しく選定された中心交差点が出発交差点となった場合は、目的交差点から出発交差点までの最適経路の探索が終了したと判断してステップ２４２へ進む。ステップ２４２で、出発交差点の直前交差点Ｂを、接点交差点に設定する。図１２の例では、出発交差点１の直前交差点Ｂに設定されている交差点６を接点交差点として設定する。
【００４７】
ステップ２４４で、リストＡに記録されている接点交差点から直前交差点Ａをたどり、接点交差点から出発交差点までの交差点列Ａを求める。図１２の例では、図１９のリストＡに示すように、接点交差点６の直前交差点Ａは交差点４であり、さらに交差点４の直前交差点Ａは出発交差点１であるから、交差点列Ａは６→４→１となる。さらにステップ２４６で、リストＡに記録されている接点交差点から直前交差点Ｂをたどり、接点交差点から目的交差点までの交差点列Ｂを求める。図１２に示す例では、図１９のリストＡに示すように、接点交差点６の直前交差点Ｂは８であり、さらに交差点８の直前交差点Ｂは目的交差点１０であるから、交差点列Ｂは６→８→１０となる。ステップ２４８において、交差点列Ａと交差点列Ｂとを組合せ、出発交差点から目的交差点までの経路を求める。つまり、この経路が現在地から目的地までの最適経路である。図１２の例では、交差点列Ａ，Ｂを組合せて１→４→６→８→１０の経路を得ることができ、この経路が現在地から目的地までの最適経路である。
【００４８】
この実施例では、現在地から目的地までの最適経路の探索を、目的地を設定した時点の時間的な余裕、すなわち目的地設定後から出発までの待ち時間に応じて３つのケースに分類する。第１のケースは、時間的な余裕が全くなく、目的地を設定したらすぐに出発しなければならず、経路探索のための待ち時間がほとんどない場合である。また、第２のケースは、目的地を設定した時点でわずかな時間の余裕があり、経路探索のためのわずかな待ち時間が許される場合である。そして、第３のケースは、目的地を設定した時点で十分な時間の余裕があり、経路探索のための十分な待ち時間がある場合である。
【００４９】
（１）第１のケース
図２０は、第１のケースにおける経路探索方法を説明する図である。
設定された目的地が無指向性の経路探索が終了している第１領域内にあれば、目的地近傍の交差点から直前交差点Ａを順にたどっていくと出発交差点Ｄに到達し、現在地から目的地までの最適経路が瞬時に得られる。
しかし、図２０に示すように目的地が第１領域内にはなく、しかもすぐに出発したい場合は以下の手順で経路探索を行なう。
この経路探索は乗員が目的地を設定してからすぐに出発する場合に行なう経路探索であり、上述した無指向性の経路探索結果を利用して目的地までの最適経路を探索する。
まず、図２０に示すように、現在地周辺の経路探索で探索が終了している第１領域の最外周の交差点の中から、目的地までの距離ｆが最短の交差点を途中通過交差点Ｔに選定する。なお、第１領域の最外周にある交差点は中心交差点候補に上がっている交差点とする。厳密には、中心交差点候補に上がっている交差点は出発交差点Ｄまでの最適経路が確定していないので、出発交差点Ｄまでの経路は最短経路でなくなる可能性がある。しかし、もともとこの第１のケースにおける経路探索自体が現在地から目的地までの探索経路の最短性を保証するものではないので、出発交差点Ｄから途中通過交差点Ｔまでの経路が最短経路でなくても、その誤差はこの第１のケースによる現在地から目的地までの探索経路の最短経路に対する誤差に比べればわずかである。したがって、中心交差点候補に上がっている交差点を第１領域の最外周の交差点としても問題はない。
【００５０】
次に、経路探索結果から、出発交差点Ｄから途中通過交差点Ｔまでの経路を読み出す。上述したように、この途中通過交差点Ｔは中心交差点ではないので、直前交差点Ａをたどって出発交差点Ｄまでの経路を探索できない。そこで、途中通過交差点Ｔの隣接交差点の内の中心交差点であるものを抽出し、それを途中通過交差点Ｔの直前交差点Ａとする。途中通過交差点Ｔの隣接交差点の中には、最低１つくらいは中心交差点がある。また、複数個の中心交差点がある場合は、中心交差点の道程ｈとその中心交差点から途中通過交差点Ｔまでの道程が最小の中心交差点を途中通過交差点Ｔの直前交差点Ａとすればよい。このようにして途中通過交差点Ｔの直前交差点Ａを選定した後は、直前交差点Ａを順にたどっていけば出発交差点Ｄまでの経路▲１▼が得られる。
【００５１】
現在地から途中通過交差点Ｔまでの経路▲１▼が求められると、車両周辺の道路地図上に経路▲１▼を表示して乗員の誘導を開始する。経路▲１▼の算出時間はほとんど瞬時であるから、乗員は目的地を設定してからすぐに経路▲１▼に沿って出発することができる。
その後、車両が途中通過交差点Ｔに到達するまでの間に、目的地から途中通過交差点Ｔまでの経路▲２▼を算出し、道路地図上に経路▲２▼を表示して途中通過交差点Ｔから目的地まで乗員を誘導する。これらの経路▲１▼＋経路▲２▼は、現在地から目的地まで通して演算したものではないから、経路の最短性は保証されない。
【００５２】
経路▲２▼の探索は、目的地から途中通過交差点Ｔに向って指向性係数Ｋ＝１の経路探索を行なう。この経路探索では、目的地が設定されると目的地から途中通過交差点Ｔに向って経路探索を開始し、目的交差点Ｓから中心交差点Ｃまでの道程ｇと中心交差点Ｃから途中通過交差点Ｔまでの推測道程ｈ’との和（ｇ＋ｈ’）が最小の交差点を順次検索していき、中心交差点Ｃが途中通過交差点Ｔに達したら経路探索を終了する。
図２１は、目的地から途中通過交差点Ｔへの指向性の経路探索における第３の探索領域を示す。この第３領域は、目的地から出発地への指向性の経路探索における図４に示す第２領域に比べて狭く、その分だけ検索する交差点数が少なくなって探索時間が短縮される。しかし反面、目的交差点Ｓから出発交差点Ｄまでの経路をすべて探索していないので、最終的に選定された経路以外にも最適な経路が存在する可能性があり、経路の最短性は保証されない。
【００５３】
図２２，２３は、目的地から途中通過交差点Ｔまでの最適経路探索プログラムを示すフローチャートである。なお、上述した目的地から出発地までの経路探索プログラムを示す図１３〜図１５と同様な処理を行なうステップに対しては同一のステップ番号を付して相違点を中心に説明する。また、図２４〜２７はＤ−ＲＡＭ２２に記憶される目的地から途中通過交差点Ｔまでの経路探索結果を示す図である。これらの図により、図１２に示す交差点ネットワークを例に上げて目的地から途中通過交差点Ｔまでの指向性の経路探索を説明する。
ステップ２００〜２１６，ステップ２５０〜２３８を実行し、中心交差点に隣接する交差点に対して上述した処理を行なった後、（ｇ＋Ｋ・ｈ’）（ここではＫ＝１）が最小の交差点を新しい中心交差点に選定する。
ステップ３０１Ａにおいて、新たに選定した中心交差点が途中通過交差点Ｔであるか否かを判別する。途中通過交差点Ｔであればステップ３０２へ進み、そうでなければステップ２１０へ戻る。ステップ３０２Ａでは、Ｄ−ＲＡＭ２２に記憶されているリストＡから、途中通過交差点Ｔである中心交差点の直前交差点Ｂをたどって目的交差点Ｓまでの経路▲２▼を求める。
【００５４】
図１２に示す交差点ネットワークを例に上げて目的地から途中通過交差点Ｔまでの経路探索を説明する。
今、目的地が設定される前の現在地を中心とする無指向性の経路探索により、交差点７までの最適経路が探索され、目的地の設定後に上述した経路▲１▼の探索により交差点７が途中通過交差点Ｔに選定されているとする。
目的地周辺の交差点１０が目的交差点に設定されると、まず目的交差点１０が中心交差点となり、隣接交差点８，９，１１，１２に対して上述した検索が行なわれ、Ｄ−ＲＡＭ２２に図２４に示す経路探索結果が記憶される。この状態で、リストＣの中心交差点候補の中から、最小の道程（ｇ＋ｈ’）＝１２を持つ交差点９が次の中心交差点に選定される。
【００５５】
新たに選定された中心交差点９の隣接交差点７，８，１０，１２に対して上記探索を行なうと、図２５に示す経路探索結果が得られ、交差点８が次の新しい中心交差点に選定される。この中心交差点８の隣接交差点６，９，１０に対して上記探索を行なうと、図２６に示す経路探索結果が得られ、交差点１２がつぎの新しい中心交差点に選定される。そして、この中心交差点１２の隣接交差点９，１０，１３に対して上記探索を行なうと、図２７の経路探索結果が得られ、交差点７が次の新しい中心交差点に選定される。
【００５６】
新たに中心交差点に選定された交差点７は途中通過交差点Ｔに選定されており、この交差点７はすでに現在地からの経路探索によって現在地までの最適経路が探索されている。したがって、図２３のステップ３０１が肯定され、この時点で目的地からの経路探索が終了する。そして、接点交差点７の直前交差点Ｂをたどって経路７→９→１０が得られる。この経路が目的交差点Ｓから途中通過交差点Ｔまでの経路▲２▼である。
出発時点では経路▲１▼を表示し、経路▲２▼が探索されたら経路▲１▼＋▲２▼を表示して乗員を目的地まで誘導する。
なお、上述した目的地から出発地までの経路探索を行なうと、図１９に示すように道程１５の１→４→６→８→１０の経路が得られた。目的地から途中通過交差点Ｔまでの経路▲２▼と、出発交差点Ｄから途中通過交差点Ｔまでの経路▲１▼との接続経路１→４→５→７→９→１０は、その道程が図２７に示すように交差点７の道程ｈ＝１０と道程ｇ＝６との合計値１６であるから、現在地から目的地までの最短経路ではなく、経路探索は不十分で他に最適な経路が存在するにもかかわらずそれを探索できなかったことになる。しかし、このような第１のケースにおける経路探索では、指向性が強いので探索領域が上述した目的地から出発地までの探索領域に比べて狭く、検索交差点数が少ない分だけ探索時間が短縮される。
【００５７】
（２）第２のケース
図２８は第２のケースにおける現在地から目的地までの経路探索を示す図である。
目的地を設定した時点でわずかな時間の余裕があり、経路探索のためのわずかな待ち時間が許される場合は、上述した現在地周辺の無指向性の探索結果を用いて目的地から出発地へのＫ＞１の超指向性探索を行なう。この超指向性探索は、上述した目的地から出発地への指向性探索と指向性係数Ｋの値が異なる以外は同様であり、説明を省略する。この目的地から出発地への超指向性探索による第４の探索領域は、上述した図４に示す指向性探索による第２領域よりも狭く、その分だけ検索交差点数が少ないので探索時間が短縮されるが、経路の最短性は保証されない。
この超指向性の経路探索により出発地から目的地までの経路▲３▼が得られたら、道路地図上に経路▲３▼を表示して乗員の誘導を開始する。これにより、乗員はわずかな待ち時間で上述した第１のケースの場合よりも最短性の高い誘導経路に沿って目的地へ出発することができる。
【００５８】
（３）第３のケース
図２９は第３のケースにおける現在地から目的地までの経路探索方法を説明する図である。
目的地を設定した時点で十分な時間の余裕があり、経路探索のための十分な待ち時間が許される場合は、上述した現在地周辺の無指向性の探索結果を用いて、上述した目的地から出発地へのＫ≦１の指向性探索を行なう。この目的地から出発地への指向性探索による第２の探索領域は、上述した図２８に示す超指向性探索による第４領域よりも広く、第４領域内では探索されなかった最小道程の経路▲４▼が探索されるが、その分、待ち時間が長くなる。
この目的地から出発地への指向性探索により経路▲４▼が求められたら、道路地図上に経路▲４▼を表示して乗員の誘導を開始する。これにより、乗員は上述した最短性の保証された誘導経路に沿って目的地へ出発することができる。
【００５９】
図３０、図３１はメイン制御プログラムを示すフローチャート、図３２はタイムアップ割り込みルーチンを示すフローチャート、図３３は目的地設定割り込みルーチンを示すフローチャートである。これらのフローチャートにより、実施例の全体動作を説明する。
イグニッションスイッチ１０２がオンされて経路誘導装置１００に電源が投入されると、ＣＰＵ１は図３０に示すＩＧＮ  ＯＮプログラムを実行する。ステップ１において車両が停車中か否かを判別する。車両が停車中か否かは車速センサ７から入力されるパルス信号に基づいて判別し、完全な停車でなくても所定速度以下の略停車中であれば停車と見なしてもよい。停車中であればステップ２へ進み、そうでなければ処理を終了する。
車両が停車中の時は、ステップ２で上述したように車両の現在地を検出する。続くステップ３において、上述した図６、図７に示す現在地周辺の各交差点までの最適経路探索プログラムを実行し、現在地を中心とする無指向性の経路探索を行なう。この時、同じ現在地においてイグニッションがオフされた時にすでに途中まで経路探索が行なわれていた場合は、Ｓ−ＲＡＭ２４に記憶されている探索結果をＤ−ＲＡＭ２２へ転送するとともに、未探索部分から探索を開始する。なお、この現在地周辺の経路探索は後述する目的地設定割り込みがかかるまで行なわれる。
【００６０】
イグニッションスイッチ１０２がオフされると、ＣＰＵ１は図３１に示すＩＧＮ  ＯＦＦプログラムを実行する。ステップ１１でタイマー２６をスタートしてステップ１２へ進み、車両の現在地を検出する。続くステップ１３で、上述した図６、図７に示す現在地周辺の各交差点までの最適経路探索プログラムを実行し、現在地を中心とする無指向性の経路探索を行なう。なお、この現在地周辺の経路探索は後述するタイマー割り込みがかかるまで行なわれる。
【００６１】
イグニッションオフ後にタイマー２６がタイムアップするとタイムアップ割り込みが発生し、ＣＰＵ１は図３２に示すタイムアップ割り込みルーチンを実行する。ステップ２１で、イグニッションオフ後に開始した現在地を中心とする無指向性探索を終了する。
【００６２】
乗員により目的地が設定されると目的地設定割り込みが発生し、ＣＰＵ１は図３３に示す目的地設定割り込みルーチンを実行する。ステップ３１において、車両の停車中に開始された現在地周辺の経路探索を終了させる。続くステップ３２で、乗員により上述した第１〜第３のケースの内のどのケースが選択されたかを判別する。キー８に中には第１〜第３のケースを選択するための不図示のセレクタースイッチが設けられており、そのセレクタースイッチの設定に応じて以後の処理を行なう。
【００６３】
第１のケースが選択された時、すなわち、時間的な余裕が全くなく、目的地を設定したらすぐに出発したい時はステップ３３へ進み、経路探索のための待ち時間がほとんどないので、上述したように取り敢えず経路▲１▼の探索を行なう。ここで、設定された目的地が経路探索が終了している第１領域内にあれば、目的地近くの目的交差点から直前交差点Ａを順にたどり出発交差点Ｄから目的交差点Ｓまでの完全な最短経路▲１▼が瞬時に得られる。一方、目的地が第１領域内にない場合は、上述したように途中通過交差点Ｔを選定し、出発交差点Ｄから途中通過交差点Ｔまでの経路▲１▼を探索する。
ステップ３４で、現在地周辺の道路地図上に探索した経路▲１▼を表示して乗員の誘導を開始する。経路▲１▼の算出時間はほとんど瞬時であるから、乗員は目的地を設定してからすぐに経路▲１▼に沿って出発することができる。続くステップ３５で、上述したように途中通過交差点Ｔから目的地までの経路▲２▼を探索する。そしてステップ３７で、経路▲１▼と経路▲２▼を連結して現在地周辺の道路地図上に表示する。ステップ３８で車両が目的地へ到着したか否かを判別し、目的地へ到着したら誘導処理を終了する。
【００６４】
一方、第２のケースが選択された時、すなわち、目的地を設定した時点でわずかな時間の余裕がある時はステップ３９へ進み、経路探索のためのわずかな待ち時間が許されるので、上述したように現在地周辺の無指向性の探索結果を用いて目的地から出発地への超指向性探索を行ない、経路▲３▼を求める。続くステップ４０で、現在地周辺の道路地図上に探索された経路▲３▼を表示して乗員の誘導を開始する。乗員はわずかな待ち時間で第１のケースよりも最短性の高い経路▲３▼に沿って目的地へ出発することができる。ステップ４１で車両が目的地へ到着したか否かを判別し、目的地へ到着したら経路誘導処理を終了する。
【００６５】
さらに、第３のケースが選択された時、すなわち、目的地を設定した時点で十分な時間の余裕がある時は、ステップ４２へ進み、経路探索のための十分な待ち時間があるので、上述したように現在地周辺の無指向性の探索結果を用いて目的地から出発地への指向性探索を行ない、経路▲４▼を求める。続くステップ４３で、現在地周辺の道路地図上に探索された経路▲４▼を表示して乗員の誘導を開始する。乗員は最短性の保証された経路▲４▼に沿って目的地へ出発することができる。ステップ４４で車両が目的地へ到着したか否かを判別し、目的地へ到着したら経路誘導処理を終了する。
【００６６】
このように、現在地から目的地までの最適経路の探索を、目的地を設定した時点の時間的な余裕にしたがって３つのケースに分類する。
第１のケースは、時間的な余裕が全くなく、目的地を設定したらすぐに出発しなければならず、経路探索のための待ち時間がほとんどない場合である。この場合は、現在地周辺の探索済みの交差点の中から目的地に最も近い交差点を途中通過交差点Ｔに選定し、現在地周辺の経路探索結果に基づいて現在地から途中通過交差点Ｔまでの経路▲１▼を探索する。次に、目的地から途中通過交差点までの指向性の経路探索により経路▲２▼を探索し、経路▲１▼と経路▲２▼に沿って乗員を誘導する。このケースによる探索は、探索経路の最短性は保証されないが最短時間で探索が終了し、目的地設定後にすぐに経路▲１▼を表示して乗員の誘導を開始することができる。
第２のケースは、目的地を設定した時点でわずかな時間の余裕があり、経路探索のためのわずかな待ち時間が許される場合である。この場合は、現在地周辺の探索結果に基づいて目的地から現在地への超指向性の経路探索により経路▲３▼を探索する。このケースによる探索では、第１のケースよりも最短性の高い経路がわずかな待ち時間で得られる。
第３のケースは、目的地を設定した時点で十分な時間の余裕があり、経路探索のための十分な待ち時間がある場合である。この場合は、現在地周辺の探索結果に基づいて目的地から現在地への指向性の経路探索により経路▲４▼を探索する。このケースによる探索では、探索時間はかかるが最も最短性の高い経路が得られる。
そして、車両の停車中に現在地を中心とする無指向性の経路探索を行なうとともに、目的地設定後に第１〜第３のケースの内の乗員により選択されたケースにより現在地から目的地への最適経路を探索し、道路地図上に最適経路を表示して乗員を目的地へ誘導するようにしたので、目的地設定時点における時間的な余裕に応じた最適な経路探索を選択することができ、乗員の要望に的確に応えることができる。
【００６７】
−実施例の変形例−
上述した実施例では、目的地の設定後に乗員が第１〜第３のケースの内のいずれかを手動で選択し、選択されたケースの経路探索を行なうようにしたが、目的地設定後の出発待ち時間に応じて自動的に第１〜第３のケースを選択する上記実施例の変形例を説明する。
図３４、図３５は目的地設定割り込みルーチンの変形例を示すフローチャートである。このフローチャートにより、目的地設定後の経路探索動作を説明する。なお、目的地設定後の経路探索以外の構成と動作については上述した実施例と同様であり、説明を省略する。
乗員により目的地が設定されると目的地設定割り込みが発生し、ＣＰＵ１は図３４、図３５に示す目的地設定割り込みルーチンを実行する。ステップ５１において、車両の停車中に開始された現在地周辺の経路探索を終了させる。続くステップ５２で、乗員がすぐに出発するかも知れないので取り敢えず上述した第１のケースの経路▲１▼の探索を行なう。ここで、設定された目的地が経路探索が終了している第１領域内にあれば、目的地近くの目的交差点から直前交差点Ａを順にたどり出発交差点Ｄから目的交差点Ｓまでの完全な最短経路▲１▼が瞬時に得られる。一方、目的地が第１領域内にない場合は、上述したように途中通過交差点Ｔを選定し、出発交差点Ｄから途中通過交差点Ｔまでの経路▲１▼を探索する。ステップ５３で、現在地周辺の道路地図上に探索された出発地から途中通過交差点Ｔまでの経路▲１▼を表示する。この状態において、乗員は経路▲１▼に沿って出発することができる。
【００６８】
ステップ５４で車両が停車中か否かを判別する。車両の停車中は上述した判定方法で行なえばよいが、逆に車両の走行状態を検出し、走行状態でなければ停車中であるとしてもよい。停車中でなければステップ５５へ進み、停車中であればステップ６１へ進む。
経路▲１▼を表示した直後に車両が走行状態に移行した時は、乗員が急いで出発しなければならず、より最短の経路を探索している時間がない時であるから、ステップ５５で、上述したように途中通過交差点Ｔから目的地までの経路▲２▼を探索する。そしてステップ５７で、経路▲１▼と経路▲２▼を連結して現在地周辺の道路地図上に表示する。ステップ５８で車両が目的地へ到着したか否かを判別し、目的地へ到着したら誘導処理を終了する。
【００６９】
一方、ＣＲＴ１８に第１のケースの経路▲１▼を表示した時点で停車中の場合は、ステップ６１で、第１のケースによる経路探索よりも最短な経路が探索できる第２のケースによる経路▲３▼の探索を開始する。続くステップ６２で停車中か否かを判別し、経路▲３▼の探索中に車両が走行状態に移行したら探索を中止してステップ５５へ進む。この状態ではＣＲＴ１８に第１のケースによる経路▲１▼が表示されており、ステップ５５で、第１のケースの経路▲２▼の探索を行ない、上述したように第１のケースの経路▲１▼と経路▲２▼による乗員の誘導を行なう。
ステップ６３で第２のケースの経路▲３▼の探索が終了したか否かを判別し、探索が終了していなければステップ６２へ戻る。停車中の間に経路▲３▼の探索が終了したらステップ６４へ進み、車両周辺の道路地図上に探索した経路▲３▼を表示する。これ以後に乗員が出発した時は、第１のケースよりも最短である可能性が高い第２のケースによる経路▲３▼に沿って目的地へ出発できる。
ステップ６５で停車中か否かを判別し、走行状態に移行していれば第２のケースの経路▲３▼による誘導に決定し、ステップ６６へ進む。ステップ６６で目的地へ到着したか否かを判別し、目的地へ到着するまでステップ６７を実行して現在地周辺の道路地図上に経路▲３▼を表示する。
【００７０】
また、ＣＲＴ１８に第２のケースの経路▲３▼を表示した時点でも車両が停車中の場合は、ステップ７１で、第２のケースによる経路探索よりも最短な経路が探索できる第３のケースによる経路▲４▼の探索を開始する。続くステップ７２で停車中か否かを判別する。経路▲４▼の探索中に走行状態に移行した時は、乗員にはこれ以上の経路探索のための待ち時間がなく、すぐに出発しなければならないと判断してステップ６６へ進む。この状態では、ＣＲＴ１８に第２のケースによる経路▲３▼が表示されているので、上述したようにステップ６６、６７で目的地へ到着するまで第２のケースの経路▲３▼による乗員の誘導を行なう。
ステップ７３で第３のケースの経路▲４▼の探索が終了したか否かを判別し、終了していなければステップ７２へ戻り、終了したらステップ７４へ進む。停車中に第３のケースの経路▲４▼の探索が終了した時は、ステップ７４で、車両周辺の道路地図上に探索した経路▲４▼を表示してステップ７５へ進み、目的地へ到着するまでステップ７４を実行して第３のケースの経路▲４▼による乗員の誘導を行なう。
【００７１】
このように、車両の停車中に現在地を中心とする無指向性の経路探索を行なうとともに、目的地設定後の出発待ち時間に応じて自動的に第１〜第３のケースを選択する。まず、目的地設定後に取り敢えず第１ケースによる経路▲１▼の探索を行なって道路地図上に表示するようにしたので、この段階で時間的な余裕がほどんどない乗員は経路▲１▼に沿ってすぐに出発することができる。
経路▲１▼を表示した時点に停車中であれば第２のケースによる経路▲３▼の探索を開始し、経路▲３▼の探索中に車両が走行状態に移行した時は経路▲３▼の探索を中止するとともに第１のケースによる経路▲２▼の探索を行なって道路地図上に経路▲１▼と経路▲２▼を表示するようにしたので、目的地設定後に乗員を経路▲１▼に沿ってすぐに出発させることができ、途中から経路▲２▼に沿って目的地まで誘導できる。
また、停車中に第２のケースの経路▲３▼の探索が終了したら道路地図上に経路▲３▼を表示するようにしたので、わずかな待ち時間で第１のケースの経路▲１▼＋▲２▼よりも最短である可能性が高い経路▲３▼に沿って乗員を目的地まで誘導できる。
さらに、経路▲３▼を表示した時点に停車中であれば第３のケースによる経路▲４▼の探索を開始し、停車中に経路▲４▼の探索が終了したら経路▲４▼を道路地図上に表示するようにしたので、時間の余裕があれば最も最短である可能性が高い経路▲４▼に沿って乗員を目的地まで誘導できる。
【００７２】
なお、上述した実施例では交差点を中心に経路探索を行なう例を示したが、道路の屈曲点や、道路と地域メッシュの区画線との交点を含めて経路探索を行なうようにしてもよい。
また、上述した各実施例では最小道程の経路を最適経路としたが、所要走行時間が最小の経路を最適経路としてもよい。この場合は、交差点間の距離と走行速度により所要走行時間を算出しなければならないが、実際の走行速度を予め特定することは困難であるから、走行速度の代りにその交差点間の制限速度を用いて所要走行時間を算出すればよい。またこの場合、目的地からの経路探索における検索中の交差点から出発交差点までの推測所要走行時間は、その交差点から出発交差点までの直線距離と、その間の考えられる最高速度により算出する。この考えられる最高速度は、検索中の交差点から出発交差点までの間の考えられる経路の中で、考えられる最高の走行速度とする。例えば、経路上に１００ｍ／ｈの高速道路があれば最高走行速度を１００ｍ／ｈとする。
【００７３】
以上の実施例の構成において、ＣＤ−ＲＯＭ１６が道路地図記憶手段を、ＣＰＵ１方位センサ３、車速センサ７およびＧＰＳレシーバ１２が現在地検出手段を、キー８が目的地設定手段および選択手段を、ＣＰＵ１および車速センサ７が停車検出手段を、ＣＰＵ１が現在地周辺探索手段、経路探索手段、選択手段、第１の経路探索手段、交差点抽出手段、第２の経路探索手段、第３の経路探索手段および第４の経路探索手段を、ＣＲＴ１８が表示手段をそれぞれ構成する。
【００７４】
【発明の効果】
以上説明したように請求項１の発明によれば、車両の停車状態が検出されている時に道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索するとともに、目的地の設定後に出発までの待ち時間に応じた経路探索手段を選択し、その経路探索手段によって現在地周辺の探索結果に基づいて目的地から現在地への最適経路を探索する。そして、道路地図上に選択された経路探索手段の探索結果の最適経路を表示するようにしたので、目的地設定時点における時間的な余裕と経路の最短性や所要走行時間に応じた最適な経路探索方法を選択することができ、乗員の要望に的確に応えることができる。
請求項２の発明によれば、複数の経路探索手段の中から目的地設定後から出発までの待ち時間に応じた経路探索手段を手動で選択するようにしたので、待ち時間に応じて任意の経路探索方法を選択することができる。
請求項３の発明によれば、複数の経路探索手段の中から目的地設定後から出発までの待ち時間に応じて自動的に経路探索手段を選択するようにしたので、目的地設定時点における時間的な余裕と経路の最短性や所要走行時間に応じた最適な経路が探索される。
請求項４の発明によれば、複数の経路探索手段の中から目的地から現在地への指向性の強い順に経路探索手段を選択するようにしたので、すぐに出発したい乗員から時間的な余裕のある乗員まで、目的地設定時点における時間的な余裕に応じたそれぞれの乗員に最適な経路探索方法を提供できる。
請求項５の発明によれば、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたので、経路選択時の指向性を任意に設定でき、経路探索における探索時間と経路の最短性または所要走行時間とをバランスしたそれぞれの乗員に最適な探索方法を提供できる。
請求項６の発明によれば、複数の経路探索手段に指向性の強さＫが１以下の経路探索手段と指向性の強さＫが１よりも大きい経路探索手段とを含むようにしたので、Ｋが１以下の経路探索手段によって探索時間はかかるが最短経路または最小所要時間経路が探索され、Ｋが１よりも大きな経路探索手段によって探索経路の最短性と所要時間は犠牲になるがわずかな時間で経路が探索され、すぐに出発したい乗員から時間的な余裕のある乗員まで、目的地設定時点における時間的な余裕に応じたそれぞれの乗員に最適な経路探索方法を提供できる。
請求項７の発明によれば、まず、車両の停車状態が検出されている時に、道路地図に基づいて現在地からその周辺の各交差点へ至る最適経路を探索する。次に目的地が設定されると、現在地からの最適経路が探索された交差点の中から目的地に最も近い交差点を抽出し、現在地周辺の最適経路の探索結果に基づいて現在地から抽出された交差点までの最適経路を探索する。そして、道路地図を表示するとともに、その道路地図上に探索された現在地から抽出交差点までの最適経路を表示するようにしたので、目的地設定後すぐに出発したい乗員に対しては、速やかに経路を表示して誘導を開始することができる。
請求項８の発明によれば、目的地から抽出された交差点までの最適経路を探索し、道路地図上に探索された現在地から抽出交差点までの最適経路と目的地から抽出交差点までの最適経路とを表示するようにしたので、目的地設定後すぐに出発したい乗員に対しては、速やかに現在地から抽出交差点までの経路を表示して誘導を開始することができる上に、その後さらに抽出交差点から目的地までの経路を表示して目的地まで乗員を誘導することができる。
請求項９の発明によれば、前記第２の経路探索手段により探索された最適経路が表示された時点に車両の停車状態が検出されると、現在地周辺の最適経路の探索結果に基づいて目的地から現在地までの最適経路を探索し、その最適経路の探索が車両の停車状態が検出されている間に終了したら、探索結果の最適経路を道路地図上に表示するようにしたので、現在地から抽出交差点までの経路と抽出交差点から目的地までの経路との合算経路に比べて現在地から目的地まで通して演算されたより最適な経路が探索でき、わずかな出発待ち時間でそのような最適な経路を表示して乗員を誘導できる。
請求項１０の発明によれば、前記第３の経路探索手段は目的地から現在地への指向性の強い探索を行なうようにしたので、探索領域が狭くなり、その分だけ検索交差点数が少なくなって経路探索時間が短縮できる。
請求項１１の発明によれば、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、前記第３の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたので、経路選択時の指向性を任意に設定でき、経路探索における探索時間と経路の最短性または所要走行時間とをバランスした最適な探索方法を提供できる。
請求項１２の発明によれば、第３の経路探索手段の指向性の強さＫを１よりも大きな値としたので、わずかな出発待ち時間しかない乗員に最適な経路探索方法を提供でき、探索経路の最短性と所要時間は犠牲になるがわずかな時間で経路が探索される。
請求項１３の発明によれば、前記第３の経路探索手段により探索された最適経路が道路地図上に表示された時点に車両の停車状態が検出されると、現在地周辺の最適経路の探索結果に基づいて前記第３の経路探索手段よりも弱い指向性で目的地から現在地までの最適経路を探索し、その最適経路の探索が車両の停車状態が検出されている間に終了したら、探索結果の最適経路を道路地図上に表示するようにしたので、十分な出発待ち時間がある乗員に対しては最短な経路または最小所要時間の経路を提供できる。
請求項１４の発明によれば、目的地から現在地への指向性の強さをＫで表わし、目的地から検索中の交差点までの道程をｇで表わし、その検索中の交差点から現在地までの推測道程をｈ’で表わした時、第４の経路探索手段は（ｇ＋Ｋ・ｈ’）が小さい順に交差点を検索して経路を探索するようにしたので、経路選択時の指向性を任意に設定でき、経路探索における探索時間と経路の最短性または所要走行時間とをバランスした最適な探索方法を提供できる。
請求項１５の発明によれば、第４の経路探索手段の指向性の強さＫを１以下としたので、時間的な余裕のある乗員に最適な経路探索方法を提供でき、探索時間はかかるが最短経路または最小所要時間経路が探索される。
【図面の簡単な説明】
【図１】一実施例の構成を示す機能ブロック図。
【図２】図１に続く、一実施例の構成を示す機能ブロック図。
【図３】実施例の電源系統図。
【図４】一実施例の基本的な経路探索方法を説明する図。
【図５】出発交差点から目的交差点までの種々の指向性係数に対する経路探索領域を示す図。
【図６】現在地周辺の各交差点までの最適経路探索プログラムを示すフローチャート。
【図７】図６に続く、現在地周辺の各交差点までの最適経路探索プログラムを示すフローチャート。
【図８】現在地周辺の経路探索結果を示す図。
【図９】図８に続く、現在地周辺の経路探索結果を示す図。
【図１０】図９に続く、現在地周辺の経路探索結果を示す図。
【図１１】図１０に続く、現在地周辺の経路探索結果を示す図。
【図１２】交差点ネットワークの一例を示す図。
【図１３】目的地から現在地までの最適経路探索プログラムを示すフローチャート。
【図１４】図１３に続く、目的地から現在地までの最適経路探索プログラムを示すフローチャート。
【図１５】図１４に続く、目的地から現在地までの最適経路探索プログラムを示すフローチャート。
【図１６】目的地から現在地までの経路探索結果を示す図。
【図１７】図１６に続く、目的地から現在地までの経路探索結果を示す図。
【図１８】図１７に続く、目的地から現在地までの経路探索結果を示す図。
【図１９】図１８に続く、目的地から現在地までの経路探索結果を示す図。
【図２０】第１のケースにおける経路探索方法を説明する図。
【図２１】目的地から途中通過交差点への指向性の経路探索における探索領域を示す図。
【図２２】目的地から途中通過交差点までの最適経路探索プログラムを示すフローチャート。
【図２３】図２２に続く、目的地から途中通過交差点までの最適経路探索プログラムを示すフローチャート。
【図２４】目的地から途中通過交差点までの経路探索結果を示す図。
【図２５】図２４に続く、目的地から途中通過交差点までの経路探索結果を示す図。
【図２６】図２５に続く、目的地から途中通過交差点までの経路探索結果を示す図。
【図２７】図２６に続く、目的地から途中通過交差点までの経路探索結果を示す図。
【図２８】第２のケースにおける現在地から目的地までの経路探索方法を説明する図。
【図２９】第３のケースにおける現在地から目的地までの経路探索方法を説明する図。
【図３０】ＩＧＮ  ＯＮ時のメインプログラムを示すフローチャート。
【図３１】ＩＧＮ  ＯＦＦ時のメインプログラムを示すフローチャート。
【図３２】タイムアップ割り込みルーチンを示すフローチャート。
【図３３】目的地設定割り込みルーチンを示すフローチャート。
【図３４】目的地設定割り込みルーチンの変形例を示すフローチャート。
【図３５】図３４に続く、目的地設定割り込みルーチンの変形例を示すフローチャート。
【符号の説明】
１  ＣＰＵ
２  システムバス
３  方位センサ
４  増幅器
５  Ａ／Ｄ変換器
６，９  Ｉ／Ｏコントローラー
７  車速センサ
８  キー
１０  スピーカー
１１  サウンドジェネレーター
１２  ＧＰＳレシーバー
１３  拡張Ｉ／Ｏ
１４  受信機
１５  アンテナ
１６  ＣＤ−ＲＯＭ
１７  ＳＣＳＩコントローラー
１８  ＣＲＴ
１９  グラフィックコントローラー
２０  Ｖ−ＲＡＭ
２１  ＲＯＭ
２２  Ｄ−ＲＡＭ
２３  漢字ＲＯＭ
２４  Ｓ−ＲＡＭ
２６  タイマー
２７  補助電池
１００  車両用経路誘導装置
１０１  バッテリー
１０２  キースイッチ
【図１】
0003541482.tif 000002
【図２】
0003541482.tif 000003
【図３】
0003541482.tif 000004
【図４】
0003541482.tif 000005
【図５】
0003541482.tif 000006
【図６】
0003541482.tif 000007
【図７】
0003541482.tif 000008
【図８】
0003541482.tif 000009
【図９】
0003541482.tif 000010
【図１０】
0003541482.tif 000011
【図１１】
0003541482.tif 000012
【図１２】
0003541482.tif 000013
【図１３】
0003541482.tif 000014
【図１４】
0003541482.tif 000015
【図１５】
0003541482.tif 000016
【図１６】
0003541482.tif 000017
【図１７】
0003541482.tif 000018
【図１８】
0003541482.tif 000019
【図１９】
0003541482.tif 000020
【図２０】
0003541482.tif 000021
【図２１】
0003541482.tif 000022
【図２２】
0003541482.tif 000023
【図２３】
0003541482.tif 000024
【図２４】
0003541482.tif 000025
【図２５】
0003541482.tif 000026
【図２６】
0003541482.tif 000027
【図２７】
0003541482.tif 000028
【図２８】
0003541482.tif 000029
【図２９】
0003541482.tif 000030
【図３０】
0003541482.tif 000031
【図３１】
0003541482.tif 000032
【図３２】
0003541482.tif 000033
【図３３】
0003541482.tif 000034
【図３４】
0003541482.tif 000035
【図３５】
0003541482.tif 000036