A tight lower bound for semi-synchronous collaborative grid exploration

DOI10.4230/LIPICS.DISC.2018.13MaRDI QIDQ5090903zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(10)

• Exploring an infinite space with finite memory scouts
• Energy consumption of group search on a line
• 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

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)