Technical Report MSC-2007-18

Title: Ant Robotics: Covering Continuous Domains by Multi-A(ge)nt Systems
Authors: Eliyahu Osherovich
Supervisors: Alfred Bruckstein
Abstract: In this work we present an algorithm for covering continuous connected domains by ant-like robots with very limited capabilities. The robots can mark visited places with pheromone marks and sense the level of the pheromone in their local neighborhood. In case of multiple robots these pheromone marks can be sensed by all robots and provide the only way of (indirect) communication between the robots. The robots are assumed to be memoryless, and to have no global information such as the domain map, their own position (either absolute or relative), total marked area percentage, maximal pheromone level, etc.. Despite the robots' simplicity, we show that they are able, by running a very simple rule of behavior, to ensure efficient covering of arbitrary connected domains, including non-planar and multidimensional ones. The novelty of our algorithm lies in the fact that, unlike previously proposed methods, our algorithm works on continuous domains without relying on some "induced" underlying graph, that effectively reduces the problem to a discrete case of graph covering. The algorithm guarantees complete coverage of any connected domain. We also prove that the algorithm is noise immune, i.e., it is able to cope with any initial pheromone profle (noise). In addition the algorithm provides a bounded constant time between two successive visits of the robot, and thus, is suitable for patrolling or surveillance applications.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2007
To the main CS technical reports page

Computer science department, Technion