Occupancy Grid Mapping

Introduction

Ray casting for $\hat z$

For an occupancy grid with cell size

c

Transform the beam direction: $\theta_k = \theta_t + \phi_k$ .
Step along the ray with DDA or Bresenham’s algorithm until:
- The ray reaches an occupied cell (the endpoint).
- The distance exceeds $z_{\max}$ .

Return the Euclidean distance from the sensor origin.

Pseudocode

function ray_cast(grid, pose, angle, z_max):
    x, y, θ = pose
    θb = θ + angle
    (cx, cy) = metric_to_cell(x, y)
    init step increments (sx, sy) via DDA
    while dist < z_max:
        if grid[cx, cy] occupied: return dist_to_cell_boundary(...)
        advance to next cell (cx += sx or cy += sy)
    return z_max

The inverse sensor model

To update a cell’s occupancy, we need

p(m_i \mid z_t, \mathbf x_t)

. The simplified inverse beam model applies these updates:

For cells before the measured endpoint, increase the probability that they are free.
For the cell at the endpoint, increase the probability that it is occupied if $z < z_{\max}$ .
Do not update cells beyond the endpoint.

In log-odds form, the update is:

L_t(i) = L_{t-1}(i) + \ell_i - L_0,

where

\ell_i = \log \frac{p(m_i=1 \mid z_t, \mathbf x_t)}{1 - p(m_i=1 \mid z_t, \mathbf x_t)}, \quad L_0 = \log \frac{p(m_i=1)}{1 - p(m_i=1)}.

Recover the probability with:

p(m_i=1) = \frac{1}{1 + e^{-L_t(i)}}.

Approximate inversion

Exact inversion requires:

p(m_i \mid z_t, \mathbf x_t) \propto p(z_t \mid m_i, \mathbf x_t) p(m_i),

but coupling among cells makes the calculation intractable. The beam-based inverse model is a heuristic that is consistent with the forward geometry. —>

Occupancy updates with multiple beams

For each beam:

Use ray tracing to find the traversed cells.
Update the free cells: $L \mathrel{+}= \ell_{\text{free}}$ .
If the beam hits an endpoint, update that cell: $L \mathrel{+}= \ell_{\text{occ}}$ .

Clip the log-odds values to avoid saturation. Key references: (Qi et al., 2016)

References

Qi, C., Su, H., Mo, K., Guibas, L. (2016). PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. arXiv [cs.CV].

Edit this page on GitHub or file an issue.

State Estimation & Mapping

State Estimation

SLAM

Occupancy Grid Mapping

Introduction

Ray casting for $\hat z$

Pseudocode

The inverse sensor model

Approximate inversion

Occupancy updates with multiple beams

References

​Introduction

​Ray casting for z^\hat zz^

​Pseudocode

​The inverse sensor model

​Approximate inversion

​Occupancy updates with multiple beams

​References

Introduction

Ray casting for $\hat z$

Pseudocode

The inverse sensor model

Approximate inversion

Occupancy updates with multiple beams

References