行動経路推定方法及びプログラム
【課題】ユーザが通過する位置を確率分布で表すことで高精度の行動経路推定を可能にする。
【解決手段】地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに確率密度分布をp(xd)を用いた式(1)によりスコアを計算する。次に、上記スコアが計算された各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索する。
【解決手段】地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに確率密度分布をp(xd)を用いた式(1)によりスコアを計算する。次に、上記スコアが計算された各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索する。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、ユーザが携行する位置計測デバイスによって計測された位置データをもとに、当該ユーザの行動経路を推定する行動経路推定方法及びプログラムに関する。
【背景技術】
【0002】
近年、Global Positioning System(GPS)に代表される位置計測機能を備えた携帯端末が増加しており、この種の携帯端末により計測されるGPSデータを利用して当該携帯端末を携行するユーザの行動の規則性を抽出し、その結果をもとにユーザの行動予測を行う技術が提案されている。例えば、非特許文献1には、取得されたGPSデータをクラスタリングしてユーザが滞留した場所を抽出したのち、蓄積されたデータをもとに滞在場所間の移動を表すマルコフモデルを構築し、このマルコフモデルを用いて未来の滞留場所を予測する技術が記載されている。
【0003】
ユーザの行動を的確に予測できれば、ユーザに対しより有益な情報を提供することが可能となる。例えば、ユーザが会社にいるときにその帰宅経路を予測することで、予測された経路での災害情報や、経路途中に存在する店舗のタイムセール情報を前もって提供する等、一歩先を読んだ情報提供が可能となる。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】Daniel Ashbrook and Thad Starner,“Using GPS to Learn Significant Locations and Predict Movement across Multiple Users”,Personal and Ubiquitous Computing 7(5),pp.275-286 (2003)
【発明の概要】
【発明が解決しようとする課題】
【0005】
ところが、上記従来の技術はユーザが将来滞留する場所を予測することはできるが、滞留場所が離散的に求まるのみで、その場所に到達するまでの途中経路については予測することができない。つまり、従来技術では、A地点にいるユーザがB地点に向かうことについては知ることができるが、A地点からB地点に向かう際に利用する経路については知ることができない。
【0006】
一方、途中の経路を推測する手法として、線形補間やラグランジュ補間のような既存のデータ補間法を用いることが考えられる。しかし、単純にデータ補間を行っただけでは道路や鉄道等の地理的な制約が考慮されないため、予測された途中経路は正確さに欠けたものとなる。
【0007】
この発明は上記事情に着目してなされたもので、その目的とするところは、ユーザが通過する位置を小領域ごとに確率分布で表すことで高精度の行動経路推定を可能にした行動経路推定方法及びプログラムを提供することにある。
【課題を解決するための手段】
【0008】
上記目的を達成するためにこの発明の第1の観点は、ユーザが所持する携帯端末から当該ユーザの位置データを受信して、この受信された位置データの集合を記憶媒体に記憶しておく。この状態で、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲を複数の小領域に分割する。そして、上記記憶媒体に記憶された位置データ集合に基づいて、上記分割された小領域ごとに当該小領域を上記ユーザが通過する確率を表すスコアを算出し、この算出されたスコアに基づいて上記補間対象区間の始点と終点との間の最適経路を算出するようにしたものである。具体的には、上記スコアを算出する際に、上記位置データ集合をZ、上記小領域dの集合をD、小領域の中心座標をxd 、xd の確率密度分布をp(xd)としたとき、スコアscore(d)を
【数1】
により算出する。
【0009】
したがって、この発明の第1の観点によれば、地図情報を反映した二次元空間上において、ユーザが通過する可能性の高さが小領域ごとに確率密度分布をp(xd)を用いたスコアとして算出され、このスコアをもとに補間対象区間の始点と終点との間の最適経路が算出される。このため、既存の線形補間やグランジュ補間を用いる場合に比べ、ユーザの行動経路を高精度に補間し推定することが可能となる。
【0010】
上記スコアを算出する方法としては、次の複数の方法を使用することが可能である。
第1の方法は、hをカーネルの広がりを定めるガウス分布の標準偏差とするとき、上記確率密度分布p(xd)を、
【数2】
により算出するものである。
【0011】
第2の方法は、上記記憶媒体に記憶された位置データ集合に含まれる位置データの各々に、座標値の計測誤差に関する情報が付加されている場合に、hをカーネルの広がりを定めるガウス分布の標準偏差とし、かつ上記誤差をωi 、当該ωi の上記ガウス分布の標準偏差hに対する影響を調整するためのパラメータをλとしたとき、上記確率密度分布p(xd)を、
【数3】
により算出するものである。
このようにすると、位置データに含まれる座標値の誤差の大きさに応じてガウス分布の標準偏差を大きくすることができ、これにより位置データの誤差を考慮して確率密度分布p(xd)を算出することが可能となる。
【0012】
第3の方法は、上記記憶媒体に記憶された位置データ集合Zの中の点xi について、xi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルui^、vi^をそれぞれ
【数4】
と定義し、Iを2×2の単位行列、σを分散共分散行列の等方性を調整するためのパラメータとし、上記単位ベクトルui^、vi^を用いて2×2の分散共分散行列Σi を
【数5】
と定義し、さらに2×2の分散共分散行列Σi^を
【数6】
により表したとき、上記確率密度分布p(xd)を、
【数7】
により算出するものである。
このようにすると、ユーザの移動方向の標準偏差がユーザの移動方向と直交する方向の標準偏差に対し大きく設定される。したがって、各観測点xi が確率密度分布に与える影響がどの方向についても一定であると仮定せずに、過去にユーザが移動していた方向を利用して、確率密度分布に与える影響の向きを変化させることが可能となる。
【0013】
第4の方法は、上記記憶媒体に記憶された位置データ集合から、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除処理後に残った位置データの集合をもとにスコアを算出するものである。
一般に、記憶された位置データ集合に、ユーザがある場所に長時間滞留したときのデータが含まれていると、カーネル密度分布によって推定される確率密度分布のスコアがその場所でのみ極端に大きくなり、スコアに偏りが生じる。そこで、上記したように隣接する2点間の距離がしきい値以下となる点の位置データを事前に削除しておくことで、上記したようなスコアの偏りを防止することが可能となる。
【0014】
この発明の第2の観点は、最適経路を算出する際に、上記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ上記各ノードに上記小領域ごとに算出されたスコアを反映させた重み付きグラフを作成し、この作成された重み付きグラフに対しダイクストラ法を適用することにより、スコアを最小とする小領域をつないだ小領域列を補間経路として算出するものである。
このようにすると、小領域ごとのスコアを考慮した最適経路を、ダイクストラ法によって効率よく求めることが可能となる。
【0015】
この発明の第3の観点は、上記スコアの算出過程及び最適経路の算出過程に、上記経路探索範囲を第1のサイズからなる複数の小領域に分割し、これらの小領域に対して補間経路の候補を算出する第1の過程と、上記第1の過程により算出された補間経路の候補に対応する小領域とその周辺領域を含む限定された経路探索範囲を上記第1のサイズより小さい第2のサイズからなる複数の小領域に分割し、これらの小領域に対し補間経路の候補を算出する第2の過程とを備える。そして、この第2の過程を、上記小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら少なくとも1回実行するようにしたものである。
【0016】
一般に、経路探索の処理にかかる計算量と、得られる補間経路の精度とはトレードオフの関係にある。すなわち、1つひとつの小領域のサイズを大きく設定すると処理にかかる計算量は小さくてすむが、得られる補間経路の精度は粗くなる。一方、小領域のサイズを小さく設定すると得られる補間経路は精細なものとなるが、計算量は増大する。そこで、上記したように最初は小領域のサイズを大きなサイズ(第1のサイズ)に設定して補間経路を求め、次にこの求められた補間経路とその周辺領域を対象とする限定範囲について小さいサイズ(第2のサイズ)の小領域を設定して補間経路を求める。そして、小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら上記補間経路を求める処理を繰り返す。このようにすることで、比較的少ない計算量で精細な補間経路を求めることが可能となる。
【発明の効果】
【0017】
すなわちこの発明によれば、ユーザが通過する位置を小領域ごとにその確率分布で表すことで高精度の行動経路推定を可能にした行動経路推定方法及びプログラムを提供することができる。
【図面の簡単な説明】
【0018】
【図1】この発明の第1の実施形態に係わる行動経路推定装置を備えたシステムの概略構成図。
【図2】図1に示したシステムに設けられる行動経路推定装置の機能構成を示すブロック図。
【図3】ユーザ端末から取得される位置データの一例を示す図。
【図4】図2に示した行動経路推定装置による全体の処理手順と処理内容を示すフローチャート。
【図5】図4に示した全体の処理手順のうち位置スコア計算処理の手順と処理内容を示すフローチャート。
【図6】図5に示した位置スコア計算処理による探索範囲と矩形領域への分割処理の概念を示す図。
【図7】図5に示した位置スコア計算処理による確率スコアの計算結果の一例を示す図。
【図8】位置データ選択処理の手順と処理内容を示すフローチャート。
【図9】小領域とグラフとの対応関係を示す図。
【図10】最適経路計算処理の手順と処理内容を示すフローチャート。
【図11】補間経路の概念を示す図。
【図12】この発明の第2の実施形態に係る行動経路推定装置による段階的な経路補間処理の手順と処理内容を示すフローチャート。
【図13】段階的な経路補間処理の概念を示す図。
【発明を実施するための形態】
【0019】
以下、図面を参照してこの発明に係わる実施形態を説明する。
(第1の実施形態)
図1は、この発明の第1の実施形態に係わる行動経路推定装置を備えたシステムを示す図である。このシステムは、ユーザが所持する複数の携帯端末MS1〜MSnと行動経路推定装置SVとの間を通信ネットワークNWを介して接続し、携帯端末MS1〜MSnの位置データを行動経路推定装置SVに収集可能としたものである。
【0020】
通信ネットワークNWは、IP(Internet Protocol)網と、このIP網にアクセスするためのアクセス網とから構成される。アクセス網としては、公衆通信網、携帯電話網、LAN(Local Area Network)、無線LAN、CATV(Cable Television)網等が用いられる。
【0021】
携帯端末MS1〜MSnは、例えば携帯電話機やPDA(Personal Digital Assistant)、スマートホン、ネットブック等と呼ばれる携帯型のパーソナル・コンピュータからなり、音声通信機能やメール送受信機能、ブラウザ機能に加えて、位置計測機能を備えている。位置計測機能は、GPS(Global Positioning System)受信機と、GPS計測制御部と、GPSデータ送信制御部とにより実現される。
【0022】
GPS受信機は、図示しない複数のGPS衛星から送信されるGPS信号をアンテナを介して受信する。GPS計測制御部は、予め定められた計測周期で上記GPS受信機を起動し、当該GPS受信機により受信されたGPS信号を取り込んで自端末の位置データを生成する。位置データzi は、計測IDをi とするとき、この計測IDi と、経度xi と、緯度yi と、計測時刻ti とからなる4つの要素で表される。
【0023】
なお、GPS計測制御部によっては、経度xi 及び緯度yiの座標データのほかに、計測された座標値の精度に関するデータを得る機能を有するものがある。例えばGPSデータに対しては、測位時に水平方向の誤差(Horizontal Dilution of Precision;HDOP)を得ることができる。このような誤差データが得られた場合には、zi =(xi,yi,wi,ti)とする。wiは誤差の半径を示す。以上のように生成された位置データzi は、携帯端末内の記憶部に記憶される。
【0024】
GPSデータ送信制御部は、行動経路推定装置SVから位置データの送信要求が到来した場合に、上記記憶部に記憶された位置データzi を読み出して要求元の行動経路推定装置SVに向け送信する。なお、位置データzi は、定期的又は自端末の緯度経度が一定量以上変化したときに、記憶部から読み出して行動経路推定装置SVへ送信するようにしてもよい。
【0025】
さて、行動経路推定装置SVは、例えば通信事業者又はサービス事業者が運用するサービスサーバからなり、次のように構成される。図2はその機能構成を示すブロック図である。
すなわち、行動経路推定装置SVは、送受信ユニット1と、制御ユニット2と、記憶ユニット3とを備えている。送受信ユニット1は、制御ユニット2の制御の下で通信ネットワークNWとの間で情報の送受信を行う。
【0026】
記憶ユニット3は、HDD(Hard Disc Drive)又はSSD(Solid State Drive)を使用したランダムアクセス可能な不揮発性メモリを使用したもので、この発明を実現するために必要な記憶部として、位置データ記憶部31を備えている。
位置データ記憶部31は、上記携帯端末MS1〜MSnから取得した過去の一定期間分の位置データzi を位置データ集合Z={z1,z2,…,zN}として記憶するために用いられる。図3はこの位置データ記憶部31に記憶される位置データ集合の一例を示すもので、個々の位置データは先に述べたように計測IDiと、経度xi と、緯度yi と、計測時刻ti とからなる4つの要素で表される。
【0027】
制御ユニット2は、中央処理ユニット(CPU;Central Processing Unit)を中核として備えるもので、この発明を実施するために必要な制御機能として、位置データ収集制御部21と、スコア算出処理部22と、経路計算処理部23と、補間経路出力部24とを備えている。これらの制御機能はいずれもアプリケーション・プログラムを上記CPUに実行させることにより実現される。
【0028】
位置データ収集処理部21は、送受信ユニット1を制御することで、各携帯端末MS1〜MSnに対しそれぞれ異なるタイミングで定期的に位置データの送信要求を送信し、この要求に対し各携帯端末MS1〜MSnから送信される位置データを受信する。そして、この受信された位置データを上記位置データ記憶部31に記憶させる処理を行う。
【0029】
スコア算出処理部22は、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、上記位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに当該小領域をユーザが通過する確率を表すスコアを計算する処理を実行する。
【0030】
経路計算処理部23は、上記スコア算出処理部22によりスコアを計算した各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索する処理を行う。
【0031】
補間経路出力部24は、上記経路計算処理部23により計算された補間経路を表す情報をもとに、地図上に最適行動経路を表示した経路案内情報を作成する。そして、この作成された経路案内情報を、送受信ユニット1から該当する携帯端末MS1〜MSnへ向けて送信させる処理を実行する。
【0032】
次に、以上のように構成された行動経路推定装置SVによる行動経路推定処理動作を説明する。図4はその全体の処理手順と処理内容を示すフローチャートである。
(1)位置データの収集
制御ユニット2は、位置データ収集処理部21の制御の下で、先ずステップS1により各携帯端末MS1〜MSnに対しそれぞれ異なるタイミングで定期的に位置データの送信要求を送信し、この要求に対し各携帯端末MS1〜MSnから送信される位置データを送受信ユニット1で受信する。そして、この受信された位置データをステップS2で制御ユニット2に取り込み、この取り込んだ位置データをステップS3により位置データ記憶部31に記憶させる。各位置データzi は、計測IDをi とするとき、この計測IDi と、経度xi と、緯度yi と、計測時刻ti とから構成される。このとき位置データZi は、zi =(xi,yi,ti)と表される。
なお、一般にGPS受信機は測位時に水平方向の誤差(Horizontal Dilution of Precision;HDOP)を得ることができ、この誤差も位置データに付加される。この場合位置データzi は、zi =(xi,yi,ωi,ti)と表される。ωiは誤差の半径を示す。
以下、xi,yiの組について、二次元ベクトルxiを用いてxi=(xi,yi)とも書く。
【0033】
位置データ収集処理部21は、以上の位置データ収集処理を、所定の期間(例えば1ヶ月から1年)に渡り一定の時間間隔(例えば1分間隔)で実施する。この結果、位置データ記憶部31には位置データの集合がユーザの行動履歴として蓄積される。
(2)補間対象データの特定
制御ユニット2は、続いてスコア算出処理部22の制御の下で、補間対象データを特定する処理を行う。すなわち、ステップS4において、補間の対象となる2つの座標x(s) ,x(e) を特定する。この座標値はユーザが手動で入力してもよいし、スコア算出処理部22が蓄積された位置データ集合Zの中から選択してもよい。このとき、x(s) を補間処理の始点、x(e) を補間処理の終点とそれぞれ定義し、この2点間の軌跡を求める処理を補間処理と定義する。この特定された補間処理の始点x(s) 及び補間処理の終点x(e) を表す情報は、記憶ユニット3内の制御データ一時記憶部(図示せず)に保存される。
【0034】
(3)位置スコアの計算
制御ユニット2は、次にステップS4により、スコア算出処理部22の制御の下で位置スコアの算出処理を以下のように実行する。図5はその処理手順と処理内容の概要を示すフローチャートである。
【0035】
すなわち、スコア算出処理部22は先ずステップ11により、上記特定された補間処理の始点x(s) 及び補間処理の終点x(e) を表す情報を記憶ユニット3から読み込み、続いてステップS12において経路探索範囲Uを設定する。経路探索範囲Uは、上記補間処理の始点x(s) 及び補間処理の終点x(e) を含み、かつこれらの始点x(s) から終点x(e)への正しい経路が存在する可能性のある領域とする。例えば、始点x(s) と終点x(e)を含む矩形領域のうち、各辺と始点x(s) 及び終点x(e) との距離がある一定値以上のものとする。なお、経路探索範囲Uの形状は任意とする。
【0036】
スコア算出処理部22は、次にステップS13において、上記設定された経路探索範囲Uを矩形をなす複数の小領域に分割する。矩形領域への分割は、経路探索範囲Uが矩形領域であるならば、その各辺に平行な方向に適当な分割数で分割することにより行われる。例えば、各辺に平行にそれぞれn分割、m分割すれば、n×m個の矩形の小領域が得られる。矩形小領域の集合をDとすると、経路探索範囲Dに含まれる小領域dの和集合を意味する∪d∈Dd=Uのとき、d, d’∈Dかつd ≠d’ならばd ∩d’≠0を満たすとする。図6に、この経路探索範囲Uと小領域の分割の一例を示す。同図において、外側の太い線で囲まれた領域が探索範囲U、内側の点線で囲まれた小さな領域ひとつひとつが分割された矩形領域に対応する。
【0037】
スコア算出処理部22は、次にステップS14において、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとに基づいて、上記分割された小領域ごとに以下のようにスコアを計算する。
【0038】
すなわち、いま小領域d∈Dの中心座標をxd とすると、スコアscore(d)は
【数8】
により計算される。
【0039】
ここで、p(xd)はカーネル密度推定によって求められるx
D における確率密度分布であり、
【数9】
として与えられる。
【0040】
ここで、hはガウス分布の標準偏差であり、カーネルの広がりを定める。hは処理に先立ってあらかじめ設定される。なお、位置データにHDOP等の誤差データが付加されている場合は、この誤差データを利用して上記確率密度分布p(xd)を、
【数10】
としてもよい。ここで、λは上記ガウス分布の標準偏差hに対する上記誤差ωi の影響を調整するためのパラメータであり、処理に先立ってあらかじめ設定される。
【0041】
ところで、上記式(2)では、各観測点xiが密度分布に与える影響がどの方向についても一定であると仮定した。しかし、過去に取得された位置データからユーザが移動していた方向が判明している場合には、このデータを利用して確率密度分布に与える影響の向きを変化させることが可能である。以下のその手法について述べる。
【0042】
すなわち、先ず位置データ集合Z中の点xi について、
【数11】
と定義する。
【0043】
ここで、ui^,vi^はそれぞれxi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルである。これらの単位ベクトルui^,vi^を用いて、2×2の分散共分散行列を
【数12】
と定義する。
【0044】
ここで、Iは2×2の単位行列、σは分散共分散行列の等方性を調整するためのパラメータであり、いずれも処理に先立って設定される。σは、ユーザ位置を中心とした楕円の半径で標準偏差を表すとき、ユーザの移動方向を楕円の長辺、それと直交する方向を楕円の短辺として、その両者の長さの比を調整するパラメータである。すなわち、σを大きくするほど、標準偏差を表す楕円は円に近づく。
【0045】
分散共分散行列Σi を用いることで、上記式(2)を
【数13】
として再定義する。
【0046】
ここでΣi^は2×2の分散共分散行列であり、
【数14】
と表される。なお、Iは2×2の単位行列、hはガウス分布の標準偏差である。
【0047】
被験者たるあるユーザが通勤時に携行したGPSデータ計測器によって取得されたGPSデータを収集して、各位置に対する確率密度p(x)を算出した結果の一例を図7に示す。同図において、横軸、縦軸はそれぞれ経度、緯度を表し、図中の色の濃さは位置に対応する小領域での確率密度を反映している。確率密度はパラメータhを適当な値に定めた式(2)によって算出されたものである。この計算結果から、ユーザが普段通過する場所に対して確率密度p(x)が高くなる様子が分かる。
【0048】
上記処理手順では、位置データ記憶部31に蓄積されているすべての位置データをスコア計算に用いた場合について述べた。しかし、蓄積されている位置データ中に、ユーザがある場所に長時間滞留したときのデータが含まれていると、カーネル密度分布によって推定される確率密度分布がその場所でのみ極端に大きくなり、スコアに偏りが生じる場合がある。
【0049】
このような課題は、新たな位置データ集合Z′を作成し、この新たな位置データ集合Z′に対しスコア計算行うことで解決できる。図8は上記新たな位置データ集合Z′を作成するための処理手順と処理内容を示すフローチャートである。なお、ここでは位置データの集合Zの要素{z1,z2,…,zN}に対し、t1<t2<…<tNが成り立っているものとして説明を行う。
【0050】
スコア算出処理部22は、先ずステップS21においてカウンタiを0に初期化する。次にステップS22において新たなデータの集合Z′を空集合とし定義し、ステップS23においてカウンタjを0に初期化する。そして、ステップS24においてiが集合の要素数Nを超えていないかどうかを確認し、超えていなければステップS25に移行する。ステップS25では、xi 及びxj の座標間の距離を求め、距離が予め設定した一定値以下であるか否かを判定する。この判定の結果、一定値以下ならばステップS26においてZ′をZ′∪{zi}に更新する。またそれと共に、ステップS27によりjをiの値に更新すると共に、ステップS28によりiの値をインクリメント(i=i+1)したのち、ステップS24に戻る。
以後、iがNになるまで上記ステップS24〜ステップS28の処理を繰り返す。そして、すべてのiについての処理が終了すると、上記ステップS26において最終的に得られたZ′出力して処理を終了する。
【0051】
このようにして生成された新たな位置データ集合Z′は、位置データ記憶部31に元々蓄積されていた位置データ集合Zの中で、隣接する点xi-1とxiとの距離が一定値以下だった場合にこれを除いたものとなる。したがって、この新たな位置データ集合Z′を使用してスコア計算を行うことで、ユーザが長期滞留している場所の位置データが多くなりすぎる不具合を解消できる。
【0052】
(4)スコアが最小となる経路の探索
上記スコア計算が終了すると、制御ユニット2はステップS6に移行してここで経路計算処理部23を起動し、この経路計算処理部23の制御の下で、以下のようにスコアが最小となる経路の探索処理を実行する。
【0053】
先ず、スコアを計算した矩形の小領域の集合d∈Dを重み付きグラフG=(V,E)に変換する。このグラフG=(V,E)は、各小領域dをそれぞれノードとし、これらのノードの隣接するもの同士をリンクで接続することにより作成される。ここで、V(G) はグラフのノードの集合であり、V(G)=Dである。E(G)はグラフのリンク集合である。図9は小領域とグラフとの対応関係を表す図であり、(a)が小領域の集合を、(b)がグラフを示している。また、v∈V(G)である各vに対し、開始点からvまでの累積スコア最小経路に対するスコアをl(v) と定義する。また、prev(v)を、ある点s∈V(G)からvまでのスコアが最小となる経路でvの直前のノードを指すポインタとする。
【0054】
以下、図10を用いて最適経路計算の処理を説明する。最適経路計算処理は、重み付きグラフG=(V,E)において最短経路を探索するダイクストラ法で実現できる。
先ずステップS31において、始点x(s) を含む小領域を探し、この小領域をsとする。次にステップS32において、スコアをl(s)=0,v∈V(G)\sであるvについて、l(v)=∞とする。なお、v∈V(G)\sは、「要素sを除く集合V(G)」に含まれる要素vを意味する。また、V(G)の部分集合Rを≠0に初期化する。
【0055】
次に、ステップS33において、vを端点に含むすべてのリンク(v,w)∈E(G)の端点w∈V(G)についてスコアを更新する。すなわち、l(w)>l(v)+score(w)ならばl(w)=l(v)+score(w)とし、prev(w)=vとおく。続いてステップS36において、RがV(G)と等しいか否かを判定し、R⊂V(G)であるならばステップS33に戻って上記ステップS33〜ステップS36の処理を繰り返す。
【0056】
これに対し、R=V(G)ならばステップS37に移行する。ステップS37では、終点x(e)を含む領域をeとする。ステップS38では、eからprev(e),prev(prev(e)),…としてsまでの経路を辿る。この処理により、sからeまでのスコアを最小とする経路を求めることができる。以上の処理により得られる最短経路は、図11に示すように通過する小領域を繋いだものとして表現される。
【0057】
(5)補間経路情報の出力
制御ユニット2は、上記ステップS6によるスコア最小経路計算が終了すると、次にステップS7に移行して補間経路出力部24を起動し、この補間経路出力部24の制御の下で補間経路を表す情報を出力する。例えば、上記経路計算処理部23により計算された補間経路を表す情報をもとに、地図上に最適行動経路を表示した経路案内情報を作成する。そして、この作成された経路案内情報を、送受信ユニット1から該当する携帯端末MS1〜MSnへ向けて送信させる。
【0058】
以上詳述したようにこの実施形態では、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに確率密度分布をp(xd)を用いた式(1)によりスコアを計算する。次に、上記スコアが計算された各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索するようにしている。
【0059】
したがって、地図情報を反映した二次元空間上において、ユーザが通過する可能性の高さが小領域ごとに確率密度分布をp(xd)を用いたスコアとして算出され、このスコアをもとに補間対象区間の始点と終点との間の最適経路が算出される。このため、既存の線形補間やグランジュ補間を用いる場合に比べ、ユーザの行動経路を高精度に補間し推定することが可能となる。
【0060】
上記スコアの計算に使用する確率密度分布p(xd)の計算には、式(2)、式(3)及び式(7)のいずれかを使用できる。特に、式(3)を用いると、位置データに含まれる座標値の誤差の大きさに応じてガウス分布の標準偏差を大きくすることができ、これにより位置データの誤差を考慮して確率密度分布p(xd)を算出することが可能となる。また、式(7)を用いると、ユーザの移動方向の標準偏差がユーザの移動方向と直交する方向の標準偏差に対し大きく設定される。したがって、各観測点xi が確率密度分布に与える影響がどの方向についても一定であると仮定せずに、過去にユーザが移動していた方向を利用して、確率密度分布に与える影響の向きを変化させることが可能となる。
【0061】
また、スコア計算に先立ち、位置データ記憶部31に記憶された位置データ集合Zから、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除処理後に残った位置データの集合Z′をもとにスコアを算出するようにしている。
このようにすると、ユーザが特定の場所に長時間滞留した場合に、当該場所の位置データが間引きして、スコアの偏りを防止することが可能となる。
【0062】
さらに第1の実施形態では、最適経路を算出する際に、上記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ上記各ノードに上記小領域ごとに算出されたスコアを反映させた重み付きグラフG=(V,E)を作成し、この作成された重み付きグラフG=(V,E)に対しダイクストラ法を適用して、スコアを最小とする小領域をつないだ小領域列を補間経路として算出するようにしている。
したがって、小領域ごとにスコアを算出する方法を採用しているにもかかわらず、ダイクストラ法をそのまま適用して最適経路を探索することが可能となる。
【0063】
(第2の実施形態)
この発明の第2の実施形態は、スコアを算出しさらに最適経路を算出する際に、最初は経路探索範囲を比較的大きいサイズの小領域に分割してスコア計算と補間経路の探索処理を行い、以後小領域のサイズを段階的に小さくしながらスコア計算と補間経路の探索処理を繰り返し行うことにより補間経路を表す小領域を絞り込むようにしたものである。
図12はこの発明の第2の実施形態に係わる行動経路推定装置による行動経路推定処理の手順と処理内容を示すフローチャートである。なお、同図において前記図4と同一部分には同一符号を付して詳しい説明は省略する。
【0064】
スコア算出処理部22は、ステップS5において1回目のスコア計算を行う際に、探索経路範囲Uを比較的大きい第1のサイズの小領域に分割し、この第1のサイズの小領域についてスコアを計算する。経路計算処理部23は、ステップS6において、上記第1のサイズの小領域について得られたスコアをもとにスコアが最小となる小領域のつながりからなる補間経路の候補として求める。図13(a)はこの第1のサイズの小領域に対し得られた補間経路候補の一例を示すものである。
【0065】
上記補間経路の候補が得られると、制御ユニット2はステップS41において、上記設定した小領域のサイズが予め設定された基準サイズ以下であるか否かを判定する。基準サイズは、補間経路に要求される精度を満足する必要最低限の小領域サイズに設定される。上記判定の結果、小領域のサイズがまだ基準サイズ以下になっていなければ、制御ユニット2はステップS42に移行する。そして、このステップS42において、上記ステップS6によるスコア最小経路計算処理で得られた補間経路の候補に対応する小領域とその周辺の隣接小領域を新たな限定された経路探索範囲とし、ステップS5による位置スコア計算処理に2回目のスコア計算処理を行わせる。
【0066】
位置スコア計算処理は、2回目のスコア計算処理を実行するに当たり、小領域のサイズを上記第1のサイズより一定量小さい第2のサイズに変更する。そして、上記ステップS542の処理により限定された経路探索範囲を上記第2のサイズの小領域に分割し、この第2のサイズの小領域についてスコアを計算する。経路計算処理部23は、上記第2のサイズの小領域について得られたスコアをもとにスコアが最小となる補間経路の候補を求める。
【0067】
そして、制御ユニット2はステップS41において、上記設定した小領域のサイズが予め設定された基準サイズ以下であるか否かを判定する。そして、小領域のサイズがまだ基準サイズ以下になっていなければ、ステップS42において、経路探索範囲を上記2回目の経路計算処理で得られた補間経路の候補を含む小領域とその隣接小領域に限定し、ステップS5による位置スコア計算処理に3回目のスコア計算処理を行わせる。
【0068】
以後同様に、上記位置スコア計算処理において設定される小領域のサイズが基準サイズ以下と判定されるまで、上記ステップS5〜ステップS42による処理が繰り替えし行われる。そして、小領域のサイズが基準サイズ以下になると、制御ユニット2は最後の補間経路計算処理により得られた補間経路の候補を探索結果として携帯端末へ送信する。図13(b)は小領域のサイズが基準サイズ以下になったときの小領域のサイズの一例を、また図13(c)は当該サイズの小領域について得られた補間経路候補の例を示すものである。
【0069】
以上述べたように第2の実施形態によれば次のような効果が奏せられる。すなわち、1つひとつの小領域のサイズを大きく設定すると処理にかかる計算量は小さくてすむが、得られる補間経路の精度は粗くなる。一方、小領域のサイズを小さく設定すると得られる補間経路は精細なものとなるが、計算量は増大する。つまり、経路探索の処理にかかる計算量と得られる補間経路の精度とはトレードオフの関係にある。
そこで、第2の実施形態のように小領域のサイズを最初は大きなサイズ(第1のサイズ)に設定して補間経路の候補を求め、以後探索経路範囲を限定しかつ小領域のサイズを段階的に小さくしながら補間経路の候補を探索することによって、比較的少ない計算量で精細な補間経路を求めることが可能となる。
【0070】
(その他の実施形態)
なお、この発明は上記実施形態に限定されるものではない。例えば、前記実施形態では例えばWebサーバにより構成される行動経路推定装置SVにおいてユーザの行動経路を推定するようにした。しかし、それに限定されるものではなく、携帯端末MS1〜MSnに行動経路推定処理機能を持たせるようにしてもよい。
その他、行動経路推定装置の構成、行動経路推定処理の手順と処理内容等についても、この発明の要旨を逸脱しない範囲で種々変形して実施可能である。
【0071】
要するにこの発明は、上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【0072】
MS1〜MSn…携帯端末、SV…行動経路推定装置、NW…通信ネットワーク、1…送受信ユニット、2…制御ユニット、3…記憶ユニット、21…位置データ収集処理部、22…スコア算出処理部、23…経路計算処理部、24…補間経路出力部、31…位置データ記憶部。
【技術分野】
【0001】
この発明は、ユーザが携行する位置計測デバイスによって計測された位置データをもとに、当該ユーザの行動経路を推定する行動経路推定方法及びプログラムに関する。
【背景技術】
【0002】
近年、Global Positioning System(GPS)に代表される位置計測機能を備えた携帯端末が増加しており、この種の携帯端末により計測されるGPSデータを利用して当該携帯端末を携行するユーザの行動の規則性を抽出し、その結果をもとにユーザの行動予測を行う技術が提案されている。例えば、非特許文献1には、取得されたGPSデータをクラスタリングしてユーザが滞留した場所を抽出したのち、蓄積されたデータをもとに滞在場所間の移動を表すマルコフモデルを構築し、このマルコフモデルを用いて未来の滞留場所を予測する技術が記載されている。
【0003】
ユーザの行動を的確に予測できれば、ユーザに対しより有益な情報を提供することが可能となる。例えば、ユーザが会社にいるときにその帰宅経路を予測することで、予測された経路での災害情報や、経路途中に存在する店舗のタイムセール情報を前もって提供する等、一歩先を読んだ情報提供が可能となる。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】Daniel Ashbrook and Thad Starner,“Using GPS to Learn Significant Locations and Predict Movement across Multiple Users”,Personal and Ubiquitous Computing 7(5),pp.275-286 (2003)
【発明の概要】
【発明が解決しようとする課題】
【0005】
ところが、上記従来の技術はユーザが将来滞留する場所を予測することはできるが、滞留場所が離散的に求まるのみで、その場所に到達するまでの途中経路については予測することができない。つまり、従来技術では、A地点にいるユーザがB地点に向かうことについては知ることができるが、A地点からB地点に向かう際に利用する経路については知ることができない。
【0006】
一方、途中の経路を推測する手法として、線形補間やラグランジュ補間のような既存のデータ補間法を用いることが考えられる。しかし、単純にデータ補間を行っただけでは道路や鉄道等の地理的な制約が考慮されないため、予測された途中経路は正確さに欠けたものとなる。
【0007】
この発明は上記事情に着目してなされたもので、その目的とするところは、ユーザが通過する位置を小領域ごとに確率分布で表すことで高精度の行動経路推定を可能にした行動経路推定方法及びプログラムを提供することにある。
【課題を解決するための手段】
【0008】
上記目的を達成するためにこの発明の第1の観点は、ユーザが所持する携帯端末から当該ユーザの位置データを受信して、この受信された位置データの集合を記憶媒体に記憶しておく。この状態で、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲を複数の小領域に分割する。そして、上記記憶媒体に記憶された位置データ集合に基づいて、上記分割された小領域ごとに当該小領域を上記ユーザが通過する確率を表すスコアを算出し、この算出されたスコアに基づいて上記補間対象区間の始点と終点との間の最適経路を算出するようにしたものである。具体的には、上記スコアを算出する際に、上記位置データ集合をZ、上記小領域dの集合をD、小領域の中心座標をxd 、xd の確率密度分布をp(xd)としたとき、スコアscore(d)を
【数1】
により算出する。
【0009】
したがって、この発明の第1の観点によれば、地図情報を反映した二次元空間上において、ユーザが通過する可能性の高さが小領域ごとに確率密度分布をp(xd)を用いたスコアとして算出され、このスコアをもとに補間対象区間の始点と終点との間の最適経路が算出される。このため、既存の線形補間やグランジュ補間を用いる場合に比べ、ユーザの行動経路を高精度に補間し推定することが可能となる。
【0010】
上記スコアを算出する方法としては、次の複数の方法を使用することが可能である。
第1の方法は、hをカーネルの広がりを定めるガウス分布の標準偏差とするとき、上記確率密度分布p(xd)を、
【数2】
により算出するものである。
【0011】
第2の方法は、上記記憶媒体に記憶された位置データ集合に含まれる位置データの各々に、座標値の計測誤差に関する情報が付加されている場合に、hをカーネルの広がりを定めるガウス分布の標準偏差とし、かつ上記誤差をωi 、当該ωi の上記ガウス分布の標準偏差hに対する影響を調整するためのパラメータをλとしたとき、上記確率密度分布p(xd)を、
【数3】
により算出するものである。
このようにすると、位置データに含まれる座標値の誤差の大きさに応じてガウス分布の標準偏差を大きくすることができ、これにより位置データの誤差を考慮して確率密度分布p(xd)を算出することが可能となる。
【0012】
第3の方法は、上記記憶媒体に記憶された位置データ集合Zの中の点xi について、xi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルui^、vi^をそれぞれ
【数4】
と定義し、Iを2×2の単位行列、σを分散共分散行列の等方性を調整するためのパラメータとし、上記単位ベクトルui^、vi^を用いて2×2の分散共分散行列Σi を
【数5】
と定義し、さらに2×2の分散共分散行列Σi^を
【数6】
により表したとき、上記確率密度分布p(xd)を、
【数7】
により算出するものである。
このようにすると、ユーザの移動方向の標準偏差がユーザの移動方向と直交する方向の標準偏差に対し大きく設定される。したがって、各観測点xi が確率密度分布に与える影響がどの方向についても一定であると仮定せずに、過去にユーザが移動していた方向を利用して、確率密度分布に与える影響の向きを変化させることが可能となる。
【0013】
第4の方法は、上記記憶媒体に記憶された位置データ集合から、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除処理後に残った位置データの集合をもとにスコアを算出するものである。
一般に、記憶された位置データ集合に、ユーザがある場所に長時間滞留したときのデータが含まれていると、カーネル密度分布によって推定される確率密度分布のスコアがその場所でのみ極端に大きくなり、スコアに偏りが生じる。そこで、上記したように隣接する2点間の距離がしきい値以下となる点の位置データを事前に削除しておくことで、上記したようなスコアの偏りを防止することが可能となる。
【0014】
この発明の第2の観点は、最適経路を算出する際に、上記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ上記各ノードに上記小領域ごとに算出されたスコアを反映させた重み付きグラフを作成し、この作成された重み付きグラフに対しダイクストラ法を適用することにより、スコアを最小とする小領域をつないだ小領域列を補間経路として算出するものである。
このようにすると、小領域ごとのスコアを考慮した最適経路を、ダイクストラ法によって効率よく求めることが可能となる。
【0015】
この発明の第3の観点は、上記スコアの算出過程及び最適経路の算出過程に、上記経路探索範囲を第1のサイズからなる複数の小領域に分割し、これらの小領域に対して補間経路の候補を算出する第1の過程と、上記第1の過程により算出された補間経路の候補に対応する小領域とその周辺領域を含む限定された経路探索範囲を上記第1のサイズより小さい第2のサイズからなる複数の小領域に分割し、これらの小領域に対し補間経路の候補を算出する第2の過程とを備える。そして、この第2の過程を、上記小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら少なくとも1回実行するようにしたものである。
【0016】
一般に、経路探索の処理にかかる計算量と、得られる補間経路の精度とはトレードオフの関係にある。すなわち、1つひとつの小領域のサイズを大きく設定すると処理にかかる計算量は小さくてすむが、得られる補間経路の精度は粗くなる。一方、小領域のサイズを小さく設定すると得られる補間経路は精細なものとなるが、計算量は増大する。そこで、上記したように最初は小領域のサイズを大きなサイズ(第1のサイズ)に設定して補間経路を求め、次にこの求められた補間経路とその周辺領域を対象とする限定範囲について小さいサイズ(第2のサイズ)の小領域を設定して補間経路を求める。そして、小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら上記補間経路を求める処理を繰り返す。このようにすることで、比較的少ない計算量で精細な補間経路を求めることが可能となる。
【発明の効果】
【0017】
すなわちこの発明によれば、ユーザが通過する位置を小領域ごとにその確率分布で表すことで高精度の行動経路推定を可能にした行動経路推定方法及びプログラムを提供することができる。
【図面の簡単な説明】
【0018】
【図1】この発明の第1の実施形態に係わる行動経路推定装置を備えたシステムの概略構成図。
【図2】図1に示したシステムに設けられる行動経路推定装置の機能構成を示すブロック図。
【図3】ユーザ端末から取得される位置データの一例を示す図。
【図4】図2に示した行動経路推定装置による全体の処理手順と処理内容を示すフローチャート。
【図5】図4に示した全体の処理手順のうち位置スコア計算処理の手順と処理内容を示すフローチャート。
【図6】図5に示した位置スコア計算処理による探索範囲と矩形領域への分割処理の概念を示す図。
【図7】図5に示した位置スコア計算処理による確率スコアの計算結果の一例を示す図。
【図8】位置データ選択処理の手順と処理内容を示すフローチャート。
【図9】小領域とグラフとの対応関係を示す図。
【図10】最適経路計算処理の手順と処理内容を示すフローチャート。
【図11】補間経路の概念を示す図。
【図12】この発明の第2の実施形態に係る行動経路推定装置による段階的な経路補間処理の手順と処理内容を示すフローチャート。
【図13】段階的な経路補間処理の概念を示す図。
【発明を実施するための形態】
【0019】
以下、図面を参照してこの発明に係わる実施形態を説明する。
(第1の実施形態)
図1は、この発明の第1の実施形態に係わる行動経路推定装置を備えたシステムを示す図である。このシステムは、ユーザが所持する複数の携帯端末MS1〜MSnと行動経路推定装置SVとの間を通信ネットワークNWを介して接続し、携帯端末MS1〜MSnの位置データを行動経路推定装置SVに収集可能としたものである。
【0020】
通信ネットワークNWは、IP(Internet Protocol)網と、このIP網にアクセスするためのアクセス網とから構成される。アクセス網としては、公衆通信網、携帯電話網、LAN(Local Area Network)、無線LAN、CATV(Cable Television)網等が用いられる。
【0021】
携帯端末MS1〜MSnは、例えば携帯電話機やPDA(Personal Digital Assistant)、スマートホン、ネットブック等と呼ばれる携帯型のパーソナル・コンピュータからなり、音声通信機能やメール送受信機能、ブラウザ機能に加えて、位置計測機能を備えている。位置計測機能は、GPS(Global Positioning System)受信機と、GPS計測制御部と、GPSデータ送信制御部とにより実現される。
【0022】
GPS受信機は、図示しない複数のGPS衛星から送信されるGPS信号をアンテナを介して受信する。GPS計測制御部は、予め定められた計測周期で上記GPS受信機を起動し、当該GPS受信機により受信されたGPS信号を取り込んで自端末の位置データを生成する。位置データzi は、計測IDをi とするとき、この計測IDi と、経度xi と、緯度yi と、計測時刻ti とからなる4つの要素で表される。
【0023】
なお、GPS計測制御部によっては、経度xi 及び緯度yiの座標データのほかに、計測された座標値の精度に関するデータを得る機能を有するものがある。例えばGPSデータに対しては、測位時に水平方向の誤差(Horizontal Dilution of Precision;HDOP)を得ることができる。このような誤差データが得られた場合には、zi =(xi,yi,wi,ti)とする。wiは誤差の半径を示す。以上のように生成された位置データzi は、携帯端末内の記憶部に記憶される。
【0024】
GPSデータ送信制御部は、行動経路推定装置SVから位置データの送信要求が到来した場合に、上記記憶部に記憶された位置データzi を読み出して要求元の行動経路推定装置SVに向け送信する。なお、位置データzi は、定期的又は自端末の緯度経度が一定量以上変化したときに、記憶部から読み出して行動経路推定装置SVへ送信するようにしてもよい。
【0025】
さて、行動経路推定装置SVは、例えば通信事業者又はサービス事業者が運用するサービスサーバからなり、次のように構成される。図2はその機能構成を示すブロック図である。
すなわち、行動経路推定装置SVは、送受信ユニット1と、制御ユニット2と、記憶ユニット3とを備えている。送受信ユニット1は、制御ユニット2の制御の下で通信ネットワークNWとの間で情報の送受信を行う。
【0026】
記憶ユニット3は、HDD(Hard Disc Drive)又はSSD(Solid State Drive)を使用したランダムアクセス可能な不揮発性メモリを使用したもので、この発明を実現するために必要な記憶部として、位置データ記憶部31を備えている。
位置データ記憶部31は、上記携帯端末MS1〜MSnから取得した過去の一定期間分の位置データzi を位置データ集合Z={z1,z2,…,zN}として記憶するために用いられる。図3はこの位置データ記憶部31に記憶される位置データ集合の一例を示すもので、個々の位置データは先に述べたように計測IDiと、経度xi と、緯度yi と、計測時刻ti とからなる4つの要素で表される。
【0027】
制御ユニット2は、中央処理ユニット(CPU;Central Processing Unit)を中核として備えるもので、この発明を実施するために必要な制御機能として、位置データ収集制御部21と、スコア算出処理部22と、経路計算処理部23と、補間経路出力部24とを備えている。これらの制御機能はいずれもアプリケーション・プログラムを上記CPUに実行させることにより実現される。
【0028】
位置データ収集処理部21は、送受信ユニット1を制御することで、各携帯端末MS1〜MSnに対しそれぞれ異なるタイミングで定期的に位置データの送信要求を送信し、この要求に対し各携帯端末MS1〜MSnから送信される位置データを受信する。そして、この受信された位置データを上記位置データ記憶部31に記憶させる処理を行う。
【0029】
スコア算出処理部22は、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、上記位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに当該小領域をユーザが通過する確率を表すスコアを計算する処理を実行する。
【0030】
経路計算処理部23は、上記スコア算出処理部22によりスコアを計算した各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索する処理を行う。
【0031】
補間経路出力部24は、上記経路計算処理部23により計算された補間経路を表す情報をもとに、地図上に最適行動経路を表示した経路案内情報を作成する。そして、この作成された経路案内情報を、送受信ユニット1から該当する携帯端末MS1〜MSnへ向けて送信させる処理を実行する。
【0032】
次に、以上のように構成された行動経路推定装置SVによる行動経路推定処理動作を説明する。図4はその全体の処理手順と処理内容を示すフローチャートである。
(1)位置データの収集
制御ユニット2は、位置データ収集処理部21の制御の下で、先ずステップS1により各携帯端末MS1〜MSnに対しそれぞれ異なるタイミングで定期的に位置データの送信要求を送信し、この要求に対し各携帯端末MS1〜MSnから送信される位置データを送受信ユニット1で受信する。そして、この受信された位置データをステップS2で制御ユニット2に取り込み、この取り込んだ位置データをステップS3により位置データ記憶部31に記憶させる。各位置データzi は、計測IDをi とするとき、この計測IDi と、経度xi と、緯度yi と、計測時刻ti とから構成される。このとき位置データZi は、zi =(xi,yi,ti)と表される。
なお、一般にGPS受信機は測位時に水平方向の誤差(Horizontal Dilution of Precision;HDOP)を得ることができ、この誤差も位置データに付加される。この場合位置データzi は、zi =(xi,yi,ωi,ti)と表される。ωiは誤差の半径を示す。
以下、xi,yiの組について、二次元ベクトルxiを用いてxi=(xi,yi)とも書く。
【0033】
位置データ収集処理部21は、以上の位置データ収集処理を、所定の期間(例えば1ヶ月から1年)に渡り一定の時間間隔(例えば1分間隔)で実施する。この結果、位置データ記憶部31には位置データの集合がユーザの行動履歴として蓄積される。
(2)補間対象データの特定
制御ユニット2は、続いてスコア算出処理部22の制御の下で、補間対象データを特定する処理を行う。すなわち、ステップS4において、補間の対象となる2つの座標x(s) ,x(e) を特定する。この座標値はユーザが手動で入力してもよいし、スコア算出処理部22が蓄積された位置データ集合Zの中から選択してもよい。このとき、x(s) を補間処理の始点、x(e) を補間処理の終点とそれぞれ定義し、この2点間の軌跡を求める処理を補間処理と定義する。この特定された補間処理の始点x(s) 及び補間処理の終点x(e) を表す情報は、記憶ユニット3内の制御データ一時記憶部(図示せず)に保存される。
【0034】
(3)位置スコアの計算
制御ユニット2は、次にステップS4により、スコア算出処理部22の制御の下で位置スコアの算出処理を以下のように実行する。図5はその処理手順と処理内容の概要を示すフローチャートである。
【0035】
すなわち、スコア算出処理部22は先ずステップ11により、上記特定された補間処理の始点x(s) 及び補間処理の終点x(e) を表す情報を記憶ユニット3から読み込み、続いてステップS12において経路探索範囲Uを設定する。経路探索範囲Uは、上記補間処理の始点x(s) 及び補間処理の終点x(e) を含み、かつこれらの始点x(s) から終点x(e)への正しい経路が存在する可能性のある領域とする。例えば、始点x(s) と終点x(e)を含む矩形領域のうち、各辺と始点x(s) 及び終点x(e) との距離がある一定値以上のものとする。なお、経路探索範囲Uの形状は任意とする。
【0036】
スコア算出処理部22は、次にステップS13において、上記設定された経路探索範囲Uを矩形をなす複数の小領域に分割する。矩形領域への分割は、経路探索範囲Uが矩形領域であるならば、その各辺に平行な方向に適当な分割数で分割することにより行われる。例えば、各辺に平行にそれぞれn分割、m分割すれば、n×m個の矩形の小領域が得られる。矩形小領域の集合をDとすると、経路探索範囲Dに含まれる小領域dの和集合を意味する∪d∈Dd=Uのとき、d, d’∈Dかつd ≠d’ならばd ∩d’≠0を満たすとする。図6に、この経路探索範囲Uと小領域の分割の一例を示す。同図において、外側の太い線で囲まれた領域が探索範囲U、内側の点線で囲まれた小さな領域ひとつひとつが分割された矩形領域に対応する。
【0037】
スコア算出処理部22は、次にステップS14において、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとに基づいて、上記分割された小領域ごとに以下のようにスコアを計算する。
【0038】
すなわち、いま小領域d∈Dの中心座標をxd とすると、スコアscore(d)は
【数8】
により計算される。
【0039】
ここで、p(xd)はカーネル密度推定によって求められるx
D における確率密度分布であり、
【数9】
として与えられる。
【0040】
ここで、hはガウス分布の標準偏差であり、カーネルの広がりを定める。hは処理に先立ってあらかじめ設定される。なお、位置データにHDOP等の誤差データが付加されている場合は、この誤差データを利用して上記確率密度分布p(xd)を、
【数10】
としてもよい。ここで、λは上記ガウス分布の標準偏差hに対する上記誤差ωi の影響を調整するためのパラメータであり、処理に先立ってあらかじめ設定される。
【0041】
ところで、上記式(2)では、各観測点xiが密度分布に与える影響がどの方向についても一定であると仮定した。しかし、過去に取得された位置データからユーザが移動していた方向が判明している場合には、このデータを利用して確率密度分布に与える影響の向きを変化させることが可能である。以下のその手法について述べる。
【0042】
すなわち、先ず位置データ集合Z中の点xi について、
【数11】
と定義する。
【0043】
ここで、ui^,vi^はそれぞれxi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルである。これらの単位ベクトルui^,vi^を用いて、2×2の分散共分散行列を
【数12】
と定義する。
【0044】
ここで、Iは2×2の単位行列、σは分散共分散行列の等方性を調整するためのパラメータであり、いずれも処理に先立って設定される。σは、ユーザ位置を中心とした楕円の半径で標準偏差を表すとき、ユーザの移動方向を楕円の長辺、それと直交する方向を楕円の短辺として、その両者の長さの比を調整するパラメータである。すなわち、σを大きくするほど、標準偏差を表す楕円は円に近づく。
【0045】
分散共分散行列Σi を用いることで、上記式(2)を
【数13】
として再定義する。
【0046】
ここでΣi^は2×2の分散共分散行列であり、
【数14】
と表される。なお、Iは2×2の単位行列、hはガウス分布の標準偏差である。
【0047】
被験者たるあるユーザが通勤時に携行したGPSデータ計測器によって取得されたGPSデータを収集して、各位置に対する確率密度p(x)を算出した結果の一例を図7に示す。同図において、横軸、縦軸はそれぞれ経度、緯度を表し、図中の色の濃さは位置に対応する小領域での確率密度を反映している。確率密度はパラメータhを適当な値に定めた式(2)によって算出されたものである。この計算結果から、ユーザが普段通過する場所に対して確率密度p(x)が高くなる様子が分かる。
【0048】
上記処理手順では、位置データ記憶部31に蓄積されているすべての位置データをスコア計算に用いた場合について述べた。しかし、蓄積されている位置データ中に、ユーザがある場所に長時間滞留したときのデータが含まれていると、カーネル密度分布によって推定される確率密度分布がその場所でのみ極端に大きくなり、スコアに偏りが生じる場合がある。
【0049】
このような課題は、新たな位置データ集合Z′を作成し、この新たな位置データ集合Z′に対しスコア計算行うことで解決できる。図8は上記新たな位置データ集合Z′を作成するための処理手順と処理内容を示すフローチャートである。なお、ここでは位置データの集合Zの要素{z1,z2,…,zN}に対し、t1<t2<…<tNが成り立っているものとして説明を行う。
【0050】
スコア算出処理部22は、先ずステップS21においてカウンタiを0に初期化する。次にステップS22において新たなデータの集合Z′を空集合とし定義し、ステップS23においてカウンタjを0に初期化する。そして、ステップS24においてiが集合の要素数Nを超えていないかどうかを確認し、超えていなければステップS25に移行する。ステップS25では、xi 及びxj の座標間の距離を求め、距離が予め設定した一定値以下であるか否かを判定する。この判定の結果、一定値以下ならばステップS26においてZ′をZ′∪{zi}に更新する。またそれと共に、ステップS27によりjをiの値に更新すると共に、ステップS28によりiの値をインクリメント(i=i+1)したのち、ステップS24に戻る。
以後、iがNになるまで上記ステップS24〜ステップS28の処理を繰り返す。そして、すべてのiについての処理が終了すると、上記ステップS26において最終的に得られたZ′出力して処理を終了する。
【0051】
このようにして生成された新たな位置データ集合Z′は、位置データ記憶部31に元々蓄積されていた位置データ集合Zの中で、隣接する点xi-1とxiとの距離が一定値以下だった場合にこれを除いたものとなる。したがって、この新たな位置データ集合Z′を使用してスコア計算を行うことで、ユーザが長期滞留している場所の位置データが多くなりすぎる不具合を解消できる。
【0052】
(4)スコアが最小となる経路の探索
上記スコア計算が終了すると、制御ユニット2はステップS6に移行してここで経路計算処理部23を起動し、この経路計算処理部23の制御の下で、以下のようにスコアが最小となる経路の探索処理を実行する。
【0053】
先ず、スコアを計算した矩形の小領域の集合d∈Dを重み付きグラフG=(V,E)に変換する。このグラフG=(V,E)は、各小領域dをそれぞれノードとし、これらのノードの隣接するもの同士をリンクで接続することにより作成される。ここで、V(G) はグラフのノードの集合であり、V(G)=Dである。E(G)はグラフのリンク集合である。図9は小領域とグラフとの対応関係を表す図であり、(a)が小領域の集合を、(b)がグラフを示している。また、v∈V(G)である各vに対し、開始点からvまでの累積スコア最小経路に対するスコアをl(v) と定義する。また、prev(v)を、ある点s∈V(G)からvまでのスコアが最小となる経路でvの直前のノードを指すポインタとする。
【0054】
以下、図10を用いて最適経路計算の処理を説明する。最適経路計算処理は、重み付きグラフG=(V,E)において最短経路を探索するダイクストラ法で実現できる。
先ずステップS31において、始点x(s) を含む小領域を探し、この小領域をsとする。次にステップS32において、スコアをl(s)=0,v∈V(G)\sであるvについて、l(v)=∞とする。なお、v∈V(G)\sは、「要素sを除く集合V(G)」に含まれる要素vを意味する。また、V(G)の部分集合Rを≠0に初期化する。
【0055】
次に、ステップS33において、vを端点に含むすべてのリンク(v,w)∈E(G)の端点w∈V(G)についてスコアを更新する。すなわち、l(w)>l(v)+score(w)ならばl(w)=l(v)+score(w)とし、prev(w)=vとおく。続いてステップS36において、RがV(G)と等しいか否かを判定し、R⊂V(G)であるならばステップS33に戻って上記ステップS33〜ステップS36の処理を繰り返す。
【0056】
これに対し、R=V(G)ならばステップS37に移行する。ステップS37では、終点x(e)を含む領域をeとする。ステップS38では、eからprev(e),prev(prev(e)),…としてsまでの経路を辿る。この処理により、sからeまでのスコアを最小とする経路を求めることができる。以上の処理により得られる最短経路は、図11に示すように通過する小領域を繋いだものとして表現される。
【0057】
(5)補間経路情報の出力
制御ユニット2は、上記ステップS6によるスコア最小経路計算が終了すると、次にステップS7に移行して補間経路出力部24を起動し、この補間経路出力部24の制御の下で補間経路を表す情報を出力する。例えば、上記経路計算処理部23により計算された補間経路を表す情報をもとに、地図上に最適行動経路を表示した経路案内情報を作成する。そして、この作成された経路案内情報を、送受信ユニット1から該当する携帯端末MS1〜MSnへ向けて送信させる。
【0058】
以上詳述したようにこの実施形態では、地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲Uを設定し、この経路探索範囲Uを矩形なす複数の小領域に分割する。そして、位置データ記憶部31に記憶された位置データ集合Zと、上記各小領域の位置を表す座標データとをもとに、上記分割された小領域ごとに確率密度分布をp(xd)を用いた式(1)によりスコアを計算する。次に、上記スコアが計算された各小領域をノードとしてこれらのノードをリンクで接続し、さらに上記各ノードにスコアを反映させた重み付きグラフを作成する。そして、この作成された重み付きグラフに対しダイクストラ法を適用し、始点から終点に至る経路のうちスコアが最小となる補間経路を探索するようにしている。
【0059】
したがって、地図情報を反映した二次元空間上において、ユーザが通過する可能性の高さが小領域ごとに確率密度分布をp(xd)を用いたスコアとして算出され、このスコアをもとに補間対象区間の始点と終点との間の最適経路が算出される。このため、既存の線形補間やグランジュ補間を用いる場合に比べ、ユーザの行動経路を高精度に補間し推定することが可能となる。
【0060】
上記スコアの計算に使用する確率密度分布p(xd)の計算には、式(2)、式(3)及び式(7)のいずれかを使用できる。特に、式(3)を用いると、位置データに含まれる座標値の誤差の大きさに応じてガウス分布の標準偏差を大きくすることができ、これにより位置データの誤差を考慮して確率密度分布p(xd)を算出することが可能となる。また、式(7)を用いると、ユーザの移動方向の標準偏差がユーザの移動方向と直交する方向の標準偏差に対し大きく設定される。したがって、各観測点xi が確率密度分布に与える影響がどの方向についても一定であると仮定せずに、過去にユーザが移動していた方向を利用して、確率密度分布に与える影響の向きを変化させることが可能となる。
【0061】
また、スコア計算に先立ち、位置データ記憶部31に記憶された位置データ集合Zから、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除処理後に残った位置データの集合Z′をもとにスコアを算出するようにしている。
このようにすると、ユーザが特定の場所に長時間滞留した場合に、当該場所の位置データが間引きして、スコアの偏りを防止することが可能となる。
【0062】
さらに第1の実施形態では、最適経路を算出する際に、上記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ上記各ノードに上記小領域ごとに算出されたスコアを反映させた重み付きグラフG=(V,E)を作成し、この作成された重み付きグラフG=(V,E)に対しダイクストラ法を適用して、スコアを最小とする小領域をつないだ小領域列を補間経路として算出するようにしている。
したがって、小領域ごとにスコアを算出する方法を採用しているにもかかわらず、ダイクストラ法をそのまま適用して最適経路を探索することが可能となる。
【0063】
(第2の実施形態)
この発明の第2の実施形態は、スコアを算出しさらに最適経路を算出する際に、最初は経路探索範囲を比較的大きいサイズの小領域に分割してスコア計算と補間経路の探索処理を行い、以後小領域のサイズを段階的に小さくしながらスコア計算と補間経路の探索処理を繰り返し行うことにより補間経路を表す小領域を絞り込むようにしたものである。
図12はこの発明の第2の実施形態に係わる行動経路推定装置による行動経路推定処理の手順と処理内容を示すフローチャートである。なお、同図において前記図4と同一部分には同一符号を付して詳しい説明は省略する。
【0064】
スコア算出処理部22は、ステップS5において1回目のスコア計算を行う際に、探索経路範囲Uを比較的大きい第1のサイズの小領域に分割し、この第1のサイズの小領域についてスコアを計算する。経路計算処理部23は、ステップS6において、上記第1のサイズの小領域について得られたスコアをもとにスコアが最小となる小領域のつながりからなる補間経路の候補として求める。図13(a)はこの第1のサイズの小領域に対し得られた補間経路候補の一例を示すものである。
【0065】
上記補間経路の候補が得られると、制御ユニット2はステップS41において、上記設定した小領域のサイズが予め設定された基準サイズ以下であるか否かを判定する。基準サイズは、補間経路に要求される精度を満足する必要最低限の小領域サイズに設定される。上記判定の結果、小領域のサイズがまだ基準サイズ以下になっていなければ、制御ユニット2はステップS42に移行する。そして、このステップS42において、上記ステップS6によるスコア最小経路計算処理で得られた補間経路の候補に対応する小領域とその周辺の隣接小領域を新たな限定された経路探索範囲とし、ステップS5による位置スコア計算処理に2回目のスコア計算処理を行わせる。
【0066】
位置スコア計算処理は、2回目のスコア計算処理を実行するに当たり、小領域のサイズを上記第1のサイズより一定量小さい第2のサイズに変更する。そして、上記ステップS542の処理により限定された経路探索範囲を上記第2のサイズの小領域に分割し、この第2のサイズの小領域についてスコアを計算する。経路計算処理部23は、上記第2のサイズの小領域について得られたスコアをもとにスコアが最小となる補間経路の候補を求める。
【0067】
そして、制御ユニット2はステップS41において、上記設定した小領域のサイズが予め設定された基準サイズ以下であるか否かを判定する。そして、小領域のサイズがまだ基準サイズ以下になっていなければ、ステップS42において、経路探索範囲を上記2回目の経路計算処理で得られた補間経路の候補を含む小領域とその隣接小領域に限定し、ステップS5による位置スコア計算処理に3回目のスコア計算処理を行わせる。
【0068】
以後同様に、上記位置スコア計算処理において設定される小領域のサイズが基準サイズ以下と判定されるまで、上記ステップS5〜ステップS42による処理が繰り替えし行われる。そして、小領域のサイズが基準サイズ以下になると、制御ユニット2は最後の補間経路計算処理により得られた補間経路の候補を探索結果として携帯端末へ送信する。図13(b)は小領域のサイズが基準サイズ以下になったときの小領域のサイズの一例を、また図13(c)は当該サイズの小領域について得られた補間経路候補の例を示すものである。
【0069】
以上述べたように第2の実施形態によれば次のような効果が奏せられる。すなわち、1つひとつの小領域のサイズを大きく設定すると処理にかかる計算量は小さくてすむが、得られる補間経路の精度は粗くなる。一方、小領域のサイズを小さく設定すると得られる補間経路は精細なものとなるが、計算量は増大する。つまり、経路探索の処理にかかる計算量と得られる補間経路の精度とはトレードオフの関係にある。
そこで、第2の実施形態のように小領域のサイズを最初は大きなサイズ(第1のサイズ)に設定して補間経路の候補を求め、以後探索経路範囲を限定しかつ小領域のサイズを段階的に小さくしながら補間経路の候補を探索することによって、比較的少ない計算量で精細な補間経路を求めることが可能となる。
【0070】
(その他の実施形態)
なお、この発明は上記実施形態に限定されるものではない。例えば、前記実施形態では例えばWebサーバにより構成される行動経路推定装置SVにおいてユーザの行動経路を推定するようにした。しかし、それに限定されるものではなく、携帯端末MS1〜MSnに行動経路推定処理機能を持たせるようにしてもよい。
その他、行動経路推定装置の構成、行動経路推定処理の手順と処理内容等についても、この発明の要旨を逸脱しない範囲で種々変形して実施可能である。
【0071】
要するにこの発明は、上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【0072】
MS1〜MSn…携帯端末、SV…行動経路推定装置、NW…通信ネットワーク、1…送受信ユニット、2…制御ユニット、3…記憶ユニット、21…位置データ収集処理部、22…スコア算出処理部、23…経路計算処理部、24…補間経路出力部、31…位置データ記憶部。
【特許請求の範囲】
【請求項1】
ユーザが所持する携帯端末から当該ユーザの位置データを受信し、この受信された位置データの集合を記憶媒体に記憶する過程と、
地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲を複数の小領域に分割する過程と、
前記記憶媒体に記憶された位置データの集合に基づいて、前記分割された小領域ごとに当該小領域を前記ユーザが通過する確率を表すスコアを算出する過程と、
前記算出されたスコアに基づいて、前記補間対象区間の始点と終点との間の最適経路を算出する過程と
を具備し、
前記スコアを算出する過程は、前記位置データ集合をZ、前記小領域dの集合をD、小領域の中心座標をxd 、xd の確率密度分布をp(xd)としたとき、スコアscore(d)を
【数1】
により算出することを特徴とする行動経路推定方法。
【請求項2】
前記スコアを算出する過程は、
hをカーネルの広がりを定めるガウス分布の標準偏差とするとき、前記確率密度分布p(xd)を、
【数2】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項3】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合に含まれる位置データの各々に、座標値の計測誤差に関する情報が付加されている場合に、hをカーネルの広がりを定めるガウス分布の標準偏差とし、かつ前記誤差をωi 、当該ωi の前記ガウス分布の標準偏差hに対する影響を調整するためのパラメータをλとしたとき、
前記確率密度分布p(xd)を、
【数3】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項4】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合Zの中の点xi について、xi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルui^,vi^をそれぞれ
【数4】
と定義し、
Iを2×2の単位行列、σを分散共分散行列の等方性を調整するためのパラメータとし、前記単位ベクトルui^,vi^を用いて2×2の分散共分散行列Σi を
【数5】
と定義し、
さらに2×2の分散共分散行列Σi^を
【数6】
により表したとき、
前記確率密度分布p(xd)を、
【数7】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項5】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合から、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除後に残った位置データの集合をもとにスコアを算出することを特徴とする請求項1乃至4のいずれかに記載の行動経路推定方法。
【請求項6】
前記最適経路を算出する過程は、
前記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ前記各ノードに前記小領域ごとに算出されたスコアを反映させた重み付きグラフを作成する過程と、
前記作成された重み付きグラフに対しダイクストラ法を適用して、スコアを最小とする小領域をつないだ小領域列を算出する過程と
を備えることを特徴とする請求項1記載の行動経路推定方法。
【請求項7】
前記スコアの算出過程及び最適経路の算出過程は、
前記経路探索範囲を第1のサイズからなる複数の小領域に分割し、これらの小領域に対して補間経路の候補を算出する第1の過程と、
前記第1の過程により算出された補間経路の候補に対応する小領域とその周辺領域を含む限定された経路探索範囲を前記第1のサイズより小さい第2のサイズからなる複数の小領域に分割し、これらの小領域に対し補間経路の候補を算出する第2の過程と
を備え、
前記第2の過程を、前記小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら少なくとも1回実行することを特徴とする請求項1乃至6のいずれかに記載の行動経路推定方法。
【請求項8】
請求項1乃至7記載の行動経路推定方法が備える各過程を実現する処理を、コンピュータに実行させるプログラム。
【請求項1】
ユーザが所持する携帯端末から当該ユーザの位置データを受信し、この受信された位置データの集合を記憶媒体に記憶する過程と、
地図情報を反映した二次元空間上において、補間対象となる区間の始点と終点を含む経路探索範囲を複数の小領域に分割する過程と、
前記記憶媒体に記憶された位置データの集合に基づいて、前記分割された小領域ごとに当該小領域を前記ユーザが通過する確率を表すスコアを算出する過程と、
前記算出されたスコアに基づいて、前記補間対象区間の始点と終点との間の最適経路を算出する過程と
を具備し、
前記スコアを算出する過程は、前記位置データ集合をZ、前記小領域dの集合をD、小領域の中心座標をxd 、xd の確率密度分布をp(xd)としたとき、スコアscore(d)を
【数1】
により算出することを特徴とする行動経路推定方法。
【請求項2】
前記スコアを算出する過程は、
hをカーネルの広がりを定めるガウス分布の標準偏差とするとき、前記確率密度分布p(xd)を、
【数2】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項3】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合に含まれる位置データの各々に、座標値の計測誤差に関する情報が付加されている場合に、hをカーネルの広がりを定めるガウス分布の標準偏差とし、かつ前記誤差をωi 、当該ωi の前記ガウス分布の標準偏差hに対する影響を調整するためのパラメータをλとしたとき、
前記確率密度分布p(xd)を、
【数3】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項4】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合Zの中の点xi について、xi-1からxi への方向とxiからxi+1への方向を表す単位ベクトルui^,vi^をそれぞれ
【数4】
と定義し、
Iを2×2の単位行列、σを分散共分散行列の等方性を調整するためのパラメータとし、前記単位ベクトルui^,vi^を用いて2×2の分散共分散行列Σi を
【数5】
と定義し、
さらに2×2の分散共分散行列Σi^を
【数6】
により表したとき、
前記確率密度分布p(xd)を、
【数7】
により算出することを特徴とする請求項1記載の行動経路推定方法。
【請求項5】
前記スコアを算出する過程は、
前記記憶媒体に記憶された位置データ集合から、隣接する2点間の距離が予め設定したしきい値以下となる点の位置データを削除し、この削除後に残った位置データの集合をもとにスコアを算出することを特徴とする請求項1乃至4のいずれかに記載の行動経路推定方法。
【請求項6】
前記最適経路を算出する過程は、
前記分割された各小領域をノードに対応付けると共にこれらのノード間をリンクで接続し、かつ前記各ノードに前記小領域ごとに算出されたスコアを反映させた重み付きグラフを作成する過程と、
前記作成された重み付きグラフに対しダイクストラ法を適用して、スコアを最小とする小領域をつないだ小領域列を算出する過程と
を備えることを特徴とする請求項1記載の行動経路推定方法。
【請求項7】
前記スコアの算出過程及び最適経路の算出過程は、
前記経路探索範囲を第1のサイズからなる複数の小領域に分割し、これらの小領域に対して補間経路の候補を算出する第1の過程と、
前記第1の過程により算出された補間経路の候補に対応する小領域とその周辺領域を含む限定された経路探索範囲を前記第1のサイズより小さい第2のサイズからなる複数の小領域に分割し、これらの小領域に対し補間経路の候補を算出する第2の過程と
を備え、
前記第2の過程を、前記小領域のサイズが予め設定したサイズ以下になるまで当該小領域のサイズを段階的に減少させながら少なくとも1回実行することを特徴とする請求項1乃至6のいずれかに記載の行動経路推定方法。
【請求項8】
請求項1乃至7記載の行動経路推定方法が備える各過程を実現する処理を、コンピュータに実行させるプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2012−42287(P2012−42287A)
【公開日】平成24年3月1日(2012.3.1)
【国際特許分類】
【出願番号】特願2010−182567(P2010−182567)
【出願日】平成22年8月17日(2010.8.17)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成24年3月1日(2012.3.1)
【国際特許分類】
【出願日】平成22年8月17日(2010.8.17)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]