Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:How Many Ants Does It Take To Find the Food?
Speaker:Jara Uitto
coming from:ETH Zürich
Speakers Bio: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.
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Friday, 16 January 2015
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Joel Rybicki
EMail:jrybicki@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Joel Rybicki, 01/07/2015 04:35 PM
  • Joel Rybicki, 01/07/2015 11:57 AM
  • Joel Rybicki, 01/06/2015 05:05 PM -- Created document.