Lab03 - Map Building

Occupancy grid maps represent an example of environment representation in probabilistic robotics which address the problem of generating maps from noisy and uncertain sensor measurement data, with the assumption that the robot pose is known. ¹⁾ The goal of the occupancy mapping is to estimate the posterior probability over maps given the data: $p( m \vert z_{1:t} , x_{1:t} )$ where $m$ is the map, $z_{1:t}$ is the set of measurements from time $1$ to $t$, and $x_{1:t}$ is the set of robot poses from time $1$ to $t$. Typically, the problem decomposes to estimation of $p( m_i \vert z_{1:t} , x_{1:t} )$, where $m_i$ is a single cell of the occupancy grid map.

In general, the grid maps divide the action space of the robot into discrete cells which carry the information about the occupancy of the designated area (occupied, free, unknown). The cell dimensions are user defined and usually is a balance between the environment size, that influence the overall memory consumption, and geometrical precision, that should be proportional to the robot dimensions. The data from the sensors are fused to the occupancy grid using either Bayesian or Non-bayesian way.

The Bayesian occupancy grid update is defined as: $$ P(m_i = occupied \vert z) = \dfrac{p(z \vert m_i = occupied)P(m_i = occupied)}{p(z \vert m_i = occupied)P(m_i = occupied) + p(z \vert m_i = free)P(m_i = free)}, $$ where $P(m_i = occupied \vert z)$ is the probability of cell $m_i$ being occupied after the fusion of the sensory data; $P(m_i = occupied)$ is the previous probability of the cell being occupied and $p(z \vert m_i = occupied)$ is the model of the sensor which is usually modeled as: $$ p(z \vert m_i = occupied) = \dfrac{1 + S^z_{occupied} - S^z_{free}}{2}, $$ $$ p(z \vert m_i = free) = 1 - p(z \vert m_i = occupied), $$ where $S^z_{occupied}$ and $S^z_{free}$ are the sensory models for the occupied and free space respectively.

For the LIDAR sensor, the simplified sensory model yields: $$ S^z_{occupied} = \begin{cases} 1 \qquad\text{for}\qquad d \in [r-\epsilon, r+\epsilon]\\ 0 \qquad\text{otherwise} \end{cases}, \qquad\qquad S^z_{free} = \begin{cases} 1 \qquad\text{for}\qquad d \in [0,r-\epsilon)\\ 0 \qquad\text{otherwise} \end{cases}, $$ where $r$ is the distance of the measured point and $\epsilon$ is the precision of the sensor. I.e. it is assumed that the space between the sensor and the measured point is free and the close vicinity of the measured point given by the sensor precision is occupied.

An example of the occupancy grid mapping: https://www.youtube.com/watch?v=zjl7NmutMIc