(57)【要約】  【課題】  探索条件に応じて評価関数を変えて探索を行うナビゲーション装置において、適切な評価関数を選択できるように学習を行う。  【解決手段】  ナビゲーション装置１は、経路のコストを計算するための重み係数テーブルを複数記憶した重み係数テーブル記憶部１２を有する。経路探索を行う際には、テーブル選択部２６が、テーブル選択モデルを用いて、経路探索の条件に応じて一の重み係数テーブルを選択し、選択した重み係数テーブルを用いて経路探索を行う。ナビゲーション装置１は、出発地から目的地まで車両が走行したときに、車両の走行経路を構成するリンクを過去に通過した回数が所定の基準値より少ない場合にテーブル選択モデルの学習を行い、走行経路を構成するリンクを過去に通過した回数が所定の基準値以上の場合には、テーブル選択モデルの学習を行わないと判定する学習可否判定部３２を備える。【選択図】  図１
2008292237.tif 000002
【特許請求の範囲】
【請求項１】
経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するナビゲーション装置であって、
前記コストを計算するための複数の評価関数を記憶した評価関数記憶部と、
経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記複数の評価関数の中から経路探索の条件に対応する一の評価関数を選択する評価関数選択部と、
前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索する推奨経路探索部と、
出発地から目的地までの車両の走行経路を取得する走行経路取得部と、
前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正する学習部と、
を備えるナビゲーション装置。
【請求項２】
前記学習部は、それぞれの評価関数に対応する複数の経路を計算し、前記複数の経路と前記走行経路との差分に基いて、前記各経路を計算した評価関数が選択される確率を更新する請求項１に記載のナビゲーション装置。
【請求項３】
所定回数以上通過したルートを学習ルートとして記憶しておく学習ルート記憶部を備え、
前記推奨経路探索部は、コストに基づいて求めた経路を、前記学習ルート記憶部に記憶された学習ルートによって補正して前記推奨経路を探索する請求項１または２に記載のナビゲーション装置。
【請求項４】
前記学習ルート記憶部に記憶した学習ルートを所定期間通らなかったときに、前記学習ルート記憶部から当該学習ルートを消去する請求項３に記載のナビゲーション装置。
【請求項５】
学習ルートを消去するまでの前記所定期間を当該学習ルートの自宅からの距離に応じて設定している請求項４に記載のナビゲーション装置。
【請求項６】
前記学習ルート記憶部は、分岐を有する学習ルートを記憶する場合には、当該分岐の通過実績に関する情報を記憶する請求項３〜５のいずれかに記載のナビゲーション装置。
【請求項７】
前記学習ルート記憶部は、前記学習ルートに関連付けて前記学習ルートを通ったときの経路探索の条件を示す情報を記憶する請求項３〜６のいずれかに記載のナビゲーション装置。
【請求項８】
前記学習ルート記憶部に記憶した学習ルートを地図上に表示する学習ルート表示部を備える請求項３〜７のいずれかに記載のナビゲーション装置。
【請求項９】
前記道路属性に、過去にリンクを通過した回数を示す情報が含まれており、
前記各評価関数は、前記リンクを通過した回数が多いほどコストが小さくなるように設定されている請求項１〜８のいずれかに記載のナビゲーション装置。
【請求項１０】
前記リンクを過去に通過した回数の情報は、直近の所定期間における当該リンクの通過回数を示す情報である請求項９に記載のナビゲーション装置。
【請求項１１】
前記道路属性に、過去にリンクを通過するのに要した所要時間を示す情報が含まれており、
前記各評価関数は、前記所要時間が短いほどコストが小さくなるように設定されている請求項１〜１０のいずれかに記載のナビゲーション装置。
【請求項１２】
経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するナビゲーション方法であって、
前記コストを計算するための複数の評価関数を記憶した評価関数記憶部を準備するステップと、
経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記複数の評価関数の中から経路探索条件に対応する一の評価関数を選択するステップと、
前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索するステップと、
出発地から目的地までにおける車両の走行経路を取得するステップと、
前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正するステップと、
を備えるナビゲーション方法。
【請求項１３】
経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するためのプログラムであって、コンピュータに、
経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記コストを計算するための複数の評価関数を記憶した評価関数記憶部から経路探索の条件に対応する一の評価関数を抽出するステップと、
前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索するステップと、
出発地から目的地までにおける車両の走行経路を取得するステップと、
前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正するステップと、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置の経路探索に関する。
【背景技術】
【０００２】
従来から、カーナビゲーション装置における経路探索技術として、ダイクストラ法等の探索アルゴリズムが広く知られている。ダイクストラ法は、出発地と目的地を基点として、地図上のどのリンクを通ると最小コストになるかを計算し、経路を求める方法である。
【０００３】
本発明の発明者らは、経路のコストを計算するための評価関数が、状況に応じて異なることに着目し、状況に応じて適切な評価関数を用いてコストを計算し、経路を求める方法を出願した（特許文献１）。特許文献１では、あらかじめ複数のコストテーブル（評価関数）を準備しておく。コストテーブルは、経路のコストを計算に用いられるテーブルである。そして、例えば、ドライバの年齢層や性別、運転の日の曜日や運転の時間帯等の状況を示す情報を経路探索の条件とし、複数のコストテーブルの中から経路探索の条件に合ったコストテーブル（評価関数）を選択する。具体的には、ベイジアンネットのモデルを用いた確率推論の計算を行って、最も確率の高いコストテーブルを選択する。この構成により、経路探索の条件に応じて適切な経路を推奨することができる。
【０００４】
また、特許文献１の発明では、コストテーブルを選択するためのベイジアンネットのモデルの学習を行う。実際に走行した経路に最も近い推奨経路を算出するコストテーブルが選択されるように、コストテーブル選択用のモデルの学習を行う。
【特許文献１】特開２００７−１０５７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
例えば、毎日の通勤等においては、決まった道を通るというドライバも多い。このようにいつも通る道がある場合に、特許文献１に記載された発明において選択用のモデルの学習を行うと、同じ教師信号によって何度も学習が行われることになり、複数のコストテーブルのうちの一つが極度に選択されやすくなってしまう可能性がある。
【０００６】
本発明は、上記背景に鑑み、探索条件に応じて評価関数を変えて経路探索を行うナビゲーション装置であって、適切な評価関数を選択できるように学習を行うナビゲーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明のナビゲーション装置は、経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するナビゲーション装置であって、前記コストを計算するための複数の評価関数を記憶した評価関数記憶部と、経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記複数の評価関数の中から経路探索の条件に対応する一の評価関数を選択する評価関数選択部と、前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索する推奨経路探索部と、出発地から目的地までの車両の走行経路を取得する走行経路取得部と、前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正する学習部とを備える。
【０００８】
このように学習部が経路探索の条件と用いるべき評価関数との所定の関係を修正するか否かを判定するので、走行経路が過去に何度も通過したリンクを多く含む場合には、所定の関係を修正しないと判定することができる。これにより、ドライバがよく通る走行経路を教師信号として、評価関数を求めるための所定の関係に対する過度の学習が行われることがない。過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、評価関数を求めるための所定の関係を適切に学習することができる。従って、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できる。
【０００９】
本発明のナビゲーション装置において、前記学習部は、それぞれの評価関数に対応する複数の経路を計算し、前記複数の経路と前記走行経路との差分に基いて、前記各経路を計算した評価関数が選択される確率を更新してもよい。
【００１０】
このように複数の経路と走行経路との差分を用いて評価関数が選択される確率を更新することにより、一の走行経路を用いて複数の評価関数の選択確率を更新することができ、学習の速度を高めることができる。
【００１１】
本発明のナビゲーション装置は、所定回数以上通過したルートを学習ルートとして記憶しておく学習ルート記憶部を備え、前記推奨経路探索部は、コストに基づいて求めた経路を、前記学習ルート記憶部に記憶された学習ルートによって補正して前記推奨経路を探索してもよい。
【００１２】
この構成により、出発地から目的地までの経路の周辺に学習ルートがある場合には、学習ルートを含む推奨経路を探索することができる。
【００１３】
本発明のナビゲーション装置は、前記学習ルート記憶部に記憶した学習ルートを所定期間通らなかったときに、前記学習ルート記憶部から当該学習ルートを消去してもよい。
【００１４】
この構成により、所定期間通らなかった古い学習ルートが推奨経路の探索に影響を与えないようにすることができる。
【００１５】
本発明のナビゲーション装置は、学習ルートを消去するまでの前記所定期間を当該学習ルートの自宅からの距離に応じて設定してもよい。
【００１６】
自宅から遠くにある場所は、自宅付近の場所に比べて行く回数が少ないので、自宅からの距離に応じて学習ルートを消去するまでの所定期間を変えることにより、自宅から遠い場所と近い場所で、学習ルートを消去するタイミングを整合させることができる。
【００１７】
本発明のナビゲーション装置において、前記学習ルート記憶部は、分岐を有する学習ルートを記憶する場合には、当該分岐の通過実績に関する情報を記憶してもよい。
【００１８】
この構成により、経路探索に分岐の通過実績を用いることができる。例えば、分岐した後に再び合流する経路において、どちらの経路もリンクコストが同じである場合に、分岐の通過実績を用いていずれの経路を推奨経路とするかを決定できる。なお、分岐の通過実績を、例えば、確率値として記憶してもよい。
【００１９】
本発明のナビゲーション装置において、前記学習ルート記憶部は、前記学習ルートに関連付けて前記学習ルートを通ったときの経路探索の条件を示す情報を記憶してもよい。
【００２０】
この構成により、学習ルート記憶部に記憶された学習ルートで推奨経路を補正する場合に、経路探索の条件に基づいて補正に用いるべき適切な学習ルートを選択することができる。
【００２１】
本発明のナビゲーション装置は、前記学習ルート記憶部に記憶した学習ルートを地図上に表示する学習ルート表示部を備えてもよい。
【００２２】
この構成により、ドライバは、学習ルートとして記憶されている道を容易に把握することができる。
【００２３】
本発明のナビゲーション装置は、前記道路属性に、過去にリンクを通過した回数を示す情報が含まれており、前記各評価関数は、前記リンクを通過した回数が多いほどコストが小さくなるように設定されていてもよい。
【００２４】
このようにリンクを過去に通過した回数が多いほどコストを小さくすることにより、コストに基づく経路探索により、よく通る道を含む推奨経路が探索される。
【００２５】
前記リンクを過去に通過した回数の情報は、直近の所定期間における当該リンクの通過回数を示す情報としてもよい。
【００２６】
この構成により、以前によく通った道ではなく、直近の所定期間によく通る道を含む推奨経路が探索される。
【００２７】
本発明のナビゲーション装置は、前記道路属性に、過去にリンクを通過するのに要した所要時間を示す情報が含まれており、前記各評価関数は、前記所要時間が短いほどコストが小さくなるように設定されていてもよい。
【００２８】
このようにリンクの所要時間が短いほどコストを小さくすることにより、コストに基づく経路探索により、所要時間の短い推奨経路が探索される。
【００２９】
本発明のナビゲーション方法は、経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するナビゲーション方法であって、前記コストを計算するための複数の評価関数を記憶した評価関数記憶部を準備するステップと、経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記複数の評価関数の中から経路探索条件に対応する一の評価関数を選択するステップと、前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索するステップと、出発地から目的地までにおける車両の走行経路を取得するステップと、前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正するステップとを備える。
【００３０】
これにより、本発明のナビゲーション装置と同様に、過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、評価関数を求めるための所定の関係を適切に学習することができる。従って、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できる。なお、本発明のナビゲーション装置の各種の構成を、本発明のナビゲーション方法に適用することも可能である。
【００３１】
本発明のプログラムは、経路を構成するリンクの複数の道路属性をパラメータとする評価関数を用いて前記経路のコストを計算し、前記コストに基づいて出発地から目的地までの最適経路を探索するためのプログラムであって、コンピュータに、経路探索の条件と用いるべき評価関数との所定の関係に基いて、前記コストを計算するための複数の評価関数を記憶した評価関数記憶部から経路探索の条件に対応する一の評価関数を抽出するステップと、前記評価関数を用いて経路のコストを求め、前記経路のコストに基いて出発地から目的地に至る推奨経路を探索するステップと、出発地から目的地までにおける車両の走行経路を取得するステップと、前記走行経路を構成するリンクを過去に通過した回数に基いて前記所定の関係を修正するか否かを判定し、前記所定の関係を修正すると判定された場合に、前記経路探索の条件および前記走行経路の情報に基づいて前記所定の関係を修正するステップとを実行させる。
【００３２】
これにより、本発明のナビゲーション装置と同様に、過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、評価関数を求めるための所定の関係を適切に学習することができる。従って、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できる。なお、本発明のナビゲーション装置の各種の構成を、本発明のプログラムに適用することも可能である。
【発明の効果】
【００３３】
本発明によれば、過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、評価関数を求めるための所定の関係を適切に学習することができ、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できるという効果を有する。
【発明を実施するための最良の形態】
【００３４】
以下、本発明の実施の形態のナビゲーション装置について、図面を用いて説明する。
（第１の実施の形態）
図１は、第１の実施の形態のナビゲーション装置１の構成を示す図である。ナビゲーション装置１は、道路地図の情報を記憶した地図情報記憶部１０と、車両の現在位置を求める車両位置検出部１８と、ドライバからの操作を受け付けるスイッチ２０と、地図等を表示するディスプレイ２２と、経路探索等を行う制御部２４とを備えている。
【００３５】
地図情報記憶部１０は、道路の情報に加えて、観光施設やレストランなどの各種の施設情報を記憶している。また、地図情報記憶部１０は、道路の属性に関する情報を記憶している。
【００３６】
図２（ａ）および図２（ｂ）は、道路の属性情報の例を示す図である。図２（ａ）に示すように、道路をノードＡ〜ノードＥ、リンクＬａｂ、Ｌｂｄ等で表現する。図２（ｂ）に示すように、道路属性は、各リンクの道幅、距離、通過回数などの情報である。本実施の形態では、通過回数には、直近の３ヶ月間に当該リンクを通過した回数を記憶する。なお、本実施の形態では、通過回数の情報を地図情報に含めて記憶することとしているが、例えば、地図情報記憶部１０として、ＣＤ−ＲＯＭ等の読取専用の記録媒体を利用する場合には、通過回数の情報を地図情報記憶部１０とは別にナビゲーション装置１のメモリに記憶してもよい。
【００３７】
車両位置検出部１８は、車両の現在位置を検出する機能を有する。車両位置検出部１８としては、例えば、地磁気センサ、ジャイロスコープ、距離センサ、ＧＰＳ受信機、ステアリングの回転センサ、各転動輪の車両センサ等を用いることができる。車両位置検出部１８は、これらのいくつかのセンサを用いて構成してもよい。これらのセンサは、性質の異なる誤差を持っているので、複数のセンサで補完することにより、車両の現在位置を精度良く検出できる。
【００３８】
ディスプレイ２２は、現在位置の周辺地図や目的地までの経路を表示する機能を有する。また、ディスプレイ２２は、タッチパネルを備えており、目的地設定等のために必要な情報の入力を受け付ける。
【００３９】
次に、ナビゲーション装置１によって経路探索を行うための構成について説明する。ナビゲーション装置１は、出発地から目的地までのコストが最小となる経路（以下、「コスト最小経路」という）を探索する。そして、コスト最小経路に対して、ドライバがよく通るルートの情報を加味して推奨経路を求める。
【００４０】
ナビゲーション装置１は、評価関数を用いて経路のコストを計算する。本実施の形態では、ナビゲーション装置１は、複数の評価関数を記憶しており、探索条件に応じて適切な評価関数を用いてコスト最小経路を探索する。
【００４１】
本実施の形態のナビゲーション装置１が用いる評価関数は、リンクコスト＝Σ（重み係数×道路属性のパラメータ）で表される。ナビゲーション装置１は、経路を構成するリンクの総リンクコストを経路のコストとして求める。
【００４２】
道路属性のパラメータとしては、道路情報記憶部に記憶された道路属性の情報を利用する。ただし、道路属性の情報をリンクコストの計算に用いる場合には、道路属性を、リンクコスト計算用のパラメータに置き換える。例えば、道路属性の「道幅」は、広い方が車両が通りやすく、ドライバに好まれるので、コストを小さくする。例えば、道幅５ｍ未満の場合はパラメータを「３」に、道幅５ｍ以上１０ｍ未満の場合はパラメータを「２」に、道幅１０ｍ以上の場合はパラメータを「１」に置き換える。
【００４３】
ナビゲーション装置１は、評価関数の重み係数を記憶した重み係数記憶部１２を備えている。重み係数記憶部１２には、複数の評価関数の重み係数を記憶している。
【００４４】
図３は、重み係数記憶部１２に記憶されたデータの例を示す図である。図３に示すように、重み係数記憶部１２には、複数の重み係数テーブルＴＡ〜ＴＣが記憶されている。重み係数テーブルＴＡ〜ＴＣは、評価関数において道路属性のパラメータに乗じる重み係数を記憶している。一の重み係数テーブルは、一の評価関数に対応する。図３において、例えば、重み係数テーブルＴＡでは、距離の重み係数が０．９であり、道幅の重み係数が０．３であるので、距離の方が道幅よりリンクコストに与える影響が大きい。重み係数テーブルＴＡは、道幅よりも距離を重視して経路を探索する評価関数である。
【００４５】
ナビゲーション装置１は、経路探索を行うために用いる評価関数を探索条件に応じて決定するための構成として、テーブル選択モデルを記憶したテーブル選択モデル記憶部１４を有する。テーブル選択モデルは、ベイジアンネットのモデルである。
【００４６】
図４は、テーブル選択モデルの例を示す図である。テーブル選択モデルは、年齢層のノードＮ１、性別のノードＮ２、曜日のノードＮ３、時間帯のノードＮ４と、重み係数テーブルＴＡ〜ＴＣのノードＮ５〜Ｎ７とが、確率的な依存関係を表すリンクで接続されている。図４において、リンクの矢印の向きは、依存する方向を示している。例えば、重み係数テーブルＴＡのノードＮ５の確率値は、ノードＮ１〜Ｎ４の値に依存している。年齢層のノードＮ１、性別のノードＮ２、曜日のノードＮ３、時間帯のノードＮ４は、観測ノードであり、これらのノードＮ１〜Ｎ４にドライバの年齢、性別の情報や、経路探索時の曜日や時間帯を設定する。各リンクは、図示しない条件付き確率テーブル（ＣＰＴ）の情報を有しており、ナビゲーション装置１は、条件付き確率テーブルに従って、重み係数テーブルＴＡ〜ＴＣの確率値を求める。
【００４７】
学習ルート記憶部１６は、車両がよく通るルートを記憶する。学習ルート記憶部１６は、よく通るルートを構成するリンクの情報を記憶してもよいし、当該ルートを構成するノードの情報を記憶してもよい。また、学習ルート記憶部１６は、よく通るルートにおいて、右左折のポイントとなるノードだけを記憶し、道なりの部分のノードを記憶しない構成とすることもできる。これにより、学習ルート記憶部１６に記憶すべき情報量を削減できる。
【００４８】
次に、ナビゲーション装置１の制御部２４について説明する。制御部２４は、テーブル選択部２６と、経路探索部２８と、走行経路取得部３０と、学習可否判定部３２と、モデル学習部３４と、ルート学習部３６とを有している。テーブル選択部２６は、重み係数記憶部１２に記憶された複数の重み係数テーブルの中から、探索条件に応じて重み係数テーブルを選択する処理を実行する。図３に示すテーブル選択モデルを用いて、重み係数テーブルＴＡ〜ＴＣの確率値を計算し、確率値の最も高い重み係数テーブルを選択する。
【００４９】
経路探索部２８は、選択した重み係数テーブルを用いて、出発地から目的地までの経路のコストを計算し、コスト最小経路を探索する処理を実行する。経路探索部２８は、ダイクストラ法などの探索手法を用いて、コスト最小経路を探索する。また、経路探索部２８は、学習ルート記憶部１６に記憶された学習ルートを用いて、コスト最小の経路を補正し、推奨経路を計算する。
【００５０】
図５（ａ）および図５（ｂ）は、学習ルートを用いてコスト最小の経路を補正する方法の一例を示す図である。図５（ａ）は、出発地から目的地までのコスト最小経路Ｒ１と学習ルート記憶部１６に記憶された学習ルートＲ２を示す。図５（ａ）に示すように、コスト最小経路Ｒ１の所定の２点をつなぐ学習ルートＲ２がある場合、学習ルートＲ２によってコスト最小経路Ｒ１を補正し、図５（ｂ）に示すように推奨経路Ｒ３を求める。なお、ここでは、学習ルートＲ２を用いて推奨経路Ｒ３を求める方法の一例を示したが、学習ルートを利用して推奨経路を求める方法は図５（ａ）および図５（ｂ）に示す方法に限られない。例えば、コスト最小経路の付近に学習ルートがある場合に、コスト最小経路と学習ルートのノードが重なっていなくても、コスト最小経路と学習ルートとをつなぐルートを引いて推奨経路としてもよい。
【００５１】
走行経路取得部３０は、出発地から目的地まで、実際に車両が走行した経路を取得する処理を実行する。走行経路取得部３０は、車両位置検出部１８にて検出した車両位置を随時取得することにより、走行経路を取得する。
【００５２】
学習可否判定部３２は、テーブル選択モデルの学習を行うか否かの判定を行う。学習可否判定部３２は、実際に走行した経路と推奨経路とが一致しているか否かを判定し、一致する場合には、学習を行わないと判定する。走行経路と推奨経路とが一致しない場合には、走行経路がよく通る道か否かを判定する。走行経路がよく通る道である場合には、学習を行わないと判定する。走行経路がよく通る道でない場合には、走行経路に基づいてテーブル選択モデルの学習を行うと判定する。
【００５３】
ここで、走行経路がよく通る道であるか否かの判定の仕方について説明する。走行経路がよく通る道であるか否かの判定には、道路属性の通過回数のパラメータを用いる。学習可否判定部３２は、例えば、走行経路を構成する全リンクの通過回数の平均値を求め、平均値が所定の閾値（例えば、５回）以上である場合に、走行経路はよく通る経路であると判定してもよい。また、所定の閾値（例えば、５回）を超える通過回数のリンクが、走行経路を構成する全リンクの何パーセントあるかを求め、このパーセンテージが所定の閾値（例えば７０パーセント）以上である場合に、走行経路はよく通る経路であると判定してもよい。ここでは、よく通る道であるか否かを判定する方法の一例を挙げたが、上記方法以外にも、走行経路がよく通る道であるか否かを判定する方法として、様々な方法が考えられる。
【００５４】
モデル学習部３４は、テーブル選択モデルの学習を行う処理を実行する。前述したように、図４に示すテーブル選択モデルにおいて、各ノードＮ１〜Ｎ７は、条件付き確率の依存関係を示すリンクで接続され、各リンクは、条件付き確率テーブルの情報を有している。モデル学習部３４は、走行経路と走行経路の情報を取得したときの探索条件（ドライバの年齢層、性別、走行時の曜日、時間帯）に応じて、条件付き確率テーブルの情報を更新する。
【００５５】
モデル学習部３４は、重み係数記憶部１２に記憶された重み係数テーブルを用いて、出発地から目的地までの経路を計算する。以下、説明の便宜上、各重み係数テーブルを用いて計算した経路を「候補経路」という。次に、モデル学習部３４は、走行経路とそれぞれの候補経路との差分を求め、差分に基づいて候補経路に順位を付ける。差分の計算には、様々な手法を用いることができるが、一例を挙げれば、推奨経路を構成する全リンクのうち、走行経路に一致しないリンクの割合を差分として計算してもよい。
【００５６】
モデル学習部３４は、候補経路に付与した順位の情報と、走行経路を取得したときの探索条件とを用いて、テーブル選択モデルの学習を行う。例えば、高順位の候補経路を算出した重み係数テーブルの確率値を高め、低順位の候補経路を算出した重み係数テーブルの確率値を低くするように条件付き確率テーブルを更新する。この方法の一例を以下に示す。
【００５７】
条件付き確率テーブルは、各探索条件においてそれぞれの重み係数テーブルが選ばれる確率値を記憶している。例えば、性別：男、年齢層：４０代、曜日：月曜、時間帯：８時〜１０時という状況（探索条件）において、重み係数テーブルＴＡが選ばれる確率値（７／１０）、重み係数テーブルＴＢが選ばれる確率値（２／１０）、重み係数テーブルＴＣが選ばれる確率値（１／１０）というような条件付き確率の情報を探索条件の全ての組合せについて記憶している。この条件付き確率値は、１０回の試行において７回重み係数テーブルＴＡが選ばれたという過去の実績に基づいていると考えることができる。この状況で、実際の走行経路と各候補経路との差分を求めた結果、差分に基づく順位が、１位：重み係数テーブルＴＡ、２位：重み係数テーブルＴＢ、３位：重み係数テーブルＴＣであったとする。この場合、１位の重み係数テーブルＴＡが選ばれたとして確率値を更新すると、重み係数テーブルＴＡは、１１回中８回選ばれたことになるので、重み係数テーブルＴＡの確率値は（８／１１）となる。同様に、重み係数テーブルＴＢの確率値は（２／１１）、重み係数テーブルＴＣの確率値は（１／１１）となる。
【００５８】
また、条件付き確率テーブルを順位に応じて更新することとしてもよい。例えば、順位に応じて、重み係数テーブルＴＡが３回中２回選ばれたとし、重み係数テーブルＴＢが３回中１回選ばれたとして確率値を更新すると、重み係数テーブルＴＡの確率値は（９／１３）、重み係数テーブルＴＢの確率値は（３／１３）、重み係数テーブルＴＣの確率値は（１／１３）となる。走行経路との差分を用いてテーブル選択モデルの条件付き確率テーブルを更新することにより、走行経路と近い候補経路を算出した重み係数テーブルが選択される確率を高めることができる。
【００５９】
ルート学習部３６は、走行経路と推奨経路との差分ルートを求め、差分ルートに基づいてルート学習を行う。例えば、走行経路と推奨経路との差分ルートを学習ルート記憶部１６に記憶する。学習ルート記憶部１６に、同じ差分ルートが所定回数書き込まれた場合に、その差分ルートを学習ルートとして記憶する。学習ルート記憶部１６に記憶された学習ルートは、ディスプレイ２２に表示した地図上に示してもよい。これにより、ドライバは、学習ルートとして記憶された道を容易に把握できる。
【００６０】
次に、第１の実施の形態のナビゲーション装置１の動作について説明する。
図６は、ナビゲーション装置１による経路探索の動作を示す図である。ナビゲーション装置１は、経路探索に用いる重み係数テーブルを選択する（Ｓ１０）。ナビゲーション装置１は、ドライバの年齢、性別および運転時の曜日、時間帯をテーブル選択モデルの観測ノードに設定し、確率推論によって各重み係数テーブルの確率値を求め、確率値に基づいて重み係数テーブルを選択する。
【００６１】
次に、ナビゲーション装置１は、求めた重み係数テーブルを用いて、ドライバによって入力された出発地から目的地までのコスト最小経路を探索する（Ｓ１２）。続いて、ナビゲーション装置１は、学習ルート記憶部１６から学習ルートの情報を読み出し（Ｓ１４）、学習ルートの情報を用いてコスト最小経路の補正を行う（Ｓ１６）。ナビゲーション装置１は、探索された経路を推奨経路としてディスプレイ２２に表示し、経路案内を行う。
【００６２】
図７は、ナビゲーション装置１によるテーブル選択モデルの学習の動作を示す図である。まず、車両が走行を開始し（Ｓ２０）、車両の走行中に、車両位置検出部１８にて検出した車両の位置情報を用いて、車両の走行経路を取得する（Ｓ２２）。車両が走行を終了したことを検知する（Ｓ２４）。ここで、車両の走行終了とは、例えば、目的地に到着して停止したことを意味する。本実施の形態では、ナビゲーション装置１は、車両のエンジンが切れたときに、車両の走行の終了を検知する。
【００６３】
次に、ナビゲーション装置１は、出発地から目的地までの推奨経路を探索する（Ｓ２６）。ナビゲーション装置１は、ドライバから経路探索が指示されない場合であっても、学習を行うか否かの判定を行うために、推奨経路の探索を行う。経路探索の処理（Ｓ２６）は、図６を用いて説明した経路探索処理と同じである。ナビゲーション装置１は、探索された推奨経路と走行経路とを比較する（Ｓ２８）。推奨経路と探索経路とが一致する場合（Ｓ２８でＹＥＳ）、ナビゲーション装置１は、学習を行わない。
【００６４】
推奨経路と探索経路とが一致しない場合（Ｓ２８でＮＯ）、走行経路が、そのドライバがよく通る道であるか否かを判定する（Ｓ３０）。学習可否判定部３２は、経路を構成するリンクの通過回数の属性に基づいて走行経路がよく通る道であるか否かを判定する。走行経路がよく通る道であると判定された場合（Ｓ３０でＹＥＳ）、ナビゲーション装置１は学習を行わない。走行経路がよく通る道ではないと判定された場合（Ｓ３０でＮＯ）、ナビゲーション装置１は、テーブル選択モデルの学習を行う（Ｓ３２）。
【００６５】
図８は、テーブル選択モデルの学習の動作を示す図である。モデル学習部３４は、重み係数記憶部１２から全ての重み係数テーブルを読み出す（Ｓ４０）。ここでは、重み係数テーブルＴＡ〜ＴＣを読み出す。次に、モデル学習部３４は、いずれかの重み係数テーブルを用いて、出発地から目的地までのコスト最小経路を検索し（Ｓ４２）、コスト最小経路と走行経路との差分を計算する（Ｓ４４）。モデル学習部３４は、重み係数記憶部１２から読み出した全ての重み係数テーブルについて、上記したコスト最小経路の検索および差分の計算を行ったか否かを判定する（Ｓ４６）。この判定の結果、全重み係数テーブルについて計算済みでない場合には（Ｓ４６でＮＯ）、未計算の重み係数テーブルを用いてコスト最小経路の計算処理に移行する（Ｓ４２）。
【００６６】
全重み係数テーブルについて計算済みの場合（Ｓ４６でＹＥＳ）、モデル学習部３４は、求めた差分に基づいて重み係数テーブルの順位付けを行う（Ｓ４８）。モデル学習部３４は、差分の小さい経路を算出した重み係数テーブルから順に、高い順位を与える。モデル学習部３４は、与えられた順位を用いて、テーブル選択モデルの学習を行う（Ｓ５０）。
以上、本実施の形態のナビゲーション装置１の構成および動作について説明した。
【００６７】
本実施の形態のナビゲーション装置１は、出発地から目的地までの実際の走行経路が推奨経路と異なる場合であっても、走行経路がよく通る道である場合には、テーブル選択モデルの学習を行わない。これにより、よく通る道を教師信号として過度に学習が行われることがない。過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、テーブル選択モデルを適切に学習するので、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できる。
【００６８】
また、本実施の形態のナビゲーション装置１は、探索条件に応じて適切な重み係数テーブルを用いてコスト最小経路を探索した後、よく通る道として学習した学習ルートを用いて、コスト最小経路を補正するので、ドライバの走り慣れた道を探索し、推奨経路とすることができる。
【００６９】
（第２の実施の形態）
次に、本発明の第２の実施の形態のナビゲーション装置について説明する。第２の実施の形態のナビゲーション装置は、経路探索を行う際に、コスト最小経路を学習ルートで補正するのではなく、通過回数の属性を経路のコスト計算に含めることにより、よく通る道が推奨経路として探索されるようにしている。
【００７０】
図９は、第２の実施の形態のナビゲーション装置２の構成を示す図である。第２の実施の形態のナビゲーション装置２の基本的な構成は、第１の実施の形態のナビゲーション装置１と同じであるが、第１の実施の形態で説明した学習ルート記憶部１６およびルート学習部３６を備えていない。また、第２の実施の形態のナビゲーション装置２は、重み係数記憶部１２に記憶された重み係数テーブルの内容が、第１の実施の形態のナビゲーション装置１と異なる。
【００７１】
図１０は、重み係数記憶部１２に記憶された重み係数テーブルの例を示す図である。第２の実施の形態においては、重み係数テーブルには、通過回数の属性に対する重み係数が記憶されている。すなわち、第２の実施の形態では、リンクコストを求めるための評価関数は、リンクの通過回数をパラメータの一つとしている。通過回数のパラメータは、通過回数が多いほどコストが低くなるように置き換える。例えば、リンクの通過回数が１０回以上の場合には、パラメータを「１」とし、リンクの通過回数が４回以上１０回未満の場合には、パラメータを「２」とし、リンクの通過回数が３回未満の場合には、パラメータを「３」とする。これにより、リンクの通過回数が多くなるほどそのリンクのコストが低くなるので、通過回数の多いリンクを含む経路がコスト最小経路として探索されることになる。
【００７２】
図１１は、第２の実施の形態のナビゲーション装置２によるテーブル選択モデルの学習の動作を示す図である。第２の実施の形態のナビゲーション装置２の基本的な動作は、第１の実施の形態のナビゲーション装置１と同じであるが、第２の実施の形態では、推奨経路探索の処理（Ｓ１７）が第１の実施の形態のナビゲーション装置１とは異なる。第２の実施の形態のナビゲーション装置１は、リンクの通過回数をパラメータの一つとして経路のコスト計算を行い、コスト最小経路を探索する。そして、コスト最小経路が求まると、学習ルートによる補正を行わず、コスト最小経路を推奨経路の探索結果とする。
【００７３】
また、第２の実施の形態のナビゲーション装置２の学習の動作では、テーブル選択モデルの学習（Ｓ２２）を行った後に、ルート学習の処理を行わないで学習処理を終了する。
【００７４】
以上、第２の実施の形態のナビゲーション装置２の構成および動作について、第１の実施の形態のナビゲーション装置１との相違点を中心に説明した。
【００７５】
第２の実施の形態のナビゲーション装置１は、第１の実施の形態と同様に、過去の通過回数に基づいて選択した適切な走行経路（教師信号）を用いて、テーブル選択モデルを適切に学習するので、経路探索の際に、経路探索の条件に応じて適切な評価関数を選択できる。
【００７６】
また、本実施の形態のナビゲーション装置２は、状況に応じて適切な重み係数テーブルを用いてコスト最小経路を探索する際に、リンクの通過回数をパラメータとして経路のコストを計算するので、ドライバの走り慣れた道を探索し、推奨経路とすることができる。
【００７７】
以上、本発明のナビゲーション装置およびナビゲーション方法について実施の形態を挙げて詳細に説明したが、本発明は上記した実施の形態に限定されるものではない。
【００７８】
上記した実施の形態では、ナビゲーション装置およびナビゲーション方法について説明したが、上記のナビゲーション方法の各処理をナビゲーション装置に実行させるプログラムも本発明の範囲に含まれる。
【００７９】
上記した第１の実施の形態において、学習ルート記憶部１６は、学習ルートを記憶する際に、当該ルートを学習したときの状況を示す情報を関連付けて記憶することとしてもよい。これにより、推奨経路を探索する際に、学習ルート記憶部１６から状況に応じて適切な学習ルートを読み出し、読み出した学習ルートを用いてコスト最小経路を補正することができる。
【００８０】
上記した第１の実施の形態において、学習ルート記憶部１６にいったん記憶した学習ルートを所定期間にわたって通らなかったときに、その学習ルートの情報を消去する構成を採用してもよい。これにより、利用されなくなったルートによって推奨経路の探索が行われるという不都合を防止できる。学習ルートの情報を消去する構成を採用する際、学習ルートの情報を消去するまでの所定期間を、自宅からの距離に応じて変更することとしてもよい。例えば、自宅から半径１０Ｋｍ未満の領域にある学習ルートについては、１ヶ月間通らなかった場合に学習ルートの情報を消去し、自宅から半径１０Ｋｍ以上の領域にある学習ルートについては、３ヶ月間通らなかった場合に学習ルートの情報を消去する。自宅から遠い場所は、自宅から近い場所に比べて行く回数が少ないので、学習ルートを利用しているか否かの判定の基準を、自宅からの距離に応じて変えることにより、よく通る道であるか否かを適切に判断できる。
【００８１】
学習ルート記憶部１６に記憶する学習ルートに分岐がある場合には、過去にその分岐をどちらに通過したかを示す情報を記憶してもよい。例えば、分岐を右折した回数が１０回、左折した回数が１５回であれば、右折４０％、左折６０％という情報を記憶する。これにより、学習ルート記憶部１６に記憶した学習ルートを用いて推奨経路を探索する場合に、過去の通過実績に基づいて、適切な学習ルートを用いて補正した推奨経路を探索できる。
【００８２】
上記した第２の実施の形態では、リンクを過去に通過した回数を用いて、リンクのコストを計算する例について説明したが、さらに過去にリンクを通過したときに要した通過所要時間を用いてリンクのコストを計算することとしてもよい。
【００８３】
図１２（ａ）は、リンクの通過所要時間を用いてコスト計算を行う実施の形態において地図情報記憶部１０に記憶した道路の属性情報の例を示す図、図１２（ｂ）は重み係数記憶部１２に記憶した重み係数テーブルの例を示す図である。図１２（ａ）に示すように、道路属性として、過去にリンクを通過したときに要した時間を示す「通過所要時間」のデータを記憶している。そのリンクを複数回通過している場合には、通過所要時間は、例えば、過去にリンクを通過したときの所要時間の平均値でもよいし、最頻値でもよい。図１２（ｂ）に示すように重み係数テーブルには、通過所要時間についての重み係数が設定されており、この重み係数を用いてリンクコストを計算する。これにより、通過所要時間が短いリンクを含む経路が推奨経路として探索されやすくなる。
【００８４】
上記した実施の形態では、コスト最小経路を学習ルートで補正して推奨経路を探索する第１の実施の形態と、リンクの通過回数をパラメータとしてコスト最小経路を求める第２の実施の形態について説明したが、第１の実施の形態と第２の実施の形態とを組み合わせた構成を採用してもよい。すなわち、リンクの通過回数をパラメータとしてコスト最小経路を求めた後、学習ルート記憶部１６に記憶された学習ルートで補正を行い、推奨経路を求めてもよい。
【産業上の利用可能性】
【００８５】
本発明によれば、経路探索の条件に応じて評価関数を適切に選択できるように学習が行われ、経路探索を行うカーナビゲーション装置等として有用である。
【図面の簡単な説明】
【００８６】
【図１】第１の実施の形態のナビゲーション装置の構成を示す図である。
【図２】（ａ）道路を構成するノードおよびリンクの例を示す図である。（ｂ）道路の属性情報の例を示す図である。
【図３】重み係数テーブルの例を示す図である。
【図４】テーブル選択モデルの例を示す図である。
【図５】（ａ）コスト最小経路と学習ルートの例を示す図である。（ｂ）推奨経路の例を示す図である。
【図６】ナビゲーション装置にて行う経路探索の動作を示す図である。
【図７】ナビゲーション装置にて行うテーブル選択モデルの学習の全体の動作を示す図である。
【図８】ナビゲーション装置にて行うテーブル選択モデルの学習の詳細な動作を示す図である。
【図９】第２の実施の形態のナビゲーション装置の構成を示す図である。
【図１０】重み係数テーブルの例を示す図である。
【図１１】ナビゲーション装置にて行うテーブル選択モデルの学習の全体の動作を示す図である。
【図１２】（ａ）地図情報記憶部に記憶した道路の属性情報の例を示す図である。（ｂ）重み係数記憶部に記憶した重み係数テーブルの例を示す図である。
【符号の説明】
【００８７】
１，２  ナビゲーション装置
１０  地図情報記憶部
１２  重み係数記憶部
１４  テーブル選択モデル記憶部
１６  学習ルート記憶部
１８  車両位置検出部
２０  スイッチ
２２  ディスプレイ
２４  制御部
２６  テーブル選択部
２８  経路探索部
３０  走行経路取得部
３２  学習可否判定部
３４  モデル学習部
３６  ルート学習部
【図１】
2008292237.tif 000003
【図２】
2008292237.tif 000004
【図３】
2008292237.tif 000005
【図４】
2008292237.tif 000006
【図５】
2008292237.tif 000007
【図６】
2008292237.tif 000008
【図７】
2008292237.tif 000009
【図８】
2008292237.tif 000010
【図９】
2008292237.tif 000011
【図１０】
2008292237.tif 000012
【図１１】
2008292237.tif 000013
【図１２】
2008292237.tif 000014