Collaborative search on the plane without communication

DOI10.1145/2332432.2332444zbMath1301.68230arXiv1205.2170OpenAlexW2053831174MaRDI QIDQ2933778

Jean-Sébastien Sereni, Zvi Lotker, Amos Korman, Ofer Feinerman

Publication date: 5 December 2014

Published in: Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.2170

zbMATH Keywords

online algorithmssearch algorithmsmobile robotssocial insectsspeed-upantsuniform algorithmscow-path problemcollective foraging

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) (n)-person games, (n>2) (91A06) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Animal behavior (92D50) Distributed algorithms (68W15) Agent technology and artificial intelligence (68T42)

Related Items (29)

Collaboration Without Communication: Evacuating Two Robots from a Disk ⋮ Unnamed Item ⋮ Treasure Hunt with Advice ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Evacuating an Equilateral Triangle in the Face-to-Face Model ⋮ ANTS on a Plane ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ How many ants does it take to find the food? ⋮ 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 ⋮ Evacuating equilateral triangles and squares in the face-to-face model ⋮ Fuzzy Optimal Search Plan for N-Dimensional Randomly Moving Target ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Parabolic spiral search plan for a randomly located target in the plane ⋮ Lower bounds for searching robots, some faulty ⋮ Linear search by a pair of distinct-speed robots ⋮ Search on a line with faulty robots ⋮ Optimal Distributed Searching in the Plane with and Without Uncertainty ⋮ The Synergy of Finite State Machines ⋮ Linear Search by a Pair of Distinct-Speed Robots ⋮ Group search of the plane with faulty robots ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Extreme hitting probabilities for diffusion* ⋮ Two-agent tree evacuation

This page was built for publication: Collaborative search on the plane without communication