(57)【要約】目標装置の位置が位置評価モジュール(LEM)によって評価される。該モジュールは、各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)を含む。位置評価モジュール(LEM)は、信号値の観測値on(n=1,2,3．．．)の系列(OS)を作成する。各観測値は目標装置の経路に沿うそれぞれの位置qnに対応する。観測値の系列とそれぞれの位置とが間接マルコフモデルを構成する。このモジュールは、確率モデル(PM)と前記観測値の系列とにもとづいて目標装置の位置qnを評価し、このとき、前記観測値の系列は一つ以上の未来の観測値on+mを含み、ここでmは正の整数である。言い換えると、目標装置の位置が、少なくとも一部はその未来に関する知識にもとづいて、評価される。
2005528621.tif 000002
【特許請求の範囲】
【請求項１】
目標装置(T)の位置を評価する方法であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)を維持し、
各観測値が目標装置の経路に沿うそれぞれの位置qnに対応する、信号値の観測値on(n=1．．．．Ｎ)の系列(OS)を作成し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成する、
ことから成る方法において、
確率モデル(PM)と前記観測値の系列とにもとづいて目標装置の位置qtを評価し、このとき、前記観測値の系列が一つ以上の未来の観測値ot+mを含み、ここでmが正の整数であって、
【数１】
2005528621.tif 000015
である、
ことを特徴とする方法。
【請求項２】
前記観測値の集合が一つ以上の過去の観測値on-mを含むことを特徴とする請求項１に記載の方法。
【請求項３】
一つ以上の過去の観測値の順方向再帰、
一つ以上の未来の観測値の逆方向再帰、
にもとづいて、目標装置の位置qnを評価することを特徴とする請求項２に記載の方法。
【請求項４】
サンプル点間の目標装置の推移確率を評価し、一部この推移確率にもとづいて目標装置の位置を評価することを特徴とする請求項１から３の中のいずれか１つに記載の方法。
【請求項５】
前記推移確率を評価し、これらの確率を観測値の系列を作成する前に前記確率モデルとともに記憶することを特徴とする請求項２に記載の方法。
【請求項６】
前記位置評価ステップを目標装置(T)で実行することを特徴とする請求項１から５の中のいずれか１つに記載の方法。
【請求項７】
前記位置評価ステップを、目標装置が高周波ネットワーク(RN)を通じて観測値の系列を報告する定置装置で実行することを特徴とする請求項１から５の中のいずれか１つに記載の方法。
【請求項８】
少なくとも一つの測定可能な信号値(x)に信号強度が含まれることを特徴とする請求項１から７の中のいずれか１つに記載の方法。
【請求項９】
少なくとも一つの測定可能な信号値(x)にビット誤り率が含まれることを特徴とする請求項１から８の中のいずれか１つに記載の方法。
【請求項１０】
目標装置(T)の位置を評価する位置評価モジュール(LEM)であって、
各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデル(PM)、
各観測値が目標装置の経路に沿うそれぞれの位置qnに対応し、このとき、該観測値の系列とそれぞれの位置とが間接マルコフモデルを構成するような、信号値の観測値on(n=1．．．．N)の系列(OS)を作成する手段、
から成るモジュールにおいて、
確率モデル(PM)と前記観測値の系列とにもとづいて目標装置の位置qtを評価し、このとき、前記観測値の系列が一つ以上の未来の観測値ot+mを含み、ここでmが正の整数であって、
【数２】
2005528621.tif 000016
であるような、目標装置の位置qtを評価する手段、
から成ることを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的に言えば、目標装置の無線通信環境に関する観測値の系列にもとづいて目標装置の位置を評価する位置決め技法に関する。
【背景技術】
【０００２】
図１はそのような位置決め技法の一例を模式的に示す。目標装置Tは高周波インタフェース(radio interface)RIにより基地局BSと通信する。この例では、通信は高周波通信であると仮定している。目標装置Tは高周波インタフェースRIにおける信号値を観測する。観測値Oを、目標装置の無線通信環境をモデル化する確率モデルPMに使用し、位置評価値LEを生成する。ここで使用する目標装置という言葉は、その位置を決定すべき装置を意味する。目標装置は無線環境で信号により通信するので、目標装置の位置を決定するために、無線環境における信号値が使用される。たとえば、目標装置は無線ローカルエリアネットワーク(WLAN)で通信するデータ処理装置とすることができる。データ処理装置は汎用のラップトップもしくはパームトップコンピュータまたは通信装置とすることができ、あるいは専用の試験または測定装置たとえばWLANに接続された病院の装置とすることができる。ここで使用する位置という言葉は、1〜3個の座標から成る座標の組を意味する。いくつかの特殊なケースたとえばトンネルの場合、単一の座標で十分でありうるが、大部分の場合、この位置は座標対(x、y、または角度/半径)で表される。
【０００３】
もっと詳しく言えば、本発明は間接(hidden)マルコフモデルにもとづく位置決め技法に関する。図２は間接マルコフモデルを模式的に示す。このモデルは、位置、位置間の推移(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の直線矢印は、目標装置が直線経路に沿って、あるいは一定の速度で移動していること、または観測が等間隔で行われることを意味するものではない、ということに注意されたい。)
【０００７】
本発明のもとになった問題は、間接マルコフモデルから出てきたものである。すなわち、距離または位置に対して一意の(monotonous)の関係を有する変数を観測することができないという問題である。この位置決め法は、そのような変数の代わりに信号値の観測結果を使用するものである。二つ以上の位置が大体同じ信号値の組を有することが可能であり、したがって位置評価値がひどく不正確になりうる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、前記欠点を小さくするような方法と該方法を実施するための装置とを提供することである。言い換えると、本発明の目的は、予測される信号値の確率モデルにもとづく位置決め技法の不確実性を低下させることである。本発明のこの目的は、独立クレームに述べることを特徴とする方法と装置によって達成される。本発明の好ましい実施形態は、従属クレームに開示されている。
【課題を解決するための手段】
【０００９】
本発明は、目標装置の位置に関する不確定さを低下させるために、目標装置の未来の観測値を使用するというアイデアにもとづく。ちょっと考えると、このアイデアはばかげているように思われる。なぜなら、どんな時刻にも、目標装置の未来の観測値は未知であるからである。すなわち、本発明の明らかな限界は、少なくとも一つの未来の観測値を有する観測値の集合にしか適用できない、ということである。言い換えると、本発明は目標装置の最新の観測値に関する不確定さを直接に低下させることはできない。しかし、本発明は、部分的に、目標装置の過去の観測値に関する不確定さを低下させることから利益の得られる多くの応用がある、という意外な発見にもとづく。たとえば、本発明は、ショッピングカートに適当な目標装置を取りつけることにより、店舗内での買物客の経路を追跡するのに使用することができる。そのような情報は店舗内での商品の配置を考えるのに有用でありうる。買物客の経路が、買物客がショッピングカートを持ち出しまたもとに戻すそれぞれの場所で始まりまた終わると仮定する。この場合、店舗の所有者は最新の位置を正確に決定することには関心がない。すべての経路は精算場所で終わるからである。一方、店舗の所有者は店舗内の買物客の経路を決定することに関心があり、また最新の観測値は店舗内での先行位置の不確定さを低下させるのに使用することができる。
【００１０】
本発明の方法は下記の各ステップから成る。
1.各サンプル点がサンプル位置と該サンプル点における信号値の予測分布とから成る、複数のサンプル点に関する確率モデルを維持し、
2.各観測値が目標装置の経路に沿うそれぞれの位置qnに対応する、信号値の観測値on(n=1、2、3．．．．)の系列を作成し、このとき、前記観測値の系列とそれぞれの位置とが間接マルコフモデルを構成し、
3.確率モデルと前記観測値の集合とにもとづいて目標装置の位置qnを評価し、このとき、前記観測値の集合が少なくとも一つの観測値on+mを含み、ここでmが正の整数である。
【００１１】
サンプル点というのは、確率モデルの点、すなわち、信号値の分布が計測(calibration)(物理的測定)またはシミュレーションもしくは理論計算によって知られる点である。サンプル点は他の既知の位置から補間または外挿によって得ることもできる。
【００１２】
位置決めの正確さは一つ以上の過去の観測値を使用することによってさらに改善することができる。過去および未来の観測値は好ましくは2方向の再帰によって結集される。すなわち、時間が左から右に進むとすると、過去の観測値は左から右への(順方向)再帰によって考慮され、未来の観測値は右から左への(逆方向)再帰によって考慮される。
【００１３】
本発明を実時間位置決めに使用する場合、少なくとも一つの観測値の遅れを許容しなければならない。実時間位置決めにおけるこの遅れを最小限に抑えるためには、未来の観測値の数を小さく保たなければならない。ここで使用する実時間位置決めという言葉は、一つまたは二三の観測値の遅れがあるとしても、目標装置を技術的に可能な最大速度で位置決めするということを意味する。
【発明を実施するための最良の形態】
【００１４】
以下、本発明を、好ましい実施形態により、添付の図面を参照しつつ、より詳細に説明する。
【００１５】
ふたたび図２を参照すると、この図には、一連の信号値観測値ot-2〜ot+2が示してある。それぞれの観測値に対して、目標装置経路に沿うそれぞれの位置qt-2〜qt+2が示されている。この関係を矢印21で示す。矢印21の向きは位置qtが観測値otに含まれる信号値を決定するが逆は真でないということを示す。言い換えると、直接観測できるのは信号値だけであって、観測値otから対応する位置qtへの簡単な関係はないということである。開かれた海上では、信号値は送信機からの距離とともに予想可能な減少を示すが、本発明が使用される環境の事実上すべてにおいて、送信機からの直接経路はしばしば妨害され、そうでない場合でも、直接経路が送信の行われるただ一つの経路というわけではない。多重経路による送信は、位相によって、強めあうように干渉したり、弱めあうように干渉したりしうる。したがって、位置と信号値との関係は一意であるというにはほど遠く、いくつかの位置がある信号値を共有するということが起こりうる。いくつかのチャンネルで観測を行うことが、目標装置の位置の不確定さを低下させる一つの方法である。
【００１６】
図３は本発明の原理を示す。本発明においては、目標装置の現在位置に関する不確定さを、目標装置の未来に関する知識を使用することによって、さらに低下させることができる。前述のように、既知の未来を有する位置は過去にしか存在しないが、本発明は、部分的には、過去が問題である多くの状況や応用が多く存在するという発見にもとづく。時刻tにおける目標装置の位置すなわち位置qtを決定したいものとする。矢印33は、対応する観測値otから位置qtへの関係を示す。通常、観測値otは位置qtを決定するのに最善の単一の観測値である。単一の‘観測値’は、一つ以上のチャンネルからのいくつかの信号値測定値を含みうるということ、また一般に含むということに注意されたい。このことは、確率モデルにおいて、一つの信号値の確率分布を測定するということであり、いろいろな位置における信号値に重なりがある場合には、これらの位置は位置ごとの単一測定値にもとづいては決定できないということである。したがって、各測定値は、確率分布を決定するために、複数の測定値を含んでいなければならない。
【００１７】
図１および２においては、時間が分割されている(quantified)ということにも注意すべきである。すなわち、単一の高周波受信機を有する目標装置は任意の時点において一つのチャンネルしか観測できないが、該高周波受信機は数ミリ秒で別のチャンネルに切り換えることができ、したがって観測値ot-2〜ot+2は一般に少なくとも百ミリ秒だけ離れている。観測値間の間隔は一般的な目標装置の速度に合わせて選択することができる。したがって、高周波受信機をチャンネル間で切り換えなければならない場合でも、単一の観測値がいくつかのチャンネルからの信号値を含むことができる。
【００１８】
本発明においては、目標装置の位置qtの不確定さを、現在の観測値otばかりでなく一つ以上の未来の観測値ot+m(mは正の整数)を使用することによって、低下させることができる。二つの未来の観測値ot+1とot+2とがそれぞれ矢印34と35によって示してある。当然のことながら、位置決めの不確定実性を低下させるために、それぞれ矢印31と32で示すように、先行観測値ot-2とot-1をも使用することができる。
【００１９】
本発明は目標装置の位置および/または経路を評価するのに使用することができる。これら二つの用途(位置および経路の評価)は、詳しくは下記のように言うことができる。位置の評価では、観測値の系列が与えられたとき、単一位置の確率が最大になるようにしたい。式としては、p(qt|O1T)を最大にしたいということである。(あるいは、最小期待誤差を有する位置を決定したい場合も考えられ、たとえば位置評価値をいくつかの位置の確率重み付き平均とすることができる。)経路の評価の場合、観測値の系列が与えられたときに、経路(位置の系列)の確率を最大化したいということになる。式としては、p(qtT|O1T)を最大にしたいということである。(あるいは、最小期待誤差を有する経路を決定したい場合も考えられる。)これら二つの用途の間の違いは、位置評価の場合、各位置が個別に評価される(ただし、観測値の系列にもとづいて)ということである。この場合、連続位置からなる経路が、該経路が各個別位置の確率を最大化するものであるときに、壁を通過するなどといったことはありそうにない。経路の評価の場合、もっとも確率の高い経路が選択される。経路評価は、位置間の推移確率を決定して、それぞれの位置確率と推移確率との結集値を最大化する経路を決定して最大確率の経路を決定することにより、実行することができる。
【００２０】
図２および３には、一次の(first-order)間接マルコフモデルを示すが、本発明の方法は任意の次数の間接マルコフモデルに適用することができる。
【００２１】
図４は、高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMの一例のブロック図である。図４は、コンパクトな位置評価モジュールLEMを示すが、より複雑な実施形態も可能である。この位置評価モジュールの本質的特徴は目標装置無線環境の確率モデルPMであり、この確率モデルは、高周波インタフェースからの複数の観測値が与えられると、目標装置位置を予想することができる。この例の場合、確率モデルPMがモデル構築モジュールMCMによって構築されて、維持される。モデル構築モジュールMCMは、計測データCDもしくは一つ以上の伝搬(propagation)モデルの形の伝搬データPD、またはこれらの任意の組合せにもとづいて確率モデルを構築し、維持する。計測データCDは、既知の位置(または、これらの位置を他の手段では知り得ない場合、これらの位置の座標を物理的に決定する)での信号値の物理的測定の結果である。随意であるが、計測データレコードは、信号パラメータが時間とともに変化する場合には、測定がなされた時刻をも含むことができる。高周波インタフェースRIをモデル化するのに、計測データＣＤの代わりに、またはこれに加えて、一つ以上の伝搬モデルPDを使用することができる。伝搬モデルは、可視シミュレーションのための光線追跡(ray-tracing)法に似た方法によって構築することができる。計測値が集められる位置を計測点と呼ぶ。計測データCDはデータレコードからなり、各レコードは、当該計測点の位置と該計測点で測定された信号パラメータの集合とを含む。この位置は任意の絶対または相対座標系で表すことができる。特殊な場合、たとえば列車、公道、トンネル、水路、その他では、単一の座標で十分でありうるが、通常は、二つまたは三つの座標が使用される。
【００２２】
目標装置観測値集合OSと確率モデルPMとにもとづいて位置評価値LEを生成するための位置計算モジュールLCMも備えられている。たとえば、この位置計算モジュールは、ラップトップまたはパームトップコンピュータで実行されるソフトウェアプログラムとして具体化することができる。技術的には、‘測定(measurements)’と‘観測(observations)’は同様に実施することができるが、混乱を避けるために、‘測定値’という言葉は一般に計測値に関して使用し、目標装置のそのときの位置で得られた信号パラメータを‘観測値’と呼ぶ。目標装置のもっとも新しい観測値の集合を最新観測値と呼ぶ。
【００２３】
図５Ａは、位置を決定すべき目標装置Tの典型例を示すブロック図である。この例の場合、目標装置Tは高周波ネットワークRNによって通信するポータブルコンピュータとして示されている。たとえば、高周波ネットワークはWLAN(無線ローカルエリアネットワーク)ネットワークとすることができる。図５Ａに示す実施形態の場合、確率モデルPMを有する位置評価モジュールLEMは、目標装置Tには備えられていない。そのため、目標装置Tは、該装置が接続されている一つ以上の基地局BSを通じて、該装置の観測値集合OSを位置評価モジュールLEMに送信しなければならない。位置評価モジュールLEMは、高周波インタフェースRIを通じて、目標装置にその位置評価値LEを戻す。
【００２４】
図５Ｂは、代替実施形態であって、該実施形態においては、目標装置に備えられたコンピュータPCが、確率モデルPMのコピーを、取りはずしのできるメモリDMたとえばCD-ROMディスク上に受信し、目標装置Tは何も送信することなく、それ自身の位置を決定することができる。もう一つの代替実施形態(独立には図示しない)として、備えられているコンピュータPCが、位置評価モジュールLEMへのインターネット(またはその他のデータ)接続を通じて確率モデルを受信することができる。広帯域移動局が高周波インタフェースRIを通じて確率モデルを受信することができる。これらの技術の組合せも使用することができ、受信機が、有線接続によりまたは取りはずしできるメモリ上に、初期確率モデルを受信するが、そのあと、モデルの更新内容が高周波インタフェースによって送信されるようにすることができる。
【００２５】
図６は位置決めの不確実性を低下させるための簡単な実施例を示す。この実施例は下記のように実施される。位置空間は離散位置として分離表示されている。図６には、これらの位置のうち、位置q1-1〜q3-8が十字印として示してある。目標装置がとる可能な経路が、位置q1-1、q2-2、q2-3、q2-4、およびq3-3に黒い円で示してある。目標装置の第二の観測値が、位置q1-3が位置q2-2の代替物として可能であることを示すとする。言い換えると、単一の観測値だけでは、第二の観測がなされたときに、目標装置位置がq2-2にあるかq1-3にあるかを決定するのに不十分であるということである。同様に、位置q1-5が位置q2-3の可能な代替物であり、位置q1-8が位置q2-4の可能な代替物であるとする。しかし、第五の観測値は位置q3-3にあるとする解釈しか許さないとする。すなわち、たとえば、目標装置位置q3-3が他の手段によって決定できるか、または位置q3-3が第五の観測信号値を有する唯一の位置である場合である。図６に示す例の場合、位置q1-8を排除することができる。既知の位置q3-3への推移には目標装置が実現できない速度が必要だからである。注意すべきことは、代替位置q1-3、q1-5、およびq１-8はどれも過去の観測値によっては排除できないが、これらの位置はいずれもその未来によって排除できる、ということである。位置q1-8は第五の観測値に対する位置q3-3に到達するのに必要な速度が不可能な大きさのものであるために、直接に排除することができる。位置q1-5は不可能な位置q1-8に導くので排除することができ、以下同様である。
【００２６】
図６は障害物のない開いた空間を示していることに注意すべきである。現実の世界の環境では、位置間の直接推移の多くが障害物によって妨害される。そのような障害物は位置(サンプル点)間の推移の推移確率を決定することによって考慮することができる。たとえば、二つの位置間の推移確率は、これらの位置が壁その他の障害物によって分離されている場合、またはその推移が目標装置が実現できない速度を必要とする場合には、ゼロである。推移確率に関しては、以下で“再帰にもとづく方法”の項でさらに説明する。
【００２７】
図６に示す例は、本発明の別の適用を示唆している。本発明は、目標装置の過去の位置を計算するのに使用する代わりに、実時間位置評価の信頼性を向上させるために使用することができる。本発明は、既知の未来がある場合にのみ使用することができるので、少なくとも一つの観測分の遅れを許容しなければならない。しかし、やや意外なことであるが、ある遅れの導入により、位置評価の正確さを向上させることができる。まず、目標装置の位置が実時間で報告される、すなわち、技術的に可能な最大速度で、未来の観測値を使用することなく、報告されるとする。この場合、目標装置の位置評価値は迅速に報告されるが、評価値は非常に不正確になりうる。これに対して、本発明の方法を使用し、位置評価値が、少なくとも一つの未来観測値が使用できる位置に関してのみ報告される場合には、位置評価値はある遅れをもって報告されるが、この評価値が非常に不正確になるという可能性はずっと小さい。
【００２８】
図６に示す実施例の場合、目標装置の位置が離散変数として扱われる。言い換えると、目標装置は離散位置q1-1〜q3-8の一つにある。位置を連続変数として扱うもっと進んだ実施例については、以下で述べる。
【００２９】
図６に示す実施例の場合、q1-1からq3-3への推移は、目標装置が不可能な大きな速度を必要とするということから、排除される。もっと定量的に言えば、そのような推移の推移確率がゼロであるということである。位置間の推移確率が既知である場合、このモデルの信頼性はさらに向上させることができる。この推移確率は実測、またはシミュレーション、もしくは理論計算によって決定することができる。
再帰にもとづく方法
【００３０】
時系列をなす観測値
【数３】
2005528621.tif 000003
が与えられ、時刻
【数４】
2005528621.tif 000004
における位置分布qtを決定したいものとする。観測値oiは現在位置qiのみに依存し、qiは先行位置qi-1のみに依存するとする。後者の仮定は、履歴が一つの先行観測値よりも先までは調べられないということを意味する。これらの仮定が満たされる場合には、位置決めの問題を次数(order)1の間接マルコフモデル(HMN)として表現することができる。ここで、o1Tは観測値の系列であり、q1Tは位置の系列である。この場合、o1Tとq1Tの結合(joint)確率は下記のように表される。
【数５】
2005528621.tif 000005
【００３１】
したがって、結合分布は、
1.初期状態確率P(q1)、
2.推移確率P(qt|qt-1)、
3.観測確率P(ot|qt)、
によって完全に決定される。
【００３２】
すべての位置が省略時選択(default)により同様に可能であるとみなす場合には、すべての位置に対して初期状態確率P(q1)を同じにすることにより、式1を簡単化することができる。その場合、結合分布は推移確率と観測確率とにのみ依存する。これらの確率はいろいろなやり方で定義することができる。たとえば、推移確率は、位置間の空間距離にもとづいて定めることができ、距離の増大につれてゼロに近づくようにすることができる。本発明は推移および観測確率がどのように決定されるかにはかかわりなく適用することができるので、以下では、推移確率と観測確率とが与えられていると仮定する。
【００３３】
時刻tにおける位置分布は下記のように定義することができる。
【数６】
2005528621.tif 000006
ここで、P(o1t,qt)とP(ot+1T|qt)は式3と4(順方向再帰と逆方向再帰)から得られ、P(o1T)は規格化のための観測確率である。Sを、このモデルにおける可能な位置の集合であるとし、n=|S|をSの大きさであるとする。順方向再帰と逆方向再帰との時間的複雑さ(time complexity)をO(Tm)とし、ここでTは履歴の長さであり、mは各時刻ステップにおける非ゼロ推移確率の数を示す。明らかに、
【数７】
2005528621.tif 000007
である。最悪の場合、すべての推移が非ゼロ確率を有するからである。しかし、大部分の推移は、たとえばm<<n2の場合のように、確率ゼロを有し、計算が非常に速く実行される。
【数８】
2005528621.tif 000008
【００３４】
このようにして、ある特定の時刻におけるいろいろな位置の確率を得ることができる。しかし、多くの用途においては、位置分布ではなく単一の位置に関する位置評価値が必要である。この場合にも、時刻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)までの順方向および逆方向経路の確率をかけることによって、得ることができる。
実施例
【００３７】
以下に詳細を示す計算は、少なくともある種の状況下で、本発明により、実時間位置決めの場合でさえも、位置決めの正確さを向上させうる、ということを示すものである。状況によっては、この向上は著しいものになりうる。下記の表１は、(離散)時刻t=1〜5における位置A〜Fの観測確率を示す。太字は各時刻ステップにおける実際の経路A、B、D、E、Fの観測確率を示す。時刻t=3の実際の位置はDであるが、位置Cの方が大きな観測確率を有する。したがって、その時点での観測確率のみにもとづく位置決めでは、この点において間違いが起こる。表２は、位置A〜Fでの推移確率を示す。表３〜５は、それぞれ、順、逆、および2方向再帰の規格化計算結果(式3、4、および2)を示す。ここでも、各時刻ステップにおける実際の位置の確率を、太字で示す。表６は時刻t=３における位置A〜Fの確率を示す。
【００３８】
表１  観測確率
【表１】
2005528621.tif 000009
【００３９】
表２  推移確率
【表２】
2005528621.tif 000010
【００４０】
表３  順方向再帰
【表３】
2005528621.tif 000011
【００４１】
表４  逆方向再帰
【表４】
2005528621.tif 000012
【００４２】
表５  2方向再帰
【表５】
2005528621.tif 000013
【００４３】
表６  時刻t=3における位置A〜Fの確率
【表６】
2005528621.tif 000014
【００４４】
この実施例の場合、5回の観測のあと、第三の観測時刻における目標装置の最善の評価位置はDになる。Dが正しい位置である確率は86%であり、それは表６に太字で示してある。しかし、順方向再帰も逆方向再帰も一つだけでは、Dがもっとも可能性の高い位置であるということを決定することはできない。順方向再帰はCとBがDよりも可能性の高い位置であることを示し、また逆方向再帰は位置EとFとの方が可能性の高い位置であることを示している。2方向再帰により、間違った位置評価が事実上なくなる。
【００４５】
当業者には明らかなように、技術の進歩に伴い、本発明の発明的概念はいろいろなやり方で具体化することができる。本発明およびその実施形態は、前述の実施形態のみに限定されるものではなく、特許請求の範囲に示す範囲内で変更することができる。
【図面の簡単な説明】
【００４６】
【図１】位置決め法を模式的に示す図である。
【図２】間接マルコフモデルを示す図である。
【図３】本発明の原理を示す流れ図である。
【図４】高周波インタフェースRIにおける信号値にもとづいて目標装置の位置を評価するための位置評価モジュールLEMを示す図である。
【図５Ａ】位置を決定すべき代表的目標装置を示すブロック図である。
【図５Ｂ】位置を決定すべき代表的目標装置を示すブロック図である。
【図６】位置決めの不確実さを低下させるための簡単な実施例を示す図である。
【符号の説明】
【００４７】
BS  基地局
RI  高周波インタフェース
DM  取りはずしのできるメモリ
LEM  位置評価モジュール
LCM  位置計算モジュール
MCM  モデル構築モジュール
PC  パーソナルコンピュータ
PM  確率モデル
RN  高周波ネットワーク
T  目標装置
o  観測値
q  位置
【図１】
2005528621.tif 000017
【図２】
2005528621.tif 000018
【図３】
2005528621.tif 000019
【図４】
2005528621.tif 000020
2005528621.tif 000021
【図６】
2005528621.tif 000022
【国際調査報告】
2005528621.tif 000023
2005528621.tif 000024