Localization

Localization is the process of finding out the pose of the robot. It's a robotic specific use case of state estimation because at the end of the day, we want to estimate the robot state $x_t$. The localization is a direct application of Bayes filter. We have seen different filters in previous chapters and each of them, equipped with appropriate motion models and measurement models, forms a localization algorithm. The relationship is given as the table below:

Filter Algorithm	Localization Algorithm
Kalman Filter	Markov Localization
Histogram Filter/Discrete Bayes Filter	Grid Localization
Particle Filter	Monte Carlo Localization

Markov Localization

TODO

Grid Localization

The grid localization is a direct application of the Discrete Bayes Filter.

The first step is to define the grid. One common approach is to divide the state space into small chunks. The figure below is a grid map of the world:

(source: Wiki: https://en.m.wikipedia.org/wiki/File:World_Map_1-2,500,000_grid.svg)

The grids above only concerns the $(x,y)$ coordinates and we need an additional dimension to take the robot orientation into account. The grid size can be uniform or variable depending on the need. Similar to the discussion in the Discrete Bayes Filter section, the finer the grid, the more accurate the estimation is.

The grid above is called the metric representation of the world. There is another type called topological grids. The idea is that only (important) features are on the grid map. One example is the subway map:

Stations are "feature" of the city and each station represents the surrounding area. We could immediately notice that the topological grid is a coarse representation of the real world. The emphasis is on features and other details are omitted.

The next step is to select the motion model and measurement model. The grid size has impact on the motion model and measurement model implementation. The problem is that most of the time, the center of the grid is used to represent the robot position. Image we apply some control $u_t$to the robot, if we don't pay enough attention in the implementation, what would happen is that the motion model would think that the control $u_t$is not large enough and the robot stays in the same grid. This is problematic because the robot moves in the real world but the model thinks the robot stays in the same grid (which essentially puts the robot back to the center to the grid) and get stuck in that state. One common solution to this problem is to increase the noise in the motion and measurement model so that it's more likely for the robot to move to a new grid estimated by the model.

Finally, apply the Discrete Bayes Filter algorithm and we obtain the grid localization algorithm as follows:

(source: Probabilistic Robotics)

Monte Carlo Localization

TODO