(57)【特許請求の範囲】
【請求項１】
複数の車両に備えられた複数の車載装置と、情報処理装置とを備える車両検索システムであって、
前記車載装置は、
前記車両に関する車両情報を、前記情報処理装置へ送信する車両情報送信手段と、
前記車両情報に基づいて、予め定められた予測時間後まで、前記車両の挙動の時系列を繰り返し予測する車両挙動予測手段と、
前記情報処理装置から送信された、位置及び時間に関する検索条件を受信した場合に、前記車両挙動予測手段によって予測された前記車両の挙動の時系列に基づいて、前記検索条件を満たすか否かを表す情報を生成する検索情報生成手段と、
前記検索情報生成手段によって生成された前記検索条件を満たすか否かを表す情報を、前記情報処理装置へ送信する検索情報送信手段と、を備え、
前記情報処理装置は、
入力された前記検索条件と、前記複数の車載装置の各々から送信された前記車両情報とに基づいて、前記複数の車両の各々から、前記検索条件を満たす前記車両の候補を選択する車両選択手段と、
前記車両選択手段によって前記車両の候補として選択された前記車両の前記車載装置の各々に対し、前記検索条件を送信する検索条件送信手段と、
前記車載装置の各々から送信された前記検索条件を満たすか否かを表す情報に基づいて、前記検索条件を満たす車両を検索する車両検索手段と、を備える
車両検索システム。
【請求項２】
複数の車両に備えられた複数の車載装置と、情報処理装置とを備える車両検索システムであって、
前記車載装置は、
前記車両に関する車両情報を、前記情報処理装置へ送信する車両情報送信手段と、
前記車両情報に基づいて、予め定められた予測時間後まで、前記車両の挙動の時系列を繰り返し予測する車両挙動予測手段と、
前記情報処理装置から送信された、予測結果送信要求を受信した場合に、前記車両挙動予測手段によって予測された前記車両の挙動の時系列を、前記情報処理装置へ送信する車両挙動情報送信手段と、を備え、
前記情報処理装置は、
位置及び時間に関する入力された検索条件と、前記複数の車載装置の各々から送信された前記車両情報とに基づいて、前記複数の車両の各々から、前記検索条件を満たす前記車両の候補を選択する車両選択手段と、
前記車両選択手段によって前記車両の候補として選択された前記車両の前記車載装置の各々に対し、前記予測結果送信要求を送信する予測結果送信要求送信手段と、
前記車載装置の各々から送信された前記車両の挙動の時系列に基づいて、前記車載装置の各々について、前記検索条件を満たすか否かを表す情報を生成する検索情報生成手段と、
前記検索情報生成手段によって生成された前記検索条件を満たすか否かを表す情報に基づいて、前記検索条件を満たす車両を検索する車両検索手段と、を備える
車両検索システム。
【請求項３】
前記検索条件は、車両の走行位置と時間区間とを含む検索条件であり、
前記車両挙動予測手段は、前記車両情報に基づいて、前記検索条件に含まれる時間区間の上限として予め定められた予測時間後まで、前記車両の走行位置の時系列を繰り返し予測し、
前記検索情報生成手段は、前記車両挙動予測手段によって予測された前記車両の走行位置の時系列に基づいて、前記検索条件に含まれる前記時間区間内に、前記検索条件に含まれる前記走行位置を前記車両が走行するか否かを表す情報を算出する
請求項１又は請求項２に記載の車両検索システム。
【請求項４】
前記検索条件を満たすか否かを表す情報は、前記検索条件を満たす度合いを表す確信度である請求項１〜請求項３の何れか１項に記載の車両検索システム。
【請求項５】
前記検索された車両の各々に対し、
前記情報処理装置は、
前記検索条件を満たすか否かを表す情報に応じたタスクであって、前記車両に実行させるタスクを指示する指示情報を生成するタスク生成手段と、
前記タスク生成手段によって生成された前記指示情報を、前記車両の前記車載装置に対し送信するタスク送信手段と、を更に備え、
前記車載装置は、
前記情報処理装置から送信された前記指示情報に基づいて、前記タスクを実行するタスク処理手段を更に備える
請求項１〜請求項４の何れか１項に記載の車両検索システム。
【請求項６】
前記検索された車両の各々に対し、前記タスク生成手段は、前記検索条件を満たすか否かを表す情報に応じて、情報の提示の有無又は提示情報の種類を指示する前記指示情報を生成し、
前記タスク処理手段は、前記情報処理装置から送信された前記指示情報に基づいて、前記車両の乗員に対して情報を提示するタスクを実行する
請求項５に記載の車両検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両検索システムに係り、特に、検索条件を満たす車両を検索する車両検索システムに関する。
【背景技術】
【０００２】
従来より、データベースからある条件を満たすような車両を検索する検索技術が知られている。
例えば、過去の車両走行履歴データに対して検索を行う技術が知られている（特許文献１）。
【０００３】
また、カーナビの目的地および経路情報をサーバ側で受け取り、その情報に基づいて、カーナビに適切な広告を表示する技術が知られている（特許文献２）。
【０００４】
また、車両挙動、特に経路の予測モデルに関して従来技術が存在する（特許文献３、非特許文献１、及び非特許文献２）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−１６３６９０号公報
【特許文献２】特開２０１０−１０２６８５号公報
【特許文献３】特開２０１３−１２０５２６号公報
【非特許文献】
【０００６】
【非特許文献１】Brian D.Ziebart，Andrew L.Maas，Anind K.Dey，and J.Andrew Bagnell，“Navigate Like a Cabbie:Probabilistic Reasoning from Observed Context-Aware Behavior”，UbiComp'08 Proceedings of the 10th international conference on Ubiquitous computing
【非特許文献２】John Krumm，“A Markov Model for Driver Turn Prediction”，SAE 2008 World Congress
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ここで、「未来車両挙動の検索」は不確実性が絡む複雑な問題であるため、例えば上記特許文献１のような過去の移動体情報を扱う通常のデータベースシステムでは実現が難しい。例えば、「時刻Ｔまでの将来に、道路Ａを通過しそうな車を列挙せよ」という問い合わせに対して、通常のデータベースシステムを用いると、「カーナビに入力した目的地および経路」を、多数の車両のカーナビへの入力をリアルタイムで管理するようなデータベースに通信経由で格納し、それを検索する、ということになる。このようなアイデアは例えば上記特許文献２において見られる。このような技術は、ドライバがカーナビに目的地を入力している車両に対しては有効であるが、それ以外の車両の経路は不確実であるため、検索することができないという問題点がある。
【０００８】
一方、未来の車両挙動は「車両挙動の予測モデル」を用いることで予測することができる。車両の進行方向や経路を予測する予測モデルとして、たとえば上記非特許文献１、又は上記非特許文献２に記載のようなものがある。車両の挙動の予測をｙ＝ｆ（ｘ）と表すことにする。ただし、ｙは予測値であり、ｘは現在までの状況、ｆは予測モデルである。未来の車両挙動検索は簡単に言えば「ｙがある条件を満たす車両の列挙」というタスクであると言えるが、すべての車両に対してｆ（ｘ）を計算し、その結果を用いて条件に合致する車両を列挙するのでは計算負荷が大きくなってしまい、遅延もしくは計算リソースの増大という問題点を引き起こしてしまう。この問題点は、通常の予測モデルが「順方向」の予測にフォーカスしており、予測結果がある条件を満たす、という「逆方向」の予測の用途は想定されていないためである。通常のデータベース技術では索引（インデクス）を構築することで検索の速度を高速化するが、「未来車両挙動の検索」は極めて動的かつ不確実な対象であり、常に変化し続けるため、索引を構成することは現状では難しいと考えられる。
【０００９】
以上の計算リソース増大の問題を回避するために、上記特許文献３で示されているような車両側での分散処理が考えられる。しかしながら、上記特許文献３の方法では、車両が処理の依頼を受けてから、計算（予測）を開始するため、遅延が発生してしまう。また、上記特許文献３の方法では、遊休リソースを持つ車両に対して優先的に分散処理を依頼する考え方に基づいている。しかし車両挙動の予測について考えると、関係のない他車両に自車の予測を依頼することになってしまう。これは車両の目的地や経路の履歴を関係のない他車両に送信することを意味し、プライバシーの問題が発生し得る。これらの問題を解決するためには上記特許文献３とは異なるアプローチが必要になる。
【００１０】
本発明は、上記の事情に鑑みて成されたものであり、車両検索の遅延を抑制することができる車両検索システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために第１の発明に係る車両検索システムは、複数の車両に備えられた複数の車載装置と、情報処理装置とを備える車両検索システムであって、前記車載装置は、前記車両に関する車両情報を、前記情報処理装置へ送信する車両情報送信手段と、前記車両情報に基づいて、予め定められた予測時間後まで、前記車両の挙動の時系列を繰り返し予測する車両挙動予測手段と、前記情報処理装置から送信された、位置及び時間に関する検索条件を受信した場合に、前記車両挙動予測手段によって予測された前記車両の挙動の時系列に基づいて、前記検索条件を満たすか否かを表す情報を生成する検索情報生成手段と、前記検索情報生成手段によって生成された前記検索条件を満たすか否かを表す情報を、前記情報処理装置へ送信する検索情報送信手段と、を備え、前記情報処理装置は、入力された前記検索条件と、前記複数の車載装置の各々から送信された前記車両情報とに基づいて、前記複数の車両の各々から、前記検索条件を満たす前記車両の候補を選択する車両選択手段と、前記車両選択手段によって前記車両の候補として選択された前記車両の前記車載装置の各々に対し、前記検索条件を送信する検索条件送信手段と、前記車載装置の各々から送信された前記検索条件を満たすか否かを表す情報に基づいて、前記検索条件を満たす車両を検索する車両検索手段と、を備える。
【００１２】
第１の発明の車載装置によれば、車両情報送信手段によって、車両に関する車両情報を、情報処理装置へ送信する。そして、車両挙動予測手段によって、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測する。
【００１３】
そして、検索情報生成手段によって、情報処理装置から送信された、位置及び時間に関する検索条件を受信した場合に、車両挙動予測手段によって予測された車両の挙動の時系列に基づいて、検索条件を満たすか否かを表す情報を生成する。そして、検索情報送信手段によって、検索情報生成手段によって生成された検索条件を満たすか否かを表す情報を、情報処理装置へ送信する。
【００１４】
また、第１の発明の情報処理装置によれば、車両選択手段によって、入力された検索条件と、複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択する。
【００１５】
そして、検索条件送信手段によって、車両選択手段によって車両の候補として選択された車両の車載装置の各々に対し、検索条件を送信する。そして、車両検索手段によって、車載装置の各々から送信された検索条件を満たすか否かを表す情報に基づいて、検索条件を満たす車両を検索する。
【００１６】
このように、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測し、情報処理装置から送信された検索条件を受信した場合に、予測された車両の挙動の時系列に基づいて検索条件を満たすか否かを表す情報を生成し、生成された検索条件を満たすか否かを表す情報を情報処理装置へ送信し、情報処理装置は、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、検索条件を送信し、車載装置の各々から送信された検索条件を満たすか否かを表す情報に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる。
【００１７】
また、第２の発明に係る車両検索システムは、複数の車両に備えられた複数の車載装置と、情報処理装置とを備える車両検索システムであって、前記車載装置は、前記車両に関する車両情報を、前記情報処理装置へ送信する車両情報送信手段と、前記車両情報に基づいて、予め定められた予測時間後まで、前記車両の挙動の時系列を繰り返し予測する車両挙動予測手段と、前記情報処理装置から送信された、予測結果送信要求を受信した場合に、前記車両挙動予測手段によって予測された前記車両の挙動の時系列を、前記情報処理装置へ送信する車両挙動情報送信手段と、を備え、前記情報処理装置は、位置及び時間に関する入力された検索条件と、前記複数の車載装置の各々から送信された前記車両情報とに基づいて、前記複数の車両の各々から、前記検索条件を満たす前記車両の候補を選択する車両選択手段と、前記車両選択手段によって前記車両の候補として選択された前記車両の前記車載装置の各々に対し、前記予測結果送信要求を送信する予測結果送信要求送信手段と、前記車載装置の各々から送信された前記車両の挙動の時系列に基づいて、前記車載装置の各々について、前記検索条件を満たすか否かを表す情報を生成する検索情報生成手段と、前記検索情報生成手段によって生成された前記検索条件を満たすか否かを表す情報に基づいて、前記検索条件を満たす車両を検索する車両検索手段と、を備える
【００１８】
第２の発明の車載装置によれば、車両情報送信手段によって、車両に関する車両情報前記情報処理装置へ送信する。そして、車両挙動予測手段によって、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測する。
【００１９】
そして、車両挙動情報送信手段によって、情報処理装置から送信された、予測結果送信要求を受信した場合に、車両挙動予測手段によって予測された車両の挙動の時系列を、情報処理装置へ送信する。
【００２０】
また、第２の発明の情報処理装置によれば、車両選択手段によって、位置及び時間に関する入力された検索条件と、複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択する。そして、予測結果送信要求送信手段によって、車両選択手段によって車両の候補として選択された車両の車載装置の各々に対し、予測結果送信要求を送信する。
【００２１】
そして、検索情報生成手段によって、車載装置の各々から送信された車両の挙動の時系列に基づいて、車載装置の各々について、検索条件を満たすか否かを表す情報を生成する。そして、車両検索手段によって、検索情報生成手段によって生成された検索条件を満たすか否かを表す情報に基づいて、検索条件を満たす車両を検索する。
【００２２】
このように、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測し、情報処理装置から送信された予測結果送信要求を受信した場合に、予測された車両の挙動の時系列を情報処理装置へ送信し、情報処理装置は、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、予測結果送信要求を送信し、車載装置の各々から送信された車両の挙動の時系列に基づいて、車載装置の各々について検索条件を満たすか否かを表す情報を算出し、検索条件を満たすか否かを表す情報に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる。
【００２３】
本発明に係る前記検索条件は、車両の走行位置と時間区間とを含む検索条件であり、
前記車両挙動予測手段は、前記車両情報に基づいて、前記検索条件に含まれる時間区間の上限として予め定められた予測時間後まで、前記車両の走行位置の時系列を繰り返し予測し、前記検索情報生成手段は、前記車両挙動予測手段によって予測された前記車両の走行位置の時系列に基づいて、前記検索条件に含まれる前記時間区間内に、前記検索条件に含まれる前記走行位置を前記車両が走行するか否かを表す情報を算出するようにすることができる。
【００２４】
本発明に係る前記検索条件を満たすか否かを表す情報は、前記検索条件を満たす度合いを表す確信度であるようにすることができる。
【００２５】
本発明は、前記検索された車両の各々に対し、前記情報処理装置は、前記検索条件を満たすか否かを表す情報に応じたタスクであって、前記車両に実行させるタスクを指示する指示情報を生成するタスク生成手段と、前記タスク生成手段によって生成された前記指示情報を、前記車両の前記車載装置に対し送信するタスク送信手段と、を更に備え、前記車載装置は、前記情報処理装置から送信された前記指示情報に基づいて、前記タスクを実行するタスク処理手段を更に備えるようにすることができる。
【００２６】
本発明は、前記検索された車両の各々に対し、前記タスク生成手段は、前記検索条件を満たすか否かを表す情報に応じて、情報の提示の有無又は提示情報の種類を指示する前記指示情報を生成し、前記タスク処理手段は、前記情報処理装置から送信された前記指示情報に基づいて、前記車両の乗員に対して情報を提示するタスクを実行するようにすることができる。
【発明の効果】
【００２７】
以上説明したように、第１の発明によれば、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測し、情報処理装置から送信された検索条件を受信した場合に、予測された車両の挙動の時系列に基づいて検索条件を満たすか否かを表す情報を生成し、生成された検索条件を満たすか否かを表す情報を情報処理装置へ送信し、情報処理装置は、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、検索条件を送信し、車載装置の各々から送信された検索条件を満たすか否かを表す情報に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる、という効果が得られる。
【００２８】
また、第２の発明によれば、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の挙動の時系列を繰り返し予測し、情報処理装置から送信された予測結果送信要求を受信した場合に、予測された車両の挙動の時系列を情報処理装置へ送信し、情報処理装置は、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、予測結果送信要求を送信し、車載装置の各々から送信された車両の挙動の時系列に基づいて、車載装置の各々について検索条件を満たすか否かを表す情報を算出し、検索条件を満たすか否かを表す情報に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる、という効果が得られる。
【図面の簡単な説明】
【００２９】
【図１】本発明の第１の実施の形態に係る車両検索システムの構成を示すブロック図である。
【図２】車両の経路予測を説明するための説明図である。
【図３】地図データをメッシュによって離散化することを説明するための説明図である。
【図４】ハッシュテーブルＨを説明するための概念図である。
【図５】ハッシュテーブルＨの更新を説明するための概念図である。
【図６】補助的ハッシュテーブルＧを説明するための概念図である。
【図７】領域Ｑの設定を説明するための概念図である。
【図８】車両検索システムのサーバの動作例を説明するための説明図である。
【図９】本発明の実施の形態に係る車載装置における予測処理ルーチンの内容を示すフローチャートである。
【図１０】本発明の実施の形態に係る車載装置における車両挙動予測処理ルーチンの内容を示すフローチャートである。
【図１１】本発明の実施の形態に係るサーバにおけるデータ格納処理ルーチンの内容を示すフローチャートである。
【図１２】本発明の実施の形態に係るサーバにおける検索処理ルーチンの内容を示すフローチャートである。
【図１３】本発明の実施の形態に係るサーバにおける簡易予測処理ルーチンの内容を示すフローチャートである。
【図１４】本発明の実施の形態に係る車載装置における推論処理ルーチンの内容を示すフローチャートである。
【図１５】本発明の実施の形態に係る車載装置における確信度算出処理ルーチンの内容を示すフローチャートである。
【図１６】本発明の第２の実施の形態に係る車両検索システムの構成を示すブロック図である。
【発明を実施するための形態】
【００３０】
以下、図面を参照して、本発明の実施の形態について説明する。
【００３１】
［第１の実施の形態］
＜第１の実施の形態に係る車両検索システム２１０の構成＞
図１に示すように、本発明の第１の実施の形態に係る車両検索システム１０は、複数の車両に備えられた複数の車載装置１２と、複数の車載装置１２から送信された車両情報を受信して、検索条件を満たす車両を検索するサーバ１４とを備えている。複数の車載装置１２とサーバ１４とは、インターネットなどのネットワーク１６を介して接続されている。なお、サーバ１４は、情報処理装置の一例である。
【００３２】
本実施の形態では、ユーザは車両検索システム１０に対して、例えば「Ｔｑ分後までに道路セグメントＡを通過しそうな車両とその確信度」というような「将来の車両挙動に関する質問（クエリ）」を問い合わせる。そして、車両検索システム１０の車載装置１２及びサーバ１４は、クエリに対する検索結果を出力する。以下では、車両の挙動を条件付ける「Ｔｑ分後までに道路セグメントＡを通過しそうな車両」を、位置及び時間区間に関する検索条件として用いる場合を例に説明する。
【００３３】
［車載装置１２］
車載装置１２は、自車両の位置情報を逐次計測する位置計測部１２０と、自車両の速度を逐次検出する車両センサ１２４と、位置計測部１２０によって計測された自車両の位置情報、及び車両センサ１２４によって検出された自車両の速度に基づいて、自車両の挙動を予測するコンピュータ１２６とを備えている。車載装置１２は車両に搭載される。
【００３４】
位置計測部１２０は、例えば、ＧＰＳセンサを用いて構成され、自車両の現時刻ｔの位置情報（Ｘ，Ｙ）を計測する。位置情報は、現時刻ｔにおいて自車両が位置する緯度Ｘと経度Ｙとを含む。
【００３５】
コンピュータ１２６は、ＣＰＵと、ＲＡＭと、後述する各処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備え、機能的には次に示すように構成されている。コンピュータ１２６は、位置計測部１２０によって計測された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）と、車両センサ１２４によって検出された自車両の速度とを取得する情報取得部１２８と、情報取得部１２８によって取得された車両情報を車両ＩＤと共にサーバ１４へ逐次送信すると共に、サーバ１４との間でデータの送受信を行う通信部１３０と、情報取得部１２８によって取得された自車両の位置情報及び自車両の速度に基づいて、自車両の予測経路を予測する車両挙動予測部１３２と、サーバ１４から送信された検索条件を受信した場合に、検索条件を満たすか否かを表す情報を生成する推論部１３４と、サーバ１４から送信されたタスクの指示情報を受信した場合に、タスクを実行するタスク処理部１３６とを備えている。通信部１３０は、車両情報送信手段と、検索情報送信手段との一例である。また、推論部１３４は、検索情報生成手段の一例である。
【００３６】
情報取得部１２８は、位置計測部１２０によって計測された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）を、車両に関する車両情報として取得する。また、情報取得部１２８は、車両センサ１２４によって検出された現時刻ｔの自車両の速度を取得する。
【００３７】
通信部１３０は、情報取得部１２８によって取得された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）を、サーバ１４へ逐次送信する。また、通信部１３０は、サーバ１４から送信された、位置及び時間区間に関する検索条件を受信する。また、通信部１３０は、サーバ１４から送信された検索条件を受信した場合に、後述する推論部１３４によって生成された検索条件を満たすか否かを表す情報をサーバ１４へ送信する。また、通信部１３０は、サーバ１４から送信された、車両に実行させるタスクを指示する指示情報を受信する。
【００３８】
車両挙動予測部１３２は、情報取得部１２８によって取得された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）と、自車両の速度とに基づいて、予め定められた予測限界まで、自車両の予測経路を繰り返し予測する。なお、自車両の予測経路は、自車両の挙動の時系列の一例である。
車両挙動予測部１３２は、サーバ１４から検索条件を受信していない場合であっても、例えば数ミリ秒〜数秒〜数分おきに逐次的に予測を更新する。逐次的に車両の挙動の予測を更新することで、検索条件を受け取った後に予測を行う場合に比べて、高速なレスポンスをすることができ、遅延の問題を緩和することができる。また、逐次的に車両の経路の予測を行い、計算リソースに余裕がある場合に行うようにスケジューリングすることで負荷を平滑化することが可能になる。
【００３９】
本実施の形態では、Ｔ分後（例えば、１〜１０分程度）までに、自車両が走行する経路の予測を行う場合を例に説明する（以下、Ｔを予測限界と称する。）。なお、予測限界Ｔは予め定められており、検索条件に含まれる時間区間の上限に対応している。
【００４０】
図２に、自車両の経路を予測する経路予測モデルを説明するための図を示す。
図２に示されるように、時刻ｔにおいて、自車両の走行した経路の履歴（道路セグメントＩＤのリスト）が、ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎであったとする。このとき予め推定された条件付確率ｐ（ｒｔ｜ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎ）に基づいて、次の時刻の道路セグメントを予測することができる。条件付確率は、個人の走行履歴または全車両の走行履歴から統計的に学習することで得られる。条件付確率は現在道路セグメントＡを自車両が走行している場合に、道路セグメントＡと接続されている道路セグメントであって、次に自車両が走行する道路セグメントのうちのいずれが高い確率であるかを示すものであり、「右折よりも直進のほうが、確率が大きい」「二回連続の右折は発生する確率は低い」などをモデル化したものである。
また、カーナビに目的地が入力されている場合、カーナビの提示する経路を利用する可能性が高いことなどを反映することなども考えられる。
【００４１】
本実施の形態では、サンプリングによって経路の予測を行う場合を例に説明する。すなわち、車両挙動予測部１３２は、条件付確率ｐ（ｒｔ｜ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎ）に比例する確率で次に走行する道路セグメントを一つサンプリングする。経路の履歴をＲ＝｛ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎ｝と表し、履歴Ｒのときにサンプリングしてｒｔを得る操作をｒｔ←Ｓ（Ｒ）と表す。また、ｒｔの平均的な所要走行時間をＴ（ｒｔ）と表すことにすれば、以下の擬似コードで示されるような手続きで予測を行うことができる。なお、ｒｔの平均的な所要走行時間Ｔ（ｒｔ）は、自車両の速度の履歴や道路セグメントの制限速度などによって算出される。
【００４２】
［擬似コード］
（アルゴリズム／経路サンプリング）
入力：経路履歴Ｒ＝｛ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎ｝、予測限界Ｔ
出力：予測経路Ｒ’＝｛ｒｔ＋Ｋ，ｒｔ＋Ｋ−１，・・・，ｒｔ｝
Ｒ’←｛｝                //  空の配列
Ｔ０←０                  //  予測限界Ｔを超えたら終了する
ｗｈｉｌｅ  Ｔ０＜Ｔ
ｒ←Ｓ（Ｒ’∪Ｒ）    //  これまでの走行の履歴からサンプリング
Ｒ’←Ｒ’∪｛ｒ｝    //  予測経路に追加
Ｔ０←Ｔ０＋Ｔ（ｒ）    //  必要な走行時間Ｔ（ｒ）を加算する
ｅｎｄ  ｗｈｉｌｅ
ｒｅｔｕｒｎ  Ｒ’
［擬似コード終わり］
【００４３】
以上のアルゴリズムは予測限界Ｔ分後までの予測経路を一つサンプリングする。このアルゴリズムを十分な回数実行することにより、複数の予測経路を得る。予測経路のリストは近似的にＴ分後までの確率的な経路予測とみなすことができる。本実施の形態では、上記予測アルゴリズムをＪ回実行し、Ｊ個の予測経路を得る場合を例に説明する。
【００４４】
推論部１３４は、サーバ１４から送信された検索条件を受信した場合に、車両挙動予測部１３２によって予測された自車両の予測経路に基づいて、検索条件を満たすか否かを表す情報として、検索条件を満たす度合いを表す確信度を算出する。検索条件には、車両の走行位置と時間区間とが含まれている。
【００４５】
具体的には、推論部１３４は、自車両の予測経路をサーバ１４が必要とする形式に変換する。変換後の形式はサーバ１４の検索条件に依存するが、以下ではサーバ１４側で、「Ｔｑ分以内に道路セグメントＡを確信度Ｐ以上で通過する車両を列挙せよ」（ただし、Ｔｑ＜Ｔ；Ｔは車両の予測限界）というクエリである場合について説明する。
【００４６】
車両挙動予測部１３２によって予測された予測経路のリストを、以下のアルゴリズムを用いて加工することで「Ｔｑ分以内に道路セグメントＡを通過する確信度」を算出する。
【００４７】
［擬似コード］
［アルゴリズム／推論部１３４における道路セグメント通過の確信度の算出］
入力：予測経路のリストＬ＝｛Ｒ１，Ｒ２，・・・，ＲＫ｝，道路セグメントＡ，時間Ｔｑ
出力：Ｔｑ分以内に該当車両が道路セグメントＡを通過する確信度Ｐ
Ｐ<−０                                    //確信度
Ｋ<−ｌｅｎｇｔｈ（Ｌ）                    //予測経路の数
Ｆｏｒ  ｅａｃｈ（Ｒ ｉｎ Ｌ）：           //予測経路リストＬに含まれる
全ての経路Ｒに対するループ
Ｔｃ<−０                          //Ｔｃ＞Ｔｑになったらこの経路Ｒに
Ａは含まれていないとみなす
Ｆｏｒ  ｅａｃｈ（ｒ  ｉｎ  Ｒ）：  //経路Ｒに含まれる
道路セグメントｒに対するループ
ｉｆ（ｒ＝＝Ａ）：          //経路ＲにＡが含まれた場合
Ｐ<−Ｐ＋１／Ｋ      //確信度を増加させる
ｂｒｅａｋ  ｔｈｉｓ  ｉｎｎｅｒ  ｌｏｏｐ
//経路Ｒの処理は終わりなので
次の経路Ｒ’を考える
ｅｎｄ ｉｆ
Ｔｃ<−Ｔｃ＋Ｔ（ｒ）      //時間をｒの所要時間Ｔ（ｒ）分
だけ増加させる
ｉｆ（Ｔｃ＞Ｔｑ）:       //Ｔｑを超えたら終了
ｂｒｅａｋ  ｔｈｉｓ  ｉｎｎｅｒ  ｌｏｏｐ
ｅｎｄ  ｉｆ
ｅｎｄ  ｉｎｎｅｒ  ｆｏｒ ｌｏｏｐ
ｅｎｄ  ｏｕｔｅｒ  ｆｏｒ  ｌｏｏｐ
ｒｅｔｕｒｎ  Ｐ
［擬似コード終わり］
【００４８】
確信度の算出は、道路セグメントＡや時間Ｔｑに依存し、検索条件が受信されるまで不明なので、事前に計算しておくことができない。
【００４９】
なお、上記確信度の算出について、クエリが「Ｔｑ分以内に道路セグメントＡを確信度Ｐ以上で通過する車両を列挙せよ」である場合を例に説明したが、他のタイプのクエリについても、基本的に上述したのと同等の考え方のアルゴリズムで確信度を算出することができる。また、車両挙動の予測処理はどのタイプのクエリに対しても共通した処理であるため、クエリのタイプを増やすために別の種類の車両挙動予測処理を行う必要はない。これは、逐次的な車両挙動予測処理とオンデマンドの推論処理（確信度算出処理）とを分離したことによる。また、新たなタイプのクエリを実施する場合には、車両側に、新たな推論処理のプログラムを送信して実行することも考えられる。
【００５０】
また、車両の車載装置１２側で、遊休リソースがなかったため、本来は車両側で逐次的に更新されているはずの車両の経路の予測が古くなってしまっている場合も考えられるが、その場合はその旨をサーバ１４側に通知し、サーバ１４側ではそれを受けて、経路の予測及び推論をサーバ１４側で行うかを計算リソースなどとの兼ね合いから決定するようにすればよい。
【００５１】
タスク処理部１３６は、サーバ１４から送信されたタスクの指示情報に基づいて、タスクを実行する。本実施の形態では、タスク処理部１３６は、サーバ１４から送信された指示情報に基づいて、車両の乗員に対して情報を提示するタスクを実行する場合を例に説明する。例えば、タスク処理部１３６は、信号での停止時にカーナビゲーションシステムの表示部に広告を表示する。
【００５２】
［サーバ１４］
サーバ１４は、ＣＰＵ、後述する各処理ルーチンを実現するためのプログラム等を記憶したＲＯＭ、データを一時的に記憶するＲＡＭ、記憶手段としてのメモリ、ネットワークインタフェース等を含むサーバで構成されており、機能的には、受付部１４０、通信部１４２、データ格納部１４４、データベース１４５、簡易予測部１４６、車両検索部１４８、及びタスク生成部１５０を含んだ構成で表すことができる。通信部１４２は、検索条件送信手段及びタスク送信手段の一例であり、簡易予測部１４６は、車両選択手段の一例である。
【００５３】
受付部１４０は、サーバ１４に入力されたクエリを受け付ける。クエリは、例えば、「Ｔｑ分後までに道路セグメントＡを通過しそうな車両とその確信度」というような「将来の車両挙動に関する質問」である。クエリに含まれる検索条件は、上述したように、車両の走行位置と時間区間とが含まれている。上記では、「Ｔｑ分後までに道路セグメントＡを通過しそうな車両」という問い合わせについて考えたが、本実施の形態における検索条件は、以下のように車両位置の様々な時間・空間的な条件を考えることができる。
【００５４】
（１）道路セグメントＡをＴ１分以内に通過し、その後道路セグメントＢをＴ２分以内に通過する車両
（２）道路セグメントＡをＴ１分以内に通過し、その後道路セグメントＢをＴ２分以内に通過しない車両
（３）Ｔ１分以内に道路セグメントＡもしくは道路セグメントＢを通過する車両
（４）Ｔ１分以内に道路セグメントＡを右折する車両、など。
【００５５】
通信部１４２は、複数の車載装置１２の各々から送信された車両の位置情報（Ｘ，Ｙ）を受信する。また、通信部１４２は、後述する簡易予測部１４６によって車両の候補として選択された車両の車載装置１２の各々に対し、受付部１４０によって受け付けたクエリに含まれる検索条件を送信する。また、通信部１４２は、検索条件を受信した車載装置１２の各々から送信された確信度を受信する。また、通信部１４２は、後述するタスク生成部１５０によって生成された指示情報を、車両の車載装置１２に対し送信する。
【００５６】
データ格納部１４４は、通信部１４２によって受信された、複数の車載装置１２の各々から送信された車両の位置情報（Ｘ，Ｙ）と当該車両の車両ＩＤとの組み合わせをデータベース１４５へ格納する。
【００５７】
具体的には、データ格納部１４４は、通信部１４２によって受信された（車両ＩＤ，Ｘ（緯度），Ｙ（経度））を取得する。なお、本実施の形態では、図３に示されるように、地図上の緯度及び経度をメッシュに離散化し、離散化されたメッシュの各々に対してメッシュＩＤを付与する。なお、以下では、車両ＩＤをＶで表す。
【００５８】
データ格納部１４４は、通信部１４２によって受信された（車両ＩＤ，Ｘ（緯度），Ｙ（経度））を、メッシュＩＤをキーとするハッシュテーブルＨ（データの格納場所）に格納する。メッシュＩＤをｍとすると、Ｈ［ｍ］にはメッシュｍに含まれるすべての車両データが「車両ＩＤをキーとするハッシュテーブル」として格納される。すなわち、ハッシュテーブルＨの構造は、図４に示されるような二重のハッシュテーブルとして実現される。なお、ｍｎはメッシュＩＤを表し、Ｖｎは車両ＩＤを表し、（Ｘｎ，Ｙｎ）は緯度及び経度を表す。
【００５９】
また、通信部１４２によって受信された最新のデータのみをＨに格納する、という制約から、車両ＩＤ（Ｖ）の車両を格納する際に、図５に示されるように、Ｖの過去のデータをハッシュテーブルＨから消去する必要がある。そのために車両ＩＤが与えられたときに、どのメッシュＩＤにデータが格納されているかを特定する必要がある。そのため、図６に示されるように車両ＩＤ→メッシュＩＤの検索を可能にする補助的ハッシュテーブルＧを用意する。上記図４のハッシュテーブルでは、Ｖ１はｍ１に属していることがわかるが、ハッシュテーブルの性質上、逆引き（矢印と逆の方向）の検索は極めて非効率であるため、補助的ハッシュテーブルＧを用いて車両ＩＤからメッシュＩＤへの対応を効率的に行えるようにする。補助的ハッシュテーブルＧを用いることにより、上記図５に示されるように、Ｖ２がｍ１に属していることがわかるため、Ｈ［ｍ１］からＶ２のデータを消去することができる。
【００６０】
以上をまとめると、データの格納処理は以下の擬似コードに示されるようになる。
【００６１】
［擬似コード］
［アルゴリズム／データ格納］
入力：（車両ＩＤ，緯度，経度）  （以下（Ｖ，Ｘ，Ｙ）と表す。）
ｏｌｄＭｅｓｈＩＤ＜−Ｇ［ｖ］  //車両ＩＤ（Ｖ）のデータが現状
どのメッシュに含まれているかを特定
車両ＶのデータをＨ［ｏｌｄＭｅｓｈ］から取り除く       //図５
ｎｅｗＭｅｓｈＩＤ＜−Ｄｉｓｃｒｅｔｉｚｅ（Ｘ，Ｙ）//メッシュＩＤを計算
（図３）
Ｈ［ｎｅｗＭｅｓｈＩＤ］［Ｖ］＜−（Ｘ，Ｙ）      //メッシュｎｅｗＭｅｓｈＩＤ
を走行する、車両ＩＤＶの新し
いデータを格納
Ｇ［Ｖ］＜−ｎｅｗＭｅｓｈＩＤ                  //補助的ハッシュテーブルを更新
［擬似コード終わり］
【００６２】
データベース１４５には、車両の各々についての（車両ＩＤ，Ｘ（緯度），Ｙ（経度））が格納される。また、データベース１４５は、ハッシュテーブルＨ及び補助的ハッシュテーブルＧによって各データが格納されている。
【００６３】
簡易予測部１４６は、受付部１４０によって受け付けたクエリに含まれる検索条件と、データベース１４５に格納された複数の車両の位置情報（Ｘ，Ｙ）とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択する。
【００６４】
全ての車両の車載装置１２に対して「検索条件を満たす確信度を計算せよ」と指令を出すのは車両のリソースの無駄である。厳密な予測をせずとも、物理的な制約条件などを勘案した簡易的な予測を用いれば、より効率的な計算が可能になる。例えば「５分後の車両位置が地点Ａ付近である車両」を検索する場合、車両が時速１２０ｋｍ／ｈ以下であると仮定すれば、現時点で地点Ａから１０ｋｍ以内に存在する車両に対してのみ確信度を計算すれば十分である。
【００６５】
したがって、簡易予測部１４６に求められる要件は、検索条件に合致する可能性のある車両を、データベース１４５に格納された複数の車両の位置情報（Ｘ，Ｙ）の情報を用いて、高速に（リアルタイムで）抽出可能であること、となる。
【００６６】
具体的には、まず、簡易予測部１４６は、データベース１４５のハッシュテーブルＨを用いて、ある地理的な領域Ｑの内部（上述した「道路セグメントＡから１０ｋｍ以内に存在する車両」の例では、領域Ｑは道路セグメントＡを中心とする１０ｋｍの円、ということになる）を走行する車両ＩＤのリストアップをする。図７に領域Ｑとメッシュとの関係を説明するための図を示す。図７では、細かい網掛け部分が領域Ｑを表し、粗い網掛け部分が領域Ｑを含むメッシュ集合を表す。図７に示されるように、領域Ｑが与えられたとき、領域Ｑを含むような（なるべく少ない数の）メッシュ集合を取得したい。これは領域Ｑ内の一点を適当に選択し、それをメッシュＩＤに変換し、そのメッシュの周囲のメッシュを探索し、領域Ｑとの共通部分があればそれもメッシュ集合として加えていく、ということを繰り返すことで得ることができる。領域Ｑの検索を行う際には、領域Ｑと粗い網掛け部分に対応するメッシュ集合Ｍとについて検索すれば十分であるが、本実施の形態では、領域Ｑの車両を過不足なく検索するために、粗い網掛け部分から領域Ｑに含まれない位置に存在する車両を取り除く。
【００６７】
ひとたび領域Ｑに対応するメッシュ集合Ｍが得られれば、そのすべての要素メッシュｍに対してＨ［ｍ］を列挙し、Ｈ［ｍ］に含まれる車両それぞれが本当に領域Ｑに含まれているかをチェックすることで、領域Ｑの内部を走行する車両ＩＤのリストアップという目的が達成される。
【００６８】
以上をまとめると、データベースの検索は以下の擬似コードに示されるようになる。
【００６９】
［擬似コード］
［アルゴリズム／簡易的予測］
入力：領域Ｑ
出力：領域Ｑを走行している車両のリストＷ
Ｗ＜−｛｝
Ｍ＜−Ｑを含むメッシュ集合の取得
Ｆｏｒ  ｅａｃｈ（ｍ  ｉｎ  Ｍ）：
Ｆｏｒ  ｅａｃｈ（ｖ  ｉｎ  Ｈ［ｍ］）：
（Ｘ，Ｙ）＜−Ｈ［ｍ］［Ｖ］
ｉｆ（（Ｘ，Ｙ）ｉｓ  ｉｎｃｌｕｄｅｄ  ｉｎ  Ｑ）：
Ｗ＜−Ｗ∪｛Ｖ｝
ｅｎｄ  ｉｆ
ｅｎｄ  ｉｎｎｅｒ  ｆｏｒ  ｌｏｏｐ
Ｅｎｄ  ｏｕｔｅｒ  ｆｏｒ  ｌｏｏｐ
［擬似コードおわり］
【００７０】
車両検索部１４８は、車載装置１２の各々から送信された確信度に基づいて、検索条件を満たす車両を検索する。具体的には、車両検索部１４８は、通信部１４２によって受信された車両ＩＤと確信度との組み合わせを表す情報に基づいて、検索条件を満たす車両を検索する。例えば、検索条件が「Ｔｑ分後に道路セグメントＡを通過しそうな車両」である場合には、車両検索部１４８は、確信度が５０％以上の車両を、検索条件を満たす車両とする。また、検索クエリが、例えば「Ｔｑ分以内に道路セグメントＡを確信度Ｐ以上で通過する車両を列挙せよ」である場合には、車両検索部１４８は、確信度がＰ以上の車両を、検索条件を満たす車両とする。
【００７１】
通信部１４２、簡易予測部１４６、及び車両検索部１４８の処理について、図８に示されるような「Ｔｑ分後までに道路セグメントＡを通過しそうな車両とその確信度を列挙せよ」というクエリがサーバ１４に入力された場合に、サーバ１４はどのように結果を返すのかについて、具体的な手続きを説明する。
【００７２】
（１）まず、道路セグメントＡをＴｑ分後までに通過できるような車両が現時点で走行している領域は車両の物理的な速度を勘案することで決定することができる。これを領域Ｑとする。領域Ｑを入力として、簡易予測部１４６における領域クエリ処理を行うことで、現状領域Ｑを走行している車両がリストアップされる。
通信部１４２は、リストアップされたＱを走行する車両全てに対して、車載装置１２に「Ｔｑ分後までに道路セグメントＡを通過する確信度を通知せよ」というクエリを送信する。
【００７３】
（２）サーバ１４側ではすべての車両の確信度の計算結果が戻ってくれば、これを結果とするが、所定の時間内に結果が揃わない場合でも、戻ってきたもののみを用いて結果とする。また、場合によっては、結果のリストの中で確信度がある値以下のものを取り除くことで確信度の高い車両のリストを得ることができる。
【００７４】
タスク生成部１５０は、通信部１４２によって受信された車両ＩＤと確信度との組み合わせを表す情報に基づいて、確信度に応じたタスクであって、車両に実行させるタスクを指示する指示情報を生成する。本実施の形態では、タスク生成部１５０は、確信度に応じて、情報の提示の有無又は提示情報の種類を指示する指示情報を生成する場合を例に説明する。
【００７５】
上記図８（３）では、具体的なタスクの例として、広告を挙げている。ある道路セグメントを通過しそうな車両に、その通り沿いの店舗のセール情報などを通知することで、よりターゲットを絞った、適切な広告が可能になる。この例では、確信度Ｐに応じて広告の有無やタイプなどを決定している。この戦略は予め定義されたデータベースに応じて行えば良い。
【００７６】
＜車両検索システムの作用＞
次に、本発明の実施の形態に係る車両検索システム１０の動作について説明する。車載装置１２を搭載した車両の各々が走行しているときに、各車両の車載装置１２は図９に示す予測処理ルーチンを実行し、サーバ１４は、図１２に示す検索処理ルーチンを実行する。
【００７７】
まず、各車両の車載装置１２が実行する予測処理ルーチンについて説明する。車載装置１２は、位置計測部１２０によって自車両の現時刻ｔの位置情報（Ｘ，Ｙ）が計測され、車両センサ１２４によって現時刻ｔの自車両の速度が検出されているときに、図９に示す予測処理ルーチンを実行する。
【００７８】
＜予測処理ルーチン＞
まず、ステップＳ１００において、情報取得部１２８は、位置計測部１２０によって計測された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）を、車両情報として取得する。また、情報取得部１２８は、車両センサ１２４によって検出された現時刻ｔの自車両の速度を取得する。
【００７９】
ステップＳ１０２において、通信部１３０は、上記ステップＳ１００で取得された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）と車両ＩＤとを、サーバ１４へ送信する。
【００８０】
そして、ステップＳ１０４において、車両挙動予測部１３２は、上記ステップＳ１００で取得された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）と、自車両の速度とに基づいて、予め定められた予測時間後まで、自車両の予測経路を予測する。ステップＳ１０４は、図１０に示す車両挙動予測処理ルーチンによって実現される。
【００８１】
＜車両挙動予測処理ルーチン＞
ステップＳ２００において、上記ステップＳ１００で取得された自車両の位置情報（Ｘ，Ｙ）の時系列に基づいて、自車両が走行した経路の履歴Ｒを取得する。
【００８２】
ステップＳ２０１において、予測経路の数に関する変数ｊに１を代入し、初期化する。
【００８３】
ステップＳ２０２において、予測経路Ｒ’と時間変数Ｔ０とを初期化する。
【００８４】
ステップＳ２０４において、時間変数Ｔ０が予測限界Ｔよりも小さいか否かを判定する。時間変数Ｔ０が予測限界Ｔよりも小さい場合には、ステップＳ２０６へ進む。一方、時間変数Ｔ０が予測限界Ｔ以上の場合には、ステップＳ２１１へ移行する。
【００８５】
ステップＳ２０６において、上記ステップＳ２００で取得された経路の履歴Ｒと、前回までに本ステップＳ２０６で予測された経路Ｒ’と、予め推定された条件付確率ｐ（ｒｔ｜ｒｔ−１，ｒｔ−２，・・・，ｒｔ−Ｎ）とに基づいて、次時刻に自車両が走行すると予測される経路ｒをサンプリングする。
【００８６】
ステップＳ２０８において、上記ステップＳ２０６でサンプリングされた経路ｒを、予測経路Ｒ’に追加する。
【００８７】
ステップＳ２１０において、上記ステップＳ２０８で追加されたｒの平均的な所要走行時間Ｔ（ｒ）を、時間変数Ｔ０に加算する。
【００８８】
ステップＳ２１１では、上記ステップＳ２０４〜ステップＳ２１０で得られた予測経路Ｒ’をメモリ（図示省略）に格納する。
【００８９】
ステップＳ２１２において、予め定められた予測経路の数Ｊと、上記ステップＳ２１１でメモリに格納された予測経路Ｒ’の数に対応する変数ｊとが等しいか否かを判定する。予測経路の数Ｊと変数ｊとが等しい場合には、ステップＳ２１６へ進む。一方、予測経路の数Ｊと変数ｊとが異なる場合には、ステップＳ２１４において変数ｊをインクリメントして、ステップＳ２０２へ戻る。
【００９０】
ステップＳ２１６において、上記ステップＳ２１１でメモリに格納された複数の予測経路を結果として出力して、車両挙動予測処理ルーチンを終了する。
【００９１】
次に、サーバ１４が実行する検索処理ルーチンについて説明する。サーバ１４は、少なくとも１台の車載装置１２から送信された、車両ＩＤと当該車両の位置情報（Ｘ，Ｙ）を受信すると、図１１に示すデータ格納処理ルーチンを実行する。
また、サーバ１４は、ユーザから入力されたクエリを受け付けると、図１２に示す検索処理ルーチンを実行する。
【００９２】
＜データ格納処理ルーチン＞
ステップＳ３００において、受信された車両ＩＤと当該車両の位置情報（Ｘ，Ｙ）とを受け付ける。
【００９３】
ステップＳ３０２において、補助的ハッシュテーブルＧを用いて、上記ステップＳ３００で受け付けた車両ＩＤから、当該車両ＩＤが現在属するメッシュＩＤを特定する。
【００９４】
ステップＳ３０４において、上記ステップＳ３０２で特定されたメッシュＩＤに対応するハッシュテーブルから、上記ステップＳ３００で受け付けた車両ＩＤに対応するデータを取り除く。
【００９５】
ステップＳ３０６において、上記ステップＳ３００で取得された車両の位置情報（Ｘ，Ｙ）に基づいて、新たなメッシュＩＤを計算する。
【００９６】
ステップＳ３０８において、上記ステップＳ３０６で計算されたメッシュＩＤに対応するハッシュテーブルに、上記ステップＳ３００で受け付けた車両ＩＤに対応するデータを格納する。
【００９７】
ステップＳ３１０において、上記ステップＳ３０６で計算された新たなメッシュＩＤに基づいて、補助的ハッシュテーブルＧを更新し、データ格納処理ルーチンを終了する。
【００９８】
＜検索処理ルーチン＞
まず、ステップＳ４００において、受付部１４０は、サーバ１４に入力されたクエリを受け付ける。
【００９９】
次に、ステップＳ４０２において、簡易予測部１４６は、上記ステップＳ４００で受け付けたクエリに含まれる検索条件と、上記データ格納処理ルーチンでデータベース１４５に格納された複数の車両の位置情報（Ｘ，Ｙ）とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択する。ステップＳ４０２は、図１３に示す簡易予測処理ルーチンによって実現される。
【０１００】
＜簡易予測処理ルーチン＞
ステップＳ５００において、検索条件に含まれる位置（道路セグメント）を中心とし、かつ検索条件に含まれる時間区間に応じて予め定められた範囲の領域Ｑを受け付ける。
【０１０１】
ステップＳ５０２において、車両のリストＷを初期化する。
【０１０２】
ステップＳ５０４において、上記ステップＳ５００で受け付けた領域Ｑを含むメッシュ集合を取得する。
【０１０３】
ステップＳ５０６において、上記ステップＳ５０４で取得されたメッシュ集合から、１つのメッシュｍを設定する。
【０１０４】
ステップＳ５０８において、データベース１４５に格納された位置情報（Ｘ，Ｙ）の各々に基づいて、上記ステップＳ５０６で設定されたメッシュｍに含まれる車両ＩＤの各々のうち、１つの車両ＩＤを設定する。
【０１０５】
ステップＳ５１０において、データベース１４５に格納された位置情報（Ｘ，Ｙ）の各々から、上記ステップＳ５０８で設定された車両ＩＤに対応する車両の位置情報（Ｘ，Ｙ）を取得する。
【０１０６】
ステップＳ５１２において、上記ステップＳ５１０で取得された車両の位置情報（Ｘ，Ｙ）に基づいて、車両が位置する緯度Ｘ及び経度Ｙが上記ステップＳ５００で取得された領域Ｑに含まれているか否かを判定する。車両が位置する緯度Ｘ及び経度Ｙが領域Ｑに含まれている場合には、ステップＳ５１４へ進む。一方、車両が位置する緯度Ｘ及び経度Ｙが上記ステップＳ５００で取得された領域Ｑに含まれていない場合には、ステップＳ５１６へ移行する。
【０１０７】
ステップＳ５１４において、上記ステップＳ５０８で設定された車両ＩＤを、車両のリストＷに格納する。
【０１０８】
ステップＳ５１６において、上記ステップＳ５０６で設定されたメッシュｍに属する全ての車両について、上記ステップＳ５０８〜ステップＳ５１４の処理を実行したか否かを判定する。上記ステップＳ５０６で設定されたメッシュｍに属する全ての車両について、上記ステップＳ５０８〜ステップＳ５１４の処理を実行した場合には、ステップＳ５１８へ進む。一方、上記ステップＳ５０６で設定されたメッシュｍに属する車両について、上記ステップＳ５０８〜ステップＳ５１４の処理を実行していない車両が存在する場合には、ステップＳ５０８へ戻る。
【０１０９】
ステップＳ５１８において、上記ステップＳ５０４で取得されたメッシュ集合に含まれる全てのメッシュについて、上記ステップＳ５０６〜ステップＳ５１６の処理を実行したか否かを判定する。上記ステップＳ５０４で取得されたメッシュ集合に含まれる全てのメッシュについて、上記ステップＳ５０６〜ステップＳ５１６の処理を実行した場合には、ステップＳ５２０へ進む。一方、上記ステップＳ５０４で取得されたメッシュ集合に含まれるメッシュについて、上記ステップＳ５０６〜ステップＳ５１６の処理を実行していないメッシュが存在する場合には、ステップＳ５０６へ戻る。
【０１１０】
ステップＳ５２０において、上記ステップＳ５１４で車両のリストＷに格納された車両ＩＤの各々を、検索条件を満たす車両の候補として、結果として出力し、簡易予測処理ルーチンを終了する。
【０１１１】
次に、検索処理ルーチンに戻り、ステップＳ４０４において、上記ステップＳ４０２で車両の候補として選択された車両の車載装置１２の各々に対し、上記ステップＳ４００で受け付けたクエリに含まれる検索条件を送信する。
【０１１２】
ここで、車両の候補として選択された車両の車載装置１２の各々は、上記ステップＳ４０４でサーバ１４から送信された検索条件を通信部１３０により受信すると、車載装置１２の推論部１３４は、図１４に示す推論処理ルーチンを実行する。以下、車載装置１２において実行される推論処理ルーチンを説明した後に、サーバ１４で実行される検索処理ルーチンのステップＳ４０６以降の処理を説明する。
【０１１３】
＜推論処理ルーチン＞
ステップＳ６００において、上記予測処理ルーチンのステップＳ１０４で出力された複数の予測経路と、通信部１３０により受信された検索条件とを取得する。
【０１１４】
ステップＳ６０２において、推論部１３４は、上記ステップＳ６００で取得された自車両の複数の予測経路及び検索条件に基づいて、確信度を算出する。ステップＳ６０２は、図１５に示す確信度算出処理ルーチンによって実現される。
【０１１５】
＜確信度算出処理ルーチン＞
ステップＳ７００において、上記ステップＳ６００で取得された検索条件に含まれる時間Ｔｑ及び道路セグメントＡを取得する。
【０１１６】
ステップＳ７０２において、確信度Ｐを初期化する。
【０１１７】
ステップＳ７０４において、上記ステップＳ６００で取得された予測経路の数Ｋを取得する。
【０１１８】
ステップＳ７０６において、上記ステップＳ６００で取得された複数の予測経路のうち、１つの予測経路Ｒを設定する。
【０１１９】
ステップＳ７０８において、時間変数Ｔｃを初期化する。
【０１２０】
ステップＳ７１０において、上記ステップＳ７０６で設定された予測経路Ｒに含まれる道路セグメントのうち、１つの道路セグメントｒを設定する。
【０１２１】
ステップＳ７１２において、上記ステップＳ７１０で設定された道路セグメントｒが、上記ステップＳ７００で取得された道路セグメントＡと一致するか否かを判定する。道路セグメントｒが道路セグメントＡと一致する場合には、ステップＳ７１３に移行する。一方、道路セグメントｒが道路セグメントＡと一致しない場合には、ステップＳ７１４へ進む。
【０１２２】
ステップＳ７１３において、上記ステップＳ７０２で初期化された確信度Ｐ又は前回の本ステップＳ７１３において更新された確信度Ｐを、増加式Ｐ←Ｐ＋１／Ｋに従って増加させる。
【０１２３】
ステップＳ７１４において、上記ステップＳ７０８で初期化された時間変数Ｔｃ又は前回の本ステップＳ７１４で更新された時間変数Ｔｃに、上記ステップＳ７１０で設定された道路セグメントｒの平均的な所要走行時間Ｔ（ｒｔ）を加算する。
【０１２４】
ステップＳ７１６において、上記ステップＳ７１４で更新された時間変数Ｔｃが、上記ステップＳ７００で取得された時間Ｔｑよりも大きいか否かを判定する。時間変数Ｔｃが時間Ｔｑよりも大きい場合には、ステップＳ７０６へ戻る。一方、時間変数Ｔｃが時間Ｔｑ以下の場合には、ステップＳ７１８へ進む。
【０１２５】
ステップＳ７１８において、上記ステップＳ７０６で設定された予測経路Ｒに含まれる全ての道路セグメントについて、上記ステップＳ７１０〜ステップＳ７１６の処理を実行したか否かを判定する。上記ステップＳ７０６で設定された予測経路Ｒに含まれる全ての道路セグメントについて、上記ステップＳ７１０〜ステップＳ７１６の処理を実行した場合には、ステップＳ７２０へ進む。一方、上記ステップＳ７０６で設定された予測経路Ｒに含まれる道路セグメントについて、上記ステップＳ７１０〜ステップＳ７１６の処理を実行していない道路セグメントが存在する場合には、ステップＳ７１０へ戻る。
【０１２６】
ステップＳ７２０において、上記ステップＳ７０４で取得されたＫ個の予測経路の全てについて、上記ステップＳ７０６〜ステップＳ７１８の処理を実行したか否かを判定する。上記ステップＳ７０４で取得されたＫ個の予測経路の全てについて、上記ステップＳ７０６〜ステップＳ７１８の処理を実行した場合には、ステップＳ７２２へ進む。一方、上記ステップＳ７０４で取得されたＫ個の予測経路について、上記ステップＳ７０６〜ステップＳ７１８の処理を実行していない予測経路が存在する場合には、ステップＳ７０６へ戻る。
【０１２７】
ステップＳ７２２において、上記ステップＳ７１３で更新された確信度Ｐを結果として出力して、確信度算出処理ルーチンを終了する。
【０１２８】
次に、推論処理ルーチンに戻り、ステップＳ６０４において、上記ステップＳ６０２で出力された確信度Ｐを、通信部１３０によりサーバ１４へ送信して、推論処理ルーチンを終了する。
【０１２９】
次に、サーバ１４で実行される検索処理ルーチンのステップＳ４０６以降の処理を説明する。
【０１３０】
ステップＳ４０６において、サーバ１４の通信部１４２は、車載装置１２の各々から送信された確信度Ｐを受信する。
【０１３１】
ステップＳ４０８において、上記ステップＳ４０４で検索条件を送信した車両の全てから、確信度Ｐを受信したか否かを判定する。検索条件を送信した車両の全てから、確信度Ｐを受信した場合には、ステップＳ４１０へ進む。一方、検索条件を送信した車両の全てから、確信度Ｐを受信していない場合には、ステップＳ４０６へ戻る。なお、検索条件を送信した車両の全てから確信度Ｐを受信していない場合であっても、予め定められた時間を経過した場合には、ステップＳ４１０へ進む。
【０１３２】
ステップＳ４１０において、車両検索部１４８は、上記ステップＳ４０６で受信された確信度Ｐの各々に基づいて、クエリに含まれる検索条件を満たす車両を検索する。
【０１３３】
ステップＳ４１２において、上記ステップＳ４１０で検索された車両の各々に対し、当該車両から送信された確信度に応じたタスクであって、車両に実行させるタスクを指示する指示情報を生成する。
【０１３４】
ステップＳ４１４において、上記ステップＳ４１２で生成された車両に実行させるタスクを指示する指示情報の各々を、車両の各々に送信して、検索処理ルーチンを終了する。
【０１３５】
また、指示情報を受信した車載装置１２の各々は、タスク処理部１３６によって、通信部１３０が受信した指示情報に基づいて、タスクが実行される。
【０１３６】
以上説明したように、本発明の第１の実施の形態の車両検索システムによれば、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の予測経路を繰り返し予測し、サーバから送信された検索条件を受信した場合に、予測された車両の予測経路に基づいて確信度を生成し、生成された確信度をサーバへ送信し、サーバは、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、検索条件を送信し、車載装置の各々から送信された確信度に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる。
【０１３７】
また、将来位置の予測を逐次的に行うため、サーバ側から問い合わせがあった段階で推論処理（確信度算出処理）のみを行えば結果を返すことができるため、予測に要する時間の分だけ遅延を短縮することができ、多数の候補車両に対して「未来の車両位置の検索」という不確実性を伴う複雑な検索処理を、遅延を抑制して実現することができる。
【０１３８】
また、サーバ側ですべての処理を行わず、車両側のリソースを分散的に活用するため、サーバ側での小さな負荷を実現でき、車両台数が増加してもサーバ側のリソース増強を必要とせずに、車両の検索を行うことができる。
【０１３９】
また、推論処理を実施すべき車両の数を減らすことで車両−サーバ間の通信量および車両側の一台あたりの平均的な計算負荷を軽減することができ、推論処理の負荷の総量を小さくすることができる。
【０１４０】
［第２の実施の形態］
次に、本発明の第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１４１】
第２の実施の形態では、確信度を算出する推論部がサーバ側に備えられている点が、第１の実施の形態と異なっている。上記第１の実施の形態では、確信度を算出する推論部が車載装置に実装されている場合を例に説明したが、推論部をサーバ側に実装することもできる。推論部をサーバ側に実装する場合、サーバの通信部は、車載装置の車両挙動予測部によって出力された予測経路を通信によって受け取り、サーバ側の推論部で確信度を算出する。
【０１４２】
＜第２の実施の形態に係る車両検索システム２１０の構成＞
図１６に示すように、本発明の第２の実施の形態に係る車両検索システム２１０は、複数の車両に備えられた複数の車載装置２１２と、複数の車載装置２１２から送信された車両情報を受信して、検索条件を満たす車両を検索するサーバ２１４とを備えている。複数の車載装置２１２とサーバ２１４とは、インターネットなどのネットワーク１６を介して接続されている。
【０１４３】
［車載装置２１２］
車載装置２１２は、位置計測部１２０と、車両センサ１２４と、位置計測部１２０によって計測された自車両の位置情報、及び車両センサ１２４によって検出された自車両の速度に基づいて、自車両の挙動を予測するコンピュータ２２６とを備えている。
【０１４４】
コンピュータ２２６は、ＣＰＵと、ＲＡＭと、後述する各処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備え、機能的には次に示すように構成されている。コンピュータ２２６は、位置計測部１２０によって計測された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）と、車両センサ１２４によって検出された自車両の速度とを取得する情報取得部１２８と、情報取得部１２８によって取得された車両情報を車両ＩＤと共にサーバ２１４へ逐次送信すると共に、サーバ２１４との間でデータの送受信を行う通信部２３０と、情報取得部１２８によって取得された自車両の位置情報及び自車両の速度に基づいて、自車両の予測経路を予測する車両挙動予測部１３２と、サーバ２１４から送信されたタスクの指示情報を受信した場合に、タスクを実行するタスク処理部１３６とを備えている。なお、通信部２３０は、車両挙動情報送信手段と、車両情報送信手段との一例である。
【０１４５】
通信部２３０は、情報取得部１２８によって取得された自車両の現時刻ｔの位置情報（Ｘ，Ｙ）を、サーバ２１４へ逐次送信する。また、通信部２３０は、サーバ２１４から送信された、予測結果送信要求を受信する。また、通信部２３０は、サーバ２１４から送信された予測結果送信要求を受信した場合に、車両挙動予測部１３２によって予測された予測経路をサーバ２１４へ送信する。また、通信部２３０は、サーバ２１４から送信された、車両に実行させるタスクを指示する指示情報を受信する。
【０１４６】
［サーバ２１４］
サーバ２１４は、ＣＰＵ、後述する各処理ルーチンを実現するためのプログラム等を記憶したＲＯＭ、データを一時的に記憶するＲＡＭ、記憶手段としてのメモリ、ネットワークインタフェース等を含むサーバで構成されており、機能的には、受付部１４０、通信部２４２、データ格納部１４４、データベース１４５、簡易予測部１４６、推論部２３４、車両検索部２４８、及びタスク生成部１５０を含んだ構成で表すことができる。通信部１４２は、予測結果送信要求送信手段の一例であり、簡易予測部１４６は、車両選択手段の一例である。また、推論部２３４は、検索情報生成手段の一例である。
【０１４７】
通信部２４２は、複数の車載装置２１２の各々から送信された車両の位置情報（Ｘ，Ｙ）を受信する。また、通信部２４２は、後述する簡易予測部１４６によって車両の候補として選択された車両の車載装置２１２の各々に対し、予測結果送信要求を送信する。また、通信部２４２は、後述するタスク生成部１５０によって生成された指示情報を、車両の車載装置２１２に対し送信する。
【０１４８】
推論部２３４は、通信部２４２によって受信された車両の予測経路の各々に基づいて、車載装置２１２の各々について、クエリに含まれる検索条件を満たすか否かを表す情報として、検索条件を満たす度合いを表す確信度を算出する。
【０１４９】
車両検索部２４８は、推論部２３４によって生成された確信度に基づいて、検索条件を満たす車両を検索する。
【０１５０】
＜車両検索システムの作用＞
次に、本発明の第２の実施の形態に係る車両検索システム２１０の動作について説明する。車載装置２１２を搭載した車両の各々が走行し、サーバ２１４が起動されると、各車両の車載装置２１２は図９に示す予測処理ルーチンを実行し、サーバ２１４は、図１２に示す検索処理ルーチンを実行する。また、上記図１４に示した推論処理ルーチン及び上記図１５に示した確信度算出処理ルーチンは、サーバ２１４側で実行される。
【０１５１】
なお、第２の実施の形態に係る車両検索システムの他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１５２】
以上説明したように、本発明の第２の実施の形態の車両検索システムによれば、車載装置は、車両情報に基づいて、予め定められた予測時間後まで、車両の予測経路を繰り返し予測し、サーバから送信された予測結果送信要求を受信した場合に、予測された車両の予測経路をサーバへ送信し、サーバは、入力された検索条件と複数の車載装置の各々から送信された車両情報とに基づいて、複数の車両の各々から、検索条件を満たす車両の候補を選択し、車両の候補として選択された車両の車載装置の各々に対し、予測結果送信要求を送信し、車載装置の各々から送信された車両の予測経路に基づいて、車載装置の各々について確信度を算出し、確信度に基づいて、車両を検索することにより、車両検索の遅延を抑制することができる。
【０１５３】
なお、本発明は、各図を用いて説明した実施の形態例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更して適用することが可能である。
【０１５４】
例えば、上記の実施の形態では、車両の経路を予測する場合を例に説明したが、これに限定されるものではない。例えば、車両センサ１２４がカーナビゲーションシステムを用いて構成されており、当該カーナビゲーションシステムに目的地が入力され、車両の走行経路がドライバに示されている場合、ドライバは高い可能性でカーナビゲーションシステムの経路を利用すると考えられるため、当該経路を予測経路とするなどの改良も考えられる。
【０１５５】
また、上記の実施の形態では、車両の挙動の時系列として予測経路を予測する場合を例に説明したが、これに限定されるものではなく、例えば車両の挙動の時系列として目的地を予測してもよい。
【０１５６】
また、上記の実施の形態では、簡易予測部は、車両の位置情報に基づいて確信度を算出する場合を例に説明したが、これに限定されるものではなく、例えば、車両の進行方向のベクトルの先に道路セグメントＡ（地点Ａ）があるか否かのような角度の情報に基づいて、確信度を算出することもできる。
【０１５７】
また、上記の実施の形態では、タスク生成部１５０が、確信度に応じたタスクを生成し、タスク処理部１３６が、タスクを実行する場合を例に説明したが、これに限定されるものではなく、タスクを生成せず、タスクを実行せずともよい。
【０１５８】
また、上記の実施の形態では、車両センサ１２４によって自車両の速度を検出し、自車両の速度を用いてｒｔの平均的な所要走行時間をＴ（ｒｔ）を算出する場合を例に説明したが、これに限定されるものではない。例えば、ｒｔについて予め定められた平均的な所要走行時間をＴ（ｒｔ）を用いてもよい。
【０１５９】
なお、本発明のプログラムを記憶する記憶媒体は、特に限定されず、ハードディスクであってもよいし、ＲＯＭであってもよい。また、ＣＤ−ＲＯＭやＤＶＤディスク、光磁気ディスクやＩＣカードであってもよい。更にまた、該プログラムを、ネットワークに接続されたサーバ等からダウンロードするようにしてもよい。
【符号の説明】
【０１６０】
１０，２１０  車両検索システム
１２，２１２  車載装置
１４，２１４  サーバ
１６   ネットワーク
１２０ 位置計測部
１２４ 車両センサ
１２６，２２６  コンピュータ
１２８ 情報取得部
１３０，２３０  通信部
１３２ 車両挙動予測部
１３４，２３４  推論部
１３６ タスク処理部
１４０ 受付部
１４２，２４２  通信部
１４４ データ格納部
１４５ データベース
１４６ 簡易予測部
１４８，２４８  車両検索部
１５０ タスク生成部
【図１】
0006477087.tif 000002
【図２】
0006477087.tif 000003
【図３】
0006477087.tif 000004
【図４】
0006477087.tif 000005
【図５】
0006477087.tif 000006
【図６】
0006477087.tif 000007
【図７】
0006477087.tif 000008
【図８】
0006477087.tif 000009
【図９】
0006477087.tif 000010
【図１０】
0006477087.tif 000011
【図１１】
0006477087.tif 000012
【図１２】
0006477087.tif 000013
【図１３】
0006477087.tif 000014
【図１４】
0006477087.tif 000015
【図１５】
0006477087.tif 000016
【図１６】
0006477087.tif 000017