モンテカルロ法による局所化

モンテ カルロ位置推定( MCL ) は、粒子フィルタ位置推定とも呼ばれ、^{[ 1 ]}粒子フィルタを使用してロボットが位置推定を行うアルゴリズムです。^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]}環境のマップが与えられると、このアルゴリズムはロボットが移動して環境を感知する際の位置と向きを推定します。 ^{[ 4 ]}このアルゴリズムは粒子フィルタを使用して、可能性のある状態の分布を表します。各粒子は可能な状態、つまりロボットがどこにいるかという仮説を表します。^{[ 4 ]}このアルゴリズムは通常、配置空間上の粒子の均一でランダムな分布から開始します。つまり、ロボットは自分がどこにいるかについての情報を持たず、空間内のどの点にいても等しく可能性があると想定します。^{[ 4 ]}ロボットが移動するたびに、粒子をシフトして、移動後の新しい状態を予測します。ロボットが何かを感知するたびに、粒子は再帰ベイズ推定、つまり実際の感知データと予測された状態との相関関係に基づいて再サンプリングされます。最終的には粒子はロボットの実際の位置に向かって収束するはずです。^{[ 4 ]}

基本的な説明

環境の内部地図を持つロボットを考えてみましょう。ロボットが動き回る際には、この地図上のどこにいるかを知る必要があります。センサー観測を用いてロボットの位置と回転（より一般的には姿勢）を決定することを、ロボット位置推定と呼びます。

ロボットは常に完全に予測可能な行動をとるとは限らないため、次にどこへ行くかについてランダムな推測を数多く生成します。これらの推測は粒子と呼ばれます。それぞれの粒子には、起こり得る将来の状態に関する完全な記述が含まれています。ロボットが環境を観察する際、観察結果と矛盾する粒子を破棄し、一見矛盾しない粒子に近い粒子をさらに生成します。最終的には、ほとんどの粒子がロボットの実際の位置へと収束することが期待されます。

州の代表

ロボットの状態は、アプリケーションと設計によって異なります。例えば、典型的な2Dロボットの状態は、位置と向きのタプル で構成されます。10個の関節を持つロボットアームの場合は、各関節の角度を含むタプル となる場合があります。 ${\displaystyle (x,y,\theta )}$ ${\displaystyle x,y}$ ${\displaystyle \theta}$ ${\displaystyle (\theta _{1},\theta _{2},...,\theta _{10})}$

ロボットの現在の状態に関する推定値である確信度は、状態空間に分布する確率密度関数である。[ 1 ] ^{[ 4 ] MCLアルゴリズムで}は、ある時点における確信度は粒子の集合によって表される。^{[ 4 ]}各粒子は状態を含むため、ロボットの状態に関する仮説と見なすことができる。状態空間において粒子数が多い領域は、ロボットが存在する確率が高いことに対応し、粒子数が少ない領域はロボットが存在する可能性が低い。 ${\displaystyle t}$ ${\displaystyle M}$ ${\displaystyle X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace }$

このアルゴリズムは、現在の状態の確率分布が前の状態にのみ依存し（それ以前の状態に依存せず）、つまりはにのみ依存するというマルコフ性を前提としています。^{[ 4 ]}これは、環境が静的で時間とともに変化しない場合にのみ機能します。^{[ 4 ]}通常、起動時にはロボットは現在の姿勢に関する情報を持っていないため、粒子は構成空間に均一に分布しています。^{[ 4 ]}${\displaystyle X_{t}}$ ${\displaystyle X_{t-1}}$

概要

環境のマップが与えられた場合、アルゴリズムの目的は、ロボットが環境内で の姿勢を決定することです。

アルゴリズムは毎回、前回の信念、作動コマンド、センサーから受信したデータを入力として受け取り、新しい信念を出力します。^{[ 4 ]}${\displaystyle t}$ ${\displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M]}\rbrace }$ ${\displaystyle u_{t}}$ ${\displaystyle z_{t}}$ ${\displaystyle X_{t}}$

アルゴリズム MCL : for to : motion_update sensor_update${\displaystyle (X_{t-1},u_{t},z_{t})}$ ${\displaystyle {\bar {X_{t}}}=X_{t}=\emptyset }$ ${\displaystyle m=1}$ ${\displaystyle M}$ ${\displaystyle x_{t}^{[m]}=}$ ${\displaystyle (u_{t},x_{t-1}^{[m]})}$ ${\displaystyle w_{t}^{[m]}=}$ ${\displaystyle (z_{t},x_{t}^{[m]})}$ ${\displaystyle {\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{[m]},w_{t}^{[m]}\rangle }$  エンドフォー〜の ために：${\displaystyle m=1}$ ${\displaystyle M}$ 確率的に 引き出す${\displaystyle x_{t}^{[m]}}$ ${\displaystyle {\bar {X_{t}}}}$ ${\displaystyle \propto w_{t}^{[m]}}$ ${\displaystyle X_{t}=X_{t}+x_{t}^{[m]}}$  エンドフォー 戻る${\displaystyle X_{t}}$ 

1Dロボットの例

ロボットは、ドアがあるか (左)、ドアがないか (右) のみを判別できるセンサーを搭載し、1 次元の廊下に沿って移動します。

ドアの有無に応じて true または falseを返すセンサーを使用し、3 つの同一のドアがある1 次元の円形廊下を移動するロボットを考えます。

${\displaystyle t=0}$
アルゴリズムは粒子の均一な分布で初期化されます。ロボットは、物理的には最初のドアにいても、廊下の空間上のどの地点にいても、その可能性は等しいとみなします。	センサーの更新：ロボットはドアを検知します。各パーティクルに重みを割り当てます。このセンサーの読み取り値を示す可能性が高いパーティクルには、より高い重みが割り当てられます。	再サンプリング：ロボットは新しい粒子の集合を生成します。そのほとんどは、以前の粒子の周囲に生成された、より重みのある粒子です。ロボットは3つのドアのいずれかにいると認識します。

${\displaystyle t=1}$
モーション更新：ロボットは右へ少し移動します。すべてのパーティクルも右に移動し、ノイズが適用されます。ロボットは物理的には2番目と3番目のドアの間にいます。	センサーの更新：ロボットはドアを検知しません。各パーティクルに重みを割り当てます。このセンサー値を示す可能性が高いパーティクルには、より高い重みが割り当てられます。	再サンプリング：ロボットは新しい粒子の集合を生成します。そのほとんどは、以前の粒子の周囲に生成された、より重みのある粒子です。ロボットは、現在、自分が2つの位置のいずれかにいると認識しています。

${\displaystyle t=2}$
モーション更新：ロボットは左に少し移動します。すべてのパーティクルも左に移動し、ノイズが適用されます。ロボットは物理的に2番目のドアにいます。	センサーの更新：ロボットはドアを検知します。各パーティクルに重みを割り当てます。このセンサー値を示す可能性が高いパーティクルには、より高い重みが割り当てられます。	リサンプリング：ロボットは新しい粒子群を生成します。そのほとんどは、以前の粒子の周囲に重みが増した状態で生成されます。ロボットは自己位置推定に成功しました。

3 回の反復の最後に、ほとんどの粒子が希望どおりにロボットの実際の位置に収束します。

モーションアップデート

センシングなしで一般的なモーション モデルを使用した2D ロボットが数ステップ移動した後の確信。

動作更新中に、ロボットは各粒子にシミュレートされた動作を適用することにより、与えられた作動コマンドに基づいて新しい位置を予測する。^{[ 1 ]}たとえば、ロボットが前進する場合、すべての粒子は、それらがどの方向を向いているかに関係なく、それぞれの方向へ前進する。ロボットが時計回りに 90 度回転する場合、すべての粒子は、それらがどこにいるかに関係なく、時計回りに 90 度回転する。 しかし、現実の世界では、アクチュエータは完璧ではなく、望ましい動作量をオーバーシュートまたはアンダーシュートする場合があります。ロボットが直線で運転しようとすると、ホイール半径のわずかな違いにより、必然的にどちらかの側に曲がる。^{[ 1 ]}したがって、動作モデルはノイズを補正する必要があります。結果として、粒子は動作更新中に必然的に発散します。ロボットが環境を感知せずに盲目的に移動する場合には、ロボットは自分の位置をあまり確信できなくなるため、これは予想されることです。

センサーの更新

ロボットが環境を感知すると、粒子を更新して、現在地をより正確に反映します。各粒子について、ロボットは、その粒子の状態にあったとしたら、センサーが実際に感知したものを知覚する確率を計算します。そして、その確率に比例する重みを各粒子に割り当てます。次に、ロボットは、確率が に比例する以前の確信から、新しい粒子をランダムに抽出します。センサーの読み取り値と一致する粒子は（おそらく複数回）選択される可能性が高く、センサーの読み取り値と一致しない粒子はほとんど選択されません。そのため、粒子はロボットの状態をより正確に推定する方向に収束します。ロボットは環境を感知するにつれて、自分の位置をますます確信するようになるため、これは予想されたことです。 ${\displaystyle w_{t}^{[i]}}$ ${\displaystyle M}$ ${\displaystyle w_{t}^{[i]}}$

プロパティ

非パラメトリシティ

MCL の中核を成すパーティクルフィルタは、非パラメトリック表現であるため、複数の異なる種類の確率分布を近似することができる。[ 4 ]カルマンフィルタ（^{およびその変種}である拡張カルマンフィルタとアンセンテッドカルマンフィルタ）などの他のベイズ局所化アルゴリズムでは、ロボットの確信はガウス分布に近いと仮定しており、確信がマルチモーダルな状況ではうまく機能しない。^{[ 4 ]}たとえば、似たようなドアが多数ある長い廊下にいるロボットは、ドアごとにピークを持つ確信に到達する可能性があるが、ロボットはどのドアにいるのかを区別することができない。このような状況では、パーティクルフィルタはパラメトリックフィルタよりも優れたパフォーマンスを発揮する可能性がある。^{[ 4 ]}

マルコフ局在化に対するもう一つの非パラメトリックなアプローチは、ヒストグラムを用いて確信度分布を表すグリッドベース局在化である。グリッドベースアプローチと比較して、モンテカルロ局在化はサンプルで表される状態が離散化されていないため、より正確である。^{[ 2 ]}

計算要件

粒子フィルタの時間計算量は粒子数に対して線形である。当然のことながら、粒子数が多いほど精度は向上するため、速度と精度の間には妥協点があり、最適な値を見つけることが望ましい。選択すべき戦略の一つは、次のコマンドとセンサー読み取り値のペアが到着するまで、継続的に粒子を生成し続けることである。^{[ 4 ]}この方法により、ロボットの他の部分の機能を妨げずに、可能な限り多くの粒子を得ることができる。このように、実装は利用可能な計算リソースに適応的である。プロセッサの速度が速いほど、より多くの粒子を生成でき、したがってアルゴリズムの精度も向上する。^{[ 4 ]}${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle u_{t}}$ ${\displaystyle z_{t}}$

グリッドベースのマルコフ局在化と比較して、モンテカルロ局在化では、メモリ使用量が粒子の数にのみ依存し、マップのサイズに応じて変化しないため、メモリ使用量が削減され、^{[ 2 ]}より高い頻度で測定値を積分することができます。^{[ 2 ]}

このアルゴリズムは、以下に説明するように、ロボットの位置の確実性に基づいて使用する粒子の数を調整する KLD サンプリングを使用して改善できます。

粒子欠乏

モンテカルロ法による局所化の単純な実装の欠点は、ロボットが一点に留まり、移動せずに環境を繰り返し検知するというシナリオで発生する。^{[ 4 ]}粒子がすべて誤った状態に収束すると仮定する。あるいは、粒子が収束した後に、隠れた手がロボットを持ち上げて新しい場所に移動させると仮定する。収束した状態から遠く離れた粒子が次の反復で選択されることは稀であるため、反復ごとに粒子の数が少なくなり、ついには完全に消滅してしまう。この時点で、アルゴリズムは回復することができない。^{[ 4 ]}この問題は、粒子数が少ない場合（例えば、）、および粒子が広い状態空間に分散している場合に発生する可能性が高くなります。^{[ 4 ]}実際、粒子フィルタアルゴリズムは、再サンプリングの段階で、正しい状態に近いすべての粒子を誤って破棄する可能性があります。^{[ 4 ]}${\displaystyle M\leq 50}$

この問題を緩和する1つの方法は、反復ごとにランダムに粒子を追加することです。^{[ 4 ]}これは、どの時点でもロボットがマップ内のランダムな位置に誘拐される可能性がわずかにあると仮定することと同等であり、その結果、動作モデルにランダムな状態の一部が発生します。^{[ 4 ]}マップ内のどの領域も粒子が完全に失われないようにすることで、アルゴリズムは粒子の喪失に対して堅牢になります。

変種

オリジナルのモンテカルロ法による局所化アルゴリズムは非常にシンプルです。このアルゴリズムには、欠点を克服したり、特定の状況でより効果的なものとなるように改良したいくつかのバリエーションが提案されています。

KLDサンプリング

モンテカルロ法による局所化は、カルバック・ライブラー情報（KLD）を用いた誤差推定に基づいて適応的に粒子をサンプリングすることで改善される可能性がある。マップ全体を均一にランダムに分布させた粒子で覆う必要があるため、初期段階では大きなサンプルサイズが必要となる。しかし、粒子が同じ場所に収束すると、これほど大きなサンプルサイズを維持することは計算上の無駄が生じる。^{[ 6 ]}${\displaystyle M}$

KLDサンプリングはモンテカルロ局所化の変種であり、各反復においてサンプルサイズが計算されます。サンプルサイズは、確率 において、真の事後分布とサンプルベースの近似値との誤差が 未満となるように計算されます。変数と は固定パラメータです。^{[ 4 ]}${\displaystyle M_{x}}$ ${\displaystyle M_{x}}$ ${\displaystyle 1-\delta }$ ${\displaystyle \epsilon }$ ${\displaystyle \delta}$ ${\displaystyle \epsilon }$

基本的な考え方は、状態空間に重ね合わせたグリッド（ヒストグラム）を作成することです。ヒストグラムの各ビンは最初は空です。各反復処理において、新しい粒子は、その重みに比例した確率で、前の（重み付けされた）粒子セットから抽出されます。従来のMCLで行われる再サンプリングの代わりに、KLDサンプリングアルゴリズムは、前の重み付けされた粒子セットから粒子を抽出し、モーションとセンサーの更新を適用してから、粒子をビンに配置します。このアルゴリズムは、空でないビンの数を追跡します。粒子が以前に空だったビンに挿入された場合、の値が再計算され、ほぼ線形に増加します。これは、サンプルサイズがと同じになるまで繰り返されます。^{[ 4 ]}${\displaystyle k}$ ${\displaystyle M_{x}}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle M_{x}}$

KLDサンプリングは、新しい場所（ビン）が埋まった場合にのみ粒子数を増やすことで、粒子集合から冗長な粒子を除去できることは容易に理解できます。実際には、KLDサンプリングは従来のMCLよりも一貫して優れた性能を示し、収束も速くなります。^{[ 4 ]}${\displaystyle M_{x}}$

参考文献

1. Ioannis M. Rekleitis. 「移動ロボットの位置特定のための粒子フィルタチュートリアル」マギル大学インテリジェントマシンセンター、技術報告書 TR-CIM-04-02 (2004)。
2. Frank Dellaert、Dieter Fox、Wolfram Burgard、Sebastian Thrun。「移動ロボットのモンテカルロ法による位置推定」（Wayback Machineに2007年9月17日アーカイブ） IEEE国際ロボティクス・オートメーション会議論文集第2巻。IEEE、1999年。
3. Dieter Fox、Wolfram Burgard、Frank Dellaert、Sebastian Thrun、「モンテカルロ法によるローカリゼーション：移動ロボットの効率的な位置推定」第16回人工知能全国会議議事録、 John Wiley & Sons Ltd、1999年。
4. セバスチャン・スラン、ウォルフラム・バーガード、ディーター・フォックス著。確率論的ロボティクスMITプレス、2005年、第8.3章ISBN 9780262201629。
5. Sebastian Thrun、Dieter Fox、Wolfram Burgard、Frank Dellaert。「移動ロボットのための堅牢なモンテカルロ法による位置推定」人工知能128.1（2001）：99–141。
6. Dieter Fox. 「 KLD–Sampling: Adaptive Particle Filters」ワシントン大学コンピュータサイエンス工学部. NIPS, 2001.