Besides state estimation or localization, which provide a robot with knowledge of where it is, it’s equally important for a mobile robot to perceive its surrounding and form a knowledge of where is occupied, that’s where mapping comes in. This note covers a fundamental mapping algorithm, occupancy grid mapping.

Problem Statement

In occupancy grid mapping, a map $\mathbf{m}=\left\{m_i\right\}_{i=1}^N$ is discretized into $N$ different cells, where each cell $m_i$ is a binary random variable that models the occupancy, and $p(m_i)$ is the probability of a cell being occupied. The map is assumed to be static. The goal is to find the belief $\mathrm{bel}_t(\mathbf{m})=p(\mathbf{m}\mid \mathbf{z}_{1:t}, \mathbf{x}_{1:t})$, where $\mathbf{z}$ is the observation and $\mathbf{x}$ is the state of the robot.

Two assumptions are made for tractability

• The robot state $\mathbf{x}_t$ are known.

• The occupancy of individual cells $m_i$ are independent, and thus

At each timestep $t$, the sensor performs some measurement and provide the information of whether a cell $m_i$ is believed to be occupied or not, in terms of $p(m_i\mid\mathbf{z}_t, \mathbf{x}_t)$, which is known as the inverse sensor model.

One simple inverse sensor model is shown in the figure above. Consider a laser beam range sensor that provides the reading $\mathbf{z}=(z_1^r,\dots, z_n^r,z_{1}^{\phi},\dots,z_{n}^{\phi})$, where $z_k^r$ and $z_k^\phi$ are the range and bearing of the $k$-th beam. For grid $i$, let $r_i$ and $\phi_i$ be the range and bearing of the grid as observed from the current robot pose $\mathbf{x}$, and $k=\argmin_j\left|\phi_i-z_j^{\phi}\right|$ be the beam going through that gird. Based on the relation of a grid’s position relative to the robot, we have three different cases:

• If $r_i>\min(z_{\max},z_k^r+w_{\mathrm{grid}})$ or $\left|\phi_i-z_{k}^{\phi}\right|>w_{\mathrm{beam}} / 2$, then return $p_{\mathrm{previous}}$, the sensor has no information about this grid.

• Else if $z_k^r < z_{\max}$ and $\left|r_i-z_k^r\right|<w_{\mathrm{grid}}$, then return $p_{\mathrm{occupied}}$, the sensor think the grid is occupied.

• Else if $z_k^r<z_{\max}$ and $r_i < z_k^r$, then return $p_{\mathrm{free}}$, the sensor think the grid is free.

where $z_{\max}$ is a sensor-specific parameter representing the maximum detectable range, $w_{\mathrm{grid}}$ is the grid size and $w_{\mathrm{beam}}$ is the width of each beam.

Mapping Algorithm

Following the Bayes filtering framework, a general algorithm can be derived for the occupancy grid mapping [2]. Starting from equation 1,

Further notice that the map $\mathbf{m}$ is independent of the robot state $\mathbf{x}_t$, we obtain

Similarly, for the negation

Compute the ratio of equation (2) and (3), we get

Then, change to log odds form by defining

and the product chain turns into a sum

Bayes Inference using Conjugate Prior

The previous section derived an equation for updating the belief of the map under the Bayes framework, however, it lacks the notion of uncertainty (i.e., how confident we are about the map). With the notion of conjugate prior, a proper selection of the underlying distribution function for $p(m_i)$ can both simplifies the updating rule and provide a closed form formula for uncertainty.

Recall that from Bayes rule

Bernoulli Likelihood and Beta Prior

First consider the case where the occupancy of a grid is binary, i.e., $m_i\in\{0, 1\}$. Let $\theta_i\triangleq p(m_i=1)$ be the unknown occupancy probability. From the inverse sensor model described above, we know that each sensor measurement provide a binary result, denoted as $y_t$, where

Then, the likelihood is modeled as a Bernoulli with parameter $\theta_i$, i.e.,

Furthermore, if we model the prior as a Beta distribution, i.e.,

where $B(\cdot, \cdot)$ is the beta function.

Then, it follows from the Bayes rule that the posterior is

which still follows a Beta distribution, $p(\theta_i\mid \mathbf{z}_{1:t},\mathbf{x}_{1:t})=\mathrm{Beta}(\theta_i;\alpha_t, \beta_t)$, where

In this case, we call beta distribution the conjugate prior for the Bernoulli likelihood.

• Conjugate Distribution and Conjugate Prior [2]

  • If the posterior distributions are in the same probability distribution family as the prior probability distribution, the prior and posterior are then called conjugate distributions.

  • The prior is called a conjugate prior for the likelihood function.

Note that the choice of modeling the prior as a Beta distribution here is an algebraic convenience, which provides a closed-form expression for the posterior. Then the mean and covariance can be easily obtained

Given the simple update rule in Equation (4), the recursive Bayes framework becomes a simple counting problem: when the sensor model returns “occupied”, increment $\alpha_i$ by 1, if the sensor model returns “free”, increment $\beta_i$ by 1.

Categorical Likelihood and Dirichlet Prior

Next, we can generalize the above binary occupancy mapping into a multi-categorical case using the categorical likelihood and the Dirichlet prior.

Suppose we have $K$ different categories and each grid can be belongs to exactly one category or empty, i.e., $m_i\in\{0,1,\dots, K\}$. Let $\boldsymbol{\theta}_i=\left(\theta_{i,0},\dots, \theta_{i, K}\right)$ be a vector where $\theta_{i,k}\triangleq p(m_i=k)$, and $\sum_{k=0}^{K}\theta_{i,k}=1$. Further let the measurement be a one-hot-encoded tuple $\mathbf{y}_t=(y_{t,0},y_{t, 1}, \dots, y_{t,K})$ with $y_{t,k}\in\{0, 1\}$ and $\sum_{k=0}^{K}y_{t,k}=1$, indicating which category the sensor believes cell $i$ belongs to.

Similarly, the likelihood can be modeled as a categorical distribution

Then, we apply a Dirichlet distribution with parameter $\boldsymbol{\alpha}_{i,t-1}=(\alpha_{i,t-1,0}, \dots, \alpha_{i,t-1,K})$ on the prior

The posterior then follows another Dirichlet distribution with parameter $\boldsymbol{\alpha}_{i,t}$,

Thus, the update rule is

which is simply adding 1 to the $\alpha$ of the category to which the sensor believes the cell belongs.

For the multi-categorical case, the mean and covariance can also be computed in closed-form:

Counting Sensor Models

Finally, we can write out the mapping algorithm for multi-category discrete counting sensor model

Note that if $K=1$, the above algorithm reduces to the binary occupancy grid mapping.

One more generalization can be made to the above discrete CSM, which is to take into account the spatial continuity. In the $\texttt{multi\_category\_discrete\_CSM}$ algorithm listed above, an observation falling into a cell grid $i$ only updates $\boldsymbol{\alpha}_i$ of that cell and not any other cell. In reality, if a cell is observed to be occupied by a wall, then its nearby cells may also be occupied by that wall.

Let $\mathcal{X}\subset\mathbb{R}^d$ be the spatial support of the map (e.g., $d=2$ or $d=3$). Define a kernel function $k(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\to[0,1]$ that operates on the spatial inputs. The kernel function determines how much an observation at a location influences our belief about location $\mathbf{x}^{*}$.

Specifically, the inverse sensor model is corrected as follows. For beam $k$, we construct a set of sample points $\mathcal{S}=\left\{\mathbf{x}_{\mathrm{obs}},\mathbf{x}_{\mathrm{ray}}^{(1)}, \mathbf{x}_{\mathrm{ray}}^{(2)}, \dots\right\}$ where

• $\mathbf{x}_{\mathrm{obs}}\in\mathbb{R}^d$ is the global coordinate of the beam’s endpoint. All grids close to this endpoint is considered as occupied (or fall into some category), by a kernel-weighted factor.

• $\mathbf{x}_{\mathrm{ray}}^{(l)}\in\mathbb{R}^{d}$ is the global coordinate of other sample points on the beam. All grids close to any of these sample points are considered as free, by a kernel-weighted factor.

Then, during the map construction, we update the Dirichlet parameter for grid $i$ with

Another benefit of continuous CSM is that we can query any point $\mathbf{x}^*$ in the spatial support after the map is built, with

where $\alpha_{k,0}$ is the initial prior.

Reference

[1]. https://www.mathworks.com/help/nav/ref/occupancymap.insertray.html

[2]. M. Ghaffari, ROB530 Lecture Slides — Robotic Mapping. University of Michigan, 2026.