行動予測装置、方法およびプログラム
【課題】目的地までの経路、および経由地点での時刻を推定する。
【解決手段】第１時刻と第１位置と第１速度と第１重みスコアとを含むパーティクルを複数個設定し、開始時刻での全ての重みスコアをゼロに設定し全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する手段１０３と、パーティクルごとに、パーティクルの現在位置および現在速度に基づいて未来の第２時刻での第２位置を計算し、パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での第２速度を計算し、第２時刻での複数のパーティクルのうちユーザに関する過去の所在時刻と所在位置と所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する手段１０３と、複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する手段１０３と、を具備する。
【解決手段】第１時刻と第１位置と第１速度と第１重みスコアとを含むパーティクルを複数個設定し、開始時刻での全ての重みスコアをゼロに設定し全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する手段１０３と、パーティクルごとに、パーティクルの現在位置および現在速度に基づいて未来の第２時刻での第２位置を計算し、パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での第２速度を計算し、第２時刻での複数のパーティクルのうちユーザに関する過去の所在時刻と所在位置と所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する手段１０３と、複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する手段１０３と、を具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定する行動予測装置、方法およびプログラムに関する。
【背景技術】
【０００２】
ユーザの現在位置と目的地を入力することによって、ユーザが目的地に向かう経路と、経路途中で通過する場所、目的地に到着する時刻を得ることができるナビゲーションサービスが存在する。そのようなナビゲーションを実現する技術として、特許文献１や特許文献２では、ユーザの通過する経路が既知であるとして、目的地までの通行時間を精度よく予測する方法が示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−３２８５７２号公報
【特許文献２】特開２００２−１１７４９２公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
既存のナビゲーションシステムは、利用者がある規定の経路に沿って行動することを仮定している。しかし、この方法だと目的地に到着する経路が複数ある場合や、ユーザがナビゲーションシステムの提示した経路通りに行動しない場合には目的地に到着する時刻や経路の推定に失敗してしまう。
【０００５】
本発明は、上記の事情に鑑みてなされたもので、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定する行動予測装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述の課題を解決するため、本発明の行動予測装置は、開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測装置であって、第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定手段と、パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算手段と、複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力手段と、を具備することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定することができる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施の形態に係る行動予測装置のブロック図。
【図２】図１の行動予測装置の動作の一例を示すフローチャート。
【図３】図２のステップＳ２０４の詳細な一例を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照しながら本発明の実施形態に係る行動予測装置、方法およびプログラムについて詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
まず実施形態の行動予測装置の動作原理について概略を説明する。
ユーザが携行するデバイスに搭載される位置情報計測システムによって取得された位置情報履歴を用いることで、実施形態の行動予測装置は、ユーザが過去に移動したときの履歴をもとにしてユーザの経路および移動中の経由地点を通過するときの時刻を推定することが可能になる。本実施の形態では、ユーザが行動する経路の推定にはパーティクルフィルタを用いる。パーティクルフィルタを用いることで、ユーザの過去の行動経路のうち、行動経路の推定に有用な履歴を自動的に選択し、経路の予測を行うことができる。また、パーティクルフィルタを用いることで、ユーザがとる経路が幾種類もあった場合にも、どの経路をとっているかを確率的に求めることができる。
【００１０】
次に、実施の形態の行動予測装置について図１を参照して説明する。
本実施の形態の行動予測装置は、位置クエリ入力部１０１、位置情報履歴記録部１０２、行動予測処理部１０３、および予測結果出力部１０４を含む。
位置クエリ入力部１０１は、行動予測処理開始のトリガとなる、ユーザの現在の滞在位置の座標（緯度および経度で指定）と現在時刻との組、およびユーザの目的地の座標（緯度および経度で指定）を入力として受けとる。現在の滞在位置の座標と現在時刻との組は（緯度，経度，計測された時刻）で表され、ユーザの目的地の座標は（緯度，経度）で表される。受けとったクエリを行動予測処理部１０３に渡すことで行動予測処理が行われる。
【００１１】
位置情報履歴記録部１０２は、過去に記録されたユーザの位置情報（位置情報履歴とも称する）を記録している。記録されている位置情報は緯度、経度および計測された時刻の３つ組からなり、（緯度，経度，計測された時刻）で表される。また、位置情報はユーザが携行するデバイスに搭載される位置情報計測システムによって、例えば一ヶ月以上の長期間継続的に記録されているものとする。
【００１２】
行動予測処理部１０３は、位置クエリ入力部１０１から受けとった入力と、位置情報履歴記録部１０２に保存されているユーザの位置情報履歴とを利用して行動予測処理を行う。ある時刻におけるユーザの位置の予測結果は、有限個のパーティクルとよばれる緯度および経度の値をもつ点の集合として表される。パーティクルの分布密度がより高い場所が、その時点でユーザがいる可能性がより高い場所として解釈される。予測結果は予測結果出力部１０４に渡される。パーティクルの詳細については後に図２を参照して説明する。
【００１３】
予測結果出力部１０４は、行動予測処理部１０３から受け取ったパーティクルの集合からユーザの位置を推定して出力する。ユーザの位置の推定には、例えばパーティクルの重心をとる方法、カーネル密度推定法によってユーザ位置の確率分布を算出する等の方法が適用できる。
【００１４】
次に、実施形態の行動予測装置の動作の一例について図２を参照して説明する。
処理開始後、位置クエリ入力部１０１が入力クエリを受けとる（ステップＳ２０１）。入力クエリは、ユーザの現在位置の座標および時刻ｓ＝（ｘｓ，ｙｓ，ｔｓ）と、目的とする滞在場所の座標ｇ＝（ｘｇ，ｙｇ）とからなる。
【００１５】
行動予測処理部１０３がステップＳ２０１で入力として受けとったパラメータをもとにしてパーティクルフィルタの初期化処理を行う（ステップＳ２０２）。ここで、ｐｔ（ｉ）を時刻ｔにおけるｉ番目のパーティクルとして、ｐｔ（ｉ）＝＜ｘ（ｉ），ｙ（ｉ），ｕ（ｉ），ｖ（ｉ），ｗ（ｉ），ｔ＞と定義する。ここで、ｘ（ｉ）、ｙ（ｉ）はそれぞれパーティクルｐｔ（ｉ）の経度および緯度、ｕ（ｉ）、ｖ（ｉ）はそれぞれ東西方向、南北方向の速度、ｗ（ｉ）は重みスコア、ｔは時刻であるとする。生成するパーティクルの個数をＮとすると、パーティクルの初期化はｐｔｓ（１）、…、ｐｔｓ（Ｎ）のそれぞれについて重みスコアをゼロにすること、すなわち、ｐｔｓ（ｉ）＝＜ｘｓ，ｙｓ，ｕｓ，ｖｓ，０，ｔｓ＞とすることに相当する（ｉは１からＮの自然数）。ここでベクトル（ｕｓ，ｖｓ）は、ｓとｇを結ぶ方向ベクトルの正数倍であるような単位ベクトルとする。なお、以下ではベクトルｘ（ｉ）＝（ｘ（ｉ），ｙ（ｉ））、ベクトルｖ（ｉ）＝（ｕ（ｉ），ｖ（ｉ））、ベクトルｖｓ＝（ｕｓ，ｖｓ）というベクトルを用いた表記も併用する。図および数式ではベクトルを単に太字で示す。例えばベクトルｘを単にｘの太字で示す。
【００１６】
行動予測処理部１０３が、ある時点ｔでのパーティクルの集合が目的地ｇに到達したか、あるいはステップＳ２０４からステップＳ２０６までの反復の回数があらかじめ定めたしきい値以上となっているかどうかを判定する（ステップＳ２０３）。ここで、目的地ｇに到達したかどうかの判定は、例えばｇから距離ε以内にあるパーティクルと距離εの外にあるパーティクルとの比率があるしきい値を超えたかどうかで判定できる。行動予測処理部１０３はこの比率がしきい値以上である場合には目的地ｇに到達したと判定する。判定結果が真であるならば処理を終了し、判定結果が偽であるならばステップＳ２０４に遷移する。
【００１７】
行動予測処理部１０３がパーティクルの更新処理を行う（ステップＳ２０４）。
ここで、ステップＳ２０４のパーティクル更新処理の詳細を図３のフローを用いて説明する。
まずパーティクルの時刻ｔ＋１での新しい位置を現在の位置と速度をもとに計算する（ステップＳ３０１）。ここでΔｔは時刻ｔと時刻ｔ＋１の間の時間幅であり、処理開始時にパラメータとして与えるものとする。
【００１８】
次に速度ベクトルの更新を行う（ステップＳ３０２）。ここでＮ（μ，Σ）は平均値μ、分散共分散行列がΣである２次元のガウス分布を表しており、この式では２次元のガウス分布に沿った正規乱数を発生させて、その値を速度ベクトルの更新値としている。分散共分散行列は処理開始時にパラメータとして与えるものとする。
【００１９】
最後にステップＳ３０２で更新された速度と位置によってパーティクルを更新し（ステップＳ３０３）、処理を終了する。
再び図２のフローチャートに戻り、ステップＳ２０５へ進む。
行動予測処理部１０３が各パーティクルについて重みスコアｗ’（ｉ）を計算する（ステップＳ２０５）。重みスコアの計算には過去に取得された位置情報履歴データを利用する。ここで、過去の観測データである位置情報履歴に含まれるベクトルｘには、緯度、経度、時刻とともにその時点での速度も関連づけられているとする。速度は位置取得時に同時に計測されるとしてもよいし、実施の形態の行動予測装置が、直前、直後の観測データとの位置、時刻の差分より算出してもよい。
【００２０】
全ての過去の観測データの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、位置、速度、観測された時刻の組とする。Ｄを用いた重みスコアの計算式は下記の（１）式のとおりである。
【００２１】
【数１】
ここで、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、下記の（２）式で表される。
【００２２】
【数２】
ここでθ１、θ２は重みスコア計算におけるパラメータであり、本手法実行時に手動で定めるものとする。
次に行動予測処理部１０３が、現在のパーティクルの集合｛ｐｔ（１），ｐｔ（２），…，ｐｔ（Ｎ）｝から、１つのパーティクルが、それぞれ確率ｗ（１）／Ｗｔ、ｗ（２）／Ｗｔ、…、ｗ（Ｎ）／Ｗｔで選択されるとしてＮ回復元抽出を行い、新たなＮ個のパーティクルの集合を生成し獲得する（ステップＳ２０６）。ここでＷｔ＝Σｗ（ｉ）である。
ステップＳ２０４からＳ２０６までを繰り返す回数が時間を進めることになるので、この回数を調整すれば任意の時点でのユーザの位置の予測が可能になる。
【００２３】
また、本実施の形態の手法は、ある２つの時刻においてユーザの位置が観測された場合に、２つの時刻間でのユーザの位置を推定する補間問題にも適用することができる。その場合は補間対象の２点のうち時刻的に先の方を開始地点、後の方を目的地点として図１の行動予測装置を実行すればよい。さらに、処理によって得られたパーティクルの分布に対し、“Mike Klaas, Mark Briers, Nando de Freitas, Arnaud Doucet, Simon Maskell, Dustin Lang, “Fast Particle Filter Smoothing: If I Had a Million Particles”, In proceedings of the 23rd international conference on machine learning, 2006”にあるようなBackward Smootherを適用することによって、開始地点、目的地点の座標を制約に組み込んだパーティクルの分布を再計算することができる。
【００２４】
以上に示した行動予測装置によれば、蓄積された過去のユーザの位置情報履歴を用いて、未来の任意のある時刻におけるユーザの位置の予測、および２つの観測点間での任意の時刻における位置の予測を行うことができる。実施の形態の行動予測装置によれば、例えば、ユーザが公共交通手段を利用して移動する際、ユーザの現在位置とこれから向かう目的地が既知の場合に、その目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定することができる。
【００２５】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の行動予測装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、またはこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の行動予測装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合または読み込む場合はネットワークを通じて取得または読み込んでもよい。
また、記録媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記録媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
また、記録媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記録媒体に含まれ、媒体の構成は何れの構成であってもよい。
【００２６】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記録媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【００２７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００２８】
１０１…位置クエリ入力部、１０２…位置情報履歴記録部、１０３…行動予測処理部、１０４…予測結果出力部。
【技術分野】
【０００１】
本発明は、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定する行動予測装置、方法およびプログラムに関する。
【背景技術】
【０００２】
ユーザの現在位置と目的地を入力することによって、ユーザが目的地に向かう経路と、経路途中で通過する場所、目的地に到着する時刻を得ることができるナビゲーションサービスが存在する。そのようなナビゲーションを実現する技術として、特許文献１や特許文献２では、ユーザの通過する経路が既知であるとして、目的地までの通行時間を精度よく予測する方法が示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−３２８５７２号公報
【特許文献２】特開２００２−１１７４９２公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
既存のナビゲーションシステムは、利用者がある規定の経路に沿って行動することを仮定している。しかし、この方法だと目的地に到着する経路が複数ある場合や、ユーザがナビゲーションシステムの提示した経路通りに行動しない場合には目的地に到着する時刻や経路の推定に失敗してしまう。
【０００５】
本発明は、上記の事情に鑑みてなされたもので、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定する行動予測装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述の課題を解決するため、本発明の行動予測装置は、開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測装置であって、第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定手段と、パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算手段と、複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力手段と、を具備することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定することができる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施の形態に係る行動予測装置のブロック図。
【図２】図１の行動予測装置の動作の一例を示すフローチャート。
【図３】図２のステップＳ２０４の詳細な一例を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照しながら本発明の実施形態に係る行動予測装置、方法およびプログラムについて詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
まず実施形態の行動予測装置の動作原理について概略を説明する。
ユーザが携行するデバイスに搭載される位置情報計測システムによって取得された位置情報履歴を用いることで、実施形態の行動予測装置は、ユーザが過去に移動したときの履歴をもとにしてユーザの経路および移動中の経由地点を通過するときの時刻を推定することが可能になる。本実施の形態では、ユーザが行動する経路の推定にはパーティクルフィルタを用いる。パーティクルフィルタを用いることで、ユーザの過去の行動経路のうち、行動経路の推定に有用な履歴を自動的に選択し、経路の予測を行うことができる。また、パーティクルフィルタを用いることで、ユーザがとる経路が幾種類もあった場合にも、どの経路をとっているかを確率的に求めることができる。
【００１０】
次に、実施の形態の行動予測装置について図１を参照して説明する。
本実施の形態の行動予測装置は、位置クエリ入力部１０１、位置情報履歴記録部１０２、行動予測処理部１０３、および予測結果出力部１０４を含む。
位置クエリ入力部１０１は、行動予測処理開始のトリガとなる、ユーザの現在の滞在位置の座標（緯度および経度で指定）と現在時刻との組、およびユーザの目的地の座標（緯度および経度で指定）を入力として受けとる。現在の滞在位置の座標と現在時刻との組は（緯度，経度，計測された時刻）で表され、ユーザの目的地の座標は（緯度，経度）で表される。受けとったクエリを行動予測処理部１０３に渡すことで行動予測処理が行われる。
【００１１】
位置情報履歴記録部１０２は、過去に記録されたユーザの位置情報（位置情報履歴とも称する）を記録している。記録されている位置情報は緯度、経度および計測された時刻の３つ組からなり、（緯度，経度，計測された時刻）で表される。また、位置情報はユーザが携行するデバイスに搭載される位置情報計測システムによって、例えば一ヶ月以上の長期間継続的に記録されているものとする。
【００１２】
行動予測処理部１０３は、位置クエリ入力部１０１から受けとった入力と、位置情報履歴記録部１０２に保存されているユーザの位置情報履歴とを利用して行動予測処理を行う。ある時刻におけるユーザの位置の予測結果は、有限個のパーティクルとよばれる緯度および経度の値をもつ点の集合として表される。パーティクルの分布密度がより高い場所が、その時点でユーザがいる可能性がより高い場所として解釈される。予測結果は予測結果出力部１０４に渡される。パーティクルの詳細については後に図２を参照して説明する。
【００１３】
予測結果出力部１０４は、行動予測処理部１０３から受け取ったパーティクルの集合からユーザの位置を推定して出力する。ユーザの位置の推定には、例えばパーティクルの重心をとる方法、カーネル密度推定法によってユーザ位置の確率分布を算出する等の方法が適用できる。
【００１４】
次に、実施形態の行動予測装置の動作の一例について図２を参照して説明する。
処理開始後、位置クエリ入力部１０１が入力クエリを受けとる（ステップＳ２０１）。入力クエリは、ユーザの現在位置の座標および時刻ｓ＝（ｘｓ，ｙｓ，ｔｓ）と、目的とする滞在場所の座標ｇ＝（ｘｇ，ｙｇ）とからなる。
【００１５】
行動予測処理部１０３がステップＳ２０１で入力として受けとったパラメータをもとにしてパーティクルフィルタの初期化処理を行う（ステップＳ２０２）。ここで、ｐｔ（ｉ）を時刻ｔにおけるｉ番目のパーティクルとして、ｐｔ（ｉ）＝＜ｘ（ｉ），ｙ（ｉ），ｕ（ｉ），ｖ（ｉ），ｗ（ｉ），ｔ＞と定義する。ここで、ｘ（ｉ）、ｙ（ｉ）はそれぞれパーティクルｐｔ（ｉ）の経度および緯度、ｕ（ｉ）、ｖ（ｉ）はそれぞれ東西方向、南北方向の速度、ｗ（ｉ）は重みスコア、ｔは時刻であるとする。生成するパーティクルの個数をＮとすると、パーティクルの初期化はｐｔｓ（１）、…、ｐｔｓ（Ｎ）のそれぞれについて重みスコアをゼロにすること、すなわち、ｐｔｓ（ｉ）＝＜ｘｓ，ｙｓ，ｕｓ，ｖｓ，０，ｔｓ＞とすることに相当する（ｉは１からＮの自然数）。ここでベクトル（ｕｓ，ｖｓ）は、ｓとｇを結ぶ方向ベクトルの正数倍であるような単位ベクトルとする。なお、以下ではベクトルｘ（ｉ）＝（ｘ（ｉ），ｙ（ｉ））、ベクトルｖ（ｉ）＝（ｕ（ｉ），ｖ（ｉ））、ベクトルｖｓ＝（ｕｓ，ｖｓ）というベクトルを用いた表記も併用する。図および数式ではベクトルを単に太字で示す。例えばベクトルｘを単にｘの太字で示す。
【００１６】
行動予測処理部１０３が、ある時点ｔでのパーティクルの集合が目的地ｇに到達したか、あるいはステップＳ２０４からステップＳ２０６までの反復の回数があらかじめ定めたしきい値以上となっているかどうかを判定する（ステップＳ２０３）。ここで、目的地ｇに到達したかどうかの判定は、例えばｇから距離ε以内にあるパーティクルと距離εの外にあるパーティクルとの比率があるしきい値を超えたかどうかで判定できる。行動予測処理部１０３はこの比率がしきい値以上である場合には目的地ｇに到達したと判定する。判定結果が真であるならば処理を終了し、判定結果が偽であるならばステップＳ２０４に遷移する。
【００１７】
行動予測処理部１０３がパーティクルの更新処理を行う（ステップＳ２０４）。
ここで、ステップＳ２０４のパーティクル更新処理の詳細を図３のフローを用いて説明する。
まずパーティクルの時刻ｔ＋１での新しい位置を現在の位置と速度をもとに計算する（ステップＳ３０１）。ここでΔｔは時刻ｔと時刻ｔ＋１の間の時間幅であり、処理開始時にパラメータとして与えるものとする。
【００１８】
次に速度ベクトルの更新を行う（ステップＳ３０２）。ここでＮ（μ，Σ）は平均値μ、分散共分散行列がΣである２次元のガウス分布を表しており、この式では２次元のガウス分布に沿った正規乱数を発生させて、その値を速度ベクトルの更新値としている。分散共分散行列は処理開始時にパラメータとして与えるものとする。
【００１９】
最後にステップＳ３０２で更新された速度と位置によってパーティクルを更新し（ステップＳ３０３）、処理を終了する。
再び図２のフローチャートに戻り、ステップＳ２０５へ進む。
行動予測処理部１０３が各パーティクルについて重みスコアｗ’（ｉ）を計算する（ステップＳ２０５）。重みスコアの計算には過去に取得された位置情報履歴データを利用する。ここで、過去の観測データである位置情報履歴に含まれるベクトルｘには、緯度、経度、時刻とともにその時点での速度も関連づけられているとする。速度は位置取得時に同時に計測されるとしてもよいし、実施の形態の行動予測装置が、直前、直後の観測データとの位置、時刻の差分より算出してもよい。
【００２０】
全ての過去の観測データの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、位置、速度、観測された時刻の組とする。Ｄを用いた重みスコアの計算式は下記の（１）式のとおりである。
【００２１】
【数１】
ここで、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、下記の（２）式で表される。
【００２２】
【数２】
ここでθ１、θ２は重みスコア計算におけるパラメータであり、本手法実行時に手動で定めるものとする。
次に行動予測処理部１０３が、現在のパーティクルの集合｛ｐｔ（１），ｐｔ（２），…，ｐｔ（Ｎ）｝から、１つのパーティクルが、それぞれ確率ｗ（１）／Ｗｔ、ｗ（２）／Ｗｔ、…、ｗ（Ｎ）／Ｗｔで選択されるとしてＮ回復元抽出を行い、新たなＮ個のパーティクルの集合を生成し獲得する（ステップＳ２０６）。ここでＷｔ＝Σｗ（ｉ）である。
ステップＳ２０４からＳ２０６までを繰り返す回数が時間を進めることになるので、この回数を調整すれば任意の時点でのユーザの位置の予測が可能になる。
【００２３】
また、本実施の形態の手法は、ある２つの時刻においてユーザの位置が観測された場合に、２つの時刻間でのユーザの位置を推定する補間問題にも適用することができる。その場合は補間対象の２点のうち時刻的に先の方を開始地点、後の方を目的地点として図１の行動予測装置を実行すればよい。さらに、処理によって得られたパーティクルの分布に対し、“Mike Klaas, Mark Briers, Nando de Freitas, Arnaud Doucet, Simon Maskell, Dustin Lang, “Fast Particle Filter Smoothing: If I Had a Million Particles”, In proceedings of the 23rd international conference on machine learning, 2006”にあるようなBackward Smootherを適用することによって、開始地点、目的地点の座標を制約に組み込んだパーティクルの分布を再計算することができる。
【００２４】
以上に示した行動予測装置によれば、蓄積された過去のユーザの位置情報履歴を用いて、未来の任意のある時刻におけるユーザの位置の予測、および２つの観測点間での任意の時刻における位置の予測を行うことができる。実施の形態の行動予測装置によれば、例えば、ユーザが公共交通手段を利用して移動する際、ユーザの現在位置とこれから向かう目的地が既知の場合に、その目的地に到達するまでの経路、および経路途中でユーザが経由する各地点を通過する時刻を推定することができる。
【００２５】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の行動予測装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、またはこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の行動予測装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合または読み込む場合はネットワークを通じて取得または読み込んでもよい。
また、記録媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記録媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
また、記録媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記録媒体に含まれ、媒体の構成は何れの構成であってもよい。
【００２６】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記録媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【００２７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００２８】
１０１…位置クエリ入力部、１０２…位置情報履歴記録部、１０３…行動予測処理部、１０４…予測結果出力部。
【特許請求の範囲】
【請求項１】
開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測装置であって、
第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定手段と、
パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算手段と、
複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力手段と、を具備することを特徴とする行動予測装置。
【請求項２】
前記計算手段は、前記第２重みスコアとして、下記ｗ’（ｉ）
【数１】
を計算し、ｉはパーティクルのインデックスであり、全ての過去の前記位置情報履歴に含まれるデータの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、ｔｄが過去の所在時刻、ベクトルｘｄが該所在時刻での所在位置、およびベクトルｖｄが該所在時刻および該所在位置での所在速度を示し、ベクトルｖｓは開始時刻での速度であり、θ１、θ２はある値を有するパラメータであり、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、
【数２】
であることを特徴とする請求項１に記載の行動予測装置。
【請求項３】
前記第２時刻での複数のパーティクルの位置が前記目的位置からしきい値距離以内にあると見なせる場合には該第２時刻を目標到達時刻と判定し、しきい値距離以内にあると見なせない場合には第２時刻を現在時刻として、前記計算手段が計算した第２位置および第２速度をそれぞれ現在位置および現在速度として前記計算手段に第２時刻よりも未来の第３時刻での第３位置、第３速度、および第３重みスコアを計算させる判定手段と、
第３位置、第３速度、および第３重みスコアを有する全てのパーティクル集合から、パーティクルごとに算出される確率である（対応する第３重みスコア）／（全てのパーティクルについての第３重みスコアの和）で該パーティクルが選択されるとしてパーティクルの数だけ復元抽出を行い、新たなパーティクル集合を生成する生成手段と、をさらに具備することを特徴とする請求項１または請求項２に記載の行動予測装置。
【請求項４】
開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測方法であって、
第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定ステップと、
パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算ステップと、
複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力ステップと、を具備することを特徴とする行動予測方法。
【請求項５】
前記計算ステップでは、前記第２重みスコアとして、下記ｗ’（ｉ）
【数３】
を計算し、ｉはパーティクルのインデックスであり、全ての過去の前記位置情報履歴に含まれるデータの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、ｔｄが過去の所在時刻、ベクトルｘｄが該所在時刻での所在位置、およびベクトルｖｄが該所在時刻および該所在位置での所在速度を示し、ベクトルｖｓは開始時刻での速度であり、θ１、θ２はある値を有するパラメータであり、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、
【数４】
であることを特徴とする請求項１に記載の行動予測方法。
【請求項６】
前記第２時刻での複数のパーティクルの位置が前記目的位置からしきい値距離以内にあると見なせる場合には該第２時刻を目標到達時刻と判定し、しきい値距離以内にあると見なせない場合には第２時刻を現在時刻として、前記計算ステップで計算した第２位置および第２速度をそれぞれ現在位置および現在速度として前記計算ステップで第２時刻よりも未来の第３時刻での第３位置、第３速度、および第３重みスコアを計算させる判定ステップと、
第３位置、第３速度、および第３重みスコアを有する全てのパーティクル集合から、パーティクルごとに算出される確率である（対応する第３重みスコア）／（全てのパーティクルについての第３重みスコアの和）で該パーティクルが選択されるとしてパーティクルの数だけ復元抽出を行い、新たなパーティクル集合を生成する生成ステップと、をさらに具備することを特徴とする請求項１または請求項２に記載の行動予測方法。
【請求項７】
コンピュータを、請求項１から請求項３のいずれか１項に記載の行動予測装置の各手段として実行させるためのプログラム。
【請求項１】
開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測装置であって、
第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定手段と、
パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算手段と、
複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力手段と、を具備することを特徴とする行動予測装置。
【請求項２】
前記計算手段は、前記第２重みスコアとして、下記ｗ’（ｉ）
【数１】
を計算し、ｉはパーティクルのインデックスであり、全ての過去の前記位置情報履歴に含まれるデータの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、ｔｄが過去の所在時刻、ベクトルｘｄが該所在時刻での所在位置、およびベクトルｖｄが該所在時刻および該所在位置での所在速度を示し、ベクトルｖｓは開始時刻での速度であり、θ１、θ２はある値を有するパラメータであり、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、
【数２】
であることを特徴とする請求項１に記載の行動予測装置。
【請求項３】
前記第２時刻での複数のパーティクルの位置が前記目的位置からしきい値距離以内にあると見なせる場合には該第２時刻を目標到達時刻と判定し、しきい値距離以内にあると見なせない場合には第２時刻を現在時刻として、前記計算手段が計算した第２位置および第２速度をそれぞれ現在位置および現在速度として前記計算手段に第２時刻よりも未来の第３時刻での第３位置、第３速度、および第３重みスコアを計算させる判定手段と、
第３位置、第３速度、および第３重みスコアを有する全てのパーティクル集合から、パーティクルごとに算出される確率である（対応する第３重みスコア）／（全てのパーティクルについての第３重みスコアの和）で該パーティクルが選択されるとしてパーティクルの数だけ復元抽出を行い、新たなパーティクル集合を生成する生成手段と、をさらに具備することを特徴とする請求項１または請求項２に記載の行動予測装置。
【請求項４】
開始時刻と、該時刻での開始位置から目的地の目的位置までユーザが移動する場合にユーザの位置および時刻を推測する行動予測方法であって、
第１時刻と、該第１時刻での第１位置と、該第１時刻および該第１位置での第１速度と、第１重みスコアとを含むパーティクルを複数個設定し、前記開始時刻での該複数のパーティクルの全ての重みスコアをゼロに設定し、複数のパーティクルの全ての位置、速度、および時刻をそれぞれ開始位置、開始位置での速度、および開始時刻に設定する設定ステップと、
パーティクルごとに、該パーティクルの現在位置および現在速度に基づいて未来の第２時刻での該パーティクルの第２位置を計算し、該パーティクルの現在速度を平均とする分布関数に基づいて第２時刻での該パーティクルの第２速度を計算し、第２時刻での複数のパーティクルのうち、ユーザに関する過去の所在時刻と、該所在時刻での所在位置と、該所在時刻および該所在位置での所在速度とを含む過去の位置情報履歴により近い値を有するパーティクルほどより高い値を有する第２重みスコアを計算する計算ステップと、
複数のパーティクルの分布密度が最も高い場所を第２時刻でのユーザの位置推測結果として出力する出力ステップと、を具備することを特徴とする行動予測方法。
【請求項５】
前記計算ステップでは、前記第２重みスコアとして、下記ｗ’（ｉ）
【数３】
を計算し、ｉはパーティクルのインデックスであり、全ての過去の前記位置情報履歴に含まれるデータの集合をＤとし、Ｄの各要素ｄ（ｄ∈Ｄ）はｄ＝＜ベクトルｘｄ，ベクトルｖｄ，ｔｄ＞として、ｔｄが過去の所在時刻、ベクトルｘｄが該所在時刻での所在位置、およびベクトルｖｄが該所在時刻および該所在位置での所在速度を示し、ベクトルｖｓは開始時刻での速度であり、θ１、θ２はある値を有するパラメータであり、ｓｉｍはコサイン類似度を［０，１］の区間に移した関数であり、
【数４】
であることを特徴とする請求項１に記載の行動予測方法。
【請求項６】
前記第２時刻での複数のパーティクルの位置が前記目的位置からしきい値距離以内にあると見なせる場合には該第２時刻を目標到達時刻と判定し、しきい値距離以内にあると見なせない場合には第２時刻を現在時刻として、前記計算ステップで計算した第２位置および第２速度をそれぞれ現在位置および現在速度として前記計算ステップで第２時刻よりも未来の第３時刻での第３位置、第３速度、および第３重みスコアを計算させる判定ステップと、
第３位置、第３速度、および第３重みスコアを有する全てのパーティクル集合から、パーティクルごとに算出される確率である（対応する第３重みスコア）／（全てのパーティクルについての第３重みスコアの和）で該パーティクルが選択されるとしてパーティクルの数だけ復元抽出を行い、新たなパーティクル集合を生成する生成ステップと、をさらに具備することを特徴とする請求項１または請求項２に記載の行動予測方法。
【請求項７】
コンピュータを、請求項１から請求項３のいずれか１項に記載の行動予測装置の各手段として実行させるためのプログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１１−１８００２５（Ｐ２０１１−１８００２５Ａ）
【公開日】平成２３年９月１５日（２０１１．９．１５）
【国際特許分類】
【出願番号】特願２０１０−４５７４５（Ｐ２０１０−４５７４５）
【出願日】平成２２年３月２日（２０１０．３．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月１５日（２０１１．９．１５）
【国際特許分類】
【出願日】平成２２年３月２日（２０１０．３．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]