(57)【特許請求の範囲】
【請求項１】
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定するステップと、
前記制御部が、前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索するステップとを含む
経路探索方法。
【請求項２】
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、実時間に変化する事象に関する情報を取得するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索するステップとを含む
経路探索方法。
【請求項３】
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定する決定手段と
前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索する探索手段とを備えた
経路探索装置。
【請求項４】
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
実時間に変化する事象に関する情報を取得する取得手段と、
前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索する探索手段とを備えた
経路探索装置。
【請求項５】
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定するステップと、
前記制御部が、前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索するステップと
前記制御部が、前記経路を地図と共に表示手段に表示させるステップとを含む
地図表示方法。
【請求項６】
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、実時間に変化する事象に関する情報を取得するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索するステップと、
前記制御部が、前記経路を地図と共に表示手段に表示させるステップとを含む
地図表示方法。
【請求項７】
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定する決定手段と
前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索する探索手段と、
少なくとも地図を表示するための表示手段と、
前記経路を地図と共に前記表示手段に表示させる表示処理手段とを備えた
地図表示装置。
【請求項８】
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
実時間に変化する事象に関する情報を取得する取得手段と、
前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索する探索手段と、
少なくとも地図を表示するための表示手段と、
前記経路を地図と共に前記表示手段に表示させる表示処理手段とを備えた
地図表示装置。
【請求項９】
現在位置を測定し、前記現在位置を地図と共に表示するナビゲート方法において、
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定するステップと、
前記制御部が、前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索するステップと
前記制御部が、前記経路を表示手段に表示させるステップと、
前記制御部が、前記経路に沿って誘導を行なうステップとを含む
ナビゲート方法。
【請求項１０】
現在位置を測定し、前記現在位置を地図と共に表示するナビゲート方法において、
演算処理装置から成る制御部が、ユーザーの入力操作に基づいて目的地を設定するステップと、
前記制御部が、ユーザーの入力操作に基づいて探索条件を設定するステップと、
前記制御部が、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定するステップと、
前記制御部が、実時間に変化する事象に関する情報を取得するステップと、
前記制御部が、前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索するステップと、
前記制御部が、前記経路を地図と共に表示手段に表示させるステップと、
前記制御部が、前記経路に沿って誘導を行なうステップとを含む
ナビゲート方法。
【請求項１１】
現在位置を測定する測定手段と、前記現在位置を地図と共に画像表示手段に表示させる表示処理手段とを有するナビゲーション装置において、
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定する決定手段と、
前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索する探索手段と、
前記経路を画像表示手段に表示させる表示処理手段と、
前記経路に沿った誘導を行なう誘導手段とを備えた
ナビゲーション装置。
【請求項１２】
現在位置を測定する測定手段と、前記現在位置を地図と共に画像表示手段に表示させる表示処理手段とを有するナビゲーション装置において、
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
実時間に変化する事象に関する情報を取得する取得手段と、
前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索する探索手段と、
前記経路を画像表示手段に表示させる表示処理手段と、
前記経路に沿った誘導を行なう誘導手段とを備えた
ナビゲーション装置。
【請求項１３】
現在位置を測定する測定手段と、少なくとも地図を表示するための画像表示手段と、前記現在位置を地図と共に前記画像表示手段に表示させる表示処理手段とを有するナビゲーション装置を搭載した自動車において、
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
前記探索条件及び前記依存関係に基づき、前記複数の経由地の通過順序を決定する決定手段と、
前記通過順序で前記複数の経由地を通過して前記目的地に至る経路を探索する探索手段と、
前記経路を前記画像表示手段に表示させる表示処理手段と、
前記経路に沿った誘導を行なう誘導手段とを備えた
自動車。
【請求項１４】
現在位置を測定する測定手段と、少なくとも地図を表示するための画像表示手段と、前記現在位置を地図と共に前記画像表示手段に表示させる表示処理手段とを有するナビゲーション装置を搭載した自動車において、
ユーザーの入力操作に基づいて目的地を設定する設定手段と、
ユーザーの入力操作に基づいて探索条件を設定する設定手段と、
ユーザーの入力操作に基づき、複数の経由地を設定すると共に、前記複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに前記目的地に直行するという依存関係を設定する設定手段と、
実時間に変化する事象に関する情報を取得する取得手段と、
前記探索条件及び前記依存関係に基づいた通過順序で前記複数の経由地を通過して前記目的地に至る経路を、前記事象の変化に応じて探索する探索手段と、
前記経路を前記画像表示手段に表示させる表示処理手段と、
前記経路に沿った誘導を行なう誘導手段とを備えた
自動車。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びにナビゲーション装置を搭載した自動車に関する。
【０００２】
【従来の技術】
ＧＰＳ（世界的衛星測位装置）を利用したナビゲーション装置が、自動車に搭載される（後付けされるかまたは製造工程で組み込まれる）ことが多くなっている。このナビゲーション装置の最も基本的機能は、自車の現在位置を測定して、その現在位置を地図と共に画面表示することである。しかし、現在普及しているナビゲーション装置には、一般に、この基本的機能以外に各種の付加的な機能が備わっている。
【０００３】
そうした付加的な機能の１つに、ユーザーが目的地及び複数の経由地を設定する操作を行なうことに基づいて、それらの経由地を通過して目的地に至る経路を探索し、探索した経路（推奨経路）を画面表示したり、走行時にその推奨経路に沿って音声や画像で自車を誘導したりする機能がある。この機能を利用すれば、ユーザーは、道に迷うことなく、複数の経由地に立ち寄りつつ目的地に到達することができる。
【０００４】
【発明が解決しようとする課題】
ところで、複数の経由地を通過する経路を探索する際に、それらの経由地の通過順序をどのように決定するのが望ましいかは、ユーザーが重視する探索条件（例えば所要時間の短さを重視するのか、走行距離の短さを重視するのか、あるいは通行料金の低さを重視するのか）によって左右される。
【０００５】
しかるに、従来のナビゲーション装置では、こうした探索条件が、経路を探索する際の経由地の通過順序の決定に反映されることはなかった。そのため、探索された経路における経由地の通過順序が、ユーザーが重視する探索条件からみて望ましくない（例えば時間的，距離的または料金的に効率の悪い）ものとなってしまうことがあった。
【０００６】
また、ユーザーが複数の経由地に立ち寄る際には、先にそのうちのある１つの経由地に立ち寄った後に別の１つの経由地に立ち寄らなければ用を成さない場合（例えば、先に銀行に立ち寄って現金を引き出した後に郵便局に立ち寄ってその現金を振り込む場合）や、ある１つの経由地に立ち寄った後にどこにも立ち寄らずに目的地に直行しなければ用を成さない場合（例えば冷凍食品を購入してそれが融けないうちに自宅に戻りたい場合）がある。
【０００７】
しかるに、従来のナビゲーション装置では、こうした複数の経由地の先後の関係（本明細書ではこの関係を「依存関係」と呼ぶことにする）が、経路を探索する際の複数の経由地の通過順序の決定に反映されることもなかった。そのため、探索された経路における経由地の通過順序が、この依存関係からみて用を成さないものとなってしまうことがあった。
【０００８】
また、推奨経路に沿って実際に誘導されている最中には、例えば道路渋滞や通行規制や天候の状況といった実時間に変化する事象を原因として、それまでの推奨経路に沿って走行を続けることが望ましくなくなることがある。
【０００９】
しかるに、従来のナビゲーション装置では、推奨経路に沿った実際の誘導時にこうした事象の変化があった場合にも、ユーザーが新たな望ましい経路を探索するために経由地を設定し直す操作等を行なわない限り、推奨経路の変更が行なわれることはなかった。そのため、こうした場合には、ユーザーは、走行中に新たな経路の探索のための繁雑な操作を行なうことを強いられる（さもなければ、渋滞や悪天候の中での走行の継続を強いられる）結果となっていた。
【００１０】
したがって、本発明の課題は、こうしたユーザーが重視する探索条件やユーザーが立ち寄る複数の経由地の依存関係を反映した通過順序でそれらの経由地を通過して目的地に至る経路の探索を行なうことのできる経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びにナビゲーション装置を搭載した自動車や、実時間に変化する事象を原因としてユーザーが新たな経路の探索のための操作を強いられることのない経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びにナビゲーション装置を搭載した自動車を提供することにある。
【００１１】
【課題を解決するための手段】
この課題を解決するために、本出願人は、請求項１，３，５，７，９，１１及び１３に記載のように、ユーザーの入力操作に基づいて目的地を設定し、ユーザーの入力操作に基づいて探索条件を設定し、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、この複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずにこの目的地に直行するという依存関係を設定し、この探索条件及び依存関係に基づいてこの複数の経由地の通過順序を決定し、この通過順序でこの複数の経由地を通過してこの目的地に至る経路を探索する経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びにナビゲーション装置を搭載した自動車を提案する。
【００１２】
これらの発明によれば、ユーザーの入力操作に基づいて目的地を設定するだけでなく、ユーザーの入力操作に基づいて探索条件を設定し、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、この複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずにこの目的地に直行するという依存関係を設定することにより、その探索条件及び依存関係に基づいて決定された通過順序でそれらの経由地を通過して目的地に至る経路が探索される。これにより、ユーザーの入力操作に基づいて設定した複数の経由地の依存関係を満たす範囲内で、探索条件にとって望ましい通過順序でそれらの経由地を通過して目的地に至る経路が探索されるようになるので、探索された経路における経由地の通過順序が、探索条件からみて望ましいものとなるだけでなく、この依存関係からみて必ず用を成すものとなる。
【００１３】
したがって、請求項５，７に記載の地図表示の方法及び装置では、このようにユーザーが重視する探索条件からみて望ましいだけでなくユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序の経路が地図と共に表示されるようになる。
【００１４】
また、請求項９，１１，１３に記載のナビゲートの方法及び装置並びに自動車では、このようにユーザーが重視する探索条件からみて望ましいだけでなくユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序の経路に沿った誘導が行なわれるようになる。
【００１９】
次に、本出願人は、請求項２，４，６，８，１０，１２及び１４に記載のように、ユーザーの入力操作に基づいて目的地を設定し、ユーザーの入力操作に基づいて探索条件を設定し、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、この複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずにこの目的地に直行するという依存関係を設定し、実時間に変化する事象に関する情報を取得し、この探索条件及び依存関係に基づいた通過順序でこの複数の経由地を通過してこの目的地に至る経路を、この事象の変化に応じて探索する経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びにナビゲーション装置を搭載した自動車を提案する。
【００２０】
これらの発明によれば、ユーザーの入力操作に基づいて目的地を設定するだけでなく、ユーザーの入力操作に基づいて探索条件を設定し、ユーザーの入力操作に基づき、複数の経由地を設定すると共に、この複数の経由地のうちのある１つの経由地に先に立ち寄った後に別の１つの経由地に立ち寄るという２つの経由地の先後の関係のみの依存関係、及び、ある１つの経由地に立ち寄った後にどこにも立ち寄らずにこの目的地に直行するという依存関係を設定し、しかも、実時間に変化する事象に関する情報を取得することにより、その探索条件及び依存関係に基づいた通過順序でその複数の経由地を通過してその目的地に至る経路の探索が、その事象の変化に応じて行なわれる。これにより、例えば道路渋滞や通行規制や天候の状況といった実時間に変化する事象に応じて経路が自動的に変更されるようになるので、こうした実時間に変化する事象を原因としてユーザーが新たな経路の探索のための操作を強いられることがなくなる。しかも、事象の変化に応じて自動的に変更される経路における複数の経由地の通過順序が、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成すものとなる。
【００２１】
したがって、請求項６，８に記載の地図表示の方法及び装置では、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序であり、しかも実時間に変化する事象に応じて自動的に変更される経路が地図と共に表示されるようになる。
【００２２】
また、請求項１０，１２及び１４に記載のナビゲートの方法及び装置並びに自動車では、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序であり、しかも実時間に変化する事象に応じて自動的に変更される経路に沿った誘導が行なわれるようになる。
【００２７】
【発明の実施の形態】
以下では、ナビゲーション装置を搭載した自動車に本発明を適用した例について説明する。
図１は、本発明を適用した自動車におけるナビゲーション装置の配置例を示す側面図である。この自動車３１には、トランクルーム３２内に、ナビゲーション装置本体２１が配置され、ダッシュボード３３の上に、地図等の画像を表示するための液晶ディスプレイ（ＬＣＤ）２２（進行方向等の案内情報を音声で送出するためのスピーカを付属させたもの）が配置され、このダッシュボード３３内に、地図ディスク等のＣＤ−ＲＯＭを再生するためのＣＤ−ＲＯＭドライブ２３が配置されている。
【００２８】
また、屋根３４の下側に、ＧＰＳ衛星からの電波を受信するためのＧＰＳアンテナ２４が配置され、シート３５の下に、自動車３１のＦＭアンテナ３６を介してＦＭ多重放送によるＶＩＣＳ情報（財団法人道路交通情報通信システムセンターが提供する道路交通情報）（「ＶＩＣＳ」は同財団法人の登録商標）を受信するためのＦＭチューナ２５が配置されている。ナビゲーション装置の操作は、リモートコントローラ２６を用いて行なうようになっている。（同図では、ナビゲーション装置の各部を結ぶ配線については図示を省略している。）
なお、図１はあくまで一例であり、図１とは異なる配置でナビゲーション装置を搭載した自動車に本発明を適用してもよいことはもちろんである。
【００２９】
図２は、図１のナビゲーション装置のハードウェア構成の一例を示すブロック図である。
同図において、図１と同一の符号を付したＬＣＤ２２，ＣＤ−ＲＯＭドライブ２３，ＧＰＳアンテナ２４，ＦＭチューナ２５及びリモートコントローラ２６は図１におけると同一のものであり、スピーカ７はＬＣＤ２２に付属されているものであり、その他の各部はナビゲーション装置本体２１に含まれているものである。
【００３０】
このナビゲーション装置は、メインＣＰＵ１と、その主記憶装置であるＤＲＡＭ２，マスクＲＯＭ３，フラッシュＲＯＭ４及びＳＲＡＭ５と、ＦＭチューナ２５と、周辺制御装置６及びサブＣＰＵ７と、次の各部とを含んでいる。
（１）スピーカ８と、周辺制御装置６からスピーカ８に向けて送られる進行方向等の案内情報のデジタル音声信号をアナログ変換するＤ／Ａ変換器９。
（２）ＬＣＤ２２。
（３）ＣＤ−ＲＯＭ１０を再生するためのＣＤ−ＲＯＭドライブ２３。
（４）ＧＳＰアンテナ２４と、ＧＳＰアンテナ２４の受信電波に基づいて自車の絶対位置を測定するためのＧＳＰコントローラ１１。
（５）リモートコントローラ２６と、リモートコントローラ２６からの信号（遠赤外線領域の信号）を受光するためのリモコン受光部１２。
（６）自車の相対位置を測定するためのジャイロセンサ１３（図示しない車速度センサからの車速パルスも相対位置測定のために併用される）。
【００３１】
フラッシュＲＯＭ４にはメインＣＰＵ１が実行すべきソフトウェアが格納されており、このフラッシュＲＯＭ４からＤＲＡＭ２に転送されたソフトウェアをメインＣＰＵ１が実行することにより、周辺制御装置６及びサブＣＰＵ７を介して上記の各部が制御されると共に、ＦＭチューナ２５で受信したＶＩＣＳ情報が取得される。
【００３２】
こうしたナビゲーション装置のハードウェア構成自体は、既存のものと同様であってよい。ただし、フラッシュＲＯＭ４内のソフトウェアには、次に図３〜図９を用いて説明するような処理のソフトウェアが含まれており、リモートコントローラ２６上の特定の操作キーにも、ユーザーがこの処理における設定を行なう際に操作すべきキーとしての役割が付与されている。また、図２はあくまで一例であり、図２とは異なるハードウェア構成のナビゲーション装置に本発明を適用して、図３〜図９を用いて説明するような処理を実行させるようにしてもよいことはもちろんである。
【００３３】
図３は、図２のナビゲーション装置においてメインＣＰＵ１の処理により実現される経路探索・表示機能の一例を示すブロック図である。
目的地入力部４１では、目的地の設定が行なわれる。この目的地入力部４１は、ユーザーがＬＣＤ２２の表示を見ながらリモートコントローラ２６のキーを操作することに基づいて実現される。
【００３４】
経由地入力部４２では、出発地（自車の現在地）から目的地に至るまでに通過する１または複数の経由地の設定と、複数の経由地を設定した場合のそれらの依存関係の設定とが行なわれる。この経由地入力部４２も、ユーザーがＬＣＤ２２の表示を見ながらリモートコントローラ２６のキーを操作することに基づいて実現される。
【００３５】
経由地リスト作成部４３では、経由地入力部４２で複数の経由地が設定された場合に、各経由地の複数通りの通過順序のうち設定された依存関係を満たす１または複数通りの通過順序のリストである経由地リストの作成が行なわれる。例えば、３つの経由地Ａ，Ｂ及びＣが設定された場合、それらの経由地の通過順序は３×２×１＝６通りあるが、先に経由地Ａに立ち寄った後経由地Ｂに立ち寄るという依存関係が設定されると、その依存関係を満たす通過順序はＡ→Ｂ→ＣとＡ→Ｃ→ＢとＣ→Ａ→Ｂとの３通りだけなので、経由地リスト作成部４３で作成される経由地リスト中にはこの３通りの通過順序だけが存在することになる。
【００３６】
経由地リスト記憶部４４では、経由地リスト作成部４３で作成された経由地リスト経由地が記憶される。この経由地リスト記憶部４４には、図２のＤＲＡＭ２が利用される。
【００３７】
探索条件入力部４５では、経路を探索する際に重視すべき探索条件が、例えば時間（所要時間の短さ），距離（走行距離の短さ），料金（通行料金の低さ）のうちのいずれか１つに設定される。この探索条件入力部４５も、ユーザーがＬＣＤ２２の表示を見ながらリモートコントローラ２６のキーを操作することに基づいて実現される。
【００３８】
移動コスト計算部４６では、経由地リスト作成部４３で作成されて経由地リスト記憶部４４で記憶された経由地リスト中の各通過順序について、探索条件入力部４５で設定された探索条件に基づき、各経由地を通過する際の移動コストが計算される。この移動コストは、探索条件として設定された時間，距離または料金を定量的に表現したものであり、例えば所要時間，走行距離または通過料金を変数とする関数として定義してよい。移動コスト計算部４６で計算された移動コストは、経由地リスト記憶部４４に記憶されている経由地リストに付加される。
【００３９】
なお、この移動コストの計算の基礎となる所要時間，走行距離または通過料金の値は、ＦＭチューナ２５で受信されるＶＩＣＳ情報中の道路渋滞や通行規制や天候の状況等の情報を利用して決定される。
【００４０】
経路探索部４７では、経由地リスト記憶部４４に記憶されている経由地リスト中の通過順序から、移動コストが最小となる通過順序が選択される。そして、出発地からその通過順序で経由地を通過して目的地に至る経路の探索が、例えばダイクストラ法のような周知の経路探索手法により行なわれる。
【００４１】
地図表示部４８では、経路探索部４７で探索された経路（推奨経路）が地図と共に表示される。この表示は、ＣＤ−ＲＯＭドライブ２３でＣＤ−ＲＯＭ１０から再生した地図を用いてＬＣＤ２２の画面上に行なわれる。
【００４２】
次に、図３に示した経路探索・表示機能により経路が探索される様子の具体例を説明する。
例えば図４に示すような地図で表される町において、ユーザーが、自車の現在地から、先に銀行に立ち寄った後に郵便局に立ち寄り、且つデパートに立ち寄った後にどこにも立ち寄らずに自宅に直行するという依存関係で、銀行，デパート，鈴木さん宅及び郵便局に立ち寄って自宅に戻りたいとする。
【００４３】
図５は、この例のように経路の探索を行なう必要がある場合に、ユーザーの操作に基づいてスタートして図３の経路探索・表示機能により実行される処理の流れの一例を示すフローチャートである。
【００４４】
最初に、目的地入力部４１で（すなわちユーザーがＬＣＤ２２を見ながらリモートコントローラ２６のキーを操作することにより）自宅を目的地として設定する（ステップＳ１）。
【００４５】
続いて、探索条件入力部４５で探索条件の設定を行なう（ステップＳ２）。
この探索条件の設定は、図６に示すように、最初に時間，距離，料金のうちいずれか１つを選択させるメニューをＬＣＤ２２に表示し（ステップＳ１１）、ユーザーがそのメニューを見ながらリモートコントローラ２６のキー操作により選択を行なうと（ステップＳ１２）、その選択したものを探索条件として設定する（ステップＳ１３，Ｓ１４，Ｓ１５）。
【００４６】
ステップＳ２に続いて、経由地入力部４２で（すなわちユーザーがＬＣＤ２２を見ながらリモートコントローラ２６のキーを操作することにより）、銀行，デパート，鈴木さん宅及び郵便局を経由地として設定すると共に、先に銀行に立ち寄った後に郵便局に立ち寄り、且つデパートに立ち寄った後にどこにも立ち寄らずに自宅に直行するという依存関係を設定する（ステップＳ３）。
【００４７】
続いて、経由地リスト作成部４３で、銀行，デパート，鈴木さん宅及び郵便局の複数通りの通過順序のうちこの依存関係を満たす１または複数通りの通過順序のリストである経由地リストを作成し（ステップＳ４）、その経由地リストを経由地リスト記憶部４４で記憶する（すなわちＤＲＡＭ２に書き込む）（ステップＳ５）。
【００４８】
続いて、ＦＭチューナ２５で受信したＶＩＣＳ情報を取得する（ステップＳ６）。そして、移動コスト計算部４６で、そのＶＩＣＳ情報中の道路渋滞や通行規制や天候の状況等の情報を利用して、経由地リストの各通過順序について、探索条件に基づいて移動コストを計算し（ステップＳ７）、計算した移動コストを経由地リストに付加する（すなわちＤＲＡＭ２に書き込む）（ステップＳ８）。
【００４９】
図７は、ステップＳ４において作成されてステップＳ７において移動コストを付加された経由地リスト中の１通りの通過順序のリストの構成例を示す。銀行→郵便局→鈴木さん宅→デパートという通過順序について、各経由地のＩＤ及び名称と、その前の経由地（最初の経由地の場合には現在地）のＩＤと、その次の経由地（最後の経由地の場合には目的地）のＩＤと、当該経由地を通過する際の移動コストと、当該経由地と他の経由地との依存関係とでリストが構成されている。依存関係のうち、（ＩＤ，ＩＤ）は前述の銀行と郵便局とのように先後の関係のみを規定し、（ＩＤ→ＩＤ）は前述のデパートと自宅とのようにその間にどこにも立ち寄らないという関係を規定するものである。
【００５０】
ステップＳ８に続いて、経路探索部４７で、経由地リスト中から移動コスト（図７の例では各経由地についての移動コストの合計）が最小となる通過順序を選択し、現在地からその通過順序で経由地を通過して目的地に至る経路を探索する（ステップＳ９）。そして、探索した経路（推奨経路）を地図表示部４８で図４の町の地図と共に表示する（すなわちＣＤ−ＲＯＭドライブ２３でＣＤ−ＲＯＭ１０から再生した図４の町の地図と共に推奨経路をＬＣＤ２２の画面上に表示する）（ステップＳ１０）。そして処理を終了する。
【００５１】
図８は、ステップＳ９において探索された推奨経路の一例（図７と同じ通過順序のもの）を示す。ｎ，ｋ，ｊ，…，ｄの各符号は図４の地図における交差点を示しており、これらの交差点を順にたどることにより、銀行→郵便局→鈴木さん宅→デパートという通過順序でこれらの経由地を通過して目的地である自宅に至ることができる。また、ステップＳ１０における推奨経路の表示では、例えば図４の町の地図上の道路のうち図８の交差点の順に結ばれる道路を他の道路とは色分けして表示する。
【００５２】
このようにして、先に銀行に立ち寄った後に郵便局に立ち寄り、且つデパートに立ち寄った後にどこにも立ち寄らずに自宅に直行するという依存関係を満たす範囲内で、時間，距離，料金のうちユーザーが重視する探索条件にとって望ましい通過順序で銀行，デパート，鈴木さん宅及び郵便局を通過して自宅に至る経路が探索される。これにより、探索された経路における経由地の通過順序が、この探索条件からみて望ましいものとなるだけでなく、この依存関係からみて必ず用を成すものとなる。
なお、走行時には、メインＣＰＵ１がこの推奨経路に沿って音声や画像で自車を誘導する周知の処理を実行する。
【００５３】
次に、図９は、図５の処理を終了した後、タイマ割り込み等により所定の時間間隔（例えば秒単位または分単位の時間間隔）おきに自動的に繰り返しスタートして図３の経路探索・表示機能により実行される処理の流れの一例を示すフローチャートである。
【００５４】
最初に、ＦＭチューナ２５で受信したＶＩＣＳ情報を取得する（ステップＳ２１）。
続いて、そのＶＩＣＳ情報と、直前に取得したＶＩＣＳ情報（図９の処理を最初に実行する場合には図５のステップＳ６で取得したＶＩＣＳ情報であり、図９の処理を２回目以降に実行する場合には前回図９のステップＳ２１で取得したＶＩＣＳ情報である）との間に、所要時間，走行距離または通過料金の値の決定の基礎となる道路渋滞や通行規制や天候の状況等について変化があるか否かを判断する（ステップＳ２２）。
【００５５】
変化があると、移動コスト計算部４６で、図５のステップＳ７と同じく、そのＶＩＣＳ情報を利用して移動コストを計算し（ステップＳ２３）、計算した移動コストを、それまで経由地リストに付加されていた移動コストに代えて経由地リストに付加し直す（ステップＳ２４）。
【００５６】
続いて、経路探索部４７で、図５のステップＳ９と同じく、経由地リスト中から移動コストが最小となる通過順序を選択し、現在地からその通過順序で経由地を通過して目的地に至る経路を探索する（ステップＳ２５）。したがって、道路渋滞や通行規制や天候の状況等の変化を原因とする移動コストの変動により経由地リスト中で移動コストが最小となる通過順序が変動した場合には、通過順序の入れ換えを伴う推奨経路の変更が行なわれることになる。また、移動コストが最小となる通過順序が変動していない場合にも、通過順序の入れ換えを伴わない推奨経路の変更が行なわれることがあり得る。
【００５７】
続いて、地図表示部４８で、図５のステップＳ１０と同じく、探索した推奨経路を図４の町の地図と共に表示する（ステップＳ２６）。そして処理を終了する。
他方、ステップＳ２２で変化がなければ、そのまま処理を終了する。
【００５８】
このように、依存関係を満たす範囲内で探索条件にとって望ましい通過順序で銀行，デパート，鈴木さん宅及び郵便局を通過して自宅に至る経路の探索が、道路渋滞や通行規制や天候の状況等の実時間に変化する事象に応じて行なわれることにより、こうした実時間に変化する事象に応じて推奨経路が自動的に変更される。
【００５９】
これにより、推奨経路に沿った実際の誘導時にも、実時間に変化する事象に応じて推奨経路が自動的に変更されるので、この事象の変化を原因としてユーザーが走行中に新たな経路の探索のための繁雑な操作を強いられることがなくなる。
【００６０】
なお、以上の例では、道路渋滞や通行規制や天候の状況等の情報を、ＦＭ多重放送として提供されるＶＩＣＳ情報から得ている。しかし、これに限らず、光ビーコンや電波ビーコンとして提供されるＶＩＣＳ情報から道路渋滞や通行規制や天候の状況等の情報を得るようにしてもよい。また、例えばインターネットユニット及びデジタル携帯電話を介してインターネットにアクセスできるようになっている場合には、インターネットにアクセスして道路渋滞や通行規制や天候の状況等の情報を得るようにしてもよい。
【００６１】
また、以上の例では、ナビゲーション装置を搭載した自動車に本発明を適用している。しかし、ナビゲーションシステム（自動車用のものであってもそれ以外の用途のものであってもよい）自体や、複数の経由地を通過して目的地に至る経路を探索して地図と共に表示するナビゲーションシステム以外の地図表示システムや、複数の経由地を通過して目的地に至る経路を探索するナビゲーションシステム以外の経路探索システムにも本発明を適用できることは、以上の説明から明かである。
また、本発明は、以上の例に限らず、本発明の要旨を逸脱することなく、その他様々の構成をとりうることはもちろんである。
【００６２】
【発明の効果】
以上のように、本発明に係る請求項１，３，５，７，９，１１及び１３に記載の経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びに自動車によれば、複数の経由地を通過して目的地に至る経路を探索する際に、探索された経路におけるそれらの経由地の通過順序を、ユーザーが重視する探索条件（例えば時間，距離または料金）からみて望ましいものとするだけでなく、ユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成すものとすることができるという効果が得られる。
【００６３】
したがって、請求項５，７に記載の地図表示の方法及び装置では、このようにユーザーが重視する探索条件からみて望ましいだけでなくユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序の経路を地図と共に表示できるようになる。
【００６４】
また、請求項９，１１，１３に記載のナビゲートの方法及び装置並びに自動車では、このようにユーザーが重視する探索条件からみて望ましいだけでなくユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序の経路に沿った誘導を行なえるようになる。
【００６８】
次に、本発明に係る請求項２，４，６，８，１０，１２及び１４に記載の経路探索の方法及び装置、地図表示の方法及び装置、ナビゲートの方法及び装置、並びに自動車によれば、推奨経路に沿った実際の誘導時にも、実時間に変化する事象に応じて推奨経路が自動的に変更されるので、ユーザーに走行中に経路を変更するために経由地の設定し直し等の繁雑な操作を強いる事態やその事象の変化によって望ましくなくなった経路に沿った走行の継続を強いる事態を回避することができ、しかも、事象の変化に応じて自動的に変更される経路における複数の経由地の通過順序を、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成すものとすることができるという効果が得られる。
【００６９】
したがって、請求項６，８に記載の地図表示の方法及び装置では、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序であり、しかも実時間に変化する事象に応じて自動的に変更される経路を地図と共に表示できるようになる。
【００７０】
また、請求項１０，１２及び１４に記載のナビゲートの方法及び装置並びに自動車では、ユーザーが重視する探索条件からみて望ましく且つユーザーの入力操作に基づいて設定した複数の経由地の依存関係からみて必ず用を成す通過順序であり、しかも実時間に変化する事象に応じて自動的に変更される経路に沿った誘導を行なえるようになる。
【図面の簡単な説明】
【図１】本発明を適用した自動車におけるナビゲーション装置の配置例を示す側面図である。
【図２】図１のナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【図３】図２のナビゲーション装置においてメインＣＰＵ１の処理により実現される経路探索・表示機能の一例を示すブロック図である。
【図４】町の地図の一例を示す図である。
【図５】図３の経路探索・表示機能により実行される処理の流れの一例を示すフローチャートである。
【図６】図５の処理の一部を示すフローチャートである。
【図７】経由地リスト中の１通りの通過順序のリストの構成例を示す図である。
【図８】図５の処理により探索された推奨経路の一例を示す図である。
【図９】図３の経路探索・表示機能により実行される処理の流れの一例を示すフローチャートである。
【符号の説明】
１  メインＣＰＵ、  ２  ＤＲＡＭ、  ３  マスクＲＯＭ、  ４  フラッシュＲＯＭ、  ５  ＳＲＡＭ、  ６  周辺制御装置、  ７  サブＣＰＵ、  ８  スピーカ、  ９  Ｄ／Ａ変換器、  １０  ＣＤ−ＲＯＭ、  １１  ＧＳＰコントローラ、  １２  リモコン受光部、  １３  ジャイロセンサ、  ２１  ナビゲーション装置本体、  ２２  液晶ディスプレイ（ＬＣＤ）、  ２３  ＣＤ−ＲＯＭドライブ、  ２４  ＧＰＳアンテナ、  ２５  ＦＭチューナ、  ２６  リモートコントローラ、  ３１  自動車、  ３２  トランクルーム、  ３３  ダッシュボード、  ３４  屋根、  ３５  シート、  ３６  ＦＭアンテナ、  ４１  目的地入力部４１、  ４２  経由地入力部、  ４３  経由地リスト作成部、  ４４  経由地リスト記憶部、  ４５  探索条件入力部、  ４６  移動コスト計算部、  ４７  経路探索部、  ４８  地図表示部
【図１】
0004507333.tif 000002
【図２】
0004507333.tif 000003
【図３】
0004507333.tif 000004
【図４】
0004507333.tif 000005
【図５】
0004507333.tif 000006
【図６】
0004507333.tif 000007
【図７】
0004507333.tif 000008
【図８】
0004507333.tif 000009
【図９】
0004507333.tif 000010