A tight lower bound for semi-synchronous collaborative grid exploration

DOI10.1007/S00446-020-00369-0MaRDI QIDQ2220396zbMATH OpenOpenAlexFDO

Authors Jara Uitto, Roger Wattenhofer, Sebastian F. Brandt

Publication date 22 January 2021

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00446-020-00369-0

zbMATH Keywords

finite automatamobile robotsgraph explorationagents

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• A tight lower bound for semi-synchronous collaborative grid exploration
• On the minimum universal collectives of automata for plane labyrinths
• Exploring an infinite space with finite memory scouts
• scientific article; zbMATH DE number 2036576
• A general lower bound for collaborative tree exploration

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
• 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

(5)

• Exploring an infinite space with finite memory scouts
• A general lower bound for collaborative tree exploration
• A tight lower bound for semi-synchronous collaborative grid exploration
• Tight bounds for deterministic high-dimensional grid exploration
• scientific article; zbMATH DE number 7525472 (Why is no real title available?)

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 Q2220396)