A tight lower bound for semi-synchronous collaborative grid exploration
- PDF / 422,882 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 85 Downloads / 230 Views
A tight lower bound for semi-synchronous collaborative grid exploration Sebastian Brandt1 · Jara Uitto2 · Roger Wattenhofer1 Received: 4 July 2019 / Accepted: 7 January 2020 © The Author(s) 2020
Abstract Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. (Theor Comput Sci 608:255–267, 2015) in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look–compute–move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent’s automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration. Keywords Finite automata · Graph exploration · Mobile robots
1 Introduction
Sebastian Brandt [email protected]
Semi-Synchrony Recently, there has been a growing interest in studying constant memory agents performing exploration on an infinite grid. An infinite grid is a natural discrete version of a plane which disallows the bounded memory agents to make any use of the boundaries of the grid. Emek et al. [16] introduced a model where the agents are able to communicate by sensing each other’s states and showed a tight upper bound for the time needed for k agents to find a treasure1 at distance D. As the first step into the model, let us introduce the way that the semi-synchrony is defined. The time is divided into discrete time steps, and in each time step, an adversarially chosen subset of the agents performs a look–compute–move cycle in parallel. In each cycle, the chosen agents first sense the states of all the other agents in the same cell and then, determined by their transition function, either stay still or move to an adjacent grid cell. We point out that in every step, every agent performs the “look” action before any agent executes their “compute” step, i.e., agents sharing a cell and activated in the same time step see each other’s states before any of them executes a state transition. This definition allows an arbitrary discrepancy in the number of steps the agents perform but ensures that, whenever two agents meet, at least
Roger Wattenhofer [email protected]
1
Consider the problem of exploring an infinite grid with a set of mobile robots, ants, or agents. In practical applications, it is often desirable to make use of inexpensive and simple devices and therefore, a finite automaton is an attractive choice for modeling these agents. Furthermore, neither reliable communication nor synchronous time is always available and thus, distributed and
Data Loading...
