  We introduce the Ants Nearby Treasure Search (ANTS) problem, which models
natural cooperative foraging behavior such as that performed by ants around
their nest. In this problem, k probabilistic agents, initially placed at a
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
agents' 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.
We concentrate on the case in which agents cannot communicate while searching.
It is straightforward to see that the time until at least one agent finds the
target is at least $\Omega$(D + D 2 /k), even for very sophisticated agents,
with unrestricted memory. Our algorithmic analysis aims at establishing
connections between the time complexity and the initial knowledge held by
agents (e.g., regarding their total number k), as they commence the search. We
provide a range of both upper and lower bounds for the initial knowledge
required for obtaining fast running time. For example, we prove that log log k
+ $\Theta$(1) bits of initial information are both necessary and sufficient to
obtain asymptotically optimal running time, i.e., O(D +D 2 /k). We also we
prove that for every 0 \textless{} \textless{} 1, running in time O(log 1-- k
$\times$(D +D 2 /k)) requires that agents have the capacity for storing
$\Omega$(log k) different states as they leave the nest to start the search. To
the best of our knowledge, the lower bounds presented in this paper provide the
first non-trivial lower bounds on the memory complexity of probabilistic agents
in the context of search problems. We view this paper as a "proof of concept"
for a new type of interdisciplinary methodology. To fully demonstrate this
methodology, the theoretical tradeoff presented here (or a similar one) should
be combined with measurements of the time performance of searching ants.
