Probabilistic Robotics - Chap.9 Occupancy Grid Mapping

9.1 Introduction

　今まではロボットが動作を開始する前に、環境地図が既知であることを仮定していた。ただこれは現実世界では稀なケースである。そこでロボットが自律的に環境地図を知る必要がある。ただし、環境地図の獲得には、下記２つの理由から困難な課題の１つである。

地図の候補空間は巨大である
地図を得ることは"鶏と卵"の問題がある

困難度合いを決める要因には、下記４つがある。

地図のサイズ（地図を作る上で対象となる空間の大きさ）
認識・動作におけるノイズの程度
認識の曖昧さ（特徴量が少ない、似たような光景が広がっているなど）
周回路（ループクロージャの問題）

　本章では、ロボットの姿勢は既知と仮定（ ${mappig \ with \ known \ pose}$ 問題）。Grid Mappingは、ロボットの姿勢が既知という仮定の元、ノイズを含む不確かなセンサデータから環境地図を生成する技術である。地図中の各Gridは、 ${occupied}$ か ${free}$ のどちらかの値を取る。どちらの値を取るかは、近似的に実装する事後確率で表現する。
Occupancy Grid Mapは、SLAMやパスプランニングに使うことは少ない。

9.2 The Occupancy Grid Mapping Algorithm

環境地図に関する事後確率は
${ p(m | z_{1:t}, x_{1:t}) \tag{9.1} }$
で表される。ここで ${x_{1:t}}$ は、計測開始後から現在までのロボットの経路（各時刻でのロボットの姿勢）を、 ${z_{1:t}}$ は計測開始後から現在までのセンサデータを、それぞれ表す。
なおOccupancy Grid Mapは一般的に２次元の地図を表すが、何層にも重ねることで３次元の地図を形成することもできる。ただし計算コストが膨大なため、通常Occupancy Grid Mapで３次元地図は構成しない。

環境地図 ${m}$ は、沢山のセルで構成されることから、
${ m \ = \ \{m_i\} }$
とできる。このとき ${m_i \in \{0, \ 1\}}$ 、 ${p(m_i \ = \ 1) \ = \ p(m_i)}$ とする。

式(9.1)の問題は、次元数である。もしも地図が10,000個のセルで構成される場合、地図の次元は ${2^{10000}}$ となる。そのため、地図がセルの集合体だと考えると、計算量が膨大となる。

そこで標準的なOccupancy Grid Mapは、各セルに注目して事後確率を計算する。つまり ${p(m_i | z_{1:t}, x_{1:t})}$ を計算し、
${ \displaystyle p(m | z_{1:t}, x_{1:t}) = \prod_i p(m_i | z_{1:t}, x_{1:t}) }$
のように統合することで、環境地図の事後確率を求める。

Occupancy Grid Mappingでは、各グリッドの状態を表すのに下記式(9.5)で表される対数オッズを使う。
${ \displaystyle l_{t, i} \ = \ log \frac{p(m_i | z_{1:t}, x_{1:t})}{1 \ - \ p(m_i | z_{1:t}, x_{1:t})} \tag{9.5} }$
対数オッズを使うメリットは、事後確率が計算結果が不安定になる０、１の近傍を取らなくなることである。

${ 1: \ Algorithm \ occupancy\_grid\_mapping(\{l_{t-1, i}\}, x_t, z_t): \\ 2: \ \quad for\ all \ cells \ m_i \ do \\ 3: \ \qquad if \ \ m_i \ \ in \ perceptual \ field \ of \ z_t \ then \\ 4: \ \qquad \quad l_{t, i} = l_{t-1, i} + inverse\_sensor\_model(m_i, x_t, z_t) - l_0 \\ 5: \ \qquad else \\ 6: \ \qquad \quad l_{t,i} = l_{t-1, i}\\ 7: \ \qquad endif \\ 8: \ \quad endfor \\ 9: \ \quad return \{l_{t,i}\} }$

なお式中の ${l_0}$ は、対数オッズで表現されるOccupancy Grid Mapの事前分布で、
${ \displaystyle l_0 = log \frac{p(m_i \ = \ 1)}{p(m_i \ = \ 0)} \ = \ log \frac{p(m_i)}{1 \ - \ p(m_i)} }$
とする。ここで、 ${p(m_i) \ = \ p(m_i \ = \ 1)}$ であり、
${ \displaystyle inverse\_sensor\_model(m_i, x_t, z_t) \ = \ log \frac{p(m_i | z_t, x_t)}{1 - p(m_i | z_t, x_t)} }$
である。

なお、Occupancy Grid Mapを作成する時は、ロボット自身が専有する領域（ロボットの身体）を考慮することは大切である。特に通行人が多いとき等には有用である。

9.3 Learning Inverse Measurement Models

9.3.1 Inverting the Measurement Model

Occupancy Grid Mapは、各セルの逆観測モデル ${p(m_i | x, z)}$ が必要である。
Table9.2ではとりあえずの逆観測モデルを定義した。
ここでいう逆観測モデルは、複数のマップを用意し、それぞれのマップの ${m^k_i \ = \ m_i}$ を満たすマップを使って逆観測モデルを近似する。つまり、
${ \displaystyle p(m_i | x, z) \ = \ \eta \sum_{m:m(i)=m_i} p(z | x, m) p(m) }$
となる。上記の式は計算不可能のため、ロジスティクス回帰やニューラルネットワーク等の教師付き学習アルゴリズムを使って近似的に求める。