Trade-offs between selection complexity and performance when searching the plane without communication

DOI10.1145/2611462.2611463MaRDI QIDQ2943625zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Calvin Newport, Tsvetomira Radeva, Nancy Lynch

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

biology-inspired algorithmsdistributed algorithmsMarkov chainsmobile agentssearch algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Abstract: We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the behavior of biological species, we argue that in addition to studying the {em time complexity} of solutions it is also important to study the {em selection complexity}, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. In more detail, we propose a new selection complexity metric $chi$, defined for algorithm $calA$ such that $chi(calA)=b+logell$, where $b$ is the number of memory bits used by each agent and $ell$ bounds the fineness of available probabilities (agents use probabilities of at least $1/2^{e}ll$). In this paper, we study the trade-off between the standard performance metric of speed-up, which measures how the expected time to find the target improves with $n$, and our new selection metric. In particular, consider $n$ agents searching for a treasure located at (unknown) distance $D$ from the origin (where $n$ is sub-exponential in $D$). For this problem, we identify $loglogD$ as a crucial threshold for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up of $(D^2/n+D)cdot{2}^{O(ell)}$ for $chi(calA)leq3loglogD+O(1)$. In particular, for $ellinO(1)$, the speed-up is asymptotically optimal. By comparison, the existing results for this problem [Feinerman et al.] that achieve similar speed-up require $chi(calA)=Omega(logD)$. We then show that this threshold is tight by describing a lower bound showing that if $chi(calA)<loglogD-omega(1)$, then with high probability the target is not found within $D^{2-o(1)}$ moves per agent. Hence, there is a sizable gap to the straightforward $Omega(D^2/n+D)$ lower bound in this setting.

Recommendations

• Searching without communicating: tradeoffs between performance and selection complexity
• The ANTS problem
• Collaborative search on the plane without communication
• Memory lower bounds for randomized collaborative search and implications for biology
• How many ants does it take to find the food?

Cited in

(11)

• Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract)
• Evacuating equilateral triangles and squares in the face-to-face model
• The ANTS problem
• Searching without communicating: tradeoffs between performance and selection complexity
• Evacuating from \(\ell_p\) unit disks in the wireless model
• Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
• Evacuating an equilateral triangle in the face-to-face model
• Exploration of High-Dimensional Grids by Finite Automata
• ANTS on a Plane
• Exploration of High-Dimensional Grids by Finite State Machines
• How many ants does it take to find the food?

This page was built for publication: Trade-offs between selection complexity and performance when searching the plane without communication

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