モンテカルロローカリゼーション

モンテカルロ位置推定（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 sensors_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}}$

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

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

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

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

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

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

粒子フィルタの時間計算量は粒子の数に対して線形です。当然、粒子の数が多いほど精度は向上するため、速度と精度の間には妥協点があり、の最適値を見つけることが望まれます。選択する戦略の 1 つは、次のコマンドとセンサー読み取りのペアが到着するまで、継続的に追加の粒子を生成することです。^[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）を用いた誤差推定に基づいて適応的に粒子をサンプリングすることで改善される可能性がある。最初は、マップ全体を粒子の均一なランダム分布でカバーする必要があるため、大きなサイズを使用する必要がある。しかし、粒子が同じ場所に収束すると、このような大きなサンプルサイズを維持することは計算上無駄になる。^[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}}$