Collaborative search on the plane without communication
From MaRDI portal
antscollective foragingcow-path problemmobile robotsonline algorithmssearch algorithmssocial insectsspeed-upuniform algorithms
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 generalize the classical cow-path problem [7, 14, 38, 39] into a question that is relevant for collective foraging in animal groups. Specifically, we consider a setting in which k identical (probabilistic) agents, initially placed at some central location, collectively search for a treasure in the two-dimensional plane. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both k and D, where D is the distance between the central location and the target. This is biologically motivated by cooperative, central place foraging such as performed by ants around their nest. In this type of search there is a strong preference to locate nearby food sources before those that are further away. Our focus is on trying to find what can be achieved if communication is limited or altogether absent. Indeed, to avoid overlaps agents must be highly dispersed making communication difficult. Furthermore, if agents do not commence the search in synchrony then even initial communication is problematic. This holds, in particular, with respect to the question of whether the agents can communicate and conclude their total number, k. It turns out that the knowledge of k by the individual agents is crucial for performance. Indeed, it is a straightforward observation that the time required for finding the treasure is (D + D 2 /k), and we show in this paper that this bound can be matched if the agents have knowledge of k up to some constant approximation. We present an almost tight bound for the competitive penalty that must be paid, in the running time, if agents have no information about k. Specifically, on the negative side, we show that in such a case, there is no algorithm whose competitiveness is O(log k). On the other hand, we show that for every constant , there exists a rather simple uniform search algorithm which is -competitive. In addition, we give a lower bound for the setting in which agents are given some estimation of k. As a special case, this lower bound implies that for any constant , if each agent is given a (one-sided) -approximation to k, then the competitiveness is (log k). Informally, our results imply that the agents can potentially perform well without any knowledge of their total number k, however, to further improve, they must be given a relatively good approximation of k. Finally, we propose a uniform algorithm that is both efficient and extremely simple suggesting its relevance for actual biological scenarios.
Recommendations
Cited in
(40)- Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
- Linear search by a pair of distinct-speed robots
- Lower bounds for searching robots, some faulty
- Search on a line with faulty robots
- Weighted group search on a line \& implications to the priority evacuation problem
- Two-agent tree evacuation
- Evacuating equilateral triangles and squares in the face-to-face model
- A tight lower bound for semi-synchronous collaborative grid exploration
- Group search of the plane with faulty robots
- The ANTS problem
- Searching without communicating: tradeoffs between performance and selection complexity
- Parabolic spiral search plan for a randomly located target in the plane
- On the advantages of non-cooperative behavior in agent populations
- Distributed house-hunting in ant colonies
- Optimal distributed searching in the plane with and without uncertainty
- Linear search by a pair of distinct-speed robots
- Trade-offs between selection complexity and performance when searching the plane without communication
- Fuzzy optimal search plan for n-dimensional randomly moving target
- Evacuating an equilateral triangle in the face-to-face model
- Treasure hunt with barely communicating agents
- Lower and upper competitive bounds for online directed graph exploration
- Treasure hunt with advice
- Ant-inspired density estimation via random walks
- Optimal cooperative searching using purely repulsive interactions
- Memory lower bounds for randomized collaborative search and implications for biology
- A tight lower bound for semi-synchronous collaborative grid exploration
- The Synergy of Finite State Machines
- ANTS on a Plane
- Solving the ANTS problem with asynchronous finite state machines
- Collaboration without communication: evacuating two robots from a disk
- How many ants does it take to find the food?
- Extreme hitting probabilities for diffusion*
- Search and rescue on the line
- Extreme statistics of superdiffusive Lévy flights and every other Lévy subordinate Brownian motion
- Algorithms for \(p\)-Faulty Search on a half-line
- Tight bounds for deterministic high-dimensional grid exploration
- On the limits of information spread by memory-less agents
- Searching in the plane
- The beachcombers' problem: walking and searching with mobile robots
- How many ants does it take to find the food?
This page was built for publication: Collaborative search on the plane without communication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933778)
