Tom Duckett

Concurrent Map Building and Self-Localisation for Mobile Robot Navigation

Ph.D. Thesis, Department of Computer Science, University of Manchester, 2000.


This thesis addresses the problem of navigation by a mobile robot operating in large, real world environments which have not been modified for the purpose of robot navigation. Maps are essential for mobile robot control in complex environments, being needed for self-localisation, path planning and human-robot interaction. In attempting to navigate in unknown environments, a self-governing robot is faced with a fundamental dilemma: to explore and build maps of uncharted territory, the robot needs to know its location, but in order to know its location, the robot needs a map.

A unified solution to the problems of simultaneous map building and self-localisation is presented, which is embedded in a hybrid deliberative-reactive control architecture. A particular contribution of the work is that all of the environment and location models, feature models and sensor-motor competences required for navigation are acquired independently by the robot. The learning techniques include self-organisation, where no teaching signal is required, and self-supervised learning, where all of the training examples are generated by the robot. Consequently, the new system is able to build its own maps and navigate in many different, indoor environments that are unfamiliar, without requiring intervention by a human operator.

During an exploration phase, the robot builds a graph-like representation of its environment, in which each location is identified by a description of the robot's sensory information known as a landmark. To determine an appropriate landmark recognition mechanism, an experimental procedure was developed which permitted different algorithms to be compared under identical experimental conditions. With this method, existing approaches to landmark recognition were evaluated, and a new self-localisation system was developed. To overcome problems such as perceptual aliasing - the fact that landmarks may not be unique to individual places - a self-localisation algorithm was developed which accumulates sensory evidence over time so that the robot can recover its position even after becoming lost. To maintain geometric consistency in the robot's map, an optimisation algorithm was developed, which is proved to converge to a globally optimal solution. To explore unknown environments, an artificial neural network was trained to recognise areas of uncharted territory. Quantitative performance measures were applied throughout the work, guiding the development of the new algorithms and allowing the effects of individual system components to be investigated.

Finally, the research was validated by building a complete, self-navigating mobile robot capable of operation in complex, untreated environments of several hundred metres squared. In this system, human intervention is only required to specify a goal location, and all processing is carried out in real-time on board the robot, thereby increasing the autonomy of the robot.


[pdf] [ps.gz]


  AUTHOR = "Tom Duckett",
  TITLE = "Concurrent Map Building and Self-Localisation for Mobile Robot Navigation",
  SCHOOL = "Department of Computer Science, University of Manchester",
  YEAR = 2000