JP5506252B2 - 経路探索装置および経路探索方法 - Google Patents

Description

本発明は、経路探索技術に関するものである。

従来、ナビゲーション装置では、最適経路から逸脱した際に、実際の走行経路を学習区間として記憶し、後に最適経路を探索する際に、当該学習区間の始点と終点とが経路に含まれる場合には、始点から終点までの経路を学習区間と置き換えて探索する経路学習に関する技術が用いられている。特許文献１には、このようなナビゲーション装置についての技術が記載されている。

特開２００１−１７４２８０号公報

上記のようなナビゲーション装置では、探索する経路が学習区間の始点と終点とを含む場合には、探索する経路に関係なく、逸脱区間の経路と置き換える。そのため、使用者が望まない遠回りの経路が探索されてしまうことがあった。

本発明の目的は、探索する経路に応じて、より適切に学習経路を適用する技術を提供することにある。

上記課題を解決すべく、本発明に係る経路探索装置は、道路リンクを含む地図データを記憶する地図データ記憶手段と、現在地から目的地までの経路を、前記地図データ記憶手段に記憶されている道路リンクを用いて探索する経路探索手段と、前記経路探索手段により探索された経路から逸脱して走行したか否かを判定する逸脱判定手段と、前記逸脱判定手段により前記経路から逸脱して走行したと判定した場合に、前記経路探索手段により探索された経路から逸脱する直前のリンクである逸脱直前リンクを、逸脱した位置に関連する道路リンクとして、前記経路探索手段により探索された経路へ復帰した直後のリンクである復帰直後リンクを、復帰した位置に関連する道路リンクとして、格納し、逸脱して走行した経路を置換優先度と対応付けて格納し、前記経路探索手段により探索された経路が設定されていない状態で走行した走行経路に、前記逸脱情報記憶手段に格納された前記逸脱して走行した経路に該当する経路が含まれる場合、当該逸脱して走行した経路の置換優先度を高める逸脱情報記憶手段と、記逸脱直前リンクと、前記復帰直後リンクとが、前記経路探索手段により探索した経路に含まれる場合に、前記経路探索手段により探索した経路のうち少なくとも一部を、前記逸脱情報記憶手段に格納された経路のうち前記置換優先度が高い経路と優先的に置き換える経路置換手段と、を備えることを特徴とする。

また、本発明の経路探索方法は、経路探索装置が、道路リンクを含む地図データを記憶する地図データ記憶手段と、現在地から目的地までの経路を、前記地図データ記憶手段に記憶されている道路リンクを用いて探索する経路探索手段と、を備え、前記経路探索手段により探索された経路から逸脱して走行したか否かを判定する逸脱判定ステップと、前記逸脱判定ステップにより前記経路から逸脱して走行したと判定した場合に、前記経路探索手段により探索された経路から逸脱する直前のリンクである逸脱直前リンクを、逸脱した位置に関連する道路リンクとして、前記経路探索手段により探索された経路へ復帰した直後のリンクである復帰直後リンクを、復帰した位置に関連する道路リンクとして、格納し、逸脱して走行した経路を置換優先度と対応付けて格納し、前記経路探索手段により探索された経路が設定されていない状態で走行した走行経路に、前記逸脱情報記憶手段に格納された前記逸脱して走行した経路に該当する経路が含まれる場合、当該逸脱して走行した経路の置換優先度を高める逸脱情報記憶ステップと、前記逸脱直前リンクと、前記復帰直後リンクとが、前記経路探索手段により探索した経路に含まれる場合に、前記経路探索手段により探索した経路のうち少なくとも一部を、前記逸脱情報記憶ステップにて格納された経路のうち前記置換優先度が高い経路と優先的に置き換える経路置換ステップと、を実施することを特徴とする。

図１は、ナビゲーション装置の概略構成図である。 図２は、リンクテーブルの構成を示す図である。 図３は、学習経路テーブルの構成を示す図である。 図４は、演算処理部の機能構成図である。 図５は、最適経路探索処理のフロー図である。 図６は、使用者の意図に沿わない学習経路の置換を示す図である。 図７は、使用者の意図に沿う学習経路の置換を示す図である。 図８は、経路学習処理のフロー図である。 図９は、最適経路探索処理の変形例を示す図である。

以下に、本発明の一実施形態を適用した車載装置であるナビゲーション装置１００について、図面を参照して説明する。

図１に、ナビゲーション装置１００の構成図を示す。

ナビゲーション装置１００は、演算処理部１と、ディスプレイ２と、記憶装置３と、音声入出力装置４（音声入力装置としてマイクロフォン４１、音声出力装置としてスピーカ４２を備える）と、入力装置５と、ＲＯＭ装置６と、車速センサ７と、ジャイロセンサ８と、ＧＰＳ(Global Positioning System)受信装置９と、ＦＭ多重放送受信装置１０と、ビーコン受信装置１１と、を備えている。

演算処理部１は、様々な処理を行う中心的ユニットである。例えば各種センサ７,８やＧＰＳ受信装置９、ＦＭ多重放送受信装置１０等から出力される情報を基にして現在地を検出する。また、得られた現在地情報に基づいて、表示に必要な地図データを記憶装置３あるいはＲＯＭ装置６から読み出す。そして、走行した経路を学習経路として記録する。

また、演算処理部１は、読み出した地図データをグラフィックス展開し、そこに現在地を示すマークを重ねてディスプレイ２へ表示する。また、記憶装置３あるいはＲＯＭ装置６に記憶されている地図データ等を用いて、ユーザから指示された出発地（現在地）と目的地とを結ぶ最適な経路（推奨経路）を探索する。その際には、学習した経路を用いて、ユーザの望む経路を適切に特定する。また、スピーカ４２やディスプレイ２を用いてユーザを誘導する。

ナビゲーション装置１００の演算処理部１は、各デバイス間をバス２５で接続した構成である。演算処理部１は、数値演算及び各デバイスを制御するといった様々な処理を実行するＣＰＵ(Central Processing Unit)２１と、記憶装置３から読み出した地図データ、演算データなどを格納するＲＡＭ(Random Access Memory)２２と、プログラムやデータを格納するＲＯＭ(Read Only Memory)２３と、各種ハードウェアを演算処理部１と接続するためのＩ／Ｆ（インターフェイス）２４と、を有する。

ディスプレイ２は、演算処理部１等で生成されたグラフィックス情報を表示するユニットである。ディスプレイ２は、液晶ディスプレイ、有機ＥＬディスプレイなどで構成される。

記憶装置３は、ＨＤＤ（Hard Disk Drive）や不揮発性メモリカードといった、少なくとも読み書きが可能な記憶媒体で構成される。

この記憶媒体には、通常の経路探索装置に必要な地図データ（地図上の道路を構成するリンクのリンクデータを含む）であるリンクテーブル２００と、学習経路テーブル２５０と、が記憶されている。

図２は、リンクテーブル２００の構成を示す図である。リンクテーブル２００は、地図上の区画された領域であるメッシュの識別コード（メッシュＩＤ）２０１ごとに、そのメッシュ領域に含まれる道路を構成する各リンクのリンクデータ２０２を含んでいる。

リンクデータ２０２は、リンクの識別子であるリンクＩＤ２１１ごとに、リンクを構成する２つのノード（開始ノード、終了ノード）の座標情報２２２、リンクを含む道路の種別を示す道路種別２２３、リンクの長さを示すリンク長２２４、予め記憶されたリンク旅行時間２２５、当該リンクの開始ノードに接続するリンクである開始接続リンクと、当該リンクの終了ノードに接続するリンクである終了接続リンクと、を特定する開始接続リンク、終了接続リンク２２６、リンクを含む道路の制限速度を示す制限速度２２７、などを含んでいる。

なお、ここでは、リンクを構成する２つのノードについて開始ノードと終了ノードとを区別することで、同じ道路の上り方向と下り方向とを、それぞれ別のリンクとして管理するようにしている。

図３は、学習経路テーブル２５０の構成を示す図である。学習経路テーブル２５０は、格納するレコードごとに、学習経路を特定する情報を記録するテーブルである。例えば、学習経路テーブル２５０は、学習経路に進入する方向を特定することができる逸脱直前リンク２５１および逸脱リンク２５２と、学習経路を構成するリンクを特定する学習経路のリンク列２５３と、学習経路から退出する方向を特定することができる復帰直前リンク２５４および復帰リンク２５５と、当該学習経路を他の学習経路と比べて優先的に適用する度合いを示す置換優先度２５６と、を含んでいる。

逸脱直前リンク２５１には、当該学習経路に進入する直前に走行するリンクを特定する情報が格納される。

逸脱リンク２５２には、当該学習経路に進入した直後に走行するリンクを特定する情報が格納される。

学習経路のリンク列２５３には、走行する順に従って、学習経路を構成するリンクを特定する情報が格納される。例えば、学習経路を構成するリンクは、逸脱リンクに続く経路の途中のリンクを通過順に並べた経路情報と、当該経路情報の最後のリンクである復帰直前リンクと、の情報を有する。

復帰直前リンク２５４には、当該学習経路から退出する直前に走行するリンクを特定する情報が格納される。

復帰リンク２５５には、当該学習経路から退出した直後に走行するリンクを特定する情報が格納される。

置換優先度２５６には、当該学習経路を他の学習経路と比べて優先的に適用する度合いを示す。本実施形態では、置換優先度の値が大きいほど、当該学習経路は、他の学習経路に比べて優先的に適用される。

図１に戻って説明する。音声入出力装置４は、音声入力装置としてマイクロフォン４１と、音声出力装置としてスピーカ４２と、を備える。マイクロフォン４１は、使用者やその他の搭乗者が発した声などのナビゲーション装置１００の外部の音声を取得する。

スピーカ４２は、演算処理部１で生成された使用者へのメッセージを音声信号として出力する。マイクロフォン４１とスピーカ４２は、車両の所定の部位に、別個に配されている。ただし、一体の筐体に収納されていても良い。ナビゲーション装置１００は、マイクロフォン４１及びスピーカ４２を、それぞれ複数備えることができる。

入力装置５は、使用者からの指示を使用者による操作を介して受け付ける装置である。入力装置５は、タッチパネル５１と、ダイヤルスイッチ５２と、その他のハードスイッチ（図示しない）であるスクロールキー、縮尺変更キーなどで構成される。

タッチパネル５１は、ディスプレイ２の表示面側に搭載され、表示画面を透視可能である。タッチパネル５１は、ディスプレイ２に表示された画像のＸＹ座標と対応したタッチ位置を特定し、タッチ位置を座標に変換して出力する。タッチパネル５１は、感圧式または静電式の入力検出素子などにより構成される。

ダイヤルスイッチ５２は、時計回り及び反時計回りに回転可能に構成され、所定の角度の回転ごとにパルス信号を発生し、演算処理部１に出力する。演算処理部１では、パルス信号の数から、回転角度を求める。

ＲＯＭ装置６は、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等のＲＯＭ（Read Only Memory）や、ＩＣ（Integrated Circuit）カードといった、少なくとも読み取りが可能な記憶媒体で構成されている。この記憶媒体には、例えば、動画データや、音声データなどが記憶されている。

車速センサ７,ジャイロセンサ８およびＧＰＳ受信装置９は、ナビゲーション装置１００で現在地（自車位置）を検出するために使用されるものである。

車速センサ７は、車速を算出するのに用いる値を出力するセンサである。

ジャイロセンサ８は、光ファイバジャイロや振動ジャイロ等で構成され、移動体の回転による角速度を検出するものである。

ＧＰＳ受信装置９は、ＧＰＳ衛星からの信号を受信し移動体とＧＰＳ衛星間の距離と距離の変化率とを３個以上の衛星に対して測定することで移動体の現在位置、進行速度および進行方位を測定するものである。

ＦＭ多重放送受信装置１０は、ＦＭ多重放送局から送られてくるＦＭ多重放送信号を受信する。ＦＭ多重放送には、ＶＩＣＳ（Vehicle Information Communication System：登録商標）情報の概略現況交通情報、規制情報、ＳＡ／ＰＡ（サービスエリア／パーキングエリア）情報、駐車場情報、天気情報などやＦＭ多重一般情報としてラジオ局が提供する文字情報などがある。

ビーコン受信装置１１は、ＶＩＣＳ情報などの概略現況交通情報、規制情報、ＳＡ／ＰＡ（サービスエリア／パーキングエリア）情報、駐車場情報、天気情報や緊急警報などを受信する。例えば、光により通信する光ビーコン、電波により通信する電波ビーコン等の受信装置である。

図４は、演算処理部１の機能ブロック図である。図示するように、演算処理部１は、主制御部１０１と、入力受付部１０２と、出力処理部１０３と、経路探索部１０４と、経路置換部１０５と、学習経路管理部１０６と、を有する。

主制御部１０１は、様々な処理を行う中心的な機能部であり、処理内容に応じて、他の処理部を制御する。また、各種センサ、ＧＰＳ受信装置９等の情報を取得し、マップマッチング部１０４等に依頼して現在位置を特定する。また、随時、走行した日付および時刻と、位置と、を対応付けて、リンクごとに走行履歴を記憶装置３に記憶する。さらに、各処理部からの要求に応じて、現在時刻を出力する。また、ユーザから指示された出発地（現在地）と目的地とを結ぶ最適な経路（推奨経路）を探索し、推奨経路から逸脱しないよう、スピーカ４２やディスプレイ２を用いてユーザを誘導する。

入力受付部１０２は、入力装置５またはマイクロフォン４１を介して入力された使用者からの指示を受け付け、その要求内容に対応する処理を実行するように演算処理部１の各部を制御する。例えば、使用者が推奨経路の探索を要求したときは、目的地を設定するため、地図をディスプレイ２に表示する処理を出力処理部１０３に要求する。

出力処理部１０３は、表示させる画面情報を受け取り、ディスプレイ２に描画するための信号に変換してディスプレイ２に対して描画する指示を行う。

経路探索部１０４は、主制御部１０１により検出した現在位置を示す情報と、リンクテーブル２００に格納された地図データ等を用いて、目的地に到るまでの経路を探索する。具体的には、例えば、経路探索部１０４は、現在位置を示す情報により示される位置を出発地として、目的地へ到る経路をダイクストラ法等の経路探索法に従って探索する。なお、経路探索部１０４は、経路置換部１０５に依頼して、探索した結果得られた経路の一部について、所定の条件を満たす場合に、優先度の高い学習経路と置き換える。なお、経路探索部１０４は、経路上の学習経路に置き換えられた部分について、再度学習経路を適用して置き換えることは行わない。そして、経路探索部１０４は、学習経路を反映させた経路を推奨経路として記憶する。

経路置換部１０５は、経路探索部１０４にて経路を探索する際に、所定の条件を満たす場合には、経路探索部１０４が探索した経路の一部を学習経路と置き換える。所定の条件とは、学習経路の始点と終点とが当該経路に含まれ、かつ、当該始点および終点における走行方向が探索された経路と一致するか否かである（具体的には、始点については始点直前のリンクが当該経路に含まれ、終点については終点直後のリンクが当該経路に含まれるか否かである）。すなわち、経路置換部１０５は、学習経路に進入する方向および退出する方向を加味して、学習経路と置き換えるか否かを判定する。

学習経路管理部１０６は、学習経路を記録する。また、学習経路管理部１０６は、学習経路の置換優先度を管理する。すなわち、学習経路管理部１０６は、新たに学習すべき経路を登録するとともに、既に登録された学習経路について置換優先度を管理する。具体的には、学習経路管理部１０６は、推奨経路から逸脱して走行した場合に、当該逸脱した区間（逸脱してからもとの推奨経路に復帰するまでの区間）を、逸脱区間として特定する。そして、特定した逸脱区間が、既に学習経路として学習経路テーブル２５０に登録されているか否かを判定し、既に登録されている場合には、当該学習経路の置換優先度を増加させ、登録されていない場合には、当該逸脱区間を学習経路として新たに登録する。

また、学習経路管理部１０６は、推奨経路が設定されていない状態で走行した経路について、既に登録済みの学習経路が含まれているか否かを判定する。そして、学習経路管理部１０６は、当該経路に登録済みの学習経路が含まれている場合には、該当する学習経路の置換優先度を増加させる。

また、学習経路管理部１０６は、所定の期間（例えば２週間）ごとに、学習経路テーブル２５０に登録された各学習経路の置換優先度を、減少させる。このようにすることで、新たに学習経路として登録された経路と、何度も走行している学習経路と、についての優先度の差を所定の範囲内に収め、優先度の逆転をある程度容易とすることが可能となる。例えば、学習経路管理部１０６は、最大の置換優先度を有する学習経路の置換優先度が１０以下となるように、他の学習経路の置換優先度を一律の値で減少させる（ただし、置換優先度は負の値にはならず、最低でも０とする）ことで、優先度の差を所定の範囲内に収めるようにする。

上記した演算処理部１の各機能部、すなわち主制御部１０１、入力受付部１０２、出力処理部１０３、経路探索部１０４、経路置換部１０５、学習経路管理部１０６は、ＣＰＵ２１が所定のプログラムを読み込み実行することにより構築される。そのため、ＲＡＭ２１には、各機能部の処理を実現するためのプログラムが記憶されている。

なお、上記した各構成要素は、ナビゲーション装置１００の構成を理解容易にするために、主な処理内容に応じて分類したものである。そのため、構成要素の分類の仕方やその名称によって、本願発明が制限されることはない。ナビゲーション装置１００の構成は、処理内容に応じて、さらに多くの構成要素に分類することもできる。また、１つの構成要素がさらに多くの処理を実行するように分類することもできる。

また、各機能部は、ハードウェア（ＡＳＩＣ、ＧＰＵなど）により構築されてもよい。また、各機能部の処理が一つのハードウェアで実行されてもよいし、複数のハードウェアで実行されてもよい。

［動作の説明］
次に、ナビゲーション装置１００の動作について説明する。

図５は、経路探索時において、探索した経路に学習経路へと置き換えるべき部分が含まれているか否かを判定し、含まれている場合には、当該学習経路に置き換える最適経路探索処理のフロー図である。このフローは、ナビゲーション装置１００が目的地の指定を伴う使用者からの経路探索の指示を受け付けることで開始される。

まず、経路探索部１０４は、出発地から目的地へ到る経路を探索する。この探索においては、通常の経路探索ロジック、例えばダイクストラ法等による経路探索ロジックを適用する。そして、経路置換部１０５は、探索して得られた経路（以降、探索経路とする）の全域について、「未確定区間」と設定する（ステップＳ００１）。具体的には、経路置換部１０５は、探索して得られた経路を構成するリンクのすべてに対して、「未確定区間」である旨の情報を対応付ける。

次に、経路置換部１０５は、学習経路テーブル２５０を探索して、未比較の学習経路が探索経路に含まれているか否かを判定する（ステップＳ００２）。具体的には、経路置換部１０５は、学習経路テーブル２５０に格納されている学習経路のうち、ステップＳ００３以降の処理を行っていない学習経路が含まれない場合には、未比較の学習経路はないものと判定する。

未比較の学習経路がない場合（ステップＳ００２にて「Ｎｏ」）、経路置換部１０５は、最終的に得られた探索経路の情報を経路探索部１０４に受け渡し、最適経路探索処理を終了させる。

未比較の学習経路がある場合（ステップＳ００２にて「Ｙｅｓ」）、経路置換部１０５は、置換優先度２５６が高い順に、未比較の学習経路を一つ選択する（ステップＳ００３）。

次に、経路置換部１０５は、選択した学習経路の置換優先度２５６の値が、所定の値（例えば、置換優先度「３」）以上か否かを判定する（ステップＳ００４）。置換優先度の値が所定の値を下回る場合には、経路置換部１０５は、最適経路探索処理により得られた探索経路の情報を経路探索部１０４に受け渡し、最適経路探索処理を終了させる。

置換優先度の値が所定の値以上である場合には、経路置換部１０５は、探索経路内の未確定区間として設定された区間内に、選択した学習経路の逸脱直前リンク２５１を含むか否かを判定する（ステップＳ００５）。

選択した学習経路の逸脱直前リンク２５１が経路に含まれない場合（ステップＳ００５にて「Ｎｏ」）、経路置換部１０５は、当該学習経路を比較済みとして、ステップＳ００２に処理を戻す。

選択した学習経路の逸脱直前リンク２５１を含む場合（ステップＳ００５にて「Ｙｅｓ」）、経路置換部１０５は、探索経路の経路逸脱直前リンクから目的地までの未確定区間に、学習経路の復帰リンク２５５を含むか否かを判定する（ステップＳ００６）。

経路逸脱直前リンクから目的地までの未確定区間に学習経路の復帰リンクを含まない場合（ステップＳ００６にて「Ｎｏ」）、経路置換部１０５は、該学習経路を比較済みとして、ステップＳ００２に処理を戻す。

経路逸脱直前リンクから目的地までの未確定区間に学習経路の復帰リンクを含む場合（ステップＳ００６にて「Ｙｅｓ」）、経路置換部１０５は、経路上の逸脱直前リンクから復帰リンクまでの区間に、確定区間が含まれるか否かを判定する（ステップＳ００７）。

経路上の逸脱直前リンクから復帰リンクまでの区間に、確定区間が含まれる場合（ステップＳ００７にて「Ｙｅｓ」）、経路置換部１０５は、該学習経路を比較済みとして、ステップＳ００２に処理を戻す。

経路上の逸脱直前リンクから復帰リンクまでの区間に、確定区間が含まれない場合（ステップＳ００７にて「Ｎｏ」）、経路置換部１０５は、経路上の逸脱直前リンクから復帰リンクまでの区間を、当該学習経路で置換して、置換した区間に含まれるリンクを確定区間に設定するとともに、該学習経路を比較済みとして、ステップＳ００２に処理を戻す。

以上が、最適経路探索処理の処理内容である。

上記の最適経路探索処理を行う事によって、ナビゲーション装置１００は、経路探索時に所定の条件を満たす場合、経路の一部を学習経路へ置き換えることができる。また、当該置き換えの条件は、置き換える対象の経路における学習経路への進入方向が、学習経路が備える進入方向の情報と一致し、かつ、置き換える対象の経路における学習経路からの退出方向が、学習経路が備える退出方向の情報と一致することである。そのため、たとえ学習経路の始点と終点を含む経路であっても、学習経路への進入方向または学習経路からの退出方向が異なる経路については、置き換えが行われず、より使用者の意図に沿う学習経路の適用が可能となる。

また、上記の最適経路探索処理においては、未確定区間あるいは確定区間という情報を用いることで、既に学習経路への置き換えを行った区間および当該区間を含む区間については、再度の置き換えを行わないように制御している。これにより、置き換えの重要度が高くない経路の適用を抑制しつつ、過度にまわり道を行い複雑になる経路の探索を阻止することができる。

ここで、図６、図７を用いて、学習経路の置換の具体例を対比して説明する。図６、図７は、本発明に係るナビゲーション装置による学習経路適用例を示す図である。

図６および図７では、ノード３２１Ｎ〜３２６Ｎと、ノード３２１Ｎ〜３２６Ｎに接続されるリンク３１０Ｌ〜３１６Ｌと、ノード３４１Ｎおよびノード３４２Ｎと、ノード３４１Ｎおよびノード３４２Ｎに接続されるリンク３３１Ｌ〜３３３Ｌと、ノード３６１Ｎおよびノード３６２Ｎと、ノード３６１Ｎおよびノード３６２Ｎに接続されるリンク３５１Ｌ〜リンク３５３Ｌと、ノード３２５Ｎに接続されるリンク３５４Ｌと、が示されている。

図示するように、リンク３１０Ｌは、ノード３２１Ｎにおいてリンク３１１Ｌに接続している。リンク３１１Ｌは、ノード３２２Ｎにおいてリンク３１２Ｌ、リンク３３１Ｌおよびリンク３５３Ｌに接続している。リンク３１２Ｌは、ノード３２３Ｎにおいてリンク３１３Ｌと接続している。リンク３１３Ｌは、ノード３２４Ｎにおいてリンク３１４Ｌと接続している。リンク３１４Ｌは、ノード３２５Ｎにおいてリンク３１５Ｌ、リンク３３３Ｌおよびリンク３５４Ｌと接続している。リンク３１５Ｌは、ノード３２６Ｎにおいてリンク３１６Ｌに接続している。

また、リンク３５１Ｌは、ノード３６１Ｎにおいてリンク３５２Ｌに接続しており、リンク３５２Ｌはノード３６２Ｎにおいてリンク３５３Ｌに接続している。リンク３５３Ｌは、ノード３２２Ｎにおいてリンク３１１Ｌ、リンク３１２Ｌおよびリンク３３１Ｌに接続している。リンク３３１Ｌは、ノード３４１Ｎにおいてリンク３３２Ｌに接続している。リンク３３２Ｌは、ノード３４２Ｎにおいてリンク３３３Ｌに接続している。リンク３３３Ｌは、ノード３２５Ｎにおいてリンク３１４Ｌ、リンク３１５Ｌおよびリンク３５４Ｌに接続している。

なお、ノード３２２Ｎは、十字路を構成しており、リンク３１１Ｌとリンク３１２Ｌとを含む道路が、リンク３５３Ｌとリンク３３１Ｌとを含む道路と交差する。同様に、ノード３２５Ｎについても、十字路を構成しており、リンク３１４Ｌとリンク３１５Ｌとを含む道路が、リンク３３３Ｌとリンク３５４Ｌとを含む道路と交差する。

ここで、学習経路が、ノード３２２Ｎ、ノード３４１Ｎ、ノード３４２Ｎ、ノード３２５Ｎを通る経路として登録されている場合を想定して、図６（ａ）、図６（ｂ）を説明する。なお、図６（ａ）、図６（ｂ）については、学習経路への進入方向と学習経路からの退出方向とを考慮する本発明と対比するための説明である。本発明による学習経路の適用処理の例は、図７（ａ）、図７（ｂ）に示す。

図６（ａ）は、学習経路を考慮せずに探索した経路が、ノード３２１Ｎ、ノード３２２Ｎ、ノード３２３Ｎ、ノード３２４Ｎ、ノード３２５Ｎ、ノード３２６Ｎを通過する経路である場合を示す。この場合、当該経路は学習経路の始点ノードであるノード３２２Ｎと、終点ノードであるノード３２５Ｎとを通過する経路であるため、ノード３２２Ｎからノード３２５Ｎまでの区間が学習経路と置き換えられて、探索経路となる。

図６（ｂ）は、学習経路を考慮せずに探索した経路が、ノード３６１Ｎ、ノード３６２Ｎ、ノード３２２Ｎ、ノード３２３Ｎ、ノード３２４Ｎ、ノード３２５Ｎおよびリンク３５４Ｌを通過する経路である場合を示す。この場合にも、当該経路は学習経路の始点ノードであるノード３２２Ｎと、終点ノードであるノード３２５Ｎとを通過する経路であるため、ノード３２２Ｎからノード３２５Ｎまでの区間が学習経路と置き換えられて、探索経路となる。しかし、特に図６（ｂ）に示す場合にあっては、学習経路を適用すると大回りとなってしまう経路であるため、実際には、使用者が望んでいる経路とは異なる可能性が高い。

ここで、本発明に係るナビゲーション装置１００を用いた場合であって、学習経路が、ノード３２２Ｎ、ノード３４１Ｎ、ノード３４２Ｎ、ノード３２５Ｎを通る経路として登録されている場合の学習経路の適用について、図７（ａ）、図７（ｂ）を用いて説明する。

なお、本発明に係る最適経路探索処理では、学習経路には進入および退出の方向の概念があるため、ここでは逸脱直前リンクを３１１Ｌ、逸脱リンクを３３１Ｌ、復帰直前リンクを３３３Ｌ、復帰リンクを３１５Ｌとする。

図７（ａ）は、学習経路を考慮せずに探索した経路が、ノード３２１Ｎ、ノード３２２Ｎ、ノード３２３Ｎ、ノード３２４Ｎ、ノード３２５Ｎ、ノード３２６Ｎを通過する経路である場合を示す。この場合、当該経路は学習経路の逸脱直前リンクであるリンク３１１Ｌを通過し、復帰リンク３１５Ｌを通過する経路であるため、ノード３２２Ｎからノード３２５Ｎまでの区間が学習経路と置き換えられて、探索経路となる。

これに対し、図７（ｂ）は、学習経路を考慮せずに探索した経路が、ノード３６１Ｎ、ノード３６２Ｎ、ノード３２２Ｎ、ノード３２３Ｎ、ノード３２４Ｎ、ノード３２５Ｎおよびリンク３５４Ｌを通過する経路である場合を示す。この場合には、当該経路は学習経路の逸脱直前リンクであるリンク３１１Ｌを通過せず、復帰リンク３１５Ｌを通過しない経路であるため、ノード３２２Ｎからノード３２５Ｎまでの区間が学習経路と置き換えられることはない。そのため、特に図６（ｂ）の場合と比較して、学習経路を適用しないで大回りを避けることができるため、使用者の望みの経路となる可能性が高い。

このように、本発明に係る最適経路探索処理を適用することで、経路への進入方向および退出方向を加味して学習経路の適用が可能となるため、より適切に学習経路を適用することができる。

また、上記実施形態において、学習経路の置換優先度を管理する経路学習処理について、図８を用いて説明する。図８は、経路学習処理についてのフロー図である。このフローは、ナビゲーション装置１００が搭載された車両が走行を終了する際、例えばナビゲーション装置１００の終了処理において開始される。

まず、主制御部１０１は、走行履歴を記録する（ステップＳ２０１）。具体的には、主制御部１０１は、走行した期間について、所定のタイミングにおける現在位置の情報を記録して、当該位置が属するリンクを特定して記録する。

次に、学習経路管理部１０６は、当該走行期間、すなわち直近にナビゲーション装置１００を起動した後に推奨経路が設定されたか否かを判定する（ステップＳ２０２）。

推奨経路が設定されていなかった場合（ステップＳ２０２にて「Ｎｏ」）、学習経路管理部１０６は、走行履歴に含まれる区間であって、既登録の学習経路に該当する区間を特定する（ステップＳ２０３）。

そして、学習経路管理部１０６は、該当する学習経路の優先度を増加させる。そして、学習経路管理部１０６は、経路学習処理を終了させる（ステップＳ２０４）。具体的には、学習経路管理部１０６は、ステップＳ２０３にて特定した既登録の学習経路の置換優先度２５６の値を、所定の値だけ増加させる（例えば、「＋１」する）。

推奨経路が設定されていた場合（ステップＳ２０２にて「Ｙｅｓ」）、学習経路管理部１０６は、推奨経路から逸脱して走行した区間を特定する（ステップＳ２０５）。そして、学習経路管理部１０６は、逸脱した区間が既登録の学習経路と一致するか否かを判定する（ステップＳ２０６）。

逸脱した区間が既登録の学習経路と一致する場合（ステップＳ２０６において「Ｙｅｓ」）、学習経路管理部１０６は、ステップＳ２０４に処理を進める。

逸脱した区間が既登録の学習経路と一致しない場合（ステップＳ２０６において「Ｎｏ」）、学習経路管理部１０６は、逸脱区間について、逸脱直前リンクと、逸脱リンクと、復帰直前リンクと、復帰リンクと、逸脱リンクから復帰直前リンク間の走行経路と、を特定して、学習経路テーブルに登録する。そして、学習経路管理部１０６は、経路学習処理を終了させる（ステップＳ２０７）。

以上が、経路学習処理の処理内容である。

経路学習処理を行う事により、走行後に学習経路の登録および学習経路の置換優先度の管理を行うことが可能となる。とくに、推奨経路が設定されていない状態での走行に関しても学習経路の管理が可能となるため、適切な学習を行うことが可能となる。使用者は、よく見知った場所を走行する際には特に経路探索を行わないことが多く、そのような場所の走行経路を学習状況に反映させることで、使用者の走行の習性に応じた最適経路を設定することが可能となる。

以上、本発明の一実施形態について説明した。

本発明の一実施形態によると、ナビゲーション装置１００は、使用者の望まない大回りの経路の探索を抑制し、探索する経路に応じて、より適切に学習経路を適用することができる。

また、推奨経路が設定されていない状態で走行した走行履歴から、経路の学習を行うことが可能となる。

本発明は、上記実施形態に制限されない。上記実施形態は、本発明の技術的思想の範囲内で様々な変形が可能である。例えば、上記実施形態における最適経路探索処理について、図９に示す処理内容とすることが可能である。

図９は、図５に示した最適経路探索処理のフローと基本的に同じフローを示す。しかし、ステップＳ００７とステップＳ００８との間で、ステップＳ１０８の処理が行われる点において、図５に示したフローと相違する。

ステップＳ１０８は、置換する学習経路の渋滞度が所定以上であれば、置換しない、という処理である。具体的には、経路置換部１０５は、置換する学習経路に含まれるリンクに、所定の渋滞度以上の渋滞度のリンクが含まれている場合、当該学習経路の置換を取りやめる。または、経路置換部１０５は、学習経路に含まれるリンクの渋滞度と、置換される経路の渋滞度とを比べて、学習経路のリンクの方が渋滞している場合には、置換を取りやめる。なお、経路置換部１０５は、渋滞度として、ＶＩＣＳ情報などの概略現況交通情報から取得した渋滞度を用いる。

当該処理は、ステップＳ００７とステップＳ００８の間で行う必要があるわけではなく、ステップＳ００３からステップＳ００８までのいずれかの処理の間で行うようにすればよい。例えば、ステップＳ００４とステップＳ００５の間で行うものであってもよい。

このようにすることで、より適切に学習経路を推奨経路に反映させることができるようになる。

また、上記実施形態においては、最適経路探索処理のステップＳ００３において、置換優先度が高い順に、未比較学習経路から学習経路を選択しているが、これに限られない。例えば、学習経路テーブル２５０に格納された学習経路が、置換優先度２５６の値が高い順にソートされて予め格納されるものであってもよい。かかる場合、経路置換部１０５は、ステップＳ００３において、ソートされた順に従って学習経路を選択する。このようにすることで、経路探索の際の処理負荷を低く抑えることができる。

以上が、変形の例である。

なお、上記の実施形態では、本発明を車載ナビゲーション装置に適用した例について説明したが、本発明は車載ナビゲーション装置に限らず、ナビゲーション装置全般に適用することができる。

１・・・演算処理部、２・・・ディスプレイ、３・・・記憶装置、４・・・音声出入力装置、５・・・入力装置、６・・・ＲＯＭ装置、７・・・車速センサ、８・・・ジャイロセンサ、９・・・ＧＰＳ受信装置、１０・・・ＦＭ多重放送受信装置、１１・・・ビーコン受信装置、２１・・・ＣＰＵ、２２・・・ＲＡＭ、２３・・・ＲＯＭ、２４・・・Ｉ／Ｆ、２５・・・バス、４１・・・マイクロフォン、４２・・・スピーカ、５１・・・タッチパネル、５２・・・ダイヤルスイッチ、１００・・・ナビゲーション装置、１０１・・・主制御部、１０２・・・入力受付部、１０３・・・出力処理部、１０４・・・経路探索部、１０５・・・経路置換部、１０６・・・学習経路管理部、２００・・・リンクテーブル、２５０・・・学習経路テーブル

Claims (6)

1. 道路リンクを含む地図データを記憶する地図データ記憶手段と、
   現在地から目的地までの経路を、前記地図データ記憶手段に記憶されている道路リンクを用いて探索する経路探索手段と、
   前記経路探索手段により探索された経路から逸脱して走行したか否かを判定する逸脱判定手段と、
   前記逸脱判定手段により前記経路から逸脱して走行したと判定した場合に、前記経路探索手段により探索された経路から逸脱する直前のリンクである逸脱直前リンクを、逸脱した位置に関連する道路リンクとして、前記経路探索手段により探索された経路へ復帰した直後のリンクである復帰直後リンクを、復帰した位置に関連する道路リンクとして、格納し、逸脱して走行した経路を置換優先度と対応付けて格納し、前記経路探索手段により探索された経路が設定されていない状態で走行した走行経路に、前記逸脱情報記憶手段に格納された前記逸脱して走行した経路に該当する経路が含まれる場合、当該逸脱して走行した経路の置換優先度を高める逸脱情報記憶手段と、
   前記逸脱直前リンクと、前記復帰直後リンクとが、前記経路探索手段により探索した経路に含まれる場合に、前記経路探索手段により探索した経路のうち少なくとも一部を、前記逸脱情報記憶手段に格納された経路のうち前記置換優先度が高い経路と優先的に置き換える経路置換手段と、
   を備えることを特徴とする経路探索装置。
2. 請求項１に記載の経路探索装置であって、
   前記経路置換手段は、前記逸脱情報記憶手段に格納された前記逸脱して走行した経路の渋滞の度合いが所定以上である場合には、当該経路について置換を行わない、
   ことを特徴とする経路探索装置。
3. 請求項１又は２に記載の経路探索装置であって、
   前記経路置換手段は、
   前記置換優先度が高い経路によって置換された区間を含む経路を、置換対象から除外する、
   ことを特徴とする経路探索装置。
4. 経路探索装置を用いた経路探索方法であって、
   前記経路探索装置は、
   道路リンクを含む地図データを記憶する地図データ記憶手段と、
   現在地から目的地までの経路を、前記地図データ記憶手段に記憶されている道路リンクを用いて探索する経路探索手段と、を備え、
   前記経路探索手段により探索された経路から逸脱して走行したか否かを判定する逸脱判定ステップと、
   前記逸脱判定ステップにより前記経路から逸脱して走行したと判定した場合に、前記経路探索手段により探索された経路から逸脱する直前のリンクである逸脱直前リンクを、逸脱した位置に関連する道路リンクとして、前記経路探索手段により探索された経路へ復帰した直後のリンクである復帰直後リンクを、復帰した位置に関連する道路リンクとして、格納し、逸脱して走行した経路を置換優先度と対応付けて格納し、前記経路探索手段により探索された経路が設定されていない状態で走行した走行経路に、前記逸脱情報記憶手段に格納された前記逸脱して走行した経路に該当する経路が含まれる場合、当該逸脱して走行した経路の置換優先度を高める逸脱情報記憶ステップと、
   前記逸脱直前リンクと、前記復帰直後リンクとが、前記経路探索手段により探索した経路に含まれる場合に、前記経路探索手段により探索した経路のうち少なくとも一部を、前記逸脱情報記憶ステップにて格納された経路のうち前記置換優先度が高い経路と優先的に置き換える経路置換ステップと、
   を実施することを特徴とする経路探索方法。
5. 請求項４に記載の経路探索方法であって、
   前記経路置換ステップでは、前記逸脱情報記憶ステップにて格納された前記逸脱して走行した経路の渋滞の度合いが所定以上である場合には、当該経路について置換を行わない、
   ことを特徴とする経路探索方法。
6. 請求項４又は５に記載の経路探索方法であって、
   前記経路置換ステップでは、
   前記置換優先度が高い経路によって置換された区間を含む経路を、置換対象から除外する、
   ことを特徴とする経路探索方法。

Images