Chapter 1 Introduction
3.3 Laser-based Localisation
3.3.3 Map-based localisation
Figure 3.25: Common direction in the histogram matching
In polygonal environments the histogram and its cross-correlation can be used to nd the translational shift too. After the correct rotations between the scans have been found, the current scan can be rotated to the same heading as the reference scan.
The histograms for x- and y-translation are calculated with respect to common directions. The common direction is illustrated in Figure 3.25 and can be found by searching for the maximum of the histogram . The common direction is such that it aligns the scan so that a maximum number of scan points represents a single x (or y) value.
The work of Censi et al.  falls into the same category, but instead of using histogram transformation they use Hough transformation. Hough transformation also provides invariance to the translation, and the orientation can be found in a similar way to the histogram case, which can be used to search for translations.
Both methods are dense methods in the sense that they use the whole data set as such.
by Schultz and Adams  fuses a batch of measurements as a local grid to a global grid. The global grid in their work was incrementally built, but the method could be used just as well with a known map. A general way to use scan-matching algorithms for map matching is to compute the expected scan from the expected pose and use that as a reference scan.
Continuous localisation is an easy task using the above methods, given an initial pose, a perfect model (map), a static environment, a good estimate of movement (dead reckoning), and perfect measurement. Unfortunately, none of these is usually the case. Uncertainty is always present in real localisation, which is why localisation has been formulated in a probabilistic manner for decades1
A popular approach has been (and is) to use the Extended Kalman Filter (EKF) for pose tracking. EKF provides a minimum variance estimate of the state on the basis of a motion model and a measurement model. EKF uses a uni-modal distribution (represented by mean and variance) to track the pose. Intuitively, the motion transfers the mean and adds variance, while the measurement reduces the variance. Both the measurement and the map also have noise, which causes the result of matching the measurement to the map to be treated as a distribution as well (i.e. the measurement can be taken from an area dened by a mean and variance).
The method has been used since the late '80s and has been demonstrated to work with articial beacons (e.g. in the Automatic Guided Vehicle (AGV) application [14, 39] and later in the autonomous straddle carrier system ), as well as with the natural geometric beacons .
The scan-matching methods presented above (or any methods that can produce a pose based on matching a measurement to a map) can be used with EKF. For example, Sciele and Crowley  present similar work to that presented by Schultz and Adams, but they used EKF for tracking the pose. Additionally, Gutmann et al.
 use scan matching and EKF for tracking the pose.
EKF is a solid, ecient, and well-formulated method for continuous localisation, as long as everything goes as expected. The justications for not choosing EKF are: 1) it cannot solve the global localisation problem, and 2) EKF can only represent uni- modal pose distributions. The rst refers to a case in which the robot initially starts from an unknown pose within a known environment (or the pose is suddenly lost for some reason). The second is perhaps even more critical. Uni-modality means that given a time instant the pose is represented with a mean of the pose and its variance.
However, there are several possibilities of ending in a situation in which the pose can be just one of the many possibilities (represented by a number of mean-variance pairs, cf. Figure 3.6). In the mid-'90s Burgard et al.  proposed probability grids as an alternative approach to solving Bayesian localisation. The idea of a probability grid is to represent the posterior of the pose belief over all the possible poses in a discretised manner. In other words, the probability grid represents all the discrete values that the robot can be within the given environment. The probability grid approach is able to represent multi-modal distribution and it can be used for
1The formulation of the probabilistic continuous localisation was made in section 18.104.22.168.
global localisation. However, the method is computationally heavy, requiring plenty of memory. To represent a belief of a 2D pose, the probability grid is a 3D grid, with Nx*Ny*Na components. The number of components depends on the size of the environment and the desired resolution of the poses (e.g. Konolige and Chou used a 38-m x 30-m map with 10-cm and 2-deg resolution, which adds up to 20×106 poses). The prediction and update step must be calculated for each pose cell, which makes the algorithm extremely heavy in large environments. Konolige and Chou  used correlation to approximate the measurement likelihood. The algorithm was more ecient than the maximum likelihood version, but the number of poses still remains the same.
The most inuential method for this thesis is the one called Monte Carlo Localisation (MCL) presented by Fox et al. 2. MCL approximates the beliefs by using samples and basically the integration is performed in a Monte Carlo fashion .
MCL possesses the same advantages as grid localisation, but the main dierence is that the belief is approximated with samples that are concentrated around the most probable states. The advantage of MCL over a grid-based approach is that it can represent the posterior more accurately, with fewer computational requirements.
For more details on MCL see Section 22.214.171.124, where it was already introduced.
2See also section 126.96.36.199