C-LOG: A Chamfer distance based algorithm for localisation in occupancy grid-maps

Abstract

A novel algorithm for localising a robot in a known two-dimensional environment is presented in this paper. An occupancy grid representing the environment is first converted to a distance function that encodes the distance to the nearest obstacle from any given location. A Chamfer distance based sensor model to associate observations from a laser ranger finder to the map of the environment without the need for ray tracing, data association, or feature extraction is presented. It is shown that the robot can be localised by solving a non-linear optimisation problem formulated to minimise the Chamfer distance with respect to the robot location. The proposed algorithm is able to perform well even when robot odometry is unavailable and requires only a single tuning parameter to operate even in highly dynamic environments. As such, it is superior than the state-of-the-art particle filter based solutions for robot localisation in occupancy grids, provided that an approximate initial location of the robot is available. Experimental results based on simulated and public domain datasets as well as data collected by the authors are used to demonstrate the effectiveness of the proposed algorithm.