位置決め技法
【課題】高周波ネットワーク内の目標装置の位置を、ある位置における信号値の予測分布を示すいくつかのサンプル点に関する確率モデルを維持することによって評価する。
【解決手段】目標装置が信号値(OS)を観測し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成する。グラフ(G)が位置決め環境のトポロジーをモデル化する。このグラフは、環境内の許容される位置である複数の節点と、二つの節点間の許容される位置推移である複数の弧を示す。このグラフ(G)は、確率モデル(PM)と観測値の系列(OS)とにもとづいて目標装置の位置を評価するのに使用される。
【解決手段】目標装置が信号値(OS)を観測し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成する。グラフ(G)が位置決め環境のトポロジーをモデル化する。このグラフは、環境内の許容される位置である複数の節点と、二つの節点間の許容される位置推移である複数の弧を示す。このグラフ(G)は、確率モデル(PM)と観測値の系列(OS)とにもとづいて目標装置の位置を評価するのに使用される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的に言えば、目標装置の無線通信環境に関する観測値の系列にもとづいて目標装置の位置を評価する位置決め技法に関する。
【背景技術】
【０００２】
図１はそのような位置決め技法の一例を模式的に示す。目標装置Tは高周波インタフェース(radio interface)RIにより基地局BSと通信する。この例では、通信は高周波通信であると仮定している。目標装置Tは高周波インタフェースRIにおける信号値を観測する。観測値Oを、目標装置の無線通信環境をモデル化する確率モデルPMに使用し、位置評価値LEを生成する。ここで使用する目標装置という言葉は、その位置を決定すべき装置を意味する。目標装置は無線環境で信号により通信するので、目標装置の位置を決定するために、無線環境における信号値が使用される。たとえば、目標装置は無線ローカルエリアネットワーク(WLAN)で通信するデータ処理装置とすることができる。データ処理装置は汎用のラップトップもしくはパームトップコンピュータまたは通信装置とすることができ、あるいは専用の試験または測定装置たとえばWLANに接続された病院の装置とすることができる。ここで使用する位置という言葉は、1〜3個の座標から成る座標の組を意味する。いくつかの特殊なケースたとえばトンネルの場合、単一の座標で十分でありうるが、大部分の場合、この位置は座標対(x、y、または角度/半径)で表される。
【０００３】
もっと詳しく言えば、本発明は間接(hidden)マルコフモデルにもとづく位置決め技法に関する。図２は間接マルコフモデルHMMを模式的に示す。このモデルは、位置、位置間の推移(transition)、およびこれらの位置で得られる観測値から成る。図２に示す例の場合、目標装置は一つの経路に沿って移動し、該経路に沿って、五つの位置qt-2〜qt+2が示してある。もっと詳しく言えば、qtは時刻tにおける位置分布を定義し、したがってP(qt=s)は目標装置が時刻tに位置sにいる確率である。しかし、位置分布は簡単に一つの位置評価値に変換することができるので、位置分布qを表すのに短縮表記“位置q”を使用する。
【０００４】
目標装置の経路に沿う位置は、経路点と呼ぶことができる。目標装置は無線環境内で信号により通信するので、無線環境内の信号値が目標装置の位置の決定に使用される。
【０００５】
目標装置の実際の例としては、無線ローカルエリアネットワーク(WLAN)またはセルラー高周波ネットワーク内で通信するデータ処理装置がある。このデータ処理装置は汎用のラップトップもしくはパームトップコンピュータまたは通信装置とすることができ、あるいは専用の試験または測定装置たとえばWLANに接続された病院の装置とすることができる。ここで使用する信号値という言葉は、送信機特定信号(fixed transmitter's signal)の測定可能な位置依存量である。たとえば、信号強度およびビット誤り率(bit error rate/ratio)が測定可能な位置依存量の例である。
【０００６】
間接マルコフモデルの‘間接’という言葉は、位置qt-2〜qt+2に主要な関心があるが、これらの位置は直接には観測できないという事実に由来している。信号値にもとづいて、これらの位置の代わりに、一連の観測値ot-2〜ot+2を得ることができるが、観測値ot-2〜ot+2と位置qt-2〜qt+2との間には、簡単な関係がない。(位置qt-2〜qt+2の直線矢印は、目標装置が直線経路に沿って移動すること、あるいは一定の速度で移動すること、または観測が等間隔で行われることを意味するものではない、ということに注意されたい。)
【０００７】
単一の‘観測値’は、一つ以上のチャンネルからのいくつかの信号値測定値を含みうること、また一般に含むということに注意すべきである。確率モデルにおいては、信号値の確率分布を測定するということが考えられるが、いろいろな位置における信号値に重複がある場合、これらの位置は位置あたり一つの測定値によっては決定できない。したがって、確率分布を決定するためには、各観測値は複数の測定値を含むものでなければならない。
【０００８】
図１および２においては、時間が分割されている(quantified)ということにも注意すべきである。すなわち、単一の高周波受信機を有する目標装置は任意の時点において一つのチャンネルしか観測できないが、該高周波受信機は数ミリ秒で別のチャンネルに切り換えることができ、したがって観測値ot-2〜ot+2は一般に少なくとも百ミリ秒だけ離れている。観測値間の間隔は一般的な目標装置の速度に合わせて選択することができる。したがって、高周波受信機をチャンネル間で切り換えなければならない場合でも、単一の観測値がいくつかのチャンネルからの信号値を含むことができる。
【０００９】
高周波受信機は、信号値たとえば信号強度を事実上連続的に測定できるが、間接マルコフモデルにもとづく位置決めに適用する場合、分割された時間における観測値を使用するのが有利である。したがって、‘観測値’というのは、所定の時間間隔からのいくつかの信号値の統計サンプルであると要約することができる。
【００１０】
本発明のもとになった問題は、間接マルコフモデルから出てきたものである。すなわち、距離または位置に対して一意の(monotonous)の関係を有する変数を観測することができないという問題である。この位置決め法は、そのような変数の代わりに信号値の観測結果を使用するものである。しかし、二つ以上の位置が大体同じ信号値の組を有することが可能であり、したがって位置評価値がひどく不正確になりうる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、前記欠点を小さくするような方法と該方法を実施するための装置とを提供することである。言い換えると、本発明の目的は、予測される信号値の確率モデルにもとづく位置決め技法の不確実性を低下させることである。本発明のこの目的は、独立クレームに述べることを特徴とする方法と装置によって達成される。本発明の好ましい実施形態は、従属クレームに開示されている。
【課題を解決するための手段】
【００１２】
本発明は、位置決め環境のトポロジーをモデル化するグラフ(またはグラフの組)の使用にもとづく。一つのグラフG[V,A]は、n個の節点または頂点V=[ν1,ν2,...νn]とm個の弧A=[a1,a2,...am]を有し、ここで各弧ak=(νi,νj)は、νiからνjへの可能な経路または位置推移を示す。したがって、位置決め環境内のすべての可能な経路はグラフGの弧のいろいろな組合せによって記述することができる。たとえば、一般的オフィスのグラフGは各廊下としての弧、廊下を部屋に結びつける(ドアを通じて)弧、その他を有する。複数階から成る環境が、いくつかの相互連結されたグラフ、または弧の一部が垂直位置推移(エレベータ、階段、またはエスカレータ)を示す一つのグラフによって記述されるかどうかは重要あるいは有意(semantics)なことである。コンピュータ支援設計においては、弧は湾曲セグメントを意味するが、グラフ理論においては、本発明におけると同様に、弧は単に二つの節点間の連結を意味する。実際、弧は直線として引かれる。
【００１３】
注意すべきことは、本発明によるグラフは一般に位置決め環境の一つの性質であり、位置決め環境内の障害物にもとづいて決定される、ということである。これは、いくつかの先行技術の位置決め法におけるものとは異なる。後者においては、各目標装置の許容位置は、目標装置自身の位置履歴と実現しうる速度とにもとづいて、独立に決定される。
【００１４】
本発明の利点は、目標装置の報告位置が自然な動きをするということ、すなわち、目標装置が壁その他の障害物を通過して動くように見えるようなことがない、ということである。もう一つの利点は、グラフが、計測値または計算値にもとづいて確率モデルを確立するための十分な基礎として役立つ、ということである。グラフ節点が確率モデルのサンプル点としても使用される場合、この位置決め法は目標装置が移動する可能性の高い領域でもっとも正確である。
【００１５】
目標装置の位置がグラフの点または節点として解釈される場合には、目標装置の動きはコンピュータ解析するのが容易である。言い換えると、十分明確なグラフ上の点または節点として解釈される報告位置は、分割のなされていない任意の位置に比して、データ採取(mining)作業のためのずっとすぐれたデータ源となる。たとえば、デパート店舗設計者は客の動きのパターンまたは相関を調べたいと思うことがあるであろう。グラフ節点がいくつかのデスクに置かれている場合、デスクxで止まった客がデスクyをも通るかどうかを見るのはかなり容易である。グラフと独自の分割とがない場合、設計者は各デスクに近いある領域内で座標を設定しなければならないであろう。各グラフ節点は許容される位置であるが、許容される位置は必ずしもグラフ節点ではない。節点間の距離は必要分解能に応じて選択すべきである。言い換えると、グラフを引く人は、報告位置が真の位置からどれだけ隔たっていても良いか、という質問に答えなければならない。答えは、代表的な目標装置の性質による。目標装置が人が携行する通信装置である場合には、数mの誤差は許容されるであろう。人は数mの距離からは容易に見分けられるからである。一方、目標装置が病院の機器その他である場合には、もっと高い分解能が望ましい。大部分の用途においては、分解能(節点間の距離)は大体1 mである。もっと小さな距離を用いる高い分解能は、資源のより多くの使用によって可能である。使用される資源は、たとえば、計測用のもの、確率モデルを記憶するメモリ、および計算能力である。開かれた空間は、水平および垂直の弧から成る格子として扱うことができる。開かれた空間では、可視性が良好であるから、通常の分解能よりも低い分解能が許容できる。
【００１６】
グラフGは以下のように間接マルコフモデルと結びつけることができる。弧に沿う点間の代表距離をdとする。この代表距離は必要な分解能たとえば1 mである。S=[s1,s2,…sk]を、弧に沿う点の集合とし、点間距離がdであるとする。Sは、間接マルコフモデルの間接状態変数qiの定義域として使用することができる。
【００１７】
グラフGは、好ましくは、グラフ節点間の推移確率の集合と一緒に使用する。推移確率P(qt|qt-1)は、目標装置が二つの観測間に適合する時間間隔内でその位置推移を行うことができる場合にのみ、siからsjへの推移の確率すなわちP(qt=sj|qt-1=si)が非ゼロとなるように、定義することができる。
【００１８】
推移確率を使用するための二つの方法について述べる。第一の方法は、代表的な目標装置の速度、観測間の時間間隔、および点間の距離のみによるものである。dmaxを、観測間の最大時間間隔内に代表的な目標装置が移動する最大距離であるとする。dmaxを越える長さの位置推移は確率ゼロであるかまたはゼロに非常に近い。たとえば、通常の屋内環境において、人が2 m/sよりも速く移動することはめったにない。したがって、二つの観測間の時間が1 sである場合、2 mを越える距離の位置推移の確率はゼロであり、あるいは少なくとも非常に小さい。(この非ゼロ確率は、たとえば、人はめったに走らないが、走るのが厳禁されてはいない、ということを意味する。)
【００１９】
推移確率に関する第二の方法は、隣接点すなわち密接に結びつけられた点の概念によるものである。二つの点siとsjは、Sの他の点を経由することなくAの弧によって互いに到達することができる場合には、隣接点である。この隣接点による方法は、Gの弧の集合が許容される推移の集合でもあるという点ですっきりしたものであり、計算が簡単になる。小さな欠点は、高速移動する目標装置の位置がある遅れをもって報告されるということである。目標装置がその先行評価位置から3節点だけ離れた節点に高速で直線的に移動するとする。隣接点への位置推移のみが許容されているので、位置評価はすべての介在節点を経由して進行しなければならない。そのため、三つの観測時間だけの遅れが生じる。
【００２０】
本発明のもう一つの好ましい実施形態においては、推移確率には、節点間距離と代表的な目標装置速度とにもとづいて、まず予備値が割り当てられる。位置決めシステムが使用されるとき、目標装置の動きの履歴がまとめられ、それから推移確率が実験的に微調整される。
【００２１】
推移確率の使用に関しては、あとで“再帰にもとづく方法”の項でさらに詳しく述べる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を、好ましい実施形態により、添付の図面を参照しつつ、より詳細に説明する。
【００２３】
図３は、本発明によるグラフGを示す。この例の場合、グラフGは二つの部分グラフG1とG2とから成り、部分グラフG1は一階の平面図31に対応し、部分グラフG2は二階の平面図32に対応する。このグラフは、黒丸で示された節点を有し、各節点が目標装置の許容位置を示すようになっている。節点間の距離は必要分解能にもとづいて選択すべきである。大部分の用途においては、分解能(節点間距離)は大体1 mである。もっと小さな距離を用いる高い分解能は、資源のより多くの使用によって可能である。使用される資源は、たとえば、計測用のもの、確率モデルを記憶するメモリ、および計算能力である。大部分のオフィス室に対しては、たとえば左上部の室の節点311のような、単一の節点で十分である。一方、大きな室は、左下部の室の節点312と313のように、もっと多くの節点を有しうる。節点314~319は、開かれた空間に配置された節点である。そのような節点は、多すぎる計算資源を使用することなく、必要な分解能が実現できるように配置すべきである。この平面図は、破線で示された許容されない領域33を有している。たとえば、この許容されない領域は、受付係のデスク、オフィス装置、建築構造物、あるいは目標装置が入れないその他の障害物でありうる。あるいは、もっと正確に表現すると、目標装置は領域33内にはいれるかもしれないが、その位置は領域33の外部にあると解釈される、ということである。
【００２４】
グラフGは、許容される位置を示す節点310、311、その他に加えて、節点間の許容される位置推移を示す弧を含む。図3においては、グラフを簡単にするために、弧は、水平または垂直で、他の節点を通過することなく二つの節点だけを連結する場合にのみ、示されている。たとえば、弧331は節点314と315とを連結し、弧332は節点315と316とを連結するが、節点314と節点316を結ぶ弧はない。
【００２５】
図３に示すオフィス空間は、三次元であるが、連結されたいくつかの二次元空間として扱われている。節点310および320は、それぞれ一階および二階への入口点である。弧333は二つの階への入口点310と320を連結する。
【００２６】
図４は、高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMの一例のブロック図である。図４は、コンパクトな位置評価モジュールLEMを示すが、より複雑な実施形態も可能である。この位置評価モジュールの本質的特徴は目標装置無線環境の確率モデルPMであり、この確率モデルは、高周波インタフェースからの複数の観測値が与えられると、目標装置位置を予想することができる。この例の場合、確率モデルPMがモデル構築モジュールMCMによって構築されて、維持される。モデル構築モジュールMCMは、計測データCDもしくは一つ以上の伝搬(propagation)モデルの形の伝搬データPD、またはこれらの任意の組合せにもとづいて確率モデルを構築し、維持する。計測データCDは、既知の位置(または、これらの位置を他の手段では知り得ない場合、これらの位置の座標を物理的に決定する)での信号値の物理的測定の結果である。随意であるが、計測データレコードは、信号パラメータが時間とともに変化する場合には、測定がなされた時刻をも含むことができる。高周波インタフェースRIをモデル化するのに、計測データＣＤの代わりに、またはこれに加えて、一つ以上の伝搬モデルPDを使用することができる。伝搬モデルは、可視シミュレーションのための光線追跡(ray-tracing)法に似た方法によって構築することができる。計測値が集められる位置を計測点と呼ぶ。計測データCDはデータレコードからなり、各レコードは、当該計測点の位置と該計測点で測定された信号パラメータの集合とを含む。この位置は任意の絶対または相対座標系で表すことができる。特殊な場合、たとえば列車、公道、トンネル、水路、その他では、単一の座標で十分でありうるが、通常は、二つまたは三つの座標が使用される。
【００２７】
目標装置観測値集合OSと確率モデルPMとにもとづいて位置評価値LEを生成するための位置計算モジュールLCMも備えられている。たとえば、この位置計算モジュールは、ラップトップまたはパームトップコンピュータで実行されるソフトウェアプログラムとして具体化することができる。技術的には、‘測定’と‘観測’は同様に実施することができるが、混乱を避けるために、‘測定値’という言葉は一般に計測値に関して使用し、目標装置のそのときの位置で得られた信号パラメータを‘観測値’と呼ぶ。目標装置のもっとも新しい観測値の集合を最新観測値と呼ぶ。
【００２８】
グラフGは、位置決めシステムにおいて、いくつかの主要用途を有する。たとえば、グラフは確率モデルの構築時に使用することができる。確率モデルのサンプル点は、好ましくはグラフの節点に配置される。たとえば、モデル構築モジュールMCMは、好ましくは、各グラフ節点に対してサンプル点が実際に決定された(計測、シミュレーション、または補間された)ということを自動チェックする機能を有する。
【００２９】
グラフは、また、可能な位置の間での推移確率を決定するための十分な根拠ともなる。
【００３０】
最後に、グラフは目標装置の位置を評価または解釈するのに使用することができる。たとえば、目標装置の位置は、評価位置にもっとも近い弧上の一点であると解釈できる。この場合、位置はグラフの一つの弧の上にあると強制的に解釈される。さらに、この位置を、評価位置にもっとも近いグラフ節点であると解釈することができる。いくつかの中間評価値を組み合わせることによって、最終的な位置解釈を行うことができる。
【００３１】
グラフの一部またはすべてが、好ましくは、確率モデルのサンプル点がグラフの節点に配置され、かつ目標装置の位置がグラフにもとづいて評価または解釈されるように使用される。許容される位置はグラフ節点またはその近くにあるので、位置決めはグラフ節点近くでもっとも正確である。逆に、位置決めは許容されない位置たとえば領域33では相対的に不正確でありうるが、この領域にまったくはいれない場合、または少なくともこの領域の内部が目標装置の位置であると報告されない場合には、そのような領域における不正確さは問題にならない。破線41および42は、それぞれ、モデル構築および位置評価/解釈のためのグラフGの使用を示す。当然のことながら、重要なのはグラフの可視表示ではなく、その内部構造である。
【００３２】
図５Ａは、位置を決定すべき目標装置Tの典型例を示すブロック図である。この例の場合、目標装置Tは高周波ネットワークRNによって通信するポータブルコンピュータとして示されている。たとえば、高周波ネットワークはWLAN(無線ローカルエリアネットワーク)ネットワークとすることができる。図５Ａに示す実施形態の場合、確率モデルPMを有する位置評価モジュールLEMは、目標装置Tには備えられていない。そのため、目標装置Tは、該装置が接続されている一つ以上の基地局BSを通じて、該装置の観測値集合OSを位置評価モジュールLEMに送信しなければならない。位置評価モジュールLEMは、高周波インタフェースRIを通じて、目標装置にその位置評価値LEを戻す。
【００３３】
図５Ｂは、代替実施形態であって、該実施形態においては、目標装置に備えられたコンピュータPCが、確率モデルPMのコピーを、取りはずしのできるメモリDMたとえばCD-ROMディスク上に受信し、目標装置Tは何も送信することなく、それ自身の位置を決定することができる。もう一つの代替実施形態(独立には図示しない)として、備えられているコンピュータPCが、位置評価モジュールLEMへのインターネット(またはその他のデータ)接続を通じて確率モデルを受信することができる。広帯域移動局が高周波インタフェースRIを通じて確率モデルを受信することができる。これらの技術の組合せも使用することができ、受信機が、有線接続によりまたは取りはずしできるメモリ上に、初期確率モデルを受信するが、そのあと、モデルの更新内容が高周波インタフェースによって送信されるようにすることができる。
【００３４】
図６は大きい間隔の取り扱いを示す。この場合、“大きい”というのは、位置決めシステムの必要分解能よりも大きいということを意味する。1 mよりも小さな丸め誤差を有することが望ましい場合、2 mを越える間隔は“大きい”ということになる。そのような大きな間隔は廊下および大きな開かれた空間では普通のことである。この例の場合、グラフ600は廊下の両端に二つの自然発生節点601、605を有するが、目標装置の位置をこれらの端節点の一つであると解釈すると、大きすぎる分割誤差が生じる。したがって好ましくは、グラフ600は、オペレータが曲がりまたは継ぎ目が自然発生する節点601および605を入力する必要はあるが、コンピュータ支援プログラムによって、該プログラムが自動的に必要分解能を越える間隔を認識して必要に応じて追加節点を挿入したかたちに描かれる。たとえば、601から605までの間隔が9 mであり、1 mの丸め誤差が許容される場合、間隔601-605は、三つの追加節点602、603、および604によって、四つの弧611〜614に分割される。
【００３５】
あるいは、節点間の距離が必要分解能よりも大きい場合、節点間の補間を行うことができる。たとえば、目標装置の観測値が節点602および603に対応するが、602がより良く合うという場合には、目標装置の位置は、補間して、602と603との間の点620とすることができる。しかし、多くの用途においては、好ましくは、補間が必要でなく目標装置の位置が評価位置にもっとも近い節点と解釈されるように、十分密に節点を配置する。たとえば、データ採取用途は、評価位置を節点間の点でなくグラフ節点に割り当てることによって簡単化される。
【００３６】
グラフ節点601~605も好ましくは確率モデルPMのサンプル点である。何種類かのサンプル点が存在し、あるいは存在しうる。計測点と呼ばれるタイプのサンプル点は、実際の位置決め環境で実施された実際の計測にもとづくものである。(図４の計測データCD参照。) もう一つのタイプのサンプル点は一つ以上の伝搬モデルPMによって計算される。第三のタイプのサンプル点は計測点または計算点間の補間によって得られる。たとえば、節点601と605とが計測点であるとすると、節点602、603、および604は前記計測点から補間によって得られる。この補間は、下記の理由により、節点601と605における確率分布の総和(平均)によるものとすべきではない。位置決めのために信号強度を使用し、節点601における信号強度が20単位のところに確率ピークを有すると仮定する。節点605においては、確率ピークが40単位のところであるとする。これらの確率分布を平均すると、結集確率分布はやはり20および40単位のところにピークを有するが、結集確率は約30単位のところに一つのピークを有するのが当然であると考えられる。したがって、好ましい形の補間は、補間の基礎となる節点における信号値の累積分布関数の結集によるものである。補間が中間点で行われるのでない場合には、既知の節点に距離に反比例する重みをつける。たとえば、既知の計測点601と605とにもとづいて節点602を補間するとする。節点605は節点601よりも三倍遠くにある。したがって、節点601の累積分布関数には節点605のそれの三倍の重みが与えられる。
【００３７】
図７は、本発明によるグラフにもとづいて確率モデルを作成するための好ましい方法を示す。ステップ71においては、コンピュータ支援設計(CAD)プログラムに似たプログラムが位置決め環境の平面図を表示する。ステップ72においては、オペレータが節点座標と弧を入力する。ステップ73においては、図６に関して述べたように、CADに似たプログラムが必要分解能を越える長さの弧を検出し、これらの弧を、必要分解能よりも短い弧が与えられるような節点を挿入することによって分割する。このプログラムは、最小数の追加節点を自動的に挿入することができ、あるいは適当な数の節点を挿入するようにオペレータを促すことができる。ステップ74においては、グラフGが表示され、またたいていの場合、計測作業員のための地図として使用するために紙に印刷される。ステップ75においては、計測節点が計測され、かつ/または伝搬モデルにもとづく節点が計算される。オペレータが入力する節点は、実際の計測または計算によって決定されたものであるのが好ましい。随意ステップ76においては、コンピュータ挿入節点が計測または計算節点にもとづく補間によって決定される。もう一つの随意ステップ77においては、前述のように、節点間推移確率が代表的な目標装置速度および観測頻度にもとづいて決定される。
【００３８】
図８は、どのようにグラフを経路図(road map)として使用できるかを示す。そのような経路図は、目標装置を最適経路Pによって所望位置まで案内するのに使用することができる。この経路は、たとえば、経路のいくつかの費用パラメータ(cost parameter)、たとえば長さ、時間、およびエネルギーを最小化することによって最適化することができる。周知のように、ある種の経路最適化問題は非常に複雑であり、妥当な時間内では解くことができない。本発明は経路最適化そのものには関係せず、本発明のいくつかの側面は、本発明によるグラフＧの弧から最適経路を構成することに関する。したがって、‘最適’という言葉は必ずしもその経路が実際に最適であるということを意味するものではなく、ある種の最適化プロセス(完全であってもなくても良い)の結果であるということを意味する。
【００３９】
最適経路Pはオペレータまたはロボットに提示することができる。ふたたび図３に示す平面図とグラフを使用する。具体的な例として、環境が病院であり、目標装置を節点(部屋)312にいる医師が携帯し、その医師がただちに節点325に行く必要があるものとする。図８は、最適経路Pがどのようにグラフの弧から形成されるかを示すために、二つの階のそれぞれに関する部分グラフG1とG2から成る全体グラフGを示す。しかし、好ましくは全体グラフGは医師には示されない。その代わりに、節点312-319-310-320-324-321-325を通る最適経路のみが示される。代表的な目標装置たとえばパームトップコンピュータは小さなディスプレイを有するので、好ましくは、最適経路Pと背景の平面図とは、目標装置の検出位置に応じて、部分的に示される。まず、一階の経路部分312-319-310を、平面図31の背景部分とともに示すことができる。目標装置が階段またはエレベータ333に近づくと、その部分が示され、また、目標装置が二階32への入口節点320に近づくと、残りの部分320-324-321-325が示される。このように、グラフ節点が分割された位置を示すだけでなく、グラフの選択された弧が組み合わされて、目標装置の検出位置から所望位置までの最適経路を示すことができる。
【００４０】
図９は位置の解釈と最適経路選択とのさらなる例を示す。警備員が節点910にいて、警報が大きな障害物900の向こう側のどこかで発せられたとする。この警報を送っている目標装置は実際には点920にあるが、当然のことながら、位置決めシステムは正確な位置を知らない。この確率位置決めシステムが、節点(サンプル点)933が目標装置の最近接節点である確率が最大(40%)の節点である、ということを決定したとする。この例の場合、位置決めシステムは、節点931、932、933、934、935、および936がそれぞれ確率5、5、40、35、10、および5%を有するということを決定する。また、この例の場合、目標装置の位置評価値を六つの節点931~936 (または、確率が所定しきい値を越える他の節点部分集合) の確率分布とすることができる。しかし、大部分の実用目的での使用においては、確率分布は単一位置として解釈しなければならない。たとえば、目標装置の位置は、節点931~936の確率重み付き結集値であると解釈することができる。この確率重み付き結集値は位置921として示されている。しばしば有効なのは、目標装置の位置を評価位置921にもっとも近いグラフGの点または節点と解釈することである。位置921にもっとも近いグラフGの点は、点922である。
【００４１】
場合によっては、目標装置の位置をグラフ節点の一つとして(グラフの任意の点ではなく)解釈または割り当てを行うのが望ましい。そのような割り当てにより、たとえば、データ採取または決定を行うのが簡単になる。確率モデルによれば、節点933が最大確率の最近接節点である。目標装置の位置を節点933と解釈すると、節点910からの最適経路Pは節点932を経由するものである。一方、節点934は節点の確率重み付き結集値921にもっとも近い節点である。節点934を目標装置の解釈位置として選択すると、節点910からの最適経路P´は節点935を経由するものである。したがって、実際に選択される好ましい最適経路は、経路のいくつかの費用パラメータたとえば長さまたは時間の期待値を最小化する経路である。
【００４２】
以上の議論では、目標装置の最新観測値のみが該装置の位置評価に使用された。以下では、もっと進んだ、系列にもとづく位置評価法を説明する。
再帰にもとづく方法
【００４３】
時系列をなす観測値o1T=[o1,…,oT]が与えられ、時刻
【数１】
における位置分布qtを決定したいものとする。観測値oiは現在位置qiのみに依存し、qiは先行位置qi-1のみに依存するとする。後者の仮定は、履歴が一つの先行観測値よりも先までは調べられないということを意味する。これらの仮定が満たされる場合には、位置決めの問題を次数(order)1の間接マルコフモデル(HMM)として表現することができる。ここで、o1Tは観測値の系列であり、q1Tは位置の系列である。この場合、o1Tとq1Tの結合(joint)確率は下記のように表される。
【数２】
【００４４】
したがって、結合分布は、
1. 初期状態確率P(q1)、
2. 推移確率P(qt|qt-1)、
3. 観測確率P(ot|qt)、
によって完全に決定される。
【００４５】
すべての位置が省略時選択(default)により同様に可能であるとみなす場合には、すべての位置に対して初期状態確率P(q1)を同じにすることにより、式1を簡単化することができる。その場合、結合分布は推移確率と観測確率とにのみ依存する。これらの確率はいろいろなやり方で定義することができる。たとえば、推移確率は、位置間の空間距離にもとづいて定めることができ、距離の増大につれてゼロに近づくようにすることができる。この再帰にもとづく方法は推移および観測確率がどのように決定されるかにはかかわりなく適用することができるので、以下では、推移確率と観測確率とが与えられていると仮定する。
【００４６】
時刻tにおける位置分布は下記のように定義することができる。
【数３】
ここで、P(o1t,qt)とP(ot+1T|qt)は式3と4(順方向再帰と逆方向再帰)から得られ、P(o1T)は規格化のための観測確率である。Sを、このモデルにおける可能な位置の集合であるとし、n=|S|をSの大きさであるとする。順方向再帰と逆方向再帰との時間的複雑さ(time complexity)をO(Tm)とする。ここでTは履歴の長さであり、mは各時刻ステップにおける非ゼロ推移確率の数を示す。明らかに、
【数４】
である。最悪の場合、すべての推移が非ゼロ確率を有するからである。しかし、大部分の推移は、たとえばm<<n2の場合のように、確率ゼロを有し、計算が非常に速く実行される。
【数５】
【００４７】
このようにして、ある特定の時刻におけるいろいろな位置の確率を得ることができる。しかし、多くの用途においては、位置分布ではなく単一の位置である位置評価値が必要である。この場合にも、時刻tにおける点評価値を計算するのにいくつかのやり方がある。たとえば、点評価値は、位置確率を重みとする位置の重み付き平均とすることができ、あるいは最大確率の位置とすることができる。
【００４８】
可能性最大の経路を見出すためには、Viterbiアルゴリズムを使用することができる。Viterbiアルゴリズムにより、確率P(o1T|q1=s1,…,qT=sT)を最大にする位置の系列s1,…,sTを見出すことができる。明らかに、一つの位置stを時刻tにおける位置評価値として使用することができる。しかし、この方法は、各時刻ステップにおいて、位置評価値が可能な位置の一つであるに過ぎないことがあるという欠点を有する。したがって、位置評価値の正確さは可能な位置の密度に依存する。正確さは、非常に密な可能な位置を有する大きなSを使用することにより、向上させることができるであろう。しかし、これはこのアルゴリズムの必要とする時間が急激に増大するという欠点を有する。
【００４９】
妥当な量の計算により正確な位置評価値を得るために、割合に小さなSを使用し、時刻tにおける位置評価値を可能な位置の重み付き平均Σ(wi・si)/Σwiとして計算することができる。位置siに対する重みwiは、時刻tに位置siを通過する経路のうちもっとも可能性の高いものの確率と定義することができる。経路確率は、順方向の時刻ステップ1〜t(順方向経路の創出)に対して、また逆方向の時刻ステップT〜t(逆方向経路の創出)に対して、Viterbiアルゴリズムを使用し、si(i=1..n)までの順方向および逆方向経路の確率をかけることによって、得ることができる。
【００５０】
当業者には明らかなように、技術の進歩に伴い、本発明の発明的概念はいろいろなやり方で具体化することができる。本発明およびその実施形態は、前述の実施形態の例のみに限定されるものではなく、特許請求の範囲に示す範囲内で変更することができる。
【図面の簡単な説明】
【００５１】
【図１】位置決め法を模式的に示す図である。
【図２】間接マルコフモデルを示す図である。
【図３】本発明によるグラフを示す図である。
【図４】高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMを示す図である。
【図５Ａ】位置を決定すべき代表的目標装置を示すブロック図である。
【図５Ｂ】位置を決定すべき代表的目標装置を示すブロック図である。
【図６】大きい間隔の取り扱いを示す図である。
【図７】本発明によるグラフにもとづいて確率モデルを作成するための好ましい方法を示す図である。
【図８】前記グラフをどのように経路図として使用できるかを示す図である。
【図９】位置解釈と最適経路選択とのさらなる例を示す図である。
【符号の説明】
【００５２】
31 一階の平面図
32 二階の平面図
33 許容されない領域
41、42 モデル構築および位置評価/解釈のためのグラフGの使用を示す破線
310〜325 節点
331〜333 弧
600 グラフ
601、605 自然発生節点
602〜604 追加節点
611〜614 弧
620 602と603との間の補間点
900 障害物
910 節点
920 点
921 評価位置
922 点
931〜936 節点
BS 基地局
DM 取りはずしのできるメモリ
G グラフ
G1、G2 部分グラフ
LEM 位置評価モジュール
LCM 位置計算モジュール
MCM モデル構築モジュール
P、P´ 最適経路
PC パーソナルコンピュータ
PM 確率モデル
RN 高周波ネットワーク、無線通信環境
RI 高周波インタフェース
T 目標装置
o 観測値
q 位置
【技術分野】
【０００１】
本発明は、包括的に言えば、目標装置の無線通信環境に関する観測値の系列にもとづいて目標装置の位置を評価する位置決め技法に関する。
【背景技術】
【０００２】
図１はそのような位置決め技法の一例を模式的に示す。目標装置Tは高周波インタフェース(radio interface)RIにより基地局BSと通信する。この例では、通信は高周波通信であると仮定している。目標装置Tは高周波インタフェースRIにおける信号値を観測する。観測値Oを、目標装置の無線通信環境をモデル化する確率モデルPMに使用し、位置評価値LEを生成する。ここで使用する目標装置という言葉は、その位置を決定すべき装置を意味する。目標装置は無線環境で信号により通信するので、目標装置の位置を決定するために、無線環境における信号値が使用される。たとえば、目標装置は無線ローカルエリアネットワーク(WLAN)で通信するデータ処理装置とすることができる。データ処理装置は汎用のラップトップもしくはパームトップコンピュータまたは通信装置とすることができ、あるいは専用の試験または測定装置たとえばWLANに接続された病院の装置とすることができる。ここで使用する位置という言葉は、1〜3個の座標から成る座標の組を意味する。いくつかの特殊なケースたとえばトンネルの場合、単一の座標で十分でありうるが、大部分の場合、この位置は座標対(x、y、または角度/半径)で表される。
【０００３】
もっと詳しく言えば、本発明は間接(hidden)マルコフモデルにもとづく位置決め技法に関する。図２は間接マルコフモデルHMMを模式的に示す。このモデルは、位置、位置間の推移(transition)、およびこれらの位置で得られる観測値から成る。図２に示す例の場合、目標装置は一つの経路に沿って移動し、該経路に沿って、五つの位置qt-2〜qt+2が示してある。もっと詳しく言えば、qtは時刻tにおける位置分布を定義し、したがってP(qt=s)は目標装置が時刻tに位置sにいる確率である。しかし、位置分布は簡単に一つの位置評価値に変換することができるので、位置分布qを表すのに短縮表記“位置q”を使用する。
【０００４】
目標装置の経路に沿う位置は、経路点と呼ぶことができる。目標装置は無線環境内で信号により通信するので、無線環境内の信号値が目標装置の位置の決定に使用される。
【０００５】
目標装置の実際の例としては、無線ローカルエリアネットワーク(WLAN)またはセルラー高周波ネットワーク内で通信するデータ処理装置がある。このデータ処理装置は汎用のラップトップもしくはパームトップコンピュータまたは通信装置とすることができ、あるいは専用の試験または測定装置たとえばWLANに接続された病院の装置とすることができる。ここで使用する信号値という言葉は、送信機特定信号(fixed transmitter's signal)の測定可能な位置依存量である。たとえば、信号強度およびビット誤り率(bit error rate/ratio)が測定可能な位置依存量の例である。
【０００６】
間接マルコフモデルの‘間接’という言葉は、位置qt-2〜qt+2に主要な関心があるが、これらの位置は直接には観測できないという事実に由来している。信号値にもとづいて、これらの位置の代わりに、一連の観測値ot-2〜ot+2を得ることができるが、観測値ot-2〜ot+2と位置qt-2〜qt+2との間には、簡単な関係がない。(位置qt-2〜qt+2の直線矢印は、目標装置が直線経路に沿って移動すること、あるいは一定の速度で移動すること、または観測が等間隔で行われることを意味するものではない、ということに注意されたい。)
【０００７】
単一の‘観測値’は、一つ以上のチャンネルからのいくつかの信号値測定値を含みうること、また一般に含むということに注意すべきである。確率モデルにおいては、信号値の確率分布を測定するということが考えられるが、いろいろな位置における信号値に重複がある場合、これらの位置は位置あたり一つの測定値によっては決定できない。したがって、確率分布を決定するためには、各観測値は複数の測定値を含むものでなければならない。
【０００８】
図１および２においては、時間が分割されている(quantified)ということにも注意すべきである。すなわち、単一の高周波受信機を有する目標装置は任意の時点において一つのチャンネルしか観測できないが、該高周波受信機は数ミリ秒で別のチャンネルに切り換えることができ、したがって観測値ot-2〜ot+2は一般に少なくとも百ミリ秒だけ離れている。観測値間の間隔は一般的な目標装置の速度に合わせて選択することができる。したがって、高周波受信機をチャンネル間で切り換えなければならない場合でも、単一の観測値がいくつかのチャンネルからの信号値を含むことができる。
【０００９】
高周波受信機は、信号値たとえば信号強度を事実上連続的に測定できるが、間接マルコフモデルにもとづく位置決めに適用する場合、分割された時間における観測値を使用するのが有利である。したがって、‘観測値’というのは、所定の時間間隔からのいくつかの信号値の統計サンプルであると要約することができる。
【００１０】
本発明のもとになった問題は、間接マルコフモデルから出てきたものである。すなわち、距離または位置に対して一意の(monotonous)の関係を有する変数を観測することができないという問題である。この位置決め法は、そのような変数の代わりに信号値の観測結果を使用するものである。しかし、二つ以上の位置が大体同じ信号値の組を有することが可能であり、したがって位置評価値がひどく不正確になりうる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、前記欠点を小さくするような方法と該方法を実施するための装置とを提供することである。言い換えると、本発明の目的は、予測される信号値の確率モデルにもとづく位置決め技法の不確実性を低下させることである。本発明のこの目的は、独立クレームに述べることを特徴とする方法と装置によって達成される。本発明の好ましい実施形態は、従属クレームに開示されている。
【課題を解決するための手段】
【００１２】
本発明は、位置決め環境のトポロジーをモデル化するグラフ(またはグラフの組)の使用にもとづく。一つのグラフG[V,A]は、n個の節点または頂点V=[ν1,ν2,...νn]とm個の弧A=[a1,a2,...am]を有し、ここで各弧ak=(νi,νj)は、νiからνjへの可能な経路または位置推移を示す。したがって、位置決め環境内のすべての可能な経路はグラフGの弧のいろいろな組合せによって記述することができる。たとえば、一般的オフィスのグラフGは各廊下としての弧、廊下を部屋に結びつける(ドアを通じて)弧、その他を有する。複数階から成る環境が、いくつかの相互連結されたグラフ、または弧の一部が垂直位置推移(エレベータ、階段、またはエスカレータ)を示す一つのグラフによって記述されるかどうかは重要あるいは有意(semantics)なことである。コンピュータ支援設計においては、弧は湾曲セグメントを意味するが、グラフ理論においては、本発明におけると同様に、弧は単に二つの節点間の連結を意味する。実際、弧は直線として引かれる。
【００１３】
注意すべきことは、本発明によるグラフは一般に位置決め環境の一つの性質であり、位置決め環境内の障害物にもとづいて決定される、ということである。これは、いくつかの先行技術の位置決め法におけるものとは異なる。後者においては、各目標装置の許容位置は、目標装置自身の位置履歴と実現しうる速度とにもとづいて、独立に決定される。
【００１４】
本発明の利点は、目標装置の報告位置が自然な動きをするということ、すなわち、目標装置が壁その他の障害物を通過して動くように見えるようなことがない、ということである。もう一つの利点は、グラフが、計測値または計算値にもとづいて確率モデルを確立するための十分な基礎として役立つ、ということである。グラフ節点が確率モデルのサンプル点としても使用される場合、この位置決め法は目標装置が移動する可能性の高い領域でもっとも正確である。
【００１５】
目標装置の位置がグラフの点または節点として解釈される場合には、目標装置の動きはコンピュータ解析するのが容易である。言い換えると、十分明確なグラフ上の点または節点として解釈される報告位置は、分割のなされていない任意の位置に比して、データ採取(mining)作業のためのずっとすぐれたデータ源となる。たとえば、デパート店舗設計者は客の動きのパターンまたは相関を調べたいと思うことがあるであろう。グラフ節点がいくつかのデスクに置かれている場合、デスクxで止まった客がデスクyをも通るかどうかを見るのはかなり容易である。グラフと独自の分割とがない場合、設計者は各デスクに近いある領域内で座標を設定しなければならないであろう。各グラフ節点は許容される位置であるが、許容される位置は必ずしもグラフ節点ではない。節点間の距離は必要分解能に応じて選択すべきである。言い換えると、グラフを引く人は、報告位置が真の位置からどれだけ隔たっていても良いか、という質問に答えなければならない。答えは、代表的な目標装置の性質による。目標装置が人が携行する通信装置である場合には、数mの誤差は許容されるであろう。人は数mの距離からは容易に見分けられるからである。一方、目標装置が病院の機器その他である場合には、もっと高い分解能が望ましい。大部分の用途においては、分解能(節点間の距離)は大体1 mである。もっと小さな距離を用いる高い分解能は、資源のより多くの使用によって可能である。使用される資源は、たとえば、計測用のもの、確率モデルを記憶するメモリ、および計算能力である。開かれた空間は、水平および垂直の弧から成る格子として扱うことができる。開かれた空間では、可視性が良好であるから、通常の分解能よりも低い分解能が許容できる。
【００１６】
グラフGは以下のように間接マルコフモデルと結びつけることができる。弧に沿う点間の代表距離をdとする。この代表距離は必要な分解能たとえば1 mである。S=[s1,s2,…sk]を、弧に沿う点の集合とし、点間距離がdであるとする。Sは、間接マルコフモデルの間接状態変数qiの定義域として使用することができる。
【００１７】
グラフGは、好ましくは、グラフ節点間の推移確率の集合と一緒に使用する。推移確率P(qt|qt-1)は、目標装置が二つの観測間に適合する時間間隔内でその位置推移を行うことができる場合にのみ、siからsjへの推移の確率すなわちP(qt=sj|qt-1=si)が非ゼロとなるように、定義することができる。
【００１８】
推移確率を使用するための二つの方法について述べる。第一の方法は、代表的な目標装置の速度、観測間の時間間隔、および点間の距離のみによるものである。dmaxを、観測間の最大時間間隔内に代表的な目標装置が移動する最大距離であるとする。dmaxを越える長さの位置推移は確率ゼロであるかまたはゼロに非常に近い。たとえば、通常の屋内環境において、人が2 m/sよりも速く移動することはめったにない。したがって、二つの観測間の時間が1 sである場合、2 mを越える距離の位置推移の確率はゼロであり、あるいは少なくとも非常に小さい。(この非ゼロ確率は、たとえば、人はめったに走らないが、走るのが厳禁されてはいない、ということを意味する。)
【００１９】
推移確率に関する第二の方法は、隣接点すなわち密接に結びつけられた点の概念によるものである。二つの点siとsjは、Sの他の点を経由することなくAの弧によって互いに到達することができる場合には、隣接点である。この隣接点による方法は、Gの弧の集合が許容される推移の集合でもあるという点ですっきりしたものであり、計算が簡単になる。小さな欠点は、高速移動する目標装置の位置がある遅れをもって報告されるということである。目標装置がその先行評価位置から3節点だけ離れた節点に高速で直線的に移動するとする。隣接点への位置推移のみが許容されているので、位置評価はすべての介在節点を経由して進行しなければならない。そのため、三つの観測時間だけの遅れが生じる。
【００２０】
本発明のもう一つの好ましい実施形態においては、推移確率には、節点間距離と代表的な目標装置速度とにもとづいて、まず予備値が割り当てられる。位置決めシステムが使用されるとき、目標装置の動きの履歴がまとめられ、それから推移確率が実験的に微調整される。
【００２１】
推移確率の使用に関しては、あとで“再帰にもとづく方法”の項でさらに詳しく述べる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を、好ましい実施形態により、添付の図面を参照しつつ、より詳細に説明する。
【００２３】
図３は、本発明によるグラフGを示す。この例の場合、グラフGは二つの部分グラフG1とG2とから成り、部分グラフG1は一階の平面図31に対応し、部分グラフG2は二階の平面図32に対応する。このグラフは、黒丸で示された節点を有し、各節点が目標装置の許容位置を示すようになっている。節点間の距離は必要分解能にもとづいて選択すべきである。大部分の用途においては、分解能(節点間距離)は大体1 mである。もっと小さな距離を用いる高い分解能は、資源のより多くの使用によって可能である。使用される資源は、たとえば、計測用のもの、確率モデルを記憶するメモリ、および計算能力である。大部分のオフィス室に対しては、たとえば左上部の室の節点311のような、単一の節点で十分である。一方、大きな室は、左下部の室の節点312と313のように、もっと多くの節点を有しうる。節点314~319は、開かれた空間に配置された節点である。そのような節点は、多すぎる計算資源を使用することなく、必要な分解能が実現できるように配置すべきである。この平面図は、破線で示された許容されない領域33を有している。たとえば、この許容されない領域は、受付係のデスク、オフィス装置、建築構造物、あるいは目標装置が入れないその他の障害物でありうる。あるいは、もっと正確に表現すると、目標装置は領域33内にはいれるかもしれないが、その位置は領域33の外部にあると解釈される、ということである。
【００２４】
グラフGは、許容される位置を示す節点310、311、その他に加えて、節点間の許容される位置推移を示す弧を含む。図3においては、グラフを簡単にするために、弧は、水平または垂直で、他の節点を通過することなく二つの節点だけを連結する場合にのみ、示されている。たとえば、弧331は節点314と315とを連結し、弧332は節点315と316とを連結するが、節点314と節点316を結ぶ弧はない。
【００２５】
図３に示すオフィス空間は、三次元であるが、連結されたいくつかの二次元空間として扱われている。節点310および320は、それぞれ一階および二階への入口点である。弧333は二つの階への入口点310と320を連結する。
【００２６】
図４は、高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMの一例のブロック図である。図４は、コンパクトな位置評価モジュールLEMを示すが、より複雑な実施形態も可能である。この位置評価モジュールの本質的特徴は目標装置無線環境の確率モデルPMであり、この確率モデルは、高周波インタフェースからの複数の観測値が与えられると、目標装置位置を予想することができる。この例の場合、確率モデルPMがモデル構築モジュールMCMによって構築されて、維持される。モデル構築モジュールMCMは、計測データCDもしくは一つ以上の伝搬(propagation)モデルの形の伝搬データPD、またはこれらの任意の組合せにもとづいて確率モデルを構築し、維持する。計測データCDは、既知の位置(または、これらの位置を他の手段では知り得ない場合、これらの位置の座標を物理的に決定する)での信号値の物理的測定の結果である。随意であるが、計測データレコードは、信号パラメータが時間とともに変化する場合には、測定がなされた時刻をも含むことができる。高周波インタフェースRIをモデル化するのに、計測データＣＤの代わりに、またはこれに加えて、一つ以上の伝搬モデルPDを使用することができる。伝搬モデルは、可視シミュレーションのための光線追跡(ray-tracing)法に似た方法によって構築することができる。計測値が集められる位置を計測点と呼ぶ。計測データCDはデータレコードからなり、各レコードは、当該計測点の位置と該計測点で測定された信号パラメータの集合とを含む。この位置は任意の絶対または相対座標系で表すことができる。特殊な場合、たとえば列車、公道、トンネル、水路、その他では、単一の座標で十分でありうるが、通常は、二つまたは三つの座標が使用される。
【００２７】
目標装置観測値集合OSと確率モデルPMとにもとづいて位置評価値LEを生成するための位置計算モジュールLCMも備えられている。たとえば、この位置計算モジュールは、ラップトップまたはパームトップコンピュータで実行されるソフトウェアプログラムとして具体化することができる。技術的には、‘測定’と‘観測’は同様に実施することができるが、混乱を避けるために、‘測定値’という言葉は一般に計測値に関して使用し、目標装置のそのときの位置で得られた信号パラメータを‘観測値’と呼ぶ。目標装置のもっとも新しい観測値の集合を最新観測値と呼ぶ。
【００２８】
グラフGは、位置決めシステムにおいて、いくつかの主要用途を有する。たとえば、グラフは確率モデルの構築時に使用することができる。確率モデルのサンプル点は、好ましくはグラフの節点に配置される。たとえば、モデル構築モジュールMCMは、好ましくは、各グラフ節点に対してサンプル点が実際に決定された(計測、シミュレーション、または補間された)ということを自動チェックする機能を有する。
【００２９】
グラフは、また、可能な位置の間での推移確率を決定するための十分な根拠ともなる。
【００３０】
最後に、グラフは目標装置の位置を評価または解釈するのに使用することができる。たとえば、目標装置の位置は、評価位置にもっとも近い弧上の一点であると解釈できる。この場合、位置はグラフの一つの弧の上にあると強制的に解釈される。さらに、この位置を、評価位置にもっとも近いグラフ節点であると解釈することができる。いくつかの中間評価値を組み合わせることによって、最終的な位置解釈を行うことができる。
【００３１】
グラフの一部またはすべてが、好ましくは、確率モデルのサンプル点がグラフの節点に配置され、かつ目標装置の位置がグラフにもとづいて評価または解釈されるように使用される。許容される位置はグラフ節点またはその近くにあるので、位置決めはグラフ節点近くでもっとも正確である。逆に、位置決めは許容されない位置たとえば領域33では相対的に不正確でありうるが、この領域にまったくはいれない場合、または少なくともこの領域の内部が目標装置の位置であると報告されない場合には、そのような領域における不正確さは問題にならない。破線41および42は、それぞれ、モデル構築および位置評価/解釈のためのグラフGの使用を示す。当然のことながら、重要なのはグラフの可視表示ではなく、その内部構造である。
【００３２】
図５Ａは、位置を決定すべき目標装置Tの典型例を示すブロック図である。この例の場合、目標装置Tは高周波ネットワークRNによって通信するポータブルコンピュータとして示されている。たとえば、高周波ネットワークはWLAN(無線ローカルエリアネットワーク)ネットワークとすることができる。図５Ａに示す実施形態の場合、確率モデルPMを有する位置評価モジュールLEMは、目標装置Tには備えられていない。そのため、目標装置Tは、該装置が接続されている一つ以上の基地局BSを通じて、該装置の観測値集合OSを位置評価モジュールLEMに送信しなければならない。位置評価モジュールLEMは、高周波インタフェースRIを通じて、目標装置にその位置評価値LEを戻す。
【００３３】
図５Ｂは、代替実施形態であって、該実施形態においては、目標装置に備えられたコンピュータPCが、確率モデルPMのコピーを、取りはずしのできるメモリDMたとえばCD-ROMディスク上に受信し、目標装置Tは何も送信することなく、それ自身の位置を決定することができる。もう一つの代替実施形態(独立には図示しない)として、備えられているコンピュータPCが、位置評価モジュールLEMへのインターネット(またはその他のデータ)接続を通じて確率モデルを受信することができる。広帯域移動局が高周波インタフェースRIを通じて確率モデルを受信することができる。これらの技術の組合せも使用することができ、受信機が、有線接続によりまたは取りはずしできるメモリ上に、初期確率モデルを受信するが、そのあと、モデルの更新内容が高周波インタフェースによって送信されるようにすることができる。
【００３４】
図６は大きい間隔の取り扱いを示す。この場合、“大きい”というのは、位置決めシステムの必要分解能よりも大きいということを意味する。1 mよりも小さな丸め誤差を有することが望ましい場合、2 mを越える間隔は“大きい”ということになる。そのような大きな間隔は廊下および大きな開かれた空間では普通のことである。この例の場合、グラフ600は廊下の両端に二つの自然発生節点601、605を有するが、目標装置の位置をこれらの端節点の一つであると解釈すると、大きすぎる分割誤差が生じる。したがって好ましくは、グラフ600は、オペレータが曲がりまたは継ぎ目が自然発生する節点601および605を入力する必要はあるが、コンピュータ支援プログラムによって、該プログラムが自動的に必要分解能を越える間隔を認識して必要に応じて追加節点を挿入したかたちに描かれる。たとえば、601から605までの間隔が9 mであり、1 mの丸め誤差が許容される場合、間隔601-605は、三つの追加節点602、603、および604によって、四つの弧611〜614に分割される。
【００３５】
あるいは、節点間の距離が必要分解能よりも大きい場合、節点間の補間を行うことができる。たとえば、目標装置の観測値が節点602および603に対応するが、602がより良く合うという場合には、目標装置の位置は、補間して、602と603との間の点620とすることができる。しかし、多くの用途においては、好ましくは、補間が必要でなく目標装置の位置が評価位置にもっとも近い節点と解釈されるように、十分密に節点を配置する。たとえば、データ採取用途は、評価位置を節点間の点でなくグラフ節点に割り当てることによって簡単化される。
【００３６】
グラフ節点601~605も好ましくは確率モデルPMのサンプル点である。何種類かのサンプル点が存在し、あるいは存在しうる。計測点と呼ばれるタイプのサンプル点は、実際の位置決め環境で実施された実際の計測にもとづくものである。(図４の計測データCD参照。) もう一つのタイプのサンプル点は一つ以上の伝搬モデルPMによって計算される。第三のタイプのサンプル点は計測点または計算点間の補間によって得られる。たとえば、節点601と605とが計測点であるとすると、節点602、603、および604は前記計測点から補間によって得られる。この補間は、下記の理由により、節点601と605における確率分布の総和(平均)によるものとすべきではない。位置決めのために信号強度を使用し、節点601における信号強度が20単位のところに確率ピークを有すると仮定する。節点605においては、確率ピークが40単位のところであるとする。これらの確率分布を平均すると、結集確率分布はやはり20および40単位のところにピークを有するが、結集確率は約30単位のところに一つのピークを有するのが当然であると考えられる。したがって、好ましい形の補間は、補間の基礎となる節点における信号値の累積分布関数の結集によるものである。補間が中間点で行われるのでない場合には、既知の節点に距離に反比例する重みをつける。たとえば、既知の計測点601と605とにもとづいて節点602を補間するとする。節点605は節点601よりも三倍遠くにある。したがって、節点601の累積分布関数には節点605のそれの三倍の重みが与えられる。
【００３７】
図７は、本発明によるグラフにもとづいて確率モデルを作成するための好ましい方法を示す。ステップ71においては、コンピュータ支援設計(CAD)プログラムに似たプログラムが位置決め環境の平面図を表示する。ステップ72においては、オペレータが節点座標と弧を入力する。ステップ73においては、図６に関して述べたように、CADに似たプログラムが必要分解能を越える長さの弧を検出し、これらの弧を、必要分解能よりも短い弧が与えられるような節点を挿入することによって分割する。このプログラムは、最小数の追加節点を自動的に挿入することができ、あるいは適当な数の節点を挿入するようにオペレータを促すことができる。ステップ74においては、グラフGが表示され、またたいていの場合、計測作業員のための地図として使用するために紙に印刷される。ステップ75においては、計測節点が計測され、かつ/または伝搬モデルにもとづく節点が計算される。オペレータが入力する節点は、実際の計測または計算によって決定されたものであるのが好ましい。随意ステップ76においては、コンピュータ挿入節点が計測または計算節点にもとづく補間によって決定される。もう一つの随意ステップ77においては、前述のように、節点間推移確率が代表的な目標装置速度および観測頻度にもとづいて決定される。
【００３８】
図８は、どのようにグラフを経路図(road map)として使用できるかを示す。そのような経路図は、目標装置を最適経路Pによって所望位置まで案内するのに使用することができる。この経路は、たとえば、経路のいくつかの費用パラメータ(cost parameter)、たとえば長さ、時間、およびエネルギーを最小化することによって最適化することができる。周知のように、ある種の経路最適化問題は非常に複雑であり、妥当な時間内では解くことができない。本発明は経路最適化そのものには関係せず、本発明のいくつかの側面は、本発明によるグラフＧの弧から最適経路を構成することに関する。したがって、‘最適’という言葉は必ずしもその経路が実際に最適であるということを意味するものではなく、ある種の最適化プロセス(完全であってもなくても良い)の結果であるということを意味する。
【００３９】
最適経路Pはオペレータまたはロボットに提示することができる。ふたたび図３に示す平面図とグラフを使用する。具体的な例として、環境が病院であり、目標装置を節点(部屋)312にいる医師が携帯し、その医師がただちに節点325に行く必要があるものとする。図８は、最適経路Pがどのようにグラフの弧から形成されるかを示すために、二つの階のそれぞれに関する部分グラフG1とG2から成る全体グラフGを示す。しかし、好ましくは全体グラフGは医師には示されない。その代わりに、節点312-319-310-320-324-321-325を通る最適経路のみが示される。代表的な目標装置たとえばパームトップコンピュータは小さなディスプレイを有するので、好ましくは、最適経路Pと背景の平面図とは、目標装置の検出位置に応じて、部分的に示される。まず、一階の経路部分312-319-310を、平面図31の背景部分とともに示すことができる。目標装置が階段またはエレベータ333に近づくと、その部分が示され、また、目標装置が二階32への入口節点320に近づくと、残りの部分320-324-321-325が示される。このように、グラフ節点が分割された位置を示すだけでなく、グラフの選択された弧が組み合わされて、目標装置の検出位置から所望位置までの最適経路を示すことができる。
【００４０】
図９は位置の解釈と最適経路選択とのさらなる例を示す。警備員が節点910にいて、警報が大きな障害物900の向こう側のどこかで発せられたとする。この警報を送っている目標装置は実際には点920にあるが、当然のことながら、位置決めシステムは正確な位置を知らない。この確率位置決めシステムが、節点(サンプル点)933が目標装置の最近接節点である確率が最大(40%)の節点である、ということを決定したとする。この例の場合、位置決めシステムは、節点931、932、933、934、935、および936がそれぞれ確率5、5、40、35、10、および5%を有するということを決定する。また、この例の場合、目標装置の位置評価値を六つの節点931~936 (または、確率が所定しきい値を越える他の節点部分集合) の確率分布とすることができる。しかし、大部分の実用目的での使用においては、確率分布は単一位置として解釈しなければならない。たとえば、目標装置の位置は、節点931~936の確率重み付き結集値であると解釈することができる。この確率重み付き結集値は位置921として示されている。しばしば有効なのは、目標装置の位置を評価位置921にもっとも近いグラフGの点または節点と解釈することである。位置921にもっとも近いグラフGの点は、点922である。
【００４１】
場合によっては、目標装置の位置をグラフ節点の一つとして(グラフの任意の点ではなく)解釈または割り当てを行うのが望ましい。そのような割り当てにより、たとえば、データ採取または決定を行うのが簡単になる。確率モデルによれば、節点933が最大確率の最近接節点である。目標装置の位置を節点933と解釈すると、節点910からの最適経路Pは節点932を経由するものである。一方、節点934は節点の確率重み付き結集値921にもっとも近い節点である。節点934を目標装置の解釈位置として選択すると、節点910からの最適経路P´は節点935を経由するものである。したがって、実際に選択される好ましい最適経路は、経路のいくつかの費用パラメータたとえば長さまたは時間の期待値を最小化する経路である。
【００４２】
以上の議論では、目標装置の最新観測値のみが該装置の位置評価に使用された。以下では、もっと進んだ、系列にもとづく位置評価法を説明する。
再帰にもとづく方法
【００４３】
時系列をなす観測値o1T=[o1,…,oT]が与えられ、時刻
【数１】
における位置分布qtを決定したいものとする。観測値oiは現在位置qiのみに依存し、qiは先行位置qi-1のみに依存するとする。後者の仮定は、履歴が一つの先行観測値よりも先までは調べられないということを意味する。これらの仮定が満たされる場合には、位置決めの問題を次数(order)1の間接マルコフモデル(HMM)として表現することができる。ここで、o1Tは観測値の系列であり、q1Tは位置の系列である。この場合、o1Tとq1Tの結合(joint)確率は下記のように表される。
【数２】
【００４４】
したがって、結合分布は、
1. 初期状態確率P(q1)、
2. 推移確率P(qt|qt-1)、
3. 観測確率P(ot|qt)、
によって完全に決定される。
【００４５】
すべての位置が省略時選択(default)により同様に可能であるとみなす場合には、すべての位置に対して初期状態確率P(q1)を同じにすることにより、式1を簡単化することができる。その場合、結合分布は推移確率と観測確率とにのみ依存する。これらの確率はいろいろなやり方で定義することができる。たとえば、推移確率は、位置間の空間距離にもとづいて定めることができ、距離の増大につれてゼロに近づくようにすることができる。この再帰にもとづく方法は推移および観測確率がどのように決定されるかにはかかわりなく適用することができるので、以下では、推移確率と観測確率とが与えられていると仮定する。
【００４６】
時刻tにおける位置分布は下記のように定義することができる。
【数３】
ここで、P(o1t,qt)とP(ot+1T|qt)は式3と4(順方向再帰と逆方向再帰)から得られ、P(o1T)は規格化のための観測確率である。Sを、このモデルにおける可能な位置の集合であるとし、n=|S|をSの大きさであるとする。順方向再帰と逆方向再帰との時間的複雑さ(time complexity)をO(Tm)とする。ここでTは履歴の長さであり、mは各時刻ステップにおける非ゼロ推移確率の数を示す。明らかに、
【数４】
である。最悪の場合、すべての推移が非ゼロ確率を有するからである。しかし、大部分の推移は、たとえばm<<n2の場合のように、確率ゼロを有し、計算が非常に速く実行される。
【数５】
【００４７】
このようにして、ある特定の時刻におけるいろいろな位置の確率を得ることができる。しかし、多くの用途においては、位置分布ではなく単一の位置である位置評価値が必要である。この場合にも、時刻tにおける点評価値を計算するのにいくつかのやり方がある。たとえば、点評価値は、位置確率を重みとする位置の重み付き平均とすることができ、あるいは最大確率の位置とすることができる。
【００４８】
可能性最大の経路を見出すためには、Viterbiアルゴリズムを使用することができる。Viterbiアルゴリズムにより、確率P(o1T|q1=s1,…,qT=sT)を最大にする位置の系列s1,…,sTを見出すことができる。明らかに、一つの位置stを時刻tにおける位置評価値として使用することができる。しかし、この方法は、各時刻ステップにおいて、位置評価値が可能な位置の一つであるに過ぎないことがあるという欠点を有する。したがって、位置評価値の正確さは可能な位置の密度に依存する。正確さは、非常に密な可能な位置を有する大きなSを使用することにより、向上させることができるであろう。しかし、これはこのアルゴリズムの必要とする時間が急激に増大するという欠点を有する。
【００４９】
妥当な量の計算により正確な位置評価値を得るために、割合に小さなSを使用し、時刻tにおける位置評価値を可能な位置の重み付き平均Σ(wi・si)/Σwiとして計算することができる。位置siに対する重みwiは、時刻tに位置siを通過する経路のうちもっとも可能性の高いものの確率と定義することができる。経路確率は、順方向の時刻ステップ1〜t(順方向経路の創出)に対して、また逆方向の時刻ステップT〜t(逆方向経路の創出)に対して、Viterbiアルゴリズムを使用し、si(i=1..n)までの順方向および逆方向経路の確率をかけることによって、得ることができる。
【００５０】
当業者には明らかなように、技術の進歩に伴い、本発明の発明的概念はいろいろなやり方で具体化することができる。本発明およびその実施形態は、前述の実施形態の例のみに限定されるものではなく、特許請求の範囲に示す範囲内で変更することができる。
【図面の簡単な説明】
【００５１】
【図１】位置決め法を模式的に示す図である。
【図２】間接マルコフモデルを示す図である。
【図３】本発明によるグラフを示す図である。
【図４】高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMを示す図である。
【図５Ａ】位置を決定すべき代表的目標装置を示すブロック図である。
【図５Ｂ】位置を決定すべき代表的目標装置を示すブロック図である。
【図６】大きい間隔の取り扱いを示す図である。
【図７】本発明によるグラフにもとづいて確率モデルを作成するための好ましい方法を示す図である。
【図８】前記グラフをどのように経路図として使用できるかを示す図である。
【図９】位置解釈と最適経路選択とのさらなる例を示す図である。
【符号の説明】
【００５２】
31 一階の平面図
32 二階の平面図
33 許容されない領域
41、42 モデル構築および位置評価/解釈のためのグラフGの使用を示す破線
310〜325 節点
331〜333 弧
600 グラフ
601、605 自然発生節点
602〜604 追加節点
611〜614 弧
620 602と603との間の補間点
900 障害物
910 節点
920 点
921 評価位置
922 点
931〜936 節点
BS 基地局
DM 取りはずしのできるメモリ
G グラフ
G1、G2 部分グラフ
LEM 位置評価モジュール
LCM 位置計算モジュール
MCM モデル構築モジュール
P、P´ 最適経路
PC パーソナルコンピュータ
PM 確率モデル
RN 高周波ネットワーク、無線通信環境
RI 高周波インタフェース
T 目標装置
o 観測値
q 位置
【特許請求の範囲】
【請求項１】
無線通信環境内の目標装置(T)の位置を評価する方法であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)を維持し、
各観測値が目標装置の経路に沿うそれぞれの位置に対応する、信号値の観測値の系列(OS)を作成し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデル(HMM)を構成する、
ことから成る方法において、
当該目標装置による推移の為の無線通信環境のトポロジーをモデル化するグラフ(G)を構成し、ここで、該グラフが、
各節点が無線通信環境内の許容される位置を示す、節点の集合(310〜323;601〜605)と、
各弧が二つの節点間の許容される目標装置の位置推移を示す、弧の集合(331〜333;611〜614)と、
を示し、
当該グラフ(G)によって示される節点間の、当該目的装置による推移の為の推移確率を決定し(77)、
確率モデル(PM)と観測値の系列(OS)とにもとづいて目標装置の位置を評価するのに節点間の推移確率を含むグラフ(G)を使用し、
当該グラフを使用するステップが、目標装置の位置を評価し、弧の集合(331〜333;611〜614)の１つ以上の弧(612)に沿う点(602、603、620;922, 933, 934)として評価位置を解釈する、
ことを特徴とする方法。
【請求項２】
前記グラフを使用するステップが、目標装置の位置を評価し、評価位置を該評価位置にもっとも近い弧の点(602、603、620)と解釈することから成ることを特徴とする請求項１に記載の方法。
【請求項３】
目標装置の評価位置を該評価位置にもっとも近い節点(602)と解釈することを特徴とする請求項２に記載の方法。
【請求項４】
前記グラフを使用するステップが、目標装置の位置を、グラフ点または節点の部分集合として評価し、該部分集合の各点または節点に確率を付与し、評価位置を、点または節点の前記部分集合の確率重み付き結集値と解釈することから成ることを特徴とする請求項１に記載の方法。
【請求項５】
各弧が、二つの観測間に適合する時間間隔における二つの節点間の許容される目標装置の位置推移を示すことを特徴とする請求項１から４の中のいずれか１つに記載の方法。
【請求項６】
節点を確率モデル(PM)のサンプル点として使用することを特徴とする請求項１から５の中のいずれか１つに記載の方法。
【請求項７】
グラフ(G)を構成するステップが、プログラムされたコンピュータによって実行される下記の作業、
オペレータからオペレータが指示する節点および弧の座標を受け取ること(72)と、
長さが、代表的な目標装置速度と観測間の代表的な時間間隔とにもとづく所定の最大距離を越える弧(600)を検出して、そのような弧を追加節点(602〜604)によって分割すること(73)と、
から成ることを特徴とする請求項１に記載の方法。
【請求項８】
確率モデル(PM)のサンプル点をグラフ(G)の節点に配置し、
計測および/または伝搬モデルにもとづいて、オペレータ指示の節点におけるサンプル点の少なくともいくつかを決定し、
オペレータ指示の節点からの補間により、前記追加節点における少なくともいくつかのサンプル点を決定すること、
を特徴とする請求項７に記載の方法。
【請求項９】
前記推移確率が、代表的な目標装置速度と観測間の代表的な時間間隔とにもとづくものであることを特徴とする請求項１から８の中のいずれか１つに記載の方法。
【請求項１０】
目標装置(T)の検出節点(312)からその所望節点(325)への節点の最適化された経路(P)を構成し、該最適化された経路の構成が、グラフ(G)の弧に沿った複数の可能な経路の中から費用パラメータの集合を最小化する経路を選択することから成ることを特徴とする請求項１から９の中のいずれか１つに記載の方法。
【請求項１１】
前記最適化された経路(P)を背景となる地図または平面図(31、32)に重ねて表示することを特徴とする請求項１０に記載の方法。
【請求項１２】
目標装置の検出位置に応じて前記最適化された経路(P)の一部を表示することを特徴とする請求項１０または１１に記載の方法。
【請求項１３】
目標装置の位置を、観測値の系列(OS)に関する一回以上の再帰にもとづいて評価することを特徴とする請求項１から１２に記載の方法。
【請求項１４】
前記一回以上の再帰が順方向再帰と逆方向再帰とから成ることを特徴とする請求項１３に記載の方法。
【請求項１５】
無線通信環境(RN)内の目標装置(T)の位置を評価する位置評価モジュール(LEM)であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)と、
各観測値が目標装置の経路に沿うそれぞれの位置に対応し、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成するような、信号値の観測値の系列(OS)を作成する手段と、
から成る位置評価モジュールにおいて、
当該目標装置による推移の為の無線通信環境のトポロジーをモデル化するグラフ(G)であって、
各節点が無線通信環境内の許容される位置を示す、いくつかの節点(310〜323;601〜605)と、
各弧が二つの節点間の許容される目標装置の位置推移を示す、いくつかの弧(331〜333;611〜614)と、
を示すグラフと、
当該グラフ(G)によって示される節点間の、当該目標装置による推移の為の推移確率を決定する(77)手段と、
確率モデル(PM)と観測値の系列(OS)と節点間の推移確率を含むグラフ(G)にもとづいて目標装置の位置を評価する手段と、
弧の集合(331〜333;611〜614)の１つ以上の弧(612)に沿う点(602、603、620;922, 933, 934)として目標装置の評価位置を解釈する手段と、
を特徴とする位置評価モジュール。
【請求項１６】
位置評価モジュールが目標装置(T)内に備えられることを特徴とする請求項１５に記載の位置評価モジュール(LEM)。
【請求項１７】
位置評価モジュールが無線通信環境(RN)の定置要素内に備えられることを特徴とする請求項１５に記載の位置評価モジュール(LEM)。
【請求項１】
無線通信環境内の目標装置(T)の位置を評価する方法であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)を維持し、
各観測値が目標装置の経路に沿うそれぞれの位置に対応する、信号値の観測値の系列(OS)を作成し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデル(HMM)を構成する、
ことから成る方法において、
当該目標装置による推移の為の無線通信環境のトポロジーをモデル化するグラフ(G)を構成し、ここで、該グラフが、
各節点が無線通信環境内の許容される位置を示す、節点の集合(310〜323;601〜605)と、
各弧が二つの節点間の許容される目標装置の位置推移を示す、弧の集合(331〜333;611〜614)と、
を示し、
当該グラフ(G)によって示される節点間の、当該目的装置による推移の為の推移確率を決定し(77)、
確率モデル(PM)と観測値の系列(OS)とにもとづいて目標装置の位置を評価するのに節点間の推移確率を含むグラフ(G)を使用し、
当該グラフを使用するステップが、目標装置の位置を評価し、弧の集合(331〜333;611〜614)の１つ以上の弧(612)に沿う点(602、603、620;922, 933, 934)として評価位置を解釈する、
ことを特徴とする方法。
【請求項２】
前記グラフを使用するステップが、目標装置の位置を評価し、評価位置を該評価位置にもっとも近い弧の点(602、603、620)と解釈することから成ることを特徴とする請求項１に記載の方法。
【請求項３】
目標装置の評価位置を該評価位置にもっとも近い節点(602)と解釈することを特徴とする請求項２に記載の方法。
【請求項４】
前記グラフを使用するステップが、目標装置の位置を、グラフ点または節点の部分集合として評価し、該部分集合の各点または節点に確率を付与し、評価位置を、点または節点の前記部分集合の確率重み付き結集値と解釈することから成ることを特徴とする請求項１に記載の方法。
【請求項５】
各弧が、二つの観測間に適合する時間間隔における二つの節点間の許容される目標装置の位置推移を示すことを特徴とする請求項１から４の中のいずれか１つに記載の方法。
【請求項６】
節点を確率モデル(PM)のサンプル点として使用することを特徴とする請求項１から５の中のいずれか１つに記載の方法。
【請求項７】
グラフ(G)を構成するステップが、プログラムされたコンピュータによって実行される下記の作業、
オペレータからオペレータが指示する節点および弧の座標を受け取ること(72)と、
長さが、代表的な目標装置速度と観測間の代表的な時間間隔とにもとづく所定の最大距離を越える弧(600)を検出して、そのような弧を追加節点(602〜604)によって分割すること(73)と、
から成ることを特徴とする請求項１に記載の方法。
【請求項８】
確率モデル(PM)のサンプル点をグラフ(G)の節点に配置し、
計測および/または伝搬モデルにもとづいて、オペレータ指示の節点におけるサンプル点の少なくともいくつかを決定し、
オペレータ指示の節点からの補間により、前記追加節点における少なくともいくつかのサンプル点を決定すること、
を特徴とする請求項７に記載の方法。
【請求項９】
前記推移確率が、代表的な目標装置速度と観測間の代表的な時間間隔とにもとづくものであることを特徴とする請求項１から８の中のいずれか１つに記載の方法。
【請求項１０】
目標装置(T)の検出節点(312)からその所望節点(325)への節点の最適化された経路(P)を構成し、該最適化された経路の構成が、グラフ(G)の弧に沿った複数の可能な経路の中から費用パラメータの集合を最小化する経路を選択することから成ることを特徴とする請求項１から９の中のいずれか１つに記載の方法。
【請求項１１】
前記最適化された経路(P)を背景となる地図または平面図(31、32)に重ねて表示することを特徴とする請求項１０に記載の方法。
【請求項１２】
目標装置の検出位置に応じて前記最適化された経路(P)の一部を表示することを特徴とする請求項１０または１１に記載の方法。
【請求項１３】
目標装置の位置を、観測値の系列(OS)に関する一回以上の再帰にもとづいて評価することを特徴とする請求項１から１２に記載の方法。
【請求項１４】
前記一回以上の再帰が順方向再帰と逆方向再帰とから成ることを特徴とする請求項１３に記載の方法。
【請求項１５】
無線通信環境(RN)内の目標装置(T)の位置を評価する位置評価モジュール(LEM)であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)と、
各観測値が目標装置の経路に沿うそれぞれの位置に対応し、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成するような、信号値の観測値の系列(OS)を作成する手段と、
から成る位置評価モジュールにおいて、
当該目標装置による推移の為の無線通信環境のトポロジーをモデル化するグラフ(G)であって、
各節点が無線通信環境内の許容される位置を示す、いくつかの節点(310〜323;601〜605)と、
各弧が二つの節点間の許容される目標装置の位置推移を示す、いくつかの弧(331〜333;611〜614)と、
を示すグラフと、
当該グラフ(G)によって示される節点間の、当該目標装置による推移の為の推移確率を決定する(77)手段と、
確率モデル(PM)と観測値の系列(OS)と節点間の推移確率を含むグラフ(G)にもとづいて目標装置の位置を評価する手段と、
弧の集合(331〜333;611〜614)の１つ以上の弧(612)に沿う点(602、603、620;922, 933, 934)として目標装置の評価位置を解釈する手段と、
を特徴とする位置評価モジュール。
【請求項１６】
位置評価モジュールが目標装置(T)内に備えられることを特徴とする請求項１５に記載の位置評価モジュール(LEM)。
【請求項１７】
位置評価モジュールが無線通信環境(RN)の定置要素内に備えられることを特徴とする請求項１５に記載の位置評価モジュール(LEM)。
【図１】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−２９４９（Ｐ２００９−２９４９Ａ）
【公開日】平成２１年１月８日（２００９．１．８）
【国際特許分類】
【出願番号】特願２００８−１５９５６２（Ｐ２００８−１５９５６２）
【出願日】平成２０年６月１８日（２００８．６．１８）
【分割の表示】特願２００４−５２０６９８（Ｐ２００４−５２０６９８）の分割
【原出願日】平成１５年７月８日（２００３．７．８）
【出願人】（５０３２３２４０９）
【Ｆターム（参考）】
【公開日】平成２１年１月８日（２００９．１．８）
【国際特許分類】
【出願日】平成２０年６月１８日（２００８．６．１８）
【分割の表示】特願２００４−５２０６９８（Ｐ２００４−５２０６９８）の分割
【原出願日】平成１５年７月８日（２００３．７．８）
【出願人】（５０３２３２４０９）
【Ｆターム（参考）】
[ Back to top ]