ナビゲーション装置及び経路案内方法
【課題】案内経路と代替経路を含む複数経路の乗り換え案内を可能にするナビゲーション装置において、適切なタイミングで経路乗り換え案内を提示することを可能にする。
【解決手段】地図データを記憶する地図データ記憶手段と、地図データを使用して経路を探索する探索手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、行動パタンデータを使用して経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、代替経路を出力する代替経路出力手段と、を備えるナビゲーション装置。
【解決手段】地図データを記憶する地図データ記憶手段と、地図データを使用して経路を探索する探索手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、行動パタンデータを使用して経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、代替経路を出力する代替経路出力手段と、を備えるナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの案内経路を案内するナビゲーション装置に関し、特に、案内経路と代替経路との乗り換え案内が可能なナビゲーション装置に関する。
【背景技術】
【０００２】
従来のナビゲーション装置は、利用者が設定した目的地までの経路を探索条件に基づいて探索する経路探索機能、及び利用者が途中で道に迷わないように案内経路に沿って目的地まで誘導する経路誘導機能を提供する。経路探索時には、異なる探索条件（例えば、有料道路を優先するか又は一般道路を優先するか）に基づいて、複数の経路が探索され、探索された複数の経路が利用者に提示される。そして、提示された複数の経路から、利用者に案内する案内経路を利用者に選択させる。
【０００３】
しかしながら、利用者にとって、複数の経路から一つの経路を選択するための操作は煩わしいものである。このため、ナビゲーション装置は、予め設定された探索条件に基づいて、一つの案内経路を探索し、探索された一つの案内経路に沿って誘導する。
【０００４】
利用者が案内経路を外れた場合又は案内経路を構成する道路の交通状況が渋滞又は工事等によって変化した場合には、ナビゲーション装置は、予め設定された探索条件に基づいて案内経路を探索することによって、自動的に案内経路を設定するリルート機能を備える。
【０００５】
利用者が走行中に案内経路の変更を所望する場合には、一旦自動車を停めて、探索条件を設定しなおすことによって案内経路を変更する方法と、ナビゲーション装置によって提示されている案内経路による誘導を無視して、案内経路上に位置しない道路に進入することによって、ナビゲーション装置のリルート機能によって所望の経路に変更されるのを待つ方法とがある。どちらの方法も、利用者にとって煩わしいものであった。
【０００６】
この問題点を解決するために、走行中に探索条件の異なる複数の経路を探索して、現在利用者を案内している案内経路上に位置する交差点のうち、探索された案内経路以外の経路（代替経路）に進入可能な交差点（分岐点）を案内ポイントとして抽出し、抽出された案内ポイント毎に探索条件の異なる代替経路へ進入が可能であることを提示するナビゲーション装置が知られている（例えば、特許文献１参照）。
【特許文献１】特開２００７−２８５８８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載のナビゲーション装置によれば、案内経路を限定しない経路乗り換え案内が可能となる。しかしながら、すべての分岐点で乗り換え案内が提示されると、利用者にとって煩わしいばかりで、最適な経路案内ができない。
【０００８】
本発明は、この問題点を鑑み、利用者が経路乗り換え案内を必要とする可能性の高い分岐点を抽出し、その手前でタイミングよく経路乗り換え案内を提示可能なナビゲーション装置の提供を目的とする。
【課題を解決するための手段】
【０００９】
請求項１にかかわる本発明によれば、地図データを記憶する地図データ記憶手段と、前記地図データを使用して経路を探索する探索手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、前記行動パタンデータ記憶手段から読み出された前記行動パタンデータを使用して前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、前記流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、前記代替経路をユーザに対して出力する代替経路出力手段と、を備えることを特徴とする。
【００１０】
上記構成によれば、地図データ記憶手段に記憶された地図データを使用して経路が探索され、行動パタンデータ記憶手段に記憶された交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを使用して、経路上の交差点からの案内ポイントが抽出され、案内ポイントにおいて進行する流出リンクが推定され、推定された流出リンクを進行した場合の代替経路が探索され、代替経路がユーザに対して出力される。
【００１１】
また、請求項７にかかわる本発明によれば、地図データを記憶する地図データ記憶手段と、複数の経路を探索する複数経路探索手段と、前記複数の探索された経路から好適な経路を選択する経路選択する経路選択手段と、前記経路をユーザに対して出力する出力手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、前記複数経路探索手段によって探索された複数の異なる前記経路の分岐点を抽出する分岐点抽出手段と、前記複数経路探索手段によって探索された前記複数の経路の前記分岐点における前記進行頻度を、前記行動パタンデータから算出する進行頻度算出手段と、を備え、前記分岐点抽出手段によって抽出された分岐点において、前記経路選択手段によって選択された好適な経路上の流出リンクの進行頻度より、前記好適な経路と異なる経路上の分岐点からの流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路を前記出力手段に出力することを特徴とする。
【００１２】
上記構成によれば、地図データを使用して、複数の経路が探索され、複数の経路から好適な経路が選択され、選択された好適な経路と異なる経路との分岐点を分岐点抽出手段が抽出し、抽出された分岐点の交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶した行動パタン記憶手段の行動パタンデータから、分岐点における進行頻度を算出し、好適な経路の流出リンクの進行頻度より、好適な経路と異なる経路の流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路がユーザに対して出力手段によって出力される。
【発明の効果】
【００１３】
請求項１の発明によれば、進行頻度の高い代替経路を含む案内ポイントを抽出し、代替経路がユーザに出力される。これによって、進行頻度の高い代替経路が存在する場合にのみ代替経路を表示するので、すべての分岐点で代替経路を表示する場合と比較して、ユーザの煩わしさが軽減する。
【００１４】
請求項７の発明によれば、好適な経路を選択中に進行頻度の高い別の経路への分岐点を抽出し、別の経路を表示できる。これによって、進行頻度の高い探索経路が存在する場合にのみ別の経路を表示するので、すべての分岐点で別の経路を表示する場合と比較して、ユーザの煩わしさが軽減する。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態について、図１〜図２２を用いて説明する。
【００１６】
（第１実施形態）
まず、本発明の第１実施形態を図１〜図１４を用いて説明する。
【００１７】
ナビゲーション装置１０の構成について説明する。図１は、本発明の第１実施形態のナビゲーション装置１０の構成を示すブロック図である。
【００１８】
ナビゲーション装置１０は、出発地から目的地までの経路を利用者に案内する装置であり、制御部１００、無線通信部１１０、センサ情報取得部１２０、入力部１３０、
出力部１４０、地図データ記憶部１５０、行動パタン辞書部１６０、及び行動データ記憶部１７０を備える。
【００１９】
制御部１００は、ナビゲーション装置１０の全体を制御する。具体的には、制御部１００は、図示しないプロセッサ及びメモリを備える。メモリには、プロセッサによって実行される各種プログラムが記憶される。メモリには、入力制御プログラム１０１、経路探索プログラム１０２、経路案内プログラム１０３、行動パタン推定プログラム１０４、及び行動データ蓄積プログラム１０５が記憶される。なお、メモリに記憶される各種プログラム１０１〜１０５の処理については、後述する。
【００２０】
無線通信部１１０は、ナビゲーション装置１０を無線通信ネットワークに接続する。これによって、ナビゲーション装置１０は、無線通信ネットワークに接続される図示しないサーバ等にアクセスできる。
【００２１】
センサ情報取得部１２０は、ＧＰＳ（Global Positioning System）及び車速センサ等から利用者の現在位置等の利用者の状況を示すセンサ情報を取得する。
【００２２】
入力部１３０は、利用者からの入力を受け付ける。出力部１４０は、利用者に情報を提示するための画像出力部（ディスプレイ等）又は音声出力部（スピーカ等）である。
【００２３】
地図データ記憶部１５０には、利用者に表示する地図データが記憶される。なお、地図情報は、ナビゲーション装置１０が目的地までの経路を探索する場合にも使用される。
【００２４】
行動パタン辞書部１６０及び行動データ記憶部１７０には、交差点における各リンクへの進路選択を示す行動パタンデータ１６００が記憶される。なお、行動パタンデータ１６００については、図４及び図５で詳細を説明する。
【００２５】
行動パタン辞書部１６０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０に予め設定されているデータであり、例えば、過去の交通量に基づいた各交差点における各リンクへの進路選択を示すデータである。
【００２６】
一方、行動データ記憶部１７０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０の走行履歴等に対応して更新されるデータである、例えば、利用者の走行履歴に基づいた各交差点における各リンクへの進路選択を示すデータである。
【００２７】
行動パタン辞書部１６０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０が図示しないサーバ等にアクセスすることによって、最新のデータに更新されてもよい。
【００２８】
なお、地図データ記憶部１６０、行動パタン辞書部１６０、及び行動データ記憶部１７０は、ハードディスクドライブ、フラッシュメモリ等の記憶媒体によって構成される。
【００２９】
次に、制御部１００に備わるメモリに記憶される各種プログラム１０１〜１０５について、説明する。
【００３０】
入力制御プログラム１０１は、利用者によって入力された情報をメモリに設定するプログラムである。例えば、利用者から目的地が入力された場合、入力制御プログラム１０１は、入力された目的地をメモリに設定する。
【００３１】
経路探索プログラム１０２は、地図データ記憶部１５０に記憶された地図データを参照して、異なる探索条件に基づいて目的地までの複数の経路を探索する。探索条件とは、例えば、有料道路を優先するか又は一般道路を優先するか等の条件である。そして、探索された複数の経路のうち、利用者に提示することによって利用者を目的地まで案内する経路を案内経路といい、探索された複数の経路のうち、案内経路以外の経路を代替経路という。
【００３２】
経路案内プログラム１０３は、案内経路に沿って利用者を目的地まで誘導し、案内経路上に位置する交差点のうち、利用者が案内経路から外れた経路に進入する可能性する可能性の高い交差点（案内ポイント）で、案内経路及び利用者が進入する可能性の高い経路に進入した場合の目的地までの代替経路を提示する。
【００３３】
行動パタン推定プログラム１０４は、行動パタン辞書部１６０及び行動データ記憶部１７０に記憶された行動パタンデータ１６００から、交差点における進路選択の頻度を示す行動パタン推定データ５００（図５参照）、案内経路上に位置する交差点から案内ポイントを抽出する。なお、案内ポイントを抽出する処理については、図９で詳細を説明する。
【００３４】
行動データ蓄積プログラム１０５は、センサ情報取得部１２０によって取得された利用者の現在位置を蓄積した走行履歴を作成し、作成した走行履歴を行動パタンデータ１６００として、行動データ記憶部１７０に記憶する。
【００３５】
次に、行動パタンについて、図２〜図５を用いて説明する。
【００３６】
図２は、本発明の第１実施形態の交差点における交通流の説明図である。
【００３７】
ナビゲーション装置１０の地図データ記憶部１５０に記憶される地図データの交差点には一意な識別子（例えば、Ｎ０〜Ｎ４）が付与されている。また、この地図データの道路は、二つの交差点を接続するリンクに区分され、リンクごとに一意な識別子（Ｌ０１〜Ｌ４１）が付与されている。
【００３８】
図２では、交差点に流入する流入リンクと交差点から流出する流出リンクとを区分するために、一本のリンクに流入リンクの識別子と流出リンクの識別子とが付与されている。例えば、Ｌ０１によって識別されるリンクは流入リンクであり、Ｌ１０によって識別されるリンクは流出リンクである。
【００３９】
図３は、本発明の第１実施形態の交差点（Ｎ１）における利用者が選択し得る行動パタンの説明図である。
【００４０】
リンク（Ｌ０１）から交差点（Ｎ１）に進入した利用者が選択し得る行動パタンは、リンク（Ｌ１０）に進入する行動パタン（Ａ０）、リンク（Ｌ１２）に進入する行動パタン（Ａ１）、リンク（Ｌ１３）に進入する行動パタン（Ａ２）、及びリンク（Ｌ１４）に進入する行動パタン（Ａ３）である。
【００４１】
ここで、行動パタン（Ａ０）はＵターンを示し、行動パタン（Ａ１）は左折を示し、行動パタン（Ａ２）は右折を示し、行動パタン（Ａ３）は直進を示す。
【００４２】
例えば、行動パタンＡ０は、Ｎ０→Ｌ０１→Ｎ１→Ｌ１０→Ｎ０と示すことができる。
【００４３】
図４は、本発明の第１実施形態の交差点における行動パタンデータ１６００の説明図である。
【００４４】
行動パタンデータ１６００は、交差点ごとの流入量及び流出量を示すデータである。ここで、流入量及び流出量は、行動データ記憶部１７０に記憶されている行動パタンデータ１６００の場合、当該ナビゲーション装置１０を搭載した自動車の走行履歴から算出され、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００の場合、予め設定されている。
【００４５】
行動パタンデータ１６００は、時間帯分類１６０１、利用者分類１６０２、ノードＩＤ１６０３、分岐数１６０４及び進入方向１６０５を含む。
【００４６】
時間帯分類１６０１は、ノードＩＤ１６０３に登録された識別子によって識別される交差点を利用者が通過した時刻の平均である時間帯が登録される。また、時間帯分類１６０１には、時間帯だけでなく、当該交差点を利用者が通過した季節、曜日、祝日か平日か等の情報が登録されてもよい。
【００４７】
利用者分類１６０２には、ナビゲーション装置１０を搭載した自動車の車種、並びに利用者の年齢、性別及び住所等が登録される。
【００４８】
ノードＩＤ１６０３には、当該行動パタンデータ１６００が流入量及び流出量を示す交差点の一意な識別子が登録される。
【００４９】
分岐数１６０４は、ノードＩＤ１６０３に登録された識別子によって識別される交差点を構成するリンクの数が登録される。例えば、図２に示す交差点（Ｎ１）の場合、交差点（Ｎ１）は四つのリンクから構成されているので、分岐数１６０４には、「４」が登録される。
【００５０】
進入方向１６０５は、一つの流入リンク１６０６、及び分岐数１６０４に登録された数分の流出リンクＡ１６０７〜流出リンクＤ１６１０を含む。
【００５１】
流入リンク１６０６は、リンクＩＤ１６０６Ａ及び流入量１６０６Ｂを含む。リンクＩＤ１６０６Ａには、当該流入リンクの一意な識別子が登録される。図２に示す交差点（Ｎ１）の場合、リンクＩＤ１６０６Ａには、リンク（Ｌ０１）の識別子（Ｌ０１）が登録される。流入量１６０６Ｂには、流入リンクから交差点に流入する回数（ｘ０１）が登録される。
【００５２】
流出リンクＡ１６０７は、リンクＩＤ１６０７Ａ及び流出量１６０７Ｂを含む。リンクＩＤ１６０７Ａには、当該流出リンクの一意な識別子が登録される。流出量１６０７Ｂには、交差点からリンクＩＤ１６０７Ａに登録されたリンクの識別子によって識別される流出リンクへ流出する回数（ｙ１２）が登録される。
【００５３】
なお、流出リンクＢ１６０８〜流出リンクＤ１６１０も、流出リンクＡ１６０７と同じ構成であるので、説明を省略する。
【００５４】
なお、進入方向１６０５は、交差点を構成するリンクの数だけ登録される。図４では、リンク（Ｌ０１）が流入リンクである場合の進入方向Ａ１６０５しか図示していないが、リンク（Ｌ２１）が流入リンクである場合の進入方向Ｂ、リンク（Ｌ３１）が流入リンクである場合の進入方向Ｃ、及びリンク（Ｌ４１）が流入リンクである場合の進入方向Ｄも行動パタンデータ１６００に登録されている。
【００５５】
ここで、流入量１６０６Ｂに登録された回数と、流出量１６０７Ｂ〜１６１０Ｂに登録された回数との間には、式１に示す関係が成立している。
（式１）
ｘ０１＝ｙ１２＋ｙ１３＋ｙ１４＋ｙ１０
図５は、本発明の第１実施形態の行動パタン推定データ５００の説明図である。
【００５６】
行動パタン推定データ５００は、行動パタン推定プログラム１０４によって、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００及び行動データ記憶部１７０に記憶されている行動パタンデータ１６００に基づいて生成される。
【００５７】
行動パタン推定データ５００は、各交差点における一つの流入リンクに対する利用者の進路選択の頻度を示す。換言すると、行動パタン推定データ５００は、各交差点における一つ流入リンクから進入可能な流出リンクに進入した頻度を示す。
【００５８】
行動パタン推定データ５００は、行動パタン５０１、流入リンクＩＤ５０２、流出リンクＩＤ５０３、及び出現頻度５０４を含む。
【００５９】
行動パタン５０１は、一つの流入リンクから一つの流出リンクの進路選択を示す行動パタンの一意な識別子が登録される。流入リンクＩＤ５０２には、流入リンクの一意な識別子が登録される。流出リンクＩＤ５０３には、流出リンクの一意な識別子が登録される。
【００６０】
出現頻度５０４には、当該エントリに含まれる流入リンクＩＤ５０２に登録された識別子によって識別される流入リンクから、流出リンクＩＤ５０３に登録された識別子によって識別される流出リンクに進路選択された頻度が登録される。
【００６１】
この進路選択された頻度の算出方法について説明する。
【００６２】
まず、ナビゲーション装置１０は、流入リンクＩＤ５０２に登録された流入リンクの識別子を取得する。そして、ナビゲーション装置１０は、図４に示す行動パタンデータ１６００に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された流入リンクの識別子のうち、取得された流入リンクの識別子と一致するリンクＩＤ１６０６Ａに対応する流入量１６０６Ｂに登録された流入量１６０６Ｂに登録された回数を取得する。
【００６３】
次に、ナビゲーション装置１０は、流入リンクＩＤ５０２に登録された流入リンクの識別子と一致する流入リンク１６０６のリンクＩＤ１６０６Ａが属する進入方向１６０５に含まれる流出リンクＡ〜Ｄ１６０７〜１６１０のリンクＩＤ１６０７Ａ〜１６１０Ａに登録された識別子のうち、流出リンクＩＤ５０３に登録された流出リンクの識別子に対応する流出量に登録された回数を取得する。
【００６４】
そして、ナビゲーション装置１０は、取得された流出量に登録された回数を取得された流入量１６０６Ｂに登録された回数で除算することによって、出現頻度に登録される一つの流入リンクから一つの流出リンクが進路選択された頻度を算出する。
【００６５】
次に、本発明のナビゲーション装置１０に備わる制御部１００によって実行される処理を、図６〜図９を用いて説明する。
【００６６】
図６は、本発明の第１実施形態の経路乗換案内処理のフローチャートである。
【００６７】
まず、入力制御プログラム１０１が入力部１３０を介して利用者が入力した目的地の情報を受け付けて、目的地を設定する（Ｓ１０）。
【００６８】
ここで、利用者から目的地が入力されない場合、入力制御プログラム１０１は、行動データ記憶部１７０に記憶される走行履歴を参照して、目的地を設定してもよい。
【００６９】
次に、経路探索プログラム１０２は、地図データ記憶部１５０に記憶された地図データを参照して、複数の探索条件に基づいて、Ｓ１０の処理で設定された目的地までの複数の経路を探索する。そして、経路探索プログラム１０２は、探索された複数の経路のうち、予め設定された探索条件に基づく一つの経路を案内経路として設定し、他の経路を代替経路として設定する（Ｓ２０）。
【００７０】
なお、Ｓ２０の処理では、利用者からの要求があれば、利用者が、探索された複数の経路から案内経路とする経路を選択できるようになっている。
【００７１】
次に、経路案内プログラム１０３は、Ｓ２０の処理で設定された案内経路に沿って経路案内を開始する。そして、経路案内プログラム１０３は、経路を案内するために出力部１４０から出力する案内データを生成する（Ｓ３０）。
【００７２】
次に、行動パタン推定プログラム１０４は、案内経路及び利用者が進入する可能性の高い経路に進入した場合の目的地までの代替経路を提示する案内ポイントとなる交差点を抽出する（Ｓ４０）。なお、Ｓ４０の処理（案内ポイント抽出処理）については、図７及び図８で詳細を説明する。
【００７３】
次に、経路探索プログラム１０２は、抽出された案内ポイントで利用者が案内経路から他の経路に進入した場合の目的地までの代替経路を探索する（Ｓ５０）。
【００７４】
次に、制御部１００は、Ｓ５０の処理で代替経路が探索されたか否かを判定する（Ｓ６０）。
【００７５】
Ｓ５０の処理で代替経路が探索されなかったと、Ｓ６０の処理で判定された場合、当該案内ポイントで他の経路に進入してもＳ１０の処理で設定された目的地に到達できないので、Ｓ４０の処理に戻る。
【００７６】
一方、Ｓ５０の処理で代替経路が探索されたと、Ｓ６０の処理で判定された場合、経路案内プログラム１０３は、Ｓ５０の処理で探索された代替経路と案内経路とを提示するための経路乗換案内情報を生成する（Ｓ７０）。
【００７７】
次に、制御部１００は、利用者が目的地に到達したか否かを判定するために、利用者の現在位置から目的地までの距離を算出し、算出した距離が所定値以内であるか否かを判定する（Ｓ８０）。
【００７８】
Ｓ８０の処理で、利用者の現在位置から目的地までの距離が所定値以内でないと判定された場合、利用者は目的地に到達していないので、Ｓ４０の処理に戻る。一方、Ｓ８０の処理で、利用者の現在位置から目的地までの距離が所定値以内であると判定された場合には、利用者は目的地に到達したので、経路乗換案内処理を終了する。
【００７９】
図７は、本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【００８０】
まず、行動パタン推定プログラム１０４は、案内経路上に位置する交差点のうち、利用者の現在位置から近い順に一つ交差点を選択する（Ｓ１１）。
【００８１】
次に、行動パタン推定プログラム１０４は、行動パタン辞書部１６０に記憶された行動パタンデータ１６００に基づいて、Ｓ１１の処理で選択された交差点の行動パタン推定データ５００を生成する（Ｓ１２）。
【００８２】
行動パタン推定データ５００を生成する処理について、具体的に説明する。
行動パタン辞書部１６０に記憶された行動パタンデータ１６００のノードＩＤ１６０３に登録された識別子が、Ｓ１１の処理で選択された交差点の識別子と一致する行動パタンデータ１６００を選択する。
【００８３】
行動パタン推定プログラム１０４は、センサ情報取得部１２０に利用者の現在位置を取得させる。そして、行動パタン推定プログラム１０４は、取得された現在位置に基づいて、Ｓ１１の処理で選択された交差点の流入リンクを特定する。
【００８４】
次に、行動パタン推定プログラム１０４は、行動パタン辞書部１６０に記憶された行動パタンデータ１６００に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された識別子が、特定された流入リンクの識別子と一致する流入リンク１６０６が含まれる進入方向１６０５を選択する。
【００８５】
そして、行動パタン推定プログラム１０４は、選択した進入方向１６０５に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された識別子及び流入量１６０６Ｂに登録された回数を取得する。また、行動パタン推定プログラム１０４は、選択した進入方向１６０５に含まれる流出リンク１６０７〜１６１０のリンクＩＤ１６０７Ａ〜１６１０Ａに登録された識別子及び流出量１６０７Ｂ〜１６１０Ｂに登録された回数を取得する。
【００８６】
そして、行動パタン推定プログラム１０４は、取得した流入リンクの識別子を流入リンクＩＤ５０２に格納し、取得した流出リンクの識別子を流出リンクＩＤ５０３に格納する。そして、各エントリの出現頻度５０４には、流出リンクの流出量を流入リンクの流入量で除算した値が格納される。
【００８７】
以上によって、図５に示す行動パタン推定データ５００が生成される。
【００８８】
次に、行動パタン推定プログラム１０４は、行動データ記憶部１７０に記憶された行動パタンデータ１６００に基づいて、Ｓ１１の処理で選択された交差点の行動パタン推定データ５００を生成する（Ｓ１３）。
【００８９】
なお、Ｓ１３の処理の具体的な説明は、Ｓ１２の処理の具体的な説明と同様であるので、説明を省略する。
【００９０】
次に、行動パタン推定プログラム１０４は、Ｓ１２の処理で生成された行動パタン推定データ５００及びＳ１３の処理で生成された行動パタン推定データ５００に基づいて、行動パタンを推定する（Ｓ１４）。
【００９１】
具体的には、行動パタン推定プログラム１０４は、式２を計算することによって、Ｓ１２の処理で生成された行動パタン推定データ５００の出現頻度５０４に登録された頻度と、Ｓ１３の処理で生成された行動パタン推定データ５００の出現頻度５０４に登録された頻度と、を重み付けた出現頻度を算出する。
（式２）
Ｐｉ＝（１−β）・ｐｉ＋β・ｑｉ（ｉ＝０，１，２，３）
Ｐｉは、行動パタンＡｉの出現頻度を示し、ｐｉは、Ｓ１２の処理で生成された行動パタン推定データ５００の出現頻度５０４を示し、ｑｉは、Ｓ１３の処理で生成された行動パタン推定データ５００の出現頻度５０４を示す。また、βは、０と１との間の値の重み付けパラメータであり、実際の行動データから学習できるようにしてもよい。
【００９２】
また、ナビゲーション装置１０を搭載した自動車の走行距離が長くなるにつれて、つまり行動データ記憶部１７０に記憶された行動パタンデータ１６００の容量が大きくなるにつれて、βの値が増大する。
【００９３】
つまり、ナビゲーション装置１０が利用者の自動車に搭載された直後の状態では、利用者の走行履歴が蓄積されていないので、予め設定されている行動パタン辞書部１６０に記憶されている行動パタンデータ１６００に基づいて生成された行動パタン推定データ５００の出現頻度の重み付けを大きくする。
【００９４】
一方、ナビゲーション装置１０が利用者の自動車に搭載され、利用者の走行履歴がある程度蓄積されていれば、行動データ記憶部１７０に記憶された行動パタンデータ１６００は利用者自身の走行履歴から生成されるデータであるため、行動データ記憶部１７０に記憶された行動パタンデータ１６００は、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００よりも、信頼度が高い。
【００９５】
このため、利用者の走行履歴がある程度蓄積されている場合には、行動データ記憶部１７０に記憶されている行動パタンデータ１６００に基づいて生成された行動パタン推定データ５００の出現頻度の重み付けを大きくする。
【００９６】
次に、行動パタン推定プログラム１０４は、Ｓ１４の処理で算出された出現頻度に基づいて、Ｓ１１の処理で選択された交差点が案内ポイントであるか否かを判定する（Ｓ１５）。なお、Ｓ１５の処理（案内ポイント抽出処理）については、図７で詳細を説明する。
【００９７】
Ｓ１１の処理で選択された交差点が案内ポイントでないと、Ｓ１５の処理で判定された場合、Ｓ１１の処理に戻る。
【００９８】
一方、Ｓ１１の処理で選択された交差点が案内ポイントであると、Ｓ１５の処理で判定された場合、案内ポイント抽出処理を終了する。
【００９９】
図８は、本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【０１００】
まず、行動パタン推定プログラム１０４は、図７に示すＳ１４の処理で算出された出現頻度のうち、最大の出現頻度を取得し、取得した最大の出現頻度が所定値より大きいか否かを判定する（Ｓ１）。
【０１０１】
Ｓ１の処理で、最大の出現頻度が所定値以下であると判定された場合、案内ポイント抽出処理を終了する。
【０１０２】
一方、Ｓ１の処理で、最大の出現頻度が所定値よりも大きいと判定された場合、行動パタン推定プログラム１０４は、最大の出現頻度の流出リンクが案内経路上に位置するか否かを判定する（Ｓ２）。
【０１０３】
Ｓ２の処理で、最大の出現頻度の流出リンクが案内経路上に存在しないと判定された場合、行動パタン推定プログラム１０４は、当該交差点では、利用者が案内経路上に位置しないリンクを進路として選択する可能性が高いので、当該交差点を案内ポイントとして抽出し（Ｓ３）、案内ポイント抽出処理を終了する。
【０１０４】
一方、Ｓ２の処理で、最大の出現頻度の流出リンクが案内経路上に存在すると判定された場合、行動パタン推定プログラム１０４は、利用者が進路として選択する可能性の高いリンクが案内経路上に位置するため、経路乗換案内を提示する必要がないので、Ｓ４の処理に進む。
【０１０５】
行動パタン推定プログラム１０４は、式３を満たす流出リンクが存在するか否かを判定する（Ｓ４）。
（式３）
Ｐｎ／Ｐａ＞αｔｈ
Ｐｎは、ある行動パタンＡｎの出現頻度を示し、Ｐａは、最大の出現頻度を示し、αｔｈは、所定の閾値を示す。
【０１０６】
つまり、Ｓ４の処理では、行動パタン推定プログラム１０４は、ある流出リンクの出現頻度を最大の出現頻度で除算した値が所定値よりも大きいか否かを判定する。
【０１０７】
Ｓ４の処理では、最大の出現頻度が所定値よりも大きいにも係らず、当該最大の出現頻度の流出リンクが案内経路上に位置するため、この交差点が案内ポイントとして抽出されなかった場合、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路として選択する可能性が高い流出リンクが存在する可能性がある。Ｓ４の処理は、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路選択する可能性の高い流出リンクが存在するか否かを判定する処理である。
【０１０８】
Ｓ４の処理で、式３を満たす流出リンクが存在すると判定された場合、最大の出現頻度の流出リンクが案内経路上に位置するため、式３を満たす流出リンクは、案内経路上に位置しないリンクであるので、行動パタン推定プログラム１０４は、当該交差点を案内ポイントとして抽出して（Ｓ３）、案内ポイント抽出処理を終了する。
【０１０９】
一方、Ｓ４の処理で、式３を満たす流出リンクが存在しないと判定された場合、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路選択する可能性の高い流出リンクが存在しないので、案内ポイント抽出処理を終了する。
【０１１０】
図９は、本発明の第１実施形態の行動データ蓄積プログラム１０５によって実行される行動データ蓄積処理のフローチャートである。
【０１１１】
まず、行動データ蓄積プログラム１０５は、センサ情報取得部１２０を介してセンサ情報を取得する（Ｓ２１）。センサ情報には、ＧＰＳ及び車速センサ等から取得されたナビゲーション装置１０の現在位置情報が含まれる。
【０１１２】
次に、行動データ蓄積プログラム１０５は、Ｓ２１の処理で取得したセンサ情報からノイズを除去するために、センサ情報を補正する（Ｓ２２）。例えば、マップマッチングによる補正がある。
【０１１３】
次に、行動データ蓄積プログラム１０５は、Ｓ２２の処理で補正したセンサ情報を、行動データ記憶部１７０に記憶する形式に変換する（Ｓ２３）。具体的には、行動パタンデータ蓄積プログラム１０５は、センサ情報に含まれる現在位置情報を時間と対応付けて、走行履歴を生成する。そして、行動データ蓄積プログラム１０５は、図４に示す行動データ記憶部１７０に記憶される行動パタンデータ１６００に、生成した走行履歴を反映する。
【０１１４】
なお、行動データ蓄積プログラム１０５は、Ｓ２２の処理で補正したセンサ情報をサンプリング及びデータ圧縮等をしてから、走行履歴を生成してもよい。
【０１１５】
次に、行動データ蓄積プログラム１０５は、走行履歴が反映された行動パタンデータ１６００を行動データ記憶部１７０に記憶する（Ｓ２４）。
【０１１６】
次に、経路案内プログラム１０３によって利用者に提供される経路乗換案内を図１０〜図１４を用いて説明する。
【０１１７】
図１０は、本発明の第１実施形態の出力部１４０を介して利用者に提示される案内経路に沿った経路案内の説明図である。
【０１１８】
出発地Ｏ及び目的地Ｄが入力部１３０を介してナビゲーション装置１０に入力された場合、図６に示す経路乗換案内処理のＳ２０の処理で、案内経路Ｒ１が設定される。そして、Ｓ３０の処理で案内経路Ｒ１に沿った経路案内が開始される。そして、Ｓ４０の処理で案内経路Ｒ上に位置する交差点（Ｎ１〜Ｎ５）のうち、利用者の現在位置から近い順に交差点が選択され、選択された交差点が案内ポイントであるか否かが判定される。
【０１１９】
交差点Ｎ１において、流入リンクは「１」であり、流出リンクは「０」、「２」、「３」、「４」である。交差点Ｎ１において、流出リンク「０」が進路として選択された場合、利用者がＵターンすることを示し、流出リンク「２」が進路として選択された場合、利用者が左折することを示し、流出リンク「３」が進路として選択された場合、利用者が直進することを示し、流出リンク「４」が進路として選択された場合、利用者が右折することを示す。
【０１２０】
図１１Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１２１】
図６に示す経路乗換案内所のＳ４０の処理で、交差点Ｎ１が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ１から目的地までの代替経路（Ｒ２及びＲ３）が探索される。
【０１２２】
なお、代替経路Ｒ２は交差点（Ｎ１）を左折した場合の目的地までの経路であり、代替経路Ｒ３は交差点（Ｎ１）を右折した場合の目的地までの経路であり、案内経路Ｒ１は交差点（Ｎ１）を直進した場合の目的地までの経路である。
【０１２３】
また、図１１Ａに示す「５」は、利用者の現在位置を示す。
【０１２４】
図１１Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）付近で提示される経路乗換案内画面の説明図である。
【０１２５】
図１１Ｂの経路乗換案内画面は、利用者が交差点（Ｎ１）に到達する前に出力部１４０から出力される。
【０１２６】
経路乗換案内画面は、案内経路及びＳ５０の処理で探索された代替経路の全体を表示する全体表示画面６、及び案内ポイントとして抽出された交差点（Ｎ１）付近を拡大した拡大表示画面７を含む。
【０１２７】
なお、図１１Ｂは、本発明を限定するものではなく、拡大表示画面７は、通常スケールの地図表示であってもよい。全体表示画面６及び拡大表示画面７に分割した２画面構成にする必要はなく、どちらか一方がポップアップ表示されるようにしてもよい。
【０１２８】
また、全体表示画面６及び拡大表示画面７のいずれか一方の１画面表示としてもよい。拡大表示画面７の代わりに全体表示画面６が１画面で表示されている場合、利用者の現在位置と交差点（Ｎ１）との距離が所定値以下になった場合に、拡大表示画面７が表示されるようにしてもよい。
【０１２９】
さらに、経路乗換案内画面には、利用者にとって経路選択の判断材料となる情報（例えば、目的地までの所要時間、及び目的地までかかる料金等）も表示されるが、図１１Ｂでは省略している。
【０１３０】
図１１Ａにおいて、交差点Ｎ１を直進した場合について図１２Ａ及び１２Ｂを用いて説明する。
【０１３１】
図１２Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第２交差点（Ｎ２）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１３２】
利用者は、図１１Ａの交差点（Ｎ１）を直進している。
【０１３３】
図６に示す経路乗換案内所のＳ４０の処理で、交差点（Ｎ２）が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ２から目的地までの代替経路（Ｒ４）が探索される。
【０１３４】
なお、代替経路（Ｒ４）は、交差点（Ｎ２）を左折した場合の目的地までの経路である。
【０１３５】
図１２Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第２交差点（Ｎ２）付近で提示される経路乗換案内画面の説明図である。
【０１３６】
経路乗換案内画面に含まれる全体表示画面６では、案内経路Ｒ１及び交差点（Ｎ）２）から目的地までの代替経路Ｒ４の全体が表示される。また、拡大表示画面７では、交差点（Ｎ２）付近における案内経路Ｒ１及び代替経路Ｒ４が拡大して表示される。
【０１３７】
図１１Ａにおいて、利用者が、交差点Ｎ２を左折して、代替経路Ｒ２に進入した場合について図１３Ａ〜図１４Ｂを用いて説明する。
【０１３８】
図１３Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）を左折した場合の経路案内の説明図である。
【０１３９】
図１３Ａは、利用者が交差点（Ｎ１）を左折して、案内経路Ｒ２へ進入していることを示す。
【０１４０】
図１３Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）を左折した場合に、代替経路（Ｒ２）が案内経路に設定された場合の経路案内の説明図である。
【０１４１】
利用者が交差点（Ｎ１）を左折して、代替経路（Ｒ２）に進入した場合、ナビゲーション装置１０は、代替経路（Ｒ２）を案内経路として設定し、交差点（Ｎ１）を出発地として、案内経路（Ｒ２）に沿って経路案内を開始する。
【０１４２】
図１４Ａは、本発明の第１実施形態の案内経路Ｒ２上に位置する第１交差点（Ｎ６）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１４３】
図６に示す経路乗換案内所のＳ４０の処理で、交差点Ｎ６が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ１から目的地までの代替経路（Ｒ５）が探索される。
【０１４４】
なお、代替経路Ｒ５は交差点（Ｎ６）を右折した場合の目的地までの経路であり、案内経路Ｒ２は交差点（Ｎ６）を直進した場合の目的地までの経路である。
【０１４５】
図１４Ｂは、本発明の第１実施形態の案内経路Ｒ２上に位置する第１交差点（Ｎ６）付近で提示される経路乗換案内画面の説明図である。
【０１４６】
経路乗換案内画面に含まれる全体表示画面６では、案内経路Ｒ２及び交差点（Ｎ）６）から目的地までの代替経路Ｒ５の全体が表示される。また、拡大表示画面７では、交差点（Ｎ６）付近における案内経路Ｒ２及び代替経路Ｒ５が拡大して表示される。
【０１４７】
（第１実施形態の変形例）
第１実施形態の変形例は、複数の経路が探索されて、探索された複数の経路の分岐点のうち、分岐点で分岐する経路の交通量が、利用者が走行している経路の交通量よりも多い分岐点が案内ポイントとして抽出され、抽出された分岐点で経路乗換案内を提示する。これによって、利用者は、知らなかった経路を知ることができるようになる。
【０１４８】
図１５は、本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでのリンク、分岐点の説明図である。
【０１４９】
リンク（Ｌ１〜Ｌ６）は、出発地Ｏから目的地Ｄまでの間にある進行可能なリンクである。なお、リンクは、出発地Ｏから目的地Ｄまでの交通流を示すだけでよいので、一方向のみのリンクを示している。
【０１５０】
分岐点（Ｎ１〜Ｎ３）は、リンクが分岐する交差点（Ｎ１及びＮ３）及びリンクが合流する交差点（Ｎ２）である。
【０１５１】
出発地Ｏから分岐点Ｎ１まではリンク（Ｌ１）で接続されている。分岐点Ｎ１で、リンクＬ２とリンクＬ４とが分岐する。リンクＬ２は、分岐点Ｎ１から分岐点Ｎ２までを接続し、リンクＬ４は、分岐点Ｎ１から分岐点Ｎ４までを接続する。
【０１５２】
分岐点Ｎ３で、リンクＬ５及びリンクＬ６は、分岐点Ｎ３から分岐点Ｎ２までを接続するが、経路が相違する。分岐点Ｎ２で、リンクＬ２、Ｌ５、及びＬ６が合流する。リンクＬ３は、分岐点Ｎ２から目的地Ｄまでを接続する。
【０１５３】
なお、複数の利用者が選択する可能性の高い施設のみが目的地Ｄとして登録されてもよい。また、複数の利用者の経路が合流する地点のみが出発地Ｏとして登録されてもよい。
【０１５４】
なお、出発地Ｏ及び目的地Ｄの組合せに対する経路選択行動パタンは、少数派も含めると実際には多数の行動パタンが存在すると考えられる。しかしながら、行動パタンをモデル化する目的では冗長となる。そこで、出現頻度の高い上位の行動パタンに対応するリンクのみを抽出するものとする。また、出発地Ｏ及び目的地Ｄの組合せについても、実際には多数の組合せが存在している。
【０１５５】
図１６は、本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでの経路の説明図である。
【０１５６】
出発地Ｏから目的地Ｄまで到達可能な経路は、三つの経路Ｂ１〜Ｂ３が存在する。これらの経路Ｂ１〜Ｂ３が利用者によって選択され得る行動パタンとなる。
【０１５７】
経路Ｂ１は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ２→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。経路Ｂ２は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ４→分岐点Ｎ３→リンクＬ５→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。経路Ｂ３は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ４→分岐点Ｎ３→リンクＬ６→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。
【０１５８】
このように、経路（行動パタン）は、分岐点（ノード）及びリンクの遷移として表現される。
【０１５９】
図１７は、本発明の第１実施形態の行動パタン辞書部１６０及び行動データ記憶部１７０に記憶される経路交通量データ１７００の説明図である。なお、第１実施形態の変形例の経路交通量データ１７００の構成のうち、第１実施形態の経路交通量データ１７００と同じ構成については、同じ符号を付与し、説明を省略する。
【０１６０】
経路交通量データ１７００は、多数の利用者から収集された走行履歴データのような行動データを統計処理によって加工したプローブ統計データを用いることを想定している。
【０１６１】
経路交通量データ１７００は、時間帯分類１６０１、利用者分類１６０２、出発地１７０１、目的地１７０２、交通量１７０３、及び経路Ａ１７０４〜Ｃ１７０６を含む。
【０１６２】
時間帯分類１６０１及び利用者分類１６０２は、図４に示す第１実施形態の経路交通量データ１７００の時間帯分類１６０１及び利用者分類１６０２と同じであるので、説明を省略する。
【０１６３】
出発地１７０１には、ナビゲーション装置１０によって設定された出発地が登録される。目的地１７０２には、ナビゲーション装置１０によって設定された目的地が登録される。交通量１７０３には、出発地から目的地までの交通量が登録される。交通量は、ナビゲーション装置１０が、行動パタン辞書部１６０に記憶される行動パタンデータ１６００の各経路上に位置する交差点の流入量を加算することによって算出される。
【０１６４】
経路Ａ１７０４〜経路Ｃ１７０６には、出発地から目的地まで到達し得る経路がそれぞれ登録される。経路Ａ１７０４は図１６に示す経路Ｂ１を示し、経路Ｂ１７０５は図１６に示す経路Ｂ２を示し、経路Ｃ１７０６は図１６に示す経路Ｂ３を示す。
【０１６５】
経路Ａ１７０４〜経路Ｃ１７０６は、それぞれリンク列１７０４Ａ〜１７０６Ａ及び交通量１７０６Ａ〜１７０６Ｃを含む。
【０１６６】
リンク列１７０４Ａ〜１７０６Ａには、それぞれの経路を構成する出発地から目的地までのリンクが列として登録される。交通量１７０４Ｂ〜１７０６Ｂには、それぞれの経路の交通量が登録される。
【０１６７】
ここで、交通量１７０３に登録される交通量ｘ０と、交通量１７０４Ｂ〜交通量１７０６Ｂに登録される交通量ｙ１〜ｙ３との間には、式４に示す関係が成立している。
（式４）
ｘ０＝ｙ１＋ｙ２＋ｙ３
図１８は、本発明の第１実施形態の変形例の行動パタン推定データ５００の説明図である。なお、本発明の第１実施形態の変形例の行動パタン推定データ５００の構成のうち、第１実施形態の行動パタン推定データ５００と同じ構成については、同じ符号を付与し、説明を省略する。
【０１６８】
行動パタン推定データ５００は、行動パタン５０１、リンク列１８０１、及び出現頻度５０４を含む。
【０１６９】
行動パタン５０１は、図５に示す第１実施形態の行動パタン推定データ５００の行動パタン５０１と同じなので、説明を省略する。
【０１７０】
リンク列１８０１には、経路交通量データ１７００のリンク列１７０４Ａ〜１７０６Ａに登録されたリンク列が登録される。
【０１７１】
出現頻度５０４には、各リンク列１７０４Ａ〜１７０６Ａに登録されたリンク列に対応する図１７に示す交通量１７０４に登録された交通量を交通量１７０３に登録された交通量で除算することによって算出される出現頻度が登録される。
【０１７２】
次に、第１実施形態の変形例の経路乗換案内処理について説明する。本発明の第１実施形態の変形例の経路乗換案内処理は図６に示す第１実施形態の経路乗換案内処理とほぼ同じであり、相違する処理のみ説明する。
【０１７３】
Ｓ２０の処理では、経路探索プログラム１０２は、目的地から出発地までの複数の経路を探索した後、探索された経路を、行動パタン辞書部１６０に記憶されている経路交通量データ１７００に登録する。また、経路探索プログラム１０２は複数の経路を探索した後に、探索された複数の経路の分岐点となる交差点を探索する。
【０１７４】
具体的には、経路探索プログラム１０２は、探索された経路の識別子を経路１７０４〜１７０６に登録し、各経路のリンク列をリンク列１７０４Ａ〜１７０６Ａに登録する。次に、経路探索プログラム１０２は、行動パタン辞書部１６０に記憶されている予め設定された行動パタンデータ１６００を参照して、探索された各経路の交通量を算出して、算出された各経路の交通量を対応する経路１７０４〜１７０６の交通量１７０４Ｂ〜１７０６Ｂに登録する。
【０１７５】
これによって、予め設定された行動パタンデータ１６００に基づいて、経路交通量データ１７００が生成される。
【０１７６】
そして、Ｓ３０の処理で、経路案内プログラム１０３は、案内経路に沿って経路案内を開始する。
【０１７７】
次に、Ｓ４０の処理で、行動パタン推定プログラム１０４は、案内ポイントを抽出する。Ｓ４０の処理を実行した後、ナビゲーション装置１０は、Ｓ５０及びＳ６０の処理を実行しないで、Ｓ７０及びＳ８０の処理を実行して経路乗換案内処理を終了する。
【０１７８】
Ｓ４０の案内ポイント抽出処理について説明する。図１９は、本発明の第１実施形態の変形例の案内ポイント抽出処理のフローチャートである。
【０１７９】
まず、行動パタン推定プログラム１０４は、Ｓ２０の処理で探索された分岐点のうち、利用者の現在位置から近い順に一つ分岐点を選択する（Ｓ１９１）。
【０１８０】
次に、行動パタン推定プログラム１０４は、センサ情報取得部１２０から利用者の現在位置情報を含むセンサ情報を取得し、利用者が現在走行している経路を特定する。そして、行動パタン推定プログラム１０４は、図１８に示す行動パタン推定データ１８００を参照し、特定された現在走行中の経路の出現頻度Ｐｎを取得する（Ｓ１９２）。
【０１８１】
次に、行動パタン推定プログラム１０４は、Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在するか否かを判定する（Ｓ１９３）。
【０１８２】
Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在すると、Ｓ１９３の処理で判定された場合、Ｓ１９１の処理で選択された分岐点を案内ポイントとして抽出して（Ｓ１９４）、案内ポイント抽出処理を終了する。
【０１８３】
一方、Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在しないと、Ｓ１９３の処理で判定された場合、案内ポイント抽出処理を終了する。
【０１８４】
以上によって、利用者が走行している経路が、同じ目的地に向かう他の多くの利用者が走行している経路と異なる場合であっても、多くの利用者が走行している経路の分岐点で経路乗換案内を提示するので、多くの利用者と同じ経路を走行できる。
【０１８５】
（第２実施形態）
次に、本発明の第２実施形態を図２０〜図２２を用いて説明する。
【０１８６】
本発明の第２実施形態の計算機システムは、他の利用者の走行履歴を収集して、他の利用者の走行履歴に基づく行動パタンデータ１６００を生成して、生成された行動パタンデータ１６００を各利用者のナビゲーション装置１０に送信するプローブデータサーバ３０、及びナビゲーション装置１０を備える。
【０１８７】
図２０は、本発明の第２実施形態の計算機システムの説明図である。
【０１８８】
ナビゲーション装置１０について説明する。第２実施形態のナビゲーション装置１０の構成のうち、第１実施形態のナビゲーション装置１０と同じ構成については、同じ符号を付与し、説明を省略する。
【０１８９】
無線通信部１１０は、ナビゲーション装置１０を無線通信ネットワーク２０に接続する。これによって、ナビゲーション装置１０は、無線通信ネットワーク２０に接続されたプローブデータサーバ３０にアクセスできる。
【０１９０】
行動データ送信プログラム１０６は、利用者の現在位置を行動データとしてプローブデータサーバ３０に送信する。行動パタンデータ要求プログラム１０７は、行動パタンデータ３６００をプローブデータサーバ３０に要求する行動パタンデータ要求をプローブデータサーバ３０に送信する。
【０１９１】
プローブデータサーバ３０について説明する。
【０１９２】
プローブデータサーバ３０は、制御部３００、無線通信部３１０、地図データ記憶部３５０、行動パタン辞書部３６０、及び行動データ記憶部３７０を備える。
【０１９３】
制御部３００は、プローブデータサーバ３０の全体を制御する。具体的には、制御部３００は、図示しないプロセッサ及びメモリを備える。メモリには、プロセッサによって実行される各種プログラムが記憶される。メモリには、行動データ蓄積プログラム３０１、行動データ解析プログラム３０２、行動パタンデータ更新プログラム３０３、及び行動パタンデータ検索プログラム３０４が記憶される。なお、メモリに記憶される各種プログラム３０１〜３０４の処理については、後述する。
【０１９４】
無線通信部３１０は、プローブデータサーバ３０を無線通信ネットワーク２０に接続する。これによって、プローブデータサーバ３０は、無線通信ネットワーク２０に接続されたナビゲーション装置１０にアクセスできる。
【０１９５】
地図データ記憶部３５０、は、第１実施形態のナビゲーション装置１０の地図データ記憶部１５０と同じであるので説明を省略する。
【０１９６】
地図データ記憶部３５０には、地図データが記憶される。行動パタン辞書部３６０には、プローブデータサーバ３０が行動データを収集したすべてのナビゲーション装置１０の利用者の走行履歴に基づいて生成された行動パタンデータ３６００が記憶される。行動データ記憶部３７０には、プローブデータサーバ３０が行動データを収集したナビゲーション装置１０の各利用者の走行履歴に基づいて生成された行動パタンデータ３６００が利用者ごとに記憶される。
【０１９７】
次に、制御部３００に備わるメモリに記憶される各種プログラム３０１〜３０４について、説明する。
【０１９８】
行動データ蓄積プログラム３０１は、複数の利用者の現在位置を蓄積した走行履歴を作成し、作成した走行履歴を蓄積する。
【０１９９】
行動データ解析プログラム３０２は、行動データ蓄積プログラム３０１によって蓄積された走行履歴に基づいて行動パタンデータ３６００を生成する。
【０２００】
行動パタンデータ更新プログラム３０３は、行動データ解析プログラムによって生成された行動パタンデータ３６００に基づいて、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００を更新する。
【０２０１】
行動パタンデータ検索プログラム３０４は、ナビゲーション装置１０からの行動パタンデータ要求に対応する行動パタンデータ３６００を、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００から検索する。
【０２０２】
次に、計算機システムで実行される行動データ送信処理について説明する。図２１は、本発明の第２実施形態の行動データ送信処理のシーケンス図である。
【０２０３】
まず、ナビゲーション装置１０は、センサ情報取得部１２０から利用者の現在位置情報を取得し、取得した現在位置情報を行動データとしてプローブデータサーバ３０に送信する（Ｓ３１）。
【０２０４】
なお、行動データは、所定の周期で送信されてもよいし、一回の走行が終了したタイミングで送信されてもよい。
【０２０５】
プローブデータサーバ３０は、行動データを受信する（Ｓ３１）。次に、プローブデータサーバ３０の行動データ蓄積プログラム３０１は、Ｓ３１の処理で受信した行動データを行動データ記憶部３７０に記憶し、行動データに基づいて走行履歴を生成する（Ｓ３３）。
【０２０６】
次に、プローブデータサーバ３０の行動データ解析プログラム３０２は、行動データ蓄積プログラム３０１によって生成された走行履歴に基づいて、行動パタンデータ３６００を生成する（Ｓ３４）。
【０２０７】
次に、プローブデータサーバ３０の行動パタンデータ更新プログラム３０３は、行動データ解析プログラム３０２によって生成された行動パタンデータ３６００を、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００に反映する（Ｓ３５）。
【０２０８】
なお、Ｓ３３及びＳ３４の処理は、所定のタイミングでバッチ処理的に実行される。
【０２０９】
次に、計算機システムによって実行される行動パタンデータ配信処理について説明する。図２２は、本発明の第２実施形態の行動パタンデータ配信処理のシーケンス図である。
【０２１０】
まず、ナビゲーション装置１０の行動パタンデータ要求プログラム１０７は、行動パタンデータ要求をプローブデータサーバ３０に送信する（Ｓ４１）。
【０２１１】
プローブデータサーバ３０は、行動パタンデータ要求を受信した場合、行動パタンデータ検索プログラム３０４を起動する。行動パタンデータ検索プログラム３０４は、行動データ記憶された行動パタンデータ３６００から、行動パタンデータ要求を送信したナビゲーション装置１０の利用者に対応する行動パタンデータ３６００を検索する（Ｓ４２）。
【０２１２】
そして、プローブデータサーバ３０は、行動データ記憶部３７０から検索された行動パタンデータ３６００、及び行動パタン辞書部３６０に記憶された行動パタンデータ３６００をナビゲーション装置１０に送信する（Ｓ４３）。
【０２１３】
ナビゲーション装置１０は、行動パタンデータ要求に対する応答である行動パタンデータを受信すると（Ｓ４４）、行動データ記憶部３７０から検索された行動パタンデータ３６００に基づいて、行動データ記憶部１７０に記憶された行動パタンデータ１６００を更新し、行動パタン辞書部３６０に記憶された行動パタンデータ３６００に基づいて行動パタン辞書部１６０に記憶された行動パタンデータ１６００を更新する。
【０２１４】
なお、ナビゲーション装置１０の行動パタンデータ１６００の更新範囲は、例えば、一括で全領域を更新する方式、適当な領域を指定して更新する方式、及び交差点毎に指定して更新する方式等がある。
【図面の簡単な説明】
【０２１５】
【図１】本発明の第１実施形態のナビゲーション装置の構成を示すブロック図である。
【図２】本発明の第１実施形態の交差点における交通流の説明図である。
【図３】本発明の第１実施形態の交差点における利用者が選択し得る行動パタンの説明図である。
【図４】本発明の第１実施形態の交差点における行動パタンデータの説明図である。
【図５】本発明の第１実施形態の行動パタン推定データの説明図である。
【図６】本発明の第１実施形態の経路乗換案内処理のフローチャートである。
【図７】本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【図８】本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【図９】本発明の第１実施形態の行動データ蓄積プログラムによって実行される行動データ蓄積処理のフローチャートである。
【図１０】本発明の第１実施形態の出力部を介して利用者に提示される案内経路に沿った経路案内の説明図である。
【図１１Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１１Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点付近で提示される経路乗換案内画面の説明図である。
【図１２Ａ】本発明の第１実施形態の案内経路上に位置する第２交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１２Ｂ】本発明の第１実施形態の案内経路上に位置する第２交差点付近で提示される経路乗換案内画面の説明図である。
【図１３Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点を左折した場合の経路案内の説明図である。
【図１３Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点を左折した場合に、代替経路が案内経路に設定された場合の経路案内の説明図である。
【図１４Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１４Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点付近で提示される経路乗換案内画面の説明図である。
【図１５】本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでのリンク、分岐点の説明図である。
【図１６】本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでの経路の説明図である。
【図１７】本発明の第１実施形態の行動パタン辞書部及び行動データ記憶部に記憶される経路交通量データの説明図である。
【図１８】本発明の第１実施形態の変形例の行動パタン推定データの説明図である。
【図１９】本発明の第１実施形態の変形例の案内ポイント抽出処理のフローチャートである。
【図２０】本発明の第２実施形態の計算機システムの説明図である。
【図２１】本発明の第２実施形態の行動データ送信処理のシーケンス図である。
【図２２】本発明の第２実施形態の行動パタンデータ配信処理のシーケンス図である。
【符号の説明】
【０２１６】
１０ ナビゲーション装置
３０ プローブデータサーバ
１００ 制御部
１０１ 入力制御部
１０２ 経路探索プログラム
１０３ 経路案内プログラム
１０４ 行動パタン推定プログラム
１０５ 行動データ蓄積プログラム
１１０ 無線通信部
１２０ センサ情報取得部
１３０ 入力部
１４０ 出力部
１５０ 地図データ記憶部
１６０ 行動パタン辞書部
１７０ 行動データ記憶部
【技術分野】
【０００１】
本発明は、出発地から目的地までの案内経路を案内するナビゲーション装置に関し、特に、案内経路と代替経路との乗り換え案内が可能なナビゲーション装置に関する。
【背景技術】
【０００２】
従来のナビゲーション装置は、利用者が設定した目的地までの経路を探索条件に基づいて探索する経路探索機能、及び利用者が途中で道に迷わないように案内経路に沿って目的地まで誘導する経路誘導機能を提供する。経路探索時には、異なる探索条件（例えば、有料道路を優先するか又は一般道路を優先するか）に基づいて、複数の経路が探索され、探索された複数の経路が利用者に提示される。そして、提示された複数の経路から、利用者に案内する案内経路を利用者に選択させる。
【０００３】
しかしながら、利用者にとって、複数の経路から一つの経路を選択するための操作は煩わしいものである。このため、ナビゲーション装置は、予め設定された探索条件に基づいて、一つの案内経路を探索し、探索された一つの案内経路に沿って誘導する。
【０００４】
利用者が案内経路を外れた場合又は案内経路を構成する道路の交通状況が渋滞又は工事等によって変化した場合には、ナビゲーション装置は、予め設定された探索条件に基づいて案内経路を探索することによって、自動的に案内経路を設定するリルート機能を備える。
【０００５】
利用者が走行中に案内経路の変更を所望する場合には、一旦自動車を停めて、探索条件を設定しなおすことによって案内経路を変更する方法と、ナビゲーション装置によって提示されている案内経路による誘導を無視して、案内経路上に位置しない道路に進入することによって、ナビゲーション装置のリルート機能によって所望の経路に変更されるのを待つ方法とがある。どちらの方法も、利用者にとって煩わしいものであった。
【０００６】
この問題点を解決するために、走行中に探索条件の異なる複数の経路を探索して、現在利用者を案内している案内経路上に位置する交差点のうち、探索された案内経路以外の経路（代替経路）に進入可能な交差点（分岐点）を案内ポイントとして抽出し、抽出された案内ポイント毎に探索条件の異なる代替経路へ進入が可能であることを提示するナビゲーション装置が知られている（例えば、特許文献１参照）。
【特許文献１】特開２００７−２８５８８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載のナビゲーション装置によれば、案内経路を限定しない経路乗り換え案内が可能となる。しかしながら、すべての分岐点で乗り換え案内が提示されると、利用者にとって煩わしいばかりで、最適な経路案内ができない。
【０００８】
本発明は、この問題点を鑑み、利用者が経路乗り換え案内を必要とする可能性の高い分岐点を抽出し、その手前でタイミングよく経路乗り換え案内を提示可能なナビゲーション装置の提供を目的とする。
【課題を解決するための手段】
【０００９】
請求項１にかかわる本発明によれば、地図データを記憶する地図データ記憶手段と、前記地図データを使用して経路を探索する探索手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、前記行動パタンデータ記憶手段から読み出された前記行動パタンデータを使用して前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、前記流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、前記代替経路をユーザに対して出力する代替経路出力手段と、を備えることを特徴とする。
【００１０】
上記構成によれば、地図データ記憶手段に記憶された地図データを使用して経路が探索され、行動パタンデータ記憶手段に記憶された交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを使用して、経路上の交差点からの案内ポイントが抽出され、案内ポイントにおいて進行する流出リンクが推定され、推定された流出リンクを進行した場合の代替経路が探索され、代替経路がユーザに対して出力される。
【００１１】
また、請求項７にかかわる本発明によれば、地図データを記憶する地図データ記憶手段と、複数の経路を探索する複数経路探索手段と、前記複数の探索された経路から好適な経路を選択する経路選択する経路選択手段と、前記経路をユーザに対して出力する出力手段と、交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、前記複数経路探索手段によって探索された複数の異なる前記経路の分岐点を抽出する分岐点抽出手段と、前記複数経路探索手段によって探索された前記複数の経路の前記分岐点における前記進行頻度を、前記行動パタンデータから算出する進行頻度算出手段と、を備え、前記分岐点抽出手段によって抽出された分岐点において、前記経路選択手段によって選択された好適な経路上の流出リンクの進行頻度より、前記好適な経路と異なる経路上の分岐点からの流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路を前記出力手段に出力することを特徴とする。
【００１２】
上記構成によれば、地図データを使用して、複数の経路が探索され、複数の経路から好適な経路が選択され、選択された好適な経路と異なる経路との分岐点を分岐点抽出手段が抽出し、抽出された分岐点の交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶した行動パタン記憶手段の行動パタンデータから、分岐点における進行頻度を算出し、好適な経路の流出リンクの進行頻度より、好適な経路と異なる経路の流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路がユーザに対して出力手段によって出力される。
【発明の効果】
【００１３】
請求項１の発明によれば、進行頻度の高い代替経路を含む案内ポイントを抽出し、代替経路がユーザに出力される。これによって、進行頻度の高い代替経路が存在する場合にのみ代替経路を表示するので、すべての分岐点で代替経路を表示する場合と比較して、ユーザの煩わしさが軽減する。
【００１４】
請求項７の発明によれば、好適な経路を選択中に進行頻度の高い別の経路への分岐点を抽出し、別の経路を表示できる。これによって、進行頻度の高い探索経路が存在する場合にのみ別の経路を表示するので、すべての分岐点で別の経路を表示する場合と比較して、ユーザの煩わしさが軽減する。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態について、図１〜図２２を用いて説明する。
【００１６】
（第１実施形態）
まず、本発明の第１実施形態を図１〜図１４を用いて説明する。
【００１７】
ナビゲーション装置１０の構成について説明する。図１は、本発明の第１実施形態のナビゲーション装置１０の構成を示すブロック図である。
【００１８】
ナビゲーション装置１０は、出発地から目的地までの経路を利用者に案内する装置であり、制御部１００、無線通信部１１０、センサ情報取得部１２０、入力部１３０、
出力部１４０、地図データ記憶部１５０、行動パタン辞書部１６０、及び行動データ記憶部１７０を備える。
【００１９】
制御部１００は、ナビゲーション装置１０の全体を制御する。具体的には、制御部１００は、図示しないプロセッサ及びメモリを備える。メモリには、プロセッサによって実行される各種プログラムが記憶される。メモリには、入力制御プログラム１０１、経路探索プログラム１０２、経路案内プログラム１０３、行動パタン推定プログラム１０４、及び行動データ蓄積プログラム１０５が記憶される。なお、メモリに記憶される各種プログラム１０１〜１０５の処理については、後述する。
【００２０】
無線通信部１１０は、ナビゲーション装置１０を無線通信ネットワークに接続する。これによって、ナビゲーション装置１０は、無線通信ネットワークに接続される図示しないサーバ等にアクセスできる。
【００２１】
センサ情報取得部１２０は、ＧＰＳ（Global Positioning System）及び車速センサ等から利用者の現在位置等の利用者の状況を示すセンサ情報を取得する。
【００２２】
入力部１３０は、利用者からの入力を受け付ける。出力部１４０は、利用者に情報を提示するための画像出力部（ディスプレイ等）又は音声出力部（スピーカ等）である。
【００２３】
地図データ記憶部１５０には、利用者に表示する地図データが記憶される。なお、地図情報は、ナビゲーション装置１０が目的地までの経路を探索する場合にも使用される。
【００２４】
行動パタン辞書部１６０及び行動データ記憶部１７０には、交差点における各リンクへの進路選択を示す行動パタンデータ１６００が記憶される。なお、行動パタンデータ１６００については、図４及び図５で詳細を説明する。
【００２５】
行動パタン辞書部１６０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０に予め設定されているデータであり、例えば、過去の交通量に基づいた各交差点における各リンクへの進路選択を示すデータである。
【００２６】
一方、行動データ記憶部１７０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０の走行履歴等に対応して更新されるデータである、例えば、利用者の走行履歴に基づいた各交差点における各リンクへの進路選択を示すデータである。
【００２７】
行動パタン辞書部１６０に記憶される行動パタンデータ１６００は、ナビゲーション装置１０が図示しないサーバ等にアクセスすることによって、最新のデータに更新されてもよい。
【００２８】
なお、地図データ記憶部１６０、行動パタン辞書部１６０、及び行動データ記憶部１７０は、ハードディスクドライブ、フラッシュメモリ等の記憶媒体によって構成される。
【００２９】
次に、制御部１００に備わるメモリに記憶される各種プログラム１０１〜１０５について、説明する。
【００３０】
入力制御プログラム１０１は、利用者によって入力された情報をメモリに設定するプログラムである。例えば、利用者から目的地が入力された場合、入力制御プログラム１０１は、入力された目的地をメモリに設定する。
【００３１】
経路探索プログラム１０２は、地図データ記憶部１５０に記憶された地図データを参照して、異なる探索条件に基づいて目的地までの複数の経路を探索する。探索条件とは、例えば、有料道路を優先するか又は一般道路を優先するか等の条件である。そして、探索された複数の経路のうち、利用者に提示することによって利用者を目的地まで案内する経路を案内経路といい、探索された複数の経路のうち、案内経路以外の経路を代替経路という。
【００３２】
経路案内プログラム１０３は、案内経路に沿って利用者を目的地まで誘導し、案内経路上に位置する交差点のうち、利用者が案内経路から外れた経路に進入する可能性する可能性の高い交差点（案内ポイント）で、案内経路及び利用者が進入する可能性の高い経路に進入した場合の目的地までの代替経路を提示する。
【００３３】
行動パタン推定プログラム１０４は、行動パタン辞書部１６０及び行動データ記憶部１７０に記憶された行動パタンデータ１６００から、交差点における進路選択の頻度を示す行動パタン推定データ５００（図５参照）、案内経路上に位置する交差点から案内ポイントを抽出する。なお、案内ポイントを抽出する処理については、図９で詳細を説明する。
【００３４】
行動データ蓄積プログラム１０５は、センサ情報取得部１２０によって取得された利用者の現在位置を蓄積した走行履歴を作成し、作成した走行履歴を行動パタンデータ１６００として、行動データ記憶部１７０に記憶する。
【００３５】
次に、行動パタンについて、図２〜図５を用いて説明する。
【００３６】
図２は、本発明の第１実施形態の交差点における交通流の説明図である。
【００３７】
ナビゲーション装置１０の地図データ記憶部１５０に記憶される地図データの交差点には一意な識別子（例えば、Ｎ０〜Ｎ４）が付与されている。また、この地図データの道路は、二つの交差点を接続するリンクに区分され、リンクごとに一意な識別子（Ｌ０１〜Ｌ４１）が付与されている。
【００３８】
図２では、交差点に流入する流入リンクと交差点から流出する流出リンクとを区分するために、一本のリンクに流入リンクの識別子と流出リンクの識別子とが付与されている。例えば、Ｌ０１によって識別されるリンクは流入リンクであり、Ｌ１０によって識別されるリンクは流出リンクである。
【００３９】
図３は、本発明の第１実施形態の交差点（Ｎ１）における利用者が選択し得る行動パタンの説明図である。
【００４０】
リンク（Ｌ０１）から交差点（Ｎ１）に進入した利用者が選択し得る行動パタンは、リンク（Ｌ１０）に進入する行動パタン（Ａ０）、リンク（Ｌ１２）に進入する行動パタン（Ａ１）、リンク（Ｌ１３）に進入する行動パタン（Ａ２）、及びリンク（Ｌ１４）に進入する行動パタン（Ａ３）である。
【００４１】
ここで、行動パタン（Ａ０）はＵターンを示し、行動パタン（Ａ１）は左折を示し、行動パタン（Ａ２）は右折を示し、行動パタン（Ａ３）は直進を示す。
【００４２】
例えば、行動パタンＡ０は、Ｎ０→Ｌ０１→Ｎ１→Ｌ１０→Ｎ０と示すことができる。
【００４３】
図４は、本発明の第１実施形態の交差点における行動パタンデータ１６００の説明図である。
【００４４】
行動パタンデータ１６００は、交差点ごとの流入量及び流出量を示すデータである。ここで、流入量及び流出量は、行動データ記憶部１７０に記憶されている行動パタンデータ１６００の場合、当該ナビゲーション装置１０を搭載した自動車の走行履歴から算出され、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００の場合、予め設定されている。
【００４５】
行動パタンデータ１６００は、時間帯分類１６０１、利用者分類１６０２、ノードＩＤ１６０３、分岐数１６０４及び進入方向１６０５を含む。
【００４６】
時間帯分類１６０１は、ノードＩＤ１６０３に登録された識別子によって識別される交差点を利用者が通過した時刻の平均である時間帯が登録される。また、時間帯分類１６０１には、時間帯だけでなく、当該交差点を利用者が通過した季節、曜日、祝日か平日か等の情報が登録されてもよい。
【００４７】
利用者分類１６０２には、ナビゲーション装置１０を搭載した自動車の車種、並びに利用者の年齢、性別及び住所等が登録される。
【００４８】
ノードＩＤ１６０３には、当該行動パタンデータ１６００が流入量及び流出量を示す交差点の一意な識別子が登録される。
【００４９】
分岐数１６０４は、ノードＩＤ１６０３に登録された識別子によって識別される交差点を構成するリンクの数が登録される。例えば、図２に示す交差点（Ｎ１）の場合、交差点（Ｎ１）は四つのリンクから構成されているので、分岐数１６０４には、「４」が登録される。
【００５０】
進入方向１６０５は、一つの流入リンク１６０６、及び分岐数１６０４に登録された数分の流出リンクＡ１６０７〜流出リンクＤ１６１０を含む。
【００５１】
流入リンク１６０６は、リンクＩＤ１６０６Ａ及び流入量１６０６Ｂを含む。リンクＩＤ１６０６Ａには、当該流入リンクの一意な識別子が登録される。図２に示す交差点（Ｎ１）の場合、リンクＩＤ１６０６Ａには、リンク（Ｌ０１）の識別子（Ｌ０１）が登録される。流入量１６０６Ｂには、流入リンクから交差点に流入する回数（ｘ０１）が登録される。
【００５２】
流出リンクＡ１６０７は、リンクＩＤ１６０７Ａ及び流出量１６０７Ｂを含む。リンクＩＤ１６０７Ａには、当該流出リンクの一意な識別子が登録される。流出量１６０７Ｂには、交差点からリンクＩＤ１６０７Ａに登録されたリンクの識別子によって識別される流出リンクへ流出する回数（ｙ１２）が登録される。
【００５３】
なお、流出リンクＢ１６０８〜流出リンクＤ１６１０も、流出リンクＡ１６０７と同じ構成であるので、説明を省略する。
【００５４】
なお、進入方向１６０５は、交差点を構成するリンクの数だけ登録される。図４では、リンク（Ｌ０１）が流入リンクである場合の進入方向Ａ１６０５しか図示していないが、リンク（Ｌ２１）が流入リンクである場合の進入方向Ｂ、リンク（Ｌ３１）が流入リンクである場合の進入方向Ｃ、及びリンク（Ｌ４１）が流入リンクである場合の進入方向Ｄも行動パタンデータ１６００に登録されている。
【００５５】
ここで、流入量１６０６Ｂに登録された回数と、流出量１６０７Ｂ〜１６１０Ｂに登録された回数との間には、式１に示す関係が成立している。
（式１）
ｘ０１＝ｙ１２＋ｙ１３＋ｙ１４＋ｙ１０
図５は、本発明の第１実施形態の行動パタン推定データ５００の説明図である。
【００５６】
行動パタン推定データ５００は、行動パタン推定プログラム１０４によって、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００及び行動データ記憶部１７０に記憶されている行動パタンデータ１６００に基づいて生成される。
【００５７】
行動パタン推定データ５００は、各交差点における一つの流入リンクに対する利用者の進路選択の頻度を示す。換言すると、行動パタン推定データ５００は、各交差点における一つ流入リンクから進入可能な流出リンクに進入した頻度を示す。
【００５８】
行動パタン推定データ５００は、行動パタン５０１、流入リンクＩＤ５０２、流出リンクＩＤ５０３、及び出現頻度５０４を含む。
【００５９】
行動パタン５０１は、一つの流入リンクから一つの流出リンクの進路選択を示す行動パタンの一意な識別子が登録される。流入リンクＩＤ５０２には、流入リンクの一意な識別子が登録される。流出リンクＩＤ５０３には、流出リンクの一意な識別子が登録される。
【００６０】
出現頻度５０４には、当該エントリに含まれる流入リンクＩＤ５０２に登録された識別子によって識別される流入リンクから、流出リンクＩＤ５０３に登録された識別子によって識別される流出リンクに進路選択された頻度が登録される。
【００６１】
この進路選択された頻度の算出方法について説明する。
【００６２】
まず、ナビゲーション装置１０は、流入リンクＩＤ５０２に登録された流入リンクの識別子を取得する。そして、ナビゲーション装置１０は、図４に示す行動パタンデータ１６００に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された流入リンクの識別子のうち、取得された流入リンクの識別子と一致するリンクＩＤ１６０６Ａに対応する流入量１６０６Ｂに登録された流入量１６０６Ｂに登録された回数を取得する。
【００６３】
次に、ナビゲーション装置１０は、流入リンクＩＤ５０２に登録された流入リンクの識別子と一致する流入リンク１６０６のリンクＩＤ１６０６Ａが属する進入方向１６０５に含まれる流出リンクＡ〜Ｄ１６０７〜１６１０のリンクＩＤ１６０７Ａ〜１６１０Ａに登録された識別子のうち、流出リンクＩＤ５０３に登録された流出リンクの識別子に対応する流出量に登録された回数を取得する。
【００６４】
そして、ナビゲーション装置１０は、取得された流出量に登録された回数を取得された流入量１６０６Ｂに登録された回数で除算することによって、出現頻度に登録される一つの流入リンクから一つの流出リンクが進路選択された頻度を算出する。
【００６５】
次に、本発明のナビゲーション装置１０に備わる制御部１００によって実行される処理を、図６〜図９を用いて説明する。
【００６６】
図６は、本発明の第１実施形態の経路乗換案内処理のフローチャートである。
【００６７】
まず、入力制御プログラム１０１が入力部１３０を介して利用者が入力した目的地の情報を受け付けて、目的地を設定する（Ｓ１０）。
【００６８】
ここで、利用者から目的地が入力されない場合、入力制御プログラム１０１は、行動データ記憶部１７０に記憶される走行履歴を参照して、目的地を設定してもよい。
【００６９】
次に、経路探索プログラム１０２は、地図データ記憶部１５０に記憶された地図データを参照して、複数の探索条件に基づいて、Ｓ１０の処理で設定された目的地までの複数の経路を探索する。そして、経路探索プログラム１０２は、探索された複数の経路のうち、予め設定された探索条件に基づく一つの経路を案内経路として設定し、他の経路を代替経路として設定する（Ｓ２０）。
【００７０】
なお、Ｓ２０の処理では、利用者からの要求があれば、利用者が、探索された複数の経路から案内経路とする経路を選択できるようになっている。
【００７１】
次に、経路案内プログラム１０３は、Ｓ２０の処理で設定された案内経路に沿って経路案内を開始する。そして、経路案内プログラム１０３は、経路を案内するために出力部１４０から出力する案内データを生成する（Ｓ３０）。
【００７２】
次に、行動パタン推定プログラム１０４は、案内経路及び利用者が進入する可能性の高い経路に進入した場合の目的地までの代替経路を提示する案内ポイントとなる交差点を抽出する（Ｓ４０）。なお、Ｓ４０の処理（案内ポイント抽出処理）については、図７及び図８で詳細を説明する。
【００７３】
次に、経路探索プログラム１０２は、抽出された案内ポイントで利用者が案内経路から他の経路に進入した場合の目的地までの代替経路を探索する（Ｓ５０）。
【００７４】
次に、制御部１００は、Ｓ５０の処理で代替経路が探索されたか否かを判定する（Ｓ６０）。
【００７５】
Ｓ５０の処理で代替経路が探索されなかったと、Ｓ６０の処理で判定された場合、当該案内ポイントで他の経路に進入してもＳ１０の処理で設定された目的地に到達できないので、Ｓ４０の処理に戻る。
【００７６】
一方、Ｓ５０の処理で代替経路が探索されたと、Ｓ６０の処理で判定された場合、経路案内プログラム１０３は、Ｓ５０の処理で探索された代替経路と案内経路とを提示するための経路乗換案内情報を生成する（Ｓ７０）。
【００７７】
次に、制御部１００は、利用者が目的地に到達したか否かを判定するために、利用者の現在位置から目的地までの距離を算出し、算出した距離が所定値以内であるか否かを判定する（Ｓ８０）。
【００７８】
Ｓ８０の処理で、利用者の現在位置から目的地までの距離が所定値以内でないと判定された場合、利用者は目的地に到達していないので、Ｓ４０の処理に戻る。一方、Ｓ８０の処理で、利用者の現在位置から目的地までの距離が所定値以内であると判定された場合には、利用者は目的地に到達したので、経路乗換案内処理を終了する。
【００７９】
図７は、本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【００８０】
まず、行動パタン推定プログラム１０４は、案内経路上に位置する交差点のうち、利用者の現在位置から近い順に一つ交差点を選択する（Ｓ１１）。
【００８１】
次に、行動パタン推定プログラム１０４は、行動パタン辞書部１６０に記憶された行動パタンデータ１６００に基づいて、Ｓ１１の処理で選択された交差点の行動パタン推定データ５００を生成する（Ｓ１２）。
【００８２】
行動パタン推定データ５００を生成する処理について、具体的に説明する。
行動パタン辞書部１６０に記憶された行動パタンデータ１６００のノードＩＤ１６０３に登録された識別子が、Ｓ１１の処理で選択された交差点の識別子と一致する行動パタンデータ１６００を選択する。
【００８３】
行動パタン推定プログラム１０４は、センサ情報取得部１２０に利用者の現在位置を取得させる。そして、行動パタン推定プログラム１０４は、取得された現在位置に基づいて、Ｓ１１の処理で選択された交差点の流入リンクを特定する。
【００８４】
次に、行動パタン推定プログラム１０４は、行動パタン辞書部１６０に記憶された行動パタンデータ１６００に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された識別子が、特定された流入リンクの識別子と一致する流入リンク１６０６が含まれる進入方向１６０５を選択する。
【００８５】
そして、行動パタン推定プログラム１０４は、選択した進入方向１６０５に含まれる流入リンク１６０６のリンクＩＤ１６０６Ａに登録された識別子及び流入量１６０６Ｂに登録された回数を取得する。また、行動パタン推定プログラム１０４は、選択した進入方向１６０５に含まれる流出リンク１６０７〜１６１０のリンクＩＤ１６０７Ａ〜１６１０Ａに登録された識別子及び流出量１６０７Ｂ〜１６１０Ｂに登録された回数を取得する。
【００８６】
そして、行動パタン推定プログラム１０４は、取得した流入リンクの識別子を流入リンクＩＤ５０２に格納し、取得した流出リンクの識別子を流出リンクＩＤ５０３に格納する。そして、各エントリの出現頻度５０４には、流出リンクの流出量を流入リンクの流入量で除算した値が格納される。
【００８７】
以上によって、図５に示す行動パタン推定データ５００が生成される。
【００８８】
次に、行動パタン推定プログラム１０４は、行動データ記憶部１７０に記憶された行動パタンデータ１６００に基づいて、Ｓ１１の処理で選択された交差点の行動パタン推定データ５００を生成する（Ｓ１３）。
【００８９】
なお、Ｓ１３の処理の具体的な説明は、Ｓ１２の処理の具体的な説明と同様であるので、説明を省略する。
【００９０】
次に、行動パタン推定プログラム１０４は、Ｓ１２の処理で生成された行動パタン推定データ５００及びＳ１３の処理で生成された行動パタン推定データ５００に基づいて、行動パタンを推定する（Ｓ１４）。
【００９１】
具体的には、行動パタン推定プログラム１０４は、式２を計算することによって、Ｓ１２の処理で生成された行動パタン推定データ５００の出現頻度５０４に登録された頻度と、Ｓ１３の処理で生成された行動パタン推定データ５００の出現頻度５０４に登録された頻度と、を重み付けた出現頻度を算出する。
（式２）
Ｐｉ＝（１−β）・ｐｉ＋β・ｑｉ（ｉ＝０，１，２，３）
Ｐｉは、行動パタンＡｉの出現頻度を示し、ｐｉは、Ｓ１２の処理で生成された行動パタン推定データ５００の出現頻度５０４を示し、ｑｉは、Ｓ１３の処理で生成された行動パタン推定データ５００の出現頻度５０４を示す。また、βは、０と１との間の値の重み付けパラメータであり、実際の行動データから学習できるようにしてもよい。
【００９２】
また、ナビゲーション装置１０を搭載した自動車の走行距離が長くなるにつれて、つまり行動データ記憶部１７０に記憶された行動パタンデータ１６００の容量が大きくなるにつれて、βの値が増大する。
【００９３】
つまり、ナビゲーション装置１０が利用者の自動車に搭載された直後の状態では、利用者の走行履歴が蓄積されていないので、予め設定されている行動パタン辞書部１６０に記憶されている行動パタンデータ１６００に基づいて生成された行動パタン推定データ５００の出現頻度の重み付けを大きくする。
【００９４】
一方、ナビゲーション装置１０が利用者の自動車に搭載され、利用者の走行履歴がある程度蓄積されていれば、行動データ記憶部１７０に記憶された行動パタンデータ１６００は利用者自身の走行履歴から生成されるデータであるため、行動データ記憶部１７０に記憶された行動パタンデータ１６００は、行動パタン辞書部１６０に記憶されている行動パタンデータ１６００よりも、信頼度が高い。
【００９５】
このため、利用者の走行履歴がある程度蓄積されている場合には、行動データ記憶部１７０に記憶されている行動パタンデータ１６００に基づいて生成された行動パタン推定データ５００の出現頻度の重み付けを大きくする。
【００９６】
次に、行動パタン推定プログラム１０４は、Ｓ１４の処理で算出された出現頻度に基づいて、Ｓ１１の処理で選択された交差点が案内ポイントであるか否かを判定する（Ｓ１５）。なお、Ｓ１５の処理（案内ポイント抽出処理）については、図７で詳細を説明する。
【００９７】
Ｓ１１の処理で選択された交差点が案内ポイントでないと、Ｓ１５の処理で判定された場合、Ｓ１１の処理に戻る。
【００９８】
一方、Ｓ１１の処理で選択された交差点が案内ポイントであると、Ｓ１５の処理で判定された場合、案内ポイント抽出処理を終了する。
【００９９】
図８は、本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【０１００】
まず、行動パタン推定プログラム１０４は、図７に示すＳ１４の処理で算出された出現頻度のうち、最大の出現頻度を取得し、取得した最大の出現頻度が所定値より大きいか否かを判定する（Ｓ１）。
【０１０１】
Ｓ１の処理で、最大の出現頻度が所定値以下であると判定された場合、案内ポイント抽出処理を終了する。
【０１０２】
一方、Ｓ１の処理で、最大の出現頻度が所定値よりも大きいと判定された場合、行動パタン推定プログラム１０４は、最大の出現頻度の流出リンクが案内経路上に位置するか否かを判定する（Ｓ２）。
【０１０３】
Ｓ２の処理で、最大の出現頻度の流出リンクが案内経路上に存在しないと判定された場合、行動パタン推定プログラム１０４は、当該交差点では、利用者が案内経路上に位置しないリンクを進路として選択する可能性が高いので、当該交差点を案内ポイントとして抽出し（Ｓ３）、案内ポイント抽出処理を終了する。
【０１０４】
一方、Ｓ２の処理で、最大の出現頻度の流出リンクが案内経路上に存在すると判定された場合、行動パタン推定プログラム１０４は、利用者が進路として選択する可能性の高いリンクが案内経路上に位置するため、経路乗換案内を提示する必要がないので、Ｓ４の処理に進む。
【０１０５】
行動パタン推定プログラム１０４は、式３を満たす流出リンクが存在するか否かを判定する（Ｓ４）。
（式３）
Ｐｎ／Ｐａ＞αｔｈ
Ｐｎは、ある行動パタンＡｎの出現頻度を示し、Ｐａは、最大の出現頻度を示し、αｔｈは、所定の閾値を示す。
【０１０６】
つまり、Ｓ４の処理では、行動パタン推定プログラム１０４は、ある流出リンクの出現頻度を最大の出現頻度で除算した値が所定値よりも大きいか否かを判定する。
【０１０７】
Ｓ４の処理では、最大の出現頻度が所定値よりも大きいにも係らず、当該最大の出現頻度の流出リンクが案内経路上に位置するため、この交差点が案内ポイントとして抽出されなかった場合、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路として選択する可能性が高い流出リンクが存在する可能性がある。Ｓ４の処理は、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路選択する可能性の高い流出リンクが存在するか否かを判定する処理である。
【０１０８】
Ｓ４の処理で、式３を満たす流出リンクが存在すると判定された場合、最大の出現頻度の流出リンクが案内経路上に位置するため、式３を満たす流出リンクは、案内経路上に位置しないリンクであるので、行動パタン推定プログラム１０４は、当該交差点を案内ポイントとして抽出して（Ｓ３）、案内ポイント抽出処理を終了する。
【０１０９】
一方、Ｓ４の処理で、式３を満たす流出リンクが存在しないと判定された場合、最大の出現頻度の流出リンク以外の流出リンクのうち、利用者が進路選択する可能性の高い流出リンクが存在しないので、案内ポイント抽出処理を終了する。
【０１１０】
図９は、本発明の第１実施形態の行動データ蓄積プログラム１０５によって実行される行動データ蓄積処理のフローチャートである。
【０１１１】
まず、行動データ蓄積プログラム１０５は、センサ情報取得部１２０を介してセンサ情報を取得する（Ｓ２１）。センサ情報には、ＧＰＳ及び車速センサ等から取得されたナビゲーション装置１０の現在位置情報が含まれる。
【０１１２】
次に、行動データ蓄積プログラム１０５は、Ｓ２１の処理で取得したセンサ情報からノイズを除去するために、センサ情報を補正する（Ｓ２２）。例えば、マップマッチングによる補正がある。
【０１１３】
次に、行動データ蓄積プログラム１０５は、Ｓ２２の処理で補正したセンサ情報を、行動データ記憶部１７０に記憶する形式に変換する（Ｓ２３）。具体的には、行動パタンデータ蓄積プログラム１０５は、センサ情報に含まれる現在位置情報を時間と対応付けて、走行履歴を生成する。そして、行動データ蓄積プログラム１０５は、図４に示す行動データ記憶部１７０に記憶される行動パタンデータ１６００に、生成した走行履歴を反映する。
【０１１４】
なお、行動データ蓄積プログラム１０５は、Ｓ２２の処理で補正したセンサ情報をサンプリング及びデータ圧縮等をしてから、走行履歴を生成してもよい。
【０１１５】
次に、行動データ蓄積プログラム１０５は、走行履歴が反映された行動パタンデータ１６００を行動データ記憶部１７０に記憶する（Ｓ２４）。
【０１１６】
次に、経路案内プログラム１０３によって利用者に提供される経路乗換案内を図１０〜図１４を用いて説明する。
【０１１７】
図１０は、本発明の第１実施形態の出力部１４０を介して利用者に提示される案内経路に沿った経路案内の説明図である。
【０１１８】
出発地Ｏ及び目的地Ｄが入力部１３０を介してナビゲーション装置１０に入力された場合、図６に示す経路乗換案内処理のＳ２０の処理で、案内経路Ｒ１が設定される。そして、Ｓ３０の処理で案内経路Ｒ１に沿った経路案内が開始される。そして、Ｓ４０の処理で案内経路Ｒ上に位置する交差点（Ｎ１〜Ｎ５）のうち、利用者の現在位置から近い順に交差点が選択され、選択された交差点が案内ポイントであるか否かが判定される。
【０１１９】
交差点Ｎ１において、流入リンクは「１」であり、流出リンクは「０」、「２」、「３」、「４」である。交差点Ｎ１において、流出リンク「０」が進路として選択された場合、利用者がＵターンすることを示し、流出リンク「２」が進路として選択された場合、利用者が左折することを示し、流出リンク「３」が進路として選択された場合、利用者が直進することを示し、流出リンク「４」が進路として選択された場合、利用者が右折することを示す。
【０１２０】
図１１Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１２１】
図６に示す経路乗換案内所のＳ４０の処理で、交差点Ｎ１が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ１から目的地までの代替経路（Ｒ２及びＲ３）が探索される。
【０１２２】
なお、代替経路Ｒ２は交差点（Ｎ１）を左折した場合の目的地までの経路であり、代替経路Ｒ３は交差点（Ｎ１）を右折した場合の目的地までの経路であり、案内経路Ｒ１は交差点（Ｎ１）を直進した場合の目的地までの経路である。
【０１２３】
また、図１１Ａに示す「５」は、利用者の現在位置を示す。
【０１２４】
図１１Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）付近で提示される経路乗換案内画面の説明図である。
【０１２５】
図１１Ｂの経路乗換案内画面は、利用者が交差点（Ｎ１）に到達する前に出力部１４０から出力される。
【０１２６】
経路乗換案内画面は、案内経路及びＳ５０の処理で探索された代替経路の全体を表示する全体表示画面６、及び案内ポイントとして抽出された交差点（Ｎ１）付近を拡大した拡大表示画面７を含む。
【０１２７】
なお、図１１Ｂは、本発明を限定するものではなく、拡大表示画面７は、通常スケールの地図表示であってもよい。全体表示画面６及び拡大表示画面７に分割した２画面構成にする必要はなく、どちらか一方がポップアップ表示されるようにしてもよい。
【０１２８】
また、全体表示画面６及び拡大表示画面７のいずれか一方の１画面表示としてもよい。拡大表示画面７の代わりに全体表示画面６が１画面で表示されている場合、利用者の現在位置と交差点（Ｎ１）との距離が所定値以下になった場合に、拡大表示画面７が表示されるようにしてもよい。
【０１２９】
さらに、経路乗換案内画面には、利用者にとって経路選択の判断材料となる情報（例えば、目的地までの所要時間、及び目的地までかかる料金等）も表示されるが、図１１Ｂでは省略している。
【０１３０】
図１１Ａにおいて、交差点Ｎ１を直進した場合について図１２Ａ及び１２Ｂを用いて説明する。
【０１３１】
図１２Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第２交差点（Ｎ２）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１３２】
利用者は、図１１Ａの交差点（Ｎ１）を直進している。
【０１３３】
図６に示す経路乗換案内所のＳ４０の処理で、交差点（Ｎ２）が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ２から目的地までの代替経路（Ｒ４）が探索される。
【０１３４】
なお、代替経路（Ｒ４）は、交差点（Ｎ２）を左折した場合の目的地までの経路である。
【０１３５】
図１２Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第２交差点（Ｎ２）付近で提示される経路乗換案内画面の説明図である。
【０１３６】
経路乗換案内画面に含まれる全体表示画面６では、案内経路Ｒ１及び交差点（Ｎ）２）から目的地までの代替経路Ｒ４の全体が表示される。また、拡大表示画面７では、交差点（Ｎ２）付近における案内経路Ｒ１及び代替経路Ｒ４が拡大して表示される。
【０１３７】
図１１Ａにおいて、利用者が、交差点Ｎ２を左折して、代替経路Ｒ２に進入した場合について図１３Ａ〜図１４Ｂを用いて説明する。
【０１３８】
図１３Ａは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）を左折した場合の経路案内の説明図である。
【０１３９】
図１３Ａは、利用者が交差点（Ｎ１）を左折して、案内経路Ｒ２へ進入していることを示す。
【０１４０】
図１３Ｂは、本発明の第１実施形態の案内経路Ｒ１上に位置する第１交差点（Ｎ１）を左折した場合に、代替経路（Ｒ２）が案内経路に設定された場合の経路案内の説明図である。
【０１４１】
利用者が交差点（Ｎ１）を左折して、代替経路（Ｒ２）に進入した場合、ナビゲーション装置１０は、代替経路（Ｒ２）を案内経路として設定し、交差点（Ｎ１）を出発地として、案内経路（Ｒ２）に沿って経路案内を開始する。
【０１４２】
図１４Ａは、本発明の第１実施形態の案内経路Ｒ２上に位置する第１交差点（Ｎ６）が案内ポイントとして抽出された場合の経路案内の説明図である。
【０１４３】
図６に示す経路乗換案内所のＳ４０の処理で、交差点Ｎ６が案内ポイントとして抽出された場合、Ｓ５０の処理で交差点Ｎ１から目的地までの代替経路（Ｒ５）が探索される。
【０１４４】
なお、代替経路Ｒ５は交差点（Ｎ６）を右折した場合の目的地までの経路であり、案内経路Ｒ２は交差点（Ｎ６）を直進した場合の目的地までの経路である。
【０１４５】
図１４Ｂは、本発明の第１実施形態の案内経路Ｒ２上に位置する第１交差点（Ｎ６）付近で提示される経路乗換案内画面の説明図である。
【０１４６】
経路乗換案内画面に含まれる全体表示画面６では、案内経路Ｒ２及び交差点（Ｎ）６）から目的地までの代替経路Ｒ５の全体が表示される。また、拡大表示画面７では、交差点（Ｎ６）付近における案内経路Ｒ２及び代替経路Ｒ５が拡大して表示される。
【０１４７】
（第１実施形態の変形例）
第１実施形態の変形例は、複数の経路が探索されて、探索された複数の経路の分岐点のうち、分岐点で分岐する経路の交通量が、利用者が走行している経路の交通量よりも多い分岐点が案内ポイントとして抽出され、抽出された分岐点で経路乗換案内を提示する。これによって、利用者は、知らなかった経路を知ることができるようになる。
【０１４８】
図１５は、本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでのリンク、分岐点の説明図である。
【０１４９】
リンク（Ｌ１〜Ｌ６）は、出発地Ｏから目的地Ｄまでの間にある進行可能なリンクである。なお、リンクは、出発地Ｏから目的地Ｄまでの交通流を示すだけでよいので、一方向のみのリンクを示している。
【０１５０】
分岐点（Ｎ１〜Ｎ３）は、リンクが分岐する交差点（Ｎ１及びＮ３）及びリンクが合流する交差点（Ｎ２）である。
【０１５１】
出発地Ｏから分岐点Ｎ１まではリンク（Ｌ１）で接続されている。分岐点Ｎ１で、リンクＬ２とリンクＬ４とが分岐する。リンクＬ２は、分岐点Ｎ１から分岐点Ｎ２までを接続し、リンクＬ４は、分岐点Ｎ１から分岐点Ｎ４までを接続する。
【０１５２】
分岐点Ｎ３で、リンクＬ５及びリンクＬ６は、分岐点Ｎ３から分岐点Ｎ２までを接続するが、経路が相違する。分岐点Ｎ２で、リンクＬ２、Ｌ５、及びＬ６が合流する。リンクＬ３は、分岐点Ｎ２から目的地Ｄまでを接続する。
【０１５３】
なお、複数の利用者が選択する可能性の高い施設のみが目的地Ｄとして登録されてもよい。また、複数の利用者の経路が合流する地点のみが出発地Ｏとして登録されてもよい。
【０１５４】
なお、出発地Ｏ及び目的地Ｄの組合せに対する経路選択行動パタンは、少数派も含めると実際には多数の行動パタンが存在すると考えられる。しかしながら、行動パタンをモデル化する目的では冗長となる。そこで、出現頻度の高い上位の行動パタンに対応するリンクのみを抽出するものとする。また、出発地Ｏ及び目的地Ｄの組合せについても、実際には多数の組合せが存在している。
【０１５５】
図１６は、本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでの経路の説明図である。
【０１５６】
出発地Ｏから目的地Ｄまで到達可能な経路は、三つの経路Ｂ１〜Ｂ３が存在する。これらの経路Ｂ１〜Ｂ３が利用者によって選択され得る行動パタンとなる。
【０１５７】
経路Ｂ１は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ２→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。経路Ｂ２は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ４→分岐点Ｎ３→リンクＬ５→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。経路Ｂ３は、出発地Ｏ→リンクＬ１→分岐点Ｎ１→リンクＬ４→分岐点Ｎ３→リンクＬ６→分岐点Ｎ２→リンクＬ３→目的地Ｄとして表現される。
【０１５８】
このように、経路（行動パタン）は、分岐点（ノード）及びリンクの遷移として表現される。
【０１５９】
図１７は、本発明の第１実施形態の行動パタン辞書部１６０及び行動データ記憶部１７０に記憶される経路交通量データ１７００の説明図である。なお、第１実施形態の変形例の経路交通量データ１７００の構成のうち、第１実施形態の経路交通量データ１７００と同じ構成については、同じ符号を付与し、説明を省略する。
【０１６０】
経路交通量データ１７００は、多数の利用者から収集された走行履歴データのような行動データを統計処理によって加工したプローブ統計データを用いることを想定している。
【０１６１】
経路交通量データ１７００は、時間帯分類１６０１、利用者分類１６０２、出発地１７０１、目的地１７０２、交通量１７０３、及び経路Ａ１７０４〜Ｃ１７０６を含む。
【０１６２】
時間帯分類１６０１及び利用者分類１６０２は、図４に示す第１実施形態の経路交通量データ１７００の時間帯分類１６０１及び利用者分類１６０２と同じであるので、説明を省略する。
【０１６３】
出発地１７０１には、ナビゲーション装置１０によって設定された出発地が登録される。目的地１７０２には、ナビゲーション装置１０によって設定された目的地が登録される。交通量１７０３には、出発地から目的地までの交通量が登録される。交通量は、ナビゲーション装置１０が、行動パタン辞書部１６０に記憶される行動パタンデータ１６００の各経路上に位置する交差点の流入量を加算することによって算出される。
【０１６４】
経路Ａ１７０４〜経路Ｃ１７０６には、出発地から目的地まで到達し得る経路がそれぞれ登録される。経路Ａ１７０４は図１６に示す経路Ｂ１を示し、経路Ｂ１７０５は図１６に示す経路Ｂ２を示し、経路Ｃ１７０６は図１６に示す経路Ｂ３を示す。
【０１６５】
経路Ａ１７０４〜経路Ｃ１７０６は、それぞれリンク列１７０４Ａ〜１７０６Ａ及び交通量１７０６Ａ〜１７０６Ｃを含む。
【０１６６】
リンク列１７０４Ａ〜１７０６Ａには、それぞれの経路を構成する出発地から目的地までのリンクが列として登録される。交通量１７０４Ｂ〜１７０６Ｂには、それぞれの経路の交通量が登録される。
【０１６７】
ここで、交通量１７０３に登録される交通量ｘ０と、交通量１７０４Ｂ〜交通量１７０６Ｂに登録される交通量ｙ１〜ｙ３との間には、式４に示す関係が成立している。
（式４）
ｘ０＝ｙ１＋ｙ２＋ｙ３
図１８は、本発明の第１実施形態の変形例の行動パタン推定データ５００の説明図である。なお、本発明の第１実施形態の変形例の行動パタン推定データ５００の構成のうち、第１実施形態の行動パタン推定データ５００と同じ構成については、同じ符号を付与し、説明を省略する。
【０１６８】
行動パタン推定データ５００は、行動パタン５０１、リンク列１８０１、及び出現頻度５０４を含む。
【０１６９】
行動パタン５０１は、図５に示す第１実施形態の行動パタン推定データ５００の行動パタン５０１と同じなので、説明を省略する。
【０１７０】
リンク列１８０１には、経路交通量データ１７００のリンク列１７０４Ａ〜１７０６Ａに登録されたリンク列が登録される。
【０１７１】
出現頻度５０４には、各リンク列１７０４Ａ〜１７０６Ａに登録されたリンク列に対応する図１７に示す交通量１７０４に登録された交通量を交通量１７０３に登録された交通量で除算することによって算出される出現頻度が登録される。
【０１７２】
次に、第１実施形態の変形例の経路乗換案内処理について説明する。本発明の第１実施形態の変形例の経路乗換案内処理は図６に示す第１実施形態の経路乗換案内処理とほぼ同じであり、相違する処理のみ説明する。
【０１７３】
Ｓ２０の処理では、経路探索プログラム１０２は、目的地から出発地までの複数の経路を探索した後、探索された経路を、行動パタン辞書部１６０に記憶されている経路交通量データ１７００に登録する。また、経路探索プログラム１０２は複数の経路を探索した後に、探索された複数の経路の分岐点となる交差点を探索する。
【０１７４】
具体的には、経路探索プログラム１０２は、探索された経路の識別子を経路１７０４〜１７０６に登録し、各経路のリンク列をリンク列１７０４Ａ〜１７０６Ａに登録する。次に、経路探索プログラム１０２は、行動パタン辞書部１６０に記憶されている予め設定された行動パタンデータ１６００を参照して、探索された各経路の交通量を算出して、算出された各経路の交通量を対応する経路１７０４〜１７０６の交通量１７０４Ｂ〜１７０６Ｂに登録する。
【０１７５】
これによって、予め設定された行動パタンデータ１６００に基づいて、経路交通量データ１７００が生成される。
【０１７６】
そして、Ｓ３０の処理で、経路案内プログラム１０３は、案内経路に沿って経路案内を開始する。
【０１７７】
次に、Ｓ４０の処理で、行動パタン推定プログラム１０４は、案内ポイントを抽出する。Ｓ４０の処理を実行した後、ナビゲーション装置１０は、Ｓ５０及びＳ６０の処理を実行しないで、Ｓ７０及びＳ８０の処理を実行して経路乗換案内処理を終了する。
【０１７８】
Ｓ４０の案内ポイント抽出処理について説明する。図１９は、本発明の第１実施形態の変形例の案内ポイント抽出処理のフローチャートである。
【０１７９】
まず、行動パタン推定プログラム１０４は、Ｓ２０の処理で探索された分岐点のうち、利用者の現在位置から近い順に一つ分岐点を選択する（Ｓ１９１）。
【０１８０】
次に、行動パタン推定プログラム１０４は、センサ情報取得部１２０から利用者の現在位置情報を含むセンサ情報を取得し、利用者が現在走行している経路を特定する。そして、行動パタン推定プログラム１０４は、図１８に示す行動パタン推定データ１８００を参照し、特定された現在走行中の経路の出現頻度Ｐｎを取得する（Ｓ１９２）。
【０１８１】
次に、行動パタン推定プログラム１０４は、Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在するか否かを判定する（Ｓ１９３）。
【０１８２】
Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在すると、Ｓ１９３の処理で判定された場合、Ｓ１９１の処理で選択された分岐点を案内ポイントとして抽出して（Ｓ１９４）、案内ポイント抽出処理を終了する。
【０１８３】
一方、Ｓ１９１の処理で選択された分岐点で分岐する経路の出現頻度のうち、Ｓ１９２の処理で取得された出現頻度よりも大きい出現の経路が存在しないと、Ｓ１９３の処理で判定された場合、案内ポイント抽出処理を終了する。
【０１８４】
以上によって、利用者が走行している経路が、同じ目的地に向かう他の多くの利用者が走行している経路と異なる場合であっても、多くの利用者が走行している経路の分岐点で経路乗換案内を提示するので、多くの利用者と同じ経路を走行できる。
【０１８５】
（第２実施形態）
次に、本発明の第２実施形態を図２０〜図２２を用いて説明する。
【０１８６】
本発明の第２実施形態の計算機システムは、他の利用者の走行履歴を収集して、他の利用者の走行履歴に基づく行動パタンデータ１６００を生成して、生成された行動パタンデータ１６００を各利用者のナビゲーション装置１０に送信するプローブデータサーバ３０、及びナビゲーション装置１０を備える。
【０１８７】
図２０は、本発明の第２実施形態の計算機システムの説明図である。
【０１８８】
ナビゲーション装置１０について説明する。第２実施形態のナビゲーション装置１０の構成のうち、第１実施形態のナビゲーション装置１０と同じ構成については、同じ符号を付与し、説明を省略する。
【０１８９】
無線通信部１１０は、ナビゲーション装置１０を無線通信ネットワーク２０に接続する。これによって、ナビゲーション装置１０は、無線通信ネットワーク２０に接続されたプローブデータサーバ３０にアクセスできる。
【０１９０】
行動データ送信プログラム１０６は、利用者の現在位置を行動データとしてプローブデータサーバ３０に送信する。行動パタンデータ要求プログラム１０７は、行動パタンデータ３６００をプローブデータサーバ３０に要求する行動パタンデータ要求をプローブデータサーバ３０に送信する。
【０１９１】
プローブデータサーバ３０について説明する。
【０１９２】
プローブデータサーバ３０は、制御部３００、無線通信部３１０、地図データ記憶部３５０、行動パタン辞書部３６０、及び行動データ記憶部３７０を備える。
【０１９３】
制御部３００は、プローブデータサーバ３０の全体を制御する。具体的には、制御部３００は、図示しないプロセッサ及びメモリを備える。メモリには、プロセッサによって実行される各種プログラムが記憶される。メモリには、行動データ蓄積プログラム３０１、行動データ解析プログラム３０２、行動パタンデータ更新プログラム３０３、及び行動パタンデータ検索プログラム３０４が記憶される。なお、メモリに記憶される各種プログラム３０１〜３０４の処理については、後述する。
【０１９４】
無線通信部３１０は、プローブデータサーバ３０を無線通信ネットワーク２０に接続する。これによって、プローブデータサーバ３０は、無線通信ネットワーク２０に接続されたナビゲーション装置１０にアクセスできる。
【０１９５】
地図データ記憶部３５０、は、第１実施形態のナビゲーション装置１０の地図データ記憶部１５０と同じであるので説明を省略する。
【０１９６】
地図データ記憶部３５０には、地図データが記憶される。行動パタン辞書部３６０には、プローブデータサーバ３０が行動データを収集したすべてのナビゲーション装置１０の利用者の走行履歴に基づいて生成された行動パタンデータ３６００が記憶される。行動データ記憶部３７０には、プローブデータサーバ３０が行動データを収集したナビゲーション装置１０の各利用者の走行履歴に基づいて生成された行動パタンデータ３６００が利用者ごとに記憶される。
【０１９７】
次に、制御部３００に備わるメモリに記憶される各種プログラム３０１〜３０４について、説明する。
【０１９８】
行動データ蓄積プログラム３０１は、複数の利用者の現在位置を蓄積した走行履歴を作成し、作成した走行履歴を蓄積する。
【０１９９】
行動データ解析プログラム３０２は、行動データ蓄積プログラム３０１によって蓄積された走行履歴に基づいて行動パタンデータ３６００を生成する。
【０２００】
行動パタンデータ更新プログラム３０３は、行動データ解析プログラムによって生成された行動パタンデータ３６００に基づいて、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００を更新する。
【０２０１】
行動パタンデータ検索プログラム３０４は、ナビゲーション装置１０からの行動パタンデータ要求に対応する行動パタンデータ３６００を、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００から検索する。
【０２０２】
次に、計算機システムで実行される行動データ送信処理について説明する。図２１は、本発明の第２実施形態の行動データ送信処理のシーケンス図である。
【０２０３】
まず、ナビゲーション装置１０は、センサ情報取得部１２０から利用者の現在位置情報を取得し、取得した現在位置情報を行動データとしてプローブデータサーバ３０に送信する（Ｓ３１）。
【０２０４】
なお、行動データは、所定の周期で送信されてもよいし、一回の走行が終了したタイミングで送信されてもよい。
【０２０５】
プローブデータサーバ３０は、行動データを受信する（Ｓ３１）。次に、プローブデータサーバ３０の行動データ蓄積プログラム３０１は、Ｓ３１の処理で受信した行動データを行動データ記憶部３７０に記憶し、行動データに基づいて走行履歴を生成する（Ｓ３３）。
【０２０６】
次に、プローブデータサーバ３０の行動データ解析プログラム３０２は、行動データ蓄積プログラム３０１によって生成された走行履歴に基づいて、行動パタンデータ３６００を生成する（Ｓ３４）。
【０２０７】
次に、プローブデータサーバ３０の行動パタンデータ更新プログラム３０３は、行動データ解析プログラム３０２によって生成された行動パタンデータ３６００を、行動パタン辞書部３６０及び行動データ記憶部３７０に記憶された行動パタンデータ３６００に反映する（Ｓ３５）。
【０２０８】
なお、Ｓ３３及びＳ３４の処理は、所定のタイミングでバッチ処理的に実行される。
【０２０９】
次に、計算機システムによって実行される行動パタンデータ配信処理について説明する。図２２は、本発明の第２実施形態の行動パタンデータ配信処理のシーケンス図である。
【０２１０】
まず、ナビゲーション装置１０の行動パタンデータ要求プログラム１０７は、行動パタンデータ要求をプローブデータサーバ３０に送信する（Ｓ４１）。
【０２１１】
プローブデータサーバ３０は、行動パタンデータ要求を受信した場合、行動パタンデータ検索プログラム３０４を起動する。行動パタンデータ検索プログラム３０４は、行動データ記憶された行動パタンデータ３６００から、行動パタンデータ要求を送信したナビゲーション装置１０の利用者に対応する行動パタンデータ３６００を検索する（Ｓ４２）。
【０２１２】
そして、プローブデータサーバ３０は、行動データ記憶部３７０から検索された行動パタンデータ３６００、及び行動パタン辞書部３６０に記憶された行動パタンデータ３６００をナビゲーション装置１０に送信する（Ｓ４３）。
【０２１３】
ナビゲーション装置１０は、行動パタンデータ要求に対する応答である行動パタンデータを受信すると（Ｓ４４）、行動データ記憶部３７０から検索された行動パタンデータ３６００に基づいて、行動データ記憶部１７０に記憶された行動パタンデータ１６００を更新し、行動パタン辞書部３６０に記憶された行動パタンデータ３６００に基づいて行動パタン辞書部１６０に記憶された行動パタンデータ１６００を更新する。
【０２１４】
なお、ナビゲーション装置１０の行動パタンデータ１６００の更新範囲は、例えば、一括で全領域を更新する方式、適当な領域を指定して更新する方式、及び交差点毎に指定して更新する方式等がある。
【図面の簡単な説明】
【０２１５】
【図１】本発明の第１実施形態のナビゲーション装置の構成を示すブロック図である。
【図２】本発明の第１実施形態の交差点における交通流の説明図である。
【図３】本発明の第１実施形態の交差点における利用者が選択し得る行動パタンの説明図である。
【図４】本発明の第１実施形態の交差点における行動パタンデータの説明図である。
【図５】本発明の第１実施形態の行動パタン推定データの説明図である。
【図６】本発明の第１実施形態の経路乗換案内処理のフローチャートである。
【図７】本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【図８】本発明の第１実施形態の案内ポイント抽出処理のフローチャートである。
【図９】本発明の第１実施形態の行動データ蓄積プログラムによって実行される行動データ蓄積処理のフローチャートである。
【図１０】本発明の第１実施形態の出力部を介して利用者に提示される案内経路に沿った経路案内の説明図である。
【図１１Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１１Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点付近で提示される経路乗換案内画面の説明図である。
【図１２Ａ】本発明の第１実施形態の案内経路上に位置する第２交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１２Ｂ】本発明の第１実施形態の案内経路上に位置する第２交差点付近で提示される経路乗換案内画面の説明図である。
【図１３Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点を左折した場合の経路案内の説明図である。
【図１３Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点を左折した場合に、代替経路が案内経路に設定された場合の経路案内の説明図である。
【図１４Ａ】本発明の第１実施形態の案内経路上に位置する第１交差点が案内ポイントとして抽出された場合の経路案内の説明図である。
【図１４Ｂ】本発明の第１実施形態の案内経路上に位置する第１交差点付近で提示される経路乗換案内画面の説明図である。
【図１５】本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでのリンク、分岐点の説明図である。
【図１６】本発明の第１実施形態の変形例の出発地Ｏから目的地Ｄまでの経路の説明図である。
【図１７】本発明の第１実施形態の行動パタン辞書部及び行動データ記憶部に記憶される経路交通量データの説明図である。
【図１８】本発明の第１実施形態の変形例の行動パタン推定データの説明図である。
【図１９】本発明の第１実施形態の変形例の案内ポイント抽出処理のフローチャートである。
【図２０】本発明の第２実施形態の計算機システムの説明図である。
【図２１】本発明の第２実施形態の行動データ送信処理のシーケンス図である。
【図２２】本発明の第２実施形態の行動パタンデータ配信処理のシーケンス図である。
【符号の説明】
【０２１６】
１０ ナビゲーション装置
３０ プローブデータサーバ
１００ 制御部
１０１ 入力制御部
１０２ 経路探索プログラム
１０３ 経路案内プログラム
１０４ 行動パタン推定プログラム
１０５ 行動データ蓄積プログラム
１１０ 無線通信部
１２０ センサ情報取得部
１３０ 入力部
１４０ 出力部
１５０ 地図データ記憶部
１６０ 行動パタン辞書部
１７０ 行動データ記憶部
【特許請求の範囲】
【請求項１】
地図データを記憶する地図データ記憶手段と、
前記地図データを使用して経路を探索する探索手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、
前記行動パタンデータ記憶手段から読み出された前記行動パタンデータを使用して前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、
前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、
前記流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、
前記代替経路をユーザに対して出力する代替経路出力手段と、を備えることを特徴とするナビゲーション装置。
【請求項２】
前記案内ポイント抽出手段は、
前記経路上に存在する交差点における前記行動パタンデータを使用して、前記交差点で前記進行頻度が最も多い流出リンクを特定し、
前記特定された流出リンクの進行頻度が第１の所定値以上であって、且つ前記特定された流出リンクが前記経路と異なる場合に、前記交差点を前記案内ポイントとして抽出することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記案内ポイント抽出手段は、
前記特定された流出リンクの進行頻度が前記第１の所定値以上であって、且つ前記特定された流出リンクが経路と一致する場合には、前記交差点における前記流出リンクと異なる流出リンクの進行頻度が、前記第１の所定値よりも小さい第２の所定値以上である場合に、前記交差点を前記案内ポイントとして抽出することを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
現在位置を取得する現在位置取得手段と、
前記取得された現在位置の移動履歴を記憶する移動履歴記憶手段と、
前記交差点における前記移動履歴と一致する流出リンクを特定する流出リンクを特定する流出リンク特定手段と、を備え、
前記行動パタンデータ記憶手段は、前記流出リンク特定手段によって特定された流出リンクを前記行動パタンデータとして記憶することを特徴とする請求項１に記載のナビゲーション装置。
【請求項５】
現在位置を取得する現在位置取得手段と、
移動履歴を収集する収集サーバに、前記取得された現在位置の移動履歴を送信する移動履歴送信手段と、
前記収集サーバが収集した移動履歴から推定した行動パタン推定データを受信する行動パタン受信手段と、を備え、
前記行動パタンデータ記憶手段は、前記行動パタン受信手段で受信した前記行動パタン推定データを前記行動パタンデータとして記憶することを特徴とする請求項１に記載のナビゲーション装置。
【請求項６】
前記行動パタン記憶手段は、
道路を二つの交差点の間を接続するリンクとして記憶するリンク記憶手段と、
複数の前記リンクから構成された交差点における進路を選択する進路選択手段と、を備えることを特徴とする請求項１に記載のナビゲーション装置。
【請求項７】
地図データを記憶する地図データ記憶手段と、
複数の経路を探索する複数経路探索手段と、
前記複数の探索された経路から好適な経路を選択する経路選択する経路選択手段と、
前記経路をユーザに対して出力する出力手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、
前記複数経路探索手段によって探索された複数の異なる前記経路の分岐点を抽出する分岐点抽出手段と、
前記複数経路探索手段によって探索された前記複数の経路の前記分岐点における前記進行頻度を、前記行動パタンデータから算出する進行頻度算出手段と、を備え、
前記分岐点抽出手段によって抽出された分岐点において、前記経路選択手段によって選択された好適な経路上の流出リンクの進行頻度より、前記好適な経路と異なる経路上の分岐点からの流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路を前記出力手段に出力することを特徴とするナビゲーション装置。
【請求項８】
地図データを記憶する地図データ記憶手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、を備えるナビゲーション装置における経路案内方法において、
前記地図データを使用して経路を探索する探索ステップと、
前記行動パタンデータ記憶手段から読み出された行動パタンデータを使用して、前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出ステップと、
前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定ステップと、
前記流出リンク推定ステップによって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索ステップと、
前記代替経路をユーザに対して出力する代替経路出力ステップと、を有することを特徴とする経路案内方法。
【請求項１】
地図データを記憶する地図データ記憶手段と、
前記地図データを使用して経路を探索する探索手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、
前記行動パタンデータ記憶手段から読み出された前記行動パタンデータを使用して前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出手段と、
前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定手段と、
前記流出リンク推定手段によって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索手段と、
前記代替経路をユーザに対して出力する代替経路出力手段と、を備えることを特徴とするナビゲーション装置。
【請求項２】
前記案内ポイント抽出手段は、
前記経路上に存在する交差点における前記行動パタンデータを使用して、前記交差点で前記進行頻度が最も多い流出リンクを特定し、
前記特定された流出リンクの進行頻度が第１の所定値以上であって、且つ前記特定された流出リンクが前記経路と異なる場合に、前記交差点を前記案内ポイントとして抽出することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記案内ポイント抽出手段は、
前記特定された流出リンクの進行頻度が前記第１の所定値以上であって、且つ前記特定された流出リンクが経路と一致する場合には、前記交差点における前記流出リンクと異なる流出リンクの進行頻度が、前記第１の所定値よりも小さい第２の所定値以上である場合に、前記交差点を前記案内ポイントとして抽出することを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
現在位置を取得する現在位置取得手段と、
前記取得された現在位置の移動履歴を記憶する移動履歴記憶手段と、
前記交差点における前記移動履歴と一致する流出リンクを特定する流出リンクを特定する流出リンク特定手段と、を備え、
前記行動パタンデータ記憶手段は、前記流出リンク特定手段によって特定された流出リンクを前記行動パタンデータとして記憶することを特徴とする請求項１に記載のナビゲーション装置。
【請求項５】
現在位置を取得する現在位置取得手段と、
移動履歴を収集する収集サーバに、前記取得された現在位置の移動履歴を送信する移動履歴送信手段と、
前記収集サーバが収集した移動履歴から推定した行動パタン推定データを受信する行動パタン受信手段と、を備え、
前記行動パタンデータ記憶手段は、前記行動パタン受信手段で受信した前記行動パタン推定データを前記行動パタンデータとして記憶することを特徴とする請求項１に記載のナビゲーション装置。
【請求項６】
前記行動パタン記憶手段は、
道路を二つの交差点の間を接続するリンクとして記憶するリンク記憶手段と、
複数の前記リンクから構成された交差点における進路を選択する進路選択手段と、を備えることを特徴とする請求項１に記載のナビゲーション装置。
【請求項７】
地図データを記憶する地図データ記憶手段と、
複数の経路を探索する複数経路探索手段と、
前記複数の探索された経路から好適な経路を選択する経路選択する経路選択手段と、
前記経路をユーザに対して出力する出力手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、
前記複数経路探索手段によって探索された複数の異なる前記経路の分岐点を抽出する分岐点抽出手段と、
前記複数経路探索手段によって探索された前記複数の経路の前記分岐点における前記進行頻度を、前記行動パタンデータから算出する進行頻度算出手段と、を備え、
前記分岐点抽出手段によって抽出された分岐点において、前記経路選択手段によって選択された好適な経路上の流出リンクの進行頻度より、前記好適な経路と異なる経路上の分岐点からの流出リンクの進行頻度が多い場合には、当該好適な経路と異なる経路を前記出力手段に出力することを特徴とするナビゲーション装置。
【請求項８】
地図データを記憶する地図データ記憶手段と、
交差点における流出リンクと進行頻度とを関連付けした行動パタンデータを記憶する行動パタンデータ記憶手段と、を備えるナビゲーション装置における経路案内方法において、
前記地図データを使用して経路を探索する探索ステップと、
前記行動パタンデータ記憶手段から読み出された行動パタンデータを使用して、前記経路上の交差点を案内ポイントとして抽出する案内ポイント抽出ステップと、
前記案内ポイントにおいて進行する流出リンクを推定する流出リンク推定ステップと、
前記流出リンク推定ステップによって推定された流出リンクを進行した場合の代替経路を探索する代替経路探索ステップと、
前記代替経路をユーザに対して出力する代替経路出力ステップと、を有することを特徴とする経路案内方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１０−１０７４４２（Ｐ２０１０−１０７４４２Ａ）
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願番号】特願２００８−２８１６３９（Ｐ２００８−２８１６３９）
【出願日】平成２０年１０月３１日（２００８．１０．３１）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願日】平成２０年１０月３１日（２００８．１０．３１）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
[ Back to top ]