Occupancy grids
Intorduction to occupancy grids
In this post we look into occupancy grid maps.
Simply put an occupancy grid is a discretized version of the environment surrounding the ego vehicle [3]. The discretization can be either two or three dimensional. The following images show versions of 2D and 3D grids.
Figure 1. 2D occupancy grid map.
Figure 2. 3D occupancy grid map.
Each cell in an occupancy grid indicates if the space represented by the cell is empty or occupied by an obstacle. Given this, the more dense the grid is the finer the representation of the environment will be. However, the more dense the grid is the more computationally expensive is to create it. Each cell in the grid is binary i.e. it has a value, $m_i$, of either one or zero [3].
Typically, in order to create an occupancy grid, we make the following assumptions [3]
- Static environment i.e. no dynamic objects
- Grid cells are independent
- The vehicle state is known
Given the gride cell value $mi_i$, we can construct a belief map meaning a map at time $t$ such that for each cell
$$bel_{t}(m_i) = P(m_i | (x,y))$$
where $(x,y)$ denotes the vehicle state and the sensor measurements for a given cell. We can establish a threshold at which a given belief can be classified as occupied. Furthermore, we can combine measurements from different time steps to obtain a more accurate belief. In particular, using Baye's theorem we can come up with the following equation [3]
$$bel_{t}(m_i) = \eta P(y_t | m_i)bel_{t-1}(m^i)$$
where $\eta$ is a scaling or normalization constant to ensure that the $bel$ function represents a probability.
In occupancy grid mapping every grid cell is one of two states; occupied or empty [2]. But in some situations it makes sense for a cell to be partially filled. This may occur when only part of the grid cell is filled and the rest is empty, or when the objects that occupies the grid cell have special characteristics [2]. For example it may be that we want a grid cell occupied with vegetation to be somehow less occupied than a grid cell filled with solid rock.
Semi-transparent obstacles and Mitigation Classical occupancy grids have trouble dealing with semi-transparent obstacles such as glass and vegetation. These obstacles may return hits to the laser rangefinder about half of the time, but eventually the occupancy grid will converge to either occupied or not, both of which are incorrect. [2]
A possible solution to this problem would be to consider a more continous measure that measures the density or probability of a beam to have reflected and not passed. Perhaps the simplest approach towards this is to treat the random variable as a biased coin and for each state keep a count of the number of hits and pass throughs [2]. Thus, the only difference is that each state tracks two numbers. Then, the probability can be calculated empirically as the ratio of the hits to the sum of hits and passes. For the inverse sensor model, we either spread the high probability zone or use fractional number of hits and misses for each state [2].
- Bruno Siciliano, Lorenzo Sciavicco, Luigi Villani, Giuseppe Oriolo,
Robotics Modelling, Planning and Control, Springer - Drew Bagnell
Statistical Techniques in Robotics, Lecture notes. - Motion planning for self-driving cars