Technical Report CIS-2007-04

Title: Robust and Efficient Covering of Unknown Continuous Domains with Simple, Ant-Like A(ge)nts
Authors: Eliyahu Osherovich, Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein
Abstract: We propose a new ``Mark-Ant-Walk'' algorithm for robust and efficient covering of continuous domains by ant-like robots with very limited capabilities. The robots can mark places visited 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 information besides that mentioned above. 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. In addition we demonstrate various benefits of our

successive visits of the robot at the same location, that makes it suitable for patrolling.

Finally we provide a new theoretical bound on covering time of a wide family of such mark and walk algorithms.

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 CIS technical reports of 2007
To the main CS technical reports page

Computer science department, Technion