Technical Report CIS9610

Title: Cooperative Covering by Ant-Robots using Evaporating Traces
Authors: Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein.
Abstract: Some insects are known to use chemicals called pheromones for various communication and coordination tasks. In this paper we investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown network. More specifically, we consider robots which leave chemical odor traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multia(ge)nt adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of cooperatively covering a graph, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. As opposed to existing traversal methods (e.g. DFS), our algorithms are adaptive: they will complete the traversal of the graph even if some of the agents die or the graph changes (edges/vertices added or deleted) during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time.
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 1996
To the main CS technical reports page

Computer science department, Technion