Memory lower bounds for randomized collaborative search and implications for biology

DOI10.1007/978-3-642-33651-5_5MaRDI QIDQ4909402zbMATH OpenOpenAlexFDO

Authors Ofer Feinerman, Amos Korman

Publication date 13 March 2013

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

Full work available at URL https://arxiv.org/abs/1205.4545, https://hal.inria.fr/hal-01241102/file/Ants-memory-new.pdf

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

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