占有グリッドマッピング

占有グリッドマッピングとは、移動ロボットのための確率ロボティクスにおけるコンピュータアルゴリズムの一種であり、ロボットの姿勢が既知であるという仮定のもと、ノイズが多く不確実なセンサー測定データから地図を生成する問題に取り組みます。占有グリッドは、1985年にH. MoravecとA. Elfesによって初めて提案されました。^[1]

占有グリッドの基本的な考え方は、環境マップを、環境内のその場所における障害物の存在を表す2値ランダム変数の等間隔フィールドとして表現することです。占有グリッドアルゴリズムは、これらのランダム変数の近似事後推定値を計算し、環境マップを構築します。^[2]

アルゴリズムの概要

占有グリッドマッピングアプローチには、4つの主要な要素があります

• 解釈
• 統合
• 位置推定
• 探査^[3]

占有グリッドマッピングアルゴリズム

占有マッピングアルゴリズムの目的は、以下のデータが与えられた場合のマップ上の事後確率を推定することです。ここで、はマップ、は時刻1からtまでの計測値の集合、 は時刻1からtまでのロボットの姿勢の集合です。経路は既知であると仮定されるため、制御データとオドメトリデータは占有グリッドマッピングアルゴリズムでは考慮されません。 ${\displaystyle p(m\mid z_{1:t},x_{1:t})}$ ${\displaystyle m}$ ${\displaystyle z_{1:t}}$ ${\displaystyle x_{1:t}}$

占有グリッドアルゴリズムは、環境内の連続した位置空間を細分化したグリッドとして マップを表現します。最も一般的な占有グリッドマップは、3D世界の一部を描写する2Dマップです。${\displaystyle m}$

インデックスiのグリッドセルをとすると（2次元マップでは、2つのインデックスを用いて2つの次元を表すことが多い）、 という表記はセルiが占有されている確率を表します。事後確率を推定する際の計算上の問題は、問題の次元性です。マップに10,000個のグリッドセル（比較的小さなマップ）が含まれている場合、このグリッドで表現できるマップの数は です。したがって、そのようなマップすべてについて事後確率を計算することは不可能です。 ${\displaystyle m_{i}}$ ${\displaystyle p(m_{i})}$ ${\displaystyle p(m\mid z_{1:t},x_{1:t})}$ ${\displaystyle 2^{10,000}}$

標準的なアプローチは、問題をより小さな推定問題に分割することです。

${\displaystyle p(m_{i}\mid z_{1:t},x_{1:t})}$

すべてのグリッドセルについて。これらの推定問題はそれぞれ2値問題となる。この分割は便利だが、隣接セル間の依存関係をモデル化できないため、問題の構造の一部が失われる。代わりに、マップの事後分布は次のように因数分解することで近似される。 ${\displaystyle m_{i}}$

${\displaystyle p(m\mid z_{1:t},x_{1:t})=\prod _{i}p(m_{i}\mid z_{1:t},x_{1:t})}$ 。

この因数分解により、2値ベイズフィルタを使用して各グリッドセルの占有確率を推定できます。各グリッドセルが占有されている確率の 対数オッズ表現を使用するのが一般的です

参照

• ロボットマッピング

参考文献

1. H. Moravec; AE Elfes (1984). 「広角ソナーによる高解像度マップ」.議事録. 1985 IEEE 国際ロボティクス・オートメーション会議. シルバースプリング、ミズーリ州: IEEE コンピュータ協会出版. pp.  116– 121. doi :10.1109/ROBOT.1985.1087316. S2CID  41852334.
2. Thrun, S. ; Burgard, W. ; Fox, D. (2005). 確率論的ロボティクス. ケンブリッジ, マサチューセッツ州: MIT 出版. ISBN 0-262-20162-3 OL  3422030M
3. Thrun, S. & Bücken, A. (1996). 「移動ロボットナビゲーションのためのグリッドベースマップとトポロジカルマップの統合」(PDF) .第13回人工知能全国会議議事録: 944–950 . ISBN 0-262-51091-X。

外部リンク

• RI CMUにおけるロボット工学における統計的手法：16-831の講義ノート