トップ :: G 物理学 :: G01 測定;試験

【発明の名称】 移動体位置推定システム、及び、移動体位置推定方法
【発明者】 【氏名】中田 豊久

【氏名】國藤 進

【氏名】金井 秀明

【要約】 【課題】探索者の位置や探索履歴をも考慮して被探索者の位置を推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。

【構成】第1の移動体の位置情報を用いて地図データの座標系の各位置に第1の移動体が存在する確率を算出し、その確率に応じて当該地図データの座標系に分散する第1の移動体用のパーティクルをサンプリングする第1のサンプリング手段と、第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、地図データの座標系の各位置に第1の移動体が存在する確率を算出し、第1のサンプリング手段によりサンプリングされた第1の移動体用のパーティクルを、その確率に応じてリサンプリングする第2のサンプリング手段とを有し、リサンプリングしたパーティクルから第1の移動体の位置を推定する。
【特許請求の範囲】
【請求項1】
移動体位置計測装置から移動体の位置情報を取得すると、当該移動体の位置情報を用いて地図データの座標系にランダムウォークするパーティクルをサンプリングするパーティクルフィルタを有し、当該サンプリングしたパーティクルを用いて当該移動体の位置を推定する移動体位置推定システムにおいて、
当該パーティクルフィルタは、移動体位置計測装置から第1の移動体の位置情報を取得すると、当該第1の移動体の位置情報を用いて地図データの座標系の各位置に当該第1の移動体が存在する確率を算出し、算出された確率に応じて当該地図データの座標系に分散する第1の移動体用のパーティクルをサンプリングする第1のサンプリング手段と、
第2の移動体の位置情報を取得すると、当該第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、当該地図データの座標系の各位置に第1の移動体が存在する確率を算出し、前記第1のサンプリング手段によりサンプリングされた第1の移動体用のパーティクルを、当該算出された確率に応じてリサンプリングする第2のサンプリング手段とを有し、
当該第2のサンプリング手段によりサンプリングした第1の移動体用のパーティクルから第1の移動体の位置を推定する位置推定手段を備えることを特徴とする移動体位置推定システム。
【請求項2】
前記第2のサンプリング手段は、前記地図データの座標系の各位置に第1の移動体が存在する確率として、前記第2の移動体の位置情報から地図データの座標系の各位置に当該第2の移動体が存在する確率を算出し、当該算出された確率の逆数を用いることを特徴とする請求項1に記載の移動体位置システム。
【請求項3】
前記位置推定手段は、前記第2のサンプリング手段によりサンプリングした第1の移動体用パーティクルをクラスタリングし、各クラスターの平均値を当該第1の移動体の推定位置とすることを特徴とする請求項1又は請求項2に記載の移動体位置推定システム。
【請求項4】
スタート地点が与えられると、当該スタート地点から、前記位置推定手段により算出された第1の移動体の推定位置を巡回可能な巡回経路を算出する巡回経路算出手段を備えることを特徴とする請求項3に記載の移動体位置推定システム。
【請求項5】
前記巡回経路算出手段は、各巡回経路ごとに、下記数1を用いて評価値Vを求め、各巡回経路を当該評価値Vに基づいて順位付けすることを特徴とする請求項4に記載の移動体位置推定システム。
【数1】


Routeは評価値Vを求めようとする経路における推定位置r(スタート地点を除く各地点)の集合であり、rはその推定位置の1つを示す。T(r)は、推定位置rに到達するまでの1つ前の地点(スタート地点又は推定位置)からの時間を求める関数である。P(r)は、推定位置rの1つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。
【請求項6】
移動体位置計測装置から移動体の位置情報を取得し、当該移動体の位置情報を用いて地図データの座標系にランダムウォークするパーティクルをサンプリングするパーティクルフィルタを有し、当該サンプリングしたパーティクルを用いて当該移動体の位置を推定する移動体位置推定方法において、
当該パーティクルフィルタは、移動体位置計測装置から第1の移動体の位置情報を取得すると、当該第1の移動体の位置情報を用いて地図データの座標系の各位置に当該第1の移動体が存在する確率を算出し、算出された確率に応じて当該地図データの座標系に分散する第1の移動体用のパーティクルをサンプリングする第1のサンプリングステップ、
第2の移動体の位置情報を取得すると、当該第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、当該地図データの座標系の各位置に第1の移動体が存在する確率を算出し、当該第1のサンプリングステップにおいてサンプリングされた第1の移動体用のパーティクルを当該確率に応じてリサンプリングする第2のサンプリングステップとを有し、
当該第2のサンプリングステップにおいてサンプリングした第1の移動体用のパーティクルから第1の移動体の位置を推定する位置推定ステップを備えることを特徴とする移動体位置推定方法。
【請求項7】
前記第2のサンプリングステップは、前記地図データの座標系に第1の移動体が存在する確率として、前記第2の移動体の位置情報から地図データの座標系の各位置に当該第2の移動体が存在する確率を算出し、当該算出された確率の逆数を用いることを特徴とする請求項6に記載の移動体位置推定方法。
【請求項8】
前記位置推定ステップは、前記第2のサンプリングステップによりサンプリングした第1の移動体用パーティクルをクラスタリングし、各クラスターの平均値を当該第1の移動体の推定位置とすることを特徴とする請求項6又は請求項7に記載の移動体位置推定方法。
【請求項9】
スタート地点が与えられると、当該スタート地点から、前記位置推定方法により算出された第1の移動体の推定位置を巡回可能な巡回経路を算出する巡回経路算出ステップを備えることを特徴とする請求項8に記載の移動体位置推定方法。
【請求項10】
前記巡回経路算出ステップは、各巡回経路ごとに、下記関数1を用いて評価値Vを求め、各巡回経路を当該評価値Vに基づいて順位付けすることを特徴とする請求項9に記載の移動体位置推定方法。
【数1】


Routeは評価値Vを求めようとする経路における推定位置r(スタート地点を除く各地点)の集合であり、rはその推定位置の1つを示す。T(r)は、推定位置rに到達するまでの1つ前の地点(スタート地点又は推定位置)からの時間を求める関数である。P(r)は、推定位置rの1つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。
【発明の詳細な説明】【技術分野】
【0001】
移動体位置計測装置から得られる位置情報を利用して、移動体の位置を推定する移動体位置推定システム、及び、移動体位置推定方法に関する。
【背景技術】
【0002】
近年、GPSなどの移動体位置計測装置により、移動体の位置を取得することが容易に可能となってきた。しかし、その位置情報は精度が低く、移動体位置計測装置単体では数十メートルから数百メートルの誤差が発生するのが現状である。その不確実性を軽減するために、移動体位置計測装置から得た位置情報に基づいて、コンピュータにより移動体の位置を推定する移動体位置推定システムが用いられている。下記非特許文献1には、移動体位置推定システムにパーティクルフィルタを用いて位置を確率的に扱う技術が提案されている。パーティクルフィルタとは、複数個のパーティクルの重み付き総和によって全体の確率分布を近似する手法であり、コンピュータにより次のように位置の推定が行われる。(1)地図データの座標系上のランダムな位置にN個のパーティクルを生成する。(2)パーティクルをランダムウォークさせる。(3)移動体位置計測装置からの位置情報を確率分布として表す。(4)確率分布に従って個々のパーティクル位置の生起確率を求める。(5)生起確率に比例させて、各パーティクルの重みを更新する。(6)各パーティクルの重みと位置とから移動体の位置について確率分布を最尤推定する。(7)確率分布の平均を移動体の位置と推定する。
【非特許文献1】J.Hightower,B.Borriello.“The Location Stack:A Layerd Model for Location in Ubiquitous Computing”,4th IEEE Workshop on Modile Computing Systems & Applications (WMCSA 2002),pp.22−28.2002.
【発明の開示】
【発明が解決しようとする課題】
【0003】
上記従来の移動体位置推定システムは、遭難者や徘徊する高齢者などの探索に用いられる。この場合、被探索者にGPS機能を備える情報端末等を携帯させ、情報端末等の位置を推定することにより、被探索者を探索する。かかる探索では、探索者がいる位置や探索済みの位置には被探索者が存在しない確率が高いなど、被探索者の位置情報だけでなく、探索者の位置や探索履歴も重要な要素となってくる。しかしながら、従来の移動体位置推定システムは、被探索者の位置情報のみに基づいて被探索者の位置が推定されるだけであり、探索者の位置や探索履歴はまったく考慮されていなかった。
【0004】
また、上記従来の移動体位置推定システムは、パーティクルから一つの確率分布を求め、その平均を移動体の位置と推定するため、推定される位置は一つとなる。しかしながら、移動体位置計測装置の誤差が大きいときは、一つの推定位置に集約すると推定確率の分散が大きくなり、推定精度が低くなってしまうという問題が生じていた。
【0005】
そこで、本発明は、被探索者の位置情報のみならず、探索者の位置や探索履歴をも考慮して被探索者の位置を推定可能であり、更には、移動体の位置を高い精度で推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。
【課題を解決するための手段】
【0006】
本発明の移動体位置推定システム/方法は、移動体位置計測装置から移動体の位置情報を取得すると、当該移動体の位置情報を用いて地図データの座標系にランダムウォークするパーティクルをサンプリングするパーティクルフィルタを有し、当該サンプリングしたパーティクルを用いて当該移動体の位置を推定する移動体位置推定システム/方法において、
当該パーティクルフィルタは、移動体位置計測装置から第1の移動体の位置情報を取得すると、当該第1の移動体の位置情報を用いて地図データの座標系の各位置に当該第1の移動体が存在する確率を算出し、算出された確率に応じて当該地図データの座標系に分散する第1の移動体用のパーティクルをサンプリングする第1のサンプリング手段/ステップと、
第2の移動体の位置情報を取得すると、当該第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、当該地図データの座標系の各位置に第1の移動体が存在する確率を算出し、当該第1のサンプリング手段/ステップによりサンプリングされた第1の移動体用のパーティクルを当該確率に応じてリサンプリングする第2のサンプリング手段/ステップとを有し、
当該第2のサンプリング手段/ステップによりサンプリングした第1の移動体用のパーティクルから第1の移動体の位置を推定する位置推定手段/ステップを備えることを特徴とする。
【0007】
ここで、第1の移動体の位置情報は、被探索者が携帯する移動体情報端末の位置として移動体位置計測装置から得られる位置情報である。また、第2の移動体の位置情報は、その時点での探索者の位置や、探索者が探索済みの位置を特定する位置情報であり、探索者が携帯する移動体情報端末の位置として移動体位置計測装置から得られてもよいし、探索者等の探索履歴等として入力される単数又は複数の位置情報でもよい。
【0008】
本発明の移動体位置推定システム/ステップは、捜索者が被捜索者を探索する場合などに使用される。上記第1の移動体は情報端末を携帯する被捜索者であり、第2の移動体は探索者である。探索に際しては、探索者がいる位置や探索済みの位置には、被探索者の存在する確率が低いため、これらの位置については被探索者がいる確率を低くする。すなわち、この発明によれば、第1のサンプリング手段/ステップにより、第1の移動体の位置情報を用いて地図データの座標系の各位置に第1の移動体が存在する確率を算出し、その確率に応じて第1の移動体用のパーティクルをサンプリングする。そして、第2のサンプリング手段/ステップにより、第2の移動体の位置情報によって特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、地図データの座標系の各位置に第1の移動体が存在する確率を算出し、その確率に応じて第1の移動体用のパーティクルをリサンプリングする。これにより、探索者が存在する位置や探索済みの位置については、被捜索者が存在する確率を低くすることができ、探索者の位置をも考慮した位置推定を行うことができる。
【0009】
前記第2のサンプリング手段/ステップは、前記地図データの座標系の各位置に第1の移動体が存在する確率として、前記第2の移動体の位置情報から地図データの座標系の各位置に当該第2の移動体が存在する確率を算出し、当該算出された確率の逆数を用いることが好ましい。
【0010】
この発明によれば、第2のサンプリング手段/ステップは、取得した第2の移動体の位置情報から第2の移動体が存在する確率を算出し、算出された確率の逆数を求める。そして、この逆数を第1の移動体が存在する確率として用い、この逆数に応じて第1の移動体用のパーティクルをリサンプリングする。これにより、被探索者の位置の推定に、探索者の位置をより詳細に反映させることができる。
【0011】
前記位置推定手段/ステップは、前記第2のサンプリング手段/ステップによりサンプリングした第1の移動体用パーティクルをクラスタリングし、各クラスターの平均値を当該第1の移動体の推定位置とすることが好ましい。算出される推定位置は単数でも良いし複数でも良い。
【0012】
すべての第1の移動体用パーティクルから移動体の位置を推定した場合、移動体位置計測装置からの位置情報の誤差が大きいときには、推定確率の分散が大きくなり、推定精度が低くなる。本発明によれば、第1の移動体用パーティクルをクラスタリングし、各クラスターの平均値を推定位置とするため、各クラスター内の推定確率の分散を抑えることができ、推定精度を高めることができる。
【0013】
本発明の移動体位置推定システム/方法は、スタート地点が与えられると、当該スタート地点から、前記位置推定手段/ステップにより算出された第1の移動体の推定位置を巡回可能な巡回経路を算出する巡回経路算出手段/ステップを備えることが好ましい。
【0014】
本発明によれば、巡回経路算出手段/ステップは、与えられたスタート地点から出発して推定位置を巡回する巡回経路を算出するため、探索者は算出された巡回経路に従って推定位置を巡回することで被探索者を探索することができる。
【0015】
前記巡回経路算出手段/ステップは、各巡回経路ごとに、下記数1により評価置Vを求め、各巡回経路を当該評価値Vに応じて順位付けすることが好ましい。
【数1】


Routeは評価値Vを求めようとする経路における推定位置r(スタート地点を除く各地点)の集合であり、rはその推定位置の1つを示す。T(r)は、推定位置rに到達するまでの1つ前の地点(スタート地点又は推定位置)からの時間を求める関数である。P(r)は、推定位置rの1つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。
【0016】
本発明によれば、巡回経路算出手段/ステップは、上記数1により巡回経路を順位付けすることにより、各推定位置における第1の移動体が存在する確率と、推定位置を巡回するために必要な時間との二つの観点から、巡回経路を順位付けすることができる。これにより、探索者に対して速く且つ確実に被探索者を探索できる巡回経路を提示することができる。
【発明の効果】
【0017】
本発明に係る移動体位置推定ステム/方法によれば、第1のサンプリング手段/ステップにより、第1の移動体の位置情報を用いて地図データの座標系の各位置に第1の移動体が存在する確率を算出し、その確率に応じてパーティクルをサンプリングする。その後に、第2のサンプリング手段/ステップにより、第1の移動体が存在する確率を、第2の移動体の位置情報により特定される位置のほうが他の位置よりも低くなるように算出し、その確率に応じてパーティクルをリサンプリングする。これにより、探索者等が存在する位置や探索済みの位置については、被捜索者等が存在する確率を低くすることができ、探索者の位置や探索履歴を考慮した被探索者の位置の推定が可能となる。
【0018】
また、上記第2のサンプリング手段/ステップは、前記第2の移動体の位置情報から地図データの座標系の各位置に当該第2の移動体が存在する確率を算出し、当該算出された確率の逆数を算出し、この逆数を前記地図データの座標系に第1の移動体が存在する確率として用いる。逆数を用いることにより、被探索者の位置推定に探索者の位置をより詳細に反映させることができる。
【0019】
また、位置推定手段/ステップは第1の移動体用パーティクルをクラスタリングし、各クラスターごとの平均値を推定位置とすれば、推定確率の分散を抑えることができ、推定精度を向上させることができる。また、複数の推定位置を出力可能であり、より多くの情報を探索者に与えることができる。
【0020】
また、巡回経路算出手段/ステップが、被探索者の推定位置を巡回する巡回経路を算出すれば、探索者は算出された巡回経路に従って巡回することで被探索者を探索することができる。
【0021】
また、巡回経路算出手段/ステップが、上記数1により巡回経路を順位付けすれば、各推定位置に被探索者が存在する確率と、推定位置を巡回するために必要な時間との二つの観点から、探索者が被探索者を探索するのに有効な順序で巡回経路を順位付けすることができる。高い順位の巡回経路で巡回することにより、探索者は効率的に推定位置を巡回することができ、より早く被探索者を発見することが可能となる。
【0022】
本発明は、様々な分野に応用可能であり、例えばGPS機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索するのに用いたり、登下校中の児童の位置を把握し、緊急時には駆けつけて安全を確保したりするのに用いることができる。
【発明を実施するための最良の形態】
【0023】
(第1の実施の形態)
本実施の形態の移動体位置推定システム1は、移動体位置計測装置から移動体の位置情報を取得し、当該移動体の位置情報に応じて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを有し、パーティクルフィルタによりサンプリングしたパーティクルを用いて移動体の位置を推定するシステムである。
【0024】
図1は、本発明の第1の実施の形態による移動体位置推定システム1の一構成を示すブロック図である。本実施の形態による移動体位置推定システム1は、内部バス11に、通信インタフェース12、CPU13、ROM14、RAM15、ディスプレイ16、キーボード/マウス17、ドライブ18、ハードディスク19を接続させ、アドレス信号、制御信号、データ等を伝送させ、本実施の形態による移動体位置推定システム1を実現するコンピュータシステムとしての構成を備えている。
【0025】
通信インタフェース12は、移動体位置計測装置との通信やインターネット等の通信網に接続する各種通信機能を有しており、移動体位置計測装置から移動体の位置情報を受信したり、本発明に係る位置推定をコンピュータに実行させるプログラム19aや地図データ19cをダウンロードしたりすることも可能である。CPU13は、ROM14に格納されたOSにより装置全体の制御を行うとともにハードディスク19に格納された各種のアプリケーションプログラム19aに基づいて処理を実行する機能を司る。
【0026】
ROM14は、OS等のように装置全体の制御を行うためのプログラムを格納しており、これらをCPU13に供給する機能を有している。RAM15は、CPU13による各種プログラムの実行時にワークエリアとして利用されるメモリ機能を有している。
【0027】
ディスプレイ16は、地図データや確率データや推定位置をグラフィカルに表示したりする機能を有している。キーボード/マスス17は、文字、数字、記号等のデータを入力したり、画面上のポイント位置を操作することが可能である。
【0028】
ドライブ18は、各種のプログラム、データを記録したCD、DVD等の記録媒体からインストール作業を実行するための駆動ユニットである。コンピュータを移動体位置推定システム1として機能させるプログラム19aや地図データ19cを記憶媒体からインストールしたりすることも可能である。
【0029】
ハードディスク19は、プログラム19a、メモリ19b、地図データ19c等の各種データを記憶する外部記憶装置である。プログラム19aは、前述した通信インタフェース12、ドライブ18等からインストールされたプログラムを実行形式で記憶したものに相当する。メモリ19bは、各種プログラムの実行結果等のファイルを保存する記憶部である。
【0030】
地図データ19cは、例えば図2に示すように、経度・緯度で表される座標系に建物・道路・河川等や、都道府県、市町村、住所などの領域や、位置、方角、距離等の基本データD1が含まれている。
【0031】
地図データ19cには、基本データD1の各領域に対応するように移動体が存在する確率を示す確率データD2が含まれていてもよい。確率データD2は、例えば、図2に示すように、建物がカテゴリa、道路がカテゴリb、河川がカテゴリc、その他がカテゴリdというように領域がカテゴリに分けられており、カテゴリごとに確率が設定されている。この確率は推定対象となる第1の移動体がその領域に存在する確率である。推定対象として人が携帯する端末であれば、建物のカテゴリaや道路のカテゴリbの確率は高く、河川のカテゴリcの確率は低く設定されている。また、カテゴリ分けすることなく、各建物ごとや各道路ごとというように、領域ごとに確率が設定されていても良いし、住所などの人為的に分けられた領域に設定されていても良い。これにより、移動体固有の行動パターンや行動範囲を推定に反映させることができる。確率データD2は地図情報19cの一部として一体となっていても良いし、別データとして記憶されていても良い。
【0032】
確率データD2は、後述するステップS1の前に行われる事前処理で生成され、ハードディスク19に記憶されている。確率は予めシステム1内に設定されていても良いし、ユーザにより任意に設定や変更を可能としても良い。たとえば、地図データ19cの基本データD1をグラフィカルに表示し、ユーザにより各建物や道路等ごとに確率やカテゴリを事前設定可能とし、この事前設定により確率データD2を生成可能としても良い。また、基本データD1が建物や道路などの領域を識別する識別情報を含む場合(例えば、建物や道路などが色分けされていたり、マークが付されていたりする場合)、移動体位置推定システム1が、その識別情報を利用して領域をカテゴリ分けし、そのカテゴリを確率データD2で用いてもよい。これにより、カテゴリ分けの作業が不要となり、既存の地図データ19cを用いて、領域のカテゴリ分けを簡単に行うことができる。
【0033】
本発明におけるパーティクルとは、地図データ19cの座標系上の位置を示す指標であり、属性には少なくとも地図データ19cの座標系において位置を特定可能な位置情報を含む。パーティクルフィルタとは、移動体位置計測装置から得られる位置情報を取得すると、地図データ19cの座標系に分散する複数のパーティクルから、上記位置情報に応じてパーティクルをサンプリングする機能を少なくとも備え、本実施の形態においては少なくとも下記のステップS1からS9を実行する機能を備える。
【0034】
図3は、移動体位置推定システム1を用いた移動体位置推定方法を説明するフローチャートであり、図4は概念的に説明する説明図である。移動体位置推定システム1はランダムウォーク手段、第1のサンプリング手段、第2のサンプリング手段、位置推定手段を備え、各手段が下記ように機能して、本発明の移動体位置推定方法を実現する。
【0035】
(ステップS1)ランダムウォーク手段は、地図データ19cの第1の座標系のランダムな位置に第1の移動体用のパーティクルを複数配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図4(1)に示すように、複数の第1の移動体用のパーティクル(図4(1)中の灰色の円)がランダムな位置に配置される。
【0036】
(ステップS2)ランダムウォーク手段は、定期的に地図データ19cの第1の座標系に配置されたすべてのパーティクルをランダムに移動(ランダムウォーク)させる。地図データ19cに確率データD2を含む場合は、その確率に依存させてすべてのパーティクルをランダムウォークさせる。確率データD2は必須ではないが、確率データD2を用いることにより、道路や建物や河川といった領域ごとに移動体が存在する確率を反映させることができ、移動体の位置をより高い精度で推定可能となる。パーティクルのランダムウォークは、各パーティクルの位置情報を変更することにより行う。たとえば、図5に示すように、確率データD2は、基本データD1の緯度経度座標系をピクセル単位に変換し、基本データD1でカテゴリa,b,c,dに分けられた各領域にピクセル単位で確率を設定したものとする。そして、パーティクルの移動可能範囲eをパーティクルの位置を中心とした一定半径サークル内として設定しておき、パーティクルをランダムウォークさせるときには、移動可能範囲e内のすべてのピクセルの確率データを取得し、その確率に比例させて次の位置を決定し、その位置にパーティクルを移動させる。パーティクルを移動させるタイミングは予め移動体位置推定システム1に設定されており、そのタイミングになると確率データD2に従ってパーティクルをランダムウォークさせる。図4(2)は、確率データD2に従ってパーティクルをランダムウォークさせたときの状態を概念的に示す説明図である。建物や道路等の確率の高い領域に多くのパーティクルが配置される。
【0037】
(ステップS3)移動体位置計測装置から第1の移動体の位置情報を取得しない間は、ステップS2に戻り上記ランダムウォークを続ける。移動体位置計測装置から第1の移動体の位置の情報を取得した場合は、ステップS4に進む。
【0038】
(ステップS4)第1のサンプリング手段は、第1の移動体の位置情報を取得すると、取得した位置情報を用いて、地図データ19cの座標系上の各位置に第1の移動体が存在する確率を算出する。確率の算出は、例えば取得した位置情報を確率分布P1(x)に変換することにより行う。移動体位置計測装置からの位置情報の形式は、その装置の特性によって異なるので、装置に応じた確率分布P1(x)に変換する必要がある。このため、移動体位置推定システム1には移動体位置計測装置ごとに予め数式等による変換規則が設定されており、位置情報から確率分布P1(x)への変換はその規則に従い行う。例えば、GPSの場合は緯度経度情報を出力するので、取得した緯度経度情報を平均とした正規分布に変換する。また、PHSは各地に所在する基地局のどの基地局で端末からのデータを受信したかで位置が特定される。このため、移動体からの電波を受信した基地局が電波を受信できる範囲内は、移動体が存在する確率が一様であり、その他の範囲は確率が0である。そこで、PHSから位置情報を取得した場合は、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を0より大の一定値とし、その他の領域は確率を0とする一様分布に変換する。
【0039】
(ステップS5)算出された確率に従って、地図データ19cにランダムウォークする第1の移動体用のパーティクルの母集団からパーティクルをサンプリングする。図4(3)は第1の移動体用のパーティクルのサンプリングを概念的に説明する説明図である。サンプリングの方法は、まず、ステップS4にて算出された確率分布P1(x)に従って1つのパーティクルを第1の移動体用のパーティクルの母集団から抽出して記憶し、それを母集団に戻して再び同様に次のパーティクルを抽出する。それを繰り返すことにより、第1の移動体用のパーティクルの母集団と同じ数のパーティクルを確率分布P1(x)に従って抽出する。図6(a)は、GPSの位置情報を用いたときの確率分布P1(x)と、地図データ19cの座標系にランダムウォークするパーティクルの母集団と、サンプリングされたパーティクルとを説明する説明図である。横軸の上に並んでいる長方形が個々のパーティクルを表している。取得した位置情報を平均とした確率分布P1(x)に従って、母集団からパーティクルが抽出される。パーティクルは、確率分布P1(x)の値の高いところがより多く抽出され、低いところほど抽出されにくい。正規分布の場合、パーティクルは取得した第1の移動体の位置情報により特定される位置(すなわち確率分布P1(x)の平均値)に最も近いところが多く抽出されやすく、遠いところほど抽出されにくい。
【0040】
(ステップS6)第2の移動体の位置情報を取得した場合は、ステップS7に進む。
【0041】
(ステップS7)第2のサンプリング手段は、第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるように、地図データ19cの座標系の各位置に第1の移動体が存在する確率を算出する。
【0042】
地図データ19cの座標系の各位置に第1の移動体が存在する確率は、次のように算出する。まず、取得した第2の移動体の位置情報を確率分布P2(x)に変換する。第2の移動体の位置情報を移動体位置計測装置から取得した場合、確率分布P2(x)へ変換する。変換方法はステップS4と同じである。捜索者等がキーボード等の入力手段により第2の移動体の位置情報を入力した場合は、入力された位置情報を取得し、その位置情報により特定される位置に第2の移動体が存在する確率を0より大とし、その他の領域は確率を0とする確率分布に変換する。入力される位置情報は、捜索者がその時点でいる位置の情報でもよいし、捜索者の捜索履歴である複数の位置情報でもよい。
【0043】
(ステップS8)つぎに、上記第2の移動体の存在する確率を用いて、地図データ19cの座標系の各位置に第1の移動体が存在する確率を算出する。探索時には探索者がいる場所には被探索者がいない確率が高いことから、第2の移動体の位置情報により特定される位置における第1の移動体が存在する確率が、他の位置における第1の移動体が存在する確率と比較して低くなるようにする。たとえば、算出された確率分布P2(x)の逆数P3(x)を算出する。
【0044】
(ステップS9)ステップS8にて算出された逆数P3(x)に応じて、ステップS5にてサンプリングした第1の移動体用のパーティクルを再度サンプリング(リサンプリング)する。リサンプリング方法はステップS5と同様である。図6(b)は、GPSの位置情報を用いたときの確率分布P2(x)と、その逆数P3(x)と、リサンプリングされたパーティクルとを説明する説明図である。図4(4)は、逆数P3(x)に応じてリサンプリングされたパーティクルの分散を概念的に説明する説明図である。確率分布P2(x)が正規分布の場合、パーティクルは取得した第2の移動体の位置情報により特定される位置に最も近いところほど抽出されにくく、遠いほど抽出されやすい。これにより、探索者が存在する位置や探索済みの位置については、被捜索者が存在する確率を低くすることができ、探索者の位置を被探索者の位置推定に反映させることができる。
【0045】
(ステップS10)位置推定手段は、ステップS9にてリサンプリングされた第1の移動体用のパーティクルをクラスタリングする。図4(5)はパーティクルのクラスタリングを概念的に説明する説明図である。サンプリングされたパーティクルは複数のクラスターにクラスタリングされる。ここで、本実施の形態のクラスタリングについて説明する。本実施の形態のクラスタリングには、正規混合分布P(x)を用いたクラスタリング手法を用いる。正規混合分布P(x)とは数2に示される確率分布である。数2のPi(x)は正規分布を表す。この数2における正規分布の数cと各正規分布の重みαi、および各正規分布Pi(x)の平均値と分散を求めることがクラスタリング処理にあたる。本実施の形態では、これらの値を総じて、正規混合分布P(x)のパラメータと呼ぶこととする。クラスタリングによって生成されるクラスターは、正規混合分布P(x)を構成する個々の正規分布Pi(x)に対応する。正規混合分布P(x)のパラメータが求まると、数2によって各パーティクルがどのクラスターに所属するかを確率的に得ることが可能となる。さらに、地図データ19cの座標系の任意の位置を入力として与えると、その位置に移動体が存在する確率を求めることができるようになる。
【数2】


【0046】
図7に、正規混合分布P(x)によるクラスタリング例を示す。横軸の上に並んでいる長方形が個々のパーティクルを表している。P(x)は正規混合分布を表す。個々のパーティクルから求められた正規混合分布P(x)は、パーティクルが集まっているところほど、確率が高く(山が高く)なっている。この例では2つのクラスターが生成されている。
【0047】
すなわちステップS10において位置推定手段は、以下のように動作する。数2は移動体位置推定システム1に予め設定されており、位置推定手段は、ステップS9にてリサンプリングしたパーティクルの情報を用いて、数2の各パラメータ数cと各正規分布の重みαi、及び、正規分布Pi(x)の平均値と分散を算出する。各正規分布Pi(x)の重みαi、および正規分布Pi(x)の平均値と分散については、個々のパーティクルが所属するクラスターを隠れ変数としたEMアルゴリズムに基づいて算出する。EMアルゴリズムとは、隠れ変数がある場合の最尤推定方法として広く知られている手法であり、繰り返し計算を行うことで、解が収束することが証明されている。一方、正規混合分布P(x)の数cについては、初期値を1として数3に示される正規混合分布P(x)における各パーティクルの対数尤度の値が減少するまで1つずつ加算して求める。算出された各正規分布Pi(x)の平均値が第1の移動体の推定位置の座標(x、y)となる。
【数3】


【0048】
さらに、移動体位置推定システム1は、各推定位置(x、y)における第1の移動体が存在する確率P(x)を算出してもよい。この場合、上記算出された各パラメータを数2に代入し、上記算出された各推定位置の座標(x、y)を数2の入力情報(x)とし、P(x)を計算する。
【0049】
なお、クラスタリング方法は、上記に限られるものではなく、あらかじめ固定された数のクラスターに分類する非階層的クラスタリングでも良いし、互いの距離の近いものから順にクラスターを融合していくことにより、適当な数のグループに分割するC−Means法などの階層的クラスタリングでも良いし、クラスタリング方法は限定されない。
【0050】
(ステップS11)ステップS10にて算出された各クラスターの平均値、すなわち、各正規分布Pi(x)の平均値を推定位置(x,y)として出力する。図4(5)は各クラスターの平均値を概念的に説明する説明図である。算出された推定位置が複数の場合は、各推定位置(x,y)に確率を表示したり、推定位置(x,y)を確率の高い順に順位付けして出力してもよい。出力先はディスプレイ16でも良いし、通信インタフェイス12からネットワークを介して接続可能な情報端末(例えば携帯電話等)に出力しても良い。また、算出された複数の推定位置のすべてを出力してもよいし、確率順に上位数個を出力するようにしてもよい。
【0051】
パーティクルをクラスタリングして位置推定を行うため、クラスター内の推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置が唯一に出力される従来技術と比較して、本発明は推定位置として複数の候補を得ることができる。たとえば、ユーザが移動体を捜索している場合は、複数の候補地を捜索することが可能となる。
【0052】
(第2の実施の形態)
移動体位置推定システム1が徘徊老人の探索などに使用される場合、探索者は被探索者が見つかるまで複数の推定位置を巡回する必要がある。そこで、移動体位置推定システム1は、複数の推定位置の巡回経路を算出する巡回経路算出手段を備えてもよい。図8は本実施の形態の位置推定処理を説明するフローチャートであり、図9は概念的に説明する説明図である。第1の実施の形態と同様の部分については説明を省略する。
【0053】
(ステップS1)地図データ19cの第1の座標系のランダムな位置に第1の移動体用のパーティクルと第2の移動体用のパーティクルを各々複数配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図9(1)に示すように、複数の第1の移動体用のパーティクル(図9(1)中の灰色の円)と複数の第2の移動体用のパーティクル(図9(1)中の白色の円)がランダムな位置に配置される。
【0054】
(ステップ2からステップ11)ステップ2からステップ11までは上記第1の実施の形態と同様である。
【0055】
(ステップS12からステップS13)巡回経路の算出のステップS14よりも前までに巡回のスタート地点が入力される。スタート地点は、探索者等が任意に入力可能としてもよいし、探索者が携帯する情報端末のGPS等の機能を用いて移動体位置計測装置から得られる位置情報が入力されても良い。本実施の形態では、スタート地点として、移動体位置計測装置から得られた第2の移動体の位置情報を利用する場合(ステップS12とステップS13)を例に説明する。
【0056】
(ステップS12)巡回経路算出手段は、ステップS7で得られた確率分布P2(x)に基づいて、地図データ19cの第1の座標系に分布する第2の移動体用のパーティクルをサンプリングする。サンプリングの方法は、第1の移動体用のパーティクルのサンプリング方法と同じである。図9(4)は第2の移動体用のパーティクルのサンプリングを概念的に説明する説明図である。第2の移動体の位置情報に近いパーティクルが高い確率で抽出される。
【0057】
(ステップS13)抽出された第2の移動体用のパーティクルの平均値を算出する(図9(5))。この平均値をスタート地点とする。
【0058】
(ステップS14)巡回経路算出手段は、スタート地点の位置情報と、上記算出した複数の推定位置やその推定位置に移動体が存在する確率から、探索者が移動体に到達する可能性が高く、且つ、短時間に巡回できる経路を算出する。
【0059】
たとえば、巡回経路算出手段は、次のように巡回経路を算出する。まず、スタート地点から推定位置(すなわち、推定位置を表す正規混合分布を構成する各正規分布の頂点)をすべて巡回する経路を探索する。正規混合分布を構成する正規分布の数をCとすると、経路はその階乗C!だけ存在する。これらの経路を評価する関数として、下記数1を用いる。
【数1】


Routeは評価値Vを求めようとする経路における推定位置r(スタート地点を除く各地点)の集合であり、rはその推定位置の1つを示す。T(r)は、推定位置rに到達するまでの1つ前の地点(スタート地点又は推定位置)からの時間を求める関数である。P(r)は、推定位置rの1つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。評価値Vの値が小さいほど、効率的な巡回経路であるといえる。
【0060】
図10は、数1の一実施例をグラフで表した図である。図10の横軸は時間、縦軸はその移動体が存在しない確率(数3における1−P(x))、すなわち、探索者が被探索者を発見できない確率を示している。ここでは、正規混合分布を構成する正規分布の数(すなわち推定位置の数)C=3を例に説明する。すべての経路について次の処理を行う。スタート地点sから一つ目の正規分布の頂点(推定位置)p1に達するときに必要な時間と、その到達した頂点(推定位置)p1に移動体を発見できない確率を算出する。さらに、一つ目の頂点(推定位置)p1から次の頂点(推定位置)p2に達するときに必要な時間と、その到達した頂点p2における移動体を発見できない確率を算出する。このように、スタート地点から巡回する経由地点順に時間と得点を算出する。そして、横軸を時間、縦軸を移動体を発見できない確率として、算出された各頂点(推定位置)の時間と移動体が存在しない確率をプロットし、その積分値(図10の斜線部分の面積)の大きさが評価値Vとなる。これにより、第1の移動体を発見できる確率と巡回時間とを考慮した評価が可能となる。巡回経路の出力に際しては、評価値Vが低い経路のみを提示してもよいし、評価値順に順位付けしてすべての巡回経路を出力しても良い。
【0061】
一例として、図11(a)のように、移動体位置推定の結果、a,b,cの三つの推定位置が得られた場合の巡回経路の算出を説明する。スタート地点は座標(0,0)であり、推定位置aは座標(5,0)、bは座標(4,3)、cは座標(0,5)の位置であり、各推定位置における移動体が存在する確率がaは0.5,bは0.1,cは0.4であったとする。すべての巡回経路について上記評価値Vを算出した結果を図11(b)に示す。a−b−cの順で巡回する経路が最も高い評価値であるという結果が得られ、有効な巡回経路としてa−b−cが出力される。
【0062】
これにより、探索者は、出力された複数の推定位置を効率的に巡回できる経路の情報を得ることができる。たとえば、徘徊老人の探索においては、効率的に巡回することにより、より迅速に徘徊老人を見つけ出し、安全を確保することができる。
【0063】
なお、本発明は、上記実施の形態に限られるものではなく、本発明から逸脱しない範囲内で変更が可能である。たとえば、位置推定にクラスタリングを用いることなく、従来のようにパラメータの最尤推定を行う技術に適用しても良い。この場合、移動体位置推定システム1は以下のように処理を行う。図12は、そのフローチャートである。移動体位置推定システムは、上記ステップ1からステップ9を行った後、サンプリング結果からパラメータ最尤推定を行って確立分布を算出し、得られた確率分布から推定位置を算出し(ステップS10)、推定位置を出力する(ステップS11)。パラメータ最尤推定や、確率分布からの推定位置の算出は、位置計測装置の種類に応じて行えばよい。例えばGPSであればパラメータ最尤推定を行って正規分布を算出し、その正規分布の平均値を推定位置として出力する。また、PHSの場合は、ステップS4において、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を0より大の一定値(0より大)とし、その他の範囲は確率を0とする一様分布データに変換される。ステップ4以外は、PHSであってもGPSであっても同じ処理である。
【0064】
また、本発明は、様々な分野に応用可能である。たとえば、GPS機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保するのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。
【図面の簡単な説明】
【0065】
【図1】本発明の第1の実施の形態による移動体位置推定システムの一構成を示すブロック図である。
【図2】地図データを概念的に説明する説明図である。
【図3】上記実施の形態における移動体位置推定システムを用いた移動体位置推定方法を説明するフローチャートである。
【図4】上記実施の形態の位置推定処理を概念的に説明する説明図である。
【図5】上記実施の形態において確率データの設定を説明する説明図である。
【図6】(a)は、GPSの位置情報を用いたときの確率分布P1(x)と、地図データの座標系上に分散するパーティクルの母集団と、抽出されたパーティクルとを説明する説明図である。(b)は、GPSの位置情報を用いたときの確率分布P2(x)と、その逆数P3(x)と、リサンプリングされたパーティクルとを説明する説明図である。
【図7】パーティクルフィルタにより抽出されたパーティクルの確率分布を正規混合分布によって表す例を示す説明図である。
【図8】第2の実施の形態の処理を説明するフローチャートである。
【図9】上記実施の形態の位置推定処理を概念的に説明する説明図である。
【図10】上記実施の形態の巡回経路の算出に用いる関数を説明する説明図である。
【図11】上記実施の形態の巡回経路の算出の例を示す説明図である。
【図12】他の実施の形態の処理を説明するフローチャートである。
【符号の説明】
【0066】
1 移動体位置推定システム
19c 地図データ
D1 基本データ
D2 確率データ
【出願人】 【識別番号】304024430
【氏名又は名称】国立大学法人北陸先端科学技術大学院大学
【出願日】 平成18年7月5日(2006.7.5)
【代理人】 【識別番号】100105809
【弁理士】
【氏名又は名称】木森 有平


【公開番号】 特開2008−14743(P2008−14743A)
【公開日】 平成20年1月24日(2008.1.24)
【出願番号】 特願2006−185199(P2006−185199)