论文标题
确定性高维网格探索的紧密界限
Tight Bounds for Deterministic High-Dimensional Grid Exploration
论文作者
论文摘要
我们研究了探索由有限自动机管理的自主剂的定向网格的问题。在二维网格的情况下，在同步和半同步设置中都完全理解了在网格中探索网格或等效地找到隐藏宝藏的问题。对于更高的维度，Dobrev，Narayanan，Opatrny和Pankratov [iCalp'19]最近表明，令人惊讶的是，令人惊讶的是，（少数）恒定数量的代理人足以找到宝藏，独立于维度的数量，从而否认了Cohen，Emek，Emek，Louidor，louidor，uitto，uitto [sodasodosodaysodasodosodasode sodasodosody'' Dobrev等。作为一个公开的问题，他们是否可以提高其对代理数量的界限。我们在确定性有限自动机的肯定中回答了这个问题：我们表明，3个同步和4个半同步代理足以探索任何常数$ n $的$ n $二维网格。边界是最佳的，值得注意的是，在二维情况下，匹配的下限已经存在。 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).
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).
