In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is  Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles.#R##N##R##N#We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of  exploration : within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task.#R##N##R##N#We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that there are  n -node trees where  i¾? ( n ) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. Finally, we prove that the size of the team is asymptotically  optimal : we show that there are trees of degree 3 whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots.
['Paola Flocchini', 'David Ilcinkas', 'Andrzej Pelc', 'Nicola Santoro']
Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots