Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication

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 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. In more detail, we propose a new selection complexity metric \chi, defined for algorithm A such that \chi(A) = b + log p, where b is the number of memory bits used by each agent and p bounds the range of available probabilities (agents use probabilities in a range lower bounded by 1/2^p). In this paper, we study the trade-off between the standard performance metric of speed-up 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 log log D as a crucial threshold for our selection complexity metric. We first prove a lower bound showing that if \chi(A) < log log D - omega(1), then in D^{2-o(1)} rounds or less the agents do not find the target with high probability. This represents a sizable gap with the straightforward \Omega(D^2/n + D) bound on speed-up in this setting. We then prove that this threshold is (near) tight, by describing a new upper bound that achieves a near-optimal speed-up of (D^2/n +D) 2^{O(p)} for \chi <= 3 log log D + O(1). In particular, for p \in O(1), the speed-up is asymptotically optimal. By comparison, the existing results for this problem that achieve similar speed-ups require a \chi = \Omega(log D).