占有格子地図(Occupancy Grid Mapping)
**占有格子(occupancy grid)**は空間をセル(2Dの正方形または3Dのボクセル)に離散化し、各セル について障害物によって占有されている確率 を保持する。SLAMから得られる既知のロボット姿勢と、測距センサ(LiDAR、ソナー、深度カメラ)による計測が与えられると、占有格子マッピングは各セルに対する多数のノイズを含む観測を統合し、安定した自由/占有/未知の分類を得る——これはパスプランナーが実際に利用する地図形式である。
セルごとの二値ベイズフィルタ
主なモデリング上の仮定は次のとおりである。各セルは二値かつ静的な確率変数である(占有か自由かのいずれかで、時間経過で変化しない)。そしてセル同士は互いに独立である。この仮定のもとでは、地図全体の事後分布はセルごとの事後分布に因数分解され、それぞれが計測 が到着するたびに二値ベイズフィルタで更新される。
確率を直接扱うと、更新ごとに再正規化が必要になる。標準的なトリックは**対数オッズ(log-odds)**表現である。
対数オッズは を に写す。 は未知()を意味し、正の値は占有の可能性が高いことを、負の値は自由である可能性が高いことを意味する。対数オッズの形式では、ベイズ更新は単純な加算になる。
ここで、
- — 計測 を取り込んだ後のセルの対数オッズ、
- — 逆センサモデル:現在の計測だけから示唆される占有確率、
- — 事前対数オッズ(情報を持たない事前分布 の場合はゼロ)。
再正規化も積も不要で、各観測は単に定数の増分を加算するだけである。これが占有マッピングが組み込みロボット上でも十分安価に実行できる理由である。
逆センサモデルとレイキャスティング
測距センサの場合、各ビームは測定されたレイをグリッド上でレイキャスティングすることによって処理される(例:ブレゼンハムのライントラバーサル)。
- ヒットの手前でビームが通過したセルは、ビームによって透視されたことになるため、ミス更新——負の増分 (例:逆モデルの確率がおよそ )——を受ける。
- 測定された距離にあるセルはビームを反射した:正のヒット増分 (例:確率がおよそ )。
- ヒットより遠いセルは遮蔽されている——情報がないため更新もない。
一致する観測が繰り返されると累積するため、20回のミスと1回の偽ヒットに触れられたセルは、依然として明確に自由と読み取れる。移動する人物は一時的な筋を残すが、その後のミスによって消去される。実装は通常、対数オッズを最小/最大範囲にクランプしてセルを更新可能な状態に保ち(この有界信頼度クランピングはOctoMapが行っている手法である)、計画のためにセルを分類する際には をしきい値処理する(例:で)。
2Dグリッド、オクトリー、ボクセル
平坦な2Dグリッドは屋内移動ロボットの古典的な表現である(ROSのnav_msgs/OccupancyGrid)。3Dでは、密なグリッドは のメモリを消費するため、実用的なシステムでは階層的またはスパースな構造が使われる。OctoMapは、幾何が存在する場所だけを細分化し、均一な領域を刈り込むことができるオクトリーに確率的占有情報を格納する。一方、ハッシュベースのボクセルマップは階層構造を犠牲にしてO(1)アクセスを実現する。セルごとの対数オッズの計算はいずれも同一である。
SLAMにおける意義
SLAMは軌跡とランドマーク/点の地図を与えてくれるが、スパースな点群は「この空間は走行しても安全か」という問いには答えられない。なぜなら自由空間について何も語っていないからである。占有格子は自由・占有・未知の各体積を明示的に表現し、それが衝突判定、フロンティアベースの探索、パスプランニングに必要となるものである。実際には、SLAMシステムが姿勢を供給し、占有マッパーが姿勢付きのスキャンをナビゲーションスタックが動作するコストマップへと変換する。対数オッズフィルタはまた、生の幾何地図には欠けている動的物体やセンサノイズへの自然なロバスト性も提供する。