JP6238738B2 - 経路探索装置及びその方法、並びに経路を探索するためのコンピュータプログラム及びコンピュータプログラムを記録した記録媒体 - Google Patents

Description

本発明は、車両を走行させて現地調査を行う際、過去の現地調査の走行状況を反映し、効率的な経路を探索する装置及びその方法に関する。

一般に、ナビゲーション装置等で用いられる地図データは、調査対象となる道路を実際に車両で走行して得られる位置情報等の情報や、車載ビデオカメラ等により得られる走行時の車両前後方の撮影画像等に基づいて作成されている。そして、このように車両を走行させて行う現地調査（以下、走行現調ともいう）を効率的に行うために種々の開発が行われてきている。
例えば、特許文献１には、道路調査において、地図情報を取得すべき道路の通行を開始した旨、終了した旨を調査員に警告することにより、地図作成のための情報の取得漏れを軽減する技術が開示されている。
一方、特許文献２には、車両が新規道路を走行中に撮像した画像を地図管理装置へ送信し、画像解析することにより道路地図データを更新する道路地図更新システムが開示されている。詳しくは、上記画像が天候情報に基づいて地図更新に使用可能と判定された場合に限り、当該画像を送信することにより送信回数を減少できるシステムが開示されている。
本発明に関連する従来技術を開示する特許文献３又は４も参照されたい。

特開２００７−２１２９７２号公報 特開２００８−０３９６８７号公報 特開２０１０−２３０３６５号公報 特開２０１０−１８０１０１号公報

本発明者は、より効率的に走行現調を行うべく鋭意検討を重ねてきた。その結果、以下の点に気がついた。
通常、走行現調は、車載ビデオカメラを車両に固定して備え、走行現調の対象となるリンク（以下、対象リンクということがある）を走行して取得される走行画像から、地図データ作成に有用な情報を抽出することにより行われる。そのため、有用な情報、すなわち、道路標識等の交通規制に関する情報や交差点名称を記載した看板（以下、単に「信号機看板」ということがある）に関する文字情報を、撮像範囲内に鮮明に収めることが重要となる。一度の走行現調で、地図データ作成に利用可能な走行画像（鮮明な画像）を取得できれば効率的であるが、常にこのような走行画像を取得することは容易でない。走行画像の鮮明具合は、走行現調時の走行状況に依存するためである。
ここで、走行現調が、最適な走行状況下で行われた場合のみ、取得された走行画像が利用可能な画像であるとして、走行したリンクを走行済みとし、最適とはいえない走行状況下で行われた場合には再度走行を要するリンクとしても良い。しかしながら、最適とはいえない走行状況下で走行現調が実施された場合であっても、同じリンクを複数回走行すれば、それらの走行画像から上記有用な情報が得られることも少なくない。このような場合に、最適とはいえない走行状況下での走行を一律に要再走の対象とするのは効率性に欠ける。
そこで、本発明者は、走行現調の際の走行状況に基づき、リンクごとに取得された走行画像の利用可能度合いを重み付けして、地図データベース内の対応するリンクに関連付けられた重み付け値に反映させ、該反映された重み付け値が第１の閾値未満である対象リンクについて経路探索の対象とすることで、効率的な走行現調を遂行可能なことに想到した。

この発明は上述の課題に鑑みてなされたものであり、その第１の局面は次のように規定される。即ち、
第１のエリア内における所定条件を満たす対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを格納する第１の地図データベースと、
車両が走行した走行履歴を蓄積する走行履歴データベースと、
前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定部と、
前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定部と、
前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新部と、
前記更新された第１の地図データベースを参照して、目的地までの経路であって、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する経路を探索する経路探索部と、
を備える、経路探索装置。

このように規定される第１の局面の経路探索装置によれば、車両の走行履歴に基づいて走行済みリンクを特定し、該走行済みリンクに対応する走行履歴に関連付けて蓄積された走行状況に基づき、走行済みリンクに重み付け値を設定する。そして、設定された重み付け値を、地図データベース内の走行済みリンクに対応する対象リンクに付与された重み付け値に反映させることにより、上記地図データベースを更新する。さらには、該更新された地図データベース内の対象リンクに付与された重み付け値に基づいて、該重み付け値が第１の閾値未満である対象リンク（以下、要再走リンクともいう）を含むように経路探索する。このように、走行現調を行った対象リンクについては、走行状況に応じて重み付けを行い、該重み付けを更新するため、複数回の走行現調に基づいて総合的に走行画像の利用可否を行うことが可能となる。ゆえに、実施された走行現調を効率的に利用することができる。また、走行現調を行うごとに重み付け値を更新するため、自動的に走行を要する対象リンクを特定でき、該特定された対象リンクを含む経路探索が可能になり、走行現調の効率性を向上させることができる。
ここでリンクとは、道路ネットワークデータの構成要素であって、一般に道路の交差点等に対応するノード−ノード間を結ぶ道路に対応して生成されたデータをいう。対象リンクとは、通常の地図データベースに含まれるリンクのうち、走行現調の対象となるリンクであり、例えばリンク属性等を基準として選択される。このようなリンク属性としては、例えば、道路幅、リンク種別、車線数、路線番号等が挙げられる。詳細には、道路幅が所定閾値以上であるリンク、リンク種別が幹線道路、高速道路であるリンク、車線数が所定閾値以上であるリンク等が対象リンクとして選択される。当該対象リンクは、上記リンク属性を基準として選択される他、オペレータの手動により選択することとしても良い。

上記走行済みリンクとは、車両により走行されたリンクである。好ましくは、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定することとすることができる（第４の局面）。このような装置によれば、当該対象リンク全域にわたる情報を取得することができ、より綿密な地図データベースを作成することができる。走行済みリンクの他の例としては、一の対象リンクにおいて所定割合以上（例えば、５０％以上）走行されているリンクを走行済みリンクとしても良い。また、別の例として、一の対象リンクの一部を走行した場合において、その走行した部分について走行済みである旨の情報を、対象リンクに付与することで走行済みリンクとすることとしても良い。例えば、走行履歴が対象リンクから逸脱した座標に基づき、当該逸脱点までを走行済みとしたり、対象リンクのリンク形状に反してハンドル操作を行った場合に当該操作を行った座標に基づき、当該操作地点までを走行済みとすることとしても良い。この場合、上記重み付け設定部は、該走行済みリンク中の走行済み部分に基づいて重み付け値を設定することができる。

上記重み付け値とは、走行現調の際に取得された走行画像の利用可能度合いを、走行現調時の走行状況に基づいて算出した値であって、例えばコストとして表すことができる。当該重み付け値は、重み付け値の低い対象リンクを優先的に経路に含める等、経路探索の際の対象リンク選択の指標として用いられる。他の利用方法としては、例えば、グーグル株式会社のストリートビューのように、一般ユーザが参照する画像として走行画像を公開する場合に、重み付け値の高い、すなわち、良好な走行状況で撮像された走行画像を優先的に公開するための指標とすることもできる。上記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一とすることができる（第５の局面）。

上記経路探索部は、前記第１のエリア内の前記対象リンクを巡回する経路を探索するものとすることができる（第２の局面）。
ここで、巡回経路とは、上記第１のエリア内に存在する対象リンクをより効率良く巡回するための経路であり、このような巡回経路として、例えば、該エリア内の対象リンクを一筆書きの要領で走行する経路や、該エリア内においてより多くの対象リンクを走行しつつ同一の対象リンクを走行する回数を極力抑えた経路等が挙げられる。

所定エリア内において要再走リンクが少なくなったとき、すなわち、第１の閾値以上のコストが付与された対象リンクの割合が大きくなったときには、該要再走リンクのみを巡回するよう経路を探索することは効率性に欠けることとなる。
そこで、この発明の第３の局面は次のように規定される。即ち、
第２の局面に規定の経路探索装置において、第２のエリア内における所定条件を満たす対象リンクに関する情報を含む地図データを格納する第２の地図データベースと、
前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出部と、を備え、
前記経路探索部は、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記経路を探索する。
このように規定される第４の局面の経路探索装置によれば、所定エリア内の第１の閾値以上のコストが付与された対象リンクの割合を算出し、該割合が所定閾値以上であるとき、該エリアに隣接するエリアを含めて巡回経路を探索するため、走行現調の効率性が向上する。

また、この発明の第６の局面は次のように規定される。即ち、
第１のエリア内における所定条件を満たす対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを第１の地図データベースに格納する第１の格納ステップと、
車両が走行した走行履歴を走行履歴データベースに蓄積する蓄積ステップと、
走行済みリンク特定部が、前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定ステップと、
重み付け設定部が、前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定ステップと、
地図データベース更新部が、前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新ステップと、
経路探索部が、前記更新された第１の地図データベースを参照して、目的地までの経路であって、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する経路を探索する経路探索ステップと、
を備える、経路探索方法。
このように規定される第６の局面の発明によれば、第１の局面と同等の効果を奏する。

この発明の第７の局面は次のように規定される。即ち、
第６の局面に規定の方法において、前記経路探索ステップでは、前記第１のエリア内の前記対象リンクを巡回する経路を探索する。
このように規定される第７の局面の発明によれば、第２の局面と同等の効果を奏する。

この発明の第８の局面は次のように規定される。即ち、
第７の局面に規定の方法において、第２のエリア内における所定条件を満たす対象リンクに関する情報を含む地図データを第２の地図データベースに格納する第２の格納ステップと、
割合算出部が、前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出ステップと、を備え、
前記経路探索ステップでは、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記経路を探索する。
このように規定される第８の局面の発明によれば、第３の局面と同等の効果を奏する。

この発明の第９の局面は次のように規定される。即ち、
第６〜第８のいずれかの局面に規定の方法において、前記走行済みリンク特定ステップでは、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定する。
このように規定される第９の局面の発明によれば、第４の局面と同等の効果を奏する。

この発明の第１０の局面は次のように規定される。即ち、
第６〜第９のいずれかの局面に規定の方法において、前記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一である。
このように規定される第１０の局面の発明によれば、第５の局面と同等の効果を奏する。

更に、この発明の第１１の局面は次のように規定される。即ち、
経路を探索するためのコンピュータプログラムであって、コンピュータを、
第１のエリア内における所定条件を満たす対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを第１の地図データベースに格納する第１の格納手段と、
車両が走行した走行履歴を走行履歴データベースに蓄積する蓄積手段と、
前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定手段と、
前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定手段と、
前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新手段と、
前記更新された第１の地図データベースを参照して、目的地までの経路であって、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する経路を探索する経路探索手段、
として機能させる、コンピュータプログラム。
このように規定される第１１の局面の発明によれば、第１の局面と同等の効果を奏する。

この発明の第１２の局面は次のように規定される。即ち、
第１１の局面に規定のコンピュータプログラムにおいて、前記経路探索手段は、前記第１のエリア内の前記対象リンクを巡回する経路を探索する。
このように規定される第１２の局面の発明によれば、第２の局面と同等の効果を奏する。

この発明の第１３の局面は次のように規定される。即ち、
第１２の局面に規定のコンピュータプログラムにおいて、前記コンピュータを、更に、
第２のエリア内における所定条件を満たす対象リンクに関する情報を含む地図データを第２の地図データベースに格納する第２の格納手段と、
前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出手段、として機能させ、
前記経路探索手段は、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記経路を探索する。
このように規定される第１３の局面の発明によれば、第３の局面と同等の効果を奏する。

この発明の第１４の局面は次のように規定される。即ち、
第１１〜第１３のいずれかの局面に規定のコンピュータプログラムにおいて、前記走行済みリンク特定手段は、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定する。
このように規定される第１４の局面の発明によれば、第４の局面と同等の効果を奏する。

この発明の第１５の局面は次のように規定される。即ち、
第１１〜第１４のいずれかの局面に規定のコンピュータプログラムにおいて、前記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一である。

第１１〜第１５のいずれかの局面に規定されるコンピュータプログラムを記録する記録媒体が第１６の局面として規定される。

図１は、本発明の実施の形態の経路探索装置１の構成を示すブロック図である。 図２は、本発明の実施の形態の経路探索装置１の動作の一例を示すフローチャートである。 図３は、（Ａ）第１の地図データベース３内に格納される地図データを、（Ｂ）走行履歴データベース５内に格納される走行履歴データを、（Ｃ）更新後の第１の地図データベース３内に格納される地図データを説明するための模式図である。 図４は、本発明の他の実施の形態の経路探索装置２１の構成を示すブロック図である。 図５は、本発明の他の実施の形態の経路探索装置２１の動作の一例を示すフローチャートである。 図６は、（Ａ）第１の地図データベース３内に格納される地図データ、（Ｂ）走行履歴データベース５内に格納される走行履歴データ、（Ｃ）更新後の第１の地図データベース３内に格納される地図データ及び第２の地図データベース２３内に格納される地図データ、を説明するための模式図である。 図７は、本発明の実施例の移動体端末装置５１の構成を示すブロック図である。

この発明の実施の形態の経路探索装置を説明する。
図１に、経路探索装置１の概略構成を示す。適宜、図３に示す模式図を用いて、以下に説明する。
図１に示すように、この経路探索装置１は、第１の地図データベース３、走行履歴データベース５、走行済みリンク特定部７、重み付け設定部９、地図データベース更新部１１及び経路探索部１３を備えている。

第１の地図データベース３には、経路を探索するための地図データであって、第１のエリア内の対象リンクを含むリンクに関する情報を含む地図データが格納されている（図３（Ａ）参照）。当該第１の地図データベース３は、通常の地図データベースに上記基準等を適用して作成することができる。具体的には、通常の地図データベース内のリンクに上記重み付け値としてのコストを付与することにより作成される。図３（Ａ）において、リンクに付与されるコストを括弧内に示す。例えば、Ｌ_１１に付与されるコストは０である。この例において、後述の経路探索部の探索対象となる対象リンクは、コストが１未満（第１の閾値未満）のリンクとしており、当該リンクを太線で表している（Ｌ_１１〜Ｌ_２２）。また、上記対象リンク以外のリンクには高い値のコスト（例えば、コスト∞等）を付与することにより、経路探索の際に選択されるリンクとしての優先度を下げることができる。このような第１の地図データベースを用いれば、実質的に上記対象リンクが経路の対象として選択されることとなる。また、第１の地図データベース３内に格納される対象リンクに対して、デフォルト設定で「未走行」である旨のデータや、「走行回数０回」である旨のデータが入力されていても良い。

走行履歴データベース５には、車両が走行した走行履歴が蓄積される（図３（Ｂ）参照）。当該走行履歴データベース５には、例えば、車両のプローブ情報に基づき、該車両が走行した各リンクの履歴Ｒ_１〜Ｒ_１０が蓄積される。各リンクの履歴は、走行日時、走行速度、走行した車線等を含むこととしても良い。他の例として、各リンクの履歴は、車両に取り付けられた撮像装置（図示せず）で取得された走行画像（走行画像データ）と関連付けられていても良い。上記走行画像データは、時間的に連続する複数のフレーム画像から構成されていることが好ましい。ここで、車両に取り付けられる撮像装置の設置向きや角度は、走行画像中に信号機看板の文字表示や交通規制標識を撮像可能なように設定すれば、特に制限されない。例えば、進行方向を撮影するよう設置するか、あるいは、進行方向と逆方向を撮影可能なよう設置することが好ましい。さらには進行方向及び進行方向と逆方向の両方を撮影可能なように複数の撮像装置を設置しても良い。さらに他の例として、外部情報等として取得された走行時の天候等が関連付けられていても良い。各リンクの走行履歴Ｒ_１〜Ｒ_１０は、例えば、図３（Ｂ）の点線として表すことができる。

走行済みリンク特定部７は、上記走行履歴データベース５内に蓄積された走行履歴に基づいて、上記第１の地図データベース内の対象リンクのうち走行済みリンクを特定する。当該走行済みリンクの特定方法は、特に限定されないが、対象リンクの一部、例えば半分以上を走行したものを走行済みリンクとして特定することができる。他の例として、対象リンクの一方の端点から他の方の端点までを完走したものを上記走行済みリンクとして特定したり、対象リンクを完走していない場合であっても走行した部分について部分的に走行済みと特定することとしても良い。

重み付け設定部９は、走行済みリンク特定部７で特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する。当該設定の方法としては、例えば、現調時の走行状況に基づき、当該現調によって取得される画像が利用可能と判断される場合には、再度の走行を要しないためコスト１を設定する。一方、現調時の走行状況に基づき、取得された画像に所望の情報が映っていない、あるいは、所望の情報は映っているものの明瞭でない、等の可能性がある場合には、当該現調のみによって再走不要となることがないよう、例えば、１未満（０．１など）の値をコストとして設定する。当該設定されるコストは、走行状況の程度に応じて段階的に設定することができる。当該重み付け値を設定する際に参照される走行状況としては、特に限定されないが、走行画像、道路の車線数、天候、現調車両のプローブ情報、経過時間等が挙げられる。重み付け設定部９は、これらの走行状況の一を用いて重み付け値を設定しても良いし、二以上の走行状況を組み合わせて重み付け値を設定することにしても良い。二以上の走行状況を用いる際には、夫々の走行状況に基づき得られた重み付け値を加算して総合的な重み付け値を設定しても良く、また走行状況の重要度を反映させるべく、夫々の走行状況に基づいて得られた重み付け値に適宜係数を乗じて総合的な重み付け値を設定しても良い。上記した走行状況の詳細を以下に示す。

（走行画像）
例えば、現調車両の前後に大型車両等が存在している場合や、夜間や曇天など周囲が薄暗い場合、逆光などで光が画像に映りこんでしまう場合には、取得された画像内に現調の目的とする標識や交差点名が明りょうに映り込む可能性が低い。そこで、画像内の変化を指標として、取得された画像内に変化が見られない場合や変化が小さい場合には、利用可能な画像が取得できている可能性が低いとすることができる。具体的には、現調の際に取得された走行画像を画像処理して、所定条件を充足している場合には、当該画像は、撮像情報の観点からは、利用可能な画像であるものとしてコスト１を設定することができる。一方、所定条件を充足していない場合には、当該画像を利用可能な画像である可能性が低いものとし、例えば、１未満（０．１など）の値をコストとして設定することができる。当該コストは、明度や輝度の度合いに応じて、段階的に増減させることにしても良い。この点については、本出願人による特願２０１３−２５４０５８号明細書及び図面を参照されたい。
上記利用可能な画像であるか否かの判断は、走行画像全体として行っても良く、また、その一部について行っても良い。例えば、走行画像内において現調の対象が映り込む領域について画像処理し、その結果が上記所定の条件を満たせば利用可能な画像であると判断することができる。具体的には、現調の対象が交差点名称である場合、交差点看板は走行画像内の上側領域に映り込み、現調の対象が交通規制である場合、道路標識は走行画像内の左側領域に移り込む可能性が高い。このような場合、現調対象に対応する領域の画像処理結果に基づき、当該画像が利用可能であるか判断する。現調対象に対応する領域の画像が鮮明であれば、所望の情報を得るに足るからである。

（道路の車線数）
走行現調を行って走行済みとされた道路であっても、当該道路の車線数によっては、利用可能な画像を取得する観点から必ずしも適切な車線を走行しているとは限らない。車線数の多い道路、すなわち、幅員の大きい道路の場合、走行する車線によっては、道路標識や交差点名等所望の情報が画像内に収まらない可能性がある。そこで、現調の際、車線数属性等に適した車線を走行した場合にはコスト１を、それ以外の場合には適宜１未満のコストを設定することができる。

（天候）
雨天や曇天等の天候では、現調を行っても道路標識や交差点名等の情報が鮮明に撮像された画像を取得することは困難である。そこで、走行現調時の天候に基づいて、晴天等鮮明な画像を取得可能な場合にはコスト１を設定し、それ以外の場合には適宜１未満のコストを設定することができる。当該コストは、車外の明度等に応じて段階的に設定しても良い。このような天候情報は、外部から取得しても良いし、車両に備えられた雨天検知器や日照計等から得られる情報に基づいて判断されても良い。

（車両のプローブ情報）
例えば、現調車両の車両速度が速い場合、取得される画像が乱れてブレが生じる可能性がある。また、走行時刻が夕方、夜間、早朝の場合には、辺りがまだ薄暗く、又は真っ暗で良好な画像を取得できる可能性が低い。そのため、所定閾値以上（例えば、６０ｋｍ／ｈ以上）の車両速度で走行した場合や、走行時刻が所定範囲（１８：００〜６：００の間）にある場合には、１未満の値をコストとして設定することができる。一方、車両速度が所定閾値未満である場合や、走行時刻が所定範囲外である場合にはコスト１を設定することができる。当該コストは、走行時の速度や時刻に基づいて、段階的に増減させることにしても良い。
また、他の例として、交差点で停止した車両の車載ビデオカメラで、前方の信号機看板を撮影する場合、交差点の幅が広いと信号機看板までの距離が大きく該信号機看板の文字情報が不鮮明となる場合がある。このような場合、交差点を右左折する時に撮影しても、やはり交差点中心から信号機までの距離が長いため信号機看板の文字情報を利用可能な程度に鮮明に取得できない可能性もある。このような交差点においては、車両が信号機に十分近づけるよう交差点を直進走行すれば、前方の信号機看板の文字情報を鮮明に撮影できる可能性が高い。そこで、交差点幅が広い場合、すなわち、前方信号機までの距離が大きい場合には、車両の走行履歴を参照して直進走行した場合にはコスト１を、それ以外の場合には適宜１未満のコストを設定することができる。この点については、本出願人による特願２０１３−２４８１６０号明細書及び図面を参照されたい。また、車両の後方を撮像することによって、信号機看板の文字情報を撮像可能な場合にも、適宜コストを設定しても良い。

（経過時間）
例えば、走行済みリンクの前回現調時から長期間経過している場合には、経年変化により道路標識や交差点名等が変更されている可能性がある。そのため、前回現調時から所定期間経過している場合、前回の現調以前に付与された重み付け値をキャンセルするよう重み付け値を設定することができる。例えば、負の値（−１など）をコストとして設定するようにしても良い。
一方、今回の現調が前回現調時から所定期間内である場合には、特に重み付け値を付与する必要はない。上記のように、前回現調時から所定期間を経過しているときコスト−１とした場合には、コスト０とすれば良い。

地図データベース更新部１１は、上記第１の地図データベース内の上記特定された走行済みリンクに付与された重み付け値に、重み付け設定部９で設定された重み付け値を反映させることにより、第１の地図データベースを更新する（図３（Ｃ）参照）。当該重み付け値を反映させる方法としては、既に付与されている重み付け値に、重み付け設定部９で設定された重み付け値を加算等することができる。他の例としては、重み付け設定部９で設定された重み付け値と、第１の地図データベース３内の対応する対象リンクに関連付けられた重み付け値とを比較し、設定された重み付け値の方が大きい場合、既に対象リンクに関連付けられている走行画像を、当該設定された重み付け値に関連付けられた走行画像に置き換えることにより、地図データベースの更新を行っても良い。

経路探索部１３は、上記第１の地図データベース３を参照して、目的地までの経路であって、対象リンクに付与されたコストが１未満（第１の閾値未満）である対象リンクを含む経路を探索する。当該探索の方法として、特に、付与されたコストが低い対象リンクを優先的に走行するような経路を探索することができる。経路探索部１３は、第１の地図データベース３内の要再走リンクを巡回すべく、巡回経路を探索することにしても良い。当該探索の方法としては、例えば、上記要再走リンクを一筆書きの要領で走行可能な経路を探索することとすることができる。なお、当該巡回経路は、もちろん要再走リンク以外の対象リンク、対象リンク以外のリンクを含んでいても良い。経路探索部１３は、例えば、図３（Ｃ）中、点線で示すような巡回経路を探索する。

図２を用いて、図１に示す経路探索装置１の動作の一例を説明する。
まず、ステップ１では、図示しない走行履歴取得部は、車両の走行履歴Ｒ_１〜Ｒ_１０を取得し、該走行に際して取得された走行状況と関連付けて走行履歴データベース５に蓄積する。当該蓄積された走行履歴Ｒ_１〜Ｒ_１０の一例を図３（Ｂ）に示す。
ステップ３では、走行済みリンク特定部７は、上記第１の地図データベース３を参照して、ステップ１で取得された走行履歴Ｒ_ｎに対応する対象リンクＬ_ｍを抽出する。例えば、走行履歴Ｒ_１に対応する対象リンクとして対象リンクＬ_１１が抽出される。
ステップ５では、走行済みリンク特定部７は、ステップ１で取得された走行履歴Ｒ_ｎが、ステップ３の対象リンクＬ_ｍの両端点間を完走しているか否か判定する。ステップ５においてＹｅｓのときステップ７へ進む。例えば、上記抽出された走行履歴Ｒ_１は、対象リンクＬ_１１の一方の端点から他方の端点まで走行しているので、ステップ７へ進む。一方、走行履歴が、対応する対象リンクの両端点間を完走していない場合には、ステップ１３へ進む。

ステップ７では、走行済みリンク特定部７は、上記ステップ３で抽出された対象リンクＬ_ｍを走行済みリンクと特定する。
ステップ９では、重み付け設定部９は、ステップ１の走行履歴Ｒ_ｎに関連付けられた走行状況に基づいて、コストを算出する。例えば、走行履歴に関連付けられた連続する走行画像を比較し、輝度変化量に応じてコストを算出することができる。例えば、輝度変化量が所定閾値以上である場合にコスト１とし、それ以下の場合にコスト０．１とすることができる。
ステップ１１では、地図データベース更新部１１は、ステップ９で算出されたコストを、第１の地図データベース３内におけるステップ５の対象リンクＬ_ｍに付与されているコストに加算することにより第１の地図データベースを更新する。

当該走行履歴Ｒ_ｎに続く走行履歴Ｒ_ｎ＋１について、ステップ３〜ステップ９を実行する（ステップ１３、１５）。
ステップ１７では、経路探索部１３は、ステップ１１を実行することにより更新された第１の地図データベース３を参照して、巡回経路を探索する。すなわち、更新された第１の地図データベース３において、付与されているコストが１未満である対象リンクＬ_１２、Ｌ_１３、Ｌ_１４、Ｌ_１５、Ｌ_１８、Ｌ_１９、Ｌ_２２を巡回すべく、例えば、図３（Ｃ）中、点線で示すような巡回経路を探索する。この例のように、当該巡回経路を走行後、さらに再走を要するリンクが存在する場合には、該リンクを走行すべく新たに巡回経路を探索することとしても良いし、後述の経路探索装置２１にて行われるように隣接エリアの対象リンクと併せて巡回できるよう経路探索することとしても良い。

図４に、他の実施の形態の経路探索装置２１を示す。図４において、図１と同一の要素には同一の符号を付して、その説明を部分的に省略する。
図４に示すのは、所定エリア内における、第１の閾値未満の対象リンク、すなわち、要再走リンクが少ないとき、該エリア内の要再走リンクと、該エリアに隣接するエリアの対象リンクとを併せて巡回経路を探索することが可能な経路探索装置２１である。すなわち、当該装置２１は、図１に示す装置１において、第２の地図データベース２３及び割合算出部２５を更に備え、経路探索部１３に代えて巡回経路探索部２７を備えている。

第２の地図データベース２３には、巡回経路を探索するための地図データであって、第１のエリアに隣接する第２のエリア内の対象リンクに関する情報を含む地図データが格納されている。上記第２のエリアは、上記第１のエリアに隣接していれば良く、両エリア内のリンクが直接接続していることは要せず、また、両エリア内のリンクが重複していても良い。当該第２の地図データベース２３は、上記第１の地図データベース３と同様の方法によって更新されているものであっても良い。
割合算出部２５は、上記更新された第１の地図データベース３を参照して、上記第１のエリア内の全対象リンクに対する要再走リンク以外の対象リンクの割合を算出する。当該算出の方法として、例えば、上記第１のエリア内の全対象リンクのリンク数に対する上記要再走リンク以外のリンクのリンク数の割合を算出することができる。また、他の例としては、上記第１のエリア内の全対象リンクの総距離に対する上記要再走リンク以外のリンクの総距離の割合を算出することとしても良い。

巡回経路探索部２７は、上記割合算出部２５で算出された割合が所定閾値以上であるとき、上記更新された第１の地図データベース３及び第２の地図データベース２３を参照して、巡回経路を探索する。当該探索の方法は、特に限定されず、上記経路探索部１３と同様にして行うことができる。特には、当該巡回経路探索部２７は、上記要再走リンクの割合がより小さい第１の地図データベース３内の対象リンク（要再走の対象リンク）を優先的に巡回することにしても良い。上記所定閾値は、例えば、８０％以上とすることができる。
上記経路探索装置２１の構成要素の一部をサーバ装置で実行可能とする経路探索システムとしても良い。当該サーバ装置で実行可能な構成は、特に限定されないが、例えば、地図データベース更新部１１、割合算出部２５及び巡回経路探索部２７とすることができる。サーバ装置で一元管理することで、異なる車両の走行履歴に基づき、一括して地図データベースを更新することができ、効率的な巡回経路の探索を行うことができる。

図５を用いて、図４に示す経路探索装置２１の動作の一例を説明する。
ステップ２１〜３５は、ステップ１〜１５と同様であるため、説明を省略する。
ステップ３７では、割合算出部２５は、上記第１の地図データベース３内の全対象リンクの総距離を算出する。
続くステップ３９では、割合算出部２５は、上記第１の地図データベース３内の対象リンクのうち、付与されているコストが１以上である対象リンクの総距離を算出する。
ステップ４１では、割合算出部２５は、ステップ３７及び３９の算出結果に基づいて、全対象リンクに対するステップ３９の対象リンクの割合を算出する。当該算出の結果、ステップ３９の対象リンクの割合が８０％以上であるとき（ステップ４３：Ｙｅｓ）、ステップ４５へ進む。

ステップ４７では、巡回経路探索部２７は、上記更新された第１の地図データベース３及び上記第２の地図データベース２３を参照して、第１のエリア内のコスト１未満である対象リンク）及び第２のエリアのコスト１未満である対象リンクを巡回すべく巡回経路を探索する。すなわち、更新された第１の地図データベース３において、対象リンクＬ_１５、Ｌ_１９を巡回すべく、例えば、図６（Ｃ）中、点線で示すような巡回経路を探索する。
一方、ステップ４３においてＮｏの場合には、ステップ４７へ進む。
ステップ４７では、巡回経路探索部２７は、上記更新された第１の地図データベース３を参照して、第１のエリア内のコスト１未満である対象リンクを巡回すべく巡回経路を探索する。

図７に、実施例の移動体端末装置５１を示す。図７において、図１及び図４と同一の要素には同一の符号を付して、その説明を部分的に省略する。
図７に示すのは、図４に示す装置２１を備えた移動体端末装置５１である。この移動体端末装置５１は、制御部５１０、メモリ部５１１、入力部５１２、出力部５１３、インターフェース部５１４、端末位置特定部５１５、プローブ情報取得部５１６、第１の地図データベース３、第２の地図データベース２３、走行履歴データベース５、走行済みリンク特定部７、重み付け設定部９、割合算出部２５、地図データベース更新部１１及び巡回経路探索部２７を備えている。

制御部５１０はＣＰＵ、バッファメモリその他の装置を備えたコンピュータ装置であり、移動体端末装置５１を構成する他の要素を制御する。
メモリ部５１１にはコンピュータプログラムが保存され、このコンピュータプログラムはコンピュータ装置である制御部５１０に読み込まれて、これを機能させる。このコンピュータプログラムは、移動体端末装置の記憶装置としての内蔵ハードディスク又は内蔵メモリ、移動体端末装置に差し替え可能な記憶媒体としてのＳＤ（登録商標）メモリカード、メモリスティック、スマートメディア、コンパクトフラッシュ（登録商標）、ＤＶＤ等の汎用的な媒体へ保存できる。
入力部５１２は、例えば、ユーザの指令の入力に用いられる。具体的には、上記経路探索における目的地等の入力に用いられる。入力部５１２として、マウス、ライトペン又はディスプレイの表示内容と協働するタッチパネル等のポインティングデバイスやキーボード又はマイクロホン等の音声入力装置を用いることができる。

出力部５１３はディスプレイを含み、後述の端末位置特定部５１５で特定された端末装置の位置や、巡回経路探索部２７で探索された巡回経路、対象リンクや要再走リンクの表示等、その他の情報を表示する。この出力部５１３は音声発信部を含むこともできる。
インターフェース部５１４は移動体端末装置５１を無線ネットワーク等へ連結させる。
端末位置特定部５１５は、ＧＰＳ装置やジャイロ装置により端末装置の現在の位置情報を特定する。併せて、現在時刻を特定することもできる。
プローブ情報取得部５１６は、車両のプローブ情報を取得する。当該プローブ情報取得部５１６は、ネットワークを介して無線で連結された車両から送信されるプローブ情報を取得することとしても良いし、車両内のメモリへ一旦格納し、直接又は有線を介して得られるプローブ情報を取得することとしても良い。当該プローブ情報には、少なくとも座標情報、プローブカーを特定するＩＤ情報が含まれる。ＧＰＳ等の位置検出機能を有する車両であればこれらの情報を特定することができる。更に、時間情報、速度情報、方位情報、高度情報、アクセル開度、エンジン回転数、前後加速度、ヨーレイト、ストップランプ、ＡＢＳウォーニングランプ、燃料消費量、電力残存容量、舵角（ハンドルの回転角度情報）、シフトレバー情報等を備えていても良い。

以上、本発明の実施の形態及び実施例について説明してきたが、これらのうち、２つ以上の実施の形態（実施例）を組み合わせて実施しても構わない。あるいは、これらのうち、１つの実施の形態（実施例）を部分的に実施しても構わない。さらには、これらのうち、２つ以上の実施の形態（実施例）を部分的に組み合わせて実施しても構わない。

この発明は、上記発明の実施の形態及び実施例の説明に何ら限定されるものではない。特許請求の範囲の記載を逸脱せず、当業者が容易に想到できる範囲で種々の変形態様もこの発明に含まれる。

１ ２１ 経路探索装置
３ ２３ 地図データベース（地図ＤＢ）
５ 走行履歴データベース（走行履歴ＤＢ）
７ 走行済みリンク特定部
９ 重み付け設定部
１１ 地図データベース更新部（地図ＤＢ更新部）
１３ 経路探索部
２５ 割合算出部

Claims (13)

1. 所定条件を満たす対象リンクを車両により巡回するための巡回経路を探索する経路探索装置において、
   第１のエリア内における対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを格納する第１の地図データベースと、
   車両が走行した走行履歴を蓄積する走行履歴データベースと、
   前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定部と、
   前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定部と、
   前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新部と、
   前記更新された第１の地図データベースを参照して、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する前記巡回経路を探索する経路探索部と、
   を備える、経路探索装置。
2. 前記第１のエリアに隣接する第２のエリア内における前記対象リンクに関する情報を含む地図データを格納する第２の地図データベースと、
   前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出部と、を備え、
   前記経路探索部は、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記巡回経路を探索する、
   請求項１に記載の経路探索装置。
3. 前記走行済みリンク特定部は、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定する、
   請求項１又は２に記載の経路探索装置。
4. 前記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一である、
   請求項１〜３のいずれか一項に記載の経路探索装置。
5. 所定条件を満たす対象リンクを車両により巡回するための巡回経路を探索する経路探索方法において、
   第１のエリア内における対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを第１の地図データベースに格納する第１の格納ステップと、
   車両が走行した走行履歴を走行履歴データベースに蓄積する蓄積ステップと、
   走行済みリンク特定部が、前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定ステップと、
   重み付け設定部が、前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定ステップと、
   地図データベース更新部が、前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新ステップと、
   経路探索部が、前記更新された第１の地図データベースを参照して、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する前記巡回経路を探索する経路探索ステップと、
   を備える、経路探索方法。
6. 前記第１のエリアに隣接する第２のエリア内における所定条件を満たす対象リンクに関する情報を含む地図データを第２の地図データベースに格納する第２の格納ステップと、
   割合算出部が、前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出ステップと、を備え、
   前記経路探索ステップでは、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記巡回経路を探索する、
   請求項５に記載の経路探索方法。
7. 前記走行済みリンク特定ステップでは、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定する、
   請求項５又は６に記載の経路探索方法。
8. 前記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一である、
   請求項５〜７のいずれか一項に記載の経路探索方法。
9. 所定条件を満たす対象リンクを車両により巡回するための巡回経路を探索するためのコンピュータプログラムであって、コンピュータを、
   第１のエリア内における対象リンクであって、重み付け値が付与された対象リンクに関する情報を含む地図データを第１の地図データベースに格納する第１の格納手段と、
   車両が走行した走行履歴を走行履歴データベースに蓄積する蓄積手段と、
   前記走行履歴に基づいて、前記第１の地図データベース内の前記対象リンクのうち走行済みリンクを特定する走行済みリンク特定手段と、
   前記特定された走行済みリンクの走行状況に基づいて、該走行済みリンクに重み付け値を設定する重み付け設定手段と、
   前記第１の地図データベース内の前記特定された走行済みリンクに付与された重み付け値に、前記設定された重み付け値を反映させることにより、前記第１の地図データベースを更新する地図データベース更新手段と、
   前記更新された第１の地図データベースを参照して、前記対象リンクのうち前記付与された重み付け値が第１の閾値未満である対象リンクを走行する前記巡回経路を探索する経路探索手段、
   として機能させる、コンピュータプログラム。
10. 前記コンピュータを、更に、
    前記第１のエリアに隣接する第２のエリア内における所定条件を満たす対象リンクに関する情報を含む地図データを第２の地図データベースに格納する第２の格納手段と、
    前記第１のエリア内の前記対象リンクに対する前記付与された重み付け値が前記第１の閾値以上である対象リンクの割合を算出する割合算出手段、として機能させ、
    前記経路探索手段は、前記算出された割合が第２の閾値以上であるとき、前記更新された第１の地図データベース及び前記第２の地図データベースを参照して、前記巡回経路を探索する、
    請求項９に記載のコンピュータプログラム。
11. 前記走行済みリンク特定手段は、前記対象リンクの一方の端点から他方の端点までを完走した対象リンクを前記走行済みリンクとして特定する、
    請求項９又は１０に記載のコンピュータプログラム。
12. 前記走行状況は、走行画像、道路の車線数、天候、前記車両のプローブ情報、の少なくとも一である、
    請求項９〜１１のいずれか一項に記載のコンピュータプログラム。
13. 請求項９〜請求項１２のいずれかに記載のコンピュータプログラムを記録する記録媒体。

Images