JP2008014743A - 移動体位置推定システム、及び、移動体位置推定方法 - Google Patents

Abstract

【課題】 探索者の位置や探索履歴をも考慮して被探索者の位置を推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。
【解決手段】 第１の移動体の位置情報を用いて地図データの座標系の各位置に第１の移動体が存在する確率を算出し、その確率に応じて当該地図データの座標系に分散する第１の移動体用のパーティクルをサンプリングする第１のサンプリング手段と、第２の移動体の位置情報により特定される位置における第１の移動体が存在する確率が、他の位置における第１の移動体が存在する確率と比較して低くなるように、地図データの座標系の各位置に第１の移動体が存在する確率を算出し、第１のサンプリング手段によりサンプリングされた第１の移動体用のパーティクルを、その確率に応じてリサンプリングする第２のサンプリング手段とを有し、リサンプリングしたパーティクルから第１の移動体の位置を推定する。
【選択図】 図３

Description

移動体位置計測装置から得られる位置情報を利用して、移動体の位置を推定する移動体位置推定システム、及び、移動体位置推定方法に関する。

近年、ＧＰＳなどの移動体位置計測装置により、移動体の位置を取得することが容易に可能となってきた。しかし、その位置情報は精度が低く、移動体位置計測装置単体では数十メートルから数百メートルの誤差が発生するのが現状である。その不確実性を軽減するために、移動体位置計測装置から得た位置情報に基づいて、コンピュータにより移動体の位置を推定する移動体位置推定システムが用いられている。下記非特許文献１には、移動体位置推定システムにパーティクルフィルタを用いて位置を確率的に扱う技術が提案されている。パーティクルフィルタとは、複数個のパーティクルの重み付き総和によって全体の確率分布を近似する手法であり、コンピュータにより次のように位置の推定が行われる。（１）地図データの座標系上のランダムな位置にＮ個のパーティクルを生成する。（２）パーティクルをランダムウォークさせる。（３）移動体位置計測装置からの位置情報を確率分布として表す。（４）確率分布に従って個々のパーティクル位置の生起確率を求める。（５）生起確率に比例させて、各パーティクルの重みを更新する。（６）各パーティクルの重みと位置とから移動体の位置について確率分布を最尤推定する。（７）確率分布の平均を移動体の位置と推定する。
Ｊ．Ｈｉｇｈｔｏｗｅｒ，Ｂ．Ｂｏｒｒｉｅｌｌｏ．"Ｔｈｅ Ｌｏｃａｔｉｏｎ Ｓｔａｃｋ：Ａ Ｌａｙｅｒｄ Ｍｏｄｅｌ ｆｏｒ Ｌｏｃａｔｉｏｎ ｉｎ Ｕｂｉｑｕｉｔｏｕｓ Ｃｏｍｐｕｔｉｎｇ"，４ｔｈ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｏｄｉｌｅ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ ＆ Ａｐｐｌｉｃａｔｉｏｎｓ （ＷＭＣＳＡ ２００２），ｐｐ．２２−２８．２００２．

上記従来の移動体位置推定システムは、遭難者や徘徊する高齢者などの探索に用いられる。この場合、被探索者にＧＰＳ機能を備える情報端末等を携帯させ、情報端末等の位置を推定することにより、被探索者を探索する。かかる探索では、探索者がいる位置や探索済みの位置には被探索者が存在しない確率が高いなど、被探索者の位置情報だけでなく、探索者の位置や探索履歴も重要な要素となってくる。しかしながら、従来の移動体位置推定システムは、被探索者の位置情報のみに基づいて被探索者の位置が推定されるだけであり、探索者の位置や探索履歴はまったく考慮されていなかった。

また、上記従来の移動体位置推定システムは、パーティクルから一つの確率分布を求め、その平均を移動体の位置と推定するため、推定される位置は一つとなる。しかしながら、移動体位置計測装置の誤差が大きいときは、一つの推定位置に集約すると推定確率の分散が大きくなり、推定精度が低くなってしまうという問題が生じていた。

そこで、本発明は、被探索者の位置情報のみならず、探索者の位置や探索履歴をも考慮して被探索者の位置を推定可能であり、更には、移動体の位置を高い精度で推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。

本発明の移動体位置推定システム／方法は、移動体位置計測装置から移動体の位置情報を取得すると、当該移動体の位置情報を用いて地図データの座標系にランダムウォークするパーティクルをサンプリングするパーティクルフィルタを有し、当該サンプリングしたパーティクルを用いて当該移動体の位置を推定する移動体位置推定システム／方法において、
当該パーティクルフィルタは、移動体位置計測装置から第１の移動体の位置情報を取得すると、当該第１の移動体の位置情報を用いて地図データの座標系の各位置に当該第１の移動体が存在する確率を算出し、算出された確率に応じて当該地図データの座標系に分散する第１の移動体用のパーティクルをサンプリングする第１のサンプリング手段／ステップと、
第２の移動体の位置情報を取得すると、当該第２の移動体の位置情報により特定される位置における第１の移動体が存在する確率が、他の位置における第１の移動体が存在する確率と比較して低くなるように、当該地図データの座標系の各位置に第１の移動体が存在する確率を算出し、当該第１のサンプリング手段／ステップによりサンプリングされた第１の移動体用のパーティクルを当該確率に応じてリサンプリングする第２のサンプリング手段／ステップとを有し、
当該第２のサンプリング手段／ステップによりサンプリングした第１の移動体用のパーティクルから第１の移動体の位置を推定する位置推定手段／ステップを備えることを特徴とする。

ここで、第１の移動体の位置情報は、被探索者が携帯する移動体情報端末の位置として移動体位置計測装置から得られる位置情報である。また、第２の移動体の位置情報は、その時点での探索者の位置や、探索者が探索済みの位置を特定する位置情報であり、探索者が携帯する移動体情報端末の位置として移動体位置計測装置から得られてもよいし、探索者等の探索履歴等として入力される単数又は複数の位置情報でもよい。

本発明の移動体位置推定システム／ステップは、捜索者が被捜索者を探索する場合などに使用される。上記第１の移動体は情報端末を携帯する被捜索者であり、第２の移動体は探索者である。探索に際しては、探索者がいる位置や探索済みの位置には、被探索者の存在する確率が低いため、これらの位置については被探索者がいる確率を低くする。すなわち、この発明によれば、第１のサンプリング手段／ステップにより、第１の移動体の位置情報を用いて地図データの座標系の各位置に第１の移動体が存在する確率を算出し、その確率に応じて第１の移動体用のパーティクルをサンプリングする。そして、第２のサンプリング手段／ステップにより、第２の移動体の位置情報によって特定される位置における第１の移動体が存在する確率が、他の位置における第１の移動体が存在する確率と比較して低くなるように、地図データの座標系の各位置に第１の移動体が存在する確率を算出し、その確率に応じて第１の移動体用のパーティクルをリサンプリングする。これにより、探索者が存在する位置や探索済みの位置については、被捜索者が存在する確率を低くすることができ、探索者の位置をも考慮した位置推定を行うことができる。

前記第２のサンプリング手段／ステップは、前記地図データの座標系の各位置に第１の移動体が存在する確率として、前記第２の移動体の位置情報から地図データの座標系の各位置に当該第２の移動体が存在する確率を算出し、当該算出された確率の逆数を用いることが好ましい。

この発明によれば、第２のサンプリング手段／ステップは、取得した第２の移動体の位置情報から第２の移動体が存在する確率を算出し、算出された確率の逆数を求める。そして、この逆数を第１の移動体が存在する確率として用い、この逆数に応じて第１の移動体用のパーティクルをリサンプリングする。これにより、被探索者の位置の推定に、探索者の位置をより詳細に反映させることができる。

前記位置推定手段／ステップは、前記第２のサンプリング手段／ステップによりサンプリングした第１の移動体用パーティクルをクラスタリングし、各クラスターの平均値を当該第１の移動体の推定位置とすることが好ましい。算出される推定位置は単数でも良いし複数でも良い。

すべての第１の移動体用パーティクルから移動体の位置を推定した場合、移動体位置計測装置からの位置情報の誤差が大きいときには、推定確率の分散が大きくなり、推定精度が低くなる。本発明によれば、第１の移動体用パーティクルをクラスタリングし、各クラスターの平均値を推定位置とするため、各クラスター内の推定確率の分散を抑えることができ、推定精度を高めることができる。

本発明の移動体位置推定システム／方法は、スタート地点が与えられると、当該スタート地点から、前記位置推定手段／ステップにより算出された第１の移動体の推定位置を巡回可能な巡回経路を算出する巡回経路算出手段／ステップを備えることが好ましい。

本発明によれば、巡回経路算出手段／ステップは、与えられたスタート地点から出発して推定位置を巡回する巡回経路を算出するため、探索者は算出された巡回経路に従って推定位置を巡回することで被探索者を探索することができる。

前記巡回経路算出手段／ステップは、各巡回経路ごとに、下記数１により評価置Ｖを求め、各巡回経路を当該評価値Ｖに応じて順位付けすることが好ましい。

Ｒｏｕｔｅは評価値Ｖを求めようとする経路における推定位置ｒ（スタート地点を除く各地点）の集合であり、ｒはその推定位置の１つを示す。Ｔ（ｒ）は、推定位置ｒに到達するまでの１つ前の地点（スタート地点又は推定位置）からの時間を求める関数である。Ｐ（ｒ）は、推定位置ｒの１つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。

本発明によれば、巡回経路算出手段／ステップは、上記数１により巡回経路を順位付けすることにより、各推定位置における第１の移動体が存在する確率と、推定位置を巡回するために必要な時間との二つの観点から、巡回経路を順位付けすることができる。これにより、探索者に対して速く且つ確実に被探索者を探索できる巡回経路を提示することができる。

本発明に係る移動体位置推定ステム／方法によれば、第１のサンプリング手段／ステップにより、第１の移動体の位置情報を用いて地図データの座標系の各位置に第１の移動体が存在する確率を算出し、その確率に応じてパーティクルをサンプリングする。その後に、第２のサンプリング手段／ステップにより、第１の移動体が存在する確率を、第２の移動体の位置情報により特定される位置のほうが他の位置よりも低くなるように算出し、その確率に応じてパーティクルをリサンプリングする。これにより、探索者等が存在する位置や探索済みの位置については、被捜索者等が存在する確率を低くすることができ、探索者の位置や探索履歴を考慮した被探索者の位置の推定が可能となる。

また、上記第２のサンプリング手段／ステップは、前記第２の移動体の位置情報から地図データの座標系の各位置に当該第２の移動体が存在する確率を算出し、当該算出された確率の逆数を算出し、この逆数を前記地図データの座標系に第１の移動体が存在する確率として用いる。逆数を用いることにより、被探索者の位置推定に探索者の位置をより詳細に反映させることができる。

また、位置推定手段／ステップは第１の移動体用パーティクルをクラスタリングし、各クラスターごとの平均値を推定位置とすれば、推定確率の分散を抑えることができ、推定精度を向上させることができる。また、複数の推定位置を出力可能であり、より多くの情報を探索者に与えることができる。

また、巡回経路算出手段／ステップが、被探索者の推定位置を巡回する巡回経路を算出すれば、探索者は算出された巡回経路に従って巡回することで被探索者を探索することができる。

また、巡回経路算出手段／ステップが、上記数１により巡回経路を順位付けすれば、各推定位置に被探索者が存在する確率と、推定位置を巡回するために必要な時間との二つの観点から、探索者が被探索者を探索するのに有効な順序で巡回経路を順位付けすることができる。高い順位の巡回経路で巡回することにより、探索者は効率的に推定位置を巡回することができ、より早く被探索者を発見することが可能となる。

本発明は、様々な分野に応用可能であり、例えばＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索するのに用いたり、登下校中の児童の位置を把握し、緊急時には駆けつけて安全を確保したりするのに用いることができる。

（第１の実施の形態）
本実施の形態の移動体位置推定システム１は、移動体位置計測装置から移動体の位置情報を取得し、当該移動体の位置情報に応じて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを有し、パーティクルフィルタによりサンプリングしたパーティクルを用いて移動体の位置を推定するシステムである。

図１は、本発明の第１の実施の形態による移動体位置推定システム１の一構成を示すブロック図である。本実施の形態による移動体位置推定システム１は、内部バス１１に、通信インタフェース１２、ＣＰＵ１３、ＲＯＭ１４、ＲＡＭ１５、ディスプレイ１６、キーボード／マウス１７、ドライブ１８、ハードディスク１９を接続させ、アドレス信号、制御信号、データ等を伝送させ、本実施の形態による移動体位置推定システム１を実現するコンピュータシステムとしての構成を備えている。

通信インタフェース１２は、移動体位置計測装置との通信やインターネット等の通信網に接続する各種通信機能を有しており、移動体位置計測装置から移動体の位置情報を受信したり、本発明に係る位置推定をコンピュータに実行させるプログラム１９ａや地図データ１９ｃをダウンロードしたりすることも可能である。ＣＰＵ１３は、ＲＯＭ１４に格納されたＯＳにより装置全体の制御を行うとともにハードディスク１９に格納された各種のアプリケーションプログラム１９ａに基づいて処理を実行する機能を司る。

ＲＯＭ１４は、ＯＳ等のように装置全体の制御を行うためのプログラムを格納しており、これらをＣＰＵ１３に供給する機能を有している。ＲＡＭ１５は、ＣＰＵ１３による各種プログラムの実行時にワークエリアとして利用されるメモリ機能を有している。

ディスプレイ１６は、地図データや確率データや推定位置をグラフィカルに表示したりする機能を有している。キーボード／マスス１７は、文字、数字、記号等のデータを入力したり、画面上のポイント位置を操作することが可能である。

ドライブ１８は、各種のプログラム、データを記録したＣＤ、ＤＶＤ等の記録媒体からインストール作業を実行するための駆動ユニットである。コンピュータを移動体位置推定システム１として機能させるプログラム１９ａや地図データ１９ｃを記憶媒体からインストールしたりすることも可能である。

ハードディスク１９は、プログラム１９ａ、メモリ１９ｂ、地図データ１９ｃ等の各種データを記憶する外部記憶装置である。プログラム１９ａは、前述した通信インタフェース１２、ドライブ１８等からインストールされたプログラムを実行形式で記憶したものに相当する。メモリ１９ｂは、各種プログラムの実行結果等のファイルを保存する記憶部である。

地図データ１９ｃは、例えば図２に示すように、経度・緯度で表される座標系に建物・道路・河川等や、都道府県、市町村、住所などの領域や、位置、方角、距離等の基本データＤ１が含まれている。

地図データ１９ｃには、基本データＤ１の各領域に対応するように移動体が存在する確率を示す確率データＤ２が含まれていてもよい。確率データＤ２は、例えば、図２に示すように、建物がカテゴリａ、道路がカテゴリｂ、河川がカテゴリｃ、その他がカテゴリｄというように領域がカテゴリに分けられており、カテゴリごとに確率が設定されている。この確率は推定対象となる第１の移動体がその領域に存在する確率である。推定対象として人が携帯する端末であれば、建物のカテゴリａや道路のカテゴリｂの確率は高く、河川のカテゴリｃの確率は低く設定されている。また、カテゴリ分けすることなく、各建物ごとや各道路ごとというように、領域ごとに確率が設定されていても良いし、住所などの人為的に分けられた領域に設定されていても良い。これにより、移動体固有の行動パターンや行動範囲を推定に反映させることができる。確率データＤ２は地図情報１９ｃの一部として一体となっていても良いし、別データとして記憶されていても良い。

確率データＤ２は、後述するステップＳ１の前に行われる事前処理で生成され、ハードディスク１９に記憶されている。確率は予めシステム１内に設定されていても良いし、ユーザにより任意に設定や変更を可能としても良い。たとえば、地図データ１９ｃの基本データＤ１をグラフィカルに表示し、ユーザにより各建物や道路等ごとに確率やカテゴリを事前設定可能とし、この事前設定により確率データＤ２を生成可能としても良い。また、基本データＤ１が建物や道路などの領域を識別する識別情報を含む場合（例えば、建物や道路などが色分けされていたり、マークが付されていたりする場合）、移動体位置推定システム１が、その識別情報を利用して領域をカテゴリ分けし、そのカテゴリを確率データＤ２で用いてもよい。これにより、カテゴリ分けの作業が不要となり、既存の地図データ１９ｃを用いて、領域のカテゴリ分けを簡単に行うことができる。

本発明におけるパーティクルとは、地図データ１９ｃの座標系上の位置を示す指標であり、属性には少なくとも地図データ１９ｃの座標系において位置を特定可能な位置情報を含む。パーティクルフィルタとは、移動体位置計測装置から得られる位置情報を取得すると、地図データ１９ｃの座標系に分散する複数のパーティクルから、上記位置情報に応じてパーティクルをサンプリングする機能を少なくとも備え、本実施の形態においては少なくとも下記のステップＳ１からＳ９を実行する機能を備える。

図３は、移動体位置推定システム１を用いた移動体位置推定方法を説明するフローチャートであり、図４は概念的に説明する説明図である。移動体位置推定システム１はランダムウォーク手段、第１のサンプリング手段、第２のサンプリング手段、位置推定手段を備え、各手段が下記ように機能して、本発明の移動体位置推定方法を実現する。

（ステップＳ１）ランダムウォーク手段は、地図データ１９ｃの第１の座標系のランダムな位置に第１の移動体用のパーティクルを複数配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図４（１）に示すように、複数の第１の移動体用のパーティクル（図４（１）中の灰色の円）がランダムな位置に配置される。

（ステップＳ２）ランダムウォーク手段は、定期的に地図データ１９ｃの第１の座標系に配置されたすべてのパーティクルをランダムに移動（ランダムウォーク）させる。地図データ１９ｃに確率データＤ２を含む場合は、その確率に依存させてすべてのパーティクルをランダムウォークさせる。確率データＤ２は必須ではないが、確率データＤ２を用いることにより、道路や建物や河川といった領域ごとに移動体が存在する確率を反映させることができ、移動体の位置をより高い精度で推定可能となる。パーティクルのランダムウォークは、各パーティクルの位置情報を変更することにより行う。たとえば、図５に示すように、確率データＤ２は、基本データＤ１の緯度経度座標系をピクセル単位に変換し、基本データＤ１でカテゴリａ，ｂ，ｃ，ｄに分けられた各領域にピクセル単位で確率を設定したものとする。そして、パーティクルの移動可能範囲ｅをパーティクルの位置を中心とした一定半径サークル内として設定しておき、パーティクルをランダムウォークさせるときには、移動可能範囲ｅ内のすべてのピクセルの確率データを取得し、その確率に比例させて次の位置を決定し、その位置にパーティクルを移動させる。パーティクルを移動させるタイミングは予め移動体位置推定システム１に設定されており、そのタイミングになると確率データＤ２に従ってパーティクルをランダムウォークさせる。図４（２）は、確率データＤ２に従ってパーティクルをランダムウォークさせたときの状態を概念的に示す説明図である。建物や道路等の確率の高い領域に多くのパーティクルが配置される。

（ステップＳ３）移動体位置計測装置から第１の移動体の位置情報を取得しない間は、ステップＳ２に戻り上記ランダムウォークを続ける。移動体位置計測装置から第１の移動体の位置の情報を取得した場合は、ステップＳ４に進む。

（ステップＳ４）第１のサンプリング手段は、第１の移動体の位置情報を取得すると、取得した位置情報を用いて、地図データ１９ｃの座標系上の各位置に第１の移動体が存在する確率を算出する。確率の算出は、例えば取得した位置情報を確率分布Ｐ１（ｘ）に変換することにより行う。移動体位置計測装置からの位置情報の形式は、その装置の特性によって異なるので、装置に応じた確率分布Ｐ１（ｘ）に変換する必要がある。このため、移動体位置推定システム１には移動体位置計測装置ごとに予め数式等による変換規則が設定されており、位置情報から確率分布Ｐ１（ｘ）への変換はその規則に従い行う。例えば、ＧＰＳの場合は緯度経度情報を出力するので、取得した緯度経度情報を平均とした正規分布に変換する。また、ＰＨＳは各地に所在する基地局のどの基地局で端末からのデータを受信したかで位置が特定される。このため、移動体からの電波を受信した基地局が電波を受信できる範囲内は、移動体が存在する確率が一様であり、その他の範囲は確率が０である。そこで、ＰＨＳから位置情報を取得した場合は、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値とし、その他の領域は確率を０とする一様分布に変換する。

（ステップＳ５）算出された確率に従って、地図データ１９ｃにランダムウォークする第１の移動体用のパーティクルの母集団からパーティクルをサンプリングする。図４（３）は第１の移動体用のパーティクルのサンプリングを概念的に説明する説明図である。サンプリングの方法は、まず、ステップＳ４にて算出された確率分布Ｐ１（ｘ）に従って１つのパーティクルを第１の移動体用のパーティクルの母集団から抽出して記憶し、それを母集団に戻して再び同様に次のパーティクルを抽出する。それを繰り返すことにより、第１の移動体用のパーティクルの母集団と同じ数のパーティクルを確率分布Ｐ１（ｘ）に従って抽出する。図６（ａ）は、ＧＰＳの位置情報を用いたときの確率分布Ｐ１（ｘ）と、地図データ１９ｃの座標系にランダムウォークするパーティクルの母集団と、サンプリングされたパーティクルとを説明する説明図である。横軸の上に並んでいる長方形が個々のパーティクルを表している。取得した位置情報を平均とした確率分布Ｐ１（ｘ）に従って、母集団からパーティクルが抽出される。パーティクルは、確率分布Ｐ１（ｘ）の値の高いところがより多く抽出され、低いところほど抽出されにくい。正規分布の場合、パーティクルは取得した第１の移動体の位置情報により特定される位置（すなわち確率分布Ｐ１（ｘ）の平均値）に最も近いところが多く抽出されやすく、遠いところほど抽出されにくい。

（ステップＳ６）第２の移動体の位置情報を取得した場合は、ステップＳ７に進む。

（ステップＳ７）第２のサンプリング手段は、第２の移動体の位置情報により特定される位置における第１の移動体が存在する確率が、他の位置における第１の移動体が存在する確率と比較して低くなるように、地図データ１９ｃの座標系の各位置に第１の移動体が存在する確率を算出する。

地図データ１９ｃの座標系の各位置に第１の移動体が存在する確率は、次のように算出する。まず、取得した第２の移動体の位置情報を確率分布Ｐ２（ｘ）に変換する。第２の移動体の位置情報を移動体位置計測装置から取得した場合、確率分布Ｐ２（ｘ）へ変換する。変換方法はステップＳ４と同じである。捜索者等がキーボード等の入力手段により第２の移動体の位置情報を入力した場合は、入力された位置情報を取得し、その位置情報により特定される位置に第２の移動体が存在する確率を０より大とし、その他の領域は確率を０とする確率分布に変換する。入力される位置情報は、捜索者がその時点でいる位置の情報でもよいし、捜索者の捜索履歴である複数の位置情報でもよい。

（ステップＳ８）つぎに、上記第２の移動体の存在する確率を用いて、地図データ１９ｃの座標系の各位置に第１の移動体が存在する確率を算出する。探索時には探索者がいる場所には被探索者がいない確率が高いことから、第２の移動体の位置情報により特定される位置における第１の移動体が存在する確率が、他の位置における第１の移動体が存在する確率と比較して低くなるようにする。たとえば、算出された確率分布Ｐ２（ｘ）の逆数Ｐ３（ｘ）を算出する。

（ステップＳ９）ステップＳ８にて算出された逆数Ｐ３（ｘ）に応じて、ステップＳ５にてサンプリングした第１の移動体用のパーティクルを再度サンプリング（リサンプリング）する。リサンプリング方法はステップＳ５と同様である。図６（ｂ）は、ＧＰＳの位置情報を用いたときの確率分布Ｐ２（ｘ）と、その逆数Ｐ３（ｘ）と、リサンプリングされたパーティクルとを説明する説明図である。図４（４）は、逆数Ｐ３（ｘ）に応じてリサンプリングされたパーティクルの分散を概念的に説明する説明図である。確率分布Ｐ２（ｘ）が正規分布の場合、パーティクルは取得した第２の移動体の位置情報により特定される位置に最も近いところほど抽出されにくく、遠いほど抽出されやすい。これにより、探索者が存在する位置や探索済みの位置については、被捜索者が存在する確率を低くすることができ、探索者の位置を被探索者の位置推定に反映させることができる。

（ステップＳ１０）位置推定手段は、ステップＳ９にてリサンプリングされた第１の移動体用のパーティクルをクラスタリングする。図４（５）はパーティクルのクラスタリングを概念的に説明する説明図である。サンプリングされたパーティクルは複数のクラスターにクラスタリングされる。ここで、本実施の形態のクラスタリングについて説明する。本実施の形態のクラスタリングには、正規混合分布Ｐ（ｘ）を用いたクラスタリング手法を用いる。正規混合分布Ｐ（ｘ）とは数２に示される確率分布である。数２のＰｉ（ｘ）は正規分布を表す。この数２における正規分布の数ｃと各正規分布の重みα_i、および各正規分布Ｐｉ（ｘ）の平均値と分散を求めることがクラスタリング処理にあたる。本実施の形態では、これらの値を総じて、正規混合分布Ｐ（ｘ）のパラメータと呼ぶこととする。クラスタリングによって生成されるクラスターは、正規混合分布Ｐ（ｘ）を構成する個々の正規分布Ｐｉ（ｘ）に対応する。正規混合分布Ｐ（ｘ）のパラメータが求まると、数２によって各パーティクルがどのクラスターに所属するかを確率的に得ることが可能となる。さらに、地図データ１９ｃの座標系の任意の位置を入力として与えると、その位置に移動体が存在する確率を求めることができるようになる。

図７に、正規混合分布Ｐ（ｘ）によるクラスタリング例を示す。横軸の上に並んでいる長方形が個々のパーティクルを表している。Ｐ（ｘ）は正規混合分布を表す。個々のパーティクルから求められた正規混合分布Ｐ（ｘ）は、パーティクルが集まっているところほど、確率が高く（山が高く）なっている。この例では２つのクラスターが生成されている。

すなわちステップＳ１０において位置推定手段は、以下のように動作する。数２は移動体位置推定システム１に予め設定されており、位置推定手段は、ステップＳ９にてリサンプリングしたパーティクルの情報を用いて、数２の各パラメータ数ｃと各正規分布の重みα_i、及び、正規分布Ｐｉ（ｘ）の平均値と分散を算出する。各正規分布Ｐｉ（ｘ）の重みα_i、および正規分布Ｐｉ（ｘ）の平均値と分散については、個々のパーティクルが所属するクラスターを隠れ変数としたＥＭアルゴリズムに基づいて算出する。ＥＭアルゴリズムとは、隠れ変数がある場合の最尤推定方法として広く知られている手法であり、繰り返し計算を行うことで、解が収束することが証明されている。一方、正規混合分布Ｐ（ｘ）の数ｃについては、初期値を１として数３に示される正規混合分布Ｐ（ｘ）における各パーティクルの対数尤度の値が減少するまで１つずつ加算して求める。算出された各正規分布Ｐｉ（ｘ）の平均値が第１の移動体の推定位置の座標（ｘ、ｙ）となる。

さらに、移動体位置推定システム１は、各推定位置（ｘ、ｙ）における第１の移動体が存在する確率Ｐ（ｘ）を算出してもよい。この場合、上記算出された各パラメータを数２に代入し、上記算出された各推定位置の座標（ｘ、ｙ）を数２の入力情報（ｘ）とし、Ｐ（ｘ）を計算する。

なお、クラスタリング方法は、上記に限られるものではなく、あらかじめ固定された数のクラスターに分類する非階層的クラスタリングでも良いし、互いの距離の近いものから順にクラスターを融合していくことにより、適当な数のグループに分割するＣ−Ｍｅａｎｓ法などの階層的クラスタリングでも良いし、クラスタリング方法は限定されない。

（ステップＳ１１）ステップＳ１０にて算出された各クラスターの平均値、すなわち、各正規分布Ｐｉ（ｘ）の平均値を推定位置（ｘ，ｙ）として出力する。図４（５）は各クラスターの平均値を概念的に説明する説明図である。算出された推定位置が複数の場合は、各推定位置（ｘ，ｙ）に確率を表示したり、推定位置（ｘ，ｙ）を確率の高い順に順位付けして出力してもよい。出力先はディスプレイ１６でも良いし、通信インタフェイス１２からネットワークを介して接続可能な情報端末（例えば携帯電話等）に出力しても良い。また、算出された複数の推定位置のすべてを出力してもよいし、確率順に上位数個を出力するようにしてもよい。

パーティクルをクラスタリングして位置推定を行うため、クラスター内の推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置が唯一に出力される従来技術と比較して、本発明は推定位置として複数の候補を得ることができる。たとえば、ユーザが移動体を捜索している場合は、複数の候補地を捜索することが可能となる。

（第２の実施の形態）
移動体位置推定システム１が徘徊老人の探索などに使用される場合、探索者は被探索者が見つかるまで複数の推定位置を巡回する必要がある。そこで、移動体位置推定システム１は、複数の推定位置の巡回経路を算出する巡回経路算出手段を備えてもよい。図８は本実施の形態の位置推定処理を説明するフローチャートであり、図９は概念的に説明する説明図である。第１の実施の形態と同様の部分については説明を省略する。

（ステップＳ１）地図データ１９ｃの第１の座標系のランダムな位置に第１の移動体用のパーティクルと第２の移動体用のパーティクルを各々複数配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図９（１）に示すように、複数の第１の移動体用のパーティクル（図９（１）中の灰色の円）と複数の第２の移動体用のパーティクル（図９（１）中の白色の円）がランダムな位置に配置される。

（ステップ２からステップ１１）ステップ２からステップ１１までは上記第１の実施の形態と同様である。

（ステップＳ１２からステップＳ１３）巡回経路の算出のステップＳ１４よりも前までに巡回のスタート地点が入力される。スタート地点は、探索者等が任意に入力可能としてもよいし、探索者が携帯する情報端末のＧＰＳ等の機能を用いて移動体位置計測装置から得られる位置情報が入力されても良い。本実施の形態では、スタート地点として、移動体位置計測装置から得られた第２の移動体の位置情報を利用する場合（ステップＳ１２とステップＳ１３）を例に説明する。

（ステップＳ１２）巡回経路算出手段は、ステップＳ７で得られた確率分布Ｐ２（ｘ）に基づいて、地図データ１９ｃの第１の座標系に分布する第２の移動体用のパーティクルをサンプリングする。サンプリングの方法は、第１の移動体用のパーティクルのサンプリング方法と同じである。図９（４）は第２の移動体用のパーティクルのサンプリングを概念的に説明する説明図である。第２の移動体の位置情報に近いパーティクルが高い確率で抽出される。

（ステップＳ１３）抽出された第２の移動体用のパーティクルの平均値を算出する（図９（５））。この平均値をスタート地点とする。

（ステップＳ１４）巡回経路算出手段は、スタート地点の位置情報と、上記算出した複数の推定位置やその推定位置に移動体が存在する確率から、探索者が移動体に到達する可能性が高く、且つ、短時間に巡回できる経路を算出する。

たとえば、巡回経路算出手段は、次のように巡回経路を算出する。まず、スタート地点から推定位置（すなわち、推定位置を表す正規混合分布を構成する各正規分布の頂点）をすべて巡回する経路を探索する。正規混合分布を構成する正規分布の数をＣとすると、経路はその階乗Ｃ！だけ存在する。これらの経路を評価する関数として、下記数１を用いる。

Ｒｏｕｔｅは評価値Ｖを求めようとする経路における推定位置ｒ（スタート地点を除く各地点）の集合であり、ｒはその推定位置の１つを示す。Ｔ（ｒ）は、推定位置ｒに到達するまでの１つ前の地点（スタート地点又は推定位置）からの時間を求める関数である。Ｐ（ｒ）は、推定位置ｒの１つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。評価値Ｖの値が小さいほど、効率的な巡回経路であるといえる。

図１０は、数１の一実施例をグラフで表した図である。図１０の横軸は時間、縦軸はその移動体が存在しない確率（数３における１−Ｐ（ｘ））、すなわち、探索者が被探索者を発見できない確率を示している。ここでは、正規混合分布を構成する正規分布の数（すなわち推定位置の数）Ｃ＝３を例に説明する。すべての経路について次の処理を行う。スタート地点ｓから一つ目の正規分布の頂点（推定位置）ｐ１に達するときに必要な時間と、その到達した頂点（推定位置）ｐ１に移動体を発見できない確率を算出する。さらに、一つ目の頂点（推定位置）ｐ１から次の頂点（推定位置）ｐ２に達するときに必要な時間と、その到達した頂点ｐ２における移動体を発見できない確率を算出する。このように、スタート地点から巡回する経由地点順に時間と得点を算出する。そして、横軸を時間、縦軸を移動体を発見できない確率として、算出された各頂点（推定位置）の時間と移動体が存在しない確率をプロットし、その積分値（図１０の斜線部分の面積）の大きさが評価値Ｖとなる。これにより、第１の移動体を発見できる確率と巡回時間とを考慮した評価が可能となる。巡回経路の出力に際しては、評価値Ｖが低い経路のみを提示してもよいし、評価値順に順位付けしてすべての巡回経路を出力しても良い。

一例として、図１１（ａ）のように、移動体位置推定の結果、ａ，ｂ，ｃの三つの推定位置が得られた場合の巡回経路の算出を説明する。スタート地点は座標（０，０）であり、推定位置ａは座標（５，０）、ｂは座標（４，３）、ｃは座標（０，５）の位置であり、各推定位置における移動体が存在する確率がａは０．５，ｂは０．１，ｃは０．４であったとする。すべての巡回経路について上記評価値Ｖを算出した結果を図１１（ｂ）に示す。ａ−ｂ−ｃの順で巡回する経路が最も高い評価値であるという結果が得られ、有効な巡回経路としてａ−ｂ−ｃが出力される。

これにより、探索者は、出力された複数の推定位置を効率的に巡回できる経路の情報を得ることができる。たとえば、徘徊老人の探索においては、効率的に巡回することにより、より迅速に徘徊老人を見つけ出し、安全を確保することができる。

なお、本発明は、上記実施の形態に限られるものではなく、本発明から逸脱しない範囲内で変更が可能である。たとえば、位置推定にクラスタリングを用いることなく、従来のようにパラメータの最尤推定を行う技術に適用しても良い。この場合、移動体位置推定システム１は以下のように処理を行う。図１２は、そのフローチャートである。移動体位置推定システムは、上記ステップ１からステップ９を行った後、サンプリング結果からパラメータ最尤推定を行って確立分布を算出し、得られた確率分布から推定位置を算出し（ステップＳ１０）、推定位置を出力する（ステップＳ１１）。パラメータ最尤推定や、確率分布からの推定位置の算出は、位置計測装置の種類に応じて行えばよい。例えばＧＰＳであればパラメータ最尤推定を行って正規分布を算出し、その正規分布の平均値を推定位置として出力する。また、ＰＨＳの場合は、ステップＳ４において、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値（０より大）とし、その他の範囲は確率を０とする一様分布データに変換される。ステップ４以外は、ＰＨＳであってもＧＰＳであっても同じ処理である。

また、本発明は、様々な分野に応用可能である。たとえば、ＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保するのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。

本発明の第１の実施の形態による移動体位置推定システムの一構成を示すブロック図である。 地図データを概念的に説明する説明図である。 上記実施の形態における移動体位置推定システムを用いた移動体位置推定方法を説明するフローチャートである。 上記実施の形態の位置推定処理を概念的に説明する説明図である。 上記実施の形態において確率データの設定を説明する説明図である。 （ａ）は、ＧＰＳの位置情報を用いたときの確率分布Ｐ１（ｘ）と、地図データの座標系上に分散するパーティクルの母集団と、抽出されたパーティクルとを説明する説明図である。（ｂ）は、ＧＰＳの位置情報を用いたときの確率分布Ｐ２（ｘ）と、その逆数Ｐ３（ｘ）と、リサンプリングされたパーティクルとを説明する説明図である。 パーティクルフィルタにより抽出されたパーティクルの確率分布を正規混合分布によって表す例を示す説明図である。 第２の実施の形態の処理を説明するフローチャートである。 上記実施の形態の位置推定処理を概念的に説明する説明図である。 上記実施の形態の巡回経路の算出に用いる関数を説明する説明図である。 上記実施の形態の巡回経路の算出の例を示す説明図である。 他の実施の形態の処理を説明するフローチャートである。

符号の説明

１ 移動体位置推定システム
１９ｃ 地図データ
Ｄ１ 基本データ
Ｄ２ 確率データ

Claims (10)

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

   

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

    

    Ｒｏｕｔｅは評価値Ｖを求めようとする経路における推定位置ｒ（スタート地点を除く各地点）の集合であり、ｒはその推定位置の１つを示す。Ｔ（ｒ）は、推定位置ｒに到達するまでの１つ前の地点（スタート地点又は推定位置）からの時間を求める関数である。Ｐ（ｒ）は、推定位置ｒの１つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。

Images