• Home
• Research
• » Publications
• » PhD
• Other

PhD Thesis

Supervisors: Dr Bruce MacDonald and Dr George Coghill

Research group: Robotics, group webpage

Topic: Qualitative topological coverage of unknown environments by mobile robots

I have passed my oral exam in November 2005 and submitted the final version of my thesis in Feburary 2006. You can obtain an electronic copy of the thesis from here.

Overview

In coverage navigation tasks, a robot is required to visit all reachable surfaces in an environment. This type of navigation is needed in a variety of applications such as vacuum cleaning, painting, humanitarian de-mining and foraging. To completely cover an unknown environment, the robot must use sensor information to avoid obstacles and to build a map to remember where it has been, so that it may return to cover remaining areas.

Coverage algorithms generally use grid-based maps for their spatial representation. This is due to the ease of representing covered areas on a grid. However, to create a coherent grid map, the robot needs to maintain a global metric consistency. Therefore, very accurate localisation is required.

An alternative approach is the qualitative topological map. Here, an environment is represented as a graph where landmarks are nodes, and edges the connectivity between landmarks. Animals, such as bees, birds and rats, also store their spatial information topologically. However, due to the qualitative nature of the representation, it is rather difficult to mark covered areas. This is because a landmark in a topological map does not directly correspond to any specific area in an environment.

The aim of my thesis was to develop algorithms that allow simultaneous exploration and coverage of unknown environments using a qualitative topological map. The problem of coverage information storage was tackled by embedding a cell decomposition within the topological map. Unlike existing cell decomposition methods, the cell boundary of this new decomposition is defined by large features. These large features are the landmarks of the topological map. The coverage algorithm was implemented and tested both in simulation and on a real robot. Landmark detection using simple thresholding and neural networks were investigated. Also, two new metrics for measuring performance of coverage experiments were proposed to evaluate the results of simulation and real robot experiments.

Results

Here are some results from a simulated robot equipped with 8 range sensors. The simulator is written in C++ on linux.

Testing is also done on a Khepera robot. The robot is controlled via a serial connection by a linux PC. The robot has an onboard microcontroller, but by using the PC for decision making, code from the simulator can be reused in experiments with the Khepera. The surfaces coloured in red are covered by the robot during the experiment.