Dobrev, Stefan ;
Narayanan, Lata ;
Opatrny, Jaroslav ;
Pankratov, Denis
Exploration of HighDimensional Grids by Finite Automata
Abstract
We consider the problem of finding a treasure at an unknown point of an ndimensional infinite grid, n >= 3, by initially collocated finite automaton agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semisynchronous models [S. Brandt et al., 2018; Y. Emek et al., 2015]. It has been conjectured that n+1 randomized agents are necessary to solve this problem in the ndimensional grid [L. Cohen et al., 2017]. In this paper we disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an ndimensional grid for any n. Our algorithm is optimal in terms of the number of the agents. Our key insight is that a constant number of finite automaton agents can, by their positions and movements, implement a stack, which can store the path being explored. We also show how to implement our algorithm using: four randomized semisynchronous agents; four deterministic synchronous agents; or five deterministic semisynchronous agents.
We give a different algorithm that uses 4 deterministic semisynchronous agents for the 3dimensional grid. This is provably optimal, and surprisingly, matches the result for 2 dimensions. For n >= 4, the time complexity of the solutions mentioned above is exponential in distance D of the treasure from the starting point of the agents. We show that in the deterministic case, one additional agent brings the time down to a polynomial. Finally, we focus on algorithms that never venture much beyond the distance D. We describe an algorithm that uses O(sqrt{n}) semisynchronous deterministic agents that never go beyond 2D, as well as show that any algorithm using 3 synchronous deterministic agents in 3 dimensions, if it exists, must travel beyond Omega(D^{3/2}) from the origin.
BibTeX  Entry
@InProceedings{dobrev_et_al:LIPIcs:2019:10715,
author = {Stefan Dobrev and Lata Narayanan and Jaroslav Opatrny and Denis Pankratov},
title = {{Exploration of HighDimensional Grids by Finite Automata}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {139:1139:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10715},
URN = {urn:nbn:de:0030drops107153},
doi = {10.4230/LIPIcs.ICALP.2019.139},
annote = {Keywords: Multiagent systems, finite state machines, highdimensional grids, robot exploration, randomized agents, semisynchronous and synchronous agents}
}
04.07.2019
Keywords: 

Multiagent systems, finite state machines, highdimensional grids, robot exploration, randomized agents, semisynchronous and synchronous agents 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 