(57)【要約】【課題】通過実績のない道路に対する通過可能性を精度良く予測する技術を提供する。【解決手段】道路区間ごとの通過可能性を複数の道路区間の少なくとも一部に対して含む通過可否情報を、複数の車両について記憶する記憶手段と、あらかじめ定められた順序関係にしたがって車Ａと車Ｂの通過可否情報を比較可能であるか否か判断する判断手段と、両車両の通過可否情報が比較可能である場合に、両車両の通過可否情報間で道路区間の通過可能性を推論する推論手段と、を備える。推論を複数回行って推論を広く伝搬しても良い。また、通過可否情報に差分が少ない場合は推論を行わないことも好ましい。また、通過可能性を信頼度ともに記憶し、推論によって予測される通過可能性の信頼度は小さくすることも好ましい。【選択図】図８
2010128692.tif 000002
【特許請求の範囲】
【請求項１】
車両から送信される道路区間ごとの通過可否の実績を表す通過実績報告に基づいて作成された通過可否情報を、複数の車両について記憶する記憶手段と、
第１および第２の車両の通過可否情報に含まれる各道路区間の通過可否を調べることで、両車両の通過可否情報が比較可能であるか否か判断する判断手段と、
第１および第２の車両の通過可否情報が比較可能である場合に、一方の車両について通過可能性が判明しており他方の車両について通過可能性が判明していない道路区間について、前記一方の車両の当該道路区間の通過可能性に基づいて、前記他方の車両の当該道路区間の通過可能性を推論する推論手段と、
を備える通過可能性データベース作成装置。
【請求項２】
前記判断手段は、
第１および第２の車両の通過可能性が判明している道路区間のうち、少なくとも１つの道路区間について両車両間で通過可能性が相違し、その他の道路区間で当該相違と矛盾する道路区間が存在しない場合に、第１および第２の車両の通過可否情報を比較可能であると判断し、
それ以外の場合に第１および第２の車両の通過可否情報を比較不可能であると判断する
ことを特徴とする請求項１に記載の通過可能性データベース作成装置。
【請求項３】
前記判断手段は、第１および第２の車両の通過可能性に矛盾する相違がある場合でも、矛盾する相違の割合が所定割合よりも少ないときには、当該矛盾する相違を無視して、第１および第２の車両の通過可否情報が比較可能であると判断する
ことを特徴とする請求項２に記載の通過可能性データベース作成装置。
【請求項４】
前記推論手段は、前記記憶手段に通過可否情報が記憶されている車両の中から任意の２車両の組み合わせ全てについて推論処理を実行する
ことを特徴とする請求項１〜３のいずれかに記載のデータベース作成装置。
【請求項５】
前記推論手段は、推論が適用できる間、全ての車両の組み合わせについて推論処理を繰り返し実行する
ことを特徴とする請求項４に記載の通過可能性データベース作成装置。
【請求項６】
前記推論手段は、前記２車両の間で通過可否情報が比較可能であっても、当該２車両の通過可否情報において、一方の車両が通過可能であって他方の車両が通過不可能である道路区間の割合が所定割合よりも少ない場合は、当該２車両の間での通過可能性の推論は行わない
ことを特徴とする請求項１〜５のいずれかに記載の通過可能性データベース作成装置。
【請求項７】
前記記憶手段には、各道路区間の通過可能性のそれぞれが信頼度とともに格納されており、
前記推論手段は、一方の車両についてのある道路区間の通過可能性から他方の車両の当該道路区間の通過可能性を推論する場合に、推論される前記他方の車両についての通過可能性の信頼度を、推論元の前記一方の車両の当該道路区間の通過可能性の信頼度よりも小さく設定する
ことを特徴とする請求項１〜６のいずれかに記載の通過可能性データベース作成装置。
【請求項８】
前記推論手段は、推論される通過可能性の信頼度を、推論元の通過可能性の信頼度に所定の減衰係数を乗算した値とする
ことを特徴とする請求項７に記載の通過可能性データベース作成装置。
【請求項９】
前記判断手段は、前記２つの車両の通過可否情報に含まれる各通過可能性の信頼度に基づいて、当該２車両の通過可否情報の比較について信頼度を算出し、
前記推論手段は、推論される通過可能性の信頼度を、前記比較の信頼度にも基づいて決定する
ことを特徴とする請求項８に記載の通過可能性データベース作成装置。
【請求項１０】
前記推論手段は、通過可能性の信頼度が所定値以下である場合には、当該通過可能性に基づいた推論は行わない
ことを特徴とする請求項７〜９のいずれかに記載の通過可能性データベース作成装置。
【請求項１１】
無線通信手段を有する経路探索装置を備えた車両と、
請求項１〜１０のいずれかに記載の通過可能性データベース作成装置と、から構成され、
前記経路探索装置は、前記無線通信手段によって通過可能性データベース作成装置から自車両に関する推論された通過可否情報を取得し、当該推論された通過可否情報に基づいて経路探索を行う
ことを特徴とする経路探索システム。
【請求項１２】
前記経路探索装置は、自車両が通過不可能であると推論されている道路区間の通過コストを大きくして、経路探索を行う
ことを特徴とする請求項１１に記載の経路探索システム。
【請求項１３】
無線通信手段を有する経路探索装置を備えた車両と、
請求項７〜１０のいずれかに記載の通過可能性データベース作成装置と、から構成され、
前記経路探索装置が、前記無線通信手段によって通過可能性データベース作成装置から自車両に関する推論された通過可否情報を取得し、当該推論された通過可否情報に基づいて経路探索を行う経路探索システムであって、
信頼度の高い通過可否情報を優先的に利用して経路探索を行う
ことを特徴とする経路探索システム。
【請求項１４】
複数の車両それぞれについて記憶されている、各車両から送信される道路区間ごとの通過可否の実績を表す通過実績報告に基づいて作成された通過可否情報に基づいて、通過可能性が判明していない道路区間の通過可能性を予測する通過可能性予測方法であって、
第１および第２の車両の通過可否情報に含まれる各道路区間の通過可否を調べることで、両車両の通過可否情報が比較可能であるか否かを判断する判断工程と、
第１および第２の車両の通過可否情報が比較可能である場合に、一方の車両について通過可能性が判明しており、他方の車両ついて通過可能性が判明していない道路区間について、前記一方の車両の当該道路区間の通過可能性に基づいて、前記他方の車両の当該道路区間の通過可能性を推論する推論工程と、
を含む通過可能性予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両ごとの道路区間の通過可能性を予測する通過可能性データベース作成装置およびこれを利用する経路探索システムに関する。
【背景技術】
【０００２】
幅が狭い道路は、車によって通れない場合があるため、カーナビゲーション装置（経路案内装置）では案内しないことが多い。このような道路幅が狭い道路は細街路と呼ばれ、たとえば、３ｍ以上５．５ｍ未満の道路を細街路とみなすことが多い。また、交差点についても、図１１に示すように、いわゆる「すみ切り」の有無などにより曲がれる方向と曲がれない方向が存在する。このような道路や交差点を通過できるか否かは、車両の大きさといった要素だけでなく、運転者のスキルや慣れなどの要素も影響する。たとえば、その道路に慣れている地元の運転者は通過できる道も、不慣れな運転者は通過できないという状況が存在する。
【０００３】
このような細街路を対象とする経路案内では、その細街路を通過可能であるか否かを車両ごとに判断できる必要がある。このような細街路の経路案内を目的とした技術として、特許文献１，２を挙げることができる。
【０００４】
特許文献１は、小型車・普通車・大型車・特殊車などの種別、車の大きさ、車の重量などの車両に関する情報と、地図データに併せ持つ高さ制限・重量制限などの道路に関する情報とを利用して、車が通行できない細街路や、高さ制限や重量制限のある道路を避けて経路探索する。
【０００５】
特許文献２は、どの道路を実際に通過できたかという情報を、その車の大きさ（車幅、車高、全長）に関する情報とともに、サーバーで収集する。これにより、その車が通れる細街路を記憶しておくことができるとともに、通過実績のある車よりも小さい車両はその細街路を通れると判断して経路案内ができる。
【特許文献１】特開平１１−２５３５号公報
【特許文献２】特開２００６−２７５６４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のような従来技術の場合には、下記のような問題が生じていた。
【０００７】
特許文献１，２はいずれも、正常動作のためには、車の大きさ（車幅、車高、全長）の正しい情報を必要とする。ある車（当該車と呼ぶ）の大きさに関する情報が経路探索システムに与えられない場合には、特許文献１の手法は当該車に対しては全く機能しない。同様に、特許文献２の手法は、当該車に対して全く機能しないだけでなく、他車に対して当該車の実績値を活用することができない。さらに、誤設定などにより車の大きさとして誤った情報がシステムに与えられた場合、特許文献１の手法は当該車に対して誤った結果を提示する。同様に、特許文献２の手法は当該車に対して誤った結果を提示し、収集される実績値が誤るため、結果の精度が落ちる。
【０００８】
また、特許文献１，２はいずれも、車の大きさにのみ着目し、全長と車幅のバランス、回転半径、運転者の運転スキル、運転者の各道路に対する慣れなどの道路を通過できるか否かに影響するその他の要素を考慮していない。
【０００９】
本発明は上記実情に鑑みてなされたものであって、その目的は、道路の通過実績に基づいて、通過実績のない道路に対する通過可能性を精度良く予測できる技術を提供することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するために本発明では、以下の手段または処理によって通過実績のない道路に対する通過可能性の予測を行う。
【００１１】
本発明に係る通過可能性データベース作成装置は、各車両から送信される道路区間ごとの通過可能・通過不可能を表す通過実績報告から作成した通過可否情報を記憶しておき、異なる車両間で通過可否情報の比較（順序付け）が可能であるか判断し、比較が可能である場合には推論規則を適用することで、通過可能性が不明の道路に対する通過可能性を予測する。
【００１２】
より具体的に、本発明に係る通過可能性データベース作成装置は、
車両から送信される道路区間ごとの通過可否を表す通過実績報告に基づいて作成された通過可否情報を、複数の車両について記憶する記憶手段と、
第１および第２の車両の通過可否情報に含まれる各道路区間の通過可否を調べることで、両車両の通過可否情報が比較可能であるか否か判断する判断手段と、
第１および第２の車両の通過可否情報が比較可能である場合に、一方の車両について通過可能性が含まれており他方の車両について通過可能性が含まれていない道路区間について、前記一方の車両の当該道路区間の通過可能性に基づいて、前記他方の車両の当該道路区間の通過可能性を推論する推論手段と、
を備える。
【００１３】
このように、車両ごと道路区間ごとの通過可能性（通過実績）のみに基づいて推論が行えるので、車両の大きさなどの情報の入力が不要になる。また、通過可能性（通過実績）に基づいた推論であるため、車両の大きさだけでなく、運転者のスキルなどその他の要素も考慮されていることになり、より実情にあった推論が行える。
【００１４】
車両間での通過可否情報の比較とは、ある車両（車両Ａ）についての各道路区間の通過可能性の集合と、別の車両（車両Ｂ）についての各道路区間の通過可能性の集合との間で定義された所定の順序関係（二項関係）にしたがった比較を意味する。この順序関係は、車両Ａと車両Ｂの間での、道路の通過しやすさを表す順序関係とすることが好ましい。より具体的には、車両Ａ，Ｂ両方の通過可能性が判明している道路区間のうち、少なくとも１つの道路区間について両車両間で通過可能性が相違し、その他の道路でこの相違と矛盾する道路区間がない（たとえば、ある道路区間について車両Ａが通過可能で車両Ｂが通過不可能な場合、その他の道路区間について車両Ａが通過不可能であるにもかかわらず車両Ｂが通過可能ということがない）場合に、順序づけが可能であると定義できる。上記の場合には、これらの車両の通過可否情報を比較可能であり、一方の車両の方が他方の車両よりも道路の通過しやすさが高いと判断できる。２車両の通過可否情報に矛盾する情報が含まれることもあり得ることであり、このような場合は比較ができないと判断する。
【００１５】
本明細書において、道路区間は道路上の任意の２地点間の区間を意味する。したがって、道路区間は、ある交差点から別の交差点までの道路、ある交差点から別の交差点までの道路を分割したうちの１つ、交差点内の道路などが含まれる。交差点内の道路に関しては、その交差点にどの道路から進入しどの道路へ退出したか、すわなち、直線・左折・右折などを区別する。
【００１６】
本発明においては、記憶手段に通過可否情報が記憶されている車両の中から任意の２車両の組み合わせ全てについて推論処理を実行することが好ましい。こうすることで、推論の適用範囲を拡げることができる。
【００１７】
また、本発明において、通過可能性が推論された場合に、推論結果とあらかじめ格納されている通過可能性とを同一視して、さらに推論処理を繰り返し適用することが好ましい。つまり、推論を複数回繰り返し実行しても良い。この場合、それ以上推論が適用できなくなるまで繰り返し実行することが好適である。こうすることで、推論の適用範囲をより拡げることができる。
【００１８】
また、２車両の間で通過可否情報が比較可能であっても、当該２車両の通過可否情報の差分が少ない場合には、この２車両間での推論を行わないことが好ましい。つまり、この２車両間の通過可否情報において、一方の車両が通過可能であって他方の車両が通過不可能である道路区間の割合（両車両ともに通過可能性が判明している道路に対する割合）が、所定割合よりも少ない場合には、これら２車両の間での通過可能性の推論を行わないことが好ましい。
【００１９】
通過可否情報の差分が少ない場合、その僅かな違いに基づいて一方の車両の方が他方の車両よりも道路を通行しやすいと判断することになってしまう。このように判断の根拠となるデータが少ない場合は、比較判断が誤っている可能性が高まり、推論の精度が低下するおそれがある。そこで、通過可否情報の差分が少ない場合には推論を適用しないことで精度の低下を回避する。
【００２０】
本発明において、通過可否情報における各道路区間の通過可能性のそれぞれに信頼度を関連付けて管理することが好適である。このように通過可能性に信頼度を設けることで、通過可能性が推論された場合に、その推論をどの程度信頼して良いかという基準を得ることができる。
【００２１】
信頼度を設ける場合、上記の推論処理によって、通過可能性を推論する場合に、推論される通過可能性の信頼度は、推論の元となる通過可能性の信頼度よりも低くすることが好適である。より好適には、推論される通過可能性の信頼度は、推論元の通過可能性の信頼度に所定の減衰係数を乗算した値とすることが好適である。さらには、２車両間の通過可否情報の比較（どちらの車両の方が道路を通過しやすいかを示す比較結果）についての信頼度を算出し、この比較の信頼度にも基づいて、推論される通過可能性の信頼度を決定することが好適である。
【００２２】
また、推論の元となる通過可能性の信頼度が所定値以下である場合には、この通過可能性に基づく推論を行わないことが好適である。信頼度の低い通過可能性に基づくさらなる推論は精度の低下を招くので、このような精度の低下を防止することができる。
【００２３】
また、本発明の別の態様は、無線通信手段を有する経路探索装置を備えた車両と、上記の通過可能性データベース作成装置とから構成される経路探索システムである。この経路探索システムにおいては、経路探索装置は、無線通信手段によって通過可能性データベース作成装置から自車両に関する通過可否情報を取得し、この通過可否情報に基づいて経路探索を行うことが好適である。通過可能性データベース作成装置は、推論によって各車両が道路区間を通過可能であるかを予測するので、経路探索装置は初めて通る道路区間であってもその道路区間を通過可能であるか通過不可能であるかを判断できる。そして、このような通過可能性に基づいて経路探索を行うことで、より実情に適した経路案内が行える。
【００２４】
また、経路探索装置は、自車両が通過不可能であると推論されている道路区間の通過コストを大きくして経路探索を行うことが好適である。また、通過可能性が不明の道路区間についても、通過コストを大きくしても良い（この場合は、通過コストの上昇分は通過不可能な道路区間よりも小さくする）。このようにすることで、通過可能である道路区間を優先的に対象として経路探索が行え、車が通れる可能性の高い経路を案内することができる。
【００２５】
また、通過可能性データベース作成装置が道路区間の通過可能性を信頼度付きで管理している場合は、経路探索装置は、信頼度の高い通過可否情報を優先的に利用して経路探索を行うことが好ましい。すなわち、通過可能または通過不可能と予測されていても、その信頼度が低い場合には、実際に通過可能や通過不可能ではない確率が高まる。そこで、信頼度の高い情報、つまり、より確実に通過可能・通過不可能が判明している道路区間を対象として経路探索をする。これにより、誤った推論による影響を回避して、より適切な経路案内を実現できる。
【００２６】
なお、本発明は、上記手段の少なくとも一部を有する通過可能性データベース作成装置または経路探索システムとして捉えることができる。また、本発明は、上記処理の少なくとも一部を含む通過可能性データベース作成方法や経路探索方法、または、かかる方法を実現するためのプログラムとして捉えることもできる。上記手段および処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００２７】
本発明によれば、通過実績のない道路に対する通過可能性を精度良く予測することが可能となる。
【００２８】
また、精度の良い通過可能性の予測結果に基づいて経路探索を行えるので、より精度の良い経路探索を行うことができる。
【発明を実施するための最良の形態】
【００２９】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００３０】
（第１の実施形態）
〈システム概要〉
まず、本実施形態に係る細街路経路案内システムの概要を、図１を参照して説明する。本システムは、無線通信装置を搭載した複数の車両と、サーバー装置（通過可能性データベース作成装置）とから構成される。各車両は、実際に細街路を通行した際に、細街路を通れたか通れなかったかをサーバー装置に通知する。サーバー装置は複数の車両から通過実績（通過ログ）を取得した上で、これらの通過実績を利用して、各車両に関して、通過実績がなく通過できるか不明な細街路についての通過可能性を予測する。そして、予測結果を各車両に送信する。車両側では、自車両がまだ通行したことのない細街路に関しての通過可能性がサーバー装置から送信されることになる。車両側では経路探索を行う際にこの情報も利用することで、自車両が通行可能な道路を利用した適切な経路案内を実現できる。
【００３１】
現在一般に利用されている地図データは、図２に示すように、交差点を表す「ノード」と道路を表す「リンク」から構成されている。各ノードおよび各リンクは、識別子としてそれぞれノードＩＤとリンクＩＤを持つ。本実施形態に係る細街路経路案内システムでは、道路（リンク）の通過可能性だけでなく交差点（ノード）の右折・左折などの通過可能性も把握可能とする。そのために、通過可能性を判断する対象の道路区間としてリンクとノードの両方を含め、対象の道路区間を識別するための「通過ラベル」を次のように定め
る。
【００３２】
通過ラベル  ：＝
｛ノードＩＤ，通過元リンクＩＤ，通過先リンクＩＤ｝    ・・・ノードの場合
｛リンクＩＤ，通過元ノードＩＤ，通過先ノードＩＤ｝    ・・・リンクの場合
【００３３】
図２に示される例では、交差点間の道路（リンク）の通過ラベルは｛Ｌ１，Ｎ１，Ｎ２｝と表され、交差点（ノード）の通過ラベルは｛Ｎ２，Ｌ１，Ｌ２｝と表される。
【００３４】
なお、以下では、記載の簡略化のために、識別子である通過ラベルと、識別対象である道路区間とを同一視して記載する。たとえば、「通過ラベルによって特定される道路区間の通過可能性」の意味で「通過ラベルの通過可能性」と記載する。
【００３５】
各車両は識別子として車ＩＤを持つ。車ＩＤは、車載機を識別する車載機ＩＤで代用しても構わない。車が細街路を通行すると、車載機は下記の形式の通過実績報告をサーバーに送る。
【００３６】
通過実績報告  ：＝  ｛車ＩＤ，時刻，通過ラベル，通過可能フラグ｝
【００３７】
「時刻」は車が通過ラベルで表される移動を行った時刻である。通過可能フラグは、通過可能であった場合にはＴ（真）、通過不能であった場合にはＦ（偽）を取る真偽値である。
【００３８】
サーバー装置は種々の車から通過実績報告を収集する。したがって、サーバー装置には通過ラベルと車ＩＤを軸とした２次元の通過ログ表（通過可能性データベース）が作成される（図１参照）。通過ログ表の各行（通過ログという）は、通過ラベルと通過可能フラグ（ＴまたはＦの値を取る）の対からなる集合のべき集合である。ここで、通過ラベルの包含関係とＦ＜Ｔとする順序関係を定めると、通過ログ表は半順序集合と見なせる。このとき、通過ログ表は図３に示すような束（ｌａｔｔｉｃｅ）となる。
【００３９】
このように通過ログ表は半順序集合であるため、各車両の通過ログは順序付けができる場合がある。ここでの順序づけは、車両の細街路の通過しやすさを表すものである。したがって、順序づけが可能な２つの車の間では、推論を適用して通過ラベルの通過可能性を推論することができる。つまり、車両Ａ，Ｂのうち車両Ａの方がより細街路を通過しやすいと順序づけができる場合に、車両Ａが通過不可能な通過ラベルは車両Ｂも通過不可能であると推論可能であるし、車両Ｂが通過可能な通過ラベルであれば車両Ａも通過可能であると推論可能である。
【００４０】
このようにしてサーバー装置は各車両の通過可能性の予測をおこない、その結果を車両に送信する。車両側ではこの結果を利用して細街路の経路探索を行うことで、自車両が通行可能な道路のみを含む経路を探索することができるようになる。
【００４１】
〈システム構成〉
図４に本実施形態に係る細街路経路案内システムの機能構成を表す機能ブロック図を示す。本システムは、既に述べたように、車両に搭載された車載機１とサーバー装置２とから構成される。
【００４２】
≪車両の構成≫
車載機１は、通過実績判断部１１、通過実績報告送信部１２、通過可能性受信部１３、経路探索部１４、ＧＰＳ装置１５、地図データベース１６を含む。車載機１の各機能部は
、ＣＰＵが所定のプログラムを実行することで実現される。ただし、各機能部の一部または全部について専用のハードウェア装置によって実現しても良い。
【００４３】
通過実績判断部１１は、ＧＰＳ装置１５からの受信データや地図データベース１６などを参照して、リンクやノードなどの道路区間を実際に通過できたか、あるいは通過できなかったを判断する。なお、地図データベース１６は、高精度であることが好ましいが、通過可能性を判断する対象とする道路についての情報があれば十分であり、現在普及している地図データ程度の精度があればよい。
【００４４】
本実施形態では、たとえば、次のような基準に従って通過可能であるか通過不可能であるかを判断する。
【００４５】
通過可能  ：＝
通過元ノードから通過先ノードに一定時間以内に到達    ・・・リンクの場合
通過元リンクから通過先リンクに一定時間以内に到達    ・・・ノードの場合
通過不可能  ：＝
通過元ノードから通過先ノードに一定時間以内に到達しない  ・・・リンクの場合
通過元リンクから通過先リンクに一定時間以内に到達しないか、または、運転手が経路変更を選択                                                ・・・ノードの場合
【００４６】
通過不可能は、リンクの場合であれば、途中で後退するなどした場合が該当する。同様に、ノードの場合であれば、途中で後退したり、経路案内とは別の道を選択したりした場合が該当する。通過可能にも通過不可能にも該当しない場合は、通過実績報告を作成しない。
【００４７】
通過可能・不可能の判断方法には、上記以外にもたとえば、車載カメラやセンサーなどから外壁や電柱に擦ったなどの状況を取得して、その場合に通過不可能と判定する方法も考えられる。
【００４８】
通過実績報告送信部１２は、通過実績判断部１１によって判断された通過ラベル（道路区間）ごとの通過可能・通過不可能を示す通過実績報告を、サーバー装置２へ無線通信によって送信する。この送信のタイミングは、通過実績判断部１１が判断を下すごとや、一定量の通過実績が溜まったときや、定期的なタイミングなどに行うことができる。また、車両１とサーバー装置２との間の無線通信方式は、任意の通信方式を採用して構わない。
【００４９】
通過可能性受信部１３は、サーバー装置２によって推論処理によって予測された自車両の通過可能・通過不可能の情報（通過可能性情報）を、無線通信によって受信する。サーバー装置２は、車両からの情報取得要求に応じて予測結果を送信してもよく、定期的に車両に対して送信しても構わない。
【００５０】
経路探索部１４は、地図データベース１６に格納されるデーターに加えて、サーバー装置２から送られた通過可能性情報も参照して、経路探索を行う。この際、通過不可能であると推論されている道路区間については通過コストを大きくして経路探索することで、通過できない道路区間を含む経路を探索結果として提示しないようにできる。つまり、車が通過できる道路区間のみから構成される経路が探索結果となる。
【００５１】
≪サーバー装置の構成≫
サーバー装置２は、通過実績報告受信部２１、通過可能性データベース２２、通過可能性予測部２３、通過可能性送信部２６から構成される。サーバー装置２の各機能部は、ＣＰＵが所定のプログラムを実行することで実現される。ただし、各機能部の一部または全
部について専用のハードウェア装置によって実現しても良い。
【００５２】
通過可能性データベース２２は、車両ごと、通過ラベル（道路区間）ごとに、通過可能か通過不可能かを示す通過可能フラグを格納している。この通過可能性データベース２２における通過可能フラグは、次に示すＬｏｇＴｙｐｅという型を持ち、下記のいずれかの値を取る。
【００５３】
ＬｏｇＴｙｐｅ  ：＝  ＮＵＬＬ｜Ｔ｜Ｆ｜ＰＴ｜ＰＦ
【００５４】
ここで、Ｔ，Ｆは通過実績報告から確実に判断できる通過可能・通過不可能をそれぞれ表す。一方、ＰＴは推論により通過可能と判断されたことを示し、ＰＦは推論により通過不可能と判断されたことを示す。また、ＮＵＬＬは通過可能であるか通過不可能であるか不明である（情報がない）ことを示す。通過可能性データベース２２の各要素は、初期値としてはＮＵＬＬを持つ（図では「−」で表している）。
【００５５】
通過実績報告受信部２１は、各車両から送信される通過実績報告を受信する。通過実績報告を受信すると、通過可能性データベース２２中の該当する車ＩＤと通過ラベルの要素に、通過フラグの値（ＴまたはＦ）が書き込まれる。
【００５６】
通過可能性データベース２２における、ある車両についての全ての通過可能フラグの集合（データベースの一行に相当）が、本発明における通過可否情報に相当する。通過ログは、ある車両についての全道路区間の通過可能フラグの集合である。
【００５７】
通過可能性予測部２３は、あらかじめ定められたタイミング（一定時間ごと、一定の通過実績報告受信ごと、など）に、通過可能性の予測を行う。通過可能性予測部２３は、任意の２車両についてそれらの通過ログに順序付けが可能か（一方の車両の方が他方の車両よりも道路を通行しやすいか）を判断し、順序付けが可能である場合には通過可能性の推論を行う。この推論結果は、通過可能性データベース２２に書き込まれる。この推論処理によって推論された通過可能性は、上述したようにＰＴまたはＰＦで表される。
【００５８】
通過可能性送信部２６は、通過可能性データベース２２の内容を各車両に送信する。
【００５９】
〈通過可能性予測処理〉
以下、通過可能性予測部２３が実行する通過可能性の予測処理の内容について説明する。図５Ａは通過可能性予測処理の全体の流れを示すフローチャートであり、図５Ｂはこの処理を実現するための擬似プログラムコードである。
【００６０】
任意の２車両ｉ，ｊの組み合わせについて、以下の処理が実行される（Ｓ１，Ｓ２）。まず、比較判断部２４が、車両ｉと車両ｊの通過ログの間に順序付けが可能であるか判断する（Ｓ３，compareTo関数）。これらの車両間で順序付けが可能である場合（Ｓ４：Ｙ
ＥＳ）には、これらの車両の通過ログの間に推論処理を適用する（Ｓ５，propagate関数
）。通過可能性予測部２３は、以上の比較判断および推論処理を全ての車両の組み合わせについて実行する（Ｓ１，Ｓ２のループ）。
【００６１】
≪比較判断処理≫
次に、ステップＳ３における比較判断処理の詳細な処理内容を図６Ａに示すフローチャートを参照して説明する。また、図６Ｂにこの比較判断処理を実現するための擬似プログラムコードを示している。この比較判断処理では、両車両とも通過可能性が判明している通過ラベルに関して、矛盾する情報がない場合に順序付け（比較）可能であると判定する。
【００６２】
すなわち、車両ｉが通過可能であり車両ｊが通過不可能な通過ラベルが存在する場合（Ｓ３１：ＹＥＳ）に、それと矛盾する情報である、車両ｉが通過不可能であり車両ｊが通過可能な通過ラベルがない場合（Ｓ３２：ＮＯ）は、順序付けが可能である。この場合は、車両ｉの方が車両ｊよりも道路を通過しやすい（車両ｉ＞車両ｊと表す）という順序付けが可能である（Ｓ３５）。
【００６３】
一方、ある通過ラベルについては車両ｉが通過可能で車両ｊが通過不可能であり（Ｓ３１：ＹＥＳ）、他の通過ラベルについては車両ｉが通過不可能で車両ｊが通過可能である（Ｓ３２：ＹＥＳ）場合は、車両ｉ，ｊの間で順序付けが不可能と判断できる（Ｓ３６）。
【００６４】
また、車両ｉが通過不可能であり車両ｊが通過可能な通過ラベルが存在する場合（Ｓ３３：ＹＥＳ）に、それと矛盾する情報である、車両ｉが通過可能であり車両ｊが通過不可能な通過ラベルがない場合（Ｓ３４：ＮＯ）は、順序付けが可能である。この場合は、車両ｊの方が車両ｉよりも道路を通過しやすい（車両ｉ＜車両ｊと表す）という順序付けが可能である（Ｓ３７）。
【００６５】
一方、ある通過ラベルについては車両ｉが通過不可能で車両ｊが通過可能であり（Ｓ３３：ＹＥＳ）、他の通過ラベルについては車両ｉが通過可能で車両ｊが通過不可能である（Ｓ３４：ＹＥＳ）場合は、車両ｉ，ｊの間で順序付けが不可能と判断できる（Ｓ３６）。
【００６６】
また、車両ｉ，ｊの両方について通過可能性が判明している通過ラベルがない場合や、全ての通過ラベルについて車両ｉ，ｊで通過可能・不可能が同一であり相違がない場合（いずれの場合もＳ３１：ＮＯかつＳ３３：ＮＯとなる）は、車両ｉ，ｊとの間で順序付けが不可能であると判断する（Ｓ３６）。なお、車両ｉ，ｊの両方について通過可能性が判明しており通過ラベルが存在し、かつ、その通過可能フラグに相違がない場合は、車両ｉとｊの道路の通過しやすさは同じである（車両ｉ＝車両ｊ）と判断できる。ただし、本予測処理では通過しやすさの相違に着目しているため、このような場合も順序付け不可能として取り扱う。
【００６７】
≪推論処理≫
次に、ステップＳ５における推論処理の詳細な処理内容を図７Ａに示すフローチャートを参照して説明する。また、図７Ｂにこの推論処理を実現するための擬似プログラムコードを示している。
【００６８】
この推論処理では、推論を適用する２つの車両と、その２つの車両の間の順序関係が特定される（Ｓ５１）。ここでは、２つの車両を車両Ａ，車両Ｂとし、車両Ａ＞車両Ｂという順序付けができるとステップＳ３で判断されたとして説明する。
【００６９】
これら車両Ａ，Ｂの通過ログを対象に、全ての通過ラベルに対して以下に説明する推論の適用を行う。
【００７０】
まず、通過ラベルｊについて、車両Ａが通過不可能（Ｆ）であり、かつ、車両Ｂの通過可能性が不明（ＮＵＬＬ）であるか判断し（Ｓ５３）、この条件が満たされる場合（Ｓ５３：ＹＥＳ）は、車両Ｂが通過ラベルｊを通過不可能（ＰＦ）と推論する（Ｓ５４）。通過ラベルｊはより道路を通過しやすい車両Ａでも通過できないので、車両Ａよりも道路を通過しにくい車両Ｂは通過ラベルｊを通過できないと推論することができる。
【００７１】
また、同様に、通過ラベルｊについて、車両Ｂが通過可能（Ｔ）であり、かつ、車両Ａの通過可能性が不明（ＮＵＬＬ）であるか判断し（Ｓ５５）、この条件が満たされる場合（Ｓ５５：ＹＥＳ）は、車両Ａが通過ラベルｊを通過可能（ＰＴ）と推論する（Ｓ５６）。通過ラベルｊはより道路を通過しにくい車両Ｂでも通過できるので、車両Ｂよりも道路を通過しやすい車両Ａは通過ラベルｊを通過できると推論することができる。
【００７２】
以上の推論を全ての通過ラベルに適用する（Ｓ５２のループ）。
【００７３】
≪動作例≫
通過可能性の予測処理の具体的な例を図８を参照して説明する。図８Ａは比較判断処理を説明する図である。車Ａと車Ｂの通過ログをみると、両方の車両について通過可能性が判明している通過ラベルに関して、通過可能・不可能が相違する場合は、常に車Ａが通過可能であり、車Ｂが通過不可能となっている。したがって、車Ａの方が車Ｂよりも道路を通過しやすい（車Ａ＞車Ｂ）と順序付けできることが分かる。
【００７４】
図８Ｂは推論処理を説明する図である。推論８１は、道路を通過しやすい車Ａが通過不可能であれば、車Ｂも通過不可能であるという推論が適用されている。推論８２は、道路を通過しにくい車両Ｂが通過可能であれば、車Ａも通過可能であるという推論が適用されている。図８Ｂに示すように、推論によって得られた通過可能性は、ＰＴあるいはＰＦとして表される。
【００７５】
なお、車Ａが通過可能である場合には、その通過ラベルを車Ｂが通過可能であるとは推論できないので、この通過ラベルに対しては推論が適用されていない。また同様に、車Ｂが通過不可能である場合には、その通過ラベルを車Ａが通過不可能であるとは推論できないので、この通過ラベルに対しては推論が適用されていない。
【００７６】
〈実施形態の作用・効果〉
本実施形態における細街路経路案内システムは、車両側では、道路区間を実際に通過できたかできなかったかを表す通過実績を判断し、サーバー装置へ送信しているだけである。そして、サーバー装置は、送信された通過実績に基づいて各車両について通過可能性が不明な道路区間について、通過可能性の予測を行っている。
【００７７】
車両側では、実際に通過できたかできなかったかを判断するだけであり、車両の大きさに関する情報を利用していない。すなわち、車載機などに車両の大きさ等に関する情報が登録されていなくても適切に動作する。また、このような情報が不要であるため、誤った設定がされている場合の誤動作なども考慮する必要が無くなる。
【００７８】
さらに、実際に通過できたかという実績に基づいた推論を行っているため、車両の大きさ以外に、車の全長と車幅のバランス、回転半径、運転者の運転スキル、道路に対する慣れなど、通過可能性に影響を与える種々の要素を反映した判断を行える。このように、従来は無視されていた車と運転者の属性を加味した通過可能性の提示を行えるため、予測精度が向上する。さらに、予測精度が向上した通過可能性に基づいて経路探索を行えるため、より適切な経路案内を実行することができる。また、交差点の右左折などを区別して通過可能性を判断しているため、この点からもより適切な経路案内を実行することができる。
【００７９】
（第２の実施形態）
第１の実施形態における比較判断処理では、差分の少ない通過ログに対して敏感に反応しすぎるおそれがある。たとえば、２つの車両の通過ログが、図９に示すような状況を考える。この例では、ほとんどの通過ラベルで通過可能フラグが一致しており、１つの通過
ラベルでのみ通過可能フラグが相違している。第１の実施形態による通過可能性予測処理では、このような場合でも、両車両間での推論が実行される。しかしながら、少ない相違のみでは２車両間の順序付けの根拠が乏しく、実際には２車両間で順序付けができなかったり、或いは逆の順序付けをすべきであるということもあり得る。このように、僅かな相違のみに基づいて推論を適用すると精度が低下するおそれがある。
【００８０】
そこで、本実施形態では、第１の実施形態の条件に加えて、２車両の通過ログに差分が一定以上ある場合のみ、推論処理（Ｓ５，図７Ａ，７Ｂ）を実行する。ここで、２車両の通過ログの差分量を以下のように定義する。
【００８１】
【数１】
2010128692.tif 000003
ここで、ＣＡとＣＢは、車Ａと車Ｂがそれぞれ生成した通過ログに含まれる通過ラベル集合である。ＲＡ（ｅ）とＲＢ（ｅ）は通過ラベルｅに対する車Ａと車Ｂの通過可能フラグの値である。
【００８２】
ここでの通過ログの差分量は、２車両の両方で通過可能フラグが判明している通過ラベルのうち、２車両間で通過可能フラグが相違する通過ラベルの割合を表す。本実施形態では、このように定められる通過ログの差分量が所定割合を超える場合のみ、推論処理を適用する。
【００８３】
このようにすることで、２車両間の通過ログの差分が少ない場合に生じるおそれのある行きすぎた推論、およびその結果生じる精度の低下を防止することができる。
【００８４】
（第３の実施形態）
第１の実施形態における比較判断処理では、通過ログにおいて、一方の車両が通過可能であり他方の車両が通過不可能な通過ラベルがある場合に、その他の通過ラベルで一方の車両が通過不可能であり他方の車両が通過可能な場合は、これら２車両の通過ログに順序付けができないと判断している。したがって、これらの車両間では通過可能性の推論が実行されない。
【００８５】
ここで、たとえば図１０に示す通過ログのように、通過可能性が異なる通過ラベルのうち、ほぼ全てで車両Ａが通過可能（Ｔ）で車両Ｂが通過不可能（Ｆ）であるのに、ごく一部の通過ラベルについて車両Ａが通過不可能（Ｆ）で車両Ｂが通過可能（Ｔ）な場合を考える。この例の場合は、車両Ａの方が車両Ｂよりも道路を通過しやすい（車両Ａ＞車両Ｂ）であると合理的に判断することができる。しかしながら、第１の実施形態で説明した比較判断処理では、順序付けが不可能と判断され推論処理が行われないことになる。
【００８６】
そこで、本実施形態では、順序付けが可能であるか否かの判断を以下のように変更する。すなわち、通過可能フラグが相違する通過ラベルのうち所定割合以上の通過ラベルに対して、車両Ａが通過可能（Ｔ）であり車両Ｂが通過不可能な場合（Ｆ）に、車両Ａと車両
Ｂの通過ログが順序付け可能（車両Ａ＞車両Ｂ）であると判断する。
【００８７】
このように比較判断処理を変更することで、推論の精度をほとんど低下させずに、推論の適用範囲を拡げることが可能となる。
【００８８】
（第４の実施形態）
上記第１の実施形態では、通過可能性予測処理（図５Ａ）を所定のタイミングごとに１回ずつ実行している。本実施形態では、各実行タイミングで通過可能性予測処理を複数回繰り返して実行する。つまり、予測処理を１回行った後に、さらにこの推論結果に基づいて推論を適用する。２回目以降の予測処理では、通過可能性データベースには、実績値による通過可能（Ｔ）・通過不可能（Ｆ）以外に、推論による通過可能（ＰＴ）・通過不可能（ＰＦ）が格納されているが、予測処理においてはＰＴ，ＰＦをＴ，Ｆと同一視して予測を行う。
【００８９】
図５Ａに示すフローチャートを繰り返し実行する場合、あらかじめ定められた所定回数だけ繰り返し実行することとしても良いし、新しい推論が適用されなくなるまで繰り返し実行しても良い。
【００９０】
取得済みの通過ログが少ない場合は、一方の車両の通過ログが他方の車両の通過ログのサブセットとなる場合が少なく推論がほとんど適用できないことがある。本実施形態によれば、推論を複数回伝搬させることで推論の適用範囲を拡げることができ、より多くの通過可能性を推論することができる。よって、より適切な経路案内を実行できるようになる。
【００９１】
（第５の実施形態）
上記第４の実施形態では、推論を複数回伝搬させることで、推論の適用範囲を拡げることができる。ここで、推論を過剰に伝搬させると、推論の信頼度が低下する危険性がある。そのためには、
（要件１）信頼度が低下したと考えられる時点で伝搬を停止するか、
（要件２）経路探索の際に信頼度の高い情報を優先する
ことが好ましい。
【００９２】
そこで、本実施形態では各通過ラベルの通過可能性を表すデータ型であるＬｏｇＴｙｐｅを、次のように再定義する。
【００９３】
ＬｏｇＴｙｐｅ  ：＝  （ｆ，ｒ）
ｆ  ：＝  Ｔ｜Ｆ
ｒ  ：＝  0.0〜1.0の値を取る実数値
ただし、（）は値の組み合わせ、｜は値の選択を表す。ｆは通過可能フラグであり、ｒはその信頼度である。
【００９４】
サーバー装置２が車両１から通過実績報告を取得した場合は、通過可能性データベース２２には、通過可能フラグ（ＴまたはＦ）が信頼度ｒ＝１．０とともに格納される。
【００９５】
そして、本実施形態では、通過ラベルｅについて、車Ａの通過可能フラグから車Ｂの通過可能フラグを推論する際に、推論される通過可能フラグの信頼度ｒＢ，ｅを以下のように定める。
【００９６】
ｒＢ，ｅ  ＝  ｒＡ，ｅ×α
ここで、ｒＡ，ｅは車Ａの通過ラベルｅの通過可能フラグの信頼度を表し、αは０．０
〜１．０の値を取るあらかじめ定められた減衰係数である（たとえば、０．９）。
【００９７】
このようにすることで、推論された通過可能フラグの信頼度を下げることができる。そして、上記の（要件１）を満たすためには、信頼度ｒが所定の閾値Ｒ（０＜Ｒ＜１）よりも小さくなったら伝搬を停止させればよい。また、（要件２）を満たすためには、経路選択の際に高い信頼度ｒを持つＬｏｇＴｙｐｅの通過ラベルを優先的に使用すればよい。
【００９８】
上記の信頼度の設定方法は、単純に信頼度を所定の割合で減少させる方法であるが、さらに、比較判断の信頼度を考慮して通過可能フラグの信頼度を設定することも好ましい。つまり、推論される通過可能フラグの信頼度を以下のように定める。
【００９９】
【数２】
2010128692.tif 000004
ただし、ＣＡ，ＣＢは、車Ａと車Ｂがそれぞれの通過ログに含まれる通過可能性が判明している（通過可能フラグがＮＵＬＬ以外の）通過ラベルの集合である。
【０１００】
この右辺第１項は、車両Ａ，Ｂ間で共通する通過ラベルにおける信頼度の積の平均値である。したがって、比較判断に使用される通過可能フラグの信頼度を表すものであり、比較判断の信頼度と捉えることができる。右辺第１項と第２項の積が伝搬前の情報の信頼度であり、これに減衰係数αを掛けたものを伝搬後の信頼度としている。
【０１０１】
このような方法によって信頼度を設定することで、より正確な信頼度を設定することが可能である。
【０１０２】
（変形例）
なお、上記実施形態は本発明の一具体例を例示したものにすぎない。本発明の範囲は上記実施形態に限られるものではなく、その技術思想の範囲内で種々の変形が可能である。
【０１０３】
たとえば、上記の説明では細街路の経路案内を目的としたシステムの説明をしているが、車両によって通過可能・通過不可能が分かれるような道路であれば、細街路以外の道路を対象として経路探索や経路案内を行っても構わない。
【０１０４】
また、上記の説明では車両側で通過可能か不可能かの判断をしてサーバー装置に送信しているが、車両からは定期的に位置情報を時間情報ととともに送信し、各通過ラベルを通過可能であったか否かの判断をサーバー装置側で行っても構わない。
【０１０５】
また、上記の説明ではサーバー装置から車両に対して通過可能データベースの情報を送信し車両側で経路探索を実行しているが、車両からサーバー装置に対して経路探索の要求を送信し、サーバー装置が通過可能データベースを考慮して経路探索をした上で、探索結果を車両に通知しても構わない。
【０１０６】
また、上記の説明では任意の道路区間を表すために、リンクとノードの組み合わせによって通過ラベルを表す例を説明しているが、これは現在一般に利用されている地図データの形式に合わせているだけであり、その他のデータ構造の地図データを利用する場合には適宜通過ラベルのデータ表現を変えて構わない。
【０１０７】
また、上記実施形態では、車の大きさの要素のみで通過可能性を予測せずに、その他の
要素を考慮に入れるために、通過実績のみに基づいて通過可能性を予測している。しかし、本発明は、通過実績以外に車両の大きさや道路の幅などに関する情報の利用を排除するものではない。本発明においてはこれらの情報も組み合わせて利用して予測の精度を高めても構わない。
【図面の簡単な説明】
【０１０８】
【図１】本実施形態に係る細街路案内システムの概要を説明する図である。
【図２】通過ラベル（道路区間）のデータ表現を説明する図である。
【図３】通過ログの順序関係を説明する図である。
【図４】本実施形態に係る細街路案内システムの機能ブロックを示す図である。
【図５Ａ】通過可能性予測処理の全体の処理の流れを示すフローチャートである。
【図５Ｂ】通過可能性予測処理を実行するための擬似プログラムコードである。
【図６Ａ】比較判断処理の流れを示すフローチャートである。
【図６Ｂ】比較判断処理を実行するための擬似プログラムコードである。
【図７Ａ】推論処理の流れを示すフローチャートである。
【図７Ｂ】推論処理を実行するための擬似プログラムコードである。
【図８】比較判断処理および推論処理の具体例を説明する図である。
【図９】差分が少ない通過ログの例を示す図である（第２の実施形態）。
【図１０】一部に矛盾する相違を含む通過ログの例を示す図である（第３の実施形態）。
【図１１】すみ切りを説明する図である。
【符号の説明】
【０１０９】
１  車載機（経路探索装置）
１１  通過実績判断部
２  サーバー装置（通過可能性データベース作成装置）
２２  通過可能性データベース
２３  通過可能性予測部
２４  比較判断部
２５  通過可能性推論部
【図１】
2010128692.tif 000005
【図２】
2010128692.tif 000006
【図３】
2010128692.tif 000007
【図４】
2010128692.tif 000008
【図５Ａ】
2010128692.tif 000009
【図５Ｂ】
2010128692.tif 000010
【図６Ａ】
2010128692.tif 000011
【図６Ｂ】
2010128692.tif 000012
【図７Ａ】
2010128692.tif 000013
【図７Ｂ】
2010128692.tif 000014
【図８】
2010128692.tif 000015
【図９】
2010128692.tif 000016
【図１０】
2010128692.tif 000017
【図１１】
2010128692.tif 000018