移動体位置推定システム、及び、移動体位置推定方法
【課題】 移動体の位置を高い精度で推定可能な移動体位置推定システム及び移動体位置推定方法を提供する。
【解決手段】 移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システム及び移動体位置推定方法であり、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させることにより、移動体の位置を高い精度で推定する。
【解決手段】 移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システム及び移動体位置推定方法であり、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させることにより、移動体の位置を高い精度で推定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体位置計測装置から得られる位置情報を使用して、移動体の位置を推定する移動体位置推定システム、及び、移動体位置推定方法に関する。
【背景技術】
【０００２】
近年、ＧＰＳなどの移動体位置計測装置によって、移動体の位置情報を取得することが容易に可能となってきた。しかし、その位置情報は精度が低く、移動体位置計測装置単体では数十メートルから数百メートルの誤差が発生するのが現状である。
【０００３】
その不確実性を軽減するために、移動体位置計測装置から得た位置情報に基づいて、コンピュータにより移動体の位置を推定する移動体位置推定システムが用いられている。下記非特許文献１には、移動体位置推定システムにパーティクルフィルタを用いて位置を確率的に扱う技術が提案されている。パーティクルフィルタとは、複数個のパーティクルの重み付き総和によって全体の確率分布を近似する手法であり、位置の推定は次のように行われる。（１）地図データの座標系上のランダムな位置にＮ個のパーティクルを生成する。（２）パーティクルをランダムウォークさせる。（３）移動体位置計測装置からの位置情報を確率分布として示す。（４）確率分布に従って個々のパーティクル位置の生起確率を求める。（５）生起確率に比例させて、各パーティクルの重みを更新する。（６）各パーティクルの重みと位置とから移動体の位置について正規分布を最尤推定する。（７）正規分布の平均を移動体の位置と推定する。
【非特許文献１】Ｊ．Ｈｉｇｈｔｏｗｅｒ，Ｂ．Ｂｏｒｒｉｅｌｌｏ．“Ｔｈｅ Ｌｏｃａｔｉｏｎ Ｓｔａｃｋ：Ａ Ｌａｙｅｒｄ Ｍｏｄｅｌ ｆｏｒ Ｌｏｃａｔｉｏｎ ｉｎ Ｕｂｉｑｕｉｔｏｕｓ Ｃｏｍｐｕｔｉｎｇ”，４ｔｈ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｏｄｉｌｅ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ ＆ Ａｐｐｌｉｃａｔｉｏｎｓ （ＷＭＣＳＡ ２００２），ｐｐ．２２−２８．２００２．
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記従来技術は、移動体の位置を移動体位置計測装置からの測定値のみで推定しているため、推定精度は移動体位置計測装置に依存してしまう。現在の移動体位置計測装置による位置測定は、数十メートルから数百メートルの誤差を含んでいるため、位置推定にもその誤差が影響してしまい、精度の良い推定を行うことが困難であった。また、パーティクルから一つの正規分布を求め、その平均を移動体の位置と推定するため、出力される推定位置は一つである。移動体位置計測装置の誤差が大きいときは、一つの推定値に集約すると推定確率の分散が大きくなり、推定精度が低くなってしまう。
【０００５】
そこで、本発明は、移動体の位置を高い精度で推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の移動体位置推定システムは、移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システムにおいて、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させる手段を備えることを特徴とする。また、本発明の移動体位置推定方法は、コンピュータが、移動体位置計測装置から移動体の位置情報を取得すると、パーティクルフィルタにより当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングし、当該サンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定方法において、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを参照し、当該確率データに従って当該地図データの座標系にパーティクルを分散させるステップを備えることを特徴とする。
【０００７】
ここで、領域とは、建物や道路や河川といった物理的に区別される領域でも良いし、住所といった人為的に定められた領域でも良いし、ユーザが任意に設定した領域でも良い。地図上の各領域に移動体が存在する確率データは、ユーザにより任意に設定可能としてもよいし、予めシステム内に設定されていてもよい。
【０００８】
移動体が存在する確率は、例えば人が携帯する情報端末であれば、道路や建物が高く、河川や山中は低いなど、領域によって異なる。また、移動体の移動パターンや移動範囲によっても異なる場合がある。本発明によれば、地図上の各領域に移動体が存在する確率を示す確率データを参照し、その確率に応じてパーティクルを移動させるため、その確率を反映させた位置の推定が可能となる。
【０００９】
また、前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることが好ましい。
【００１０】
各領域における移動体が存在する確率は、例えば、移動体が人であれば建物や道路が高く河川は低く、また、移動体が船舶であれば河川が高く陸地は低いというように、領域ごとに区別できる。この発明によれば、前記確率データは、各領域をカテゴリ分けし、そのカテゴリごとに確率を設定することが可能となっているため、移動体に応じて各領域の確率を容易に設定することができる。
【００１１】
また、前記地図データには前記各領域を識別する識別情報が含まれており、前記確率データは、当該識別情報を用いて前記各領域がカテゴリ分けされていることが好ましい。
【００１２】
地図は道や建物や川などの領域ごとに色分けされたり、マークが付されたりして、各領域を識別する識別情報が付されていることが多い。この発明によれば、確率データは、これらの識別情報を利用してカテゴリが分けられるため、既存の地図データを用いて簡単にカテゴリ分けを行うことができる。
【００１３】
前記移動体位置推定システム／方法は、 前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力する手段／ステップを備えることが好ましい。
【００１４】
パーティクル全体から移動体の位置を推定した場合、移動体位置計測装置からの位置情報の誤差が大きいときには、推定確率の分散が大きくなり、推定精度が低くなる。この発明によれば、パーティクルをクラスタリングし、各クラスターの平均値を推定位置とするため、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。
【発明の効果】
【００１５】
本発明に係る移動体位置推定ステム／方法によれば、道路や建物や河川といった領域ごとに移動体が存在する確率を示す確率データを有し、移動体の位置推定に際しては、その確率データを反映させるため、移動体の位置をより高い精度で推定可能となる。
【００１６】
確率データの領域を例えば道路や河川などのようにカテゴリに分け、カテゴリごとに確率を設定可能とすれば、推定対象となる移動体に適する確率を容易に設定することができる。確率データを生成する処理は、カテゴリ分けを地図の各領域に付される識別情報を利用して行うことにより、既存の地図情報を用いて簡単にカテゴリ分けを行うことができる。
【００１７】
また、パーティクルをクラスタリングし、各クラスターの平均値を移動体の位置として出力することにより、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置として複数の候補を得ることができる。たとえば、移動体を捜索する場合、従来技術のように推定位置が唯一に出力されると捜索場所も一つに限られてしまう。本システム／方法によれば、複数の場所を候補として捜索できるため発見できる可能性も高まる。
【００１８】
本発明は、様々な分野に応用可能である。たとえば、ＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保したりするのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。
【発明を実施するための最良の形態】
【００１９】
本実施の形態の移動体位置推定システム１は、移動体位置計測装置から得られる位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定するシステムである。
【００２０】
図１は、本発明の第１の実施の形態による移動体位置推定システム１の一構成を示すブロック図である。本実施の形態による移動体位置推定システム１は、内部バス１１に、通信インタフェース１２、ＣＰＵ１３、ＲＯＭ１４、ＲＡＭ１５、ディスプレイ１６、キーボード／マウス１７、ドライブ１８、ハードディスク１９を接続させ、アドレス信号、制御信号、データ等を伝送させ、本実施の形態による移動体位置推定システムを実現するコンピュータシステムとしての構成を備えている。
【００２１】
通信インタフェース１２は、移動体位置計測装置との通信やインターネット等の通信網に接続する各種通信機能を有しており、移動体位置計測装置から移動体の位置情報を受信したり、本発明に係る位置推定をコンピュータに実行させるプログラム１９ａや地図データ１９ｃをダウンロードしたりすることも可能である。ＣＰＵ１３は、ＲＯＭ１４に格納されたＯＳにより装置全体の制御を行うとともにハードディスク１９に格納された各種のアプリケーションプログラム１９ａに基づいて処理を実行する機能を司る。
【００２２】
ＲＯＭ１４は、ＯＳ等のように装置全体の制御を行うためのプログラムを格納しており、これらをＣＰＵ１３に供給する機能を有している。ＲＡＭ１５は、ＣＰＵ１３による各種プログラムの実行時にワークエリアとして利用されるメモリ機能を有している。
【００２３】
ディスプレイ１６は、地図データや確率データや推定位置をグラフィカルに表示したりする機能を有している。キーボード／マウス１７は、文字、数字、記号等のデータを入力したり、画面上のポイント位置を操作することが可能である。
【００２４】
ドライブ１８は、各種のプログラム、データを記録したＣＤ、ＤＶＤ等の記録媒体からインストール作業を実行するための駆動ユニットである。コンピュータを移動体位置推定システム１として機能させるプログラムや地図データを記憶媒体からインストールしたりすることも可能である。
【００２５】
ハードディスク１９は、プログラム１９ａ、メモリ１９ｂ、位置推定に用いられる地図データ１９ｃ等の各種データを記憶する外部記憶装置である。プログラム１９ａは、前述した通信インタフェース１２、ドライブ１８等からインストールされたプログラムを実行形式で記憶したものに相当する。メモリ１９ｂは、各種プログラムの実行結果等のファイルを保存する記憶部である。
【００２６】
地図データ１９ｃは、例えば図２に示すように、基本データＤ１と確率データＤ２とを含む。基本データＤ１は、建物・道路・河川等や、都道府県、市町村、住所などの領域や、位置、経緯度、方角、距離等のデータが含まれている。また、確率データＤ２は、基本データＤ１の各領域に移動体が存在する確率を示す情報が含まれている。確率データＤ２は、建物がカテゴリａ、道路がカテゴリｂ、河川がカテゴリｃ、その他がカテゴリｄというように、領域がカテゴリ分けされており、カテゴリごとに確率が設定されている。この確率はその領域に推定対象となる移動体が存在する確率である。推定対象として人が携帯する情報端末であれば、建物に対応するカテゴリａや道路に対応するカテゴリｂの確率は高く、河川に対応するカテゴリｃの確率は低く設定されている。ただし、確率データＤ２は、カテゴリ分けすることなく、各建物や、各道路ごとというように、領域ごとに確率が設定されていても良いし、住所などの人為的に分けられた領域に設定されていても良い。これにより、移動体固有の行動パターンや行動範囲を確率に反映させることができる。また、確率データＤ２は地図データ１９ｃの一部として一体となっていても良いし、別データとして記憶されていても良い。
【００２７】
確率データＤ２は、後述するステップＳ１の処理前の事前処理で生成され、ハードディスク１９に記憶されている。また、確率データＤ２は予めシステム１内に設定されていても良いし、ユーザが任意に設定や変更を可能としても良い。たとえば、地図データ１９ｃの基本データＤ１をグラフィカルに表示し、各建物や道路等ごとに確率を直接設定可能とし、ユーザが事前設定として確率やカテゴリを設定するようにして確率データＤ２を生成可能としても良い。また、基本データＤ１が建物や道路などの領域を識別する識別情報を含む場合（例えば、建物や道路などが色分けされていたり、マークが付されていたりする場合）、移動体位置推定システム１が、その識別情報を利用して領域をカテゴリ分けし、そのカテゴリを確率データＤ２のカテゴリとしても良い。これにより、人為的なカテゴリ分けが不要となり、既存の地図データを用いて、領域のカテゴリ分けを簡単に行うことができる。
【００２８】
本発明におけるパーティクルとは、地図データ１９ｃの座標系上の位置を示す指標であり、属性には少なくとも地図データ１９ｃの座標系において位置を特定可能な位置情報を含む。本発明におけるパーティクルフィルタとは、移動体位置計測装置から得られる位置情報を取得すると、地図データ１９ｃの座標系に分散する複数のパーティクルから、上記位置情報に応じてパーティクルをサンプリングする機能を少なくとも備えるものであり、本実施の形態においては少なくとも下記のステップＳ１からＳ５を実行する機能を備えるフィルタである。
【００２９】
図３は、移動体位置推定システム１を用いた移動体位置推定方法を説明するフローチャートである。図４は、位置推定処理を概念的に説明する説明図である。移動体位置推定システム１は下記のように機能して、本発明の移動体位置推定方法を実現する。
【００３０】
（ステップＳ１）地図データ１９ｃの座標系のランダムな位置に複数のパーティクルを配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図４（１）に示すように、パーティクル（図中、白円）はランダムな位置に配置される。
【００３１】
（ステップＳ２）地図データ１９ｃの確率データＤ２を参照し、その確率に依存させてすべてのパーティクルを移動（ランダムウォーク）させる。たとえば、図５に示すように、確率データＤ２は、基本データＤ１の緯度経度座標系をピクセル単位に変換し、基本データＤ１でカテゴリａ，ｂ，ｃ，ｄに分けられた各領域にピクセル単位で確率を設定したものとする。そして、パーティクルの移動可能範囲ｅをパーティクルの位置を中心とした一定半径サークル内と設定しておき、パーティクルをランダムウォークさせるときには、移動可能範囲内ｅのすべてのピクセルの確率データを取得し、その確率に比例して次の位置を決定し、その位置にパーティクルを移動させる。パーティクルを移動させるタイミングは予め移動体位置推定システム１に設定されており、そのタイミングになると確率データＤ２に従ってパーティクルをランダムウォークさせる。図４（２）は、確率データに従ってパーティクルをランダムウォークさせたときの状態を概念的に示す説明図である。確率の高い領域に多くのパーティクルが配置される。
【００３２】
（ステップＳ３）移動体位置計測装置から移動体の位置情報を取得しない間は、ステップＳ２に戻り上記ランダムウォークを続ける。移動体位置計測装置から移動体の位置情報を取得した場合は、ステップＳ４に進む。
【００３３】
（ステップＳ４）移動体位置推定システム１は、位置情報を取得すると、その位置情報を確率分布Ｐ１（ｘ）で表されるデータに変換する。位置情報から確率分布Ｐ１（ｘ）への変換は、予め設定されている数式等の規則に従い変換する。移動体位置計測装置からの位置情報の形式は、その機器の特性に応じて異なるので、機器に応じた確率分布に変換する。このため、移動体位置推定システム１には移動体位置計測装置ごとに予め数式等による変換規則が設定されており、位置情報から確率分布Ｐ１（ｘ）への変換はその規則に従い行う。例えば、ＧＰＳの場合は緯度経度情報を出力するので、取得した緯度経度情報を平均とした正規分布に変換する。また、ＰＨＳは各地に所在する基地局のどの基地局で端末からのデータを受信したかで位置が特定される。このため、移動体からの電波を受信した基地局が電波を受信できる範囲内は、移動体が存在する確率が一様であり、その他の範囲は確率が０である。そこで、ＰＨＳから位置情報を取得した場合は、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値（０より大）とし、その他の範囲は確率を０とする一様分布に変換する。
【００３４】
（ステップＳ５）確率分布Ｐ（１）に従って、地図上の母集団からパーティクルをサンプリングする。サンプリングの方法は、まず、その確率分布Ｐ１（ｘ）に従った確率で１つのパーティクルを地図上の母集団から抽出し、それを母集団に戻してから再び同様に次のパーティクルを抽出する。それを繰り返すことにより、母集団と同じ数のパーティクルを確率分布Ｐ１（ｘ）に従って抽出する。図６は、ＧＰＳの位置情報を用いたときの確率分布Ｐ１（ｘ）のデータと、地図データ１９ｃの座標系上の母集団と、抽出されたパーティクルとを説明する説明図である。取得した位置情報を平均とした正規分布データＰ１（ｘ）に従って、母集団からパーティクルが抽出される。パーティクルは、正規分布の頂点（平均）に最も近いところが多く抽出され、遠いところほど抽出されない。図４（３）は、この正規分布によりサンプリングされたパーティクルの分散を概念的に説明する説明図である。パーティクルは、取得した位置情報に最も近いところが多く抽出され、遠いところほど抽出されない。
【００３５】
（ステップＳ６）サンプリングされたパーティクルをクラスタリングする。図４（４）はパーティクルのクラスタリングを概念的に説明する説明図である。サンプリングされたパーティクルは複数のクラスターにクラスタリングされる。ここで、本実施の形態のクラスタリングについて説明する。本実施の形態のクラスタリングには、正規混合分布Ｐ（ｘ）を用いたクラスタリング手法を用いる。正規混合分布とは数１に示される確率分布である。数１のｐｉ（ｘ）は正規分布を表す。この数１における正規分布の数ｃと各正規分布の重みαi、および各正規分布ｐｉ（ｘ）の平均値と分散を求めることがクラスタリング処理にあたる。本実施の形態では、これらの値を総じて、正規混合分布Ｐ（ｘ）のパラメータと呼ぶこととする。クラスタリングによって生成されるクラスターは、正規混合分布Ｐ（ｘ）を構成する個々の正規分布に対応する。正規混合分布Ｐ（ｘ）のパラメータが求まると、数１によって各パーティクルがどのクラスターに所属するかを確率的に得ることが可能となる。さらに、地図上の任意の位置を入力として与えると、その位置に移動体が居る確率を求めることができるようになる。
【数１】
【００３６】
図７に、正規混合分布Ｐ（ｘ）によるクラスタリング例を示す。水平線の上に並んでいる長方形が個々のパーティクルを表している。Ｐ（ｘ）は正規混合分布を表す。個々のパーティクルから求められた正規混合分布Ｐ（ｘ）は、パーティクルが集まっているところほど、確率が高く（山が高く）なっている。この例では２つのクラスターが生成されている。
【００３７】
すなわちステップＳ６において移動体位置推定システム１は、以下のように動作する。数１は移動体位置推定システム１に予め設定されており、移動体位置推定システム１は、ステップＳ５にてサンプリングしたパーティクルの情報を用いて、数１の各パラメータ数cと各正規分布の重みαi、及び、正規分布ｐｉ（ｘ）の平均値と分散を算出する。詳しくは、各正規分布の重みαi、および正規分布ｐｉ（ｘ）の平均値と分散については、個々のパーティクルが所属するクラスターを隠れ変数としたＥＭアルゴリズムに基づいて算出する。ＥＭアルゴリズムとは、隠れ変数がある場合の最尤推定方法として広く知られている手法であり、繰り返し計算を行うことで、解が収束することが証明されている。一方、正規混合分布Ｐ（ｘ）の数ｃについては、初期値を１として数２に示される正規混合分布Ｐ（ｘ）における各パーティクルの対数尤度の値が減少するまで１つずつ加算して求める。図４（５）は各クラスターの平均値を概念的に説明する説明図である。算出された各正規分布ｐｉ（ｘ）の平均値が移動体の推定位置の座標（ｘ、ｙ）となる。
【数２】
【００３８】
さらに、移動体位置推定システム１は、各推定位置（ｘ、ｙ）における移動体が存在する確率Ｐ（ｘ）を算出してもよい。この場合、上記算出された各パラメータを数１に代入し、上記算出された各推定位置の座標（ｘ、ｙ）を数１の入力情報（ｘ）とし、Ｐ（ｘ）を計算する。
【００３９】
なお、クラスタリング方法は、上記に限られるものではなく、あらかじめ固定された数のクラスターに分類する非階層的クラスタリングでも良いし、互いの距離の近いものから順にクラスターを融合していくことにより、適当な数のグループに分割するＣ−Ｍｅａｎｓ法などの階層的クラスタリングでも良いし、クラスタリング方法は限定されない。
【００４０】
（ステップＳ７）ステップＳ６にて算出された複数の推定位置（ｘ，ｙ）を出力する。ステップ６にて、各推定位置（ｘ，ｙ）に対する移動体が存在する確率Ｐ（ｘ）を算出した場合は、各推定位置（ｘ，ｙ）に確率Ｐ（ｘ）を表示したり、推定位置（ｘ，ｙ）を確率Ｐ（ｘ）の高い順に順位付けして出力してもよい。出力先はディスプレイ１６でも良いし、通信インタフェイス１２からネットワークを介して接続可能な情報端末（例えば携帯電話等）に出力しても良い。また、算出された複数の推定位置のすべてを出力してもよいし、確率順に上位数個を出力するようにしてもよい。
【００４１】
移動体位置推定システム１による上記移動体位置推定方法によれば、道路や建物や河川といった領域ごとに移動体が存在する確率データＤ２を反映させるため、移動体の位置をより高い精度で推定可能となる。また、パーティクルをクラスタリングして位置推定を行うため、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置が唯一に出力される従来技術と比較して、本発明は推定位置として複数の候補を得ることができる。たとえば、ユーザが移動体を捜索している場合は、複数の候補地を捜索することが可能となる。
【００４２】
（第２の実施の形態）
また、例えば移動体位置推定システム１が徘徊老人の探索など、移動体の探索に使用される場合は、出力される複数の推定位置を探索者が巡回する必要がある。そこで、移動体位置推定システム１は、複数の推定位置の巡回経路を出力するようにしても良い。巡回経路の出力は次のように行う。図８は本実施の形態の処理を説明するフローチャートである。この巡回経路の処理（ステップＳ６−１）は、上記第１の実施の形態の処理のステップＳ６の終了後に行われ、巡回経路を算出し、推定位置とともに巡回経路の出力を行うことにより実現される。第１の実施の形態と同様の部分については説明を省略する。
【００４３】
移動体位置推定装置１には、巡回経路の算出のステップＳ６−１よりも前までに巡回のスタート地点が入力される。スタート地点は、巡回者が任意に入力可能としてもよいし、巡回者が携帯する情報端末のＧＰＳ等の機能を用いて移動体位置計測装置から得られる位置情報を入力としても良い。移動体位置測定システム１は、スタート地点の位置情報と、上記算出した複数の推定位置やその推定位置に移動体が存在する確率から、巡回者が移動体に到達する可能性が高く、且つ、短時間に巡回できる経路を算出する。
【００４４】
たとえば、移動体位置推定システム１は、次のように巡回経路を算出する。スタート地点から推定位置（すなわち、推定位置を表す正規混合分布Ｐ（ｘ）を構成する各正規分布ｐｉ（ｘ）の頂点）をすべて巡回する経路を探索する。正規混合分布Ｐ（ｘ）を構成する正規分布ｐｉ（ｘ）の数をＣとすると、経路はその階乗Ｃ！だけ存在する。これらの経路を評価する関数として、下記数３を用いる。
【数３】
Ｒｏｕｔｅは評価値Ｖを求めようとする経路における推定位置ｒ（スタート地点を除く各地点）の集合であり、ｒはその推定位置の１つを示す。Ｔ（ｒ）は、推定位置ｒに到達するまでの１つ前の地点（スタート地点又は推定位置）からの時間を求める関数である。Ｐ（ｒ）は、推定位置ｒの１つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。評価値Ｖの値が小さいほど、効率的な巡回経路であるといえる。
【００４５】
図９は、数３の一実施例をグラフで表した図である。図９の横軸は時間、縦軸はその移動体が存在しない確率（数３における１−Ｐ（ｘ））、すなわち、探索者が被探索者を発見できない確率を示している。ここでは、正規混合分布を構成する正規分布の数（すなわち推定位置の数）Ｃ＝３を例に説明する。すべての経路について次の処理を行う。スタート地点ｓから一つ目の正規分布の頂点（推定位置）ｐ１に達するときに必要な時間と、その到達した頂点（推定位置）ｐ１において移動体を発見できない確率を算出する。さらに、一つ目の頂点（推定位置）ｐ１から次の頂点（推定位置）ｐ２に達するときに必要な時間と、その到達した頂点ｐ２における移動体を発見できない確率を算出する。このように、スタート地点から巡回する経由地点順に、時間と移動体を発見できない確率を算出する。そして、横軸を時間、縦軸を移動体を発見できない確率として、算出された各頂点（推定位置）の時間と移動体を発見できない確率をプロットし、その積分値（図９の斜線部分の面積）の大きさが評価値Ｖとなる。これにより、移動体を発見できる確率と巡回時間とを考慮した評価が可能となる。巡回経路の出力に際しては、評価値Ｖが低い経路のみを提示してもよいし、評価値順に順位付けしてすべての巡回経路を出力しても良い。
【００４６】
一例として、図１０（ａ）のように、移動体位置推定の結果、ａ，ｂ，ｃの三つの推定位置が得られた場合の巡回経路の算出を説明する。スタート地点は座標（０，０）であり、推定位置ａは座標（５，０）、ｂは座標（４，３）、ｃは座標（０，５）の位置であり、各推定位置における移動体が存在する確率がａは０．５，ｂは０．１，ｃは０．４であったとする。すべての巡回経路について上記評価値Ｖを算出した結果を図１０（ｂ）に示す。ａ−ｂ−ｃの順で巡回する経路が最も良い評価値であるという結果が得られ、有効な巡回経路としてａ−ｂ−ｃを出力される。
【００４７】
これにより、探索者は、出力された複数の推定位置を効率的に巡回できる経路の情報を得ることができる。たとえば、徘徊老人の探索においては、効率的に巡回することにより、より迅速に徘徊老人を見つけ出し、安全を確保することができる。
【００４８】
なお、本発明は、上記実施の形態に限られるものではなく、本発明から逸脱しない範囲内で変更が可能である。たとえば、確率データを用いて領域ごとに移動体が存在する確率を反映させる技術（ステップＳ２）は、位置推定にクラスタリングを用いることなく、従来のようにパラメータの最尤推定を行う技術に適用しても良い。これによっても、領域ごとの確率が反映され、従来よりも高精度に位置推定が行われる。この場合、移動体位置推定システム１は以下のように処理を行う。図１１は、そのフローチャートである。移動体位置推定システムは、上記ステップ１からステップ５を行った後、サンプリング結果からパラメータ最尤推定を行って確立分布を算出し、得られた確率分布から推定位置を算出し（ステップＳ６）、推定位置を出力する（ステップＳ７）。パラメータ最尤推定や、確率分布からの推定位置の算出は、位置計測装置の種類に応じて行えばよい。例えばＧＰＳであればパラメータ最尤推定を行って正規分布を算出し、その正規分布の平均値を推定位置として出力する。また、ＰＨＳの場合は、ステップ４において、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値（０より大）とし、その他の範囲は確率を０とする一様分布データに変換される。ステップ４以外は、ＰＨＳであってもＧＰＳであっても同じ処理である。
【００４９】
また、本発明は、様々な分野に応用可能である。たとえば、ＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保するのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。
【図面の簡単な説明】
【００５０】
【図１】本発明の第１の実施の形態による移動体位置推定システムの一構成を示すブロック図である。
【図２】地図情報と確率データを概念的に説明する説明図である。
【図３】上記実施の形態における移動体位置推定システムを用いた移動体位置推定方法を説明するフローチャートである。
【図４】上記実施の形態の位置推定処理を概念的に説明する説明図である。
【図５】上記実施の形態において地図情報に対する確率データの設定を説明する説明図である。
【図６】ＧＰＳの位置情報を用いたときの確率分布データと、地図情報上のパーティクルの母集団と、抽出されたパーティクルとを説明する説明図である。
【図７】パーティクルフィルタにより抽出されたパーティクルの確率分布を正規混合分布によって表す例を示す説明図である。
【図８】第２の実施の形態の処理を説明するフローチャートである。
【図９】上記実施の形態の巡回経路の算出に用いる関数を説明する説明図である。
【図１０】上記実施の形態の巡回経路の算出の例を示す説明図である。
【図１１】他の実施の形態の処理を説明するフローチャートである。
【符号の説明】
【００５１】
１ 移動体位置推定システム
１９ｃ 地図データ
Ｄ１ 基本データ
Ｄ２ 確率データ
【技術分野】
【０００１】
本発明は、移動体位置計測装置から得られる位置情報を使用して、移動体の位置を推定する移動体位置推定システム、及び、移動体位置推定方法に関する。
【背景技術】
【０００２】
近年、ＧＰＳなどの移動体位置計測装置によって、移動体の位置情報を取得することが容易に可能となってきた。しかし、その位置情報は精度が低く、移動体位置計測装置単体では数十メートルから数百メートルの誤差が発生するのが現状である。
【０００３】
その不確実性を軽減するために、移動体位置計測装置から得た位置情報に基づいて、コンピュータにより移動体の位置を推定する移動体位置推定システムが用いられている。下記非特許文献１には、移動体位置推定システムにパーティクルフィルタを用いて位置を確率的に扱う技術が提案されている。パーティクルフィルタとは、複数個のパーティクルの重み付き総和によって全体の確率分布を近似する手法であり、位置の推定は次のように行われる。（１）地図データの座標系上のランダムな位置にＮ個のパーティクルを生成する。（２）パーティクルをランダムウォークさせる。（３）移動体位置計測装置からの位置情報を確率分布として示す。（４）確率分布に従って個々のパーティクル位置の生起確率を求める。（５）生起確率に比例させて、各パーティクルの重みを更新する。（６）各パーティクルの重みと位置とから移動体の位置について正規分布を最尤推定する。（７）正規分布の平均を移動体の位置と推定する。
【非特許文献１】Ｊ．Ｈｉｇｈｔｏｗｅｒ，Ｂ．Ｂｏｒｒｉｅｌｌｏ．“Ｔｈｅ Ｌｏｃａｔｉｏｎ Ｓｔａｃｋ：Ａ Ｌａｙｅｒｄ Ｍｏｄｅｌ ｆｏｒ Ｌｏｃａｔｉｏｎ ｉｎ Ｕｂｉｑｕｉｔｏｕｓ Ｃｏｍｐｕｔｉｎｇ”，４ｔｈ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｏｄｉｌｅ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ ＆ Ａｐｐｌｉｃａｔｉｏｎｓ （ＷＭＣＳＡ ２００２），ｐｐ．２２−２８．２００２．
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記従来技術は、移動体の位置を移動体位置計測装置からの測定値のみで推定しているため、推定精度は移動体位置計測装置に依存してしまう。現在の移動体位置計測装置による位置測定は、数十メートルから数百メートルの誤差を含んでいるため、位置推定にもその誤差が影響してしまい、精度の良い推定を行うことが困難であった。また、パーティクルから一つの正規分布を求め、その平均を移動体の位置と推定するため、出力される推定位置は一つである。移動体位置計測装置の誤差が大きいときは、一つの推定値に集約すると推定確率の分散が大きくなり、推定精度が低くなってしまう。
【０００５】
そこで、本発明は、移動体の位置を高い精度で推定可能な移動体位置推定システム、及び、移動体位置推定方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の移動体位置推定システムは、移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システムにおいて、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させる手段を備えることを特徴とする。また、本発明の移動体位置推定方法は、コンピュータが、移動体位置計測装置から移動体の位置情報を取得すると、パーティクルフィルタにより当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングし、当該サンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定方法において、当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを参照し、当該確率データに従って当該地図データの座標系にパーティクルを分散させるステップを備えることを特徴とする。
【０００７】
ここで、領域とは、建物や道路や河川といった物理的に区別される領域でも良いし、住所といった人為的に定められた領域でも良いし、ユーザが任意に設定した領域でも良い。地図上の各領域に移動体が存在する確率データは、ユーザにより任意に設定可能としてもよいし、予めシステム内に設定されていてもよい。
【０００８】
移動体が存在する確率は、例えば人が携帯する情報端末であれば、道路や建物が高く、河川や山中は低いなど、領域によって異なる。また、移動体の移動パターンや移動範囲によっても異なる場合がある。本発明によれば、地図上の各領域に移動体が存在する確率を示す確率データを参照し、その確率に応じてパーティクルを移動させるため、その確率を反映させた位置の推定が可能となる。
【０００９】
また、前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることが好ましい。
【００１０】
各領域における移動体が存在する確率は、例えば、移動体が人であれば建物や道路が高く河川は低く、また、移動体が船舶であれば河川が高く陸地は低いというように、領域ごとに区別できる。この発明によれば、前記確率データは、各領域をカテゴリ分けし、そのカテゴリごとに確率を設定することが可能となっているため、移動体に応じて各領域の確率を容易に設定することができる。
【００１１】
また、前記地図データには前記各領域を識別する識別情報が含まれており、前記確率データは、当該識別情報を用いて前記各領域がカテゴリ分けされていることが好ましい。
【００１２】
地図は道や建物や川などの領域ごとに色分けされたり、マークが付されたりして、各領域を識別する識別情報が付されていることが多い。この発明によれば、確率データは、これらの識別情報を利用してカテゴリが分けられるため、既存の地図データを用いて簡単にカテゴリ分けを行うことができる。
【００１３】
前記移動体位置推定システム／方法は、 前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力する手段／ステップを備えることが好ましい。
【００１４】
パーティクル全体から移動体の位置を推定した場合、移動体位置計測装置からの位置情報の誤差が大きいときには、推定確率の分散が大きくなり、推定精度が低くなる。この発明によれば、パーティクルをクラスタリングし、各クラスターの平均値を推定位置とするため、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。
【発明の効果】
【００１５】
本発明に係る移動体位置推定ステム／方法によれば、道路や建物や河川といった領域ごとに移動体が存在する確率を示す確率データを有し、移動体の位置推定に際しては、その確率データを反映させるため、移動体の位置をより高い精度で推定可能となる。
【００１６】
確率データの領域を例えば道路や河川などのようにカテゴリに分け、カテゴリごとに確率を設定可能とすれば、推定対象となる移動体に適する確率を容易に設定することができる。確率データを生成する処理は、カテゴリ分けを地図の各領域に付される識別情報を利用して行うことにより、既存の地図情報を用いて簡単にカテゴリ分けを行うことができる。
【００１７】
また、パーティクルをクラスタリングし、各クラスターの平均値を移動体の位置として出力することにより、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置として複数の候補を得ることができる。たとえば、移動体を捜索する場合、従来技術のように推定位置が唯一に出力されると捜索場所も一つに限られてしまう。本システム／方法によれば、複数の場所を候補として捜索できるため発見できる可能性も高まる。
【００１８】
本発明は、様々な分野に応用可能である。たとえば、ＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保したりするのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。
【発明を実施するための最良の形態】
【００１９】
本実施の形態の移動体位置推定システム１は、移動体位置計測装置から得られる位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定するシステムである。
【００２０】
図１は、本発明の第１の実施の形態による移動体位置推定システム１の一構成を示すブロック図である。本実施の形態による移動体位置推定システム１は、内部バス１１に、通信インタフェース１２、ＣＰＵ１３、ＲＯＭ１４、ＲＡＭ１５、ディスプレイ１６、キーボード／マウス１７、ドライブ１８、ハードディスク１９を接続させ、アドレス信号、制御信号、データ等を伝送させ、本実施の形態による移動体位置推定システムを実現するコンピュータシステムとしての構成を備えている。
【００２１】
通信インタフェース１２は、移動体位置計測装置との通信やインターネット等の通信網に接続する各種通信機能を有しており、移動体位置計測装置から移動体の位置情報を受信したり、本発明に係る位置推定をコンピュータに実行させるプログラム１９ａや地図データ１９ｃをダウンロードしたりすることも可能である。ＣＰＵ１３は、ＲＯＭ１４に格納されたＯＳにより装置全体の制御を行うとともにハードディスク１９に格納された各種のアプリケーションプログラム１９ａに基づいて処理を実行する機能を司る。
【００２２】
ＲＯＭ１４は、ＯＳ等のように装置全体の制御を行うためのプログラムを格納しており、これらをＣＰＵ１３に供給する機能を有している。ＲＡＭ１５は、ＣＰＵ１３による各種プログラムの実行時にワークエリアとして利用されるメモリ機能を有している。
【００２３】
ディスプレイ１６は、地図データや確率データや推定位置をグラフィカルに表示したりする機能を有している。キーボード／マウス１７は、文字、数字、記号等のデータを入力したり、画面上のポイント位置を操作することが可能である。
【００２４】
ドライブ１８は、各種のプログラム、データを記録したＣＤ、ＤＶＤ等の記録媒体からインストール作業を実行するための駆動ユニットである。コンピュータを移動体位置推定システム１として機能させるプログラムや地図データを記憶媒体からインストールしたりすることも可能である。
【００２５】
ハードディスク１９は、プログラム１９ａ、メモリ１９ｂ、位置推定に用いられる地図データ１９ｃ等の各種データを記憶する外部記憶装置である。プログラム１９ａは、前述した通信インタフェース１２、ドライブ１８等からインストールされたプログラムを実行形式で記憶したものに相当する。メモリ１９ｂは、各種プログラムの実行結果等のファイルを保存する記憶部である。
【００２６】
地図データ１９ｃは、例えば図２に示すように、基本データＤ１と確率データＤ２とを含む。基本データＤ１は、建物・道路・河川等や、都道府県、市町村、住所などの領域や、位置、経緯度、方角、距離等のデータが含まれている。また、確率データＤ２は、基本データＤ１の各領域に移動体が存在する確率を示す情報が含まれている。確率データＤ２は、建物がカテゴリａ、道路がカテゴリｂ、河川がカテゴリｃ、その他がカテゴリｄというように、領域がカテゴリ分けされており、カテゴリごとに確率が設定されている。この確率はその領域に推定対象となる移動体が存在する確率である。推定対象として人が携帯する情報端末であれば、建物に対応するカテゴリａや道路に対応するカテゴリｂの確率は高く、河川に対応するカテゴリｃの確率は低く設定されている。ただし、確率データＤ２は、カテゴリ分けすることなく、各建物や、各道路ごとというように、領域ごとに確率が設定されていても良いし、住所などの人為的に分けられた領域に設定されていても良い。これにより、移動体固有の行動パターンや行動範囲を確率に反映させることができる。また、確率データＤ２は地図データ１９ｃの一部として一体となっていても良いし、別データとして記憶されていても良い。
【００２７】
確率データＤ２は、後述するステップＳ１の処理前の事前処理で生成され、ハードディスク１９に記憶されている。また、確率データＤ２は予めシステム１内に設定されていても良いし、ユーザが任意に設定や変更を可能としても良い。たとえば、地図データ１９ｃの基本データＤ１をグラフィカルに表示し、各建物や道路等ごとに確率を直接設定可能とし、ユーザが事前設定として確率やカテゴリを設定するようにして確率データＤ２を生成可能としても良い。また、基本データＤ１が建物や道路などの領域を識別する識別情報を含む場合（例えば、建物や道路などが色分けされていたり、マークが付されていたりする場合）、移動体位置推定システム１が、その識別情報を利用して領域をカテゴリ分けし、そのカテゴリを確率データＤ２のカテゴリとしても良い。これにより、人為的なカテゴリ分けが不要となり、既存の地図データを用いて、領域のカテゴリ分けを簡単に行うことができる。
【００２８】
本発明におけるパーティクルとは、地図データ１９ｃの座標系上の位置を示す指標であり、属性には少なくとも地図データ１９ｃの座標系において位置を特定可能な位置情報を含む。本発明におけるパーティクルフィルタとは、移動体位置計測装置から得られる位置情報を取得すると、地図データ１９ｃの座標系に分散する複数のパーティクルから、上記位置情報に応じてパーティクルをサンプリングする機能を少なくとも備えるものであり、本実施の形態においては少なくとも下記のステップＳ１からＳ５を実行する機能を備えるフィルタである。
【００２９】
図３は、移動体位置推定システム１を用いた移動体位置推定方法を説明するフローチャートである。図４は、位置推定処理を概念的に説明する説明図である。移動体位置推定システム１は下記のように機能して、本発明の移動体位置推定方法を実現する。
【００３０】
（ステップＳ１）地図データ１９ｃの座標系のランダムな位置に複数のパーティクルを配置する。パーティクルの配置は、各パーティクルの位置情報をランダムに設定することにより行われる。図４（１）に示すように、パーティクル（図中、白円）はランダムな位置に配置される。
【００３１】
（ステップＳ２）地図データ１９ｃの確率データＤ２を参照し、その確率に依存させてすべてのパーティクルを移動（ランダムウォーク）させる。たとえば、図５に示すように、確率データＤ２は、基本データＤ１の緯度経度座標系をピクセル単位に変換し、基本データＤ１でカテゴリａ，ｂ，ｃ，ｄに分けられた各領域にピクセル単位で確率を設定したものとする。そして、パーティクルの移動可能範囲ｅをパーティクルの位置を中心とした一定半径サークル内と設定しておき、パーティクルをランダムウォークさせるときには、移動可能範囲内ｅのすべてのピクセルの確率データを取得し、その確率に比例して次の位置を決定し、その位置にパーティクルを移動させる。パーティクルを移動させるタイミングは予め移動体位置推定システム１に設定されており、そのタイミングになると確率データＤ２に従ってパーティクルをランダムウォークさせる。図４（２）は、確率データに従ってパーティクルをランダムウォークさせたときの状態を概念的に示す説明図である。確率の高い領域に多くのパーティクルが配置される。
【００３２】
（ステップＳ３）移動体位置計測装置から移動体の位置情報を取得しない間は、ステップＳ２に戻り上記ランダムウォークを続ける。移動体位置計測装置から移動体の位置情報を取得した場合は、ステップＳ４に進む。
【００３３】
（ステップＳ４）移動体位置推定システム１は、位置情報を取得すると、その位置情報を確率分布Ｐ１（ｘ）で表されるデータに変換する。位置情報から確率分布Ｐ１（ｘ）への変換は、予め設定されている数式等の規則に従い変換する。移動体位置計測装置からの位置情報の形式は、その機器の特性に応じて異なるので、機器に応じた確率分布に変換する。このため、移動体位置推定システム１には移動体位置計測装置ごとに予め数式等による変換規則が設定されており、位置情報から確率分布Ｐ１（ｘ）への変換はその規則に従い行う。例えば、ＧＰＳの場合は緯度経度情報を出力するので、取得した緯度経度情報を平均とした正規分布に変換する。また、ＰＨＳは各地に所在する基地局のどの基地局で端末からのデータを受信したかで位置が特定される。このため、移動体からの電波を受信した基地局が電波を受信できる範囲内は、移動体が存在する確率が一様であり、その他の範囲は確率が０である。そこで、ＰＨＳから位置情報を取得した場合は、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値（０より大）とし、その他の範囲は確率を０とする一様分布に変換する。
【００３４】
（ステップＳ５）確率分布Ｐ（１）に従って、地図上の母集団からパーティクルをサンプリングする。サンプリングの方法は、まず、その確率分布Ｐ１（ｘ）に従った確率で１つのパーティクルを地図上の母集団から抽出し、それを母集団に戻してから再び同様に次のパーティクルを抽出する。それを繰り返すことにより、母集団と同じ数のパーティクルを確率分布Ｐ１（ｘ）に従って抽出する。図６は、ＧＰＳの位置情報を用いたときの確率分布Ｐ１（ｘ）のデータと、地図データ１９ｃの座標系上の母集団と、抽出されたパーティクルとを説明する説明図である。取得した位置情報を平均とした正規分布データＰ１（ｘ）に従って、母集団からパーティクルが抽出される。パーティクルは、正規分布の頂点（平均）に最も近いところが多く抽出され、遠いところほど抽出されない。図４（３）は、この正規分布によりサンプリングされたパーティクルの分散を概念的に説明する説明図である。パーティクルは、取得した位置情報に最も近いところが多く抽出され、遠いところほど抽出されない。
【００３５】
（ステップＳ６）サンプリングされたパーティクルをクラスタリングする。図４（４）はパーティクルのクラスタリングを概念的に説明する説明図である。サンプリングされたパーティクルは複数のクラスターにクラスタリングされる。ここで、本実施の形態のクラスタリングについて説明する。本実施の形態のクラスタリングには、正規混合分布Ｐ（ｘ）を用いたクラスタリング手法を用いる。正規混合分布とは数１に示される確率分布である。数１のｐｉ（ｘ）は正規分布を表す。この数１における正規分布の数ｃと各正規分布の重みαi、および各正規分布ｐｉ（ｘ）の平均値と分散を求めることがクラスタリング処理にあたる。本実施の形態では、これらの値を総じて、正規混合分布Ｐ（ｘ）のパラメータと呼ぶこととする。クラスタリングによって生成されるクラスターは、正規混合分布Ｐ（ｘ）を構成する個々の正規分布に対応する。正規混合分布Ｐ（ｘ）のパラメータが求まると、数１によって各パーティクルがどのクラスターに所属するかを確率的に得ることが可能となる。さらに、地図上の任意の位置を入力として与えると、その位置に移動体が居る確率を求めることができるようになる。
【数１】
【００３６】
図７に、正規混合分布Ｐ（ｘ）によるクラスタリング例を示す。水平線の上に並んでいる長方形が個々のパーティクルを表している。Ｐ（ｘ）は正規混合分布を表す。個々のパーティクルから求められた正規混合分布Ｐ（ｘ）は、パーティクルが集まっているところほど、確率が高く（山が高く）なっている。この例では２つのクラスターが生成されている。
【００３７】
すなわちステップＳ６において移動体位置推定システム１は、以下のように動作する。数１は移動体位置推定システム１に予め設定されており、移動体位置推定システム１は、ステップＳ５にてサンプリングしたパーティクルの情報を用いて、数１の各パラメータ数cと各正規分布の重みαi、及び、正規分布ｐｉ（ｘ）の平均値と分散を算出する。詳しくは、各正規分布の重みαi、および正規分布ｐｉ（ｘ）の平均値と分散については、個々のパーティクルが所属するクラスターを隠れ変数としたＥＭアルゴリズムに基づいて算出する。ＥＭアルゴリズムとは、隠れ変数がある場合の最尤推定方法として広く知られている手法であり、繰り返し計算を行うことで、解が収束することが証明されている。一方、正規混合分布Ｐ（ｘ）の数ｃについては、初期値を１として数２に示される正規混合分布Ｐ（ｘ）における各パーティクルの対数尤度の値が減少するまで１つずつ加算して求める。図４（５）は各クラスターの平均値を概念的に説明する説明図である。算出された各正規分布ｐｉ（ｘ）の平均値が移動体の推定位置の座標（ｘ、ｙ）となる。
【数２】
【００３８】
さらに、移動体位置推定システム１は、各推定位置（ｘ、ｙ）における移動体が存在する確率Ｐ（ｘ）を算出してもよい。この場合、上記算出された各パラメータを数１に代入し、上記算出された各推定位置の座標（ｘ、ｙ）を数１の入力情報（ｘ）とし、Ｐ（ｘ）を計算する。
【００３９】
なお、クラスタリング方法は、上記に限られるものではなく、あらかじめ固定された数のクラスターに分類する非階層的クラスタリングでも良いし、互いの距離の近いものから順にクラスターを融合していくことにより、適当な数のグループに分割するＣ−Ｍｅａｎｓ法などの階層的クラスタリングでも良いし、クラスタリング方法は限定されない。
【００４０】
（ステップＳ７）ステップＳ６にて算出された複数の推定位置（ｘ，ｙ）を出力する。ステップ６にて、各推定位置（ｘ，ｙ）に対する移動体が存在する確率Ｐ（ｘ）を算出した場合は、各推定位置（ｘ，ｙ）に確率Ｐ（ｘ）を表示したり、推定位置（ｘ，ｙ）を確率Ｐ（ｘ）の高い順に順位付けして出力してもよい。出力先はディスプレイ１６でも良いし、通信インタフェイス１２からネットワークを介して接続可能な情報端末（例えば携帯電話等）に出力しても良い。また、算出された複数の推定位置のすべてを出力してもよいし、確率順に上位数個を出力するようにしてもよい。
【００４１】
移動体位置推定システム１による上記移動体位置推定方法によれば、道路や建物や河川といった領域ごとに移動体が存在する確率データＤ２を反映させるため、移動体の位置をより高い精度で推定可能となる。また、パーティクルをクラスタリングして位置推定を行うため、各クラスター内における推定確率の分散を抑えることができ、推定精度を高めることができる。また、推定位置が唯一に出力される従来技術と比較して、本発明は推定位置として複数の候補を得ることができる。たとえば、ユーザが移動体を捜索している場合は、複数の候補地を捜索することが可能となる。
【００４２】
（第２の実施の形態）
また、例えば移動体位置推定システム１が徘徊老人の探索など、移動体の探索に使用される場合は、出力される複数の推定位置を探索者が巡回する必要がある。そこで、移動体位置推定システム１は、複数の推定位置の巡回経路を出力するようにしても良い。巡回経路の出力は次のように行う。図８は本実施の形態の処理を説明するフローチャートである。この巡回経路の処理（ステップＳ６−１）は、上記第１の実施の形態の処理のステップＳ６の終了後に行われ、巡回経路を算出し、推定位置とともに巡回経路の出力を行うことにより実現される。第１の実施の形態と同様の部分については説明を省略する。
【００４３】
移動体位置推定装置１には、巡回経路の算出のステップＳ６−１よりも前までに巡回のスタート地点が入力される。スタート地点は、巡回者が任意に入力可能としてもよいし、巡回者が携帯する情報端末のＧＰＳ等の機能を用いて移動体位置計測装置から得られる位置情報を入力としても良い。移動体位置測定システム１は、スタート地点の位置情報と、上記算出した複数の推定位置やその推定位置に移動体が存在する確率から、巡回者が移動体に到達する可能性が高く、且つ、短時間に巡回できる経路を算出する。
【００４４】
たとえば、移動体位置推定システム１は、次のように巡回経路を算出する。スタート地点から推定位置（すなわち、推定位置を表す正規混合分布Ｐ（ｘ）を構成する各正規分布ｐｉ（ｘ）の頂点）をすべて巡回する経路を探索する。正規混合分布Ｐ（ｘ）を構成する正規分布ｐｉ（ｘ）の数をＣとすると、経路はその階乗Ｃ！だけ存在する。これらの経路を評価する関数として、下記数３を用いる。
【数３】
Ｒｏｕｔｅは評価値Ｖを求めようとする経路における推定位置ｒ（スタート地点を除く各地点）の集合であり、ｒはその推定位置の１つを示す。Ｔ（ｒ）は、推定位置ｒに到達するまでの１つ前の地点（スタート地点又は推定位置）からの時間を求める関数である。Ｐ（ｒ）は、推定位置ｒの１つ前の地点までの全ての推定位置における移動体が存在する確率の総和である。評価値Ｖの値が小さいほど、効率的な巡回経路であるといえる。
【００４５】
図９は、数３の一実施例をグラフで表した図である。図９の横軸は時間、縦軸はその移動体が存在しない確率（数３における１−Ｐ（ｘ））、すなわち、探索者が被探索者を発見できない確率を示している。ここでは、正規混合分布を構成する正規分布の数（すなわち推定位置の数）Ｃ＝３を例に説明する。すべての経路について次の処理を行う。スタート地点ｓから一つ目の正規分布の頂点（推定位置）ｐ１に達するときに必要な時間と、その到達した頂点（推定位置）ｐ１において移動体を発見できない確率を算出する。さらに、一つ目の頂点（推定位置）ｐ１から次の頂点（推定位置）ｐ２に達するときに必要な時間と、その到達した頂点ｐ２における移動体を発見できない確率を算出する。このように、スタート地点から巡回する経由地点順に、時間と移動体を発見できない確率を算出する。そして、横軸を時間、縦軸を移動体を発見できない確率として、算出された各頂点（推定位置）の時間と移動体を発見できない確率をプロットし、その積分値（図９の斜線部分の面積）の大きさが評価値Ｖとなる。これにより、移動体を発見できる確率と巡回時間とを考慮した評価が可能となる。巡回経路の出力に際しては、評価値Ｖが低い経路のみを提示してもよいし、評価値順に順位付けしてすべての巡回経路を出力しても良い。
【００４６】
一例として、図１０（ａ）のように、移動体位置推定の結果、ａ，ｂ，ｃの三つの推定位置が得られた場合の巡回経路の算出を説明する。スタート地点は座標（０，０）であり、推定位置ａは座標（５，０）、ｂは座標（４，３）、ｃは座標（０，５）の位置であり、各推定位置における移動体が存在する確率がａは０．５，ｂは０．１，ｃは０．４であったとする。すべての巡回経路について上記評価値Ｖを算出した結果を図１０（ｂ）に示す。ａ−ｂ−ｃの順で巡回する経路が最も良い評価値であるという結果が得られ、有効な巡回経路としてａ−ｂ−ｃを出力される。
【００４７】
これにより、探索者は、出力された複数の推定位置を効率的に巡回できる経路の情報を得ることができる。たとえば、徘徊老人の探索においては、効率的に巡回することにより、より迅速に徘徊老人を見つけ出し、安全を確保することができる。
【００４８】
なお、本発明は、上記実施の形態に限られるものではなく、本発明から逸脱しない範囲内で変更が可能である。たとえば、確率データを用いて領域ごとに移動体が存在する確率を反映させる技術（ステップＳ２）は、位置推定にクラスタリングを用いることなく、従来のようにパラメータの最尤推定を行う技術に適用しても良い。これによっても、領域ごとの確率が反映され、従来よりも高精度に位置推定が行われる。この場合、移動体位置推定システム１は以下のように処理を行う。図１１は、そのフローチャートである。移動体位置推定システムは、上記ステップ１からステップ５を行った後、サンプリング結果からパラメータ最尤推定を行って確立分布を算出し、得られた確率分布から推定位置を算出し（ステップＳ６）、推定位置を出力する（ステップＳ７）。パラメータ最尤推定や、確率分布からの推定位置の算出は、位置計測装置の種類に応じて行えばよい。例えばＧＰＳであればパラメータ最尤推定を行って正規分布を算出し、その正規分布の平均値を推定位置として出力する。また、ＰＨＳの場合は、ステップ４において、受信した基地局が電波を受信できる範囲内において移動体が存在する確率を０より大の一定値（０より大）とし、その他の範囲は確率を０とする一様分布データに変換される。ステップ４以外は、ＰＨＳであってもＧＰＳであっても同じ処理である。
【００４９】
また、本発明は、様々な分野に応用可能である。たとえば、ＧＰＳ機能付き情報携帯端末等の移動体を人に携帯させ、徘徊する高齢者や遭難者を捜索したり、登下校中の児童の位置を把握して安全を確保するのに用いることができる。また、移動体を自動車等に搭載すれば、タクシーや配送車等の位置管理などにも応用可能である。
【図面の簡単な説明】
【００５０】
【図１】本発明の第１の実施の形態による移動体位置推定システムの一構成を示すブロック図である。
【図２】地図情報と確率データを概念的に説明する説明図である。
【図３】上記実施の形態における移動体位置推定システムを用いた移動体位置推定方法を説明するフローチャートである。
【図４】上記実施の形態の位置推定処理を概念的に説明する説明図である。
【図５】上記実施の形態において地図情報に対する確率データの設定を説明する説明図である。
【図６】ＧＰＳの位置情報を用いたときの確率分布データと、地図情報上のパーティクルの母集団と、抽出されたパーティクルとを説明する説明図である。
【図７】パーティクルフィルタにより抽出されたパーティクルの確率分布を正規混合分布によって表す例を示す説明図である。
【図８】第２の実施の形態の処理を説明するフローチャートである。
【図９】上記実施の形態の巡回経路の算出に用いる関数を説明する説明図である。
【図１０】上記実施の形態の巡回経路の算出の例を示す説明図である。
【図１１】他の実施の形態の処理を説明するフローチャートである。
【符号の説明】
【００５１】
１ 移動体位置推定システム
１９ｃ 地図データ
Ｄ１ 基本データ
Ｄ２ 確率データ
【特許請求の範囲】
【請求項１】
移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システムにおいて、
当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させる手段を備えることを特徴とする移動体位置推定システム。
【請求項２】
前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることを特徴とする請求項１記載の移動体位置推定システム。
【請求項３】
前記確率データは、前記地図データに含まれる各領域を識別する識別情報を用いて、前記各領域がカテゴリ分けされていることを特徴とする請求項２記載の移動体位置推定システム。
【請求項４】
前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力する手段を備えることを特徴とする請求項１乃至請求項３のいずれか１項に記載の移動体位置システム。
【請求項５】
コンピュータが、移動体位置計測装置から移動体の位置情報を取得すると、パーティクルフィルタにより当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングし、当該サンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定方法において、
当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを参照し、当該確率データに従って当該地図データの座標系にパーティクルを分散させるステップを備えることを特徴とする移動体位置推定方法。
【請求項６】
前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることを特徴とする請求項５記載の移動体位置推定方法。
【請求項７】
前記地図データには前記各領域を識別する識別情報が含まれており、前記確率データは、当該識別情報を用いて前記各領域がカテゴリ分けされていることを特徴とする請求項６記載の移動体位置推定方法。
【請求項８】
前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力するステップを備えることを特徴とする請求項５乃至請求項７のいずれか１項に記載の移動体位置方法。
【請求項１】
移動体位置計測装置から移動体の位置情報を取得すると、当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングするパーティクルフィルタを備え、当該パーティクルフィルタによりサンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定システムにおいて、
当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを有し、当該確率データに従って当該地図データの座標系にパーティクルを分散させる手段を備えることを特徴とする移動体位置推定システム。
【請求項２】
前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることを特徴とする請求項１記載の移動体位置推定システム。
【請求項３】
前記確率データは、前記地図データに含まれる各領域を識別する識別情報を用いて、前記各領域がカテゴリ分けされていることを特徴とする請求項２記載の移動体位置推定システム。
【請求項４】
前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力する手段を備えることを特徴とする請求項１乃至請求項３のいずれか１項に記載の移動体位置システム。
【請求項５】
コンピュータが、移動体位置計測装置から移動体の位置情報を取得すると、パーティクルフィルタにより当該位置情報を用いて地図データの座標系に分散するパーティクルをサンプリングし、当該サンプリングしたパーティクルから当該移動体の位置を推定する移動体位置推定方法において、
当該地図データの座標系上の各領域に当該移動体が存在する確率を示す確率データを参照し、当該確率データに従って当該地図データの座標系にパーティクルを分散させるステップを備えることを特徴とする移動体位置推定方法。
【請求項６】
前記確率データは、前記各領域がカテゴリ分けされており、当該カテゴリごとに前記確率を設定可能であることを特徴とする請求項５記載の移動体位置推定方法。
【請求項７】
前記地図データには前記各領域を識別する識別情報が含まれており、前記確率データは、当該識別情報を用いて前記各領域がカテゴリ分けされていることを特徴とする請求項６記載の移動体位置推定方法。
【請求項８】
前記サンプリングされたパーティクルをクラスタリングし、各クラスターの平均値を前記移動体の推定位置として出力するステップを備えることを特徴とする請求項５乃至請求項７のいずれか１項に記載の移動体位置方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００８−１４７４２（Ｐ２００８−１４７４２Ａ）
【公開日】平成２０年１月２４日（２００８．１．２４）
【国際特許分類】
【出願番号】特願２００６−１８５１９８（Ｐ２００６−１８５１９８）
【出願日】平成１８年７月５日（２００６．７．５）
【特許番号】特許第４０３２１２５号（Ｐ４０３２１２５）
【特許公報発行日】平成２０年１月１６日（２００８．１．１６）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１７年度、知的創造による地域産学官連携強化プログラム「文部科学省 知的クラスター創成事業」委託研究、産業活力再生特別措置法第３０条の適用を受ける特許出願
【出願人】（３０４０２４４３０）国立大学法人北陸先端科学技術大学院大学 (169)
【Ｆターム（参考）】
【公開日】平成２０年１月２４日（２００８．１．２４）
【国際特許分類】
【出願日】平成１８年７月５日（２００６．７．５）
【特許番号】特許第４０３２１２５号（Ｐ４０３２１２５）
【特許公報発行日】平成２０年１月１６日（２００８．１．１６）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成１７年度、知的創造による地域産学官連携強化プログラム「文部科学省 知的クラスター創成事業」委託研究、産業活力再生特別措置法第３０条の適用を受ける特許出願
【出願人】（３０４０２４４３０）国立大学法人北陸先端科学技術大学院大学 (169)
【Ｆターム（参考）】
[ Back to top ]