Grid Maps

• Geometric model of the environment.
• The 2D world plane is divided into grid cells.
• Map cells can be free or occupied.
• The robot can only navigate in the free cells.
• It is a dense representation of the world. I Suitable for indoor environments.

Occupancy Grid Maps

Binary cells

either free or occupied

Probabilistic cells

The cell occupancy is modelled by a binary random variable.
Map occupancy probabilities:

• Free cell: $p(mi)=0$
• Occupied cell: $p(mi)=1$
• No knowledge: $p(mi)=0.5$

Assumptions:

• Cells are independent of each other.
• Range measurement $z_t$ only depends on current robot pose $x_t$ (Markov property)

Algorithm

Possible states

• p_occupied
• p_prior (unchanged)
• p_free

Inverse Sensor Model