Exploration of High-Dimensional Grids by Finite Automata

DOI10.4230/LIPIcs.ICALP.2019.139OpenAlexW2965530148MaRDI QIDQ5092342

Denis Pankratov, Stefan Dobrev, Jaroslav Opatrny, Lata Narayanan

Publication date: 21 July 2022

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

zbMATH Keywords

multi-agent systemsrobot explorationfinite state machineshigh-dimensional gridsrandomized agentssemi-synchronous and synchronous agents

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items

Exploration of dynamic networks: tight bounds on the number of agents

Cites Work

• Unnamed Item
• Online algorithms for searching and exploration in the plane
• How many ants does it take to find the food?
• Autonomous mobile robots with lights
• Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
• Remembering without memory: tree exploration by asynchronous oblivious robots
• On the two-dimensional cow search problem
• The power of a pebble: Exploring and mapping directed graphs
• Parallel searching in the plane
• On the linear search problem
• More on the linear search problem
• The return of the linear search problem
• Graph exploration by a finite automaton
• Revisiting the Problem of Searching on a Line
• Trade-offs between selection complexity and performance when searching the plane without communication
• Exploring an Infinite Space with Finite Memory Scouts
• A tight lower bound for semi-synchronous collaborative grid exploration
• Solving the ANTS Problem with Asynchronous Finite State Machines
• Group Search on the Line
• On Cumulative Sums of Random Variables
• Wireless evacuation on \(m\) rays with \(k\) searchers