1.地图分类

环境地图是机器人进行定位（特征地图）和规划（栅格地图）的前提

• 尺度地图
• 拓扑地图
• 语义地图

2.覆盖栅格建图算法

• 把环境分解成一个一个的小栅格
• 每个栅格有两种状态：占用（Occupied）或者空闲（free）
• 非参模型
• 随着地图的增大，内存需求急剧增加
• 天然区分可通行区域，适合进行轨迹规划

1.数学描述

给定机器人的位姿和传感器的观测数据（主要是激光雷达）
$$data=x_1,z_1,x_2,z_2,\cdots ,x_n,z_n\text{\hspace{1em}(2-1)}$$
估计出最可能的地图
$$m^{\ast }=argma{x}_{m}P(m|data)\Rightarrow m^{\ast }=argma{x}_{m}P(m|x_{1:t},z_{1:t})\text{\hspace{1em}(2-2)}$$

1.假设

• 栅格地图中的栅格是一个二元随机变量，只能取两个值：占用或者空闲
• p(m_i)=1表示被占用，p(m_i)=0表示空闲，p(m_i)=0.5表示不知道
• 在建图的过程中，环境不会发生改变
• 地图中每一帧栅格都是独立的，因此数学表达式可以表示为

$$P(m)=\prod p(m_i)\text{\hspace{1em}(2-3)}$$

• 地图估计问题表示为：

$$P(m|x_{1:t},z_{1:t})=\prod p(m_i|x_{1:t},z_{1:t})\text{\hspace{1em}(2-4)}$$

• 因此，估计环境的地图只需对每个独立的栅格进行估计即可

2.地图估计

m_i是一个二元随机变量因此：
$$\begin{gathered} P(m_i|x_{1:t},z_{1:t})=\frac{P(z_t|m_i,x_{1:t},z_{1:t-1})P(m_i|x_{1:t},z_{1:t-1})}{P(z_t|x_{1:t},z_{1:t-1})} \\ =\frac{P(z_t|m_i,x_t)P(m_i|x_{1:t-1},z_{1:t-1})}{P(z_t|x_{1:t},z_{1:t-1})}\text{\hspace{1em}(2-5)} \end{gathered}$$
其中：
$$P(z_t|m_i,x_t)=\frac{P(m_i|x_t,z_t)P(z_t|x_t)}{P(m_i|x_t)}\text{\hspace{1em}(2-5)}$$

$$\begin{gathered} P(m_i|x_{1:t},z_{1:t})=\frac{P(m_i|x_t,z_t)P(z_t|x_t)}{P(m_i|x_t)}\frac{P(m_i|x_{1:t-1},z_{1:t-1})}{P(z_t|x_{1:t},z_{1:t-1})} \\ =\frac{P(m_i|x_t,z_t)P(z_t|x_t)}{P(m_i)}\frac{P(m_i|x_{1:t-1},z_{1:t-1})}{P(z_t|x_{1:t},z_{1:t-1})}\text{\hspace{1em}(2-7)} \end{gathered}$$

m_i是个二元随机变量：
$$P(┐m_i|x_{1:t},z_{1:t})==\frac{P(┐m_i|x_t,z_t)P(z_t|x_t)}{P(┐m_i)}\frac{P(┐m_i|x_{1:t-1},z_{1:t-1})}{P(z_t|x_{1:t},z_{1:t-1})}\text{\hspace{1em}(2-8)}$$
式（2-7）和式（2-8）相比：
$$\begin{gathered} \frac{P(m_i|x_{1:t},z_{1:t})}{P(┐m_i|x_{1:t},z_{1:t})}=\frac{P(m_i|x_t,z_t)}{P(m_i)}\frac{P(m_i|x_{1:t-1},z_{1:t-1})P(┐m_i)}{P(┐m_i|x_t,z_t)P(┐m_i|x_{1:t-1},z_{1:t-1})} \\ =\frac{P(m_i|x_t,z_t)}{P(┐m_i|x_t,z_t)}\frac{P(m_i|x_{1:t-1},z_{1:t-1})}{P(┐m_i|x_{1:t-1},z_{1:t-1})}\frac{P(┐m_i)}{P(m_i)}\text{\hspace{1em}(2-9)} \end{gathered}$$

$$\frac{P(m_i|x_{1:t},z_{1:t})}{P(┐m_i|x_{1:t},z_{1:t})}=\frac{P(m_i|x_t,z_t)}{1-P(m_i|x_t,z_t)}\frac{P(m_i|x_{1:t-1},z_{1:t-1})}{1-P(m_i|x_{1:t-1},z_{1:t-1})}\frac{1-P(m_i)}{P(m_i)}\text{\hspace{1em}(2-10)}$$

对于P(X),定义对应的Log-Odd项：
$$l(x)=\frac{p(x)}{1-p(x)}\text{\hspace{1em}(2-11)}$$
则：
$$P(x)=1-\frac{1}{1+exp(l(x))}\text{\hspace{1em}(2-12)}$$
则式（2-10）则变成：
$$l(m_i|x_{1:t},z_{1:t})=l(m_i|x_t,z_t)+l(m_i|x_{1:t-1},z_{1:t-1})-l(m_i)\text{\hspace{1em}(2-13)}$$

• $l(m_i|x_t,z_t)$表示激光雷达的逆观测模型
• $l(m_i|x_{1:t-1},z_{1:t-1})$表示栅格m_i在t-1时刻的状态
• $l(m_i)$表示栅格m_i的先验值，该值对所有栅格都相同

3.算法流程

• 算法对某个栅格进行操作的时候，只有加法操作，因此具有非常高的更新速度。
• 更新时需要知道传感器逆测量模型。

[

4.激光雷达的逆观测模型