Distributed covering by ant-robots using evaporating traces

Ants and other insects are known to use chemicals called pheromones for var ious communication and coordination tasks. In this paper, we investigate th e ability of a group of robots, that communicate by leaving traces, to perf orm the task of cleaning the floor of an un-mapped building, or any task th at requires the traversal of an unknown region. More specifically, we consi der robots which leave chemical odor traces that evaporate with time, and a re able to evaluate the strength of smell at every point they reach, with s ome measurement error. Our abstract model is a decentralized multiagent ada ptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distribute d fashion, using smell traces that gradually vanish with time, and show tha t they all result in eventual task completion, two of them in a time polyno mial in the number of tiles. As opposed to existing traversal methods (e.g. , depth first search), our algorithms are adaptive: they will complete the traversal of the graph even if some of the a(ge)nts die or the graph change s (edges/vertices added or deleted) during the execution, as long as the gr aph stays connected. Another advantage of our agent interaction processes i s the ability of agents to use noisy information at the cost of longer cove r time.