Memory lower bounds for randomized collaborative search and implications for biology

DOI10.1007/978-3-642-33651-5_5zbMATH Open1321.68415arXiv1205.4545OpenAlexW1844529830MaRDI QIDQ4909402FDOQ4909402

Authors: Ofer Feinerman, Amos Korman 

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Initial knowledge regarding group size can be crucial for collective performance. We study this relation in the context of the {em Ants Nearby Treasure Search (ANTS)} problem cite{FKLS}, which models natural cooperative foraging behavior such as that performed by ants around their nest. In this problem, $k$ (probabilistic) agents, initially placed at some central location, collectively search for a treasure on the two-dimensional grid. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both $k$ and $D$, where $D$ is the (unknown) distance between the central location and the target. It is easy to see that $T=Omega(D+D^2/k)$ time units are necessary for finding the treasure. Recently, it has been established that $O(T)$ time is sufficient if the agents know their total number $k$ (or a constant approximation of it), and enough memory bits are available at their disposal cite{FKLS}. In this paper, we establish lower bounds on the agent memory size required for achieving certain running time performances. To the best our knowledge, these bounds are the first non-trivial lower bounds for the memory size of probabilistic searchers. For example, for every given positive constant $epsilon$, terminating the search by time $O(lo{g}^{1-epsilon}kcdotT)$ requires agents to use $Omega(loglogk)$ memory bits. Such distributed computing bounds may provide a novel, strong tool for the investigation of complex biological systems.

Full work available at URL: https://arxiv.org/abs/1205.4545

Recommendations

• The ANTS problem
• Collaborative search on the plane without communication
• How many ants does it take to find the food?
• How many ants does it take to find the food?
• Solving the ANTS problem with asynchronous finite state machines

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Animal behavior (92D50) Distributed algorithms (68W15)

Cited In (16)

• The Synergy of Finite State Machines
• Collaboration without communication: evacuating two robots from a disk
• ANTS on a Plane
• Two-agent tree evacuation
• Memoryless search algorithms in a network with faulty advice
• Ant-inspired density estimation via random walks
• An algorithmic approach to collective behavior
• How many ants does it take to find the food?
• Identification Rate, Search and Memory Complexity Tradeoff: Fundamental Limits
• Lower and upper competitive bounds for online directed graph exploration
• Searching without communicating: tradeoffs between performance and selection complexity
• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• How many ants does it take to find the food?
• Querying with Uncertainty
• The ANTS problem
• Treasure hunt with advice

This page was built for publication: Memory lower bounds for randomized collaborative search and implications for biology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909402)