Jara Uitto is a PhD student in the Distributed Computing Group in ETH Zürich headed by Professor Roger Wattenhofer. His research interests include distributed graph algorithms, weak models of computation, and recommendation systems.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

30 Minutes

Saarbrücken

In the Ants Nearby Treasure Search (ANTS) problem n mobile agents, initially placed at the origin of an infinite grid, collaboratively search for an adversarially hidden treasure. We consider variants of this model, where the agents are controlled by deterministic/randomized finite or pushdown automata and are able to communicate with each other through constant-size messages. We show that the minimum number of agents required to solve the ANTS problem crucially depends on the computational capabilities of the agents as well as the timing parameters of the execution environment, i.e., whether the agents' actions are synchronized. We give lower and upper bounds for all aforementioned scenarios.

Joel Rybicki

--email hidden

passcode not visible

logged in users only