Searching without communicating: tradeoffs between performance and selection complexity

Abstract

© 2016, Springer-Verlag Berlin Heidelberg. 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 time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature due to selective pressures. Intuitively, the larger the χ value, the more complicated the algorithm, and therefore the less likely it is to arise in nature. In more detail, we propose a new selection complexity metric χ, defined for algorithm A such that χ(A) = b+ log ℓ, where b is the number of memory bits used by each agent and ℓ bounds the fineness of available probabilities (agents use probabilities of at least 1 / 2 ℓ). 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. Our goal is to determine the thresholds of algorithmic complexity needed to enable efficient search. In particular, consider n agents searching for a treasure located within some distance D from the origin (where n is sub-exponential in D). For this problem, we identify the threshold log log D to be crucial for our selection complexity metric. We first prove a new upper bound that achieves a near-optimal speed-up for χ(A) ≈ log log D+ O(1). In particular, for ℓ∈ O(1) , the speed-up is asymptotically optimal. By comparison, the existing results for this problem (Feinerman et al.) that achieve similar speed-up require χ(A) = Ω(log D). We then show that this threshold is tight by describing a lower bound showing that if χ(A) < log log D- ω(1) , then with high probability the target is not found in D2-o(1) moves per agent. Hence, there is a sizable gap with respect to the straightforward Ω(D2/ n+ D) lower bound in this setting.