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

agentsfinite automatagraph explorationmobile robots

Mathematics Subject Classification ID

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

Review text

The paper is related to the problem of exploring an infinite grid with a set of agents. The main result is the proof of the fact that three semi-synchronous agents controlled by a finite automaton are not sufficient to explore the infinite grid. This main result involves a complex theoretical model that is nicely described in detail in the paper.

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

• 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 an infinite space with finite memory scouts
• Exploring an unknown graph
• Exploring Unknown Environments
• Group search on the line
• How many ants does it take to find the food?
• 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?)
• Optimal constrained graph exploration
• Searching in the plane
• Solving the ANTS problem with asynchronous finite state machines
• STACS 2004
• Tree exploration with little memory
• Undirected Graph Exploration with ⊝(log log n) Pebbles

Cited in

(8)

• On the minimum universal collectives of automata for plane labyrinths
• Exploring an infinite space with finite memory scouts
• Building a nest by an automaton
• A tight lower bound for semi-synchronous collaborative grid exploration
• Exploration of High-Dimensional Grids by Finite Automata
• A general lower bound for collaborative tree exploration
• Tight bounds for deterministic high-dimensional grid exploration
• Busy agents 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 Q2220396)