The ANTS problem
From MaRDI portal
advice complexityantscentral place foragingcow-path problemmemory boundsmobile robotsonline algorithmsquorum sensingsearch algorithmssocial insectsspeed-up
Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15) (n)-person games, (n>2) (91A06) Animal behavior (92D50)
Abstract: 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 (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 + (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 extless{} extless{} 1, running in time O(log 1-- k (D +D 2 /k)) requires that agents have the capacity for storing (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.
Recommendations
Cites work
- \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
- \textit{Physarum} can compute shortest paths
- A biological solution to a fundamental distributed computing problem
- A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
- Automata, Languages and Programming
- Automaten in planaren Graphen
- Co-evolution of learning complexity and social foraging strategies
- Collaborative search on the plane without communication
- Collective tree exploration
- Distributed computing with advice: information sensitivity of graph coloring
- Distributed verification of minimum spanning trees
- Exploring Unknown Environments
- Exploring Unknown Undirected Graphs
- How many ants does it take to find the food?
- How many oblivious robots can explore a line
- Local MST computation with short advice
- Many Random Walks Are Faster Than One
- Memory lower bounds for randomized collaborative search and implications for biology
- Multiple random walks in random regular graphs
- Natural algorithms
- On the advice complexity of the k-server problem
- Online computation with advice
- Online searching with turn cost
- Optimal graph exploration without good maps
- Oracle size, a new measure of difficulty for communication tasks
- Parallel exhaustive search without coordination
- Parallel search with no coordination
- Proof labeling schemes
- Remembering without memory: tree exploration by asynchronous oblivious robots
- Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
- Searching in the plane
- Solving the ANTS problem with asynchronous finite state machines
- Stability of closed invariant sets of semidynamical systems. The method of sign definite Lyapunov functions
- Stone age distributed computing
- The harmonic k -server algorithm is competitive
- Tight bounds for the cover time of multiple random walks
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Towards a complexity theory for local distributed computing
- Trade-offs between selection complexity and performance when searching the plane without communication
- Tree exploration with logarithmic memory
- Undirected connectivity in log-space
Cited in
(19)- Multi-round cooperative search games with multiple players
- Searching without communicating: tradeoffs between performance and selection complexity
- Distributed house-hunting in ant colonies
- Trade-offs between selection complexity and performance when searching the plane without communication
- Treasure hunt with barely communicating agents
- scientific article; zbMATH DE number 2046040 (Why is no real title available?)
- Ant-inspired density estimation via random walks
- Memory lower bounds for randomized collaborative search and implications for biology
- Multi-round cooperative search games with multiple players
- ANTS on a Plane
- Solving the ANTS problem with asynchronous finite state machines
- scientific article; zbMATH DE number 6784996 (Why is no real title available?)
- How many ants does it take to find the food?
- The antenna problem
- Wireless evacuation on \(m\) rays with \(k\) searchers
- How Do Mobile Agents Benefit from Randomness?
- Weighted group search on the disk \& improved lower bounds for priority evacuation
- Weighted group search on the disk and improved LP-based lower bounds for priority evacuation
- How many ants does it take to find the food?
This page was built for publication: The ANTS problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401118)
