A tight lower bound for semi-synchronous collaborative grid exploration

DOI10.4230/LIPICS.DISC.2018.13zbMATH Open1497.68037OpenAlexW2898804437MaRDI QIDQ5090903FDOQ5090903

Authors: Sebastian F. Brandt, Jara Uitto, Roger Wattenhofer 

Publication date: 21 July 2022

Full work available at URL: http://dblp.uni-trier.de/db/conf/wdag/disc2018.html#BrandtUW18

Recommendations

• A tight lower bound for semi-synchronous collaborative grid exploration
• Fast collaborative graph exploration
• A general lower bound for collaborative tree exploration
• A general lower bound for collaborative tree exploration
• Distributed exploration of dynamic rings

zbMATH Keywords

finite automatamobile robotsgraph exploration

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42) Distributed systems (68M14)

Cites Work

• Searching in the plane
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Exploring an unknown graph
• Title not available (Why is that?)
• Collaborative search on the plane without communication
• Tree exploration with little memory
• Exploring Unknown Environments
• Solving the ANTS problem with asynchronous finite state machines
• STACS 2004
• Automata and Labyrinths
• A tight lower bound for the capture time of the cops and robbers game
• Optimal constrained graph exploration
• Group search on the line
• Title not available (Why is that?)
• How many ants does it take to find the food?
• Title not available (Why is that?)
• Exploring an infinite space with finite memory scouts
• Title not available (Why is that?)
• Undirected Graph Exploration with ⊝(log log n) Pebbles

Cited In (10)

• Weighted group search on a line \& implications to the priority evacuation problem
• A general lower bound for collaborative tree exploration
• A tight lower bound for semi-synchronous collaborative grid exploration
• Building a nest by an automaton
• Graph exploration by a deterministic memoryless automaton with pebbles
• Algorithms for \(p\)-Faulty Search on a half-line
• Exploration of High-Dimensional Grids by Finite State Machines
• Exploration of High-Dimensional Grids by Finite Automata
• Exploring an infinite space with finite memory scouts
• Energy consumption of group search on a line

This page was built for publication: A tight lower bound for semi-synchronous collaborative grid exploration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090903)