Skip to main content

​
Introduction

​
Ray Casting to Compute z^\hat z

For occupancy grid with cell size cc:
  1. Transform beam direction: θk=θt+ϕk\theta_k = \theta_t + \phi_k.
  2. Step along ray using DDA / Bresenham until:
    • Occupied cell encountered (endpoint).
    • Distance exceeds zmax⁡z_{\max}.
Return Euclidean distance from 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

​
Inverse Sensor Model for Occupancy Grids

We need p(mi∣zt,xt)p(m_i \mid z_t, \mathbf x_t) to update cell occupancy. Simplified inverse beam model:
  • Cells before measured endpoint along beam: increase probability free.
  • Cell at endpoint (if z<zmax⁡z < z_{\max}): increase probability occupied.
  • Beyond endpoint: no update.
Log-odds representation: Lt(i)=Lt−1(i)+ℓi−L0,L_t(i) = L_{t-1}(i) + \ell_i - L_0, where ℓi=log⁡p(mi=1∣zt,xt)1−p(mi=1∣zt,xt),L0=log⁡p(mi=1)1−p(mi=1).\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 probability: p(mi=1)=11+e−Lt(i).p(m_i=1) = \frac{1}{1 + e^{-L_t(i)}}.

​
From Forward to Inverse (Approximation)

Exact inversion requires: p(mi∣zt,xt)∝p(zt∣mi,xt)p(mi),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 leads to intractability. Beam-based inverse model is a heuristic consistent with forward geometry. —>

​
Occupancy Update with Multiple Beams

For each beam:
  1. Ray trace list of traversed cells.
  2. Update free: L+=ℓfreeL \mathrel{+}= \ell_{\text{free}}.
  3. Endpoint (if hit): L+=ℓoccL \mathrel{+}= \ell_{\text{occ}}.
Clip log-odds to avoid saturation.
Edit this page on GitHub or file an issue.
Connect these docs to Claude, VSCode, and more via MCP for real-time answers.