A grid-based proposal for efficient global localisation of mobile robots

In this paper we present an extension to Monte Carlo localisation (MCL) to solve the global localisation problem. This extension is in the form of an efficient data-dependent proposal that can be used both for initialisation and re-initialisation after tracking failure or robot kidnapping. The proposal is a Gaussian mixture over a fixed grid of locations, each of which has a sensor structure similar to that of the robot. The robot measurements are matched to these structures to give the best-match orientation for each grid point. The mixture components are then centred on the grid locations and best-match orientations, with the component weights proportional to the best-match likelihoods. Empirical results illustrate that our MCL approach is more computationally efficient than standard MCL, and demonstrates faster recovery from localisation failures.