(57)【特許請求の範囲】
【請求項１】
移動体の道案内を行うためのナビゲーション装置において、
どこにどのような道路があるかを表す道路データを予め記憶するための手段と、
前記移動体の現在位置を計算するための手段と、
目的地を指定するための手段と、
１又は２以上の中継点を指定するための手段と、
前記各中継点を経由して前記目的地に至る経路を、前記道路データに基づいて計算するための経路計算手段と、
前記現在位置に基づいて、前記経路に沿った道案内を行うための手段と、
前記各中継点において方向転換が可能かどうかを区別するための区別手段と、を備え、
前記区別手段は、前記各中継点付近における前記移動体の走行状態に基づいて、その中継点において方向転換が可能かどうかを区別するように構成され、
前記経路計算手段は、前記中継点において方向転換が可能かどうかに基づいて、前記経路を計算するように構成されたことを特徴とするナビゲーション装置。
【請求項２】
前記経路計算手段は、前記現在位置から次の中継点までの経路を計算するように構成され、
前記区別手段は、前記現在位置が前記中継点からみて予め決められた位置関係となったことを判定するための手段と、
前記位置関係において前記移動体の速度が所定の値以下になったかどうかに応じて、前記中継点において方向転換可能かどうかを判断するための手段と、を備え、
前記経路計算手段は、前記中継点における方向転換が可能かどうかに基づいて、次の中継点又は目的地までの経路を計算するように構成されたことを特徴とする請求項１記載のナビゲーション装置。
【請求項３】
コンピュータを使って、移動体の道案内を行うためのナビゲーション用ソフトウェアを記録した記録媒体において、
そのソフトウェアは前記コンピュータに、
どこにどのような道路があるかを表す道路データを予め記憶させ、
前記移動体の現在位置を計算させ、
目的地の指定を受け付けさせ、
１又は２以上の中継点の指定を受け付けさせ、
前記各中継点を経由して前記目的地に至る経路を、前記道路データに基づいて計算させ、
前記現在位置に基づいて、前記経路に沿った道案内を行わせ、
前記各中継点付近における前記移動体の走行状態に基づいて、その中継点において方向転換が可能かどうかを区別させ、
前記中継点において方向転換が可能かどうかに基づいて、前記経路を計算させることを特徴とするナビゲーション用ソフトウェアを記録した記録媒体。
【請求項４】
前記ソフトウェアは前記コンピュータに、
前記現在位置から次の中継点までの経路を計算させ、
前記現在位置が前記中継点からみて予め決められた位置関係となったことを判定させ、
前記位置関係において前記移動体の速度が所定の値以下になったかどうかに応じて、前記中継点において方向転換可能かどうかを判断させ、
前記中継点における方向転換が可能かどうかに基づいて、次の中継点又は目的地までの経路を計算させることを特徴とする請求項３記載のナビゲーション用ソフトウェアを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自動車などの移動体に搭載して道案内を行うためのナビゲーションの技術の改良に関するもので、特に、中継点で方向転換できるかどうかに基づいて経路探索を行うことで、より妥当な経路を用いるようにしたものである。
【０００２】
【従来の技術】
近年、自動車などの移動体に搭載し、指定された目的地までの最適な経路を誘導案内する技術として、ナビゲーション装置が知られている。このナビゲーション装置では、地図上の道路や建物などの位置、関係、形状、名称などを数値化することで、経路探索用の道路データや表示用の地図データなどのデータを作成し、データベースとしてＣＤ−ＲＯＭなどの記録媒体に予め記録しておく。
【０００３】
そして、ナビゲーション装置では、指定された目的地までの最適な径路すなわち誘導路を、そのデータベースに基づいて探索すなわち計算する。また、誘導路に沿った誘導案内では、ジャイロスコープや車速パルスを用いた自律航法や、ＧＰＳ(Global Positioning System) やＦＭ多重などを用いた電波航法からリアルタイムに推定した自車位置を、前記誘導路と照合するマップマッチング処理を行いながら画面上の地図に表示し、交差点や分岐での進行方向などを、画面表示や合成音声などで誘導案内する。
【０００４】
また、このようなナビゲーション装置としては、自車の現在位置と目的地以外に、任意の地点を中継点として１つ又は複数指定することで、現在位置からその中継点を経由して目的地に至る径路を、一括して計算するものも知られている。
【０００５】
ところで、このように中継点を経由する径路を計算する場合、幅が広くＵターンの車線があるような道路以外は、中継点のある道路でＵターンするような経路を計算し、そのような径路に基くＵターンの案内通りにドライバーを走行させることはドライバーの負担となる。このため、上記のような従来技術では、指定された中継点での方向転換を避け、図１０に例示するように、中継点の最寄りの道路をただ単に通過するような経路を計算していた。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記のような従来技術では、方向転換できる中継点についても、通過して大回りする経路が用いられるため、効率的なナビゲーションが困難という問題点があった。
【０００７】
例えば、従来技術では、図１０のような例においてユーザが、白丸で示す中継点１を指定した場合、三角形で示す自車の現在位置（自車位置）Ｃから、黒丸で示す目的地までの経路は、図１０に示すような破線、あるいは図１１に示すような破線になると考えられる。これは、従来技術ではあくまで中継点を通過と考える結果、Ｕターンを避ける経路が探索されるからである。
【０００８】
しかしながら、中継点１は実際は観光地であり、ユーザはそこに駐車場があると知っていて、その場所に寄りたいために指定したような場合も考えられる。このような場合は、駐車場でＵターンが可能になるので、図１０のように山道を大回りする経路や、図１１のように中継点を通過しわざわざその先で右左折を繰り返して大回りする経路は効率的でない。すなわち、これらの経路よりも、図１２に示すように、中継点１付近でＵターンする経路の方が、所要時間といったユーザのコストが最小であり、より妥当なものと言える。
【０００９】
本発明は、上記のような従来技術の問題点を解決するために提案されたもので、その目的は、中継点で方向転換できるかどうかに基づいて経路探索を行うことで、より妥当な経路を用いるナビゲーションの技術すなわちナビゲーション装置及び方法並びにナビゲーション用ソフトウェアを記録した記録媒体を提供することである。
【００１０】
【課題を解決するための手段】
上記の目的を達成するため、請求項１の発明は、移動体の道案内を行うためのナビゲーション装置において、どこにどのような道路があるかを表す道路データを予め記憶するための手段と、前記移動体の現在位置を計算するための手段と、目的地を指定するための手段と、１又は２以上の中継点を指定するための手段と、前記各中継点を経由して前記目的地に至る経路を、前記道路データに基づいて計算するための経路計算手段と、前記現在位置に基づいて、前記経路に沿った道案内を行うための手段と、前記各中継点において方向転換が可能かどうかを区別するための区別手段と、を備え、前記区別手段は、前記各中継点付近における前記移動体の走行状態に基づいて、その中継点において方向転換が可能かどうかを区別するように構成され、前記経路計算手段は、前記中継点において方向転換が可能かどうかに基づいて、前記経路を計算するように構成されたことを特徴とする。なお、この発明は、請求項３に記載のように、コンピュータのソフトウェアを記録した記録媒体という見方からとらえることも可能である。
【００１１】
以上の態様では、各中継点について、方向転換できない通過地点なのか、方向転換可能な立ち寄り地点なのかを、自動判定したり、ユーザにマニュアルで指定させたり、データベースなどから判定するなどして区別する。そして、このような区別を加味して経路を探索し計算することで、中継点を一律に通過して大回りすることなく、より妥当な経路を利用することが可能となる。例えば、ある中継点が駐車場などで方向転換可能な立ち寄り地点とわかり、さらにその最寄りの道路が両方向通行可能のような場合は、通過して大回りしてくるよりも、より所要時間といったコストの低い経路を利用できる可能性が生じる。また、自車が中継点付近に差し掛かったときの実際の走行状態に基づいて、その中継点で方向転換可能かどうかを区別する。具体的には例えば、中継点から所定距離内で、経路から自車が一旦外れ、車速が所定以下の実質的停車状態となったときは方向転換可能と判断するなどが考えられる。そして、その結果に応じて、その中継点から先の経路を追加計算したり再計算することで、実際の状況に即した妥当な経路の利用が容易になる。特に、事前にユーザが指定したりデータベースなどから調べた結果と、実状とが違っていたような場合にも、実状に基いた最適な経路の利用が容易になる。
【００１２】
請求項２の発明は、請求項１記載のナビゲーション装置において、前記経路計算手段は、前記現在位置から次の中継点までの経路を計算するように構成され、前記区別手段は、前記現在位置が前記中継点からみて予め決められた位置関係となったことを判定するための手段と、前記位置関係において前記移動体の速度が所定の値以下になったかどうかに応じて、前記中継点において方向転換可能かどうかを判断するための手段と、を備え、前記経路計算手段は、前記中継点における方向転換が可能かどうかに基づいて、次の中継点又は目的地までの経路を計算するように構成されたことを特徴とする。なお、この発明は、請求項４に記載のように、コンピュータのソフトウェアを記録した記録媒体という見方からとらえることも可能である。
以上の態様では、中継点までごとに経路を計算し、その中継点付近に自車が差し掛かると、中継点との位置関係及び車速に基づいて、その中継点で方向転換可能かどうかを判断し、その結果に応じて、次の中継点までの最適な経路を計算する。これにより、事前にユーザの指定やデータベースからの情報読み出しを行うことなく、実状に応じて最適な経路を臨機応変に利用することが容易になる。
【００１５】
【発明の実施の形態】
次に、この発明の複数の実施の形態（以下、本実施形態と呼ぶ）について、図面を参照して具体的に説明する。なお、本実施形態は、各種ハードウェア装置を備えたコンピュータを、コンピュータのソフトウェアによって制御することで実現できる。この場合、そのソフトウェアは、この明細書の記載にしたがった命令を組み合わせることで作られ、上記従来技術と共通の部分には従来技術で説明した手法も利用される。
【００１６】
また、前記ソフトウェアは、プログラムコードだけでなく、プログラムコードの実行のために予め用意されたデータも含み、また、前記コンピュータに組み込まれたＣＰＵや各種回路などの物理的な処理装置を活用することでこの発明の作用効果を実現する。
【００１７】
但し、この発明を実現する具体的なハードウェアやソフトウェアの構成はいろいろ変更することができる。例えば、回路の構成やＣＰＵの処理能力などに応じて、ある機能を、ＬＳＩなどの物理的な電子回路で実現する場合も、ソフトウェアによって実現する場合も考えられる。また、ソフトウェアの形式も、実行モジュールや中間コード、高級言語などいろいろ考えられる。さらに、この発明を実現する上記ソフトウェアを記録した、コンピュータによる読み取り可能な記録媒体は、単独でもこの発明の一態様である。
【００１８】
以上のように、コンピュータを使ってこの発明を実現する具体的な態様はいろいろ考えられるので、以下では、この発明や実施形態に含まれる個々の機能を実現する仮想的回路ブロックを使って、この発明と実施形態とを説明する。
【００１９】
〔１．構成〕
まず、本実施形態は、移動体である自動車に搭載して経路を案内するためのナビゲーション装置（本装置と呼ぶ）と、このナビゲーション装置上で実行されるナビゲーション方法を示すもので、これらを実現するためのナビゲーション用ソフトウェアを記録した記録媒体として把握することもできる。
【００２０】
特に、本実施形態は、上記のようなナビゲーションの技術において、中継点で方向転換できるかどうかに基づいて経路探索を行うことで、より妥当な経路を用いるようにした例であり、図１は、本実施形態の構成を示す機能ブロック図である。
【００２１】
〔１−１．全体の構成〕
すなわち、本実施形態は、絶対位置・方位検出部１と、相対方位検出部２と、車速検出部３と、メインＣＰＵ及びその周辺回路４と、メモリ群Ｍと、ユーザインタフェース部９と、表示部１０と、入力部１１と、ＣＤ−ＲＯＭ制御部１２と、ＦＭ多重受信及び処理部１３と、を備えている。
【００２２】
このうち、絶対位置・方位検出部１は、本装置が搭載された自動車（自車と呼ぶ）の現在位置すなわち自車位置について、地表での絶対的な位置座標や方位を計算するために、例えば、ＧＰＳ衛星から送られてくるＧＰＳ電波をアンテナやレシーバなどで受信するための部分である。また、相対方位検出部２は、ジャイロなどを使って自車の相対的な方位を検出するための部分である。また、車速検出部３は、自車の速度を計算するために、自動車より得られる車速パルスを処理するための部分である。
【００２３】
また、メインＣＰＵ及びその周辺回路４は、本装置全体を制御する制御回路の役割を果たす部分である。また、メモリ群Ｍは、本装置が動作するのに必要な各種のメモリである。これらのメモリのうち、例えば、ＲＯＭ５は、ＢＩＯＳやブートアッププログラムなどを予め格納し、本装置の起動時等にメインＣＰＵ及びその周辺回路４によってアクセスされる。また、ダイナミックＲＡＭ（ＤＲＡＭ）６については、ワークエリアなどに使われる他、本装置の各機能を実現するためのコンピュータプログラムがロードされる。
【００２４】
また、スタティックＲＡＭ（ＳＲＡＭ）７は、不揮発性メモリであり、すなわち、自動車のアクセサリ電源など本装置のメイン電源がオフになっている間も、バッテリーバックアップされることで、電源がオンになったときのためにメモリ内容を保持するものである。また、ＶｉｄｅｏＲＡＭ（ＶＲＡＭ）８は、表示部１０でビデオ表示を行うためのメモリである。
【００２５】
また、表示部１０は、地図や操作メニューなど各種の情報を、図示しない液晶表示パネルや音声合成装置などを使って出力するための部分であり、入力部１１は、リモコン用ユニットなどに備えられた操作キーなどを使ってユーザが命令や目的地などさまざまな情報を本装置に入力するための部分である。また、ユーザインタフェース部９は、Ｉ／Ｏ制御回路やドライバなどを使って、表示部１０及び入力部１１と、メインＣＰＵ及びその周辺回路４とを結ぶユーザインタフェースである。
【００２６】
また、ＣＤ−ＲＯＭ制御部１２は、ＣＤ−ＲＯＭに記録されたナビゲーション装置用のソフトウェアと、このソフトウェアが用いるデータを記録したデータベースと、を読み出すための手段である。また、このデータベースは、どこにどのような道路があるかを表す経路探索用の道路データと、表示用の地図データなどをあらかじめ記憶させたものである。
【００２７】
また、ＦＭ多重受信及び処理部１３は、ＦＭ放送波を受信するための部分であり、併せて、受信した電波からＶＩＣＳの交通情報を取り出すといった処理を行うように構成してもよい。
【００２８】
〔１−２．メインＣＰＵ及びその周辺回路の役割〕
さらに、メインＣＰＵ及びその周辺回路４は、上記のようなソフトウェアの作用によって、現在位置計算部４０と、目的地指定部４１と、経路計算部４３と、案内部４４と、としての役割を果たすように構成されている。
【００２９】
このうち現在位置計算部４０は、自車の現在位置すなわち自車位置を計算するための手段であり、具体的には、電波航法と自律航法とを組み合わせることで自車位置を計算するように構成されている。ここで、電波航法は、ＧＰＳ人工衛星などからの電波に基づいて絶対位置・方位検出部１から得られる情報を使って現在位置を計算するものである。また、自律航法は、地磁気及び自車の速度に基づいて相対方位検出部２及び車速検出部３から得られる情報を使って現在位置を計算するものである。
【００３０】
また、目的地指定部４１は、本装置による道案内の目的地を指定するための手段であり、目的地は、例えば、表示部１０に画面表示される地図上からカーソルで指定したり、自車位置付近のガソリンスタンド、コンビニエンスストア、ファミリーレストランといった条件に基づいてデータのなかから検索し、検索結果から指定すればよい。
【００３１】
また、中継点指定部４２は、１又は２以上の中継点を指定するための手段である。また、経路計算部４３は、指定された各中継点を経由し、指定された目的地に至る最適な経路を、前記道路データに基づいて計算するための経路計算手段である。
【００３２】
また、案内部４４は、経路計算部４３によって計算された経路に沿って、ＣＤ−ＲＯＭ制御部１２によって読み出される前記道路データや、現在位置計算部４０によって計算された現在位置などに基づいて、合成音声や画面表示によって道案内する手段である。
【００３３】
〔１−３．方向転換の判断に関する構成〕
また、メインＣＰＵ及びその周辺回路４は、上記のようなソフトウェアの作用によって、各中継点において方向転換が可能かどうかを区別するための区別手段として、位置判定部４５及び方向転換判断部４６と、マニュアル指定部４７と、データベース読み出し部４８と、を備えている。また、経路計算部４３は、各中継点において方向転換が可能かどうかに基づいて、前記経路を計算するように構成されている。
【００３４】
そして、前記区別手段のうち、まず、位置判定部４５及び方向転換判断部４６は、両者あわせて、各中継点付近における自車の走行状態に基づいて、その中継点において方向転換が可能かどうかを自動的に区別するように構成された部分であり、このような区別を仮に逐次判別と呼ぶ。
【００３５】
ここで、経路計算部４３は、このような逐次判別によってナビゲーションを行う場合、自車の現在位置から次の中継点又は目的地までごとに経路を計算するように構成されている。また、位置判定部４５及び方向転換判断部４６は、現在計算されている経路の終点となっている中継点（現在の中継点と呼ぶ）ごとに、次のような役割を果たすように構成された手段である。
【００３６】
すなわち、位置判定部４５は、自車の現在位置が現在の中継点からみて所定の位置関係となったときにそのことを判定するための手段である。また、方向転換判断部４６は、自車の現在位置が前記所定の位置関係と位置判定部４５によって判定された場合、自車の速度が所定の値以下になったかどうかに応じて、現在の中継点において方向転換可能かどうかを判断するための手段である。
【００３７】
例えば、位置判定部４５は、自車位置が、中継点の最寄りの道路区間から一定距離内の範囲には収まるが、その道路区間から一旦外れたときにそのことを判定する。そして、方向転換判断部４６は、そのような位置関係において、自車の速度が時速１０ｋｍといった所定の値以下にならないときは、現在の中継点を、方向転換のできない地点（通過地点と呼ぶ）と判断し、逆に、自車の速度が時速１０ｋｍといった所定の値以下になったときは、現在の中継点を、方向転換可能な地点（立ち寄り地点と呼ぶ）と判断する。
【００３８】
また、経路計算部４３は、上記のような逐次判別によってナビゲーションを行う場合、現在の中継点における方向転換が可能かどうかに基づいて、次の中継点又は目的地までの経路を計算するように構成されている。
【００３９】
また、マニュアル指定部４７及びデータベース読み出し部４８は、上記のような逐次判別とは異なった態様で中継点における方向転換が可能かどうか区別するための部分であり、それぞれ単独で、前記区別手段の一種である。
【００４０】
このうちマニュアル指定部４７は、各中継点について方向転換が可能かどうかに関するユーザによる指定を入力部１１から受け付けるように構成された部分である。また、データベース読み出し部４８は、各中継点において方向転換が可能かどうかについて前記データベース内に予め用意された情報に基づいて、指定された中継点において方向転換が可能かどうかを区別するように構成された部分である。
【００４１】
〔２．作用〕
上記のように構成された本実施形態は、次のように作用する。
〔２−１．作用の概略〕
まず、ユーザは、入力部１１から、道案内を行うために必要なさまざまな情報、例えば目的地、中継点等を入力する。その入力の際には、メニュー等が表示され、ユーザはそれに従い、目的地指定部４１の作用により道案内の目的地を指定し、また、中継点指定部４２の作用により１又は２以上の中継点を指定する。また、ユーザは、有料道優先、一般道優先といった経路計算の条件なども必要に応じて入力したうえで、経路計算（経路探索とも呼ぶ）を開始させるための所定の操作を行う。
【００４２】
これによって経路探索の要求が発生し、経路計算部４３が経路探索アルゴリズムを用いて、ユーザの入力した設定に従い、経路探索を開始する。すなわち、経路計算部４３は、ユーザの入力した情報と、予め決められた経路探索アルゴリズムにしたがって、現在位置計算部４０によって計算された現在位置から各中継点を経由し目的地に至る最適な経路を、前記道路データに基づいて計算する。また、案内部４４は、このように経路計算部４３によって計算された経路に沿って、ＣＤ−ＲＯＭ制御部１２によって読み出される前記道路データや、現在位置計算部４０によって計算された現在位置などに基づいて、合成音声や画面表示によって道案内を行う。
【００４３】
〔２−２．経路探索の概略〕
上記の処理のうち経路探索は、大まかには、次のように行われる。すなわち、経路探索用の前記道路データは、例えば、交差点のように道路が交差している部分を表すノードと、そのノード間の道路区間を表すリンクと、を単位として構成される。
【００４４】
例えば、図２に例示するように、ノードＮ０とＮ１との間に存在する道路区間は、走行可能な各方向に対応して、ノードＮ０からノードＮ１への方向を持ったリンクＮ０−Ｎ１と、逆に、ノードＮ１からノードＮ０への方向を持ったリンクＮ１−Ｎ０と、によって表すことができ、仮にこの道路区間が一方通行などで一方向への走行しかできない場合は、どちらか一方だけのリンクが存在することになる。
【００４５】
また、各リンクには、例えば、あらかじめ計算された推定通過所要時間といったコスト、あるいは、距離、道路クラス、道幅といった情報が結合されており、経路探索の際には、地点から地点へ向かう経路ごとに、計算されるコストが最小になるように、ダイクストラ法のアルゴリズム、あるいはその応用を用いて最適な経路が計算される。
【００４６】
〔２−３．区別の態様〕
特に、本実施形態では、各中継点が、方向転換できない通過地点か、方向転換できる立ち寄り地点か、に基づいて経路探索を行うことでより妥当な経路を用いる。そして、本実施形態において、中継点が、通過地点なのか立ち寄り地点なのかを区別する態様は、前記逐次判別、マニュアル指定、データベース読み出しという３種類である。
【００４７】
このうち逐次判別は、上記のように、位置判定部４５及び方向転換判断部４６の作用により、各中継点付近における自車の走行状態に基づいて、その中継点が通過地点か立ち寄り地点かを、逐次かつ自動的に区別するものである。
【００４８】
また、マニュアル指定は、マニュアル指定部４７の作用により、各中継点について、方向転換が可能かどうかに関するユーザによる指定を、入力部１１から受け付けることによって、通過地点か立ち寄り地点かを区別するものである。また、データベース読み出しは、データベース読み出し部４８の作用により、各中継点において方向転換が可能かどうかについて前記データベース内に予め用意された情報に基づいて、指定された各中継点が通過地点か立ち寄り地点かを区別するものである。
【００４９】
以下、これら逐次判別、マニュアル指定及びデータベース読み出しについて、それぞれ説明する。
〔２−４．逐次判別〕
まず、経路計算部４３は、逐次判別によってナビゲーションを行う場合、自車の現在位置から次の中継点までごとに経路を計算する。この場合、例えば、図３のように中継点１、中継点２、目的地をユーザが指定し、経路探索を開始した場合、経路計算部４３はまず、出発地から中継点１までの経路探索を行うことで、目的地に至る経路全体のうち一部分を計算する。
【００５０】
そして、案内部４４がこのように計算された経路に沿ってユーザを誘導し、中継点１付近に自車が近づくと、位置判定部４５と方向転換判断部４６との作用により、中継点１付近における自車の走行状態に基づいて、この中継点１が通過地点なのか立ち寄り地点なのかを以下のように判断する。
【００５１】
具体的には、まず、位置判定部４５は、自車の現在位置が現在の中継点１からみて所定の位置関係になるとそのことを判定し、この場合、方向転換判断部４６が、自車の速度が所定の値以下になったかどうかに応じて、現在の中継点が通過地点か立ち寄り地点かを判断する。
【００５２】
すなわち、方向転換判断部４６は、自車の速度が時速１０ｋｍといった所定の値以下にならないときは、現在の中継点を、方向転換のできない通過地点と判断し、逆に、自車の速度が時速１０ｋｍといった所定の値以下になったときは、現在の中継点を、方向転換可能な立ち寄り地点と判断する。そして、経路計算部４３は、この判断の結果に基づいて、次の中継点２までの経路を計算することになる。
【００５３】
ここで、逐次判別の具体例を示す。なお、経路を構成する道路区間を誘導路とも呼ぶ。例えば、図４に例示する中継点１について逐次判別を行う場合、位置判定部４５は予め、中継点１からみて、最寄りの誘導路上で最も近い座標Ｏを、ユークリッド法などを使って求め、また、誘導路のうち前記座標Ｏの直前直後の所定の範囲の部分Ｍ，Ｎを特定しておく。
【００５４】
また、図５は、逐次判別の処理手順を示すフローチャートである。すなわち、自車が、この部分Ｍ，Ｎを走行したうえで（ステップ５１）、部分Ｍ，Ｎ上から一旦外れ（ステップ５５）、かつ、座標Ｏから所定の半径Ｒ内である所定の位置にいる間（ステップ５６）、位置判定部４５はそのことを判定して方向転換判断部４６に知らせる。なお、このような道路と自車位置との位置関係に関する判定は、従来から知られているマップマッチングの技術を用いることによって容易に行うことができる（ステップ５１）。
【００５５】
方向転換判断部４６は、自車が前記所定の位置と位置判定部４５によって判定されている間に、走行速度が０に近くなった場合に（ステップ５７）、そのことを検出して、その中継点についてユーザは「立ち寄り」しようとしている、すなわち方向転換可能な立ち寄り地点と判断する（ステップ５８）。
【００５６】
それ以外の場合、例えば、座標Ｏから半径Ｒ外に出たまま（ステップ５６）、部分Ｍ，Ｎを走行中でなかったり、部分Ｍ，Ｎを通り過ぎたり（ステップ５３）といった場合は、その中継点についてユーザは「通過」しようとしている、すなわち方向転換不可能な通過地点と判断される（ステップ５４）。
【００５７】
そして、図４の例の場合、自車位置が中継点１付近の道路部分Ｍ、Ｎを通り過ぎると、経路計算部４３は、その時点の自車位置から次の中継点あるいは目的地（ここでは次の中継点２）までの経路探索を開始する。この経路探索では、上記のように方向転換判断部４６によって中継点１が通過地点と判定された場合は、その時点における自車の走行方向を求め、その方向に向かうリンクのみを経路探索の最初のリンク（開始リンクと呼ぶ）として行われる。ここで、図６（ａ）は、中継点について通過と判断された場合に、破線で示す自車Ｃの走行方向のリンクだけが開始リンクとなる状態を示す概念図である。
【００５８】
一方、中継点について立ち寄りと判定された場合、経路探索では、自車の走行方向は考慮せず、図６（ｂ）に破線で示すように、最寄りの道路区間が双方向通行で、走行方向に応じた２つのリンクがあれば、その双方を開始リンクとして、経路探索を行う。そして、その後中継点２でも上記のような逐次判定を行い、その結果に応じて、中継点２付近から目的地までを経路探索を行い、経路誘導を開始する。
【００５９】
〔２−５．マニュアル指定による区別〕
また、マニュアル指定の場合は、中継点指定部４２により指定した各中継点について、通過地点なのか立ち寄り地点なのかについて、マニュアル指定部４７が、ユーザによる指定を受け付けることによって区別する。この場合、典型的には、すべての中継点について通過地点か立ち寄り地点かの指定を事前にユーザから受け付けたうえ、経路計算部４３がそれら指定に基づいて、各中継点を経て目的地に至る経路を経路探索する。
【００６０】
但し、例えば、経路誘導途中で所望の中継点について指定を変更すると経路が再計算されるようにしたり、また、上記の逐次判定も併用し、逐次判定によって指定と違った結果が判明すると、経路が再計算されるようにするなども可能である。
【００６１】
〔２−６．データベース読み出し〕
また、データベース読み出しの場合は、各中継点のデータや、中継点を検索するために用いられるようなデータ（検索データと呼ぶ）などについて、予め各地点が立ち寄り地点か通過地点かをフラグなどの形で、前記データベースなどに記録しておく。具体的には、検索データにおいて例えば、観光地で駐車場がある場所については立ち寄り地点としておき、逆に、駐車場がないコンビニエンスストア等は通過地点とするといったように、必要な情報をあらかじめ前記データベース内のデータに埋め込んでおく。
【００６２】
そして、中継点指定部４２を通じて指定されたすべての中継点について、データベース読み出し部４８が、前記データベースから情報を読み出すことによって、方向転換が可能かどうかを区別する。こうすることで、検索データなどに基づいて指定された中継点など、事前に情報が用意されている中継点については、ユーザが改めてマニュアル指定するまでもなく、その中継点が通過地点か立ち寄り地点かの情報を加味することで、よりコストの低い経路が得られる。
【００６３】
また、事前にはどちらともとれないような場所については、その旨の情報を埋め込んでおくなどして、マニュアル指定や、逐次判別を併用してもよい。
【００６４】
〔２−７．マニュアル指定及びデータベース読み出しに基く経路計算〕
次に、中継点が通過地点か立ち寄り地点かの区別が、上記のマニュアル指定又はデータベース読み出しによって行われた場合の経路計算について説明する。まず、本実施形態において、中継点１，２…といった具合に中継点が指定された場合の経路探索の一般的な手順としては、まず、出発地から中継点１までの経路をダイクストラ法やその応用等によって計算し、次に、中継点１から次の中継点２までを同様に計算し、これを目的地まで繰り返し、その結果を結合するものが考えられる。
【００６５】
ここで、単純な例として、目的のほかに１つの中継点１だけが指定された場合の経路探索において、上記のマニュアル指定やデータベース読み出しにより、ある中継点１が通過地点と区別された場合の処理手順を説明する。例えば、図７に例示するように、出発地からその中継点１までの経路探索が既に行われ、探索済経路を構成する最後のリンクが、太い破線で示すリンクＬ１であるとする。
【００６６】
そして、中継点１が通過地点と区別されている場合、中継点１で方向転換はできないので、その先の経路すなわち中継点１から目的地までの経路探索における開始点は、太い破線で示す同じ内容のリンクＬ１のみとなる。これは、両方向通行可能な道路について走行方向毎に逆向きの２つリンクがある場合は、その一方だけを開始リンクとして選択することを意味する。この結果、図７の例では、経路探索の結果は細い破線で示す経路になると考えられる。
【００６７】
なお、中継点１から先の経路を計算し、中継点１までの経路と結合して一体化する場合、例えば、リンクＬ１同士は重複するので、いずれか一方を取り除けばよい。
【００６８】
一方、例えば図８に示す道路Ａが両方向通行可能な場合、太い破線で示すように、ある方向のリンクＬ１だけでなく、これとは逆方向のリンクＬ１’も道路データには存在する。そして、そのような道路Ａの近くに指定された中継点１が立ち寄り地点の場合は、この中継点１付近で、駐車場に出入りしたり、あるいは何らかの他のかたちで停車するなどして方向転換が可能ど考えられる。
【００６９】
このため、経路としては、中継点１付近で方向転換するようなＵターン路を用いても、ユーザにとって不快などの問題は生じない。このため、中継点１から先の目的地までの経路探索を開始する場合の開始リンクとしては、道路データに含まれている２つのリンクＬ１、Ｌ１’を両方用いることができる。この場合、中継点１から目的地までは、リンクＬ１’にしたがって取って返した方が短距離であるから、図８に細い破線で示すような経路になると考えられる。
【００７０】
もちろん、目的地によっては、仮に方向転換が可能でも通過したほうが良い経路となる場合もあるが、上記のように、中継点１が立ち寄り地点の場合は、目的地までの経路として、方向転換する経路としない経路の中から、より低いコストの最適な選択肢を選ぶことで、従来より優れた経路を計算できる可能性が増大する。
【００７１】
なお、経路計算により、中継点１付近から目的地までの経路の最初のリンクとして結果的に採用されるのは、リンクＬ１とＬ１’のうちどちらの可能性もあるが、中継点１までの経路の最後のリンクＬ１と同じリンクＬ１が最初のリンクの場合は、リンクＬ１は重複することとなるから、新しく計算した経路とそこまでの経路を結合する際に取り除けばよい。
【００７２】
また、中継点１付近から目的地までの最初のリンクが、中継点１までの経路の最後のリンクＬ１と反対方向のリンクＬ１’の場合は、図８に破線の折り返しで示すように、リンクＬ１からリンクＬ１’にまたがるＵターンになるが、画面表示する際には、リンクＬ１とリンクＬ１’に対応する道路区間全体について誘導経路を表示するのではなく、誘導経路としては、図８に細い破線で示すように、道路Ａのうち中継点１に最も距離が短い座標まで表示し、このような誘導経路について誘導を行う。
【００７３】
ここで、図９は、中継点までごとの部分的経路探索を繰り返すことで経路全体を計算する処理手順を示すフローチャートである。すなわち、この手順では、中継点が１つ以上（ここでは複数の意）あるのでなければ（ステップ９０１）、単純に、現在地などの出発地から目的地までの経路探索を行う（ステップ９０２）。一方、中継点が１つ以上あれば（ステップ９０１）、まず、出発地から最初の中継点１を目的地として経路探索し、結果は、探索済経路の格納領域ｌｉｎｋ［０］〜ｌｉｎｋ［ｍ−１］に格納する（ステップ９０３）。ここで、ｍは、探索済経路の格納領域における格納済リンク数を表す。
【００７４】
そして、中継点の個数を所定の変数Ｎに格納し、ループの処理回数ｎを１に初期化する（ステップ９０４）。そして、部分的経路探索の終点を表す変数Ｍに、Ｎ≦ｎならすなわち最後は目的地を、それ以前はｎ＋１番目の中継点すなわち２番目から始め、次の中継点をセットする（ステップ９０５）。
【００７５】
そして、中継点ｎすなわち部分的経路探索の始点が通過地点のときは（ステップ９０６）、開始リンクを、それまでに探索された経路の最後のリンクｌｉｎｋ［ｍ−１］とし、Ｍ地点すなわちＭにセットされた地点までの経路探索を行い、結果は一時保存バッファｂｕｆ［０］〜ｂｕｆ［Ｉ−１］に格納する（ステップ９０７）。
【００７６】
この場合、一部保存バッファ中の最初のリンクｂｕｆ［０］と、探索済経路の最後のリンクｌｉｎｋ［ｍ−１］は同じであるから、ｂｕｆ［０］を取り除き、探索済経路の最後のリンクに続く格納領域ｌｉｎｋ［ｍ］以降に、一時保存バッファ中の２番目のリンク以降ｂｕｆ［１］〜ｂｕｆ［Ｉ−１］を追加格納することによって、探索済経路に、新しく探索された経路を結合する。また、格納済リンク数ｍに、追加格納されたリンク数Ｉ−１を加える（ステップ９０８）。
【００７７】
そして、処理済となったＭが目的地であれば経路探索全体を終了するが（ステップ９０９）、そうでなければ、ループの処理回数ｎを１加算して（ステップ９１０）ステップ９０５からの処理を繰り返す。
【００７８】
また、ステップ９０６の判断において、中継点ｎが通過地点でなく、立ち寄り地点のときは、それまでに探索された経路の最後のリンクｌｉｎｋ［ｍ−１］と、これとは方向が逆の逆リンクを求め、その２つを開始リンクとして、Ｍにセットされた地点までの経路探索を行い、結果を一時保存バッファｂｕｆ［０］〜ｂｕｆ［Ｉ−１］に格納する（ステップ９１１）。
【００７９】
このとき、結果的に採用された開始リンクｂｕｆ［０］が、探索済経路の格納領域に格納されている最後のリンクｌｉｎｋ［ｍ−１］と同じであれば（ステップ９１２）、部分的経路探索の結果は中継点ｎが通過地点だった場合と同じであるからステップ９０８に進む。
【００８０】
また、結果的に採用された開始リンクｂｕｆ［０］が、探索済経路の格納領域に格納されている最後のリンクｌｉｎｋ［ｍ−１］と同じでなければ（ステップ９１２）、取り除くべきリンクは無いので、探索済経路の最後のリンクに続く格納領域ｌｉｎｋ［ｍ］以降に、一時保存バッファ中の最初のリンク以降ｂｕｆ［０］〜ｂｕｆ［Ｉ−１］を追加格納することによって、探索済経路に、新しく探索された経路を結合する。この場合、追加格納されたリンク数はＩとなるので、これを格納済リンク数ｍに加え（ステップ９１３）、ステップ９０９の判断に進む。
【００８１】
〔３．効果〕
上記のように、本実施形態では、位置判定部４５、方向転換判断部４６、マニュアル指定部４７、データベース読み出し部４８の作用により、各中継点について、方向転換できない通過地点なのか、方向転換可能な立ち寄り地点なのかを、自動判定したり、ユーザにマニュアルで指定させたり、データベースなどから判定するなどして区別する。そして、このような区別を加味して経路を探索し計算することで、中継点を一律に通過して大回りすることなく、より妥当な経路を利用することが可能となる。
【００８２】
また、本実施形態では、位置判定部４５及び方向転換判断部４６の作用により、自車が中継点付近に差し掛かったときの実際の走行状態に基づいて、その中継点で方向転換可能かどうかを区別し、その結果に応じて、その中継点から先の経路を追加計算したり再計算することで、実際の状況に即した妥当な経路の利用が容易になる。特に、事前にユーザが指定したりデータベースなどから調べた結果と、実状とが違っていたような場合にも、実状に基いた最適な経路の利用が容易になる。
【００８３】
また、本実施形態では、経路計算部４３の作用により、中継点までごとに経路を計算し、その中継点付近に自車が差し掛かると、位置判定部４５と方向転換判断部４６との作用により、中継点との位置関係及び車速に基づいて、その中継点で方向転換可能かどうかを判断し、その結果に応じて、経路計算部４３が、次の中継点までの最適な経路を計算する。これにより、事前にユーザの指定やデータベースからの情報読み出しを行うことなく、実情に応じて最適な経路を臨機応変に利用することが容易になる。
【００８４】
また、本実施形態では、マニュアル指定部４７の作用により、各中継点について方向転換可能かどうかをユーザにマニュアルで指定させることにより、ユーザの知識や意向を活かした効果的な経路の計算が可能となる。
【００８５】
また、本実施形態では、データベース読み出し部４８の作用により、データベースなどに予め記録された情報に基づいて、各中継点で方向転換可能かどうか区別されるので、ユーザにマニュアルで指定させるマニュアル指定より操作が簡略化される。また、中継点に差し掛かるたびに走行状態などから区別してその先の経路を計算する逐次判定と比べて、事前に目的地までの経路全体を一括計算することができるので、ユーザは経路全体を事前に把握することが容易になる。
【００８６】
〔４．他の実施形態〕
なお、本発明は上記各実施形態に限定されるものではなく、次に例示するような他の実施形態も包含するものである。例えば、本発明は、自動車だけでなく二輪車など他の種類の移動体にも適用することもできる。また、道路データの形式、現在位置や経路の計算に使うアルゴリズム、経路に道案内の具体的な内容といった詳細は自由である。
【００８７】
また、中継点において方向転換が可能かどうかを区別するための手法や、各中継点付近における移動体の走行状態に基づいてその中継点において方向転換が可能かどうかを区別するための手法は自由であり、例えば、中継点付近において、ジャイロセンサによって検出される相対方位が、一定の角度以上変化したときに方向転換可能な立ち寄り地点と判断するなども考えられる。
【００８８】
同様に、方向転換可能かどうか逐次判定する基準において、中継点からみた所定の「位置関係」や、そのような位置関係において、移動体の速度について「所定の値」についても、具体的には自由に定めることができる。
【００８９】
【発明の効果】
以上説明したように、本発明によれば、中継点で方向転換できるかどうかに基づいて経路探索を行うことで、より妥当な経路を用いるナビゲーションの技術すなわちナビゲーション装置及び方法並びにナビゲーション用ソフトウェアを記録した記録媒体を提供することができるので、ナビゲーションの使い勝手が向上する。
【図面の簡単な説明】
【図１】本発明の実施形態の構成を示す機能ブロック図。
【図２】本発明の実施形態におけるノードとリンクの例を示す概念図。
【図３】本発明の実施形態における中継点と目的地の例を示す図。
【図４】本発明の実施形態において、中継点１について方向転換可能かどうか逐次判定する原理を示す概念図。
【図５】本発明の実施形態における逐次判定の処理手順を示すフローチャート。
【図６】本発明の実施形態において、中継点について通過と判断された場合（ａ）と、立ち寄りと判断された場合（ｂ）で、その先の経路計算における開始リンクが変化する状態を示す図。
【図７】本発明の実施形態において、中継点が通過地点の場合に、探索済経路の最後のリンクと、その先の経路探索の開始リンクが同じ向きになる状態を示す概念図。
【図８】本発明の実施形態において、中継点が立ち寄り地点の場合に、探索済経路の最後のリンクと向きが反対のリンクも、その先の経路探索の開始リンクになりうる状態を示す概念図。
【図９】本発明の実施形態における経路計算の処理手順を示すフローチャート。
【図１０】従来技術において、中継点を通過する経路の例を示す概念図。
【図１１】従来技術において、中継点を通過する経路の例を示す概念図。
【図１２】中継点で方向転換する妥当な経路の例を示す概念図。
【符号の説明】
１…絶対位置・方位検出部
２…相対方位検出部
３…車速検出部
４…メインＣＰＵ及びその周辺回路
Ｍ…メモリ群
５…ＲＯＭ
６…ダイナミックＲＡＭ（ＤＲＡＭ）
７…スタチックＲＡＭ（ＳＲＡＭ）
８…ＶｉｄｅｏＲＡＭ（ＶＲＡＭ）
９…ユーザインタフェース部
１０…表示部
１１…入力部
１２…ＣＤ−ＲＯＭ制御部
１３…ＦＭ多重受信及び処理部
４０…現在位置計算部
４１…目的地指定部
４２…中継点指定部
４３…経路計算部
４４…案内部
４５…位置判定部
４６…方向転換判断部
４７…マニュアル指定部
４８…データベース読み出し部
【図１】
0004220066.tif 000002
【図２】
0004220066.tif 000003
【図３】
0004220066.tif 000004
【図４】
0004220066.tif 000005
【図５】
0004220066.tif 000006
【図６】
0004220066.tif 000007
【図７】
0004220066.tif 000008
【図８】
0004220066.tif 000009
【図９】
0004220066.tif 000010
【図１０】
0004220066.tif 000011
【図１１】
0004220066.tif 000012
【図１２】
0004220066.tif 000013