The ANTS problem

DOI10.1007/s00446-016-0285-8zbMath1409.68295arXiv1701.02555OpenAlexW2538997421MaRDI QIDQ2401118

Ofer Feinerman, Amos Korman

Publication date: 31 August 2017

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmssearch algorithmsmobile robotsquorum sensingadvice complexitysocial insectsspeed-upcentral place foragingantsmemory boundscow-path problem

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 (4)

Multi-round cooperative search games with multiple players ⋮ ANTS on a Plane ⋮ Unnamed Item ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers

Cites Work

• Unnamed Item
• Unnamed Item
• Tight bounds for the cover time of multiple random walks
• Online computation with advice
• Local MST computation with short advice
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• Optimal graph exploration without good maps
• Remembering without memory: tree exploration by asynchronous oblivious robots
• Automaten in planaren Graphen
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• Co-evolution of learning complexity and social foraging strategies
• Parallel search with no coordination
• Stability of closed invariant sets of semidynamical systems. The method of sign definite Lyapunov functions
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• How many oblivious robots can explore a line
• Distributed verification of minimum spanning trees
• Proof labeling schemes
• Distributed computing with advice: information sensitivity of graph coloring
• Beeping a maximal independent set
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Online searching with turn cost
• Collaborative search on the plane without communication
• Trade-offs between selection complexity and performance when searching the plane without communication
• On the Advice Complexity of the k-Server Problem
• Multiple Random Walks in Random Regular Graphs
• A Biological Solution to a Fundamental Distributed Computing Problem
• Tree exploration with logarithmic memory
• Collective tree exploration
• Undirected connectivity in log-space
• Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Solving the ANTS Problem with Asynchronous Finite State Machines
• Stone age distributed computing
• Oracle size
• Many Random Walks Are Faster Than One
• Parallel exhaustive search without coordination
• Towards a complexity theory for local distributed computing
• The harmonic k -server algorithm is competitive
• How Many Ants Does It Take to Find the Food?
• Automata, Languages and Programming

This page was built for publication: The ANTS problem