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}\mathrm{\_}\mathrm{sensor}\mathrm{\_}\mathrm{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