Tight Bounds for Deterministic High-Dimensional Grid Exploration
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
34th International Symposium on Distributed Computing (DISC 2020), pp. 1-16, Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 179
Abstract
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP'19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA'17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an n-dimensional grid for any constant n. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case. Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).Description
Keywords
Other note
Citation
Brandt, S, Portmann, J & Uitto, J 2020, Tight Bounds for Deterministic High-Dimensional Grid Exploration. in 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, International Symposium on Distributed Computing, Virtual, Online, Germany, 12/10/2020. https://doi.org/10.4230/LIPIcs.DISC.2020.13