Robot Mapping

用 Occupancy grid mapping 算法构建地图，就是计算下面概率：
\[p(m \mid z_{1:t}, x_{1:t})\]

其中， \(m\) 是地图， \(z_{1:t}\) 是测量值， \(x_{1:t}\) 是机器人的路径，即一系列位置。由于假设机器人的位置是已知的，所以控制量 \(u_{1:t}\) 就没必要作为已知条件了。

Occupancy grid mapping 算法把地图分解为有限的很多网格单元(grid cells)，即：
\[m = \sum_i m_i\]

每一个网格单元看作是一个二值（即“已被占据”或“未被占据”）的随机变量，用 \(p(m_i = 1)\) 或者 \(p(m_i)\) 来表示网格单元被物体占据的概率。

要直接计算 \(p(m \mid z_{1:t}, x_{1:t})\) 基本上是不可行的，因为它的维度太大，假设有 10000 个网格单元，则可能的地图有 \(2^{10000}\) 个。Occupancy grid mapping 的作法是把各个网格单元看作是相互独立的（各个网格单元相互独立的假设其实并不成立，这是为了简化计算而做的妥协），这样概率 \(p(m \mid z_{1:t}, x_{1:t})\) 可分解为：
\[p(m \mid z_{1:t}, x_{1:t}) = \prod_i p(m_i \mid z_{1:t}, x_{1:t})\]

这样，我们可以用“Binary Bayes Filter”对每个网格单元是否被占据进行概率估计了。

对每个网格单元应用“Binary Bayes Filter”算法可得 Occupancy grid mapping 算法，如图 1 所示。

上面算法中 \(l_{t,i} = \log \frac{p(m_i \mid z_{1:t}, x_{1:t})}{1 - p(m_i \mid z_{1:t}, x_{1:t})}\) ， \(l_0 = \log \frac{p(m_i = 1)}{p(m_i = 0)} \ = \log \frac{p(m_i)}{1 - p(m_i)}\) ， \(\mathrm{inverse\_sensor\_model}(m_i, x_t, z_t) = \log \frac{p(m_i \mid z_t, x_t)}{1 - p(m_i \mid z_t, x_t)}\)

说明：Occupancy Grid Mapping 有两个假设：(1) 机器人位置已知；(2) 网格单元是否被占据是相互独立的。

参考：
Probabilistic Robotics, by Sebastian Thrun, 9.2 The Occupancy Grid Mapping Algorithm
http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/12-occupancy-mapping.pdf

还有一种简单的办法来估计网格单元是否被物体占据：计数法(Simple Counting)。
基本思路是按下面方法分析传感器返回的数据：
For every cell count
hits(x,y): number of cases where a beam ended at <x,y>
misses(x,y): number of cases where a beam passed through <x,y>
\[Bel(m^{[xy]}) = \frac{\text{hits}(x,y)}{\text{hits}(x,y) + \text{misses}(x,y)}\]

参考：
http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/12-occupancy-mapping.pdf
http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/55IntelligentRobotics/110WorldMap.pdf